lib/ecoli_tk_expr.c

   1 /*
   2  * Copyright (c) 2016-2017, Olivier MATZ <zer0@droids-corp.org>
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are met:
   6  *
   7  *     * Redistributions of source code must retain the above copyright
   8  *       notice, this list of conditions and the following disclaimer.
   9  *     * Redistributions in binary form must reproduce the above copyright
  10  *       notice, this list of conditions and the following disclaimer in the
  11  *       documentation and/or other materials provided with the distribution.
  12  *     * Neither the name of the University of California, Berkeley nor the
  13  *       names of its contributors may be used to endorse or promote products
  14  *       derived from this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND ANY
  17  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  18  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  19  * DISCLAIMED. IN NO EVENT SHALL THE REGENTS AND CONTRIBUTORS BE LIABLE FOR ANY
  20  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  21  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  22  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  23  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  25  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27
  28 #include <stdio.h>
  29 #include <stdlib.h>
  30 #include <string.h>
  31 #include <assert.h>
  32 #include <stdarg.h>
  33 #include <limits.h>
  34 #include <errno.h>
  35
  36 #include <ecoli_malloc.h>
  37 #include <ecoli_log.h>
  38 #include <ecoli_test.h>
  39 #include <ecoli_strvec.h>
  40 #include <ecoli_tk.h>
  41 #include <ecoli_tk_str.h>
  42 #include <ecoli_tk_int.h>
  43 #include <ecoli_tk_seq.h>
  44 #include <ecoli_tk_many.h>
  45 #include <ecoli_tk_or.h>
  46 #include <ecoli_tk_expr.h>
  47 #include <ecoli_tk_bypass.h>
  48
  49 struct ec_tk_expr {
  50         struct ec_tk gen;
  51
  52         /* the built node */
  53         struct ec_tk *child;
  54
  55         /* the configuration nodes */
  56         struct ec_tk *val_tk;
  57         struct ec_tk **bin_ops;
  58         unsigned int bin_ops_len;
  59         struct ec_tk **pre_ops;
  60         unsigned int pre_ops_len;
  61         struct ec_tk **post_ops;
  62         unsigned int post_ops_len;
  63         struct ec_tk **open_ops;
  64         struct ec_tk **close_ops;
  65         unsigned int paren_len;
  66 };
  67
  68 static struct ec_parsed_tk *ec_tk_expr_parse(const struct ec_tk *gen_tk,
  69         const struct ec_strvec *strvec)
  70 {
  71         struct ec_tk_expr *tk = (struct ec_tk_expr *)gen_tk;
  72
  73         return ec_tk_parse_tokens(tk->child, strvec);
  74 }
  75
  76 static struct ec_completed_tk *ec_tk_expr_complete(const struct ec_tk *gen_tk,
  77         const struct ec_strvec *strvec)
  78 {
  79         struct ec_tk_expr *tk = (struct ec_tk_expr *)gen_tk;
  80
  81         return ec_tk_complete_tokens(tk->child, strvec);
  82 }
  83
  84 static void ec_tk_expr_free_priv(struct ec_tk *gen_tk)
  85 {
  86         struct ec_tk_expr *tk = (struct ec_tk_expr *)gen_tk;
  87         struct ec_tk *final;
  88         unsigned int i;
  89
  90         ec_log(EC_LOG_DEBUG, "free %p %p %p\n", tk, tk->child, tk->val_tk);
  91         ec_tk_free(tk->val_tk);
  92
  93         for (i = 0; i < tk->bin_ops_len; i++)
  94                 ec_tk_free(tk->bin_ops[i]);
  95         ec_free(tk->bin_ops);
  96         for (i = 0; i < tk->pre_ops_len; i++)
  97                 ec_tk_free(tk->pre_ops[i]);
  98         ec_free(tk->pre_ops);
  99         for (i = 0; i < tk->post_ops_len; i++)
 100                 ec_tk_free(tk->post_ops[i]);
 101         ec_free(tk->post_ops);
 102         for (i = 0; i < tk->paren_len; i++) {
 103                 ec_tk_free(tk->open_ops[i]);
 104                 ec_tk_free(tk->close_ops[i]);
 105         }
 106         ec_free(tk->open_ops);
 107         ec_free(tk->close_ops);
 108
 109         /* break the graph loop, and free the nodes */
 110         if (tk->child != NULL) {
 111                 final = ec_tk_bypass_pop(tk->child);
 112                 ec_tk_free(tk->child);
 113                 ec_tk_free(final);
 114         }
 115 }
 116
 117 static int ec_tk_expr_build(struct ec_tk *gen_tk)
 118 {
 119         struct ec_tk_expr *tk = (struct ec_tk_expr *)gen_tk;
 120         struct ec_tk *term = NULL, *expr = NULL, *next = NULL,
 121                 *pre_op = NULL, *post_op = NULL,
 122                 *post = NULL, *final = NULL;
 123         unsigned int i;
 124         int ret;
 125
 126         if (tk->val_tk == NULL)
 127                 return -EINVAL;
 128         if (tk->bin_ops_len == 0 && tk->pre_ops_len == 0 &&
 129                         tk->post_ops_len == 0)
 130                 return -EINVAL;
 131
 132         /* create the object, we will initialize it later: this is
 133          * needed because we have a circular dependency */
 134         ret = -ENOMEM;
 135         expr = ec_tk_bypass_empty("expr");
 136         if (expr == NULL)
 137                 goto fail;
 138
 139         /* prefix unary operators */
 140         pre_op = ec_tk_or("pre-op");
 141         if (pre_op == NULL)
 142                 goto fail;
 143         for (i = 0; i < tk->pre_ops_len; i++) {
 144                 if (ec_tk_or_add(pre_op, ec_tk_clone(tk->pre_ops[i])) < 0)
 145                         goto fail;
 146         }
 147
 148         /* suffix unary operators */
 149         post_op = ec_tk_or("post-op");
 150         if (post_op == NULL)
 151                 goto fail;
 152         for (i = 0; i < tk->post_ops_len; i++) {
 153                 if (ec_tk_or_add(post_op, ec_tk_clone(tk->post_ops[i])) < 0)
 154                         goto fail;
 155         }
 156
 157         term = ec_tk_or("term");
 158         if (term == NULL)
 159                 goto fail;
 160         if (ec_tk_or_add(term, ec_tk_clone(tk->val_tk)) < 0)
 161                 goto fail;
 162         if (ec_tk_or_add(term,
 163                 EC_TK_SEQ(NULL,
 164                         ec_tk_clone(pre_op),
 165                         ec_tk_clone(expr))) < 0)
 166                 goto fail;
 167         for (i = 0; i < tk->paren_len; i++) {
 168                 if (ec_tk_or_add(term, EC_TK_SEQ(NULL,
 169                                         ec_tk_clone(tk->open_ops[i]),
 170                                         ec_tk_clone(expr),
 171                                         ec_tk_clone(tk->close_ops[i]))) < 0)
 172                         goto fail;
 173         }
 174
 175         for (i = 0; i < tk->bin_ops_len; i++) {
 176                 next = EC_TK_SEQ("next",
 177                         ec_tk_clone(term),
 178                         ec_tk_many(NULL,
 179                                 EC_TK_SEQ(NULL,
 180                                         ec_tk_clone(tk->bin_ops[i]),
 181                                         ec_tk_clone(term)
 182                                 ),
 183                                 0, 0
 184                         )
 185                 );
 186                 ec_tk_free(term);
 187                 term = next;
 188                 if (term == NULL)
 189                         goto fail;
 190         }
 191
 192         final = EC_TK_SEQ("final",
 193                 ec_tk_clone(term),
 194                 ec_tk_many(NULL, ec_tk_clone(post_op), 0, 0)
 195         );
 196         if (final == NULL)
 197                 goto fail;
 198
 199         /* free the initial references */
 200         ec_tk_free(pre_op);
 201         pre_op = NULL;
 202         ec_tk_free(post_op);
 203         post_op = NULL;
 204         ec_tk_free(term);
 205         term = NULL;
 206         ec_tk_free(post);
 207         post = NULL;
 208
 209         if (ec_tk_bypass_set(expr, ec_tk_clone(final)) < 0)
 210                 goto fail;
 211
 212         ec_tk_free(final);
 213         final = NULL;
 214
 215         tk->child = expr;
 216
 217         return 0;
 218
 219 fail:
 220         ec_tk_free(term);
 221         ec_tk_free(expr);
 222         ec_tk_free(pre_op);
 223         ec_tk_free(post_op);
 224         ec_tk_free(post);
 225         ec_tk_free(final);
 226
 227         return ret;
 228 }
 229
 230 static struct ec_tk_ops ec_tk_expr_ops = {
 231         .typename = "expr",
 232         .build = ec_tk_expr_build,
 233         .parse = ec_tk_expr_parse,
 234         .complete = ec_tk_expr_complete,
 235         .free_priv = ec_tk_expr_free_priv,
 236 };
 237
 238 struct ec_tk *ec_tk_expr(const char *id)
 239 {
 240         struct ec_tk_expr *tk = NULL;
 241         struct ec_tk *gen_tk = NULL;
 242
 243         gen_tk = ec_tk_new(id, &ec_tk_expr_ops, sizeof(*tk));
 244         if (gen_tk == NULL)
 245                 return NULL;
 246         tk = (struct ec_tk_expr *)gen_tk;
 247
 248         return gen_tk;
 249 }
 250
 251 int ec_tk_expr_set_val_tk(struct ec_tk *gen_tk, struct ec_tk *val_tk)
 252 {
 253         struct ec_tk_expr *tk = (struct ec_tk_expr *)gen_tk;
 254         int ret;
 255
 256         ret = -EINVAL;
 257         if (val_tk == NULL)
 258                 goto fail;
 259         ret = -EPERM;
 260         if (gen_tk->flags & EC_TK_F_BUILT)
 261                 goto fail;
 262         ret = -EEXIST;
 263         if (tk->val_tk != NULL)
 264                 goto fail;
 265
 266         tk->val_tk = val_tk;
 267         gen_tk->flags &= ~EC_TK_F_BUILT;
 268
 269         return 0;
 270
 271 fail:
 272         ec_tk_free(val_tk);
 273         return ret;
 274 }
 275
 276 /* add a binary operator */
 277 int ec_tk_expr_add_bin_op(struct ec_tk *gen_tk, struct ec_tk *op)
 278 {
 279         struct ec_tk_expr *tk = (struct ec_tk_expr *)gen_tk;
 280         struct ec_tk **bin_ops;
 281         int ret;
 282
 283         // XXX check tk type
 284
 285         ret = -EINVAL;
 286         if (tk == NULL || op == NULL)
 287                 goto fail;
 288         ret = -EPERM;
 289         if (gen_tk->flags & EC_TK_F_BUILT)
 290                 goto fail;
 291
 292         ret = -ENOMEM;
 293         bin_ops = ec_realloc(tk->bin_ops,
 294                 (tk->bin_ops_len + 1) * sizeof(*tk->bin_ops));
 295         if (bin_ops == NULL)
 296                 goto fail;;
 297
 298         tk->bin_ops = bin_ops;
 299         bin_ops[tk->bin_ops_len] = op;
 300         tk->bin_ops_len++;
 301         gen_tk->flags &= ~EC_TK_F_BUILT;
 302
 303         return 0;
 304
 305 fail:
 306         ec_tk_free(op);
 307         return ret;
 308 }
 309
 310 /* add a unary pre-operator */
 311 int ec_tk_expr_add_pre_op(struct ec_tk *gen_tk, struct ec_tk *op)
 312 {
 313         struct ec_tk_expr *tk = (struct ec_tk_expr *)gen_tk;
 314         struct ec_tk **pre_ops;
 315         int ret;
 316
 317         // XXX check tk type
 318
 319         ret = -EINVAL;
 320         if (tk == NULL || op == NULL)
 321                 goto fail;
 322         ret = -EPERM;
 323         if (gen_tk->flags & EC_TK_F_BUILT)
 324                 goto fail;
 325
 326         ret = -ENOMEM;
 327         pre_ops = ec_realloc(tk->pre_ops,
 328                 (tk->pre_ops_len + 1) * sizeof(*tk->pre_ops));
 329         if (pre_ops == NULL)
 330                 goto fail;
 331
 332         tk->pre_ops = pre_ops;
 333         pre_ops[tk->pre_ops_len] = op;
 334         tk->pre_ops_len++;
 335         gen_tk->flags &= ~EC_TK_F_BUILT;
 336
 337         return 0;
 338
 339 fail:
 340         ec_tk_free(op);
 341         return ret;
 342 }
 343
 344 /* add a unary post-operator */
 345 int ec_tk_expr_add_post_op(struct ec_tk *gen_tk, struct ec_tk *op)
 346 {
 347         struct ec_tk_expr *tk = (struct ec_tk_expr *)gen_tk;
 348         struct ec_tk **post_ops;
 349         int ret;
 350
 351         // XXX check tk type
 352
 353         ret = -EINVAL;
 354         if (tk == NULL || op == NULL)
 355                 goto fail;
 356         ret = -EPERM;
 357         if (gen_tk->flags & EC_TK_F_BUILT)
 358                 goto fail;
 359
 360         ret = -ENOMEM;
 361         post_ops = ec_realloc(tk->post_ops,
 362                 (tk->post_ops_len + 1) * sizeof(*tk->post_ops));
 363         if (post_ops == NULL)
 364                 goto fail;
 365
 366         tk->post_ops = post_ops;
 367         post_ops[tk->post_ops_len] = op;
 368         tk->post_ops_len++;
 369         gen_tk->flags &= ~EC_TK_F_BUILT;
 370
 371         return 0;
 372
 373 fail:
 374         ec_tk_free(op);
 375         return ret;
 376 }
 377
 378 /* add parenthesis symbols */
 379 int ec_tk_expr_add_parenthesis(struct ec_tk *gen_tk,
 380         struct ec_tk *open, struct ec_tk *close)
 381 {
 382         struct ec_tk_expr *tk = (struct ec_tk_expr *)gen_tk;
 383         struct ec_tk **open_ops, **close_ops;
 384         int ret;
 385
 386         // XXX check tk type
 387
 388         ret = -EINVAL;
 389         if (tk == NULL || open == NULL || close == NULL)
 390                 goto fail;
 391         ret = -EPERM;
 392         if (gen_tk->flags & EC_TK_F_BUILT)
 393                 goto fail;;
 394
 395         ret = -ENOMEM;
 396         open_ops = ec_realloc(tk->open_ops,
 397                 (tk->paren_len + 1) * sizeof(*tk->open_ops));
 398         if (open_ops == NULL)
 399                 goto fail;
 400         close_ops = ec_realloc(tk->close_ops,
 401                 (tk->paren_len + 1) * sizeof(*tk->close_ops));
 402         if (close_ops == NULL)
 403                 goto fail;
 404
 405         tk->open_ops = open_ops;
 406         tk->close_ops = close_ops;
 407         open_ops[tk->paren_len] = open;
 408         close_ops[tk->paren_len] = close;
 409         tk->paren_len++;
 410         gen_tk->flags &= ~EC_TK_F_BUILT;
 411
 412         return 0;
 413
 414 fail:
 415         ec_tk_free(open);
 416         ec_tk_free(close);
 417         return ret;
 418 }
 419
 420 static int ec_tk_expr_testcase_manual(void)
 421 {
 422         struct ec_tk *term = NULL, *factor = NULL, *expr = NULL, *val = NULL,
 423                 *pre_op = NULL, *post_op = NULL, *post = NULL, *final = NULL;
 424         int ret = 0;
 425
 426         // XXX check all APIs: pointers are "moved", they are freed by
 427         // the callee
 428
 429         /* Example that generates an expression "manually". We keep it
 430          * here for reference. */
 431
 432         /* create the object, we will initialize it later: this is
 433          * needed because we have a circular dependency */
 434         expr = ec_tk_bypass_empty("expr");
 435         if (expr == NULL)
 436                 return -1;
 437
 438         /* reverse bits */
 439         pre_op = EC_TK_OR("pre-op",
 440                 ec_tk_str(NULL, "~")
 441         );
 442
 443         /* factorial */
 444         post_op = EC_TK_OR("post-op",
 445                 ec_tk_str(NULL, "!")
 446         );
 447
 448         val = ec_tk_int("val", 0, UCHAR_MAX, 0);
 449         term = EC_TK_OR("term",
 450                 val,
 451                 EC_TK_SEQ(NULL,
 452                         ec_tk_str(NULL, "("),
 453                         ec_tk_clone(expr),
 454                         ec_tk_str(NULL, ")")
 455                 ),
 456                 EC_TK_SEQ(NULL,
 457                         ec_tk_clone(pre_op),
 458                         ec_tk_clone(expr)
 459                 )
 460         );
 461         val = NULL;
 462
 463         factor = EC_TK_SEQ("factor",
 464                 ec_tk_clone(term),
 465                 ec_tk_many(NULL,
 466                         EC_TK_SEQ(NULL,
 467                                 ec_tk_str(NULL, "+"),
 468                                 ec_tk_clone(term)
 469                         ),
 470                         0, 0
 471                 )
 472         );
 473
 474         post = EC_TK_SEQ("post",
 475                 ec_tk_clone(factor),
 476                 ec_tk_many(NULL,
 477                         EC_TK_SEQ(NULL,
 478                                 ec_tk_str(NULL, "*"),
 479                                 ec_tk_clone(factor)
 480                         ),
 481                         0, 0
 482                 )
 483         );
 484
 485         final = EC_TK_SEQ("final",
 486                 ec_tk_clone(post),
 487                 ec_tk_many(NULL, ec_tk_clone(post_op), 0, 0)
 488         );
 489
 490         /* free the initial references */
 491         ec_tk_free(pre_op);
 492         pre_op = NULL;
 493         ec_tk_free(post_op);
 494         post_op = NULL;
 495         ec_tk_free(term);
 496         term = NULL;
 497         ec_tk_free(factor);
 498         factor = NULL;
 499         ec_tk_free(post);
 500         post = NULL;
 501
 502         if (ec_tk_bypass_set(expr, ec_tk_clone(final)) < 0)
 503                 goto fail;
 504
 505         ec_tk_free(final);
 506         final = NULL;
 507
 508         ret |= EC_TEST_CHECK_TK_PARSE(expr, 1, "1");
 509         ret |= EC_TEST_CHECK_TK_PARSE(expr, 1, "1", "*");
 510         ret |= EC_TEST_CHECK_TK_PARSE(expr, 3, "1", "*", "1");
 511         ret |= EC_TEST_CHECK_TK_PARSE(expr, 3, "1", "+", "1");
 512         ret |= EC_TEST_CHECK_TK_PARSE(expr, 5, "1", "*", "1", "+", "1");
 513         ret |= EC_TEST_CHECK_TK_PARSE(
 514                 expr, 10, "~", "(", "1", "*", "(", "1", "+", "1", ")", ")");
 515         ret |= EC_TEST_CHECK_TK_PARSE(expr, 4, "1", "+", "~", "1");
 516
 517         final = ec_tk_bypass_pop(expr);
 518         ec_tk_free(expr);
 519         ec_tk_free(final);
 520
 521         return ret;
 522
 523 fail:
 524         ec_tk_free(term);
 525         ec_tk_free(factor);
 526         ec_tk_free(expr);
 527         ec_tk_free(val);
 528         ec_tk_free(pre_op);
 529         ec_tk_free(post_op);
 530         ec_tk_free(post);
 531         ec_tk_free(final);
 532         return 0;
 533 }
 534
 535 static int ec_tk_expr_testcase(void)
 536 {
 537         struct ec_tk *tk;
 538         int ret;
 539
 540         ret = ec_tk_expr_testcase_manual();
 541         if (ret < 0)
 542                 return ret;
 543
 544         tk = ec_tk_expr(NULL);
 545         if (tk == NULL)
 546                 return -1;
 547
 548         ec_tk_expr_set_val_tk(tk, ec_tk_int(NULL, 0, UCHAR_MAX, 0));
 549         ec_tk_expr_add_bin_op(tk, ec_tk_str(NULL, "+"));
 550         ec_tk_expr_add_bin_op(tk, ec_tk_str(NULL, "*"));
 551         ec_tk_expr_add_pre_op(tk, ec_tk_str(NULL, "~"));
 552         ec_tk_expr_add_pre_op(tk, ec_tk_str(NULL, "!"));
 553         ec_tk_expr_add_parenthesis(tk, ec_tk_str(NULL, "("),
 554                 ec_tk_str(NULL, ")"));
 555         ret |= EC_TEST_CHECK_TK_PARSE(tk, 1, "1");
 556         ret |= EC_TEST_CHECK_TK_PARSE(tk, 1, "1", "*");
 557         ret |= EC_TEST_CHECK_TK_PARSE(tk, 3, "1", "*", "1");
 558         ret |= EC_TEST_CHECK_TK_PARSE(tk, 3, "1", "+", "1");
 559         ret |= EC_TEST_CHECK_TK_PARSE(tk, 5, "1", "*", "1", "+", "1");
 560         ret |= EC_TEST_CHECK_TK_PARSE(
 561                 tk, 10, "~", "(", "1", "*", "(", "1", "+", "1", ")", ")");
 562         ret |= EC_TEST_CHECK_TK_PARSE(tk, 4, "1", "+", "~", "1");
 563         ec_tk_free(tk);
 564
 565         return ret;
 566 }
 567
 568 static struct ec_test ec_tk_expr_test = {
 569         .name = "tk_expr",
 570         .test = ec_tk_expr_testcase,
 571 };
 572
 573 EC_REGISTER_TEST(ec_tk_expr_test);