Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
static reg_errcode_t re_compile_internal (regex_t *preg, const char * pattern,
- int length, reg_syntax_t syntax);
+ Idx length, reg_syntax_t syntax);
static void re_compile_fastmap_iter (regex_t *bufp,
const re_dfastate_t *init_state,
char *fastmap);
-static reg_errcode_t init_dfa (re_dfa_t *dfa, int pat_len);
+static reg_errcode_t init_dfa (re_dfa_t *dfa, Idx pat_len);
#ifdef RE_ENABLE_I18N
static void free_charset (re_charset_t *cset);
#endif /* RE_ENABLE_I18N */
static reg_errcode_t calc_first (void *extra, bin_tree_t *node);
static reg_errcode_t calc_next (void *extra, bin_tree_t *node);
static reg_errcode_t link_nfa_nodes (void *extra, bin_tree_t *node);
-static int duplicate_node (re_dfa_t *dfa, int org_idx, unsigned int constraint);
-static int search_duplicated_node (re_dfa_t *dfa, int org_node,
+static Idx duplicate_node (re_dfa_t *dfa, Idx org_idx, unsigned int constraint);
+static Idx search_duplicated_node (const re_dfa_t *dfa, Idx org_node,
unsigned int constraint);
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);
+ Idx node, bool root);
static reg_errcode_t calc_inveclosure (re_dfa_t *dfa);
-static int fetch_number (re_string_t *input, re_token_t *token,
+static Idx fetch_number (re_string_t *input, re_token_t *token,
reg_syntax_t syntax);
static int peek_token (re_token_t *token, re_string_t *input,
reg_syntax_t syntax);
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);
+ Idx 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);
+ Idx 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);
+ Idx 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);
+ Idx 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);
re_token_t *token, int token_len,
re_dfa_t *dfa,
reg_syntax_t syntax,
- int accept_hyphen);
+ bool accept_hyphen);
static reg_errcode_t parse_bracket_symbol (bracket_elem_t *elem,
re_string_t *regexp,
re_token_t *token);
#ifdef RE_ENABLE_I18N
-static reg_errcode_t build_equiv_class (re_bitset_ptr_t sbcset,
+static reg_errcode_t build_equiv_class (bitset sbcset,
re_charset_t *mbcset,
- int *equiv_class_alloc,
+ Idx *equiv_class_alloc,
const unsigned char *name);
static reg_errcode_t build_charclass (unsigned REG_TRANSLATE_TYPE trans,
- re_bitset_ptr_t sbcset,
+ bitset sbcset,
re_charset_t *mbcset,
- int *char_class_alloc,
+ Idx *char_class_alloc,
const unsigned char *class_name,
reg_syntax_t syntax);
#else /* not RE_ENABLE_I18N */
-static reg_errcode_t build_equiv_class (re_bitset_ptr_t sbcset,
+static reg_errcode_t build_equiv_class (bitset sbcset,
const unsigned char *name);
static reg_errcode_t build_charclass (unsigned REG_TRANSLATE_TYPE trans,
- re_bitset_ptr_t sbcset,
+ bitset sbcset,
const unsigned char *class_name,
reg_syntax_t syntax);
#endif /* not RE_ENABLE_I18N */
unsigned REG_TRANSLATE_TYPE trans,
const unsigned char *class_name,
const unsigned char *extra,
- int non_match, reg_errcode_t *err);
+ bool non_match, reg_errcode_t *err);
static bin_tree_t *create_tree (re_dfa_t *dfa,
bin_tree_t *left, bin_tree_t *right,
re_token_type_t type);
static inline void
__attribute ((always_inline))
-re_set_fastmap (char *fastmap, int icase, int ch)
+re_set_fastmap (char *fastmap, bool icase, int ch)
{
fastmap[ch] = 1;
if (icase)
char *fastmap)
{
re_dfa_t *dfa = (re_dfa_t *) bufp->re_buffer;
- int node_cnt;
- int icase = (dfa->mb_cur_max == 1 && (bufp->re_syntax & REG_IGNORE_CASE));
+ Idx node_cnt;
+ bool icase = (dfa->mb_cur_max == 1 && (bufp->re_syntax & REG_IGNORE_CASE));
for (node_cnt = 0; node_cnt < init_state->nodes.nelem; ++node_cnt)
{
- int node = init_state->nodes.elems[node_cnt];
+ Idx node = init_state->nodes.elems[node_cnt];
re_token_type_t type = dfa->nodes[node].type;
if (type == CHARACTER)
&state) == p - buf
&& (__wcrtomb ((char *) buf, towlower (wc), &state)
!= (size_t) -1))
- re_set_fastmap (fastmap, 0, buf[0]);
+ re_set_fastmap (fastmap, false, buf[0]);
}
#endif
}
else if (type == SIMPLE_BRACKET)
{
int i, j, ch;
- for (i = 0, ch = 0; i < BITSET_UINTS; ++i)
- for (j = 0; j < UINT_BITS; ++j, ++ch)
- if (dfa->nodes[node].opr.sbcset[i] & (1u << j))
+ for (i = 0, ch = 0; i < BITSET_WORDS; ++i)
+ for (j = 0; j < BITSET_WORD_BITS; ++j, ++ch)
+ if (dfa->nodes[node].opr.sbcset[i] & ((bitset_word) 1 << j))
re_set_fastmap (fastmap, icase, ch);
}
#ifdef RE_ENABLE_I18N
else if (type == COMPLEX_BRACKET)
{
- int i;
+ Idx i;
re_charset_t *cset = dfa->nodes[node].opr.mbcset;
if (cset->non_match || cset->ncoll_syms || cset->nequiv_classes
|| cset->nranges || cset->nchar_classes)
is a valid collation element, and don't catch
'b' since 'b' is the only collation element
which starts from 'b'. */
- int j, ch;
const int32_t *table = (const int32_t *)
_NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
- for (i = 0, ch = 0; i < BITSET_UINTS; ++i)
- for (j = 0; j < UINT_BITS; ++j, ++ch)
- if (table[ch] < 0)
- re_set_fastmap (fastmap, icase, ch);
+ for (i = 0; i < SBC_MAX; ++i)
+ if (table[i] < 0)
+ re_set_fastmap (fastmap, icase, i);
}
# else
if (dfa->mb_cur_max > 1)
{
if (__wcrtomb (buf, towlower (cset->mbchars[i]), &state)
!= (size_t) -1)
- re_set_fastmap (fastmap, 0, *(unsigned char *) buf);
+ re_set_fastmap (fastmap, false, *(unsigned char *) buf);
}
}
}
static const bitset utf8_sb_map =
{
/* Set the first 128 bits. */
-# if UINT_MAX == 0xffffffff
- 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff
-# else
-# error "Add case for new unsigned int size"
+# if 2 < BITSET_WORDS
+ BITSET_WORD_MAX,
+# endif
+# if 4 < BITSET_WORDS
+ BITSET_WORD_MAX,
+# endif
+# if 6 < BITSET_WORDS
+ BITSET_WORD_MAX,
# endif
+# if 8 < BITSET_WORDS
+# error "Invalid BITSET_WORDS"
+# endif
+ (BITSET_WORD_MAX
+ >> (SBC_MAX % BITSET_WORD_BITS == 0
+ ? 0
+ : BITSET_WORD_BITS - SBC_MAX % BITSET_WORD_BITS))
};
#endif
static void
free_dfa_content (re_dfa_t *dfa)
{
- int i, j;
+ Idx i, j;
if (dfa->nodes)
for (i = 0; i < dfa->nodes_len; ++i)
SYNTAX indicate regular expression's syntax. */
static reg_errcode_t
-re_compile_internal (regex_t *preg, const char * pattern, int length,
+re_compile_internal (regex_t *preg, const char *pattern, Idx length,
reg_syntax_t syntax)
{
reg_errcode_t err = REG_NOERROR;
as the initial length of some arrays. */
static reg_errcode_t
-init_dfa (re_dfa_t *dfa, int pat_len)
+init_dfa (re_dfa_t *dfa, Idx pat_len)
{
- unsigned int table_size;
+ __re_size_t table_size;
#ifndef _LIBC
char *codeset_name;
#endif
dfa->str_tree_storage_idx = BIN_TREE_STORAGE_SIZE;
dfa->nodes_alloc = pat_len + 1;
- dfa->nodes = re_malloc (re_token_t, dfa->nodes_alloc);
+ dfa->nodes = re_xmalloc (re_token_t, dfa->nodes_alloc);
/* table_size = 2 ^ ceil(log pat_len) */
- for (table_size = 1; ; table_size <<= 1)
- if (table_size > pat_len)
- break;
+ for (table_size = 1; table_size <= pat_len; table_size <<= 1)
+ if (0 < (Idx) -1 && table_size == 0)
+ return REG_ESPACE;
dfa->state_table = re_calloc (struct re_state_table_entry, table_size);
dfa->state_hash_mask = table_size - 1;
{
int i, j, ch;
- dfa->sb_char = re_calloc (unsigned int, BITSET_UINTS);
+ dfa->sb_char = re_calloc (bitset_word, BITSET_WORDS);
if (BE (dfa->sb_char == NULL, 0))
return REG_ESPACE;
- /* Clear all bits by, then set those corresponding to single
- byte chars. */
- bitset_empty (dfa->sb_char);
-
- for (i = 0, ch = 0; i < BITSET_UINTS; ++i)
- for (j = 0; j < UINT_BITS; ++j, ++ch)
+ /* Set the bits corresponding to single byte chars. */
+ for (i = 0, ch = 0; i < BITSET_WORDS; ++i)
+ for (j = 0; j < BITSET_WORD_BITS; ++j, ++ch)
{
wint_t wch = __btowc (ch);
if (wch != WEOF)
- dfa->sb_char[i] |= 1u << j;
+ dfa->sb_char[i] |= (bitset_word) 1 << j;
# ifndef _LIBC
if (isascii (ch) && wch != ch)
dfa->map_notascii = 1;
{
int i, j, ch;
dfa->word_ops_used = 1;
- for (i = 0, ch = 0; i < BITSET_UINTS; ++i)
- for (j = 0; j < UINT_BITS; ++j, ++ch)
+ for (i = 0, ch = 0; i < BITSET_WORDS; ++i)
+ for (j = 0; j < BITSET_WORD_BITS; ++j, ++ch)
if (isalnum (ch) || ch == '_')
- dfa->word_char[i] |= 1u << j;
+ dfa->word_char[i] |= (bitset_word) 1 << j;
}
/* Free the work area which are only used while compiling. */
static reg_errcode_t
create_initial_state (re_dfa_t *dfa)
{
- int first, i;
+ Idx first, i;
reg_errcode_t err;
re_node_set init_nodes;
if (dfa->nbackref > 0)
for (i = 0; i < init_nodes.nelem; ++i)
{
- int node_idx = init_nodes.elems[i];
+ Idx node_idx = init_nodes.elems[i];
re_token_type_t type = dfa->nodes[node_idx].type;
- int clexp_idx;
+ Idx clexp_idx;
if (type != OP_BACK_REF)
continue;
for (clexp_idx = 0; clexp_idx < init_nodes.nelem; ++clexp_idx)
if (type == OP_BACK_REF)
{
- int dest_idx = dfa->edests[node_idx].elems[0];
+ Idx dest_idx = dfa->edests[node_idx].elems[0];
if (!re_node_set_contains (&init_nodes, dest_idx))
{
re_node_set_merge (&init_nodes, dfa->eclosures + dest_idx);
static void
optimize_utf8 (re_dfa_t *dfa)
{
- int node, i, mb_chars = 0, has_period = 0;
+ Idx node;
+ int i;
+ bool mb_chars = false;
+ bool has_period = false;
for (node = 0; node < dfa->nodes_len; ++node)
switch (dfa->nodes[node].type)
{
case CHARACTER:
if (dfa->nodes[node].opr.c >= 0x80)
- mb_chars = 1;
+ mb_chars = true;
break;
case ANCHOR:
switch (dfa->nodes[node].opr.idx)
}
break;
case OP_PERIOD:
- has_period = 1;
+ has_period = true;
break;
case OP_BACK_REF:
case OP_ALT:
return;
case SIMPLE_BRACKET:
/* Just double check. */
- for (i = 0x80 / UINT_BITS; i < BITSET_UINTS; ++i)
- if (dfa->nodes[node].opr.sbcset[i])
- return;
+ {
+ int rshift =
+ (SBC_MAX / 2 % BITSET_WORD_BITS == 0
+ ? 0
+ : BITSET_WORD_BITS - SBC_MAX / 2 % BITSET_WORD_BITS);
+ for (i = SBC_MAX / 2 / BITSET_WORD_BITS; i < BITSET_WORDS; ++i)
+ {
+ if (dfa->nodes[node].opr.sbcset[i] >> rshift != 0)
+ return;
+ rshift = 0;
+ }
+ }
break;
default:
abort ();
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->nexts = re_malloc (Idx, dfa->nodes_alloc);
+ dfa->org_indices = re_malloc (Idx, dfa->nodes_alloc);
+ dfa->edests = re_xmalloc (re_node_set, dfa->nodes_alloc);
dfa->eclosures = re_malloc (re_node_set, dfa->nodes_alloc);
if (BE (dfa->nexts == NULL || dfa->org_indices == NULL || dfa->edests == NULL
|| dfa->eclosures == NULL, 0))
return REG_ESPACE;
- dfa->subexp_map = re_malloc (int, preg->re_nsub);
+ dfa->subexp_map = re_xmalloc (Idx, preg->re_nsub);
if (dfa->subexp_map != NULL)
{
- int i;
+ Idx i;
for (i = 0; i < preg->re_nsub; i++)
dfa->subexp_map[i] = i;
preorder (dfa->str_tree, optimize_subexps, dfa);
if ((!preg->re_no_sub && preg->re_nsub > 0 && dfa->has_plural_match)
|| dfa->nbackref)
{
- dfa->inveclosures = re_malloc (re_node_set, dfa->nodes_len);
+ dfa->inveclosures = re_xmalloc (re_node_set, dfa->nodes_len);
if (BE (dfa->inveclosures == NULL, 0))
return REG_ESPACE;
ret = calc_inveclosure (dfa);
else if (node->token.type == SUBEXP
&& node->left && node->left->token.type == SUBEXP)
{
- int other_idx = node->left->token.opr.idx;
+ Idx other_idx = node->left->token.opr.idx;
node->left = node->left->left;
if (node->left)
node->left->parent = node;
dfa->subexp_map[other_idx] = dfa->subexp_map[node->token.opr.idx];
- if (other_idx < CHAR_BIT * sizeof dfa->used_bkref_map)
- dfa->used_bkref_map &= ~(1u << other_idx);
+ if (other_idx < BITSET_WORD_BITS)
+ dfa->used_bkref_map &= ~ ((bitset_word) 1 << other_idx);
}
return REG_NOERROR;
very common, so we do not lose much. An example that triggers
this case is the sed "script" /\(\)/x. */
&& node->left != NULL
- && (node->token.opr.idx >= CHAR_BIT * sizeof dfa->used_bkref_map
- || !(dfa->used_bkref_map & (1u << node->token.opr.idx))))
+ && ! (node->token.opr.idx < BITSET_WORD_BITS
+ && dfa->used_bkref_map & ((bitset_word) 1 << node->token.opr.idx)))
return node->left;
/* Convert the SUBEXP node to the concatenation of an
{
node->first = node;
node->node_idx = re_dfa_add_node (dfa, node->token);
- if (BE (node->node_idx == -1, 0))
+ if (BE (node->node_idx == REG_MISSING, 0))
return REG_ESPACE;
}
return REG_NOERROR;
link_nfa_nodes (void *extra, bin_tree_t *node)
{
re_dfa_t *dfa = (re_dfa_t *) extra;
- int idx = node->node_idx;
+ Idx idx = node->node_idx;
reg_errcode_t err = REG_NOERROR;
switch (node->token.type)
case OP_DUP_ASTERISK:
case OP_ALT:
{
- int left, right;
+ Idx left, right;
dfa->has_plural_match = 1;
if (node->left != NULL)
left = node->left->first->node_idx;
right = node->right->first->node_idx;
else
right = node->next->node_idx;
- assert (left > -1);
- assert (right > -1);
+ assert (REG_VALID_INDEX (left));
+ assert (REG_VALID_INDEX (right));
err = re_node_set_init_2 (dfa->edests + idx, left, right);
}
break;
to their own constraint. */
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)
+duplicate_node_closure (re_dfa_t *dfa, Idx top_org_node,
+ Idx top_clone_node, Idx root_node,
+ unsigned int init_constraint)
{
- int org_node, clone_node, ret;
+ Idx org_node, clone_node;
+ bool ok;
unsigned int constraint = init_constraint;
for (org_node = top_org_node, clone_node = top_clone_node;;)
{
- int org_dest, clone_dest;
+ Idx org_dest, clone_dest;
if (dfa->nodes[org_node].type == OP_BACK_REF)
{
/* If the back reference epsilon-transit, its destination must
org_dest = dfa->nexts[org_node];
re_node_set_empty (dfa->edests + clone_node);
clone_dest = duplicate_node (dfa, org_dest, constraint);
- if (BE (clone_dest == -1, 0))
+ if (BE (clone_dest == REG_MISSING, 0))
return REG_ESPACE;
dfa->nexts[clone_node] = dfa->nexts[org_node];
- ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
- if (BE (ret < 0, 0))
+ ok = re_node_set_insert (dfa->edests + clone_node, clone_dest);
+ if (BE (! ok, 0))
return REG_ESPACE;
}
else if (dfa->edests[org_node].nelem == 0)
/* ...but if the node is root_node itself, it means the
epsilon closure have a loop, then tie it to the
destination of the root_node. */
- ret = re_node_set_insert (dfa->edests + clone_node,
+ ok = re_node_set_insert (dfa->edests + clone_node,
org_dest);
- if (BE (ret < 0, 0))
+ if (BE (! ok, 0))
return REG_ESPACE;
break;
}
constraint |= dfa->nodes[org_node].opr.ctx_type;
}
clone_dest = duplicate_node (dfa, org_dest, constraint);
- if (BE (clone_dest == -1, 0))
+ if (BE (clone_dest == REG_MISSING, 0))
return REG_ESPACE;
- ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
- if (BE (ret < 0, 0))
+ ok = re_node_set_insert (dfa->edests + clone_node, clone_dest);
+ if (BE (! ok, 0))
return REG_ESPACE;
}
else /* dfa->edests[org_node].nelem == 2 */
re_node_set_empty (dfa->edests + clone_node);
/* Search for a duplicated node which satisfies the constraint. */
clone_dest = search_duplicated_node (dfa, org_dest, constraint);
- if (clone_dest == -1)
+ if (clone_dest == REG_MISSING)
{
/* There are no such a duplicated node, create a new one. */
reg_errcode_t err;
clone_dest = duplicate_node (dfa, org_dest, constraint);
- if (BE (clone_dest == -1, 0))
+ if (BE (clone_dest == REG_MISSING, 0))
return REG_ESPACE;
- ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
- if (BE (ret < 0, 0))
+ ok = re_node_set_insert (dfa->edests + clone_node, clone_dest);
+ if (BE (! ok, 0))
return REG_ESPACE;
err = duplicate_node_closure (dfa, org_dest, clone_dest,
root_node, constraint);
{
/* There are a duplicated node which satisfy the constraint,
use it to avoid infinite loop. */
- ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
- if (BE (ret < 0, 0))
+ ok = re_node_set_insert (dfa->edests + clone_node, clone_dest);
+ if (BE (! ok, 0))
return REG_ESPACE;
}
org_dest = dfa->edests[org_node].elems[1];
clone_dest = duplicate_node (dfa, org_dest, constraint);
- if (BE (clone_dest == -1, 0))
+ if (BE (clone_dest == REG_MISSING, 0))
return REG_ESPACE;
- ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
- if (BE (ret < 0, 0))
+ ok = re_node_set_insert (dfa->edests + clone_node, clone_dest);
+ if (BE (! ok, 0))
return REG_ESPACE;
}
org_node = org_dest;
/* Search for a node which is duplicated from the node ORG_NODE, and
satisfies the constraint CONSTRAINT. */
-static int
-search_duplicated_node (re_dfa_t *dfa, int org_node, unsigned int constraint)
+static Idx
+search_duplicated_node (const re_dfa_t *dfa, Idx org_node,
+ unsigned int constraint)
{
- int idx;
+ Idx idx;
for (idx = dfa->nodes_len - 1; dfa->nodes[idx].duplicated && idx > 0; --idx)
{
if (org_node == dfa->org_indices[idx]
&& constraint == dfa->nodes[idx].constraint)
return idx; /* Found. */
}
- return -1; /* Not found. */
+ return REG_MISSING; /* Not found. */
}
/* Duplicate the node whose index is ORG_IDX and set the constraint CONSTRAINT.
- Return the index of the new node, or -1 if insufficient storage is
+ Return the index of the new node, or REG_MISSING if insufficient storage is
available. */
-static int
-duplicate_node (re_dfa_t *dfa, int org_idx, unsigned int constraint)
+static Idx
+duplicate_node (re_dfa_t *dfa, Idx org_idx, unsigned int constraint)
{
- int dup_idx = re_dfa_add_node (dfa, dfa->nodes[org_idx]);
- if (BE (dup_idx != -1, 1))
+ Idx dup_idx = re_dfa_add_node (dfa, dfa->nodes[org_idx]);
+ if (BE (dup_idx != REG_MISSING, 1))
{
dfa->nodes[dup_idx].constraint = constraint;
if (dfa->nodes[org_idx].type == ANCHOR)
static reg_errcode_t
calc_inveclosure (re_dfa_t *dfa)
{
- int src, idx, ret;
+ Idx src, idx;
+ bool ok;
for (idx = 0; idx < dfa->nodes_len; ++idx)
re_node_set_init_empty (dfa->inveclosures + idx);
for (src = 0; src < dfa->nodes_len; ++src)
{
- int *elems = dfa->eclosures[src].elems;
+ Idx *elems = dfa->eclosures[src].elems;
for (idx = 0; idx < dfa->eclosures[src].nelem; ++idx)
{
- ret = re_node_set_insert_last (dfa->inveclosures + elems[idx], src);
- if (BE (ret == -1, 0))
+ ok = re_node_set_insert_last (dfa->inveclosures + elems[idx], src);
+ if (BE (! ok, 0))
return REG_ESPACE;
}
}
static reg_errcode_t
calc_eclosure (re_dfa_t *dfa)
{
- int node_idx, incomplete;
+ Idx node_idx;
+ bool incomplete;
#ifdef DEBUG
assert (dfa->nodes_len > 0);
#endif
- incomplete = 0;
+ incomplete = false;
/* For each nodes, calculate epsilon closure. */
for (node_idx = 0; ; ++node_idx)
{
{
if (!incomplete)
break;
- incomplete = 0;
+ incomplete = false;
node_idx = 0;
}
#ifdef DEBUG
- assert (dfa->eclosures[node_idx].nelem != -1);
+ assert (dfa->eclosures[node_idx].nelem != REG_MISSING);
#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);
+ err = calc_eclosure_iter (&eclosure_elem, dfa, node_idx, true);
if (BE (err != REG_NOERROR, 0))
return err;
if (dfa->eclosures[node_idx].nelem == 0)
{
- incomplete = 1;
+ incomplete = true;
re_node_set_free (&eclosure_elem);
}
}
/* Calculate epsilon closure of NODE. */
static reg_errcode_t
-calc_eclosure_iter (re_node_set *new_set, re_dfa_t *dfa, int node, int root)
+calc_eclosure_iter (re_node_set *new_set, re_dfa_t *dfa, Idx node, bool root)
{
reg_errcode_t err;
unsigned int constraint;
- int i, incomplete;
+ Idx i;
+ bool incomplete;
+ bool ok;
re_node_set eclosure;
- incomplete = 0;
+ incomplete = false;
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;
+ dfa->eclosures[node].nelem = REG_MISSING;
constraint = ((dfa->nodes[node].type == ANCHOR)
? dfa->nodes[node].opr.ctx_type : 0);
&& dfa->edests[node].nelem
&& !dfa->nodes[dfa->edests[node].elems[0]].duplicated)
{
- int org_node, cur_node;
+ Idx org_node, cur_node;
org_node = cur_node = node;
err = duplicate_node_closure (dfa, node, node, node, constraint);
if (BE (err != REG_NOERROR, 0))
for (i = 0; i < dfa->edests[node].nelem; ++i)
{
re_node_set eclosure_elem;
- int edest = dfa->edests[node].elems[i];
+ Idx 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)
+ if (dfa->eclosures[edest].nelem == REG_MISSING)
{
- incomplete = 1;
+ incomplete = true;
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);
+ err = calc_eclosure_iter (&eclosure_elem, dfa, edest, false);
if (BE (err != REG_NOERROR, 0))
return err;
}
the epsilon closure of this node is also incomplete. */
if (dfa->eclosures[edest].nelem == 0)
{
- incomplete = 1;
+ incomplete = true;
re_node_set_free (&eclosure_elem);
}
}
/* Epsilon closures include itself. */
- re_node_set_insert (&eclosure, node);
+ ok = re_node_set_insert (&eclosure, node);
+ if (BE (! ok, 0))
+ return REG_ESPACE;
if (incomplete && !root)
dfa->eclosures[node].nelem = 0;
else
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)
+ reg_syntax_t syntax, Idx nest, reg_errcode_t *err)
{
re_dfa_t *dfa = (re_dfa_t *) preg->re_buffer;
bin_tree_t *tree, *branch = NULL;
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)
+ reg_syntax_t syntax, Idx nest, reg_errcode_t *err)
{
bin_tree_t *tree, *exp;
re_dfa_t *dfa = (re_dfa_t *) preg->re_buffer;
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)
+ reg_syntax_t syntax, Idx nest, reg_errcode_t *err)
{
re_dfa_t *dfa = (re_dfa_t *) preg->re_buffer;
bin_tree_t *tree;
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)
+ reg_syntax_t syntax, Idx nest, reg_errcode_t *err)
{
re_dfa_t *dfa = (re_dfa_t *) preg->re_buffer;
bin_tree_t *tree;
re_token_t *token, reg_syntax_t syntax, reg_errcode_t *err)
{
bin_tree_t *tree = NULL, *old_tree = NULL;
- int i, start, end, start_idx = re_string_cur_idx (regexp);
+ Idx i, start, end, start_idx = re_string_cur_idx (regexp);
re_token_t start_token = *token;
if (token->type == OP_OPEN_DUP_NUM)
{
end = 0;
start = fetch_number (regexp, token, syntax);
- if (start == -1)
+ if (start == REG_MISSING)
{
if (token->type == CHARACTER && token->opr.c == ',')
start = 0; /* We treat "{,m}" as "{0,m}". */
return NULL;
}
}
- if (BE (start != -2, 1))
+ if (BE (start != REG_ERROR, 1))
{
/* We treat "{n}" as "{n,n}". */
end = ((token->type == OP_CLOSE_DUP_NUM) ? start
: ((token->type == CHARACTER && token->opr.c == ',')
- ? fetch_number (regexp, token, syntax) : -2));
+ ? fetch_number (regexp, token, syntax) : REG_ERROR));
}
- if (BE (start == -2 || end == -2, 0))
+ if (BE (start == REG_ERROR || end == REG_ERROR, 0))
{
/* Invalid sequence. */
if (BE (!(syntax & REG_INVALID_INTERVAL_ORD), 0))
return elem;
}
- if (BE (end != -1 && start > end, 0))
+ if (BE (end != REG_MISSING && start > end, 0))
{
/* First number greater than second. */
*err = REG_BADBR;
else
{
start = (token->type == OP_DUP_PLUS) ? 1 : 0;
- end = (token->type == OP_DUP_QUESTION) ? 1 : -1;
+ end = (token->type == OP_DUP_QUESTION) ? 1 : REG_MISSING;
}
fetch_token (token, regexp, syntax);
if (elem->token.type == SUBEXP)
postorder (elem, mark_opt_subexp, (void *) (long) elem->token.opr.idx);
- tree = create_tree (dfa, elem, NULL, (end == -1 ? OP_DUP_ASTERISK : OP_ALT));
+ tree = create_tree (dfa, elem, NULL,
+ (end == REG_MISSING ? OP_DUP_ASTERISK : OP_ALT));
if (BE (tree == NULL, 0))
goto parse_dup_op_espace;
- /* This loop is actually executed only when end != -1,
+ /* This loop is actually executed only when end != REG_MISSING,
to rewrite <re>{0,n} as (<re>(<re>...<re>?)?)?... We have
already created the start+1-th copy. */
- for (i = start + 2; i <= end; ++i)
- {
- elem = duplicate_tree (elem, dfa);
- tree = create_tree (dfa, tree, elem, CONCAT);
- if (BE (elem == NULL || tree == NULL, 0))
- goto parse_dup_op_espace;
-
- tree = create_tree (dfa, tree, NULL, OP_ALT);
- if (BE (tree == NULL, 0))
- goto parse_dup_op_espace;
- }
+ if ((Idx) -1 < 0 || end != REG_MISSING)
+ for (i = start + 2; i <= end; ++i)
+ {
+ elem = duplicate_tree (elem, dfa);
+ tree = create_tree (dfa, tree, elem, CONCAT);
+ if (BE (elem == NULL || tree == NULL, 0))
+ goto parse_dup_op_espace;
+
+ tree = create_tree (dfa, tree, NULL, OP_ALT);
+ if (BE (tree == NULL, 0))
+ goto parse_dup_op_espace;
+ }
if (old_tree)
tree = create_tree (dfa, old_tree, tree, CONCAT);
update it. */
static reg_errcode_t
-build_range_exp (re_bitset_ptr_t sbcset,
+build_range_exp (bitset sbcset,
# ifdef RE_ENABLE_I18N
- re_charset_t *mbcset, int *range_alloc,
+ re_charset_t *mbcset, Idx *range_alloc,
# endif
bracket_elem_t *start_elem, bracket_elem_t *end_elem)
{
{
/* There is not enough space, need realloc. */
wchar_t *new_array_start, *new_array_end;
- int new_nranges;
+ Idx new_nranges;
- /* +1 in case of mbcset->nranges is 0. */
- new_nranges = 2 * mbcset->nranges + 1;
+ new_nranges = mbcset->nranges;
/* 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_start = re_x2realloc (mbcset->range_starts, wchar_t,
+ &new_nranges);
new_array_end = re_realloc (mbcset->range_ends, wchar_t,
new_nranges);
pointer argument since we may update it. */
static reg_errcode_t
-build_collating_symbol (re_bitset_ptr_t sbcset,
+build_collating_symbol (bitset sbcset,
# ifdef RE_ENABLE_I18N
- re_charset_t *mbcset, int *coll_sym_alloc,
+ re_charset_t *mbcset, Idx *coll_sym_alloc,
# endif
const unsigned char *name)
{
auto inline reg_errcode_t
__attribute ((always_inline))
- build_range_exp (re_bitset_ptr_t sbcset, re_charset_t *mbcset,
- int *range_alloc,
+ build_range_exp (bitset sbcset, re_charset_t *mbcset,
+ Idx *range_alloc,
bracket_elem_t *start_elem, bracket_elem_t *end_elem)
{
unsigned int ch;
/* There is not enough space, need realloc. */
uint32_t *new_array_start;
uint32_t *new_array_end;
- int new_nranges;
+ Idx new_nranges;
- /* +1 in case of mbcset->nranges is 0. */
- new_nranges = 2 * mbcset->nranges + 1;
- new_array_start = re_realloc (mbcset->range_starts, uint32_t,
- new_nranges);
+ new_nranges = mbcset->nranges;
+ new_array_start = re_x2realloc (mbcset->range_starts, uint32_t,
+ &new_nranges);
new_array_end = re_realloc (mbcset->range_ends, uint32_t,
new_nranges);
auto inline reg_errcode_t
__attribute ((always_inline))
- build_collating_symbol (re_bitset_ptr_t sbcset, re_charset_t *mbcset,
- int *coll_sym_alloc, const unsigned char *name)
+ build_collating_symbol (bitset sbcset, re_charset_t *mbcset,
+ Idx *coll_sym_alloc, const unsigned char *name)
{
int32_t elem, idx;
size_t name_len = strlen ((const char *) name);
if (BE (*coll_sym_alloc == mbcset->ncoll_syms, 0))
{
/* Not enough, realloc it. */
- /* +1 in case of mbcset->ncoll_syms is 0. */
- int new_coll_sym_alloc = 2 * mbcset->ncoll_syms + 1;
+ Idx new_coll_sym_alloc = mbcset->ncoll_syms;
/* Use realloc since mbcset->coll_syms is NULL
if *alloc == 0. */
- int32_t *new_coll_syms = re_realloc (mbcset->coll_syms, int32_t,
- new_coll_sym_alloc);
+ int32_t *new_coll_syms = re_x2realloc (mbcset->coll_syms, int32_t,
+ &new_coll_sym_alloc);
if (BE (new_coll_syms == NULL, 0))
return REG_ESPACE;
mbcset->coll_syms = new_coll_syms;
re_bitset_ptr_t sbcset;
#ifdef RE_ENABLE_I18N
re_charset_t *mbcset;
- int coll_sym_alloc = 0, range_alloc = 0, mbchar_alloc = 0;
- int equiv_class_alloc = 0, char_class_alloc = 0;
+ Idx coll_sym_alloc = 0, range_alloc = 0, mbchar_alloc = 0;
+ Idx equiv_class_alloc = 0, char_class_alloc = 0;
#endif /* not RE_ENABLE_I18N */
- int non_match = 0;
+ bool non_match = false;
bin_tree_t *work_tree;
int token_len;
- int first_round = 1;
+ bool first_round = true;
#ifdef _LIBC
collseqmb = (const unsigned char *)
_NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQMB);
_NL_COLLATE_SYMB_EXTRAMB);
}
#endif
- sbcset = re_calloc (unsigned int, BITSET_UINTS);
+ sbcset = re_calloc (bitset_word, BITSET_WORDS);
#ifdef RE_ENABLE_I18N
mbcset = re_calloc (re_charset_t, 1);
#endif /* RE_ENABLE_I18N */
#ifdef RE_ENABLE_I18N
mbcset->non_match = 1;
#endif /* not RE_ENABLE_I18N */
- non_match = 1;
+ non_match = true;
if (syntax & REG_HAT_LISTS_NOT_NEWLINE)
bitset_set (sbcset, '\0');
re_string_skip_bytes (regexp, token_len); /* Skip a token. */
unsigned char start_name_buf[BRACKET_NAME_BUF_SIZE];
unsigned char end_name_buf[BRACKET_NAME_BUF_SIZE];
reg_errcode_t ret;
- int token_len2 = 0, is_range_exp = 0;
+ int token_len2 = 0;
+ bool is_range_exp = false;
re_token_t token2;
start_elem.opr.name = start_name_buf;
*err = ret;
goto parse_bracket_exp_free_return;
}
- first_round = 0;
+ first_round = false;
/* Get information about the next token. We need it in any case. */
token_len = peek_token_bracket (token, regexp, syntax);
token->type = CHARACTER;
}
else
- is_range_exp = 1;
+ is_range_exp = true;
}
}
- if (is_range_exp == 1)
+ if (is_range_exp == true)
{
end_elem.opr.name = end_name_buf;
ret = parse_bracket_element (&end_elem, regexp, &token2, token_len2,
- dfa, syntax, 1);
+ dfa, syntax, true);
if (BE (ret != REG_NOERROR, 0))
{
*err = ret;
{
wchar_t *new_mbchars;
/* Not enough, realloc it. */
- /* +1 in case of mbcset->nmbchars is 0. */
- mbchar_alloc = 2 * mbcset->nmbchars + 1;
+ mbchar_alloc = mbcset->nmbchars;
/* Use realloc since array is NULL if *alloc == 0. */
- new_mbchars = re_realloc (mbcset->mbchars, wchar_t,
- mbchar_alloc);
+ new_mbchars = re_x2realloc (mbcset->mbchars, wchar_t,
+ &mbchar_alloc);
if (BE (new_mbchars == NULL, 0))
goto parse_bracket_exp_espace;
mbcset->mbchars = new_mbchars;
mbc_tree = create_token_tree (dfa, NULL, NULL, &br_token);
if (BE (mbc_tree == NULL, 0))
goto parse_bracket_exp_espace;
- for (sbc_idx = 0; sbc_idx < BITSET_UINTS; ++sbc_idx)
+ for (sbc_idx = 0; sbc_idx < BITSET_WORDS; ++sbc_idx)
if (sbcset[sbc_idx])
break;
/* If there are no bits set in sbcset, there is no point
of having both SIMPLE_BRACKET and COMPLEX_BRACKET. */
- if (sbc_idx < BITSET_UINTS)
+ if (sbc_idx < BITSET_WORDS)
{
/* Build a tree for simple bracket. */
br_token.type = SIMPLE_BRACKET;
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, int accept_hyphen)
+ reg_syntax_t syntax, bool accept_hyphen)
{
#ifdef RE_ENABLE_I18N
int cur_char_size;
is a pointer argument sinse we may update it. */
static reg_errcode_t
-build_equiv_class (re_bitset_ptr_t sbcset,
+build_equiv_class (bitset sbcset,
#ifdef RE_ENABLE_I18N
- re_charset_t *mbcset, int *equiv_class_alloc,
+ re_charset_t *mbcset, Idx *equiv_class_alloc,
#endif
const unsigned char *name)
{
if (BE (*equiv_class_alloc == mbcset->nequiv_classes, 0))
{
/* Not enough, realloc it. */
- /* +1 in case of mbcset->nequiv_classes is 0. */
- int new_equiv_class_alloc = 2 * mbcset->nequiv_classes + 1;
+ Idx new_equiv_class_alloc = mbcset->nequiv_classes;
/* Use realloc since the array is NULL if *alloc == 0. */
- int32_t *new_equiv_classes = re_realloc (mbcset->equiv_classes,
- int32_t,
- new_equiv_class_alloc);
+ int32_t *new_equiv_classes = re_x2realloc (mbcset->equiv_classes,
+ int32_t,
+ &new_equiv_class_alloc);
if (BE (new_equiv_classes == NULL, 0))
return REG_ESPACE;
mbcset->equiv_classes = new_equiv_classes;
is a pointer argument sinse we may update it. */
static reg_errcode_t
-build_charclass (unsigned REG_TRANSLATE_TYPE trans, re_bitset_ptr_t sbcset,
+build_charclass (unsigned REG_TRANSLATE_TYPE trans, bitset sbcset,
#ifdef RE_ENABLE_I18N
- re_charset_t *mbcset, int *char_class_alloc,
+ re_charset_t *mbcset, Idx *char_class_alloc,
#endif
const unsigned char *class_name, reg_syntax_t syntax)
{
if (BE (*char_class_alloc == mbcset->nchar_classes, 0))
{
/* Not enough, realloc it. */
- /* +1 in case of mbcset->nchar_classes is 0. */
- int new_char_class_alloc = 2 * mbcset->nchar_classes + 1;
+ Idx new_char_class_alloc = mbcset->nchar_classes;
/* Use realloc since array is NULL if *alloc == 0. */
- wctype_t *new_char_classes = re_realloc (mbcset->char_classes, wctype_t,
- new_char_class_alloc);
+ wctype_t *new_char_classes = re_x2realloc (mbcset->char_classes, wctype_t,
+ &new_char_class_alloc);
if (BE (new_char_classes == NULL, 0))
return REG_ESPACE;
mbcset->char_classes = new_char_classes;
build_charclass_op (re_dfa_t *dfa, unsigned REG_TRANSLATE_TYPE trans,
const unsigned char *class_name,
const unsigned char *extra,
- int non_match, reg_errcode_t *err)
+ bool non_match, reg_errcode_t *err)
{
re_bitset_ptr_t sbcset;
#ifdef RE_ENABLE_I18N
re_charset_t *mbcset;
- int alloc = 0;
+ Idx alloc = 0;
#endif /* not RE_ENABLE_I18N */
reg_errcode_t ret;
re_token_t br_token;
bin_tree_t *tree;
- sbcset = re_calloc (unsigned int, BITSET_UINTS);
+ sbcset = re_calloc (bitset_word, BITSET_WORDS);
#ifdef RE_ENABLE_I18N
mbcset = re_calloc (re_charset_t, 1);
#endif /* RE_ENABLE_I18N */
/* This is intended for the expressions like "a{1,3}".
Fetch a number from `input', and return the number.
- Return -1, if the number field is empty like "{,1}".
- Return -2, If an error is occured. */
+ Return REG_MISSING if the number field is empty like "{,1}".
+ Return REG_ERROR if an error occurred. */
-static int
+static Idx
fetch_number (re_string_t *input, re_token_t *token, reg_syntax_t syntax)
{
- int num = -1;
+ Idx num = REG_MISSING;
unsigned char c;
while (1)
{
fetch_token (token, input, syntax);
c = token->opr.c;
if (BE (token->type == END_OF_RE, 0))
- return -2;
+ return REG_ERROR;
if (token->type == OP_CLOSE_DUP_NUM || c == ',')
break;
- num = ((token->type != CHARACTER || c < '0' || '9' < c || num == -2)
- ? -2 : ((num == -1) ? c - '0' : num * 10 + c - '0'));
- num = (num > REG_DUP_MAX) ? -2 : num;
+ num = ((token->type != CHARACTER || c < '0' || '9' < c
+ || num == REG_ERROR)
+ ? REG_ERROR
+ : ((num == REG_MISSING) ? c - '0' : num * 10 + c - '0'));
+ num = (num > REG_DUP_MAX) ? REG_ERROR : num;
}
return num;
}
tree->token.opt_subexp = 0;
tree->first = NULL;
tree->next = NULL;
- tree->node_idx = -1;
+ tree->node_idx = REG_MISSING;
if (left != NULL)
left->parent = tree;
static reg_errcode_t
mark_opt_subexp (void *extra, bin_tree_t *node)
{
- int idx = (int) (long) extra;
+ Idx idx = (Idx) (long) extra;
if (node->token.type == SUBEXP && node->token.opr.idx == idx)
node->token.opt_subexp = 1;