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