Merge pull request #13649 from donaldsharp/unlock_the_node_or_else

[mirror_frr.git] / lib / command_parse.y

// SPDX-License-Identifier: GPL-2.0-or-later
/*
 * Command format string parser for CLI backend.
 *
 * --
 * Copyright (C) 2016 Cumulus Networks, Inc.
 */

%{
// compile with debugging facilities
#define YYDEBUG 1
%}

%locations
/* define parse.error verbose */
%define api.pure full
/* define api.prefix {cmd_yy} */

/* names for generated header and parser files */
%defines "lib/command_parse.h"
%output  "lib/command_parse.c"

/* note: code blocks are output in order, to both .c and .h:
 *  1. %code requires
 *  2. %union + bison forward decls
 *  3. %code provides
 * command_lex.h needs to be included at 3.; it needs the union and YYSTYPE.
 * struct parser_ctx is needed for the bison forward decls.
 */
%code requires {
  #include "config.h"

  #include <stdbool.h>
  #include <stdlib.h>
  #include <string.h>
  #include <ctype.h>

  #include "command_graph.h"
  #include "log.h"

  DECLARE_MTYPE(LEX);

  #define YYSTYPE CMD_YYSTYPE
  #define YYLTYPE CMD_YYLTYPE
  struct parser_ctx;

  /* subgraph semantic value */
  struct subgraph {
    struct graph_node *start, *end;
  };
}

%union {
  long long number;
  char *string;
  struct graph_node *node;
  struct subgraph subgraph;
}

%code provides {
  #ifndef FLEX_SCANNER
  #include "lib/command_lex.h"
  #endif

  extern void set_lexer_string (yyscan_t *scn, const char *string);
  extern void cleanup_lexer (yyscan_t *scn);

  struct parser_ctx {
    yyscan_t scanner;

    const struct cmd_element *el;

    struct graph *graph;
    struct graph_node *currnode;

    /* pointers to copy of command docstring */
    char *docstr_start, *docstr;
  };
}

/* union types for lexed tokens */
%token <string> WORD
%token <string> IPV4
%token <string> IPV4_PREFIX
%token <string> IPV6
%token <string> IPV6_PREFIX
%token <string> VARIABLE
%token <string> RANGE
%token <string> MAC
%token <string> MAC_PREFIX
%token <string> ASNUM

/* special syntax, value is irrelevant */
%token <string> EXCL_BRACKET

/* union types for parsed rules */
%type <node> start
%type <node> literal_token
%type <node> placeholder_token
%type <node> placeholder_token_real
%type <node> simple_token
%type <subgraph> selector
%type <subgraph> selector_token
%type <subgraph> selector_token_seq
%type <subgraph> selector_seq_seq

%type <string> varname_token

%code {

  /* bison declarations */
  void
  cmd_yyerror (CMD_YYLTYPE *locp, struct parser_ctx *ctx, char const *msg);

  /* helper functions for parser */
  static const char *
  doc_next (struct parser_ctx *ctx);

  static struct graph_node *
  new_token_node (struct parser_ctx *,
                  enum cmd_token_type type,
                  const char *text,
                  const char *doc);

  static void
  terminate_graph (CMD_YYLTYPE *locp, struct parser_ctx *ctx,
                   struct graph_node *);

  static void
  cleanup (struct parser_ctx *ctx);

  static void loopcheck(struct parser_ctx *ctx, struct subgraph *sg);

  #define scanner ctx->scanner
}

/* yyparse parameters */
%lex-param {yyscan_t scanner}
%parse-param {struct parser_ctx *ctx}

/* called automatically before yyparse */
%initial-action {
  /* clear state pointers */
  ctx->currnode = vector_slot (ctx->graph->nodes, 0);

  /* copy docstring and keep a pointer to the copy */
  if (ctx->el->doc)
  {
    // allocate a new buffer, making room for a flag
    size_t length = (size_t) strlen (ctx->el->doc) + 2;
    ctx->docstr = malloc (length);
    memcpy (ctx->docstr, ctx->el->doc, strlen (ctx->el->doc));
    // set the flag so doc_next knows when to print a warning
    ctx->docstr[length - 2] = 0x03;
    // null terminate
    ctx->docstr[length - 1] = 0x00;
  }
  ctx->docstr_start = ctx->docstr;
}

%%

start:
  cmd_token_seq
{
  // tack on the command element
  terminate_graph (&@1, ctx, ctx->currnode);
}
| cmd_token_seq placeholder_token '.' '.' '.'
{
  if ((ctx->currnode = graph_add_edge (ctx->currnode, $2)) != $2)
    graph_delete_node (ctx->graph, $2);

  ((struct cmd_token *)ctx->currnode->data)->allowrepeat = 1;

  // adding a node as a child of itself accepts any number
  // of the same token, which is what we want for variadics
  graph_add_edge (ctx->currnode, ctx->currnode);

  // tack on the command element
  terminate_graph (&@1, ctx, ctx->currnode);
}
;

varname_token: '$' WORD
{
  $$ = $2;
}
| /* empty */
{
  $$ = NULL;
}
;

cmd_token_seq:
  /* empty */
