lib: parser: split off & rename graph handling

Put core CLI graph stuff in lib/command_graph.[ch] and consistently
prefix all function names with "cmd_".

Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

9 files changed, 507 insertions, 435 deletions

diff --git a/lib/Makefile.am b/lib/Makefile.am
index 6e3c6d680d..0323f9ab96 100644
--- a/lib/Makefile.am
+++ b/lib/Makefile.am
@@ -17,6 +17,7 @@ libfrr_la_SOURCES = \
 	network.c pid_output.c getopt.c getopt1.c \
 	checksum.c vector.c linklist.c vty.c \
 	graph.c command_parse.y command_lex.l command_match.c \
+	command_graph.c \
 	command.c \
 	sockunion.c prefix.c thread.c if.c buffer.c table.c hash.c \
 	filter.c routemap.c distribute.c stream.c log.c plist.c \
@@ -60,6 +61,7 @@ pkginclude_HEADERS = \
 	buffer.h checksum.h filter.h getopt.h hash.h \
 	if.h linklist.h log.h \
 	graph.h command_match.h \
+	command_graph.h \
 	command.h \
 	memory.h network.h prefix.h routemap.h distribute.h sockunion.h \
 	stream.h table.h thread.h vector.h version.h vty.h zebra.h \
diff --git a/lib/command.c b/lib/command.c
index 06d9422f70..7a53357e7a 100644
--- a/lib/command.c
+++ b/lib/command.c
@@ -40,15 +40,12 @@
 #include "workqueue.h"
 #include "vrf.h"
 #include "command_match.h"
+#include "command_graph.h"
 #include "qobj.h"
 #include "defaults.h"
 
 DEFINE_MTYPE(       LIB, HOST,       "Host config")
 DEFINE_MTYPE(       LIB, STRVEC,     "String vector")
-DEFINE_MTYPE_STATIC(LIB, CMD_TOKENS, "Command Tokens")
-DEFINE_MTYPE_STATIC(LIB, CMD_DESC,   "Command Token Text")
-DEFINE_MTYPE_STATIC(LIB, CMD_TEXT,   "Command Token Help")
-DEFINE_MTYPE(       LIB, CMD_ARG,    "Command Argument")
 
 /* Command vector which includes some level of command lists. Normally
    each daemon maintains each own cmdvec. */
@@ -234,8 +231,8 @@ install_node (struct cmd_node *node,
   node->cmdgraph = graph_new ();
   node->cmd_vector = vector_init (VECTOR_MIN_SIZE);
   // add start node
-  struct cmd_token *token = new_cmd_token (START_TKN, CMD_ATTR_NORMAL, NULL, NULL);
-  graph_new_node (node->cmdgraph, token, (void (*)(void *)) &del_cmd_token);
+  struct cmd_token *token = cmd_token_new (START_TKN, CMD_ATTR_NORMAL, NULL, NULL);
+  graph_new_node (node->cmdgraph, token, (void (*)(void *)) &cmd_token_del);
   node->cmd_hash = hash_create (cmd_hash_key, cmd_hash_cmp);
 }
 
@@ -306,272 +303,6 @@ cmd_prompt (enum node_type node)
   return cnode->prompt;
 }
 
