/* GRegex -- regular expression API wrapper around PCRE.
 * Copyright (C) 1999, 2000 Scott Wimer
 * Copyright (C) 2004 Matthias Clasen <mclasen@redhat.com>
 *
 * This is basically an ease of user wrapper around the functionality of
 * PCRE.
 *
 * With this library, we are, hopefully, drastically reducing the code
 * complexity necessary by making use of a more complex and detailed
 * data structure to store the regex info.  I am hoping to have a regex
 * interface that is almost as easy to use as Perl's.  <fingers crossed>
 *
 * Author: Scott Wimer <scottw@cylant.com>
 *
 * This library 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.  
 *
 * This library is free software, you can distribute it or modify it
 * under any of the following terms:
 *  1) The GNU General Public License (GPL)
 *  2) The GNU Library General Public License (LGPL)
 *  3) The Perl Artistic license (Artistic)
 *  4) The BSD license (BSD)
 *
 * In short, you can use this library in any code you desire, so long as
 * the Copyright notice above remains intact.  If you do make changes to
 * it, I would appreciate that you let me know so I can improve this 
 * library for everybody, but I'm not gonna force you to.
 * 
 * Please note that this library is just a wrapper around Philip Hazel's
 * PCRE library.  Please see the file 'LICENSE' in your PCRE distribution.
 * And, if you live in England, please send him a pint of good beer, his
 * library is great.
 *
 */

#include "config.h"
#include "gregex.h"
#include "gi18n-lib.h"
#include "pcre/pcre.h"

struct _GRegex
{
  gchar *pattern;       /* the pattern */
  pcre *regex;		/* compiled form of the pattern */
  pcre_extra *extra;	/* data stored when g_regex_optimize() is used */
  gint matches;		/* number of matching sub patterns */
  gint pos;		/* position in the string where last match left off */
  gint *offsets;	/* array of offsets paired 0,1 ; 2,3 ; 3,4 etc */
  gint n_offsets;	/* number of offsets */
  GRegexCompileFlags compile_opts;	/* options used at compile time on the pattern */
  GRegexMatchFlags match_opts;	/* options used at match time on the regex */
  gint string_len;	/* length of the string last used against */
  GSList *delims;	/* delimiter sub strings from split next */
};

GQuark
g_regex_error_quark (void)
{
  static GQuark error_quark = 0;

  if (error_quark == 0)
    error_quark = g_quark_from_static_string ("g-regex-error-quark");

  return error_quark;
}

/** 
 * g_regex_new:
 * @pattern: the regular expression
 * @compile_options: compile options for the regular expression
 * @match_options: match options for the regular expression
 * @error: return location for a #GError
 * 
 * Compiles the regular expression to an internal form, and does the initial
 * setup of the #GRegex structure.  
 * 
 * Returns: a #GRegex structure
 */
GRegex *
g_regex_new (const gchar         *pattern, 
 	     GRegexCompileFlags   compile_options,
	     GRegexMatchFlags     match_options,
	     GError             **error)
{
  GRegex *regex = g_new0 (GRegex, 1);
  const gchar *errmsg;
  gint erroffset;
  gint capture_count;
  
  /* preset the parts of gregex that need to be set, regardless of the
   * type of match that will be checked */
  regex->pattern = g_strdup (pattern);
  regex->extra = NULL;
  regex->pos = 0;
  regex->string_len = -1;	/* not set yet */

  /* set the options */
  regex->compile_opts = compile_options | PCRE_UTF8 | PCRE_NO_UTF8_CHECK;
  regex->match_opts = match_options | PCRE_NO_UTF8_CHECK;

  /* compile the pattern */
  regex->regex = _pcre_compile (pattern, regex->compile_opts,
				 &errmsg, &erroffset, NULL);

  /* if the compilation failed, set the error member and return 
   * immediately */
  if (regex->regex == NULL)
    {
      GError *tmp_error = g_error_new (G_REGEX_ERROR, 0, 
				       _("Error while compiling regular "
					 "expression %s at char %d: %s"),
				       pattern, erroffset, errmsg);
      g_propagate_error (error, tmp_error);

      return regex;
    }

  /* otherwise, find out how many sub patterns exist in this pattern,
   * and setup the offsets array and n_offsets accordingly */
  _pcre_fullinfo (regex->regex, regex->extra, 
		  PCRE_INFO_CAPTURECOUNT, &capture_count);
  regex->n_offsets = (capture_count + 1) * 3;
  regex->offsets = g_new0 (gint, regex->n_offsets);

  return regex;
}


