git.cworth.org Git - tar/blob - gnu/regex_internal.c

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