(re_dfa_add_node): Remove the substitutions which became useless.
[kopensolaris-gnu/glibc.git] / posix / regex_internal.c
index 63bed42..69fb9a6 100644 (file)
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
-#include <wchar.h>
-#include <wctype.h>
+
+#if defined HAVE_WCHAR_H || defined _LIBC
+# include <wchar.h>
+#endif /* HAVE_WCHAR_H || _LIBC */
+#if defined HAVE_WCTYPE_H || defined _LIBC
+# include <wctype.h>
+#endif /* HAVE_WCTYPE_H || _LIBC */
 
 #ifdef _LIBC
 # ifndef _RE_DEFINE_LOCALE_FUNCTIONS
@@ -41,7 +46,8 @@
 # include <libintl.h>
 # ifdef _LIBC
 #  undef gettext
-#  define gettext(msgid) __dcgettext ("libc", msgid, LC_MESSAGES)
+#  define gettext(msgid) \
+  INTUSE(__dcgettext) (_libc_intl_domainname_internal, msgid, LC_MESSAGES)
 # endif
 #else
 # define gettext(msgid) (msgid)
 #include "regex.h"
 #include "regex_internal.h"
 
-static void re_string_construct_common (const unsigned char *str,
-                                        int len, re_string_t *pstr);
+static void re_string_construct_common (const char *str, int len,
+                                        re_string_t *pstr,
+                                        RE_TRANSLATE_TYPE trans, int icase);
 #ifdef RE_ENABLE_I18N
-static reg_errcode_t build_wcs_buffer (re_string_t *pstr);
-static reg_errcode_t build_wcs_upper_buffer (re_string_t *pstr);
+static int re_string_skip_chars (re_string_t *pstr, int new_raw_idx);
 #endif /* RE_ENABLE_I18N */
-static reg_errcode_t build_upper_buffer (re_string_t *pstr);
-static reg_errcode_t re_string_translate_buffer (re_string_t *pstr,
-                                                RE_TRANSLATE_TYPE trans);
 static re_dfastate_t *create_newstate_common (re_dfa_t *dfa,
                                               const re_node_set *nodes,
                                               unsigned int hash);
+static reg_errcode_t register_state (re_dfa_t *dfa, re_dfastate_t *newstate,
+                                     unsigned int hash);
 static re_dfastate_t *create_ci_newstate (re_dfa_t *dfa,
                                           const re_node_set *nodes,
                                           unsigned int hash);
