3252081524

Build # 3252081524

Build Type

github

Committed by GitHub

Commit Message

<a href="https://github.com/maidsafe/crdt_tree/commit/<a class=hub.com/maidsafe/crdt_tree/commit/<a class="double-link" href="https://git"><a class=hub.com/maidsafe/crdt_tree/commit/<a class="double-link" href="https://git"><a class=hub.com/maidsafe/crdt_tree/commit/<a class="double-link" href="https://git"><a class=hub.com/maidsafe/crdt_tree/commit/<a class="double-link" href="https://git"><a class=hub.com/maidsafe/crdt_tree/commit/fe998010e6198dae1b977629a9f5378f147001e6">fe998010e">&lt;a href=&quot;https://github.com/maidsafe/crdt_tree/commit/</a><a class="double-link" href="https://github.com/maidsafe/crdt_tree/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/maidsafe/crdt_tree/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/maidsafe/crdt_tree/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/maidsafe/crdt_tree/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/maidsafe/crdt_tree/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/maidsafe/crdt_tree/commit/fe998010e6198dae1b977629a9f5378f147001e6">fe998010e</a><a href="https://github.com/maidsafe/crdt_tree/commit/fe998010e6198dae1b977629a9f5378f147001e6">&quot;&gt;&amp;lt;a href=&amp;quot;https://github.com/maidsafe/crdt_tree/commit/&lt;/a&gt;&lt;a class=&quot;double-link&quot; href=&quot;https://github.com/maidsafe/crdt_tree/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/maidsafe/crdt_tree/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/maidsafe/crdt_tree/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/maidsafe/crdt_tree/commit/fe998010e6198dae1b977629a9f5378f147001e6&quot;&gt;fe998010e&lt;/a&gt;&lt;a href=&quot;https://github.com/maidsafe/crdt_tree/commit/fe998010e6198dae1b977629a9f5378f147001e6&quot;&gt;&amp;lt;a href=&amp;quot;https://github.com/maidsafe/crdt_tree/commit/fe998010e6198dae1b977629a9f5378f147001e6&amp;quot;&amp;gt;&amp;amp;quot;&amp;amp;gt;&amp;amp;amp;lt;a href=&amp;amp;amp;quot;https://github.com/maidsafe/crdt_tree/commit/&amp;amp;lt;/... (continued)

Pull Request Pull Request #40: WIP - chore: switch to bsd3 license

Run Details

2 of 5 new or added lines in 3 files covered. (40.0%)

22 of 132 relevant lines covered (16.67%)

0.95 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

14.49

/src/tree.rs

// Copyright (c) 2022, MaidSafe.
// All rights reserved.
//
// This SAFE Network Software is licensed under the BSD-3-Clause license.
// Please see the LICENSE file for more details.

use serde::{Deserialize, Serialize};
use std::cmp::{Eq, PartialEq};
use std::collections::{HashMap, HashSet};
use std::fmt;
use std::fmt::Debug;

use super::{TreeId, TreeMeta, TreeNode};

/// Implements `Tree`, a set of triples representing current tree structure.
///
/// Normally this `Tree` struct should not be instantiated directly.
/// Instead instantiate `State` (lower-level) or `TreeReplica` (higher-level)
/// and invoke operations on them.
///
/// From the paper[1]:
/// ----
/// We can represent the tree as a set of (parent, meta, child)
/// triples, denoted in Isabelle/HOL as (’n × ’m × ’n) set. When
/// we have (p, m, c) ∈ tree, that means c is a child of p in the tree,
/// with associated metadata m. Given a tree, we can construct
/// a new tree’ in which the child c is moved to a new parent p,
/// with associated metadata m, as follows:
///
/// tree’ = {(p’, m’, c’) ∈ tree. c’ != c} ∪ {(p, m, c)}
///
/// That is, we remove any existing parent-child relationship
/// for c from the set tree, and then add {(p, m, c)} to represent
/// the new parent-child relationship.
/// ----
/// [1] https://martin.kleppmann.com/papers/move-op.pdf
#[derive(Default, Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct Tree<ID: TreeId, TM: TreeMeta> {
    triples: HashMap<ID, TreeNode<ID, TM>>, // tree_nodes, indexed by child_id.
    children: HashMap<ID, HashSet<ID>>,     // parent_id => [child_id].  index/optimization.
}

impl<ID: TreeId, TM: TreeMeta> Tree<ID, TM> {
    /// create a new Tree instance
    pub fn new() -> Self {
        Self {
            triples: HashMap::<ID, TreeNode<ID, TM>>::new(), // tree_nodes, indexed by child_id.
            children: HashMap::<ID, HashSet<ID>>::new(), // parent_id => [child_id].  index/optimization.
        }
    }

