fsa/
nfa.rs

1use bit_set::BitSet;
2use std::fmt::Display;
3use std::io::Write;
4
5pub use self::Etrans::{No, One, Two, More};
6
7/* non-deterministic finite automaton */
8
9// dirty optimisation
10// states of the automaton built by the Thompson construction may have
11// * A single e-trans, in the case of the f1nal states of an or
12// * Two e-trans, in most cases
13// * More, for the initial state on the NFA that may transition to the NFA
14//   of each of the patterns
15// To avoid systematically using an array, we use this structure:
16pub enum Etrans {
17    No,
18    One(usize),
19    Two(usize, usize),
20    More(Vec<usize>)
21}
22
23impl Etrans {
24    pub fn push(&mut self, item: usize) {
25        match *self {
26            No => *self = One(item),
27            One(x) => *self = Two(x, item),
28            Two(x, y) => *self = More(vec![x, y, item]),
29            More(ref mut v) => v.push(item)
30        }
31    }
32}
33
34pub trait StateData {
35    fn no_data() -> Self;
36    fn combine(a: Self, b: Self) -> Self;
37    fn is_final(&self) -> bool;
38}
39
40pub trait State {
41    type Data: StateData;
42    type Iter: Iterator<Item = usize>;
43
44    fn new() -> Self;
45    fn etransition<'a>(&'a self) -> &'a Etrans;
46    fn transition(&self, c: u8) -> Self::Iter;
47    fn data(&self) -> Self::Data;
48}
49
50pub struct Automaton<T> where T: State {
51    pub states: Vec<T>,
52    pub initial: usize
53}
54
55impl<T: State> Automaton<T> {
56    // insert a new empty state and return its number
57    pub fn create_state(&mut self) -> usize {
58        self.states.push(T::new());
59        self.states.len() - 1
60    }
61
62    pub fn moves(&self, st: &BitSet, c: u8) -> Vec<usize> {
63        let mut ret = Vec::with_capacity(st.len());
64
65        for s in st.iter() {
66            for dst in self.states[s].transition(c) {
67                ret.push(dst);
68            }
69        }
70
71        ret
72    }
73
74    #[inline(always)]
75    pub fn eclosure_(&self, st: usize) -> (BitSet, T::Data) {
76        self.eclosure(&[st])
77    }
78
79    pub fn eclosure(&self, st: &[usize]) -> (BitSet, T::Data) {
80        let mut ret = BitSet::with_capacity(self.states.len());
81        let mut ret_action = T::Data::no_data();
82        let mut stack = Vec::with_capacity(st.len());
83
84        macro_rules! add {
85            ($state: expr) => {
86                if !ret.contains($state) {
87                    ret.insert($state);
88                    stack.push($state);
89
90                    ret_action = T::Data::combine(
91                        self.states[$state].data(),
92                        ret_action
93                    );
94                }
95            }
96        }
97
98        for &s in st.iter() {
99            add!(s);
100        }
101
102        while !stack.is_empty() {
103            let st = stack.pop().unwrap();
104            let st = &self.states[st];
105
106            match *st.etransition() {
107                No => (),
108                One(i) => add!(i),
109                Two(i, j) => { add!(i) ; add!(j) }
110                More(ref v) => {
111                    for &i in v.iter() {
112                        add!(i);
113                    }
114                }
115            }
116        }
117
118        (ret, ret_action)
119    }
120
121    #[allow(dead_code)]
122    #[allow(unused_must_use)]
123    // outs the automaton as a dot file for graphviz
124    // for debugging purposes
125    pub fn todot(&self, out: &mut Write) where T::Data: Display + Eq {
126        writeln!(out, "digraph automata {{");
127        writeln!(out, "\trankdir = LR;");
128        writeln!(out, "\tsize = \"4,4\";");
129        writeln!(out, "\tnode [shape=box]; {};", self.initial);
130        writeln!(out, "\tnode [shape=doublecircle];");
131        write!(out, "\t");
132
133        // outputs f1nal states as doublecircle-shaped nodes
134        for st in 0 .. self.states.len() {
135            if self.states[st].data() != T::Data::no_data() {
136                write!(out, "{} ", st);
137            }
138        }
139
140        writeln!(out, ";\n");
141        writeln!(out, "\tnode [shape=circle];");
142
143        for st in 0 .. self.states.len() {
144            for ch in 0 .. 256 {
145                for dst in self.states[st].transition(ch as u8) {
146                    let mut esc = String::new();
147                    esc.extend((ch as u8 as char).escape_default());
148                    writeln!(out, "\t{} -> {} [label=\"{}\"];", st, dst, esc);
149                }
150            }
151
152            match *self.states[st].etransition() {
153                One(s) => {
154                    writeln!(out, "\t{} -> {} [label=\"e\"];", st, s);
155                }
156                Two(s, t) => {
157                    writeln!(out, "\t{} -> {} [label=\"e\"];", st, s);
158                    writeln!(out, "\t{} -> {} [label=\"e\"];", st, t);
159                }
160                More(ref v) => {
161                    for i in v.iter() {
162                        writeln!(out, "\t{} -> {} [label=\"e\"];", st, *i);
163                    }
164                }
165                _ => ()
166            }
167        }
168
169        writeln!(out, "}}");
170    }
171}
fsa/nfa.rs

fsa/
nfa.rs
