/* histexpand.c -- history expansion. */

/* Copyright (C) 1989-2010 Free Software Foundation, Inc.

   This file contains the GNU History Library (History), a set of

   routines for managing the text of previously typed lines.

   History 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 3 of the License, or

   (at your option) any later version.

   History 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 History.  If not, see <http://www.gnu.org/licenses/>.

*/

#define READLINE_LIBRARY

#if defined (HAVE_CONFIG_H)

#  include <config.h>

#endif

#include <stdio.h>

#if defined (HAVE_STDLIB_H)

#  include <stdlib.h>

#else

#  include "ansi_stdlib.h"

#endif /* HAVE_STDLIB_H */

#if defined (HAVE_UNISTD_H)

#  ifndef _MINIX

#    include <sys/types.h>

#  endif

#  include <unistd.h>

#endif

#include "rlmbutil.h"

#include "history.h"

#include "histlib.h"

#include "rlshell.h"

#include "xmalloc.h"

#define HISTORY_WORD_DELIMITERS		" \t\n;&()|<>"

#define HISTORY_QUOTE_CHARACTERS	"\"'`"

#define slashify_in_quotes "\\`\"$"

typedef int _hist_search_func_t PARAMS((const char *, int));

static char error_pointer;

static char *subst_lhs;

static char *subst_rhs;

static int subst_lhs_len;

static int subst_rhs_len;

static char *get_history_word_specifier PARAMS((char *, char *, int *));

static int history_tokenize_word PARAMS((const char *, int));

static char **history_tokenize_internal PARAMS((const char *, int, int *));

static char *history_substring PARAMS((const char *, int, int));

static void freewords PARAMS((char **, int));

static char *history_find_word PARAMS((char *, int));

static char *quote_breaks PARAMS((char *));

/* Variables exported by this file. */

/* The character that represents the start of a history expansion

   request.  This is usually `!'. */

char history_expansion_char = '!';

/* The character that invokes word substitution if found at the start of

   a line.  This is usually `^'. */

char history_subst_char = '^';

/* During tokenization, if this character is seen as the first character

   of a word, then it, and all subsequent characters upto a newline are

   ignored.  For a Bourne shell, this should be '#'.  Bash special cases

   the interactive comment character to not be a comment delimiter. */

char history_comment_char = '\0';

/* The list of characters which inhibit the expansion of text if found

   immediately following history_expansion_char. */

char *history_no_expand_chars = " \t\n\r=";

/* If set to a non-zero value, single quotes inhibit history expansion.

   The default is 0. */

int history_quotes_inhibit_expansion = 0;

/* Used to split words by history_tokenize_internal. */

char *history_word_delimiters = HISTORY_WORD_DELIMITERS;

/* If set, this points to a function that is called to verify that a

   particular history expansion should be performed. */

rl_linebuf_func_t *history_inhibit_expansion_function;

/* **************************************************************** */

/*								    */

/*			History Expansion			    */

/*								    */

/* **************************************************************** */

/* Hairy history expansion on text, not tokens.  This is of general

   use, and thus belongs in this library. */

/* The last string searched for by a !?string? search. */

static char *search_string;

/* The last string matched by a !?string? search. */

static char *search_match;

/* Return the event specified at TEXT + OFFSET modifying OFFSET to

   point to after the event specifier.  Just a pointer to the history

   line is returned; NULL is returned in the event of a bad specifier.

   You pass STRING with *INDEX equal to the history_expansion_char that

   begins this specification.

   DELIMITING_QUOTE is a character that is allowed to end the string

   specification for what to search for in addition to the normal

   characters `:', ` ', `\t', `\n', and sometimes `?'.

   So you might call this function like:

   line = get_history_event ("!echo:p", &index, 0);  */

char *

get_history_event (string, caller_index, delimiting_quote)

     const char *string;

     int *caller_index;

     int delimiting_quote;

