/* match-regexp.c - functions for comparing a string to a regexp
*
****************************************************************
* Copyright (C) 1998, 2000 Thomas Lord
*
* See the file "COPYING" for further information about
* the copyright and warranty status of this work.
*/
/* #define TRACE */
#include "hackerlab/bugs/panic.h"
#include "hackerlab/char/char-class.h"
#include "hackerlab/char/str.h"
#include "hackerlab/bitsets/bits.h"
#include "hackerlab/rx/nfa-cache.h"
#include "hackerlab/rx/dfa.h"
#include "hackerlab/rx/escape.h"
#ifdef TRACE
#include "hackerlab/vu/safe.h"
#include "hackerlab/rx/dbug.h"
int rx_trace = 0;
int rx_depth_limit = 0;
#endif
#include "hackerlab/rx-posix/errnorx.h"
#include "hackerlab/rx-posix/match-regexp.h"
static unsigned long solns_allocated;
static unsigned long solns_freed;
#define max0(N) (((N) >= 0) ? (N) : 0)
/* __STDC__ prototypes for static functions */
static int rx_str_vmfn (void * closure,
const t_uchar ** burstp,
rx_off_t * lenp,
rx_off_t * offsetp,
rx_off_t start,
rx_off_t end,
rx_off_t need);
static int rx_str_contextfn (void * closure,
struct rx_exp_node * node,
rx_off_t start,
rx_off_t end,
struct rx_registers * regs);
static int rx_solution_fit_cset_p (struct rx_solutions * solns);
static int rx_solution_fit_str_p (struct rx_solutions * solns);
static int rx_solution_fits (struct rx_solutions * solns);
static int rx_dfa_longest_counting (int * label,
size_t * match_len,
size_t * matches_count,
struct rx_dfa * dfa,
const t_uchar * str,
size_t len);
static int rx_longest_split_guess (volatile int * label, struct rx_solutions * solns);
static int save_nested_registers (struct rx_solutions * solns);
static void restore_nested_registers (struct rx_solutions * solns);
static int rx_next_solution_internal (struct rx_solutions * solns, jmp_buf * err_escape, int depth);
/************************************************************************
*(h0 "Regexp Matching"
* :includes ("rx-posix/match-regexp.h"))
*
*
* In xref:"Regexp Expression Trees", we saw how to build expression
* trees for regexps and elsewhere how to convert those regexps which
* are regular expressions to DFA. In xref:"DFA String Comparisons"
* we saw DFA-based functions that can compare a string to a regular
* expression.
*
* But what about those regexps which are not regular expressions? So
* far, except for the quasi-standard functions `regexec' and
* `regnexec', we have no way to match non-regular regexps.
*
* The functions in this chapter implement regexp matching. The
* interface is very detailed, but there are only a few functions and
* they are conceptually simple.
*
*/
/*(menu)
*/
/************************************************************************
*(h1 "An Overview of the Regexp Matching Interface")
*
* Given a regexp, and an input string, a regexp comparison function
* should return a value that indicates whether or not the string
* matches, and an array of values filled in with the substring
* positions of elements of the input string that matched the
* parenthesized subexpressions in the match. (For example, see
* xref:"regexec".) We start out intending to build a regexp
* comparison function that fits the preceeding description and make
* two observations.
*
* First, the function needs to be recursive because we only know how
* to check whether or not some kinds of regexp match by checking
* whether their subexpressions match.
*
* Second, the function needs to return more than one set of return
* values because a regexp can often match a string in more than one
* way -- returning a different set of values for each way of
* matching. To find the best overall match for a regexp, we may have
* to consider more than one way of matching the subexpressions of
* that regexp. In fact, the Posix standard for regexps essentially
* mandates that we perform a potentially exhaustive search through
* the possible ways of matching subexpressions. So, our recursive
* comparison function has to be able to find all of the different
* ways of matching a particular regexp and string to facilitate that
* search.
*
* Fortunately, we are able to order the search through the set of
* subexpressions in such a way that we will often find the best
* answer (and know it is the best answer) early. So while our
* recursive comparison function has to be able to return all possible
* solutions, it should be free to return them in the order we will
* search them, and to only actually construct a particular solution
* if it is actually required during a search. We can usually save
* time by not building solutions that we don't need to search.
*
* The functions in this chapter implement such a recursive comparison
* function. Given a regexp and a string, the functions return a
* lazilly-constructed stream of all of the possible ways of matching
* the regexp to the string. The stream is sorted; in the solution
* stream of a regexp subexpression, the best match, according to the
* rules mandated by Posix, is always the earliest match in the stream
* that also satisfies the constraints of the overall match of the
* containing expressions.
*
* You build one of these streams of subexpression solutions by calling
* `rx_make_solutions', passing the regexp and input string. You
* read off elements of the stream by calling `rx_next_solution' which
* actually does the work of computing the next solution in the list.
*
* Implementing a function like `regexec' or `regnexec' is easy.
* `regexec' iterates over each possible starting point for a match:
*
* for (start_pos = 0; start_pos < string_length; ++start_pos)
*
* At each starting position, `regexec' iterates through each possible
* ending position:
*
* for (end_pos = string_length; end_pos >= start_pos; --end_pos)
*
* For each possible starting and ending position, `regexec'
* constructs a stream of regexp solutions for that substring (by
* calling `rx_make_solutions'). It tries to read the first solution
* on that stream by calling `rx_next_solution'. If the stream is not
* empty, the first solution in the stream is the best possible
* solution, and it is returned from `regexec'.
*
* When `regexec' calls `rx_next_solution' to find out if the stream
* of solutions is empty, more streams of solutions may be created for
* the subexpressions of the overall regexp. Those recursively
* created streams may have to be searched to find an overall
* solution. Even though `regexec' only reads one solution from the
* stream it creates, the recursive calls to `rx_next_solution' may
* read many solutions from the streams they create.
*
* As just described, you might think `regexec' and `regnexec' do a
* lot of work (running so many separate regexp comparisons). You
* would be right. Consequently, the real-world implementations of
* `regexec' and `regnexec' employ several tricks to reduce the number
* of regexp comparisons actually performed -- they try to avoid
* calling the functions in this chapter. In addition, the functions
* in this chapter employ several tricks to avoid searching
* recursively created streams of solutions. Still, in the general
* case, functions like `regexec' use the interface described here in
* the computationally expensive way described above. (The exact
* complexity of a search depends on the particular regexp but in the
* worst cases, it is a polynomial function (of high degree) of the
* length of the string being searched.)
*
*/
/************************************************************************
*(h1 "Regexp Match Function Data Structures")
*
*/
/*(c #s"struct rx_solutions" :category type)
* struct rx_solutions;
*
* This opaque structure type represents the stream of solutions for
* matching a particular regexp against a particular string.
*/
struct rx_solutions
{
int small_p;
int step;
int cset_size;
struct rx_exp_node * exp;
struct rx_exp_node ** subexps;
int nsub;
struct rx_registers * regs;
rx_off_t start;
rx_off_t end;
rx_vmfn vmfn;
rx_contextfn contextfn;
void * closure;
struct rx_unfa * dfa;
struct rx_dfa match_engine;
int certainly_fits; /* we know in advance that rx_solution_fits returns 1 */
int certain_final_tag;
int no_fancy_guessing;
struct rx_unfa * left_dfa;
struct rx_dfa left_match_engine;
rx_off_t split_guess;
struct rx_solutions * left;
struct rx_solutions * right;
int interval_x;
int interval_from;
int interval_to;
rx_off_t * saved_rm_so;
rx_off_t * saved_rm_eo;
int final_tag;
};
static struct rx_solutions no_solutions;
#if 0
/*(c #s"struct rx_registers" :category type)
* struct rx_registers;
*
* This structure type holds information about the match position
* of one regexp subexpression in a (potentially) larger string.
* It includes at least these fields:
*
insert*/
struct rx_registers
{
rx_off_t rm_so; /* The start of the match. */
rx_off_t rm_eo; /* The end of the match. */
};
/*end-insert
*/
#endif
/************************************************************************
* Low Level Support for Basic String Matching
*
*/
struct rx_str_closure
{
struct rx_context_rules rules;
const t_uchar * str;
rx_off_t len;
};
static int
rx_str_vmfn (void * closure,
const t_uchar ** burstp,
rx_off_t * lenp,
rx_off_t * offsetp,
rx_off_t start,
rx_off_t end,
rx_off_t need)
{
struct rx_str_closure * strc;
strc = (struct rx_str_closure *)closure;
if ( (need < 0)
|| (need > strc->len))
return 0;
*burstp = strc->str;
*lenp = strc->len;
*offsetp = 0;
return 0;
}
static int
rx_str_contextfn (void * closure,
struct rx_exp_node * node,
rx_off_t start,
rx_off_t end,
struct rx_registers * regs)
{
struct rx_str_closure * strc;
strc = (struct rx_str_closure *)closure;
switch (node->intval)
{
case '1': case '2': case '3': case '4': case '5':
case '6': case '7': case '8': case '9':
{
int cmp;
int regn;
regn = node->intval - '0';
if ( (regs[regn].rm_so == -1)
|| ((end - start) != (regs[regn].rm_eo - regs[regn].rm_so)))
return 0;
else
{
if (strc->rules.case_indep)
cmp = str_casecmp_n ((t_uchar *)strc->str + start,
end - start,
(t_uchar *)strc->str + regs[regn].rm_so,
end - start);
else
cmp = str_cmp_n ((t_uchar *)strc->str + start,
end - start,
(t_uchar *)strc->str + regs[regn].rm_so,
end - start);
return (!cmp
? 1
: 0);
}
}
case '^':
{
return (( (start == end)
&& ( ((start == 0) && !strc->rules.not_bol)
|| ( (start > 0)
&& strc->rules.newline_anchor
&& (strc->str[start - 1] == '\n'))))
? 1
: 0);
}
case '$':
{
return (( (start == end)
&& ( ((start == strc->len) && !strc->rules.not_eol)
|| ( (start < strc->len)
&& strc->rules.newline_anchor
&& (strc->str[start] == '\n'))))
? 1
: 0);
}
default:
while (1)
panic ("unrecognized context function in rx_str_contextfn");
}
}
/************************************************************************
*(h1 "Building and Freeing a Stream of Solutions -- The Simplified Common Case")
*
*/
#if 0
/*(c rx_basic_make_solutions)
* struct rx_solutions *
* rx_basic_make_solutions (struct rx_registers * regs,
* struct rx_exp_node * expression,
* struct rx_exp_node ** subexps,
* int nsub,
* rx_off_t start,
* rx_off_t end,
* struct rx_context_rules * rules,
* const t_uchar * str,
* int small_p);
*
* Construct a stream of solutions for matching the regexp
* `expression' against the substring of `str' beginning at `start'
* and ending at `end'.
*
* Part of the output of stream, the positions of sub-expressions in a
* solution, will be stored in `regs' each time the next solution is
* read using `rx_next_solution'.
*
* The parameter `context_rules' contains flags which effect the
* meaning of some regexp operators.
*
insert*/
struct rx_context_rules
{
t_uchar newline_anchor;
/* If set, an anchor at a newline matches.*/
t_uchar not_bol;
t_uchar not_eol;
/* If set, the anchors do not match the beginning and end
of the complete input string.*/
t_uchar case_indep;
/* If set, all string comparisons should be case independent.*/
};
/*end-insert
*
* You must apply `rx_analyze_rexp' to the regexp `expression' before
* calling his function. `rx_analyze_rexp' computes recursively
* defined properties of the subexpressions of the expression and
* records those properties in the expression tree. During a match,
* `rx_next_solution' examines those properties to decide how each
* subexpression should be treated.
*
* `rx_analyze_rexp' will return to you an array of the parenthesized
* subexpressions of `expression' and tell you the total number of
* subexpressions. You must pass this information along to
* `rx_basic_make_solutions' as the `subexps' and `nsub' parameters.
*
* `rx_analyze_rexp' will also fill in the `small_advised_p' field of
* `expression'. You can pass this along to `rx_basic_make_solutions'
* as the parameter `small_p'. If not 0, `small_p' advises
* `rx_basic_make_solutions' that the regexp is small and simple and
* therefore not worthy of several high-latency optimizations that
* `rx_next_solution' is capable of. Setting this parameter correctly
* can improve performance, setting it incorrectly can ruin
* performance, and `rx_analyze_rexp' can only approximately compute
* whether or not to set this parameter (it makes a safe guess). The
* safest value to pass is 0, which activates the high-latency
* optimizations, sometimes (slightly) slowing down matches that
* aren't particularly expensive while (substantially) speeding up
* some matches that are particularly expensive.
*
* `rx_basic_make_solutions' requires that the entire input string be
* in contiguous memory at one time. Another function,
* `rx_make_solutions', can be used if the string is not contiguous in
* memory or is not all in memory at one time.
*/
#endif
struct rx_solutions *
rx_basic_make_solutions (struct rx_registers * regs,
struct rx_exp_node * expression,
struct rx_exp_node ** subexps,
int nsub,
rx_off_t start,
rx_off_t end,
struct rx_context_rules * rules,
const t_uchar * str,
int small_p)
{
struct rx_solutions * solns;
struct rx_str_closure * closure;
if ( expression
&& (expression->len >= 0)
&& (expression->len != (end - start)))
return &no_solutions;
closure = (struct rx_str_closure *)rx_nfa_cache_malloc (sizeof (*closure));
if (!closure)
return 0;
closure->str = str;
closure->len = end;
closure->rules = *rules;
solns = rx_make_solutions (regs,
256, expression, subexps, nsub,
start, end, 0,
rx_str_vmfn, rx_str_contextfn, (void *)closure, small_p, 0, 0);
if (!solns)
{
rx_nfa_cache_free ((void *)closure);
return 0;
}
return solns;
}
/*(c rx_basic_free_solutions)
* void rx_basic_free_solutions (struct rx_solutions * solns);
*
* Release all storage held by a stream of regexp solutions allocated
* by `rx_basic_make_solutions'.
*/
void
rx_basic_free_solutions (struct rx_solutions * solns)
{
if (solns == 0)
return;
if (solns == &no_solutions)
return;
rx_nfa_cache_free (rx_solutions_closure (solns));
rx_free_solutions (solns);
}
/************************************************************************
* Low Level Support for rx_next_solution
*
*
*
*/
/* static int rx_solution_fit_cset_p (struct rx_solutions * solns);
*
* The expression is a character set node and the current substring is
* one character long. Compare the two and return 1 if they match, 0
* otherwise.
*/
static int
rx_solution_fit_cset_p (struct rx_solutions * solns)
{
int current_pos;
const t_uchar * burst;
rx_off_t burst_addr;
rx_off_t burst_len;
rx_off_t rel_pos_in_burst;
int vmstat;
const t_uchar * pos;
current_pos = solns->start;
vmstat = solns->vmfn (solns->closure,
&burst, &burst_len, &burst_addr,
current_pos, current_pos + 1, current_pos);
if (vmstat)
return vmstat;
rel_pos_in_burst = current_pos - burst_addr;
pos = burst + rel_pos_in_burst;
return !!bits_is_member (solns->exp->cset, *pos);
}
/* static int rx_solution_fit_str_p (struct rx_solutions * solns);
*
* The expression is a string node and the current substring is the
* same length. Compare the two and return 1 if they match, 0
* otherwise.
*/
static int
rx_solution_fit_str_p (struct rx_solutions * solns)
{
rx_off_t current_pos;
const t_uchar * burst;
rx_off_t burst_addr;
rx_off_t burst_len;
rx_off_t burst_end_addr;
rx_off_t rel_pos_in_burst;
int vmstat;
rx_off_t count;
t_uchar * key;
current_pos = solns->start;
count = solns->exp->str_len;
key = (t_uchar *)solns->exp->str;
next_burst:
vmstat = solns->vmfn (solns->closure,
&burst, &burst_len, &burst_addr,
current_pos, solns->end,
current_pos);
if (vmstat)
return vmstat;
rel_pos_in_burst = current_pos - burst_addr;
burst_end_addr = burst_addr + burst_len;
{
const t_uchar * pos;
pos = burst + rel_pos_in_burst;
if (burst_end_addr >= solns->end)
{
while (count)
{
if (rx_poll)
(*rx_poll)();
if (*pos != *key)
return 0;
++pos;
++key;
--count;
}
return 1;
}
else
{
rx_off_t part_count;
rx_off_t part_count_init;
part_count_init = burst_len - rel_pos_in_burst;
part_count = part_count_init;
while (part_count)
{
if (rx_poll)
(*rx_poll)();
if (*pos != *key)
return 0;
++pos;
++key;
--part_count;
}
count -= part_count_init;
current_pos += burst_len - rel_pos_in_burst;
goto next_burst;
}
}
}
/* static int rx_solution_fits (struct rx_solutions * solns);
*
* Compare a DFA which describes a superset of the regexp expression
* to the current substring and return 1 if they match, 0 otherwise.
* That the DFA matches is a necessary but not sufficient condition of
* the regexp expression itself matching. This test can be used to
* avoid a more expensive regexp comparison. Return -1 for ESPACE.
*/
static int
rx_solution_fits (struct rx_solutions * solns)
{
const t_uchar * burst;
rx_off_t burst_addr;
rx_off_t burst_len;
rx_off_t burst_end_addr;
rx_off_t rel_pos_in_burst;
int vmstat;
rx_off_t current_pos;
if (solns->certainly_fits)
{
solns->match_engine.final_tag = solns->certain_final_tag;
return 1;
}
current_pos = solns->start;
next_burst:
vmstat = solns->vmfn (solns->closure,
&burst, &burst_len, &burst_addr,
current_pos, solns->end,
current_pos);
if (vmstat)
return vmstat;
rel_pos_in_burst = current_pos - burst_addr;
burst_end_addr = burst_addr + burst_len;
if (burst_end_addr >= solns->end)
{
int fit_label;
if (rx_dfa_fits (&fit_label,
&solns->match_engine,
burst + rel_pos_in_burst,
solns->end - current_pos))
return -1; /* espace */
return fit_label;
}
else
{
int fit_status;
fit_status = rx_dfa_advance (&solns->match_engine,
burst + rel_pos_in_burst,
burst_len - rel_pos_in_burst);
if (fit_status < 0)
{
return -1;
}
else if (fit_status)
{
current_pos += burst_len - rel_pos_in_burst;
goto next_burst;
}
else
return 0;
}
}
static int
rx_dfa_longest_counting (int * label,
size_t * match_len,
size_t * matches_count,
struct rx_dfa * dfa,
const t_uchar * str,
size_t len)
{
size_t pos;
size_t n_matches;
size_t best_len;
int best_label;
pos = 0;
n_matches = 0;
best_len = 0;
best_label = rx_dfa_tag (dfa);
if (best_label)
{
n_matches = 1;
}
while (pos < len)
{
int adv_stat;
size_t adv_amt;
adv_stat = rx_dfa_advance_to_final (&adv_amt, dfa, str + pos, len - pos);
if (adv_stat < 0)
return -1;
if (!adv_stat)
break;
pos += adv_amt;
if (rx_dfa_tag (dfa))
{
best_len = pos;
++n_matches;
best_label = rx_dfa_tag (dfa);
}
}
*label = best_label;
*match_len = best_len;
*matches_count = n_matches;
return 0;
}
/* adjust split_guess downward to the nearest plausible
* position. Return 0 if none exists, 1 otherwise.
*/
static int
rx_longest_split_guess (int volatile * label, struct rx_solutions * solns)
{
const t_uchar * burst;
rx_off_t burst_addr;
rx_off_t burst_len;
rx_off_t burst_end_addr;
rx_off_t rel_pos_in_burst;
int vmstat;
rx_off_t current_pos;
size_t n_matches;
rx_off_t best_guess;
int best_label;
if (solns->no_fancy_guessing)
{
*label = 0;
return 1;
}
current_pos = solns->start;
n_matches = 0;
best_guess = -1;
best_label = 0;
if (rx_dfa_goto_start_superstate (&solns->left_match_engine, 1))
return -1;
while (1)
{
int fit_label;
size_t matches_here;
size_t len_here;
vmstat = solns->vmfn (solns->closure,
&burst, &burst_len, &burst_addr,
current_pos, solns->split_guess,
current_pos);
if (vmstat)
{
rx_clear_dfa_state (&solns->left_match_engine);
return vmstat;
}
rel_pos_in_burst = current_pos - burst_addr;
burst_end_addr = burst_addr + burst_len;
if (rx_dfa_longest_counting (&fit_label,
&len_here,
&matches_here,
&solns->left_match_engine,
burst + rel_pos_in_burst,
((burst_end_addr >= solns->split_guess)
? solns->split_guess - current_pos
: burst_end_addr - current_pos)))
{
rx_clear_dfa_state (&solns->left_match_engine);
return -1;
}
if (fit_label)
{
n_matches += matches_here;
best_guess = len_here + rel_pos_in_burst;
best_label = fit_label;
}
if (!fit_label || (burst_end_addr >= solns->split_guess))
{
if (!n_matches)
{
rx_clear_dfa_state (&solns->left_match_engine);
return 0;
}
solns->split_guess = best_guess;
*label = best_label;
if (n_matches > (best_guess * 2))
solns->no_fancy_guessing = 1;
rx_clear_dfa_state (&solns->left_match_engine);
return 1;
}
current_pos += burst_len - rel_pos_in_burst;
}
}
/************************************************************************
*(h1 "Reading Elements From a Stream of Solutions")
*
*/
/* Save the values of registers for reporting parentheses
* enclosed in the expression solns->exp. Initialize
* those registers to -1.
*
* These are stored in the `solns' structure. Only one set of register
* values can be saved, per `solns', at a time.
*/
static int
save_nested_registers (struct rx_solutions * solns)
{
int first_subexp;
int last_subexp;
int n_subexps;
int x;
/* Save the value of the set of numbered
* parentheses in the tree rooted at this
* expression and initialized them to -1. If
* this expression does not match, they will
* be restored. If it does match, they get values
* from that match and not from previous matches.
*/
first_subexp = solns->exp->min_enclosed_paren;
last_subexp = solns->exp->max_enclosed_paren;
n_subexps = 1 + (last_subexp - first_subexp);
if (!solns->saved_rm_so)
{
solns->saved_rm_so = (rx_off_t *)rx_nfa_cache_malloc (sizeof (rx_off_t) * n_subexps);
solns->saved_rm_eo = (rx_off_t *)rx_nfa_cache_malloc (sizeof (rx_off_t) * n_subexps);
if (!solns->saved_rm_so || !solns->saved_rm_eo)
{
rx_nfa_cache_free ((void *)solns->saved_rm_so);
rx_nfa_cache_free ((void *)solns->saved_rm_eo);
return -1;
}
}
for (x = 0; x < n_subexps; ++x)
{
solns->saved_rm_so[x] = solns->regs[x + first_subexp].rm_so;
solns->saved_rm_eo[x] = solns->regs[x + first_subexp].rm_eo;
solns->regs[x + first_subexp].rm_so = -1;
solns->regs[x + first_subexp].rm_eo = -1;
}
return 0;
}
/* Restore register values saved by `save_nested_registers'.
*
* This doesn't erase the stored values.
*/
static void
restore_nested_registers (struct rx_solutions * solns)
{
int first_subexp;
int last_subexp;
int n_subexps;
int x;
first_subexp = solns->exp->min_enclosed_paren;
last_subexp = solns->exp->max_enclosed_paren;
n_subexps = 1 + (last_subexp - first_subexp);
for (x = 0; x < n_subexps; ++x)
{
solns->regs[x + first_subexp].rm_so = solns->saved_rm_so[x];
solns->regs[x + first_subexp].rm_eo = solns->saved_rm_eo[x];
}
}
/*(c rx_next_solution)
* int rx_next_solution (struct rx_solutions * solns);
*
* If there are no more solutions in the stream of regexp solutions
* `solns', return 0. Otherwise, advance the stream to the next
* solution and return 1. Return -1 for ESPACE.
*
* Advancing the stream means filling in the `regs' structure that was
* passed to `rx_basic_make_solutions' or `rx_make_solutions' and
* establishing the value that will be returned by subsequent calls to
* `rx_solutions_final_tag'.
*
* Solutions are returned in order from best to worst according to the
* leftmost-longest rule (see xref:"Describing Regexps Formally").
*
* It is possible to asynchronously abort a call to this function.
* See xref:"Exiting Long-Running Matches".
*/
int
rx_next_solution (struct rx_solutions * solns)
{
jmp_buf err_escape;
if (setjmp (err_escape))
{
return -1;
}
return rx_next_solution_internal (solns, &err_escape, 0);
}
static int
rx_next_solution_internal (struct rx_solutions * solns, jmp_buf * err_escape, int depth)
{
#ifdef TRACE
if (rx_trace && (!rx_depth_limit || (depth < rx_depth_limit)))
{
safe_printfmt (2, "%*s================\n", depth, "");
safe_printfmt (2, "%*sstep: %d\n", depth, "", solns->step);
safe_printfmt (2, "%*s----------------\n", depth, "");
safe_printfmt (2, "%*sexpression:\n", depth, "");
safe_printfmt (2, "%*s", depth, "");
rx_unparse_print_rexp (2, 256, solns->exp);
safe_printfmt (2, "\n");
safe_printfmt (2, "%*s----------------\n", depth, "");
safe_printfmt (2, "%*sstring:\n", depth, "");
{
const t_uchar * burst;
rx_off_t burst_addr;
rx_off_t burst_len;
rx_off_t rel_pos_in_burst;
int vmstat;
vmstat = solns->vmfn (solns->closure,
&burst, &burst_len, &burst_addr,
solns->start, solns->end, solns->start);
if (vmstat)
panic ("vmstat failure in trace");
rel_pos_in_burst = solns->start - burst_addr;
safe_printfmt (2, "%*s%.*s\n", depth, "",
((solns->end - solns->start) <= (burst_len - rel_pos_in_burst)
? (solns->end - solns->start)
: (burst_len - rel_pos_in_burst)),
burst + rel_pos_in_burst);
}
safe_printfmt (2, "%*s----------------\n", depth, "");
}
#endif
#define KNOWN_LENGTH(EXP) (!(EXP) \
? 0 \
: ((EXP)->len >= 0 \
? (EXP)->len \
: ((((EXP)->type == r_context) && ((EXP)->intval >= '0') && ((EXP)->intval <= '9')) \
? ((solns->regs[(EXP)->intval - '0'].rm_so >= 0) \
? (solns->regs[(EXP)->intval - '0'].rm_eo - solns->regs[(EXP)->intval - '0'].rm_so) \
: -1) \
: -1)))
if (solns == &no_solutions)
{
return 0;
}
if (!solns->exp)
{
if (solns->step != 0)
{
return 0;
}
else
{
solns->step = 1;
solns->final_tag = 1;
return (solns->start == solns->end
? 1
: 0);
}
}
else if (!(solns->small_p || solns->exp->observed))
{
if (solns->step != 0)
{
return 0;
}
else if (solns->exp->type == r_string)
{
int ans;
ans = rx_solution_fit_str_p (solns);
solns->final_tag = 1;
solns->step = -1;
return ans;
}
else
{
int ans;
ans = rx_solution_fits (solns);
if (ans < 0)
longjmp (*err_escape, 1);
solns->final_tag = solns->match_engine.final_tag;
solns->step = -1;
return !!ans;
}
}
else /* if (solns->small_p || solns->exp->observed) */
{
int fits;
switch (solns->step)
{
case -2:
if (solns->exp->min_enclosed_paren)
{
int first_subexp;
int last_subexp;
int x;
first_subexp = solns->exp->min_enclosed_paren;
last_subexp = solns->exp->max_enclosed_paren;
for (x = first_subexp; x <= last_subexp; ++x)
{
solns->regs[x].rm_so = solns->saved_rm_so[x - first_subexp];
solns->regs[x].rm_eo = solns->saved_rm_eo[x - first_subexp];
}
}
return 0;
case -1:
return 0;
case 0:
if (solns->small_p)
{
solns->step = 1;
goto resolve_fit;
}
else
{
fits = rx_solution_fits (solns);
if (fits < 0)
longjmp (*err_escape, 1);
/* Set final_tag here because this rough fit test
* may be all the matching that gets done.
* For example, consider a paren node containing
* a true regular expression ending with a cut
* operator.
*/
solns->final_tag = solns->match_engine.final_tag;
if (fits == 0)
{
solns->step = -1;
return fits;
}
else
{
solns->step = 1;
goto resolve_fit;
}
}
default:
resolve_fit:
switch (solns->exp->type)
{
case r_string:
if (!solns->small_p)
{
while (1)
panic ("bogus regexp in rx_next_solution_internal");
}
else
{
int answer;
answer = rx_solution_fit_str_p (solns);
solns->final_tag = 1;
solns->step = -1;
return answer;
}
case r_cset:
if (!solns->small_p)
{
while (1)
panic ("bogus regexp in rx_next_solution_internal");
}
else
{
int answer;
answer = rx_solution_fit_cset_p (solns);
solns->final_tag = 1;
solns->step = -1;
return answer;
}
case r_cut:
if (!solns->small_p)
{
while (1)
panic ("bogus regexp in rx_next_solution_internal");
}
else
{
solns->final_tag = solns->exp->intval;
solns->step = -1;
return !!solns->exp->intval;
}
case r_parens:
{
int paren_stat;
switch (solns->step)
{
case 1:
if (solns->exp->min_enclosed_paren)
{
if (save_nested_registers (solns))
longjmp (*err_escape, 1);
}
if ( !solns->small_p
&& ( !solns->exp->left
|| !solns->exp->left->observed))
{
/* We already proved that this (simple)
* subexpression matches. Optionally, record
* its position. Return success once, and
* failure for all subsequent attempts to find
* other matches.
*/
if (solns->exp->intval)
{
solns->regs[solns->exp->intval].rm_so = solns->start;
solns->regs[solns->exp->intval].rm_eo = solns->end;
}
solns->step = -2;
/* Keep the final_tag from the fits test. */
return 1;
}
/* We must search through possible matches of the subexpression.
*/
solns->left = rx_make_solutions (solns->regs,
solns->cset_size,
solns->exp->left,
solns->subexps,
solns->nsub,
solns->start,
solns->end,
0,
solns->vmfn,
solns->contextfn,
solns->closure,
solns->small_p,
0,
0);
if (!solns->left)
longjmp (*err_escape, 1);
case 2:
if (solns->exp->min_enclosed_paren)
{
int first_subexp;
int last_subexp;
int x;
/* Initialize the parentheses in the tree
* rooted at this expression to -1.
*/
first_subexp = solns->exp->min_enclosed_paren;
last_subexp = solns->exp->max_enclosed_paren;
for (x = first_subexp; x <= last_subexp; ++x)
{
solns->regs[x].rm_so = -1;
solns->regs[x].rm_eo = -1;
}
}
paren_stat = rx_next_solution_internal (solns->left, err_escape, depth + 1);
if (paren_stat < 0)
longjmp (*err_escape, 1);
if (paren_stat == 1)
{
if (solns->exp->intval)
{
solns->regs[solns->exp->intval].rm_so = solns->start;
solns->regs[solns->exp->intval].rm_eo = solns->end;
}
solns->final_tag = solns->left->final_tag;
solns->step = 2;
return 1;
}
else
{
rx_free_solutions (solns->left);
solns->left = 0;
if (solns->exp->min_enclosed_paren)
{
/* This expression didn't match. Restore the old subexpression
* positions.
*/
restore_nested_registers (solns);
}
solns->step = -1;
return paren_stat;
}
}
}
case r_alternate:
{
int alt_stat;
switch (solns->step)
{
case 1:
solns->left = rx_make_solutions (solns->regs,
solns->cset_size,
solns->exp->left,
solns->subexps,
solns->nsub,
solns->start,
solns->end,
0,
solns->vmfn,
solns->contextfn,
solns->closure,
solns->small_p,
0,
0);
if (!solns->left)
longjmp (*err_escape, 1);
case 2:
alt_stat = rx_next_solution_internal (solns->left, err_escape, depth + 1);
if (alt_stat < 0)
longjmp (*err_escape, 1);
if (alt_stat == 1)
{
solns->final_tag = solns->left->final_tag;
solns->step = 2;
return alt_stat;
}
else
{
rx_free_solutions (solns->left);
solns->left = 0;
}
solns->right = rx_make_solutions (solns->regs,
solns->cset_size,
solns->exp->right,
solns->subexps,
solns->nsub,
solns->start,
solns->end,
0,
solns->vmfn,
solns->contextfn,
solns->closure,
solns->small_p,
0,
0);
if (!solns->right)
longjmp (*err_escape, 1);
case 4:
alt_stat = rx_next_solution_internal (solns->right, err_escape, depth + 1);
if (alt_stat < 0)
longjmp (*err_escape, 1);
if (alt_stat == 1)
{
solns->final_tag = solns->right->final_tag;
solns->step = 4;
return alt_stat;
}
else
{
solns->step = -1;
rx_free_solutions (solns->right);
solns->right = 0;
return alt_stat;
}
}
}
case r_concat:
{
volatile int certain_label = 0;
switch (solns->step)
{
int concat_stat;
int split_guess_stat;
case 1:
if (!solns->exp->left)
solns->split_guess = solns->start;
else
{
rx_off_t known_left_length;
known_left_length = KNOWN_LENGTH (solns->exp->left);
if (known_left_length >= 0)
{
if (known_left_length > (solns->end - solns->start))
{
solns->step = -1;
return 0;
}
solns->split_guess = solns->start + known_left_length;
}
else
{
rx_off_t known_right_length;
known_right_length = KNOWN_LENGTH (solns->exp->right);
if (known_right_length >= 0)
{
if (known_right_length > (solns->end - solns->start))
{
solns->step = -1;
return 0;
}
solns->split_guess = solns->end - known_right_length;
}
else
solns->split_guess = solns->end;
}
}
concat_split_guess_loop:
split_guess_stat = rx_longest_split_guess (&certain_label, solns);
if (split_guess_stat < 0)
longjmp (*err_escape, 1);
if (!split_guess_stat)
{
solns->step = -1;
return 0;
}
solns->left = rx_make_solutions (solns->regs,
solns->cset_size,
solns->exp->left,
solns->subexps,
solns->nsub,
solns->start,
solns->split_guess,
0,
solns->vmfn,
solns->contextfn,
solns->closure,
solns->small_p,
!!certain_label,
certain_label);
if (!solns->left)
longjmp (*err_escape, 1);
concat_try_next_left_match:
concat_stat = rx_next_solution_internal (solns->left, err_escape, depth + 1);
if (concat_stat < 0)
longjmp (*err_escape, 1);
if (concat_stat != 1)
{
rx_free_solutions (solns->left);
solns->left = 0;
if ( (KNOWN_LENGTH (solns->exp->left) < 0)
&& (KNOWN_LENGTH (solns->exp->right) < 0))
{
--solns->split_guess;
if (solns->split_guess >= solns->start)
goto concat_split_guess_loop;
}
solns->step = -1;
return 0;
}
solns->right = rx_make_solutions (solns->regs,
solns->cset_size,
solns->exp->right,
solns->subexps,
solns->nsub,
solns->split_guess,
solns->end,
0,
solns->vmfn,
solns->contextfn,
solns->closure,
solns->small_p,
0,
0);
if (!solns->right)
longjmp (*err_escape, 1);
case 2:
concat_stat = rx_next_solution_internal (solns->right, err_escape, depth + 1);
if (concat_stat < 0)
longjmp (*err_escape, 1);
if (concat_stat == 1)
{
solns->final_tag = solns->right->final_tag;
solns->step = 2;
return concat_stat;
}
else
{
rx_free_solutions (solns->right);
solns->right = 0;
goto concat_try_next_left_match;
}
}
}
case r_right_concat:
{
switch (solns->step)
{
int concat_stat;
rx_off_t known_left_length;
rx_off_t known_right_length;
case 1:
known_left_length = KNOWN_LENGTH (solns->exp->left);
known_right_length = KNOWN_LENGTH (solns->exp->right);
if (known_left_length >= 0)
{
solns->split_guess = solns->start + known_left_length;
}
else if (known_right_length >= 0)
{
solns->split_guess = solns->end - known_right_length;
}
else
solns->split_guess = solns->start;
right_concat_split_guess_loop:
solns->left = rx_make_solutions (solns->regs,
solns->cset_size,
solns->exp->left,
solns->subexps,
solns->nsub,
solns->start,
solns->split_guess,
0,
solns->vmfn,
solns->contextfn,
solns->closure,
solns->small_p,
0,
0);
if (!solns->left)
longjmp (*err_escape, 1);
right_concat_try_next_left_match:
concat_stat = rx_next_solution_internal (solns->left, err_escape, depth + 1);
if (concat_stat < 0)
longjmp (*err_escape, 1);
if (concat_stat != 1)
{
rx_free_solutions (solns->left);
solns->left = 0;
if ( (KNOWN_LENGTH (solns->exp->left) < 0)
&& (KNOWN_LENGTH (solns->exp->right) < 0))
{
++solns->split_guess;
if (solns->split_guess <= solns->end)
goto right_concat_split_guess_loop;
}
solns->step = -1;
return 0;
}
solns->right = rx_make_solutions (solns->regs,
solns->cset_size,
solns->exp->right,
solns->subexps,
solns->nsub,
solns->split_guess,
solns->end,
0,
solns->vmfn,
solns->contextfn,
solns->closure,
solns->small_p,
0,
0);
if (!solns->right)
longjmp (*err_escape, 1);
case 2:
concat_stat = rx_next_solution_internal (solns->right, err_escape, depth + 1);
if (concat_stat < 0)
longjmp (*err_escape, 1);
if (concat_stat == 1)
{
solns->final_tag = solns->right->final_tag;
solns->step = 2;
return concat_stat;
}
else
{
rx_free_solutions (solns->right);
solns->right = 0;
goto right_concat_try_next_left_match;
}
}
}
case r_star:
{
int star_stat;
switch (solns->step)
{
case 1:
/* Begin by trying to match the entire string
* with a single iteration.
*/
solns->left = rx_make_solutions (solns->regs,
solns->cset_size,
solns->exp->left,
solns->subexps,
solns->nsub,
solns->start,
solns->end,
0,
solns->vmfn,
solns->contextfn,
solns->closure,
solns->small_p,
0,
0);
if (!solns->left)
longjmp (*err_escape, 1);
case 2:
star_stat = rx_next_solution_internal (solns->left, err_escape, depth + 1);
if (star_stat < 0)
longjmp (*err_escape, 1);
if (star_stat == 1)
{
/* found a single-iteration whole-string match */
solns->final_tag = solns->left->final_tag;
solns->step = 2;
return 1;
}
/* no more single-iteration whole-string matches */
rx_free_solutions (solns->left);
solns->left = 0;
if (solns->start == solns->end)
{
/* when comaring to the empty string and none of the single-iteration
* matches work, try matching with zero iterations, then give up
*/
solns->step = -1;
return 1;
}
/* when comparing to a non-empty string and none of the single-iteration
* matches work, try all matches with two or more non-empty iterations.
*/
if (!solns->exp->left || (solns->exp->left->len == 0))
{
solns->step = -1;
return 0;
}
else if (solns->exp->left->len > 0)
{
if ( (solns->exp->left->len >= (solns->end - solns->start))
|| (0 != ((solns->end - solns->start) % solns->exp->left->len)))
{
solns->step = -1;
return 0;
}
solns->split_guess = solns->end - solns->exp->left->len;
}
else
solns->split_guess = solns->start + 1;
case 3:
star_3:
/* Suppose the string has been split into two parts: s == s1 s2
* and we are trying to match R*.
*
* Recurse by matching s1 against R*, and s2 against R.
*
* However, if s == s1 and s2 is the empty string, comparing
* s1 to R* would cause an infinite recursion. So instead,
* compare s1 to R and s2 to R.
*
* Comparing s2 to R is often much less expensive than comparing
* s1 to R*. If s2 doesn't match R, time spent comparing s1 to R*
* is wasted. So, before trying s1 against R*, make sure that
* s2 can match R.
*
* Registers are subtle. There are three possibilities:
*
* [A] R contains no reporting parens
* [B] R contains reporting parens
*
* In case A, matching s1 against R* won't change any registers,
* so it is safe to match s to R first.
*
* In the second case, either
*
* [B1] R is a reporting parenthesized expression
* [B2] R is a non-reporting parenthesized expression
*
* In either of those two cases, the first step of
* comparing s2 to R is to set all of the
* registers for nested reporting parentheses to
* -1. As a result, again, s1 against R* has no (observable) effect
* on registers -- so it is safe to match s to R first.
*
*/
solns->right = rx_make_solutions (solns->regs,
solns->cset_size,
solns->exp->left,
solns->subexps,
solns->nsub,
solns->split_guess,
solns->end,
0,
solns->vmfn,
solns->contextfn,
solns->closure,
solns->small_p,
0,
0);
if (!solns->right)
longjmp (*err_escape, 1);
star_stat = rx_next_solution_internal (solns->right, err_escape, depth + 1);
if (star_stat < 0)
longjmp (*err_escape, 1);
if (star_stat != 1)
{
/* No match for s2 against R, so guess again:
*/
rx_free_solutions (solns->right);
solns->right = 0;
if (solns->exp->left->len > 0)
{
solns->step = -1;
return 0;
}
++solns->split_guess;
if (solns->split_guess > solns->end)
{
solns->step = -1;
return 0;
}
goto star_3;
}
/* Aha -- s2 matches R. Does s1 match R*?
*
* Testing s1 against R* can modify some registers
* that were set while matching s2 to R. These
* registers must be saved and then restored before
* returning the overall match.
*/
if (save_nested_registers (solns))
{
longjmp (*err_escape, 1);
}
if (solns->split_guess == solns->end)
solns->left = rx_make_solutions (solns->regs,
solns->cset_size,
solns->exp->left,
solns->subexps,
solns->nsub,
solns->start,
solns->split_guess,
0,
solns->vmfn,
solns->contextfn,
solns->closure,
solns->small_p,
0,
0);
else
solns->left = rx_make_solutions (solns->regs,
solns->cset_size,
solns->exp,
solns->subexps,
solns->nsub,
solns->start,
solns->split_guess,
0,
solns->vmfn,
solns->contextfn,
solns->closure,
solns->small_p,
0,
0);
if (!solns->left)
longjmp (*err_escape, 1);
star_stat = rx_next_solution_internal (solns->left, err_escape, depth + 1);
if (star_stat < 0)
longjmp (*err_escape, 1);
if (star_stat != 1)
{
/* no matches for the left part of the split string
* at this split_guess.
*/
rx_free_solutions (solns->left);
rx_free_solutions (solns->right);
solns->left = 0;
solns->right = 0;
if (solns->exp->left->len > 0)
{
solns->step = -1;
return 0;
}
++solns->split_guess;
if (solns->split_guess > solns->end)
{
solns->step = -1;
return 0;
}
goto star_3;
}
/* Found at least one solution for both s1 against R* and
* s2 against R.
*
* Return that solution. First, restore the registers from
* the s2/R match:
*
*/
restore_nested_registers (solns);
solns->final_tag = solns->right->final_tag;
solns->step = 4;
return 1;
case 4:
/* This is reached when we've found one solution for
* s1 against R* and s2 against R, but that solution
* was rejected.
*
* Try to find another solution for s2/R, using the same
* match for s1/R*.
*/
star_stat = rx_next_solution_internal (solns->right, err_escape, depth + 1);
if (star_stat < 0)
longjmp (*err_escape, 1);
if (star_stat == 1)
{
/* found a match */
solns->final_tag = solns->right->final_tag;
solns->step = 4;
}
/* No more matches for s2/R for the current match of s1/R*
*
* We could look for another s1/R* match -- but why bother?
* Any changes to registers made by such a match are
* not observable after any s/R match. So, try again with
* a different split guess:
*/
rx_free_solutions (solns->left);
rx_free_solutions (solns->right);
solns->left = 0;
solns->right = 0;
if (solns->exp->left->len > 0)
{
solns->step = -1;
return 0;
}
++solns->split_guess;
if (solns->split_guess > solns->end)
{
solns->step = -1;
return 0;
}
goto star_3;
}
}
case r_interval:
{
/* On entry, interval_x is the number of iterations
* already charged to this interval. So, instead
* of {intval, intval2}, the interval is actually:
*
* { max(0, intval - interval_x),
* max(0, intval2 - interval_x) }
*
*/
switch (solns->step)
{
int interval_stat;
case 1:
solns->interval_from = max0(solns->exp->intval - solns->interval_x);
solns->interval_to = max0(solns->exp->intval2 - solns->interval_x);
/* Should we try single iteration solutions?
*
* Yes if either:
*
* (interval_from <= 1) && (interval_to >= 1)
*
* or
* ((solns->start == solns->end) && (interval_to >= 1))
*
* If the string is the empty string (start == end), and any
* iterations are permitted (interval_to >= 1) then all possible
* solutions (except the 0-iteration solution) can be found with
* a single iteration. Repeated iterations for a null match do not
* add new solutions compared to a single iteration because the
* single iteration will always have the same side effects as multiple
* iterations ending with that single iteration.
*/
if ( ( (solns->start == solns->end)
&& (solns->interval_to >= 1)
&& ( !solns->exp->left
|| (solns->exp->left->len <= 0)))
|| ( (solns->interval_from <= 1)
&& (solns->interval_to >= 1)
&& (solns->start != solns->end)
&& solns->exp->left
&& ( (solns->exp->left->len < 0)
|| (solns->exp->left->len == (solns->end - solns->start)))))
{
solns->left = rx_make_solutions (solns->regs,
solns->cset_size,
solns->exp->left,
solns->subexps,
solns->nsub,
solns->start,
solns->end,
0,
solns->vmfn,
solns->contextfn,
solns->closure,
solns->small_p,
0,
0);
if (!solns->left)
longjmp (*err_escape, 1);
case 2:
interval_stat = rx_next_solution_internal (solns->left, err_escape, depth + 1);
if (interval_stat < 0)
longjmp (*err_escape, 1);
if (interval_stat != 1)
{
rx_free_solutions (solns->left);
solns->left = 0;
goto try_0_iteration_null_match;
}
else
{
solns->step = 2;
return 1;
}
}
try_0_iteration_null_match:
/* If we're trying to match the empty string, and 0 iterations are
* permitted, that is the next best solution. If we're trying to
* match the empty string, the 0 iteration solution is the only
* remaining possibility.
*/
if (solns->start == solns->end)
{
solns->step = -1;
return (solns->interval_from == 0);
}
/* The string is not empty. If only 0 iterations are permitted,
* then no solutions are possible.
*/
if (solns->interval_to == 0)
{
solns->step = -1;
return 0;
}
/* The string is not empty and no single iteration solution works.
* Search through solutions with at least two iterations. We split
* the string into two parts, and try to match the left part with N
* iterations (N >= 1) and the right part with 1 iteration.
*
* To satisfy the left-to-right longest-subexpression rule, the right
* part (matched by the last iteration) should be as long as possible.
*/
if (!solns->exp->left || (solns->exp->left->len == 0))
{
/* never reached unless certain other optimizations are removed
*/
solns->step = -1;
return 0;
}
else if (solns->exp->left->len > 0)
{
if ( (solns->exp->left->len > (solns->end - solns->start))
|| (0 != ((solns->end - solns->start) % solns->exp->left->len)))
{
solns->step = -1;
return 0;
}
solns->split_guess = solns->end - solns->exp->left->len;
}
else
solns->split_guess = solns->start;
interval_split_start_at_new_split_guess:
solns->right = rx_make_solutions (solns->regs,
solns->cset_size,
solns->exp->left,
solns->subexps,
solns->nsub,
solns->split_guess,
solns->end,
0,
solns->vmfn,
solns->contextfn,
solns->closure,
solns->small_p,
0,
0);
if (!solns->right)
longjmp (*err_escape, 1);
next_interval_right_solution:
interval_stat = rx_next_solution_internal (solns->right, err_escape, depth + 1);
if (interval_stat < 0)
longjmp (*err_escape, 1);
if (interval_stat != 1)
{
rx_free_solutions (solns->right);
solns->right = 0;
if (solns->exp->left->len < 0)
{
++solns->split_guess;
if (solns->split_guess <= solns->end)
goto interval_split_start_at_new_split_guess;
}
/* No more solutions at all. */
solns->step = -1;
return 0;
}
/* Found a solution for the right half of the split.
*/
if (save_nested_registers (solns))
{
longjmp (*err_escape, 1);
}
solns->left = rx_make_solutions (solns->regs,
solns->cset_size,
solns->exp,
solns->subexps,
solns->nsub,
solns->start,
solns->split_guess,
solns->interval_x + 1,
solns->vmfn,
solns->contextfn,
solns->closure,
solns->small_p,
0,
0);
if (!solns->left)
longjmp (*err_escape, 1);
interval_stat = rx_next_solution_internal (solns->left, err_escape, depth + 1);
if (interval_stat < 0)
longjmp (*err_escape, 1);
if (interval_stat != 1)
{
/* No more solutions for the left part of the string.
*/
rx_free_solutions (solns->left);
solns->left = 0;
goto next_interval_right_solution;
}
/* We found an overall solution for the interval.
*/
solns->step = 3;
restore_nested_registers (solns);
solns->final_tag = solns->right->final_tag;
return 1;
case 3:
rx_free_solutions (solns->left);
solns->left = 0;
goto next_interval_right_solution;
}
}
case r_context:
{
solns->step = -1;
solns->final_tag = 1;
return solns->contextfn (solns->closure,
solns->exp,
solns->start, solns->end,
solns->regs);
}
}
}
while (1)
panic ("unreached in rx_next_solution_internal");
}
}
/*(c rx_solutions_final_tag)
* int rx_solutions_final_tag (struct rx_solutions * solns);
*
* Return the state label of the last DFA state reached during
* the solution most recently returned by `rx_next_solution'.
*/
int
rx_solutions_final_tag (struct rx_solutions * solns)
{
return solns->final_tag;
}
/************************************************************************
*(h1 "Building and Freeing a Stream of Solutions -- The General Case")
*
* The functions in this section are quite general. They can be used
* to compare a regexp to a string which is not entirely in memory at
* any one time.
*/
/*(c rx_make_solutions)
* struct rx_solutions *
* rx_make_solutions (struct rx_registers * regs,
* int cset_size,
* struct rx_exp_node * expression,
* struct rx_exp_node ** subexps,
* int nsub,
* rx_off_t start,
* rx_off_t end,
* int interval_x,
* rx_vmfn vmfn,
* rx_contextfn contextfn,
* void * closure,
* int small_p,
* int certainly_fits,
* int certain_final_tag);
*
*
* Construct a stream-of-solutions to a regexp matching problem. For
* arguments which are not documented here, see
* xref:"rx_basic_make_solutions".
*
* If `expression' is of type `r_interval', then `interval_x'
* is the number of matches already accumulated for the subexpression.
* In other words, if expression is `RE{M,N}', it will match as:
*
* RE{max (0,M - interval_x), max (0, N - interval_x)
*
* This function does not directly accept an input string. Instead,
* it accepts the parameters `vmfn', `contextfn', and `closure'.
*
* `vmfn' is a function which can return the address of a substring
* containing a chosen character position within the entire input
* string. It is used to page-in parts of the input string during a
* match. The details of this parameter are given below.
*
* `contextfn' is a function that knows how to evaluate regexp
* expressions which are anchors or backreferences. These kinds of
* subexpressions may be defined in terms of parts of the input string
* that are not in memory or that are not contiguous in memory. The
* `contextfn' has the job of sorting that out in an efficient way.
* The details of this parameter are also given below.
*
* `closure' is an opaque parameter that is passed along to `vmfn' and
* `contextfn'.
*
* `small_p', if not 0, means that the regexp is so trivial that
* heavy-weight optimizations are not likely to pay off. It is always
* safe to pass 0 for this parameter. Internally, Rx passes a non-0
* value if `expression' is 0 or if `expression->small_advised_p' is
* non-0. `expression->small_advised_p' is filled in by
* `rx_analyze_rexp'.
*
* `certainly_fits', if not 0, means that if `expression' is converted
* to a true regular expression (such as by `rx_simplify_rexp') and
* compared to the target string, the target string will certainly match.
* Setting this field can speed up some matches. If this field is
* non-0, `certain_final_tag' must also be set. It is always safe to
* pass 0 for `certainly_fits', though doing so may slow down some matches
* slightly.
*
* `certain_final_tag' is the final DFA state label returned for a
* match of simplified form of `expression' against the target string.
* This field is only used if `certainly_fits' is not 0.
*/
struct rx_solutions *
rx_make_solutions (struct rx_registers * regs,
int cset_size,
struct rx_exp_node * expression,
struct rx_exp_node ** subexps,
int nsub,
rx_off_t start,
rx_off_t end,
int interval_x,
rx_vmfn vmfn,
rx_contextfn contextfn,
void * closure,
int small_p,
int certainly_fits,
int certain_final_tag)
{
struct rx_solutions * solns;
if (!expression && (start != end))
return &no_solutions;
if ( expression
&& (expression->len >= 0)
&& ((expression->type != r_interval)
? (expression->len != (end - start))
: (/* Is an interval expression of fixed length */
(!expression->len
? (end != start)
: ((expression->len - (interval_x * expression->left->len)) != (end - start))))))
return &no_solutions;
solns = (struct rx_solutions *)rx_nfa_cache_malloc (sizeof (*solns));
if (!solns)
return 0;
++solns_allocated;
solns->small_p = small_p;
solns->step = 0;
solns->cset_size = cset_size;
solns->exp = expression;
rx_save_exp (expression);
solns->subexps = subexps;
solns->nsub = nsub;
solns->regs = regs;
solns->start = start;
solns->end = end;
solns->vmfn = vmfn;
solns->contextfn = contextfn;
solns->closure = closure;
solns->dfa = 0;
solns->match_engine.rx = 0;
solns->match_engine.state = 0;
solns->certainly_fits = certainly_fits;
solns->certain_final_tag = certain_final_tag;
solns->no_fancy_guessing = 0;
solns->left_dfa = 0;
solns->left_match_engine.rx = 0;
solns->left_match_engine.state = 0;
solns->split_guess = 0;
solns->left = 0;
solns->right = 0;
solns->interval_x = interval_x;
solns->interval_from = 0;
solns->interval_to = 0;
solns->saved_rm_so = 0;
solns->saved_rm_eo = 0;
solns->final_tag = 0;
if (!small_p)
{
if (!solns->exp || !solns->exp->observed)
{
solns->dfa = rx_unfa (expression, cset_size);
if (!solns->dfa)
{
rx_free_solutions (solns);
return 0;
}
rx_init_dfa_from_nfa (&solns->match_engine, solns->dfa->nfa);
if (rx_dfa_goto_start_superstate (&solns->match_engine, 1))
{
rx_free_solutions (solns);
return 0;
}
}
else
{
struct rx_exp_node * simplified;
if (rx_simplify_rexp (&simplified, cset_size, solns->exp, subexps))
{
rx_free_solutions (solns);
return 0;
}
solns->dfa = rx_unfa (simplified, cset_size);
if (!solns->dfa)
{
rx_free_exp (simplified);
rx_free_solutions (solns);
return 0;
}
rx_init_dfa_from_nfa (&solns->match_engine, solns->dfa->nfa);
if (rx_dfa_goto_start_superstate (&solns->match_engine, 1))
{
rx_free_exp (simplified);
rx_free_solutions (solns);
return 0;
}
rx_free_exp (simplified);
}
}
if (solns->exp && (solns->exp->observed || solns->small_p) && (solns->exp->type == r_concat))
{
struct rx_exp_node * left_simplified;
if (rx_simplify_rexp (&left_simplified, cset_size, solns->exp->left, solns->subexps))
{
rx_free_solutions (solns);
return 0;
}
solns->left_dfa = rx_unfa (left_simplified, cset_size);
if (!solns->left_dfa)
{
rx_free_exp (left_simplified);
rx_free_solutions (solns);
return 0;
}
rx_init_dfa_from_nfa (&solns->left_match_engine, solns->left_dfa->nfa);
rx_free_exp (left_simplified);
}
return solns;
}
/*(include-documentation "match-regexp.h")
*/
/*(c rx_solutions_closure)
* void * rx_solutions_closure (struct rx_solutions * solns);
*
* Given a stream of regexp solutions, return the `closure'
* parameter that was passed to `rx_make_solutions'.
*/
void *
rx_solutions_closure (struct rx_solutions * solns)
{
return solns->closure;
}
/*(c rx_free_solutions)
* void rx_free_solutions (struct rx_solutions * solns);
*
* Free all storage associated with a stream of regexp solutions
* allocated by `rx_make_solutions'. See also
* xref:"rx_basic_free_solutions".
*/
void
rx_free_solutions (struct rx_solutions * solns)
{
if (!solns)
return;
if (solns == &no_solutions)
return;
if (solns->left)
{
rx_free_solutions (solns->left);
solns->left = 0;
}
if (solns->right)
{
rx_free_solutions (solns->right);
solns->right = 0;
}
if (solns->dfa)
{
rx_free_unfa (solns->dfa);
solns->dfa = 0;
}
rx_clear_dfa_state (&solns->match_engine);
if (solns->left_dfa)
{
rx_free_unfa (solns->left_dfa);
solns->left_dfa = 0;
}
rx_clear_dfa_state (&solns->left_match_engine);
if (solns->exp)
{
rx_free_exp (solns->exp);
solns->exp = 0;
}
if (solns->saved_rm_so)
rx_nfa_cache_free (solns->saved_rm_so);
if (solns->saved_rm_eo)
rx_nfa_cache_free (solns->saved_rm_eo);
rx_nfa_cache_free (solns);
++solns_freed;
}
/****************************************************************
*(h1 "Regexp Tree To Regular Expression Conversion")
*
*/
/*(c rx_simplify_rexp)
* int rx_simplify_rexp (struct rx_exp_node ** answer,
* int cset_size,
* struct rx_exp_node *node,
* struct rx_exp_node ** subexps);
*
* Convert an expression, which might not be a regular expression, into
* a regular expression matching a superset of the original pattern.
*
* This is useful for a matching heuristic: the regular superset
* language is used to test a candidate string for a match, the
* original irregular regexp is used to verify the match. The test
* using the regular superset is very fast and many non-matching
* strings can be quickly rejected; the verification using the
* irregular regexp may be slow, so we avoid it when we can.
*
* If the input expression is a regular expression, this is an
* identity function which increments the reference count of `node'.
*
* `answer' is a return parameter.
*
* `subexps' is an array of pointers into the expression `node'.
* Element `N' of the array is the `N'th parenthesized subexpression
* of the tree rooted at `node'. This array is usually computed by
* `rx_analyze_rexp'.
*/
int
rx_simplify_rexp (struct rx_exp_node ** answer,
int cset_size,
struct rx_exp_node * node,
struct rx_exp_node ** subexps)
{
int err;
if (!node)
{
*answer = 0;
return 0;
}
if (!node->observed)
{
rx_save_exp (node);
*answer = node;
return 0;
}
if (node->simplified)
{
rx_save_exp (node->simplified);
*answer = node->simplified;
return 0;
}
switch (node->type)
{
default:
case r_cset:
case r_string:
case r_cut:
panic ("bogus regexp in rx_simplify_rexp");
return -1;
case r_parens:
err = rx_simplify_rexp (answer, cset_size, node->left, subexps);
if (err)
return err;
break;
case r_context:
if (char_is_digit (node->intval))
{
err = rx_simplify_rexp (answer, cset_size, subexps [node->intval - '0'], subexps);
if (err)
return err;
}
else
*answer = 0;
break;
case r_concat:
case r_right_concat:
case r_alternate:
case r_star:
case r_interval:
{
struct rx_exp_node *n;
n = rx_exp_node (node->type);
if (!n)
return REG_ESPACE;
if (node->cset)
{
panic ("found a cset bitset in an unexpected place");
}
n->intval = node->intval;
n->intval2 = node->intval2;
err = rx_simplify_rexp (&n->left, cset_size, node->left, subexps);
if (err)
{
rx_free_exp (n);
return err;
}
err = rx_simplify_rexp (&n->right, cset_size, node->right, subexps);
if (err)
{
rx_free_exp (n);
return err;
}
*answer = n;
}
break;
}
node->simplified = *answer;
rx_save_exp (node->simplified);
return 0;
}
/****************************************************************
*(h1 "Regexp Tree Analysis")
*
*/
/*(c rx_analyze_rexp)
* void rx_analyze_rexp (struct rx_exp_node *** subexps,
* size_t * re_nsub,
* struct rx_exp_node * node);
*
* Recursively analyze the expression tree rooted at `node'. For each
* node, fill in the fields `observed', `observation_contingent',
* `small_advised_p', and `len'. Build an array of parenthesized
* sub-expressions in the tree and return that array in `subexps' and
* the number of elements it contains in `re_nsub'.
*
* See `struct rx_exp_node' for information about the meaning of
* structure fields filled in by this function.
*/
int
rx_analyze_rexp (struct rx_exp_node *** subexps,
size_t * re_nsub,
struct rx_exp_node * node)
{
#define rx_max(a, b) ((a) > (b) ? (a) : (b))
#define rx_min(a, b) ((a) < (b) ? (a) : (b))
if (node)
{
size_t this_subexp;
this_subexp = 0;
if (node->type == r_parens)
{
if (node->intval > 0)
{
struct rx_exp_node ** array;
this_subexp = *re_nsub;
++*re_nsub;
if (!*subexps)
array = ((struct rx_exp_node **)
rx_nfa_cache_malloc (sizeof (struct rx_exp_node *) * *re_nsub));
else
array = ((struct rx_exp_node **)
rx_nfa_cache_realloc (*subexps,
sizeof (struct rx_exp_node *) * *re_nsub));
if (!array)
return -1;
else
*subexps = array;
}
}
if (node->left && rx_analyze_rexp (subexps, re_nsub, node->left))
return -1;
if (node->right && rx_analyze_rexp (subexps, re_nsub, node->right))
return -1;
switch (node->type)
{
case r_cset:
node->len = 1;
node->observed = 0;
node->observation_contingent = 1;
node->small_advised_p = 1;
node->max_enclosed_paren = 0;
node->min_enclosed_paren = 0;
break;
case r_string:
node->len = node->str_len;
node->observed = 0;
node->observation_contingent = 1;
node->small_advised_p = 1;
node->max_enclosed_paren = 0;
node->min_enclosed_paren = 0;
break;
case r_cut:
node->len = -1;
node->observed = 0;
node->observation_contingent = 1;
node->small_advised_p = 1;
node->max_enclosed_paren = 0;
node->min_enclosed_paren = 0;
break;
case r_concat:
case r_right_concat:
case r_alternate:
{
int lob, rob;
int lobc, robc;
long llen, rlen;
lob = (!node->left ? 0 : node->left->observed);
lobc = (!node->left ? 1 : node->left->observation_contingent);
rob = (!node->right ? 0 : node->right->observed);
robc = (!node->right ? 1 : node->right->observation_contingent);
llen = (!node->left ? 0 : node->left->len);
rlen = (!node->right ? 0 : node->right->len);
if ((llen < 0) || (rlen < 0))
node->len = -1;
else if ((node->type == r_concat) || (node->type == r_right_concat))
{
if (((size_t)llen + (size_t)rlen) > SSIZE_MAX)
panic ("absurdly large regexp in rx_analyze_rexp");
node->len = (long)(llen + rlen);
}
else /* node->type == r_alternate */
{
if (llen == rlen)
node->len = llen;
else
node->len = -1;
}
node->observed = lob || rob;
node->observation_contingent = lobc && robc;
if ((node->type == r_concat) || (node->type == r_right_concat))
{
node->small_advised_p = ( (!node->left || node->left->small_advised_p)
&& (!node->right || node->right->small_advised_p));
}
else /* node->type == r_alternate */
{
node->small_advised_p = 0;
}
node->max_enclosed_paren = rx_max ((node->left ? node->left->max_enclosed_paren : 0),
(node->right ? node->right->max_enclosed_paren : 0));
{
int lmin;
int rmin;
lmin = (node->left ? node->left->min_enclosed_paren : 0);
rmin = (node->right ? node->right->min_enclosed_paren : 0);
node->min_enclosed_paren = (!lmin
? rmin
: (!rmin
? lmin
: rx_min (lmin, rmin)));
}
break;
}
case r_star:
node->len = ((node->left && node->left->len)
? -1
: 0);
node->observed = (node->left
? node->left->observed
: 0);
node->observation_contingent = (node->left
? node->left->observation_contingent
: 1);
node->small_advised_p = 0;
node->max_enclosed_paren = (node->left ? node->left->max_enclosed_paren : 0);
node->min_enclosed_paren = (node->left ? node->left->min_enclosed_paren : 0);
break;
case r_interval:
if (!node->left || (node->left->len == 0) || (node->intval2 == 0))
node->len = 0;
else if (node->left->len < 0)
node->len = -1;
else if (node->intval == node->intval2)
{
if (node->left->len > (SSIZE_MAX / node->intval))
node->len = -1;
else
node->len = node->left->len * node->intval;
}
else
node->len = -1;
node->observed = 1;
node->observation_contingent = 0;
node->small_advised_p = 0;
node->max_enclosed_paren = (node->left ? node->left->max_enclosed_paren : 0);
node->min_enclosed_paren = (node->left ? node->left->min_enclosed_paren : 0);
break;
case r_parens:
if (node->intval > 0)
{
node->observed = 1;
(*subexps)[this_subexp] = node;
}
else
node->observed = (node->left
? node->left->observed
: 0);
node->observation_contingent = ( node->observed
&& (node->left
? node->left->observation_contingent
: 1));
node->len = (node->left
? node->left->len
: 0);
node->small_advised_p = (!node->left || node->left->small_advised_p);
node->max_enclosed_paren = rx_max (node->intval, (node->left ? node->left->max_enclosed_paren : 0));
if (node->left && node->left->min_enclosed_paren)
{
if (!node->intval)
node->min_enclosed_paren = node->left->min_enclosed_paren;
else
node->min_enclosed_paren = rx_min (node->intval, node->left->min_enclosed_paren);
}
else
node->min_enclosed_paren = node->intval;
break;
case r_context:
switch (node->intval)
{
default:
node->small_advised_p = 1;
node->observed = 1;
node->observation_contingent = 0;
node->len = -1;
break;
case '^':
case '$':
node->small_advised_p = 1;
node->observed = 1;
node->observation_contingent = 0;
node->len = 0;
break;
}
node->max_enclosed_paren = 0;
node->min_enclosed_paren = 0;
break;
}
}
return 0;
}
syntax highlighted by Code2HTML, v. 0.9.1