/* Extended regular expression matching and search library.

   Copyright (C) 2002-2018 Free Software Foundation, Inc.

   This file is part of the GNU C Library.

   Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.

   The GNU C Library 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.

   The GNU C 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.  See the GNU

   General Public License for more details.

   You should have received a copy of the GNU General Public

   License along with the GNU C Library; if not, see

   <https://www.gnu.org/licenses/>.  */

static void re_string_construct_common (const char *str, Idx len,

					re_string_t *pstr,

					RE_TRANSLATE_TYPE trans, bool icase,

					const re_dfa_t *dfa);

static re_dfastate_t *create_ci_newstate (const re_dfa_t *dfa,

					  const re_node_set *nodes,

					  re_hashval_t hash);

static re_dfastate_t *create_cd_newstate (const re_dfa_t *dfa,

					  const re_node_set *nodes,

					  unsigned int context,

					  re_hashval_t hash);

static reg_errcode_t re_string_realloc_buffers (re_string_t *pstr,

						Idx new_buf_len);

#ifdef RE_ENABLE_I18N

static void build_wcs_buffer (re_string_t *pstr);

static reg_errcode_t build_wcs_upper_buffer (re_string_t *pstr);

#endif /* RE_ENABLE_I18N */

static void build_upper_buffer (re_string_t *pstr);

static void re_string_translate_buffer (re_string_t *pstr);

static unsigned int re_string_context_at (const re_string_t *input, Idx idx,

					  int eflags) __attribute__ ((pure));

/* Functions for string operation.  */

/* This function allocate the buffers.  It is necessary to call

   re_string_reconstruct before using the object.  */

static reg_errcode_t

__attribute_warn_unused_result__

re_string_allocate (re_string_t *pstr, const char *str, Idx len, Idx init_len,

		    RE_TRANSLATE_TYPE trans, bool icase, const re_dfa_t *dfa)

{

  reg_errcode_t ret;

  Idx init_buf_len;

  /* Ensure at least one character fits into the buffers.  */

  if (init_len < dfa->mb_cur_max)

    init_len = dfa->mb_cur_max;

  init_buf_len = (len + 1 < init_len) ? len + 1: init_len;

  re_string_construct_common (str, len, pstr, trans, icase, dfa);

  ret = re_string_realloc_buffers (pstr, init_buf_len);

  if (BE (ret != REG_NOERROR, 0))

    return ret;

  pstr->word_char = dfa->word_char;

  pstr->word_ops_used = dfa->word_ops_used;

  pstr->mbs = pstr->mbs_allocated ? pstr->mbs : (unsigned char *) str;

  pstr->valid_len = (pstr->mbs_allocated || dfa->mb_cur_max > 1) ? 0 : len;

  pstr->valid_raw_len = pstr->valid_len;

  return REG_NOERROR;

}

/* This function allocate the buffers, and initialize them.  */

static reg_errcode_t

__attribute_warn_unused_result__

re_string_construct (re_string_t *pstr, const char *str, Idx len,

		     RE_TRANSLATE_TYPE trans, bool icase, const re_dfa_t *dfa)

{

  reg_errcode_t ret;

  memset (pstr, '\0', sizeof (re_string_t));

  re_string_construct_common (str, len, pstr, trans, icase, dfa);

  if (len > 0)

    {

      ret = re_string_realloc_buffers (pstr, len + 1);

      if (BE (ret != REG_NOERROR, 0))

	return ret;

    }

  pstr->mbs = pstr->mbs_allocated ? pstr->mbs : (unsigned char *) str;

  if (icase)

    {

#ifdef RE_ENABLE_I18N

      if (dfa->mb_cur_max > 1)

	{

	  while (1)

	    {

	      ret = build_wcs_upper_buffer (pstr);

	      if (BE (ret != REG_NOERROR, 0))

		return ret;

	      if (pstr->valid_raw_len >= len)

		break;

	      if (pstr->bufs_len > pstr->valid_len + dfa->mb_cur_max)

		break;

	      ret = re_string_realloc_buffers (pstr, pstr->bufs_len * 2);

	      if (BE (ret != REG_NOERROR, 0))

		return ret;

	    }

	}

      else

#endif /* RE_ENABLE_I18N  */

	build_upper_buffer (pstr);

    }

  else

    {

#ifdef RE_ENABLE_I18N

      if (dfa->mb_cur_max > 1)

	build_wcs_buffer (pstr);

      else

#endif /* RE_ENABLE_I18N  */

	{

	  if (trans != NULL)

	    re_string_translate_buffer (pstr);

	  else

	    {

	      pstr->valid_len = pstr->bufs_len;

	      pstr->valid_raw_len = pstr->bufs_len;

	    }

	}

    }

  return REG_NOERROR;

}

