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