nb_tree/tree/
diff.rs

1use std::{collections::HashMap, hash::Hash, marker::PhantomData, mem};
2use tracing::{debug, error, trace, trace_span};
3
4use crate::{path::Path, tree::entry::Entry, tree::iter::depth::Traversal};
5
6use super::{
7    entry::{TreeRefEntry, TREEBOUND},
8    iter::depth::TreeIterTarget,
9    node::TreeNode,
10    NodeIDX, Tree,
11};
12
13/// Representation of a node differential
14pub type DiffNode<N> = (Option<N>, Option<N>);
15/// A tree containing [DiffNode]s as nodes
16pub type DiffTree<N, B> = Tree<DiffNode<N>, B>;
17
18pub struct Before<N>(PhantomData<N>);
19pub struct Now<N>(PhantomData<N>);
20
21impl<'a, N, B> TreeIterTarget<'a, DiffNode<N>, B> for Now<&'a N> {
22    type Target = &'a Option<N>;
23    fn target(tree: &'a Tree<DiffNode<N>, B>, idx: NodeIDX) -> Self::Target {
24        &tree.nodes[idx].value.1
25    }
26}
27
28impl<'a, N, B> TreeIterTarget<'a, DiffNode<N>, B> for Before<&'a N> {
29    type Target = &'a Option<N>;
30    fn target(tree: &'a Tree<DiffNode<N>, B>, idx: NodeIDX) -> Self::Target {
31        &tree.nodes[idx].value.0
32    }
33}
34
35impl<N, B> DiffTree<N, B>
36where
37    B: Clone,
38{
39    // Reverses a Differential
40    pub fn rev(&mut self) {
41        for node in self.nodes.iter_mut() {
42            mem::swap(&mut node.value.0, &mut node.value.1);
43        }
44    }
45
46    pub fn validate(&self) -> Result<(), Path<B>> {
47        //TODO: rewrite method
48        let mut ph = Path::new();
49        for diff in self.iter_on::<&TreeNode<DiffNode<N>, B>>() {
50            ph.apply(&diff);
51            let d: &TreeNode<_, _> = diff.take();
52            // Node removal
53            if let (Some(_), None) = d.value {
54                // But
55                if !d.children.is_empty() {
56                    return Err(ph.branches_to_owned());
57                }
58            }
59        }
60        Ok(())
61    }
62}
63
64impl<N, B> DiffTree<N, B>
65where
66    N: Clone,
67    B: Clone + Eq + Hash,
68{
69    pub(super) fn mirror_subtree_at(
70        &mut self,
71        tree: &Tree<N, B>,
72        idx_s: NodeIDX,
73        idx_t: NodeIDX,
74        now: bool,
75    ) {
76        if now {
77            self.nodes[idx_s].value.1 = Some(tree.nodes[idx_t].value.clone());
78        } else {
79            self.nodes[idx_s].value.0 = Some(tree.nodes[idx_t].value.clone());
80        }
81        self.mirror_subtree_rec(tree, idx_s, idx_t, now);
82    }
83
84    pub fn mirror_subtree_rec(
85        &mut self,
86        tree: &Tree<N, B>,
87        idx_s: NodeIDX,
88        idx_t: NodeIDX,
89        now: bool,
90    ) {
91        for (branch, &c_idx_t) in &tree.nodes[idx_t].children {
92            let c_idx_s = if let Some(&c_idx_s) = self.nodes[idx_s].children.get(branch) {
93                if now {
94                    self.nodes[c_idx_s].value.1 = Some(tree.nodes[c_idx_t].value.clone());
95                } else {
96                    self.nodes[c_idx_s].value.0 = Some(tree.nodes[c_idx_t].value.clone());
97                }
98                c_idx_s
99            } else {
100                self.insert_at(
101                    idx_s,
102                    branch.clone(),
103                    if now {
104                        (None, Some(tree.nodes[c_idx_t].value.clone()))
105                    } else {
106                        (Some(tree.nodes[c_idx_t].value.clone()), None)
107                    },
108                );
109                self.nodes[idx_s].children[branch]
110            };
111            self.mirror_subtree_rec(tree, c_idx_s, c_idx_t, now);
112        }
113    }
114}
115
116impl<N, B> DiffTree<N, B>
117where
118    N: Clone + Default,
119    B: Clone + Eq + Hash + Default,
120{
121    pub fn mirror_subtree(&mut self, tree: &Tree<N, B>, path: &Path<B>, now: bool) {
122        let root_t = tree.get_idx(path, None).unwrap();
123        let root_s = if let Ok(root_s) = self.get_idx(path, None) {
124            root_s
125        } else {
126            *self.extend(path, None).last().unwrap()
127        };
128        self.mirror_subtree_at(tree, root_s, root_t, now)
129    }
130}
131
132impl<N, B> DiffTree<N, B>
133where
134    N: Default + Eq,
135    B: Default + Eq + Hash + Clone,
136{
137    pub fn is_applicable_extend(&self, tree: &Tree<N, B>) -> Result<(), DiffApplyError<B>> {
138        self.is_applicable_with(tree, |entry, new| {
139            // Extend if needed
140            new.unwrap().1 = entry.path().len();
141            Ok(())
142        })
143    }
144}
145
146type Insertable<N, B> = fn(
147    &mut TreeRefEntry<N, B, TREEBOUND>,
148    &mut Option<(usize, usize)>,
149) -> Result<(), DiffApplyError<B>>;
150
151impl<N, B> DiffTree<N, B>
152where
153    N: Eq,
154    B: Eq + Hash + Clone,
155{
156    pub fn is_applicable(&self, tree: &Tree<N, B>) -> Result<(), DiffApplyError<B>> {
157        self.is_applicable_with(tree, |entry, new| {
158            if entry.is_node() {
159                // Attached
160                return Ok(());
161            }
162            // Can't extend, can only append
163            let detached = entry.detached().unwrap();
164            let detached_dist =
165                detached.iter_detached_path().len() - new.map(|(s, e)| e - s).unwrap_or(0);
166            debug_assert!(
167                detached_dist > 0,
168                "Expected detached entry, got attached entry"
169            );
170            if detached_dist == 1 {
171                // New node will be created
172                if new.is_some() {
173                    new.unwrap().1 += 1;
174                } else {
175                    let l = entry.path().len();
176                    *new = Some((l - 1, l));
177                }
178                Ok(())
179            } else {
180                // Parent node inexistent
181                Err(DiffApplyError::Other("Expected Parent".to_string()))
182            }
183        })
184    }
185    fn is_applicable_with(
186        &self,
187        tree: &Tree<N, B>,
188        insertable: Insertable<N, B>,
189    ) -> Result<(), DiffApplyError<B>> {
190        use DiffApplyError::*;
191        let mut diff_i = self.iter_on::<&DiffNode<N>>();
192        let mut entry = tree.entry(&Path::new());
193        let mut deleted = None;
194        let mut new = None;
195        // Root
196        match diff_i.next() {
197            Some(Traversal::Start((b, n))) => {
198                if let Some(before) = &b {
199                    let _s1 = trace_span!("Node existed");
200                    let _s1_ = _s1.enter();
201                    // Node should exist
202                    if let Some(node) = entry.node_mut() {
203                        if **node != *before {
204                            return Err(DifferentValue(Path::new()));
205                        }
206                    } else {
207                        return Err(Expected(Path::new()));
208                    }
209                    if n.is_none() {
210                        // Node deleted
211                        trace!("node will be deleted");
212                        deleted = Some(0);
213                    } else {
214                        // Node changed
215                        trace!("node will change");
216                    }
217                } else if n.is_some() {
218                    let _s1 = trace_span!("New node");
219                    let _s1_ = _s1.enter();
220                    // New node
221                    if entry.is_detached() {
222                        trace!("node will be created");
223                        insertable(&mut entry, &mut new)?;
224                    } else {
225                        return Err(Unexpected(Path::new()));
226                    }
227                } else {
228                    trace!("node will remain unchanged");
229                    // No change
230                }
231            }
232            None => {
233                debug!("diff is empty");
234                // Empty diff
235                return Ok(());
236            }
237            Some(_) => {
238                unreachable!("Tree iteration should always start with a Root node");
239            }
240        };
241        // Children
242        for d in diff_i {
243            entry.apply_move_deref(&d);
244            if let Some(idx) = deleted {
245                if entry.path().len() <= idx {
246                    deleted = None;
247                }
248            }
249
250            if let Some(n) = &mut new.as_mut() {
251                let l = entry.path().len();
252                if l <= n.0
253                /*start*/
254                {
255                    new = None;
256                } else if l < n.1
257                /*end*/
258                {
259                    n.1 = l;
260                }
261            }
262
263            let _s1 = trace_span!("next node");
264            let _s1_ = _s1.enter();
265            let (b, n) = d.take();
266
267            if let Some(before) = &b {
268                let _s2 = trace_span!("Node existed");
269                let _s2_ = _s2.enter();
270                // Change or delete node
271                // Node should exist
272                if let Some(node) = entry.node_mut() {
273                    // Diff corresponds to node value?
274                    if **node != *before {
275                        return Err(DifferentValue(node.path().clone()));
276                    }
277                } else {
278                    return Err(Expected(entry.path().clone()));
279                }
280                if n.is_some() {
281                    trace!("node will change");
282                    // Node changed
283                    if deleted.is_some() {
284                        return Err(BelowDeletion(entry.path().clone()));
285                    }
286                } else {
287                    trace!("node will be deleted");
288                    // Node deleted
289                    if deleted.is_none() {
290                        deleted = Some(entry.path().len());
291                    }
292                }
293            } else if n.is_some() {
294                let _s2 = trace_span!("New node");
295                let _s2_ = _s2.enter();
296                // New node
297                if deleted.is_some() {
298                    return Err(BelowDeletion(entry.path().clone()));
299                }
300                if let Entry::Node(node) = entry {
301                    return Err(Unexpected(node.path().clone()));
302                }
303                insertable(&mut entry, &mut new)?;
304            } else {
305                trace!("node will remain unchanged");
306                // No change
307            }
308        }
309        Ok(())
310    }
311}
312
313#[derive(Debug, Clone, PartialEq, Eq)]
314pub enum DiffApplyError<B> {
315    Expected(Path<B>),
316    Unexpected(Path<B>),
317    DifferentValue(Path<B>),
318    BelowDeletion(Path<B>),
319    Other(String),
320}
321
322impl<B, T> From<DiffApplyError<B>> for Result<T, DiffApplyError<B>> {
323    fn from(value: DiffApplyError<B>) -> Self {
324        Err(value)
325    }
326}
327
328/// Structure mapping [Path]s to [DiffNodes]
329pub struct DiffMap<N, B> {
330    diffs: HashMap<Path<B>, DiffNode<N>>,
331}
332
333impl<N, B> IntoIterator for DiffMap<N, B> {
334    type Item = (Path<B>, DiffNode<N>);
335
336    type IntoIter = std::collections::hash_map::IntoIter<Path<B>, DiffNode<N>>;
337
338    fn into_iter(self) -> Self::IntoIter {
339        self.diffs.into_iter()
340    }
341}
342
343impl<N, B> From<HashMap<Path<B>, DiffNode<N>>> for DiffMap<N, B> {
344    fn from(value: HashMap<Path<B>, DiffNode<N>>) -> Self {
345        Self { diffs: value }
346    }
347}
348
349//TODO: remove Ord on N?
350impl<N, B> From<DiffMap<N, B>> for DiffTree<N, B>
351where
352    N: Ord,
353    B: Ord + Default + Hash + Clone,
354{
355    fn from(value: DiffMap<N, B>) -> Self {
356        value
357            .diffs
358            .into_iter()
359            .fold(DiffTree::new(), |mut tree, (ph, v)| {
360                tree.insert_extend(&ph, v);
361                tree
362            })
363    }
364}
nb_tree/tree/diff.rs

nb_tree/tree/
diff.rs
