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