/**
 * g_regex_free:
 * @regex: a #GRegex structure from g_regex_new()
 *
 * Frees all the memory associated with the regex structure.
 */
void
g_regex_free (GRegex *regex)
{
  g_free (regex->pattern);
  g_slist_free (regex->delims);
  g_free (regex->offsets);
  if (regex->regex != NULL)
    _pcre_free (regex->regex);
  if (regex->extra != NULL)
    _pcre_free (regex->extra);
  g_free (regex);
}


/**
 * g_regex_clear:
 * @regex: a #GRegex structure
 *
 * Clears out the members of @regex that are holding information about the
 * last set of matches for this pattern.  g_regex_clear() needs to be
 * called between uses of g_regex_match() or g_regex_match_next() against
 * new target strings. 
 */
void
g_regex_clear (GRegex *regex)
{
  regex->matches = -1;
  regex->string_len = -1;
  regex->pos = 0;

  /* if the pattern was used with g_regex_split_next(), it may have
   * delimiter offsets stored.  Free up those guys as well. */
  if (regex->delims != NULL)
    g_slist_free (regex->delims);
}

/**
 * g_regex_optimize:
 * @regex: a #GRegex structure
 * @error: return location for a #GError
 *
 * If the pattern will be used many times, then it may be worth the
 * effort to optimize it to improve the speed of matches.
 */
void
g_regex_optimize (GRegex  *regex,
		  GError **error)
{
  const gchar *errmsg;

  regex->extra = _pcre_study (regex->regex, 0, &errmsg);

  if (errmsg)
    {
      GError *tmp_error = g_error_new (G_REGEX_ERROR,
				       0, _("Error while optimizing "
					    "regular expression %s: %s"),
				       regex->pattern,
				       errmsg);
      g_propagate_error (error, tmp_error);
    }
}

/**
 * g_regex_match:
 * @regex: a #GRegex structure from g_regex_new()
 * @string: the string to scan for matches
 * @string_len: the length of @string, or -1 to use strlen()
 * @match_options:  match options
 *
 * Scans for a match in string for the pattern in @regex. The starting index
 * of the match goes into the pos member of the @regex struct. The indexes
 * of the full match, and all matches get stored off in the offsets array.
 *
 * The @match_options are combined with the match options specified when the 
 * @regex structure was created, letting you have more flexibility in reusing
 * #GRegex structures.
 *
 * Returns:  Number of matched substrings + 1, or 1 if the pattern has no
 *           substrings in it.  Returns #GREGEX_NOMATCH if the pattern
 *           did not match.
 */
gint 
g_regex_match (GRegex          *regex, 
	       const gchar     *string, 
	       gssize           string_len,
	       GRegexMatchFlags match_options)
{
  if (string_len < 0)
    string_len = strlen (string);

  regex->string_len = string_len;

  /* perform the match */
  regex->matches = _pcre_exec (regex->regex, regex->extra, 
			       string, regex->string_len, 0,
			       regex->match_opts | match_options,
			       regex->offsets, regex->n_offsets);

  /* if the regex matched, set regex->pos to the character past the 
   * end of the match.
   */
  if (regex->matches > 0)
    regex->pos = regex->offsets[1];

  return regex->matches;	/* return what pcre_exec() returned */
}


