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