lib/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_LOG(EC_LOG_DEBUG, "free %p %p %p\n", node, node->child, node->val_node);
  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 struct ec_node *
 241 ec_node_expr_get_child(const struct ec_node *gen_node, size_t i)
 242 {
 243         struct ec_node_expr *node = (struct ec_node_expr *)gen_node;
 244
 245         if (i >= 1)
 246                 return NULL;
 247
 248         return node->child;
 249 }
 250
 251 static struct ec_node_type ec_node_expr_type = {
 252         .name = "expr",
 253         .parse = ec_node_expr_parse,
 254         .complete = ec_node_expr_complete,
 255         .size = sizeof(struct ec_node_expr),
 256         .free_priv = ec_node_expr_free_priv,
 257         .get_children_count = ec_node_expr_get_children_count,
 258         .get_child = ec_node_expr_get_child,
 259 };
 260
 261 EC_NODE_TYPE_REGISTER(ec_node_expr_type);
 262
 263 int ec_node_expr_set_val_node(struct ec_node *gen_node, struct ec_node *val_node)
 264 {
 265         struct ec_node_expr *node = (struct ec_node_expr *)gen_node;
 266
 267         if (ec_node_check_type(gen_node, &ec_node_expr_type) < 0)
 268                 goto fail;
 269
 270         if (val_node == NULL) {
 271                 errno = EINVAL;
 272                 goto fail;
 273         }
 274
 275         ec_node_free(node->val_node);
 276         node->val_node = val_node;
 277         ec_node_expr_build(node);
 278
 279         return 0;
 280
 281 fail:
 282         ec_node_free(val_node);
 283         return -1;
 284 }
 285
 286 /* add a binary operator */
 287 int ec_node_expr_add_bin_op(struct ec_node *gen_node, struct ec_node *op)
 288 {
 289         struct ec_node_expr *node = (struct ec_node_expr *)gen_node;
 290         struct ec_node **bin_ops;
 291
 292         if (ec_node_check_type(gen_node, &ec_node_expr_type) < 0)
 293                 goto fail;
 294
 295         if (node == NULL || op == NULL) {
 296                 errno = EINVAL;
 297                 goto fail;
 298         }
 299
 300         bin_ops = ec_realloc(node->bin_ops,
 301                 (node->bin_ops_len + 1) * sizeof(*node->bin_ops));
 302         if (bin_ops == NULL)
 303                 goto fail;;
 304
 305         node->bin_ops = bin_ops;
 306         bin_ops[node->bin_ops_len] = op;
 307         node->bin_ops_len++;
 308         ec_node_expr_build(node);
 309
 310         return 0;
 311
 312 fail:
 313         ec_node_free(op);
 314         return -1;
 315 }
 316
 317 /* add a unary pre-operator */
 318 int ec_node_expr_add_pre_op(struct ec_node *gen_node, struct ec_node *op)
 319 {
 320         struct ec_node_expr *node = (struct ec_node_expr *)gen_node;
 321         struct ec_node **pre_ops;
 322
 323         if (ec_node_check_type(gen_node, &ec_node_expr_type) < 0)
 324                 goto fail;
 325
 326         if (node == NULL || op == NULL) {
 327                 errno = EINVAL;
 328                 goto fail;
 329         }
 330
 331         pre_ops = ec_realloc(node->pre_ops,
 332                 (node->pre_ops_len + 1) * sizeof(*node->pre_ops));
 333         if (pre_ops == NULL)
 334                 goto fail;
 335
 336         node->pre_ops = pre_ops;
 337         pre_ops[node->pre_ops_len] = op;
 338         node->pre_ops_len++;
 339         ec_node_expr_build(node);
 340
 341         return 0;
 342
 343 fail:
 344         ec_node_free(op);
 345         return -1;
 346 }
 347
 348 /* add a unary post-operator */
 349 int ec_node_expr_add_post_op(struct ec_node *gen_node, struct ec_node *op)
 350 {
 351         struct ec_node_expr *node = (struct ec_node_expr *)gen_node;
 352         struct ec_node **post_ops;
 353
 354         if (ec_node_check_type(gen_node, &ec_node_expr_type) < 0)
 355                 goto fail;
 356
 357         if (node == NULL || op == NULL) {
 358                 errno = EINVAL;
 359                 goto fail;
 360         }
 361
 362         post_ops = ec_realloc(node->post_ops,
 363                 (node->post_ops_len + 1) * sizeof(*node->post_ops));
 364         if (post_ops == NULL)
 365                 goto fail;
 366
 367         node->post_ops = post_ops;
 368         post_ops[node->post_ops_len] = op;
 369         node->post_ops_len++;
 370         ec_node_expr_build(node);
 371
 372         return 0;
 373
 374 fail:
 375         ec_node_free(op);
 376         return -1;
 377 }
 378
 379 /* add parenthesis symbols */
 380 int ec_node_expr_add_parenthesis(struct ec_node *gen_node,
 381         struct ec_node *open, struct ec_node *close)
 382 {
 383         struct ec_node_expr *node = (struct ec_node_expr *)gen_node;
 384         struct ec_node **open_ops, **close_ops;
 385
 386         if (ec_node_check_type(gen_node, &ec_node_expr_type) < 0)
 387                 goto fail;
 388
 389         if (node == NULL || open == NULL || close == NULL) {
 390                 errno = EINVAL;
 391                 goto fail;
 392         }
 393
 394         open_ops = ec_realloc(node->open_ops,
 395                 (node->paren_len + 1) * sizeof(*node->open_ops));
 396         if (open_ops == NULL)
 397                 goto fail;
 398         close_ops = ec_realloc(node->close_ops,
 399                 (node->paren_len + 1) * sizeof(*node->close_ops));
 400         if (close_ops == NULL)
 401                 goto fail;
 402
 403         node->open_ops = open_ops;
 404         node->close_ops = close_ops;
 405         open_ops[node->paren_len] = open;
 406         close_ops[node->paren_len] = close;
 407         node->paren_len++;
 408         ec_node_expr_build(node);
 409
 410         return 0;
 411
 412 fail:
 413         ec_node_free(open);
 414         ec_node_free(close);
 415         return -1;
 416 }
 417
 418 enum expr_node_type {
 419         NONE,
 420         VAL,
 421         BIN_OP,
 422         PRE_OP,
 423         POST_OP,
 424         PAREN_OPEN,
 425         PAREN_CLOSE,
 426 };
 427
 428 static enum expr_node_type get_node_type(const struct ec_node *expr_gen_node,
 429         const struct ec_node *check)
 430 {
 431         struct ec_node_expr *expr_node = (struct ec_node_expr *)expr_gen_node;
 432         size_t i;
 433
 434         if (check == expr_node->val_node)
 435                 return VAL;
 436
 437         for (i = 0; i < expr_node->bin_ops_len; i++) {
 438                 if (check == expr_node->bin_ops[i])
 439                         return BIN_OP;
 440         }
 441         for (i = 0; i < expr_node->pre_ops_len; i++) {
 442                 if (check == expr_node->pre_ops[i])
 443                         return PRE_OP;
 444         }
 445         for (i = 0; i < expr_node->post_ops_len; i++) {
 446                 if (check == expr_node->post_ops[i])
 447                         return POST_OP;
 448         }
 449
 450         for (i = 0; i < expr_node->paren_len; i++) {
 451                 if (check == expr_node->open_ops[i])
 452                         return PAREN_OPEN;
 453         }
 454         for (i = 0; i < expr_node->paren_len; i++) {
 455                 if (check == expr_node->close_ops[i])
 456                         return PAREN_CLOSE;
 457         }
 458
 459         return NONE;
 460 }
 461
 462 struct result {
 463         bool has_val;
 464         void *val;
 465         const struct ec_parse *op;
 466         enum expr_node_type op_type;
 467 };
 468
 469 /* merge x and y results in x */
 470 static int merge_results(void *userctx,
 471         const struct ec_node_expr_eval_ops *ops,
 472         struct result *x, const struct result *y)
 473 {
 474         if (y->has_val == 0 && y->op == NULL)
 475                 return 0;
 476         if (x->has_val == 0 && x->op == NULL) {
 477                 *x = *y;
 478                 return 0;
 479         }
 480
 481         if (x->has_val && y->has_val && y->op != NULL) {
 482                 if (y->op_type == BIN_OP) {
 483                         if (ops->eval_bin_op(&x->val, userctx, x->val,
 484                                         y->op, y->val) < 0)
 485                                 return -1;
 486
 487                         return 0;
 488                 }
 489         }
 490
 491         if (x->has_val == 0 && x->op != NULL && y->has_val && y->op == NULL) {
 492                 if (x->op_type == PRE_OP) {
 493                         if (ops->eval_pre_op(&x->val, userctx, y->val,
 494                                                 x->op) < 0)
 495                                 return -1;
 496                         x->has_val = true;
 497                         x->op_type = NONE;
 498                         x->op = NULL;
 499                         return 0;
 500                 } else if (x->op_type == BIN_OP) {
 501                         x->val = y->val;
 502                         x->has_val = true;
 503                         return 0;
 504                 }
 505         }
 506
 507         if (x->has_val && x->op == NULL && y->has_val == 0 && y->op != NULL) {
 508                 if (ops->eval_post_op(&x->val, userctx, x->val, y->op) < 0)
 509                         return -1;
 510
 511                 return 0;
 512         }
 513
 514         assert(false); /* we should not get here */
 515         return -1;
 516 }
 517
 518 static int eval_expression(struct result *result,
 519         void *userctx,
 520         const struct ec_node_expr_eval_ops *ops,
 521         const struct ec_node *expr_gen_node,
 522         const struct ec_parse *parse)
 523
 524 {
 525         struct ec_parse *open = NULL, *close = NULL;
 526         struct result child_result;
 527         struct ec_parse *child;
 528         enum expr_node_type type;
 529
 530         memset(result, 0, sizeof(*result));
 531         memset(&child_result, 0, sizeof(child_result));
 532
 533         type = get_node_type(expr_gen_node, ec_parse_get_node(parse));
 534         if (type == VAL) {
 535                 if (ops->eval_var(&result->val, userctx, parse) < 0)
 536                         goto fail;
 537                 result->has_val = 1;
 538         } else if (type == PRE_OP || type == POST_OP || type == BIN_OP) {
 539                 result->op = parse;
 540                 result->op_type = type;
 541         }
 542
 543         EC_PARSE_FOREACH_CHILD(child, parse) {
 544
 545                 type = get_node_type(expr_gen_node, ec_parse_get_node(child));
 546                 if (type == PAREN_OPEN) {
 547                         open = child;
 548                         continue;
 549                 } else if (type == PAREN_CLOSE) {
 550                         close = child;
 551                         continue;
 552                 }
 553
 554                 if (eval_expression(&child_result, userctx, ops,
 555                         expr_gen_node, child) < 0)
 556                         goto fail;
 557
 558                 if (merge_results(userctx, ops, result, &child_result) < 0)
 559                         goto fail;
 560
 561                 memset(&child_result, 0, sizeof(child_result));
 562         }
 563
 564         if (open != NULL && close != NULL) {
 565                 if (ops->eval_parenthesis(&result->val, userctx, open, close,
 566                         result->val) < 0)
 567                         goto fail;
 568         }
 569
 570         return 0;
 571
 572 fail:
 573         if (result->has_val)
 574                 ops->eval_free(result->val, userctx);
 575         if (child_result.has_val)
 576                 ops->eval_free(child_result.val, userctx);
 577         memset(result, 0, sizeof(*result));
 578
 579         return -1;
 580 }
 581
 582 int ec_node_expr_eval(void **user_result, const struct ec_node *node,
 583         struct ec_parse *parse, const struct ec_node_expr_eval_ops *ops,
 584         void *userctx)
 585 {
 586         struct result result;
 587
 588         if (ops == NULL || ops->eval_var == NULL || ops->eval_pre_op == NULL ||
 589                         ops->eval_post_op == NULL || ops->eval_bin_op == NULL ||
 590                         ops->eval_parenthesis == NULL ||
 591                         ops->eval_free == NULL) {
 592                 errno = EINVAL;
 593                 return -1;
 594         }
 595
 596         if (ec_node_check_type(node, &ec_node_expr_type) < 0)
 597                 return -1;
 598
 599         if (!ec_parse_matches(parse)) {
 600                 errno = EINVAL;
 601                 return -1;
 602         }
 603
 604         if (eval_expression(&result, userctx, ops, node, parse) < 0)
 605                 return -1;
 606
 607         assert(result.has_val);
 608         assert(result.op == NULL);
 609         *user_result = result.val;
 610
 611         return 0;
 612 }
 613
 614 /* the test case is in a separate file ecoli_node_expr_test.c */