lib: Allow nesting options in selectors

Options may now be nested in selectors as long
as they are not the first token in sequence.

Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>

1 files changed, 139 insertions, 138 deletions

diff --git a/lib/command_parse.y b/lib/command_parse.y
index cf829eeb5..1922ba229 100644
--- a/lib/command_parse.y
+++ b/lib/command_parse.y
@@ -62,6 +62,7 @@
   long long number;
   char *string;
   struct graph_node *node;
+  struct subgraph *subgraph;
 }
 
 /* union types for lexed tokens */
@@ -72,39 +73,36 @@
 %token <string> IPV6_PREFIX
 %token <string> VARIABLE
 %token <string> RANGE
-%token <number> NUMBER
 
 /* union types for parsed rules */
 %type <node> start
 %type <node> sentence_root
 %type <node> literal_token
 %type <node> placeholder_token
-%type <node> option
-%type <node> option_token
-%type <node> option_token_seq
-%type <node> selector
-%type <node> selector_token
-%type <node> selector_token_seq
+%type <node> simple_token
+%type <subgraph> option
+%type <subgraph> option_token
+%type <subgraph> option_token_seq
+%type <subgraph> selector
+%type <subgraph> selector_token
+%type <subgraph> selector_token_seq
+%type <subgraph> selector_seq_seq
+%type <subgraph> compound_token
 
 %code {
   /* bison declarations */
   void
   yyerror (struct graph *, struct cmd_element *el, char const *msg);
 
-  /* state variables for a single parser run */
-  struct graph_node *startnode;       // start node of DFA
+  /* subgraph semantic value */
+  struct subgraph {
+    struct graph_node *start, *end;
+  };
 
-  struct graph_node *currnode;        // current position in DFA
+  struct graph_node *currnode, *startnode;
 
-  struct graph_node *optnode_start,   // start node for option set
-                    *optnode_seqtail, // sequence tail for option sequence
-                    *optnode_end;     // end node for option set
-
-  struct graph_node *selnode_start,   // start node for selector set
-                    *selnode_seqtail, // sequence tail for selector sequence
-                    *selnode_end;     // end node for selector set
-
-  char *docstr_start, *docstr;        // pointers to copy of command docstring
+  /* pointers to copy of command docstring */
+  char *docstr_start, *docstr;
 
   /* helper functions for parser */
   static char *
@@ -124,9 +122,6 @@
                   enum cmd_token_type_t type,
                   char *text, char *doc);
 
-  static struct graph_node *
-  find_tail (struct graph_node *);
-
   static void
   terminate_graph (struct graph *,
                    struct graph_node *,
@@ -142,12 +137,10 @@
 
 /* called automatically before yyparse */
 %initial-action {
-  startnode = vector_slot (graph->nodes, 0);
-
   /* clear state pointers */
-  currnode = NULL;
-  selnode_start = selnode_seqtail = selnode_end = NULL;
-  optnode_start = optnode_seqtail = optnode_end = NULL;
+  currnode = startnode = NULL;
+
+  startnode = vector_slot (graph->nodes, 0);
 
   /* set string to parse */
   set_lexer_string (element->string);
@@ -165,10 +158,10 @@ start:
   // tack on the command element
   terminate_graph (graph, currnode, element);
 }
-| sentence_root cmd_token_seq '.' placeholder_token
+| sentence_root cmd_token_seq placeholder_token '.' '.' '.'
 {
-  if ((currnode = add_edge_dedup (currnode, $4)) != $4)
-    graph_delete_node (graph, $4);
+  if ((currnode = add_edge_dedup (currnode, $3)) != $3)
+    graph_delete_node (graph, $3);
 
   // adding a node as a child of itself accepts any number
   // of the same token, which is what we want for varags
@@ -177,46 +170,55 @@ start:
   // tack on the command element
   terminate_graph (graph, currnode, element);
 }
+;
 
 sentence_root: WORD
 {
   struct graph_node *root =
-    new_token_node (graph, WORD_TKN, XSTRDUP(MTYPE_CMD_TOKENS, $1), doc_next());
+    new_token_node (graph, WORD_TKN, XSTRDUP (MTYPE_CMD_TOKENS, $1), doc_next());
 
   if ((currnode = add_edge_dedup (startnode, root)) != root)
     graph_delete_node (graph, root);
 
   free ($1);
   $$ = currnode;
-};
+}
+;
+
+cmd_token_seq:
+  %empty
+| cmd_token_seq cmd_token
+;
 
 cmd_token:
-  placeholder_token
-{
-  if ((currnode = add_edge_dedup (currnode, $1)) != $1)
-    graph_delete_node (graph, $1);
-}
-| literal_token
+  simple_token
 {
   if ((currnode = add_edge_dedup (currnode, $1)) != $1)
     graph_delete_node (graph, $1);
 }