@@ -80,277 +85,424 @@ static unsigned int inline calc_state_hash (const re_node_set *nodes,
 \f
 /* Functions for string operation.  */
 
-/* Construct string object.  */
+/* This function allocate the buffers.  It is necessary to call
+   re_string_reconstruct before using the object.  */
+
 static reg_errcode_t
-re_string_construct (pstr, str, len, trans)
+re_string_allocate (pstr, str, len, init_len, trans, icase)
      re_string_t *pstr;
-     const unsigned char *str;
-     int len;
+     const char *str;
+     int len, init_len, icase;
      RE_TRANSLATE_TYPE trans;
 {
   reg_errcode_t ret;
-  re_string_construct_common (str, len, pstr);
-#ifdef RE_ENABLE_I18N
-  if (MB_CUR_MAX >1 && pstr->len > 0)
+  int init_buf_len = (len + 1 < init_len) ? len + 1: init_len;
+  re_string_construct_common (str, len, pstr, trans, icase);
+  pstr->stop = pstr->len;
+
+  ret = re_string_realloc_buffers (pstr, init_buf_len);
+  if (BE (ret != REG_NOERROR, 0))
+    return ret;
+
+  pstr->mbs_case = (MBS_CASE_ALLOCATED (pstr) ? pstr->mbs_case
+                    : (unsigned char *) str);
+  pstr->mbs = MBS_ALLOCATED (pstr) ? pstr->mbs : pstr->mbs_case;
+  pstr->valid_len = (MBS_CASE_ALLOCATED (pstr) || MBS_ALLOCATED (pstr)
+                     || MB_CUR_MAX > 1) ? pstr->valid_len : len;
+  return REG_NOERROR;
+}
+
+/* This function allocate the buffers, and initialize them.  */
+
+static reg_errcode_t
+re_string_construct (pstr, str, len, trans, icase)
+     re_string_t *pstr;
+     const char *str;
+     int len, icase;
+     RE_TRANSLATE_TYPE trans;
+{
+  reg_errcode_t ret;
+  re_string_construct_common (str, len, pstr, trans, icase);
+  pstr->stop = pstr->len;
+  /* Set 0 so that this function can initialize whole buffers.  */
+  pstr->valid_len = 0;
+
+  if (len > 0)
     {
-      ret = build_wcs_buffer (pstr);
-      if (ret != REG_NOERROR)
+      ret = re_string_realloc_buffers (pstr, len + 1);
+      if (BE (ret != REG_NOERROR, 0))
         return ret;
     }
+  pstr->mbs_case = (MBS_CASE_ALLOCATED (pstr) ? pstr->mbs_case
+                    : (unsigned char *) str);
+  pstr->mbs = MBS_ALLOCATED (pstr) ? pstr->mbs : pstr->mbs_case;
+
+  if (icase)
+    {
+#ifdef RE_ENABLE_I18N
+      if (MB_CUR_MAX > 1)
+        build_wcs_upper_buffer (pstr);
+      else
 #endif /* RE_ENABLE_I18N  */
-  pstr->mbs_case = str;
-  if (trans != NULL)
+        build_upper_buffer (pstr);
+    }
+  else
     {
-      ret = re_string_translate_buffer (pstr, trans);
-      if (ret != REG_NOERROR)
-        return ret;
+#ifdef RE_ENABLE_I18N
+      if (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 = len;
+        }
     }
+
+  /* Initialized whole buffers, then valid_len == bufs_len.  */
+  pstr->valid_len = pstr->bufs_len;
   return REG_NOERROR;
 }
 
-/* Construct string object. We use this function instead of
-   re_string_construct for case insensitive mode.  */
+/* Helper functions for re_string_allocate, and re_string_construct.  */
 
 static reg_errcode_t
-re_string_construct_toupper (pstr, str, len, trans)
+re_string_realloc_buffers (pstr, new_buf_len)
      re_string_t *pstr;
-     const unsigned char *str;
-     int len;
-     RE_TRANSLATE_TYPE trans;
+     int new_buf_len;
 {
-  reg_errcode_t ret;
-  /* Set case sensitive buffer.  */
-  re_string_construct_common (str, len, pstr);
 #ifdef RE_ENABLE_I18N
-  if (MB_CUR_MAX >1)
+  if (MB_CUR_MAX > 1)
     {
-      if (pstr->len > 0)
-        {
-          ret = build_wcs_upper_buffer (pstr);
-          if (ret != REG_NOERROR)
-            return ret;
-        }
+      pstr->wcs = re_realloc (pstr->wcs, wint_t, new_buf_len);
+      if (BE (pstr->wcs == NULL, 0))
+        return REG_ESPACE;
     }
-  else
 #endif /* RE_ENABLE_I18N  */
+  if (MBS_ALLOCATED (pstr))
     {
-      if (pstr->len > 0)
-        {
-          ret = build_upper_buffer (pstr);
-          if (ret != REG_NOERROR)
-            return ret;
-        }
+      pstr->mbs = re_realloc (pstr->mbs, unsigned char, new_buf_len);
+      if (BE (pstr->mbs == NULL, 0))
+        return REG_ESPACE;
     }
-  pstr->mbs_case = str;
-  if (trans != NULL)
+  if (MBS_CASE_ALLOCATED (pstr))
     {
-      ret = re_string_translate_buffer (pstr, trans);
-      if (ret != REG_NOERROR)
-        return ret;
+      pstr->mbs_case = re_realloc (pstr->mbs_case, unsigned char, new_buf_len);
+      if (BE (pstr->mbs_case == NULL, 0))
+        return REG_ESPACE;
+      if (!MBS_ALLOCATED (pstr))
+        pstr->mbs = pstr->mbs_case;
     }
+  pstr->bufs_len = new_buf_len;
   return REG_NOERROR;
 }
 
-/* Helper functions for re_string_construct_*.  */
+
 static void
-re_string_construct_common (str, len, pstr)
-     const unsigned char *str;
+re_string_construct_common (str, len, pstr, trans, icase)
+     const char *str;
      int len;
      re_string_t *pstr;
+     RE_TRANSLATE_TYPE trans;
+     int icase;
 {
-  pstr->mbs = str;
-  pstr->cur_idx = 0;
+  memset (pstr, '\0', sizeof (re_string_t));
+  pstr->raw_mbs = (const unsigned char *) str;
   pstr->len = len;
-#ifdef RE_ENABLE_I18N
-  pstr->wcs = NULL;
-#endif
-  pstr->mbs_case = NULL;
-  pstr->mbs_alloc = 0;
-  pstr->mbs_case_alloc = 0;
+  pstr->trans = trans;
+  pstr->icase = icase ? 1 : 0;
 }
 
 #ifdef RE_ENABLE_I18N
 
-/* Build wide character buffer for `pstr'.
+/* 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.  */
+   a first byte of a multibyte character.
 
-static reg_errcode_t
+   Note that this function assumes PSTR->VALID_LEN elements are already
+   built and starts from PSTR->VALID_LEN.  */
+
+static void
 build_wcs_buffer (pstr)
      re_string_t *pstr;
 {
-  mbstate_t state, prev_st;
-  wchar_t wc;
-  int char_idx, char_len, mbclen;
-
-  pstr->wcs = re_malloc (wchar_t, pstr->len + 1);
-  if (pstr->wcs == NULL)
-    return REG_ESPACE;
-
-  memset (&state, '\0', sizeof (mbstate_t));
-  char_len = pstr->len;
-  for (char_idx = 0; char_idx < char_len ;)
+  mbstate_t prev_st;
+  int byte_idx, end_idx, mbclen, remain_len;
+  /* 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;)
     {
-      int next_idx, remain_len = char_len - char_idx;
-      prev_st = state;
-      mbclen = mbrtowc (&wc, pstr->mbs + char_idx, remain_len, &state);
-      if (mbclen == (size_t) -2 || mbclen == (size_t) -1 || mbclen == 0)
-        /* We treat these cases as a singlebyte character.  */
+      wchar_t wc;
+      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, 0))
         {
+          /* The buffer doesn't have enough space, finish to build.  */
+          pstr->cur_state = prev_st;
+          break;
+        }
+      else if (BE (mbclen == (size_t) -1 || mbclen == 0, 0))
+        {
+          /* We treat these cases as a singlebyte character.  */
           mbclen = 1;
-          wc = (wchar_t) pstr->mbs[char_idx++];
-          state = prev_st;
+          wc = (wchar_t) pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx];
+          pstr->cur_state = prev_st;
+        }
+
+      /* Apply the translateion if we need.  */
+      if (pstr->trans != NULL && mbclen == 1)
+        {
+          int ch = pstr->trans[pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx]];
+          pstr->mbs_case[byte_idx] = ch;
         }
       /* Write wide character and padding.  */
-      pstr->wcs[char_idx++] = wc;
-      for (next_idx = char_idx + mbclen - 1; char_idx < next_idx ;)
-        pstr->wcs[char_idx++] = WEOF;
+      pstr->wcs[byte_idx++] = wc;
+      /* Write paddings.  */
+      for (remain_len = byte_idx + mbclen - 1; byte_idx < remain_len ;)
+        pstr->wcs[byte_idx++] = WEOF;
     }
-  return REG_NOERROR;
+  pstr->valid_len = byte_idx;
 }
 
