radicle 0.23.0

pub mod error;

mod iter;

#[cfg(test)]
mod test;

use std::collections::{BTreeMap, HashMap};
use std::num::NonZeroUsize;
use std::path::Path;

use crypto::{signature, PublicKey};
use nonempty::NonEmpty;
use radicle_core::{NodeId, RepoId};
use radicle_git_metadata::commit::CommitData;
use radicle_oid::Oid;

use crate::git;
use crate::identity::doc;
use crate::storage::refs::sigrefs::git::{object, reference};
use crate::storage::refs::{
    FeatureLevel, Refs, SignedRefs, IDENTITY_ROOT, REFS_BLOB_PATH, SIGNATURE_BLOB_PATH,
    SIGREFS_BRANCH,
};

/// A `rad/sigrefs` that has passed the following verification checks:
///
/// - Has a valid `/signature` blob, which is verified by the signing key.
/// - Contains the `refs/rad/root` entry under `/refs`, which matches the
///   [`RepoId`] of the local repository.
/// - The `refs/rad/sigrefs-parent` entry matches the commit's parent, if the
///   entry exists.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct VerifiedCommit {
    /// The commit that was verified.
    commit: Commit,
    /// The feature level that was recognized for the commit that was verified.
    level: FeatureLevel,
}

impl VerifiedCommit {
    /// Borrow the [`Commit`] that was verified.
    pub(super) fn commit(&self) -> &Commit {
        &self.commit
    }

    // The [`FeatureLevel`] of the refs in this commit.
    #[cfg(test)]
    pub(super) fn level(&self) -> FeatureLevel {
        self.level
    }

    pub(crate) fn into_sigrefs_at(self, id: PublicKey) -> SignedRefs {
        SignedRefs {
            refs: self.commit.refs,
            signature: self.commit.signature,
            id,
            level: self.level,
            parent: self.commit.parent,
            at: self.commit.oid,
        }
    }
}

/// A [`SignedRefsReader`] reads and verifies a commit chain for a `rad/sigrefs`
/// entry.
///
/// To create a new reader, use [`SignedRefsReader::new`].
///
/// The construction expects:
/// - A [`RepoId`] which is the repository identifier of the Radicle repository.
/// - A [`Tip`] which describes where and how to start the verification.
/// - A `repository` which is the Git repository that is being used for the reading.
/// - A `verifier` which is the entity that verifies the cryptographic signatures.
pub struct SignedRefsReader<'a, R, V> {
    rid: RepoId,
    tip: Tip,
    repository: &'a R,
    verifier: &'a V,
}

/// Describe where to start a [`SignedRefsReader`]'s commit chain.
pub enum Tip {
    /// Use the namespace of the given [`NodeId`], resolving their `rad/sigrefs`
    /// to its commit [`Oid`].
    Reference(NodeId),
    /// Use the supplied commit [`Oid`].
    Commit(Oid),
}

/// Describes the feature levels of a history of commits.
#[derive(Debug, PartialEq)]
pub struct FeatureLevels(BTreeMap<FeatureLevel, Oid>);

impl FeatureLevels {
    fn new() -> Self {
        Self(BTreeMap::new())
    }

    pub fn max(&self) -> FeatureLevel {
        self.0.last_key_value().map(|(k, _)| *k).unwrap_or_default()
    }

    fn insert(&mut self, verified: &VerifiedCommit) {
        if verified.level != FeatureLevel::None {
            self.0.entry(verified.level).or_insert(verified.commit.oid);
        }
    }

    #[cfg(any(test, feature = "test"))]
    pub fn test(from: impl IntoIterator<Item = (FeatureLevel, Oid)>) -> Self {
        Self(BTreeMap::from_iter(from))
    }
}

impl std::fmt::Display for FeatureLevels {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.write_str(
            &self
                .0
                .iter()
                .map(|(level, at)| format!("{level}@{at}"))
                .collect::<Vec<_>>()
                .join(", "),
        )
    }
}