-static bool
-cmd_nodes_link (struct graph_node *from, struct graph_node *to)
-{
-  for (size_t i = 0; i < vector_active (from->to); i++)
-    if (vector_slot (from->to, i) == to)
-      return true;
-  return false;
-}
-
-static bool cmd_nodes_equal (struct graph_node *ga, struct graph_node *gb);
-
-/* returns a single node to be excluded as "next" from iteration
- * - for JOIN_TKN, never continue back to the FORK_TKN
- * - in all other cases, don't try the node itself (in case of "...")
- */
-static inline struct graph_node *
-cmd_loopstop(struct graph_node *gn)
-{
-  struct cmd_token *tok = gn->data;
-  if (tok->type == JOIN_TKN)
-    return tok->forkjoin;
-  else
-    return gn;
-}
-
-static bool
-cmd_subgraph_equal (struct graph_node *ga, struct graph_node *gb,
-                    struct graph_node *a_join)
-{
-  size_t i, j;
-  struct graph_node *a_fork, *b_fork;
-  a_fork = cmd_loopstop (ga);
-  b_fork = cmd_loopstop (gb);
-
-  if (vector_active (ga->to) != vector_active (gb->to))
-    return false;
-  for (i = 0; i < vector_active (ga->to); i++)
-    {
-      struct graph_node *cga = vector_slot (ga->to, i);
-
-      for (j = 0; j < vector_active (gb->to); j++)
-        {
-          struct graph_node *cgb = vector_slot (gb->to, i);
-
-          if (cga == a_fork && cgb != b_fork)
-            continue;
-          if (cga == a_fork && cgb == b_fork)
-            break;
-
-          if (cmd_nodes_equal (cga, cgb))
-            {
-              if (cga == a_join)
-                break;
-              if (cmd_subgraph_equal (cga, cgb, a_join))
-                break;
-            }
-        }
-      if (j == vector_active (gb->to))
-        return false;
-    }
-  return true;
-}
-
-/* deep compare -- for FORK_TKN, the entire subgraph is compared.
- * this is what's needed since we're not currently trying to partially
- * merge subgraphs */
-static bool
-cmd_nodes_equal (struct graph_node *ga, struct graph_node *gb)
-{
-  struct cmd_token *a = ga->data, *b = gb->data;
-
-  if (a->type != b->type || a->allowrepeat != b->allowrepeat)
-    return false;
-  if (a->type < SPECIAL_TKN && strcmp (a->text, b->text))
-    return false;
-  /* one a ..., the other not. */
-  if (cmd_nodes_link (ga, ga) != cmd_nodes_link (gb, gb))
-    return false;
-
-  switch (a->type)
-    {
-    case RANGE_TKN:
-      return a->min == b->min && a->max == b->max;
-
-    case FORK_TKN:
-      /* one is keywords, the other just option or selector ... */
-      if (cmd_nodes_link (a->forkjoin, ga) != cmd_nodes_link (b->forkjoin, gb))
-        return false;
-      if (cmd_nodes_link (ga, a->forkjoin) != cmd_nodes_link (gb, b->forkjoin))
-        return false;
-      return cmd_subgraph_equal (ga, gb, a->forkjoin);
-
-    default:
-      return true;
-    }
-}
-
-static void
-cmd_fork_bump_attr (struct graph_node *gn, struct graph_node *join,
-                    u_char attr)
-{
-  size_t i;
-  struct cmd_token *tok = gn->data;
-  struct graph_node *stop = cmd_loopstop (gn);
-
-  tok->attr = attr;
-  for (i = 0; i < vector_active (gn->to); i++)
-    {
-      struct graph_node *next = vector_slot (gn->to, i);
-      if (next == stop || next == join)
-        continue;
-      cmd_fork_bump_attr (next, join, attr);
-    }
-}
-
-/* move an entire subtree from the temporary graph resulting from
- * parse() into the permanent graph for the command node.
- *
- * this touches rather deeply into the graph code unfortunately.
- */
-static void
-cmd_reparent_tree (struct graph *fromgraph, struct graph *tograph,
-                   struct graph_node *node)
-{
-  struct graph_node *stop = cmd_loopstop (node);
-  size_t i;
-
-  for (i = 0; i < vector_active (fromgraph->nodes); i++)
-    if (vector_slot (fromgraph->nodes, i) == node)
-      {
-        /* agressive iteration punching through subgraphs - may hit some
-         * nodes twice.  reparent only if found on old graph */
-        vector_unset (fromgraph->nodes, i);
-        vector_set (tograph->nodes, node);
-        break;
-      }
-
-  for (i = 0; i < vector_active (node->to); i++)
-    {
-      struct graph_node *next = vector_slot (node->to, i);
-      if (next != stop)
-        cmd_reparent_tree (fromgraph, tograph, next);
-    }
-}
-
-static void
-cmd_free_recur (struct graph *graph, struct graph_node *node,
-                struct graph_node *stop)
-{
-  struct graph_node *next, *nstop;
-
-  for (size_t i = vector_active (node->to); i; i--)
-    {
-      next = vector_slot (node->to, i - 1);
-      if (next == stop)
-        continue;
-      nstop = cmd_loopstop (next);
-      if (nstop != next)
-        cmd_free_recur (graph, next, nstop);
-      cmd_free_recur (graph, nstop, stop);
-    }
-  graph_delete_node (graph, node);
-}
-
-static void
-cmd_free_node (struct graph *graph, struct graph_node *node)
-{
-  struct cmd_token *tok = node->data;
-  if (tok->type == JOIN_TKN)
-    cmd_free_recur (graph, tok->forkjoin, node);
-  graph_delete_node (graph, node);
-}
-
-/* recursive graph merge.  call with
- *   old ~= new
- * (which holds true for old == START_TKN, new == START_TKN)
- */
-static void
-cmd_merge_nodes (struct graph *oldgraph, struct graph *newgraph,
-                 struct graph_node *old, struct graph_node *new,
-                 int direction)
-{
-  struct cmd_token *tok;
-  struct graph_node *old_skip, *new_skip;
-  old_skip = cmd_loopstop (old);
-  new_skip = cmd_loopstop (new);
-
-  assert (direction == 1 || direction == -1);
-
-  tok = old->data;
-  tok->refcnt += direction;
-
-  size_t j, i;
-  for (j = 0; j < vector_active (new->to); j++)
-    {
-      struct graph_node *cnew = vector_slot (new->to, j);
-      if (cnew == new_skip)
-        continue;
-
-      for (i = 0; i < vector_active (old->to); i++)
-        {
-          struct graph_node *cold = vector_slot (old->to, i);
-          if (cold == old_skip)
-            continue;
-
-          if (cmd_nodes_equal (cold, cnew))
-            {
-              struct cmd_token *told = cold->data, *tnew = cnew->data;
-
-              if (told->type == END_TKN)
-                {
-                  if (direction < 0)
-                    {
-                      graph_delete_node (oldgraph, vector_slot (cold->to, 0));
-                      graph_delete_node (oldgraph, cold);
-                    }
-                  else
-                    /* force no-match handling to install END_TKN */
-                    i = vector_active (old->to);
-                  break;
-                }
-
-              /* the entire fork compared as equal, we continue after it. */
-              if (told->type == FORK_TKN)
-                {
-                  if (tnew->attr < told->attr && direction > 0)
-                    cmd_fork_bump_attr (cold, told->forkjoin, tnew->attr);
-                  /* XXX: no reverse bump on uninstall */
-                  told = (cold = told->forkjoin)->data;
-                  tnew = (cnew = tnew->forkjoin)->data;
-                }
-              if (tnew->attr < told->attr)
-                told->attr = tnew->attr;
-
-              cmd_merge_nodes (oldgraph, newgraph, cold, cnew, direction);
-              break;
-            }
-        }
-      /* nothing found => add new to old */
-      if (i == vector_active (old->to) && direction > 0)
-        {
-          assert (vector_count (cnew->from) ==
-                          cmd_nodes_link (cnew, cnew) ? 2 : 1);
-          graph_remove_edge (new, cnew);
-
-          cmd_reparent_tree (newgraph, oldgraph, cnew);
-
-          graph_add_edge (old, cnew);
-        }
-    }
-
-  if (!tok->refcnt)
-    cmd_free_node (oldgraph, old);
-}
-
-void
-cmd_merge_graphs (struct graph *old, struct graph *new, int direction)
-{
-  assert (vector_active (old->nodes) >= 1);
-  assert (vector_active (new->nodes) >= 1);
-
-  cmd_merge_nodes (old, new,
-                   vector_slot (old->nodes, 0), vector_slot (new->nodes, 0),
-                   direction);
-}
-
 /* Install a command into a node. */
 void
 install_element (enum node_type ntype, struct cmd_element *cmd)
