lib/
lib.rs

1#![feature(let_chains)]
2#![feature(if_let_guard)]
3#![feature(trait_alias)]
4#![feature(impl_trait_in_bindings)]
5#![feature(lock_value_accessors)]
6#![feature(pattern)]
7
8use debug_print::debug_println;
9use fsm::NodeType::{self, *};
10use fsm::{CycleAwareOp, Keyword};
11pub use fsm::{FSMNode, ToCSV};
12use regex::Regex;
13use std::cell::RefCell;
14#[cfg(not(feature = "thread-safe"))]
15use std::cell::{Ref, RefMut};
16#[cfg(feature = "thread-safe")]
17use std::sync::{RwLock, RwLockReadGuard, RwLockWriteGuard};
18
19pub mod frontend;
20
21mod fsm;
22pub use fsm::FSMNodeWrapper;
23
24pub mod protocol;
25
26thread_local! {
27    static CNT: RefCell<usize> = RefCell::new(0);
28}
29
30fn get_id() -> usize {
31    let mut ret = 0;
32    CNT.with_borrow(|cnt| ret = *cnt);
33    CNT.with_borrow_mut(|cnt| *cnt += 1);
34    return ret;
35}
36fn dbg_id() {
37    debug_println!("{:?}", CNT);
38}
39
40trait PartialMatch {
41    fn partial_match(&self, hay: &str) -> bool;
42}
43
44impl PartialMatch for Regex {
45    /**
46    not a perfect solution and should therefore be never used
47    **/
48    fn partial_match(&self, hay: &str) -> bool {
49        let orig = self.as_str();
50        for i in 1..orig.len() {
51            if let Ok(regex) = Regex::new(&orig[0..=i])
52                && regex.is_match(hay)
53            {
54                return true;
55            }
56        }
57        false
58    }
59}
60
61pub fn get_test_fsm() -> FSMNodeWrapper {
62    let root = FSMNode::new_null(None);
63    let mut sign_token = NodeType::Keyword(Keyword::new("unsigned".to_string(), None));
64    let child = FSMNode::new(sign_token.clone(), &root);
65    sign_token = NodeType::Keyword(Keyword::new("signed".to_string(), None));
66
67    let child2 = FSMNode::new(sign_token, &root);
68    let types = FSMNode::new_required(NodeType::Null, &child);
69
70    let int = FSMNode::new_keyword_with_parent("int".to_string(), types.clone());
71    let float = FSMNode::new_keyword_with_parent("short".to_string(), types.clone());
72    child.borrow_mut().add_child(&types);
73    child2.borrow_mut().add_child(&types);
74    root
75}
76
77// ironic that this only expands names
78struct NameShortener;
79impl NameShortener {
80    fn expand(old: Option<&str>, full: &str) -> String {
81        if full.is_empty() {
82            panic!("Cannot expand the void!")
83        }
84        let ret = if let Some(old) = old {
85            if old == full {
86                return old.to_string(); // FIXME: this can't be a good handling
87                // well screw you past me! It's actually vital for collisions between s1 and s2
88                // where s2.starts_with(s1) applies
89            }
90            if full.len() < old.len() {
91                panic!("NS: There is nothing left...")
92            }
93            let mut ret = old.to_string();
94            ret.push_str(&full[old.len()..old.len() + 1]);
95            ret
96        } else {
97            full[0..1].to_string()
98        };
99        debug_println!("Got {} instead of {old:?}", ret);
100        ret
101    }
102}
103
104#[cfg(not(feature = "thread-safe"))]
105type FSMRc<T> = std::rc::Rc<T>;
106#[cfg(not(feature = "thread-safe"))]
107type FSMWeak<T> = std::rc::Weak<T>;
108#[cfg(not(feature = "thread-safe"))]
109#[derive(Debug, PartialEq)]
110pub struct FSMLock<T>(RefCell<T>);
111#[cfg(not(feature = "thread-safe"))]
112impl<T> FSMLock<T> {
113    fn new(val: T) -> Self {
114        Self(RefCell::new(val))
115    }
116    pub fn borrow(&self) -> Ref<'_, T> {
117        self.0.borrow()
118    }
119    fn borrow_mut(&self) -> RefMut<'_, T> {
120        self.0.borrow_mut()
121    }
122    fn replace_with(&self, op: impl FnOnce(&mut T) -> T) {
123        self.0.replace_with(op);
124    }
125}
126
127#[cfg(feature = "thread-safe")]
128type FSMRc<T> = std::sync::Arc<T>;
129#[cfg(feature = "thread-safe")]
130type FSMWeak<T> = std::sync::Weak<T>;
131#[cfg(feature = "thread-safe")]
132#[derive(Debug)]
133pub struct FSMLock<T>(RwLock<T>);
134#[cfg(feature = "thread-safe")]
135impl<T> FSMLock<T> {
136    pub fn borrow(&self) -> RwLockReadGuard<'_, T> {
137        self.0.read().expect("FSMLock borrow()")
138    }
139    fn borrow_mut(&self) -> RwLockWriteGuard<'_, T> {
140        self.0.write().expect("FSMLock borrow()")
141    }
142    fn new(val: T) -> Self {
143        Self(RwLock::new(val))
144    }
145    fn replace_with(&self, op: impl FnOnce(&mut T) -> T) {
146        let new = op(&mut self.0.write().unwrap());
147        self.0.set(new).unwrap();
148    }
149}
150#[cfg(feature = "thread-safe")]
151impl<T: PartialEq> PartialEq for FSMLock<T> {
152    fn eq(&self, other: &Self) -> bool {
153        self.0.read().unwrap().eq(&other.0.read().unwrap())
154    }
155}
156type InternalCursor = FSMWeak<FSMLock<FSMNode>>;
157#[derive(Clone, Debug, Default)]
158pub struct FSMCursor {
159    root: InternalCursor,
160    cur_ast_pos: InternalCursor,
161    input_buf: String,
162    unfinished_nodes: Vec<InternalCursor>,
163    path: Vec<InternalCursor>,
164}
165
166impl FSMCursor {
167    pub fn new(fsm_root: &FSMRc<FSMLock<FSMNode>>) -> Self {
168        Self {
169            root: FSMRc::downgrade(fsm_root),
170            cur_ast_pos: FSMRc::downgrade(fsm_root),
171            ..Default::default()
172        }
173    }
174    pub fn reset(&mut self) {
175        self.cur_ast_pos = FSMWeak::clone(&self.root);
176        self.input_buf.clear();
177    }
178    fn handle_userdefined_combo(&mut self, input: char, final_chars: &Vec<char>) -> Option<String> {
179        let child_idx = final_chars.iter().position(|char| *char == input);
180        if let Some(_) = child_idx {
181            let strong_ref = self.get_cur_ast_binding();
182            // let borrow = strong_ref.borrow();
183            // let next_node = FSMRc::clone(&borrow.children[child_idx]);
184            let mut ret = None;
185            strong_ref.walk_fsm_depth(
186                &mut |_, _, c, _| {
187                    if let Keyword(Keyword {
188                        short, expanded, ..
189                    }) = &c.borrow().value
190                        && short.starts_with(input)
191                    {
192                        self.update_cursor(&c);
193                        self.input_buf.clear();
194                        ret = Some(expanded.clone());
195                        true
196                    } else {
197                        false
198                    }
199                },
200                false,
201            );
202            ret
203        } else {
204            if let UserDefinedCombo(r, _) = self.get_current_nodeval()
205                && !r.is_match(&self.input_buf)
206            {
207                self.input_buf.pop();
208            }
209            None
210        }
211    }
212    fn handle_userdefined(&mut self, input: char, final_chars: &Vec<char>) -> Option<String> {
213        let child_idx = final_chars.iter().position(|char| *char == input);
214        if let Some(child_idx) = child_idx {
215            let strong_ref = self.get_cur_ast_binding();
216            let borrow = strong_ref.borrow();
217            let next_node = FSMRc::clone(&borrow.children[child_idx]);
218            self.update_cursor(&next_node);
219            let ret = if let NodeType::Keyword(Keyword {
220                short,
221                expanded,
222                closing_token: None,
223                ..
224            }) = &next_node.borrow().value
225                && *short == String::from(input)
226            {
227                Some(expanded.clone())
228            } else {
229                Some(String::from(final_chars[child_idx]))
230            };
231            self.input_buf.clear();
232            ret
233        } else {
234            None
235        }
236    }
237    pub fn clear_inputbuf(&mut self) {
238        self.input_buf.clear();
239    }
240    fn search_for_userdefs(
241        &self,
242        treenode: &FSMRc<FSMLock<FSMNode>>,
243    ) -> Option<FSMRc<FSMLock<FSMNode>>> {
244        treenode.borrow().walk_fsm_breadth(
245            &mut |_, _, child, _| match &child.value {
246                UserDefined { .. } => true,
247                UserDefinedRegex(regex) | UserDefinedCombo(regex, _)
248                    if regex.partial_match(&self.input_buf) =>
249                {
250                    true
251                }
252                _ => false,
253            },
254            false,
255        )
256    }
257    pub fn search_rec(
258        &mut self,
259        treenode: &FSMRc<FSMLock<FSMNode>>,
260    ) -> Option<FSMRc<FSMLock<FSMNode>>> {
261        self.search_rec_internal(treenode, false)
262    }
263    pub fn search_rec_internal(
264        &mut self,
265        treenode: &FSMRc<FSMLock<FSMNode>>,
266        best_effort: bool, // overcomplicates things (and is probably not even used)
267    ) -> Option<FSMRc<FSMLock<FSMNode>>> {
268        debug_println!(
269            "search_rec at {:?} {}",
270            treenode.borrow().value,
271            treenode.borrow().short_id()
272        );
273        debug_println!("search_rec input buf: {}", self.input_buf);
274        let mut keyword_match = None;
275        let mut potential_matches = 0;
276        let mut visited_keywords = 0;
277        let mut last_keyword = None;
278        treenode.walk_fsm_allow_cycle_to_self(
279            &mut |_, _, child, _| {
280                let node_val = &child.borrow().value;
281                debug_println!(
282                    "search_rec closure at {:?} {}",
283                    child.borrow().value,
284                    child.borrow().short_id()
285                );
286                match node_val {
287                    NodeType::Keyword(Keyword { short, .. }) => {
288                        if short.starts_with(&self.input_buf) {
289                            debug_println!("{:?}", child.borrow().value);
290                            debug_println!("{short} == {}", self.input_buf);
291                            keyword_match = Some(child.clone());
292                            potential_matches += 1;
293                            potential_matches > 1
294                        } else {
295                            // bandaid logic
296                            visited_keywords += 1;
297                            if visited_keywords == 1 {
298                                last_keyword = Some(child.clone());
299                            }
300                            false
301                        }
302                    }
303                    _ => false,
304                }
305            },
306            false,
307            false,
308        );
309        debug_println!("pm: {potential_matches}");
310        if keyword_match.is_some() && potential_matches == 1 {
311            return keyword_match;
312        }
313
314        debug_println!("vk: {visited_keywords}");
315        if visited_keywords == 1 && best_effort {
316            // probably what the user wants
317            return last_keyword;
318        }
319
320        let userdef_match = self.search_for_userdefs(treenode);
321        if userdef_match.is_some() {
322            return userdef_match;
323        }
324
325        // if we didn't find any potential keywords/userdef nodes
326        if potential_matches == 0 {
327            // don't like that this function has to take a &mut self just because of this
328            self.input_buf.pop();
329        }
330        None
331    }
332    pub fn advance(&mut self, input: char) -> Option<String> {
333        let binding = self.get_cur_ast_binding();
334        let borrow = binding.borrow();
335        debug_println!(
336            "advance with cursor {:?} {}",
337            borrow.value,
338            borrow.short_id()
339        );
340        self.input_buf.push(input);
341        // TODO: refactor
342        if borrow.is_done() {
343            let res = self.search_rec(&binding);
344            if let Some(node) = res {
345                self.update_cursor(&node);
346                return match &node.borrow().value {
347                    NodeType::Keyword(Keyword { expanded, .. }) => {
348                        self.input_buf.clear();
349                        Some(expanded.clone())
350                    }
351                    NodeType::UserDefined { final_chars } => {
352                        let res = self.handle_userdefined(input, &final_chars);
353                        res
354                    }
355                    NodeType::UserDefinedRegex(_) => None,
356                    _ => unreachable!(),
357                };
358            }
359        }
360        match &borrow.value {
361            NodeType::UserDefined { final_chars, .. } => {
362                let res = self.handle_userdefined(input, final_chars);
363                if res.is_some() {
364                    return res;
365                }
366            }
367            NodeType::UserDefinedRegex(r) => {
368                debug_println!("Checking regex against '{}'", &self.input_buf);
369                if r.is_match(&self.input_buf) {
370                    drop(borrow);
371                    binding.borrow_mut().set_is_done(true);
372                    self.input_buf.clear();
373                    self.input_buf.push(input);
374                    let next_node = self.search_rec_internal(&binding, true);
375                    if next_node.is_none() {
376                        debug_println!("No node found");
377                        self.input_buf.clear();
378                        return Some(input.to_string());
379                    }
380                    let next_node = next_node.unwrap();
381                    self.update_cursor(&next_node);
382                    let ret = if let NodeType::Keyword(Keyword {
383                        short,
384                        expanded,
385                        closing_token: None,
386                        ..
387                    }) = &next_node.borrow().value
388                    {
389                        if short.starts_with(input) {
390                            Some(expanded.clone())
391                        } else {
392                            // FIXME: this is terrible logic
393                            if let Some(next_node) = self.search_rec_internal(&next_node, true) {
394                                self.update_cursor(&next_node);
395                                if let Keyword(Keyword {
396                                    expanded,
397                                    closing_token: None,
398                                    ..
399                                }) = &next_node.borrow().value
400                                // && short.starts_with(input)
401                                {
402                                    Some(expanded.clone())
403                                } else {
404                                    Some(input.to_string())
405                                }
406                            } else {
407                                Some(input.to_string())
408                            }
409                        }
410                    } else {
411                        Some(input.to_string())
412                    };
413                    self.input_buf.clear();
414                    return ret;
415                }
416            }
417            UserDefinedCombo(_, f) => {
418                let ret = self.handle_userdefined_combo(input, f);
419                if ret.is_some() {
420                    return ret;
421                }
422            }
423            _ => {
424                let res = self.search_rec(&binding);
425                if let Some(node) = res {
426                    self.update_cursor(&node);
427                    return match &node.borrow().value {
428                        NodeType::Keyword(Keyword { expanded, .. }) => {
429                            self.input_buf.clear();
430                            Some(expanded.clone())
431                        }
432                        NodeType::UserDefined { final_chars } => {
433                            let res = self.handle_userdefined(input, &final_chars);
434                            res
435                        }
436                        NodeType::UserDefinedRegex(_) => None,
437                        NodeType::UserDefinedCombo(r, f) => {
438                            let res = self.handle_userdefined_combo(input, f);
439                            res
440                        }
441                        _ => unreachable!(),
442                    };
443                }
444            }
445        }
446        None
447    }
448
449    pub fn revert(&mut self) {
450        if self.input_buf.is_empty()
451            && let Some(new_cursor_pos) = self.path.pop()
452        {
453            self.cur_ast_pos = new_cursor_pos;
454        } else if !self.input_buf.is_empty() {
455            self.input_buf.pop();
456        }
457    }
458
459    fn update_cursor(&mut self, node: &FSMRc<FSMLock<FSMNode>>) {
460        self.path.push(self.cur_ast_pos.clone());
461        self.cur_ast_pos = FSMRc::downgrade(&FSMRc::clone(&node));
462        if let NodeType::Keyword(Keyword {
463            closing_token: Some(_),
464            ..
465        }) = &node.borrow().value
466        {
467            self.unfinished_nodes.push(FSMRc::downgrade(&node));
468        } else if node.borrow().children.is_empty() && self.unfinished_nodes.len() > 1 {
469            // we don't need to jump back if only one remains
470            self.cur_ast_pos = self.unfinished_nodes.pop().unwrap();
471        }
472        debug_println!(
473            "uc: {:?} {}",
474            self.get_cur_ast_binding().borrow().value,
475            self.get_cur_ast_binding().borrow().id()
476        );
477    }
478    fn dump(&self) {
479        println!(
480            "Last matched node: {:?}",
481            self.cur_ast_pos.upgrade().unwrap().borrow().value
482        );
483        println!("Input buf: {}", self.input_buf);
484    }
485
486    pub fn is_done(&self) -> bool {
487        let ast_ref = self.cur_ast_pos.upgrade().unwrap();
488        let binding = ast_ref.borrow();
489        match binding.value {
490            UserDefinedRegex(..) | UserDefined { .. } if !binding.is_done() => false,
491            _ => binding.children.is_empty() || !binding.has_useful_children(),
492        }
493    }
494
495    fn get_cur_ast_binding(&self) -> FSMRc<FSMLock<FSMNode>> {
496        self.cur_ast_pos.upgrade().unwrap()
497    }
498    pub fn is_in_userdefined_stage(&self) -> bool {
499        match self.get_cur_ast_binding().borrow().value {
500            NodeType::UserDefined { .. }
501            | NodeType::UserDefinedRegex(..)
502            | NodeType::UserDefinedCombo(_, _) => true,
503            _ => false,
504        }
505    }
506
507    fn get_current_nodeval(&self) -> NodeType {
508        println!("{}", self.get_cur_ast_binding().borrow().id());
509        self.get_cur_ast_binding().borrow().value.clone()
510    }
511    fn find_node_with_code(&self, short: &str) -> Option<FSMRc<FSMLock<FSMNode>>> {
512        let binding = self.get_cur_ast_binding();
513        let binding = binding.borrow();
514        binding.find_node_with_code(short)
515    }
516}
517
518#[cfg(test)]
519mod tests {
520    use crate::frontend::create_graph_from_ebnf;
521
522    use super::*;
523
524    #[test]
525    fn simple_tree() {
526        let root = FSMNode::new_keyword("int".to_string());
527        let _other = FSMNode::new_keyword_with_parent("asdf".to_string(), root.clone());
528        assert_eq!(root.borrow().children.len(), 1);
529    }
530
531    #[test]
532    fn simple_cursor_steps() {
533        let root = FSMNode::new_null(None);
534        let second = FSMNode::new_keyword_with_parent("int".to_string(), root.clone());
535        FSMNode::new_keyword_with_parent("asdf".to_string(), second.clone());
536        let mut cursor = FSMCursor::new(&root);
537        assert_eq!(cursor.get_current_nodeval(), Null);
538        cursor.advance('i').unwrap();
539        assert_eq!(
540            cursor.get_current_nodeval(),
541            NodeType::Keyword(Keyword::new("int".to_string(), None)),
542        );
543        cursor.advance('a').unwrap();
544        assert_eq!(
545            cursor.get_current_nodeval(),
546            NodeType::Keyword(Keyword::new("asdf".to_string(), None)),
547        );
548    }
549
550    #[test]
551    fn test_conflict_check() {
552        let root = FSMNode::new_null(None);
553        let mut sign_token = NodeType::Keyword(Keyword::new("unsigned".to_string(), None));
554        let child = FSMNode::new(sign_token.clone(), &root);
555        sign_token = NodeType::Keyword(Keyword::new("signed".to_string(), None));
556
557        let child2 = FSMNode::new(sign_token, &root);
558        let types = FSMNode::new_required(NodeType::Null, &child);
559
560        let int = FSMNode::new_keyword_with_parent("int".to_string(), types.clone());
561        let float = FSMNode::new_keyword_with_parent("short".to_string(), types.clone());
562        child.borrow_mut().add_child(&types);
563        child2.borrow_mut().add_child(&types);
564
565        assert!(root.borrow().check_for_conflicts("s"));
566        assert!(child2.borrow().check_for_conflicts("s"));
567        assert!(types.borrow().check_for_conflicts("s"));
568        assert!(!int.borrow().check_for_conflicts("s"));
569    }
570
571    #[test]
572    fn test_keyword_matching() {
573        let root = FSMNode::new_null(None);
574        let mut sign_token = NodeType::Keyword(Keyword::new("unsigned".to_string(), None));
575        let child = FSMNode::new(sign_token.clone(), &root);
576        sign_token = NodeType::Keyword(Keyword::new("signed".to_string(), None));
577
578        let child2 = FSMNode::new(sign_token, &root);
579        let types = FSMNode::new_required(NodeType::Null, &child);
580
581        let int = FSMNode::new_keyword_with_parent("int".to_string(), types.clone());
582        let float = FSMNode::new_keyword_with_parent("short".to_string(), types.clone());
583        root.borrow_mut().add_child(&types);
584        child2.borrow_mut().add_child(&types);
585
586        let mut cursor = FSMCursor::new(&root);
587        assert!(cursor.advance('s').is_none());
588        assert!(cursor.advance('h').is_some());
589        let mut cursor = FSMCursor::new(&root);
590        assert!(cursor.advance('u').is_some());
591        assert!(cursor.advance('s').is_some());
592    }
593
594    #[test]
595    fn test_deep_clone() {
596        let root = FSMNode::new_null(None);
597        let mut sign_token = NodeType::Keyword(Keyword::new("unsigned".to_string(), None));
598        let child = FSMNode::new(sign_token.clone(), &root);
599        sign_token = NodeType::Keyword(Keyword::new("signed".to_string(), None));
600
601        let child2 = FSMNode::new(sign_token, &root);
602        let types = FSMNode::new_required(NodeType::Null, &child);
603        println!("hi?");
604        FSMNode::add_child_cycle_safe(&types, &root);
605        let cloned_root = root.borrow().deep_clone();
606        let root = root.borrow();
607        let cloned_root = cloned_root.borrow();
608        assert_eq!(root.value, cloned_root.value);
609        // TODO: make this go all the way through the tree
610        for (i, child) in root.children.iter().enumerate() {
611            assert_eq!(child.borrow().value, cloned_root.children[i].borrow().value);
612        }
613    }
614
615    #[test]
616    fn simple_full() {
617        let bnf = r"
618        t1 ::= t2 | t3;
619        t2 ::= 'r' t3;
620        t3 ::= 'a';
621        ";
622        let root = frontend::create_graph_from_ebnf(bnf).unwrap();
623        let mut cursor = FSMCursor::new(&root);
624        assert_eq!("r", cursor.advance('r').unwrap());
625        assert_eq!("a", cursor.advance('a').unwrap());
626        assert!(cursor.is_done());
627    }
628
629    #[test]
630    fn test_optional() {
631        let bnf = r"
632        t1 ::= 't' ( 'e' t2 )? 't';
633        t2 ::= 's' ( t3 )?;
634        t3 ::= 'a';
635        ";
636        let root = frontend::create_graph_from_ebnf(bnf).unwrap();
637        let mut cursor = FSMCursor::new(&root);
638        assert_eq!("t", cursor.advance('t').unwrap());
639        assert_eq!("t", cursor.advance('t').unwrap());
640        assert!(cursor.is_done());
641
642        let mut cursor = FSMCursor::new(&root);
643        assert_eq!("t", cursor.advance('t').unwrap());
644        assert_eq!("e", cursor.advance('e').unwrap());
645        assert_eq!("s", cursor.advance('s').unwrap());
646        assert_eq!("a", cursor.advance('a').unwrap());
647        assert_eq!("t", cursor.advance('t').unwrap());
648        assert!(cursor.is_done());
649
650        let mut cursor = FSMCursor::new(&root);
651        assert_eq!("t", cursor.advance('t').unwrap());
652        assert_eq!("e", cursor.advance('e').unwrap());
653        assert_eq!("s", cursor.advance('s').unwrap());
654        assert_eq!("t", cursor.advance('t').unwrap());
655        assert!(cursor.is_done());
656    }
657
658    #[test]
659    fn test_optional2() {
660        let bnf = r"
661        t1 ::= 'te' t2 't';
662        t2 ::= ( 's' )?; 
663        ";
664        let root = frontend::create_graph_from_ebnf(bnf).unwrap();
665        let mut cursor = FSMCursor::new(&root);
666        assert_eq!("te", cursor.advance('t').unwrap());
667        assert_eq!("t", cursor.advance('t').unwrap());
668        assert!(cursor.is_done());
669        let mut cursor = FSMCursor::new(&root);
670        assert_eq!("te", cursor.advance('t').unwrap());
671        assert_eq!("s", cursor.advance('s').unwrap());
672        assert_eq!("t", cursor.advance('t').unwrap());
673        assert!(cursor.is_done());
674    }
675
676    // you are the bane of my existence. If I ever had the chance to erase
677    // something from the universe permanently, I would erase recursive bnf terminal definitions.
678    // There is no reason this is so incredibly hard to parse.
679    #[test]
680    fn test_sql() {
681        let bnf = r"
682        query ::= select | insert;
683        select ::= 'SELECT' '*' | collist 'FROM' #'^.*$' ';';
684        insert ::= 'INSERT INTO' #'^.*$' ' ' 'VALUES' '(' collist ')';
685        collist ::= col ( ',' collist )?;
686        col ::= #'^.*[, ]$';
687    ";
688        let root = frontend::create_graph_from_ebnf(bnf).unwrap();
689        root.borrow().dbg();
690        let mut cursor = FSMCursor::new(&root);
691        assert_eq!("SELECT", cursor.advance('S').unwrap());
692        assert_eq!(None, cursor.advance('a'));
693        assert_eq!(",", cursor.advance(',').unwrap());
694        assert_eq!(None, cursor.advance('b'));
695        cursor.advance(' ');
696        assert_eq!("FROM", cursor.advance('F').unwrap());
697        cursor.advance('a');
698        assert_eq!(";", cursor.advance(';').unwrap());
699        assert!(cursor.is_done());
700    }
701
702    #[test]
703    fn test_repeat() {
704        let bnf = r"
705        t1 ::= 't' { 'e' } 'st';
706    ";
707        let root = frontend::create_graph_from_ebnf(bnf).unwrap();
708        // >:3
709        for i in 0..=30 {
710            let mut cursor = FSMCursor::new(&root);
711            assert_eq!("t", cursor.advance('t').unwrap());
712            for _ in 0..i {
713                assert_eq!("e", cursor.advance('e').unwrap());
714            }
715            assert_eq!("st", cursor.advance('s').unwrap());
716            assert!(cursor.is_done());
717        }
718    }
719
720    #[test]
721    fn test_terminal() {
722        let terms: usize = 100;
723        let mut bnf = String::with_capacity(terms * 14);
724        for i in 1..terms {
725            bnf.push_str(&format!("t{i:0>3} ::= t{:0>3};\n", i + 1));
726        }
727        bnf.push_str(&format!("t{terms:0>3} ::= 't' 'st';"));
728        println!("{bnf}");
729        let root = frontend::create_graph_from_ebnf(&bnf).unwrap();
730        let mut cursor = FSMCursor::new(&root);
731        assert_eq!("t", cursor.advance('t').unwrap());
732        assert_eq!("st", cursor.advance('s').unwrap());
733        assert!(cursor.is_done());
734    }
735
736    fn util_check_str(root: &FSMRc<FSMLock<FSMNode>>, str: &str) {
737        let mut cursor = FSMCursor::new(root);
738        for char in str.chars() {
739            cursor.advance(char);
740        }
741        assert!(cursor.is_done())
742    }
743
744    #[test]
745    fn test_combi() {
746        let bnf = r"
747        t1 ::= ( 'u' | 'a' | 'o' ) { 'w' | 'v' } ( 'u' | 'a' | 'o' );
748    ";
749        let root = frontend::create_graph_from_ebnf(bnf).unwrap();
750        util_check_str(&root, "uwu");
751        util_check_str(&root, "owo");
752        util_check_str(&root, "owwwwwo");
753        util_check_str(&root, "owwwwwu");
754    }
755
756    #[test]
757    fn test_repeat_multiple() {
758        let bnf = r"
759        t1 ::= 't' t2 't';
760        t2 ::= 'oas' | ( 'e' { 'a' 's' } );
761    ";
762        let root = frontend::create_graph_from_ebnf(bnf).unwrap();
763        let mut cursor = FSMCursor::new(&root);
764        assert_eq!("t", cursor.advance('t').unwrap());
765        assert_eq!("oas", cursor.advance('o').unwrap());
766        assert_eq!("t", cursor.advance('t').unwrap());
767        assert!(cursor.is_done());
768
769        let mut cursor = FSMCursor::new(&root);
770        assert_eq!("t", cursor.advance('t').unwrap());
771        assert_eq!("e", cursor.advance('e').unwrap());
772        assert_eq!("a", cursor.advance('a').unwrap());
773        assert_eq!("s", cursor.advance('s').unwrap());
774        assert_eq!("a", cursor.advance('a').unwrap());
775        assert_eq!("s", cursor.advance('s').unwrap());
776        assert_eq!("t", cursor.advance('t').unwrap());
777        assert!(cursor.is_done());
778    }
779
780    #[test]
781    fn test_userdefs() {
782        let bnf = r"
783        t1 ::= ( #'[0-9]' 't' ) | ( #'[a-z]' 'e' );
784    ";
785        let root = frontend::create_graph_from_ebnf(bnf).unwrap();
786        let mut cursor = FSMCursor::new(&root);
787        assert_eq!(None, cursor.advance('1'));
788        assert_eq!("t", cursor.advance('t').unwrap());
789        assert!(cursor.is_done());
790
791        let mut cursor = FSMCursor::new(&root);
792        assert_eq!(None, cursor.advance('a'));
793        assert_eq!("e", cursor.advance('e').unwrap());
794        assert!(cursor.is_done());
795    }
796    fn test_minify() {
797        let root = FSMNode::new_null(None);
798        let child = FSMNode::new_null(Some(&root));
799        let child = FSMNode::new_keyword_with_parent("asdf".to_string(), child);
800        // minify
801        root.borrow().dbg();
802        FSMNode::minify(&root);
803        root.borrow().dbg();
804        assert_eq!(Null, root.borrow().value);
805        assert_eq!(
806            Keyword(Keyword::new("asdf".to_string(), None)),
807            root.borrow().children[0].borrow().value
808        );
809        assert_eq!(1, root.borrow().children.len())
810    }
811
812    #[test]
813    fn test_minify_multiple() {
814        let root = FSMNode::new_null(None);
815        let child = FSMNode::new_null(Some(&root));
816        let child = FSMNode::new_null(Some(&child));
817        let child = FSMNode::new_keyword_with_parent("asdf".to_string(), child);
818        // minify
819        root.borrow().dbg();
820        FSMNode::minify(&root);
821        root.borrow().dbg();
822        assert_eq!(Null, root.borrow().value);
823        assert_eq!(
824            Keyword(Keyword::new("asdf".to_string(), None)),
825            root.borrow().children[0].borrow().value
826        );
827        assert_eq!(1, root.borrow().children.len())
828    }
829
830    #[test]
831    fn test_minify_cycles() {
832        let root = FSMNode::new_null(None);
833        let child = FSMNode::new_null(Some(&root));
834        let child2 = FSMNode::new_null(Some(&child));
835        let child = FSMNode::new_keyword_with_parent("asdf".to_string(), child2.clone());
836        FSMNode::add_child_cycle_safe(&child, &child2);
837        FSMNode::minify(&root);
838
839        assert_eq!(Null, root.borrow().value);
840        assert_eq!(
841            Keyword(Keyword::new("asdf".to_string(), None)),
842            root.borrow().children[0].borrow().value
843        );
844        assert_eq!(1, root.borrow().children.len());
845        assert_eq!(1, root.borrow().children[0].borrow().children.len());
846    }
847
848    #[test]
849    fn test_userdef_links() {
850        let root = create_graph_from_ebnf(
851            r"
852     main ::= #'[0-9]+' ( ('-' 'test') | (';' 'uwu') );
853",
854        )
855        .unwrap();
856        let mut cursor = FSMCursor::new(&root);
857        for i in 0..=9 {
858            assert_eq!(None, cursor.advance(i.to_string().chars().nth(0).unwrap()));
859        }
860        let mut cursor2 = cursor.clone();
861        assert_eq!("-", cursor.advance('-').unwrap());
862        assert_eq!("test", cursor.advance('t').unwrap());
863        assert_eq!(";", cursor2.advance(';').unwrap());
864        assert_eq!("uwu", cursor2.advance('u').unwrap());
865        root.borrow().dbg();
866    }
867
868    #[test]
869    fn test_fancy_regex_usecase() {
870        let root = create_graph_from_ebnf(
871            r"
872     main ::= (#'[0-9]+' 'uwu') | (#'[a-z]' 'awa');
873",
874        )
875        .unwrap();
876        let mut cursor = FSMCursor::new(&root);
877        let mut cursor2 = cursor.clone();
878        assert_eq!(None, cursor.advance('0'));
879        assert_eq!("uwu", cursor.advance('u').unwrap());
880        assert_eq!(None, cursor2.advance('b'));
881        assert_eq!("awa", cursor2.advance('a').unwrap());
882        root.borrow().dbg();
883    }
884
885    #[test]
886    fn test_reset() {
887        let root = FSMNode::new_null(None);
888        let other = FSMNode::new_keyword_with_parent("int".to_string(), root.clone());
889        let _other = FSMNode::new_keyword_with_parent("asdf".to_string(), other.clone());
890        assert_eq!(root.borrow().children.len(), 1);
891        let mut cursor = FSMCursor::new(&root);
892        assert_eq!("int", cursor.advance('i').unwrap());
893        assert_eq!(None, cursor.advance('i'));
894        cursor.reset();
895        assert_eq!("int", cursor.advance('i').unwrap());
896    }
897
898    #[test]
899    fn test_revert() {
900        let root = FSMNode::new_null(None);
901        let other = FSMNode::new_keyword_with_parent("int".to_string(), root.clone());
902        let _other = FSMNode::new_keyword_with_parent("asdf".to_string(), other.clone());
903        let mut cursor = FSMCursor::new(&root);
904
905        assert_eq!("int", cursor.advance('i').unwrap());
906        assert_eq!("asdf", cursor.advance('a').unwrap());
907        cursor.revert();
908        assert_eq!("asdf", cursor.advance('a').unwrap());
909    }
910
911    #[test]
912    fn test_dead_end_prevention() {
913        let root = FSMNode::new_null(None);
914        let other = FSMNode::new_keyword_with_parent("int".to_string(), root.clone());
915        let _other = FSMNode::new_keyword_with_parent("asdf".to_string(), other.clone());
916        let mut cursor = FSMCursor::new(&root);
917
918        assert_eq!("int", cursor.advance('i').unwrap());
919        assert_eq!(None, cursor.advance('i'));
920        assert_eq!(None, cursor.advance('?'));
921        assert_eq!("asdf", cursor.advance('a').unwrap());
922    }
923    #[test]
924    fn test_dead_end_prevention_userdef() {
925        let ebnf = r"
926        t1 ::= ( #'[0-9]' 'asdf' ) | ( #'[a-z]' 'test' );
927        ";
928        let root = create_graph_from_ebnf(ebnf).unwrap();
929        let mut cursor = FSMCursor::new(&root);
930
931        assert_eq!(None, cursor.advance('0'));
932        assert_eq!("asdf", cursor.advance('a').unwrap());
933        cursor.reset();
934        assert_eq!(None, cursor.advance('a'));
935        assert_eq!("test", cursor.advance('t').unwrap());
936        cursor.reset();
937        assert_eq!(None, cursor.advance('A'));
938        assert_eq!(None, cursor.advance('B'));
939        assert_eq!(None, cursor.advance('!'));
940
941        assert_eq!(None, cursor.advance('a'));
942        assert_eq!("test", cursor.advance('t').unwrap());
943    }
944}
lib/lib.rs

lib/
lib.rs