-static reg_errcode_t
+/* Build wide character buffer PSTR->WCS like build_wcs_buffer,
+   but for REG_ICASE.  */
+
+static void
 build_wcs_upper_buffer (pstr)
      re_string_t *pstr;
 {
-  mbstate_t state, prev_st;
-  wchar_t wc;
-  unsigned char *mbs_upper;
-  int char_idx, char_len, mbclen;
-
-  pstr->wcs = re_malloc (wchar_t, pstr->len + 1);
-  mbs_upper = re_malloc (unsigned char, pstr->len + 1);
-  if (pstr->wcs == NULL || mbs_upper == NULL)
-    {
-      pstr->wcs = NULL;
-      return REG_ESPACE;
-    }
-
-  memset (&state, '\0', sizeof (mbstate_t));
-  char_len = pstr->len;
-  for (char_idx = 0 ; char_idx < char_len ; char_idx += mbclen)
+  mbstate_t prev_st;
+  int byte_idx, end_idx, mbclen, remain_len;
+  /* 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;)
     {
-      int byte_idx, remain_len = char_len - char_idx;
-      prev_st = state;
-      mbclen = mbrtowc (&wc, pstr->mbs + char_idx, remain_len, &state);
-      if (mbclen == 1)
+      wchar_t wc;
+      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, 0))
         {
-          pstr->wcs[char_idx] = wc;
-          if (islower (pstr->mbs[char_idx]))
-            mbs_upper[char_idx] = toupper (pstr->mbs[char_idx]);
-          else
-            mbs_upper[char_idx] = pstr->mbs[char_idx];
+          /* The buffer doesn't have enough space, finish to build.  */
+          pstr->cur_state = prev_st;
+          break;
         }
-      else if (mbclen == (size_t) -2 || mbclen == (size_t) -1 || mbclen == 0)
-        /* We treat these cases as a singlebyte character.  */
+      else if (mbclen == 1 || mbclen == (size_t) -1 || mbclen == 0)
         {
-          mbclen = 1;
-          pstr->wcs[char_idx] = (wchar_t) pstr->mbs[char_idx];
-          mbs_upper[char_idx] = pstr->mbs[char_idx];
-          state = prev_st;
+          /* In case of a singlebyte character.  */
+          int ch = pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx];
+          /* Apply the translateion if we need.  */
+          if (pstr->trans != NULL && mbclen == 1)
+            {
+              ch = pstr->trans[ch];
+              pstr->mbs_case[byte_idx] = ch;
+            }
+          pstr->wcs[byte_idx] = iswlower (wc) ? toupper (wc) : wc;
+          pstr->mbs[byte_idx++] = islower (ch) ? toupper (ch) : ch;
+          if (BE (mbclen == (size_t) -1, 0))
+            pstr->cur_state = prev_st;
         }
       else /* mbclen > 1 */
         {
-          pstr->wcs[char_idx] = wc;
           if (iswlower (wc))
-            wcrtomb (mbs_upper + char_idx, towupper (wc), &prev_st);
+            wcrtomb ((char *) pstr->mbs + byte_idx, towupper (wc), &prev_st);
           else
-            memcpy (mbs_upper + char_idx, pstr->mbs + char_idx, mbclen);
-          for (byte_idx = 1 ; byte_idx < mbclen ; byte_idx++)
-            pstr->wcs[char_idx + byte_idx] = WEOF;
+            memcpy (pstr->mbs + byte_idx,
+                    pstr->raw_mbs + pstr->raw_mbs_idx + byte_idx, mbclen);
+          pstr->wcs[byte_idx++] = iswlower (wc) ? toupper (wc) : wc;
+          /* Write paddings.  */
+          for (remain_len = byte_idx + mbclen - 1; byte_idx < remain_len ;)
+            pstr->wcs[byte_idx++] = WEOF;
         }
     }
