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