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