grit-lib 0.5.24

//! Building blocks for custom [`RefStore`](super::RefStore) backends.
//!
//! A backend that keeps refs somewhere other than a git directory (a database, a network
//! service, an in-process map) does not have to re-derive Git's ref-update rules. The helpers
//! here are the ones the built-in backends use:
//!
//! - [`check_transaction`] runs every check [`RefStore::prepare`](super::RefStore::prepare)
//!   must make: ref names and null ids ([`validate_transaction`]), directory/file conflicts
//!   ([`verify_create_conflicts`]), compare-and-swap expectations ([`expected_matches`],
//!   through symbolic refs) and two updates writing the same stored ref.
//! - [`apply_transaction`] computes the refs and reflogs after a commit, including
//!   symbolic-ref dereferencing and the reflog lines appended to both the symbolic ref and
//!   its target.
//! - [`resolve_symbolic`] follows symbolic refs inside a [`RefBatchState`].
//!
//! A typical store loads the refs (and reflogs) a transaction touches into a
//! [`RefBatchState`], calls [`check_transaction`] in `prepare` while holding its lock, and
//! at commit applies [`apply_transaction`] to a copy and persists the difference.
//! `MemoryRefStore` is implemented exactly this way. Run the
//! `grit_test_support::refstore_conformance` suite to check a backend against the built-ins.

use std::collections::BTreeMap;

use crate::objects::{ObjectId, ObjectKind};
use crate::refs::SYMREF_MAXDEPTH;

use super::apply::{
    apply_case_only_ref_rename, apply_reflog_rename, apply_update, simulate_batch_apply,
};
use super::error::{BackendError, RefStoreError};
use super::transaction::RefTransaction;
use super::validation::validate_storable_refname as validate_name;
use super::{RawRef, RefUpdate};

pub use super::apply::RefBatchState;
pub use super::transaction::expected_matches;
pub use super::validation::verify_create_conflicts;

/// Reject `name` when Git refuses to store it (path traversal, illegal components, a
/// `.lock` suffix, an empty `refs/` name, …).
///
/// `HEAD` and other root refs such as `FETCH_HEAD` are accepted.
///
/// # Errors
///
/// Returns [`RefStoreError::InvalidRefName`] naming the rejected ref.
pub fn validate_storable_refname(name: &str) -> Result<(), RefStoreError> {
    validate_name(name)
}

/// The checks every backend makes before taking locks: each update name and both sides of
/// every reflog and case-only rename must be safe to store, and an update other than a
/// reflog-only one may not store the null object id.
///
/// [`check_transaction`] runs this first; call it on its own when your store must reject a
/// malformed batch before acquiring its lock.
///
/// # Errors
///
/// Returns [`RefStoreError::InvalidRefName`] for the first name Git would refuse to store,
/// [`RefStoreError::NullOid`] for an update pointing a ref at the null id, or
/// [`RefStoreError::InvalidReflog`] for forged reflog metadata.
pub fn validate_transaction(txn: &RefTransaction) -> Result<(), RefStoreError> {
    txn.validate()
}

/// Run every check `prepare` must make for `txn` against the current `state`.
///
/// `state.refs` must contain every stored ref the transaction names, the targets of any
/// symbolic refs among them, and every stored ref that is an ancestor or descendant (in the
/// `a` / `a/b` directory sense) of a ref the transaction creates. Loading the whole store is
/// always correct. `state.reflogs` may be empty; reflogs are not consulted by the checks.
///
/// # Errors
///
/// - [`RefStoreError::DuplicateUpdate`] when two updates name, or dereference to, the same
///   stored ref.
/// - [`RefStoreError::InvalidRefName`] for a name Git refuses to store, and
///   [`RefStoreError::NullOid`] for an update storing the null id.
/// - [`RefStoreError::NameUnavailable`] for a directory/file conflict with a stored ref or
///   another ref in the batch.
/// - [`RefStoreError::ExpectedMismatch`] when an [`Expected`](super::Expected) check fails.
/// - [`RefStoreError::SymrefLoop`] when dereferencing exceeds the symbolic-ref depth limit.
pub fn check_transaction(state: &RefBatchState, txn: &RefTransaction) -> Result<(), RefStoreError> {
    txn.validate()?;
    verify_create_conflicts(&state.refs, txn.updates())?;
    simulate_batch_apply(
        state,
        txn.updates(),
        txn.reflog_renames(),
        txn.case_only_renames(),
    )
}