-  pstr->mbs = mbs_upper;
-  pstr->mbs_alloc = 1;
-  return REG_NOERROR;
+  pstr->valid_len = byte_idx;
+}
+
+/* Skip characters until the index becomes greater than NEW_RAW_IDX.
+   Return the index.  */
+
+static int
+re_string_skip_chars (pstr, new_raw_idx)
+     re_string_t *pstr;
+     int new_raw_idx;
+{
+  mbstate_t prev_st;
+  int rawbuf_idx, mbclen;
+
+  /* Skip the characters which are not necessary to check.  */
+  for (rawbuf_idx = pstr->raw_mbs_idx + pstr->valid_len;
+       rawbuf_idx < new_raw_idx;)
+    {
+      int remain_len = pstr->len - rawbuf_idx;
+      prev_st = pstr->cur_state;
+      mbclen = mbrlen ((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 singlebyte character.  */
+          mbclen = 1;
+          pstr->cur_state = prev_st;
+        }
+      /* Then proceed the next character.  */
+      rawbuf_idx += mbclen;
+    }
+  return rawbuf_idx;
 }
 #endif /* RE_ENABLE_I18N  */
 
-static reg_errcode_t
+/* 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 (pstr)
      re_string_t *pstr;
 {
-  unsigned char *mbs_upper;
-  int char_idx, char_len;
-
-  mbs_upper = re_malloc (unsigned char, pstr->len + 1);
-  if (mbs_upper == NULL)
-    return REG_ESPACE;
+  int char_idx, end_idx;
+  end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len;
 
-  char_len = pstr->len;
-  for (char_idx = 0 ; char_idx < char_len ; char_idx ++)
+  for (char_idx = pstr->valid_len; char_idx < end_idx; ++char_idx)
     {
-      if (islower (pstr->mbs[char_idx]))
-        mbs_upper[char_idx] = toupper (pstr->mbs[char_idx]);
+      int ch = pstr->raw_mbs[pstr->raw_mbs_idx + char_idx];
+      if (pstr->trans != NULL)
+        {
+          ch =  pstr->trans[ch];
+          pstr->mbs_case[char_idx] = ch;
+        }
+      if (islower (ch))
+        pstr->mbs[char_idx] = toupper (ch);
       else
-        mbs_upper[char_idx] = pstr->mbs[char_idx];
+        pstr->mbs[char_idx] = ch;
     }
-  pstr->mbs = mbs_upper;
-  pstr->mbs_alloc = 1;
-  return REG_NOERROR;
+  pstr->valid_len = char_idx;
 }
 
-/* Apply TRANS to the buffer in PSTR.  We assume that wide char buffer
-   is already constructed if MB_CUR_MAX > 1.  */
+/* Apply TRANS to the buffer in PSTR.  */
 
-static reg_errcode_t
-re_string_translate_buffer (pstr, trans)
+static void
+re_string_translate_buffer (pstr)
      re_string_t *pstr;
-     RE_TRANSLATE_TYPE trans;
 {
-  int buf_idx;
-  unsigned char *transed_buf, *transed_case_buf;
-#ifdef DEBUG
-  assert (trans != NULL);
-#endif
-  if (pstr->mbs_alloc)
+  int 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)
     {
-      transed_buf = (unsigned char *) pstr->mbs;
-      transed_case_buf = re_malloc (unsigned char, pstr->len + 1);
-      if (transed_case_buf == NULL)
-        return REG_ESPACE;
-      pstr->mbs_case_alloc = 1;
+      int ch = pstr->raw_mbs[pstr->raw_mbs_idx + buf_idx];
+      pstr->mbs_case[buf_idx] = pstr->trans[ch];
     }
-  else
+
+  pstr->valid_len = buf_idx;
+}
+
+/* This function re-construct the buffers.
+   Concretely, convert to wide character in case of MB_CUR_MAX > 1,
+   convert to upper case in case of REG_ICASE, apply translation.  */
+
+static reg_errcode_t
+re_string_reconstruct (pstr, idx, eflags, newline)
+     re_string_t *pstr;
+     int idx, eflags, newline;
+{
+  int offset = idx - pstr->raw_mbs_idx;
+  if (offset < 0)
     {
-      transed_buf = re_malloc (unsigned char, pstr->len + 1);
-      if (transed_buf == NULL)
-        return REG_ESPACE;
-      transed_case_buf = NULL;
-      pstr->mbs_alloc = 1;
+      /* Reset buffer.  */
+#ifdef RE_ENABLE_I18N
+      if (MB_CUR_MAX > 1)
+        memset (&pstr->cur_state, '\0', sizeof (mbstate_t));
+#endif /* RE_ENABLE_I18N */
+      pstr->len += pstr->raw_mbs_idx;
+      pstr->stop += pstr->raw_mbs_idx;
+      pstr->valid_len = pstr->raw_mbs_idx = 0;
+      pstr->tip_context = ((eflags & REG_NOTBOL) ? CONTEXT_BEGBUF
+                           : CONTEXT_NEWLINE | CONTEXT_BEGBUF);
+      if (!MBS_CASE_ALLOCATED (pstr))
+        pstr->mbs_case = (unsigned char *) pstr->raw_mbs;
+      if (!MBS_ALLOCATED (pstr) && !MBS_CASE_ALLOCATED (pstr))
+        pstr->mbs = (unsigned char *) pstr->raw_mbs;
+      offset = idx;
     }
-  for (buf_idx = 0 ; buf_idx < pstr->len ; buf_idx++)
+
+  if (offset != 0)
     {
+      pstr->tip_context = re_string_context_at (pstr, offset - 1, eflags,
+                                                newline);
+      /* Are the characters which are already checked remain?  */
+      if (offset < pstr->valid_len)
+        {
+          /* Yes, move them to the front of the buffer.  */
 #ifdef RE_ENABLE_I18N
-      if (MB_CUR_MAX > 1 && !re_string_is_single_byte_char (pstr, buf_idx))
-        transed_buf[buf_idx] = pstr->mbs[buf_idx];
-      else
+          if (MB_CUR_MAX > 1)
+            memmove (pstr->wcs, pstr->wcs + offset,
+                     (pstr->valid_len - offset) * sizeof (wint_t));
+#endif /* RE_ENABLE_I18N */
+          if (MBS_ALLOCATED (pstr))
+            memmove (pstr->mbs, pstr->mbs + offset,
+                     pstr->valid_len - offset);
+          if (MBS_CASE_ALLOCATED (pstr))
+            memmove (pstr->mbs_case, pstr->mbs_case + offset,
+                     pstr->valid_len - offset);
+          pstr->valid_len -= offset;
+#if DEBUG
+          assert (pstr->valid_len > 0);
 #endif
-        transed_buf[buf_idx] = trans[pstr->mbs[buf_idx]];
-      if (transed_case_buf)
+        }
+      else
         {
+          /* No, skip all characters until IDX.  */
+          pstr->valid_len = 0;
 #ifdef RE_ENABLE_I18N
-         if (MB_CUR_MAX > 1 && !re_string_is_single_byte_char (pstr, buf_idx))
-            transed_case_buf[buf_idx] = pstr->mbs_case[buf_idx];
-          else
-#endif
-            transed_case_buf[buf_idx] = trans[pstr->mbs_case[buf_idx]];
+          if (MB_CUR_MAX > 1)
+            {
+              int wcs_idx;
+              pstr->valid_len = re_string_skip_chars (pstr, idx) - idx;
+              for (wcs_idx = 0; wcs_idx < pstr->valid_len; ++wcs_idx)
+                pstr->wcs[wcs_idx] = WEOF;
+            }
+#endif /* RE_ENABLE_I18N */
+        }
+      if (!MBS_CASE_ALLOCATED (pstr))
+        {
+          pstr->mbs_case += offset; 
+          /* In case of !MBS_ALLOCATED && !MBS_CASE_ALLOCATED.  */
+          if (!MBS_ALLOCATED (pstr))
+            pstr->mbs += offset; 
         }
     }
-  if (pstr->mbs_case_alloc == 1)
+  pstr->raw_mbs_idx = idx;
+  pstr->len -= offset;
+  pstr->stop -= offset;
+
+  /* Then build the buffers.  */
+#ifdef RE_ENABLE_I18N
+  if (MB_CUR_MAX > 1)
     {
-      pstr->mbs = transed_buf;
-      pstr->mbs_case = transed_case_buf;
+      if (pstr->icase)
+        build_wcs_upper_buffer (pstr);
+      else
+        build_wcs_buffer (pstr);
     }
   else
+#endif /* RE_ENABLE_I18N */
     {
-      pstr->mbs = transed_buf;
-      pstr->mbs_case = transed_buf;
+      if (pstr->icase)
+        build_upper_buffer (pstr);
+      else if (pstr->trans != NULL)
+        re_string_translate_buffer (pstr);
     }
+  pstr->cur_idx = 0;
+
   return REG_NOERROR;
 }
 
