uspace/lib/bithenge/expression.c

   1 /*
   2  * Copyright (c) 2012 Sean Bartell
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * - Redistributions of source code must retain the above copyright
  10  *   notice, this list of conditions and the following disclaimer.
  11  * - Redistributions in binary form must reproduce the above copyright
  12  *   notice, this list of conditions and the following disclaimer in the
  13  *   documentation and/or other materials provided with the distribution.
  14  * - The name of the author may not be used to endorse or promote products
  15  *   derived from this software without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  18  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  19  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  20  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  22  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 /** @addtogroup bithenge
  30  * @{
  31  */
  32 /**
  33  * @file
  34  * Expressions.
  35  */
  36
  37 #include <assert.h>
  38 #include <errno.h>
  39 #include <stdlib.h>
  40 #include "blob.h"
  41 #include "expression.h"
  42 #include "os.h"
  43 #include "transform.h"
  44 #include "tree.h"
  45
  46 /** Initialize a new expression.
  47  * @param[out] self Expression to initialize.
  48  * @param[in] ops Operations provided by the expression.
  49  * @return EOK or an error code from errno.h. */
  50 int bithenge_init_expression(bithenge_expression_t *self,
  51     const bithenge_expression_ops_t *ops)
  52 {
  53         assert(ops);
  54         assert(ops->evaluate);
  55         assert(ops->destroy);
  56         if (bithenge_should_fail())
  57                 return ENOMEM;
  58         self->ops = ops;
  59         self->refs = 1;
  60         return EOK;
  61 }
  62
  63 static void expression_indestructible(bithenge_expression_t *self)
  64 {
  65         assert(false);
  66 }
  67
  68
  69
  70 /***************** binary_expression                         *****************/
  71
  72 typedef struct {
  73         bithenge_expression_t base;
  74         bithenge_binary_op_t op;
  75         bithenge_expression_t *a, *b;
  76 } binary_expression_t;
  77
  78 static inline binary_expression_t *expression_as_binary(
  79     bithenge_expression_t *base)
  80 {
  81         return (binary_expression_t *)base;
  82 }
  83
  84 static inline bithenge_expression_t *binary_as_expression(
  85     binary_expression_t *self)
  86 {
  87         return &self->base;
  88 }
  89
  90 static int binary_expression_evaluate(bithenge_expression_t *base,
  91     bithenge_scope_t *scope, bithenge_node_t **out)
  92 {
  93         int rc;
  94         binary_expression_t *self = expression_as_binary(base);
  95         bithenge_node_t *a, *b;
  96         rc = bithenge_expression_evaluate(self->a, scope, &a);
  97         if (rc != EOK)
  98                 return rc;
  99         if (self->op != BITHENGE_EXPRESSION_CONCAT) {
 100                 rc = bithenge_expression_evaluate(self->b, scope, &b);
 101                 if (rc != EOK) {
 102                         bithenge_node_dec_ref(a);
 103                         return rc;
 104                 }
 105         }
 106
 107         /* Check types and get values. */
 108         /* Assigning 0 only to make the compiler happy. */
 109         bithenge_int_t a_int = 0, b_int = 0;
 110         bool a_bool = false, b_bool = false, out_bool = false;
 111         switch (self->op) {
 112         case BITHENGE_EXPRESSION_ADD: /* fallthrough */
 113         case BITHENGE_EXPRESSION_SUBTRACT: /* fallthrough */
 114         case BITHENGE_EXPRESSION_MULTIPLY: /* fallthrough */
 115         case BITHENGE_EXPRESSION_INTEGER_DIVIDE: /* fallthrough */
 116         case BITHENGE_EXPRESSION_MODULO: /* fallthrough */
 117         case BITHENGE_EXPRESSION_LESS_THAN: /* fallthrough */
 118         case BITHENGE_EXPRESSION_LESS_THAN_OR_EQUAL: /* fallthrough */
 119         case BITHENGE_EXPRESSION_GREATER_THAN: /* fallthrough */
 120         case BITHENGE_EXPRESSION_GREATER_THAN_OR_EQUAL:
 121                 rc = EINVAL;
 122                 if (bithenge_node_type(a) != BITHENGE_NODE_INTEGER)
 123                         goto error;
 124                 if (bithenge_node_type(b) != BITHENGE_NODE_INTEGER)
 125                         goto error;
 126                 a_int = bithenge_integer_node_value(a);
 127                 b_int = bithenge_integer_node_value(b);
 128                 break;
 129         case BITHENGE_EXPRESSION_AND: /* fallthrough */
 130         case BITHENGE_EXPRESSION_OR:
 131                 rc = EINVAL;
 132                 if (bithenge_node_type(a) != BITHENGE_NODE_BOOLEAN)
 133                         goto error;
 134                 if (bithenge_node_type(b) != BITHENGE_NODE_BOOLEAN)
 135                         goto error;
 136                 a_bool = bithenge_boolean_node_value(a);
 137                 b_bool = bithenge_boolean_node_value(b);
 138                 break;
 139         case BITHENGE_EXPRESSION_CONCAT:
 140                 if (bithenge_node_type(a) != BITHENGE_NODE_BLOB)
 141                         goto error;
 142                 break;
 143         default:
 144                 break;
 145         }
 146
 147         switch (self->op) {
 148         case BITHENGE_EXPRESSION_ADD:
 149                 rc = bithenge_new_integer_node(out, a_int + b_int);
 150                 break;
 151         case BITHENGE_EXPRESSION_SUBTRACT:
 152                 rc = bithenge_new_integer_node(out, a_int - b_int);
 153                 break;
 154         case BITHENGE_EXPRESSION_MULTIPLY:
 155                 rc = bithenge_new_integer_node(out, a_int * b_int);
 156                 break;
 157         case BITHENGE_EXPRESSION_INTEGER_DIVIDE:
 158                 /* Integer division can behave in three major ways when the
 159                   operands are signed: truncated, floored, or Euclidean. When
 160                  * b > 0, we give the same result as floored and Euclidean;
 161                  * otherwise, we currently raise an error. See
 162                  * https://en.wikipedia.org/wiki/Modulo_operation and its
 163                  * references. */
 164                 if (b_int <= 0) {
 165                         rc = EINVAL;
 166                         break;
 167                 }
 168                 rc = bithenge_new_integer_node(out,
 169                     (a_int / b_int) + (a_int % b_int < 0 ? -1 : 0));
 170                 break;
 171         case BITHENGE_EXPRESSION_MODULO:
 172                 /* This is consistent with division; see above. */
 173                 if (b_int <= 0) {
 174                         rc = EINVAL;
 175                         break;
 176                 }
 177                 rc = bithenge_new_integer_node(out,
 178                     (a_int % b_int) + (a_int % b_int < 0 ? b_int : 0));
 179                 break;
 180         case BITHENGE_EXPRESSION_LESS_THAN:
 181                 rc = bithenge_new_boolean_node(out, a_int < b_int);
 182                 break;
 183         case BITHENGE_EXPRESSION_LESS_THAN_OR_EQUAL:
 184                 rc = bithenge_new_boolean_node(out, a_int <= b_int);
 185                 break;
 186         case BITHENGE_EXPRESSION_GREATER_THAN:
 187                 rc = bithenge_new_boolean_node(out, a_int > b_int);
 188                 break;
 189         case BITHENGE_EXPRESSION_GREATER_THAN_OR_EQUAL:
 190                 rc = bithenge_new_boolean_node(out, a_int >= b_int);
 191                 break;
 192         case BITHENGE_EXPRESSION_EQUALS:
 193                 rc = bithenge_node_equal(&out_bool, a, b);
 194                 if (rc != EOK)
 195                         break;
 196                 rc = bithenge_new_boolean_node(out, out_bool);
 197                 break;
 198         case BITHENGE_EXPRESSION_NOT_EQUALS:
 199                 rc = bithenge_node_equal(&out_bool, a, b);
 200                 if (rc != EOK)
 201                         break;
 202                 rc = bithenge_new_boolean_node(out, !out_bool);
 203                 break;
 204         case BITHENGE_EXPRESSION_AND:
 205                 rc = bithenge_new_boolean_node(out, a_bool && b_bool);
 206                 break;
 207         case BITHENGE_EXPRESSION_OR:
 208                 rc = bithenge_new_boolean_node(out, a_bool || b_bool);
 209                 break;
 210         case BITHENGE_EXPRESSION_MEMBER:
 211                 rc = bithenge_node_get(a, b, out);
 212                 b = NULL;
 213                 break;
 214         case BITHENGE_EXPRESSION_CONCAT:
 215                 bithenge_expression_inc_ref(self->b);
 216                 bithenge_scope_inc_ref(scope);
 217                 rc = bithenge_concat_blob_lazy(out, bithenge_node_as_blob(a),
 218                     self->b, scope);
 219                 a = NULL;
 220                 b = NULL;
 221                 break;
 222         case BITHENGE_EXPRESSION_INVALID_BINARY_OP:
 223                 assert(false);
 224                 break;
 225         }
 226
 227 error:
 228         bithenge_node_dec_ref(a);
 229         bithenge_node_dec_ref(b);
 230         return rc;
 231 }
 232
 233 static void binary_expression_destroy(bithenge_expression_t *base)
 234 {
 235         binary_expression_t *self = expression_as_binary(base);
 236         bithenge_expression_dec_ref(self->a);
 237         bithenge_expression_dec_ref(self->b);
 238         free(self);
 239 }
 240
 241 static const bithenge_expression_ops_t binary_expression_ops = {
 242         .evaluate = binary_expression_evaluate,
 243         .destroy = binary_expression_destroy,
 244 };
 245
 246 /** Create a binary expression. Takes ownership of @a a and @a b.
 247  * @param[out] out Holds the new expression.
 248  * @param op The operator to apply.
 249  * @param a The first operand.
 250  * @param b The second operand.
 251  * @return EOK on success or an error code from errno.h. */
 252 int bithenge_binary_expression(bithenge_expression_t **out,
 253     bithenge_binary_op_t op, bithenge_expression_t *a,
 254     bithenge_expression_t *b)
 255 {
 256         int rc;
 257         binary_expression_t *self = malloc(sizeof(*self));
 258         if (!self) {
 259                 rc = ENOMEM;
 260                 goto error;
 261         }
 262
 263         rc = bithenge_init_expression(binary_as_expression(self),
 264             &binary_expression_ops);
 265         if (rc != EOK)
 266                 goto error;
 267
 268         self->op = op;
 269         self->a = a;
 270         self->b = b;
 271         *out = binary_as_expression(self);
 272         return EOK;
 273
 274 error:
 275         bithenge_expression_dec_ref(a);
 276         bithenge_expression_dec_ref(b);
 277         free(self);
 278         return rc;
 279 }
 280
 281
 282
 283 /***************** in_node_expression                        *****************/
 284
 285 static int in_node_evaluate(bithenge_expression_t *self,
 286     bithenge_scope_t *scope, bithenge_node_t **out)
 287 {
 288         for (; scope; scope = bithenge_scope_outer(scope)) {
 289                 *out = bithenge_scope_in_node(scope);
 290                 if (*out)
 291                         return EOK;
 292         }
 293         return EINVAL;
 294 }
 295
 296 static const bithenge_expression_ops_t in_node_ops = {
 297         .evaluate = in_node_evaluate,
 298         .destroy = expression_indestructible,
 299 };
 300
 301 static bithenge_expression_t in_node_expression = {
 302         &in_node_ops, 1
 303 };
 304
 305 /** Create an expression that gets the current input node.
 306  * @param[out] out Holds the new expression.
 307  * @return EOK on success or an error code from errno.h. */
 308 int bithenge_in_node_expression(bithenge_expression_t **out)
 309 {
 310         if (bithenge_should_fail())
 311                 return ENOMEM;
 312         bithenge_expression_inc_ref(&in_node_expression);
 313         *out = &in_node_expression;
 314         return EOK;
 315 }
 316
 317
 318
 319 /***************** current_node_expression                   *****************/
 320
 321 static int current_node_evaluate(bithenge_expression_t *self,
 322     bithenge_scope_t *scope, bithenge_node_t **out)
 323 {
 324         *out = bithenge_scope_get_current_node(scope);
 325         if (!*out)
 326                 return EINVAL;
 327         return EOK;
 328 }
 329
 330 static const bithenge_expression_ops_t current_node_ops = {
 331         .evaluate = current_node_evaluate,
 332         .destroy = expression_indestructible,
 333 };
 334
 335 static bithenge_expression_t current_node_expression = {
 336         &current_node_ops, 1
 337 };
 338
 339 /** Create an expression that gets the current node being created.
 340  * @param[out] out Holds the new expression.
 341  * @return EOK on success or an error code from errno.h. */
 342 int bithenge_current_node_expression(bithenge_expression_t **out)
 343 {
 344         bithenge_expression_inc_ref(&current_node_expression);
 345         *out = &current_node_expression;
 346         return EOK;
 347 }
 348
 349
 350
 351 /***************** param_expression                          *****************/
 352
 353 typedef struct {
 354         bithenge_expression_t base;
 355         int index;
 356 } param_expression_t;
 357
 358 static inline param_expression_t *expression_as_param(
 359     bithenge_expression_t *base)
 360 {
 361         return (param_expression_t *)base;
 362 }
 363
 364 static inline bithenge_expression_t *param_as_expression(
 365     param_expression_t *self)
 366 {
 367         return &self->base;
 368 }
 369
 370 static int param_expression_evaluate(bithenge_expression_t *base,
 371     bithenge_scope_t *scope, bithenge_node_t **out)
 372 {
 373         param_expression_t *self = expression_as_param(base);
 374         return bithenge_scope_get_param(scope, self->index, out);
 375 }
 376
 377 static void param_expression_destroy(bithenge_expression_t *base)
 378 {
 379         param_expression_t *self = expression_as_param(base);
 380         free(self);
 381 }
 382
 383 static const bithenge_expression_ops_t param_expression_ops = {
 384         .evaluate = param_expression_evaluate,
 385         .destroy = param_expression_destroy,
 386 };
 387
 388 /** Create an expression that returns a parameter.
 389  * @param[out] out Holds the created expression.
 390  * @param index The index of the parameter to get.
 391  * @return EOK on success or an error code from errno.h. */
 392 int bithenge_param_expression(bithenge_expression_t **out, int index)
 393 {
 394         int rc;
 395         param_expression_t *self = malloc(sizeof(*self));
 396         if (!self)
 397                 return ENOMEM;
 398
 399         rc = bithenge_init_expression(param_as_expression(self),
 400             &param_expression_ops);
 401         if (rc != EOK) {
 402                 free(self);
 403                 return rc;
 404         }
 405
 406         self->index = index;
 407         *out = param_as_expression(self);
 408         return EOK;
 409 }
 410
 411
 412
 413 /***************** const_expression                          *****************/
 414
 415 typedef struct {
 416         bithenge_expression_t base;
 417         bithenge_node_t *node;
 418 } const_expression_t;
 419
 420 static inline const_expression_t *expression_as_const(
 421     bithenge_expression_t *base)
 422 {
 423         return (const_expression_t *)base;
 424 }
 425
 426 static inline bithenge_expression_t *const_as_expression(
 427     const_expression_t *self)
 428 {
 429         return &self->base;
 430 }
 431
 432 static int const_expression_evaluate(bithenge_expression_t *base,
 433     bithenge_scope_t *scope, bithenge_node_t **out)
 434 {
 435         const_expression_t *self = expression_as_const(base);
 436         bithenge_node_inc_ref(self->node);
 437         *out = self->node;
 438         return EOK;
 439 }
 440
 441 static void const_expression_destroy(bithenge_expression_t *base)
 442 {
 443         const_expression_t *self = expression_as_const(base);
 444         bithenge_node_dec_ref(self->node);
 445         free(self);
 446 }
 447
 448 static const bithenge_expression_ops_t const_expression_ops = {
 449         .evaluate = const_expression_evaluate,
 450         .destroy = const_expression_destroy,
 451 };
 452
 453 /** Create an expression that returns a constant. Takes a reference to @a node.
 454  * @param[out] out Holds the created expression.
 455  * @param node The constant.
 456  * @return EOK on success or an error code from errno.h. */
 457 int bithenge_const_expression(bithenge_expression_t **out,
 458     bithenge_node_t *node)
 459 {
 460         int rc;
 461         const_expression_t *self = malloc(sizeof(*self));
 462         if (!self) {
 463                 rc = ENOMEM;
 464                 goto error;
 465         }
 466
 467         rc = bithenge_init_expression(const_as_expression(self),
 468             &const_expression_ops);
 469         if (rc != EOK)
 470                 goto error;
 471
 472         self->node = node;
 473         *out = const_as_expression(self);
 474         return EOK;
 475
 476 error:
 477         free(self);
 478         bithenge_node_dec_ref(node);
 479         return rc;
 480 }
 481
 482
 483
 484 /***************** scope_member_expression                   *****************/
 485
 486 typedef struct {
 487         bithenge_expression_t base;
 488         bithenge_node_t *key;
 489 } scope_member_expression_t;
 490
 491 static scope_member_expression_t *expression_as_scope_member(
 492     bithenge_expression_t *base)
 493 {
 494         return (scope_member_expression_t *)base;
 495 }
 496
 497 static bithenge_expression_t *scope_member_as_expression(
 498     scope_member_expression_t *expr)
 499 {
 500         return &expr->base;
 501 }
 502
 503 static int scope_member_expression_evaluate(bithenge_expression_t *base,
 504     bithenge_scope_t *scope, bithenge_node_t **out)
 505 {
 506         scope_member_expression_t *self = expression_as_scope_member(base);
 507         for (; scope && !bithenge_scope_is_barrier(scope);
 508             scope = bithenge_scope_outer(scope)) {
 509                 bithenge_node_t *cur = bithenge_scope_get_current_node(scope);
 510                 if (!cur)
 511                         continue;
 512                 bithenge_node_inc_ref(self->key);
 513                 int rc = bithenge_node_get(cur, self->key, out);
 514                 bithenge_node_dec_ref(cur);
 515                 if (rc != ENOENT) /* EOK or error */
 516                         return rc;
 517         }
 518         return bithenge_scope_error(scope, "No scope member %t", self->key);
 519 }
 520
 521 static void scope_member_expression_destroy(bithenge_expression_t *base)
 522 {
 523         scope_member_expression_t *self = expression_as_scope_member(base);
 524         bithenge_node_dec_ref(self->key);
 525         free(self);
 526 }
 527
 528 static const bithenge_expression_ops_t scope_member_expression_ops = {
 529         .evaluate = scope_member_expression_evaluate,
 530         .destroy = scope_member_expression_destroy,
 531 };
 532
 533 /** Create an expression that gets a member from one of the current nodes being
 534  * created. It searches from the current scope outwards, stopping at barrier
 535  * scopes.
 536  * @param[out] out Holds the new expression.
 537  * @param key The key to search for in nodes being created.
 538  * @return EOK on success or an error code from errno.h. */
 539 int bithenge_scope_member_expression(bithenge_expression_t **out,
 540     bithenge_node_t *key)
 541 {
 542         int rc;
 543         scope_member_expression_t *self = malloc(sizeof(*self));
 544         if (!self) {
 545                 rc = ENOMEM;
 546                 goto error;
 547         }
 548
 549         rc = bithenge_init_expression(scope_member_as_expression(self),
 550             &scope_member_expression_ops);
 551         if (rc != EOK)
 552                 goto error;
 553
 554         self->key = key;
 555         *out = scope_member_as_expression(self);
 556         return EOK;
 557
 558 error:
 559         bithenge_node_dec_ref(key);
 560         free(self);
 561         return rc;
 562 }
 563
 564
 565
 566 /***************** subblob_expression                        *****************/
 567
 568 typedef struct {
 569         bithenge_expression_t base;
 570         bithenge_expression_t *blob, *start, *limit;
 571         bool absolute_limit;
 572 } subblob_expression_t;
 573
 574 static subblob_expression_t *expression_as_subblob(bithenge_expression_t *base)
 575 {
 576         return (subblob_expression_t *)base;
 577 }
 578
 579 static bithenge_expression_t *subblob_as_expression(subblob_expression_t *expr)
 580 {
 581         return &expr->base;
 582 }
 583
 584 static int subblob_expression_evaluate(bithenge_expression_t *base,
 585     bithenge_scope_t *scope, bithenge_node_t **out)
 586 {
 587         subblob_expression_t *self = expression_as_subblob(base);
 588         bithenge_node_t *start_node;
 589         int rc = bithenge_expression_evaluate(self->start, scope, &start_node);
 590         if (rc != EOK)
 591                 return rc;
 592         if (bithenge_node_type(start_node) != BITHENGE_NODE_INTEGER) {
 593                 bithenge_node_dec_ref(start_node);
 594                 return EINVAL;
 595         }
 596         bithenge_int_t start = bithenge_integer_node_value(start_node);
 597         bithenge_node_dec_ref(start_node);
 598
 599         bithenge_int_t limit = -1;
 600         if (self->limit) {
 601                 bithenge_node_t *limit_node;
 602                 rc = bithenge_expression_evaluate(self->limit, scope,
 603                     &limit_node);
 604                 if (rc != EOK)
 605                         return rc;
 606                 if (bithenge_node_type(limit_node) != BITHENGE_NODE_INTEGER) {
 607                         bithenge_node_dec_ref(limit_node);
 608                         return EINVAL;
 609                 }
 610                 limit = bithenge_integer_node_value(limit_node);
 611                 bithenge_node_dec_ref(limit_node);
 612                 if (self->absolute_limit)
 613                         limit -= start;
 614         }
 615
 616         if (start < 0 || (self->limit && limit < 0))
 617                 return EINVAL;
 618
 619         bithenge_node_t *blob;
 620         rc = bithenge_expression_evaluate(self->blob, scope, &blob);
 621         if (rc != EOK)
 622                 return rc;
 623         if (bithenge_node_type(blob) != BITHENGE_NODE_BLOB) {
 624                 bithenge_node_dec_ref(blob);
 625                 return EINVAL;
 626         }
 627
 628         if (self->limit)
 629                 return bithenge_new_subblob(out, bithenge_node_as_blob(blob),
 630                     start, limit);
 631         else
 632                 return bithenge_new_offset_blob(out,
 633                     bithenge_node_as_blob(blob), start);
 634 }
 635
 636 static void subblob_expression_destroy(bithenge_expression_t *base)
 637 {
 638         subblob_expression_t *self = expression_as_subblob(base);
 639         bithenge_expression_dec_ref(self->blob);
 640         bithenge_expression_dec_ref(self->start);
 641         bithenge_expression_dec_ref(self->limit);
 642         free(self);
 643 }
 644
 645 static const bithenge_expression_ops_t subblob_expression_ops = {
 646         .evaluate = subblob_expression_evaluate,
 647         .destroy = subblob_expression_destroy,
 648 };
 649
 650 /** Create an expression that gets a subblob. Takes references to @a blob,
 651  * @a start, and @a limit.
 652  * @param[out] out Holds the new expression.
 653  * @param blob Calculates the blob.
 654  * @param start Calculates the start offset within the blob.
 655  * @param limit Calculates the limit. Can be NULL, in which case an offset blob
 656  * is returned.
 657  * @param absolute_limit If true, the limit is an absolute offset; otherwise,
 658  * it is relative to the start.
 659  * @return EOK on success or an error code from errno.h. */
 660 int bithenge_subblob_expression(bithenge_expression_t **out,
 661     bithenge_expression_t *blob, bithenge_expression_t *start,
 662     bithenge_expression_t *limit, bool absolute_limit)
 663 {
 664         int rc;
 665         subblob_expression_t *self = malloc(sizeof(*self));
 666         if (!self) {
 667                 rc = ENOMEM;
 668                 goto error;
 669         }
 670
 671         rc = bithenge_init_expression(subblob_as_expression(self),
 672             &subblob_expression_ops);
 673         if (rc != EOK)
 674                 goto error;
 675
 676         self->blob = blob;
 677         self->start = start;
 678         self->limit = limit;
 679         self->absolute_limit = absolute_limit;
 680         *out = subblob_as_expression(self);
 681         return EOK;
 682
 683 error:
 684         bithenge_expression_dec_ref(blob);
 685         bithenge_expression_dec_ref(start);
 686         bithenge_expression_dec_ref(limit);
 687         free(self);
 688         return rc;
 689 }
 690
 691 /***************** param_wrapper                             *****************/
 692
 693 typedef struct {
 694         bithenge_transform_t base;
 695         bithenge_transform_t *transform;
 696         bithenge_expression_t **params;
 697 } param_wrapper_t;
 698
 699 static inline bithenge_transform_t *param_wrapper_as_transform(
 700     param_wrapper_t *self)
 701 {
 702         return &self->base;
 703 }
 704
 705 static inline param_wrapper_t *transform_as_param_wrapper(
 706     bithenge_transform_t *base)
 707 {
 708         return (param_wrapper_t *)base;
 709 }
 710
 711 static int param_wrapper_fill_scope(param_wrapper_t *self, bithenge_scope_t
 712     *inner, bithenge_scope_t *outer)
 713 {
 714         int rc;
 715         int num_params = bithenge_transform_num_params(self->transform);
 716         rc = bithenge_scope_alloc_params(inner, num_params);
 717         if (rc != EOK)
 718                 return rc;
 719         for (int i = 0; i < num_params; i++) {
 720                 bithenge_node_t *node;
 721                 rc = bithenge_expression_evaluate(self->params[i], outer,
 722                     &node);
 723                 if (rc != EOK)
 724                         return rc;
 725                 rc = bithenge_scope_set_param(inner, i, node);
 726                 if (rc != EOK)
 727                         return rc;
 728         }
 729         return EOK;
 730 }
 731
 732 static int param_wrapper_apply(bithenge_transform_t *base,
 733     bithenge_scope_t *outer, bithenge_node_t *in, bithenge_node_t **out)
 734 {
 735         param_wrapper_t *self = transform_as_param_wrapper(base);
 736         bithenge_scope_t *inner;
 737         int rc = bithenge_scope_new(&inner, outer);
 738         if (rc != EOK)
 739                 return rc;
 740         rc = param_wrapper_fill_scope(self, inner, outer);
 741         if (rc != EOK)
 742                 goto error;
 743
 744         rc = bithenge_transform_apply(self->transform, inner, in, out);
 745         in = NULL;
 746
 747 error:
 748         bithenge_scope_dec_ref(inner);
 749         return rc;
 750 }
 751
 752 static int param_wrapper_prefix_length(bithenge_transform_t *base,
 753     bithenge_scope_t *outer, bithenge_blob_t *in, aoff64_t *out)
 754 {
 755         param_wrapper_t *self = transform_as_param_wrapper(base);
 756         bithenge_scope_t *inner;
 757         int rc = bithenge_scope_new(&inner, outer);
 758         if (rc != EOK)
 759                 return rc;
 760         rc = param_wrapper_fill_scope(self, inner, outer);
 761         if (rc != EOK)
 762                 goto error;
 763
 764         rc = bithenge_transform_prefix_length(self->transform, inner, in, out);
 765         in = NULL;
 766
 767 error:
 768         bithenge_scope_dec_ref(inner);
 769         return rc;
 770 }
 771
 772 static int param_wrapper_prefix_apply(bithenge_transform_t *base,
 773     bithenge_scope_t *outer, bithenge_blob_t *in, bithenge_node_t **out_node,
 774     aoff64_t *out_length)
 775 {
 776         param_wrapper_t *self = transform_as_param_wrapper(base);
 777         bithenge_scope_t *inner;
 778         int rc = bithenge_scope_new(&inner, outer);
 779         if (rc != EOK)
 780                 return rc;
 781         rc = param_wrapper_fill_scope(self, inner, outer);
 782         if (rc != EOK)
 783                 goto error;
 784
 785         rc = bithenge_transform_prefix_apply(self->transform, inner, in,
 786             out_node, out_length);
 787
 788 error:
 789         bithenge_scope_dec_ref(inner);
 790         return rc;
 791 }
 792
 793 static void param_wrapper_destroy(bithenge_transform_t *base)
 794 {
 795         param_wrapper_t *self = transform_as_param_wrapper(base);
 796         int num_params = bithenge_transform_num_params(self->transform);
 797         bithenge_transform_dec_ref(self->transform);
 798         for (int i = 0; i < num_params; i++)
 799                 bithenge_expression_dec_ref(self->params[i]);
 800         free(self->params);
 801         free(self);
 802 }
 803
 804 static const bithenge_transform_ops_t param_wrapper_ops = {
 805         .apply = param_wrapper_apply,
 806         .prefix_length = param_wrapper_prefix_length,
 807         .prefix_apply = param_wrapper_prefix_apply,
 808         .destroy = param_wrapper_destroy,
 809 };
 810
 811 /** Create a transform that calculates parameters for another transform. Takes
 812  * ownership of @a transform, @a params, and each element of @a params. The
 813  * number of parameters must be correct.
 814  * @param[out] out Holds the new transform.
 815  * @param transform The transform for which parameters are calculated.
 816  * @param params The expressions used to calculate the parameters.
 817  * @return EOK on success or an error code from errno.h. */
 818 int bithenge_param_wrapper(bithenge_transform_t **out,
 819     bithenge_transform_t *transform, bithenge_expression_t **params)
 820 {
 821         int rc;
 822         int num_params = bithenge_transform_num_params(transform);
 823         param_wrapper_t *self = malloc(sizeof(*self));
 824         if (!self) {
 825                 rc = ENOMEM;
 826                 goto error;
 827         }
 828
 829         rc = bithenge_init_transform(param_wrapper_as_transform(self),
 830             &param_wrapper_ops, 0);
 831         if (rc != EOK)
 832                 goto error;
 833
 834         self->transform = transform;
 835         self->params = params;
 836         *out = param_wrapper_as_transform(self);
 837         return EOK;
 838
 839 error:
 840         free(self);
 841         for (int i = 0; i < num_params; i++)
 842                 bithenge_expression_dec_ref(params[i]);
 843         free(params);
 844         bithenge_transform_dec_ref(transform);
 845         return rc;
 846 }
 847
 848
 849
 850 /***************** expression_transform           *****************/
 851
 852 /* Also used by inputless_transform. */
 853 typedef struct {
 854         bithenge_transform_t base;
 855         bithenge_expression_t *expr;
 856 } expression_transform_t;
 857
 858 static inline bithenge_transform_t *expression_as_transform(
 859     expression_transform_t *self)
 860 {
 861         return &self->base;
 862 }
 863
 864 static inline expression_transform_t *transform_as_expression(
 865     bithenge_transform_t *base)
 866 {
 867         return (expression_transform_t *)base;
 868 }
 869
 870 static int expression_transform_apply(bithenge_transform_t *base,
 871     bithenge_scope_t *scope, bithenge_node_t *in, bithenge_node_t **out)
 872 {
 873         expression_transform_t *self = transform_as_expression(base);
 874         bithenge_scope_t *inner;
 875         int rc = bithenge_scope_new(&inner, scope);
 876         if (rc != EOK)
 877                 return rc;
 878         bithenge_scope_set_in_node(inner, in);
 879         rc = bithenge_expression_evaluate(self->expr, inner, out);
 880         bithenge_scope_dec_ref(inner);
 881         return rc;
 882 }
 883
 884 /* Also used by inputless_transform. */
 885 static void expression_transform_destroy(bithenge_transform_t *base)
 886 {
 887         expression_transform_t *self = transform_as_expression(base);
 888         bithenge_expression_dec_ref(self->expr);
 889         free(self);
 890 }
 891
 892 static const bithenge_transform_ops_t expression_transform_ops = {
 893         .apply = expression_transform_apply,
 894         .destroy = expression_transform_destroy,
 895 };
 896
 897 /** Create a transform that evaluates an expression on the input node. Takes a
 898  * reference to the expression.
 899  * @param[out] out Holds the new transform.
 900  * @param expr The expression to evaluate.
 901  * @return EOK on success or an error code from errno.h. */
 902 int bithenge_expression_transform(bithenge_transform_t ** out,
 903     bithenge_expression_t *expr)
 904 {
 905         int rc;
 906         expression_transform_t *self = malloc(sizeof(*self));
 907         if (!self) {
 908                 rc = ENOMEM;
 909                 goto error;
 910         }
 911
 912         rc = bithenge_init_transform(expression_as_transform(self),
 913             &expression_transform_ops, 0);
 914         if (rc != EOK)
 915                 goto error;
 916
 917         self->expr = expr;
 918         *out = expression_as_transform(self);
 919         return EOK;
 920
 921 error:
 922         free(self);
 923         bithenge_expression_dec_ref(expr);
 924         return rc;
 925 }
 926
 927
 928
 929 /***************** inputless_transform            *****************/
 930
 931 static int inputless_transform_prefix_length(bithenge_transform_t *base,
 932     bithenge_scope_t *scope, bithenge_blob_t *in, aoff64_t *out)
 933 {
 934         *out = 0;
 935         return EOK;
 936 }
 937
 938 static int inputless_transform_prefix_apply(bithenge_transform_t *base,
 939     bithenge_scope_t *scope, bithenge_blob_t *in, bithenge_node_t **out_node,
 940     aoff64_t *out_size)
 941 {
 942         expression_transform_t *self = transform_as_expression(base);
 943         if (out_size)
 944                 *out_size = 0;
 945         return bithenge_expression_evaluate(self->expr, scope, out_node);
 946 }
 947
 948 static const bithenge_transform_ops_t inputless_transform_ops = {
 949         .prefix_length = inputless_transform_prefix_length,
 950         .prefix_apply = inputless_transform_prefix_apply,
 951         .destroy = expression_transform_destroy,
 952 };
 953
 954 /** Create a transform that takes an empty blob and produces the result of an
 955  * expression. Takes a reference to the expression.
 956  * @param[out] out Holds the new transform.
 957  * @param expr The expression to evaluate.
 958  * @return EOK on success or an error code from errno.h. */
 959 int bithenge_inputless_transform(bithenge_transform_t ** out,
 960     bithenge_expression_t *expr)
 961 {
 962         int rc;
 963         expression_transform_t *self = malloc(sizeof(*self));
 964         if (!self) {
 965                 rc = ENOMEM;
 966                 goto error;
 967         }
 968
 969         rc = bithenge_init_transform(expression_as_transform(self),
 970             &inputless_transform_ops, 0);
 971         if (rc != EOK)
 972                 goto error;
 973
 974         self->expr = expr;
 975         *out = expression_as_transform(self);
 976         return EOK;
 977
 978 error:
 979         free(self);
 980         bithenge_expression_dec_ref(expr);
 981         return rc;
 982 }
 983
 984
 985
 986 /***************** concat_blob                    *****************/
 987
 988 typedef struct {
 989         bithenge_blob_t base;
 990         bithenge_blob_t *a, *b;
 991         aoff64_t a_size;
 992         bithenge_expression_t *b_expr;
 993         bithenge_scope_t *scope;
 994 } concat_blob_t;
 995
 996 static inline concat_blob_t *blob_as_concat(bithenge_blob_t *base)
 997 {
 998         return (concat_blob_t *)base;
 999 }