/**
 * g_regex_match_next:
 * @regex: a #GRegex structure 
 * @string: the string to scan for matches
 * @string_len: the length of @string, or -1 to use strlen()
 * @match_options: the match options
 *
 * Scans for the next match in @string of the pattern in @regex.  The starting 
 * index of the match goes into the pos member of the @regex struct.  The 
 * indexes of the full match, and all matches get stored off in the offsets 
 * array.  The match options are ored with the match options set when
 * the @regex was created.
 *
 * You have to call g_regex_clear() to reuse the same pattern on a new string.
 * This is especially true for use with g_regex_match_next().
 *
 * Returns:  Number of matched substrings + 1, or 1 if the pattern has no
 *           substrings in it.  Returns #GREGEX_NOMATCH if the pattern
 *           did not match.
 */
gint 
g_regex_match_next (GRegex          *regex, 
		    const gchar     *string, 
		    gssize           string_len,
		    GRegexMatchFlags match_options)
{
  /* if this regex hasn't been used on this string before, then we
   * need to calculate the length of the string, and set pos to the
   * start of it.  
   * Knowing if this regex has been used on this string is a bit of 
   * a challenge.  For now, we require the user to call g_regex_clear()
   * in between usages on a new string.  Not perfect, but not such a
   * bad solution either.
   */
  if (regex->string_len == -1)
    {
      if (string_len < 0)
	string_len = strlen (string);
      
      regex->string_len = string_len;
    }

  /* perform the match */
  regex->matches = _pcre_exec (regex->regex, regex->extra,
			       string + regex->pos, 
			       regex->string_len - regex->pos,
			       0, regex->match_opts | match_options,
			       regex->offsets, regex->n_offsets);

  /* if the regex matched, adjust the offsets array to take into account
   * the fact that the string they're out of is shorter than the string
   * that the caller passed us, by regex->pos to be exact.
   * Then, update regex->pos to take into account the new starting point.
   */
  if (regex->matches > 0)
    {
      gint i, pieces;
      pieces = (regex->matches * 2) - 1;

      for (i = 0; i <= pieces; i++)
	regex->offsets[i] += regex->pos;

      regex->pos = regex->offsets[1];
    }

  return regex->matches;
}


/**
 * g_regex_fetch:
 * @regex: #GRegex structure used in last match
 * @string: the string on which the last match was made
 * @match_num: number of the sub expression
 *
 * Retrieves the text matching the @match_num<!-- -->'th capturing parentheses.
 * 0 is the full text of the match, 1 is the first paren set, 2 the second,
 * and so on.
 *
 * Returns: The matched substring.  You have to free it yourself.
 */
gchar *
g_regex_fetch (GRegex      *regex, 
	       const gchar *string,
	       gint         match_num)
{
  gchar *match;

  /* make sure the sub expression number they're requesting is less than
   * the total number of sub expressions that were matched. */
  if (match_num >= regex->matches)
    return NULL;

  _pcre_get_substring (string, regex->offsets, regex->matches, 
		       match_num, (const char **)&match);

  return match;
}

/**
 * g_regex_fetch_all:
 * @regex: a #GRegex structure
 * @string: the string on which the last match was made
 *
 * Bundles up pointers to each of the matching substrings from a match 
 * and stores then in an array of gchar pointers.
 *
 * Returns: a %NULL-terminated array of gchar * pointers. It must be freed using
 * g_strfreev(). If the memory can't be allocated, returns %NULL.
 */
gchar **
g_regex_fetch_all (GRegex      *regex,
		   const gchar *string)
{
  gchar **listptr = NULL; /* the list pcre_get_substring_list() will fill */
  gchar **result;

  if (regex->matches < 0)
    return NULL;
  
  _pcre_get_substring_list (string, regex->offsets, 
			    regex->matches, (const char ***)&listptr);

  if (listptr)
    {
      /* PCRE returns a single block of memory which
       * isn't suitable for g_strfreev().
       */
      result = g_strdupv (listptr);
      _pcre_free (listptr);
    }
  else 
    result = NULL;

  return result;
}


/**
 * g_regex_split:
 * @regex:  a #GRegex structure
 * @string:  the string to split with the pattern
 * @string_len: the length of @string, or -1 to use strlen()
 * @match_options:  match time option flags
 * @max_pieces:  maximum number of pieces to split the string into, 
 *    or 0 for no limit
 *
 * Breaks the string on the pattern, and returns an array of the pieces.  
 *
 * Returns: a %NULL-terminated gchar ** array. Free it using g_strfreev().
 **/
