]>
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"
30 DEFINE_MTYPE_STATIC(LIB
, CMD_TOKENS
, "Command Tokens")
31 DEFINE_MTYPE_STATIC(LIB
, CMD_MATCHSTACK
, "Command Match Stack")
41 #define trace_matcher(...) \
42 do { if (TM) fprintf (stderr, __VA_ARGS__); } while (0);
44 /* matcher helper prototypes */
46 add_nexthops (struct list
*, struct graph_node
*,
47 struct graph_node
**, size_t);
50 command_match_r (struct graph_node
*, vector
, unsigned int,
51 struct graph_node
**);
54 score_precedence (enum cmd_token_type
);
56 static enum match_type
57 min_match_level (enum cmd_token_type
);
60 del_arglist (struct list
*);
62 static struct cmd_token
*
63 disambiguate_tokens (struct cmd_token
*, struct cmd_token
*, char *);
66 disambiguate (struct list
*, struct list
*, vector
, unsigned int);
69 compare_completions (const void *, const void *);
71 /* token matcher prototypes */
72 static enum match_type
73 match_token (struct cmd_token
*, char *);
75 static enum match_type
76 match_ipv4 (const char *);
78 static enum match_type
79 match_ipv4_prefix (const char *);
81 static enum match_type
82 match_ipv6 (const char *);
84 static enum match_type
85 match_ipv6_prefix (const char *);
87 static enum match_type
88 match_range (struct cmd_token
*, const char *);
90 static enum match_type
91 match_word (struct cmd_token
*, const char *);
93 static enum match_type
94 match_variable (struct cmd_token
*, const char *);
96 /* matching functions */
97 static enum matcher_rv matcher_rv
;
100 command_match (struct graph
*cmdgraph
,
103 const struct cmd_element
**el
)
105 struct graph_node
*stack
[MAXDEPTH
];
106 matcher_rv
= MATCHER_NO_MATCH
;
108 // prepend a dummy token to match that pesky start node
109 vector vvline
= vector_init (vline
->alloced
+ 1);
110 vector_set_index (vvline
, 0, (void *) XSTRDUP (MTYPE_TMP
, "dummy"));
111 memcpy (vvline
->index
+ 1, vline
->index
, sizeof (void *) * vline
->alloced
);
112 vvline
->active
= vline
->active
+ 1;
114 struct graph_node
*start
= vector_slot (cmdgraph
->nodes
, 0);
115 if ((*argv
= command_match_r (start
, vvline
, 0, stack
))) // successful match
117 struct listnode
*head
= listhead (*argv
);
118 struct listnode
*tail
= listtail (*argv
);
120 // delete dummy start node
121 del_cmd_token ((struct cmd_token
*) head
->data
);
122 list_delete_node (*argv
, head
);
124 // get cmd_element out of list tail
125 *el
= listgetdata (tail
);
126 list_delete_node (*argv
, tail
);
128 // now argv is an ordered list of cmd_token matching the user
129 // input, with each cmd_token->arg holding the corresponding input
134 trace_matcher ("No match\n");
137 trace_matcher ("Matched command\n->string %s\n->desc %s\n", (*el
)->string
, (*el
)->doc
);
140 // free the leader token we alloc'd
141 XFREE (MTYPE_TMP
, vector_slot (vvline
, 0));
143 vector_free (vvline
);
149 * Builds an argument list given a DFA and a matching input line.
151 * First the function determines if the node it is passed matches the first
152 * token of input. If it does not, it returns NULL (MATCHER_NO_MATCH). If it
153 * does match, then it saves the input token as the head of an argument list.
155 * The next step is to see if there is further input in the input line. If
156 * there is not, the current node's children are searched to see if any of them
157 * are leaves (type END_TKN). If this is the case, then the bottom of the
158 * recursion stack has been reached, the leaf is pushed onto the argument list,
159 * the current node is pushed, and the resulting argument list is
160 * returned (MATCHER_OK). If it is not the case, NULL is returned, indicating
161 * that there is no match for the input along this path (MATCHER_INCOMPLETE).
163 * If there is further input, then the function recurses on each of the current
164 * node's children, passing them the input line minus the token that was just
165 * matched. For each child, the return value of the recursive call is
166 * inspected. If it is null, then there is no match for the input along the
167 * subgraph headed by that child. If it is not null, then there is at least one
168 * input match in that subgraph (more on this in a moment).
170 * If a recursive call on a child returns a non-null value, then it has matched
171 * the input given it on the subgraph that starts with that child. However, due
172 * to the flexibility of the grammar, it is sometimes the case that two or more
173 * child graphs match the same input (two or more of the recursive calls have
174 * non-NULL return values). This is not a valid state, since only one true
175 * match is possible. In order to resolve this conflict, the function keeps a
176 * reference to the child node that most specifically matches the input. This
177 * is done by assigning each node type a precedence. If a child is found to
178 * match the remaining input, then the precedence values of the current
179 * best-matching child and this new match are compared. The node with higher
180 * precedence is kept, and the other match is discarded. Due to the recursive
181 * nature of this function, it is only necessary to compare the precedence of
182 * immediate children, since all subsequent children will already have been
183 * disambiguated in this way.
185 * In the event that two children are found to match with the same precedence,
186 * then the input is ambiguous for the passed cmd_element and NULL is returned.
188 * @param[in] start the start node.
189 * @param[in] vline the vectorized input line.
190 * @param[in] n the index of the first input token.
191 * @return A linked list of n elements. The first n-1 elements are pointers to
192 * struct cmd_token and represent the sequence of tokens matched by the input.
193 * The ->arg field of each token points to a copy of the input matched on it.
194 * The final nth element is a pointer to struct cmd_element, which is the
195 * command that was matched.
197 * If no match was found, the return value is NULL.
200 command_match_r (struct graph_node
*start
, vector vline
, unsigned int n
,
201 struct graph_node
**stack
)
203 assert (n
< vector_active (vline
));
205 // get the minimum match level that can count as a full match
206 struct cmd_token
*token
= start
->data
;
207 enum match_type minmatch
= min_match_level (token
->type
);
209 /* check history/stack of tokens
210 * this disallows matching the same one more than once if there is a
211 * circle in the graph (used for keyword arguments) */
214 if (!token
->allowrepeat
)
215 for (size_t s
= 0; s
< n
; s
++)
216 if (stack
[s
] == start
)
219 // get the current operating input token
220 char *input_token
= vector_slot (vline
, n
);
223 fprintf (stdout
, "\"%-20s\" matches \"%-30s\" ? ", input_token
, token
->text
);
224 enum match_type mt
= match_token (token
, input_token
);
225 fprintf (stdout
, "min: %d - ", minmatch
);
229 fprintf (stdout
, "trivial_match ");
232 fprintf (stdout
, "no_match ");
235 fprintf (stdout
, "partly_match ");
238 fprintf (stdout
, "exact_match ");
241 if (mt
>= minmatch
) fprintf (stdout
, " MATCH");
242 fprintf (stdout
, "\n");
245 // if we don't match this node, die
246 if (match_token (token
, input_token
) < minmatch
)
251 // pointers for iterating linklist
253 struct graph_node
*gn
;
255 // get all possible nexthops
256 struct list
*next
= list_new();
257 add_nexthops (next
, start
, NULL
, 0);
259 // determine the best match
261 struct list
*currbest
= NULL
;
262 for (ALL_LIST_ELEMENTS_RO (next
,ln
,gn
))
264 // if we've matched all input we're looking for END_TKN
265 if (n
+1 == vector_active (vline
))
267 struct cmd_token
*tok
= gn
->data
;
268 if (tok
->type
== END_TKN
)
270 if (currbest
) // there is more than one END_TKN in the follow set
275 currbest
= list_new();
276 // node should have one child node with the element
277 struct graph_node
*leaf
= vector_slot (gn
->to
, 0);
278 // last node in the list will hold the cmd_element;
279 // this is important because list_delete() expects
280 // that all nodes have the same data type, so when
281 // deleting this list the last node must be
283 struct cmd_element
*el
= leaf
->data
;
284 listnode_add (currbest
, el
);
285 currbest
->del
= (void (*)(void *)) &del_cmd_token
;
286 // do not break immediately; continue walking through the follow set
287 // to ensure that there is exactly one END_TKN
292 // else recurse on candidate child node
293 struct list
*result
= command_match_r (gn
, vline
, n
+1, stack
);
295 // save the best match
296 if (result
&& currbest
)
298 // pick the best of two matches
299 struct list
*newbest
= disambiguate (currbest
, result
, vline
, n
+1);
300 // set ambiguity flag
301 ambiguous
= !newbest
|| (ambiguous
&& newbest
== currbest
);
302 // delete the unnecessary result
303 struct list
*todelete
= ((newbest
&& newbest
== result
) ? currbest
: result
);
304 del_arglist (todelete
);
306 currbest
= newbest
? newbest
: currbest
;
316 del_arglist (currbest
);
318 matcher_rv
= MATCHER_AMBIGUOUS
;
322 // copy token, set arg and prepend to currbest
323 struct cmd_token
*token
= start
->data
;
324 struct cmd_token
*copy
= copy_cmd_token (token
);
325 copy
->arg
= XSTRDUP (MTYPE_CMD_TOKENS
, input_token
);
326 listnode_add_before (currbest
, currbest
->head
, copy
);
327 matcher_rv
= MATCHER_OK
;
330 else if (n
+1 == vector_active (vline
) && matcher_rv
== MATCHER_NO_MATCH
)
331 matcher_rv
= MATCHER_INCOMPLETE
;
340 stack_del (void *val
)
342 XFREE (MTYPE_CMD_MATCHSTACK
, val
);
346 command_complete (struct graph
*graph
,
348 struct list
**completions
)
350 // pointer to next input token to match
353 struct list
*current
= list_new(), // current nodes to match input token against
354 *next
= list_new(); // possible next hops after current input token
355 current
->del
= next
->del
= stack_del
;
357 // pointers used for iterating lists
358 struct graph_node
**gstack
, **newstack
;
359 struct listnode
*node
;
361 // add all children of start node to list
362 struct graph_node
*start
= vector_slot (graph
->nodes
, 0);
363 add_nexthops (next
, start
, &start
, 0);
366 for (idx
= 0; idx
< vector_active (vline
) && next
->count
> 0; idx
++)
368 list_delete (current
);
371 next
->del
= stack_del
;
373 input_token
= vector_slot (vline
, idx
);
375 int exact_match_exists
= 0;
376 for (ALL_LIST_ELEMENTS_RO (current
,node
,gstack
))
377 if (!exact_match_exists
)
378 exact_match_exists
= (match_token (gstack
[0]->data
, input_token
) == exact_match
);
382 for (ALL_LIST_ELEMENTS_RO (current
,node
,gstack
))
384 struct cmd_token
*token
= gstack
[0]->data
;
386 if (token
->attr
== CMD_ATTR_HIDDEN
|| token
->attr
== CMD_ATTR_DEPRECATED
)
389 enum match_type minmatch
= min_match_level (token
->type
);
390 trace_matcher ("\"%s\" matches \"%s\" (%d) ? ",
391 input_token
, token
->text
, token
->type
);
393 unsigned int last_token
= (vector_active (vline
) - 1 == idx
);
394 enum match_type matchtype
= match_token (token
, input_token
);
397 // occurs when last token is whitespace
399 trace_matcher ("trivial_match\n");
401 newstack
= XMALLOC (MTYPE_CMD_MATCHSTACK
,
402 sizeof(struct graph_node
*));
403 /* we're not recursing here, just the first element is OK */
404 newstack
[0] = gstack
[0];
405 listnode_add (next
, newstack
);
408 trace_matcher ("trivial_match\n");
409 if (exact_match_exists
&& !last_token
)
412 trace_matcher ("exact_match\n");
415 newstack
= XMALLOC (MTYPE_CMD_MATCHSTACK
,
416 sizeof(struct graph_node
*));
417 /* same as above, not recursing on this */
418 newstack
[0] = gstack
[0];
419 listnode_add (next
, newstack
);
421 else if (matchtype
>= minmatch
)
422 add_nexthops (next
, gstack
[0], gstack
, idx
+ 1);
425 trace_matcher ("no_match\n");
432 * -----------------------------------------------------------------
433 * token = last input token processed
434 * idx = index in `command` of last token processed
435 * current = set of all transitions from the previous input token
436 * next = set of all nodes reachable from all nodes in `matched`
440 idx
== vector_active(vline
) && next
->count
?
445 if (!MATCHER_ERROR(matcher_rv
))
447 // extract cmd_token into list
448 *completions
= list_new ();
449 for (ALL_LIST_ELEMENTS_RO (next
,node
,gstack
)) {
450 listnode_add (*completions
, gstack
[0]->data
);
454 list_delete (current
);
461 * Adds all children that are reachable by one parser hop to the given list.
462 * NUL_TKN, SELECTOR_TKN, and OPTION_TKN nodes are treated as transparent.
464 * @param[in] list to add the nexthops to
465 * @param[in] node to start calculating nexthops from
466 * @param[in] stack listing previously visited nodes, if non-NULL.
467 * @param[in] stackpos how many valid entries are in stack
468 * @return the number of children added to the list
470 * NB: non-null "stack" means that new stacks will be added to "list" as
471 * output, instead of direct node pointers!
474 add_nexthops (struct list
*list
, struct graph_node
*node
,
475 struct graph_node
**stack
, size_t stackpos
)
478 struct graph_node
*child
;
479 struct graph_node
**nextstack
;
480 for (unsigned int i
= 0; i
< vector_active (node
->to
); i
++)
482 child
= vector_slot (node
->to
, i
);
484 struct cmd_token
*token
= child
->data
;
485 if (!token
->allowrepeat
)
487 for (j
= 0; j
< stackpos
; j
++)
488 if (child
== stack
[j
])
498 added
+= add_nexthops (list
, child
, stack
, stackpos
);
503 nextstack
= XMALLOC (MTYPE_CMD_MATCHSTACK
,
504 (stackpos
+ 1) * sizeof(struct graph_node
*));
505 nextstack
[0] = child
;
506 memcpy(nextstack
+ 1, stack
, stackpos
* sizeof(struct graph_node
*));
508 listnode_add (list
, nextstack
);
511 listnode_add (list
, child
);
520 * Determines the node types for which a partial match may count as a full
521 * match. Enables command abbrevations.
523 * @param[in] type node type
524 * @return minimum match level needed to for a token to fully match
526 static enum match_type
527 min_match_level (enum cmd_token_type type
)
531 // anything matches a start node, for the sake of recursion
534 // allowing words to partly match enables command abbreviation
543 * Assigns precedence scores to node types.
545 * @param[in] type node type to score
546 * @return precedence score
549 score_precedence (enum cmd_token_type type
)
553 // some of these are mutually exclusive, so they share
554 // the same precedence value
556 case IPV4_PREFIX_TKN
:
558 case IPV6_PREFIX_TKN
:
571 * Picks the better of two possible matches for a token.
573 * @param[in] first candidate node matching token
574 * @param[in] second candidate node matching token
575 * @param[in] token the token being matched
576 * @return the best-matching node, or NULL if the two are entirely ambiguous
578 static struct cmd_token
*
579 disambiguate_tokens (struct cmd_token
*first
,
580 struct cmd_token
*second
,
583 // if the types are different, simply go off of type precedence
584 if (first
->type
!= second
->type
)
586 int firstprec
= score_precedence (first
->type
);
587 int secndprec
= score_precedence (second
->type
);
588 if (firstprec
!= secndprec
)
589 return firstprec
< secndprec
? first
: second
;
594 // if they're the same, return the more exact match
595 enum match_type fmtype
= match_token (first
, input_token
);
596 enum match_type smtype
= match_token (second
, input_token
);
597 if (fmtype
!= smtype
)
598 return fmtype
> smtype
? first
: second
;
604 * Picks the better of two possible matches for an input line.
606 * @param[in] first candidate list of cmd_token matching vline
607 * @param[in] second candidate list of cmd_token matching vline
608 * @param[in] vline the input line being matched
609 * @param[in] n index into vline to start comparing at
610 * @return the best-matching list, or NULL if the two are entirely ambiguous
613 disambiguate (struct list
*first
,
618 // doesn't make sense for these to be inequal length
619 assert (first
->count
== second
->count
);
620 assert (first
->count
== vector_active (vline
) - n
+1);
622 struct listnode
*fnode
= listhead (first
),
623 *snode
= listhead (second
);
624 struct cmd_token
*ftok
= listgetdata (fnode
),
625 *stok
= listgetdata (snode
),
628 // compare each token, if one matches better use that one
629 for (unsigned int i
= n
; i
< vector_active (vline
); i
++)
631 char *token
= vector_slot(vline
, i
);
632 if ((best
= disambiguate_tokens (ftok
, stok
, token
)))
633 return best
== ftok
? first
: second
;
634 fnode
= listnextnode (fnode
);
635 snode
= listnextnode (snode
);
636 ftok
= listgetdata (fnode
);
637 stok
= listgetdata (snode
);
644 * Deletion function for arglist.
646 * Since list->del for arglists expects all listnode->data to hold cmd_token,
647 * but arglists have cmd_element as the data for the tail, this function
648 * manually deletes the tail before deleting the rest of the list as usual.
650 * The cmd_element at the end is *not* a copy. It is the one and only.
652 * @param list the arglist to delete
655 del_arglist (struct list
*list
)
657 // manually delete last node
658 struct listnode
*tail
= listtail (list
);
660 list_delete_node (list
, tail
);
662 // delete the rest of the list as usual
666 /*---------- token level matching functions ----------*/
668 static enum match_type
669 match_token (struct cmd_token
*token
, char *input_token
)
671 // nothing trivially matches everything
673 return trivial_match
;
675 switch (token
->type
) {
677 return match_word (token
, input_token
);
679 return match_ipv4 (input_token
);
680 case IPV4_PREFIX_TKN
:
681 return match_ipv4_prefix (input_token
);
683 return match_ipv6 (input_token
);
684 case IPV6_PREFIX_TKN
:
685 return match_ipv6_prefix (input_token
);
687 return match_range (token
, input_token
);
689 return match_variable (token
, input_token
);
696 #define IPV4_ADDR_STR "0123456789."
697 #define IPV4_PREFIX_STR "0123456789./"
699 static enum match_type
700 match_ipv4 (const char *str
)
703 int dots
= 0, nums
= 0;
708 memset (buf
, 0, sizeof (buf
));
717 if (*(str
+ 1) == '.')
720 if (*(str
+ 1) == '\0')
726 if (!isdigit ((int) *str
))
735 strncpy (buf
, sp
, str
- sp
);
736 if (atoi (buf
) > 255)
753 static enum match_type
754 match_ipv4_prefix (const char *str
)
762 memset (buf
, 0, sizeof (buf
));
764 while (*str
!= '\0' && *str
!= '/')
771 if (*(str
+ 1) == '.' || *(str
+ 1) == '/')
774 if (*(str
+ 1) == '\0')
781 if (!isdigit ((int) *str
))
790 strncpy (buf
, sp
, str
- sp
);
791 if (atoi (buf
) > 255)
798 if (*(str
+ 1) == '\0')
804 else if (*str
== '\0')
817 if (!isdigit ((int) *str
))
830 #define IPV6_ADDR_STR "0123456789abcdefABCDEF:."
831 #define IPV6_PREFIX_STR "0123456789abcdefABCDEF:./"
832 #define STATE_START 1
833 #define STATE_COLON 2
834 #define STATE_DOUBLE 3
837 #define STATE_SLASH 6
840 static enum match_type
841 match_ipv6 (const char *str
)
843 struct sockaddr_in6 sin6_dummy
;
846 if (strspn (str
, IPV6_ADDR_STR
) != strlen (str
))
849 ret
= inet_pton(AF_INET6
, str
, &sin6_dummy
.sin6_addr
);
857 static enum match_type
858 match_ipv6_prefix (const char *str
)
860 int state
= STATE_START
;
861 int colons
= 0, nums
= 0, double_colon
= 0;
863 const char *sp
= NULL
;
869 if (strspn (str
, IPV6_PREFIX_STR
) != strlen (str
))
872 while (*str
!= '\0' && state
!= STATE_MASK
)
879 if (*(str
+ 1) != ':' && *(str
+ 1) != '\0')
893 if (*(str
+ 1) == '/')
895 else if (*(str
+ 1) == ':')
896 state
= STATE_DOUBLE
;
907 if (*(str
+ 1) == ':')
911 if (*(str
+ 1) != '\0' && *(str
+ 1) != '/')
915 if (*(str
+ 1) == '/')
925 if (*(str
+ 1) == ':' || *(str
+ 1) == '.'
926 || *(str
+ 1) == '\0' || *(str
+ 1) == '/')
931 for (; sp
<= str
; sp
++)
937 if (*(str
+ 1) == ':')
939 else if (*(str
+ 1) == '.')
941 if (colons
|| double_colon
)
946 else if (*(str
+ 1) == '/')
954 if (*(str
+ 1) == '\0')
972 if (state
< STATE_MASK
)
975 mask
= strtol (str
, &endptr
, 10);
979 if (mask
< 0 || mask
> 128)
985 static enum match_type
986 match_range (struct cmd_token
*token
, const char *str
)
988 assert (token
->type
== RANGE_TKN
);
993 val
= strtoll (str
, &endptr
, 10);
997 if (val
< token
->min
|| val
> token
->max
)
1003 static enum match_type
1004 match_word (struct cmd_token
*token
, const char *word
)
1006 assert (token
->type
== WORD_TKN
);
1008 // if the passed token is 0 length, partly match
1010 return partly_match
;
1012 // if the passed token is strictly a prefix of the full word, partly match
1013 if (strlen (word
) < strlen (token
->text
))
1014 return !strncmp (token
->text
, word
, strlen (word
)) ?
1018 // if they are the same length and exactly equal, exact match
1019 else if (strlen (word
) == strlen (token
->text
))
1020 return !strncmp (token
->text
, word
, strlen (word
)) ? exact_match
: no_match
;
1025 static enum match_type
1026 match_variable (struct cmd_token
*token
, const char *word
)
1028 assert (token
->type
== VARIABLE_TKN
);