/*
- * Command DFA module.
- * Provides a DFA data structure and associated functions for manipulating it.
- * Used to match user command line input.
+ * CLI graph handling
*
- * @author Quentin Young <qlyoung@cumulusnetworks.com>
+ * --
+ * Copyright (C) 2016 Cumulus Networks, Inc.
+ * Copyright (C) 1997, 98, 99 Kunihiro Ishiguro
+ * Copyright (C) 2013 by Open Source Routing.
+ * Copyright (C) 2013 by Internet Systems Consortium, Inc. ("ISC")
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the Free
+ * Software Foundation; either version 2 of the License, or (at your option)
+ * any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
+ * more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; see the file COPYING; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
*/
-#include "command_graph.h"
#include <zebra.h>
-#include "memory.h"
-
-struct graph_node *
-add_node(struct graph_node *parent, struct graph_node *child)
-{
- vector_set(parent->children, child);
- child->refs++;
- return child;
-}
-
-int
-cmp_node(struct graph_node *first, struct graph_node *second)
-{
- // compare types
- if (first->type != second->type) return 0;
-
- switch (first->type) {
- case WORD_GN:
- case VARIABLE_GN:
- if (first->text && second->text) {
- if (strcmp(first->text, second->text)) return 0;
- }
- else if (first->text != second->text) return 0;
- break;
- case RANGE_GN:
- if (first->min != second->min || first->max != second->max)
- return 0;
- break;
- case NUMBER_GN:
- if (first->value != second->value) return 0;
- break;
- /* selectors and options should be equal if all paths are equal,
- * but the graph isomorphism problem is not solvable in polynomial
- * time so we consider selectors and options inequal in all cases
- */
- case SELECTOR_GN:
- case OPTION_GN:
- return 0;
- /* end nodes are always considered equal, since each node may only
- * have one at a time
- */
- case START_GN:
- case END_GN:
- case NUL_GN:
- default:
- break;
- }
-
- return 1;
-}
-
-struct graph_node *
-new_node(enum graph_node_type type)
-{
- struct graph_node *node =
- XMALLOC(MTYPE_CMD_TOKENS, sizeof(struct graph_node));
-
- node->type = type;
- node->children = vector_init(VECTOR_MIN_SIZE);
- node->end = NULL;
- node->text = NULL;
- node->element = NULL;
- node->arg = NULL;
- node->is_start = 0;
- node->value = 0;
- node->min = 0;
- node->max = 0;
- node->refs = 0;
-
- return node;
-}
-
-void
-free_node (struct graph_node *node)
-{
- if (!node) return;
- if (node->children) vector_free (node->children);
- if (node->element) free_cmd_element (node->element);
- free (node->text);
- free (node->arg);
- free (node);
-}
-
-void
-free_graph (struct graph_node *start)
-{
- if (start && start->children && vector_active(start->children) > 0) {
- for (unsigned int i = 0; i < vector_active(start->children); i++) {
- free_graph (vector_slot(start->children, i));
- vector_unset(start->children, i);
- }
- }
-
- if (--(start->refs) == 0)
- free_node (start);
-}
-
-char *
-describe_node(struct graph_node *node, char* buffer, unsigned int bufsize)
-{
- if (node == NULL) {
- snprintf(buffer, bufsize, "(null node)");
- return buffer;
- }
-
- // print this node
- switch (node->type) {
- case WORD_GN:
- case IPV4_GN:
- case IPV4_PREFIX_GN:
- case IPV6_GN:
- case IPV6_PREFIX_GN:
- case VARIABLE_GN:
- case RANGE_GN:
- snprintf(buffer, bufsize, node->text);
- break;
- case NUMBER_GN:
- snprintf(buffer, bufsize, "%ld", node->value);
- break;
- case SELECTOR_GN:
- snprintf(buffer, bufsize, "<>");
- break;
- case OPTION_GN:
- snprintf(buffer, bufsize, "[]");
- break;
- case NUL_GN:
- snprintf(buffer, bufsize, "NUL");
- break;
- case END_GN:
- snprintf(buffer, bufsize, "END");
- break;
- case START_GN:
- snprintf(buffer, bufsize, "START");
- break;
- default:
- snprintf(buffer, bufsize, "ERROR");
- }
-
- return buffer;
-}
-
-
-void
-walk_graph(struct graph_node *start, int level)
-{
- char* desc = malloc(50);
- // print this node
- fprintf(stderr, "%s[%d] ", describe_node(start, desc, 50), vector_active(start->children));
- free(desc);
-
- if (vector_active(start->children)) {
- if (vector_active(start->children) == 1)
- walk_graph(vector_slot(start->children, 0), level);
- else {
- fprintf(stderr, "\n");
- for (unsigned int i = 0; i < vector_active(start->children); i++) {
- struct graph_node *r = vector_slot(start->children, i);
- for (int j = 0; j < level+1; j++)
- fprintf(stderr, " ");
- walk_graph(r, level+1);
- }
- }
- }
- else
- fprintf(stderr, "\n");
-}
-
-void
-dump_node (struct graph_node *node)
-{
- char buf[50];
- describe_node(node, buf, 50);
- fprintf(stderr, "%s[%d]\n", buf, node->type);
- fprintf(stderr, "\t->text: %s\n", node->text);
- fprintf(stderr, "\t->value: %ld\n", node->value);
- fprintf(stderr, "\t->is_start: %d\n", node->is_start);
- fprintf(stderr, "\t->element: %p\n", node->element);
- fprintf(stderr, "\t->min: %d\n->max: %d\n", node->min, node->max);
- fprintf(stderr, "\t->arg: %s\n", node->arg);
- fprintf(stderr, "\t->refs: %d\n", node->refs);
- fprintf(stderr, "\tnum children: %d\n", vector_active(node->children));
+
+#include "command_graph.h"
+
+DEFINE_MTYPE_STATIC(LIB, CMD_TOKENS, "Command Tokens")
+DEFINE_MTYPE_STATIC(LIB, CMD_DESC, "Command Token Text")
+DEFINE_MTYPE_STATIC(LIB, CMD_TEXT, "Command Token Help")
+DEFINE_MTYPE(LIB, CMD_ARG, "Command Argument")
+DEFINE_MTYPE_STATIC(LIB, CMD_VAR, "Command Argument Name")
+
+struct cmd_token *cmd_token_new(enum cmd_token_type type, uint8_t attr,
+ const char *text, const char *desc)
+{
+ struct cmd_token *token =
+ XCALLOC(MTYPE_CMD_TOKENS, sizeof(struct cmd_token));
+ token->type = type;
+ token->attr = attr;
+ token->text = text ? XSTRDUP(MTYPE_CMD_TEXT, text) : NULL;
+ token->desc = desc ? XSTRDUP(MTYPE_CMD_DESC, desc) : NULL;
+ token->refcnt = 1;
+ token->arg = NULL;
+ token->allowrepeat = false;
+ token->varname = NULL;
+
+ return token;
+}
+
+void cmd_token_del(struct cmd_token *token)
+{
+ if (!token)
+ return;
+
+ XFREE(MTYPE_CMD_TEXT, token->text);
+ XFREE(MTYPE_CMD_DESC, token->desc);
+ XFREE(MTYPE_CMD_ARG, token->arg);
+ XFREE(MTYPE_CMD_VAR, token->varname);
+
+ XFREE(MTYPE_CMD_TOKENS, token);
+}
+
+struct cmd_token *cmd_token_dup(struct cmd_token *token)
+{
+ struct cmd_token *copy =
+ cmd_token_new(token->type, token->attr, NULL, NULL);
+ copy->max = token->max;
+ copy->min = token->min;
+ copy->text = token->text ? XSTRDUP(MTYPE_CMD_TEXT, token->text) : NULL;
+ copy->desc = token->desc ? XSTRDUP(MTYPE_CMD_DESC, token->desc) : NULL;
+ copy->arg = token->arg ? XSTRDUP(MTYPE_CMD_ARG, token->arg) : NULL;
+ copy->varname =
+ token->varname ? XSTRDUP(MTYPE_CMD_VAR, token->varname) : NULL;
+
+ return copy;
+}
+
+void cmd_token_varname_set(struct cmd_token *token, const char *varname)
+{
+ XFREE(MTYPE_CMD_VAR, token->varname);
+ if (!varname) {
+ token->varname = NULL;
+ return;
+ }
+
+ size_t len = strlen(varname), i;
+ token->varname = XMALLOC(MTYPE_CMD_VAR, len + 1);
+
+ for (i = 0; i < len; i++)
+ switch (varname[i]) {
+ case '-':
+ case '+':
+ case '*':
+ case ':':
+ token->varname[i] = '_';
+ break;
+ default:
+ token->varname[i] = tolower((int)varname[i]);
+ }
+ token->varname[len] = '\0';
+}
+
+static bool cmd_nodes_link(struct graph_node *from, struct graph_node *to)
+{
+ for (size_t i = 0; i < vector_active(from->to); i++)
+ if (vector_slot(from->to, i) == to)
+ return true;
+ return false;
+}
+
+static bool cmd_nodes_equal(struct graph_node *ga, struct graph_node *gb);
+
+/* returns a single node to be excluded as "next" from iteration
+ * - for JOIN_TKN, never continue back to the FORK_TKN
+ * - in all other cases, don't try the node itself (in case of "...")
+ */
+static inline struct graph_node *cmd_loopstop(struct graph_node *gn)
+{
+ struct cmd_token *tok = gn->data;
+ if (tok->type == JOIN_TKN)
+ return tok->forkjoin;
+ else
+ return gn;
+}
+
+static bool cmd_subgraph_equal(struct graph_node *ga, struct graph_node *gb,
+ struct graph_node *a_join)
+{
+ size_t i, j;
+ struct graph_node *a_fork, *b_fork;
+ a_fork = cmd_loopstop(ga);
+ b_fork = cmd_loopstop(gb);
+
+ if (vector_active(ga->to) != vector_active(gb->to))
+ return false;
+ for (i = 0; i < vector_active(ga->to); i++) {
+ struct graph_node *cga = vector_slot(ga->to, i);
+
+ for (j = 0; j < vector_active(gb->to); j++) {
+ struct graph_node *cgb = vector_slot(gb->to, i);
+
+ if (cga == a_fork && cgb != b_fork)
+ continue;
+ if (cga == a_fork && cgb == b_fork)
+ break;
+
+ if (cmd_nodes_equal(cga, cgb)) {
+ if (cga == a_join)
+ break;
+ if (cmd_subgraph_equal(cga, cgb, a_join))
+ break;
+ }
+ }
+ if (j == vector_active(gb->to))
+ return false;
+ }
+ return true;
+}
+
+/* deep compare -- for FORK_TKN, the entire subgraph is compared.
+ * this is what's needed since we're not currently trying to partially
+ * merge subgraphs */
+static bool cmd_nodes_equal(struct graph_node *ga, struct graph_node *gb)
+{
+ struct cmd_token *a = ga->data, *b = gb->data;
+
+ if (a->type != b->type || a->allowrepeat != b->allowrepeat)
+ return false;
+ if (a->type < SPECIAL_TKN && strcmp(a->text, b->text))
+ return false;
+ /* one a ..., the other not. */
+ if (cmd_nodes_link(ga, ga) != cmd_nodes_link(gb, gb))
+ return false;
+ if (!a->varname != !b->varname)
+ return false;
+ if (a->varname && strcmp(a->varname, b->varname))
+ return false;
+
+ switch (a->type) {
+ case RANGE_TKN:
+ return a->min == b->min && a->max == b->max;
+
+ case FORK_TKN:
+ /* one is keywords, the other just option or selector ... */
+ if (cmd_nodes_link(a->forkjoin, ga)
+ != cmd_nodes_link(b->forkjoin, gb))
+ return false;
+ if (cmd_nodes_link(ga, a->forkjoin)
+ != cmd_nodes_link(gb, b->forkjoin))
+ return false;
+ return cmd_subgraph_equal(ga, gb, a->forkjoin);
+
+ default:
+ return true;
+ }
+}
+
+static void cmd_fork_bump_attr(struct graph_node *gn, struct graph_node *join,
+ uint8_t attr)
+{
+ size_t i;
+ struct cmd_token *tok = gn->data;
+ struct graph_node *stop = cmd_loopstop(gn);
+
+ tok->attr = attr;
+ for (i = 0; i < vector_active(gn->to); i++) {
+ struct graph_node *next = vector_slot(gn->to, i);
+ if (next == stop || next == join)
+ continue;
+ cmd_fork_bump_attr(next, join, attr);
+ }
+}
+
+/* move an entire subtree from the temporary graph resulting from
+ * parse() into the permanent graph for the command node.
+ *
+ * this touches rather deeply into the graph code unfortunately.
+ */
+static void cmd_reparent_tree(struct graph *fromgraph, struct graph *tograph,
+ struct graph_node *node)
+{
+ struct graph_node *stop = cmd_loopstop(node);
+ size_t i;
+
+ for (i = 0; i < vector_active(fromgraph->nodes); i++)
+ if (vector_slot(fromgraph->nodes, i) == node) {
+ /* agressive iteration punching through subgraphs - may
+ * hit some
+ * nodes twice. reparent only if found on old graph */
+ vector_unset(fromgraph->nodes, i);
+ vector_set(tograph->nodes, node);
+ break;
+ }
+
+ for (i = 0; i < vector_active(node->to); i++) {
+ struct graph_node *next = vector_slot(node->to, i);
+ if (next != stop)
+ cmd_reparent_tree(fromgraph, tograph, next);
+ }
+}
+
+static void cmd_free_recur(struct graph *graph, struct graph_node *node,
+ struct graph_node *stop)
+{
+ struct graph_node *next, *nstop;
+
+ for (size_t i = vector_active(node->to); i; i--) {
+ next = vector_slot(node->to, i - 1);
+ if (next == stop)
+ continue;
+ nstop = cmd_loopstop(next);
+ if (nstop != next)
+ cmd_free_recur(graph, next, nstop);
+ cmd_free_recur(graph, nstop, stop);
+ }
+ graph_delete_node(graph, node);
+}
+
+static void cmd_free_node(struct graph *graph, struct graph_node *node)
+{
+ struct cmd_token *tok = node->data;
+ if (tok->type == JOIN_TKN)
+ cmd_free_recur(graph, tok->forkjoin, node);
+ graph_delete_node(graph, node);
+}
+
+/* recursive graph merge. call with
+ * old ~= new
+ * (which holds true for old == START_TKN, new == START_TKN)
+ */
+static void cmd_merge_nodes(struct graph *oldgraph, struct graph *newgraph,
+ struct graph_node *old, struct graph_node *new,
+ int direction)
+{
+ struct cmd_token *tok;
+ struct graph_node *old_skip, *new_skip;
+ old_skip = cmd_loopstop(old);
+ new_skip = cmd_loopstop(new);
+
+ assert(direction == 1 || direction == -1);
+
+ tok = old->data;
+ tok->refcnt += direction;
+
+ size_t j, i;
+ for (j = 0; j < vector_active(new->to); j++) {
+ struct graph_node *cnew = vector_slot(new->to, j);
+ if (cnew == new_skip)
+ continue;
+
+ for (i = 0; i < vector_active(old->to); i++) {
+ struct graph_node *cold = vector_slot(old->to, i);
+ if (cold == old_skip)
+ continue;
+
+ if (cmd_nodes_equal(cold, cnew)) {
+ struct cmd_token *told = cold->data,
+ *tnew = cnew->data;
+
+ if (told->type == END_TKN) {
+ if (direction < 0) {
+ graph_delete_node(
+ oldgraph,
+ vector_slot(cold->to,
+ 0));
+ graph_delete_node(oldgraph,
+ cold);
+ } else
+ /* force no-match handling to
+ * install END_TKN */
+ i = vector_active(old->to);
+ break;
+ }
+
+ /* the entire fork compared as equal, we
+ * continue after it. */
+ if (told->type == FORK_TKN) {
+ if (tnew->attr < told->attr
+ && direction > 0)
+ cmd_fork_bump_attr(
+ cold, told->forkjoin,
+ tnew->attr);
+ /* XXX: no reverse bump on uninstall */
+ told = (cold = told->forkjoin)->data;
+ tnew = (cnew = tnew->forkjoin)->data;
+ }
+ if (tnew->attr < told->attr)
+ told->attr = tnew->attr;
+
+ cmd_merge_nodes(oldgraph, newgraph, cold, cnew,
+ direction);
+ break;
+ }
+ }
+ /* nothing found => add new to old */
+ if (i == vector_active(old->to) && direction > 0) {
+ graph_remove_edge(new, cnew);
+
+ cmd_reparent_tree(newgraph, oldgraph, cnew);
+
+ graph_add_edge(old, cnew);
+ }
+ }
+
+ if (!tok->refcnt)
+ cmd_free_node(oldgraph, old);
+}
+
+void cmd_graph_merge(struct graph *old, struct graph *new, int direction)
+{
+ assert(vector_active(old->nodes) >= 1);
+ assert(vector_active(new->nodes) >= 1);
+
+ cmd_merge_nodes(old, new, vector_slot(old->nodes, 0),
+ vector_slot(new->nodes, 0), direction);
+}
+
+static void cmd_node_names(struct graph_node *gn, struct graph_node *join,
+ const char *prevname)
+{
+ size_t i;
+ struct cmd_token *tok = gn->data, *jointok;
+ struct graph_node *stop = cmd_loopstop(gn);
+
+ switch (tok->type) {
+ case WORD_TKN:
+ prevname = tok->text;
+ break;
+
+ case VARIABLE_TKN:
+ if (!tok->varname && strcmp(tok->text, "WORD")
+ && strcmp(tok->text, "NAME"))
+ cmd_token_varname_set(tok, tok->text);
+ /* fallthrough */
+ case RANGE_TKN:
+ case IPV4_TKN:
+ case IPV4_PREFIX_TKN:
+ case IPV6_TKN:
+ case IPV6_PREFIX_TKN:
+ case MAC_TKN:
+ case MAC_PREFIX_TKN:
+ if (!tok->varname && prevname)
+ cmd_token_varname_set(tok, prevname);
+ prevname = NULL;
+ break;
+
+ case START_TKN:
+ case JOIN_TKN:
+ /* "<foo|bar> WORD" -> word is not "bar" or "foo" */
+ prevname = NULL;
+ break;
+
+ case FORK_TKN:
+ /* apply "<A.B.C.D|X:X::X:X>$name" */
+ jointok = tok->forkjoin->data;
+ if (!jointok->varname)
+ break;
+ for (i = 0; i < vector_active(tok->forkjoin->from); i++) {
+ struct graph_node *tail =
+ vector_slot(tok->forkjoin->from, i);
+ struct cmd_token *tailtok = tail->data;
+ if (tail == gn || tailtok->varname)
+ continue;
+ cmd_token_varname_set(tailtok, jointok->varname);
+ }
+ break;
+
+ case END_TKN:
+ return;
+ }
+
+ for (i = 0; i < vector_active(gn->to); i++) {
+ struct graph_node *next = vector_slot(gn->to, i);
+ if (next == stop || next == join)
+ continue;
+ cmd_node_names(next, join, prevname);
+ }
+
+ if (tok->type == FORK_TKN && tok->forkjoin != join)
+ cmd_node_names(tok->forkjoin, join, NULL);
+}
+
+void cmd_graph_names(struct graph *graph)
+{
+ struct graph_node *start;
+
+ assert(vector_active(graph->nodes) >= 1);
+ start = vector_slot(graph->nodes, 0);
+
+ /* apply varname on initial "[no]" */
+ do {
+ if (vector_active(start->to) != 1)
+ break;
+
+ struct graph_node *first = vector_slot(start->to, 0);
+ struct cmd_token *tok = first->data;
+ /* looking for an option with 2 choices, nothing or "no" */
+ if (tok->type != FORK_TKN || vector_active(first->to) != 2)
+ break;
+
+ struct graph_node *next0 = vector_slot(first->to, 0);
+ struct graph_node *next1 = vector_slot(first->to, 1);
+ /* one needs to be empty */
+ if (next0 != tok->forkjoin && next1 != tok->forkjoin)
+ break;
+
+ struct cmd_token *tok0 = next0->data;
+ struct cmd_token *tok1 = next1->data;
+ /* the other one needs to be "no" (only one will match here) */
+ if ((tok0->type == WORD_TKN && !strcmp(tok0->text, "no")))
+ cmd_token_varname_set(tok0, "no");
+ if ((tok1->type == WORD_TKN && !strcmp(tok1->text, "no")))
+ cmd_token_varname_set(tok1, "no");
+ } while (0);
+
+ cmd_node_names(start, NULL, NULL);
+}
+
+#ifndef BUILDING_CLIPPY
+
+#include "command.h"
+#include "log.h"
+
+void cmd_graph_node_print_cb(struct graph_node *gn, struct buffer *buf)
+{
+ static bool wasend;
+
+ char nbuf[512];
+ struct cmd_token *tok = gn->data;
+ const char *color;
+
+ if (wasend == true) {
+ wasend = false;
+ return;
+ }
+
+ if (tok->type == END_TKN) {
+ wasend = true;
+ return;
+ }
+
+ snprintf(nbuf, sizeof(nbuf), " n%p [ shape=box, label=<", gn);
+ buffer_putstr(buf, nbuf);
+ snprintf(nbuf, sizeof(nbuf), "<b>%s</b>",
+ lookup_msg(tokennames, tok->type, NULL));
+ buffer_putstr(buf, nbuf);
+ if (tok->attr == CMD_ATTR_DEPRECATED)
+ buffer_putstr(buf, " (d)");
+ else if (tok->attr == CMD_ATTR_HIDDEN)
+ buffer_putstr(buf, " (h)");
+ if (tok->text) {
+ if (tok->type == WORD_TKN)
+ snprintf(
+ nbuf, sizeof(nbuf),
+ "<br/>\"<font color=\"#0055ff\" point-size=\"11\"><b>%s</b></font>\"",
+ tok->text);
+ else
+ snprintf(nbuf, sizeof(nbuf), "<br/>%s", tok->text);
+ buffer_putstr(buf, nbuf);
+ }
+
+ switch (tok->type) {
+ case START_TKN:
+ color = "#ccffcc";
+ break;
+ case FORK_TKN:
+ color = "#aaddff";
+ break;
+ case JOIN_TKN:
+ color = "#ddaaff";
+ break;
+ case WORD_TKN:
+ color = "#ffffff";
+ break;
+ default:
+ color = "#ffffff";
+ break;
+ }
+ snprintf(nbuf, sizeof(nbuf),
+ ">, style = filled, fillcolor = \"%s\" ];\n", color);
+ buffer_putstr(buf, nbuf);
+
+ for (unsigned int i = 0; i < vector_active(gn->to); i++) {
+ struct graph_node *adj = vector_slot(gn->to, i);
+
+ if (((struct cmd_token *)adj->data)->type == END_TKN) {
+ snprintf(nbuf, sizeof(nbuf), " n%p -> end%p;\n", gn,
+ adj);
+ buffer_putstr(buf, nbuf);
+ snprintf(
+ nbuf, sizeof(nbuf),
+ " end%p [ shape=box, label=<end>, style = filled, fillcolor = \"#ffddaa\" ];\n",
+ adj);
+ } else
+ snprintf(nbuf, sizeof(nbuf), " n%p -> n%p;\n", gn,
+ adj);
+
+ buffer_putstr(buf, nbuf);
+ }
}
+
+char *cmd_graph_dump_dot(struct graph *cmdgraph)
+{
+ struct graph_node *start = vector_slot(cmdgraph->nodes, 0);
+
+ return graph_dump_dot(cmdgraph, start, cmd_graph_node_print_cb);
+}
+
+#endif /* BUILDING_CLIPPY */
projects / mirror_frr.git / blobdiff