@@ -606,11 +337,11 @@ install_element (enum node_type ntype, struct cmd_element *cmd)
   assert (hash_get (cnode->cmd_hash, cmd, hash_alloc_intern));
 
   struct graph *graph = graph_new();
-  struct cmd_token *token = new_cmd_token (START_TKN, CMD_ATTR_NORMAL, NULL, NULL);
-  graph_new_node (graph, token, (void (*)(void *)) &del_cmd_token);
+  struct cmd_token *token = cmd_token_new (START_TKN, CMD_ATTR_NORMAL, NULL, NULL);
+  graph_new_node (graph, token, (void (*)(void *)) &cmd_token_del);
 
-  command_parse_format (graph, cmd);
-  cmd_merge_graphs (cnode->cmdgraph, graph, +1);
+  cmd_graph_parse (graph, cmd);
+  cmd_graph_merge (cnode->cmdgraph, graph, +1);
   graph_delete_graph (graph);
 
   vector_set (cnode->cmd_vector, cmd);
@@ -652,11 +383,11 @@ uninstall_element (enum node_type ntype, struct cmd_element *cmd)
   vector_unset_value (cnode->cmd_vector, cmd);
 
   struct graph *graph = graph_new();
-  struct cmd_token *token = new_cmd_token (START_TKN, CMD_ATTR_NORMAL, NULL, NULL);
-  graph_new_node (graph, token, (void (*)(void *)) &del_cmd_token);
+  struct cmd_token *token = cmd_token_new (START_TKN, CMD_ATTR_NORMAL, NULL, NULL);
+  graph_new_node (graph, token, (void (*)(void *)) &cmd_token_del);
 
-  command_parse_format (graph, cmd);
-  cmd_merge_graphs (cnode->cmdgraph, graph, -1);
+  cmd_graph_parse (graph, cmd);
+  cmd_graph_merge (cnode->cmdgraph, graph, -1);
   graph_delete_graph (graph);
 
   if (ntype == VIEW_NODE)
@@ -2760,59 +2491,6 @@ cmd_init (int terminal)
 #endif
 }
 
-struct cmd_token *
-new_cmd_token (enum cmd_token_type type, u_char attr,
-               const char *text, const char *desc)
-{
-  struct cmd_token *token = XCALLOC (MTYPE_CMD_TOKENS, sizeof (struct cmd_token));
-  token->type = type;
-  token->attr = attr;
-  token->text = text ? XSTRDUP (MTYPE_CMD_TEXT, text) : NULL;
-  token->desc = desc ? XSTRDUP (MTYPE_CMD_DESC, desc) : NULL;
-  token->refcnt = 1;
-  token->arg  = NULL;
-  token->allowrepeat = false;
-  token->varname = NULL;
-
-  return token;
-}
-
-void
-del_cmd_token (struct cmd_token *token)
-{
-  if (!token) return;
-
-  if (token->text)
-    XFREE (MTYPE_CMD_TEXT, token->text);
-  if (token->desc)
-    XFREE (MTYPE_CMD_DESC, token->desc);
-  if (token->arg)
-    XFREE (MTYPE_CMD_ARG, token->arg);
-
-  XFREE (MTYPE_CMD_TOKENS, token);
-}
-
-struct cmd_token *
-copy_cmd_token (struct cmd_token *token)
-{
-  struct cmd_token *copy = new_cmd_token (token->type, token->attr, NULL, NULL);
-  copy->max   = token->max;
-  copy->min   = token->min;
-  copy->text  = token->text ? XSTRDUP (MTYPE_CMD_TEXT, token->text) : NULL;
-  copy->desc  = token->desc ? XSTRDUP (MTYPE_CMD_DESC, token->desc) : NULL;
-  copy->arg   = token->arg  ? XSTRDUP (MTYPE_CMD_ARG, token->arg) : NULL;
-  copy->varname = token->varname ? XSTRDUP (MTYPE_CMD_ARG, token->varname) : NULL;
-
-  return copy;
-}
-
-void
-cmd_set_varname (struct cmd_token *token, const char *varname)
-{
-  XFREE (MTYPE_CMD_VAR, token->varname);
-  token->varname = varname ? XSTRDUP (MTYPE_CMD_VAR, varname) : NULL;
-}
-
 void
 cmd_terminate ()
 {
diff --git a/lib/command.h b/lib/command.h
index 9b2af57991..4531ec9a17 100644
--- a/lib/command.h
+++ b/lib/command.h
@@ -29,9 +29,9 @@
 #include "graph.h"
 #include "memory.h"
 #include "hash.h"
+#include "command_graph.h"
 
 DECLARE_MTYPE(HOST)
-DECLARE_MTYPE(CMD_ARG)
 
 /* for test-commands.c */
 DECLARE_MTYPE(STRVEC)
@@ -165,70 +165,6 @@ struct cmd_node
   struct hash *cmd_hash;
 };
 
