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