impl<'a, R, V> SignedRefsReader<'a, R, V>
where
    R: object::Reader + reference::Reader,
    V: signature::Verifier<crypto::Signature>,
{
    /// Construct a new [`SignedRefsReader`].
    pub fn new(rid: RepoId, tip: Tip, repository: &'a R, verifier: &'a V) -> Self {
        Self {
            rid,
            tip,
            repository,
            verifier,
        }
    }

    /// Read a [`VerifiedCommit`] using the [`SignedRefsReader`], from a
    /// linear history.
    ///
    /// The [`VerifiedCommit`] will be the latest commit, if the commit verifies
    /// and contains its parent in its [`Refs`] entry.
    ///
    /// If the commit does not contain a parent, but its signature is not
    /// repeated, then it is still returned.
    ///
    /// Otherwise, the latest commit that has no duplicate signatures in its
    /// ancestry is returned.
    ///
    /// # Replay Attacks
    ///
    /// The [`SignedRefsReader`] prevents replay attacks via two mechanisms:
    /// - The first is recording the parent commit in the `/refs` blob. This
    ///   prevents a replay by not allowing the same signature payload to be
    ///   used in a new commit, since the parents would not match. Note that
    ///   this does not detect replays by older clients, since they will not
    ///   include this entry in `/refs`.
    /// - The second mechanism uses the fact that a replay will give duplicate
    ///   signatures. This means that any repeated signatures will be skipped,
    ///   and the commit returned will be the first valid commit, that was not a
    ///   replay.
    pub fn read(self) -> Result<VerifiedCommit, error::Read> {
        const ONE: NonZeroUsize = NonZeroUsize::new(1).expect("one is non-zero");
        const SIGNATURES_COLLECTED: &str = "all signatures were collected";

        let mut head = CommitReader::new(self.resolve_tip()?, self.repository)
            .read()
            .map_err(error::Read::Commit)?
            .verify(self.rid, self.verifier)
            .map_err(error::Read::Verify)?;

        if head.commit.parent.is_none() && head.level == FeatureLevel::Root {
            head.level = FeatureLevel::Parent;
        }

        let head = head;

        if head.level >= FeatureLevel::Parent {
            // `head` is verified, thus we know that if the parent reference
            // exists, its target actually matches the parent OID.
            // The fact that the parent OID is a hash over all previous history
            // makes it *incredibly unlikely* or rather *practically impossible*
            // that the same `/refs` blob re-appears in previous history.
            // Thus, we can spare oureselves walking the history.
            return Ok(head);
        }

        // `seen` maps from signatures to the `NonEmpty` of commits they were
        // seen in. Note that for all sets of commits which share the same
        // signature, the `NonEmpty` in `seen` will be in reverse order of the
        // walk.  That is, the latest commit in the set will be at the first
        // position, and the earliest commit will be at the last position.
        //
        // `level` is the feature level of the history, which is
        // the maximum feature level over all commits in the history.
        let (seen, levels) = iter::Walk::new(head.commit.oid, self.repository).try_fold(
            (
                HashMap::<crypto::Signature, NonEmpty<Oid>>::new(),
                FeatureLevels::new(),
            ),
            |(mut seen, mut levels), commit| {
                let commit = commit.map_err(error::Read::Commit)?;

                seen.entry(commit.signature)
                    .and_modify(|value| value.push(commit.oid))
                    .or_insert_with(|| NonEmpty::new(commit.oid));

                // Before `commit` can be interpreted for feature detection,
                // it must be verified. In particular, we do not want to
                // detect features on commits that have an invalid signature.
                // However, if we have already reached the maximum level,
                // this is not required anymore, since it cannot increase any
                // further.
                if levels.max() < FeatureLevel::LATEST {
                    let commit = commit
                        .verify(self.rid, self.verifier)
                        .map_err(error::Read::Verify)?;

                    if commit.level > FeatureLevel::None {
                        levels.insert(&commit);
                    }
                }

                Ok((seen, levels))
            },
        )?;

        let level = levels.max();

        if head.level < level {
            return Err(error::Read::Downgrade {
                levels,
                actual: head.level,
                commit: head.commit.oid,
            });
        }

        if seen
            .get(&head.commit.signature)
            .expect(SIGNATURES_COLLECTED)
            .len_nonzero()
            == ONE
        {
            // `head` has a verified, non-repeated signature, but does not
            // include the parent reference in the `/refs` blob. Maintains
            // backwards-compatibility.
            return Ok(head);
        }

        // If the signature in `head` was seen twice, then
        // `head` must have a parent.
        let parent = head.commit.parent.expect("parent must exist");

        // The second walk can start from the parent of `head`. We do not need to
        // verify `head` twice, and we already know that the parent exists.
        for commit in iter::Walk::new(parent, self.repository) {
            let verified = commit
                .map_err(error::Read::Commit)?
                .verify(self.rid, self.verifier)
                .map_err(error::Read::Verify)?;

            if verified.level < level {
                // To avoid downgrade attacks, we skip `commit`.
                continue;
            }

            let commit = verified.commit();

            let commits = seen.get(&commit.signature).expect(SIGNATURES_COLLECTED);
            if commits.len_nonzero() == ONE {
                return Ok(verified);
            }

            let id = &commit.oid;
            if id == commits.last() {
                // If this commit is the last element of `commits`,
                // then this means it is the earliest of all that share
                // its signature. It thus cannot have been replayed.
                return Ok(verified);
            }

            if id == commits.first() {
                // We only log one warning per set of duplicates, and that is
                // when we reach the first element of `commits`, which is the
                // latest in the history.
                log::warn!("Duplicate signature found in commits {commits:?}");
            }
        }

        unreachable!()
    }

    fn resolve_tip(&self) -> Result<Oid, error::Read> {
        match self.tip {
            Tip::Commit(oid) => Ok(oid),
            Tip::Reference(namespace) => {
                let reference =
                    SIGREFS_BRANCH.with_namespace(git::fmt::Component::from(&namespace));
                let head = self
                    .repository
                    .find_reference(&reference)
                    .map_err(error::Read::FindReference)?
                    .ok_or_else(|| error::Read::MissingSigrefs { namespace })?;
                Ok(head)
            }
        }
    }
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub(super) struct Commit {
    oid: Oid,
    parent: Option<Oid>,
    refs: Refs,
    signature: crypto::Signature,
    identity_root: Option<IdentityRoot>,
}

impl Commit {
    /// The [`Oid`] of this commit.
    pub(super) fn oid(&self) -> &Oid {
        &self.oid
    }

    /// The parent [`Oid`] of the commit, unless it is the root commit.
    #[cfg(test)]
    pub(super) fn parent(&self) -> Option<&Oid> {
        self.parent.as_ref()
    }

    /// The [`Refs`] found in the blob at `/refs` in in the tree of this commit.
    pub(super) fn refs(&self) -> &Refs {
        &self.refs
    }

    /// The [`crypto::Signature`] found in blob at `/signature` in the tree of the commit.
    #[cfg(test)]
    pub(super) fn signature(&self) -> &crypto::Signature {
        &self.signature
    }

    pub(super) fn verify<V>(
        mut self,
        expected: RepoId,
        verifier: &V,
    ) -> Result<VerifiedCommit, error::Verify>
    where
        V: signature::Verifier<crypto::Signature>,
    {
        verifier
            .verify(&self.refs.canonical(), &self.signature)
            .map_err(error::Verify::Signature)?;

        let level = if let Some(IdentityRoot {
            commit: identity_commit,
            rid,
        }) = self.identity_root
        {
            if rid != expected {
                return Err(error::Verify::MismatchedIdentity {
                    identity_commit,
                    sigrefs_commit: self.oid,
                    expected,
                    found: rid,
                });
            } else {
                FeatureLevel::Root
            }
        } else {
            FeatureLevel::None
        };

        self.refs.remove_sigrefs();

        let level = match (self.parent, self.refs.remove_parent()) {
            (None, None) | (Some(_), None) => {
                // Pattern 1:
                // We are looking at a root commit.
                // This is a special case, as there is no good value
                // for `rad/refs/sigrefs-parent` to target. The zero OID would
                // be a candidate, but it is filtered out in [`Refs`].
                // Upgrading to `FeatureLevel::Parent` is not a good idea
                // either, otherwise any history containing this commit
                // would be at that level from the root onwards.

                // Pattern 2:
                // The ref `refs/rad/sigrefs-parent` is simply absent,
                // we remain on the same feature level.

                level
            }
            (None, Some(actual)) => {
                // We are looking at a root commit.
                // Any target OID is treated as dangling.
                return Err(error::Verify::DanglingParent {
                    sigrefs_commit: self.oid,
                    actual,
                });
            }
            (Some(expected), Some(actual)) if expected == actual => {
                // We have a good value for `refs/rad/sigrefs-parent`, however,
                // as feature levels are monotonic, we also make sure that the
                // earlier check of `refs/rad/root` was positive.
                // In case the prior feature level was not `FeatureLevel::Root`,
                // we can even error early.
                if level == FeatureLevel::Root {
                    FeatureLevel::Parent
                } else {
                    return Err(error::Verify::IdentityRootDowngrade {
                        sigrefs_commit: self.oid,
                    });
                }
            }
            (Some(expected), Some(actual)) => {
                return Err(error::Verify::MismatchedParent {
                    sigrefs_commit: self.oid,
                    expected,
                    actual,
                })
            }
        };

        Ok(VerifiedCommit {
            commit: self,
            level,
        })
    }
}

pub(super) struct CommitReader<'a, R> {
    commit: Oid,
    repository: &'a R,
}

