/* dfa.c - functions that manipulate regexps as DFAs
*
****************************************************************
* Copyright (C) 1998, 2000 Thomas Lord
*
* See the file "COPYING" for further information about
* the copyright and warranty status of this work.
*/
#include "hackerlab/bugs/panic.h"
#include "hackerlab/mem/mem.h"
#include "hackerlab/rx/escape.h"
#include "hackerlab/rx/dfa.h"
/************************************************************************
*(h0 "DFA String Comparisons"
* :includes ("rx/dfa.h"))
*
*
* A common use for regular expressions is to compile them to DFA and
* compare them to strings using a loop that advances through DFA
* states.
*
* In Rx, the DFA data structure has been heavily optimized for such
* loops. The functions in this chapter implement the most common
* kinds of DFA loop, taking full advantage of the Rx optimizations.
*/
/*(menu)
*/
/*(include-documentation "dfa.h")
*/
/************************************************************************
*(h1 "DFA Allocation Functions")
*
*/
/*(c rx_dfa_alloc)
* struct rx_dfa * rx_dfa_alloc (alloc_limits limits);
*
* Allocate a new DFA, initially not pointing to any NFA or DFA state.
*
*/
struct rx_dfa *
rx_dfa_alloc (alloc_limits limits)
{
struct rx_dfa * a;
a = (struct rx_dfa *)lim_malloc (limits, sizeof (*a));
mem_set0 ((t_uchar *)a, sizeof (*a));
return a;
}
/*(c rx_dfa_free)
* void rx_free_dfa (alloc_limits limits, struct rx_dfa * dfa);
*
* Release all storage associated with `dfa'.
*/
void
rx_dfa_free (alloc_limits limits, struct rx_dfa * dfa)
{
if (dfa->rx)
rx_clear_dfa_state (dfa);
lim_free (limits, dfa);
}
/************************************************************************
*(h1 "Initializing a DFA")
*
*/
/*(c rx_init_dfa_from_nfa)
* void rx_init_dfa_from_nfa (struct rx_dfa * frame, struct rx_nfa * rx);
*
* Make `rx' the NFA of DFA machine `frame'.
*
* The DFA machine must not already have a current DFA state (must be
* in state 0). See xref:"rx_clear_dfa_state".
*
* This function sets the DFA used by `frame', but does not set the
* current DFA state of `frame'.
*/
void
rx_init_dfa_from_nfa (struct rx_dfa * frame, struct rx_nfa * rx)
{
frame->rx = rx;
frame->state = 0;
frame->final_tag = 0;
}
/*(c rx_init_dfa_from_dfa)
* void rx_init_dfa_from_dfa (struct rx_dfa * dest, struct rx_dfa * src);
*
* Make the NFA and DFA state of `src' the NFA and DFA state of
* `dest'. After a call to this function (which is inexpensive), you
* have two DFA machines in equivalent states.
*
* The DFA machine `dest' must not already have a current DFA state
* (`state' must be in state 0). See xref:"rx_clear_dfa_state".
*/
void
rx_init_dfa_from_dfa (struct rx_dfa * dest, struct rx_dfa * src)
{
dest->rx = src->rx;
dest->state = src->state;
dest->final_tag = src->final_tag;
if (dest->state)
rx_lock_superstate (dest->rx, dest->state);
}
/*(c rx_clear_dfa_state)
* void rx_clear_dfa_state (struct rx_dfa * frame);
*
* Clear the DFA state of DFA machine `frame'.
*/
void
rx_clear_dfa_state (struct rx_dfa * frame)
{
if (frame->state)
{
rx_unlock_superstate (frame->rx, frame->state);
frame->state = 0;
frame->final_tag = 0;
}
}
/* rx_dfa_goto_start_superstate
*
* Return (or initialize) a DFA to its start state.
*/
/*(c rx_dfa_goto_start_superstate)
* void rx_dfa_goto_start_superstate (struct rx_dfa * frame,
* int storage_unit_size);
*
* Return state machine `frame' to its starting state.
*
* The starting state is a DFA state built from the epsilon closure of
* the starting state of the NFA. See xref:"rx_set_start_state".
*/
int
rx_dfa_goto_start_superstate (struct rx_dfa * frame,
int storage_unit_size)
{
struct rx_superstate * start_state;
start_state = rx_nfa_state_to_superstate (frame->rx, frame->rx->start_nfa_state, storage_unit_size);
if (!start_state)
return -1;
if (frame->state)
rx_unlock_superstate (frame->rx, frame->state);
frame->state = start_state;
frame->final_tag = start_state->members->state_label;
rx_lock_superstate (frame->rx, frame->state);
return 0;
}
/************************************************************************
*(h1 "DFA Comparison Functions")
*
* The functions in this section compare an input string to a regular
* expression by advancing through DFA states according to the
* characters in the input string.
*/
/*(c rx_dfa_can_continue)
* int rx_dfa_can_continue (struct rx_dfa * frame);
*
* Return a non-zero value if there exist characters for which the
* current state of DFA machine `frame' has transitions defined. If
* this function returns 0, then the machine is in a dead-end state.
*/
int
rx_dfa_can_continue (struct rx_dfa * frame)
{
return ( frame->state
&& frame->state->members->has_cset_edges);
}
int
rx_dfa_tag (struct rx_dfa * frame)
{
return frame->final_tag;
}
/*(c rx_dfa_fits)
* int rx_dfa_fits (int * label,
* struct rx_dfa * frame,
* const t_uchar * burst,
* size_t len);
*
*
* Compare a DFA to string: is the entire string matched by the DFA?
* Return -1 if an error occurs, 0 otherwise.
*
* The final state label reached is returned in `*label': 0 if
* if the string does not match, non-0 if it does.
*
* It is possible to asynchronously abort a call to this function.
* See xref:"Exiting Long-running Matches".
*/
int
rx_dfa_fits (int * label,
struct rx_dfa * frame,
const t_uchar * burst,
size_t len)
{
int adv;
adv = rx_dfa_advance (frame, burst, len);
if (adv < 0)
return -1;
else if (!adv)
{
*label = 0;
return 0;
}
else
{
*label = frame->final_tag;
return 0;
}
}
/*(c rx_dfa_advance)
* int rx_dfa_advance (struct rx_dfa * frame,
* const t_uchar * burst,
* size_t len);
*
*
* Advance a DFA, reading characters from the input string. Stop at
* the end of the string, returning 1 or when a character is
* encountered for which no transition is defined, returning 0.
* -1 == ESPACE.
*
* This is similar to `rx_dfa_fits', except that in this case, we
* don't care about the state label of the final state.
*
* It is possible to asynchronously abort a call to this function.
* See xref:"Exiting Long-running Matches".
*/
int
rx_dfa_advance (struct rx_dfa * frame,
const t_uchar * burst,
size_t len)
{
rx_transition_table inx_table;
if (!len)
return 1;
inx_table = frame->state->transitions;
rx_unlock_superstate (frame->rx, frame->state);
frame->state = 0;
while (len--)
{
struct rx_inx * inx;
rx_transition_table next_table;
if (rx_poll)
(*rx_poll)();
inx = rx_transition8 (inx_table, *burst);
next_table = (rx_transition_table)inx->data;
while (!next_table)
{
struct rx_superstate * state;
state = rx_transitions_to_suprestate (inx_table);
switch ((long)inx->inx)
{
case rx_backtrack:
/* RX_BACKTRACK means that we've reached the empty
* superstate, indicating that match can't succeed
* from this point.
*/
frame->state = 0;
frame->final_tag = 0;
return 0;
case rx_cache_miss:
/* Because the superstate NFA is lazily constructed,
* and in fact may erode from underneath us, we sometimes
* have to construct the next instruction from the hard way.
* This invokes one step in the lazy-conversion.
*/
inx = rx_handle_cache_miss (frame->rx, state, *burst, inx->data_2);
if (!inx)
{
frame->state = 0;
frame->final_tag = 0;
return -1;
}
next_table = (rx_transition_table)inx->data;
continue;
/* No other instructions are legal here.
*/
default:
panic ("unrecognized instruction in rx_dfa_advance");
}
}
inx_table = next_table;
++burst;
}
frame->state = rx_transitions_to_suprestate (inx_table);
frame->final_tag = frame->state->members->state_label;
rx_lock_superstate (frame->rx, frame->state);
return 1;
}
/*(c rx_dfa_advance_to_final)
* size_t rx_dfa_advance_to_final (struct rx_dfa * frame,
* const t_uchar * burst,
* size_t len);
*
* Advance a DFA, reading characters from a string.
*
* Stop at the end of the string, a character with no transition, or
* when a superstate is encountered with a non-0 label. Return the
* number of characters read from the string.
*
* 0 == backtrack, 1 == found final state or ran out of characters, -1 == ESPACE
*
* This function stops on a transition *into* a state with a non-0
* state label. It doesn't matter if the machine is initially in a
* state with a non-0 label: the machine will consume the first input
* character regardless. That means that if your regular expression
* can match the empty string, you must detect this condition before
* calling `rx_dfa_advance_to_final' by checking `dfa->final_tag'
* after setting the start state of the DFA.
*
* If the match stopped in a final state, `dfa->final_tag' contains
* the non-0 state label of the final state, otherwise, it contains 0.
* If the match stopped on an illegal character, `dfa->state' is 0,
* otherwise it is non-0.
*
* It is possible to asynchronously abort a call to this function.
* See xref:"Exiting Long-running Matches".
*/
int
rx_dfa_advance_to_final (size_t * amt,
struct rx_dfa * frame,
const t_uchar * burst,
size_t len)
{
size_t initial_len;
rx_transition_table inx_table;
if (!len)
{
*amt = 0;
return 1;
}
initial_len = len;
inx_table = frame->state->transitions;
rx_unlock_superstate (frame->rx, frame->state);
frame->state = 0;
while (len--)
{
struct rx_inx * inx;
rx_transition_table next_table;
if (rx_poll)
(*rx_poll)();
inx = rx_transition8 (inx_table, *burst);
next_table = (rx_transition_table)inx->data;
while (!next_table)
{
struct rx_superstate * state;
state = rx_transitions_to_suprestate (inx_table);
switch ((long)inx->inx)
{
case rx_backtrack:
/* RX_BACKTRACK means that we've reached the empty
* superstate, indicating that match can't succeed
* from this point.
*/
frame->state = 0;
frame->final_tag = 0;
*amt = (initial_len - len) - 1;
return 0;
case rx_cache_miss:
/* Because the superstate NFA is lazily constructed,
* and in fact may erode from underneath us, we sometimes
* have to construct the next instruction from the hard way.
* This invokes one step in the lazy-conversion.
*/
inx = rx_handle_cache_miss (frame->rx, state, *burst, inx->data_2);
if (!inx)
{
frame->state = 0;
frame->final_tag = 0;
return -1;
}
next_table = (rx_transition_table)inx->data;
continue;
/* No other instructions are legal here.
*/
default:
while (1)
panic ("unrecognized instruction in rx_dfa_advance_to_final");
}
}
if (inx->data_2)
{
frame->state = rx_transitions_to_suprestate (next_table);
rx_lock_superstate (frame->rx, frame->state);
frame->final_tag = (long)inx->data_2;
*amt = (initial_len - len);
return 1;
}
inx_table = next_table;
++burst;
}
/* Consumed all of the characters. */
frame->state = rx_transitions_to_suprestate (inx_table);
rx_lock_superstate (frame->rx, frame->state);
frame->final_tag = 0;
*amt = initial_len;
return 1;
}
syntax highlighted by Code2HTML, v. 0.9.1