Improve errors during canonical quorum — heartwood

The aim of this patch was to explore a scenario discovered in Zulip¹. When pushing to the default branch, an object was missing. To improve this, I needed to hunt down where the error was originating from.

The patch starts with refactoring the cases when the git push is not in the delete case. We classify if the push is opening a patch, updating a patch, or simply pushing a ref.

From there, we refactor the canonical computation by separating it out into its business logic. Here, I was able to refactor the error scenarios, and discovered that it was due to the missing commit during the converges calculation. The patch adds a check that all the commits are present, and if not, provide a better error message.

Finally, a test for the scenario outlined in Zulip is added showing how it can be recovered from.

¹

https://radicle.zulipchat.com/#narrow/channel/369873-support/topic/.60error.3A.20git.3A.20object.20not.20found.20-.20no.20match.20for.20id.60.20on.20push/with/527912706

 $ git push rad
 hint: you are attempting to push a commit that would cause your upstream to diverge from the canonical reference refs/heads/master
 hint: to integrate the remote changes, run `git pull --rebase` and try again
 error: refusing to update branch to commit that is not a descendant of canonical head
 error: refusing to update canonical reference to commit that is not a descendant of current canonical head
 error: failed to push some refs to 'rad://z42hL2jL4XNk6K8oHQaSWfMgCL7ji/z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi'
 ```

 Sometimes, commits may appear missing in the working copy when pushing to the
 default branch. In this scenario, we show this happening, and then how to
 recover from the problem.
 First, we need to be in a scenario where there is more than one delegate:
 ``` ~alice
 $ rad id update --title "Add Bob" --description "Add Bob as a delegate" --delegate did:key:z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk -q
 be665f9fccba97abb21b2fa85a6fd3181c72858
 ```
 ``` ~alice
 $ rad follow did:key:z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk
 ✓ Follow policy updated for z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk
 $ rad sync
 Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from the network, found 1 potential seed(s).
 ✓ Target met: 1 seed(s)
 🌱 Fetched from z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk
 ✓ Synced with 1 seed(s)
 $ rad id update --title "Bump threshold" --description "Bumping threshold to 2" --threshold 2 -q
 f515dc5af139b8eb9fa817df3f637f2acc29c12b
 $ rad sync -a
 ✓ Synced with 1 seed(s)
 ```
 ``` ~bob
 $ rad id accept f515dc5af139b8eb9fa817df3f637f2acc29c12b -q
 $ rad sync -a
 ✓ Synced with 1 seed(s)
 ```
 At this stage, Bob makes some changes at the same time, updating the default
 branch:
 ``` ~bob (stderr) RAD_SOCKET=/dev/null
 $ touch README.md
 $ git add README.md
 $ git commit -m "Add README"
 $ git push rad master
 To rad://z42hL2jL4XNk6K8oHQaSWfMgCL7ji/z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk
    f2de534..361f146  master -> master
 ```
 Alice, is also busy making some changes:
 ``` ~alice
 $ rad sync -f
 Fetching rad:z42hL2jL4XNk6K8oHQaSWfMgCL7ji from the network, found 1 potential seed(s).
 ✓ Target met: 1 seed(s)
 🌱 Fetched from z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk
 ```
 ``` ~alice
 $ touch LICENSE
 $ git add LICENSE
 $ git commit -m "Add LICENSE"
 [master 62d19fd] Add LICENSE
 file changed, 0 insertions(+), 0 deletions(-)
  create mode 100644 LICENSE
 ```
 However, when she goes to push to the default branch she sees an error about a missing commit from Bob:
 ``` ~alice (fails) (stderr)
 $ git push rad master
 error: the commit 361f146ec7339fffdea1ea586f51410250bec9cf for did:key:z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk is missing from the repository [..]
 error: failed to push some refs to 'rad://z42hL2jL4XNk6K8oHQaSWfMgCL7ji/z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi'
 ```
 The reason for this is that when attempting to compute the canonical commit for
 the default branch, there are some checks to see if the delegates agree on the
 new commit. In this case, Bob's commit was not available to perform this check,
 so, Alice must fetch from Bob's state of the repository. She can do this by
 adding him as a remote:
 ``` ~alice
 $ rad remote add did:key:z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk --name "bob"
 ✓ Remote bob added
 ✓ Remote-tracking branch bob/master created for z6Mkt67GdsW7715MEfRuP4pSZxJRJh6kj6Y48WRqVv4N1tRk
 ```
 ``` ~alice (stderr) RAD_SOCKET=/dev/null
 $ git push rad master
 To rad://z42hL2jL4XNk6K8oHQaSWfMgCL7ji/z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi
    f2de534..62d19fd  master -> master
 ```
 Note that if the remote tracking branch already exists, then she can simply `git
 fetch bob/master`.

 }
 #[test]
 fn rad_id_missing_commits() {
     let mut environment = Environment::new();
     let alice = environment.node("alice");
     let bob = environment.node("bob");
     let acme = RepoId::from_str("z42hL2jL4XNk6K8oHQaSWfMgCL7ji").unwrap();
     environment.repository(&alice);
     test(
         "examples/rad-init.md",
         environment.work(&alice),
         Some(&alice.home),
         [],
     )
     .unwrap();
     let mut alice = alice.spawn();
     let mut bob = bob.spawn();
     bob.handle.seed(acme, Scope::All).unwrap();
     alice.connect(&bob).converge([&bob]);
     bob.fork(acme, environment.work(&bob)).unwrap();
     formula(&environment.tempdir(), "examples/rad-id-missing-commits.md")
         .unwrap()
         .home(
             "alice",
             environment.work(&alice),
             [("RAD_HOME", alice.home.path().display())],
         )
         .home(
             "bob",
             environment.work(&bob).join("heartwood"),
             [("RAD_HOME", bob.home.path().display())],
         )
         .run()
         .unwrap();
 }
 #[test]
 fn rad_id_update_delete_field() {
     Environment::alice(["rad-init", "rad-id-update-delete-field"]);
 }

 #![allow(clippy::too_many_arguments)]
 mod canonical;
 mod error;
 use std::collections::HashMap;
 use std::io::IsTerminal;
 use std::path::{Path, PathBuf};

 use radicle::cob::patch::cache::Patches as _;
 use radicle::crypto;
 use radicle::explorer::ExplorerResource;
 use radicle::git::canonical;
 use radicle::identity::{CanonicalRefs, Did};
 use radicle::node;
 use radicle::node::{Handle, NodeId};

 use radicle_cli as cli;
 use radicle_cli::terminal as term;
 use crate::{hint, read_line, warn, Options};
 use crate::{hint, read_line, Options};
 #[derive(Debug, Error)]
 pub enum Error {

     /// No public key is given
     #[error("no public key given as a remote namespace, perhaps you are attempting to push to restricted refs")]
     NoKey,
     /// Head being pushed diverges from canonical head.
     #[error("refusing to update branch to commit that is not a descendant of canonical head")]
     HeadsDiverge(git::Oid, git::Oid),
     /// User tried to delete the canonical branch.
     #[error("refusing to delete default branch ref '{0}'")]
     DeleteForbidden(git::RefString),

     /// Invalid reference name.
     #[error("invalid ref: {0}")]
     InvalidRef(#[from] radicle::git::fmt::Error),
     /// Invalid reference name.
     #[error("invalid qualified ref: {0}")]
     InvalidQualifiedRef(git::RefString),
     /// Git error.
     #[error("git: {0}")]
     Git(#[from] git::raw::Error),

     Quorum(#[from] radicle::git::canonical::QuorumError),
     #[error(transparent)]
     CanonicalRefs(#[from] radicle::identity::doc::CanonicalRefsError),
     #[error(transparent)]
     PushAction(#[from] error::PushAction),
     #[error(transparent)]
     Canonical(#[from] error::CanonicalUnrecoverable),
 }
 /// Push command.

     }
 }
 enum PushAction {
     OpenPatch,
     UpdatePatch {
         dst: git::Qualified<'static>,
         patch: patch::PatchId,
     },
     PushRef {
         dst: git::Qualified<'static>,
     },
 }
 impl PushAction {
     fn new(dst: &git::RefString) -> Result<Self, error::PushAction> {
         if dst == &*rad::PATCHES_REFNAME {
             Ok(Self::OpenPatch)
         } else {
             let dst = git::Qualified::from_refstr(dst)
                 .ok_or_else(|| error::PushAction::InvalidRef {
                     refname: dst.clone(),
                 })?
                 .to_owned();
             if let Some(oid) = dst.strip_prefix(git::refname!("refs/heads/patches")) {
                 let patch = git::Oid::from_str(oid)
                     .map_err(|err| error::PushAction::InvalidPatchId {
                         suffix: oid.to_string(),
                         source: err,
                     })
                     .map(patch::PatchId::from)?;
                 Ok(Self::UpdatePatch { dst, patch })
             } else {
                 Ok(Self::PushRef { dst })
             }
         }
     }
 }
 /// Run a git push command.
 pub fn run(
     mut specs: Vec<String>,

             }
             Command::Push(git::Refspec { src, dst, force }) => {
                 let patches = crate::patches_mut(profile, stored)?;
                 let action = PushAction::new(dst)?;
                 if dst == &*rad::PATCHES_REFNAME {
                     patch_open(
                 match action {
                     PushAction::OpenPatch => patch_open(
                         src,
                         &remote,
                         &nid,

                         &signer,
                         profile,
                         opts.clone(),
                     )
                 } else {
                     let dst = git::Qualified::from_refstr(dst)
                         .ok_or_else(|| Error::InvalidQualifiedRef(dst.clone()))?;
                     if let Some(oid) = dst.strip_prefix(git::refname!("refs/heads/patches")) {
                         let oid = git::Oid::from_str(oid)?;
                         patch_update(
                             src,
                             &dst,
                             *force,
                             &oid,
                             &nid,
                             &working,
                             stored,
                             patches,
                             &signer,
                             opts.clone(),
                         )
                     } else {
                     ),
                     PushAction::UpdatePatch { dst, patch } => patch_update(
                         src,
                         &dst,
                         *force,
                         patch,
                         &nid,
                         &working,
                         stored,
                         patches,
                         &signer,
                         opts.clone(),
                     ),
                     PushAction::PushRef { dst } => {
                         let identity = stored.identity()?;
                         let crefs = identity.canonical_refs_or_default(|| {
                             let rule = identity.doc().default_branch_rule()?;

                         //
                         // Note that we *do* allow rolling back to a previous commit on the
                         // canonical branch.
                         if let Some(mut canonical) = rules.canonical(dst.clone(), stored)? {
                             if canonical.is_allowed(&me) {
                                 let head = *src;
                                 let converges = canonical.converges(&working, (&me, &head))?;
                                 // If `canonical` is empty then we're creating a new reference.
                                 // If we're the only delegate then we need to modify our vote.
                                 if converges || canonical.has_no_tips() || canonical.is_only(&me) {
                                     canonical.modify_vote(me, head);
                                 }
                                 match canonical.quorum(&working) {
                                     Ok((dst, 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(
                                                     format!("you are attempting to push a commit that would cause \
                                                     your upstream to diverge from the canonical reference {dst}"),
                                                 );
                                                 hint(
                                                     "to integrate the remote changes, run `git pull --rebase` \
                                                     and try again",
                                                 );
                                             }
                                             return Err(Error::HeadsDiverge(head, canonical_oid));
                                         }
                                         set_canonical_refs
                                             .push((dst.clone().to_owned(), canonical_oid));
                                     }
                                     Err(canonical::QuorumError::Git(e)) => return Err(e.into()),
                                     Err(e) => {
                                         warn(e.to_string());
                                         warn("it is recommended to find a commit to agree upon");
                                     }
                                 }
                         if let Some(canonical) = rules.canonical(dst.clone(), stored)? {
                             let canonical = canonical::Canonical::new(me, *src, canonical);
                             match canonical.quorum(&working) {
                                 Ok(quorum) => set_canonical_refs.push(quorum),
                                 Err(e) => canonical::io::handle_error(e, &dst, hints)?,
                             }
                         }
                         push(src, &dst, *force, &nid, &working, stored, patches, &signer)

     src: &git::Oid,
     dst: &git::Qualified,
     force: bool,
     oid: &git::Oid,
     patch_id: patch::PatchId,
     nid: &NodeId,
     working: &git::raw::Repository,
     stored: &storage::git::Repository,

     G: crypto::signature::Signer<crypto::Signature>,
 {
     let commit = *src;
     let patch_id = radicle::cob::ObjectId::from(oid);
     let dst = dst.with_namespace(nid.into());
     push_ref(src, &dst, force, working, stored.raw())?;

 use radicle::git;
 use radicle::git::raw::Repository;
 use radicle::prelude::Did;
 use super::error;
 pub(crate) struct Vote {
     did: Did,
     commit: git::Oid,
 }
 /// Validates a vote to update a canonical reference during push.
 pub(crate) struct Canonical<'a, 'b> {
     vote: Vote,
     canonical: git::canonical::Canonical<'a, 'b>,
 }
 impl<'a, 'b> Canonical<'a, 'b> {
     pub fn new(me: Did, head: git::Oid, canonical: git::canonical::Canonical<'a, 'b>) -> Self {
         Self {
             vote: Vote {
                 did: me,
                 commit: head,
             },
             canonical,
         }
     }
     /// Calculates the quorum of the [`git::canonical::Canonical`] provided.
     ///
     /// In some cases, it ensures that the [`head`] is attempting to converge
     /// with the set of commits of the other [`Did`]s.
     ///
     /// If a quorum is found, then it is also ensured that the new [`head`] is a
     /// descendant of the current canonical commit, otherwise the commits are
     /// considered diverging.
     ///
     /// # Errors
     ///
     /// Ensures that the commits of the other [`Did`]s are in the working
     /// copy, and that checks that any two commits are related in the graph.
     ///
     /// Ensures that the new head and the canonical commit do not diverge.
     ///
     /// [`head`]: crate::push::canonical::Canonical::head
     pub fn quorum(
         mut self,
         working: &Repository,
     ) -> Result<(git::Qualified<'a>, git::Oid), error::Canonical> {
         let converges = self
             .canonical
             .converges(working, (&self.vote.did, &self.vote.commit))?;
         if converges || self.canonical.has_no_tips() || self.canonical.is_only(&self.vote.did) {
             self.canonical.modify_vote(self.vote.did, self.vote.commit);
         }
         match self.canonical.quorum(working) {
             Ok((cref, quorum_head)) => {
                 // Canonical head is an ancestor of head.
                 let is_ff = self.vote.commit == quorum_head
                     || working
                         .graph_descendant_of(*self.vote.commit, *quorum_head)
                         .map_err(|err| {
                             error::Canonical::graph_descendant(self.vote.commit, quorum_head, err)
                         })?;
                 if !is_ff && !converges {
                     Err(error::Canonical::heads_diverge(
                         self.vote.commit,
                         quorum_head,
                     ))
                 } else {
                     Ok((cref, quorum_head))
                 }
             }
             Err(err) => Err(err.into()),
         }
     }
 }
 pub(crate) mod io {
     use radicle::git;
     use radicle::git::canonical;
     use crate::push::error;
     use crate::{hint, warn};
     /// Handle recoverable errors, printing relevant information to the
     /// terminal. Otherwise, convert the error into an unrecoverable error
     /// [`error::CanonicalUnrecoverable`].
     pub fn handle_error(
         e: error::Canonical,
         canonical: &git::Qualified,
         hints: bool,
     ) -> Result<(), error::CanonicalUnrecoverable> {
         match e {
             error::Canonical::GraphDescendant(e) => Err(e.into()),
             error::Canonical::Converges(e) => Err(e.into()),
             error::Canonical::HeadsDiverge(e) => {
                 if hints {
                     hint(
                         format!("you are attempting to push a commit that would cause \
                                                  your upstream to diverge from the canonical reference {canonical}"),
                     );
                     hint(
                         "to integrate the remote changes, run `git pull --rebase` \
                                                  and try again",
                     );
                 }
                 Err(e.into())
             }
             error::Canonical::Quorum(e) => match e {
                 e @ canonical::QuorumError::Diverging { .. } => {
                     warn(e.to_string());
                     warn("it is recommended to find a commit to agree upon");
                     Ok(())
                 }
                 e @ canonical::QuorumError::NoCandidates { .. } => {
                     warn(e.to_string());
                     warn("it is recommended to find a commit to agree upon");
                     Ok(())
                 }
                 canonical::QuorumError::Git(err) => {
                     Err(error::CanonicalUnrecoverable::Git { source: err })
                 }
             },
         }
     }
 }

 use radicle::git;
 use radicle::git::canonical;
 use thiserror::Error;
 #[derive(Debug, Error)]
 pub enum CanonicalUnrecoverable {
     #[error(transparent)]
     GraphDescendant(#[from] GraphDescendant),
     #[error(transparent)]
     Converges(#[from] canonical::ConvergesError),
     #[error(transparent)]
     HeadsDiverge(#[from] HeadsDiverge),
     #[error("failure while computing canonical reference: {source}")]
     Git { source: git::raw::Error },
 }
 #[derive(Debug, Error)]
 pub enum Canonical {
     #[error(transparent)]
     GraphDescendant(GraphDescendant),
     #[error(transparent)]
     Converges(#[from] canonical::ConvergesError),
     #[error(transparent)]
     HeadsDiverge(HeadsDiverge),
     #[error(transparent)]
     Quorum(#[from] canonical::QuorumError),
 }
 impl Canonical {
     pub fn graph_descendant(head: git::Oid, canonical: git::Oid, source: git::raw::Error) -> Self {
         Self::GraphDescendant(GraphDescendant {
             head,
             canonical,
             source,
         })
     }
     pub fn heads_diverge(head: git::Oid, canonical: git::Oid) -> Self {
         Self::HeadsDiverge(HeadsDiverge { head, canonical })
     }
 }
 #[derive(Debug, Error)]
 #[error("failed to check if {head} is an ancestor of {canonical} due to: {source}")]
 pub struct GraphDescendant {
     head: git::Oid,
     canonical: git::Oid,
     source: git::raw::Error,
 }
 #[derive(Debug, Error)]
 /// Head being pushed diverges from canonical head.
 #[error("refusing to update canonical reference to commit that is not a descendant of current canonical head")]
 pub struct HeadsDiverge {
     head: git::Oid,
     canonical: git::Oid,
 }
 #[derive(Debug, Error)]
 pub enum PushAction {
     #[error("invalid reference {refname}, expected qualified reference starting with `refs/`")]
     InvalidRef { refname: git::RefString },
     #[error("found refs/heads/patches/{suffix} where {suffix} was an invalid Patch ID")]
     InvalidPatchId {
         suffix: String,
         source: git::raw::Error,
     },
 }

 pub use rules::{MatchedRule, RawRule, Rules, ValidRule};
 use std::collections::BTreeMap;
 use std::path::PathBuf;
 use raw::Repository;
 use thiserror::Error;

     Git(#[from] git2::Error),
 }
 #[derive(Debug, Error)]
 #[error("failed to check if {head} is an ancestor of {canonical} due to: {source}")]
 pub struct GraphDescendant {
     head: Oid,
     canonical: Oid,
     source: raw::Error,
 }
 #[derive(Debug, Error)]
 #[error("the commit {commit} for {did} is missing from the repository {repo:?}")]
 pub struct MissingCommit {
     repo: PathBuf,
     did: Did,
     commit: Oid,
     source: raw::Error,
 }
 #[derive(Debug, Error)]
 #[error("could not determine whether the commit {commit} for {did} is part of the repository {repo:?} due to: {source}")]
 pub struct InvalidCommit {
     repo: PathBuf,
     did: Did,
     commit: Oid,
     source: raw::Error,
 }
 #[derive(Debug, Error)]
 pub enum ConvergesError {
     #[error(transparent)]
     GraphDescendant(#[from] GraphDescendant),
     #[error(transparent)]
     MissingCommit(#[from] MissingCommit),
     #[error(transparent)]
     InvalidCommit(#[from] InvalidCommit),
 }
 impl ConvergesError {
     pub fn graph_descendant(head: Oid, canonical: Oid, source: raw::Error) -> Self {
         Self::GraphDescendant(GraphDescendant {
             head,
             canonical,
             source,
         })
     }
     pub fn missing_commit(repo: PathBuf, did: Did, commit: Oid, err: raw::Error) -> Self {
         Self::MissingCommit(MissingCommit {
             repo,
             did,
             commit,
             source: err,
         })
     }
     pub fn invalid_commit(repo: PathBuf, did: Did, commit: Oid, err: raw::Error) -> Self {
         Self::InvalidCommit(InvalidCommit {
             repo,
             did,
             commit,
             source: err,
         })
     }
 }
 impl<'a, 'b> Canonical<'a, 'b> {
     /// Construct the set of canonical tips given for the given `rule` and
     /// the reference `refname`.

     pub fn converges(
         &self,
         repo: &Repository,
         candidate: (&Did, &Oid),
     ) -> Result<bool, raw::Error> {
         for tip in self
             .tips
             .iter()
             .filter_map(|(did, tip)| (did != candidate.0).then_some(tip))
         {
             let (ahead, behind) = repo.graph_ahead_behind(**candidate.1, **tip)?;
         (candidate, commit): (&Did, &Oid),
     ) -> Result<bool, ConvergesError> {
         let heads = {
             let mut heads = self
                 .tips
                 .iter()
                 .filter_map(|(did, tip)| (did != candidate).then_some((did, tip)));
             heads.try_fold(
                 Vec::with_capacity(heads.size_hint().0),
                 |mut heads, (did, head)| {
                     heads.push(Self::ensure_commit(*did, *head, repo)?);
                     Ok::<_, ConvergesError>(heads)
                 },
             )?
         };
         for head in heads {
             let (ahead, behind) = repo
                 .graph_ahead_behind(**commit, *head)
                 .map_err(|err| ConvergesError::graph_descendant(*commit, head, err))?;
             if ahead * behind == 0 {
                 return Ok(true);
             }

     fn threshold(&self) -> usize {
         (*self.rule.threshold()).into()
     }
     fn ensure_commit(from: Did, commit: Oid, working: &Repository) -> Result<Oid, ConvergesError> {
         match working.find_commit(*commit).map(|_| commit) {
             Ok(oid) => Ok(oid),
             Err(err) if err.code() == raw::ErrorCode::NotFound => Err(
                 ConvergesError::missing_commit(working.path().to_path_buf(), from, commit, err),
             ),
             Err(err) => Err(ConvergesError::invalid_commit(
                 working.path().to_path_buf(),
                 from,
                 commit,
                 err,
             )),
         }
     }
 }
 #[cfg(test)]