1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright 2016, Olivier MATZ <zer0@droids-corp.org>
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>
21 #include <ecoli_node_str.h>
22 #include <ecoli_node_seq.h>
23 #include <ecoli_node_or.h>
24 #include <ecoli_node_int.h>
26 EC_LOG_TYPE_REGISTER(node);
28 /* These states are used to mark the grammar graph when freeing, to
30 enum ec_node_free_state {
31 EC_NODE_FREE_STATE_NONE,
32 EC_NODE_FREE_STATE_TRAVERSED,
33 EC_NODE_FREE_STATE_FREEABLE,
34 EC_NODE_FREE_STATE_NOT_FREEABLE,
35 EC_NODE_FREE_STATE_FREEING,
39 * The grammar node structure.
42 const struct ec_node_type *type; /**< The node type. */
43 struct ec_config *config; /**< Node configuration. */
44 char *id; /**< Node identifier (EC_NO_ID if none). */
45 struct ec_dict *attrs; /**< Attributes of the node. */
46 unsigned int refcnt; /**< Reference counter. */
48 enum ec_node_free_state state; /**< State of loop detection. */
49 unsigned int refcnt; /**< Number of reachable references
50 * starting from node beeing freed. */
51 } free; /**< Freeing state: used for loop detection */
54 static struct ec_node_type_list node_type_list =
55 TAILQ_HEAD_INITIALIZER(node_type_list);
57 const struct ec_node_type *
58 ec_node_type_lookup(const char *name)
60 struct ec_node_type *type;
62 TAILQ_FOREACH(type, &node_type_list, next) {
63 if (!strcmp(name, type->name))
71 int ec_node_type_register(struct ec_node_type *type, bool override)
73 if (!override && ec_node_type_lookup(type->name) != NULL) {
78 TAILQ_INSERT_HEAD(&node_type_list, type, next);
83 void ec_node_type_dump(FILE *out)
85 struct ec_node_type *type;
87 TAILQ_FOREACH(type, &node_type_list, next)
88 fprintf(out, "%s\n", type->name);
91 struct ec_node *ec_node_from_type(const struct ec_node_type *type, const char *id)
93 struct ec_node *node = NULL;
95 EC_LOG(EC_LOG_DEBUG, "create node type=%s id=%s\n",
102 node = ec_calloc(1, sizeof(*node) + type->size);
109 // XXX check that id matches [_a-zA-Z][:-_0-9a-zA-Z]*
110 node->id = ec_strdup(id);
111 if (node->id == NULL)
114 node->attrs = ec_dict();
115 if (node->attrs == NULL)
118 if (type->init_priv != NULL) {
119 if (type->init_priv(node) < 0)
127 ec_dict_free(node->attrs);
135 const struct ec_config_schema *
136 ec_node_type_schema(const struct ec_node_type *type)
142 ec_node_type_name(const struct ec_node_type *type)
147 struct ec_node *ec_node(const char *typename, const char *id)
149 const struct ec_node_type *type;
151 type = ec_node_type_lookup(typename);
153 EC_LOG(EC_LOG_ERR, "type=%s does not exist\n",
158 return ec_node_from_type(type, id);
161 static void count_references(struct ec_node *node, unsigned int refs)
163 struct ec_node *child;
167 if (node->free.state == EC_NODE_FREE_STATE_TRAVERSED) {
168 node->free.refcnt += refs;
171 node->free.refcnt = refs;
172 node->free.state = EC_NODE_FREE_STATE_TRAVERSED;
173 n = ec_node_get_children_count(node);
174 for (i = 0; i < n; i++) {
175 ret = ec_node_get_child(node, i, &child, &refs);
177 count_references(child, refs);
181 static void mark_freeable(struct ec_node *node, enum ec_node_free_state mark)
183 struct ec_node *child;
188 if (mark == node->free.state)
191 if (node->refcnt > node->free.refcnt)
192 mark = EC_NODE_FREE_STATE_NOT_FREEABLE;
193 assert(node->refcnt >= node->free.refcnt);
194 node->free.state = mark;
196 n = ec_node_get_children_count(node);
197 for (i = 0; i < n; i++) {
198 ret = ec_node_get_child(node, i, &child, &refs);
200 mark_freeable(child, mark);
204 static void reset_mark(struct ec_node *node)
206 struct ec_node *child;
211 if (node->free.state == EC_NODE_FREE_STATE_NONE)
214 node->free.state = EC_NODE_FREE_STATE_NONE;
215 node->free.refcnt = 0;
217 n = ec_node_get_children_count(node);
218 for (i = 0; i < n; i++) {
219 ret = ec_node_get_child(node, i, &child, &refs);
225 /* free a node, taking care of loops in the node graph */
226 void ec_node_free(struct ec_node *node)
233 assert(node->refcnt > 0);
235 if (node->free.state == EC_NODE_FREE_STATE_NONE &&
238 /* Traverse the node tree starting from this node, and for each
239 * node, count the number of reachable references. Then, all
240 * nodes whose reachable references == total reference are
241 * marked as freeable, and other are marked as unfreeable. Any
242 * node reachable from an unfreeable node is also marked as
244 if (node->free.state == EC_NODE_FREE_STATE_NONE) {
245 count_references(node, 1);
246 mark_freeable(node, EC_NODE_FREE_STATE_FREEABLE);
250 if (node->free.state == EC_NODE_FREE_STATE_NOT_FREEABLE) {
256 if (node->free.state != EC_NODE_FREE_STATE_FREEING) {
257 node->free.state = EC_NODE_FREE_STATE_FREEING;
259 /* children will be freed by config_free() and free_priv() */
260 ec_config_free(node->config);
262 n = ec_node_get_children_count(node);
263 assert(n == 0 || node->type->free_priv != NULL);
264 if (node->type->free_priv != NULL)
265 node->type->free_priv(node);
267 ec_dict_free(node->attrs);
271 if (node->refcnt != 0)
274 node->free.state = EC_NODE_FREE_STATE_NONE;
275 node->free.refcnt = 0;
280 struct ec_node *ec_node_clone(struct ec_node *node)
287 size_t ec_node_get_children_count(const struct ec_node *node)
289 if (node->type->get_children_count == NULL)
291 return node->type->get_children_count(node);
295 ec_node_get_child(const struct ec_node *node, size_t i,
296 struct ec_node **child, unsigned int *refs)
300 if (node->type->get_child == NULL)
302 return node->type->get_child(node, i, child, refs);
306 ec_node_set_config(struct ec_node *node, struct ec_config *config)
308 if (node->type->schema == NULL) {
312 if (ec_config_validate(config, node->type->schema) < 0)
314 if (node->type->set_config != NULL) {
315 if (node->type->set_config(node, config) < 0)
319 ec_config_free(node->config);
320 node->config = config;
325 ec_config_free(config);
329 const struct ec_config *ec_node_get_config(struct ec_node *node)
334 struct ec_node *ec_node_find(struct ec_node *node, const char *id)
336 struct ec_node *child, *retnode;
337 const char *node_id = ec_node_id(node);
342 if (id != NULL && node_id != NULL && !strcmp(node_id, id))
345 n = ec_node_get_children_count(node);
346 for (i = 0; i < n; i++) {
347 ret = ec_node_get_child(node, i, &child, &refs);
349 retnode = ec_node_find(child, id);
357 const struct ec_node_type *ec_node_type(const struct ec_node *node)
362 struct ec_dict *ec_node_attrs(const struct ec_node *node)
367 const char *ec_node_id(const struct ec_node *node)
372 static void __ec_node_dump(FILE *out,
373 const struct ec_node *node, size_t indent, struct ec_dict *dict)
375 const char *id, *typename;
376 struct ec_node *child;
382 id = ec_node_id(node);
383 typename = node->type->name;
385 snprintf(buf, sizeof(buf), "%p", node);
386 if (ec_dict_has_key(dict, buf)) {
387 fprintf(out, "%*s" "type=%s id=%s %p... (loop)\n",
388 (int)indent * 4, "", typename, id, node);
392 ec_dict_set(dict, buf, NULL, NULL);
393 fprintf(out, "%*s" "type=%s id=%s %p refs=%u free_state=%d free_refs=%d\n",
394 (int)indent * 4, "", typename, id, node, node->refcnt,
395 node->free.state, node->free.refcnt);
397 n = ec_node_get_children_count(node);
398 for (i = 0; i < n; i++) {
399 ret = ec_node_get_child(node, i, &child, &refs);
401 __ec_node_dump(out, child, indent + 1, dict);
405 /* XXX this is too much debug-oriented, we should have a parameter or 2 funcs */
406 void ec_node_dump(FILE *out, const struct ec_node *node)
408 struct ec_dict *dict = NULL;
410 fprintf(out, "------------------- node dump:\n");
413 fprintf(out, "node is NULL\n");
421 __ec_node_dump(out, node, 0, dict);
428 EC_LOG(EC_LOG_ERR, "failed to dump node\n");
431 char *ec_node_desc(const struct ec_node *node)
435 if (node->type->desc != NULL)
436 return node->type->desc(node);
438 if (ec_asprintf(&desc, "<%s>", node->type->name) < 0)
444 int ec_node_check_type(const struct ec_node *node,
445 const struct ec_node_type *type)
447 if (strcmp(node->type->name, type->name)) {
455 const char *ec_node_get_type_name(const struct ec_node *node)
457 return node->type->name;
460 void *ec_node_priv(const struct ec_node *node)
464 return (void *)(node + 1);
467 /* LCOV_EXCL_START */
468 static int ec_node_testcase(void)
470 struct ec_node *node = NULL, *expr = NULL;
471 struct ec_node *expr2 = NULL, *val = NULL, *op = NULL, *seq = NULL;
472 const struct ec_node_type *type;
473 struct ec_node *child;
482 node = EC_NODE_SEQ(EC_NO_ID,
483 ec_node_str("id_x", "x"),
484 ec_node_str("id_y", "y"));
491 f = open_memstream(&buf, &buflen);
494 ec_node_dump(f, node);
495 ec_node_type_dump(f);
496 ec_node_dump(f, NULL);
500 testres |= EC_TEST_CHECK(
501 strstr(buf, "type=seq id=no-id"), "bad dump\n");
502 testres |= EC_TEST_CHECK(
503 strstr(buf, "type=str id=id_x") &&
504 strstr(strstr(buf, "type=str id=id_x") + 1,
510 desc = ec_node_desc(node);
511 testres |= EC_TEST_CHECK(
512 !strcmp(ec_node_type(node)->name, "seq") &&
513 !strcmp(ec_node_id(node), EC_NO_ID) &&
514 !strcmp(desc, "<seq>"),
519 testres |= EC_TEST_CHECK(
520 ec_node_get_children_count(node) == 2,
521 "bad children count\n");
522 ret = ec_node_get_child(node, 0, &child, &refs);
523 testres |= EC_TEST_CHECK(ret == 0 &&
525 !strcmp(ec_node_type(child)->name, "str") &&
526 !strcmp(ec_node_id(child), "id_x"),
528 ret = ec_node_get_child(node, 1, &child, &refs);
529 testres |= EC_TEST_CHECK(ret == 0 &&
531 !strcmp(ec_node_type(child)->name, "str") &&
532 !strcmp(ec_node_id(child), "id_y"),
534 ret = ec_node_get_child(node, 2, &child, &refs);
535 testres |= EC_TEST_CHECK(ret != 0,
536 "ret should be != 0");
537 testres |= EC_TEST_CHECK(child == NULL,
538 "child 2 should be NULL");
540 child = ec_node_find(node, "id_x");
541 desc = ec_node_desc(child);
542 testres |= EC_TEST_CHECK(child != NULL &&
543 !strcmp(ec_node_type(child)->name, "str") &&
544 !strcmp(ec_node_id(child), "id_x") &&
549 child = ec_node_find(node, "id_dezdex");
550 testres |= EC_TEST_CHECK(child == NULL,
551 "child with wrong id should be NULL");
553 ret = ec_dict_set(ec_node_attrs(node), "key", "val", NULL);
554 testres |= EC_TEST_CHECK(ret == 0,
555 "cannot set node attribute\n");
557 type = ec_node_type_lookup("seq");
558 testres |= EC_TEST_CHECK(type != NULL &&
559 ec_node_check_type(node, type) == 0,
560 "cannot get seq node type");
561 type = ec_node_type_lookup("str");
562 testres |= EC_TEST_CHECK(type != NULL &&
563 ec_node_check_type(node, type) < 0,
564 "node type should not be str");
569 node = ec_node("deznuindez", EC_NO_ID);
570 testres |= EC_TEST_CHECK(node == NULL,
571 "should not be able to create node\n");
574 expr = ec_node("or", EC_NO_ID);
575 val = ec_node_int(EC_NO_ID, 0, 10, 0);
576 op = ec_node_str(EC_NO_ID, "!");
577 seq = EC_NODE_SEQ(EC_NO_ID,
579 ec_node_clone(expr));
581 if (expr == NULL || val == NULL || seq == NULL)
583 if (ec_node_or_add(expr, ec_node_clone(seq)) < 0)
587 if (ec_node_or_add(expr, ec_node_clone(val)) < 0)
592 testres |= EC_TEST_CHECK_PARSE(expr, 1, "1");
593 testres |= EC_TEST_CHECK_PARSE(expr, 3, "!", "!", "1");
594 testres |= EC_TEST_CHECK_PARSE(expr, -1, "!", "!", "!");
599 /* same loop test, but keep some refs (released later) */
600 expr = ec_node("or", EC_NO_ID);
603 val = ec_node_int(EC_NO_ID, 0, 10, 0);
604 op = ec_node_str(EC_NO_ID, "!");
605 seq = EC_NODE_SEQ(EC_NO_ID,
607 ec_node_clone(expr));
609 if (expr == NULL || val == NULL || seq == NULL)
611 if (ec_node_or_add(expr, ec_node_clone(seq)) < 0)
615 if (ec_node_or_add(expr, ec_node_clone(val)) < 0)
618 testres |= EC_TEST_CHECK_PARSE(expr, 1, "1");
619 testres |= EC_TEST_CHECK_PARSE(expr, 3, "!", "!", "1");
620 testres |= EC_TEST_CHECK_PARSE(expr, -1, "!", "!", "!");
646 static struct ec_test ec_node_test = {
648 .test = ec_node_testcase,
651 EC_TEST_REGISTER(ec_node_test);