1000
1001 static inline bithenge_blob_t *concat_as_blob(concat_blob_t *blob)
1002 {
1003         return &blob->base;
1004 }
1005
1006 static int concat_blob_evaluate_b(concat_blob_t *self)
1007 {
1008         if (self->b)
1009                 return EOK;
1010         bithenge_node_t *b_node;
1011         int rc = bithenge_expression_evaluate(self->b_expr, self->scope,
1012             &b_node);
1013         if (rc != EOK)
1014                 return rc;
1015         if (bithenge_node_type(b_node) != BITHENGE_NODE_BLOB) {
1016                 bithenge_node_dec_ref(b_node);
1017                 return bithenge_scope_error(self->scope,
1018                     "Concatenation arguments must be blobs");
1019         }
1020         self->b = bithenge_node_as_blob(b_node);
1021         bithenge_expression_dec_ref(self->b_expr);
1022         bithenge_scope_dec_ref(self->scope);
1023         self->b_expr = NULL;
1024         self->scope = NULL;
1025         return EOK;
1026 }
1027
1028 static int concat_blob_size(bithenge_blob_t *base, aoff64_t *size)
1029 {
1030         concat_blob_t *self = blob_as_concat(base);
1031         int rc = concat_blob_evaluate_b(self);
1032         if (rc != EOK)
1033                 return rc;
1034         rc = bithenge_blob_size(self->b, size);
1035         *size += self->a_size;
1036         return rc;
1037 }
1038
1039 static int concat_blob_read(bithenge_blob_t *base, aoff64_t offset,
1040     char *buffer, aoff64_t *size)
1041 {
1042         int rc;
1043         concat_blob_t *self = blob_as_concat(base);
1044
1045         aoff64_t a_size = 0, b_size = 0;
1046         if (offset < self->a_size) {
1047                 a_size = *size;
1048                 rc = bithenge_blob_read(self->a, offset, buffer, &a_size);
1049                 if (rc != EOK)
1050                         return rc;
1051         }
1052         if (offset + *size > self->a_size) {
1053                 rc = concat_blob_evaluate_b(self);
1054                 if (rc != EOK)
1055                         return rc;
1056                 b_size = *size - a_size;
1057                 rc = bithenge_blob_read(self->b,
1058                     offset + a_size - self->a_size, buffer + a_size, &b_size);
1059                 if (rc != EOK)
1060                         return rc;
1061         }
1062         assert(a_size + b_size <= *size);
1063         *size = a_size + b_size;
1064         return EOK;
1065 }
1066
1067 static int concat_blob_read_bits(bithenge_blob_t *base, aoff64_t offset,
1068     char *buffer, aoff64_t *size, bool little_endian)
1069 {
1070         int rc;
1071         concat_blob_t *self = blob_as_concat(base);
1072
1073         aoff64_t a_size = 0, b_size = 0;
1074         if (offset < self->a_size) {
1075                 a_size = *size;
1076                 rc = bithenge_blob_read_bits(self->a, offset, buffer, &a_size,
1077                     little_endian);
1078                 if (rc != EOK)
1079                         return rc;
1080         }
1081         if (offset + *size > self->a_size) {
1082                 rc = concat_blob_evaluate_b(self);
1083                 if (rc != EOK)
1084                         return rc;
1085                 b_size = *size - a_size;
1086                 assert(a_size % 8 == 0); /* TODO: don't require this */
1087                 rc = bithenge_blob_read_bits(self->b,
1088                     offset + a_size - self->a_size, buffer + a_size / 8,
1089                     &b_size, little_endian);
1090                 if (rc != EOK)
1091                         return rc;
1092         }
1093         assert(a_size + b_size <= *size);
1094         *size = a_size + b_size;
1095         return EOK;
1096 }
1097
1098 static void concat_blob_destroy(bithenge_blob_t *base)
1099 {
1100         concat_blob_t *self = blob_as_concat(base);
1101         bithenge_blob_dec_ref(self->a);
1102         bithenge_blob_dec_ref(self->b);
1103         bithenge_expression_dec_ref(self->b_expr);
1104         bithenge_scope_dec_ref(self->scope);
1105         free(self);
1106 }
1107
1108 static const bithenge_random_access_blob_ops_t concat_blob_ops = {
1109         .size = concat_blob_size,
1110         .read = concat_blob_read,
1111         .read_bits = concat_blob_read_bits,
1112         .destroy = concat_blob_destroy,
1113 };
1114
1115 /** Create a concatenated blob. Takes references to @a a and @a b.
1116  * @param[out] out Holds the new blob.
1117  * @param a The first blob.
1118  * @param b The second blob.
1119  * @return EOK on success or an error code from errno.h. */
1120 int bithenge_concat_blob(bithenge_node_t **out, bithenge_blob_t *a,
1121     bithenge_blob_t *b)
1122 {
1123         assert(out);
1124         assert(a);
1125         assert(b);
1126         int rc;
1127         concat_blob_t *self = malloc(sizeof(*self));
1128         if (!self) {
1129                 rc = ENOMEM;
1130                 goto error;
1131         }
1132
1133         rc = bithenge_blob_size(a, &self->a_size);
1134         if (rc != EOK)
1135                 goto error;
1136
1137         rc = bithenge_init_random_access_blob(concat_as_blob(self),
1138             &concat_blob_ops);
1139         if (rc != EOK)
1140                 goto error;
1141         self->a = a;
1142         self->b = b;
1143         self->b_expr = NULL;
1144         self->scope = NULL;
1145         *out = bithenge_blob_as_node(concat_as_blob(self));
1146         return EOK;
1147
1148 error:
1149         bithenge_blob_dec_ref(a);
1150         bithenge_blob_dec_ref(b);
1151         free(self);
1152         return rc;
1153 }
1154
1155 /** Create a lazy concatenated blob. Takes references to @a a, @a b_expr, and
1156  * @a scope.
1157  * @param[out] out Holds the new blob.
1158  * @param a The first blob.
1159  * @param b_expr An expression to calculate the second blob.
1160  * @param scope The scope in which @a b_expr should be evaluated.
1161  * @return EOK on success or an error code from errno.h. */
1162 int bithenge_concat_blob_lazy(bithenge_node_t **out, bithenge_blob_t *a,
1163     bithenge_expression_t *b_expr, bithenge_scope_t *scope)
1164 {
1165         assert(out);
1166         assert(a);
1167         assert(b_expr);
1168         assert(scope);
1169         int rc;
1170         concat_blob_t *self = malloc(sizeof(*self));
1171         if (!self) {
1172                 rc = ENOMEM;
1173                 goto error;
1174         }
1175
1176         rc = bithenge_blob_size(a, &self->a_size);
1177         if (rc != EOK)
1178                 goto error;
1179
1180         rc = bithenge_init_random_access_blob(concat_as_blob(self),
1181             &concat_blob_ops);
1182         if (rc != EOK)
1183                 goto error;
1184         self->a = a;
1185         self->b = NULL;
1186         self->b_expr = b_expr;
1187         self->scope = scope;
1188         *out = bithenge_blob_as_node(concat_as_blob(self));
1189         return EOK;
1190
1191 error:
1192         bithenge_blob_dec_ref(a);
1193         bithenge_expression_dec_ref(b_expr);
1194         bithenge_scope_dec_ref(scope);
1195         free(self);
1196         return rc;
1197 }
1198
1199 /** @}
1200  */