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