contrib/grep/lib/regex_internal.c

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