    /// helper for removing a triple based on child_id
    pub fn rm_child(&mut self, child_id: &ID) {
        let result = self.triples.get(child_id);
        if let Some(t) = result {
            if let Some(map) = self.children.get_mut(t.parent_id()) {
                map.remove(child_id);
                // cleanup parent entry if empty.
                if map.is_empty() {
                    self.children.remove(t.parent_id());
                }
            }
            self.triples.remove(child_id);
        }
    }

    /// removes a subtree.  useful for emptying trash.
    /// not used by crdt algo.
    pub fn rm_subtree(&mut self, parent_id: &ID, include_parent: bool) {
        for c in self.children(parent_id) {
            self.rm_subtree(&c, false);
            self.rm_child(&c);
        }
        if include_parent {
            self.rm_child(parent_id)
        }
    }

    /// adds a node to the tree
    pub fn add_node(&mut self, child_id: ID, tt: TreeNode<ID, TM>) {
        if let Some(n) = self.children.get_mut(tt.parent_id()) {
            n.insert(child_id.to_owned());
        } else {
            let mut h: HashSet<ID> = HashSet::new();
            h.insert(child_id.to_owned());
            self.children.insert(tt.parent_id().to_owned(), h);
        }
        self.triples.insert(child_id, tt);
    }

    /// returns matching node, or None.
    pub fn find(&self, child_id: &ID) -> Option<&TreeNode<ID, TM>> {
        self.triples.get(child_id)
    }

    /// returns children (IDs) of a given parent node.
    /// useful for walking tree.
    /// not used by crdt algo.
    pub fn children(&self, parent_id: &ID) -> Vec<ID> {
        if let Some(list) = self.children.get(parent_id) {
            list.iter().cloned().collect()
        } else {
            Vec::<ID>::default()
        }
    }

    /// walks tree and calls FnMut f for each node.
    /// not used by crdt algo.
    ///
    /// walk uses a non-recursive algorithm, so calling
    /// it on a deep tree will not cause stack overflow.
    pub fn walk<F>(&self, parent_id: &ID, mut f: F)
    where
        F: FnMut(&Self, &ID, usize),
    {
        let mut stack: Vec<ID> = Vec::new();
        stack.push(parent_id.clone());
        while !stack.is_empty() {
            if let Some(next) = stack.pop() {
                f(self, &next, stack.len());
                for child in self.children(&next) {
                    stack.push(child)
                }
            }
        }
    }

    /// returns true if ancestor_id is an ancestor of child_id in tree.
    ///
    /// ```text
    /// parent | child
    /// --------------
    /// 1        2
    /// 1        3
    /// 3        5
    /// 2        6
    /// 6        8
    ///
    ///                  1
    ///               2     3
    ///             6         5
    ///           8
    ///
    /// is 2 ancestor of 8?  yes.
    /// is 2 ancestor of 5?   no.
    /// ```
    pub fn is_ancestor(&self, child_id: &ID, ancestor_id: &ID) -> bool {
        let mut target_id = child_id;
        while let Some(n) = self.find(target_id) {
            if n.parent_id() == ancestor_id {
                return true;
            }
            target_id = n.parent_id();
        }
        false
    }

    /// Total number of nodes (triples) in the tree
    pub fn num_nodes(&self) -> usize {
        self.triples.len()
    }
}

/// Implement `IntoIterator` for `Tree`.  This is useful for
/// walking all Nodes in tree without knowing a starting point.
impl<ID: TreeId, TM: TreeMeta> IntoIterator for Tree<ID, TM> {
    type Item = (ID, TreeNode<ID, TM>);
    type IntoIter = std::collections::hash_map::IntoIter<ID, TreeNode<ID, TM>>;

    fn into_iter(self) -> Self::IntoIter {
        self.triples.into_iter()
    }
}

impl<ID: TreeId + Debug, TM: TreeMeta + Debug> fmt::Display for Tree<ID, TM> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        self.print_tree(f)
    }
}

impl<ID: TreeId + Debug, TM: TreeMeta + Debug> Tree<ID, TM> {
    // print a treenode, recursively
    fn print_treenode(
        &self,
        f: &mut fmt::Formatter<'_>,
        node_id: &ID,
        depth: usize,
    ) -> fmt::Result {
        let findresult = self.find(node_id);
        let meta = match findresult {
            Some(tn) => format!("{:?} [{:?}]", node_id, tn.metadata()),
            None => format!("{:?}", node_id),
        };
        let mut result = writeln!(f, "{:indent$}{}", "", meta, indent = depth * 2);

        for c in self.children(node_id) {
            result = self.print_treenode(f, &c, depth + 1);
            if result.is_err() {
                break;
            }
        }
        result
    }

