fr_trie/glob/
mod.rs

1//! A tiny and limited glob matcher implementation for FR Tries (optional)
2pub mod acl;
3
4use std::cell::RefCell;
5use std::sync::Arc;
6use crate::matcher::{Ahead, Event, MatchType, PushdownStateMachine, State, StateSequence};
7
8#[derive(Debug)]
9pub struct MachineInstance {
10    tokens: Vec<Arc<StateSequence>>,
11    state: State,
12    glob_idx: usize,
13    glob_char_idx: usize,
14}
15
16impl MachineInstance {
17
18    #[inline]
19    fn feed(&mut self, ev: Event) {
20        match (&self.state, ev) {
21            (State::Accepting | State::Expecting, Event::EndOfStream) => {
22                if self.at_end() {
23                    match &self.state {
24                        State::Accepting => {
25                            self.state = State::Accepted;
26                        }
27                        State::Expecting => {
28                            self.state = State::Accepted;
29                        }
30                        State::Accepted => {
31                            self.state = State::Accepted;
32                        }
33                        State::Rejected => {
34                            self.state = State::Rejected;
35                        }
36                        State::Beyond => {
37                            self.state = State::Beyond;
38                        }
39                        State::Failure(msg) => {
40                            self.state = State::Failure(msg.clone());
41                        }
42                    }
43                }
44                else {
45                    match self.look_ahead() {
46                        None => {
47                            self.state = State::Accepted;
48                        }
49                        Some(_ahead) => {
50                            self.state = State::Rejected;
51                        }
52                    }
53
54                }
55            },
56            (State::Accepting | State::Expecting, Event::CharIn(ch)) => {
57                match self.look_ahead() {
58                    None => {
59                        self.state = State::Beyond;
60                    }
61                    Some(ahead) => {
62                        match ahead {
63                            Ahead::Exactly(current_char) => {
64                                if current_char == ch {
65                                    self.advance();
66                                    if self.at_end() {
67                                        //self.state = State::Accepted;
68                                    }
69                                    else {
70                                        //self.state = State::Expecting;
71                                    }
72                                }
73                                else if ch < current_char {
74                                    self.state = State::Beyond;
75                                }
76                                else {
77                                    self.state = State::Rejected;
78                                }
79                            }
80                            Ahead::AnyOr(current_char) => {
81                                if current_char == ch {
82                                    self.advance();
83                                    if self.at_end() {
84                                        //self.state = State::Accepted;
85                                    }
86                                    self.state = State::Accepting;
87                                }
88                            }
89                            Ahead::Any => {
90                                self.state = State::Accepting;
91                            }
92                        }
93                    }
94                }
95            }
96            (s, e) => {
97                self.state = State::Failure(format!("Wrong state, event combination: {:#?} {:#?}", s, e)
98                    .to_string())
99            }
100        }
101    }
102
103    #[inline]
104    fn look_ahead(&self) -> Option<Ahead> {
105        match self.tokens.get(self.glob_idx) {
106            None => {
107                return None; // Exceeding limits
108            }
109            Some(current_glob) => {
110                match current_glob.sequence.get(self.glob_char_idx) {
111                    None => {
112                        match current_glob.match_type {
113                            MatchType::Literal => {
114                                return None;
115                            }
116                            MatchType::AnyOr => {
117                                return Some(Ahead::Any)
118                            }
119                        }
120                    }
121                    Some(current_char) => {
122                        match current_glob.match_type {
123                            MatchType::Literal => {
124                                return Some(Ahead::Exactly(*current_char))
125                            }
126                            MatchType::AnyOr => {
127                                return Some(Ahead::AnyOr(*current_char))
128                            }
129                        }
130                    }
131                }
132            }
133        }
134    }
135
136    #[inline]
137    fn advance(&mut self) {
138        match self.tokens.get(self.glob_idx) {
139            None => {
140                panic!("Cannot advance");
141            }
142            Some(current_glob) => {
143                if self.glob_char_idx < current_glob.sequence.len() - 1 {
144                    self.glob_char_idx += 1;
145                }
146                else if self.glob_idx < self.tokens.len() - 1 {
147                    self.glob_char_idx = 0;
148                    self.glob_idx += 1;
149                }
150                else { // Position at END
151                    self.glob_char_idx = 0;
152                    self.glob_idx = self.tokens.len();
153                }
154            }
155        }
156    }
157
158    #[inline]
159    fn at_end(&self) -> bool {
160        match self.tokens.get(self.glob_idx) {
161            None => {
162                true
163            }
164            Some(current_glob) => {
165                if self.glob_idx + 1 >= self.tokens.len() {
166                    if self.glob_char_idx + 1 > current_glob.sequence.len() {
167                        return true;
168                    }
169                    else {
170                        return false;
171                    }
172                }
173                else {
174                    return false;
175                }
176            }
177        }
178    }
179
180    #[inline]
181    fn is_expecting(&self) -> bool {
182        match self.tokens.get(self.glob_idx) {
183            None => {
184                false
185            }
186            Some(_) => {
187                if self.glob_idx == self.tokens.len() {
188                    return false;
189                }
190                else {
191                    return true;
192                }
193            }
194        }
195    }
196}
197
198/////////////////////////////
199#[derive(Debug, Clone)]
200pub struct GlobMatcher {
201    stack: Vec<Arc<RefCell<MachineInstance>>>,
202}
203
204impl PushdownStateMachine for GlobMatcher {
205    fn new() -> Self {
206        Self {
207            stack: Vec::new(),
208        }
209    }
210
211    #[inline]
212    fn step_in(&mut self, sequence: &Vec<Arc<StateSequence>>) {
213        let new_instance = match self.stack.last() {
214            None => {
215                let initial_state = match sequence.first() {
216                    None => {
217                        State::Failure(String::from("No regexp provided"))
218                    }
219                    Some(first_seq) => {
220                        match first_seq.match_type {
221                            MatchType::Literal => {
222                                State::Expecting
223                            },
224                            MatchType::AnyOr => {
225                                State::Accepting
226                            },
227                        }
228                    }
229                };
230
231                Arc::new(RefCell::new(MachineInstance {
232                    tokens: sequence.clone(),
233                    state: initial_state,
234                    glob_idx: 0,
235                    glob_char_idx: 0,
236                }))
237            }
238            Some(top) => {
239                let machine = top.borrow();
240                let mut tokens = machine.tokens.clone();
241                for aditional_token in sequence {
242                    tokens.push(aditional_token.clone());
243                }
244                Arc::new(RefCell::new(MachineInstance {
245                    tokens,
246                    state: machine.state.clone(),
247                    glob_idx: machine.glob_idx,
248                    glob_char_idx: machine.glob_char_idx,
249                }))
250            }
251        };
252        self.stack.push(new_instance);
253    }
254
255    #[inline]
256    fn step_out(&mut self) {
257        let _k = self.stack.pop();
258    }
259
260    #[inline]
261    fn accepts_more(&self) -> bool {
262        match self.stack.last() {
263            Some(machine) => machine.borrow().is_expecting(),
264            None => false
265        }
266    }
267
268    #[inline]
269    fn feed(&mut self, ev: Event) {
270        match self.stack.last_mut() {
271            Some(machine) => machine.borrow_mut().feed(ev),
272            None => {}
273        }
274    }
275
276    #[inline]
277    fn state(&self) -> State {
278        match self.stack.last() {
279            Some(machine) => machine.borrow().state.clone(),
280            None => State::Failure(String::from("Machine not initiallized"))
281        }
282    }
283
284    #[inline]
285    fn is_sink(&self) -> bool {
286        match self.stack.last() {
287            Some(machine) => match machine.borrow().state {
288                State::Accepting => false,
289                State::Expecting => false,
290                State::Accepted => true,
291                State::Rejected => true,
292                State::Beyond => true,
293                State::Failure(_) => true,
294            },
295            None => true,
296        }
297    }
298}
299
300#[cfg(test)]
301mod tests {
302    use super::*;
303
304    #[test]
305    fn matcher_test() {
306
307        let mut expected_token_sequence: Vec<Arc<StateSequence>> = Vec::new();
308        expected_token_sequence.push(Arc::new(StateSequence {
309            match_type: MatchType::Literal,
310            sequence: String::from("123").chars().collect()
311        }));
312        let mut matcher = GlobMatcher::new();
313        matcher.step_in(&expected_token_sequence);
314        let str: Vec<char> = String::from("12345").chars().collect();
315        let mut input = str.iter();
316        matcher.feed(Event::CharIn(*input.next().unwrap()));
317        matcher.feed(Event::CharIn(*input.next().unwrap()));
318        matcher.feed(Event::CharIn(*input.next().unwrap()));
319
320        matcher.feed(Event::EndOfStream);
321        let _st = matcher.state();
322        let _st = matcher.accepts_more();
323
324        matcher.feed(Event::CharIn(*input.next().unwrap()));
325        let _st = matcher.state();
326        let _st = matcher.accepts_more();
327
328        println!("{:?}", matcher.stack.last().unwrap());
329        let mi = matcher.stack.last().unwrap();
330        let _v = mi.as_ref().borrow().look_ahead();
331        let _v = mi.as_ref().borrow().is_expecting();
332
333        matcher.step_out();
334        let _st = matcher.state();
335        let _st = matcher.accepts_more();
336
337        matcher.feed(Event::CharIn(*input.next().unwrap()));
338
339        println!("{:?}", matcher.clone());
340
341        expected_token_sequence.push(Arc::new(StateSequence {
342            match_type: MatchType::AnyOr,
343            sequence: Vec::new()
344        }));
345        let str: Vec<char> = String::from("12345").chars().collect();
346        let mut input = str.iter();
347        matcher.step_out();
348        matcher.step_in(&expected_token_sequence);
349        matcher.feed(Event::CharIn(*input.next().unwrap()));
350        let _st = matcher.state();
351        let _st = matcher.accepts_more();
352
353        let mi = matcher.stack.last().unwrap();
354        let _v = mi.as_ref().borrow().look_ahead();
355        let _v = mi.as_ref().borrow().is_expecting();
356
357    }
358}
fr_trie/glob/mod.rs

fr_trie/glob/
mod.rs
