summaryrefslogtreecommitdiffstats
path: root/lib/command_match.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/command_match.c')
-rw-r--r--lib/command_match.c1072
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;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-27 21:44:17 +0000