lib: Implement node comparison function

Implement comparator for nodes, some miscellaneous cleanup.

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

4 files changed, 111 insertions, 40 deletions

diff --git a/lib/cmdtree.c b/lib/cmdtree.c
index da647a7ae..38632dca4 100644
--- a/lib/cmdtree.c
+++ b/lib/cmdtree.c
@@ -13,12 +13,11 @@
 struct graph_node *
 add_node(struct graph_node *parent, struct graph_node *child)
 {
-  unsigned int index;
   struct graph_node *p_child;
 
-  for (index = 0; index < vector_active(parent->children); index++)
+  for (unsigned int i = 0; i < vector_active(parent->children); i++)
   {
-    p_child = vector_slot(parent->children, index);
+    p_child = vector_slot(parent->children, i);
     if (cmp_node(child, p_child))
       return p_child;
   }
@@ -29,7 +28,36 @@ add_node(struct graph_node *parent, struct graph_node *child)
 int
 cmp_node(struct graph_node *first, struct graph_node *second)
 {
-  return 0;
+  // compare types
+  if (first->type != second->type) return 0;
+
+  switch (first->type) {
+    case WORD_GN:       // words and variables are equal if their
+    case VARIABLE_GN:   // text value is equal
+      if (first->text && second->text) {
+        if (strcmp(first->text, second->text)) return 0;
+      }
+      else if (first->text != second->text) return 0;
+      break;
+    case RANGE_GN:      // ranges are equal if their bounds are equal
+      if (first->min != second->min || first->max != second->max)
+        return 0;
+      break;
+    case NUMBER_GN:     // numbers are equal if their values are equal
+      if (first->value != second->value) return 0;
+      break;
+    /* selectors and options should be equal if all paths are equal,
+     * but the graph isomorphism problem is not solvable in polynomial
+     * time so we consider selectors and options inequal in all cases
+     */
+    case SELECTOR_GN:
+    case OPTION_GN:
+      return 0;
+    default:
+      break;
+  }
+
+  return 1;
 }
 
 struct graph_node *
@@ -40,6 +68,11 @@ new_node(enum graph_node_type type)
   node->children = vector_init(VECTOR_MIN_SIZE);
   node->is_leaf = 0;
   node->is_root = 0;
+  node->end = NULL;
+  node->text = NULL;
+  node->value = 0;
+  node->min   = 0;
+  node->max   = 0;
   node->func = NULL;
 
   return node;
@@ -77,22 +110,24 @@ walk_graph(struct graph_node *start, int level)
   fprintf(stderr, "[%d] ", vector_active(start->children));
 
   if (vector_active(start->children))
-    for (unsigned int i = 0; i < vector_active(start->children); i++) {
+    for (unsigned int i = 0; i < vector_active(start->children); i++)
+    {
       struct graph_node *r = vector_slot(start->children, i);
       if (!r) {
         fprintf(stderr, "Child seems null?\n");
         break;
       }
       else {
-        if (start->type == OPTION_GN || start->type == SELECTOR_GN) {
+        if (vector_active(start->children) > 1) {
           fprintf(stderr, "\n");
           for (int i = 0; i < level+1; i++)
-            fprintf(stderr, "\t");
+            fprintf(stderr, "    ");
+          walk_graph(r, level+1);
         }
-        walk_graph(r, level+1);
+        else
+          walk_graph(r, level);
       }
     }
-  else {
+  if (level == 0)
     fprintf(stderr, "\n");
-  }
 }
diff --git a/lib/cmdtree.h b/lib/cmdtree.h
index 9b512e3bb..3d2366b00 100644
--- a/lib/cmdtree.h
+++ b/lib/cmdtree.h
@@ -20,20 +20,23 @@ struct graph_node
 {
   enum graph_node_type type;
   vector children;
-  int is_root;      // true if first token in command
-  int is_leaf;      // true if last token in command
+  int is_root;              // true if first token in command
+  int is_leaf;              // true if last token in command
+  struct graph_node * end;  // pointer to end for selector & option
 
   int (*func)(struct vty *, int, const char *[]);
 
   /* various data fields for nodes */
   char* text;       // for words and variables
   int value;        // for numbers
-  int start, end;   // for ranges
+  int min, max;     // for ranges
 };
 
 /*
- * Adds a child to a node. If the node already has the exact same
- * child, nothing is done.
+ * Adds a child to a node.
+ * If the node already has the exact same child, nothing is done. This is
+ * decided with cmp_node.
+ *
  * @param[in] parent node
  * @param[in] child node
  * @return the new child, or the existing child if the parent already has the
@@ -43,16 +46,35 @@ extern struct graph_node *
 add_node(struct graph_node *, struct graph_node *);
 
 /*
- * Compares two nodes for equivalence.
- * What exactly constitutes two nodes being equal depends on the
- * node type.
- * @return 0 if equal, nonzero otherwise.
+ * Compares two nodes for parsing equivalence.
+ * Equivalence in this case means that a single user input token
+ * should be able to unambiguously match one of the two nodes.
+ * For example, two nodes which have all fields equal except their
+ * function pointers would be considered equal.
+ *
+ * @param[in] first node to compare
+ * @param[in] second node to compare
+ * @return 1 if equal, zero otherwise.
  */
 extern int
-cmp_node(struct graph_node *first, struct graph_node *second);
+cmp_node(struct graph_node *, struct graph_node *);
 
+/*
+ * Create a new node.
+ * Initializes all fields to default values and sets the node type.
+ *
+ * @param[in] node type
+ * @return pointer to the newly allocated node
+ */
 extern struct graph_node *
-new_node(enum graph_node_type type);
+new_node(enum graph_node_type);
 
+/**
+ * Walks a command DFA, printing structure to stdout.
+ * For debugging.
+ *
+ * @param[in] start node of graph to walk
+ * @param[in] graph depth for recursion, caller passes 0
+ */
 extern void
 walk_graph(struct graph_node *, int);
diff --git a/lib/command_parse.y b/lib/command_parse.y
index 7bdec6dca..cf2cd95bd 100644
--- a/lib/command_parse.y
+++ b/lib/command_parse.y
@@ -48,7 +48,7 @@ struct graph_node *selnode_start,   // start node for selector set
 %type <node> option_token
 %type <node> option_token_seq
 %type <node> selector
-%type <node> selector_root
+%type <node> selector_element_root
 %type <node> selector_token
 %type <node> selector_token_seq
 
@@ -70,7 +70,7 @@ sentence_root: WORD
 
   currnode = $$;
   currnode->is_root = 1;
-  add_node(startnode, currnode);
+  currnode = add_node(startnode, currnode);
 };
 
 /* valid top level tokens */
@@ -106,22 +106,22 @@ placeholder_token:
   $$->text = strdup(yylval.string);
 }
 | IPV4_PREFIX