impl<'a, R> CommitReader<'a, R>
where
    R: object::Reader,
{
    pub(super) fn new(commit: Oid, repository: &'a R) -> Self {
        Self { commit, repository }
    }

    pub(super) fn read(self) -> Result<Commit, error::Commit> {
        let commit = self.read_commit_data()?;
        let Tree { refs, signature } = TreeReader::new(self.commit, self.repository)
            .read()
            .map_err(error::Commit::Tree)?;
        let identity_root = IdentityRootReader::new(&refs, self.repository)
            .read()
            .map_err(error::Commit::IdentityRoot)?;
        let parent = Self::get_parent(&commit).transpose()?;

        Ok(Commit {
            oid: self.commit,
            parent,
            refs,
            signature,
            identity_root,
        })
    }

    fn read_commit_data(&self) -> Result<CommitData<Oid, Oid>, error::Commit> {
        let bytes = self
            .repository
            .read_commit(&self.commit)
            .map_err(error::Commit::Read)?
            .ok_or(error::Commit::Missing { oid: self.commit })?;
        CommitData::from_bytes(&bytes).map_err(|err| error::Commit::Parse {
            oid: self.commit,
            source: err,
        })
    }

    /// Extract the single parent [`Oid`] from a [`CommitData`], if any.
    ///
    /// Returns `None` if the commit has no parents (i.e. it is a root commit).
    /// Returns an error if the commit has more than one parent, since the
    /// transparency log is a linear chain.
    fn get_parent(commit: &CommitData<Oid, Oid>) -> Option<Result<Oid, error::Commit>> {
        let NonEmpty {
            head: parent,
            tail: mut rest,
        } = NonEmpty::collect(commit.parents())?;
        if rest.is_empty() {
            Some(Ok(parent))
        } else {
            rest.insert(0, parent);
            let err = error::Commit::TooManyParents(error::Parent { parents: rest });
            Some(Err(err))
        }
    }
}

