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