quorum_set/quorum/
joint.rs

1use std::collections::BTreeSet;
2use std::collections::btree_set;
3
4use crate::quorum::QuorumBridge;
5use crate::quorum::QuorumIntersection;
6use crate::quorum::QuorumSet;
7
8/// A quorum rule that accepts an ID set only when every one of its rules accepts it.
9///
10/// A membership change can move through a joint of the old and the new rule, whose every quorum
11/// is a quorum of both. An empty `Joint` accepts no set, like an empty `Vec<BTreeSet<ID>>`.
12///
13/// [`ids()`](QuorumSet::ids) returns the union of the IDs of every rule, each ID once.
14///
15/// # Examples
16///
17/// ```
18/// use std::collections::BTreeSet;
19/// use std::num::NonZeroU64;
20///
21/// use quorum_set::{Joint, QuorumSet, ThresholdQuorumSet};
22///
23/// let two = NonZeroU64::new(2).unwrap();
24/// let old = ThresholdQuorumSet::new(two, BTreeSet::from([1, 2, 3]));
25/// let new = ThresholdQuorumSet::new(two, BTreeSet::from([2, 3, 4]));
26/// let joint = Joint::new([old, new]);
27///
28/// // {1,2} holds 2 of the old IDs but only 1 of the new IDs.
29/// let accepts_one_two = joint.is_quorum([1, 2].iter());
30/// assert!(!accepts_one_two);
31/// let accepts_one_two_four = joint.is_quorum([1, 2, 4].iter());
32/// assert!(accepts_one_two_four);
33/// ```
34#[derive(Clone, Debug, PartialEq, Eq)]
35pub struct Joint<Q> {
36    rules: Vec<Q>,
37}
38
39impl<Q> Joint<Q> {
40    /// Builds a rule that accepts an ID set only when every one of `rules` accepts it.
41    pub fn new(rules: impl IntoIterator<Item = Q>) -> Self {
42        let rules = rules.into_iter().collect();
43        Self { rules }
44    }
45
46    /// Returns the rules, in the order they were given.
47    pub fn rules(&self) -> &[Q] {
48        &self.rules
49    }
50}
51
52/// Written by hand: `derive(Default)` would require `Q: Default`.
53impl<Q> Default for Joint<Q> {
54    fn default() -> Self {
55        Self { rules: vec![] }
56    }
57}
58
59impl<Q> QuorumSet for Joint<Q>
60where
61    Q: QuorumSet,
62    Q::Id: Ord,
63{
64    type Id = Q::Id;
65    type Iter = btree_set::IntoIter<Q::Id>;
66
67    fn is_quorum<'a, I>(&self, ids: I) -> bool
68    where
69        Self::Id: 'a,
70        I: Iterator<Item = &'a Self::Id> + Clone,
71    {
72        if self.rules.is_empty() {
73            return false;
74        }
75
76        for rule in &self.rules {
77            if !rule.is_quorum(ids.clone()) {
78                return false;
79            }
80        }
81        true
82    }
83
84    fn ids(&self) -> Self::Iter {
85        let mut ids = BTreeSet::new();
86        for rule in &self.rules {
87            ids.extend(rule.ids());
88        }
89        ids.into_iter()
90    }
91}
92
93/// Two joints are treated as having quorum intersection when some rule of one intersects some
94/// rule of the other: every quorum of a joint is also a quorum of each of its rules, so every
95/// quorum of one joint then intersects every quorum of the other. This is sufficient but not
96/// necessary for that property, so this check answers `None` for some pairs of joints whose
97/// quorums do in fact all intersect.
98impl<Q> QuorumIntersection<Joint<Q>> for Joint<Q>
99where
100    Q: QuorumIntersection<Q>,
101    Q::Id: Ord,
102{
103    /// Return the answer of the rule check when each joint holds one rule. For other joints,
104    /// return `Some(true)` when some rule of `self` intersects some rule of `other`.
105    ///
106    /// When either joint is empty, return `Some(true)`: an empty joint has no quorum, so no pair
107    /// of quorums can be disjoint.
108    ///
109    /// Return `None` for every other pair: two rules that do not intersect prove nothing about
110    /// two joints that contain them.
111    fn intersects_with(&self, other: &Joint<Q>) -> Option<bool> {
112        let either_is_empty = self.rules.is_empty() || other.rules.is_empty();
113        if either_is_empty {
114            return Some(true);
115        }
116
117        let both_uniform = self.rules.len() == 1 && other.rules.len() == 1;
118        if both_uniform {
119            return self.rules[0].intersects_with(&other.rules[0]);
120        }
121
122        for a in &self.rules {
123            for b in &other.rules {
124                let intersects = a.intersects_with(b);
125                if intersects == Some(true) {
126                    return Some(true);
127                }
128            }
129        }
130        None
131    }
132}
133
134/// Builds the joint of the source and target rules.
135impl<Q> QuorumBridge<Joint<Q>> for Joint<Q>
136where
137    Q: QuorumSet + Clone,
138    Q::Id: Ord,
139{
140    /// Return the rules of `self` followed by the rules of `other`. Return an empty joint when
141    /// `self` or `other` is empty: an empty joint has no quorum, so a joint with it has no quorum
142    /// either.
143    fn joint_with(&self, other: Joint<Q>) -> Self {
144        if self.rules.is_empty() || other.rules.is_empty() {
145            return Self::default();
146        }
147        let mut rules = self.rules.clone();
148        rules.extend(other.rules);
149        Self { rules }
150    }
151}
quorum_set/quorum/joint.rs

quorum_set/quorum/
joint.rs