| cmd_token_seq cmd_token
;

cmd_token:
  simple_token
{
  if ((ctx->currnode = graph_add_edge (ctx->currnode, $1)) != $1)
    graph_delete_node (ctx->graph, $1);
  cmd_token_varname_seqappend($1);
}
| selector
{
  graph_add_edge (ctx->currnode, $1.start);
  cmd_token_varname_seqappend($1.start);
  ctx->currnode = $1.end;
}
;

simple_token:
  literal_token
| placeholder_token
;

literal_token: WORD varname_token
{
  $$ = new_token_node (ctx, WORD_TKN, $1, doc_next(ctx));
  cmd_token_varname_set ($$->data, $2);
  XFREE (MTYPE_LEX, $2);
  XFREE (MTYPE_LEX, $1);
}
;

placeholder_token_real:
  IPV4
{
  $$ = new_token_node (ctx, IPV4_TKN, $1, doc_next(ctx));
  XFREE (MTYPE_LEX, $1);
}
| IPV4_PREFIX
{
  $$ = new_token_node (ctx, IPV4_PREFIX_TKN, $1, doc_next(ctx));
  XFREE (MTYPE_LEX, $1);
}
| IPV6
{
  $$ = new_token_node (ctx, IPV6_TKN, $1, doc_next(ctx));
  XFREE (MTYPE_LEX, $1);
}
| IPV6_PREFIX
{
  $$ = new_token_node (ctx, IPV6_PREFIX_TKN, $1, doc_next(ctx));
  XFREE (MTYPE_LEX, $1);
}
| VARIABLE
{
  $$ = new_token_node (ctx, VARIABLE_TKN, $1, doc_next(ctx));
  XFREE (MTYPE_LEX, $1);
}
| RANGE
{
  $$ = new_token_node (ctx, RANGE_TKN, $1, doc_next(ctx));
  struct cmd_token *token = $$->data;

  // get the numbers out
  yylval.string++;
  token->min = strtoll (yylval.string, &yylval.string, 10);
  strsep (&yylval.string, "-");
  token->max = strtoll (yylval.string, &yylval.string, 10);

  // validate range
  if (token->min > token->max) cmd_yyerror (&@1, ctx, "Invalid range.");

  XFREE (MTYPE_LEX, $1);
}
| MAC
{
  $$ = new_token_node (ctx, MAC_TKN, $1, doc_next(ctx));
  XFREE (MTYPE_LEX, $1);
}
| MAC_PREFIX
{
  $$ = new_token_node (ctx, MAC_PREFIX_TKN, $1, doc_next(ctx));
  XFREE (MTYPE_LEX, $1);
}
| ASNUM
{
  $$ = new_token_node (ctx, ASNUM_TKN, $1, doc_next(ctx));
  XFREE (MTYPE_LEX, $1);
}

placeholder_token:
  placeholder_token_real varname_token
{
  $$ = $1;
  cmd_token_varname_set ($$->data, $2);
  XFREE (MTYPE_LEX, $2);
};


/* <selector|set> productions */
selector: '<' selector_seq_seq '>' varname_token
{
  $$ = $2;
  cmd_token_varname_join ($2.end, $4);
  XFREE (MTYPE_LEX, $4);
};

selector_seq_seq:
  selector_seq_seq '|' selector_token_seq
{
  $$ = $1;
  graph_add_edge ($$.start, $3.start);
  graph_add_edge ($3.end, $$.end);
}
| selector_token_seq
{
  $$.start = new_token_node (ctx, FORK_TKN, NULL, NULL);
  $$.end   = new_token_node (ctx, JOIN_TKN, NULL, NULL);
  ((struct cmd_token *)$$.start->data)->forkjoin = $$.end;
  ((struct cmd_token *)$$.end->data)->forkjoin = $$.start;

  graph_add_edge ($$.start, $1.start);
  graph_add_edge ($1.end, $$.end);
}
;

/* {keyword} productions */
selector: '{' selector_seq_seq '}' varname_token
{
  $$ = $2;
  graph_add_edge ($$.end, $$.start);
  /* there is intentionally no start->end link, for two reasons:
   * 1) this allows "at least 1 of" semantics, which are otherwise impossible
   * 2) this would add a start->end->start loop in the graph that the current
   *    loop-avoidal fails to handle
   * just use [{a|b}] if necessary, that will work perfectly fine, and reason
   * #1 is good enough to keep it this way. */

  loopcheck(ctx, &$$);
  cmd_token_varname_join ($2.end, $4);
  XFREE (MTYPE_LEX, $4);
};


selector_token:
  simple_token
{
  $$.start = $$.end = $1;
}
| selector
;

selector_token_seq:
  selector_token_seq selector_token
{
  graph_add_edge ($1.end, $2.start);
  cmd_token_varname_seqappend($2.start);
  $$.start = $1.start;
  $$.end   = $2.end;
}
| selector_token
;

/* [option] productions */
selector: '[' selector_seq_seq ']' varname_token
{
  $$ = $2;
  graph_add_edge ($$.start, $$.end);
  cmd_token_varname_join ($2.end, $4);
  XFREE (MTYPE_LEX, $4);
}
;

