radicle/git/
canonical.rs

1pub mod error;
2use error::*;
3
4mod convergence;
5use convergence::Convergence;
6
7mod quorum;
8use quorum::{CommitQuorum, CommitQuorumFailure, TagQuorum, TagQuorumFailure};
9
10mod voting;
11
12pub mod effects;
13pub mod rules;
14
15pub use rules::{MatchedRule, RawRule, Rules, ValidRule};
16
17use std::collections::{BTreeMap, BTreeSet};
18use std::fmt;
19use std::marker::PhantomData;
20use std::ops::ControlFlow;
21
22use crate::git::fmt::Namespaced;
23
24use crate::prelude::Did;
25
26use super::fmt::Qualified;
27use crate::git::Oid;
28
29/// A marker for the initial state of [`Canonical`], after construction using
30/// [`Canonical::new`].
31pub struct Initial;
32
33/// A marker for the state of [`Canonical`] once it has found objects for the
34/// calculation, using [`Canonical::find_objects`].
35pub struct ObjectsFound;
36
37/// [`Canonical`] captures the state for finding the quorum between a set of
38/// [`Did`]s and their references, attempting to agree on a Git commit or tag.
39///
40/// Construction happens through [`Canonical::new`], at which point you must use
41/// [`Canonical::find_objects`] so that the state has the set of [`Object`]s it
42/// must use for the quorum calculation.
43///
44/// At this point, the caller can either call [`Canonical::quorum`] to find the
45/// quorum, or modify the calculation by produce a [`CanonicalWithConvergence`]
46/// using [`Canonical::with_convergence`], and then using
47/// [`CanonicalWithConvergence::quorum`].
48pub struct Canonical<'a, 'b, 'r, R, T> {
49    refname: Qualified<'a>,
50    rule: &'b ValidRule,
51    repo: &'r R,
52    objects: BTreeMap<Did, Object>,
53    missing: Missing,
54    _marker: PhantomData<T>,
55}
56
57impl<'a, 'b, 'r, R, T> fmt::Debug for Canonical<'a, 'b, 'r, R, T> {
58    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
59        f.debug_struct("Canonical")
60            .field("refname", &self.refname)
61            .field("rule", &self.rule)
62            .field("objects", &self.objects)
63            .field("missing", &self.missing)
64            .finish()
65    }
66}
67
68/// Similar to [`Canonical`], however it checks that a new vote of a single
69/// [`Did`] converges with any other [`Did`], to then see if that provides a
70/// different quorum result.
71pub struct CanonicalWithConvergence<'a, 'b, 'r, R> {
72    canonical: Canonical<'a, 'b, 'r, R, ObjectsFound>,
73    convergence: Convergence<'r, R>,
74}
75
76impl<'a, 'b, 'r, R> fmt::Debug for CanonicalWithConvergence<'a, 'b, 'r, R> {
77    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
78        f.debug_struct("CanonicalWithConvergence")
79            .field("canonical", &self.canonical)
80            .field("convergence", &self.convergence)
81            .finish()
82    }
83}
84
85impl<'a, 'b, 'r, R> AsRef<Canonical<'a, 'b, 'r, R, ObjectsFound>>
86    for CanonicalWithConvergence<'a, 'b, 'r, R>
87{
88    fn as_ref(&self) -> &Canonical<'a, 'b, 'r, R, ObjectsFound> {
89        &self.canonical
90    }
91}
92
93impl<'a, 'b, 'r, R> Canonical<'a, 'b, 'r, R, Initial>
94where
95    R: effects::Ancestry + effects::FindMergeBase + effects::FindObjects,
96{
97    /// Construct a new [`Canonical`] with the given [`Qualified`] reference, a
98    /// canonical reference [`ValidRule`] for that reference, and the Git
99    /// repository to load and check the Git data.
100    pub fn new(refname: Qualified<'a>, rule: &'b ValidRule, repo: &'r R) -> Self {
101        Self {
102            refname,
103            rule,
104            repo,
105            missing: Missing::default(),
106            objects: BTreeMap::new(),
107            _marker: PhantomData,
108        }
109    }
110
111    /// Find the objects for the [`Canonical`] computation, and prepare it to
112    /// find the quorum.
113    pub fn find_objects(
114        self,
115    ) -> Result<Canonical<'a, 'b, 'r, R, ObjectsFound>, effects::FindObjectsError> {
116        let FoundObjects {
117            objects,
118            missing_refs,
119            missing_objects,
120        } = self
121            .repo
122            .find_objects(&self.refname, self.rule.allowed().iter())?;
123        let missing = Missing {
124            refs: missing_refs,
125            objects: missing_objects,
126        };
127        Ok(Canonical {
128            refname: self.refname,
129            rule: self.rule,
130            repo: self.repo,
131            missing,
132            objects,
133            _marker: PhantomData,
134        })
135    }
136}
137
138impl<'a, 'b, 'r, R> Canonical<'a, 'b, 'r, R, ObjectsFound>
139where
140    R: effects::Ancestry + effects::FindMergeBase + effects::FindObjects,
141{
142    /// Adds the check for convergence before finding the quorum.
143    pub fn with_convergence(
144        self,
145        candidate: Did,
146        object: Object,
147    ) -> CanonicalWithConvergence<'a, 'b, 'r, R> {
148        let convergence = Convergence::new(self.repo, candidate, object);
149        CanonicalWithConvergence {
150            canonical: self,
151            convergence,
152        }
153    }
154
155    /// Find the [`Quorum`] for the canonical computation.
156    pub fn quorum(self) -> Result<Quorum<'a>, QuorumError> {
157        let mut finder = QuorumFinder::new(self.refname, self.rule, self.objects.values());
158        while let ControlFlow::Continue(pairs) = finder.find_merge_bases() {
159            let mut bases = Vec::with_capacity(pairs.size_hint().0);
160            for (a, b) in pairs {
161                bases.push(self.repo.merge_base(a, b)?);
162            }
163            finder.found_merge_bases(bases.into_iter());
164        }
165        let refname = finder.refname.clone();
166        let threshold = (*finder.rule.threshold()).into();
167        let results = finder.find_quorum();
168        match results {
169            (Ok(commit), Err(_)) => Ok(commit),
170            (Err(_), Ok(tag)) => Ok(tag),
171            (Ok(_), Ok(_)) => Err(QuorumError::DifferentTypes {
172                refname: refname.to_string(),
173            }),
174            (Err(ec), Err(eq)) => Err(Self::convert_failures(
175                ec,
176                eq,
177                refname.to_string(),
178                threshold,
179            )),
180        }
181    }
182
183    /// If there are [`Missing`] objects, these may be reported by the caller,
184    /// and if further objects are found, then these can be marked using
185    /// [`Canonical::found_objects`].
186    pub fn missing(&self) -> &Missing {
187        &self.missing
188    }
189
190    /// Mark the `objects` provided as found, removing them from the [`Missing`]
191    /// set.
192    pub fn found_objects(&mut self, objects: impl IntoIterator<Item = (Did, Object)>) {
193        let objects = objects.into_iter();
194        for (did, object) in objects {
195            self.missing.found(&did, &self.refname);
196            self.objects.insert(did, object);
197        }
198    }
199
200    fn convert_failures(
201        commit: CommitQuorumFailure,
202        tag: TagQuorumFailure,
203        refname: String,
204        threshold: usize,
205    ) -> QuorumError {
206        match (commit, tag) {
207            (CommitQuorumFailure::NoCandidates, TagQuorumFailure::NoCandidates) => {
208                QuorumError::NoCandidates { refname, threshold }
209            }
210            (CommitQuorumFailure::NoCandidates, TagQuorumFailure::DivergingTags { candidates }) => {
211                QuorumError::DivergingTags {
212                    refname,
213                    threshold,
214                    candidates,
215                }
216            }
217            (
218                CommitQuorumFailure::DivergingCommits {
219                    base,
220                    longest,
221                    candidate,
222                },
223                _,
224            ) => QuorumError::DivergingCommits {
225                refname,
226                threshold,
227                base,
228                longest,
229                head: candidate,
230            },
231            (CommitQuorumFailure::NoMergeBase { a, b }, _) => {
232                #[derive(thiserror::Error, Debug)]
233                #[error("no existing merge base found for commit quorum")]
234                struct NoMergeBase;
235
236                effects::MergeBaseError::new(a, b, NoMergeBase).into()
237            }
238        }
239    }
240}
241
242impl<'a, 'b, 'r, R> CanonicalWithConvergence<'a, 'b, 'r, R>
243where
244    R: effects::Ancestry + effects::FindMergeBase + effects::FindObjects,
245{
246    /// Find the [`QuorumWithConvergence`] for the canonical computation.
247    pub fn quorum(mut self) -> Result<QuorumWithConvergence<'a>, QuorumError> {
248        let converges = match self.convergence.check(self.canonical.objects.iter())? {
249            Some((candidate, object)) => {
250                if self.canonical.objects.is_empty()
251                    || self.canonical.rule.allowed().is_only(&candidate)
252                {
253                    self.canonical.objects.insert(candidate, object);
254                }
255                true
256            }
257            None => false,
258        };
259        let quorum = self.canonical.quorum()?;
260        Ok(QuorumWithConvergence { quorum, converges })
261    }
262}
263
264/// The result of finding a quorum.
265#[derive(Clone, Debug, PartialEq, Eq)]
266pub struct Quorum<'a> {
267    /// The reference the quorum has been found for.
268    pub refname: Qualified<'a>,
269    /// The object the reference should be updated to.
270    pub object: Object,
271}
272
273/// Similar to [`Quorum`], but also reports whether the candidate converged with
274/// one of the other voters.
275#[derive(Clone, Debug, PartialEq, Eq)]
276pub struct QuorumWithConvergence<'a> {
277    pub quorum: Quorum<'a>,
278    pub converges: bool,
279}
280
281/// Helper to perform the quorum check for both a [`TagQuorum`] and
282/// [`CommitQuorum`].
283#[derive(Debug)]
284struct QuorumFinder<'a, 'b> {
285    refname: Qualified<'a>,
286    rule: &'b ValidRule,
287    tag_quorum: TagQuorum,
288    commit_quorum: CommitQuorum,
289}
290
291impl<'a, 'b> QuorumFinder<'a, 'b> {
292    fn new<'c, I>(refname: Qualified<'a>, rule: &'b ValidRule, objects: I) -> Self
293    where
294        I: Iterator<Item = &'c Object> + Clone,
295    {
296        let threshold = *rule.threshold();
297        let tag_quorum = TagQuorum::new(objects.clone(), threshold.into());
298        let commit_quorum = CommitQuorum::new(objects, threshold.into());
299        Self {
300            refname,
301            rule,
302            tag_quorum,
303            commit_quorum,
304        }
305    }
306
307    fn find_merge_bases(&mut self) -> ControlFlow<(), impl Iterator<Item = (Oid, Oid)>> {
308        match self.commit_quorum.next_candidate() {
309            Some(candidate) => ControlFlow::Continue(candidate),
310            None => ControlFlow::Break(()),
311        }
312    }
313
314    fn found_merge_bases<I>(&mut self, bases: I)
315    where
316        I: Iterator<Item = MergeBase>,
317    {
318        self.commit_quorum.found_merge_bases(bases);
319    }
320
321    fn find_quorum(
322        self,
323    ) -> (
324        Result<Quorum<'a>, quorum::CommitQuorumFailure>,
325        Result<Quorum<'a>, quorum::TagQuorumFailure>,
326    ) {
327        let commit = self.commit_quorum.find_quorum().map(|id| Quorum {
328            refname: self.refname.clone(),
329            object: Object::Commit { id },
330        });
331        let tag = self.tag_quorum.find_quorum().map(|id| Quorum {
332            refname: self.refname.clone(),
333            object: Object::Tag { id },
334        });
335        (commit, tag)
336    }
337}
338
339/// Record a merge base between `a` and `b`.
340#[derive(Clone, Copy, Debug, PartialEq, Eq)]
341pub struct MergeBase {
342    /// The first commit for the merge base.
343    pub a: Oid,
344    /// The second commit that is being compared against for the merge base.
345    pub b: Oid,
346    /// The computed merge base commit.
347    pub base: Oid,
348}
349
350impl MergeBase {
351    /// The merge base of the same commit is the commit itself.
352    #[cfg(test)]
353    pub fn trivial(oid: Oid) -> Self {
354        Self {
355            a: oid,
356            b: oid,
357            base: oid,
358        }
359    }
360
361    /// The result of a merge base computation is trivial.
362    pub fn is_trivial(&self) -> bool {
363        if self.a == self.b {
364            // By definition, the merge base of a commit and itself is itself.
365            // These asserts will catch our fall in case we set an invalid
366            // base in this case.
367            debug_assert_eq!(self.a, self.base);
368            debug_assert_eq!(self.b, self.base);
369            true
370        } else {
371            false
372        }
373    }
374
375    /// Collapses a non-trivial and linear result of a merge base computation
376    /// into a single commit, if possible.
377    pub fn linear(self) -> Option<Oid> {
378        if self.is_trivial() || (self.a != self.base && self.b != self.base) {
379            None
380        } else {
381            Some(self.base)
382        }
383    }
384}
385
386/// The supported type of Git object and its [`Oid`], for canonical computation.
387#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
388pub enum Object {
389    Commit { id: Oid },
390    Tag { id: Oid },
391}
392
393impl Object {
394    pub fn new(obj: &crate::git::raw::Object) -> Option<Self> {
395        obj.kind().and_then(|kind| match kind {
396            crate::git::raw::ObjectType::Commit => Some(Self::Commit {
397                id: obj.id().into(),
398            }),
399            crate::git::raw::ObjectType::Tag => Some(Self::Tag {
400                id: obj.id().into(),
401            }),
402            _ => None,
403        })
404    }
405
406    /// The [`Oid`] of the [`Object`]
407    pub fn id(&self) -> Oid {
408        match self {
409            Object::Commit { id } => *id,
410            Object::Tag { id } => *id,
411        }
412    }
413
414    /// Checks if the object is a Git commit.
415    pub fn is_commit(&self) -> bool {
416        matches!(self, Self::Commit { .. })
417    }
418
419    /// Checks if the object is a Git tag.
420    pub fn is_tag(&self) -> bool {
421        matches!(self, Self::Commit { .. })
422    }
423
424    /// Returns the [`ObjectType`] of the [`Object`].
425    pub fn object_type(&self) -> ObjectType {
426        match self {
427            Object::Commit { .. } => ObjectType::Commit,
428            Object::Tag { .. } => ObjectType::Tag,
429        }
430    }
431}
432
433/// Supported Git object types for canonical computation
434#[derive(Clone, Copy, Debug, PartialEq, Eq)]
435pub enum ObjectType {
436    /// The Git object corresponds to a commit.
437    Commit,
438    /// The Git object corresponds to a tag.
439    Tag,
440}
441
442impl fmt::Display for ObjectType {
443    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
444        match self {
445            ObjectType::Commit => f.write_str("commit"),
446            ObjectType::Tag => f.write_str("tag"),
447        }
448    }
449}
450
451/// The result of checking the relationship between two commits in the commit graph.
452#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
453pub struct GraphAheadBehind {
454    /// The number of commits the given commit is ahead of the other.
455    pub ahead: usize,
456    /// The number of commits the given commit is behind the other.
457    pub behind: usize,
458}
459
460impl GraphAheadBehind {
461    /// Whether self represents a linear history between two commits.
462    ///
463    /// The following three conditions are equivalent characterizations of
464    /// a linear history:
465    ///  1. One commit is ahead and not behind of the other.
466    ///  2. One commit is behind and not ahead of the other.
467    ///  3. One commit can be "fast-forwarded" to the other.
468    pub fn is_linear(&self) -> bool {
469        self.ahead * self.behind == 0
470    }
471}
472
473/// The result of finding a set of objects in a Git repository.
474#[derive(Clone, Debug, PartialEq, Eq)]
475pub struct FoundObjects {
476    /// The found objects, and under which [`Did`] they were found.
477    pub objects: BTreeMap<Did, Object>,
478    /// Any missing references while attempting to find the objects.
479    pub missing_refs: BTreeSet<Namespaced<'static>>,
480    // TODO(finto): I think this doesn't make sense now that we use only one
481    // repository.
482    /// Any missing objects, where the reference was found, but the object was
483    /// missing.
484    pub missing_objects: BTreeMap<Did, Oid>,
485}
486
487/// [`Missing`] marks whether there were any missing references or objects.
488#[derive(Clone, Debug, Default, PartialEq, Eq)]
489pub struct Missing {
490    pub refs: BTreeSet<Namespaced<'static>>,
491    pub objects: BTreeMap<Did, Oid>,
492}
493
494impl Missing {
495    fn found<'a>(&mut self, did: &Did, refname: &Qualified<'a>) {
496        self.objects.remove(did);
497        self.refs
498            .remove(&refname.with_namespace((did.as_key()).into()).to_owned());
499    }
500}
501
502#[cfg(test)]
503#[allow(clippy::unwrap_used)]
504mod tests {
505
506    use super::*;
507    use crate::assert_matches;
508    use crate::git;
509    use crate::node::device::Device;
510    use crate::test::fixtures;
511
512    /// Test helper to construct a Canonical and get the quorum
513    fn quorum(
514        heads: &[crate::git::Oid],
515        threshold: usize,
516        repo: &crate::git::raw::Repository,
517    ) -> Result<Oid, QuorumError> {
518        let refname = git::refs::branch(crate::git::fmt::RefStr::try_from_str("master").unwrap());
519
520        let mut delegates = Vec::new();
521        for (i, head) in heads.iter().enumerate() {
522            let signer = Device::mock_from_seed([(i + 1) as u8; 32]);
523            let did = Did::from(signer.public_key());
524            delegates.push(did);
525            let ns = git::fmt::Component::from(signer.public_key());
526            repo.reference(refname.with_namespace(ns).as_str(), head.into(), true, "")
527                .unwrap();
528        }
529
530        let rule: RawRule = crate::git::canonical::rules::Rule::new(
531            crate::git::canonical::rules::Allowed::Delegates,
532            threshold,
533        );
534        let delegates = crate::identity::doc::Delegates::new(delegates).unwrap();
535        let rule = rule.validate(&mut || delegates.clone()).unwrap();
536
537        Canonical::new(refname, &rule, repo)
538            .find_objects()
539            .unwrap()
540            .quorum()
541            .map(|Quorum { object, .. }| object.id())
542    }
543
544    fn commit(id: &str) -> Object {
545        Object::Commit {
546            id: id.parse().unwrap(),
547        }
548    }
549
550    fn tag(id: &str) -> Object {
551        Object::Tag {
552            id: id.parse().unwrap(),
553        }
554    }
555
556    #[test]
557    fn test_quorum_properties() {
558        let tmp = tempfile::tempdir().unwrap();
559        let (repo, c0) = fixtures::repository(tmp.path());
560        let c0: crate::git::Oid = c0.into();
561        let a1 = fixtures::commit("A1", &[c0.into()], &repo);
562        let a2 = fixtures::commit("A2", &[a1.into()], &repo);
563        let d1 = fixtures::commit("D1", &[c0.into()], &repo);
564        let c1 = fixtures::commit("C1", &[c0.into()], &repo);
565        let c2 = fixtures::commit("C2", &[c1.into()], &repo);
566        let b2 = fixtures::commit("B2", &[c1.into()], &repo);
567        let a1 = fixtures::commit("A1", &[c0.into()], &repo);
568        let m1 = fixtures::commit("M1", &[c2.into(), b2.into()], &repo);
569        let m2 = fixtures::commit("M2", &[a1.into(), b2.into()], &repo);
570        let mut rng = fastrand::Rng::new();
571        let choices = [c0, c1, c2, b2, a1, a2, d1, m1, m2];
572
573        for _ in 0..100 {
574            let count = rng.usize(1..=choices.len());
575            let threshold = rng.usize(1..=count);
576            let mut heads = Vec::new();
577
578            for _ in 0..count {
579                let ix = rng.usize(0..choices.len());
580                heads.push(choices[ix]);
581            }
582            rng.shuffle(&mut heads);
583
584            if let Ok(canonical) = quorum(&heads, threshold, &repo) {
585                assert!(heads.contains(&canonical));
586            }
587        }
588    }
589
590    #[test]
591    fn test_quorum_different_types() {
592        let tmp = tempfile::tempdir().unwrap();
593        let (repo, c0) = fixtures::repository(tmp.path());
594        let t0 = fixtures::tag("v1", "", c0, &repo);
595
596        assert_matches!(
597            quorum(&[c0.into(), t0], 1, &repo),
598            Err(QuorumError::DifferentTypes { .. })
599        );
600    }
601
602    #[test]
603    fn test_commit_quorum_groups() {
604        let c0 = commit("f2de534b5e81d7c6e2dcaf58c3dd91573c0a0354");
605        let c1 = commit("bfb1a513e420eade90b0e6be64117b861b16ecb5");
606        let c2 = commit("8fc5160702365f231c77732a8fa162379e54f57a");
607
608        //   C1  C2
609        //    \ /
610        //     C0
611
612        let mut cq = CommitQuorum::new([c1, c2, c1, c2].iter(), 2);
613        cq.found_merge_bases([MergeBase {
614            a: c1.id(),
615            b: c2.id(),
616            base: c0.id(),
617        }]);
618        assert_matches!(
619            cq.find_quorum(),
620            Err(CommitQuorumFailure::DivergingCommits { .. })
621        );
622
623        let mut cq = CommitQuorum::new([c1, c2].iter(), 1);
624        cq.found_merge_bases([MergeBase {
625            a: c1.id(),
626            b: c2.id(),
627            base: c0.id(),
628        }]);
629        assert_matches!(
630            cq.find_quorum(),
631            Err(CommitQuorumFailure::DivergingCommits { .. })
632        );
633    }
634
635    #[test]
636    fn test_tag_quorum() {
637        let t1 = tag("0480391dd7312d35c79a455ec5d004657260b358");
638        let t2 = tag("a2eec713ec5c287ecdf13a0180f68acfef7962d0");
639
640        assert_eq!(
641            TagQuorum::new([t1].iter(), 1).find_quorum().unwrap(),
642            t1.id()
643        );
644        assert_eq!(
645            TagQuorum::new([t1, t1].iter(), 2).find_quorum().unwrap(),
646            t1.id()
647        );
648        assert_matches!(
649            TagQuorum::new([t1, t2].iter(), 1).find_quorum(),
650            Err(TagQuorumFailure::DivergingTags { .. })
651        );
652    }
653
654    #[test]
655    fn test_commit_quorum_single() {
656        let c0 = commit("f2de534b5e81d7c6e2dcaf58c3dd91573c0a0354");
657        let c1 = commit("bfb1a513e420eade90b0e6be64117b861b16ecb5");
658        let c2 = commit("8fc5160702365f231c77732a8fa162379e54f57a");
659        assert_eq!(
660            CommitQuorum::new([c0].iter(), 1).find_quorum().unwrap(),
661            c0.id()
662        );
663        assert_eq!(
664            CommitQuorum::new([c1].iter(), 1).find_quorum().unwrap(),
665            c1.id()
666        );
667        assert_eq!(
668            CommitQuorum::new([c2].iter(), 1).find_quorum().unwrap(),
669            c2.id()
670        );
671    }
672
673    #[test]
674    fn test_commit_quorum_linear() {
675        let c0 = commit("f2de534b5e81d7c6e2dcaf58c3dd91573c0a0354");
676        let c1 = commit("bfb1a513e420eade90b0e6be64117b861b16ecb5");
677        let c2 = commit("8fc5160702365f231c77732a8fa162379e54f57a");
678        //   C2
679        //   |
680        //  C1
681        //  |
682        // C0
683        let merge_bases = [
684            MergeBase {
685                a: c2.id(),
686                b: c1.id(),
687                base: c1.id(),
688            },
689            MergeBase {
690                a: c2.id(),
691                b: c0.id(),
692                base: c0.id(),
693            },
694            MergeBase {
695                a: c1.id(),
696                b: c0.id(),
697                base: c0.id(),
698            },
699            MergeBase::trivial(c2.id()),
700            MergeBase::trivial(c1.id()),
701            MergeBase::trivial(c0.id()),
702        ];
703
704        let mut cq = CommitQuorum::new([c1, c2].iter(), 1);
705        cq.found_merge_bases(merge_bases);
706        assert_eq!(cq.find_quorum().unwrap(), c2.id());
707
708        let mut cq = CommitQuorum::new([c1, c2].iter(), 2);
709        cq.found_merge_bases(merge_bases);
710        assert_eq!(cq.find_quorum().unwrap(), c1.id());
711
712        let mut cq = CommitQuorum::new([c0, c1, c2].iter(), 3);
713        cq.found_merge_bases(merge_bases);
714        assert_eq!(cq.find_quorum().unwrap(), c0.id());
715
716        let mut cq = CommitQuorum::new([c1, c1, c2].iter(), 2);
717        cq.found_merge_bases(merge_bases);
718        assert_eq!(cq.find_quorum().unwrap(), c1.id());
719
720        let mut cq = CommitQuorum::new([c1, c1, c2].iter(), 1);
721        cq.found_merge_bases(merge_bases);
722        assert_eq!(cq.find_quorum().unwrap(), c2.id());
723
724        let mut cq = CommitQuorum::new([c2, c2, c1].iter(), 1);
725        cq.found_merge_bases(merge_bases);
726        assert_eq!(cq.find_quorum().unwrap(), c2.id());
727    }
728
729    #[test]
730    fn test_commit_quorum_two_way_fork() {
731        let c0 = commit("f2de534b5e81d7c6e2dcaf58c3dd91573c0a0354");
732        let c1 = commit("bfb1a513e420eade90b0e6be64117b861b16ecb5");
733        let c2 = commit("8fc5160702365f231c77732a8fa162379e54f57a");
734        let b2 = commit("037a148170e3d41524b7c482a4798e5c2daeaa00");
735
736        eprintln!("C0: {}", c0.id());
737        eprintln!("C1: {}", c1.id());
738        eprintln!("C2: {}", c2.id());
739        eprintln!("B2: {}", b2.id());
740
741        // B2 C2
742        //   \|
743        //   C1
744        //   |
745        //  C0
746        let merge_bases = [
747            MergeBase {
748                a: b2.id(),
749                b: c2.id(),
750                base: c1.id(),
751            },
752            MergeBase {
753                a: c2.id(),
754                b: c1.id(),
755                base: c1.id(),
756            },
757            MergeBase {
758                a: b2.id(),
759                b: c1.id(),
760                base: c1.id(),
761            },
762            MergeBase {
763                a: c1.id(),
764                b: c0.id(),
765                base: c0.id(),
766            },
767            MergeBase::trivial(b2.id()),
768            MergeBase::trivial(c2.id()),
769            MergeBase::trivial(c1.id()),
770            MergeBase::trivial(c0.id()),
771        ];
772
773        let mut cq = CommitQuorum::new([c1, c2, b2].iter(), 1);
774        cq.found_merge_bases(merge_bases);
775        assert_matches!(
776            cq.find_quorum(),
777            Err(CommitQuorumFailure::DivergingCommits { .. })
778        );
779
780        let mut cq = CommitQuorum::new([c2, b2].iter(), 1);
781        cq.found_merge_bases(merge_bases);
782        assert_matches!(
783            cq.find_quorum(),
784            Err(CommitQuorumFailure::DivergingCommits { .. })
785        );
786
787        let mut cq = CommitQuorum::new([b2, c2].iter(), 1);
788        cq.found_merge_bases(merge_bases);
789        assert_matches!(
790            cq.find_quorum(),
791            Err(CommitQuorumFailure::DivergingCommits { .. })
792        );
793
794        // Note for the next two cases we only give enough merge base
795        // information so that the quorum fails. If we provided all
796        // `merge_bases`, it would mean that c0 could be chosen as the quourum.
797        let mut cq = CommitQuorum::new([c2, b2].iter(), 2);
798        cq.found_merge_bases([MergeBase {
799            a: b2.id(),
800            b: c2.id(),
801            base: c1.id(),
802        }]);
803        assert_matches!(cq.find_quorum(), Err(CommitQuorumFailure::NoCandidates));
804
805        let mut cq = CommitQuorum::new([b2, c2].iter(), 2);
806        cq.found_merge_bases([MergeBase {
807            a: b2.id(),
808            b: c2.id(),
809            base: c1.id(),
810        }]);
811        assert_matches!(cq.find_quorum(), Err(CommitQuorumFailure::NoCandidates));
812
813        let mut cq = CommitQuorum::new([c1, c2, b2].iter(), 2);
814        cq.found_merge_bases(merge_bases);
815        assert_eq!(cq.find_quorum().unwrap(), c1.id());
816
817        let mut cq = CommitQuorum::new([c1, c2, b2].iter(), 3);
818        cq.found_merge_bases(merge_bases);
819        assert_eq!(cq.find_quorum().unwrap(), c1.id());
820
821        let mut cq = CommitQuorum::new([b2, b2, c2].iter(), 2);
822        cq.found_merge_bases(merge_bases);
823        assert_eq!(cq.find_quorum().unwrap(), b2.id());
824
825        let mut cq = CommitQuorum::new([b2, c2, c2].iter(), 2);
826        cq.found_merge_bases(merge_bases);
827        assert_eq!(cq.find_quorum().unwrap(), c2.id());
828
829        let mut cq = CommitQuorum::new([b2, b2, c2, c2].iter(), 2);
830        cq.found_merge_bases(merge_bases);
831        assert_matches!(
832            cq.find_quorum(),
833            Err(CommitQuorumFailure::DivergingCommits { .. })
834        );
835    }
836
837    #[test]
838    fn test_commit_quorum_three_way_fork() {
839        let c1 = commit("bfb1a513e420eade90b0e6be64117b861b16ecb5");
840        let c2 = commit("8fc5160702365f231c77732a8fa162379e54f57a");
841        let c3 = commit("07c2a0f856e0d6b08115f98a265df88c4e507fa0");
842        let b2 = commit("037a148170e3d41524b7c482a4798e5c2daeaa00");
843
844        // B2 C2 C3
845        //  \ | /
846        //    C1
847        //    |
848        //    C0
849        let mut cq = CommitQuorum::new([b2, c2, c2].iter(), 2);
850        cq.found_merge_bases([
851            MergeBase {
852                a: b2.id(),
853                b: c2.id(),
854                base: c1.id(),
855            },
856            MergeBase::trivial(b2.id()),
857        ]);
858        assert_eq!(cq.find_quorum().unwrap(), c2.id());
859
860        let mut cq = CommitQuorum::new([b2, c2, c2].iter(), 3);
861        cq.found_merge_bases([
862            MergeBase {
863                a: b2.id(),
864                b: c2.id(),
865                base: c1.id(),
866            },
867            MergeBase::trivial(c2.id()),
868        ]);
869        assert_eq!(cq.find_quorum(), Err(CommitQuorumFailure::NoCandidates));
870
871        let mut cq = CommitQuorum::new([b2, c2, b2, c2].iter(), 3);
872        cq.found_merge_bases([
873            MergeBase {
874                a: b2.id(),
875                b: c2.id(),
876                base: c1.id(),
877            },
878            MergeBase {
879                a: c2.id(),
880                b: b2.id(),
881                base: c1.id(),
882            },
883            MergeBase::trivial(b2.id()),
884            MergeBase::trivial(c2.id()),
885        ]);
886        assert_eq!(cq.find_quorum(), Err(CommitQuorumFailure::NoCandidates));
887
888        let mut cq = CommitQuorum::new([c3, b2, c2, b2, c2, c3].iter(), 3);
889        cq.found_merge_bases([
890            MergeBase {
891                a: c3.id(),
892                b: b2.id(),
893                base: c1.id(),
894            },
895            MergeBase {
896                a: c3.id(),
897                b: c2.id(),
898                base: c1.id(),
899            },
900            MergeBase {
901                a: b2.id(),
902                b: c2.id(),
903                base: c1.id(),
904            },
905            MergeBase {
906                a: c2.id(),
907                b: b2.id(),
908                base: c1.id(),
909            },
910            MergeBase::trivial(b2.id()),
911            MergeBase::trivial(c2.id()),
912            MergeBase::trivial(c3.id()),
913        ]);
914        assert_eq!(cq.find_quorum(), Err(CommitQuorumFailure::NoCandidates));
915    }
916
917    #[test]
918    fn test_commit_quorum_fork_of_a_fork() {
919        let c0 = commit("f2de534b5e81d7c6e2dcaf58c3dd91573c0a0354");
920        let c1 = commit("bfb1a513e420eade90b0e6be64117b861b16ecb5");
921        let c2 = commit("8fc5160702365f231c77732a8fa162379e54f57a");
922        let b2 = commit("037a148170e3d41524b7c482a4798e5c2daeaa00");
923        let a1 = commit("2224468e22b30359611d880ccf0850d023f86f9b");
924
925        //  B2 C2
926        //    \|
927        // A1 C1
928        //   \|
929        //   C0
930        let mut cq = CommitQuorum::new([c2, b2, a1].iter(), 1);
931        cq.found_merge_bases([
932            MergeBase {
933                a: c2.id(),
934                b: b2.id(),
935                base: c1.id(),
936            },
937            MergeBase {
938                a: c2.id(),
939                b: a1.id(),
940                base: c0.id(),
941            },
942            MergeBase {
943                a: b2.id(),
944                b: a1.id(),
945                base: c0.id(),
946            },
947        ]);
948        assert_matches!(
949            cq.find_quorum(),
950            Err(CommitQuorumFailure::DivergingCommits { .. })
951        );
952        let mut cq = CommitQuorum::new([c2, b2, a1].iter(), 2);
953        cq.found_merge_bases([
954            MergeBase {
955                a: c2.id(),
956                b: b2.id(),
957                base: c1.id(),
958            },
959            MergeBase {
960                a: c2.id(),
961                b: a1.id(),
962                base: c0.id(),
963            },
964            MergeBase {
965                a: b2.id(),
966                b: a1.id(),
967                base: c0.id(),
968            },
969        ]);
970        assert_eq!(cq.find_quorum(), Err(CommitQuorumFailure::NoCandidates));
971
972        let mut cq = CommitQuorum::new([c2, b2, a1].iter(), 3);
973        cq.found_merge_bases([
974            MergeBase {
975                a: c2.id(),
976                b: b2.id(),
977                base: c1.id(),
978            },
979            MergeBase {
980                a: c2.id(),
981                b: a1.id(),
982                base: c0.id(),
983            },
984            MergeBase {
985                a: b2.id(),
986                b: a1.id(),
987                base: c0.id(),
988            },
989        ]);
990        assert_eq!(cq.find_quorum(), Err(CommitQuorumFailure::NoCandidates));
991
992        let mut cq = CommitQuorum::new([c1, c2, b2, a1].iter(), 4);
993        cq.found_merge_bases([
994            MergeBase {
995                a: c1.id(),
996                b: c2.id(),
997                base: c1.id(),
998            },
999            MergeBase {
1000                a: c1.id(),
1001                b: b2.id(),
1002                base: c1.id(),
1003            },
1004            MergeBase {
1005                a: c1.id(),
1006                b: a1.id(),
1007                base: c0.id(),
1008            },
1009            MergeBase {
1010                a: c2.id(),
1011                b: b2.id(),
1012                base: c1.id(),
1013            },
1014            MergeBase {
1015                a: c2.id(),
1016                b: a1.id(),
1017                base: c0.id(),
1018            },
1019            MergeBase {
1020                a: b2.id(),
1021                b: a1.id(),
1022                base: c0.id(),
1023            },
1024        ]);
1025        assert_eq!(cq.find_quorum(), Err(CommitQuorumFailure::NoCandidates));
1026
1027        let all_merge_bases = [
1028            MergeBase {
1029                a: c0.id(),
1030                b: c1.id(),
1031                base: c0.id(),
1032            },
1033            MergeBase {
1034                a: c0.id(),
1035                b: c2.id(),
1036                base: c0.id(),
1037            },
1038            MergeBase {
1039                a: c0.id(),
1040                b: b2.id(),
1041                base: c0.id(),
1042            },
1043            MergeBase {
1044                a: c0.id(),
1045                b: a1.id(),
1046                base: c0.id(),
1047            },
1048            MergeBase {
1049                a: c1.id(),
1050                b: c2.id(),
1051                base: c1.id(),
1052            },
1053            MergeBase {
1054                a: c1.id(),
1055                b: b2.id(),
1056                base: c1.id(),
1057            },
1058            MergeBase {
1059                a: c1.id(),
1060                b: a1.id(),
1061                base: c0.id(),
1062            },
1063            MergeBase {
1064                a: c2.id(),
1065                b: b2.id(),
1066                base: c1.id(),
1067            },
1068            MergeBase {
1069                a: c2.id(),
1070                b: a1.id(),
1071                base: c0.id(),
1072            },
1073            MergeBase {
1074                a: b2.id(),
1075                b: a1.id(),
1076                base: c0.id(),
1077            },
1078        ];
1079        let mut cq = CommitQuorum::new([c0, c1, c2, b2, a1].iter(), 2);
1080        cq.found_merge_bases(all_merge_bases);
1081        assert_eq!(cq.find_quorum().unwrap(), c1.id());
1082
1083        let mut cq = CommitQuorum::new([c0, c1, c2, b2, a1].iter(), 3);
1084        cq.found_merge_bases(all_merge_bases);
1085        assert_eq!(cq.find_quorum().unwrap(), c1.id());
1086
1087        let mut cq = CommitQuorum::new([c0, c2, b2, a1].iter(), 3);
1088        cq.found_merge_bases(all_merge_bases);
1089        assert_eq!(cq.find_quorum().unwrap(), c0.id());
1090
1091        let mut cq = CommitQuorum::new([c0, c1, c2, b2, a1].iter(), 4);
1092        cq.found_merge_bases(all_merge_bases);
1093        assert_eq!(cq.find_quorum().unwrap(), c0.id());
1094
1095        let mut cq = CommitQuorum::new([a1, a1, c2, c2, c1].iter(), 2);
1096        cq.found_merge_bases([
1097            MergeBase::trivial(a1.id()),
1098            MergeBase::trivial(c2.id()),
1099            MergeBase {
1100                a: a1.id(),
1101                b: c2.id(),
1102                base: c0.id(),
1103            },
1104            MergeBase {
1105                a: a1.id(),
1106                b: c1.id(),
1107                base: c0.id(),
1108            },
1109            MergeBase {
1110                a: c2.id(),
1111                b: c1.id(),
1112                base: c0.id(),
1113            },
1114        ]);
1115        assert_matches!(
1116            cq.find_quorum(),
1117            Err(CommitQuorumFailure::DivergingCommits { .. })
1118        );
1119
1120        let mut cq = CommitQuorum::new([a1, a1, c2, c2, c1].iter(), 1);
1121        cq.found_merge_bases([
1122            MergeBase::trivial(a1.id()),
1123            MergeBase::trivial(c2.id()),
1124            MergeBase {
1125                a: a1.id(),
1126                b: c2.id(),
1127                base: c0.id(),
1128            },
1129            MergeBase {
1130                a: a1.id(),
1131                b: c1.id(),
1132                base: c0.id(),
1133            },
1134            MergeBase {
1135                a: c2.id(),
1136                b: c1.id(),
1137                base: c0.id(),
1138            },
1139        ]);
1140        assert_matches!(
1141            cq.find_quorum(),
1142            Err(CommitQuorumFailure::DivergingCommits { .. })
1143        );
1144
1145        let mut cq = CommitQuorum::new([a1, a1, c2, c2, c1].iter(), 1);
1146        cq.found_merge_bases([
1147            MergeBase::trivial(a1.id()),
1148            MergeBase {
1149                a: a1.id(),
1150                b: c2.id(),
1151                base: c0.id(),
1152            },
1153        ]);
1154        assert_matches!(
1155            cq.find_quorum(),
1156            Err(CommitQuorumFailure::DivergingCommits { .. })
1157        );
1158
1159        let mut cq = CommitQuorum::new([b2, b2, c2, c2].iter(), 1);
1160        cq.found_merge_bases([
1161            MergeBase::trivial(b2.id()),
1162            MergeBase::trivial(c2.id()),
1163            MergeBase {
1164                a: b2.id(),
1165                b: c2.id(),
1166                base: c1.id(),
1167            },
1168        ]);
1169        assert_matches!(
1170            cq.find_quorum(),
1171            Err(CommitQuorumFailure::DivergingCommits { .. })
1172        );
1173
1174        let mut cq = CommitQuorum::new([b2, b2, c2, c2, a1].iter(), 1);
1175        cq.found_merge_bases([
1176            MergeBase::trivial(b2.id()),
1177            MergeBase::trivial(c2.id()),
1178            MergeBase {
1179                a: b2.id(),
1180                b: c2.id(),
1181                base: c1.id(),
1182            },
1183            MergeBase {
1184                a: b2.id(),
1185                b: a1.id(),
1186                base: c0.id(),
1187            },
1188            MergeBase {
1189                a: c2.id(),
1190                b: a1.id(),
1191                base: c0.id(),
1192            },
1193        ]);
1194        assert_matches!(
1195            cq.find_quorum(),
1196            Err(CommitQuorumFailure::DivergingCommits { .. })
1197        );
1198    }
1199
1200    #[test]
1201    fn test_commit_quorum_forked_merge_commits() {
1202        let c0 = commit("f2de534b5e81d7c6e2dcaf58c3dd91573c0a0354");
1203        let c1 = commit("bfb1a513e420eade90b0e6be64117b861b16ecb5");
1204        let c2 = commit("8fc5160702365f231c77732a8fa162379e54f57a");
1205        let b2 = commit("037a148170e3d41524b7c482a4798e5c2daeaa00");
1206        let a1 = commit("2224468e22b30359611d880ccf0850d023f86f9b");
1207        let m1 = commit("dd7ee5bca2fc7288a6efcb4303278e26a2dbaa45");
1208        let m2 = commit("d54e505e3fb5c0c7e4b9a4b8a1cdeefb3fc9ef18");
1209
1210        //    M2  M1
1211        //    /\  /\
1212        //    \ B2 C2
1213        //     \  \|
1214        //     A1 C1
1215        //       \|
1216        //       C0
1217        let cq = CommitQuorum::new([m1].iter(), 1);
1218        assert_eq!(cq.find_quorum().unwrap(), m1.id());
1219
1220        let mut cq = CommitQuorum::new([m1, m2].iter(), 1);
1221        cq.found_merge_bases([MergeBase {
1222            a: m1.id(),
1223            b: m2.id(),
1224            base: b2.id(),
1225        }]);
1226        assert_matches!(
1227            cq.find_quorum(),
1228            Err(CommitQuorumFailure::DivergingCommits { .. })
1229        );
1230
1231        let mut cq = CommitQuorum::new([m2, m1].iter(), 1);
1232        cq.found_merge_bases([MergeBase {
1233            a: m2.id(),
1234            b: m1.id(),
1235            base: b2.id(),
1236        }]);
1237        assert_matches!(
1238            cq.find_quorum(),
1239            Err(CommitQuorumFailure::DivergingCommits { .. })
1240        );
1241
1242        let mut cq = CommitQuorum::new([m1, m2].iter(), 2);
1243        cq.found_merge_bases([MergeBase {
1244            a: m1.id(),
1245            b: m2.id(),
1246            base: b2.id(),
1247        }]);
1248        assert_eq!(cq.find_quorum(), Err(CommitQuorumFailure::NoCandidates));
1249
1250        let mut cq = CommitQuorum::new([m1, m2, c2].iter(), 1);
1251        cq.found_merge_bases([
1252            MergeBase {
1253                a: m1.id(),
1254                b: m2.id(),
1255                base: b2.id(),
1256            },
1257            MergeBase {
1258                a: m1.id(),
1259                b: c2.id(),
1260                base: c2.id(),
1261            },
1262            MergeBase {
1263                a: m2.id(),
1264                b: c2.id(),
1265                base: c0.id(),
1266            },
1267        ]);
1268        assert_matches!(
1269            cq.find_quorum(),
1270            Err(CommitQuorumFailure::DivergingCommits { .. })
1271        );
1272
1273        let mut cq = CommitQuorum::new([m1, a1].iter(), 1);
1274        cq.found_merge_bases([MergeBase {
1275            a: m1.id(),
1276            b: a1.id(),
1277            base: c0.id(),
1278        }]);
1279        assert_matches!(
1280            cq.find_quorum(),
1281            Err(CommitQuorumFailure::DivergingCommits { .. })
1282        );
1283
1284        let mut cq = CommitQuorum::new([m1, a1].iter(), 2);
1285        cq.found_merge_bases([MergeBase {
1286            a: m1.id(),
1287            b: a1.id(),
1288            base: c0.id(),
1289        }]);
1290        assert_eq!(cq.find_quorum(), Err(CommitQuorumFailure::NoCandidates));
1291
1292        let mut cq = CommitQuorum::new([m1, m2, b2, c1].iter(), 4);
1293        cq.found_merge_bases([
1294            MergeBase {
1295                a: m1.id(),
1296                b: m2.id(),
1297                base: b2.id(),
1298            },
1299            MergeBase {
1300                a: m1.id(),
1301                b: b2.id(),
1302                base: b2.id(),
1303            },
1304            MergeBase {
1305                a: m1.id(),
1306                b: c1.id(),
1307                base: c1.id(),
1308            },
1309            MergeBase {
1310                a: m2.id(),
1311                b: b2.id(),
1312                base: b2.id(),
1313            },
1314            MergeBase {
1315                a: m2.id(),
1316                b: c1.id(),
1317                base: c1.id(),
1318            },
1319            MergeBase {
1320                a: b2.id(),
1321                b: c1.id(),
1322                base: c1.id(),
1323            },
1324        ]);
1325        assert_eq!(cq.find_quorum().unwrap(), c1.id());
1326
1327        let mut cq = CommitQuorum::new([m1, m1, b2].iter(), 2);
1328        cq.found_merge_bases([
1329            MergeBase::trivial(m1.id()),
1330            MergeBase {
1331                a: m1.id(),
1332                b: b2.id(),
1333                base: b2.id(),
1334            },
1335        ]);
1336        assert_eq!(cq.find_quorum().unwrap(), m1.id());
1337
1338        let mut cq = CommitQuorum::new([m1, m1, c2].iter(), 2);
1339        cq.found_merge_bases([
1340            MergeBase::trivial(m1.id()),
1341            MergeBase {
1342                a: m1.id(),
1343                b: c2.id(),
1344                base: c2.id(),
1345            },
1346        ]);
1347        assert_eq!(cq.find_quorum().unwrap(), m1.id());
1348
1349        let mut cq = CommitQuorum::new([m2, m2, b2].iter(), 2);
1350        cq.found_merge_bases([
1351            MergeBase::trivial(m2.id()),
1352            MergeBase {
1353                a: m2.id(),
1354                b: b2.id(),
1355                base: b2.id(),
1356            },
1357        ]);
1358        assert_eq!(cq.find_quorum().unwrap(), m2.id());
1359
1360        let mut cq = CommitQuorum::new([m2, m2, a1].iter(), 2);
1361        cq.found_merge_bases([
1362            MergeBase::trivial(m2.id()),
1363            MergeBase {
1364                a: m2.id(),
1365                b: a1.id(),
1366                base: a1.id(),
1367            },
1368        ]);
1369        assert_eq!(cq.find_quorum().unwrap(), m2.id());
1370
1371        let mut cq = CommitQuorum::new([m1, m1, b2, b2].iter(), 2);
1372        cq.found_merge_bases([
1373            MergeBase::trivial(m1.id()),
1374            MergeBase::trivial(b2.id()),
1375            MergeBase {
1376                a: m1.id(),
1377                b: b2.id(),
1378                base: b2.id(),
1379            },
1380        ]);
1381        assert_eq!(cq.find_quorum().unwrap(), m1.id());
1382
1383        let mut cq = CommitQuorum::new([m1, m1, c2, c2].iter(), 2);
1384        cq.found_merge_bases([
1385            MergeBase::trivial(m1.id()),
1386            MergeBase::trivial(c2.id()),
1387            MergeBase {
1388                a: m1.id(),
1389                b: c2.id(),
1390                base: c2.id(),
1391            },
1392        ]);
1393        assert_eq!(cq.find_quorum().unwrap(), m1.id());
1394
1395        let mut cq = CommitQuorum::new([m1, b2, c1, c0].iter(), 3);
1396        cq.found_merge_bases([
1397            MergeBase {
1398                a: m1.id(),
1399                b: b2.id(),
1400                base: b2.id(),
1401            },
1402            MergeBase {
1403                a: m1.id(),
1404                b: c1.id(),
1405                base: c1.id(),
1406            },
1407            MergeBase {
1408                a: m1.id(),
1409                b: c0.id(),
1410                base: c0.id(),
1411            },
1412            MergeBase {
1413                a: b2.id(),
1414                b: c1.id(),
1415                base: c1.id(),
1416            },
1417            MergeBase {
1418                a: b2.id(),
1419                b: c0.id(),
1420                base: c0.id(),
1421            },
1422            MergeBase {
1423                a: c1.id(),
1424                b: c0.id(),
1425                base: c0.id(),
1426            },
1427        ]);
1428        assert_eq!(cq.find_quorum().unwrap(), c1.id());
1429
1430        let mut cq = CommitQuorum::new([m1, b2, c1, c0].iter(), 4);
1431        cq.found_merge_bases([
1432            MergeBase {
1433                a: m1.id(),
1434                b: b2.id(),
1435                base: b2.id(),
1436            },
1437            MergeBase {
1438                a: m1.id(),
1439                b: c1.id(),
1440                base: c1.id(),
1441            },
1442            MergeBase {
1443                a: m1.id(),
1444                b: c0.id(),
1445                base: c0.id(),
1446            },
1447            MergeBase {
1448                a: b2.id(),
1449                b: c1.id(),
1450                base: c0.id(),
1451            },
1452            MergeBase {
1453                a: b2.id(),
1454                b: c0.id(),
1455                base: c0.id(),
1456            },
1457            MergeBase {
1458                a: c1.id(),
1459                b: c0.id(),
1460                base: c0.id(),
1461            },
1462        ]);
1463        assert_eq!(cq.find_quorum().unwrap(), c0.id());
1464    }
1465
1466    #[test]
1467    fn test_commit_quorum_merges() {
1468        let c2 = commit("8fc5160702365f231c77732a8fa162379e54f57a");
1469        let m1 = commit("dd7ee5bca2fc7288a6efcb4303278e26a2dbaa45");
1470        let m2 = commit("d54e505e3fb5c0c7e4b9a4b8a1cdeefb3fc9ef18");
1471        let m3 = commit("2224468e22b30359611d880ccf0850d023f86f9b");
1472
1473        //    M2  M1
1474        //    /\  /\
1475        //   C1 C2 C3
1476        //     \| /
1477        //      C0
1478
1479        let mut cq = CommitQuorum::new([m1, m2].iter(), 1);
1480        cq.found_merge_bases([MergeBase {
1481            a: m1.id(),
1482            b: m2.id(),
1483            base: c2.id(),
1484        }]);
1485        assert_matches!(
1486            cq.find_quorum(),
1487            Err(CommitQuorumFailure::DivergingCommits { .. })
1488        );
1489
1490        let mut cq = CommitQuorum::new([m1, m2].iter(), 2);
1491        cq.found_merge_bases([MergeBase {
1492            a: m1.id(),
1493            b: m2.id(),
1494            base: c2.id(),
1495        }]);
1496        assert_eq!(cq.find_quorum(), Err(CommitQuorumFailure::NoCandidates));
1497
1498        //   M3/M2 M1
1499        //    /\  /\
1500        //   C1 C2 C3
1501        //     \| /
1502        //      C0
1503        let mut cq = CommitQuorum::new([m1, m3].iter(), 1);
1504        cq.found_merge_bases([MergeBase {
1505            a: m1.id(),
1506            b: m3.id(),
1507            base: c2.id(),
1508        }]);
1509        assert_matches!(
1510            cq.find_quorum(),
1511            Err(CommitQuorumFailure::DivergingCommits { .. })
1512        );
1513
1514        let mut cq = CommitQuorum::new([m1, m3].iter(), 2);
1515        cq.found_merge_bases([MergeBase {
1516            a: m1.id(),
1517            b: m3.id(),
1518            base: c2.id(),
1519        }]);
1520        assert_eq!(cq.find_quorum(), Err(CommitQuorumFailure::NoCandidates));
1521
1522        let mut cq = CommitQuorum::new([m3, m1].iter(), 1);
1523        cq.found_merge_bases([MergeBase {
1524            a: m3.id(),
1525            b: m1.id(),
1526            base: c2.id(),
1527        }]);
1528        assert_matches!(
1529            cq.find_quorum(),
1530            Err(CommitQuorumFailure::DivergingCommits { .. })
1531        );
1532
1533        let mut cq = CommitQuorum::new([m3, m1].iter(), 2);
1534        cq.found_merge_bases([MergeBase {
1535            a: m3.id(),
1536            b: m1.id(),
1537            base: c2.id(),
1538        }]);
1539        assert_eq!(cq.find_quorum(), Err(CommitQuorumFailure::NoCandidates));
1540
1541        let mut cq = CommitQuorum::new([m3, m2].iter(), 1);
1542        cq.found_merge_bases([MergeBase {
1543            a: m3.id(),
1544            b: m2.id(),
1545            base: c2.id(),
1546        }]);
1547        assert_matches!(
1548            cq.find_quorum(),
1549            Err(CommitQuorumFailure::DivergingCommits { .. })
1550        );
1551
1552        let mut cq = CommitQuorum::new([m3, m2].iter(), 2);
1553        cq.found_merge_bases([MergeBase {
1554            a: m3.id(),
1555            b: m2.id(),
1556            base: c2.id(),
1557        }]);
1558        assert_eq!(cq.find_quorum(), Err(CommitQuorumFailure::NoCandidates));
1559    }
1560}
radicle/git/canonical.rs

radicle/git/
canonical.rs
