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