lib/regex_internal.c

   1 /* Extended regular expression matching and search library.
   2    Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
   3    This file is part of the GNU C Library.
   4    Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
   5
   6    This program is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 2, or (at your option)
   9    any later version.
  10
  11    This program is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License along
  17    with this program; if not, write to the Free Software Foundation,
  18    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
  19
  20 static void re_string_construct_common (const char *str, int len,
  21                                         re_string_t *pstr,
  22                                         RE_TRANSLATE_TYPE trans, int icase,
  23                                         const re_dfa_t *dfa) internal_function;
  24 #ifdef RE_ENABLE_I18N
  25 static int re_string_skip_chars (re_string_t *pstr, int new_raw_idx,
  26                                  wint_t *last_wc) internal_function;
  27 #endif /* RE_ENABLE_I18N */
  28 static reg_errcode_t register_state (re_dfa_t *dfa, re_dfastate_t *newstate,
  29                                      unsigned int hash) internal_function;
  30 static re_dfastate_t *create_ci_newstate (re_dfa_t *dfa,
  31                                           const re_node_set *nodes,
  32                                           unsigned int hash) internal_function;
  33 static re_dfastate_t *create_cd_newstate (re_dfa_t *dfa,
  34                                           const re_node_set *nodes,
  35                                           unsigned int context,
  36                                           unsigned int hash) internal_function;
  37 static unsigned int inline calc_state_hash (const re_node_set *nodes,
  38                                             unsigned int context) internal_function;
  39 \f
  40 /* Functions for string operation.  */
  41
  42 /* This function allocate the buffers.  It is necessary to call
  43    re_string_reconstruct before using the object.  */
  44
  45 static reg_errcode_t
  46 re_string_allocate (pstr, str, len, init_len, trans, icase, dfa)
  47      re_string_t *pstr;
  48      const char *str;
  49      int len, init_len, icase;
  50      RE_TRANSLATE_TYPE trans;
  51      const re_dfa_t *dfa;
  52 {
  53   reg_errcode_t ret;
  54   int init_buf_len;
  55
  56   /* Ensure at least one character fits into the buffers.  */
  57   if (init_len < dfa->mb_cur_max)
  58     init_len = dfa->mb_cur_max;
  59   init_buf_len = (len + 1 < init_len) ? len + 1: init_len;
  60   re_string_construct_common (str, len, pstr, trans, icase, dfa);
  61
  62   ret = re_string_realloc_buffers (pstr, init_buf_len);
  63   if (BE (ret != REG_NOERROR, 0))
  64     return ret;
  65
  66   pstr->word_char = dfa->word_char;
  67   pstr->word_ops_used = dfa->word_ops_used;
  68   pstr->mbs = pstr->mbs_allocated ? pstr->mbs : (unsigned char *) str;
  69   pstr->valid_len = (pstr->mbs_allocated || dfa->mb_cur_max > 1) ? 0 : len;
  70   pstr->valid_raw_len = pstr->valid_len;
  71   return REG_NOERROR;
  72 }
  73
  74 /* This function allocate the buffers, and initialize them.  */
  75
  76 static reg_errcode_t
  77 re_string_construct (pstr, str, len, trans, icase, dfa)
  78      re_string_t *pstr;
  79      const char *str;
  80      int len, icase;
  81      RE_TRANSLATE_TYPE trans;
  82      const re_dfa_t *dfa;
  83 {
  84   reg_errcode_t ret;
  85   memset (pstr, '\0', sizeof (re_string_t));
  86   re_string_construct_common (str, len, pstr, trans, icase, dfa);
  87
  88   if (len > 0)
  89     {
  90       ret = re_string_realloc_buffers (pstr, len + 1);
  91       if (BE (ret != REG_NOERROR, 0))
  92         return ret;
  93     }
  94   pstr->mbs = pstr->mbs_allocated ? pstr->mbs : (unsigned char *) str;
  95
  96   if (icase)
  97     {
  98 #ifdef RE_ENABLE_I18N
  99       if (dfa->mb_cur_max > 1)
 100         {
 101           while (1)
 102             {
 103               ret = build_wcs_upper_buffer (pstr);
 104               if (BE (ret != REG_NOERROR, 0))
 105                 return ret;
 106               if (pstr->valid_raw_len >= len)
 107                 break;
 108               if (pstr->bufs_len > pstr->valid_len + dfa->mb_cur_max)
 109                 break;
 110               ret = re_string_realloc_buffers (pstr, pstr->bufs_len * 2);
 111               if (BE (ret != REG_NOERROR, 0))
 112                 return ret;
 113             }
 114         }
 115       else
 116 #endif /* RE_ENABLE_I18N  */
 117         build_upper_buffer (pstr);
 118     }
 119   else
 120     {
 121 #ifdef RE_ENABLE_I18N
 122       if (dfa->mb_cur_max > 1)
 123         build_wcs_buffer (pstr);
 124       else
 125 #endif /* RE_ENABLE_I18N  */
 126         {
 127           if (trans != NULL)
 128             re_string_translate_buffer (pstr);
 129           else
 130             {
 131               pstr->valid_len = pstr->bufs_len;
 132               pstr->valid_raw_len = pstr->bufs_len;
 133             }
 134         }
 135     }
 136
 137   return REG_NOERROR;
 138 }
 139
 140 /* Helper functions for re_string_allocate, and re_string_construct.  */
 141
 142 static reg_errcode_t
 143 re_string_realloc_buffers (pstr, new_buf_len)
 144      re_string_t *pstr;
 145      int new_buf_len;
 146 {
 147 #ifdef RE_ENABLE_I18N
 148   if (pstr->mb_cur_max > 1)
 149     {
 150       wint_t *new_wcs = re_realloc (pstr->wcs, wint_t, new_buf_len);
 151       if (BE (new_wcs == NULL, 0))
 152         return REG_ESPACE;
 153       pstr->wcs = new_wcs;
 154       if (pstr->offsets != NULL)
 155         {
 156           int *new_offsets = re_realloc (pstr->offsets, int, new_buf_len);
 157           if (BE (new_offsets == NULL, 0))
 158             return REG_ESPACE;
 159           pstr->offsets = new_offsets;
 160         }
 161     }
 162 #endif /* RE_ENABLE_I18N  */
 163   if (pstr->mbs_allocated)
 164     {
 165       unsigned char *new_mbs = re_realloc (pstr->mbs, unsigned char,
 166                                            new_buf_len);
 167       if (BE (new_mbs == NULL, 0))
 168         return REG_ESPACE;
 169       pstr->mbs = new_mbs;
 170     }
 171   pstr->bufs_len = new_buf_len;
 172   return REG_NOERROR;
 173 }
 174
 175
 176 static void
 177 re_string_construct_common (str, len, pstr, trans, icase, dfa)
 178      const char *str;
 179      int len;
 180      re_string_t *pstr;
 181      RE_TRANSLATE_TYPE trans;
 182      int icase;
 183      const re_dfa_t *dfa;
 184 {
 185   pstr->raw_mbs = (const unsigned char *) str;
 186   pstr->len = len;
 187   pstr->raw_len = len;
 188   pstr->trans = (unsigned RE_TRANSLATE_TYPE) trans;
 189   pstr->icase = icase ? 1 : 0;
 190   pstr->mbs_allocated = (trans != NULL || icase);
 191   pstr->mb_cur_max = dfa->mb_cur_max;
 192   pstr->is_utf8 = dfa->is_utf8;
 193   pstr->map_notascii = dfa->map_notascii;
 194   pstr->stop = pstr->len;
 195   pstr->raw_stop = pstr->stop;
 196 }
 197
 198 #ifdef RE_ENABLE_I18N
 199
 200 /* Build wide character buffer PSTR->WCS.
 201    If the byte sequence of the string are:
 202      <mb1>(0), <mb1>(1), <mb2>(0), <mb2>(1), <sb3>
 203    Then wide character buffer will be:
 204      <wc1>   , WEOF    , <wc2>   , WEOF    , <wc3>
 205    We use WEOF for padding, they indicate that the position isn't
 206    a first byte of a multibyte character.
 207
 208    Note that this function assumes PSTR->VALID_LEN elements are already
 209    built and starts from PSTR->VALID_LEN.  */
 210
 211 static void
 212 build_wcs_buffer (pstr)
 213      re_string_t *pstr;
 214 {
 215 #ifdef _LIBC
 216   unsigned char buf[MB_LEN_MAX];
 217   assert (MB_LEN_MAX >= pstr->mb_cur_max);
 218 #else
 219   unsigned char buf[64];
 220 #endif
 221   mbstate_t prev_st;
 222   int byte_idx, end_idx, remain_len;
 223   size_t mbclen;
 224
 225   /* Build the buffers from pstr->valid_len to either pstr->len or
 226      pstr->bufs_len.  */
 227   end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len;
 228   for (byte_idx = pstr->valid_len; byte_idx < end_idx;)
 229     {
 230       wchar_t wc;
 231       const char *p;
 232
 233       remain_len = end_idx - byte_idx;
 234       prev_st = pstr->cur_state;
 235       /* Apply the translation if we need.  */
 236       if (BE (pstr->trans != NULL, 0))
 237         {
 238           int i, ch;
 239
 240           for (i = 0; i < pstr->mb_cur_max && i < remain_len; ++i)
 241             {
 242               ch = pstr->raw_mbs [pstr->raw_mbs_idx + byte_idx + i];
 243               buf[i] = pstr->mbs[byte_idx + i] = pstr->trans[ch];
 244             }
 245           p = (const char *) buf;
 246         }
 247       else
 248         p = (const char *) pstr->raw_mbs + pstr->raw_mbs_idx + byte_idx;
 249       mbclen = mbrtowc (&wc, p, remain_len, &pstr->cur_state);
 250       if (BE (mbclen == (size_t) -2, 0))
 251         {
 252           /* The buffer doesn't have enough space, finish to build.  */
 253           pstr->cur_state = prev_st;
 254           break;
 255         }
 256       else if (BE (mbclen == (size_t) -1 || mbclen == 0, 0))
 257         {
 258           /* We treat these cases as a singlebyte character.  */
 259           mbclen = 1;
 260           wc = (wchar_t) pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx];
 261           if (BE (pstr->trans != NULL, 0))
 262             wc = pstr->trans[wc];
 263           pstr->cur_state = prev_st;
 264         }
 265
 266       /* Write wide character and padding.  */
 267       pstr->wcs[byte_idx++] = wc;
 268       /* Write paddings.  */
 269       for (remain_len = byte_idx + mbclen - 1; byte_idx < remain_len ;)
 270         pstr->wcs[byte_idx++] = WEOF;
 271     }
 272   pstr->valid_len = byte_idx;
 273   pstr->valid_raw_len = byte_idx;
 274 }
 275
 276 /* Build wide character buffer PSTR->WCS like build_wcs_buffer,
 277    but for REG_ICASE.  */
 278
 279 static int
 280 build_wcs_upper_buffer (pstr)
 281      re_string_t *pstr;
 282 {
 283   mbstate_t prev_st;
 284   int src_idx, byte_idx, end_idx, remain_len;
 285   size_t mbclen;
 286 #ifdef _LIBC
 287   char buf[MB_LEN_MAX];
 288   assert (MB_LEN_MAX >= pstr->mb_cur_max);
 289 #else
 290   char buf[64];
 291 #endif
 292
 293   byte_idx = pstr->valid_len;
 294   end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len;
 295
 296   /* The following optimization assumes that ASCII characters can be
 297      mapped to wide characters with a simple cast.  */
 298   if (! pstr->map_notascii && pstr->trans == NULL && !pstr->offsets_needed)
 299     {
 300       while (byte_idx < end_idx)
 301         {
 302           wchar_t wc;
 303
 304           if (isascii (pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx])
 305               && mbsinit (&pstr->cur_state))
 306             {
 307               /* In case of a singlebyte character.  */
 308               pstr->mbs[byte_idx]
 309                 = toupper (pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx]);
 310               /* The next step uses the assumption that wchar_t is encoded
 311                  ASCII-safe: all ASCII values can be converted like this.  */
 312               pstr->wcs[byte_idx] = (wchar_t) pstr->mbs[byte_idx];
 313               ++byte_idx;
 314               continue;
 315             }
 316
 317           remain_len = end_idx - byte_idx;
 318           prev_st = pstr->cur_state;
 319           mbclen = mbrtowc (&wc,
 320                             ((const char *) pstr->raw_mbs + pstr->raw_mbs_idx
 321                              + byte_idx), remain_len, &pstr->cur_state);
 322           if (BE (mbclen + 2 > 2, 1))
 323             {
 324               wchar_t wcu = wc;
 325               if (iswlower (wc))
 326                 {
 327                   size_t mbcdlen;
 328
 329                   wcu = towupper (wc);
 330                   mbcdlen = wcrtomb (buf, wcu, &prev_st);
 331                   if (BE (mbclen == mbcdlen, 1))
 332                     memcpy (pstr->mbs + byte_idx, buf, mbclen);
 333                   else
 334                     {
 335                       src_idx = byte_idx;
 336                       goto offsets_needed;
 337                     }
 338                 }
 339               else
 340                 memcpy (pstr->mbs + byte_idx,
 341                         pstr->raw_mbs + pstr->raw_mbs_idx + byte_idx, mbclen);
 342               pstr->wcs[byte_idx++] = wcu;
 343               /* Write paddings.  */
 344               for (remain_len = byte_idx + mbclen - 1; byte_idx < remain_len ;)
 345                 pstr->wcs[byte_idx++] = WEOF;
 346             }
 347           else if (mbclen == (size_t) -1 || mbclen == 0)
 348             {
 349               /* It is an invalid character or '\0'.  Just use the byte.  */
 350               int ch = pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx];
 351               pstr->mbs[byte_idx] = ch;
 352               /* And also cast it to wide char.  */
 353               pstr->wcs[byte_idx++] = (wchar_t) ch;
 354               if (BE (mbclen == (size_t) -1, 0))
 355                 pstr->cur_state = prev_st;
 356             }
 357           else
 358             {
 359               /* The buffer doesn't have enough space, finish to build.  */
 360               pstr->cur_state = prev_st;
 361               break;
 362             }
 363         }
 364       pstr->valid_len = byte_idx;
 365       pstr->valid_raw_len = byte_idx;
 366       return REG_NOERROR;
 367     }
 368   else
 369     for (src_idx = pstr->valid_raw_len; byte_idx < end_idx;)
 370       {
 371         wchar_t wc;
 372         const char *p;
 373       offsets_needed:
 374         remain_len = end_idx - byte_idx;
 375         prev_st = pstr->cur_state;
 376         if (BE (pstr->trans != NULL, 0))
 377           {
 378             int i, ch;
 379
 380             for (i = 0; i < pstr->mb_cur_max && i < remain_len; ++i)
 381               {
 382                 ch = pstr->raw_mbs [pstr->raw_mbs_idx + src_idx + i];
 383                 buf[i] = pstr->trans[ch];
 384               }
 385             p = (const char *) buf;
 386           }
 387         else
 388           p = (const char *) pstr->raw_mbs + pstr->raw_mbs_idx + src_idx;
 389         mbclen = mbrtowc (&wc, p, remain_len, &pstr->cur_state);
 390         if (BE (mbclen + 2 > 2, 1))
 391           {
 392             wchar_t wcu = wc;
 393             if (iswlower (wc))
 394               {
 395                 size_t mbcdlen;
 396
 397                 wcu = towupper (wc);
 398                 mbcdlen = wcrtomb ((char *) buf, wcu, &prev_st);
 399                 if (BE (mbclen == mbcdlen, 1))
 400                   memcpy (pstr->mbs + byte_idx, buf, mbclen);
 401                 else if (mbcdlen != (size_t) -1)
 402                   {
 403                     size_t i;
 404
 405                     if (byte_idx + mbcdlen > pstr->bufs_len)
 406                       {
 407                         pstr->cur_state = prev_st;
 408                         break;
 409                       }
 410
 411                     if (pstr->offsets == NULL)
 412                       {
 413                         pstr->offsets = re_malloc (int, pstr->bufs_len);
 414
 415                         if (pstr->offsets == NULL)
 416                           return REG_ESPACE;
 417                       }
 418                     if (!pstr->offsets_needed)
 419                       {
 420                         for (i = 0; i < (size_t) byte_idx; ++i)
 421                           pstr->offsets[i] = i;
 422                         pstr->offsets_needed = 1;
 423                       }
 424
 425                     memcpy (pstr->mbs + byte_idx, buf, mbcdlen);
 426                     pstr->wcs[byte_idx] = wcu;
 427                     pstr->offsets[byte_idx] = src_idx;
 428                     for (i = 1; i < mbcdlen; ++i)
 429                       {
 430                         pstr->offsets[byte_idx + i]
 431                           = src_idx + (i < mbclen ? i : mbclen - 1);
 432                         pstr->wcs[byte_idx + i] = WEOF;
 433                       }
 434                     pstr->len += mbcdlen - mbclen;
 435                     if (pstr->raw_stop > src_idx)
 436                       pstr->stop += mbcdlen - mbclen;
 437                     end_idx = (pstr->bufs_len > pstr->len)
 438                               ? pstr->len : pstr->bufs_len;
 439                     byte_idx += mbcdlen;
 440                     src_idx += mbclen;
 441                     continue;
 442                   }
 443                 else
 444                   memcpy (pstr->mbs + byte_idx, p, mbclen);
 445               }
 446             else
 447               memcpy (pstr->mbs + byte_idx, p, mbclen);
 448
 449             if (BE (pstr->offsets_needed != 0, 0))
 450               {
 451                 size_t i;
 452                 for (i = 0; i < mbclen; ++i)
 453                   pstr->offsets[byte_idx + i] = src_idx + i;
 454               }
 455             src_idx += mbclen;
 456
 457             pstr->wcs[byte_idx++] = wcu;
 458             /* Write paddings.  */
 459             for (remain_len = byte_idx + mbclen - 1; byte_idx < remain_len ;)
 460               pstr->wcs[byte_idx++] = WEOF;
 461           }
 462         else if (mbclen == (size_t) -1 || mbclen == 0)
 463           {
 464             /* It is an invalid character or '\0'.  Just use the byte.  */
 465             int ch = pstr->raw_mbs[pstr->raw_mbs_idx + src_idx];
 466
 467             if (BE (pstr->trans != NULL, 0))
 468               ch = pstr->trans [ch];
 469             pstr->mbs[byte_idx] = ch;
 470
 471             if (BE (pstr->offsets_needed != 0, 0))
 472               pstr->offsets[byte_idx] = src_idx;
 473             ++src_idx;
 474
 475             /* And also cast it to wide char.  */
 476             pstr->wcs[byte_idx++] = (wchar_t) ch;
 477             if (BE (mbclen == (size_t) -1, 0))
 478               pstr->cur_state = prev_st;
 479           }
 480         else
 481           {
 482             /* The buffer doesn't have enough space, finish to build.  */
 483             pstr->cur_state = prev_st;
 484             break;
 485           }
 486       }
 487   pstr->valid_len = byte_idx;
 488   pstr->valid_raw_len = src_idx;
 489   return REG_NOERROR;
 490 }
 491
 492 /* Skip characters until the index becomes greater than NEW_RAW_IDX.
 493    Return the index.  */
 494
 495 static int
 496 re_string_skip_chars (pstr, new_raw_idx, last_wc)
 497      re_string_t *pstr;
 498      int new_raw_idx;
 499      wint_t *last_wc;
 500 {
 501   mbstate_t prev_st;
 502   int rawbuf_idx;
 503   size_t mbclen;
 504   wchar_t wc = 0;
 505
 506   /* Skip the characters which are not necessary to check.  */
 507   for (rawbuf_idx = pstr->raw_mbs_idx + pstr->valid_raw_len;
 508        rawbuf_idx < new_raw_idx;)
 509     {
 510       int remain_len;
 511       remain_len = pstr->len - rawbuf_idx;
 512       prev_st = pstr->cur_state;
 513       mbclen = mbrtowc (&wc, (const char *) pstr->raw_mbs + rawbuf_idx,
 514                         remain_len, &pstr->cur_state);
 515       if (BE (mbclen == (size_t) -2 || mbclen == (size_t) -1 || mbclen == 0, 0))
 516         {
 517           /* We treat these cases as a singlebyte character.  */
 518           mbclen = 1;
 519           pstr->cur_state = prev_st;
 520         }
 521       /* Then proceed the next character.  */
 522       rawbuf_idx += mbclen;
 523     }
 524   *last_wc = (wint_t) wc;
 525   return rawbuf_idx;
 526 }
 527 #endif /* RE_ENABLE_I18N  */
 528
 529 /* Build the buffer PSTR->MBS, and apply the translation if we need.
 530    This function is used in case of REG_ICASE.  */
 531
 532 static void
 533 build_upper_buffer (pstr)
 534      re_string_t *pstr;
 535 {
 536   int char_idx, end_idx;
 537   end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len;
 538
 539   for (char_idx = pstr->valid_len; char_idx < end_idx; ++char_idx)
 540     {
 541       int ch = pstr->raw_mbs[pstr->raw_mbs_idx + char_idx];
 542       if (BE (pstr->trans != NULL, 0))
 543         ch = pstr->trans[ch];
 544       if (islower (ch))
 545         pstr->mbs[char_idx] = toupper (ch);
 546       else
 547         pstr->mbs[char_idx] = ch;
 548     }
 549   pstr->valid_len = char_idx;
 550   pstr->valid_raw_len = char_idx;
 551 }
 552
 553 /* Apply TRANS to the buffer in PSTR.  */
 554
 555 static void
 556 re_string_translate_buffer (pstr)
 557      re_string_t *pstr;
 558 {
 559   int buf_idx, end_idx;
 560   end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len;
 561
 562   for (buf_idx = pstr->valid_len; buf_idx < end_idx; ++buf_idx)
 563     {
 564       int ch = pstr->raw_mbs[pstr->raw_mbs_idx + buf_idx];
 565       pstr->mbs[buf_idx] = pstr->trans[ch];
 566     }
 567
 568   pstr->valid_len = buf_idx;
 569   pstr->valid_raw_len = buf_idx;
 570 }
 571
 572 /* This function re-construct the buffers.
 573    Concretely, convert to wide character in case of pstr->mb_cur_max > 1,
 574    convert to upper case in case of REG_ICASE, apply translation.  */
 575
 576 static reg_errcode_t
 577 re_string_reconstruct (pstr, idx, eflags)
 578      re_string_t *pstr;
 579      int idx, eflags;
 580 {
 581   int offset = idx - pstr->raw_mbs_idx;
 582   if (BE (offset < 0, 0))
 583     {
 584       /* Reset buffer.  */
 585 #ifdef RE_ENABLE_I18N
 586       if (pstr->mb_cur_max > 1)
 587         memset (&pstr->cur_state, '\0', sizeof (mbstate_t));
 588 #endif /* RE_ENABLE_I18N */
 589       pstr->len = pstr->raw_len;
 590       pstr->stop = pstr->raw_stop;
 591       pstr->valid_len = 0;
 592       pstr->raw_mbs_idx = 0;
 593       pstr->valid_raw_len = 0;
 594       pstr->offsets_needed = 0;
 595       pstr->tip_context = ((eflags & REG_NOTBOL) ? CONTEXT_BEGBUF
 596                            : CONTEXT_NEWLINE | CONTEXT_BEGBUF);
 597       if (!pstr->mbs_allocated)
 598         pstr->mbs = (unsigned char *) pstr->raw_mbs;
 599       offset = idx;
 600     }
 601
 602   if (BE (offset != 0, 1))
 603     {
 604       /* Are the characters which are already checked remain?  */
 605       if (BE (offset < pstr->valid_raw_len, 1)
 606 #ifdef RE_ENABLE_I18N
 607           /* Handling this would enlarge the code too much.
 608              Accept a slowdown in that case.  */
 609           && pstr->offsets_needed == 0
 610 #endif
 611          )
 612         {
 613           /* Yes, move them to the front of the buffer.  */
 614           pstr->tip_context = re_string_context_at (pstr, offset - 1, eflags);
 615 #ifdef RE_ENABLE_I18N
 616           if (pstr->mb_cur_max > 1)
 617             memmove (pstr->wcs, pstr->wcs + offset,
 618                      (pstr->valid_len - offset) * sizeof (wint_t));
 619 #endif /* RE_ENABLE_I18N */
 620           if (BE (pstr->mbs_allocated, 0))
 621             memmove (pstr->mbs, pstr->mbs + offset,
 622                      pstr->valid_len - offset);
 623           pstr->valid_len -= offset;
 624           pstr->valid_raw_len -= offset;
 625 #if DEBUG
 626           assert (pstr->valid_len > 0);
 627 #endif
 628         }
 629       else
 630         {
 631           /* No, skip all characters until IDX.  */
 632 #ifdef RE_ENABLE_I18N
 633           if (BE (pstr->offsets_needed, 0))
 634             {
 635               pstr->len = pstr->raw_len - idx + offset;
 636               pstr->stop = pstr->raw_stop - idx + offset;
 637               pstr->offsets_needed = 0;
 638             }
 639 #endif
 640           pstr->valid_len = 0;
 641           pstr->valid_raw_len = 0;
 642 #ifdef RE_ENABLE_I18N
 643           if (pstr->mb_cur_max > 1)
 644             {
 645               int wcs_idx;
 646               wint_t wc = WEOF;
 647
 648               if (pstr->is_utf8)
 649                 {
 650                   const unsigned char *raw, *p, *q, *end;
 651
 652                   /* Special case UTF-8.  Multi-byte chars start with any
 653                      byte other than 0x80 - 0xbf.  */
 654                   raw = pstr->raw_mbs + pstr->raw_mbs_idx;
 655                   end = raw + (offset - pstr->mb_cur_max);
 656                   for (p = raw + offset - 1; p >= end; --p)
 657                     if ((*p & 0xc0) != 0x80)
 658                       {
 659                         mbstate_t cur_state;
 660                         wchar_t wc2;
 661                         int mlen = raw + pstr->len - p;
 662                         unsigned char buf[6];
 663
 664                         q = p;
 665                         if (BE (pstr->trans != NULL, 0))
 666                           {
 667                             int i = mlen < 6 ? mlen : 6;
 668                             while (--i >= 0)
 669                               buf[i] = pstr->trans[p[i]];
 670                             q = buf;
 671                           }
 672                         /* XXX Don't use mbrtowc, we know which conversion
 673                            to use (UTF-8 -> UCS4).  */
 674                         memset (&cur_state, 0, sizeof (cur_state));
 675                         mlen = (mbrtowc (&wc2, (const char *) p, mlen,
 676                                          &cur_state)
 677                                 - (raw + offset - p));
 678                         if (mlen >= 0)
 679                           {
 680                             memset (&pstr->cur_state, '\0',
 681                                     sizeof (mbstate_t));
 682                             pstr->valid_len = mlen;
 683                             wc = wc2;
 684                           }
 685                         break;
 686                       }
 687                 }
 688
 689               if (wc == WEOF)
 690                 pstr->valid_len = re_string_skip_chars (pstr, idx, &wc) - idx;
 691               if (BE (pstr->valid_len, 0))
 692                 {
 693                   for (wcs_idx = 0; wcs_idx < pstr->valid_len; ++wcs_idx)
 694                     pstr->wcs[wcs_idx] = WEOF;
 695                   if (pstr->mbs_allocated)
 696                     memset (pstr->mbs, 255, pstr->valid_len);
 697                 }
 698               pstr->valid_raw_len = pstr->valid_len;
 699               pstr->tip_context = ((BE (pstr->word_ops_used != 0, 0)
 700                                     && IS_WIDE_WORD_CHAR (wc))
 701                                    ? CONTEXT_WORD
 702                                    : ((IS_WIDE_NEWLINE (wc)
 703                                        && pstr->newline_anchor)
 704                                       ? CONTEXT_NEWLINE : 0));
 705             }
 706           else
 707 #endif /* RE_ENABLE_I18N */
 708             {
 709               int c = pstr->raw_mbs[pstr->raw_mbs_idx + offset - 1];
 710               if (pstr->trans)
 711                 c = pstr->trans[c];
 712               pstr->tip_context = (bitset_contain (pstr->word_char, c)
 713                                    ? CONTEXT_WORD
 714                                    : ((IS_NEWLINE (c) && pstr->newline_anchor)
 715                                       ? CONTEXT_NEWLINE : 0));
 716             }
 717         }
 718       if (!BE (pstr->mbs_allocated, 0))
 719         pstr->mbs += offset;
 720     }
 721   pstr->raw_mbs_idx = idx;
 722   pstr->len -= offset;
 723   pstr->stop -= offset;
 724
 725   /* Then build the buffers.  */
 726 #ifdef RE_ENABLE_I18N
 727   if (pstr->mb_cur_max > 1)
 728     {
 729       if (pstr->icase)
 730         {
 731           int ret = build_wcs_upper_buffer (pstr);
 732           if (BE (ret != REG_NOERROR, 0))
 733             return ret;
 734         }
 735       else
 736         build_wcs_buffer (pstr);
 737     }
 738   else
 739 #endif /* RE_ENABLE_I18N */
 740   if (BE (pstr->mbs_allocated, 0))
 741     {
 742       if (pstr->icase)
 743         build_upper_buffer (pstr);
 744       else if (pstr->trans != NULL)
 745         re_string_translate_buffer (pstr);
 746     }
 747   else
 748     pstr->valid_len = pstr->len;
 749
 750   pstr->cur_idx = 0;
 751   return REG_NOERROR;
 752 }
 753
 754 static unsigned char
 755 re_string_peek_byte_case (pstr, idx)
 756      const re_string_t *pstr;
 757      int idx;
 758 {
 759   int ch, off;
 760
 761   /* Handle the common (easiest) cases first.  */
 762   if (BE (!pstr->mbs_allocated, 1))
 763     return re_string_peek_byte (pstr, idx);
 764
 765 #ifdef RE_ENABLE_I18N
 766   if (pstr->mb_cur_max > 1
 767       && ! re_string_is_single_byte_char (pstr, pstr->cur_idx + idx))
 768     return re_string_peek_byte (pstr, idx);
 769 #endif
 770
 771   off = pstr->cur_idx + idx;
 772 #ifdef RE_ENABLE_I18N
 773   if (pstr->offsets_needed)
 774     off = pstr->offsets[off];
 775 #endif
 776
 777   ch = pstr->raw_mbs[pstr->raw_mbs_idx + off];
 778
 779 #ifdef RE_ENABLE_I18N
 780   /* Ensure that e.g. for tr_TR.UTF-8 BACKSLASH DOTLESS SMALL LETTER I
 781      this function returns CAPITAL LETTER I instead of first byte of
 782      DOTLESS SMALL LETTER I.  The latter would confuse the parser,
 783      since peek_byte_case doesn't advance cur_idx in any way.  */
 784   if (pstr->offsets_needed && !isascii (ch))
 785     return re_string_peek_byte (pstr, idx);
 786 #endif
 787
 788   return ch;
 789 }
 790
 791 static unsigned char
 792 re_string_fetch_byte_case (pstr)
 793      re_string_t *pstr;
 794 {
 795   if (BE (!pstr->mbs_allocated, 1))
 796     return re_string_fetch_byte (pstr);
 797
 798 #ifdef RE_ENABLE_I18N
 799   if (pstr->offsets_needed)
 800     {
 801       int off, ch;
 802
 803       /* For tr_TR.UTF-8 [[:islower:]] there is
 804          [[: CAPITAL LETTER I WITH DOT lower:]] in mbs.  Skip
 805          in that case the whole multi-byte character and return
 806          the original letter.  On the other side, with
 807          [[: DOTLESS SMALL LETTER I return [[:I, as doing
 808          anything else would complicate things too much.  */
 809
 810       if (!re_string_first_byte (pstr, pstr->cur_idx))
 811         return re_string_fetch_byte (pstr);
 812
 813       off = pstr->offsets[pstr->cur_idx];
 814       ch = pstr->raw_mbs[pstr->raw_mbs_idx + off];
 815
 816       if (! isascii (ch))
 817         return re_string_fetch_byte (pstr);
 818
 819       re_string_skip_bytes (pstr,
 820                             re_string_char_size_at (pstr, pstr->cur_idx));
 821       return ch;
 822     }
 823 #endif
 824
 825   return pstr->raw_mbs[pstr->raw_mbs_idx + pstr->cur_idx++];
 826 }
 827
 828 static void
 829 re_string_destruct (pstr)
 830      re_string_t *pstr;
 831 {
 832 #ifdef RE_ENABLE_I18N
 833   re_free (pstr->wcs);
 834   re_free (pstr->offsets);
 835 #endif /* RE_ENABLE_I18N  */
 836   if (pstr->mbs_allocated)
 837     re_free (pstr->mbs);
 838 }
 839
 840 /* Return the context at IDX in INPUT.  */
 841
 842 static unsigned int
 843 re_string_context_at (input, idx, eflags)
 844      const re_string_t *input;
 845      int idx, eflags;
 846 {
 847   int c;
 848   if (BE (idx < 0, 0))
 849     /* In this case, we use the value stored in input->tip_context,
 850        since we can't know the character in input->mbs[-1] here.  */
 851     return input->tip_context;
 852   if (BE (idx == input->len, 0))
 853     return ((eflags & REG_NOTEOL) ? CONTEXT_ENDBUF
 854             : CONTEXT_NEWLINE | CONTEXT_ENDBUF);
 855 #ifdef RE_ENABLE_I18N
 856   if (input->mb_cur_max > 1)
 857     {
 858       wint_t wc;
 859       int wc_idx = idx;
 860       while(input->wcs[wc_idx] == WEOF)
 861         {
 862 #ifdef DEBUG
 863           /* It must not happen.  */
 864           assert (wc_idx >= 0);
 865 #endif
 866           --wc_idx;
 867           if (wc_idx < 0)
 868             return input->tip_context;
 869         }
 870       wc = input->wcs[wc_idx];
 871       if (BE (input->word_ops_used != 0, 0) && IS_WIDE_WORD_CHAR (wc))
 872         return CONTEXT_WORD;
 873       return (IS_WIDE_NEWLINE (wc) && input->newline_anchor
 874               ? CONTEXT_NEWLINE : 0);
 875     }
 876   else
 877 #endif
 878     {
 879       c = re_string_byte_at (input, idx);
 880       if (bitset_contain (input->word_char, c))
 881         return CONTEXT_WORD;
 882       return IS_NEWLINE (c) && input->newline_anchor ? CONTEXT_NEWLINE : 0;
 883     }
 884 }
 885 \f
 886 /* Functions for set operation.  */
 887
 888 static reg_errcode_t
 889 re_node_set_alloc (set, size)
 890      re_node_set *set;
 891      int size;
 892 {
 893   set->alloc = size;
 894   set->nelem = 0;
 895   set->elems = re_malloc (int, size);
 896   if (BE (set->elems == NULL, 0))
 897     return REG_ESPACE;
 898   return REG_NOERROR;
 899 }
 900
 901 static reg_errcode_t
 902 re_node_set_init_1 (set, elem)
 903      re_node_set *set;
 904      int elem;
 905 {
 906   set->alloc = 1;
 907   set->nelem = 1;
 908   set->elems = re_malloc (int, 1);
 909   if (BE (set->elems == NULL, 0))
 910     {
 911       set->alloc = set->nelem = 0;
 912       return REG_ESPACE;
 913     }
 914   set->elems[0] = elem;
 915   return REG_NOERROR;
 916 }
 917
 918 static reg_errcode_t
 919 re_node_set_init_2 (set, elem1, elem2)
 920      re_node_set *set;
 921      int elem1, elem2;
 922 {
 923   set->alloc = 2;
 924   set->elems = re_malloc (int, 2);
 925   if (BE (set->elems == NULL, 0))
 926     return REG_ESPACE;
 927   if (elem1 == elem2)
 928     {
 929       set->nelem = 1;
 930       set->elems[0] = elem1;
 931     }
 932   else
 933     {
 934       set->nelem = 2;
 935       if (elem1 < elem2)
 936         {
 937           set->elems[0] = elem1;
 938           set->elems[1] = elem2;
 939         }
 940       else
 941         {
 942           set->elems[0] = elem2;
 943           set->elems[1] = elem1;
 944         }
 945     }
 946   return REG_NOERROR;
 947 }
 948
 949 static reg_errcode_t
 950 re_node_set_init_copy (dest, src)
 951      re_node_set *dest;
 952      const re_node_set *src;
 953 {
 954   dest->nelem = src->nelem;
 955   if (src->nelem > 0)
 956     {
 957       dest->alloc = dest->nelem;
 958       dest->elems = re_malloc (int, dest->alloc);
 959       if (BE (dest->elems == NULL, 0))
 960         {
 961           dest->alloc = dest->nelem = 0;
 962           return REG_ESPACE;
 963         }
 964       memcpy (dest->elems, src->elems, src->nelem * sizeof (int));
 965     }
 966   else
 967     re_node_set_init_empty (dest);
 968   return REG_NOERROR;
 969 }
 970
 971 /* Calculate the intersection of the sets SRC1 and SRC2. And merge it to
 972    DEST. Return value indicate the error code or REG_NOERROR if succeeded.
 973    Note: We assume dest->elems is NULL, when dest->alloc is 0.  */
 974
 975 static reg_errcode_t
 976 re_node_set_add_intersect (dest, src1, src2)
 977      re_node_set *dest;
 978      const re_node_set *src1, *src2;
 979 {
 980   int i1, i2, is, id, delta, sbase;
 981   if (src1->nelem == 0 || src2->nelem == 0)
 982     return REG_NOERROR;
 983
 984   /* We need dest->nelem + 2 * elems_in_intersection; this is a
 985      conservative estimate.  */
 986   if (src1->nelem + src2->nelem + dest->nelem > dest->alloc)
 987     {
 988       int new_alloc = src1->nelem + src2->nelem + dest->alloc;
 989       int *new_elems = re_realloc (dest->elems, int, new_alloc);
 990       if (BE (new_elems == NULL, 0))
 991         return REG_ESPACE;
 992       dest->elems = new_elems;
 993       dest->alloc = new_alloc;
 994     }
 995
 996   /* Find the items in the intersection of SRC1 and SRC2, and copy
 997      into the top of DEST those that are not already in DEST itself.  */
 998   sbase = dest->nelem + src1->nelem + src2->nelem;
 999   i1 = src1->nelem - 1;
1000   i2 = src2->nelem - 1;
1001   id = dest->nelem - 1;
1002   for (;;)
1003     {
1004       if (src1->elems[i1] == src2->elems[i2])
1005         {
1006           /* Try to find the item in DEST.  Maybe we could binary search?  */
1007           while (id >= 0 && dest->elems[id] > src1->elems[i1])
1008             --id;
1009
1010           if (id < 0 || dest->elems[id] != src1->elems[i1])
1011             dest->elems[--sbase] = src1->elems[i1];
1012
1013           if (--i1 < 0 || --i2 < 0)
1014             break;
1015         }
1016
1017       /* Lower the highest of the two items.  */
1018       else if (src1->elems[i1] < src2->elems[i2])
1019         {
1020           if (--i2 < 0)
1021             break;
1022         }
1023       else
1024         {
1025           if (--i1 < 0)
1026             break;
1027         }
1028     }
1029
1030   id = dest->nelem - 1;
1031   is = dest->nelem + src1->nelem + src2->nelem - 1;
1032   delta = is - sbase + 1;
1033
1034   /* Now copy.  When DELTA becomes zero, the remaining
1035      DEST elements are already in place; this is more or
1036      less the same loop that is in re_node_set_merge.  */
1037   dest->nelem += delta;
1038   if (delta > 0 && id >= 0)
1039     for (;;)
1040       {
1041         if (dest->elems[is] > dest->elems[id])
1042           {
1043             /* Copy from the top.  */
1044             dest->elems[id + delta--] = dest->elems[is--];
1045             if (delta == 0)
1046               break;
1047           }
1048         else
1049           {
1050             /* Slide from the bottom.  */
1051             dest->elems[id + delta] = dest->elems[id];
1052             if (--id < 0)
1053               break;
1054           }
1055       }
1056
1057   /* Copy remaining SRC elements.  */
1058   memcpy (dest->elems, dest->elems + sbase, delta * sizeof (int));
1059
1060   return REG_NOERROR;
1061 }
1062
1063 /* Calculate the union set of the sets SRC1 and SRC2. And store it to
1064    DEST. Return value indicate the error code or REG_NOERROR if succeeded.  */
1065
1066 static reg_errcode_t
1067 re_node_set_init_union (dest, src1, src2)
1068      re_node_set *dest;
1069      const re_node_set *src1, *src2;
1070 {
1071   int i1, i2, id;
1072   if (src1 != NULL && src1->nelem > 0 && src2 != NULL && src2->nelem > 0)
1073     {
1074       dest->alloc = src1->nelem + src2->nelem;
1075       dest->elems = re_malloc (int, dest->alloc);
1076       if (BE (dest->elems == NULL, 0))
1077         return REG_ESPACE;
1078     }
1079   else
1080     {
1081       if (src1 != NULL && src1->nelem > 0)
1082         return re_node_set_init_copy (dest, src1);
1083       else if (src2 != NULL && src2->nelem > 0)
1084         return re_node_set_init_copy (dest, src2);
1085       else
1086         re_node_set_init_empty (dest);
1087       return REG_NOERROR;
1088     }
1089   for (i1 = i2 = id = 0 ; i1 < src1->nelem && i2 < src2->nelem ;)
1090     {
1091       if (src1->elems[i1] > src2->elems[i2])
1092         {
1093           dest->elems[id++] = src2->elems[i2++];
1094           continue;
1095         }
1096       if (src1->elems[i1] == src2->elems[i2])
1097         ++i2;
1098       dest->elems[id++] = src1->elems[i1++];
1099     }
1100   if (i1 < src1->nelem)
1101     {
1102       memcpy (dest->elems + id, src1->elems + i1,
1103              (src1->nelem - i1) * sizeof (int));
1104       id += src1->nelem - i1;
1105     }
1106   else if (i2 < src2->nelem)
1107     {
1108       memcpy (dest->elems + id, src2->elems + i2,
1109              (src2->nelem - i2) * sizeof (int));
1110       id += src2->nelem - i2;
1111     }
1112   dest->nelem = id;
1113   return REG_NOERROR;
1114 }
1115
1116 /* Calculate the union set of the sets DEST and SRC. And store it to
1117    DEST. Return value indicate the error code or REG_NOERROR if succeeded.  */
1118
1119 static reg_errcode_t
1120 re_node_set_merge (dest, src)
1121      re_node_set *dest;
1122      const re_node_set *src;
1123 {
1124   int is, id, sbase, delta;
1125   if (src == NULL || src->nelem == 0)
1126     return REG_NOERROR;
1127   if (dest->alloc < 2 * src->nelem + dest->nelem)
1128     {
1129       int new_alloc = 2 * (src->nelem + dest->alloc);
1130       int *new_buffer = re_realloc (dest->elems, int, new_alloc);
1131       if (BE (new_buffer == NULL, 0))
1132         return REG_ESPACE;
1133       dest->elems = new_buffer;
1134       dest->alloc = new_alloc;
1135     }
1136
1137   if (BE (dest->nelem == 0, 0))
1138     {
1139       dest->nelem = src->nelem;
1140       memcpy (dest->elems, src->elems, src->nelem * sizeof (int));
1141       return REG_NOERROR;
1142     }
1143
1144   /* Copy into the top of DEST the items of SRC that are not
1145      found in DEST.  Maybe we could binary search in DEST?  */
1146   for (sbase = dest->nelem + 2 * src->nelem,
1147        is = src->nelem - 1, id = dest->nelem - 1; is >= 0 && id >= 0; )
1148     {
1149       if (dest->elems[id] == src->elems[is])
1150         is--, id--;
1151       else if (dest->elems[id] < src->elems[is])
1152         dest->elems[--sbase] = src->elems[is--];
1153       else /* if (dest->elems[id] > src->elems[is]) */
1154         --id;
1155     }
1156
1157   if (is >= 0)
1158     {
1159       /* If DEST is exhausted, the remaining items of SRC must be unique.  */
1160       sbase -= is + 1;
1161       memcpy (dest->elems + sbase, src->elems, (is + 1) * sizeof (int));
1162     }
1163
1164   id = dest->nelem - 1;
1165   is = dest->nelem + 2 * src->nelem - 1;
1166   delta = is - sbase + 1;
1167   if (delta == 0)
1168     return REG_NOERROR;
1169
1170   /* Now copy.  When DELTA becomes zero, the remaining
1171      DEST elements are already in place.  */
1172   dest->nelem += delta;
1173   for (;;)
1174     {
1175       if (dest->elems[is] > dest->elems[id])
1176         {
1177           /* Copy from the top.  */
1178           dest->elems[id + delta--] = dest->elems[is--];
1179           if (delta == 0)
1180             break;
1181         }
1182       else
1183         {
1184           /* Slide from the bottom.  */
1185           dest->elems[id + delta] = dest->elems[id];
1186           if (--id < 0)
1187             {
1188               /* Copy remaining SRC elements.  */
1189               memcpy (dest->elems, dest->elems + sbase,
1190                       delta * sizeof (int));
1191               break;
1192             }
1193         }
1194     }
1195
1196   return REG_NOERROR;
1197 }
1198
1199 /* Insert the new element ELEM to the re_node_set* SET.
1200    SET should not already have ELEM.
1201    return -1 if an error is occured, return 1 otherwise.  */
1202
1203 static int
1204 re_node_set_insert (set, elem)
1205      re_node_set *set;
1206      int elem;
1207 {
1208   int idx;
1209   /* In case the set is empty.  */
1210   if (set->alloc == 0)
1211     {
1212       if (BE (re_node_set_init_1 (set, elem) == REG_NOERROR, 1))
1213         return 1;
1214       else
1215         return -1;
1216     }
1217
1218   if (BE (set->nelem, 0) == 0)
1219     {
1220       /* We already guaranteed above that set->alloc != 0.  */
1221       set->elems[0] = elem;
1222       ++set->nelem;
1223       return 1;
1224     }
1225
1226   /* Realloc if we need.  */
1227   if (set->alloc == set->nelem)
1228     {
1229       int *new_elems;
1230       set->alloc = set->alloc * 2;
1231       new_elems = re_realloc (set->elems, int, set->alloc);
1232       if (BE (new_elems == NULL, 0))
1233         return -1;
1234       set->elems = new_elems;
1235     }
1236
1237   /* Move the elements which follows the new element.  Test the
1238      first element separately to skip a check in the inner loop.  */
1239   if (elem < set->elems[0])
1240     {
1241       idx = 0;
1242       for (idx = set->nelem; idx > 0; idx--)
1243         set->elems[idx] = set->elems[idx - 1];
1244     }
1245   else
1246     {
1247       for (idx = set->nelem; set->elems[idx - 1] > elem; idx--)
1248         set->elems[idx] = set->elems[idx - 1];
1249     }
1250
1251   /* Insert the new element.  */
1252   set->elems[idx] = elem;
1253   ++set->nelem;
1254   return 1;
1255 }
1256
1257 /* Insert the new element ELEM to the re_node_set* SET.
1258    SET should not already have any element greater than or equal to ELEM.
1259    Return -1 if an error is occured, return 1 otherwise.  */
1260
1261 static int
1262 re_node_set_insert_last (set, elem)
1263      re_node_set *set;
1264      int elem;
1265 {
1266   /* Realloc if we need.  */
1267   if (set->alloc == set->nelem)
1268     {
1269       int *new_elems;
1270       set->alloc = (set->alloc + 1) * 2;
1271       new_elems = re_realloc (set->elems, int, set->alloc);
1272       if (BE (new_elems == NULL, 0))
1273         return -1;
1274       set->elems = new_elems;
1275     }
1276
1277   /* Insert the new element.  */
1278   set->elems[set->nelem++] = elem;
1279   return 1;
1280 }
1281
1282 /* Compare two node sets SET1 and SET2.
1283    return 1 if SET1 and SET2 are equivalent, return 0 otherwise.  */
1284
1285 static int
1286 re_node_set_compare (set1, set2)
1287      const re_node_set *set1, *set2;
1288 {
1289   int i;
1290   if (set1 == NULL || set2 == NULL || set1->nelem != set2->nelem)
1291     return 0;
1292   for (i = set1->nelem ; --i >= 0 ; )
1293     if (set1->elems[i] != set2->elems[i])
1294       return 0;
1295   return 1;
1296 }
1297
1298 /* Return (idx + 1) if SET contains the element ELEM, return 0 otherwise.  */
1299
1300 static int
1301 re_node_set_contains (set, elem)
1302      const re_node_set *set;
1303      int elem;
1304 {
1305   unsigned int idx, right, mid;
1306   if (set->nelem <= 0)
1307     return 0;
1308
1309   /* Binary search the element.  */
1310   idx = 0;
1311   right = set->nelem - 1;
1312   while (idx < right)
1313     {
1314       mid = (idx + right) / 2;
1315       if (set->elems[mid] < elem)
1316         idx = mid + 1;
1317       else
1318         right = mid;
1319     }
1320   return set->elems[idx] == elem ? idx + 1 : 0;
1321 }
1322
1323 static void
1324 re_node_set_remove_at (set, idx)
1325      re_node_set *set;
1326      int idx;
1327 {
1328   if (idx < 0 || idx >= set->nelem)
1329     return;
1330   --set->nelem;
1331   for (; idx < set->nelem; idx++)
1332     set->elems[idx] = set->elems[idx + 1];
1333 }
1334 \f
1335
1336 /* Add the token TOKEN to dfa->nodes, and return the index of the token.
1337    Or return -1, if an error will be occured.  */
1338
1339 static int
1340 re_dfa_add_node (dfa, token)
1341      re_dfa_t *dfa;
1342      re_token_t token;
1343 {
1344   int type = token.type;
1345   if (BE (dfa->nodes_len >= dfa->nodes_alloc, 0))
1346     {
1347       int new_nodes_alloc = dfa->nodes_alloc * 2;
1348       int *new_nexts, *new_indices;
1349       re_node_set *new_edests, *new_eclosures;
1350
1351       re_token_t *new_nodes = re_realloc (dfa->nodes, re_token_t,
1352                                           new_nodes_alloc);
1353       if (BE (new_nodes == NULL, 0))
1354         return -1;
1355       dfa->nodes = new_nodes;
1356       new_nexts = re_realloc (dfa->nexts, int, new_nodes_alloc);
1357       new_indices = re_realloc (dfa->org_indices, int, new_nodes_alloc);
1358       new_edests = re_realloc (dfa->edests, re_node_set, new_nodes_alloc);
1359       new_eclosures = re_realloc (dfa->eclosures, re_node_set, new_nodes_alloc);
1360       if (BE (new_nexts == NULL || new_indices == NULL
1361               || new_edests == NULL || new_eclosures == NULL, 0))
1362         return -1;
1363       dfa->nexts = new_nexts;
1364       dfa->org_indices = new_indices;
1365       dfa->edests = new_edests;
1366       dfa->eclosures = new_eclosures;
1367       dfa->nodes_alloc = new_nodes_alloc;
1368     }
1369   dfa->nodes[dfa->nodes_len] = token;
1370   dfa->nodes[dfa->nodes_len].constraint = 0;
1371 #ifdef RE_ENABLE_I18N
1372   dfa->nodes[dfa->nodes_len].accept_mb =
1373     (type == OP_PERIOD && dfa->mb_cur_max > 1) || type == COMPLEX_BRACKET;
1374 #endif
1375   dfa->nexts[dfa->nodes_len] = -1;
1376   re_node_set_init_empty (dfa->edests + dfa->nodes_len);
1377   re_node_set_init_empty (dfa->eclosures + dfa->nodes_len);
1378   return dfa->nodes_len++;
1379 }
1380
1381 static unsigned int inline
1382 calc_state_hash (nodes, context)
1383      const re_node_set *nodes;
1384      unsigned int context;
1385 {
1386   unsigned int hash = nodes->nelem + context;
1387   int i;
1388   for (i = 0 ; i < nodes->nelem ; i++)
1389     hash += nodes->elems[i];
1390   return hash;
1391 }
1392
1393 /* Search for the state whose node_set is equivalent to NODES.
1394    Return the pointer to the state, if we found it in the DFA.
1395    Otherwise create the new one and return it.  In case of an error
1396    return NULL and set the error code in ERR.
1397    Note: - We assume NULL as the invalid state, then it is possible that
1398            return value is NULL and ERR is REG_NOERROR.
1399          - We never return non-NULL value in case of any errors, it is for
1400            optimization.  */
1401
1402 static re_dfastate_t*
1403 re_acquire_state (err, dfa, nodes)
1404      reg_errcode_t *err;
1405      re_dfa_t *dfa;
1406      const re_node_set *nodes;
1407 {
1408   unsigned int hash;
1409   re_dfastate_t *new_state;
1410   struct re_state_table_entry *spot;
1411   int i;
1412   if (BE (nodes->nelem == 0, 0))
1413     {
1414       *err = REG_NOERROR;
1415       return NULL;
1416     }
1417   hash = calc_state_hash (nodes, 0);
1418   spot = dfa->state_table + (hash & dfa->state_hash_mask);
1419
1420   for (i = 0 ; i < spot->num ; i++)
1421     {
1422       re_dfastate_t *state = spot->array[i];
1423       if (hash != state->hash)
1424         continue;
1425       if (re_node_set_compare (&state->nodes, nodes))
1426         return state;
1427     }
1428
1429   /* There are no appropriate state in the dfa, create the new one.  */
1430   new_state = create_ci_newstate (dfa, nodes, hash);
1431   if (BE (new_state != NULL, 1))
1432     return new_state;
1433   else
1434     {
1435       *err = REG_ESPACE;
1436       return NULL;
1437     }
1438 }
1439
1440 /* Search for the state whose node_set is equivalent to NODES and
1441    whose context is equivalent to CONTEXT.
1442    Return the pointer to the state, if we found it in the DFA.
1443    Otherwise create the new one and return it.  In case of an error
1444    return NULL and set the error code in ERR.
1445    Note: - We assume NULL as the invalid state, then it is possible that
1446            return value is NULL and ERR is REG_NOERROR.
1447          - We never return non-NULL value in case of any errors, it is for
1448            optimization.  */
1449
1450 static re_dfastate_t*
1451 re_acquire_state_context (err, dfa, nodes, context)
1452      reg_errcode_t *err;
1453      re_dfa_t *dfa;
1454      const re_node_set *nodes;
1455      unsigned int context;
1456 {
1457   unsigned int hash;
1458   re_dfastate_t *new_state;
1459   struct re_state_table_entry *spot;
1460   int i;
1461   if (nodes->nelem == 0)
1462     {
1463       *err = REG_NOERROR;
1464       return NULL;
1465     }
1466   hash = calc_state_hash (nodes, context);
1467   spot = dfa->state_table + (hash & dfa->state_hash_mask);
1468
1469   for (i = 0 ; i < spot->num ; i++)
1470     {
1471       re_dfastate_t *state = spot->array[i];
1472       if (state->hash == hash
1473           && state->context == context
1474           && re_node_set_compare (state->entrance_nodes, nodes))
1475         return state;
1476     }
1477   /* There are no appropriate state in `dfa', create the new one.  */
1478   new_state = create_cd_newstate (dfa, nodes, context, hash);
1479   if (BE (new_state != NULL, 1))
1480     return new_state;
1481   else
1482     {
1483       *err = REG_ESPACE;
1484       return NULL;
1485     }
1486 }
1487
1488 /* Finish initialization of the new state NEWSTATE, and using its hash value
1489    HASH put in the appropriate bucket of DFA's state table.  Return value
1490    indicates the error code if failed.  */
1491
1492 static reg_errcode_t
1493 register_state (dfa, newstate, hash)
1494      re_dfa_t *dfa;
1495      re_dfastate_t *newstate;
1496      unsigned int hash;
1497 {
1498   struct re_state_table_entry *spot;
1499   reg_errcode_t err;
1500   int i;
1501
1502   newstate->hash = hash;
1503   err = re_node_set_alloc (&newstate->non_eps_nodes, newstate->nodes.nelem);
1504   if (BE (err != REG_NOERROR, 0))
1505     return REG_ESPACE;
1506   for (i = 0; i < newstate->nodes.nelem; i++)
1507     {
1508       int elem = newstate->nodes.elems[i];
1509       if (!IS_EPSILON_NODE (dfa->nodes[elem].type))
1510         re_node_set_insert_last (&newstate->non_eps_nodes, elem);
1511     }
1512
1513   spot = dfa->state_table + (hash & dfa->state_hash_mask);
1514   if (BE (spot->alloc <= spot->num, 0))
1515     {
1516       int new_alloc = 2 * spot->num + 2;
1517       re_dfastate_t **new_array = re_realloc (spot->array, re_dfastate_t *,
1518                                               new_alloc);
1519       if (BE (new_array == NULL, 0))
1520         return REG_ESPACE;
1521       spot->array = new_array;
1522       spot->alloc = new_alloc;
1523     }
1524   spot->array[spot->num++] = newstate;
1525   return REG_NOERROR;
1526 }
1527
1528 /* Create the new state which is independ of contexts.
1529    Return the new state if succeeded, otherwise return NULL.  */
1530
1531 static re_dfastate_t *
1532 create_ci_newstate (dfa, nodes, hash)
1533      re_dfa_t *dfa;
1534      const re_node_set *nodes;
1535      unsigned int hash;
1536 {
1537   int i;
1538   reg_errcode_t err;
1539   re_dfastate_t *newstate;
1540
1541   newstate = (re_dfastate_t *) calloc (sizeof (re_dfastate_t), 1);
1542   if (BE (newstate == NULL, 0))
1543     return NULL;
1544   err = re_node_set_init_copy (&newstate->nodes, nodes);
1545   if (BE (err != REG_NOERROR, 0))
1546     {
1547       re_free (newstate);
1548       return NULL;
1549     }
1550
1551   newstate->entrance_nodes = &newstate->nodes;
1552   for (i = 0 ; i < nodes->nelem ; i++)
1553     {
1554       re_token_t *node = dfa->nodes + nodes->elems[i];
1555       re_token_type_t type = node->type;
1556       if (type == CHARACTER && !node->constraint)
1557         continue;
1558 #ifdef RE_ENABLE_I18N
1559       newstate->accept_mb |= node->accept_mb;
1560 #endif /* RE_ENABLE_I18N */
1561
1562       /* If the state has the halt node, the state is a halt state.  */
1563       if (type == END_OF_RE)
1564         newstate->halt = 1;
1565       else if (type == OP_BACK_REF)
1566         newstate->has_backref = 1;
1567       else if (type == ANCHOR || node->constraint)
1568         newstate->has_constraint = 1;
1569     }
1570   err = register_state (dfa, newstate, hash);
1571   if (BE (err != REG_NOERROR, 0))
1572     {
1573       free_state (newstate);
1574       newstate = NULL;
1575     }
1576   return newstate;
1577 }
1578
1579 /* Create the new state which is depend on the context CONTEXT.
1580    Return the new state if succeeded, otherwise return NULL.  */
1581
1582 static re_dfastate_t *
1583 create_cd_newstate (dfa, nodes, context, hash)
1584      re_dfa_t *dfa;
1585      const re_node_set *nodes;
1586      unsigned int context, hash;
1587 {
1588   int i, nctx_nodes = 0;
1589   reg_errcode_t err;
1590   re_dfastate_t *newstate;
1591
1592   newstate = (re_dfastate_t *) calloc (sizeof (re_dfastate_t), 1);
1593   if (BE (newstate == NULL, 0))
1594     return NULL;
1595   err = re_node_set_init_copy (&newstate->nodes, nodes);
1596   if (BE (err != REG_NOERROR, 0))
1597     {
1598       re_free (newstate);
1599       return NULL;
1600     }
1601
1602   newstate->context = context;
1603   newstate->entrance_nodes = &newstate->nodes;
1604
1605   for (i = 0 ; i < nodes->nelem ; i++)
1606     {
1607       unsigned int constraint = 0;
1608       re_token_t *node = dfa->nodes + nodes->elems[i];
1609       re_token_type_t type = node->type;
1610       if (node->constraint)
1611         constraint = node->constraint;
1612
1613       if (type == CHARACTER && !constraint)
1614         continue;
1615 #ifdef RE_ENABLE_I18N
1616       newstate->accept_mb |= node->accept_mb;
1617 #endif /* RE_ENABLE_I18N */
1618
1619       /* If the state has the halt node, the state is a halt state.  */
1620       if (type == END_OF_RE)
1621         newstate->halt = 1;
1622       else if (type == OP_BACK_REF)
1623         newstate->has_backref = 1;
1624       else if (type == ANCHOR)
1625         constraint = node->opr.ctx_type;
1626
1627       if (constraint)
1628         {
1629           if (newstate->entrance_nodes == &newstate->nodes)
1630             {
1631               newstate->entrance_nodes = re_malloc (re_node_set, 1);
1632               if (BE (newstate->entrance_nodes == NULL, 0))
1633                 {
1634                   free_state (newstate);
1635                   return NULL;
1636                 }
1637               re_node_set_init_copy (newstate->entrance_nodes, nodes);
1638               nctx_nodes = 0;
1639               newstate->has_constraint = 1;
1640             }
1641
1642           if (NOT_SATISFY_PREV_CONSTRAINT (constraint,context))
1643             {
1644               re_node_set_remove_at (&newstate->nodes, i - nctx_nodes);
1645               ++nctx_nodes;
1646             }
1647         }
1648     }
1649   err = register_state (dfa, newstate, hash);
1650   if (BE (err != REG_NOERROR, 0))
1651     {
1652       free_state (newstate);
1653       newstate = NULL;
1654     }
1655   return  newstate;
1656 }
1657
1658 static void
1659 free_state (state)
1660      re_dfastate_t *state;
1661 {
1662   re_node_set_free (&state->non_eps_nodes);
1663   re_node_set_free (&state->inveclosure);
1664   if (state->entrance_nodes != &state->nodes)
1665     {
1666       re_node_set_free (state->entrance_nodes);
1667       re_free (state->entrance_nodes);
1668     }
1669   re_node_set_free (&state->nodes);
1670   re_free (state->word_trtable);
1671   re_free (state->trtable);
1672   re_free (state);
1673 }