struct Tree {
    refs: Refs,
    signature: crypto::Signature,
}

struct TreeReader<'a, R> {
    commit: Oid,
    repository: &'a R,
}

impl<'a, R> TreeReader<'a, R>
where
    R: object::Reader,
{
    fn new(commit: Oid, repository: &'a R) -> Self {
        Self { commit, repository }
    }

    fn read(self) -> Result<Tree, error::Tree> {
        let (refs, signature) = self.try_handle_blobs()?;
        let refs = Refs::from_canonical(&refs.bytes).map_err(error::Tree::ParseRefs)?;
        let signature = crypto::Signature::try_from(signature.bytes.as_slice())
            .map_err(error::Tree::ParseSignature)?;
        Ok(Tree { refs, signature })
    }

    /// Fetch the refs blob and signature blob from the repository, returning a
    /// descriptive error if either or both are missing.
    fn try_handle_blobs(&self) -> Result<(object::Blob, object::Blob), error::Tree> {
        let commit = &self.commit;
        let refs_path = Path::new(REFS_BLOB_PATH);
        let sig_path = Path::new(SIGNATURE_BLOB_PATH);

        let refs_bytes = self
            .repository
            .read_blob(commit, refs_path)
            .map_err(error::Tree::Refs)?;
        let sig_bytes = self
            .repository
            .read_blob(commit, sig_path)
            .map_err(error::Tree::Signature)?;

        let result = match (refs_bytes, sig_bytes) {
            (None, None) => Err(error::MissingBlobs::Both {
                commit: *commit,
                refs: refs_path.to_path_buf(),
                signature: sig_path.to_path_buf(),
            }),
            (None, Some(_)) => Err(error::MissingBlobs::Signature {
                commit: *commit,
                path: sig_path.to_path_buf(),
            }),
            (Some(_), None) => Err(error::MissingBlobs::Refs {
                commit: *commit,
                path: refs_path.to_path_buf(),
            }),
            (Some(refs), Some(sig)) => Ok((refs, sig)),
        };

        result.map_err(error::Tree::from)
    }
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(super) struct IdentityRoot {
    commit: Oid,
    rid: RepoId,
}

struct IdentityRootReader<'a, 'b, R> {
    refs: &'a Refs,
    repository: &'b R,
}

impl<'a, 'b, R> IdentityRootReader<'a, 'b, R>
where
    R: object::Reader,
{
    fn new(refs: &'a Refs, repository: &'b R) -> Self {
        Self { refs, repository }
    }

    fn read(self) -> Result<Option<IdentityRoot>, error::IdentityRoot> {
        match self.refs.get(&IDENTITY_ROOT) {
            Some(commit) => self
                .read_blob(&commit)
                .map(|rid| Some(IdentityRoot { commit, rid })),
            None => Ok(None),
        }
    }

    fn read_blob(&self, commit: &Oid) -> Result<RepoId, error::IdentityRoot> {
        let path = Path::new("embeds").join(*doc::PATH);
        let object::Blob { oid, .. } = self
            .repository
            .read_blob(commit, &path)
            .map_err(error::IdentityRoot::Blob)?
            .ok_or_else(|| error::IdentityRoot::MissingIdentity { commit: *commit })?;
        Ok(RepoId::from(oid))
    }
}