/// Check that each direct value in `updates` names an object, and that a branch or `HEAD`
/// names a commit.
///
/// `kind_of` reports the stored kind of an object, or `None` when it is absent. Deletes,
/// symbolic values, reflog-only updates, the null id (rejected as
/// [`RefStoreError::NullOid`] by [`validate_transaction`]) and updates flagged
/// [`RefUpdateFlags::skip_oid_verification`](super::RefUpdateFlags::skip_oid_verification)
/// are not looked up. The branch rule applies to the name the update gives, before any
/// symbolic dereference.
///
/// # Errors
///
/// [`RefStoreError::MissingObject`], [`RefStoreError::NotACommit`], or
/// [`RefStoreError::ObjectLookup`] wrapping a `kind_of` failure, for the first offending
/// update.
pub(crate) fn verify_direct_targets(
    updates: &[RefUpdate],
    mut kind_of: impl FnMut(&ObjectId) -> crate::error::Result<Option<ObjectKind>>,
) -> Result<(), RefStoreError> {
    for update in updates {
        let Some(RawRef::Direct(oid)) = &update.new_value else {
            continue;
        };
        if update.flags.log_only || update.flags.skip_oid_verification || oid.is_zero() {
            continue;
        }
        let kind = kind_of(oid).map_err(|err| RefStoreError::ObjectLookup {
            name: update.name.clone(),
            oid: *oid,
            source: BackendError::new(err),
        })?;
        match kind {
            None => {
                return Err(RefStoreError::MissingObject {
                    name: update.name.clone(),
                    oid: *oid,
                })
            }
            Some(kind) if kind != ObjectKind::Commit && names_branch(&update.name) => {
                return Err(RefStoreError::NotACommit {
                    name: update.name.clone(),
                    oid: *oid,
                    kind,
                })
            }
            Some(_) => {}
        }
    }
    Ok(())
}

/// Whether Git requires `name` to point at a commit.
fn names_branch(name: &str) -> bool {
    name == "HEAD" || name.starts_with("refs/heads/")
}

/// Directory/file, compare-and-swap and duplicate-write checks for `updates` alone (names
/// already validated, no renames).
pub(crate) fn check_transaction_updates(
    state: &RefBatchState,
    updates: &[RefUpdate],
) -> Result<(), RefStoreError> {
    verify_create_conflicts(&state.refs, updates)?;
    simulate_batch_apply(state, updates, &[], &[])
}

/// Apply `txn` to `state`: ref values, symbolic-ref dereferencing, appended reflog lines,
/// case-only renames and reflog renames.
///
/// Updates apply in transaction order. A direct-value update through a symbolic ref (without
/// [`RefUpdateFlags::no_deref`](super::RefUpdateFlags::no_deref)) writes the end of the
/// symbolic chain and logs the same entry on the symbolic ref and on that target. A delete
/// with a [`ReflogUpdate`](super::ReflogUpdate) appends an entry whose new id is zero and
/// keeps the reflog. Call [`check_transaction`] first; this function does not re-check
/// expectations, so on error `state` may be partially updated (apply to a copy).
///
/// # Errors
///
/// Returns [`RefStoreError::SymrefLoop`] for a too-deep symbolic chain, or
/// [`RefStoreError::ExpectedMismatch`] / [`RefStoreError::Corrupt`] when a case-only rename
/// finds its source missing or its destination taken.
pub fn apply_transaction(
    state: &mut RefBatchState,
    txn: &RefTransaction,
) -> Result<(), RefStoreError> {
    for update in txn.updates() {
        apply_update(state, update)?;
    }
    for rename in txn.case_only_renames() {
        apply_case_only_ref_rename(state, rename)?;
    }
    for rename in txn.reflog_renames() {
        apply_reflog_rename(state, rename)?;
    }
    Ok(())
}

