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