{

  register int i;

  register char c;

  HIST_ENTRY *entry;

  int which, sign, local_index, substring_okay;

  _hist_search_func_t *search_func;

  char *temp;

  /* The event can be specified in a number of ways.

     !!   the previous command

     !n   command line N

     !-n  current command-line minus N

     !str the most recent command starting with STR

     !?str[?]

	  the most recent command containing STR

     All values N are determined via HISTORY_BASE. */

  i = *caller_index;

  if (string[i] != history_expansion_char)

    return ((char *)NULL);

  /* Move on to the specification. */

  i++;

  sign = 1;

  substring_okay = 0;

#define RETURN_ENTRY(e, w) \

	return ((e = history_get (w)) ? e->line : (char *)NULL)

  /* Handle !! case. */

  if (string[i] == history_expansion_char)

    {

      i++;

      which = history_base + (history_length - 1);

      *caller_index = i;

      RETURN_ENTRY (entry, which);

    }

  /* Hack case of numeric line specification. */

  if (string[i] == '-')

    {

      sign = -1;

      i++;

    }

  if (_rl_digit_p (string[i]))

    {

      /* Get the extent of the digits and compute the value. */

      for (which = 0; _rl_digit_p (string[i]); i++)

	which = (which * 10) + _rl_digit_value (string[i]);

      *caller_index = i;

      if (sign < 0)

	which = (history_length + history_base) - which;

      RETURN_ENTRY (entry, which);

    }

  /* This must be something to search for.  If the spec begins with

     a '?', then the string may be anywhere on the line.  Otherwise,

     the string must be found at the start of a line. */

  if (string[i] == '?')

    {

      substring_okay++;

      i++;

    }

  /* Only a closing `?' or a newline delimit a substring search string. */

  for (local_index = i; c = string[i]; i++)

    {

#if defined (HANDLE_MULTIBYTE)

      if (MB_CUR_MAX > 1 && rl_byte_oriented == 0)

	{

	  int v;

	  mbstate_t ps;

	  memset (&ps, 0, sizeof (mbstate_t));

	  /* These produce warnings because we're passing a const string to a

	     function that takes a non-const string. */

	  _rl_adjust_point ((char *)string, i, &ps);

	  if ((v = _rl_get_char_len ((char *)string + i, &ps)) > 1)

	    {

	      i += v - 1;

	      continue;

	    }

        }

#endif /* HANDLE_MULTIBYTE */

      if ((!substring_okay && (whitespace (c) || c == ':' ||

	  (history_search_delimiter_chars && member (c, history_search_delimiter_chars)) ||

	  string[i] == delimiting_quote)) ||

	  string[i] == '\n' ||

	  (substring_okay && string[i] == '?'))

	break;

    }

  which = i - local_index;

  temp = (char *)xmalloc (1 + which);

  if (which)

    strncpy (temp, string + local_index, which);

  temp[which] = '\0';

  if (substring_okay && string[i] == '?')

    i++;

  *caller_index = i;

#define FAIL_SEARCH() \

  do { \

    history_offset = history_length; xfree (temp) ; return (char *)NULL; \

  } while (0)

  /* If there is no search string, try to use the previous search string,

     if one exists.  If not, fail immediately. */

  if (*temp == '\0' && substring_okay)

    {

      if (search_string)

        {

          xfree (temp);

          temp = savestring (search_string);

        }

      else

        FAIL_SEARCH ();

    }

  search_func = substring_okay ? history_search : history_search_prefix;

  while (1)

    {

      local_index = (*search_func) (temp, -1);

      if (local_index < 0)

	FAIL_SEARCH ();

      if (local_index == 0 || substring_okay)

	{

	  entry = current_history ();

	  history_offset = history_length;

	  /* If this was a substring search, then remember the

	     string that we matched for word substitution. */

	  if (substring_okay)

	    {

	      FREE (search_string);

	      search_string = temp;

	      FREE (search_match);

	      search_match = history_find_word (entry->line, local_index);

	    }

	  else

	    xfree (temp);

	  return (entry->line);

	}

      if (history_offset)

	history_offset--;

      else

	FAIL_SEARCH ();

    }

#undef FAIL_SEARCH

#undef RETURN_ENTRY

}

