Index: boot/Makefile.common =================================================================== --- boot/Makefile.common (revision 371cb6c7c5c610699e4f24e912dba3d86953e6f8) +++ boot/Makefile.common (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -151,4 +151,5 @@ RD_APPS_NON_ESSENTIAL = \ + $(USPACE_PATH)/app/bithenge/bithenge \ $(USPACE_PATH)/app/blkdump/blkdump \ $(USPACE_PATH)/app/bnchmark/bnchmark \ Index: uspace/Makefile =================================================================== --- uspace/Makefile (revision 371cb6c7c5c610699e4f24e912dba3d86953e6f8) +++ uspace/Makefile (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -35,4 +35,5 @@ DIRS = \ app/bdsh \ + app/bithenge \ app/blkdump \ app/bnchmark \ Index: uspace/app/bithenge/Makefile =================================================================== --- uspace/app/bithenge/Makefile (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/app/bithenge/Makefile (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,48 @@ +# +# Copyright (c) 2012 Sean Bartell +# All rights reserved. +# +# Redistribution and use in source and binary forms, with or without +# modification, are permitted provided that the following conditions +# are met: +# +# - Redistributions of source code must retain the above copyright +# notice, this list of conditions and the following disclaimer. +# - Redistributions in binary form must reproduce the above copyright +# notice, this list of conditions and the following disclaimer in the +# documentation and/or other materials provided with the distribution. +# - The name of the author may not be used to endorse or promote products +# derived from this software without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR +# IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES +# OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. +# IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, +# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT +# NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF +# THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +# + +USPACE_PREFIX = ../.. +LIBS = $(LIBBLOCK_PREFIX)/libblock.a +EXTRA_CFLAGS = -I$(LIBBLOCK_PREFIX) -D__HELENOS__ -Ihelenos +BINARY = bithenge + +SOURCES = \ + helenos/block.c \ + blob.c \ + compound.c \ + expression.c \ + file.c \ + print.c \ + script.c \ + sequence.c \ + source.c \ + test.c \ + transform.c \ + tree.c + +include $(USPACE_PREFIX)/Makefile.common Index: uspace/app/bithenge/Makefile.linux =================================================================== --- uspace/app/bithenge/Makefile.linux (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/app/bithenge/Makefile.linux (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,56 @@ +# +# Copyright (c) 2012 Sean Bartell +# All rights reserved. +# +# Redistribution and use in source and binary forms, with or without +# modification, are permitted provided that the following conditions +# are met: +# +# - Redistributions of source code must retain the above copyright +# notice, this list of conditions and the following disclaimer. +# - Redistributions in binary form must reproduce the above copyright +# notice, this list of conditions and the following disclaimer in the +# documentation and/or other materials provided with the distribution. +# - The name of the author may not be used to endorse or promote products +# derived from this software without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR +# IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES +# OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. +# IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, +# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT +# NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF +# THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +# + +CFLAGS += -fexec-charset=UTF-8 -finput-charset=UTF-8 -std=gnu99 -pipe +CFLAGS += -Wall -Wextra -Werror -Wno-clobbered -Wno-unused-parameter -Wmissing-prototypes -Werror-implicit-function-declaration -Wwrite-strings +CFLAGS += -g +CFLAGS += -Ilinux + +BINARY = bithenge + +SOURCES = \ + blob.c \ + compound.c \ + expression.c \ + file.c \ + print.c \ + script.c \ + sequence.c \ + source.c \ + test.c \ + transform.c \ + tree.c + +OBJECTS := $(addsuffix .o,$(basename $(SOURCES))) + +$(BINARY): $(OBJECTS) + $(CC) -o $@ $^ + +clean: + find . -name '*.o' -follow -exec rm \{\} \; + rm -f $(BINARY) Index: uspace/app/bithenge/blob.c =================================================================== --- uspace/app/bithenge/blob.c (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/app/bithenge/blob.c (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,490 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Raw binary blobs. + */ + +#include +#include +#include +#include "blob.h" +#include "os.h" +#include "tree.h" + +/** Initialize a random access blob. + * @memberof bithenge_blob_t + * @param[out] blob The blob to initialize. + * @param[in] ops Operations providing random access support. This pointer must + * be valid until the blob is destroyed. + * @return EOK on success or an error code from errno.h. + */ +int bithenge_init_random_access_blob(bithenge_blob_t *blob, + const bithenge_random_access_blob_ops_t *ops) +{ + assert(blob); + assert(ops); + assert(ops->destroy); + assert(ops->read || ops->read_bits); + assert(ops->size); + + blob->base.type = BITHENGE_NODE_BLOB; + blob->base.refs = 1; + blob->base.blob_ops = ops; + return EOK; +} + +static int sequential_buffer(bithenge_sequential_blob_t *blob, aoff64_t end) +{ + bool need_realloc = false; + while (end > blob->buffer_size) { + blob->buffer_size = max(4096, 2 * blob->buffer_size); + need_realloc = true; + } + if (need_realloc) { + char *buffer = realloc(blob->buffer, blob->buffer_size); + if (!buffer) + return ENOMEM; + blob->buffer = buffer; + } + aoff64_t size = end - blob->data_size; + int rc = blob->ops->read(blob, blob->buffer + blob->data_size, &size); + if (rc != EOK) + return rc; + blob->data_size += size; + return EOK; +} + +static inline bithenge_sequential_blob_t *blob_as_sequential( + bithenge_blob_t *base) +{ + return (bithenge_sequential_blob_t *)base; +} + +static inline bithenge_blob_t *sequential_as_blob( + bithenge_sequential_blob_t *blob) +{ + return &blob->base; +} + +static int sequential_size(bithenge_blob_t *base, aoff64_t *size) +{ + bithenge_sequential_blob_t *blob = blob_as_sequential(base); + int rc; + if (blob->ops->size) { + rc = blob->ops->size(blob, size); + if (rc == EOK) + return EOK; + } + rc = sequential_buffer(blob, blob->buffer_size); + if (rc != EOK) + return rc; + while (blob->data_size == blob->buffer_size) { + rc = sequential_buffer(blob, 2 * blob->buffer_size); + if (rc != EOK) + return rc; + } + *size = blob->data_size; + return EOK; +} + +static int sequential_read(bithenge_blob_t *base, aoff64_t offset, + char *buffer, aoff64_t *size) +{ + bithenge_sequential_blob_t *blob = blob_as_sequential(base); + aoff64_t end = offset + *size; + if (end > blob->data_size) { + int rc = sequential_buffer(blob, end); + if (rc != EOK) + return rc; + } + if (offset > blob->data_size) + return EINVAL; + *size = min(*size, blob->data_size - end); + memcpy(buffer, blob->buffer + offset, *size); + return EOK; +} + +static void sequential_destroy(bithenge_blob_t *base) +{ + bithenge_sequential_blob_t *blob = blob_as_sequential(base); + free(blob->buffer); + blob->ops->destroy(blob); +} + +static const bithenge_random_access_blob_ops_t sequential_ops = { + .size = sequential_size, + .read = sequential_read, + .destroy = sequential_destroy, +}; + +/** Initialize a sequential blob. + * @memberof bithenge_sequential_blob_t + * @param[out] blob The blob to initialize. + * @param[in] ops Operations providing sequential access support. This pointer + * must be valid until the blob is destroyed. + * @return EOK on success or an error code from errno.h. + */ +int bithenge_init_sequential_blob(bithenge_sequential_blob_t *blob, + const bithenge_sequential_blob_ops_t *ops) +{ + assert(blob); + assert(ops); + assert(ops->destroy); + assert(ops->read); + // ops->size is optional + + int rc = bithenge_init_random_access_blob(sequential_as_blob(blob), + &sequential_ops); + if (rc != EOK) + return rc; + blob->ops = ops; + blob->buffer = NULL; // realloc(NULL, ...) works like malloc + blob->buffer_size = 0; + blob->data_size = 0; + return EOK; +} + +typedef struct { + bithenge_blob_t base; + const char *buffer; + size_t size; + bool needs_free; +} memory_blob_t; + +static inline memory_blob_t *blob_as_memory(bithenge_blob_t *base) +{ + return (memory_blob_t *)base; +} + +static inline bithenge_blob_t *memory_as_blob(memory_blob_t *blob) +{ + return &blob->base; +} + +static int memory_size(bithenge_blob_t *base, aoff64_t *size) +{ + memory_blob_t *blob = blob_as_memory(base); + *size = blob->size; + return EOK; +} + +static int memory_read(bithenge_blob_t *base, aoff64_t offset, char *buffer, + aoff64_t *size) +{ + memory_blob_t *blob = blob_as_memory(base); + if (offset > blob->size) + return ELIMIT; + *size = min(*size, blob->size - offset); + memcpy(buffer, blob->buffer + offset, *size); + return EOK; +} + +static void memory_destroy(bithenge_blob_t *base) +{ + memory_blob_t *blob = blob_as_memory(base); + if (blob->needs_free) + free((void *)blob->buffer); + free(blob); +} + +static const bithenge_random_access_blob_ops_t memory_ops = { + .size = memory_size, + .read = memory_read, + .destroy = memory_destroy, +}; + +/** Create a blob node from data. Unlike with @a + * bithenge_blob_t::bithenge_new_blob_from_buffer, the data is copied into a + * new buffer and the original data can be changed after this call. The blob + * must be freed with @a bithenge_node_t::bithenge_node_destroy after it is + * used. + * @memberof bithenge_blob_t + * @param[out] out Stores the created blob node. + * @param[in] data The data. + * @param len The length of the data. + * @return EOK on success or an error code from errno.h. */ +int bithenge_new_blob_from_data(bithenge_node_t **out, const void *data, + size_t len) +{ + int rc; + assert(data || !len); + + memory_blob_t *blob = malloc(sizeof(*blob)); + if (!blob) + return ENOMEM; + rc = bithenge_init_random_access_blob(memory_as_blob(blob), + &memory_ops); + if (rc != EOK) { + free(blob); + return rc; + } + char *buffer = malloc(len); + if (!buffer) { + free(blob); + return rc; + } + memcpy(buffer, data, len); + blob->buffer = buffer; + blob->size = len; + blob->needs_free = true; + *out = bithenge_blob_as_node(memory_as_blob(blob)); + return EOK; +} + +/** Create a blob node from a buffer. The buffer must exist as long as the blob + * does. The blob must be freed with @a bithenge_node_t::bithenge_node_destroy + * after it is used. + * @memberof bithenge_blob_t + * @param[out] out Stores the created blob node. + * @param[in] buffer The buffer, which must not be changed until the blob is + * destroyed. + * @param len The length of the data. + * @param needs_free If true, the buffer will be freed with free() if this + * function fails or the blob is destroyed. + * @return EOK on success or an error code from errno.h. */ +int bithenge_new_blob_from_buffer(bithenge_node_t **out, const void *buffer, + size_t len, bool needs_free) +{ + int rc; + assert(buffer || !len); + + memory_blob_t *blob = malloc(sizeof(*blob)); + if (!blob) + return ENOMEM; + rc = bithenge_init_random_access_blob(memory_as_blob(blob), + &memory_ops); + if (rc != EOK) { + free(blob); + return rc; + } + blob->buffer = buffer; + blob->size = len; + blob->needs_free = needs_free; + *out = bithenge_blob_as_node(memory_as_blob(blob)); + return EOK; +} + +typedef struct { + bithenge_blob_t base; + bithenge_blob_t *source; + aoff64_t offset; + aoff64_t size; + bool size_matters; +} subblob_t; + +static inline subblob_t *blob_as_subblob(bithenge_blob_t *base) +{ + return (subblob_t *)base; +} + +static inline bithenge_blob_t *subblob_as_blob(subblob_t *blob) +{ + return &blob->base; +} + +static int subblob_size(bithenge_blob_t *base, aoff64_t *size) +{ + subblob_t *blob = blob_as_subblob(base); + if (blob->size_matters) { + *size = blob->size; + return EOK; + } else { + int rc = bithenge_blob_size(blob->source, size); + *size -= blob->offset; + return rc; + } +} + +static int subblob_read(bithenge_blob_t *base, aoff64_t offset, + char *buffer, aoff64_t *size) +{ + subblob_t *blob = blob_as_subblob(base); + if (blob->size_matters) { + if (offset > blob->size) + return EINVAL; + *size = min(*size, blob->size - offset); + } + offset += blob->offset; + return bithenge_blob_read(blob->source, offset, buffer, size); +} + +static int subblob_read_bits(bithenge_blob_t *base, aoff64_t offset, + char *buffer, aoff64_t *size, bool little_endian) +{ + subblob_t *blob = blob_as_subblob(base); + if (blob->size_matters) { + if (offset > blob->size) + return EINVAL; + *size = min(*size, blob->size - offset); + } + offset += blob->offset; + return bithenge_blob_read_bits(blob->source, offset, buffer, size, + little_endian); +} + +static void subblob_destroy(bithenge_blob_t *base) +{ + subblob_t *blob = blob_as_subblob(base); + bithenge_blob_dec_ref(blob->source); + free(blob); +} + +static const bithenge_random_access_blob_ops_t subblob_ops = { + .size = subblob_size, + .read = subblob_read, + .read_bits = subblob_read_bits, + .destroy = subblob_destroy, +}; + +static bool is_subblob(bithenge_blob_t *blob) +{ + return blob->base.blob_ops == &subblob_ops; +} + +static int new_subblob(bithenge_node_t **out, bithenge_blob_t *source, + aoff64_t offset, aoff64_t size, bool size_matters) +{ + assert(out); + assert(source); + int rc; + subblob_t *blob = 0; + + if (is_subblob(source)) { + /* We can do some optimizations this way */ + if (!size_matters) + size = 0; + subblob_t *source_subblob = blob_as_subblob(source); + if (source_subblob->size_matters && + offset + size > source_subblob->size) { + rc = EINVAL; + goto error; + } + + if (source->base.refs == 1) { + source_subblob->offset += offset; + source_subblob->size -= offset; + if (size_matters) { + source_subblob->size_matters = true; + source_subblob->size = size; + } + *out = bithenge_blob_as_node(source); + return EOK; + } + + if (!size_matters && source_subblob->size_matters) { + size_matters = true; + size = source_subblob->size - offset; + } + offset += source_subblob->offset; + source = source_subblob->source; + bithenge_blob_inc_ref(source); + bithenge_blob_dec_ref(subblob_as_blob(source_subblob)); + } + + blob = malloc(sizeof(*blob)); + if (!blob) { + rc = ENOMEM; + goto error; + } + rc = bithenge_init_random_access_blob(subblob_as_blob(blob), + &subblob_ops); + if (rc != EOK) + goto error; + blob->source = source; + blob->offset = offset; + blob->size = size; + blob->size_matters = size_matters; + *out = bithenge_blob_as_node(subblob_as_blob(blob)); + return EOK; + +error: + bithenge_blob_dec_ref(source); + free(blob); + return rc; +} + +/** Create a blob from data offset within another blob. This function takes + * ownership of a reference to @a blob. + * @param[out] out Stores the created blob node. On error, this is unchanged. + * @param[in] source The input blob. + * @param offset The offset within the input blob at which the new blob will start. + * @return EOK on success or an error code from errno.h. */ +int bithenge_new_offset_blob(bithenge_node_t **out, bithenge_blob_t *source, + aoff64_t offset) +{ + return new_subblob(out, source, offset, 0, false); +} + +/** Create a blob from part of another blob. This function takes ownership of a + * reference to @a blob. + * @param[out] out Stores the created blob node. On error, this is unchanged. + * @param[in] source The input blob. + * @param offset The offset within the input blob at which the new blob will start. + * @param size The size of the new blob. + * @return EOK on success or an error code from errno.h. */ +int bithenge_new_subblob(bithenge_node_t **out, bithenge_blob_t *source, + aoff64_t offset, aoff64_t size) +{ + return new_subblob(out, source, offset, size, true); +} + +/** Check whether the contents of two blobs are equal. + * @memberof bithenge_blob_t + * @param a, b Blobs to compare. + * @return Whether the blobs are equal. If an error occurs, returns false. + */ +bool bithenge_blob_equal(bithenge_blob_t *a, bithenge_blob_t *b) +{ + assert(a); + assert(a->base.blob_ops); + assert(b); + assert(b->base.blob_ops); + int rc; + char buffer_a[4096], buffer_b[4096]; + aoff64_t offset = 0, size_a = sizeof(buffer_a), size_b = sizeof(buffer_b); + do { + rc = bithenge_blob_read(a, offset, buffer_a, &size_a); + if (rc != EOK) + return false; + rc = bithenge_blob_read(b, offset, buffer_b, &size_b); + if (rc != EOK) + return false; + if (size_a != size_b || bcmp(buffer_a, buffer_b, size_a)) + return false; + offset += size_a; + } while (size_a == sizeof(buffer_a)); + return true; +} + +/** @} + */ Index: uspace/app/bithenge/blob.h =================================================================== --- uspace/app/bithenge/blob.h (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/app/bithenge/blob.h (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,250 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Raw binary blobs. + */ + +#ifndef BITHENGE_BLOB_H_ +#define BITHENGE_BLOB_H_ + +#include +#include "tree.h" + +/** A blob of raw binary data. + * @implements bithenge_node_t */ +typedef struct { + /** @privatesection */ + struct bithenge_node_t base; +} bithenge_blob_t; + +/** Operations providing random access to binary data. + * @todo Should these be thread-safe? */ +typedef struct bithenge_random_access_blob_ops_t { + /** @copydoc bithenge_blob_t::bithenge_blob_size */ + int (*size)(bithenge_blob_t *self, aoff64_t *size); + /** @copydoc bithenge_blob_t::bithenge_blob_read */ + int (*read)(bithenge_blob_t *self, aoff64_t offset, char *buffer, + aoff64_t *size); + /** @copydoc bithenge_blob_t::bithenge_blob_read_bits */ + int (*read_bits)(bithenge_blob_t *self, aoff64_t offset, char *buffer, + aoff64_t *size, bool little_endian); + /** Destroy the blob. + * @param blob The blob. */ + void (*destroy)(bithenge_blob_t *self); +} bithenge_random_access_blob_ops_t; + +/** A blob built from an object that supports only sequential reading. + * @implements bithenge_blob_t */ +typedef struct { + /** @privatesection */ + /** The base random-access blob. */ + bithenge_blob_t base; + /** Operations providing sequential access. */ + const struct bithenge_sequential_blob_ops_t *ops; + /** Buffer containing all data read. */ + char *buffer; + /** Size of buffer. */ + aoff64_t buffer_size; + /** Amount of data actually in buffer. */ + aoff64_t data_size; +} bithenge_sequential_blob_t; + +/** Operations providing sequential access to binary data. + * @memberof bithenge_sequential_blob_t */ +typedef struct bithenge_sequential_blob_ops_t { + + /** Get the total size of the blob. If the total size cannot be + * determined easily, this field may be null or return an error, + * forcing the entire blob to be read to determine its size. + * + * @memberof bithenge_blob_t + * @param self The blob. + * @param[out] size Total size of the blob. + * @return EOK on success or an error code from errno.h. + */ + int (*size)(bithenge_sequential_blob_t *self, aoff64_t *size); + + /** Read the next part of the blob. If the requested data extends + * beyond the end of the blob, the data up until the end of the blob + * will be read. + * + * @param self The blob. + * @param[out] buffer Buffer to read into. If an error occurs, the contents are + * undefined. + * @param[in,out] size Number of bytes to read; may be 0. If not enough + * data is left in the blob, the actual number of bytes read should be + * stored here. If an error occurs, the contents are undefined. + * @return EOK on success or an error code from errno.h. + */ + int (*read)(bithenge_sequential_blob_t *self, char *buffer, + aoff64_t *size); + + /** Destroy the blob. + * @param self The blob. */ + void (*destroy)(bithenge_sequential_blob_t *self); +} bithenge_sequential_blob_ops_t; + +/** Get the total size of the blob. + * + * @memberof bithenge_blob_t + * @param self The blob. + * @param[out] size Total size of the blob. + * @return EOK on success or an error code from errno.h. + */ +static inline int bithenge_blob_size(bithenge_blob_t *self, aoff64_t *size) +{ + assert(self); + assert(self->base.blob_ops); + return self->base.blob_ops->size(self, size); +} + +/** Read part of the blob. If the requested data extends beyond the end of the + * blob, the data up until the end of the blob will be read. If the offset is + * beyond the end of the blob, even if the size is zero, an error will be + * returned. + * + * @memberof bithenge_blob_t + * @param self The blob. + * @param offset Byte offset within the blob. + * @param[out] buffer Buffer to read into. If an error occurs, the contents are + * undefined. + * @param[in,out] size Number of bytes to read; may be 0. If the requested + * range extends beyond the end of the blob, the actual number of bytes read + * should be stored here. If an error occurs, the contents are undefined. + * @return EOK on success or an error code from errno.h. + */ +static inline int bithenge_blob_read(bithenge_blob_t *self, aoff64_t offset, + char *buffer, aoff64_t *size) +{ + assert(self); + assert(self->base.blob_ops); + if (!self->base.blob_ops->read) + return EINVAL; + return self->base.blob_ops->read(self, offset, buffer, size); +} + +/** Read part of the bit blob. If the requested data extends beyond the end of + * the blob, the data up until the end of the blob will be read. If the offset + * is beyond the end of the blob, even if the size is zero, an error will be + * returned. + * + * @memberof bithenge_blob_t + * @param self The blob. + * @param offset Byte offset within the blob. + * @param[out] buffer Buffer to read into. If an error occurs, the contents are + * undefined. + * @param[in,out] size Number of bytes to read; may be 0. If the requested + * range extends beyond the end of the blob, the actual number of bytes read + * should be stored here. If an error occurs, the contents are undefined. + * @param little_endian If true, bytes will be filled starting at the least + * significant bit; otherwise, they will be filled starting at the most + * significant bit. + * @return EOK on success or an error code from errno.h. + */ +static inline int bithenge_blob_read_bits(bithenge_blob_t *self, + aoff64_t offset, char *buffer, aoff64_t *size, bool little_endian) +{ + assert(self); + assert(self->base.blob_ops); + if (!self->base.blob_ops->read_bits) + return EINVAL; + return self->base.blob_ops->read_bits(self, offset, buffer, size, + little_endian); +} + +/** Check whether the blob is empty. + * + * @memberof bithenge_blob_t + * @param self The blob. + * @param[out] out Holds whether the blob is empty. + * @return EOK on success or an error code from errno.h. */ +static inline int bithenge_blob_empty(bithenge_blob_t *self, bool *out) +{ + assert(self); + assert(self->base.blob_ops); + aoff64_t size; + int rc = bithenge_blob_size(self, &size); + *out = size == 0; + return rc; +} + +/** Cast a blob node to a generic node. + * @memberof bithenge_blob_t + * @param blob The blob to cast. + * @return The blob node as a generic node. */ +static inline bithenge_node_t *bithenge_blob_as_node(bithenge_blob_t *blob) +{ + return &blob->base; +} + +/** Cast a generic node to a blob node. + * @memberof bithenge_blob_t + * @param node The node to cast, which must be a blob node. + * @return The generic node as a blob node. */ +static inline bithenge_blob_t *bithenge_node_as_blob(bithenge_node_t *node) +{ + assert(node->type == BITHENGE_NODE_BLOB); + return (bithenge_blob_t *)node; +} + +/** Increment a blob's reference count. + * @param blob The blob to reference. */ +static inline void bithenge_blob_inc_ref(bithenge_blob_t *blob) +{ + bithenge_node_inc_ref(bithenge_blob_as_node(blob)); +} + +/** Decrement a blob's reference count. + * @param blob The blob to dereference, or NULL. */ +static inline void bithenge_blob_dec_ref(bithenge_blob_t *blob) +{ + if (blob) + bithenge_node_dec_ref(bithenge_blob_as_node(blob)); +} + +int bithenge_init_random_access_blob(bithenge_blob_t *, + const bithenge_random_access_blob_ops_t *); +int bithenge_init_sequential_blob(bithenge_sequential_blob_t *, + const bithenge_sequential_blob_ops_t *); +int bithenge_new_blob_from_data(bithenge_node_t **, const void *, size_t); +int bithenge_new_blob_from_buffer(bithenge_node_t **, const void *, size_t, + bool); +int bithenge_new_offset_blob(bithenge_node_t **, bithenge_blob_t *, aoff64_t); +int bithenge_new_subblob(bithenge_node_t **, bithenge_blob_t *, aoff64_t, + aoff64_t); +bool bithenge_blob_equal(bithenge_blob_t *, bithenge_blob_t *); + +#endif + +/** @} + */ Index: uspace/app/bithenge/compound.c =================================================================== --- uspace/app/bithenge/compound.c (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/app/bithenge/compound.c (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,337 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Compound transforms. + */ + +#include +#include "compound.h" +#include "expression.h" +#include "transform.h" +#include "tree.h" + + + +/***************** compose_transform *****************/ + +typedef struct { + bithenge_transform_t base; + bithenge_transform_t **xforms; + size_t num; +} compose_transform_t; + +static bithenge_transform_t *compose_as_transform(compose_transform_t *xform) +{ + return &xform->base; +} + +static compose_transform_t *transform_as_compose(bithenge_transform_t *xform) +{ + return (compose_transform_t *)xform; +} + +static int compose_apply(bithenge_transform_t *base, bithenge_scope_t *scope, + bithenge_node_t *in, bithenge_node_t **out) +{ + int rc; + compose_transform_t *self = transform_as_compose(base); + bithenge_node_inc_ref(in); + + /* i ranges from (self->num - 1) to 0 inside the loop. */ + for (size_t i = self->num; i--; ) { + bithenge_node_t *tmp; + rc = bithenge_transform_apply(self->xforms[i], scope, in, + &tmp); + bithenge_node_dec_ref(in); + if (rc != EOK) + return rc; + in = tmp; + } + + *out = in; + return rc; +} + +static int compose_prefix_length(bithenge_transform_t *base, + bithenge_scope_t *scope, bithenge_blob_t *blob, aoff64_t *out) +{ + compose_transform_t *self = transform_as_compose(base); + return bithenge_transform_prefix_length(self->xforms[self->num - 1], + scope, blob, out); +} + +static void compose_destroy(bithenge_transform_t *base) +{ + compose_transform_t *self = transform_as_compose(base); + for (size_t i = 0; i < self->num; i++) + bithenge_transform_dec_ref(self->xforms[i]); + free(self->xforms); + free(self); +} + +static const bithenge_transform_ops_t compose_transform_ops = { + .apply = compose_apply, + .prefix_length = compose_prefix_length, + .destroy = compose_destroy, +}; + +/** Create a composition of multiple transforms. When the result is applied to a + * node, each transform is applied in turn, with the last transform applied + * first. @a xforms may contain any number of transforms or no transforms at + * all. This function takes ownership of @a xforms and the references therein. + * @param[out] out Holds the result. + * @param[in] xforms The transforms to apply. + * @param num The number of transforms. + * @return EOK on success or an error code from errno.h. */ +int bithenge_new_composed_transform(bithenge_transform_t **out, + bithenge_transform_t **xforms, size_t num) +{ + if (num == 0) { + /* TODO: optimize */ + } else if (num == 1) { + *out = xforms[0]; + free(xforms); + return EOK; + } + + int rc; + compose_transform_t *self = malloc(sizeof(*self)); + if (!self) { + rc = ENOMEM; + goto error; + } + rc = bithenge_init_transform(compose_as_transform(self), + &compose_transform_ops, 0); + if (rc != EOK) + goto error; + self->xforms = xforms; + self->num = num; + *out = compose_as_transform(self); + return EOK; +error: + for (size_t i = 0; i < num; i++) + bithenge_transform_dec_ref(xforms[i]); + free(xforms); + free(self); + return rc; +} + + + +/***************** if_transform *****************/ + +typedef struct { + bithenge_transform_t base; + bithenge_expression_t *expr; + bithenge_transform_t *true_xform, *false_xform; +} if_transform_t; + +static inline bithenge_transform_t *if_as_transform(if_transform_t *self) +{ + return &self->base; +} + +static inline if_transform_t *transform_as_if(bithenge_transform_t *base) +{ + return (if_transform_t *)base; +} + +static int if_transform_choose(if_transform_t *self, bithenge_scope_t *scope, + bool *out) +{ + bithenge_node_t *cond_node; + int rc = bithenge_expression_evaluate(self->expr, scope, &cond_node); + if (rc != EOK) + return rc; + if (bithenge_node_type(cond_node) != BITHENGE_NODE_BOOLEAN) { + bithenge_node_dec_ref(cond_node); + return EINVAL; + } + *out = bithenge_boolean_node_value(cond_node); + bithenge_node_dec_ref(cond_node); + return EOK; +} + +static int if_transform_apply(bithenge_transform_t *base, + bithenge_scope_t *scope, bithenge_node_t *in, bithenge_node_t **out) +{ + if_transform_t *self = transform_as_if(base); + bool cond; + int rc = if_transform_choose(self, scope, &cond); + if (rc != EOK) + return rc; + return bithenge_transform_apply( + cond ? self->true_xform : self->false_xform, scope, in, out); +} + +static int if_transform_prefix_length(bithenge_transform_t *base, + bithenge_scope_t *scope, bithenge_blob_t *in, aoff64_t *out) +{ + if_transform_t *self = transform_as_if(base); + bool cond; + int rc = if_transform_choose(self, scope, &cond); + if (rc != EOK) + return rc; + return bithenge_transform_prefix_length( + cond ? self->true_xform : self->false_xform, scope, in, out); +} + +static void if_transform_destroy(bithenge_transform_t *base) +{ + if_transform_t *self = transform_as_if(base); + bithenge_expression_dec_ref(self->expr); + bithenge_transform_dec_ref(self->true_xform); + bithenge_transform_dec_ref(self->false_xform); + free(self); +} + +static const bithenge_transform_ops_t if_transform_ops = { + .apply = if_transform_apply, + .prefix_length = if_transform_prefix_length, + .destroy = if_transform_destroy, +}; + +/** Create a transform that applies either of two transforms depending on a + * boolean expression. Takes references to @a expr, @a true_xform, and + * @a false_xform. + * @param[out] out Holds the new transform. + * @param expr The boolean expression to evaluate. + * @param true_xform The transform to apply if the expression is true. + * @param false_xform The transform to apply if the expression is false. + * @return EOK on success or an error code from errno.h. */ +int bithenge_if_transform(bithenge_transform_t **out, + bithenge_expression_t *expr, bithenge_transform_t *true_xform, + bithenge_transform_t *false_xform) +{ + int rc; + if_transform_t *self = malloc(sizeof(*self)); + if (!self) { + rc = ENOMEM; + goto error; + } + + rc = bithenge_init_transform(if_as_transform(self), &if_transform_ops, + 0); + if (rc != EOK) + goto error; + + self->expr = expr; + self->true_xform = true_xform; + self->false_xform = false_xform; + *out = if_as_transform(self); + return EOK; + +error: + free(self); + bithenge_expression_dec_ref(expr); + bithenge_transform_dec_ref(true_xform); + bithenge_transform_dec_ref(false_xform); + return rc; +} + + + +/***************** partial_transform *****************/ + +typedef struct { + bithenge_transform_t base; + bithenge_transform_t *xform; +} partial_transform_t; + +static inline bithenge_transform_t *partial_as_transform( + partial_transform_t *self) +{ + return &self->base; +} + +static inline partial_transform_t *transform_as_partial( + bithenge_transform_t *base) +{ + return (partial_transform_t *)base; +} + +static int partial_transform_apply(bithenge_transform_t *base, + bithenge_scope_t *scope, bithenge_node_t *in, bithenge_node_t **out) +{ + partial_transform_t *self = transform_as_partial(base); + if (bithenge_node_type(in) != BITHENGE_NODE_BLOB) + return EINVAL; + uint64_t size; + return bithenge_transform_prefix_apply(self->xform, scope, + bithenge_node_as_blob(in), out, &size); +} + +static void partial_transform_destroy(bithenge_transform_t *base) +{ + partial_transform_t *self = transform_as_partial(base); + bithenge_transform_dec_ref(self->xform); + free(self); +} + +static const bithenge_transform_ops_t partial_transform_ops = { + .apply = partial_transform_apply, + .destroy = partial_transform_destroy, +}; + +/** Create a transform that doesn't require its subtransform to use the whole + * input. Takes a reference to @a xform. + * @param[out] out Holds the new transform. + * @param xform The subtransform to apply. + * @return EOK on success or an error code from errno.h. */ +int bithenge_partial_transform(bithenge_transform_t **out, + bithenge_transform_t *xform) +{ + int rc; + partial_transform_t *self = malloc(sizeof(*self)); + if (!self) { + rc = ENOMEM; + goto error; + } + + rc = bithenge_init_transform(partial_as_transform(self), + &partial_transform_ops, 0); + if (rc != EOK) + goto error; + + self->xform = xform; + *out = partial_as_transform(self); + return EOK; + +error: + free(self); + bithenge_transform_dec_ref(xform); + return rc; +} + +/** @} + */ Index: uspace/app/bithenge/compound.h =================================================================== --- uspace/app/bithenge/compound.h (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/app/bithenge/compound.h (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,53 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Compound transforms. + */ + +#ifndef BITHENGE_COMPOUND_H_ +#define BITHENGE_COMPOUND_H_ + +#include "expression.h" +#include "transform.h" + +int bithenge_new_composed_transform(bithenge_transform_t **, + bithenge_transform_t **, size_t); +int bithenge_if_transform(bithenge_transform_t **, bithenge_expression_t *, + bithenge_transform_t *, bithenge_transform_t *); +int bithenge_partial_transform(bithenge_transform_t **, + bithenge_transform_t *); + +#endif + +/** @} + */ Index: uspace/app/bithenge/expression.c =================================================================== --- uspace/app/bithenge/expression.c (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/app/bithenge/expression.c (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,964 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Expressions. + */ + +#include +#include +#include +#include "blob.h" +#include "expression.h" +#include "transform.h" +#include "tree.h" + +/** Initialize a new expression. + * @param[out] self Expression to initialize. + * @param[in] ops Operations provided by the expression. + * @return EOK or an error code from errno.h. */ +int bithenge_init_expression(bithenge_expression_t *self, + const bithenge_expression_ops_t *ops) +{ + assert(ops); + assert(ops->evaluate); + assert(ops->destroy); + self->ops = ops; + self->refs = 1; + return EOK; +} + +static void expression_indestructible(bithenge_expression_t *self) +{ + assert(false); +} + + + +/***************** binary_expression *****************/ + +typedef struct { + bithenge_expression_t base; + bithenge_binary_op_t op; + bithenge_expression_t *a, *b; +} binary_expression_t; + +static inline binary_expression_t *expression_as_binary( + bithenge_expression_t *base) +{ + return (binary_expression_t *)base; +} + +static inline bithenge_expression_t *binary_as_expression( + binary_expression_t *self) +{ + return &self->base; +} + +static int binary_expression_evaluate(bithenge_expression_t *base, + bithenge_scope_t *scope, bithenge_node_t **out) +{ + binary_expression_t *self = expression_as_binary(base); + bithenge_node_t *a, *b; + int rc = bithenge_expression_evaluate(self->a, scope, &a); + if (rc != EOK) + return rc; + rc = bithenge_expression_evaluate(self->b, scope, &b); + if (rc != EOK) { + bithenge_node_dec_ref(a); + return rc; + } + + /* Check types and get values. */ + bithenge_int_t a_int = 0, b_int = 0; + switch (self->op) { + case BITHENGE_EXPRESSION_ADD: /* fallthrough */ + case BITHENGE_EXPRESSION_SUBTRACT: /* fallthrough */ + case BITHENGE_EXPRESSION_MULTIPLY: + rc = EINVAL; + if (bithenge_node_type(a) != BITHENGE_NODE_INTEGER) + goto error; + if (bithenge_node_type(b) != BITHENGE_NODE_INTEGER) + goto error; + a_int = bithenge_integer_node_value(a); + b_int = bithenge_integer_node_value(b); + break; + default: + break; + } + + switch (self->op) { + case BITHENGE_EXPRESSION_ADD: + rc = bithenge_new_integer_node(out, a_int + b_int); + break; + case BITHENGE_EXPRESSION_SUBTRACT: + rc = bithenge_new_integer_node(out, a_int - b_int); + break; + case BITHENGE_EXPRESSION_MULTIPLY: + rc = bithenge_new_integer_node(out, a_int * b_int); + break; + case BITHENGE_EXPRESSION_EQUALS: + rc = bithenge_new_boolean_node(out, bithenge_node_equal(a, b)); + break; + case BITHENGE_EXPRESSION_INVALID_BINARY_OP: + assert(false); + break; + } + +error: + bithenge_node_dec_ref(a); + bithenge_node_dec_ref(b); + return rc; +} + +static void binary_expression_destroy(bithenge_expression_t *base) +{ + binary_expression_t *self = expression_as_binary(base); + bithenge_expression_dec_ref(self->a); + bithenge_expression_dec_ref(self->b); + free(self); +} + +static const bithenge_expression_ops_t binary_expression_ops = { + .evaluate = binary_expression_evaluate, + .destroy = binary_expression_destroy, +}; + +/** Create a binary expression. Takes ownership of @a a and @a b. + * @param[out] out Holds the new expression. + * @param op The operator to apply. + * @param a The first operand. + * @param b The second operand. + * @return EOK on success or an error code from errno.h. */ +int bithenge_binary_expression(bithenge_expression_t **out, + bithenge_binary_op_t op, bithenge_expression_t *a, + bithenge_expression_t *b) +{ + int rc; + binary_expression_t *self = malloc(sizeof(*self)); + if (!self) { + rc = ENOMEM; + goto error; + } + + rc = bithenge_init_expression(binary_as_expression(self), + &binary_expression_ops); + if (rc != EOK) + goto error; + + self->op = op; + self->a = a; + self->b = b; + *out = binary_as_expression(self); + return EOK; + +error: + bithenge_expression_dec_ref(a); + bithenge_expression_dec_ref(b); + free(self); + return rc; +} + + + +/***************** in_node_expression *****************/ + +static int in_node_evaluate(bithenge_expression_t *self, + bithenge_scope_t *scope, bithenge_node_t **out) +{ + for (; scope && !bithenge_scope_is_barrier(scope); + scope = bithenge_scope_outer(scope)) { + *out = bithenge_scope_in_node(scope); + if (*out) + return EOK; + } + return EINVAL; +} + +static const bithenge_expression_ops_t in_node_ops = { + .evaluate = in_node_evaluate, + .destroy = expression_indestructible, +}; + +static bithenge_expression_t in_node_expression = { + &in_node_ops, 1 +}; + +/** Create an expression that gets the current input node. + * @param[out] out Holds the new expression. + * @return EOK on success or an error code from errno.h. */ +int bithenge_in_node_expression(bithenge_expression_t **out) +{ + bithenge_expression_inc_ref(&in_node_expression); + *out = &in_node_expression; + return EOK; +} + + + +/***************** current_node_expression *****************/ + +static int current_node_evaluate(bithenge_expression_t *self, + bithenge_scope_t *scope, bithenge_node_t **out) +{ + *out = bithenge_scope_get_current_node(scope); + if (!*out) + return EINVAL; + return EOK; +} + +static const bithenge_expression_ops_t current_node_ops = { + .evaluate = current_node_evaluate, + .destroy = expression_indestructible, +}; + +static bithenge_expression_t current_node_expression = { + ¤t_node_ops, 1 +}; + +/** Create an expression that gets the current node being created. + * @param[out] out Holds the new expression. + * @return EOK on success or an error code from errno.h. */ +int bithenge_current_node_expression(bithenge_expression_t **out) +{ + bithenge_expression_inc_ref(¤t_node_expression); + *out = ¤t_node_expression; + return EOK; +} + + + +/***************** param_expression *****************/ + +typedef struct { + bithenge_expression_t base; + int index; +} param_expression_t; + +static inline param_expression_t *expression_as_param( + bithenge_expression_t *base) +{ + return (param_expression_t *)base; +} + +static inline bithenge_expression_t *param_as_expression( + param_expression_t *self) +{ + return &self->base; +} + +static int param_expression_evaluate(bithenge_expression_t *base, + bithenge_scope_t *scope, bithenge_node_t **out) +{ + param_expression_t *self = expression_as_param(base); + return bithenge_scope_get_param(scope, self->index, out); +} + +static void param_expression_destroy(bithenge_expression_t *base) +{ + param_expression_t *self = expression_as_param(base); + free(self); +} + +static const bithenge_expression_ops_t param_expression_ops = { + .evaluate = param_expression_evaluate, + .destroy = param_expression_destroy, +}; + +/** Create an expression that returns a parameter. + * @param[out] out Holds the created expression. + * @param index The index of the parameter to get. + * @return EOK on success or an error code from errno.h. */ +int bithenge_param_expression(bithenge_expression_t **out, int index) +{ + int rc; + param_expression_t *self = malloc(sizeof(*self)); + if (!self) + return ENOMEM; + + rc = bithenge_init_expression(param_as_expression(self), + ¶m_expression_ops); + if (rc != EOK) { + free(self); + return rc; + } + + self->index = index; + *out = param_as_expression(self); + return EOK; +} + + + +/***************** const_expression *****************/ + +typedef struct { + bithenge_expression_t base; + bithenge_node_t *node; +} const_expression_t; + +static inline const_expression_t *expression_as_const( + bithenge_expression_t *base) +{ + return (const_expression_t *)base; +} + +static inline bithenge_expression_t *const_as_expression( + const_expression_t *self) +{ + return &self->base; +} + +static int const_expression_evaluate(bithenge_expression_t *base, + bithenge_scope_t *scope, bithenge_node_t **out) +{ + const_expression_t *self = expression_as_const(base); + bithenge_node_inc_ref(self->node); + *out = self->node; + return EOK; +} + +static void const_expression_destroy(bithenge_expression_t *base) +{ + const_expression_t *self = expression_as_const(base); + bithenge_node_dec_ref(self->node); + free(self); +} + +static const bithenge_expression_ops_t const_expression_ops = { + .evaluate = const_expression_evaluate, + .destroy = const_expression_destroy, +}; + +/** Create an expression that returns a constant. Takes a reference to @a node. + * @param[out] out Holds the created expression. + * @param node The constant. + * @return EOK on success or an error code from errno.h. */ +int bithenge_const_expression(bithenge_expression_t **out, + bithenge_node_t *node) +{ + int rc; + const_expression_t *self = malloc(sizeof(*self)); + if (!self) { + rc = ENOMEM; + goto error; + } + + rc = bithenge_init_expression(const_as_expression(self), + &const_expression_ops); + if (rc != EOK) + goto error; + + self->node = node; + *out = const_as_expression(self); + return EOK; + +error: + free(self); + bithenge_node_dec_ref(node); + return rc; +} + + + +/***************** member_expression *****************/ + +typedef struct { + bithenge_expression_t base; + bithenge_expression_t *expr; + bithenge_node_t *key; +} member_expression_t; + +static member_expression_t *expression_as_member(bithenge_expression_t *base) +{ + return (member_expression_t *)base; +} + +static bithenge_expression_t *member_as_expression(member_expression_t *expr) +{ + return &expr->base; +} + +static int member_expression_evaluate(bithenge_expression_t *base, + bithenge_scope_t *scope, bithenge_node_t **out) +{ + member_expression_t *self = expression_as_member(base); + bithenge_node_t *node; + int rc = bithenge_expression_evaluate(self->expr, scope, &node); + if (rc != EOK) + return rc; + bithenge_node_inc_ref(self->key); + rc = bithenge_node_get(node, self->key, out); + bithenge_node_dec_ref(node); + return rc; +} + +static void member_expression_destroy(bithenge_expression_t *base) +{ + member_expression_t *self = expression_as_member(base); + bithenge_expression_dec_ref(self->expr); + bithenge_node_dec_ref(self->key); + free(self); +} + +static const bithenge_expression_ops_t member_expression_ops = { + .evaluate = member_expression_evaluate, + .destroy = member_expression_destroy, +}; + +/** Create an expression that gets a member from a node. Takes references to + * @a expr and @a key. + * @param[out] out Holds the new expression. + * @param expr Calculates the node to get the member of. + * @param key The member to get. + * @return EOK on success or an error code from errno.h. */ +int bithenge_member_expression(bithenge_expression_t **out, + bithenge_expression_t *expr, bithenge_node_t *key) +{ + int rc; + member_expression_t *self = malloc(sizeof(*self)); + if (!self) { + rc = ENOMEM; + goto error; + } + + rc = bithenge_init_expression(member_as_expression(self), + &member_expression_ops); + if (rc != EOK) + goto error; + + self->expr = expr; + self->key = key; + *out = member_as_expression(self); + return EOK; + +error: + bithenge_expression_dec_ref(expr); + bithenge_node_dec_ref(key); + free(self); + return rc; +} + + + +/***************** scope_member_expression *****************/ + +typedef struct { + bithenge_expression_t base; + bithenge_node_t *key; +} scope_member_expression_t; + +static scope_member_expression_t *expression_as_scope_member( + bithenge_expression_t *base) +{ + return (scope_member_expression_t *)base; +} + +static bithenge_expression_t *scope_member_as_expression( + scope_member_expression_t *expr) +{ + return &expr->base; +} + +static int scope_member_expression_evaluate(bithenge_expression_t *base, + bithenge_scope_t *scope, bithenge_node_t **out) +{ + scope_member_expression_t *self = expression_as_scope_member(base); + for (; scope && !bithenge_scope_is_barrier(scope); + scope = bithenge_scope_outer(scope)) { + bithenge_node_inc_ref(self->key); + bithenge_node_t *cur = bithenge_scope_get_current_node(scope); + int rc = bithenge_node_get(cur, self->key, out); + bithenge_node_dec_ref(cur); + if (rc != ENOENT) /* EOK or error */ + return rc; + } + return ENOENT; +} + +static void scope_member_expression_destroy(bithenge_expression_t *base) +{ + scope_member_expression_t *self = expression_as_scope_member(base); + bithenge_node_dec_ref(self->key); + free(self); +} + +static const bithenge_expression_ops_t scope_member_expression_ops = { + .evaluate = scope_member_expression_evaluate, + .destroy = scope_member_expression_destroy, +}; + +int bithenge_scope_member_expression(bithenge_expression_t **out, + bithenge_node_t *key) +{ + int rc; + scope_member_expression_t *self = malloc(sizeof(*self)); + if (!self) { + rc = ENOMEM; + goto error; + } + + rc = bithenge_init_expression(scope_member_as_expression(self), + &scope_member_expression_ops); + if (rc != EOK) + goto error; + + self->key = key; + *out = scope_member_as_expression(self); + return EOK; + +error: + bithenge_node_dec_ref(key); + free(self); + return rc; +} + + + +/***************** subblob_expression *****************/ + +typedef struct { + bithenge_expression_t base; + bithenge_expression_t *blob, *start, *limit; + bool absolute_limit; +} subblob_expression_t; + +static subblob_expression_t *expression_as_subblob(bithenge_expression_t *base) +{ + return (subblob_expression_t *)base; +} + +static bithenge_expression_t *subblob_as_expression(subblob_expression_t *expr) +{ + return &expr->base; +} + +static int subblob_expression_evaluate(bithenge_expression_t *base, + bithenge_scope_t *scope, bithenge_node_t **out) +{ + subblob_expression_t *self = expression_as_subblob(base); + bithenge_node_t *start_node; + int rc = bithenge_expression_evaluate(self->start, scope, &start_node); + if (rc != EOK) + return rc; + if (bithenge_node_type(start_node) != BITHENGE_NODE_INTEGER) { + bithenge_node_dec_ref(start_node); + return EINVAL; + } + bithenge_int_t start = bithenge_integer_node_value(start_node); + bithenge_node_dec_ref(start_node); + + bithenge_int_t limit = -1; + if (self->limit) { + bithenge_node_t *limit_node; + rc = bithenge_expression_evaluate(self->limit, scope, + &limit_node); + if (rc != EOK) + return rc; + if (bithenge_node_type(limit_node) != BITHENGE_NODE_INTEGER) { + bithenge_node_dec_ref(limit_node); + return EINVAL; + } + limit = bithenge_integer_node_value(limit_node); + bithenge_node_dec_ref(limit_node); + if (self->absolute_limit) + limit -= start; + } + + if (start < 0 || (self->limit && limit < 0)) + return EINVAL; + + bithenge_node_t *blob; + rc = bithenge_expression_evaluate(self->blob, scope, &blob); + if (rc != EOK) + return rc; + if (bithenge_node_type(blob) != BITHENGE_NODE_BLOB) { + bithenge_node_dec_ref(blob); + return EINVAL; + } + + if (self->limit) + return bithenge_new_subblob(out, bithenge_node_as_blob(blob), + start, limit); + else + return bithenge_new_offset_blob(out, + bithenge_node_as_blob(blob), start); +} + +static void subblob_expression_destroy(bithenge_expression_t *base) +{ + subblob_expression_t *self = expression_as_subblob(base); + bithenge_expression_dec_ref(self->start); + bithenge_expression_dec_ref(self->limit); + free(self); +} + +static const bithenge_expression_ops_t subblob_expression_ops = { + .evaluate = subblob_expression_evaluate, + .destroy = subblob_expression_destroy, +}; + +/** Create an expression that gets a subblob. Takes references to @a blob, + * @a start, and @a limit. + * @param[out] out Holds the new expression. + * @param blob Calculates the blob. + * @param start Calculates the start offset within the blob. + * @param limit Calculates the limit. Can be NULL, in which case an offset blob + * is returned. + * @param absolute_limit If true, the limit is an absolute offset; otherwise, + * it is relative to the start. + * @return EOK on success or an error code from errno.h. */ +int bithenge_subblob_expression(bithenge_expression_t **out, + bithenge_expression_t *blob, bithenge_expression_t *start, + bithenge_expression_t *limit, bool absolute_limit) +{ + int rc; + subblob_expression_t *self = malloc(sizeof(*self)); + if (!self) { + rc = ENOMEM; + goto error; + } + + rc = bithenge_init_expression(subblob_as_expression(self), + &subblob_expression_ops); + if (rc != EOK) + goto error; + + self->blob = blob; + self->start = start; + self->limit = limit; + self->absolute_limit = absolute_limit; + *out = subblob_as_expression(self); + return EOK; + +error: + bithenge_expression_dec_ref(blob); + bithenge_expression_dec_ref(start); + bithenge_expression_dec_ref(limit); + free(self); + return rc; +} + +/***************** param_wrapper *****************/ + +typedef struct { + bithenge_transform_t base; + bithenge_transform_t *transform; + bithenge_expression_t **params; +} param_wrapper_t; + +static inline bithenge_transform_t *param_wrapper_as_transform( + param_wrapper_t *self) +{ + return &self->base; +} + +static inline param_wrapper_t *transform_as_param_wrapper( + bithenge_transform_t *base) +{ + return (param_wrapper_t *)base; +} + +static int param_wrapper_fill_scope(param_wrapper_t *self, bithenge_scope_t + *inner, bithenge_scope_t *outer) +{ + int rc; + int num_params = bithenge_transform_num_params(self->transform); + rc = bithenge_scope_alloc_params(inner, num_params); + if (rc != EOK) + return rc; + for (int i = 0; i < num_params; i++) { + bithenge_node_t *node; + rc = bithenge_expression_evaluate(self->params[i], outer, + &node); + if (rc != EOK) + return rc; + rc = bithenge_scope_set_param(inner, i, node); + if (rc != EOK) + return rc; + } + return EOK; +} + +static int param_wrapper_apply(bithenge_transform_t *base, + bithenge_scope_t *outer, bithenge_node_t *in, bithenge_node_t **out) +{ + param_wrapper_t *self = transform_as_param_wrapper(base); + bithenge_scope_t *inner; + int rc = bithenge_scope_new(&inner, outer); + if (rc != EOK) + return rc; + rc = param_wrapper_fill_scope(self, inner, outer); + if (rc != EOK) + goto error; + + rc = bithenge_transform_apply(self->transform, inner, in, out); + in = NULL; + +error: + bithenge_scope_dec_ref(inner); + return rc; +} + +static int param_wrapper_prefix_length(bithenge_transform_t *base, + bithenge_scope_t *outer, bithenge_blob_t *in, aoff64_t *out) +{ + param_wrapper_t *self = transform_as_param_wrapper(base); + bithenge_scope_t *inner; + int rc = bithenge_scope_new(&inner, outer); + if (rc != EOK) + return rc; + rc = param_wrapper_fill_scope(self, inner, outer); + if (rc != EOK) + goto error; + + rc = bithenge_transform_prefix_length(self->transform, inner, in, out); + in = NULL; + +error: + bithenge_scope_dec_ref(inner); + return rc; +} + +static int param_wrapper_prefix_apply(bithenge_transform_t *base, + bithenge_scope_t *outer, bithenge_blob_t *in, bithenge_node_t **out_node, + aoff64_t *out_length) +{ + param_wrapper_t *self = transform_as_param_wrapper(base); + bithenge_scope_t *inner; + int rc = bithenge_scope_new(&inner, outer); + if (rc != EOK) + return rc; + rc = param_wrapper_fill_scope(self, inner, outer); + if (rc != EOK) + goto error; + + rc = bithenge_transform_prefix_apply(self->transform, inner, in, + out_node, out_length); + +error: + bithenge_scope_dec_ref(inner); + return rc; +} + +static void param_wrapper_destroy(bithenge_transform_t *base) +{ + param_wrapper_t *self = transform_as_param_wrapper(base); + int num_params = bithenge_transform_num_params(self->transform); + bithenge_transform_dec_ref(self->transform); + for (int i = 0; i < num_params; i++) + bithenge_expression_dec_ref(self->params[i]); + free(self->params); + free(self); +} + +static const bithenge_transform_ops_t param_wrapper_ops = { + .apply = param_wrapper_apply, + .prefix_length = param_wrapper_prefix_length, + .prefix_apply = param_wrapper_prefix_apply, + .destroy = param_wrapper_destroy, +}; + +/** Create a transform that calculates parameters for another transform. Takes + * ownership of @a transform, @a params, and each element of @a params. The + * number of parameters must be correct. + * @param[out] out Holds the new transform. + * @param transform The transform for which parameters are calculated. + * @param params The expressions used to calculate the parameters. + * @return EOK on success or an error code from errno.h. */ +int bithenge_param_wrapper(bithenge_transform_t **out, + bithenge_transform_t *transform, bithenge_expression_t **params) +{ + int rc; + int num_params = bithenge_transform_num_params(transform); + param_wrapper_t *self = malloc(sizeof(*self)); + if (!self) { + rc = ENOMEM; + goto error; + } + + rc = bithenge_init_transform(param_wrapper_as_transform(self), + ¶m_wrapper_ops, 0); + if (rc != EOK) + goto error; + + self->transform = transform; + self->params = params; + *out = param_wrapper_as_transform(self); + return EOK; + +error: + free(self); + for (int i = 0; i < num_params; i++) + bithenge_expression_dec_ref(params[i]); + free(params); + bithenge_transform_dec_ref(transform); + return rc; +} + + + +/***************** expression_transform *****************/ + +/* Also used by inputless_transform. */ +typedef struct { + bithenge_transform_t base; + bithenge_expression_t *expr; +} expression_transform_t; + +static inline bithenge_transform_t *expression_as_transform( + expression_transform_t *self) +{ + return &self->base; +} + +static inline expression_transform_t *transform_as_expression( + bithenge_transform_t *base) +{ + return (expression_transform_t *)base; +} + +static int expression_transform_apply(bithenge_transform_t *base, + bithenge_scope_t *scope, bithenge_node_t *in, bithenge_node_t **out) +{ + expression_transform_t *self = transform_as_expression(base); + bithenge_scope_t *inner; + int rc = bithenge_scope_new(&inner, scope); + if (rc != EOK) + return rc; + bithenge_scope_set_in_node(inner, in); + rc = bithenge_expression_evaluate(self->expr, inner, out); + bithenge_scope_dec_ref(inner); + return rc; +} + +/* Also used by inputless_transform. */ +static void expression_transform_destroy(bithenge_transform_t *base) +{ + expression_transform_t *self = transform_as_expression(base); + bithenge_expression_dec_ref(self->expr); + free(self); +} + +static const bithenge_transform_ops_t expression_transform_ops = { + .apply = expression_transform_apply, + .destroy = expression_transform_destroy, +}; + +/** Create a transform that evaluates an expression on the input node. Takes a + * reference to the expression. + * @param[out] out Holds the new transform. + * @param expr The expression to evaluate. + * @return EOK on success or an error code from errno.h. */ +int bithenge_expression_transform(bithenge_transform_t ** out, + bithenge_expression_t *expr) +{ + int rc; + expression_transform_t *self = malloc(sizeof(*self)); + if (!self) { + rc = ENOMEM; + goto error; + } + + rc = bithenge_init_transform(expression_as_transform(self), + &expression_transform_ops, 0); + if (rc != EOK) + goto error; + + self->expr = expr; + *out = expression_as_transform(self); + return EOK; + +error: + free(self); + bithenge_expression_dec_ref(expr); + return rc; +} + + + +/***************** inputless_transform *****************/ + +static int inputless_transform_prefix_length(bithenge_transform_t *base, + bithenge_scope_t *scope, bithenge_blob_t *in, aoff64_t *out) +{ + *out = 0; + return EOK; +} + +static int inputless_transform_prefix_apply(bithenge_transform_t *base, + bithenge_scope_t *scope, bithenge_blob_t *in, bithenge_node_t **out_node, + aoff64_t *out_size) +{ + expression_transform_t *self = transform_as_expression(base); + *out_size = 0; + return bithenge_expression_evaluate(self->expr, scope, out_node); +} + +static const bithenge_transform_ops_t inputless_transform_ops = { + .prefix_length = inputless_transform_prefix_length, + .prefix_apply = inputless_transform_prefix_apply, + .destroy = expression_transform_destroy, +}; + +/** Create a transform that takes an empty blob and produces the result of an + * expression. Takes a reference to the expression. + * @param[out] out Holds the new transform. + * @param expr The expression to evaluate. + * @return EOK on success or an error code from errno.h. */ +int bithenge_inputless_transform(bithenge_transform_t ** out, + bithenge_expression_t *expr) +{ + int rc; + expression_transform_t *self = malloc(sizeof(*self)); + if (!self) { + rc = ENOMEM; + goto error; + } + + rc = bithenge_init_transform(expression_as_transform(self), + &inputless_transform_ops, 0); + if (rc != EOK) + goto error; + + self->expr = expr; + *out = expression_as_transform(self); + return EOK; + +error: + free(self); + bithenge_expression_dec_ref(expr); + return rc; +} + +/** @} + */ Index: uspace/app/bithenge/expression.h =================================================================== --- uspace/app/bithenge/expression.h (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/app/bithenge/expression.h (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,126 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Expressions. + */ + +#ifndef BITHENGE_EXPRESSION_H_ +#define BITHENGE_EXPRESSION_H_ + +#include "transform.h" +#include "tree.h" + +/** An expression that calculates a value given a scope. */ +typedef struct { + /** @privatesection */ + const struct bithenge_expression_ops *ops; + unsigned int refs; +} bithenge_expression_t; + +/** Operations provided by an expression. */ +typedef struct bithenge_expression_ops { + /** @copydoc bithenge_expression_t::bithenge_expression_evaluate */ + int (*evaluate)(bithenge_expression_t *self, bithenge_scope_t *scope, + bithenge_node_t **out); + /** Destroy the expression. + * @param self The expression. */ + void (*destroy)(bithenge_expression_t *self); +} bithenge_expression_ops_t; + +/** Increment an expression's reference count. + * @param self The expression to reference. */ +static inline void bithenge_expression_inc_ref(bithenge_expression_t *self) +{ + assert(self); + self->refs++; +} + +/** Decrement an expression's reference count and free it if appropriate. + * @param self The expression to dereference, or NULL. */ +static inline void bithenge_expression_dec_ref(bithenge_expression_t *self) +{ + if (!self) + return; + assert(self->ops); + if (--self->refs == 0) + self->ops->destroy(self); +} + +/** Evaluate an expression. Takes ownership of nothing. + * @memberof bithenge_expression_t + * @param self The expression. + * @param scope The scope. + * @param[out] out Where the output tree will be stored. + * @return EOK on success or an error code from errno.h. */ +static inline int bithenge_expression_evaluate(bithenge_expression_t *self, + bithenge_scope_t *scope, bithenge_node_t **out) +{ + assert(self); + assert(self->ops); + return self->ops->evaluate(self, scope, out); +} + +typedef enum { + BITHENGE_EXPRESSION_INVALID_BINARY_OP, + BITHENGE_EXPRESSION_ADD, + BITHENGE_EXPRESSION_SUBTRACT, + BITHENGE_EXPRESSION_MULTIPLY, + BITHENGE_EXPRESSION_EQUALS, +} bithenge_binary_op_t; + +int bithenge_init_expression(bithenge_expression_t *, + const bithenge_expression_ops_t *); +int bithenge_binary_expression(bithenge_expression_t **, bithenge_binary_op_t, + bithenge_expression_t *, bithenge_expression_t *); +int bithenge_in_node_expression(bithenge_expression_t **); +int bithenge_current_node_expression(bithenge_expression_t **); +int bithenge_param_expression(bithenge_expression_t **, int); +int bithenge_const_expression(bithenge_expression_t **, bithenge_node_t *); +int bithenge_member_expression(bithenge_expression_t **, + bithenge_expression_t *, bithenge_node_t *); +int bithenge_scope_member_expression(bithenge_expression_t **, + bithenge_node_t *); +int bithenge_subblob_expression(bithenge_expression_t **, + bithenge_expression_t *, bithenge_expression_t *, bithenge_expression_t *, + bool); +int bithenge_param_wrapper(bithenge_transform_t **, bithenge_transform_t *, + bithenge_expression_t **); +int bithenge_expression_transform(bithenge_transform_t **, + bithenge_expression_t *); +int bithenge_inputless_transform(bithenge_transform_t **, + bithenge_expression_t *); + +#endif + +/** @} + */ Index: uspace/app/bithenge/file.c =================================================================== --- uspace/app/bithenge/file.c (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/app/bithenge/file.c (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,188 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Access files as blobs. + * @todo Provide more information about the file. + */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include "blob.h" +#include "file.h" +#include "os.h" + +typedef struct { + bithenge_blob_t base; + int fd; + aoff64_t size; // needed by file_read() + bool needs_close; +} file_blob_t; + +static inline file_blob_t *blob_as_file(bithenge_blob_t *base) +{ + return (file_blob_t *)base; +} + +static inline bithenge_blob_t *file_as_blob(file_blob_t *blob) +{ + return &blob->base; +} + +static int file_size(bithenge_blob_t *base, aoff64_t *size) +{ + file_blob_t *blob = blob_as_file(base); + *size = blob->size; + return EOK; +} + +static int file_read(bithenge_blob_t *base, aoff64_t offset, char *buffer, + aoff64_t *size) +{ + file_blob_t *blob = blob_as_file(base); + if (offset > blob->size) + return ELIMIT; + if (lseek(blob->fd, offset, SEEK_SET) < 0) + return errno; + + ssize_t amount_read; + aoff64_t remaining_size = *size; + *size = 0; + do { + amount_read = read(blob->fd, buffer, remaining_size); + if (amount_read < 0) + return errno; + buffer += amount_read; + *size += amount_read; + remaining_size -= amount_read; + } while (remaining_size && amount_read); + return EOK; +} + +static void file_destroy(bithenge_blob_t *base) +{ + file_blob_t *blob = blob_as_file(base); + close(blob->fd); + free(blob); +} + +static const bithenge_random_access_blob_ops_t file_ops = { + .size = file_size, + .read = file_read, + .destroy = file_destroy, +}; + +static int new_file_blob(bithenge_node_t **out, int fd, bool needs_close) +{ + assert(out); + + struct stat stat; + int rc = fstat(fd, &stat); + if (rc != EOK) { + if (needs_close) + close(fd); + return rc; + } + + // Create blob + file_blob_t *blob = malloc(sizeof(*blob)); + if (!blob) { + if (needs_close) + close(fd); + return ENOMEM; + } + rc = bithenge_init_random_access_blob(file_as_blob(blob), &file_ops); + if (rc != EOK) { + free(blob); + if (needs_close) + close(fd); + return rc; + } + blob->fd = fd; +#ifdef __HELENOS__ + blob->size = stat.size; +#else + blob->size = stat.st_size; +#endif + blob->needs_close = needs_close; + *out = bithenge_blob_as_node(file_as_blob(blob)); + + return EOK; +} + +/** Create a blob for a file. The blob must be freed with @a + * bithenge_node_t::bithenge_node_destroy after it is used. + * @param[out] out Stores the created blob. + * @param filename The name of the file. + * @return EOK on success or an error code from errno.h. */ +int bithenge_new_file_blob(bithenge_node_t **out, const char *filename) +{ + assert(filename); + + int fd = open(filename, O_RDONLY); + if (fd < 0) + return fd; + + return new_file_blob(out, fd, true); +} + +/** Create a blob for a file descriptor. The blob must be freed with @a + * bithenge_node_t::bithenge_node_destroy after it is used. + * @param[out] out Stores the created blob. + * @param fd The file descriptor. + * @return EOK on success or an error code from errno.h. */ +int bithenge_new_file_blob_from_fd(bithenge_node_t **out, int fd) +{ + return new_file_blob(out, fd, false); +} + +/** Create a blob for a file pointer. The blob must be freed with @a + * bithenge_node_t::bithenge_node_destroy after it is used. + * @param[out] out Stores the created blob. + * @param file The file pointer. + * @return EOK on success or an error code from errno.h. */ +int bithenge_new_file_blob_from_file(bithenge_node_t **out, FILE *file) +{ + int fd = fileno(file); + if (fd < 0) + return errno; + return new_file_blob(out, fd, false); +} + +/** @} + */ Index: uspace/app/bithenge/file.h =================================================================== --- uspace/app/bithenge/file.h (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/app/bithenge/file.h (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,50 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Access files as blobs. + */ + +#ifndef BITHENGE_FILE_H_ +#define BITHENGE_FILE_H_ + +#include +#include "blob.h" + +int bithenge_new_file_blob(bithenge_node_t **, const char *); +int bithenge_new_file_blob_from_fd(bithenge_node_t **, int); +int bithenge_new_file_blob_from_file(bithenge_node_t **, FILE *); + +#endif + +/** @} + */ Index: uspace/app/bithenge/helenos/block.c =================================================================== --- uspace/app/bithenge/helenos/block.c (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/app/bithenge/helenos/block.c (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,145 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Access block devices as blobs. + * @todo Provide more information about the block device (block size). + */ + +#include +#include +#include +#include +#include +#include +#include "../blob.h" +#include "block.h" + +typedef struct { + bithenge_blob_t base; + service_id_t service_id; + aoff64_t size; +} block_blob_t; + +static inline block_blob_t *blob_as_block(bithenge_blob_t *base) +{ + return (block_blob_t *)base; +} + +static inline bithenge_blob_t *block_as_blob(block_blob_t *blob) +{ + return &blob->base; +} + +static int block_size(bithenge_blob_t *base, aoff64_t *size) +{ + block_blob_t *self = blob_as_block(base); + *size = self->size; + return EOK; +} + +static int block_read(bithenge_blob_t *base, aoff64_t offset, char *buffer, + aoff64_t *size) +{ + block_blob_t *self = blob_as_block(base); + if (offset > self->size) + return ELIMIT; + *size = min(*size, self->size - offset); + return block_read_bytes_direct(self->service_id, offset, *size, buffer); +} + +static void block_destroy(bithenge_blob_t *base) +{ + block_blob_t *self = blob_as_block(base); + block_fini(self->service_id); + free(self); +} + +static const bithenge_random_access_blob_ops_t block_ops = { + .size = block_size, + .read = block_read, + .destroy = block_destroy, +}; + +/** Create a blob for a block device. The blob must be freed with + * @a bithenge_node_t::bithenge_node_destroy after it is used. + * @param[out] out Stores the created blob. + * @param service_id The service ID of the block device. + * @return EOK on success or an error code from errno.h. */ +int bithenge_new_block_blob(bithenge_node_t **out, service_id_t service_id) +{ + assert(out); + + // Initialize libblock + int rc; + rc = block_init(EXCHANGE_SERIALIZE, service_id, 2048); + if (rc != EOK) + return rc; + + // Calculate total device size + size_t bsize; + aoff64_t nblocks; + aoff64_t size; + rc = block_get_bsize(service_id, &bsize); + if (rc != EOK) { + block_fini(service_id); + return rc; + } + rc = block_get_nblocks(service_id, &nblocks); + if (rc != EOK) { + block_fini(service_id); + return rc; + } + size = bsize * nblocks; + + // Create blob + block_blob_t *blob = malloc(sizeof(*blob)); + if (!blob) { + block_fini(service_id); + return ENOMEM; + } + rc = bithenge_init_random_access_blob(block_as_blob(blob), + &block_ops); + if (rc != EOK) { + free(blob); + block_fini(service_id); + return rc; + } + blob->service_id = service_id; + blob->size = size; + *out = bithenge_blob_as_node(block_as_blob(blob)); + + return EOK; +} + +/** @} + */ Index: uspace/app/bithenge/helenos/block.h =================================================================== --- uspace/app/bithenge/helenos/block.h (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/app/bithenge/helenos/block.h (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,48 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Access block devices as blobs. + */ + +#ifndef BITHENGE_BLOCK_H_ +#define BITHENGE_BLOCK_H_ + +#include +#include "../blob.h" + +int bithenge_new_block_blob(bithenge_node_t **, service_id_t); + +#endif + +/** @} + */ Index: uspace/app/bithenge/helenos/os.h =================================================================== --- uspace/app/bithenge/helenos/os.h (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/app/bithenge/helenos/os.h (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,93 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef BITHENGE_OS_H_ +#define BITHENGE_OS_H_ + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +typedef int64_t bithenge_int_t; +#define BITHENGE_PRId PRId64 + +typedef struct { + const char *string; + size_t offset; + wchar_t ch; +} string_iterator_t; + +static inline string_iterator_t string_iterator(const char *string) +{ + string_iterator_t i; + i.string = string; + i.offset = 0; + i.ch = str_decode(i.string, &i.offset, STR_NO_LIMIT); + return i; +} + +static inline bool string_iterator_done(const string_iterator_t *i) +{ + return i->ch == L'\0'; +} + +static inline int string_iterator_next(string_iterator_t *i, wchar_t *out) +{ + *out = i->ch; + if (*out == U_SPECIAL) + return EINVAL; + i->ch = str_decode(i->string, &i->offset, STR_NO_LIMIT); + return EOK; +} + +static inline void *memchr(const void *s, int c, size_t n) +{ + for (size_t i = 0; i < n; i++) + if (((char *)s)[i] == c) + return (void *)(s + i); + return NULL; +} + +static inline int bithenge_parse_int(const char *start, bithenge_int_t *result) +{ + const char *real_start = *start == '-' ? start + 1 : start; + uint64_t val; + int rc = str_uint64_t(real_start, NULL, 10, false, &val); + *result = val; + if (*start == '-') + *result = -*result; + return rc; +} + +#endif Index: uspace/app/bithenge/linux/os.h =================================================================== --- uspace/app/bithenge/linux/os.h (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/app/bithenge/linux/os.h (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,141 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef BITHENGE_OS_H_ +#define BITHENGE_OS_H_ + +#include +#include +#include +#include +#include +#include +#include +#include + +#define max(aleph, bet) ((aleph) > (bet) ? (aleph) : (bet)) +#define min(aleph, bet) ((aleph) < (bet) ? (aleph) : (bet)) + +#define EOK 0 +#define ELIMIT EINVAL + +typedef intmax_t bithenge_int_t; +#define BITHENGE_PRId PRIdMAX +typedef uint64_t aoff64_t; +typedef const char *string_iterator_t; + +static inline string_iterator_t string_iterator(const char *string) +{ + return string; +} + +static inline int string_iterator_next(string_iterator_t *i, wchar_t *out) +{ + wint_t rc = btowc(*(*i)++); // TODO + *out = (wchar_t) rc; + return rc == WEOF ? EILSEQ : EOK; +} + +static inline bool string_iterator_done(const string_iterator_t *i) +{ + return !**i; +} + +static inline size_t str_length(const char *string) +{ + return strlen(string); +} + +static inline const char *str_chr(const char *string, wchar_t ch) +{ + return strchr(string, wctob(ch)); // TODO +} + +static inline int str_cmp(const char *s1, const char *s2) +{ + return strcmp(s1, s2); +} + +static inline int str_lcmp(const char *s1, const char *s2, size_t max_len) +{ + return strncmp(s1, s2, max_len); +} + +static inline char *str_dup(const char *s) +{ + return strdup(s); +} + +static inline char *str_ndup(const char *s, size_t max_len) +{ + return strndup(s, max_len); +} + +static inline const char *str_error(int e) +{ + return strerror(e); +} + +static inline uint16_t uint16_t_le2host(uint16_t val) +{ + return le16toh(val); +} + +static inline uint16_t uint16_t_be2host(uint16_t val) +{ + return be16toh(val); +} + +static inline uint32_t uint32_t_le2host(uint32_t val) +{ + return le32toh(val); +} + +static inline uint32_t uint32_t_be2host(uint32_t val) +{ + return be32toh(val); +} + +static inline uint64_t uint64_t_le2host(uint64_t val) +{ + return le64toh(val); +} + +static inline uint64_t uint64_t_be2host(uint64_t val) +{ + return be64toh(val); +} + +static inline int bithenge_parse_int(const char *start, bithenge_int_t *result) +{ + errno = 0; + *result = strtoll(start, NULL, 10); + return errno; +} + +#endif Index: uspace/app/bithenge/print.c =================================================================== --- uspace/app/bithenge/print.c (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/app/bithenge/print.c (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,205 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Write a tree as JSON or other text formats. + * @todo Allow more control over the printing style, and handle printing in + * limited space. + */ + +#include +#include +#include "blob.h" +#include "print.h" +#include "tree.h" + +typedef struct { + bithenge_print_type_t type; + bool first; + int depth; +} state_t; + +static int print_node(state_t *, bithenge_node_t *); + +static void newline(state_t *state) +{ + printf("\n"); + for (int i = 0; i < state->depth; i++) { + printf(" "); + } +} + +static void increase_depth(state_t *state) +{ + state->depth++; +} + +static void decrease_depth(state_t *state) +{ + state->depth--; +} + +static int print_internal_func(bithenge_node_t *key, bithenge_node_t *value, void *data) +{ + state_t *state = (state_t *)data; + int rc = EOK; + if (!state->first) + printf(","); + newline(state); + state->first = false; + bool add_quotes = state->type == BITHENGE_PRINT_JSON + && bithenge_node_type(key) != BITHENGE_NODE_STRING; + if (add_quotes) + printf("\""); + rc = print_node(state, key); + if (rc != EOK) + goto end; + if (add_quotes) + printf("\""); + printf(": "); + rc = print_node(state, value); + if (rc != EOK) + goto end; +end: + bithenge_node_dec_ref(key); + bithenge_node_dec_ref(value); + return rc; +} + +static int print_internal(state_t *state, bithenge_node_t *node) +{ + int rc; + printf("{"); + increase_depth(state); + state->first = true; + rc = bithenge_node_for_each(node, print_internal_func, state); + if (rc != EOK) + return rc; + decrease_depth(state); + if (!state->first) + newline(state); + state->first = false; + printf("}"); + return EOK; +} + +static int print_boolean(state_t *state, bithenge_node_t *node) +{ + bool value = bithenge_boolean_node_value(node); + switch (state->type) { + case BITHENGE_PRINT_PYTHON: + printf(value ? "True" : "False"); + break; + case BITHENGE_PRINT_JSON: + printf(value ? "true" : "false"); + break; + } + return EOK; +} + +static int print_integer(state_t *state, bithenge_node_t *node) +{ + bithenge_int_t value = bithenge_integer_node_value(node); + printf("%" BITHENGE_PRId, value); + return EOK; +} + +static int print_string(state_t *state, bithenge_node_t *node) +{ + const char *value = bithenge_string_node_value(node); + printf("\""); + for (string_iterator_t i = string_iterator(value); !string_iterator_done(&i); ) { + wchar_t ch; + int rc = string_iterator_next(&i, &ch); + if (rc != EOK) + return rc; + if (ch == '"' || ch == '\\') { + printf("\\%lc", (wint_t) ch); + } else if (ch <= 0x1f) { + printf("\\u%04x", (unsigned int) ch); + } else { + printf("%lc", (wint_t) ch); + } + } + printf("\""); + return EOK; +} + +static int print_blob(state_t *state, bithenge_node_t *node) +{ + bithenge_blob_t *blob = bithenge_node_as_blob(node); + aoff64_t pos = 0; + char buffer[1024]; + aoff64_t size = sizeof(buffer); + int rc; + printf(state->type == BITHENGE_PRINT_PYTHON ? "b\"" : "\""); + do { + rc = bithenge_blob_read(blob, pos, buffer, &size); + if (rc != EOK) + return rc; + for (aoff64_t i = 0; i < size; i++) + printf("\\x%02x", (unsigned int)(uint8_t)buffer[i]); + pos += size; + } while (size == sizeof(buffer)); + printf("\""); + return EOK; +} + +static int print_node(state_t *state, bithenge_node_t *tree) +{ + switch (bithenge_node_type(tree)) { + case BITHENGE_NODE_INTERNAL: + return print_internal(state, tree); + case BITHENGE_NODE_BOOLEAN: + return print_boolean(state, tree); + case BITHENGE_NODE_INTEGER: + return print_integer(state, tree); + case BITHENGE_NODE_STRING: + return print_string(state, tree); + case BITHENGE_NODE_BLOB: + return print_blob(state, tree); + } + return ENOTSUP; +} + +/** Print a tree as text. + * @param type The format to use. + * @param tree The root node of the tree to print. + * @return EOK on success or an error code from errno.h. */ +int bithenge_print_node(bithenge_print_type_t type, bithenge_node_t *tree) +{ + state_t state = {type, true, 0}; + return print_node(&state, tree); +} + +/** @} + */ Index: uspace/app/bithenge/print.h =================================================================== --- uspace/app/bithenge/print.h (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/app/bithenge/print.h (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,57 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Write a tree as JSON or other text formats. + */ + +#ifndef BITHENGE_PRINT_H_ +#define BITHENGE_PRINT_H_ + +#include "tree.h" + +/** Specifies the format to be used when printing. */ +typedef enum { + /** Print a Python value. Note that internal nodes will be represented + * as unordered dictionaries. */ + BITHENGE_PRINT_PYTHON, + /** Print JSON. Due to the limitations of JSON, type information may be + * lost. */ + BITHENGE_PRINT_JSON, +} bithenge_print_type_t; + +int bithenge_print_node(bithenge_print_type_t, bithenge_node_t *); + +#endif + +/** @} + */ Index: uspace/app/bithenge/script.c =================================================================== --- uspace/app/bithenge/script.c (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/app/bithenge/script.c (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,1208 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Script parsing. + */ + +#include +#include +#include +#include "compound.h" +#include "expression.h" +#include "os.h" +#include "script.h" +#include "sequence.h" +#include "transform.h" +#include "tree.h" + +/** Tokens with more characters than this may be read incorrectly. */ +#define MAX_TOKEN_SIZE 256 +#define BUFFER_SIZE 4096 + +/** Single-character symbols are represented by the character itself. Every + * other token uses one of these values: */ +typedef enum { + TOKEN_EQUALS = -128, + TOKEN_ERROR, + TOKEN_EOF, + TOKEN_IDENTIFIER, + TOKEN_INTEGER, + TOKEN_LEFT_ARROW, + + /* Keywords */ + TOKEN_DO, + TOKEN_ELSE, + TOKEN_FALSE, + TOKEN_IF, + TOKEN_IN, + TOKEN_PARTIAL, + TOKEN_REPEAT, + TOKEN_STRUCT, + TOKEN_SWITCH, + TOKEN_TRANSFORM, + TOKEN_TRUE, + TOKEN_WHILE, +} token_type_t; + +/** Singly-linked list of named transforms. */ +typedef struct transform_list { + char *name; + bithenge_transform_t *transform; + struct transform_list *next; +} transform_list_t; + +/** State kept by the parser. */ +typedef struct { + /** Rather than constantly checking return values, the parser uses this + * to indicate whether an error has occurred. */ + int error; + + /** The list of named transforms. */ + transform_list_t *transform_list; + + /** The name of the script file. */ + const char *filename; + /** The script file being read from. */ + FILE *file; + /** The buffer that holds script code. There is always a '\0' after the + * current position to prevent reading too far. */ + char buffer[BUFFER_SIZE]; + /** The start position within the buffer of the next unread token. */ + size_t buffer_pos; + /** The start position within the buffer of the current token. */ + size_t old_buffer_pos; + /** The line number of the current token. */ + int lineno; + /** Added to a buffer position to find the column number. */ + int line_offset; + + /** The type of the current token. */ + token_type_t token; + union { + /** The value of a TOKEN_IDENTIFIER token. Unless changed to + * NULL, it will be freed when the next token is read. */ + char *token_string; + /** The value of a TOKEN_INTEGER token. */ + bithenge_int_t token_int; + }; + + /** The names of the current transform's parameters. */ + char **parameter_names; + /** The number of parameters. */ + int num_params; + /** @a parse_expression sets this when TOKEN_IN is used. */ + bool in_node_used; +} state_t; + +/** Free the previous token's data. This must be called before changing + * state->token. */ +static void done_with_token(state_t *state) +{ + if (state->token == TOKEN_IDENTIFIER) + free(state->token_string); + state->token = TOKEN_ERROR; +} + +/** Note that an error has occurred if error is not EOK. */ +static void error_errno(state_t *state, int error) +{ + // Don't overwrite a previous error. + if (state->error == EOK && error != EOK) { + done_with_token(state); + state->token = TOKEN_ERROR; + state->error = error; + } +} + +/** Note that a syntax error has occurred and print an error message. */ +static void syntax_error(state_t *state, const char *message) +{ + // Printing multiple errors is confusing. + if (state->error == EOK) { + size_t start_char = state->old_buffer_pos + state->line_offset; + size_t end_char = state->buffer_pos + state->line_offset; + size_t size = end_char - start_char; + fprintf(stderr, "%s:%d:", state->filename, state->lineno); + if (size <= 1) + fprintf(stderr, "%zd: ", start_char); + else + fprintf(stderr, "%zd-%zd: ", start_char, end_char - 1); + fprintf(stderr, "%s: \"%.*s\"\n", message, (int)size, + state->buffer + state->old_buffer_pos); + error_errno(state, EINVAL); + } +} + +/** Ensure the buffer contains enough characters to read a token. */ +static void fill_buffer(state_t *state) +{ + if (state->buffer_pos + MAX_TOKEN_SIZE < BUFFER_SIZE) + return; + + size_t empty_size = state->buffer_pos; + size_t used_size = BUFFER_SIZE - 1 - state->buffer_pos; + memmove(state->buffer, state->buffer + state->buffer_pos, used_size); + state->line_offset += state->buffer_pos; + state->buffer_pos = 0; + + size_t read_size = fread(state->buffer + used_size, 1, empty_size, + state->file); + if (ferror(state->file)) + error_errno(state, EIO); + state->buffer[used_size + read_size] = '\0'; +} + +/** Read the next token. */ +static void next_token(state_t *state) +{ + fill_buffer(state); + done_with_token(state); + state->old_buffer_pos = state->buffer_pos; + char ch = state->buffer[state->buffer_pos]; + if (ch == '\0') { + state->token = TOKEN_EOF; + } else if (ch == '#') { + while (state->buffer[state->buffer_pos] != '\n' + && state->buffer[state->buffer_pos] != '\0') { + state->buffer_pos++; + fill_buffer(state); + } + next_token(state); + return; + } else if (isspace(ch)) { + // Will eventually reach the '\0' at the end + while (isspace(state->buffer[state->buffer_pos])) { + if (state->buffer[state->buffer_pos] == '\n') { + state->lineno++; + state->line_offset = -state->buffer_pos; + } + state->buffer_pos++; + } + next_token(state); + return; + } else if (isalpha(ch)) { + while (isalnum(state->buffer[state->buffer_pos]) + || state->buffer[state->buffer_pos] == '_') + state->buffer_pos++; + char *value = str_ndup(state->buffer + state->old_buffer_pos, + state->buffer_pos - state->old_buffer_pos); + if (!value) { + error_errno(state, ENOMEM); + } else if (!str_cmp(value, "do")) { + state->token = TOKEN_DO; + free(value); + } else if (!str_cmp(value, "else")) { + state->token = TOKEN_ELSE; + free(value); + } else if (!str_cmp(value, "false")) { + state->token = TOKEN_FALSE; + free(value); + } else if (!str_cmp(value, "if")) { + state->token = TOKEN_IF; + free(value); + } else if (!str_cmp(value, "in")) { + state->token = TOKEN_IN; + free(value); + } else if (!str_cmp(value, "partial")) { + state->token = TOKEN_PARTIAL; + free(value); + } else if (!str_cmp(value, "repeat")) { + state->token = TOKEN_REPEAT; + free(value); + } else if (!str_cmp(value, "struct")) { + state->token = TOKEN_STRUCT; + free(value); + } else if (!str_cmp(value, "switch")) { + state->token = TOKEN_SWITCH; + free(value); + } else if (!str_cmp(value, "transform")) { + state->token = TOKEN_TRANSFORM; + free(value); + } else if (!str_cmp(value, "true")) { + state->token = TOKEN_TRUE; + free(value); + } else if (!str_cmp(value, "while")) { + state->token = TOKEN_WHILE; + free(value); + } else { + state->token = TOKEN_IDENTIFIER; + state->token_string = value; + } + } else if (isdigit(ch)) { + while (isdigit(state->buffer[state->buffer_pos])) + state->buffer_pos++; + state->token = TOKEN_INTEGER; + int rc = bithenge_parse_int(state->buffer + + state->old_buffer_pos, &state->token_int); + error_errno(state, rc); + } else if (ch == '<') { + state->token = ch; + state->buffer_pos++; + if (state->buffer[state->buffer_pos] == '-') { + state->buffer_pos++; + state->token = TOKEN_LEFT_ARROW; + } + } else if (ch == '=') { + state->token = ch; + state->buffer_pos++; + if (state->buffer[state->buffer_pos] == '=') { + state->token = TOKEN_EQUALS; + state->buffer_pos++; + } + } else { + state->token = ch; + state->buffer_pos++; + } +} + +/** Allocate memory and handle failure by setting the error in the state. The + * caller must check the state for errors before using the return value of this + * function. */ +static void *state_malloc(state_t *state, size_t size) +{ + if (state->error != EOK) + return NULL; + void *result = malloc(size); + if (result == NULL) + error_errno(state, ENOMEM); + return result; +} + +/** Reallocate memory and handle failure by setting the error in the state. If + * an error occurs, the existing pointer will be returned. */ +static void *state_realloc(state_t *state, void *ptr, size_t size) +{ + if (state->error != EOK) + return ptr; + void *result = realloc(ptr, size); + if (result == NULL) { + error_errno(state, ENOMEM); + return ptr; + } + return result; +} + +/** Expect and consume a certain token. If the next token is of the wrong type, + * an error is caused. */ +static void expect(state_t *state, token_type_t type) +{ + if (state->token != type) { + syntax_error(state, "unexpected"); + return; + } + next_token(state); +} + +/** Expect and consume an identifier token. If the next token is not an + * identifier, an error is caused and this function returns null. */ +static char *expect_identifier(state_t *state) +{ + if (state->token != TOKEN_IDENTIFIER) { + syntax_error(state, "unexpected (identifier expected)"); + return NULL; + } + char *val = state->token_string; + state->token_string = NULL; + next_token(state); + return val; +} + +/** Find a transform by name. A reference will be added to the transform. + * @return The found transform, or NULL if none was found. */ +static bithenge_transform_t *get_named_transform(state_t *state, + const char *name) +{ + for (transform_list_t *e = state->transform_list; e; e = e->next) { + if (!str_cmp(e->name, name)) { + bithenge_transform_inc_ref(e->transform); + return e->transform; + } + } + for (int i = 0; bithenge_primitive_transforms[i].name; i++) { + if (!str_cmp(bithenge_primitive_transforms[i].name, name)) { + bithenge_transform_t *xform = + bithenge_primitive_transforms[i].transform; + bithenge_transform_inc_ref(xform); + return xform; + } + } + return NULL; +} + +/** Add a named transform. This function takes ownership of the name and a + * reference to the transform. If an error has occurred, either may be null. */ +static void add_named_transform(state_t *state, bithenge_transform_t *xform, char *name) +{ + transform_list_t *entry = state_malloc(state, sizeof(*entry)); + if (state->error != EOK) { + free(name); + bithenge_transform_dec_ref(xform); + free(entry); + return; + } + entry->name = name; + entry->transform = xform; + entry->next = state->transform_list; + state->transform_list = entry; +} + +static bithenge_transform_t *parse_transform(state_t *state); +static bithenge_transform_t *parse_struct(state_t *state); +static bithenge_expression_t *parse_expression(state_t *state); + + + +/***************** Expressions *****************/ + +typedef enum { + PRECEDENCE_NONE, + PRECEDENCE_EQUALS, + PRECEDENCE_ADD, + PRECEDENCE_MULTIPLY, +} precedence_t; + +static bithenge_binary_op_t token_as_binary_operator(token_type_t token) +{ + switch ((int)token) { + case '+': + return BITHENGE_EXPRESSION_ADD; + case '-': + return BITHENGE_EXPRESSION_SUBTRACT; + case '*': + return BITHENGE_EXPRESSION_MULTIPLY; + case TOKEN_EQUALS: + return BITHENGE_EXPRESSION_EQUALS; + default: + return BITHENGE_EXPRESSION_INVALID_BINARY_OP; + } +} + +static precedence_t binary_operator_precedence(bithenge_binary_op_t op) +{ + switch (op) { + case BITHENGE_EXPRESSION_ADD: /* fallthrough */ + case BITHENGE_EXPRESSION_SUBTRACT: + return PRECEDENCE_ADD; + case BITHENGE_EXPRESSION_MULTIPLY: + return PRECEDENCE_MULTIPLY; + case BITHENGE_EXPRESSION_EQUALS: + return PRECEDENCE_EQUALS; + default: + assert(false); + return PRECEDENCE_NONE; + } +} + +static bithenge_expression_t *parse_term(state_t *state) +{ + int rc; + if (state->token == TOKEN_TRUE || state->token == TOKEN_FALSE) { + bool val = state->token == TOKEN_TRUE; + next_token(state); + bithenge_node_t *node; + rc = bithenge_new_boolean_node(&node, val); + if (rc != EOK) { + error_errno(state, rc); + return NULL; + } + + bithenge_expression_t *expr; + rc = bithenge_const_expression(&expr, node); + if (rc != EOK) { + error_errno(state, rc); + return NULL; + } + + return expr; + } else if (state->token == TOKEN_IN) { + next_token(state); + state->in_node_used = true; + bithenge_expression_t *expr; + rc = bithenge_in_node_expression(&expr); + if (rc != EOK) { + error_errno(state, rc); + return NULL; + } + return expr; + } else if (state->token == TOKEN_INTEGER) { + bithenge_int_t val = state->token_int; + next_token(state); + bithenge_node_t *node; + rc = bithenge_new_integer_node(&node, val); + if (rc != EOK) { + error_errno(state, rc); + return NULL; + } + + bithenge_expression_t *expr; + rc = bithenge_const_expression(&expr, node); + if (rc != EOK) { + error_errno(state, rc); + return NULL; + } + + return expr; + } else if (state->token == TOKEN_IDENTIFIER) { + int i; + for (i = 0; i < state->num_params; i++) + if (!str_cmp(state->parameter_names[i], + state->token_string)) + break; + + if (i == state->num_params) { + syntax_error(state, "unknown identifier"); + return NULL; + } + + bithenge_expression_t *expr; + rc = bithenge_param_expression(&expr, i); + if (rc != EOK) { + error_errno(state, rc); + return NULL; + } + + next_token(state); + + return expr; + } else if (state->token == '.') { + next_token(state); + + const char *id = expect_identifier(state); + bithenge_node_t *key = NULL; + bithenge_expression_t *expr = NULL; + + if (state->error == EOK) { + rc = bithenge_new_string_node(&key, id, true); + id = NULL; + error_errno(state, rc); + } + + if (state->error == EOK) { + rc = bithenge_scope_member_expression(&expr, key); + key = NULL; + if (rc != EOK) + expr = NULL; + error_errno(state, rc); + } + + if (state->error != EOK) { + free((char *)id); + bithenge_node_dec_ref(key); + bithenge_expression_dec_ref(expr); + return NULL; + } + + return expr; + } else if (state->token == '(') { + next_token(state); + bithenge_expression_t *expr = parse_expression(state); + expect(state, ')'); + return expr; + } else { + syntax_error(state, "expression expected"); + return NULL; + } +} + +static bithenge_expression_t *parse_postfix_expression(state_t *state) +{ + int rc; + bithenge_expression_t *expr = parse_term(state); + while (state->error == EOK) { + if (state->token == '.') { + next_token(state); + + const char *id = expect_identifier(state); + + if (state->error != EOK) { + free((char *)id); + bithenge_expression_dec_ref(expr); + return NULL; + } + + bithenge_node_t *key = NULL; + rc = bithenge_new_string_node(&key, id, true); + if (rc != EOK) { + error_errno(state, rc); + bithenge_expression_dec_ref(expr); + return NULL; + } + + rc = bithenge_member_expression(&expr, expr, key); + if (rc != EOK) { + error_errno(state, rc); + return NULL; + } + } else if (state->token == '[') { + next_token(state); + bithenge_expression_t *start = parse_expression(state); + bool absolute_limit = false; + if (state->token == ',') { + absolute_limit = false; + next_token(state); + } else if (state->token == ':') { + absolute_limit = true; + next_token(state); + } else { + syntax_error(state, "expected ',' or ':'"); + } + bithenge_expression_t *limit = NULL; + if (!(state->token == ']' && absolute_limit)) + limit = parse_expression(state); + expect(state, ']'); + + if (state->error != EOK) { + bithenge_expression_dec_ref(expr); + bithenge_expression_dec_ref(start); + bithenge_expression_dec_ref(limit); + return NULL; + } + rc = bithenge_subblob_expression(&expr, expr, start, + limit, absolute_limit); + if (rc != EOK) { + error_errno(state, rc); + return NULL; + } + } else { + break; + } + } + return expr; +} + +static bithenge_expression_t *parse_expression_precedence(state_t *state, + precedence_t prev_precedence) +{ + bithenge_expression_t *expr = parse_postfix_expression(state); + while (state->error == EOK) { + bithenge_binary_op_t op = + token_as_binary_operator(state->token); + if (op == BITHENGE_EXPRESSION_INVALID_BINARY_OP) + break; + precedence_t precedence = binary_operator_precedence(op); + if (precedence <= prev_precedence) + break; + next_token(state); + + bithenge_expression_t *expr2 = parse_postfix_expression(state); + if (state->error != EOK) { + bithenge_expression_dec_ref(expr2); + break; + } + int rc = bithenge_binary_expression(&expr, op, expr, expr2); + if (rc != EOK) + error_errno(state, rc); + } + if (state->error != EOK) { + bithenge_expression_dec_ref(expr); + expr = NULL; + } + return expr; +} + +static bithenge_expression_t *parse_expression(state_t *state) +{ + return parse_expression_precedence(state, PRECEDENCE_NONE); +} + + + +/* state->token must be TOKEN_IDENTIFIER when this is called. */ +static bithenge_transform_t *parse_invocation(state_t *state) +{ + bithenge_transform_t *result = get_named_transform(state, + state->token_string); + if (!result) + syntax_error(state, "transform not found"); + next_token(state); + + bithenge_expression_t **params = NULL; + int num_params = 0; + if (state->token == '(') { + next_token(state); + while (state->error == EOK && state->token != ')') { + if (num_params) + expect(state, ','); + params = state_realloc(state, params, + (num_params + 1)*sizeof(*params)); + if (state->error != EOK) + break; + params[num_params] = parse_expression(state); + num_params++; + } + expect(state, ')'); + } + + /* TODO: show correct error position */ + if (state->error == EOK + && bithenge_transform_num_params(result) != num_params) + syntax_error(state, "incorrect number of parameters before"); + + if (state->error != EOK) { + while (num_params--) + bithenge_expression_dec_ref(params[num_params]); + free(params); + bithenge_transform_dec_ref(result); + return NULL; + } + + if (num_params) { + int rc = bithenge_param_wrapper(&result, result, params); + if (rc != EOK) { + error_errno(state, rc); + result = NULL; + } + } + + return result; +} + +/** Create a transform that just produces an empty node. + * @param state The parser state. + * @return The new transform, or NULL on error. */ +static bithenge_transform_t *make_empty_transform(state_t *state) +{ + bithenge_node_t *node; + int rc = bithenge_new_empty_internal_node(&node); + if (rc != EOK) { + error_errno(state, rc); + return NULL; + } + + bithenge_expression_t *expr; + rc = bithenge_const_expression(&expr, node); + if (rc != EOK) { + error_errno(state, rc); + return NULL; + } + + bithenge_transform_t *xform; + rc = bithenge_inputless_transform(&xform, expr); + if (rc != EOK) { + error_errno(state, rc); + return NULL; + } + + return xform; +} + +static bithenge_transform_t *parse_if(state_t *state, bool in_struct) +{ + expect(state, TOKEN_IF); + expect(state, '('); + bithenge_expression_t *expr = parse_expression(state); + expect(state, ')'); + expect(state, '{'); + bithenge_transform_t *true_xform = + in_struct ? parse_struct(state) : parse_transform(state); + expect(state, '}'); + + bithenge_transform_t *false_xform = NULL; + if (state->token == TOKEN_ELSE) { + next_token(state); + expect(state, '{'); + false_xform = + in_struct ? parse_struct(state) : parse_transform(state); + expect(state, '}'); + } else { + if (in_struct) + false_xform = make_empty_transform(state); + else + syntax_error(state, "else expected"); + } + + if (state->error != EOK) { + bithenge_expression_dec_ref(expr); + bithenge_transform_dec_ref(true_xform); + bithenge_transform_dec_ref(false_xform); + return NULL; + } + + bithenge_transform_t *if_xform; + int rc = bithenge_if_transform(&if_xform, expr, true_xform, + false_xform); + if (rc != EOK) { + error_errno(state, rc); + return NULL; + } + return if_xform; +} + +static bithenge_transform_t *parse_switch(state_t *state, bool in_struct) +{ + expect(state, TOKEN_SWITCH); + expect(state, '('); + bithenge_expression_t *ref_expr = parse_expression(state); + expect(state, ')'); + expect(state, '{'); + int num = 0; + bithenge_expression_t **exprs = NULL; + bithenge_transform_t **xforms = NULL; + while (state->error == EOK && state->token != '}') { + bithenge_expression_t *expr; + if (state->token == TOKEN_ELSE) { + next_token(state); + bithenge_node_t *node; + int rc = bithenge_new_boolean_node(&node, true); + if (rc != EOK) { + error_errno(state, rc); + break; + } + rc = bithenge_const_expression(&expr, node); + if (rc != EOK) { + error_errno(state, rc); + break; + } + } else { + expr = parse_expression(state); + if (state->error == EOK) { + bithenge_expression_inc_ref(ref_expr); + int rc = bithenge_binary_expression(&expr, + BITHENGE_EXPRESSION_EQUALS, ref_expr, + expr); + if (rc != EOK) { + error_errno(state, rc); + break; + } + } + } + + expect(state, ':'); + bithenge_transform_t *xform; + if (in_struct) { + expect(state, '{'); + xform = parse_struct(state); + expect(state, '}'); + } else + xform = parse_transform(state); + expect(state, ';'); + + exprs = state_realloc(state, exprs, + sizeof(*exprs) * (num + 1)); + xforms = state_realloc(state, xforms, + sizeof(*xforms) * (num + 1)); + if (state->error != EOK) { + bithenge_expression_dec_ref(expr); + bithenge_transform_dec_ref(xform); + break; + } + + exprs[num] = expr; + xforms[num] = xform; + num++; + } + bithenge_expression_dec_ref(ref_expr); + + bithenge_transform_t *switch_xform = &bithenge_invalid_transform; + bithenge_transform_inc_ref(switch_xform); + while (state->error == EOK && num >= 1) { + num--; + int rc = bithenge_if_transform(&switch_xform, exprs[num], + xforms[num], switch_xform); + if (rc != EOK) + error_errno(state, rc); + } + + while (num >= 1) { + num--; + bithenge_expression_dec_ref(exprs[num]); + bithenge_transform_dec_ref(xforms[num]); + } + free(exprs); + free(xforms); + + expect(state, '}'); + return switch_xform; +} + +static bithenge_transform_t *parse_repeat(state_t *state) +{ + expect(state, TOKEN_REPEAT); + bithenge_expression_t *expr = NULL; + if (state->token == '(') { + next_token(state); + expr = parse_expression(state); + expect(state, ')'); + } + expect(state, '{'); + bithenge_transform_t *xform = parse_transform(state); + expect(state, '}'); + + if (state->error != EOK) { + bithenge_expression_dec_ref(expr); + bithenge_transform_dec_ref(xform); + return NULL; + } + + bithenge_transform_t *repeat_xform; + int rc = bithenge_repeat_transform(&repeat_xform, xform, expr); + if (rc != EOK) { + error_errno(state, rc); + return NULL; + } + return repeat_xform; +} + +static bithenge_transform_t *parse_do_while(state_t *state) +{ + expect(state, TOKEN_DO); + expect(state, '{'); + bithenge_transform_t *xform = parse_transform(state); + expect(state, '}'); + expect(state, TOKEN_WHILE); + expect(state, '('); + bithenge_expression_t *expr = parse_expression(state); + expect(state, ')'); + + if (state->error != EOK) { + bithenge_expression_dec_ref(expr); + bithenge_transform_dec_ref(xform); + return NULL; + } + + bithenge_transform_t *do_while_xform; + int rc = bithenge_do_while_transform(&do_while_xform, xform, expr); + if (rc != EOK) { + error_errno(state, rc); + return NULL; + } + return do_while_xform; +} + +static bithenge_transform_t *parse_partial(state_t *state) +{ + expect(state, TOKEN_PARTIAL); + bithenge_transform_t *offset_xform = NULL; + if (state->token == '(') { + next_token(state); + bithenge_expression_t *offset = parse_expression(state); + expect(state, ')'); + + bithenge_expression_t *in_expr; + int rc = bithenge_in_node_expression(&in_expr); + if (rc != EOK) + error_errno(state, rc); + if (state->error != EOK) { + bithenge_expression_dec_ref(offset); + return NULL; + } + + rc = bithenge_subblob_expression(&offset, in_expr, offset, + NULL, true); + if (rc != EOK) { + error_errno(state, rc); + return NULL; + } + + rc = bithenge_expression_transform(&offset_xform, offset); + if (rc != EOK) { + error_errno(state, rc); + return NULL; + } + } + expect(state, '{'); + bithenge_transform_t *xform = parse_transform(state); + expect(state, '}'); + if (state->error != EOK) { + bithenge_transform_dec_ref(offset_xform); + bithenge_transform_dec_ref(xform); + return NULL; + } + + int rc = bithenge_partial_transform(&xform, xform); + if (rc != EOK) { + error_errno(state, rc); + bithenge_transform_dec_ref(offset_xform); + return NULL; + } + + if (offset_xform) { + bithenge_transform_t **xforms = malloc(2 * sizeof(*xforms)); + if (!xforms) { + error_errno(state, ENOMEM); + bithenge_transform_dec_ref(xform); + bithenge_transform_dec_ref(offset_xform); + return NULL; + } + xforms[0] = xform; + xforms[1] = offset_xform; + rc = bithenge_new_composed_transform(&xform, xforms, 2); + if (rc != EOK) { + error_errno(state, rc); + return NULL; + } + } + + return xform; +} + +/* The TOKEN_STRUCT and '{' must already have been skipped. */ +static bithenge_transform_t *parse_struct(state_t *state) +{ + size_t num = 0; + bithenge_named_transform_t *subxforms; + /* We keep an extra space for the {NULL, NULL} terminator. */ + subxforms = state_malloc(state, sizeof(*subxforms)); + while (state->error == EOK && state->token != '}') { + if (state->token == TOKEN_IF) { + subxforms[num].transform = parse_if(state, true); + subxforms[num].name = NULL; + } else if (state->token == TOKEN_SWITCH) { + subxforms[num].transform = parse_switch(state, true); + subxforms[num].name = NULL; + } else { + if (state->token == '.') { + next_token(state); + subxforms[num].name = expect_identifier(state); + } else { + subxforms[num].name = NULL; + } + expect(state, TOKEN_LEFT_ARROW); + subxforms[num].transform = parse_transform(state); + expect(state, ';'); + } + num++; + subxforms = state_realloc(state, subxforms, + (num + 1)*sizeof(*subxforms)); + } + + if (state->error != EOK) { + while (num--) { + free((void *)subxforms[num].name); + bithenge_transform_dec_ref(subxforms[num].transform); + } + free(subxforms); + return NULL; + } + + subxforms[num].name = NULL; + subxforms[num].transform = NULL; + bithenge_transform_t *result; + int rc = bithenge_new_struct(&result, subxforms); + if (rc != EOK) { + error_errno(state, rc); + return NULL; + } + return result; +} + +/** Parse a transform without composition. + * @return The parsed transform, or NULL if an error occurred. */ +static bithenge_transform_t *parse_transform_no_compose(state_t *state) +{ + if (state->token == '(') { + next_token(state); + state->in_node_used = false; + bithenge_expression_t *expr = parse_expression(state); + expect(state, ')'); + if (state->error != EOK) { + bithenge_expression_dec_ref(expr); + return NULL; + } + + bithenge_transform_t *xform; + int rc; + if (state->in_node_used) + rc = bithenge_expression_transform(&xform, expr); + else + rc = bithenge_inputless_transform(&xform, expr); + if (rc != EOK) { + error_errno(state, rc); + return NULL; + } + return xform; + } else if (state->token == TOKEN_DO) { + return parse_do_while(state); + } else if (state->token == TOKEN_IDENTIFIER) { + return parse_invocation(state); + } else if (state->token == TOKEN_IF) { + return parse_if(state, false); + } else if (state->token == TOKEN_PARTIAL) { + return parse_partial(state); + } else if (state->token == TOKEN_REPEAT) { + return parse_repeat(state); + } else if (state->token == TOKEN_STRUCT) { + next_token(state); + expect(state, '{'); + bithenge_transform_t *xform = parse_struct(state); + expect(state, '}'); + return xform; + } else if (state->token == TOKEN_SWITCH) { + return parse_switch(state, false); + } else { + syntax_error(state, "unexpected (transform expected)"); + return NULL; + } +} + +/** Parse a transform. + * @return The parsed transform, or NULL if an error occurred. */ +static bithenge_transform_t *parse_transform(state_t *state) +{ + bithenge_transform_t *result = parse_transform_no_compose(state); + bithenge_transform_t **xforms = NULL; + size_t num = 1; + while (state->token == TOKEN_LEFT_ARROW) { + expect(state, TOKEN_LEFT_ARROW); + xforms = state_realloc(state, xforms, + (num + 1) * sizeof(*xforms)); + if (state->error != EOK) + break; + xforms[num] = parse_transform_no_compose(state); + num++; + } + if (state->error != EOK) { + while (xforms && num--) + bithenge_transform_dec_ref(xforms[num]); + free(xforms); + bithenge_transform_dec_ref(result); + return NULL; + } + if (xforms) { + xforms[0] = result; + int rc = bithenge_new_composed_transform(&result, xforms, num); + if (rc != EOK) { + error_errno(state, rc); + return NULL; + } + } + return result; +} + +/** Parse a definition. */ +static void parse_definition(state_t *state) +{ + expect(state, TOKEN_TRANSFORM); + char *name = expect_identifier(state); + + if (state->token == '(') { + next_token(state); + while (state->error == EOK && state->token != ')') { + if (state->num_params) + expect(state, ','); + state->parameter_names = state_realloc(state, + state->parameter_names, + (state->num_params + 1)*sizeof(*state->parameter_names)); + if (state->error != EOK) + break; + state->parameter_names[state->num_params++] = + expect_identifier(state); + } + expect(state, ')'); + } + + expect(state, '='); + bithenge_transform_t *xform = parse_transform(state); + expect(state, ';'); + + if (state->error == EOK) { + int rc = bithenge_new_barrier_transform(&xform, xform, + state->num_params); + if (rc != EOK) { + xform = NULL; + error_errno(state, rc); + } + } + + add_named_transform(state, xform, name); + + for (int i = 0; i < state->num_params; i++) + free(state->parameter_names[i]); + free(state->parameter_names); + state->parameter_names = NULL; + state->num_params = 0; +} + +/** Initialize the state. */ +static void state_init(state_t *state, const char *filename) +{ + state->error = EOK; + state->transform_list = NULL; + state->parameter_names = NULL; + state->num_params = 0; + state->token = TOKEN_ERROR; + state->old_buffer_pos = state->buffer_pos = BUFFER_SIZE - 1; + state->lineno = 1; + state->line_offset = (int)-state->buffer_pos + 1; + state->filename = filename; + state->file = fopen(filename, "r"); + if (!state->file) { + error_errno(state, errno); + } else { + next_token(state); + } +} + +/** Destroy the state. */ +static void state_destroy(state_t *state) +{ + done_with_token(state); + state->token = TOKEN_ERROR; + if (state->file) + fclose(state->file); + transform_list_t *entry = state->transform_list; + while (entry) { + transform_list_t *next = entry->next; + free(entry->name); + bithenge_transform_dec_ref(entry->transform); + free(entry); + entry = next; + } + for (int i = 0; i < state->num_params; i++) + free(state->parameter_names[i]); + free(state->parameter_names); +} + +/** Parse a script file. + * @param filename The name of the script file. + * @param[out] out Stores the "main" transform. + * @return EOK on success, EINVAL on syntax error, or an error code from + * errno.h. */ +int bithenge_parse_script(const char *filename, bithenge_transform_t **out) +{ + state_t state; + state_init(&state, filename); + while (state.error == EOK && state.token != TOKEN_EOF) + parse_definition(&state); + *out = get_named_transform(&state, "main"); + int rc = state.error; + state_destroy(&state); + if (rc == EOK && !*out) { + fprintf(stderr, "no \"main\" transform\n"); + rc = EINVAL; + } + return rc; +} + +/** @} + */ Index: uspace/app/bithenge/script.h =================================================================== --- uspace/app/bithenge/script.h (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/app/bithenge/script.h (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,47 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Script parsing. + */ + +#ifndef BITHENGE_SCRIPT_H_ +#define BITHENGE_SCRIPT_H_ + +#include "transform.h" + +int bithenge_parse_script(const char *, bithenge_transform_t **); + +#endif + +/** @} + */ Index: uspace/app/bithenge/sequence.c =================================================================== --- uspace/app/bithenge/sequence.c (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/app/bithenge/sequence.c (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,1132 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Sequence transforms. + */ + +#include +#include "blob.h" +#include "expression.h" +#include "os.h" +#include "sequence.h" +#include "tree.h" + + + +/***************** seq_node *****************/ + +typedef struct { + bithenge_node_t base; + const struct seq_node_ops *ops; + bithenge_blob_t *blob; + bithenge_scope_t *scope; + aoff64_t *ends; + size_t num_ends; + bool end_on_empty; + bithenge_int_t num_xforms; +} seq_node_t; + +typedef struct seq_node_ops { + int (*get_transform)(seq_node_t *self, bithenge_transform_t **out, + bithenge_int_t index); +} seq_node_ops_t; + +static bithenge_node_t *seq_as_node(seq_node_t *node) +{ + return &node->base; +} + +static seq_node_t *node_as_seq(bithenge_node_t *node) +{ + return (seq_node_t *)node; +} + +static int seq_node_field_offset(seq_node_t *self, aoff64_t *out, size_t index) +{ + if (index == 0) { + *out = 0; + return EOK; + } + index--; + aoff64_t prev_offset = + self->num_ends ? self->ends[self->num_ends - 1] : 0; + for (; self->num_ends <= index; self->num_ends++) { + bithenge_transform_t *subxform; + int rc = self->ops->get_transform(self, &subxform, + self->num_ends); + if (rc != EOK) + return rc; + + bithenge_node_t *subblob_node; + bithenge_blob_inc_ref(self->blob); + rc = bithenge_new_offset_blob(&subblob_node, self->blob, + prev_offset); + if (rc != EOK) { + bithenge_transform_dec_ref(subxform); + return rc; + } + + if (self->end_on_empty) { + bool empty; + rc = bithenge_blob_empty( + bithenge_node_as_blob(subblob_node), &empty); + if (rc == EOK && empty) { + self->num_xforms = self->num_ends; + rc = ENOENT; + } + if (rc != EOK) { + bithenge_transform_dec_ref(subxform); + bithenge_node_dec_ref(subblob_node); + return rc; + } + } + + bithenge_blob_t *subblob = bithenge_node_as_blob(subblob_node); + aoff64_t field_size; + rc = bithenge_transform_prefix_length(subxform, self->scope, + subblob, &field_size); + bithenge_node_dec_ref(subblob_node); + bithenge_transform_dec_ref(subxform); + if (rc != EOK) + return rc; + + if (self->num_xforms == -1) { + aoff64_t *new_ends = realloc(self->ends, + (self->num_ends + 1)*sizeof(*new_ends)); + if (!new_ends) + return ENOMEM; + self->ends = new_ends; + } + + prev_offset = self->ends[self->num_ends] = + prev_offset + field_size; + } + *out = self->ends[index]; + return EOK; +} + +static int seq_node_subtransform(seq_node_t *self, bithenge_node_t **out, + size_t index) +{ + aoff64_t start_pos; + int rc = seq_node_field_offset(self, &start_pos, index); + if (rc != EOK) + return rc; + + bithenge_transform_t *subxform; + rc = self->ops->get_transform(self, &subxform, index); + if (rc != EOK) + return rc; + + if (index == self->num_ends) { + /* We can apply the subtransform and cache its prefix length at + * the same time. */ + bithenge_node_t *blob_node; + bithenge_blob_inc_ref(self->blob); + rc = bithenge_new_offset_blob(&blob_node, self->blob, + start_pos); + if (rc != EOK) { + bithenge_transform_dec_ref(subxform); + return rc; + } + + if (self->end_on_empty) { + bool empty; + rc = bithenge_blob_empty( + bithenge_node_as_blob(blob_node), &empty); + if (rc == EOK && empty) { + self->num_xforms = self->num_ends; + rc = ENOENT; + } + if (rc != EOK) { + bithenge_transform_dec_ref(subxform); + bithenge_node_dec_ref(blob_node); + return rc; + } + } + + aoff64_t size; + rc = bithenge_transform_prefix_apply(subxform, self->scope, + bithenge_node_as_blob(blob_node), out, &size); + bithenge_node_dec_ref(blob_node); + bithenge_transform_dec_ref(subxform); + if (rc != EOK) + return rc; + + if (self->num_xforms == -1) { + aoff64_t *new_ends = realloc(self->ends, + (self->num_ends + 1)*sizeof(*new_ends)); + if (!new_ends) + return ENOMEM; + self->ends = new_ends; + } + self->ends[self->num_ends++] = start_pos + size; + } else { + aoff64_t end_pos; + int rc = seq_node_field_offset(self, &end_pos, index + 1); + if (rc != EOK) { + bithenge_transform_dec_ref(subxform); + return rc; + } + + bithenge_node_t *blob_node; + bithenge_blob_inc_ref(self->blob); + rc = bithenge_new_subblob(&blob_node, self->blob, start_pos, + end_pos - start_pos); + if (rc != EOK) { + bithenge_transform_dec_ref(subxform); + return rc; + } + + rc = bithenge_transform_apply(subxform, self->scope, blob_node, + out); + bithenge_node_dec_ref(blob_node); + bithenge_transform_dec_ref(subxform); + if (rc != EOK) + return rc; + } + + return EOK; +} + +static int seq_node_complete(seq_node_t *self, bool *out) +{ + aoff64_t blob_size, end_pos; + int rc = bithenge_blob_size(self->blob, &blob_size); + if (rc != EOK) + return rc; + rc = seq_node_field_offset(self, &end_pos, self->num_xforms); + if (rc != EOK) + return rc; + *out = blob_size == end_pos; + return EOK; +} + +static void seq_node_destroy(seq_node_t *self) +{ + bithenge_scope_dec_ref(self->scope); + bithenge_blob_dec_ref(self->blob); + free(self->ends); +} + +static void seq_node_set_num_xforms(seq_node_t *self, + bithenge_int_t num_xforms) +{ + self->num_xforms = num_xforms; +} + +static bithenge_scope_t *seq_node_scope(seq_node_t *self) +{ + return self->scope; +} + +static int seq_node_init(seq_node_t *self, const seq_node_ops_t *ops, + bithenge_scope_t *scope, bithenge_blob_t *blob, bithenge_int_t num_xforms, + bool end_on_empty) +{ + self->ops = ops; + if (num_xforms != -1) { + self->ends = malloc(sizeof(*self->ends) * num_xforms); + if (!self->ends) + return ENOMEM; + } else + self->ends = NULL; + bithenge_blob_inc_ref(blob); + self->blob = blob; + self->num_xforms = num_xforms; + self->num_ends = 0; + self->end_on_empty = end_on_empty; + self->scope = scope; + if (self->scope) + bithenge_scope_inc_ref(self->scope); + return EOK; +} + + + +/***************** bithenge_new_struct *****************/ + +typedef struct { + bithenge_transform_t base; + bithenge_named_transform_t *subtransforms; + size_t num_subtransforms; +} struct_transform_t; + +static bithenge_transform_t *struct_as_transform(struct_transform_t *xform) +{ + return &xform->base; +} + +static struct_transform_t *transform_as_struct(bithenge_transform_t *xform) +{ + return (struct_transform_t *)xform; +} + +typedef struct { + seq_node_t base; + struct_transform_t *transform; + bool prefix; +} struct_node_t; + +static seq_node_t *struct_as_seq(struct_node_t *node) +{ + return &node->base; +} + +static struct_node_t *seq_as_struct(seq_node_t *base) +{ + return (struct_node_t *)base; +} + +static bithenge_node_t *struct_as_node(struct_node_t *node) +{ + return seq_as_node(struct_as_seq(node)); +} + +static struct_node_t *node_as_struct(bithenge_node_t *node) +{ + return seq_as_struct(node_as_seq(node)); +} + +static int struct_node_for_each(bithenge_node_t *base, + bithenge_for_each_func_t func, void *data) +{ + int rc = EOK; + struct_node_t *self = node_as_struct(base); + bithenge_named_transform_t *subxforms = + self->transform->subtransforms; + + for (bithenge_int_t i = 0; subxforms[i].transform; i++) { + bithenge_node_t *subxform_result; + rc = seq_node_subtransform(struct_as_seq(self), + &subxform_result, i); + if (rc != EOK) + return rc; + + if (subxforms[i].name) { + bithenge_node_t *name_node; + rc = bithenge_new_string_node(&name_node, + subxforms[i].name, false); + if (rc == EOK) { + rc = func(name_node, subxform_result, data); + subxform_result = NULL; + } + } else { + if (bithenge_node_type(subxform_result) != + BITHENGE_NODE_INTERNAL) { + rc = EINVAL; + } else { + rc = bithenge_node_for_each(subxform_result, + func, data); + } + } + bithenge_node_dec_ref(subxform_result); + if (rc != EOK) + return rc; + } + + if (!self->prefix) { + bool complete; + rc = seq_node_complete(struct_as_seq(self), &complete); + if (rc != EOK) + return rc; + if (!complete) + return EINVAL; + } + + return rc; +} + +static int struct_node_get(bithenge_node_t *base, bithenge_node_t *key, + bithenge_node_t **out) +{ + struct_node_t *self = node_as_struct(base); + + int rc = ENOENT; + if (bithenge_node_type(key) != BITHENGE_NODE_STRING) + goto end; + const char *name = bithenge_string_node_value(key); + + const bithenge_named_transform_t *subxforms = + self->transform->subtransforms; + for (bithenge_int_t i = 0; subxforms[i].transform; i++) { + if (subxforms[i].name && !str_cmp(name, subxforms[i].name)) { + rc = seq_node_subtransform(struct_as_seq(self), out, i); + goto end; + } + } + + for (bithenge_int_t i = 0; subxforms[i].transform; i++) { + if (subxforms[i].name) + continue; + bithenge_node_t *subxform_result; + rc = seq_node_subtransform(struct_as_seq(self), + &subxform_result, i); + if (rc != EOK) + goto end; + if (bithenge_node_type(subxform_result) != + BITHENGE_NODE_INTERNAL) { + bithenge_node_dec_ref(subxform_result); + rc = EINVAL; + goto end; + } + bithenge_node_inc_ref(key); + rc = bithenge_node_get(subxform_result, key, out); + bithenge_node_dec_ref(subxform_result); + if (rc != ENOENT) + goto end; + } + + rc = ENOENT; +end: + bithenge_node_dec_ref(key); + return rc; +} + +static void struct_node_destroy(bithenge_node_t *base) +{ + struct_node_t *node = node_as_struct(base); + + /* We didn't inc_ref for the scope in struct_transform_make_node, so + * make sure it doesn't try to dec_ref. */ + seq_node_scope(struct_as_seq(node))->current_node = NULL; + seq_node_destroy(struct_as_seq(node)); + + bithenge_transform_dec_ref(struct_as_transform(node->transform)); + free(node); +} + +static const bithenge_internal_node_ops_t struct_node_ops = { + .for_each = struct_node_for_each, + .get = struct_node_get, + .destroy = struct_node_destroy, +}; + +static int struct_node_get_transform(seq_node_t *base, + bithenge_transform_t **out, bithenge_int_t index) +{ + struct_node_t *self = seq_as_struct(base); + *out = self->transform->subtransforms[index].transform; + bithenge_transform_inc_ref(*out); + return EOK; +} + +static const seq_node_ops_t struct_node_seq_ops = { + .get_transform = struct_node_get_transform, +}; + +static int struct_transform_make_node(struct_transform_t *self, + bithenge_node_t **out, bithenge_scope_t *scope, bithenge_blob_t *blob, + bool prefix) +{ + struct_node_t *node = malloc(sizeof(*node)); + if (!node) + return ENOMEM; + + int rc = bithenge_init_internal_node(struct_as_node(node), + &struct_node_ops); + if (rc != EOK) { + free(node); + return rc; + } + bithenge_scope_t *inner; + rc = bithenge_scope_new(&inner, scope); + if (rc != EOK) { + free(node); + return rc; + } + /* We should inc_ref(node) here, but that would make a cycle. Instead, + * we leave it 1 too low, so that when the only remaining use of node + * is the scope, node will be destroyed. Also see the comment in + * struct_node_destroy. */ + bithenge_scope_set_current_node(inner, struct_as_node(node)); + + rc = seq_node_init(struct_as_seq(node), &struct_node_seq_ops, inner, + blob, self->num_subtransforms, false); + bithenge_scope_dec_ref(inner); + if (rc != EOK) { + free(node); + return rc; + } + + bithenge_transform_inc_ref(struct_as_transform(self)); + node->transform = self; + node->prefix = prefix; + *out = struct_as_node(node); + + return EOK; +} + +static int struct_transform_apply(bithenge_transform_t *base, + bithenge_scope_t *scope, bithenge_node_t *in, bithenge_node_t **out) +{ + struct_transform_t *self = transform_as_struct(base); + if (bithenge_node_type(in) != BITHENGE_NODE_BLOB) + return EINVAL; + return struct_transform_make_node(self, out, scope, + bithenge_node_as_blob(in), false); +} + +static int struct_transform_prefix_length(bithenge_transform_t *base, + bithenge_scope_t *scope, bithenge_blob_t *blob, aoff64_t *out) +{ + struct_transform_t *self = transform_as_struct(base); + bithenge_node_t *struct_node; + int rc = struct_transform_make_node(self, &struct_node, scope, blob, + true); + if (rc != EOK) + return rc; + + rc = seq_node_field_offset(node_as_seq(struct_node), out, + self->num_subtransforms); + bithenge_node_dec_ref(struct_node); + return rc; +} + +static int struct_transform_prefix_apply(bithenge_transform_t *base, + bithenge_scope_t *scope, bithenge_blob_t *blob, bithenge_node_t **out_node, + aoff64_t *out_size) +{ + struct_transform_t *self = transform_as_struct(base); + int rc = struct_transform_make_node(self, out_node, scope, blob, + true); + if (rc != EOK) + return rc; + + rc = seq_node_field_offset(node_as_seq(*out_node), out_size, + self->num_subtransforms); + if (rc != EOK) { + bithenge_node_dec_ref(*out_node); + return rc; + } + + return EOK; +} + +static void free_subtransforms(bithenge_named_transform_t *subtransforms) +{ + for (size_t i = 0; subtransforms[i].transform; i++) { + free((void *)subtransforms[i].name); + bithenge_transform_dec_ref(subtransforms[i].transform); + } + free(subtransforms); +} + +static void struct_transform_destroy(bithenge_transform_t *base) +{ + struct_transform_t *self = transform_as_struct(base); + free_subtransforms(self->subtransforms); + free(self); +} + +static bithenge_transform_ops_t struct_transform_ops = { + .apply = struct_transform_apply, + .prefix_length = struct_transform_prefix_length, + .prefix_apply = struct_transform_prefix_apply, + .destroy = struct_transform_destroy, +}; + +/** Create a struct transform. The transform will apply its subtransforms + * sequentially to a blob to create an internal node. Each result is either + * given a key from @a subtransforms or, if the name is NULL, the result's keys + * and values are merged into the struct transform's result. This function + * takes ownership of @a subtransforms and the names and references therein. + * @param[out] out Stores the created transform. + * @param subtransforms The subtransforms and field names. + * @return EOK on success or an error code from errno.h. */ +int bithenge_new_struct(bithenge_transform_t **out, + bithenge_named_transform_t *subtransforms) +{ + int rc; + struct_transform_t *self = malloc(sizeof(*self)); + if (!self) { + rc = ENOMEM; + goto error; + } + rc = bithenge_init_transform(struct_as_transform(self), + &struct_transform_ops, 0); + if (rc != EOK) + goto error; + self->subtransforms = subtransforms; + self->num_subtransforms = 0; + for (self->num_subtransforms = 0; + subtransforms[self->num_subtransforms].transform; + self->num_subtransforms++); + *out = struct_as_transform(self); + return EOK; +error: + free_subtransforms(subtransforms); + free(self); + return rc; +} + + + +/***************** bithenge_repeat_transform *****************/ + +typedef struct { + bithenge_transform_t base; + bithenge_expression_t *expr; + bithenge_transform_t *xform; +} repeat_transform_t; + +static inline bithenge_transform_t *repeat_as_transform( + repeat_transform_t *self) +{ + return &self->base; +} + +static inline repeat_transform_t *transform_as_repeat( + bithenge_transform_t *base) +{ + return (repeat_transform_t *)base; +} + +typedef struct { + seq_node_t base; + bool prefix; + bithenge_int_t count; + bithenge_transform_t *xform; +} repeat_node_t; + +static seq_node_t *repeat_as_seq(repeat_node_t *self) +{ + return &self->base; +} + +static repeat_node_t *seq_as_repeat(seq_node_t *base) +{ + return (repeat_node_t *)base; +} + +static bithenge_node_t *repeat_as_node(repeat_node_t *self) +{ + return seq_as_node(repeat_as_seq(self)); +} + +static repeat_node_t *node_as_repeat(bithenge_node_t *base) +{ + return seq_as_repeat(node_as_seq(base)); +} + +static int repeat_node_for_each(bithenge_node_t *base, + bithenge_for_each_func_t func, void *data) +{ + int rc = EOK; + repeat_node_t *self = node_as_repeat(base); + + for (bithenge_int_t i = 0; self->count == -1 || i < self->count; i++) { + bithenge_node_t *subxform_result; + rc = seq_node_subtransform(repeat_as_seq(self), + &subxform_result, i); + if ((rc == EINVAL || rc == ENOENT) && self->count == -1) { + self->count = i; + seq_node_set_num_xforms(repeat_as_seq(self), + self->count); + rc = EOK; + break; + } + if (rc != EOK) + return rc; + + bithenge_node_t *key_node; + rc = bithenge_new_integer_node(&key_node, i); + if (rc != EOK) { + bithenge_node_dec_ref(subxform_result); + return rc; + } + rc = func(key_node, subxform_result, data); + if (rc != EOK) + return rc; + } + + if (!self->prefix) { + bool complete; + rc = seq_node_complete(repeat_as_seq(self), &complete); + if (rc != EOK) + return rc; + if (!complete) + return EINVAL; + } + + return rc; +} + +static int repeat_node_get(bithenge_node_t *base, bithenge_node_t *key, + bithenge_node_t **out) +{ + repeat_node_t *self = node_as_repeat(base); + + if (bithenge_node_type(key) != BITHENGE_NODE_INTEGER) { + bithenge_node_dec_ref(key); + return ENOENT; + } + + bithenge_int_t index = bithenge_integer_node_value(key); + bithenge_node_dec_ref(key); + if (index < 0 || (self->count != -1 && index >= self->count)) + return ENOENT; + return seq_node_subtransform(repeat_as_seq(self), out, index); +} + +static void repeat_node_destroy(bithenge_node_t *base) +{ + repeat_node_t *self = node_as_repeat(base); + seq_node_destroy(repeat_as_seq(self)); + bithenge_transform_dec_ref(self->xform); + free(self); +} + +static const bithenge_internal_node_ops_t repeat_node_ops = { + .for_each = repeat_node_for_each, + .get = repeat_node_get, + .destroy = repeat_node_destroy, +}; + +static int repeat_node_get_transform(seq_node_t *base, + bithenge_transform_t **out, bithenge_int_t index) +{ + repeat_node_t *self = seq_as_repeat(base); + *out = self->xform; + bithenge_transform_inc_ref(*out); + return EOK; +} + +static const seq_node_ops_t repeat_node_seq_ops = { + .get_transform = repeat_node_get_transform, +}; + +static int repeat_transform_make_node(repeat_transform_t *self, + bithenge_node_t **out, bithenge_scope_t *scope, bithenge_blob_t *blob, + bool prefix) +{ + bithenge_int_t count = -1; + if (self->expr != NULL) { + bithenge_node_t *count_node; + int rc = bithenge_expression_evaluate(self->expr, scope, + &count_node); + if (rc != EOK) + return rc; + if (bithenge_node_type(count_node) != BITHENGE_NODE_INTEGER) { + bithenge_node_dec_ref(count_node); + return EINVAL; + } + count = bithenge_integer_node_value(count_node); + bithenge_node_dec_ref(count_node); + if (count < 0) + return EINVAL; + } + + repeat_node_t *node = malloc(sizeof(*node)); + if (!node) + return ENOMEM; + + int rc = bithenge_init_internal_node(repeat_as_node(node), + &repeat_node_ops); + if (rc != EOK) { + free(node); + return rc; + } + + rc = seq_node_init(repeat_as_seq(node), &repeat_node_seq_ops, scope, + blob, count, count == -1); + if (rc != EOK) { + free(node); + return rc; + } + + bithenge_transform_inc_ref(self->xform); + node->xform = self->xform; + node->count = count; + node->prefix = prefix; + *out = repeat_as_node(node); + return EOK; +} + +static int repeat_transform_apply(bithenge_transform_t *base, + bithenge_scope_t *scope, bithenge_node_t *in, bithenge_node_t **out) +{ + repeat_transform_t *self = transform_as_repeat(base); + if (bithenge_node_type(in) != BITHENGE_NODE_BLOB) + return EINVAL; + return repeat_transform_make_node(self, out, scope, + bithenge_node_as_blob(in), false); +} + +static int repeat_transform_prefix_apply(bithenge_transform_t *base, + bithenge_scope_t *scope, bithenge_blob_t *blob, bithenge_node_t **out_node, + aoff64_t *out_size) +{ + repeat_transform_t *self = transform_as_repeat(base); + int rc = repeat_transform_make_node(self, out_node, scope, blob, true); + if (rc != EOK) + return rc; + + bithenge_int_t count = node_as_repeat(*out_node)->count; + if (count != -1) { + rc = seq_node_field_offset(node_as_seq(*out_node), out_size, count); + if (rc != EOK) { + bithenge_node_dec_ref(*out_node); + return rc; + } + } else { + *out_size = 0; + for (count = 1; ; count++) { + aoff64_t size; + rc = seq_node_field_offset(node_as_seq(*out_node), + &size, count); + if (rc != EOK) + break; + *out_size = size; + } + } + return EOK; +} + +static void repeat_transform_destroy(bithenge_transform_t *base) +{ + repeat_transform_t *self = transform_as_repeat(base); + bithenge_transform_dec_ref(self->xform); + bithenge_expression_dec_ref(self->expr); + free(self); +} + +static const bithenge_transform_ops_t repeat_transform_ops = { + .apply = repeat_transform_apply, + .prefix_apply = repeat_transform_prefix_apply, + .destroy = repeat_transform_destroy, +}; + +/** Create a transform that applies its subtransform repeatedly. Takes a + * reference to @a xform and @a expr. + * @param[out] out Holds the new transform. + * @param xform The subtransform to apply repeatedly. + * @param expr Used to calculate the number of times @a xform will be applied. + * May be NULL, in which case @a xform will be applied indefinitely. + * @return EOK on success or an error code from errno.h. */ +int bithenge_repeat_transform(bithenge_transform_t **out, + bithenge_transform_t *xform, bithenge_expression_t *expr) +{ + int rc; + repeat_transform_t *self = malloc(sizeof(*self)); + if (!self) { + rc = ENOMEM; + goto error; + } + + rc = bithenge_init_transform(repeat_as_transform(self), + &repeat_transform_ops, 0); + if (rc != EOK) + goto error; + + self->expr = expr; + self->xform = xform; + *out = repeat_as_transform(self); + return EOK; + +error: + free(self); + bithenge_expression_dec_ref(expr); + bithenge_transform_dec_ref(xform); + return rc; +} + + + +/***************** bithenge_do_while_transform *****************/ + +typedef struct { + bithenge_transform_t base; + bithenge_expression_t *expr; + bithenge_transform_t *xform; +} do_while_transform_t; + +static inline bithenge_transform_t *do_while_as_transform( + do_while_transform_t *self) +{ + return &self->base; +} + +static inline do_while_transform_t *transform_as_do_while( + bithenge_transform_t *base) +{ + return (do_while_transform_t *)base; +} + +typedef struct { + seq_node_t base; + bool prefix; + bithenge_expression_t *expr; + bithenge_transform_t *xform; + bithenge_int_t count; +} do_while_node_t; + +static seq_node_t *do_while_as_seq(do_while_node_t *self) +{ + return &self->base; +} + +static do_while_node_t *seq_as_do_while(seq_node_t *base) +{ + return (do_while_node_t *)base; +} + +static bithenge_node_t *do_while_as_node(do_while_node_t *self) +{ + return seq_as_node(do_while_as_seq(self)); +} + +static do_while_node_t *node_as_do_while(bithenge_node_t *base) +{ + return seq_as_do_while(node_as_seq(base)); +} + +static int do_while_node_for_each(bithenge_node_t *base, + bithenge_for_each_func_t func, void *data) +{ + int rc = EOK; + do_while_node_t *self = node_as_do_while(base); + + for (bithenge_int_t i = 0; ; i++) { + bithenge_node_t *subxform_result; + rc = seq_node_subtransform(do_while_as_seq(self), + &subxform_result, i); + if (rc != EOK) + return rc; + + bithenge_node_t *key_node; + rc = bithenge_new_integer_node(&key_node, i); + if (rc != EOK) { + bithenge_node_dec_ref(subxform_result); + return rc; + } + bithenge_node_inc_ref(subxform_result); + rc = func(key_node, subxform_result, data); + if (rc != EOK) { + bithenge_node_dec_ref(subxform_result); + return rc; + } + + bithenge_scope_t *scope; + rc = bithenge_scope_new(&scope, + seq_node_scope(do_while_as_seq(self))); + if (rc != EOK) { + bithenge_node_dec_ref(subxform_result); + return rc; + } + bithenge_scope_set_current_node(scope, subxform_result); + bithenge_node_t *expr_result; + rc = bithenge_expression_evaluate(self->expr, scope, + &expr_result); + bithenge_scope_dec_ref(scope); + if (rc != EOK) + return rc; + if (bithenge_node_type(expr_result) != BITHENGE_NODE_BOOLEAN) { + bithenge_node_dec_ref(expr_result); + return EINVAL; + } + bool cond = bithenge_boolean_node_value(expr_result); + bithenge_node_dec_ref(expr_result); + if (!cond) { + self->count = i + 1; + seq_node_set_num_xforms(do_while_as_seq(self), + self->count); + break; + } + } + + if (!self->prefix) { + bool complete; + rc = seq_node_complete(do_while_as_seq(self), &complete); + if (rc != EOK) + return rc; + if (!complete) + return EINVAL; + } + + return rc; +} + +static void do_while_node_destroy(bithenge_node_t *base) +{ + do_while_node_t *self = node_as_do_while(base); + seq_node_destroy(do_while_as_seq(self)); + bithenge_expression_dec_ref(self->expr); + bithenge_transform_dec_ref(self->xform); + free(self); +} + +static const bithenge_internal_node_ops_t do_while_node_ops = { + .for_each = do_while_node_for_each, + .destroy = do_while_node_destroy, +}; + +static int do_while_node_get_transform(seq_node_t *base, + bithenge_transform_t **out, bithenge_int_t index) +{ + do_while_node_t *self = seq_as_do_while(base); + *out = self->xform; + bithenge_transform_inc_ref(*out); + return EOK; +} + +static const seq_node_ops_t do_while_node_seq_ops = { + .get_transform = do_while_node_get_transform, +}; + +static int do_while_transform_make_node(do_while_transform_t *self, + bithenge_node_t **out, bithenge_scope_t *scope, bithenge_blob_t *blob, + bool prefix) +{ + do_while_node_t *node = malloc(sizeof(*node)); + if (!node) + return ENOMEM; + + int rc = bithenge_init_internal_node(do_while_as_node(node), + &do_while_node_ops); + if (rc != EOK) { + free(node); + return rc; + } + + rc = seq_node_init(do_while_as_seq(node), &do_while_node_seq_ops, + scope, blob, -1, false); + if (rc != EOK) { + free(node); + return rc; + } + + bithenge_transform_inc_ref(self->xform); + node->xform = self->xform; + bithenge_expression_inc_ref(self->expr); + node->expr = self->expr; + node->prefix = prefix; + node->count = -1; + *out = do_while_as_node(node); + return EOK; +} + +static int do_while_transform_apply(bithenge_transform_t *base, + bithenge_scope_t *scope, bithenge_node_t *in, bithenge_node_t **out) +{ + do_while_transform_t *self = transform_as_do_while(base); + if (bithenge_node_type(in) != BITHENGE_NODE_BLOB) + return EINVAL; + return do_while_transform_make_node(self, out, scope, + bithenge_node_as_blob(in), false); +} + +static int for_each_noop(bithenge_node_t *key, bithenge_node_t *value, + void *data) +{ + bithenge_node_dec_ref(key); + bithenge_node_dec_ref(value); + return EOK; +} + +static int do_while_transform_prefix_apply(bithenge_transform_t *base, + bithenge_scope_t *scope, bithenge_blob_t *blob, bithenge_node_t **out_node, + aoff64_t *out_size) +{ + do_while_transform_t *self = transform_as_do_while(base); + int rc = do_while_transform_make_node(self, out_node, scope, blob, + true); + if (rc != EOK) + return rc; + + rc = bithenge_node_for_each(*out_node, for_each_noop, NULL); + if (rc != EOK) { + bithenge_node_dec_ref(*out_node); + return rc; + } + + rc = seq_node_field_offset(node_as_seq(*out_node), out_size, + node_as_do_while(*out_node)->count); + if (rc != EOK) { + bithenge_node_dec_ref(*out_node); + return rc; + } + + return EOK; +} + +static void do_while_transform_destroy(bithenge_transform_t *base) +{ + do_while_transform_t *self = transform_as_do_while(base); + bithenge_transform_dec_ref(self->xform); + bithenge_expression_dec_ref(self->expr); + free(self); +} + +static const bithenge_transform_ops_t do_while_transform_ops = { + .apply = do_while_transform_apply, + .prefix_apply = do_while_transform_prefix_apply, + .destroy = do_while_transform_destroy, +}; + +/** Create a transform that applies its subtransform while an expression on the + * result returns true. Takes a reference to @a xform and @a expr. + * @param[out] out Holds the new transform. + * @param xform The subtransform to apply repeatedly. + * @param expr Applied in the result of each application of @a xform to + * determine whether there will be more. + * @return EOK on success or an error code from errno.h. */ +int bithenge_do_while_transform(bithenge_transform_t **out, + bithenge_transform_t *xform, bithenge_expression_t *expr) +{ + int rc; + do_while_transform_t *self = malloc(sizeof(*self)); + if (!self) { + rc = ENOMEM; + goto error; + } + + rc = bithenge_init_transform(do_while_as_transform(self), + &do_while_transform_ops, 0); + if (rc != EOK) + goto error; + + self->expr = expr; + self->xform = xform; + *out = do_while_as_transform(self); + return EOK; + +error: + free(self); + bithenge_expression_dec_ref(expr); + bithenge_transform_dec_ref(xform); + return rc; +} + +/** @} + */ Index: uspace/app/bithenge/sequence.h =================================================================== --- uspace/app/bithenge/sequence.h (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/app/bithenge/sequence.h (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,52 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Sequence transforms. + */ + +#ifndef BITHENGE_SEQUENCE_H_ +#define BITHENGE_SEQUENCE_H_ + +#include "transform.h" + +int bithenge_new_struct(bithenge_transform_t **, + bithenge_named_transform_t *); +int bithenge_repeat_transform(bithenge_transform_t **, bithenge_transform_t *, + bithenge_expression_t *); +int bithenge_do_while_transform(bithenge_transform_t **, + bithenge_transform_t *, bithenge_expression_t *); + +#endif + +/** @} + */ Index: uspace/app/bithenge/source.c =================================================================== --- uspace/app/bithenge/source.c (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/app/bithenge/source.c (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,112 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Provide various external sources of data. + */ + +#include +#include +#include "blob.h" +#include "file.h" +#include "source.h" + +#ifdef __HELENOS__ +#include +#include "helenos/block.h" +#endif + +static inline int hex_digit(char digit) +{ + if ('0' <= digit && digit <= '9') + return digit - '0' + 0x0; + if ('a' <= digit && digit <= 'f') + return digit - 'a' + 0xa; + if ('A' <= digit && digit <= 'F') + return digit - 'A' + 0xA; + return -1; +} + +static int blob_from_hex(bithenge_node_t **out, const char *hex) +{ + size_t size = str_length(hex); + if (size % 2) + return EINVAL; + size /= 2; + char *buffer = malloc(size); + if (!buffer) + return ENOMEM; + for (size_t i = 0; i < size; i++) { + int upper = hex_digit(hex[2 * i + 0]); + int lower = hex_digit(hex[2 * i + 1]); + if (upper == -1 || lower == -1) { + free(buffer); + return EINVAL; + } + buffer[i] = upper << 4 | lower; + } + return bithenge_new_blob_from_buffer(out, buffer, size, true); +} + +/** Create a node from a source described with a string. For instance, + * "hex:55aa" will result in a blob node. If there is no colon in the string, + * it is assumed to be a filename. + * @param[out] out Stores the created node. + * @param source Specifies the node to be created. + * @return EOK on success or an error code from errno.h. */ +int bithenge_node_from_source(bithenge_node_t **out, const char *source) +{ + if (str_chr(source, ':')) { + if (!str_lcmp(source, "file:", 5)) { + // Example: file:/textdemo + return bithenge_new_file_blob(out, source + 5); +#ifdef __HELENOS__ + } else if (!str_lcmp(source, "block:", 6)) { + // Example: block:bd/initrd + service_id_t service_id; + int rc = loc_service_get_id(source + 6, &service_id, 0); + if (rc != EOK) + return rc; + return bithenge_new_block_blob(out, service_id); +#endif + } else if (!str_lcmp(source, "hex:", 4)) { + // Example: hex:04000000 + return blob_from_hex(out, source + 4); + } else { + return EINVAL; + } + } + return bithenge_new_file_blob(out, source); +} + +/** @} + */ Index: uspace/app/bithenge/source.h =================================================================== --- uspace/app/bithenge/source.h (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/app/bithenge/source.h (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,47 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Provide various external sources of data. + */ + +#ifndef BITHENGE_SOURCE_H_ +#define BITHENGE_SOURCE_H_ + +#include "tree.h" + +int bithenge_node_from_source(bithenge_node_t **, const char *); + +#endif + +/** @} + */ Index: uspace/app/bithenge/test.c =================================================================== --- uspace/app/bithenge/test.c (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/app/bithenge/test.c (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,133 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Simple program to test Bithenge. + */ + +#include +#include +#include +#include +#include "blob.h" +#include "source.h" +#include "print.h" +#include "script.h" +#include "transform.h" +#include "tree.h" + +int main(int argc, char *argv[]) +{ + int rc; + if (argc < 3) { + // {True: {}, -1351: "\"false\"", "true": False, 0: b"..."} + const char data[] = "'Twas brillig, and the slithy toves"; + bithenge_node_t *node; + bithenge_node_t *subnodes[8]; + bithenge_new_boolean_node(&subnodes[0], true); + bithenge_new_simple_internal_node(&subnodes[1], NULL, 0, false); + bithenge_new_integer_node(&subnodes[2], -1351); + bithenge_new_string_node(&subnodes[3], "\"false\"", false); + bithenge_new_string_node(&subnodes[4], "true", false); + bithenge_new_boolean_node(&subnodes[5], false); + bithenge_new_integer_node(&subnodes[6], 0); + bithenge_new_blob_from_data(&subnodes[7], data, sizeof(data)); + bithenge_new_simple_internal_node(&node, subnodes, 4, false); + bithenge_print_node(BITHENGE_PRINT_PYTHON, node); + printf("\n"); + bithenge_print_node(BITHENGE_PRINT_JSON, node); + printf("\n"); + bithenge_node_dec_ref(node); + } else { + bithenge_scope_t *scope = NULL; + bithenge_transform_t *transform = NULL; + bithenge_node_t *node = NULL, *node2 = NULL; + + rc = bithenge_scope_new(&scope, NULL); + if (rc != EOK) { + printf("Error creating scope: %s\n", str_error(rc)); + scope = NULL; + goto error; + } + + rc = bithenge_parse_script(argv[1], &transform); + if (rc != EOK) { + printf("Error parsing script: %s\n", str_error(rc)); + transform = NULL; + goto error; + } + + rc = bithenge_node_from_source(&node, argv[2]); + if (rc != EOK) { + printf("Error creating node from source: %s\n", str_error(rc)); + node = NULL; + goto error; + } + + rc = bithenge_transform_apply(transform, scope, node, &node2); + if (rc != EOK) { + printf("Error applying transform: %s\n", str_error(rc)); + node2 = NULL; + goto error; + } + + bithenge_node_dec_ref(node); + node = NULL; + bithenge_transform_dec_ref(transform); + transform = NULL; + + rc = bithenge_print_node(BITHENGE_PRINT_PYTHON, node2); + if (rc != EOK) { + printf("Error printing node: %s\n", str_error(rc)); + goto error; + } + bithenge_node_dec_ref(node2); + node2 = NULL; + bithenge_scope_dec_ref(scope); + scope = NULL; + printf("\n"); + + return 0; + +error: + bithenge_node_dec_ref(node); + bithenge_node_dec_ref(node2); + bithenge_transform_dec_ref(transform); + bithenge_scope_dec_ref(scope); + return 1; + } + + return 0; +} + +/** @} + */ Index: uspace/app/bithenge/transform.c =================================================================== --- uspace/app/bithenge/transform.c (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/app/bithenge/transform.c (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,951 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Transforms. + */ + +#include +#include +#include +#include "blob.h" +#include "transform.h" + +/** Initialize a new transform. + * @param[out] self Transform to initialize. + * @param[in] ops Operations provided by the transform. + * @param num_params The number of parameters required. If this is nonzero, the + * transform will get its own context with parameters, probably provided by a + * param_wrapper. If this is zero, the existing outer context will be used with + * whatever parameters it has, so they can be passed to any param_wrappers + * within. + * @return EOK or an error code from errno.h. */ +int bithenge_init_transform(bithenge_transform_t *self, + const bithenge_transform_ops_t *ops, int num_params) +{ + assert(ops); + assert(ops->apply || ops->prefix_apply); + assert(ops->destroy); + self->ops = ops; + self->refs = 1; + self->num_params = num_params; + return EOK; +} + +static void transform_indestructible(bithenge_transform_t *self) +{ + assert(false); +} + +/** Apply a transform. Takes ownership of nothing. + * @memberof bithenge_transform_t + * @param self The transform. + * @param scope The scope. + * @param in The input tree. + * @param[out] out Where the output tree will be stored. + * @return EOK on success or an error code from errno.h. */ +int bithenge_transform_apply(bithenge_transform_t *self, + bithenge_scope_t *scope, bithenge_node_t *in, bithenge_node_t **out) +{ + assert(self); + assert(self->ops); + if (self->ops->apply) + return self->ops->apply(self, scope, in, out); + + if (bithenge_node_type(in) != BITHENGE_NODE_BLOB) + return EINVAL; + aoff64_t self_size, whole_size; + int rc = bithenge_transform_prefix_apply(self, scope, + bithenge_node_as_blob(in), out, &self_size); + if (rc != EOK) + return rc; + rc = bithenge_blob_size(bithenge_node_as_blob(in), &whole_size); + if (rc == EOK && whole_size != self_size) + rc = EINVAL; + if (rc != EOK) { + bithenge_node_dec_ref(*out); + return rc; + } + return EOK; +} + +/** Find the length of the prefix of a blob this transform can use as input. In + * other words, figure out how many bytes this transform will use up. This + * method is optional and can return an error, but it must succeed for struct + * subtransforms. Takes ownership of nothing. + * @memberof bithenge_transform_t + * @param self The transform. + * @param scope The scope. + * @param blob The blob. + * @param[out] out Where the prefix length will be stored. + * @return EOK on success, ENOTSUP if not supported, or another error code from + * errno.h. */ +int bithenge_transform_prefix_length(bithenge_transform_t *self, + bithenge_scope_t *scope, bithenge_blob_t *blob, aoff64_t *out) +{ + assert(self); + assert(self->ops); + if (self->ops->prefix_length) + return self->ops->prefix_length(self, scope, blob, out); + if (!self->ops->prefix_apply) + return ENOTSUP; + + bithenge_node_t *node; + int rc = bithenge_transform_prefix_apply(self, scope, blob, &node, + out); + if (rc != EOK) + return rc; + bithenge_node_dec_ref(node); + return EOK; +} + +/** Apply this transform to a prefix of a blob. In other words, feed as much of + * the blob into this transform as possible. Takes ownership of nothing. + * @memberof bithenge_transform_t + * @param self The transform. + * @param scope The scope. + * @param blob The blob. + * @param[out] out_node Holds the result of applying this transform to the + * prefix. + * @param[out] out_size Holds the size of the prefix. + * @return EOK on success, ENOTSUP if not supported, or another error code from + * errno.h. */ +int bithenge_transform_prefix_apply(bithenge_transform_t *self, + bithenge_scope_t *scope, bithenge_blob_t *blob, bithenge_node_t **out_node, + aoff64_t *out_size) +{ + assert(self); + assert(self->ops); + if (self->ops->prefix_apply) + return self->ops->prefix_apply(self, scope, blob, out_node, + out_size); + if (!self->ops->prefix_length) + return ENOTSUP; + + int rc = bithenge_transform_prefix_length(self, scope, blob, out_size); + if (rc != EOK) + return rc; + bithenge_node_t *prefix_blob; + bithenge_blob_inc_ref(blob); + rc = bithenge_new_subblob(&prefix_blob, blob, 0, *out_size); + if (rc != EOK) + return rc; + rc = bithenge_transform_apply(self, scope, prefix_blob, out_node); + bithenge_node_dec_ref(prefix_blob); + return rc; +} + +/** Create a transform scope. It must be dereferenced with @a + * bithenge_scope_dec_ref after it is used. Takes ownership of nothing. + * @param[out] out Holds the new scope. + * @param outer The outer scope, or NULL. + * @return EOK on success or an error code from errno.h. */ +int bithenge_scope_new(bithenge_scope_t **out, bithenge_scope_t *outer) +{ + bithenge_scope_t *self = malloc(sizeof(*self)); + if (!self) + return ENOMEM; + self->refs = 1; + if (outer) + bithenge_scope_inc_ref(outer); + self->outer = outer; + self->barrier = false; + self->num_params = 0; + self->params = NULL; + self->current_node = NULL; + self->in_node = NULL; + *out = self; + return EOK; +} + +/** Dereference a transform scope. + * @param self The scope to dereference. */ +void bithenge_scope_dec_ref(bithenge_scope_t *self) +{ + if (!self) + return; + if (--self->refs) + return; + bithenge_node_dec_ref(self->current_node); + for (int i = 0; i < self->num_params; i++) + bithenge_node_dec_ref(self->params[i]); + bithenge_scope_dec_ref(self->outer); + free(self->params); + free(self); +} + +/** Get the outer scope of a scope, which may be NULL. + * @param self The scope to examine. + * @return The outer scope, which may be NULL. */ +bithenge_scope_t *bithenge_scope_outer(bithenge_scope_t *self) +{ + return self->outer; +} + +/** Get the current node being created, which may be NULL. + * @param scope The scope to get the current node from. + * @return The node being created, or NULL. */ +bithenge_node_t *bithenge_scope_get_current_node(bithenge_scope_t *scope) +{ + if (scope->current_node) + bithenge_node_inc_ref(scope->current_node); + return scope->current_node; +} + +/** Set the current node being created. Takes a reference to @a node. + * @param scope The scope to set the current node in. + * @param node The current node being created, or NULL. */ +void bithenge_scope_set_current_node(bithenge_scope_t *scope, + bithenge_node_t *node) +{ + bithenge_node_dec_ref(scope->current_node); + scope->current_node = node; +} + +/** Get the current input node, which may be NULL. + * @param scope The scope to get the current input node from. + * @return The input node, or NULL. */ +bithenge_node_t *bithenge_scope_in_node(bithenge_scope_t *scope) +{ + if (scope->in_node) + bithenge_node_inc_ref(scope->in_node); + return scope->in_node; +} + +/** Set the current input node. Takes a reference to @a node. + * @param scope The scope to set the input node in. + * @param node The input node, or NULL. */ +void bithenge_scope_set_in_node(bithenge_scope_t *scope, bithenge_node_t *node) +{ + bithenge_node_dec_ref(scope->in_node); + scope->in_node = node; +} + +/** Set a scope as a barrier. + * @param self The scope to change. */ +void bithenge_scope_set_barrier(bithenge_scope_t *self) +{ + self->barrier = true; +} + +/** Check whether a scope is a barrier, meaning that variable lookup stops at + * it. + * @param self The scope to check. + * @return Whether the scope is a barrier. */ +bool bithenge_scope_is_barrier(bithenge_scope_t *self) +{ + return self->barrier; +} + +/** Allocate parameters. The parameters must then be set with @a + * bithenge_scope_set_param. This must not be called on a scope that already + * has parameters. + * @param scope The scope in which to allocate parameters. + * @param num_params The number of parameters to allocate. + * @return EOK on success or an error code from errno.h. */ +int bithenge_scope_alloc_params(bithenge_scope_t *scope, int num_params) +{ + scope->params = malloc(sizeof(*scope->params) * num_params); + if (!scope->params) + return ENOMEM; + scope->num_params = num_params; + for (int i = 0; i < num_params; i++) + scope->params[i] = NULL; + return EOK; +} + +/** Set a parameter. Takes a reference to @a value. Note that range checking is + * not done in release builds. + * @param scope The scope in which to allocate parameters. + * @param i The index of the parameter to set. + * @param value The value to store in the parameter. + * @return EOK on success or an error code from errno.h. */ +int bithenge_scope_set_param( bithenge_scope_t *scope, int i, + bithenge_node_t *node) +{ + assert(scope); + assert(i >= 0 && i < scope->num_params); + scope->params[i] = node; + return EOK; +} + +/** Get a parameter. Note that range checking is not done in release builds. + * @param scope The scope to get the parameter from. + * @param i The index of the parameter to set. + * @param[out] out Stores a new reference to the parameter. + * @return EOK on success or an error code from errno.h. */ +int bithenge_scope_get_param(bithenge_scope_t *scope, int i, + bithenge_node_t **out) +{ + assert(scope); + if (scope->num_params) { + assert(i >= 0 && i < scope->num_params); + *out = scope->params[i]; + bithenge_node_inc_ref(*out); + return EOK; + } else { + return bithenge_scope_get_param(scope->outer, i, out); + } +} + +typedef struct { + bithenge_transform_t base; + bithenge_transform_t *transform; +} barrier_transform_t; + +static inline barrier_transform_t *transform_as_barrier( + bithenge_transform_t *base) +{ + return (barrier_transform_t *)base; +} + +static inline bithenge_transform_t *barrier_as_transform( + barrier_transform_t *self) +{ + return &self->base; +} + +static int barrier_transform_apply(bithenge_transform_t *base, + bithenge_scope_t *scope, bithenge_node_t *in, bithenge_node_t **out) +{ + barrier_transform_t *self = transform_as_barrier(base); + bithenge_scope_t *inner_scope; + int rc = bithenge_scope_new(&inner_scope, scope); + if (rc != EOK) + return rc; + bithenge_scope_set_barrier(inner_scope); + rc = bithenge_transform_apply(self->transform, scope, in, out); + bithenge_scope_dec_ref(inner_scope); + return rc; +} + +static int barrier_transform_prefix_length(bithenge_transform_t *base, + bithenge_scope_t *scope, bithenge_blob_t *in, aoff64_t *out) +{ + barrier_transform_t *self = transform_as_barrier(base); + bithenge_scope_t *inner_scope; + int rc = bithenge_scope_new(&inner_scope, scope); + if (rc != EOK) + return rc; + bithenge_scope_set_barrier(inner_scope); + rc = bithenge_transform_prefix_length(self->transform, scope, in, out); + bithenge_scope_dec_ref(inner_scope); + return rc; +} + +static int barrier_transform_prefix_apply(bithenge_transform_t *base, + bithenge_scope_t *scope, bithenge_blob_t *in, bithenge_node_t **out_node, + aoff64_t *out_length) +{ + barrier_transform_t *self = transform_as_barrier(base); + bithenge_scope_t *inner_scope; + int rc = bithenge_scope_new(&inner_scope, scope); + if (rc != EOK) + return rc; + bithenge_scope_set_barrier(inner_scope); + rc = bithenge_transform_prefix_apply(self->transform, scope, in, + out_node, out_length); + bithenge_scope_dec_ref(inner_scope); + return rc; +} + +static void barrier_transform_destroy(bithenge_transform_t *base) +{ + barrier_transform_t *self = transform_as_barrier(base); + bithenge_transform_dec_ref(self->transform); + free(self); +} + +static const bithenge_transform_ops_t barrier_transform_ops = { + .apply = barrier_transform_apply, + .prefix_length = barrier_transform_prefix_length, + .prefix_apply = barrier_transform_prefix_apply, + .destroy = barrier_transform_destroy, +}; + +/** Create a wrapper transform that creates a new scope. This ensures nothing + * from the outer scope is passed in, other than parameters. The wrapper may + * have a different value for num_params. Takes a reference to @a transform, + * which it will use for all operations. + * @param[out] out Holds the created transform. + * @param transform The transform to wrap. + * @param num_params The number of parameters to require, which may be 0. + * @return EOK on success or an error code from errno.h. */ +int bithenge_new_barrier_transform(bithenge_transform_t **out, + bithenge_transform_t *transform, int num_params) +{ + assert(transform); + assert(bithenge_transform_num_params(transform) == 0); + + int rc; + barrier_transform_t *self = malloc(sizeof(*self)); + if (!self) { + rc = ENOMEM; + goto error; + } + rc = bithenge_init_transform(barrier_as_transform(self), + &barrier_transform_ops, num_params); + if (rc != EOK) + goto error; + self->transform = transform; + *out = barrier_as_transform(self); + return EOK; +error: + bithenge_transform_dec_ref(transform); + free(self); + return rc; +} + + + +/***************** ascii *****************/ + +static int ascii_apply(bithenge_transform_t *self, bithenge_scope_t *scope, + bithenge_node_t *in, bithenge_node_t **out) +{ + int rc; + if (bithenge_node_type(in) != BITHENGE_NODE_BLOB) + return EINVAL; + bithenge_blob_t *blob = bithenge_node_as_blob(in); + aoff64_t size; + rc = bithenge_blob_size(blob, &size); + if (rc != EOK) + return rc; + + char *buffer = malloc(size + 1); + if (!buffer) + return ENOMEM; + aoff64_t size_read = size; + rc = bithenge_blob_read(blob, 0, buffer, &size_read); + if (rc != EOK) { + free(buffer); + return rc; + } + if (size_read != size) { + free(buffer); + return EINVAL; + } + buffer[size] = '\0'; + + /* TODO: what if the OS encoding is incompatible with ASCII? */ + return bithenge_new_string_node(out, buffer, true); +} + +static const bithenge_transform_ops_t ascii_ops = { + .apply = ascii_apply, + .destroy = transform_indestructible, +}; + +/** The ASCII text transform. */ +bithenge_transform_t bithenge_ascii_transform = { + &ascii_ops, 1, 0 +}; + + + +/***************** bit *****************/ + +static int bit_prefix_apply(bithenge_transform_t *self, + bithenge_scope_t *scope, bithenge_blob_t *blob, bithenge_node_t **out_node, + aoff64_t *out_size) +{ + char buffer; + *out_size = 1; + int rc = bithenge_blob_read_bits(blob, 0, &buffer, out_size, true); + if (rc != EOK) + return rc; + if (*out_size != 1) + return EINVAL; + return bithenge_new_boolean_node(out_node, (buffer & 1) != 0); +} + +static const bithenge_transform_ops_t bit_ops = { + .prefix_apply = bit_prefix_apply, + .destroy = transform_indestructible, +}; + +/** A transform that decodes a bit as a boolean. */ +bithenge_transform_t bithenge_bit_transform = { + &bit_ops, 1, 0 +}; + + + +/***************** bits_be, bits_le *****************/ + +typedef struct { + bithenge_blob_t base; + bithenge_blob_t *bytes; + bool little_endian; +} bits_xe_blob_t; + +static bits_xe_blob_t *blob_as_bits_xe(bithenge_blob_t *base) +{ + return (bits_xe_blob_t *)base; +} + +static bithenge_blob_t *bits_xe_as_blob(bits_xe_blob_t *self) +{ + return &self->base; +} + +static int bits_xe_size(bithenge_blob_t *base, aoff64_t *out) +{ + bits_xe_blob_t *self = blob_as_bits_xe(base); + int rc = bithenge_blob_size(self->bytes, out); + *out *= 8; + return rc; +} + +static uint8_t reverse_byte(uint8_t val) +{ + val = ((val & 0x0f) << 4) ^ ((val & 0xf0) >> 4); + val = ((val & 0x33) << 2) ^ ((val & 0xcc) >> 2); + val = ((val & 0x55) << 1) ^ ((val & 0xaa) >> 1); + return val; +} + +static int bits_xe_read_bits(bithenge_blob_t *base, aoff64_t offset, + char *buffer, aoff64_t *size, bool little_endian) +{ + bits_xe_blob_t *self = blob_as_bits_xe(base); + aoff64_t bytes_offset = offset / 8; + aoff64_t bit_offset = offset % 8; + aoff64_t output_num_bytes = (*size + 7) / 8; + aoff64_t bytes_size = (*size + bit_offset + 7) / 8; + bool separate_buffer = bit_offset != 0; + uint8_t *bytes_buffer; + if (separate_buffer) { + /* Allocate an extra byte, to make sure byte1 can be read. */ + bytes_buffer = malloc(bytes_size + 1); + if (!bytes_buffer) + return ENOMEM; + } else + bytes_buffer = (uint8_t *)buffer; + + int rc = bithenge_blob_read(self->bytes, bytes_offset, + (char *)bytes_buffer, &bytes_size); + if (rc != EOK) + goto end; + *size = min(*size, bytes_size * 8 - bit_offset); + + if (little_endian != self->little_endian) + for (aoff64_t i = 0; i < bytes_size; i++) + bytes_buffer[i] = reverse_byte(bytes_buffer[i]); + + if (bit_offset || separate_buffer) { + for (aoff64_t i = 0; i < output_num_bytes; i++) { + uint8_t byte0 = bytes_buffer[i]; + uint8_t byte1 = bytes_buffer[i + 1]; + buffer[i] = little_endian ? + (byte0 >> bit_offset) ^ (byte1 << (8 - bit_offset)) : + (byte0 << bit_offset) ^ (byte1 >> (8 - bit_offset)); + } + } + +end: + if (separate_buffer) + free(bytes_buffer); + return rc; +} + +static void bits_xe_destroy(bithenge_blob_t *base) +{ + bits_xe_blob_t *self = blob_as_bits_xe(base); + bithenge_blob_dec_ref(self->bytes); + free(self); +} + +static const bithenge_random_access_blob_ops_t bits_xe_blob_ops = { + .size = bits_xe_size, + .read_bits = bits_xe_read_bits, + .destroy = bits_xe_destroy, +}; + +static int bits_xe_apply(bithenge_transform_t *self, bithenge_scope_t *scope, + bithenge_node_t *in, bithenge_node_t **out) +{ + if (bithenge_node_type(in) != BITHENGE_NODE_BLOB) + return EINVAL; + bits_xe_blob_t *blob = malloc(sizeof(*blob)); + if (!blob) + return ENOMEM; + int rc = bithenge_init_random_access_blob(bits_xe_as_blob(blob), + &bits_xe_blob_ops); + if (rc != EOK) { + free(blob); + return rc; + } + bithenge_node_inc_ref(in); + blob->bytes = bithenge_node_as_blob(in); + blob->little_endian = (self == &bithenge_bits_le_transform); + *out = bithenge_blob_as_node(bits_xe_as_blob(blob)); + return EOK; +} + +static const bithenge_transform_ops_t bits_xe_ops = { + .apply = bits_xe_apply, + .destroy = transform_indestructible, +}; + +/** A transform that converts a byte blob to a bit blob, most-significant bit + * first. */ +bithenge_transform_t bithenge_bits_be_transform = { + &bits_xe_ops, 1, 0 +}; + +/** A transform that converts a byte blob to a bit blob, least-significant bit + * first. */ +bithenge_transform_t bithenge_bits_le_transform = { + &bits_xe_ops, 1, 0 +}; + + + +/***************** invalid *****************/ + +static int invalid_apply(bithenge_transform_t *self, bithenge_scope_t *scope, + bithenge_node_t *in, bithenge_node_t **out) +{ + return EINVAL; +} + +static const bithenge_transform_ops_t invalid_ops = { + .apply = invalid_apply, + .destroy = transform_indestructible, +}; + +/** A transform that always raises an error. */ +bithenge_transform_t bithenge_invalid_transform = { + &invalid_ops, 1, 0 +}; + + + +/***************** known_length *****************/ + +static int known_length_apply(bithenge_transform_t *self, + bithenge_scope_t *scope, bithenge_node_t *in, bithenge_node_t **out) +{ + bithenge_node_t *length_node; + int rc = bithenge_scope_get_param(scope, 0, &length_node); + if (rc != EOK) + return rc; + if (bithenge_node_type(length_node) != BITHENGE_NODE_INTEGER) { + bithenge_node_dec_ref(length_node); + return EINVAL; + } + bithenge_int_t length = bithenge_integer_node_value(length_node); + bithenge_node_dec_ref(length_node); + + if (bithenge_node_type(in) != BITHENGE_NODE_BLOB) + return EINVAL; + aoff64_t size; + rc = bithenge_blob_size(bithenge_node_as_blob(in), &size); + if (rc != EOK) + return rc; + if (length != (bithenge_int_t)size) + return EINVAL; + + bithenge_node_inc_ref(in); + *out = in; + return EOK; +} + +static int known_length_prefix_length(bithenge_transform_t *self, + bithenge_scope_t *scope, bithenge_blob_t *in, aoff64_t *out) +{ + bithenge_node_t *length_node; + int rc = bithenge_scope_get_param(scope, 0, &length_node); + if (rc != EOK) + return rc; + if (bithenge_node_type(length_node) != BITHENGE_NODE_INTEGER) { + bithenge_node_dec_ref(length_node); + return EINVAL; + } + bithenge_int_t length = bithenge_integer_node_value(length_node); + bithenge_node_dec_ref(length_node); + + *out = (aoff64_t)length; + return EOK; +} + +static const bithenge_transform_ops_t known_length_ops = { + .apply = known_length_apply, + .prefix_length = known_length_prefix_length, + .destroy = transform_indestructible, +}; + +/** Pass through a blob, but require its length to equal the first argument. */ +bithenge_transform_t bithenge_known_length_transform = { + &known_length_ops, 1, 1 +}; + +static int nonzero_boolean_apply(bithenge_transform_t *self, + bithenge_scope_t *scope, bithenge_node_t *in, bithenge_node_t **out) +{ + if (bithenge_node_type(in) != BITHENGE_NODE_INTEGER) + return EINVAL; + bool value = bithenge_integer_node_value(in) != 0; + return bithenge_new_boolean_node(out, value); +} + +static const bithenge_transform_ops_t nonzero_boolean_ops = { + .apply = nonzero_boolean_apply, + .destroy = transform_indestructible, +}; + +/** A transform that converts integers to booleans, true if nonzero. */ +bithenge_transform_t bithenge_nonzero_boolean_transform = { + &nonzero_boolean_ops, 1, 0 +}; + +static int prefix_length_1(bithenge_transform_t *self, bithenge_scope_t *scope, + bithenge_blob_t *blob, aoff64_t *out) +{ + *out = 1; + return EOK; +} + +static int prefix_length_2(bithenge_transform_t *self, bithenge_scope_t *scope, + bithenge_blob_t *blob, aoff64_t *out) +{ + *out = 2; + return EOK; +} + +static int prefix_length_4(bithenge_transform_t *self, bithenge_scope_t *scope, + bithenge_blob_t *blob, aoff64_t *out) +{ + *out = 4; + return EOK; +} + +static int prefix_length_8(bithenge_transform_t *self, bithenge_scope_t *scope, + bithenge_blob_t *blob, aoff64_t *out) +{ + *out = 8; + return EOK; +} + +#define MAKE_UINT_TRANSFORM(NAME, TYPE, ENDIAN, PREFIX_LENGTH_FUNC) \ + static int NAME##_apply(bithenge_transform_t *self, \ + bithenge_scope_t *scope, bithenge_node_t *in, \ + bithenge_node_t **out) \ + { \ + int rc; \ + if (bithenge_node_type(in) != BITHENGE_NODE_BLOB) \ + return EINVAL; \ + bithenge_blob_t *blob = bithenge_node_as_blob(in); \ + \ + /* Read too many bytes; success means the blob is too long. */ \ + TYPE val[2]; \ + aoff64_t size = sizeof(val[0]) + 1; \ + rc = bithenge_blob_read(blob, 0, (char *)val, &size); \ + if (rc != EOK) \ + return rc; \ + if (size != sizeof(val[0])) \ + return EINVAL; \ + \ + return bithenge_new_integer_node(out, ENDIAN(val[0])); \ + } \ + \ + static const bithenge_transform_ops_t NAME##_ops = { \ + .apply = NAME##_apply, \ + .prefix_length = PREFIX_LENGTH_FUNC, \ + .destroy = transform_indestructible, \ + }; \ + \ + bithenge_transform_t bithenge_##NAME##_transform = { \ + &NAME##_ops, 1, 0 \ + } + +MAKE_UINT_TRANSFORM(uint8 , uint8_t , , prefix_length_1); +MAKE_UINT_TRANSFORM(uint16le, uint16_t, uint16_t_le2host, prefix_length_2); +MAKE_UINT_TRANSFORM(uint16be, uint16_t, uint16_t_be2host, prefix_length_2); +MAKE_UINT_TRANSFORM(uint32le, uint32_t, uint32_t_le2host, prefix_length_4); +MAKE_UINT_TRANSFORM(uint32be, uint32_t, uint32_t_be2host, prefix_length_4); +MAKE_UINT_TRANSFORM(uint64le, uint64_t, uint32_t_le2host, prefix_length_8); +MAKE_UINT_TRANSFORM(uint64be, uint64_t, uint32_t_be2host, prefix_length_8); + + + +/***************** uint_be, uint_le *****************/ + +static int uint_xe_prefix_apply(bithenge_transform_t *self, + bithenge_scope_t *scope, bithenge_blob_t *blob, bithenge_node_t **out_node, + aoff64_t *out_size) +{ + bool little_endian = (self == &bithenge_uint_le_transform); + bithenge_node_t *num_bits_node; + int rc = bithenge_scope_get_param(scope, 0, &num_bits_node); + if (rc != EOK) + return rc; + if (bithenge_node_type(num_bits_node) != BITHENGE_NODE_INTEGER) { + bithenge_node_dec_ref(num_bits_node); + return EINVAL; + } + bithenge_int_t num_bits = bithenge_integer_node_value(num_bits_node); + bithenge_node_dec_ref(num_bits_node); + if (num_bits < 0) + return EINVAL; + if ((size_t)num_bits > sizeof(bithenge_int_t) * 8 - 1) + return EINVAL; + + *out_size = num_bits; + uint8_t buffer[sizeof(bithenge_int_t)]; + rc = bithenge_blob_read_bits(blob, 0, (char *)buffer, out_size, + little_endian); + if (rc != EOK) + return rc; + if (*out_size != (aoff64_t)num_bits) + return EINVAL; + + bithenge_int_t result = 0; + bithenge_int_t num_easy_bytes = num_bits / 8; + if (little_endian) { + for (bithenge_int_t i = 0; i < num_easy_bytes; i++) + result += buffer[i] << 8 * i; + if (num_bits % 8) + result += (buffer[num_easy_bytes] & + ((1 << num_bits % 8) - 1)) << 8 * num_easy_bytes; + } else { + for (bithenge_int_t i = 0; i < num_easy_bytes; i++) + result += buffer[i] << (num_bits - 8 * (i + 1)); + if (num_bits % 8) + result += buffer[num_easy_bytes] >> (8 - num_bits % 8); + } + + return bithenge_new_integer_node(out_node, result); +} + +static const bithenge_transform_ops_t uint_xe_ops = { + .prefix_apply = uint_xe_prefix_apply, + .destroy = transform_indestructible, +}; + +/** A transform that reads an unsigned integer from an arbitrary number of + * bits, most-significant bit first. */ +bithenge_transform_t bithenge_uint_be_transform = { + &uint_xe_ops, 1, 1 +}; + +/** A transform that reads an unsigned integer from an arbitrary number of + * bits, least-significant bit first. */ +bithenge_transform_t bithenge_uint_le_transform = { + &uint_xe_ops, 1, 1 +}; + + + +/***************** zero_terminated *****************/ + +static int zero_terminated_apply(bithenge_transform_t *self, + bithenge_scope_t *scope, bithenge_node_t *in, bithenge_node_t **out) +{ + int rc; + if (bithenge_node_type(in) != BITHENGE_NODE_BLOB) + return EINVAL; + bithenge_blob_t *blob = bithenge_node_as_blob(in); + aoff64_t size; + rc = bithenge_blob_size(blob, &size); + if (rc != EOK) + return rc; + if (size < 1) + return EINVAL; + char ch; + aoff64_t size_read = 1; + rc = bithenge_blob_read(blob, size - 1, &ch, &size_read); + if (rc != EOK) + return rc; + if (size_read != 1 || ch != '\0') + return EINVAL; + bithenge_blob_inc_ref(blob); + return bithenge_new_subblob(out, blob, 0, size - 1); +} + +static int zero_terminated_prefix_length(bithenge_transform_t *self, + bithenge_scope_t *scope, bithenge_blob_t *blob, aoff64_t *out) +{ + int rc; + char buffer[4096]; + aoff64_t offset = 0, size_read = sizeof(buffer); + do { + rc = bithenge_blob_read(blob, offset, buffer, &size_read); + if (rc != EOK) + return rc; + char *found = memchr(buffer, '\0', size_read); + if (found) { + *out = found - buffer + offset + 1; + return EOK; + } + offset += size_read; + } while (size_read == sizeof(buffer)); + return EINVAL; +} + +static const bithenge_transform_ops_t zero_terminated_ops = { + .apply = zero_terminated_apply, + .prefix_length = zero_terminated_prefix_length, + .destroy = transform_indestructible, +}; + +/** The zero-terminated data transform. */ +bithenge_transform_t bithenge_zero_terminated_transform = { + &zero_terminated_ops, 1, 0 +}; + +static bithenge_named_transform_t primitive_transforms[] = { + {"ascii", &bithenge_ascii_transform}, + {"bit", &bithenge_bit_transform}, + {"bits_be", &bithenge_bits_be_transform}, + {"bits_le", &bithenge_bits_le_transform}, + {"known_length", &bithenge_known_length_transform}, + {"nonzero_boolean", &bithenge_nonzero_boolean_transform}, + {"uint8", &bithenge_uint8_transform}, + {"uint16be", &bithenge_uint16be_transform}, + {"uint16le", &bithenge_uint16le_transform}, + {"uint32be", &bithenge_uint32be_transform}, + {"uint32le", &bithenge_uint32le_transform}, + {"uint64be", &bithenge_uint64be_transform}, + {"uint64le", &bithenge_uint64le_transform}, + {"uint_be", &bithenge_uint_be_transform}, + {"uint_le", &bithenge_uint_le_transform}, + {"zero_terminated", &bithenge_zero_terminated_transform}, + {NULL, NULL} +}; + +/** An array of named built-in transforms. */ +bithenge_named_transform_t *bithenge_primitive_transforms = primitive_transforms; + +/** @} + */ Index: uspace/app/bithenge/transform.h =================================================================== --- uspace/app/bithenge/transform.h (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/app/bithenge/transform.h (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,167 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Transforms. + */ + +#ifndef BITHENGE_TRANSFORM_H_ +#define BITHENGE_TRANSFORM_H_ + +#include "blob.h" +#include "tree.h" + +/** A transform that creates a new tree from an old tree. */ +typedef struct { + /** @privatesection */ + const struct bithenge_transform_ops *ops; + unsigned int refs; + int num_params; +} bithenge_transform_t; + +/** Context and parameters used when applying transforms. */ +typedef struct bithenge_scope { + /** @privatesection */ + unsigned int refs; + struct bithenge_scope *outer; + bool barrier; + int num_params; + bithenge_node_t **params; + bithenge_node_t *current_node; + bithenge_node_t *in_node; +} bithenge_scope_t; + +static inline void bithenge_scope_inc_ref(bithenge_scope_t *self) { + self->refs++; +} + +/** Operations that may be provided by a transform. All transforms must provide + * apply and/or prefix_apply. To be used in struct transforms and repeat + * transforms, transforms must provide prefix_length and/or prefix_apply. */ +typedef struct bithenge_transform_ops { + /** @copydoc bithenge_transform_t::bithenge_transform_apply */ + int (*apply)(bithenge_transform_t *self, bithenge_scope_t *scope, + bithenge_node_t *in, bithenge_node_t **out); + /** @copydoc bithenge_transform_t::bithenge_transform_prefix_length */ + int (*prefix_length)(bithenge_transform_t *self, + bithenge_scope_t *scope, bithenge_blob_t *blob, aoff64_t *out); + /** @copydoc bithenge_transform_t::bithenge_transform_prefix_apply */ + int (*prefix_apply)(bithenge_transform_t *self, + bithenge_scope_t *scope, bithenge_blob_t *blob, + bithenge_node_t **out_node, aoff64_t *out_size); + /** Destroy the transform. + * @param self The transform. */ + void (*destroy)(bithenge_transform_t *self); +} bithenge_transform_ops_t; + +/** Get the number of parameters required by a transform. This number is used + * by the parser and param-wrapper. Takes ownership of nothing. + * @param self The transform. + * @return The number of parameters required. */ +static inline int bithenge_transform_num_params(bithenge_transform_t *self) +{ + assert(self); + return self->num_params; +} + +/** Increment a transform's reference count. + * @param self The transform to reference. */ +static inline void bithenge_transform_inc_ref(bithenge_transform_t *self) +{ + assert(self); + self->refs++; +} + +/** Decrement a transform's reference count and free it if appropriate. + * @param self The transform to dereference, or NULL. */ +static inline void bithenge_transform_dec_ref(bithenge_transform_t *self) +{ + if (!self) + return; + assert(self->ops); + if (--self->refs == 0) + self->ops->destroy(self); +} + +/** A transform with a name. */ +typedef struct { + const char *name; + bithenge_transform_t *transform; +} bithenge_named_transform_t; + +extern bithenge_transform_t bithenge_ascii_transform; +extern bithenge_transform_t bithenge_bit_transform; +extern bithenge_transform_t bithenge_bits_be_transform; +extern bithenge_transform_t bithenge_bits_le_transform; +extern bithenge_transform_t bithenge_invalid_transform; +extern bithenge_transform_t bithenge_known_length_transform; +extern bithenge_transform_t bithenge_nonzero_boolean_transform; +extern bithenge_transform_t bithenge_uint8_transform; +extern bithenge_transform_t bithenge_uint16le_transform; +extern bithenge_transform_t bithenge_uint16be_transform; +extern bithenge_transform_t bithenge_uint32le_transform; +extern bithenge_transform_t bithenge_uint32be_transform; +extern bithenge_transform_t bithenge_uint64le_transform; +extern bithenge_transform_t bithenge_uint64be_transform; +extern bithenge_transform_t bithenge_uint_le_transform; +extern bithenge_transform_t bithenge_uint_be_transform; +extern bithenge_transform_t bithenge_zero_terminated_transform; +extern bithenge_named_transform_t *bithenge_primitive_transforms; + +int bithenge_init_transform(bithenge_transform_t *, + const bithenge_transform_ops_t *, int); +int bithenge_transform_apply(bithenge_transform_t *, bithenge_scope_t *, + bithenge_node_t *, bithenge_node_t **); +int bithenge_transform_prefix_length(bithenge_transform_t *, + bithenge_scope_t *, bithenge_blob_t *, aoff64_t *); +int bithenge_transform_prefix_apply(bithenge_transform_t *, bithenge_scope_t *, + bithenge_blob_t *, bithenge_node_t **, aoff64_t *); +int bithenge_new_barrier_transform(bithenge_transform_t **, + bithenge_transform_t *, int); + +int bithenge_scope_new(bithenge_scope_t **, bithenge_scope_t *); +void bithenge_scope_dec_ref(bithenge_scope_t *); +bithenge_scope_t *bithenge_scope_outer(bithenge_scope_t *); +bithenge_node_t *bithenge_scope_get_current_node(bithenge_scope_t *); +void bithenge_scope_set_current_node(bithenge_scope_t *, bithenge_node_t *); +bithenge_node_t *bithenge_scope_in_node(bithenge_scope_t *); +void bithenge_scope_set_in_node(bithenge_scope_t *, bithenge_node_t *); +void bithenge_scope_set_barrier(bithenge_scope_t *); +bool bithenge_scope_is_barrier(bithenge_scope_t *); +int bithenge_scope_alloc_params(bithenge_scope_t *, int); +int bithenge_scope_set_param(bithenge_scope_t *, int, bithenge_node_t *); +int bithenge_scope_get_param(bithenge_scope_t *, int, bithenge_node_t **); + +#endif + +/** @} + */ Index: uspace/app/bithenge/tree.c =================================================================== --- uspace/app/bithenge/tree.c (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/app/bithenge/tree.c (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,354 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Trees and nodes. + */ + +#include +#include +#include "blob.h" +#include "os.h" +#include "tree.h" + +static void blob_destroy(bithenge_node_t *base) +{ + bithenge_blob_t *self = bithenge_node_as_blob(base); + assert(self->base.blob_ops); + self->base.blob_ops->destroy(self); +} + +static void node_destroy(bithenge_node_t *self) +{ + switch (bithenge_node_type(self)) { + case BITHENGE_NODE_BLOB: + blob_destroy(self); + return; + case BITHENGE_NODE_STRING: + if (self->string_value.needs_free) + free((void *)self->string_value.ptr); + break; + case BITHENGE_NODE_INTERNAL: + self->internal_ops->destroy(self); + return; + case BITHENGE_NODE_BOOLEAN: + return; /* The boolean nodes are allocated statically below. */ + case BITHENGE_NODE_INTEGER: /* pass-through */ + break; + } + free(self); +} + +/** Decrement a node's reference count and free it if appropriate. + * @memberof bithenge_node_t + * @param node The node to dereference, or NULL. */ +void bithenge_node_dec_ref(bithenge_node_t *node) +{ + if (!node) + return; + if (--node->refs == 0) + node_destroy(node); +} + +typedef struct { + bithenge_node_t *key; + bithenge_node_t **out; +} get_for_each_data_t; + +static int get_for_each_func(bithenge_node_t *key, bithenge_node_t *value, + void *raw_data) +{ + get_for_each_data_t *data = (get_for_each_data_t *)raw_data; + bool equal = bithenge_node_equal(key, data->key); + bithenge_node_dec_ref(key); + if (equal) { + *data->out = value; + return EEXIST; + } + bithenge_node_dec_ref(value); + return EOK; +} + +/** Get a child of a node. Takes ownership of the key. If the node does not + * provide this function, for_each will be used as an alternative, which may be + * very slow. + * @memberof bithenge_node_t + * @param self The internal node to find a child of. + * @param key The key to search for. + * @param[out] out Holds the found node. + * @return EOK on success, ENOENT if not found, or another error code from + * errno.h. */ +int bithenge_node_get(bithenge_node_t *self, bithenge_node_t *key, + bithenge_node_t **out) +{ + assert(self->type == BITHENGE_NODE_INTERNAL); + if (self->internal_ops->get) + return self->internal_ops->get(self, key, out); + *out = NULL; + get_for_each_data_t data = {key, out}; + int rc = bithenge_node_for_each(self, get_for_each_func, &data); + bithenge_node_dec_ref(key); + if (rc == EEXIST && *out) + return EOK; + if (rc == EOK) + rc = ENOENT; + bithenge_node_dec_ref(*out); + return rc; +} + +/** Initialize an internal node. + * @memberof bithenge_node_t + * @param[out] self The node. + * @param[in] ops The operations provided. + * @return EOK on success or an error code from errno.h. */ +int bithenge_init_internal_node(bithenge_node_t *self, + const bithenge_internal_node_ops_t *ops) +{ + self->type = BITHENGE_NODE_INTERNAL; + self->refs = 1; + self->internal_ops = ops; + return EOK; +} + +static void internal_node_indestructible(bithenge_node_t *self) +{ + assert(false); +} + +static int empty_internal_node_for_each(bithenge_node_t *base, + bithenge_for_each_func_t func, void *data) +{ + return EOK; +} + +static int empty_internal_node_get(bithenge_node_t *self, bithenge_node_t *key, + bithenge_node_t **out) +{ + return ENOENT; +} + +static const bithenge_internal_node_ops_t empty_internal_node_ops = { + .for_each = empty_internal_node_for_each, + .get = empty_internal_node_get, + .destroy = internal_node_indestructible, +}; + +static bithenge_node_t empty_internal_node = { + BITHENGE_NODE_INTERNAL, + 1, + { .internal_ops = &empty_internal_node_ops }, +}; + +/** Create an empty internal node. + * @param[out] out Holds the created node. + * @return EOK on success or an error code from errno.h. */ +int bithenge_new_empty_internal_node(bithenge_node_t **out) +{ + bithenge_node_inc_ref(&empty_internal_node); + *out = &empty_internal_node; + return EOK; +} + +typedef struct +{ + bithenge_node_t base; + bithenge_node_t **nodes; + bithenge_int_t len; + bool needs_free; +} simple_internal_node_t; + +static simple_internal_node_t *node_as_simple(bithenge_node_t *node) +{ + return (simple_internal_node_t *)node; +} + +static bithenge_node_t *simple_as_node(simple_internal_node_t *node) +{ + return &node->base; +} + +static int simple_internal_node_for_each(bithenge_node_t *base, + bithenge_for_each_func_t func, void *data) +{ + int rc; + simple_internal_node_t *self = node_as_simple(base); + for (bithenge_int_t i = 0; i < self->len; i++) { + bithenge_node_inc_ref(self->nodes[2*i+0]); + bithenge_node_inc_ref(self->nodes[2*i+1]); + rc = func(self->nodes[2*i+0], self->nodes[2*i+1], data); + if (rc != EOK) + return rc; + } + return EOK; +} + +static void simple_internal_node_destroy(bithenge_node_t *base) +{ + simple_internal_node_t *self = node_as_simple(base); + for (bithenge_int_t i = 0; i < 2 * self->len; i++) + bithenge_node_dec_ref(self->nodes[i]); + if (self->needs_free) + free(self->nodes); + free(self); +} + +static bithenge_internal_node_ops_t simple_internal_node_ops = { + .for_each = simple_internal_node_for_each, + .destroy = simple_internal_node_destroy, +}; + +/** Create an internal node from a set of keys and values. This function takes + * ownership of a reference to the key and value nodes, and optionally the + * array @a nodes. + * @memberof bithenge_node_t + * @param[out] out Stores the created internal node. + * @param nodes The array of key-value pairs. Keys are stored at even indices + * and values are stored at odd indices. + * @param len The number of key-value pairs in the node array. + * @param needs_free If true, when the internal node is destroyed it will free + * the nodes array rather than just dereferencing each node inside it. + * @return EOK on success or an error code from errno.h. */ +int bithenge_new_simple_internal_node(bithenge_node_t **out, + bithenge_node_t **nodes, bithenge_int_t len, bool needs_free) +{ + int rc; + assert(out); + simple_internal_node_t *self = malloc(sizeof(*self)); + if (!self) { + rc = ENOMEM; + goto error; + } + rc = bithenge_init_internal_node(simple_as_node(self), + &simple_internal_node_ops); + if (rc != EOK) + goto error; + self->nodes = nodes; + self->len = len; + self->needs_free = needs_free; + *out = simple_as_node(self); + return EOK; +error: + for (bithenge_int_t i = 0; i < 2 * len; i++) + bithenge_node_dec_ref(nodes[i]); + if (needs_free) + free(nodes); + free(self); + return rc; +} + +static bithenge_node_t false_node = { BITHENGE_NODE_BOOLEAN, 1, .boolean_value = false }; +static bithenge_node_t true_node = { BITHENGE_NODE_BOOLEAN, 1, .boolean_value = true }; + +/** Create a boolean node. + * @memberof bithenge_node_t + * @param[out] out Stores the created boolean node. + * @param value The value for the node to hold. + * @return EOK on success or an error code from errno.h. */ +int bithenge_new_boolean_node(bithenge_node_t **out, bool value) +{ + assert(out); + *out = value ? &true_node : &false_node; + (*out)->refs++; + return EOK; +} + +/** Create an integer node. + * @memberof bithenge_node_t + * @param[out] out Stores the created integer node. + * @param value The value for the node to hold. + * @return EOK on success or an error code from errno.h. */ +int bithenge_new_integer_node(bithenge_node_t **out, bithenge_int_t value) +{ + assert(out); + bithenge_node_t *self = malloc(sizeof(*self)); + if (!self) + return ENOMEM; + self->type = BITHENGE_NODE_INTEGER; + self->refs = 1; + self->integer_value = value; + *out = self; + return EOK; +} + +/** Create a string node. + * @memberof bithenge_node_t + * @param[out] out Stores the created string node. On error, this is unchanged. + * @param value The value for the node to hold. + * @param needs_free Whether the string should be freed when the node is + * destroyed. + * @return EOK on success or an error code from errno.h. */ +int bithenge_new_string_node(bithenge_node_t **out, const char *value, bool needs_free) +{ + assert(out); + bithenge_node_t *self = malloc(sizeof(*self)); + if (!self) { + if (needs_free) + free((void *)value); + return ENOMEM; + } + self->type = BITHENGE_NODE_STRING; + self->refs = 1; + self->string_value.ptr = value; + self->string_value.needs_free = needs_free; + *out = self; + return EOK; +} + +/** Check whether the contents of two nodes are equal. Does not yet work for + * internal nodes. Takes ownership of nothing. + * @memberof bithenge_node_t + * @param a, b Nodes to compare. + * @return Whether the nodes are equal. If an error occurs, returns false. + * @todo Add support for internal nodes. + */ +bool bithenge_node_equal(bithenge_node_t *a, bithenge_node_t *b) +{ + if (a->type != b->type) + return false; + switch (a->type) { + case BITHENGE_NODE_INTERNAL: + return false; + case BITHENGE_NODE_BOOLEAN: + return a->boolean_value == b->boolean_value; + case BITHENGE_NODE_INTEGER: + return a->integer_value == b->integer_value; + case BITHENGE_NODE_STRING: + return !str_cmp(a->string_value.ptr, b->string_value.ptr); + case BITHENGE_NODE_BLOB: + return bithenge_blob_equal(bithenge_node_as_blob(a), + bithenge_node_as_blob(b)); + } + return false; +} + +/** @} + */ Index: uspace/app/bithenge/tree.h =================================================================== --- uspace/app/bithenge/tree.h (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/app/bithenge/tree.h (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,174 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Trees and nodes. + */ + +#ifndef BITHENGE_TREE_H_ +#define BITHENGE_TREE_H_ + +#include +#include +#include "os.h" + +/** Indicates the type of a tree node. */ +typedef enum { + /** An internal node with labelled edges to other nodes. */ + BITHENGE_NODE_INTERNAL = 1, + /** A leaf node holding a boolean value. */ + BITHENGE_NODE_BOOLEAN, + /** A leaf node holding an integer. */ + BITHENGE_NODE_INTEGER, + /** A leaf node holding a string. */ + BITHENGE_NODE_STRING, + /** A leaf node holding a binary blob. */ + BITHENGE_NODE_BLOB, +} bithenge_node_type_t; + +typedef struct bithenge_node_t { + /** @privatesection */ + bithenge_node_type_t type; + unsigned int refs; + union { + const struct bithenge_internal_node_ops_t *internal_ops; + bool boolean_value; + bithenge_int_t integer_value; + struct { + const char *ptr; + bool needs_free; + } string_value; + const struct bithenge_random_access_blob_ops_t *blob_ops; + }; +} bithenge_node_t; + +/** A callback function used to iterate over a node's children. It takes + * ownership of a reference to both the key and the value. + * @memberof bithenge_node_t + * @param key The key. + * @param value The value. + * @param data Data provided to @a bithenge_node_t::bithenge_node_for_each. + * @return EOK on success or an error code from errno.h. */ +typedef int (*bithenge_for_each_func_t)(bithenge_node_t *key, bithenge_node_t *value, void *data); + +/** Operations providing access to an internal node. */ +typedef struct bithenge_internal_node_ops_t { + /** @copydoc bithenge_node_t::bithenge_node_for_each */ + int (*for_each)(bithenge_node_t *self, bithenge_for_each_func_t func, void *data); + /** @copydoc bithenge_node_t::bithenge_node_get */ + int (*get)(bithenge_node_t *self, bithenge_node_t *key, + bithenge_node_t **out); + /** Destroys the internal node. + * @param self The node to destroy. */ + void (*destroy)(bithenge_node_t *self); +} bithenge_internal_node_ops_t; + +/** Find the type of a node. + * @memberof bithenge_node_t + * @param node The node. + * @return The type of the node. */ +static inline bithenge_node_type_t bithenge_node_type(const bithenge_node_t *node) +{ + return node->type; +} + +/** Increment a node's reference count. + * @memberof bithenge_node_t + * @param node The node to reference. */ +static inline void bithenge_node_inc_ref(bithenge_node_t *node) +{ + assert(node); + node->refs++; +} + +void bithenge_node_dec_ref(bithenge_node_t *node); + +/** Iterate over a node's children. + * @memberof bithenge_node_t + * @param self The internal node to iterate over. + * @param func The callback function. + * @param data Data to provide to the callback function. + * @return EOK on success or an error code from errno.h. */ +static inline int bithenge_node_for_each(bithenge_node_t *self, + bithenge_for_each_func_t func, void *data) +{ + assert(self->type == BITHENGE_NODE_INTERNAL); + return self->internal_ops->for_each(self, func, data); +} + +int bithenge_node_get(bithenge_node_t *, bithenge_node_t *, + bithenge_node_t **); + +/** Get the value of a boolean node. + * @memberof bithenge_node_t + * @param self The boolean node. + * @return The node's value. */ +static inline bool bithenge_boolean_node_value(bithenge_node_t *self) +{ + assert(self->type == BITHENGE_NODE_BOOLEAN); + return self->boolean_value; +} + +/** Get the value of an integer node. + * @memberof bithenge_node_t + * @param self The integer node. + * @return The node's value. */ +static inline bithenge_int_t bithenge_integer_node_value(bithenge_node_t *self) +{ + assert(self->type == BITHENGE_NODE_INTEGER); + return self->integer_value; +} + +/** Get the value of an string node. + * @memberof bithenge_node_t + * @param self The string node. + * @return The node's value. */ +static inline const char *bithenge_string_node_value(bithenge_node_t *self) +{ + assert(self->type == BITHENGE_NODE_STRING); + return self->string_value.ptr; +} + +int bithenge_init_internal_node(bithenge_node_t *, + const bithenge_internal_node_ops_t *); +int bithenge_new_empty_internal_node(bithenge_node_t **); +int bithenge_new_simple_internal_node(bithenge_node_t **, bithenge_node_t **, + bithenge_int_t, bool needs_free); +int bithenge_new_boolean_node(bithenge_node_t **, bool); +int bithenge_new_integer_node(bithenge_node_t **, bithenge_int_t); +int bithenge_new_string_node(bithenge_node_t **, const char *, bool); +bool bithenge_node_equal(bithenge_node_t *, bithenge_node_t *); + +#endif + +/** @} + */ Index: uspace/dist/src/bithenge/test-bits.bh =================================================================== --- uspace/dist/src/bithenge/test-bits.bh (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/dist/src/bithenge/test-bits.bh (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,25 @@ +transform main = struct { + .bits_le <- repeat(8) { bit } <- bits_le <- known_length(1); + .bits_be <- repeat(8) { bit } <- bits_be <- known_length(1); + <- struct { + .le0 <- uint_le(0); + .le1 <- uint_le(1); + .le2 <- uint_le(2); + .le3 <- uint_le(3); + .le4 <- uint_le(4); + .le5 <- uint_le(5); + .le6 <- uint_le(6); + .le7 <- uint_le(7); + .le8 <- uint_le(8); + + .be8 <- uint_be(8); + .be7 <- uint_be(7); + .be6 <- uint_be(6); + .be5 <- uint_be(5); + .be4 <- uint_be(4); + .be3 <- uint_be(3); + .be2 <- uint_be(2); + .be1 <- uint_be(1); + .be0 <- uint_be(0); + } <- bits_be <- known_length(9); +}; Index: uspace/dist/src/bithenge/test-bits.dat =================================================================== --- uspace/dist/src/bithenge/test-bits.dat (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/dist/src/bithenge/test-bits.dat (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,1 @@ +ee¤BB% Index: uspace/dist/src/bithenge/test-repeat.bh =================================================================== --- uspace/dist/src/bithenge/test-repeat.bh (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/dist/src/bithenge/test-repeat.bh (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,26 @@ +transform with_count = struct { + .none <- repeat(0) { uint8 }; + .one <- repeat(1) { uint8 }; + .count <- uint8; + if (true) { # test whether .count is still accessible + .many <- repeat(.count) { uint8 }; + } +}; + +transform without_count = struct { + .until_error <- repeat { uint8 <- zero_terminated }; + .until_end <- repeat { uint8 }; +}; + +transform do_while = do { + struct { + .valid <- nonzero_boolean <- uint8; + .val <- uint8; + } +} while (.valid); + +transform main = struct { + .with_count <- with_count; + .without_count <- without_count <- known_length(9); + .do_while <- do_while; +}; Index: uspace/dist/src/bithenge/test.bh =================================================================== --- uspace/dist/src/bithenge/test.bh (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/dist/src/bithenge/test.bh (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,36 @@ +transform pascal_string = struct { + <- struct { # An inner struct for testing purposes + .len <- uint8; + }; + .string <- ascii <- known_length(.len); +}; + +transform u32(little_endian) = + if (little_endian) { + uint32le + } else { + uint32be + }; + +transform item(little_endian, len) = struct { + .type <- (3 * in + 1) <- u32(little_endian); + .name <- pascal_string; + switch (.type) { + 10: { + .val <- u32(little_endian); + }; + 11: { + .text <- ascii <- known_length(len); + }; + else: { + .unknown <- known_length(len); + }; + } +}; + +transform main() = struct { + .first_len <- (3); + .second_len <- (6 - 2); + .first_item <- item(true, .first_len); + .second_item <- item(false, .second_len); +}; Index: uspace/dist/src/bithenge/trip.bh =================================================================== --- uspace/dist/src/bithenge/trip.bh (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/dist/src/bithenge/trip.bh (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,15 @@ +transform point = struct { + .lat <- uint32le; + .lon <- uint32le; +}; + +transform named_point = struct { + .name <- ascii <- zero_terminated; + <- point; +}; + +transform main = struct { + .from <- named_point; + .to <- named_point; + .distance <- uint32le; # in kilometers +}; Index: uspace/dist/src/bithenge/usbdesc.bh =================================================================== --- uspace/dist/src/bithenge/usbdesc.bh (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) +++ uspace/dist/src/bithenge/usbdesc.bh (revision 05f5fbfc5c9c4326cfcfe05020160cd425e78353) @@ -0,0 +1,68 @@ +## +## +## USB DESCRIPTORS +## +## + +# Originally by Vojtech Horky. + +# Block prefixed with a byte length +transform block = (in.data) <- struct { + .bLength <- uint8; + .data <- known_length(.bLength - 1); +}; + +# USB configuration descriptor +# This is not the full configuration descriptor (i.e. with interface +# and endpoint descriptors included) but only the header. +transform usb_configuration_descriptor_bare = struct { + .wTotalLength <- uint16le; + .bNumInterfaces <- uint8; + .bConfigurationValue <- uint8; + .iConfiguration <- uint8; + .bmAttributes <- uint8; + .MaxPower <- uint8; +}; + +# USB interface descriptor +transform usb_interface_descriptor = struct { + .bInterfaceNumber <- uint8; + .bAlternateSetting <- uint8; + .bNumEndpoints <- uint8; + .bInterfaceClass <- uint8; + .bInterfaceSubClass <- uint8; + .bInterfaceProtocol <- uint8; + .iInterface <- uint8; +}; + +# USB endpoint descriptor +transform usb_endpoint_descriptor = struct { + .bEndpointAddress <- uint8; + .bmAttributes <- uint8; + .wMaxPacketSize <- uint16le; + .bInterval <- uint8; +}; + +# USB HID descriptor +transform usb_hid_descriptor = struct { + .bcdHID <- uint16le; + .bCountryCode <- uint8; + .bNumDescriptors <- uint8; + <- repeat(.bNumDescriptors) { struct { + .bDescriptorType <- uint8; + .wDescriptorLength <- uint16le; + } }; +}; + +# USB descriptor +transform usb_descriptor = struct { + .bDescriptorType <- uint8; + <- switch (.bDescriptorType) { + 2: usb_configuration_descriptor_bare; + 4: usb_interface_descriptor; + 5: usb_endpoint_descriptor; + 33: usb_hid_descriptor; + }; +} <- block; + +transform main = repeat { usb_descriptor };