Add TAB-based auto-completion to the CLI

Hitting tab:
 - in the middle of a uniquely defined subcommand will expand the subcommand
 - in the middle of a non-uniquely defined (or empty) subcommand will display
   all possible subcommands, and possibly expand to the lowest common prefix

Change-Id: Ib858eefdb0353cd2c3aad472799d15cd537455a0
Signed-off-by: Yoann Desmouceaux <ydesmouc@cisco.com>

3 files changed, 259 insertions, 0 deletions

diff --git a/src/vlib/cli.c b/src/vlib/cli.c
index 5a0f7ec3c10..9e14bee219e 100644
--- a/src/vlib/cli.c
+++ b/src/vlib/cli.c
@@ -40,6 +40,7 @@
 #include <vlib/vlib.h>
 #include <vppinfra/cpu.h>
 #include <unistd.h>
+#include <ctype.h>
 
 /* Root of all show commands. */
 /* *INDENT-OFF* */
@@ -235,6 +236,107 @@ unformat_vlib_cli_sub_command (unformat_input_t * i, va_list * args)
   return is_unique;
 }
 
+static int
+vlib_cli_cmp_strings (void *a1, void *a2)
+{
+  u8 *c1 = *(u8 **) a1;
+  u8 *c2 = *(u8 **) a2;
+
+  return vec_cmp (c1, c2);
+}
+
+u8 **
+vlib_cli_get_possible_completions (u8 * str)
+{
+  vlib_cli_command_t *c;
+  vlib_cli_sub_command_t *sc;
+  vlib_main_t *vm = vlib_get_main ();
+  vlib_cli_main_t *vcm = &vm->cli_main;
+  uword *match_bitmap = 0;
+  uword index, is_unique, help_next_level;
+  u8 **result = 0;
+  unformat_input_t input;
+  unformat_init_vector (&input, vec_dup (str));
+  c = vec_elt_at_index (vcm->commands, 0);
+
+  /* remove trailing whitespace, except for one of them */
+  while (vec_len (input.buffer) >= 2 &&
+	 isspace (input.buffer[vec_len (input.buffer) - 1]) &&
+	 isspace (input.buffer[vec_len (input.buffer) - 2]))
+    {
+      vec_del1 (input.buffer, vec_len (input.buffer) - 1);
+    }
+
+  /* if input is empty, directly return list of root commands */
+  if (vec_len (input.buffer) == 0 ||
+      (vec_len (input.buffer) == 1 && isspace (input.buffer[0])))
+    {
+      vec_foreach (sc, c->sub_commands)
+      {
+	vec_add1 (result, (u8 *) sc->name);
+      }
+      goto done;
+    }
+
+  /* add a trailing '?' so that vlib_cli_sub_command_match can find
+   * all commands starting with the input string */
+  vec_add1 (input.buffer, '?');
+
+  while (1)
+    {
+      match_bitmap = vlib_cli_sub_command_match (c, &input);
+      /* no match: return no result */
+      if (match_bitmap == 0)
+	{
+	  goto done;
+	}
+      is_unique = clib_bitmap_count_set_bits (match_bitmap) == 1;
+      /* unique match: try to step one subcommand level further */
+      if (is_unique)
+	{
+	  /* stop if no more input */
+	  if (input.index >= vec_len (input.buffer) - 1)
+	    {
+	      break;
+	    }
+
+	  index = clib_bitmap_first_set (match_bitmap);
+	  c = get_sub_command (vcm, c, index);
+	  clib_bitmap_free (match_bitmap);
+	  continue;
+	}
+      /* multiple matches: stop here, return all matches */
+      break;
+    }
+
+  /* remove trailing '?' */
+  vec_del1 (input.buffer, vec_len (input.buffer) - 1);
+
+  /* if we have a space at the end of input, and a unique match,
+   * autocomplete the next level of subcommands */
+  help_next_level = (vec_len (str) == 0) || isspace (str[vec_len (str) - 1]);
+  /* *INDENT-OFF* */
+  clib_bitmap_foreach(index, match_bitmap, {
+    if (help_next_level && is_unique) {
+	c = get_sub_command (vcm, c, index);
+	vec_foreach (sc, c->sub_commands) {
+	  vec_add1 (result, (u8*) sc->name);
+	}
+	goto done; /* break doesn't work in this macro-loop */
+    }
+    sc = &c->sub_commands[index];
+    vec_add1(result, (u8*) sc->name);
+  });
+  /* *INDENT-ON* */
+
+done:
+  clib_bitmap_free (match_bitmap);
+  unformat_free (&input);
+
+  vec_sort_with_function (result, vlib_cli_cmp_strings);
+  return result;
+}
+
 static u8 *
 format_vlib_cli_command_help (u8 * s, va_list * args)
 {
diff --git a/src/vlib/cli.h b/src/vlib/cli.h
index 009c7e82cf7..e713808f18e 100644
--- a/src/vlib/cli.h
+++ b/src/vlib/cli.h
@@ -181,6 +181,10 @@ clib_error_t *vlib_cli_register_parse_rule (struct vlib_main_t *vm,
 
 uword unformat_vlib_cli_sub_input (unformat_input_t * i, va_list * args);
 
+/* Return an vector of strings consisting of possible auto-completions
+ * for a given input string */
+u8 **vlib_cli_get_possible_completions (u8 * input_str);
+
 #endif /* included_vlib_cli_h */
 
 /*
diff --git a/src/vlib/unix/cli.c b/src/vlib/unix/cli.c
index 88e2453cff2..cf524213f5b 100644
--- a/src/vlib/unix/cli.c
+++ b/src/vlib/unix/cli.c
@@ -1230,6 +1230,8 @@ unix_cli_line_process_one (unix_cli_main_t * cm,
 			   u8 input, unix_cli_parse_action_t action)
 {
   u8 *prev;
+  u8 *save = 0;
+  u8 **possible_commands;
   int j, delta;
 
   switch (action)
@@ -1553,6 +1555,157 @@ unix_cli_line_process_one (unix_cli_main_t * cm,
       break;
 
     case UNIX_CLI_PARSE_ACTION_TAB:
+      if (cf->cursor < vec_len (cf->current_command))
+	{
+	  /* if we are in the middle of a line, complete only if
+	   * the cursor points to whitespace */
+	  if (isspace (cf->current_command[cf->cursor]))
+	    {
+	      /* save and clear any input that is after the cursor */
+	      vec_resize (save, vec_len (cf->current_command) - cf->cursor);
+	      clib_memcpy (save, cf->current_command + cf->cursor,
+			   vec_len (cf->current_command) - cf->cursor);
+	      _vec_len (cf->current_command) = cf->cursor;
+	    }
+	  else
+	    {
+	      unix_vlib_cli_output_raw (cf, uf, (u8 *) "\a", 1);
+	      break;
+	    }
+	}
+      possible_commands =
+	vlib_cli_get_possible_completions (cf->current_command);
+      if (vec_len (possible_commands) == 1)
+	{
+	  u32 j = cf->cursor;
+	  u8 *completed = possible_commands[0];
+
+	  /* find the last word of current_command */
+	  while (j >= 1 && !isspace (cf->current_command[j - 1]))
+	    {
+	      j--;
+	      unix_vlib_cli_output_raw (cf, uf, (u8 *) "\b", 1);
+	    }
+	  _vec_len (cf->current_command) = j;
+
+	  /* replace it with the newly expanded command */
+	  vec_append (cf->current_command, completed);
+
+	  /* echo to the terminal */
+	  unix_vlib_cli_output_raw (cf, uf, completed, vec_len (completed));
+
+	  /* add one trailing space if needed */
+	  if (vec_len (save) == 0)
+	    {
+	      vec_add1 (cf->current_command, ' ');
+	      unix_vlib_cli_output_raw (cf, uf, (u8 *) " ", 1);
+	    }
+
+	  cf->cursor = vec_len (cf->current_command);
+
+	}
+      else if (vec_len (possible_commands) >= 2)
+	{
+	  u8 **possible_command;
+	  uword max_command_len = 0, min_command_len = ~0;
+	  u32 i, j;
+
+	  vec_foreach (possible_command, possible_commands)
+	  {
+	    if (vec_len (*possible_command) > max_command_len)
+	      {
+		max_command_len = vec_len (*possible_command);
+	      }
+	    if (vec_len (*possible_command) < min_command_len)
+	      {
+		min_command_len = vec_len (*possible_command);
+	      }
+	  }
+
+	  unix_vlib_cli_output_cooked (cf, uf, (u8 *) "\n", 1);
+
+	  i = 0;
+	  vec_foreach (possible_command, possible_commands)
+	  {
+	    if (i + max_command_len >= cf->width)
+	      {
+		unix_vlib_cli_output_cooked (cf, uf, (u8 *) "\n", 1);
+		i = 0;
+	      }
+	    unix_vlib_cli_output_raw (cf, uf, *possible_command,
+				      vec_len (*possible_command));
+	    for (j = vec_len (*possible_command); j < max_command_len + 2;
+		 j++)
+	      {
+		unix_vlib_cli_output_raw (cf, uf, (u8 *) " ", 1);
+	      }
+	    i += max_command_len + 2;
+	  }
+
+	  unix_vlib_cli_output_cooked (cf, uf, (u8 *) "\n", 1);
+
+	  /* rewrite prompt */
+	  unix_cli_cli_prompt (cf, uf);
+	  unix_vlib_cli_output_raw (cf, uf, cf->current_command,
+				    vec_len (cf->current_command));
+
+	  /* count length of last word */
+	  j = cf->cursor;
+	  i = 0;
+	  while (j >= 1 && !isspace (cf->current_command[j - 1]))
+	    {
+	      j--;
+	      i++;
+	    }
+
+	  /* determine smallest common command */
+	  for (; i < min_command_len; i++)
+	    {
+	      u8 common = '\0';
+	      int stop = 0;
+	      vec_foreach (possible_command, possible_commands)
+	      {
+		if (common == '\0')
+		  {
+		    common = (*possible_command)[i];
+		  }
+		else if (common != (*possible_command)[i])
+		  {
+		    stop = 1;
+		    break;
+		  }
+	      }
+	      if (!stop)
+		{
+		  vec_add1 (cf->current_command, common);
+		  cf->cursor++;
+		  unix_vlib_cli_output_raw (cf, uf, (u8 *) & common, 1);
+		}
+	      else
+		{
+		  break;
+		}
+	    }
+	}
+      else
+	{
+	  unix_vlib_cli_output_raw (cf, uf, (u8 *) "\a", 1);
+	}
+
+      if (vec_len (save) > 0)
+	{
+	  /* restore remaining input if tab was hit in the middle of a line */
+	  unix_vlib_cli_output_raw (cf, uf, save, vec_len (save));
+	  for (j = 0; j < vec_len (save); j++)
+	    {
+	      unix_vlib_cli_output_raw (cf, uf, (u8 *) "\b", 1);
+	    }
+	  vec_append (cf->current_command, save);
+	  vec_free (save);
+	}
+      vec_free (possible_commands);
+
+      break;
     case UNIX_CLI_PARSE_ACTION_YANK:
       /* TODO */
       break;