From 18be0e599d1ba666e59a3d027e973eb41798f46f Mon Sep 17 00:00:00 2001 From: Quentin Young Date: Thu, 21 Jul 2016 21:38:03 +0000 Subject: lib: Mostly complete matcher Input matching and completions works. Still some rough edges. Signed-off-by: Quentin Young --- lib/command_match.c | 181 +++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 178 insertions(+), 3 deletions(-) (limited to 'lib/command_match.c') diff --git a/lib/command_match.c b/lib/command_match.c index bcc28bdc5b..f7e2789253 100644 --- a/lib/command_match.c +++ b/lib/command_match.c @@ -1,12 +1,187 @@ #include #include "memory.h" +#include "vector.h" #include "command_match.h" -enum match_type +static enum match_type +match_token (struct graph_node *node, char *token, enum filter_type filter) +{ + switch (node->type) { + case WORD_GN: + return cmd_word_match (node, filter, token); + case IPV4_GN: + return cmd_ipv4_match (token); + case IPV4_PREFIX_GN: + return cmd_ipv4_prefix_match (token); + case IPV6_GN: + return cmd_ipv6_match (token); + case IPV6_PREFIX_GN: + return cmd_ipv6_prefix_match (token); + case RANGE_GN: + return cmd_range_match (node, token); + case NUMBER_GN: + return node->value == atoi(token); + case VARIABLE_GN: + default: + return no_match; + } +} + +/* Breaking up string into each command piece. I assume given + character is separated by a space character. Return value is a + vector which includes char ** data element. */ +static vector +cmd_make_strvec (const char *string) +{ + const char *cp, *start; + char *token; + int strlen; + vector strvec; + + if (string == NULL) + return NULL; + + cp = string; + + /* Skip white spaces. */ + while (isspace ((int) *cp) && *cp != '\0') + cp++; + + /* Return if there is only white spaces */ + if (*cp == '\0') + return NULL; + + if (*cp == '!' || *cp == '#') + return NULL; + + /* Prepare return vector. */ + strvec = vector_init (VECTOR_MIN_SIZE); + + /* Copy each command piece and set into vector. */ + while (1) + { + start = cp; + while (!(isspace ((int) *cp) || *cp == '\r' || *cp == '\n') && + *cp != '\0') + cp++; + strlen = cp - start; + token = XMALLOC (MTYPE_STRVEC, strlen + 1); + memcpy (token, start, strlen); + *(token + strlen) = '\0'; + vector_set (strvec, token); + + while ((isspace ((int) *cp) || *cp == '\n' || *cp == '\r') && + *cp != '\0') + cp++; + + if (*cp == '\0') + return strvec; + } +} + +/** + * Adds all children that are reachable by one parser hop + * to the given list. NUL_GN, SELECTOR_GN, and OPTION_GN + * nodes are treated as though their children are attached + * to their parent. + * + * @param[out] l the list to add the children to + * @param[in] node the node to get the children of + * @return the number of children added to the list + */ +static int +add_nexthops(struct list *l, struct graph_node *node) +{ + int added = 0; + struct graph_node *child; + for (unsigned int i = 0; i < vector_active(node->children); i++) + { + child = vector_slot(node->children, i); + if (child->type == OPTION_GN || child->type == SELECTOR_GN || child->type == NUL_GN) + added += add_nexthops(l, child); + else { + listnode_add(l, child); + added++; + } + } + return added; +} + +/** + * Compiles matches or next-hops for a given line of user input. + * + * Given a string of input and a start node for a matching DFA, runs the input + * against the DFA until the input is exhausted, there are no possible + * transitions, or both. + * If there are no further state transitions available, one of two scenarios is possible: + * - The end of input has been reached. This indicates a valid command. + * - The end of input has not yet been reached. The input does not match any command. + * If there are further transitions available, one of two scenarios is possible: + * - The current input is a valid prefix to a longer command + * - The current input matches a command + * - The current input matches a command, and is also a valid prefix to a longer command + * + * Any other states indicate a programming error. + * + * @param[in] start the start node of the DFA to match against + * @param[in] filter the filtering method + * @param[in] input the input string + * @return an array with two lists. The first list is + */ +struct list** match_command (struct graph_node *start, enum filter_type filter, const char *input) { - // match input on DFA - return exact_match; + // break command + vector command = cmd_make_strvec (input); + + // pointer to next input token to match + char *token; + + struct list *current = list_new(), // current nodes to match input token against + *matched = list_new(), // current nodes that match the input token + *next = list_new(); // possible next hops to current input token + + // pointers used for iterating lists + struct graph_node *cnode; + struct listnode *node; + + // add all children of start node to list + add_nexthops(next, start); + + unsigned int idx; + for (idx = 0; idx < vector_active(command) && next->count > 0; idx++) + { + list_free (current); + current = next; + next = list_new(); + + token = vector_slot(command, idx); + + list_delete_all_node(matched); + + for (ALL_LIST_ELEMENTS_RO(current,node,cnode)) + { + if (match_token(cnode, token, filter) == exact_match) { + listnode_add(matched, cnode); + add_nexthops(next, cnode); + } + } + } + + /* 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 + * matched = set of all nodes reachable with current input + * next = set of all nodes reachable from all nodes in `matched` + */ + + struct list **result = malloc( 2 * sizeof(struct list *) ); + result[0] = matched; + result[1] = next; + + return result; } -- cgit v1.2.3