gchar **
g_regex_split (GRegex           *regex, 
	       const gchar      *string, 
	       gssize            string_len,
	       GRegexMatchFlags  match_options,
	       gint              max_pieces)
{
  gchar **string_list;		/* The array of char **s worked on */
  gint pos;
  gint match_ret;
  gint pieces;
  gint start_pos;
  gchar *piece;
  GList *list, *last;

  start_pos = 0;
  pieces = 0;
  list = NULL;
  while (TRUE)
    {
      match_ret = g_regex_match_next (regex, string, string_len, match_options);
      if ((match_ret > 0) && ((max_pieces == 0) || (pieces < max_pieces)))
	{
	  piece = g_strndup (string + start_pos, regex->offsets[0] - start_pos);
	  list = g_list_prepend (list, piece);

	  /* if there were substrings, these need to get added to the
	   * list as well */
	  if (match_ret > 1)
	    {
	      int i;
	      for (i = 1; i < match_ret; i++)
		list = g_list_prepend (list, g_regex_fetch (regex, string, i));
	    }

	  start_pos = regex->pos;	/* move start_pos to end of match */
	  pieces++;
	}
      else	 /* if there was no match, copy to end of string, and break */
	{
	  piece = g_strndup (string + start_pos, regex->string_len - start_pos);
	  list = g_list_prepend (list, piece);
	  break;
	}
    }

  string_list = (gchar **) g_malloc (sizeof (gchar *) * (g_list_length (list) + 1));
  pos = 0;
  for (last = g_list_last (list); last; last = last->prev)
    string_list[pos++] = last->data;
  string_list[pos] = 0;

  g_list_free (list);
  return string_list;
}


/**
 * g_regex_split_next:
 * @pattern:  gchar pointer to the pattern
 * @string:  the string to split on pattern
 * @string_len: the length of @string, or -1 to use strlen()
 * @match_options:  match time options for the regex
 *
 * g_regex_split_next() breaks the string on pattern, and returns the  
 * pieces, one per call.  If the pattern contains capturing parentheses, 
 * then the text for each of the substrings will also be returned.
 * If the pattern does not match anywhere in the string, then the whole 
 * string is returned as the first piece.
 *
 * Returns:  a gchar * to the next piece of the string
 */
gchar *
g_regex_split_next (GRegex      *regex, 
		    const gchar *string, 
		    gssize       string_len, 
		    GRegexMatchFlags match_options)
{
  gint start_pos = regex->pos;
  gchar *piece = NULL;
  gint match_ret;

  /* if there are delimiter substrings stored, return those one at a
   * time.  
   */
  if (regex->delims != NULL)
    {
      piece = regex->delims->data;
      regex->delims = g_slist_remove (regex->delims, piece);
      return piece;
    }

  /* otherwise...
   * use g_regex_match_next() to find the next occurance of the pattern
   * in the string.  We use start_pos to keep track of where the stuff
   * up to the current match starts.  Copy that piece of the string off
   * and append it to the buffer using strncpy.  We have to NUL term the
   * piece we copied off before returning it.
   */
  match_ret = g_regex_match_next (regex, string, string_len, match_options);
  if (match_ret > 0)
    {
      piece = g_strndup (string + start_pos, regex->offsets[0] - start_pos);

      /* if there were substrings, these need to get added to the
       * list of delims */
      if (match_ret > 1)
	{
	  gint i;
	  for (i = 1; i < match_ret; i++)
	    regex->delims = g_slist_append (regex->delims,
					     g_regex_fetch (regex, string, i));
	}
    }
  else		/* if there was no match, copy to end of string */
    piece = g_strndup (string + start_pos, regex->string_len - start_pos);

  return piece;
}

static gboolean
copy_replacement (GRegex      *regex,
		  const gchar *string,
		  GString     *result,
	          gpointer     data)
{
  g_string_append (result, (gchar *)data);

  return FALSE;
}

typedef struct 
{
  gchar **pieces; /* the split replacement text */
  gint  *match;   /* if pieces[i] is a backreference $n
		   * match[i] is n, else 0
		   */
} InterpolationData;

