summaryrefslogtreecommitdiffstats
path: root/lib/command_graph.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/command_graph.c')
-rw-r--r--lib/command_graph.c562
1 files changed, 562 insertions, 0 deletions
diff --git a/lib/command_graph.c b/lib/command_graph.c
new file mode 100644
index 0000000..09d802e
--- /dev/null
+++ b/lib/command_graph.c
@@ -0,0 +1,562 @@
+/*
+ * CLI graph handling
+ *
+ * --
+ * 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 <zebra.h>
+
+#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;
+}
+
+static void cmd_token_varname_do(struct cmd_token *token, const char *varname,
+ uint8_t varname_src)
+{
+ if (token->varname_src >= varname_src)
+ return;
+
+ XFREE(MTYPE_CMD_VAR, token->varname);
+
+ size_t len = strlen(varname), i;
+ token->varname = XMALLOC(MTYPE_CMD_VAR, len + 1);
+ token->varname_src = varname_src;
+
+ for (i = 0; i < len; i++)
+ switch (varname[i]) {
+ case '-':
+ case '+':
+ case '*':
+ case ':':
+ token->varname[i] = '_';
+ break;
+ default:
+ token->varname[i] = tolower((unsigned char)varname[i]);
+ }
+ token->varname[len] = '\0';
+}
+
+void cmd_token_varname_set(struct cmd_token *token, const char *varname)
+{
+ if (varname) {
+ cmd_token_varname_do(token, varname, VARNAME_EXPLICIT);
+ return;
+ }
+ if (token->type == VARIABLE_TKN) {
+ if (strcmp(token->text, "WORD") && strcmp(token->text, "NAME"))
+ cmd_token_varname_do(token, token->text, VARNAME_TEXT);
+ }
+}
+
+static void cmd_token_varname_fork(struct graph_node *node,
+ struct cmd_token *prevtoken)
+{
+ for (size_t i = 0; i < vector_active(node->to); i++) {
+ struct graph_node *next = vector_slot(node->to, i);
+ struct cmd_token *nexttoken = next->data;
+
+ if (nexttoken->type == FORK_TKN) {
+ cmd_token_varname_fork(next, prevtoken);
+ continue;
+ }
+ if (nexttoken->varname)
+ continue;
+ if (!IS_VARYING_TOKEN(nexttoken->type))
+ continue;
+
+ cmd_token_varname_do(nexttoken, prevtoken->text, VARNAME_TEXT);
+ }
+}
+
+void cmd_token_varname_join(struct graph_node *join, const char *varname)
+{
+ if (!varname)
+ return;
+
+ for (size_t i = 0; i < vector_active(join->from); i++) {
+ struct graph_node *prev = vector_slot(join->from, i);
+ struct cmd_token *token = prev->data;
+
+ if (token->type == JOIN_TKN)
+ cmd_token_varname_join(prev, varname);
+ else if (token->type < SPECIAL_TKN)
+ cmd_token_varname_do(token, varname, VARNAME_EXPLICIT);
+ }
+}
+
+void cmd_token_varname_seqappend(struct graph_node *node)
+{
+ struct graph_node *prevnode = node;
+ struct cmd_token *token = node->data;
+ struct cmd_token *prevtoken;
+
+ if (token->type == WORD_TKN)
+ return;
+
+ do {
+ if (vector_active(prevnode->from) != 1)
+ return;
+
+ prevnode = vector_slot(prevnode->from, 0);
+ prevtoken = prevnode->data;
+ } while (prevtoken->type == FORK_TKN);
+
+ if (prevtoken->type != WORD_TKN)
+ return;
+
+ if (token->type == FORK_TKN)
+ cmd_token_varname_fork(node, prevtoken);
+ else
+ cmd_token_varname_do(token, prevtoken->text, VARNAME_TEXT);
+}
+
+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);
+}
+
+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_do(tok0, "no", VARNAME_AUTO);
+ if ((tok1->type == WORD_TKN && !strcmp(tok1->text, "no")))
+ cmd_token_varname_do(tok1, "no", VARNAME_AUTO);
+ } while (0);
+}
+
+#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) {
+ 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 NEG_ONLY_TKN:
+ color = "#ffddaa";
+ 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 */