245000359

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/14cbed38c3067322448e5145077042d089404cc9">14cbed38c<a href="https://github.com/maidsafe/crdt_tree/commit/14cbed38c3067322448e5145077042d089404cc9">">Merge </a><a class="double-link" href="https://github.com/maidsafe/crdt_tree/commit/<a class="double-link" href="https://github.com/maidsafe/crdt_tree/commit/1de7b77c0488d997aae3b98d81e64a8503d53060">1de7b77c0</a>">1de7b77c0</a><a href="https://github.com/maidsafe/crdt_tree/commit/14cbed38c3067322448e5145077042d089404cc9"> into 27ace7c82">27ace7c82</a>

Pull Request Pull Request #10: Code review pr

Run Details

3 of 13 new or added lines in 3 files covered. (23.08%)

107 of 264 relevant lines covered (40.53%)

1.19 hits per line

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

25.0

/src/tree.rs

// Copyright 2020 MaidSafe.net limited.
//
// This SAFE Network Software is licensed to you under the MIT license <LICENSE-MIT
// http://opensource.org/licenses/MIT> or the Modified BSD license <LICENSE-BSD
// https://opensource.org/licenses/BSD-3-Clause>, at your option. This file may not be copied,
// modified, or distributed except according to those terms. Please review the Licences for the
// specific language governing permissions and limitations relating to use of the SAFE Network
// Software.

//! Implements Tree, a set of triples representing current tree structure.
//!
//! For usage/examples, see:
//!   examples/tree.rs
//!   test/tree.rs
//!
//! This code aims to be an accurate implementation of the
//! tree crdt described in:
//!
//! "A highly-available move operation for replicated trees
//! and distributed filesystems" [1] by Martin Klepmann, et al.
//!
//! [1] https://martin.kleppmann.com/papers/move-op.pdf
//!
//! For clarity, data structures in this implementation are named
//! the same as in the paper (State, Tree) or close to
//! (OpMove --> Move, LogOpMove --> LogOp).  Some are not explicitly
//! named in the paper, such as TreeId, TreeMeta, TreeNode, Clock.

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

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

/// From the paper:
/// ----
/// 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.
/// ----
#[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, HashMap<ID, bool>>, // parent_id => [child_id => true].  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, HashMap<ID, bool>>::new(), // parent_id => [child_id => true].  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(), true);
        } else {
            let mut h: HashMap<ID, bool> = HashMap::new();
            h.insert(child_id.to_owned(), true);
            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.keys().cloned().collect()
        } else {
            Vec::<ID>::default()
        }
    }

    /// walks tree and calls Fn 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, f: &F)
    where
        F: Fn(&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)
                }
            }
        }
    }

    /// 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.

    /// determines if ancestor_id is an ancestor of node_id in tree.
    /// returns bool
    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
    }
}

/// 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()
    }
}

