regcomp.c File Reference

Go to the source code of this file.

Defines
#define	REG_NOERROR_IDX   0
#define	REG_NOMATCH_IDX   (REG_NOERROR_IDX + sizeof "Success")
#define	REG_BADPAT_IDX   (REG_NOMATCH_IDX + sizeof "No match")
#define	REG_ECOLLATE_IDX   (REG_BADPAT_IDX + sizeof "Invalid regular expression")
#define	REG_ECTYPE_IDX   (REG_ECOLLATE_IDX + sizeof "Invalid collation character")
#define	REG_EESCAPE_IDX   (REG_ECTYPE_IDX + sizeof "Invalid character class name")
#define	REG_ESUBREG_IDX   (REG_EESCAPE_IDX + sizeof "Trailing backslash")
#define	REG_EBRACK_IDX   (REG_ESUBREG_IDX + sizeof "Invalid back reference")
#define	REG_EPAREN_IDX   (REG_EBRACK_IDX + sizeof "Unmatched [ or [^")
#define	REG_EBRACE_IDX   (REG_EPAREN_IDX + sizeof "Unmatched ( or \\(")
#define	REG_BADBR_IDX   (REG_EBRACE_IDX + sizeof "Unmatched \\{")
#define	REG_ERANGE_IDX   (REG_BADBR_IDX + sizeof "Invalid content of \\{\\}")
#define	REG_ESPACE_IDX   (REG_ERANGE_IDX + sizeof "Invalid range end")
#define	REG_BADRPT_IDX   (REG_ESPACE_IDX + sizeof "Memory exhausted")
#define	REG_EEND_IDX   (REG_BADRPT_IDX + sizeof "Invalid preceding regular expression")
#define	REG_ESIZE_IDX   (REG_EEND_IDX + sizeof "Premature end of regular expression")
#define	REG_ERPAREN_IDX   (REG_ESIZE_IDX + sizeof "Regular expression too big")
#define	BRACKET_NAME_BUF_SIZE   32
#define	BUILD_CHARCLASS_LOOP(ctype_func)
Functions
static reg_errcode_t re_compile_internal	_RE_ARGS ((regex_t *preg, const char *pattern, int length, reg_syntax_t syntax))
const char *	re_compile_pattern (char *pattern, size_t length, struct re_pattern_buffer *bufp) const
reg_syntax_t	re_set_syntax (reg_syntax_t syntax)
int	re_compile_fastmap (struct re_pattern_buffer *bufp)
static void	re_set_fastmap (char *fastmap, int icase, int ch)
static void	re_compile_fastmap_iter (regex_t *bufp, const re_dfastate_t *init_state, char *fastmap)
int	regcomp (regex_t *__restrict preg, const char *__restrict pattern, int cflags)
size_t	regerror (int errcode, const regex_t *preg, char *errbuf, size_t errbuf_size)
static void	free_dfa_content (re_dfa_t *dfa)
void	regfree (regex_t *preg)
static reg_errcode_t	re_compile_internal (regex_t *preg, const char *pattern, int length, reg_syntax_t syntax)
static reg_errcode_t	init_dfa (re_dfa_t *dfa, int pat_len)
static reg_errcode_t	init_word_char (re_dfa_t *dfa)
static void	free_workarea_compile (regex_t *preg)
static reg_errcode_t	create_initial_state (re_dfa_t *dfa)
static reg_errcode_t	analyze (re_dfa_t *dfa)
static reg_errcode_t	analyze_tree (re_dfa_t *dfa, bin_tree_t *node)
static void	calc_first (re_dfa_t *dfa, bin_tree_t *node)
static void	calc_next (re_dfa_t *dfa, bin_tree_t *node)
static void	calc_epsdest (re_dfa_t *dfa, bin_tree_t *node)
static reg_errcode_t	duplicate_node_closure (re_dfa_t *dfa, int top_org_node, int top_clone_node, int root_node, unsigned int init_constraint)
static int	search_duplicated_node (re_dfa_t *dfa, int org_node, unsigned int constraint)
static reg_errcode_t	duplicate_node (int *new_idx, re_dfa_t *dfa, int org_idx, unsigned int constraint)
static void	calc_inveclosure (re_dfa_t *dfa)
static reg_errcode_t	calc_eclosure (re_dfa_t *dfa)
static reg_errcode_t	calc_eclosure_iter (re_node_set *new_set, re_dfa_t *dfa, int node, int root)
static re_token_t	fetch_token (re_string_t *input, reg_syntax_t syntax)
static int	peek_token (re_token_t *token, re_string_t *input, reg_syntax_t syntax)
static int	peek_token_bracket (re_token_t *token, re_string_t *input, reg_syntax_t syntax)
static bin_tree_t *	parse (re_string_t *regexp, regex_t *preg, reg_syntax_t syntax, reg_errcode_t *err)
static bin_tree_t *	parse_reg_exp (re_string_t *regexp, regex_t *preg, re_token_t *token, reg_syntax_t syntax, int nest, reg_errcode_t *err)
static bin_tree_t *	parse_branch (re_string_t *regexp, regex_t *preg, re_token_t *token, reg_syntax_t syntax, int nest, reg_errcode_t *err)
static bin_tree_t *	parse_expression (re_string_t *regexp, regex_t *preg, re_token_t *token, reg_syntax_t syntax, int nest, reg_errcode_t *err)
static bin_tree_t *	parse_sub_exp (re_string_t *regexp, regex_t *preg, re_token_t *token, reg_syntax_t syntax, int nest, reg_errcode_t *err)
static bin_tree_t *	parse_dup_op (bin_tree_t *dup_elem, re_string_t *regexp, re_dfa_t *dfa, re_token_t *token, reg_syntax_t syntax, reg_errcode_t *err)
static reg_errcode_t	build_range_exp (re_bitset_ptr_t sbcset, bracket_elem_t *start_elem, bracket_elem_t *end_elem)
static reg_errcode_t	build_collating_symbol (re_bitset_ptr_t sbcset, const unsigned char *name)
static bin_tree_t *	parse_bracket_exp (re_string_t *regexp, re_dfa_t *dfa, re_token_t *token, reg_syntax_t syntax, reg_errcode_t *err)
static reg_errcode_t	parse_bracket_element (bracket_elem_t *elem, re_string_t *regexp, re_token_t *token, int token_len, re_dfa_t *dfa, reg_syntax_t syntax)
static reg_errcode_t	parse_bracket_symbol (bracket_elem_t *elem, re_string_t *regexp, re_token_t *token)
static reg_errcode_t	build_equiv_class (re_bitset_ptr_t sbcset, const unsigned char *name)
static reg_errcode_t	build_charclass (RE_TRANSLATE_TYPE trans, re_bitset_ptr_t sbcset, const unsigned char *class_name, reg_syntax_t syntax)
static bin_tree_t *	build_word_op (re_dfa_t *dfa, RE_TRANSLATE_TYPE trans, int not, reg_errcode_t *err)
static int	fetch_number (re_string_t *input, re_token_t *token, reg_syntax_t syntax)
static bin_tree_t *	create_tree (bin_tree_t *left, bin_tree_t *right, re_token_type_t type, int index)
static void	free_bin_tree (bin_tree_t *tree)
static bin_tree_t *	duplicate_tree (bin_tree_t *src, re_dfa_t *dfa) const
Variables
const char __re_error_msgid[]	attribute_hidden
reg_syntax_t	re_syntax_options

