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_weakref.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         unsigned int i;
  88
  89         ec_log(EC_LOG_DEBUG, "free %p %p %p\n", tk, tk->child, tk->val_tk);
  90         ec_tk_free(tk->val_tk);
  91
  92         for (i = 0; i < tk->bin_ops_len; i++)
  93                 ec_tk_free(tk->bin_ops[i]);
  94         ec_free(tk->bin_ops);
  95         for (i = 0; i < tk->pre_ops_len; i++)
  96                 ec_tk_free(tk->pre_ops[i]);
  97         ec_free(tk->pre_ops);
  98         for (i = 0; i < tk->post_ops_len; i++)
  99                 ec_tk_free(tk->post_ops[i]);
 100         ec_free(tk->post_ops);
 101         for (i = 0; i < tk->paren_len; i++) {
 102                 ec_tk_free(tk->open_ops[i]);
 103                 ec_tk_free(tk->close_ops[i]);
 104         }
 105         ec_free(tk->open_ops);
 106         ec_free(tk->close_ops);
 107
 108         ec_tk_free(tk->child);
 109 }
 110
 111 static int ec_tk_expr_build(struct ec_tk *gen_tk)
 112 {
 113         struct ec_tk_expr *tk = (struct ec_tk_expr *)gen_tk;
 114         struct ec_tk *term = NULL, *expr = NULL, *next = NULL,
 115                 *pre_op = NULL, *post_op = NULL,
 116                 *post = NULL, *weak = NULL;
 117         unsigned int i;
 118         int ret;
 119
 120         if (tk->val_tk == NULL)
 121                 return -EINVAL;
 122         if (tk->bin_ops_len == 0 && tk->pre_ops_len == 0 &&
 123                         tk->post_ops_len == 0)
 124                 return -EINVAL;
 125
 126         /* create the object, we will initialize it later: this is
 127          * needed because we have a circular dependency */
 128         ret = -ENOMEM;
 129         weak = ec_tk_weakref_empty("weak");
 130         if (weak == NULL)
 131                 return -1;
 132
 133         /* prefix unary operators */
 134         pre_op = ec_tk_or("pre-op");
 135         if (pre_op == NULL)
 136                 goto fail;
 137         for (i = 0; i < tk->pre_ops_len; i++) {
 138                 if (ec_tk_or_add(pre_op, ec_tk_clone(tk->pre_ops[i])) < 0)
 139                         goto fail;
 140         }
 141
 142         /* suffix unary operators */
 143         post_op = ec_tk_or("post-op");
 144         if (post_op == NULL)
 145                 goto fail;
 146         for (i = 0; i < tk->post_ops_len; i++) {
 147                 if (ec_tk_or_add(post_op, ec_tk_clone(tk->post_ops[i])) < 0)
 148                         goto fail;
 149         }
 150
 151         term = ec_tk_or("term");
 152         if (term == NULL)
 153                 goto fail;
 154         if (ec_tk_or_add(term, ec_tk_clone(tk->val_tk)) < 0)
 155                 goto fail;
 156         if (ec_tk_or_add(term,
 157                 EC_TK_SEQ(NULL,
 158                         ec_tk_clone(pre_op),
 159                         ec_tk_clone(weak))) < 0)
 160                 goto fail;
 161         for (i = 0; i < tk->paren_len; i++) {
 162                 if (ec_tk_or_add(term, EC_TK_SEQ(NULL,
 163                                         ec_tk_clone(tk->open_ops[i]),
 164                                         ec_tk_clone(weak),
 165                                         ec_tk_clone(tk->close_ops[i]))) < 0)
 166                         goto fail;
 167         }
 168
 169         for (i = 0; i < tk->bin_ops_len; i++) {
 170                 next = EC_TK_SEQ("next",
 171                         ec_tk_clone(term),
 172                         ec_tk_many(NULL,
 173                                 EC_TK_SEQ(NULL,
 174                                         ec_tk_clone(tk->bin_ops[i]),
 175                                         ec_tk_clone(term)
 176                                 ),
 177                                 0, 0
 178                         )
 179                 );
 180                 ec_tk_free(term);
 181                 term = next;
 182                 if (term == NULL)
 183                         goto fail;
 184         }
 185
 186         expr = EC_TK_SEQ("expr",
 187                 ec_tk_clone(term),
 188                 ec_tk_many(NULL, ec_tk_clone(post_op), 0, 0)
 189         );
 190         if (expr == NULL)
 191                 goto fail;
 192
 193         /* free the initial references */
 194         ec_tk_free(pre_op);
 195         pre_op = NULL;
 196         ec_tk_free(post_op);
 197         post_op = NULL;
 198         ec_tk_free(term);
 199         term = NULL;
 200         ec_tk_free(post);
 201         post = NULL;
 202
 203         /* no need to clone here, the node is not consumed */
 204         if (ec_tk_weakref_set(weak, expr) < 0)
 205                 goto fail;
 206         ec_tk_free(weak);
 207         weak = NULL;
 208
 209         tk->child = expr;
 210
 211         return 0;
 212
 213 fail:
 214         ec_tk_free(term);
 215         ec_tk_free(expr);
 216         ec_tk_free(pre_op);
 217         ec_tk_free(post_op);
 218         ec_tk_free(post);
 219         ec_tk_free(weak);
 220
 221         return ret;
 222 }
 223
 224 static struct ec_tk_ops ec_tk_expr_ops = {
 225         .typename = "expr",
 226         .build = ec_tk_expr_build,
 227         .parse = ec_tk_expr_parse,
 228         .complete = ec_tk_expr_complete,
 229         .free_priv = ec_tk_expr_free_priv,
 230 };
 231
 232 struct ec_tk *ec_tk_expr(const char *id)
 233 {
 234         struct ec_tk_expr *tk = NULL;
 235         struct ec_tk *gen_tk = NULL;
 236
 237         gen_tk = ec_tk_new(id, &ec_tk_expr_ops, sizeof(*tk));
 238         if (gen_tk == NULL)
 239                 return NULL;
 240         tk = (struct ec_tk_expr *)gen_tk;
 241
 242         return gen_tk;
 243 }
 244
 245 int ec_tk_expr_set_val_tk(struct ec_tk *gen_tk, struct ec_tk *val_tk)
 246 {
 247         struct ec_tk_expr *tk = (struct ec_tk_expr *)gen_tk;
 248         int ret;
 249
 250         ret = -EINVAL;
 251         if (val_tk == NULL)
 252                 goto fail;
 253         ret = -EPERM;
 254         if (gen_tk->flags & EC_TK_F_BUILT)
 255                 goto fail;
 256         ret = -EEXIST;
 257         if (tk->val_tk != NULL)
 258                 goto fail;
 259
 260         tk->val_tk = val_tk;
 261         gen_tk->flags &= ~EC_TK_F_BUILT;
 262
 263         return 0;
 264
 265 fail:
 266         ec_tk_free(val_tk);
 267         return ret;
 268 }
 269
 270 /* add a binary operator */
 271 int ec_tk_expr_add_bin_op(struct ec_tk *gen_tk, struct ec_tk *op)
 272 {
 273         struct ec_tk_expr *tk = (struct ec_tk_expr *)gen_tk;
 274         struct ec_tk **bin_ops;
 275         int ret;
 276
 277         // XXX check tk type
 278
 279         ret = -EINVAL;
 280         if (tk == NULL || op == NULL)
 281                 goto fail;
 282         ret = -EPERM;
 283         if (gen_tk->flags & EC_TK_F_BUILT)
 284                 goto fail;
 285
 286         ret = -ENOMEM;
 287         bin_ops = ec_realloc(tk->bin_ops,
 288                 (tk->bin_ops_len + 1) * sizeof(*tk->bin_ops));
 289         if (bin_ops == NULL)
 290                 goto fail;;
 291
 292         tk->bin_ops = bin_ops;
 293         bin_ops[tk->bin_ops_len] = op;
 294         tk->bin_ops_len++;
 295         gen_tk->flags &= ~EC_TK_F_BUILT;
 296
 297         return 0;
 298
 299 fail:
 300         ec_tk_free(op);
 301         return ret;
 302 }
 303
 304 /* add a unary pre-operator */
 305 int ec_tk_expr_add_pre_op(struct ec_tk *gen_tk, struct ec_tk *op)
 306 {
 307         struct ec_tk_expr *tk = (struct ec_tk_expr *)gen_tk;
 308         struct ec_tk **pre_ops;
 309         int ret;
 310
 311         // XXX check tk type
 312
 313         ret = -EINVAL;
 314         if (tk == NULL || op == NULL)
 315                 goto fail;
 316         ret = -EPERM;
 317         if (gen_tk->flags & EC_TK_F_BUILT)
 318                 goto fail;
 319
 320         ret = -ENOMEM;
 321         pre_ops = ec_realloc(tk->pre_ops,
 322                 (tk->pre_ops_len + 1) * sizeof(*tk->pre_ops));
 323         if (pre_ops == NULL)
 324                 goto fail;
 325
 326         tk->pre_ops = pre_ops;
 327         pre_ops[tk->pre_ops_len] = op;
 328         tk->pre_ops_len++;
 329         gen_tk->flags &= ~EC_TK_F_BUILT;
 330
 331         return 0;
 332
 333 fail:
 334         ec_tk_free(op);
 335         return ret;
 336 }
 337
 338 /* add a unary post-operator */
 339 int ec_tk_expr_add_post_op(struct ec_tk *gen_tk, struct ec_tk *op)
 340 {
 341         struct ec_tk_expr *tk = (struct ec_tk_expr *)gen_tk;
 342         struct ec_tk **post_ops;
 343         int ret;
 344
 345         // XXX check tk type
 346
 347         ret = -EINVAL;
 348         if (tk == NULL || op == NULL)
 349                 goto fail;
 350         ret = -EPERM;
 351         if (gen_tk->flags & EC_TK_F_BUILT)
 352                 goto fail;
 353
 354         ret = -ENOMEM;
 355         post_ops = ec_realloc(tk->post_ops,
 356                 (tk->post_ops_len + 1) * sizeof(*tk->post_ops));
 357         if (post_ops == NULL)
 358                 goto fail;
 359
 360         tk->post_ops = post_ops;
 361         post_ops[tk->post_ops_len] = op;
 362         tk->post_ops_len++;
 363         gen_tk->flags &= ~EC_TK_F_BUILT;
 364
 365         return 0;
 366
 367 fail:
 368         ec_tk_free(op);
 369         return ret;
 370 }
 371
 372 /* add parenthesis symbols */
 373 int ec_tk_expr_add_parenthesis(struct ec_tk *gen_tk,
 374         struct ec_tk *open, struct ec_tk *close)
 375 {
 376         struct ec_tk_expr *tk = (struct ec_tk_expr *)gen_tk;
 377         struct ec_tk **open_ops, **close_ops;
 378         int ret;
 379
 380         // XXX check tk type
 381
 382         ret = -EINVAL;
 383         if (tk == NULL || open == NULL || close == NULL)
 384                 goto fail;
 385         ret = -EPERM;
 386         if (gen_tk->flags & EC_TK_F_BUILT)
 387                 goto fail;;
 388
 389         ret = -ENOMEM;
 390         open_ops = ec_realloc(tk->open_ops,
 391                 (tk->paren_len + 1) * sizeof(*tk->open_ops));
 392         if (open_ops == NULL)
 393                 goto fail;
 394         close_ops = ec_realloc(tk->close_ops,
 395                 (tk->paren_len + 1) * sizeof(*tk->close_ops));
 396         if (close_ops == NULL)
 397                 goto fail;
 398
 399         tk->open_ops = open_ops;
 400         tk->close_ops = close_ops;
 401         open_ops[tk->paren_len] = open;
 402         close_ops[tk->paren_len] = close;
 403         tk->paren_len++;
 404         gen_tk->flags &= ~EC_TK_F_BUILT;
 405
 406         return 0;
 407
 408 fail:
 409         ec_tk_free(open);
 410         ec_tk_free(close);
 411         return ret;
 412 }
 413
 414 static int ec_tk_expr_testcase_manual(void)
 415 {
 416         struct ec_tk *term = NULL, *factor = NULL, *expr = NULL, *val = NULL,
 417                 *pre_op = NULL, *post_op = NULL, *post = NULL, *weak = NULL;
 418         int ret = 0;
 419
 420         // XXX check all APIs: pointers are "moved", they are freed by
 421         // the callee
 422
 423         /* Example that generates an expression "manually". We keep it
 424          * here for reference. */
 425
 426         weak = ec_tk_weakref_empty("weak");
 427         if (weak == NULL)
 428                 return -1;
 429
 430         /* reverse bits */
 431         pre_op = EC_TK_OR("pre-op",
 432                 ec_tk_str(NULL, "~")
 433         );
 434
 435         /* factorial */
 436         post_op = EC_TK_OR("post-op",
 437                 ec_tk_str(NULL, "!")
 438         );
 439
 440         val = ec_tk_int("val", 0, UCHAR_MAX, 0);
 441         term = EC_TK_OR("term",
 442                 val,
 443                 EC_TK_SEQ(NULL,
 444                         ec_tk_str(NULL, "("),
 445                         ec_tk_clone(weak),
 446                         ec_tk_str(NULL, ")")
 447                 ),
 448                 EC_TK_SEQ(NULL,
 449                         ec_tk_clone(pre_op),
 450                         ec_tk_clone(weak)
 451                 )
 452         );
 453         val = NULL;
 454
 455         factor = EC_TK_SEQ("factor",
 456                 ec_tk_clone(term),
 457                 ec_tk_many(NULL,
 458                         EC_TK_SEQ(NULL,
 459                                 ec_tk_str(NULL, "+"),
 460                                 ec_tk_clone(term)
 461                         ),
 462                         0, 0
 463                 )
 464         );
 465
 466         post = EC_TK_SEQ("post",
 467                 ec_tk_clone(factor),
 468                 ec_tk_many(NULL,
 469                         EC_TK_SEQ(NULL,
 470                                 ec_tk_str(NULL, "*"),
 471                                 ec_tk_clone(factor)
 472                         ),
 473                         0, 0
 474                 )
 475         );
 476
 477         expr = EC_TK_SEQ("expr",
 478                 ec_tk_clone(post),
 479                 ec_tk_many(NULL, ec_tk_clone(post_op), 0, 0)
 480         );
 481
 482         /* free the initial references */
 483         ec_tk_free(pre_op);
 484         pre_op = NULL;
 485         ec_tk_free(post_op);
 486         post_op = NULL;
 487         ec_tk_free(term);
 488         term = NULL;
 489         ec_tk_free(factor);
 490         factor = NULL;
 491         ec_tk_free(post);
 492         post = NULL;
 493
 494         /* no need to clone here, the node is not consumed */
 495         if (ec_tk_weakref_set(weak, expr) < 0)
 496                 goto fail;
 497         ec_tk_free(weak);
 498         weak = NULL;
 499
 500         ret |= EC_TEST_CHECK_TK_PARSE(expr, 1, "1");
 501         ret |= EC_TEST_CHECK_TK_PARSE(expr, 1, "1", "*");
 502         ret |= EC_TEST_CHECK_TK_PARSE(expr, 3, "1", "*", "1");
 503         ret |= EC_TEST_CHECK_TK_PARSE(expr, 3, "1", "+", "1");
 504         ret |= EC_TEST_CHECK_TK_PARSE(expr, 5, "1", "*", "1", "+", "1");
 505         ret |= EC_TEST_CHECK_TK_PARSE(
 506                 expr, 10, "~", "(", "1", "*", "(", "1", "+", "1", ")", ")");
 507         ret |= EC_TEST_CHECK_TK_PARSE(expr, 4, "1", "+", "~", "1");
 508
 509         ec_tk_free(expr);
 510
 511         return ret;
 512
 513 fail:
 514         ec_tk_free(term);
 515         ec_tk_free(factor);
 516         ec_tk_free(expr);
 517         ec_tk_free(val);
 518         ec_tk_free(pre_op);
 519         ec_tk_free(post_op);
 520         ec_tk_free(post);
 521         ec_tk_free(weak);
 522         return 0;
 523 }
 524
 525 static int ec_tk_expr_testcase(void)
 526 {
 527         struct ec_tk *tk;
 528         int ret;
 529
 530         ret = ec_tk_expr_testcase_manual();
 531         if (ret < 0)
 532                 return ret;
 533
 534         tk = ec_tk_expr(NULL);
 535         if (tk == NULL)
 536                 return -1;
 537
 538         ec_tk_expr_set_val_tk(tk, ec_tk_int(NULL, 0, UCHAR_MAX, 0));
 539         ec_tk_expr_add_bin_op(tk, ec_tk_str(NULL, "+"));
 540         ec_tk_expr_add_bin_op(tk, ec_tk_str(NULL, "*"));
 541         ec_tk_expr_add_pre_op(tk, ec_tk_str(NULL, "~"));
 542         ec_tk_expr_add_pre_op(tk, ec_tk_str(NULL, "!"));
 543         ec_tk_expr_add_parenthesis(tk, ec_tk_str(NULL, "("),
 544                 ec_tk_str(NULL, ")"));
 545         ret |= EC_TEST_CHECK_TK_PARSE(tk, 1, "1");
 546         ret |= EC_TEST_CHECK_TK_PARSE(tk, 1, "1", "*");
 547         ret |= EC_TEST_CHECK_TK_PARSE(tk, 3, "1", "*", "1");
 548         ret |= EC_TEST_CHECK_TK_PARSE(tk, 3, "1", "+", "1");
 549         ret |= EC_TEST_CHECK_TK_PARSE(tk, 5, "1", "*", "1", "+", "1");
 550         ret |= EC_TEST_CHECK_TK_PARSE(
 551                 tk, 10, "~", "(", "1", "*", "(", "1", "+", "1", ")", ")");
 552         ret |= EC_TEST_CHECK_TK_PARSE(tk, 4, "1", "+", "~", "1");
 553         ec_tk_free(tk);
 554
 555         return ret;
 556 }
 557
 558 static struct ec_test ec_tk_expr_test = {
 559         .name = "tk_expr",
 560         .test = ec_tk_expr_testcase,
 561 };
 562
 563 EC_REGISTER_TEST(ec_tk_expr_test);