/* ![option] productions */
selector: EXCL_BRACKET selector_seq_seq ']' varname_token
{
  struct graph_node *neg_only = new_token_node (ctx, NEG_ONLY_TKN, NULL, NULL);

  $$ = $2;
  graph_add_edge ($$.start, neg_only);
  graph_add_edge (neg_only, $$.end);
  cmd_token_varname_join ($2.end, $4);
  XFREE (MTYPE_LEX, $4);
}
;

%%

#undef scanner

DEFINE_MTYPE(LIB, LEX, "Lexer token (temporary)");

void
cmd_graph_parse (struct graph *graph, const struct cmd_element *cmd)
{
  struct parser_ctx ctx = { .graph = graph, .el = cmd };

  // set to 1 to enable parser traces
  yydebug = 0;

  set_lexer_string (&ctx.scanner, cmd->string);

  // parse command into DFA
  cmd_yyparse (&ctx);

  /* cleanup lexer */
  cleanup_lexer (&ctx.scanner);

  // cleanup
  cleanup (&ctx);
}

/* parser helper functions */

static bool loopcheck_inner(struct graph_node *start, struct graph_node *node,
			    struct graph_node *end, size_t depth)
{
	size_t i;
	bool ret;

	/* safety check */
	if (depth++ == 64)
		return true;

	for (i = 0; i < vector_active(node->to); i++) {
		struct graph_node *next = vector_slot(node->to, i);
		struct cmd_token *tok = next->data;

		if (next == end || next == start)
			return true;
		if (tok->type < SPECIAL_TKN)
			continue;
		ret = loopcheck_inner(start, next, end, depth);
		if (ret)
			return true;
	}
	return false;
}

static void loopcheck(struct parser_ctx *ctx, struct subgraph *sg)
{
	if (loopcheck_inner(sg->start, sg->start, sg->end, 0))
		zlog_err("FATAL: '%s': {} contains an empty path! Use [{...}]",
			 ctx->el->string);
}

void
yyerror (CMD_YYLTYPE *loc, struct parser_ctx *ctx, char const *msg)
{
  char *tmpstr = strdup(ctx->el->string);
  char *line, *eol;
  char spacing[256];
  int lineno = 0;

  zlog_notice ("%s: FATAL parse error: %s", __func__, msg);
  zlog_notice ("%s: %d:%d-%d of this command definition:", __func__, loc->first_line, loc->first_column, loc->last_column);

  line = tmpstr;
  do {
    lineno++;
    eol = strchr(line, '\n');
    if (eol)
      *eol++ = '\0';

    zlog_notice ("%s: | %s", __func__, line);
    if (lineno == loc->first_line && lineno == loc->last_line
        && loc->first_column < (int)sizeof(spacing) - 1
        && loc->last_column < (int)sizeof(spacing) - 1) {

      int len = loc->last_column - loc->first_column;
      if (len == 0)
        len = 1;

      memset(spacing, ' ', loc->first_column - 1);
      memset(spacing + loc->first_column - 1, '^', len);
      spacing[loc->first_column - 1 + len] = '\0';
      zlog_notice ("%s: | %s", __func__, spacing);
    }
  } while ((line = eol));
  free(tmpstr);
}

static void
cleanup (struct parser_ctx *ctx)
{
  /* free resources */
  free (ctx->docstr_start);

  /* clear state pointers */
  ctx->currnode = NULL;
  ctx->docstr_start = ctx->docstr = NULL;
}

static void
terminate_graph (CMD_YYLTYPE *locp, struct parser_ctx *ctx,
                 struct graph_node *finalnode)
{
  // end of graph should look like this
  // * -> finalnode -> END_TKN -> cmd_element
  const struct cmd_element *element = ctx->el;
  struct graph_node *end_token_node =
    new_token_node (ctx, END_TKN, CMD_CR_TEXT, "");
  struct graph_node *end_element_node =
    graph_new_node (ctx->graph, (void *)element, NULL);

  if (ctx->docstr && strlen (ctx->docstr) > 1) {
    zlog_err ("Excessive docstring while parsing '%s'", ctx->el->string);
    zlog_err ("----------");
    while (ctx->docstr && ctx->docstr[1] != '\0')
      zlog_err ("%s", strsep(&ctx->docstr, "\n"));
    zlog_err ("----------");
  }

  graph_add_edge (finalnode, end_token_node);
  graph_add_edge (end_token_node, end_element_node);
}

static const char *
doc_next (struct parser_ctx *ctx)
{
  const char *piece = ctx->docstr ? strsep (&ctx->docstr, "\n") : "";
  if (*piece == 0x03)
  {
    zlog_err ("Ran out of docstring while parsing '%s'", ctx->el->string);
    piece = "";
  }

  return piece;
}

static struct graph_node *
new_token_node (struct parser_ctx *ctx, enum cmd_token_type type,
                const char *text, const char *doc)
{
  struct cmd_token *token = cmd_token_new (type, ctx->el->attr, text, doc);
  return graph_new_node (ctx->graph, token, (void (*)(void *)) &cmd_token_del);
}