lib/
lib.rs

1#![feature(let_chains)]
2#![feature(if_let_guard)]
3
4use std::cell::RefCell;
5use std::collections::{HashMap, HashSet};
6use std::rc::{Rc, Weak};
7
8pub mod frontend;
9
10static mut CNT: usize = 0;
11fn get_id() -> usize {
12    let ret;
13    unsafe {
14        ret = CNT;
15        CNT += 1;
16    }
17    return ret;
18}
19
20// ironic that this only expands names
21struct NameShortener;
22impl NameShortener {
23    fn expand(old: Option<&str>, full: &str) -> String {
24        if full.is_empty() {
25            panic!("Cannot expand the void!")
26        }
27        let ret = if let Some(old) = old {
28            if old == full {
29                return old.to_string(); // FIXME: this can't be a good handling
30            }
31            if full.len() < old.len() {
32                panic!("NS: There is nothing left...")
33            }
34            let mut ret = old.to_string();
35            ret.push_str(&full[old.len()..old.len() + 1]);
36            ret
37        } else {
38            full[0..1].to_string()
39        };
40        debug_println!("Got {} instead of {old:?}", ret);
41        ret
42    }
43}
44
45#[derive(Debug, Clone, PartialEq)]
46pub struct Keyword {
47    short: String,
48    expanded: String,
49    closing_token: Option<String>,
50}
51
52impl Keyword {
53    pub fn new(expanded: String, closing_token: Option<String>) -> Self {
54        Self {
55            short: expanded.chars().nth(0).unwrap().to_string(),
56            expanded,
57            closing_token,
58        }
59    }
60}
61
62impl Default for Keyword {
63    fn default() -> Self {
64        Self {
65            short: String::new(),
66            expanded: String::new(),
67            closing_token: None,
68        }
69    }
70}
71
72// TODO: combine UserDefined and UserDefinedRegex into one variant
73#[derive(Debug, Clone)]
74pub enum NodeType {
75    Keyword(Keyword),
76    UserDefined { final_chars: Vec<char> },
77    UserDefinedRegex(Regex),
78    Null,
79}
80
81impl PartialEq for NodeType {
82    fn eq(&self, other: &Self) -> bool {
83        match self {
84            Keyword(k) => match other {
85                Keyword(k2) => k.eq(k2),
86                _ => false,
87            },
88            UserDefined { final_chars: fc } => match other {
89                UserDefined { final_chars: fc2 } => fc.eq(fc2),
90                _ => false,
91            },
92            UserDefinedRegex(r) => match other {
93                UserDefinedRegex(r2) => r.as_str().eq(r2.as_str()),
94                _ => false,
95            },
96            Null => match other {
97                Null => true,
98                _ => false,
99            },
100        }
101    }
102    fn ne(&self, other: &Self) -> bool {
103        !self.eq(other)
104    }
105}
106
107trait PartialMatch {
108    fn partial_match(&self, hay: &str) -> bool;
109}
110
111impl PartialMatch for Regex {
112    /**
113    not a perfect solution and should therefore be never used
114    **/
115    fn partial_match(&self, hay: &str) -> bool {
116        let orig = self.as_str();
117        for i in 1..orig.len() {
118            if let Ok(regex) = Regex::new(&orig[0..=i])
119                && regex.is_match(hay)
120            {
121                return true;
122            }
123        }
124        false
125    }
126}
127
128use NodeType::*;
129use debug_print::debug_println;
130use regex::Regex;
131
132#[derive(Debug, Clone, PartialEq)]
133pub struct NodeValue {
134    pub ntype: NodeType,
135    pub is_done: bool,
136}
137
138type NodeId = usize;
139#[derive(Debug, Clone, PartialEq)]
140pub struct FSMNode {
141    id: NodeId,
142    is_done: bool,
143    value: NodeType,
144    parent: Option<Rc<RefCell<FSMNode>>>,
145    children: Vec<Rc<RefCell<FSMNode>>>,
146}
147
148impl Default for FSMNode {
149    fn default() -> Self {
150        Self {
151            id: get_id(),
152            is_done: false,
153            value: Null,
154            parent: None,
155            children: Vec::new(),
156        }
157    }
158}
159
160impl FSMNode {
161    pub fn is_null(&self) -> bool {
162        if let Null = self.value { true } else { false }
163    }
164    fn deep_clone_internal(
165        stub: &Rc<RefCell<Self>>,
166        old: &FSMNode,
167        visited_nodes: &mut HashMap<usize, Rc<RefCell<FSMNode>>>,
168    ) -> Rc<RefCell<Self>> {
169        for child in &old.children {
170            if !visited_nodes.contains_key(&child.borrow().id) {
171                let clone = Rc::new(RefCell::new(Self {
172                    value: child.borrow().value.clone(),
173                    ..Default::default()
174                }));
175                visited_nodes.insert(child.borrow().id, clone.clone());
176                FSMNode::deep_clone_internal(&clone, &child.borrow(), visited_nodes);
177                stub.borrow_mut().children.push(clone);
178            } else {
179                stub.borrow_mut()
180                    .children
181                    .push(visited_nodes.get(&child.borrow().id).unwrap().clone());
182            }
183        }
184        stub.clone()
185    }
186    fn deep_clone(&self) -> Rc<RefCell<Self>> {
187        debug_println!("Deep cloning node {}", self.short_id());
188        let ret = Rc::new(RefCell::new(Self {
189            value: self.value.clone(),
190            ..Default::default()
191        }));
192        let mut visited_nodes = HashMap::new();
193        visited_nodes.insert(self.id, ret.clone());
194        let ret = FSMNode::deep_clone_internal(&ret, self, &mut visited_nodes);
195        debug_println!("Finish deep clone:");
196        ret.borrow().dbg();
197        ret
198    }
199    fn has_direct_child(&self, id: usize) -> bool {
200        self.children.iter().find(|c| c.borrow().id == id).is_some()
201    }
202    pub fn node_cnt(this: &Rc<RefCell<FSMNode>>) -> usize {
203        let mut ret = 1; // one root node
204        FSMNode::util_walk_fsm_cycle_aware(
205            this,
206            &mut |_, parent, _, _| {
207                ret += parent.borrow().children.len();
208                false
209            },
210            true,
211        );
212        ret
213    }
214    fn get_direct_child_dups(&self) -> Vec<usize> {
215        let mut ids = HashSet::new();
216        let mut ret = Vec::new();
217        self.children.iter().enumerate().for_each(|(i, c)| {
218            if ids.contains(&c.borrow().id) {
219                ret.push(i);
220            } else {
221                ids.insert(c.borrow().id);
222            }
223        });
224        ret
225    }
226    fn minify(this: &Rc<RefCell<FSMNode>>) {
227        debug_println!("before minify:");
228        this.borrow().dbg();
229        let mut cycle_translation_table = HashMap::new();
230        FSMNode::util_walk_fsm_cycle_aware(
231            this,
232            &mut |_, parent, child, childidx| {
233                // TODO: figure out why the parent check needs to be here
234                if parent.borrow().is_null()
235                    && child.borrow().is_null()
236                    && parent.borrow().children.len() == 1
237                {
238                    cycle_translation_table.insert(child.borrow().id, parent.clone());
239                    parent.borrow_mut().children.remove(*childidx as usize);
240                    for child in &child.borrow().children {
241                        debug_println!("CID: {}", child.borrow().short_id());
242                        if child.borrow().id == parent.borrow().id
243                            || parent.borrow().has_direct_child(child.borrow().id)
244                        {
245                            continue;
246                        }
247                        parent.borrow_mut().children.push(child.clone());
248                    }
249                    child.borrow_mut().children.clear();
250                    *childidx -= 1;
251                }
252                let pborrow = parent.borrow();
253                let dup_idxs = pborrow.get_direct_child_dups();
254                drop(pborrow);
255                dup_idxs.iter().for_each(|ci| {
256                    parent.borrow_mut().children.remove(*ci);
257                });
258                false
259            },
260            true,
261        );
262        // fix any broken pointers the last op may have created
263        FSMNode::util_walk_fsm_cycle_aware(
264            this,
265            &mut |_, parent, child, childidx| {
266                if let Some(new_child) = cycle_translation_table.get(&child.borrow().id) {
267                    if new_child.borrow().id == parent.borrow().id
268                        || parent.borrow().has_direct_child(new_child.borrow().id)
269                    {
270                        parent.borrow_mut().children.remove(*childidx as usize);
271                        return false;
272                    }
273                    parent.borrow_mut().children[*childidx as usize] = new_child.clone();
274                }
275                false
276            },
277            true,
278        );
279        debug_println!("after minify:");
280        this.borrow().dbg();
281    }
282    fn util_walk_fsm_cycle_aware(
283        this: &Rc<RefCell<FSMNode>>,
284        op: &mut impl FnMut(
285            &mut HashSet<usize>,
286            &Rc<RefCell<FSMNode>>,
287            &Rc<RefCell<FSMNode>>,
288            &mut isize,
289        ) -> bool,
290        greedy: bool,
291    ) -> Option<Rc<RefCell<FSMNode>>> {
292        let mut visisted_nodes = HashSet::new();
293        visisted_nodes.insert(this.borrow().id);
294        FSMNode::util_walk_fsm_cycle_aware_internal(this, op, &mut visisted_nodes, greedy)
295    }
296    fn util_walk_fsm_cycle_aware_internal(
297        this: &Rc<RefCell<FSMNode>>,
298        op: &mut impl FnMut(
299            &mut HashSet<usize>,
300            &Rc<RefCell<FSMNode>>,
301            &Rc<RefCell<FSMNode>>,
302            &mut isize,
303        ) -> bool,
304        visited_nodes: &mut HashSet<usize>,
305        greedy: bool,
306    ) -> Option<Rc<RefCell<FSMNode>>> {
307        // don't like this
308        let children = this.borrow().children.clone();
309        let mut c_idx = 0;
310        for child in children.iter() {
311            if !visited_nodes.contains(&child.borrow().id) {
312                visited_nodes.insert(child.borrow().id);
313                // TODO: make this configurable whether to do breadth/depth
314                if (greedy || child.borrow().is_null())
315                    && let Some(child) = FSMNode::util_walk_fsm_cycle_aware_internal(
316                        &child,
317                        op,
318                        visited_nodes,
319                        greedy,
320                    )
321                {
322                    return Some(child);
323                }
324                if op(visited_nodes, &this, &child, &mut c_idx) {
325                    return Some(child.clone());
326                }
327            }
328            c_idx += 1;
329        }
330        None
331    }
332    #[deprecated]
333    fn do_stuff_cycle_aware(
334        &self,
335        op: &mut impl FnMut(&mut HashSet<usize>, &FSMNode, Rc<RefCell<FSMNode>>) -> bool,
336    ) -> Option<Rc<RefCell<FSMNode>>> {
337        let mut visited_nodes = HashSet::new();
338        visited_nodes.insert(self.id);
339        self.do_stuff_cycle_aware_internal(op, &mut visited_nodes)
340    }
341    fn do_stuff_cycle_aware_internal(
342        &self,
343        op: &mut impl FnMut(&mut HashSet<usize>, &FSMNode, Rc<RefCell<FSMNode>>) -> bool,
344        visited_nodes: &mut HashSet<usize>,
345    ) -> Option<Rc<RefCell<FSMNode>>> {
346        for child in &self.children {
347            if !visited_nodes.contains(&child.borrow().id) {
348                visited_nodes.insert(child.borrow().id);
349                if op(visited_nodes, self, child.clone()) {
350                    return Some(child.clone());
351                }
352                if let Some(child) = child
353                    .borrow()
354                    .do_stuff_cycle_aware_internal(op, visited_nodes)
355                {
356                    return Some(child);
357                }
358            }
359        }
360        None
361    }
362
363    fn do_stuff_cycle_aware_non_greedy(
364        &self,
365        op: &mut impl FnMut(Rc<RefCell<FSMNode>>) -> bool,
366    ) -> Option<Rc<RefCell<FSMNode>>> {
367        // TODO: figure out why this breaks things when you start the hashset off with the id of
368        // self
369        self.do_stuff_cycle_aware_non_greedy_internal(op, &mut HashSet::new())
370    }
371    fn do_stuff_cycle_aware_non_greedy_internal(
372        &self,
373        op: &mut impl FnMut(Rc<RefCell<FSMNode>>) -> bool,
374        visited_nodes: &mut HashSet<usize>,
375    ) -> Option<Rc<RefCell<FSMNode>>> {
376        for child in &self.children {
377            if !visited_nodes.contains(&child.borrow().id) {
378                visited_nodes.insert(child.borrow().id);
379                if op(child.clone()) {
380                    return Some(child.clone());
381                }
382                if let Null = child.borrow().value
383                    && let Some(ret) = child
384                        .borrow()
385                        .do_stuff_cycle_aware_non_greedy_internal(op, visited_nodes)
386                {
387                    return Some(ret);
388                }
389            }
390        }
391        None
392    }
393    fn has_useful_children(&self) -> bool {
394        self.do_stuff_cycle_aware(&mut |_, _, c| match c.borrow().value {
395            Null => false,
396            _ => true,
397        })
398        .is_some()
399    }
400
401    pub fn get_last_child(&self) -> Option<Rc<RefCell<FSMNode>>> {
402        self.children.last().cloned()
403    }
404    pub fn add_child(&mut self, child: &Rc<RefCell<FSMNode>>) {
405        while self.handle_potential_conflict(child) {}
406        self.children.push(Rc::clone(&child));
407    }
408    pub fn add_child_cycle_safe(this: &Rc<RefCell<FSMNode>>, child: &Rc<RefCell<FSMNode>>) {
409        while this.borrow().handle_potential_conflict(child) {}
410        this.borrow_mut().children.push(Rc::clone(&child));
411    }
412    pub fn new_null(parent: Option<&Rc<RefCell<FSMNode>>>) -> Rc<RefCell<Self>> {
413        let parent_ref = if let Some(parent) = parent {
414            Some(Rc::clone(parent))
415        } else {
416            None
417        };
418        let ret = Rc::new(RefCell::new(Self {
419            value: Null,
420            parent: parent_ref,
421            children: Vec::new(),
422            ..Default::default()
423        }));
424        if let Some(parent) = parent {
425            parent.borrow_mut().add_child(&ret);
426        }
427        ret
428    }
429
430    fn short_id(&self) -> String {
431        format!("{:#x}", self.id)
432    }
433
434    fn dbg_internal(&self, indent: usize, visited_nodes: &mut HashSet<usize>) {
435        println!("{}{:?} {}", " ".repeat(indent), self.value, self.short_id());
436        visited_nodes.insert(self.id);
437        for child in self.children.iter() {
438            if !visited_nodes.contains(&child.borrow().id) {
439                child.borrow().dbg_internal(indent + 4, visited_nodes);
440            } else {
441                println!(
442                    "{}Cycle to {}",
443                    " ".repeat(indent + 4),
444                    child.borrow().short_id()
445                );
446            }
447        }
448    }
449    fn get_all_leaves(&self, discovered_leaves: &mut Vec<Rc<RefCell<FSMNode>>>) {
450        self.do_stuff_cycle_aware(&mut |visited_nodes, _, child| {
451            if discovered_leaves
452                .iter()
453                .find(|dl| dl.borrow().id == child.borrow().id)
454                .is_some()
455            {
456                return false;
457            }
458            if child.borrow().children.is_empty() {
459                debug_println!(
460                    "adding node {:?} {}",
461                    child.borrow().value,
462                    child.borrow().short_id()
463                );
464                discovered_leaves.push(child.clone());
465            } else {
466                let mut has_only_cycles = true;
467                for child in &child.borrow().children {
468                    if !visited_nodes.contains(&child.borrow().id) {
469                        has_only_cycles = false;
470                        break;
471                    }
472                }
473                if has_only_cycles {
474                    debug_println!(
475                        "adding node {:?} {}",
476                        child.borrow().value,
477                        child.borrow().short_id()
478                    );
479                    discovered_leaves.push(child.clone());
480                }
481            }
482            false
483        });
484    }
485    pub fn add_child_to_all_leaves(this: &Rc<RefCell<FSMNode>>, child: &Rc<RefCell<FSMNode>>) {
486        let mut leaves = Vec::new();
487        this.borrow().get_all_leaves(&mut leaves);
488        while let Some(node) = leaves.pop() {
489            FSMNode::add_child_cycle_safe(&node, child);
490            // NOTE: hopefully this isn't needed anymore
491            // if node.borrow().children.is_empty() {
492            //     FSMNode::add_child_cycle_safe(&node, child);
493            // }
494        }
495        if this.borrow().children.is_empty() {
496            FSMNode::add_child_cycle_safe(&this, child);
497        }
498    }
499
500    pub fn race_to_leaf(&self) -> Option<Rc<RefCell<FSMNode>>> {
501        self.do_stuff_cycle_aware(&mut |visited_nodes, _, child| {
502            let mut ret = true;
503            // avoid going back to a node previously visited so do_stuff_cycle_aware doesn't return
504            // a false negative
505            for child in &child.borrow().children {
506                if !visited_nodes.contains(&child.borrow().id) {
507                    ret = false;
508                    break;
509                }
510            }
511            ret
512        })
513    }
514    pub fn dbg(&self) {
515        #[cfg(debug_assertions)]
516        self.dbg_internal(0, &mut HashSet::new());
517    }
518
519    pub fn new(value: NodeType, parent: &Rc<RefCell<FSMNode>>) -> Rc<RefCell<Self>> {
520        let ret = Rc::new(RefCell::new(Self {
521            value,
522            parent: Some(Rc::clone(parent)),
523            children: Vec::new(),
524            ..Default::default()
525        }));
526        parent.borrow_mut().add_child(&ret);
527        ret
528    }
529
530    pub fn new_required(value: NodeType, parent: &Rc<RefCell<FSMNode>>) -> Rc<RefCell<Self>> {
531        let ret = Rc::new(RefCell::new(Self {
532            value,
533            parent: Some(Rc::clone(parent)),
534            children: Vec::new(),
535            ..Default::default()
536        }));
537        parent.borrow_mut().add_child(&ret);
538        ret
539    }
540
541    pub fn new_keyword(expanded_name: String) -> Rc<RefCell<Self>> {
542        Rc::new(RefCell::new(Self {
543            value: Keyword(Keyword {
544                short: expanded_name.chars().nth(0).unwrap().to_string(),
545                expanded: expanded_name,
546                ..Default::default()
547            }),
548            parent: None,
549            children: Vec::new(),
550            ..Default::default()
551        }))
552    }
553
554    pub fn new_keyword_with_parent(
555        expanded_name: String,
556        parent: Rc<RefCell<FSMNode>>,
557    ) -> Rc<RefCell<Self>> {
558        let ret = Self::new_keyword(expanded_name);
559        ret.borrow_mut().parent = Some(Rc::clone(&parent));
560        FSMNode::add_child_cycle_safe(&parent, &ret);
561        ret
562    }
563    fn find_node_with_code(&self, short: &str) -> Option<Rc<RefCell<FSMNode>>> {
564        for child in &self.children {
565            if let Keyword(Keyword { short: nshort, .. }) = &child.borrow().value
566                && nshort == short
567            {
568                return Some(Rc::clone(&child));
569            }
570        }
571        for child in &self.children {
572            let rec_res = child.borrow().find_node_with_code(short);
573            if rec_res.is_some() {
574                return rec_res;
575            }
576        }
577        None
578    }
579
580    fn check_for_conflicts(&self, short: &str) -> bool {
581        for child in &self.children {
582            let borrow = child.borrow();
583            match &borrow.value {
584                Keyword(Keyword { short: nshort, .. }) if nshort == short => return true,
585                Null => {
586                    let rec_res = borrow.check_for_conflicts(short);
587                    if rec_res {
588                        return true;
589                    }
590                }
591                _ => {}
592            }
593        }
594        false
595    }
596
597    fn get_conflicting_node(&self, short: &str) -> Option<Rc<RefCell<FSMNode>>> {
598        self.do_stuff_cycle_aware_non_greedy(&mut |child: Rc<RefCell<FSMNode>>| {
599            println!("awa?");
600            match &child.borrow().value {
601                Keyword(Keyword { short: nshort, .. }) if short.starts_with(nshort) => {
602                    return true;
603                }
604                _ => false,
605            }
606        })
607    }
608    fn handle_potential_conflict_internal(&self, child: &Rc<RefCell<FSMNode>>) -> bool {
609        let child_borrow = child.borrow();
610        let mut ret = false;
611        if let Keyword(Keyword { short: cshort, .. }) = &child_borrow.value {
612            if let Some(node) = self.get_conflicting_node(cshort)
613                && node.borrow().value != child_borrow.value
614            {
615                node.replace_with(|node| {
616                    if let Keyword(keyword_struct) = &mut node.value {
617                        let new_short = NameShortener::expand(
618                            Some(&keyword_struct.short),
619                            &keyword_struct.expanded,
620                        );
621                        keyword_struct.short = new_short;
622                        debug_println!("conflict handler 2");
623                        ret = true;
624                        node.to_owned()
625                    } else {
626                        panic!(
627                            "What?! We got a non-keyword node from the get_conflicting_node fn! Anyways, I'm gonna snuggle some foxxos now..."
628                        )
629                    }
630                });
631            }
632        }
633        ret
634    }
635    pub fn handle_potential_conflict(&self, child: &Rc<RefCell<FSMNode>>) -> bool {
636        let child_borrow = child.borrow();
637        if let Keyword(keyword_struct) = &child_borrow.value {
638            debug_println!("{:?}", self.value);
639            debug_println!("{:?}", child.borrow().value);
640            if self.handle_potential_conflict_internal(child) {
641                let short =
642                    NameShortener::expand(Some(&keyword_struct.short), &keyword_struct.expanded);
643                drop(child_borrow);
644                child.replace_with(|node| {
645                    if let Keyword(k) = &mut node.value {
646                        k.short = short;
647                    } else {
648                        unreachable!()
649                    }
650                    node.to_owned()
651                });
652                return true;
653            }
654        } else if let Null = &child_borrow.value {
655            // println!("awa?");
656            let mut ret = false;
657            let mut visited_nodes = HashSet::new();
658            // iterate over every child and return true if at least one had a conflict
659            for child in &child_borrow.children {
660                if !visited_nodes.contains(&child.borrow().id) {
661                    visited_nodes.insert(child.borrow().id);
662                    if self.handle_potential_conflict_internal(&child) {
663                        let mut mut_child = child.borrow_mut();
664                        if let Keyword(k) = &mut mut_child.value {
665                            k.short = NameShortener::expand(Some(&k.short), &k.expanded);
666                        }
667                        ret = true;
668                    }
669                }
670            }
671            if ret {
672                return true;
673            }
674        }
675        false
676    }
677    pub fn dump_children(&self) {
678        self.children
679            .iter()
680            .for_each(|child| println!("{:?}", child.borrow().value));
681    }
682}
683
684type InternalCursor = Weak<RefCell<FSMNode>>;
685pub struct FSMCursor {
686    cur_ast_pos: InternalCursor,
687    input_buf: String,
688    unfinished_nodes: Vec<InternalCursor>,
689}
690
691impl FSMCursor {
692    pub fn new(fsm_root: &Rc<RefCell<FSMNode>>) -> Self {
693        Self {
694            cur_ast_pos: Rc::downgrade(fsm_root),
695            input_buf: String::new(),
696            unfinished_nodes: Vec::new(),
697        }
698    }
699    fn handle_userdefined(&mut self, input: char, final_chars: &Vec<char>) -> Option<String> {
700        let child_idx = final_chars.iter().position(|char| *char == input);
701        if let Some(child_idx) = child_idx {
702            let strong_ref = self.get_cur_ast_binding();
703            let borrow = strong_ref.borrow();
704            let next_node = Rc::clone(&borrow.children[child_idx]);
705            self.update_cursor(&next_node);
706            let ret = if let NodeType::Keyword(Keyword {
707                short,
708                expanded,
709                closing_token: None,
710                ..
711            }) = &next_node.borrow().value
712                && *short == String::from(input)
713            {
714                Some(expanded.clone())
715            } else {
716                Some(String::from(final_chars[child_idx]))
717            };
718            self.input_buf.clear();
719            ret
720        } else {
721            None
722        }
723    }
724    pub fn clear_inputbuf(&mut self) {
725        self.input_buf.clear();
726    }
727    fn search_for_userdefs(&self, treenode: &Rc<RefCell<FSMNode>>) -> Option<Rc<RefCell<FSMNode>>> {
728        treenode.borrow().do_stuff_cycle_aware_non_greedy(
729            &mut |child| match &child.borrow().value {
730                UserDefined { .. } => true,
731                UserDefinedRegex(regex) if regex.partial_match(&self.input_buf) => true,
732                _ => false,
733            },
734        )
735    }
736    pub fn search_rec(&self, treenode: &Rc<RefCell<FSMNode>>) -> Option<Rc<RefCell<FSMNode>>> {
737        self.search_rec_internal(treenode, false)
738    }
739    pub fn search_rec_internal(
740        &self,
741        treenode: &Rc<RefCell<FSMNode>>,
742        best_effort: bool,
743    ) -> Option<Rc<RefCell<FSMNode>>> {
744        debug_println!(
745            "search_rec at {:?} {}",
746            treenode.borrow().value,
747            treenode.borrow().short_id()
748        );
749        let mut keyword_match = None;
750        let mut potential_matches = 0;
751        let mut visited_keywords = 0;
752        let mut last_keyword = None;
753        treenode
754            .borrow()
755            .do_stuff_cycle_aware_non_greedy(&mut |child| {
756                let node_val = &child.borrow().value;
757                debug_println!(
758                    "search_rec closure at {:?} {}",
759                    child.borrow().value,
760                    child.borrow().short_id()
761                );
762                match node_val {
763                    NodeType::Keyword(Keyword { short, .. }) => {
764                        if short.starts_with(&self.input_buf) {
765                            debug_println!("{:?}", child.borrow().value);
766                            debug_println!("{short} == {}", self.input_buf);
767                            keyword_match = Some(child.clone());
768                            potential_matches += 1;
769                            potential_matches > 1
770                        } else {
771                            // bandaid logic
772                            visited_keywords += 1;
773                            if visited_keywords == 1 {
774                                last_keyword = Some(child.clone());
775                            }
776                            false
777                        }
778                    }
779                    _ => false,
780                }
781            });
782        debug_println!("pm: {potential_matches}");
783        if keyword_match.is_some() && potential_matches == 1 {
784            return keyword_match;
785        }
786
787        debug_println!("vk: {visited_keywords}");
788        if visited_keywords == 1 && best_effort {
789            // probably what the user wants
790            return last_keyword;
791        }
792
793        let userdef_match = self.search_for_userdefs(treenode);
794        if userdef_match.is_some() {
795            return userdef_match;
796        }
797        None
798    }
799    pub fn advance(&mut self, input: char) -> Option<String> {
800        let binding = self.get_cur_ast_binding();
801        let borrow = binding.borrow();
802        debug_println!(
803            "advance with cursor {:?} {}",
804            borrow.value,
805            borrow.short_id()
806        );
807        self.input_buf.push(input);
808        // TODO: refactor
809        if borrow.is_done {
810            let res = self.search_rec(&binding);
811            if let Some(node) = res {
812                self.update_cursor(&node);
813                return match &node.borrow().value {
814                    NodeType::Keyword(Keyword { expanded, .. }) => {
815                        self.input_buf.clear();
816                        Some(expanded.clone())
817                    }
818                    NodeType::UserDefined { final_chars } => {
819                        let res = self.handle_userdefined(input, &final_chars);
820                        res
821                    }
822                    NodeType::UserDefinedRegex(_) => None,
823                    _ => unreachable!(),
824                };
825            }
826        }
827        match &borrow.value {
828            NodeType::UserDefined { final_chars, .. } => {
829                let res = self.handle_userdefined(input, final_chars);
830                if res.is_some() {
831                    return res;
832                }
833            }
834            NodeType::UserDefinedRegex(r) => {
835                debug_println!("Checking regex against '{}'", &self.input_buf);
836                if r.is_match(&self.input_buf) {
837                    drop(borrow);
838                    binding.borrow_mut().is_done = true;
839                    self.input_buf.clear();
840                    self.input_buf.push(input);
841                    let next_node = self.search_rec_internal(&binding, true);
842                    if next_node.is_none() {
843                        debug_println!("No node found");
844                        self.input_buf.clear();
845                        return Some(input.to_string());
846                    }
847                    let next_node = next_node.unwrap();
848                    self.update_cursor(&next_node);
849                    let ret = if let NodeType::Keyword(Keyword {
850                        short,
851                        expanded,
852                        closing_token: None,
853                        ..
854                    }) = &next_node.borrow().value
855                    {
856                        if short.starts_with(input) {
857                            Some(expanded.clone())
858                        } else {
859                            // FIXME: this is terrible logic
860                            if let Some(next_node) = self.search_rec_internal(&next_node, true) {
861                                self.update_cursor(&next_node);
862                                if let Keyword(Keyword {
863                                    expanded,
864                                    closing_token: None,
865                                    ..
866                                }) = &next_node.borrow().value
867                                // && short.starts_with(input)
868                                {
869                                    Some(expanded.clone())
870                                } else {
871                                    Some(input.to_string())
872                                }
873                            } else {
874                                Some(input.to_string())
875                            }
876                        }
877                    } else {
878                        Some(input.to_string())
879                    };
880                    self.input_buf.clear();
881                    return ret;
882                }
883            }
884            _ => {
885                let res = self.search_rec(&binding);
886                if let Some(node) = res {
887                    self.update_cursor(&node);
888                    return match &node.borrow().value {
889                        NodeType::Keyword(Keyword { expanded, .. }) => {
890                            self.input_buf.clear();
891                            Some(expanded.clone())
892                        }
893                        NodeType::UserDefined { final_chars } => {
894                            let res = self.handle_userdefined(input, &final_chars);
895                            res
896                        }
897                        NodeType::UserDefinedRegex(_) => None,
898                        _ => unreachable!(),
899                    };
900                }
901            }
902        }
903        None
904    }
905
906    fn update_cursor(&mut self, node: &Rc<RefCell<FSMNode>>) {
907        self.cur_ast_pos = Rc::downgrade(&Rc::clone(&node));
908        if let NodeType::Keyword(Keyword {
909            closing_token: Some(_),
910            ..
911        }) = &node.borrow().value
912        {
913            self.unfinished_nodes.push(Rc::downgrade(&node));
914        } else if node.borrow().children.is_empty() && self.unfinished_nodes.len() > 1 {
915            // we don't need to jump back if only one remains
916            self.cur_ast_pos = self.unfinished_nodes.pop().unwrap();
917        }
918        debug_println!(
919            "uc: {:?} {}",
920            self.get_cur_ast_binding().borrow().value,
921            self.get_cur_ast_binding().borrow().id
922        );
923    }
924    fn dump(&self) {
925        println!(
926            "Last matched node: {:?}",
927            self.cur_ast_pos.upgrade().unwrap().borrow().value
928        );
929        println!("Input buf: {}", self.input_buf);
930    }
931
932    pub fn is_done(&self) -> bool {
933        let ast_ref = self.cur_ast_pos.upgrade().unwrap();
934        let binding = ast_ref.borrow();
935        match binding.value {
936            UserDefinedRegex(..) | UserDefined { .. } if !binding.is_done => false,
937            _ => binding.children.is_empty() || !binding.has_useful_children(),
938        }
939    }
940
941    fn get_cur_ast_binding(&self) -> Rc<RefCell<FSMNode>> {
942        self.cur_ast_pos.upgrade().unwrap()
943    }
944    pub fn is_in_userdefined_stage(&self) -> bool {
945        match self.get_cur_ast_binding().borrow().value {
946            NodeType::UserDefined { .. } | NodeType::UserDefinedRegex(..) => true,
947            _ => false,
948        }
949    }
950
951    fn get_current_nodeval(&self) -> NodeType {
952        println!("{}", self.get_cur_ast_binding().borrow().id);
953        self.get_cur_ast_binding().borrow().value.clone()
954    }
955    fn find_node_with_code(&self, short: &str) -> Option<Rc<RefCell<FSMNode>>> {
956        let binding = self.get_cur_ast_binding();
957        let binding = binding.borrow();
958        binding.find_node_with_code(short)
959    }
960}
961
962#[cfg(test)]
963mod tests {
964    use super::*;
965
966    #[test]
967    fn simple_tree() {
968        let root = FSMNode::new_keyword("int".to_string());
969        let _other = FSMNode::new_keyword_with_parent("asdf".to_string(), root.clone());
970        assert_eq!(root.borrow().children.len(), 1);
971    }
972
973    #[test]
974    fn simple_cursor_steps() {
975        let root = FSMNode::new_null(None);
976        let second = FSMNode::new_keyword_with_parent("int".to_string(), root.clone());
977        FSMNode::new_keyword_with_parent("asdf".to_string(), second.clone());
978        let mut cursor = FSMCursor::new(&root);
979        assert_eq!(cursor.get_current_nodeval(), Null);
980        cursor.advance('i').unwrap();
981        assert_eq!(
982            cursor.get_current_nodeval(),
983            NodeType::Keyword(Keyword::new("int".to_string(), None)),
984        );
985        cursor.advance('a').unwrap();
986        assert_eq!(
987            cursor.get_current_nodeval(),
988            NodeType::Keyword(Keyword::new("asdf".to_string(), None)),
989        );
990    }
991
992    #[test]
993    fn test_conflict_check() {
994        let root = FSMNode::new_null(None);
995        let mut sign_token = NodeType::Keyword(Keyword::new("unsigned".to_string(), None));
996        let child = FSMNode::new(sign_token.clone(), &root);
997        sign_token = NodeType::Keyword(Keyword::new("signed".to_string(), None));
998
999        let child2 = FSMNode::new(sign_token, &root);
1000        let types = FSMNode::new_required(NodeType::Null, &child);
1001
1002        let int = FSMNode::new_keyword_with_parent("int".to_string(), types.clone());
1003        let float = FSMNode::new_keyword_with_parent("short".to_string(), types.clone());
1004        child.borrow_mut().add_child(&types);
1005        child2.borrow_mut().add_child(&types);
1006
1007        assert!(root.borrow().check_for_conflicts("s"));
1008        assert!(child2.borrow().check_for_conflicts("s"));
1009        assert!(types.borrow().check_for_conflicts("s"));
1010        assert!(!int.borrow().check_for_conflicts("s"));
1011    }
1012
1013    #[test]
1014    fn test_keyword_matching() {
1015        let root = FSMNode::new_null(None);
1016        let mut sign_token = NodeType::Keyword(Keyword::new("unsigned".to_string(), None));
1017        let child = FSMNode::new(sign_token.clone(), &root);
1018        sign_token = NodeType::Keyword(Keyword::new("signed".to_string(), None));
1019
1020        let child2 = FSMNode::new(sign_token, &root);
1021        let types = FSMNode::new_required(NodeType::Null, &child);
1022
1023        let int = FSMNode::new_keyword_with_parent("int".to_string(), types.clone());
1024        let float = FSMNode::new_keyword_with_parent("short".to_string(), types.clone());
1025        root.borrow_mut().add_child(&types);
1026        child2.borrow_mut().add_child(&types);
1027
1028        let mut cursor = FSMCursor::new(&root);
1029        assert!(cursor.advance('s').is_none());
1030        assert!(cursor.advance('h').is_some());
1031        let mut cursor = FSMCursor::new(&root);
1032        assert!(cursor.advance('u').is_some());
1033        assert!(cursor.advance('s').is_some());
1034    }
1035
1036    #[test]
1037    fn test_deep_clone() {
1038        let root = FSMNode::new_null(None);
1039        let mut sign_token = NodeType::Keyword(Keyword::new("unsigned".to_string(), None));
1040        let child = FSMNode::new(sign_token.clone(), &root);
1041        sign_token = NodeType::Keyword(Keyword::new("signed".to_string(), None));
1042
1043        let child2 = FSMNode::new(sign_token, &root);
1044        let types = FSMNode::new_required(NodeType::Null, &child);
1045        println!("hi?");
1046        FSMNode::add_child_cycle_safe(&types, &root);
1047        let cloned_root = root.borrow().deep_clone();
1048        let root = root.borrow();
1049        let cloned_root = cloned_root.borrow();
1050        assert_eq!(root.value, cloned_root.value);
1051        // TODO: make this go all the way through the tree
1052        for (i, child) in root.children.iter().enumerate() {
1053            assert_eq!(child.borrow().value, cloned_root.children[i].borrow().value);
1054        }
1055    }
1056
1057    #[test]
1058    fn simple_full() {
1059        let bnf = r"
1060        t1 ::= t2 | t3;
1061        t2 ::= 'r' t3;
1062        t3 ::= 'a';
1063        ";
1064        let root = frontend::create_graph_from_ebnf(bnf).unwrap();
1065        let mut cursor = FSMCursor::new(&root);
1066        assert_eq!("r", cursor.advance('r').unwrap());
1067        assert_eq!("a", cursor.advance('a').unwrap());
1068        assert!(cursor.is_done());
1069    }
1070
1071    #[test]
1072    fn test_optional() {
1073        let bnf = r"
1074        t1 ::= 't' ( 'e' t2 )? 't';
1075        t2 ::= 's' ( t3 )?;
1076        t3 ::= 'a';
1077        ";
1078        let root = frontend::create_graph_from_ebnf(bnf).unwrap();
1079        let mut cursor = FSMCursor::new(&root);
1080        assert_eq!("t", cursor.advance('t').unwrap());
1081        assert_eq!("t", cursor.advance('t').unwrap());
1082        assert!(cursor.is_done());
1083
1084        let mut cursor = FSMCursor::new(&root);
1085        assert_eq!("t", cursor.advance('t').unwrap());
1086        assert_eq!("e", cursor.advance('e').unwrap());
1087        assert_eq!("s", cursor.advance('s').unwrap());
1088        assert_eq!("a", cursor.advance('a').unwrap());
1089        assert_eq!("t", cursor.advance('t').unwrap());
1090        assert!(cursor.is_done());
1091
1092        let mut cursor = FSMCursor::new(&root);
1093        assert_eq!("t", cursor.advance('t').unwrap());
1094        assert_eq!("e", cursor.advance('e').unwrap());
1095        assert_eq!("s", cursor.advance('s').unwrap());
1096        assert_eq!("t", cursor.advance('t').unwrap());
1097        assert!(cursor.is_done());
1098    }
1099
1100    #[test]
1101    fn test_optional2() {
1102        let bnf = r"
1103        t1 ::= 'te' t2 't';
1104        t2 ::= ( 's' )?; 
1105        ";
1106        let root = frontend::create_graph_from_ebnf(bnf).unwrap();
1107        let mut cursor = FSMCursor::new(&root);
1108        assert_eq!("te", cursor.advance('t').unwrap());
1109        assert_eq!("t", cursor.advance('t').unwrap());
1110        assert!(cursor.is_done());
1111        let mut cursor = FSMCursor::new(&root);
1112        assert_eq!("te", cursor.advance('t').unwrap());
1113        assert_eq!("s", cursor.advance('s').unwrap());
1114        assert_eq!("t", cursor.advance('t').unwrap());
1115        assert!(cursor.is_done());
1116    }
1117
1118    // you are the bane of my existence. If I ever had the chance to erase
1119    // something from the universe permanently, I would erase recursive bnf terminal definitions.
1120    // There is no reason this is so incredibly hard to parse.
1121    #[test]
1122    fn test_sql() {
1123        let bnf = r"
1124        query ::= select | insert;
1125        select ::= 'SELECT' '*' | collist 'FROM' #'^.*;$';
1126        insert ::= 'INSERT INTO' #'^.* $' 'VALUES' '(' collist ')';
1127        collist ::= col ( ',' collist )?;
1128        col ::= #'^.*[, ]$';
1129    ";
1130        let root = frontend::create_graph_from_ebnf(bnf).unwrap();
1131        root.borrow().dbg();
1132        let mut cursor = FSMCursor::new(&root);
1133        assert_eq!("SELECT", cursor.advance('S').unwrap());
1134        assert_eq!(None, cursor.advance('a'));
1135        assert_eq!(",", cursor.advance(',').unwrap());
1136        assert_eq!(None, cursor.advance('b'));
1137        cursor.advance(' ');
1138        assert_eq!("FROM", cursor.advance('F').unwrap());
1139        cursor.advance('a');
1140        assert_eq!(";", cursor.advance(';').unwrap());
1141        assert!(cursor.is_done());
1142    }
1143
1144    #[test]
1145    fn test_repeat() {
1146        let bnf = r"
1147        t1 ::= 't' { 'e' } 'st';
1148    ";
1149        let root = frontend::create_graph_from_ebnf(bnf).unwrap();
1150        // >:3
1151        for i in 0..=30 {
1152            let mut cursor = FSMCursor::new(&root);
1153            assert_eq!("t", cursor.advance('t').unwrap());
1154            for _ in 0..i {
1155                assert_eq!("e", cursor.advance('e').unwrap());
1156            }
1157            assert_eq!("st", cursor.advance('s').unwrap());
1158            assert!(cursor.is_done());
1159        }
1160    }
1161
1162    #[test]
1163    fn test_terminal() {
1164        let terms: usize = 100;
1165        let mut bnf = String::with_capacity(terms * 14);
1166        for i in 1..terms {
1167            bnf.push_str(&format!("t{i:0>3} ::= t{:0>3};\n", i + 1));
1168        }
1169        bnf.push_str(&format!("t{terms:0>3} ::= 't' 'st';"));
1170        println!("{bnf}");
1171        let root = frontend::create_graph_from_ebnf(&bnf).unwrap();
1172        let mut cursor = FSMCursor::new(&root);
1173        assert_eq!("t", cursor.advance('t').unwrap());
1174        assert_eq!("st", cursor.advance('s').unwrap());
1175        assert!(cursor.is_done());
1176    }
1177
1178    fn util_check_str(root: &Rc<RefCell<FSMNode>>, str: &str) {
1179        let mut cursor = FSMCursor::new(root);
1180        for char in str.chars() {
1181            cursor.advance(char);
1182        }
1183        assert!(cursor.is_done())
1184    }
1185
1186    #[test]
1187    fn test_combi() {
1188        let bnf = r"
1189        t1 ::= ( 'u' | 'a' | 'o' ) { 'w' | 'v' } ( 'u' | 'a' | 'o' );
1190    ";
1191        let root = frontend::create_graph_from_ebnf(bnf).unwrap();
1192        util_check_str(&root, "uwu");
1193        util_check_str(&root, "owo");
1194        util_check_str(&root, "owwwwwo");
1195        util_check_str(&root, "owwwwwu");
1196    }
1197
1198    #[test]
1199    fn test_repeat_multiple() {
1200        let bnf = r"
1201        t1 ::= 't' t2 't';
1202        t2 ::= 'oas' | ( 'e' { 'a' 's' } );
1203    ";
1204        let root = frontend::create_graph_from_ebnf(bnf).unwrap();
1205        let mut cursor = FSMCursor::new(&root);
1206        assert_eq!("t", cursor.advance('t').unwrap());
1207        assert_eq!("oas", cursor.advance('o').unwrap());
1208        assert_eq!("t", cursor.advance('t').unwrap());
1209        assert!(cursor.is_done());
1210
1211        let mut cursor = FSMCursor::new(&root);
1212        assert_eq!("t", cursor.advance('t').unwrap());
1213        assert_eq!("e", cursor.advance('e').unwrap());
1214        assert_eq!("a", cursor.advance('a').unwrap());
1215        assert_eq!("s", cursor.advance('s').unwrap());
1216        assert_eq!("a", cursor.advance('a').unwrap());
1217        assert_eq!("s", cursor.advance('s').unwrap());
1218        assert_eq!("t", cursor.advance('t').unwrap());
1219        assert!(cursor.is_done());
1220    }
1221
1222    #[test]
1223    fn test_userdefs() {
1224        let bnf = r"
1225        t1 ::= ( #'[0-9]' 't' ) | ( #'[a-z]' 'e' );
1226    ";
1227        let root = frontend::create_graph_from_ebnf(bnf).unwrap();
1228        let mut cursor = FSMCursor::new(&root);
1229        assert_eq!(None, cursor.advance('1'));
1230        assert_eq!("t", cursor.advance('t').unwrap());
1231        assert!(cursor.is_done());
1232
1233        let mut cursor = FSMCursor::new(&root);
1234        assert_eq!(None, cursor.advance('a'));
1235        assert_eq!("e", cursor.advance('e').unwrap());
1236        assert!(cursor.is_done());
1237    }
1238    fn test_minify() {
1239        let root = FSMNode::new_null(None);
1240        let child = FSMNode::new_null(Some(&root));
1241        let child = FSMNode::new_keyword_with_parent("asdf".to_string(), child);
1242        // minify
1243        root.borrow().dbg();
1244        FSMNode::minify(&root);
1245        root.borrow().dbg();
1246        assert_eq!(Null, root.borrow().value);
1247        assert_eq!(
1248            Keyword(Keyword::new("asdf".to_string(), None)),
1249            root.borrow().children[0].borrow().value
1250        );
1251        assert_eq!(1, root.borrow().children.len())
1252    }
1253
1254    #[test]
1255    fn test_minify_multiple() {
1256        let root = FSMNode::new_null(None);
1257        let child = FSMNode::new_null(Some(&root));
1258        let child = FSMNode::new_null(Some(&child));
1259        let child = FSMNode::new_keyword_with_parent("asdf".to_string(), child);
1260        // minify
1261        root.borrow().dbg();
1262        FSMNode::minify(&root);
1263        root.borrow().dbg();
1264        assert_eq!(Null, root.borrow().value);
1265        assert_eq!(
1266            Keyword(Keyword::new("asdf".to_string(), None)),
1267            root.borrow().children[0].borrow().value
1268        );
1269        assert_eq!(1, root.borrow().children.len())
1270    }
1271
1272    #[test]
1273    fn test_minify_cycles() {
1274        let root = FSMNode::new_null(None);
1275        let child = FSMNode::new_null(Some(&root));
1276        let child2 = FSMNode::new_null(Some(&child));
1277        let child = FSMNode::new_keyword_with_parent("asdf".to_string(), child2.clone());
1278        FSMNode::add_child_cycle_safe(&child, &child2);
1279        FSMNode::minify(&root);
1280
1281        assert_eq!(Null, root.borrow().value);
1282        assert_eq!(
1283            Keyword(Keyword::new("asdf".to_string(), None)),
1284            root.borrow().children[0].borrow().value
1285        );
1286        assert_eq!(1, root.borrow().children.len());
1287        assert_eq!(1, root.borrow().children[0].borrow().children.len());
1288    }
1289}
lib/lib.rs

lib/
lib.rs