/* Helper functions for re_string_allocate, and re_string_construct.  */

static reg_errcode_t

__attribute_warn_unused_result__

re_string_realloc_buffers (re_string_t *pstr, Idx new_buf_len)

{

#ifdef RE_ENABLE_I18N

  if (pstr->mb_cur_max > 1)

    {

      wint_t *new_wcs;

      /* Avoid overflow in realloc.  */

      const size_t max_object_size = MAX (sizeof (wint_t), sizeof (Idx));

      if (BE (MIN (IDX_MAX, SIZE_MAX / max_object_size) < new_buf_len, 0))

	return REG_ESPACE;

      new_wcs = re_realloc (pstr->wcs, wint_t, new_buf_len);

      if (BE (new_wcs == NULL, 0))

	return REG_ESPACE;

      pstr->wcs = new_wcs;

      if (pstr->offsets != NULL)

	{

	  Idx *new_offsets = re_realloc (pstr->offsets, Idx, new_buf_len);

	  if (BE (new_offsets == NULL, 0))

	    return REG_ESPACE;

	  pstr->offsets = new_offsets;

	}

    }

#endif /* RE_ENABLE_I18N  */

  if (pstr->mbs_allocated)

    {

      unsigned char *new_mbs = re_realloc (pstr->mbs, unsigned char,

					   new_buf_len);

      if (BE (new_mbs == NULL, 0))

	return REG_ESPACE;

      pstr->mbs = new_mbs;

    }

  pstr->bufs_len = new_buf_len;

  return REG_NOERROR;

}

static void

re_string_construct_common (const char *str, Idx len, re_string_t *pstr,

			    RE_TRANSLATE_TYPE trans, bool icase,

			    const re_dfa_t *dfa)

{

  pstr->raw_mbs = (const unsigned char *) str;

  pstr->len = len;

  pstr->raw_len = len;

  pstr->trans = trans;

  pstr->icase = icase;

  pstr->mbs_allocated = (trans != NULL || icase);

  pstr->mb_cur_max = dfa->mb_cur_max;

  pstr->is_utf8 = dfa->is_utf8;

  pstr->map_notascii = dfa->map_notascii;

  pstr->stop = pstr->len;

  pstr->raw_stop = pstr->stop;

}

#ifdef RE_ENABLE_I18N

/* Build wide character buffer PSTR->WCS.

   If the byte sequence of the string are:

     <mb1>(0), <mb1>(1), <mb2>(0), <mb2>(1), <sb3>

   Then wide character buffer will be:

     <wc1>   , WEOF    , <wc2>   , WEOF    , <wc3>

   We use WEOF for padding, they indicate that the position isn't

   a first byte of a multibyte character.

   Note that this function assumes PSTR->VALID_LEN elements are already

   built and starts from PSTR->VALID_LEN.  */

static void

build_wcs_buffer (re_string_t *pstr)

