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