]>
Commit | Line | Data |
---|---|---|
eceb1066 QY |
1 | #include "command_match.h" |
2 | #include "command_parse.h" | |
9d0662e0 QY |
3 | #include <zebra.h> |
4 | #include "memory.h" | |
9d0662e0 | 5 | |
eceb1066 | 6 | /* matcher helper prototypes */ |
880e24a1 QY |
7 | static int |
8 | add_nexthops(struct list *, struct graph_node *); | |
18be0e59 | 9 | |
eceb1066 | 10 | static struct list * |
76699ae7 QY |
11 | match_build_argv_r (struct graph_node *, vector, unsigned int); |
12 | ||
13 | static int | |
14 | score_precedence (struct graph_node *); | |
eceb1066 QY |
15 | |
16 | /* token matcher prototypes */ | |
17 | static enum match_type | |
18 | match_ipv4 (const char *); | |
19 | ||
880e24a1 | 20 | static enum match_type |
eceb1066 | 21 | match_ipv4_prefix (const char *); |
18be0e59 | 22 | |
880e24a1 | 23 | static enum match_type |
eceb1066 | 24 | match_ipv6 (const char *); |
18be0e59 | 25 | |
880e24a1 | 26 | static enum match_type |
eceb1066 | 27 | match_ipv6_prefix (const char *); |
18be0e59 | 28 | |
880e24a1 | 29 | static enum match_type |
eceb1066 | 30 | match_range (struct graph_node *, const char *str); |
18be0e59 | 31 | |
880e24a1 | 32 | static enum match_type |
eceb1066 | 33 | match_word (struct graph_node *, enum filter_type, const char *); |
18be0e59 | 34 | |
880e24a1 | 35 | static enum match_type |
eceb1066 | 36 | match_number (struct graph_node *, const char *); |
18be0e59 | 37 | |
eceb1066 QY |
38 | static enum match_type |
39 | match_variable (struct graph_node *, const char *); | |
18be0e59 | 40 | |
880e24a1 QY |
41 | static enum match_type |
42 | match_token (struct graph_node *, char *, enum filter_type); | |
18be0e59 | 43 | |
880e24a1 | 44 | /* matching functions */ |
18be0e59 | 45 | |
eceb1066 QY |
46 | struct cmd_element * |
47 | match_command (struct graph_node *start, const char *line, enum filter_type filter) | |
a53fbbf5 QY |
48 | { |
49 | // get all possible completions | |
eceb1066 | 50 | struct list *completions = match_command_complete (start, line, filter); |
a53fbbf5 QY |
51 | |
52 | // one of them should be END_GN if this command matches | |
53 | struct graph_node *gn; | |
54 | struct listnode *node; | |
eceb1066 | 55 | for (ALL_LIST_ELEMENTS_RO(completions,node,gn)) |
a53fbbf5 QY |
56 | { |
57 | if (gn->type == END_GN) | |
58 | break; | |
59 | gn = NULL; | |
60 | } | |
61 | return gn ? gn->element : NULL; | |
62 | } | |
63 | ||
880e24a1 | 64 | struct list * |
eceb1066 | 65 | match_command_complete (struct graph_node *start, const char *line, enum filter_type filter) |
9d0662e0 | 66 | { |
eceb1066 QY |
67 | // vectorize command line |
68 | vector vline = cmd_make_strvec (line); | |
18be0e59 QY |
69 | |
70 | // pointer to next input token to match | |
71 | char *token; | |
72 | ||
73 | struct list *current = list_new(), // current nodes to match input token against | |
74 | *matched = list_new(), // current nodes that match the input token | |
75 | *next = list_new(); // possible next hops to current input token | |
76 | ||
77 | // pointers used for iterating lists | |
a53fbbf5 | 78 | struct graph_node *gn; |
18be0e59 QY |
79 | struct listnode *node; |
80 | ||
81 | // add all children of start node to list | |
82 | add_nexthops(next, start); | |
83 | ||
84 | unsigned int idx; | |
eceb1066 | 85 | for (idx = 0; idx < vector_active(vline) && next->count > 0; idx++) |
18be0e59 QY |
86 | { |
87 | list_free (current); | |
88 | current = next; | |
89 | next = list_new(); | |
90 | ||
eceb1066 | 91 | token = vector_slot(vline, idx); |
18be0e59 QY |
92 | |
93 | list_delete_all_node(matched); | |
94 | ||
a53fbbf5 | 95 | for (ALL_LIST_ELEMENTS_RO(current,node,gn)) |
18be0e59 | 96 | { |
a53fbbf5 QY |
97 | if (match_token(gn, token, filter) == exact_match) { |
98 | listnode_add(matched, gn); | |
99 | add_nexthops(next, gn); | |
18be0e59 QY |
100 | } |
101 | } | |
102 | } | |
103 | ||
104 | /* Variable summary | |
105 | * ----------------------------------------------------------------- | |
106 | * token = last input token processed | |
107 | * idx = index in `command` of last token processed | |
108 | * current = set of all transitions from the previous input token | |
109 | * matched = set of all nodes reachable with current input | |
110 | * next = set of all nodes reachable from all nodes in `matched` | |
111 | */ | |
880e24a1 QY |
112 | list_free (current); |
113 | list_free (matched); | |
114 | ||
eceb1066 QY |
115 | cmd_free_strvec(vline); |
116 | ||
880e24a1 QY |
117 | return next; |
118 | } | |
119 | ||
120 | /** | |
121 | * Adds all children that are reachable by one parser hop | |
122 | * to the given list. NUL_GN, SELECTOR_GN, and OPTION_GN | |
eceb1066 | 123 | * nodes are treated as transparent. |
880e24a1 QY |
124 | * |
125 | * @param[out] l the list to add the children to | |
126 | * @param[in] node the node to get the children of | |
127 | * @return the number of children added to the list | |
128 | */ | |
129 | static int | |
130 | add_nexthops(struct list *l, struct graph_node *node) | |
131 | { | |
132 | int added = 0; | |
133 | struct graph_node *child; | |
134 | for (unsigned int i = 0; i < vector_active(node->children); i++) | |
135 | { | |
136 | child = vector_slot(node->children, i); | |
a53fbbf5 QY |
137 | switch (child->type) { |
138 | case OPTION_GN: | |
139 | case SELECTOR_GN: | |
140 | case NUL_GN: | |
141 | added += add_nexthops(l, child); | |
142 | break; | |
143 | default: | |
144 | listnode_add(l, child); | |
145 | added++; | |
880e24a1 QY |
146 | } |
147 | } | |
148 | return added; | |
149 | } | |
18be0e59 | 150 | |
eceb1066 QY |
151 | struct list * |
152 | match_build_argv (const char *line, struct cmd_element *element) | |
a53fbbf5 | 153 | { |
eceb1066 QY |
154 | struct list *argv = NULL; |
155 | ||
156 | // parse command | |
a53fbbf5 | 157 | struct graph_node *start = new_node(NUL_GN); |
eceb1066 QY |
158 | parse_command_format(start, element); |
159 | ||
160 | vector vline = cmd_make_strvec (line); | |
161 | ||
162 | for (unsigned int i = 0; i < vector_active(start->children); i++) | |
163 | { | |
164 | // call recursive builder on each starting child | |
165 | argv = match_build_argv_r (vector_slot(start->children, i), vline, 0); | |
76699ae7 QY |
166 | // if any of them succeed, return their argv |
167 | // since all command DFA's must begin with a word and these are deduplicated, | |
168 | // no need to check precedence | |
eceb1066 QY |
169 | if (argv) break; |
170 | } | |
171 | ||
172 | return argv; | |
a53fbbf5 | 173 | } |
a53fbbf5 | 174 | |
76699ae7 QY |
175 | /** |
176 | * Builds an argument list given a DFA and a matching input line. | |
177 | * This function should be passed the start node of the DFA, a matching | |
178 | * input line, and the index of the first input token in the input line. | |
179 | * | |
180 | * First the function determines if the node it is passed matches the | |
181 | * first token of input. If it does not, it returns NULL. If it does | |
182 | * match, then it saves the input token as the head of an argument list. | |
183 | * | |
184 | * The next step is to see if there is further input in the input line. | |
185 | * If there is not, the current node's children are searched to see if | |
186 | * any of them are leaves (type END_GN). If this is the case, then the | |
187 | * bottom of the recursion stack has been reached, and the argument list | |
188 | * (with one node) is returned. If it is not the case, NULL is returned, | |
189 | * indicating that there is no match for the input along this path. | |
190 | * | |
191 | * If there is further input, then the function recurses on each of the | |
192 | * current node's children, passing them the input line minus the token | |
193 | * that was just matched. For each child, the return value of the recursive | |
194 | * call is inspected. If it is null, then there is no match for the input along | |
195 | * the subgraph headed by that child. If it is not null, then there is at least | |
196 | * one input match in that subgraph (more on this in a moment). | |
197 | * | |
198 | * If a recursive call on a child returns a non-null value, then it has matched | |
199 | * the input given it on the subgraph that starts with that child. However, due | |
200 | * to the flexibility of the grammar, it is sometimes the case that two or more | |
201 | * child graphs match the same input (two or more of the recursive calls have | |
202 | * non-NULL return values). This is not a valid state, since only one | |
203 | * true match is possible. In order to resolve this conflict, the function | |
204 | * keeps a reference to the child node that most specifically matches the | |
205 | * input. This is done by assigning each node type a precedence. If a child is | |
206 | * found to match the remaining input, then the precedence values of the | |
207 | * current best-matching child and this new match are compared. The node with | |
208 | * higher precedence is kept, and the other match is discarded. Due to the | |
209 | * recursive nature of this function, it is only necessary to compare the | |
210 | * precedence of immediate children, since all subsequent children will already | |
211 | * have been disambiguated in this way. | |
212 | * | |
213 | * In the event that two children are found to match with the same precedence, | |
214 | * then this command is totally ambiguous (how did you even match it in the first | |
215 | * place?) and NULL is returned. | |
216 | * | |
217 | * The ultimate return value is an ordered linked list of nodes that comprise | |
218 | * the best match for the command, each with their `arg` fields pointing to the | |
219 | * matching token string. | |
220 | * | |
221 | * @param[out] start the start node. | |
222 | * @param[in] vline the vectorized input line. | |
223 | * @param[in] n the index of the first input token. Should be 0 for external | |
224 | * callers. | |
225 | */ | |
eceb1066 QY |
226 | static struct list * |
227 | match_build_argv_r (struct graph_node *start, vector vline, unsigned int n) | |
228 | { | |
229 | // if we don't match this node, die | |
76699ae7 | 230 | if (match_token(start, vector_slot(vline, n), FILTER_STRICT) != exact_match) |
eceb1066 QY |
231 | return NULL; |
232 | ||
76699ae7 | 233 | // arg list for this subgraph |
eceb1066 | 234 | struct list *argv = list_new(); |
76699ae7 QY |
235 | |
236 | // pointers for iterating linklist | |
eceb1066 QY |
237 | struct graph_node *gn; |
238 | struct listnode *ln; | |
239 | ||
240 | // append current arg | |
eceb1066 QY |
241 | listnode_add(argv, start); |
242 | ||
243 | // get all possible nexthops | |
244 | struct list *next = list_new(); | |
245 | add_nexthops(next, start); | |
246 | ||
76699ae7 QY |
247 | // if we're at the end of input, need END_GN or no match |
248 | if (n+1 == vector_active (vline)) { | |
249 | for (ALL_LIST_ELEMENTS_RO(next,ln,gn)) { | |
250 | if (gn->type == END_GN) { | |
251 | list_delete (next); | |
252 | start->arg = XSTRDUP(MTYPE_CMD_TOKENS, vector_slot(vline, n)); | |
253 | if (start->type == VARIABLE_GN) | |
254 | fprintf(stderr, "Setting variable %s->arg with text %s\n", start->text, start->arg); | |
255 | return argv; | |
256 | } | |
eceb1066 | 257 | } |
76699ae7 QY |
258 | list_free (next); |
259 | return NULL; | |
eceb1066 QY |
260 | } |
261 | ||
eceb1066 | 262 | // otherwise recurse on all nexthops |
76699ae7 | 263 | struct list *bestmatch = NULL; |
eceb1066 | 264 | for (ALL_LIST_ELEMENTS_RO(next,ln,gn)) |
76699ae7 QY |
265 | { |
266 | if (gn->type == END_GN) // skip END_GN since we aren't at end of input | |
267 | continue; | |
268 | ||
269 | // get the result of the next node | |
270 | for (unsigned int i = 0; i < n; i++) fprintf(stderr, "\t"); | |
271 | fprintf(stderr, "Recursing on node %s for token %s\n", gn->text, (char*) vector_slot(vline, n+1)); | |
272 | struct list *result = match_build_argv_r (gn, vline, n+1); | |
273 | ||
274 | // compare to our current best match, and save if it's better | |
275 | if (result) { | |
276 | if (bestmatch) { | |
277 | int currprec = score_precedence (listgetdata(listhead(bestmatch))); | |
278 | int rsltprec = score_precedence (gn); | |
279 | if (currprec < rsltprec) | |
280 | list_delete (result); | |
281 | if (currprec > rsltprec) { | |
282 | for (unsigned int i = 0; i < n; i++) fprintf(stderr, "\t"); | |
283 | fprintf(stderr, ">> Overwriting bestmatch with: %s\n", gn->text); | |
284 | list_delete (bestmatch); | |
285 | bestmatch = result; | |
286 | } | |
287 | if (currprec == rsltprec) { | |
288 | fprintf(stderr, ">> Ambiguous match. Abort.\n"); | |
289 | list_delete (bestmatch); | |
290 | list_delete (result); | |
291 | list_delete (argv); | |
292 | return NULL; | |
293 | } | |
294 | } | |
295 | else { | |
296 | bestmatch = result; | |
297 | for (unsigned int i = 0; i < n; i++) fprintf(stderr, "\t"); | |
298 | fprintf(stderr, ">> Setting bestmatch with: %s\n", gn->text); | |
299 | } | |
300 | } | |
eceb1066 | 301 | } |
76699ae7 QY |
302 | |
303 | if (bestmatch) { | |
304 | list_add_list(argv, bestmatch); | |
305 | list_delete (bestmatch); | |
306 | start->arg = XSTRDUP(MTYPE_CMD_TOKENS, vector_slot(vline, n)); | |
307 | if (start->type == VARIABLE_GN) | |
308 | fprintf(stderr, "Setting variable %s->arg with text %s\n", start->text, start->arg); | |
309 | return argv; | |
310 | } | |
311 | else { | |
312 | list_delete (argv); | |
313 | return NULL; | |
eceb1066 | 314 | } |
eceb1066 | 315 | } |
18be0e59 | 316 | |
880e24a1 QY |
317 | /* matching utility functions */ |
318 | ||
76699ae7 QY |
319 | static int |
320 | score_precedence (struct graph_node *node) | |
321 | { | |
322 | switch (node->type) | |
323 | { | |
324 | // these should be mutually exclusive | |
325 | case IPV4_GN: | |
326 | case IPV4_PREFIX_GN: | |
327 | case IPV6_GN: | |
328 | case IPV6_PREFIX_GN: | |
329 | case RANGE_GN: | |
330 | case NUMBER_GN: | |
331 | return 1; | |
332 | case WORD_GN: | |
333 | return 2; | |
334 | case VARIABLE_GN: | |
335 | return 3; | |
336 | default: | |
337 | return 10; | |
338 | } | |
339 | } | |
340 | ||
880e24a1 QY |
341 | static enum match_type |
342 | match_token (struct graph_node *node, char *token, enum filter_type filter) | |
343 | { | |
344 | switch (node->type) { | |
345 | case WORD_GN: | |
eceb1066 | 346 | return match_word (node, filter, token); |
880e24a1 | 347 | case IPV4_GN: |
eceb1066 | 348 | return match_ipv4 (token); |
880e24a1 | 349 | case IPV4_PREFIX_GN: |
eceb1066 | 350 | return match_ipv4_prefix (token); |
880e24a1 | 351 | case IPV6_GN: |
eceb1066 | 352 | return match_ipv6 (token); |
880e24a1 | 353 | case IPV6_PREFIX_GN: |
eceb1066 | 354 | return match_ipv6_prefix (token); |
880e24a1 | 355 | case RANGE_GN: |
eceb1066 | 356 | return match_range (node, token); |
880e24a1 | 357 | case NUMBER_GN: |
eceb1066 | 358 | return match_number (node, token); |
880e24a1 | 359 | case VARIABLE_GN: |
eceb1066 QY |
360 | return match_variable (node, token); |
361 | case END_GN: | |
880e24a1 QY |
362 | default: |
363 | return no_match; | |
364 | } | |
9d0662e0 QY |
365 | } |
366 | ||
9d0662e0 QY |
367 | #define IPV4_ADDR_STR "0123456789." |
368 | #define IPV4_PREFIX_STR "0123456789./" | |
369 | ||
880e24a1 | 370 | static enum match_type |
eceb1066 | 371 | match_ipv4 (const char *str) |
9d0662e0 QY |
372 | { |
373 | struct sockaddr_in sin_dummy; | |
374 | ||
375 | if (str == NULL) | |
376 | return partly_match; | |
377 | ||
378 | if (strspn (str, IPV4_ADDR_STR) != strlen (str)) | |
379 | return no_match; | |
380 | ||
381 | if (inet_pton(AF_INET, str, &sin_dummy.sin_addr) != 1) | |
382 | return no_match; | |
383 | ||
384 | return exact_match; | |
385 | } | |
386 | ||
880e24a1 | 387 | static enum match_type |
eceb1066 | 388 | match_ipv4_prefix (const char *str) |
9d0662e0 QY |
389 | { |
390 | struct sockaddr_in sin_dummy; | |
391 | const char *delim = "/\0"; | |
392 | char *dupe, *prefix, *mask, *context, *endptr; | |
393 | int nmask = -1; | |
394 | ||
395 | if (str == NULL) | |
396 | return partly_match; | |
397 | ||
398 | if (strspn (str, IPV4_PREFIX_STR) != strlen (str)) | |
399 | return no_match; | |
400 | ||
401 | /* tokenize to address + mask */ | |
402 | dupe = XMALLOC(MTYPE_TMP, strlen(str)+1); | |
403 | strncpy(dupe, str, strlen(str)+1); | |
404 | prefix = strtok_r(dupe, delim, &context); | |
405 | mask = strtok_r(NULL, delim, &context); | |
406 | ||
407 | if (!mask) | |
408 | return partly_match; | |
409 | ||
410 | /* validate prefix */ | |
411 | if (inet_pton(AF_INET, prefix, &sin_dummy.sin_addr) != 1) | |
412 | return no_match; | |
413 | ||
414 | /* validate mask */ | |
415 | nmask = strtol (mask, &endptr, 10); | |
416 | if (*endptr != '\0' || nmask < 0 || nmask > 32) | |
417 | return no_match; | |
418 | ||
419 | XFREE(MTYPE_TMP, dupe); | |
420 | ||
421 | return exact_match; | |
422 | } | |
423 | ||
a53fbbf5 | 424 | #ifdef HAVE_IPV6 |
9d0662e0 QY |
425 | #define IPV6_ADDR_STR "0123456789abcdefABCDEF:." |
426 | #define IPV6_PREFIX_STR "0123456789abcdefABCDEF:./" | |
427 | ||
880e24a1 | 428 | static enum match_type |
eceb1066 | 429 | match_ipv6 (const char *str) |
9d0662e0 QY |
430 | { |
431 | struct sockaddr_in6 sin6_dummy; | |
432 | int ret; | |
433 | ||
434 | if (str == NULL) | |
435 | return partly_match; | |
436 | ||
437 | if (strspn (str, IPV6_ADDR_STR) != strlen (str)) | |
438 | return no_match; | |
439 | ||
440 | ret = inet_pton(AF_INET6, str, &sin6_dummy.sin6_addr); | |
441 | ||
442 | if (ret == 1) | |
443 | return exact_match; | |
444 | ||
445 | return no_match; | |
446 | } | |
447 | ||
880e24a1 | 448 | static enum match_type |
eceb1066 | 449 | match_ipv6_prefix (const char *str) |
9d0662e0 QY |
450 | { |
451 | struct sockaddr_in6 sin6_dummy; | |
452 | const char *delim = "/\0"; | |
453 | char *dupe, *prefix, *mask, *context, *endptr; | |
454 | int nmask = -1; | |
455 | ||
456 | if (str == NULL) | |
457 | return partly_match; | |
458 | ||
459 | if (strspn (str, IPV6_PREFIX_STR) != strlen (str)) | |
460 | return no_match; | |
461 | ||
462 | /* tokenize to address + mask */ | |
463 | dupe = XMALLOC(MTYPE_TMP, strlen(str)+1); | |
464 | strncpy(dupe, str, strlen(str)+1); | |
465 | prefix = strtok_r(dupe, delim, &context); | |
466 | mask = strtok_r(NULL, delim, &context); | |
467 | ||
468 | if (!mask) | |
469 | return partly_match; | |
470 | ||
471 | /* validate prefix */ | |
472 | if (inet_pton(AF_INET6, prefix, &sin6_dummy.sin6_addr) != 1) | |
473 | return no_match; | |
474 | ||
475 | /* validate mask */ | |
476 | nmask = strtol (mask, &endptr, 10); | |
477 | if (*endptr != '\0' || nmask < 0 || nmask > 128) | |
478 | return no_match; | |
479 | ||
480 | XFREE(MTYPE_TMP, dupe); | |
481 | ||
482 | return exact_match; | |
483 | } | |
484 | #endif | |
485 | ||
880e24a1 | 486 | static enum match_type |
eceb1066 | 487 | match_range (struct graph_node *rangenode, const char *str) |
9d0662e0 QY |
488 | { |
489 | char *endptr = NULL; | |
eceb1066 | 490 | signed long val; |
9d0662e0 QY |
491 | |
492 | if (str == NULL) | |
493 | return 1; | |
494 | ||
495 | val = strtoll (str, &endptr, 10); | |
496 | if (*endptr != '\0') | |
497 | return 0; | |
498 | val = llabs(val); | |
499 | ||
500 | if (val < rangenode->min || val > rangenode->max) | |
501 | return no_match; | |
502 | else | |
503 | return exact_match; | |
504 | } | |
505 | ||
880e24a1 | 506 | static enum match_type |
eceb1066 QY |
507 | match_word(struct graph_node *wordnode, |
508 | enum filter_type filter, | |
509 | const char *word) | |
9d0662e0 QY |
510 | { |
511 | if (filter == FILTER_RELAXED) | |
a53fbbf5 | 512 | { |
9d0662e0 QY |
513 | if (!word || !strlen(word)) |
514 | return partly_match; | |
a53fbbf5 QY |
515 | else if (!strncmp(wordnode->text, word, strlen(word))) |
516 | return !strcmp(wordnode->text, word) ? exact_match : partly_match; | |
517 | else | |
518 | return no_match; | |
519 | } | |
520 | else | |
9d0662e0 | 521 | { |
a53fbbf5 QY |
522 | if (!word) |
523 | return no_match; | |
524 | else | |
525 | return !strcmp(wordnode->text, word) ? exact_match : no_match; | |
9d0662e0 | 526 | } |
a53fbbf5 | 527 | } |
9d0662e0 | 528 | |
eceb1066 QY |
529 | static enum match_type |
530 | match_number(struct graph_node *numnode, const char *word) | |
a53fbbf5 QY |
531 | { |
532 | if (!strcmp("\0", word)) return no_match; | |
533 | char *endptr; | |
534 | long num = strtol(word, &endptr, 10); | |
535 | if (endptr != '\0') return no_match; | |
536 | return num == numnode->value ? exact_match : no_match; | |
537 | } | |
538 | ||
eceb1066 | 539 | #define VARIABLE_ALPHABET "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890" |
a53fbbf5 | 540 | |
eceb1066 QY |
541 | static enum match_type |
542 | match_variable(struct graph_node *varnode, const char *word) | |
a53fbbf5 | 543 | { |
eceb1066 QY |
544 | return strlen(word) == strspn(word, VARIABLE_ALPHABET) && isalpha(word[0]) ? |
545 | exact_match : no_match; | |
9d0662e0 | 546 | } |