regexec.c revision 7e7bd3dccbfe8f79e25e5c1554b5bc3a9aaca321
/* Extended regular expression matching and search library.
Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007 Free Software Foundation,
Inc.
This file is part of the GNU C Library.
Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License along
with this program; if not, write to the Free Software Foundation,
Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
Idx n) internal_function;
int eflags) internal_function;
struct re_registers *regs,
struct re_registers *regs,
bool ret_len) internal_function;
const re_match_context_t *mctx,
bool fl_backtrack) internal_function;
#ifdef RE_ENABLE_I18N
#endif /* RE_ENABLE_I18N */
const re_node_set *candidates)
const re_node_set *limits,
const re_node_set *candidates,
struct re_backref_cache_entry *bkref_ents,
re_dfastate_t **dst,
#if 0
#endif
#ifdef RE_ENABLE_I18N
#endif /* RE_ENABLE_I18N */
const re_node_set *nodes)
const re_sub_match_top_t *sub_top,
int type) internal_function;
int type) internal_function;
#ifdef RE_ENABLE_I18N
# ifdef _LIBC
static unsigned int find_collation_sequence_value (const unsigned char *mbs,
# endif /* _LIBC */
#endif /* RE_ENABLE_I18N */
const re_dfastate_t *state,
/* Entry point for POSIX code. */
/* regexec searches for a given pattern, specified by PREG, in the
string STRING.
If NMATCH is zero or REG_NOSUB was set in the cflags argument to
`regcomp', we ignore PMATCH. Otherwise, we assume PMATCH has at
least NMATCH elements, and we set them to the offsets of the
corresponding matched substrings.
EFLAGS specifies `execution flags' which affect matching: if
REG_NOTBOL is set, then ^ does not match at the beginning of the
string; if REG_NOTEOL is set, then $ does not match at the end.
We return 0 if we find a match and REG_NOMATCH if not. */
int
const char *_Restrict_ string;
int eflags;
{
#ifdef _LIBC
#endif
return REG_BADPAT;
if (eflags & REG_STARTEND)
{
}
else
{
start = 0;
}
else
return err != REG_NOERROR;
}
#ifdef _LIBC
# include <shlib-compat.h>
int
{
}
# endif
#endif
/* Entry points for GNU code. */
/* re_match, re_search, re_match_2, re_search_2
The former two functions operate on STRING with length LENGTH,
while the later two operate on concatenation of STRING1 and STRING2
with lengths LENGTH1 and LENGTH2, respectively.
re_match() matches the compiled pattern in BUFP against the string,
starting at index START.
re_search() first tries matching at index START, then it tries to match
starting from index START + 1, and so on. The last start position tried
is START + RANGE. (Thus RANGE = 0 forces re_search to operate the same
way as re_match().)
The parameter STOP of re_{match,search}_2 specifies that no match exceeding
the first STOP characters of the concatenation of the strings should be
concerned.
If REGS is not NULL, and BUFP->no_sub is not set, the offsets of the match
and all groups is stored in REGS. (For the "_2" variants, the offsets are
computed relative to the concatenation, not relative to the individual
strings.)
On success, re_match* functions return the length of the match, re_search*
return the position of the start of the match. Return value -1 means no
match was found and -2 indicates an internal error. */
struct re_pattern_buffer *bufp;
const char *string;
struct re_registers *regs;
{
}
#ifdef _LIBC
#endif
struct re_pattern_buffer *bufp;
const char *string;
struct re_registers *regs;
{
false);
}
#ifdef _LIBC
#endif
struct re_pattern_buffer *bufp;
struct re_registers *regs;
{
}
#ifdef _LIBC
#endif
struct re_pattern_buffer *bufp;
struct re_registers *regs;
{
}
#ifdef _LIBC
#endif
static regoff_t
{
const char *str;
char *s = NULL;
return -2;
/* Concatenate the strings. */
if (length2 > 0)
if (length1 > 0)
{
return -2;
#ifdef _LIBC
#else
#endif
str = s;
}
else
else
ret_len);
re_free (s);
return rval;
}
/* The parameters have the same meaning as those of re_search.
Additional parameters:
If RET_LEN is true the length of the match is returned (re_match style);
otherwise the position of the match is returned. */
static regoff_t
bool ret_len)
{
int eflags = 0;
#ifdef _LIBC
#endif
/* Check for out-of-range. */
return -1;
last_start = length;
last_start = 0;
/* Compile fastmap if we haven't yet. */
/* We need at least 1 register. */
nregs = 1;
{
{
/* Nothing can be copied to regs. */
nregs = 1;
}
}
else
{
rval = -2;
goto out;
}
rval = 0;
/* I hope we needn't fill ther regs with -1's when no match was found. */
if (result != REG_NOERROR)
rval = -1;
{
/* If caller wants register contents data back, copy them. */
rval = -2;
}
{
if (ret_len)
{
}
else
}
out:
return rval;
}
static unsigned int
int regs_allocated)
{
int rval = REGS_REALLOCATE;
Idx i;
/* We need one extra element beyond `num_regs' for the `-1' marker GNU code
uses. */
/* Have the register data arrays been allocated? */
if (regs_allocated == REGS_UNALLOCATED)
{ /* No. So allocate them with malloc. */
return REGS_UNALLOCATED;
{
return REGS_UNALLOCATED;
}
}
else if (regs_allocated == REGS_REALLOCATE)
{ /* Yes. If we need more elements than were already
allocated, reallocate them. If we need fewer, just
leave it alone. */
{
return REGS_UNALLOCATED;
{
return REGS_UNALLOCATED;
}
}
}
else
{
/* This function may not be called with REGS_FIXED and nregs too big. */
rval = REGS_FIXED;
}
/* Copy the regs. */
for (i = 0; i < nregs; ++i)
{
}
return rval;
}
/* Set REGS to hold NUM_REGS registers, storing them in STARTS and
ENDS. Subsequent matches using PATTERN_BUFFER and REGS will use
this memory for recording register information. STARTS and ENDS
must be allocated using the malloc library routine, and must each
be at least NUM_REGS * sizeof (regoff_t) bytes long.
If NUM_REGS == 0, then subsequent matches should allocate their own
register data.
Unless this function is called, the first search or match using
PATTERN_BUFFER will allocate its own register data, without
freeing the old data. */
void
struct re_pattern_buffer *bufp;
struct re_registers *regs;
{
if (num_regs)
{
}
else
{
}
}
#ifdef _LIBC
#endif
/* Entry points compatible with 4.2 BSD regex library. We don't define
them unless specifically requested. */
#if defined _REGEX_RE_COMP || defined _LIBC
int
# ifdef _LIBC
# endif
re_exec (s)
const char *s;
{
}
#endif /* _REGEX_RE_COMP */
/* Internal entry point. */
/* Searches for a compiled pattern PREG in the string STRING, whose
length is LENGTH. NMATCH, PMATCH, and EFLAGS have the same
meaning as with regexec. LAST_START is START + RANGE, where
START and RANGE have the same meaning as with re_search.
Return REG_NOERROR if we find a match, and REG_NOMATCH if not,
otherwise return the error code.
Note: We assume front end functions already check ranges.
(0 <= LAST_START && LAST_START <= LENGTH) */
static reg_errcode_t
int eflags)
{
int incr;
bool fl_longest_match;
int match_kind;
bool sb;
int ch;
#else
#endif
#endif
nmatch -= extra_nmatch;
/* Check if the DFA haven't been compiled. */
return REG_NOMATCH;
#ifdef DEBUG
/* We assume front-end functions already check them. */
#endif
/* If initial states with non-begbuf contexts have no elements,
the regex must be anchored. If preg->newline_anchor is set,
we'll never use init_state_nl, so do not check it. */
|| !preg->newline_anchor))
{
if (start != 0 && last_start != 0)
return REG_NOMATCH;
start = last_start = 0;
}
/* We must check the longest matching, if nmatch > 0. */
goto free_return;
goto free_return;
/* We will log all the DFA states through which the dfa pass,
if nmatch > 1, or this dfa has "multibyte node", which is a
back-reference or a node which can accept multibyte character or
multi character collating element. */
{
/* Avoid overflow. */
{
err = REG_ESPACE;
goto free_return;
}
{
err = REG_ESPACE;
goto free_return;
}
}
else
match_first = start;
/* Check incrementally whether of not the input string match. */
| (t != NULL ? 1 : 0))
: 8);
for (;; match_first += incr)
{
err = REG_NOMATCH;
goto free_return;
/* Advance as rapidly as possible through the string, until we
find a plausible place to start matching. This may be done
with varying efficiency, so there are various possibilities:
only the most common of them are specialized, in order to
save on code size. We use a switch statement for speed. */
switch (match_kind)
{
case 8:
/* No fastmap. */
break;
case 7:
/* Fastmap with single-byte translation, match forward. */
++match_first;
case 6:
/* Fastmap without translation, match forward. */
++match_first;
{
? 0 : (unsigned char) string[match_first];
goto free_return;
}
break;
case 4:
case 5:
/* Fastmap without multi-byte translation, match backwards. */
while (match_first >= left_lim)
{
? 0 : (unsigned char) string[match_first];
break;
--match_first;
}
if (match_first < left_lim)
goto free_return;
break;
default:
/* In this case, we can't determine easily the current byte,
since it might be a component byte of a multibyte
character. Then we use the constructed buffer instead. */
for (;;)
{
/* If MATCH_FIRST is out of the valid range, reconstruct the
buffers. */
{
eflags);
goto free_return;
}
/* If MATCH_FIRST is out of the buffer, leave it as '\0'.
Note that MATCH_FIRST must not be smaller than 0. */
break;
match_first += incr;
{
err = REG_NOMATCH;
goto free_return;
}
}
break;
}
/* Reconstruct the buffers so that the matcher can assume that
the matching starts from the beginning of the buffer. */
goto free_return;
#ifdef RE_ENABLE_I18N
/* Don't consider this char as a possible match start if it part,
yet isn't the head, of a multibyte character. */
continue;
#endif
/* It seems to be appropriate one, then use the matcher. */
/* We assume that the matching starts from 0. */
if (match_last != REG_MISSING)
{
{
err = REG_ESPACE;
goto free_return;
}
else
{
{
}
{
if (err == REG_NOERROR)
break;
goto free_return;
}
else
break; /* We found a match. */
}
}
match_ctx_clean (&mctx);
}
#ifdef DEBUG
#endif
/* Set pmatch[] if we need. */
if (nmatch > 0)
{
/* Initialize registers. */
/* FIXME: This function should fail if mctx.match_last exceeds
the maximum possible regoff_t value. We need a new error
code REG_OVERFLOW. */
{
goto free_return;
}
/* At last, add the offset to the each registers, since we slided
the buffers so that we could assume that the matching starts
from 0. */
{
#ifdef RE_ENABLE_I18N
{
}
#else
#endif
}
{
}
if (dfa->subexp_map)
{
}
}
match_ctx_free (&mctx);
return err;
}
static reg_errcode_t
{
#ifdef DEBUG
#endif
/* Avoid overflow. */
return REG_ESPACE;
{
ret = REG_ESPACE;
goto free_return;
}
{
{
ret = REG_ESPACE;
goto free_return;
}
while (1)
{
goto free_return;
break;
do
{
--match_last;
if (! REG_VALID_INDEX (match_last))
{
ret = REG_NOMATCH;
goto free_return;
}
}
match_last + 1);
lim_states = NULL;
goto free_return;
}
else
{
goto free_return;
}
ret = REG_NOERROR;
return ret;
}
/* Acquire an initial state and return it.
We must select appropriate initial state depending on the context,
since initial states may have constraints like "\<", "^", etc.. */
static inline re_dfastate_t *
{
{
unsigned int context;
if (IS_WORD_CONTEXT (context))
return dfa->init_state_word;
else if (IS_ORDINARY_CONTEXT (context))
return dfa->init_state;
return dfa->init_state_begbuf;
else if (IS_NEWLINE_CONTEXT (context))
return dfa->init_state_nl;
else if (IS_BEGBUF_CONTEXT (context))
{
/* It is relatively rare case, then calculate on demand. */
context);
}
else
/* Must not happen? */
return dfa->init_state;
}
else
return dfa->init_state;
}
/* Check whether the regular expression match input string INPUT or not,
and return the index where the matching end. Return REG_MISSING if
there is no match, and return REG_ERROR in case of an error.
FL_LONGEST_MATCH means we want the POSIX longest matching.
If P_MATCH_FIRST is not NULL, and the match fails, it is set to the
next place where we may want to try matching.
Note that the matcher assume that the maching starts from the current
index of the buffer. */
static Idx
{
err = REG_NOERROR;
/* An initial state must not be NULL (invalid). */
{
return REG_ERROR;
}
{
/* Check OP_OPEN_SUBEXP in the initial state in case that we use them
later. E.g. Processing back references. */
{
at_init_state = false;
return err;
if (cur_state->has_backref)
{
return err;
}
}
}
/* If the RE accepts NULL string. */
{
if (!cur_state->has_constraint
{
if (!fl_longest_match)
return cur_str_idx;
else
{
match = 1;
}
}
}
{
{
{
return REG_ERROR;
}
}
{
/* Reached the invalid state or an error. Try to recover a valid
state using the state log, if available and if we have not
already found a valid (even if not the longest) match. */
return REG_ERROR;
|| (match && !fl_longest_match)
break;
}
if (BE (at_init_state, 0))
{
else
at_init_state = false;
}
{
/* Reached a halt state.
Check the halt state can satisfy the current context. */
if (!cur_state->has_constraint
{
/* We found an appropriate halt state. */
match = 1;
/* We found a match, do not modify match_first below. */
if (!fl_longest_match)
break;
}
}
}
if (p_match_first)
return match_last;
}
/* Check NODE match the current context. */
static bool
{
return false;
if (!constraint)
return true;
return false;
return true;
}
/* Check the halt state STATE match the current context.
Return 0 if not match, if the node, STATE has, is a halt node and
match the context, return the node. */
static Idx
{
Idx i;
unsigned int context;
#ifdef DEBUG
#endif
return 0;
}
/* Compute the next node to which "NFA" transit from NODE("NFA" is a NFA
corresponding to the DFA).
Return the destination node, and update EPS_VIA_NODES;
return REG_MISSING in case of errors. */
static Idx
struct re_fail_stack_t *fs)
{
Idx i;
bool ok;
{
return REG_ERROR;
/* Pick up a valid destination, or return REG_MISSING if none
is found. */
{
continue;
if (dest_node == REG_MISSING)
else
{
/* In order to avoid infinite loop like "(a*)*", return the second
epsilon-transition if the first was already considered. */
return candidate;
/* Otherwise, push the second epsilon-transition on the fail stack. */
return REG_ERROR;
/* We know we are going to exit. */
break;
}
}
return dest_node;
}
else
{
#ifdef RE_ENABLE_I18N
else
#endif /* RE_ENABLE_I18N */
if (type == OP_BACK_REF)
{
{
return REG_MISSING;
else if (naccepted)
{
naccepted) != 0)
return REG_MISSING;
}
}
if (naccepted == 0)
{
return REG_ERROR;
return dest_node;
}
}
if (naccepted != 0
{
dest_node)))
return REG_MISSING;
return dest_node;
}
}
return REG_MISSING;
}
static reg_errcode_t
{
{
struct re_fail_stack_ent_t *new_array;
return REG_ESPACE;
}
return REG_ESPACE;
return err;
}
static Idx
{
}
PMATCH.
Note: We assume that pmatch[0] is already set, and
pmatch[i].rm_so == pmatch[i].rm_eo == -1 for 0 < i < nmatch. */
static reg_errcode_t
{
struct re_fail_stack_t *fs;
bool prev_idx_match_malloced = false;
#ifdef DEBUG
#endif
if (fl_backtrack)
{
return REG_ESPACE;
}
else
else
{
if (prev_idx_match == NULL)
{
return REG_ESPACE;
}
prev_idx_match_malloced = true;
}
{
{
if (fs)
{
break;
{
return free_fail_stack_return (fs);
}
}
else
{
return REG_NOERROR;
}
}
/* Proceed to next node. */
&eps_via_nodes, fs);
{
{
return REG_ESPACE;
}
if (fs)
else
{
return REG_NOMATCH;
}
}
}
return free_fail_stack_return (fs);
}
static reg_errcode_t
{
if (fs)
{
{
}
}
return REG_NOERROR;
}
static void
{
if (type == OP_OPEN_SUBEXP)
{
/* We are at the first node of this sub expression. */
{
}
}
else if (type == OP_CLOSE_SUBEXP)
{
{
/* We are at the last node of this sub expression. */
{
/* This is a non-empty match or we are not inside an optional
subexpression. Accept this right away. */
}
else
{
/* We transited through an empty match for an optional
subexpression, like (a?)*, and this is not the subexp's
first match. Copy back the old content of the registers
so that matches of an inner subexpression are undone as
well, like in ((a?))*. */
else
/* We completed a subexpression, but it may be part of
an optional one, so do not update PREV_IDX_MATCH. */
}
}
}
}
/* This function checks the STATE_LOG from the SCTX->last_str_idx to 0
and sift the nodes in each states according to the following rules.
Updated state_log will be wrote to STATE_LOG.
Rules: We throw away the Node `a' in the STATE_LOG[STR_IDX] if...
1. When STR_IDX == MATCH_LAST(the last index in the state_log):
If `a' isn't the LAST_NODE and `a' can't epsilon transit to
the LAST_NODE, we throw away the node `a'.
2. When 0 <= STR_IDX < MATCH_LAST and `a' accepts
string `s' and transit to `b':
i. If 'b' isn't in the STATE_LOG[STR_IDX+strlen('s')], we throw
away the node `a'.
ii. If 'b' is in the STATE_LOG[STR_IDX+strlen('s')] but 'b' is
thrown away, we throw away the node `a'.
3. When 0 <= STR_IDX < MATCH_LAST and 'a' epsilon transit to 'b':
i. If 'b' isn't in the STATE_LOG[STR_IDX], we throw away the
node `a'.
ii. If 'b' is in the STATE_LOG[STR_IDX] but 'b' is thrown away,
we throw away the node `a'. */
static reg_errcode_t
{
int null_cnt = 0;
#ifdef DEBUG
#endif
/* Build sifted state_log[str_idx]. It has the nodes which can epsilon
transit to the last_node and the last_node itself. */
return err;
goto free_return;
/* Then check each states in the state_log. */
while (str_idx > 0)
{
/* Update counters. */
{
sizeof (re_dfastate_t *) * str_idx);
return REG_NOERROR;
}
--str_idx;
{
goto free_return;
}
/* Add all the nodes which satisfy the following conditions:
- It can epsilon transit to a node in CUR_DEST.
- It is in CUR_SRC.
And update state_log. */
goto free_return;
}
err = REG_NOERROR;
return err;
}
static reg_errcode_t
{
Idx i;
/* Then build the next sifted state.
We build the next sifted state on `cur_dest', and update
`sifted_states[str_idx]' with `cur_dest'.
Note:
`cur_dest' is the sifted state from `state_log[str_idx + 1]'.
`cur_src' points the node_set of the old `state_log[str_idx]'
(with the epsilon nodes pre-filtered out). */
{
int naccepted = 0;
bool ok;
#ifdef DEBUG
#endif
#ifdef RE_ENABLE_I18N
/* If the node may accept `multi byte'. */
#endif /* RE_ENABLE_I18N */
/* We don't check backreferences here.
See update_cur_sifted_state(). */
if (!naccepted
naccepted = 1;
if (naccepted == 0)
continue;
{
continue;
}
return REG_ESPACE;
}
return REG_NOERROR;
}
/* Helper functions. */
static reg_errcode_t
{
{
return err;
}
if (top < next_state_log_idx)
{
}
return REG_NOERROR;
}
static reg_errcode_t
{
{
{
return err;
return err;
}
}
return REG_NOERROR;
}
static reg_errcode_t
{
const re_node_set *candidates;
if (dest_nodes->nelem == 0)
else
{
if (candidates)
{
/* At first, add the nodes which can epsilon transit to a node in
DEST_NODE. */
return err;
/* Then, check the limitations in the current sift_context. */
{
return err;
}
}
return err;
}
{
return err;
}
return REG_NOERROR;
}
static reg_errcode_t
const re_node_set *candidates)
{
Idx i;
return err;
{
return REG_ESPACE;
for (i = 0; i < dest_nodes->nelem; i++)
}
&state->inveclosure);
}
static reg_errcode_t
const re_node_set *candidates)
{
{
continue;
{
|| (REG_VALID_NONZERO_INDEX (edst2)
{
{
return err;
}
}
}
}
{
{
}
}
return REG_NOERROR;
}
static bool
{
{
struct re_backref_cache_entry *ent;
/* In case of:
<src> <dst> ( <subexp> )
( <subexp> ) <src> <dst>
( <subexp1> <src> <subexp2> <dst> <subexp3> ) */
continue; /* This is unrelated limitation. */
else
return true;
}
return false;
}
static int
{
/* Else, we are on the boundary: examine the nodes on the epsilon
closure. */
{
{
case OP_BACK_REF:
if (bkref_idx != REG_MISSING)
{
do
{
int cpos;
continue;
if (subexp_idx < BITSET_WORD_BITS
&& !(ent->eps_reachable_subexps_map
continue;
/* Recurse trying to reach the OP_OPEN_SUBEXP and
OP_CLOSE_SUBEXP cases below. But, if the
destination node is the same node as the source
node, don't recurse because it would cause an
infinite loop: a regex that exhibits this behavior
is ()\1*\1* */
{
if (boundaries & 1)
return -1;
else /* if (boundaries & 2) */
return 0;
}
cpos =
return -1;
return 0;
if (subexp_idx < BITSET_WORD_BITS)
}
}
break;
case OP_OPEN_SUBEXP:
return -1;
break;
case OP_CLOSE_SUBEXP:
return 0;
break;
default:
break;
}
}
}
static int
{
int boundaries;
/* If we are outside the range of the subexpression, return -1 or 1. */
return -1;
return 1;
/* If we are within the subexpression, return 0. */
if (boundaries == 0)
return 0;
/* Else, examine epsilon closure. */
}
/* Check the limitations of sub expressions LIMITS, and remove the nodes
which are against limitations from DEST_NODES. */
static reg_errcode_t
{
{
struct re_backref_cache_entry *ent;
continue; /* This is unrelated limitation. */
{
{
if (type == OP_OPEN_SUBEXP
else if (type == OP_CLOSE_SUBEXP
}
/* Check the limitation of the open subexpression. */
/* Note that (ent->subexp_to = str_idx != ent->subexp_from). */
if (REG_VALID_INDEX (ops_node))
{
return err;
}
/* Check the limitation of the close subexpression. */
if (REG_VALID_INDEX (cls_node))
{
cls_node))
{
/* It is against this limitation.
Remove it form the current sifted state. */
return err;
--node_idx;
}
}
}
else /* (ent->subexp_to != str_idx) */
{
{
{
continue;
/* It is against this limitation.
Remove it form the current sifted state. */
return err;
}
}
}
}
return REG_NOERROR;
}
static reg_errcode_t
{
if (first_idx == REG_MISSING)
return REG_NOERROR;
{
struct re_backref_cache_entry *entry;
/* Avoid infinite loop for the REs like "()\1+". */
continue;
if (type != OP_BACK_REF)
continue;
do
{
bool ok;
continue;
continue;
{
local_sctx = *sctx;
goto free_return;
}
{
err = REG_ESPACE;
goto free_return;
}
goto free_return;
{
str_idx + 1);
goto free_return;
}
/* mctx->bkref_ents may have changed, reload the pointer. */
}
}
err = REG_NOERROR;
{
}
return err;
}
#ifdef RE_ENABLE_I18N
static int
{
int naccepted;
/* Check the node can accept `multi byte'. */
/* The node can't accept the `multi byte', or the
destination was already thrown away, then the node
could't accept the current input `multi byte'. */
naccepted = 0;
/* Otherwise, it is sure that the node could accept
`naccepted' bytes input. */
return naccepted;
}
#endif /* RE_ENABLE_I18N */
/* Functions for state transition. */
/* Return the next state to which the current state STATE will transit by
accepting the current input byte, and update STATE_LOG if necessary.
update the destination of STATE_LOG. */
static re_dfastate_t *
{
unsigned char ch;
#ifdef RE_ENABLE_I18N
/* If the current state can accept multibyte. */
{
return NULL;
}
#endif /* RE_ENABLE_I18N */
/* Then decide the next state with the single byte. */
#if 0
if (0)
/* don't use transition table */
#endif
/* Use transition table */
for (;;)
{
{
unsigned int context;
if (IS_WORD_CONTEXT (context))
else
}
{
*err = REG_ESPACE;
return NULL;
}
/* Retry, we now have a transition table. */
}
}
/* Update the state_log if we need */
static re_dfastate_t *
{
{
}
{
}
else
{
unsigned int context;
/* If (state_log[cur_idx] != 0), it implies that cur_idx is
back reference. Then the next state is the union set of
these destinations and the results of the transition table. */
if (next_state != NULL)
{
return NULL;
}
else
next_nodes = *log_nodes;
/* Note: We already add the nodes of the initial state,
then we don't need to add them here. */
/* We don't need to check errors here, since the return value of
this function is next_state and ERR is already set. */
if (table_nodes != NULL)
}
{
/* Check OP_OPEN_SUBEXP in the current state in case that we use them
later. We must check them here, since the back references in the
next state might use them. */
cur_idx);
return NULL;
/* If the next state has back references. */
if (next_state->has_backref)
{
return NULL;
}
}
return next_state;
}
/* Skip bytes in the input that correspond to part of a
multi-byte match, then look in the log for a state
from which to restart matching. */
static re_dfastate_t *
{
do
{
do
{
if (++cur_str_idx > max)
return NULL;
}
}
return cur_state;
}
/* Helper functions for transit_state. */
/* From the node set CUR_NODES, pick up the nodes whose types are
OP_OPEN_SUBEXP and which have corresponding back references in the regular
expression. And register them to use them later for evaluating the
correspoding back references. */
static reg_errcode_t
{
/* TODO: This isn't efficient.
Because there might be more than one nodes whose types are
OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
nodes.
E.g. RE: (a){2} */
{
&& (dfa->used_bkref_map
{
return err;
}
}
return REG_NOERROR;
}
#if 0
/* Return the next state to which the current state STATE will transit by
accepting the current input byte. */
static re_dfastate_t *
{
unsigned int context;
return NULL;
{
{
{
return NULL;
}
}
}
/* We don't need to check errors here, since the return value of
this function is next_state and ERR is already set. */
return next_state;
}
#endif
#ifdef RE_ENABLE_I18N
static reg_errcode_t
{
Idx i;
{
int naccepted;
unsigned int context;
continue;
{
context))
continue;
}
/* How many bytes the node can accept? */
if (naccepted == 0)
continue;
/* The node can accepts `naccepted' bytes. */
: mctx->max_mb_elem_len);
return err;
#ifdef DEBUG
#endif
if (dest_state == NULL)
dest_nodes = *new_nodes;
else
{
return err;
}
if (dest_state != NULL)
return err;
}
return REG_NOERROR;
}
#endif /* RE_ENABLE_I18N */
static reg_errcode_t
{
Idx i;
{
unsigned int context;
/* Check whether `node' is a backreference or not. */
continue;
if (node->constraint)
{
continue;
}
/* `node' is a backreference.
Check the substring which the substring matched. */
goto free_return;
/* And add the epsilon closures (which is `new_dest_nodes') of
the backreference to appropriate state_log. */
#ifdef DEBUG
#endif
{
struct re_backref_cache_entry *bkref_ent;
continue;
new_dest_nodes = (subexp_len == 0
- bkref_ent->subexp_from);
/* Add `new_dest_node' to state_log. */
if (dest_state == NULL)
{
context);
&& err != REG_NOERROR, 0))
goto free_return;
}
else
{
{
goto free_return;
}
&& err != REG_NOERROR, 0))
goto free_return;
}
/* We need to check recursively if the backreference can epsilon
transit. */
if (subexp_len == 0
{
goto free_return;
goto free_return;
}
}
}
err = REG_NOERROR;
return err;
}
/* Enumerate all the candidates which the backreference BKREF_NODE can match
at BKREF_STR_IDX, and register them by match_ctx_add_entry().
Note that we might collect inappropriate candidates here.
However, the cost of checking them strictly here is too high, then we
delay these checking for prune_impossible_nodes(). */
static reg_errcode_t
{
/* Return if we have already checked BKREF_NODE at BKREF_STR_IDX. */
if (cache_idx != REG_MISSING)
{
const struct re_backref_cache_entry *entry
do
return REG_NOERROR; /* We already checked it. */
}
/* For each sub expression */
{
continue; /* It isn't related. */
/* At first, check the last node of sub expressions we already
evaluated. */
{
/* The matched string by the sub expression match with the substring
at the back reference? */
if (sl_str_diff > 0)
{
{
/* Not enough chars for a successful match. */
break;
+ sl_str_diff);
return err;
}
/* We don't need to search this sub expression any more. */
break;
}
sl_str += sl_str_diff;
/* Reload buf, since the preceding call might have reallocated
the buffer. */
if (err == REG_NOMATCH)
continue;
return err;
}
continue;
if (sub_last_idx > 0)
++sl_str;
/* Then, search for the other last nodes of the sub expression. */
{
const re_node_set *nodes;
/* The matched string by the sub expression match with the substring
at the back reference? */
if (sl_str_off > 0)
{
{
/* If we are at the end of the input, we cannot match. */
break;
return err;
}
break; /* We don't need to search this sub expression
any more. */
}
continue;
/* Does this state have a ')' of the sub expression? */
if (cls_node == REG_MISSING)
continue; /* No. */
{
return REG_ESPACE;
}
/* Can the OP_OPEN_SUBEXP node arrive the OP_CLOSE_SUBEXP node
in the current context? */
if (err == REG_NOMATCH)
continue;
return err;
return REG_ESPACE;
if (err == REG_NOMATCH)
continue;
}
}
return REG_NOERROR;
}
/* Helper functions for get_subexp(). */
/* Check SUB_LAST can arrive to the back reference BKREF_NODE at BKREF_STR.
If it can arrive, register the sub expression expressed with SUB_TOP
and SUB_LAST. */
static reg_errcode_t
{
/* Can the subexpression arrive the back reference? */
if (err != REG_NOERROR)
return err;
return err;
}
/* Find the first node which is '(' or ')' and whose index is SUBEXP_IDX.
Search '(' if FL_OPEN, or search ')' otherwise.
TODO: This function isn't efficient...
Because there might be more than one nodes whose types are
OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
nodes.
E.g. RE: (a){2} */
static Idx
{
{
return cls_node;
}
return REG_MISSING;
}
/* Check whether the node TOP_NODE at TOP_STR can arrive to the node
LAST_NODE at LAST_STR. We record the path onto PATH since it will be
heavily reused.
Return REG_NOERROR if it can arrive, or REG_NOMATCH otherwise. */
static reg_errcode_t
{
unsigned int context;
/* Extend the buffer if we need. */
{
return REG_ESPACE;
return REG_ESPACE;
}
/* Temporary modify MCTX. */
/* Setup initial node set. */
{
return err;
{
return err;
}
}
else
{
{
return err;
}
else
}
{
if (next_nodes.nelem)
{
subexp_num, type);
{
return err;
}
}
{
return err;
}
}
{
{
{
return err;
}
}
if (cur_state)
{
&next_nodes);
{
return err;
}
}
++str_idx;
if (next_nodes.nelem)
{
{
return err;
}
subexp_num, type);
{
return err;
}
}
{
return err;
}
}
/* Fix MCTX. */
/* Then check the current node set has the node LAST_NODE. */
return REG_NOERROR;
return REG_NOMATCH;
}
/* Helper functions for check_arrival. */
/* Calculate the destination nodes of CUR_NODES at STR_IDX, and append them
to NEXT_NODES.
TODO: This function is similar to the functions transit_state*(),
however this function has many additional works.
Can't we unify them? */
static reg_errcode_t
{
bool ok;
{
int naccepted = 0;
#ifdef DEBUG
#endif
#ifdef RE_ENABLE_I18N
/* If the node may accept `multi byte'. */
{
str_idx);
if (naccepted > 1)
{
if (dest_state)
{
{
return err;
}
}
{
return REG_ESPACE;
}
&union_set);
&& err != REG_NOERROR, 0))
{
return err;
}
}
}
#endif /* RE_ENABLE_I18N */
if (naccepted
{
{
return REG_ESPACE;
}
}
}
return REG_NOERROR;
}
/* For all the nodes in CUR_NODES, add the epsilon closures of them to
CUR_NODES, however exclude the nodes which are:
- inside the sub expression whose number is EX_SUBEXP, if FL_OPEN.
- out of the sub expression whose number is EX_SUBEXP, if !FL_OPEN.
*/
static reg_errcode_t
{
#ifdef DEBUG
#endif
return err;
/* Create a new node set NEW_NODES with the nodes which are epsilon
closures of the node in CUR_NODES. */
{
if (outside_node == REG_MISSING)
{
/* There are no problematic nodes, just merge them. */
{
return err;
}
}
else
{
/* There are problematic nodes, re-calculate incrementally. */
{
return err;
}
}
}
return REG_NOERROR;
}
/* Helper function for check_arrival_expand_ecl.
Check incrementally the epsilon closure of TARGET, and if it isn't
problematic append it to DST_NODES. */
static reg_errcode_t
{
{
bool ok;
{
if (type == OP_CLOSE_SUBEXP)
{
return REG_ESPACE;
}
break;
}
return REG_ESPACE;
break;
{
return err;
}
}
return REG_NOERROR;
}
/* For all the back references in the current state, calculate the
destination of the back references by the appropriate entry
in MCTX->BKREF_ENTS. */
static reg_errcode_t
{
struct re_backref_cache_entry *ent;
if (cache_idx_start == REG_MISSING)
return REG_NOERROR;
do
{
/* Is this entry ENT is appropriate? */
continue; /* No. */
/* Calculate the destination of the back reference, and append it
to MCTX->STATE_LOG. */
{
/* The backreference did epsilon transit, we must re-check all the
node in the current state. */
continue;
|| err3 != REG_NOERROR, 0))
{
return err;
}
/* TODO: It is still inefficient... */
goto restart;
}
else
{
{
bool ok;
continue;
{
return err;
}
}
else
{
return err;
}
&& err != REG_NOERROR, 0))
return err;
}
}
return REG_NOERROR;
}
/* Build transition table for the state.
Return true if successful. */
static bool
{
Idx i, j;
int ch;
bool need_word_trtable = false;
bool dests_node_malloced = false;
bool dest_states_malloced = false;
struct dests_alloc
{
} *dests_alloc;
/* We build DFA states which corresponds to the destination nodes
from `state'. `dests_node[i]' represents the nodes which i-th
destination state contains, and `dests_ch[i]' represents the
characters which i-th destination state accepts. */
if (__libc_use_alloca (sizeof (struct dests_alloc)))
else
{
return false;
dests_node_malloced = true;
}
/* Initialize transiton table. */
/* At first, group all nodes belonging to `state' into several
destinations. */
{
if (dests_node_malloced)
free (dests_alloc);
if (ndests == 0)
{
return true;
}
return false;
}
goto out_free;
/* Avoid arithmetic overflow in size calculation. */
/ (3 * sizeof (re_dfastate_t *)))
< ndests),
0))
goto out_free;
dest_states = (re_dfastate_t **)
else
{
dest_states = (re_dfastate_t **)
{
if (dest_states_malloced)
free (dest_states);
for (i = 0; i < ndests; ++i)
re_node_set_free (dests_node + i);
if (dests_node_malloced)
free (dests_alloc);
return false;
}
dest_states_malloced = true;
}
/* Then build the states for all destinations. */
for (i = 0; i < ndests; ++i)
{
/* Merge the follows of this destination states. */
for (j = 0; j < dests_node[i].nelem; ++j)
{
if (next_node != REG_MISSING)
{
goto out_free;
}
}
goto out_free;
/* If the new state has context constraint,
build appropriate states for these contexts. */
if (dest_states[i]->has_constraint)
{
goto out_free;
need_word_trtable = true;
goto out_free;
}
else
{
dest_states_word[i] = dest_states[i];
dest_states_nl[i] = dest_states[i];
}
}
if (!BE (need_word_trtable, 0))
{
/* We don't care about whether the following character is a word
character, or we are in a single-byte character set so we can
discern by looking at the character code: allocate a
256-entry transition table. */
goto out_free;
/* For all characters ch...: */
for (i = 0; i < BITSET_WORDS; ++i)
elem;
{
/* There must be exactly one destination which accepts
character ch. See group_nodes_into_DFAstates. */
;
/* j-th destination accepts the word character ch. */
else
}
}
else
{
/* We care about whether the following character is a word
character, and we are in a multi-byte character set: discern
by looking at the character code: build two 256-entry
transition tables, one starting at trtable[0] and one
starting at trtable[SBC_MAX]. */
goto out_free;
/* For all characters ch...: */
for (i = 0; i < BITSET_WORDS; ++i)
elem;
{
/* There must be exactly one destination which accepts
character ch. See group_nodes_into_DFAstates. */
;
/* j-th destination accepts the word character ch. */
}
}
/* new line */
{
/* The current state accepts newline character. */
for (j = 0; j < ndests; ++j)
{
/* k-th destination accepts newline character. */
if (need_word_trtable)
/* There must be only one destination which accepts
newline. See group_nodes_into_DFAstates. */
break;
}
}
if (dest_states_malloced)
free (dest_states);
for (i = 0; i < ndests; ++i)
re_node_set_free (dests_node + i);
if (dests_node_malloced)
free (dests_alloc);
return true;
}
/* Group all nodes belonging to STATE into several destinations.
Then for all destinations, set the nodes belonging to the destination
to DESTS_NODE[i] and set the characters accepted by the destination
to DEST_CH[i]. This function return the number of destinations. */
static Idx
{
bool ok;
Idx i, j, k;
ndests = 0;
/* For all the nodes belonging to `state', */
{
/* Enumerate all single byte character this node can accept. */
else if (type == SIMPLE_BRACKET)
{
}
{
#ifdef RE_ENABLE_I18N
else
#endif
}
#ifdef RE_ENABLE_I18N
else if (type == OP_UTF8_PERIOD)
{
if (ASCII_CHARS % BITSET_WORD_BITS == 0)
else
}
#endif
else
continue;
/* Check the `accepts' and sift the characters which are not
match it the context. */
if (constraint)
{
{
if (accepts_newline)
else
continue;
}
if (constraint & NEXT_ENDBUF_CONSTRAINT)
{
continue;
}
if (constraint & NEXT_WORD_CONSTRAINT)
{
bitset_word_t any_set = 0;
{
continue;
}
#ifdef RE_ENABLE_I18N
for (j = 0; j < BITSET_WORDS; ++j)
else
#endif
for (j = 0; j < BITSET_WORDS; ++j)
if (!any_set)
continue;
}
{
bitset_word_t any_set = 0;
{
continue;
}
#ifdef RE_ENABLE_I18N
for (j = 0; j < BITSET_WORDS; ++j)
else
#endif
for (j = 0; j < BITSET_WORDS; ++j)
if (!any_set)
continue;
}
}
/* Then divide `accepts' into DFA states, or create a new
state. Above, we make sure that accepts is not empty. */
for (j = 0; j < ndests; ++j)
{
/* Flags, see below. */
/* Optimization, skip if this state doesn't accept the character. */
continue;
/* Enumerate the intersection set of this state and `accepts'. */
has_intersec = 0;
for (k = 0; k < BITSET_WORDS; ++k)
/* And skip if the intersection set is empty. */
if (!has_intersec)
continue;
/* Then check if this state is a subset of `accepts'. */
not_subset = not_consumed = 0;
for (k = 0; k < BITSET_WORDS; ++k)
{
}
/* If this state isn't a subset of `accepts', create a
new group state, which has the `remains'. */
if (not_subset)
{
goto error_return;
++ndests;
}
/* Put the position in the current group. */
goto error_return;
/* If all characters are consumed, go to next node. */
if (!not_consumed)
break;
}
/* Some characters remain, create a new group. */
if (j == ndests)
{
goto error_return;
++ndests;
}
}
return ndests;
for (j = 0; j < ndests; ++j)
re_node_set_free (dests_node + j);
return REG_MISSING;
}
#ifdef RE_ENABLE_I18N
/* Check how many bytes the node `dfa->nodes[node_idx]' accepts.
Return the number of the bytes the node accepts.
STR_IDX is the current index of the input string.
This function handles the nodes which can accept one character, or
one collating element like '.', '[a-z]', opposite to the other nodes
can only accept one byte. */
static int
{
Idx i;
{
return 0;
return 0;
if (c < 0xe0)
return (d < 0x80 || d > 0xbf) ? 0 : 2;
else if (c < 0xf0)
{
char_len = 3;
if (c == 0xe0 && d < 0xa0)
return 0;
}
else if (c < 0xf8)
{
char_len = 4;
if (c == 0xf0 && d < 0x90)
return 0;
}
else if (c < 0xfc)
{
char_len = 5;
if (c == 0xf8 && d < 0x88)
return 0;
}
else if (c < 0xfe)
{
char_len = 6;
if (c == 0xfc && d < 0x84)
return 0;
}
else
return 0;
return 0;
for (i = 1; i < char_len; ++i)
{
if (d < 0x80 || d > 0xbf)
return 0;
}
return char_len;
}
{
if (char_len <= 1)
return 0;
/* FIXME: I don't think this if is needed, as both '\n'
and '\0' are char_len == 1. */
/* '.' accepts any one character except the following two cases. */
return 0;
return char_len;
}
return 0;
{
# ifdef _LIBC
const unsigned char *pin
Idx j;
# endif /* _LIBC */
int match_len = 0;
/* match with multibyte character? */
{
}
/* match with character_class? */
for (i = 0; i < cset->nchar_classes; ++i)
{
{
}
}
# ifdef _LIBC
if (nrules != 0)
{
unsigned int in_collseq = 0;
const char *collseqwc;
/* This #include defines a local function! */
/* match with collating_symbol? */
if (cset->ncoll_syms)
extra = (const unsigned char *)
for (i = 0; i < cset->ncoll_syms; ++i)
{
/* Compare the length of input collating element and
the length of current collating element. */
continue;
/* Compare each bytes. */
for (j = 0; j < *coll_sym; j++)
break;
if (j == *coll_sym)
{
/* Match if every bytes is equal. */
match_len = j;
}
}
{
{
}
else
}
/* match with range expression? */
{
}
/* match with equivalence_class? */
if (cset->nequiv_classes)
{
weights = (const unsigned char *)
extra = (const unsigned char *)
if (idx > 0)
for (i = 0; i < cset->nequiv_classes; ++i)
{
{
while (cnt <= weight_len
++cnt;
if (cnt > weight_len)
{
}
}
}
}
}
else
# endif /* _LIBC */
{
/* match with range expression? */
#else
#endif
{
{
}
}
}
return match_len;
else
{
if (match_len > 0)
return 0;
else
}
}
return 0;
}
# ifdef _LIBC
static unsigned int
{
if (nrules == 0)
{
if (mbs_len == 1)
{
/* No valid character. Match it as a single byte character. */
const unsigned char *collseq = (const unsigned char *)
}
return UINT_MAX;
}
else
{
const unsigned char *extra = (const unsigned char *)
{
int mbs_cnt;
bool found = false;
/* Skip the name of collating element name. */
if (mbs_len == elem_mbs_len)
{
break;
if (mbs_cnt == elem_mbs_len)
/* Found the entry. */
found = true;
}
/* Skip the byte sequence of the collating element. */
idx += elem_mbs_len;
/* Adjust for the alignment. */
/* Skip the collation sequence value. */
/* Skip the wide char sequence of the collating element. */
/* If we found the entry, return the sequence value. */
if (found)
/* Skip the collation sequence value. */
}
return UINT_MAX;
}
}
# endif /* _LIBC */
#endif /* RE_ENABLE_I18N */
/* Check whether the node accepts the byte which is IDX-th
byte of the INPUT. */
static bool
{
unsigned char ch;
{
case CHARACTER:
return false;
break;
case SIMPLE_BRACKET:
return false;
break;
#ifdef RE_ENABLE_I18N
case OP_UTF8_PERIOD:
if (ch >= ASCII_CHARS)
return false;
/* FALLTHROUGH */
#endif
case OP_PERIOD:
return false;
break;
default:
return false;
}
if (node->constraint)
{
/* The node has constraints. Check whether the current context
satisfies the constraints. */
return false;
}
return true;
}
/* Extend the buffers, if the buffers have run out. */
static reg_errcode_t
{
/* Avoid overflow. */
return REG_ESPACE;
/* Double the lengthes of the buffers. */
return ret;
{
/* And double the length of state_log. */
/* XXX We have no indication of the size of this buffer. If this
allocation fail we have no indication that the state_log array
does not have the right size. */
return REG_ESPACE;
}
/* Then reconstruct the buffers. */
{
#ifdef RE_ENABLE_I18N
{
return ret;
}
else
#endif /* RE_ENABLE_I18N */
}
else
{
#ifdef RE_ENABLE_I18N
else
#endif /* RE_ENABLE_I18N */
{
}
}
return REG_NOERROR;
}
/* Functions for matching context. */
/* Initialize MCTX. */
static reg_errcode_t
{
if (n > 0)
{
/* Avoid overflow. */
MAX (sizeof (struct re_backref_cache_entry),
sizeof (re_sub_match_top_t *));
return REG_ESPACE;
return REG_ESPACE;
}
/* Already zero-ed by the caller.
else
mctx->bkref_ents = NULL;
mctx->nbkref_ents = 0;
mctx->nsub_tops = 0; */
mctx->abkref_ents = n;
return REG_NOERROR;
}
/* Clean the entries which depend on the current input in MCTX.
This function must be invoked when the matcher changes the start index
of the input, or changes the input string. */
static void
{
{
{
}
{
}
}
mctx->nbkref_ents = 0;
}
/* Free all the memory associated with MCTX. */
static void
{
/* First, free all the memory associated with MCTX->SUB_TOPS. */
}
/* Add a new backreference entry to MCTX.
Note that we assume that caller never call this function with duplicate
entry, and call with STR_IDX which isn't smaller than any existing entry.
*/
static reg_errcode_t
{
{
struct re_backref_cache_entry* new_entry;
{
return REG_ESPACE;
}
}
if (mctx->nbkref_ents > 0
/* This is a cache that saves negative results of check_dst_limits_calc_pos.
If bit N is clear, means that this entry won't epsilon-transition to
an OP_OPEN_SUBEXP or OP_CLOSE_SUBEXP for the N+1-th subexpression. If
it is set, check_dst_limits_calc_pos_1 will recurse and try to find one
such node.
A backreference does not epsilon-transition unless it is empty, so set
to all zeros if FROM != TO. */
return REG_NOERROR;
}
/* Return the first entry with the same str_idx, or REG_MISSING if none is
found. Note that MCTX->BKREF_ENTS is already sorted by MCTX->STR_IDX. */
static Idx
{
{
else
}
return left;
else
return REG_MISSING;
}
/* Register the node NODE, whose type is OP_OPEN_SUBEXP, and which matches
at STR_IDX. */
static reg_errcode_t
{
#ifdef DEBUG
#endif
{
return REG_ESPACE;
}
return REG_ESPACE;
return REG_NOERROR;
}
/* Register the node NODE, whose type is OP_CLOSE_SUBEXP, and which matches
at STR_IDX, whose corresponding OP_OPEN_SUBEXP is SUB_TOP. */
static re_sub_match_last_t *
{
{
return NULL;
}
{
}
return new_entry;
}
static void
{
}