Annotation of embedaddon/smartmontools/regex/regcomp.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 re_compile_internal (regex_t *preg, const char * pattern,
! 22: int length, reg_syntax_t syntax);
! 23: static void re_compile_fastmap_iter (regex_t *bufp,
! 24: const re_dfastate_t *init_state,
! 25: char *fastmap);
! 26: static reg_errcode_t init_dfa (re_dfa_t *dfa, int pat_len);
! 27: static reg_errcode_t init_word_char (re_dfa_t *dfa);
! 28: #ifdef RE_ENABLE_I18N
! 29: static void free_charset (re_charset_t *cset);
! 30: #endif /* RE_ENABLE_I18N */
! 31: static void free_workarea_compile (regex_t *preg);
! 32: static reg_errcode_t create_initial_state (re_dfa_t *dfa);
! 33: static reg_errcode_t analyze (re_dfa_t *dfa);
! 34: static reg_errcode_t analyze_tree (re_dfa_t *dfa, bin_tree_t *node);
! 35: static void calc_first (re_dfa_t *dfa, bin_tree_t *node);
! 36: static void calc_next (re_dfa_t *dfa, bin_tree_t *node);
! 37: static void calc_epsdest (re_dfa_t *dfa, bin_tree_t *node);
! 38: static reg_errcode_t duplicate_node_closure (re_dfa_t *dfa, int top_org_node,
! 39: int top_clone_node, int root_node,
! 40: unsigned int constraint);
! 41: static reg_errcode_t duplicate_node (int *new_idx, re_dfa_t *dfa, int org_idx,
! 42: unsigned int constraint);
! 43: static int search_duplicated_node (re_dfa_t *dfa, int org_node,
! 44: unsigned int constraint);
! 45: static reg_errcode_t calc_eclosure (re_dfa_t *dfa);
! 46: static reg_errcode_t calc_eclosure_iter (re_node_set *new_set, re_dfa_t *dfa,
! 47: int node, int root);
! 48: static void calc_inveclosure (re_dfa_t *dfa);
! 49: static int fetch_number (re_string_t *input, re_token_t *token,
! 50: reg_syntax_t syntax);
! 51: static re_token_t fetch_token (re_string_t *input, reg_syntax_t syntax);
! 52: static int peek_token (re_token_t *token, re_string_t *input,
! 53: reg_syntax_t syntax);
! 54: static int peek_token_bracket (re_token_t *token, re_string_t *input,
! 55: reg_syntax_t syntax);
! 56: static bin_tree_t *parse (re_string_t *regexp, regex_t *preg,
! 57: reg_syntax_t syntax, reg_errcode_t *err);
! 58: static bin_tree_t *parse_reg_exp (re_string_t *regexp, regex_t *preg,
! 59: re_token_t *token, reg_syntax_t syntax,
! 60: int nest, reg_errcode_t *err);
! 61: static bin_tree_t *parse_branch (re_string_t *regexp, regex_t *preg,
! 62: re_token_t *token, reg_syntax_t syntax,
! 63: int nest, reg_errcode_t *err);
! 64: static bin_tree_t *parse_expression (re_string_t *regexp, regex_t *preg,
! 65: re_token_t *token, reg_syntax_t syntax,
! 66: int nest, reg_errcode_t *err);
! 67: static bin_tree_t *parse_sub_exp (re_string_t *regexp, regex_t *preg,
! 68: re_token_t *token, reg_syntax_t syntax,
! 69: int nest, reg_errcode_t *err);
! 70: static bin_tree_t *parse_dup_op (bin_tree_t *dup_elem, re_string_t *regexp,
! 71: re_dfa_t *dfa, re_token_t *token,
! 72: reg_syntax_t syntax, reg_errcode_t *err);
! 73: static bin_tree_t *parse_bracket_exp (re_string_t *regexp, re_dfa_t *dfa,
! 74: re_token_t *token, reg_syntax_t syntax,
! 75: reg_errcode_t *err);
! 76: static reg_errcode_t parse_bracket_element (bracket_elem_t *elem,
! 77: re_string_t *regexp,
! 78: re_token_t *token, int token_len,
! 79: re_dfa_t *dfa,
! 80: reg_syntax_t syntax);
! 81: static reg_errcode_t parse_bracket_symbol (bracket_elem_t *elem,
! 82: re_string_t *regexp,
! 83: re_token_t *token);
! 84: #ifndef _LIBC
! 85: # ifdef RE_ENABLE_I18N
! 86: static reg_errcode_t build_range_exp (re_bitset_ptr_t sbcset,
! 87: re_charset_t *mbcset, int *range_alloc,
! 88: bracket_elem_t *start_elem,
! 89: bracket_elem_t *end_elem);
! 90: static reg_errcode_t build_collating_symbol (re_bitset_ptr_t sbcset,
! 91: re_charset_t *mbcset,
! 92: int *coll_sym_alloc,
! 93: const unsigned char *name);
! 94: # else /* not RE_ENABLE_I18N */
! 95: static reg_errcode_t build_range_exp (re_bitset_ptr_t sbcset,
! 96: bracket_elem_t *start_elem,
! 97: bracket_elem_t *end_elem);
! 98: static reg_errcode_t build_collating_symbol (re_bitset_ptr_t sbcset,
! 99: const unsigned char *name);
! 100: # endif /* not RE_ENABLE_I18N */
! 101: #endif /* not _LIBC */
! 102: #ifdef RE_ENABLE_I18N
! 103: static reg_errcode_t build_equiv_class (re_bitset_ptr_t sbcset,
! 104: re_charset_t *mbcset,
! 105: int *equiv_class_alloc,
! 106: const unsigned char *name);
! 107: static reg_errcode_t build_charclass (re_bitset_ptr_t sbcset,
! 108: re_charset_t *mbcset,
! 109: int *char_class_alloc,
! 110: const unsigned char *class_name,
! 111: reg_syntax_t syntax);
! 112: #else /* not RE_ENABLE_I18N */
! 113: static reg_errcode_t build_equiv_class (re_bitset_ptr_t sbcset,
! 114: const unsigned char *name);
! 115: static reg_errcode_t build_charclass (re_bitset_ptr_t sbcset,
! 116: const unsigned char *class_name,
! 117: reg_syntax_t syntax);
! 118: #endif /* not RE_ENABLE_I18N */
! 119: static bin_tree_t *build_word_op (re_dfa_t *dfa, int not, reg_errcode_t *err);
! 120: static void free_bin_tree (bin_tree_t *tree);
! 121: static bin_tree_t *create_tree (bin_tree_t *left, bin_tree_t *right,
! 122: re_token_type_t type, int index);
! 123: static bin_tree_t *duplicate_tree (const bin_tree_t *src, re_dfa_t *dfa);
! 124:
! 125: /* This table gives an error message for each of the error codes listed
! 126: in regex.h. Obviously the order here has to be same as there.
! 127: POSIX doesn't require that we do anything for REG_NOERROR,
! 128: but why not be nice? */
! 129:
! 130: const char __re_error_msgid[] attribute_hidden =
! 131: {
! 132: #define REG_NOERROR_IDX 0
! 133: gettext_noop ("Success") /* REG_NOERROR */
! 134: "\0"
! 135: #define REG_NOMATCH_IDX (REG_NOERROR_IDX + sizeof "Success")
! 136: gettext_noop ("No match") /* REG_NOMATCH */
! 137: "\0"
! 138: #define REG_BADPAT_IDX (REG_NOMATCH_IDX + sizeof "No match")
! 139: gettext_noop ("Invalid regular expression") /* REG_BADPAT */
! 140: "\0"
! 141: #define REG_ECOLLATE_IDX (REG_BADPAT_IDX + sizeof "Invalid regular expression")
! 142: gettext_noop ("Invalid collation character") /* REG_ECOLLATE */
! 143: "\0"
! 144: #define REG_ECTYPE_IDX (REG_ECOLLATE_IDX + sizeof "Invalid collation character")
! 145: gettext_noop ("Invalid character class name") /* REG_ECTYPE */
! 146: "\0"
! 147: #define REG_EESCAPE_IDX (REG_ECTYPE_IDX + sizeof "Invalid character class name")
! 148: gettext_noop ("Trailing backslash") /* REG_EESCAPE */
! 149: "\0"
! 150: #define REG_ESUBREG_IDX (REG_EESCAPE_IDX + sizeof "Trailing backslash")
! 151: gettext_noop ("Invalid back reference") /* REG_ESUBREG */
! 152: "\0"
! 153: #define REG_EBRACK_IDX (REG_ESUBREG_IDX + sizeof "Invalid back reference")
! 154: gettext_noop ("Unmatched [ or [^") /* REG_EBRACK */
! 155: "\0"
! 156: #define REG_EPAREN_IDX (REG_EBRACK_IDX + sizeof "Unmatched [ or [^")
! 157: gettext_noop ("Unmatched ( or \\(") /* REG_EPAREN */
! 158: "\0"
! 159: #define REG_EBRACE_IDX (REG_EPAREN_IDX + sizeof "Unmatched ( or \\(")
! 160: gettext_noop ("Unmatched \\{") /* REG_EBRACE */
! 161: "\0"
! 162: #define REG_BADBR_IDX (REG_EBRACE_IDX + sizeof "Unmatched \\{")
! 163: gettext_noop ("Invalid content of \\{\\}") /* REG_BADBR */
! 164: "\0"
! 165: #define REG_ERANGE_IDX (REG_BADBR_IDX + sizeof "Invalid content of \\{\\}")
! 166: gettext_noop ("Invalid range end") /* REG_ERANGE */
! 167: "\0"
! 168: #define REG_ESPACE_IDX (REG_ERANGE_IDX + sizeof "Invalid range end")
! 169: gettext_noop ("Memory exhausted") /* REG_ESPACE */
! 170: "\0"
! 171: #define REG_BADRPT_IDX (REG_ESPACE_IDX + sizeof "Memory exhausted")
! 172: gettext_noop ("Invalid preceding regular expression") /* REG_BADRPT */
! 173: "\0"
! 174: #define REG_EEND_IDX (REG_BADRPT_IDX + sizeof "Invalid preceding regular expression")
! 175: gettext_noop ("Premature end of regular expression") /* REG_EEND */
! 176: "\0"
! 177: #define REG_ESIZE_IDX (REG_EEND_IDX + sizeof "Premature end of regular expression")
! 178: gettext_noop ("Regular expression too big") /* REG_ESIZE */
! 179: "\0"
! 180: #define REG_ERPAREN_IDX (REG_ESIZE_IDX + sizeof "Regular expression too big")
! 181: gettext_noop ("Unmatched ) or \\)") /* REG_ERPAREN */
! 182: };
! 183:
! 184: const size_t __re_error_msgid_idx[] attribute_hidden =
! 185: {
! 186: REG_NOERROR_IDX,
! 187: REG_NOMATCH_IDX,
! 188: REG_BADPAT_IDX,
! 189: REG_ECOLLATE_IDX,
! 190: REG_ECTYPE_IDX,
! 191: REG_EESCAPE_IDX,
! 192: REG_ESUBREG_IDX,
! 193: REG_EBRACK_IDX,
! 194: REG_EPAREN_IDX,
! 195: REG_EBRACE_IDX,
! 196: REG_BADBR_IDX,
! 197: REG_ERANGE_IDX,
! 198: REG_ESPACE_IDX,
! 199: REG_BADRPT_IDX,
! 200: REG_EEND_IDX,
! 201: REG_ESIZE_IDX,
! 202: REG_ERPAREN_IDX
! 203: };
! 204:
! 205: /* Entry points for GNU code. */
! 206:
! 207: /* re_compile_pattern is the GNU regular expression compiler: it
! 208: compiles PATTERN (of length LENGTH) and puts the result in BUFP.
! 209: Returns 0 if the pattern was valid, otherwise an error string.
! 210:
! 211: Assumes the `allocated' (and perhaps `buffer') and `translate' fields
! 212: are set in BUFP on entry. */
! 213:
! 214: const char *
! 215: re_compile_pattern (pattern, length, bufp)
! 216: const char *pattern;
! 217: size_t length;
! 218: struct re_pattern_buffer *bufp;
! 219: {
! 220: reg_errcode_t ret;
! 221:
! 222: /* And GNU code determines whether or not to get register information
! 223: by passing null for the REGS argument to re_match, etc., not by
! 224: setting no_sub. */
! 225: bufp->no_sub = 0;
! 226:
! 227: /* Match anchors at newline. */
! 228: bufp->newline_anchor = 1;
! 229:
! 230: ret = re_compile_internal (bufp, pattern, length, re_syntax_options);
! 231:
! 232: if (!ret)
! 233: return NULL;
! 234: return gettext (__re_error_msgid + __re_error_msgid_idx[(int) ret]);
! 235: }
! 236: #ifdef _LIBC
! 237: weak_alias (__re_compile_pattern, re_compile_pattern)
! 238: #endif
! 239:
! 240: /* Set by `re_set_syntax' to the current regexp syntax to recognize. Can
! 241: also be assigned to arbitrarily: each pattern buffer stores its own
! 242: syntax, so it can be changed between regex compilations. */
! 243: /* This has no initializer because initialized variables in Emacs
! 244: become read-only after dumping. */
! 245: reg_syntax_t re_syntax_options;
! 246:
! 247:
! 248: /* Specify the precise syntax of regexps for compilation. This provides
! 249: for compatibility for various utilities which historically have
! 250: different, incompatible syntaxes.
! 251:
! 252: The argument SYNTAX is a bit mask comprised of the various bits
! 253: defined in regex.h. We return the old syntax. */
! 254:
! 255: reg_syntax_t
! 256: re_set_syntax (syntax)
! 257: reg_syntax_t syntax;
! 258: {
! 259: reg_syntax_t ret = re_syntax_options;
! 260:
! 261: re_syntax_options = syntax;
! 262: return ret;
! 263: }
! 264: #ifdef _LIBC
! 265: weak_alias (__re_set_syntax, re_set_syntax)
! 266: #endif
! 267:
! 268: int
! 269: re_compile_fastmap (bufp)
! 270: struct re_pattern_buffer *bufp;
! 271: {
! 272: re_dfa_t *dfa = (re_dfa_t *) bufp->buffer;
! 273: char *fastmap = bufp->fastmap;
! 274:
! 275: memset (fastmap, '\0', sizeof (char) * SBC_MAX);
! 276: re_compile_fastmap_iter (bufp, dfa->init_state, fastmap);
! 277: if (dfa->init_state != dfa->init_state_word)
! 278: re_compile_fastmap_iter (bufp, dfa->init_state_word, fastmap);
! 279: if (dfa->init_state != dfa->init_state_nl)
! 280: re_compile_fastmap_iter (bufp, dfa->init_state_nl, fastmap);
! 281: if (dfa->init_state != dfa->init_state_begbuf)
! 282: re_compile_fastmap_iter (bufp, dfa->init_state_begbuf, fastmap);
! 283: bufp->fastmap_accurate = 1;
! 284: return 0;
! 285: }
! 286: #ifdef _LIBC
! 287: weak_alias (__re_compile_fastmap, re_compile_fastmap)
! 288: #endif
! 289:
! 290: static inline void
! 291: re_set_fastmap (char *fastmap, int icase, int ch)
! 292: {
! 293: fastmap[ch] = 1;
! 294: if (icase)
! 295: fastmap[tolower (ch)] = 1;
! 296: }
! 297:
! 298: /* Helper function for re_compile_fastmap.
! 299: Compile fastmap for the initial_state INIT_STATE. */
! 300:
! 301: static void
! 302: re_compile_fastmap_iter (bufp, init_state, fastmap)
! 303: regex_t *bufp;
! 304: const re_dfastate_t *init_state;
! 305: char *fastmap;
! 306: {
! 307: re_dfa_t *dfa = (re_dfa_t *) bufp->buffer;
! 308: int node_cnt;
! 309: int icase = (MB_CUR_MAX == 1 && (bufp->syntax & RE_ICASE));
! 310: for (node_cnt = 0; node_cnt < init_state->nodes.nelem; ++node_cnt)
! 311: {
! 312: int node = init_state->nodes.elems[node_cnt];
! 313: re_token_type_t type = dfa->nodes[node].type;
! 314:
! 315: if (type == CHARACTER)
! 316: re_set_fastmap (fastmap, icase, dfa->nodes[node].opr.c);
! 317: else if (type == SIMPLE_BRACKET)
! 318: {
! 319: int i, j, ch;
! 320: for (i = 0, ch = 0; i < BITSET_UINTS; ++i)
! 321: for (j = 0; j < UINT_BITS; ++j, ++ch)
! 322: if (dfa->nodes[node].opr.sbcset[i] & (1 << j))
! 323: re_set_fastmap (fastmap, icase, ch);
! 324: }
! 325: #ifdef RE_ENABLE_I18N
! 326: else if (type == COMPLEX_BRACKET)
! 327: {
! 328: int i;
! 329: re_charset_t *cset = dfa->nodes[node].opr.mbcset;
! 330: if (cset->non_match || cset->ncoll_syms || cset->nequiv_classes
! 331: || cset->nranges || cset->nchar_classes)
! 332: {
! 333: # ifdef _LIBC
! 334: if (_NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES) != 0)
! 335: {
! 336: /* In this case we want to catch the bytes which are
! 337: the first byte of any collation elements.
! 338: e.g. In da_DK, we want to catch 'a' since "aa"
! 339: is a valid collation element, and don't catch
! 340: 'b' since 'b' is the only collation element
! 341: which starts from 'b'. */
! 342: int j, ch;
! 343: const int32_t *table = (const int32_t *)
! 344: _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
! 345: for (i = 0, ch = 0; i < BITSET_UINTS; ++i)
! 346: for (j = 0; j < UINT_BITS; ++j, ++ch)
! 347: if (table[ch] < 0)
! 348: re_set_fastmap (fastmap, icase, ch);
! 349: }
! 350: # else
! 351: if (MB_CUR_MAX > 1)
! 352: for (i = 0; i < SBC_MAX; ++i)
! 353: if (__btowc (i) == WEOF)
! 354: re_set_fastmap (fastmap, icase, i);
! 355: # endif /* not _LIBC */
! 356: }
! 357: for (i = 0; i < cset->nmbchars; ++i)
! 358: {
! 359: char buf[256];
! 360: mbstate_t state;
! 361: memset (&state, '\0', sizeof (state));
! 362: __wcrtomb (buf, cset->mbchars[i], &state);
! 363: re_set_fastmap (fastmap, icase, *(unsigned char *) buf);
! 364: }
! 365: }
! 366: #endif /* RE_ENABLE_I18N */
! 367: else if (type == END_OF_RE || type == OP_PERIOD)
! 368: {
! 369: memset (fastmap, '\1', sizeof (char) * SBC_MAX);
! 370: if (type == END_OF_RE)
! 371: bufp->can_be_null = 1;
! 372: return;
! 373: }
! 374: }
! 375: }
! 376:
! 377: /* Entry point for POSIX code. */
! 378: /* regcomp takes a regular expression as a string and compiles it.
! 379:
! 380: PREG is a regex_t *. We do not expect any fields to be initialized,
! 381: since POSIX says we shouldn't. Thus, we set
! 382:
! 383: `buffer' to the compiled pattern;
! 384: `used' to the length of the compiled pattern;
! 385: `syntax' to RE_SYNTAX_POSIX_EXTENDED if the
! 386: REG_EXTENDED bit in CFLAGS is set; otherwise, to
! 387: RE_SYNTAX_POSIX_BASIC;
! 388: `newline_anchor' to REG_NEWLINE being set in CFLAGS;
! 389: `fastmap' to an allocated space for the fastmap;
! 390: `fastmap_accurate' to zero;
! 391: `re_nsub' to the number of subexpressions in PATTERN.
! 392:
! 393: PATTERN is the address of the pattern string.
! 394:
! 395: CFLAGS is a series of bits which affect compilation.
! 396:
! 397: If REG_EXTENDED is set, we use POSIX extended syntax; otherwise, we
! 398: use POSIX basic syntax.
! 399:
! 400: If REG_NEWLINE is set, then . and [^...] don't match newline.
! 401: Also, regexec will try a match beginning after every newline.
! 402:
! 403: If REG_ICASE is set, then we considers upper- and lowercase
! 404: versions of letters to be equivalent when matching.
! 405:
! 406: If REG_NOSUB is set, then when PREG is passed to regexec, that
! 407: routine will report only success or failure, and nothing about the
! 408: registers.
! 409:
! 410: It returns 0 if it succeeds, nonzero if it doesn't. (See regex.h for
! 411: the return codes and their meanings.) */
! 412:
! 413: int
! 414: regcomp (preg, pattern, cflags)
! 415: regex_t *__restrict preg;
! 416: const char *__restrict pattern;
! 417: int cflags;
! 418: {
! 419: reg_errcode_t ret;
! 420: reg_syntax_t syntax = ((cflags & REG_EXTENDED) ? RE_SYNTAX_POSIX_EXTENDED
! 421: : RE_SYNTAX_POSIX_BASIC);
! 422:
! 423: preg->buffer = NULL;
! 424: preg->allocated = 0;
! 425: preg->used = 0;
! 426:
! 427: /* Try to allocate space for the fastmap. */
! 428: preg->fastmap = re_malloc (char, SBC_MAX);
! 429: if (BE (preg->fastmap == NULL, 0))
! 430: return REG_ESPACE;
! 431:
! 432: syntax |= (cflags & REG_ICASE) ? RE_ICASE : 0;
! 433:
! 434: /* If REG_NEWLINE is set, newlines are treated differently. */
! 435: if (cflags & REG_NEWLINE)
! 436: { /* REG_NEWLINE implies neither . nor [^...] match newline. */
! 437: syntax &= ~RE_DOT_NEWLINE;
! 438: syntax |= RE_HAT_LISTS_NOT_NEWLINE;
! 439: /* It also changes the matching behavior. */
! 440: preg->newline_anchor = 1;
! 441: }
! 442: else
! 443: preg->newline_anchor = 0;
! 444: preg->no_sub = !!(cflags & REG_NOSUB);
! 445: preg->translate = NULL;
! 446:
! 447: ret = re_compile_internal (preg, pattern, strlen (pattern), syntax);
! 448:
! 449: /* POSIX doesn't distinguish between an unmatched open-group and an
! 450: unmatched close-group: both are REG_EPAREN. */
! 451: if (ret == REG_ERPAREN)
! 452: ret = REG_EPAREN;
! 453:
! 454: /* We have already checked preg->fastmap != NULL. */
! 455: if (BE (ret == REG_NOERROR, 1))
! 456: /* Compute the fastmap now, since regexec cannot modify the pattern
! 457: buffer. This function nevers fails in this implementation. */
! 458: (void) re_compile_fastmap (preg);
! 459: else
! 460: {
! 461: /* Some error occurred while compiling the expression. */
! 462: re_free (preg->fastmap);
! 463: preg->fastmap = NULL;
! 464: }
! 465:
! 466: return (int) ret;
! 467: }
! 468: #ifdef _LIBC
! 469: weak_alias (__regcomp, regcomp)
! 470: #endif
! 471:
! 472: /* Returns a message corresponding to an error code, ERRCODE, returned
! 473: from either regcomp or regexec. We don't use PREG here. */
! 474:
! 475: size_t
! 476: regerror (errcode, preg, errbuf, errbuf_size)
! 477: int errcode;
! 478: const regex_t *preg;
! 479: char *errbuf;
! 480: size_t errbuf_size;
! 481: {
! 482: const char *msg;
! 483: size_t msg_size;
! 484:
! 485: if (BE (errcode < 0
! 486: || errcode >= (int) (sizeof (__re_error_msgid_idx)
! 487: / sizeof (__re_error_msgid_idx[0])), 0))
! 488: /* Only error codes returned by the rest of the code should be passed
! 489: to this routine. If we are given anything else, or if other regex
! 490: code generates an invalid error code, then the program has a bug.
! 491: Dump core so we can fix it. */
! 492: abort ();
! 493:
! 494: msg = gettext (__re_error_msgid + __re_error_msgid_idx[errcode]);
! 495:
! 496: msg_size = strlen (msg) + 1; /* Includes the null. */
! 497:
! 498: if (BE (errbuf_size != 0, 1))
! 499: {
! 500: if (BE (msg_size > errbuf_size, 0))
! 501: {
! 502: #if defined HAVE_MEMPCPY || defined _LIBC
! 503: *((char *) __mempcpy (errbuf, msg, errbuf_size - 1)) = '\0';
! 504: #else
! 505: memcpy (errbuf, msg, errbuf_size - 1);
! 506: errbuf[errbuf_size - 1] = 0;
! 507: #endif
! 508: }
! 509: else
! 510: memcpy (errbuf, msg, msg_size);
! 511: }
! 512:
! 513: return msg_size;
! 514: }
! 515: #ifdef _LIBC
! 516: weak_alias (__regerror, regerror)
! 517: #endif
! 518:
! 519:
! 520: static void
! 521: free_dfa_content (re_dfa_t *dfa)
! 522: {
! 523: int i, j;
! 524:
! 525: re_free (dfa->subexps);
! 526:
! 527: for (i = 0; i < dfa->nodes_len; ++i)
! 528: {
! 529: re_token_t *node = dfa->nodes + i;
! 530: #ifdef RE_ENABLE_I18N
! 531: if (node->type == COMPLEX_BRACKET && node->duplicated == 0)
! 532: free_charset (node->opr.mbcset);
! 533: else
! 534: #endif /* RE_ENABLE_I18N */
! 535: if (node->type == SIMPLE_BRACKET && node->duplicated == 0)
! 536: re_free (node->opr.sbcset);
! 537: }
! 538: re_free (dfa->nexts);
! 539: for (i = 0; i < dfa->nodes_len; ++i)
! 540: {
! 541: if (dfa->eclosures != NULL)
! 542: re_node_set_free (dfa->eclosures + i);
! 543: if (dfa->inveclosures != NULL)
! 544: re_node_set_free (dfa->inveclosures + i);
! 545: if (dfa->edests != NULL)
! 546: re_node_set_free (dfa->edests + i);
! 547: }
! 548: re_free (dfa->edests);
! 549: re_free (dfa->eclosures);
! 550: re_free (dfa->inveclosures);
! 551: re_free (dfa->nodes);
! 552:
! 553: for (i = 0; i <= dfa->state_hash_mask; ++i)
! 554: {
! 555: struct re_state_table_entry *entry = dfa->state_table + i;
! 556: for (j = 0; j < entry->num; ++j)
! 557: {
! 558: re_dfastate_t *state = entry->array[j];
! 559: free_state (state);
! 560: }
! 561: re_free (entry->array);
! 562: }
! 563: re_free (dfa->state_table);
! 564:
! 565: if (dfa->word_char != NULL)
! 566: re_free (dfa->word_char);
! 567: #ifdef DEBUG
! 568: re_free (dfa->re_str);
! 569: #endif
! 570:
! 571: re_free (dfa);
! 572: }
! 573:
! 574:
! 575: /* Free dynamically allocated space used by PREG. */
! 576:
! 577: void
! 578: regfree (preg)
! 579: regex_t *preg;
! 580: {
! 581: re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
! 582: if (BE (dfa != NULL, 1))
! 583: free_dfa_content (dfa);
! 584:
! 585: re_free (preg->fastmap);
! 586: }
! 587: #ifdef _LIBC
! 588: weak_alias (__regfree, regfree)
! 589: #endif
! 590:
! 591: /* Entry points compatible with 4.2 BSD regex library. We don't define
! 592: them unless specifically requested. */
! 593:
! 594: #if defined _REGEX_RE_COMP || defined _LIBC
! 595:
! 596: /* BSD has one and only one pattern buffer. */
! 597: static struct re_pattern_buffer re_comp_buf;
! 598:
! 599: char *
! 600: # ifdef _LIBC
! 601: /* Make these definitions weak in libc, so POSIX programs can redefine
! 602: these names if they don't use our functions, and still use
! 603: regcomp/regexec above without link errors. */
! 604: weak_function
! 605: # endif
! 606: re_comp (s)
! 607: const char *s;
! 608: {
! 609: reg_errcode_t ret;
! 610: char *fastmap;
! 611:
! 612: if (!s)
! 613: {
! 614: if (!re_comp_buf.buffer)
! 615: return gettext ("No previous regular expression");
! 616: return 0;
! 617: }
! 618:
! 619: if (re_comp_buf.buffer)
! 620: {
! 621: fastmap = re_comp_buf.fastmap;
! 622: re_comp_buf.fastmap = NULL;
! 623: __regfree (&re_comp_buf);
! 624: memset (&re_comp_buf, '\0', sizeof (re_comp_buf));
! 625: re_comp_buf.fastmap = fastmap;
! 626: }
! 627:
! 628: if (re_comp_buf.fastmap == NULL)
! 629: {
! 630: re_comp_buf.fastmap = (char *) malloc (SBC_MAX);
! 631: if (re_comp_buf.fastmap == NULL)
! 632: return (char *) gettext (__re_error_msgid
! 633: + __re_error_msgid_idx[(int) REG_ESPACE]);
! 634: }
! 635:
! 636: /* Since `re_exec' always passes NULL for the `regs' argument, we
! 637: don't need to initialize the pattern buffer fields which affect it. */
! 638:
! 639: /* Match anchors at newlines. */
! 640: re_comp_buf.newline_anchor = 1;
! 641:
! 642: ret = re_compile_internal (&re_comp_buf, s, strlen (s), re_syntax_options);
! 643:
! 644: if (!ret)
! 645: return NULL;
! 646:
! 647: /* Yes, we're discarding `const' here if !HAVE_LIBINTL. */
! 648: return (char *) gettext (__re_error_msgid + __re_error_msgid_idx[(int) ret]);
! 649: }
! 650:
! 651: #ifdef _LIBC
! 652: libc_freeres_fn (free_mem)
! 653: {
! 654: __regfree (&re_comp_buf);
! 655: }
! 656: #endif
! 657:
! 658: #endif /* _REGEX_RE_COMP */
! 659:
! 660: /* Internal entry point.
! 661: Compile the regular expression PATTERN, whose length is LENGTH.
! 662: SYNTAX indicate regular expression's syntax. */
! 663:
! 664: static reg_errcode_t
! 665: re_compile_internal (preg, pattern, length, syntax)
! 666: regex_t *preg;
! 667: const char * pattern;
! 668: int length;
! 669: reg_syntax_t syntax;
! 670: {
! 671: reg_errcode_t err = REG_NOERROR;
! 672: re_dfa_t *dfa;
! 673: re_string_t regexp;
! 674:
! 675: /* Initialize the pattern buffer. */
! 676: preg->fastmap_accurate = 0;
! 677: preg->syntax = syntax;
! 678: preg->not_bol = preg->not_eol = 0;
! 679: preg->used = 0;
! 680: preg->re_nsub = 0;
! 681: preg->can_be_null = 0;
! 682: preg->regs_allocated = REGS_UNALLOCATED;
! 683:
! 684: /* Initialize the dfa. */
! 685: dfa = (re_dfa_t *) preg->buffer;
! 686: if (preg->allocated < sizeof (re_dfa_t))
! 687: {
! 688: /* If zero allocated, but buffer is non-null, try to realloc
! 689: enough space. This loses if buffer's address is bogus, but
! 690: that is the user's responsibility. If ->buffer is NULL this
! 691: is a simple allocation. */
! 692: dfa = re_realloc (preg->buffer, re_dfa_t, 1);
! 693: if (dfa == NULL)
! 694: return REG_ESPACE;
! 695: preg->allocated = sizeof (re_dfa_t);
! 696: }
! 697: preg->buffer = (unsigned char *) dfa;
! 698: preg->used = sizeof (re_dfa_t);
! 699:
! 700: err = init_dfa (dfa, length);
! 701: if (BE (err != REG_NOERROR, 0))
! 702: {
! 703: re_free (dfa);
! 704: preg->buffer = NULL;
! 705: preg->allocated = 0;
! 706: return err;
! 707: }
! 708: #ifdef DEBUG
! 709: dfa->re_str = re_malloc (char, length + 1);
! 710: strncpy (dfa->re_str, pattern, length + 1);
! 711: #endif
! 712:
! 713: err = re_string_construct (®exp, pattern, length, preg->translate,
! 714: syntax & RE_ICASE);
! 715: if (BE (err != REG_NOERROR, 0))
! 716: {
! 717: re_free (dfa);
! 718: preg->buffer = NULL;
! 719: preg->allocated = 0;
! 720: return err;
! 721: }
! 722:
! 723: /* Parse the regular expression, and build a structure tree. */
! 724: preg->re_nsub = 0;
! 725: dfa->str_tree = parse (®exp, preg, syntax, &err);
! 726: if (BE (dfa->str_tree == NULL, 0))
! 727: goto re_compile_internal_free_return;
! 728:
! 729: /* Analyze the tree and collect information which is necessary to
! 730: create the dfa. */
! 731: err = analyze (dfa);
! 732: if (BE (err != REG_NOERROR, 0))
! 733: goto re_compile_internal_free_return;
! 734:
! 735: /* Then create the initial state of the dfa. */
! 736: err = create_initial_state (dfa);
! 737:
! 738: /* Release work areas. */
! 739: free_workarea_compile (preg);
! 740: re_string_destruct (®exp);
! 741:
! 742: if (BE (err != REG_NOERROR, 0))
! 743: {
! 744: re_compile_internal_free_return:
! 745: free_dfa_content (dfa);
! 746: preg->buffer = NULL;
! 747: preg->allocated = 0;
! 748: }
! 749:
! 750: return err;
! 751: }
! 752:
! 753: /* Initialize DFA. We use the length of the regular expression PAT_LEN
! 754: as the initial length of some arrays. */
! 755:
! 756: static reg_errcode_t
! 757: init_dfa (dfa, pat_len)
! 758: re_dfa_t *dfa;
! 759: int pat_len;
! 760: {
! 761: int table_size;
! 762:
! 763: memset (dfa, '\0', sizeof (re_dfa_t));
! 764:
! 765: dfa->nodes_alloc = pat_len + 1;
! 766: dfa->nodes = re_malloc (re_token_t, dfa->nodes_alloc);
! 767:
! 768: dfa->states_alloc = pat_len + 1;
! 769:
! 770: /* table_size = 2 ^ ceil(log pat_len) */
! 771: for (table_size = 1; table_size > 0; table_size <<= 1)
! 772: if (table_size > pat_len)
! 773: break;
! 774:
! 775: dfa->state_table = calloc (sizeof (struct re_state_table_entry), table_size);
! 776: dfa->state_hash_mask = table_size - 1;
! 777:
! 778: dfa->subexps_alloc = 1;
! 779: dfa->subexps = re_malloc (re_subexp_t, dfa->subexps_alloc);
! 780: dfa->word_char = NULL;
! 781:
! 782: if (BE (dfa->nodes == NULL || dfa->state_table == NULL
! 783: || dfa->subexps == NULL, 0))
! 784: {
! 785: /* We don't bother to free anything which was allocated. Very
! 786: soon the process will go down anyway. */
! 787: dfa->subexps = NULL;
! 788: dfa->state_table = NULL;
! 789: dfa->nodes = NULL;
! 790: return REG_ESPACE;
! 791: }
! 792: return REG_NOERROR;
! 793: }
! 794:
! 795: /* Initialize WORD_CHAR table, which indicate which character is
! 796: "word". In this case "word" means that it is the word construction
! 797: character used by some operators like "\<", "\>", etc. */
! 798:
! 799: static reg_errcode_t
! 800: init_word_char (dfa)
! 801: re_dfa_t *dfa;
! 802: {
! 803: int i, j, ch;
! 804: dfa->word_char = (re_bitset_ptr_t) calloc (sizeof (bitset), 1);
! 805: if (BE (dfa->word_char == NULL, 0))
! 806: return REG_ESPACE;
! 807: for (i = 0, ch = 0; i < BITSET_UINTS; ++i)
! 808: for (j = 0; j < UINT_BITS; ++j, ++ch)
! 809: if (isalnum (ch) || ch == '_')
! 810: dfa->word_char[i] |= 1 << j;
! 811: return REG_NOERROR;
! 812: }
! 813:
! 814: /* Free the work area which are only used while compiling. */
! 815:
! 816: static void
! 817: free_workarea_compile (preg)
! 818: regex_t *preg;
! 819: {
! 820: re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
! 821: free_bin_tree (dfa->str_tree);
! 822: dfa->str_tree = NULL;
! 823: re_free (dfa->org_indices);
! 824: dfa->org_indices = NULL;
! 825: }
! 826:
! 827: /* Create initial states for all contexts. */
! 828:
! 829: static reg_errcode_t
! 830: create_initial_state (dfa)
! 831: re_dfa_t *dfa;
! 832: {
! 833: int first, i;
! 834: reg_errcode_t err;
! 835: re_node_set init_nodes;
! 836:
! 837: /* Initial states have the epsilon closure of the node which is
! 838: the first node of the regular expression. */
! 839: first = dfa->str_tree->first;
! 840: dfa->init_node = first;
! 841: err = re_node_set_init_copy (&init_nodes, dfa->eclosures + first);
! 842: if (BE (err != REG_NOERROR, 0))
! 843: return err;
! 844:
! 845: /* The back-references which are in initial states can epsilon transit,
! 846: since in this case all of the subexpressions can be null.
! 847: Then we add epsilon closures of the nodes which are the next nodes of
! 848: the back-references. */
! 849: if (dfa->nbackref > 0)
! 850: for (i = 0; i < init_nodes.nelem; ++i)
! 851: {
! 852: int node_idx = init_nodes.elems[i];
! 853: re_token_type_t type = dfa->nodes[node_idx].type;
! 854:
! 855: int clexp_idx;
! 856: if (type != OP_BACK_REF)
! 857: continue;
! 858: for (clexp_idx = 0; clexp_idx < init_nodes.nelem; ++clexp_idx)
! 859: {
! 860: re_token_t *clexp_node;
! 861: clexp_node = dfa->nodes + init_nodes.elems[clexp_idx];
! 862: if (clexp_node->type == OP_CLOSE_SUBEXP
! 863: && clexp_node->opr.idx + 1 == dfa->nodes[node_idx].opr.idx)
! 864: break;
! 865: }
! 866: if (clexp_idx == init_nodes.nelem)
! 867: continue;
! 868:
! 869: if (type == OP_BACK_REF)
! 870: {
! 871: int dest_idx = dfa->edests[node_idx].elems[0];
! 872: if (!re_node_set_contains (&init_nodes, dest_idx))
! 873: {
! 874: re_node_set_merge (&init_nodes, dfa->eclosures + dest_idx);
! 875: i = 0;
! 876: }
! 877: }
! 878: }
! 879:
! 880: /* It must be the first time to invoke acquire_state. */
! 881: dfa->init_state = re_acquire_state_context (&err, dfa, &init_nodes, 0);
! 882: /* We don't check ERR here, since the initial state must not be NULL. */
! 883: if (BE (dfa->init_state == NULL, 0))
! 884: return err;
! 885: if (dfa->init_state->has_constraint)
! 886: {
! 887: dfa->init_state_word = re_acquire_state_context (&err, dfa, &init_nodes,
! 888: CONTEXT_WORD);
! 889: dfa->init_state_nl = re_acquire_state_context (&err, dfa, &init_nodes,
! 890: CONTEXT_NEWLINE);
! 891: dfa->init_state_begbuf = re_acquire_state_context (&err, dfa,
! 892: &init_nodes,
! 893: CONTEXT_NEWLINE
! 894: | CONTEXT_BEGBUF);
! 895: if (BE (dfa->init_state_word == NULL || dfa->init_state_nl == NULL
! 896: || dfa->init_state_begbuf == NULL, 0))
! 897: return err;
! 898: }
! 899: else
! 900: dfa->init_state_word = dfa->init_state_nl
! 901: = dfa->init_state_begbuf = dfa->init_state;
! 902:
! 903: re_node_set_free (&init_nodes);
! 904: return REG_NOERROR;
! 905: }
! 906:
! 907: /* Analyze the structure tree, and calculate "first", "next", "edest",
! 908: "eclosure", and "inveclosure". */
! 909:
! 910: static reg_errcode_t
! 911: analyze (dfa)
! 912: re_dfa_t *dfa;
! 913: {
! 914: int i;
! 915: reg_errcode_t ret;
! 916:
! 917: /* Allocate arrays. */
! 918: dfa->nexts = re_malloc (int, dfa->nodes_alloc);
! 919: dfa->org_indices = re_malloc (int, dfa->nodes_alloc);
! 920: dfa->edests = re_malloc (re_node_set, dfa->nodes_alloc);
! 921: dfa->eclosures = re_malloc (re_node_set, dfa->nodes_alloc);
! 922: dfa->inveclosures = re_malloc (re_node_set, dfa->nodes_alloc);
! 923: if (BE (dfa->nexts == NULL || dfa->org_indices == NULL || dfa->edests == NULL
! 924: || dfa->eclosures == NULL || dfa->inveclosures == NULL, 0))
! 925: return REG_ESPACE;
! 926: /* Initialize them. */
! 927: for (i = 0; i < dfa->nodes_len; ++i)
! 928: {
! 929: dfa->nexts[i] = -1;
! 930: re_node_set_init_empty (dfa->edests + i);
! 931: re_node_set_init_empty (dfa->eclosures + i);
! 932: re_node_set_init_empty (dfa->inveclosures + i);
! 933: }
! 934:
! 935: ret = analyze_tree (dfa, dfa->str_tree);
! 936: if (BE (ret == REG_NOERROR, 1))
! 937: {
! 938: ret = calc_eclosure (dfa);
! 939: if (ret == REG_NOERROR)
! 940: calc_inveclosure (dfa);
! 941: }
! 942: return ret;
! 943: }
! 944:
! 945: /* Helper functions for analyze.
! 946: This function calculate "first", "next", and "edest" for the subtree
! 947: whose root is NODE. */
! 948:
! 949: static reg_errcode_t
! 950: analyze_tree (dfa, node)
! 951: re_dfa_t *dfa;
! 952: bin_tree_t *node;
! 953: {
! 954: reg_errcode_t ret;
! 955: if (node->first == -1)
! 956: calc_first (dfa, node);
! 957: if (node->next == -1)
! 958: calc_next (dfa, node);
! 959: if (node->eclosure.nelem == 0)
! 960: calc_epsdest (dfa, node);
! 961: /* Calculate "first" etc. for the left child. */
! 962: if (node->left != NULL)
! 963: {
! 964: ret = analyze_tree (dfa, node->left);
! 965: if (BE (ret != REG_NOERROR, 0))
! 966: return ret;
! 967: }
! 968: /* Calculate "first" etc. for the right child. */
! 969: if (node->right != NULL)
! 970: {
! 971: ret = analyze_tree (dfa, node->right);
! 972: if (BE (ret != REG_NOERROR, 0))
! 973: return ret;
! 974: }
! 975: return REG_NOERROR;
! 976: }
! 977:
! 978: /* Calculate "first" for the node NODE. */
! 979: static void
! 980: calc_first (dfa, node)
! 981: re_dfa_t *dfa;
! 982: bin_tree_t *node;
! 983: {
! 984: int idx, type;
! 985: idx = node->node_idx;
! 986: type = (node->type == 0) ? dfa->nodes[idx].type : node->type;
! 987:
! 988: switch (type)
! 989: {
! 990: #ifdef DEBUG
! 991: case OP_OPEN_BRACKET:
! 992: case OP_CLOSE_BRACKET:
! 993: case OP_OPEN_DUP_NUM:
! 994: case OP_CLOSE_DUP_NUM:
! 995: case OP_NON_MATCH_LIST:
! 996: case OP_OPEN_COLL_ELEM:
! 997: case OP_CLOSE_COLL_ELEM:
! 998: case OP_OPEN_EQUIV_CLASS:
! 999: case OP_CLOSE_EQUIV_CLASS:
! 1000: case OP_OPEN_CHAR_CLASS:
! 1001: case OP_CLOSE_CHAR_CLASS:
! 1002: /* These must not be appeared here. */
! 1003: assert (0);
! 1004: #endif
! 1005: case END_OF_RE:
! 1006: case CHARACTER:
! 1007: case OP_PERIOD:
! 1008: case OP_DUP_ASTERISK:
! 1009: case OP_DUP_QUESTION:
! 1010: #ifdef RE_ENABLE_I18N
! 1011: case COMPLEX_BRACKET:
! 1012: #endif /* RE_ENABLE_I18N */
! 1013: case SIMPLE_BRACKET:
! 1014: case OP_BACK_REF:
! 1015: case ANCHOR:
! 1016: case OP_OPEN_SUBEXP:
! 1017: case OP_CLOSE_SUBEXP:
! 1018: node->first = idx;
! 1019: break;
! 1020: case OP_DUP_PLUS:
! 1021: #ifdef DEBUG
! 1022: assert (node->left != NULL);
! 1023: #endif
! 1024: if (node->left->first == -1)
! 1025: calc_first (dfa, node->left);
! 1026: node->first = node->left->first;
! 1027: break;
! 1028: case OP_ALT:
! 1029: node->first = idx;
! 1030: break;
! 1031: /* else fall through */
! 1032: default:
! 1033: #ifdef DEBUG
! 1034: assert (node->left != NULL);
! 1035: #endif
! 1036: if (node->left->first == -1)
! 1037: calc_first (dfa, node->left);
! 1038: node->first = node->left->first;
! 1039: break;
! 1040: }
! 1041: }
! 1042:
! 1043: /* Calculate "next" for the node NODE. */
! 1044:
! 1045: static void
! 1046: calc_next (dfa, node)
! 1047: re_dfa_t *dfa;
! 1048: bin_tree_t *node;
! 1049: {
! 1050: int idx, type;
! 1051: bin_tree_t *parent = node->parent;
! 1052: if (parent == NULL)
! 1053: {
! 1054: node->next = -1;
! 1055: idx = node->node_idx;
! 1056: if (node->type == 0)
! 1057: dfa->nexts[idx] = node->next;
! 1058: return;
! 1059: }
! 1060:
! 1061: idx = parent->node_idx;
! 1062: type = (parent->type == 0) ? dfa->nodes[idx].type : parent->type;
! 1063:
! 1064: switch (type)
! 1065: {
! 1066: case OP_DUP_ASTERISK:
! 1067: case OP_DUP_PLUS:
! 1068: node->next = idx;
! 1069: break;
! 1070: case CONCAT:
! 1071: if (parent->left == node)
! 1072: {
! 1073: if (parent->right->first == -1)
! 1074: calc_first (dfa, parent->right);
! 1075: node->next = parent->right->first;
! 1076: break;
! 1077: }
! 1078: /* else fall through */
! 1079: default:
! 1080: if (parent->next == -1)
! 1081: calc_next (dfa, parent);
! 1082: node->next = parent->next;
! 1083: break;
! 1084: }
! 1085: idx = node->node_idx;
! 1086: if (node->type == 0)
! 1087: dfa->nexts[idx] = node->next;
! 1088: }
! 1089:
! 1090: /* Calculate "edest" for the node NODE. */
! 1091:
! 1092: static void
! 1093: calc_epsdest (dfa, node)
! 1094: re_dfa_t *dfa;
! 1095: bin_tree_t *node;
! 1096: {
! 1097: int idx;
! 1098: idx = node->node_idx;
! 1099: if (node->type == 0)
! 1100: {
! 1101: if (dfa->nodes[idx].type == OP_DUP_ASTERISK
! 1102: || dfa->nodes[idx].type == OP_DUP_PLUS
! 1103: || dfa->nodes[idx].type == OP_DUP_QUESTION)
! 1104: {
! 1105: if (node->left->first == -1)
! 1106: calc_first (dfa, node->left);
! 1107: if (node->next == -1)
! 1108: calc_next (dfa, node);
! 1109: re_node_set_init_2 (dfa->edests + idx, node->left->first,
! 1110: node->next);
! 1111: }
! 1112: else if (dfa->nodes[idx].type == OP_ALT)
! 1113: {
! 1114: int left, right;
! 1115: if (node->left != NULL)
! 1116: {
! 1117: if (node->left->first == -1)
! 1118: calc_first (dfa, node->left);
! 1119: left = node->left->first;
! 1120: }
! 1121: else
! 1122: {
! 1123: if (node->next == -1)
! 1124: calc_next (dfa, node);
! 1125: left = node->next;
! 1126: }
! 1127: if (node->right != NULL)
! 1128: {
! 1129: if (node->right->first == -1)
! 1130: calc_first (dfa, node->right);
! 1131: right = node->right->first;
! 1132: }
! 1133: else
! 1134: {
! 1135: if (node->next == -1)
! 1136: calc_next (dfa, node);
! 1137: right = node->next;
! 1138: }
! 1139: re_node_set_init_2 (dfa->edests + idx, left, right);
! 1140: }
! 1141: else if (dfa->nodes[idx].type == ANCHOR
! 1142: || dfa->nodes[idx].type == OP_OPEN_SUBEXP
! 1143: || dfa->nodes[idx].type == OP_CLOSE_SUBEXP
! 1144: || dfa->nodes[idx].type == OP_BACK_REF)
! 1145: re_node_set_init_1 (dfa->edests + idx, node->next);
! 1146: }
! 1147: }
! 1148:
! 1149: /* Duplicate the epsilon closure of the node ROOT_NODE.
! 1150: Note that duplicated nodes have constraint INIT_CONSTRAINT in addition
! 1151: to their own constraint. */
! 1152:
! 1153: static reg_errcode_t
! 1154: duplicate_node_closure (dfa, top_org_node, top_clone_node, root_node,
! 1155: init_constraint)
! 1156: re_dfa_t *dfa;
! 1157: int top_org_node, top_clone_node, root_node;
! 1158: unsigned int init_constraint;
! 1159: {
! 1160: reg_errcode_t err;
! 1161: int org_node, clone_node, ret;
! 1162: unsigned int constraint = init_constraint;
! 1163: for (org_node = top_org_node, clone_node = top_clone_node;;)
! 1164: {
! 1165: int org_dest, clone_dest;
! 1166: if (dfa->nodes[org_node].type == OP_BACK_REF)
! 1167: {
! 1168: /* If the back reference epsilon-transit, its destination must
! 1169: also have the constraint. Then duplicate the epsilon closure
! 1170: of the destination of the back reference, and store it in
! 1171: edests of the back reference. */
! 1172: org_dest = dfa->nexts[org_node];
! 1173: re_node_set_empty (dfa->edests + clone_node);
! 1174: err = duplicate_node (&clone_dest, dfa, org_dest, constraint);
! 1175: if (BE (err != REG_NOERROR, 0))
! 1176: return err;
! 1177: dfa->nexts[clone_node] = dfa->nexts[org_node];
! 1178: ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
! 1179: if (BE (ret < 0, 0))
! 1180: return REG_ESPACE;
! 1181: }
! 1182: else if (dfa->edests[org_node].nelem == 0)
! 1183: {
! 1184: /* In case of the node can't epsilon-transit, don't duplicate the
! 1185: destination and store the original destination as the
! 1186: destination of the node. */
! 1187: dfa->nexts[clone_node] = dfa->nexts[org_node];
! 1188: break;
! 1189: }
! 1190: else if (dfa->edests[org_node].nelem == 1)
! 1191: {
! 1192: /* In case of the node can epsilon-transit, and it has only one
! 1193: destination. */
! 1194: org_dest = dfa->edests[org_node].elems[0];
! 1195: re_node_set_empty (dfa->edests + clone_node);
! 1196: if (dfa->nodes[org_node].type == ANCHOR)
! 1197: {
! 1198: /* In case of the node has another constraint, append it. */
! 1199: if (org_node == root_node && clone_node != org_node)
! 1200: {
! 1201: /* ...but if the node is root_node itself, it means the
! 1202: epsilon closure have a loop, then tie it to the
! 1203: destination of the root_node. */
! 1204: ret = re_node_set_insert (dfa->edests + clone_node,
! 1205: org_dest);
! 1206: if (BE (ret < 0, 0))
! 1207: return REG_ESPACE;
! 1208: break;
! 1209: }
! 1210: constraint |= dfa->nodes[org_node].opr.ctx_type;
! 1211: }
! 1212: err = duplicate_node (&clone_dest, dfa, org_dest, constraint);
! 1213: if (BE (err != REG_NOERROR, 0))
! 1214: return err;
! 1215: ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
! 1216: if (BE (ret < 0, 0))
! 1217: return REG_ESPACE;
! 1218: }
! 1219: else /* dfa->edests[org_node].nelem == 2 */
! 1220: {
! 1221: /* In case of the node can epsilon-transit, and it has two
! 1222: destinations. E.g. '|', '*', '+', '?'. */
! 1223: org_dest = dfa->edests[org_node].elems[0];
! 1224: re_node_set_empty (dfa->edests + clone_node);
! 1225: /* Search for a duplicated node which satisfies the constraint. */
! 1226: clone_dest = search_duplicated_node (dfa, org_dest, constraint);
! 1227: if (clone_dest == -1)
! 1228: {
! 1229: /* There are no such a duplicated node, create a new one. */
! 1230: err = duplicate_node (&clone_dest, dfa, org_dest, constraint);
! 1231: if (BE (err != REG_NOERROR, 0))
! 1232: return err;
! 1233: ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
! 1234: if (BE (ret < 0, 0))
! 1235: return REG_ESPACE;
! 1236: err = duplicate_node_closure (dfa, org_dest, clone_dest,
! 1237: root_node, constraint);
! 1238: if (BE (err != REG_NOERROR, 0))
! 1239: return err;
! 1240: }
! 1241: else
! 1242: {
! 1243: /* There are a duplicated node which satisfy the constraint,
! 1244: use it to avoid infinite loop. */
! 1245: ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
! 1246: if (BE (ret < 0, 0))
! 1247: return REG_ESPACE;
! 1248: }
! 1249:
! 1250: org_dest = dfa->edests[org_node].elems[1];
! 1251: err = duplicate_node (&clone_dest, dfa, org_dest, constraint);
! 1252: if (BE (err != REG_NOERROR, 0))
! 1253: return err;
! 1254: ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
! 1255: if (BE (ret < 0, 0))
! 1256: return REG_ESPACE;
! 1257: }
! 1258: org_node = org_dest;
! 1259: clone_node = clone_dest;
! 1260: }
! 1261: return REG_NOERROR;
! 1262: }
! 1263:
! 1264: /* Search for a node which is duplicated from the node ORG_NODE, and
! 1265: satisfies the constraint CONSTRAINT. */
! 1266:
! 1267: static int
! 1268: search_duplicated_node (dfa, org_node, constraint)
! 1269: re_dfa_t *dfa;
! 1270: int org_node;
! 1271: unsigned int constraint;
! 1272: {
! 1273: int idx;
! 1274: for (idx = dfa->nodes_len - 1; dfa->nodes[idx].duplicated && idx > 0; --idx)
! 1275: {
! 1276: if (org_node == dfa->org_indices[idx]
! 1277: && constraint == dfa->nodes[idx].constraint)
! 1278: return idx; /* Found. */
! 1279: }
! 1280: return -1; /* Not found. */
! 1281: }
! 1282:
! 1283: /* Duplicate the node whose index is ORG_IDX and set the constraint CONSTRAINT.
! 1284: The new index will be stored in NEW_IDX and return REG_NOERROR if succeeded,
! 1285: otherwise return the error code. */
! 1286:
! 1287: static reg_errcode_t
! 1288: duplicate_node (new_idx, dfa, org_idx, constraint)
! 1289: re_dfa_t *dfa;
! 1290: int *new_idx, org_idx;
! 1291: unsigned int constraint;
! 1292: {
! 1293: re_token_t dup;
! 1294: int dup_idx;
! 1295:
! 1296: dup = dfa->nodes[org_idx];
! 1297: dup_idx = re_dfa_add_node (dfa, dup, 1);
! 1298: if (BE (dup_idx == -1, 0))
! 1299: return REG_ESPACE;
! 1300: dfa->nodes[dup_idx].constraint = constraint;
! 1301: if (dfa->nodes[org_idx].type == ANCHOR)
! 1302: dfa->nodes[dup_idx].constraint |= dfa->nodes[org_idx].opr.ctx_type;
! 1303: dfa->nodes[dup_idx].duplicated = 1;
! 1304: re_node_set_init_empty (dfa->edests + dup_idx);
! 1305: re_node_set_init_empty (dfa->eclosures + dup_idx);
! 1306: re_node_set_init_empty (dfa->inveclosures + dup_idx);
! 1307:
! 1308: /* Store the index of the original node. */
! 1309: dfa->org_indices[dup_idx] = org_idx;
! 1310: *new_idx = dup_idx;
! 1311: return REG_NOERROR;
! 1312: }
! 1313:
! 1314: static void
! 1315: calc_inveclosure (dfa)
! 1316: re_dfa_t *dfa;
! 1317: {
! 1318: int src, idx, dest;
! 1319: for (src = 0; src < dfa->nodes_len; ++src)
! 1320: {
! 1321: for (idx = 0; idx < dfa->eclosures[src].nelem; ++idx)
! 1322: {
! 1323: dest = dfa->eclosures[src].elems[idx];
! 1324: re_node_set_insert (dfa->inveclosures + dest, src);
! 1325: }
! 1326: }
! 1327: }
! 1328:
! 1329: /* Calculate "eclosure" for all the node in DFA. */
! 1330:
! 1331: static reg_errcode_t
! 1332: calc_eclosure (dfa)
! 1333: re_dfa_t *dfa;
! 1334: {
! 1335: int node_idx, incomplete;
! 1336: #ifdef DEBUG
! 1337: assert (dfa->nodes_len > 0);
! 1338: #endif
! 1339: incomplete = 0;
! 1340: /* For each nodes, calculate epsilon closure. */
! 1341: for (node_idx = 0; ; ++node_idx)
! 1342: {
! 1343: reg_errcode_t err;
! 1344: re_node_set eclosure_elem;
! 1345: if (node_idx == dfa->nodes_len)
! 1346: {
! 1347: if (!incomplete)
! 1348: break;
! 1349: incomplete = 0;
! 1350: node_idx = 0;
! 1351: }
! 1352:
! 1353: #ifdef DEBUG
! 1354: assert (dfa->eclosures[node_idx].nelem != -1);
! 1355: #endif
! 1356: /* If we have already calculated, skip it. */
! 1357: if (dfa->eclosures[node_idx].nelem != 0)
! 1358: continue;
! 1359: /* Calculate epsilon closure of `node_idx'. */
! 1360: err = calc_eclosure_iter (&eclosure_elem, dfa, node_idx, 1);
! 1361: if (BE (err != REG_NOERROR, 0))
! 1362: return err;
! 1363:
! 1364: if (dfa->eclosures[node_idx].nelem == 0)
! 1365: {
! 1366: incomplete = 1;
! 1367: re_node_set_free (&eclosure_elem);
! 1368: }
! 1369: }
! 1370: return REG_NOERROR;
! 1371: }
! 1372:
! 1373: /* Calculate epsilon closure of NODE. */
! 1374:
! 1375: static reg_errcode_t
! 1376: calc_eclosure_iter (new_set, dfa, node, root)
! 1377: re_node_set *new_set;
! 1378: re_dfa_t *dfa;
! 1379: int node, root;
! 1380: {
! 1381: reg_errcode_t err;
! 1382: unsigned int constraint;
! 1383: int i, incomplete;
! 1384: re_node_set eclosure;
! 1385: incomplete = 0;
! 1386: err = re_node_set_alloc (&eclosure, dfa->edests[node].nelem + 1);
! 1387: if (BE (err != REG_NOERROR, 0))
! 1388: return err;
! 1389:
! 1390: /* This indicates that we are calculating this node now.
! 1391: We reference this value to avoid infinite loop. */
! 1392: dfa->eclosures[node].nelem = -1;
! 1393:
! 1394: constraint = ((dfa->nodes[node].type == ANCHOR)
! 1395: ? dfa->nodes[node].opr.ctx_type : 0);
! 1396: /* If the current node has constraints, duplicate all nodes.
! 1397: Since they must inherit the constraints. */
! 1398: if (constraint && !dfa->nodes[dfa->edests[node].elems[0]].duplicated)
! 1399: {
! 1400: int org_node, cur_node;
! 1401: org_node = cur_node = node;
! 1402: err = duplicate_node_closure (dfa, node, node, node, constraint);
! 1403: if (BE (err != REG_NOERROR, 0))
! 1404: return err;
! 1405: }
! 1406:
! 1407: /* Expand each epsilon destination nodes. */
! 1408: if (IS_EPSILON_NODE(dfa->nodes[node].type))
! 1409: for (i = 0; i < dfa->edests[node].nelem; ++i)
! 1410: {
! 1411: re_node_set eclosure_elem;
! 1412: int edest = dfa->edests[node].elems[i];
! 1413: /* If calculating the epsilon closure of `edest' is in progress,
! 1414: return intermediate result. */
! 1415: if (dfa->eclosures[edest].nelem == -1)
! 1416: {
! 1417: incomplete = 1;
! 1418: continue;
! 1419: }
! 1420: /* If we haven't calculated the epsilon closure of `edest' yet,
! 1421: calculate now. Otherwise use calculated epsilon closure. */
! 1422: if (dfa->eclosures[edest].nelem == 0)
! 1423: {
! 1424: err = calc_eclosure_iter (&eclosure_elem, dfa, edest, 0);
! 1425: if (BE (err != REG_NOERROR, 0))
! 1426: return err;
! 1427: }
! 1428: else
! 1429: eclosure_elem = dfa->eclosures[edest];
! 1430: /* Merge the epsilon closure of `edest'. */
! 1431: re_node_set_merge (&eclosure, &eclosure_elem);
! 1432: /* If the epsilon closure of `edest' is incomplete,
! 1433: the epsilon closure of this node is also incomplete. */
! 1434: if (dfa->eclosures[edest].nelem == 0)
! 1435: {
! 1436: incomplete = 1;
! 1437: re_node_set_free (&eclosure_elem);
! 1438: }
! 1439: }
! 1440:
! 1441: /* Epsilon closures include itself. */
! 1442: re_node_set_insert (&eclosure, node);
! 1443: if (incomplete && !root)
! 1444: dfa->eclosures[node].nelem = 0;
! 1445: else
! 1446: dfa->eclosures[node] = eclosure;
! 1447: *new_set = eclosure;
! 1448: return REG_NOERROR;
! 1449: }
! 1450:
! 1451: /* Functions for token which are used in the parser. */
! 1452:
! 1453: /* Fetch a token from INPUT.
! 1454: We must not use this function inside bracket expressions. */
! 1455:
! 1456: static re_token_t
! 1457: fetch_token (input, syntax)
! 1458: re_string_t *input;
! 1459: reg_syntax_t syntax;
! 1460: {
! 1461: re_token_t token;
! 1462: int consumed_byte;
! 1463: consumed_byte = peek_token (&token, input, syntax);
! 1464: re_string_skip_bytes (input, consumed_byte);
! 1465: return token;
! 1466: }
! 1467:
! 1468: /* Peek a token from INPUT, and return the length of the token.
! 1469: We must not use this function inside bracket expressions. */
! 1470:
! 1471: static int
! 1472: peek_token (token, input, syntax)
! 1473: re_token_t *token;
! 1474: re_string_t *input;
! 1475: reg_syntax_t syntax;
! 1476: {
! 1477: unsigned char c;
! 1478:
! 1479: if (re_string_eoi (input))
! 1480: {
! 1481: token->type = END_OF_RE;
! 1482: return 0;
! 1483: }
! 1484:
! 1485: c = re_string_peek_byte (input, 0);
! 1486: token->opr.c = c;
! 1487:
! 1488: #ifdef RE_ENABLE_I18N
! 1489: token->mb_partial = 0;
! 1490: if (MB_CUR_MAX > 1 &&
! 1491: !re_string_first_byte (input, re_string_cur_idx (input)))
! 1492: {
! 1493: token->type = CHARACTER;
! 1494: token->mb_partial = 1;
! 1495: return 1;
! 1496: }
! 1497: #endif
! 1498: if (c == '\\')
! 1499: {
! 1500: unsigned char c2;
! 1501: if (re_string_cur_idx (input) + 1 >= re_string_length (input))
! 1502: {
! 1503: token->type = BACK_SLASH;
! 1504: return 1;
! 1505: }
! 1506:
! 1507: c2 = re_string_peek_byte_case (input, 1);
! 1508: token->opr.c = c2;
! 1509: token->type = CHARACTER;
! 1510: switch (c2)
! 1511: {
! 1512: case '|':
! 1513: if (!(syntax & RE_LIMITED_OPS) && !(syntax & RE_NO_BK_VBAR))
! 1514: token->type = OP_ALT;
! 1515: break;
! 1516: case '1': case '2': case '3': case '4': case '5':
! 1517: case '6': case '7': case '8': case '9':
! 1518: if (!(syntax & RE_NO_BK_REFS))
! 1519: {
! 1520: token->type = OP_BACK_REF;
! 1521: token->opr.idx = c2 - '0';
! 1522: }
! 1523: break;
! 1524: case '<':
! 1525: if (!(syntax & RE_NO_GNU_OPS))
! 1526: {
! 1527: token->type = ANCHOR;
! 1528: token->opr.idx = WORD_FIRST;
! 1529: }
! 1530: break;
! 1531: case '>':
! 1532: if (!(syntax & RE_NO_GNU_OPS))
! 1533: {
! 1534: token->type = ANCHOR;
! 1535: token->opr.idx = WORD_LAST;
! 1536: }
! 1537: break;
! 1538: case 'b':
! 1539: if (!(syntax & RE_NO_GNU_OPS))
! 1540: {
! 1541: token->type = ANCHOR;
! 1542: token->opr.idx = WORD_DELIM;
! 1543: }
! 1544: break;
! 1545: case 'B':
! 1546: if (!(syntax & RE_NO_GNU_OPS))
! 1547: {
! 1548: token->type = ANCHOR;
! 1549: token->opr.idx = INSIDE_WORD;
! 1550: }
! 1551: break;
! 1552: case 'w':
! 1553: if (!(syntax & RE_NO_GNU_OPS))
! 1554: token->type = OP_WORD;
! 1555: break;
! 1556: case 'W':
! 1557: if (!(syntax & RE_NO_GNU_OPS))
! 1558: token->type = OP_NOTWORD;
! 1559: break;
! 1560: case '`':
! 1561: if (!(syntax & RE_NO_GNU_OPS))
! 1562: {
! 1563: token->type = ANCHOR;
! 1564: token->opr.idx = BUF_FIRST;
! 1565: }
! 1566: break;
! 1567: case '\'':
! 1568: if (!(syntax & RE_NO_GNU_OPS))
! 1569: {
! 1570: token->type = ANCHOR;
! 1571: token->opr.idx = BUF_LAST;
! 1572: }
! 1573: break;
! 1574: case '(':
! 1575: if (!(syntax & RE_NO_BK_PARENS))
! 1576: token->type = OP_OPEN_SUBEXP;
! 1577: break;
! 1578: case ')':
! 1579: if (!(syntax & RE_NO_BK_PARENS))
! 1580: token->type = OP_CLOSE_SUBEXP;
! 1581: break;
! 1582: case '+':
! 1583: if (!(syntax & RE_LIMITED_OPS) && (syntax & RE_BK_PLUS_QM))
! 1584: token->type = OP_DUP_PLUS;
! 1585: break;
! 1586: case '?':
! 1587: if (!(syntax & RE_LIMITED_OPS) && (syntax & RE_BK_PLUS_QM))
! 1588: token->type = OP_DUP_QUESTION;
! 1589: break;
! 1590: case '{':
! 1591: if ((syntax & RE_INTERVALS) && (!(syntax & RE_NO_BK_BRACES)))
! 1592: token->type = OP_OPEN_DUP_NUM;
! 1593: break;
! 1594: case '}':
! 1595: if ((syntax & RE_INTERVALS) && (!(syntax & RE_NO_BK_BRACES)))
! 1596: token->type = OP_CLOSE_DUP_NUM;
! 1597: break;
! 1598: default:
! 1599: break;
! 1600: }
! 1601: return 2;
! 1602: }
! 1603:
! 1604: token->type = CHARACTER;
! 1605: switch (c)
! 1606: {
! 1607: case '\n':
! 1608: if (syntax & RE_NEWLINE_ALT)
! 1609: token->type = OP_ALT;
! 1610: break;
! 1611: case '|':
! 1612: if (!(syntax & RE_LIMITED_OPS) && (syntax & RE_NO_BK_VBAR))
! 1613: token->type = OP_ALT;
! 1614: break;
! 1615: case '*':
! 1616: token->type = OP_DUP_ASTERISK;
! 1617: break;
! 1618: case '+':
! 1619: if (!(syntax & RE_LIMITED_OPS) && !(syntax & RE_BK_PLUS_QM))
! 1620: token->type = OP_DUP_PLUS;
! 1621: break;
! 1622: case '?':
! 1623: if (!(syntax & RE_LIMITED_OPS) && !(syntax & RE_BK_PLUS_QM))
! 1624: token->type = OP_DUP_QUESTION;
! 1625: break;
! 1626: case '{':
! 1627: if ((syntax & RE_INTERVALS) && (syntax & RE_NO_BK_BRACES))
! 1628: token->type = OP_OPEN_DUP_NUM;
! 1629: break;
! 1630: case '}':
! 1631: if ((syntax & RE_INTERVALS) && (syntax & RE_NO_BK_BRACES))
! 1632: token->type = OP_CLOSE_DUP_NUM;
! 1633: break;
! 1634: case '(':
! 1635: if (syntax & RE_NO_BK_PARENS)
! 1636: token->type = OP_OPEN_SUBEXP;
! 1637: break;
! 1638: case ')':
! 1639: if (syntax & RE_NO_BK_PARENS)
! 1640: token->type = OP_CLOSE_SUBEXP;
! 1641: break;
! 1642: case '[':
! 1643: token->type = OP_OPEN_BRACKET;
! 1644: break;
! 1645: case '.':
! 1646: token->type = OP_PERIOD;
! 1647: break;
! 1648: case '^':
! 1649: if (!(syntax & RE_CONTEXT_INDEP_ANCHORS) &&
! 1650: re_string_cur_idx (input) != 0)
! 1651: {
! 1652: char prev = re_string_peek_byte (input, -1);
! 1653: if (prev != '|' && prev != '(' &&
! 1654: (!(syntax & RE_NEWLINE_ALT) || prev != '\n'))
! 1655: break;
! 1656: }
! 1657: token->type = ANCHOR;
! 1658: token->opr.idx = LINE_FIRST;
! 1659: break;
! 1660: case '$':
! 1661: if (!(syntax & RE_CONTEXT_INDEP_ANCHORS) &&
! 1662: re_string_cur_idx (input) + 1 != re_string_length (input))
! 1663: {
! 1664: re_token_t next;
! 1665: re_string_skip_bytes (input, 1);
! 1666: peek_token (&next, input, syntax);
! 1667: re_string_skip_bytes (input, -1);
! 1668: if (next.type != OP_ALT && next.type != OP_CLOSE_SUBEXP)
! 1669: break;
! 1670: }
! 1671: token->type = ANCHOR;
! 1672: token->opr.idx = LINE_LAST;
! 1673: break;
! 1674: default:
! 1675: break;
! 1676: }
! 1677: return 1;
! 1678: }
! 1679:
! 1680: /* Peek a token from INPUT, and return the length of the token.
! 1681: We must not use this function out of bracket expressions. */
! 1682:
! 1683: static int
! 1684: peek_token_bracket (token, input, syntax)
! 1685: re_token_t *token;
! 1686: re_string_t *input;
! 1687: reg_syntax_t syntax;
! 1688: {
! 1689: unsigned char c;
! 1690: if (re_string_eoi (input))
! 1691: {
! 1692: token->type = END_OF_RE;
! 1693: return 0;
! 1694: }
! 1695: c = re_string_peek_byte (input, 0);
! 1696: token->opr.c = c;
! 1697:
! 1698: #ifdef RE_ENABLE_I18N
! 1699: if (MB_CUR_MAX > 1 &&
! 1700: !re_string_first_byte (input, re_string_cur_idx (input)))
! 1701: {
! 1702: token->type = CHARACTER;
! 1703: return 1;
! 1704: }
! 1705: #endif /* RE_ENABLE_I18N */
! 1706:
! 1707: if (c == '\\' && (syntax & RE_BACKSLASH_ESCAPE_IN_LISTS))
! 1708: {
! 1709: /* In this case, '\' escape a character. */
! 1710: unsigned char c2;
! 1711: re_string_skip_bytes (input, 1);
! 1712: c2 = re_string_peek_byte (input, 0);
! 1713: token->opr.c = c2;
! 1714: token->type = CHARACTER;
! 1715: return 1;
! 1716: }
! 1717: if (c == '[') /* '[' is a special char in a bracket exps. */
! 1718: {
! 1719: unsigned char c2;
! 1720: int token_len;
! 1721: c2 = re_string_peek_byte (input, 1);
! 1722: token->opr.c = c2;
! 1723: token_len = 2;
! 1724: switch (c2)
! 1725: {
! 1726: case '.':
! 1727: token->type = OP_OPEN_COLL_ELEM;
! 1728: break;
! 1729: case '=':
! 1730: token->type = OP_OPEN_EQUIV_CLASS;
! 1731: break;
! 1732: case ':':
! 1733: if (syntax & RE_CHAR_CLASSES)
! 1734: {
! 1735: token->type = OP_OPEN_CHAR_CLASS;
! 1736: break;
! 1737: }
! 1738: /* else fall through. */
! 1739: default:
! 1740: token->type = CHARACTER;
! 1741: token->opr.c = c;
! 1742: token_len = 1;
! 1743: break;
! 1744: }
! 1745: return token_len;
! 1746: }
! 1747: switch (c)
! 1748: {
! 1749: case '-':
! 1750: token->type = OP_CHARSET_RANGE;
! 1751: break;
! 1752: case ']':
! 1753: token->type = OP_CLOSE_BRACKET;
! 1754: break;
! 1755: case '^':
! 1756: token->type = OP_NON_MATCH_LIST;
! 1757: break;
! 1758: default:
! 1759: token->type = CHARACTER;
! 1760: }
! 1761: return 1;
! 1762: }
! 1763:
! 1764: /* Functions for parser. */
! 1765:
! 1766: /* Entry point of the parser.
! 1767: Parse the regular expression REGEXP and return the structure tree.
! 1768: If an error is occured, ERR is set by error code, and return NULL.
! 1769: This function build the following tree, from regular expression <reg_exp>:
! 1770: CAT
! 1771: / \
! 1772: / \
! 1773: <reg_exp> EOR
! 1774:
! 1775: CAT means concatenation.
! 1776: EOR means end of regular expression. */
! 1777:
! 1778: static bin_tree_t *
! 1779: parse (regexp, preg, syntax, err)
! 1780: re_string_t *regexp;
! 1781: regex_t *preg;
! 1782: reg_syntax_t syntax;
! 1783: reg_errcode_t *err;
! 1784: {
! 1785: re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
! 1786: bin_tree_t *tree, *eor, *root;
! 1787: re_token_t current_token;
! 1788: int new_idx;
! 1789: current_token = fetch_token (regexp, syntax);
! 1790: tree = parse_reg_exp (regexp, preg, ¤t_token, syntax, 0, err);
! 1791: if (BE (*err != REG_NOERROR && tree == NULL, 0))
! 1792: return NULL;
! 1793: new_idx = re_dfa_add_node (dfa, current_token, 0);
! 1794: eor = create_tree (NULL, NULL, 0, new_idx);
! 1795: if (tree != NULL)
! 1796: root = create_tree (tree, eor, CONCAT, 0);
! 1797: else
! 1798: root = eor;
! 1799: if (BE (new_idx == -1 || eor == NULL || root == NULL, 0))
! 1800: {
! 1801: *err = REG_ESPACE;
! 1802: return NULL;
! 1803: }
! 1804: return root;
! 1805: }
! 1806:
! 1807: /* This function build the following tree, from regular expression
! 1808: <branch1>|<branch2>:
! 1809: ALT
! 1810: / \
! 1811: / \
! 1812: <branch1> <branch2>
! 1813:
! 1814: ALT means alternative, which represents the operator `|'. */
! 1815:
! 1816: static bin_tree_t *
! 1817: parse_reg_exp (regexp, preg, token, syntax, nest, err)
! 1818: re_string_t *regexp;
! 1819: regex_t *preg;
! 1820: re_token_t *token;
! 1821: reg_syntax_t syntax;
! 1822: int nest;
! 1823: reg_errcode_t *err;
! 1824: {
! 1825: re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
! 1826: bin_tree_t *tree, *branch = NULL;
! 1827: int new_idx;
! 1828: tree = parse_branch (regexp, preg, token, syntax, nest, err);
! 1829: if (BE (*err != REG_NOERROR && tree == NULL, 0))
! 1830: return NULL;
! 1831:
! 1832: while (token->type == OP_ALT)
! 1833: {
! 1834: re_token_t alt_token = *token;
! 1835: new_idx = re_dfa_add_node (dfa, alt_token, 0);
! 1836: *token = fetch_token (regexp, syntax);
! 1837: if (token->type != OP_ALT && token->type != END_OF_RE
! 1838: && (nest == 0 || token->type != OP_CLOSE_SUBEXP))
! 1839: {
! 1840: branch = parse_branch (regexp, preg, token, syntax, nest, err);
! 1841: if (BE (*err != REG_NOERROR && branch == NULL, 0))
! 1842: {
! 1843: free_bin_tree (tree);
! 1844: return NULL;
! 1845: }
! 1846: }
! 1847: else
! 1848: branch = NULL;
! 1849: tree = create_tree (tree, branch, 0, new_idx);
! 1850: if (BE (new_idx == -1 || tree == NULL, 0))
! 1851: {
! 1852: *err = REG_ESPACE;
! 1853: return NULL;
! 1854: }
! 1855: dfa->has_plural_match = 1;
! 1856: }
! 1857: return tree;
! 1858: }
! 1859:
! 1860: /* This function build the following tree, from regular expression
! 1861: <exp1><exp2>:
! 1862: CAT
! 1863: / \
! 1864: / \
! 1865: <exp1> <exp2>
! 1866:
! 1867: CAT means concatenation. */
! 1868:
! 1869: static bin_tree_t *
! 1870: parse_branch (regexp, preg, token, syntax, nest, err)
! 1871: re_string_t *regexp;
! 1872: regex_t *preg;
! 1873: re_token_t *token;
! 1874: reg_syntax_t syntax;
! 1875: int nest;
! 1876: reg_errcode_t *err;
! 1877: {
! 1878: bin_tree_t *tree, *exp;
! 1879: tree = parse_expression (regexp, preg, token, syntax, nest, err);
! 1880: if (BE (*err != REG_NOERROR && tree == NULL, 0))
! 1881: return NULL;
! 1882:
! 1883: while (token->type != OP_ALT && token->type != END_OF_RE
! 1884: && (nest == 0 || token->type != OP_CLOSE_SUBEXP))
! 1885: {
! 1886: exp = parse_expression (regexp, preg, token, syntax, nest, err);
! 1887: if (BE (*err != REG_NOERROR && exp == NULL, 0))
! 1888: {
! 1889: free_bin_tree (tree);
! 1890: return NULL;
! 1891: }
! 1892: if (tree != NULL && exp != NULL)
! 1893: {
! 1894: tree = create_tree (tree, exp, CONCAT, 0);
! 1895: if (tree == NULL)
! 1896: {
! 1897: *err = REG_ESPACE;
! 1898: return NULL;
! 1899: }
! 1900: }
! 1901: else if (tree == NULL)
! 1902: tree = exp;
! 1903: /* Otherwise exp == NULL, we don't need to create new tree. */
! 1904: }
! 1905: return tree;
! 1906: }
! 1907:
! 1908: /* This function build the following tree, from regular expression a*:
! 1909: *
! 1910: |
! 1911: a
! 1912: */
! 1913:
! 1914: static bin_tree_t *
! 1915: parse_expression (regexp, preg, token, syntax, nest, err)
! 1916: re_string_t *regexp;
! 1917: regex_t *preg;
! 1918: re_token_t *token;
! 1919: reg_syntax_t syntax;
! 1920: int nest;
! 1921: reg_errcode_t *err;
! 1922: {
! 1923: re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
! 1924: bin_tree_t *tree;
! 1925: int new_idx;
! 1926: switch (token->type)
! 1927: {
! 1928: case CHARACTER:
! 1929: new_idx = re_dfa_add_node (dfa, *token, 0);
! 1930: tree = create_tree (NULL, NULL, 0, new_idx);
! 1931: if (BE (new_idx == -1 || tree == NULL, 0))
! 1932: {
! 1933: *err = REG_ESPACE;
! 1934: return NULL;
! 1935: }
! 1936: #ifdef RE_ENABLE_I18N
! 1937: if (MB_CUR_MAX > 1)
! 1938: {
! 1939: while (!re_string_eoi (regexp)
! 1940: && !re_string_first_byte (regexp, re_string_cur_idx (regexp)))
! 1941: {
! 1942: bin_tree_t *mbc_remain;
! 1943: *token = fetch_token (regexp, syntax);
! 1944: new_idx = re_dfa_add_node (dfa, *token, 0);
! 1945: mbc_remain = create_tree (NULL, NULL, 0, new_idx);
! 1946: tree = create_tree (tree, mbc_remain, CONCAT, 0);
! 1947: if (BE (new_idx == -1 || mbc_remain == NULL || tree == NULL, 0))
! 1948: {
! 1949: *err = REG_ESPACE;
! 1950: return NULL;
! 1951: }
! 1952: }
! 1953: }
! 1954: #endif
! 1955: break;
! 1956: case OP_OPEN_SUBEXP:
! 1957: tree = parse_sub_exp (regexp, preg, token, syntax, nest + 1, err);
! 1958: if (BE (*err != REG_NOERROR && tree == NULL, 0))
! 1959: return NULL;
! 1960: break;
! 1961: case OP_OPEN_BRACKET:
! 1962: tree = parse_bracket_exp (regexp, dfa, token, syntax, err);
! 1963: if (BE (*err != REG_NOERROR && tree == NULL, 0))
! 1964: return NULL;
! 1965: break;
! 1966: case OP_BACK_REF:
! 1967: if (BE (preg->re_nsub < token->opr.idx
! 1968: || dfa->subexps[token->opr.idx - 1].end == -1, 0))
! 1969: {
! 1970: *err = REG_ESUBREG;
! 1971: return NULL;
! 1972: }
! 1973: dfa->used_bkref_map |= 1 << (token->opr.idx - 1);
! 1974: new_idx = re_dfa_add_node (dfa, *token, 0);
! 1975: tree = create_tree (NULL, NULL, 0, new_idx);
! 1976: if (BE (new_idx == -1 || tree == NULL, 0))
! 1977: {
! 1978: *err = REG_ESPACE;
! 1979: return NULL;
! 1980: }
! 1981: ++dfa->nbackref;
! 1982: dfa->has_mb_node = 1;
! 1983: break;
! 1984: case OP_DUP_ASTERISK:
! 1985: case OP_DUP_PLUS:
! 1986: case OP_DUP_QUESTION:
! 1987: case OP_OPEN_DUP_NUM:
! 1988: if (syntax & RE_CONTEXT_INVALID_OPS)
! 1989: {
! 1990: *err = REG_BADRPT;
! 1991: return NULL;
! 1992: }
! 1993: else if (syntax & RE_CONTEXT_INDEP_OPS)
! 1994: {
! 1995: *token = fetch_token (regexp, syntax);
! 1996: return parse_expression (regexp, preg, token, syntax, nest, err);
! 1997: }
! 1998: /* else fall through */
! 1999: case OP_CLOSE_SUBEXP:
! 2000: if ((token->type == OP_CLOSE_SUBEXP) &&
! 2001: !(syntax & RE_UNMATCHED_RIGHT_PAREN_ORD))
! 2002: {
! 2003: *err = REG_ERPAREN;
! 2004: return NULL;
! 2005: }
! 2006: /* else fall through */
! 2007: case OP_CLOSE_DUP_NUM:
! 2008: /* We treat it as a normal character. */
! 2009:
! 2010: /* Then we can these characters as normal characters. */
! 2011: token->type = CHARACTER;
! 2012: new_idx = re_dfa_add_node (dfa, *token, 0);
! 2013: tree = create_tree (NULL, NULL, 0, new_idx);
! 2014: if (BE (new_idx == -1 || tree == NULL, 0))
! 2015: {
! 2016: *err = REG_ESPACE;
! 2017: return NULL;
! 2018: }
! 2019: break;
! 2020: case ANCHOR:
! 2021: if (dfa->word_char == NULL)
! 2022: {
! 2023: *err = init_word_char (dfa);
! 2024: if (BE (*err != REG_NOERROR, 0))
! 2025: return NULL;
! 2026: }
! 2027: if (token->opr.ctx_type == WORD_DELIM)
! 2028: {
! 2029: bin_tree_t *tree_first, *tree_last;
! 2030: int idx_first, idx_last;
! 2031: token->opr.ctx_type = WORD_FIRST;
! 2032: idx_first = re_dfa_add_node (dfa, *token, 0);
! 2033: tree_first = create_tree (NULL, NULL, 0, idx_first);
! 2034: token->opr.ctx_type = WORD_LAST;
! 2035: idx_last = re_dfa_add_node (dfa, *token, 0);
! 2036: tree_last = create_tree (NULL, NULL, 0, idx_last);
! 2037: token->type = OP_ALT;
! 2038: new_idx = re_dfa_add_node (dfa, *token, 0);
! 2039: tree = create_tree (tree_first, tree_last, 0, new_idx);
! 2040: if (BE (idx_first == -1 || idx_last == -1 || new_idx == -1
! 2041: || tree_first == NULL || tree_last == NULL
! 2042: || tree == NULL, 0))
! 2043: {
! 2044: *err = REG_ESPACE;
! 2045: return NULL;
! 2046: }
! 2047: }
! 2048: else
! 2049: {
! 2050: new_idx = re_dfa_add_node (dfa, *token, 0);
! 2051: tree = create_tree (NULL, NULL, 0, new_idx);
! 2052: if (BE (new_idx == -1 || tree == NULL, 0))
! 2053: {
! 2054: *err = REG_ESPACE;
! 2055: return NULL;
! 2056: }
! 2057: }
! 2058: /* We must return here, since ANCHORs can't be followed
! 2059: by repetition operators.
! 2060: eg. RE"^*" is invalid or "<ANCHOR(^)><CHAR(*)>",
! 2061: it must not be "<ANCHOR(^)><REPEAT(*)>". */
! 2062: *token = fetch_token (regexp, syntax);
! 2063: return tree;
! 2064: case OP_PERIOD:
! 2065: new_idx = re_dfa_add_node (dfa, *token, 0);
! 2066: tree = create_tree (NULL, NULL, 0, new_idx);
! 2067: if (BE (new_idx == -1 || tree == NULL, 0))
! 2068: {
! 2069: *err = REG_ESPACE;
! 2070: return NULL;
! 2071: }
! 2072: if (MB_CUR_MAX > 1)
! 2073: dfa->has_mb_node = 1;
! 2074: break;
! 2075: case OP_WORD:
! 2076: tree = build_word_op (dfa, 0, err);
! 2077: if (BE (*err != REG_NOERROR && tree == NULL, 0))
! 2078: return NULL;
! 2079: break;
! 2080: case OP_NOTWORD:
! 2081: tree = build_word_op (dfa, 1, err);
! 2082: if (BE (*err != REG_NOERROR && tree == NULL, 0))
! 2083: return NULL;
! 2084: break;
! 2085: case OP_ALT:
! 2086: case END_OF_RE:
! 2087: return NULL;
! 2088: case BACK_SLASH:
! 2089: *err = REG_EESCAPE;
! 2090: return NULL;
! 2091: default:
! 2092: /* Must not happen? */
! 2093: #ifdef DEBUG
! 2094: assert (0);
! 2095: #endif
! 2096: return NULL;
! 2097: }
! 2098: *token = fetch_token (regexp, syntax);
! 2099:
! 2100: while (token->type == OP_DUP_ASTERISK || token->type == OP_DUP_PLUS
! 2101: || token->type == OP_DUP_QUESTION || token->type == OP_OPEN_DUP_NUM)
! 2102: {
! 2103: tree = parse_dup_op (tree, regexp, dfa, token, syntax, err);
! 2104: if (BE (*err != REG_NOERROR && tree == NULL, 0))
! 2105: return NULL;
! 2106: dfa->has_plural_match = 1;
! 2107: }
! 2108:
! 2109: return tree;
! 2110: }
! 2111:
! 2112: /* This function build the following tree, from regular expression
! 2113: (<reg_exp>):
! 2114: SUBEXP
! 2115: |
! 2116: <reg_exp>
! 2117: */
! 2118:
! 2119: static bin_tree_t *
! 2120: parse_sub_exp (regexp, preg, token, syntax, nest, err)
! 2121: re_string_t *regexp;
! 2122: regex_t *preg;
! 2123: re_token_t *token;
! 2124: reg_syntax_t syntax;
! 2125: int nest;
! 2126: reg_errcode_t *err;
! 2127: {
! 2128: re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
! 2129: bin_tree_t *tree, *left_par, *right_par;
! 2130: size_t cur_nsub;
! 2131: int new_idx;
! 2132: cur_nsub = preg->re_nsub++;
! 2133: if (dfa->subexps_alloc < preg->re_nsub)
! 2134: {
! 2135: re_subexp_t *new_array;
! 2136: dfa->subexps_alloc *= 2;
! 2137: new_array = re_realloc (dfa->subexps, re_subexp_t, dfa->subexps_alloc);
! 2138: if (BE (new_array == NULL, 0))
! 2139: {
! 2140: dfa->subexps_alloc /= 2;
! 2141: *err = REG_ESPACE;
! 2142: return NULL;
! 2143: }
! 2144: dfa->subexps = new_array;
! 2145: }
! 2146: dfa->subexps[cur_nsub].start = dfa->nodes_len;
! 2147: dfa->subexps[cur_nsub].end = -1;
! 2148:
! 2149: new_idx = re_dfa_add_node (dfa, *token, 0);
! 2150: left_par = create_tree (NULL, NULL, 0, new_idx);
! 2151: if (BE (new_idx == -1 || left_par == NULL, 0))
! 2152: {
! 2153: *err = REG_ESPACE;
! 2154: return NULL;
! 2155: }
! 2156: dfa->nodes[new_idx].opr.idx = cur_nsub;
! 2157: *token = fetch_token (regexp, syntax);
! 2158:
! 2159: /* The subexpression may be a null string. */
! 2160: if (token->type == OP_CLOSE_SUBEXP)
! 2161: tree = NULL;
! 2162: else
! 2163: {
! 2164: tree = parse_reg_exp (regexp, preg, token, syntax, nest, err);
! 2165: if (BE (*err != REG_NOERROR && tree == NULL, 0))
! 2166: return NULL;
! 2167: }
! 2168: if (BE (token->type != OP_CLOSE_SUBEXP, 0))
! 2169: {
! 2170: free_bin_tree (tree);
! 2171: *err = REG_BADPAT;
! 2172: return NULL;
! 2173: }
! 2174: new_idx = re_dfa_add_node (dfa, *token, 0);
! 2175: dfa->subexps[cur_nsub].end = dfa->nodes_len;
! 2176: right_par = create_tree (NULL, NULL, 0, new_idx);
! 2177: tree = ((tree == NULL) ? right_par
! 2178: : create_tree (tree, right_par, CONCAT, 0));
! 2179: tree = create_tree (left_par, tree, CONCAT, 0);
! 2180: if (BE (new_idx == -1 || right_par == NULL || tree == NULL, 0))
! 2181: {
! 2182: *err = REG_ESPACE;
! 2183: return NULL;
! 2184: }
! 2185: dfa->nodes[new_idx].opr.idx = cur_nsub;
! 2186:
! 2187: return tree;
! 2188: }
! 2189:
! 2190: /* This function parse repetition operators like "*", "+", "{1,3}" etc. */
! 2191:
! 2192: static bin_tree_t *
! 2193: parse_dup_op (dup_elem, regexp, dfa, token, syntax, err)
! 2194: bin_tree_t *dup_elem;
! 2195: re_string_t *regexp;
! 2196: re_dfa_t *dfa;
! 2197: re_token_t *token;
! 2198: reg_syntax_t syntax;
! 2199: reg_errcode_t *err;
! 2200: {
! 2201: re_token_t dup_token;
! 2202: bin_tree_t *tree = dup_elem, *work_tree;
! 2203: int new_idx, start_idx = re_string_cur_idx (regexp);
! 2204: re_token_t start_token = *token;
! 2205: if (token->type == OP_OPEN_DUP_NUM)
! 2206: {
! 2207: int i;
! 2208: int end = 0;
! 2209: int start = fetch_number (regexp, token, syntax);
! 2210: bin_tree_t *elem;
! 2211: if (start == -1)
! 2212: {
! 2213: if (token->type == CHARACTER && token->opr.c == ',')
! 2214: start = 0; /* We treat "{,m}" as "{0,m}". */
! 2215: else
! 2216: {
! 2217: *err = REG_BADBR; /* <re>{} is invalid. */
! 2218: return NULL;
! 2219: }
! 2220: }
! 2221: if (BE (start != -2, 1))
! 2222: {
! 2223: /* We treat "{n}" as "{n,n}". */
! 2224: end = ((token->type == OP_CLOSE_DUP_NUM) ? start
! 2225: : ((token->type == CHARACTER && token->opr.c == ',')
! 2226: ? fetch_number (regexp, token, syntax) : -2));
! 2227: }
! 2228: if (BE (start == -2 || end == -2, 0))
! 2229: {
! 2230: /* Invalid sequence. */
! 2231: if (token->type == OP_CLOSE_DUP_NUM)
! 2232: goto parse_dup_op_invalid_interval;
! 2233: else
! 2234: goto parse_dup_op_ebrace;
! 2235: }
! 2236: if (BE (start == 0 && end == 0, 0))
! 2237: {
! 2238: /* We treat "<re>{0}" and "<re>{0,0}" as null string. */
! 2239: *token = fetch_token (regexp, syntax);
! 2240: free_bin_tree (dup_elem);
! 2241: return NULL;
! 2242: }
! 2243:
! 2244: /* Extract "<re>{n,m}" to "<re><re>...<re><re>{0,<m-n>}". */
! 2245: elem = tree;
! 2246: for (i = 0; i < start; ++i)
! 2247: if (i != 0)
! 2248: {
! 2249: work_tree = duplicate_tree (elem, dfa);
! 2250: tree = create_tree (tree, work_tree, CONCAT, 0);
! 2251: if (BE (work_tree == NULL || tree == NULL, 0))
! 2252: goto parse_dup_op_espace;
! 2253: }
! 2254:
! 2255: if (end == -1)
! 2256: {
! 2257: /* We treat "<re>{0,}" as "<re>*". */
! 2258: dup_token.type = OP_DUP_ASTERISK;
! 2259: if (start > 0)
! 2260: {
! 2261: elem = duplicate_tree (elem, dfa);
! 2262: new_idx = re_dfa_add_node (dfa, dup_token, 0);
! 2263: work_tree = create_tree (elem, NULL, 0, new_idx);
! 2264: tree = create_tree (tree, work_tree, CONCAT, 0);
! 2265: if (BE (elem == NULL || new_idx == -1 || work_tree == NULL
! 2266: || tree == NULL, 0))
! 2267: goto parse_dup_op_espace;
! 2268: }
! 2269: else
! 2270: {
! 2271: new_idx = re_dfa_add_node (dfa, dup_token, 0);
! 2272: tree = create_tree (elem, NULL, 0, new_idx);
! 2273: if (BE (new_idx == -1 || tree == NULL, 0))
! 2274: goto parse_dup_op_espace;
! 2275: }
! 2276: }
! 2277: else if (end - start > 0)
! 2278: {
! 2279: /* Then extract "<re>{0,m}" to "<re>?<re>?...<re>?". */
! 2280: dup_token.type = OP_DUP_QUESTION;
! 2281: if (start > 0)
! 2282: {
! 2283: elem = duplicate_tree (elem, dfa);
! 2284: new_idx = re_dfa_add_node (dfa, dup_token, 0);
! 2285: elem = create_tree (elem, NULL, 0, new_idx);
! 2286: tree = create_tree (tree, elem, CONCAT, 0);
! 2287: if (BE (elem == NULL || new_idx == -1 || tree == NULL, 0))
! 2288: goto parse_dup_op_espace;
! 2289: }
! 2290: else
! 2291: {
! 2292: new_idx = re_dfa_add_node (dfa, dup_token, 0);
! 2293: tree = elem = create_tree (elem, NULL, 0, new_idx);
! 2294: if (BE (new_idx == -1 || tree == NULL, 0))
! 2295: goto parse_dup_op_espace;
! 2296: }
! 2297: for (i = 1; i < end - start; ++i)
! 2298: {
! 2299: work_tree = duplicate_tree (elem, dfa);
! 2300: tree = create_tree (tree, work_tree, CONCAT, 0);
! 2301: if (BE (work_tree == NULL || tree == NULL, 0))
! 2302: {
! 2303: *err = REG_ESPACE;
! 2304: return NULL;
! 2305: }
! 2306: }
! 2307: }
! 2308: }
! 2309: else
! 2310: {
! 2311: new_idx = re_dfa_add_node (dfa, *token, 0);
! 2312: tree = create_tree (tree, NULL, 0, new_idx);
! 2313: if (BE (new_idx == -1 || tree == NULL, 0))
! 2314: {
! 2315: *err = REG_ESPACE;
! 2316: return NULL;
! 2317: }
! 2318: }
! 2319: *token = fetch_token (regexp, syntax);
! 2320: return tree;
! 2321:
! 2322: parse_dup_op_espace:
! 2323: free_bin_tree (tree);
! 2324: *err = REG_ESPACE;
! 2325: return NULL;
! 2326:
! 2327: parse_dup_op_ebrace:
! 2328: if (BE (!(syntax & RE_INVALID_INTERVAL_ORD), 0))
! 2329: {
! 2330: *err = REG_EBRACE;
! 2331: return NULL;
! 2332: }
! 2333: goto parse_dup_op_rollback;
! 2334: parse_dup_op_invalid_interval:
! 2335: if (BE (!(syntax & RE_INVALID_INTERVAL_ORD), 0))
! 2336: {
! 2337: *err = REG_BADBR;
! 2338: return NULL;
! 2339: }
! 2340: parse_dup_op_rollback:
! 2341: re_string_set_index (regexp, start_idx);
! 2342: *token = start_token;
! 2343: token->type = CHARACTER;
! 2344: return dup_elem;
! 2345: }
! 2346:
! 2347: /* Size of the names for collating symbol/equivalence_class/character_class.
! 2348: I'm not sure, but maybe enough. */
! 2349: #define BRACKET_NAME_BUF_SIZE 32
! 2350:
! 2351: #ifndef _LIBC
! 2352: /* Local function for parse_bracket_exp only used in case of NOT _LIBC.
! 2353: Build the range expression which starts from START_ELEM, and ends
! 2354: at END_ELEM. The result are written to MBCSET and SBCSET.
! 2355: RANGE_ALLOC is the allocated size of mbcset->range_starts, and
! 2356: mbcset->range_ends, is a pointer argument sinse we may
! 2357: update it. */
! 2358:
! 2359: static reg_errcode_t
! 2360: # ifdef RE_ENABLE_I18N
! 2361: build_range_exp (sbcset, mbcset, range_alloc, start_elem, end_elem)
! 2362: re_charset_t *mbcset;
! 2363: int *range_alloc;
! 2364: # else /* not RE_ENABLE_I18N */
! 2365: build_range_exp (sbcset, start_elem, end_elem)
! 2366: # endif /* not RE_ENABLE_I18N */
! 2367: re_bitset_ptr_t sbcset;
! 2368: bracket_elem_t *start_elem, *end_elem;
! 2369: {
! 2370: unsigned int start_ch, end_ch;
! 2371: /* Equivalence Classes and Character Classes can't be a range start/end. */
! 2372: if (BE (start_elem->type == EQUIV_CLASS || start_elem->type == CHAR_CLASS
! 2373: || end_elem->type == EQUIV_CLASS || end_elem->type == CHAR_CLASS,
! 2374: 0))
! 2375: return REG_ERANGE;
! 2376:
! 2377: /* We can handle no multi character collating elements without libc
! 2378: support. */
! 2379: if (BE ((start_elem->type == COLL_SYM
! 2380: && strlen ((char *) start_elem->opr.name) > 1)
! 2381: || (end_elem->type == COLL_SYM
! 2382: && strlen ((char *) end_elem->opr.name) > 1), 0))
! 2383: return REG_ECOLLATE;
! 2384:
! 2385: # ifdef RE_ENABLE_I18N
! 2386: {
! 2387: wchar_t wc, start_wc, end_wc;
! 2388: wchar_t cmp_buf[6] = {L'\0', L'\0', L'\0', L'\0', L'\0', L'\0'};
! 2389:
! 2390: start_ch = ((start_elem->type == SB_CHAR) ? start_elem->opr.ch
! 2391: : ((start_elem->type == COLL_SYM) ? start_elem->opr.name[0]
! 2392: : 0));
! 2393: end_ch = ((end_elem->type == SB_CHAR) ? end_elem->opr.ch
! 2394: : ((end_elem->type == COLL_SYM) ? end_elem->opr.name[0]
! 2395: : 0));
! 2396: start_wc = ((start_elem->type == SB_CHAR || start_elem->type == COLL_SYM)
! 2397: ? __btowc (start_ch) : start_elem->opr.wch);
! 2398: end_wc = ((end_elem->type == SB_CHAR || end_elem->type == COLL_SYM)
! 2399: ? __btowc (end_ch) : end_elem->opr.wch);
! 2400: cmp_buf[0] = start_wc;
! 2401: cmp_buf[4] = end_wc;
! 2402: if (wcscoll (cmp_buf, cmp_buf + 4) > 0)
! 2403: return REG_ERANGE;
! 2404:
! 2405: /* Check the space of the arrays. */
! 2406: if (*range_alloc == mbcset->nranges)
! 2407: {
! 2408: /* There are not enough space, need realloc. */
! 2409: wchar_t *new_array_start, *new_array_end;
! 2410: int new_nranges;
! 2411:
! 2412: /* +1 in case of mbcset->nranges is 0. */
! 2413: new_nranges = 2 * mbcset->nranges + 1;
! 2414: /* Use realloc since mbcset->range_starts and mbcset->range_ends
! 2415: are NULL if *range_alloc == 0. */
! 2416: new_array_start = re_realloc (mbcset->range_starts, wchar_t,
! 2417: new_nranges);
! 2418: new_array_end = re_realloc (mbcset->range_ends, wchar_t,
! 2419: new_nranges);
! 2420:
! 2421: if (BE (new_array_start == NULL || new_array_end == NULL, 0))
! 2422: return REG_ESPACE;
! 2423:
! 2424: mbcset->range_starts = new_array_start;
! 2425: mbcset->range_ends = new_array_end;
! 2426: *range_alloc = new_nranges;
! 2427: }
! 2428:
! 2429: mbcset->range_starts[mbcset->nranges] = start_wc;
! 2430: mbcset->range_ends[mbcset->nranges++] = end_wc;
! 2431:
! 2432: /* Build the table for single byte characters. */
! 2433: for (wc = 0; wc <= SBC_MAX; ++wc)
! 2434: {
! 2435: cmp_buf[2] = wc;
! 2436: if (wcscoll (cmp_buf, cmp_buf + 2) <= 0
! 2437: && wcscoll (cmp_buf + 2, cmp_buf + 4) <= 0)
! 2438: bitset_set (sbcset, wc);
! 2439: }
! 2440: }
! 2441: # else /* not RE_ENABLE_I18N */
! 2442: {
! 2443: unsigned int ch;
! 2444: start_ch = ((start_elem->type == SB_CHAR ) ? start_elem->opr.ch
! 2445: : ((start_elem->type == COLL_SYM) ? start_elem->opr.name[0]
! 2446: : 0));
! 2447: end_ch = ((end_elem->type == SB_CHAR ) ? end_elem->opr.ch
! 2448: : ((end_elem->type == COLL_SYM) ? end_elem->opr.name[0]
! 2449: : 0));
! 2450: if (start_ch > end_ch)
! 2451: return REG_ERANGE;
! 2452: /* Build the table for single byte characters. */
! 2453: for (ch = 0; ch <= SBC_MAX; ++ch)
! 2454: if (start_ch <= ch && ch <= end_ch)
! 2455: bitset_set (sbcset, ch);
! 2456: }
! 2457: # endif /* not RE_ENABLE_I18N */
! 2458: return REG_NOERROR;
! 2459: }
! 2460: #endif /* not _LIBC */
! 2461:
! 2462: #ifndef _LIBC
! 2463: /* Helper function for parse_bracket_exp only used in case of NOT _LIBC..
! 2464: Build the collating element which is represented by NAME.
! 2465: The result are written to MBCSET and SBCSET.
! 2466: COLL_SYM_ALLOC is the allocated size of mbcset->coll_sym, is a
! 2467: pointer argument since we may update it. */
! 2468:
! 2469: static reg_errcode_t
! 2470: # ifdef RE_ENABLE_I18N
! 2471: build_collating_symbol (sbcset, mbcset, coll_sym_alloc, name)
! 2472: re_charset_t *mbcset;
! 2473: int *coll_sym_alloc;
! 2474: # else /* not RE_ENABLE_I18N */
! 2475: build_collating_symbol (sbcset, name)
! 2476: # endif /* not RE_ENABLE_I18N */
! 2477: re_bitset_ptr_t sbcset;
! 2478: const unsigned char *name;
! 2479: {
! 2480: size_t name_len = strlen ((const char *) name);
! 2481: if (BE (name_len != 1, 0))
! 2482: return REG_ECOLLATE;
! 2483: else
! 2484: {
! 2485: bitset_set (sbcset, name[0]);
! 2486: return REG_NOERROR;
! 2487: }
! 2488: }
! 2489: #endif /* not _LIBC */
! 2490:
! 2491: /* This function parse bracket expression like "[abc]", "[a-c]",
! 2492: "[[.a-a.]]" etc. */
! 2493:
! 2494: static bin_tree_t *
! 2495: parse_bracket_exp (regexp, dfa, token, syntax, err)
! 2496: re_string_t *regexp;
! 2497: re_dfa_t *dfa;
! 2498: re_token_t *token;
! 2499: reg_syntax_t syntax;
! 2500: reg_errcode_t *err;
! 2501: {
! 2502: #ifdef _LIBC
! 2503: const unsigned char *collseqmb;
! 2504: const char *collseqwc;
! 2505: uint32_t nrules;
! 2506: int32_t table_size;
! 2507: const int32_t *symb_table;
! 2508: const unsigned char *extra;
! 2509:
! 2510: /* Local function for parse_bracket_exp used in _LIBC environement.
! 2511: Seek the collating symbol entry correspondings to NAME.
! 2512: Return the index of the symbol in the SYMB_TABLE. */
! 2513:
! 2514: static inline int32_t
! 2515: seek_collating_symbol_entry (name, name_len)
! 2516: const unsigned char *name;
! 2517: size_t name_len;
! 2518: {
! 2519: int32_t hash = elem_hash ((const char *) name, name_len);
! 2520: int32_t elem = hash % table_size;
! 2521: int32_t second = hash % (table_size - 2);
! 2522: while (symb_table[2 * elem] != 0)
! 2523: {
! 2524: /* First compare the hashing value. */
! 2525: if (symb_table[2 * elem] == hash
! 2526: /* Compare the length of the name. */
! 2527: && name_len == extra[symb_table[2 * elem + 1]]
! 2528: /* Compare the name. */
! 2529: && memcmp (name, &extra[symb_table[2 * elem + 1] + 1],
! 2530: name_len) == 0)
! 2531: {
! 2532: /* Yep, this is the entry. */
! 2533: break;
! 2534: }
! 2535:
! 2536: /* Next entry. */
! 2537: elem += second;
! 2538: }
! 2539: return elem;
! 2540: }
! 2541:
! 2542: /* Local function for parse_bracket_exp used in _LIBC environement.
! 2543: Look up the collation sequence value of BR_ELEM.
! 2544: Return the value if succeeded, UINT_MAX otherwise. */
! 2545:
! 2546: static inline unsigned int
! 2547: lookup_collation_sequence_value (br_elem)
! 2548: bracket_elem_t *br_elem;
! 2549: {
! 2550: if (br_elem->type == SB_CHAR)
! 2551: {
! 2552: /*
! 2553: if (MB_CUR_MAX == 1)
! 2554: */
! 2555: if (nrules == 0)
! 2556: return collseqmb[br_elem->opr.ch];
! 2557: else
! 2558: {
! 2559: wint_t wc = __btowc (br_elem->opr.ch);
! 2560: return collseq_table_lookup (collseqwc, wc);
! 2561: }
! 2562: }
! 2563: else if (br_elem->type == MB_CHAR)
! 2564: {
! 2565: return collseq_table_lookup (collseqwc, br_elem->opr.wch);
! 2566: }
! 2567: else if (br_elem->type == COLL_SYM)
! 2568: {
! 2569: size_t sym_name_len = strlen ((char *) br_elem->opr.name);
! 2570: if (nrules != 0)
! 2571: {
! 2572: int32_t elem, idx;
! 2573: elem = seek_collating_symbol_entry (br_elem->opr.name,
! 2574: sym_name_len);
! 2575: if (symb_table[2 * elem] != 0)
! 2576: {
! 2577: /* We found the entry. */
! 2578: idx = symb_table[2 * elem + 1];
! 2579: /* Skip the name of collating element name. */
! 2580: idx += 1 + extra[idx];
! 2581: /* Skip the byte sequence of the collating element. */
! 2582: idx += 1 + extra[idx];
! 2583: /* Adjust for the alignment. */
! 2584: idx = (idx + 3) & ~3;
! 2585: /* Skip the multibyte collation sequence value. */
! 2586: idx += sizeof (unsigned int);
! 2587: /* Skip the wide char sequence of the collating element. */
! 2588: idx += sizeof (unsigned int) *
! 2589: (1 + *(unsigned int *) (extra + idx));
! 2590: /* Return the collation sequence value. */
! 2591: return *(unsigned int *) (extra + idx);
! 2592: }
! 2593: else if (symb_table[2 * elem] == 0 && sym_name_len == 1)
! 2594: {
! 2595: /* No valid character. Match it as a single byte
! 2596: character. */
! 2597: return collseqmb[br_elem->opr.name[0]];
! 2598: }
! 2599: }
! 2600: else if (sym_name_len == 1)
! 2601: return collseqmb[br_elem->opr.name[0]];
! 2602: }
! 2603: return UINT_MAX;
! 2604: }
! 2605:
! 2606: /* Local function for parse_bracket_exp used in _LIBC environement.
! 2607: Build the range expression which starts from START_ELEM, and ends
! 2608: at END_ELEM. The result are written to MBCSET and SBCSET.
! 2609: RANGE_ALLOC is the allocated size of mbcset->range_starts, and
! 2610: mbcset->range_ends, is a pointer argument sinse we may
! 2611: update it. */
! 2612:
! 2613: static inline reg_errcode_t
! 2614: # ifdef RE_ENABLE_I18N
! 2615: build_range_exp (sbcset, mbcset, range_alloc, start_elem, end_elem)
! 2616: re_charset_t *mbcset;
! 2617: int *range_alloc;
! 2618: # else /* not RE_ENABLE_I18N */
! 2619: build_range_exp (sbcset, start_elem, end_elem)
! 2620: # endif /* not RE_ENABLE_I18N */
! 2621: re_bitset_ptr_t sbcset;
! 2622: bracket_elem_t *start_elem, *end_elem;
! 2623: {
! 2624: unsigned int ch;
! 2625: uint32_t start_collseq;
! 2626: uint32_t end_collseq;
! 2627:
! 2628: # ifdef RE_ENABLE_I18N
! 2629: /* Check the space of the arrays. */
! 2630: if (*range_alloc == mbcset->nranges)
! 2631: {
! 2632: /* There are not enough space, need realloc. */
! 2633: uint32_t *new_array_start;
! 2634: uint32_t *new_array_end;
! 2635: int new_nranges;
! 2636:
! 2637: /* +1 in case of mbcset->nranges is 0. */
! 2638: new_nranges = 2 * mbcset->nranges + 1;
! 2639: /* Use realloc since mbcset->range_starts and mbcset->range_ends
! 2640: are NULL if *range_alloc == 0. */
! 2641: new_array_start = re_realloc (mbcset->range_starts, uint32_t,
! 2642: new_nranges);
! 2643: new_array_end = re_realloc (mbcset->range_ends, uint32_t,
! 2644: new_nranges);
! 2645:
! 2646: if (BE (new_array_start == NULL || new_array_end == NULL, 0))
! 2647: return REG_ESPACE;
! 2648:
! 2649: mbcset->range_starts = new_array_start;
! 2650: mbcset->range_ends = new_array_end;
! 2651: *range_alloc = new_nranges;
! 2652: }
! 2653: # endif /* RE_ENABLE_I18N */
! 2654:
! 2655: /* Equivalence Classes and Character Classes can't be a range
! 2656: start/end. */
! 2657: if (BE (start_elem->type == EQUIV_CLASS || start_elem->type == CHAR_CLASS
! 2658: || end_elem->type == EQUIV_CLASS || end_elem->type == CHAR_CLASS,
! 2659: 0))
! 2660: return REG_ERANGE;
! 2661:
! 2662: start_collseq = lookup_collation_sequence_value (start_elem);
! 2663: end_collseq = lookup_collation_sequence_value (end_elem);
! 2664: /* Check start/end collation sequence values. */
! 2665: if (BE (start_collseq == UINT_MAX || end_collseq == UINT_MAX, 0))
! 2666: return REG_ECOLLATE;
! 2667: if (BE ((syntax & RE_NO_EMPTY_RANGES) && start_collseq > end_collseq, 0))
! 2668: return REG_ERANGE;
! 2669:
! 2670: # ifdef RE_ENABLE_I18N
! 2671: /* Got valid collation sequence values, add them as a new entry. */
! 2672: mbcset->range_starts[mbcset->nranges] = start_collseq;
! 2673: mbcset->range_ends[mbcset->nranges++] = end_collseq;
! 2674: # endif /* RE_ENABLE_I18N */
! 2675:
! 2676: /* Build the table for single byte characters. */
! 2677: for (ch = 0; ch <= SBC_MAX; ch++)
! 2678: {
! 2679: uint32_t ch_collseq;
! 2680: /*
! 2681: if (MB_CUR_MAX == 1)
! 2682: */
! 2683: if (nrules == 0)
! 2684: ch_collseq = collseqmb[ch];
! 2685: else
! 2686: ch_collseq = collseq_table_lookup (collseqwc, __btowc (ch));
! 2687: if (start_collseq <= ch_collseq && ch_collseq <= end_collseq)
! 2688: bitset_set (sbcset, ch);
! 2689: }
! 2690: return REG_NOERROR;
! 2691: }
! 2692:
! 2693: /* Local function for parse_bracket_exp used in _LIBC environement.
! 2694: Build the collating element which is represented by NAME.
! 2695: The result are written to MBCSET and SBCSET.
! 2696: COLL_SYM_ALLOC is the allocated size of mbcset->coll_sym, is a
! 2697: pointer argument sinse we may update it. */
! 2698:
! 2699: static inline reg_errcode_t
! 2700: # ifdef RE_ENABLE_I18N
! 2701: build_collating_symbol (sbcset, mbcset, coll_sym_alloc, name)
! 2702: re_charset_t *mbcset;
! 2703: int *coll_sym_alloc;
! 2704: # else /* not RE_ENABLE_I18N */
! 2705: build_collating_symbol (sbcset, name)
! 2706: # endif /* not RE_ENABLE_I18N */
! 2707: re_bitset_ptr_t sbcset;
! 2708: const unsigned char *name;
! 2709: {
! 2710: int32_t elem, idx;
! 2711: size_t name_len = strlen ((const char *) name);
! 2712: if (nrules != 0)
! 2713: {
! 2714: elem = seek_collating_symbol_entry (name, name_len);
! 2715: if (symb_table[2 * elem] != 0)
! 2716: {
! 2717: /* We found the entry. */
! 2718: idx = symb_table[2 * elem + 1];
! 2719: /* Skip the name of collating element name. */
! 2720: idx += 1 + extra[idx];
! 2721: }
! 2722: else if (symb_table[2 * elem] == 0 && name_len == 1)
! 2723: {
! 2724: /* No valid character, treat it as a normal
! 2725: character. */
! 2726: bitset_set (sbcset, name[0]);
! 2727: return REG_NOERROR;
! 2728: }
! 2729: else
! 2730: return REG_ECOLLATE;
! 2731:
! 2732: # ifdef RE_ENABLE_I18N
! 2733: /* Got valid collation sequence, add it as a new entry. */
! 2734: /* Check the space of the arrays. */
! 2735: if (*coll_sym_alloc == mbcset->ncoll_syms)
! 2736: {
! 2737: /* Not enough, realloc it. */
! 2738: /* +1 in case of mbcset->ncoll_syms is 0. */
! 2739: *coll_sym_alloc = 2 * mbcset->ncoll_syms + 1;
! 2740: /* Use realloc since mbcset->coll_syms is NULL
! 2741: if *alloc == 0. */
! 2742: mbcset->coll_syms = re_realloc (mbcset->coll_syms, int32_t,
! 2743: *coll_sym_alloc);
! 2744: if (BE (mbcset->coll_syms == NULL, 0))
! 2745: return REG_ESPACE;
! 2746: }
! 2747: mbcset->coll_syms[mbcset->ncoll_syms++] = idx;
! 2748: # endif /* RE_ENABLE_I18N */
! 2749: return REG_NOERROR;
! 2750: }
! 2751: else
! 2752: {
! 2753: if (BE (name_len != 1, 0))
! 2754: return REG_ECOLLATE;
! 2755: else
! 2756: {
! 2757: bitset_set (sbcset, name[0]);
! 2758: return REG_NOERROR;
! 2759: }
! 2760: }
! 2761: }
! 2762: #endif
! 2763:
! 2764: re_token_t br_token;
! 2765: re_bitset_ptr_t sbcset;
! 2766: #ifdef RE_ENABLE_I18N
! 2767: re_charset_t *mbcset;
! 2768: int coll_sym_alloc = 0, range_alloc = 0, mbchar_alloc = 0;
! 2769: int equiv_class_alloc = 0, char_class_alloc = 0;
! 2770: #else /* not RE_ENABLE_I18N */
! 2771: int non_match = 0;
! 2772: #endif /* not RE_ENABLE_I18N */
! 2773: bin_tree_t *work_tree;
! 2774: int token_len, new_idx;
! 2775: #ifdef _LIBC
! 2776: collseqmb = (const unsigned char *)
! 2777: _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQMB);
! 2778: nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
! 2779: if (nrules)
! 2780: {
! 2781: /*
! 2782: if (MB_CUR_MAX > 1)
! 2783: */
! 2784: collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC);
! 2785: table_size = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_SYMB_HASH_SIZEMB);
! 2786: symb_table = (const int32_t *) _NL_CURRENT (LC_COLLATE,
! 2787: _NL_COLLATE_SYMB_TABLEMB);
! 2788: extra = (const unsigned char *) _NL_CURRENT (LC_COLLATE,
! 2789: _NL_COLLATE_SYMB_EXTRAMB);
! 2790: }
! 2791: #endif
! 2792: sbcset = (re_bitset_ptr_t) calloc (sizeof (unsigned int), BITSET_UINTS);
! 2793: #ifdef RE_ENABLE_I18N
! 2794: mbcset = (re_charset_t *) calloc (sizeof (re_charset_t), 1);
! 2795: #endif /* RE_ENABLE_I18N */
! 2796: #ifdef RE_ENABLE_I18N
! 2797: if (BE (sbcset == NULL || mbcset == NULL, 0))
! 2798: #else
! 2799: if (BE (sbcset == NULL, 0))
! 2800: #endif /* RE_ENABLE_I18N */
! 2801: {
! 2802: *err = REG_ESPACE;
! 2803: return NULL;
! 2804: }
! 2805:
! 2806: token_len = peek_token_bracket (token, regexp, syntax);
! 2807: if (BE (token->type == END_OF_RE, 0))
! 2808: {
! 2809: *err = REG_BADPAT;
! 2810: goto parse_bracket_exp_free_return;
! 2811: }
! 2812: if (token->type == OP_NON_MATCH_LIST)
! 2813: {
! 2814: #ifdef RE_ENABLE_I18N
! 2815: int i;
! 2816: mbcset->non_match = 1;
! 2817: #else /* not RE_ENABLE_I18N */
! 2818: non_match = 1;
! 2819: #endif /* not RE_ENABLE_I18N */
! 2820: if (syntax & RE_HAT_LISTS_NOT_NEWLINE)
! 2821: bitset_set (sbcset, '\0');
! 2822: re_string_skip_bytes (regexp, token_len); /* Skip a token. */
! 2823: token_len = peek_token_bracket (token, regexp, syntax);
! 2824: if (BE (token->type == END_OF_RE, 0))
! 2825: {
! 2826: *err = REG_BADPAT;
! 2827: goto parse_bracket_exp_free_return;
! 2828: }
! 2829: #ifdef RE_ENABLE_I18N
! 2830: if (MB_CUR_MAX > 1)
! 2831: for (i = 0; i < SBC_MAX; ++i)
! 2832: if (__btowc (i) == WEOF)
! 2833: bitset_set (sbcset, i);
! 2834: #endif /* RE_ENABLE_I18N */
! 2835: }
! 2836:
! 2837: /* We treat the first ']' as a normal character. */
! 2838: if (token->type == OP_CLOSE_BRACKET)
! 2839: token->type = CHARACTER;
! 2840:
! 2841: while (1)
! 2842: {
! 2843: bracket_elem_t start_elem, end_elem;
! 2844: unsigned char start_name_buf[BRACKET_NAME_BUF_SIZE];
! 2845: unsigned char end_name_buf[BRACKET_NAME_BUF_SIZE];
! 2846: reg_errcode_t ret;
! 2847: int token_len2 = 0, is_range_exp = 0;
! 2848: re_token_t token2;
! 2849:
! 2850: start_elem.opr.name = start_name_buf;
! 2851: ret = parse_bracket_element (&start_elem, regexp, token, token_len, dfa,
! 2852: syntax);
! 2853: if (BE (ret != REG_NOERROR, 0))
! 2854: {
! 2855: *err = ret;
! 2856: goto parse_bracket_exp_free_return;
! 2857: }
! 2858:
! 2859: token_len = peek_token_bracket (token, regexp, syntax);
! 2860: if (BE (token->type == END_OF_RE, 0))
! 2861: {
! 2862: *err = REG_BADPAT;
! 2863: goto parse_bracket_exp_free_return;
! 2864: }
! 2865: if (token->type == OP_CHARSET_RANGE)
! 2866: {
! 2867: re_string_skip_bytes (regexp, token_len); /* Skip '-'. */
! 2868: token_len2 = peek_token_bracket (&token2, regexp, syntax);
! 2869: if (BE (token->type == END_OF_RE, 0))
! 2870: {
! 2871: *err = REG_BADPAT;
! 2872: goto parse_bracket_exp_free_return;
! 2873: }
! 2874: if (token2.type == OP_CLOSE_BRACKET)
! 2875: {
! 2876: /* We treat the last '-' as a normal character. */
! 2877: re_string_skip_bytes (regexp, -token_len);
! 2878: token->type = CHARACTER;
! 2879: }
! 2880: else
! 2881: is_range_exp = 1;
! 2882: }
! 2883:
! 2884: if (is_range_exp == 1)
! 2885: {
! 2886: end_elem.opr.name = end_name_buf;
! 2887: ret = parse_bracket_element (&end_elem, regexp, &token2, token_len2,
! 2888: dfa, syntax);
! 2889: if (BE (ret != REG_NOERROR, 0))
! 2890: {
! 2891: *err = ret;
! 2892: goto parse_bracket_exp_free_return;
! 2893: }
! 2894:
! 2895: token_len = peek_token_bracket (token, regexp, syntax);
! 2896: if (BE (token->type == END_OF_RE, 0))
! 2897: {
! 2898: *err = REG_BADPAT;
! 2899: goto parse_bracket_exp_free_return;
! 2900: }
! 2901: *err = build_range_exp (sbcset,
! 2902: #ifdef RE_ENABLE_I18N
! 2903: mbcset, &range_alloc,
! 2904: #endif /* RE_ENABLE_I18N */
! 2905: &start_elem, &end_elem);
! 2906: if (BE (*err != REG_NOERROR, 0))
! 2907: goto parse_bracket_exp_free_return;
! 2908: }
! 2909: else
! 2910: {
! 2911: switch (start_elem.type)
! 2912: {
! 2913: case SB_CHAR:
! 2914: bitset_set (sbcset, start_elem.opr.ch);
! 2915: break;
! 2916: #ifdef RE_ENABLE_I18N
! 2917: case MB_CHAR:
! 2918: /* Check whether the array has enough space. */
! 2919: if (mbchar_alloc == mbcset->nmbchars)
! 2920: {
! 2921: /* Not enough, realloc it. */
! 2922: /* +1 in case of mbcset->nmbchars is 0. */
! 2923: mbchar_alloc = 2 * mbcset->nmbchars + 1;
! 2924: /* Use realloc since array is NULL if *alloc == 0. */
! 2925: mbcset->mbchars = re_realloc (mbcset->mbchars, wchar_t,
! 2926: mbchar_alloc);
! 2927: if (BE (mbcset->mbchars == NULL, 0))
! 2928: goto parse_bracket_exp_espace;
! 2929: }
! 2930: mbcset->mbchars[mbcset->nmbchars++] = start_elem.opr.wch;
! 2931: break;
! 2932: #endif /* RE_ENABLE_I18N */
! 2933: case EQUIV_CLASS:
! 2934: *err = build_equiv_class (sbcset,
! 2935: #ifdef RE_ENABLE_I18N
! 2936: mbcset, &equiv_class_alloc,
! 2937: #endif /* RE_ENABLE_I18N */
! 2938: start_elem.opr.name);
! 2939: if (BE (*err != REG_NOERROR, 0))
! 2940: goto parse_bracket_exp_free_return;
! 2941: break;
! 2942: case COLL_SYM:
! 2943: *err = build_collating_symbol (sbcset,
! 2944: #ifdef RE_ENABLE_I18N
! 2945: mbcset, &coll_sym_alloc,
! 2946: #endif /* RE_ENABLE_I18N */
! 2947: start_elem.opr.name);
! 2948: if (BE (*err != REG_NOERROR, 0))
! 2949: goto parse_bracket_exp_free_return;
! 2950: break;
! 2951: case CHAR_CLASS:
! 2952: *err = build_charclass (sbcset,
! 2953: #ifdef RE_ENABLE_I18N
! 2954: mbcset, &char_class_alloc,
! 2955: #endif /* RE_ENABLE_I18N */
! 2956: start_elem.opr.name, syntax);
! 2957: if (BE (*err != REG_NOERROR, 0))
! 2958: goto parse_bracket_exp_free_return;
! 2959: break;
! 2960: default:
! 2961: assert (0);
! 2962: break;
! 2963: }
! 2964: }
! 2965: if (token->type == OP_CLOSE_BRACKET)
! 2966: break;
! 2967: }
! 2968:
! 2969: re_string_skip_bytes (regexp, token_len); /* Skip a token. */
! 2970:
! 2971: /* If it is non-matching list. */
! 2972: #ifdef RE_ENABLE_I18N
! 2973: if (mbcset->non_match)
! 2974: #else /* not RE_ENABLE_I18N */
! 2975: if (non_match)
! 2976: #endif /* not RE_ENABLE_I18N */
! 2977: bitset_not (sbcset);
! 2978:
! 2979: /* Build a tree for simple bracket. */
! 2980: br_token.type = SIMPLE_BRACKET;
! 2981: br_token.opr.sbcset = sbcset;
! 2982: new_idx = re_dfa_add_node (dfa, br_token, 0);
! 2983: work_tree = create_tree (NULL, NULL, 0, new_idx);
! 2984: if (BE (new_idx == -1 || work_tree == NULL, 0))
! 2985: goto parse_bracket_exp_espace;
! 2986:
! 2987: #ifdef RE_ENABLE_I18N
! 2988: if (mbcset->nmbchars || mbcset->ncoll_syms || mbcset->nequiv_classes
! 2989: || mbcset->nranges || (MB_CUR_MAX > 1 && (mbcset->nchar_classes
! 2990: || mbcset->non_match)))
! 2991: {
! 2992: re_token_t alt_token;
! 2993: bin_tree_t *mbc_tree;
! 2994: /* Build a tree for complex bracket. */
! 2995: br_token.type = COMPLEX_BRACKET;
! 2996: br_token.opr.mbcset = mbcset;
! 2997: dfa->has_mb_node = 1;
! 2998: new_idx = re_dfa_add_node (dfa, br_token, 0);
! 2999: mbc_tree = create_tree (NULL, NULL, 0, new_idx);
! 3000: if (BE (new_idx == -1 || mbc_tree == NULL, 0))
! 3001: goto parse_bracket_exp_espace;
! 3002: /* Then join them by ALT node. */
! 3003: dfa->has_plural_match = 1;
! 3004: alt_token.type = OP_ALT;
! 3005: new_idx = re_dfa_add_node (dfa, alt_token, 0);
! 3006: work_tree = create_tree (work_tree, mbc_tree, 0, new_idx);
! 3007: if (BE (new_idx != -1 && mbc_tree != NULL, 1))
! 3008: return work_tree;
! 3009: }
! 3010: else
! 3011: {
! 3012: free_charset (mbcset);
! 3013: return work_tree;
! 3014: }
! 3015: #else /* not RE_ENABLE_I18N */
! 3016: return work_tree;
! 3017: #endif /* not RE_ENABLE_I18N */
! 3018:
! 3019: parse_bracket_exp_espace:
! 3020: *err = REG_ESPACE;
! 3021: parse_bracket_exp_free_return:
! 3022: re_free (sbcset);
! 3023: #ifdef RE_ENABLE_I18N
! 3024: free_charset (mbcset);
! 3025: #endif /* RE_ENABLE_I18N */
! 3026: return NULL;
! 3027: }
! 3028:
! 3029: /* Parse an element in the bracket expression. */
! 3030:
! 3031: static reg_errcode_t
! 3032: parse_bracket_element (elem, regexp, token, token_len, dfa, syntax)
! 3033: bracket_elem_t *elem;
! 3034: re_string_t *regexp;
! 3035: re_token_t *token;
! 3036: int token_len;
! 3037: re_dfa_t *dfa;
! 3038: reg_syntax_t syntax;
! 3039: {
! 3040: #ifdef RE_ENABLE_I18N
! 3041: int cur_char_size;
! 3042: cur_char_size = re_string_char_size_at (regexp, re_string_cur_idx (regexp));
! 3043: if (cur_char_size > 1)
! 3044: {
! 3045: elem->type = MB_CHAR;
! 3046: elem->opr.wch = re_string_wchar_at (regexp, re_string_cur_idx (regexp));
! 3047: re_string_skip_bytes (regexp, cur_char_size);
! 3048: return REG_NOERROR;
! 3049: }
! 3050: #endif /* RE_ENABLE_I18N */
! 3051: re_string_skip_bytes (regexp, token_len); /* Skip a token. */
! 3052: if (token->type == OP_OPEN_COLL_ELEM || token->type == OP_OPEN_CHAR_CLASS
! 3053: || token->type == OP_OPEN_EQUIV_CLASS)
! 3054: return parse_bracket_symbol (elem, regexp, token);
! 3055: elem->type = SB_CHAR;
! 3056: elem->opr.ch = token->opr.c;
! 3057: return REG_NOERROR;
! 3058: }
! 3059:
! 3060: /* Parse a bracket symbol in the bracket expression. Bracket symbols are
! 3061: such as [:<character_class>:], [.<collating_element>.], and
! 3062: [=<equivalent_class>=]. */
! 3063:
! 3064: static reg_errcode_t
! 3065: parse_bracket_symbol (elem, regexp, token)
! 3066: bracket_elem_t *elem;
! 3067: re_string_t *regexp;
! 3068: re_token_t *token;
! 3069: {
! 3070: unsigned char ch, delim = token->opr.c;
! 3071: int i = 0;
! 3072: for (;; ++i)
! 3073: {
! 3074: if (re_string_eoi(regexp) || i >= BRACKET_NAME_BUF_SIZE)
! 3075: return REG_EBRACK;
! 3076: if (token->type == OP_OPEN_CHAR_CLASS)
! 3077: ch = re_string_fetch_byte_case (regexp);
! 3078: else
! 3079: ch = re_string_fetch_byte (regexp);
! 3080: if (ch == delim && re_string_peek_byte (regexp, 0) == ']')
! 3081: break;
! 3082: elem->opr.name[i] = ch;
! 3083: }
! 3084: re_string_skip_bytes (regexp, 1);
! 3085: elem->opr.name[i] = '\0';
! 3086: switch (token->type)
! 3087: {
! 3088: case OP_OPEN_COLL_ELEM:
! 3089: elem->type = COLL_SYM;
! 3090: break;
! 3091: case OP_OPEN_EQUIV_CLASS:
! 3092: elem->type = EQUIV_CLASS;
! 3093: break;
! 3094: case OP_OPEN_CHAR_CLASS:
! 3095: elem->type = CHAR_CLASS;
! 3096: break;
! 3097: default:
! 3098: break;
! 3099: }
! 3100: return REG_NOERROR;
! 3101: }
! 3102:
! 3103: /* Helper function for parse_bracket_exp.
! 3104: Build the equivalence class which is represented by NAME.
! 3105: The result are written to MBCSET and SBCSET.
! 3106: EQUIV_CLASS_ALLOC is the allocated size of mbcset->equiv_classes,
! 3107: is a pointer argument sinse we may update it. */
! 3108:
! 3109: static reg_errcode_t
! 3110: #ifdef RE_ENABLE_I18N
! 3111: build_equiv_class (sbcset, mbcset, equiv_class_alloc, name)
! 3112: re_charset_t *mbcset;
! 3113: int *equiv_class_alloc;
! 3114: #else /* not RE_ENABLE_I18N */
! 3115: build_equiv_class (sbcset, name)
! 3116: #endif /* not RE_ENABLE_I18N */
! 3117: re_bitset_ptr_t sbcset;
! 3118: const unsigned char *name;
! 3119: {
! 3120: #if defined _LIBC && defined RE_ENABLE_I18N
! 3121: uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
! 3122: if (nrules != 0)
! 3123: {
! 3124: const int32_t *table, *indirect;
! 3125: const unsigned char *weights, *extra, *cp;
! 3126: unsigned char char_buf[2];
! 3127: int32_t idx1, idx2;
! 3128: unsigned int ch;
! 3129: size_t len;
! 3130: /* This #include defines a local function! */
! 3131: # include <locale/weight.h>
! 3132: /* Calculate the index for equivalence class. */
! 3133: cp = name;
! 3134: table = (const int32_t *) _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
! 3135: weights = (const unsigned char *) _NL_CURRENT (LC_COLLATE,
! 3136: _NL_COLLATE_WEIGHTMB);
! 3137: extra = (const unsigned char *) _NL_CURRENT (LC_COLLATE,
! 3138: _NL_COLLATE_EXTRAMB);
! 3139: indirect = (const int32_t *) _NL_CURRENT (LC_COLLATE,
! 3140: _NL_COLLATE_INDIRECTMB);
! 3141: idx1 = findidx (&cp);
! 3142: if (BE (idx1 == 0 || cp < name + strlen ((const char *) name), 0))
! 3143: /* This isn't a valid character. */
! 3144: return REG_ECOLLATE;
! 3145:
! 3146: /* Build single byte matcing table for this equivalence class. */
! 3147: char_buf[1] = (unsigned char) '\0';
! 3148: len = weights[idx1];
! 3149: for (ch = 0; ch < SBC_MAX; ++ch)
! 3150: {
! 3151: char_buf[0] = ch;
! 3152: cp = char_buf;
! 3153: idx2 = findidx (&cp);
! 3154: /*
! 3155: idx2 = table[ch];
! 3156: */
! 3157: if (idx2 == 0)
! 3158: /* This isn't a valid character. */
! 3159: continue;
! 3160: if (len == weights[idx2])
! 3161: {
! 3162: int cnt = 0;
! 3163: while (cnt <= len &&
! 3164: weights[idx1 + 1 + cnt] == weights[idx2 + 1 + cnt])
! 3165: ++cnt;
! 3166:
! 3167: if (cnt > len)
! 3168: bitset_set (sbcset, ch);
! 3169: }
! 3170: }
! 3171: /* Check whether the array has enough space. */
! 3172: if (*equiv_class_alloc == mbcset->nequiv_classes)
! 3173: {
! 3174: /* Not enough, realloc it. */
! 3175: /* +1 in case of mbcset->nequiv_classes is 0. */
! 3176: *equiv_class_alloc = 2 * mbcset->nequiv_classes + 1;
! 3177: /* Use realloc since the array is NULL if *alloc == 0. */
! 3178: mbcset->equiv_classes = re_realloc (mbcset->equiv_classes, int32_t,
! 3179: *equiv_class_alloc);
! 3180: if (BE (mbcset->equiv_classes == NULL, 0))
! 3181: return REG_ESPACE;
! 3182: }
! 3183: mbcset->equiv_classes[mbcset->nequiv_classes++] = idx1;
! 3184: }
! 3185: else
! 3186: #endif /* _LIBC && RE_ENABLE_I18N */
! 3187: {
! 3188: if (BE (strlen ((const char *) name) != 1, 0))
! 3189: return REG_ECOLLATE;
! 3190: bitset_set (sbcset, *name);
! 3191: }
! 3192: return REG_NOERROR;
! 3193: }
! 3194:
! 3195: /* Helper function for parse_bracket_exp.
! 3196: Build the character class which is represented by NAME.
! 3197: The result are written to MBCSET and SBCSET.
! 3198: CHAR_CLASS_ALLOC is the allocated size of mbcset->char_classes,
! 3199: is a pointer argument sinse we may update it. */
! 3200:
! 3201: static reg_errcode_t
! 3202: #ifdef RE_ENABLE_I18N
! 3203: build_charclass (sbcset, mbcset, char_class_alloc, class_name, syntax)
! 3204: re_charset_t *mbcset;
! 3205: int *char_class_alloc;
! 3206: #else /* not RE_ENABLE_I18N */
! 3207: build_charclass (sbcset, class_name, syntax)
! 3208: #endif /* not RE_ENABLE_I18N */
! 3209: re_bitset_ptr_t sbcset;
! 3210: const unsigned char *class_name;
! 3211: reg_syntax_t syntax;
! 3212: {
! 3213: int i;
! 3214: const char *name = (const char *) class_name;
! 3215:
! 3216: /* In case of REG_ICASE "upper" and "lower" match the both of
! 3217: upper and lower cases. */
! 3218: if ((syntax & RE_ICASE)
! 3219: && (strcmp (name, "upper") == 0 || strcmp (name, "lower") == 0))
! 3220: name = "alpha";
! 3221:
! 3222: #ifdef RE_ENABLE_I18N
! 3223: /* Check the space of the arrays. */
! 3224: if (*char_class_alloc == mbcset->nchar_classes)
! 3225: {
! 3226: /* Not enough, realloc it. */
! 3227: /* +1 in case of mbcset->nchar_classes is 0. */
! 3228: *char_class_alloc = 2 * mbcset->nchar_classes + 1;
! 3229: /* Use realloc since array is NULL if *alloc == 0. */
! 3230: mbcset->char_classes = re_realloc (mbcset->char_classes, wctype_t,
! 3231: *char_class_alloc);
! 3232: if (BE (mbcset->char_classes == NULL, 0))
! 3233: return REG_ESPACE;
! 3234: }
! 3235: mbcset->char_classes[mbcset->nchar_classes++] = __wctype (name);
! 3236: #endif /* RE_ENABLE_I18N */
! 3237:
! 3238: #define BUILD_CHARCLASS_LOOP(ctype_func)\
! 3239: for (i = 0; i < SBC_MAX; ++i) \
! 3240: { \
! 3241: if (ctype_func (i)) \
! 3242: bitset_set (sbcset, i); \
! 3243: }
! 3244:
! 3245: if (strcmp (name, "alnum") == 0)
! 3246: BUILD_CHARCLASS_LOOP (isalnum)
! 3247: else if (strcmp (name, "cntrl") == 0)
! 3248: BUILD_CHARCLASS_LOOP (iscntrl)
! 3249: else if (strcmp (name, "lower") == 0)
! 3250: BUILD_CHARCLASS_LOOP (islower)
! 3251: else if (strcmp (name, "space") == 0)
! 3252: BUILD_CHARCLASS_LOOP (isspace)
! 3253: else if (strcmp (name, "alpha") == 0)
! 3254: BUILD_CHARCLASS_LOOP (isalpha)
! 3255: else if (strcmp (name, "digit") == 0)
! 3256: BUILD_CHARCLASS_LOOP (isdigit)
! 3257: else if (strcmp (name, "print") == 0)
! 3258: BUILD_CHARCLASS_LOOP (isprint)
! 3259: else if (strcmp (name, "upper") == 0)
! 3260: BUILD_CHARCLASS_LOOP (isupper)
! 3261: else if (strcmp (name, "blank") == 0)
! 3262: BUILD_CHARCLASS_LOOP (isblank)
! 3263: else if (strcmp (name, "graph") == 0)
! 3264: BUILD_CHARCLASS_LOOP (isgraph)
! 3265: else if (strcmp (name, "punct") == 0)
! 3266: BUILD_CHARCLASS_LOOP (ispunct)
! 3267: else if (strcmp (name, "xdigit") == 0)
! 3268: BUILD_CHARCLASS_LOOP (isxdigit)
! 3269: else
! 3270: return REG_ECTYPE;
! 3271:
! 3272: return REG_NOERROR;
! 3273: }
! 3274:
! 3275: static bin_tree_t *
! 3276: build_word_op (dfa, not, err)
! 3277: re_dfa_t *dfa;
! 3278: int not;
! 3279: reg_errcode_t *err;
! 3280: {
! 3281: re_bitset_ptr_t sbcset;
! 3282: #ifdef RE_ENABLE_I18N
! 3283: re_charset_t *mbcset;
! 3284: int alloc = 0;
! 3285: #else /* not RE_ENABLE_I18N */
! 3286: int non_match = 0;
! 3287: #endif /* not RE_ENABLE_I18N */
! 3288: reg_errcode_t ret;
! 3289: re_token_t br_token;
! 3290: bin_tree_t *tree;
! 3291: int new_idx;
! 3292:
! 3293: sbcset = (re_bitset_ptr_t) calloc (sizeof (unsigned int), BITSET_UINTS);
! 3294: #ifdef RE_ENABLE_I18N
! 3295: mbcset = (re_charset_t *) calloc (sizeof (re_charset_t), 1);
! 3296: #endif /* RE_ENABLE_I18N */
! 3297:
! 3298: #ifdef RE_ENABLE_I18N
! 3299: if (BE (sbcset == NULL || mbcset == NULL, 0))
! 3300: #else /* not RE_ENABLE_I18N */
! 3301: if (BE (sbcset == NULL, 0))
! 3302: #endif /* not RE_ENABLE_I18N */
! 3303: {
! 3304: *err = REG_ESPACE;
! 3305: return NULL;
! 3306: }
! 3307:
! 3308: if (not)
! 3309: {
! 3310: #ifdef RE_ENABLE_I18N
! 3311: int i;
! 3312: /*
! 3313: if (syntax & RE_HAT_LISTS_NOT_NEWLINE)
! 3314: bitset_set(cset->sbcset, '\0');
! 3315: */
! 3316: mbcset->non_match = 1;
! 3317: if (MB_CUR_MAX > 1)
! 3318: for (i = 0; i < SBC_MAX; ++i)
! 3319: if (__btowc (i) == WEOF)
! 3320: bitset_set (sbcset, i);
! 3321: #else /* not RE_ENABLE_I18N */
! 3322: non_match = 1;
! 3323: #endif /* not RE_ENABLE_I18N */
! 3324: }
! 3325:
! 3326: /* We don't care the syntax in this case. */
! 3327: ret = build_charclass (sbcset,
! 3328: #ifdef RE_ENABLE_I18N
! 3329: mbcset, &alloc,
! 3330: #endif /* RE_ENABLE_I18N */
! 3331: (const unsigned char *) "alpha", 0);
! 3332:
! 3333: if (BE (ret != REG_NOERROR, 0))
! 3334: {
! 3335: re_free (sbcset);
! 3336: #ifdef RE_ENABLE_I18N
! 3337: free_charset (mbcset);
! 3338: #endif /* RE_ENABLE_I18N */
! 3339: *err = ret;
! 3340: return NULL;
! 3341: }
! 3342: /* \w match '_' also. */
! 3343: bitset_set (sbcset, '_');
! 3344:
! 3345: /* If it is non-matching list. */
! 3346: #ifdef RE_ENABLE_I18N
! 3347: if (mbcset->non_match)
! 3348: #else /* not RE_ENABLE_I18N */
! 3349: if (non_match)
! 3350: #endif /* not RE_ENABLE_I18N */
! 3351: bitset_not (sbcset);
! 3352:
! 3353: /* Build a tree for simple bracket. */
! 3354: br_token.type = SIMPLE_BRACKET;
! 3355: br_token.opr.sbcset = sbcset;
! 3356: new_idx = re_dfa_add_node (dfa, br_token, 0);
! 3357: tree = create_tree (NULL, NULL, 0, new_idx);
! 3358: if (BE (new_idx == -1 || tree == NULL, 0))
! 3359: goto build_word_op_espace;
! 3360:
! 3361: #ifdef RE_ENABLE_I18N
! 3362: if (MB_CUR_MAX > 1)
! 3363: {
! 3364: re_token_t alt_token;
! 3365: bin_tree_t *mbc_tree;
! 3366: /* Build a tree for complex bracket. */
! 3367: br_token.type = COMPLEX_BRACKET;
! 3368: br_token.opr.mbcset = mbcset;
! 3369: dfa->has_mb_node = 1;
! 3370: new_idx = re_dfa_add_node (dfa, br_token, 0);
! 3371: mbc_tree = create_tree (NULL, NULL, 0, new_idx);
! 3372: if (BE (new_idx == -1 || mbc_tree == NULL, 0))
! 3373: goto build_word_op_espace;
! 3374: /* Then join them by ALT node. */
! 3375: alt_token.type = OP_ALT;
! 3376: new_idx = re_dfa_add_node (dfa, alt_token, 0);
! 3377: tree = create_tree (tree, mbc_tree, 0, new_idx);
! 3378: if (BE (new_idx != -1 && mbc_tree != NULL, 1))
! 3379: return tree;
! 3380: }
! 3381: else
! 3382: {
! 3383: free_charset (mbcset);
! 3384: return tree;
! 3385: }
! 3386: #else /* not RE_ENABLE_I18N */
! 3387: return tree;
! 3388: #endif /* not RE_ENABLE_I18N */
! 3389:
! 3390: build_word_op_espace:
! 3391: re_free (sbcset);
! 3392: #ifdef RE_ENABLE_I18N
! 3393: free_charset (mbcset);
! 3394: #endif /* RE_ENABLE_I18N */
! 3395: *err = REG_ESPACE;
! 3396: return NULL;
! 3397: }
! 3398:
! 3399: /* This is intended for the expressions like "a{1,3}".
! 3400: Fetch a number from `input', and return the number.
! 3401: Return -1, if the number field is empty like "{,1}".
! 3402: Return -2, If an error is occured. */
! 3403:
! 3404: static int
! 3405: fetch_number (input, token, syntax)
! 3406: re_string_t *input;
! 3407: re_token_t *token;
! 3408: reg_syntax_t syntax;
! 3409: {
! 3410: int num = -1;
! 3411: unsigned char c;
! 3412: while (1)
! 3413: {
! 3414: *token = fetch_token (input, syntax);
! 3415: c = token->opr.c;
! 3416: if (BE (token->type == END_OF_RE, 0))
! 3417: return -2;
! 3418: if (token->type == OP_CLOSE_DUP_NUM || c == ',')
! 3419: break;
! 3420: num = ((token->type != CHARACTER || c < '0' || '9' < c || num == -2)
! 3421: ? -2 : ((num == -1) ? c - '0' : num * 10 + c - '0'));
! 3422: num = (num > RE_DUP_MAX) ? -2 : num;
! 3423: }
! 3424: return num;
! 3425: }
! 3426:
! 3427: #ifdef RE_ENABLE_I18N
! 3428: static void
! 3429: free_charset (re_charset_t *cset)
! 3430: {
! 3431: re_free (cset->mbchars);
! 3432: # ifdef _LIBC
! 3433: re_free (cset->coll_syms);
! 3434: re_free (cset->equiv_classes);
! 3435: re_free (cset->range_starts);
! 3436: re_free (cset->range_ends);
! 3437: # endif
! 3438: re_free (cset->char_classes);
! 3439: re_free (cset);
! 3440: }
! 3441: #endif /* RE_ENABLE_I18N */
! 3442:
! 3443: /* Functions for binary tree operation. */
! 3444:
! 3445: /* Create a node of tree.
! 3446: Note: This function automatically free left and right if malloc fails. */
! 3447:
! 3448: static bin_tree_t *
! 3449: create_tree (left, right, type, index)
! 3450: bin_tree_t *left;
! 3451: bin_tree_t *right;
! 3452: re_token_type_t type;
! 3453: int index;
! 3454: {
! 3455: bin_tree_t *tree;
! 3456: tree = re_malloc (bin_tree_t, 1);
! 3457: if (BE (tree == NULL, 0))
! 3458: {
! 3459: free_bin_tree (left);
! 3460: free_bin_tree (right);
! 3461: return NULL;
! 3462: }
! 3463: tree->parent = NULL;
! 3464: tree->left = left;
! 3465: tree->right = right;
! 3466: tree->type = type;
! 3467: tree->node_idx = index;
! 3468: tree->first = -1;
! 3469: tree->next = -1;
! 3470: re_node_set_init_empty (&tree->eclosure);
! 3471:
! 3472: if (left != NULL)
! 3473: left->parent = tree;
! 3474: if (right != NULL)
! 3475: right->parent = tree;
! 3476: return tree;
! 3477: }
! 3478:
! 3479: /* Free the sub tree pointed by TREE. */
! 3480:
! 3481: static void
! 3482: free_bin_tree (tree)
! 3483: bin_tree_t *tree;
! 3484: {
! 3485: if (tree == NULL)
! 3486: return;
! 3487: /*re_node_set_free (&tree->eclosure);*/
! 3488: free_bin_tree (tree->left);
! 3489: free_bin_tree (tree->right);
! 3490: re_free (tree);
! 3491: }
! 3492:
! 3493: /* Duplicate the node SRC, and return new node. */
! 3494:
! 3495: static bin_tree_t *
! 3496: duplicate_tree (src, dfa)
! 3497: const bin_tree_t *src;
! 3498: re_dfa_t *dfa;
! 3499: {
! 3500: bin_tree_t *left = NULL, *right = NULL, *new_tree;
! 3501: int new_node_idx;
! 3502: /* Since node indies must be according to Post-order of the tree,
! 3503: we must duplicate the left at first. */
! 3504: if (src->left != NULL)
! 3505: {
! 3506: left = duplicate_tree (src->left, dfa);
! 3507: if (left == NULL)
! 3508: return NULL;
! 3509: }
! 3510:
! 3511: /* Secondaly, duplicate the right. */
! 3512: if (src->right != NULL)
! 3513: {
! 3514: right = duplicate_tree (src->right, dfa);
! 3515: if (right == NULL)
! 3516: {
! 3517: free_bin_tree (left);
! 3518: return NULL;
! 3519: }
! 3520: }
! 3521:
! 3522: /* At last, duplicate itself. */
! 3523: if (src->type == NON_TYPE)
! 3524: {
! 3525: new_node_idx = re_dfa_add_node (dfa, dfa->nodes[src->node_idx], 0);
! 3526: dfa->nodes[new_node_idx].duplicated = 1;
! 3527: if (BE (new_node_idx == -1, 0))
! 3528: {
! 3529: free_bin_tree (left);
! 3530: free_bin_tree (right);
! 3531: return NULL;
! 3532: }
! 3533: }
! 3534: else
! 3535: new_node_idx = src->type;
! 3536:
! 3537: new_tree = create_tree (left, right, src->type, new_node_idx);
! 3538: if (BE (new_tree == NULL, 0))
! 3539: {
! 3540: free_bin_tree (left);
! 3541: free_bin_tree (right);
! 3542: }
! 3543: return new_tree;
! 3544: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to regcomp.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