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