lib/command_parse.y

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