lib: fix rare bug in ambiguous command resolution

In certain situations, the CLI matcher would not handle ambiguous
commands properly. If it found an ambiguous result in a lower subgraph,
the ambiguous result would not correctly propagate up to previous frames
in the resolution DFS as ambiguous; instead it would propagate up as a
non-match, which could subsequently be overridden by a partial match.

Example CLI space:

  show ip route summary
  show ip route supernet-only
  show ipv6 route summary

Entering `show ip route su` would result in an ambiguous resolution for
the `show ip route` subgraph but would propagate up to the `show ip`
subgraph as a no-match, allowing `ip` to partial-match `ipv6` and
execute that command.

In this example entering `show ip route summary` would disambiguate the
`show ip` subgraph. So this bug would only appear when entering input
that caused ambiguities in at least two parallel subgraphs.

Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>

1 files changed, 72 insertions, 58 deletions

diff --git a/lib/command_match.c b/lib/command_match.c
index f07448d716..5590fce6b1 100644
--- a/lib/command_match.c
+++ b/lib/command_match.c
@@ -46,8 +46,9 @@ DEFINE_MTYPE_STATIC(LIB, CMD_MATCHSTACK, "Command Match Stack")
 static int add_nexthops(struct list *, struct graph_node *,
 			struct graph_node **, size_t);
 
-static struct list *command_match_r(struct graph_node *, vector, unsigned int,
-				    struct graph_node **);
+static enum matcher_rv command_match_r(struct graph_node *, vector,
+				       unsigned int, struct graph_node **,
+				       struct list **);
 
 static int score_precedence(enum cmd_token_type);
 