-{ 
+{
   $$ = new_node(IPV4_PREFIX_GN);
   $$->text = strdup(yylval.string);
 }
 | IPV6
-{ 
+{
   $$ = new_node(IPV6_GN);
   $$->text = strdup(yylval.string);
 }
 | IPV6_PREFIX
-{ 
+{
   $$ = new_node(IPV6_PREFIX_GN);
   $$->text = strdup(yylval.string);
 }
 | VARIABLE
-{ 
+{
   $$ = new_node(VARIABLE_GN);
   $$->text = strdup(yylval.string);
 }
@@ -132,9 +132,9 @@ placeholder_token:
 
   // get the numbers out
   strsep(&yylval.string, "(-)");
-  $$->start = atoi( strsep(&yylval.string, "(-)") );
+  $$->min = atoi( strsep(&yylval.string, "(-)") );
   strsep(&yylval.string, "(-)");
-  $$->end   = atoi( strsep(&yylval.string, "(-)") );
+  $$->max = atoi( strsep(&yylval.string, "(-)") );
 
   // we could do this a variety of ways with either
   // the lexer or the parser, but this is the simplest
@@ -148,7 +148,7 @@ literal_token:
   $$ = new_node(WORD_GN);
   $$->text = strdup(yylval.string);
   fprintf(stderr, ">>>>>>>> YYLVAL.STRING: %s\n", yylval.string);
-  fprintf(stderr, ">>>>>>>> TEXT: %s\n", $$->text);
+  fprintf(stderr, ">>>>>>>>          TEXT: %s\n", $$->text);
 }
 | NUMBER
 {
@@ -172,13 +172,14 @@ selector_part:
 ;
 
 selector_element:
-  selector_root selector_token_seq
+  selector_element_root selector_token_seq
 {
   // if the selector start and end do not exist, create them
   if (!selnode_start || !selnode_end) {     // if one is null
     assert(!selnode_start && !selnode_end); // both should be null
     selnode_start = new_node(SELECTOR_GN);  // diverging node
     selnode_end = new_node(NUL_GN);         // converging node
+    selnode_start->end = selnode_end;       // duh
   }
 
   // add element head as a child of the selector
@@ -210,13 +211,13 @@ selector_token_seq:
 }
 ;
 
-selector_root:
+selector_element_root:
   literal_token
 | placeholder_token
 ;
 
 selector_token:
-  selector_root
+  selector_element_root
 | option
 ;
 
diff --git a/lib/grammar_sandbox.c b/lib/grammar_sandbox.c
index 0cc6896d8..807ada9d9 100644
--- a/lib/grammar_sandbox.c
+++ b/lib/grammar_sandbox.c
@@ -4,9 +4,11 @@
 
 #define GRAMMAR_STR "CLI grammar sandbox\n"
 
+struct graph_node * nodegraph;
+
 DEFUN (grammar_test,
        grammar_test_cmd,
-       "grammar .COMMAND",
+       "grammar parse .COMMAND",
        GRAMMAR_STR
        "command to pass to new parser\n")
 {
@@ -22,17 +24,28 @@ DEFUN (grammar_test,
       strcat(cat, " ");
   }
 
-  struct graph_node *result = new_node(NUL_GN);
-  /* cmd_parse_format_new((const char*) cat, "lol", result);*/
-  cmd_parse_format_new ("test <command|options> lol", "lol", result);
-  cmd_parse_format_new ("test <command|options> lol", "lol", result);
-  walk_graph(result, 0);
-  
+  //struct graph_node *result = new_node(NUL_GN);
+  cmd_parse_format_new((const char*) cat, "lol", nodegraph);
+  walk_graph(nodegraph, 0);
+
   return CMD_SUCCESS;
 }
 
+DEFUN (grammar_test_show,
+       grammar_test_show_cmd,
+       "grammar tree",
+       GRAMMAR_STR
+       "print current accumulated DFA\n")
+{
+   walk_graph(nodegraph, 0);
+   return CMD_SUCCESS;
+}
+
 
 void grammar_sandbox_init(void);
 void grammar_sandbox_init() {
+  fprintf(stderr, "reinitializing graph\n");
+  nodegraph = new_node(NUL_GN);
   install_element (ENABLE_NODE, &grammar_test_cmd);
+  install_element (ENABLE_NODE, &grammar_test_show_cmd);
 }