/* Function for extracting single-quoted strings.  Used for inhibiting

   history expansion within single quotes. */

/* Extract the contents of STRING as if it is enclosed in single quotes.

   SINDEX, when passed in, is the offset of the character immediately

   following the opening single quote; on exit, SINDEX is left pointing

   to the closing single quote.  FLAGS currently used to allow backslash

   to escape a single quote (e.g., for bash $'...'). */

static void

hist_string_extract_single_quoted (string, sindex, flags)

     char *string;

     int *sindex, flags;

{

  register int i;

  for (i = *sindex; string[i] && string[i] != '\''; i++)

    {

      if ((flags & 1) && string[i] == '\\' && string[i+1])

        i++;

    }

  *sindex = i;

}

static char *

quote_breaks (s)

     char *s;

{

  register char *p, *r;

  char *ret;

  int len = 3;

  for (p = s; p && *p; p++, len++)

    {

      if (*p == '\'')

	len += 3;

      else if (whitespace (*p) || *p == '\n')

	len += 2;

    }

  r = ret = (char *)xmalloc (len);

  *r++ = '\'';

  for (p = s; p && *p; )

    {

      if (*p == '\'')

	{

	  *r++ = '\'';

	  *r++ = '\\';

	  *r++ = '\'';

	  *r++ = '\'';

	  p++;

	}

      else if (whitespace (*p) || *p == '\n')

	{

	  *r++ = '\'';

	  *r++ = *p++;

	  *r++ = '\'';

	}

      else

	*r++ = *p++;

    }

  *r++ = '\'';

  *r = '\0';

  return ret;

}

static char *

hist_error(s, start, current, errtype)

      char *s;

      int start, current, errtype;

{

  char *temp;

  const char *emsg;

  int ll, elen;

  ll = current - start;

  switch (errtype)

    {

    case EVENT_NOT_FOUND:

      emsg = "event not found";

      elen = 15;

      break;

    case BAD_WORD_SPEC:

      emsg = "bad word specifier";

      elen = 18;

      break;

    case SUBST_FAILED:

      emsg = "substitution failed";

      elen = 19;

      break;

    case BAD_MODIFIER:

      emsg = "unrecognized history modifier";

      elen = 29;

      break;

    case NO_PREV_SUBST:

      emsg = "no previous substitution";

      elen = 24;

      break;

    default:

      emsg = "unknown expansion error";

      elen = 23;

      break;

    }

  temp = (char *)xmalloc (ll + elen + 3);

  strncpy (temp, s + start, ll);

  temp[ll] = ':';

  temp[ll + 1] = ' ';

  strcpy (temp + ll + 2, emsg);

  return (temp);

}

/* Get a history substitution string from STR starting at *IPTR

   and return it.  The length is returned in LENPTR.

   A backslash can quote the delimiter.  If the string is the

   empty string, the previous pattern is used.  If there is

   no previous pattern for the lhs, the last history search

   string is used.

   If IS_RHS is 1, we ignore empty strings and set the pattern

   to "" anyway.  subst_lhs is not changed if the lhs is empty;

   subst_rhs is allowed to be set to the empty string. */

static char *

get_subst_pattern (str, iptr, delimiter, is_rhs, lenptr)

     char *str;

     int *iptr, delimiter, is_rhs, *lenptr;

{

  register int si, i, j, k;

  char *s;

#if defined (HANDLE_MULTIBYTE)

  mbstate_t ps;

#endif

  s = (char *)NULL;

  i = *iptr;

#if defined (HANDLE_MULTIBYTE)

  memset (&ps, 0, sizeof (mbstate_t));

  _rl_adjust_point (str, i, &ps);

#endif

  for (si = i; str[si] && str[si] != delimiter; si++)

#if defined (HANDLE_MULTIBYTE)

    if (MB_CUR_MAX > 1 && rl_byte_oriented == 0)

      {

	int v;

	if ((v = _rl_get_char_len (str + si, &ps)) > 1)

	  si += v - 1;

	else if (str[si] == '\\' && str[si + 1] == delimiter)

	  si++;

      }

    else

#endif /* HANDLE_MULTIBYTE */

      if (str[si] == '\\' && str[si + 1] == delimiter)

	si++;

  if (si > i || is_rhs)

    {

      s = (char *)xmalloc (si - i + 1);

      for (j = 0, k = i; k < si; j++, k++)

	{

	  /* Remove a backslash quoting the search string delimiter. */

	  if (str[k] == '\\' && str[k + 1] == delimiter)

	    k++;

	  s[j] = str[k];

	}

      s[j] = '\0';

      if (lenptr)

	*lenptr = j;

    }

  i = si;

  if (str[i])

    i++;

  *iptr = i;

  return s;

}

