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