---

Define Documentation

#define BRACKET_NAME_BUF_SIZE   32

Definition at line 2359 of file regcomp.c. Referenced by parse_bracket_exp(), and parse_bracket_symbol().

#define BUILD_CHARCLASS_LOOP (  ctype_func   )

Value: for (i = 0; i < SBC_MAX; ++i) \ { \ if (ctype_func (i)) \ { \ int ch = trans ? trans[i] : i; \ bitset_set (sbcset, ch); \ } \ } Referenced by build_charclass().

#define REG_BADBR_IDX   (REG_EBRACE_IDX + sizeof "Unmatched \\{")

#define REG_BADPAT_IDX   (REG_NOMATCH_IDX + sizeof "No match")

#define REG_BADRPT_IDX   (REG_ESPACE_IDX + sizeof "Memory exhausted")

#define REG_EBRACE_IDX   (REG_EPAREN_IDX + sizeof "Unmatched ( or \\(")

#define REG_EBRACK_IDX   (REG_ESUBREG_IDX + sizeof "Invalid back reference")

#define REG_ECOLLATE_IDX   (REG_BADPAT_IDX + sizeof "Invalid regular expression")

#define REG_ECTYPE_IDX   (REG_ECOLLATE_IDX + sizeof "Invalid collation character")

#define REG_EEND_IDX   (REG_BADRPT_IDX + sizeof "Invalid preceding regular expression")

