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_keyval.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_keyval *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_keyval();
 153         if (parse->attrs == NULL)
 154                 goto fail;
 155
 156         return parse;
 157
 158  fail:
 159         if (parse != NULL)
 160                 ec_keyval_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_keyval *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_keyval_dup(root->attrs);
 185         if (attrs == NULL)
 186                 goto fail;
 187         ec_keyval_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_keyval_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 = parse->node->id;
 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_get_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(struct ec_parse *parse)
 369 {
 370         struct ec_parse *child, *parent, *next;
 371
 372         child = TAILQ_FIRST(&parse->children);
 373         if (child != NULL)
 374                 return child;
 375         parent = parse->parent;
 376         while (parent != NULL) {
 377                 next = TAILQ_NEXT(parse, next);
 378                 if (next != NULL)
 379                         return next;
 380                 parse = parent;
 381                 parent = parse->parent;
 382         }
 383         return NULL;
 384 }
 385
 386 struct ec_parse *ec_parse_find_first(struct ec_parse *parse,
 387         const char *id)
 388 {
 389         struct ec_parse *iter;
 390
 391         if (parse == NULL)
 392                 return NULL;
 393
 394         for (iter = parse; iter != NULL; iter = ec_parse_iter_next(iter)) {
 395                 if (iter->node != NULL &&
 396                                 iter->node->id != NULL &&
 397                                 !strcmp(iter->node->id, id))
 398                         return iter;
 399         }
 400
 401         return NULL;
 402 }
 403
 404 struct ec_keyval *
 405 ec_parse_get_attrs(struct ec_parse *parse)
 406 {
 407         if (parse == NULL)
 408                 return NULL;
 409
 410         return parse->attrs;
 411 }
 412
 413 const struct ec_strvec *ec_parse_strvec(const struct ec_parse *parse)
 414 {
 415         if (parse == NULL || parse->strvec == NULL)
 416                 return NULL;
 417
 418         return parse->strvec;
 419 }
 420
 421 /* number of strings in the parse vector */
 422 size_t ec_parse_len(const struct ec_parse *parse)
 423 {
 424         if (parse == NULL || parse->strvec == NULL)
 425                 return 0;
 426
 427         return ec_strvec_len(parse->strvec);
 428 }
 429
 430 size_t ec_parse_matches(const struct ec_parse *parse)
 431 {
 432         if (parse == NULL)
 433                 return 0;
 434
 435         if (parse->strvec == NULL)
 436                 return 0;
 437
 438         return 1;
 439 }
 440
 441 /* LCOV_EXCL_START */
 442 static int ec_parse_testcase(void)
 443 {
 444         struct ec_node *node = NULL;
 445         struct ec_parse *p = NULL, *p2 = NULL;
 446         const struct ec_parse *pc;
 447         FILE *f = NULL;
 448         char *buf = NULL;
 449         size_t buflen = 0;
 450         int testres = 0;
 451         int ret;
 452
 453         node = ec_node_sh_lex(EC_NO_ID,
 454                         EC_NODE_SEQ(EC_NO_ID,
 455                                 ec_node_str("id_x", "x"),
 456                                 ec_node_str("id_y", "y")));
 457         if (node == NULL)
 458                 goto fail;
 459
 460         p = ec_node_parse(node, "xcdscds");
 461         testres |= EC_TEST_CHECK(
 462                 p != NULL && !ec_parse_matches(p),
 463                 "parse should not match\n");
 464
 465         f = open_memstream(&buf, &buflen);
 466         if (f == NULL)
 467                 goto fail;
 468         ec_parse_dump(f, p);
 469         fclose(f);
 470         f = NULL;
 471
 472         testres |= EC_TEST_CHECK(
 473                 strstr(buf, "no match"), "bad dump\n");
 474         free(buf);
 475         buf = NULL;
 476         ec_parse_free(p);
 477
 478         p = ec_node_parse(node, "x y");
 479         testres |= EC_TEST_CHECK(
 480                 p != NULL && ec_parse_matches(p),
 481                 "parse should match\n");
 482         testres |= EC_TEST_CHECK(
 483                 ec_parse_len(p) == 1, "bad parse len\n");
 484
 485         ret = ec_keyval_set(ec_parse_get_attrs(p), "key", "val", NULL);
 486         testres |= EC_TEST_CHECK(ret == 0,
 487                 "cannot set parse attribute\n");
 488
 489         p2 = ec_parse_dup(p);
 490         testres |= EC_TEST_CHECK(
 491                 p2 != NULL && ec_parse_matches(p2),
 492                 "parse should match\n");
 493         ec_parse_free(p2);
 494         p2 = NULL;
 495
 496         pc = ec_parse_find_first(p, "id_x");
 497         testres |= EC_TEST_CHECK(pc != NULL, "cannot find id_x");
 498         testres |= EC_TEST_CHECK(pc != NULL &&
 499                 ec_parse_get_parent(pc) != NULL &&
 500                 ec_parse_get_parent(ec_parse_get_parent(pc)) == p,
 501                 "invalid parent\n");
 502
 503         pc = ec_parse_find_first(p, "id_y");
 504         testres |= EC_TEST_CHECK(pc != NULL, "cannot find id_y");
 505         pc = ec_parse_find_first(p, "id_dezdezdez");
 506         testres |= EC_TEST_CHECK(pc == NULL, "should not find bad id");
 507
 508
 509         f = open_memstream(&buf, &buflen);
 510         if (f == NULL)
 511                 goto fail;
 512         ec_parse_dump(f, p);
 513         fclose(f);
 514         f = NULL;
 515
 516         testres |= EC_TEST_CHECK(
 517                 strstr(buf, "type=sh_lex id=no-id") &&
 518                 strstr(buf, "type=seq id=no-id") &&
 519                 strstr(buf, "type=str id=id_x") &&
 520                 strstr(buf, "type=str id=id_x"),
 521                 "bad dump\n");
 522         free(buf);
 523         buf = NULL;
 524
 525         ec_parse_free(p);
 526         ec_node_free(node);
 527         return testres;
 528
 529 fail:
 530         ec_parse_free(p2);
 531         ec_parse_free(p);
 532         ec_node_free(node);
 533         if (f != NULL)
 534                 fclose(f);
 535         free(buf);
 536
 537         return -1;
 538 }
 539 /* LCOV_EXCL_STOP */
 540
 541 static struct ec_test ec_parse_test = {
 542         .name = "parse",
 543         .test = ec_parse_testcase,
 544 };
 545
 546 EC_TEST_REGISTER(ec_parse_test);