@@ -87,7 +88,8 @@ enum matcher_rv command_match(struct graph *cmdgraph, vector vline,
 			      struct list **argv, const struct cmd_element **el)
 {
 	struct graph_node *stack[MAXDEPTH];
-	matcher_rv = MATCHER_NO_MATCH;
+	enum matcher_rv status;
+	*argv = NULL;
 
 	// prepend a dummy token to match that pesky start node
 	vector vvline = vector_init(vline->alloced + 1);
@@ -97,9 +99,8 @@ enum matcher_rv command_match(struct graph *cmdgraph, vector vline,
 	vvline->active = vline->active + 1;
 
 	struct graph_node *start = vector_slot(cmdgraph->nodes, 0);
-	if ((*argv = command_match_r(start, vvline, 0,
-				     stack))) // successful match
-	{
+	status = command_match_r(start, vvline, 0, stack, argv);
+	if (status == MATCHER_OK) { // successful match
 		struct listnode *head = listhead(*argv);
 		struct listnode *tail = listtail(*argv);
 
@@ -115,6 +116,9 @@ enum matcher_rv command_match(struct graph *cmdgraph, vector vline,
 		// input, with each cmd_token->arg holding the corresponding
 		// input
 		assert(*el);
+	} else if (*argv) {
+		del_arglist(*argv);
+		*argv = NULL;
 	}
 
 	if (!*el) {
@@ -129,7 +133,7 @@ enum matcher_rv command_match(struct graph *cmdgraph, vector vline,
 	// free vector
 	vector_free(vvline);
 
-	return matcher_rv;
+	return status;
 }
 
 /**
@@ -183,11 +187,15 @@ enum matcher_rv command_match(struct graph *cmdgraph, vector vline,
  *
  * If no match was found, the return value is NULL.
  */
-static struct list *command_match_r(struct graph_node *start, vector vline,
-				    unsigned int n, struct graph_node **stack)
+static enum matcher_rv command_match_r(struct graph_node *start, vector vline,
+				       unsigned int n,
+				       struct graph_node **stack,
+				       struct list **currbest)
 {
 	assert(n < vector_active(vline));
 
+	enum matcher_rv status = MATCHER_NO_MATCH;
+
 	// get the minimum match level that can count as a full match
 	struct cmd_token *token = start->data;
 	enum match_type minmatch = min_match_level(token->type);
@@ -196,11 +204,11 @@ static struct list *command_match_r(struct graph_node *start, vector vline,
 	 * this disallows matching the same one more than once if there is a
 	 * circle in the graph (used for keyword arguments) */
 	if (n == MAXDEPTH)
-		return NULL;
+		return MATCHER_NO_MATCH;
 	if (!token->allowrepeat)
 		for (size_t s = 0; s < n; s++)
 			if (stack[s] == start)
-				return NULL;
+				return MATCHER_NO_MATCH;
 
 	// get the current operating input token
 	char *input_token = vector_slot(vline, n);
@@ -231,7 +239,7 @@ static struct list *command_match_r(struct graph_node *start, vector vline,
 
 	// if we don't match this node, die
 	if (match_token(token, input_token) < minmatch)
-		return NULL;
+		return MATCHER_NO_MATCH;
 
 	stack[n] = start;
 
@@ -244,86 +252,92 @@ static struct list *command_match_r(struct graph_node *start, vector vline,
 	add_nexthops(next, start, NULL, 0);
 
 	// determine the best match
-	int ambiguous = 0;
-	struct list *currbest = NULL;
 	for (ALL_LIST_ELEMENTS_RO(next, ln, gn)) {
 		// if we've matched all input we're looking for END_TKN
 		if (n + 1 == vector_active(vline)) {
 			struct cmd_token *tok = gn->data;
 			if (tok->type == END_TKN) {
-				if (currbest) // there is more than one END_TKN
-					      // in the follow set
-				{
-					ambiguous = 1;
+				// if more than one END_TKN in the follow set
+				if (*currbest) {
+					status = MATCHER_AMBIGUOUS;
 					break;
+				} else {
+					status = MATCHER_OK;
 				}
-				currbest = list_new();
+				*currbest = list_new();
 				// node should have one child node with the
 				// element
 				struct graph_node *leaf =
 					vector_slot(gn->to, 0);
 				// last node in the list will hold the
-				// cmd_element;
-				// this is important because list_delete()
-				// expects
-				// that all nodes have the same data type, so
-				// when
-				// deleting this list the last node must be
-				// manually deleted
+				// cmd_element; this is important because
+				// list_delete() expects that all nodes have
+				// the same data type, so when deleting this
+				// list the last node must be manually deleted
 				struct cmd_element *el = leaf->data;
-				listnode_add(currbest, el);
-				currbest->del =
+				listnode_add(*currbest, el);
+				(*currbest)->del =
 					(void (*)(void *)) & cmd_token_del;
 				// do not break immediately; continue walking
-				// through the follow set
-				// to ensure that there is exactly one END_TKN
+				// through the follow set to ensure that there
+				// is exactly one END_TKN
 			}
 			continue;
 		}
 
 		// else recurse on candidate child node
-		struct list *result = command_match_r(gn, vline, n + 1, stack);
+		struct list *result = NULL;
+		enum matcher_rv rstat =
+			command_match_r(gn, vline, n + 1, stack, &result);
 
 		// save the best match
-		if (result && currbest) {
+		if (result && *currbest) {
 			// pick the best of two matches
 			struct list *newbest =
-				disambiguate(currbest, result, vline, n + 1);
-			// set ambiguity flag
-			ambiguous =
-				!newbest || (ambiguous && newbest == currbest);
+				disambiguate(*currbest, result, vline, n + 1);
+
+			// current best and result are ambiguous
+			if (!newbest)
+				status = MATCHER_AMBIGUOUS;
+			// current best is still the best, but ambiguous
+			else if (newbest == *currbest
+				 && status == MATCHER_AMBIGUOUS)
+				status = MATCHER_AMBIGUOUS;
+			// result is better, but also ambiguous
+			else if (newbest == result
+				 && rstat == MATCHER_AMBIGUOUS)
+				status = MATCHER_AMBIGUOUS;
+			// one or the other is superior and not ambiguous
+			else
+				status = MATCHER_OK;
+
 			// delete the unnecessary result
 			struct list *todelete =
-				((newbest && newbest == result) ? currbest
+				((newbest && newbest == result) ? *currbest
 								: result);
 			del_arglist(todelete);
 
-			currbest = newbest ? newbest : currbest;
-		} else if (result)
-			currbest = result;
-	}
-
-	if (currbest) {
-		if (ambiguous) {
-			del_arglist(currbest);
-			currbest = NULL;
-			matcher_rv = MATCHER_AMBIGUOUS;
-		} else {
-			// copy token, set arg and prepend to currbest
-			struct cmd_token *token = start->data;
-			struct cmd_token *copy = cmd_token_dup(token);
-			copy->arg = XSTRDUP(MTYPE_CMD_ARG, input_token);
-			listnode_add_before(currbest, currbest->head, copy);
-			matcher_rv = MATCHER_OK;
+			*currbest = newbest ? newbest : *currbest;
+		} else if (result) {
+			status = rstat;
+			*currbest = result;
+		} else if (!*currbest) {
+			status = MAX(rstat, status);
 		}
-	} else if (n + 1 == vector_active(vline)
-		   && matcher_rv == MATCHER_NO_MATCH)
-		matcher_rv = MATCHER_INCOMPLETE;
+	}
+	if (*currbest) {
+		// copy token, set arg and prepend to currbest
+		struct cmd_token *token = start->data;
+		struct cmd_token *copy = cmd_token_dup(token);
+		copy->arg = XSTRDUP(MTYPE_CMD_ARG, input_token);
+		listnode_add_before(*currbest, (*currbest)->head, copy);
+	} else if (n + 1 == vector_active(vline) && status == MATCHER_NO_MATCH)
+		status = MATCHER_INCOMPLETE;
 
 	// cleanup
 	list_delete(next);
 
-	return currbest;
+	return status;
 }
 
 static void stack_del(void *val)