{

#ifdef _LIBC

  unsigned char buf[MB_LEN_MAX];

  assert (MB_LEN_MAX >= pstr->mb_cur_max);

#else

  unsigned char buf[64];

#endif

  mbstate_t prev_st;

  Idx byte_idx, end_idx, remain_len;

  size_t mbclen;

  /* Build the buffers from pstr->valid_len to either pstr->len or

     pstr->bufs_len.  */

  end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len;

  for (byte_idx = pstr->valid_len; byte_idx < end_idx;)

    {

      wchar_t wc;

      const char *p;

      remain_len = end_idx - byte_idx;

      prev_st = pstr->cur_state;

      /* Apply the translation if we need.  */

      if (BE (pstr->trans != NULL, 0))

	{

	  int i, ch;

	  for (i = 0; i < pstr->mb_cur_max && i < remain_len; ++i)

	    {

	      ch = pstr->raw_mbs [pstr->raw_mbs_idx + byte_idx + i];

	      buf[i] = pstr->mbs[byte_idx + i] = pstr->trans[ch];

	    }

	  p = (const char *) buf;

	}

      else

	p = (const char *) pstr->raw_mbs + pstr->raw_mbs_idx + byte_idx;

      mbclen = __mbrtowc (&wc, p, remain_len, &pstr->cur_state);

      if (BE (mbclen == (size_t) -1 || mbclen == 0

	      || (mbclen == (size_t) -2 && pstr->bufs_len >= pstr->len), 0))

	{

	  /* We treat these cases as a singlebyte character.  */

	  mbclen = 1;

	  wc = (wchar_t) pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx];

	  if (BE (pstr->trans != NULL, 0))

	    wc = pstr->trans[wc];

	  pstr->cur_state = prev_st;

	}

      else if (BE (mbclen == (size_t) -2, 0))

	{

	  /* The buffer doesn't have enough space, finish to build.  */

	  pstr->cur_state = prev_st;

	  break;

	}

      /* Write wide character and padding.  */

      pstr->wcs[byte_idx++] = wc;

      /* Write paddings.  */

      for (remain_len = byte_idx + mbclen - 1; byte_idx < remain_len ;)

	pstr->wcs[byte_idx++] = WEOF;

    }

  pstr->valid_len = byte_idx;

  pstr->valid_raw_len = byte_idx;

}

/* Build wide character buffer PSTR->WCS like build_wcs_buffer,

   but for REG_ICASE.  */

static reg_errcode_t

__attribute_warn_unused_result__

build_wcs_upper_buffer (re_string_t *pstr)

