]>
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 along
20 * with this program; see the file COPYING; if not, write to the Free Software
21 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
26 #include "command_match.h"
29 DEFINE_MTYPE_STATIC(LIB
, CMD_MATCHSTACK
, "Command Match Stack")
39 #define trace_matcher(...) \
42 fprintf(stderr, __VA_ARGS__); \
45 /* matcher helper prototypes */
46 static int add_nexthops(struct list
*, struct graph_node
*,
47 struct graph_node
**, size_t);
49 static struct list
*command_match_r(struct graph_node
*, vector
, unsigned int,
50 struct graph_node
**);
52 static int score_precedence(enum cmd_token_type
);
54 static enum match_type
min_match_level(enum cmd_token_type
);
56 static void del_arglist(struct list
*);
58 static struct cmd_token
*disambiguate_tokens(struct cmd_token
*,
59 struct cmd_token
*, char *);
61 static struct list
*disambiguate(struct list
*, struct list
*, vector
,
64 int compare_completions(const void *, const void *);
66 /* token matcher prototypes */
67 static enum match_type
match_token(struct cmd_token
*, char *);
69 static enum match_type
match_ipv4(const char *);
71 static enum match_type
match_ipv4_prefix(const char *);
73 static enum match_type
match_ipv6_prefix(const char *, bool);
75 static enum match_type
match_range(struct cmd_token
*, const char *);
77 static enum match_type
match_word(struct cmd_token
*, const char *);
79 static enum match_type
match_variable(struct cmd_token
*, const char *);
81 static enum match_type
match_mac(const char *, bool);
83 /* matching functions */
84 static enum matcher_rv matcher_rv
;
86 enum matcher_rv
command_match(struct graph
*cmdgraph
, vector vline
,
87 struct list
**argv
, const struct cmd_element
**el
)
89 struct graph_node
*stack
[MAXDEPTH
];
90 matcher_rv
= MATCHER_NO_MATCH
;
92 // prepend a dummy token to match that pesky start node
93 vector vvline
= vector_init(vline
->alloced
+ 1);
94 vector_set_index(vvline
, 0, (void *)XSTRDUP(MTYPE_TMP
, "dummy"));
95 memcpy(vvline
->index
+ 1, vline
->index
,
96 sizeof(void *) * vline
->alloced
);
97 vvline
->active
= vline
->active
+ 1;
99 struct graph_node
*start
= vector_slot(cmdgraph
->nodes
, 0);
100 if ((*argv
= command_match_r(start
, vvline
, 0,
101 stack
))) // successful match
103 struct listnode
*head
= listhead(*argv
);
104 struct listnode
*tail
= listtail(*argv
);
106 // delete dummy start node
107 cmd_token_del((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
121 trace_matcher("No match\n");
123 trace_matcher("Matched command\n->string %s\n->desc %s\n",
124 (*el
)->string
, (*el
)->doc
);
127 // free the leader token we alloc'd
128 XFREE(MTYPE_TMP
, vector_slot(vvline
, 0));
136 * Builds an argument list given a DFA and a matching input line.
138 * First the function determines if the node it is passed matches the first
139 * token of input. If it does not, it returns NULL (MATCHER_NO_MATCH). If it
140 * does match, then it saves the input token as the head of an argument list.
142 * The next step is to see if there is further input in the input line. If
143 * there is not, the current node's children are searched to see if any of them
144 * are leaves (type END_TKN). If this is the case, then the bottom of the
145 * recursion stack has been reached, the leaf is pushed onto the argument list,
146 * the current node is pushed, and the resulting argument list is
147 * returned (MATCHER_OK). If it is not the case, NULL is returned, indicating
148 * that there is no match for the input along this path (MATCHER_INCOMPLETE).
150 * If there is further input, then the function recurses on each of the current
151 * node's children, passing them the input line minus the token that was just
152 * matched. For each child, the return value of the recursive call is
153 * inspected. If it is null, then there is no match for the input along the
154 * subgraph headed by that child. If it is not null, then there is at least one
155 * input match in that subgraph (more on this in a moment).
157 * If a recursive call on a child returns a non-null value, then it has matched
158 * the input given it on the subgraph that starts with that child. However, due
159 * to the flexibility of the grammar, it is sometimes the case that two or more
160 * child graphs match the same input (two or more of the recursive calls have
161 * non-NULL return values). This is not a valid state, since only one true
162 * match is possible. In order to resolve this conflict, the function keeps a
163 * reference to the child node that most specifically matches the input. This
164 * is done by assigning each node type a precedence. If a child is found to
165 * match the remaining input, then the precedence values of the current
166 * best-matching child and this new match are compared. The node with higher
167 * precedence is kept, and the other match is discarded. Due to the recursive
168 * nature of this function, it is only necessary to compare the precedence of
169 * immediate children, since all subsequent children will already have been
170 * disambiguated in this way.
172 * In the event that two children are found to match with the same precedence,
173 * then the input is ambiguous for the passed cmd_element and NULL is returned.
175 * @param[in] start the start node.
176 * @param[in] vline the vectorized input line.
177 * @param[in] n the index of the first input token.
178 * @return A linked list of n elements. The first n-1 elements are pointers to
179 * struct cmd_token and represent the sequence of tokens matched by the input.
180 * The ->arg field of each token points to a copy of the input matched on it.
181 * The final nth element is a pointer to struct cmd_element, which is the
182 * command that was matched.
184 * If no match was found, the return value is NULL.
186 static struct list
*command_match_r(struct graph_node
*start
, vector vline
,
187 unsigned int n
, struct graph_node
**stack
)
189 assert(n
< vector_active(vline
));
191 // get the minimum match level that can count as a full match
192 struct cmd_token
*token
= start
->data
;
193 enum match_type minmatch
= min_match_level(token
->type
);
195 /* check history/stack of tokens
196 * this disallows matching the same one more than once if there is a
197 * circle in the graph (used for keyword arguments) */
200 if (!token
->allowrepeat
)
201 for (size_t s
= 0; s
< n
; s
++)
202 if (stack
[s
] == start
)
205 // get the current operating input token
206 char *input_token
= vector_slot(vline
, n
);
209 fprintf(stdout
, "\"%-20s\" matches \"%-30s\" ? ", input_token
,
211 enum match_type mt
= match_token(token
, input_token
);
212 fprintf(stdout
, "min: %d - ", minmatch
);
215 fprintf(stdout
, "trivial_match ");
218 fprintf(stdout
, "no_match ");
221 fprintf(stdout
, "partly_match ");
224 fprintf(stdout
, "exact_match ");
228 fprintf(stdout
, " MATCH");
229 fprintf(stdout
, "\n");
232 // if we don't match this node, die
233 if (match_token(token
, input_token
) < minmatch
)
238 // pointers for iterating linklist
240 struct graph_node
*gn
;
242 // get all possible nexthops
243 struct list
*next
= list_new();
244 add_nexthops(next
, start
, NULL
, 0);
246 // determine the best match
248 struct list
*currbest
= NULL
;
249 for (ALL_LIST_ELEMENTS_RO(next
, ln
, gn
)) {
250 // if we've matched all input we're looking for END_TKN
251 if (n
+ 1 == vector_active(vline
)) {
252 struct cmd_token
*tok
= gn
->data
;
253 if (tok
->type
== END_TKN
) {
254 if (currbest
) // there is more than one END_TKN
260 currbest
= list_new();
261 // node should have one child node with the
263 struct graph_node
*leaf
=
264 vector_slot(gn
->to
, 0);
265 // last node in the list will hold the
267 // this is important because list_delete()
269 // that all nodes have the same data type, so
271 // deleting this list the last node must be
273 struct cmd_element
*el
= leaf
->data
;
274 listnode_add(currbest
, el
);
276 (void (*)(void *)) & cmd_token_del
;
277 // do not break immediately; continue walking
278 // through the follow set
279 // to ensure that there is exactly one END_TKN
284 // else recurse on candidate child node
285 struct list
*result
= command_match_r(gn
, vline
, n
+ 1, stack
);
287 // save the best match
288 if (result
&& currbest
) {
289 // pick the best of two matches
290 struct list
*newbest
=
291 disambiguate(currbest
, result
, vline
, n
+ 1);
292 // set ambiguity flag
294 !newbest
|| (ambiguous
&& newbest
== currbest
);
295 // delete the unnecessary result
296 struct list
*todelete
=
297 ((newbest
&& newbest
== result
) ? currbest
299 del_arglist(todelete
);
301 currbest
= newbest
? newbest
: currbest
;
308 del_arglist(currbest
);
310 matcher_rv
= MATCHER_AMBIGUOUS
;
312 // copy token, set arg and prepend to currbest
313 struct cmd_token
*token
= start
->data
;
314 struct cmd_token
*copy
= cmd_token_dup(token
);
315 copy
->arg
= XSTRDUP(MTYPE_CMD_ARG
, input_token
);
316 listnode_add_before(currbest
, currbest
->head
, copy
);
317 matcher_rv
= MATCHER_OK
;
319 } else if (n
+ 1 == vector_active(vline
)
320 && matcher_rv
== MATCHER_NO_MATCH
)
321 matcher_rv
= MATCHER_INCOMPLETE
;
329 static void stack_del(void *val
)
331 XFREE(MTYPE_CMD_MATCHSTACK
, val
);
334 enum matcher_rv
command_complete(struct graph
*graph
, vector vline
,
335 struct list
**completions
)
337 // pointer to next input token to match
342 list_new(), // current nodes to match input token against
343 *next
= list_new(); // possible next hops after current input
345 current
->del
= next
->del
= stack_del
;
347 // pointers used for iterating lists
348 struct graph_node
**gstack
, **newstack
;
349 struct listnode
*node
;
351 // add all children of start node to list
352 struct graph_node
*start
= vector_slot(graph
->nodes
, 0);
353 add_nexthops(next
, start
, &start
, 0);
356 for (idx
= 0; idx
< vector_active(vline
) && next
->count
> 0; idx
++) {
357 list_delete(current
);
360 next
->del
= stack_del
;
362 input_token
= vector_slot(vline
, idx
);
364 int exact_match_exists
= 0;
365 for (ALL_LIST_ELEMENTS_RO(current
, node
, gstack
))
366 if (!exact_match_exists
)
368 (match_token(gstack
[0]->data
,
374 for (ALL_LIST_ELEMENTS_RO(current
, node
, gstack
)) {
375 struct cmd_token
*token
= gstack
[0]->data
;
377 if (token
->attr
== CMD_ATTR_HIDDEN
378 || token
->attr
== CMD_ATTR_DEPRECATED
)
381 enum match_type minmatch
= min_match_level(token
->type
);
382 trace_matcher("\"%s\" matches \"%s\" (%d) ? ",
383 input_token
, token
->text
, token
->type
);
385 unsigned int last_token
=
386 (vector_active(vline
) - 1 == idx
);
387 enum match_type matchtype
=
388 match_token(token
, input_token
);
390 // occurs when last token is whitespace
392 trace_matcher("trivial_match\n");
394 newstack
= XMALLOC(MTYPE_CMD_MATCHSTACK
,
395 sizeof(struct graph_node
*));
396 /* we're not recursing here, just the first
398 newstack
[0] = gstack
[0];
399 listnode_add(next
, newstack
);
402 trace_matcher("trivial_match\n");
403 if (exact_match_exists
&& !last_token
)
407 trace_matcher("exact_match\n");
410 MTYPE_CMD_MATCHSTACK
,
411 sizeof(struct graph_node
*));
412 /* same as above, not recursing on this
414 newstack
[0] = gstack
[0];
415 listnode_add(next
, newstack
);
416 } else if (matchtype
>= minmatch
)
417 add_nexthops(next
, gstack
[0], gstack
,
421 trace_matcher("no_match\n");
428 * -----------------------------------------------------------------
429 * token = last input token processed
430 * idx = index in `command` of last token processed
431 * current = set of all transitions from the previous input token
432 * next = set of all nodes reachable from all nodes in `matched`
435 matcher_rv
= idx
== vector_active(vline
) && next
->count
440 if (!MATCHER_ERROR(matcher_rv
)) {
441 // extract cmd_token into list
442 *completions
= list_new();
443 for (ALL_LIST_ELEMENTS_RO(next
, node
, gstack
)) {
444 listnode_add(*completions
, gstack
[0]->data
);
448 list_delete(current
);
455 * Adds all children that are reachable by one parser hop to the given list.
456 * special tokens except END_TKN are treated as transparent.
458 * @param[in] list to add the nexthops to
459 * @param[in] node to start calculating nexthops from
460 * @param[in] stack listing previously visited nodes, if non-NULL.
461 * @param[in] stackpos how many valid entries are in stack
462 * @return the number of children added to the list
464 * NB: non-null "stack" means that new stacks will be added to "list" as
465 * output, instead of direct node pointers!
467 static int add_nexthops(struct list
*list
, struct graph_node
*node
,
468 struct graph_node
**stack
, size_t stackpos
)
471 struct graph_node
*child
;
472 struct graph_node
**nextstack
;
473 for (unsigned int i
= 0; i
< vector_active(node
->to
); i
++) {
474 child
= vector_slot(node
->to
, i
);
476 struct cmd_token
*token
= child
->data
;
477 if (!token
->allowrepeat
&& stack
) {
478 for (j
= 0; j
< stackpos
; j
++)
479 if (child
== stack
[j
])
484 if (token
->type
>= SPECIAL_TKN
&& token
->type
!= END_TKN
) {
485 added
+= add_nexthops(list
, child
, stack
, stackpos
);
489 MTYPE_CMD_MATCHSTACK
,
491 * sizeof(struct graph_node
*));
492 nextstack
[0] = child
;
493 memcpy(nextstack
+ 1, stack
,
494 stackpos
* sizeof(struct graph_node
*));
496 listnode_add(list
, nextstack
);
498 listnode_add(list
, child
);
507 * Determines the node types for which a partial match may count as a full
508 * match. Enables command abbrevations.
510 * @param[in] type node type
511 * @return minimum match level needed to for a token to fully match
513 static enum match_type
min_match_level(enum cmd_token_type type
)
516 // anything matches a start node, for the sake of recursion
519 // allowing words to partly match enables command abbreviation
528 * Assigns precedence scores to node types.
530 * @param[in] type node type to score
531 * @return precedence score
533 static int score_precedence(enum cmd_token_type type
)
536 // some of these are mutually exclusive, so they share
537 // the same precedence value
539 case IPV4_PREFIX_TKN
:
541 case IPV6_PREFIX_TKN
:
556 * Picks the better of two possible matches for a token.
558 * @param[in] first candidate node matching token
559 * @param[in] second candidate node matching token
560 * @param[in] token the token being matched
561 * @return the best-matching node, or NULL if the two are entirely ambiguous
563 static struct cmd_token
*disambiguate_tokens(struct cmd_token
*first
,
564 struct cmd_token
*second
,
567 // if the types are different, simply go off of type precedence
568 if (first
->type
!= second
->type
) {
569 int firstprec
= score_precedence(first
->type
);
570 int secndprec
= score_precedence(second
->type
);
571 if (firstprec
!= secndprec
)
572 return firstprec
< secndprec
? first
: second
;
577 // if they're the same, return the more exact match
578 enum match_type fmtype
= match_token(first
, input_token
);
579 enum match_type smtype
= match_token(second
, input_token
);
580 if (fmtype
!= smtype
)
581 return fmtype
> smtype
? first
: second
;
587 * Picks the better of two possible matches for an input line.
589 * @param[in] first candidate list of cmd_token matching vline
590 * @param[in] second candidate list of cmd_token matching vline
591 * @param[in] vline the input line being matched
592 * @param[in] n index into vline to start comparing at
593 * @return the best-matching list, or NULL if the two are entirely ambiguous
595 static struct list
*disambiguate(struct list
*first
, struct list
*second
,
596 vector vline
, unsigned int n
)
598 // doesn't make sense for these to be inequal length
599 assert(first
->count
== second
->count
);
600 assert(first
->count
== vector_active(vline
) - n
+ 1);
602 struct listnode
*fnode
= listhead(first
), *snode
= listhead(second
);
603 struct cmd_token
*ftok
= listgetdata(fnode
), *stok
= listgetdata(snode
),
606 // compare each token, if one matches better use that one
607 for (unsigned int i
= n
; i
< vector_active(vline
); i
++) {
608 char *token
= vector_slot(vline
, i
);
609 if ((best
= disambiguate_tokens(ftok
, stok
, token
)))
610 return best
== ftok
? first
: second
;
611 fnode
= listnextnode(fnode
);
612 snode
= listnextnode(snode
);
613 ftok
= listgetdata(fnode
);
614 stok
= listgetdata(snode
);
621 * Deletion function for arglist.
623 * Since list->del for arglists expects all listnode->data to hold cmd_token,
624 * but arglists have cmd_element as the data for the tail, this function
625 * manually deletes the tail before deleting the rest of the list as usual.
627 * The cmd_element at the end is *not* a copy. It is the one and only.
629 * @param list the arglist to delete
631 static void del_arglist(struct list
*list
)
633 // manually delete last node
634 struct listnode
*tail
= listtail(list
);
636 list_delete_node(list
, tail
);
638 // delete the rest of the list as usual
642 /*---------- token level matching functions ----------*/
644 static enum match_type
match_token(struct cmd_token
*token
, char *input_token
)
646 // nothing trivially matches everything
648 return trivial_match
;
650 switch (token
->type
) {
652 return match_word(token
, input_token
);
654 return match_ipv4(input_token
);
655 case IPV4_PREFIX_TKN
:
656 return match_ipv4_prefix(input_token
);
658 return match_ipv6_prefix(input_token
, false);
659 case IPV6_PREFIX_TKN
:
660 return match_ipv6_prefix(input_token
, true);
662 return match_range(token
, input_token
);
664 return match_variable(token
, input_token
);
666 return match_mac(input_token
, false);
668 return match_mac(input_token
, true);
675 #define IPV4_ADDR_STR "0123456789."
676 #define IPV4_PREFIX_STR "0123456789./"
678 static enum match_type
match_ipv4(const char *str
)
681 int dots
= 0, nums
= 0;
685 memset(buf
, 0, sizeof(buf
));
687 while (*str
!= '\0') {
692 if (*(str
+ 1) == '.')
695 if (*(str
+ 1) == '\0')
701 if (!isdigit((int)*str
))
710 strncpy(buf
, sp
, str
- sp
);
728 static enum match_type
match_ipv4_prefix(const char *str
)
735 memset(buf
, 0, sizeof(buf
));
737 while (*str
!= '\0' && *str
!= '/') {
742 if (*(str
+ 1) == '.' || *(str
+ 1) == '/')
745 if (*(str
+ 1) == '\0')
752 if (!isdigit((int)*str
))
761 strncpy(buf
, sp
, str
- sp
);
767 if (*(str
+ 1) == '\0')
772 } else if (*str
== '\0')
783 while (*str
!= '\0') {
784 if (!isdigit((int)*str
))
797 #define IPV6_ADDR_STR "0123456789abcdefABCDEF:."
798 #define IPV6_PREFIX_STR "0123456789abcdefABCDEF:./"
799 #define STATE_START 1
800 #define STATE_COLON 2
801 #define STATE_DOUBLE 3
804 #define STATE_SLASH 6
807 static enum match_type
match_ipv6_prefix(const char *str
, bool prefix
)
809 int state
= STATE_START
;
810 int colons
= 0, nums
= 0, double_colon
= 0;
812 const char *sp
= NULL
, *start
= str
;
818 if (strspn(str
, prefix
? IPV6_PREFIX_STR
: IPV6_ADDR_STR
)
822 while (*str
!= '\0' && state
!= STATE_MASK
) {
826 if (*(str
+ 1) != ':' && *(str
+ 1) != '\0')
838 if (*(str
+ 1) == '/')
840 else if (*(str
+ 1) == ':')
841 state
= STATE_DOUBLE
;
851 if (*(str
+ 1) == ':')
854 if (*(str
+ 1) != '\0' && *(str
+ 1) != '/')
858 if (*(str
+ 1) == '/')
868 if (*(str
+ 1) == ':' || *(str
+ 1) == '.'
869 || *(str
+ 1) == '\0' || *(str
+ 1) == '/') {
873 for (; sp
<= str
; sp
++)
879 if (*(str
+ 1) == ':')
881 else if (*(str
+ 1) == '.') {
882 if (colons
|| double_colon
)
886 } else if (*(str
+ 1) == '/')
894 if (*(str
+ 1) == '\0')
913 struct sockaddr_in6 sin6_dummy
;
914 int ret
= inet_pton(AF_INET6
, start
, &sin6_dummy
.sin6_addr
);
915 return ret
== 1 ? exact_match
: partly_match
;
918 if (state
< STATE_MASK
)
921 mask
= strtol(str
, &endptr
, 10);
925 if (mask
< 0 || mask
> 128)
931 static enum match_type
match_range(struct cmd_token
*token
, const char *str
)
933 assert(token
->type
== RANGE_TKN
);
938 val
= strtoll(str
, &endptr
, 10);
942 if (val
< token
->min
|| val
> token
->max
)
948 static enum match_type
match_word(struct cmd_token
*token
, const char *word
)
950 assert(token
->type
== WORD_TKN
);
952 // if the passed token is 0 length, partly match
956 // if the passed token is strictly a prefix of the full word, partly
958 if (strlen(word
) < strlen(token
->text
))
959 return !strncmp(token
->text
, word
, strlen(word
)) ? partly_match
962 // if they are the same length and exactly equal, exact match
963 else if (strlen(word
) == strlen(token
->text
))
964 return !strncmp(token
->text
, word
, strlen(word
)) ? exact_match
970 static enum match_type
match_variable(struct cmd_token
*token
, const char *word
)
972 assert(token
->type
== VARIABLE_TKN
);
976 #define MAC_CHARS "ABCDEFabcdef0123456789:"
978 static enum match_type
match_mac(const char *word
, bool prefix
)
980 /* 6 2-digit hex numbers separated by 5 colons */
981 size_t mac_explen
= 6 * 2 + 5;
982 /* '/' + 2-digit integer */
983 size_t mask_len
= 1 + 2;
986 unsigned int maskval
;
989 if (strlen(word
) > mac_explen
+ (prefix
? mask_len
: 0))
993 for (i
= 0; i
< mac_explen
; i
++) {
994 if (word
[i
] == '\0' || !strchr(MAC_CHARS
, word
[i
]))
996 if (((i
+ 1) % 3 == 0) != (word
[i
] == ':'))
1000 /* incomplete address */
1001 if (i
< mac_explen
&& word
[i
] == '\0')
1002 return partly_match
;
1003 else if (i
< mac_explen
)
1007 if (prefix
&& word
[i
] == '/') {
1008 if (word
[++i
] == '\0')
1009 return partly_match
;
1011 maskval
= strtoul(&word
[i
], &eptr
, 10);
1012 if (*eptr
!= '\0' || maskval
> 48)
1014 } else if (prefix
&& word
[i
] == '\0') {
1015 return partly_match
;
1016 } else if (prefix
) {