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