static void

postproc_subst_rhs ()

{

  char *new;

  int i, j, new_size;

  new = (char *)xmalloc (new_size = subst_rhs_len + subst_lhs_len);

  for (i = j = 0; i < subst_rhs_len; i++)

    {

      if (subst_rhs[i] == '&')

	{

	  if (j + subst_lhs_len >= new_size)

	    new = (char *)xrealloc (new, (new_size = new_size * 2 + subst_lhs_len));

	  strcpy (new + j, subst_lhs);

	  j += subst_lhs_len;

	}

      else

	{

	  /* a single backslash protects the `&' from lhs interpolation */

	  if (subst_rhs[i] == '\\' && subst_rhs[i + 1] == '&')

	    i++;

	  if (j >= new_size)

	    new = (char *)xrealloc (new, new_size *= 2);

	  new[j++] = subst_rhs[i];

	}

    }

  new[j] = '\0';

  xfree (subst_rhs);

  subst_rhs = new;

  subst_rhs_len = j;

}

/* Expand the bulk of a history specifier starting at STRING[START].

   Returns 0 if everything is OK, -1 if an error occurred, and 1

   if the `p' modifier was supplied and the caller should just print

   the returned string.  Returns the new index into string in

   *END_INDEX_PTR, and the expanded specifier in *RET_STRING. */

static int

history_expand_internal (string, start, end_index_ptr, ret_string, current_line)

     char *string;

     int start, *end_index_ptr;

     char **ret_string;

     char *current_line;	/* for !# */

