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