src/ecoli_node_expr.c

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright 2016, Olivier MATZ <zer0@droids-corp.org>
   3  */
   4
   5 #include <stdio.h>
   6 #include <stdlib.h>
   7 #include <stdbool.h>
   8 #include <stdint.h>
   9 #include <string.h>
  10 #include <assert.h>
  11 #include <stdarg.h>
  12 #include <errno.h>
  13
  14 #include <ecoli_malloc.h>
  15 #include <ecoli_log.h>
  16 #include <ecoli_test.h>
  17 #include <ecoli_strvec.h>
  18 #include <ecoli_node.h>
  19 #include <ecoli_parse.h>
  20 #include <ecoli_complete.h>
  21 #include <ecoli_node_seq.h>
  22 #include <ecoli_node_many.h>
  23 #include <ecoli_node_or.h>
  24 #include <ecoli_node_expr.h>
  25
  26 EC_LOG_TYPE_REGISTER(node_expr);
  27
  28 struct ec_node_expr {
  29         /* the built node */
  30         struct ec_node *child;
  31
  32         /* the configuration nodes */
  33         struct ec_node *val_node;
  34         struct ec_node **bin_ops;
  35         unsigned int bin_ops_len;
  36         struct ec_node **pre_ops;
  37         unsigned int pre_ops_len;
  38         struct ec_node **post_ops;
  39         unsigned int post_ops_len;
  40         struct ec_node **open_ops;
  41         struct ec_node **close_ops;
  42         unsigned int paren_len;
  43 };
  44
  45 static int ec_node_expr_parse(const struct ec_node *node,
  46                         struct ec_pnode *pstate,
  47                         const struct ec_strvec *strvec)
  48 {
  49         struct ec_node_expr *priv = ec_node_priv(node);
  50
  51         if (priv->child == NULL) {
  52                 errno = ENOENT;
  53                 return -1;
  54         }
  55
  56         return ec_parse_child(priv->child, pstate, strvec);
  57 }
  58
  59 static int
  60 ec_node_expr_complete(const struct ec_node *node,
  61                 struct ec_comp *comp,
  62                 const struct ec_strvec *strvec)
  63 {
  64         struct ec_node_expr *priv = ec_node_priv(node);
  65
  66         if (priv->child == NULL) {
  67                 errno = ENOENT;
  68                 return -1;
  69         }
  70
  71         return ec_complete_child(priv->child, comp, strvec);
  72 }
  73
  74 static void ec_node_expr_free_priv(struct ec_node *node)
  75 {
  76         struct ec_node_expr *priv = ec_node_priv(node);
  77         unsigned int i;
  78
  79         ec_node_free(priv->child);
  80         ec_node_free(priv->val_node);
  81
  82         for (i = 0; i < priv->bin_ops_len; i++)
  83                 ec_node_free(priv->bin_ops[i]);
  84         ec_free(priv->bin_ops);
  85         for (i = 0; i < priv->pre_ops_len; i++)
  86                 ec_node_free(priv->pre_ops[i]);
  87         ec_free(priv->pre_ops);
  88         for (i = 0; i < priv->post_ops_len; i++)
  89                 ec_node_free(priv->post_ops[i]);
  90         ec_free(priv->post_ops);
  91         for (i = 0; i < priv->paren_len; i++) {
  92                 ec_node_free(priv->open_ops[i]);
  93                 ec_node_free(priv->close_ops[i]);
  94         }
  95         ec_free(priv->open_ops);
  96         ec_free(priv->close_ops);
  97 }
  98
  99 static int ec_node_expr_build(struct ec_node_expr *priv)
 100 {
 101         struct ec_node *term = NULL, *expr = NULL, *next = NULL,
 102                 *pre_op = NULL, *post_op = NULL, *ref = NULL,
 103                 *post = NULL;
 104         unsigned int i;
 105
 106         ec_node_free(priv->child);
 107         priv->child = NULL;
 108
 109         if (priv->val_node == NULL) {
 110                 errno = EINVAL;
 111                 return -1;
 112         }
 113
 114         if (priv->bin_ops_len == 0 && priv->pre_ops_len == 0 &&
 115                         priv->post_ops_len == 0) {
 116                 errno = EINVAL;
 117                 return -1;
 118         }
 119
 120         /*
 121          * Example of created grammar:
 122          *
 123          * pre_op = "!"
 124          * post_op = "^"
 125          * post = val |
 126          *        pre_op expr |
 127          *        "(" expr ")"
 128          * term = post post_op*
 129          * prod = term ( "*" term )*
 130          * sum = prod ( "+" prod )*
 131          * expr = sum
 132          */
 133
 134         /* we use this as a ref, will be set later */
 135         ref = ec_node("seq", "ref");
 136         if (ref == NULL)
 137                 return -1;
 138
 139         /* prefix unary operators */
 140         pre_op = ec_node("or", "pre-op");
 141         if (pre_op == NULL)
 142                 goto fail;
 143         for (i = 0; i < priv->pre_ops_len; i++) {
 144                 if (ec_node_or_add(pre_op, ec_node_clone(priv->pre_ops[i])) < 0)
 145                         goto fail;
 146         }
 147
 148         /* suffix unary operators */
 149         post_op = ec_node("or", "post-op");
 150         if (post_op == NULL)
 151                 goto fail;
 152         for (i = 0; i < priv->post_ops_len; i++) {
 153                 if (ec_node_or_add(post_op, ec_node_clone(priv->post_ops[i])) < 0)
 154                         goto fail;
 155         }
 156
 157         post = ec_node("or", "post");
 158         if (post == NULL)
 159                 goto fail;
 160         if (ec_node_or_add(post, ec_node_clone(priv->val_node)) < 0)
 161                 goto fail;
 162         if (ec_node_or_add(post,
 163                 EC_NODE_SEQ(EC_NO_ID,
 164                         ec_node_clone(pre_op),
 165                         ec_node_clone(ref))) < 0)
 166                 goto fail;
 167         for (i = 0; i < priv->paren_len; i++) {
 168                 if (ec_node_or_add(post, EC_NODE_SEQ(EC_NO_ID,
 169                                         ec_node_clone(priv->open_ops[i]),
 170                                         ec_node_clone(ref),
 171                                         ec_node_clone(priv->close_ops[i]))) < 0)
 172                         goto fail;
 173         }
 174         term = EC_NODE_SEQ("term",
 175                 ec_node_clone(post),
 176                 ec_node_many(EC_NO_ID, ec_node_clone(post_op), 0, 0)
 177         );
 178         if (term == NULL)
 179                 goto fail;
 180
 181         for (i = 0; i < priv->bin_ops_len; i++) {
 182                 next = EC_NODE_SEQ("next",
 183                         ec_node_clone(term),
 184                         ec_node_many(EC_NO_ID,
 185                                 EC_NODE_SEQ(EC_NO_ID,
 186                                         ec_node_clone(priv->bin_ops[i]),
 187                                         ec_node_clone(term)
 188                                 ),
 189                                 0, 0
 190                         )
 191                 );
 192                 ec_node_free(term);
 193                 term = next;
 194                 if (term == NULL)
 195                         goto fail;
 196         }
 197         expr = term;
 198         term = NULL;
 199
 200         /* free the initial references */
 201         ec_node_free(pre_op);
 202         pre_op = NULL;
 203         ec_node_free(post_op);
 204         post_op = NULL;
 205         ec_node_free(post);
 206         post = NULL;
 207
 208         if (ec_node_seq_add(ref, ec_node_clone(expr)) < 0)
 209                 goto fail;
 210         ec_node_free(ref);
 211         ref = NULL;
 212
 213         priv->child = expr;
 214
 215         return 0;
 216
 217 fail:
 218         ec_node_free(term);
 219         ec_node_free(expr);
 220         ec_node_free(pre_op);
 221         ec_node_free(post_op);
 222         ec_node_free(post);
 223         ec_node_free(ref);
 224
 225         return -1;
 226 }
 227
 228 static size_t
 229 ec_node_expr_get_children_count(const struct ec_node *node)
 230 {
 231         struct ec_node_expr *priv = ec_node_priv(node);
 232
 233         if (priv->child)
 234                 return 1;
 235         return 0;
 236 }
 237
 238 static int
 239 ec_node_expr_get_child(const struct ec_node *node, size_t i,
 240                 struct ec_node **child, unsigned int *refs)
 241 {
 242         struct ec_node_expr *priv = ec_node_priv(node);
 243
 244         if (i >= 1)
 245                 return -1;
 246
 247         *child = priv->child;
 248         *refs = 1;
 249         return 0;
 250 }
 251
 252 static struct ec_node_type ec_node_expr_type = {
 253         .name = "expr",
 254         .parse = ec_node_expr_parse,
 255         .complete = ec_node_expr_complete,
 256         .size = sizeof(struct ec_node_expr),
 257         .free_priv = ec_node_expr_free_priv,
 258         .get_children_count = ec_node_expr_get_children_count,
 259         .get_child = ec_node_expr_get_child,
 260 };
 261
 262 EC_NODE_TYPE_REGISTER(ec_node_expr_type);
 263
 264 int ec_node_expr_set_val_node(struct ec_node *node, struct ec_node *val_node)
 265 {
 266         struct ec_node_expr *priv = ec_node_priv(node);
 267
 268         if (ec_node_check_type(node, &ec_node_expr_type) < 0)
 269                 goto fail;
 270
 271         if (val_node == NULL) {
 272                 errno = EINVAL;
 273                 goto fail;
 274         }
 275
 276         ec_node_free(priv->val_node);
 277         priv->val_node = val_node;
 278         ec_node_expr_build(priv);
 279
 280         return 0;
 281
 282 fail:
 283         ec_node_free(val_node);
 284         return -1;
 285 }
 286
 287 /* add a binary operator */
 288 int ec_node_expr_add_bin_op(struct ec_node *node, struct ec_node *op)
 289 {
 290         struct ec_node_expr *priv = ec_node_priv(node);
 291         struct ec_node **bin_ops;
 292
 293         if (ec_node_check_type(node, &ec_node_expr_type) < 0)
 294                 goto fail;
 295
 296         if (node == NULL || op == NULL) {
 297                 errno = EINVAL;
 298                 goto fail;
 299         }
 300
 301         bin_ops = ec_realloc(priv->bin_ops,
 302                 (priv->bin_ops_len + 1) * sizeof(*priv->bin_ops));
 303         if (bin_ops == NULL)
 304                 goto fail;;
 305
 306         priv->bin_ops = bin_ops;
 307         bin_ops[priv->bin_ops_len] = op;
 308         priv->bin_ops_len++;
 309         ec_node_expr_build(priv);
 310
 311         return 0;
 312
 313 fail:
 314         ec_node_free(op);
 315         return -1;
 316 }
 317
 318 /* add a unary pre-operator */
 319 int ec_node_expr_add_pre_op(struct ec_node *node, struct ec_node *op)
 320 {
 321         struct ec_node_expr *priv = ec_node_priv(node);
 322         struct ec_node **pre_ops;
 323
 324         if (ec_node_check_type(node, &ec_node_expr_type) < 0)
 325                 goto fail;
 326
 327         if (node == NULL || op == NULL) {
 328                 errno = EINVAL;
 329                 goto fail;
 330         }
 331
 332         pre_ops = ec_realloc(priv->pre_ops,
 333                 (priv->pre_ops_len + 1) * sizeof(*priv->pre_ops));
 334         if (pre_ops == NULL)
 335                 goto fail;
 336
 337         priv->pre_ops = pre_ops;
 338         pre_ops[priv->pre_ops_len] = op;
 339         priv->pre_ops_len++;
 340         ec_node_expr_build(priv);
 341
 342         return 0;
 343
 344 fail:
 345         ec_node_free(op);
 346         return -1;
 347 }
 348
 349 /* add a unary post-operator */
 350 int ec_node_expr_add_post_op(struct ec_node *node, struct ec_node *op)
 351 {
 352         struct ec_node_expr *priv = ec_node_priv(node);
 353         struct ec_node **post_ops;
 354
 355         if (ec_node_check_type(node, &ec_node_expr_type) < 0)
 356                 goto fail;
 357
 358         if (node == NULL || op == NULL) {
 359                 errno = EINVAL;
 360                 goto fail;
 361         }
 362
 363         post_ops = ec_realloc(priv->post_ops,
 364                 (priv->post_ops_len + 1) * sizeof(*priv->post_ops));
 365         if (post_ops == NULL)
 366                 goto fail;
 367
 368         priv->post_ops = post_ops;
 369         post_ops[priv->post_ops_len] = op;
 370         priv->post_ops_len++;
 371         ec_node_expr_build(priv);
 372
 373         return 0;
 374
 375 fail:
 376         ec_node_free(op);
 377         return -1;
 378 }
 379
 380 /* add parenthesis symbols */
 381 int ec_node_expr_add_parenthesis(struct ec_node *node,
 382         struct ec_node *open, struct ec_node *close)
 383 {
 384         struct ec_node_expr *priv = ec_node_priv(node);
 385         struct ec_node **open_ops, **close_ops;
 386
 387         if (ec_node_check_type(node, &ec_node_expr_type) < 0)
 388                 goto fail;
 389
 390         if (node == NULL || open == NULL || close == NULL) {
 391                 errno = EINVAL;
 392                 goto fail;
 393         }
 394
 395         open_ops = ec_realloc(priv->open_ops,
 396                 (priv->paren_len + 1) * sizeof(*priv->open_ops));
 397         if (open_ops == NULL)
 398                 goto fail;
 399         close_ops = ec_realloc(priv->close_ops,
 400                 (priv->paren_len + 1) * sizeof(*priv->close_ops));
 401         if (close_ops == NULL)
 402                 goto fail;
 403
 404         priv->open_ops = open_ops;
 405         priv->close_ops = close_ops;
 406         open_ops[priv->paren_len] = open;
 407         close_ops[priv->paren_len] = close;
 408         priv->paren_len++;
 409         ec_node_expr_build(priv);
 410
 411         return 0;
 412
 413 fail:
 414         ec_node_free(open);
 415         ec_node_free(close);
 416         return -1;
 417 }
 418
 419 enum expr_node_type {
 420         NONE,
 421         VAL,
 422         BIN_OP,
 423         PRE_OP,
 424         POST_OP,
 425         PAREN_OPEN,
 426         PAREN_CLOSE,
 427 };
 428
 429 static enum expr_node_type get_node_type(const struct ec_node *expr_node,
 430         const struct ec_node *check)
 431 {
 432         struct ec_node_expr *expr_priv = ec_node_priv(expr_node);
 433         size_t i;
 434
 435         if (check == expr_priv->val_node)
 436                 return VAL;
 437
 438         for (i = 0; i < expr_priv->bin_ops_len; i++) {
 439                 if (check == expr_priv->bin_ops[i])
 440                         return BIN_OP;
 441         }
 442         for (i = 0; i < expr_priv->pre_ops_len; i++) {
 443                 if (check == expr_priv->pre_ops[i])
 444                         return PRE_OP;
 445         }
 446         for (i = 0; i < expr_priv->post_ops_len; i++) {
 447                 if (check == expr_priv->post_ops[i])
 448                         return POST_OP;
 449         }
 450
 451         for (i = 0; i < expr_priv->paren_len; i++) {
 452                 if (check == expr_priv->open_ops[i])
 453                         return PAREN_OPEN;
 454         }
 455         for (i = 0; i < expr_priv->paren_len; i++) {
 456                 if (check == expr_priv->close_ops[i])
 457                         return PAREN_CLOSE;
 458         }
 459
 460         return NONE;
 461 }
 462
 463 struct result {
 464         bool has_val;
 465         void *val;
 466         const struct ec_pnode *op;
 467         enum expr_node_type op_type;
 468 };
 469
 470 /* merge x and y results in x */
 471 static int merge_results(void *userctx,
 472         const struct ec_node_expr_eval_ops *ops,
 473         struct result *x, const struct result *y)
 474 {
 475         if (y->has_val == 0 && y->op == NULL)
 476                 return 0;
 477         if (x->has_val == 0 && x->op == NULL) {
 478                 *x = *y;
 479                 return 0;
 480         }
 481
 482         if (x->has_val && y->has_val && y->op != NULL) {
 483                 if (y->op_type == BIN_OP) {
 484                         if (ops->eval_bin_op(&x->val, userctx, x->val,
 485                                         y->op, y->val) < 0)
 486                                 return -1;
 487
 488                         return 0;
 489                 }
 490         }
 491
 492         if (x->has_val == 0 && x->op != NULL && y->has_val && y->op == NULL) {
 493                 if (x->op_type == PRE_OP) {
 494                         if (ops->eval_pre_op(&x->val, userctx, y->val,
 495                                                 x->op) < 0)
 496                                 return -1;
 497                         x->has_val = true;
 498                         x->op_type = NONE;
 499                         x->op = NULL;
 500                         return 0;
 501                 } else if (x->op_type == BIN_OP) {
 502                         x->val = y->val;
 503                         x->has_val = true;
 504                         return 0;
 505                 }
 506         }
 507
 508         if (x->has_val && x->op == NULL && y->has_val == 0 && y->op != NULL) {
 509                 if (ops->eval_post_op(&x->val, userctx, x->val, y->op) < 0)
 510                         return -1;
 511
 512                 return 0;
 513         }
 514
 515         assert(false); /* we should not get here */
 516         return -1;
 517 }
 518
 519 static int eval_expression(struct result *result,
 520         void *userctx,
 521         const struct ec_node_expr_eval_ops *ops,
 522         const struct ec_node *expr_node,
 523         const struct ec_pnode *parse)
 524
 525 {
 526         struct ec_pnode *open = NULL, *close = NULL;
 527         struct result child_result;
 528         struct ec_pnode *child;
 529         enum expr_node_type type;
 530
 531         memset(result, 0, sizeof(*result));
 532         memset(&child_result, 0, sizeof(child_result));
 533
 534         type = get_node_type(expr_node, ec_pnode_get_node(parse));
 535         if (type == VAL) {
 536                 if (ops->eval_var(&result->val, userctx, parse) < 0)
 537                         goto fail;
 538                 result->has_val = 1;
 539         } else if (type == PRE_OP || type == POST_OP || type == BIN_OP) {
 540                 result->op = parse;
 541                 result->op_type = type;
 542         }
 543
 544         EC_PNODE_FOREACH_CHILD(child, parse) {
 545
 546                 type = get_node_type(expr_node, ec_pnode_get_node(child));
 547                 if (type == PAREN_OPEN) {
 548                         open = child;
 549                         continue;
 550                 } else if (type == PAREN_CLOSE) {
 551                         close = child;
 552                         continue;
 553                 }
 554
 555                 if (eval_expression(&child_result, userctx, ops,
 556                         expr_node, child) < 0)
 557                         goto fail;
 558
 559                 if (merge_results(userctx, ops, result, &child_result) < 0)
 560                         goto fail;
 561
 562                 memset(&child_result, 0, sizeof(child_result));
 563         }
 564
 565         if (open != NULL && close != NULL) {
 566                 if (ops->eval_parenthesis(&result->val, userctx, open, close,
 567                         result->val) < 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 -1;
 581 }
 582
 583 int ec_node_expr_eval(void **user_result, const struct ec_node *node,
 584         struct ec_pnode *parse, const struct ec_node_expr_eval_ops *ops,
 585         void *userctx)
 586 {
 587         struct result result;
 588
 589         if (ops == NULL || ops->eval_var == NULL || ops->eval_pre_op == NULL ||
 590                         ops->eval_post_op == NULL || ops->eval_bin_op == NULL ||
 591                         ops->eval_parenthesis == NULL ||
 592                         ops->eval_free == NULL) {
 593                 errno = EINVAL;
 594                 return -1;
 595         }
 596
 597         if (ec_node_check_type(node, &ec_node_expr_type) < 0)
 598                 return -1;
 599
 600         if (!ec_pnode_matches(parse)) {
 601                 errno = EINVAL;
 602                 return -1;
 603         }
 604
 605         if (eval_expression(&result, userctx, ops, node, parse) < 0)
 606                 return -1;
 607
 608         assert(result.has_val);
 609         assert(result.op == NULL);
 610         *user_result = result.val;
 611
 612         return 0;
 613 }
 614
 615 /* the test case is in a separate file ecoli_node_expr_test.c */