{

  mbstate_t prev_st;

  Idx src_idx, byte_idx, end_idx, remain_len;

  size_t mbclen;

#ifdef _LIBC

  char buf[MB_LEN_MAX];

  assert (MB_LEN_MAX >= pstr->mb_cur_max);

#else

  char buf[64];

#endif

  byte_idx = pstr->valid_len;

  end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len;

  /* The following optimization assumes that ASCII characters can be

     mapped to wide characters with a simple cast.  */

  if (! pstr->map_notascii && pstr->trans == NULL && !pstr->offsets_needed)

    {

      while (byte_idx < end_idx)

	{

	  wchar_t wc;

	  if (isascii (pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx])

	      && mbsinit (&pstr->cur_state))

	    {

	      /* In case of a singlebyte character.  */

	      pstr->mbs[byte_idx]

		= toupper (pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx]);

	      /* The next step uses the assumption that wchar_t is encoded

		 ASCII-safe: all ASCII values can be converted like this.  */

	      pstr->wcs[byte_idx] = (wchar_t) pstr->mbs[byte_idx];

	      ++byte_idx;

	      continue;

	    }

	  remain_len = end_idx - byte_idx;

	  prev_st = pstr->cur_state;

	  mbclen = __mbrtowc (&wc,

			      ((const char *) pstr->raw_mbs + pstr->raw_mbs_idx

			       + byte_idx), remain_len, &pstr->cur_state);

	  if (BE (mbclen < (size_t) -2, 1))

	    {

	      wchar_t wcu = __towupper (wc);

	      if (wcu != wc)

		{

		  size_t mbcdlen;

		  mbcdlen = __wcrtomb (buf, wcu, &prev_st);

		  if (BE (mbclen == mbcdlen, 1))

		    memcpy (pstr->mbs + byte_idx, buf, mbclen);

		  else

		    {

		      src_idx = byte_idx;

		      goto offsets_needed;

		    }

		}

	      else

		memcpy (pstr->mbs + byte_idx,

			pstr->raw_mbs + pstr->raw_mbs_idx + byte_idx, mbclen);

	      pstr->wcs[byte_idx++] = wcu;

	      /* Write paddings.  */

	      for (remain_len = byte_idx + mbclen - 1; byte_idx < remain_len ;)

		pstr->wcs[byte_idx++] = WEOF;

	    }

	  else if (mbclen == (size_t) -1 || mbclen == 0

		   || (mbclen == (size_t) -2 && pstr->bufs_len >= pstr->len))

	    {

	      /* It is an invalid character, an incomplete character

		 at the end of the string, or '\0'.  Just use the byte.  */

	      int ch = pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx];

	      pstr->mbs[byte_idx] = ch;

	      /* And also cast it to wide char.  */

	      pstr->wcs[byte_idx++] = (wchar_t) ch;

	      if (BE (mbclen == (size_t) -1, 0))

		pstr->cur_state = prev_st;

	    }

	  else

	    {

	      /* The buffer doesn't have enough space, finish to build.  */

	      pstr->cur_state = prev_st;

	      break;

	    }

	}

      pstr->valid_len = byte_idx;

      pstr->valid_raw_len = byte_idx;

      return REG_NOERROR;

    }

  else

    for (src_idx = pstr->valid_raw_len; byte_idx < end_idx;)

      {

	wchar_t wc;

	const char *p;

      offsets_needed:

	remain_len = end_idx - byte_idx;

	prev_st = pstr->cur_state;

	if (BE (pstr->trans != NULL, 0))

	  {

	    int i, ch;

	    for (i = 0; i < pstr->mb_cur_max && i < remain_len; ++i)

	      {

		ch = pstr->raw_mbs [pstr->raw_mbs_idx + src_idx + i];

		buf[i] = pstr->trans[ch];

	      }

	    p = (const char *) buf;

	  }

	else

	  p = (const char *) pstr->raw_mbs + pstr->raw_mbs_idx + src_idx;

	mbclen = __mbrtowc (&wc, p, remain_len, &pstr->cur_state);

	if (BE (mbclen < (size_t) -2, 1))

	  {

	    wchar_t wcu = __towupper (wc);

	    if (wcu != wc)

	      {

		size_t mbcdlen;

		mbcdlen = __wcrtomb ((char *) buf, wcu, &prev_st);

		if (BE (mbclen == mbcdlen, 1))

		  memcpy (pstr->mbs + byte_idx, buf, mbclen);

		else if (mbcdlen != (size_t) -1)

		  {

		    size_t i;

		    if (byte_idx + mbcdlen > pstr->bufs_len)

		      {

			pstr->cur_state = prev_st;

			break;

		      }

		    if (pstr->offsets == NULL)

		      {

			pstr->offsets = re_malloc (Idx, pstr->bufs_len);

			if (pstr->offsets == NULL)

			  return REG_ESPACE;

		      }

		    if (!pstr->offsets_needed)

		      {

			for (i = 0; i < (size_t) byte_idx; ++i)

			  pstr->offsets[i] = i;

			pstr->offsets_needed = 1;

		      }

		    memcpy (pstr->mbs + byte_idx, buf, mbcdlen);

		    pstr->wcs[byte_idx] = wcu;

		    pstr->offsets[byte_idx] = src_idx;

		    for (i = 1; i < mbcdlen; ++i)

		      {

			pstr->offsets[byte_idx + i]

			  = src_idx + (i < mbclen ? i : mbclen - 1);

			pstr->wcs[byte_idx + i] = WEOF;

		      }

		    pstr->len += mbcdlen - mbclen;

		    if (pstr->raw_stop > src_idx)

		      pstr->stop += mbcdlen - mbclen;

		    end_idx = (pstr->bufs_len > pstr->len)

			      ? pstr->len : pstr->bufs_len;

		    byte_idx += mbcdlen;

		    src_idx += mbclen;

		    continue;

		  }

		else

		  memcpy (pstr->mbs + byte_idx, p, mbclen);

	      }

	    else

	      memcpy (pstr->mbs + byte_idx, p, mbclen);

	    if (BE (pstr->offsets_needed != 0, 0))

	      {

		size_t i;

		for (i = 0; i < mbclen; ++i)

		  pstr->offsets[byte_idx + i] = src_idx + i;

	      }

	    src_idx += mbclen;

	    pstr->wcs[byte_idx++] = wcu;

	    /* Write paddings.  */

	    for (remain_len = byte_idx + mbclen - 1; byte_idx < remain_len ;)

	      pstr->wcs[byte_idx++] = WEOF;

	  }

	else if (mbclen == (size_t) -1 || mbclen == 0

		 || (mbclen == (size_t) -2 && pstr->bufs_len >= pstr->len))

	  {

	    /* It is an invalid character or '\0'.  Just use the byte.  */

	    int ch = pstr->raw_mbs[pstr->raw_mbs_idx + src_idx];

	    if (BE (pstr->trans != NULL, 0))

	      ch = pstr->trans [ch];

	    pstr->mbs[byte_idx] = ch;

	    if (BE (pstr->offsets_needed != 0, 0))

	      pstr->offsets[byte_idx] = src_idx;

	    ++src_idx;

	    /* And also cast it to wide char.  */

	    pstr->wcs[byte_idx++] = (wchar_t) ch;

	    if (BE (mbclen == (size_t) -1, 0))

	      pstr->cur_state = prev_st;

	  }

	else

	  {

	    /* The buffer doesn't have enough space, finish to build.  */

	    pstr->cur_state = prev_st;

	    break;

	  }

      }

  pstr->valid_len = byte_idx;

  pstr->valid_raw_len = src_idx;

  return REG_NOERROR;

}

