2 * Copyright (c) 2016, Olivier MATZ <zer0@droids-corp.org>
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are met:
7 * * Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * * Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * * Neither the name of the University of California, Berkeley nor the
13 * names of its contributors may be used to endorse or promote products
14 * derived from this software without specific prior written permission.
16 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND ANY
17 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19 * DISCLAIMED. IN NO EVENT SHALL THE REGENTS AND CONTRIBUTORS BE LIABLE FOR ANY
20 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 #include <ecoli_malloc.h>
35 #include <ecoli_strvec.h>
36 #include <ecoli_keyval.h>
37 #include <ecoli_log.h>
38 #include <ecoli_node.h>
40 static struct ec_node_type_list node_type_list =
41 TAILQ_HEAD_INITIALIZER(node_type_list);
43 struct ec_node_type *ec_node_type_lookup(const char *name)
45 struct ec_node_type *type;
47 TAILQ_FOREACH(type, &node_type_list, next) {
48 if (!strcmp(name, type->name))
55 int ec_node_type_register(struct ec_node_type *type)
57 if (ec_node_type_lookup(type->name) != NULL)
59 if (type->size < sizeof(struct ec_node))
62 TAILQ_INSERT_TAIL(&node_type_list, type, next);
67 void ec_node_type_dump(FILE *out)
69 struct ec_node_type *type;
71 TAILQ_FOREACH(type, &node_type_list, next)
72 fprintf(out, "%s\n", type->name);
75 struct ec_node *__ec_node_new(const struct ec_node_type *type, const char *id)
77 struct ec_node *node = NULL;
80 ec_log(EC_LOG_DEBUG, "create node type=%s id=%s\n", type->name, id);
82 node = ec_calloc(1, type->size);
86 TAILQ_INIT(&node->children);
91 node->id = ec_strdup(id);
96 snprintf(buf, sizeof(buf), "<%s>", type->name);
97 node->desc = ec_strdup(buf); // XXX ec_asprintf ?
98 if (node->desc == NULL)
101 node->attrs = ec_keyval_new();
102 if (node->attrs == NULL)
112 struct ec_node *ec_node_new(const char *typename, const char *id)
114 struct ec_node_type *type;
116 type = ec_node_type_lookup(typename);
118 ec_log(EC_LOG_ERR, "type=%s does not exist\n", typename);
122 return __ec_node_new(type, id);
125 void ec_node_free(struct ec_node *node)
130 assert(node->refcnt > 0);
132 if (--node->refcnt > 0)
135 if (node->type != NULL && node->type->free_priv != NULL)
136 node->type->free_priv(node);
139 ec_free(node->attrs);
143 struct ec_node *ec_node_clone(struct ec_node *node)
150 struct ec_node *ec_node_find(struct ec_node *node, const char *id)
152 struct ec_node *child, *ret;
153 const char *node_id = ec_node_id(node);
155 if (id != NULL && node_id != NULL && !strcmp(node_id, id))
158 TAILQ_FOREACH(child, &node->children, next) {
159 ret = ec_node_find(child, id);
167 struct ec_keyval *ec_node_attrs(const struct ec_node *node)
172 const char *ec_node_id(const struct ec_node *node)
177 struct ec_node *ec_node_parent(const struct ec_node *node)
182 static void __ec_node_dump(FILE *out,
183 const struct ec_node *node, size_t indent)
185 struct ec_node *child;
187 const char *id = "None", *typename = "None";
189 if (node->id != NULL)
191 typename = node->type->name;
194 for (i = 0; i < indent; i++) {
201 fprintf(out, "node_type=%s id=%s\n", typename, id);
202 TAILQ_FOREACH(child, &node->children, next)
203 __ec_node_dump(out, child, indent + 2);
206 void ec_node_dump(FILE *out, const struct ec_node *node)
208 fprintf(out, "------------------- node dump:\n"); //XXX
211 fprintf(out, "node is NULL\n");
215 __ec_node_dump(out, node, 0);
218 struct ec_parsed *ec_node_parse(struct ec_node *node, const char *str)
220 struct ec_strvec *strvec = NULL;
221 struct ec_parsed *parsed;
224 strvec = ec_strvec_new();
228 if (ec_strvec_add(strvec, str) < 0)
231 parsed = ec_node_parse_strvec(node, strvec);
235 ec_strvec_free(strvec);
239 ec_strvec_free(strvec);
243 struct ec_parsed *ec_node_parse_strvec(struct ec_node *node,
244 const struct ec_strvec *strvec)
246 struct ec_parsed *parsed;
249 /* build the node if required */
250 if (node->type->build != NULL) {
251 if ((node->flags & EC_NODE_F_BUILT) == 0) {
252 ret = node->type->build(node);
259 node->flags |= EC_NODE_F_BUILT;
261 if (node->type->parse == NULL) {
266 parsed = node->type->parse(node, strvec);
272 struct ec_parsed *ec_parsed_new(void)
274 struct ec_parsed *parsed = NULL;
276 parsed = ec_calloc(1, sizeof(*parsed));
280 TAILQ_INIT(&parsed->children);
288 void ec_parsed_set_match(struct ec_parsed *parsed,
289 const struct ec_node *node, struct ec_strvec *strvec)
292 parsed->strvec = strvec;
295 void ec_parsed_free_children(struct ec_parsed *parsed)
297 struct ec_parsed *child;
302 while (!TAILQ_EMPTY(&parsed->children)) {
303 child = TAILQ_FIRST(&parsed->children);
304 TAILQ_REMOVE(&parsed->children, child, next);
305 ec_parsed_free(child);
309 void ec_parsed_free(struct ec_parsed *parsed)
314 ec_parsed_free_children(parsed);
315 ec_strvec_free(parsed->strvec);
319 static void __ec_parsed_dump(FILE *out,
320 const struct ec_parsed *parsed, size_t indent)
322 struct ec_parsed *child;
323 const struct ec_strvec *vec;
325 const char *id = "None", *typename = "None";
327 if (parsed->node != NULL) {
328 if (parsed->node->id != NULL)
329 id = parsed->node->id;
330 typename = parsed->node->type->name;
334 for (i = 0; i < indent; i++) {
341 fprintf(out, "node_type=%s id=%s vec=[", typename, id);
342 vec = ec_parsed_strvec(parsed);
343 for (i = 0; i < ec_strvec_len(vec); i++)
344 fprintf(out, "%s<%s>",
346 ec_strvec_val(vec, i));
349 TAILQ_FOREACH(child, &parsed->children, next)
350 __ec_parsed_dump(out, child, indent + 2);
353 void ec_parsed_dump(FILE *out, const struct ec_parsed *parsed)
355 fprintf(out, "------------------- parsed dump:\n"); //XXX
357 if (parsed == NULL) {
358 fprintf(out, "parsed is NULL, error in parse\n");
361 if (!ec_parsed_matches(parsed)) {
362 fprintf(out, "no match\n");
366 __ec_parsed_dump(out, parsed, 0);
369 void ec_parsed_add_child(struct ec_parsed *parsed,
370 struct ec_parsed *child)
372 TAILQ_INSERT_TAIL(&parsed->children, child, next);
375 void ec_parsed_del_child(struct ec_parsed *parsed,
376 struct ec_parsed *child)
378 TAILQ_REMOVE(&parsed->children, child, next);
381 struct ec_parsed *ec_parsed_find_first(struct ec_parsed *parsed,
384 struct ec_parsed *child, *ret;
389 if (parsed->node != NULL &&
390 parsed->node->id != NULL &&
391 !strcmp(parsed->node->id, id))
394 TAILQ_FOREACH(child, &parsed->children, next) {
395 ret = ec_parsed_find_first(child, id);
403 const struct ec_strvec *ec_parsed_strvec(
404 const struct ec_parsed *parsed)
406 if (parsed == NULL || parsed->strvec == NULL)
409 return parsed->strvec;
412 /* number of parsed strings in the vector */
413 size_t ec_parsed_len(const struct ec_parsed *parsed)
415 if (parsed == NULL || parsed->strvec == NULL)
418 return ec_strvec_len(parsed->strvec);
421 size_t ec_parsed_matches(const struct ec_parsed *parsed)
426 if (parsed->node == NULL && TAILQ_EMPTY(&parsed->children))
432 struct ec_completed *ec_completed_new(void)
434 struct ec_completed *completed = NULL;
436 completed = ec_calloc(1, sizeof(*completed));
437 if (completed == NULL)
440 TAILQ_INIT(&completed->elts);
441 completed->count_match = 0;
446 struct ec_completed_elt *ec_completed_elt_new(const struct ec_node *node,
449 struct ec_completed_elt *elt = NULL;
451 elt = ec_calloc(1, sizeof(*elt));
457 elt->add = ec_strdup(add);
458 if (elt->add == NULL) {
459 ec_completed_elt_free(elt);
467 /* XXX define when to use ec_node_complete() or node->complete()
469 * suggestion: node->op() is internal, user calls the function
470 * other idea: have 2 functions
472 struct ec_completed *ec_node_complete(struct ec_node *node,
475 struct ec_strvec *strvec = NULL;
476 struct ec_completed *completed;
479 strvec = ec_strvec_new();
483 if (ec_strvec_add(strvec, str) < 0)
486 completed = ec_node_complete_strvec(node, strvec);
487 if (completed == NULL)
490 ec_strvec_free(strvec);
494 ec_strvec_free(strvec);
498 /* default completion function: return a no-match element */
499 struct ec_completed *ec_node_default_complete(const struct ec_node *gen_node,
500 const struct ec_strvec *strvec)
502 struct ec_completed *completed;
503 struct ec_completed_elt *completed_elt;
507 completed = ec_completed_new();
508 if (completed == NULL)
511 completed_elt = ec_completed_elt_new(gen_node, NULL);
512 if (completed_elt == NULL) {
513 ec_completed_free(completed);
517 ec_completed_add_elt(completed, completed_elt);
522 struct ec_completed *ec_node_complete_strvec(struct ec_node *node,
523 const struct ec_strvec *strvec)
527 /* build the node if required */
528 if (node->type->build != NULL) {
529 if ((node->flags & EC_NODE_F_BUILT) == 0) {
530 ret = node->type->build(node);
537 node->flags |= EC_NODE_F_BUILT;
539 if (node->type->complete == NULL) {
544 return node->type->complete(node, strvec);
547 /* count the number of identical chars at the beginning of 2 strings */
548 static size_t strcmp_count(const char *s1, const char *s2)
552 while (s1[i] && s2[i] && s1[i] == s2[i])
558 void ec_completed_add_elt(
559 struct ec_completed *completed, struct ec_completed_elt *elt)
563 TAILQ_INSERT_TAIL(&completed->elts, elt, next);
565 if (elt->add != NULL)
566 completed->count_match++;
567 if (elt->add != NULL) {
568 if (completed->smallest_start == NULL) {
569 completed->smallest_start = ec_strdup(elt->add);
571 n = strcmp_count(elt->add,
572 completed->smallest_start);
573 completed->smallest_start[n] = '\0';
578 void ec_completed_elt_free(struct ec_completed_elt *elt)
584 void ec_completed_merge(struct ec_completed *completed1,
585 struct ec_completed *completed2)
587 struct ec_completed_elt *elt;
589 assert(completed1 != NULL);
590 assert(completed2 != NULL);
592 while (!TAILQ_EMPTY(&completed2->elts)) {
593 elt = TAILQ_FIRST(&completed2->elts);
594 TAILQ_REMOVE(&completed2->elts, elt, next);
595 ec_completed_add_elt(completed1, elt);
598 ec_completed_free(completed2);
601 void ec_completed_free(struct ec_completed *completed)
603 struct ec_completed_elt *elt;
605 if (completed == NULL)
608 while (!TAILQ_EMPTY(&completed->elts)) {
609 elt = TAILQ_FIRST(&completed->elts);
610 TAILQ_REMOVE(&completed->elts, elt, next);
611 ec_completed_elt_free(elt);
613 ec_free(completed->smallest_start);
617 void ec_completed_dump(FILE *out, const struct ec_completed *completed)
619 struct ec_completed_elt *elt;
621 if (completed == NULL || completed->count == 0) {
622 fprintf(out, "no completion\n");
626 fprintf(out, "completion: count=%u match=%u smallest_start=<%s>\n",
627 completed->count, completed->count_match,
628 completed->smallest_start);
630 TAILQ_FOREACH(elt, &completed->elts, next) {
631 fprintf(out, "add=<%s>, node=%p, node_type=%s\n",
632 elt->add, elt->node, elt->node->type->name);
636 const char *ec_completed_smallest_start(
637 const struct ec_completed *completed)
639 if (completed == NULL || completed->smallest_start == NULL)
642 return completed->smallest_start;
645 unsigned int ec_completed_count(
646 const struct ec_completed *completed,
647 enum ec_completed_filter_flags flags)
649 unsigned int count = 0;
651 if (completed == NULL)
654 if (flags & EC_MATCH)
655 count += completed->count_match;
656 if (flags & EC_NO_MATCH)
657 count += (completed->count - completed->count_match); //XXX
662 struct ec_completed_iter *
663 ec_completed_iter_new(struct ec_completed *completed,
664 enum ec_completed_filter_flags flags)
666 struct ec_completed_iter *iter;
668 iter = ec_calloc(1, sizeof(*iter));
672 iter->completed = completed;
679 const struct ec_completed_elt *ec_completed_iter_next(
680 struct ec_completed_iter *iter)
682 if (iter->completed == NULL)
686 if (iter->cur == NULL) {
687 iter->cur = TAILQ_FIRST(&iter->completed->elts);
689 iter->cur = TAILQ_NEXT(iter->cur, next);
692 if (iter->cur == NULL)
695 if (iter->cur->add == NULL &&
696 (iter->flags & EC_NO_MATCH))
699 if (iter->cur->add != NULL &&
700 (iter->flags & EC_MATCH))
703 } while (iter->cur != NULL);
708 void ec_completed_iter_free(struct ec_completed_iter *iter)
713 const char *ec_node_desc(const struct ec_node *node)
715 if (node->type->desc != NULL)
716 return node->type->desc(node);