@@ -361,13 +513,14 @@ re_string_destruct (pstr)
 #ifdef RE_ENABLE_I18N
   re_free (pstr->wcs);
 #endif /* RE_ENABLE_I18N  */
-  if (pstr->mbs_alloc)
-    re_free ((void *) pstr->mbs);
-  if (pstr->mbs_case_alloc)
-    re_free ((void *) pstr->mbs_case);
+  if (MBS_ALLOCATED (pstr))
+    re_free (pstr->mbs);
+  if (MBS_CASE_ALLOCATED (pstr))
+    re_free (pstr->mbs_case);
 }
 
 /* Return the context at IDX in INPUT.  */
+
 static unsigned int
 re_string_context_at (input, idx, eflags, newline_anchor)
      const re_string_t *input;
@@ -376,17 +529,13 @@ re_string_context_at (input, idx, eflags, newline_anchor)
   int c;
   if (idx < 0 || idx == input->len)
     {
-      unsigned int context = 0;
       if (idx < 0)
-        context = CONTEXT_BEGBUF;
-      else if (idx == input->len)
-        context = CONTEXT_ENDBUF;
-
-      if ((idx < 0 && !(eflags & REG_NOTBOL))
-          || (idx == input->len && !(eflags & REG_NOTEOL)))
-        return CONTEXT_NEWLINE | context;
-      else
-        return context;
+        /* In this case, we use the value stored in input->tip_context,
+           since we can't know the character in input->mbs[-1] here.  */
+        return input->tip_context;
+      else /* (idx == input->len) */
+        return ((eflags & REG_NOTEOL) ? CONTEXT_ENDBUF
+                : CONTEXT_NEWLINE | CONTEXT_ENDBUF);
     }
   c = re_string_byte_at (input, idx);
   if (IS_WORD_CHAR (c))
@@ -404,7 +553,7 @@ re_node_set_alloc (set, size)
   set->alloc = size;
   set->nelem = 0;
   set->elems = re_malloc (int, size);
-  if (set->elems == NULL)
+  if (BE (set->elems == NULL, 0))
     return REG_ESPACE;
   return REG_NOERROR;
 }
@@ -417,7 +566,7 @@ re_node_set_init_1 (set, elem)
   set->alloc = 1;
   set->nelem = 1;
   set->elems = re_malloc (int, 1);
-  if (set->elems == NULL)
+  if (BE (set->elems == NULL, 0))
     return REG_ESPACE;
   set->elems[0] = elem;
   return REG_NOERROR;
@@ -430,7 +579,7 @@ re_node_set_init_2 (set, elem1, elem2)
 {
   set->alloc = 2;
   set->elems = re_malloc (int, 2);
-  if (set->elems == NULL)
+  if (BE (set->elems == NULL, 0))
     return REG_ESPACE;
   if (elem1 == elem2)
     {
@@ -464,7 +613,7 @@ re_node_set_init_copy (dest, src)
     {
       dest->alloc = dest->nelem;
       dest->elems = re_malloc (int, dest->alloc);
-      if (dest->elems == NULL)
+      if (BE (dest->elems == NULL, 0))
         return REG_ESPACE;
       memcpy (dest->elems, src->elems, src->nelem * sizeof (int));
     }
@@ -473,48 +622,9 @@ re_node_set_init_copy (dest, src)
   return REG_NOERROR;
 }
 
-static reg_errcode_t
-re_node_set_intersect (dest, src1, src2)
-     re_node_set *dest;
-     const re_node_set *src1, *src2;
-{
-  int i1, i2, id;
-  if (src1->nelem > 0 && src2->nelem > 0)
-    {
-      if (src1->nelem + src2->nelem > dest->alloc)
-        {
-          int *new_array;
-          if (dest->alloc == 0)
-            new_array = re_malloc (int, src1->nelem + src2->nelem);
-          else
-            new_array = re_realloc (dest->elems, int,
-                                    src1->nelem + src2->nelem);
-          dest->alloc = src1->nelem + src2->nelem;
-          if (new_array == NULL)
-            return REG_ESPACE;
-          dest->elems = new_array;
-        }
-    }
-  else
-    {
-      dest->nelem = 0;
-      return REG_NOERROR;
-    }
-
-  for (i1 = i2 = id = 0 ; i1 < src1->nelem && i2 < src2->nelem ;)
-    {
-      if (src1->elems[i1] > src2->elems[i2])
-        {
-          ++i2;
-          continue;
-        }
-      if (src1->elems[i1] == src2->elems[i2])
-        dest->elems[id++] = src2->elems[i2++];
-      ++i1;
-    }
-  dest->nelem = id;
-  return REG_NOERROR;
-}
+/* Calculate the intersection of the sets SRC1 and SRC2. And merge it to
+   DEST. Return value indicate the error code or REG_NOERROR if succeeded.
+   Note: We assume dest->elems is NULL, when dest->alloc is 0.  */
 
 static reg_errcode_t
 re_node_set_add_intersect (dest, src1, src2)
@@ -526,16 +636,10 @@ re_node_set_add_intersect (dest, src1, src2)
     {
       if (src1->nelem + src2->nelem + dest->nelem > dest->alloc)
         {
-          int *new_array;
-          if (dest->alloc == 0)
-            new_array = re_malloc (int, src1->nelem + src2->nelem);
-          else
-            new_array = re_realloc (dest->elems, int,
-                                    src1->nelem + src2->nelem + dest->nelem);
           dest->alloc = src1->nelem + src2->nelem + dest->nelem;
-          if (new_array == NULL)
+          dest->elems = re_realloc (dest->elems, int, dest->alloc);
+          if (BE (dest->elems == NULL, 0))
             return REG_ESPACE;
-          dest->elems = new_array;
         }
     }
   else
@@ -567,6 +671,9 @@ re_node_set_add_intersect (dest, src1, src2)
   return REG_NOERROR;
 }
 
