do not use reserved names.
[protos/libecoli.git] / lib / ecoli_node_subset.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 <string.h>
8 #include <assert.h>
9 #include <stdarg.h>
10 #include <errno.h>
11 #include <stdbool.h>
12
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>
23
24 EC_LOG_TYPE_REGISTER(node_subset);
25
26 struct ec_node_subset {
27         struct ec_node gen;
28         struct ec_node **table;
29         unsigned int len;
30 };
31
32 struct parse_result {
33         size_t parse_len;           /* number of parsed nodes */
34         size_t len;                 /* consumed strings */
35 };
36
37 /* recursively find the longest list of nodes that matches: the state is
38  * updated accordingly. */
39 static int
40 __ec_node_subset_parse(struct parse_result *out, struct ec_node **table,
41                 size_t table_len, struct ec_parse *state,
42                 const struct ec_strvec *strvec)
43 {
44         struct ec_node **child_table;
45         struct ec_strvec *childvec = NULL;
46         size_t i, j, len = 0;
47         struct parse_result best_result, result;
48         struct ec_parse *best_parse = NULL;
49         int ret;
50
51         if (table_len == 0)
52                 return 0;
53
54         memset(&best_result, 0, sizeof(best_result));
55
56         child_table = ec_calloc(table_len - 1, sizeof(*child_table));
57         if (child_table == NULL)
58                 goto fail;
59
60         for (i = 0; i < table_len; i++) {
61                 /* try to parse elt i */
62                 ret = ec_node_parse_child(table[i], state, strvec);
63                 if (ret < 0)
64                         goto fail;
65
66                 if (ret == EC_PARSE_NOMATCH)
67                         continue;
68
69                 /* build a new table without elt i */
70                 for (j = 0; j < table_len; j++) {
71                         if (j < i)
72                                 child_table[j] = table[j];
73                         else if (j > i)
74                                 child_table[j - 1] = table[j];
75                 }
76
77                 /* build a new strvec (ret is the len of matched strvec) */
78                 len = ret;
79                 childvec = ec_strvec_ndup(strvec, len,
80                                         ec_strvec_len(strvec) - len);
81                 if (childvec == NULL)
82                         goto fail;
83
84                 memset(&result, 0, sizeof(result));
85                 ret = __ec_node_subset_parse(&result, child_table,
86                                         table_len - 1, state, childvec);
87                 ec_strvec_free(childvec);
88                 childvec = NULL;
89                 if (ret < 0)
90                         goto fail;
91
92                 /* if result is not the best, ignore */
93                 if (result.parse_len < best_result.parse_len) {
94                         memset(&result, 0, sizeof(result));
95                         ec_parse_del_last_child(state);
96                         continue;
97                 }
98
99                 /* replace the previous best result */
100                 ec_parse_free(best_parse);
101                 best_parse = ec_parse_get_last_child(state);
102                 ec_parse_unlink_child(state, best_parse);
103
104                 best_result.parse_len = result.parse_len + 1;
105                 best_result.len = len + result.len;
106
107                 memset(&result, 0, sizeof(result));
108         }
109
110         *out = best_result;
111         ec_free(child_table);
112         if (best_parse != NULL)
113                 ec_parse_link_child(state, best_parse);
114
115         return 0;
116
117  fail:
118         ec_parse_free(best_parse);
119         ec_strvec_free(childvec);
120         ec_free(child_table);
121         return -1;
122 }
123
124 static int
125 ec_node_subset_parse(const struct ec_node *gen_node,
126                 struct ec_parse *state,
127                 const struct ec_strvec *strvec)
128 {
129         struct ec_node_subset *node = (struct ec_node_subset *)gen_node;
130         struct ec_parse *parse = NULL;
131         struct parse_result result;
132         int ret;
133
134         memset(&result, 0, sizeof(result));
135
136         ret = __ec_node_subset_parse(&result, node->table,
137                                 node->len, state, strvec);
138         if (ret < 0)
139                 goto fail;
140
141         /* if no child node matches, return a matching empty strvec */
142         if (result.parse_len == 0)
143                 return 0;
144
145         return result.len;
146
147  fail:
148         ec_parse_free(parse);
149         return ret;
150 }
151
152 static int
153 __ec_node_subset_complete(struct ec_node **table, size_t table_len,
154                         struct ec_comp *comp,
155                         const struct ec_strvec *strvec)
156 {
157         struct ec_parse *parse = ec_comp_get_state(comp);
158         struct ec_strvec *childvec = NULL;
159         struct ec_node *save;
160         size_t i, len;
161         int ret;
162
163         /*
164          * example with table = [a, b, c]
165          * subset_complete([a,b,c], strvec) returns:
166          *   complete(a, strvec) + complete(b, strvec) + complete(c, strvec) +
167          *   + __subset_complete([b, c], childvec) if a matches
168          *   + __subset_complete([a, c], childvec) if b matches
169          *   + __subset_complete([a, b], childvec) if c matches
170          */
171
172         /* first, try to complete with each node of the table */
173         for (i = 0; i < table_len; i++) {
174                 if (table[i] == NULL)
175                         continue;
176
177                 ret = ec_node_complete_child(table[i],
178                                         comp, strvec);
179                 if (ret < 0)
180                         goto fail;
181         }
182
183         /* then, if a node matches, advance in strvec and try to complete with
184          * all the other nodes */
185         for (i = 0; i < table_len; i++) {
186                 if (table[i] == NULL)
187                         continue;
188
189                 ret = ec_node_parse_child(table[i], parse, strvec);
190                 if (ret < 0)
191                         goto fail;
192
193                 if (ret == EC_PARSE_NOMATCH)
194                         continue;
195
196                 len = ret;
197                 childvec = ec_strvec_ndup(strvec, len,
198                                         ec_strvec_len(strvec) - len);
199                 if (childvec == NULL) {
200                         ec_parse_del_last_child(parse);
201                         goto fail;
202                 }
203
204                 save = table[i];
205                 table[i] = NULL;
206                 ret = __ec_node_subset_complete(table, table_len,
207                                                 comp, childvec);
208                 table[i] = save;
209                 ec_strvec_free(childvec);
210                 childvec = NULL;
211                 ec_parse_del_last_child(parse);
212
213                 if (ret < 0)
214                         goto fail;
215         }
216
217         return 0;
218
219 fail:
220         return -1;
221 }
222
223 static int
224 ec_node_subset_complete(const struct ec_node *gen_node,
225                         struct ec_comp *comp,
226                         const struct ec_strvec *strvec)
227 {
228         struct ec_node_subset *node = (struct ec_node_subset *)gen_node;
229
230         return __ec_node_subset_complete(node->table, node->len, comp,
231                                         strvec);
232 }
233
234 static void ec_node_subset_free_priv(struct ec_node *gen_node)
235 {
236         struct ec_node_subset *node = (struct ec_node_subset *)gen_node;
237         size_t i;
238
239         for (i = 0; i < node->len; i++)
240                 ec_node_free(node->table[i]);
241         ec_free(node->table);
242 }
243
244 static size_t
245 ec_node_subset_get_children_count(const struct ec_node *gen_node)
246 {
247         struct ec_node_subset *node = (struct ec_node_subset *)gen_node;
248         return node->len;
249 }
250
251 static int
252 ec_node_subset_get_child(const struct ec_node *gen_node, size_t i,
253                         struct ec_node **child, unsigned int *refs)
254 {
255         struct ec_node_subset *node = (struct ec_node_subset *)gen_node;
256
257         if (i >= node->len)
258                 return -1;
259
260         *child = node->table[i];
261         *refs = 1;
262         return 0;
263 }
264
265 static struct ec_node_type ec_node_subset_type = {
266         .name = "subset",
267         .parse = ec_node_subset_parse,
268         .complete = ec_node_subset_complete,
269         .size = sizeof(struct ec_node_subset),
270         .free_priv = ec_node_subset_free_priv,
271         .get_children_count = ec_node_subset_get_children_count,
272         .get_child = ec_node_subset_get_child,
273 };
274
275 EC_NODE_TYPE_REGISTER(ec_node_subset_type);
276
277 int ec_node_subset_add(struct ec_node *gen_node, struct ec_node *child)
278 {
279         struct ec_node_subset *node = (struct ec_node_subset *)gen_node;
280         struct ec_node **table;
281
282         assert(node != NULL); // XXX specific assert for it, like in libyang
283
284         if (child == NULL) {
285                 errno = EINVAL;
286                 goto fail;
287         }
288
289         if (ec_node_check_type(gen_node, &ec_node_subset_type) < 0)
290                 goto fail;
291
292         table = ec_realloc(node->table, (node->len + 1) * sizeof(*node->table));
293         if (table == NULL) {
294                 ec_node_free(child);
295                 return -1;
296         }
297
298         node->table = table;
299         table[node->len] = child;
300         node->len++;
301
302         return 0;
303
304 fail:
305         ec_node_free(child);
306         return -1;
307 }
308
309 struct ec_node *__ec_node_subset(const char *id, ...)
310 {
311         struct ec_node *gen_node = NULL;
312         struct ec_node_subset *node = NULL;
313         struct ec_node *child;
314         va_list ap;
315         int fail = 0;
316
317         va_start(ap, id);
318
319         gen_node = ec_node_from_type(&ec_node_subset_type, id);
320         node = (struct ec_node_subset *)gen_node;
321         if (node == NULL)
322                 fail = 1;;
323
324         for (child = va_arg(ap, struct ec_node *);
325              child != EC_NODE_ENDLIST;
326              child = va_arg(ap, struct ec_node *)) {
327
328                 /* on error, don't quit the loop to avoid leaks */
329                 if (fail == 1 || child == NULL ||
330                                 ec_node_subset_add(gen_node, child) < 0) {
331                         fail = 1;
332                         ec_node_free(child);
333                 }
334         }
335
336         if (fail == 1)
337                 goto fail;
338
339         va_end(ap);
340         return gen_node;
341
342 fail:
343         ec_node_free(gen_node); /* will also free children */
344         va_end(ap);
345         return NULL;
346 }
347
348 /* LCOV_EXCL_START */
349 static int ec_node_subset_testcase(void)
350 {
351         struct ec_node *node;
352         int testres = 0;
353
354         node = EC_NODE_SUBSET(EC_NO_ID,
355                 EC_NODE_OR(EC_NO_ID,
356                         ec_node_str(EC_NO_ID, "foo"),
357                         ec_node_str(EC_NO_ID, "bar")),
358                 ec_node_str(EC_NO_ID, "bar"),
359                 ec_node_str(EC_NO_ID, "toto")
360         );
361         if (node == NULL) {
362                 EC_LOG(EC_LOG_ERR, "cannot create node\n");
363                 return -1;
364         }
365         testres |= EC_TEST_CHECK_PARSE(node, 0);
366         testres |= EC_TEST_CHECK_PARSE(node, 1, "foo");
367         testres |= EC_TEST_CHECK_PARSE(node, 1, "bar");
368         testres |= EC_TEST_CHECK_PARSE(node, 2, "foo", "bar", "titi");
369         testres |= EC_TEST_CHECK_PARSE(node, 3, "bar", "foo", "toto");
370         testres |= EC_TEST_CHECK_PARSE(node, 1, "foo", "foo");
371         testres |= EC_TEST_CHECK_PARSE(node, 2, "bar", "bar");
372         testres |= EC_TEST_CHECK_PARSE(node, 2, "bar", "foo");
373         testres |= EC_TEST_CHECK_PARSE(node, 0, " ");
374         testres |= EC_TEST_CHECK_PARSE(node, 0, "foox");
375         ec_node_free(node);
376
377         /* test completion */
378         node = EC_NODE_SUBSET(EC_NO_ID,
379                 ec_node_str(EC_NO_ID, "foo"),
380                 ec_node_str(EC_NO_ID, "bar"),
381                 ec_node_str(EC_NO_ID, "bar2"),
382                 ec_node_str(EC_NO_ID, "toto"),
383                 ec_node_str(EC_NO_ID, "titi")
384         );
385         if (node == NULL) {
386                 EC_LOG(EC_LOG_ERR, "cannot create node\n");
387                 return -1;
388         }
389         testres |= EC_TEST_CHECK_COMPLETE(node,
390                 "", EC_NODE_ENDLIST,
391                 "foo", "bar", "bar2", "toto", "titi", EC_NODE_ENDLIST);
392         testres |= EC_TEST_CHECK_COMPLETE(node,
393                 "", EC_NODE_ENDLIST,
394                 "bar2", "bar", "foo", "toto", "titi", EC_NODE_ENDLIST);
395         testres |= EC_TEST_CHECK_COMPLETE(node,
396                 "bar", "bar2", "", EC_NODE_ENDLIST,
397                 "foo", "toto", "titi", EC_NODE_ENDLIST);
398         testres |= EC_TEST_CHECK_COMPLETE(node,
399                 "f", EC_NODE_ENDLIST,
400                 "foo", EC_NODE_ENDLIST);
401         testres |= EC_TEST_CHECK_COMPLETE(node,
402                 "b", EC_NODE_ENDLIST,
403                 "bar", "bar2", EC_NODE_ENDLIST);
404         testres |= EC_TEST_CHECK_COMPLETE(node,
405                 "bar", EC_NODE_ENDLIST,
406                 "bar", "bar2", EC_NODE_ENDLIST);
407         testres |= EC_TEST_CHECK_COMPLETE(node,
408                 "bar", "b", EC_NODE_ENDLIST,
409                 "bar2", EC_NODE_ENDLIST);
410         testres |= EC_TEST_CHECK_COMPLETE(node,
411                 "t", EC_NODE_ENDLIST,
412                 "toto", "titi", EC_NODE_ENDLIST);
413         testres |= EC_TEST_CHECK_COMPLETE(node,
414                 "to", EC_NODE_ENDLIST,
415                 "toto", EC_NODE_ENDLIST);
416         testres |= EC_TEST_CHECK_COMPLETE(node,
417                 "x", EC_NODE_ENDLIST,
418                 EC_NODE_ENDLIST);
419         ec_node_free(node);
420
421         return testres;
422 }
423 /* LCOV_EXCL_STOP */
424
425 static struct ec_test ec_node_subset_test = {
426         .name = "node_subset",
427         .test = ec_node_subset_testcase,
428 };
429
430 EC_TEST_REGISTER(ec_node_subset_test);