Radish alpha
h
heartwood
rad:z3gqcJUoA1n9HaHKufZs5FCSGazv5
Radicle Heartwood Protocol & Stack
Radicle
Git
Patches › 1baa217a
Relax quorum checks
Merged fintohaps opened 1 year ago

The aim of this patch is to help relax the quorum checks in the remote helper.

See the commits for more details.

Note that it is currently in a draft state since I would want to replace the old quorum function with the new Canonical type.

Activity Changes +910 -410
11 files changed +910 -410 a79ca5e8 → 84aaf9ef
added radicle-cli/examples/git/git-push-amend.md
@@ -0,0 +1,27 @@
+ 
``` ~alice
+ 
$ rad id update --title "Add Bob" --delegate did:key:z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk --repo rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji -q
+ 
c036c0d89ce26aef3ad7da402157dba16b5163b4
+ 
```
+
+ 
``` ~bob
+ 
$ rad sync --fetch
+ 
✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MknSL…StBU8Vi..
+ 
✓ Fetched repository from 1 seed(s)
+ 
```
+
+ 
``` ~alice
+ 
$ git commit -m "New changes" --allow-empty -q
+ 
$ git push rad master -o no-sync
+ 
```
+
+ 
``` ~alice
+ 
$ git commit --amend -m "Neue Änderungen" --allow-empty -q
+ 
```
+
+ 
``` ~alice (stderr)
+ 
$ git push rad master -f
+ 
✓ Canonical head updated to 9170c8795d3a78f0381a0ffafb20ea69fb0f5b6b
+ 
✓ Synced with 1 node(s)
+ 
To rad://z42hL2jL4XNk6K8oHQaSWfMgCL7ji/z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi
+ 
 + fb25886...9170c87 master -> master (forced update)
+ 
```
added radicle-cli/examples/git/git-push-converge.md
@@ -0,0 +1,142 @@
+ 
In this scenario we check that we can easily reset our canonical head to the
+ 
head of another delegate when there is divergence between the 3 delegates.
+
+ 
First we add our new delegates, Bob & Eve, to our repo, while also setting the
+ 
`threshold` to `3`:
+
+ 
``` ~alice
+ 
$ rad id update --title "Add Bob & Eve" --delegate did:key:z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk --delegate did:key:z6Mkux1aUQD2voWWukVb5nNUR7thrHveQG4pDQua8nVhib7Z --threshold 3 --repo rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji -q
+ 
3143236b2e40338f5574ec04e935a5ab80a6868a
+ 
```
+
+ 
Bob and Eve will fetch the changes to ensure they hear about their delegate
+ 
responsibilities:
+
+ 
``` ~bob
+ 
$ rad sync --fetch
+ 
✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MknSL…StBU8Vi..
+ 
✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6Mkux1…nVhib7Z..
+ 
✓ Fetched repository from 2 seed(s)
+ 
```
+
+ 
``` ~eve
+ 
$ rad sync --fetch
+ 
✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6Mkt67…v4N1tRk..
+ 
✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MknSL…StBU8Vi..
+ 
✓ Fetched repository from 2 seed(s)
+ 
```
+
+ 
To demonstrate the divergence, Alice, Bob, and Eve will all create a new change,
+ 
pushing to their `rad` remote -- but they won't sync to the network just yet:
+
+ 
``` ~alice
+ 
$ git commit -m "Alice's commit" --allow-empty -q
+ 
$ git push rad -o no-sync
+ 
$ git ls-remote rad
+ 
f2de534b5e81d7c6e2dcaf58c3dd91573c0a0354	refs/heads/master
+ 
```
+
+ 
``` ~bob
+ 
$ git add README
+ 
$ git commit -m "Bob's commit" -q
+ 
$ git push rad -o no-sync
+ 
$ git ls-remote rad
+ 
f2de534b5e81d7c6e2dcaf58c3dd91573c0a0354	refs/heads/master
+ 
```
+
+ 
``` ~eve
+ 
$ git add README
+ 
$ git commit -m "Eve's commit" -q
+ 
$ git push rad -o no-sync
+ 
$ git ls-remote rad
+ 
f2de534b5e81d7c6e2dcaf58c3dd91573c0a0354	refs/heads/master
+ 
```
+
+ 
Alice adds Bob and Eve as remotes and starts to notice that the `no quorum was
+ 
found` error is showing up:
+
+ 
``` ~alice
+ 
$ rad remote add did:key:z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk --name bob
+ 
✓ Follow policy updated for z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk (bob)
+ 
✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6Mkt67…v4N1tRk..
+ 
✗ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6Mkux1…nVhib7Z.. error: no quorum was found
+ 
✓ Remote bob added
+ 
✓ Remote-tracking branch bob/master created for z6Mkt67…v4N1tRk
+ 
$ rad remote add did:key:z6Mkux1aUQD2voWWukVb5nNUR7thrHveQG4pDQua8nVhib7Z --name eve
+ 
✓ Follow policy updated for z6Mkux1aUQD2voWWukVb5nNUR7thrHveQG4pDQua8nVhib7Z (eve)
+ 
✗ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6Mkt67…v4N1tRk.. error: no quorum was found
+ 
✗ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6Mkux1…nVhib7Z.. error: no quorum was found
+ 
✓ Remote eve added
+ 
✓ Remote-tracking branch eve/master created for z6Mkux1…nVhib7Z
+ 
```
+
+ 
Alice does indeed have Bob and Eve's references, however, a new canonical
+ 
`refs/heads/master` cannot be decided while they're out of quorum. This can be
+ 
remedied by the delegates agreeing upon which way to move forward. In this case,
+ 
Alice resets her `master` to `bob/master`:
+
+ 
``` ~alice
+ 
$ git merge bob/master
+ 
Merge made by the 'ort' strategy.
+ 
 README | 2 +-
+ 
 1 file changed, 1 insertion(+), 1 deletion(-)
+ 
$ git merge eve/master -s ours
+ 
Merge made by the 'ours' strategy.
+ 
```
+
+ 
She can then force push to update the canonical head to the new agreed upon
+ 
commit:
+
+ 
``` ~alice (stderr)
+ 
$ git push rad -f
+ 
warn: no quorum was found for `refs/heads/master`
+ 
warn: it is recommended to find a commit to agree upon
+ 
✓ Synced with 1 node(s)
+ 
To rad://z42hL2jL4XNk6K8oHQaSWfMgCL7ji/z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi
+ 
   d09e634..0f9bd80  master -> master
+ 
```
+
+ 
``` ~bob
+ 
$ rad remote add did:key:z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi --name alice
+ 
✓ Follow policy updated for z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi (alice)
+ 
✗ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MknSL…StBU8Vi.. error: no quorum was found
+ 
✗ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6Mkux1…nVhib7Z.. error: no quorum was found
+ 
✓ Remote alice added
+ 
✓ Remote-tracking branch alice/master created for z6MknSL…StBU8Vi
+ 
$ git reset --hard alice/master
+ 
HEAD is now at 0f9bd80 Merge remote-tracking branch 'eve/master'
+ 
```
+
+ 
When we check Bob's `rad` remote, we see that the commit for `refs/heads/master`
+ 
has changed. This is actually Eve's commit as part of Alice merging above. Now
+ 
that Alice, Bob, and Eve all have this commit as part of their history it has
+ 
become the canonical `master`.
+
+ 
``` ~bob (stderr)
+ 
$ git push rad
+ 
✓ Canonical head updated to 3a75f66dd0020c9a0355cc6ec21f15de989e2001
+ 
✓ Synced with 2 node(s)
+ 
To rad://z42hL2jL4XNk6K8oHQaSWfMgCL7ji/z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk
+ 
   2a37862..0f9bd80  master -> master
+ 
```
+
+ 
Once Eve also resets to the merge commits, the canonical `master` is set to this tip.
+
+ 
``` ~eve
+ 
$ rad remote add did:key:z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi --name alice
+ 
✓ Follow policy updated for z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi (alice)
+ 
✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6Mkt67…v4N1tRk..
+ 
✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MknSL…StBU8Vi..
+ 
✓ Remote alice added
+ 
✓ Remote-tracking branch alice/master created for z6MknSL…StBU8Vi
+ 
$ git reset --hard alice/master
+ 
HEAD is now at 0f9bd80 Merge remote-tracking branch 'eve/master'
+ 
```
+
+ 
``` ~eve (stderr)
+ 
$ git push rad
+ 
✓ Canonical head updated to 0f9bd8035c04b3f73f5408e73e8454879b20800b
+ 
✓ Synced with 2 node(s)
+ 
To rad://z42hL2jL4XNk6K8oHQaSWfMgCL7ji/z6Mkux1aUQD2voWWukVb5nNUR7thrHveQG4pDQua8nVhib7Z
+ 
   3a75f66..0f9bd80  master -> master
+ 
```
modified radicle-cli/examples/git/git-push-diverge.md
@@ -66,19 +66,14 @@ To rad://z42hL2jL4XNk6K8oHQaSWfMgCL7ji/z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkE
   f2de534..f6cff86  master -> master