+/* Calculate the union set of the sets SRC1 and SRC2. And store it to
+   DEST. Return value indicate the error code or REG_NOERROR if succeeded.  */
+
 static reg_errcode_t
 re_node_set_init_union (dest, src1, src2)
      re_node_set *dest;
@@ -577,7 +684,7 @@ re_node_set_init_union (dest, src1, src2)
     {
       dest->alloc = src1->nelem + src2->nelem;
       dest->elems = re_malloc (int, dest->alloc);
-      if (dest->elems == NULL)
+      if (BE (dest->elems == NULL, 0))
         return REG_ESPACE;
     }
   else
@@ -617,6 +724,9 @@ re_node_set_init_union (dest, src1, src2)
   return REG_NOERROR;
 }
 
+/* Calculate the union set of the sets DEST and SRC. And store it to
+   DEST. Return value indicate the error code or REG_NOERROR if succeeded.  */
+
 static reg_errcode_t
 re_node_set_merge (dest, src)
      re_node_set *dest;
@@ -625,15 +735,12 @@ re_node_set_merge (dest, src)
   int si, di;
   if (src == NULL || src->nelem == 0)
     return REG_NOERROR;
-  else if (dest == NULL)
-    {
-      dest = re_malloc (re_node_set, 1);
-      return re_node_set_init_copy (dest, src);
-    }
   if (dest->alloc < src->nelem + dest->nelem)
     {
       dest->alloc = 2 * (src->nelem + dest->alloc);
       dest->elems = re_realloc (dest->elems, int, dest->alloc);
+      if (BE (dest->elems == NULL, 0))
+        return REG_ESPACE;
     }
 
   for (si = 0, di = 0 ; si < src->nelem && di < dest->nelem ;)
@@ -698,7 +805,7 @@ re_node_set_insert (set, elem)
   /* In case of the set is empty.  */
   if (set->elems == NULL || set->alloc == 0)
     {
-      if (re_node_set_init_1 (set, elem) == REG_NOERROR)
+      if (BE (re_node_set_init_1 (set, elem) == REG_NOERROR, 1))
         return 1;
       else
         return -1;
@@ -722,7 +829,7 @@ re_node_set_insert (set, elem)
       int *new_array;
       set->alloc = set->alloc * 2;
       new_array = re_malloc (int, set->alloc);
-      if (new_array == NULL)
+      if (BE (new_array == NULL, 0))
         return -1;
       /* Copy the elements they are followed by the new element.  */
       if (idx > 0)
@@ -731,6 +838,7 @@ re_node_set_insert (set, elem)
       if (set->nelem - idx > 0)
         memcpy (new_array + idx + 1, set->elems + idx,
                sizeof (int) * (set->nelem - idx));
+      re_free (set->elems);
       set->elems = new_array;
     }
   else
@@ -762,7 +870,7 @@ re_node_set_compare (set1, set2)
   return 1;
 }
 
-/* Return 1 if SET contains the element ELEM, return 0 otherwise.  */
+/* Return (idx + 1) if SET contains the element ELEM, return 0 otherwise.  */
 
 static int
 re_node_set_contains (set, elem)
@@ -784,7 +892,7 @@ re_node_set_contains (set, elem)
       else
         right = mid;
     }
-  return set->elems[idx] == elem;
+  return set->elems[idx] == elem ? idx + 1 : 0;
 }
 
 static void
@@ -815,26 +923,24 @@ re_dfa_add_node (dfa, token, mode)
       re_token_t *new_array;
       dfa->nodes_alloc *= 2;
       new_array = re_realloc (dfa->nodes, re_token_t, dfa->nodes_alloc);
-      if (new_array == NULL)
+      if (BE (new_array == NULL, 0))
         return -1;
       else
         dfa->nodes = new_array;
       if (mode)
         {
-          int *new_firsts, *new_nexts;
+          int *new_nexts;
           re_node_set *new_edests, *new_eclosures, *new_inveclosures;
 
-          new_firsts = re_realloc (dfa->firsts, int, dfa->nodes_alloc);
           new_nexts = re_realloc (dfa->nexts, int, dfa->nodes_alloc);
           new_edests = re_realloc (dfa->edests, re_node_set, dfa->nodes_alloc);
           new_eclosures = re_realloc (dfa->eclosures, re_node_set,
                                       dfa->nodes_alloc);
           new_inveclosures = re_realloc (dfa->inveclosures, re_node_set,
                                          dfa->nodes_alloc);
-          if (new_firsts == NULL || new_nexts == NULL || new_edests == NULL
-              || new_eclosures == NULL || new_inveclosures == NULL)
+          if (BE (new_nexts == NULL || new_edests == NULL
+                  || new_eclosures == NULL || new_inveclosures == NULL, 0))
             return -1;
-          dfa->firsts = new_firsts;
           dfa->nexts = new_nexts;
           dfa->edests = new_edests;
           dfa->eclosures = new_eclosures;
@@ -843,6 +949,7 @@ re_dfa_add_node (dfa, token, mode)
     }
   dfa->nodes[dfa->nodes_len] = token;
   dfa->nodes[dfa->nodes_len].duplicated = 0;
+  dfa->nodes[dfa->nodes_len].constraint = 0;
   return dfa->nodes_len++;
 }
 
