/* tab.c
 * Part of the Readline module for Tap. This is where command line
 * completion is implemented.
 */

/* Copyright (C) 1999 Jonathan duSaint
 *
 * This file is part of Tap, an interactive program for reading and
 * writing data to the serial port to facilitate the reverse
 * engineering of communication protocols.
 *
 * Tap 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, or (at your option)
 * any later version.
 *
 * Tap 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.
 *
 * The GNU General Public License is generally kept in a file called
 * COPYING or LICENSE.  If you do not have a copy of the license, write
 * to the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
 */

#include "readline.h"
#include <glob.h>

/* returned to do_tab_completion () when a successful match hasn't been made */
char *null_match[] = { NULL, NULL };

/* find the number of matching characters in the two strings */
int
strmatch (char *first, char *second)
{
  int highest;

  for (highest = 0; highest < MAX (strlen (first), strlen (second)); highest++)
    if (first[highest] != second[highest]) break;

  return (highest);
}

/* Scan an array of strings looking for the largest
 * number of matching characters. For the array
 *
 *   "dobri"
 *   "dyen"
 *   "dinamacheskiye"
 *   "dudayevtsi"
 *
 * the result would be 1.
 */
int
find_matching_chars (char *matches[])
{
  int current_match, max_match = INT_MAX, index, last = 0;

  while (matches[last + 1] != NULL) last++;

  if (!last) return (strlen (matches[0])); /* one item in array */

  for (index = 1; index <= last; index++)
    {
      current_match = strmatch (matches[index - 1], matches[index]);

      max_match = MIN (max_match, current_match);
    }

  return (max_match);
}

/* Return an array of strings containing the main command names */
char **
command_names (void)
{
  static char **names = NULL;
  int index = 0, max_commands;

  if (names != NULL) return (names);

  names = xmalloc (sizeof (char *) * INCR_VALUE);
  max_commands = INCR_VALUE;

  while (commands[index].name != NULL)
    {
      if (index == max_commands - 1)
	{
	  names = xrealloc (names, sizeof (char *)*(max_commands+INCR_VALUE));
	  max_commands += INCR_VALUE;
	}

      names[index] = commands[index].name;
      index++;
    }

  names[index] = NULL;

  return (names);
}

/* Return the `number' of the current token */
int
find_current_token_number (void)
{
  int token_number = 1, pos = current_position + 1;

  while (pos--)
    { /* scan backward counting whitespace regions */

      if (current_line[pos] == ' ') /* found one */
	{
	  token_number++;

	  /* skip the rest of the region */
	  while (current_line[pos] == ' ' && pos) pos--;

	  /* if the first char is ' ' */
	  if (!pos && current_line[pos] ==  ' ') token_number--;
	}
    }

  return (token_number);
}

/* move the point to the end of the current token */
void
move_to_token_end (void)
{
  while (current_line[current_position] != ' '
	 && current_position != chars_in_line) move_cursor_right ();
}

/* If a match string for a command is \f, this function is
 * called. Uses the POSIX.2 function glob() to match files
 * and returns all files matched by SEARCH with a '*' tacked
 * onto the end.
 */
char **
match_file_esc (char *search)
{
  glob_t file_list;
  int k;
  char **ret_list, *pattern;

  pattern = xmalloc (strlen (search) + 2);
  sprintf (pattern, "%s*", search);

  if (glob (pattern, GLOB_MARK, NULL, &file_list)) return (null_match);

  ret_list = xmalloc ((file_list.gl_pathc + 1) * sizeof (char *));

  for (k = 0; k < file_list.gl_pathc; k++)
    {
      ret_list[k] = xmalloc (strlen (file_list.gl_pathv[k]) + 1);
      strcpy (ret_list[k], file_list.gl_pathv[k]);
    }

  ret_list[file_list.gl_pathc] = NULL;

  xfree (pattern);
  return (ret_list);
}

/* Returns an array of strings which match the escape. Valid
 * escapes are \f - a filename, \c - a command name, and \m - anything.
 */
