lib/ecoli_node_expr.c

   1 /*
   2  * Copyright (c) 2016-2017, Olivier MATZ <zer0@droids-corp.org>
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are met:
   6  *
   7  *     * Redistributions of source code must retain the above copyright
   8  *       notice, this list of conditions and the following disclaimer.
   9  *     * Redistributions in binary form must reproduce the above copyright
  10  *       notice, this list of conditions and the following disclaimer in the
  11  *       documentation and/or other materials provided with the distribution.
  12  *     * Neither the name of the University of California, Berkeley nor the
  13  *       names of its contributors may be used to endorse or promote products
  14  *       derived from this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND ANY
  17  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  18  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  19  * DISCLAIMED. IN NO EVENT SHALL THE REGENTS AND CONTRIBUTORS BE LIABLE FOR ANY
  20  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  21  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  22  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  23  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  25  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27
  28 #include <stdio.h>
  29 #include <stdlib.h>
  30 #include <stdbool.h>
  31 #include <stdint.h>
  32 #include <string.h>
  33 #include <assert.h>
  34 #include <stdarg.h>
  35 #include <errno.h>
  36
  37 #include <ecoli_malloc.h>
  38 #include <ecoli_log.h>
  39 #include <ecoli_test.h>
  40 #include <ecoli_strvec.h>
  41 #include <ecoli_node.h>
  42 #include <ecoli_parsed.h>
  43 #include <ecoli_completed.h>
  44 #include <ecoli_node_seq.h>
  45 #include <ecoli_node_many.h>
  46 #include <ecoli_node_or.h>
  47 #include <ecoli_node_weakref.h>
  48 #include <ecoli_node_expr.h>
  49
  50 EC_LOG_TYPE_REGISTER(node_expr);
  51
  52 struct ec_node_expr {
  53         struct ec_node gen;
  54
  55         /* the built node */
  56         struct ec_node *child;
  57
  58         /* the configuration nodes */
  59         struct ec_node *val_node;
  60         struct ec_node **bin_ops;
  61         unsigned int bin_ops_len;
  62         struct ec_node **pre_ops;
  63         unsigned int pre_ops_len;
  64         struct ec_node **post_ops;
  65         unsigned int post_ops_len;
  66         struct ec_node **open_ops;
  67         struct ec_node **close_ops;
  68         unsigned int paren_len;
  69 };
  70
  71 static int ec_node_expr_parse(const struct ec_node *gen_node,
  72                         struct ec_parsed *state,
  73                         const struct ec_strvec *strvec)
  74 {
  75         struct ec_node_expr *node = (struct ec_node_expr *)gen_node;
  76
  77         if (node->child == NULL)
  78                 return -ENOENT;
  79         return ec_node_parse_child(node->child, state, strvec);
  80 }
  81
  82 static int
  83 ec_node_expr_complete(const struct ec_node *gen_node,
  84                 struct ec_completed *completed,
  85                 const struct ec_strvec *strvec)
  86 {
  87         struct ec_node_expr *node = (struct ec_node_expr *)gen_node;
  88
  89         if (node->child == NULL)
  90                 return -ENOENT;
  91         return ec_node_complete_child(node->child, completed, strvec);
  92 }
  93
  94 static void ec_node_expr_free_priv(struct ec_node *gen_node)
  95 {
  96         struct ec_node_expr *node = (struct ec_node_expr *)gen_node;
  97         unsigned int i;
  98
  99         EC_LOG(EC_LOG_DEBUG, "free %p %p %p\n", node, node->child, node->val_node);
 100         ec_node_free(node->val_node);
 101
 102         for (i = 0; i < node->bin_ops_len; i++)
 103                 ec_node_free(node->bin_ops[i]);
 104         ec_free(node->bin_ops);
 105         for (i = 0; i < node->pre_ops_len; i++)
 106                 ec_node_free(node->pre_ops[i]);
 107         ec_free(node->pre_ops);
 108         for (i = 0; i < node->post_ops_len; i++)
 109                 ec_node_free(node->post_ops[i]);
 110         ec_free(node->post_ops);
 111         for (i = 0; i < node->paren_len; i++) {
 112                 ec_node_free(node->open_ops[i]);
 113                 ec_node_free(node->close_ops[i]);
 114         }
 115         ec_free(node->open_ops);
 116         ec_free(node->close_ops);
 117
 118         ec_node_free(node->child);
 119 }
 120
 121 static int ec_node_expr_build(struct ec_node_expr *node)
 122 {
 123         struct ec_node *term = NULL, *expr = NULL, *next = NULL,
 124                 *pre_op = NULL, *post_op = NULL,
 125                 *post = NULL, *weak = NULL;
 126         unsigned int i;
 127         int ret;
 128
 129         ec_node_free(node->child);
 130         node->child = NULL;
 131
 132         if (node->val_node == NULL)
 133                 return -EINVAL;
 134         if (node->bin_ops_len == 0 && node->pre_ops_len == 0 &&
 135                         node->post_ops_len == 0)
 136                 return -EINVAL;
 137
 138         /*
 139          * Example of created grammar:
 140          *
 141          * pre_op = "!"
 142          * post_op = "^"
 143          * post = val |
 144          *        pre_op expr |
 145          *        "(" expr ")"
 146          * term = post post_op*
 147          * prod = term ( "*" term )*
 148          * sum = prod ( "+" prod )*
 149          * expr = sum
 150          */
 151
 152         /* create the object, we will initialize it later: this is
 153          * needed because we have a circular dependency */
 154         ret = -ENOMEM;
 155         weak = ec_node("weakref", "weak");
 156         if (weak == NULL)
 157                 return -1;
 158
 159         /* prefix unary operators */
 160         pre_op = ec_node("or", "pre-op");
 161         if (pre_op == NULL)
 162                 goto fail;
 163         for (i = 0; i < node->pre_ops_len; i++) {
 164                 if (ec_node_or_add(pre_op, ec_node_clone(node->pre_ops[i])) < 0)
 165                         goto fail;
 166         }
 167
 168         /* suffix unary operators */
 169         post_op = ec_node("or", "post-op");
 170         if (post_op == NULL)
 171                 goto fail;
 172         for (i = 0; i < node->post_ops_len; i++) {
 173                 if (ec_node_or_add(post_op, ec_node_clone(node->post_ops[i])) < 0)
 174                         goto fail;
 175         }
 176
 177         post = ec_node("or", "post");
 178         if (post == NULL)
 179                 goto fail;
 180         if (ec_node_or_add(post, ec_node_clone(node->val_node)) < 0)
 181                 goto fail;
 182         if (ec_node_or_add(post,
 183                 EC_NODE_SEQ(EC_NO_ID,
 184                         ec_node_clone(pre_op),
 185                         ec_node_clone(weak))) < 0)
 186                 goto fail;
 187         for (i = 0; i < node->paren_len; i++) {
 188                 if (ec_node_or_add(post, EC_NODE_SEQ(EC_NO_ID,
 189                                         ec_node_clone(node->open_ops[i]),
 190                                         ec_node_clone(weak),
 191                                         ec_node_clone(node->close_ops[i]))) < 0)
 192                         goto fail;
 193         }
 194         term = EC_NODE_SEQ("term",
 195                 ec_node_clone(post),
 196                 ec_node_many(EC_NO_ID, ec_node_clone(post_op), 0, 0)
 197         );
 198         if (term == NULL)
 199                 goto fail;
 200
 201         for (i = 0; i < node->bin_ops_len; i++) {
 202                 next = EC_NODE_SEQ("next",
 203                         ec_node_clone(term),
 204                         ec_node_many(EC_NO_ID,
 205                                 EC_NODE_SEQ(EC_NO_ID,
 206                                         ec_node_clone(node->bin_ops[i]),
 207                                         ec_node_clone(term)
 208                                 ),
 209                                 0, 0
 210                         )
 211                 );
 212                 ec_node_free(term);
 213                 term = next;
 214                 if (term == NULL)
 215                         goto fail;
 216         }
 217         expr = term;
 218         term = NULL;
 219
 220         /* free the initial references */
 221         ec_node_free(pre_op);
 222         pre_op = NULL;
 223         ec_node_free(post_op);
 224         post_op = NULL;
 225         ec_node_free(post);
 226         post = NULL;
 227
 228         /* no need to clone here, the node is not consumed */
 229         if (ec_node_weakref_set(weak, expr) < 0)
 230                 goto fail;
 231         ec_node_free(weak);
 232         weak = NULL;
 233
 234         node->child = expr;
 235
 236         return 0;
 237
 238 fail:
 239         ec_node_free(term);
 240         ec_node_free(expr);
 241         ec_node_free(pre_op);
 242         ec_node_free(post_op);
 243         ec_node_free(post);
 244         ec_node_free(weak);
 245
 246         return ret;
 247 }
 248
 249 static struct ec_node_type ec_node_expr_type = {
 250         .name = "expr",
 251         .parse = ec_node_expr_parse,
 252         .complete = ec_node_expr_complete,
 253         .size = sizeof(struct ec_node_expr),
 254         .free_priv = ec_node_expr_free_priv,
 255 };
 256
 257 EC_NODE_TYPE_REGISTER(ec_node_expr_type);
 258
 259 int ec_node_expr_set_val_node(struct ec_node *gen_node, struct ec_node *val_node)
 260 {
 261         struct ec_node_expr *node = (struct ec_node_expr *)gen_node;
 262         int ret;
 263
 264         ret = ec_node_check_type(gen_node, &ec_node_expr_type);
 265         if (ret < 0)
 266                 return ret;
 267
 268         ret = -EINVAL;
 269         if (val_node == NULL)
 270                 goto fail;
 271
 272         ec_node_free(node->val_node);
 273         node->val_node = val_node;
 274         ec_node_expr_build(node);
 275
 276         return 0;
 277
 278 fail:
 279         ec_node_free(val_node);
 280         return ret;
 281 }
 282
 283 /* add a binary operator */
 284 int ec_node_expr_add_bin_op(struct ec_node *gen_node, struct ec_node *op)
 285 {
 286         struct ec_node_expr *node = (struct ec_node_expr *)gen_node;
 287         struct ec_node **bin_ops;
 288         int ret;
 289
 290         ret = ec_node_check_type(gen_node, &ec_node_expr_type);
 291         if (ret < 0)
 292                 return ret;
 293
 294         ret = -EINVAL;
 295         if (node == NULL || op == NULL)
 296                 goto fail;
 297
 298         ret = -ENOMEM;
 299         bin_ops = ec_realloc(node->bin_ops,
 300                 (node->bin_ops_len + 1) * sizeof(*node->bin_ops));
 301         if (bin_ops == NULL)
 302                 goto fail;;
 303
 304         node->bin_ops = bin_ops;
 305         bin_ops[node->bin_ops_len] = op;
 306         node->bin_ops_len++;
 307         ec_node_expr_build(node);
 308
 309         return 0;
 310
 311 fail:
 312         ec_node_free(op);
 313         return ret;
 314 }
 315
 316 /* add a unary pre-operator */
 317 int ec_node_expr_add_pre_op(struct ec_node *gen_node, struct ec_node *op)
 318 {
 319         struct ec_node_expr *node = (struct ec_node_expr *)gen_node;
 320         struct ec_node **pre_ops;
 321         int ret;
 322
 323         ret = ec_node_check_type(gen_node, &ec_node_expr_type);
 324         if (ret < 0)
 325                 return ret;
 326
 327         ret = -EINVAL;
 328         if (node == NULL || op == NULL)
 329                 goto fail;
 330
 331         ret = -ENOMEM;
 332         pre_ops = ec_realloc(node->pre_ops,
 333                 (node->pre_ops_len + 1) * sizeof(*node->pre_ops));
 334         if (pre_ops == NULL)
 335                 goto fail;
 336
 337         node->pre_ops = pre_ops;
 338         pre_ops[node->pre_ops_len] = op;
 339         node->pre_ops_len++;
 340         ec_node_expr_build(node);
 341
 342         return 0;
 343
 344 fail:
 345         ec_node_free(op);
 346         return ret;
 347 }
 348
 349 /* add a unary post-operator */
 350 int ec_node_expr_add_post_op(struct ec_node *gen_node, struct ec_node *op)
 351 {
 352         struct ec_node_expr *node = (struct ec_node_expr *)gen_node;
 353         struct ec_node **post_ops;
 354         int ret;
 355
 356         ret = ec_node_check_type(gen_node, &ec_node_expr_type);
 357         if (ret < 0)
 358                 return ret;
 359
 360         ret = -EINVAL;
 361         if (node == NULL || op == NULL)
 362                 goto fail;
 363
 364         ret = -ENOMEM;
 365         post_ops = ec_realloc(node->post_ops,
 366                 (node->post_ops_len + 1) * sizeof(*node->post_ops));
 367         if (post_ops == NULL)
 368                 goto fail;
 369
 370         node->post_ops = post_ops;
 371         post_ops[node->post_ops_len] = op;
 372         node->post_ops_len++;
 373         ec_node_expr_build(node);
 374
 375         return 0;
 376
 377 fail:
 378         ec_node_free(op);
 379         return ret;
 380 }
 381
 382 /* add parenthesis symbols */
 383 int ec_node_expr_add_parenthesis(struct ec_node *gen_node,
 384         struct ec_node *open, struct ec_node *close)
 385 {
 386         struct ec_node_expr *node = (struct ec_node_expr *)gen_node;
 387         struct ec_node **open_ops, **close_ops;
 388         int ret;
 389
 390         ret = ec_node_check_type(gen_node, &ec_node_expr_type);
 391         if (ret < 0)
 392                 return ret;
 393
 394         ret = -EINVAL;
 395         if (node == NULL || open == NULL || close == NULL)
 396                 goto fail;
 397
 398         ret = -ENOMEM;
 399         open_ops = ec_realloc(node->open_ops,
 400                 (node->paren_len + 1) * sizeof(*node->open_ops));
 401         if (open_ops == NULL)
 402                 goto fail;
 403         close_ops = ec_realloc(node->close_ops,
 404                 (node->paren_len + 1) * sizeof(*node->close_ops));
 405         if (close_ops == NULL)
 406                 goto fail;
 407
 408         node->open_ops = open_ops;
 409         node->close_ops = close_ops;
 410         open_ops[node->paren_len] = open;
 411         close_ops[node->paren_len] = close;
 412         node->paren_len++;
 413         ec_node_expr_build(node);
 414
 415         return 0;
 416
 417 fail:
 418         ec_node_free(open);
 419         ec_node_free(close);
 420         return ret;
 421 }
 422
 423 enum expr_node_type {
 424         NONE,
 425         VAL,
 426         BIN_OP,
 427         PRE_OP,
 428         POST_OP,
 429         PAREN_OPEN,
 430         PAREN_CLOSE,
 431 };
 432
 433 static enum expr_node_type get_node_type(const struct ec_node *expr_gen_node,
 434         const struct ec_node *check)
 435 {
 436         struct ec_node_expr *expr_node = (struct ec_node_expr *)expr_gen_node;
 437         size_t i;
 438
 439         if (check == expr_node->val_node)
 440                 return VAL;
 441
 442         for (i = 0; i < expr_node->bin_ops_len; i++) {
 443                 if (check == expr_node->bin_ops[i])
 444                         return BIN_OP;
 445         }
 446         for (i = 0; i < expr_node->pre_ops_len; i++) {
 447                 if (check == expr_node->pre_ops[i])
 448                         return PRE_OP;
 449         }
 450         for (i = 0; i < expr_node->post_ops_len; i++) {
 451                 if (check == expr_node->post_ops[i])
 452                         return POST_OP;
 453         }
 454
 455         for (i = 0; i < expr_node->paren_len; i++) {
 456                 if (check == expr_node->open_ops[i])
 457                         return PAREN_OPEN;
 458         }
 459         for (i = 0; i < expr_node->paren_len; i++) {
 460                 if (check == expr_node->close_ops[i])
 461                         return PAREN_CLOSE;
 462         }
 463
 464         return NONE;
 465 }
 466
 467 struct result {
 468         bool has_val;
 469         void *val;
 470         const struct ec_parsed *op;
 471         enum expr_node_type op_type;
 472 };
 473
 474 /* merge x and y results in x */
 475 static int merge_results(void *userctx,
 476         const struct ec_node_expr_eval_ops *ops,
 477         struct result *x, const struct result *y)
 478 {
 479         int ret;
 480
 481         if (y->has_val == 0 && y->op == NULL)
 482                 return 0;
 483         if (x->has_val == 0 && x->op == NULL) {
 484                 *x = *y;
 485                 return 0;
 486         }
 487
 488         if (x->has_val && y->has_val && y->op != NULL) {
 489                 if (y->op_type == BIN_OP) {
 490                         ret = ops->eval_bin_op(&x->val, userctx, x->val,
 491                                         y->op, y->val);
 492                         if (ret < 0)
 493                                 return ret;
 494
 495                         return 0;
 496                 }
 497         }
 498
 499         if (x->has_val == 0 && x->op != NULL && y->has_val && y->op == NULL) {
 500                 if (x->op_type == PRE_OP) {
 501                         ret = ops->eval_pre_op(&x->val, userctx, y->val, x->op);
 502                         if (ret < 0)
 503                                 return ret;
 504                         x->has_val = true;
 505                         x->op_type = NONE;
 506                         x->op = NULL;
 507                         return 0;
 508                 } else if (x->op_type == BIN_OP) {
 509                         x->val = y->val;
 510                         x->has_val = true;
 511                         return 0;
 512                 }
 513         }
 514
 515         if (x->has_val && x->op == NULL && y->has_val == 0 && y->op != NULL) {
 516                 ret = ops->eval_post_op(&x->val, userctx, x->val, y->op);
 517                 if (ret < 0)
 518                         return ret;
 519
 520                 return 0;
 521         }
 522
 523         assert(false); /* we should not get here */
 524         return -EINVAL;
 525 }
 526
 527 static int eval_expression(struct result *result,
 528         void *userctx,
 529         const struct ec_node_expr_eval_ops *ops,
 530         const struct ec_node *expr_gen_node,
 531         const struct ec_parsed *parsed)
 532
 533 {
 534         struct ec_parsed *open = NULL, *close = NULL;
 535         struct result child_result;
 536         struct ec_parsed *child;
 537         enum expr_node_type type;
 538         int ret;
 539
 540         memset(result, 0, sizeof(*result));
 541         memset(&child_result, 0, sizeof(child_result));
 542
 543         type = get_node_type(expr_gen_node, ec_parsed_get_node(parsed));
 544         if (type == VAL) {
 545                 ret = ops->eval_var(&result->val, userctx, parsed);
 546                 if (ret < 0)
 547                         goto fail;
 548                 result->has_val = 1;
 549         } else if (type == PRE_OP || type == POST_OP || type == BIN_OP) {
 550                 result->op = parsed;
 551                 result->op_type = type;
 552         }
 553
 554         EC_PARSED_FOREACH_CHILD(child, parsed) {
 555
 556                 type = get_node_type(expr_gen_node, ec_parsed_get_node(child));
 557                 if (type == PAREN_OPEN) {
 558                         open = child;
 559                         continue;
 560                 } else if (type == PAREN_CLOSE) {
 561                         close = child;
 562                         continue;
 563                 }
 564
 565                 ret = eval_expression(&child_result, userctx, ops,
 566                         expr_gen_node, child);
 567                 if (ret < 0)
 568                         goto fail;
 569
 570                 ret = merge_results(userctx, ops, result, &child_result);
 571                 if (ret < 0)
 572                         goto fail;
 573
 574                 memset(&child_result, 0, sizeof(child_result));
 575         }
 576
 577         if (open != NULL && close != NULL) {
 578                 ret = ops->eval_parenthesis(&result->val, userctx, open, close,
 579                         result->val);
 580                 if (ret < 0)
 581                         goto fail;
 582         }
 583
 584         return 0;
 585
 586 fail:
 587         if (result->has_val)
 588                 ops->eval_free(result->val, userctx);
 589         if (child_result.has_val)
 590                 ops->eval_free(child_result.val, userctx);
 591         memset(result, 0, sizeof(*result));
 592
 593         return ret;
 594 }
 595
 596 int ec_node_expr_eval(void **user_result, const struct ec_node *node,
 597         struct ec_parsed *parsed, const struct ec_node_expr_eval_ops *ops,
 598         void *userctx)
 599 {
 600         struct result result;
 601         int ret;
 602
 603         if (ops == NULL || ops->eval_var == NULL || ops->eval_pre_op == NULL ||
 604                         ops->eval_post_op == NULL || ops->eval_bin_op == NULL ||
 605                         ops->eval_parenthesis == NULL || ops->eval_free == NULL)
 606                 return -EINVAL;
 607
 608         ret = ec_node_check_type(node, &ec_node_expr_type);
 609         if (ret < 0)
 610                 return ret;
 611
 612         if (!ec_parsed_matches(parsed))
 613                 return -EINVAL;
 614
 615         ret = eval_expression(&result, userctx, ops, node, parsed);
 616         if (ret < 0)
 617                 return ret;
 618
 619         assert(result.has_val);
 620         assert(result.op == NULL);
 621         *user_result = result.val;
 622
 623         return 0;
 624 }
 625
 626 /* the test case is in a separate file ecoli_node_expr_test.c */