#define REG_EESCAPE_IDX   (REG_ECTYPE_IDX + sizeof "Invalid character class name")

#define REG_EPAREN_IDX   (REG_EBRACK_IDX + sizeof "Unmatched [ or [^")

#define REG_ERANGE_IDX   (REG_BADBR_IDX + sizeof "Invalid content of \\{\\}")

#define REG_ERPAREN_IDX   (REG_ESIZE_IDX + sizeof "Regular expression too big")

#define REG_ESIZE_IDX   (REG_EEND_IDX + sizeof "Premature end of regular expression")

#define REG_ESPACE_IDX   (REG_ERANGE_IDX + sizeof "Invalid range end")

#define REG_ESUBREG_IDX   (REG_EESCAPE_IDX + sizeof "Trailing backslash")

#define REG_NOERROR_IDX   0

#define REG_NOMATCH_IDX   (REG_NOERROR_IDX + sizeof "Success")

---

Function Documentation

static reg_errcode_t re_compile_internal _RE_ARGS (  (regex_t *preg, const char *pattern, int length, reg_syntax_t syntax)   )  [static]

static reg_errcode_t analyze (  re_dfa_t *  dfa  )  [static]

Definition at line 917 of file regcomp.c. References analyze_tree(), BE, calc_eclosure(), calc_inveclosure(), i, NULL, re_malloc, re_node_set_init_empty, REG_ESPACE, and REG_NOERROR. Referenced by re_compile_internal(). { int i; reg_errcode_t ret; /* Allocate arrays. */ dfa->nexts = re_malloc (int, dfa->nodes_alloc); dfa->org_indices = re_malloc (int, dfa->nodes_alloc); dfa->edests = re_malloc (re_node_set, dfa->nodes_alloc); dfa->eclosures = re_malloc (re_node_set, dfa->nodes_alloc); dfa->inveclosures = re_malloc (re_node_set, dfa->nodes_alloc); if (BE (dfa->nexts == NULL || dfa->org_indices == NULL || dfa->edests == NULL || dfa->eclosures == NULL || dfa->inveclosures == NULL, 0)) return REG_ESPACE; /* Initialize them. */ for (i = 0; i < dfa->nodes_len; ++i) { dfa->nexts[i] = -1; re_node_set_init_empty (dfa->edests + i); re_node_set_init_empty (dfa->eclosures + i); re_node_set_init_empty (dfa->inveclosures + i); } ret = analyze_tree (dfa, dfa->str_tree); if (BE (ret == REG_NOERROR, 1)) { ret = calc_eclosure (dfa); if (ret == REG_NOERROR) calc_inveclosure (dfa); } return ret; }

static reg_errcode_t analyze_tree (  re_dfa_t *  dfa, bin_tree_t *  node )  [static]

Definition at line 956 of file regcomp.c. References BE, calc_epsdest(), calc_first(), calc_next(), bin_tree_t::eclosure, bin_tree_t::first, bin_tree_t::left, re_node_set::nelem, bin_tree_t::next, NULL, REG_NOERROR, and bin_tree_t::right. Referenced by analyze(). { reg_errcode_t ret; if (node->first == -1) calc_first (dfa, node); if (node->next == -1) calc_next (dfa, node); if (node->eclosure.nelem == 0) calc_epsdest (dfa, node); /* Calculate "first" etc. for the left child. */ if (node->left != NULL) { ret = analyze_tree (dfa, node->left); if (BE (ret != REG_NOERROR, 0)) return ret; } /* Calculate "first" etc. for the right child. */ if (node->right != NULL) { ret = analyze_tree (dfa, node->right); if (BE (ret != REG_NOERROR, 0)) return ret; } return REG_NOERROR; }

