extern crate levenshtein_automata;
use self::StartsWithStateInternal::*;
use self::levenshtein_automata::Distance;
pub trait Automaton {
type State;
fn start(&self) -> Self::State;
fn is_match(&self, state: &Self::State) -> bool;
fn can_match(&self, _state: &Self::State) -> bool {
true
}
fn will_always_match(&self, _state: &Self::State) -> bool {
false
}
fn accept(&self, state: &Self::State, byte: u8) -> Self::State;
fn starts_with(self) -> StartsWith<Self> where Self: Sized {
StartsWith(self)
}
fn union<Rhs: Automaton>(
self,
rhs: Rhs,
) -> Union<Self, Rhs> where Self: Sized {
Union(self, rhs)
}
fn intersection<Rhs: Automaton>(
self,
rhs: Rhs,
) -> Intersection<Self, Rhs> where Self: Sized {
Intersection(self, rhs)
}
fn complement(self) -> Complement<Self> where Self: Sized {
Complement(self)
}
}
impl<'a, T: Automaton> Automaton for &'a T {
type State = T::State;
fn start(&self) -> Self::State {
(*self).start()
}
fn is_match(&self, state: &Self::State) -> bool {
(*self).is_match(state)
}
fn can_match(&self, state: &Self::State) -> bool {
(*self).can_match(state)
}
fn will_always_match(&self, state: &Self::State) -> bool {
(*self).will_always_match(state)
}
fn accept(&self, state: &Self::State, byte: u8) -> Self::State {
(*self).accept(state, byte)
}
}
impl Automaton for levenshtein_automata::DFA {
type State = u32;
fn start(&self) -> Self::State {
self.initial_state()
}
fn is_match(&self, state: &Self::State) -> bool {
match self.distance(*state) {
Distance::Exact(_) => true,
Distance::AtLeast(_) => false
}
}
fn accept(&self, state: &Self::State, byte: u8) -> Self::State {
self.transition(*state, byte)
}
}
#[derive(Clone, Debug)]
pub struct Subsequence<'a> {
subseq: &'a [u8]
}
impl<'a> Subsequence<'a> {
#[inline]
pub fn new(subsequence: &'a str) -> Subsequence<'a> {
Subsequence { subseq: subsequence.as_bytes() }
}
}
impl<'a> Automaton for Subsequence<'a> {
type State = usize;
#[inline]
fn start(&self) -> usize { 0 }
#[inline]
fn is_match(&self, &state: &usize) -> bool {
state == self.subseq.len()
}
#[inline]
fn can_match(&self, _: &usize) -> bool { true }
#[inline]
fn will_always_match(&self, &state: &usize) -> bool {
state == self.subseq.len()
}
#[inline]
fn accept(&self, &state: &usize, byte: u8) -> usize {
if state == self.subseq.len() { return state; }
state + (byte == self.subseq[state]) as usize
}
}
#[derive(Clone, Debug)]
pub struct AlwaysMatch;
impl Automaton for AlwaysMatch {
type State = ();
#[inline] fn start(&self) -> () { () }
#[inline] fn is_match(&self, _: &()) -> bool { true }
#[inline] fn can_match(&self, _: &()) -> bool { true }
#[inline] fn will_always_match(&self, _: &()) -> bool { true }
#[inline] fn accept(&self, _: &(), _: u8) -> () { () }
}
#[derive(Clone, Debug)]
pub struct StartsWith<A>(A);
pub struct StartsWithState<A: Automaton>(StartsWithStateInternal<A>);
enum StartsWithStateInternal<A: Automaton> {
Done,
Running(A::State)
}
impl<A: Automaton> Automaton for StartsWith<A> {
type State = StartsWithState<A>;
fn start(&self) -> StartsWithState<A> {
StartsWithState({
let inner = self.0.start();
if self.0.is_match(&inner) {
Done
} else {
Running(inner)
}
})
}
fn is_match(&self, state: &StartsWithState<A>) -> bool {
match state.0 {
Done => true,
Running(_) => false
}
}
fn can_match(&self, state: &StartsWithState<A>) -> bool {
match state.0 {
Done => true,
Running(ref inner) => self.0.can_match(inner)
}
}
fn will_always_match(&self, state: &StartsWithState<A>) -> bool {
match state.0 {
Done => true,
Running(_) => false
}
}
fn accept(
&self,
state: &StartsWithState<A>,
byte: u8,
) -> StartsWithState<A> {
StartsWithState(
match state.0 {
Done => Done,
Running(ref inner) => {
let next_inner = self.0.accept(inner, byte);
if self.0.is_match(&next_inner) {
Done
} else {
Running(next_inner)
}
}
}
)
}
}
#[derive(Clone, Debug)]
pub struct Union<A, B>(A, B);
pub struct UnionState<A: Automaton, B: Automaton>(A::State, B::State);
impl<A: Automaton, B: Automaton> Automaton for Union<A, B> {
type State = UnionState<A, B>;
fn start(&self) -> UnionState<A, B> {
UnionState(
self.0.start(),
self.1.start()
)
}
fn is_match(&self, state: &UnionState<A, B>) -> bool {
self.0.is_match(&state.0) || self.1.is_match(&state.1)
}
fn can_match(&self, state: &UnionState<A, B>) -> bool {
self.0.can_match(&state.0) || self.1.can_match(&state.1)
}
fn will_always_match(&self, state: &UnionState<A, B>) -> bool {
self.0.will_always_match(&state.0)
|| self.1.will_always_match(&state.1)
}
fn accept(&self, state: &UnionState<A, B>, byte: u8) -> UnionState<A, B> {
UnionState(
self.0.accept(&state.0, byte),
self.1.accept(&state.1, byte)
)
}
}
#[derive(Clone, Debug)]
pub struct Intersection<A, B>(A, B);
pub struct IntersectionState<A: Automaton, B: Automaton>(A::State, B::State);
impl<A: Automaton, B: Automaton> Automaton for Intersection<A, B> {
type State = IntersectionState<A, B>;
fn start(&self) -> IntersectionState<A, B> {
IntersectionState(
self.0.start(),
self.1.start()
)
}
fn is_match(&self, state: &IntersectionState<A, B>) -> bool {
self.0.is_match(&state.0) && self.1.is_match(&state.1)
}
fn can_match(&self, state: &IntersectionState<A, B>) -> bool {
self.0.can_match(&state.0) && self.1.can_match(&state.1)
}
fn will_always_match(&self, state: &IntersectionState<A, B>) -> bool {
self.0.will_always_match(&state.0) && self.1.will_always_match(&state.1)
}
fn accept(
&self,
state: &IntersectionState<A, B>,
byte: u8,
) -> IntersectionState<A, B> {
IntersectionState(
self.0.accept(&state.0, byte),
self.1.accept(&state.1, byte)
)
}
}
#[derive(Clone, Debug)]
pub struct Complement<A>(A);
pub struct ComplementState<A: Automaton>(A::State);
impl<A: Automaton> Automaton for Complement<A> {
type State = ComplementState<A>;
fn start(&self) -> ComplementState<A> {
ComplementState(self.0.start())
}
fn is_match(&self, state: &ComplementState<A>) -> bool {
!self.0.is_match(&state.0)
}
fn can_match(&self, state: &ComplementState<A>) -> bool {
!self.0.will_always_match(&state.0)
}
fn will_always_match(&self, state: &ComplementState<A>) -> bool {
!self.0.can_match(&state.0)
}
fn accept(
&self,
state: &ComplementState<A>,
byte: u8,
) -> ComplementState<A> {
ComplementState(self.0.accept(&state.0, byte))
}
}