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