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   // adding a node as a child of itself accepts any number
 184   // of the same token, which is what we want for variadics
 185   add_edge_dedup (ctx->currnode, ctx->currnode);
 186
 187   // tack on the command element
 188   terminate_graph (ctx, ctx->currnode);
 189 }
 190 ;
 191
 192 sentence_root: WORD
 193 {
 194   struct graph_node *root =
 195     new_token_node (ctx, WORD_TKN, strdup ($1), doc_next(ctx));
 196
 197   if ((ctx->currnode = add_edge_dedup (ctx->startnode, root)) != root)
 198     graph_delete_node (ctx->graph, root);
 199
 200   free ($1);
 201   $$ = ctx->currnode;
 202 }
 203 ;
 204
 205 cmd_token_seq:
 206   /* empty */
 207 | cmd_token_seq cmd_token
 208 ;
 209
 210 cmd_token:
 211   simple_token
 212 {
 213   if ((ctx->currnode = add_edge_dedup (ctx->currnode, $1)) != $1)
 214     graph_delete_node (ctx->graph, $1);
 215 }
 216 | compound_token
 217 {
 218   graph_add_edge (ctx->currnode, $1->start);
 219   ctx->currnode = $1->end;
 220   free ($1);
 221 }
 222 ;
 223
 224 simple_token:
 225   literal_token
 226 | placeholder_token
 227 ;
 228
 229 compound_token:
 230   selector
 231 | option
 232 ;
 233
 234 literal_token: WORD
 235 {
 236   $$ = new_token_node (ctx, WORD_TKN, strdup($1), doc_next(ctx));
 237   free ($1);
 238 }
 239 ;
 240
 241 placeholder_token:
 242   IPV4
 243 {
 244   $$ = new_token_node (ctx, IPV4_TKN, strdup($1), doc_next(ctx));
 245   free ($1);
 246 }
 247 | IPV4_PREFIX
 248 {
 249   $$ = new_token_node (ctx, IPV4_PREFIX_TKN, strdup($1), doc_next(ctx));
 250   free ($1);
 251 }
 252 | IPV6
 253 {
 254   $$ = new_token_node (ctx, IPV6_TKN, strdup($1), doc_next(ctx));
 255   free ($1);
 256 }
 257 | IPV6_PREFIX
 258 {
 259   $$ = new_token_node (ctx, IPV6_PREFIX_TKN, strdup($1), doc_next(ctx));
 260   free ($1);
 261 }
 262 | VARIABLE
 263 {
 264   $$ = new_token_node (ctx, VARIABLE_TKN, strdup($1), doc_next(ctx));
 265   free ($1);
 266 }
 267 | RANGE
 268 {
 269   $$ = new_token_node (ctx, RANGE_TKN, strdup($1), doc_next(ctx));
 270   struct cmd_token *token = $$->data;
 271
 272   // get the numbers out
 273   yylval.string++;
 274   token->min = strtoll (yylval.string, &yylval.string, 10);
 275   strsep (&yylval.string, "-");
 276   token->max = strtoll (yylval.string, &yylval.string, 10);
 277
 278   // validate range
 279   if (token->min > token->max) cmd_yyerror (ctx, "Invalid range.");
 280
 281   free ($1);
 282 }
 283
 284 /* <selector|set> productions */
 285 selector: '<' selector_seq_seq '>'
 286 {
 287   $$ = malloc (sizeof (struct subgraph));
 288   $$->start = new_token_node (ctx, SELECTOR_TKN, NULL, NULL);
 289   $$->end   = new_token_node (ctx, NUL_TKN, NULL, NULL);
 290   for (unsigned int i = 0; i < vector_active ($2->start->to); i++)
 291   {
 292     struct graph_node *sn = vector_slot ($2->start->to, i),
 293                       *en = vector_slot ($2->end->from, i);
 294     graph_add_edge ($$->start, sn);
 295     graph_add_edge (en, $$->end);
 296   }
 297   graph_delete_node (ctx->graph, $2->start);
 298   graph_delete_node (ctx->graph, $2->end);
 299   free ($2);
 300 };
 301
 302 selector_seq_seq:
 303   selector_seq_seq '|' selector_token_seq
 304 {
 305   $$ = malloc (sizeof (struct subgraph));
 306   $$->start = graph_new_node (ctx->graph, NULL, NULL);
 307   $$->end   = graph_new_node (ctx->graph, NULL, NULL);
 308
 309   // link in last sequence
 310   graph_add_edge ($$->start, $3->start);
 311   graph_add_edge ($3->end, $$->end);
 312
 313   for (unsigned int i = 0; i < vector_active ($1->start->to); i++)
 314   {
 315     struct graph_node *sn = vector_slot ($1->start->to, i),
 316                       *en = vector_slot ($1->end->from, i);
 317     graph_add_edge ($$->start, sn);
 318     graph_add_edge (en, $$->end);
 319   }
 320   graph_delete_node (ctx->graph, $1->start);
 321   graph_delete_node (ctx->graph, $1->end);
 322   free ($1);
 323   free ($3);
 324 }
 325 | selector_token_seq '|' selector_token_seq
 326 {
 327   $$ = malloc (sizeof (struct subgraph));
 328   $$->start = graph_new_node (ctx->graph, NULL, NULL);
 329   $$->end   = graph_new_node (ctx->graph, NULL, NULL);
 330   graph_add_edge ($$->start, $1->start);
 331   graph_add_edge ($1->end, $$->end);
 332   graph_add_edge ($$->start, $3->start);
 333   graph_add_edge ($3->end, $$->end);
 334   free ($1);
 335   free ($3);
 336 }
 337 ;
 338
 339 selector_token_seq:
 340   simple_token
 341 {
 342   $$ = malloc (sizeof (struct subgraph));
 343   $$->start = $$->end = $1;
 344 }
 345 | selector_token_seq selector_token
 346 {
 347   $$ = malloc (sizeof (struct subgraph));
 348   graph_add_edge ($1->end, $2->start);
 349   $$->start = $1->start;
 350   $$->end   = $2->end;
 351   free ($1);
 352   free ($2);
 353 }
 354 ;
 355
 356 selector_token:
 357   simple_token
 358 {
 359   $$ = malloc (sizeof (struct subgraph));
 360   $$->start = $$->end = $1;
 361 }
 362 | option
 363 | selector
 364 ;
 365
 366 /* [option] productions */
 367 option: '[' option_token_seq ']'
 368 {
 369   // make a new option
 370   $$ = malloc (sizeof (struct subgraph));
 371   $$->start = new_token_node (ctx, OPTION_TKN, NULL, NULL);
 372   $$->end   = new_token_node (ctx, NUL_TKN, NULL, NULL);
 373   // add a path through the sequence to the end
 374   graph_add_edge ($$->start, $2->start);
 375   graph_add_edge ($2->end, $$->end);
 376   // add a path directly from the start to the end
 377   graph_add_edge ($$->start, $$->end);
 378   free ($2);
 379 }
 380 ;
 381
 382 option_token_seq:
 383   option_token
 384 | option_token_seq option_token
 385 {
 386   $$ = malloc (sizeof (struct subgraph));
 387   graph_add_edge ($1->end, $2->start);
 388   $$->start = $1->start;
 389   $$->end   = $2->end;
 390   free ($1);
 391   free ($2);
 392 }
 393 ;
 394
 395 option_token:
 396   simple_token
 397 {
 398   $$ = malloc (sizeof (struct subgraph));
 399   $$->start = $$->end = $1;
 400 }
 401 | compound_token
 402 ;
 403
 404 %%
 405
 406 #undef scanner
 407
 408 void
 409 command_parse_format (struct graph *graph, struct cmd_element *cmd)
 410 {
 411   struct parser_ctx ctx = { .graph = graph, .el = cmd };
 412
 413   // set to 1 to enable parser traces
 414   yydebug = 0;
 415
 416   set_lexer_string (&ctx.scanner, cmd->string);
 417
 418   // parse command into DFA
 419   cmd_yyparse (&ctx);
 420
 421   /* cleanup lexer */
 422   cleanup_lexer (&ctx.scanner);
 423
 424   // cleanup
 425   cleanup (&ctx);
 426 }
 427
 428 /* parser helper functions */
 429
 430 void
 431 yyerror (struct parser_ctx *ctx, char const *msg)
 432 {
 433   zlog_err ("%s: FATAL parse error: %s", __func__, msg);
 434   zlog_err ("while parsing this command definition: \n\t%s\n", ctx->el->string);
 435   //exit(EXIT_FAILURE);
 436 }
 437
 438 static void
 439 cleanup (struct parser_ctx *ctx)
 440 {
 441   /* free resources */
 442   free (ctx->docstr_start);
 443
 444   /* clear state pointers */
 445   ctx->currnode = NULL;
 446   ctx->docstr_start = ctx->docstr = NULL;
 447 }
 448
 449 static void
 450 terminate_graph (struct parser_ctx *ctx, struct graph_node *finalnode)
 451 {
 452   // end of graph should look like this
 453   // * -> finalnode -> END_TKN -> cmd_element
 454   struct cmd_element *element = ctx->el;
 455   struct graph_node *end_token_node =
 456     new_token_node (ctx,
 457                     END_TKN,
 458                     strdup (CMD_CR_TEXT),
 459                     strdup (""));
 460   struct graph_node *end_element_node =
 461     graph_new_node (ctx->graph, element, NULL);
 462
 463   if (node_adjacent (finalnode, end_token_node))
 464     cmd_yyerror (ctx, "Duplicate command.");
 465
 466   graph_add_edge (finalnode, end_token_node);
 467   graph_add_edge (end_token_node, end_element_node);
 468 }
 469
 470 static 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 strdup (piece);
 481 }
 482
 483 static struct graph_node *
 484 new_token_node (struct parser_ctx *ctx, enum cmd_token_type type,
 485                 char *text, char *doc)
 486 {
 487   struct cmd_token *token = new_cmd_token (type, ctx->el->attr, text, doc);
 488   return graph_new_node (ctx->graph, token, (void (*)(void *)) &del_cmd_token);
 489 }
 490
 491 /**
 492  * Determines if there is an out edge from the first node to the second
 493  */
 494 static struct graph_node *
 495 node_adjacent (struct graph_node *first, struct graph_node *second)
 496 {
 497   struct graph_node *adj;
 498   for (unsigned int i = 0; i < vector_active (first->to); i++)
 499     {
 500       adj = vector_slot (first->to, i);
 501       struct cmd_token *ftok = adj->data,
 502                          *stok = second->data;
 503       if (cmp_token (ftok, stok))
 504         return adj;
 505     }
 506   return NULL;
 507 }
 508
 509 /**
 510  * Creates an edge betwen two nodes, unless there is already an edge to an
 511  * equivalent node.
 512  *
 513  * The first node's out edges are searched to see if any of them point to a
 514  * node that is equivalent to the second node. If such a node exists, it is
 515  * returned. Otherwise an edge is created from the first node to the second.
 516  *
 517  * @param from start node for edge
 518  * @param to end node for edge
 519  * @return the node which the new edge points to
 520  */
 521 static struct graph_node *
 522 add_edge_dedup (struct graph_node *from, struct graph_node *to)
 523 {
 524   struct graph_node *existing = node_adjacent (from, to);
 525   if (existing)
 526   {
 527     struct cmd_token *ex_tok = existing->data;
 528     struct cmd_token *to_tok = to->data;
 529     // NORMAL takes precedence over DEPRECATED takes precedence over HIDDEN
 530     ex_tok->attr = (ex_tok->attr < to_tok->attr) ? ex_tok->attr : to_tok->attr;
 531     return existing;
 532   }
 533   else
 534     return graph_add_edge (from, to);
 535 }
 536
 537 /**
 538  * Compares two cmd_token's for equality,
 539  *
 540  * As such, this function is the working definition of token equality
 541  * for parsing purposes and determines overall graph structure.
 542  */
 543 static int
 544 cmp_token (struct cmd_token *first, struct cmd_token *second)
 545 {
 546   // compare types
 547   if (first->type != second->type) return 0;
 548
 549   switch (first->type) {
 550     case WORD_TKN:
 551     case VARIABLE_TKN:
 552       if (first->text && second->text)
 553         {
 554           if (strcmp (first->text, second->text))
 555             return 0;
 556         }
 557       else if (first->text != second->text) return 0;
 558       break;
 559     case RANGE_TKN:
 560       if (first->min != second->min || first->max != second->max)
 561         return 0;
 562       break;
 563     /* selectors and options should be equal if their subgraphs are equal,
 564      * but the graph isomorphism problem is not known to be solvable in
 565      * polynomial time so we consider selectors and options inequal in all
 566      * cases; ultimately this forks the graph, but the matcher can handle
 567      * this regardless
 568      */
 569     case SELECTOR_TKN:
 570     case OPTION_TKN:
 571       return 0;
 572
 573     /* end nodes are always considered equal, since each node may only
 574      * have one END_TKN child at a time
 575      */
 576     case START_TKN:
 577     case END_TKN:
 578     case NUL_TKN:
 579     default:
 580       break;
 581   }
 582   return 1;
 583 }