From de9d7e4f3ccb1b199602c1a1ce884df37e54f834 Mon Sep 17 00:00:00 2001 From: Quentin Young Date: Fri, 29 Jul 2016 15:54:03 +0000 Subject: lib: Cleanup some memory issues in CLI Various memory leaks have been fixed and the quagga memory macros are in use. Also consolidated the argv and matching code into one graph traversal. Signed-off-by: Quentin Young --- lib/command_match.c | 326 ++++++++++++++++++++++++++-------------------------- 1 file changed, 166 insertions(+), 160 deletions(-) (limited to 'lib/command_match.c') diff --git a/lib/command_match.c b/lib/command_match.c index 023faafade..91b6069b1a 100644 --- a/lib/command_match.c +++ b/lib/command_match.c @@ -8,7 +8,7 @@ static int add_nexthops(struct list *, struct graph_node *); static struct list * -match_build_argv_r (struct graph_node *, vector, unsigned int); +match_command_r (struct graph_node *, vector, unsigned int); static int score_precedence (struct graph_node *); @@ -43,176 +43,86 @@ match_token (struct graph_node *, char *, enum filter_type); /* matching functions */ -struct cmd_element * -match_command (struct graph_node *start, const char *line, enum filter_type filter) -{ - // get all possible completions - struct list *completions = match_command_complete (start, line, filter); - - // one of them should be END_GN if this command matches - struct graph_node *gn; - struct listnode *node; - for (ALL_LIST_ELEMENTS_RO(completions,node,gn)) - { - if (gn->type == END_GN) - break; - gn = NULL; - } - return gn ? gn->element : NULL; +static void +free_nodelist (void *node) { + free_node ((struct graph_node *) node); } -struct list * -match_command_complete (struct graph_node *start, const char *line, enum filter_type filter) -{ - // vectorize command line - vector vline = cmd_make_strvec (line); - - // 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 *gn; - struct listnode *node; - - // add all children of start node to list - add_nexthops(next, start); - - unsigned int idx; - for (idx = 0; idx < vector_active(vline) && next->count > 0; idx++) - { - list_free (current); - current = next; - next = list_new(); - - token = vector_slot(vline, idx); - - list_delete_all_node(matched); - - for (ALL_LIST_ELEMENTS_RO(current,node,gn)) - { - if (match_token(gn, token, filter) == exact_match) { - listnode_add(matched, gn); - add_nexthops(next, gn); - } - } - } - - /* 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` - */ - list_free (current); - list_free (matched); - - cmd_free_strvec(vline); - - return next; -} - -/** - * 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 transparent. - * - * @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); - switch (child->type) { - case OPTION_GN: - case SELECTOR_GN: - case NUL_GN: - added += add_nexthops(l, child); - break; - default: - listnode_add(l, child); - added++; - } - } - return added; -} - -struct list * -match_build_argv (const char *line, struct cmd_element *element) +struct cmd_element * +match_command (struct graph_node *start, const char *line, struct list **argv) { - struct list *argv = NULL; - // parse command - struct graph_node *start = new_node(NUL_GN); - parse_command_format(start, element); - vector vline = cmd_make_strvec (line); for (unsigned int i = 0; i < vector_active(start->children); i++) { // call recursive builder on each starting child - argv = match_build_argv_r (vector_slot(start->children, i), vline, 0); + *argv = match_command_r(vector_slot(start->children, i), vline, 0); // if any of them succeed, return their argv - // since all command DFA's must begin with a word and these are deduplicated, - // no need to check precedence - if (argv) break; + // since all command DFA's must begin with a word, there can only be + // one valid return value + if (*argv) break; + } + + if (*argv) { + // copy the nodes we need + struct listnode *ln; + struct graph_node *gn; + char buf[50]; + for (ALL_LIST_ELEMENTS_RO(*argv,ln,gn)) { + describe_node(gn, buf, 50); + fprintf(stderr, "%s[%d]\n", buf, gn->type); + if (gn->type == END_GN) + return gn->element; + } + assert(0); } - return argv; + return NULL; } /** - * Builds an argument list given a DFA and a matching input line. - * This function should be passed the start node of the DFA, a matching - * input line, and the index of the first input token in the input line. + * Matches a given input line against a DFA. + * + * Builds an argument list given a DFA and a matching input line. This function + * should be passed the start node of the DFA, a matching input line, and the + * index of the first token in the 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. If it does - * match, then it saves the input token as the head of an argument list. + * First the function determines if the node it is passed matches the first + * token of input. If it does not, it returns NULL. 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_GN). If this is the case, then the - * bottom of the recursion stack has been reached, and the argument list - * (with one node) is returned. If it is not the case, NULL is returned, - * indicating that there is no match for the input along this path. + * 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_GN). If this is the case, then the bottom of the + * recursion stack has been reached, and the argument list (with one node) is + * returned. If it is not the case, NULL is returned, indicating that there is + * no match for the input along this path. * - * 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 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. + * 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 this command is totally ambiguous (how did you even match it in the first - * place?) and NULL is returned. + * then the input is ambiguous for the passed cmd_element and NULL is returned. * * The ultimate return value is an ordered linked list of nodes that comprise * the best match for the command, each with their `arg` fields pointing to the @@ -224,22 +134,19 @@ match_build_argv (const char *line, struct cmd_element *element) * callers. */ static struct list * -match_build_argv_r (struct graph_node *start, vector vline, unsigned int n) +match_command_r (struct graph_node *start, vector vline, unsigned int n) { // if we don't match this node, die if (match_token(start, vector_slot(vline, n), FILTER_STRICT) != exact_match) return NULL; // arg list for this subgraph - struct list *argv = list_new(); + struct list *argv; // pointers for iterating linklist struct graph_node *gn; struct listnode *ln; - // append current arg - listnode_add(argv, start); - // get all possible nexthops struct list *next = list_new(); add_nexthops(next, start); @@ -248,14 +155,22 @@ match_build_argv_r (struct graph_node *start, vector vline, unsigned int n) if (n+1 == vector_active (vline)) { for (ALL_LIST_ELEMENTS_RO(next,ln,gn)) { if (gn->type == END_GN) { + // delete nexthops, we don't need them list_delete (next); - start->arg = XSTRDUP(MTYPE_CMD_TOKENS, vector_slot(vline, n)); - if (start->type == VARIABLE_GN) - fprintf(stderr, "Setting variable %s->arg with text %s\n", start->text, start->arg); + // dupe current node, set arg field, and return + struct graph_node *curr = copy_node(start); + curr->arg = XSTRDUP(MTYPE_CMD_TOKENS, vector_slot(vline, n)); + fprintf(stderr, ">> Matched END_GN on node %s for token %s\n", curr->text, curr->arg); + // initialize a new argument list + argv = list_new(); + argv->del = &free_nodelist; + listnode_add(argv, curr); + listnode_add(argv, copy_node(gn)); return argv; } } - list_free (next); + // no END_GN found, free resources and return null + list_delete (next); return NULL; } @@ -269,7 +184,7 @@ match_build_argv_r (struct graph_node *start, vector vline, unsigned int n) // get the result of the next node for (unsigned int i = 0; i < n; i++) fprintf(stderr, "\t"); fprintf(stderr, "Recursing on node %s for token %s\n", gn->text, (char*) vector_slot(vline, n+1)); - struct list *result = match_build_argv_r (gn, vline, n+1); + struct list *result = match_command_r (gn, vline, n+1); // compare to our current best match, and save if it's better if (result) { @@ -288,7 +203,7 @@ match_build_argv_r (struct graph_node *start, vector vline, unsigned int n) fprintf(stderr, ">> Ambiguous match. Abort.\n"); list_delete (bestmatch); list_delete (result); - list_delete (argv); + list_delete (next); return NULL; } } @@ -301,19 +216,110 @@ match_build_argv_r (struct graph_node *start, vector vline, unsigned int n) } if (bestmatch) { + argv = list_new(); + listnode_add(argv, start); list_add_list(argv, bestmatch); - list_delete (bestmatch); + list_free (bestmatch); + list_delete (next); start->arg = XSTRDUP(MTYPE_CMD_TOKENS, vector_slot(vline, n)); if (start->type == VARIABLE_GN) fprintf(stderr, "Setting variable %s->arg with text %s\n", start->text, start->arg); return argv; } - else { - list_delete (argv); + else return NULL; +} + +struct list * +match_command_complete (struct graph_node *start, const char *line, enum filter_type filter) +{ + enum match_type minmatch = filter + 1; + + // vectorize command line + vector vline = cmd_make_strvec (line); + + // 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 *gn; + struct listnode *node; + + // add all children of start node to list + add_nexthops(next, start); + + unsigned int idx; + for (idx = 0; idx < vector_active(vline) && next->count > 0; idx++) + { + list_free (current); + current = next; + next = list_new(); + + token = vector_slot(vline, idx); + + list_delete_all_node(matched); + + for (ALL_LIST_ELEMENTS_RO(current,node,gn)) + { + if (match_token(gn, token, filter) >= minmatch) { + listnode_add(matched, gn); + add_nexthops(next, gn); + } + } } + + /* 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` + */ + list_free (current); + list_free (matched); + + cmd_free_strvec(vline); + + return next; } +/** + * 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 transparent. + * + * @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); + switch (child->type) { + case OPTION_GN: + case SELECTOR_GN: + case NUL_GN: + added += add_nexthops(l, child); + break; + default: + listnode_add(l, child); + added++; + } + } + return added; +} + + /* matching utility functions */ static int -- cgit v1.2.3