quorum_set/tree/
tree.rs

1use std::cmp::Ordering;
2use std::fmt;
3use std::hash::Hash;
4use std::hash::Hasher;
5
6use super::tree_spec::QuorumTreeSpec;
7use crate::CanonicalId;
8use crate::Node;
9use crate::QuorumTreeError;
10
11mod impl_display;
12
13/// A single quorum rule represented as a tree.
14///
15/// `QuorumTree` models one side of a quorum configuration. A consensus
16/// implementation should usually build one tree for read quorums and another
17/// tree for write quorums, then ensure every read quorum intersects every write
18/// quorum.
19///
20/// A child node is selected when it is either an included node ID or a nested
21/// quorum tree whose own quorum rule is satisfied.
22///
23/// # Invariants
24///
25/// - A [`QuorumTree`] represents exactly one quorum rule.
26/// - Child nodes are unique and traversal order is deterministic according to [`Node`] ordering.
27/// - `quorum_size` never exceeds the number of child nodes: construction rejects duplicate children
28///   and unsatisfiable quorum sizes.
29/// - Equality and ordering for [`QuorumTree`] are based only on its canonical ID.
30/// - Canonical IDs are stable identifiers. [`std::fmt::Display`] is human-readable output and is
31///   not a serialization format.
32#[derive(Clone, Debug)]
33pub struct QuorumTree<ID>
34where ID: Ord
35{
36    pub(crate) spec: QuorumTreeSpec<ID>,
37
38    canonical_id: String,
39}
40
41impl<ID> QuorumTree<ID>
42where ID: Ord
43{
44    /// Builds a quorum tree from a quorum size and child nodes.
45    ///
46    /// `quorum_size` is the number of child nodes that must be selected for this
47    /// tree to be selected. A child can be a single ID or another quorum tree.
48    /// If `quorum_size` is `0`, every input satisfies the tree.
49    ///
50    /// # Errors
51    ///
52    /// - [`QuorumTreeError::DuplicateChild`]: a child was given more than once. A duplicate child
53    ///   is always an upstream bug; a tree never contains the same child twice.
54    /// - [`QuorumTreeError::UnsatisfiableQuorum`]: `quorum_size` exceeds the number of child nodes,
55    ///   so no input could satisfy the tree.
56    ///
57    /// # Examples
58    ///
59    /// ```
60    /// use quorum_set::{Node, QuorumSet, QuorumTree, QuorumTreeError};
61    ///
62    /// let tree = QuorumTree::new(2, [
63    ///     Node::Id(1),
64    ///     Node::Id(2),
65    ///     Node::Id(3),
66    /// ]).unwrap();
67    ///
68    /// assert!(tree.is_quorum([1, 2].iter()));
69    /// assert!(!tree.is_quorum([1].iter()));
70    ///
71    /// let err = QuorumTree::new(1, [Node::Id(1), Node::Id(1)]).unwrap_err();
72    /// assert_eq!(
73    ///     QuorumTreeError::DuplicateChild { canonical_id: "Id=1".to_string() },
74    ///     err
75    /// );
76    /// ```
77    pub fn new(
78        quorum_size: u64,
79        nodes: impl IntoIterator<Item = Node<ID>>,
80    ) -> Result<Self, QuorumTreeError>
81    where
82        ID: CanonicalId,
83    {
84        let spec = QuorumTreeSpec::new(quorum_size, nodes)?;
85        let canonical_id = spec.canonical_id();
86        Ok(Self { spec, canonical_id })
87    }
88
89    /// Returns the number of selected child nodes required to satisfy this
90    /// tree.
91    pub fn quorum_size(&self) -> u64 {
92        self.spec.quorum_size()
93    }
94
95    /// Returns this tree's child nodes in canonical order.
96    ///
97    /// Children are unique: construction rejects duplicate child nodes.
98    pub fn children(&self) -> impl Iterator<Item = &Node<ID>> {
99        self.spec.children()
100    }
101
102    /// Returns the canonical ID of this tree.
103    ///
104    /// The canonical ID decides equality and ordering. It is computed once at
105    /// construction, so this accessor does not allocate.
106    pub fn canonical_id(&self) -> &str {
107        &self.canonical_id
108    }
109}
110
111/// Equality and ordering are decided solely by `canonical_id`.
112///
113/// `new()` is the sole constructor and `canonical_id` is the cached canonical
114/// representation of the quorum tree spec. A single string comparison keeps
115/// `BTreeSet` operations cheap; no recursive structural comparison is needed.
116impl<ID> PartialEq for QuorumTree<ID>
117where ID: Ord
118{
119    fn eq(&self, other: &Self) -> bool {
120        self.canonical_id == other.canonical_id
121    }
122}
123
124impl<ID> Eq for QuorumTree<ID> where ID: Ord {}
125
126impl<ID> PartialOrd for QuorumTree<ID>
127where ID: Ord
128{
129    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
130        Some(self.cmp(other))
131    }
132}
133
134impl<ID> Ord for QuorumTree<ID>
135where ID: Ord
136{
137    fn cmp(&self, other: &Self) -> Ordering {
138        self.canonical_id.cmp(&other.canonical_id)
139    }
140}
141
142/// Hashing is based solely on `canonical_id`, consistent with equality.
143impl<ID> Hash for QuorumTree<ID>
144where ID: Ord
145{
146    fn hash<H: Hasher>(&self, state: &mut H) {
147        self.canonical_id.hash(state);
148    }
149}
150
151impl<ID> CanonicalId for QuorumTree<ID>
152where ID: Ord + CanonicalId
153{
154    fn fmt_canonical_id<W>(&self, f: &mut W) -> fmt::Result
155    where W: fmt::Write + ?Sized {
156        write!(f, "{}", self.canonical_id)
157    }
158}
159
160#[cfg(test)]
161mod tests {
162    use std::collections::HashSet;
163
164    use crate::Node;
165    use crate::QuorumTree;
166    use crate::QuorumTreeError;
167
168    fn id(i: u64) -> Node<u64> {
169        Node::Id(i)
170    }
171
172    #[test]
173    fn test_eq_ignores_construction_order() {
174        let a = QuorumTree::new(2, [id(1), id(2), id(3)]).unwrap();
175        let b = QuorumTree::new(2, [id(3), id(1), id(2)]).unwrap();
176        let c = QuorumTree::new(3, [id(1), id(2), id(3)]).unwrap();
177
178        assert_eq!(a, b);
179        assert_eq!(a.canonical_id(), b.canonical_id());
180        assert_ne!(a, c);
181    }
182
183    #[test]
184    fn test_hash_is_consistent_with_eq() {
185        let a = QuorumTree::new(2, [id(1), id(2), id(3)]).unwrap();
186        let b = QuorumTree::new(2, [id(3), id(2), id(1)]).unwrap();
187        let c = QuorumTree::new(3, [id(1), id(2), id(3)]).unwrap();
188
189        let set: HashSet<QuorumTree<u64>> = [a.clone(), b.clone(), c.clone()].into_iter().collect();
190
191        assert_eq!(HashSet::from([a, c]), set);
192    }
193
194    #[test]
195    fn test_canonical_id_accessor() {
196        let tree = QuorumTree::new(2, [id(3), id(1), id(2)]).unwrap();
197
198        assert_eq!("2/(Id=1,Id=2,Id=3)", tree.canonical_id());
199    }
200
201    #[test]
202    fn test_children_are_sorted() {
203        let tree = QuorumTree::new(2, [id(3), id(1), id(2)]).unwrap();
204
205        assert_eq!(
206            vec![id(1), id(2), id(3)],
207            tree.children().cloned().collect::<Vec<_>>()
208        );
209    }
210
211    #[test]
212    fn test_new_rejects_duplicate_child() {
213        let err = QuorumTree::new(2, [id(1), id(2), id(2)]).unwrap_err();
214
215        assert_eq!(
216            QuorumTreeError::DuplicateChild {
217                canonical_id: "Id=2".to_string()
218            },
219            err
220        );
221
222        let sub = QuorumTree::new(1, [id(1), id(2)]).unwrap();
223        let err = QuorumTree::new(2, [Node::Subtree(sub.clone()), Node::Subtree(sub)]).unwrap_err();
224
225        assert_eq!(
226            QuorumTreeError::DuplicateChild {
227                canonical_id: "Subtree=1/(Id=1,Id=2)".to_string(),
228            },
229            err
230        );
231    }
232
233    #[test]
234    fn test_new_rejects_unsatisfiable_quorum() {
235        let err = QuorumTree::new(3, [id(1), id(2)]).unwrap_err();
236
237        assert_eq!(
238            QuorumTreeError::UnsatisfiableQuorum {
239                quorum_size: 3,
240                num_children: 2
241            },
242            err
243        );
244    }
245}
quorum_set/tree/tree.rs

quorum_set/tree/
tree.rs
