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