-/**
- * Types for tokens.
- *
- * The type determines what kind of data the token can match (in the
- * matching use case) or hold (in the argv use case).
- */
-enum cmd_token_type
-{
-  WORD_TKN,         // words
-  VARIABLE_TKN,     // almost anything
-  RANGE_TKN,        // integer range
-  IPV4_TKN,         // IPV4 addresses
-  IPV4_PREFIX_TKN,  // IPV4 network prefixes
-  IPV6_TKN,         // IPV6 prefixes
-  IPV6_PREFIX_TKN,  // IPV6 network prefixes
-
-  /* plumbing types */
-  FORK_TKN,         // marks subgraph beginning
-  JOIN_TKN,         // marks subgraph end
-  START_TKN,        // first token in line
-  END_TKN,          // last token in line
-
-  SPECIAL_TKN = FORK_TKN,
-};
-
-/* Command attributes */
-enum
-{
-  CMD_ATTR_NORMAL,
-  CMD_ATTR_DEPRECATED,
-  CMD_ATTR_HIDDEN,
-};
-
-/* Comamand token struct. */
-struct cmd_token
-{
-  enum cmd_token_type type;     // token type
-  u_char attr;                  // token attributes
-  bool allowrepeat;             // matcher allowed to match token repetively?
-  uint32_t refcnt;
-
-  char *text;                   // token text
-  char *desc;                   // token description
-  long long min, max;           // for ranges
-  char *arg;                    // user input that matches this token
-  char *varname;
-
-  struct graph_node *forkjoin;  // paired FORK/JOIN for JOIN/FORK
-};
-
-/* Structure of command element. */
-struct cmd_element
-{
-  const char *string;           /* Command specification by string. */
-  const char *doc;              /* Documentation of this command. */
-  int daemon;                   /* Daemon to which this command belong. */
-  u_char attr;                  /* Command attributes */
-
-  /* handler function for command */
-  int (*func) (const struct cmd_element *, struct vty *, int, struct cmd_token *[]);
-
-  const char *name;             /* symbol name for debugging */
-};
-
 /* Return value of the commands. */
 #define CMD_SUCCESS              0
 #define CMD_WARNING              1
@@ -442,16 +378,7 @@ extern int cmd_hostname_set (const char *hostname);
 /* NOT safe for general use; call this only if DEV_BUILD! */
 extern void grammar_sandbox_init (void);
 
-/* memory management for cmd_token */
-extern struct cmd_token *new_cmd_token (enum cmd_token_type, u_char attr,
-                                        const char *text, const char *desc);
-extern void del_cmd_token (struct cmd_token *);
-extern struct cmd_token *copy_cmd_token (struct cmd_token *);
-extern void cmd_set_varname(struct cmd_token *token, const char *varname);
-
 extern vector completions_to_vec (struct list *completions);
-extern void cmd_merge_graphs (struct graph *old, struct graph *new, int direction);
-extern void command_parse_format (struct graph *graph, struct cmd_element *cmd);
 
 /* Export typical functions. */
 extern const char *host_config_get (void);
@@ -464,7 +391,4 @@ extern int cmd_banner_motd_file (const char *);
 /* struct host global, ick */
 extern struct host host;
 
-/* text for <cr> command */
-#define CMD_CR_TEXT "<cr>"
-
 #endif /* _ZEBRA_COMMAND_H */
