Don't use error to print error message, they won't end up in the .out file.
[kopensolaris-gnu/glibc.git] / posix / regex_internal.c
1 /* Extended regular expression matching and search library.
2    Copyright (C) 2002, 2003, 2004 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 static void re_string_construct_common (const char *str, int len,
22                                         re_string_t *pstr,
23                                         RE_TRANSLATE_TYPE trans, int icase,
24                                         const re_dfa_t *dfa) internal_function;
25 #ifdef RE_ENABLE_I18N
26 static int re_string_skip_chars (re_string_t *pstr, int new_raw_idx,
27                                  wint_t *last_wc) internal_function;
28 #endif /* RE_ENABLE_I18N */
29 static re_dfastate_t *create_newstate_common (re_dfa_t *dfa,
30                                               const re_node_set *nodes,
31                                               unsigned int hash) internal_function;
32 static reg_errcode_t register_state (re_dfa_t *dfa, re_dfastate_t *newstate,
33                                      unsigned int hash) internal_function;
34 static re_dfastate_t *create_ci_newstate (re_dfa_t *dfa,
35                                           const re_node_set *nodes,
36                                           unsigned int hash) internal_function;
37 static re_dfastate_t *create_cd_newstate (re_dfa_t *dfa,
38                                           const re_node_set *nodes,
39                                           unsigned int context,
40                                           unsigned int hash) internal_function;
41 static unsigned int inline calc_state_hash (const re_node_set *nodes,
42                                             unsigned int context) internal_function;
43 \f
44 /* Functions for string operation.  */
45
46 /* This function allocate the buffers.  It is necessary to call
47    re_string_reconstruct before using the object.  */
48
49 static reg_errcode_t
50 re_string_allocate (pstr, str, len, init_len, trans, icase, dfa)
51      re_string_t *pstr;
52      const char *str;
53      int len, init_len, icase;
54      RE_TRANSLATE_TYPE trans;
55      const re_dfa_t *dfa;
56 {
57   reg_errcode_t ret;
58   int init_buf_len;
59
60   /* Ensure at least one character fits into the buffers.  */
61   if (init_len < dfa->mb_cur_max)
62     init_len = dfa->mb_cur_max;
63   init_buf_len = (len + 1 < init_len) ? len + 1: init_len;
64   re_string_construct_common (str, len, pstr, trans, icase, dfa);
65
66   ret = re_string_realloc_buffers (pstr, init_buf_len);
67   if (BE (ret != REG_NOERROR, 0))
68     return ret;
69
70   pstr->word_char = dfa->word_char;
71   pstr->word_ops_used = dfa->word_ops_used;
72   pstr->mbs = pstr->mbs_allocated ? pstr->mbs : (unsigned char *) str;
73   pstr->valid_len = (pstr->mbs_allocated || dfa->mb_cur_max > 1) ? 0 : len;
74   pstr->valid_raw_len = pstr->valid_len;
75   return REG_NOERROR;
76 }
77
78 /* This function allocate the buffers, and initialize them.  */
79
80 static reg_errcode_t
81 re_string_construct (pstr, str, len, trans, icase, dfa)
82      re_string_t *pstr;
83      const char *str;
84      int len, icase;
85      RE_TRANSLATE_TYPE trans;
86      const re_dfa_t *dfa;
87 {
88   reg_errcode_t ret;
89   memset (pstr, '\0', sizeof (re_string_t));
90   re_string_construct_common (str, len, pstr, trans, icase, dfa);
91
92   if (len > 0)
93     {
94       ret = re_string_realloc_buffers (pstr, len + 1);
95       if (BE (ret != REG_NOERROR, 0))
96         return ret;
97     }
98   pstr->mbs = pstr->mbs_allocated ? pstr->mbs : (unsigned char *) str;
99
100   if (icase)
101     {
102 #ifdef RE_ENABLE_I18N
103       if (dfa->mb_cur_max > 1)
104         {
105           while (1)
106             {
107               ret = build_wcs_upper_buffer (pstr);
108               if (BE (ret != REG_NOERROR, 0))
109                 return ret;
110               if (pstr->valid_raw_len >= len)
111                 break;
112               if (pstr->bufs_len > pstr->valid_len + dfa->mb_cur_max)
113                 break;
114               ret = re_string_realloc_buffers (pstr, pstr->bufs_len * 2);
115               if (BE (ret != REG_NOERROR, 0))
116                 return ret;
117             }
118         }
119       else
120 #endif /* RE_ENABLE_I18N  */
121         build_upper_buffer (pstr);
122     }
123   else
124     {
125 #ifdef RE_ENABLE_I18N
126       if (dfa->mb_cur_max > 1)
127         build_wcs_buffer (pstr);
128       else
129 #endif /* RE_ENABLE_I18N  */
130         {
131           if (trans != NULL)
132             re_string_translate_buffer (pstr);
133           else
134             {
135               pstr->valid_len = pstr->bufs_len;
136               pstr->valid_raw_len = pstr->bufs_len;
137             }
138         }
139     }
140
141   return REG_NOERROR;
142 }
143
144 /* Helper functions for re_string_allocate, and re_string_construct.  */
145
146 static reg_errcode_t
147 re_string_realloc_buffers (pstr, new_buf_len)
148      re_string_t *pstr;
149      int new_buf_len;
150 {
151 #ifdef RE_ENABLE_I18N
152   if (pstr->mb_cur_max > 1)
153     {
154       wint_t *new_array = re_realloc (pstr->wcs, wint_t, new_buf_len);
155       if (BE (new_array == NULL, 0))
156         return REG_ESPACE;
157       pstr->wcs = new_array;
158       if (pstr->offsets != NULL)
159         {
160           int *new_array = re_realloc (pstr->offsets, int, new_buf_len);
161           if (BE (new_array == NULL, 0))
162             return REG_ESPACE;
163           pstr->offsets = new_array;
164         }
165     }
166 #endif /* RE_ENABLE_I18N  */
167   if (pstr->mbs_allocated)
168     {
169       unsigned char *new_array = re_realloc (pstr->mbs, unsigned char,
170                                              new_buf_len);
171       if (BE (new_array == NULL, 0))
172         return REG_ESPACE;
173       pstr->mbs = new_array;
174     }
175   pstr->bufs_len = new_buf_len;
176   return REG_NOERROR;
177 }
178
179
180 static void
181 re_string_construct_common (str, len, pstr, trans, icase, dfa)
182      const char *str;
183      int len;
184      re_string_t *pstr;
185      RE_TRANSLATE_TYPE trans;
186      int icase;
187      const re_dfa_t *dfa;
188 {
189   pstr->raw_mbs = (const unsigned char *) str;
190   pstr->len = len;
191   pstr->raw_len = len;
192   pstr->trans = (unsigned RE_TRANSLATE_TYPE) trans;
193   pstr->icase = icase ? 1 : 0;
194   pstr->mbs_allocated = (trans != NULL || icase);
195   pstr->mb_cur_max = dfa->mb_cur_max;
196   pstr->is_utf8 = dfa->is_utf8;
197   pstr->map_notascii = dfa->map_notascii;
198   pstr->stop = pstr->len;
199   pstr->raw_stop = pstr->stop;
200 }
201
202 #ifdef RE_ENABLE_I18N
203
204 /* Build wide character buffer PSTR->WCS.
205    If the byte sequence of the string are:
206      <mb1>(0), <mb1>(1), <mb2>(0), <mb2>(1), <sb3>
207    Then wide character buffer will be:
208      <wc1>   , WEOF    , <wc2>   , WEOF    , <wc3>
209    We use WEOF for padding, they indicate that the position isn't
210    a first byte of a multibyte character.
211
212    Note that this function assumes PSTR->VALID_LEN elements are already
213    built and starts from PSTR->VALID_LEN.  */
214
215 static void
216 build_wcs_buffer (pstr)
217      re_string_t *pstr;
218 {
219 #ifdef _LIBC
220   unsigned char buf[pstr->mb_cur_max];
221 #else
222   unsigned char buf[64];
223 #endif
224   mbstate_t prev_st;
225   int byte_idx, end_idx, mbclen, remain_len;
226
227   /* Build the buffers from pstr->valid_len to either pstr->len or
228      pstr->bufs_len.  */
229   end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len;
230   for (byte_idx = pstr->valid_len; byte_idx < end_idx;)
231     {
232       wchar_t wc;
233       const char *p;
234
235       remain_len = end_idx - byte_idx;
236       prev_st = pstr->cur_state;
237       /* Apply the translation if we need.  */
238       if (BE (pstr->trans != NULL, 0))
239         {
240           int i, ch;
241
242           for (i = 0; i < pstr->mb_cur_max && i < remain_len; ++i)
243             {
244               ch = pstr->raw_mbs [pstr->raw_mbs_idx + byte_idx + i];
245               buf[i] = pstr->mbs[byte_idx + i] = pstr->trans[ch];
246             }
247           p = (const char *) buf;
248         }
249       else
250         p = (const char *) pstr->raw_mbs + pstr->raw_mbs_idx + byte_idx;
251       mbclen = mbrtowc (&wc, p, remain_len, &pstr->cur_state);
252       if (BE (mbclen == (size_t) -2, 0))
253         {
254           /* The buffer doesn't have enough space, finish to build.  */
255           pstr->cur_state = prev_st;
256           break;
257         }
258       else if (BE (mbclen == (size_t) -1 || mbclen == 0, 0))
259         {
260           /* We treat these cases as a singlebyte character.  */
261           mbclen = 1;
262           wc = (wchar_t) pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx];
263           if (BE (pstr->trans != NULL, 0))
264             wc = pstr->trans[wc];
265           pstr->cur_state = prev_st;
266         }
267
268       /* Write wide character and padding.  */
269       pstr->wcs[byte_idx++] = wc;
270       /* Write paddings.  */
271       for (remain_len = byte_idx + mbclen - 1; byte_idx < remain_len ;)
272         pstr->wcs[byte_idx++] = WEOF;
273     }
274   pstr->valid_len = byte_idx;
275   pstr->valid_raw_len = byte_idx;
276 }
277
278 /* Build wide character buffer PSTR->WCS like build_wcs_buffer,
279    but for REG_ICASE.  */
280
281 static int
282 build_wcs_upper_buffer (pstr)
283      re_string_t *pstr;
284 {
285   mbstate_t prev_st;
286   int src_idx, byte_idx, end_idx, mbclen, remain_len;
287 #ifdef _LIBC
288   unsigned char buf[pstr->mb_cur_max];
289 #else
290   unsigned char buf[64];
291 #endif
292
293   byte_idx = pstr->valid_len;
294   end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len;
295
296   /* The following optimization assumes that ASCII characters can be
297      mapped to wide characters with a simple cast.  */
298   if (! pstr->map_notascii && pstr->trans == NULL && !pstr->offsets_needed)
299     {
300       while (byte_idx < end_idx)
301         {
302           wchar_t wc;
303
304           if (isascii (pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx])
305               && mbsinit (&pstr->cur_state))
306             {
307               /* In case of a singlebyte character.  */
308               pstr->mbs[byte_idx]
309                 = toupper (pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx]);
310               /* The next step uses the assumption that wchar_t is encoded
311                  ASCII-safe: all ASCII values can be converted like this.  */
312               pstr->wcs[byte_idx] = (wchar_t) pstr->mbs[byte_idx];
313               ++byte_idx;
314               continue;
315             }
316
317           remain_len = end_idx - byte_idx;
318           prev_st = pstr->cur_state;
319           mbclen = mbrtowc (&wc,
320                             ((const char *) pstr->raw_mbs + pstr->raw_mbs_idx
321                              + byte_idx), remain_len, &pstr->cur_state);
322           if (BE (mbclen > 0, 1))
323             {
324               wchar_t wcu = wc;
325               if (iswlower (wc))
326                 {
327                   int mbcdlen;
328
329                   wcu = towupper (wc);
330                   mbcdlen = wcrtomb (buf, wcu, &prev_st);
331                   if (BE (mbclen == mbcdlen, 1))
332                     memcpy (pstr->mbs + byte_idx, buf, mbclen);
333                   else
334                     {
335                       src_idx = byte_idx;
336                       goto offsets_needed;
337                     }
338                 }
339               else
340                 memcpy (pstr->mbs + byte_idx,
341                         pstr->raw_mbs + pstr->raw_mbs_idx + byte_idx, mbclen);
342               pstr->wcs[byte_idx++] = wcu;
343               /* Write paddings.  */
344               for (remain_len = byte_idx + mbclen - 1; byte_idx < remain_len ;)
345                 pstr->wcs[byte_idx++] = WEOF;
346             }
347           else if (mbclen == (size_t) -1 || mbclen == 0)
348             {
349               /* It is an invalid character or '\0'.  Just use the byte.  */
350               int ch = pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx];
351               pstr->mbs[byte_idx] = ch;
352               /* And also cast it to wide char.  */
353               pstr->wcs[byte_idx++] = (wchar_t) ch;
354               if (BE (mbclen == (size_t) -1, 0))
355                 pstr->cur_state = prev_st;
356             }
357           else
358             {
359               /* The buffer doesn't have enough space, finish to build.  */
360               pstr->cur_state = prev_st;
361               break;
362             }
363         }
364       pstr->valid_len = byte_idx;
365       pstr->valid_raw_len = byte_idx;
366       return REG_NOERROR;
367     }
368   else
369     for (src_idx = pstr->valid_raw_len; byte_idx < end_idx;)
370       {
371         wchar_t wc;
372         const char *p;
373       offsets_needed:
374         remain_len = end_idx - byte_idx;
375         prev_st = pstr->cur_state;
376         if (BE (pstr->trans != NULL, 0))
377           {
378             int i, ch;
379
380             for (i = 0; i < pstr->mb_cur_max && i < remain_len; ++i)
381               {
382                 ch = pstr->raw_mbs [pstr->raw_mbs_idx + src_idx + i];
383                 buf[i] = pstr->trans[ch];
384               }
385             p = (const char *) buf;
386           }
387         else
388           p = (const char *) pstr->raw_mbs + pstr->raw_mbs_idx + src_idx;
389         mbclen = mbrtowc (&wc, p, remain_len, &pstr->cur_state);
390         if (BE (mbclen > 0, 1))
391           {
392             wchar_t wcu = wc;
393             if (iswlower (wc))
394               {
395                 int mbcdlen;
396
397                 wcu = towupper (wc);
398                 mbcdlen = wcrtomb ((char *) buf, wcu, &prev_st);
399                 if (BE (mbclen == mbcdlen, 1))
400                   memcpy (pstr->mbs + byte_idx, buf, mbclen);
401                 else
402                   {
403                     int i;
404
405                     if (byte_idx + mbcdlen > pstr->bufs_len)
406                       {
407                         pstr->cur_state = prev_st;
408                         break;
409                       }
410
411                     if (pstr->offsets == NULL)
412                       {
413                         pstr->offsets = re_malloc (int, pstr->bufs_len);
414
415                         if (pstr->offsets == NULL)
416                           return REG_ESPACE;
417                       }
418                     if (!pstr->offsets_needed)
419                       {
420                         for (i = 0; i < byte_idx; ++i)
421                           pstr->offsets[i] = i;
422                         pstr->offsets_needed = 1;
423                       }
424
425                     memcpy (pstr->mbs + byte_idx, buf, mbcdlen);
426                     pstr->wcs[byte_idx] = wcu;
427                     pstr->offsets[byte_idx] = src_idx;
428                     for (i = 1; i < mbcdlen; ++i)
429                       {
430                         pstr->offsets[byte_idx + i]
431                           = src_idx + (i < mbclen ? i : mbclen - 1);
432                         pstr->wcs[byte_idx + i] = WEOF;
433                       }
434                     pstr->len += mbcdlen - mbclen;
435                     if (pstr->raw_stop > src_idx)
436                       pstr->stop += mbcdlen - mbclen;
437                     end_idx = (pstr->bufs_len > pstr->len)
438                               ? pstr->len : pstr->bufs_len;
439                     byte_idx += mbcdlen;
440                     src_idx += mbclen;
441                     continue;
442                   }
443               }
444             else
445               memcpy (pstr->mbs + byte_idx, p, mbclen);
446
447             if (BE (pstr->offsets_needed != 0, 0))
448               {
449                 int i;
450                 for (i = 0; i < mbclen; ++i)
451                   pstr->offsets[byte_idx + i] = src_idx + i;
452               }
453             src_idx += mbclen;
454
455             pstr->wcs[byte_idx++] = wcu;
456             /* Write paddings.  */
457             for (remain_len = byte_idx + mbclen - 1; byte_idx < remain_len ;)
458               pstr->wcs[byte_idx++] = WEOF;
459           }
460         else if (mbclen == (size_t) -1 || mbclen == 0)
461           {
462             /* It is an invalid character or '\0'.  Just use the byte.  */
463             int ch = pstr->raw_mbs[pstr->raw_mbs_idx + src_idx];
464
465             if (BE (pstr->trans != NULL, 0))
466               ch = pstr->trans [ch];
467             pstr->mbs[byte_idx] = ch;
468
469             if (BE (pstr->offsets_needed != 0, 0))
470               pstr->offsets[byte_idx] = src_idx;
471             ++src_idx;
472
473             /* And also cast it to wide char.  */
474             pstr->wcs[byte_idx++] = (wchar_t) ch;
475             if (BE (mbclen == (size_t) -1, 0))
476               pstr->cur_state = prev_st;
477           }
478         else
479           {
480             /* The buffer doesn't have enough space, finish to build.  */
481             pstr->cur_state = prev_st;
482             break;
483           }
484       }
485   pstr->valid_len = byte_idx;
486   pstr->valid_raw_len = src_idx;
487   return REG_NOERROR;
488 }
489
490 /* Skip characters until the index becomes greater than NEW_RAW_IDX.
491    Return the index.  */
492
493 static int
494 re_string_skip_chars (pstr, new_raw_idx, last_wc)
495      re_string_t *pstr;
496      int new_raw_idx;
497      wint_t *last_wc;
498 {
499   mbstate_t prev_st;
500   int rawbuf_idx, mbclen;
501   wchar_t wc = 0;
502
503   /* Skip the characters which are not necessary to check.  */
504   for (rawbuf_idx = pstr->raw_mbs_idx + pstr->valid_raw_len;
505        rawbuf_idx < new_raw_idx;)
506     {
507       int remain_len;
508       remain_len = pstr->len - rawbuf_idx;
509       prev_st = pstr->cur_state;
510       mbclen = mbrtowc (&wc, (const char *) pstr->raw_mbs + rawbuf_idx,
511                         remain_len, &pstr->cur_state);
512       if (BE (mbclen == (size_t) -2 || mbclen == (size_t) -1 || mbclen == 0, 0))
513         {
514           /* We treat these cases as a singlebyte character.  */
515           mbclen = 1;
516           pstr->cur_state = prev_st;
517         }
518       /* Then proceed the next character.  */
519       rawbuf_idx += mbclen;
520     }
521   *last_wc = (wint_t) wc;
522   return rawbuf_idx;
523 }
524 #endif /* RE_ENABLE_I18N  */
525
526 /* Build the buffer PSTR->MBS, and apply the translation if we need.
527    This function is used in case of REG_ICASE.  */
528
529 static void
530 build_upper_buffer (pstr)
531      re_string_t *pstr;
532 {
533   int char_idx, end_idx;
534   end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len;
535
536   for (char_idx = pstr->valid_len; char_idx < end_idx; ++char_idx)
537     {
538       int ch = pstr->raw_mbs[pstr->raw_mbs_idx + char_idx];
539       if (BE (pstr->trans != NULL, 0))
540         ch = pstr->trans[ch];
541       if (islower (ch))
542         pstr->mbs[char_idx] = toupper (ch);
543       else
544         pstr->mbs[char_idx] = ch;
545     }
546   pstr->valid_len = char_idx;
547   pstr->valid_raw_len = char_idx;
548 }
549
550 /* Apply TRANS to the buffer in PSTR.  */
551
552 static void
553 re_string_translate_buffer (pstr)
554      re_string_t *pstr;
555 {
556   int buf_idx, end_idx;
557   end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len;
558
559   for (buf_idx = pstr->valid_len; buf_idx < end_idx; ++buf_idx)
560     {
561       int ch = pstr->raw_mbs[pstr->raw_mbs_idx + buf_idx];
562       pstr->mbs[buf_idx] = pstr->trans[ch];
563     }
564
565   pstr->valid_len = buf_idx;
566   pstr->valid_raw_len = buf_idx;
567 }
568
569 /* This function re-construct the buffers.
570    Concretely, convert to wide character in case of pstr->mb_cur_max > 1,
571    convert to upper case in case of REG_ICASE, apply translation.  */
572
573 static reg_errcode_t
574 re_string_reconstruct (pstr, idx, eflags)
575      re_string_t *pstr;
576      int idx, eflags;
577 {
578   int offset = idx - pstr->raw_mbs_idx;
579   if (offset < 0)
580     {
581       /* Reset buffer.  */
582 #ifdef RE_ENABLE_I18N
583       if (pstr->mb_cur_max > 1)
584         memset (&pstr->cur_state, '\0', sizeof (mbstate_t));
585 #endif /* RE_ENABLE_I18N */
586       pstr->len = pstr->raw_len;
587       pstr->stop = pstr->raw_stop;
588       pstr->valid_len = 0;
589       pstr->raw_mbs_idx = 0;
590       pstr->valid_raw_len = 0;
591       pstr->offsets_needed = 0;
592       pstr->tip_context = ((eflags & REG_NOTBOL) ? CONTEXT_BEGBUF
593                            : CONTEXT_NEWLINE | CONTEXT_BEGBUF);
594       if (!pstr->mbs_allocated)
595         pstr->mbs = (unsigned char *) pstr->raw_mbs;
596       offset = idx;
597     }
598
599   if (offset != 0)
600     {
601       /* Are the characters which are already checked remain?  */
602       if (offset < pstr->valid_raw_len
603 #ifdef RE_ENABLE_I18N
604           /* Handling this would enlarge the code too much.
605              Accept a slowdown in that case.  */
606           && pstr->offsets_needed == 0
607 #endif
608          )
609         {
610           /* Yes, move them to the front of the buffer.  */
611           pstr->tip_context = re_string_context_at (pstr, offset - 1, eflags);
612 #ifdef RE_ENABLE_I18N
613           if (pstr->mb_cur_max > 1)
614             memmove (pstr->wcs, pstr->wcs + offset,
615                      (pstr->valid_len - offset) * sizeof (wint_t));
616 #endif /* RE_ENABLE_I18N */
617           if (pstr->mbs_allocated)
618             memmove (pstr->mbs, pstr->mbs + offset,
619                      pstr->valid_len - offset);
620           pstr->valid_len -= offset;
621           pstr->valid_raw_len -= offset;
622 #if DEBUG
623           assert (pstr->valid_len > 0);
624 #endif
625         }
626       else
627         {
628           /* No, skip all characters until IDX.  */
629 #ifdef RE_ENABLE_I18N
630           if (BE (pstr->offsets_needed, 0))
631             {
632               pstr->len = pstr->raw_len - idx + offset;
633               pstr->stop = pstr->raw_stop - idx + offset;
634               pstr->offsets_needed = 0;
635             }
636 #endif
637           pstr->valid_len = 0;
638           pstr->valid_raw_len = 0;
639 #ifdef RE_ENABLE_I18N
640           if (pstr->mb_cur_max > 1)
641             {
642               int wcs_idx;
643               wint_t wc = WEOF;
644
645               if (pstr->is_utf8)
646                 {
647                   const unsigned char *raw, *p, *q, *end;
648
649                   /* Special case UTF-8.  Multi-byte chars start with any
650                      byte other than 0x80 - 0xbf.  */
651                   raw = pstr->raw_mbs + pstr->raw_mbs_idx;
652                   end = raw + (offset - pstr->mb_cur_max);
653                   for (p = raw + offset - 1; p >= end; --p)
654                     if ((*p & 0xc0) != 0x80)
655                       {
656                         mbstate_t cur_state;
657                         wchar_t wc2;
658                         int mlen = raw + pstr->len - p;
659                         unsigned char buf[6];
660
661                         q = p;
662                         if (BE (pstr->trans != NULL, 0))
663                           {
664                             int i = mlen < 6 ? mlen : 6;
665                             while (--i >= 0)
666                               buf[i] = pstr->trans[p[i]];
667                             q = buf;
668                           }
669                         /* XXX Don't use mbrtowc, we know which conversion
670                            to use (UTF-8 -> UCS4).  */
671                         memset (&cur_state, 0, sizeof (cur_state));
672                         mlen = mbrtowc (&wc2, p, mlen, &cur_state)
673                                - (raw + offset - p);
674                         if (mlen >= 0)
675                           {
676                             memset (&pstr->cur_state, '\0',
677                                     sizeof (mbstate_t));
678                             pstr->valid_len = mlen;
679                             wc = wc2;
680                           }
681                         break;
682                       }
683                 }
684
685               if (wc == WEOF)
686                 pstr->valid_len = re_string_skip_chars (pstr, idx, &wc) - idx;
687               if (BE (pstr->valid_len, 0))
688                 {
689                   for (wcs_idx = 0; wcs_idx < pstr->valid_len; ++wcs_idx)
690                     pstr->wcs[wcs_idx] = WEOF;
691                   if (pstr->mbs_allocated)
692                     memset (pstr->mbs, 255, pstr->valid_len);
693                 }
694               pstr->valid_raw_len = pstr->valid_len;
695               pstr->tip_context = ((BE (pstr->word_ops_used != 0, 0)
696                                     && IS_WIDE_WORD_CHAR (wc))
697                                    ? CONTEXT_WORD
698                                    : ((IS_WIDE_NEWLINE (wc)
699                                        && pstr->newline_anchor)
700                                       ? CONTEXT_NEWLINE : 0));
701             }
702           else
703 #endif /* RE_ENABLE_I18N */
704             {
705               int c = pstr->raw_mbs[pstr->raw_mbs_idx + offset - 1];
706               if (pstr->trans)
707                 c = pstr->trans[c];
708               pstr->tip_context = (bitset_contain (pstr->word_char, c)
709                                    ? CONTEXT_WORD
710                                    : ((IS_NEWLINE (c) && pstr->newline_anchor)
711                                       ? CONTEXT_NEWLINE : 0));
712             }
713         }
714       if (!pstr->mbs_allocated)
715         pstr->mbs += offset;
716     }
717   pstr->raw_mbs_idx = idx;
718   pstr->len -= offset;
719   pstr->stop -= offset;
720
721   /* Then build the buffers.  */
722 #ifdef RE_ENABLE_I18N
723   if (pstr->mb_cur_max > 1)
724     {
725       if (pstr->icase)
726         {
727           int ret = build_wcs_upper_buffer (pstr);
728           if (BE (ret != REG_NOERROR, 0))
729             return ret;
730         }
731       else
732         build_wcs_buffer (pstr);
733     }
734   else
735 #endif /* RE_ENABLE_I18N */
736     {
737       if (pstr->icase)
738         build_upper_buffer (pstr);
739       else if (pstr->trans != NULL)
740         re_string_translate_buffer (pstr);
741       else
742         pstr->valid_len = pstr->len;
743     }
744   pstr->cur_idx = 0;
745
746   return REG_NOERROR;
747 }
748
749 static unsigned char
750 re_string_peek_byte_case (pstr, idx)
751      const re_string_t *pstr;
752      int idx;
753 {
754   int ch, off;
755
756   /* Handle the common (easiest) cases first.  */
757   if (BE (!pstr->mbs_allocated, 1))
758     return re_string_peek_byte (pstr, idx);
759
760 #ifdef RE_ENABLE_I18N
761   if (pstr->mb_cur_max > 1
762       && ! re_string_is_single_byte_char (pstr, pstr->cur_idx + idx))
763     return re_string_peek_byte (pstr, idx);
764 #endif
765
766   off = pstr->cur_idx + idx;
767 #ifdef RE_ENABLE_I18N
768   if (pstr->offsets_needed)
769     off = pstr->offsets[off];
770 #endif
771
772   ch = pstr->raw_mbs[pstr->raw_mbs_idx + off];
773
774 #ifdef RE_ENABLE_I18N
775   /* Ensure that e.g. for tr_TR.UTF-8 BACKSLASH DOTLESS SMALL LETTER I
776      this function returns CAPITAL LETTER I instead of first byte of
777      DOTLESS SMALL LETTER I.  The latter would confuse the parser,
778      since peek_byte_case doesn't advance cur_idx in any way.  */
779   if (pstr->offsets_needed && !isascii (ch))
780     return re_string_peek_byte (pstr, idx);
781 #endif
782
783   return ch;
784 }
785
786 static unsigned char
787 re_string_fetch_byte_case (pstr)
788      re_string_t *pstr;
789 {
790   if (BE (!pstr->mbs_allocated, 1))
791     return re_string_fetch_byte (pstr);
792
793 #ifdef RE_ENABLE_I18N
794   if (pstr->offsets_needed)
795     {
796       int off, ch;
797
798       /* For tr_TR.UTF-8 [[:islower:]] there is
799          [[: CAPITAL LETTER I WITH DOT lower:]] in mbs.  Skip
800          in that case the whole multi-byte character and return
801          the original letter.  On the other side, with
802          [[: DOTLESS SMALL LETTER I return [[:I, as doing
803          anything else would complicate things too much.  */
804
805       if (!re_string_first_byte (pstr, pstr->cur_idx))
806         return re_string_fetch_byte (pstr);
807
808       off = pstr->offsets[pstr->cur_idx];
809       ch = pstr->raw_mbs[pstr->raw_mbs_idx + off];
810
811       if (! isascii (ch))
812         return re_string_fetch_byte (pstr);
813
814       re_string_skip_bytes (pstr,
815                             re_string_char_size_at (pstr, pstr->cur_idx));
816       return ch;
817     }
818 #endif
819
820   return pstr->raw_mbs[pstr->raw_mbs_idx + pstr->cur_idx++];
821 }
822
823 static void
824 re_string_destruct (pstr)
825      re_string_t *pstr;
826 {
827 #ifdef RE_ENABLE_I18N
828   re_free (pstr->wcs);
829   re_free (pstr->offsets);
830 #endif /* RE_ENABLE_I18N  */
831   if (pstr->mbs_allocated)
832     re_free (pstr->mbs);
833 }
834
835 /* Return the context at IDX in INPUT.  */
836
837 static unsigned int
838 re_string_context_at (input, idx, eflags)
839      const re_string_t *input;
840      int idx, eflags;
841 {
842   int c;
843   if (idx < 0 || idx == input->len)
844     {
845       if (idx < 0)
846         /* In this case, we use the value stored in input->tip_context,
847            since we can't know the character in input->mbs[-1] here.  */
848         return input->tip_context;
849       else /* (idx == input->len) */
850         return ((eflags & REG_NOTEOL) ? CONTEXT_ENDBUF
851                 : CONTEXT_NEWLINE | CONTEXT_ENDBUF);
852     }
853 #ifdef RE_ENABLE_I18N
854   if (input->mb_cur_max > 1)
855     {
856       wint_t wc;
857       int wc_idx = idx;
858       while(input->wcs[wc_idx] == WEOF)
859         {
860 #ifdef DEBUG
861           /* It must not happen.  */
862           assert (wc_idx >= 0);
863 #endif
864           --wc_idx;
865           if (wc_idx < 0)
866             return input->tip_context;
867         }
868       wc = input->wcs[wc_idx];
869       if (BE (input->word_ops_used != 0, 0) && IS_WIDE_WORD_CHAR (wc))
870         return CONTEXT_WORD;
871       return (IS_WIDE_NEWLINE (wc) && input->newline_anchor
872               ? CONTEXT_NEWLINE : 0);
873     }
874   else
875 #endif
876     {
877       c = re_string_byte_at (input, idx);
878       if (bitset_contain (input->word_char, c))
879         return CONTEXT_WORD;
880       return IS_NEWLINE (c) && input->newline_anchor ? CONTEXT_NEWLINE : 0;
881     }
882 }
883 \f
884 /* Functions for set operation.  */
885
886 static reg_errcode_t
887 re_node_set_alloc (set, size)
888      re_node_set *set;
889      int size;
890 {
891   set->alloc = size;
892   set->nelem = 0;
893   set->elems = re_malloc (int, size);
894   if (BE (set->elems == NULL, 0))
895     return REG_ESPACE;
896   return REG_NOERROR;
897 }
898
899 static reg_errcode_t
900 re_node_set_init_1 (set, elem)
901      re_node_set *set;
902      int elem;
903 {
904   set->alloc = 1;
905   set->nelem = 1;
906   set->elems = re_malloc (int, 1);
907   if (BE (set->elems == NULL, 0))
908     {
909       set->alloc = set->nelem = 0;
910       return REG_ESPACE;
911     }
912   set->elems[0] = elem;
913   return REG_NOERROR;
914 }
915
916 static reg_errcode_t
917 re_node_set_init_2 (set, elem1, elem2)
918      re_node_set *set;
919      int elem1, elem2;
920 {
921   set->alloc = 2;
922   set->elems = re_malloc (int, 2);
923   if (BE (set->elems == NULL, 0))
924     return REG_ESPACE;
925   if (elem1 == elem2)
926     {
927       set->nelem = 1;
928       set->elems[0] = elem1;
929     }
930   else
931     {
932       set->nelem = 2;
933       if (elem1 < elem2)
934         {
935           set->elems[0] = elem1;
936           set->elems[1] = elem2;
937         }
938       else
939         {
940           set->elems[0] = elem2;
941           set->elems[1] = elem1;
942         }
943     }
944   return REG_NOERROR;
945 }
946
947 static reg_errcode_t
948 re_node_set_init_copy (dest, src)
949      re_node_set *dest;
950      const re_node_set *src;
951 {
952   dest->nelem = src->nelem;
953   if (src->nelem > 0)
954     {
955       dest->alloc = dest->nelem;
956       dest->elems = re_malloc (int, dest->alloc);
957       if (BE (dest->elems == NULL, 0))
958         {
959           dest->alloc = dest->nelem = 0;
960           return REG_ESPACE;
961         }
962       memcpy (dest->elems, src->elems, src->nelem * sizeof (int));
963     }
964   else
965     re_node_set_init_empty (dest);
966   return REG_NOERROR;
967 }
968
969 /* Calculate the intersection of the sets SRC1 and SRC2. And merge it to
970    DEST. Return value indicate the error code or REG_NOERROR if succeeded.
971    Note: We assume dest->elems is NULL, when dest->alloc is 0.  */
972
973 static reg_errcode_t
974 re_node_set_add_intersect (dest, src1, src2)
975      re_node_set *dest;
976      const re_node_set *src1, *src2;
977 {
978   int i1, i2, is, id, delta, sbase;
979   if (src1->nelem == 0 || src2->nelem == 0)
980     return REG_NOERROR;
981
982   /* We need dest->nelem + 2 * elems_in_intersection; this is a
983      conservative estimate.  */
984   if (src1->nelem + src2->nelem + dest->nelem > dest->alloc)
985     {
986       int new_alloc = src1->nelem + src2->nelem + dest->alloc;
987       int *new_elems = re_realloc (dest->elems, int, new_alloc);
988       if (BE (new_elems == NULL, 0))
989         return REG_ESPACE;
990       dest->elems = new_elems;
991       dest->alloc = new_alloc;
992     }
993
994   /* Find the items in the intersection of SRC1 and SRC2, and copy
995      into the top of DEST those that are not already in DEST itself.  */
996   sbase = dest->nelem + src1->nelem + src2->nelem;
997   i1 = src1->nelem - 1;
998   i2 = src2->nelem - 1;
999   id = dest->nelem - 1;
1000   for (;;)
1001     {
1002       if (src1->elems[i1] == src2->elems[i2])
1003         {
1004           /* Try to find the item in DEST.  Maybe we could binary search?  */
1005           while (id >= 0 && dest->elems[id] > src1->elems[i1])
1006             --id;
1007
1008           if (id < 0 || dest->elems[id] != src1->elems[i1])
1009             dest->elems[--sbase] = src1->elems[i1];
1010
1011           if (--i1 < 0 || --i2 < 0)
1012             break;
1013         }
1014
1015       /* Lower the highest of the two items.  */
1016       else if (src1->elems[i1] < src2->elems[i2])
1017         {
1018           if (--i2 < 0)
1019             break;
1020         }
1021       else
1022         {
1023           if (--i1 < 0)
1024             break;
1025         }
1026     }
1027
1028   id = dest->nelem - 1;
1029   is = dest->nelem + src1->nelem + src2->nelem - 1;
1030   delta = is - sbase + 1;
1031
1032   /* Now copy.  When DELTA becomes zero, the remaining
1033      DEST elements are already in place; this is more or
1034      less the same loop that is in re_node_set_merge.  */
1035   dest->nelem += delta;
1036   if (delta > 0 && id >= 0)
1037     for (;;)
1038       {
1039         if (dest->elems[is] > dest->elems[id])
1040           {
1041             /* Copy from the top.  */
1042             dest->elems[id + delta--] = dest->elems[is--];
1043             if (delta == 0)
1044               break;
1045           }
1046         else
1047           {
1048             /* Slide from the bottom.  */
1049             dest->elems[id + delta] = dest->elems[id];
1050             if (--id < 0)
1051               break;
1052           }
1053       }
1054
1055   /* Copy remaining SRC elements.  */
1056   memcpy (dest->elems, dest->elems + sbase, delta * sizeof (int));
1057
1058   return REG_NOERROR;
1059 }
1060
1061 /* Calculate the union set of the sets SRC1 and SRC2. And store it to
1062    DEST. Return value indicate the error code or REG_NOERROR if succeeded.  */
1063
1064 static reg_errcode_t
1065 re_node_set_init_union (dest, src1, src2)
1066      re_node_set *dest;
1067      const re_node_set *src1, *src2;
1068 {
1069   int i1, i2, id;
1070   if (src1 != NULL && src1->nelem > 0 && src2 != NULL && src2->nelem > 0)
1071     {
1072       dest->alloc = src1->nelem + src2->nelem;
1073       dest->elems = re_malloc (int, dest->alloc);
1074       if (BE (dest->elems == NULL, 0))
1075         return REG_ESPACE;
1076     }
1077   else
1078     {
1079       if (src1 != NULL && src1->nelem > 0)
1080         return re_node_set_init_copy (dest, src1);
1081       else if (src2 != NULL && src2->nelem > 0)
1082         return re_node_set_init_copy (dest, src2);
1083       else
1084         re_node_set_init_empty (dest);
1085       return REG_NOERROR;
1086     }
1087   for (i1 = i2 = id = 0 ; i1 < src1->nelem && i2 < src2->nelem ;)
1088     {
1089       if (src1->elems[i1] > src2->elems[i2])
1090         {
1091           dest->elems[id++] = src2->elems[i2++];
1092           continue;
1093         }
1094       if (src1->elems[i1] == src2->elems[i2])
1095         ++i2;
1096       dest->elems[id++] = src1->elems[i1++];
1097     }
1098   if (i1 < src1->nelem)
1099     {
1100       memcpy (dest->elems + id, src1->elems + i1,
1101              (src1->nelem - i1) * sizeof (int));
1102       id += src1->nelem - i1;
1103     }
1104   else if (i2 < src2->nelem)
1105     {
1106       memcpy (dest->elems + id, src2->elems + i2,
1107              (src2->nelem - i2) * sizeof (int));
1108       id += src2->nelem - i2;
1109     }
1110   dest->nelem = id;
1111   return REG_NOERROR;
1112 }
1113
1114 /* Calculate the union set of the sets DEST and SRC. And store it to
1115    DEST. Return value indicate the error code or REG_NOERROR if succeeded.  */
1116
1117 static reg_errcode_t
1118 re_node_set_merge (dest, src)
1119      re_node_set *dest;
1120      const re_node_set *src;
1121 {
1122   int is, id, sbase, delta;
1123   if (src == NULL || src->nelem == 0)
1124     return REG_NOERROR;
1125   if (dest->alloc < 2 * src->nelem + dest->nelem)
1126     {
1127       int new_alloc = 2 * (src->nelem + dest->alloc);
1128       int *new_buffer = re_realloc (dest->elems, int, new_alloc);
1129       if (BE (new_buffer == NULL, 0))
1130         return REG_ESPACE;
1131       dest->elems = new_buffer;
1132       dest->alloc = new_alloc;
1133     }
1134
1135   if (BE (dest->nelem == 0, 0))
1136     {
1137       dest->nelem = src->nelem;
1138       memcpy (dest->elems, src->elems, src->nelem * sizeof (int));
1139       return REG_NOERROR;
1140     }
1141
1142   /* Copy into the top of DEST the items of SRC that are not
1143      found in DEST.  Maybe we could binary search in DEST?  */
1144   for (sbase = dest->nelem + 2 * src->nelem,
1145        is = src->nelem - 1, id = dest->nelem - 1; is >= 0 && id >= 0; )
1146     {
1147       if (dest->elems[id] == src->elems[is])
1148         is--, id--;
1149       else if (dest->elems[id] < src->elems[is])
1150         dest->elems[--sbase] = src->elems[is--];
1151       else /* if (dest->elems[id] > src->elems[is]) */
1152         --id;
1153     }
1154
1155   if (is >= 0)
1156     {
1157       /* If DEST is exhausted, the remaining items of SRC must be unique.  */
1158       sbase -= is + 1;
1159       memcpy (dest->elems + sbase, src->elems, (is + 1) * sizeof (int));
1160     }
1161
1162   id = dest->nelem - 1;
1163   is = dest->nelem + 2 * src->nelem - 1;
1164   delta = is - sbase + 1;
1165   if (delta == 0)
1166     return REG_NOERROR;
1167
1168   /* Now copy.  When DELTA becomes zero, the remaining
1169      DEST elements are already in place.  */
1170   dest->nelem += delta;
1171   for (;;)
1172     {
1173       if (dest->elems[is] > dest->elems[id])
1174         {
1175           /* Copy from the top.  */
1176           dest->elems[id + delta--] = dest->elems[is--];
1177           if (delta == 0)
1178             break;
1179         }
1180       else
1181         {
1182           /* Slide from the bottom.  */
1183           dest->elems[id + delta] = dest->elems[id];
1184           if (--id < 0)
1185             {
1186               /* Copy remaining SRC elements.  */
1187               memcpy (dest->elems, dest->elems + sbase,
1188                       delta * sizeof (int));
1189               break;
1190             }
1191         }
1192     }
1193
1194   return REG_NOERROR;
1195 }
1196
1197 /* Insert the new element ELEM to the re_node_set* SET.
1198    SET should not already have ELEM.
1199    return -1 if an error is occured, return 1 otherwise.  */
1200
1201 static int
1202 re_node_set_insert (set, elem)
1203      re_node_set *set;
1204      int elem;
1205 {
1206   int idx;
1207   /* In case the set is empty.  */
1208   if (set->alloc == 0)
1209     {
1210       if (BE (re_node_set_init_1 (set, elem) == REG_NOERROR, 1))
1211         return 1;
1212       else
1213         return -1;
1214     }
1215
1216   if (BE (set->nelem, 0) == 0)
1217     {
1218       /* We already guaranteed above that set->alloc != 0.  */
1219       set->elems[0] = elem;
1220       ++set->nelem;
1221       return 1;
1222     }
1223
1224   /* Realloc if we need.  */
1225   if (set->alloc == set->nelem)
1226     {
1227       int *new_array;
1228       set->alloc = set->alloc * 2;
1229       new_array = re_realloc (set->elems, int, set->alloc);
1230       if (BE (new_array == NULL, 0))
1231         return -1;
1232       set->elems = new_array;
1233     }
1234
1235   /* Move the elements which follows the new element.  Test the
1236      first element separately to skip a check in the inner loop.  */
1237   if (elem < set->elems[0])
1238     {
1239       idx = 0;
1240       for (idx = set->nelem; idx > 0; idx--)
1241         set->elems[idx] = set->elems[idx - 1];
1242     }
1243   else
1244     {
1245       for (idx = set->nelem; set->elems[idx - 1] > elem; idx--)
1246         set->elems[idx] = set->elems[idx - 1];
1247     }
1248
1249   /* Insert the new element.  */
1250   set->elems[idx] = elem;
1251   ++set->nelem;
1252   return 1;
1253 }
1254
1255 /* Compare two node sets SET1 and SET2.
1256    return 1 if SET1 and SET2 are equivalent, return 0 otherwise.  */
1257
1258 static int
1259 re_node_set_compare (set1, set2)
1260      const re_node_set *set1, *set2;
1261 {
1262   int i;
1263   if (set1 == NULL || set2 == NULL || set1->nelem != set2->nelem)
1264     return 0;
1265   for (i = set1->nelem ; --i >= 0 ; )
1266     if (set1->elems[i] != set2->elems[i])
1267       return 0;
1268   return 1;
1269 }
1270
1271 /* Return (idx + 1) if SET contains the element ELEM, return 0 otherwise.  */
1272
1273 static int
1274 re_node_set_contains (set, elem)
1275      const re_node_set *set;
1276      int elem;
1277 {
1278   int idx, right, mid;
1279   if (set->nelem <= 0)
1280     return 0;
1281
1282   /* Binary search the element.  */
1283   idx = 0;
1284   right = set->nelem - 1;
1285   while (idx < right)
1286     {
1287       mid = (idx + right) / 2;
1288       if (set->elems[mid] < elem)
1289         idx = mid + 1;
1290       else
1291         right = mid;
1292     }
1293   return set->elems[idx] == elem ? idx + 1 : 0;
1294 }
1295
1296 static void
1297 re_node_set_remove_at (set, idx)
1298      re_node_set *set;
1299      int idx;
1300 {
1301   if (idx < 0 || idx >= set->nelem)
1302     return;
1303   --set->nelem;
1304   for (; idx < set->nelem; idx++)
1305     set->elems[idx] = set->elems[idx + 1];
1306 }
1307 \f
1308
1309 /* Add the token TOKEN to dfa->nodes, and return the index of the token.
1310    Or return -1, if an error will be occured.  */
1311
1312 static int
1313 re_dfa_add_node (dfa, token, mode)
1314      re_dfa_t *dfa;
1315      re_token_t token;
1316      int mode;
1317 {
1318   if (BE (dfa->nodes_len >= dfa->nodes_alloc, 0))
1319     {
1320       int new_nodes_alloc = dfa->nodes_alloc * 2;
1321       re_token_t *new_array = re_realloc (dfa->nodes, re_token_t,
1322                                           new_nodes_alloc);
1323       if (BE (new_array == NULL, 0))
1324         return -1;
1325       dfa->nodes = new_array;
1326       if (mode)
1327         {
1328           int *new_nexts, *new_indices;
1329           re_node_set *new_edests, *new_eclosures, *new_inveclosures;
1330
1331           new_nexts = re_realloc (dfa->nexts, int, new_nodes_alloc);
1332           new_indices = re_realloc (dfa->org_indices, int, new_nodes_alloc);
1333           new_edests = re_realloc (dfa->edests, re_node_set, new_nodes_alloc);
1334           new_eclosures = re_realloc (dfa->eclosures, re_node_set,
1335                                       new_nodes_alloc);
1336           new_inveclosures = re_realloc (dfa->inveclosures, re_node_set,
1337                                          new_nodes_alloc);
1338           if (BE (new_nexts == NULL || new_indices == NULL
1339                   || new_edests == NULL || new_eclosures == NULL
1340                   || new_inveclosures == NULL, 0))
1341             return -1;
1342           dfa->nexts = new_nexts;
1343           dfa->org_indices = new_indices;
1344           dfa->edests = new_edests;
1345           dfa->eclosures = new_eclosures;
1346           dfa->inveclosures = new_inveclosures;
1347         }
1348       dfa->nodes_alloc = new_nodes_alloc;
1349     }
1350   dfa->nodes[dfa->nodes_len] = token;
1351   dfa->nodes[dfa->nodes_len].opt_subexp = 0;
1352   dfa->nodes[dfa->nodes_len].duplicated = 0;
1353   dfa->nodes[dfa->nodes_len].constraint = 0;
1354   return dfa->nodes_len++;
1355 }
1356
1357 static unsigned int inline
1358 calc_state_hash (nodes, context)
1359      const re_node_set *nodes;
1360      unsigned int context;
1361 {
1362   unsigned int hash = nodes->nelem + context;
1363   int i;
1364   for (i = 0 ; i < nodes->nelem ; i++)
1365     hash += nodes->elems[i];
1366   return hash;
1367 }
1368
1369 /* Search for the state whose node_set is equivalent to NODES.
1370    Return the pointer to the state, if we found it in the DFA.
1371    Otherwise create the new one and return it.  In case of an error
1372    return NULL and set the error code in ERR.
1373    Note: - We assume NULL as the invalid state, then it is possible that
1374            return value is NULL and ERR is REG_NOERROR.
1375          - We never return non-NULL value in case of any errors, it is for
1376            optimization.  */
1377
1378 static re_dfastate_t*
1379 re_acquire_state (err, dfa, nodes)
1380      reg_errcode_t *err;
1381      re_dfa_t *dfa;
1382      const re_node_set *nodes;
1383 {
1384   unsigned int hash;
1385   re_dfastate_t *new_state;
1386   struct re_state_table_entry *spot;
1387   int i;
1388   if (BE (nodes->nelem == 0, 0))
1389     {
1390       *err = REG_NOERROR;
1391       return NULL;
1392     }
1393   hash = calc_state_hash (nodes, 0);
1394   spot = dfa->state_table + (hash & dfa->state_hash_mask);
1395
1396   for (i = 0 ; i < spot->num ; i++)
1397     {
1398       re_dfastate_t *state = spot->array[i];
1399       if (hash != state->hash)
1400         continue;
1401       if (re_node_set_compare (&state->nodes, nodes))
1402         return state;
1403     }
1404
1405   /* There are no appropriate state in the dfa, create the new one.  */
1406   new_state = create_ci_newstate (dfa, nodes, hash);
1407   if (BE (new_state != NULL, 1))
1408     return new_state;
1409   else
1410     {
1411       *err = REG_ESPACE;
1412       return NULL;
1413     }
1414 }
1415
1416 /* Search for the state whose node_set is equivalent to NODES and
1417    whose context is equivalent to CONTEXT.
1418    Return the pointer to the state, if we found it in the DFA.
1419    Otherwise create the new one and return it.  In case of an error
1420    return NULL and set the error code in ERR.
1421    Note: - We assume NULL as the invalid state, then it is possible that
1422            return value is NULL and ERR is REG_NOERROR.
1423          - We never return non-NULL value in case of any errors, it is for
1424            optimization.  */
1425
1426 static re_dfastate_t*
1427 re_acquire_state_context (err, dfa, nodes, context)
1428      reg_errcode_t *err;
1429      re_dfa_t *dfa;
1430      const re_node_set *nodes;
1431      unsigned int context;
1432 {
1433   unsigned int hash;
1434   re_dfastate_t *new_state;
1435   struct re_state_table_entry *spot;
1436   int i;
1437   if (nodes->nelem == 0)
1438     {
1439       *err = REG_NOERROR;
1440       return NULL;
1441     }
1442   hash = calc_state_hash (nodes, context);
1443   spot = dfa->state_table + (hash & dfa->state_hash_mask);
1444
1445   for (i = 0 ; i < spot->num ; i++)
1446     {
1447       re_dfastate_t *state = spot->array[i];
1448       if (state->hash == hash
1449           && state->context == context
1450           && re_node_set_compare (state->entrance_nodes, nodes))
1451         return state;
1452     }
1453   /* There are no appropriate state in `dfa', create the new one.  */
1454   new_state = create_cd_newstate (dfa, nodes, context, hash);
1455   if (BE (new_state != NULL, 1))
1456     return new_state;
1457   else
1458     {
1459       *err = REG_ESPACE;
1460       return NULL;
1461     }
1462 }
1463
1464 /* Allocate memory for DFA state and initialize common properties.
1465    Return the new state if succeeded, otherwise return NULL.  */
1466
1467 static re_dfastate_t *
1468 create_newstate_common (dfa, nodes, hash)
1469      re_dfa_t *dfa;
1470      const re_node_set *nodes;
1471      unsigned int hash;
1472 {
1473   re_dfastate_t *newstate;
1474   reg_errcode_t err;
1475   newstate = (re_dfastate_t *) calloc (sizeof (re_dfastate_t), 1);
1476   if (BE (newstate == NULL, 0))
1477     return NULL;
1478   err = re_node_set_init_copy (&newstate->nodes, nodes);
1479   if (BE (err != REG_NOERROR, 0))
1480     {
1481       re_free (newstate);
1482       return NULL;
1483     }
1484   newstate->trtable = NULL;
1485   newstate->hash = hash;
1486   return newstate;
1487 }
1488
1489 /* Store the new state NEWSTATE whose hash value is HASH in appropriate
1490    position.  Return value indicate the error code if failed.  */
1491
1492 static reg_errcode_t
1493 register_state (dfa, newstate, hash)
1494      re_dfa_t *dfa;
1495      re_dfastate_t *newstate;
1496      unsigned int hash;
1497 {
1498   struct re_state_table_entry *spot;
1499   spot = dfa->state_table + (hash & dfa->state_hash_mask);
1500
1501   if (BE (spot->alloc <= spot->num, 0))
1502     {
1503       int new_alloc = 2 * spot->num + 2;
1504       re_dfastate_t **new_array = re_realloc (spot->array, re_dfastate_t *,
1505                                               new_alloc);
1506       if (BE (new_array == NULL, 0))
1507         return REG_ESPACE;
1508       spot->array = new_array;
1509       spot->alloc = new_alloc;
1510     }
1511   spot->array[spot->num++] = newstate;
1512   return REG_NOERROR;
1513 }
1514
1515 /* Create the new state which is independ of contexts.
1516    Return the new state if succeeded, otherwise return NULL.  */
1517
1518 static re_dfastate_t *
1519 create_ci_newstate (dfa, nodes, hash)
1520      re_dfa_t *dfa;
1521      const re_node_set *nodes;
1522      unsigned int hash;
1523 {
1524   int i;
1525   reg_errcode_t err;
1526   re_dfastate_t *newstate;
1527   newstate = create_newstate_common (dfa, nodes, hash);
1528   if (BE (newstate == NULL, 0))
1529     return NULL;
1530   newstate->entrance_nodes = &newstate->nodes;
1531
1532   for (i = 0 ; i < nodes->nelem ; i++)
1533     {
1534       re_token_t *node = dfa->nodes + nodes->elems[i];
1535       re_token_type_t type = node->type;
1536       if (type == CHARACTER && !node->constraint)
1537         continue;
1538
1539       /* If the state has the halt node, the state is a halt state.  */
1540       else if (type == END_OF_RE)
1541         newstate->halt = 1;
1542 #ifdef RE_ENABLE_I18N
1543       else if (type == COMPLEX_BRACKET
1544                || type == OP_UTF8_PERIOD
1545                || (type == OP_PERIOD && dfa->mb_cur_max > 1))
1546         newstate->accept_mb = 1;
1547 #endif /* RE_ENABLE_I18N */
1548       else if (type == OP_BACK_REF)
1549         newstate->has_backref = 1;
1550       else if (type == ANCHOR || node->constraint)
1551         newstate->has_constraint = 1;
1552     }
1553   err = register_state (dfa, newstate, hash);
1554   if (BE (err != REG_NOERROR, 0))
1555     {
1556       free_state (newstate);
1557       newstate = NULL;
1558     }
1559   return newstate;
1560 }
1561
1562 /* Create the new state which is depend on the context CONTEXT.
1563    Return the new state if succeeded, otherwise return NULL.  */
1564
1565 static re_dfastate_t *
1566 create_cd_newstate (dfa, nodes, context, hash)
1567      re_dfa_t *dfa;
1568      const re_node_set *nodes;
1569      unsigned int context, hash;
1570 {
1571   int i, nctx_nodes = 0;
1572   reg_errcode_t err;
1573   re_dfastate_t *newstate;
1574
1575   newstate = create_newstate_common (dfa, nodes, hash);
1576   if (BE (newstate == NULL, 0))
1577     return NULL;
1578   newstate->context = context;
1579   newstate->entrance_nodes = &newstate->nodes;
1580
1581   for (i = 0 ; i < nodes->nelem ; i++)
1582     {
1583       unsigned int constraint = 0;
1584       re_token_t *node = dfa->nodes + nodes->elems[i];
1585       re_token_type_t type = node->type;
1586       if (node->constraint)
1587         constraint = node->constraint;
1588
1589       if (type == CHARACTER && !constraint)
1590         continue;
1591       /* If the state has the halt node, the state is a halt state.  */
1592       else if (type == END_OF_RE)
1593         newstate->halt = 1;
1594 #ifdef RE_ENABLE_I18N
1595       else if (type == COMPLEX_BRACKET
1596                || type == OP_UTF8_PERIOD
1597                || (type == OP_PERIOD && dfa->mb_cur_max > 1))
1598         newstate->accept_mb = 1;
1599 #endif /* RE_ENABLE_I18N */
1600       else if (type == OP_BACK_REF)
1601         newstate->has_backref = 1;
1602       else if (type == ANCHOR)
1603         constraint = node->opr.ctx_type;
1604
1605       if (constraint)
1606         {
1607           if (newstate->entrance_nodes == &newstate->nodes)
1608             {
1609               newstate->entrance_nodes = re_malloc (re_node_set, 1);
1610               if (BE (newstate->entrance_nodes == NULL, 0))
1611                 {
1612                   free_state (newstate);
1613                   return NULL;
1614                 }
1615               re_node_set_init_copy (newstate->entrance_nodes, nodes);
1616               nctx_nodes = 0;
1617               newstate->has_constraint = 1;
1618             }
1619
1620           if (NOT_SATISFY_PREV_CONSTRAINT (constraint,context))
1621             {
1622               re_node_set_remove_at (&newstate->nodes, i - nctx_nodes);
1623               ++nctx_nodes;
1624             }
1625         }
1626     }
1627   err = register_state (dfa, newstate, hash);
1628   if (BE (err != REG_NOERROR, 0))
1629     {
1630       free_state (newstate);
1631       newstate = NULL;
1632     }
1633   return  newstate;
1634 }
1635
1636 static void
1637 free_state (state)
1638      re_dfastate_t *state;
1639 {
1640   if (state->entrance_nodes != &state->nodes)
1641     {
1642       re_node_set_free (state->entrance_nodes);
1643       re_free (state->entrance_nodes);
1644     }
1645   re_node_set_free (&state->nodes);
1646   re_free (state->trtable);
1647   re_free (state);
1648 }