static reg_errcode_t build_charclass (  RE_TRANSLATE_TYPE  trans, re_bitset_ptr_t  sbcset, const unsigned char *  class_name, reg_syntax_t  syntax )  [static]

Definition at line 3217 of file regcomp.c. References __wctype, BE, BUILD_CHARCLASS_LOOP, i, isblank, name, NULL, RE_ICASE, re_realloc, REG_ECTYPE, REG_ESPACE, and REG_NOERROR. Referenced by build_word_op(), and parse_bracket_exp(). { int i; const char *name = (const char *) class_name; /* In case of REG_ICASE "upper" and "lower" match the both of upper and lower cases. */ if ((syntax & RE_ICASE) && (strcmp (name, "upper") == 0 || strcmp (name, "lower") == 0)) name = "alpha"; #ifdef RE_ENABLE_I18N /* Check the space of the arrays. */ if (*char_class_alloc == mbcset->nchar_classes) { /* Not enough, realloc it. */ /* +1 in case of mbcset->nchar_classes is 0. */ *char_class_alloc = 2 * mbcset->nchar_classes + 1; /* Use realloc since array is NULL if *alloc == 0. */ mbcset->char_classes = re_realloc (mbcset->char_classes, wctype_t, *char_class_alloc); if (BE (mbcset->char_classes == NULL, 0)) return REG_ESPACE; } mbcset->char_classes[mbcset->nchar_classes++] = __wctype (name); #endif /* RE_ENABLE_I18N */ #define BUILD_CHARCLASS_LOOP(ctype_func)\ for (i = 0; i < SBC_MAX; ++i) \ { \ if (ctype_func (i)) \ { \ int ch = trans ? trans[i] : i; \ bitset_set (sbcset, ch); \ } \ } if (strcmp (name, "alnum") == 0) BUILD_CHARCLASS_LOOP (isalnum) else if (strcmp (name, "cntrl") == 0) BUILD_CHARCLASS_LOOP (iscntrl) else if (strcmp (name, "lower") == 0) BUILD_CHARCLASS_LOOP (islower) else if (strcmp (name, "space") == 0) BUILD_CHARCLASS_LOOP (isspace) else if (strcmp (name, "alpha") == 0) BUILD_CHARCLASS_LOOP (isalpha) else if (strcmp (name, "digit") == 0) BUILD_CHARCLASS_LOOP (isdigit) else if (strcmp (name, "print") == 0) BUILD_CHARCLASS_LOOP (isprint) else if (strcmp (name, "upper") == 0) BUILD_CHARCLASS_LOOP (isupper) else if (strcmp (name, "blank") == 0) BUILD_CHARCLASS_LOOP (isblank) else if (strcmp (name, "graph") == 0) BUILD_CHARCLASS_LOOP (isgraph) else if (strcmp (name, "punct") == 0) BUILD_CHARCLASS_LOOP (ispunct) else if (strcmp (name, "xdigit") == 0) BUILD_CHARCLASS_LOOP (isxdigit) else return REG_ECTYPE; return REG_NOERROR; }

static reg_errcode_t build_collating_symbol (  re_bitset_ptr_t  sbcset, const unsigned char *  name )  [static]

Definition at line 2485 of file regcomp.c. References BE, bitset_set, REG_ECOLLATE, and REG_NOERROR. Referenced by parse_bracket_exp(). { size_t name_len = strlen ((const char *) name); if (BE (name_len != 1, 0)) return REG_ECOLLATE; else { bitset_set (sbcset, name[0]); return REG_NOERROR; } }

static reg_errcode_t build_equiv_class (  re_bitset_ptr_t  sbcset, const unsigned char *  name )  [static]

Definition at line 3125 of file regcomp.c. References BE, bitset_set, len, NULL, re_realloc, REG_ECOLLATE, REG_ESPACE, REG_NOERROR, and SBC_MAX. Referenced by parse_bracket_exp(). { #if defined _LIBC && defined RE_ENABLE_I18N uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES); if (nrules != 0) { const int32_t *table, *indirect; const unsigned char *weights, *extra, *cp; unsigned char char_buf[2]; int32_t idx1, idx2; unsigned int ch; size_t len; /* This #include defines a local function! */ # include <locale/weight.h> /* Calculate the index for equivalence class. */ cp = name; table = (const int32_t *) _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB); weights = (const unsigned char *) _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTMB); extra = (const unsigned char *) _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB); indirect = (const int32_t *) _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTMB); idx1 = findidx (&cp); if (BE (idx1 == 0 || cp < name + strlen ((const char *) name), 0)) /* This isn't a valid character. */ return REG_ECOLLATE; /* Build single byte matcing table for this equivalence class. */ char_buf[1] = (unsigned char) '\0'; len = weights[idx1]; for (ch = 0; ch < SBC_MAX; ++ch) { char_buf[0] = ch; cp = char_buf; idx2 = findidx (&cp); /* idx2 = table[ch]; */ if (idx2 == 0) /* This isn't a valid character. */ continue; if (len == weights[idx2]) { int cnt = 0; while (cnt <= len && weights[idx1 + 1 + cnt] == weights[idx2 + 1 + cnt]) ++cnt; if (cnt > len) bitset_set (sbcset, ch); } } /* Check whether the array has enough space. */ if (*equiv_class_alloc == mbcset->nequiv_classes) { /* Not enough, realloc it. */ /* +1 in case of mbcset->nequiv_classes is 0. */ *equiv_class_alloc = 2 * mbcset->nequiv_classes + 1; /* Use realloc since the array is NULL if *alloc == 0. */ mbcset->equiv_classes = re_realloc (mbcset->equiv_classes, int32_t, *equiv_class_alloc); if (BE (mbcset->equiv_classes == NULL, 0)) return REG_ESPACE; } mbcset->equiv_classes[mbcset->nequiv_classes++] = idx1; } else #endif /* _LIBC && RE_ENABLE_I18N */ { if (BE (strlen ((const char *) name) != 1, 0)) return REG_ECOLLATE; bitset_set (sbcset, *name); } return REG_NOERROR; }

static reg_errcode_t build_range_exp (  re_bitset_ptr_t  sbcset, bracket_elem_t *  start_elem, bracket_elem_t *  end_elem )  [static]

Definition at line 2375 of file regcomp.c. References __btowc, BE, bitset_set, CHAR_CLASS, COLL_SYM, EQUIV_CLASS, NULL, bracket_elem_t::opr, re_realloc, REG_ECOLLATE, REG_ERANGE, REG_ESPACE, REG_NOERROR, SB_CHAR, SBC_MAX, and bracket_elem_t::type. Referenced by parse_bracket_exp(). { unsigned int start_ch, end_ch; /* Equivalence Classes and Character Classes can't be a range start/end. */ if (BE (start_elem->type == EQUIV_CLASS || start_elem->type == CHAR_CLASS || end_elem->type == EQUIV_CLASS || end_elem->type == CHAR_CLASS, 0)) return REG_ERANGE; /* We can handle no multi character collating elements without libc support. */ if (BE ((start_elem->type == COLL_SYM && strlen ((char *) start_elem->opr.name) > 1) || (end_elem->type == COLL_SYM && strlen ((char *) end_elem->opr.name) > 1), 0)) return REG_ECOLLATE; # ifdef RE_ENABLE_I18N { wchar_t wc, start_wc, end_wc; wchar_t cmp_buf[6] = {L'\0', L'\0', L'\0', L'\0', L'\0', L'\0'}; start_ch = ((start_elem->type == SB_CHAR) ? start_elem->opr.ch : ((start_elem->type == COLL_SYM) ? start_elem->opr.name[0] : 0)); end_ch = ((end_elem->type == SB_CHAR) ? end_elem->opr.ch : ((end_elem->type == COLL_SYM) ? end_elem->opr.name[0] : 0)); start_wc = ((start_elem->type == SB_CHAR || start_elem->type == COLL_SYM) ? __btowc (start_ch) : start_elem->opr.wch); end_wc = ((end_elem->type == SB_CHAR || end_elem->type == COLL_SYM) ? __btowc (end_ch) : end_elem->opr.wch); cmp_buf[0] = start_wc; cmp_buf[4] = end_wc; if (wcscoll (cmp_buf, cmp_buf + 4) > 0) return REG_ERANGE; /* Check the space of the arrays. */ if (*range_alloc == mbcset->nranges) { /* There are not enough space, need realloc. */ wchar_t *new_array_start, *new_array_end; int new_nranges; /* +1 in case of mbcset->nranges is 0. */ new_nranges = 2 * mbcset->nranges + 1; /* Use realloc since mbcset->range_starts and mbcset->range_ends are NULL if *range_alloc == 0. */ new_array_start = re_realloc (mbcset->range_starts, wchar_t, new_nranges); new_array_end = re_realloc (mbcset->range_ends, wchar_t, new_nranges); if (BE (new_array_start == NULL || new_array_end == NULL, 0)) return REG_ESPACE; mbcset->range_starts = new_array_start; mbcset->range_ends = new_array_end; *range_alloc = new_nranges; } mbcset->range_starts[mbcset->nranges] = start_wc; mbcset->range_ends[mbcset->nranges++] = end_wc; /* Build the table for single byte characters. */ for (wc = 0; wc <= SBC_MAX; ++wc) { cmp_buf[2] = wc; if (wcscoll (cmp_buf, cmp_buf + 2) <= 0 && wcscoll (cmp_buf + 2, cmp_buf + 4) <= 0) bitset_set (sbcset, wc); } } # else /* not RE_ENABLE_I18N */ { unsigned int ch; start_ch = ((start_elem->type == SB_CHAR ) ? start_elem->opr.ch : ((start_elem->type == COLL_SYM) ? start_elem->opr.name[0] : 0)); end_ch = ((end_elem->type == SB_CHAR ) ? end_elem->opr.ch : ((end_elem->type == COLL_SYM) ? end_elem->opr.name[0] : 0)); if (start_ch > end_ch) return REG_ERANGE; /* Build the table for single byte characters. */ for (ch = 0; ch <= SBC_MAX; ++ch) if (start_ch <= ch && ch <= end_ch) bitset_set (sbcset, ch); } # endif /* not RE_ENABLE_I18N */ return REG_NOERROR; }

static bin_tree_t* build_word_op (  re_dfa_t *  dfa, RE_TRANSLATE_TYPE  trans, int  not, reg_errcode_t *  err )  [static]

Definition at line 3290 of file regcomp.c. References __btowc, BE, bitset_not(), bitset_set, BITSET_UINTS, build_charclass(), create_tree(), i, NULL, OP_ALT, re_token_t::opr, re_dfa_add_node(), re_free, REG_ESPACE, REG_NOERROR, SBC_MAX, SIMPLE_BRACKET, and re_token_t::type. Referenced by parse_expression(). { re_bitset_ptr_t sbcset; #ifdef RE_ENABLE_I18N re_charset_t *mbcset; int alloc = 0; #else /* not RE_ENABLE_I18N */ int non_match = 0; #endif /* not RE_ENABLE_I18N */ reg_errcode_t ret; re_token_t br_token; bin_tree_t *tree; int new_idx; sbcset = (re_bitset_ptr_t) calloc (sizeof (unsigned int), BITSET_UINTS); #ifdef RE_ENABLE_I18N mbcset = (re_charset_t *) calloc (sizeof (re_charset_t), 1); #endif /* RE_ENABLE_I18N */ #ifdef RE_ENABLE_I18N if (BE (sbcset == NULL || mbcset == NULL, 0)) #else /* not RE_ENABLE_I18N */ if (BE (sbcset == NULL, 0)) #endif /* not RE_ENABLE_I18N */ { *err = REG_ESPACE; return NULL; } if (not) { #ifdef RE_ENABLE_I18N int i; /* if (syntax & RE_HAT_LISTS_NOT_NEWLINE) bitset_set(cset->sbcset, '\0'); */ mbcset->non_match = 1; if (re_mb_cur_max > 1) for (i = 0; i < SBC_MAX; ++i) if (__btowc (i) == WEOF) bitset_set (sbcset, i); #else /* not RE_ENABLE_I18N */ non_match = 1; #endif /* not RE_ENABLE_I18N */ } /* We don't care the syntax in this case. */ ret = build_charclass (trans, sbcset, #ifdef RE_ENABLE_I18N mbcset, &alloc, #endif /* RE_ENABLE_I18N */ (const unsigned char *) "alpha", 0); if (BE (ret != REG_NOERROR, 0)) { re_free (sbcset); #ifdef RE_ENABLE_I18N free_charset (mbcset); #endif /* RE_ENABLE_I18N */ *err = ret; return NULL; } /* \w match '_' also. */ bitset_set (sbcset, '_'); /* If it is non-matching list. */ #ifdef RE_ENABLE_I18N if (mbcset->non_match) #else /* not RE_ENABLE_I18N */ if (non_match) #endif /* not RE_ENABLE_I18N */ bitset_not (sbcset); /* Build a tree for simple bracket. */ br_token.type = SIMPLE_BRACKET; br_token.opr.sbcset = sbcset; new_idx = re_dfa_add_node (dfa, br_token, 0); tree = create_tree (NULL, NULL, 0, new_idx); if (BE (new_idx == -1 || tree == NULL, 0)) goto build_word_op_espace; #ifdef RE_ENABLE_I18N if (re_mb_cur_max > 1) { re_token_t alt_token; bin_tree_t *mbc_tree; /* Build a tree for complex bracket. */ br_token.type = COMPLEX_BRACKET; br_token.opr.mbcset = mbcset; dfa->has_mb_node = 1; new_idx = re_dfa_add_node (dfa, br_token, 0); mbc_tree = create_tree (NULL, NULL, 0, new_idx); if (BE (new_idx == -1 || mbc_tree == NULL, 0)) goto build_word_op_espace; /* Then join them by ALT node. */ alt_token.type = OP_ALT; new_idx = re_dfa_add_node (dfa, alt_token, 0); tree = create_tree (tree, mbc_tree, 0, new_idx); if (BE (new_idx != -1 && mbc_tree != NULL, 1)) return tree; } else { free_charset (mbcset); return tree; } #else /* not RE_ENABLE_I18N */ return tree; #endif /* not RE_ENABLE_I18N */ build_word_op_espace: re_free (sbcset); #ifdef RE_ENABLE_I18N free_charset (mbcset); #endif /* RE_ENABLE_I18N */ *err = REG_ESPACE; return NULL; }

static reg_errcode_t calc_eclosure (  re_dfa_t *  dfa  )  [static]

Definition at line 1338 of file regcomp.c. References BE, calc_eclosure_iter(), err(), re_node_set_free, and REG_NOERROR. Referenced by analyze(). { int node_idx, incomplete; #ifdef DEBUG assert (dfa->nodes_len > 0); #endif incomplete = 0; /* For each nodes, calculate epsilon closure. */ for (node_idx = 0; ; ++node_idx) { reg_errcode_t err; re_node_set eclosure_elem; if (node_idx == dfa->nodes_len) { if (!incomplete) break; incomplete = 0; node_idx = 0; } #ifdef DEBUG assert (dfa->eclosures[node_idx].nelem != -1); #endif /* If we have already calculated, skip it. */ if (dfa->eclosures[node_idx].nelem != 0) continue; /* Calculate epsilon closure of `node_idx'. */ err = calc_eclosure_iter (&eclosure_elem, dfa, node_idx, 1); if (BE (err != REG_NOERROR, 0)) return err; if (dfa->eclosures[node_idx].nelem == 0) { incomplete = 1; re_node_set_free (&eclosure_elem); } } return REG_NOERROR; }

static reg_errcode_t calc_eclosure_iter (  re_node_set *  new_set, re_dfa_t *  dfa, int  node, int  root )  [static]

Definition at line 1382 of file regcomp.c. References ANCHOR, BE, duplicate_node_closure(), re_dfa_t::eclosures, re_dfa_t::edests, re_node_set::elems, err(), i, IS_EPSILON_NODE, re_node_set::nelem, re_dfa_t::nodes, re_token_t::opr, re_node_set_alloc(), re_node_set_free, re_node_set_insert(), re_node_set_merge(), REG_NOERROR, and re_token_t::type. Referenced by calc_eclosure(). { reg_errcode_t err; unsigned int constraint; int i, incomplete; re_node_set eclosure; incomplete = 0; err = re_node_set_alloc (&eclosure, dfa->edests[node].nelem + 1); if (BE (err != REG_NOERROR, 0)) return err; /* This indicates that we are calculating this node now. We reference this value to avoid infinite loop. */ dfa->eclosures[node].nelem = -1; constraint = ((dfa->nodes[node].type == ANCHOR) ? dfa->nodes[node].opr.ctx_type : 0); /* If the current node has constraints, duplicate all nodes. Since they must inherit the constraints. */ if (constraint && !dfa->nodes[dfa->edests[node].elems[0]].duplicated) { int org_node, cur_node; org_node = cur_node = node; err = duplicate_node_closure (dfa, node, node, node, constraint); if (BE (err != REG_NOERROR, 0)) return err; } /* Expand each epsilon destination nodes. */ if (IS_EPSILON_NODE(dfa->nodes[node].type)) for (i = 0; i < dfa->edests[node].nelem; ++i) { re_node_set eclosure_elem; int edest = dfa->edests[node].elems[i]; /* If calculating the epsilon closure of `edest' is in progress, return intermediate result. */ if (dfa->eclosures[edest].nelem == -1) { incomplete = 1; continue; } /* If we haven't calculated the epsilon closure of `edest' yet, calculate now. Otherwise use calculated epsilon closure. */ if (dfa->eclosures[edest].nelem == 0) { err = calc_eclosure_iter (&eclosure_elem, dfa, edest, 0); if (BE (err != REG_NOERROR, 0)) return err; } else eclosure_elem = dfa->eclosures[edest]; /* Merge the epsilon closure of `edest'. */ re_node_set_merge (&eclosure, &eclosure_elem); /* If the epsilon closure of `edest' is incomplete, the epsilon closure of this node is also incomplete. */ if (dfa->eclosures[edest].nelem == 0) { incomplete = 1; re_node_set_free (&eclosure_elem); } } /* Epsilon closures include itself. */ re_node_set_insert (&eclosure, node); if (incomplete && !root) dfa->eclosures[node].nelem = 0; else dfa->eclosures[node] = eclosure; *new_set = eclosure; return REG_NOERROR; }

static void calc_epsdest (  re_dfa_t *  dfa, bin_tree_t *  node )  [static]

Definition at line 1099 of file regcomp.c. References ANCHOR, calc_first(), calc_next(), bin_tree_t::first, bin_tree_t::left, bin_tree_t::next, bin_tree_t::node_idx, NULL, OP_ALT, OP_BACK_REF, OP_CLOSE_SUBEXP, OP_DUP_ASTERISK, OP_DUP_PLUS, OP_DUP_QUESTION, OP_OPEN_SUBEXP, re_node_set_init_1(), re_node_set_init_2(), bin_tree_t::right, and bin_tree_t::type. Referenced by analyze_tree(). { int idx; idx = node->node_idx; if (node->type == 0) { if (dfa->nodes[idx].type == OP_DUP_ASTERISK || dfa->nodes[idx].type == OP_DUP_PLUS || dfa->nodes[idx].type == OP_DUP_QUESTION) { if (node->left->first == -1) calc_first (dfa, node->left); if (node->next == -1) calc_next (dfa, node); re_node_set_init_2 (dfa->edests + idx, node->left->first, node->next); } else if (dfa->nodes[idx].type == OP_ALT) { int left, right; if (node->left != NULL) { if (node->left->first == -1) calc_first (dfa, node->left); left = node->left->first; } else { if (node->next == -1) calc_next (dfa, node); left = node->next; } if (node->right != NULL) { if (node->right->first == -1) calc_first (dfa, node->right); right = node->right->first; } else { if (node->next == -1) calc_next (dfa, node); right = node->next; } re_node_set_init_2 (dfa->edests + idx, left, right); } else if (dfa->nodes[idx].type == ANCHOR || dfa->nodes[idx].type == OP_OPEN_SUBEXP || dfa->nodes[idx].type == OP_CLOSE_SUBEXP || dfa->node