Annotation of embedaddon/smartmontools/regex/regexec.c, revision 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