posix/regex_internal.c

   1 /* Extended regular expression matching and search library.
   2    Copyright (C) 2002 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 Lesser General Public
   8    License as published by the Free Software Foundation; either
   9    version 2.1 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    Lesser General Public License for more details.
  15
  16    You should have received a copy of the GNU Lesser General Public
  17    License along with the GNU C Library; if not, write to the Free
  18    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  19    02111-1307 USA.  */
  20
  21 #include <assert.h>
  22 #include <ctype.h>
  23 #include <limits.h>
  24 #include <stdio.h>
  25 #include <stdlib.h>
  26 #include <string.h>
  27 #include <wchar.h>
  28 #include <wctype.h>
  29
  30 #ifdef _LIBC
  31 # ifndef _RE_DEFINE_LOCALE_FUNCTIONS
  32 #  define _RE_DEFINE_LOCALE_FUNCTIONS 1
  33 #  include <locale/localeinfo.h>
  34 #  include <locale/elem-hash.h>
  35 #  include <locale/coll-lookup.h>
  36 # endif
  37 #endif
  38
  39 /* This is for other GNU distributions with internationalized messages.  */
  40 #if HAVE_LIBINTL_H || defined _LIBC
  41 # include <libintl.h>
  42 # ifdef _LIBC
  43 #  undef gettext
  44 #  define gettext(msgid) \
  45   INTUSE(__dcgettext) (_libc_intl_domainname_internal, msgid, LC_MESSAGES)
  46 # endif
  47 #else
  48 # define gettext(msgid) (msgid)
  49 #endif
  50
  51 #ifndef gettext_noop
  52 /* This define is so xgettext can find the internationalizable
  53    strings.  */
  54 # define gettext_noop(String) String
  55 #endif
  56
  57 #include "regex.h"
  58 #include "regex_internal.h"
  59
  60 static void re_string_construct_common (const unsigned char *str,
  61                                         int len, re_string_t *pstr);
  62 #ifdef RE_ENABLE_I18N
  63 static reg_errcode_t build_wcs_buffer (re_string_t *pstr);
  64 static reg_errcode_t build_wcs_upper_buffer (re_string_t *pstr);
  65 #endif /* RE_ENABLE_I18N */
  66 static reg_errcode_t build_upper_buffer (re_string_t *pstr);
  67 static reg_errcode_t re_string_translate_buffer (re_string_t *pstr,
  68                                                  RE_TRANSLATE_TYPE trans);
  69 static re_dfastate_t *create_newstate_common (re_dfa_t *dfa,
  70                                               const re_node_set *nodes,
  71                                               unsigned int hash);
  72 static reg_errcode_t register_state (re_dfa_t *dfa, re_dfastate_t *newstate,
  73                                      unsigned int hash);
  74 static re_dfastate_t *create_ci_newstate (re_dfa_t *dfa,
  75                                           const re_node_set *nodes,
  76                                           unsigned int hash);
  77 static re_dfastate_t *create_cd_newstate (re_dfa_t *dfa,
  78                                           const re_node_set *nodes,
  79                                           unsigned int context,
  80                                           unsigned int hash);
  81 static unsigned int inline calc_state_hash (const re_node_set *nodes,
  82                                             unsigned int context);
  83 \f
  84 /* Functions for string operation.  */
  85
  86 /* Construct string object.  */
  87 static reg_errcode_t
  88 re_string_construct (pstr, str, len, trans)
  89      re_string_t *pstr;
  90      const unsigned char *str;
  91      int len;
  92      RE_TRANSLATE_TYPE trans;
  93 {
  94   reg_errcode_t ret;
  95   re_string_construct_common (str, len, pstr);
  96 #ifdef RE_ENABLE_I18N
  97   if (MB_CUR_MAX >1 && pstr->len > 0)
  98     {
  99       ret = build_wcs_buffer (pstr);
 100       if (BE (ret != REG_NOERROR, 0))
 101         return ret;
 102     }
 103 #endif /* RE_ENABLE_I18N  */
 104   pstr->mbs_case = str;
 105   if (trans != NULL)
 106     {
 107       ret = re_string_translate_buffer (pstr, trans);
 108       if (BE (ret != REG_NOERROR, 0))
 109         return ret;
 110     }
 111   return REG_NOERROR;
 112 }
 113
 114 /* Construct string object. We use this function instead of
 115    re_string_construct for case insensitive mode.  */
 116
 117 static reg_errcode_t
 118 re_string_construct_toupper (pstr, str, len, trans)
 119      re_string_t *pstr;
 120      const unsigned char *str;
 121      int len;
 122      RE_TRANSLATE_TYPE trans;
 123 {
 124   reg_errcode_t ret;
 125   /* Set case sensitive buffer.  */
 126   re_string_construct_common (str, len, pstr);
 127 #ifdef RE_ENABLE_I18N
 128   if (MB_CUR_MAX >1)
 129     {
 130       if (BE (pstr->len > 0, 1))
 131         {
 132           ret = build_wcs_upper_buffer (pstr);
 133           if (BE (ret != REG_NOERROR, 0))
 134             return ret;
 135         }
 136     }
 137   else
 138 #endif /* RE_ENABLE_I18N  */
 139     {
 140       if (BE (pstr->len > 0, 1))
 141         {
 142           ret = build_upper_buffer (pstr);
 143           if (BE (ret != REG_NOERROR, 0))
 144             return ret;
 145         }
 146     }
 147   pstr->mbs_case = str;
 148   if (trans != NULL)
 149     {
 150       ret = re_string_translate_buffer (pstr, trans);
 151       if (BE (ret != REG_NOERROR, 0))
 152         return ret;
 153     }
 154   return REG_NOERROR;
 155 }
 156
 157 /* Helper functions for re_string_construct_*.  */
 158 static void
 159 re_string_construct_common (str, len, pstr)
 160      const unsigned char *str;
 161      int len;
 162      re_string_t *pstr;
 163 {
 164   pstr->mbs = str;
 165   pstr->cur_idx = 0;
 166   pstr->len = len;
 167 #ifdef RE_ENABLE_I18N
 168   pstr->wcs = NULL;
 169 #endif
 170   pstr->mbs_case = NULL;
 171   pstr->mbs_alloc = 0;
 172   pstr->mbs_case_alloc = 0;
 173 }
 174
 175 #ifdef RE_ENABLE_I18N
 176
 177 /* Build wide character buffer for `pstr'.
 178    If the byte sequence of the string are:
 179      <mb1>(0), <mb1>(1), <mb2>(0), <mb2>(1), <sb3>
 180    Then wide character buffer will be:
 181      <wc1>   , WEOF    , <wc2>   , WEOF    , <wc3>
 182    We use WEOF for padding, they indicate that the position isn't
 183    a first byte of a multibyte character.  */
 184
 185 static reg_errcode_t
 186 build_wcs_buffer (pstr)
 187      re_string_t *pstr;
 188 {
 189   mbstate_t state, prev_st;
 190   wchar_t wc;
 191   int char_idx, char_len, mbclen;
 192
 193   pstr->wcs = re_malloc (wchar_t, pstr->len + 1);
 194   if (BE (pstr->wcs == NULL, 0))
 195     return REG_ESPACE;
 196
 197   memset (&state, '\0', sizeof (mbstate_t));
 198   char_len = pstr->len;
 199   for (char_idx = 0; char_idx < char_len ;)
 200     {
 201       int next_idx, remain_len = char_len - char_idx;
 202       prev_st = state;
 203       mbclen = mbrtowc (&wc, pstr->mbs + char_idx, remain_len, &state);
 204       if (BE (mbclen == (size_t) -2 || mbclen == (size_t) -1 || mbclen == 0, 0))
 205         /* We treat these cases as a singlebyte character.  */
 206         {
 207           mbclen = 1;
 208           wc = (wchar_t) pstr->mbs[char_idx++];
 209           state = prev_st;
 210         }
 211       /* Write wide character and padding.  */
 212       pstr->wcs[char_idx++] = wc;
 213       for (next_idx = char_idx + mbclen - 1; char_idx < next_idx ;)
 214         pstr->wcs[char_idx++] = WEOF;
 215     }
 216   return REG_NOERROR;
 217 }
 218
 219 static reg_errcode_t
 220 build_wcs_upper_buffer (pstr)
 221      re_string_t *pstr;
 222 {
 223   mbstate_t state, prev_st;
 224   wchar_t wc;
 225   unsigned char *mbs_upper;
 226   int char_idx, char_len, mbclen;
 227
 228   pstr->wcs = re_malloc (wchar_t, pstr->len + 1);
 229   mbs_upper = re_malloc (unsigned char, pstr->len + 1);
 230   if (BE (pstr->wcs == NULL || mbs_upper == NULL, 0))
 231     {
 232       pstr->wcs = NULL;
 233       return REG_ESPACE;
 234     }
 235
 236   memset (&state, '\0', sizeof (mbstate_t));
 237   char_len = pstr->len;
 238   for (char_idx = 0 ; char_idx < char_len ; char_idx += mbclen)
 239     {
 240       int byte_idx, remain_len = char_len - char_idx;
 241       prev_st = state;
 242       mbclen = mbrtowc (&wc, pstr->mbs + char_idx, remain_len, &state);
 243       if (mbclen == 1)
 244         {
 245           pstr->wcs[char_idx] = wc;
 246           if (islower (pstr->mbs[char_idx]))
 247             mbs_upper[char_idx] = toupper (pstr->mbs[char_idx]);
 248           else
 249             mbs_upper[char_idx] = pstr->mbs[char_idx];
 250         }
 251       else if (BE (mbclen == (size_t) -2 || mbclen == (size_t) -1
 252                    || mbclen == 0, 0))
 253         /* We treat these cases as a singlebyte character.  */
 254         {
 255           mbclen = 1;
 256           pstr->wcs[char_idx] = (wchar_t) pstr->mbs[char_idx];
 257           mbs_upper[char_idx] = pstr->mbs[char_idx];
 258           state = prev_st;
 259         }
 260       else /* mbclen > 1 */
 261         {
 262           pstr->wcs[char_idx] = wc;
 263           if (iswlower (wc))
 264             wcrtomb (mbs_upper + char_idx, towupper (wc), &prev_st);
 265           else
 266             memcpy (mbs_upper + char_idx, pstr->mbs + char_idx, mbclen);
 267           for (byte_idx = 1 ; byte_idx < mbclen ; byte_idx++)
 268             pstr->wcs[char_idx + byte_idx] = WEOF;
 269         }
 270     }
 271   pstr->mbs = mbs_upper;
 272   pstr->mbs_alloc = 1;
 273   return REG_NOERROR;
 274 }
 275 #endif /* RE_ENABLE_I18N  */
 276
 277 static reg_errcode_t
 278 build_upper_buffer (pstr)
 279      re_string_t *pstr;
 280 {
 281   unsigned char *mbs_upper;
 282   int char_idx, char_len;
 283
 284   mbs_upper = re_malloc (unsigned char, pstr->len + 1);
 285   if (BE (mbs_upper == NULL, 0))
 286     return REG_ESPACE;
 287
 288   char_len = pstr->len;
 289   for (char_idx = 0 ; char_idx < char_len ; char_idx ++)
 290     {
 291       if (islower (pstr->mbs[char_idx]))
 292         mbs_upper[char_idx] = toupper (pstr->mbs[char_idx]);
 293       else
 294         mbs_upper[char_idx] = pstr->mbs[char_idx];
 295     }
 296   pstr->mbs = mbs_upper;
 297   pstr->mbs_alloc = 1;
 298   return REG_NOERROR;
 299 }
 300
 301 /* Apply TRANS to the buffer in PSTR.  We assume that wide char buffer
 302    is already constructed if MB_CUR_MAX > 1.  */
 303
 304 static reg_errcode_t
 305 re_string_translate_buffer (pstr, trans)
 306      re_string_t *pstr;
 307      RE_TRANSLATE_TYPE trans;
 308 {
 309   int buf_idx;
 310   unsigned char *transed_buf, *transed_case_buf;
 311 #ifdef DEBUG
 312   assert (trans != NULL);
 313 #endif
 314   if (pstr->mbs_alloc)
 315     {
 316       transed_buf = (unsigned char *) pstr->mbs;
 317       transed_case_buf = re_malloc (unsigned char, pstr->len + 1);
 318       if (BE (transed_case_buf == NULL, 0))
 319         return REG_ESPACE;
 320       pstr->mbs_case_alloc = 1;
 321     }
 322   else
 323     {
 324       transed_buf = re_malloc (unsigned char, pstr->len + 1);
 325       if (BE (transed_buf == NULL, 0))
 326         return REG_ESPACE;
 327       transed_case_buf = NULL;
 328       pstr->mbs_alloc = 1;
 329     }
 330   for (buf_idx = 0 ; buf_idx < pstr->len ; buf_idx++)
 331     {
 332 #ifdef RE_ENABLE_I18N
 333       if (MB_CUR_MAX > 1 && !re_string_is_single_byte_char (pstr, buf_idx))
 334         transed_buf[buf_idx] = pstr->mbs[buf_idx];
 335       else
 336 #endif
 337         transed_buf[buf_idx] = trans[pstr->mbs[buf_idx]];
 338       if (transed_case_buf)
 339         {
 340 #ifdef RE_ENABLE_I18N
 341          if (MB_CUR_MAX > 1 && !re_string_is_single_byte_char (pstr, buf_idx))
 342             transed_case_buf[buf_idx] = pstr->mbs_case[buf_idx];
 343           else
 344 #endif
 345             transed_case_buf[buf_idx] = trans[pstr->mbs_case[buf_idx]];
 346         }
 347     }
 348   if (pstr->mbs_case_alloc == 1)
 349     {
 350       pstr->mbs = transed_buf;
 351       pstr->mbs_case = transed_case_buf;
 352     }
 353   else
 354     {
 355       pstr->mbs = transed_buf;
 356       pstr->mbs_case = transed_buf;
 357     }
 358   return REG_NOERROR;
 359 }
 360
 361 static void
 362 re_string_destruct (pstr)
 363      re_string_t *pstr;
 364 {
 365 #ifdef RE_ENABLE_I18N
 366   re_free (pstr->wcs);
 367 #endif /* RE_ENABLE_I18N  */
 368   if (pstr->mbs_alloc)
 369     re_free ((void *) pstr->mbs);
 370   if (pstr->mbs_case_alloc)
 371     re_free ((void *) pstr->mbs_case);
 372 }
 373
 374 /* Return the context at IDX in INPUT.  */
 375 static unsigned int
 376 re_string_context_at (input, idx, eflags, newline_anchor)
 377      const re_string_t *input;
 378      int idx, eflags, newline_anchor;
 379 {
 380   int c;
 381   if (idx < 0 || idx == input->len)
 382     {
 383       unsigned int context = 0;
 384       if (idx < 0)
 385         context = CONTEXT_BEGBUF;
 386       else /* (idx == input->len) */
 387         context = CONTEXT_ENDBUF;
 388
 389       if ((idx < 0 && !(eflags & REG_NOTBOL))
 390           || (idx == input->len && !(eflags & REG_NOTEOL)))
 391         return CONTEXT_NEWLINE | context;
 392       else
 393         return context;
 394     }
 395   c = re_string_byte_at (input, idx);
 396   if (IS_WORD_CHAR (c))
 397     return CONTEXT_WORD;
 398   return (newline_anchor && IS_NEWLINE (c)) ? CONTEXT_NEWLINE : 0;
 399 }
 400 \f
 401 /* Functions for set operation.  */
 402
 403 static reg_errcode_t
 404 re_node_set_alloc (set, size)
 405      re_node_set *set;
 406      int size;
 407 {
 408   set->alloc = size;
 409   set->nelem = 0;
 410   set->elems = re_malloc (int, size);
 411   if (BE (set->elems == NULL, 0))
 412     return REG_ESPACE;
 413   return REG_NOERROR;
 414 }
 415
 416 static reg_errcode_t
 417 re_node_set_init_1 (set, elem)
 418      re_node_set *set;
 419      int elem;
 420 {
 421   set->alloc = 1;
 422   set->nelem = 1;
 423   set->elems = re_malloc (int, 1);
 424   if (BE (set->elems == NULL, 0))
 425     return REG_ESPACE;
 426   set->elems[0] = elem;
 427   return REG_NOERROR;
 428 }
 429
 430 static reg_errcode_t
 431 re_node_set_init_2 (set, elem1, elem2)
 432      re_node_set *set;
 433      int elem1, elem2;
 434 {
 435   set->alloc = 2;
 436   set->elems = re_malloc (int, 2);
 437   if (BE (set->elems == NULL, 0))
 438     return REG_ESPACE;
 439   if (elem1 == elem2)
 440     {
 441       set->nelem = 1;
 442       set->elems[0] = elem1;
 443     }
 444   else
 445     {
 446       set->nelem = 2;
 447       if (elem1 < elem2)
 448         {
 449           set->elems[0] = elem1;
 450           set->elems[1] = elem2;
 451         }
 452       else
 453         {
 454           set->elems[0] = elem2;
 455           set->elems[1] = elem1;
 456         }
 457     }
 458   return REG_NOERROR;
 459 }
 460
 461 static reg_errcode_t
 462 re_node_set_init_copy (dest, src)
 463      re_node_set *dest;
 464      const re_node_set *src;
 465 {
 466   dest->nelem = src->nelem;
 467   if (src->nelem > 0)
 468     {
 469       dest->alloc = dest->nelem;
 470       dest->elems = re_malloc (int, dest->alloc);
 471       if (BE (dest->elems == NULL, 0))
 472         return REG_ESPACE;
 473       memcpy (dest->elems, src->elems, src->nelem * sizeof (int));
 474     }
 475   else
 476     re_node_set_init_empty (dest);
 477   return REG_NOERROR;
 478 }
 479
 480 /* Calculate the intersection of the sets SRC1 and SRC2. And store it in
 481    DEST. Return value indicate the error code or REG_NOERROR if succeeded.
 482    Note: We assume dest->elems is NULL, when dest->alloc is 0.  */
 483
 484 static reg_errcode_t
 485 re_node_set_intersect (dest, src1, src2)
 486      re_node_set *dest;
 487      const re_node_set *src1, *src2;
 488 {
 489   int i1, i2, id;
 490   if (src1->nelem > 0 && src2->nelem > 0)
 491     {
 492       if (src1->nelem + src2->nelem > dest->alloc)
 493         {
 494           dest->alloc = src1->nelem + src2->nelem;
 495           dest->elems = re_realloc (dest->elems, int, dest->alloc);
 496           if (BE (dest->elems == NULL, 0))
 497             return REG_ESPACE;
 498         }
 499     }
 500   else
 501     {
 502       /* The intersection of empty sets is also empty set.  */
 503       dest->nelem = 0;
 504       return REG_NOERROR;
 505     }
 506
 507   for (i1 = i2 = id = 0; i1 < src1->nelem && i2 < src2->nelem; )
 508     {
 509       if (src1->elems[i1] > src2->elems[i2])
 510         {
 511           ++i2;
 512           continue;
 513         }
 514       /* The intersection must have the elements which are in both of
 515          SRC1 and SRC2.  */
 516       if (src1->elems[i1] == src2->elems[i2])
 517         dest->elems[id++] = src2->elems[i2++];
 518       ++i1;
 519     }
 520   dest->nelem = id;
 521   return REG_NOERROR;
 522 }
 523
 524 /* Calculate the intersection of the sets SRC1 and SRC2. And merge it to
 525    DEST. Return value indicate the error code or REG_NOERROR if succeeded.
 526    Note: We assume dest->elems is NULL, when dest->alloc is 0.  */
 527
 528 static reg_errcode_t
 529 re_node_set_add_intersect (dest, src1, src2)
 530      re_node_set *dest;
 531      const re_node_set *src1, *src2;
 532 {
 533   int i1, i2, id;
 534   if (src1->nelem > 0 && src2->nelem > 0)
 535     {
 536       if (src1->nelem + src2->nelem + dest->nelem > dest->alloc)
 537         {
 538           dest->alloc = src1->nelem + src2->nelem + dest->nelem;
 539           dest->elems = re_realloc (dest->elems, int, dest->alloc);
 540           if (BE (dest->elems == NULL, 0))
 541             return REG_ESPACE;
 542         }
 543     }
 544   else
 545     return REG_NOERROR;
 546
 547   for (i1 = i2 = id = 0 ; i1 < src1->nelem && i2 < src2->nelem ;)
 548     {
 549       if (src1->elems[i1] > src2->elems[i2])
 550         {
 551           ++i2;
 552           continue;
 553         }
 554       if (src1->elems[i1] == src2->elems[i2])
 555         {
 556           while (id < dest->nelem && dest->elems[id] < src2->elems[i2])
 557             ++id;
 558           if (id < dest->nelem && dest->elems[id] == src2->elems[i2])
 559             ++id;
 560           else
 561             {
 562               memmove (dest->elems + id + 1, dest->elems + id,
 563                        sizeof (int) * (dest->nelem - id));
 564               dest->elems[id++] = src2->elems[i2++];
 565               ++dest->nelem;
 566             }
 567         }
 568       ++i1;
 569     }
 570   return REG_NOERROR;
 571 }
 572
 573 /* Calculate the union set of the sets SRC1 and SRC2. And store it to
 574    DEST. Return value indicate the error code or REG_NOERROR if succeeded.  */
 575
 576 static reg_errcode_t
 577 re_node_set_init_union (dest, src1, src2)
 578      re_node_set *dest;
 579      const re_node_set *src1, *src2;
 580 {
 581   int i1, i2, id;
 582   if (src1 != NULL && src1->nelem > 0 && src2 != NULL && src2->nelem > 0)
 583     {
 584       dest->alloc = src1->nelem + src2->nelem;
 585       dest->elems = re_malloc (int, dest->alloc);
 586       if (BE (dest->elems == NULL, 0))
 587         return REG_ESPACE;
 588     }
 589   else
 590     {
 591       if (src1 != NULL && src1->nelem > 0)
 592         return re_node_set_init_copy (dest, src1);
 593       else if (src2 != NULL && src2->nelem > 0)
 594         return re_node_set_init_copy (dest, src2);
 595       else
 596         re_node_set_init_empty (dest);
 597       return REG_NOERROR;
 598     }
 599   for (i1 = i2 = id = 0 ; i1 < src1->nelem && i2 < src2->nelem ;)
 600     {
 601       if (src1->elems[i1] > src2->elems[i2])
 602         {
 603           dest->elems[id++] = src2->elems[i2++];
 604           continue;
 605         }
 606       if (src1->elems[i1] == src2->elems[i2])
 607         ++i2;
 608       dest->elems[id++] = src1->elems[i1++];
 609     }
 610   if (i1 < src1->nelem)
 611     {
 612       memcpy (dest->elems + id, src1->elems + i1,
 613              (src1->nelem - i1) * sizeof (int));
 614       id += src1->nelem - i1;
 615     }
 616   else if (i2 < src2->nelem)
 617     {
 618       memcpy (dest->elems + id, src2->elems + i2,
 619              (src2->nelem - i2) * sizeof (int));
 620       id += src2->nelem - i2;
 621     }
 622   dest->nelem = id;
 623   return REG_NOERROR;
 624 }
 625
 626 /* Calculate the union set of the sets DEST and SRC. And store it to
 627    DEST. Return value indicate the error code or REG_NOERROR if succeeded.  */
 628
 629 static reg_errcode_t
 630 re_node_set_merge (dest, src)
 631      re_node_set *dest;
 632      const re_node_set *src;
 633 {
 634   int si, di;
 635   if (src == NULL || src->nelem == 0)
 636     return REG_NOERROR;
 637   if (dest->alloc < src->nelem + dest->nelem)
 638     {
 639       dest->alloc = 2 * (src->nelem + dest->alloc);
 640       dest->elems = re_realloc (dest->elems, int, dest->alloc);
 641       if (BE (dest->elems == NULL, 0))
 642         return REG_ESPACE;
 643     }
 644
 645   for (si = 0, di = 0 ; si < src->nelem && di < dest->nelem ;)
 646     {
 647       int cp_from, ncp, mid, right, src_elem = src->elems[si];
 648       /* Binary search the spot we will add the new element.  */
 649       right = dest->nelem;
 650       while (di < right)
 651         {
 652           mid = (di + right) / 2;
 653           if (dest->elems[mid] < src_elem)
 654             di = mid + 1;
 655           else
 656             right = mid;
 657         }
 658       if (di >= dest->nelem)
 659         break;
 660
 661       if (dest->elems[di] == src_elem)
 662         {
 663           /* Skip since, DEST already has the element.  */
 664           ++di;
 665           ++si;
 666           continue;
 667         }
 668
 669       /* Skip the src elements which are less than dest->elems[di].  */
 670       cp_from = si;
 671       while (si < src->nelem && src->elems[si] < dest->elems[di])
 672         ++si;
 673       /* Copy these src elements.  */
 674       ncp = si - cp_from;
 675       memmove (dest->elems + di + ncp, dest->elems + di,
 676                sizeof (int) * (dest->nelem - di));
 677       memcpy (dest->elems + di, src->elems + cp_from,
 678               sizeof (int) * ncp);
 679       /* Update counters.  */
 680       di += ncp;
 681       dest->nelem += ncp;
 682     }
 683
 684   /* Copy remaining src elements.  */
 685   if (si < src->nelem)
 686     {
 687       memcpy (dest->elems + di, src->elems + si,
 688               sizeof (int) * (src->nelem - si));
 689       dest->nelem += src->nelem - si;
 690     }
 691   return REG_NOERROR;
 692 }
 693
 694 /* Insert the new element ELEM to the re_node_set* SET.
 695    return 0 if SET already has ELEM,
 696    return -1 if an error is occured, return 1 otherwise.  */
 697
 698 static int
 699 re_node_set_insert (set, elem)
 700      re_node_set *set;
 701      int elem;
 702 {
 703   int idx, right, mid;
 704   /* In case of the set is empty.  */
 705   if (set->elems == NULL || set->alloc == 0)
 706     {
 707       if (BE (re_node_set_init_1 (set, elem) == REG_NOERROR, 1))
 708         return 1;
 709       else
 710         return -1;
 711     }
 712
 713   /* Binary search the spot we will add the new element.  */
 714   idx = 0;
 715   right = set->nelem;
 716   while (idx < right)
 717     {
 718       mid = (idx + right) / 2;
 719       if (set->elems[mid] < elem)
 720         idx = mid + 1;
 721       else
 722         right = mid;
 723     }
 724
 725   /* Realloc if we need.  */
 726   if (set->alloc < set->nelem + 1)
 727     {
 728       int *new_array;
 729       set->alloc = set->alloc * 2;
 730       new_array = re_malloc (int, set->alloc);
 731       if (BE (new_array == NULL, 0))
 732         return -1;
 733       /* Copy the elements they are followed by the new element.  */
 734       if (idx > 0)
 735         memcpy (new_array, set->elems, sizeof (int) * (idx));
 736       /* Copy the elements which follows the new element.  */
 737       if (set->nelem - idx > 0)
 738         memcpy (new_array + idx + 1, set->elems + idx,
 739                 sizeof (int) * (set->nelem - idx));
 740       set->elems = new_array;
 741     }
 742   else
 743     {
 744       /* Move the elements which follows the new element.  */
 745       if (set->nelem - idx > 0)
 746         memmove (set->elems + idx + 1, set->elems + idx,
 747                  sizeof (int) * (set->nelem - idx));
 748     }
 749   /* Insert the new element.  */
 750   set->elems[idx] = elem;
 751   ++set->nelem;
 752   return 1;
 753 }
 754
 755 /* Compare two node sets SET1 and SET2.
 756    return 1 if SET1 and SET2 are equivalent, retrun 0 otherwise.  */
 757
 758 static int
 759 re_node_set_compare (set1, set2)
 760      const re_node_set *set1, *set2;
 761 {
 762   int i;
 763   if (set1 == NULL || set2 == NULL || set1->nelem != set2->nelem)
 764     return 0;
 765   for (i = 0 ; i < set1->nelem ; i++)
 766     if (set1->elems[i] != set2->elems[i])
 767       return 0;
 768   return 1;
 769 }
 770
 771 /* Return 1 if SET contains the element ELEM, return 0 otherwise.  */
 772
 773 static int
 774 re_node_set_contains (set, elem)
 775      const re_node_set *set;
 776      int elem;
 777 {
 778   int idx, right, mid;
 779   if (set->nelem <= 0)
 780     return 0;
 781
 782   /* Binary search the element.  */
 783   idx = 0;
 784   right = set->nelem - 1;
 785   while (idx < right)
 786     {
 787       mid = (idx + right) / 2;
 788       if (set->elems[mid] < elem)
 789         idx = mid + 1;
 790       else
 791         right = mid;
 792     }
 793   return set->elems[idx] == elem;
 794 }
 795
 796 static void
 797 re_node_set_remove_at (set, idx)
 798      re_node_set *set;
 799      int idx;
 800 {
 801   if (idx < 0 || idx >= set->nelem)
 802     return;
 803   if (idx < set->nelem - 1)
 804     memmove (set->elems + idx, set->elems + idx + 1,
 805              sizeof (int) * (set->nelem - idx - 1));
 806   --set->nelem;
 807 }
 808 \f
 809
 810 /* Add the token TOKEN to dfa->nodes, and return the index of the token.
 811    Or return -1, if an error will be occured.  */
 812
 813 static int
 814 re_dfa_add_node (dfa, token, mode)
 815      re_dfa_t *dfa;
 816      re_token_t token;
 817      int mode;
 818 {
 819   if (dfa->nodes_len >= dfa->nodes_alloc)
 820     {
 821       re_token_t *new_array;
 822       dfa->nodes_alloc *= 2;
 823       new_array = re_realloc (dfa->nodes, re_token_t, dfa->nodes_alloc);
 824       if (BE (new_array == NULL, 0))
 825         return -1;
 826       else
 827         dfa->nodes = new_array;
 828       if (mode)
 829         {
 830           int *new_firsts, *new_nexts;
 831           re_node_set *new_edests, *new_eclosures, *new_inveclosures;
 832
 833           new_firsts = re_realloc (dfa->firsts, int, dfa->nodes_alloc);
 834           new_nexts = re_realloc (dfa->nexts, int, dfa->nodes_alloc);
 835           new_edests = re_realloc (dfa->edests, re_node_set, dfa->nodes_alloc);
 836           new_eclosures = re_realloc (dfa->eclosures, re_node_set,
 837                                       dfa->nodes_alloc);
 838           new_inveclosures = re_realloc (dfa->inveclosures, re_node_set,
 839                                          dfa->nodes_alloc);
 840           if (BE (new_firsts == NULL || new_nexts == NULL || new_edests == NULL
 841                   || new_eclosures == NULL || new_inveclosures == NULL, 0))
 842             return -1;
 843           dfa->firsts = new_firsts;
 844           dfa->nexts = new_nexts;
 845           dfa->edests = new_edests;
 846           dfa->eclosures = new_eclosures;
 847           dfa->inveclosures = new_inveclosures;
 848         }
 849     }
 850   dfa->nodes[dfa->nodes_len] = token;
 851   dfa->nodes[dfa->nodes_len].duplicated = 0;
 852   return dfa->nodes_len++;
 853 }
 854
 855 static unsigned int inline
 856 calc_state_hash (nodes, context)
 857      const re_node_set *nodes;
 858      unsigned int context;
 859 {
 860   unsigned int hash = nodes->nelem + context;
 861   int i;
 862   for (i = 0 ; i < nodes->nelem ; i++)
 863     hash += nodes->elems[i];
 864   return hash;
 865 }
 866
 867 /* Search for the state whose node_set is equivalent to NODES.
 868    Return the pointer to the state, if we found it in the DFA.
 869    Otherwise create the new one and return it.  In case of an error
 870    return NULL and set the error code in ERR.
 871    Note: - We assume NULL as the invalid state, then it is possible that
 872            return value is NULL and ERR is REG_NOERROR.
 873          - We never return non-NULL value in case of any errors, it is for
 874            optimization.  */
 875
 876 static re_dfastate_t*
 877 re_acquire_state (err, dfa, nodes)
 878      reg_errcode_t *err;
 879      re_dfa_t *dfa;
 880      const re_node_set *nodes;
 881 {
 882   unsigned int hash;
 883   re_dfastate_t *new_state;
 884   struct re_state_table_entry *spot;
 885   int i;
 886   if (BE (nodes->nelem == 0, 0))
 887     {
 888       *err = REG_NOERROR;
 889       return NULL;
 890     }
 891   hash = calc_state_hash (nodes, 0);
 892   spot = dfa->state_table + (hash & dfa->state_hash_mask);
 893
 894   for (i = 0 ; i < spot->num ; i++)
 895     {
 896       re_dfastate_t *state = spot->array[i];
 897       if (hash != state->hash)
 898         continue;
 899       if (re_node_set_compare (&state->nodes, nodes))
 900         return state;
 901     }
 902
 903   /* There are no appropriate state in the dfa, create the new one.  */
 904   new_state = create_ci_newstate (dfa, nodes, hash);
 905   if (BE (new_state != NULL, 1))
 906     return new_state;
 907   else
 908     {
 909       *err = REG_ESPACE;
 910       return NULL;
 911     }
 912 }
 913
 914 /* Search for the state whose node_set is equivalent to NODES and
 915    whose context is equivalent to CONTEXT.
 916    Return the pointer to the state, if we found it in the DFA.
 917    Otherwise create the new one and return it.  In case of an error
 918    return NULL and set the error code in ERR.
 919    Note: - We assume NULL as the invalid state, then it is possible that
 920            return value is NULL and ERR is REG_NOERROR.
 921          - We never return non-NULL value in case of any errors, it is for
 922            optimization.  */
 923
 924 static re_dfastate_t*
 925 re_acquire_state_context (err, dfa, nodes, context)
 926      reg_errcode_t *err;
 927      re_dfa_t *dfa;
 928      const re_node_set *nodes;
 929      unsigned int context;
 930 {
 931   unsigned int hash;
 932   re_dfastate_t *new_state;
 933   struct re_state_table_entry *spot;
 934   int i;
 935   if (nodes->nelem == 0)
 936     {
 937       *err = REG_NOERROR;
 938       return NULL;
 939     }
 940   hash = calc_state_hash (nodes, context);
 941   spot = dfa->state_table + (hash & dfa->state_hash_mask);
 942
 943   for (i = 0 ; i < spot->num ; i++)
 944     {
 945       re_dfastate_t *state = spot->array[i];
 946       if (hash != state->hash)
 947         continue;
 948       if (re_node_set_compare (state->entrance_nodes, nodes)
 949           && state->context == context)
 950         return state;
 951     }
 952   /* There are no appropriate state in `dfa', create the new one.  */
 953   new_state = create_cd_newstate (dfa, nodes, context, hash);
 954   if (BE (new_state != NULL, 1))
 955     return new_state;
 956   else
 957     {
 958       *err = REG_ESPACE;
 959       return NULL;
 960     }
 961 }
 962
 963 /* Allocate memory for DFA state and initialize common properties.
 964    Return the new state if succeeded, otherwise return NULL.  */
 965
 966 static re_dfastate_t *
 967 create_newstate_common (dfa, nodes, hash)
 968      re_dfa_t *dfa;
 969      const re_node_set *nodes;
 970      unsigned int hash;
 971 {
 972   re_dfastate_t *newstate;
 973   newstate = (re_dfastate_t *) calloc (sizeof (re_dfastate_t), 1);
 974   if (BE (newstate == NULL, 0))
 975     return NULL;
 976   re_node_set_init_copy (&newstate->nodes, nodes);
 977   newstate->trtable = NULL;
 978   newstate->trtable_search = NULL;
 979   newstate->hash = hash;
 980   return newstate;
 981 }
 982
 983 /* Store the new state NEWSTATE whose hash value is HASH in appropriate
 984    position.  Return value indicate the error code if failed.  */
 985
 986 static reg_errcode_t
 987 register_state (dfa, newstate, hash)
 988      re_dfa_t *dfa;
 989      re_dfastate_t *newstate;
 990      unsigned int hash;
 991 {
 992   struct re_state_table_entry *spot;
 993   spot = dfa->state_table + (hash & dfa->state_hash_mask);
 994
 995   if (spot->alloc <= spot->num)
 996     {
 997       spot->alloc = 2 * spot->num + 2;
 998       spot->array = re_realloc (spot->array, re_dfastate_t *, spot->alloc);
 999       if (BE (spot->array == NULL, 0))
1000         return REG_ESPACE;
1001     }
1002   spot->array[spot->num++] = newstate;
1003   return REG_NOERROR;
1004 }
1005
1006 /* Create the new state which is independ of contexts.
1007    Return the new state if succeeded, otherwise return NULL.  */
1008
1009 static re_dfastate_t *
1010 create_ci_newstate (dfa, nodes, hash)
1011      re_dfa_t *dfa;
1012      const re_node_set *nodes;
1013      unsigned int hash;
1014 {
1015   int i;
1016   reg_errcode_t err;
1017   re_dfastate_t *newstate;
1018   newstate = create_newstate_common (dfa, nodes, hash);
1019   if (BE (newstate == NULL, 0))
1020     return NULL;
1021   newstate->entrance_nodes = &newstate->nodes;
1022
1023   for (i = 0 ; i < nodes->nelem ; i++)
1024     {
1025       re_token_t *node = dfa->nodes + nodes->elems[i];
1026       re_token_type_t type = node->type;
1027       if (type == CHARACTER)
1028         continue;
1029
1030       /* If the state has the halt node, the state is a halt state.  */
1031       else if (type == END_OF_RE)
1032         newstate->halt = 1;
1033       else if (type == COMPLEX_BRACKET
1034                || (type == OP_PERIOD && MB_CUR_MAX > 1))
1035         newstate->accept_mb = 1;
1036       else if (type == OP_BACK_REF)
1037         newstate->has_backref = 1;
1038       else if (type == ANCHOR || OP_CONTEXT_NODE)
1039         {
1040           newstate->has_constraint = 1;
1041           if (type == OP_CONTEXT_NODE
1042               && dfa->nodes[node->opr.ctx_info->entity].type == END_OF_RE)
1043             newstate->halt = 1;
1044         }
1045     }
1046   err = register_state (dfa, newstate, hash);
1047   return (err != REG_NOERROR) ? NULL : newstate;
1048 }
1049
1050 /* Create the new state which is depend on the context CONTEXT.
1051    Return the new state if succeeded, otherwise return NULL.  */
1052
1053 static re_dfastate_t *
1054 create_cd_newstate (dfa, nodes, context, hash)
1055      re_dfa_t *dfa;
1056      const re_node_set *nodes;
1057      unsigned int context, hash;
1058 {
1059   int i, nctx_nodes = 0;
1060   reg_errcode_t err;
1061   re_dfastate_t *newstate;
1062
1063   newstate = create_newstate_common (dfa, nodes, hash);
1064   if (BE (newstate == NULL, 0))
1065     return NULL;
1066   newstate->context = context;
1067   newstate->entrance_nodes = &newstate->nodes;
1068
1069   for (i = 0 ; i < nodes->nelem ; i++)
1070     {
1071       unsigned int constraint = 0;
1072       re_token_t *node = dfa->nodes + nodes->elems[i];
1073       re_token_type_t type = node->type;
1074       if (type == CHARACTER)
1075         continue;
1076
1077       /* If the state has the halt node, the state is a halt state.  */
1078       else if (type == END_OF_RE)
1079         newstate->halt = 1;
1080       else if (type == COMPLEX_BRACKET
1081                || (type == OP_PERIOD && MB_CUR_MAX > 1))
1082         newstate->accept_mb = 1;
1083       else if (type == OP_BACK_REF)
1084         newstate->has_backref = 1;
1085       else if (type == ANCHOR)
1086         constraint = node->opr.ctx_type;
1087       else if (type == OP_CONTEXT_NODE)
1088         {
1089           re_token_type_t ctype = dfa->nodes[node->opr.ctx_info->entity].type;
1090           constraint = node->constraint;
1091           if (ctype == END_OF_RE)
1092             newstate->halt = 1;
1093           else if (ctype == OP_BACK_REF)
1094             newstate->has_backref = 1;
1095           else if (ctype == COMPLEX_BRACKET
1096                    || (type == OP_PERIOD && MB_CUR_MAX > 1))
1097             newstate->accept_mb = 1;
1098         }
1099
1100       if (constraint)
1101         {
1102           if (newstate->entrance_nodes == &newstate->nodes)
1103             {
1104               newstate->entrance_nodes = re_malloc (re_node_set, 1);
1105               if (BE (newstate->entrance_nodes == NULL, 0))
1106                 return NULL;
1107               re_node_set_init_copy (newstate->entrance_nodes, nodes);
1108               nctx_nodes = 0;
1109               newstate->has_constraint = 1;
1110             }
1111
1112           if (NOT_SATISFY_PREV_CONSTRAINT (constraint,context))
1113             {
1114               re_node_set_remove_at (&newstate->nodes, i - nctx_nodes);
1115               ++nctx_nodes;
1116             }
1117         }
1118     }
1119   err = register_state (dfa, newstate, hash);
1120   return (err != REG_NOERROR) ? NULL : newstate;
1121 }