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