{

  int i, n, starting_index;

  int substitute_globally, subst_bywords, want_quotes, print_only;

  char *event, *temp, *result, *tstr, *t, c, *word_spec;

  int result_len;

#if defined (HANDLE_MULTIBYTE)

  mbstate_t ps;

  memset (&ps, 0, sizeof (mbstate_t));

#endif

  result = (char *)xmalloc (result_len = 128);

  i = start;

  /* If it is followed by something that starts a word specifier,

     then !! is implied as the event specifier. */

  if (member (string[i + 1], ":$*%^"))

    {

      char fake_s[3];

      int fake_i = 0;

      i++;

      fake_s[0] = fake_s[1] = history_expansion_char;

      fake_s[2] = '\0';

      event = get_history_event (fake_s, &fake_i, 0);

    }

  else if (string[i + 1] == '#')

    {

      i += 2;

      event = current_line;

    }

  else

    {

      int quoted_search_delimiter = 0;

      /* If the character before this `!' is a double or single

	 quote, then this expansion takes place inside of the

	 quoted string.  If we have to search for some text ("!foo"),

	 allow the delimiter to end the search string. */

#if defined (HANDLE_MULTIBYTE)

      if (MB_CUR_MAX > 1 && rl_byte_oriented == 0)

	{

	  int ch, l;

	  l = _rl_find_prev_mbchar (string, i, MB_FIND_ANY);

	  ch = string[l];

	  /* XXX - original patch had i - 1 ???  If i == 0 it would fail. */

	  if (i && (ch == '\'' || ch == '"'))

	    quoted_search_delimiter = ch;

	}

      else

#endif /* HANDLE_MULTIBYTE */	  

	if (i && (string[i - 1] == '\'' || string[i - 1] == '"'))

	  quoted_search_delimiter = string[i - 1];

      event = get_history_event (string, &i, quoted_search_delimiter);

    }

  if (event == 0)

    {

      *ret_string = hist_error (string, start, i, EVENT_NOT_FOUND);

      xfree (result);

      return (-1);

    }

  /* If a word specifier is found, then do what that requires. */

  starting_index = i;

  word_spec = get_history_word_specifier (string, event, &i);

  /* There is no such thing as a `malformed word specifier'.  However,

     it is possible for a specifier that has no match.  In that case,

     we complain. */

  if (word_spec == (char *)&error_pointer)

    {

      *ret_string = hist_error (string, starting_index, i, BAD_WORD_SPEC);

      xfree (result);

      return (-1);

    }

  /* If no word specifier, than the thing of interest was the event. */

  temp = word_spec ? savestring (word_spec) : savestring (event);

  FREE (word_spec);

  /* Perhaps there are other modifiers involved.  Do what they say. */

  want_quotes = substitute_globally = subst_bywords = print_only = 0;

  starting_index = i;

  while (string[i] == ':')

    {

      c = string[i + 1];

      if (c == 'g' || c == 'a')

	{

	  substitute_globally = 1;

	  i++;

	  c = string[i + 1];

	}

      else if (c == 'G')

	{

	  subst_bywords = 1;

	  i++;

	  c = string[i + 1];

	}

      switch (c)

	{

	default:

	  *ret_string = hist_error (string, i+1, i+2, BAD_MODIFIER);

	  xfree (result);

	  xfree (temp);

	  return -1;

	case 'q':

	  want_quotes = 'q';

	  break;

	case 'x':

	  want_quotes = 'x';

	  break;

	  /* :p means make this the last executed line.  So we

	     return an error state after adding this line to the

	     history. */

	case 'p':

	  print_only++;

	  break;

	  /* :t discards all but the last part of the pathname. */

	case 't':

	  tstr = strrchr (temp, '/');

	  if (tstr)

	    {

	      tstr++;

	      t = savestring (tstr);

	      xfree (temp);

	      temp = t;

	    }

	  break;

	  /* :h discards the last part of a pathname. */

	case 'h':

	  tstr = strrchr (temp, '/');

	  if (tstr)

	    *tstr = '\0';

	  break;

	  /* :r discards the suffix. */

	case 'r':

	  tstr = strrchr (temp, '.');

	  if (tstr)

	    *tstr = '\0';

	  break;

	  /* :e discards everything but the suffix. */

	case 'e':

	  tstr = strrchr (temp, '.');

	  if (tstr)

	    {

	      t = savestring (tstr);

	      xfree (temp);

	      temp = t;

	    }

	  break;

	/* :s/this/that substitutes `that' for the first

	   occurrence of `this'.  :gs/this/that substitutes `that'

	   for each occurrence of `this'.  :& repeats the last

	   substitution.  :g& repeats the last substitution

	   globally. */

	case '&':

	case 's':

	  {

	    char *new_event;

	    int delimiter, failed, si, l_temp, ws, we;

	    if (c == 's')

	      {

		if (i + 2 < (int)strlen (string))

		  {

#if defined (HANDLE_MULTIBYTE)

		    if (MB_CUR_MAX > 1 && rl_byte_oriented == 0)

		      {

			_rl_adjust_point (string, i + 2, &ps);

			if (_rl_get_char_len (string + i + 2, &ps) > 1)

			  delimiter = 0;

			else

			  delimiter = string[i + 2];

		      }

		    else

#endif /* HANDLE_MULTIBYTE */

		      delimiter = string[i + 2];

		  }

		else

		  break;	/* no search delimiter */

		i += 3;

		t = get_subst_pattern (string, &i, delimiter, 0, &subst_lhs_len);

		/* An empty substitution lhs with no previous substitution

		   uses the last search string as the lhs. */

		if (t)

		  {

		    FREE (subst_lhs);

		    subst_lhs = t;

		  }

		else if (!subst_lhs)

		  {

		    if (search_string && *search_string)

		      {

			subst_lhs = savestring (search_string);

			subst_lhs_len = strlen (subst_lhs);

		      }

		    else

		      {

			subst_lhs = (char *) NULL;

			subst_lhs_len = 0;

		      }

		  }

		FREE (subst_rhs);

		subst_rhs = get_subst_pattern (string, &i, delimiter, 1, &subst_rhs_len);

		/* If `&' appears in the rhs, it's supposed to be replaced

		   with the lhs. */

		if (member ('&', subst_rhs))

		  postproc_subst_rhs ();

	      }

	    else

	      i += 2;

	    /* If there is no lhs, the substitution can't succeed. */

	    if (subst_lhs_len == 0)

	      {

		*ret_string = hist_error (string, starting_index, i, NO_PREV_SUBST);

		xfree (result);

		xfree (temp);

		return -1;

	      }

	    l_temp = strlen (temp);

	    /* Ignore impossible cases. */

	    if (subst_lhs_len > l_temp)

	      {

		*ret_string = hist_error (string, starting_index, i, SUBST_FAILED);

		xfree (result);

		xfree (temp);

		return (-1);

	      }

	    /* Find the first occurrence of THIS in TEMP. */

	    /* Substitute SUBST_RHS for SUBST_LHS in TEMP.  There are three

	       cases to consider:

		 1.  substitute_globally == subst_bywords == 0

		 2.  substitute_globally == 1 && subst_bywords == 0

		 3.  substitute_globally == 0 && subst_bywords == 1

	       In the first case, we substitute for the first occurrence only.

	       In the second case, we substitute for every occurrence.

	       In the third case, we tokenize into words and substitute the

	       first occurrence of each word. */

	    si = we = 0;

	    for (failed = 1; (si + subst_lhs_len) <= l_temp; si++)

	      {

		/* First skip whitespace and find word boundaries if

		   we're past the end of the word boundary we found

		   the last time. */

		if (subst_bywords && si > we)

		  {

		    for (; temp[si] && whitespace (temp[si]); si++)

		      ;

		    ws = si;

		    we = history_tokenize_word (temp, si);

		  }

		if (STREQN (temp+si, subst_lhs, subst_lhs_len))

		  {

		    int len = subst_rhs_len - subst_lhs_len + l_temp;

		    new_event = (char *)xmalloc (1 + len);

		    strncpy (new_event, temp, si);

		    strncpy (new_event + si, subst_rhs, subst_rhs_len);

		    strncpy (new_event + si + subst_rhs_len,

			     temp + si + subst_lhs_len,

			     l_temp - (si + subst_lhs_len));

		    new_event[len] = '\0';

		    xfree (temp);

		    temp = new_event;

		    failed = 0;

		    if (substitute_globally)

		      {

			/* Reported to fix a bug that causes it to skip every

			   other match when matching a single character.  Was

			   si += subst_rhs_len previously. */

			si += subst_rhs_len - 1;

			l_temp = strlen (temp);

			substitute_globally++;

			continue;

		      }

		    else if (subst_bywords)

		      {

			si = we;

			l_temp = strlen (temp);

			continue;

		      }

		    else

		      break;

		  }

	      }

	    if (substitute_globally > 1)

	      {

		substitute_globally = 0;

		continue;	/* don't want to increment i */

	      }

	    if (failed == 0)

	      continue;		/* don't want to increment i */

	    *ret_string = hist_error (string, starting_index, i, SUBST_FAILED);

	    xfree (result);

	    xfree (temp);

	    return (-1);

	  }

	}

      i += 2;

    }

  /* Done with modfiers. */

  /* Believe it or not, we have to back the pointer up by one. */

  --i;

  if (want_quotes)

    {

      char *x;

      if (want_quotes == 'q')

	x = sh_single_quote (temp);

      else if (want_quotes == 'x')

	x = quote_breaks (temp);

      else

	x = savestring (temp);

      xfree (temp);

      temp = x;

    }

  n = strlen (temp);

  if (n >= result_len)

    result = (char *)xrealloc (result, n + 2);

  strcpy (result, temp);

  xfree (temp);