]>
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
26 #include "command_match.h"
27 #include "command_parse.h"
28 #include "grammar_sandbox.h"
31 /* matcher helper prototypes */
33 add_nexthops (struct list
*, struct graph_node
*);
36 command_match_r (struct graph_node
*, vector
, unsigned int);
39 score_precedence (enum cmd_token_type_t
);
41 static enum match_type
42 min_match_level (enum cmd_token_type_t
);
45 del_arglist (struct list
*);
47 static struct cmd_token_t
*
48 disambiguate_tokens (struct cmd_token_t
*, struct cmd_token_t
*, char *);
51 disambiguate (struct list
*, struct list
*, vector
, unsigned int);
54 compare_completions (const void *, const void *);
56 /* token matcher prototypes */
57 static enum match_type
58 match_token (struct cmd_token_t
*, char *);
60 static enum match_type
61 match_ipv4 (const char *);
63 static enum match_type
64 match_ipv4_prefix (const char *);
66 static enum match_type
67 match_ipv6 (const char *);
69 static enum match_type
70 match_ipv6_prefix (const char *);
72 static enum match_type
73 match_range (struct cmd_token_t
*, const char *);
75 static enum match_type
76 match_word (struct cmd_token_t
*, const char *);
78 static enum match_type
79 match_number (struct cmd_token_t
*, const char *);
81 static enum match_type
82 match_variable (struct cmd_token_t
*, const char *);
84 /* matching functions */
85 static enum matcher_rv matcher_rv
;
88 command_match (struct graph
*cmdgraph
,
91 struct cmd_element
**el
)
93 matcher_rv
= MATCHER_NO_MATCH
;
95 // prepend a dummy token to match that pesky start node
96 vector vvline
= vector_init (vline
->alloced
+ 1);
97 vector_set_index (vvline
, 0, (void *) XSTRDUP (MTYPE_TMP
, "dummy"));
98 memcpy (vvline
->index
+ 1, vline
->index
, sizeof (void *) * vline
->alloced
);
99 vvline
->active
= vline
->active
+ 1;
101 struct graph_node
*start
= vector_slot (cmdgraph
->nodes
, 0);
102 if ((*argv
= command_match_r (start
, vvline
, 0))) // successful match
104 struct listnode
*head
= listhead (*argv
);
105 struct listnode
*tail
= listtail (*argv
);
107 // delete dummy start node
108 del_cmd_token ((struct cmd_token_t
*) head
->data
);
109 list_delete_node (*argv
, head
);
111 // get cmd_element out of list tail
112 *el
= listgetdata (tail
);
113 list_delete_node (*argv
, tail
);
115 // now argv is an ordered list of cmd_token matching the user
116 // input, with each cmd_token->arg holding the corresponding input
120 // free the leader token we alloc'd
121 XFREE (MTYPE_TMP
, vector_slot (vvline
, 0));
123 vector_free (vvline
);
129 * Builds an argument list given a DFA and a matching input line.
131 * First the function determines if the node it is passed matches the first
132 * token of input. If it does not, it returns NULL (MATCHER_NO_MATCH). If it
133 * does match, then it saves the input token as the head of an argument list.
135 * The next step is to see if there is further input in the input line. If
136 * there is not, the current node's children are searched to see if any of them
137 * are leaves (type END_TKN). If this is the case, then the bottom of the
138 * recursion stack has been reached, the leaf is pushed onto the argument list,
139 * the current node is pushed, and the resulting argument list is
140 * returned (MATCHER_OK). If it is not the case, NULL is returned, indicating
141 * that there is no match for the input along this path (MATCHER_INCOMPLETE).
143 * If there is further input, then the function recurses on each of the current
144 * node's children, passing them the input line minus the token that was just
145 * matched. For each child, the return value of the recursive call is
146 * inspected. If it is null, then there is no match for the input along the
147 * subgraph headed by that child. If it is not null, then there is at least one
148 * input match in that subgraph (more on this in a moment).
150 * If a recursive call on a child returns a non-null value, then it has matched
151 * the input given it on the subgraph that starts with that child. However, due
152 * to the flexibility of the grammar, it is sometimes the case that two or more
153 * child graphs match the same input (two or more of the recursive calls have
154 * non-NULL return values). This is not a valid state, since only one true
155 * match is possible. In order to resolve this conflict, the function keeps a
156 * reference to the child node that most specifically matches the input. This
157 * is done by assigning each node type a precedence. If a child is found to
158 * match the remaining input, then the precedence values of the current
159 * best-matching child and this new match are compared. The node with higher
160 * precedence is kept, and the other match is discarded. Due to the recursive
161 * nature of this function, it is only necessary to compare the precedence of
162 * immediate children, since all subsequent children will already have been
163 * disambiguated in this way.
165 * In the event that two children are found to match with the same precedence,
166 * then the input is ambiguous for the passed cmd_element and NULL is returned.
168 * The ultimate return value is an ordered linked list of nodes that comprise
169 * the best match for the command, each with their `arg` fields pointing to the
170 * matching token string.
172 * @param[in] start the start node.
173 * @param[in] vline the vectorized input line.
174 * @param[in] n the index of the first input token.
177 command_match_r (struct graph_node
*start
, vector vline
, unsigned int n
)
179 assert (n
< vector_active (vline
));
181 // get the minimum match level that can count as a full match
182 struct cmd_token_t
*token
= start
->data
;
183 enum match_type minmatch
= min_match_level (token
->type
);
185 // get the current operating input token
186 char *input_token
= vector_slot (vline
, n
);
188 // if we don't match this node, die
189 if (match_token (token
, input_token
) < minmatch
)
192 // pointers for iterating linklist
194 struct graph_node
*gn
;
196 // get all possible nexthops
197 struct list
*next
= list_new();
198 add_nexthops (next
, start
);
200 // determine the best match
202 struct list
*currbest
= NULL
;
203 for (ALL_LIST_ELEMENTS_RO (next
,ln
,gn
))
205 // if we've matched all input we're looking for END_TKN
206 if (n
+1 == vector_active (vline
))
208 struct cmd_token_t
*tok
= gn
->data
;
209 if (tok
->type
== END_TKN
)
211 currbest
= list_new();
212 // node should have one child node with the element
213 struct graph_node
*leaf
= vector_slot (gn
->to
, 0);
214 // last node in the list will hold the cmd_element;
215 // this is important because list_delete() expects
216 // that all nodes have the same data type, so when
217 // deleting this list the last node must be
219 struct cmd_element
*el
= leaf
->data
;
220 listnode_add (currbest
, copy_cmd_element (el
));
221 currbest
->del
= (void (*)(void *)) &del_cmd_token
;
227 // else recurse on candidate child node
228 struct list
*result
= command_match_r (gn
, vline
, n
+1);
230 // save the best match
231 if (result
&& currbest
)
233 // pick the best of two matches
234 struct list
*newbest
= disambiguate (currbest
, result
, vline
, n
+1);
235 // set ambiguity flag
236 ambiguous
= !newbest
|| (ambiguous
&& newbest
== currbest
);
237 // delete the unnecessary result
238 struct list
*todelete
= ((newbest
&& newbest
== result
) ? currbest
: result
);
239 del_arglist (todelete
);
241 currbest
= newbest
? newbest
: currbest
;
251 del_arglist (currbest
);
253 matcher_rv
= MATCHER_AMBIGUOUS
;
257 // copy token, set arg and prepend to currbest
258 struct cmd_token_t
*token
= start
->data
;
259 struct cmd_token_t
*copy
= copy_cmd_token (token
);
260 copy
->arg
= XSTRDUP (MTYPE_CMD_TOKENS
, input_token
);
261 list_add_node_prev (currbest
, currbest
->head
, copy
);
262 matcher_rv
= MATCHER_OK
;
265 else if (n
+1 == vector_active (vline
) && matcher_rv
== MATCHER_NO_MATCH
)
266 matcher_rv
= MATCHER_INCOMPLETE
;
275 command_complete (struct graph
*graph
,
277 struct list
**completions
)
279 // pointer to next input token to match
282 struct list
*current
= list_new(), // current nodes to match input token against
283 *next
= list_new(); // possible next hops after current input token
285 // pointers used for iterating lists
286 struct graph_node
*gn
;
287 struct listnode
*node
;
289 // add all children of start node to list
290 struct graph_node
*start
= vector_slot (graph
->nodes
, 0);
291 add_nexthops (next
, start
);
294 for (idx
= 0; idx
< vector_active (vline
) && next
->count
> 0; idx
++)
296 list_delete (current
);
300 input_token
= vector_slot (vline
, idx
);
302 for (ALL_LIST_ELEMENTS_RO (current
,node
,gn
))
304 struct cmd_token_t
*token
= gn
->data
;
305 switch (match_token (token
, input_token
))
308 if (idx
== vector_active (vline
) - 1)
310 listnode_add (next
, gn
);
314 add_nexthops (next
, gn
);
323 * -----------------------------------------------------------------
324 * token = last input token processed
325 * idx = index in `command` of last token processed
326 * current = set of all transitions from the previous input token
327 * next = set of all nodes reachable from all nodes in `matched`
331 idx
== vector_active(vline
) && next
->count
?
335 // extract cmd_token into list
336 *completions
= list_new ();
337 for (ALL_LIST_ELEMENTS_RO (next
,node
,gn
))
338 listnode_add (*completions
, gn
->data
);
340 list_delete (current
);
347 * Adds all children that are reachable by one parser hop to the given list.
348 * NUL_TKN, SELECTOR_TKN, and OPTION_TKN nodes are treated as transparent.
350 * @param[in] list to add the nexthops to
351 * @param[in] node to start calculating nexthops from
352 * @return the number of children added to the list
355 add_nexthops (struct list
*list
, struct graph_node
*node
)
358 struct graph_node
*child
;
359 for (unsigned int i
= 0; i
< vector_active (node
->to
); i
++)
361 child
= vector_slot (node
->to
, i
);
362 struct cmd_token_t
*token
= child
->data
;
368 added
+= add_nexthops (list
, child
);
371 listnode_add (list
, child
);
380 * Determines the node types for which a partial match may count as a full
381 * match. Enables command abbrevations.
383 * @param[in] type node type
384 * @return minimum match level needed to for a token to fully match
386 static enum match_type
387 min_match_level (enum cmd_token_type_t type
)
391 // anything matches a start node, for the sake of recursion
394 // allowing words to partly match enables command abbreviation
403 * Assigns precedence scores to node types.
405 * @param[in] type node type to score
406 * @return precedence score
409 score_precedence (enum cmd_token_type_t type
)
413 // some of these are mutually exclusive, so they share
414 // the same precedence value
416 case IPV4_PREFIX_TKN
:
418 case IPV6_PREFIX_TKN
:
433 * Picks the better of two possible matches for a token.
435 * @param[in] first candidate node matching token
436 * @param[in] second candidate node matching token
437 * @param[in] token the token being matched
438 * @return the best-matching node, or NULL if the two are entirely ambiguous
440 static struct cmd_token_t
*
441 disambiguate_tokens (struct cmd_token_t
*first
,
442 struct cmd_token_t
*second
,
445 // if the types are different, simply go off of type precedence
446 if (first
->type
!= second
->type
)
448 int firstprec
= score_precedence (first
->type
);
449 int secndprec
= score_precedence (second
->type
);
450 if (firstprec
!= secndprec
)
451 return firstprec
< secndprec
? first
: second
;
456 // if they're the same, return the more exact match
457 enum match_type fmtype
= match_token (first
, input_token
);
458 enum match_type smtype
= match_token (second
, input_token
);
459 if (fmtype
!= smtype
)
460 return fmtype
> smtype
? first
: second
;
466 * Picks the better of two possible matches for an input line.
468 * @param[in] first candidate list of cmd_token_t matching vline
469 * @param[in] second candidate list of cmd_token_t matching vline
470 * @param[in] vline the input line being matched
471 * @param[in] n index into vline to start comparing at
472 * @return the best-matching list, or NULL if the two are entirely ambiguous
475 disambiguate (struct list
*first
,
480 // doesn't make sense for these to be inequal length
481 assert (first
->count
== second
->count
);
482 assert (first
->count
== vector_active (vline
) - n
+1);
484 struct listnode
*fnode
= listhead (first
),
485 *snode
= listhead (second
);
486 struct cmd_token_t
*ftok
= listgetdata (fnode
),
487 *stok
= listgetdata (snode
),
490 // compare each token, if one matches better use that one
491 for (unsigned int i
= n
; i
< vector_active (vline
); i
++)
493 char *token
= vector_slot(vline
, i
);
494 if ((best
= disambiguate_tokens (ftok
, stok
, token
)))
495 return best
== ftok
? first
: second
;
496 fnode
= listnextnode (fnode
);
497 snode
= listnextnode (snode
);
498 ftok
= listgetdata (fnode
);
499 stok
= listgetdata (snode
);
506 * Deletion function for arglist.
508 * Since list->del for arglists expects all listnode->data to hold cmd_token,
509 * but arglists have cmd_element as the data for the tail, this function
510 * manually deletes the tail before deleting the rest of the list as usual.
512 * @param list the arglist to delete
515 del_arglist (struct list
*list
)
517 // manually delete last node
518 struct listnode
*tail
= listtail (list
);
519 del_cmd_element (tail
->data
);
521 list_delete_node (list
, tail
);
523 // delete the rest of the list as usual
527 /*---------- token level matching functions ----------*/
529 static enum match_type
530 match_token (struct cmd_token_t
*token
, char *input_token
)
532 switch (token
->type
) {
534 return match_word (token
, input_token
);
536 return match_ipv4 (input_token
);
537 case IPV4_PREFIX_TKN
:
538 return match_ipv4_prefix (input_token
);
540 return match_ipv6 (input_token
);
541 case IPV6_PREFIX_TKN
:
542 return match_ipv6_prefix (input_token
);
544 return match_range (token
, input_token
);
546 return match_number (token
, input_token
);
548 return match_variable (token
, input_token
);
555 #define IPV4_ADDR_STR "0123456789."
556 #define IPV4_PREFIX_STR "0123456789./"
558 static enum match_type
559 match_ipv4 (const char *str
)
562 int dots
= 0, nums
= 0;
570 memset (buf
, 0, sizeof (buf
));
579 if (*(str
+ 1) == '.')
582 if (*(str
+ 1) == '\0')
588 if (!isdigit ((int) *str
))
597 strncpy (buf
, sp
, str
- sp
);
598 if (atoi (buf
) > 255)
615 static enum match_type
616 match_ipv4_prefix (const char *str
)
627 memset (buf
, 0, sizeof (buf
));
629 while (*str
!= '\0' && *str
!= '/')
636 if (*(str
+ 1) == '.' || *(str
+ 1) == '/')
639 if (*(str
+ 1) == '\0')
646 if (!isdigit ((int) *str
))
655 strncpy (buf
, sp
, str
- sp
);
656 if (atoi (buf
) > 255)
663 if (*(str
+ 1) == '\0')
669 else if (*str
== '\0')
682 if (!isdigit ((int) *str
))
695 #define IPV6_ADDR_STR "0123456789abcdefABCDEF:."
696 #define IPV6_PREFIX_STR "0123456789abcdefABCDEF:./"
698 static enum match_type
699 match_ipv6 (const char *str
)
701 struct sockaddr_in6 sin6_dummy
;
707 if (strspn (str
, IPV6_ADDR_STR
) != strlen (str
))
710 ret
= inet_pton(AF_INET6
, str
, &sin6_dummy
.sin6_addr
);
718 static enum match_type
719 match_ipv6_prefix (const char *str
)
721 struct sockaddr_in6 sin6_dummy
;
722 const char *delim
= "/\0";
723 char *tofree
, *dupe
, *prefix
, *mask
, *endptr
;
729 if (strspn (str
, IPV6_PREFIX_STR
) != strlen (str
))
732 /* tokenize to prefix + mask */
733 tofree
= dupe
= XSTRDUP (MTYPE_TMP
, str
);
734 prefix
= strsep (&dupe
, delim
);
737 /* validate prefix */
738 if (inet_pton (AF_INET6
, prefix
, &sin6_dummy
.sin6_addr
) != 1)
740 XFREE (MTYPE_TMP
, tofree
);
747 XFREE (MTYPE_TMP
, tofree
);
751 nmask
= strtoimax (mask
, &endptr
, 10);
752 if (*endptr
!= '\0' || nmask
< 0 || nmask
> 128)
754 XFREE (MTYPE_TMP
, tofree
);
758 XFREE (MTYPE_TMP
, tofree
);
763 static enum match_type
764 match_range (struct cmd_token_t
*token
, const char *str
)
766 assert (token
->type
== RANGE_TKN
);
774 val
= strtoll (str
, &endptr
, 10);
778 if (val
< token
->min
|| val
> token
->max
)
784 static enum match_type
785 match_word (struct cmd_token_t
*token
, const char *word
)
787 assert (token
->type
== WORD_TKN
);
789 // if the passed token is null or 0 length, partly match
790 if (!word
|| !strlen(word
))
793 // if the passed token is strictly a prefix of the full word, partly match
794 if (strlen (word
) < strlen (token
->text
))
795 return !strncmp (token
->text
, word
, strlen (word
)) ?
799 // if they are the same length and exactly equal, exact match
800 else if (strlen (word
) == strlen (token
->text
))
801 return !strncmp (token
->text
, word
, strlen (word
)) ? exact_match
: no_match
;
806 static enum match_type
807 match_number (struct cmd_token_t
*token
, const char *word
)
809 assert (token
->type
== NUMBER_TKN
);
811 if (!strcmp ("\0", word
)) return no_match
;
813 long long num
= strtoll (word
, &endptr
, 10);
814 if (endptr
!= '\0') return no_match
;
815 return num
== token
->value
? exact_match
: no_match
;
818 #define VARIABLE_ALPHABET \
819 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890:"
821 static enum match_type
822 match_variable (struct cmd_token_t
*token
, const char *word
)
824 assert (token
->type
== VARIABLE_TKN
);
826 return strlen (word
) == strspn(word
, VARIABLE_ALPHABET
) ?
827 exact_match
: no_match
;