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