diff --git a/lib/command_graph.c b/lib/command_graph.c
new file mode 100644
index 0000000000..7e611e3622
--- /dev/null
+++ b/lib/command_graph.c
@@ -0,0 +1,351 @@
+/*
+ * CLI graph handling
+ *
+ * --
+ * Copyright (C) 2016 Cumulus Networks, Inc.
+ * Copyright (C) 1997, 98, 99 Kunihiro Ishiguro
+ * Copyright (C) 2013 by Open Source Routing.
+ * Copyright (C) 2013 by Internet Systems Consortium, Inc. ("ISC")
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the Free
+ * Software Foundation; either version 2 of the License, or (at your option)
+ * any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
+ * more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+#include <zebra.h>
+
+#include "command_graph.h"
+
+DECLARE_MTYPE(CMD_TOKEN_DATA)
+
+DEFINE_MTYPE_STATIC(LIB, CMD_TOKENS, "Command Tokens")
+DEFINE_MTYPE_STATIC(LIB, CMD_DESC,   "Command Token Text")
+DEFINE_MTYPE_STATIC(LIB, CMD_TEXT,   "Command Token Help")
+DEFINE_MTYPE(       LIB, CMD_ARG,    "Command Argument")
+DEFINE_MTYPE_STATIC(LIB, CMD_VAR,    "Command Argument Name")
+
+struct cmd_token *
+cmd_token_new (enum cmd_token_type type, u_char attr,
+               const char *text, const char *desc)
+{
+  struct cmd_token *token = XCALLOC (MTYPE_CMD_TOKENS, sizeof (struct cmd_token));
+  token->type = type;
+  token->attr = attr;
+  token->text = text ? XSTRDUP (MTYPE_CMD_TEXT, text) : NULL;
+  token->desc = desc ? XSTRDUP (MTYPE_CMD_DESC, desc) : NULL;
+  token->refcnt = 1;
+  token->arg  = NULL;
+  token->allowrepeat = false;
+  token->varname = NULL;
+
+  return token;
+}
+
+void
+cmd_token_del (struct cmd_token *token)
+{
+  if (!token) return;
+
+  XFREE (MTYPE_CMD_TEXT, token->text);
+  XFREE (MTYPE_CMD_DESC, token->desc);
+  XFREE (MTYPE_CMD_ARG, token->arg);
+  XFREE (MTYPE_CMD_VAR, token->varname);
+
+  XFREE (MTYPE_CMD_TOKENS, token);
+}
+
+struct cmd_token *
+cmd_token_dup (struct cmd_token *token)
+{
+  struct cmd_token *copy = cmd_token_new (token->type, token->attr, NULL, NULL);
+  copy->max   = token->max;
+  copy->min   = token->min;
+  copy->text  = token->text ? XSTRDUP (MTYPE_CMD_TEXT, token->text) : NULL;
+  copy->desc  = token->desc ? XSTRDUP (MTYPE_CMD_DESC, token->desc) : NULL;
+  copy->arg   = token->arg  ? XSTRDUP (MTYPE_CMD_ARG, token->arg) : NULL;
+  copy->varname = token->varname ? XSTRDUP (MTYPE_CMD_VAR, token->varname) : NULL;
+
+  return copy;
+}
+
+void cmd_token_varname_set(struct cmd_token *token, const char *varname)
+{
+  XFREE (MTYPE_CMD_VAR, token->varname);
+  token->varname = varname ? XSTRDUP (MTYPE_CMD_VAR, varname) : NULL;
+}
+
+static bool
+cmd_nodes_link (struct graph_node *from, struct graph_node *to)
+{
+  for (size_t i = 0; i < vector_active (from->to); i++)
+    if (vector_slot (from->to, i) == to)
+      return true;
+  return false;
+}
+
+static bool cmd_nodes_equal (struct graph_node *ga, struct graph_node *gb);
+
+/* returns a single node to be excluded as "next" from iteration
+ * - for JOIN_TKN, never continue back to the FORK_TKN
+ * - in all other cases, don't try the node itself (in case of "...")
+ */
+static inline struct graph_node *
+cmd_loopstop(struct graph_node *gn)
+{
+  struct cmd_token *tok = gn->data;
+  if (tok->type == JOIN_TKN)
+    return tok->forkjoin;
+  else
+    return gn;
+}
+
+static bool
+cmd_subgraph_equal (struct graph_node *ga, struct graph_node *gb,
+                    struct graph_node *a_join)
+{
+  size_t i, j;
+  struct graph_node *a_fork, *b_fork;
+  a_fork = cmd_loopstop (ga);
+  b_fork = cmd_loopstop (gb);
+
+  if (vector_active (ga->to) != vector_active (gb->to))
+    return false;
+  for (i = 0; i < vector_active (ga->to); i++)
+    {
+      struct graph_node *cga = vector_slot (ga->to, i);
+
+      for (j = 0; j < vector_active (gb->to); j++)
+        {
+          struct graph_node *cgb = vector_slot (gb->to, i);
+
+          if (cga == a_fork && cgb != b_fork)
+            continue;
+          if (cga == a_fork && cgb == b_fork)
+            break;
+
+          if (cmd_nodes_equal (cga, cgb))
+            {
+              if (cga == a_join)
+                break;
+              if (cmd_subgraph_equal (cga, cgb, a_join))
+                break;
+            }
+        }
+      if (j == vector_active (gb->to))
+        return false;
+    }
+  return true;
+}
+
+/* deep compare -- for FORK_TKN, the entire subgraph is compared.
+ * this is what's needed since we're not currently trying to partially
+ * merge subgraphs */
+static bool
+cmd_nodes_equal (struct graph_node *ga, struct graph_node *gb)
+{
+  struct cmd_token *a = ga->data, *b = gb->data;
+
+  if (a->type != b->type || a->allowrepeat != b->allowrepeat)
+    return false;
+  if (a->type < SPECIAL_TKN && strcmp (a->text, b->text))
+    return false;
+  /* one a ..., the other not. */
+  if (cmd_nodes_link (ga, ga) != cmd_nodes_link (gb, gb))
+    return false;
+
+  switch (a->type)
+    {
+    case RANGE_TKN:
+      return a->min == b->min && a->max == b->max;
+
+    case FORK_TKN:
+      /* one is keywords, the other just option or selector ... */
+      if (cmd_nodes_link (a->forkjoin, ga) != cmd_nodes_link (b->forkjoin, gb))
+        return false;
+      if (cmd_nodes_link (ga, a->forkjoin) != cmd_nodes_link (gb, b->forkjoin))
+        return false;
+      return cmd_subgraph_equal (ga, gb, a->forkjoin);
+
+    default:
+      return true;
+    }
+}
+
+static void
+cmd_fork_bump_attr (struct graph_node *gn, struct graph_node *join,
+                    u_char attr)
+{
+  size_t i;
+  struct cmd_token *tok = gn->data;
+  struct graph_node *stop = cmd_loopstop (gn);
+
+  tok->attr = attr;
+  for (i = 0; i < vector_active (gn->to); i++)
+    {
+      struct graph_node *next = vector_slot (gn->to, i);
+      if (next == stop || next == join)
+        continue;
+      cmd_fork_bump_attr (next, join, attr);
+    }
+}
+
+/* move an entire subtree from the temporary graph resulting from
+ * parse() into the permanent graph for the command node.
+ *
+ * this touches rather deeply into the graph code unfortunately.
+ */
+static void
+cmd_reparent_tree (struct graph *fromgraph, struct graph *tograph,
+                   struct graph_node *node)
+{
+  struct graph_node *stop = cmd_loopstop (node);
+  size_t i;
+
+  for (i = 0; i < vector_active (fromgraph->nodes); i++)
+    if (vector_slot (fromgraph->nodes, i) == node)
+      {
+        /* agressive iteration punching through subgraphs - may hit some
+         * nodes twice.  reparent only if found on old graph */
+        vector_unset (fromgraph->nodes, i);
+        vector_set (tograph->nodes, node);
+        break;
+      }
+
+  for (i = 0; i < vector_active (node->to); i++)
+    {
+      struct graph_node *next = vector_slot (node->to, i);
+      if (next != stop)
+        cmd_reparent_tree (fromgraph, tograph, next);
+    }
+}
+
+static void
+cmd_free_recur (struct graph *graph, struct graph_node *node,
+                struct graph_node *stop)
+{
+  struct graph_node *next, *nstop;
+
+  for (size_t i = vector_active (node->to); i; i--)
+    {
+      next = vector_slot (node->to, i - 1);
+      if (next == stop)
+        continue;
+      nstop = cmd_loopstop (next);
+      if (nstop != next)
+        cmd_free_recur (graph, next, nstop);
+      cmd_free_recur (graph, nstop, stop);
+    }
+  graph_delete_node (graph, node);
+}
+
+static void
+cmd_free_node (struct graph *graph, struct graph_node *node)
+{
+  struct cmd_token *tok = node->data;
+  if (tok->type == JOIN_TKN)
+    cmd_free_recur (graph, tok->forkjoin, node);
+  graph_delete_node (graph, node);
+}
+
+/* recursive graph merge.  call with
+ *   old ~= new
+ * (which holds true for old == START_TKN, new == START_TKN)
+ */
+static void
+cmd_merge_nodes (struct graph *oldgraph, struct graph *newgraph,
+                 struct graph_node *old, struct graph_node *new,
+                 int direction)
+{
+  struct cmd_token *tok;
+  struct graph_node *old_skip, *new_skip;
+  old_skip = cmd_loopstop (old);
+  new_skip = cmd_loopstop (new);
+
+  assert (direction == 1 || direction == -1);
+
+  tok = old->data;
+  tok->refcnt += direction;
+
+  size_t j, i;
+  for (j = 0; j < vector_active (new->to); j++)
+    {
+      struct graph_node *cnew = vector_slot (new->to, j);
+      if (cnew == new_skip)
+        continue;
+
+      for (i = 0; i < vector_active (old->to); i++)
+        {
+          struct graph_node *cold = vector_slot (old->to, i);
+          if (cold == old_skip)
+            continue;
+
+          if (cmd_nodes_equal (cold, cnew))
+            {
+              struct cmd_token *told = cold->data, *tnew = cnew->data;
+
+              if (told->type == END_TKN)
+                {
+                  if (direction < 0)
+                    {
+                      graph_delete_node (oldgraph, vector_slot (cold->to, 0));
+                      graph_delete_node (oldgraph, cold);
+                    }
+                  else
+                    /* force no-match handling to install END_TKN */
+                    i = vector_active (old->to);
+                  break;
+                }
+
+              /* the entire fork compared as equal, we continue after it. */
+              if (told->type == FORK_TKN)
+                {
+                  if (tnew->attr < told->attr && direction > 0)
+                    cmd_fork_bump_attr (cold, told->forkjoin, tnew->attr);
+                  /* XXX: no reverse bump on uninstall */
+                  told = (cold = told->forkjoin)->data;
+                  tnew = (cnew = tnew->forkjoin)->data;
+                }
+              if (tnew->attr < told->attr)
+                told->attr = tnew->attr;
+
+              cmd_merge_nodes (oldgraph, newgraph, cold, cnew, direction);
+              break;
+            }
+        }
+      /* nothing found => add new to old */
+      if (i == vector_active (old->to) && direction > 0)
+        {
+          assert (vector_count (cnew->from) ==
+                          cmd_nodes_link (cnew, cnew) ? 2 : 1);
+          graph_remove_edge (new, cnew);
+
+          cmd_reparent_tree (newgraph, oldgraph, cnew);
+
+          graph_add_edge (old, cnew);
+        }
+    }
+
+  if (!tok->refcnt)
+    cmd_free_node (oldgraph, old);
+}
+
+void
+cmd_graph_merge (struct graph *old, struct graph *new, int direction)
+{
+  assert (vector_active (old->nodes) >= 1);
+  assert (vector_active (new->nodes) >= 1);
+
+  cmd_merge_nodes (old, new,
+                   vector_slot (old->nodes, 0), vector_slot (new->nodes, 0),
+                   direction);
+}
diff --git a/lib/command_graph.h b/lib/command_graph.h
new file mode 100644
index 0000000000..e6d49f2f56
--- /dev/null
+++ b/lib/command_graph.h
@@ -0,0 +1,116 @@
+/*
+ * CLI graph handling
+ *
+ * --
+ * Copyright (C) 2016 Cumulus Networks, Inc.
+ * Copyright (C) 1997, 98, 99 Kunihiro Ishiguro
+ * Copyright (C) 2013 by Open Source Routing.
+ * Copyright (C) 2013 by Internet Systems Consortium, Inc. ("ISC")
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the Free
+ * Software Foundation; either version 2 of the License, or (at your option)
+ * any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
+ * more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+#ifndef _FRR_COMMAND_GRAPH_H
+#define _FRR_COMMAND_GRAPH_H
+
+#include <stdbool.h>
+#include <stdint.h>
+
+#include "memory.h"
+#include "vector.h"
+#include "graph.h"
+
+DECLARE_MTYPE(CMD_ARG)
+
+struct vty;
+
+/**
+ * Types for tokens.
+ *
+ * The type determines what kind of data the token can match (in the
+ * matching use case) or hold (in the argv use case).
+ */
+enum cmd_token_type
+{
+  WORD_TKN,         // words
+  VARIABLE_TKN,     // almost anything
+  RANGE_TKN,        // integer range
+  IPV4_TKN,         // IPV4 addresses
+  IPV4_PREFIX_TKN,  // IPV4 network prefixes
+  IPV6_TKN,         // IPV6 prefixes
+  IPV6_PREFIX_TKN,  // IPV6 network prefixes
+
+  /* plumbing types */
+  FORK_TKN,         // marks subgraph beginning
+  JOIN_TKN,         // marks subgraph end
+  START_TKN,        // first token in line
+  END_TKN,          // last token in line
+
+  SPECIAL_TKN = FORK_TKN,
+};
+
+/* Command attributes */
+enum
+{
+  CMD_ATTR_NORMAL,
+  CMD_ATTR_DEPRECATED,
+  CMD_ATTR_HIDDEN,
+};
+
+/* Comamand token struct. */
+struct cmd_token
+{
+  enum cmd_token_type type;     // token type
+  uint8_t attr;                 // token attributes
+  bool allowrepeat;             // matcher allowed to match token repetively?
+  uint32_t refcnt;
+
+  char *text;                   // token text
+  char *desc;                   // token description
+  long long min, max;           // for ranges
+  char *arg;                    // user input that matches this token
+  char *varname;
+
+  struct graph_node *forkjoin;  // paired FORK/JOIN for JOIN/FORK
+};
+
+/* Structure of command element. */
+struct cmd_element
+{
+  const char *string;           /* Command specification by string. */
+  const char *doc;              /* Documentation of this command. */
+  int daemon;                   /* Daemon to which this command belong. */
+  uint8_t attr;                 /* Command attributes */
+
+  /* handler function for command */
+  int (*func) (const struct cmd_element *, struct vty *, int, struct cmd_token *[]);
+
+  const char *name;             /* symbol name for debugging */
+};
+
+/* text for <cr> command */
+#define CMD_CR_TEXT "<cr>"
+
+/* memory management for cmd_token */
+extern struct cmd_token *cmd_token_new (enum cmd_token_type, uint8_t attr,
+                                        const char *text, const char *desc);
+extern struct cmd_token *cmd_token_dup (struct cmd_token *);
+extern void cmd_token_del (struct cmd_token *);
+extern void cmd_token_varname_set(struct cmd_token *token, const char *varname);
+
+extern void cmd_graph_parse (struct graph *graph, struct cmd_element *cmd);
+extern void cmd_graph_merge (struct graph *old, struct graph *new, int direction);
+
+#endif /* _FRR_COMMAND_GRAPH_H */
diff --git a/lib/command_match.c b/lib/command_match.c
index bbd9cd091d..df1a8bb72b 100644
--- a/lib/command_match.c
+++ b/lib/command_match.c
@@ -117,7 +117,7 @@ command_match (struct graph *cmdgraph,
       struct listnode *tail = listtail (*argv);
 
       // delete dummy start node
-      del_cmd_token ((struct cmd_token *) head->data);
+      cmd_token_del ((struct cmd_token *) head->data);
       list_delete_node (*argv, head);
 
       // get cmd_element out of list tail
@@ -281,7 +281,7 @@ command_match_r (struct graph_node *start, vector vline, unsigned int n,
               // manually deleted
               struct cmd_element *el = leaf->data;
               listnode_add (currbest, el);
-              currbest->del = (void (*)(void *)) &del_cmd_token;
+              currbest->del = (void (*)(void *)) &cmd_token_del;
               // do not break immediately; continue walking through the follow set
               // to ensure that there is exactly one END_TKN
             }
@@ -320,7 +320,7 @@ command_match_r (struct graph_node *start, vector vline, unsigned int n,
         {
           // copy token, set arg and prepend to currbest
           struct cmd_token *token = start->data;
-          struct cmd_token *copy = copy_cmd_token (token);
+          struct cmd_token *copy = cmd_token_dup (token);
           copy->arg = XSTRDUP (MTYPE_CMD_ARG, input_token);
           listnode_add_before (currbest, currbest->head, copy);
           matcher_rv = MATCHER_OK;
diff --git a/lib/command_parse.y b/lib/command_parse.y
index 7e7a68ffdd..466e3d3f1f 100644
--- a/lib/command_parse.y
+++ b/lib/command_parse.y
@@ -44,12 +44,12 @@
  * struct parser_ctx is needed for the bison forward decls.
  */
 %code requires {
-  #include "stdlib.h"
-  #include "string.h"
-  #include "memory.h"
-  #include "command.h"
+  #include <stdlib.h>
+  #include <string.h>
+  #include <ctype.h>
+
+  #include "command_graph.h"
   #include "log.h"
-  #include "graph.h"
 
   DECLARE_MTYPE(LEX)
 
@@ -223,7 +223,7 @@ simple_token:
 literal_token: WORD varname_token
 {
   $$ = new_token_node (ctx, WORD_TKN, $1, doc_next(ctx));
-  cmd_set_varname ($$->data, $2);
+  cmd_token_varname_set ($$->data, $2);
   XFREE (MTYPE_LEX, $2);
   XFREE (MTYPE_LEX, $1);
 }
@@ -277,7 +277,7 @@ placeholder_token:
 {
   struct cmd_token *token = $$->data;
   $$ = $1;
-  cmd_set_varname (token, $2);
+  cmd_token_varname_set (token, $2);
   XFREE (MTYPE_LEX, $2);
 };
 
@@ -286,7 +286,7 @@ placeholder_token:
 selector: '<' selector_seq_seq '>' varname_token
 {
   $$ = $2;
-  cmd_set_varname ($2.end->data, $4);
+  cmd_token_varname_set ($2.end->data, $4);
   XFREE (MTYPE_LEX, $4);
 };
 
@@ -321,7 +321,7 @@ selector: '{' selector_seq_seq '}' varname_token
    * just use [{a|b}] if neccessary, that will work perfectly fine, and reason
    * #1 is good enough to keep it this way. */
 
-  cmd_set_varname ($2.end->data, $4);
+  cmd_token_varname_set ($2.end->data, $4);
   XFREE (MTYPE_LEX, $4);
 };
 
@@ -349,7 +349,7 @@ selector: '[' selector_seq_seq ']' varname_token
 {
   $$ = $2;
   graph_add_edge ($$.start, $$.end);
-  cmd_set_varname ($2.end->data, $4);
+  cmd_token_varname_set ($2.end->data, $4);
   XFREE (MTYPE_LEX, $4);
 }
 ;
@@ -361,7 +361,7 @@ selector: '[' selector_seq_seq ']' varname_token
 DEFINE_MTYPE(LIB, LEX, "Lexer token (temporary)")
 
 void
-command_parse_format (struct graph *graph, struct cmd_element *cmd)
+cmd_graph_parse (struct graph *graph, struct cmd_element *cmd)
 {
   struct parser_ctx ctx = { .graph = graph, .el = cmd };
 
@@ -462,6 +462,6 @@ 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 = new_cmd_token (type, ctx->el->attr, text, doc);
-  return graph_new_node (ctx->graph, token, (void (*)(void *)) &del_cmd_token);
+  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);
 }
diff --git a/lib/grammar_sandbox.c b/lib/grammar_sandbox.c
index f35b8beffd..24bf20dac6 100644
--- a/lib/grammar_sandbox.c
+++ b/lib/grammar_sandbox.c
@@ -70,11 +70,11 @@ DEFUN (grammar_test,
 
   // parse the command and install it into the command graph
   struct graph *graph = graph_new();
-  struct cmd_token *token = new_cmd_token (START_TKN, CMD_ATTR_NORMAL, NULL, NULL);
-  graph_new_node (graph, token, (void (*)(void *)) &del_cmd_token);
+  struct cmd_token *token = cmd_token_new (START_TKN, CMD_ATTR_NORMAL, NULL, NULL);
+  graph_new_node (graph, token, (void (*)(void *)) &cmd_token_del);
 
-  command_parse_format (graph, cmd);
-  cmd_merge_graphs (nodegraph, graph, +1);
+  cmd_graph_parse (graph, cmd);
+  cmd_graph_merge (nodegraph, graph, +1);
 
   return CMD_SUCCESS;
 }
@@ -123,7 +123,7 @@ DEFUN (grammar_test_complete,
       }
 
       for (i = 0; i < vector_active (comps); i++)
-        del_cmd_token ((struct cmd_token *) vector_slot (comps, i));
+        cmd_token_del ((struct cmd_token *) vector_slot (comps, i));
       vector_free (comps);
     }
   else
@@ -229,7 +229,7 @@ DEFUN (grammar_test_doc,
   cmd->func = NULL;
 
   // parse element
-  command_parse_format (nodegraph, cmd);
+  cmd_graph_parse (nodegraph, cmd);
 
   return CMD_SUCCESS;
 }
@@ -649,8 +649,8 @@ init_cmdgraph (struct vty *vty, struct graph **graph)
   // initialize graph, add start noe
   *graph = graph_new ();
   nodegraph_free = *graph;
-  struct cmd_token *token = new_cmd_token (START_TKN, 0, NULL, NULL);
-  graph_new_node (*graph, token, (void (*)(void *)) &del_cmd_token);
+  struct cmd_token *token = cmd_token_new (START_TKN, 0, NULL, NULL);
+  graph_new_node (*graph, token, (void (*)(void *)) &cmd_token_del);
   if (vty)
     vty_out (vty, "initialized graph%s", VTY_NEWLINE);
 }
diff --git a/lib/log.h b/lib/log.h
index cc419cc374..5faf0103e2 100644
--- a/lib/log.h
+++ b/lib/log.h
@@ -24,6 +24,7 @@
 #define _ZEBRA_LOG_H
 
 #include <syslog.h>
+#include <stdint.h>
 #include <stdio.h>
 
 /* Here is some guidance on logging levels to use:
@@ -64,7 +65,7 @@ struct message
 
 /* Open zlog function */
 extern void openzlog (const char *progname, const char *protoname,
-                      u_short instance, int syslog_options, int syslog_facility);
+                      uint16_t instance, int syslog_options, int syslog_facility);
 
 /* Close zlog function. */
 extern void closezlog (void);