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