/* Skip characters until the index becomes greater than NEW_RAW_IDX.

   Return the index.  */

static Idx

re_string_skip_chars (re_string_t *pstr, Idx new_raw_idx, wint_t *last_wc)

{

  mbstate_t prev_st;

  Idx rawbuf_idx;

  size_t mbclen;

  wint_t wc = WEOF;

  /* Skip the characters which are not necessary to check.  */

  for (rawbuf_idx = pstr->raw_mbs_idx + pstr->valid_raw_len;

       rawbuf_idx < new_raw_idx;)

    {

      wchar_t wc2;

      Idx remain_len = pstr->raw_len - rawbuf_idx;

      prev_st = pstr->cur_state;

      mbclen = __mbrtowc (&wc2, (const char *) pstr->raw_mbs + rawbuf_idx,

			  remain_len, &pstr->cur_state);

      if (BE (mbclen == (size_t) -2 || mbclen == (size_t) -1 || mbclen == 0, 0))

	{

	  /* We treat these cases as a single byte character.  */

	  if (mbclen == 0 || remain_len == 0)

	    wc = L'\0';

	  else

	    wc = *(unsigned char *) (pstr->raw_mbs + rawbuf_idx);

	  mbclen = 1;

	  pstr->cur_state = prev_st;

	}

      else

	wc = wc2;

      /* Then proceed the next character.  */

      rawbuf_idx += mbclen;

    }

  *last_wc = wc;

  return rawbuf_idx;

}

#endif /* RE_ENABLE_I18N  */

/* Build the buffer PSTR->MBS, and apply the translation if we need.

   This function is used in case of REG_ICASE.  */

static void

build_upper_buffer (re_string_t *pstr)

{

  Idx char_idx, end_idx;

  end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len;

  for (char_idx = pstr->valid_len; char_idx < end_idx; ++char_idx)

    {

      int ch = pstr->raw_mbs[pstr->raw_mbs_idx + char_idx];

      if (BE (pstr->trans != NULL, 0))

	ch = pstr->trans[ch];

      pstr->mbs[char_idx] = toupper (ch);

    }

  pstr->valid_len = char_idx;

  pstr->valid_raw_len = char_idx;

}