-/* selectors and options are subgraphs with start and end nodes */
-| selector
+| compound_token
 {
-  graph_add_edge (currnode, $1);
-  currnode = find_tail ($1);
+  graph_add_edge (currnode, $1->start);
+  currnode = $1->end;
+  XFREE (MTYPE_TMP, $1);
 }
+;
+
+simple_token:
+  literal_token
+| placeholder_token
+;
+
+compound_token:
+  selector
 | option
-{
-  graph_add_edge (currnode, $1);
-  currnode = find_tail ($1);
-}
 ;
 
-cmd_token_seq:
-  %empty
-| cmd_token_seq cmd_token
+literal_token: WORD
+{
+  $$ = new_token_node (graph, WORD_TKN, XSTRDUP(MTYPE_CMD_TOKENS, $1), doc_next());
+  free ($1);
+}
 ;
 
 placeholder_token:
@@ -257,117 +259,129 @@ placeholder_token:
   token->max = strtoll (yylval.string, &yylval.string, 10);
 
   // validate range
-  if (token->min >= token->max) yyerror (graph, element, "Invalid range.");
-
-  free ($1);
-}
-;
+  if (token->min > token->max) yyerror (graph, element, "Invalid range.");
 
-literal_token:
-  WORD
-{
-  $$ = new_token_node (graph, WORD_TKN, XSTRDUP(MTYPE_CMD_TOKENS, $1), doc_next());
   free ($1);
 }
-| NUMBER
-{
-  $$ = new_token_node (graph, NUMBER_TKN, NULL, doc_next());
-  struct cmd_token_t *token = $$->data;
-
-  token->value = yylval.number;
-  token->text = XCALLOC(MTYPE_CMD_TOKENS, DECIMAL_STRLEN_MAX+1);
-  snprintf(token->text, DECIMAL_STRLEN_MAX, "%lld", token->value);
-}
 ;
 
 /* <selector|set> productions */
-selector: '<' selector_part '>'
-{
-  // all the graph building is done in selector_element,
-  // so just return the selector subgraph head
-  $$ = selnode_start;
-  selnode_start = selnode_end = NULL;
+selector: '<' selector_seq_seq '>'
+{
+  $$ = XMALLOC (MTYPE_TMP, sizeof (struct subgraph));
+  $$->start = new_token_node (graph, SELECTOR_TKN, NULL, NULL);
+  $$->end   = new_token_node (graph, NUL_TKN, NULL, NULL);
+  for (unsigned int i = 0; i < vector_active ($2->start->to); i++)
+  {
+    struct graph_node *sn = vector_slot ($2->start->to, i),
+                      *en = vector_slot ($2->end->from, i);
+    graph_add_edge ($$->start, sn);
+    graph_add_edge (en, $$->end);
+  }
+  graph_delete_node (graph, $2->start);
+  graph_delete_node (graph, $2->end);
+  XFREE (MTYPE_TMP, $2);
 };
 
-selector_part:
-  selector_part '|' selector_element
-| selector_element '|' selector_element
-;
-
-selector_element: selector_token_seq
+selector_seq_seq:
+  selector_seq_seq '|' selector_token_seq
 {
-  // if the selector start and end do not exist, create them
-  if (!selnode_start || !selnode_end) {
-    assert(!selnode_start && !selnode_end);
-    selnode_start = new_token_node (graph, SELECTOR_TKN, NULL, NULL);
-    selnode_end = new_token_node (graph, NUL_TKN, NULL, NULL);
-  }
+  $$ = XMALLOC (MTYPE_TMP, sizeof (struct subgraph));
+  $$->start = graph_new_node (graph, NULL, NULL);
+  $$->end   = graph_new_node (graph, NULL, NULL);
 
-  // add element head as a child of the selector
-  graph_add_edge (selnode_start, $1);
-  graph_add_edge (selnode_seqtail, selnode_end);
+  // link in last sequence
+  graph_add_edge ($$->start, $3->start);
+  graph_add_edge ($3->end, $$->end);
+  XFREE (MTYPE_TMP, $3);
 
-  selnode_seqtail = NULL;
+  for (unsigned int i = 0; i < vector_active ($1->start->to); i++)
+  {
+    struct graph_node *sn = vector_slot ($1->start->to, i),
+                      *en = vector_slot ($1->end->from, i);
+    graph_add_edge ($$->start, sn);
+    graph_add_edge (en, $$->end);
+  }
+  graph_delete_node (graph, $1->start);
+  graph_delete_node (graph, $1->end);
+  XFREE (MTYPE_TMP, $1);
+  XFREE (MTYPE_TMP, $3);
+}
+| selector_token_seq '|' selector_token_seq
+{
+  $$ = XMALLOC (MTYPE_TMP, sizeof (struct subgraph));
+  $$->start = graph_new_node (graph, NULL, NULL);
+  $$->end   = graph_new_node (graph, NULL, NULL);
+  graph_add_edge ($$->start, $1->start);
+  graph_add_edge ($1->end, $$->end);
+  graph_add_edge ($$->start, $3->start);
+  graph_add_edge ($3->end, $$->end);
+  XFREE (MTYPE_TMP, $1);
+  XFREE (MTYPE_TMP, $3);
 }
+;
 
 selector_token_seq:
-  selector_token
+  simple_token
 {
-  assert (!selnode_seqtail);
-  selnode_seqtail = $1;
+  $$ = XMALLOC (MTYPE_TMP, sizeof (struct subgraph));
+  $$->start = $$->end = $1;
 }
 | selector_token_seq selector_token
 {
-  graph_add_edge ($1, $2);
-  selnode_seqtail = $2;
+  $$ = XMALLOC (MTYPE_TMP, sizeof (struct subgraph));
+  graph_add_edge ($1->end, $2->start);
+  $$->start = $1->start;
+  $$->end   = $2->end;
+  XFREE (MTYPE_TMP, $1);
+  XFREE (MTYPE_TMP, $2);
 }
 ;
 
 selector_token:
-  literal_token
-| placeholder_token
-;
-
-/* [optional] productions */
-option: '[' option_element ']'
+  simple_token
 {
-  // add null path
-  graph_add_edge (optnode_start, optnode_end);
-  $$ = optnode_start;
-  optnode_start = optnode_end = NULL;
-};
+  $$ = XMALLOC (MTYPE_TMP, sizeof (struct subgraph));
+  $$->start = $$->end = $1;
+}
+| option
+;
 
