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