]>
git.proxmox.com Git - mirror_frr.git/blob - lib/command_match.c
2 * Input matching routines for CLI backend.
5 * Copyright (C) 2016 Cumulus Networks, Inc.
7 * This file is part of GNU Zebra.
9 * GNU Zebra is free software; you can redistribute it and/or modify it
10 * under the terms of the GNU General Public License as published by the
11 * Free Software Foundation; either version 2, or (at your option) any
14 * GNU Zebra is distributed in the hope that it will be useful, but
15 * WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 * General Public License for more details.
19 * You should have received a copy of the GNU General Public License
20 * along with GNU Zebra; see the file COPYING. If not, write to the Free
21 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
27 #include "command_match.h"
28 #include "command_parse.h"
31 DEFINE_MTYPE_STATIC(LIB
, CMD_TOKENS
, "Command Tokens")
33 /* matcher helper prototypes */
35 add_nexthops (struct list
*, struct graph_node
*);
38 command_match_r (struct graph_node
*, vector
, unsigned int);
41 score_precedence (enum cmd_token_type
);
43 static enum match_type
44 min_match_level (enum cmd_token_type
);
47 del_arglist (struct list
*);
49 static struct cmd_token
*
50 disambiguate_tokens (struct cmd_token
*, struct cmd_token
*, char *);
53 disambiguate (struct list
*, struct list
*, vector
, unsigned int);
56 compare_completions (const void *, const void *);
58 /* token matcher prototypes */
59 static enum match_type
60 match_token (struct cmd_token
*, char *);
62 static enum match_type
63 match_ipv4 (const char *);
65 static enum match_type
66 match_ipv4_prefix (const char *);
68 static enum match_type
69 match_ipv6 (const char *);
71 static enum match_type
72 match_ipv6_prefix (const char *);
74 static enum match_type
75 match_range (struct cmd_token
*, const char *);
77 static enum match_type
78 match_word (struct cmd_token
*, const char *);
80 static enum match_type
81 match_variable (struct cmd_token
*, const char *);
83 /* matching functions */
84 static enum matcher_rv matcher_rv
;
87 command_match (struct graph
*cmdgraph
,
90 const struct cmd_element
**el
)
92 matcher_rv
= MATCHER_NO_MATCH
;
94 // prepend a dummy token to match that pesky start node
95 vector vvline
= vector_init (vline
->alloced
+ 1);
96 vector_set_index (vvline
, 0, (void *) XSTRDUP (MTYPE_TMP
, "dummy"));
97 memcpy (vvline
->index
+ 1, vline
->index
, sizeof (void *) * vline
->alloced
);
98 vvline
->active
= vline
->active
+ 1;
100 struct graph_node
*start
= vector_slot (cmdgraph
->nodes
, 0);
101 if ((*argv
= command_match_r (start
, vvline
, 0))) // successful match
103 struct listnode
*head
= listhead (*argv
);
104 struct listnode
*tail
= listtail (*argv
);
106 // delete dummy start node
107 del_cmd_token ((struct cmd_token
*) head
->data
);
108 list_delete_node (*argv
, head
);
110 // get cmd_element out of list tail
111 *el
= listgetdata (tail
);
112 list_delete_node (*argv
, tail
);
114 // now argv is an ordered list of cmd_token matching the user
115 // input, with each cmd_token->arg holding the corresponding input
121 fprintf (stdout
, "No match\n");
123 fprintf (stdout
, "Matched command\n->string %s\n->desc %s\n", (*el
)->string
, (*el
)->doc
);
126 // free the leader token we alloc'd
127 XFREE (MTYPE_TMP
, vector_slot (vvline
, 0));
129 vector_free (vvline
);
135 * Builds an argument list given a DFA and a matching input line.
137 * First the function determines if the node it is passed matches the first
138 * token of input. If it does not, it returns NULL (MATCHER_NO_MATCH). If it
139 * does match, then it saves the input token as the head of an argument list.
141 * The next step is to see if there is further input in the input line. If
142 * there is not, the current node's children are searched to see if any of them
143 * are leaves (type END_TKN). If this is the case, then the bottom of the
144 * recursion stack has been reached, the leaf is pushed onto the argument list,
145 * the current node is pushed, and the resulting argument list is
146 * returned (MATCHER_OK). If it is not the case, NULL is returned, indicating
147 * that there is no match for the input along this path (MATCHER_INCOMPLETE).
149 * If there is further input, then the function recurses on each of the current
150 * node's children, passing them the input line minus the token that was just
151 * matched. For each child, the return value of the recursive call is
152 * inspected. If it is null, then there is no match for the input along the
153 * subgraph headed by that child. If it is not null, then there is at least one
154 * input match in that subgraph (more on this in a moment).
156 * If a recursive call on a child returns a non-null value, then it has matched
157 * the input given it on the subgraph that starts with that child. However, due
158 * to the flexibility of the grammar, it is sometimes the case that two or more
159 * child graphs match the same input (two or more of the recursive calls have
160 * non-NULL return values). This is not a valid state, since only one true
161 * match is possible. In order to resolve this conflict, the function keeps a
162 * reference to the child node that most specifically matches the input. This
163 * is done by assigning each node type a precedence. If a child is found to
164 * match the remaining input, then the precedence values of the current
165 * best-matching child and this new match are compared. The node with higher
166 * precedence is kept, and the other match is discarded. Due to the recursive
167 * nature of this function, it is only necessary to compare the precedence of
168 * immediate children, since all subsequent children will already have been
169 * disambiguated in this way.
171 * In the event that two children are found to match with the same precedence,
172 * then the input is ambiguous for the passed cmd_element and NULL is returned.
174 * @param[in] start the start node.
175 * @param[in] vline the vectorized input line.
176 * @param[in] n the index of the first input token.
177 * @return A linked list of n elements. The first n-1 elements are pointers to
178 * struct cmd_token and represent the sequence of tokens matched by the input.
179 * The ->arg field of each token points to a copy of the input matched on it.
180 * The final nth element is a pointer to struct cmd_element, which is the
181 * command that was matched.
183 * If no match was found, the return value is NULL.
186 command_match_r (struct graph_node
*start
, vector vline
, unsigned int n
)
188 assert (n
< vector_active (vline
));
190 // get the minimum match level that can count as a full match
191 struct cmd_token
*token
= start
->data
;
192 enum match_type minmatch
= min_match_level (token
->type
);
194 // get the current operating input token
195 char *input_token
= vector_slot (vline
, n
);
198 fprintf (stdout
, "\"%-20s\" matches \"%-30s\" ? ", input_token
, token
->text
);
199 enum match_type mt
= match_token (token
, input_token
);
200 fprintf (stdout
, "min: %d - ", minmatch
);
204 fprintf (stdout
, "trivial_match ");
207 fprintf (stdout
, "no_match ");
210 fprintf (stdout
, "partly_match ");
213 fprintf (stdout
, "exact_match ");
216 if (mt
>= minmatch
) fprintf (stdout
, " MATCH");
217 fprintf (stdout
, "\n");
220 // if we don't match this node, die
221 if (match_token (token
, input_token
) < minmatch
)
224 // pointers for iterating linklist
226 struct graph_node
*gn
;
228 // get all possible nexthops
229 struct list
*next
= list_new();
230 add_nexthops (next
, start
);
232 // determine the best match
234 struct list
*currbest
= NULL
;
235 for (ALL_LIST_ELEMENTS_RO (next
,ln
,gn
))
237 // if we've matched all input we're looking for END_TKN
238 if (n
+1 == vector_active (vline
))
240 struct cmd_token
*tok
= gn
->data
;
241 if (tok
->type
== END_TKN
)
243 if (currbest
) // there is more than one END_TKN in the follow set
248 currbest
= list_new();
249 // node should have one child node with the element
250 struct graph_node
*leaf
= vector_slot (gn
->to
, 0);
251 // last node in the list will hold the cmd_element;
252 // this is important because list_delete() expects
253 // that all nodes have the same data type, so when
254 // deleting this list the last node must be
256 struct cmd_element
*el
= leaf
->data
;
257 listnode_add (currbest
, el
);
258 currbest
->del
= (void (*)(void *)) &del_cmd_token
;
259 // do not break immediately; continue walking through the follow set
260 // to ensure that there is exactly one END_TKN
265 // else recurse on candidate child node
266 struct list
*result
= command_match_r (gn
, vline
, n
+1);
268 // save the best match
269 if (result
&& currbest
)
271 // pick the best of two matches
272 struct list
*newbest
= disambiguate (currbest
, result
, vline
, n
+1);
273 // set ambiguity flag
274 ambiguous
= !newbest
|| (ambiguous
&& newbest
== currbest
);
275 // delete the unnecessary result
276 struct list
*todelete
= ((newbest
&& newbest
== result
) ? currbest
: result
);
277 del_arglist (todelete
);
279 currbest
= newbest
? newbest
: currbest
;
289 del_arglist (currbest
);
291 matcher_rv
= MATCHER_AMBIGUOUS
;
295 // copy token, set arg and prepend to currbest
296 struct cmd_token
*token
= start
->data
;
297 struct cmd_token
*copy
= copy_cmd_token (token
);
298 copy
->arg
= XSTRDUP (MTYPE_CMD_TOKENS
, input_token
);
299 listnode_add_before (currbest
, currbest
->head
, copy
);
300 matcher_rv
= MATCHER_OK
;
303 else if (n
+1 == vector_active (vline
) && matcher_rv
== MATCHER_NO_MATCH
)
304 matcher_rv
= MATCHER_INCOMPLETE
;
313 command_complete (struct graph
*graph
,
315 struct list
**completions
)
317 // pointer to next input token to match
320 struct list
*current
= list_new(), // current nodes to match input token against
321 *next
= list_new(); // possible next hops after current input token
323 // pointers used for iterating lists
324 struct graph_node
*gn
;
325 struct listnode
*node
;
327 // add all children of start node to list
328 struct graph_node
*start
= vector_slot (graph
->nodes
, 0);
329 add_nexthops (next
, start
);
332 for (idx
= 0; idx
< vector_active (vline
) && next
->count
> 0; idx
++)
334 list_delete (current
);
338 input_token
= vector_slot (vline
, idx
);
340 for (ALL_LIST_ELEMENTS_RO (current
,node
,gn
))
342 struct cmd_token
*token
= gn
->data
;
344 if (token
->attr
== CMD_ATTR_HIDDEN
|| token
->attr
== CMD_ATTR_DEPRECATED
)
347 enum match_type minmatch
= min_match_level (token
->type
);
349 fprintf (stdout
, "\"%s\" matches \"%s\" (%d) ? ", input_token
, token
->text
, token
->type
);
352 switch (match_token (token
, input_token
))
356 fprintf (stdout
, "trivial_match\n");
360 fprintf (stdout
, "partly_match\n");
362 if (idx
== vector_active (vline
) - 1)
364 listnode_add (next
, gn
);
367 if (minmatch
> partly_match
)
371 fprintf (stdout
, "exact_match\n");
373 add_nexthops (next
, gn
);
377 fprintf (stdout
, "no_match\n");
385 * -----------------------------------------------------------------
386 * token = last input token processed
387 * idx = index in `command` of last token processed
388 * current = set of all transitions from the previous input token
389 * next = set of all nodes reachable from all nodes in `matched`
393 idx
== vector_active(vline
) && next
->count
?
398 if (!MATCHER_ERROR(matcher_rv
))
400 // extract cmd_token into list
401 *completions
= list_new ();
402 for (ALL_LIST_ELEMENTS_RO (next
,node
,gn
))
403 listnode_add (*completions
, gn
->data
);
406 list_delete (current
);
413 * Adds all children that are reachable by one parser hop to the given list.
414 * NUL_TKN, SELECTOR_TKN, and OPTION_TKN nodes are treated as transparent.
416 * @param[in] list to add the nexthops to
417 * @param[in] node to start calculating nexthops from
418 * @return the number of children added to the list
421 add_nexthops (struct list
*list
, struct graph_node
*node
)
424 struct graph_node
*child
;
425 for (unsigned int i
= 0; i
< vector_active (node
->to
); i
++)
427 child
= vector_slot (node
->to
, i
);
428 struct cmd_token
*token
= child
->data
;
434 added
+= add_nexthops (list
, child
);
437 listnode_add (list
, child
);
446 * Determines the node types for which a partial match may count as a full
447 * match. Enables command abbrevations.
449 * @param[in] type node type
450 * @return minimum match level needed to for a token to fully match
452 static enum match_type
453 min_match_level (enum cmd_token_type type
)
457 // anything matches a start node, for the sake of recursion
460 // allowing words to partly match enables command abbreviation
469 * Assigns precedence scores to node types.
471 * @param[in] type node type to score
472 * @return precedence score
475 score_precedence (enum cmd_token_type type
)
479 // some of these are mutually exclusive, so they share
480 // the same precedence value
482 case IPV4_PREFIX_TKN
:
484 case IPV6_PREFIX_TKN
:
497 * Picks the better of two possible matches for a token.
499 * @param[in] first candidate node matching token
500 * @param[in] second candidate node matching token
501 * @param[in] token the token being matched
502 * @return the best-matching node, or NULL if the two are entirely ambiguous
504 static struct cmd_token
*
505 disambiguate_tokens (struct cmd_token
*first
,
506 struct cmd_token
*second
,
509 // if the types are different, simply go off of type precedence
510 if (first
->type
!= second
->type
)
512 int firstprec
= score_precedence (first
->type
);
513 int secndprec
= score_precedence (second
->type
);
514 if (firstprec
!= secndprec
)
515 return firstprec
< secndprec
? first
: second
;
520 // if they're the same, return the more exact match
521 enum match_type fmtype
= match_token (first
, input_token
);
522 enum match_type smtype
= match_token (second
, input_token
);
523 if (fmtype
!= smtype
)
524 return fmtype
> smtype
? first
: second
;
530 * Picks the better of two possible matches for an input line.
532 * @param[in] first candidate list of cmd_token matching vline
533 * @param[in] second candidate list of cmd_token matching vline
534 * @param[in] vline the input line being matched
535 * @param[in] n index into vline to start comparing at
536 * @return the best-matching list, or NULL if the two are entirely ambiguous
539 disambiguate (struct list
*first
,
544 // doesn't make sense for these to be inequal length
545 assert (first
->count
== second
->count
);
546 assert (first
->count
== vector_active (vline
) - n
+1);
548 struct listnode
*fnode
= listhead (first
),
549 *snode
= listhead (second
);
550 struct cmd_token
*ftok
= listgetdata (fnode
),
551 *stok
= listgetdata (snode
),
554 // compare each token, if one matches better use that one
555 for (unsigned int i
= n
; i
< vector_active (vline
); i
++)
557 char *token
= vector_slot(vline
, i
);
558 if ((best
= disambiguate_tokens (ftok
, stok
, token
)))
559 return best
== ftok
? first
: second
;
560 fnode
= listnextnode (fnode
);
561 snode
= listnextnode (snode
);
562 ftok
= listgetdata (fnode
);
563 stok
= listgetdata (snode
);
570 * Deletion function for arglist.
572 * Since list->del for arglists expects all listnode->data to hold cmd_token,
573 * but arglists have cmd_element as the data for the tail, this function
574 * manually deletes the tail before deleting the rest of the list as usual.
576 * The cmd_element at the end is *not* a copy. It is the one and only.
578 * @param list the arglist to delete
581 del_arglist (struct list
*list
)
583 // manually delete last node
584 struct listnode
*tail
= listtail (list
);
586 list_delete_node (list
, tail
);
588 // delete the rest of the list as usual
592 /*---------- token level matching functions ----------*/
594 static enum match_type
595 match_token (struct cmd_token
*token
, char *input_token
)
597 // nothing trivially matches everything
599 return trivial_match
;
601 switch (token
->type
) {
603 return match_word (token
, input_token
);
605 return match_ipv4 (input_token
);
606 case IPV4_PREFIX_TKN
:
607 return match_ipv4_prefix (input_token
);
609 return match_ipv6 (input_token
);
610 case IPV6_PREFIX_TKN
:
611 return match_ipv6_prefix (input_token
);
613 return match_range (token
, input_token
);
615 return match_variable (token
, input_token
);
622 #define IPV4_ADDR_STR "0123456789."
623 #define IPV4_PREFIX_STR "0123456789./"
625 static enum match_type
626 match_ipv4 (const char *str
)
629 int dots
= 0, nums
= 0;
634 memset (buf
, 0, sizeof (buf
));
643 if (*(str
+ 1) == '.')
646 if (*(str
+ 1) == '\0')
652 if (!isdigit ((int) *str
))
661 strncpy (buf
, sp
, str
- sp
);
662 if (atoi (buf
) > 255)
679 static enum match_type
680 match_ipv4_prefix (const char *str
)
688 memset (buf
, 0, sizeof (buf
));
690 while (*str
!= '\0' && *str
!= '/')
697 if (*(str
+ 1) == '.' || *(str
+ 1) == '/')
700 if (*(str
+ 1) == '\0')
707 if (!isdigit ((int) *str
))
716 strncpy (buf
, sp
, str
- sp
);
717 if (atoi (buf
) > 255)
724 if (*(str
+ 1) == '\0')
730 else if (*str
== '\0')
743 if (!isdigit ((int) *str
))
756 #define IPV6_ADDR_STR "0123456789abcdefABCDEF:."
757 #define IPV6_PREFIX_STR "0123456789abcdefABCDEF:./"
759 static enum match_type
760 match_ipv6 (const char *str
)
762 struct sockaddr_in6 sin6_dummy
;
765 if (strspn (str
, IPV6_ADDR_STR
) != strlen (str
))
768 ret
= inet_pton(AF_INET6
, str
, &sin6_dummy
.sin6_addr
);
776 static enum match_type
777 match_ipv6_prefix (const char *str
)
779 struct sockaddr_in6 sin6_dummy
;
780 const char *delim
= "/\0";
781 char *tofree
, *dupe
, *prefix
, *mask
, *endptr
;
784 if (strspn (str
, IPV6_PREFIX_STR
) != strlen (str
))
787 /* tokenize to prefix + mask */
788 tofree
= dupe
= XSTRDUP (MTYPE_TMP
, str
);
789 prefix
= strsep (&dupe
, delim
);
792 /* validate prefix */
793 if (inet_pton (AF_INET6
, prefix
, &sin6_dummy
.sin6_addr
) != 1)
795 XFREE (MTYPE_TMP
, tofree
);
802 XFREE (MTYPE_TMP
, tofree
);
806 nmask
= strtoimax (mask
, &endptr
, 10);
807 if (*endptr
!= '\0' || nmask
< 0 || nmask
> 128)
809 XFREE (MTYPE_TMP
, tofree
);
813 XFREE (MTYPE_TMP
, tofree
);
818 static enum match_type
819 match_range (struct cmd_token
*token
, const char *str
)
821 assert (token
->type
== RANGE_TKN
);
826 val
= strtoll (str
, &endptr
, 10);
830 if (val
< token
->min
|| val
> token
->max
)
836 static enum match_type
837 match_word (struct cmd_token
*token
, const char *word
)
839 assert (token
->type
== WORD_TKN
);
841 // if the passed token is 0 length, partly match
845 // if the passed token is strictly a prefix of the full word, partly match
846 if (strlen (word
) < strlen (token
->text
))
847 return !strncmp (token
->text
, word
, strlen (word
)) ?
851 // if they are the same length and exactly equal, exact match
852 else if (strlen (word
) == strlen (token
->text
))
853 return !strncmp (token
->text
, word
, strlen (word
)) ? exact_match
: no_match
;
858 #define VARIABLE_ALPHABET \
859 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890:/._-"
861 static enum match_type
862 match_variable (struct cmd_token
*token
, const char *word
)
864 assert (token
->type
== VARIABLE_TKN
);
866 return strlen (word
) == strspn(word
, VARIABLE_ALPHABET
) ?
867 exact_match
: no_match
;