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