char **
find_esc_matches (char *search, char *esc_code)
{
  switch (esc_code[1])
    {
    case 'f':
      return (match_file_esc (search));

      /* this will be made functional later -- it isn't
       * used for anything now anyways */
    case 'c':

    case 'm': /* this doesn't match anything specific */
      return (null_match);
    }

  return (null_match);
}

/* Given a search string and an array of strings, returns an
 * array of strings which match
 */
char **
find_matches (char *search, char **potential_matches)
{
  char **actual_matches;
  int possible_completions, length = strlen (search), last_completion = -1, k;
  
  /* count the entries in potential_matches */
  for (possible_completions = 0;
       potential_matches[possible_completions] != NULL;
       possible_completions++);

  /* check for escapes */
  if (possible_completions == 1 && potential_matches[0][0] == '\\')
    return (find_esc_matches (search, potential_matches[0]));

  actual_matches = xmalloc ((possible_completions + 1) * sizeof (char *));

  /* zero out the output array */
  for (k = 0; k < possible_completions + 1; k++) actual_matches[k] = NULL;

  /* loop backward looking for matches */
  while (possible_completions--)
    {
      /* found a match */
      if (!strncmp (search, potential_matches[possible_completions], length))
	{
	  /* add to match list */
	  actual_matches[++last_completion] =
	    potential_matches[possible_completions];
	}
    }

  return (actual_matches);
}

/* Expands a token to the maximum possible size using
 * partial matches. Assumes that the point is at the end of the token
 * to be expanded, that token contains the partial token, and
 * that matches is a NULL terminated array with strings that
 * are matched by token.
 */
void
expand_text (char *token, char *matches[])
{
  int match_length, tok_length, match_pos;

  match_pos = tok_length = strlen (token);

  match_length = find_matching_chars (matches) - tok_length;

  if (match_length < 1) return;

  while (match_length--) insert_char (matches[0][match_pos++]);

  if (current_line[current_position] != ' '
      && matches[1] == NULL
      && current_line[current_position - 1] != '/')
    insert_char (' ');
}

/* Retrieves the match string for COMMAND. In other words
 * returns commands[n].tab_completion when
 * strcmp (command, commands[n].name) == 0
 */
char *
get_match_string (char *command)
{
  int index = -1, tok_len = strlen (command);

  while (commands[++index].name != NULL)
    {
      if (!strncmp (command, commands[index].name, tok_len))
	return (commands[index].tab_completion);
    }

  /* this should never be reached */
  return (zero_length_string);
}

/* print all of the strings in MATCHES */
void
print_partial_matches (char *matches[])
{
  int index, command_width = 0, commands_per_line;
  int x_pos = input_window->_curx, y, y_offset;

  y = input_window->_cury;
  move_cursor_to_end ();
  y_offset = input_window->_cury - y;

  waddch (input_window, '\n');

  /* find longest string */
  index = -1;
  while (matches[++index] != NULL)
    command_width = MAX (command_width, strlen (matches[index]));

  command_width += PADDING;

  commands_per_line = window_width / command_width;

  /* print strings */
  index = -1;
  while (matches[++index] != NULL)
    {
      wprintw (input_window, "%-*s", command_width, matches[index]);
      if (!((index + 1) % commands_per_line)) waddch (input_window, '\n');
    }

  if (input_window->_curx) waddch (input_window, '\n');

  start_y = input_window->_cury;

  wprintw (input_window, "%s%s", prompt, current_line);

  input_window->_curx = x_pos;
  input_window->_cury -= y_offset;
}

/* Returns the NUMBERth token in current_line */
char *
get_token_by_number (int number)
{
  int pos = 0;

  while (number--)
    {
      if (number)
	while (current_line[pos] != ' ' && pos < chars_in_line) pos++;

      while (current_line[pos] == ' ' && pos < chars_in_line) pos++;
    }

  return (get_token_only (current_line + pos));
}

/* Returns the position of the next level one match_string
 */
int
next_level_one (char *match_string, int pos)
{
  int depth = 0;

  pos--;

  while (match_string[++pos] != '\0')
    {
      switch (match_string[pos])
	{
	case '{':
	  depth++;
	  break;
	case '}':
	  depth--;
	  break;
	case ',':
	  if (!depth)
	    return (pos + 1);
	}
    }

  return (-1);
}