1	// Copyright 2020 MaidSafe.net limited.
2	//
3	// This SAFE Network Software is licensed to you under the MIT license <LICENSE-MIT
4	// http://opensource.org/licenses/MIT> or the Modified BSD license <LICENSE-BSD
5	// https://opensource.org/licenses/BSD-3-Clause>, at your option. This file may not be copied,
6	// modified, or distributed except according to those terms. Please review the Licences for the
7	// specific language governing permissions and limitations relating to use of the SAFE Network
8	// Software.
9
10	//! Implements Tree, a set of triples representing current tree structure.
11	//!
12	//! For usage/examples, see:
13	//! examples/tree.rs
14	//! test/tree.rs
15	//!
16	//! This code aims to be an accurate implementation of the
17	//! tree crdt described in:
18	//!
19	//! "A highly-available move operation for replicated trees
20	//! and distributed filesystems" [1] by Martin Klepmann, et al.
21	//!
22	//! [1] https://martin.kleppmann.com/papers/move-op.pdf
23	//!
24	//! For clarity, data structures in this implementation are named
25	//! the same as in the paper (State, Tree) or close to
26	//! (OpMove --> Move, LogOpMove --> LogOp). Some are not explicitly
27	//! named in the paper, such as TreeId, TreeMeta, TreeNode, Clock.
28
29	use serde::{Deserialize, Serialize};
30	use std::cmp::{Eq, PartialEq};
31	use std::collections::HashMap;
32
33	use super::{TreeId, TreeMeta, TreeNode};
34
35	/// From the paper:
36	/// ----
37	/// We can represent the tree as a set of (parent, meta, child)
38	/// triples, denoted in Isabelle/HOL as (’n × ’m × ’n) set. When
39	/// we have (p, m, c) ∈ tree, that means c is a child of p in the tree,
40	/// with associated metadata m. Given a tree, we can construct
41	/// a new tree’ in which the child c is moved to a new parent p,
42	/// with associated metadata m, as follows:
43	///
44	/// tree’ = {(p’, m’, c’) ∈ tree. c’ != c} ∪ {(p, m, c)}
45	///
46	/// That is, we remove any existing parent-child relationship
47	/// for c from the set tree, and then add {(p, m, c)} to represent
48	/// the new parent-child relationship.
49	/// ----
50	#[derive(Default, Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
51	pub struct Tree<ID: TreeId, TM: TreeMeta> {
52	triples: HashMap<ID, TreeNode<ID, TM>>, // tree_nodes, indexed by child_id.
53	children: HashMap<ID, HashMap<ID, bool>>, // parent_id => [child_id => true]. optimization.
54	}
55
56	impl<ID: TreeId, TM: TreeMeta> Tree<ID, TM> {
57	/// create a new Tree instance
58	pub fn new() -> Self {	2✔
59	Self {
60	triples: HashMap::<ID, TreeNode<ID, TM>>::new(), // tree_nodes, indexed by child_id.
61	children: HashMap::<ID, HashMap<ID, bool>>::new(), // parent_id => [child_id => true]. optimization.
62	}
63	}
64
65	/// helper for removing a triple based on child_id
66	pub fn rm_child(&mut self, child_id: &ID) {	2✔
67	let result = self.triples.get(child_id);	×
68	if let Some(t) = result {	6✔
69	if let Some(map) = self.children.get_mut(t.parent_id()) {	6✔
70	map.remove(child_id);	×
71	// cleanup parent entry if empty.
72	if map.is_empty() {	6✔
73	self.children.remove(t.parent_id());	×
74	}
75	}
76	self.triples.remove(child_id);	×
77	}
78	}
79
80	/// removes a subtree. useful for emptying trash.
81	/// not used by crdt algo.
82	pub fn rm_subtree(&mut self, parent_id: &ID, include_parent: bool) {	×
83	for c in self.children(parent_id) {	×
84	self.rm_subtree(&c, false);	×
85	self.rm_child(&c);	×
86	}
87	if include_parent {	×
88	self.rm_child(parent_id)	×
89	}
90	}
91
92	/// adds a node to the tree
93	pub fn add_node(&mut self, child_id: ID, tt: TreeNode<ID, TM>) {	4✔
94	if let Some(n) = self.children.get_mut(tt.parent_id()) {	4✔
95	n.insert(child_id.to_owned(), true);	×
96	} else {
97	let mut h: HashMap<ID, bool> = HashMap::new();	×
98	h.insert(child_id.to_owned(), true);	×
99	self.children.insert(tt.parent_id().to_owned(), h);	×
100	}
101	self.triples.insert(child_id, tt);	2✔
102	}
103
104	/// returns matching node, or None.
105	pub fn find(&self, child_id: &ID) -> Option<&TreeNode<ID, TM>> {	×
106	self.triples.get(child_id)	×
107	}
108
109	/// returns children (IDs) of a given parent node.
110	/// useful for walking tree.
111	/// not used by crdt algo.
112	pub fn children(&self, parent_id: &ID) -> Vec<ID> {	×
113	if let Some(list) = self.children.get(parent_id) {	×
114	list.keys().cloned().collect()	×
115	} else {
116	Vec::<ID>::default()	×
117	}
118	}
119
120	/// walks tree and calls Fn f for each node.
121	/// not used by crdt algo.
122	///
123	/// walk uses a non-recursive algorithm, so calling
124	/// it on a deep tree will not cause stack overflow.
125	pub fn walk<F>(&self, parent_id: &ID, f: &F)
126	where
127	F: Fn(&Self, &ID, usize),
128	{
NEW 129	let mut stack: Vec<ID> = Vec::new();	×
NEW 130	stack.push(parent_id.clone());	×
NEW 131	while !stack.is_empty() {	×
NEW 132	if let Some(next) = stack.pop() {	×
NEW 133	f(self, &next, stack.len());	×
NEW 134	for child in self.children(&next) {	×
NEW 135	stack.push(child)	×
136	}
137	}
138	}
139	}
140
141	/// parent \| child
142	/// --------------
143	/// 1 2
144	/// 1 3
145	/// 3 5
146	/// 2 6
147	/// 6 8
148
149	/// 1
150	/// 2 3
151	/// 6 5
152	/// 8
153	///
154	/// is 2 ancestor of 8? yes.
155	/// is 2 ancestor of 5? no.
156
157	/// determines if ancestor_id is an ancestor of node_id in tree.
158	/// returns bool
159	pub fn is_ancestor(&self, child_id: &ID, ancestor_id: &ID) -> bool {	2✔
160	let mut target_id = child_id;	×
161	while let Some(n) = self.find(&target_id) {	7✔
162	if n.parent_id() == ancestor_id {	5✔
163	return true;	×
164	}
165	target_id = n.parent_id();	×
166	}
167	false	×
168	}
169	}
170
171	/// Implement `IntoIterator` for `Tree`. This is useful for
172	/// walking all Nodes in tree without knowing a starting point.
173	impl<ID: TreeId, TM: TreeMeta> IntoIterator for Tree<ID, TM> {
174	type Item = (ID, TreeNode<ID, TM>);
175	type IntoIter = std::collections::hash_map::IntoIter<ID, TreeNode<ID, TM>>;
176
177	fn into_iter(self) -> Self::IntoIter {	×
178	self.triples.into_iter()	×
179	}
180	}

maidsafe / crdt_tree / 245000359

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