1 /*
2 * Input matching routines for CLI backend.
3 *
4 * --
5 * Copyright (C) 2016 Cumulus Networks, Inc.
6 *
7 * This file is part of GNU Zebra.
8 *
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
12 * later version.
13 *
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.
18 *
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
22 */
23
24 #include <zebra.h>
25
26 #include "command_match.h"
27 #include "memory.h"
28
29 DEFINE_MTYPE_STATIC(LIB, CMD_MATCHSTACK, "Command Match Stack")
30
31 #ifdef TRACE_MATCHER
32 #define TM 1
33 #else
34 #define TM 0
35 #endif
36
37 #define trace_matcher(...) \
38 do { \
39 if (TM) \
40 fprintf(stderr, __VA_ARGS__); \
41 } while (0);
42
43 /* matcher helper prototypes */
44 static int add_nexthops(struct list *, struct graph_node *,
45 struct graph_node **, size_t);
46
47 static enum matcher_rv command_match_r(struct graph_node *, vector,
48 unsigned int, struct graph_node **,
49 struct list **);
50
51 static int score_precedence(enum cmd_token_type);
52
53 static enum match_type min_match_level(enum cmd_token_type);
54
55 static void del_arglist(struct list *);
56
57 static struct cmd_token *disambiguate_tokens(struct cmd_token *,
58 struct cmd_token *, char *);
59
60 static struct list *disambiguate(struct list *, struct list *, vector,
61 unsigned int);
62
63 int compare_completions(const void *, const void *);
64
65 /* token matcher prototypes */
66 static enum match_type match_token(struct cmd_token *, char *);
67
68 static enum match_type match_ipv4(const char *);
69
70 static enum match_type match_ipv4_prefix(const char *);
71
72 static enum match_type match_ipv6_prefix(const char *, bool);
73
74 static enum match_type match_range(struct cmd_token *, const char *);
75
76 static enum match_type match_word(struct cmd_token *, const char *);
77
78 static enum match_type match_variable(struct cmd_token *, const char *);
79
80 static enum match_type match_mac(const char *, bool);
81
command_match(struct graph * cmdgraph,vector vline,struct list ** argv,const struct cmd_element ** el)82 enum matcher_rv command_match(struct graph *cmdgraph, vector vline,
83 struct list **argv, const struct cmd_element **el)
84 {
85 struct graph_node *stack[CMD_ARGC_MAX];
86 enum matcher_rv status;
87 *argv = NULL;
88
89 // prepend a dummy token to match that pesky start node
90 vector vvline = vector_init(vline->alloced + 1);
91 vector_set_index(vvline, 0, XSTRDUP(MTYPE_TMP, "dummy"));
92 memcpy(vvline->index + 1, vline->index,
93 sizeof(void *) * vline->alloced);
94 vvline->active = vline->active + 1;
95
96 struct graph_node *start = vector_slot(cmdgraph->nodes, 0);
97 status = command_match_r(start, vvline, 0, stack, argv);
98 if (status == MATCHER_OK) { // successful match
99 struct listnode *head = listhead(*argv);
100 struct listnode *tail = listtail(*argv);
101
102 assert(head);
103 assert(tail);
104
105 // delete dummy start node
106 cmd_token_del((struct cmd_token *)head->data);
107 list_delete_node(*argv, head);
108
109 // get cmd_element out of list tail
110 *el = listgetdata(tail);
111 list_delete_node(*argv, tail);
112
113 // now argv is an ordered list of cmd_token matching the user
114 // input, with each cmd_token->arg holding the corresponding
115 // input
116 assert(*el);
117 } else if (*argv) {
118 del_arglist(*argv);
119 *argv = NULL;
120 }
121
122 if (!*el) {
123 trace_matcher("No match\n");
124 } else {
125 trace_matcher("Matched command\n->string %s\n->desc %s\n",
126 (*el)->string, (*el)->doc);
127 }
128
129 // free the leader token we alloc'd
130 XFREE(MTYPE_TMP, vector_slot(vvline, 0));
131 // free vector
132 vector_free(vvline);
133
134 return status;
135 }
136
137 /**
138 * Builds an argument list given a DFA and a matching input line.
139 *
140 * First the function determines if the node it is passed matches the first
141 * token of input. If it does not, it returns NULL (MATCHER_NO_MATCH). If it
142 * does match, then it saves the input token as the head of an argument list.
143 *
144 * The next step is to see if there is further input in the input line. If
145 * there is not, the current node's children are searched to see if any of them
146 * are leaves (type END_TKN). If this is the case, then the bottom of the
147 * recursion stack has been reached, the leaf is pushed onto the argument list,
148 * the current node is pushed, and the resulting argument list is
149 * returned (MATCHER_OK). If it is not the case, NULL is returned, indicating
150 * that there is no match for the input along this path (MATCHER_INCOMPLETE).
151 *
152 * If there is further input, then the function recurses on each of the current
153 * node's children, passing them the input line minus the token that was just
154 * matched. For each child, the return value of the recursive call is
155 * inspected. If it is null, then there is no match for the input along the
156 * subgraph headed by that child. If it is not null, then there is at least one
157 * input match in that subgraph (more on this in a moment).
158 *
159 * If a recursive call on a child returns a non-null value, then it has matched
160 * the input given it on the subgraph that starts with that child. However, due
161 * to the flexibility of the grammar, it is sometimes the case that two or more
162 * child graphs match the same input (two or more of the recursive calls have
163 * non-NULL return values). This is not a valid state, since only one true
164 * match is possible. In order to resolve this conflict, the function keeps a
165 * reference to the child node that most specifically matches the input. This
166 * is done by assigning each node type a precedence. If a child is found to
167 * match the remaining input, then the precedence values of the current
168 * best-matching child and this new match are compared. The node with higher
169 * precedence is kept, and the other match is discarded. Due to the recursive
170 * nature of this function, it is only necessary to compare the precedence of
171 * immediate children, since all subsequent children will already have been
172 * disambiguated in this way.
173 *
174 * In the event that two children are found to match with the same precedence,
175 * then the input is ambiguous for the passed cmd_element and NULL is returned.
176 *
177 * @param[in] start the start node.
178 * @param[in] vline the vectorized input line.
179 * @param[in] n the index of the first input token.
180 * @return A linked list of n elements. The first n-1 elements are pointers to
181 * struct cmd_token and represent the sequence of tokens matched by the input.
182 * The ->arg field of each token points to a copy of the input matched on it.
183 * The final nth element is a pointer to struct cmd_element, which is the
184 * command that was matched.
185 *
186 * If no match was found, the return value is NULL.
187 */
command_match_r(struct graph_node * start,vector vline,unsigned int n,struct graph_node ** stack,struct list ** currbest)188 static enum matcher_rv command_match_r(struct graph_node *start, vector vline,
189 unsigned int n,
190 struct graph_node **stack,
191 struct list **currbest)
192 {
193 assert(n < vector_active(vline));
194
195 enum matcher_rv status = MATCHER_NO_MATCH;
196
197 // get the minimum match level that can count as a full match
198 struct cmd_token *copy, *token = start->data;
199 enum match_type minmatch = min_match_level(token->type);
200
201 /* check history/stack of tokens
202 * this disallows matching the same one more than once if there is a
203 * circle in the graph (used for keyword arguments) */
204 if (n == CMD_ARGC_MAX)
205 return MATCHER_NO_MATCH;
206 if (!token->allowrepeat)
207 for (size_t s = 0; s < n; s++)
208 if (stack[s] == start)
209 return MATCHER_NO_MATCH;
210
211 // get the current operating input token
212 char *input_token = vector_slot(vline, n);
213
214 #ifdef TRACE_MATCHER
215 fprintf(stdout, "\"%-20s\" matches \"%-30s\" ? ", input_token,
216 token->text);
217 enum match_type mt = match_token(token, input_token);
218 fprintf(stdout, "type: %d ", token->type);
219 fprintf(stdout, "min: %d - ", minmatch);
220 switch (mt) {
221 case trivial_match:
222 fprintf(stdout, "trivial_match ");
223 break;
224 case no_match:
225 fprintf(stdout, "no_match ");
226 break;
227 case partly_match:
228 fprintf(stdout, "partly_match ");
229 break;
230 case exact_match:
231 fprintf(stdout, "exact_match ");
232 break;
233 }
234 if (mt >= minmatch)
235 fprintf(stdout, " MATCH");
236 fprintf(stdout, "\n");
237 #endif
238
239 // if we don't match this node, die
240 if (match_token(token, input_token) < minmatch)
241 return MATCHER_NO_MATCH;
242
243 stack[n] = start;
244
245 // pointers for iterating linklist
246 struct listnode *ln;
247 struct graph_node *gn;
248
249 // get all possible nexthops
250 struct list *next = list_new();
251 add_nexthops(next, start, NULL, 0);
252
253 // determine the best match
254 for (ALL_LIST_ELEMENTS_RO(next, ln, gn)) {
255 // if we've matched all input we're looking for END_TKN
256 if (n + 1 == vector_active(vline)) {
257 struct cmd_token *tok = gn->data;
258 if (tok->type == END_TKN) {
259 // if more than one END_TKN in the follow set
260 if (*currbest) {
261 status = MATCHER_AMBIGUOUS;
262 break;
263 } else {
264 status = MATCHER_OK;
265 }
266 *currbest = list_new();
267 // node should have one child node with the
268 // element
269 struct graph_node *leaf =
270 vector_slot(gn->to, 0);
271 // last node in the list will hold the
272 // cmd_element; this is important because
273 // list_delete() expects that all nodes have
274 // the same data type, so when deleting this
275 // list the last node must be manually deleted
276 struct cmd_element *el = leaf->data;
277 listnode_add(*currbest, el);
278 (*currbest)->del =
279 (void (*)(void *)) & cmd_token_del;
280 // do not break immediately; continue walking
281 // through the follow set to ensure that there
282 // is exactly one END_TKN
283 }
284 continue;
285 }
286
287 // else recurse on candidate child node
288 struct list *result = NULL;
289 enum matcher_rv rstat =
290 command_match_r(gn, vline, n + 1, stack, &result);
291
292 // save the best match
293 if (result && *currbest) {
294 // pick the best of two matches
295 struct list *newbest =
296 disambiguate(*currbest, result, vline, n + 1);
297
298 // current best and result are ambiguous
299 if (!newbest)
300 status = MATCHER_AMBIGUOUS;
301 // current best is still the best, but ambiguous
302 else if (newbest == *currbest
303 && status == MATCHER_AMBIGUOUS)
304 status = MATCHER_AMBIGUOUS;
305 // result is better, but also ambiguous
306 else if (newbest == result
307 && rstat == MATCHER_AMBIGUOUS)
308 status = MATCHER_AMBIGUOUS;
309 // one or the other is superior and not ambiguous
310 else
311 status = MATCHER_OK;
312
313 // delete the unnecessary result
314 struct list *todelete =
315 ((newbest && newbest == result) ? *currbest
316 : result);
317 del_arglist(todelete);
318
319 *currbest = newbest ? newbest : *currbest;
320 } else if (result) {
321 status = rstat;
322 *currbest = result;
323 } else if (!*currbest) {
324 status = MAX(rstat, status);
325 }
326 }
327 if (*currbest) {
328 // copy token, set arg and prepend to currbest
329 token = start->data;
330 copy = cmd_token_dup(token);
331 copy->arg = XSTRDUP(MTYPE_CMD_ARG, input_token);
332 listnode_add_before(*currbest, (*currbest)->head, copy);
333 } else if (n + 1 == vector_active(vline) && status == MATCHER_NO_MATCH)
334 status = MATCHER_INCOMPLETE;
335
336 // cleanup
337 list_delete(&next);
338
339 return status;
340 }
341
stack_del(void * val)342 static void stack_del(void *val)
343 {
344 XFREE(MTYPE_CMD_MATCHSTACK, val);
345 }
346
command_complete(struct graph * graph,vector vline,struct list ** completions)347 enum matcher_rv command_complete(struct graph *graph, vector vline,
348 struct list **completions)
349 {
350 // pointer to next input token to match
351 char *input_token;
352
353 struct list *
354 current =
355 list_new(), // current nodes to match input token against
356 *next = list_new(); // possible next hops after current input
357 // token
358 current->del = next->del = stack_del;
359
360 // pointers used for iterating lists
361 struct graph_node **gstack, **newstack;
362 struct listnode *node;
363
364 // add all children of start node to list
365 struct graph_node *start = vector_slot(graph->nodes, 0);
366 add_nexthops(next, start, &start, 0);
367
368 unsigned int idx;
369 for (idx = 0; idx < vector_active(vline) && next->count > 0; idx++) {
370 list_delete(¤t);
371 current = next;
372 next = list_new();
373 next->del = stack_del;
374
375 input_token = vector_slot(vline, idx);
376
377 int exact_match_exists = 0;
378 for (ALL_LIST_ELEMENTS_RO(current, node, gstack))
379 if (!exact_match_exists)
380 exact_match_exists =
381 (match_token(gstack[0]->data,
382 input_token)
383 == exact_match);
384 else
385 break;
386
387 for (ALL_LIST_ELEMENTS_RO(current, node, gstack)) {
388 struct cmd_token *token = gstack[0]->data;
389
390 if (token->attr == CMD_ATTR_HIDDEN
391 || token->attr == CMD_ATTR_DEPRECATED)
392 continue;
393
394 enum match_type minmatch = min_match_level(token->type);
395 trace_matcher("\"%s\" matches \"%s\" (%d) ? ",
396 input_token, token->text, token->type);
397
398 unsigned int last_token =
399 (vector_active(vline) - 1 == idx);
400 enum match_type matchtype =
401 match_token(token, input_token);
402 switch (matchtype) {
403 // occurs when last token is whitespace
404 case trivial_match:
405 trace_matcher("trivial_match\n");
406 assert(last_token);
407 newstack = XMALLOC(MTYPE_CMD_MATCHSTACK,
408 sizeof(struct graph_node *));
409 /* we're not recursing here, just the first
410 * element is OK */
411 newstack[0] = gstack[0];
412 listnode_add(next, newstack);
413 break;
414 case partly_match:
415 trace_matcher("trivial_match\n");
416 if (exact_match_exists && !last_token)
417 break;
418 /* fallthru */
419 case exact_match:
420 trace_matcher("exact_match\n");
421 if (last_token) {
422 newstack = XMALLOC(
423 MTYPE_CMD_MATCHSTACK,
424 sizeof(struct graph_node *));
425 /* same as above, not recursing on this
426 */
427 newstack[0] = gstack[0];
428 listnode_add(next, newstack);
429 } else if (matchtype >= minmatch)
430 add_nexthops(next, gstack[0], gstack,
431 idx + 1);
432 break;
433 default:
434 trace_matcher("no_match\n");
435 break;
436 }
437 }
438 }
439
440 /* Variable summary
441 * -----------------------------------------------------------------
442 * token = last input token processed
443 * idx = index in `command` of last token processed
444 * current = set of all transitions from the previous input token
445 * next = set of all nodes reachable from all nodes in `matched`
446 */
447
448 enum matcher_rv mrv = idx == vector_active(vline) && next->count
449 ? MATCHER_OK
450 : MATCHER_NO_MATCH;
451
452 *completions = NULL;
453 if (!MATCHER_ERROR(mrv)) {
454 // extract cmd_token into list
455 *completions = list_new();
456 for (ALL_LIST_ELEMENTS_RO(next, node, gstack)) {
457 listnode_add(*completions, gstack[0]->data);
458 }
459 }
460
461 list_delete(¤t);
462 list_delete(&next);
463
464 return mrv;
465 }
466
467 /**
468 * Adds all children that are reachable by one parser hop to the given list.
469 * special tokens except END_TKN are treated as transparent.
470 *
471 * @param[in] list to add the nexthops to
472 * @param[in] node to start calculating nexthops from
473 * @param[in] stack listing previously visited nodes, if non-NULL.
474 * @param[in] stackpos how many valid entries are in stack
475 * @return the number of children added to the list
476 *
477 * NB: non-null "stack" means that new stacks will be added to "list" as
478 * output, instead of direct node pointers!
479 */
add_nexthops(struct list * list,struct graph_node * node,struct graph_node ** stack,size_t stackpos)480 static int add_nexthops(struct list *list, struct graph_node *node,
481 struct graph_node **stack, size_t stackpos)
482 {
483 int added = 0;
484 struct graph_node *child;
485 struct graph_node **nextstack;
486 for (unsigned int i = 0; i < vector_active(node->to); i++) {
487 child = vector_slot(node->to, i);
488 size_t j;
489 struct cmd_token *token = child->data;
490 if (!token->allowrepeat && stack) {
491 for (j = 0; j < stackpos; j++)
492 if (child == stack[j])
493 break;
494 if (j != stackpos)
495 continue;
496 }
497 if (token->type >= SPECIAL_TKN && token->type != END_TKN) {
498 added += add_nexthops(list, child, stack, stackpos);
499 } else {
500 if (stack) {
501 nextstack = XMALLOC(
502 MTYPE_CMD_MATCHSTACK,
503 (stackpos + 1)
504 * sizeof(struct graph_node *));
505 nextstack[0] = child;
506 memcpy(nextstack + 1, stack,
507 stackpos * sizeof(struct graph_node *));
508
509 listnode_add(list, nextstack);
510 } else
511 listnode_add(list, child);
512 added++;
513 }
514 }
515
516 return added;
517 }
518
519 /**
520 * Determines the node types for which a partial match may count as a full
521 * match. Enables command abbrevations.
522 *
523 * @param[in] type node type
524 * @return minimum match level needed to for a token to fully match
525 */
min_match_level(enum cmd_token_type type)526 static enum match_type min_match_level(enum cmd_token_type type)
527 {
528 switch (type) {
529 // anything matches a start node, for the sake of recursion
530 case START_TKN:
531 return no_match;
532 // allowing words to partly match enables command abbreviation
533 case WORD_TKN:
534 return partly_match;
535 default:
536 return exact_match;
537 }
538 }
539
540 /**
541 * Assigns precedence scores to node types.
542 *
543 * @param[in] type node type to score
544 * @return precedence score
545 */
score_precedence(enum cmd_token_type type)546 static int score_precedence(enum cmd_token_type type)
547 {
548 switch (type) {
549 // some of these are mutually exclusive, so they share
550 // the same precedence value
551 case IPV4_TKN:
552 case IPV4_PREFIX_TKN:
553 case IPV6_TKN:
554 case IPV6_PREFIX_TKN:
555 case MAC_TKN:
556 case MAC_PREFIX_TKN:
557 case RANGE_TKN:
558 return 2;
559 case WORD_TKN:
560 return 3;
561 case VARIABLE_TKN:
562 return 4;
563 default:
564 return 10;
565 }
566 }
567
568 /**
569 * Picks the better of two possible matches for a token.
570 *
571 * @param[in] first candidate node matching token
572 * @param[in] second candidate node matching token
573 * @param[in] token the token being matched
574 * @return the best-matching node, or NULL if the two are entirely ambiguous
575 */
disambiguate_tokens(struct cmd_token * first,struct cmd_token * second,char * input_token)576 static struct cmd_token *disambiguate_tokens(struct cmd_token *first,
577 struct cmd_token *second,
578 char *input_token)
579 {
580 // if the types are different, simply go off of type precedence
581 if (first->type != second->type) {
582 int firstprec = score_precedence(first->type);
583 int secndprec = score_precedence(second->type);
584 if (firstprec != secndprec)
585 return firstprec < secndprec ? first : second;
586 else
587 return NULL;
588 }
589
590 // if they're the same, return the more exact match
591 enum match_type fmtype = match_token(first, input_token);
592 enum match_type smtype = match_token(second, input_token);
593 if (fmtype != smtype)
594 return fmtype > smtype ? first : second;
595
596 return NULL;
597 }
598
599 /**
600 * Picks the better of two possible matches for an input line.
601 *
602 * @param[in] first candidate list of cmd_token matching vline
603 * @param[in] second candidate list of cmd_token matching vline
604 * @param[in] vline the input line being matched
605 * @param[in] n index into vline to start comparing at
606 * @return the best-matching list, or NULL if the two are entirely ambiguous
607 */
disambiguate(struct list * first,struct list * second,vector vline,unsigned int n)608 static struct list *disambiguate(struct list *first, struct list *second,
609 vector vline, unsigned int n)
610 {
611 assert(first != NULL);
612 assert(second != NULL);
613 // doesn't make sense for these to be inequal length
614 assert(first->count == second->count);
615 assert(first->count == vector_active(vline) - n + 1);
616
617 struct listnode *fnode = listhead_unchecked(first),
618 *snode = listhead_unchecked(second);
619 struct cmd_token *ftok = listgetdata(fnode), *stok = listgetdata(snode),
620 *best = NULL;
621
622 // compare each token, if one matches better use that one
623 for (unsigned int i = n; i < vector_active(vline); i++) {
624 char *token = vector_slot(vline, i);
625 if ((best = disambiguate_tokens(ftok, stok, token)))
626 return best == ftok ? first : second;
627 fnode = listnextnode(fnode);
628 snode = listnextnode(snode);
629 ftok = listgetdata(fnode);
630 stok = listgetdata(snode);
631 }
632
633 return NULL;
634 }
635
636 /*
637 * Deletion function for arglist.
638 *
639 * Since list->del for arglists expects all listnode->data to hold cmd_token,
640 * but arglists have cmd_element as the data for the tail, this function
641 * manually deletes the tail before deleting the rest of the list as usual.
642 *
643 * The cmd_element at the end is *not* a copy. It is the one and only.
644 *
645 * @param list the arglist to delete
646 */
del_arglist(struct list * list)647 static void del_arglist(struct list *list)
648 {
649 // manually delete last node
650 struct listnode *tail = listtail(list);
651 tail->data = NULL;
652 list_delete_node(list, tail);
653
654 // delete the rest of the list as usual
655 list_delete(&list);
656 }
657
658 /*---------- token level matching functions ----------*/
659
match_token(struct cmd_token * token,char * input_token)660 static enum match_type match_token(struct cmd_token *token, char *input_token)
661 {
662 // nothing trivially matches everything
663 if (!input_token)
664 return trivial_match;
665
666 switch (token->type) {
667 case WORD_TKN:
668 return match_word(token, input_token);
669 case IPV4_TKN:
670 return match_ipv4(input_token);
671 case IPV4_PREFIX_TKN:
672 return match_ipv4_prefix(input_token);
673 case IPV6_TKN:
674 return match_ipv6_prefix(input_token, false);
675 case IPV6_PREFIX_TKN:
676 return match_ipv6_prefix(input_token, true);
677 case RANGE_TKN:
678 return match_range(token, input_token);
679 case VARIABLE_TKN:
680 return match_variable(token, input_token);
681 case MAC_TKN:
682 return match_mac(input_token, false);
683 case MAC_PREFIX_TKN:
684 return match_mac(input_token, true);
685 case END_TKN:
686 default:
687 return no_match;
688 }
689 }
690
691 #define IPV4_ADDR_STR "0123456789."
692 #define IPV4_PREFIX_STR "0123456789./"
693
match_ipv4(const char * str)694 static enum match_type match_ipv4(const char *str)
695 {
696 const char *sp;
697 int dots = 0, nums = 0;
698 char buf[4];
699
700 for (;;) {
701 memset(buf, 0, sizeof(buf));
702 sp = str;
703 while (*str != '\0') {
704 if (*str == '.') {
705 if (dots >= 3)
706 return no_match;
707
708 if (*(str + 1) == '.')
709 return no_match;
710
711 if (*(str + 1) == '\0')
712 return partly_match;
713
714 dots++;
715 break;
716 }
717 if (!isdigit((unsigned char)*str))
718 return no_match;
719
720 str++;
721 }
722
723 if (str - sp > 3)
724 return no_match;
725
726 memcpy(buf, sp, str - sp);
727
728 int v = atoi(buf);
729
730 if (v > 255)
731 return no_match;
732 if (v > 0 && buf[0] == '0')
733 return no_match;
734
735 nums++;
736
737 if (*str == '\0')
738 break;
739
740 str++;
741 }
742
743 if (nums < 4)
744 return partly_match;
745
746 return exact_match;
747 }
748
match_ipv4_prefix(const char * str)749 static enum match_type match_ipv4_prefix(const char *str)
750 {
751 const char *sp;
752 int dots = 0;
753 char buf[4];
754
755 for (;;) {
756 memset(buf, 0, sizeof(buf));
757 sp = str;
758 while (*str != '\0' && *str != '/') {
759 if (*str == '.') {
760 if (dots == 3)
761 return no_match;
762
763 if (*(str + 1) == '.' || *(str + 1) == '/')
764 return no_match;
765
766 if (*(str + 1) == '\0')
767 return partly_match;
768
769 dots++;
770 break;
771 }
772
773 if (!isdigit((unsigned char)*str))
774 return no_match;
775
776 str++;
777 }
778
779 if (str - sp > 3)
780 return no_match;
781
782 memcpy(buf, sp, str - sp);
783
784 int v = atoi(buf);
785
786 if (v > 255)
787 return no_match;
788 if (v > 0 && buf[0] == '0')
789 return no_match;
790
791 if (dots == 3) {
792 if (*str == '/') {
793 if (*(str + 1) == '\0')
794 return partly_match;
795
796 str++;
797 break;
798 } else if (*str == '\0')
799 return partly_match;
800 }
801
802 if (*str == '\0')
803 return partly_match;
804
805 str++;
806 }
807
808 sp = str;
809 while (*str != '\0') {
810 if (!isdigit((unsigned char)*str))
811 return no_match;
812
813 str++;
814 }
815
816 if (atoi(sp) > 32)
817 return no_match;
818
819 return exact_match;
820 }
821
822
823 #define IPV6_ADDR_STR "0123456789abcdefABCDEF:."
824 #define IPV6_PREFIX_STR "0123456789abcdefABCDEF:./"
825 #define STATE_START 1
826 #define STATE_COLON 2
827 #define STATE_DOUBLE 3
828 #define STATE_ADDR 4
829 #define STATE_DOT 5
830 #define STATE_SLASH 6
831 #define STATE_MASK 7
832
match_ipv6_prefix(const char * str,bool prefix)833 static enum match_type match_ipv6_prefix(const char *str, bool prefix)
834 {
835 int state = STATE_START;
836 int colons = 0, nums = 0, double_colon = 0;
837 int mask;
838 const char *sp = NULL, *start = str;
839 char *endptr = NULL;
840
841 if (str == NULL)
842 return partly_match;
843
844 if (strspn(str, prefix ? IPV6_PREFIX_STR : IPV6_ADDR_STR)
845 != strlen(str))
846 return no_match;
847
848 while (*str != '\0' && state != STATE_MASK) {
849 switch (state) {
850 case STATE_START:
851 if (*str == ':') {
852 if (*(str + 1) != ':' && *(str + 1) != '\0')
853 return no_match;
854 colons--;
855 state = STATE_COLON;
856 } else {
857 sp = str;
858 state = STATE_ADDR;
859 }
860
861 continue;
862 case STATE_COLON:
863 colons++;
864 if (*(str + 1) == '/')
865 return no_match;
866 else if (*(str + 1) == ':')
867 state = STATE_DOUBLE;
868 else {
869 sp = str + 1;
870 state = STATE_ADDR;
871 }
872 break;
873 case STATE_DOUBLE:
874 if (double_colon)
875 return no_match;
876
877 if (*(str + 1) == ':')
878 return no_match;
879 else {
880 if (*(str + 1) != '\0' && *(str + 1) != '/')
881 colons++;
882 sp = str + 1;
883
884 if (*(str + 1) == '/')
885 state = STATE_SLASH;
886 else
887 state = STATE_ADDR;
888 }
889
890 double_colon++;
891 nums += 1;
892 break;
893 case STATE_ADDR:
894 if (*(str + 1) == ':' || *(str + 1) == '.'
895 || *(str + 1) == '\0' || *(str + 1) == '/') {
896 if (str - sp > 3)
897 return no_match;
898
899 for (; sp <= str; sp++)
900 if (*sp == '/')
901 return no_match;
902
903 nums++;
904
905 if (*(str + 1) == ':')
906 state = STATE_COLON;
907 else if (*(str + 1) == '.') {
908 if (colons || double_colon)
909 state = STATE_DOT;
910 else
911 return no_match;
912 } else if (*(str + 1) == '/')
913 state = STATE_SLASH;
914 }
915 break;
916 case STATE_DOT:
917 state = STATE_ADDR;
918 break;
919 case STATE_SLASH:
920 if (*(str + 1) == '\0')
921 return partly_match;
922
923 state = STATE_MASK;
924 break;
925 default:
926 break;
927 }
928
929 if (nums > 11)
930 return no_match;
931
932 if (colons > 7)
933 return no_match;
934
935 str++;
936 }
937
938 if (!prefix) {
939 struct sockaddr_in6 sin6_dummy;
940 int ret = inet_pton(AF_INET6, start, &sin6_dummy.sin6_addr);
941 return ret == 1 ? exact_match : partly_match;
942 }
943
944 if (state < STATE_MASK)
945 return partly_match;
946
947 mask = strtol(str, &endptr, 10);
948 if (*endptr != '\0')
949 return no_match;
950
951 if (mask < 0 || mask > 128)
952 return no_match;
953
954 return exact_match;
955 }
956
match_range(struct cmd_token * token,const char * str)957 static enum match_type match_range(struct cmd_token *token, const char *str)
958 {
959 assert(token->type == RANGE_TKN);
960
961 char *endptr = NULL;
962 long long val;
963
964 val = strtoll(str, &endptr, 10);
965 if (*endptr != '\0')
966 return no_match;
967
968 if (val < token->min || val > token->max)
969 return no_match;
970 else
971 return exact_match;
972 }
973
match_word(struct cmd_token * token,const char * word)974 static enum match_type match_word(struct cmd_token *token, const char *word)
975 {
976 assert(token->type == WORD_TKN);
977
978 // if the passed token is 0 length, partly match
979 if (!strlen(word))
980 return partly_match;
981
982 // if the passed token is strictly a prefix of the full word, partly
983 // match
984 if (strlen(word) < strlen(token->text))
985 return !strncmp(token->text, word, strlen(word)) ? partly_match
986 : no_match;
987
988 // if they are the same length and exactly equal, exact match
989 else if (strlen(word) == strlen(token->text))
990 return !strncmp(token->text, word, strlen(word)) ? exact_match
991 : no_match;
992
993 return no_match;
994 }
995
match_variable(struct cmd_token * token,const char * word)996 static enum match_type match_variable(struct cmd_token *token, const char *word)
997 {
998 assert(token->type == VARIABLE_TKN);
999 return exact_match;
1000 }
1001
1002 #define MAC_CHARS "ABCDEFabcdef0123456789:"
1003
match_mac(const char * word,bool prefix)1004 static enum match_type match_mac(const char *word, bool prefix)
1005 {
1006 /* 6 2-digit hex numbers separated by 5 colons */
1007 size_t mac_explen = 6 * 2 + 5;
1008 /* '/' + 2-digit integer */
1009 size_t mask_len = 1 + 2;
1010 unsigned int i;
1011 char *eptr;
1012 unsigned int maskval;
1013
1014 /* length check */
1015 if (strlen(word) > mac_explen + (prefix ? mask_len : 0))
1016 return no_match;
1017
1018 /* address check */
1019 for (i = 0; i < mac_explen; i++) {
1020 if (word[i] == '\0' || !strchr(MAC_CHARS, word[i]))
1021 break;
1022 if (((i + 1) % 3 == 0) != (word[i] == ':'))
1023 return no_match;
1024 }
1025
1026 /* incomplete address */
1027 if (i < mac_explen && word[i] == '\0')
1028 return partly_match;
1029 else if (i < mac_explen)
1030 return no_match;
1031
1032 /* mask check */
1033 if (prefix && word[i] == '/') {
1034 if (word[++i] == '\0')
1035 return partly_match;
1036
1037 maskval = strtoul(&word[i], &eptr, 10);
1038 if (*eptr != '\0' || maskval > 48)
1039 return no_match;
1040 } else if (prefix && word[i] == '\0') {
1041 return partly_match;
1042 } else if (prefix) {
1043 return no_match;
1044 }
1045
1046 return exact_match;
1047 }
1048