Adding upstream version 9.1.upstream/9.1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 1072 insertions, 0 deletions

diff --git a/lib/command_match.c b/lib/command_match.c
new file mode 100644
index 0000000..f740b72
--- /dev/null
+++ b/lib/command_match.c
@@ -0,0 +1,1072 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Input matching routines for CLI backend.
+ *
+ * --
+ * Copyright (C) 2016 Cumulus Networks, Inc.
+ */
+
+#include <zebra.h>
+
+#include "command_match.h"
+#include "memory.h"
+#include "asn.h"
+
+DEFINE_MTYPE_STATIC(LIB, CMD_MATCHSTACK, "Command Match Stack");
+
+#ifdef TRACE_MATCHER
+#define TM 1
+#else
+#define TM 0
+#endif
+
+#define trace_matcher(...)                                                     \
+	do {                                                                   \
+		if (TM)                                                        \
+			fprintf(stderr, __VA_ARGS__);                          \
+	} while (0);
+
+/* matcher helper prototypes */
+static int add_nexthops(struct list *, struct graph_node *,
+			struct graph_node **, size_t, bool);
+
+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);
+
+static enum match_type min_match_level(enum cmd_token_type);
+
+static void del_arglist(struct list *);
+
+static struct cmd_token *disambiguate_tokens(struct cmd_token *,
+					     struct cmd_token *, char *);
+
+static struct list *disambiguate(struct list *, struct list *, vector,
+				 unsigned int);
+
+int compare_completions(const void *, const void *);
+
+/* token matcher prototypes */
+static enum match_type match_token(struct cmd_token *, char *);
+
+static enum match_type match_ipv4(const char *);
+
+static enum match_type match_ipv4_prefix(const char *);
+
+static enum match_type match_ipv6_prefix(const char *, bool);
+
+static enum match_type match_range(struct cmd_token *, const char *);
+
+static enum match_type match_word(struct cmd_token *, const char *);
+
+static enum match_type match_variable(struct cmd_token *, const char *);
+
+static enum match_type match_mac(const char *, bool);
+
+static bool is_neg(vector vline, size_t idx)
+{
+	if (idx >= vector_active(vline) || !vector_slot(vline, idx))
+		return false;
+	return !strcmp(vector_slot(vline, idx), "no");
+}
+
+enum matcher_rv command_match(struct graph *cmdgraph, vector vline,
+			      struct list **argv, const struct cmd_element **el)
+{
+	struct graph_node *stack[CMD_ARGC_MAX];
+	enum matcher_rv status;
+	*argv = NULL;
+
+	// prepend a dummy token to match that pesky start node
+	vector vvline = vector_init(vline->alloced + 1);
+	vector_set_index(vvline, 0, XSTRDUP(MTYPE_TMP, "dummy"));
+	memcpy(vvline->index + 1, vline->index,
+	       sizeof(void *) * vline->alloced);
+	vvline->active = vline->active + 1;
+
+	struct graph_node *start = vector_slot(cmdgraph->nodes, 0);
+	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);
+
+		assert(head);
+		assert(tail);
+
+		// delete dummy start node
+		cmd_token_del((struct cmd_token *)head->data);
+		list_delete_node(*argv, head);
+
+		// get cmd_element out of list tail
+		*el = listgetdata(tail);
+		list_delete_node(*argv, tail);
+
+		// now argv is an ordered list of cmd_token matching the user
+		// input, with each cmd_token->arg holding the corresponding
+		// input
+		assert(*el);
+	} else if (*argv) {
+		del_arglist(*argv);
+		*argv = NULL;
+	}
+
+	if (!*el) {
+		trace_matcher("No match\n");
+	} else {
+		trace_matcher("Matched command\n->string %s\n->desc %s\n",
+			      (*el)->string, (*el)->doc);
+	}
+
+	// free the leader token we alloc'd
+	XFREE(MTYPE_TMP, vector_slot(vvline, 0));
+	// free vector
+	vector_free(vvline);
+
+	return status;
+}
+
+/**
+ * Builds an argument list given a DFA and a matching input line.
+ *
+ * First the function determines if the node it is passed matches the first
+ * token of input. If it does not, it returns NULL (MATCHER_NO_MATCH). If it
+ * does match, then it saves the input token as the head of an argument list.
+ *
+ * The next step is to see if there is further input in the input line. If
+ * there is not, the current node's children are searched to see if any of them
+ * are leaves (type END_TKN). If this is the case, then the bottom of the
+ * recursion stack has been reached, the leaf is pushed onto the argument list,
+ * the current node is pushed, and the resulting argument list is
+ * returned (MATCHER_OK). If it is not the case, NULL is returned, indicating
+ * that there is no match for the input along this path (MATCHER_INCOMPLETE).
+ *
+ * If there is further input, then the function recurses on each of the current
+ * node's children, passing them the input line minus the token that was just
+ * matched. For each child, the return value of the recursive call is
+ * inspected. If it is null, then there is no match for the input along the
+ * subgraph headed by that child. If it is not null, then there is at least one
+ * input match in that subgraph (more on this in a moment).
+ *
+ * If a recursive call on a child returns a non-null value, then it has matched
+ * the input given it on the subgraph that starts with that child. However, due
+ * to the flexibility of the grammar, it is sometimes the case that two or more
+ * child graphs match the same input (two or more of the recursive calls have
+ * non-NULL return values). This is not a valid state, since only one true
+ * match is possible. In order to resolve this conflict, the function keeps a
+ * reference to the child node that most specifically matches the input. This
+ * is done by assigning each node type a precedence. If a child is found to
+ * match the remaining input, then the precedence values of the current
+ * best-matching child and this new match are compared. The node with higher
+ * precedence is kept, and the other match is discarded. Due to the recursive
+ * nature of this function, it is only necessary to compare the precedence of
+ * immediate children, since all subsequent children will already have been
+ * disambiguated in this way.
+ *
+ * In the event that two children are found to match with the same precedence,
+ * then the input is ambiguous for the passed cmd_element and NULL is returned.
+ *
+ * @param[in] start the start node.
+ * @param[in] vline the vectorized input line.
+ * @param[in] n the index of the first input token.
+ * @return A linked list of n elements. The first n-1 elements are pointers to
+ * struct cmd_token and represent the sequence of tokens matched by the input.
+ * The ->arg field of each token points to a copy of the input matched on it.
+ * The final nth element is a pointer to struct cmd_element, which is the
+ * command that was matched.
+ *
+ * If no match was found, the return value is NULL.
+ */
+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 *copy, *token = start->data;
+	enum match_type minmatch = min_match_level(token->type);
+
+	/* check history/stack of tokens
+	 * this disallows matching the same one more than once if there is a
+	 * circle in the graph (used for keyword arguments) */
+	if (n == CMD_ARGC_MAX)
+		return MATCHER_NO_MATCH;
+	if (!token->allowrepeat)
+		for (size_t s = 0; s < n; s++)
+			if (stack[s] == start)
+				return MATCHER_NO_MATCH;
+
+	// get the current operating input token
+	char *input_token = vector_slot(vline, n);
+
+#ifdef TRACE_MATCHER
+	fprintf(stdout, "\"%-20s\" matches \"%-30s\" ? ", input_token,
+		token->text);
+	enum match_type mt = match_token(token, input_token);
+	fprintf(stdout, "type: %d ", token->type);
+	fprintf(stdout, "min: %d - ", minmatch);
+	switch (mt) {
+	case trivial_match:
+		fprintf(stdout, "trivial_match ");
+		break;
+	case no_match:
+		fprintf(stdout, "no_match ");
+		break;
+	case partly_match:
+		fprintf(stdout, "partly_match ");
+		break;
+	case exact_match:
+		fprintf(stdout, "exact_match ");
+		break;
+	}
+	if (mt >= minmatch)
+		fprintf(stdout, " MATCH");
+	fprintf(stdout, "\n");
+#endif
+
+	// if we don't match this node, die
+	if (match_token(token, input_token) < minmatch)
+		return MATCHER_NO_MATCH;
+
+	stack[n] = start;
+
+	// pointers for iterating linklist
+	struct listnode *ln;
+	struct graph_node *gn;
+
+	// get all possible nexthops
+	struct list *next = list_new();
+	add_nexthops(next, start, NULL, 0, is_neg(vline, 1));
+
+	// determine the best match
+	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 more than one END_TKN in the follow set
+				if (*currbest) {
+					status = MATCHER_AMBIGUOUS;
+					break;
+				} else {
+					status = MATCHER_OK;
+				}
+				*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
+				struct cmd_element *el = leaf->data;
+				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
+			}
+			continue;
+		}
+
+		// else recurse on candidate child node
+		struct list *result = NULL;
+		enum matcher_rv rstat =
+			command_match_r(gn, vline, n + 1, stack, &result);
+
+		// save the best match
+		if (result && *currbest) {
+			// pick the best of two matches
+			struct list *newbest =
+				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
+								: result);
+			del_arglist(todelete);
+
+			*currbest = newbest ? newbest : *currbest;
+		} else if (result) {
+			status = rstat;
+			*currbest = result;
+		} else if (!*currbest) {
+			status = MAX(rstat, status);
+		}
+	}
+	if (*currbest) {
+		// copy token, set arg and prepend to currbest
+		token = start->data;
+		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 status;
+}
+
+static void stack_del(void *val)
+{
+	XFREE(MTYPE_CMD_MATCHSTACK, val);
+}
+
+enum matcher_rv command_complete(struct graph *graph, vector vline,
+				 struct list **completions)
+{
+	// pointer to next input token to match
+	char *input_token;
+	bool neg = is_neg(vline, 0);
+
+	struct list *
+		current =
+		       list_new(), // current nodes to match input token against
+		*next = list_new(); // possible next hops after current input
+				    // token
+	current->del = next->del = stack_del;
+
+	// pointers used for iterating lists
+	struct graph_node **gstack, **newstack;
+	struct listnode *node;
+
+	// add all children of start node to list
+	struct graph_node *start = vector_slot(graph->nodes, 0);
+	add_nexthops(next, start, &start, 0, neg);
+
+	unsigned int idx;
+	for (idx = 0; idx < vector_active(vline) && next->count > 0; idx++) {
+		list_delete(&current);
+		current = next;
+		next = list_new();
+		next->del = stack_del;
+
+		input_token = vector_slot(vline, idx);
+
+		int exact_match_exists = 0;
+		for (ALL_LIST_ELEMENTS_RO(current, node, gstack))
+			if (!exact_match_exists)
+				exact_match_exists =
+					(match_token(gstack[0]->data,
+						     input_token)
+					 == exact_match);
+			else
+				break;
+
+		for (ALL_LIST_ELEMENTS_RO(current, node, gstack)) {
+			struct cmd_token *token = gstack[0]->data;
+
+			if (token->attr & CMD_ATTR_HIDDEN)
+				continue;
+
+			enum match_type minmatch = min_match_level(token->type);
+			trace_matcher("\"%s\" matches \"%s\" (%d) ? ",
+				      input_token, token->text, token->type);
+
+			unsigned int last_token =
+				(vector_active(vline) - 1 == idx);
+			enum match_type matchtype =
+				match_token(token, input_token);
+			switch (matchtype) {
+			// occurs when last token is whitespace
+			case trivial_match:
+				trace_matcher("trivial_match\n");
+				assert(last_token);
+				newstack = XMALLOC(MTYPE_CMD_MATCHSTACK,
+						   sizeof(struct graph_node *));
+				/* we're not recursing here, just the first
+				 * element is OK */
+				newstack[0] = gstack[0];
+				listnode_add(next, newstack);
+				break;
+			case partly_match:
+				trace_matcher("trivial_match\n");
+				if (exact_match_exists && !last_token)
+					break;
+			/* fallthru */
+			case exact_match:
+				trace_matcher("exact_match\n");
+				if (last_token) {
+					newstack = XMALLOC(
+						MTYPE_CMD_MATCHSTACK,
+						sizeof(struct graph_node *));
+					/* same as above, not recursing on this
+					 */
+					newstack[0] = gstack[0];
+					listnode_add(next, newstack);
+				} else if (matchtype >= minmatch)
+					add_nexthops(next, gstack[0], gstack,
+						     idx + 1, neg);
+				break;
+			case no_match:
+				trace_matcher("no_match\n");
+				break;
+			}
+		}
+	}
+
+	/* Variable summary
+	 * -----------------------------------------------------------------
+	 * token    = last input token processed
+	 * idx      = index in `command` of last token processed
+	 * current  = set of all transitions from the previous input token
+	 * next     = set of all nodes reachable from all nodes in `matched`
+	 */
+
+	enum matcher_rv mrv = idx == vector_active(vline) && next->count
+				      ? MATCHER_OK
+				      : MATCHER_NO_MATCH;
+
+	*completions = NULL;
+	if (!MATCHER_ERROR(mrv)) {
+		// extract cmd_token into list
+		*completions = list_new();
+		for (ALL_LIST_ELEMENTS_RO(next, node, gstack)) {
+			listnode_add(*completions, gstack[0]->data);
+		}
+	}
+
+	list_delete(&current);
+	list_delete(&next);
+
+	return mrv;
+}
+
+/**
+ * Adds all children that are reachable by one parser hop to the given list.
+ * special tokens except END_TKN are treated as transparent.
+ *
+ * @param[in] list to add the nexthops to
+ * @param[in] node to start calculating nexthops from
+ * @param[in] stack listing previously visited nodes, if non-NULL.
+ * @param[in] stackpos how many valid entries are in stack
+ * @return the number of children added to the list
+ *
+ * NB: non-null "stack" means that new stacks will be added to "list" as
+ * output, instead of direct node pointers!
+ */
+static int add_nexthops(struct list *list, struct graph_node *node,
+			struct graph_node **stack, size_t stackpos, bool neg)
+{
+	int added = 0;
+	struct graph_node *child;
+	struct graph_node **nextstack;
+	for (unsigned int i = 0; i < vector_active(node->to); i++) {
+		child = vector_slot(node->to, i);
+		size_t j;
+		struct cmd_token *token = child->data;
+		if (!token->allowrepeat && stack) {
+			for (j = 0; j < stackpos; j++)
+				if (child == stack[j])
+					break;
+			if (j != stackpos)
+				continue;
+		}
+
+		if (token->type == NEG_ONLY_TKN && !neg)
+			continue;
+
+		if (token->type >= SPECIAL_TKN && token->type != END_TKN) {
+			added +=
+				add_nexthops(list, child, stack, stackpos, neg);
+		} else {
+			if (stack) {
+				nextstack = XMALLOC(
+					MTYPE_CMD_MATCHSTACK,
+					(stackpos + 1)
+						* sizeof(struct graph_node *));
+				nextstack[0] = child;
+				memcpy(nextstack + 1, stack,
+				       stackpos * sizeof(struct graph_node *));
+
+				listnode_add(list, nextstack);
+			} else
+				listnode_add(list, child);
+			added++;
+		}
+	}
+
+	return added;
+}
+
+/**
+ * Determines the node types for which a partial match may count as a full
+ * match. Enables command abbrevations.
+ *
+ * @param[in] type node type
+ * @return minimum match level needed to for a token to fully match
+ */
+static enum match_type min_match_level(enum cmd_token_type type)
+{
+	switch (type) {
+	// anything matches a start node, for the sake of recursion
+	case START_TKN:
+		return no_match;
+	// allowing words to partly match enables command abbreviation
+	case WORD_TKN:
+		return partly_match;
+	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 FORK_TKN:
+	case JOIN_TKN:
+	case END_TKN:
+	case NEG_ONLY_TKN:
+	case VARIABLE_TKN:
+	case ASNUM_TKN:
+		return exact_match;
+	}
+
+	assert(!"Reached end of function we should never hit");
+}
+
+/**
+ * Assigns precedence scores to node types.
+ *
+ * @param[in] type node type to score
+ * @return precedence score
+ */
+static int score_precedence(enum cmd_token_type type)
+{
+	switch (type) {
+	// some of these are mutually exclusive, so they share
+	// the same precedence value
+	case IPV4_TKN:
+	case IPV4_PREFIX_TKN:
+	case IPV6_TKN:
+	case IPV6_PREFIX_TKN:
+	case MAC_TKN:
+	case MAC_PREFIX_TKN:
+	case RANGE_TKN:
+		return 2;
+	case ASNUM_TKN:
+	case WORD_TKN:
+		return 3;
+	case VARIABLE_TKN:
+		return 4;
+	case JOIN_TKN:
+	case START_TKN:
+	case END_TKN:
+	case NEG_ONLY_TKN:
+	case SPECIAL_TKN:
+		return 10;
+	}
+
+	assert(!"Reached end of function we should never hit");
+}
+
+/**
+ * Picks the better of two possible matches for a token.
+ *
+ * @param[in] first candidate node matching token
+ * @param[in] second candidate node matching token
+ * @param[in] token the token being matched
+ * @return the best-matching node, or NULL if the two are entirely ambiguous
+ */
+static struct cmd_token *disambiguate_tokens(struct cmd_token *first,
+					     struct cmd_token *second,
+					     char *input_token)
+{
+	// if the types are different, simply go off of type precedence
+	if (first->type != second->type) {
+		int firstprec = score_precedence(first->type);
+		int secndprec = score_precedence(second->type);
+		if (firstprec != secndprec)
+			return firstprec < secndprec ? first : second;
+		else
+			return NULL;
+	}
+
+	// if they're the same, return the more exact match
+	enum match_type fmtype = match_token(first, input_token);
+	enum match_type smtype = match_token(second, input_token);
+	if (fmtype != smtype)
+		return fmtype > smtype ? first : second;
+
+	return NULL;
+}
+
+/**
+ * Picks the better of two possible matches for an input line.
+ *
+ * @param[in] first candidate list of cmd_token matching vline
+ * @param[in] second candidate list of cmd_token matching vline
+ * @param[in] vline the input line being matched
+ * @param[in] n index into vline to start comparing at
+ * @return the best-matching list, or NULL if the two are entirely ambiguous
+ */
+static struct list *disambiguate(struct list *first, struct list *second,
+				 vector vline, unsigned int n)
+{
+	assert(first != NULL);
+	assert(second != NULL);
+	// doesn't make sense for these to be inequal length
+	assert(first->count == second->count);
+	assert(first->count == vector_active(vline) - n + 1);
+
+	struct listnode *fnode = listhead_unchecked(first),
+			*snode = listhead_unchecked(second);
+	struct cmd_token *ftok = listgetdata(fnode), *stok = listgetdata(snode),
+			 *best = NULL;
+
+	// compare each token, if one matches better use that one
+	for (unsigned int i = n; i < vector_active(vline); i++) {
+		char *token = vector_slot(vline, i);
+		if ((best = disambiguate_tokens(ftok, stok, token)))
+			return best == ftok ? first : second;
+		fnode = listnextnode(fnode);
+		snode = listnextnode(snode);
+		ftok = listgetdata(fnode);
+		stok = listgetdata(snode);
+	}
+
+	return NULL;
+}
+
+/*
+ * Deletion function for arglist.
+ *
+ * Since list->del for arglists expects all listnode->data to hold cmd_token,
+ * but arglists have cmd_element as the data for the tail, this function
+ * manually deletes the tail before deleting the rest of the list as usual.
+ *
+ * The cmd_element at the end is *not* a copy. It is the one and only.
+ *
+ * @param list the arglist to delete
+ */
+static void del_arglist(struct list *list)
+{
+	// manually delete last node
+	struct listnode *tail = listtail(list);
+	tail->data = NULL;
+	list_delete_node(list, tail);
+
+	// delete the rest of the list as usual
+	list_delete(&list);
+}
+
+/*---------- token level matching functions ----------*/
+
+static enum match_type match_token(struct cmd_token *token, char *input_token)
+{
+	// nothing trivially matches everything
+	if (!input_token)
+		return trivial_match;
+
+	switch (token->type) {
+	case WORD_TKN:
+		return match_word(token, input_token);
+	case IPV4_TKN:
+		return match_ipv4(input_token);
+	case IPV4_PREFIX_TKN:
+		return match_ipv4_prefix(input_token);
+	case IPV6_TKN:
+		return match_ipv6_prefix(input_token, false);
+	case IPV6_PREFIX_TKN:
+		return match_ipv6_prefix(input_token, true);
+	case RANGE_TKN:
+		return match_range(token, input_token);
+	case VARIABLE_TKN:
+		return match_variable(token, input_token);
+	case MAC_TKN:
+		return match_mac(input_token, false);
+	case MAC_PREFIX_TKN:
+		return match_mac(input_token, true);
+	case ASNUM_TKN:
+		return asn_str2asn_match(input_token);
+	case END_TKN:
+	case FORK_TKN:
+	case JOIN_TKN:
+	case START_TKN:
+	case NEG_ONLY_TKN:
+		return no_match;
+	}
+
+	assert(!"Reached end of function we should never hit");
+}
+
+#define IPV4_ADDR_STR   "0123456789."
+#define IPV4_PREFIX_STR "0123456789./"
+
+static enum match_type match_ipv4(const char *str)
+{
+	const char *sp;
+	int dots = 0, nums = 0;
+	char buf[4];
+
+	for (;;) {
+		memset(buf, 0, sizeof(buf));
+		sp = str;
+		while (*str != '\0') {
+			if (*str == '.') {
+				if (dots >= 3)
+					return no_match;
+
+				if (*(str + 1) == '.')
+					return no_match;
+
+				if (*(str + 1) == '\0')
+					return partly_match;
+
+				dots++;
+				break;
+			}
+			if (!isdigit((unsigned char)*str))
+				return no_match;
+
+			str++;
+		}
+
+		if (str - sp > 3)
+			return no_match;
+
+		memcpy(buf, sp, str - sp);
+
+		int v = atoi(buf);
+
+		if (v > 255)
+			return no_match;
+		if (v > 0 && buf[0] == '0')
+			return no_match;
+
+		nums++;
+
+		if (*str == '\0')
+			break;
+
+		str++;
+	}
+
+	if (nums < 4)
+		return partly_match;
+
+	return exact_match;
+}
+
+static enum match_type match_ipv4_prefix(const char *str)
+{
+	const char *sp;
+	int dots = 0;
+	char buf[4];
+
+	for (;;) {
+		memset(buf, 0, sizeof(buf));
+		sp = str;
+		while (*str != '\0' && *str != '/') {
+			if (*str == '.') {
+				if (dots == 3)
+					return no_match;
+
+				if (*(str + 1) == '.' || *(str + 1) == '/')
+					return no_match;
+
+				if (*(str + 1) == '\0')
+					return partly_match;
+
+				dots++;
+				break;
+			}
+
+			if (!isdigit((unsigned char)*str))
+				return no_match;
+
+			str++;
+		}
+
+		if (str - sp > 3)
+			return no_match;
+
+		memcpy(buf, sp, str - sp);
+
+		int v = atoi(buf);
+
+		if (v > 255)
+			return no_match;
+		if (v > 0 && buf[0] == '0')
+			return no_match;
+
+		if (dots == 3) {
+			if (*str == '/') {
+				if (*(str + 1) == '\0')
+					return partly_match;
+
+				str++;
+				break;
+			} else if (*str == '\0')
+				return partly_match;
+		}
+
+		if (*str == '\0')
+			return partly_match;
+
+		str++;
+	}
+
+	sp = str;
+	while (*str != '\0') {
+		if (!isdigit((unsigned char)*str))
+			return no_match;
+
+		str++;
+	}
+
+	if (atoi(sp) > IPV4_MAX_BITLEN)
+		return no_match;
+
+	return exact_match;
+}
+
+#define IPV6_ADDR_STR   "0123456789abcdefABCDEF:."
+#define IPV6_PREFIX_STR "0123456789abcdefABCDEF:./"
+#define STATE_START     1
+#define STATE_COLON     2
+#define STATE_DOUBLE    3
+#define STATE_ADDR      4
+#define STATE_DOT       5
+#define STATE_SLASH     6
+#define STATE_MASK      7
+
+static enum match_type match_ipv6_prefix(const char *str, bool prefix)
+{
+	int state = STATE_START;
+	int colons = 0, nums = 0, double_colon = 0;
+	int mask;
+	const char *sp = NULL, *start = str;
+	char *endptr = NULL;
+
+	if (str == NULL)
+		return partly_match;
+
+	if (strspn(str, prefix ? IPV6_PREFIX_STR : IPV6_ADDR_STR)
+	    != strlen(str))
+		return no_match;
+
+	while (*str != '\0' && state != STATE_MASK) {
+		switch (state) {
+		case STATE_START:
+			if (*str == ':') {
+				if (*(str + 1) != ':' && *(str + 1) != '\0')
+					return no_match;
+				colons--;
+				state = STATE_COLON;
+			} else {
+				sp = str;
+				state = STATE_ADDR;
+			}
+
+			continue;
+		case STATE_COLON:
+			colons++;
+			if (*(str + 1) == '/')
+				return no_match;
+			else if (*(str + 1) == ':')
+				state = STATE_DOUBLE;
+			else {
+				sp = str + 1;
+				state = STATE_ADDR;
+			}
+			break;
+		case STATE_DOUBLE:
+			if (double_colon)
+				return no_match;
+
+			if (*(str + 1) == ':')
+				return no_match;
+			else {
+				if (*(str + 1) != '\0' && *(str + 1) != '/')
+					colons++;
+				sp = str + 1;
+
+				if (*(str + 1) == '/')
+					state = STATE_SLASH;
+				else
+					state = STATE_ADDR;
+			}
+
+			double_colon++;
+			nums += 1;
+			break;
+		case STATE_ADDR:
+			if (*(str + 1) == ':' || *(str + 1) == '.'
+			    || *(str + 1) == '\0' || *(str + 1) == '/') {
+				if (str - sp > 3)
+					return no_match;
+
+				for (; sp <= str; sp++)
+					if (*sp == '/')
+						return no_match;
+
+				nums++;
+
+				if (*(str + 1) == ':')
+					state = STATE_COLON;
+				else if (*(str + 1) == '.') {
+					if (colons || double_colon)
+						state = STATE_DOT;
+					else
+						return no_match;
+				} else if (*(str + 1) == '/')
+					state = STATE_SLASH;
+			}
+			break;
+		case STATE_DOT:
+			state = STATE_ADDR;
+			break;
+		case STATE_SLASH:
+			if (*(str + 1) == '\0')
+				return partly_match;
+
+			state = STATE_MASK;
+			break;
+		default:
+			break;
+		}
+
+		if (nums > 11)
+			return no_match;
+
+		if (colons > 7)
+			return no_match;
+
+		str++;
+	}
+
+	if (!prefix) {
+		struct sockaddr_in6 sin6_dummy;
+		int ret = inet_pton(AF_INET6, start, &sin6_dummy.sin6_addr);
+		return ret == 1 ? exact_match : partly_match;
+	}
+
+	if (state < STATE_MASK)
+		return partly_match;
+
+	mask = strtol(str, &endptr, 10);
+	if (*endptr != '\0')
+		return no_match;
+
+	if (mask < 0 || mask > IPV6_MAX_BITLEN)
+		return no_match;
+
+	return exact_match;
+}
+
+static enum match_type match_range(struct cmd_token *token, const char *str)
+{
+	assert(token->type == RANGE_TKN);
+
+	char *endptr = NULL;
+	long long val;
+
+	val = strtoll(str, &endptr, 10);
+	if (*endptr != '\0')
+		return no_match;
+
+	if (val < token->min || val > token->max)
+		return no_match;
+	else
+		return exact_match;
+}
+
+static enum match_type match_word(struct cmd_token *token, const char *word)
+{
+	assert(token->type == WORD_TKN);
+
+	// if the passed token is 0 length, partly match
+	if (!strlen(word))
+		return partly_match;
+
+	// if the passed token is strictly a prefix of the full word, partly
+	// match
+	if (strlen(word) < strlen(token->text))
+		return !strncmp(token->text, word, strlen(word)) ? partly_match
+								 : no_match;
+
+	// if they are the same length and exactly equal, exact match
+	else if (strlen(word) == strlen(token->text))
+		return !strncmp(token->text, word, strlen(word)) ? exact_match
+								 : no_match;
+
+	return no_match;
+}
+
+static enum match_type match_variable(struct cmd_token *token, const char *word)
+{
+	assert(token->type == VARIABLE_TKN);
+	return exact_match;
+}
+
+#define MAC_CHARS "ABCDEFabcdef0123456789:"
+
+static enum match_type match_mac(const char *word, bool prefix)
+{
+	/* 6 2-digit hex numbers separated by 5 colons */
+	size_t mac_explen = 6 * 2 + 5;
+	/* '/' + 2-digit integer */
+	size_t mask_len = 1 + 2;
+	unsigned int i;
+	char *eptr;
+	unsigned int maskval;
+
+	/* length check */
+	if (strlen(word) > mac_explen + (prefix ? mask_len : 0))
+		return no_match;
+
+	/* address check */
+	for (i = 0; i < mac_explen; i++) {
+		if (word[i] == '\0' || !strchr(MAC_CHARS, word[i]))
+			break;
+		if (((i + 1) % 3 == 0) != (word[i] == ':'))
+			return no_match;
+	}
+
+	/* incomplete address */
+	if (i < mac_explen && word[i] == '\0')
+		return partly_match;
+	else if (i < mac_explen)
+		return no_match;
+
+	/* mask check */
+	if (prefix && word[i] == '/') {
+		if (word[++i] == '\0')
+			return partly_match;
+
+		maskval = strtoul(&word[i], &eptr, 10);
+		if (*eptr != '\0' || maskval > 48)
+			return no_match;
+	} else if (prefix && word[i] == '\0') {
+		return partly_match;
+	} else if (prefix) {
+		return no_match;
+	}
+
+	return exact_match;
+}