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