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         return ec_node_parse_child(node->child, state, strvec);
  78 }
  79
  80 static int
  81 ec_node_expr_complete(const struct ec_node *gen_node,
  82                 struct ec_completed *completed,
  83                 const struct ec_strvec *strvec)
  84 {
  85         struct ec_node_expr *node = (struct ec_node_expr *)gen_node;
  86
  87         return ec_node_complete_child(node->child, completed, strvec);
  88 }
  89
  90 static void ec_node_expr_free_priv(struct ec_node *gen_node)
  91 {
  92         struct ec_node_expr *node = (struct ec_node_expr *)gen_node;
  93         unsigned int i;
  94
  95         EC_LOG(EC_LOG_DEBUG, "free %p %p %p\n", node, node->child, node->val_node);
  96         ec_node_free(node->val_node);
  97
  98         for (i = 0; i < node->bin_ops_len; i++)
  99                 ec_node_free(node->bin_ops[i]);
 100         ec_free(node->bin_ops);
 101         for (i = 0; i < node->pre_ops_len; i++)
 102                 ec_node_free(node->pre_ops[i]);
 103         ec_free(node->pre_ops);
 104         for (i = 0; i < node->post_ops_len; i++)
 105                 ec_node_free(node->post_ops[i]);
 106         ec_free(node->post_ops);
 107         for (i = 0; i < node->paren_len; i++) {
 108                 ec_node_free(node->open_ops[i]);
 109                 ec_node_free(node->close_ops[i]);
 110         }
 111         ec_free(node->open_ops);
 112         ec_free(node->close_ops);
 113
 114         ec_node_free(node->child);
 115 }
 116
 117 static int ec_node_expr_build(struct ec_node *gen_node)
 118 {
 119         struct ec_node_expr *node = (struct ec_node_expr *)gen_node;
 120         struct ec_node *term = NULL, *expr = NULL, *next = NULL,
 121                 *pre_op = NULL, *post_op = NULL,
 122                 *post = NULL, *weak = NULL;
 123         unsigned int i;
 124         int ret;
 125
 126         if (node->val_node == NULL)
 127                 return -EINVAL;
 128         if (node->bin_ops_len == 0 && node->pre_ops_len == 0 &&
 129                         node->post_ops_len == 0)
 130                 return -EINVAL;
 131
 132         /* create the object, we will initialize it later: this is
 133          * needed because we have a circular dependency */
 134         ret = -ENOMEM;
 135         weak = ec_node("weakref", "weak");
 136         if (weak == NULL)
 137                 return -1;
 138
 139         /* prefix unary operators */
 140         pre_op = ec_node("or", "pre-op");
 141         if (pre_op == NULL)
 142                 goto fail;
 143         for (i = 0; i < node->pre_ops_len; i++) {
 144                 if (ec_node_or_add(pre_op, ec_node_clone(node->pre_ops[i])) < 0)
 145                         goto fail;
 146         }
 147
 148         /* suffix unary operators */
 149         post_op = ec_node("or", "post-op");
 150         if (post_op == NULL)
 151                 goto fail;
 152         for (i = 0; i < node->post_ops_len; i++) {
 153                 if (ec_node_or_add(post_op, ec_node_clone(node->post_ops[i])) < 0)
 154                         goto fail;
 155         }
 156
 157         post = ec_node("or", "post");
 158         if (post == NULL)
 159                 goto fail;
 160         if (ec_node_or_add(post, ec_node_clone(node->val_node)) < 0)
 161                 goto fail;
 162         if (ec_node_or_add(post,
 163                 EC_NODE_SEQ(NULL,
 164                         ec_node_clone(pre_op),
 165                         ec_node_clone(weak))) < 0)
 166                 goto fail;
 167         for (i = 0; i < node->paren_len; i++) {
 168                 if (ec_node_or_add(post, EC_NODE_SEQ(NULL,
 169                                         ec_node_clone(node->open_ops[i]),
 170                                         ec_node_clone(weak),
 171                                         ec_node_clone(node->close_ops[i]))) < 0)
 172                         goto fail;
 173         }
 174         term = EC_NODE_SEQ("term",
 175                 ec_node_clone(post),
 176                 ec_node_many(NULL, ec_node_clone(post_op), 0, 0)
 177         );
 178         if (term == NULL)
 179                 goto fail;
 180
 181         for (i = 0; i < node->bin_ops_len; i++) {
 182                 next = EC_NODE_SEQ("next",
 183                         ec_node_clone(term),
 184                         ec_node_many(NULL,
 185                                 EC_NODE_SEQ(NULL,
 186                                         ec_node_clone(node->bin_ops[i]),
 187                                         ec_node_clone(term)
 188                                 ),
 189                                 0, 0
 190                         )
 191                 );
 192                 ec_node_free(term);
 193                 term = next;
 194                 if (term == NULL)
 195                         goto fail;
 196         }
 197         expr = term;
 198         term = NULL;
 199
 200         /* free the initial references */
 201         ec_node_free(pre_op);
 202         pre_op = NULL;
 203         ec_node_free(post_op);
 204         post_op = NULL;
 205         ec_node_free(post);
 206         post = NULL;
 207
 208         /* no need to clone here, the node is not consumed */
 209         if (ec_node_weakref_set(weak, expr) < 0)
 210                 goto fail;
 211         ec_node_free(weak);
 212         weak = NULL;
 213
 214         node->child = expr;
 215         //ec_node_dump(stdout, node->child); //XXX
 216
 217         return 0;
 218
 219 fail:
 220         ec_node_free(term);
 221         ec_node_free(expr);
 222         ec_node_free(pre_op);
 223         ec_node_free(post_op);
 224         ec_node_free(post);
 225         ec_node_free(weak);
 226
 227         return ret;
 228 }
 229
 230 static struct ec_node_type ec_node_expr_type = {
 231         .name = "expr",
 232         .build = ec_node_expr_build,
 233         .parse = ec_node_expr_parse,
 234         .complete = ec_node_expr_complete,
 235         .size = sizeof(struct ec_node_expr),
 236         .free_priv = ec_node_expr_free_priv,
 237 };
 238
 239 EC_NODE_TYPE_REGISTER(ec_node_expr_type);
 240
 241 int ec_node_expr_set_val_node(struct ec_node *gen_node, struct ec_node *val_node)
 242 {
 243         struct ec_node_expr *node = (struct ec_node_expr *)gen_node;
 244         int ret;
 245
 246         ret = ec_node_check_type(gen_node, &ec_node_expr_type);
 247         if (ret < 0)
 248                 return ret;
 249
 250         ret = -EINVAL;
 251         if (val_node == NULL)
 252                 goto fail;
 253         ret = -EPERM;
 254         if (gen_node->flags & EC_NODE_F_BUILT)
 255                 goto fail;
 256         ret = -EEXIST;
 257         if (node->val_node != NULL)
 258                 goto fail;
 259
 260         node->val_node = val_node;
 261         gen_node->flags &= ~EC_NODE_F_BUILT;
 262
 263         return 0;
 264
 265 fail:
 266         ec_node_free(val_node);
 267         return ret;
 268 }
 269
 270 /* add a binary operator */
 271 int ec_node_expr_add_bin_op(struct ec_node *gen_node, struct ec_node *op)
 272 {
 273         struct ec_node_expr *node = (struct ec_node_expr *)gen_node;
 274         struct ec_node **bin_ops;
 275         int ret;
 276
 277         ret = ec_node_check_type(gen_node, &ec_node_expr_type);
 278         if (ret < 0)
 279                 return ret;
 280
 281         ret = -EINVAL;
 282         if (node == NULL || op == NULL)
 283                 goto fail;
 284         ret = -EPERM;
 285         if (gen_node->flags & EC_NODE_F_BUILT)
 286                 goto fail;
 287
 288         ret = -ENOMEM;
 289         bin_ops = ec_realloc(node->bin_ops,
 290                 (node->bin_ops_len + 1) * sizeof(*node->bin_ops));
 291         if (bin_ops == NULL)
 292                 goto fail;;
 293
 294         node->bin_ops = bin_ops;
 295         bin_ops[node->bin_ops_len] = op;
 296         node->bin_ops_len++;
 297         gen_node->flags &= ~EC_NODE_F_BUILT;
 298
 299         return 0;
 300
 301 fail:
 302         ec_node_free(op);
 303         return ret;
 304 }
 305
 306 /* add a unary pre-operator */
 307 int ec_node_expr_add_pre_op(struct ec_node *gen_node, struct ec_node *op)
 308 {
 309         struct ec_node_expr *node = (struct ec_node_expr *)gen_node;
 310         struct ec_node **pre_ops;
 311         int ret;
 312
 313         ret = ec_node_check_type(gen_node, &ec_node_expr_type);
 314         if (ret < 0)
 315                 return ret;
 316
 317         ret = -EINVAL;
 318         if (node == NULL || op == NULL)
 319                 goto fail;
 320         ret = -EPERM;
 321         if (gen_node->flags & EC_NODE_F_BUILT)
 322                 goto fail;
 323
 324         ret = -ENOMEM;
 325         pre_ops = ec_realloc(node->pre_ops,
 326                 (node->pre_ops_len + 1) * sizeof(*node->pre_ops));
 327         if (pre_ops == NULL)
 328                 goto fail;
 329
 330         node->pre_ops = pre_ops;
 331         pre_ops[node->pre_ops_len] = op;
 332         node->pre_ops_len++;
 333         gen_node->flags &= ~EC_NODE_F_BUILT;
 334
 335         return 0;
 336
 337 fail:
 338         ec_node_free(op);
 339         return ret;
 340 }
 341
 342 /* add a unary post-operator */
 343 int ec_node_expr_add_post_op(struct ec_node *gen_node, struct ec_node *op)
 344 {
 345         struct ec_node_expr *node = (struct ec_node_expr *)gen_node;
 346         struct ec_node **post_ops;
 347         int ret;
 348
 349         ret = ec_node_check_type(gen_node, &ec_node_expr_type);
 350         if (ret < 0)
 351                 return ret;
 352
 353         ret = -EINVAL;
 354         if (node == NULL || op == NULL)
 355                 goto fail;
 356         ret = -EPERM;
 357         if (gen_node->flags & EC_NODE_F_BUILT)
 358                 goto fail;
 359
 360         ret = -ENOMEM;
 361         post_ops = ec_realloc(node->post_ops,
 362                 (node->post_ops_len + 1) * sizeof(*node->post_ops));
 363         if (post_ops == NULL)
 364                 goto fail;
 365
 366         node->post_ops = post_ops;
 367         post_ops[node->post_ops_len] = op;
 368         node->post_ops_len++;
 369         gen_node->flags &= ~EC_NODE_F_BUILT;
 370
 371         return 0;
 372
 373 fail:
 374         ec_node_free(op);
 375         return ret;
 376 }
 377
 378 /* add parenthesis symbols */
 379 int ec_node_expr_add_parenthesis(struct ec_node *gen_node,
 380         struct ec_node *open, struct ec_node *close)
 381 {
 382         struct ec_node_expr *node = (struct ec_node_expr *)gen_node;
 383         struct ec_node **open_ops, **close_ops;
 384         int ret;
 385
 386         ret = ec_node_check_type(gen_node, &ec_node_expr_type);
 387         if (ret < 0)
 388                 return ret;
 389
 390         ret = -EINVAL;
 391         if (node == NULL || open == NULL || close == NULL)
 392                 goto fail;
 393         ret = -EPERM;
 394         if (gen_node->flags & EC_NODE_F_BUILT)
 395                 goto fail;;
 396
 397         ret = -ENOMEM;
 398         open_ops = ec_realloc(node->open_ops,
 399                 (node->paren_len + 1) * sizeof(*node->open_ops));
 400         if (open_ops == NULL)
 401                 goto fail;
 402         close_ops = ec_realloc(node->close_ops,
 403                 (node->paren_len + 1) * sizeof(*node->close_ops));
 404         if (close_ops == NULL)
 405                 goto fail;
 406
 407         node->open_ops = open_ops;
 408         node->close_ops = close_ops;
 409         open_ops[node->paren_len] = open;
 410         close_ops[node->paren_len] = close;
 411         node->paren_len++;
 412         gen_node->flags &= ~EC_NODE_F_BUILT;
 413
 414         return 0;
 415
 416 fail:
 417         ec_node_free(open);
 418         ec_node_free(close);
 419         return ret;
 420 }
 421
 422 enum expr_node_type {
 423         NONE,
 424         VAL,
 425         BIN_OP,
 426         PRE_OP,
 427         POST_OP,
 428         PAREN_OPEN,
 429         PAREN_CLOSE,
 430 };
 431
 432 static enum expr_node_type get_node_type(const struct ec_node *expr_gen_node,
 433         const struct ec_node *check)
 434 {
 435         struct ec_node_expr *expr_node = (struct ec_node_expr *)expr_gen_node;
 436         size_t i;
 437
 438         if (check == expr_node->val_node)
 439                 return VAL;
 440
 441         for (i = 0; i < expr_node->bin_ops_len; i++) {
 442                 if (check == expr_node->bin_ops[i])
 443                         return BIN_OP;
 444         }
 445         for (i = 0; i < expr_node->pre_ops_len; i++) {
 446                 if (check == expr_node->pre_ops[i])
 447                         return PRE_OP;
 448         }
 449         for (i = 0; i < expr_node->post_ops_len; i++) {
 450                 if (check == expr_node->post_ops[i])
 451                         return POST_OP;
 452         }
 453
 454         for (i = 0; i < expr_node->paren_len; i++) {
 455                 if (check == expr_node->open_ops[i])
 456                         return PAREN_OPEN;
 457         }
 458         for (i = 0; i < expr_node->paren_len; i++) {
 459                 if (check == expr_node->close_ops[i])
 460                         return PAREN_CLOSE;
 461         }
 462
 463         return NONE;
 464 }
 465
 466 struct result {
 467         bool has_val;
 468         void *val;
 469         const struct ec_parsed *op;
 470         enum expr_node_type op_type;
 471 };
 472
 473 /* merge x and y results in x */
 474 static int merge_results(void *userctx,
 475         const struct ec_node_expr_eval_ops *ops,
 476         struct result *x, const struct result *y)
 477 {
 478         int ret;
 479
 480         if (y->has_val == 0 && y->op == NULL)
 481                 return 0;
 482         if (x->has_val == 0 && x->op == NULL) {
 483                 *x = *y;
 484                 return 0;
 485         }
 486
 487         if (x->has_val && y->has_val && y->op != NULL) {
 488                 if (y->op_type == BIN_OP) {
 489                         ret = ops->eval_bin_op(&x->val, userctx, x->val,
 490                                         y->op, y->val);
 491                         if (ret < 0)
 492                                 return ret;
 493
 494                         return 0;
 495                 }
 496         }
 497
 498         if (x->has_val == 0 && x->op != NULL && y->has_val && y->op == NULL) {
 499                 if (x->op_type == PRE_OP) {
 500                         ret = ops->eval_pre_op(&x->val, userctx, y->val, x->op);
 501                         if (ret < 0)
 502                                 return ret;
 503                         x->has_val = true;
 504                         x->op_type = NONE;
 505                         x->op = NULL;
 506                         return 0;
 507                 } else if (x->op_type == BIN_OP) {
 508                         x->val = y->val;
 509                         x->has_val = true;
 510                         return 0;
 511                 }
 512         }
 513
 514         if (x->has_val && x->op == NULL && y->has_val == 0 && y->op != NULL) {
 515                 ret = ops->eval_post_op(&x->val, userctx, x->val, y->op);
 516                 if (ret < 0)
 517                         return ret;
 518
 519                 return 0;
 520         }
 521
 522         assert(false); /* we should not get here */
 523         return -EINVAL;
 524 }
 525
 526 static int eval_expression(struct result *result,
 527         void *userctx,
 528         const struct ec_node_expr_eval_ops *ops,
 529         const struct ec_node *expr_gen_node,
 530         const struct ec_parsed *parsed)
 531
 532 {
 533         struct ec_parsed *open = NULL, *close = NULL;
 534         struct result child_result;
 535         struct ec_parsed *child;
 536         enum expr_node_type type;
 537         int ret;
 538
 539         memset(result, 0, sizeof(*result));
 540         memset(&child_result, 0, sizeof(child_result));
 541
 542         type = get_node_type(expr_gen_node, ec_parsed_get_node(parsed));
 543         if (type == VAL) {
 544                 ret = ops->eval_var(&result->val, userctx, parsed);
 545                 if (ret < 0)
 546                         goto fail;
 547                 result->has_val = 1;
 548         } else if (type == PRE_OP || type == POST_OP || type == BIN_OP) {
 549                 result->op = parsed;
 550                 result->op_type = type;
 551         }
 552
 553         EC_PARSED_FOREACH_CHILD(child, parsed) {
 554
 555                 type = get_node_type(expr_gen_node, ec_parsed_get_node(child));
 556                 if (type == PAREN_OPEN) {
 557                         open = child;
 558                         continue;
 559                 } else if (type == PAREN_CLOSE) {
 560                         close = child;
 561                         continue;
 562                 }
 563
 564                 ret = eval_expression(&child_result, userctx, ops,
 565                         expr_gen_node, child);
 566                 if (ret < 0)
 567                         goto fail;
 568
 569                 ret = merge_results(userctx, ops, result, &child_result);
 570                 if (ret < 0)
 571                         goto fail;
 572
 573                 memset(&child_result, 0, sizeof(child_result));
 574         }
 575
 576         if (open != NULL && close != NULL) {
 577                 ret = ops->eval_parenthesis(&result->val, userctx, open, close,
 578                         result->val);
 579                 if (ret < 0)
 580                         goto fail;
 581         }
 582
 583         return 0;
 584
 585 fail:
 586         if (result->has_val)
 587                 ops->eval_free(result->val, userctx);
 588         if (child_result.has_val)
 589                 ops->eval_free(child_result.val, userctx);
 590         memset(result, 0, sizeof(*result));
 591
 592         return ret;
 593 }
 594
 595 int ec_node_expr_eval(void **user_result, const struct ec_node *node,
 596         struct ec_parsed *parsed, const struct ec_node_expr_eval_ops *ops,
 597         void *userctx)
 598 {
 599         struct result result;
 600         int ret;
 601
 602         if (ops == NULL || ops->eval_var == NULL || ops->eval_pre_op == NULL ||
 603                         ops->eval_post_op == NULL || ops->eval_bin_op == NULL ||
 604                         ops->eval_parenthesis == NULL || ops->eval_free == NULL)
 605                 return -EINVAL;
 606
 607         if (!ec_parsed_matches(parsed))
 608                 return -EINVAL;
 609
 610         //ec_parsed_dump(stdout, parsed); //XXX
 611         ret = eval_expression(&result, userctx, ops, node, parsed);
 612         if (ret < 0)
 613                 return ret;
 614
 615         assert(result.has_val);
 616         assert(result.op == NULL);
 617         *user_result = result.val;
 618
 619         return 0;
 620 }
 621
 622 /* the test case is in a separate file ecoli_node_expr_test.c */