/// Resolve `name` to an object id through symbolic refs stored in `refs`.
///
/// # Errors
///
/// Returns [`RefStoreError::NotFound`] naming the missing ref (the requested name or the
/// dangling target), or [`RefStoreError::SymrefLoop`] after
/// [`SYMREF_MAXDEPTH`] hops.
pub fn resolve_symbolic(
    refs: &BTreeMap<String, RawRef>,
    name: &str,
) -> Result<ObjectId, RefStoreError> {
    let mut current = name;
    for _ in 0..SYMREF_MAXDEPTH {
        match refs.get(current) {
            None => return Err(RefStoreError::not_found(current)),
            Some(RawRef::Direct(oid)) => return Ok(*oid),
            Some(RawRef::Symbolic(target)) => current = target,
        }
    }
    Err(RefStoreError::SymrefLoop)
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::refs::store::{Expected, RefUpdateFlags, ReflogUpdate};
    use crate::refs::RefnameUnavailable;

    fn oid(byte: u8) -> ObjectId {
        let mut bytes = [0u8; 20];
        bytes[19] = byte;
        ObjectId::from_bytes(&bytes).expect("valid oid")
    }

    fn put(name: &str, value: RawRef, expected: Expected) -> RefUpdate {
        RefUpdate {
            name: name.to_owned(),
            new_value: Some(value),
            expected,
            reflog: None,
            flags: RefUpdateFlags::default(),
        }
    }

    fn state(refs: &[(&str, RawRef)]) -> RefBatchState {
        RefBatchState {
            refs: refs
                .iter()
                .map(|(name, value)| ((*name).to_owned(), value.clone()))
                .collect(),
            reflogs: BTreeMap::new(),
        }
    }

    #[test]
    fn check_rejects_bad_names_before_anything_else() {
        let txn = RefTransaction::new()
            .update(put(
                "refs/heads/a..b",
                RawRef::Direct(oid(1)),
                Expected::Missing,
            ))
            .expect("txn");
        let err = check_transaction(&RefBatchState::default(), &txn).expect_err("bad name");
        assert!(
            matches!(&err, RefStoreError::InvalidRefName { name } if name == "refs/heads/a..b")
        );
        assert!(validate_storable_refname("HEAD").is_ok());
        assert!(validate_storable_refname("refs/heads/ok").is_ok());
    }

    #[test]
    fn check_reports_df_conflicts_both_ways() {
        let txn = RefTransaction::new()
            .update(put(
                "refs/heads/a",
                RawRef::Direct(oid(2)),
                Expected::Missing,
            ))
            .expect("txn");
        let stored = state(&[("refs/heads/a/b", RawRef::Direct(oid(1)))]);
        let err = check_transaction(&stored, &txn).expect_err("descendant blocks");
        assert!(matches!(
            err,
            RefStoreError::NameUnavailable {
                reason: RefnameUnavailable::DescendantExists { .. }
            }
        ));

        let txn = RefTransaction::new()
            .update(put(
                "refs/heads/a/b/c",
                RawRef::Direct(oid(2)),
                Expected::Missing,
            ))
            .expect("txn");
        let err = check_transaction(&stored, &txn).expect_err("ancestor blocks");
        assert!(matches!(
            err,
            RefStoreError::NameUnavailable {
                reason: RefnameUnavailable::AncestorExists { .. }
            }
        ));
    }

    #[test]
    fn check_compares_through_symrefs() {
        let stored = state(&[
            ("refs/heads/main", RawRef::Direct(oid(1))),
            ("HEAD", RawRef::Symbolic("refs/heads/main".to_owned())),
        ]);
        let good = RefTransaction::new()
            .update(put("HEAD", RawRef::Direct(oid(2)), Expected::Oid(oid(1))))
            .expect("txn");
        check_transaction(&stored, &good).expect("peeled old value matches");
        let stale = RefTransaction::new()
            .update(put("HEAD", RawRef::Direct(oid(2)), Expected::Oid(oid(9))))
            .expect("txn");
        assert!(matches!(
            check_transaction(&stored, &stale),
            Err(RefStoreError::ExpectedMismatch { .. })
        ));
    }

    #[test]
    fn apply_logs_symref_and_target() {
        let mut stored = state(&[
            ("refs/heads/main", RawRef::Direct(oid(1))),
            ("HEAD", RawRef::Symbolic("refs/heads/main".to_owned())),
        ]);
        let mut update = put("HEAD", RawRef::Direct(oid(2)), Expected::Oid(oid(1)));
        update.reflog = Some(ReflogUpdate {
            identity: "T <t@example.com>".to_owned(),
            message: "commit: two".to_owned(),
            time: time::OffsetDateTime::UNIX_EPOCH,
            old_oid: None,
            new_oid: None,
        });
        let txn = RefTransaction::new().update(update).expect("txn");
        check_transaction(&stored, &txn).expect("check");
        apply_transaction(&mut stored, &txn).expect("apply");

        assert_eq!(
            stored.refs.get("HEAD"),
            Some(&RawRef::Symbolic("refs/heads/main".to_owned()))
        );
        assert_eq!(
            resolve_symbolic(&stored.refs, "HEAD").expect("resolve"),
            oid(2)
        );
        for name in ["HEAD", "refs/heads/main"] {
            let log = stored.reflogs.get(name).expect("reflog");
            assert_eq!(log.len(), 1, "{name}");
            assert_eq!((log[0].old_oid, log[0].new_oid), (oid(1), oid(2)), "{name}");
            assert_eq!(log[0].identity, "T <t@example.com> 0 +0000", "{name}");
        }
    }

    #[test]
    fn verify_direct_targets_checks_presence_and_branch_kind() {
        let kinds = |oid: &ObjectId| {
            Ok(match oid.as_bytes()[19] {
                1 => Some(ObjectKind::Commit),
                2 => Some(ObjectKind::Tree),
                3 => Some(ObjectKind::Tag),
                _ => None,
            })
        };
        let at = |name: &str, byte: u8| put(name, RawRef::Direct(oid(byte)), Expected::Any);

        for name in ["HEAD", "refs/heads/a", "refs/tags/a", "refs/remotes/o/a"] {
            assert_eq!(
                verify_direct_targets(&[at(name, 1)], kinds),
                Ok(()),
                "{name}"
            );
            assert_eq!(
                verify_direct_targets(&[at(name, 9)], kinds),
                Err(RefStoreError::MissingObject {
                    name: name.to_owned(),
                    oid: oid(9)
                }),
                "{name}"
            );
        }
        for name in ["HEAD", "refs/heads/a"] {
            assert_eq!(
                verify_direct_targets(&[at(name, 2)], kinds),
                Err(RefStoreError::NotACommit {
                    name: name.to_owned(),
                    oid: oid(2),
                    kind: ObjectKind::Tree
                })
            );
        }
        for name in [
            "refs/tags/a",
            "refs/remotes/o/a",
            "refs/notes/commits",
            "ORIG_HEAD",
        ] {
            assert_eq!(
                verify_direct_targets(&[at(name, 2)], kinds),
                Ok(()),
                "{name}"
            );
            assert_eq!(
                verify_direct_targets(&[at(name, 3)], kinds),
                Ok(()),
                "{name}"
            );
        }
    }

    #[test]
    fn verify_direct_targets_skips_values_it_cannot_or_must_not_check() {
        let mut probes = 0;
        let mut log_only = put("refs/heads/a", RawRef::Direct(oid(9)), Expected::Any);
        log_only.flags.log_only = true;
        let mut skipped = put("refs/heads/b", RawRef::Direct(oid(9)), Expected::Any);
        skipped.flags.skip_oid_verification = true;
        let delete = RefUpdate {
            new_value: None,
            ..put("refs/heads/c", RawRef::Direct(oid(9)), Expected::Any)
        };
        let updates = [
            log_only,
            skipped,
            delete,
            put(
                "HEAD",
                RawRef::Symbolic("refs/heads/x".to_owned()),
                Expected::Any,
            ),
            put(
                "refs/heads/z",
                RawRef::Direct(ObjectId::zero()),
                Expected::Any,
            ),
        ];
        let result = verify_direct_targets(&updates, |_| {
            probes += 1;
            Ok(None)
        });
        assert_eq!(result, Ok(()));
        assert_eq!(probes, 0);
    }

    #[test]
    fn verify_direct_targets_reports_lookup_failures_and_stops_at_the_first_bad_update() {
        let updates = [
            put("refs/heads/a", RawRef::Direct(oid(1)), Expected::Any),
            put("refs/heads/b", RawRef::Direct(oid(2)), Expected::Any),
            put("refs/heads/c", RawRef::Direct(oid(3)), Expected::Any),
        ];
        let mut seen = Vec::new();
        let err = verify_direct_targets(&updates, |id| {
            seen.push(*id);
            match id.as_bytes()[19] {
                1 => Ok(Some(ObjectKind::Commit)),
                _ => Err(crate::error::Error::CorruptObject("bad header".to_owned())),
            }
        })
        .expect_err("lookup failure");
        let RefStoreError::ObjectLookup {
            name,
            oid: id,
            source,
        } = err
        else {
            panic!("expected ObjectLookup, got {err:?}");
        };
        assert_eq!((name.as_str(), id), ("refs/heads/b", oid(2)));
        assert!(matches!(
            source.downcast_ref::<crate::error::Error>(),
            Some(crate::error::Error::CorruptObject(_))
        ));
        assert_eq!(seen, vec![oid(1), oid(2)]);
    }

    #[test]
    fn resolve_symbolic_reports_missing_target_and_loops() {
        let refs = state(&[
            ("HEAD", RawRef::Symbolic("refs/heads/unborn".to_owned())),
            ("refs/heads/x", RawRef::Symbolic("refs/heads/y".to_owned())),
            ("refs/heads/y", RawRef::Symbolic("refs/heads/x".to_owned())),
        ])
        .refs;
        assert!(matches!(
            resolve_symbolic(&refs, "HEAD"),
            Err(RefStoreError::NotFound { name }) if name == "refs/heads/unborn"
        ));
        assert!(matches!(
            resolve_symbolic(&refs, "refs/heads/x"),
            Err(RefStoreError::SymrefLoop)
        ));
    }
}