```
- 
One thing of note is that we can't push an older commit either, by default:
+ 
One thing of note is that we can revert to an older commit as long as we are
+ 
still ahead of the other delegates.



``` ~alice

$ git reset --hard HEAD^ -q

```
- 
``` ~alice (fail)
- 
$ git push -f
- 
```
-
- 
We have to use the `allow.rollback` option:
- 


``` ~alice RAD_SOCKET=/dev/null (stderr)
- 
$ git push -f -o allow.rollback
+ 
$ git push -f

✓ Canonical head updated to 319a7dc3b195368ded4b099f8c90bbb80addccd3

To rad://z42hL2jL4XNk6K8oHQaSWfMgCL7ji/z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi

 + f6cff86...319a7dc master -> master (forced update)
added radicle-cli/examples/git/git-push-rollback.md
@@ -0,0 +1,60 @@
+ 
In this scenario, we will explore being able to rollback to a previous commit.
+
+ 
First we add a second delegate, Bob, to our repo. We also change the threshold
+ 
to 2:
+
+ 
``` ~alice
+ 
$ rad id update --title "Add Bob" --delegate did:key:z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk --repo rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji --threshold 2 -q
+ 
069e7d58faa9a7473d27f5510d676af33282796f
+ 
```
+
+ 
Bob then syncs these changes and adds a new commit:
+
+ 
``` ~bob
+ 
$ rad sync --fetch
+ 
✓ Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from z6MknSL…StBU8Vi..
+ 
✓ Fetched repository from 1 seed(s)
+ 
$ git commit -m "Third commit" --allow-empty -q
+ 
$ git push rad
+ 
$ git branch -arv
+ 
  alice@z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi/master f2de534 Second commit
+ 
  rad/master                                                    319a7dc Third commit
+ 
```
+
+ 
Alice merges these changes and pushes them, which updates the canonical head:
+
+ 
``` ~alice
+ 
$ rad remote add did:key:z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk --name bob --fetch --no-sync
+ 
✓ Remote bob added
+ 
✓ Remote-tracking branch bob/master created for z6Mkt67…v4N1tRk
+ 
$ git merge bob/master
+ 
Updating f2de534..319a7dc
+ 
Fast-forward
+ 
```
+
+ 
``` ~alice (stderr)
+ 
$ git push rad
+ 
✓ Canonical head updated to 319a7dc3b195368ded4b099f8c90bbb80addccd3
+ 
✓ Synced with 1 node(s)
+ 
To rad://z42hL2jL4XNk6K8oHQaSWfMgCL7ji/z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi
+ 
   f2de534..319a7dc  master -> master
+ 
```
+
+ 
Alice decides that she changes her mind about these changes and rolls back to
+ 
the previous commit:
+
+ 
``` ~alice
+ 
$ git reset --hard f2de534
+ 
HEAD is now at f2de534 Second commit
+ 
```
+
+ 
Since the canonical head is still decidable from this commit she is allowed to
+ 
push and the new canonical head becomes the previous commit again:
+
+ 
``` ~alice (stderr)
+ 
$ git push rad -f
+ 
✓ Canonical head updated to f2de534b5e81d7c6e2dcaf58c3dd91573c0a0354
+ 
✓ Synced with 1 node(s)
+ 
To rad://z42hL2jL4XNk6K8oHQaSWfMgCL7ji/z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi
+ 
 + 319a7dc...f2de534 master -> master (forced update)
+ 
```
modified radicle-cli/tests/commands.rs
@@ -2442,6 +2442,152 @@ fn git_push_diverge() {
}



#[test]
+ 
fn git_push_converge() {
+ 
    use std::fs;
+
+ 
    let mut environment = Environment::new();
+ 
    let alice = environment.node(Config::test(Alias::new("alice")));
+ 
    let bob = environment.node(Config::test(Alias::new("bob")));
+ 
    let eve = environment.node(Config::test(Alias::new("eve")));
+ 
    let working = environment.tmp().join("working");
+ 
    let acme = RepoId::from_str("z42hL2jL4XNk6K8oHQaSWfMgCL7ji").unwrap();
+
+ 
    fixtures::repository(working.join("alice"));
+
+ 
    test(
+ 
        "examples/rad-init.md",
+ 
        working.join("alice"),
+ 
        Some(&alice.home),
+ 
        [],
+ 
    )
+ 
    .unwrap();
+
+ 
    let alice = alice.spawn();
+ 
    let mut bob = bob.spawn();
+ 
    let mut eve = eve.spawn();
+
+ 
    bob.connect(&alice).connect(&eve).converge([&alice]);
+ 
    eve.connect(&alice).converge([&alice]);
+ 
    bob.fork(acme, working.join("bob")).unwrap();
+ 
    eve.fork(acme, working.join("eve")).unwrap();
+ 
    alice.has_remote_of(&acme, &bob.id);
+ 
    alice.has_remote_of(&acme, &eve.id);
+
+ 
    fs::write(
+ 
        working.join("bob").join("heartwood").join("README"),
+ 
        "Hello\n",
+ 
    )
+ 
    .unwrap();
+ 
    fs::write(
+ 
        working.join("eve").join("heartwood").join("README"),
+ 
        "Hello, world!\n",
+ 
    )
+ 
    .unwrap();
+
+ 
    formula(&environment.tmp(), "examples/git/git-push-converge.md")
+ 
        .unwrap()
+ 
        .home(
+ 
            "alice",
+ 
            working.join("alice"),
+ 
            [("RAD_HOME", alice.home.path().display())],
+ 
        )
+ 
        .home(
+ 
            "bob",
+ 
            working.join("bob").join("heartwood"),
+ 
            [("RAD_HOME", bob.home.path().display())],
+ 
        )
+ 
        .home(
+ 
            "eve",
+ 
            working.join("eve").join("heartwood"),
+ 
            [("RAD_HOME", eve.home.path().display())],
+ 
        )
+ 
        .run()
+ 
        .unwrap();
+ 
}
+
+ 
#[test]
+ 
fn git_push_amend() {
+ 
    let mut environment = Environment::new();
+ 
    let alice = environment.node(Config::test(Alias::new("alice")));
+ 
    let bob = environment.node(Config::test(Alias::new("bob")));
+ 
    let working = environment.tmp().join("working");
+ 
    let acme = RepoId::from_str("z42hL2jL4XNk6K8oHQaSWfMgCL7ji").unwrap();
+
+ 
    fixtures::repository(working.join("alice"));
+
+ 
    test(
+ 
        "examples/rad-init.md",
+ 
        working.join("alice"),
+ 
        Some(&alice.home),
+ 
        [],
+ 
    )
+ 
    .unwrap();
+
+ 
    let alice = alice.spawn();
+ 
    let mut bob = bob.spawn();
+
+ 
    bob.connect(&alice).converge([&alice]);
+ 
    bob.fork(acme, working.join("bob")).unwrap();
+ 
    alice.has_remote_of(&acme, &bob.id);
+
+ 
    formula(&environment.tmp(), "examples/git/git-push-amend.md")
+ 
        .unwrap()
+ 
        .home(
+ 
            "alice",
+ 
            working.join("alice"),
+ 
            [("RAD_HOME", alice.home.path().display())],
+ 
        )
+ 
        .home(
+ 
            "bob",
+ 
            working.join("bob").join("heartwood"),
+ 
            [("RAD_HOME", bob.home.path().display())],
+ 
        )
+ 
        .run()
+ 
        .unwrap();
+ 
}
+
+ 
#[test]
+ 
fn git_push_rollback() {
+ 
    let mut environment = Environment::new();
+ 
    let alice = environment.node(Config::test(Alias::new("alice")));
+ 
    let bob = environment.node(Config::test(Alias::new("bob")));
+ 
    let working = environment.tmp().join("working");
+ 
    let acme = RepoId::from_str("z42hL2jL4XNk6K8oHQaSWfMgCL7ji").unwrap();
+
+ 
    fixtures::repository(working.join("alice"));
+
+ 
    test(
+ 
        "examples/rad-init.md",
+ 
        working.join("alice"),
+ 
        Some(&alice.home),
+ 
        [],
+ 
    )
+ 
    .unwrap();
+
+ 
    let alice = alice.spawn();
+ 
    let mut bob = bob.spawn();
+
+ 
    bob.connect(&alice).converge([&alice]);
+ 
    bob.fork(acme, working.join("bob")).unwrap();
+ 
    alice.has_remote_of(&acme, &bob.id);
+
+ 
    formula(&environment.tmp(), "examples/git/git-push-rollback.md")
+ 
        .unwrap()
+ 
        .home(
+ 
            "alice",
+ 
            working.join("alice"),
+ 
            [("RAD_HOME", alice.home.path().display())],
+ 
        )
+ 
        .home(
+ 
            "bob",
+ 
            working.join("bob").join("heartwood"),
+ 
            [("RAD_HOME", bob.home.path().display())],
+ 
        )
+ 
        .run()
+ 
        .unwrap();
+ 
}
+
+ 
#[test]

