lib/command_parse.y

   1 /*
   2  * Command format string parser for CLI backend.
   3  *
   4  * --
   5  * Copyright (C) 2015 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 /* names for generated header and parser files */
  31 %defines "command_parse.h"
  32 %output  "command_parse.c"
  33
  34 /* required external units */
  35 %code requires {
  36   #include "command.h"
  37   #include "command_graph.h"
  38   #include "memory.h"
  39
  40   extern int
  41   yylex (void);
  42
  43   extern void
  44   set_buffer_string (const char *);
  45 }
  46
  47 /* functionality this unit exports */
  48 %code provides {
  49   struct graph_node *
  50   parse_command_format (struct graph_node *, struct cmd_element *);
  51
  52   /* maximum length of a number, lexer will not match anything longer */
  53   #define DECIMAL_STRLEN_MAX 20
  54 }
  55
  56 /* valid semantic types for tokens and rules */
  57 %union {
  58   long long number;
  59   char *string;
  60   struct graph_node *node;
  61 }
  62
  63 /* union types for lexed tokens */
  64 %token <string> WORD
  65 %token <string> IPV4
  66 %token <string> IPV4_PREFIX
  67 %token <string> IPV6
  68 %token <string> IPV6_PREFIX
  69 %token <string> VARIABLE
  70 %token <string> RANGE
  71 %token <number> NUMBER
  72
  73 /* union types for parsed rules */
  74 %type <node> start
  75 %type <node> sentence_root
  76 %type <node> literal_token
  77 %type <node> placeholder_token
  78 %type <node> option
  79 %type <node> option_token
  80 %type <node> option_token_seq
  81 %type <node> selector
  82 %type <node> selector_element_root
  83 %type <node> selector_token
  84 %type <node> selector_token_seq
  85
  86 %code {
  87   /* bison declarations */
  88   void
  89   yyerror (struct cmd_element *el, struct graph_node *sn, char const *msg);
  90
  91   /* state variables for a single parser run */
  92   struct graph_node *currnode,        // current position in DFA
  93                     *seqhead;         // sequence head
  94
  95   struct graph_node *optnode_start,   // start node for option set
  96                     *optnode_end;     // end node for option set
  97
  98   struct graph_node *selnode_start,   // start node for selector set
  99                     *selnode_end;     // end node for selector set
 100
 101   char *docstr_start, *docstr;        // pointers to copy of command docstring
 102
 103   /* helper functions for parser */
 104   static char *
 105   doc_next(void);
 106
 107   static struct graph_node *
 108   node_exists (struct graph_node *, struct graph_node *);
 109
 110   static struct graph_node *
 111   node_replace (struct graph_node *, struct graph_node *);
 112
 113   static int
 114   cmp_node (struct graph_node *, struct graph_node *);
 115
 116   static void
 117   terminate_graph (struct graph_node *,
 118                    struct graph_node *,
 119                    struct cmd_element *);
 120
 121   static void
 122   cleanup (void);
 123 }
 124
 125 /* yyparse parameters */
 126 %parse-param { struct cmd_element *element }
 127 %parse-param { struct graph_node *startnode }
 128
 129 /* called automatically before yyparse */
 130 %initial-action {
 131   /* clear state pointers */
 132   seqhead = NULL;
 133   currnode = NULL;
 134   selnode_start = selnode_end = NULL;
 135   optnode_start = optnode_end = NULL;
 136
 137   /* set string to parse */
 138   set_buffer_string (element->string);
 139
 140   /* copy docstring and keep a pointer to the copy */
 141   docstr = element->doc ? XSTRDUP(MTYPE_TMP, element->doc) : NULL;
 142   docstr_start = docstr;
 143 }
 144
 145 %%
 146
 147 start:
 148   sentence_root cmd_token_seq
 149 {
 150   // tack on the command element
 151   terminate_graph (startnode, currnode, element);
 152   cleanup();
 153 }
 154 | sentence_root cmd_token_seq '.' placeholder_token
 155 {
 156   if ((currnode = node_replace (currnode, $4)) != $4)
 157     delete_node ($4);
 158
 159   // adding a node as a child of itself accepts any number
 160   // of the same token, which is what we want for varags
 161   node_replace (currnode, currnode);
 162
 163   // tack on the command element
 164   terminate_graph (startnode, currnode, element);
 165   cleanup();
 166 }
 167
 168 sentence_root: WORD
 169 {
 170   struct graph_node *root = new_node (WORD_GN);
 171   root->text = XSTRDUP(MTYPE_CMD_TOKENS, $1);
 172   root->doc = doc_next();
 173
 174   if ((currnode = node_replace (startnode, root)) != root)
 175     free (root);
 176
 177   free ($1);
 178   $$ = currnode;
 179 };
 180
 181 cmd_token:
 182   placeholder_token
 183 {
 184   if ((currnode = node_replace (currnode, $1)) != $1)
 185     delete_node ($1);
 186 }
 187 | literal_token
 188 {
 189   if ((currnode = node_replace (currnode, $1)) != $1)
 190     delete_node ($1);
 191 }
 192 /* selectors and options are subgraphs with start and end nodes */
 193 | selector
 194 {
 195   add_node (currnode, $1);
 196   currnode = selnode_end;
 197   selnode_start = selnode_end = NULL;
 198 }
 199 | option
 200 {
 201   add_node (currnode, $1);
 202   currnode = optnode_end;
 203   optnode_start = optnode_end = NULL;
 204 }
 205 ;
 206
 207 cmd_token_seq:
 208   %empty
 209 | cmd_token_seq cmd_token
 210 ;
 211
 212 placeholder_token:
 213   IPV4
 214 {
 215   $$ = new_node (IPV4_GN);
 216   $$->text = XSTRDUP(MTYPE_CMD_TOKENS, $1);
 217   $$->doc = doc_next();
 218   free ($1);
 219 }
 220 | IPV4_PREFIX
 221 {
 222   $$ = new_node (IPV4_PREFIX_GN);
 223   $$->text = XSTRDUP(MTYPE_CMD_TOKENS, $1);
 224   $$->doc = doc_next();
 225   free ($1);
 226 }
 227 | IPV6
 228 {
 229   $$ = new_node (IPV6_GN);
 230   $$->text = XSTRDUP(MTYPE_CMD_TOKENS, $1);
 231   $$->doc = doc_next();
 232   free ($1);
 233 }
 234 | IPV6_PREFIX
 235 {
 236   $$ = new_node (IPV6_PREFIX_GN);
 237   $$->text = XSTRDUP(MTYPE_CMD_TOKENS, $1);
 238   $$->doc = doc_next();
 239   free ($1);
 240 }
 241 | VARIABLE
 242 {
 243   $$ = new_node (VARIABLE_GN);
 244   $$->text = XSTRDUP(MTYPE_CMD_TOKENS, $1);
 245   $$->doc = doc_next();
 246   free ($1);
 247 }
 248 | RANGE
 249 {
 250   $$ = new_node (RANGE_GN);
 251   $$->text = XSTRDUP(MTYPE_CMD_TOKENS, $1);
 252   $$->doc = doc_next();
 253
 254   // get the numbers out
 255   yylval.string++;
 256   $$->min = strtoll (yylval.string, &yylval.string, 10);
 257   strsep (&yylval.string, "-");
 258   $$->max = strtoll (yylval.string, &yylval.string, 10);
 259
 260   // validate range
 261   if ($$->min >= $$->max) yyerror (element, startnode, "Invalid range.");
 262
 263   free ($1);
 264 }
 265 ;
 266
 267 literal_token:
 268   WORD
 269 {
 270   $$ = new_node (WORD_GN);
 271   $$->text = XSTRDUP(MTYPE_CMD_TOKENS, $1);
 272   $$->doc = doc_next();
 273   free ($1);
 274 }
 275 | NUMBER
 276 {
 277   $$ = new_node (NUMBER_GN);
 278   $$->value = yylval.number;
 279   $$->text = XCALLOC(MTYPE_CMD_TOKENS, DECIMAL_STRLEN_MAX+1);
 280   snprintf($$->text, DECIMAL_STRLEN_MAX, "%lld", $$->value);
 281   $$->doc = doc_next();
 282 }
 283 ;
 284
 285 /* <selector|set> productions */
 286 selector: '<' selector_part '>'
 287 {
 288   // all the graph building is done in selector_element,
 289   // so just return the selector subgraph head
 290   $$ = selnode_start;
 291 };
 292
 293 selector_part:
 294   selector_part '|' selector_element
 295 | selector_element '|' selector_element
 296 ;
 297
 298 selector_element: selector_element_root selector_token_seq
 299 {
 300   // if the selector start and end do not exist, create them
 301   if (!selnode_start || !selnode_end) {     // if one is null
 302     assert(!selnode_start && !selnode_end); // both should be null
 303     selnode_start = new_node (SELECTOR_GN);  // diverging node
 304     selnode_end = new_node (NUL_GN);         // converging node
 305     selnode_start->end = selnode_end;       // duh
 306   }
 307
 308   // add element head as a child of the selector
 309   add_node (selnode_start, $1);
 310
 311   if ($2->type != NUL_GN) {
 312     add_node ($1, seqhead);
 313     add_node ($2, selnode_end);
 314   }
 315   else
 316     add_node ($1, selnode_end);
 317
 318   seqhead = NULL;
 319 }
 320
 321 selector_token_seq:
 322   %empty { $$ = new_node (NUL_GN); }
 323 | selector_token_seq selector_token
 324 {
 325   // if the sequence component is NUL_GN, this is a sequence start
 326   if ($1->type == NUL_GN) {
 327     assert(!seqhead); // sequence head should always be null here
 328     seqhead = $2;
 329   }
 330   else // chain on new node
 331     add_node ($1, $2);
 332
 333   $$ = $2;
 334 }
 335 ;
 336
 337 selector_element_root:
 338   literal_token
 339 | placeholder_token
 340 ;
 341
 342 selector_token:
 343   selector_element_root
 344 | option
 345 ;
 346
 347 /* [option|set] productions */
 348 option: '[' option_part ']'
 349 {
 350   // add null path
 351   add_node (optnode_start, optnode_end);
 352   $$ = optnode_start;
 353 };
 354
 355 option_part:
 356   option_part '|' option_element
 357 | option_element
 358 ;
 359
 360 option_element:
 361   option_token_seq
 362 {
 363   if (!optnode_start || !optnode_end) {
 364     assert(!optnode_start && !optnode_end);
 365     optnode_start = new_node (OPTION_GN);
 366     optnode_end = new_node (NUL_GN);
 367   }
 368
 369   add_node (optnode_start, seqhead);
 370   add_node ($1, optnode_end);
 371 }
 372
 373 option_token_seq:
 374   option_token
 375 { $$ = seqhead = $1; }
 376 | option_token_seq option_token
 377 { $$ = add_node ($1, $2); }
 378 ;
 379
 380 option_token:
 381   literal_token
 382 | placeholder_token
 383 ;
 384
 385 %%
 386
 387 struct graph_node *
 388 parse_command_format(struct graph_node *start, struct cmd_element *cmd)
 389 {
 390   // set to 1 to enable parser traces
 391   yydebug = 0;
 392
 393   // parse command into DFA
 394   yyparse(cmd, start);
 395
 396   return start;
 397 }
 398
 399 /* parser helper functions */
 400
 401 void
 402 yyerror (struct cmd_element *el, struct graph_node *sn, char const *msg)
 403 {
 404   zlog_err ("%s: FATAL parse error: %s", __func__, msg);
 405   zlog_err ("while parsing this command definition: \n\t%s\n", el->string);
 406   exit(EXIT_FAILURE);
 407 }
 408
 409 static void
 410 cleanup()
 411 {
 412   /* free resources */
 413   free (docstr_start);
 414
 415   /* clear state pointers */
 416   seqhead = NULL;
 417   currnode = NULL;
 418   docstr_start = docstr = NULL;
 419   selnode_start = selnode_end = NULL;
 420   optnode_start = optnode_end = NULL;
 421 }
 422
 423 static void
 424 terminate_graph (struct graph_node *startnode,
 425                  struct graph_node *finalnode,
 426                  struct cmd_element *element)
 427 {
 428   struct graph_node *end = new_node (END_GN);
 429   end->element = element;
 430   if (node_exists (finalnode, end))
 431     yyerror (element, startnode, "Duplicate command.");
 432   else
 433     add_node (finalnode, end);
 434 }
 435
 436 static char *
 437 doc_next()
 438 {
 439   char *piece = NULL;
 440   if (!docstr || !(piece = strsep (&docstr, "\n")))
 441     return NULL;
 442   return XSTRDUP(MTYPE_CMD_TOKENS, piece);
 443 }
 444
 445 static struct graph_node *
 446 node_exists (struct graph_node *parent, struct graph_node *child)
 447 {
 448   struct graph_node *p_child;
 449   for (unsigned int i = 0; i < vector_active (parent->children); i++)
 450     {
 451       p_child = vector_slot (parent->children, i);
 452       if (cmp_node (child, p_child))
 453         return p_child;
 454     }
 455   return NULL;
 456 }
 457
 458 static struct graph_node *
 459 node_replace (struct graph_node *parent, struct graph_node *child)
 460 {
 461   struct graph_node *existing = node_exists (parent, child);
 462   return existing ? existing : add_node (parent, child);
 463 }
 464
 465 static int
 466 cmp_node (struct graph_node *first, struct graph_node *second)
 467 {
 468   // compare types
 469   if (first->type != second->type) return 0;
 470
 471   switch (first->type) {
 472     case WORD_GN:
 473     case VARIABLE_GN:
 474       if (first->text && second->text && strcmp (first->text, second->text))
 475         return 0;
 476       else if (first->text != second->text) return 0;
 477       break;
 478     case RANGE_GN:
 479       if (first->min != second->min || first->max != second->max)
 480         return 0;
 481       break;
 482     case NUMBER_GN:
 483       if (first->value != second->value) return 0;
 484       break;
 485     /* selectors and options should be equal if their subgraphs are equal, but
 486      * the graph isomorphism problem is not known to be solvable in polynomial time
 487      * so we consider selectors and options inequal in all cases; ultimately this
 488      * forks the graph, but the matcher can handle this regardless
 489      */
 490     case SELECTOR_GN:
 491     case OPTION_GN:
 492       return 0;
 493     /* end nodes are always considered equal, since each node may only
 494      * have one END_GN child at a time
 495      */
 496     case START_GN:
 497     case END_GN:
 498     case NUL_GN:
 499     default:
 500       break;
 501   }
 502   return 1;
 503 }