src/ecoli_parse.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 <stdint.h>
   8 #include <string.h>
   9 #include <assert.h>
  10 #include <errno.h>
  11
  12 #include <ecoli_assert.h>
  13 #include <ecoli_malloc.h>
  14 #include <ecoli_strvec.h>
  15 #include <ecoli_dict.h>
  16 #include <ecoli_log.h>
  17 #include <ecoli_test.h>
  18 #include <ecoli_node.h>
  19 #include <ecoli_node_sh_lex.h>
  20 #include <ecoli_node_str.h>
  21 #include <ecoli_node_seq.h>
  22 #include <ecoli_parse.h>
  23
  24 EC_LOG_TYPE_REGISTER(parse);
  25
  26 TAILQ_HEAD(ec_parse_list, ec_parse);
  27
  28 struct ec_parse {
  29         TAILQ_ENTRY(ec_parse) next;
  30         struct ec_parse_list children;
  31         struct ec_parse *parent;
  32         const struct ec_node *node;
  33         struct ec_strvec *strvec;
  34         struct ec_dict *attrs;
  35 };
  36
  37 static int __ec_node_parse_child(const struct ec_node *node,
  38                                 struct ec_parse *state,
  39                                 bool is_root, const struct ec_strvec *strvec)
  40 {
  41         struct ec_strvec *match_strvec;
  42         struct ec_parse *child = NULL;
  43         int ret;
  44
  45         // XXX limit max number of recursions to avoid segfault
  46
  47         if (ec_node_type(node)->parse == NULL) {
  48                 errno = ENOTSUP;
  49                 return -1;
  50         }
  51
  52         if (!is_root) {
  53                 child = ec_parse(node);
  54                 if (child == NULL)
  55                         return -1;
  56
  57                 ec_parse_link_child(state, child);
  58         } else {
  59                 child = state;
  60         }
  61         ret = ec_node_type(node)->parse(node, child, strvec);
  62         if (ret < 0)
  63                 goto fail;
  64
  65         if (ret == EC_PARSE_NOMATCH) {
  66                 if (!is_root) {
  67                         ec_parse_unlink_child(state, child);
  68                         ec_parse_free(child);
  69                 }
  70                 return ret;
  71         }
  72
  73         match_strvec = ec_strvec_ndup(strvec, 0, ret);
  74         if (match_strvec == NULL)
  75                 goto fail;
  76
  77         child->strvec = match_strvec;
  78
  79         return ret;
  80
  81 fail:
  82         if (!is_root) {
  83                 ec_parse_unlink_child(state, child);
  84                 ec_parse_free(child);
  85         }
  86         return -1;
  87 }
  88
  89 int ec_node_parse_child(const struct ec_node *node, struct ec_parse *state,
  90                         const struct ec_strvec *strvec)
  91 {
  92         assert(state != NULL);
  93         return __ec_node_parse_child(node, state, false, strvec);
  94 }
  95
  96 // XXX what is returned if no match ??
  97 struct ec_parse *ec_node_parse_strvec(const struct ec_node *node,
  98                                 const struct ec_strvec *strvec)
  99 {
 100         struct ec_parse *parse = ec_parse(node);
 101         int ret;
 102
 103         if (parse == NULL)
 104                 return NULL;
 105
 106         ret = __ec_node_parse_child(node, parse, true, strvec);
 107         if (ret < 0) {
 108                 ec_parse_free(parse);
 109                 return NULL;
 110         }
 111
 112         return parse;
 113 }
 114
 115 struct ec_parse *ec_node_parse(const struct ec_node *node, const char *str)
 116 {
 117         struct ec_strvec *strvec = NULL;
 118         struct ec_parse *parse = NULL;
 119
 120         errno = ENOMEM;
 121         strvec = ec_strvec();
 122         if (strvec == NULL)
 123                 goto fail;
 124
 125         if (ec_strvec_add(strvec, str) < 0)
 126                 goto fail;
 127
 128         parse = ec_node_parse_strvec(node, strvec);
 129         if (parse == NULL)
 130                 goto fail;
 131
 132         ec_strvec_free(strvec);
 133         return parse;
 134
 135  fail:
 136         ec_strvec_free(strvec);
 137         ec_parse_free(parse);
 138         return NULL;
 139 }
 140
 141 struct ec_parse *ec_parse(const struct ec_node *node)
 142 {
 143         struct ec_parse *parse = NULL;
 144
 145         parse = ec_calloc(1, sizeof(*parse));
 146         if (parse == NULL)
 147                 goto fail;
 148
 149         TAILQ_INIT(&parse->children);
 150
 151         parse->node = node;
 152         parse->attrs = ec_dict();
 153         if (parse->attrs == NULL)
 154                 goto fail;
 155
 156         return parse;
 157
 158  fail:
 159         if (parse != NULL)
 160                 ec_dict_free(parse->attrs);
 161         ec_free(parse);
 162
 163         return NULL;
 164 }
 165
 166 static struct ec_parse *
 167 __ec_parse_dup(const struct ec_parse *root, const struct ec_parse *ref,
 168                 struct ec_parse **new_ref)
 169 {
 170         struct ec_parse *dup = NULL;
 171         struct ec_parse *child, *dup_child;
 172         struct ec_dict *attrs = NULL;
 173
 174         if (root == NULL)
 175                 return NULL;
 176
 177         dup = ec_parse(root->node);
 178         if (dup == NULL)
 179                 return NULL;
 180
 181         if (root == ref)
 182                 *new_ref = dup;
 183
 184         attrs = ec_dict_dup(root->attrs);
 185         if (attrs == NULL)
 186                 goto fail;
 187         ec_dict_free(dup->attrs);
 188         dup->attrs = attrs;
 189
 190         if (root->strvec != NULL) {
 191                 dup->strvec = ec_strvec_dup(root->strvec);
 192                 if (dup->strvec == NULL)
 193                         goto fail;
 194         }
 195
 196         TAILQ_FOREACH(child, &root->children, next) {
 197                 dup_child = __ec_parse_dup(child, ref, new_ref);
 198                 if (dup_child == NULL)
 199                         goto fail;
 200                 ec_parse_link_child(dup, dup_child);
 201         }
 202
 203         return dup;
 204
 205 fail:
 206         ec_parse_free(dup);
 207         return NULL;
 208 }
 209
 210 struct ec_parse *ec_parse_dup(const struct ec_parse *parse)
 211 {
 212         const struct ec_parse *root;
 213         struct ec_parse *dup_root, *dup = NULL;
 214
 215         root = ec_parse_get_root(parse);
 216         dup_root = __ec_parse_dup(root, parse, &dup);
 217         if (dup_root == NULL)
 218                 return NULL;
 219         assert(dup != NULL);
 220
 221         return dup;
 222 }
 223
 224 void ec_parse_free_children(struct ec_parse *parse)
 225 {
 226         struct ec_parse *child;
 227
 228         if (parse == NULL)
 229                 return;
 230
 231         while (!TAILQ_EMPTY(&parse->children)) {
 232                 child = TAILQ_FIRST(&parse->children);
 233                 TAILQ_REMOVE(&parse->children, child, next);
 234                 child->parent = NULL;
 235                 ec_parse_free(child);
 236         }
 237 }
 238
 239 void ec_parse_free(struct ec_parse *parse)
 240 {
 241         if (parse == NULL)
 242                 return;
 243
 244         ec_assert_print(parse->parent == NULL,
 245                         "parent not NULL in ec_parse_free()");
 246
 247         ec_parse_free_children(parse);
 248         ec_strvec_free(parse->strvec);
 249         ec_dict_free(parse->attrs);
 250         ec_free(parse);
 251 }
 252
 253 static void __ec_parse_dump(FILE *out,
 254         const struct ec_parse *parse, size_t indent)
 255 {
 256         struct ec_parse *child;
 257         const struct ec_strvec *vec;
 258         const char *id = "none", *typename = "none";
 259
 260         /* node can be null when parsing is incomplete */
 261         if (parse->node != NULL) {
 262                 id = ec_node_id(parse->node);
 263                 typename = ec_node_type(parse->node)->name;
 264         }
 265
 266         fprintf(out, "%*s" "type=%s id=%s vec=",
 267                 (int)indent * 4, "", typename, id);
 268         vec = ec_parse_strvec(parse);
 269         ec_strvec_dump(out, vec);
 270
 271         TAILQ_FOREACH(child, &parse->children, next)
 272                 __ec_parse_dump(out, child, indent + 1);
 273 }
 274
 275 void ec_parse_dump(FILE *out, const struct ec_parse *parse)
 276 {
 277         fprintf(out, "------------------- parse dump:\n");
 278
 279         if (parse == NULL) {
 280                 fprintf(out, "parse is NULL\n");
 281                 return;
 282         }
 283
 284         /* only exist if it does not match (strvec == NULL) and if it
 285          * does not have children: an incomplete parse, like those
 286          * generated by complete() don't match but have children that
 287          * may match. */
 288         if (!ec_parse_matches(parse) && TAILQ_EMPTY(&parse->children)) {
 289                 fprintf(out, "no match\n");
 290                 return;
 291         }
 292
 293         __ec_parse_dump(out, parse, 0);
 294 }
 295
 296 void ec_parse_link_child(struct ec_parse *parse,
 297         struct ec_parse *child)
 298 {
 299         TAILQ_INSERT_TAIL(&parse->children, child, next);
 300         child->parent = parse;
 301 }
 302
 303 void ec_parse_unlink_child(struct ec_parse *parse,
 304         struct ec_parse *child)
 305 {
 306         TAILQ_REMOVE(&parse->children, child, next);
 307         child->parent = NULL;
 308 }
 309
 310 struct ec_parse *
 311 ec_parse_get_first_child(const struct ec_parse *parse)
 312 {
 313         return TAILQ_FIRST(&parse->children);
 314 }
 315
 316 struct ec_parse *
 317 ec_parse_get_last_child(const struct ec_parse *parse)
 318 {
 319         return TAILQ_LAST(&parse->children, ec_parse_list);
 320 }
 321
 322 struct ec_parse *ec_parse_next(const struct ec_parse *parse)
 323 {
 324         return TAILQ_NEXT(parse, next);
 325 }
 326
 327 bool ec_parse_has_child(const struct ec_parse *parse)
 328 {
 329         return !TAILQ_EMPTY(&parse->children);
 330 }
 331
 332 const struct ec_node *ec_parse_get_node(const struct ec_parse *parse)
 333 {
 334         if (parse == NULL)
 335                 return NULL;
 336
 337         return parse->node;
 338 }
 339
 340 void ec_parse_del_last_child(struct ec_parse *parse)
 341 {
 342         struct ec_parse *child;
 343
 344         child = ec_parse_get_last_child(parse);
 345         ec_parse_unlink_child(parse, child);
 346         ec_parse_free(child);
 347 }
 348
 349 struct ec_parse *__ec_parse_get_root(struct ec_parse *parse)
 350 {
 351         if (parse == NULL)
 352                 return NULL;
 353
 354         while (parse->parent != NULL)
 355                 parse = parse->parent;
 356
 357         return parse;
 358 }
 359
 360 struct ec_parse *ec_parse_get_parent(const struct ec_parse *parse)
 361 {
 362         if (parse == NULL)
 363                 return NULL;
 364
 365         return parse->parent;
 366 }
 367
 368 struct ec_parse *__ec_parse_iter_next(const struct ec_parse *root,
 369                                 struct ec_parse *parse, bool iter_children)
 370 {
 371         struct ec_parse *child, *parent, *next;
 372
 373         if (iter_children) {
 374                 child = TAILQ_FIRST(&parse->children);
 375                 if (child != NULL)
 376                         return child;
 377         }
 378         parent = parse->parent;
 379         while (parent != NULL && parse != root) {
 380                 next = TAILQ_NEXT(parse, next);
 381                 if (next != NULL)
 382                         return next;
 383                 parse = parent;
 384                 parent = parse->parent;
 385         }
 386         return NULL;
 387 }
 388
 389 struct ec_parse *
 390 ec_parse_find_next(struct ec_parse *root, struct ec_parse *start,
 391                 const char *id, bool iter_children)
 392 {
 393         struct ec_parse *iter;
 394
 395         if (root == NULL)
 396                 return NULL;
 397         if (start == NULL)
 398                 start = root;
 399         else
 400                 start = EC_PARSE_ITER_NEXT(root, start, iter_children);
 401
 402         for (iter = start; iter != NULL;
 403              iter = EC_PARSE_ITER_NEXT(root, iter, 1)) {
 404                 if (iter->node != NULL &&
 405                                 !strcmp(ec_node_id(iter->node), id))
 406                         return iter;
 407         }
 408
 409         return NULL;
 410 }
 411
 412 struct ec_parse *ec_parse_find(struct ec_parse *parse,
 413         const char *id)
 414 {
 415         return ec_parse_find_next(parse, NULL, id, 1);
 416 }
 417
 418 struct ec_dict *
 419 ec_parse_get_attrs(struct ec_parse *parse)
 420 {
 421         if (parse == NULL)
 422                 return NULL;
 423
 424         return parse->attrs;
 425 }
 426
 427 const struct ec_strvec *ec_parse_strvec(const struct ec_parse *parse)
 428 {
 429         if (parse == NULL || parse->strvec == NULL)
 430                 return NULL;
 431
 432         return parse->strvec;
 433 }
 434
 435 /* number of strings in the parse vector */
 436 size_t ec_parse_len(const struct ec_parse *parse)
 437 {
 438         if (parse == NULL || parse->strvec == NULL)
 439                 return 0;
 440
 441         return ec_strvec_len(parse->strvec);
 442 }
 443
 444 size_t ec_parse_matches(const struct ec_parse *parse)
 445 {
 446         if (parse == NULL)
 447                 return 0;
 448
 449         if (parse->strvec == NULL)
 450                 return 0;
 451
 452         return 1;
 453 }
 454
 455 /* LCOV_EXCL_START */
 456 static int ec_parse_testcase(void)
 457 {
 458         struct ec_node *node = NULL;
 459         struct ec_parse *p = NULL, *p2 = NULL;
 460         const struct ec_parse *pc;
 461         FILE *f = NULL;
 462         char *buf = NULL;
 463         size_t buflen = 0;
 464         int testres = 0;
 465         int ret;
 466
 467         node = ec_node_sh_lex(EC_NO_ID,
 468                         EC_NODE_SEQ(EC_NO_ID,
 469                                 ec_node_str("id_x", "x"),
 470                                 ec_node_str("id_y", "y")));
 471         if (node == NULL)
 472                 goto fail;
 473
 474         p = ec_node_parse(node, "xcdscds");
 475         testres |= EC_TEST_CHECK(
 476                 p != NULL && !ec_parse_matches(p),
 477                 "parse should not match\n");
 478
 479         f = open_memstream(&buf, &buflen);
 480         if (f == NULL)
 481                 goto fail;
 482         ec_parse_dump(f, p);
 483         fclose(f);
 484         f = NULL;
 485
 486         testres |= EC_TEST_CHECK(
 487                 strstr(buf, "no match"), "bad dump\n");
 488         free(buf);
 489         buf = NULL;
 490         ec_parse_free(p);
 491
 492         p = ec_node_parse(node, "x y");
 493         testres |= EC_TEST_CHECK(
 494                 p != NULL && ec_parse_matches(p),
 495                 "parse should match\n");
 496         testres |= EC_TEST_CHECK(
 497                 ec_parse_len(p) == 1, "bad parse len\n");
 498
 499         ret = ec_dict_set(ec_parse_get_attrs(p), "key", "val", NULL);
 500         testres |= EC_TEST_CHECK(ret == 0,
 501                 "cannot set parse attribute\n");
 502
 503         p2 = ec_parse_dup(p);
 504         testres |= EC_TEST_CHECK(
 505                 p2 != NULL && ec_parse_matches(p2),
 506                 "parse should match\n");
 507         ec_parse_free(p2);
 508         p2 = NULL;
 509
 510         pc = ec_parse_find(p, "id_x");
 511         testres |= EC_TEST_CHECK(pc != NULL, "cannot find id_x");
 512         testres |= EC_TEST_CHECK(pc != NULL &&
 513                 ec_parse_get_parent(pc) != NULL &&
 514                 ec_parse_get_parent(ec_parse_get_parent(pc)) == p,
 515                 "invalid parent\n");
 516
 517         pc = ec_parse_find(p, "id_y");
 518         testres |= EC_TEST_CHECK(pc != NULL, "cannot find id_y");
 519         pc = ec_parse_find(p, "id_dezdezdez");
 520         testres |= EC_TEST_CHECK(pc == NULL, "should not find bad id");
 521
 522
 523         f = open_memstream(&buf, &buflen);
 524         if (f == NULL)
 525                 goto fail;
 526         ec_parse_dump(f, p);
 527         fclose(f);
 528         f = NULL;
 529
 530         testres |= EC_TEST_CHECK(
 531                 strstr(buf, "type=sh_lex id=no-id") &&
 532                 strstr(buf, "type=seq id=no-id") &&
 533                 strstr(buf, "type=str id=id_x") &&
 534                 strstr(buf, "type=str id=id_x"),
 535                 "bad dump\n");
 536         free(buf);
 537         buf = NULL;
 538
 539         ec_parse_free(p);
 540         ec_node_free(node);
 541         return testres;
 542
 543 fail:
 544         ec_parse_free(p2);
 545         ec_parse_free(p);
 546         ec_node_free(node);
 547         if (f != NULL)
 548                 fclose(f);
 549         free(buf);
 550
 551         return -1;
 552 }
 553 /* LCOV_EXCL_STOP */
 554
 555 static struct ec_test ec_parse_test = {
 556         .name = "parse",
 557         .test = ec_parse_testcase,
 558 };
 559
 560 EC_TEST_REGISTER(ec_parse_test);