-option_element: option_token_seq
+/* [option] productions */
+option: '[' option_token_seq ']'
 {
-  if (!optnode_start || !optnode_end) {
-    assert (!optnode_start && !optnode_end);
-    optnode_start = new_token_node (graph, OPTION_TKN, NULL, NULL);
-    optnode_end = new_token_node (graph, NUL_TKN, NULL, NULL);
-  }
-
-  graph_add_edge (optnode_start, $1);
-  graph_add_edge (optnode_seqtail, optnode_end);
-  optnode_seqtail = NULL;
+  // make a new option
+  $$ = XMALLOC (MTYPE_TMP, sizeof (struct subgraph));
+  $$->start = new_token_node (graph, OPTION_TKN, NULL, NULL);
+  $$->end   = new_token_node (graph, NUL_TKN, NULL, NULL);
+  // add a path through the sequence to the end
+  graph_add_edge ($$->start, $2->start);
+  graph_add_edge ($2->end, $$->end);
+  // add a path directly from the start to the end
+  graph_add_edge ($$->start, $$->end);
+  XFREE (MTYPE_TMP, $2);
 }
+;
 
 option_token_seq:
   option_token
-{
-  assert (!optnode_seqtail);
-  optnode_seqtail = find_tail ($1);
-}
 | option_token_seq option_token
 {
-  graph_add_edge (find_tail ($1), $2);
-//  exit (EXIT_FAILURE);
-  optnode_seqtail = find_tail ($2);
+  $$ = XMALLOC (MTYPE_TMP, sizeof (struct subgraph));
+  graph_add_edge ($1->end, $2->start);
+  $$->start = $1->start;
+  $$->end   = $2->end;
+  XFREE (MTYPE_TMP, $1);
 }
 ;
 
 option_token:
-  literal_token
-| placeholder_token
-| selector
+  simple_token
+{
+  $$ = XMALLOC (MTYPE_TMP, sizeof (struct subgraph));
+  $$->start = $$->end = $1;
+}
+| compound_token
 ;
 
 %%
@@ -407,8 +421,6 @@ cleanup()
   /* clear state pointers */
   currnode = NULL;
   docstr_start = docstr = NULL;
-  selnode_start = selnode_seqtail = selnode_end = NULL;
-  optnode_start = selnode_seqtail = optnode_end = NULL;
 }
 
 static void
@@ -466,17 +478,6 @@ node_adjacent (struct graph_node *first, struct graph_node *second)
 }
 
 /**
- * Walks down the left side of graph, returning the first encountered node with
- * no children.
- */
-static struct graph_node *
-find_tail (struct graph_node *node)
-{
-  while (vector_active (node->to) > 0)
-    node = vector_slot (node->to, 0);
-  return node;
-}
-/**
  * Creates an edge betwen two nodes, unless there is already an edge to an
  * equivalent node.
  *