lib/command_parse.y

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