Struct FastAutomaton 

pub struct FastAutomaton { /* private fields */ }

Represents a finite-state automaton.

Implementations

impl FastAutomaton

pub fn cardinality(&self) -> Result<Cardinality<u32>, EngineError>

Returns the cardinality of the automaton (i.e., the number of possible matched strings).

Works on non-deterministic automata too: acyclic NFAs are determinized internally (the only fallible step, subject to the crate::execution_profile::ExecutionProfile budget, and rejected with EngineError::DeterministicAutomatonRequired when the profile disables implicit determinization).

As in length, only cycles on accepting paths make the count infinite: cycles among dead or unreachable states don’t add a single matched string.

impl FastAutomaton

pub fn equivalent(&self, other: &FastAutomaton) -> Result<bool, EngineError>

Returns true if both automata accept the same language.

Non-deterministic operands are determinized internally, unless the execution profile disables implicit determinization, in which case EngineError::DeterministicAutomatonRequired is returned.

impl FastAutomaton

pub fn length(&self) -> (Option<u32>, Option<u32>)

Returns the minimum and maximum length of matched strings.

Cycles are only treated as “language-extending” if they sit on an accepting path. Cycles among dead states (states that can’t reach any accept) don’t extend the language and therefore don’t make the max infinite.

Runs in O(V + E): the minimum is a BFS distance; the maximum is a longest path over the subgraph of states lying on accepting paths, which is unbounded exactly when that subgraph has a cycle (any such cycle can be pumped).

impl FastAutomaton

pub fn subset(&self, other: &FastAutomaton) -> Result<bool, EngineError>

Returns true if all strings accepted by self are also accepted by other.

A non-deterministic other is determinized internally, unless the execution profile disables implicit determinization, in which case EngineError::DeterministicAutomatonRequired is returned.

impl FastAutomaton

pub fn is_empty(&self) -> bool

Checks if the automaton matches the empty language.

Sound and complete: works on NFAs and non-minimal automata without requiring determinization or minimization. O(V + E) worst case, with O(1) fast paths for the common cases.

pub fn is_total(&self) -> bool

Checks if the automaton matches all possible strings.

Sound and complete for deterministic automata: a DFA’s language equals Σ* iff every reachable state is accepting AND its outgoing conditions union to Σ. For NFAs this is sound but conservative: alternative paths may cover a character that no single reachable state covers, so callers that need an exact answer on an NFA should determinize first.

O(V + E) plus one condition-union per outgoing transition.

pub fn is_empty_string(&self) -> bool

Checks if the automaton only matches the empty string "".

Sound and complete on any automaton (DFA or NFA): the language equals {""} iff start is accepting AND no state reachable from start by at least one non-empty transition is, or can reach, an accept state. O(V + E).

pub fn live_states(&self) -> IntSet<State>

Returns the “live” (co-reachable) states: those that can reach an accept state by following non-empty transitions. Computed by a reverse traversal from the accept states.

This is co-reachability; note it is not the set of states reachable from the start state.

pub fn spanning_bases(&self) -> Result<Vec<Condition>, EngineError>

Returns one Condition per base of the spanning set, including the “rest” range when it is non-empty.

The bases must partition the whole alphabet Σ: subset construction (determinize) and Hopcroft partitioning (minimize) iterate them and would otherwise silently drop transitions whose condition lies in the “rest” range. (For a spanning set with an empty rest this is exactly the spanning ranges, so well-formed automata are unaffected.)

impl FastAutomaton

pub fn new_empty() -> Self

Creates an automaton that matches the empty language.

pub fn new_empty_string() -> Self

Creates an automaton that only matches the empty string "".

pub fn new_total() -> Self

Creates an automaton that matches all possible strings.

pub fn new_from_range(range: &CharRange) -> Self

Creates an automaton that matches one of the characters in the given CharRange.

pub fn new_state(&mut self) -> State

Creates a new state and returns its identifier.

pub fn accept(&mut self, state: State)

Marks the provided state as an accepting (final) state.

pub fn unaccept(&mut self, state: State)

Marks the provided state as a non-accepting state.

pub fn add_transition( &mut self, from_state: State, to_state: State, new_cond: &Condition, )

Creates a new transition with the given condition; the condition must follow the automaton’s current spanning set.

If you don’t want to deal with conditions and spanning sets, use add_transition_from_range, which handles the bookkeeping for you.

This method accepts a Condition rather than a raw character set. To build a Condition, call:

Condition::from_range(&range, &spanning_set);

where spanning_set is the automaton’s current SpanningSet. The CharRange you pass must be fully covered by that spanning set. If it isn’t, you have two options:

1. Merge an existing spanning set with another:

let new_set = SpanningSet::merge(&old_set, &other_set);

2. Recompute from a list of ranges:

let new_set = SpanningSet::compute_spanning_set(&[range_set1, range_set2]);

After constructing new_set, apply it to the automaton:

fast_automaton.apply_new_spanning_set(&new_set);

This design allows us to perform unions, intersections, and complements of transition conditions in O(1) time, but it does add some complexity to automaton construction. For more details, you can check this article.

