crates/gunnar-policy/src/ancestry.rs
//! Is the pushed tip a descendant of the tip it replaces?
//!
//! This is the load-bearing half of branch protection, and the half that is
//! easiest to fake. `old != new` is not a force-push test; neither is comparing
//! hex strings, nor "is `old` in the set of newly-pushed commits", nor checking
//! that `new` is *reachable from a ref*. The only honest answer is a walk of the
//! commit graph, and a walk that cannot finish must say so rather than shrug.
//!
//! # Merges are the reason this is not a three-line function
//!
//! On a linear history, "walk parents until you find it" is trivially right and
//! a first-parent-only walk is indistinguishable from a full one. On a merge it
//! is not: the old tip is very often reachable only through a merge's **second**
//! parent, so a first-parent walk reports a legitimate fast-forward as a
//! force-push. The fixtures behind this module are therefore built with real
//! merges, and one of them puts the old tip exclusively on a second-parent path.
//!
//! # Cost, and where it goes
//!
//! This is O(commits between the two tips) today. The `git` package's `__gunnar_graph__`
//! module exists to make it O(1) in the common case: a generation number is an
//! integer comparison, and `generation(old) > generation(new)` disproves descent
//! without reading a single object. [`is_descendant_of`] is shaped to take that
//! shortcut later: it is a pure function of an oid pair and a store, so the
//! accelerated version substitutes for it without touching a gate.
//!
//! # Where the hash kind comes from, now that the store does not say
//!
//! It used to be `ObjectStore::hash_kind()`. [`GitServe`] has no such method —
//! `locked_on_target.md`'s frozen `GitServe` signature leaves *"whether `hash_kind()` belongs on
//! `GitOps`"* open, because it needs a `HashKind` type in a crate that depends
//! on `anyhow` and nothing else. Nothing here has to wait for that answer:
//! `gix_hash::oid::kind()` reads the kind off the length of the id being
//! walked, so the parser is handed the hash of the very oids it is about to
//! parse rather than of whatever the store was opened as. That is strictly
//! more local, and it removes a caller from the open question rather than
//! adding one.
use std::collections::{HashSet, VecDeque};
use gix_hash::ObjectId;
use gunnar_store::git_storage_trait::{GitServe, ObjType};
use gunnar_store::object;
use crate::error::{Error, Result};
/// How many commits a single ancestry check will visit before refusing to guess.
///
/// Large enough that no honest push reaches it, small enough that a crafted one
/// cannot make a gate run for minutes. Configurable per protection rule.
pub const DEFAULT_ANCESTRY_BUDGET: usize = 200_000;
/// Does `tip` have `ancestor` somewhere in its history?
///
/// `true` when they are the same commit. A reference that does not move has not
/// been force-pushed.
///
/// # Errors
///
/// * [`Error::MissingObject`] if a commit on the way is not in the store. This is
/// *inconclusive*, not `false`, and it must never be treated as an allow.
/// * [`Error::AncestryBudget`] if the walk exceeded `budget`. Also inconclusive.
pub fn is_descendant_of(
objects: &dyn GitServe,
tip: &gix_hash::oid,
ancestor: &gix_hash::oid,
budget: usize,
) -> Result<bool> {
if tip == ancestor {
return Ok(true);
}
let hash_kind = tip.kind();
let mut seen: HashSet<ObjectId> = HashSet::new();
let mut queue: VecDeque<ObjectId> = VecDeque::new();
let mut walked = 0usize;
seen.insert(tip.to_owned());
queue.push_back(tip.to_owned());
while let Some(current) = queue.pop_front() {
walked += 1;
if walked > budget {
return Err(Error::AncestryBudget {
from: tip.to_owned(),
looking_for: ancestor.to_owned(),
walked,
budget,
});
}
let Some((kind, bytes)) = objects.read(current.as_bytes()).map_err(Error::backend)? else {
return Err(Error::MissingObject {
oid: current,
what: "ancestry",
});
};
if kind != ObjType::Commit {
// A branch tip may be an annotated tag; anything else is not a
// history at all. Peeling tags belongs to the caller, so refuse
// rather than invent an answer.
//
// `GitServe::read` resolves the delta chain, so `kind` is the
// RESOLVED type and can never be `OfsDelta`/`RefDelta` here. That
// is the whole reason this walk needs `GitServe` and not
// `GitOps::get`, whose `Stored::obj_type` is *"the entry's type in
// the pack"*.
return Err(Error::decode(
current,
format_args!("expected a commit, found a {}", kind.as_str()),
));
}
// A header scan: `commit_links` stops at the first line that is not a
// parent, so it never decodes the message or either signature, which
// matters because a signed commit's header is large.
//
// It is also **stricter** than the `gix_object::CommitRefIter`
// `parent_ids()` this replaced. That one dropped decode errors on the
// floor and returned however many parents it had managed before the
// fault, so a truncated commit could silently answer "no more parents"
// — and in a *gate*, a short parent list is the answer that lets a
// force-push through. This fails closed.
let mut parents: Vec<ObjectId> = Vec::new();
object::commit_links(&bytes, hash_kind, &mut parents)
.map_err(|err| Error::decode(current, err))?;
for parent in parents {
if parent == ancestor {
return Ok(true);
}
if seen.insert(parent) {
queue.push_back(parent);
}
}
}
Ok(false)
}
/// How many tag objects a peel will follow before refusing to guess.
///
/// A tag of a tag of a tag is legal git and nobody writes four of them. The
/// budget exists because the chain is attacker-supplied and a cycle in it —
/// which a pack can carry, since nothing about tag objects forbids one — would
/// otherwise be an unbounded loop inside a gate.
pub const MAX_TAG_DEPTH: usize = 16;
/// Follow `tip` through any chain of annotated tag objects to the commit under
/// it, returning the commit and the tags that were walked through, outermost
/// first.
///
/// **This is the hole GUN-003 named.** A ref may point at an annotated tag
/// object — including `refs/heads/*`, because nothing in git or in gunnar says
/// a branch must name a commit — and every history question then has to start
/// one hop further in. [`introduced_commits`] used to `continue` here instead,
/// which ended its walk with an *empty* commit list, which
/// `verify_update_signatures` read as "nothing to check" and answered `Allow`.
/// `git tag -a v1 <unsigned-commit> && git push origin refs/tags/v1` — two
/// stock git commands — walked straight past what `policy.proto` calls *the
/// differentiator*.
///
/// `Ok((None, tags))` when the chain ends at something that is not a commit: a
/// tag of a tree or of a blob. There is no history under it, and there is
/// nothing to sign; saying so is not the same as saying the push is fine, and
/// the caller decides which.
pub fn peel_to_commit(
objects: &dyn GitServe,
tip: &gix_hash::oid,
) -> Result<(Option<ObjectId>, Vec<ObjectId>)> {
let hash_kind = tip.kind();
let mut tags: Vec<ObjectId> = Vec::new();
let mut current = tip.to_owned();
loop {
let Some((kind, bytes)) = objects.read(current.as_bytes()).map_err(Error::backend)? else {
return Err(Error::MissingObject {
oid: current,
what: "peeling the pushed tip",
});
};
match kind {
ObjType::Commit => return Ok((Some(current), tags)),
ObjType::Tag => {
let target = object::tag_target(&bytes, hash_kind)
.map_err(|err| Error::decode(current, err))?;
tags.push(current);
// Depth AND repetition, because they are two different
// attacks: a long chain, and a short one that closes on
// itself. Either way the answer is "I could not tell", which
// this crate spells as an error and every gate turns into a
// refusal.
if tags.len() > MAX_TAG_DEPTH || tags.contains(&target) {
return Err(Error::AncestryBudget {
from: tip.to_owned(),
looking_for: target,
walked: tags.len(),
budget: MAX_TAG_DEPTH,
});
}
current = target;
}
_ => return Ok((None, tags)),
}
}
}
/// The commits this push introduced beneath `tip`, in walk order.
///
/// The walk starts at `tip` and stops the moment it reaches a commit that is
/// **not** in `introduced`. That commit and everything behind it was already in
/// the repository, so it is not this push's business. Cost is therefore
/// O(commits in the push), not O(repository), which is what makes an
/// "every new commit must be signed" policy affordable on a large repository.
///
/// `introduced` is the pack's own new-object set (see
/// [`PushContext::new_objects`](crate::PushContext::new_objects)). Passing an
/// empty set correctly yields nothing: a push that introduced no objects
/// introduced no commits.
pub fn introduced_commits(
objects: &dyn GitServe,
tip: &gix_hash::oid,
introduced: &HashSet<ObjectId>,
budget: usize,
) -> Result<Vec<ObjectId>> {
let hash_kind = tip.kind();
let mut out = Vec::new();
let mut seen: HashSet<ObjectId> = HashSet::new();
let mut queue: VecDeque<ObjectId> = VecDeque::new();
// **Peel BEFORE the membership test, not after.** The test asks "is the
// thing this ref now points at new in this pack", and for a tagged push
// the thing with a history under it is the commit, not the tag. Peeling
// afterwards would move the hole one hop rather than close it: a tag that
// was already in the repository, re-pointed at by this push, would still
// walk nothing. See [`peel_to_commit`] and GUN-003.
let (peeled, _tags) = peel_to_commit(objects, tip)?;
let Some(tip) = peeled else {
// A tag of a tree or of a blob. No commits under it, and that is the
// honest answer rather than a refusal: the signature question about
// the tag object itself is the caller's, and
// `gates::verify_update_signatures` asks it.
return Ok(out);
};
if !introduced.contains(&tip) {
return Ok(out);
}
seen.insert(tip);
queue.push_back(tip);
while let Some(current) = queue.pop_front() {
if out.len() > budget {
return Err(Error::AncestryBudget {
from: tip.to_owned(),
looking_for: current,
walked: out.len(),
budget,
});
}
let Some((kind, bytes)) = objects.read(current.as_bytes()).map_err(Error::backend)? else {
return Err(Error::MissingObject {
oid: current,
what: "the set of new commits",
});
};
if kind != ObjType::Commit {
// Unreachable from the tip, which `peel_to_commit` resolved above,
// and unreachable from a parent edge, which only a commit has. It
// stays as a refusal rather than a `continue`: a `continue` here is
// what turned an unwalkable tip into an empty commit list and an
// empty commit list into `Verdict::Allow` (GUN-003).
return Err(Error::decode(
current,
format_args!("expected a commit, found a {}", kind.as_str()),
));
}
out.push(current);
let mut parents: Vec<ObjectId> = Vec::new();
object::commit_links(&bytes, hash_kind, &mut parents)
.map_err(|err| Error::decode(current, err))?;
for parent in parents {
if introduced.contains(&parent) && seen.insert(parent) {
queue.push_back(parent);
}
}
}
Ok(out)
}
/// The commits `new` adds over `old`: `old..new`, in walk order.
///
/// The walk starts at `new` and does not go through `old`, so on a
/// fast-forward — the only shape gunnar merges — the result is exactly the set
/// of commits the ref move makes reachable that were not reachable before.
///
/// **This exists because a merge has no pack.** Every other policy question is
/// asked about a push, where "what did this introduce" is the pack's own new
/// object set. `PullRequests.Merge` moves a ref over objects that arrived in an
/// earlier push, so that set is empty, and handing an empty set to
/// `verify_update_signatures` would make `require_signature` pass by having
/// nothing to look at — the same vacuous-allow shape GUN-003 was. The honest
/// answer for a merge is the range, and this is it.
///
/// An empty result means the two are the same commit. `Err` is inconclusive —
/// budget, or an object that is not there — and, as everywhere in this module,
/// must never be read as an allow.
pub fn commits_between(
objects: &dyn GitServe,
new: &gix_hash::oid,
old: &gix_hash::oid,
budget: usize,
) -> Result<Vec<ObjectId>> {
let hash_kind = new.kind();
let mut out = Vec::new();
if new == old {
return Ok(out);
}
let mut seen: HashSet<ObjectId> = HashSet::new();
let mut queue: VecDeque<ObjectId> = VecDeque::new();
seen.insert(old.to_owned());
seen.insert(new.to_owned());
queue.push_back(new.to_owned());
while let Some(current) = queue.pop_front() {
if out.len() > budget {
return Err(Error::AncestryBudget {
from: new.to_owned(),
looking_for: old.to_owned(),
walked: out.len(),
budget,
});
}
let Some((kind, bytes)) = objects.read(current.as_bytes()).map_err(Error::backend)? else {
return Err(Error::MissingObject {
oid: current,
what: "the commits a merge adds",
});
};
if kind != ObjType::Commit {
return Err(Error::decode(
current,
format_args!("expected a commit, found a {}", kind.as_str()),
));
}
out.push(current);
let mut parents: Vec<ObjectId> = Vec::new();
object::commit_links(&bytes, hash_kind, &mut parents)
.map_err(|err| Error::decode(current, err))?;
for parent in parents {
// `seen` was seeded with `old`, so the walk stops there rather
// than running back to the root of the repository.
if seen.insert(parent) {
queue.push_back(parent);
}
}
}
Ok(out)
}
/// Every commit reachable from `tip`, up to `budget`.
///
/// Used by tests and by callers that want the closure rather than a yes/no. Kept
/// here so it cannot drift from [`is_descendant_of`]'s idea of what a parent edge
/// is (one implementation).
pub fn reachable_from(
objects: &dyn GitServe,
tip: &gix_hash::oid,
budget: usize,
) -> Result<HashSet<ObjectId>> {
let hash_kind = tip.kind();
let mut seen: HashSet<ObjectId> = HashSet::new();
let mut queue: VecDeque<ObjectId> = VecDeque::new();
seen.insert(tip.to_owned());
queue.push_back(tip.to_owned());
while let Some(current) = queue.pop_front() {
if seen.len() > budget {
return Err(Error::AncestryBudget {
from: tip.to_owned(),
looking_for: current,
walked: seen.len(),
budget,
});
}
let Some((kind, bytes)) = objects.read(current.as_bytes()).map_err(Error::backend)? else {
return Err(Error::MissingObject {
oid: current,
what: "reachability",
});
};
if kind != ObjType::Commit {
return Err(Error::decode(
current,
format_args!("expected a commit, found a {}", kind.as_str()),
));
}
let mut parents: Vec<ObjectId> = Vec::new();
object::commit_links(&bytes, hash_kind, &mut parents)
.map_err(|err| Error::decode(current, err))?;
for parent in parents {
if seen.insert(parent) {
queue.push_back(parent);
}
}
}
Ok(seen)
}