* Makefile.am, regcomp.c, regex.c, regex_internal.c, regex_internal.h,
[gnupg.git] / util / regexec.c
1 /* Extended regular expression matching and search library.
2    Copyright (C) 2002 Free Software Foundation, Inc.
3    This file is part of the GNU C Library.
4    Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
5
6    The GNU C Library is free software; you can redistribute it and/or
7    modify it under the terms of the GNU Lesser General Public
8    License as published by the Free Software Foundation; either
9    version 2.1 of the License, or (at your option) any later version.
10
11    The GNU C Library is distributed in the hope that it will be useful,
12    but WITHOUT ANY WARRANTY; without even the implied warranty of
13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14    Lesser General Public License for more details.
15
16    You should have received a copy of the GNU Lesser General Public
17    License along with the GNU C Library; if not, write to the Free
18    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
19    02111-1307 USA.  */
20
21 #include <assert.h>
22 #include <ctype.h>
23 #include <stdio.h>
24 #include <stdlib.h>
25 #include <string.h>
26
27 #if defined HAVE_WCHAR_H || defined _LIBC
28 # include <wchar.h>
29 #endif /* HAVE_WCHAR_H || _LIBC */
30 #if defined HAVE_WCTYPE_H || defined _LIBC
31 # include <wctype.h>
32 #endif /* HAVE_WCTYPE_H || _LIBC */
33
34 #ifdef _LIBC
35 # ifndef _RE_DEFINE_LOCALE_FUNCTIONS
36 #  define _RE_DEFINE_LOCALE_FUNCTIONS 1
37 #  include <locale/localeinfo.h>
38 #  include <locale/elem-hash.h>
39 #  include <locale/coll-lookup.h>
40 # endif
41 #endif
42
43 #include "_regex.h" /* gnupg */
44 #include "regex_internal.h"
45
46 static reg_errcode_t match_ctx_init (re_match_context_t *cache, int eflags,
47                                      re_string_t *input, int n);
48 static void match_ctx_free (re_match_context_t *cache);
49 static reg_errcode_t match_ctx_add_entry (re_match_context_t *cache, int node,
50                                           int str_idx, int from, int to);
51 static void match_ctx_clear_flag (re_match_context_t *mctx);
52 static void sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts,
53                            re_dfastate_t **limited_sts, int last_node,
54                            int last_str_idx, int check_subexp);
55 static reg_errcode_t re_search_internal (const regex_t *preg,
56                                          const char *string, int length,
57                                          int start, int range, int stop,
58                                          size_t nmatch, regmatch_t pmatch[],
59                                          int eflags);
60 static int re_search_2_stub (struct re_pattern_buffer *bufp,
61                              const char *string1, int length1,
62                              const char *string2, int length2,
63                              int start, int range, struct re_registers *regs,
64                              int stop, int ret_len);
65 static int re_search_stub (struct re_pattern_buffer *bufp,
66                            const char *string, int length, int start,
67                            int range, int stop, struct re_registers *regs,
68                            int ret_len);
69 static unsigned re_copy_regs (struct re_registers *regs, regmatch_t *pmatch,
70                               int nregs, int regs_allocated);
71 static inline re_dfastate_t *acquire_init_state_context (reg_errcode_t *err,
72                                                          const regex_t *preg,
73                                                          const re_match_context_t *mctx,
74                                                          int idx);
75 static int check_matching (const regex_t *preg, re_match_context_t *mctx,
76                            int fl_search, int fl_longest_match);
77 static int check_halt_node_context (const re_dfa_t *dfa, int node,
78                                     unsigned int context);
79 static int check_halt_state_context (const regex_t *preg,
80                                      const re_dfastate_t *state,
81                                      const re_match_context_t *mctx, int idx);
82 static void update_regs (re_dfa_t *dfa, regmatch_t *pmatch, int cur_node,
83                          int cur_idx, int nmatch);
84 static int proceed_next_node (const regex_t *preg, int nregs, regmatch_t *regs,
85                               const re_match_context_t *mctx,
86                               int *pidx, int node, re_node_set *eps_via_nodes,
87                               struct re_fail_stack_t *fs);
88 static reg_errcode_t push_fail_stack (struct re_fail_stack_t *fs, 
89                                       int str_idx, int *dests, int nregs,
90                                       regmatch_t *regs,
91                                       re_node_set *eps_via_nodes);
92 static int pop_fail_stack (struct re_fail_stack_t *fs, int *pidx, int nregs,
93                            regmatch_t *regs, re_node_set *eps_via_nodes);
94 static reg_errcode_t set_regs (const regex_t *preg,
95                                const re_match_context_t *mctx,
96                                size_t nmatch, regmatch_t *pmatch,
97                                int fl_backtrack);
98 #ifdef RE_ENABLE_I18N
99 static int sift_states_iter_mb (const regex_t *preg,
100                                 const re_match_context_t *mctx,
101                                 re_sift_context_t *sctx,
102                                 int node_idx, int str_idx, int max_str_idx);
103 #endif /* RE_ENABLE_I18N */
104 static reg_errcode_t sift_states_backward (const regex_t *preg,
105                                            re_match_context_t *mctx,
106                                            re_sift_context_t *sctx);
107 static reg_errcode_t update_cur_sifted_state (const regex_t *preg,
108                                               re_match_context_t *mctx,
109                                               re_sift_context_t *sctx,
110                                               int str_idx,
111                                               re_node_set *dest_nodes);
112 static reg_errcode_t add_epsilon_src_nodes (re_dfa_t *dfa,
113                                             re_node_set *dest_nodes,
114                                             const re_node_set *candidates);
115 static reg_errcode_t sub_epsilon_src_nodes (re_dfa_t *dfa, int node,
116                                             re_node_set *dest_nodes,
117                                             const re_node_set *and_nodes);
118 static int check_dst_limits (re_dfa_t *dfa, re_node_set *limits,
119                              re_match_context_t *mctx, int dst_node,
120                              int dst_idx, int src_node, int src_idx);
121 static int check_dst_limits_calc_pos (re_dfa_t *dfa, re_match_context_t *mctx,
122                                       int limit, re_node_set *eclosures,
123                                       int subexp_idx, int node, int str_idx);
124 static reg_errcode_t check_subexp_limits (re_dfa_t *dfa,
125                                           re_node_set *dest_nodes,
126                                           const re_node_set *candidates,
127                                           re_node_set *limits,
128                                           struct re_backref_cache_entry *bkref_ents,
129                                           int str_idx);
130 static reg_errcode_t search_subexp (const regex_t *preg,
131                                     re_match_context_t *mctx,
132                                     re_sift_context_t *sctx, int str_idx,
133                                     re_node_set *dest_nodes);
134 static reg_errcode_t sift_states_bkref (const regex_t *preg,
135                                         re_match_context_t *mctx,
136                                         re_sift_context_t *sctx,
137                                         int str_idx, re_node_set *dest_nodes);
138 static reg_errcode_t clean_state_log_if_need (re_match_context_t *mctx,
139                                               int next_state_log_idx);
140 static reg_errcode_t merge_state_array (re_dfa_t *dfa, re_dfastate_t **dst,
141                                         re_dfastate_t **src, int num);
142 static re_dfastate_t *transit_state (reg_errcode_t *err, const regex_t *preg,
143                                      re_match_context_t *mctx,
144                                      re_dfastate_t *state, int fl_search);
145 static re_dfastate_t *transit_state_sb (reg_errcode_t *err, const regex_t *preg,
146                                         re_dfastate_t *pstate,
147                                         int fl_search,
148                                         re_match_context_t *mctx);
149 #ifdef RE_ENABLE_I18N
150 static reg_errcode_t transit_state_mb (const regex_t *preg,
151                                        re_dfastate_t *pstate,
152                                        re_match_context_t *mctx);
153 #endif /* RE_ENABLE_I18N */
154 static reg_errcode_t transit_state_bkref (const regex_t *preg,
155                                           re_dfastate_t *pstate,
156                                           re_match_context_t *mctx);
157 static reg_errcode_t transit_state_bkref_loop (const regex_t *preg,
158                                                re_node_set *nodes,
159                                                re_dfastate_t **work_state_log,
160                                                re_match_context_t *mctx);
161 static re_dfastate_t **build_trtable (const regex_t *dfa,
162                                       const re_dfastate_t *state,
163                                       int fl_search);
164 #ifdef RE_ENABLE_I18N
165 static int check_node_accept_bytes (const regex_t *preg, int node_idx,
166                                     const re_string_t *input, int idx);
167 # ifdef _LIBC
168 static unsigned int find_collation_sequence_value (const unsigned char *mbs,
169                                                    size_t name_len);
170 # endif /* _LIBC */
171 #endif /* RE_ENABLE_I18N */
172 static int group_nodes_into_DFAstates (const regex_t *dfa,
173                                        const re_dfastate_t *state,
174                                        re_node_set *states_node,
175                                        bitset *states_ch);
176 static int check_node_accept (const regex_t *preg, const re_token_t *node,
177                               const re_match_context_t *mctx, int idx);
178 static reg_errcode_t extend_buffers (re_match_context_t *mctx);
179 \f
180 /* Entry point for POSIX code.  */
181
182 /* regexec searches for a given pattern, specified by PREG, in the
183    string STRING.
184
185    If NMATCH is zero or REG_NOSUB was set in the cflags argument to
186    `regcomp', we ignore PMATCH.  Otherwise, we assume PMATCH has at
187    least NMATCH elements, and we set them to the offsets of the
188    corresponding matched substrings.
189
190    EFLAGS specifies `execution flags' which affect matching: if
191    REG_NOTBOL is set, then ^ does not match at the beginning of the
192    string; if REG_NOTEOL is set, then $ does not match at the end.
193
194    We return 0 if we find a match and REG_NOMATCH if not.  */
195
196 int
197 regexec (preg, string, nmatch, pmatch, eflags)
198     const regex_t *__restrict preg;
199     const char *__restrict string;
200     size_t nmatch;
201     regmatch_t pmatch[];
202     int eflags;
203 {
204   reg_errcode_t err;
205   int length = strlen (string);
206   if (preg->no_sub)
207     err = re_search_internal (preg, string, length, 0, length, length, 0,
208                               NULL, eflags);
209   else
210     err = re_search_internal (preg, string, length, 0, length, length, nmatch,
211                               pmatch, eflags);
212   return err != REG_NOERROR;
213 }
214 #ifdef _LIBC
215 weak_alias (__regexec, regexec)
216 #endif
217
218 /* Entry points for GNU code.  */
219
220 /* re_match, re_search, re_match_2, re_search_2
221
222    The former two functions operate on STRING with length LENGTH,
223    while the later two operate on concatenation of STRING1 and STRING2
224    with lengths LENGTH1 and LENGTH2, respectively.
225
226    re_match() matches the compiled pattern in BUFP against the string,
227    starting at index START.
228
229    re_search() first tries matching at index START, then it tries to match
230    starting from index START + 1, and so on.  The last start position tried
231    is START + RANGE.  (Thus RANGE = 0 forces re_search to operate the same
232    way as re_match().)
233
234    The parameter STOP of re_{match,search}_2 specifies that no match exceeding
235    the first STOP characters of the concatenation of the strings should be
236    concerned.
237
238    If REGS is not NULL, and BUFP->no_sub is not set, the offsets of the match
239    and all groups is stroed in REGS.  (For the "_2" variants, the offsets are
240    computed relative to the concatenation, not relative to the individual
241    strings.)
242
243    On success, re_match* functions return the length of the match, re_search*
244    return the position of the start of the match.  Return value -1 means no
245    match was found and -2 indicates an internal error.  */
246
247 int
248 re_match (bufp, string, length, start, regs)
249     struct re_pattern_buffer *bufp;
250     const char *string;
251     int length, start;
252     struct re_registers *regs;
253 {
254   return re_search_stub (bufp, string, length, start, 0, length, regs, 1);
255 }
256 #ifdef _LIBC
257 weak_alias (__re_match, re_match)
258 #endif
259
260 int
261 re_search (bufp, string, length, start, range, regs)
262     struct re_pattern_buffer *bufp;
263     const char *string;
264     int length, start, range;
265     struct re_registers *regs;
266 {
267   return re_search_stub (bufp, string, length, start, range, length, regs, 0);
268 }
269 #ifdef _LIBC
270 weak_alias (__re_search, re_search)
271 #endif
272
273 int
274 re_match_2 (bufp, string1, length1, string2, length2, start, regs, stop)
275     struct re_pattern_buffer *bufp;
276     const char *string1, *string2;
277     int length1, length2, start, stop;
278     struct re_registers *regs;
279 {
280   return re_search_2_stub (bufp, string1, length1, string2, length2,
281                            start, 0, regs, stop, 1);
282 }
283 #ifdef _LIBC
284 weak_alias (__re_match_2, re_match_2)
285 #endif
286
287 int
288 re_search_2 (bufp, string1, length1, string2, length2, start, range, regs, stop)
289     struct re_pattern_buffer *bufp;
290     const char *string1, *string2;
291     int length1, length2, start, range, stop;
292     struct re_registers *regs;
293 {
294   return re_search_2_stub (bufp, string1, length1, string2, length2,
295                            start, range, regs, stop, 0);
296 }
297 #ifdef _LIBC
298 weak_alias (__re_search_2, re_search_2)
299 #endif
300
301 static int
302 re_search_2_stub (bufp, string1, length1, string2, length2, start, range, regs,
303                   stop, ret_len)
304     struct re_pattern_buffer *bufp;
305     const char *string1, *string2;
306     int length1, length2, start, range, stop, ret_len;
307     struct re_registers *regs;
308 {
309   const char *str;
310   int rval;
311   int len = length1 + length2;
312   int free_str = 0;
313
314   if (BE (length1 < 0 || length2 < 0 || stop < 0, 0))
315     return -2;
316
317   /* Concatenate the strings.  */
318   if (length2 > 0)
319     if (length1 > 0)
320       {
321         char *s = re_malloc (char, len);
322
323         if (BE (s == NULL, 0))
324           return -2;
325         memcpy (s, string1, length1);
326         memcpy (s + length1, string2, length2);
327         str = s;
328         free_str = 1;
329       }
330     else
331       str = string2;
332   else
333     str = string1;
334
335   rval = re_search_stub (bufp, str, len, start, range, stop, regs,
336                          ret_len);
337   if (free_str)
338       re_free ((char *) str);
339   return rval;
340 }
341
342 /* The parameters have the same meaning as those of re_search.
343    Additional parameters:
344    If RET_LEN is nonzero the length of the match is returned (re_match style);
345    otherwise the position of the match is returned.  */
346
347 static int
348 re_search_stub (bufp, string, length, start, range, stop, regs, ret_len)
349     struct re_pattern_buffer *bufp;
350     const char *string;
351     int length, start, range, stop, ret_len;
352     struct re_registers *regs;
353 {
354   reg_errcode_t result;
355   regmatch_t *pmatch;
356   int nregs, rval;
357   int eflags = 0;
358
359   /* Check for out-of-range.  */
360   if (BE (start < 0 || start > length, 0))
361     return -1;
362   if (BE (start + range > length, 0))
363     range = length - start;
364   else if (BE (start + range < 0, 0))
365     range = -start;
366
367   eflags |= (bufp->not_bol) ? REG_NOTBOL : 0;
368   eflags |= (bufp->not_eol) ? REG_NOTEOL : 0;
369
370   /* Compile fastmap if we haven't yet.  */
371   if (range > 0 && bufp->fastmap != NULL && !bufp->fastmap_accurate)
372     re_compile_fastmap (bufp);
373
374   if (BE (bufp->no_sub, 0))
375     regs = NULL;
376
377   /* We need at least 1 register.  */
378   if (regs == NULL)
379     nregs = 1;
380   else if (BE (bufp->regs_allocated == REGS_FIXED &&
381                regs->num_regs < bufp->re_nsub + 1, 0))
382     {
383       nregs = regs->num_regs;
384       if (BE (nregs < 1, 0))
385         {
386           /* Nothing can be copied to regs.  */
387           regs = NULL;
388           nregs = 1;
389         }
390     }
391   else
392     nregs = bufp->re_nsub + 1;
393   pmatch = re_malloc (regmatch_t, nregs);
394   if (BE (pmatch == NULL, 0))
395     return -2;
396
397   result = re_search_internal (bufp, string, length, start, range, stop,
398                                nregs, pmatch, eflags);
399
400   rval = 0;
401
402   /* I hope we needn't fill ther regs with -1's when no match was found.  */
403   if (result != REG_NOERROR)
404     rval = -1;
405   else if (regs != NULL)
406     {
407       /* If caller wants register contents data back, copy them.  */
408       bufp->regs_allocated = re_copy_regs (regs, pmatch, nregs,
409                                            bufp->regs_allocated);
410       if (BE (bufp->regs_allocated == REGS_UNALLOCATED, 0))
411         rval = -2;
412     }
413
414   if (BE (rval == 0, 1))
415     {
416       if (ret_len)
417         {
418           assert (pmatch[0].rm_so == start);
419           rval = pmatch[0].rm_eo - start;
420         }
421       else
422         rval = pmatch[0].rm_so;
423     }
424   re_free (pmatch);
425   return rval;
426 }
427
428 static unsigned
429 re_copy_regs (regs, pmatch, nregs, regs_allocated)
430     struct re_registers *regs;
431     regmatch_t *pmatch;
432     int nregs, regs_allocated;
433 {
434   int rval = REGS_REALLOCATE;
435   int i;
436   int need_regs = nregs + 1;
437   /* We need one extra element beyond `num_regs' for the `-1' marker GNU code
438      uses.  */
439
440   /* Have the register data arrays been allocated?  */
441   if (regs_allocated == REGS_UNALLOCATED)
442     { /* No.  So allocate them with malloc.  */
443       regs->start = re_malloc (regoff_t, need_regs);
444       if (BE (regs->start == NULL, 0))
445         return REGS_UNALLOCATED;
446       regs->end = re_malloc (regoff_t, need_regs);
447       if (BE (regs->end == NULL, 0))
448         {
449           re_free (regs->start);
450           return REGS_UNALLOCATED;
451         }
452       regs->num_regs = need_regs;
453     }
454   else if (regs_allocated == REGS_REALLOCATE)
455     { /* Yes.  If we need more elements than were already
456          allocated, reallocate them.  If we need fewer, just
457          leave it alone.  */
458       if (need_regs > regs->num_regs)
459         {
460           regs->start = re_realloc (regs->start, regoff_t, need_regs);
461           if (BE (regs->start == NULL, 0))
462             {
463               if (regs->end != NULL)
464                 re_free (regs->end);
465               return REGS_UNALLOCATED;
466             }
467           regs->end = re_realloc (regs->end, regoff_t, need_regs);
468           if (BE (regs->end == NULL, 0))
469             {
470               re_free (regs->start);
471               return REGS_UNALLOCATED;
472             }
473           regs->num_regs = need_regs;
474         }
475     }
476   else
477     {
478       assert (regs_allocated == REGS_FIXED);
479       /* This function may not be called with REGS_FIXED and nregs too big.  */
480       assert (regs->num_regs >= nregs);
481       rval = REGS_FIXED;
482     }
483
484   /* Copy the regs.  */
485   for (i = 0; i < nregs; ++i)
486     {
487       regs->start[i] = pmatch[i].rm_so;
488       regs->end[i] = pmatch[i].rm_eo;
489     }
490   for ( ; i < regs->num_regs; ++i)
491     regs->start[i] = regs->end[i] = -1;
492
493   return rval;
494 }
495
496 /* Set REGS to hold NUM_REGS registers, storing them in STARTS and
497    ENDS.  Subsequent matches using PATTERN_BUFFER and REGS will use
498    this memory for recording register information.  STARTS and ENDS
499    must be allocated using the malloc library routine, and must each
500    be at least NUM_REGS * sizeof (regoff_t) bytes long.
501
502    If NUM_REGS == 0, then subsequent matches should allocate their own
503    register data.
504
505    Unless this function is called, the first search or match using
506    PATTERN_BUFFER will allocate its own register data, without
507    freeing the old data.  */
508
509 void
510 re_set_registers (bufp, regs, num_regs, starts, ends)
511     struct re_pattern_buffer *bufp;
512     struct re_registers *regs;
513     unsigned num_regs;
514     regoff_t *starts, *ends;
515 {
516   if (num_regs)
517     {
518       bufp->regs_allocated = REGS_REALLOCATE;
519       regs->num_regs = num_regs;
520       regs->start = starts;
521       regs->end = ends;
522     }
523   else
524     {
525       bufp->regs_allocated = REGS_UNALLOCATED;
526       regs->num_regs = 0;
527       regs->start = regs->end = (regoff_t *) 0;
528     }
529 }
530 #ifdef _LIBC
531 weak_alias (__re_set_registers, re_set_registers)
532 #endif
533 \f
534 /* Entry points compatible with 4.2 BSD regex library.  We don't define
535    them unless specifically requested.  */
536
537 #if defined _REGEX_RE_COMP || defined _LIBC
538 int
539 # ifdef _LIBC
540 weak_function
541 # endif
542 re_exec (s)
543      const char *s;
544 {
545   return 0 == regexec (&re_comp_buf, s, 0, NULL, 0);
546 }
547 #endif /* _REGEX_RE_COMP */
548 \f
549 static re_node_set empty_set;
550
551 /* Internal entry point.  */
552
553 /* Searches for a compiled pattern PREG in the string STRING, whose
554    length is LENGTH.  NMATCH, PMATCH, and EFLAGS have the same
555    mingings with regexec.  START, and RANGE have the same meanings
556    with re_search.
557    Return REG_NOERROR if we find a match, and REG_NOMATCH if not,
558    otherwise return the error code.
559    Note: We assume front end functions already check ranges.
560    (START + RANGE >= 0 && START + RANGE <= LENGTH)  */
561
562 static reg_errcode_t
563 re_search_internal (preg, string, length, start, range, stop, nmatch, pmatch,
564                     eflags)
565     const regex_t *preg;
566     const char *string;
567     int length, start, range, stop, eflags;
568     size_t nmatch;
569     regmatch_t pmatch[];
570 {
571   reg_errcode_t err;
572   re_dfa_t *dfa = (re_dfa_t *)preg->buffer;
573   re_string_t input;
574   int left_lim, right_lim, incr;
575   int fl_longest_match, match_first, match_last = -1;
576   re_match_context_t mctx;
577   char *fastmap = ((preg->fastmap != NULL && preg->fastmap_accurate)
578                    ? preg->fastmap : NULL);
579
580   /* Check if the DFA haven't been compiled.  */
581   if (BE (preg->used == 0 || dfa->init_state == NULL
582           || dfa->init_state_word == NULL || dfa->init_state_nl == NULL
583           || dfa->init_state_begbuf == NULL, 0))
584     return REG_NOMATCH;
585
586   re_node_set_init_empty (&empty_set);
587
588   /* We must check the longest matching, if nmatch > 0.  */
589   fl_longest_match = (nmatch != 0);
590
591   err = re_string_allocate (&input, string, length, dfa->nodes_len + 1,
592                             preg->translate, preg->syntax & RE_ICASE);
593   if (BE (err != REG_NOERROR, 0))
594     return err;
595   input.stop = stop;
596
597   err = match_ctx_init (&mctx, eflags, &input, dfa->nbackref * 2);
598   if (BE (err != REG_NOERROR, 0))
599     return err;
600
601   /* We will log all the DFA states through which the dfa pass,
602      if nmatch > 1, or this dfa has "multibyte node", which is a
603      back-reference or a node which can accept multibyte character or
604      multi character collating element.  */
605   if (nmatch > 1 || dfa->has_mb_node)
606     {
607       mctx.state_log = re_malloc (re_dfastate_t *, dfa->nodes_len + 1);
608       if (BE (mctx.state_log == NULL, 0))
609         return REG_ESPACE;
610     }
611   else
612     mctx.state_log = NULL;
613
614 #ifdef DEBUG
615   /* We assume front-end functions already check them.  */
616   assert (start + range >= 0 && start + range <= length);
617 #endif
618
619   match_first = start;
620   input.tip_context = ((eflags & REG_NOTBOL) ? CONTEXT_BEGBUF
621                        : CONTEXT_NEWLINE | CONTEXT_BEGBUF);
622
623   /* Check incrementally whether of not the input string match.  */
624   incr = (range < 0) ? -1 : 1;
625   left_lim = (range < 0) ? start + range : start;
626   right_lim = (range < 0) ? start : start + range;
627
628   for (;;)
629     {
630       /* At first get the current byte from input string.  */
631       int ch;
632       if (MB_CUR_MAX > 1 && (preg->syntax & RE_ICASE || preg->translate))
633         {
634           /* In this case, we can't determin easily the current byte,
635              since it might be a component byte of a multibyte character.
636              Then we use the constructed buffer instead.  */
637           /* If MATCH_FIRST is out of the valid range, reconstruct the
638              buffers.  */
639           if (input.raw_mbs_idx + input.valid_len <= match_first)
640             re_string_reconstruct (&input, match_first, eflags,
641                                    preg->newline_anchor);
642           /* If MATCH_FIRST is out of the buffer, leave it as '\0'.
643              Note that MATCH_FIRST must not be smaller than 0.  */
644           ch = ((match_first >= length) ? 0
645                 : re_string_byte_at (&input, match_first - input.raw_mbs_idx));
646         }
647       else
648         {
649           /* We apply translate/conversion manually, since it is trivial
650              in this case.  */
651           /* If MATCH_FIRST is out of the buffer, leave it as '\0'.
652              Note that MATCH_FIRST must not be smaller than 0.  */
653           ch = (match_first < length) ? (unsigned char)string[match_first] : 0;
654           /* Apply translation if we need.  */
655           ch = preg->translate ? preg->translate[ch] : ch;
656           /* In case of case insensitive mode, convert to upper case.  */
657           ch = ((preg->syntax & RE_ICASE) && islower (ch)) ? toupper (ch) : ch;
658         }
659
660       /* Eliminate inappropriate one by fastmap.  */
661       if (preg->can_be_null || fastmap == NULL || fastmap[ch])
662         {
663           /* Reconstruct the buffers so that the matcher can assume that
664              the matching starts from the begining of the buffer.  */
665           re_string_reconstruct (&input, match_first, eflags,
666                                  preg->newline_anchor);
667 #ifdef RE_ENABLE_I18N
668           /* Eliminate it when it is a component of a multibyte character
669              and isn't the head of a multibyte character.  */
670           if (MB_CUR_MAX == 1 || re_string_first_byte (&input, 0))
671 #endif
672             {
673               /* It seems to be appropriate one, then use the matcher.  */
674               /* We assume that the matching starts from 0.  */
675               mctx.state_log_top = mctx.nbkref_ents = mctx.max_mb_elem_len = 0;
676               match_last = check_matching (preg, &mctx, 0, fl_longest_match);
677               if (match_last != -1)
678                 {
679                   if (BE (match_last == -2, 0))
680                     return REG_ESPACE;
681                   else
682                     break; /* We found a matching.  */
683                 }
684             }
685         }
686       /* Update counter.  */
687       match_first += incr;
688       if (match_first < left_lim || right_lim < match_first)
689         break;
690     }
691
692   /* Set pmatch[] if we need.  */
693   if (match_last != -1 && nmatch > 0)
694     {
695       int reg_idx;
696
697       /* Initialize registers.  */
698       for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
699         pmatch[reg_idx].rm_so = pmatch[reg_idx].rm_eo = -1;
700
701       /* Set the points where matching start/end.  */
702       pmatch[0].rm_so = 0;
703       mctx.match_last = pmatch[0].rm_eo = match_last;
704
705       if (!preg->no_sub && nmatch > 1)
706         {
707           /* We need the ranges of all the subexpressions.  */
708           int halt_node;
709           re_dfastate_t **sifted_states;
710           re_dfastate_t **lim_states = NULL;
711           re_dfastate_t *pstate = mctx.state_log[match_last];
712           re_sift_context_t sctx;
713 #ifdef DEBUG
714           assert (mctx.state_log != NULL);
715 #endif
716           halt_node = check_halt_state_context (preg, pstate, &mctx,
717                                                 match_last);
718           if (dfa->has_plural_match)
719             {
720               match_ctx_clear_flag (&mctx);
721               sifted_states = re_malloc (re_dfastate_t *, match_last + 1);
722               if (BE (sifted_states == NULL, 0))
723                 return REG_ESPACE;
724               if (dfa->nbackref)
725                 {
726                   lim_states = calloc (sizeof (re_dfastate_t *),
727                                        match_last + 1);
728                   if (BE (lim_states == NULL, 0))
729                     return REG_ESPACE;
730                 }
731               sift_ctx_init (&sctx, sifted_states, lim_states, halt_node,
732                              mctx.match_last, 0);
733               err = sift_states_backward (preg, &mctx, &sctx);
734               if (BE (err != REG_NOERROR, 0))
735                 return err;
736               if (lim_states != NULL)
737                 {
738                   err = merge_state_array (dfa, sifted_states, lim_states,
739                                            match_last + 1);
740                   if (BE (err != REG_NOERROR, 0))
741                     return err;
742                   re_free (lim_states);
743                 }
744               re_node_set_free (&sctx.limits);
745               re_free (mctx.state_log);
746               mctx.state_log = sifted_states;
747             }
748           mctx.last_node = halt_node;
749           err = set_regs (preg, &mctx, nmatch, pmatch,
750                           dfa->has_plural_match && dfa->nbackref > 0);
751           if (BE (err != REG_NOERROR, 0))
752             return err;
753         }
754
755       /* At last, add the offset to the each registers, since we slided
756          the buffers so that We can assume that the matching starts from 0.  */
757       for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
758         if (pmatch[reg_idx].rm_so != -1)
759           {
760             pmatch[reg_idx].rm_so += match_first;
761             pmatch[reg_idx].rm_eo += match_first;
762           }
763     }
764
765   re_free (mctx.state_log);
766   if (dfa->nbackref)
767     match_ctx_free (&mctx);
768   re_string_destruct (&input);
769
770   return (match_last == -1) ? REG_NOMATCH : REG_NOERROR;
771 }
772
773 /* Acquire an initial state and return it.
774    We must select appropriate initial state depending on the context,
775    since initial states may have constraints like "\<", "^", etc..  */
776
777 static inline re_dfastate_t *
778 acquire_init_state_context (err, preg, mctx, idx)
779      reg_errcode_t *err;
780      const regex_t *preg;
781      const re_match_context_t *mctx;
782      int idx;
783 {
784   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
785
786   *err = REG_NOERROR;
787   if (dfa->init_state->has_constraint)
788     {
789       unsigned int context;
790       context =  re_string_context_at (mctx->input, idx - 1, mctx->eflags,
791                                        preg->newline_anchor);
792       if (IS_WORD_CONTEXT (context))
793         return dfa->init_state_word;
794       else if (IS_ORDINARY_CONTEXT (context))
795         return dfa->init_state;
796       else if (IS_BEGBUF_CONTEXT (context) && IS_NEWLINE_CONTEXT (context))
797         return dfa->init_state_begbuf;
798       else if (IS_NEWLINE_CONTEXT (context))
799         return dfa->init_state_nl;
800       else if (IS_BEGBUF_CONTEXT (context))
801         {
802           /* It is relatively rare case, then calculate on demand.  */
803           return  re_acquire_state_context (err, dfa,
804                                             dfa->init_state->entrance_nodes,
805                                             context);
806         }
807       else
808         /* Must not happen?  */
809         return dfa->init_state;
810     }
811   else
812     return dfa->init_state;
813 }
814
815 /* Check whether the regular expression match input string INPUT or not,
816    and return the index where the matching end, return -1 if not match,
817    or return -2 in case of an error.
818    FL_SEARCH means we must search where the matching starts,
819    FL_LONGEST_MATCH means we want the POSIX longest matching.
820    Note that the matcher assume that the maching starts from the current
821    index of the buffer.  */
822
823 static int
824 check_matching (preg, mctx, fl_search, fl_longest_match)
825     const regex_t *preg;
826     re_match_context_t *mctx;
827     int fl_search, fl_longest_match;
828 {
829   reg_errcode_t err;
830   int match = 0;
831   int match_last = -1;
832   int cur_str_idx = re_string_cur_idx (mctx->input);
833   re_dfastate_t *cur_state;
834
835   cur_state = acquire_init_state_context (&err, preg, mctx, cur_str_idx);
836   /* An initial state must not be NULL(invalid state).  */
837   if (BE (cur_state == NULL, 0))
838     return -2;
839   if (mctx->state_log != NULL)
840     mctx->state_log[cur_str_idx] = cur_state;
841
842   if (cur_state->has_backref)
843     {
844       int i;
845       re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
846       for (i = 0; i < cur_state->nodes.nelem; ++i)
847         {
848           re_token_type_t type;
849           int node = cur_state->nodes.elems[i];
850           int entity = (dfa->nodes[node].type != OP_CONTEXT_NODE ? node
851                         : dfa->nodes[node].opr.ctx_info->entity);
852           type = dfa->nodes[entity].type;
853           if (type == OP_BACK_REF)
854             {
855               int clexp_idx;
856               for (clexp_idx = 0; clexp_idx < cur_state->nodes.nelem;
857                    ++clexp_idx)
858                 {
859                   re_token_t *clexp_node;
860                   clexp_node = dfa->nodes + cur_state->nodes.elems[clexp_idx];
861                   if (clexp_node->type == OP_CLOSE_SUBEXP
862                       && clexp_node->opr.idx + 1== dfa->nodes[entity].opr.idx)
863                     {
864                       err = match_ctx_add_entry (mctx, node, 0, 0, 0);
865                       if (BE (err != REG_NOERROR, 0))
866                         return -2;
867                       break;
868                     }
869                 }
870             }
871         }
872     }
873
874   /* If the RE accepts NULL string.  */
875   if (cur_state->halt)
876     {
877       if (!cur_state->has_constraint
878           || check_halt_state_context (preg, cur_state, mctx, cur_str_idx))
879         {
880           if (!fl_longest_match)
881             return cur_str_idx;
882           else
883             {
884               match_last = cur_str_idx;
885               match = 1;
886             }
887         }
888     }
889
890   while (!re_string_eoi (mctx->input))
891     {
892       cur_state = transit_state (&err, preg, mctx, cur_state,
893                                  fl_search && !match);
894       if (cur_state == NULL) /* Reached at the invalid state or an error.  */
895         {
896           cur_str_idx = re_string_cur_idx (mctx->input);
897           if (BE (err != REG_NOERROR, 0))
898             return -2;
899           if (fl_search && !match)
900             {
901               /* Restart from initial state, since we are searching
902                  the point from where matching start.  */
903 #ifdef RE_ENABLE_I18N
904               if (MB_CUR_MAX == 1
905                   || re_string_first_byte (mctx->input, cur_str_idx))
906 #endif /* RE_ENABLE_I18N */
907                 cur_state = acquire_init_state_context (&err, preg, mctx,
908                                                         cur_str_idx);
909               if (BE (cur_state == NULL && err != REG_NOERROR, 0))
910                 return -2;
911               if (mctx->state_log != NULL)
912                 mctx->state_log[cur_str_idx] = cur_state;
913             }
914           else if (!fl_longest_match && match)
915             break;
916           else /* (fl_longest_match && match) || (!fl_search && !match)  */
917             {
918               if (mctx->state_log == NULL)
919                 break;
920               else
921                 {
922                   int max = mctx->state_log_top;
923                   for (; cur_str_idx <= max; ++cur_str_idx)
924                     if (mctx->state_log[cur_str_idx] != NULL)
925                       break;
926                   if (cur_str_idx > max)
927                     break;
928                 }
929             }
930         }
931
932       if (cur_state != NULL && cur_state->halt)
933         {
934           /* Reached at a halt state.
935              Check the halt state can satisfy the current context.  */
936           if (!cur_state->has_constraint
937               || check_halt_state_context (preg, cur_state, mctx,
938                                            re_string_cur_idx (mctx->input)))
939             {
940               /* We found an appropriate halt state.  */
941               match_last = re_string_cur_idx (mctx->input);
942               match = 1;
943               if (!fl_longest_match)
944                 break;
945             }
946         }
947    }
948   return match_last;
949 }
950
951 /* Check NODE match the current context.  */
952
953 static int check_halt_node_context (dfa, node, context)
954     const re_dfa_t *dfa;
955     int node;
956     unsigned int context;
957 {
958   int entity;
959   re_token_type_t type = dfa->nodes[node].type;
960   if (type == END_OF_RE)
961     return 1;
962   if (type != OP_CONTEXT_NODE)
963     return 0;
964   entity = dfa->nodes[node].opr.ctx_info->entity;
965   if (dfa->nodes[entity].type != END_OF_RE
966       || NOT_SATISFY_NEXT_CONSTRAINT (dfa->nodes[node].constraint, context))
967     return 0;
968   return 1;
969 }
970
971 /* Check the halt state STATE match the current context.
972    Return 0 if not match, if the node, STATE has, is a halt node and
973    match the context, return the node.  */
974
975 static int
976 check_halt_state_context (preg, state, mctx, idx)
977     const regex_t *preg;
978     const re_dfastate_t *state;
979     const re_match_context_t *mctx;
980     int idx;
981 {
982   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
983   int i;
984   unsigned int context;
985 #ifdef DEBUG
986   assert (state->halt);
987 #endif
988   context = re_string_context_at (mctx->input, idx, mctx->eflags,
989                                   preg->newline_anchor);
990   for (i = 0; i < state->nodes.nelem; ++i)
991     if (check_halt_node_context (dfa, state->nodes.elems[i], context))
992       return state->nodes.elems[i];
993   return 0;
994 }
995
996 /* Compute the next node to which "NFA" transit from NODE("NFA" is a NFA
997    corresponding to the DFA).
998    Return the destination node, and update EPS_VIA_NODES, return -1 in case
999    of errors.  */
1000
1001 static int
1002 proceed_next_node (preg, nregs, regs, mctx, pidx, node, eps_via_nodes, fs)
1003     const regex_t *preg;
1004     regmatch_t *regs;
1005     const re_match_context_t *mctx;
1006     int nregs, *pidx, node;
1007     re_node_set *eps_via_nodes;
1008     struct re_fail_stack_t *fs;
1009 {
1010   re_dfa_t *dfa = (re_dfa_t *)preg->buffer;
1011   int i, err, dest_node, cur_entity;
1012   dest_node = -1;
1013   cur_entity = ((dfa->nodes[node].type == OP_CONTEXT_NODE)
1014                 ? dfa->nodes[node].opr.ctx_info->entity : node);
1015   if (IS_EPSILON_NODE (dfa->nodes[node].type))
1016     {
1017       int ndest, dest_nodes[2], dest_entities[2];
1018       err = re_node_set_insert (eps_via_nodes, node);
1019       if (BE (err < 0, 0))
1020         return -1;
1021       /* Pick up valid destinations.  */
1022       for (ndest = 0, i = 0; i < mctx->state_log[*pidx]->nodes.nelem; ++i)
1023         {
1024           int candidate = mctx->state_log[*pidx]->nodes.elems[i];
1025           int entity;
1026           entity = ((dfa->nodes[candidate].type == OP_CONTEXT_NODE)
1027                     ? dfa->nodes[candidate].opr.ctx_info->entity : candidate);
1028           if (!re_node_set_contains (dfa->edests + node, entity))
1029             continue;
1030           dest_nodes[0] = (ndest == 0) ? candidate : dest_nodes[0];
1031           dest_entities[0] = (ndest == 0) ? entity : dest_entities[0];
1032           dest_nodes[1] = (ndest == 1) ? candidate : dest_nodes[1];
1033           dest_entities[1] = (ndest == 1) ? entity : dest_entities[1];
1034           ++ndest;
1035         }
1036       if (ndest <= 1)
1037         return ndest == 0 ? -1 : (ndest == 1 ? dest_nodes[0] : 0);
1038       if (dest_entities[0] > dest_entities[1])
1039         {
1040           int swap_work = dest_nodes[0];
1041           dest_nodes[0] = dest_nodes[1];
1042           dest_nodes[1] = swap_work;
1043         }
1044       /* In order to avoid infinite loop like "(a*)*".  */
1045       if (re_node_set_contains (eps_via_nodes, dest_nodes[0]))
1046         return dest_nodes[1];
1047       if (fs != NULL)
1048         push_fail_stack (fs, *pidx, dest_nodes, nregs, regs, eps_via_nodes);
1049       return dest_nodes[0];
1050     }
1051   else
1052     {
1053       int naccepted = 0, entity = node;
1054       re_token_type_t type = dfa->nodes[node].type;
1055       if (type == OP_CONTEXT_NODE)
1056         {
1057           entity = dfa->nodes[node].opr.ctx_info->entity;
1058           type = dfa->nodes[entity].type;
1059         }
1060
1061 #ifdef RE_ENABLE_I18N
1062       if (ACCEPT_MB_NODE (type))
1063         naccepted = check_node_accept_bytes (preg, entity, mctx->input, *pidx);
1064       else
1065 #endif /* RE_ENABLE_I18N */
1066       if (type == OP_BACK_REF)
1067         {
1068           int subexp_idx = dfa->nodes[entity].opr.idx;
1069           naccepted = regs[subexp_idx].rm_eo - regs[subexp_idx].rm_so;
1070           if (fs != NULL)
1071             {
1072               if (regs[subexp_idx].rm_so == -1 || regs[subexp_idx].rm_eo == -1)
1073                 return -1;
1074               else if (naccepted)
1075                 {
1076                   char *buf = re_string_get_buffer (mctx->input);
1077                   if (strncmp (buf + regs[subexp_idx].rm_so, buf + *pidx,
1078                                naccepted) != 0)
1079                     return -1;
1080                 }
1081             }
1082
1083           if (naccepted == 0)
1084             {
1085               err = re_node_set_insert (eps_via_nodes, node);
1086               if (BE (err < 0, 0))
1087                 return -2;
1088               dest_node = dfa->nexts[node];
1089               if (re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1090                                         dest_node))
1091                 return dest_node;
1092               for (i = 0; i < mctx->state_log[*pidx]->nodes.nelem; ++i)
1093                 {
1094                   dest_node = mctx->state_log[*pidx]->nodes.elems[i];
1095                   if ((dfa->nodes[dest_node].type == OP_CONTEXT_NODE
1096                        && (dfa->nexts[node]
1097                            == dfa->nodes[dest_node].opr.ctx_info->entity)))
1098                     return dest_node;
1099                 }
1100             }
1101         }
1102
1103       if (naccepted != 0
1104           || check_node_accept (preg, dfa->nodes + node, mctx, *pidx))
1105         {
1106           dest_node = dfa->nexts[node];
1107           *pidx = (naccepted == 0) ? *pidx + 1 : *pidx + naccepted;
1108           if (fs && (*pidx > mctx->match_last || mctx->state_log[*pidx] == NULL
1109                      || !re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1110                                                dest_node)))
1111             return -1;
1112           re_node_set_empty (eps_via_nodes);
1113           return dest_node;
1114         }
1115     }
1116   return -1;
1117 }
1118
1119 static reg_errcode_t
1120 push_fail_stack (fs, str_idx, dests, nregs, regs, eps_via_nodes)
1121      struct re_fail_stack_t *fs;
1122      int str_idx, *dests, nregs;
1123      regmatch_t *regs;
1124      re_node_set *eps_via_nodes;
1125 {
1126   reg_errcode_t err;
1127   int num = fs->num++;
1128   if (fs->num == fs->alloc)
1129     {
1130       fs->alloc *= 2;
1131       fs->stack = realloc (fs->stack, (sizeof (struct re_fail_stack_ent_t)
1132                                        * fs->alloc));
1133       if (fs->stack == NULL)
1134         return REG_ESPACE;
1135     }
1136   fs->stack[num].idx = str_idx;
1137   fs->stack[num].node = dests[1];
1138   fs->stack[num].regs = re_malloc (regmatch_t, nregs);
1139   memcpy (fs->stack[num].regs, regs, sizeof (regmatch_t) * nregs);
1140   err = re_node_set_init_copy (&fs->stack[num].eps_via_nodes, eps_via_nodes);
1141   return err;
1142 }
1143  
1144 static int
1145 pop_fail_stack (fs, pidx, nregs, regs, eps_via_nodes)
1146      struct re_fail_stack_t *fs;
1147      int *pidx, nregs;
1148      regmatch_t *regs;
1149      re_node_set *eps_via_nodes;
1150 {
1151   int num = --fs->num;
1152   assert (num >= 0);
1153  *pidx = fs->stack[num].idx;
1154   memcpy (regs, fs->stack[num].regs, sizeof (regmatch_t) * nregs);
1155   re_node_set_free (eps_via_nodes);
1156   *eps_via_nodes = fs->stack[num].eps_via_nodes;
1157   return fs->stack[num].node;
1158 }
1159
1160 /* Set the positions where the subexpressions are starts/ends to registers
1161    PMATCH.
1162    Note: We assume that pmatch[0] is already set, and
1163    pmatch[i].rm_so == pmatch[i].rm_eo == -1 (i > 1).  */
1164
1165 static reg_errcode_t
1166 set_regs (preg, mctx, nmatch, pmatch, fl_backtrack)
1167      const regex_t *preg;
1168      const re_match_context_t *mctx;
1169      size_t nmatch;
1170      regmatch_t *pmatch;
1171      int fl_backtrack;
1172 {
1173   re_dfa_t *dfa = (re_dfa_t *)preg->buffer;
1174   int idx, cur_node, real_nmatch;
1175   re_node_set eps_via_nodes;
1176   struct re_fail_stack_t *fs;
1177   struct re_fail_stack_t fs_body = {0, 2, NULL};
1178 #ifdef DEBUG
1179   assert (nmatch > 1);
1180   assert (mctx->state_log != NULL);
1181 #endif
1182   if (fl_backtrack)
1183     {
1184       fs = &fs_body;
1185       fs->stack = re_malloc (struct re_fail_stack_ent_t, fs->alloc);
1186     }
1187   else
1188     fs = NULL;
1189   cur_node = dfa->init_node;
1190   real_nmatch = (nmatch <= preg->re_nsub) ? nmatch : preg->re_nsub + 1;
1191   re_node_set_init_empty (&eps_via_nodes);
1192   for (idx = pmatch[0].rm_so; idx <= pmatch[0].rm_eo ;)
1193     {
1194       update_regs (dfa, pmatch, cur_node, idx, real_nmatch);
1195       if (idx == pmatch[0].rm_eo && cur_node == mctx->last_node)
1196         {
1197           int reg_idx;
1198           if (fs)
1199             {
1200               for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
1201                 if (pmatch[reg_idx].rm_so > -1 && pmatch[reg_idx].rm_eo == -1)
1202                   break;
1203               if (reg_idx == nmatch)
1204                 return REG_NOERROR;
1205               cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1206                                          &eps_via_nodes);
1207             }
1208           else
1209             return REG_NOERROR;
1210         }
1211
1212       /* Proceed to next node.  */
1213       cur_node = proceed_next_node (preg, nmatch, pmatch, mctx, &idx, cur_node,
1214                                     &eps_via_nodes, fs);
1215
1216       if (BE (cur_node < 0, 0))
1217         {
1218           if (cur_node == -2)
1219             return REG_ESPACE;
1220           if (fs)
1221             cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1222                                        &eps_via_nodes);
1223           else
1224             return REG_NOMATCH;
1225         }
1226     }
1227   re_node_set_free (&eps_via_nodes);
1228   return REG_NOERROR;
1229 }
1230
1231 static void
1232 update_regs (dfa, pmatch, cur_node, cur_idx, nmatch)
1233      re_dfa_t *dfa;
1234      regmatch_t *pmatch;
1235      int cur_node, cur_idx, nmatch;
1236 {
1237   int type = dfa->nodes[cur_node].type;
1238   int reg_num;
1239   if (type != OP_OPEN_SUBEXP && type != OP_CLOSE_SUBEXP)
1240     return;
1241   reg_num = dfa->nodes[cur_node].opr.idx + 1;
1242   if (reg_num >= nmatch)
1243     return;
1244   if (type == OP_OPEN_SUBEXP)
1245     {
1246       /* We are at the first node of this sub expression.  */
1247       pmatch[reg_num].rm_so = cur_idx;
1248       pmatch[reg_num].rm_eo = -1;
1249     }
1250   else if (type == OP_CLOSE_SUBEXP)
1251     /* We are at the first node of this sub expression.  */
1252     pmatch[reg_num].rm_eo = cur_idx;
1253 }
1254
1255 #define NUMBER_OF_STATE 1
1256
1257 /* This function checks the STATE_LOG from the SCTX->last_str_idx to 0
1258    and sift the nodes in each states according to the following rules.
1259    Updated state_log will be wrote to STATE_LOG.
1260
1261    Rules: We throw away the Node `a' in the STATE_LOG[STR_IDX] if...
1262      1. When STR_IDX == MATCH_LAST(the last index in the state_log):
1263         If `a' isn't the LAST_NODE and `a' can't epsilon transit to
1264         the LAST_NODE, we throw away the node `a'.
1265      2. When 0 <= STR_IDX < MATCH_LAST and `a' accepts
1266         string `s' and transit to `b':
1267         i. If 'b' isn't in the STATE_LOG[STR_IDX+strlen('s')], we throw
1268            away the node `a'.
1269         ii. If 'b' is in the STATE_LOG[STR_IDX+strlen('s')] but 'b' is
1270             throwed away, we throw away the node `a'.
1271      3. When 0 <= STR_IDX < n and 'a' epsilon transit to 'b':
1272         i. If 'b' isn't in the STATE_LOG[STR_IDX], we throw away the
1273            node `a'.
1274         ii. If 'b' is in the STATE_LOG[STR_IDX] but 'b' is throwed away,
1275             we throw away the node `a'.  */
1276
1277 #define STATE_NODE_CONTAINS(state,node) \
1278   ((state) != NULL && re_node_set_contains (&(state)->nodes, node))
1279
1280 static reg_errcode_t
1281 sift_states_backward (preg, mctx, sctx)
1282      const regex_t *preg;
1283      re_match_context_t *mctx;
1284      re_sift_context_t *sctx;
1285 {
1286   reg_errcode_t err;
1287   re_dfa_t *dfa = (re_dfa_t *)preg->buffer;
1288   int null_cnt = 0;
1289   int str_idx = sctx->last_str_idx;
1290   re_node_set cur_dest;
1291   re_node_set *cur_src; /* Points the state_log[str_idx]->nodes  */
1292
1293 #ifdef DEBUG
1294   assert (mctx->state_log != NULL && mctx->state_log[str_idx] != NULL);
1295 #endif
1296   cur_src = &mctx->state_log[str_idx]->nodes;
1297
1298   /* Build sifted state_log[str_idx].  It has the nodes which can epsilon
1299      transit to the last_node and the last_node itself.  */
1300   err = re_node_set_init_1 (&cur_dest, sctx->last_node);
1301   if (BE (err != REG_NOERROR, 0))
1302     return err;
1303   err = update_cur_sifted_state (preg, mctx, sctx, str_idx, &cur_dest);
1304   if (BE (err != REG_NOERROR, 0))
1305     return err;
1306
1307   /* Then check each states in the state_log.  */
1308   while (str_idx > 0)
1309     {
1310       int i, ret;
1311       /* Update counters.  */
1312       null_cnt = (sctx->sifted_states[str_idx] == NULL) ? null_cnt + 1 : 0;
1313       if (null_cnt > mctx->max_mb_elem_len)
1314         {
1315           memset (sctx->sifted_states, '\0',
1316                   sizeof (re_dfastate_t *) * str_idx);
1317           return REG_NOERROR;
1318         }
1319       re_node_set_empty (&cur_dest);
1320       --str_idx;
1321       cur_src = ((mctx->state_log[str_idx] == NULL) ? &empty_set
1322                  : &mctx->state_log[str_idx]->nodes);
1323
1324       /* Then build the next sifted state.
1325          We build the next sifted state on `cur_dest', and update
1326          `sifted_states[str_idx]' with `cur_dest'.
1327          Note:
1328          `cur_dest' is the sifted state from `state_log[str_idx + 1]'.
1329          `cur_src' points the node_set of the old `state_log[str_idx]'.  */
1330       for (i = 0; i < cur_src->nelem; i++)
1331         {
1332           int prev_node = cur_src->elems[i];
1333           int entity = prev_node;
1334           int naccepted = 0;
1335           re_token_type_t type = dfa->nodes[prev_node].type;
1336
1337           if (IS_EPSILON_NODE(type))
1338             continue;
1339           if (type == OP_CONTEXT_NODE)
1340             {
1341               entity = dfa->nodes[prev_node].opr.ctx_info->entity;
1342               type = dfa->nodes[entity].type;
1343             }
1344 #ifdef RE_ENABLE_I18N
1345           /* If the node may accept `multi byte'.  */
1346           if (ACCEPT_MB_NODE (type))
1347             naccepted = sift_states_iter_mb (preg, mctx, sctx, entity, str_idx,
1348                                              sctx->last_str_idx);
1349
1350 #endif /* RE_ENABLE_I18N */
1351           /* We don't check backreferences here.
1352              See update_cur_sifted_state().  */
1353
1354           if (!naccepted
1355               && check_node_accept (preg, dfa->nodes + prev_node, mctx,
1356                                     str_idx)
1357               && STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + 1],
1358                                       dfa->nexts[prev_node]))
1359             naccepted = 1;
1360
1361           if (naccepted == 0)
1362             continue;
1363
1364           if (sctx->limits.nelem)
1365             {
1366               int to_idx = str_idx + naccepted;
1367               if (check_dst_limits (dfa, &sctx->limits, mctx,
1368                                     dfa->nexts[prev_node], to_idx,
1369                                     prev_node, str_idx))
1370                 continue;
1371             }
1372           ret = re_node_set_insert (&cur_dest, prev_node);
1373           if (BE (ret == -1, 0))
1374             return err;
1375         }
1376
1377       /* Add all the nodes which satisfy the following conditions:
1378          - It can epsilon transit to a node in CUR_DEST.
1379          - It is in CUR_SRC.
1380          And update state_log.  */
1381       err = update_cur_sifted_state (preg, mctx, sctx, str_idx, &cur_dest);
1382       if (BE (err != REG_NOERROR, 0))
1383         return err;
1384     }
1385
1386   re_node_set_free (&cur_dest);
1387   return REG_NOERROR;
1388 }
1389
1390 /* Helper functions.  */
1391
1392 static inline reg_errcode_t
1393 clean_state_log_if_need (mctx, next_state_log_idx)
1394     re_match_context_t *mctx;
1395     int next_state_log_idx;
1396 {
1397   int top = mctx->state_log_top;
1398
1399   if (next_state_log_idx >= mctx->input->bufs_len
1400       || (next_state_log_idx >= mctx->input->valid_len
1401           && mctx->input->valid_len < mctx->input->len))
1402     {
1403       reg_errcode_t err;
1404       err = extend_buffers (mctx);
1405       if (BE (err != REG_NOERROR, 0))
1406         return err;
1407     }
1408
1409   if (top < next_state_log_idx)
1410     {
1411       memset (mctx->state_log + top + 1, '\0',
1412               sizeof (re_dfastate_t *) * (next_state_log_idx - top));
1413       mctx->state_log_top = next_state_log_idx;
1414     }
1415   return REG_NOERROR;
1416 }
1417
1418 static reg_errcode_t merge_state_array (dfa, dst, src, num)
1419      re_dfa_t *dfa;
1420      re_dfastate_t **dst;
1421      re_dfastate_t **src;
1422      int num;
1423 {
1424   int st_idx;
1425   reg_errcode_t err;
1426   for (st_idx = 0; st_idx < num; ++st_idx)
1427     {
1428       if (dst[st_idx] == NULL)
1429         dst[st_idx] = src[st_idx];
1430       else if (src[st_idx] != NULL)
1431         {
1432           re_node_set merged_set;
1433           err = re_node_set_init_union (&merged_set, &dst[st_idx]->nodes,
1434                                         &src[st_idx]->nodes);
1435           if (BE (err != REG_NOERROR, 0))
1436             return err;
1437           dst[st_idx] = re_acquire_state (&err, dfa, &merged_set);
1438           if (BE (err != REG_NOERROR, 0))
1439             return err;
1440           re_node_set_free (&merged_set);
1441         }
1442     }
1443   return REG_NOERROR;
1444 }
1445
1446 static reg_errcode_t
1447 update_cur_sifted_state (preg, mctx, sctx, str_idx, dest_nodes)
1448      const regex_t *preg;
1449      re_match_context_t *mctx;
1450      re_sift_context_t *sctx;
1451      int str_idx;
1452      re_node_set *dest_nodes;
1453 {
1454   reg_errcode_t err;
1455   re_dfa_t *dfa = (re_dfa_t *)preg->buffer;
1456   const re_node_set *candidates;
1457   candidates = ((mctx->state_log[str_idx] == NULL) ? &empty_set
1458                 : &mctx->state_log[str_idx]->nodes);
1459
1460   /* At first, add the nodes which can epsilon transit to a node in
1461      DEST_NODE.  */
1462   err = add_epsilon_src_nodes (dfa, dest_nodes, candidates);
1463   if (BE (err != REG_NOERROR, 0))
1464     return err;
1465
1466   /* Then, check the limitations in the current sift_context.  */
1467   if (sctx->limits.nelem)
1468     {
1469       err = check_subexp_limits (dfa, dest_nodes, candidates, &sctx->limits,
1470                                  mctx->bkref_ents, str_idx);
1471       if (BE (err != REG_NOERROR, 0))
1472         return err;
1473     }
1474
1475   /* Update state_log.  */
1476   sctx->sifted_states[str_idx] = re_acquire_state (&err, dfa, dest_nodes);
1477   if (BE (sctx->sifted_states[str_idx] == NULL && err != REG_NOERROR, 0))
1478     return err;
1479
1480   /* If we are searching for the subexpression candidates.
1481      Note that we were from transit_state_bkref_loop() in this case.  */
1482   if (sctx->check_subexp)
1483     {
1484       err = search_subexp (preg, mctx, sctx, str_idx, dest_nodes);
1485       if (BE (err != REG_NOERROR, 0))
1486         return err;
1487     }
1488
1489   if ((mctx->state_log[str_idx] != NULL
1490        && mctx->state_log[str_idx]->has_backref))
1491     {
1492       err = sift_states_bkref (preg, mctx, sctx, str_idx, dest_nodes);
1493       if (BE (err != REG_NOERROR, 0))
1494         return err;
1495     }
1496   return REG_NOERROR;
1497 }
1498
1499 static reg_errcode_t
1500 add_epsilon_src_nodes (dfa, dest_nodes, candidates)
1501      re_dfa_t *dfa;
1502      re_node_set *dest_nodes;
1503      const re_node_set *candidates;
1504 {
1505   reg_errcode_t err;
1506   int src_idx;
1507   re_node_set src_copy;
1508
1509   err = re_node_set_init_copy (&src_copy, dest_nodes);
1510   if (BE (err != REG_NOERROR, 0))
1511     return err;
1512   for (src_idx = 0; src_idx < src_copy.nelem; ++src_idx)
1513     {
1514       err = re_node_set_add_intersect (dest_nodes, candidates,
1515                                        dfa->inveclosures
1516                                        + src_copy.elems[src_idx]);
1517       if (BE (err != REG_NOERROR, 0))
1518         return err;
1519     }
1520   re_node_set_free (&src_copy);
1521   return REG_NOERROR;
1522 }
1523
1524 static reg_errcode_t
1525 sub_epsilon_src_nodes (dfa, node, dest_nodes, candidates)
1526      re_dfa_t *dfa;
1527      int node;
1528      re_node_set *dest_nodes;
1529      const re_node_set *candidates;
1530 {
1531     int ecl_idx;
1532     reg_errcode_t err;
1533     re_node_set *inv_eclosure = dfa->inveclosures + node;
1534     re_node_set except_nodes;
1535     re_node_set_init_empty (&except_nodes);
1536     for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1537       {
1538         int cur_node = inv_eclosure->elems[ecl_idx];
1539         if (cur_node == node)
1540           continue;
1541         if (dfa->edests[cur_node].nelem)
1542           {
1543             int edst1 = dfa->edests[cur_node].elems[0];
1544             int edst2 = ((dfa->edests[cur_node].nelem > 1)
1545                          ? dfa->edests[cur_node].elems[1] : -1);
1546             if ((!re_node_set_contains (inv_eclosure, edst1)
1547                  && re_node_set_contains (dest_nodes, edst1))
1548                 || (edst2 > 0
1549                     && !re_node_set_contains (inv_eclosure, edst2)
1550                     && re_node_set_contains (dest_nodes, edst2)))
1551               {
1552                 err = re_node_set_add_intersect (&except_nodes, candidates,
1553                                                  dfa->inveclosures + cur_node);
1554                 if (BE (err != REG_NOERROR, 0))
1555                   return err;
1556               }
1557           }
1558       }
1559     for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1560       {
1561         int cur_node = inv_eclosure->elems[ecl_idx];
1562         if (!re_node_set_contains (&except_nodes, cur_node))
1563           {
1564             int idx = re_node_set_contains (dest_nodes, cur_node) - 1;
1565             re_node_set_remove_at (dest_nodes, idx);
1566           }
1567       }
1568     re_node_set_free (&except_nodes);
1569     return REG_NOERROR;
1570 }
1571
1572 static int
1573 check_dst_limits (dfa, limits, mctx, dst_node, dst_idx, src_node, src_idx)
1574      re_dfa_t *dfa;
1575      re_node_set *limits;
1576      re_match_context_t *mctx;
1577      int dst_node, dst_idx, src_node, src_idx;
1578 {
1579   int lim_idx, src_pos, dst_pos;
1580
1581   for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
1582     {
1583       int bkref, subexp_idx/*, node_idx, cls_node*/;
1584       struct re_backref_cache_entry *ent;
1585       ent = mctx->bkref_ents + limits->elems[lim_idx];
1586       bkref = (dfa->nodes[ent->node].type == OP_CONTEXT_NODE
1587                ? dfa->nodes[ent->node].opr.ctx_info->entity : ent->node);
1588       subexp_idx = dfa->nodes[bkref].opr.idx - 1;
1589
1590       dst_pos = check_dst_limits_calc_pos (dfa, mctx, limits->elems[lim_idx],
1591                                            dfa->eclosures + dst_node,
1592                                            subexp_idx, dst_node, dst_idx);
1593       src_pos = check_dst_limits_calc_pos (dfa, mctx, limits->elems[lim_idx],
1594                                            dfa->eclosures + src_node,
1595                                            subexp_idx, src_node, src_idx);
1596
1597       /* In case of:
1598          <src> <dst> ( <subexp> )
1599          ( <subexp> ) <src> <dst>
1600          ( <subexp1> <src> <subexp2> <dst> <subexp3> )  */
1601       if (src_pos == dst_pos)
1602         continue; /* This is unrelated limitation.  */
1603       else
1604         return 1;
1605     }
1606   return 0;
1607 }
1608
1609 static int
1610 check_dst_limits_calc_pos (dfa, mctx, limit, eclosures, subexp_idx, node,
1611                            str_idx)
1612      re_dfa_t *dfa;
1613      re_match_context_t *mctx;
1614      re_node_set *eclosures;
1615      int limit, subexp_idx, node, str_idx;
1616 {
1617   struct re_backref_cache_entry *lim = mctx->bkref_ents + limit;
1618   int pos = (str_idx < lim->subexp_from ? -1
1619              : (lim->subexp_to < str_idx ? 1 : 0));
1620   if (pos == 0
1621       && (str_idx == lim->subexp_from || str_idx == lim->subexp_to))
1622     {
1623       int node_idx;
1624       for (node_idx = 0; node_idx < eclosures->nelem; ++node_idx)
1625         {
1626           int node = eclosures->elems[node_idx];
1627           int entity = node;
1628           re_token_type_t type= dfa->nodes[node].type;
1629           if (type == OP_CONTEXT_NODE)
1630             {
1631               entity = dfa->nodes[node].opr.ctx_info->entity;
1632               type = dfa->nodes[entity].type;
1633             }
1634           if (type == OP_BACK_REF)
1635             {
1636               int bi;
1637               for (bi = 0; bi < mctx->nbkref_ents; ++bi)
1638                 {
1639                   struct re_backref_cache_entry *ent = mctx->bkref_ents + bi;
1640                   if (ent->node == node && ent->subexp_from == ent->subexp_to
1641                       && ent->str_idx == str_idx)
1642                     {
1643                       int cpos, dst;
1644                       dst = dfa->nexts[node];
1645                       cpos = check_dst_limits_calc_pos (dfa, mctx, limit,
1646                                                         dfa->eclosures + dst,
1647                                                         subexp_idx, dst,
1648                                                         str_idx);
1649                       if ((str_idx == lim->subexp_from && cpos == -1)
1650                           || (str_idx == lim->subexp_to && cpos == 0))
1651                         return cpos;
1652                     }
1653                 }
1654             }
1655           if (type == OP_OPEN_SUBEXP && subexp_idx == dfa->nodes[node].opr.idx
1656               && str_idx == lim->subexp_from)
1657             {
1658               pos = -1;
1659               break;
1660             }
1661           if (type == OP_CLOSE_SUBEXP && subexp_idx == dfa->nodes[node].opr.idx
1662               && str_idx == lim->subexp_to)
1663             break;
1664         }
1665       if (node_idx == eclosures->nelem && str_idx == lim->subexp_to)
1666         pos = 1;
1667     }
1668   return pos;
1669 }
1670
1671 /* Check the limitations of sub expressions LIMITS, and remove the nodes
1672    which are against limitations from DEST_NODES. */
1673
1674 static reg_errcode_t
1675 check_subexp_limits (dfa, dest_nodes, candidates, limits, bkref_ents, str_idx)
1676      re_dfa_t *dfa;
1677      re_node_set *dest_nodes;
1678      const re_node_set *candidates;
1679      re_node_set *limits;
1680      struct re_backref_cache_entry *bkref_ents;
1681      int str_idx;
1682 {
1683   reg_errcode_t err;
1684   int node_idx, lim_idx;
1685
1686   for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
1687     {
1688       int bkref, subexp_idx;
1689       struct re_backref_cache_entry *ent;
1690       ent = bkref_ents + limits->elems[lim_idx];
1691
1692       if (str_idx <= ent->subexp_from || ent->str_idx < str_idx)
1693         continue; /* This is unrelated limitation.  */
1694
1695       bkref = (dfa->nodes[ent->node].type == OP_CONTEXT_NODE
1696                ? dfa->nodes[ent->node].opr.ctx_info->entity : ent->node);
1697       subexp_idx = dfa->nodes[bkref].opr.idx - 1;
1698
1699       if (ent->subexp_to == str_idx)
1700         {
1701           int ops_node = -1;
1702           int cls_node = -1;
1703           for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
1704             {
1705               int node = dest_nodes->elems[node_idx];
1706               re_token_type_t type= dfa->nodes[node].type;
1707               if (type == OP_OPEN_SUBEXP
1708                   && subexp_idx == dfa->nodes[node].opr.idx)
1709                 ops_node = node;
1710               else if (type == OP_CLOSE_SUBEXP
1711                        && subexp_idx == dfa->nodes[node].opr.idx)
1712                 cls_node = node;
1713             }
1714
1715           /* Check the limitation of the open subexpression.  */
1716           /* Note that (ent->subexp_to = str_idx != ent->subexp_from).  */
1717           if (ops_node >= 0)
1718             {
1719               err = sub_epsilon_src_nodes(dfa, ops_node, dest_nodes,
1720                                           candidates);
1721               if (BE (err != REG_NOERROR, 0))
1722                 return err;
1723             }
1724           /* Check the limitation of the close subexpression.  */
1725           for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
1726             {
1727               int node = dest_nodes->elems[node_idx];
1728               if (!re_node_set_contains (dfa->inveclosures + node, cls_node)
1729                   && !re_node_set_contains (dfa->eclosures + node, cls_node))
1730                 {
1731                   /* It is against this limitation.
1732                      Remove it form the current sifted state.  */
1733                   err = sub_epsilon_src_nodes(dfa, node, dest_nodes,
1734                                               candidates);
1735                   if (BE (err != REG_NOERROR, 0))
1736                     return err;
1737                   --node_idx;
1738                 }
1739             }
1740         }
1741       else /* (ent->subexp_to != str_idx)  */
1742         {
1743           for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
1744             {
1745               int node = dest_nodes->elems[node_idx];
1746               re_token_type_t type= dfa->nodes[node].type;
1747               if (type == OP_CLOSE_SUBEXP || type == OP_OPEN_SUBEXP)
1748                 {
1749                   if (subexp_idx != dfa->nodes[node].opr.idx)
1750                     continue;
1751                   if ((type == OP_CLOSE_SUBEXP && ent->subexp_to != str_idx)
1752                       || (type == OP_OPEN_SUBEXP))
1753                     {
1754                       /* It is against this limitation.
1755                          Remove it form the current sifted state.  */
1756                       err = sub_epsilon_src_nodes(dfa, node, dest_nodes,
1757                                                   candidates);
1758                       if (BE (err != REG_NOERROR, 0))
1759                         return err;
1760                     }
1761                 }
1762             }
1763         }
1764     }
1765   return REG_NOERROR;
1766 }
1767
1768 /* Search for the top (in case of sctx->check_subexp < 0) or the
1769    bottom (in case of sctx->check_subexp > 0) of the subexpressions
1770    which the backreference sctx->cur_bkref can match.  */
1771
1772 static reg_errcode_t
1773 search_subexp (preg, mctx, sctx, str_idx, dest_nodes)
1774      const regex_t *preg;
1775      re_match_context_t *mctx;
1776      re_sift_context_t *sctx;
1777      int str_idx;
1778      re_node_set *dest_nodes;
1779 {
1780   reg_errcode_t err;
1781   re_dfa_t *dfa = (re_dfa_t *)preg->buffer;
1782   re_sift_context_t local_sctx;
1783   int node_idx, node=0; /* gnupg */
1784   const re_node_set *candidates;
1785   re_dfastate_t **lim_states = NULL;
1786   candidates = ((mctx->state_log[str_idx] == NULL) ? &empty_set
1787                 : &mctx->state_log[str_idx]->nodes);
1788   local_sctx.sifted_states = NULL; /* Mark that it hasn't been initialized.  */
1789
1790   for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
1791     {
1792       re_token_type_t type;
1793       int entity;
1794       node = dest_nodes->elems[node_idx];
1795       type = dfa->nodes[node].type;
1796       entity = (type != OP_CONTEXT_NODE ? node
1797                 : dfa->nodes[node].opr.ctx_info->entity);
1798       type = (type != OP_CONTEXT_NODE ? type : dfa->nodes[entity].type);
1799
1800       if (type == OP_CLOSE_SUBEXP
1801           && sctx->check_subexp == dfa->nodes[node].opr.idx + 1)
1802         {
1803           re_dfastate_t *cur_state;
1804           /* Found the bottom of the subexpression, then search for the
1805              top of it.  */
1806           if (local_sctx.sifted_states == NULL)
1807             {
1808               /* It hasn't been initialized yet, initialize it now.  */
1809               local_sctx = *sctx;
1810               err = re_node_set_init_copy (&local_sctx.limits, &sctx->limits);
1811               if (BE (err != REG_NOERROR, 0))
1812                 return err;
1813             }
1814           local_sctx.check_subexp = -sctx->check_subexp;
1815           local_sctx.limited_states = sctx->limited_states;
1816           local_sctx.last_node = node;
1817           local_sctx.last_str_idx = local_sctx.cls_subexp_idx = str_idx;
1818           cur_state = local_sctx.sifted_states[str_idx];
1819           err = sift_states_backward (preg, mctx, &local_sctx);
1820           local_sctx.sifted_states[str_idx] = cur_state;
1821           if (BE (err != REG_NOERROR, 0))
1822             return err;
1823           /* There must not 2 same node in a node set.  */
1824           break;
1825         }
1826       else if (type == OP_OPEN_SUBEXP
1827                && -sctx->check_subexp == dfa->nodes[node].opr.idx + 1)
1828         {
1829           /* Found the top of the subexpression, check that the
1830              backreference can match the input string.  */
1831           char *buf;
1832           int dest_str_idx;
1833           int bkref_str_idx = re_string_cur_idx (mctx->input);
1834           int subexp_len = sctx->cls_subexp_idx - str_idx;
1835           if (subexp_len < 0 || bkref_str_idx + subexp_len > mctx->input->len)
1836             break;
1837
1838           if (bkref_str_idx + subexp_len > mctx->input->valid_len
1839               && mctx->input->valid_len < mctx->input->len)
1840             {
1841               reg_errcode_t err;
1842               err = extend_buffers (mctx);
1843               if (BE (err != REG_NOERROR, 0))
1844                 return err;
1845             }
1846           buf = (char *) re_string_get_buffer (mctx->input);
1847           if (strncmp (buf + str_idx, buf + bkref_str_idx, subexp_len) != 0)
1848             break;
1849
1850           if (sctx->limits.nelem && str_idx > 0)
1851             {
1852               re_dfastate_t *cur_state = sctx->sifted_states[str_idx];
1853               if (lim_states == NULL)
1854                 {
1855                   lim_states = re_malloc (re_dfastate_t *, str_idx + 1);
1856                 }
1857               if (local_sctx.sifted_states == NULL)
1858                 {
1859                   /* It hasn't been initialized yet, initialize it now.  */
1860                   local_sctx = *sctx;
1861                   if (BE (lim_states == NULL, 0))
1862                     return REG_ESPACE;
1863                   err = re_node_set_init_copy (&local_sctx.limits,
1864                                                &sctx->limits);
1865                   if (BE (err != REG_NOERROR, 0))
1866                     return err;
1867                 }
1868               local_sctx.check_subexp = 0;
1869               local_sctx.last_node = node;
1870               local_sctx.last_str_idx = str_idx;
1871               local_sctx.limited_states = lim_states;
1872               memset (lim_states, '\0',
1873                       sizeof (re_dfastate_t*) * (str_idx + 1));
1874               err = sift_states_backward (preg, mctx, &local_sctx);
1875               if (BE (err != REG_NOERROR, 0))
1876                 return err;
1877               if (local_sctx.sifted_states[0] == NULL
1878                   && local_sctx.limited_states[0] == NULL)
1879                 {
1880                   sctx->sifted_states[str_idx] = cur_state;
1881                   break;
1882                 }
1883               sctx->sifted_states[str_idx] = cur_state;
1884             }
1885           /* Successfully matched, add a new cache entry.  */
1886           dest_str_idx = bkref_str_idx + subexp_len;
1887           err = match_ctx_add_entry (mctx, sctx->cur_bkref, bkref_str_idx,
1888                                      str_idx, sctx->cls_subexp_idx);
1889           if (BE (err != REG_NOERROR, 0))
1890             return err;
1891           err = clean_state_log_if_need (mctx, dest_str_idx);
1892           if (BE (err != REG_NOERROR, 0))
1893             return err;
1894           break;
1895         }
1896     }
1897
1898   /* Remove the top/bottom of the sub expression we processed.  */
1899   if (node_idx < dest_nodes->nelem)
1900     {
1901       err = sub_epsilon_src_nodes(dfa, node, dest_nodes, candidates);
1902       if (BE (err != REG_NOERROR, 0))
1903         return err;
1904       /* Update state_log.  */
1905       sctx->sifted_states[str_idx] = re_acquire_state (&err, dfa, dest_nodes);
1906       if (BE (err != REG_NOERROR, 0))
1907         return err;
1908     }
1909
1910   if (local_sctx.sifted_states != NULL)
1911     re_node_set_free (&local_sctx.limits);
1912   if (lim_states != NULL)
1913     re_free (lim_states);
1914   return REG_NOERROR;
1915 }
1916
1917 static reg_errcode_t
1918 sift_states_bkref (preg, mctx, sctx, str_idx, dest_nodes)
1919      const regex_t *preg;
1920      re_match_context_t *mctx;
1921      re_sift_context_t *sctx;
1922      int str_idx;
1923      re_node_set *dest_nodes;
1924 {
1925   reg_errcode_t err;
1926   re_dfa_t *dfa = (re_dfa_t *)preg->buffer;
1927   int node_idx, node;
1928   re_sift_context_t local_sctx;
1929   const re_node_set *candidates;
1930   candidates = ((mctx->state_log[str_idx] == NULL) ? &empty_set
1931                 : &mctx->state_log[str_idx]->nodes);
1932   local_sctx.sifted_states = NULL; /* Mark that it hasn't been initialized.  */
1933
1934   for (node_idx = 0; node_idx < candidates->nelem; ++node_idx)
1935     {
1936       int entity;
1937       int cur_bkref_idx = re_string_cur_idx (mctx->input);
1938       re_token_type_t type;
1939       node = candidates->elems[node_idx];
1940       type = dfa->nodes[node].type;
1941       entity = (type != OP_CONTEXT_NODE ? node
1942                 : dfa->nodes[node].opr.ctx_info->entity);
1943       type = (type != OP_CONTEXT_NODE ? type : dfa->nodes[entity].type);
1944       if (node == sctx->cur_bkref && str_idx == cur_bkref_idx)
1945         continue;
1946       /* Avoid infinite loop for the REs like "()\1+".  */
1947       if (node == sctx->last_node && str_idx == sctx->last_str_idx)
1948         continue;
1949       if (type == OP_BACK_REF)
1950         {
1951           int enabled_idx;
1952           for (enabled_idx = 0; enabled_idx < mctx->nbkref_ents; ++enabled_idx)
1953             {
1954               int disabled_idx, subexp_len, to_idx;
1955               struct re_backref_cache_entry *entry;
1956               entry = mctx->bkref_ents + enabled_idx;
1957               subexp_len = entry->subexp_to - entry->subexp_from;
1958               to_idx = str_idx + subexp_len;
1959
1960               if (entry->node != node || entry->str_idx != str_idx
1961                   || to_idx > sctx->last_str_idx
1962                   || sctx->sifted_states[to_idx] == NULL)
1963                 continue;
1964               if (!STATE_NODE_CONTAINS (sctx->sifted_states[to_idx],
1965                                         dfa->nexts[node]))
1966                 {
1967                   int dst_idx;
1968                   re_node_set *dsts = &sctx->sifted_states[to_idx]->nodes;
1969                   for (dst_idx = 0; dst_idx < dsts->nelem; ++dst_idx)
1970                     {
1971                       int dst_node = dsts->elems[dst_idx];
1972                       if (dfa->nodes[dst_node].type == OP_CONTEXT_NODE
1973                           && (dfa->nodes[dst_node].opr.ctx_info->entity
1974                               == dfa->nexts[node]))
1975                         break;
1976                     }
1977                   if (dst_idx == dsts->nelem)
1978                     continue;
1979                 }
1980
1981               if (check_dst_limits (dfa, &sctx->limits, mctx, node,
1982                                     str_idx, dfa->nexts[node], to_idx))
1983                 continue;
1984               if (sctx->check_subexp == dfa->nodes[entity].opr.idx)
1985                 {
1986                   char *buf;
1987                   buf = (char *) re_string_get_buffer (mctx->input);
1988                   if (strncmp (buf + entry->subexp_from,
1989                                buf + cur_bkref_idx, subexp_len) != 0)
1990                     continue;
1991                   err = match_ctx_add_entry (mctx, sctx->cur_bkref,
1992                                              cur_bkref_idx, entry->subexp_from,
1993                                              entry->subexp_to);
1994                   if (BE (err != REG_NOERROR, 0))
1995                     return err;
1996                   err = clean_state_log_if_need (mctx, cur_bkref_idx
1997                                                  + subexp_len);
1998                   if (BE (err != REG_NOERROR, 0))
1999                     return err;
2000                 }
2001               else
2002                 {
2003                   re_dfastate_t *cur_state;
2004                   entry->flag = 0;
2005                   for (disabled_idx = enabled_idx + 1;
2006                        disabled_idx < mctx->nbkref_ents; ++disabled_idx)
2007                     {
2008                       struct re_backref_cache_entry *entry2;
2009                       entry2 = mctx->bkref_ents + disabled_idx;
2010                       if (entry2->node != node || entry2->str_idx != str_idx)
2011                         continue;
2012                       entry2->flag = 1;
2013                     }
2014
2015                   if (local_sctx.sifted_states == NULL)
2016                     {
2017                       local_sctx = *sctx;
2018                       err = re_node_set_init_copy (&local_sctx.limits,
2019                                                    &sctx->limits);
2020                       if (BE (err != REG_NOERROR, 0))
2021                         return err;
2022                     }
2023                   local_sctx.last_node = node;
2024                   local_sctx.last_str_idx = str_idx;
2025                   err = re_node_set_insert (&local_sctx.limits, enabled_idx);
2026                   if (BE (err < 0, 0))
2027                     return REG_ESPACE;
2028                   cur_state = local_sctx.sifted_states[str_idx];
2029                   err = sift_states_backward (preg, mctx, &local_sctx);
2030                   if (BE (err != REG_NOERROR, 0))
2031                     return err;
2032                   if (sctx->limited_states != NULL)
2033                     {
2034                       err = merge_state_array (dfa, sctx->limited_states,
2035                                                local_sctx.sifted_states,
2036                                                str_idx + 1);
2037                       if (BE (err != REG_NOERROR, 0))
2038                         return err;
2039                     }
2040                   local_sctx.sifted_states[str_idx] = cur_state;
2041                   re_node_set_remove_at (&local_sctx.limits,
2042                                          local_sctx.limits.nelem - 1);
2043                   entry->flag = 1;
2044                 }
2045             }
2046           for (enabled_idx = 0; enabled_idx < mctx->nbkref_ents; ++enabled_idx)
2047             {
2048               struct re_backref_cache_entry *entry;
2049               entry = mctx->bkref_ents + enabled_idx;
2050               if (entry->node == node && entry->str_idx == str_idx)
2051                 entry->flag = 0;
2052             }
2053         }
2054     }
2055   if (local_sctx.sifted_states != NULL)
2056     {
2057       re_node_set_free (&local_sctx.limits);
2058     }
2059
2060   return REG_NOERROR;
2061 }
2062
2063
2064 #ifdef RE_ENABLE_I18N
2065 static int
2066 sift_states_iter_mb (preg, mctx, sctx, node_idx, str_idx, max_str_idx)
2067     const regex_t *preg;
2068     const re_match_context_t *mctx;
2069     re_sift_context_t *sctx;
2070     int node_idx, str_idx, max_str_idx;
2071 {
2072   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
2073   int naccepted;
2074   /* Check the node can accept `multi byte'.  */
2075   naccepted = check_node_accept_bytes (preg, node_idx, mctx->input, str_idx);
2076   if (naccepted > 0 && str_idx + naccepted <= max_str_idx &&
2077       !STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + naccepted],
2078                             dfa->nexts[node_idx]))
2079     /* The node can't accept the `multi byte', or the
2080        destination was already throwed away, then the node
2081        could't accept the current input `multi byte'.   */
2082     naccepted = 0;
2083   /* Otherwise, it is sure that the node could accept
2084      `naccepted' bytes input.  */
2085   return naccepted;
2086 }
2087 #endif /* RE_ENABLE_I18N */
2088
2089 \f
2090 /* Functions for state transition.  */
2091
2092 /* Return the next state to which the current state STATE will transit by
2093    accepting the current input byte, and update STATE_LOG if necessary.
2094    If STATE can accept a multibyte char/collating element/back reference
2095    update the destination of STATE_LOG.  */
2096
2097 static re_dfastate_t *
2098 transit_state (err, preg, mctx, state, fl_search)
2099      reg_errcode_t *err;
2100      const regex_t *preg;
2101      re_match_context_t *mctx;
2102      re_dfastate_t *state;
2103      int fl_search;
2104 {
2105   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
2106   re_dfastate_t **trtable, *next_state;
2107   unsigned char ch;
2108
2109   if (re_string_cur_idx (mctx->input) + 1 >= mctx->input->bufs_len
2110       || (re_string_cur_idx (mctx->input) + 1 >= mctx->input->valid_len
2111           && mctx->input->valid_len < mctx->input->len))
2112     {
2113       *err = extend_buffers (mctx);
2114       if (BE (*err != REG_NOERROR, 0))
2115         return NULL;
2116     }
2117
2118   *err = REG_NOERROR;
2119   if (state == NULL)
2120     {
2121       next_state = state;
2122       re_string_skip_bytes (mctx->input, 1);
2123     }
2124   else
2125     {
2126 #ifdef RE_ENABLE_I18N
2127       /* If the current state can accept multibyte.  */
2128       if (state->accept_mb)
2129         {
2130           *err = transit_state_mb (preg, state, mctx);
2131           if (BE (*err != REG_NOERROR, 0))
2132             return NULL;
2133         }
2134 #endif /* RE_ENABLE_I18N */
2135
2136       /* Then decide the next state with the single byte.  */
2137       if (1)
2138         {
2139           /* Use transition table  */
2140           ch = re_string_fetch_byte (mctx->input);
2141           trtable = fl_search ? state->trtable_search : state->trtable;
2142           if (trtable == NULL)
2143             {
2144               trtable = build_trtable (preg, state, fl_search);
2145               if (fl_search)
2146                 state->trtable_search = trtable;
2147               else
2148                 state->trtable = trtable;
2149             }
2150           next_state = trtable[ch];
2151         }
2152       else
2153         {
2154           /* don't use transition table  */
2155           next_state = transit_state_sb (err, preg, state, fl_search, mctx);
2156           if (BE (next_state == NULL && err != REG_NOERROR, 0))
2157             return NULL;
2158         }
2159     }
2160
2161   /* Update the state_log if we need.  */
2162   if (mctx->state_log != NULL)
2163     {
2164       int cur_idx = re_string_cur_idx (mctx->input);
2165       if (cur_idx > mctx->state_log_top)
2166         {
2167           mctx->state_log[cur_idx] = next_state;
2168           mctx->state_log_top = cur_idx;
2169         }
2170       else if (mctx->state_log[cur_idx] == 0)
2171         {
2172           mctx->state_log[cur_idx] = next_state;
2173         }
2174       else
2175         {
2176           re_dfastate_t *pstate;
2177           unsigned int context;
2178           re_node_set next_nodes, *log_nodes, *table_nodes = NULL;
2179           /* If (state_log[cur_idx] != 0), it implies that cur_idx is
2180              the destination of a multibyte char/collating element/
2181              back reference.  Then the next state is the union set of
2182              these destinations and the results of the transition table.  */
2183           pstate = mctx->state_log[cur_idx];
2184           log_nodes = pstate->entrance_nodes;
2185           if (next_state != NULL)
2186             {
2187               table_nodes = next_state->entrance_nodes;
2188               *err = re_node_set_init_union (&next_nodes, table_nodes,
2189                                              log_nodes);
2190               if (BE (*err != REG_NOERROR, 0))
2191                 return NULL;
2192             }
2193           else
2194             next_nodes = *log_nodes;
2195           /* Note: We already add the nodes of the initial state,
2196                    then we don't need to add them here.  */
2197
2198           context = re_string_context_at (mctx->input,
2199                                           re_string_cur_idx (mctx->input) - 1,
2200                                           mctx->eflags, preg->newline_anchor);
2201           next_state = mctx->state_log[cur_idx]
2202             = re_acquire_state_context (err, dfa, &next_nodes, context);
2203           /* We don't need to check errors here, since the return value of
2204              this function is next_state and ERR is already set.  */
2205
2206           if (table_nodes != NULL)
2207             re_node_set_free (&next_nodes);
2208         }
2209       /* If the next state has back references.  */
2210       if (next_state != NULL && next_state->has_backref)
2211         {
2212           *err = transit_state_bkref (preg, next_state, mctx);
2213           if (BE (*err != REG_NOERROR, 0))
2214             return NULL;
2215           next_state = mctx->state_log[cur_idx];
2216         }
2217     }
2218   return next_state;
2219 }
2220
2221 /* Helper functions for transit_state.  */
2222
2223 /* Return the next state to which the current state STATE will transit by
2224    accepting the current input byte.  */
2225
2226 static re_dfastate_t *
2227 transit_state_sb (err, preg, state, fl_search, mctx)
2228      reg_errcode_t *err;
2229      const regex_t *preg;
2230      re_dfastate_t *state;
2231      int fl_search;
2232      re_match_context_t *mctx;
2233 {
2234   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
2235   re_node_set next_nodes;
2236   re_dfastate_t *next_state;
2237   int node_cnt, cur_str_idx = re_string_cur_idx (mctx->input);
2238   unsigned int context;
2239
2240   *err = re_node_set_alloc (&next_nodes, state->nodes.nelem + 1);
2241   if (BE (*err != REG_NOERROR, 0))
2242     return NULL;
2243   for (node_cnt = 0; node_cnt < state->nodes.nelem; ++node_cnt)
2244     {
2245       int cur_node = state->nodes.elems[node_cnt];
2246       if (check_node_accept (preg, dfa->nodes + cur_node, mctx, cur_str_idx))
2247         {
2248           *err = re_node_set_merge (&next_nodes,
2249                                     dfa->eclosures + dfa->nexts[cur_node]);
2250           if (BE (*err != REG_NOERROR, 0))
2251             return NULL;
2252         }
2253     }
2254   if (fl_search)
2255     {
2256 #ifdef RE_ENABLE_I18N
2257       int not_initial = 0;
2258       if (MB_CUR_MAX > 1)
2259         for (node_cnt = 0; node_cnt < next_nodes.nelem; ++node_cnt)
2260           if (dfa->nodes[next_nodes.elems[node_cnt]].type == CHARACTER)
2261             {
2262               not_initial = dfa->nodes[next_nodes.elems[node_cnt]].mb_partial;
2263               break;
2264             }
2265       if (!not_initial)
2266 #endif
2267         {
2268           *err = re_node_set_merge (&next_nodes,
2269                                     dfa->init_state->entrance_nodes);
2270           if (BE (*err != REG_NOERROR, 0))
2271             return NULL;
2272         }
2273     }
2274   context = re_string_context_at (mctx->input, cur_str_idx, mctx->eflags,
2275                                   preg->newline_anchor);
2276   next_state = re_acquire_state_context (err, dfa, &next_nodes, context);
2277   /* We don't need to check errors here, since the return value of
2278      this function is next_state and ERR is already set.  */
2279
2280   re_node_set_free (&next_nodes);
2281   re_string_skip_bytes (mctx->input, 1);
2282   return next_state;
2283 }
2284
2285 #ifdef RE_ENABLE_I18N
2286 static reg_errcode_t
2287 transit_state_mb (preg, pstate, mctx)
2288     const regex_t *preg;
2289     re_dfastate_t *pstate;
2290     re_match_context_t *mctx;
2291 {
2292   reg_errcode_t err;
2293   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
2294   int i;
2295
2296   for (i = 0; i < pstate->nodes.nelem; ++i)
2297     {
2298       re_node_set dest_nodes, *new_nodes;
2299       int cur_node_idx = pstate->nodes.elems[i];
2300       int naccepted = 0, dest_idx;
2301       unsigned int context;
2302       re_dfastate_t *dest_state;
2303
2304       if (dfa->nodes[cur_node_idx].type == OP_CONTEXT_NODE)
2305         {
2306           context = re_string_context_at (mctx->input,
2307                                           re_string_cur_idx (mctx->input),
2308                                           mctx->eflags, preg->newline_anchor);
2309           if (NOT_SATISFY_NEXT_CONSTRAINT (dfa->nodes[cur_node_idx].constraint,
2310                                         context))
2311             continue;
2312           cur_node_idx = dfa->nodes[cur_node_idx].opr.ctx_info->entity;
2313         }
2314
2315       /* How many bytes the node can accepts?  */
2316       if (ACCEPT_MB_NODE (dfa->nodes[cur_node_idx].type))
2317         naccepted = check_node_accept_bytes (preg, cur_node_idx, mctx->input,
2318                                              re_string_cur_idx (mctx->input));
2319       if (naccepted == 0)
2320         continue;
2321
2322       /* The node can accepts `naccepted' bytes.  */
2323       dest_idx = re_string_cur_idx (mctx->input) + naccepted;
2324       mctx->max_mb_elem_len = ((mctx->max_mb_elem_len < naccepted) ? naccepted
2325                                : mctx->max_mb_elem_len);
2326       err = clean_state_log_if_need (mctx, dest_idx);
2327       if (BE (err != REG_NOERROR, 0))
2328         return err;
2329 #ifdef DEBUG
2330       assert (dfa->nexts[cur_node_idx] != -1);
2331 #endif
2332       /* `cur_node_idx' may point the entity of the OP_CONTEXT_NODE,
2333          then we use pstate->nodes.elems[i] instead.  */
2334       new_nodes = dfa->eclosures + dfa->nexts[pstate->nodes.elems[i]];
2335
2336       dest_state = mctx->state_log[dest_idx];
2337       if (dest_state == NULL)
2338         dest_nodes = *new_nodes;
2339       else
2340         {
2341           err = re_node_set_init_union (&dest_nodes,
2342                                         dest_state->entrance_nodes, new_nodes);
2343           if (BE (err != REG_NOERROR, 0))
2344             return err;
2345         }
2346       context = re_string_context_at (mctx->input, dest_idx - 1, mctx->eflags,
2347                                       preg->newline_anchor);
2348       mctx->state_log[dest_idx]
2349         = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2350       if (BE (mctx->state_log[dest_idx] == NULL && err != REG_NOERROR, 0))
2351         return err;
2352       if (dest_state != NULL)
2353         re_node_set_free (&dest_nodes);
2354     }
2355   return REG_NOERROR;
2356 }
2357 #endif /* RE_ENABLE_I18N */
2358
2359 static reg_errcode_t
2360 transit_state_bkref (preg, pstate, mctx)
2361     const regex_t *preg;
2362     re_dfastate_t *pstate;
2363     re_match_context_t *mctx;
2364 {
2365   reg_errcode_t err;
2366   re_dfastate_t **work_state_log;
2367
2368   work_state_log = re_malloc (re_dfastate_t *,
2369                               re_string_cur_idx (mctx->input) + 1);
2370   if (BE (work_state_log == NULL, 0))
2371     return REG_ESPACE;
2372
2373   err = transit_state_bkref_loop (preg, &pstate->nodes, work_state_log, mctx);
2374   re_free (work_state_log);
2375   return err;
2376 }
2377
2378 /* Caller must allocate `work_state_log'.  */
2379
2380 static reg_errcode_t
2381 transit_state_bkref_loop (preg, nodes, work_state_log, mctx)
2382     const regex_t *preg;
2383     re_node_set *nodes;
2384     re_dfastate_t **work_state_log;
2385     re_match_context_t *mctx;
2386 {
2387   reg_errcode_t err;
2388   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
2389   int i;
2390   regmatch_t *cur_regs = re_malloc (regmatch_t, preg->re_nsub + 1);
2391   int cur_str_idx = re_string_cur_idx (mctx->input);
2392   if (BE (cur_regs == NULL, 0))
2393     return REG_ESPACE;
2394
2395   for (i = 0; i < nodes->nelem; ++i)
2396     {
2397       int dest_str_idx, subexp_idx, prev_nelem, bkc_idx;
2398       int node_idx = nodes->elems[i];
2399       unsigned int context;
2400       re_token_t *node = dfa->nodes + node_idx;
2401       re_node_set *new_dest_nodes;
2402       re_sift_context_t sctx;
2403
2404       /* Check whether `node' is a backreference or not.  */
2405       if (node->type == OP_BACK_REF)
2406         subexp_idx = node->opr.idx;
2407       else if (node->type == OP_CONTEXT_NODE &&
2408                dfa->nodes[node->opr.ctx_info->entity].type == OP_BACK_REF)
2409         {
2410           context = re_string_context_at (mctx->input, cur_str_idx,
2411                                           mctx->eflags, preg->newline_anchor);
2412           if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
2413             continue;
2414           subexp_idx = dfa->nodes[node->opr.ctx_info->entity].opr.idx;
2415         }
2416       else
2417         continue;
2418
2419       /* `node' is a backreference.
2420          Check the substring which the substring matched.  */
2421       sift_ctx_init (&sctx, work_state_log, NULL, node_idx, cur_str_idx,
2422                      subexp_idx);
2423       sctx.cur_bkref = node_idx;
2424       match_ctx_clear_flag (mctx);
2425       err = sift_states_backward (preg, mctx, &sctx);
2426       if (BE (err != REG_NOERROR, 0))
2427         return err;
2428
2429       /* And add the epsilon closures (which is `new_dest_nodes') of
2430          the backreference to appropriate state_log.  */
2431 #ifdef DEBUG
2432       assert (dfa->nexts[node_idx] != -1);
2433 #endif
2434       for (bkc_idx = 0; bkc_idx < mctx->nbkref_ents; ++bkc_idx)
2435         {
2436           int subexp_len;
2437           re_dfastate_t *dest_state;
2438           struct re_backref_cache_entry *bkref_ent;
2439           bkref_ent = mctx->bkref_ents + bkc_idx;
2440           if (bkref_ent->node != node_idx || bkref_ent->str_idx != cur_str_idx)
2441             continue;
2442           subexp_len = bkref_ent->subexp_to - bkref_ent->subexp_from;
2443           new_dest_nodes = ((node->type == OP_CONTEXT_NODE && subexp_len == 0)
2444                             ? dfa->nodes[node_idx].opr.ctx_info->bkref_eclosure
2445                             : dfa->eclosures + dfa->nexts[node_idx]);
2446           dest_str_idx = (cur_str_idx + bkref_ent->subexp_to
2447                           - bkref_ent->subexp_from);
2448           context = (IS_WORD_CHAR (re_string_byte_at (mctx->input,
2449                                                       dest_str_idx - 1))
2450                      ? CONTEXT_WORD : 0);
2451           dest_state = mctx->state_log[dest_str_idx];
2452           prev_nelem = ((mctx->state_log[cur_str_idx] == NULL) ? 0
2453                         : mctx->state_log[cur_str_idx]->nodes.nelem);
2454           /* Add `new_dest_node' to state_log.  */
2455           if (dest_state == NULL)
2456             {
2457               mctx->state_log[dest_str_idx]
2458                 = re_acquire_state_context (&err, dfa, new_dest_nodes,
2459                                             context);
2460               if (BE (mctx->state_log[dest_str_idx] == NULL
2461                       && err != REG_NOERROR, 0))
2462                 return err;
2463             }
2464           else
2465             {
2466               re_node_set dest_nodes;
2467               err = re_node_set_init_union (&dest_nodes,
2468                                             dest_state->entrance_nodes,
2469                                             new_dest_nodes);
2470               if (BE (err != REG_NOERROR, 0))
2471                 return err;
2472               mctx->state_log[dest_str_idx]
2473                 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2474               if (BE (mctx->state_log[dest_str_idx] == NULL
2475                       && err != REG_NOERROR, 0))
2476                 return err;
2477               re_node_set_free (&dest_nodes);
2478             }
2479           /* We need to check recursively if the backreference can epsilon
2480              transit.  */
2481           if (subexp_len == 0
2482               && mctx->state_log[cur_str_idx]->nodes.nelem > prev_nelem)
2483             {
2484               err = transit_state_bkref_loop (preg, new_dest_nodes,
2485                                               work_state_log, mctx);
2486               if (BE (err != REG_NOERROR, 0))
2487                 return err;
2488             }
2489         }
2490     }
2491   re_free (cur_regs);
2492   return REG_NOERROR;
2493 }
2494
2495 /* Build transition table for the state.
2496    Return the new table if succeeded, otherwise return NULL.  */
2497
2498 static re_dfastate_t **
2499 build_trtable (preg, state, fl_search)
2500     const regex_t *preg;
2501     const re_dfastate_t *state;
2502     int fl_search;
2503 {
2504   reg_errcode_t err;
2505   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
2506   int i, j, k, ch;
2507   int ndests; /* Number of the destination states from `state'.  */
2508   re_dfastate_t **trtable, **dest_states, **dest_states_word, **dest_states_nl;
2509   re_node_set follows, *dests_node;
2510   bitset *dests_ch;
2511   bitset acceptable;
2512
2513   /* We build DFA states which corresponds to the destination nodes
2514      from `state'.  `dests_node[i]' represents the nodes which i-th
2515      destination state contains, and `dests_ch[i]' represents the
2516      characters which i-th destination state accepts.  */
2517   dests_node = re_malloc (re_node_set, SBC_MAX);
2518   dests_ch = re_malloc (bitset, SBC_MAX);
2519
2520   /* Initialize transiton table.  */
2521   trtable = (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), SBC_MAX);
2522   if (BE (dests_node == NULL || dests_ch == NULL || trtable == NULL, 0))
2523     return NULL;
2524
2525   /* At first, group all nodes belonging to `state' into several
2526      destinations.  */
2527   ndests = group_nodes_into_DFAstates (preg, state, dests_node, dests_ch);
2528   if (BE (ndests <= 0, 0))
2529     {
2530       re_free (dests_node);
2531       re_free (dests_ch);
2532       /* Return NULL in case of an error, trtable otherwise.  */
2533       return (ndests < 0) ? NULL : trtable;
2534     }
2535
2536   dest_states = re_malloc (re_dfastate_t *, ndests);
2537   dest_states_word = re_malloc (re_dfastate_t *, ndests);
2538   dest_states_nl = re_malloc (re_dfastate_t *, ndests);
2539   bitset_empty (acceptable);
2540
2541   err = re_node_set_alloc (&follows, ndests + 1);
2542   if (BE (dest_states == NULL || dest_states_word == NULL
2543           || dest_states_nl == NULL || err != REG_NOERROR, 0))
2544     return NULL;
2545
2546   /* Then build the states for all destinations.  */
2547   for (i = 0; i < ndests; ++i)
2548     {
2549       int next_node;
2550       re_node_set_empty (&follows);
2551       /* Merge the follows of this destination states.  */
2552       for (j = 0; j < dests_node[i].nelem; ++j)
2553         {
2554           next_node = dfa->nexts[dests_node[i].elems[j]];
2555           if (next_node != -1)
2556             {
2557               err = re_node_set_merge (&follows, dfa->eclosures + next_node);
2558               if (BE (err != REG_NOERROR, 0))
2559                 return NULL;
2560             }
2561         }
2562       /* If search flag is set, merge the initial state.  */
2563       if (fl_search)
2564         {
2565 #ifdef RE_ENABLE_I18N
2566           int not_initial = 0;
2567           for (j = 0; j < follows.nelem; ++j)
2568             if (dfa->nodes[follows.elems[j]].type == CHARACTER)
2569               {
2570                 not_initial = dfa->nodes[follows.elems[j]].mb_partial;
2571                 break;
2572               }
2573           if (!not_initial)
2574 #endif
2575             {
2576               err = re_node_set_merge (&follows,
2577                                        dfa->init_state->entrance_nodes);
2578               if (BE (err != REG_NOERROR, 0))
2579                 return NULL;
2580             }
2581         }
2582       dest_states[i] = re_acquire_state_context (&err, dfa, &follows, 0);
2583       if (BE (dest_states[i] == NULL && err != REG_NOERROR, 0))
2584         return NULL;
2585       /* If the new state has context constraint,
2586          build appropriate states for these contexts.  */
2587       if (dest_states[i]->has_constraint)
2588         {
2589           dest_states_word[i] = re_acquire_state_context (&err, dfa, &follows,
2590                                                           CONTEXT_WORD);
2591           if (BE (dest_states_word[i] == NULL && err != REG_NOERROR, 0))
2592             return NULL;
2593           dest_states_nl[i] = re_acquire_state_context (&err, dfa, &follows,
2594                                                         CONTEXT_NEWLINE);
2595           if (BE (dest_states_nl[i] == NULL && err != REG_NOERROR, 0))
2596             return NULL;
2597         }
2598       else
2599         {
2600           dest_states_word[i] = dest_states[i];
2601           dest_states_nl[i] = dest_states[i];
2602         }
2603       bitset_merge (acceptable, dests_ch[i]);
2604     }
2605
2606   /* Update the transition table.  */
2607   /* For all characters ch...:  */
2608   for (i = 0, ch = 0; i < BITSET_UINTS; ++i)
2609     for (j = 0; j < UINT_BITS; ++j, ++ch)
2610       if ((acceptable[i] >> j) & 1)
2611         {
2612           /* The current state accepts the character ch.  */
2613           if (IS_WORD_CHAR (ch))
2614             {
2615               for (k = 0; k < ndests; ++k)
2616                 if ((dests_ch[k][i] >> j) & 1)
2617                   {
2618                     /* k-th destination accepts the word character ch.  */
2619                     trtable[ch] = dest_states_word[k];
2620                     /* There must be only one destination which accepts
2621                        character ch.  See group_nodes_into_DFAstates.  */
2622                     break;
2623                   }
2624             }
2625           else /* not WORD_CHAR */
2626             {
2627               for (k = 0; k < ndests; ++k)
2628                 if ((dests_ch[k][i] >> j) & 1)
2629                   {
2630                     /* k-th destination accepts the non-word character ch.  */
2631                     trtable[ch] = dest_states[k];
2632                     /* There must be only one destination which accepts
2633                        character ch.  See group_nodes_into_DFAstates.  */
2634                     break;
2635                   }
2636             }
2637         }
2638   /* new line */
2639   if (bitset_contain (acceptable, NEWLINE_CHAR))
2640     {
2641       /* The current state accepts newline character.  */
2642       for (k = 0; k < ndests; ++k)
2643         if (bitset_contain (dests_ch[k], NEWLINE_CHAR))
2644           {
2645             /* k-th destination accepts newline character.  */
2646             trtable[NEWLINE_CHAR] = dest_states_nl[k];
2647             /* There must be only one destination which accepts
2648                newline.  See group_nodes_into_DFAstates.  */
2649             break;
2650           }
2651     }
2652
2653   re_free (dest_states_nl);
2654   re_free (dest_states_word);
2655   re_free (dest_states);
2656
2657   re_node_set_free (&follows);
2658   for (i = 0; i < ndests; ++i)
2659     re_node_set_free (dests_node + i);
2660
2661   re_free (dests_ch);
2662   re_free (dests_node);
2663
2664   return trtable;
2665 }
2666
2667 /* Group all nodes belonging to STATE into several destinations.
2668    Then for all destinations, set the nodes belonging to the destination
2669    to DESTS_NODE[i] and set the characters accepted by the destination
2670    to DEST_CH[i].  This function return the number of destinations.  */
2671
2672 static int
2673 group_nodes_into_DFAstates (preg, state, dests_node, dests_ch)
2674     const regex_t *preg;
2675     const re_dfastate_t *state;
2676     re_node_set *dests_node;
2677     bitset *dests_ch;
2678 {
2679   reg_errcode_t err;
2680   const re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
2681   int i, j, k;
2682   int ndests; /* Number of the destinations from `state'.  */
2683   bitset accepts; /* Characters a node can accept.  */
2684   const re_node_set *cur_nodes = &state->nodes;
2685   bitset_empty (accepts);
2686   ndests = 0;
2687
2688   /* For all the nodes belonging to `state',  */
2689   for (i = 0; i < cur_nodes->nelem; ++i)
2690     {
2691       unsigned int constraint = 0;
2692       re_token_t *node = &dfa->nodes[cur_nodes->elems[i]];
2693       re_token_type_t type = node->type;
2694
2695       if (type == OP_CONTEXT_NODE)
2696         {
2697           constraint = node->constraint;
2698           node = dfa->nodes + node->opr.ctx_info->entity;
2699           type = node->type;
2700         }
2701
2702       /* Enumerate all single byte character this node can accept.  */
2703       if (type == CHARACTER)
2704         bitset_set (accepts, node->opr.c);
2705       else if (type == SIMPLE_BRACKET)
2706         {
2707           bitset_merge (accepts, node->opr.sbcset);
2708         }
2709       else if (type == OP_PERIOD)
2710         {
2711           bitset_set_all (accepts);
2712           if (!(preg->syntax & RE_DOT_NEWLINE))
2713             bitset_clear (accepts, '\n');
2714           if (preg->syntax & RE_DOT_NOT_NULL)
2715             bitset_clear (accepts, '\0');
2716         }
2717       else
2718         continue;
2719
2720       /* Check the `accepts' and sift the characters which are not
2721          match it the context.  */
2722       if (constraint)
2723         {
2724           if (constraint & NEXT_WORD_CONSTRAINT)
2725             for (j = 0; j < BITSET_UINTS; ++j)
2726               accepts[j] &= dfa->word_char[j];
2727           else if (constraint & NEXT_NOTWORD_CONSTRAINT)
2728             for (j = 0; j < BITSET_UINTS; ++j)
2729               accepts[j] &= ~dfa->word_char[j];
2730           else if (constraint & NEXT_NEWLINE_CONSTRAINT)
2731             {
2732               int accepts_newline = bitset_contain (accepts, NEWLINE_CHAR);
2733               bitset_empty (accepts);
2734               if (accepts_newline)
2735                 bitset_set (accepts, NEWLINE_CHAR);
2736               else
2737                 continue;
2738             }
2739         }
2740
2741       /* Then divide `accepts' into DFA states, or create a new
2742          state.  */
2743       for (j = 0; j < ndests; ++j)
2744         {
2745           bitset intersec; /* Intersection sets, see below.  */
2746           bitset remains;
2747           /* Flags, see below.  */
2748           int has_intersec, not_subset, not_consumed;
2749
2750           /* Optimization, skip if this state doesn't accept the character.  */
2751           if (type == CHARACTER && !bitset_contain (dests_ch[j], node->opr.c))
2752             continue;
2753
2754           /* Enumerate the intersection set of this state and `accepts'.  */
2755           has_intersec = 0;
2756           for (k = 0; k < BITSET_UINTS; ++k)
2757             has_intersec |= intersec[k] = accepts[k] & dests_ch[j][k];
2758           /* And skip if the intersection set is empty.  */
2759           if (!has_intersec)
2760             continue;
2761
2762           /* Then check if this state is a subset of `accepts'.  */
2763           not_subset = not_consumed = 0;
2764           for (k = 0; k < BITSET_UINTS; ++k)
2765             {
2766               not_subset |= remains[k] = ~accepts[k] & dests_ch[j][k];
2767               not_consumed |= accepts[k] = accepts[k] & ~dests_ch[j][k];
2768             }
2769
2770           /* If this state isn't a subset of `accepts', create a
2771              new group state, which has the `remains'. */
2772           if (not_subset)
2773             {
2774               bitset_copy (dests_ch[ndests], remains);
2775               bitset_copy (dests_ch[j], intersec);
2776               err = re_node_set_init_copy (dests_node + ndests, &dests_node[j]);
2777               if (BE (err != REG_NOERROR, 0))
2778                 return -1;
2779               ++ndests;
2780             }
2781
2782           /* Put the position in the current group. */
2783           err = re_node_set_insert (&dests_node[j], cur_nodes->elems[i]);
2784           if (BE (err < 0, 0))
2785             return -1;
2786
2787           /* If all characters are consumed, go to next node. */
2788           if (!not_consumed)
2789             break;
2790         }
2791       /* Some characters remain, create a new group. */
2792       if (j == ndests)
2793         {
2794           bitset_copy (dests_ch[ndests], accepts);
2795           err = re_node_set_init_1 (dests_node + ndests, cur_nodes->elems[i]);
2796           if (BE (err != REG_NOERROR, 0))
2797             return -1;
2798           ++ndests;
2799           bitset_empty (accepts);
2800         }
2801     }
2802   return ndests;
2803 }
2804
2805 #ifdef RE_ENABLE_I18N
2806 /* Check how many bytes the node `dfa->nodes[node_idx]' accepts.
2807    Return the number of the bytes the node accepts.
2808    STR_IDX is the current index of the input string.
2809
2810    This function handles the nodes which can accept one character, or
2811    one collating element like '.', '[a-z]', opposite to the other nodes
2812    can only accept one byte.  */
2813
2814 static int
2815 check_node_accept_bytes (preg, node_idx, input, str_idx)
2816     const regex_t *preg;
2817     int node_idx, str_idx;
2818     const re_string_t *input;
2819 {
2820   const re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
2821   const re_token_t *node = dfa->nodes + node_idx;
2822   int elem_len = re_string_elem_size_at (input, str_idx);
2823   int char_len = re_string_char_size_at (input, str_idx);
2824   int i;
2825 # ifdef _LIBC
2826   int j;
2827   uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
2828 # endif /* _LIBC */
2829   if (elem_len <= 1 && char_len <= 1)
2830     return 0;
2831   if (node->type == OP_PERIOD)
2832     {
2833       /* '.' accepts any one character except the following two cases.  */
2834       if ((!(preg->syntax & RE_DOT_NEWLINE) &&
2835            re_string_byte_at (input, str_idx) == '\n') ||
2836           ((preg->syntax & RE_DOT_NOT_NULL) &&
2837            re_string_byte_at (input, str_idx) == '\0'))
2838         return 0;
2839       return char_len;
2840     }
2841   else if (node->type == COMPLEX_BRACKET)
2842     {
2843       const re_charset_t *cset = node->opr.mbcset;
2844 # ifdef _LIBC
2845       const unsigned char *pin = re_string_get_buffer (input) + str_idx;
2846 # endif /* _LIBC */
2847       int match_len = 0;
2848       wchar_t wc = ((cset->nranges || cset->nchar_classes || cset->nmbchars)
2849                     ? re_string_wchar_at (input, str_idx) : 0);
2850
2851       /* match with multibyte character?  */
2852       for (i = 0; i < cset->nmbchars; ++i)
2853         if (wc == cset->mbchars[i])
2854           {
2855             match_len = char_len;
2856             goto check_node_accept_bytes_match;
2857           }
2858       /* match with character_class?  */
2859       for (i = 0; i < cset->nchar_classes; ++i)
2860         {
2861           wctype_t wt = cset->char_classes[i];
2862           if (__iswctype (wc, wt))
2863             {
2864               match_len = char_len;
2865               goto check_node_accept_bytes_match;
2866             }
2867         }
2868
2869 # ifdef _LIBC
2870       if (nrules != 0)
2871         {
2872           unsigned int in_collseq = 0;
2873           const int32_t *table, *indirect;
2874           const unsigned char *weights, *extra;
2875           const char *collseqwc;
2876           int32_t idx;
2877           /* This #include defines a local function!  */
2878 #  include <locale/weight.h>
2879
2880           /* match with collating_symbol?  */
2881           if (cset->ncoll_syms)
2882             extra = (const unsigned char *)
2883               _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
2884           for (i = 0; i < cset->ncoll_syms; ++i)
2885             {
2886               const unsigned char *coll_sym = extra + cset->coll_syms[i];
2887               /* Compare the length of input collating element and
2888                  the length of current collating element.  */
2889               if (*coll_sym != elem_len)
2890                 continue;
2891               /* Compare each bytes.  */
2892               for (j = 0; j < *coll_sym; j++)
2893                 if (pin[j] != coll_sym[1 + j])
2894                   break;
2895               if (j == *coll_sym)
2896                 {
2897                   /* Match if every bytes is equal.  */
2898                   match_len = j;
2899                   goto check_node_accept_bytes_match;
2900                 }
2901             }
2902
2903           if (cset->nranges)
2904             {
2905               if (elem_len <= char_len)
2906                 {
2907                   collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC);
2908                   in_collseq = collseq_table_lookup (collseqwc, wc);
2909                 }
2910               else
2911                 in_collseq = find_collation_sequence_value (pin, elem_len);
2912             }
2913           /* match with range expression?  */
2914           for (i = 0; i < cset->nranges; ++i)
2915             if (cset->range_starts[i] <= in_collseq
2916                 && in_collseq <= cset->range_ends[i])
2917               {
2918                 match_len = elem_len;
2919                 goto check_node_accept_bytes_match;
2920               }
2921
2922           /* match with equivalence_class?  */
2923           if (cset->nequiv_classes)
2924             {
2925               const unsigned char *cp = pin;
2926               table = (const int32_t *)
2927                 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
2928               weights = (const unsigned char *)
2929                 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTMB);
2930               extra = (const unsigned char *)
2931                 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB);
2932               indirect = (const int32_t *)
2933                 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTMB);
2934               idx = findidx (&cp);
2935               if (idx > 0)
2936                 for (i = 0; i < cset->nequiv_classes; ++i)
2937                   {
2938                     int32_t equiv_class_idx = cset->equiv_classes[i];
2939                     size_t weight_len = weights[idx];
2940                     if (weight_len == weights[equiv_class_idx])
2941                       {
2942                         int cnt = 0;
2943                         while (cnt <= weight_len
2944                                && (weights[equiv_class_idx + 1 + cnt]
2945                                    == weights[idx + 1 + cnt]))
2946                           ++cnt;
2947                         if (cnt > weight_len)
2948                           {
2949                             match_len = elem_len;
2950                             goto check_node_accept_bytes_match;
2951                           }
2952                       }
2953                   }
2954             }
2955         }
2956       else
2957 # endif /* _LIBC */
2958         {
2959           /* match with range expression?  */
2960 #if __GNUC__ >= 2
2961           wchar_t cmp_buf[] = {L'\0', L'\0', wc, L'\0', L'\0', L'\0'};
2962 #else
2963           wchar_t cmp_buf[] = {L'\0', L'\0', L'\0', L'\0', L'\0', L'\0'};
2964           cmp_buf[2] = wc;
2965 #endif
2966           for (i = 0; i < cset->nranges; ++i)
2967             {
2968               cmp_buf[0] = cset->range_starts[i];
2969               cmp_buf[4] = cset->range_ends[i];
2970               if (wcscoll (cmp_buf, cmp_buf + 2) <= 0
2971                   && wcscoll (cmp_buf + 2, cmp_buf + 4) <= 0)
2972                 {
2973                   match_len = char_len;
2974                   goto check_node_accept_bytes_match;
2975                 }
2976             }
2977         }
2978     check_node_accept_bytes_match:
2979       if (!cset->non_match)
2980         return match_len;
2981       else
2982         {
2983           if (match_len > 0)
2984             return 0;
2985           else
2986             return (elem_len > char_len) ? elem_len : char_len;
2987         }
2988     }
2989   return 0;
2990 }
2991
2992 # ifdef _LIBC
2993 static unsigned int
2994 find_collation_sequence_value (mbs, mbs_len)
2995     const unsigned char *mbs;
2996     size_t mbs_len;
2997 {
2998   uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
2999   if (nrules == 0)
3000     {
3001       if (mbs_len == 1)
3002         {
3003           /* No valid character.  Match it as a single byte character.  */
3004           const unsigned char *collseq = (const unsigned char *)
3005             _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQMB);
3006           return collseq[mbs[0]];
3007         }
3008       return UINT_MAX;
3009     }
3010   else
3011     {
3012       int32_t idx;
3013       const unsigned char *extra = (const unsigned char *)
3014         _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
3015
3016       for (idx = 0; ;)
3017         {
3018           int mbs_cnt, found = 0;
3019           int32_t elem_mbs_len;
3020           /* Skip the name of collating element name.  */
3021           idx = idx + extra[idx] + 1;
3022           elem_mbs_len = extra[idx++];
3023           if (mbs_len == elem_mbs_len)
3024             {
3025               for (mbs_cnt = 0; mbs_cnt < elem_mbs_len; ++mbs_cnt)
3026                 if (extra[idx + mbs_cnt] != mbs[mbs_cnt])
3027                   break;
3028               if (mbs_cnt == elem_mbs_len)
3029                 /* Found the entry.  */
3030                 found = 1;
3031             }
3032           /* Skip the byte sequence of the collating element.  */
3033           idx += elem_mbs_len;
3034           /* Adjust for the alignment.  */
3035           idx = (idx + 3) & ~3;
3036           /* Skip the collation sequence value.  */
3037           idx += sizeof (uint32_t);
3038           /* Skip the wide char sequence of the collating element.  */
3039           idx = idx + sizeof (uint32_t) * (extra[idx] + 1);
3040           /* If we found the entry, return the sequence value.  */
3041           if (found)
3042             return *(uint32_t *) (extra + idx);
3043           /* Skip the collation sequence value.  */
3044           idx += sizeof (uint32_t);
3045         }
3046     }
3047 }
3048 # endif /* _LIBC */
3049 #endif /* RE_ENABLE_I18N */
3050
3051 /* Check whether the node accepts the byte which is IDX-th
3052    byte of the INPUT.  */
3053
3054 static int
3055 check_node_accept (preg, node, mctx, idx)
3056     const regex_t *preg;
3057     const re_token_t *node;
3058     const re_match_context_t *mctx;
3059     int idx;
3060 {
3061   const re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
3062   const re_token_t *cur_node;
3063   unsigned char ch;
3064   if (node->type == OP_CONTEXT_NODE)
3065     {
3066       /* The node has constraints.  Check whether the current context
3067          satisfies the constraints.  */
3068       unsigned int context = re_string_context_at (mctx->input, idx,
3069                                                    mctx->eflags,
3070                                                    preg->newline_anchor);
3071       if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
3072         return 0;
3073       cur_node = dfa->nodes + node->opr.ctx_info->entity;
3074     }
3075   else
3076     cur_node = node;
3077
3078   ch = re_string_byte_at (mctx->input, idx);
3079   if (cur_node->type == CHARACTER)
3080     return cur_node->opr.c == ch;
3081   else if (cur_node->type == SIMPLE_BRACKET)
3082     return bitset_contain (cur_node->opr.sbcset, ch);
3083   else if (cur_node->type == OP_PERIOD)
3084     return !((ch == '\n' && !(preg->syntax & RE_DOT_NEWLINE))
3085              || (ch == '\0' && (preg->syntax & RE_DOT_NOT_NULL)));
3086   else
3087     return 0;
3088 }
3089
3090 /* Extend the buffers, if the buffers have run out.  */
3091
3092 static reg_errcode_t
3093 extend_buffers (mctx)
3094      re_match_context_t *mctx;
3095 {
3096   reg_errcode_t ret;
3097   re_string_t *pstr = mctx->input;
3098
3099   /* Double the lengthes of the buffers.  */
3100   ret = re_string_realloc_buffers (pstr, pstr->bufs_len * 2);
3101   if (BE (ret != REG_NOERROR, 0))
3102     return ret;
3103
3104   if (mctx->state_log != NULL)
3105     {
3106       /* And double the length of state_log.  */
3107       mctx->state_log = re_realloc (mctx->state_log, re_dfastate_t *,
3108                                     pstr->bufs_len * 2);
3109       if (BE (mctx->state_log == NULL, 0))
3110         return REG_ESPACE;
3111     }
3112
3113   /* Then reconstruct the buffers.  */
3114   if (pstr->icase)
3115     {
3116 #ifdef RE_ENABLE_I18N
3117       if (MB_CUR_MAX > 1)
3118         build_wcs_upper_buffer (pstr);
3119       else
3120 #endif /* RE_ENABLE_I18N  */
3121         build_upper_buffer (pstr);
3122     }
3123   else
3124     {
3125 #ifdef RE_ENABLE_I18N
3126       if (MB_CUR_MAX > 1)
3127         build_wcs_buffer (pstr);
3128       else
3129 #endif /* RE_ENABLE_I18N  */
3130         {
3131           if (pstr->trans != NULL)
3132             re_string_translate_buffer (pstr);
3133           else
3134             pstr->valid_len = pstr->bufs_len;
3135         }
3136     }
3137   return REG_NOERROR;
3138 }
3139
3140 \f
3141 /* Functions for matching context.  */
3142
3143 static reg_errcode_t
3144 match_ctx_init (mctx, eflags, input, n)
3145     re_match_context_t *mctx;
3146     int eflags, n;
3147     re_string_t *input;
3148 {
3149   mctx->eflags = eflags;
3150   mctx->input = input;
3151   mctx->match_last = -1;
3152   if (n > 0)
3153     {
3154       mctx->bkref_ents = re_malloc (struct re_backref_cache_entry, n);
3155       if (BE (mctx->bkref_ents == NULL, 0))
3156         return REG_ESPACE;
3157     }
3158   else
3159     mctx->bkref_ents = NULL;
3160   mctx->nbkref_ents = 0;
3161   mctx->abkref_ents = n;
3162   mctx->max_mb_elem_len = 0;
3163   return REG_NOERROR;
3164 }
3165
3166 static void
3167 match_ctx_free (mctx)
3168     re_match_context_t *mctx;
3169 {
3170   re_free (mctx->bkref_ents);
3171 }
3172
3173 /* Add a new backreference entry to the cache.  */
3174
3175 static reg_errcode_t
3176 match_ctx_add_entry (mctx, node, str_idx, from, to)
3177     re_match_context_t *mctx;
3178     int node, str_idx, from, to;
3179 {
3180   if (mctx->nbkref_ents >= mctx->abkref_ents)
3181     {
3182       mctx->bkref_ents = re_realloc (mctx->bkref_ents,
3183                                      struct re_backref_cache_entry,
3184                                      mctx->abkref_ents * 2);
3185       if (BE (mctx->bkref_ents == NULL, 0))
3186         return REG_ESPACE;
3187       memset (mctx->bkref_ents + mctx->nbkref_ents, '\0',
3188              sizeof (struct re_backref_cache_entry) * mctx->abkref_ents);
3189       mctx->abkref_ents *= 2;
3190     }
3191   mctx->bkref_ents[mctx->nbkref_ents].node = node;
3192   mctx->bkref_ents[mctx->nbkref_ents].str_idx = str_idx;
3193   mctx->bkref_ents[mctx->nbkref_ents].subexp_from = from;
3194   mctx->bkref_ents[mctx->nbkref_ents].subexp_to = to;
3195   mctx->bkref_ents[mctx->nbkref_ents++].flag = 0;
3196   if (mctx->max_mb_elem_len < to - from)
3197     mctx->max_mb_elem_len = to - from;
3198   return REG_NOERROR;
3199 }
3200
3201 static void
3202 match_ctx_clear_flag (mctx)
3203      re_match_context_t *mctx;
3204 {
3205   int i;
3206   for (i = 0; i < mctx->nbkref_ents; ++i)
3207     {
3208       mctx->bkref_ents[i].flag = 0;
3209     }
3210 }
3211
3212 static void
3213 sift_ctx_init (sctx, sifted_sts, limited_sts, last_node, last_str_idx,
3214                check_subexp)
3215     re_sift_context_t *sctx;
3216     re_dfastate_t **sifted_sts, **limited_sts;
3217     int last_node, last_str_idx, check_subexp;
3218 {
3219   sctx->sifted_states = sifted_sts;
3220   sctx->limited_states = limited_sts;
3221   sctx->last_node = last_node;
3222   sctx->last_str_idx = last_str_idx;
3223   sctx->check_subexp = check_subexp;
3224   re_node_set_init_empty (&sctx->limits);
3225 }