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                                         REG_TRANSLATE_TYPE trans, int icase,
  23                                         const re_dfa_t *dfa) internal_function;
  24 static re_dfastate_t *create_ci_newstate (re_dfa_t *dfa,
  25                                           const re_node_set *nodes,
  26                                           unsigned int hash) internal_function;
  27 static re_dfastate_t *create_cd_newstate (re_dfa_t *dfa,
  28                                           const re_node_set *nodes,
  29                                           unsigned int context,
  30                                           unsigned int 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, int len, int init_len,
  40                     REG_TRANSLATE_TYPE trans, int icase, const re_dfa_t *dfa)
  41 {
  42   reg_errcode_t ret;
  43   int 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, int len,
  68                      REG_TRANSLATE_TYPE trans, int 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, int 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           int *new_offsets = re_realloc (pstr->offsets, int, 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, int len, re_string_t *pstr,
 164                             REG_TRANSLATE_TYPE trans, int 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 ? 1 : 0;
 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   int 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 int
 262 internal_function
 263 build_wcs_upper_buffer (re_string_t *pstr)
 264 {
 265   mbstate_t prev_st;
 266   int 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 (int, 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 int
 478 internal_function
 479 re_string_skip_chars (re_string_t *pstr, int new_raw_idx, wint_t *last_wc)
 480 {
 481   mbstate_t prev_st;
 482   int 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       int 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   int 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   int 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, int idx, int eflags)
 559 {
 560   int offset = idx - pstr->raw_mbs_idx;
 561   if (BE (offset < 0, 0))
 562     {
 563       /* Reset buffer.  */
 564 #ifdef RE_ENABLE_I18N
 565       if (pstr->mb_cur_max > 1)
 566         memset (&pstr->cur_state, '\0', sizeof (mbstate_t));
 567 #endif /* RE_ENABLE_I18N */
 568       pstr->len = pstr->raw_len;
 569       pstr->stop = pstr->raw_stop;
 570       pstr->valid_len = 0;
 571       pstr->raw_mbs_idx = 0;
 572       pstr->valid_raw_len = 0;
 573       pstr->offsets_needed = 0;
 574       pstr->tip_context = ((eflags & REG_NOTBOL) ? CONTEXT_BEGBUF
 575                            : CONTEXT_NEWLINE | CONTEXT_BEGBUF);
 576       if (!pstr->mbs_allocated)
 577         pstr->mbs = (unsigned char *) pstr->raw_mbs;
 578       offset = idx;
 579     }
 580
 581   if (BE (offset != 0, 1))
 582     {
 583       /* Are the characters which are already checked remain?  */
 584       if (BE (offset < pstr->valid_raw_len, 1)
 585 #ifdef RE_ENABLE_I18N
 586           /* Handling this would enlarge the code too much.
 587              Accept a slowdown in that case.  */
 588           && pstr->offsets_needed == 0
 589 #endif
 590          )
 591         {
 592           /* Yes, move them to the front of the buffer.  */
 593           pstr->tip_context = re_string_context_at (pstr, offset - 1, eflags);
 594 #ifdef RE_ENABLE_I18N
 595           if (pstr->mb_cur_max > 1)
 596             memmove (pstr->wcs, pstr->wcs + offset,
 597                      (pstr->valid_len - offset) * sizeof (wint_t));
 598 #endif /* RE_ENABLE_I18N */
 599           if (BE (pstr->mbs_allocated, 0))
 600             memmove (pstr->mbs, pstr->mbs + offset,
 601                      pstr->valid_len - offset);
 602           pstr->valid_len -= offset;
 603           pstr->valid_raw_len -= offset;
 604 #if DEBUG
 605           assert (pstr->valid_len > 0);
 606 #endif
 607         }
 608       else
 609         {
 610           /* No, skip all characters until IDX.  */
 611 #ifdef RE_ENABLE_I18N
 612           if (BE (pstr->offsets_needed, 0))
 613             {
 614               pstr->len = pstr->raw_len - idx + offset;
 615               pstr->stop = pstr->raw_stop - idx + offset;
 616               pstr->offsets_needed = 0;
 617             }
 618 #endif
 619           pstr->valid_len = 0;
 620           pstr->valid_raw_len = 0;
 621 #ifdef RE_ENABLE_I18N
 622           if (pstr->mb_cur_max > 1)
 623             {
 624               int wcs_idx;
 625               wint_t wc = WEOF;
 626
 627               if (pstr->is_utf8)
 628                 {
 629                   const unsigned char *raw, *p, *q, *end;
 630
 631                   /* Special case UTF-8.  Multi-byte chars start with any
 632                      byte other than 0x80 - 0xbf.  */
 633                   raw = pstr->raw_mbs + pstr->raw_mbs_idx;
 634                   end = raw + (offset - pstr->mb_cur_max);
 635                   for (p = raw + offset - 1; p >= end; --p)
 636                     if ((*p & 0xc0) != 0x80)
 637                       {
 638                         mbstate_t cur_state;
 639                         wchar_t wc2;
 640                         int mlen = raw + pstr->len - p;
 641                         unsigned char buf[6];
 642
 643                         q = p;
 644                         if (BE (pstr->trans != NULL, 0))
 645                           {
 646                             int i = mlen < 6 ? mlen : 6;
 647                             while (--i >= 0)
 648                               buf[i] = pstr->trans[p[i]];
 649                             q = buf;
 650                           }
 651                         /* XXX Don't use mbrtowc, we know which conversion
 652                            to use (UTF-8 -> UCS4).  */
 653                         memset (&cur_state, 0, sizeof (cur_state));
 654                         mlen = (mbrtowc (&wc2, (const char *) p, mlen,
 655                                          &cur_state)
 656                                 - (raw + offset - p));
 657                         if (mlen >= 0)
 658                           {
 659                             memset (&pstr->cur_state, '\0',
 660                                     sizeof (mbstate_t));
 661                             pstr->valid_len = mlen;
 662                             wc = wc2;
 663                           }
 664                         break;
 665                       }
 666                 }
 667
 668               if (wc == WEOF)
 669                 pstr->valid_len = re_string_skip_chars (pstr, idx, &wc) - idx;
 670               if (BE (pstr->valid_len, 0))
 671                 {
 672                   for (wcs_idx = 0; wcs_idx < pstr->valid_len; ++wcs_idx)
 673                     pstr->wcs[wcs_idx] = WEOF;
 674                   if (pstr->mbs_allocated)
 675                     memset (pstr->mbs, 255, pstr->valid_len);
 676                 }
 677               pstr->valid_raw_len = pstr->valid_len;
 678               pstr->tip_context = ((BE (pstr->word_ops_used != 0, 0)
 679                                     && IS_WIDE_WORD_CHAR (wc))
 680                                    ? CONTEXT_WORD
 681                                    : ((IS_WIDE_NEWLINE (wc)
 682                                        && pstr->newline_anchor)
 683                                       ? CONTEXT_NEWLINE : 0));
 684             }
 685           else
 686 #endif /* RE_ENABLE_I18N */
 687             {
 688               int c = pstr->raw_mbs[pstr->raw_mbs_idx + offset - 1];
 689               if (pstr->trans)
 690                 c = pstr->trans[c];
 691               pstr->tip_context = (bitset_contain (pstr->word_char, c)
 692                                    ? CONTEXT_WORD
 693                                    : ((IS_NEWLINE (c) && pstr->newline_anchor)
 694                                       ? CONTEXT_NEWLINE : 0));
 695             }
 696         }
 697       if (!BE (pstr->mbs_allocated, 0))
 698         pstr->mbs += offset;
 699     }
 700   pstr->raw_mbs_idx = idx;
 701   pstr->len -= offset;
 702   pstr->stop -= offset;
 703
 704   /* Then build the buffers.  */
 705 #ifdef RE_ENABLE_I18N
 706   if (pstr->mb_cur_max > 1)
 707     {
 708       if (pstr->icase)
 709         {
 710           int ret = build_wcs_upper_buffer (pstr);
 711           if (BE (ret != REG_NOERROR, 0))
 712             return ret;
 713         }
 714       else
 715         build_wcs_buffer (pstr);
 716     }
 717   else
 718 #endif /* RE_ENABLE_I18N */
 719   if (BE (pstr->mbs_allocated, 0))
 720     {
 721       if (pstr->icase)
 722         build_upper_buffer (pstr);
 723       else if (pstr->trans != NULL)
 724         re_string_translate_buffer (pstr);
 725     }
 726   else
 727     pstr->valid_len = pstr->len;
 728
 729   pstr->cur_idx = 0;
 730   return REG_NOERROR;
 731 }
 732
 733 static unsigned char
 734 internal_function
 735 re_string_peek_byte_case (const re_string_t *pstr, int idx)
 736 {
 737   int ch, off;
 738
 739   /* Handle the common (easiest) cases first.  */
 740   if (BE (!pstr->mbs_allocated, 1))
 741     return re_string_peek_byte (pstr, idx);
 742
 743 #ifdef RE_ENABLE_I18N
 744   if (pstr->mb_cur_max > 1
 745       && ! re_string_is_single_byte_char (pstr, pstr->cur_idx + idx))
 746     return re_string_peek_byte (pstr, idx);
 747 #endif
 748
 749   off = pstr->cur_idx + idx;
 750 #ifdef RE_ENABLE_I18N
 751   if (pstr->offsets_needed)
 752     off = pstr->offsets[off];
 753 #endif
 754
 755   ch = pstr->raw_mbs[pstr->raw_mbs_idx + off];
 756
 757 #ifdef RE_ENABLE_I18N
 758   /* Ensure that e.g. for tr_TR.UTF-8 BACKSLASH DOTLESS SMALL LETTER I
 759      this function returns CAPITAL LETTER I instead of first byte of
 760      DOTLESS SMALL LETTER I.  The latter would confuse the parser,
 761      since peek_byte_case doesn't advance cur_idx in any way.  */
 762   if (pstr->offsets_needed && !isascii (ch))
 763     return re_string_peek_byte (pstr, idx);
 764 #endif
 765
 766   return ch;
 767 }
 768
 769 static unsigned char
 770 internal_function
 771 re_string_fetch_byte_case (re_string_t *pstr)
 772 {
 773   if (BE (!pstr->mbs_allocated, 1))
 774     return re_string_fetch_byte (pstr);
 775
 776 #ifdef RE_ENABLE_I18N
 777   if (pstr->offsets_needed)
 778     {
 779       int off, ch;
 780
 781       /* For tr_TR.UTF-8 [[:islower:]] there is
 782          [[: CAPITAL LETTER I WITH DOT lower:]] in mbs.  Skip
 783          in that case the whole multi-byte character and return
 784          the original letter.  On the other side, with
 785          [[: DOTLESS SMALL LETTER I return [[:I, as doing
 786          anything else would complicate things too much.  */
 787
 788       if (!re_string_first_byte (pstr, pstr->cur_idx))
 789         return re_string_fetch_byte (pstr);
 790
 791       off = pstr->offsets[pstr->cur_idx];
 792       ch = pstr->raw_mbs[pstr->raw_mbs_idx + off];
 793
 794       if (! isascii (ch))
 795         return re_string_fetch_byte (pstr);
 796
 797       re_string_skip_bytes (pstr,
 798                             re_string_char_size_at (pstr, pstr->cur_idx));
 799       return ch;
 800     }
 801 #endif
 802
 803   return pstr->raw_mbs[pstr->raw_mbs_idx + pstr->cur_idx++];
 804 }
 805
 806 static void
 807 internal_function
 808 re_string_destruct (re_string_t *pstr)
 809 {
 810 #ifdef RE_ENABLE_I18N
 811   re_free (pstr->wcs);
 812   re_free (pstr->offsets);
 813 #endif /* RE_ENABLE_I18N  */
 814   if (pstr->mbs_allocated)
 815     re_free (pstr->mbs);
 816 }
 817
 818 /* Return the context at IDX in INPUT.  */
 819
 820 static unsigned int
 821 internal_function
 822 re_string_context_at (const re_string_t *input, int idx, int eflags)
 823 {
 824   int c;
 825   if (BE (idx < 0, 0))
 826     /* In this case, we use the value stored in input->tip_context,
 827        since we can't know the character in input->mbs[-1] here.  */
 828     return input->tip_context;
 829   if (BE (idx == input->len, 0))
 830     return ((eflags & REG_NOTEOL) ? CONTEXT_ENDBUF
 831             : CONTEXT_NEWLINE | CONTEXT_ENDBUF);
 832 #ifdef RE_ENABLE_I18N
 833   if (input->mb_cur_max > 1)
 834     {
 835       wint_t wc;
 836       int wc_idx = idx;
 837       while(input->wcs[wc_idx] == WEOF)
 838         {
 839 #ifdef DEBUG
 840           /* It must not happen.  */
 841           assert (wc_idx >= 0);
 842 #endif
 843           --wc_idx;
 844           if (wc_idx < 0)
 845             return input->tip_context;
 846         }
 847       wc = input->wcs[wc_idx];
 848       if (BE (input->word_ops_used != 0, 0) && IS_WIDE_WORD_CHAR (wc))
 849         return CONTEXT_WORD;
 850       return (IS_WIDE_NEWLINE (wc) && input->newline_anchor
 851               ? CONTEXT_NEWLINE : 0);
 852     }
 853   else
 854 #endif
 855     {
 856       c = re_string_byte_at (input, idx);
 857       if (bitset_contain (input->word_char, c))
 858         return CONTEXT_WORD;
 859       return IS_NEWLINE (c) && input->newline_anchor ? CONTEXT_NEWLINE : 0;
 860     }
 861 }
 862 \f
 863 /* Functions for set operation.  */
 864
 865 static reg_errcode_t
 866 internal_function
 867 re_node_set_alloc (re_node_set *set, int size)
 868 {
 869   set->alloc = size;
 870   set->nelem = 0;
 871   set->elems = re_malloc (int, size);
 872   if (BE (set->elems == NULL, 0))
 873     return REG_ESPACE;
 874   return REG_NOERROR;
 875 }
 876
 877 static reg_errcode_t
 878 internal_function
 879 re_node_set_init_1 (re_node_set *set, int elem)
 880 {
 881   set->alloc = 1;
 882   set->nelem = 1;
 883   set->elems = re_malloc (int, 1);
 884   if (BE (set->elems == NULL, 0))
 885     {
 886       set->alloc = set->nelem = 0;
 887       return REG_ESPACE;
 888     }
 889   set->elems[0] = elem;
 890   return REG_NOERROR;
 891 }
 892
 893 static reg_errcode_t
 894 internal_function
 895 re_node_set_init_2 (re_node_set *set, int elem1, int elem2)
 896 {
 897   set->alloc = 2;
 898   set->elems = re_malloc (int, 2);
 899   if (BE (set->elems == NULL, 0))
 900     return REG_ESPACE;
 901   if (elem1 == elem2)
 902     {
 903       set->nelem = 1;
 904       set->elems[0] = elem1;
 905     }
 906   else
 907     {
 908       set->nelem = 2;
 909       if (elem1 < elem2)
 910         {
 911           set->elems[0] = elem1;
 912           set->elems[1] = elem2;
 913         }
 914       else
 915         {
 916           set->elems[0] = elem2;
 917           set->elems[1] = elem1;
 918         }
 919     }
 920   return REG_NOERROR;
 921 }
 922
 923 static reg_errcode_t
 924 internal_function
 925 re_node_set_init_copy (re_node_set *dest, const re_node_set *src)
 926 {
 927   dest->nelem = src->nelem;
 928   if (src->nelem > 0)
 929     {
 930       dest->alloc = dest->nelem;
 931       dest->elems = re_malloc (int, dest->alloc);
 932       if (BE (dest->elems == NULL, 0))
 933         {
 934           dest->alloc = dest->nelem = 0;
 935           return REG_ESPACE;
 936         }
 937       memcpy (dest->elems, src->elems, src->nelem * sizeof (int));
 938     }
 939   else
 940     re_node_set_init_empty (dest);
 941   return REG_NOERROR;
 942 }
 943
 944 /* Calculate the intersection of the sets SRC1 and SRC2. And merge it to
 945    DEST. Return value indicate the error code or REG_NOERROR if succeeded.
 946    Note: We assume dest->elems is NULL, when dest->alloc is 0.  */
 947
 948 static reg_errcode_t
 949 internal_function
 950 re_node_set_add_intersect (re_node_set *dest, const re_node_set *src1,
 951                            const re_node_set *src2)
 952 {
 953   int i1, i2, is, id, delta, sbase;
 954   if (src1->nelem == 0 || src2->nelem == 0)
 955     return REG_NOERROR;
 956
 957   /* We need dest->nelem + 2 * elems_in_intersection; this is a
 958      conservative estimate.  */
 959   if (src1->nelem + src2->nelem + dest->nelem > dest->alloc)
 960     {
 961       int new_alloc = src1->nelem + src2->nelem + dest->alloc;
 962       int *new_elems = re_realloc (dest->elems, int, new_alloc);
 963       if (BE (new_elems == NULL, 0))
 964         return REG_ESPACE;
 965       dest->elems = new_elems;
 966       dest->alloc = new_alloc;
 967     }
 968
 969   /* Find the items in the intersection of SRC1 and SRC2, and copy
 970      into the top of DEST those that are not already in DEST itself.  */
 971   sbase = dest->nelem + src1->nelem + src2->nelem;
 972   i1 = src1->nelem - 1;
 973   i2 = src2->nelem - 1;
 974   id = dest->nelem - 1;
 975   for (;;)
 976     {
 977       if (src1->elems[i1] == src2->elems[i2])
 978         {
 979           /* Try to find the item in DEST.  Maybe we could binary search?  */
 980           while (id >= 0 && dest->elems[id] > src1->elems[i1])
 981             --id;
 982
 983           if (id < 0 || dest->elems[id] != src1->elems[i1])
 984             dest->elems[--sbase] = src1->elems[i1];
 985
 986           if (--i1 < 0 || --i2 < 0)
 987             break;
 988         }
 989
 990       /* Lower the highest of the two items.  */
 991       else if (src1->elems[i1] < src2->elems[i2])
 992         {
 993           if (--i2 < 0)
 994             break;
 995         }
 996       else
 997         {
 998           if (--i1 < 0)
 999             break;
1000         }
1001     }
1002
1003   id = dest->nelem - 1;
1004   is = dest->nelem + src1->nelem + src2->nelem - 1;
1005   delta = is - sbase + 1;
1006
1007   /* Now copy.  When DELTA becomes zero, the remaining
1008      DEST elements are already in place; this is more or
1009      less the same loop that is in re_node_set_merge.  */
1010   dest->nelem += delta;
1011   if (delta > 0 && id >= 0)
1012     for (;;)
1013       {
1014         if (dest->elems[is] > dest->elems[id])
1015           {
1016             /* Copy from the top.  */
1017             dest->elems[id + delta--] = dest->elems[is--];
1018             if (delta == 0)
1019               break;
1020           }
1021         else
1022           {
1023             /* Slide from the bottom.  */
1024             dest->elems[id + delta] = dest->elems[id];
1025             if (--id < 0)
1026               break;
1027           }
1028       }
1029
1030   /* Copy remaining SRC elements.  */
1031   memcpy (dest->elems, dest->elems + sbase, delta * sizeof (int));
1032
1033   return REG_NOERROR;
1034 }
1035
1036 /* Calculate the union set of the sets SRC1 and SRC2. And store it to
1037    DEST. Return value indicate the error code or REG_NOERROR if succeeded.  */
1038
1039 static reg_errcode_t
1040 internal_function
1041 re_node_set_init_union (re_node_set *dest, const re_node_set *src1,
1042                         const re_node_set *src2)
1043 {
1044   int i1, i2, id;
1045   if (src1 != NULL && src1->nelem > 0 && src2 != NULL && src2->nelem > 0)
1046     {
1047       dest->alloc = src1->nelem + src2->nelem;
1048       dest->elems = re_malloc (int, dest->alloc);
1049       if (BE (dest->elems == NULL, 0))
1050         return REG_ESPACE;
1051     }
1052   else
1053     {
1054       if (src1 != NULL && src1->nelem > 0)
1055         return re_node_set_init_copy (dest, src1);
1056       else if (src2 != NULL && src2->nelem > 0)
1057         return re_node_set_init_copy (dest, src2);
1058       else
1059         re_node_set_init_empty (dest);
1060       return REG_NOERROR;
1061     }
1062   for (i1 = i2 = id = 0 ; i1 < src1->nelem && i2 < src2->nelem ;)
1063     {
1064       if (src1->elems[i1] > src2->elems[i2])
1065         {
1066           dest->elems[id++] = src2->elems[i2++];
1067           continue;
1068         }
1069       if (src1->elems[i1] == src2->elems[i2])
1070         ++i2;
1071       dest->elems[id++] = src1->elems[i1++];
1072     }
1073   if (i1 < src1->nelem)
1074     {
1075       memcpy (dest->elems + id, src1->elems + i1,
1076              (src1->nelem - i1) * sizeof (int));
1077       id += src1->nelem - i1;
1078     }
1079   else if (i2 < src2->nelem)
1080     {
1081       memcpy (dest->elems + id, src2->elems + i2,
1082              (src2->nelem - i2) * sizeof (int));
1083       id += src2->nelem - i2;
1084     }
1085   dest->nelem = id;
1086   return REG_NOERROR;
1087 }
1088
1089 /* Calculate the union set of the sets DEST and SRC. And store it to
1090    DEST. Return value indicate the error code or REG_NOERROR if succeeded.  */
1091
1092 static reg_errcode_t
1093 internal_function
1094 re_node_set_merge (re_node_set *dest, const re_node_set *src)
1095 {
1096   int is, id, sbase, delta;
1097   if (src == NULL || src->nelem == 0)
1098     return REG_NOERROR;
1099   if (dest->alloc < 2 * src->nelem + dest->nelem)
1100     {
1101       int new_alloc = 2 * (src->nelem + dest->alloc);
1102       int *new_buffer = re_realloc (dest->elems, int, new_alloc);
1103       if (BE (new_buffer == NULL, 0))
1104         return REG_ESPACE;
1105       dest->elems = new_buffer;
1106       dest->alloc = new_alloc;
1107     }
1108
1109   if (BE (dest->nelem == 0, 0))
1110     {
1111       dest->nelem = src->nelem;
1112       memcpy (dest->elems, src->elems, src->nelem * sizeof (int));
1113       return REG_NOERROR;
1114     }
1115
1116   /* Copy into the top of DEST the items of SRC that are not
1117      found in DEST.  Maybe we could binary search in DEST?  */
1118   for (sbase = dest->nelem + 2 * src->nelem,
1119        is = src->nelem - 1, id = dest->nelem - 1; is >= 0 && id >= 0; )
1120     {
1121       if (dest->elems[id] == src->elems[is])
1122         is--, id--;
1123       else if (dest->elems[id] < src->elems[is])
1124         dest->elems[--sbase] = src->elems[is--];
1125       else /* if (dest->elems[id] > src->elems[is]) */
1126         --id;
1127     }
1128
1129   if (is >= 0)
1130     {
1131       /* If DEST is exhausted, the remaining items of SRC must be unique.  */
1132       sbase -= is + 1;
1133       memcpy (dest->elems + sbase, src->elems, (is + 1) * sizeof (int));
1134     }
1135
1136   id = dest->nelem - 1;
1137   is = dest->nelem + 2 * src->nelem - 1;
1138   delta = is - sbase + 1;
1139   if (delta == 0)
1140     return REG_NOERROR;
1141
1142   /* Now copy.  When DELTA becomes zero, the remaining
1143      DEST elements are already in place.  */
1144   dest->nelem += delta;
1145   for (;;)
1146     {
1147       if (dest->elems[is] > dest->elems[id])
1148         {
1149           /* Copy from the top.  */
1150           dest->elems[id + delta--] = dest->elems[is--];
1151           if (delta == 0)
1152             break;
1153         }
1154       else
1155         {
1156           /* Slide from the bottom.  */
1157           dest->elems[id + delta] = dest->elems[id];
1158           if (--id < 0)
1159             {
1160               /* Copy remaining SRC elements.  */
1161               memcpy (dest->elems, dest->elems + sbase,
1162                       delta * sizeof (int));
1163               break;
1164             }
1165         }
1166     }
1167
1168   return REG_NOERROR;
1169 }
1170
1171 /* Insert the new element ELEM to the re_node_set* SET.
1172    SET should not already have ELEM.
1173    return -1 if an error is occured, return 1 otherwise.  */
1174
1175 static int
1176 internal_function
1177 re_node_set_insert (re_node_set *set, int elem)
1178 {
1179   int idx;
1180   /* In case the set is empty.  */
1181   if (set->alloc == 0)
1182     {
1183       if (BE (re_node_set_init_1 (set, elem) == REG_NOERROR, 1))
1184         return 1;
1185       else
1186         return -1;
1187     }
1188
1189   if (BE (set->nelem, 0) == 0)
1190     {
1191       /* We already guaranteed above that set->alloc != 0.  */
1192       set->elems[0] = elem;
1193       ++set->nelem;
1194       return 1;
1195     }
1196
1197   /* Realloc if we need.  */
1198   if (set->alloc == set->nelem)
1199     {
1200       int *new_elems;
1201       set->alloc = set->alloc * 2;
1202       new_elems = re_realloc (set->elems, int, set->alloc);
1203       if (BE (new_elems == NULL, 0))
1204         return -1;
1205       set->elems = new_elems;
1206     }
1207
1208   /* Move the elements which follows the new element.  Test the
1209      first element separately to skip a check in the inner loop.  */
1210   if (elem < set->elems[0])
1211     {
1212       idx = 0;
1213       for (idx = set->nelem; idx > 0; idx--)
1214         set->elems[idx] = set->elems[idx - 1];
1215     }
1216   else
1217     {
1218       for (idx = set->nelem; set->elems[idx - 1] > elem; idx--)
1219         set->elems[idx] = set->elems[idx - 1];
1220     }
1221
1222   /* Insert the new element.  */
1223   set->elems[idx] = elem;
1224   ++set->nelem;
1225   return 1;
1226 }
1227
1228 /* Insert the new element ELEM to the re_node_set* SET.
1229    SET should not already have any element greater than or equal to ELEM.
1230    Return -1 if an error is occured, return 1 otherwise.  */
1231
1232 static int
1233 internal_function
1234 re_node_set_insert_last (re_node_set *set, int elem)
1235 {
1236   /* Realloc if we need.  */
1237   if (set->alloc == set->nelem)
1238     {
1239       int *new_elems;
1240       set->alloc = (set->alloc + 1) * 2;
1241       new_elems = re_realloc (set->elems, int, set->alloc);
1242       if (BE (new_elems == NULL, 0))
1243         return -1;
1244       set->elems = new_elems;
1245     }
1246
1247   /* Insert the new element.  */
1248   set->elems[set->nelem++] = elem;
1249   return 1;
1250 }
1251
1252 /* Compare two node sets SET1 and SET2.
1253    return 1 if SET1 and SET2 are equivalent, return 0 otherwise.  */
1254
1255 static int
1256 internal_function
1257 re_node_set_compare (const re_node_set *set1, const re_node_set *set2)
1258 {
1259   int i;
1260   if (set1 == NULL || set2 == NULL || set1->nelem != set2->nelem)
1261     return 0;
1262   for (i = set1->nelem ; --i >= 0 ; )
1263     if (set1->elems[i] != set2->elems[i])
1264       return 0;
1265   return 1;
1266 }
1267
1268 /* Return (idx + 1) if SET contains the element ELEM, return 0 otherwise.  */
1269
1270 static int
1271 internal_function
1272 re_node_set_contains (const re_node_set *set, int elem)
1273 {
1274   unsigned int idx, right, mid;
1275   if (set->nelem <= 0)
1276     return 0;
1277
1278   /* Binary search the element.  */
1279   idx = 0;
1280   right = set->nelem - 1;
1281   while (idx < right)
1282     {
1283       mid = (idx + right) / 2;
1284       if (set->elems[mid] < elem)
1285         idx = mid + 1;
1286       else
1287         right = mid;
1288     }
1289   return set->elems[idx] == elem ? idx + 1 : 0;
1290 }
1291
1292 static void
1293 internal_function
1294 re_node_set_remove_at (re_node_set *set, int idx)
1295 {
1296   if (idx < 0 || idx >= set->nelem)
1297     return;
1298   --set->nelem;
1299   for (; idx < set->nelem; idx++)
1300     set->elems[idx] = set->elems[idx + 1];
1301 }
1302 \f
1303
1304 /* Add the token TOKEN to dfa->nodes, and return the index of the token.
1305    Or return -1, if an error will be occured.  */
1306
1307 static int
1308 internal_function
1309 re_dfa_add_node (re_dfa_t *dfa, re_token_t token)
1310 {
1311   int type = token.type;
1312   if (BE (dfa->nodes_len >= dfa->nodes_alloc, 0))
1313     {
1314       int new_nodes_alloc = dfa->nodes_alloc * 2;
1315       int *new_nexts, *new_indices;
1316       re_node_set *new_edests, *new_eclosures;
1317
1318       re_token_t *new_nodes = re_realloc (dfa->nodes, re_token_t,
1319                                           new_nodes_alloc);
1320       if (BE (new_nodes == NULL, 0))
1321         return -1;
1322       dfa->nodes = new_nodes;
1323       new_nexts = re_realloc (dfa->nexts, int, new_nodes_alloc);
1324       new_indices = re_realloc (dfa->org_indices, int, new_nodes_alloc);
1325       new_edests = re_realloc (dfa->edests, re_node_set, new_nodes_alloc);
1326       new_eclosures = re_realloc (dfa->eclosures, re_node_set, new_nodes_alloc);
1327       if (BE (new_nexts == NULL || new_indices == NULL
1328               || new_edests == NULL || new_eclosures == NULL, 0))
1329         return -1;
1330       dfa->nexts = new_nexts;
1331       dfa->org_indices = new_indices;
1332       dfa->edests = new_edests;
1333       dfa->eclosures = new_eclosures;
1334       dfa->nodes_alloc = new_nodes_alloc;
1335     }
1336   dfa->nodes[dfa->nodes_len] = token;
1337   dfa->nodes[dfa->nodes_len].constraint = 0;
1338 #ifdef RE_ENABLE_I18N
1339   dfa->nodes[dfa->nodes_len].accept_mb =
1340     (type == OP_PERIOD && dfa->mb_cur_max > 1) || type == COMPLEX_BRACKET;
1341 #endif
1342   dfa->nexts[dfa->nodes_len] = -1;
1343   re_node_set_init_empty (dfa->edests + dfa->nodes_len);
1344   re_node_set_init_empty (dfa->eclosures + dfa->nodes_len);
1345   return dfa->nodes_len++;
1346 }
1347
1348 static inline unsigned int
1349 internal_function
1350 calc_state_hash (const re_node_set *nodes, unsigned int context)
1351 {
1352   unsigned int hash = nodes->nelem + context;
1353   int i;
1354   for (i = 0 ; i < nodes->nelem ; i++)
1355     hash += nodes->elems[i];
1356   return hash;
1357 }
1358
1359 /* Search for the state whose node_set is equivalent to NODES.
1360    Return the pointer to the state, if we found it in the DFA.
1361    Otherwise create the new one and return it.  In case of an error
1362    return NULL and set the error code in ERR.
1363    Note: - We assume NULL as the invalid state, then it is possible that
1364            return value is NULL and ERR is REG_NOERROR.
1365          - We never return non-NULL value in case of any errors, it is for
1366            optimization.  */
1367
1368 static re_dfastate_t*
1369 internal_function
1370 re_acquire_state (reg_errcode_t *err, re_dfa_t *dfa, const re_node_set *nodes)
1371 {
1372   unsigned int hash;
1373   re_dfastate_t *new_state;
1374   struct re_state_table_entry *spot;
1375   int i;
1376 #ifdef lint
1377   /* Suppress bogus uninitialized-variable warnings.  */
1378   *err = REG_NOERROR;
1379 #endif
1380   if (BE (nodes->nelem == 0, 0))
1381     {
1382       *err = REG_NOERROR;
1383       return NULL;
1384     }
1385   hash = calc_state_hash (nodes, 0);
1386   spot = dfa->state_table + (hash & dfa->state_hash_mask);
1387
1388   for (i = 0 ; i < spot->num ; i++)
1389     {
1390       re_dfastate_t *state = spot->array[i];
1391       if (hash != state->hash)
1392         continue;
1393       if (re_node_set_compare (&state->nodes, nodes))
1394         return state;
1395     }
1396
1397   /* There are no appropriate state in the dfa, create the new one.  */
1398   new_state = create_ci_newstate (dfa, nodes, hash);
1399   if (BE (new_state != NULL, 1))
1400     return new_state;
1401   else
1402     {
1403       *err = REG_ESPACE;
1404       return NULL;
1405     }
1406 }
1407
1408 /* Search for the state whose node_set is equivalent to NODES and
1409    whose context is equivalent to CONTEXT.
1410    Return the pointer to the state, if we found it in the DFA.
1411    Otherwise create the new one and return it.  In case of an error
1412    return NULL and set the error code in ERR.
1413    Note: - We assume NULL as the invalid state, then it is possible that
1414            return value is NULL and ERR is REG_NOERROR.
1415          - We never return non-NULL value in case of any errors, it is for
1416            optimization.  */
1417
1418 static re_dfastate_t*
1419 internal_function
1420 re_acquire_state_context (reg_errcode_t *err, re_dfa_t *dfa,
1421                           const re_node_set *nodes, unsigned int context)
1422 {
1423   unsigned int hash;
1424   re_dfastate_t *new_state;
1425   struct re_state_table_entry *spot;
1426   int i;
1427 #ifdef lint
1428   /* Suppress bogus uninitialized-variable warnings.  */
1429   *err = REG_NOERROR;
1430 #endif
1431   if (nodes->nelem == 0)
1432     {
1433       *err = REG_NOERROR;
1434       return NULL;
1435     }
1436   hash = calc_state_hash (nodes, context);
1437   spot = dfa->state_table + (hash & dfa->state_hash_mask);
1438
1439   for (i = 0 ; i < spot->num ; i++)
1440     {
1441       re_dfastate_t *state = spot->array[i];
1442       if (state->hash == hash
1443           && state->context == context
1444           && re_node_set_compare (state->entrance_nodes, nodes))
1445         return state;
1446     }
1447   /* There are no appropriate state in `dfa', create the new one.  */
1448   new_state = create_cd_newstate (dfa, nodes, context, hash);
1449   if (BE (new_state != NULL, 1))
1450     return new_state;
1451   else
1452     {
1453       *err = REG_ESPACE;
1454       return NULL;
1455     }
1456 }
1457
1458 /* Finish initialization of the new state NEWSTATE, and using its hash value
1459    HASH put in the appropriate bucket of DFA's state table.  Return value
1460    indicates the error code if failed.  */
1461
1462 static reg_errcode_t
1463 internal_function
1464 register_state (re_dfa_t *dfa, re_dfastate_t *newstate, unsigned int hash)
1465 {
1466   struct re_state_table_entry *spot;
1467   reg_errcode_t err;
1468   int i;
1469
1470   newstate->hash = hash;
1471   err = re_node_set_alloc (&newstate->non_eps_nodes, newstate->nodes.nelem);
1472   if (BE (err != REG_NOERROR, 0))
1473     return REG_ESPACE;
1474   for (i = 0; i < newstate->nodes.nelem; i++)
1475     {
1476       int elem = newstate->nodes.elems[i];
1477       if (!IS_EPSILON_NODE (dfa->nodes[elem].type))
1478         re_node_set_insert_last (&newstate->non_eps_nodes, elem);
1479     }
1480
1481   spot = dfa->state_table + (hash & dfa->state_hash_mask);
1482   if (BE (spot->alloc <= spot->num, 0))
1483     {
1484       int new_alloc = 2 * spot->num + 2;
1485       re_dfastate_t **new_array = re_realloc (spot->array, re_dfastate_t *,
1486                                               new_alloc);
1487       if (BE (new_array == NULL, 0))
1488         return REG_ESPACE;
1489       spot->array = new_array;
1490       spot->alloc = new_alloc;
1491     }
1492   spot->array[spot->num++] = newstate;
1493   return REG_NOERROR;
1494 }
1495
1496 /* Create the new state which is independ of contexts.
1497    Return the new state if succeeded, otherwise return NULL.  */
1498
1499 static re_dfastate_t *
1500 internal_function
1501 create_ci_newstate (re_dfa_t *dfa, const re_node_set *nodes, unsigned int hash)
1502 {
1503   int i;
1504   reg_errcode_t err;
1505   re_dfastate_t *newstate;
1506
1507   newstate = (re_dfastate_t *) calloc (sizeof (re_dfastate_t), 1);
1508   if (BE (newstate == NULL, 0))
1509     return NULL;
1510   err = re_node_set_init_copy (&newstate->nodes, nodes);
1511   if (BE (err != REG_NOERROR, 0))
1512     {
1513       re_free (newstate);
1514       return NULL;
1515     }
1516
1517   newstate->entrance_nodes = &newstate->nodes;
1518   for (i = 0 ; i < nodes->nelem ; i++)
1519     {
1520       re_token_t *node = dfa->nodes + nodes->elems[i];
1521       re_token_type_t type = node->type;
1522       if (type == CHARACTER && !node->constraint)
1523         continue;
1524 #ifdef RE_ENABLE_I18N
1525       newstate->accept_mb |= node->accept_mb;
1526 #endif /* RE_ENABLE_I18N */
1527
1528       /* If the state has the halt node, the state is a halt state.  */
1529       if (type == END_OF_RE)
1530         newstate->halt = 1;
1531       else if (type == OP_BACK_REF)
1532         newstate->has_backref = 1;
1533       else if (type == ANCHOR || node->constraint)
1534         newstate->has_constraint = 1;
1535     }
1536   err = register_state (dfa, newstate, hash);
1537   if (BE (err != REG_NOERROR, 0))
1538     {
1539       free_state (newstate);
1540       newstate = NULL;
1541     }
1542   return newstate;
1543 }
1544
1545 /* Create the new state which is depend on the context CONTEXT.
1546    Return the new state if succeeded, otherwise return NULL.  */
1547
1548 static re_dfastate_t *
1549 internal_function
1550 create_cd_newstate (re_dfa_t *dfa, const re_node_set *nodes,
1551                     unsigned int context, unsigned int hash)
1552 {
1553   int i, nctx_nodes = 0;
1554   reg_errcode_t err;
1555   re_dfastate_t *newstate;
1556
1557   newstate = (re_dfastate_t *) calloc (sizeof (re_dfastate_t), 1);
1558   if (BE (newstate == NULL, 0))
1559     return NULL;
1560   err = re_node_set_init_copy (&newstate->nodes, nodes);
1561   if (BE (err != REG_NOERROR, 0))
1562     {
1563       re_free (newstate);
1564       return NULL;
1565     }
1566
1567   newstate->context = context;
1568   newstate->entrance_nodes = &newstate->nodes;
1569
1570   for (i = 0 ; i < nodes->nelem ; i++)
1571     {
1572       unsigned int constraint = 0;
1573       re_token_t *node = dfa->nodes + nodes->elems[i];
1574       re_token_type_t type = node->type;
1575       if (node->constraint)
1576         constraint = node->constraint;
1577
1578       if (type == CHARACTER && !constraint)
1579         continue;
1580 #ifdef RE_ENABLE_I18N
1581       newstate->accept_mb |= node->accept_mb;
1582 #endif /* RE_ENABLE_I18N */
1583
1584       /* If the state has the halt node, the state is a halt state.  */
1585       if (type == END_OF_RE)
1586         newstate->halt = 1;
1587       else if (type == OP_BACK_REF)
1588         newstate->has_backref = 1;
1589       else if (type == ANCHOR)
1590         constraint = node->opr.ctx_type;
1591
1592       if (constraint)
1593         {
1594           if (newstate->entrance_nodes == &newstate->nodes)
1595             {
1596               newstate->entrance_nodes = re_malloc (re_node_set, 1);
1597               if (BE (newstate->entrance_nodes == NULL, 0))
1598                 {
1599                   free_state (newstate);
1600                   return NULL;
1601                 }
1602               re_node_set_init_copy (newstate->entrance_nodes, nodes);
1603               nctx_nodes = 0;
1604               newstate->has_constraint = 1;
1605             }
1606
1607           if (NOT_SATISFY_PREV_CONSTRAINT (constraint,context))
1608             {
1609               re_node_set_remove_at (&newstate->nodes, i - nctx_nodes);
1610               ++nctx_nodes;
1611             }
1612         }
1613     }
1614   err = register_state (dfa, newstate, hash);
1615   if (BE (err != REG_NOERROR, 0))
1616     {
1617       free_state (newstate);
1618       newstate = NULL;
1619     }
1620   return  newstate;
1621 }
1622
1623 static void
1624 internal_function
1625 free_state (re_dfastate_t *state)
1626 {
1627   re_node_set_free (&state->non_eps_nodes);
1628   re_node_set_free (&state->inveclosure);
1629   if (state->entrance_nodes != &state->nodes)
1630     {
1631       re_node_set_free (state->entrance_nodes);
1632       re_free (state->entrance_nodes);
1633     }
1634   re_node_set_free (&state->nodes);
1635   re_free (state->word_trtable);
1636   re_free (state->trtable);
1637   re_free (state);
1638 }