]>
Commit | Line | Data |
---|---|---|
9d0662e0 | 1 | /* |
1ab84bf3 | 2 | * Command format string parser for CLI backend. |
9d0662e0 | 3 | * |
1ab84bf3 QY |
4 | * -- |
5 | * Copyright (C) 2015 Cumulus Networks, Inc. | |
9d0662e0 | 6 | * |
1ab84bf3 QY |
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. | |
9d0662e0 QY |
23 | */ |
24 | ||
92055a92 | 25 | %{ |
1ab84bf3 QY |
26 | // compile with debugging facilities |
27 | #define YYDEBUG 1 | |
51fc9379 | 28 | %} |
782d9789 | 29 | |
51fc9379 QY |
30 | /* names for generated header and parser files */ |
31 | %defines "command_parse.h" | |
32 | %output "command_parse.c" | |
5a8bbed0 | 33 | |
51fc9379 | 34 | /* required external units */ |
eceb1066 QY |
35 | %code requires { |
36 | #include "command.h" | |
7a6ded40 | 37 | #include "graph.h" |
5a5d576b | 38 | #include "memory.h" |
51fc9379 QY |
39 | |
40 | extern int | |
1ab84bf3 | 41 | yylex (void); |
51fc9379 | 42 | |
eceb1066 | 43 | extern void |
4427e9b3 QY |
44 | set_lexer_string (const char *); |
45 | ||
46 | extern void | |
47 | cleanup_lexer (void); | |
51fc9379 QY |
48 | } |
49 | ||
50 | /* functionality this unit exports */ | |
51 | %code provides { | |
7a6ded40 QY |
52 | struct graph * |
53 | command_parse_format (struct graph *, struct cmd_element *); | |
92055a92 | 54 | |
51fc9379 QY |
55 | /* maximum length of a number, lexer will not match anything longer */ |
56 | #define DECIMAL_STRLEN_MAX 20 | |
57 | } | |
eceb1066 | 58 | |
51fc9379 QY |
59 | /* valid semantic types for tokens and rules */ |
60 | %union { | |
61 | long long number; | |
92055a92 | 62 | char *string; |
782d9789 | 63 | struct graph_node *node; |
92055a92 QY |
64 | } |
65 | ||
51fc9379 | 66 | /* union types for lexed tokens */ |
5a5d576b QY |
67 | %token <string> WORD |
68 | %token <string> IPV4 | |
69 | %token <string> IPV4_PREFIX | |
70 | %token <string> IPV6 | |
71 | %token <string> IPV6_PREFIX | |
72 | %token <string> VARIABLE | |
73 | %token <string> RANGE | |
51fc9379 | 74 | %token <number> NUMBER |
782d9789 | 75 | |
51fc9379 | 76 | /* union types for parsed rules */ |
782d9789 QY |
77 | %type <node> start |
78 | %type <node> sentence_root | |
782d9789 QY |
79 | %type <node> literal_token |
80 | %type <node> placeholder_token | |
782d9789 | 81 | %type <node> option |
478bdaeb QY |
82 | %type <node> option_token |
83 | %type <node> option_token_seq | |
782d9789 | 84 | %type <node> selector |
340a2b4a | 85 | %type <node> selector_element_root |
478bdaeb | 86 | %type <node> selector_token |
782d9789 | 87 | %type <node> selector_token_seq |
782d9789 | 88 | |
51fc9379 QY |
89 | %code { |
90 | /* bison declarations */ | |
91 | void | |
1ab84bf3 | 92 | yyerror (struct cmd_element *el, struct graph_node *sn, char const *msg); |
51fc9379 QY |
93 | |
94 | /* state variables for a single parser run */ | |
95 | struct graph_node *currnode, // current position in DFA | |
96 | *seqhead; // sequence head | |
97 | ||
98 | struct graph_node *optnode_start, // start node for option set | |
99 | *optnode_end; // end node for option set | |
100 | ||
101 | struct graph_node *selnode_start, // start node for selector set | |
102 | *selnode_end; // end node for selector set | |
103 | ||
104 | char *docstr_start, *docstr; // pointers to copy of command docstring | |
105 | ||
106 | /* helper functions for parser */ | |
107 | static char * | |
7a6ded40 | 108 | doc_next (void); |
51fc9379 QY |
109 | |
110 | static struct graph_node * | |
1ab84bf3 | 111 | node_exists (struct graph_node *, struct graph_node *); |
51fc9379 QY |
112 | |
113 | static struct graph_node * | |
1ab84bf3 | 114 | node_replace (struct graph_node *, struct graph_node *); |
51fc9379 QY |
115 | |
116 | static int | |
1ab84bf3 | 117 | cmp_node (struct graph_node *, struct graph_node *); |
51fc9379 QY |
118 | |
119 | static void | |
120 | terminate_graph (struct graph_node *, | |
121 | struct graph_node *, | |
122 | struct cmd_element *); | |
123 | ||
124 | static void | |
1ab84bf3 | 125 | cleanup (void); |
51fc9379 QY |
126 | } |
127 | ||
128 | /* yyparse parameters */ | |
129 | %parse-param { struct cmd_element *element } | |
7a6ded40 | 130 | %parse-param { struct graph *graph } |
51fc9379 QY |
131 | |
132 | /* called automatically before yyparse */ | |
133 | %initial-action { | |
134 | /* clear state pointers */ | |
135 | seqhead = NULL; | |
136 | currnode = NULL; | |
137 | selnode_start = selnode_end = NULL; | |
138 | optnode_start = optnode_end = NULL; | |
139 | ||
140 | /* set string to parse */ | |
4427e9b3 | 141 | set_lexer_string (element->string); |
51fc9379 QY |
142 | |
143 | /* copy docstring and keep a pointer to the copy */ | |
144 | docstr = element->doc ? XSTRDUP(MTYPE_TMP, element->doc) : NULL; | |
145 | docstr_start = docstr; | |
146 | } | |
92055a92 | 147 | |
92055a92 QY |
148 | %% |
149 | ||
88255c7c QY |
150 | start: |
151 | sentence_root cmd_token_seq | |
880e24a1 | 152 | { |
51fc9379 QY |
153 | // tack on the command element |
154 | terminate_graph (startnode, currnode, element); | |
880e24a1 | 155 | } |
88255c7c QY |
156 | | sentence_root cmd_token_seq '.' placeholder_token |
157 | { | |
1ab84bf3 | 158 | if ((currnode = node_replace (currnode, $4)) != $4) |
7a6ded40 | 159 | graph_delete_node ($4); |
88255c7c | 160 | |
1ab84bf3 QY |
161 | // adding a node as a child of itself accepts any number |
162 | // of the same token, which is what we want for varags | |
163 | node_replace (currnode, currnode); | |
88255c7c | 164 | |
51fc9379 QY |
165 | // tack on the command element |
166 | terminate_graph (startnode, currnode, element); | |
88255c7c | 167 | } |
92055a92 | 168 | |
2a23ca6e | 169 | sentence_root: WORD |
478bdaeb | 170 | { |
7a6ded40 QY |
171 | struct graph_node *root = |
172 | new_token_node (WORD_TKN, XSTRDUP(MTYPE_CMD_TOKENS, $1), doc_next()); | |
5a5d576b | 173 | |
1ab84bf3 | 174 | if ((currnode = node_replace (startnode, root)) != root) |
5a5d576b | 175 | free (root); |
4b0abf24 | 176 | |
5a5d576b QY |
177 | free ($1); |
178 | $$ = currnode; | |
478bdaeb | 179 | }; |
92055a92 | 180 | |
782d9789 QY |
181 | cmd_token: |
182 | placeholder_token | |
5a5d576b | 183 | { |
1ab84bf3 | 184 | if ((currnode = node_replace (currnode, $1)) != $1) |
7a6ded40 | 185 | graph_delete_node ($1); |
5a5d576b | 186 | } |
782d9789 | 187 | | literal_token |
5a5d576b | 188 | { |
1ab84bf3 | 189 | if ((currnode = node_replace (currnode, $1)) != $1) |
7a6ded40 | 190 | graph_delete_node ($1); |
5a5d576b | 191 | } |
478bdaeb | 192 | /* selectors and options are subgraphs with start and end nodes */ |
782d9789 | 193 | | selector |
478bdaeb | 194 | { |
7a6ded40 | 195 | graph_add_edge (currnode, $1); |
478bdaeb QY |
196 | currnode = selnode_end; |
197 | selnode_start = selnode_end = NULL; | |
198 | } | |
782d9789 | 199 | | option |
478bdaeb | 200 | { |
7a6ded40 | 201 | graph_add_edge (currnode, $1); |
478bdaeb QY |
202 | currnode = optnode_end; |
203 | optnode_start = optnode_end = NULL; | |
204 | } | |
782d9789 | 205 | ; |
92055a92 | 206 | |
782d9789 QY |
207 | cmd_token_seq: |
208 | %empty | |
209 | | cmd_token_seq cmd_token | |
210 | ; | |
211 | ||
212 | placeholder_token: | |
478bdaeb | 213 | IPV4 |
4b0abf24 | 214 | { |
7a6ded40 | 215 | $$ = new_token_node (IPV4_TKN, XSTRDUP(MTYPE_CMD_TOKENS, $1), doc_next()); |
5a5d576b | 216 | free ($1); |
4b0abf24 | 217 | } |
478bdaeb | 218 | | IPV4_PREFIX |
340a2b4a | 219 | { |
7a6ded40 | 220 | $$ = new_token_node (IPV4_PREFIX_TKN, XSTRDUP(MTYPE_CMD_TOKENS, $1), doc_next()); |
5a5d576b | 221 | free ($1); |
4b0abf24 | 222 | } |
478bdaeb | 223 | | IPV6 |
340a2b4a | 224 | { |
7a6ded40 | 225 | $$ = new_token_node (IPV6_TKN, XSTRDUP(MTYPE_CMD_TOKENS, $1), doc_next()); |
5a5d576b | 226 | free ($1); |
4b0abf24 | 227 | } |
478bdaeb | 228 | | IPV6_PREFIX |
340a2b4a | 229 | { |
7a6ded40 | 230 | $$ = new_token_node (IPV6_PREFIX_TKN, XSTRDUP(MTYPE_CMD_TOKENS, $1), doc_next()); |
5a5d576b | 231 | free ($1); |
4b0abf24 | 232 | } |
478bdaeb | 233 | | VARIABLE |
340a2b4a | 234 | { |
7a6ded40 | 235 | $$ = new_token_node (VARIABLE_TKN, XSTRDUP(MTYPE_CMD_TOKENS, $1), doc_next()); |
5a5d576b | 236 | free ($1); |
4b0abf24 | 237 | } |
478bdaeb QY |
238 | | RANGE |
239 | { | |
7a6ded40 QY |
240 | $$ = new_token_node (RANGE_TKN, XSTRDUP(MTYPE_CMD_TOKENS, $1), doc_next()); |
241 | cmd_token_t token = (cmd_token_t *) $$->data; | |
478bdaeb QY |
242 | |
243 | // get the numbers out | |
b3899769 | 244 | yylval.string++; |
7a6ded40 | 245 | token->min = strtoll (yylval.string, &yylval.string, 10); |
ef955a80 | 246 | strsep (&yylval.string, "-"); |
7a6ded40 | 247 | token->max = strtoll (yylval.string, &yylval.string, 10); |
ef955a80 QY |
248 | |
249 | // validate range | |
7a6ded40 | 250 | if (token->min >= token->max) yyerror (element, startnode, "Invalid range."); |
5a5d576b QY |
251 | |
252 | free ($1); | |
478bdaeb | 253 | } |
782d9789 QY |
254 | ; |
255 | ||
256 | literal_token: | |
478bdaeb QY |
257 | WORD |
258 | { | |
7a6ded40 | 259 | $$ = new_token_node (WORD_TKN, XSTRDUP(MTYPE_CMD_TOKENS, $1), doc_next()); |
5a5d576b | 260 | free ($1); |
478bdaeb QY |
261 | } |
262 | | NUMBER | |
263 | { | |
7a6ded40 QY |
264 | $$ = new_token_node (NUMBER_TKN, NULL, doc_next()); |
265 | cmd_token_t token = (cmd_token_t *) $$->data; | |
266 | ||
267 | token->value = yylval.number; | |
268 | token->text = XCALLOC(MTYPE_CMD_TOKENS, DECIMAL_STRLEN_MAX+1); | |
269 | snprintf(token->text, DECIMAL_STRLEN_MAX, "%lld", token->value); | |
478bdaeb | 270 | } |
782d9789 | 271 | ; |
92055a92 | 272 | |
4b0abf24 | 273 | /* <selector|set> productions */ |
51fc9379 | 274 | selector: '<' selector_part '>' |
2a23ca6e | 275 | { |
478bdaeb QY |
276 | // all the graph building is done in selector_element, |
277 | // so just return the selector subgraph head | |
278 | $$ = selnode_start; | |
2a23ca6e | 279 | }; |
782d9789 QY |
280 | |
281 | selector_part: | |
2a23ca6e | 282 | selector_part '|' selector_element |
f4b0c72e | 283 | | selector_element '|' selector_element |
782d9789 QY |
284 | ; |
285 | ||
51fc9379 | 286 | selector_element: selector_element_root selector_token_seq |
478bdaeb QY |
287 | { |
288 | // if the selector start and end do not exist, create them | |
7a6ded40 QY |
289 | if (!selnode_start || !selnode_end) { |
290 | assert(!selnode_start && !selnode_end); | |
291 | selnode_start = new_token_node (SELECTOR_TKN, NULL, NULL); | |
292 | selnode_end = new_token_node (NUL_TKN, NULL, NULL); | |
478bdaeb QY |
293 | } |
294 | ||
295 | // add element head as a child of the selector | |
7a6ded40 | 296 | graph_add_edge (selnode_start, $1); |
478bdaeb QY |
297 | |
298 | if ($2->type != NUL_GN) { | |
7a6ded40 QY |
299 | graph_add_edge ($1, seqhead); |
300 | graph_add_edge ($2, selnode_end); | |
478bdaeb QY |
301 | } |
302 | else | |
7a6ded40 | 303 | graph_add_edge ($1, selnode_end); |
478bdaeb QY |
304 | |
305 | seqhead = NULL; | |
306 | } | |
782d9789 QY |
307 | |
308 | selector_token_seq: | |
7a6ded40 | 309 | %empty { $$ = new_token_node (NUL_TKN, NULL, NULL); } |
2a23ca6e QY |
310 | | selector_token_seq selector_token |
311 | { | |
478bdaeb QY |
312 | // if the sequence component is NUL_GN, this is a sequence start |
313 | if ($1->type == NUL_GN) { | |
314 | assert(!seqhead); // sequence head should always be null here | |
315 | seqhead = $2; | |
316 | } | |
317 | else // chain on new node | |
7a6ded40 | 318 | graph_add_edge ($1, $2); |
478bdaeb QY |
319 | |
320 | $$ = $2; | |
2a23ca6e | 321 | } |
782d9789 QY |
322 | ; |
323 | ||
340a2b4a | 324 | selector_element_root: |
782d9789 QY |
325 | literal_token |
326 | | placeholder_token | |
478bdaeb QY |
327 | ; |
328 | ||
329 | selector_token: | |
340a2b4a | 330 | selector_element_root |
782d9789 | 331 | ; |
92055a92 QY |
332 | |
333 | /* [option|set] productions */ | |
2a23ca6e | 334 | option: '[' option_part ']' |
4b0abf24 QY |
335 | { |
336 | // add null path | |
7a6ded40 | 337 | graph_add_edge (optnode_start, optnode_end); |
4b0abf24 QY |
338 | $$ = optnode_start; |
339 | }; | |
782d9789 QY |
340 | |
341 | option_part: | |
478bdaeb QY |
342 | option_part '|' option_element |
343 | | option_element | |
782d9789 QY |
344 | ; |
345 | ||
478bdaeb QY |
346 | option_element: |
347 | option_token_seq | |
2a23ca6e | 348 | { |
478bdaeb QY |
349 | if (!optnode_start || !optnode_end) { |
350 | assert(!optnode_start && !optnode_end); | |
7a6ded40 QY |
351 | optnode_start = new_token_node (OPTION_TKN, NULL, NULL); |
352 | optnode_end = new_token_node (NUL_TKN, NULL, NULL); | |
478bdaeb QY |
353 | } |
354 | ||
7a6ded40 QY |
355 | graph_add_edge (optnode_start, seqhead); |
356 | graph_add_edge ($1, optnode_end); | |
4427e9b3 | 357 | seqhead = NULL; |
2a23ca6e | 358 | } |
478bdaeb QY |
359 | |
360 | option_token_seq: | |
361 | option_token | |
362 | { $$ = seqhead = $1; } | |
363 | | option_token_seq option_token | |
7a6ded40 | 364 | { $$ = graph_add_edge ($1, $2); } |
782d9789 QY |
365 | ; |
366 | ||
367 | option_token: | |
368 | literal_token | |
369 | | placeholder_token | |
370 | ; | |
371 | ||
92055a92 | 372 | %% |
4b0abf24 | 373 | |
51fc9379 | 374 | struct graph_node * |
55589d30 | 375 | command_parse_format (struct graph_node *start, struct cmd_element *cmd) |
51fc9379 | 376 | { |
1ab84bf3 | 377 | // set to 1 to enable parser traces |
51fc9379 QY |
378 | yydebug = 0; |
379 | ||
380 | // parse command into DFA | |
07079d78 QY |
381 | yyparse (cmd, start); |
382 | ||
7a6ded40 | 383 | // cleanup |
07079d78 | 384 | cleanup (); |
51fc9379 QY |
385 | |
386 | return start; | |
387 | } | |
388 | ||
389 | /* parser helper functions */ | |
390 | ||
391 | void | |
1ab84bf3 | 392 | yyerror (struct cmd_element *el, struct graph_node *sn, char const *msg) |
51fc9379 | 393 | { |
1ab84bf3 QY |
394 | zlog_err ("%s: FATAL parse error: %s", __func__, msg); |
395 | zlog_err ("while parsing this command definition: \n\t%s\n", el->string); | |
5a8bbed0 | 396 | exit(EXIT_FAILURE); |
92055a92 | 397 | } |
782d9789 | 398 | |
51fc9379 QY |
399 | static void |
400 | cleanup() | |
782d9789 | 401 | { |
51fc9379 QY |
402 | /* free resources */ |
403 | free (docstr_start); | |
478bdaeb | 404 | |
4427e9b3 | 405 | /* cleanup lexer */ |
07079d78 | 406 | cleanup_lexer (); |
4427e9b3 | 407 | |
4b0abf24 | 408 | /* clear state pointers */ |
51fc9379 QY |
409 | seqhead = NULL; |
410 | currnode = NULL; | |
411 | docstr_start = docstr = NULL; | |
4b0abf24 QY |
412 | selnode_start = selnode_end = NULL; |
413 | optnode_start = optnode_end = NULL; | |
51fc9379 | 414 | } |
4b0abf24 | 415 | |
51fc9379 QY |
416 | static void |
417 | terminate_graph (struct graph_node *startnode, | |
418 | struct graph_node *finalnode, | |
419 | struct cmd_element *element) | |
420 | { | |
7a6ded40 QY |
421 | struct graph_node *end = graph_new_node (graph, element, &cmd_delete_element); |
422 | ||
423 | if (node_adjacent (finalnode, end)) | |
1ab84bf3 | 424 | yyerror (element, startnode, "Duplicate command."); |
51fc9379 | 425 | else |
7a6ded40 | 426 | graph_add_edge (finalnode, end); |
782d9789 | 427 | } |
f4b0c72e | 428 | |
51fc9379 QY |
429 | static char * |
430 | doc_next() | |
431 | { | |
432 | char *piece = NULL; | |
1ab84bf3 | 433 | if (!docstr || !(piece = strsep (&docstr, "\n"))) |
51fc9379 QY |
434 | return NULL; |
435 | return XSTRDUP(MTYPE_CMD_TOKENS, piece); | |
436 | } | |
437 | ||
438 | static struct graph_node * | |
7a6ded40 QY |
439 | new_token_node (cmd_token_type_t type, char *text, char *doc) |
440 | { | |
441 | struct cmd_token_t *token = | |
442 | XMALLOC(MTYPE_CMD_TOKENS, sizeof (struct cmd_token_t)); | |
443 | ||
444 | token->type = type; | |
445 | token->text = text; | |
446 | token->desc = doc; | |
447 | ||
448 | return graph_new_node (graph, token, &cmd_delete_token); | |
449 | } | |
450 | ||
451 | /** | |
452 | * Determines if a node is adjacent to another node | |
453 | */ | |
454 | static struct graph_node * | |
455 | node_adjacent (struct graph_node *node, struct graph_node *neighbor) | |
f4b0c72e | 456 | { |
7a6ded40 QY |
457 | struct graph_node *adj; |
458 | for (unsigned int i = 0; i < vector_active (node->to); i++) | |
1ab84bf3 | 459 | { |
7a6ded40 QY |
460 | adj = vector_slot (node->to, i); |
461 | if (cmp_node (neighbor, adj)) | |
462 | return adj; | |
1ab84bf3 | 463 | } |
f4b0c72e QY |
464 | return NULL; |
465 | } | |
466 | ||
51fc9379 | 467 | static struct graph_node * |
1ab84bf3 | 468 | node_replace (struct graph_node *parent, struct graph_node *child) |
f4b0c72e | 469 | { |
7a6ded40 QY |
470 | struct graph_node *existing = node_adjacent (parent, child); |
471 | return existing ? existing : graph_add_edge (parent, child); | |
f4b0c72e | 472 | } |
0aa2c2ff | 473 | |
51fc9379 | 474 | static int |
7a6ded40 | 475 | cmp_token (struct cmd_token_t *first, struct cmd_token_t *second) |
0aa2c2ff | 476 | { |
7a6ded40 QY |
477 | struct cmd_token_t *first = (cmd_token *) firstgn->data; |
478 | struct cmd_token_t *second = (cmd_token *) secondgn->data; | |
479 | ||
51fc9379 QY |
480 | // compare types |
481 | if (first->type != second->type) return 0; | |
482 | ||
483 | switch (first->type) { | |
484 | case WORD_GN: | |
485 | case VARIABLE_GN: | |
e52c05cd QY |
486 | if (first->text && second->text) |
487 | { | |
488 | if (strcmp (first->text, second->text)) | |
489 | return 0; | |
490 | } | |
51fc9379 QY |
491 | else if (first->text != second->text) return 0; |
492 | break; | |
493 | case RANGE_GN: | |
494 | if (first->min != second->min || first->max != second->max) | |
495 | return 0; | |
496 | break; | |
497 | case NUMBER_GN: | |
498 | if (first->value != second->value) return 0; | |
499 | break; | |
55589d30 QY |
500 | /* selectors and options should be equal if their subgraphs are equal, |
501 | * but the graph isomorphism problem is not known to be solvable in | |
502 | * polynomial time so we consider selectors and options inequal in all | |
503 | * cases; ultimately this forks the graph, but the matcher can handle | |
504 | * this regardless | |
51fc9379 QY |
505 | */ |
506 | case SELECTOR_GN: | |
507 | case OPTION_GN: | |
508 | return 0; | |
509 | /* end nodes are always considered equal, since each node may only | |
1ab84bf3 | 510 | * have one END_GN child at a time |
51fc9379 QY |
511 | */ |
512 | case START_GN: | |
513 | case END_GN: | |
514 | case NUL_GN: | |
515 | default: | |
516 | break; | |
517 | } | |
518 | return 1; | |
0aa2c2ff | 519 | } |