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