/* Apply TRANS to the buffer in PSTR.  */

static void

re_string_translate_buffer (re_string_t *pstr)

{

  Idx buf_idx, end_idx;

  end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len;

  for (buf_idx = pstr->valid_len; buf_idx < end_idx; ++buf_idx)

    {

      int ch = pstr->raw_mbs[pstr->raw_mbs_idx + buf_idx];

      pstr->mbs[buf_idx] = pstr->trans[ch];

    }

  pstr->valid_len = buf_idx;

  pstr->valid_raw_len = buf_idx;

}

/* This function re-construct the buffers.

   Concretely, convert to wide character in case of pstr->mb_cur_max > 1,

   convert to upper case in case of REG_ICASE, apply translation.  */

static reg_errcode_t

__attribute_warn_unused_result__

re_string_reconstruct (re_string_t *pstr, Idx idx, int eflags)

{

  Idx offset;

  if (BE (pstr->raw_mbs_idx <= idx, 0))

    offset = idx - pstr->raw_mbs_idx;

  else

    {

      /* Reset buffer.  */

#ifdef RE_ENABLE_I18N

      if (pstr->mb_cur_max > 1)

	memset (&pstr->cur_state, '\0', sizeof (mbstate_t));

#endif /* RE_ENABLE_I18N */

      pstr->len = pstr->raw_len;

      pstr->stop = pstr->raw_stop;

      pstr->valid_len = 0;

      pstr->raw_mbs_idx = 0;

      pstr->valid_raw_len = 0;

      pstr->offsets_needed = 0;

      pstr->tip_context = ((eflags & REG_NOTBOL) ? CONTEXT_BEGBUF

			   : CONTEXT_NEWLINE | CONTEXT_BEGBUF);

      if (!pstr->mbs_allocated)

	pstr->mbs = (unsigned char *) pstr->raw_mbs;

      offset = idx;

    }

  if (BE (offset != 0, 1))

    {

      /* Should the already checked characters be kept?  */

      if (BE (offset < pstr->valid_raw_len, 1))

	{

	  /* Yes, move them to the front of the buffer.  */

#ifdef RE_ENABLE_I18N

	  if (BE (pstr->offsets_needed, 0))

	    {

	      Idx low = 0, high = pstr->valid_len, mid;

	      do

		{

		  mid = (high + low) / 2;

		  if (pstr->offsets[mid] > offset)

		    high = mid;

		  else if (pstr->offsets[mid] < offset)

		    low = mid + 1;

		  else

		    break;

		}

	      while (low < high);

	      if (pstr->offsets[mid] < offset)

		++mid;

	      pstr->tip_context = re_string_context_at (pstr, mid - 1,

							eflags);

	      /* This can be quite complicated, so handle specially

		 only the common and easy case where the character with

		 different length representation of lower and upper

		 case is present at or after offset.  */

	      if (pstr->valid_len > offset

		  && mid == offset && pstr->offsets[mid] == offset)

		{

		  memmove (pstr->wcs, pstr->wcs + offset,

			   (pstr->valid_len - offset) * sizeof (wint_t));

		  memmove (pstr->mbs, pstr->mbs + offset, pstr->valid_len - offset);

		  pstr->valid_len -= offset;

		  pstr->valid_raw_len -= offset;

		  for (low = 0; low < pstr->valid_len; low++)

		    pstr->offsets[low] = pstr->offsets[low + offset] - offset;

		}

	      else

		{

		  /* Otherwise, just find out how long the partial multibyte

		     character at offset is and fill it with WEOF/255.  */

		  pstr->len = pstr->raw_len - idx + offset;

		  pstr->stop = pstr->raw_stop - idx + offset;

		  pstr->offsets_needed = 0;

		  while (mid > 0 && pstr->offsets[mid - 1] == offset)

		    --mid;

		  while (mid < pstr->valid_len)

		    if (pstr->wcs[mid] != WEOF)

		      break;

		    else

		      ++mid;

		  if (mid == pstr->valid_len)

		    pstr->valid_len = 0;

		  else

		    {

		      pstr->valid_len = pstr->offsets[mid] - offset;

		      if (pstr->valid_len)

			{

			  for (low = 0; low < pstr->valid_len; ++low)

			    pstr->wcs[low] = WEOF;

			  memset (pstr->mbs, 255, pstr->valid_len);

			}

		    }

		  pstr->valid_raw_len = pstr->valid_len;

		}

	    }

	  else

#endif

	    {

	      pstr->tip_context = re_string_context_at (pstr, offset - 1,

							eflags);

#ifdef RE_ENABLE_I18N

	      if (pstr->mb_cur_max > 1)

		memmove (pstr->wcs, pstr->wcs + offset,

			 (pstr->valid_len - offset) * sizeof (wint_t));

#endif /* RE_ENABLE_I18N */

	      if (BE (pstr->mbs_allocated, 0))

		memmove (pstr->mbs, pstr->mbs + offset,

			 pstr->valid_len - offset);

	      pstr->valid_len -= offset;

	      pstr->valid_raw_len -= offset;

#if defined DEBUG && DEBUG

	      assert (pstr->valid_len > 0);

#endif

	    }

	}

      else

	{

#ifdef RE_ENABLE_I18N

	  /* No, skip all characters until IDX.  */

	  Idx prev_valid_len = pstr->valid_len;

	  if (BE (pstr->offsets_needed, 0))

	    {

	      pstr->len = pstr->raw_len - idx + offset;

	      pstr->stop = pstr->raw_stop - idx + offset;

	      pstr->offsets_needed = 0;

	    }

#endif

	  pstr->valid_len = 0;

#ifdef RE_ENABLE_I18N

	  if (pstr->mb_cur_max > 1)

	    {

	      Idx wcs_idx;

	      wint_t wc = WEOF;

	      if (pstr->is_utf8)

		{

		  const unsigned char *raw, *p, *end;

		  /* Special case UTF-8.  Multi-byte chars start with any

		     byte other than 0x80 - 0xbf.  */

		  raw = pstr->raw_mbs + pstr->raw_mbs_idx;

		  end = raw + (offset - pstr->mb_cur_max);

		  if (end < pstr->raw_mbs)

		    end = pstr->raw_mbs;

		  p = raw + offset - 1;

#ifdef _LIBC

		  /* We know the wchar_t encoding is UCS4, so for the simple

		     case, ASCII characters, skip the conversion step.  */

		  if (isascii (*p) && BE (pstr->trans == NULL, 1))

		    {

		      memset (&pstr->cur_state, '\0', sizeof (mbstate_t));

		      /* pstr->valid_len = 0; */

		      wc = (wchar_t) *p;

		    }

		  else

#endif

		    for (; p >= end; --p)

		      if ((*p & 0xc0) != 0x80)

			{

			  mbstate_t cur_state;

			  wchar_t wc2;

			  Idx mlen = raw + pstr->len - p;

			  unsigned char buf[6];

			  size_t mbclen;

			  const unsigned char *pp = p;

			  if (BE (pstr->trans != NULL, 0))

			    {

			      int i = mlen < 6 ? mlen : 6;

			      while (--i >= 0)

				buf[i] = pstr->trans[p[i]];

			      pp = buf;

			    }

			  /* XXX Don't use mbrtowc, we know which conversion

			     to use (UTF-8 -> UCS4).  */

			  memset (&cur_state, 0, sizeof (cur_state));

			  mbclen = __mbrtowc (&wc2, (const char *) pp, mlen,

					      &cur_state);

			  if (raw + offset - p <= mbclen

			      && mbclen < (size_t) -2)

			    {

			      memset (&pstr->cur_state, '\0',

				      sizeof (mbstate_t));

			      pstr->valid_len = mbclen - (raw + offset - p);

			      wc = wc2;

			    }

			  break;

			}

		}

	      if (wc == WEOF)

		pstr->valid_len = re_string_skip_chars (pstr, idx, &wc) - idx;

	      if (wc == WEOF)

		pstr->tip_context

		  = re_string_context_at (pstr, prev_valid_len - 1, eflags);

	      else

		pstr->tip_context = ((BE (pstr->word_ops_used != 0, 0)

				      && IS_WIDE_WORD_CHAR (wc))

				     ? CONTEXT_WORD

				     : ((IS_WIDE_NEWLINE (wc)

					 && pstr->newline_anchor)

					? CONTEXT_NEWLINE : 0));

	      if (BE (pstr->valid_len, 0))

		{

		  for (wcs_idx = 0; wcs_idx < pstr->valid_len; ++wcs_idx)

		    pstr->wcs[wcs_idx] = WEOF;

		  if (pstr->mbs_allocated)

		    memset (pstr->mbs, 255, pstr->valid_len);

		}

	      pstr->valid_raw_len = pstr->valid_len;

	    }

	  else

#endif /* RE_ENABLE_I18N */

	    {

	      int c = pstr->raw_mbs[pstr->raw_mbs_idx + offset - 1];

	      pstr->valid_raw_len = 0;

	      if (pstr->trans)

		c = pstr->trans[c];

	      pstr->tip_context = (bitset_contain (pstr->word_char, c)

				   ? CONTEXT_WORD

				   : ((IS_NEWLINE (c) && pstr->newline_anchor)

				      ? CONTEXT_NEWLINE : 0));

	    }

	}

      if (!BE (pstr->mbs_allocated, 0))

	pstr->mbs += offset;

    }

  pstr->raw_mbs_idx = idx;

  pstr->len -= offset;

  pstr->stop -= offset;

  /* Then build the buffers.  */

#ifdef RE_ENABLE_I18N

  if (pstr->mb_cur_max > 1)

    {

      if (pstr->icase)

	{

	  reg_errcode_t ret = build_wcs_upper_buffer (pstr);

	  if (BE (ret != REG_NOERROR, 0))

	    return ret;

	}

      else

	build_wcs_buffer (pstr);

    }

  else

#endif /* RE_ENABLE_I18N */

    if (BE (pstr->mbs_allocated, 0))

      {

	if (pstr->icase)

	  build_upper_buffer (pstr);

	else if (pstr->trans != NULL)

	  re_string_translate_buffer (pstr);

      }

    else

      pstr->valid_len = pstr->len;

  pstr->cur_idx = 0;

  return REG_NOERROR;

}

