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