    // print a tree.
    fn print_tree(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let mut r: fmt::Result = Ok(());

        let mut seen: HashSet<ID> = Default::default();

        // We iterate through all triples to find the top-level nodes,
        // i.e. those without any parent (or metadata), then print sub-tree
        // for each one.
        // PERF: This is a slow way to find top-level nodes.  We could
        //       consider keeping a list of them as tree is modified
        for treenode in self.triples.values() {
            let p = treenode.parent_id();
            if self.triples.get(p).is_none() && !seen.contains(p) {
                seen.insert(p.clone());
                r = self.print_treenode(f, p, 0);
                if r.is_err() {
                    break;
                }
            }
        }
        r
    }
}

1	// Copyright (c) 2022, MaidSafe.
2	// All rights reserved.
3	//
4	// This SAFE Network Software is licensed under the BSD-3-Clause license.
5	// Please see the LICENSE file for more details.
6
7	use serde::{Deserialize, Serialize};
8	use std::cmp::{Eq, PartialEq};
9	use std::collections::{HashMap, HashSet};
10	use std::fmt;
11	use std::fmt::Debug;
12
13	use super::{TreeId, TreeMeta, TreeNode};
14
15	/// Implements `Tree`, a set of triples representing current tree structure.
16	///
17	/// Normally this `Tree` struct should not be instantiated directly.
18	/// Instead instantiate `State` (lower-level) or `TreeReplica` (higher-level)
19	/// and invoke operations on them.
20	///
21	/// From the paper[1]:
22	/// ----
23	/// We can represent the tree as a set of (parent, meta, child)
24	/// triples, denoted in Isabelle/HOL as (’n × ’m × ’n) set. When
25	/// we have (p, m, c) ∈ tree, that means c is a child of p in the tree,
26	/// with associated metadata m. Given a tree, we can construct
27	/// a new tree’ in which the child c is moved to a new parent p,
28	/// with associated metadata m, as follows:
29	///
30	/// tree’ = {(p’, m’, c’) ∈ tree. c’ != c} ∪ {(p, m, c)}
31	///
32	/// That is, we remove any existing parent-child relationship
33	/// for c from the set tree, and then add {(p, m, c)} to represent
34	/// the new parent-child relationship.
35	/// ----
36	/// [1] https://martin.kleppmann.com/papers/move-op.pdf
37	#[derive(Default, Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
38	pub struct Tree<ID: TreeId, TM: TreeMeta> {
39	triples: HashMap<ID, TreeNode<ID, TM>>, // tree_nodes, indexed by child_id.
40	children: HashMap<ID, HashSet<ID>>, // parent_id => [child_id]. index/optimization.
41	}
42
43	impl<ID: TreeId, TM: TreeMeta> Tree<ID, TM> {
44	/// create a new Tree instance
45	pub fn new() -> Self {	3✔
46	Self {
47	triples: HashMap::<ID, TreeNode<ID, TM>>::new(), // tree_nodes, indexed by child_id.
48	children: HashMap::<ID, HashSet<ID>>::new(), // parent_id => [child_id]. index/optimization.
49	}
50	}
51
52	/// helper for removing a triple based on child_id
53	pub fn rm_child(&mut self, child_id: &ID) {	3✔
54	let result = self.triples.get(child_id);	×
55	if let Some(t) = result {	×
56	if let Some(map) = self.children.get_mut(t.parent_id()) {	6✔
57	map.remove(child_id);	×
58	// cleanup parent entry if empty.
59	if map.is_empty() {	3✔
60	self.children.remove(t.parent_id());	×
61	}
62	}
63	self.triples.remove(child_id);	×
64	}
65	}
66
67	/// removes a subtree. useful for emptying trash.
68	/// not used by crdt algo.
69	pub fn rm_subtree(&mut self, parent_id: &ID, include_parent: bool) {	×
70	for c in self.children(parent_id) {	×
71	self.rm_subtree(&c, false);	×
72	self.rm_child(&c);	×
73	}
74	if include_parent {	×
75	self.rm_child(parent_id)	×
76	}
77	}
78
79	/// adds a node to the tree
80	pub fn add_node(&mut self, child_id: ID, tt: TreeNode<ID, TM>) {	3✔
81	if let Some(n) = self.children.get_mut(tt.parent_id()) {	3✔
82	n.insert(child_id.to_owned());	×
83	} else {
84	let mut h: HashSet<ID> = HashSet::new();	×
85	h.insert(child_id.to_owned());	×
86	self.children.insert(tt.parent_id().to_owned(), h);	×
87	}
88	self.triples.insert(child_id, tt);	2✔
89	}
90
91	/// returns matching node, or None.
92	pub fn find(&self, child_id: &ID) -> Option<&TreeNode<ID, TM>> {	×
93	self.triples.get(child_id)	×
94	}
95
96	/// returns children (IDs) of a given parent node.
97	/// useful for walking tree.
98	/// not used by crdt algo.
99	pub fn children(&self, parent_id: &ID) -> Vec<ID> {	×
100	if let Some(list) = self.children.get(parent_id) {	×
101	list.iter().cloned().collect()	×
102	} else {
103	Vec::<ID>::default()	×
104	}
105	}
106
107	/// walks tree and calls FnMut f for each node.
108	/// not used by crdt algo.
109	///
110	/// walk uses a non-recursive algorithm, so calling
111	/// it on a deep tree will not cause stack overflow.
112	pub fn walk<F>(&self, parent_id: &ID, mut f: F)
113	where
114	F: FnMut(&Self, &ID, usize),
115	{
116	let mut stack: Vec<ID> = Vec::new();	×
117	stack.push(parent_id.clone());	×
118	while !stack.is_empty() {	×
119	if let Some(next) = stack.pop() {	×
120	f(self, &next, stack.len());	×
121	for child in self.children(&next) {	×
122	stack.push(child)	×
123	}
124	}
125	}
126	}
127
128	/// returns true if ancestor_id is an ancestor of child_id in tree.
129	///
130	/// ```text
131	/// parent \| child
132	/// --------------
133	/// 1 2
134	/// 1 3
135	/// 3 5
136	/// 2 6
137	/// 6 8
138	///
139	/// 1
140	/// 2 3
141	/// 6 5
142	/// 8
143	///
144	/// is 2 ancestor of 8? yes.
145	/// is 2 ancestor of 5? no.
146	/// ```
147	pub fn is_ancestor(&self, child_id: &ID, ancestor_id: &ID) -> bool {	×
148	let mut target_id = child_id;	×
149	while let Some(n) = self.find(target_id) {	4✔
150	if n.parent_id() == ancestor_id {	4✔
151	return true;	×
152	}
153	target_id = n.parent_id();	×
154	}
155	false	×
156	}
157
158	/// Total number of nodes (triples) in the tree
159	pub fn num_nodes(&self) -> usize {	×
160	self.triples.len()	×
161	}
162	}
163
164	/// Implement `IntoIterator` for `Tree`. This is useful for
165	/// walking all Nodes in tree without knowing a starting point.
166	impl<ID: TreeId, TM: TreeMeta> IntoIterator for Tree<ID, TM> {
167	type Item = (ID, TreeNode<ID, TM>);
168	type IntoIter = std::collections::hash_map::IntoIter<ID, TreeNode<ID, TM>>;
169
170	fn into_iter(self) -> Self::IntoIter {	1✔
171	self.triples.into_iter()	×
172	}
173	}
174
175	impl<ID: TreeId + Debug, TM: TreeMeta + Debug> fmt::Display for Tree<ID, TM> {
176	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {	×
177	self.print_tree(f)	×
178	}
179	}
180
181	impl<ID: TreeId + Debug, TM: TreeMeta + Debug> Tree<ID, TM> {
182	// print a treenode, recursively
183	fn print_treenode(
184	&self,
185	f: &mut fmt::Formatter<'_>,
186	node_id: &ID,
187	depth: usize,
188	) -> fmt::Result {
NEW 189	let findresult = self.find(node_id);	×
190	let meta = match findresult {	×
191	Some(tn) => format!("{:?} [{:?}]", node_id, tn.metadata()),	×
192	None => format!("{:?}", node_id),	×
193	};
194	let mut result = writeln!(f, "{:indent$}{}", "", meta, indent = depth * 2);	×
195
NEW 196	for c in self.children(node_id) {	×
197	result = self.print_treenode(f, &c, depth + 1);	×
198	if result.is_err() {	×
199	break;	×
200	}
201	}
202	result	×
203	}
204
205	// print a tree.
206	fn print_tree(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {	×
207	let mut r: fmt::Result = Ok(());	×
208
209	let mut seen: HashSet<ID> = Default::default();	×
210
211	// We iterate through all triples to find the top-level nodes,
212	// i.e. those without any parent (or metadata), then print sub-tree
213	// for each one.
214	// PERF: This is a slow way to find top-level nodes. We could
215	// consider keeping a list of them as tree is modified
216	for treenode in self.triples.values() {	×
217	let p = treenode.parent_id();	×
218	if self.triples.get(p).is_none() && !seen.contains(p) {	×
219	seen.insert(p.clone());	×
220	r = self.print_treenode(f, p, 0);	×
221	if r.is_err() {	×
222	break;	×
223	}
224	}
225	}
226	r	×
227	}
228	}

maidsafe / crdt_tree / 3252081524

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous