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