static gboolean
interpolate_replacement (GRegex      *regex,
			 const gchar *string,
			 GString     *result,
			 gpointer     data)
{
  InterpolationData *idata = data;
  gint i;
  gchar *match;

  for (i = 0; idata->pieces[i]; i++)
    {
      if (idata->match[i] == 0)
	g_string_append (result, idata->pieces[i]);
      else
	{
	  match = g_regex_fetch (regex, string, idata->match[i]);

	  if (match) 
	    g_string_append (result, match);
	  else
	    g_string_append (result, idata->pieces[i]);

	  g_free (match);
	}
    }

  return FALSE;  
}

/**
 * g_regex_replace:
 * @regex:  a #GRegex structure
 * @string:  the string to perform matches against
 * @string_len: the length of @string, or -1 to use strlen()
 * @replacement:  text to replace each match with
 * @match_options:  options for the match
 *
 * Replaces all occurances of the pattern in @regex with the 
 * replacement text. Backreferences of the form $n in the replacement
 * text are interpolated by the n-th captured subexpression of 
 * the match.
 *
 * Returns: a newly allocated string containing the replacements.
 */
gchar *
g_regex_replace (GRegex      *regex, 
		 const gchar *string, 
		 gssize       string_len,
		 const gchar *replacement,
		 GRegexMatchFlags match_options)
{
  GRegex *r;
  gchar *result;
  InterpolationData data;
  gchar *endptr;
  gint i;

  /* avoid overhead if the replacement text 
   * contains no backreferences
   */
  if (!strchr (replacement, '$'))
    return g_regex_replace_eval (regex, 
				 string, string_len,
				 copy_replacement,
				 (gpointer)replacement,
				 match_options);

  /* look for backreferences of the form $n
   */
  r = g_regex_new ("(\\$[1-9][0-9]*)", 0, 0, NULL);
  data.pieces = g_regex_split (r, replacement, -1, 0, 0);
  g_regex_free (r);
  
  for (i = 0; data.pieces[i]; i++) ;
  data.match = g_new (gint, i);
  
  for (i = 0; data.pieces[i]; i++) 
    {
      if (data.pieces[i][0] == '$')
	{
	  data.match[i] = strtol (data.pieces[i] + 1, &endptr, 10);
	  
	  if (*endptr != 0)
	    data.match[i] = 0;
	}
      else
	data.match[i] = 0; 
    }
  
  result = g_regex_replace_eval (regex, 
				 string, string_len,
				 interpolate_replacement,
				 &data,
				 match_options);
  
  g_strfreev (data.pieces);
  g_free (data.match);
  
  return result;
}


/**
 * g_regex_replace_eval:
 * @gregex:  a #GRegex structure
 * @string:  string to perform matches against
 * @string_len: the length of @string, or -1 to use strlen()
 * @eval: a function to call for each match
 * @match_options:  Options for the match
 *
 * Replaces occurances of the pattern in regex with
 * the output of @eval for that occurance.
 *
 * Returns: a newly allocated string containing the replacements.
 */
gchar *
g_regex_replace_eval (GRegex             *regex, 
		      const gchar        *string,
		      gssize              string_len,
		      GRegexEvalCallback  eval,
		      gpointer            user_data, 
		      GRegexMatchFlags match_options)
{
  GString *result;
  gint str_pos = 0;
  gboolean done = FALSE;

  if (string_len < 0)
    string_len = strlen (string);

  /* clear out the regex for reuse, just in case */
  g_regex_clear (regex);

  result = g_string_sized_new (string_len);

  /* run down the string making matches. */
  while (g_regex_match_next (regex, string, string_len, match_options) > 0 && !done)
    {
      g_string_append_len (result, 
			   string + str_pos, 
			   regex->offsets[0] - str_pos);
      done = (*eval) (regex, string, result, user_data);
      str_pos = regex->offsets[1];
    }
  
  g_string_append_len (result, string + str_pos, string_len - str_pos);

  return g_string_free (result, FALSE);
}