@@ -860,83 +967,103 @@ calc_state_hash (nodes, context)
 
 /* Search for the state whose node_set is equivalent to NODES.
    Return the pointer to the state, if we found it in the DFA.
-   Otherwise create the new one and return it.  */
-
-static re_dfastate_t *
-re_acquire_state (dfa, nodes)
+   Otherwise create the new one and return it.  In case of an error
+   return NULL and set the error code in ERR.
+   Note: - We assume NULL as the invalid state, then it is possible that
+           return value is NULL and ERR is REG_NOERROR.
+         - We never return non-NULL value in case of any errors, it is for
+           optimization.  */
+
+static re_dfastate_t*
+re_acquire_state (err, dfa, nodes)
+     reg_errcode_t *err;
      re_dfa_t *dfa;
      const re_node_set *nodes;
 {
   unsigned int hash;
+  re_dfastate_t *new_state;
   struct re_state_table_entry *spot;
   int i;
-  if (nodes->nelem == 0)
-    return NULL;
+  if (BE (nodes->nelem == 0, 0))
+    {
+      *err = REG_NOERROR;
+      return NULL;
+    }
   hash = calc_state_hash (nodes, 0);
   spot = dfa->state_table + (hash & dfa->state_hash_mask);
 
-  if (spot->alloc == 0)
+  for (i = 0 ; i < spot->num ; i++)
     {
-      /* Currently there are only one state in this spot.  */
-      if (spot->entry.state != NULL && hash == spot->entry.state->hash
-          && re_node_set_compare (&spot->entry.state->nodes, nodes))
-        return spot->entry.state;
+      re_dfastate_t *state = spot->array[i];
+      if (hash != state->hash)
+        continue;
+      if (re_node_set_compare (&state->nodes, nodes))
+        return state;
     }
-  else
-    for (i = 0 ; i < spot->num ; i++)
-      {
-        re_dfastate_t *state = spot->entry.array[i];
-        if (hash != state->hash)
-          continue;
-        if (re_node_set_compare (&state->nodes, nodes))
-          return state;
-      }
 
   /* There are no appropriate state in the dfa, create the new one.  */
-  return create_ci_newstate (dfa, nodes, hash);
+  new_state = create_ci_newstate (dfa, nodes, hash);
+  if (BE (new_state != NULL, 1))
+    return new_state;
+  else
+    {
+      *err = REG_ESPACE;
+      return NULL;
+    }
 }
 
 /* Search for the state whose node_set is equivalent to NODES and
    whose context is equivalent to CONTEXT.
    Return the pointer to the state, if we found it in the DFA.
-   Otherwise create the new one and return it.  */
-
-static re_dfastate_t *
-re_acquire_state_context (dfa, nodes, context)
+   Otherwise create the new one and return it.  In case of an error
+   return NULL and set the error code in ERR.
+   Note: - We assume NULL as the invalid state, then it is possible that
+           return value is NULL and ERR is REG_NOERROR.
+         - We never return non-NULL value in case of any errors, it is for
+           optimization.  */
+
+static re_dfastate_t*
+re_acquire_state_context (err, dfa, nodes, context)
+     reg_errcode_t *err;
      re_dfa_t *dfa;
      const re_node_set *nodes;
      unsigned int context;
 {
   unsigned int hash;
+  re_dfastate_t *new_state;
   struct re_state_table_entry *spot;
   int i;
   if (nodes->nelem == 0)
-    return NULL;
+    {
+      *err = REG_NOERROR;
+      return NULL;
+    }
   hash = calc_state_hash (nodes, context);
   spot = dfa->state_table + (hash & dfa->state_hash_mask);
 
-  if (spot->alloc == 0)
+  for (i = 0 ; i < spot->num ; i++)
     {
-      /* Currently there are only one state in this spot.  */
-      if (spot->entry.state != NULL && hash == spot->entry.state->hash
-          && re_node_set_compare (&spot->entry.state->nodes, nodes)
-          && spot->entry.state->context == context)
-        return spot->entry.state;
+      re_dfastate_t *state = spot->array[i];
+      if (hash != state->hash)
+        continue;
+      if (re_node_set_compare (state->entrance_nodes, nodes)
+          && state->context == context)
+        return state;
     }
-  else
-    for (i = 0 ; i < spot->num ; i++)
-      {
-        re_dfastate_t *state = spot->entry.array[i];
-        if (hash != state->hash)
-          continue;
-        if (re_node_set_compare (state->entrance_nodes, nodes)
-            && state->context == context)
-          return state;
-      }
   /* There are no appropriate state in `dfa', create the new one.  */
-  return create_cd_newstate (dfa, nodes, context, hash);
+  new_state = create_cd_newstate (dfa, nodes, context, hash);
+  if (BE (new_state != NULL, 1))
+    return new_state;
+  else
+    {
+      *err = REG_ESPACE;
+      return NULL;
+    }
 }
 
+/* Allocate memory for DFA state and initialize common properties.
+   Return the new state if succeeded, otherwise return NULL.  */
+
 static re_dfastate_t *
 create_newstate_common (dfa, nodes, hash)
      re_dfa_t *dfa;
@@ -945,6 +1072,8 @@ create_newstate_common (dfa, nodes, hash)
 {
   re_dfastate_t *newstate;
   newstate = (re_dfastate_t *) calloc (sizeof (re_dfastate_t), 1);
+  if (BE (newstate == NULL, 0))
+    return NULL;
   re_node_set_init_copy (&newstate->nodes, nodes);
   newstate->trtable = NULL;
   newstate->trtable_search = NULL;
@@ -952,7 +1081,10 @@ create_newstate_common (dfa, nodes, hash)
   return newstate;
 }
 
-static void
+/* Store the new state NEWSTATE whose hash value is HASH in appropriate
+   position.  Return value indicate the error code if failed.  */
+
+static reg_errcode_t
 register_state (dfa, newstate, hash)
      re_dfa_t *dfa;
      re_dfastate_t *newstate;
