src/ecoli_node.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_malloc.h>
  13 #include <ecoli_string.h>
  14 #include <ecoli_strvec.h>
  15 #include <ecoli_dict.h>
  16 #include <ecoli_log.h>
  17 #include <ecoli_config.h>
  18 #include <ecoli_test.h>
  19 #include <ecoli_node.h>
  20
  21 #include <ecoli_node_str.h>
  22 #include <ecoli_node_seq.h>
  23 #include <ecoli_node_or.h>
  24 #include <ecoli_node_int.h>
  25
  26 EC_LOG_TYPE_REGISTER(node);
  27
  28 struct ec_node {
  29         const struct ec_node_type *type;
  30         struct ec_config *config;    /**< Generic configuration. */
  31         char *id;
  32         char *desc;
  33         struct ec_dict *attrs;
  34         unsigned int refcnt;
  35         struct {
  36                 enum ec_node_free_state state; /**< State of loop detection */
  37                 unsigned int refcnt;    /**< Number of reachable references
  38                                          *   starting from node beeing freed */
  39         } free; /**< Freeing state: used for loop detection */
  40 };
  41
  42 static struct ec_node_type_list node_type_list =
  43         TAILQ_HEAD_INITIALIZER(node_type_list);
  44
  45 const struct ec_node_type *
  46 ec_node_type_lookup(const char *name)
  47 {
  48         struct ec_node_type *type;
  49
  50         TAILQ_FOREACH(type, &node_type_list, next) {
  51                 if (!strcmp(name, type->name))
  52                         return type;
  53         }
  54
  55         errno = ENOENT;
  56         return NULL;
  57 }
  58
  59 int ec_node_type_register(struct ec_node_type *type)
  60 {
  61         if (ec_node_type_lookup(type->name) != NULL) {
  62                 errno = EEXIST;
  63                 return -1;
  64         }
  65
  66         TAILQ_INSERT_TAIL(&node_type_list, type, next);
  67
  68         return 0;
  69 }
  70
  71 void ec_node_type_dump(FILE *out)
  72 {
  73         struct ec_node_type *type;
  74
  75         TAILQ_FOREACH(type, &node_type_list, next)
  76                 fprintf(out, "%s\n", type->name);
  77 }
  78
  79 struct ec_node *ec_node_from_type(const struct ec_node_type *type, const char *id)
  80 {
  81         struct ec_node *node = NULL;
  82
  83         EC_LOG(EC_LOG_DEBUG, "create node type=%s id=%s\n",
  84                 type->name, id);
  85         if (id == NULL) {
  86                 errno = EINVAL;
  87                 goto fail;
  88         }
  89
  90         node = ec_calloc(1, sizeof(*node) + type->size);
  91         if (node == NULL)
  92                 goto fail;
  93
  94         node->type = type;
  95         node->refcnt = 1;
  96
  97         // XXX check that id matches [_a-zA-Z][:-_0-9a-zA-Z]*
  98         node->id = ec_strdup(id);
  99         if (node->id == NULL)
 100                 goto fail;
 101
 102         if (ec_asprintf(&node->desc, "<%s>", type->name) < 0)
 103                 goto fail;
 104
 105         node->attrs = ec_dict();
 106         if (node->attrs == NULL)
 107                 goto fail;
 108
 109         if (type->init_priv != NULL) {
 110                 if (type->init_priv(node) < 0)
 111                         goto fail;
 112         }
 113
 114         return node;
 115
 116  fail:
 117         if (node != NULL) {
 118                 ec_dict_free(node->attrs);
 119                 ec_free(node->desc);
 120                 ec_free(node->id);
 121         }
 122         ec_free(node);
 123
 124         return NULL;
 125 }
 126
 127 const struct ec_config_schema *
 128 ec_node_type_schema(const struct ec_node_type *type)
 129 {
 130         return type->schema;
 131 }
 132
 133 const char *
 134 ec_node_type_name(const struct ec_node_type *type)
 135 {
 136         return type->name;
 137 }
 138
 139 struct ec_node *ec_node(const char *typename, const char *id)
 140 {
 141         const struct ec_node_type *type;
 142
 143         type = ec_node_type_lookup(typename);
 144         if (type == NULL) {
 145                 EC_LOG(EC_LOG_ERR, "type=%s does not exist\n",
 146                         typename);
 147                 return NULL;
 148         }
 149
 150         return ec_node_from_type(type, id);
 151 }
 152
 153 static void count_references(struct ec_node *node, unsigned int refs)
 154 {
 155         struct ec_node *child;
 156         size_t i, n;
 157         int ret;
 158
 159         if (node->free.state == EC_NODE_FREE_STATE_TRAVERSED) {
 160                 node->free.refcnt += refs;
 161                 return;
 162         }
 163         node->free.refcnt = refs;
 164         node->free.state = EC_NODE_FREE_STATE_TRAVERSED;
 165         n = ec_node_get_children_count(node);
 166         for (i = 0; i < n; i++) {
 167                 ret = ec_node_get_child(node, i, &child, &refs);
 168                 assert(ret == 0);
 169                 count_references(child, refs);
 170         }
 171 }
 172
 173 static void mark_freeable(struct ec_node *node, enum ec_node_free_state mark)
 174 {
 175         struct ec_node *child;
 176         unsigned int refs;
 177         size_t i, n;
 178         int ret;
 179
 180         if (mark == node->free.state)
 181                 return;
 182
 183         if (node->refcnt > node->free.refcnt)
 184                 mark = EC_NODE_FREE_STATE_NOT_FREEABLE;
 185         assert(node->refcnt >= node->free.refcnt);
 186         node->free.state = mark;
 187
 188         n = ec_node_get_children_count(node);
 189         for (i = 0; i < n; i++) {
 190                 ret = ec_node_get_child(node, i, &child, &refs);
 191                 assert(ret == 0);
 192                 mark_freeable(child, mark);
 193         }
 194 }
 195
 196 static void reset_mark(struct ec_node *node)
 197 {
 198         struct ec_node *child;
 199         unsigned int refs;
 200         size_t i, n;
 201         int ret;
 202
 203         if (node->free.state == EC_NODE_FREE_STATE_NONE)
 204                 return;
 205
 206         node->free.state = EC_NODE_FREE_STATE_NONE;
 207         node->free.refcnt = 0;
 208
 209         n = ec_node_get_children_count(node);
 210         for (i = 0; i < n; i++) {
 211                 ret = ec_node_get_child(node, i, &child, &refs);
 212                 assert(ret == 0);
 213                 reset_mark(child);
 214         }
 215 }
 216
 217 /* free a node, taking care of loops in the node graph */
 218 void ec_node_free(struct ec_node *node)
 219 {
 220         size_t n;
 221
 222         if (node == NULL)
 223                 return;
 224
 225         assert(node->refcnt > 0);
 226
 227         if (node->free.state == EC_NODE_FREE_STATE_NONE &&
 228                         node->refcnt != 1) {
 229
 230                 /* Traverse the node tree starting from this node, and for each
 231                  * node, count the number of reachable references. Then, all
 232                  * nodes whose reachable references == total reference are
 233                  * marked as freeable, and other are marked as unfreeable. Any
 234                  * node reachable from an unfreeable node is also marked as
 235                  * unfreeable. */
 236                 if (node->free.state == EC_NODE_FREE_STATE_NONE) {
 237                         count_references(node, 1);
 238                         mark_freeable(node, EC_NODE_FREE_STATE_FREEABLE);
 239                 }
 240         }
 241
 242         if (node->free.state == EC_NODE_FREE_STATE_NOT_FREEABLE) {
 243                 node->refcnt--;
 244                 reset_mark(node);
 245                 return;
 246         }
 247
 248         if (node->free.state != EC_NODE_FREE_STATE_FREEING) {
 249                 node->free.state = EC_NODE_FREE_STATE_FREEING;
 250
 251                 /* children will be freed by config_free() and free_priv() */
 252                 ec_config_free(node->config);
 253                 node->config = NULL;
 254                 n = ec_node_get_children_count(node);
 255                 assert(n == 0 || node->type->free_priv != NULL);
 256                 if (node->type->free_priv != NULL)
 257                         node->type->free_priv(node);
 258                 ec_free(node->id);
 259                 ec_free(node->desc);
 260                 ec_dict_free(node->attrs);
 261         }
 262
 263         node->refcnt--;
 264         if (node->refcnt != 0)
 265                 return;
 266
 267         node->free.state = EC_NODE_FREE_STATE_NONE;
 268         node->free.refcnt = 0;
 269
 270         ec_free(node);
 271 }
 272
 273 struct ec_node *ec_node_clone(struct ec_node *node)
 274 {
 275         if (node != NULL)
 276                 node->refcnt++;
 277         return node;
 278 }
 279
 280 size_t ec_node_get_children_count(const struct ec_node *node)
 281 {
 282         if (node->type->get_children_count == NULL)
 283                 return 0;
 284         return node->type->get_children_count(node);
 285 }
 286
 287 int
 288 ec_node_get_child(const struct ec_node *node, size_t i,
 289         struct ec_node **child, unsigned int *refs)
 290 {
 291         *child = NULL;
 292         *refs = 0;
 293         if (node->type->get_child == NULL)
 294                 return -1;
 295         return node->type->get_child(node, i, child, refs);
 296 }
 297
 298 int
 299 ec_node_set_config(struct ec_node *node, struct ec_config *config)
 300 {
 301         if (node->type->schema == NULL) {
 302                 errno = EINVAL;
 303                 goto fail;
 304         }
 305         if (ec_config_validate(config, node->type->schema) < 0)
 306                 goto fail;
 307         if (node->type->set_config != NULL) {
 308                 if (node->type->set_config(node, config) < 0)
 309                         goto fail;
 310         }
 311
 312         ec_config_free(node->config);
 313         node->config = config;
 314
 315         return 0;
 316
 317 fail:
 318         ec_config_free(config);
 319         return -1;
 320 }
 321
 322 const struct ec_config *ec_node_get_config(struct ec_node *node)
 323 {
 324         return node->config;
 325 }
 326
 327 struct ec_node *ec_node_find(struct ec_node *node, const char *id)
 328 {
 329         struct ec_node *child, *retnode;
 330         const char *node_id = ec_node_id(node);
 331         unsigned int refs;
 332         size_t i, n;
 333         int ret;
 334
 335         if (id != NULL && node_id != NULL && !strcmp(node_id, id))
 336                 return node;
 337
 338         n = ec_node_get_children_count(node);
 339         for (i = 0; i < n; i++) {
 340                 ret = ec_node_get_child(node, i, &child, &refs);
 341                 assert(ret == 0);
 342                 retnode = ec_node_find(child, id);
 343                 if (retnode != NULL)
 344                         return retnode;
 345         }
 346
 347         return NULL;
 348 }
 349
 350 const struct ec_node_type *ec_node_type(const struct ec_node *node)
 351 {
 352         return node->type;
 353 }
 354
 355 struct ec_dict *ec_node_attrs(const struct ec_node *node)
 356 {
 357         return node->attrs;
 358 }
 359
 360 const char *ec_node_id(const struct ec_node *node)
 361 {
 362         return node->id;
 363 }
 364
 365 static void __ec_node_dump(FILE *out,
 366         const struct ec_node *node, size_t indent, struct ec_dict *dict)
 367 {
 368         const char *id, *typename;
 369         struct ec_node *child;
 370         unsigned int refs;
 371         char buf[32];
 372         size_t i, n;
 373         int ret;
 374
 375         id = ec_node_id(node);
 376         typename = node->type->name;
 377
 378         snprintf(buf, sizeof(buf), "%p", node);
 379         if (ec_dict_has_key(dict, buf)) {
 380                 fprintf(out, "%*s" "type=%s id=%s %p... (loop)\n",
 381                         (int)indent * 4, "", typename, id, node);
 382                 return;
 383         }
 384
 385         ec_dict_set(dict, buf, NULL, NULL);
 386         fprintf(out, "%*s" "type=%s id=%s %p refs=%u free_state=%d free_refs=%d\n",
 387                 (int)indent * 4, "", typename, id, node, node->refcnt,
 388                 node->free.state, node->free.refcnt);
 389
 390         n = ec_node_get_children_count(node);
 391         for (i = 0; i < n; i++) {
 392                 ret = ec_node_get_child(node, i, &child, &refs);
 393                 assert(ret == 0);
 394                 __ec_node_dump(out, child, indent + 1, dict);
 395         }
 396 }
 397
 398 /* XXX this is too much debug-oriented, we should have a parameter or 2 funcs */
 399 void ec_node_dump(FILE *out, const struct ec_node *node)
 400 {
 401         struct ec_dict *dict = NULL;
 402
 403         fprintf(out, "------------------- node dump:\n");
 404
 405         if (node == NULL) {
 406                 fprintf(out, "node is NULL\n");
 407                 return;
 408         }
 409
 410         dict = ec_dict();
 411         if (dict == NULL)
 412                 goto fail;
 413
 414         __ec_node_dump(out, node, 0, dict);
 415
 416         ec_dict_free(dict);
 417         return;
 418
 419 fail:
 420         ec_dict_free(dict);
 421         EC_LOG(EC_LOG_ERR, "failed to dump node\n");
 422 }
 423
 424 const char *ec_node_desc(const struct ec_node *node)
 425 {
 426         if (node->type->desc != NULL)
 427                 return node->type->desc(node);
 428
 429         return node->desc;
 430 }
 431
 432 int ec_node_check_type(const struct ec_node *node,
 433                 const struct ec_node_type *type)
 434 {
 435         if (strcmp(node->type->name, type->name)) {
 436                 errno = EINVAL;
 437                 return -1;
 438         }
 439
 440         return 0;
 441 }
 442
 443 const char *ec_node_get_type_name(const struct ec_node *node)
 444 {
 445         return node->type->name;
 446 }
 447
 448 void *ec_node_priv(const struct ec_node *node)
 449 {
 450         if (node == NULL)
 451                 return NULL;
 452         return (void *)(node + 1);
 453 }
 454
 455 /* LCOV_EXCL_START */
 456 static int ec_node_testcase(void)
 457 {
 458         struct ec_node *node = NULL, *expr = NULL;
 459         struct ec_node *expr2 = NULL, *val = NULL, *op = NULL, *seq = NULL;
 460         const struct ec_node_type *type;
 461         struct ec_node *child;
 462         unsigned int refs;
 463         FILE *f = NULL;
 464         char *buf = NULL;
 465         size_t buflen = 0;
 466         int testres = 0;
 467         int ret;
 468
 469         node = EC_NODE_SEQ(EC_NO_ID,
 470                         ec_node_str("id_x", "x"),
 471                         ec_node_str("id_y", "y"));
 472         if (node == NULL)
 473                 goto fail;
 474
 475         ec_node_clone(node);
 476         ec_node_free(node);
 477
 478         f = open_memstream(&buf, &buflen);
 479         if (f == NULL)
 480                 goto fail;
 481         ec_node_dump(f, node);
 482         ec_node_type_dump(f);
 483         ec_node_dump(f, NULL);
 484         fclose(f);
 485         f = NULL;
 486
 487         testres |= EC_TEST_CHECK(
 488                 strstr(buf, "type=seq id=no-id"), "bad dump\n");
 489         testres |= EC_TEST_CHECK(
 490                 strstr(buf, "type=str id=id_x") &&
 491                 strstr(strstr(buf, "type=str id=id_x") + 1,
 492                         "type=str id=id_y"),
 493                 "bad dump\n");
 494         free(buf);
 495         buf = NULL;
 496
 497         testres |= EC_TEST_CHECK(
 498                 !strcmp(ec_node_type(node)->name, "seq") &&
 499                 !strcmp(ec_node_id(node), EC_NO_ID) &&
 500                 !strcmp(ec_node_desc(node), "<seq>"),
 501                 "bad child 0");
 502
 503         testres |= EC_TEST_CHECK(
 504                 ec_node_get_children_count(node) == 2,
 505                 "bad children count\n");
 506         ret = ec_node_get_child(node, 0, &child, &refs);
 507         testres |= EC_TEST_CHECK(ret == 0 &&
 508                 child != NULL &&
 509                 !strcmp(ec_node_type(child)->name, "str") &&
 510                 !strcmp(ec_node_id(child), "id_x"),
 511                 "bad child 0");
 512         ret = ec_node_get_child(node, 1, &child, &refs);
 513         testres |= EC_TEST_CHECK(ret == 0 &&
 514                 child != NULL &&
 515                 !strcmp(ec_node_type(child)->name, "str") &&
 516                 !strcmp(ec_node_id(child), "id_y"),
 517                 "bad child 1");
 518         ret = ec_node_get_child(node, 2, &child, &refs);
 519         testres |= EC_TEST_CHECK(ret != 0,
 520                 "ret should be != 0");
 521         testres |= EC_TEST_CHECK(child == NULL,
 522                 "child 2 should be NULL");
 523
 524         child = ec_node_find(node, "id_x");
 525         testres |= EC_TEST_CHECK(child != NULL &&
 526                 !strcmp(ec_node_type(child)->name, "str") &&
 527                 !strcmp(ec_node_id(child), "id_x") &&
 528                 !strcmp(ec_node_desc(child), "x"),
 529                 "bad child id_x");
 530         child = ec_node_find(node, "id_dezdex");
 531         testres |= EC_TEST_CHECK(child == NULL,
 532                 "child with wrong id should be NULL");
 533
 534         ret = ec_dict_set(ec_node_attrs(node), "key", "val", NULL);
 535         testres |= EC_TEST_CHECK(ret == 0,
 536                 "cannot set node attribute\n");
 537
 538         type = ec_node_type_lookup("seq");
 539         testres |= EC_TEST_CHECK(type != NULL &&
 540                 ec_node_check_type(node, type) == 0,
 541                 "cannot get seq node type");
 542         type = ec_node_type_lookup("str");
 543         testres |= EC_TEST_CHECK(type != NULL &&
 544                 ec_node_check_type(node, type) < 0,
 545                 "node type should not be str");
 546
 547         ec_node_free(node);
 548         node = NULL;
 549
 550         node = ec_node("deznuindez", EC_NO_ID);
 551         testres |= EC_TEST_CHECK(node == NULL,
 552                         "should not be able to create node\n");
 553
 554         /* test loop */
 555         expr = ec_node("or", EC_NO_ID);
 556         val = ec_node_int(EC_NO_ID, 0, 10, 0);
 557         op = ec_node_str(EC_NO_ID, "!");
 558         seq = EC_NODE_SEQ(EC_NO_ID,
 559                         op,
 560                         ec_node_clone(expr));
 561         op = NULL;
 562         if (expr == NULL || val == NULL || seq == NULL)
 563                 goto fail;
 564         if (ec_node_or_add(expr, ec_node_clone(seq)) < 0)
 565                 goto fail;
 566         ec_node_free(seq);
 567         seq = NULL;
 568         if (ec_node_or_add(expr, ec_node_clone(val)) < 0)
 569                 goto fail;
 570         ec_node_free(val);
 571         val = NULL;
 572
 573         testres |= EC_TEST_CHECK_PARSE(expr, 1, "1");
 574         testres |= EC_TEST_CHECK_PARSE(expr, 3, "!", "!", "1");
 575         testres |= EC_TEST_CHECK_PARSE(expr, -1, "!", "!", "!");
 576
 577         ec_node_free(expr);
 578         expr = NULL;
 579
 580         /* same loop test, but keep some refs (released later) */
 581         expr = ec_node("or", EC_NO_ID);
 582         ec_node_clone(expr);
 583         expr2 = expr;
 584         val = ec_node_int(EC_NO_ID, 0, 10, 0);
 585         op = ec_node_str(EC_NO_ID, "!");
 586         seq = EC_NODE_SEQ(EC_NO_ID,
 587                         op,
 588                         ec_node_clone(expr));
 589         op = NULL;
 590         if (expr == NULL || val == NULL || seq == NULL)
 591                 goto fail;
 592         if (ec_node_or_add(expr, ec_node_clone(seq)) < 0)
 593                 goto fail;
 594         ec_node_free(seq);
 595         seq = NULL;
 596         if (ec_node_or_add(expr, ec_node_clone(val)) < 0)
 597                 goto fail;
 598
 599         testres |= EC_TEST_CHECK_PARSE(expr, 1, "1");
 600         testres |= EC_TEST_CHECK_PARSE(expr, 3, "!", "!", "1");
 601         testres |= EC_TEST_CHECK_PARSE(expr, -1, "!", "!", "!");
 602
 603         ec_node_free(expr2);
 604         expr2 = NULL;
 605         ec_node_free(val);
 606         val = NULL;
 607         ec_node_free(expr);
 608         expr = NULL;
 609
 610         return testres;
 611
 612 fail:
 613         ec_node_free(expr);
 614         ec_node_free(expr2);
 615         ec_node_free(val);
 616         ec_node_free(seq);
 617         ec_node_free(node);
 618         if (f != NULL)
 619                 fclose(f);
 620         free(buf);
 621
 622         assert(errno != 0);
 623         return -1;
 624 }
 625 /* LCOV_EXCL_STOP */
 626
 627 static struct ec_test ec_node_test = {
 628         .name = "node",
 629         .test = ec_node_testcase,
 630 };
 631
 632 EC_TEST_REGISTER(ec_node_test);