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 = -EINVAL;
 247         if (val_node == NULL)
 248                 goto fail;
 249         ret = -EPERM;
 250         if (gen_node->flags & EC_NODE_F_BUILT)
 251                 goto fail;
 252         ret = -EEXIST;
 253         if (node->val_node != NULL)
 254                 goto fail;
 255
 256         node->val_node = val_node;
 257         gen_node->flags &= ~EC_NODE_F_BUILT;
 258
 259         return 0;
 260
 261 fail:
 262         ec_node_free(val_node);
 263         return ret;
 264 }
 265
 266 /* add a binary operator */
 267 int ec_node_expr_add_bin_op(struct ec_node *gen_node, struct ec_node *op)
 268 {
 269         struct ec_node_expr *node = (struct ec_node_expr *)gen_node;
 270         struct ec_node **bin_ops;
 271         int ret;
 272
 273         // XXX check node type
 274
 275         ret = -EINVAL;
 276         if (node == NULL || op == NULL)
 277                 goto fail;
 278         ret = -EPERM;
 279         if (gen_node->flags & EC_NODE_F_BUILT)
 280                 goto fail;
 281
 282         ret = -ENOMEM;
 283         bin_ops = ec_realloc(node->bin_ops,
 284                 (node->bin_ops_len + 1) * sizeof(*node->bin_ops));
 285         if (bin_ops == NULL)
 286                 goto fail;;
 287
 288         node->bin_ops = bin_ops;
 289         bin_ops[node->bin_ops_len] = op;
 290         node->bin_ops_len++;
 291         gen_node->flags &= ~EC_NODE_F_BUILT;
 292
 293         return 0;
 294
 295 fail:
 296         ec_node_free(op);
 297         return ret;
 298 }
 299
 300 /* add a unary pre-operator */
 301 int ec_node_expr_add_pre_op(struct ec_node *gen_node, struct ec_node *op)
 302 {
 303         struct ec_node_expr *node = (struct ec_node_expr *)gen_node;
 304         struct ec_node **pre_ops;
 305         int ret;
 306
 307         // XXX check node type
 308
 309         ret = -EINVAL;
 310         if (node == NULL || op == NULL)
 311                 goto fail;
 312         ret = -EPERM;
 313         if (gen_node->flags & EC_NODE_F_BUILT)
 314                 goto fail;
 315
 316         ret = -ENOMEM;
 317         pre_ops = ec_realloc(node->pre_ops,
 318                 (node->pre_ops_len + 1) * sizeof(*node->pre_ops));
 319         if (pre_ops == NULL)
 320                 goto fail;
 321
 322         node->pre_ops = pre_ops;
 323         pre_ops[node->pre_ops_len] = op;
 324         node->pre_ops_len++;
 325         gen_node->flags &= ~EC_NODE_F_BUILT;
 326
 327         return 0;
 328
 329 fail:
 330         ec_node_free(op);
 331         return ret;
 332 }
 333
 334 /* add a unary post-operator */
 335 int ec_node_expr_add_post_op(struct ec_node *gen_node, struct ec_node *op)
 336 {
 337         struct ec_node_expr *node = (struct ec_node_expr *)gen_node;
 338         struct ec_node **post_ops;
 339         int ret;
 340
 341         // XXX check node type
 342
 343         ret = -EINVAL;
 344         if (node == NULL || op == NULL)
 345                 goto fail;
 346         ret = -EPERM;
 347         if (gen_node->flags & EC_NODE_F_BUILT)
 348                 goto fail;
 349
 350         ret = -ENOMEM;
 351         post_ops = ec_realloc(node->post_ops,
 352                 (node->post_ops_len + 1) * sizeof(*node->post_ops));
 353         if (post_ops == NULL)
 354                 goto fail;
 355
 356         node->post_ops = post_ops;
 357         post_ops[node->post_ops_len] = op;
 358         node->post_ops_len++;
 359         gen_node->flags &= ~EC_NODE_F_BUILT;
 360
 361         return 0;
 362
 363 fail:
 364         ec_node_free(op);
 365         return ret;
 366 }
 367
 368 /* add parenthesis symbols */
 369 int ec_node_expr_add_parenthesis(struct ec_node *gen_node,
 370         struct ec_node *open, struct ec_node *close)
 371 {
 372         struct ec_node_expr *node = (struct ec_node_expr *)gen_node;
 373         struct ec_node **open_ops, **close_ops;
 374         int ret;
 375
 376         // XXX check node type
 377
 378         ret = -EINVAL;
 379         if (node == NULL || open == NULL || close == NULL)
 380                 goto fail;
 381         ret = -EPERM;
 382         if (gen_node->flags & EC_NODE_F_BUILT)
 383                 goto fail;;
 384
 385         ret = -ENOMEM;
 386         open_ops = ec_realloc(node->open_ops,
 387                 (node->paren_len + 1) * sizeof(*node->open_ops));
 388         if (open_ops == NULL)
 389                 goto fail;
 390         close_ops = ec_realloc(node->close_ops,
 391                 (node->paren_len + 1) * sizeof(*node->close_ops));
 392         if (close_ops == NULL)
 393                 goto fail;
 394
 395         node->open_ops = open_ops;
 396         node->close_ops = close_ops;
 397         open_ops[node->paren_len] = open;
 398         close_ops[node->paren_len] = close;
 399         node->paren_len++;
 400         gen_node->flags &= ~EC_NODE_F_BUILT;
 401
 402         return 0;
 403
 404 fail:
 405         ec_node_free(open);
 406         ec_node_free(close);
 407         return ret;
 408 }
 409
 410 enum expr_node_type {
 411         NONE,
 412         VAL,
 413         BIN_OP,
 414         PRE_OP,
 415         POST_OP,
 416         PAREN_OPEN,
 417         PAREN_CLOSE,
 418 };
 419 static enum expr_node_type get_node_type(const struct ec_node *expr_gen_node,
 420         const struct ec_node *check)
 421 {
 422         struct ec_node_expr *expr_node = (struct ec_node_expr *)expr_gen_node;
 423         size_t i;
 424
 425         if (check == expr_node->val_node)
 426                 return VAL;
 427
 428         for (i = 0; i < expr_node->bin_ops_len; i++) {
 429                 if (check == expr_node->bin_ops[i])
 430                         return BIN_OP;
 431         }
 432         for (i = 0; i < expr_node->pre_ops_len; i++) {
 433                 if (check == expr_node->pre_ops[i])
 434                         return PRE_OP;
 435         }
 436         for (i = 0; i < expr_node->post_ops_len; i++) {
 437                 if (check == expr_node->post_ops[i])
 438                         return POST_OP;
 439         }
 440
 441         for (i = 0; i < expr_node->paren_len; i++) {
 442                 if (check == expr_node->open_ops[i])
 443                         return PAREN_OPEN;
 444         }
 445         for (i = 0; i < expr_node->paren_len; i++) {
 446                 if (check == expr_node->close_ops[i])
 447                         return PAREN_CLOSE;
 448         }
 449
 450         return NONE;
 451 }
 452
 453 struct result {
 454         bool has_val;
 455         void *val;
 456         const struct ec_parsed *op;
 457         enum expr_node_type op_type;
 458 };
 459
 460 /* merge x and y results in x */
 461 static int merge_results(void *userctx,
 462         const struct ec_node_expr_eval_ops *ops,
 463         struct result *x, const struct result *y)
 464 {
 465         int ret;
 466
 467         if (y->has_val == 0 && y->op == NULL)
 468                 return 0;
 469         if (x->has_val == 0 && x->op == NULL) {
 470                 *x = *y;
 471                 return 0;
 472         }
 473
 474         if (x->has_val && y->has_val && y->op != NULL) {
 475                 if (y->op_type == BIN_OP) {
 476                         ret = ops->eval_bin_op(&x->val, userctx, x->val,
 477                                         y->op, y->val);
 478                         if (ret < 0)
 479                                 return ret;
 480
 481                         return 0;
 482                 }
 483         }
 484
 485         if (x->has_val == 0 && x->op != NULL && y->has_val && y->op == NULL) {
 486                 if (x->op_type == PRE_OP) {
 487                         ret = ops->eval_pre_op(&x->val, userctx, y->val, x->op);
 488                         if (ret < 0)
 489                                 return ret;
 490                         x->has_val = true;
 491                         x->op_type = NONE;
 492                         x->op = NULL;
 493                         return 0;
 494                 } else if (x->op_type == BIN_OP) {
 495                         x->val = y->val;
 496                         x->has_val = true;
 497                         return 0;
 498                 }
 499         }
 500
 501         if (x->has_val && x->op == NULL && y->has_val == 0 && y->op != NULL) {
 502                 ret = ops->eval_post_op(&x->val, userctx, x->val, y->op);
 503                 if (ret < 0)
 504                         return ret;
 505
 506                 return 0;
 507         }
 508
 509         assert(false); /* we should not get here */
 510         return -EINVAL;
 511 }
 512
 513 static int eval_expression(struct result *result,
 514         void *userctx,
 515         const struct ec_node_expr_eval_ops *ops,
 516         const struct ec_node *expr_gen_node,
 517         const struct ec_parsed *parsed)
 518
 519 {
 520         struct ec_parsed *open = NULL, *close = NULL;
 521         struct result child_result;
 522         struct ec_parsed *child;
 523         enum expr_node_type type;
 524         int ret;
 525
 526         memset(result, 0, sizeof(*result));
 527         memset(&child_result, 0, sizeof(child_result));
 528
 529         type = get_node_type(expr_gen_node, ec_parsed_get_node(parsed));
 530         if (type == VAL) {
 531                 ret = ops->eval_var(&result->val, userctx, parsed);
 532                 if (ret < 0)
 533                         goto fail;
 534                 result->has_val = 1;
 535         } else if (type == PRE_OP || type == POST_OP || type == BIN_OP) {
 536                 result->op = parsed;
 537                 result->op_type = type;
 538         }
 539
 540         EC_PARSED_FOREACH_CHILD(child, parsed) {
 541
 542                 type = get_node_type(expr_gen_node, ec_parsed_get_node(child));
 543                 if (type == PAREN_OPEN) {
 544                         open = child;
 545                         continue;
 546                 } else if (type == PAREN_CLOSE) {
 547                         close = child;
 548                         continue;
 549                 }
 550
 551                 ret = eval_expression(&child_result, userctx, ops,
 552                         expr_gen_node, child);
 553                 if (ret < 0)
 554                         goto fail;
 555
 556                 ret = merge_results(userctx, ops, result, &child_result);
 557                 if (ret < 0)
 558                         goto fail;
 559
 560                 memset(&child_result, 0, sizeof(child_result));
 561         }
 562
 563         if (open != NULL && close != NULL) {
 564                 ret = ops->eval_parenthesis(&result->val, userctx, open, close,
 565                         result->val);
 566                 if (ret < 0)
 567                         goto fail;
 568         }
 569
 570         return 0;
 571
 572 fail:
 573         if (result->has_val)
 574                 ops->eval_free(result->val, userctx);
 575         if (child_result.has_val)
 576                 ops->eval_free(child_result.val, userctx);
 577         memset(result, 0, sizeof(*result));
 578
 579         return ret;
 580 }
 581
 582 int ec_node_expr_eval(void **user_result, const struct ec_node *node,
 583         struct ec_parsed *parsed, const struct ec_node_expr_eval_ops *ops,
 584         void *userctx)
 585 {
 586         struct result result;
 587         int ret;
 588
 589         if (ops == NULL || ops->eval_var == NULL || ops->eval_pre_op == NULL ||
 590                         ops->eval_post_op == NULL || ops->eval_bin_op == NULL ||
 591                         ops->eval_parenthesis == NULL || ops->eval_free == NULL)
 592                 return -EINVAL;
 593
 594         if (!ec_parsed_matches(parsed))
 595                 return -EINVAL;
 596
 597         //ec_parsed_dump(stdout, parsed); //XXX
 598         ret = eval_expression(&result, userctx, ops, node, parsed);
 599         if (ret < 0)
 600                 return ret;
 601
 602         assert(result.has_val);
 603         assert(result.op == NULL);
 604         *user_result = result.val;
 605
 606         return 0;
 607 }
 608
 609 /* the test case is in a separate file ecoli_node_expr_test.c */