/* Returns the sub-match_string for TOKEN. If TOKEN isn't in
 * MATCH_STRING, returns ""
 */
char *
get_sublist (char *token, char *match_string)
{
  int pos = 0, len;
  char *sublist;

  while (1)
    {
      /* got a match */
      if (!strncmp (token, match_string + pos, strlen (token))) break;

      pos = next_level_one (match_string, pos);

      if (pos == -1) return (zero_length_string);
    }

  /* skip to end of token */
  while ((match_string[pos] != ',') && (match_string[pos] != '{')
	 && (match_string[pos] != '\0')) pos++;

  if (match_string[pos] != '{') return (zero_length_string);

  /* find substring */
  len = next_level_one (match_string, pos);

  if (len == -1)
    len = strlen (match_string) - pos + 1;
  else
    len -= pos;

  len -= 3;

  /* extract */
  sublist = xmalloc (len + 1);
  strncpy (sublist, match_string + pos + 1, len);
  sublist[len] = '\0';

  return (sublist);
}

/* Returns an array with the top level entries in SEARCH_TEXT */
char **
get_search_strings (char *search_text)
{
  char **search_strings = NULL;
  int offset, pos = 0, current = 0, max_str;

  search_strings = xmalloc (INCR_VALUE * sizeof (char *));
  max_str = INCR_VALUE;

  while (1)
    {
      offset = 0;
      while ((search_text[pos + offset] != ',')
	     && (search_text[pos + offset] != '{')
	     && (search_text[pos + offset] != '\0')) offset++;

      if (offset == 0) break;

      if (current == max_str - 1)
	{
	  search_strings = xrealloc (search_strings,
				     sizeof (char *) * (max_str + INCR_VALUE));
	  max_str += INCR_VALUE;
	}

      search_strings[current] = xmalloc (offset + 1);
      strncpy (search_strings[current], search_text + pos, offset);
      search_strings[current++][offset] = '\0';

      switch (search_text[pos + offset])
	{
	case ',':
	  pos = pos + offset + 1;
	  break;
	case '{':
	  pos = next_level_one (search_text, pos + offset);
	  break;
	case '\0':
	  goto END;
	}
    }

 END:
  search_strings[current] = NULL;
  return (search_strings);
}

/* Frees the array returned by get_search_strings () */
void
free_search_strings (char *search_strings[])
{
  int index = -1;

  while (search_strings[++index] != NULL) xfree (search_strings[index]);

  xfree (search_strings);
}

/* Completes the current token as much as possible */
void
do_tab_completion (void)
{
  char *first, **matches, **search_strings, *match_string, *token = NULL;
  int token_number = find_current_token_number (), tok;

  search_strings = command_names ();

  first = get_token_by_number (1);

  matches = find_matches (first, search_strings);

  if (matches[0] == NULL)
    {
      warning_beep ();
      return;
    }

  if (token_number == 1)
    {
      /* just matching the first token */
      move_to_token_end ();
      expand_text (first, matches);

      if (matches[1] != NULL) print_partial_matches (matches);

      return;
    }
  else if (matches[1] != NULL)
    {
      /* trying to match other than the first token w/o a unique
       * first token -- bad news
       */
      warning_beep ();
      return;
    }

  /* matching other than the first token */
  match_string = get_match_string (first);

  /* match all preceding tokens to find out what is trying to be matched */
  for (tok = 2; tok < token_number; tok++)
    {
      token = get_token_by_number (tok);
      match_string = get_sublist (token, match_string);

      if (strlen (match_string) == 0)
	{
	  warning_beep ();
	  return;
	}
    }

  token = get_token_by_number (token_number);

  /* got a matchlist for this token */
  search_strings = get_search_strings (match_string);

  matches = find_matches (token, search_strings);

  if (matches[0] == NULL)
    {
      warning_beep ();
      return;
    }

  move_to_token_end ();
  expand_text (token, matches);

  if (matches[1] != NULL) print_partial_matches (matches);

  free_search_strings (search_strings);
}