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
  27 typedef union CMD_YYSTYPE CMD_YYSTYPE;
  28 #define YYSTYPE CMD_YYSTYPE
  29 #include "command_lex.h"
  30
  31 // compile with debugging facilities
  32 #define YYDEBUG 1
  33 %}
  34
  35 %define api.pure full
  36 %define api.prefix {cmd_yy}
  37
  38 /* names for generated header and parser files */
  39 %defines "command_parse.h"
  40 %output  "command_parse.c"
  41
  42 /* required external units */
  43 %code requires {
  44   #include "stdlib.h"
  45   #include "string.h"
  46   #include "command.h"
  47   #include "log.h"
  48   #include "graph.h"
  49
  50   struct parser_ctx {
  51     yyscan_t scanner;
  52
  53     struct cmd_element *el;
  54
  55     struct graph *graph;
  56     struct graph_node *currnode, *startnode;
  57
  58     /* pointers to copy of command docstring */
  59     char *docstr_start, *docstr;
  60   };
  61
  62   extern void set_lexer_string (yyscan_t *scn, const char *string);
  63   extern void cleanup_lexer (yyscan_t *scn);
  64 }
  65
  66 /* functionality this unit exports */
  67 %code provides {
  68   /* maximum length of a number, lexer will not match anything longer */
  69   #define DECIMAL_STRLEN_MAX 20
  70 }
  71
  72 /* valid semantic types for tokens and rules */
  73 %union {
  74   long long number;
  75   char *string;
  76   struct graph_node *node;
  77   struct subgraph *subgraph;
  78 }
  79
  80 /* union types for lexed tokens */
  81 %token <string> WORD
  82 %token <string> IPV4
  83 %token <string> IPV4_PREFIX
  84 %token <string> IPV6
  85 %token <string> IPV6_PREFIX
  86 %token <string> VARIABLE
  87 %token <string> RANGE
  88
  89 /* union types for parsed rules */
  90 %type <node> start
  91 %type <node> sentence_root
  92 %type <node> literal_token
  93 %type <node> placeholder_token
  94 %type <node> simple_token
  95 %type <subgraph> option
  96 %type <subgraph> option_token
  97 %type <subgraph> option_token_seq
  98 %type <subgraph> selector
  99 %type <subgraph> selector_token
 100 %type <subgraph> selector_token_seq
 101 %type <subgraph> selector_seq_seq
 102 %type <subgraph> compound_token
 103
 104 %code {
 105
 106   /* bison declarations */
 107   void
 108   cmd_yyerror (struct parser_ctx *ctx, char const *msg);
 109
 110   /* subgraph semantic value */
 111   struct subgraph {
 112     struct graph_node *start, *end;
 113   };
 114
 115   /* helper functions for parser */
 116   static char *
 117   doc_next (struct parser_ctx *ctx);
 118
 119   static struct graph_node *
 120   node_adjacent (struct graph_node *, struct graph_node *);
 121
 122   static struct graph_node *
 123   add_edge_dedup (struct graph_node *, struct graph_node *);
 124
 125   static int
 126   cmp_token (struct cmd_token *, struct cmd_token *);
 127
 128   static struct graph_node *
 129   new_token_node (struct parser_ctx *,
 130                   enum cmd_token_type type,
 131                   char *text,
 132                   char *doc);
 133
 134   static void
 135   terminate_graph (struct parser_ctx *ctx,
 136                    struct graph_node *);
 137
 138   static void
 139   cleanup (struct parser_ctx *ctx);
 140
 141   #define scanner ctx->scanner
 142 }
 143
 144 /* yyparse parameters */
 145 %lex-param {yyscan_t scanner}
 146 %parse-param {struct parser_ctx *ctx}
 147
 148 /* called automatically before yyparse */
 149 %initial-action {
 150   /* clear state pointers */
 151   ctx->currnode = ctx->startnode = NULL;
 152
 153   ctx->startnode = 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   sentence_root cmd_token_seq
 174 {
 175   // tack on the command element
 176   terminate_graph (ctx, ctx->currnode);
 177 }
 178 | sentence_root cmd_token_seq placeholder_token '.' '.' '.'
 179 {
 180   if ((ctx->currnode = add_edge_dedup (ctx->currnode, $3)) != $3)
 181     graph_delete_node (ctx->graph, $3);
 182
 183   ctx->currnode->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   add_edge_dedup (ctx->currnode, ctx->currnode);
 188
 189   // tack on the command element
 190   terminate_graph (ctx, ctx->currnode);
 191 }
 192 ;
 193
 194 sentence_root: WORD
 195 {
 196   struct graph_node *root =
 197     new_token_node (ctx, WORD_TKN, strdup ($1), doc_next(ctx));
 198
 199   if ((ctx->currnode = add_edge_dedup (ctx->startnode, root)) != root)
 200     graph_delete_node (ctx->graph, root);
 201
 202   free ($1);
 203   $$ = ctx->currnode;
 204 }
 205 ;
 206
 207 cmd_token_seq:
 208   /* empty */
 209 | cmd_token_seq cmd_token
 210 ;
 211
 212 cmd_token:
 213   simple_token
 214 {
 215   if ((ctx->currnode = add_edge_dedup (ctx->currnode, $1)) != $1)
 216     graph_delete_node (ctx->graph, $1);
 217 }
 218 | compound_token
 219 {
 220   graph_add_edge (ctx->currnode, $1->start);
 221   ctx->currnode = $1->end;
 222   free ($1);
 223 }
 224 ;
 225
 226 simple_token:
 227   literal_token
 228 | placeholder_token
 229 ;
 230
 231 compound_token:
 232   selector
 233 | option
 234 ;
 235
 236 literal_token: WORD
 237 {
 238   $$ = new_token_node (ctx, WORD_TKN, strdup($1), doc_next(ctx));
 239   free ($1);
 240 }
 241 ;
 242
 243 placeholder_token:
 244   IPV4
 245 {
 246   $$ = new_token_node (ctx, IPV4_TKN, strdup($1), doc_next(ctx));
 247   free ($1);
 248 }
 249 | IPV4_PREFIX
 250 {
 251   $$ = new_token_node (ctx, IPV4_PREFIX_TKN, strdup($1), doc_next(ctx));
 252   free ($1);
 253 }
 254 | IPV6
 255 {
 256   $$ = new_token_node (ctx, IPV6_TKN, strdup($1), doc_next(ctx));
 257   free ($1);
 258 }
 259 | IPV6_PREFIX
 260 {
 261   $$ = new_token_node (ctx, IPV6_PREFIX_TKN, strdup($1), doc_next(ctx));
 262   free ($1);
 263 }
 264 | VARIABLE
 265 {
 266   $$ = new_token_node (ctx, VARIABLE_TKN, strdup($1), doc_next(ctx));
 267   free ($1);
 268 }
 269 | RANGE
 270 {
 271   $$ = new_token_node (ctx, RANGE_TKN, strdup($1), doc_next(ctx));
 272   struct cmd_token *token = $$->data;
 273
 274   // get the numbers out
 275   yylval.string++;
 276   token->min = strtoll (yylval.string, &yylval.string, 10);
 277   strsep (&yylval.string, "-");
 278   token->max = strtoll (yylval.string, &yylval.string, 10);
 279
 280   // validate range
 281   if (token->min > token->max) cmd_yyerror (ctx, "Invalid range.");
 282
 283   free ($1);
 284 }
 285
 286 /* <selector|set> productions */
 287 selector: '<' selector_seq_seq '>'
 288 {
 289   $$ = malloc (sizeof (struct subgraph));
 290   $$->start = new_token_node (ctx, SELECTOR_TKN, NULL, NULL);
 291   $$->end   = new_token_node (ctx, NUL_TKN, NULL, NULL);
 292   for (unsigned int i = 0; i < vector_active ($2->start->to); i++)
 293   {
 294     struct graph_node *sn = vector_slot ($2->start->to, i),
 295                       *en = vector_slot ($2->end->from, i);
 296     graph_add_edge ($$->start, sn);
 297     graph_add_edge (en, $$->end);
 298   }
 299   graph_delete_node (ctx->graph, $2->start);
 300   graph_delete_node (ctx->graph, $2->end);
 301   free ($2);
 302 };
 303
 304 selector_seq_seq:
 305   selector_seq_seq '|' selector_token_seq
 306 {
 307   $$ = malloc (sizeof (struct subgraph));
 308   $$->start = graph_new_node (ctx->graph, NULL, NULL);
 309   $$->end   = graph_new_node (ctx->graph, NULL, NULL);
 310
 311   // link in last sequence
 312   graph_add_edge ($$->start, $3->start);
 313   graph_add_edge ($3->end, $$->end);
 314
 315   for (unsigned int i = 0; i < vector_active ($1->start->to); i++)
 316   {
 317     struct graph_node *sn = vector_slot ($1->start->to, i),
 318                       *en = vector_slot ($1->end->from, i);
 319     graph_add_edge ($$->start, sn);
 320     graph_add_edge (en, $$->end);
 321   }
 322   graph_delete_node (ctx->graph, $1->start);
 323   graph_delete_node (ctx->graph, $1->end);
 324   free ($1);
 325   free ($3);
 326 }
 327 | selector_token_seq '|' selector_token_seq
 328 {
 329   $$ = malloc (sizeof (struct subgraph));
 330   $$->start = graph_new_node (ctx->graph, NULL, NULL);
 331   $$->end   = graph_new_node (ctx->graph, NULL, NULL);
 332   graph_add_edge ($$->start, $1->start);
 333   graph_add_edge ($1->end, $$->end);
 334   graph_add_edge ($$->start, $3->start);
 335   graph_add_edge ($3->end, $$->end);
 336   free ($1);
 337   free ($3);
 338 }
 339 ;
 340
 341 /* {keyword} productions */
 342 selector: '{' selector_seq_seq '}'
 343 {
 344   $$ = malloc (sizeof (struct subgraph));
 345   $$->start = new_token_node (ctx, SELECTOR_TKN, NULL, NULL);
 346   $$->end   = new_token_node (ctx, NUL_TKN, NULL, NULL);
 347   graph_add_edge ($$->start, $$->end);
 348   for (unsigned int i = 0; i < vector_active ($2->start->to); i++)
 349   {
 350     struct graph_node *sn = vector_slot ($2->start->to, i),
 351                       *en = vector_slot ($2->end->from, i);
 352     graph_add_edge ($$->start, sn);
 353     graph_add_edge (en, $$->start);
 354   }
 355   graph_delete_node (ctx->graph, $2->start);
 356   graph_delete_node (ctx->graph, $2->end);
 357   free ($2);
 358 };
 359
 360
 361 selector_token_seq:
 362   simple_token
 363 {
 364   $$ = malloc (sizeof (struct subgraph));
 365   $$->start = $$->end = $1;
 366 }
 367 | selector_token_seq selector_token
 368 {
 369   $$ = malloc (sizeof (struct subgraph));
 370   graph_add_edge ($1->end, $2->start);
 371   $$->start = $1->start;
 372   $$->end   = $2->end;
 373   free ($1);
 374   free ($2);
 375 }
 376 ;
 377
 378 selector_token:
 379   simple_token
 380 {
 381   $$ = malloc (sizeof (struct subgraph));
 382   $$->start = $$->end = $1;
 383 }
 384 | option
 385 | selector
 386 ;
 387
 388 /* [option] productions */
 389 option: '[' option_token_seq ']'
 390 {
 391   // make a new option
 392   $$ = malloc (sizeof (struct subgraph));
 393   $$->start = new_token_node (ctx, OPTION_TKN, NULL, NULL);
 394   $$->end   = new_token_node (ctx, NUL_TKN, NULL, NULL);
 395   // add a path through the sequence to the end
 396   graph_add_edge ($$->start, $2->start);
 397   graph_add_edge ($2->end, $$->end);
 398   // add a path directly from the start to the end
 399   graph_add_edge ($$->start, $$->end);
 400   free ($2);
 401 }
 402 ;
 403
 404 option_token_seq:
 405   option_token
 406 | option_token_seq option_token
 407 {
 408   $$ = malloc (sizeof (struct subgraph));
 409   graph_add_edge ($1->end, $2->start);
 410   $$->start = $1->start;
 411   $$->end   = $2->end;
 412   free ($1);
 413   free ($2);
 414 }
 415 ;
 416
 417 option_token:
 418   simple_token
 419 {
 420   $$ = malloc (sizeof (struct subgraph));
 421   $$->start = $$->end = $1;
 422 }
 423 | compound_token
 424 ;
 425
 426 %%
 427
 428 #undef scanner
 429
 430 void
 431 command_parse_format (struct graph *graph, struct cmd_element *cmd)
 432 {
 433   struct parser_ctx ctx = { .graph = graph, .el = cmd };
 434
 435   // set to 1 to enable parser traces
 436   yydebug = 0;
 437
 438   set_lexer_string (&ctx.scanner, cmd->string);
 439
 440   // parse command into DFA
 441   cmd_yyparse (&ctx);
 442
 443   /* cleanup lexer */
 444   cleanup_lexer (&ctx.scanner);
 445
 446   // cleanup
 447   cleanup (&ctx);
 448 }
 449
 450 /* parser helper functions */
 451
 452 void
 453 yyerror (struct parser_ctx *ctx, char const *msg)
 454 {
 455   zlog_err ("%s: FATAL parse error: %s", __func__, msg);
 456   zlog_err ("while parsing this command definition: \n\t%s\n", ctx->el->string);
 457   //exit(EXIT_FAILURE);
 458 }
 459
 460 static void
 461 cleanup (struct parser_ctx *ctx)
 462 {
 463   /* free resources */
 464   free (ctx->docstr_start);
 465
 466   /* clear state pointers */
 467   ctx->currnode = NULL;
 468   ctx->docstr_start = ctx->docstr = NULL;
 469 }
 470
 471 static void
 472 terminate_graph (struct parser_ctx *ctx, struct graph_node *finalnode)
 473 {
 474   // end of graph should look like this
 475   // * -> finalnode -> END_TKN -> cmd_element
 476   struct cmd_element *element = ctx->el;
 477   struct graph_node *end_token_node =
 478     new_token_node (ctx,
 479                     END_TKN,
 480                     strdup (CMD_CR_TEXT),
 481                     strdup (""));
 482   struct graph_node *end_element_node =
 483     graph_new_node (ctx->graph, element, NULL);
 484
 485   if (node_adjacent (finalnode, end_token_node))
 486     cmd_yyerror (ctx, "Duplicate command.");
 487
 488   graph_add_edge (finalnode, end_token_node);
 489   graph_add_edge (end_token_node, end_element_node);
 490 }
 491
 492 static char *
 493 doc_next (struct parser_ctx *ctx)
 494 {
 495   const char *piece = ctx->docstr ? strsep (&ctx->docstr, "\n") : "";
 496   if (*piece == 0x03)
 497   {
 498     zlog_debug ("Ran out of docstring while parsing '%s'", ctx->el->string);
 499     piece = "";
 500   }
 501
 502   return strdup (piece);
 503 }
 504
 505 static struct graph_node *
 506 new_token_node (struct parser_ctx *ctx, enum cmd_token_type type,
 507                 char *text, char *doc)
 508 {
 509   struct cmd_token *token = new_cmd_token (type, ctx->el->attr, text, doc);
 510   return graph_new_node (ctx->graph, token, (void (*)(void *)) &del_cmd_token);
 511 }
 512
 513 /**
 514  * Determines if there is an out edge from the first node to the second
 515  */
 516 static struct graph_node *
 517 node_adjacent (struct graph_node *first, struct graph_node *second)
 518 {
 519   struct graph_node *adj;
 520   for (unsigned int i = 0; i < vector_active (first->to); i++)
 521     {
 522       adj = vector_slot (first->to, i);
 523       struct cmd_token *ftok = adj->data,
 524                          *stok = second->data;
 525       if (cmp_token (ftok, stok))
 526         return adj;
 527     }
 528   return NULL;
 529 }
 530
 531 /**
 532  * Creates an edge betwen two nodes, unless there is already an edge to an
 533  * equivalent node.
 534  *
 535  * The first node's out edges are searched to see if any of them point to a
 536  * node that is equivalent to the second node. If such a node exists, it is
 537  * returned. Otherwise an edge is created from the first node to the second.
 538  *
 539  * @param from start node for edge
 540  * @param to end node for edge
 541  * @return the node which the new edge points to
 542  */
 543 static struct graph_node *
 544 add_edge_dedup (struct graph_node *from, struct graph_node *to)
 545 {
 546   struct graph_node *existing = node_adjacent (from, to);
 547   if (existing)
 548   {
 549     struct cmd_token *ex_tok = existing->data;
 550     struct cmd_token *to_tok = to->data;
 551     // NORMAL takes precedence over DEPRECATED takes precedence over HIDDEN
 552     ex_tok->attr = (ex_tok->attr < to_tok->attr) ? ex_tok->attr : to_tok->attr;
 553     return existing;
 554   }
 555   else
 556     return graph_add_edge (from, to);
 557 }
 558
 559 /**
 560  * Compares two cmd_token's for equality,
 561  *
 562  * As such, this function is the working definition of token equality
 563  * for parsing purposes and determines overall graph structure.
 564  */
 565 static int
 566 cmp_token (struct cmd_token *first, struct cmd_token *second)
 567 {
 568   // compare types
 569   if (first->type != second->type) return 0;
 570
 571   switch (first->type) {
 572     case WORD_TKN:
 573     case VARIABLE_TKN:
 574       if (first->text && second->text)
 575         {
 576           if (strcmp (first->text, second->text))
 577             return 0;
 578         }
 579       else if (first->text != second->text) return 0;
 580       break;
 581     case RANGE_TKN:
 582       if (first->min != second->min || first->max != second->max)
 583         return 0;
 584       break;
 585     /* selectors and options should be equal if their subgraphs are equal,
 586      * but the graph isomorphism problem is not known to be solvable in
 587      * polynomial time so we consider selectors and options inequal in all
 588      * cases; ultimately this forks the graph, but the matcher can handle
 589      * this regardless
 590      */
 591     case SELECTOR_TKN:
 592     case OPTION_TKN:
 593       return 0;
 594
 595     /* end nodes are always considered equal, since each node may only
 596      * have one END_TKN child at a time
 597      */
 598     case START_TKN:
 599     case END_TKN:
 600     case NUL_TKN:
 601     default:
 602       break;
 603   }
 604   return 1;
 605 }