(re_node_set_intersect): Add a check on malloc failure.
[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 (ret != REG_NOERROR)
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 (ret != REG_NOERROR)
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 (pstr->len > 0)
130         {
131           ret = build_wcs_upper_buffer (pstr);
132           if (ret != REG_NOERROR)
133             return ret;
134         }
135     }
136   else
137 #endif /* RE_ENABLE_I18N  */
138     {
139       if (pstr->len > 0)
140         {
141           ret = build_upper_buffer (pstr);
142           if (ret != REG_NOERROR)
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 (ret != REG_NOERROR)
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 (pstr->wcs == NULL)
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 (mbclen == (size_t) -2 || mbclen == (size_t) -1 || mbclen == 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 (pstr->wcs == NULL || mbs_upper == NULL)
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 (mbclen == (size_t) -2 || mbclen == (size_t) -1 || mbclen == 0)
251         /* We treat these cases as a singlebyte character.  */
252         {
253           mbclen = 1;
254           pstr->wcs[char_idx] = (wchar_t) pstr->mbs[char_idx];
255           mbs_upper[char_idx] = pstr->mbs[char_idx];
256           state = prev_st;
257         }
258       else /* mbclen > 1 */
259         {
260           pstr->wcs[char_idx] = wc;
261           if (iswlower (wc))
262             wcrtomb (mbs_upper + char_idx, towupper (wc), &prev_st);
263           else
264             memcpy (mbs_upper + char_idx, pstr->mbs + char_idx, mbclen);
265           for (byte_idx = 1 ; byte_idx < mbclen ; byte_idx++)
266             pstr->wcs[char_idx + byte_idx] = WEOF;
267         }
268     }
269   pstr->mbs = mbs_upper;
270   pstr->mbs_alloc = 1;
271   return REG_NOERROR;
272 }
273 #endif /* RE_ENABLE_I18N  */
274
275 static reg_errcode_t
276 build_upper_buffer (pstr)
277      re_string_t *pstr;
278 {
279   unsigned char *mbs_upper;
280   int char_idx, char_len;
281
282   mbs_upper = re_malloc (unsigned char, pstr->len + 1);
283   if (mbs_upper == NULL)
284     return REG_ESPACE;
285
286   char_len = pstr->len;
287   for (char_idx = 0 ; char_idx < char_len ; char_idx ++)
288     {
289       if (islower (pstr->mbs[char_idx]))
290         mbs_upper[char_idx] = toupper (pstr->mbs[char_idx]);
291       else
292         mbs_upper[char_idx] = pstr->mbs[char_idx];
293     }
294   pstr->mbs = mbs_upper;
295   pstr->mbs_alloc = 1;
296   return REG_NOERROR;
297 }
298
299 /* Apply TRANS to the buffer in PSTR.  We assume that wide char buffer
300    is already constructed if MB_CUR_MAX > 1.  */
301
302 static reg_errcode_t
303 re_string_translate_buffer (pstr, trans)
304      re_string_t *pstr;
305      RE_TRANSLATE_TYPE trans;
306 {
307   int buf_idx;
308   unsigned char *transed_buf, *transed_case_buf;
309 #ifdef DEBUG
310   assert (trans != NULL);
311 #endif
312   if (pstr->mbs_alloc)
313     {
314       transed_buf = (unsigned char *) pstr->mbs;
315       transed_case_buf = re_malloc (unsigned char, pstr->len + 1);
316       if (transed_case_buf == NULL)
317         return REG_ESPACE;
318       pstr->mbs_case_alloc = 1;
319     }
320   else
321     {
322       transed_buf = re_malloc (unsigned char, pstr->len + 1);
323       if (transed_buf == NULL)
324         return REG_ESPACE;
325       transed_case_buf = NULL;
326       pstr->mbs_alloc = 1;
327     }
328   for (buf_idx = 0 ; buf_idx < pstr->len ; buf_idx++)
329     {
330 #ifdef RE_ENABLE_I18N
331       if (MB_CUR_MAX > 1 && !re_string_is_single_byte_char (pstr, buf_idx))
332         transed_buf[buf_idx] = pstr->mbs[buf_idx];
333       else
334 #endif
335         transed_buf[buf_idx] = trans[pstr->mbs[buf_idx]];
336       if (transed_case_buf)
337         {
338 #ifdef RE_ENABLE_I18N
339          if (MB_CUR_MAX > 1 && !re_string_is_single_byte_char (pstr, buf_idx))
340             transed_case_buf[buf_idx] = pstr->mbs_case[buf_idx];
341           else
342 #endif
343             transed_case_buf[buf_idx] = trans[pstr->mbs_case[buf_idx]];
344         }
345     }
346   if (pstr->mbs_case_alloc == 1)
347     {
348       pstr->mbs = transed_buf;
349       pstr->mbs_case = transed_case_buf;
350     }
351   else
352     {
353       pstr->mbs = transed_buf;
354       pstr->mbs_case = transed_buf;
355     }
356   return REG_NOERROR;
357 }
358
359 static void
360 re_string_destruct (pstr)
361      re_string_t *pstr;
362 {
363 #ifdef RE_ENABLE_I18N
364   re_free (pstr->wcs);
365 #endif /* RE_ENABLE_I18N  */
366   if (pstr->mbs_alloc)
367     re_free ((void *) pstr->mbs);
368   if (pstr->mbs_case_alloc)
369     re_free ((void *) pstr->mbs_case);
370 }
371
372 /* Return the context at IDX in INPUT.  */
373 static unsigned int
374 re_string_context_at (input, idx, eflags, newline_anchor)
375      const re_string_t *input;
376      int idx, eflags, newline_anchor;
377 {
378   int c;
379   if (idx < 0 || idx == input->len)
380     {
381       unsigned int context = 0;
382       if (idx < 0)
383         context = CONTEXT_BEGBUF;
384       else if (idx == input->len)
385         context = CONTEXT_ENDBUF;
386
387       if ((idx < 0 && !(eflags & REG_NOTBOL))
388           || (idx == input->len && !(eflags & REG_NOTEOL)))
389         return CONTEXT_NEWLINE | context;
390       else
391         return context;
392     }
393   c = re_string_byte_at (input, idx);
394   if (IS_WORD_CHAR (c))
395     return CONTEXT_WORD;
396   return (newline_anchor && IS_NEWLINE (c)) ? CONTEXT_NEWLINE : 0;
397 }
398 \f
399 /* Functions for set operation.  */
400
401 static reg_errcode_t
402 re_node_set_alloc (set, size)
403      re_node_set *set;
404      int size;
405 {
406   set->alloc = size;
407   set->nelem = 0;
408   set->elems = re_malloc (int, size);
409   if (set->elems == NULL)
410     return REG_ESPACE;
411   return REG_NOERROR;
412 }
413
414 static reg_errcode_t
415 re_node_set_init_1 (set, elem)
416      re_node_set *set;
417      int elem;
418 {
419   set->alloc = 1;
420   set->nelem = 1;
421   set->elems = re_malloc (int, 1);
422   if (set->elems == NULL)
423     return REG_ESPACE;
424   set->elems[0] = elem;
425   return REG_NOERROR;
426 }
427
428 static reg_errcode_t
429 re_node_set_init_2 (set, elem1, elem2)
430      re_node_set *set;
431      int elem1, elem2;
432 {
433   set->alloc = 2;
434   set->elems = re_malloc (int, 2);
435   if (set->elems == NULL)
436     return REG_ESPACE;
437   if (elem1 == elem2)
438     {
439       set->nelem = 1;
440       set->elems[0] = elem1;
441     }
442   else
443     {
444       set->nelem = 2;
445       if (elem1 < elem2)
446         {
447           set->elems[0] = elem1;
448           set->elems[1] = elem2;
449         }
450       else
451         {
452           set->elems[0] = elem2;
453           set->elems[1] = elem1;
454         }
455     }
456   return REG_NOERROR;
457 }
458
459 static reg_errcode_t
460 re_node_set_init_copy (dest, src)
461      re_node_set *dest;
462      const re_node_set *src;
463 {
464   dest->nelem = src->nelem;
465   if (src->nelem > 0)
466     {
467       dest->alloc = dest->nelem;
468       dest->elems = re_malloc (int, dest->alloc);
469       if (dest->elems == NULL)
470         return REG_ESPACE;
471       memcpy (dest->elems, src->elems, src->nelem * sizeof (int));
472     }
473   else
474     re_node_set_init_empty (dest);
475   return REG_NOERROR;
476 }
477
478 /* Calculate the intersection of the sets SRC1 and SRC2. And store it in
479    DEST. Return value indicate the error code or REG_NOERROR if succeeded.
480    Note: We assume dest->elems is NULL, when dest->alloc is 0.  */
481
482 static reg_errcode_t
483 re_node_set_intersect (dest, src1, src2)
484      re_node_set *dest;
485      const re_node_set *src1, *src2;
486 {
487   int i1, i2, id;
488   if (src1->nelem > 0 && src2->nelem > 0)
489     {
490       if (src1->nelem + src2->nelem > dest->alloc)
491         {
492           dest->alloc = src1->nelem + src2->nelem;
493           dest->elems = re_realloc (dest->elems, int, dest->alloc);
494           if (dest->elems == NULL)
495             return REG_ESPACE;
496         }
497     }
498   else
499     {
500       /* The intersection of empty sets is also empty set.  */
501       dest->nelem = 0;
502       return REG_NOERROR;
503     }
504
505   for (i1 = i2 = id = 0; i1 < src1->nelem && i2 < src2->nelem; )
506     {
507       if (src1->elems[i1] > src2->elems[i2])
508         {
509           ++i2;
510           continue;
511         }
512       /* The intersection must have the elements which are in both of
513          SRC1 and SRC2.  */
514       if (src1->elems[i1] == src2->elems[i2])
515         dest->elems[id++] = src2->elems[i2++];
516       ++i1;
517     }
518   dest->nelem = id;
519   return REG_NOERROR;
520 }
521
522 /* Calculate the intersection of the sets SRC1 and SRC2. And merge it to
523    DEST. Return value indicate the error code or REG_NOERROR if succeeded.
524    Note: We assume dest->elems is NULL, when dest->alloc is 0.  */
525
526 static reg_errcode_t
527 re_node_set_add_intersect (dest, src1, src2)
528      re_node_set *dest;
529      const re_node_set *src1, *src2;
530 {
531   int i1, i2, id;
532   if (src1->nelem > 0 && src2->nelem > 0)
533     {
534       if (src1->nelem + src2->nelem + dest->nelem > dest->alloc)
535         {
536           dest->alloc = src1->nelem + src2->nelem + dest->nelem;
537           dest->elems = re_realloc (dest->elems, int, dest->alloc);
538           if (dest->elems == NULL)
539             return REG_ESPACE;
540         }
541     }
542   else
543     return REG_NOERROR;
544
545   for (i1 = i2 = id = 0 ; i1 < src1->nelem && i2 < src2->nelem ;)
546     {
547       if (src1->elems[i1] > src2->elems[i2])
548         {
549           ++i2;
550           continue;
551         }
552       if (src1->elems[i1] == src2->elems[i2])
553         {
554           while (id < dest->nelem && dest->elems[id] < src2->elems[i2])
555             ++id;
556           if (id < dest->nelem && dest->elems[id] == src2->elems[i2])
557             ++id;
558           else
559             {
560               memmove (dest->elems + id + 1, dest->elems + id,
561                        sizeof (int) * (dest->nelem - id));
562               dest->elems[id++] = src2->elems[i2++];
563               ++dest->nelem;
564             }
565         }
566       ++i1;
567     }
568   return REG_NOERROR;
569 }
570
571 /* Calculate the union set of the sets SRC1 and SRC2. And store it to
572    DEST. Return value indicate the error code or REG_NOERROR if succeeded.  */
573
574 static reg_errcode_t
575 re_node_set_init_union (dest, src1, src2)
576      re_node_set *dest;
577      const re_node_set *src1, *src2;
578 {
579   int i1, i2, id;
580   if (src1 != NULL && src1->nelem > 0 && src2 != NULL && src2->nelem > 0)
581     {
582       dest->alloc = src1->nelem + src2->nelem;
583       dest->elems = re_malloc (int, dest->alloc);
584       if (dest->elems == NULL)
585         return REG_ESPACE;
586     }
587   else
588     {
589       if (src1 != NULL && src1->nelem > 0)
590         return re_node_set_init_copy (dest, src1);
591       else if (src2 != NULL && src2->nelem > 0)
592         return re_node_set_init_copy (dest, src2);
593       else
594         re_node_set_init_empty (dest);
595       return REG_NOERROR;
596     }
597   for (i1 = i2 = id = 0 ; i1 < src1->nelem && i2 < src2->nelem ;)
598     {
599       if (src1->elems[i1] > src2->elems[i2])
600         {
601           dest->elems[id++] = src2->elems[i2++];
602           continue;
603         }
604       if (src1->elems[i1] == src2->elems[i2])
605         ++i2;
606       dest->elems[id++] = src1->elems[i1++];
607     }
608   if (i1 < src1->nelem)
609     {
610       memcpy (dest->elems + id, src1->elems + i1,
611              (src1->nelem - i1) * sizeof (int));
612       id += src1->nelem - i1;
613     }
614   else if (i2 < src2->nelem)
615     {
616       memcpy (dest->elems + id, src2->elems + i2,
617              (src2->nelem - i2) * sizeof (int));
618       id += src2->nelem - i2;
619     }
620   dest->nelem = id;
621   return REG_NOERROR;
622 }
623
624 /* Calculate the union set of the sets DEST and SRC. And store it to
625    DEST. Return value indicate the error code or REG_NOERROR if succeeded.  */
626
627 static reg_errcode_t
628 re_node_set_merge (dest, src)
629      re_node_set *dest;
630      const re_node_set *src;
631 {
632   int si, di;
633   if (src == NULL || src->nelem == 0)
634     return REG_NOERROR;
635   else if (dest == NULL)
636     {
637       dest = re_malloc (re_node_set, 1);
638       if (dest == NULL)
639         return REG_ESPACE;
640       return re_node_set_init_copy (dest, src);
641     }
642   if (dest->alloc < src->nelem + dest->nelem)
643     {
644       dest->alloc = 2 * (src->nelem + dest->alloc);
645       dest->elems = re_realloc (dest->elems, int, dest->alloc);
646       if (dest->elems == NULL)
647         return REG_ESPACE;
648     }
649
650   for (si = 0, di = 0 ; si < src->nelem && di < dest->nelem ;)
651     {
652       int cp_from, ncp, mid, right, src_elem = src->elems[si];
653       /* Binary search the spot we will add the new element.  */
654       right = dest->nelem;
655       while (di < right)
656         {
657           mid = (di + right) / 2;
658           if (dest->elems[mid] < src_elem)
659             di = mid + 1;
660           else
661             right = mid;
662         }
663       if (di >= dest->nelem)
664         break;
665
666       if (dest->elems[di] == src_elem)
667         {
668           /* Skip since, DEST already has the element.  */
669           ++di;
670           ++si;
671           continue;
672         }
673
674       /* Skip the src elements which are less than dest->elems[di].  */
675       cp_from = si;
676       while (si < src->nelem && src->elems[si] < dest->elems[di])
677         ++si;
678       /* Copy these src elements.  */
679       ncp = si - cp_from;
680       memmove (dest->elems + di + ncp, dest->elems + di,
681                sizeof (int) * (dest->nelem - di));
682       memcpy (dest->elems + di, src->elems + cp_from,
683               sizeof (int) * ncp);
684       /* Update counters.  */
685       di += ncp;
686       dest->nelem += ncp;
687     }
688
689   /* Copy remaining src elements.  */
690   if (si < src->nelem)
691     {
692       memcpy (dest->elems + di, src->elems + si,
693               sizeof (int) * (src->nelem - si));
694       dest->nelem += src->nelem - si;
695     }
696   return REG_NOERROR;
697 }
698
699 /* Insert the new element ELEM to the re_node_set* SET.
700    return 0 if SET already has ELEM,
701    return -1 if an error is occured, return 1 otherwise.  */
702
703 static int
704 re_node_set_insert (set, elem)
705      re_node_set *set;
706      int elem;
707 {
708   int idx, right, mid;
709   /* In case of the set is empty.  */
710   if (set->elems == NULL || set->alloc == 0)
711     {
712       if (re_node_set_init_1 (set, elem) == REG_NOERROR)
713         return 1;
714       else
715         return -1;
716     }
717
718   /* Binary search the spot we will add the new element.  */
719   idx = 0;
720   right = set->nelem;
721   while (idx < right)
722     {
723       mid = (idx + right) / 2;
724       if (set->elems[mid] < elem)
725         idx = mid + 1;
726       else
727         right = mid;
728     }
729
730   /* Realloc if we need.  */
731   if (set->alloc < set->nelem + 1)
732     {
733       int *new_array;
734       set->alloc = set->alloc * 2;
735       new_array = re_malloc (int, set->alloc);
736       if (new_array == NULL)
737         return -1;
738       /* Copy the elements they are followed by the new element.  */
739       if (idx > 0)
740         memcpy (new_array, set->elems, sizeof (int) * (idx));
741       /* Copy the elements which follows the new element.  */
742       if (set->nelem - idx > 0)
743         memcpy (new_array + idx + 1, set->elems + idx,
744                 sizeof (int) * (set->nelem - idx));
745       set->elems = new_array;
746     }
747   else
748     {
749       /* Move the elements which follows the new element.  */
750       if (set->nelem - idx > 0)
751         memmove (set->elems + idx + 1, set->elems + idx,
752                  sizeof (int) * (set->nelem - idx));
753     }
754   /* Insert the new element.  */
755   set->elems[idx] = elem;
756   ++set->nelem;
757   return 1;
758 }
759
760 /* Compare two node sets SET1 and SET2.
761    return 1 if SET1 and SET2 are equivalent, retrun 0 otherwise.  */
762
763 static int
764 re_node_set_compare (set1, set2)
765      const re_node_set *set1, *set2;
766 {
767   int i;
768   if (set1 == NULL || set2 == NULL || set1->nelem != set2->nelem)
769     return 0;
770   for (i = 0 ; i < set1->nelem ; i++)
771     if (set1->elems[i] != set2->elems[i])
772       return 0;
773   return 1;
774 }
775
776 /* Return 1 if SET contains the element ELEM, return 0 otherwise.  */
777
778 static int
779 re_node_set_contains (set, elem)
780      const re_node_set *set;
781      int elem;
782 {
783   int idx, right, mid;
784   if (set->nelem <= 0)
785     return 0;
786
787   /* Binary search the element.  */
788   idx = 0;
789   right = set->nelem - 1;
790   while (idx < right)
791     {
792       mid = (idx + right) / 2;
793       if (set->elems[mid] < elem)
794         idx = mid + 1;
795       else
796         right = mid;
797     }
798   return set->elems[idx] == elem;
799 }
800
801 static void
802 re_node_set_remove_at (set, idx)
803      re_node_set *set;
804      int idx;
805 {
806   if (idx < 0 || idx >= set->nelem)
807     return;
808   if (idx < set->nelem - 1)
809     memmove (set->elems + idx, set->elems + idx + 1,
810              sizeof (int) * (set->nelem - idx - 1));
811   --set->nelem;
812 }
813 \f
814
815 /* Add the token TOKEN to dfa->nodes, and return the index of the token.
816    Or return -1, if an error will be occured.  */
817
818 static int
819 re_dfa_add_node (dfa, token, mode)
820      re_dfa_t *dfa;
821      re_token_t token;
822      int mode;
823 {
824   if (dfa->nodes_len >= dfa->nodes_alloc)
825     {
826       re_token_t *new_array;
827       dfa->nodes_alloc *= 2;
828       new_array = re_realloc (dfa->nodes, re_token_t, dfa->nodes_alloc);
829       if (new_array == NULL)
830         return -1;
831       else
832         dfa->nodes = new_array;
833       if (mode)
834         {
835           int *new_firsts, *new_nexts;
836           re_node_set *new_edests, *new_eclosures, *new_inveclosures;
837
838           new_firsts = re_realloc (dfa->firsts, int, dfa->nodes_alloc);
839           new_nexts = re_realloc (dfa->nexts, int, dfa->nodes_alloc);
840           new_edests = re_realloc (dfa->edests, re_node_set, dfa->nodes_alloc);
841           new_eclosures = re_realloc (dfa->eclosures, re_node_set,
842                                       dfa->nodes_alloc);
843           new_inveclosures = re_realloc (dfa->inveclosures, re_node_set,
844                                          dfa->nodes_alloc);
845           if (new_firsts == NULL || new_nexts == NULL || new_edests == NULL
846               || new_eclosures == NULL || new_inveclosures == NULL)
847             return -1;
848           dfa->firsts = new_firsts;
849           dfa->nexts = new_nexts;
850           dfa->edests = new_edests;
851           dfa->eclosures = new_eclosures;
852           dfa->inveclosures = new_inveclosures;
853         }
854     }
855   dfa->nodes[dfa->nodes_len] = token;
856   dfa->nodes[dfa->nodes_len].duplicated = 0;
857   return dfa->nodes_len++;
858 }
859
860 static unsigned int inline
861 calc_state_hash (nodes, context)
862      const re_node_set *nodes;
863      unsigned int context;
864 {
865   unsigned int hash = nodes->nelem + context;
866   int i;
867   for (i = 0 ; i < nodes->nelem ; i++)
868     hash += nodes->elems[i];
869   return hash;
870 }
871
872 /* Search for the state whose node_set is equivalent to NODES.
873    Return the pointer to the state, if we found it in the DFA.
874    Otherwise create the new one and return it.  In case of an error
875    return NULL and set the error code in ERR.
876    Note: - We assume NULL as the invalid state, then it is possible that
877            return value is NULL and ERR is REG_NOERROR.
878          - We never return non-NULL value in case of any errors, it is for
879            optimization.  */
880
881 static re_dfastate_t*
882 re_acquire_state (err, dfa, nodes)
883      reg_errcode_t *err;
884      re_dfa_t *dfa;
885      const re_node_set *nodes;
886 {
887   unsigned int hash;
888   re_dfastate_t *new_state;
889   struct re_state_table_entry *spot;
890   int i;
891   if (nodes->nelem == 0)
892     {
893       *err = REG_NOERROR;
894       return NULL;
895     }
896   hash = calc_state_hash (nodes, 0);
897   spot = dfa->state_table + (hash & dfa->state_hash_mask);
898
899   if (spot->alloc == 0)
900     {
901       /* Currently there are only one state in this spot.  */
902       if (spot->entry.state != NULL && hash == spot->entry.state->hash
903           && re_node_set_compare (&spot->entry.state->nodes, nodes))
904         return spot->entry.state;
905     }
906   else
907     for (i = 0 ; i < spot->num ; i++)
908       {
909         re_dfastate_t *state = spot->entry.array[i];
910         if (hash != state->hash)
911           continue;
912         if (re_node_set_compare (&state->nodes, nodes))
913           return state;
914       }
915
916   /* There are no appropriate state in the dfa, create the new one.  */
917   new_state = create_ci_newstate (dfa, nodes, hash);
918   if (new_state != NULL)
919     return new_state;
920   else
921     {
922       *err = REG_ESPACE;
923       return NULL;
924     }
925 }
926
927 /* Search for the state whose node_set is equivalent to NODES and
928    whose context is equivalent to CONTEXT.
929    Return the pointer to the state, if we found it in the DFA.
930    Otherwise create the new one and return it.  In case of an error
931    return NULL and set the error code in ERR.
932    Note: - We assume NULL as the invalid state, then it is possible that
933            return value is NULL and ERR is REG_NOERROR.
934          - We never return non-NULL value in case of any errors, it is for
935            optimization.  */
936
937 static re_dfastate_t*
938 re_acquire_state_context (err, dfa, nodes, context)
939      reg_errcode_t *err;
940      re_dfa_t *dfa;
941      const re_node_set *nodes;
942      unsigned int context;
943 {
944   unsigned int hash;
945   re_dfastate_t *new_state;
946   struct re_state_table_entry *spot;
947   int i;
948   if (nodes->nelem == 0)
949     {
950       *err = REG_NOERROR;
951       return NULL;
952     }
953   hash = calc_state_hash (nodes, context);
954   spot = dfa->state_table + (hash & dfa->state_hash_mask);
955
956   if (spot->alloc == 0)
957     {
958       /* Currently there are only one state in this spot.  */
959       if (spot->entry.state != NULL && hash == spot->entry.state->hash
960           && re_node_set_compare (&spot->entry.state->nodes, nodes)
961           && spot->entry.state->context == context)
962         return spot->entry.state;
963     }
964   else
965     for (i = 0 ; i < spot->num ; i++)
966       {
967         re_dfastate_t *state = spot->entry.array[i];
968         if (hash != state->hash)
969           continue;
970         if (re_node_set_compare (state->entrance_nodes, nodes)
971             && state->context == context)
972           return state;
973       }
974   /* There are no appropriate state in `dfa', create the new one.  */
975   new_state = create_cd_newstate (dfa, nodes, context, hash);
976   if (new_state != NULL)
977     return new_state;
978   else
979     {
980       *err = REG_ESPACE;
981       return NULL;
982     }
983 }
984
985 /* Allocate memory for DFA state and initialize common properties.
986    Return the new state if succeeded, otherwise return NULL.  */
987
988 static re_dfastate_t *
989 create_newstate_common (dfa, nodes, hash)
990      re_dfa_t *dfa;
991      const re_node_set *nodes;
992      unsigned int hash;
993 {
994   re_dfastate_t *newstate;
995   newstate = (re_dfastate_t *) calloc (sizeof (re_dfastate_t), 1);
996   if (newstate == NULL)
997     return NULL;
998   re_node_set_init_copy (&newstate->nodes, nodes);
999   newstate->trtable = NULL;
1000   newstate->trtable_search = NULL;
1001   newstate->hash = hash;
1002   return newstate;
1003 }
1004
1005 /* Store the new state NEWSTATE whose hash value is HASH in appropriate
1006    position.  Return value indicate the error code if failed.  */
1007
1008 static reg_errcode_t
1009 register_state (dfa, newstate, hash)
1010      re_dfa_t *dfa;
1011      re_dfastate_t *newstate;
1012      unsigned int hash;
1013 {
1014   struct re_state_table_entry *spot;
1015   spot = dfa->state_table + (hash & dfa->state_hash_mask);
1016
1017   if (spot->alloc <= spot->num)
1018     {
1019       re_dfastate_t **new_array;
1020
1021       /* XXX Is spot->entry.array == NULL if spot->alloc == 0?  If yes
1022          the if can go away and only realloc is needed.  */
1023       if (spot->alloc == 0)
1024         {
1025           spot->alloc = 4;
1026           new_array = re_malloc (re_dfastate_t *, spot->alloc);
1027           if (new_array == NULL)
1028             return REG_ESPACE;
1029           new_array[0] = spot->entry.state;
1030         }
1031       else
1032         {
1033           spot->alloc = 2 * spot->num;
1034           new_array = re_realloc (spot->entry.array, re_dfastate_t *,
1035                                   spot->alloc);
1036         }
1037       spot->entry.array = new_array;
1038     }
1039   spot->entry.array[spot->num++] = newstate;
1040   return REG_NOERROR;
1041 }
1042
1043 /* Create the new state which is independ of contexts.
1044    Return the new state if succeeded, otherwise return NULL.  */
1045
1046 static re_dfastate_t *
1047 create_ci_newstate (dfa, nodes, hash)
1048      re_dfa_t *dfa;
1049      const re_node_set *nodes;
1050      unsigned int hash;
1051 {
1052   int i;
1053   reg_errcode_t err;
1054   re_dfastate_t *newstate;
1055   newstate = create_newstate_common (dfa, nodes, hash);
1056   if (newstate == NULL)
1057     return NULL;
1058   newstate->entrance_nodes = &newstate->nodes;
1059
1060   for (i = 0 ; i < nodes->nelem ; i++)
1061     {
1062       re_token_t *node = dfa->nodes + nodes->elems[i];
1063       re_token_type_t type = node->type;
1064       if (type == CHARACTER)
1065         continue;
1066
1067       /* If the state has the halt node, the state is a halt state.  */
1068       else if (type == END_OF_RE)
1069         newstate->halt = 1;
1070       else if (type == COMPLEX_BRACKET
1071                || (type == OP_PERIOD && MB_CUR_MAX > 1))
1072         newstate->accept_mb = 1;
1073       else if (type == OP_BACK_REF)
1074         newstate->has_backref = 1;
1075       else if (type == ANCHOR || OP_CONTEXT_NODE)
1076         {
1077           newstate->has_constraint = 1;
1078           if (type == OP_CONTEXT_NODE
1079               && dfa->nodes[node->opr.ctx_info->entity].type == END_OF_RE)
1080             newstate->halt = 1;
1081         }
1082     }
1083   err = register_state (dfa, newstate, hash);
1084   return (err != REG_NOERROR) ? NULL : newstate;
1085 }
1086
1087 /* Create the new state which is depend on the context CONTEXT.
1088    Return the new state if succeeded, otherwise return NULL.  */
1089
1090 static re_dfastate_t *
1091 create_cd_newstate (dfa, nodes, context, hash)
1092      re_dfa_t *dfa;
1093      const re_node_set *nodes;
1094      unsigned int context, hash;
1095 {
1096   int i, nctx_nodes = 0;
1097   reg_errcode_t err;
1098   re_dfastate_t *newstate;
1099
1100   newstate = create_newstate_common (dfa, nodes, hash);
1101   if (newstate == NULL)
1102     return NULL;
1103   newstate->context = context;
1104   newstate->entrance_nodes = &newstate->nodes;
1105
1106   for (i = 0 ; i < nodes->nelem ; i++)
1107     {
1108       unsigned int constraint = 0;
1109       re_token_t *node = dfa->nodes + nodes->elems[i];
1110       re_token_type_t type = node->type;
1111       if (type == CHARACTER)
1112         continue;
1113
1114       /* If the state has the halt node, the state is a halt state.  */
1115       else if (type == END_OF_RE)
1116         newstate->halt = 1;
1117       else if (type == COMPLEX_BRACKET
1118                || (type == OP_PERIOD && MB_CUR_MAX > 1))
1119         newstate->accept_mb = 1;
1120       else if (type == OP_BACK_REF)
1121         newstate->has_backref = 1;
1122       else if (type == ANCHOR)
1123         constraint = node->opr.ctx_type;
1124       else if (type == OP_CONTEXT_NODE)
1125         {
1126           re_token_type_t ctype = dfa->nodes[node->opr.ctx_info->entity].type;
1127           constraint = node->constraint;
1128           if (ctype == END_OF_RE)
1129             newstate->halt = 1;
1130           else if (ctype == OP_BACK_REF)
1131             newstate->has_backref = 1;
1132           else if (ctype == COMPLEX_BRACKET
1133                    || (type == OP_PERIOD && MB_CUR_MAX > 1))
1134             newstate->accept_mb = 1;
1135         }
1136
1137       if (constraint)
1138         {
1139           if (newstate->entrance_nodes == &newstate->nodes)
1140             {
1141               newstate->entrance_nodes = re_malloc (re_node_set, 1);
1142               if (newstate->entrance_nodes == NULL)
1143                 return NULL;
1144               re_node_set_init_copy (newstate->entrance_nodes, nodes);
1145               nctx_nodes = 0;
1146               newstate->has_constraint = 1;
1147             }
1148
1149           if (NOT_SATISFY_PREV_CONSTRAINT (constraint,context))
1150             {
1151               re_node_set_remove_at (&newstate->nodes, i - nctx_nodes);
1152               ++nctx_nodes;
1153             }
1154         }
1155     }
1156   err = register_state (dfa, newstate, hash);
1157   return (err != REG_NOERROR) ? NULL : newstate;
1158 }