fn rad_push_and_pull_patches() {

    let mut environment = Environment::new();

    let alice = environment.node(Config::test(Alias::new("alice")));
modified radicle-remote-helper/src/lib.rs
@@ -69,11 +69,6 @@ pub enum Error {
}



#[derive(Debug, Default, Clone)]
- 
pub struct Allow {
- 
    rollback: bool,
- 
}
-
- 
#[derive(Debug, Default, Clone)]

pub struct Options {

    /// Don't sync after push.

    no_sync: bool,
@@ -87,8 +82,6 @@ pub struct Options {
    base: Option<Rev>,

    /// Patch message.

    message: cli::patch::Message,
- 
    /// Operations allowed.
- 
    allow: Allow,

}



/// Run the radicle remote helper using the given profile.
@@ -215,7 +208,6 @@ fn push_option(args: &[&str], opts: &mut Options) -> Result<(), Error> {
        ["sync.debug"] => opts.sync_debug = true,

        ["no-sync"] => opts.no_sync = true,

        ["patch.draft"] => opts.draft = true,
- 
        ["allow.rollback"] => opts.allow.rollback = true,

        _ => {

            let args = args.join(" ");
@@ -259,3 +251,8 @@ pub(crate) fn read_line<'a>(stdin: &io::Stdin, line: &'a mut String) -> io::Resu
pub(crate) fn hint(s: impl fmt::Display) {

    eprintln!("{}", cli::format::hint(format!("hint: {s}")));

}
+
+ 
/// Write a warning to the user.
+ 
pub(crate) fn warn(s: impl fmt::Display) {
+ 
    eprintln!("{}", cli::format::hint(format!("warn: {s}")));
+ 
}
modified radicle-remote-helper/src/push.rs
@@ -13,6 +13,8 @@ use radicle::cob::patch;
use radicle::cob::patch::cache::Patches as _;

use radicle::crypto::Signer;

use radicle::explorer::ExplorerResource;
+ 
use radicle::git::canonical;
+ 
use radicle::git::canonical::Canonical;

use radicle::identity::Did;

use radicle::node;

use radicle::node::{Handle, NodeId};
@@ -24,7 +26,7 @@ use radicle::{git, rad};
use radicle_cli as cli;

use radicle_cli::terminal as term;
- 
use crate::{hint, read_line, Options};
+ 
use crate::{hint, read_line, warn, Options};



#[derive(Debug, Error)]

pub enum Error {
@@ -105,7 +107,7 @@ pub enum Error {
    Repository(#[from] radicle::storage::RepositoryError),

    /// Quorum error.

    #[error(transparent)]
- 
    Quorum(#[from] radicle::storage::git::QuorumError),
+ 
    Quorum(#[from] radicle::git::canonical::QuorumError),

}



/// Push command.
@@ -191,7 +193,6 @@ pub fn run(
            _ => return Err(Error::InvalidCommand(line.trim().to_owned())),

        }

    }
- 
    let canonical = stored.head()?;

    let delegates = stored.delegates()?;



    // For each refspec, push a ref or delete a ref.
@@ -203,7 +204,7 @@ pub fn run(
            Command::Delete(dst) => {

                // Delete refs.

                let refname = nid.to_namespace().join(dst);
- 
                let (canonical_ref, _) = &canonical;
+ 
                let (canonical_ref, _) = &stored.head()?;



                if *dst == canonical_ref.to_ref_string() && delegates.contains(&Did::from(nid)) {

                    return Err(Error::DeleteForbidden(dst.clone()));
@@ -249,7 +250,10 @@ pub fn run(
                            opts.clone(),

                        )

                    } else {
- 
                        let (canonical_ref, canonical_oid) = &canonical;
+ 
                        let identity = stored.identity()?;
+ 
                        let project = identity.project()?;
+ 
                        let canonical_ref = git::refs::branch(project.default_branch());
+ 
                        let me = Did::from(nid);



                        // If we're trying to update the canonical head, make sure

                        // we don't diverge from the current head. This only applies
@@ -257,41 +261,51 @@ pub fn run(
                        //

                        // Note that we *do* allow rolling back to a previous commit on the

                        // canonical branch.
- 
                        if dst == *canonical_ref
- 
                            && delegates.contains(&Did::from(nid))
- 
                            && delegates.len() > 1
- 
                        {
- 
                            if let Err(e) = working.find_commit(**canonical_oid) {
- 
                                return if git::ext::is_not_found_err(&e) {
- 
                                    Err(Error::MissingCanonicalHead(*canonical_oid))
- 
                                } else {
- 
                                    Err(e.into())
- 
                                };
- 
                            }
+ 
                        if dst == canonical_ref && delegates.contains(&me) && delegates.len() > 1 {

                            let head = working.find_reference(src.as_str())?;

                            let head = head.peel_to_commit()?.id();
- 
                            // Rollback is allowed and head is an ancestor of the canonical head.
- 
                            let rollback = opts.allow.rollback
- 
                                && working.graph_descendant_of(**canonical_oid, head)?;
-
- 
                            if head != **canonical_oid
- 
                                // Canonical head is *not* an ancestor of head.
- 
                                && !working.graph_descendant_of(head, **canonical_oid)?
- 
                                // Not a rollback.
- 
                                && !rollback
- 
                            {
- 
                                if hints {
- 
                                    hint(
- 
                                        "you are attempting to push a commit that would cause \
- 
                                        your upstream to diverge from the canonical head",
- 
                                    );
- 
                                    hint(
- 
                                        "to integrate the remote changes, run `git pull --rebase` \
- 
                                        and try again",
- 
                                    );
- 
                                }
- 
                                return Err(Error::HeadsDiverge(head.into(), *canonical_oid));
+ 
                            let mut canonical =
+ 
                                Canonical::default_branch(stored, &project, &identity.delegates)?;
+ 
                            let converges = canonical::converges(
+ 
                                canonical
+ 
                                    .tips()
+ 
                                    .filter_map(|(did, tip)| (*did != me).then_some(tip)),
+ 
                                head.into(),
+ 
                                &working,
+ 
                            )?;
+ 
                            if converges {
+ 
                                canonical.modify_vote(me, head.into());

                            }
+
+ 
                            match canonical.quorum(identity.threshold, &working) {
+ 
                                Ok(canonical_oid) => {
+ 
                                    // Canonical head is an ancestor of head.
+ 
                                    let is_ff = head == *canonical_oid
+ 
                                        || working.graph_descendant_of(head, *canonical_oid)?;
+
+ 
                                    if !is_ff && !converges {
+ 
                                        if hints {
+ 
                                            hint(
+ 
                                                "you are attempting to push a commit that would cause \
+ 
                                                 your upstream to diverge from the canonical head",
+ 
                                            );
+ 
                                            hint(
+ 
                                                "to integrate the remote changes, run `git pull --rebase` \
+ 
                                                 and try again",
+ 
                                            );
+ 
                                        }
+ 
                                        return Err(Error::HeadsDiverge(
+ 
                                            head.into(),
+ 
                                            canonical_oid,
+ 
                                        ));
+ 
                                    }
+ 
                                }
+ 
                                Err(canonical::QuorumError::NoQuorum) => {
+ 
                                    warn(format!("no quorum was found for `{canonical_ref}`"));
+ 
                                    warn("it is recommended to find a commit to agree upon");
+ 
                                }
+ 
                                Err(e) => return Err(e.into()),
+ 
                            };

                        }

                        push(

                            src,
@@ -322,15 +336,17 @@ pub fn run(
    // Sign refs and sync if at least one ref pushed successfully.

    if !ok.is_empty() {

        let _ = stored.sign_refs(&signer)?;
- 
        let head = stored.set_head()?;
- 
        if head.is_updated() {
- 
            eprintln!(
- 
                "{} Canonical head updated to {}",
- 
                term::format::positive("✓"),
- 
                term::format::secondary(head.new),
- 
            );
- 
        }
+ 
        // N.b. if an error occurs then there may be no quorum
+ 
        if let Ok(head) = stored.set_head() {
+ 
            if head.is_updated() {
+ 
                eprintln!(
+ 
                    "{} Canonical head updated to {}",
+ 
                    term::format::positive("✓"),
+ 
                    term::format::secondary(head.new),
+ 
                );
+ 
            }
+ 
        };



        if !opts.no_sync {

            if profile.policies()?.is_seeding(&stored.id)? {
modified radicle/src/git.rs
@@ -1,3 +1,5 @@
+ 
pub mod canonical;
+ 


use std::io;

use std::path::Path;

use std::process::Command;
added radicle/src/git/canonical.rs
@@ -0,0 +1,459 @@
+ 
use std::collections::BTreeMap;
+
+ 
use nonempty::NonEmpty;
+ 
use raw::Repository;
+ 
use thiserror::Error;
+
+ 
use crate::prelude::Did;
+ 
use crate::prelude::Project;
+ 
use crate::storage::ReadRepository;
+
+ 
use super::raw;
+ 
use super::{lit, Oid, Qualified};
+
+ 
/// A collection of [`Did`]s and their [`Oid`]s that is the tip for a given
+ 
/// reference for that [`Did`].
+ 
///
+ 
/// The general construction of `Canonical` is by using the
+ 
/// [`Canonical::reference`] constructor. For the default branch of a
+ 
/// [`Project`], use [`Canonical::default_branch`].
+ 
///
+ 
/// `Canonical` can then be used for performing calculations about the
+ 
/// canonicity of the reference, most importantly the [`Canonical::quorum`].
+ 
pub struct Canonical {
+ 
    tips: BTreeMap<Did, Oid>,
+ 
}
+
+ 
/// Error that can occur when calculation the [`Canonical::quorum`].
+ 
#[derive(Debug, Error)]
+ 
pub enum QuorumError {
+ 
    /// Could not determine a quorum [`Oid`].
+ 
    #[error("no quorum was found")]
+ 
    NoQuorum,
+ 
    /// An error occurred from [`git2`].
+ 
    #[error(transparent)]
+ 
    Git(#[from] git2::Error),
+ 
}
+
+ 
impl Canonical {
+ 
    /// Construct the set of canonical tips of the `Project::default_branch` for
+ 
    /// the given `delegates`.
+ 
    pub fn default_branch<S>(
+ 
        repo: &S,
+ 
        project: &Project,
+ 
        delegates: &NonEmpty<Did>,
+ 
    ) -> Result<Self, raw::Error>
+ 
    where
+ 
        S: ReadRepository,
+ 
    {
+ 
        Self::reference(
+ 
            repo,
+ 
            delegates,
+ 
            &lit::refs_heads(project.default_branch()).into(),
+ 
        )
+ 
    }
+
+ 
    /// Construct the set of canonical tips given for the given `delegates` and
+ 
    /// the reference `name`.
+ 
    pub fn reference<S>(
+ 
        repo: &S,
+ 
        delegates: &NonEmpty<Did>,
+ 
        name: &Qualified,
+ 
    ) -> Result<Self, raw::Error>
+ 
    where
+ 
        S: ReadRepository,
+ 
    {
+ 
        let mut tips = BTreeMap::new();
+ 
        for delegate in delegates.iter() {
+ 
            match repo.reference_oid(delegate, name) {
+ 
                Ok(tip) => {
+ 
                    tips.insert(*delegate, tip);
+ 
                }
+ 
                Err(e) if super::ext::is_not_found_err(&e) => {
+ 
                    log::warn!(
+ 
                        target: "radicle",
+ 
                        "Missing `refs/namespaces/{delegate}/{name}` while calculating the canonical reference"
+ 
                    );
+ 
                }
+ 
                Err(e) => return Err(e),
+ 
            }
+ 
        }
+ 
        Ok(Canonical { tips })
+ 
    }
+
+ 
    /// Return the set of [`Did`]s and their [`Oid`] tip.
+ 
    pub fn tips(&self) -> impl Iterator<Item = (&Did, &Oid)> {
+ 
        self.tips.iter()
+ 
    }
+ 
}
+
+ 
/// Check that a given `target` converges with any of the provided `tips`.
+ 
///
+ 
/// It converges if the `target` is either equal to, ahead of, or behind any of
+ 
/// the tips.
+ 
pub fn converges<'a>(
+ 
    tips: impl Iterator<Item = &'a Oid>,
+ 
    target: Oid,
+ 
    repo: &Repository,
+ 
) -> Result<bool, raw::Error> {
+ 
    for tip in tips {
+ 
        match repo.graph_ahead_behind(*target, **tip)? {
+ 
            (0, 0) => return Ok(true),
+ 
            (ahead, behind) if ahead > 0 && behind == 0 => return Ok(true),
+ 
            (ahead, behind) if behind > 0 && ahead == 0 => return Ok(true),
+ 
            (_, _) => {}
+ 
        }
+ 
    }
+ 
    Ok(false)
+ 
}
+
+ 
impl Canonical {
+ 
    /// In some cases, we allow the vote to be modified. For example, when the
+ 
    /// `did` is pushing a new commit, we may want to see if the new commit will
+ 
    /// reach a quorum.
+ 
    pub fn modify_vote(&mut self, did: Did, new: Oid) {
+ 
        self.tips.insert(did, new);
+ 
    }
+
+ 
    /// Computes the quorum or "canonical" tip based on the tips, of `Canonical`,
+ 
    /// and the threshold. This can be described as the latest commit that is
+ 
    /// included in at least `threshold` histories. In case there are multiple tips
+ 
    /// passing the threshold, and they are divergent, an error is returned.
+ 
    ///
+ 
    /// Also returns an error if `heads` is empty or `threshold` cannot be
+ 
    /// satisified with the number of heads given.
+ 
    pub fn quorum(&self, threshold: usize, repo: &raw::Repository) -> Result<Oid, QuorumError> {
+ 
        let mut candidates = BTreeMap::<_, usize>::new();
+
+ 
        // Build a list of candidate commits and count how many "votes" each of them has.
+ 
        // Commits get a point for each direct vote, as well as for being part of the ancestry
+ 
        // of a commit given to this function. Only commits given to the function are considered.
+ 
        for (i, head) in self.tips.values().enumerate() {
+ 
            // Add a direct vote for this head.
+ 
            *candidates.entry(*head).or_default() += 1;
+
+ 
            // Compare this head to all other heads ahead of it in the list.
+ 
            for other in self.tips.values().skip(i + 1) {
+ 
                // N.b. if heads are equal then skip it, otherwise it will end up as
+ 
                // a double vote.
+ 
                if *head == *other {
+ 
                    continue;
+ 
                }
+ 
                let base = Oid::from(repo.merge_base(**head, **other)?);
+
+ 
                if base == *other || base == *head {
+ 
                    *candidates.entry(base).or_default() += 1;
+ 
                }
+ 
            }
+ 
        }
+ 
        // Keep commits which pass the threshold.
+ 
        candidates.retain(|_, votes| *votes >= threshold);
+
+ 
        // Keep track of the longest identity branch.
+ 
        let (mut longest, _) = candidates.pop_first().ok_or(QuorumError::NoQuorum)?;
+
+ 
        // Now that all scores are calculated, figure out what is the longest branch
+ 
        // that passes the threshold. In case of divergence, return an error.
+ 
        for head in candidates.keys() {
+ 
            let base = repo.merge_base(**head, *longest)?;
+
+ 
            if base == *longest {
+ 
                // `head` is a successor of `longest`. Update `longest`.
+ 
                //
+ 
                //   o head
+ 
                //   |
+ 
                //   o longest (base)
+ 
                //   |
+ 
                //
+ 
                longest = *head;
+ 
            } else if base == **head || *head == longest {
+ 
                // `head` is an ancestor of `longest`, or equal to it. Do nothing.
+ 
                //
+ 
                //   o longest             o longest, head (base)
+ 
                //   |                     |
+ 
                //   o head (base)   OR    o
+ 
                //   |                     |
+ 
                //
+ 
            } else {
+ 
                // The merge base between `head` and `longest` (`base`)
+ 
                // is neither `head` nor `longest`. Therefore, the branches have
+ 
                // diverged.
+ 
                //
+ 
                //    longest   head
+ 
                //           \ /
+ 
                //            o (base)
+ 
                //            |
+ 
                //
+ 
                return Err(QuorumError::NoQuorum);
+ 
            }
+ 
        }
+ 
        Ok((*longest).into())
+ 
    }
+ 
}
+
+ 
#[cfg(test)]
+ 
#[allow(clippy::unwrap_used)]
+ 
mod tests {
+ 
    use crypto::test::signer::MockSigner;
+ 
    use radicle_crypto::Signer;
+
+ 
    use super::*;
+ 
    use crate::assert_matches;
+ 
    use crate::git;
+ 
    use crate::test::fixtures;
+
+ 
    /// Test helper to construct a Canonical and get the quorum
+ 
    fn quorum(
+ 
        heads: &[git::raw::Oid],
+ 
        threshold: usize,
+ 
        repo: &git::raw::Repository,
+ 
    ) -> Result<Oid, QuorumError> {
+ 
        let tips = heads
+ 
            .iter()
+ 
            .enumerate()
+ 
            .map(|(i, head)| {
+ 
                let signer = MockSigner::from_seed([(i + 1) as u8; 32]);
+ 
                let did = Did::from(signer.public_key());
+ 
                (did, (*head).into())
+ 
            })
+ 
            .collect();
+ 
        Canonical { tips }.quorum(threshold, repo)
+ 
    }
+
+ 
    #[test]
+ 
    fn test_quorum_properties() {
+ 
        let tmp = tempfile::tempdir().unwrap();
+ 
        let (repo, c0) = fixtures::repository(tmp.path());
+ 
        let c0: git::Oid = c0.into();
+ 
        let a1 = fixtures::commit("A1", &[*c0], &repo);
+ 
        let a2 = fixtures::commit("A2", &[*a1], &repo);
+ 
        let d1 = fixtures::commit("D1", &[*c0], &repo);
+ 
        let c1 = fixtures::commit("C1", &[*c0], &repo);
+ 
        let c2 = fixtures::commit("C2", &[*c1], &repo);
+ 
        let b2 = fixtures::commit("B2", &[*c1], &repo);
+ 
        let a1 = fixtures::commit("A1", &[*c0], &repo);
+ 
        let m1 = fixtures::commit("M1", &[*c2, *b2], &repo);
+ 
        let m2 = fixtures::commit("M2", &[*a1, *b2], &repo);
+ 
        let mut rng = fastrand::Rng::new();
+ 
        let choices = [*c0, *c1, *c2, *b2, *a1, *a2, *d1, *m1, *m2];
+
+ 
        for _ in 0..100 {
+ 
            let count = rng.usize(1..=choices.len());
+ 
            let threshold = rng.usize(1..=count);
+ 
            let mut heads = Vec::new();
+
+ 
            for _ in 0..count {
+ 
                let ix = rng.usize(0..choices.len());
+ 
                heads.push(choices[ix]);
+ 
            }
+ 
            rng.shuffle(&mut heads);
+
+ 
            if let Ok(canonical) = quorum(&heads, threshold, &repo) {
+ 
                assert!(heads.contains(&canonical));
+ 
            }
+ 
        }
+ 
    }
+
+ 
    #[test]
+ 
    fn test_quorum() {
+ 
        let tmp = tempfile::tempdir().unwrap();
+ 
        let (repo, c0) = fixtures::repository(tmp.path());
+ 
        let c0: git::Oid = c0.into();
+ 
        let c1 = fixtures::commit("C1", &[*c0], &repo);
+ 
        let c2 = fixtures::commit("C2", &[*c1], &repo);
+ 
        let c3 = fixtures::commit("C3", &[*c1], &repo);
+ 
        let b2 = fixtures::commit("B2", &[*c1], &repo);
+ 
        let a1 = fixtures::commit("A1", &[*c0], &repo);
+ 
        let m1 = fixtures::commit("M1", &[*c2, *b2], &repo);
+ 
        let m2 = fixtures::commit("M2", &[*a1, *b2], &repo);
+
+ 
        eprintln!("C0: {c0}");
+ 
        eprintln!("C1: {c1}");
+ 
        eprintln!("C2: {c2}");
+ 
        eprintln!("C3: {c3}");
+ 
        eprintln!("B2: {b2}");
+ 
        eprintln!("A1: {a1}");
+ 
        eprintln!("M1: {m1}");
+ 
        eprintln!("M2: {m2}");
+
+ 
        assert_eq!(quorum(&[*c0], 1, &repo).unwrap(), c0);
+ 
        assert_eq!(quorum(&[*c1], 1, &repo).unwrap(), c1);
+ 
        assert_eq!(quorum(&[*c2], 1, &repo).unwrap(), c2);
+ 
        assert_eq!(quorum(&[*c0], 0, &repo).unwrap(), c0);
+ 
        assert_matches!(quorum(&[], 0, &repo), Err(QuorumError::NoQuorum));
+ 
        assert_matches!(quorum(&[*c0], 2, &repo), Err(QuorumError::NoQuorum));
+
+ 
        //  C1
+ 
        //  |
+ 
        // C0
+ 
        assert_eq!(quorum(&[*c1], 1, &repo).unwrap(), c1);
+
+ 
        //   C2
+ 
        //   |
+ 
        //  C1
+ 
        //  |
+ 
        // C0
+ 
        assert_eq!(quorum(&[*c1, *c2], 1, &repo).unwrap(), c2);
+ 
        assert_eq!(quorum(&[*c1, *c2], 2, &repo).unwrap(), c1);
+ 
        assert_eq!(quorum(&[*c0, *c1, *c2], 3, &repo).unwrap(), c0);
+ 
        assert_eq!(quorum(&[*c1, *c1, *c2], 2, &repo).unwrap(), c1);
+ 
        assert_eq!(quorum(&[*c1, *c1, *c2], 1, &repo).unwrap(), c2);
+ 
        assert_eq!(quorum(&[*c2, *c2, *c1], 1, &repo).unwrap(), c2);
+
+ 
        // B2 C2
+ 
        //   \|
+ 
        //   C1
+ 
        //   |
+ 
        //  C0
+ 
        assert_matches!(
+ 
            quorum(&[*c1, *c2, *b2], 1, &repo),
+ 
            Err(QuorumError::NoQuorum)
+ 
        );
+ 
        assert_matches!(quorum(&[*c2, *b2], 1, &repo), Err(QuorumError::NoQuorum));
+ 
        assert_matches!(quorum(&[*b2, *c2], 1, &repo), Err(QuorumError::NoQuorum));
+ 
        assert_matches!(quorum(&[*c2, *b2], 2, &repo), Err(QuorumError::NoQuorum));
+ 
        assert_matches!(quorum(&[*b2, *c2], 2, &repo), Err(QuorumError::NoQuorum));
+ 
        assert_eq!(quorum(&[*c1, *c2, *b2], 2, &repo).unwrap(), c1);
+ 
        assert_eq!(quorum(&[*c1, *c2, *b2], 3, &repo).unwrap(), c1);
+ 
        assert_eq!(quorum(&[*b2, *b2, *c2], 2, &repo).unwrap(), b2);
+ 
        assert_eq!(quorum(&[*b2, *c2, *c2], 2, &repo).unwrap(), c2);
+ 
        assert_matches!(
+ 
            quorum(&[*b2, *b2, *c2, *c2], 2, &repo),
+ 
            Err(QuorumError::NoQuorum)
+ 
        );
+
+ 
        // B2 C2 C3
+ 
        //  \ | /
+ 
        //    C1
+ 
        //    |
+ 
        //    C0
+ 
        assert_eq!(quorum(&[*b2, *c2, *c2], 2, &repo).unwrap(), c2);
+ 
        assert_matches!(
+ 
            quorum(&[*b2, *c2, *c2], 3, &repo),
+ 
            Err(QuorumError::NoQuorum)
+ 
        );
+ 
        assert_matches!(
+ 
            quorum(&[*b2, *c2, *b2, *c2], 3, &repo),
+ 
            Err(QuorumError::NoQuorum)
+ 
        );
+ 
        assert_matches!(
+ 
            quorum(&[*c3, *b2, *c2, *b2, *c2, *c3], 3, &repo),
+ 
            Err(QuorumError::NoQuorum)
+ 
        );
+
+ 
        //  B2 C2
+ 
        //    \|
+ 
        // A1 C1
+ 
        //   \|
+ 
        //   C0
+ 
        assert_matches!(
+ 
            quorum(&[*c2, *b2, *a1], 1, &repo),
+ 
            Err(QuorumError::NoQuorum)
+ 
        );
+ 
        assert_matches!(
+ 
            quorum(&[*c2, *b2, *a1], 2, &repo),
+ 
            Err(QuorumError::NoQuorum)
+ 
        );
+ 
        assert_matches!(
+ 
            quorum(&[*c2, *b2, *a1], 3, &repo),
+ 
            Err(QuorumError::NoQuorum)
+ 
        );
+ 
        assert_matches!(
+ 
            quorum(&[*c1, *c2, *b2, *a1], 4, &repo),
+ 
            Err(QuorumError::NoQuorum)
+ 
        );
+ 
        assert_eq!(quorum(&[*c0, *c1, *c2, *b2, *a1], 2, &repo).unwrap(), c1,);
+ 
        assert_eq!(quorum(&[*c0, *c1, *c2, *b2, *a1], 3, &repo).unwrap(), c1,);
+ 
        assert_eq!(quorum(&[*c0, *c2, *b2, *a1], 3, &repo).unwrap(), c0);
+ 
        assert_eq!(quorum(&[*c0, *c1, *c2, *b2, *a1], 4, &repo).unwrap(), c0,);
+ 
        assert_matches!(
+ 
            quorum(&[*a1, *a1, *c2, *c2, *c1], 2, &repo),
+ 
            Err(QuorumError::NoQuorum)
+ 
        );
+ 
        assert_matches!(
+ 
            quorum(&[*a1, *a1, *c2, *c2, *c1], 1, &repo),
+ 
            Err(QuorumError::NoQuorum)
+ 
        );
+ 
        assert_matches!(
+ 
            quorum(&[*a1, *a1, *c2], 1, &repo),
+ 
            Err(QuorumError::NoQuorum)
+ 
        );
+ 
        assert_matches!(
+ 
            quorum(&[*b2, *b2, *c2, *c2], 1, &repo),
+ 
            Err(QuorumError::NoQuorum)
+ 
        );
+ 
        assert_matches!(
+ 
            quorum(&[*b2, *b2, *c2, *c2, *a1], 1, &repo),
+ 
            Err(QuorumError::NoQuorum)
+ 
        );
+
+ 
        //    M2  M1
+ 
        //    /\  /\
+ 
        //    \ B2 C2
+ 
        //     \  \|
+ 
        //     A1 C1
+ 
        //       \|
+ 
        //       C0
+ 
        assert_eq!(quorum(&[*m1], 1, &repo).unwrap(), m1);
+ 
        assert_matches!(quorum(&[*m1, *m2], 1, &repo), Err(QuorumError::NoQuorum));
+ 
        assert_matches!(quorum(&[*m2, *m1], 1, &repo), Err(QuorumError::NoQuorum));
+ 
        assert_matches!(quorum(&[*m1, *m2], 2, &repo), Err(QuorumError::NoQuorum));
+ 
        assert_matches!(
+ 
            quorum(&[*m1, *m2, *c2], 1, &repo),
+ 
            Err(QuorumError::NoQuorum)
+ 
        );
+ 
        assert_matches!(quorum(&[*m1, *a1], 1, &repo), Err(QuorumError::NoQuorum));
+ 
        assert_matches!(quorum(&[*m1, *a1], 2, &repo), Err(QuorumError::NoQuorum));
+ 
        assert_eq!(quorum(&[*m1, *m2, *b2, *c1], 4, &repo).unwrap(), c1);
+ 
        assert_eq!(quorum(&[*m1, *m1, *b2], 2, &repo).unwrap(), m1);
+ 
        assert_eq!(quorum(&[*m1, *m1, *c2], 2, &repo).unwrap(), m1);
+ 
        assert_eq!(quorum(&[*m2, *m2, *b2], 2, &repo).unwrap(), m2);
+ 
        assert_eq!(quorum(&[*m2, *m2, *a1], 2, &repo).unwrap(), m2);
+ 
        assert_eq!(quorum(&[*m1, *m1, *b2, *b2], 2, &repo).unwrap(), m1);
+ 
        assert_eq!(quorum(&[*m1, *m1, *c2, *c2], 2, &repo).unwrap(), m1);
+ 
        assert_eq!(quorum(&[*m1, *b2, *c1, *c0], 3, &repo).unwrap(), c1);
+ 
        assert_eq!(quorum(&[*m1, *b2, *c1, *c0], 4, &repo).unwrap(), c0);
+ 
    }
+
+ 
    #[test]
+ 
    fn test_quorum_merges() {
+ 
        let tmp = tempfile::tempdir().unwrap();
+ 
        let (repo, c0) = fixtures::repository(tmp.path());
+ 
        let c0: git::Oid = c0.into();
+ 
        let c1 = fixtures::commit("C1", &[*c0], &repo);
+ 
        let c2 = fixtures::commit("C2", &[*c0], &repo);
+ 
        let c3 = fixtures::commit("C3", &[*c0], &repo);
+
+ 
        let m1 = fixtures::commit("M1", &[*c1, *c2], &repo);
+ 
        let m2 = fixtures::commit("M2", &[*c2, *c3], &repo);
+
+ 
        eprintln!("C0: {c0}");
+ 
        eprintln!("C1: {c1}");
+ 
        eprintln!("C2: {c2}");
+ 
        eprintln!("C3: {c3}");
+ 
        eprintln!("M1: {m1}");
+ 
        eprintln!("M2: {m2}");
+
+ 
        //    M2  M1
+ 
        //    /\  /\
+ 
        //   C1 C2 C3
+ 
        //     \| /
+ 
        //      C0
+ 
        assert_matches!(quorum(&[*m1, *m2], 1, &repo), Err(QuorumError::NoQuorum));
+ 
        assert_matches!(quorum(&[*m1, *m2], 2, &repo), Err(QuorumError::NoQuorum));
+
+ 
        let m3 = fixtures::commit("M3", &[*c2, *c1], &repo);
+
+ 
        //   M3/M2 M1
+ 
        //    /\  /\
+ 
        //   C1 C2 C3
+ 
        //     \| /
+ 
        //      C0
+ 
        assert_matches!(quorum(&[*m1, *m3], 1, &repo), Err(QuorumError::NoQuorum));
+ 
        assert_matches!(quorum(&[*m1, *m3], 2, &repo), Err(QuorumError::NoQuorum));
+ 
        assert_matches!(quorum(&[*m3, *m1], 1, &repo), Err(QuorumError::NoQuorum));
+ 
        assert_matches!(quorum(&[*m3, *m1], 2, &repo), Err(QuorumError::NoQuorum));
+ 
        assert_matches!(quorum(&[*m3, *m2], 1, &repo), Err(QuorumError::NoQuorum));
+ 
        assert_matches!(quorum(&[*m3, *m2], 2, &repo), Err(QuorumError::NoQuorum));
+ 
    }
+ 
}
modified radicle/src/storage.rs
@@ -16,7 +16,7 @@ pub use radicle_git_ext::Oid;


use crate::cob;

use crate::collections::RandomMap;
- 
use crate::git::ext as git_ext;
+ 
use crate::git::{canonical, ext as git_ext};

use crate::git::{refspec::Refspec, PatternString, Qualified, RefError, RefStr, RefString};

use crate::identity::{Did, PayloadError};

use crate::identity::{Doc, DocAt, DocError};
@@ -116,7 +116,7 @@ pub enum RepositoryError {
    #[error(transparent)]

    GitExt(#[from] git_ext::Error),

    #[error(transparent)]
- 
    Quorum(#[from] git::QuorumError),
+ 
    Quorum(#[from] canonical::QuorumError),

    #[error(transparent)]

    Refs(#[from] refs::Error),

}
modified radicle/src/storage/git.rs
@@ -12,6 +12,7 @@ use once_cell::sync::Lazy;
use tempfile::TempDir;



use crate::crypto::Unverified;
+ 
use crate::git::canonical::Canonical;

use crate::identity::doc::DocError;

use crate::identity::{doc::DocAt, Doc, RepoId};

use crate::identity::{Identity, Project};
@@ -743,25 +744,8 @@ impl ReadRepository for Repository {
        let project = doc.project()?;

        let branch_ref = git::refs::branch(project.default_branch());

        let raw = self.raw();
- 
        let mut heads = Vec::new();
-
- 
        for delegate in doc.delegates.iter() {
- 
            let r = match self.reference_oid(delegate, &branch_ref) {
- 
                Ok(oid) => oid,
- 
                Err(e) if ext::is_not_found_err(&e) => {
- 
                    log::warn!(
- 
                        target: "radicle",
- 
                        "Missing `refs/namespaces/{delegate}/{branch_ref}` while calculating the canonical head"
- 
                    );
- 
                    continue;
- 
                }
- 
                Err(e) => return Err(e.into()),
- 
            };
-
- 
            heads.push(*r);
- 
        }
-
- 
        let oid = self::quorum(&heads, doc.threshold, raw)?;
+ 
        let oid = Canonical::default_branch(self, &project, &doc.delegates)?
+ 
            .quorum(doc.threshold, raw)?;

        Ok((branch_ref, oid))

    }
@@ -896,96 +880,6 @@ impl SignRepository for Repository {
        Ok(signed)

    }

}
-
- 
#[derive(Debug, Error)]
- 
pub enum QuorumError {
- 
    #[error("no quorum was found")]
- 
    NoQuorum,
- 
    #[error(transparent)]
- 
    Git(#[from] git2::Error),
- 
}
-
- 
/// Computes the quorum or "canonical" head based on the given heads and the
- 
/// threshold. This can be described as the latest commit that is included in
- 
/// at least `threshold` histories. In case there are multiple heads passing
- 
/// the threshold, and they are divergent, an error is returned.
- 
///
- 
/// Also returns an error if `heads` is empty or `threshold` cannot be satisified with
- 
/// the number of heads given.
- 
pub fn quorum(
- 
    heads: &[git::raw::Oid],
- 
    threshold: usize,
- 
    repo: &git::raw::Repository,
- 
) -> Result<Oid, QuorumError> {
- 
    let mut candidates = BTreeMap::<_, usize>::new();
-
- 
    // Build a list of candidate commits and count how many "votes" each of them has.
- 
    // Commits get a point for each direct vote, as well as for being part of the ancestry
- 
    // of a commit given to this function. Only commits given to the function are considered.
- 
    for (i, head) in heads.iter().enumerate() {
- 
        let head = Oid::from(*head);
-
- 
        // Add a direct vote for this head.
- 
        *candidates.entry(head).or_default() += 1;
-
- 
        // Compare this head to all other heads ahead of it in the list.
- 
        for other in heads.iter().skip(i + 1) {
- 
            // N.b. if heads are equal then skip it, otherwise it will end up as
- 
            // a double vote.
- 
            if *head == *other {
- 
                continue;
- 
            }
- 
            let base = repo.merge_base(*head, *other)?;
-
- 
            if base == *other || base == *head {
- 
                *candidates.entry(Oid::from(base)).or_default() += 1;
- 
            }
- 
        }
- 
    }
- 
    // Keep commits which pass the threshold.
- 
    candidates.retain(|_, votes| *votes >= threshold);
-
- 
    // Keep track of the longest identity branch.
- 
    let (mut longest, _) = candidates.pop_first().ok_or(QuorumError::NoQuorum)?;
-
- 
    // Now that all scores are calculated, figure out what is the longest branch
- 
    // that passes the threshold. In case of divergence, return an error.
- 
    for head in candidates.keys() {
- 
        let base = repo.merge_base(**head, *longest)?;
-
- 
        if base == *longest {
- 
            // `head` is a successor of `longest`. Update `longest`.
- 
            //
- 
            //   o head
- 
            //   |
- 
            //   o longest (base)
- 
            //   |
- 
            //
- 
            longest = *head;
- 
        } else if base == **head || *head == longest {
- 
            // `head` is an ancestor of `longest`, or equal to it. Do nothing.
- 
            //
- 
            //   o longest             o longest, head (base)
- 
            //   |                     |
- 
            //   o head (base)   OR    o
- 
            //   |                     |
- 
            //
- 
        } else {
- 
            // The merge base between `head` and `longest` (`base`)
- 
            // is neither `head` nor `longest`. Therefore, the branches have
- 
            // diverged.
- 
            //
- 
            //    longest   head
- 
            //           \ /
- 
            //            o (base)
- 
            //            |
- 
            //
- 
            return Err(QuorumError::NoQuorum);
- 
        }
- 
    }
- 
    Ok((*longest).into())
- 
}
- 


pub mod trailers {

    use std::str::FromStr;
@@ -1045,7 +939,6 @@ mod tests {
    use crypto::test::signer::MockSigner;



    use super::*;
- 
    use crate::assert_matches;

    use crate::git;

    use crate::storage::refs::SIGREFS_BRANCH;

    use crate::storage::{ReadRepository, ReadStorage};
@@ -1053,243 +946,6 @@ mod tests {
    use crate::test::fixtures;



    #[test]
- 
    fn test_quorum_properties() {
- 
        let tmp = tempfile::tempdir().unwrap();
- 
        let (repo, c0) = fixtures::repository(tmp.path());
- 
        let c0: git::Oid = c0.into();
- 
        let a1 = fixtures::commit("A1", &[*c0], &repo);
- 
        let a2 = fixtures::commit("A2", &[*a1], &repo);
- 
        let d1 = fixtures::commit("D1", &[*c0], &repo);
- 
        let c1 = fixtures::commit("C1", &[*c0], &repo);
- 
        let c2 = fixtures::commit("C2", &[*c1], &repo);
- 
        let b2 = fixtures::commit("B2", &[*c1], &repo);
- 
        let a1 = fixtures::commit("A1", &[*c0], &repo);
- 
        let m1 = fixtures::commit("M1", &[*c2, *b2], &repo);
- 
        let m2 = fixtures::commit("M2", &[*a1, *b2], &repo);
- 
        let mut rng = fastrand::Rng::new();
- 
        let choices = [*c0, *c1, *c2, *b2, *a1, *a2, *d1, *m1, *m2];
-
- 
        for _ in 0..100 {
- 
            let count = rng.usize(1..=choices.len());
- 
            let threshold = rng.usize(1..=count);
- 
            let mut heads = Vec::new();
-
- 
            for _ in 0..count {
- 
                let ix = rng.usize(0..choices.len());
- 
                heads.push(choices[ix]);
- 
            }
- 
            rng.shuffle(&mut heads);
-
- 
            if let Ok(canonical) = quorum(&heads, threshold, &repo) {
- 
                assert!(heads.contains(&canonical));
- 
            }
- 
        }
- 
    }
-
- 
    #[test]
- 
    fn test_quorum() {
- 
        let tmp = tempfile::tempdir().unwrap();
- 
        let (repo, c0) = fixtures::repository(tmp.path());
- 
        let c0: git::Oid = c0.into();
- 
        let c1 = fixtures::commit("C1", &[*c0], &repo);
- 
        let c2 = fixtures::commit("C2", &[*c1], &repo);
- 
        let c3 = fixtures::commit("C3", &[*c1], &repo);
- 
        let b2 = fixtures::commit("B2", &[*c1], &repo);
- 
        let a1 = fixtures::commit("A1", &[*c0], &repo);
- 
        let m1 = fixtures::commit("M1", &[*c2, *b2], &repo);
- 
        let m2 = fixtures::commit("M2", &[*a1, *b2], &repo);
-
- 
        eprintln!("C0: {c0}");
- 
        eprintln!("C1: {c1}");
- 
        eprintln!("C2: {c2}");
- 
        eprintln!("C3: {c3}");
- 
        eprintln!("B2: {b2}");
- 
        eprintln!("A1: {a1}");
- 
        eprintln!("M1: {m1}");
- 
        eprintln!("M2: {m2}");
-
- 
        assert_eq!(quorum(&[*c0], 1, &repo).unwrap(), c0);
- 
        assert_eq!(quorum(&[*c1], 1, &repo).unwrap(), c1);
- 
        assert_eq!(quorum(&[*c2], 1, &repo).unwrap(), c2);
- 
        assert_eq!(quorum(&[*c0], 0, &repo).unwrap(), c0);
- 
        assert_matches!(quorum(&[], 0, &repo), Err(QuorumError::NoQuorum));
- 
        assert_matches!(quorum(&[*c0], 2, &repo), Err(QuorumError::NoQuorum));
-
- 
        //  C1
- 
        //  |
- 
        // C0
- 
        assert_eq!(quorum(&[*c1], 1, &repo).unwrap(), c1);
-
- 
        //   C2
- 
        //   |
- 
        //  C1
- 
        //  |
- 
        // C0
- 
        assert_eq!(quorum(&[*c1, *c2], 1, &repo).unwrap(), c2);
- 
        assert_eq!(quorum(&[*c1, *c2], 2, &repo).unwrap(), c1);
- 
        assert_eq!(quorum(&[*c0, *c1, *c2], 3, &repo).unwrap(), c0);
- 
        assert_eq!(quorum(&[*c1, *c1, *c2], 2, &repo).unwrap(), c1);
- 
        assert_eq!(quorum(&[*c1, *c1, *c2], 1, &repo).unwrap(), c2);
- 
        assert_eq!(quorum(&[*c2, *c2, *c1], 1, &repo).unwrap(), c2);
-
- 
        // B2 C2
- 
        //   \|
- 
        //   C1
- 
        //   |
- 
        //  C0
- 
        assert_matches!(
- 
            quorum(&[*c1, *c2, *b2], 1, &repo),
- 
            Err(QuorumError::NoQuorum)
- 
        );
- 
        assert_matches!(quorum(&[*c2, *b2], 1, &repo), Err(QuorumError::NoQuorum));
- 
        assert_matches!(quorum(&[*b2, *c2], 1, &repo), Err(QuorumError::NoQuorum));
- 
        assert_matches!(quorum(&[*c2, *b2], 2, &repo), Err(QuorumError::NoQuorum));
- 
        assert_matches!(quorum(&[*b2, *c2], 2, &repo), Err(QuorumError::NoQuorum));
- 
        assert_eq!(quorum(&[*c1, *c2, *b2], 2, &repo).unwrap(), c1);
- 
        assert_eq!(quorum(&[*c1, *c2, *b2], 3, &repo).unwrap(), c1);
- 
        assert_eq!(quorum(&[*b2, *b2, *c2], 2, &repo).unwrap(), b2);
- 
        assert_eq!(quorum(&[*b2, *c2, *c2], 2, &repo).unwrap(), c2);
- 
        assert_matches!(
- 
            quorum(&[*b2, *b2, *c2, *c2], 2, &repo),
- 
            Err(QuorumError::NoQuorum)
- 
        );
-
- 
        // B2 C2 C3
- 
        //  \ | /
- 
        //    C1
- 
        //    |
- 
        //    C0
- 
        assert_eq!(quorum(&[*b2, *c2, *c2], 2, &repo).unwrap(), c2);
- 
        assert_matches!(
- 
            quorum(&[*b2, *c2, *c2], 3, &repo),
- 
            Err(QuorumError::NoQuorum)
- 
        );
- 
        assert_matches!(
- 
            quorum(&[*b2, *c2, *b2, *c2], 3, &repo),
- 
            Err(QuorumError::NoQuorum)
- 
        );
- 
        assert_matches!(
- 
            quorum(&[*c3, *b2, *c2, *b2, *c2, *c3], 3, &repo),
- 
            Err(QuorumError::NoQuorum)
- 
        );
-
- 
        //  B2 C2
- 
        //    \|
- 
        // A1 C1
- 
        //   \|
- 
        //   C0
- 
        assert_matches!(
- 
            quorum(&[*c2, *b2, *a1], 1, &repo),
- 
            Err(QuorumError::NoQuorum)
- 
        );
- 
        assert_matches!(
- 
            quorum(&[*c2, *b2, *a1], 2, &repo),
- 
            Err(QuorumError::NoQuorum)
- 
        );
- 
        assert_matches!(
- 
            quorum(&[*c2, *b2, *a1], 3, &repo),
- 
            Err(QuorumError::NoQuorum)
- 
        );
- 
        assert_matches!(
- 
            quorum(&[*c1, *c2, *b2, *a1], 4, &repo),
- 
            Err(QuorumError::NoQuorum)
- 
        );
- 
        assert_eq!(quorum(&[*c0, *c1, *c2, *b2, *a1], 2, &repo).unwrap(), c1,);
- 
        assert_eq!(quorum(&[*c0, *c1, *c2, *b2, *a1], 3, &repo).unwrap(), c1,);
- 
        assert_eq!(quorum(&[*c0, *c2, *b2, *a1], 3, &repo).unwrap(), c0);
- 
        assert_eq!(quorum(&[*c0, *c1, *c2, *b2, *a1], 4, &repo).unwrap(), c0,);
- 
        assert_matches!(
- 
            quorum(&[*a1, *a1, *c2, *c2, *c1], 2, &repo),
- 
            Err(QuorumError::NoQuorum)
- 
        );
- 
        assert_matches!(
- 
            quorum(&[*a1, *a1, *c2, *c2, *c1], 1, &repo),
- 
            Err(QuorumError::NoQuorum)
- 
        );
- 
        assert_matches!(
- 
            quorum(&[*a1, *a1, *c2], 1, &repo),
- 
            Err(QuorumError::NoQuorum)
- 
        );
- 
        assert_matches!(
- 
            quorum(&[*b2, *b2, *c2, *c2], 1, &repo),
- 
            Err(QuorumError::NoQuorum)
- 
        );
- 
        assert_matches!(
- 
            quorum(&[*b2, *b2, *c2, *c2, *a1], 1, &repo),
- 
            Err(QuorumError::NoQuorum)
- 
        );
-
- 
        //    M2  M1
- 
        //    /\  /\
- 
        //    \ B2 C2
- 
        //     \  \|
- 
        //     A1 C1
- 
        //       \|
- 
        //       C0
- 
        assert_eq!(quorum(&[*m1], 1, &repo).unwrap(), m1);
- 
        assert_matches!(quorum(&[*m1, *m2], 1, &repo), Err(QuorumError::NoQuorum));
- 
        assert_matches!(quorum(&[*m2, *m1], 1, &repo), Err(QuorumError::NoQuorum));
- 
        assert_matches!(quorum(&[*m1, *m2], 2, &repo), Err(QuorumError::NoQuorum));
- 
        assert_matches!(
- 
            quorum(&[*m1, *m2, *c2], 1, &repo),
- 
            Err(QuorumError::NoQuorum)
- 
        );
- 
        assert_matches!(quorum(&[*m1, *a1], 1, &repo), Err(QuorumError::NoQuorum));
- 
        assert_matches!(quorum(&[*m1, *a1], 2, &repo), Err(QuorumError::NoQuorum));
- 
        assert_eq!(quorum(&[*m1, *m2, *b2, *c1], 4, &repo).unwrap(), c1);
- 
        assert_eq!(quorum(&[*m1, *m1, *b2], 2, &repo).unwrap(), m1);
- 
        assert_eq!(quorum(&[*m1, *m1, *c2], 2, &repo).unwrap(), m1);
- 
        assert_eq!(quorum(&[*m2, *m2, *b2], 2, &repo).unwrap(), m2);
- 
        assert_eq!(quorum(&[*m2, *m2, *a1], 2, &repo).unwrap(), m2);
- 
        assert_eq!(quorum(&[*m1, *m1, *b2, *b2], 2, &repo).unwrap(), m1);
- 
        assert_eq!(quorum(&[*m1, *m1, *c2, *c2], 2, &repo).unwrap(), m1);
- 
        assert_eq!(quorum(&[*m1, *b2, *c1, *c0], 3, &repo).unwrap(), c1);
- 
        assert_eq!(quorum(&[*m1, *b2, *c1, *c0], 4, &repo).unwrap(), c0);
- 
    }
-
- 
    #[test]
- 
    fn test_quorum_merges() {
- 
        let tmp = tempfile::tempdir().unwrap();
- 
        let (repo, c0) = fixtures::repository(tmp.path());
- 
        let c0: git::Oid = c0.into();
- 
        let c1 = fixtures::commit("C1", &[*c0], &repo);
- 
        let c2 = fixtures::commit("C2", &[*c0], &repo);
- 
        let c3 = fixtures::commit("C3", &[*c0], &repo);
-
- 
        let m1 = fixtures::commit("M1", &[*c1, *c2], &repo);
- 
        let m2 = fixtures::commit("M2", &[*c2, *c3], &repo);
-
- 
        eprintln!("C0: {c0}");
- 
        eprintln!("C1: {c1}");
- 
        eprintln!("C2: {c2}");
- 
        eprintln!("C3: {c3}");
- 
        eprintln!("M1: {m1}");
- 
        eprintln!("M2: {m2}");
-
- 
        //    M2  M1
- 
        //    /\  /\
- 
        //   C1 C2 C3
- 
        //     \| /
- 
        //      C0
- 
        assert_matches!(quorum(&[*m1, *m2], 1, &repo), Err(QuorumError::NoQuorum));
- 
        assert_matches!(quorum(&[*m1, *m2], 2, &repo), Err(QuorumError::NoQuorum));
-
- 
        let m3 = fixtures::commit("M3", &[*c2, *c1], &repo);
-
- 
        //   M3/M2 M1
- 
        //    /\  /\
- 
        //   C1 C2 C3
- 
        //     \| /
- 
        //      C0
- 
        assert_matches!(quorum(&[*m1, *m3], 1, &repo), Err(QuorumError::NoQuorum));
- 
        assert_matches!(quorum(&[*m1, *m3], 2, &repo), Err(QuorumError::NoQuorum));
- 
        assert_matches!(quorum(&[*m3, *m1], 1, &repo), Err(QuorumError::NoQuorum));
- 
        assert_matches!(quorum(&[*m3, *m1], 2, &repo), Err(QuorumError::NoQuorum));
- 
        assert_matches!(quorum(&[*m3, *m2], 1, &repo), Err(QuorumError::NoQuorum));
- 
        assert_matches!(quorum(&[*m3, *m2], 2, &repo), Err(QuorumError::NoQuorum));
- 
    }
-
- 
    #[test]

    fn test_remote_refs() {

        let dir = tempfile::tempdir().unwrap();

        let signer = MockSigner::default();