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