summaryrefslogtreecommitdiffstats
path: root/lib/command_parse.y
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--lib/command_parse.y533
1 files changed, 533 insertions, 0 deletions
diff --git a/lib/command_parse.y b/lib/command_parse.y
new file mode 100644
index 0000000..8867e98
--- /dev/null
+++ b/lib/command_parse.y
@@ -0,0 +1,533 @@
+// 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);
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-12 11:46:25 +0000