2 * Command format string parser for CLI backend.
5 * Copyright (C) 2016 Cumulus Networks, Inc.
7 * This file is part of GNU Zebra.
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
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.
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
26 // compile with debugging facilities
31 /* define parse.error verbose */
33 /* define api.prefix {cmd_yy} */
35 /* names for generated header and parser files */
36 %defines "command_parse.h"
37 %output "command_parse.c"
39 /* note: code blocks are output in order, to both .c and .h:
41 * 2. %union + bison forward decls
43 * command_lex.h needs to be included at 3.; it needs the union and YYSTYPE.
44 * struct parser_ctx is needed for the bison forward decls.
53 #define YYSTYPE CMD_YYSTYPE
54 #define YYLTYPE CMD_YYLTYPE
57 /* subgraph semantic value */
59 struct graph_node *start, *end;
66 struct graph_node *node;
67 struct subgraph subgraph;
72 #include "command_lex.h"
75 extern void set_lexer_string (yyscan_t *scn, const char *string);
76 extern void cleanup_lexer (yyscan_t *scn);
81 struct cmd_element *el;
84 struct graph_node *currnode;
86 /* pointers to copy of command docstring */
87 char *docstr_start, *docstr;
91 /* union types for lexed tokens */
94 %token <string> IPV4_PREFIX
96 %token <string> IPV6_PREFIX
97 %token <string> VARIABLE
100 /* union types for parsed rules */
102 %type <node> literal_token
103 %type <node> placeholder_token
104 %type <node> simple_token
105 %type <subgraph> selector
106 %type <subgraph> selector_token
107 %type <subgraph> selector_token_seq
108 %type <subgraph> selector_seq_seq
112 /* bison declarations */
114 cmd_yyerror (CMD_YYLTYPE *locp, struct parser_ctx *ctx, char const *msg);
116 /* helper functions for parser */
118 doc_next (struct parser_ctx *ctx);
120 static struct graph_node *
121 node_adjacent (struct graph_node *, struct graph_node *);
123 static struct graph_node *
124 add_edge_dedup (struct graph_node *, struct graph_node *);
127 cmp_token (struct cmd_token *, struct cmd_token *);
129 static struct graph_node *
130 new_token_node (struct parser_ctx *,
131 enum cmd_token_type type,
136 terminate_graph (CMD_YYLTYPE *locp, struct parser_ctx *ctx,
137 struct graph_node *);
140 cleanup (struct parser_ctx *ctx);
142 #define scanner ctx->scanner
145 /* yyparse parameters */
146 %lex-param {yyscan_t scanner}
147 %parse-param {struct parser_ctx *ctx}
149 /* called automatically before yyparse */
151 /* clear state pointers */
152 ctx->currnode = vector_slot (ctx->graph->nodes, 0);
154 /* copy docstring and keep a pointer to the copy */
157 // allocate a new buffer, making room for a flag
158 size_t length = (size_t) strlen (ctx->el->doc) + 2;
159 ctx->docstr = malloc (length);
160 memcpy (ctx->docstr, ctx->el->doc, strlen (ctx->el->doc));
161 // set the flag so doc_next knows when to print a warning
162 ctx->docstr[length - 2] = 0x03;
164 ctx->docstr[length - 1] = 0x00;
166 ctx->docstr_start = ctx->docstr;
174 // tack on the command element
175 terminate_graph (&@1, ctx, ctx->currnode);
177 | cmd_token_seq placeholder_token '.' '.' '.'
179 if ((ctx->currnode = add_edge_dedup (ctx->currnode, $2)) != $2)
180 graph_delete_node (ctx->graph, $2);
182 ((struct cmd_token *)ctx->currnode->data)->allowrepeat = 1;
184 // adding a node as a child of itself accepts any number
185 // of the same token, which is what we want for variadics
186 add_edge_dedup (ctx->currnode, ctx->currnode);
188 // tack on the command element
189 terminate_graph (&@1, ctx, ctx->currnode);
195 | cmd_token_seq cmd_token
201 if ((ctx->currnode = add_edge_dedup (ctx->currnode, $1)) != $1)
202 graph_delete_node (ctx->graph, $1);
206 graph_add_edge (ctx->currnode, $1.start);
207 ctx->currnode = $1.end;
218 $$ = new_token_node (ctx, WORD_TKN, $1, doc_next(ctx));
226 $$ = new_token_node (ctx, IPV4_TKN, $1, doc_next(ctx));
231 $$ = new_token_node (ctx, IPV4_PREFIX_TKN, $1, doc_next(ctx));
236 $$ = new_token_node (ctx, IPV6_TKN, $1, doc_next(ctx));
241 $$ = new_token_node (ctx, IPV6_PREFIX_TKN, $1, doc_next(ctx));
246 $$ = new_token_node (ctx, VARIABLE_TKN, $1, doc_next(ctx));
251 $$ = new_token_node (ctx, RANGE_TKN, $1, doc_next(ctx));
252 struct cmd_token *token = $$->data;
254 // get the numbers out
256 token->min = strtoll (yylval.string, &yylval.string, 10);
257 strsep (&yylval.string, "-");
258 token->max = strtoll (yylval.string, &yylval.string, 10);
261 if (token->min > token->max) cmd_yyerror (&@1, ctx, "Invalid range.");
266 /* <selector|set> productions */
267 selector: '<' selector_seq_seq '>'
273 selector_seq_seq '|' selector_token_seq
276 graph_add_edge ($$.start, $3.start);
277 graph_add_edge ($3.end, $$.end);
281 $$.start = new_token_node (ctx, FORK_TKN, NULL, NULL);
282 $$.end = new_token_node (ctx, JOIN_TKN, NULL, NULL);
283 ((struct cmd_token *)$$.start->data)->forkjoin = $$.end;
284 ((struct cmd_token *)$$.end->data)->forkjoin = $$.start;
286 graph_add_edge ($$.start, $1.start);
287 graph_add_edge ($1.end, $$.end);
291 /* {keyword} productions */
292 selector: '{' selector_seq_seq '}'
295 graph_add_edge ($$.end, $$.start);
296 /* there is intentionally no start->end link, for two reasons:
297 * 1) this allows "at least 1 of" semantics, which are otherwise impossible
298 * 2) this would add a start->end->start loop in the graph that the current
299 * loop-avoidal fails to handle
300 * just use [{a|b}] if neccessary, that will work perfectly fine, and reason
301 * #1 is good enough to keep it this way. */
308 $$.start = $$.end = $1;
314 selector_token_seq selector_token
316 graph_add_edge ($1.end, $2.start);
323 /* [option] productions */
324 selector: '[' selector_seq_seq ']'
327 graph_add_edge ($$.start, $$.end);
336 command_parse_format (struct graph *graph, struct cmd_element *cmd)
338 struct parser_ctx ctx = { .graph = graph, .el = cmd };
340 // set to 1 to enable parser traces
343 set_lexer_string (&ctx.scanner, cmd->string);
345 // parse command into DFA
349 cleanup_lexer (&ctx.scanner);
355 /* parser helper functions */
358 yyerror (CMD_YYLTYPE *loc, struct parser_ctx *ctx, char const *msg)
360 char *tmpstr = strdup(ctx->el->string);
365 zlog_err ("%s: FATAL parse error: %s", __func__, msg);
366 zlog_err ("%s: %d:%d-%d of this command definition:", __func__, loc->first_line, loc->first_column, loc->last_column);
371 eol = strchr(line, '\n');
375 zlog_err ("%s: | %s", __func__, line);
376 if (lineno == loc->first_line && lineno == loc->last_line
377 && loc->first_column < (int)sizeof(spacing) - 1
378 && loc->last_column < (int)sizeof(spacing) - 1) {
380 int len = loc->last_column - loc->first_column;
384 memset(spacing, ' ', loc->first_column - 1);
385 memset(spacing + loc->first_column - 1, '^', len);
386 spacing[loc->first_column - 1 + len] = '\0';
387 zlog_err ("%s: | %s", __func__, spacing);
389 } while ((line = eol));
394 cleanup (struct parser_ctx *ctx)
397 free (ctx->docstr_start);
399 /* clear state pointers */
400 ctx->currnode = NULL;
401 ctx->docstr_start = ctx->docstr = NULL;
405 terminate_graph (CMD_YYLTYPE *locp, struct parser_ctx *ctx,
406 struct graph_node *finalnode)
408 // end of graph should look like this
409 // * -> finalnode -> END_TKN -> cmd_element
410 struct cmd_element *element = ctx->el;
411 struct graph_node *end_token_node =
412 new_token_node (ctx, END_TKN, CMD_CR_TEXT, "");
413 struct graph_node *end_element_node =
414 graph_new_node (ctx->graph, element, NULL);
416 if (node_adjacent (finalnode, end_token_node))
417 cmd_yyerror (locp, ctx, "Duplicate command.");
419 graph_add_edge (finalnode, end_token_node);
420 graph_add_edge (end_token_node, end_element_node);
424 doc_next (struct parser_ctx *ctx)
426 const char *piece = ctx->docstr ? strsep (&ctx->docstr, "\n") : "";
429 zlog_debug ("Ran out of docstring while parsing '%s'", ctx->el->string);
436 static struct graph_node *
437 new_token_node (struct parser_ctx *ctx, enum cmd_token_type type,
438 const char *text, const char *doc)
440 struct cmd_token *token = new_cmd_token (type, ctx->el->attr, text, doc);
441 return graph_new_node (ctx->graph, token, (void (*)(void *)) &del_cmd_token);
445 * Determines if there is an out edge from the first node to the second
447 static struct graph_node *
448 node_adjacent (struct graph_node *first, struct graph_node *second)
450 struct graph_node *adj;
451 for (unsigned int i = 0; i < vector_active (first->to); i++)
453 adj = vector_slot (first->to, i);
454 struct cmd_token *ftok = adj->data,
455 *stok = second->data;
456 if (cmp_token (ftok, stok))
463 * Creates an edge betwen two nodes, unless there is already an edge to an
466 * The first node's out edges are searched to see if any of them point to a
467 * node that is equivalent to the second node. If such a node exists, it is
468 * returned. Otherwise an edge is created from the first node to the second.
470 * @param from start node for edge
471 * @param to end node for edge
472 * @return the node which the new edge points to
474 static struct graph_node *
475 add_edge_dedup (struct graph_node *from, struct graph_node *to)
477 struct graph_node *existing = node_adjacent (from, to);
480 struct cmd_token *ex_tok = existing->data;
481 struct cmd_token *to_tok = to->data;
482 // NORMAL takes precedence over DEPRECATED takes precedence over HIDDEN
483 ex_tok->attr = (ex_tok->attr < to_tok->attr) ? ex_tok->attr : to_tok->attr;
487 return graph_add_edge (from, to);
491 * Compares two cmd_token's for equality,
493 * As such, this function is the working definition of token equality
494 * for parsing purposes and determines overall graph structure.
497 cmp_token (struct cmd_token *first, struct cmd_token *second)
500 if (first->type != second->type) return 0;
502 switch (first->type) {
505 if (first->text && second->text)
507 if (strcmp (first->text, second->text))
510 else if (first->text != second->text) return 0;
513 if (first->min != second->min || first->max != second->max)
516 /* selectors and options should be equal if their subgraphs are equal,
517 * but the graph isomorphism problem is not known to be solvable in
518 * polynomial time so we consider selectors and options inequal in all
519 * cases; ultimately this forks the graph, but the matcher can handle
525 /* end nodes are always considered equal, since each node may only
526 * have one END_TKN child at a time