linkspace/experimental/
tree.rs

1use linkspace_core::{
2    ShouldBreak,
3    point::{Link, PFieldsExt, Point},
4};
5
6pub fn select_all(point: &dyn Point, links: &mut Vec<Link>) -> ShouldBreak {
7    links.extend(point.get_links());
8    false
9}
10#[allow(unused_variables)]
11pub trait Visitor {
12    fn on_enter(&mut self, point: Option<&dyn Point>, link: &Link) -> ShouldBreak {
13        false
14    }
15    fn on_exit(&mut self, point: Option<&dyn Point>, link: &Link) -> ShouldBreak {
16        false
17    }
18    fn select(&mut self, point: &dyn Point, links: &mut Vec<Link>) -> ShouldBreak {
19        select_all(point, links)
20    }
21    fn on_missing(&mut self, point: &dyn Point, links: Vec<Link>) -> ShouldBreak {
22        false
23    }
24}
25
26impl Visitor for OnEnter<'_> {
27    fn on_enter(&mut self, point: Option<&dyn Point>, link: &Link) -> ShouldBreak {
28        (self.0)(point, link)
29    }
30}
31
32#[allow(missing_debug_implementations)]
33pub struct OnEnter<'o>(pub &'o mut dyn FnMut(Option<&dyn Point>, &Link) -> ShouldBreak);
34
35#[allow(missing_debug_implementations)]
36pub struct OnVisit<'o> {
37    pub on_enter: &'o mut dyn FnMut(Option<&dyn Point>, &Link) -> ShouldBreak,
38    pub on_exit: &'o mut dyn FnMut(Option<&dyn Point>, &Link) -> ShouldBreak,
39    pub select: &'o mut dyn FnMut(&dyn Point, &mut Vec<Link>) -> ShouldBreak,
40    pub on_missing: &'o mut dyn FnMut(&dyn Point, Vec<Link>) -> ShouldBreak,
41}
42
43impl Visitor for OnVisit<'_> {
44    fn on_enter(&mut self, point: Option<&dyn Point>, link: &Link) -> ShouldBreak {
45        (self.on_enter)(point, link)
46    }
47    fn on_exit(&mut self, point: Option<&dyn Point>, link: &Link) -> ShouldBreak {
48        (self.on_exit)(point, link)
49    }
50    fn select(&mut self, point: &dyn Point, links: &mut Vec<Link>) -> ShouldBreak {
51        (self.select)(point, links)
52    }
53    /// note that this might include duplicates.
54    fn on_missing(&mut self, point: &dyn Point, links: Vec<Link>) -> ShouldBreak {
55        (self.on_missing)(point, links)
56    }
57}
58
59pub fn lks_scan_tree(root: &dyn Point, mut visitor: impl Visitor) -> bool {
60    linkspace_system::thread_local::with_system(|lks| {
61        let reader = lks.dyn_reader();
62        walk_depth(&*reader, root, &mut visitor)
63    })
64}
65use linkspace_system::storage_engine::tables_traits::*;
66fn walk_depth(lks: &dyn DynTHLReadTxn, root: &dyn Point, visitor: &mut impl Visitor) -> bool {
67    let mut pending = vec![];
68    let mut missing = vec![];
69    if visitor.select(root, &mut pending) {
70        return false;
71    }
72    let mut pending_it = pending.iter();
73    let breek = lks.get_points_by_hash(&mut pending.iter().map(|o| o.ptr), &mut |point| {
74        let link = pending_it.next().unwrap();
75        let point = point.ok();
76        if point.is_none() {
77            missing.push(*link);
78        }
79        visitor.on_enter(point, link)
80            || point.map(|p| walk_depth(lks, p, visitor)).unwrap_or(false)
81            || visitor.on_exit(point, link)
82    });
83    if breek || missing.is_empty() {
84        return breek;
85    }
86    visitor.on_missing(root, missing)
87}
88
89#[cfg(test)]
90mod tests {
91    /**
92    point layout
93    root {
94      digit0,
95      digit0,
96      digit1,
97      sub23:{
98        digit2, digit3
99      },
100      sub450:{
101        digit4,digit5,digit0
102      },
103      sub450:{
104        digit4,digit5,digit0
105      },
106    }
107    returns [root,sub23,sub450,digits 0..5];
108     **/
109    use crate::*;
110    #[derive(Clone)]
111    struct LP {
112        lnk: Link,
113        p: PointBox,
114    }
115    fn generate() -> [LP; 9] {
116        let lp_gen = |name: &str, links: &[Link]| {
117            let p = lk_linkpoint(&"", name.as_bytes(), links).unwrap();
118            LP {
119                lnk: Link::new(name, p.hash()),
120                p,
121            }
122        };
123
124        let [d0, d1, d2, d3, d4, d5] = [0, 1, 2, 3, 4, 5].map(|i| lp_gen(&i.to_string(), &[]));
125        let sub23 = lp_gen("sub23", &[d2.lnk, d3.lnk]);
126        let sub45 = lp_gen("sub450", &[d4.lnk, d5.lnk, d0.lnk]);
127        let root = lp_gen(
128            "root",
129            &[d0.lnk, d0.lnk, d1.lnk, sub23.lnk, sub45.lnk, sub45.lnk],
130        );
131        [root, sub23, sub45, d0, d1, d2, d3, d4, d5]
132    }
133    use super::*;
134
135    #[test]
136    fn treewalker() {
137        let points = generate();
138
139        lks_open_inmem("");
140
141        for lp in &points {
142            lks_save(&lp.p).unwrap();
143        }
144        lks_process();
145        let mut pre_order = vec![];
146        let mut post_order = vec![];
147        let [root, sub23, sub45, d0, d1, d2, d3, d4, d5] = points;
148        lks_scan_tree(
149            &root.p,
150            OnVisit {
151                on_enter: &mut |_, l| {
152                    pre_order.push(l.tag);
153                    println!("PRE {}", l.tag);
154                    false
155                },
156                on_exit: &mut |_, l| {
157                    post_order.push(l.tag);
158                    false
159                },
160                select: &mut select_all,
161                on_missing: &mut |_, _| false,
162            },
163        );
164        assert_eq!(
165            &pre_order,
166            &[
167                &d0, &d0, &d1, &sub23, &d2, &d3, &sub45, &d4, &d5, &d0, &sub45, &d4, &d5, &d0
168            ]
169            .map(|o| o.lnk.tag)
170        );
171        assert_eq!(
172            &post_order,
173            &[
174                &d0, &d0, &d1, &d2, &d3, &sub23, &d4, &d5, &d0, &sub45, &d4, &d5, &d0, &sub45
175            ]
176            .map(|o| o.lnk.tag)
177        );
178    }
179    #[test]
180    fn tree_tap() {
181        let points = generate();
182
183        lks_open_inmem("");
184        let [root, sub23, sub45, d0, d1, d2, d3, d4, d5] = points;
185
186        // leave out sub450, and d5
187        for lp in &[root.clone(), sub23, d0, d1, d2, d3, d4] {
188            lks_save(&lp.p).unwrap();
189        }
190        lks_process();
191        lks_scan_tree(
192            &root.p,
193            OnVisit {
194                on_enter: &mut |_, _| false,
195                on_exit: &mut |_, _| false,
196                select: &mut select_all,
197                on_missing: &mut |p, l| {
198                    assert_eq!(p.hash(), root.p.hash());
199                    assert_eq!(&[sub45.lnk, sub45.lnk], l.as_slice());
200                    false
201                },
202            },
203        );
204        use crate::experimental::tap_hashes::lks_tap_tree;
205        use crate::system::cb::*;
206        lks_tap_tree(
207            &root.p,
208            Handle {
209                on_point: |point: &dyn Point, _: Option<&[u8]>| -> ControlFlow<()> {
210                    println!("{:?}", point.data_str());
211                    std::ops::ControlFlow::Continue(())
212                },
213                on_close: |_, _, _, _| {
214                    println!("Tap complete");
215                },
216            },
217            Some(Box::new(|_p, lst| {
218                println!("On Missing {lst:?}");
219                false
220            })),
221            None,
222        )
223        .unwrap();
224        println!("saving sub450");
225        lks_save(&sub45.p).unwrap();
226        lks_process();
227        println!("saving d5");
228        lks_save(&d5.p).unwrap();
229        lks_process();
230        println!("finish");
231        //let mut pre_order = vec![];
232        //let mut post_order = vec![];
233    }
234}
linkspace/experimental/tree.rs

linkspace/experimental/
tree.rs
