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