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