From 1eb5e8dcd17d84959a46a2d837ae719fc8eb3516 Mon Sep 17 00:00:00 2001
From: Quentin Young <qlyoung@cumulusnetworks.com>
Date: Wed, 7 Sep 2016 04:05:07 +0000
Subject: [PATCH] lib: Continue matching system refactor

Most things back to working, all CLI units refactored
to use improved graph implementation.

Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
---
 lib/command.c         |   2 +-
 lib/command.h         |   2 +-
 lib/command_match.c   | 292 ++++++++++++++++++++++--------------------
 lib/command_match.h   |  19 ++-
 lib/command_parse.y   | 186 ++++++++++++++++-----------
 lib/grammar_sandbox.c |  84 +++++++++---
 lib/grammar_sandbox.h |  48 ++++---
 lib/graph.c           |  38 +++---
 lib/graph.h           |  15 +--
 9 files changed, 396 insertions(+), 290 deletions(-)

diff --git a/lib/command.c b/lib/command.c
index faaa50a6f..5bc157c85 100644
--- a/lib/command.c
+++ b/lib/command.c
@@ -4191,7 +4191,7 @@ cmd_terminate_element(struct cmd_element *cmd)
 }
 
 void
-free_cmd_element(struct cmd_element *cmd)
+del_cmd_element(struct cmd_element *cmd)
 {
   if (!cmd) return;
   free ((char*) cmd->string);
diff --git a/lib/command.h b/lib/command.h
index 9a77d3b87..6d0fb1806 100644
--- a/lib/command.h
+++ b/lib/command.h
@@ -573,7 +573,7 @@ extern void cmd_terminate (void);
 
 /* memory management for cmd_element */
 void
-free_cmd_element(struct cmd_element *);
+del_cmd_element(struct cmd_element *);
 struct cmd_element *
 copy_cmd_element(struct cmd_element *cmd);
 
diff --git a/lib/command_match.c b/lib/command_match.c
index 95891dd82..0b8cc9921 100644
--- a/lib/command_match.c
+++ b/lib/command_match.c
@@ -25,6 +25,7 @@
 #include <zebra.h>
 #include "command_match.h"
 #include "command_parse.h"
+#include "grammar_sandbox.h"
 #include "memory.h"
 
 /* matcher helper prototypes */
@@ -35,19 +36,16 @@ static struct list *
 command_match_r (struct graph_node *, vector, unsigned int);
 
 static int
-score_precedence (enum graph_node_type);
+score_precedence (enum cmd_token_type_t);
 
 static enum match_type
-min_match_level (enum node_type);
-
-static struct graph_node *
-copy_node (struct graph_node *);
+min_match_level (enum cmd_token_type_t);
 
 static void
-delete_nodelist (void *);
+del_arglist (struct list *);
 
-static struct graph_node *
-disambiguate_nodes (struct graph_node *, struct graph_node *, char *);
+static struct cmd_token_t *
+disambiguate_tokens (struct cmd_token_t *, struct cmd_token_t *, char *);
 
 static struct list *
 disambiguate (struct list *, struct list *, vector, unsigned int);
@@ -57,7 +55,7 @@ compare_completions (const void *, const void *);
 
 /* token matcher prototypes */
 static enum match_type
-match_token (struct graph_node *, char *);
+match_token (struct cmd_token_t *, char *);
 
 static enum match_type
 match_ipv4 (const char *);
@@ -72,22 +70,22 @@ static enum match_type
 match_ipv6_prefix (const char *);
 
 static enum match_type
-match_range (struct graph_node *, const char *);
+match_range (struct cmd_token_t *, const char *);
 
 static enum match_type
-match_word (struct graph_node *, const char *);
+match_word (struct cmd_token_t *, const char *);
 
 static enum match_type
-match_number (struct graph_node *, const char *);
+match_number (struct cmd_token_t *, const char *);
 
 static enum match_type
-match_variable (struct graph_node *node, const char *word);
+match_variable (struct cmd_token_t *, const char *);
 
 /* matching functions */
 static enum matcher_rv matcher_rv;
 
 enum matcher_rv
-command_match (struct graph_node *start,
+command_match (struct graph *cmdgraph,
                vector vline,
                struct list **argv,
                struct cmd_element **el)
@@ -100,11 +98,19 @@ command_match (struct graph_node *start,
   memcpy (vvline->index + 1, vline->index, sizeof (void *) * vline->alloced);
   vvline->active = vline->active + 1;
 
+  struct graph_node *start = vector_slot (cmdgraph->nodes, 0);
   if ((*argv = command_match_r (start, vvline, 0))) // successful match
     {
+      // delete dummy start node
       list_delete_node (*argv, listhead (*argv));
-      struct graph_node *end = listgetdata (listtail (*argv));
-      *el = end->element;
+      // get cmd_element out of list tail
+      struct listnode *tail = listtail (*argv);
+      *el = listgetdata (tail);
+      // delete list tail
+      tail->data = NULL;
+      list_delete_node (*argv, tail);
+      // now argv is an ordered list of cmd_token matching the user
+      // input, with each cmd_token->arg holding the corresponding input
       assert (*el);
     }
 
@@ -120,7 +126,7 @@ command_match (struct graph_node *start,
  *
  * The next step is to see if there is further input in the input line. If
  * there is not, the current node's children are searched to see if any of them
- * are leaves (type END_GN). If this is the case, then the bottom of the
+ * are leaves (type END_TKN). If this is the case, then the bottom of the
  * recursion stack has been reached, the leaf is pushed onto the argument list,
  * the current node is pushed, and the resulting argument list is
  * returned (MATCHER_OK). If it is not the case, NULL is returned, indicating
@@ -165,13 +171,14 @@ command_match_r (struct graph_node *start, vector vline, unsigned int n)
   assert (n < vector_active (vline));
 
   // get the minimum match level that can count as a full match
-  enum match_type minmatch = min_match_level (start->type);
+  struct cmd_token_t *token = start->data;
+  enum match_type minmatch = min_match_level (token->type);
 
-  // get the current operating token
-  char *token = vector_slot (vline, n);
+  // get the current operating input token
+  char *input_token = vector_slot (vline, n);
 
   // if we don't match this node, die
-  if (match_token (start, token) < minmatch)
+  if (match_token (token, input_token) < minmatch)
     return NULL;
 
   // pointers for iterating linklist
@@ -187,14 +194,22 @@ command_match_r (struct graph_node *start, vector vline, unsigned int n)
   struct list *currbest = NULL;
   for (ALL_LIST_ELEMENTS_RO (next,ln,gn))
     {
-      // if we've matched all input we're looking for END_GN
+      // if we've matched all input we're looking for END_TKN
       if (n+1 == vector_active (vline))
         {
-          if (gn->type == END_GN)
+          struct cmd_token_t *tok = gn->data;
+          if (tok->type == END_TKN)
             {
               currbest = list_new();
-              listnode_add (currbest, copy_node(gn));
-              currbest->del = &delete_nodelist;
+              // node should have one child node with the element
+              struct graph_node *leaf = vector_slot (gn->to, 0);
+              // last node in the list will hold the cmd_element;
+              // this is important because list_delete() expects
+              // that all nodes have the same data type, so when
+              // deleting this list the last node must be
+              // manually deleted
+              listnode_add (currbest, leaf->data);
+              currbest->del = (void (*)(void *)) &del_cmd_token;
               break;
             }
           else continue;
@@ -206,9 +221,17 @@ command_match_r (struct graph_node *start, vector vline, unsigned int n)
       // save the best match
       if (result && currbest)
         {
+          // pick the best of two matches
           struct list *newbest = disambiguate (currbest, result, vline, n+1);
+          // set ambiguity flag
           ambiguous = !newbest || (ambiguous && newbest == currbest);
-          list_delete ((newbest && newbest == result) ? currbest : result);
+          // choose the list to be deleted
+          struct list *todelete = ((newbest && newbest == result) ? currbest : result);
+          // manually delete the last node, which has a cmd_element
+          del_cmd_element (listgetdata (listtail (todelete)));
+          // use the list->del callback to delete the rest of the list
+          list_delete (todelete);
+
           currbest = newbest ? newbest : currbest;
         }
       else if (result)
@@ -219,16 +242,16 @@ command_match_r (struct graph_node *start, vector vline, unsigned int n)
     {
       if (ambiguous)
         {
-          list_delete (currbest);
-          currbest = NULL;
+          del_arglist (currbest);
           matcher_rv = MATCHER_AMBIGUOUS;
         }
       else
         {
-          // copy current node, set arg and prepend to currbest
-          struct graph_node *curr = copy_node (start);
-          curr->arg = XSTRDUP(MTYPE_CMD_TOKENS, token);
-          list_add_node_prev (currbest, currbest->head, curr);
+          // copy token, set arg and prepend to currbest
+          struct cmd_token_t *token = start->data;
+          struct cmd_token_t *copy = copy_cmd_token (token);
+          copy->arg = XSTRDUP(MTYPE_CMD_TOKENS, input_token);
+          list_add_node_prev (currbest, currbest->head, copy);
           matcher_rv = MATCHER_OK;
         }
     }
@@ -242,12 +265,12 @@ command_match_r (struct graph_node *start, vector vline, unsigned int n)
 }
 
 enum matcher_rv
-command_complete (struct graph_node *start,
+command_complete (struct graph *graph,
                   vector vline,
                   struct list **completions)
 {
   // pointer to next input token to match
-  char *token;
+  char *input_token;
 
   struct list *current = list_new(), // current nodes to match input token against
                  *next = list_new(); // possible next hops after current input token
@@ -257,6 +280,7 @@ command_complete (struct graph_node *start,
   struct listnode *node;
 
   // add all children of start node to list
+  struct graph_node *start = vector_slot (graph->nodes, 0);
   add_nexthops (next, start);
 
   unsigned int idx;
@@ -266,11 +290,12 @@ command_complete (struct graph_node *start,
       current = next;
       next = list_new();
 
-      token = vector_slot (vline, idx);
+      input_token = vector_slot (vline, idx);
 
       for (ALL_LIST_ELEMENTS_RO (current,node,gn))
         {
-          switch (match_token (gn, token))
+          struct cmd_token_t *token = gn->data;
+          switch (match_token (token, input_token))
             {
               case partly_match:
                 if (idx == vector_active (vline) - 1)
@@ -300,19 +325,24 @@ command_complete (struct graph_node *start,
      MATCHER_OK :
      MATCHER_NO_MATCH;
 
+  // extract cmd_token into list
+  *completions = list_new ();
+  for (ALL_LIST_ELEMENTS_RO (next,node,gn))
+    listnode_add (*completions, gn->data);
+
   list_free (current);
-  *completions = next;
+  list_free (next);
 
   return matcher_rv;
 }
 
 /**
+ * TODO: move this logic to command.c
  * Compare two completions. Tightly coupled to vector.
  *
  * @param[in] fst pointer to first item pointer in vector->index
  * @param[in] snd pointer to second item poitner in vector->index
  * @return integer compare code as determined by strcmp
- */
 int
 compare_completions (const void *fst, const void *snd)
 {
@@ -353,10 +383,11 @@ command_complete_str (struct graph_node *start,
   list_delete (comps);
   return rv;
 }
+*/
 
 /**
  * Adds all children that are reachable by one parser hop to the given list.
- * NUL_GN, SELECTOR_GN, and OPTION_GN nodes are treated as transparent.
+ * NUL_TKN, SELECTOR_TKN, and OPTION_TKN nodes are treated as transparent.
  *
  * @param[in] list to add the nexthops to
  * @param[in] node to start calculating nexthops from
@@ -367,14 +398,15 @@ add_nexthops (struct list *list, struct graph_node *node)
 {
   int added = 0;
   struct graph_node *child;
-  for (unsigned int i = 0; i < vector_active (node->children); i++)
+  for (unsigned int i = 0; i < vector_active (node->to); i++)
     {
-      child = vector_slot (node->children, i);
-      switch (child->type)
+      child = vector_slot (node->to, i);
+      struct cmd_token_t *token = child->data;
+      switch (token->type)
         {
-          case OPTION_GN:
-          case SELECTOR_GN:
-          case NUL_GN:
+          case OPTION_TKN:
+          case SELECTOR_TKN:
+          case NUL_TKN:
             added += add_nexthops (list, child);
             break;
           default:
@@ -394,15 +426,15 @@ add_nexthops (struct list *list, struct graph_node *node)
  * @return minimum match level needed to for a token to fully match
  */
 static enum match_type
-min_match_level (enum node_type type)
+min_match_level (enum cmd_token_type_t type)
 {
   switch (type)
     {
       // anything matches a start node, for the sake of recursion
-      case START_GN:
+      case START_TKN:
         return no_match;
       // allowing words to partly match enables command abbreviation
-      case WORD_GN:
+      case WORD_TKN:
         return partly_match;
       default:
         return exact_match;
@@ -416,23 +448,23 @@ min_match_level (enum node_type type)
  * @return precedence score
  */
 static int
-score_precedence (enum graph_node_type type)
+score_precedence (enum cmd_token_type_t type)
 {
   switch (type)
     {
       // some of these are mutually exclusive, so they share
       // the same precedence value
-      case IPV4_GN:
-      case IPV4_PREFIX_GN:
-      case IPV6_GN:
-      case IPV6_PREFIX_GN:
-      case NUMBER_GN:
+      case IPV4_TKN:
+      case IPV4_PREFIX_TKN:
+      case IPV6_TKN:
+      case IPV6_PREFIX_TKN:
+      case NUMBER_TKN:
         return 1;
-      case RANGE_GN:
+      case RANGE_TKN:
         return 2;
-      case WORD_GN:
+      case WORD_TKN:
         return 3;
-      case VARIABLE_GN:
+      case VARIABLE_TKN:
         return 4;
       default:
         return 10;
@@ -447,10 +479,10 @@ score_precedence (enum graph_node_type type)
  * @param[in] token the token being matched
  * @return the best-matching node, or NULL if the two are entirely ambiguous
  */
-static struct graph_node *
-disambiguate_nodes (struct graph_node *first,
-                    struct graph_node *second,
-                    char *token)
+static struct cmd_token_t *
+disambiguate_tokens (struct cmd_token_t *first,
+                     struct cmd_token_t *second,
+                     char *input_token)
 {
   // if the types are different, simply go off of type precedence
   if (first->type != second->type)
@@ -464,8 +496,8 @@ disambiguate_nodes (struct graph_node *first,
     }
 
   // if they're the same, return the more exact match
-  enum match_type fmtype = match_token (first, token);
-  enum match_type smtype = match_token (second, token);
+  enum match_type fmtype = match_token (first, input_token);
+  enum match_type smtype = match_token (second, input_token);
   if (fmtype != smtype)
     return fmtype > smtype ? first : second;
 
@@ -475,8 +507,8 @@ disambiguate_nodes (struct graph_node *first,
 /**
  * Picks the better of two possible matches for an input line.
  *
- * @param[in] first candidate list of graph_node matching vline
- * @param[in] second candidate list of graph_node matching vline
+ * @param[in] first candidate list of cmd_token_t matching vline
+ * @param[in] second candidate list of cmd_token_t matching vline
  * @param[in] vline the input line being matched
  * @param[in] n index into vline to start comparing at
  * @return the best-matching list, or NULL if the two are entirely ambiguous
@@ -493,82 +525,68 @@ disambiguate (struct list *first,
 
   struct listnode *fnode = listhead (first),
                   *snode = listhead (second);
-  struct graph_node *fgn = listgetdata (fnode),
-                    *sgn = listgetdata (snode),
-                    *best = NULL;
+  struct cmd_token_t *ftok = listgetdata (fnode),
+                     *stok = listgetdata (snode),
+                     *best = NULL;
 
-  // compare each node, if one matches better use that one
+  // compare each token, if one matches better use that one
   for (unsigned int i = n; i < vector_active (vline); i++)
     {
       char *token = vector_slot(vline, i);
-      if ((best = disambiguate_nodes (fgn, sgn, token)))
-        return best == fgn ? first : second;
-      fnode = listnextnode (fnode);
-      snode = listnextnode (snode);
-      fgn = (struct graph_node *) listgetdata (fnode);
-      sgn = (struct graph_node *) listgetdata (snode);
+      if ((best = disambiguate_tokens (ftok, stok, token)))
+        return best == ftok ? first : second;
+      ftok = listgetdata (listnextnode (fnode));
+      stok = listgetdata (listnextnode (snode));
     }
 
   return NULL;
 }
 
-/**
- * Performs a deep copy on a node.
- * Used to build argv node lists that can be safely deleted or modified by
- * endpoint functions. Everything is copied except the children vector,
- * subgraph end pointer and reference count.
+/*
+ * Deletion function for arglist.
  *
- * @param[in] node to copy
- * @return the copy
- */
-static struct graph_node *
-copy_node (struct graph_node *node)
-{
-  struct graph_node *new = graphnode_new(node->type);
-  new->children = NULL;
-  new->text     = node->text ? XSTRDUP(MTYPE_CMD_TOKENS, node->text) : NULL;
-  new->value    = node->value;
-  new->min      = node->min;
-  new->max      = node->max;
-  new->element  = node->element ? copy_cmd_element(node->element) : NULL;
-  new->arg      = node->arg ? XSTRDUP(MTYPE_CMD_TOKENS, node->arg) : NULL;
-  new->refs     = 0;
-  return new;
-}
-
-/**
- * List deletion callback for argv lists.
+ * Since list->del for arglists expects all listnode->data to hold cmd_token,
+ * but arglists have cmd_element as the data for the tail, this function
+ * manually deletes the tail before deleting the rest of the list as usual.
+ *
+ * @param list the arglist to delete
  */
 static void
-delete_nodelist (void *node)
+del_arglist (struct list *list)
 {
-  graphnode_delete ((struct graph_node *) node);
+  // manually delete last node
+  struct listnode *tail = listtail (list);
+  del_cmd_element (tail->data);
+  tail->data = NULL;
+  list_delete_node (list, tail);
+
+  // delete the rest of the list as usual
+  list_delete (list);
 }
 
-
-/* token level matching functions */
+/*---------- token level matching functions ----------*/
 
 static enum match_type
-match_token (struct graph_node *node, char *token)
+match_token (struct cmd_token_t *token, char *input_token)
 {
-  switch (node->type) {
-    case WORD_GN:
-      return match_word (node, token);
-    case IPV4_GN:
-      return match_ipv4 (token);
-    case IPV4_PREFIX_GN:
-      return match_ipv4_prefix (token);
-    case IPV6_GN:
-      return match_ipv6 (token);
-    case IPV6_PREFIX_GN:
-      return match_ipv6_prefix (token);
-    case RANGE_GN:
-      return match_range (node, token);
-    case NUMBER_GN:
-      return match_number (node, token);
-    case VARIABLE_GN:
-      return match_variable (node, token);
-    case END_GN:
+  switch (token->type) {
+    case WORD_TKN:
+      return match_word (token, input_token);
+    case IPV4_TKN:
+      return match_ipv4 (input_token);
+    case IPV4_PREFIX_TKN:
+      return match_ipv4_prefix (input_token);
+    case IPV6_TKN:
+      return match_ipv6 (input_token);
+    case IPV6_PREFIX_TKN:
+      return match_ipv6_prefix (input_token);
+    case RANGE_TKN:
+      return match_range (token, input_token);
+    case NUMBER_TKN:
+      return match_number (token, input_token);
+    case VARIABLE_TKN:
+      return match_variable (token, input_token);
+    case END_TKN:
     default:
       return no_match;
   }
@@ -776,9 +794,9 @@ match_ipv6_prefix (const char *str)
 #endif
 
 static enum match_type
-match_range (struct graph_node *node, const char *str)
+match_range (struct cmd_token_t *token, const char *str)
 {
-  assert (node->type == RANGE_GN);
+  assert (token->type == RANGE_TKN);
 
   char *endptr = NULL;
   long long val;
@@ -790,53 +808,53 @@ match_range (struct graph_node *node, const char *str)
   if (*endptr != '\0')
     return 0;
 
-  if (val < node->min || val > node->max)
+  if (val < token->min || val > token->max)
     return no_match;
   else
     return exact_match;
 }
 
 static enum match_type
-match_word (struct graph_node *node, const char *word)
+match_word (struct cmd_token_t *token, const char *word)
 {
-  assert (node->type == WORD_GN);
+  assert (token->type == WORD_TKN);
 
   // if the passed token is null or 0 length, partly match
   if (!word || !strlen(word))
     return partly_match;
 
   // if the passed token is strictly a prefix of the full word, partly match
-  if (strlen (word) < strlen (node->text))
-    return !strncmp (node->text, word, strlen (word)) ?
+  if (strlen (word) < strlen (token->text))
+    return !strncmp (token->text, word, strlen (word)) ?
        partly_match :
        no_match;
 
   // if they are the same length and exactly equal, exact match
-  else if (strlen (word) == strlen (node->text))
-    return !strncmp (node->text, word, strlen (word)) ? exact_match : no_match;
+  else if (strlen (word) == strlen (token->text))
+    return !strncmp (token->text, word, strlen (word)) ? exact_match : no_match;
 
   return no_match;
 }
 
 static enum match_type
-match_number (struct graph_node *node, const char *word)
+match_number (struct cmd_token_t *token, const char *word)
 {
-  assert (node->type == NUMBER_GN);
+  assert (token->type == NUMBER_TKN);
 
   if (!strcmp ("\0", word)) return no_match;
   char *endptr;
   long long num = strtoll (word, &endptr, 10);
   if (endptr != '\0') return no_match;
-  return num == node->value ? exact_match : no_match;
+  return num == token->value ? exact_match : no_match;
 }
 
 #define VARIABLE_ALPHABET \
 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890:"
 
 static enum match_type
-match_variable (struct graph_node *node, const char *word)
+match_variable (struct cmd_token_t *token, const char *word)
 {
-  assert (node->type == VARIABLE_GN);
+  assert (token->type == VARIABLE_TKN);
 
   return strlen (word) == strspn(word, VARIABLE_ALPHABET) ?
      exact_match : no_match;
diff --git a/lib/command_match.h b/lib/command_match.h
index 765b18949..2bb079033 100644
--- a/lib/command_match.h
+++ b/lib/command_match.h
@@ -25,10 +25,9 @@
 #ifndef _ZEBRA_COMMAND_MATCH_H
 #define _ZEBRA_COMMAND_MATCH_H
 
-#include "command.h"
-#include "command_graph.h"
+#include "graph.h"
 #include "linklist.h"
-
+#include "command.h"
 
 /* These definitions exist in command.c in the current engine but should be
  * relocated here in the new engine
@@ -68,14 +67,14 @@ enum match_type
 /**
  * Attempt to find an exact command match for a line of user input.
  *
- * @param[in] start start node of command graph to match against
+ * @param[in] cmdgraph command graph to match against
  * @param[in] vline vectorized input string
  * @param[out] argv pointer to argument list if successful match
  * @param[out] element pointer to matched cmd_element if successful match
  * @return matcher status
  */
 enum matcher_rv
-command_match (struct graph_node *start,
+command_match (struct graph *cmdgraph,
                vector vline,
                struct list **argv,
                struct cmd_element **element);
@@ -85,11 +84,11 @@ command_match (struct graph_node *start,
  *
  * @param[in] start the start node of the DFA to match against
  * @param[in] vline vectorized input string
- * @param[in] completions pointer to list of possible next nodes
- * @return matcher status
+ * @param[in] completions pointer to list of cmd_token representing
+ *            acceptable next inputs
  */
 enum matcher_rv
-command_complete (struct graph_node *start,
+command_complete (struct graph *cmdgraph,
                   vector vline,
                   struct list **completions);
 
@@ -101,10 +100,10 @@ command_complete (struct graph_node *start,
  * @param[in] vline vectorized input string
  * @param[in] completions vector to fill with string completions
  * @return matcher status
- */
 enum matcher_rv
-command_complete_str (struct graph_node *start,
+command_complete_str (struct graph *cmdgraph,
                       vector vline,
                       vector completions);
 
+ */
 #endif /* _ZEBRA_COMMAND_MATCH_H */
diff --git a/lib/command_parse.y b/lib/command_parse.y
index 750054b5c..12f5a5321 100644
--- a/lib/command_parse.y
+++ b/lib/command_parse.y
@@ -36,6 +36,7 @@
   #include "command.h"
   #include "graph.h"
   #include "memory.h"
+  #include "grammar_sandbox.h"
 
   extern int
   yylex (void);
@@ -49,7 +50,7 @@
 
 /* functionality this unit exports */
 %code provides {
-  struct graph *
+  void
   command_parse_format (struct graph *, struct cmd_element *);
 
   /* maximum length of a number, lexer will not match anything longer */
@@ -89,9 +90,11 @@
 %code {
   /* bison declarations */
   void
-  yyerror (struct cmd_element *el, struct graph_node *sn, char const *msg);
+  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
+
   struct graph_node *currnode,        // current position in DFA
                     *seqhead;         // sequence head
 
@@ -108,16 +111,21 @@
   doc_next (void);
 
   static struct graph_node *
-  node_exists (struct graph_node *, struct graph_node *);
+  node_adjacent (struct graph_node *, struct graph_node *);
 
   static struct graph_node *
-  node_replace (struct graph_node *, struct graph_node *);
+  add_edge_dedup (struct graph_node *, struct graph_node *);
 
   static int
-  cmp_node (struct graph_node *, struct graph_node *);
+  cmp_token (struct cmd_token_t *, struct cmd_token_t *);
+
+  static struct graph_node *
+  new_token_node (struct graph *,
+                  enum cmd_token_type_t type,
+                  char *text, char *doc);
 
   static void
-  terminate_graph (struct graph_node *,
+  terminate_graph (struct graph *,
                    struct graph_node *,
                    struct cmd_element *);
 
@@ -126,11 +134,13 @@
 }
 
 /* yyparse parameters */
-%parse-param { struct cmd_element *element }
 %parse-param { struct graph *graph }
+%parse-param { struct cmd_element *element }
 
 /* called automatically before yyparse */
 %initial-action {
+  startnode = vector_slot (graph->nodes, 0);
+
   /* clear state pointers */
   seqhead = NULL;
   currnode = NULL;
@@ -151,28 +161,28 @@ start:
   sentence_root cmd_token_seq
 {
   // tack on the command element
-  terminate_graph (startnode, currnode, element);
+  terminate_graph (graph, currnode, element);
 }
 | sentence_root cmd_token_seq '.' placeholder_token
 {
-  if ((currnode = node_replace (currnode, $4)) != $4)
-    graph_delete_node ($4);
+  if ((currnode = add_edge_dedup (currnode, $4)) != $4)
+    graph_delete_node (graph, $4);
 
   // adding a node as a child of itself accepts any number
   // of the same token, which is what we want for varags
-  node_replace (currnode, currnode);
+  add_edge_dedup (currnode, currnode);
 
   // tack on the command element
-  terminate_graph (startnode, currnode, element);
+  terminate_graph (graph, currnode, element);
 }
 
 sentence_root: WORD
 {
   struct graph_node *root =
-    new_token_node (WORD_TKN, XSTRDUP(MTYPE_CMD_TOKENS, $1), doc_next());
+    new_token_node (graph, WORD_TKN, XSTRDUP(MTYPE_CMD_TOKENS, $1), doc_next());
 
-  if ((currnode = node_replace (startnode, root)) != root)
-    free (root);
+  if ((currnode = add_edge_dedup (startnode, root)) != root)
+    graph_delete_node (graph, root);
 
   free ($1);
   $$ = currnode;
@@ -181,13 +191,13 @@ sentence_root: WORD
 cmd_token:
   placeholder_token
 {
-  if ((currnode = node_replace (currnode, $1)) != $1)
-    graph_delete_node ($1);
+  if ((currnode = add_edge_dedup (currnode, $1)) != $1)
+    graph_delete_node (graph, $1);
 }
 | literal_token
 {
-  if ((currnode = node_replace (currnode, $1)) != $1)
-    graph_delete_node ($1);
+  if ((currnode = add_edge_dedup (currnode, $1)) != $1)
+    graph_delete_node (graph, $1);
 }
 /* selectors and options are subgraphs with start and end nodes */
 | selector
@@ -212,33 +222,33 @@ cmd_token_seq:
 placeholder_token:
   IPV4
 {
-  $$ = new_token_node (IPV4_TKN, XSTRDUP(MTYPE_CMD_TOKENS, $1), doc_next());
+  $$ = new_token_node (graph, IPV4_TKN, XSTRDUP(MTYPE_CMD_TOKENS, $1), doc_next());
   free ($1);
 }
 | IPV4_PREFIX
 {
-  $$ = new_token_node (IPV4_PREFIX_TKN, XSTRDUP(MTYPE_CMD_TOKENS, $1), doc_next());
+  $$ = new_token_node (graph, IPV4_PREFIX_TKN, XSTRDUP(MTYPE_CMD_TOKENS, $1), doc_next());
   free ($1);
 }
 | IPV6
 {
-  $$ = new_token_node (IPV6_TKN, XSTRDUP(MTYPE_CMD_TOKENS, $1), doc_next());
+  $$ = new_token_node (graph, IPV6_TKN, XSTRDUP(MTYPE_CMD_TOKENS, $1), doc_next());
   free ($1);
 }
 | IPV6_PREFIX
 {
-  $$ = new_token_node (IPV6_PREFIX_TKN, XSTRDUP(MTYPE_CMD_TOKENS, $1), doc_next());
+  $$ = new_token_node (graph, IPV6_PREFIX_TKN, XSTRDUP(MTYPE_CMD_TOKENS, $1), doc_next());
   free ($1);
 }
 | VARIABLE
 {
-  $$ = new_token_node (VARIABLE_TKN, XSTRDUP(MTYPE_CMD_TOKENS, $1), doc_next());
+  $$ = new_token_node (graph, VARIABLE_TKN, XSTRDUP(MTYPE_CMD_TOKENS, $1), doc_next());
   free ($1);
 }
 | RANGE
 {
-  $$ = new_token_node (RANGE_TKN, XSTRDUP(MTYPE_CMD_TOKENS, $1), doc_next());
-  cmd_token_t token = (cmd_token_t *) $$->data;
+  $$ = new_token_node (graph, RANGE_TKN, XSTRDUP(MTYPE_CMD_TOKENS, $1), doc_next());
+  struct cmd_token_t *token = $$->data;
 
   // get the numbers out
   yylval.string++;
@@ -247,7 +257,7 @@ placeholder_token:
   token->max = strtoll (yylval.string, &yylval.string, 10);
 
   // validate range
-  if (token->min >= token->max) yyerror (element, startnode, "Invalid range.");
+  if (token->min >= token->max) yyerror (graph, element, "Invalid range.");
 
   free ($1);
 }
@@ -256,13 +266,13 @@ placeholder_token:
 literal_token:
   WORD
 {
-  $$ = new_token_node (WORD_TKN, XSTRDUP(MTYPE_CMD_TOKENS, $1), doc_next());
+  $$ = new_token_node (graph, WORD_TKN, XSTRDUP(MTYPE_CMD_TOKENS, $1), doc_next());
   free ($1);
 }
 | NUMBER
 {
-  $$ = new_token_node (NUMBER_TKN, NULL, doc_next());
-  cmd_token_t token = (cmd_token_t *) $$->data;
+  $$ = 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);
@@ -288,14 +298,14 @@ selector_element: selector_element_root 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 (SELECTOR_TKN, NULL, NULL);
-    selnode_end = new_token_node (NUL_TKN, NULL, NULL);
+    selnode_start = new_token_node (graph, SELECTOR_TKN, NULL, NULL);
+    selnode_end = new_token_node (graph, NUL_TKN, NULL, NULL);
   }
 
   // add element head as a child of the selector
   graph_add_edge (selnode_start, $1);
 
-  if ($2->type != NUL_GN) {
+  if (((struct cmd_token_t *) $2->data)->type != NUL_TKN) {
     graph_add_edge ($1, seqhead);
     graph_add_edge ($2, selnode_end);
   }
@@ -306,12 +316,12 @@ selector_element: selector_element_root selector_token_seq
 }
 
 selector_token_seq:
-  %empty { $$ = new_token_node (NUL_TKN, NULL, NULL); }
+  %empty { $$ = new_token_node (graph, NUL_TKN, NULL, NULL); }
 | selector_token_seq selector_token
 {
-  // if the sequence component is NUL_GN, this is a sequence start
-  if ($1->type == NUL_GN) {
-    assert(!seqhead); // sequence head should always be null here
+  // if the sequence component is NUL_TKN, this is a sequence start
+  if (((struct cmd_token_t *) $1->data)->type != NUL_TKN) {
+    assert(!seqhead);
     seqhead = $2;
   }
   else // chain on new node
@@ -348,8 +358,8 @@ option_element:
 {
   if (!optnode_start || !optnode_end) {
     assert(!optnode_start && !optnode_end);
-    optnode_start = new_token_node (OPTION_TKN, NULL, NULL);
-    optnode_end = new_token_node (NUL_TKN, NULL, NULL);
+    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, seqhead);
@@ -371,25 +381,23 @@ option_token:
 
 %%
 
-struct graph_node *
-command_parse_format (struct graph_node *start, struct cmd_element *cmd)
+void
+command_parse_format (struct graph *graph, struct cmd_element *cmd)
 {
   // set to 1 to enable parser traces
   yydebug = 0;
 
   // parse command into DFA
-  yyparse (cmd, start);
+  yyparse (graph, cmd);
 
   // cleanup
   cleanup ();
-
-  return start;
 }
 
 /* parser helper functions */
 
 void
-yyerror (struct cmd_element *el, struct graph_node *sn, char const *msg)
+yyerror (struct graph *graph, struct cmd_element *el, char const *msg)
 {
   zlog_err ("%s: FATAL parse error: %s", __func__, msg);
   zlog_err ("while parsing this command definition: \n\t%s\n", el->string);
@@ -414,16 +422,19 @@ cleanup()
 }
 
 static void
-terminate_graph (struct graph_node *startnode,
-                 struct graph_node *finalnode,
-                 struct cmd_element *element)
+terminate_graph (struct graph *graph, struct graph_node *finalnode, struct cmd_element *element)
 {
-  struct graph_node *end = graph_new_node (graph, element, &cmd_delete_element);
+  // end of graph should look like this
+  // * -> finalnode -> END_TKN -> cmd_element
+  struct graph_node *end_token_node = new_token_node (graph, END_TKN, NULL, NULL);
+  struct graph_node *end_element_node =
+    graph_new_node (graph, element, (void (*)(void *)) &del_cmd_element);
 
-  if (node_adjacent (finalnode, end))
-    yyerror (element, startnode, "Duplicate command.");
-  else
-    graph_add_edge (finalnode, end);
+  if (node_adjacent (finalnode, end_token_node))
+    yyerror (graph, element, "Duplicate command.");
+
+  graph_add_edge (finalnode, end_token_node);
+  graph_add_edge (end_token_node, end_element_node);
 }
 
 static char *
@@ -432,57 +443,74 @@ doc_next()
   char *piece = NULL;
   if (!docstr || !(piece = strsep (&docstr, "\n")))
     return NULL;
-  return XSTRDUP(MTYPE_CMD_TOKENS, piece);
+  return XSTRDUP (MTYPE_CMD_TOKENS, piece);
 }
 
 static struct graph_node *
-new_token_node (cmd_token_type_t type, char *text, char *doc)
+new_token_node (struct graph *graph, enum cmd_token_type_t type, char *text, char *doc)
 {
   struct cmd_token_t *token =
-    XMALLOC(MTYPE_CMD_TOKENS, sizeof (struct cmd_token_t));
+    XMALLOC (MTYPE_CMD_TOKENS, sizeof (struct cmd_token_t));
 
   token->type = type;
   token->text = text;
   token->desc = doc;
 
-  return graph_new_node (graph, token, &cmd_delete_token);
+  return graph_new_node (graph, token, (void (*)(void *)) &del_cmd_token);
 }
 
 /**
- * Determines if a node is adjacent to another node
+ * Determines if there is an out edge from the first node to the second
  */
 static struct graph_node *
-node_adjacent (struct graph_node *node, struct graph_node *neighbor)
+node_adjacent (struct graph_node *first, struct graph_node *second)
 {
   struct graph_node *adj;
-  for (unsigned int i = 0; i < vector_active (node->to); i++)
+  for (unsigned int i = 0; i < vector_active (first->to); i++)
     {
-      adj = vector_slot (node->to, i);
-      if (cmp_node (neighbor, adj))
+      adj = vector_slot (first->to, i);
+      struct cmd_token_t *ftok = first->data,
+                         *stok = second->data;
+      if (cmp_token (ftok, stok))
         return adj;
     }
   return NULL;
 }
 
+/**
+ * Creates an edge betwen two nodes, unless there is already an edge to an
+ * equivalent node.
+ *
+ * The first node's out edges are searched to see if any of them point to a
+ * node that is equivalent to the second node. If such a node exists, it is
+ * returned. Otherwise an edge is created from the first node to the second.
+ *
+ * @param from start node for edge
+ * @param to end node for edge
+ * @return the node which the new edge points to
+ */
 static struct graph_node *
-node_replace (struct graph_node *parent, struct graph_node *child)
+add_edge_dedup (struct graph_node *from, struct graph_node *to)
 {
-  struct graph_node *existing = node_adjacent (parent, child);
-  return existing ? existing : graph_add_edge (parent, child);
+  struct graph_node *existing = node_adjacent (from, to);
+  return existing ? existing : graph_add_edge (from, to);
 }
 
+/**
+ * Compares two cmd_token's for equality,
+ *
+ * As such, this function is the working definition of token equality
+ * for parsing purposes and determines overall graph structure.
+ */
 static int
 cmp_token (struct cmd_token_t *first, struct cmd_token_t *second)
 {
-  struct cmd_token_t *first = (cmd_token *) firstgn->data;
-  struct cmd_token_t *second = (cmd_token *) secondgn->data;
-
   // compare types
   if (first->type != second->type) return 0;
 
   switch (first->type) {
-    case WORD_GN:
-    case VARIABLE_GN:
+    case WORD_TKN:
+    case VARIABLE_TKN:
       if (first->text && second->text)
         {
           if (strcmp (first->text, second->text))
@@ -490,28 +518,30 @@ cmp_token (struct cmd_token_t *first, struct cmd_token_t *second)
         }
       else if (first->text != second->text) return 0;
       break;
-    case RANGE_GN:
+    case RANGE_TKN:
       if (first->min != second->min || first->max != second->max)
         return 0;
       break;
-    case NUMBER_GN:
+    case NUMBER_TKN:
       if (first->value != second->value) return 0;
       break;
+
     /* selectors and options should be equal if their subgraphs are equal,
      * but the graph isomorphism problem is not known to be solvable in
      * polynomial time so we consider selectors and options inequal in all
      * cases; ultimately this forks the graph, but the matcher can handle
      * this regardless
      */
-    case SELECTOR_GN:
-    case OPTION_GN:
+    case SELECTOR_TKN:
+    case OPTION_TKN:
       return 0;
+
     /* end nodes are always considered equal, since each node may only
-     * have one END_GN child at a time
+     * have one END_TKN child at a time
      */
-    case START_GN:
-    case END_GN:
-    case NUL_GN:
+    case START_TKN:
+    case END_TKN:
+    case NUL_TKN:
     default:
       break;
   }
diff --git a/lib/grammar_sandbox.c b/lib/grammar_sandbox.c
index 92a0ae304..6f323d631 100644
--- a/lib/grammar_sandbox.c
+++ b/lib/grammar_sandbox.c
@@ -30,16 +30,16 @@
  */
 
 #include "command.h"
-#include "command_graph.h"
+#include "graph.h"
 #include "command_parse.h"
 #include "command_match.h"
 
 #define GRAMMAR_STR "CLI grammar sandbox\n"
 
 void
-grammar_sandbox_init(void);
+grammar_sandbox_init (void);
 void
-pretty_print_graph (struct graph_node *start, int level);
+pretty_print_graph (struct graph *start, int level);
 
 /*
  * Start node for testing command graph.
@@ -48,7 +48,7 @@ pretty_print_graph (struct graph_node *start, int level);
  * The examples below show how to install a command to the graph, calculate
  * completions for a given input line, and match input against the graph.
  */
-struct graph_node * nodegraph;
+struct graph *nodegraph;
 
 /**
  * Reference use of parsing / command installation API
@@ -62,11 +62,11 @@ DEFUN (grammar_test,
   char *command = argv_concat(argv, argc, 0);
 
   // initialize a pretend cmd_element
-  struct cmd_element *cmd = XCALLOC(MTYPE_CMD_TOKENS, sizeof(struct cmd_element));
-  cmd->string = XSTRDUP(MTYPE_TMP, command);
+  struct cmd_element *cmd = XCALLOC (MTYPE_CMD_TOKENS, sizeof (struct cmd_element));
+  cmd->string = XSTRDUP (MTYPE_TMP, command);
   cmd->doc = NULL;
   cmd->func = NULL;
-  cmd->tokens = vector_init(VECTOR_MIN_SIZE);
+  cmd->tokens = vector_init (VECTOR_MIN_SIZE);
 
   // parse the command and install it into the command graph
   command_parse_format (nodegraph, cmd);
@@ -91,22 +91,24 @@ DEFUN (grammar_test_complete,
   char *cmdstr = argv_concat (argv, argc, 0);
   vector command = cmd_make_strvec (cmdstr);
 
-  vector completions = vector_init (VECTOR_MIN_SIZE);
+  struct list *completions = list_new ();
   enum matcher_rv result =
-     command_complete_str (nodegraph, command, completions);
+     command_complete (nodegraph, command, &completions);
 
   // print completions or relevant error message
   if (!MATCHER_ERROR(result))
     {
-      for (unsigned int i = 0; i < vector_active (completions); i++)
-        zlog_info ((char *) vector_slot (completions, i));
+      struct listnode *ln;
+      struct cmd_token_t *tkn;
+      for (ALL_LIST_ELEMENTS_RO(completions,ln,tkn))
+        zlog_info (tkn->text);
     }
   else
     zlog_info ("%% No match for \"%s\"", cmdstr);
 
   // free resources
   cmd_free_strvec (command);
-  cmd_free_strvec (completions);
+  list_delete (completions);
   free (cmdstr);
 
   return CMD_SUCCESS;
@@ -138,11 +140,12 @@ DEFUN (grammar_test_match,
       zlog_info ("Matched: %s", element->string);
       struct listnode *ln;
       struct graph_node *gn;
-      for (ALL_LIST_ELEMENTS_RO(argvv,ln,gn))
-        if (gn->type == END_GN)
-          zlog_info ("func: %p", gn->element->func);
-        else
-          zlog_info ("%s -- %s", gn->text, gn->arg);
+      for (ALL_LIST_ELEMENTS_RO(argvv,ln,gn)) {
+        struct cmd_token_t *token = gn->data;
+        zlog_info ("%s -- %s", token->text, token->arg);
+      }
+
+      zlog_info ("func: %p", element->func);
 
       list_delete (argvv);
     }
@@ -182,7 +185,7 @@ DEFUN (grammar_test_doc,
        "Command end\n")
 {
   // create cmd_element with docstring
-  struct cmd_element *cmd = XCALLOC(MTYPE_CMD_TOKENS, sizeof(struct cmd_element));
+  struct cmd_element *cmd = XCALLOC (MTYPE_CMD_TOKENS, sizeof (struct cmd_element));
   cmd->string = "test docstring <example|selector follow> (1-255) end VARIABLE [OPTION|set lol] . VARARG";
   cmd->doc = "Test stuff\n"
              "docstring thing\n"
@@ -224,7 +227,13 @@ DEFUN (grammar_test_show,
 /* this is called in vtysh.c to set up the testing shim */
 void grammar_sandbox_init() {
   zlog_info ("Initializing grammar testing shim");
-  nodegraph = graphnode_new (START_GN);
+
+  // initialize graph, add start noe
+  nodegraph = graph_new ();
+  struct cmd_token_t *token = new_cmd_token (START_TKN, NULL, NULL);
+  graph_new_node (nodegraph, token, (void (*)(void *)) &del_cmd_token);
+
+  // install all enable elements
   install_element (ENABLE_NODE, &grammar_test_cmd);
   install_element (ENABLE_NODE, &grammar_test_show_cmd);
   install_element (ENABLE_NODE, &grammar_test_match_cmd);
@@ -234,8 +243,9 @@ void grammar_sandbox_init() {
 
 /* recursive pretty-print for command graph */
 void
-pretty_print_graph (struct graph_node *start, int level)
+pretty_print_graph (struct graph *graph, int level)
 {
+  /*
   // print this node
   fprintf (stdout, "%s[%d] ", start->text, vector_active (start->children));
 
@@ -266,4 +276,38 @@ pretty_print_graph (struct graph_node *start, int level)
     }
   else
     fprintf(stdout, "\n");
+  */
+}
+
+/** stuff that should go in command.c + command.h */
+struct cmd_token_t *
+new_cmd_token (enum cmd_token_type_t type, char *text, char *desc)
+{
+  struct cmd_token_t *token = XMALLOC (MTYPE_CMD_TOKENS, sizeof (struct cmd_token_t));
+  token->type = type;
+  token->text = text;
+  token->desc = desc;
+  token->arg  = NULL;
+
+  return token;
+}
+
+void
+del_cmd_token (struct cmd_token_t *token)
+{
+  XFREE (MTYPE_CMD_TOKENS, token->text);
+  XFREE (MTYPE_CMD_TOKENS, token->desc);
+  XFREE (MTYPE_CMD_TOKENS, token->arg);
+  XFREE (MTYPE_CMD_TOKENS, token);
+}
+
+struct cmd_token_t *
+copy_cmd_token (struct cmd_token_t *token)
+{
+  struct cmd_token_t *copy = new_cmd_token (token->type, NULL, NULL);
+  copy->text = XSTRDUP (MTYPE_CMD_TOKENS, token->text);
+  copy->desc = XSTRDUP (MTYPE_CMD_TOKENS, token->desc);
+  copy->arg = copy->arg ? XSTRDUP (MTYPE_CMD_TOKENS, token->arg) : NULL;
+
+  return copy;
 }
diff --git a/lib/grammar_sandbox.h b/lib/grammar_sandbox.h
index 98d987668..8cdcc2359 100644
--- a/lib/grammar_sandbox.h
+++ b/lib/grammar_sandbox.h
@@ -1,7 +1,14 @@
+#ifndef _GRAMMAR_SANDBOX_H
+#define _GRAMMAR_SANDBOX_H
+
+/**
+ * Houses functionality for testing shim as well as code that should go into
+ * command.h and command.c during integration.
+ */
 #include "memory.h"
 
 void
-grammar_sandbox_init(void);
+grammar_sandbox_init (void);
 
 /**
  * Types for tokens.
@@ -11,9 +18,8 @@ grammar_sandbox_init(void);
  */
 enum cmd_token_type_t
 {
-  _TOKEN_BUG = 0,
-  LITERAL_TKN,      // words
-  OPTION_TKN,       // integer ranges
+  WORD_TKN,         // words
+  NUMBER_TKN,       // integral numbers
   VARIABLE_TKN,     // almost anything
   RANGE_TKN,        // integer range
   IPV4_TKN,         // IPV4 addresses
@@ -22,13 +28,13 @@ enum cmd_token_type_t
   IPV6_PREFIX_TKN,  // IPV6 network prefixes
 
   /* plumbing types */
-  SELECTOR,     // marks beginning of selector
-  OPTION,       // marks beginning of option
-  NUL,          // dummy token
-  START,        // first token in line
-  END;          // last token in line
-}; 
-                        
+  SELECTOR_TKN,     // marks beginning of selector
+  OPTION_TKN,       // marks beginning of option
+  NUL_TKN,          // dummy token
+  START_TKN,        // first token in line
+  END_TKN,          // last token in line
+};
+
 /**
  * Token struct.
  */
@@ -41,13 +47,17 @@ struct cmd_token_t
 
   long long value;              // for numeric types
   long long min, max;           // for ranges
+
+  char *arg;                    // user input that matches this token
 };
 
-inline struct cmd_token_t *
-cmd_new_token (cmd_token_type_t type, char *text, char *desc)
-{
-  struct cmd_token_t *token = XMALLOC (MTYPE_CMD_TOKENS, sizeof (struct cmd_token_t));
-  token->type = type;
-  token->text = text;
-  token->desc = desc;
-}
+struct cmd_token_t *
+new_cmd_token (enum cmd_token_type_t, char *, char *);
+
+void
+del_cmd_token (struct cmd_token_t *);
+
+struct cmd_token_t *
+copy_cmd_token (struct cmd_token_t *);
+
+#endif /* _GRAMMAR_SANDBOX_H */
diff --git a/lib/graph.c b/lib/graph.c
index 891851b30..be7d5aef3 100644
--- a/lib/graph.c
+++ b/lib/graph.c
@@ -22,18 +22,26 @@
  * 02111-1307, USA.
  */
 #include <zebra.h>
-#include "command_graph.h"
+#include "graph.h"
 #include "memory.h"
 
+struct graph *
+graph_new ()
+{
+  struct graph *graph = XCALLOC (MTYPE_GRAPH, sizeof(struct graph));
+  graph->nodes = vector_init (VECTOR_MIN_SIZE);
+
+  return graph;
+}
 
 struct graph_node *
 graph_new_node (struct graph *graph, void *data, void (*del) (void*))
 {
   struct graph_node *node =
-     XCALLOC(MTYPE_CMD_TOKENS, sizeof(struct graph_node));
+     XCALLOC(MTYPE_GRAPH_NODE, sizeof(struct graph_node));
 
-  node->from = vector_init(VECTOR_MIN_SIZE);
-  node->to   = vector_init(VECTOR_MIN_SIZE);
+  node->from = vector_init (VECTOR_MIN_SIZE);
+  node->to   = vector_init (VECTOR_MIN_SIZE);
   node->data = data;
   node->del  = del;
 
@@ -51,10 +59,10 @@ graph_delete_node (struct graph *graph, struct graph_node *node)
   struct graph_node *adj;
 
   // for all nodes that have an edge to us, remove us from their ->to
-  for (int i = 0; i < vector_active (node->from); i++)
+  for (unsigned int i = 0; i < vector_active (node->from); i++)
     {
       adj = vector_slot (node->from, i);
-      for (int j = 0; j < vector_active (adj->to); j++)
+      for (unsigned int j = 0; j < vector_active (adj->to); j++)
         if (vector_slot (adj->to, j) == node)
           vector_unset (adj->to, j);
 
@@ -62,14 +70,14 @@ graph_delete_node (struct graph *graph, struct graph_node *node)
       if (vector_active (adj->to) == 0 &&
           vector_active (adj->from) == 0 &&
           adj != node)
-          graph_delete_node (adj);
+          graph_delete_node (graph, adj);
     }
 
   // for all nodes that we have an edge to, remove us from their ->from
-  for (int i = 0; i < vector_active (node->to); i++)
+  for (unsigned int i = 0; i < vector_active (node->to); i++)
     {
       adj = vector_slot (node->to, i);
-      for (int j = 0; j < vector_active (adj->from); j++)
+      for (unsigned int j = 0; j < vector_active (adj->from); j++)
         if (vector_slot (adj->from, j) == node)
           vector_unset (adj->from, j);
 
@@ -77,7 +85,7 @@ graph_delete_node (struct graph *graph, struct graph_node *node)
       if (vector_active (adj->to) == 0 &&
           vector_active (adj->from) == 0 &&
           adj != node)
-          graph_delete_node (adj);
+          graph_delete_node (graph, adj);
     }
 
   // if there is a deletion callback, call it!
@@ -89,12 +97,12 @@ graph_delete_node (struct graph *graph, struct graph_node *node)
   vector_free (node->from);
 
   // remove node from graph->nodes
-  for (int i = 0; i < vector_active (graph->nodes); i++)
+  for (unsigned int i = 0; i < vector_active (graph->nodes); i++)
     if (vector_slot (graph->nodes, i) == node)
       vector_unset (graph->nodes, i);
 
   // free the node itself
-  free (node);
+  XFREE (MTYPE_GRAPH_NODE, node);
 }
 
 struct graph_node *
@@ -109,9 +117,9 @@ void
 graph_delete_graph (struct graph *graph)
 {
   // delete each node in the graph
-  for (int i = 0; i < vector_active (graph->nodes); i++)
-    graph_delete_node (vector_slot (graph->nodes, i));
+  for (unsigned int i = 0; i < vector_active (graph->nodes); i++)
+    graph_delete_node (graph, vector_slot (graph->nodes, i));
 
   vector_free (graph->nodes);
-  free (graph);
+  XFREE (MTYPE_GRAPH, graph);
 }
diff --git a/lib/graph.h b/lib/graph.h
index 7c0f84800..bccbbb94a 100644
--- a/lib/graph.h
+++ b/lib/graph.h
@@ -27,26 +27,23 @@
 
 #include "vector.h"
 
-/**
- * Graph structure.
- */
 struct graph
 {
-  vector nodes; // all nodes in the graph
-}
+  vector nodes;
+};
 
-/**
- * Graph node / vertex.
- */
 struct graph_node
 {
   vector from;                  // nodes which have edges to this node
   vector to;                    // nodes which this node has edges to
 
   void *data;                   // node data
-  void (*del) (void *data)      // deletion callback
+  void (*del) (void *data);     // deletion callback
 };
 
+struct graph *
+graph_new (void);
+
 /**
  * Creates a new node.
  *
-- 
2.39.5