pub fn add_transition_from_range( &mut self, from_state: State, to_state: State, range: &CharRange, ) -> Result<(), EngineError>

Adds a transition labeled with the given character range, taking care of the spanning-set bookkeeping.

This is the convenient counterpart to add_transition: the range is converted to a Condition automatically, and when it is not exactly expressible in the automaton’s current spanning set, the spanning set is extended and every existing condition is re-projected first.

An empty range matches no character, so no transition is added.

Examples

use regexsolver::CharRange;
use regexsolver::fast_automaton::FastAutomaton;
use regex_charclass::char::Char;

let mut automaton = FastAutomaton::new_empty();
let s1 = automaton.new_state();
automaton.accept(s1);

let a_to_c = CharRange::new_from_range(Char::new('a')..=Char::new('c'));
automaton.add_transition_from_range(0, s1, &a_to_c).unwrap();

assert!(automaton.is_match("b"));
assert!(!automaton.is_match("d"));

pub fn try_add_transition( &mut self, from_state: State, to_state: State, new_cond: &Condition, ) -> Result<(), DeterminismLost>

Adds a transition, but refuses if it would turn a DFA into an NFA.

On Err(DeterminismLost) the automaton is left untouched; on Ok, the transition has been added and is_deterministic() still holds (provided it held before the call). This is the opt-in strict counterpart to add_transition.

pub fn add_epsilon_transition(&mut self, from_state: State, to_state: State)

Adds an epsilon transition by eagerly folding to_state’s current transitions (and acceptance) into from_state.

This is a snapshot: transitions added to to_state afterwards are not propagated retroactively. When building automata incrementally, add epsilon transitions last.

pub fn remove_transition(&mut self, from_state: State, to_state: State)

Removes the transition between the two provided states if it exists.

pub fn remove_state(&mut self, state: State)

Removes the state and its connected transitions; panics if it’s a start state.

pub fn remove_states(&mut self, states: &IntSet<State>)

Removes the given states and their connected transitions; panics if any state does not exist or is the start state.

pub fn recompute_minimal_spanning_set(&mut self) -> Result<(), EngineError>

Recompute a minimal spanning set for the automaton and apply it.

pub fn apply_new_spanning_set( &mut self, new_spanning_set: &SpanningSet, ) -> Result<(), EngineError>

Applies the provided spanning set and projects all existing conditions onto it.

impl FastAutomaton

pub fn to_regex(&self) -> Result<RegularExpression, EngineError>

Converts the automaton to a RegularExpression.

impl FastAutomaton

pub fn generate_strings( &self, limit: usize, offset: usize, options: impl Into<GenerationOptions>, ) -> Result<Vec<String>, EngineError>

Generates up to limit distinct strings matched by the automaton under the given GenerationOptions, skipping the first offset strings.

options is a PathOrder or CharacterOrder on its own (or a pair of them), or a full GenerationOptions to also set the seed and restrict the characters and string lengths used.

Strings are only guaranteed to be distinct within a single call: the offset fast-skips by counting paths, and in a non-deterministic automaton the same string can be reached through several paths, so calls with different offsets may repeat strings (or skip some). determinize (and ideally minimize) first to make pages disjoint. Offsets are also only consistent between calls made with the same options.

GenerationOptions::with_min_length and with_max_length confine the enumeration to a band of string lengths. Without a max, a deep offset into a looping language (.*) pages into arbitrarily long strings. Generation runs under the active ExecutionProfile: its timeout aborts with EngineError::OperationTimeOutError.

impl FastAutomaton

pub fn concat(&self, other: &FastAutomaton) -> Result<Self, EngineError>

Computes the concatenation between self and other.

pub fn concat_all<'a, I: IntoIterator<Item = &'a FastAutomaton>>( automata: I, ) -> Result<Self, EngineError>

Computes the concatenation of all automata in the given iterator.

impl FastAutomaton

pub fn determinize(&self) -> Result<Cow<'_, Self>, EngineError>

Determinizes the automaton and returns the result.

impl FastAutomaton

pub fn complement(&mut self) -> Result<(), EngineError>

Complements the automaton.

If self is non-deterministic, it is determinized in place first, unless the execution profile disables implicit determinization, in which case EngineError::DeterministicAutomatonRequired is returned.

pub fn difference( &self, other: &FastAutomaton, ) -> Result<FastAutomaton, EngineError>

Computes the difference between self and other.

If other is non-deterministic, it is determinized first, unless the execution profile disables implicit determinization, in which case EngineError::DeterministicAutomatonRequired is returned.

impl FastAutomaton

pub fn intersection(&self, other: &FastAutomaton) -> Result<Self, EngineError>

Computes the intersection between self and other.

pub fn intersection_all<'a, I: IntoIterator<Item = &'a FastAutomaton>>( automata: I, ) -> Result<Self, EngineError>

Computes the intersection of all automata in the given iterator.

pub fn intersection_all_par<'a, I: IntoParallelIterator<Item = &'a FastAutomaton>>( automata: I, ) -> Result<Self, EngineError>

