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