Line data    Source code

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