Computes in parallel the intersection of all automata in the given iterator.

Only available with the parallel feature (enabled by default), and not on wasm, which has no threads and does not depend on rayon.

pub fn has_intersection( &self, other: &FastAutomaton, ) -> Result<bool, EngineError>

Returns true if the two automata have a non-empty intersection.

impl FastAutomaton

pub fn minimize(&mut self) -> Result<(), EngineError>

Minimizes the automaton using Hopcroft’s Algorithm.

If self is non-deterministic, it is determinized in place first, unless the ExecutionProfile disables implicit determinization, in which case EngineError::DeterministicAutomatonRequired is returned.

impl FastAutomaton

pub fn repeat( &self, min: u32, max_opt: Option<u32>, ) -> Result<FastAutomaton, EngineError>

Computes the repetition of the automaton between min and max_opt times; if max_opt is None, the repetition is unbounded.

impl FastAutomaton

pub fn union(&self, other: &FastAutomaton) -> Result<Self, EngineError>

Computes the union between self and other.

pub fn union_all<'a, I: IntoIterator<Item = &'a FastAutomaton>>( automata: I, ) -> Result<Self, EngineError>

Computes the union of all automata in the given iterator.

pub fn union_all_par<'a, I: IntoParallelIterator<Item = &'a FastAutomaton>>( automata: I, ) -> Result<Self, EngineError>

Computes in parallel the union of all automata in the given iterator.

Only available with the parallel feature (enabled by default), and not on wasm, which has no threads and does not depend on rayon.

impl FastAutomaton

pub fn remove_dead_states(&mut self)

Removes “dead” states (those that cannot reach any accept state), since they never contribute to the language. If the language is empty the whole automaton collapses to the canonical empty automaton.

impl FastAutomaton

pub fn in_degree(&self, state: State) -> usize

Returns the number of transitions to the provided state.

pub fn out_degree(&self, state: State) -> usize

Returns the number of transitions from the provided state. Returns 0 if the state does not exist.

pub fn states(&self) -> impl Iterator<Item = State> + '_

Returns an iterator over the automaton’s states.

pub fn states_vec(&self) -> Vec<State>

Returns a vector containing the automaton’s states.

pub fn direct_states(&self, state: State) -> impl Iterator<Item = State> + '_

Returns an iterator over states directly reachable from the given state in one transition. Returns an empty iterator if the state does not exist.

pub fn direct_states_vec(&self, state: State) -> Vec<State>

Returns a vector of states directly reachable from the given state in one transition.

pub fn transitions_to_vec(&self, state: State) -> Vec<(State, Condition)>

Returns a vector of transitions to the given state.

pub fn transitions_from_vec(&self, state: State) -> Vec<(Condition, State)>

Returns a vector of transitions from the given state. Returns an empty vector if the state does not exist.

pub fn transitions_from( &self, state: State, ) -> impl Iterator<Item = (&Condition, &State)>

Returns an iterator over transitions from the given state. Returns an empty iterator if the state does not exist.

pub fn has_transition(&self, from_state: State, to_state: State) -> bool

Returns true if there is a directed transition from from_state to to_state.

pub fn number_of_states(&self) -> usize

Returns the number of states in the automaton.

pub fn condition( &self, from_state: State, to_state: State, ) -> Option<&Condition>

Returns a reference to the condition of the directed transition between the two states, if any. Returns None if either state does not exist.

pub fn start_state(&self) -> State

Returns the start state.

pub fn accept_states(&self) -> &IntSet<State>

Returns a reference to the set of accept (final) states.

pub fn spanning_set(&self) -> &SpanningSet

Returns a reference to the automaton’s spanning set.

pub fn is_accepted(&self, state: State) -> bool

Returns true if the given state is one of the accept states.

pub fn is_deterministic(&self) -> bool

Returns true if the automaton is deterministic.

Note: this flag degrades monotonically. Once add_transition introduces an overlapping condition, the flag flips to false and is not re-checked by remove_transition or remove_state. The automaton may in fact be deterministic again after such removals; call determinize if you need a fresh DFA.

pub fn is_minimal(&self) -> bool

Returns true if the automaton is minimal.

pub fn has_state(&self, state: State) -> bool

Returns true if the automaton contains the given state.

pub fn is_match(&self, string: &str) -> bool

Returns true if the automaton matches the given string.

pub fn to_dot(&self) -> String

Returns the automaton’s DOT representation.

pub fn print_dot(&self)

Prints the automaton’s DOT representation.

Trait Implementations

impl Clone for FastAutomaton

fn clone(&self) -> FastAutomaton

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for FastAutomaton

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Display for FastAutomaton

fn fmt(&self, sb: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Eq for FastAutomaton

impl From<FastAutomaton> for Term

fn from(automaton: FastAutomaton) -> Self

Converts to this type from the input type.

impl PartialEq for FastAutomaton

fn eq(&self, other: &FastAutomaton) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.

impl StructuralPartialEq for FastAutomaton