static unsigned char

__attribute__ ((pure))

re_string_peek_byte_case (const re_string_t *pstr, Idx idx)

{

  int ch;

  Idx off;

  /* Handle the common (easiest) cases first.  */

  if (BE (!pstr->mbs_allocated, 1))

    return re_string_peek_byte (pstr, idx);

#ifdef RE_ENABLE_I18N

  if (pstr->mb_cur_max > 1

      && ! re_string_is_single_byte_char (pstr, pstr->cur_idx + idx))

    return re_string_peek_byte (pstr, idx);

#endif

  off = pstr->cur_idx + idx;

#ifdef RE_ENABLE_I18N

  if (pstr->offsets_needed)

    off = pstr->offsets[off];

#endif

  ch = pstr->raw_mbs[pstr->raw_mbs_idx + off];

#ifdef RE_ENABLE_I18N

  /* Ensure that e.g. for tr_TR.UTF-8 BACKSLASH DOTLESS SMALL LETTER I

     this function returns CAPITAL LETTER I instead of first byte of

     DOTLESS SMALL LETTER I.  The latter would confuse the parser,

     since peek_byte_case doesn't advance cur_idx in any way.  */

  if (pstr->offsets_needed && !isascii (ch))

    return re_string_peek_byte (pstr, idx);

#endif

  return ch;

}

static unsigned char

re_string_fetch_byte_case (re_string_t *pstr)

{

  if (BE (!pstr->mbs_allocated, 1))

    return re_string_fetch_byte (pstr);

#ifdef RE_ENABLE_I18N

  if (pstr->offsets_needed)