1 files changed, 578 insertions, 0 deletions

diff --git a/lib/command_graph.c b/lib/command_graph.c
new file mode 100644
index 0000000..ff3c11d
--- /dev/null
+++ b/lib/command_graph.c
@@ -0,0 +1,578 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * 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")
+ */
+
+#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);
+
+	case VARIABLE_TKN:
+	case IPV4_TKN:
+	case IPV4_PREFIX_TKN:
+	case IPV6_PREFIX_TKN:
+	case IPV6_TKN:
+	case MAC_TKN:
+	case MAC_PREFIX_TKN:
+	case JOIN_TKN:
+	case START_TKN:
+	case END_TKN:
+	case NEG_ONLY_TKN:
+	case WORD_TKN:
+	case ASNUM_TKN:
+		return true;
+	}
+
+	assert(!"Reached end of function we should never hit");
+}
+
+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 = NULL;
+
+	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)");
+	/* DEPRECATED implies HIDDEN, don't print both */
+	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;
+	case RANGE_TKN:
+	case IPV4_TKN:
+	case IPV4_PREFIX_TKN:
+	case IPV6_TKN:
+	case IPV6_PREFIX_TKN:
+	case MAC_TKN:
+	case MAC_PREFIX_TKN:
+	case END_TKN:
+	case VARIABLE_TKN:
+	case ASNUM_TKN:
+		color = "#ffffff";
+		break;
+	}
+
+	/*
+	 * Some compilers have the mistaken belief that we can
+	 * get here without initializing color.
+	 */
+	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 */