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