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