(re_string_reconstruct, re_string_context_at): Add several branch
[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 (BE (offset < 0, 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 (BE (offset != 0, 1))
600     {
601       /* Are the characters which are already checked remain?  */
602       if (BE (offset < pstr->valid_raw_len, 1)
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 (BE (pstr->mbs_allocated, 0))
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 (!BE (pstr->mbs_allocated, 0))
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   if (BE (pstr->mbs_allocated, 0))
737     {
738       if (pstr->icase)
739         build_upper_buffer (pstr);
740       else if (pstr->trans != NULL)
741         re_string_translate_buffer (pstr);
742     }
743   else
744     pstr->valid_len = pstr->len;
745
746   pstr->cur_idx = 0;
747   return REG_NOERROR;
748 }
749
750 static unsigned char
751 re_string_peek_byte_case (pstr, idx)
752      const re_string_t *pstr;
753      int idx;
754 {
755   int ch, off;
756
757   /* Handle the common (easiest) cases first.  */
758   if (BE (!pstr->mbs_allocated, 1))
759     return re_string_peek_byte (pstr, idx);
760
761 #ifdef RE_ENABLE_I18N
762   if (pstr->mb_cur_max > 1
763       && ! re_string_is_single_byte_char (pstr, pstr->cur_idx + idx))
764     return re_string_peek_byte (pstr, idx);
765 #endif
766
767   off = pstr->cur_idx + idx;
768 #ifdef RE_ENABLE_I18N
769   if (pstr->offsets_needed)
770     off = pstr->offsets[off];
771 #endif
772
773   ch = pstr->raw_mbs[pstr->raw_mbs_idx + off];
774
775 #ifdef RE_ENABLE_I18N
776   /* Ensure that e.g. for tr_TR.UTF-8 BACKSLASH DOTLESS SMALL LETTER I
777      this function returns CAPITAL LETTER I instead of first byte of
778      DOTLESS SMALL LETTER I.  The latter would confuse the parser,
779      since peek_byte_case doesn't advance cur_idx in any way.  */
780   if (pstr->offsets_needed && !isascii (ch))
781     return re_string_peek_byte (pstr, idx);
782 #endif
783
784   return ch;
785 }
786
787 static unsigned char
788 re_string_fetch_byte_case (pstr)
789      re_string_t *pstr;
790 {
791   if (BE (!pstr->mbs_allocated, 1))
792     return re_string_fetch_byte (pstr);
793
794 #ifdef RE_ENABLE_I18N
795   if (pstr->offsets_needed)
796     {
797       int off, ch;
798
799       /* For tr_TR.UTF-8 [[:islower:]] there is
800          [[: CAPITAL LETTER I WITH DOT lower:]] in mbs.  Skip
801          in that case the whole multi-byte character and return
802          the original letter.  On the other side, with
803          [[: DOTLESS SMALL LETTER I return [[:I, as doing
804          anything else would complicate things too much.  */
805
806       if (!re_string_first_byte (pstr, pstr->cur_idx))
807         return re_string_fetch_byte (pstr);
808
809       off = pstr->offsets[pstr->cur_idx];
810       ch = pstr->raw_mbs[pstr->raw_mbs_idx + off];
811
812       if (! isascii (ch))
813         return re_string_fetch_byte (pstr);
814
815       re_string_skip_bytes (pstr,
816                             re_string_char_size_at (pstr, pstr->cur_idx));
817       return ch;
818     }
819 #endif
820
821   return pstr->raw_mbs[pstr->raw_mbs_idx + pstr->cur_idx++];
822 }
823
824 static void
825 re_string_destruct (pstr)
826      re_string_t *pstr;
827 {
828 #ifdef RE_ENABLE_I18N
829   re_free (pstr->wcs);
830   re_free (pstr->offsets);
831 #endif /* RE_ENABLE_I18N  */
832   if (pstr->mbs_allocated)
833     re_free (pstr->mbs);
834 }
835
836 /* Return the context at IDX in INPUT.  */
837
838 static unsigned int
839 re_string_context_at (input, idx, eflags)
840      const re_string_t *input;
841      int idx, eflags;
842 {
843   int c;
844   if (BE (idx < 0, 0))
845     /* In this case, we use the value stored in input->tip_context,
846        since we can't know the character in input->mbs[-1] here.  */
847     return input->tip_context;
848   if (BE (idx == input->len, 0))
849     return ((eflags & REG_NOTEOL) ? CONTEXT_ENDBUF
850             : CONTEXT_NEWLINE | CONTEXT_ENDBUF);
851 #ifdef RE_ENABLE_I18N
852   if (input->mb_cur_max > 1)
853     {
854       wint_t wc;
855       int wc_idx = idx;
856       while(input->wcs[wc_idx] == WEOF)
857         {
858 #ifdef DEBUG
859           /* It must not happen.  */
860           assert (wc_idx >= 0);
861 #endif
862           --wc_idx;
863           if (wc_idx < 0)
864             return input->tip_context;
865         }
866       wc = input->wcs[wc_idx];
867       if (BE (input->word_ops_used != 0, 0) && IS_WIDE_WORD_CHAR (wc))
868         return CONTEXT_WORD;
869       return (IS_WIDE_NEWLINE (wc) && input->newline_anchor
870               ? CONTEXT_NEWLINE : 0);
871     }
872   else
873 #endif
874     {
875       c = re_string_byte_at (input, idx);
876       if (bitset_contain (input->word_char, c))
877         return CONTEXT_WORD;
878       return IS_NEWLINE (c) && input->newline_anchor ? CONTEXT_NEWLINE : 0;
879     }
880 }
881 \f
882 /* Functions for set operation.  */
883
884 static reg_errcode_t
885 re_node_set_alloc (set, size)
886      re_node_set *set;
887      int size;
888 {
889   set->alloc = size;
890   set->nelem = 0;
891   set->elems = re_malloc (int, size);
892   if (BE (set->elems == NULL, 0))
893     return REG_ESPACE;
894   return REG_NOERROR;
895 }
896
897 static reg_errcode_t
898 re_node_set_init_1 (set, elem)
899      re_node_set *set;
900      int elem;
901 {
902   set->alloc = 1;
903   set->nelem = 1;
904   set->elems = re_malloc (int, 1);
905   if (BE (set->elems == NULL, 0))
906     {
907       set->alloc = set->nelem = 0;
908       return REG_ESPACE;
909     }
910   set->elems[0] = elem;
911   return REG_NOERROR;
912 }
913
914 static reg_errcode_t
915 re_node_set_init_2 (set, elem1, elem2)
916      re_node_set *set;
917      int elem1, elem2;
918 {
919   set->alloc = 2;
920   set->elems = re_malloc (int, 2);
921   if (BE (set->elems == NULL, 0))
922     return REG_ESPACE;
923   if (elem1 == elem2)
924     {
925       set->nelem = 1;
926       set->elems[0] = elem1;
927     }
928   else
929     {
930       set->nelem = 2;
931       if (elem1 < elem2)
932         {
933           set->elems[0] = elem1;
934           set->elems[1] = elem2;
935         }
936       else
937         {
938           set->elems[0] = elem2;
939           set->elems[1] = elem1;
940         }
941     }
942   return REG_NOERROR;
943 }
944
945 static reg_errcode_t
946 re_node_set_init_copy (dest, src)
947      re_node_set *dest;
948      const re_node_set *src;
949 {
950   dest->nelem = src->nelem;
951   if (src->nelem > 0)
952     {
953       dest->alloc = dest->nelem;
954       dest->elems = re_malloc (int, dest->alloc);
955       if (BE (dest->elems == NULL, 0))
956         {
957           dest->alloc = dest->nelem = 0;
958           return REG_ESPACE;
959         }
960       memcpy (dest->elems, src->elems, src->nelem * sizeof (int));
961     }
962   else
963     re_node_set_init_empty (dest);
964   return REG_NOERROR;
965 }
966
967 /* Calculate the intersection of the sets SRC1 and SRC2. And merge it to
968    DEST. Return value indicate the error code or REG_NOERROR if succeeded.
969    Note: We assume dest->elems is NULL, when dest->alloc is 0.  */
970
971 static reg_errcode_t
972 re_node_set_add_intersect (dest, src1, src2)
973      re_node_set *dest;
974      const re_node_set *src1, *src2;
975 {
976   int i1, i2, is, id, delta, sbase;
977   if (src1->nelem == 0 || src2->nelem == 0)
978     return REG_NOERROR;
979
980   /* We need dest->nelem + 2 * elems_in_intersection; this is a
981      conservative estimate.  */
982   if (src1->nelem + src2->nelem + dest->nelem > dest->alloc)
983     {
984       int new_alloc = src1->nelem + src2->nelem + dest->alloc;
985       int *new_elems = re_realloc (dest->elems, int, new_alloc);
986       if (BE (new_elems == NULL, 0))
987         return REG_ESPACE;
988       dest->elems = new_elems;
989       dest->alloc = new_alloc;
990     }
991
992   /* Find the items in the intersection of SRC1 and SRC2, and copy
993      into the top of DEST those that are not already in DEST itself.  */
994   sbase = dest->nelem + src1->nelem + src2->nelem;
995   i1 = src1->nelem - 1;
996   i2 = src2->nelem - 1;
997   id = dest->nelem - 1;
998   for (;;)
999     {
1000       if (src1->elems[i1] == src2->elems[i2])
1001         {
1002           /* Try to find the item in DEST.  Maybe we could binary search?  */
1003           while (id >= 0 && dest->elems[id] > src1->elems[i1])
1004             --id;
1005
1006           if (id < 0 || dest->elems[id] != src1->elems[i1])
1007             dest->elems[--sbase] = src1->elems[i1];
1008
1009           if (--i1 < 0 || --i2 < 0)
1010             break;
1011         }
1012
1013       /* Lower the highest of the two items.  */
1014       else if (src1->elems[i1] < src2->elems[i2])
1015         {
1016           if (--i2 < 0)
1017             break;
1018         }
1019       else
1020         {
1021           if (--i1 < 0)
1022             break;
1023         }
1024     }
1025
1026   id = dest->nelem - 1;
1027   is = dest->nelem + src1->nelem + src2->nelem - 1;
1028   delta = is - sbase + 1;
1029
1030   /* Now copy.  When DELTA becomes zero, the remaining
1031      DEST elements are already in place; this is more or
1032      less the same loop that is in re_node_set_merge.  */
1033   dest->nelem += delta;
1034   if (delta > 0 && id >= 0)
1035     for (;;)
1036       {
1037         if (dest->elems[is] > dest->elems[id])
1038           {
1039             /* Copy from the top.  */
1040             dest->elems[id + delta--] = dest->elems[is--];
1041             if (delta == 0)
1042               break;
1043           }
1044         else
1045           {
1046             /* Slide from the bottom.  */
1047             dest->elems[id + delta] = dest->elems[id];
1048             if (--id < 0)
1049               break;
1050           }
1051       }
1052
1053   /* Copy remaining SRC elements.  */
1054   memcpy (dest->elems, dest->elems + sbase, delta * sizeof (int));
1055
1056   return REG_NOERROR;
1057 }
1058
1059 /* Calculate the union set of the sets SRC1 and SRC2. And store it to
1060    DEST. Return value indicate the error code or REG_NOERROR if succeeded.  */
1061
1062 static reg_errcode_t
1063 re_node_set_init_union (dest, src1, src2)
1064      re_node_set *dest;
1065      const re_node_set *src1, *src2;
1066 {
1067   int i1, i2, id;
1068   if (src1 != NULL && src1->nelem > 0 && src2 != NULL && src2->nelem > 0)
1069     {
1070       dest->alloc = src1->nelem + src2->nelem;
1071       dest->elems = re_malloc (int, dest->alloc);
1072       if (BE (dest->elems == NULL, 0))
1073         return REG_ESPACE;
1074     }
1075   else
1076     {
1077       if (src1 != NULL && src1->nelem > 0)
1078         return re_node_set_init_copy (dest, src1);
1079       else if (src2 != NULL && src2->nelem > 0)
1080         return re_node_set_init_copy (dest, src2);
1081       else
1082         re_node_set_init_empty (dest);
1083       return REG_NOERROR;
1084     }
1085   for (i1 = i2 = id = 0 ; i1 < src1->nelem && i2 < src2->nelem ;)
1086     {
1087       if (src1->elems[i1] > src2->elems[i2])
1088         {
1089           dest->elems[id++] = src2->elems[i2++];
1090           continue;
1091         }
1092       if (src1->elems[i1] == src2->elems[i2])
1093         ++i2;
1094       dest->elems[id++] = src1->elems[i1++];
1095     }
1096   if (i1 < src1->nelem)
1097     {
1098       memcpy (dest->elems + id, src1->elems + i1,
1099              (src1->nelem - i1) * sizeof (int));
1100       id += src1->nelem - i1;
1101     }
1102   else if (i2 < src2->nelem)
1103     {
1104       memcpy (dest->elems + id, src2->elems + i2,
1105              (src2->nelem - i2) * sizeof (int));
1106       id += src2->nelem - i2;
1107     }
1108   dest->nelem = id;
1109   return REG_NOERROR;
1110 }
1111
1112 /* Calculate the union set of the sets DEST and SRC. And store it to
1113    DEST. Return value indicate the error code or REG_NOERROR if succeeded.  */
1114
1115 static reg_errcode_t
1116 re_node_set_merge (dest, src)
1117      re_node_set *dest;
1118      const re_node_set *src;
1119 {
1120   int is, id, sbase, delta;
1121   if (src == NULL || src->nelem == 0)
1122     return REG_NOERROR;
1123   if (dest->alloc < 2 * src->nelem + dest->nelem)
1124     {
1125       int new_alloc = 2 * (src->nelem + dest->alloc);
1126       int *new_buffer = re_realloc (dest->elems, int, new_alloc);
1127       if (BE (new_buffer == NULL, 0))
1128         return REG_ESPACE;
1129       dest->elems = new_buffer;
1130       dest->alloc = new_alloc;
1131     }
1132
1133   if (BE (dest->nelem == 0, 0))
1134     {
1135       dest->nelem = src->nelem;
1136       memcpy (dest->elems, src->elems, src->nelem * sizeof (int));
1137       return REG_NOERROR;
1138     }
1139
1140   /* Copy into the top of DEST the items of SRC that are not
1141      found in DEST.  Maybe we could binary search in DEST?  */
1142   for (sbase = dest->nelem + 2 * src->nelem,
1143        is = src->nelem - 1, id = dest->nelem - 1; is >= 0 && id >= 0; )
1144     {
1145       if (dest->elems[id] == src->elems[is])
1146         is--, id--;
1147       else if (dest->elems[id] < src->elems[is])
1148         dest->elems[--sbase] = src->elems[is--];
1149       else /* if (dest->elems[id] > src->elems[is]) */
1150         --id;
1151     }
1152
1153   if (is >= 0)
1154     {
1155       /* If DEST is exhausted, the remaining items of SRC must be unique.  */
1156       sbase -= is + 1;
1157       memcpy (dest->elems + sbase, src->elems, (is + 1) * sizeof (int));
1158     }
1159
1160   id = dest->nelem - 1;
1161   is = dest->nelem + 2 * src->nelem - 1;
1162   delta = is - sbase + 1;
1163   if (delta == 0)
1164     return REG_NOERROR;
1165
1166   /* Now copy.  When DELTA becomes zero, the remaining
1167      DEST elements are already in place.  */
1168   dest->nelem += delta;
1169   for (;;)
1170     {
1171       if (dest->elems[is] > dest->elems[id])
1172         {
1173           /* Copy from the top.  */
1174           dest->elems[id + delta--] = dest->elems[is--];
1175           if (delta == 0)
1176             break;
1177         }
1178       else
1179         {
1180           /* Slide from the bottom.  */
1181           dest->elems[id + delta] = dest->elems[id];
1182           if (--id < 0)
1183             {
1184               /* Copy remaining SRC elements.  */
1185               memcpy (dest->elems, dest->elems + sbase,
1186                       delta * sizeof (int));
1187               break;
1188             }
1189         }
1190     }
1191
1192   return REG_NOERROR;
1193 }
1194
1195 /* Insert the new element ELEM to the re_node_set* SET.
1196    SET should not already have ELEM.
1197    return -1 if an error is occured, return 1 otherwise.  */
1198
1199 static int
1200 re_node_set_insert (set, elem)
1201      re_node_set *set;
1202      int elem;
1203 {
1204   int idx;
1205   /* In case the set is empty.  */
1206   if (set->alloc == 0)
1207     {
1208       if (BE (re_node_set_init_1 (set, elem) == REG_NOERROR, 1))
1209         return 1;
1210       else
1211         return -1;
1212     }
1213
1214   if (BE (set->nelem, 0) == 0)
1215     {
1216       /* We already guaranteed above that set->alloc != 0.  */
1217       set->elems[0] = elem;
1218       ++set->nelem;
1219       return 1;
1220     }
1221
1222   /* Realloc if we need.  */
1223   if (set->alloc == set->nelem)
1224     {
1225       int *new_array;
1226       set->alloc = set->alloc * 2;
1227       new_array = re_realloc (set->elems, int, set->alloc);
1228       if (BE (new_array == NULL, 0))
1229         return -1;
1230       set->elems = new_array;
1231     }
1232
1233   /* Move the elements which follows the new element.  Test the
1234      first element separately to skip a check in the inner loop.  */
1235   if (elem < set->elems[0])
1236     {
1237       idx = 0;
1238       for (idx = set->nelem; idx > 0; idx--)
1239         set->elems[idx] = set->elems[idx - 1];
1240     }
1241   else
1242     {
1243       for (idx = set->nelem; set->elems[idx - 1] > elem; idx--)
1244         set->elems[idx] = set->elems[idx - 1];
1245     }
1246
1247   /* Insert the new element.  */
1248   set->elems[idx] = elem;
1249   ++set->nelem;
1250   return 1;
1251 }
1252
1253 /* Compare two node sets SET1 and SET2.
1254    return 1 if SET1 and SET2 are equivalent, return 0 otherwise.  */
1255
1256 static int
1257 re_node_set_compare (set1, set2)
1258      const re_node_set *set1, *set2;
1259 {
1260   int i;
1261   if (set1 == NULL || set2 == NULL || set1->nelem != set2->nelem)
1262     return 0;
1263   for (i = set1->nelem ; --i >= 0 ; )
1264     if (set1->elems[i] != set2->elems[i])
1265       return 0;
1266   return 1;
1267 }
1268
1269 /* Return (idx + 1) if SET contains the element ELEM, return 0 otherwise.  */
1270
1271 static int
1272 re_node_set_contains (set, elem)
1273      const re_node_set *set;
1274      int elem;
1275 {
1276   int idx, right, mid;
1277   if (set->nelem <= 0)
1278     return 0;
1279
1280   /* Binary search the element.  */
1281   idx = 0;
1282   right = set->nelem - 1;
1283   while (idx < right)
1284     {
1285       mid = (idx + right) / 2;
1286       if (set->elems[mid] < elem)
1287         idx = mid + 1;
1288       else
1289         right = mid;
1290     }
1291   return set->elems[idx] == elem ? idx + 1 : 0;
1292 }
1293
1294 static void
1295 re_node_set_remove_at (set, idx)
1296      re_node_set *set;
1297      int idx;
1298 {
1299   if (idx < 0 || idx >= set->nelem)
1300     return;
1301   --set->nelem;
1302   for (; idx < set->nelem; idx++)
1303     set->elems[idx] = set->elems[idx + 1];
1304 }
1305 \f
1306
1307 /* Add the token TOKEN to dfa->nodes, and return the index of the token.
1308    Or return -1, if an error will be occured.  */
1309
1310 static int
1311 re_dfa_add_node (dfa, token, mode)
1312      re_dfa_t *dfa;
1313      re_token_t token;
1314      int mode;
1315 {
1316   if (BE (dfa->nodes_len >= dfa->nodes_alloc, 0))
1317     {
1318       int new_nodes_alloc = dfa->nodes_alloc * 2;
1319       re_token_t *new_array = re_realloc (dfa->nodes, re_token_t,
1320                                           new_nodes_alloc);
1321       if (BE (new_array == NULL, 0))
1322         return -1;
1323       dfa->nodes = new_array;
1324       if (mode)
1325         {
1326           int *new_nexts, *new_indices;
1327           re_node_set *new_edests, *new_eclosures, *new_inveclosures;
1328
1329           new_nexts = re_realloc (dfa->nexts, int, new_nodes_alloc);
1330           new_indices = re_realloc (dfa->org_indices, int, new_nodes_alloc);
1331           new_edests = re_realloc (dfa->edests, re_node_set, new_nodes_alloc);
1332           new_eclosures = re_realloc (dfa->eclosures, re_node_set,
1333                                       new_nodes_alloc);
1334           new_inveclosures = re_realloc (dfa->inveclosures, re_node_set,
1335                                          new_nodes_alloc);
1336           if (BE (new_nexts == NULL || new_indices == NULL
1337                   || new_edests == NULL || new_eclosures == NULL
1338                   || new_inveclosures == NULL, 0))
1339             return -1;
1340           dfa->nexts = new_nexts;
1341           dfa->org_indices = new_indices;
1342           dfa->edests = new_edests;
1343           dfa->eclosures = new_eclosures;
1344           dfa->inveclosures = new_inveclosures;
1345         }
1346       dfa->nodes_alloc = new_nodes_alloc;
1347     }
1348   dfa->nodes[dfa->nodes_len] = token;
1349   dfa->nodes[dfa->nodes_len].opt_subexp = 0;
1350   dfa->nodes[dfa->nodes_len].duplicated = 0;
1351   dfa->nodes[dfa->nodes_len].constraint = 0;
1352   return dfa->nodes_len++;
1353 }
1354
1355 static unsigned int inline
1356 calc_state_hash (nodes, context)
1357      const re_node_set *nodes;
1358      unsigned int context;
1359 {
1360   unsigned int hash = nodes->nelem + context;
1361   int i;
1362   for (i = 0 ; i < nodes->nelem ; i++)
1363     hash += nodes->elems[i];
1364   return hash;
1365 }
1366
1367 /* Search for the state whose node_set is equivalent to NODES.
1368    Return the pointer to the state, if we found it in the DFA.
1369    Otherwise create the new one and return it.  In case of an error
1370    return NULL and set the error code in ERR.
1371    Note: - We assume NULL as the invalid state, then it is possible that
1372            return value is NULL and ERR is REG_NOERROR.
1373          - We never return non-NULL value in case of any errors, it is for
1374            optimization.  */
1375
1376 static re_dfastate_t*
1377 re_acquire_state (err, dfa, nodes)
1378      reg_errcode_t *err;
1379      re_dfa_t *dfa;
1380      const re_node_set *nodes;
1381 {
1382   unsigned int hash;
1383   re_dfastate_t *new_state;
1384   struct re_state_table_entry *spot;
1385   int i;
1386   if (BE (nodes->nelem == 0, 0))
1387     {
1388       *err = REG_NOERROR;
1389       return NULL;
1390     }
1391   hash = calc_state_hash (nodes, 0);
1392   spot = dfa->state_table + (hash & dfa->state_hash_mask);
1393
1394   for (i = 0 ; i < spot->num ; i++)
1395     {
1396       re_dfastate_t *state = spot->array[i];
1397       if (hash != state->hash)
1398         continue;
1399       if (re_node_set_compare (&state->nodes, nodes))
1400         return state;
1401     }
1402
1403   /* There are no appropriate state in the dfa, create the new one.  */
1404   new_state = create_ci_newstate (dfa, nodes, hash);
1405   if (BE (new_state != NULL, 1))
1406     return new_state;
1407   else
1408     {
1409       *err = REG_ESPACE;
1410       return NULL;
1411     }
1412 }
1413
1414 /* Search for the state whose node_set is equivalent to NODES and
1415    whose context is equivalent to CONTEXT.
1416    Return the pointer to the state, if we found it in the DFA.
1417    Otherwise create the new one and return it.  In case of an error
1418    return NULL and set the error code in ERR.
1419    Note: - We assume NULL as the invalid state, then it is possible that
1420            return value is NULL and ERR is REG_NOERROR.
1421          - We never return non-NULL value in case of any errors, it is for
1422            optimization.  */
1423
1424 static re_dfastate_t*
1425 re_acquire_state_context (err, dfa, nodes, context)
1426      reg_errcode_t *err;
1427      re_dfa_t *dfa;
1428      const re_node_set *nodes;
1429      unsigned int context;
1430 {
1431   unsigned int hash;
1432   re_dfastate_t *new_state;
1433   struct re_state_table_entry *spot;
1434   int i;
1435   if (nodes->nelem == 0)
1436     {
1437       *err = REG_NOERROR;
1438       return NULL;
1439     }
1440   hash = calc_state_hash (nodes, context);
1441   spot = dfa->state_table + (hash & dfa->state_hash_mask);
1442
1443   for (i = 0 ; i < spot->num ; i++)
1444     {
1445       re_dfastate_t *state = spot->array[i];
1446       if (state->hash == hash
1447           && state->context == context
1448           && re_node_set_compare (state->entrance_nodes, nodes))
1449         return state;
1450     }
1451   /* There are no appropriate state in `dfa', create the new one.  */
1452   new_state = create_cd_newstate (dfa, nodes, context, hash);
1453   if (BE (new_state != NULL, 1))
1454     return new_state;
1455   else
1456     {
1457       *err = REG_ESPACE;
1458       return NULL;
1459     }
1460 }
1461
1462 /* Allocate memory for DFA state and initialize common properties.
1463    Return the new state if succeeded, otherwise return NULL.  */
1464
1465 static re_dfastate_t *
1466 create_newstate_common (dfa, nodes, hash)
1467      re_dfa_t *dfa;
1468      const re_node_set *nodes;
1469      unsigned int hash;
1470 {
1471   re_dfastate_t *newstate;
1472   reg_errcode_t err;
1473   newstate = (re_dfastate_t *) calloc (sizeof (re_dfastate_t), 1);
1474   if (BE (newstate == NULL, 0))
1475     return NULL;
1476   err = re_node_set_init_copy (&newstate->nodes, nodes);
1477   if (BE (err != REG_NOERROR, 0))
1478     {
1479       re_free (newstate);
1480       return NULL;
1481     }
1482   newstate->trtable = NULL;
1483   newstate->hash = hash;
1484   return newstate;
1485 }
1486
1487 /* Store the new state NEWSTATE whose hash value is HASH in appropriate
1488    position.  Return value indicate the error code if failed.  */
1489
1490 static reg_errcode_t
1491 register_state (dfa, newstate, hash)
1492      re_dfa_t *dfa;
1493      re_dfastate_t *newstate;
1494      unsigned int hash;
1495 {
1496   struct re_state_table_entry *spot;
1497   spot = dfa->state_table + (hash & dfa->state_hash_mask);
1498
1499   if (BE (spot->alloc <= spot->num, 0))
1500     {
1501       int new_alloc = 2 * spot->num + 2;
1502       re_dfastate_t **new_array = re_realloc (spot->array, re_dfastate_t *,
1503                                               new_alloc);
1504       if (BE (new_array == NULL, 0))
1505         return REG_ESPACE;
1506       spot->array = new_array;
1507       spot->alloc = new_alloc;
1508     }
1509   spot->array[spot->num++] = newstate;
1510   return REG_NOERROR;
1511 }
1512
1513 /* Create the new state which is independ of contexts.
1514    Return the new state if succeeded, otherwise return NULL.  */
1515
1516 static re_dfastate_t *
1517 create_ci_newstate (dfa, nodes, hash)
1518      re_dfa_t *dfa;
1519      const re_node_set *nodes;
1520      unsigned int hash;
1521 {
1522   int i;
1523   reg_errcode_t err;
1524   re_dfastate_t *newstate;
1525   newstate = create_newstate_common (dfa, nodes, hash);
1526   if (BE (newstate == NULL, 0))
1527     return NULL;
1528   newstate->entrance_nodes = &newstate->nodes;
1529
1530   for (i = 0 ; i < nodes->nelem ; i++)
1531     {
1532       re_token_t *node = dfa->nodes + nodes->elems[i];
1533       re_token_type_t type = node->type;
1534       if (type == CHARACTER && !node->constraint)
1535         continue;
1536
1537       /* If the state has the halt node, the state is a halt state.  */
1538       else if (type == END_OF_RE)
1539         newstate->halt = 1;
1540 #ifdef RE_ENABLE_I18N
1541       else if (type == COMPLEX_BRACKET
1542                || type == OP_UTF8_PERIOD
1543                || (type == OP_PERIOD && dfa->mb_cur_max > 1))
1544         newstate->accept_mb = 1;
1545 #endif /* RE_ENABLE_I18N */
1546       else if (type == OP_BACK_REF)
1547         newstate->has_backref = 1;
1548       else if (type == ANCHOR || node->constraint)
1549         newstate->has_constraint = 1;
1550     }
1551   err = register_state (dfa, newstate, hash);
1552   if (BE (err != REG_NOERROR, 0))
1553     {
1554       free_state (newstate);
1555       newstate = NULL;
1556     }
1557   return newstate;
1558 }
1559
1560 /* Create the new state which is depend on the context CONTEXT.
1561    Return the new state if succeeded, otherwise return NULL.  */
1562
1563 static re_dfastate_t *
1564 create_cd_newstate (dfa, nodes, context, hash)
1565      re_dfa_t *dfa;
1566      const re_node_set *nodes;
1567      unsigned int context, hash;
1568 {
1569   int i, nctx_nodes = 0;
1570   reg_errcode_t err;
1571   re_dfastate_t *newstate;
1572
1573   newstate = create_newstate_common (dfa, nodes, hash);
1574   if (BE (newstate == NULL, 0))
1575     return NULL;
1576   newstate->context = context;
1577   newstate->entrance_nodes = &newstate->nodes;
1578
1579   for (i = 0 ; i < nodes->nelem ; i++)
1580     {
1581       unsigned int constraint = 0;
1582       re_token_t *node = dfa->nodes + nodes->elems[i];
1583       re_token_type_t type = node->type;
1584       if (node->constraint)
1585         constraint = node->constraint;
1586
1587       if (type == CHARACTER && !constraint)
1588         continue;
1589       /* If the state has the halt node, the state is a halt state.  */
1590       else if (type == END_OF_RE)
1591         newstate->halt = 1;
1592 #ifdef RE_ENABLE_I18N
1593       else if (type == COMPLEX_BRACKET
1594                || type == OP_UTF8_PERIOD
1595                || (type == OP_PERIOD && dfa->mb_cur_max > 1))
1596         newstate->accept_mb = 1;
1597 #endif /* RE_ENABLE_I18N */
1598       else if (type == OP_BACK_REF)
1599         newstate->has_backref = 1;
1600       else if (type == ANCHOR)
1601         constraint = node->opr.ctx_type;
1602
1603       if (constraint)
1604         {
1605           if (newstate->entrance_nodes == &newstate->nodes)
1606             {
1607               newstate->entrance_nodes = re_malloc (re_node_set, 1);
1608               if (BE (newstate->entrance_nodes == NULL, 0))
1609                 {
1610                   free_state (newstate);
1611                   return NULL;
1612                 }
1613               re_node_set_init_copy (newstate->entrance_nodes, nodes);
1614               nctx_nodes = 0;
1615               newstate->has_constraint = 1;
1616             }
1617
1618           if (NOT_SATISFY_PREV_CONSTRAINT (constraint,context))
1619             {
1620               re_node_set_remove_at (&newstate->nodes, i - nctx_nodes);
1621               ++nctx_nodes;
1622             }
1623         }
1624     }
1625   err = register_state (dfa, newstate, hash);
1626   if (BE (err != REG_NOERROR, 0))
1627     {
1628       free_state (newstate);
1629       newstate = NULL;
1630     }
1631   return  newstate;
1632 }
1633
1634 static void
1635 free_state (state)
1636      re_dfastate_t *state;
1637 {
1638   if (state->entrance_nodes != &state->nodes)
1639     {
1640       re_node_set_free (state->entrance_nodes);
1641       re_free (state->entrance_nodes);
1642     }
1643   re_node_set_free (&state->nodes);
1644   re_free (state->trtable);
1645   re_free (state);
1646 }