]>
Commit | Line | Data |
---|---|---|
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 | ||
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, (void *)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 | */ | |
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 *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 | struct cmd_token *token = start->data; | |
330 | struct cmd_token *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_and_null(&next); | |
338 | ||
339 | return status; | |
340 | } | |
341 | ||
342 | static void stack_del(void *val) | |
343 | { | |
344 | XFREE(MTYPE_CMD_MATCHSTACK, val); | |
345 | } | |
346 | ||
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_and_null(¤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_and_null(¤t); | |
462 | list_delete_and_null(&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 | */ | |
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 | */ | |
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 | */ | |
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 | */ | |
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 | */ | |
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 | */ | |
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_and_null(&list); | |
656 | } | |
657 | ||
658 | /*---------- token level matching functions ----------*/ | |
659 | ||
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 | ||
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((int)*str)) | |
718 | return no_match; | |
719 | ||
720 | str++; | |
721 | } | |
722 | ||
723 | if (str - sp > 3) | |
724 | return no_match; | |
725 | ||
726 | strncpy(buf, sp, str - sp); | |
727 | if (atoi(buf) > 255) | |
728 | return no_match; | |
729 | ||
730 | nums++; | |
731 | ||
732 | if (*str == '\0') | |
733 | break; | |
734 | ||
735 | str++; | |
736 | } | |
737 | ||
738 | if (nums < 4) | |
739 | return partly_match; | |
740 | ||
741 | return exact_match; | |
742 | } | |
743 | ||
744 | static enum match_type match_ipv4_prefix(const char *str) | |
745 | { | |
746 | const char *sp; | |
747 | int dots = 0; | |
748 | char buf[4]; | |
749 | ||
750 | for (;;) { | |
751 | memset(buf, 0, sizeof(buf)); | |
752 | sp = str; | |
753 | while (*str != '\0' && *str != '/') { | |
754 | if (*str == '.') { | |
755 | if (dots == 3) | |
756 | return no_match; | |
757 | ||
758 | if (*(str + 1) == '.' || *(str + 1) == '/') | |
759 | return no_match; | |
760 | ||
761 | if (*(str + 1) == '\0') | |
762 | return partly_match; | |
763 | ||
764 | dots++; | |
765 | break; | |
766 | } | |
767 | ||
768 | if (!isdigit((int)*str)) | |
769 | return no_match; | |
770 | ||
771 | str++; | |
772 | } | |
773 | ||
774 | if (str - sp > 3) | |
775 | return no_match; | |
776 | ||
777 | strncpy(buf, sp, str - sp); | |
778 | if (atoi(buf) > 255) | |
779 | return no_match; | |
780 | ||
781 | if (dots == 3) { | |
782 | if (*str == '/') { | |
783 | if (*(str + 1) == '\0') | |
784 | return partly_match; | |
785 | ||
786 | str++; | |
787 | break; | |
788 | } else if (*str == '\0') | |
789 | return partly_match; | |
790 | } | |
791 | ||
792 | if (*str == '\0') | |
793 | return partly_match; | |
794 | ||
795 | str++; | |
796 | } | |
797 | ||
798 | sp = str; | |
799 | while (*str != '\0') { | |
800 | if (!isdigit((int)*str)) | |
801 | return no_match; | |
802 | ||
803 | str++; | |
804 | } | |
805 | ||
806 | if (atoi(sp) > 32) | |
807 | return no_match; | |
808 | ||
809 | return exact_match; | |
810 | } | |
811 | ||
812 | ||
813 | #define IPV6_ADDR_STR "0123456789abcdefABCDEF:." | |
814 | #define IPV6_PREFIX_STR "0123456789abcdefABCDEF:./" | |
815 | #define STATE_START 1 | |
816 | #define STATE_COLON 2 | |
817 | #define STATE_DOUBLE 3 | |
818 | #define STATE_ADDR 4 | |
819 | #define STATE_DOT 5 | |
820 | #define STATE_SLASH 6 | |
821 | #define STATE_MASK 7 | |
822 | ||
823 | static enum match_type match_ipv6_prefix(const char *str, bool prefix) | |
824 | { | |
825 | int state = STATE_START; | |
826 | int colons = 0, nums = 0, double_colon = 0; | |
827 | int mask; | |
828 | const char *sp = NULL, *start = str; | |
829 | char *endptr = NULL; | |
830 | ||
831 | if (str == NULL) | |
832 | return partly_match; | |
833 | ||
834 | if (strspn(str, prefix ? IPV6_PREFIX_STR : IPV6_ADDR_STR) | |
835 | != strlen(str)) | |
836 | return no_match; | |
837 | ||
838 | while (*str != '\0' && state != STATE_MASK) { | |
839 | switch (state) { | |
840 | case STATE_START: | |
841 | if (*str == ':') { | |
842 | if (*(str + 1) != ':' && *(str + 1) != '\0') | |
843 | return no_match; | |
844 | colons--; | |
845 | state = STATE_COLON; | |
846 | } else { | |
847 | sp = str; | |
848 | state = STATE_ADDR; | |
849 | } | |
850 | ||
851 | continue; | |
852 | case STATE_COLON: | |
853 | colons++; | |
854 | if (*(str + 1) == '/') | |
855 | return no_match; | |
856 | else if (*(str + 1) == ':') | |
857 | state = STATE_DOUBLE; | |
858 | else { | |
859 | sp = str + 1; | |
860 | state = STATE_ADDR; | |
861 | } | |
862 | break; | |
863 | case STATE_DOUBLE: | |
864 | if (double_colon) | |
865 | return no_match; | |
866 | ||
867 | if (*(str + 1) == ':') | |
868 | return no_match; | |
869 | else { | |
870 | if (*(str + 1) != '\0' && *(str + 1) != '/') | |
871 | colons++; | |
872 | sp = str + 1; | |
873 | ||
874 | if (*(str + 1) == '/') | |
875 | state = STATE_SLASH; | |
876 | else | |
877 | state = STATE_ADDR; | |
878 | } | |
879 | ||
880 | double_colon++; | |
881 | nums += 1; | |
882 | break; | |
883 | case STATE_ADDR: | |
884 | if (*(str + 1) == ':' || *(str + 1) == '.' | |
885 | || *(str + 1) == '\0' || *(str + 1) == '/') { | |
886 | if (str - sp > 3) | |
887 | return no_match; | |
888 | ||
889 | for (; sp <= str; sp++) | |
890 | if (*sp == '/') | |
891 | return no_match; | |
892 | ||
893 | nums++; | |
894 | ||
895 | if (*(str + 1) == ':') | |
896 | state = STATE_COLON; | |
897 | else if (*(str + 1) == '.') { | |
898 | if (colons || double_colon) | |
899 | state = STATE_DOT; | |
900 | else | |
901 | return no_match; | |
902 | } else if (*(str + 1) == '/') | |
903 | state = STATE_SLASH; | |
904 | } | |
905 | break; | |
906 | case STATE_DOT: | |
907 | state = STATE_ADDR; | |
908 | break; | |
909 | case STATE_SLASH: | |
910 | if (*(str + 1) == '\0') | |
911 | return partly_match; | |
912 | ||
913 | state = STATE_MASK; | |
914 | break; | |
915 | default: | |
916 | break; | |
917 | } | |
918 | ||
919 | if (nums > 11) | |
920 | return no_match; | |
921 | ||
922 | if (colons > 7) | |
923 | return no_match; | |
924 | ||
925 | str++; | |
926 | } | |
927 | ||
928 | if (!prefix) { | |
929 | struct sockaddr_in6 sin6_dummy; | |
930 | int ret = inet_pton(AF_INET6, start, &sin6_dummy.sin6_addr); | |
931 | return ret == 1 ? exact_match : partly_match; | |
932 | } | |
933 | ||
934 | if (state < STATE_MASK) | |
935 | return partly_match; | |
936 | ||
937 | mask = strtol(str, &endptr, 10); | |
938 | if (*endptr != '\0') | |
939 | return no_match; | |
940 | ||
941 | if (mask < 0 || mask > 128) | |
942 | return no_match; | |
943 | ||
944 | return exact_match; | |
945 | } | |
946 | ||
947 | static enum match_type match_range(struct cmd_token *token, const char *str) | |
948 | { | |
949 | assert(token->type == RANGE_TKN); | |
950 | ||
951 | char *endptr = NULL; | |
952 | long long val; | |
953 | ||
954 | val = strtoll(str, &endptr, 10); | |
955 | if (*endptr != '\0') | |
956 | return no_match; | |
957 | ||
958 | if (val < token->min || val > token->max) | |
959 | return no_match; | |
960 | else | |
961 | return exact_match; | |
962 | } | |
963 | ||
964 | static enum match_type match_word(struct cmd_token *token, const char *word) | |
965 | { | |
966 | assert(token->type == WORD_TKN); | |
967 | ||
968 | // if the passed token is 0 length, partly match | |
969 | if (!strlen(word)) | |
970 | return partly_match; | |
971 | ||
972 | // if the passed token is strictly a prefix of the full word, partly | |
973 | // match | |
974 | if (strlen(word) < strlen(token->text)) | |
975 | return !strncmp(token->text, word, strlen(word)) ? partly_match | |
976 | : no_match; | |
977 | ||
978 | // if they are the same length and exactly equal, exact match | |
979 | else if (strlen(word) == strlen(token->text)) | |
980 | return !strncmp(token->text, word, strlen(word)) ? exact_match | |
981 | : no_match; | |
982 | ||
983 | return no_match; | |
984 | } | |
985 | ||
986 | static enum match_type match_variable(struct cmd_token *token, const char *word) | |
987 | { | |
988 | assert(token->type == VARIABLE_TKN); | |
989 | return exact_match; | |
990 | } | |
991 | ||
992 | #define MAC_CHARS "ABCDEFabcdef0123456789:" | |
993 | ||
994 | static enum match_type match_mac(const char *word, bool prefix) | |
995 | { | |
996 | /* 6 2-digit hex numbers separated by 5 colons */ | |
997 | size_t mac_explen = 6 * 2 + 5; | |
998 | /* '/' + 2-digit integer */ | |
999 | size_t mask_len = 1 + 2; | |
1000 | unsigned int i; | |
1001 | char *eptr; | |
1002 | unsigned int maskval; | |
1003 | ||
1004 | /* length check */ | |
1005 | if (strlen(word) > mac_explen + (prefix ? mask_len : 0)) | |
1006 | return no_match; | |
1007 | ||
1008 | /* address check */ | |
1009 | for (i = 0; i < mac_explen; i++) { | |
1010 | if (word[i] == '\0' || !strchr(MAC_CHARS, word[i])) | |
1011 | break; | |
1012 | if (((i + 1) % 3 == 0) != (word[i] == ':')) | |
1013 | return no_match; | |
1014 | } | |
1015 | ||
1016 | /* incomplete address */ | |
1017 | if (i < mac_explen && word[i] == '\0') | |
1018 | return partly_match; | |
1019 | else if (i < mac_explen) | |
1020 | return no_match; | |
1021 | ||
1022 | /* mask check */ | |
1023 | if (prefix && word[i] == '/') { | |
1024 | if (word[++i] == '\0') | |
1025 | return partly_match; | |
1026 | ||
1027 | maskval = strtoul(&word[i], &eptr, 10); | |
1028 | if (*eptr != '\0' || maskval > 48) | |
1029 | return no_match; | |
1030 | } else if (prefix && word[i] == '\0') { | |
1031 | return partly_match; | |
1032 | } else if (prefix) { | |
1033 | return no_match; | |
1034 | } | |
1035 | ||
1036 | return exact_match; | |
1037 | } |