@@ -963,30 +1095,18 @@ register_state (dfa, newstate, hash)
 
   if (spot->alloc <= spot->num)
     {
-      re_dfastate_t **new_array;
-
-      /* XXX Is spot->entry.array == NULL if spot->alloc == 0?  If yes
-        the if can go away and only realloc is needed.  */
-      if (spot->alloc == 0)
-        {
-          spot->alloc = 4;
-          new_array = re_malloc (re_dfastate_t *, spot->alloc);
-         if (new_array == NULL)
-           /* XXX return value */
-           return;
-          new_array[0] = spot->entry.state;
-        }
-      else
-        {
-          spot->alloc = 2 * spot->num;
-          new_array = re_realloc (spot->entry.array, re_dfastate_t *,
-                                  spot->alloc);
-        }
-      spot->entry.array = new_array;
+      spot->alloc = 2 * spot->num + 2;
+      spot->array = re_realloc (spot->array, re_dfastate_t *, spot->alloc);
+      if (BE (spot->array == NULL, 0))
+        return REG_ESPACE;
     }
-  spot->entry.array[spot->num++] = newstate;
+  spot->array[spot->num++] = newstate;
+  return REG_NOERROR;
 }
 
+/* Create the new state which is independ of contexts.
+   Return the new state if succeeded, otherwise return NULL.  */
+
 static re_dfastate_t *
 create_ci_newstate (dfa, nodes, hash)
      re_dfa_t *dfa;
@@ -994,38 +1114,40 @@ create_ci_newstate (dfa, nodes, hash)
      unsigned int hash;
 {
   int i;
+  reg_errcode_t err;
   re_dfastate_t *newstate;
   newstate = create_newstate_common (dfa, nodes, hash);
+  if (BE (newstate == NULL, 0))
+    return NULL;
   newstate->entrance_nodes = &newstate->nodes;
 
   for (i = 0 ; i < nodes->nelem ; i++)
     {
       re_token_t *node = dfa->nodes + nodes->elems[i];
       re_token_type_t type = node->type;
-      if (type == CHARACTER)
+      if (type == CHARACTER && !node->constraint)
         continue;
 
       /* If the state has the halt node, the state is a halt state.  */
       else if (type == END_OF_RE)
         newstate->halt = 1;
+#ifdef RE_ENABLE_I18N
       else if (type == COMPLEX_BRACKET
                || (type == OP_PERIOD && MB_CUR_MAX > 1))
         newstate->accept_mb = 1;
+#endif /* RE_ENABLE_I18N */
       else if (type == OP_BACK_REF)
         newstate->has_backref = 1;
-      else if (type == ANCHOR || OP_CONTEXT_NODE)
-        {
-          newstate->has_constraint = 1;
-          if (type == OP_CONTEXT_NODE
-              && dfa->nodes[node->opr.ctx_info->entity].type == END_OF_RE)
-            newstate->halt = 1;
-        }
+      else if (type == ANCHOR || node->constraint)
+        newstate->has_constraint = 1;
     }
-
-  register_state (dfa, newstate, hash);
-  return newstate;
+  err = register_state (dfa, newstate, hash);
+  return (err != REG_NOERROR) ? NULL : newstate;
 }
 
+/* Create the new state which is depend on the context CONTEXT.
+   Return the new state if succeeded, otherwise return NULL.  */
+
 static re_dfastate_t *
 create_cd_newstate (dfa, nodes, context, hash)
      re_dfa_t *dfa;
@@ -1033,9 +1155,12 @@ create_cd_newstate (dfa, nodes, context, hash)
      unsigned int context, hash;
 {
   int i, nctx_nodes = 0;
+  reg_errcode_t err;
   re_dfastate_t *newstate;
 
   newstate = create_newstate_common (dfa, nodes, hash);
+  if (BE (newstate == NULL, 0))
+    return NULL;
   newstate->context = context;
   newstate->entrance_nodes = &newstate->nodes;
 
@@ -1044,39 +1169,30 @@ create_cd_newstate (dfa, nodes, context, hash)
       unsigned int constraint = 0;
       re_token_t *node = dfa->nodes + nodes->elems[i];
       re_token_type_t type = node->type;
-      if (type == CHARACTER)
-        continue;
+      if (node->constraint)
+        constraint = node->constraint;
 
+      if (type == CHARACTER && !constraint)
+        continue;
       /* If the state has the halt node, the state is a halt state.  */
       else if (type == END_OF_RE)
         newstate->halt = 1;
+#ifdef RE_ENABLE_I18N
       else if (type == COMPLEX_BRACKET
                || (type == OP_PERIOD && MB_CUR_MAX > 1))
         newstate->accept_mb = 1;
+#endif /* RE_ENABLE_I18N */
       else if (type == OP_BACK_REF)
         newstate->has_backref = 1;
       else if (type == ANCHOR)
         constraint = node->opr.ctx_type;
-      else if (type == OP_CONTEXT_NODE)
-        {
-          re_token_type_t ctype = dfa->nodes[node->opr.ctx_info->entity].type;
-          constraint = node->constraint;
-          if (ctype == END_OF_RE)
-            newstate->halt = 1;
-          else if (ctype == OP_BACK_REF)
-            newstate->has_backref = 1;
-          else if (ctype == COMPLEX_BRACKET
-                   || (type == OP_PERIOD && MB_CUR_MAX > 1))
-            newstate->accept_mb = 1;
-        }
 
       if (constraint)
         {
           if (newstate->entrance_nodes == &newstate->nodes)
             {
               newstate->entrance_nodes = re_malloc (re_node_set, 1);
-             if (newstate->entrance_nodes == NULL)
-               /* XXX Return which value?  */
+             if (BE (newstate->entrance_nodes == NULL, 0))
                return NULL;
               re_node_set_init_copy (newstate->entrance_nodes, nodes);
               nctx_nodes = 0;
@@ -1090,6 +1206,6 @@ create_cd_newstate (dfa, nodes, context, hash)
             }
         }
     }
-  register_state (dfa, newstate, hash);
-  return newstate;
+  err = register_state (dfa, newstate, hash);
+  return (err != REG_NOERROR) ? NULL : newstate;
 }