1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright 2016, Olivier MATZ <zer0@droids-corp.org>
13 #include <ecoli_malloc.h>
14 #include <ecoli_log.h>
15 #include <ecoli_strvec.h>
16 #include <ecoli_node.h>
17 #include <ecoli_parse.h>
18 #include <ecoli_complete.h>
19 #include <ecoli_node_subset.h>
20 #include <ecoli_node_str.h>
21 #include <ecoli_node_or.h>
22 #include <ecoli_test.h>
24 EC_LOG_TYPE_REGISTER(node_subset);
26 struct ec_node_subset {
27 struct ec_node **table;
32 size_t parse_len; /* number of parsed nodes */
33 size_t len; /* consumed strings */
36 /* recursively find the longest list of nodes that matches: the state is
37 * updated accordingly. */
39 __ec_node_subset_parse(struct parse_result *out, struct ec_node **table,
40 size_t table_len, struct ec_pnode *state,
41 const struct ec_strvec *strvec)
43 struct ec_node **child_table;
44 struct ec_strvec *childvec = NULL;
46 struct parse_result best_result, result;
47 struct ec_pnode *best_parse = NULL;
53 memset(&best_result, 0, sizeof(best_result));
55 child_table = ec_calloc(table_len - 1, sizeof(*child_table));
56 if (child_table == NULL)
59 for (i = 0; i < table_len; i++) {
60 /* try to parse elt i */
61 ret = ec_parse_child(table[i], state, strvec);
65 if (ret == EC_PARSE_NOMATCH)
68 /* build a new table without elt i */
69 for (j = 0; j < table_len; j++) {
71 child_table[j] = table[j];
73 child_table[j - 1] = table[j];
76 /* build a new strvec (ret is the len of matched strvec) */
78 childvec = ec_strvec_ndup(strvec, len,
79 ec_strvec_len(strvec) - len);
83 memset(&result, 0, sizeof(result));
84 ret = __ec_node_subset_parse(&result, child_table,
85 table_len - 1, state, childvec);
86 ec_strvec_free(childvec);
91 /* if result is not the best, ignore */
92 if (result.parse_len < best_result.parse_len) {
93 memset(&result, 0, sizeof(result));
94 ec_pnode_del_last_child(state);
98 /* replace the previous best result */
99 ec_pnode_free(best_parse);
100 best_parse = ec_pnode_get_last_child(state);
101 ec_pnode_unlink_child(state, best_parse);
103 best_result.parse_len = result.parse_len + 1;
104 best_result.len = len + result.len;
106 memset(&result, 0, sizeof(result));
110 ec_free(child_table);
111 if (best_parse != NULL)
112 ec_pnode_link_child(state, best_parse);
117 ec_pnode_free(best_parse);
118 ec_strvec_free(childvec);
119 ec_free(child_table);
124 ec_node_subset_parse(const struct ec_node *node,
125 struct ec_pnode *state,
126 const struct ec_strvec *strvec)
128 struct ec_node_subset *priv = ec_node_priv(node);
129 struct ec_pnode *parse = NULL;
130 struct parse_result result;
133 memset(&result, 0, sizeof(result));
135 ret = __ec_node_subset_parse(&result, priv->table,
136 priv->len, state, strvec);
140 /* if no child node matches, return a matching empty strvec */
141 if (result.parse_len == 0)
147 ec_pnode_free(parse);
152 __ec_node_subset_complete(struct ec_node **table, size_t table_len,
153 struct ec_comp *comp,
154 const struct ec_strvec *strvec)
156 struct ec_pnode *parse = ec_comp_get_state(comp);
157 struct ec_strvec *childvec = NULL;
158 struct ec_node *save;
163 * example with table = [a, b, c]
164 * subset_complete([a,b,c], strvec) returns:
165 * complete(a, strvec) + complete(b, strvec) + complete(c, strvec) +
166 * + __subset_complete([b, c], childvec) if a matches
167 * + __subset_complete([a, c], childvec) if b matches
168 * + __subset_complete([a, b], childvec) if c matches
171 /* first, try to complete with each node of the table */
172 for (i = 0; i < table_len; i++) {
173 if (table[i] == NULL)
176 ret = ec_complete_child(table[i],
182 /* then, if a node matches, advance in strvec and try to complete with
183 * all the other nodes */
184 for (i = 0; i < table_len; i++) {
185 if (table[i] == NULL)
188 ret = ec_parse_child(table[i], parse, strvec);
192 if (ret == EC_PARSE_NOMATCH)
196 childvec = ec_strvec_ndup(strvec, len,
197 ec_strvec_len(strvec) - len);
198 if (childvec == NULL) {
199 ec_pnode_del_last_child(parse);
205 ret = __ec_node_subset_complete(table, table_len,
208 ec_strvec_free(childvec);
210 ec_pnode_del_last_child(parse);
223 ec_node_subset_complete(const struct ec_node *node,
224 struct ec_comp *comp,
225 const struct ec_strvec *strvec)
227 struct ec_node_subset *priv = ec_node_priv(node);
229 return __ec_node_subset_complete(priv->table, priv->len, comp,
233 static void ec_node_subset_free_priv(struct ec_node *node)
235 struct ec_node_subset *priv = ec_node_priv(node);
238 for (i = 0; i < priv->len; i++)
239 ec_node_free(priv->table[i]);
240 ec_free(priv->table);
244 ec_node_subset_get_children_count(const struct ec_node *node)
246 struct ec_node_subset *priv = ec_node_priv(node);
251 ec_node_subset_get_child(const struct ec_node *node, size_t i,
252 struct ec_node **child, unsigned int *refs)
254 struct ec_node_subset *priv = ec_node_priv(node);
259 *child = priv->table[i];
264 static struct ec_node_type ec_node_subset_type = {
266 .parse = ec_node_subset_parse,
267 .complete = ec_node_subset_complete,
268 .size = sizeof(struct ec_node_subset),
269 .free_priv = ec_node_subset_free_priv,
270 .get_children_count = ec_node_subset_get_children_count,
271 .get_child = ec_node_subset_get_child,
274 EC_NODE_TYPE_REGISTER(ec_node_subset_type);
276 int ec_node_subset_add(struct ec_node *node, struct ec_node *child)
278 struct ec_node_subset *priv = ec_node_priv(node);
279 struct ec_node **table;
281 assert(node != NULL); // XXX specific assert for it, like in libyang
288 if (ec_node_check_type(node, &ec_node_subset_type) < 0)
291 table = ec_realloc(priv->table, (priv->len + 1) * sizeof(*priv->table));
298 table[priv->len] = child;
308 struct ec_node *__ec_node_subset(const char *id, ...)
310 struct ec_node *node = NULL;
311 struct ec_node *child;
317 node = ec_node_from_type(&ec_node_subset_type, id);
321 for (child = va_arg(ap, struct ec_node *);
323 child = va_arg(ap, struct ec_node *)) {
325 /* on error, don't quit the loop to avoid leaks */
326 if (fail == 1 || child == NULL ||
327 ec_node_subset_add(node, child) < 0) {
340 ec_node_free(node); /* will also free children */
345 /* LCOV_EXCL_START */
346 static int ec_node_subset_testcase(void)
348 struct ec_node *node;
351 node = EC_NODE_SUBSET(EC_NO_ID,
353 ec_node_str(EC_NO_ID, "foo"),
354 ec_node_str(EC_NO_ID, "bar")),
355 ec_node_str(EC_NO_ID, "bar"),
356 ec_node_str(EC_NO_ID, "toto")
359 EC_LOG(EC_LOG_ERR, "cannot create node\n");
362 testres |= EC_TEST_CHECK_PARSE(node, 0);
363 testres |= EC_TEST_CHECK_PARSE(node, 1, "foo");
364 testres |= EC_TEST_CHECK_PARSE(node, 1, "bar");
365 testres |= EC_TEST_CHECK_PARSE(node, 2, "foo", "bar", "titi");
366 testres |= EC_TEST_CHECK_PARSE(node, 3, "bar", "foo", "toto");
367 testres |= EC_TEST_CHECK_PARSE(node, 1, "foo", "foo");
368 testres |= EC_TEST_CHECK_PARSE(node, 2, "bar", "bar");
369 testres |= EC_TEST_CHECK_PARSE(node, 2, "bar", "foo");
370 testres |= EC_TEST_CHECK_PARSE(node, 0, " ");
371 testres |= EC_TEST_CHECK_PARSE(node, 0, "foox");
374 /* test completion */
375 node = EC_NODE_SUBSET(EC_NO_ID,
376 ec_node_str(EC_NO_ID, "foo"),
377 ec_node_str(EC_NO_ID, "bar"),
378 ec_node_str(EC_NO_ID, "bar2"),
379 ec_node_str(EC_NO_ID, "toto"),
380 ec_node_str(EC_NO_ID, "titi")
383 EC_LOG(EC_LOG_ERR, "cannot create node\n");
386 testres |= EC_TEST_CHECK_COMPLETE(node,
388 "foo", "bar", "bar2", "toto", "titi", EC_VA_END);
389 testres |= EC_TEST_CHECK_COMPLETE(node,
391 "bar2", "bar", "foo", "toto", "titi", EC_VA_END);
392 testres |= EC_TEST_CHECK_COMPLETE(node,
393 "bar", "bar2", "", EC_VA_END,
394 "foo", "toto", "titi", EC_VA_END);
395 testres |= EC_TEST_CHECK_COMPLETE(node,
398 testres |= EC_TEST_CHECK_COMPLETE(node,
400 "bar", "bar2", EC_VA_END);
401 testres |= EC_TEST_CHECK_COMPLETE(node,
403 "bar", "bar2", EC_VA_END);
404 testres |= EC_TEST_CHECK_COMPLETE(node,
405 "bar", "b", EC_VA_END,
407 testres |= EC_TEST_CHECK_COMPLETE(node,
409 "toto", "titi", EC_VA_END);
410 testres |= EC_TEST_CHECK_COMPLETE(node,
413 testres |= EC_TEST_CHECK_COMPLETE(node,
422 static struct ec_test ec_node_subset_test = {
423 .name = "node_subset",
424 .test = ec_node_subset_testcase,
427 EC_TEST_REGISTER(ec_node_subset_test);