1 /* 2 * Command format string parser 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 %{ 26 // compile with debugging facilities 27 #define YYDEBUG 1 28 %} 29 30 %locations 31 /* define parse.error verbose */ 32 %define api.pure full 33 /* define api.prefix {cmd_yy} */ 34 35 /* names for generated header and parser files */ 36 %defines "lib/command_parse.h" 37 %output "lib/command_parse.c" 38 39 /* note: code blocks are output in order, to both .c and .h: 40 * 1. %code requires 41 * 2. %union + bison forward decls 42 * 3. %code provides 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. 45 */ 46 %code requires { 47 #include "config.h" 48 49 #include <stdbool.h> 50 #include <stdlib.h> 51 #include <string.h> 52 #include <ctype.h> 53 54 #include "command_graph.h" 55 #include "log.h" 56 57 DECLARE_MTYPE(LEX) 58 59 #define YYSTYPE CMD_YYSTYPE 60 #define YYLTYPE CMD_YYLTYPE 61 struct parser_ctx; 62 63 /* subgraph semantic value */ 64 struct subgraph { 65 struct graph_node *start, *end; 66 }; 67 } 68 69 %union { 70 long long number; 71 char *string; 72 struct graph_node *node; 73 struct subgraph subgraph; 74 } 75 76 %code provides { 77 #ifndef FLEX_SCANNER 78 #include "command_lex.h" 79 #endif 80 81 extern void set_lexer_string (yyscan_t *scn, const char *string); 82 extern void cleanup_lexer (yyscan_t *scn); 83 84 struct parser_ctx { 85 yyscan_t scanner; 86 87 const struct cmd_element *el; 88 89 struct graph *graph; 90 struct graph_node *currnode; 91 92 /* pointers to copy of command docstring */ 93 char *docstr_start, *docstr; 94 }; 95 } 96 97 /* union types for lexed tokens */ 98 %token <string> WORD 99 %token <string> IPV4 100 %token <string> IPV4_PREFIX 101 %token <string> IPV6 102 %token <string> IPV6_PREFIX 103 %token <string> VARIABLE 104 %token <string> RANGE 105 %token <string> MAC 106 %token <string> MAC_PREFIX 107 108 /* union types for parsed rules */ 109 %type <node> start 110 %type <node> literal_token 111 %type <node> placeholder_token 112 %type <node> placeholder_token_real 113 %type <node> simple_token 114 %type <subgraph> selector 115 %type <subgraph> selector_token 116 %type <subgraph> selector_token_seq 117 %type <subgraph> selector_seq_seq 118 119 %type <string> varname_token 120 121 %code { 122 123 /* bison declarations */ 124 void 125 cmd_yyerror (CMD_YYLTYPE *locp, struct parser_ctx *ctx, char const *msg); 126 127 /* helper functions for parser */ 128 static const char * 129 doc_next (struct parser_ctx *ctx); 130 131 static struct graph_node * 132 new_token_node (struct parser_ctx *, 133 enum cmd_token_type type, 134 const char *text, 135 const char *doc); 136 137 static void 138 terminate_graph (CMD_YYLTYPE *locp, struct parser_ctx *ctx, 139 struct graph_node *); 140 141 static void 142 cleanup (struct parser_ctx *ctx); 143 144 static void loopcheck(struct parser_ctx *ctx, struct subgraph *sg); 145 146 #define scanner ctx->scanner 147 } 148 149 /* yyparse parameters */ 150 %lex-param {yyscan_t scanner} 151 %parse-param {struct parser_ctx *ctx} 152 153 /* called automatically before yyparse */ 154 %initial-action { 155 /* clear state pointers */ 156 ctx->currnode = vector_slot (ctx->graph->nodes, 0); 157 158 /* copy docstring and keep a pointer to the copy */ 159 if (ctx->el->doc) 160 { 161 // allocate a new buffer, making room for a flag 162 size_t length = (size_t) strlen (ctx->el->doc) + 2; 163 ctx->docstr = malloc (length); 164 memcpy (ctx->docstr, ctx->el->doc, strlen (ctx->el->doc)); 165 // set the flag so doc_next knows when to print a warning 166 ctx->docstr[length - 2] = 0x03; 167 // null terminate 168 ctx->docstr[length - 1] = 0x00; 169 } 170 ctx->docstr_start = ctx->docstr; 171 } 172 173 %% 174 175 start: 176 cmd_token_seq 177 { 178 // tack on the command element 179 terminate_graph (&@1, ctx, ctx->currnode); 180 } 181 | cmd_token_seq placeholder_token '.' '.' '.' 182 { 183 if ((ctx->currnode = graph_add_edge (ctx->currnode, $2)) != $2) 184 graph_delete_node (ctx->graph, $2); 185 186 ((struct cmd_token *)ctx->currnode->data)->allowrepeat = 1; 187 188 // adding a node as a child of itself accepts any number 189 // of the same token, which is what we want for variadics 190 graph_add_edge (ctx->currnode, ctx->currnode); 191 192 // tack on the command element 193 terminate_graph (&@1, ctx, ctx->currnode); 194 } 195 ; 196 197 varname_token: '$' WORD 198 { 199 $$ = $2; 200 } 201 | /* empty */ 202 { 203 $$ = NULL; 204 } 205 ; 206 207 cmd_token_seq: 208 /* empty */ 209 | cmd_token_seq cmd_token 210 ; 211 212 cmd_token: 213 simple_token 214 { 215 if ((ctx->currnode = graph_add_edge (ctx->currnode, $1)) != $1) 216 graph_delete_node (ctx->graph, $1); 217 } 218 | selector 219 { 220 graph_add_edge (ctx->currnode, $1.start); 221 ctx->currnode = $1.end; 222 } 223 ; 224 225 simple_token: 226 literal_token 227 | placeholder_token 228 ; 229 230 literal_token: WORD varname_token 231 { 232 $$ = new_token_node (ctx, WORD_TKN, $1, doc_next(ctx)); 233 cmd_token_varname_set ($$->data, $2); 234 XFREE (MTYPE_LEX, $2); 235 XFREE (MTYPE_LEX, $1); 236 } 237 ; 238 239 placeholder_token_real: 240 IPV4 241 { 242 $$ = new_token_node (ctx, IPV4_TKN, $1, doc_next(ctx)); 243 XFREE (MTYPE_LEX, $1); 244 } 245 | IPV4_PREFIX 246 { 247 $$ = new_token_node (ctx, IPV4_PREFIX_TKN, $1, doc_next(ctx)); 248 XFREE (MTYPE_LEX, $1); 249 } 250 | IPV6 251 { 252 $$ = new_token_node (ctx, IPV6_TKN, $1, doc_next(ctx)); 253 XFREE (MTYPE_LEX, $1); 254 } 255 | IPV6_PREFIX 256 { 257 $$ = new_token_node (ctx, IPV6_PREFIX_TKN, $1, doc_next(ctx)); 258 XFREE (MTYPE_LEX, $1); 259 } 260 | VARIABLE 261 { 262 $$ = new_token_node (ctx, VARIABLE_TKN, $1, doc_next(ctx)); 263 XFREE (MTYPE_LEX, $1); 264 } 265 | RANGE 266 { 267 $$ = new_token_node (ctx, RANGE_TKN, $1, doc_next(ctx)); 268 struct cmd_token *token = $$->data; 269 270 // get the numbers out 271 yylval.string++; 272 token->min = strtoll (yylval.string, &yylval.string, 10); 273 strsep (&yylval.string, "-"); 274 token->max = strtoll (yylval.string, &yylval.string, 10); 275 276 // validate range 277 if (token->min > token->max) cmd_yyerror (&@1, ctx, "Invalid range."); 278 279 XFREE (MTYPE_LEX, $1); 280 } 281 | MAC 282 { 283 $$ = new_token_node (ctx, MAC_TKN, $1, doc_next(ctx)); 284 XFREE (MTYPE_LEX, $1); 285 } 286 | MAC_PREFIX 287 { 288 $$ = new_token_node (ctx, MAC_PREFIX_TKN, $1, doc_next(ctx)); 289 XFREE (MTYPE_LEX, $1); 290 } 291 292 placeholder_token: 293 placeholder_token_real varname_token 294 { 295 struct cmd_token *token = $$->data; 296 $$ = $1; 297 cmd_token_varname_set (token, $2); 298 XFREE (MTYPE_LEX, $2); 299 }; 300 301 302 /* <selector|set> productions */ 303 selector: '<' selector_seq_seq '>' varname_token 304 { 305 $$ = $2; 306 cmd_token_varname_set ($2.end->data, $4); 307 XFREE (MTYPE_LEX, $4); 308 }; 309 310 selector_seq_seq: 311 selector_seq_seq '|' selector_token_seq 312 { 313 $$ = $1; 314 graph_add_edge ($$.start, $3.start); 315 graph_add_edge ($3.end, $$.end); 316 } 317 | selector_token_seq 318 { 319 $$.start = new_token_node (ctx, FORK_TKN, NULL, NULL); 320 $$.end = new_token_node (ctx, JOIN_TKN, NULL, NULL); 321 ((struct cmd_token *)$$.start->data)->forkjoin = $$.end; 322 ((struct cmd_token *)$$.end->data)->forkjoin = $$.start; 323 324 graph_add_edge ($$.start, $1.start); 325 graph_add_edge ($1.end, $$.end); 326 } 327 ; 328 329 /* {keyword} productions */ 330 selector: '{' selector_seq_seq '}' varname_token 331 { 332 $$ = $2; 333 graph_add_edge ($$.end, $$.start); 334 /* there is intentionally no start->end link, for two reasons: 335 * 1) this allows "at least 1 of" semantics, which are otherwise impossible 336 * 2) this would add a start->end->start loop in the graph that the current 337 * loop-avoidal fails to handle 338 * just use [{a|b}] if neccessary, that will work perfectly fine, and reason 339 * #1 is good enough to keep it this way. */ 340 341 loopcheck(ctx, &$$); 342 cmd_token_varname_set ($2.end->data, $4); 343 XFREE (MTYPE_LEX, $4); 344 }; 345 346 347 selector_token: 348 simple_token 349 { 350 $$.start = $$.end = $1; 351 } 352 | selector 353 ; 354 355 selector_token_seq: 356 selector_token_seq selector_token 357 { 358 graph_add_edge ($1.end, $2.start); 359 $$.start = $1.start; 360 $$.end = $2.end; 361 } 362 | selector_token 363 ; 364 365 /* [option] productions */ 366 selector: '[' selector_seq_seq ']' varname_token 367 { 368 $$ = $2; 369 graph_add_edge ($$.start, $$.end); 370 cmd_token_varname_set ($2.end->data, $4); 371 XFREE (MTYPE_LEX, $4); 372 } 373 ; 374 375 %% 376 377 #undef scanner 378 379 DEFINE_MTYPE(LIB, LEX, "Lexer token (temporary)") 380 381 void 382 cmd_graph_parse (struct graph *graph, const struct cmd_element *cmd) 383 { 384 struct parser_ctx ctx = { .graph = graph, .el = cmd }; 385 386 // set to 1 to enable parser traces 387 yydebug = 0; 388 389 set_lexer_string (&ctx.scanner, cmd->string); 390 391 // parse command into DFA 392 cmd_yyparse (&ctx); 393 394 /* cleanup lexer */ 395 cleanup_lexer (&ctx.scanner); 396 397 // cleanup 398 cleanup (&ctx); 399 } 400 401 /* parser helper functions */ 402 403 static bool loopcheck_inner(struct graph_node *start, struct graph_node *node, 404 struct graph_node *end, size_t depth) 405 { 406 size_t i; 407 bool ret; 408 409 /* safety check */ 410 if (depth++ == 64) 411 return true; 412 413 for (i = 0; i < vector_active(node->to); i++) { 414 struct graph_node *next = vector_slot(node->to, i); 415 struct cmd_token *tok = next->data; 416 417 if (next == end || next == start) 418 return true; 419 if (tok->type < SPECIAL_TKN) 420 continue; 421 ret = loopcheck_inner(start, next, end, depth); 422 if (ret) 423 return true; 424 } 425 return false; 426 } 427 428 static void loopcheck(struct parser_ctx *ctx, struct subgraph *sg) 429 { 430 if (loopcheck_inner(sg->start, sg->start, sg->end, 0)) 431 zlog_err("FATAL: '%s': {} contains an empty path! Use [{...}]", 432 ctx->el->string); 433 } 434 435 void 436 yyerror (CMD_YYLTYPE *loc, struct parser_ctx *ctx, char const *msg) 437 { 438 char *tmpstr = strdup(ctx->el->string); 439 char *line, *eol; 440 char spacing[256]; 441 int lineno = 0; 442 443 zlog_notice ("%s: FATAL parse error: %s", __func__, msg); 444 zlog_notice ("%s: %d:%d-%d of this command definition:", __func__, loc->first_line, loc->first_column, loc->last_column); 445 446 line = tmpstr; 447 do { 448 lineno++; 449 eol = strchr(line, '\n'); 450 if (eol) 451 *eol++ = '\0'; 452 453 zlog_notice ("%s: | %s", __func__, line); 454 if (lineno == loc->first_line && lineno == loc->last_line 455 && loc->first_column < (int)sizeof(spacing) - 1 456 && loc->last_column < (int)sizeof(spacing) - 1) { 457 458 int len = loc->last_column - loc->first_column; 459 if (len == 0) 460 len = 1; 461 462 memset(spacing, ' ', loc->first_column - 1); 463 memset(spacing + loc->first_column - 1, '^', len); 464 spacing[loc->first_column - 1 + len] = '\0'; 465 zlog_notice ("%s: | %s", __func__, spacing); 466 } 467 } while ((line = eol)); 468 free(tmpstr); 469 } 470 471 static void 472 cleanup (struct parser_ctx *ctx) 473 { 474 /* free resources */ 475 free (ctx->docstr_start); 476 477 /* clear state pointers */ 478 ctx->currnode = NULL; 479 ctx->docstr_start = ctx->docstr = NULL; 480 } 481 482 static void 483 terminate_graph (CMD_YYLTYPE *locp, struct parser_ctx *ctx, 484 struct graph_node *finalnode) 485 { 486 // end of graph should look like this 487 // * -> finalnode -> END_TKN -> cmd_element 488 const struct cmd_element *element = ctx->el; 489 struct graph_node *end_token_node = 490 new_token_node (ctx, END_TKN, CMD_CR_TEXT, ""); 491 struct graph_node *end_element_node = 492 graph_new_node (ctx->graph, (void *)element, NULL); 493 494 if (ctx->docstr && strlen (ctx->docstr) > 1) { 495 zlog_debug ("Excessive docstring while parsing '%s'", ctx->el->string); 496 zlog_debug ("----------"); 497 while (ctx->docstr && ctx->docstr[1] != '\0') 498 zlog_debug ("%s", strsep(&ctx->docstr, "\n")); 499 zlog_debug ("----------\n"); 500 } 501 502 graph_add_edge (finalnode, end_token_node); 503 graph_add_edge (end_token_node, end_element_node); 504 } 505 506 static const char * 507 doc_next (struct parser_ctx *ctx) 508 { 509 const char *piece = ctx->docstr ? strsep (&ctx->docstr, "\n") : ""; 510 if (*piece == 0x03) 511 { 512 zlog_debug ("Ran out of docstring while parsing '%s'", ctx->el->string); 513 piece = ""; 514 } 515 516 return piece; 517 } 518 519 static struct graph_node * 520 new_token_node (struct parser_ctx *ctx, enum cmd_token_type type, 521 const char *text, const char *doc) 522 { 523 struct cmd_token *token = cmd_token_new (type, ctx->el->attr, text, doc); 524 return graph_new_node (ctx->graph, token, (void (*)(void *)) &cmd_token_del); 525 } 526