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