pub mod bisect;
pub mod graph;
pub mod revlist;
mod setup;
use sley_config::GitConfig;
use sley_core::{GitError, MissingObjectContext, ObjectFormat, ObjectId, Result};
pub use setup::{
MatchedRef, NoWalkMode, PseudoRefResolver, RevisionOptions, RevisionOrder,
RevisionSetupContext, RevisionSymmetricRange, RevisionTip, SetupRevisions,
ambiguous_argument_error, ambiguous_argument_message, setup_revisions, setup_revisions_os,
};
pub use sley_core::BString;
use sley_formats::CommitGraph;
use sley_index::Index;
use sley_object::{Commit, EncodedObject, ObjectType, Tag, TreeEntries};
use sley_odb::{FileObjectDatabase, ObjectPrefixResolution, ObjectReader, repository_objects_dir};
use sley_refs::{
FileRefStore, PackedRef, RefTarget, ReflogEntry, validate_ref_name_for_read,
validate_symref_target,
};
use std::collections::{HashMap, HashSet, VecDeque};
use std::fs;
use std::ops::Range;
use std::path::{Path, PathBuf};
use std::sync::{Arc, Mutex, OnceLock};
fn read_revision_object<R: ObjectReader>(reader: &R, oid: &ObjectId) -> Result<Arc<EncodedObject>> {
reader
.read_object(oid)
.map_err(|err| with_missing_object_context(err, *oid, MissingObjectContext::RevisionWalk))
}
fn with_missing_object_context(
err: GitError,
oid: ObjectId,
context: MissingObjectContext,
) -> GitError {
let kind = err
.not_found_kind()
.and_then(sley_core::NotFoundKind::missing_object_kind);
match kind {
Some(kind) => GitError::object_kind_not_found_in(oid, kind, context),
None => err,
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct RevisionSpec {
pub raw: String,
}
impl RevisionSpec {
pub fn parse(raw: impl Into<String>) -> Result<Self> {
let raw = raw.into();
if raw.is_empty() {
return Err(GitError::InvalidFormat("empty revision spec".into()));
}
Ok(Self { raw })
}
pub fn borrowed(&self) -> Result<RevisionSpecRef<'_>> {
RevisionSpecRef::parse(&self.raw)
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct RevisionSpecRef<'a> {
raw: &'a str,
kind: RevisionSpecKind<'a>,
}
impl<'a> RevisionSpecRef<'a> {
pub fn parse(raw: &'a str) -> Result<Self> {
if raw.is_empty() {
return Err(GitError::InvalidFormat("empty revision spec".into()));
}
let kind = if let Some(text) = raw.strip_prefix(":/") {
RevisionSpecKind::MessageSearch { text }
} else if let Some(rest) = raw.strip_prefix(':') {
let (stage, path) = parse_index_stage_path(rest);
RevisionSpecKind::IndexPath { stage, path }
} else if let Some((rev, path)) = split_top_level_rev_path(raw) {
RevisionSpecKind::TreePath { rev, path }
} else {
RevisionSpecKind::Revision { rev: raw }
};
Ok(Self { raw, kind })
}
pub fn raw(&self) -> &'a str {
self.raw
}
pub fn kind(&self) -> RevisionSpecKind<'a> {
self.kind
}
pub fn tree_path(&self) -> Option<(&'a str, &'a str)> {
match self.kind {
RevisionSpecKind::TreePath { rev, path } => Some((rev, path)),
_ => None,
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum RevisionSpecKind<'a> {
MessageSearch { text: &'a str },
IndexPath { stage: u8, path: &'a str },
TreePath { rev: &'a str, path: &'a str },
Revision { rev: &'a str },
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CommitRecord {
pub oid: ObjectId,
pub parents: Vec<ObjectId>,
pub commit: Commit,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ObjectDisambiguation {
Any,
Commit,
Commitish,
Tree,
Treeish,
Tag,
Blob,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ShortObjectIdResolution {
Missing,
Unique(ObjectId),
Ambiguous(Vec<ObjectId>),
}
impl ShortObjectIdResolution {
pub fn into_result(self, prefix: &str) -> Result<ObjectId> {
match self {
Self::Unique(oid) => Ok(oid),
Self::Missing => Err(GitError::not_found(format!("revision {prefix}"))),
Self::Ambiguous(_) => Err(short_object_id_ambiguous_error(prefix)),
}
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CommitMetadata {
pub oid: ObjectId,
pub parents: Vec<ObjectId>,
pub commit_time: i64,
}
pub fn commit_graph_tree_oid(
git_dir: &Path,
format: sley_core::ObjectFormat,
oid: &ObjectId,
) -> Result<Option<ObjectId>> {
let mut graph = CommitGraphContext::load(git_dir, format);
match graph.direct_graph() {
DirectCommitGraph::Raw(graph) => graph.tree_oid(oid).or(Ok(None)),
DirectCommitGraph::Missing | DirectCommitGraph::Invalid(_) => Ok(None),
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct BisectTerms {
pub bad: String,
pub good: String,
}
impl Default for BisectTerms {
fn default() -> Self {
Self {
bad: "bad".to_string(),
good: "good".to_string(),
}
}
}
impl BisectTerms {
pub fn is_bad_ref(&self, ref_name: &str) -> bool {
bisect_ref_matches_term(ref_name, &self.bad)
}
pub fn is_good_ref(&self, ref_name: &str) -> bool {
bisect_ref_matches_term(ref_name, &self.good)
}
}
pub fn read_bisect_terms(git_dir: impl AsRef<Path>) -> Result<BisectTerms> {
let path = git_dir.as_ref().join("BISECT_TERMS");
let contents = match fs::read_to_string(&path) {
Ok(contents) => contents,
Err(err) if err.kind() == std::io::ErrorKind::NotFound => {
return Ok(BisectTerms::default());
}
Err(err) => return Err(GitError::Io(err.to_string())),
};
let mut lines = contents.lines();
let bad = match lines.next() {
Some(line) => line.to_string(),
None => String::new(),
};
let good = match lines.next() {
Some(line) => line.to_string(),
None => String::new(),
};
Ok(BisectTerms { bad, good })
}
fn bisect_ref_matches_term(ref_name: &str, term: &str) -> bool {
ref_name
.strip_prefix("refs/bisect/")
.is_some_and(|name| name.starts_with(term))
}
pub fn resolve_revision(
git_dir: impl AsRef<Path>,
format: ObjectFormat,
rev: &str,
) -> Result<ObjectId> {
let git_dir = git_dir.as_ref();
let db = FileObjectDatabase::from_git_dir(git_dir, format);
resolve_revision_with_reader(git_dir, format, &db, rev)
}
pub fn resolve_revision_with_reader<R: ObjectReader>(
git_dir: &Path,
format: ObjectFormat,
reader: &R,
rev: &str,
) -> Result<ObjectId> {
resolve_revision_inner(
git_dir,
format,
reader,
rev,
None,
ObjectDisambiguation::Any,
)
}
pub fn resolve_revision_with_config<R: ObjectReader>(
git_dir: &Path,
format: ObjectFormat,
reader: &R,
rev: &str,
config: &GitConfig,
) -> Result<ObjectId> {
resolve_revision_inner(
git_dir,
format,
reader,
rev,
Some(config),
ObjectDisambiguation::Any,
)
}
pub fn resolve_revision_with_disambiguation(
git_dir: impl AsRef<Path>,
format: ObjectFormat,
rev: &str,
disambiguation: ObjectDisambiguation,
) -> Result<ObjectId> {
let git_dir = git_dir.as_ref();
let db = FileObjectDatabase::from_git_dir(git_dir, format);
resolve_revision_inner(git_dir, format, &db, rev, None, disambiguation)
}
pub fn resolve_revision_commitish_with_reader<R: ObjectReader>(
git_dir: &Path,
format: ObjectFormat,
reader: &R,
rev: &str,
) -> Result<ObjectId> {
resolve_revision_inner(
git_dir,
format,
reader,
rev,
None,
ObjectDisambiguation::Commitish,
)
}
pub fn resolve_revision_commitish_with_config<R: ObjectReader>(
git_dir: &Path,
format: ObjectFormat,
reader: &R,
rev: &str,
config: &GitConfig,
) -> Result<ObjectId> {
resolve_revision_inner(
git_dir,
format,
reader,
rev,
Some(config),
ObjectDisambiguation::Commitish,
)
}
pub fn resolve_revision_commitish(
git_dir: impl AsRef<Path>,
format: ObjectFormat,
rev: &str,
) -> Result<ObjectId> {
let git_dir = git_dir.as_ref();
let db = FileObjectDatabase::from_git_dir(git_dir, format);
resolve_revision_commitish_with_reader(git_dir, format, &db, rev)
}
pub fn resolve_revision_symbolic_full_name(
git_dir: &Path,
format: ObjectFormat,
rev: &str,
) -> Result<Option<String>> {
resolve_revision_symbolic_full_name_inner(git_dir, format, rev, None)
}
pub fn resolve_revision_symbolic_full_name_with_config(
git_dir: &Path,
format: ObjectFormat,
rev: &str,
config: &GitConfig,
) -> Result<Option<String>> {
resolve_revision_symbolic_full_name_inner(git_dir, format, rev, Some(config))
}
fn resolve_revision_symbolic_full_name_inner(
git_dir: &Path,
format: ObjectFormat,
rev: &str,
config: Option<&GitConfig>,
) -> Result<Option<String>> {
if rev.len() == format.hex_len() && rev.bytes().all(|byte| byte.is_ascii_hexdigit()) {
return Ok(None);
}
if let Some(name) = resolve_at_selector_ref_name(git_dir, format, rev, config)? {
return Ok(Some(name));
}
let refs = FileRefStore::new(git_dir.to_path_buf(), format);
if rev == "HEAD" {
return refs.current_branch_ref();
}
if rev.starts_with("refs/") {
return Ok(refs.read_ref(rev)?.map(|_| rev.to_string()));
}
for candidate in [
format!("refs/{rev}"),
format!("refs/tags/{rev}"),
format!("refs/heads/{rev}"),
format!("refs/remotes/{rev}"),
format!("refs/remotes/{rev}/HEAD"),
] {
if refs.read_ref(&candidate)?.is_some() {
return Ok(Some(candidate));
}
}
Err(GitError::not_found(format!("revision {rev}")))
}
fn resolve_revision_inner<R: ObjectReader>(
git_dir: &Path,
format: ObjectFormat,
reader: &R,
rev: &str,
config: Option<&GitConfig>,
disambiguation: ObjectDisambiguation,
) -> Result<ObjectId> {
let parsed = RevisionSpecRef::parse(rev)?;
match parsed.kind() {
RevisionSpecKind::MessageSearch { text } => {
return search_commit_message_all(git_dir, format, reader, text);
}
RevisionSpecKind::IndexPath { stage, path } => {
return resolve_index_path(git_dir, format, reader, stage, path);
}
RevisionSpecKind::TreePath {
rev: rev_part,
path,
} => {
return resolve_rev_path(git_dir, format, reader, rev_part, path);
}
RevisionSpecKind::Revision { rev: _ } => {}
}
if let Some(oid) = resolve_at_selector(git_dir, format, rev, config)? {
return Ok(oid);
}
if let Some((base, suffix)) = split_revision_suffix(rev)? {
if base.is_empty() {
return Err(GitError::InvalidFormat(format!(
"revision {rev} has empty base"
)));
}
let base_disambiguation =
disambiguation_for_suffix(suffix).unwrap_or(ObjectDisambiguation::Any);
let base_oid =
resolve_revision_inner(git_dir, format, reader, base, config, base_disambiguation)?;
return apply_revision_suffix(git_dir, reader, format, &base_oid, suffix, rev);
}
resolve_revision_name(git_dir, format, rev, disambiguation)
}
fn disambiguation_for_suffix(suffix: RevisionSuffix<'_>) -> Option<ObjectDisambiguation> {
match suffix {
RevisionSuffix::Parent(_) | RevisionSuffix::FirstParent(_) | RevisionSuffix::Search(_) => {
Some(ObjectDisambiguation::Commitish)
}
RevisionSuffix::Peel(PeelKind::Object) => Some(ObjectDisambiguation::Any),
RevisionSuffix::Peel(PeelKind::AnyNonTag) => Some(ObjectDisambiguation::Any),
RevisionSuffix::Peel(PeelKind::Commit) => Some(ObjectDisambiguation::Commitish),
RevisionSuffix::Peel(PeelKind::Tree) => Some(ObjectDisambiguation::Treeish),
RevisionSuffix::Peel(PeelKind::Tag) => Some(ObjectDisambiguation::Tag),
RevisionSuffix::Peel(PeelKind::Blob) => Some(ObjectDisambiguation::Blob),
}
}
pub struct RevisionResolver<'a, R> {
git_dir: &'a Path,
format: ObjectFormat,
reader: &'a R,
config: Option<&'a GitConfig>,
}
impl<'a, R: ObjectReader> RevisionResolver<'a, R> {
pub fn new(git_dir: &'a Path, format: ObjectFormat, reader: &'a R) -> Self {
Self {
git_dir,
format,
reader,
config: None,
}
}
pub fn with_config(mut self, config: &'a GitConfig) -> Self {
self.config = Some(config);
self
}
pub fn resolve(&self, rev: &str) -> Result<ObjectId> {
resolve_revision_inner(
self.git_dir,
self.format,
self.reader,
rev,
self.config,
ObjectDisambiguation::Any,
)
}
pub fn peel_to_blob(&self, rev: &str) -> Result<ObjectId> {
let oid = self.resolve(rev)?;
peel_tags(self.reader, self.format, &oid)
}
pub fn peel_to_tree(&self, rev: &str) -> Result<ObjectId> {
let oid = self.resolve(rev)?;
peel_to_tree(self.reader, self.format, &oid)
}
pub fn peel_to_commit(&self, rev: &str) -> Result<ObjectId> {
let oid = self.resolve(rev)?;
peel_to_commit(self.reader, self.format, &oid)
}
pub fn resolve_path(&self, rev: &str, path: &str) -> Result<ResolvedTreePath> {
resolve_rev_path_entry(self.git_dir, self.format, self.reader, rev, path)
}
pub fn resolve_path_follow_symlinks(&self, rev: &str, path: &str) -> SymlinkedTreePath {
resolve_rev_path_follow_symlinks(self.git_dir, self.format, self.reader, rev, path)
}
}
fn resolve_revision_name(
git_dir: &Path,
format: sley_core::ObjectFormat,
rev: &str,
disambiguation: ObjectDisambiguation,
) -> Result<ObjectId> {
if rev.len() == format.hex_len() && rev.bytes().all(|byte| byte.is_ascii_hexdigit()) {
return ObjectId::from_hex(format, rev);
}
let refs = FileRefStore::new(git_dir.to_path_buf(), format);
if let Some(oid) = resolve_revision_ref(&refs, rev)? {
return Ok(oid);
}
if rev.len() >= 4
&& rev.len() < format.hex_len()
&& rev.bytes().all(|byte| byte.is_ascii_hexdigit())
{
return resolve_short_object_id(git_dir, format, rev, disambiguation)?.into_result(rev);
}
if let Some(oid) = resolve_describe_name(git_dir, format, rev)? {
return Ok(oid);
}
Err(GitError::not_found(format!("revision {rev}")))
}
pub fn short_object_id_ambiguous_error(prefix: &str) -> GitError {
GitError::InvalidObjectId(format!("short object ID {prefix} is ambiguous"))
}
pub fn is_short_object_id_ambiguous_error(err: &GitError) -> bool {
matches!(err, GitError::InvalidObjectId(msg) if msg.starts_with("short object ID ") && msg.ends_with(" is ambiguous"))
}
pub fn resolve_short_object_id(
git_dir: &Path,
format: ObjectFormat,
prefix: &str,
disambiguation: ObjectDisambiguation,
) -> Result<ShortObjectIdResolution> {
let db = FileObjectDatabase::from_git_dir(git_dir, format);
resolve_short_object_id_with_reader(git_dir, format, &db, prefix, disambiguation)
}
pub fn object_ids_with_prefix(
git_dir: &Path,
format: ObjectFormat,
prefix: &str,
) -> Result<Vec<ObjectId>> {
FileObjectDatabase::from_git_dir(git_dir, format).object_ids_with_prefix(prefix)
}
pub fn resolve_short_object_id_with_reader<R: ObjectReader>(
git_dir: &Path,
format: ObjectFormat,
reader: &R,
prefix: &str,
disambiguation: ObjectDisambiguation,
) -> Result<ShortObjectIdResolution> {
let db = FileObjectDatabase::from_git_dir(git_dir, format);
let candidates = db.object_ids_with_prefix(prefix)?;
if candidates.is_empty() {
return Ok(ShortObjectIdResolution::Missing);
}
if disambiguation == ObjectDisambiguation::Any {
return Ok(match candidates.len() {
1 => ShortObjectIdResolution::Unique(candidates[0]),
_ => ShortObjectIdResolution::Ambiguous(candidates),
});
}
let mut accepted = Vec::new();
for oid in &candidates {
if short_object_id_matches_type(reader, format, oid, disambiguation) {
accepted.push(*oid);
}
}
Ok(match accepted.len() {
1 => ShortObjectIdResolution::Unique(accepted[0]),
0 => ShortObjectIdResolution::Ambiguous(candidates),
_ => ShortObjectIdResolution::Ambiguous(accepted),
})
}
fn short_object_id_matches_type<R: ObjectReader>(
reader: &R,
format: ObjectFormat,
oid: &ObjectId,
disambiguation: ObjectDisambiguation,
) -> bool {
match disambiguation {
ObjectDisambiguation::Any => true,
ObjectDisambiguation::Commit => reader
.read_object(oid)
.is_ok_and(|object| object.object_type == ObjectType::Commit),
ObjectDisambiguation::Commitish => peel_to_commit(reader, format, oid).is_ok(),
ObjectDisambiguation::Tree => reader
.read_object(oid)
.is_ok_and(|object| object.object_type == ObjectType::Tree),
ObjectDisambiguation::Treeish => peel_to_tree(reader, format, oid).is_ok(),
ObjectDisambiguation::Tag => reader
.read_object(oid)
.is_ok_and(|object| object.object_type == ObjectType::Tag),
ObjectDisambiguation::Blob => peel_to_blob(reader, format, oid).is_ok(),
}
}
pub fn ambiguous_short_object_id_hint(
git_dir: &Path,
format: ObjectFormat,
prefix: &str,
disambiguation: ObjectDisambiguation,
) -> Result<Vec<String>> {
let db = FileObjectDatabase::from_git_dir(git_dir, format);
let mut candidates = db.object_ids_with_prefix(prefix)?;
candidates.sort_by(|left, right| {
let left_type = ambiguous_candidate_type_for_sort(&db, left);
let right_type = ambiguous_candidate_type_for_sort(&db, right);
ambiguous_type_sort_key(left_type)
.cmp(&ambiguous_type_sort_key(right_type))
.then_with(|| left.to_hex().cmp(&right.to_hex()))
});
let mut out = Vec::new();
for oid in candidates {
if disambiguation != ObjectDisambiguation::Any
&& !short_object_id_matches_type(&db, format, &oid, disambiguation)
{
continue;
}
out.push(ambiguous_short_object_id_line(&db, format, &oid)?);
}
if out.is_empty() && disambiguation != ObjectDisambiguation::Any {
for oid in db.object_ids_with_prefix(prefix)? {
out.push(ambiguous_short_object_id_line(&db, format, &oid)?);
}
}
Ok(out)
}
fn ambiguous_candidate_type_for_sort(
db: &FileObjectDatabase,
oid: &ObjectId,
) -> Option<ObjectType> {
match db.read_object_header(oid) {
Ok(Some((object_type, _))) => Some(object_type),
Err(GitError::InvalidObject(message)) if message.starts_with("unable to unpack ") => {
eprintln!("error: {message}");
None
}
Ok(None) | Err(_) => None,
}
}
fn ambiguous_type_sort_key(object_type: Option<ObjectType>) -> u8 {
match object_type {
None => 0,
Some(ObjectType::Tag) => 1,
Some(ObjectType::Commit) => 2,
Some(ObjectType::Tree) => 3,
Some(ObjectType::Blob) => 4,
}
}
fn ambiguous_short_object_id_line(
db: &FileObjectDatabase,
format: ObjectFormat,
oid: &ObjectId,
) -> Result<String> {
let abbrev = unique_object_abbrev(db, oid)?;
let object_type = match db.read_object_header(oid) {
Ok(Some((object_type, _))) => object_type,
Err(GitError::InvalidObject(message)) if message.starts_with("unknown object type") => {
return Err(GitError::InvalidObject(message));
}
Err(GitError::InvalidObject(message)) if message.starts_with("unable to unpack ") => {
eprintln!("error: {message}");
return Ok(format!("{abbrev} [bad object]"));
}
Ok(None) | Err(_) => return Ok(format!("{abbrev} [bad object]")),
};
if matches!(object_type, ObjectType::Tree | ObjectType::Blob) {
return Ok(format!("{abbrev} {}", object_type.as_str()));
}
let object = match db.read_object(oid) {
Ok(object) => object,
Err(GitError::InvalidObject(message)) if message.starts_with("unknown object type") => {
return Err(GitError::InvalidObject(message));
}
Err(GitError::InvalidObject(message)) if message.starts_with("unable to unpack ") => {
eprintln!("error: {message}");
return Ok(format!("{abbrev} [bad object]"));
}
Err(_) => return Ok(format!("{abbrev} [bad object]")),
};
Ok(match object_type {
ObjectType::Commit => {
let commit = Commit::parse_ref(format, &object.body)?;
let subject = first_message_line(commit.message);
match short_date_from_ident(commit.committer) {
Some(date) if !subject.is_empty() => format!("{abbrev} commit {date} - {subject}"),
Some(date) => format!("{abbrev} commit {date} - "),
None if !subject.is_empty() => format!("{abbrev} commit - {subject}"),
None => format!("{abbrev} commit - "),
}
}
ObjectType::Tag => match Tag::parse_ref(format, &object.body) {
Ok(tag) => {
let name = String::from_utf8_lossy(tag.name);
match tag.tagger.and_then(short_date_from_ident) {
Some(date) => format!("{abbrev} tag {date} - {name}"),
None => format!("{abbrev} tag - {name}"),
}
}
Err(_) => format!("{abbrev} [bad tag, could not parse it]"),
},
ObjectType::Tree => format!("{abbrev} tree"),
ObjectType::Blob => format!("{abbrev} blob"),
})
}
fn unique_object_abbrev(db: &FileObjectDatabase, oid: &ObjectId) -> Result<String> {
let hex = oid.to_hex();
let mut width = 7.min(hex.len());
while width < hex.len() {
match db.resolve_prefix(&hex[..width])? {
ObjectPrefixResolution::Ambiguous(_) => width += 1,
_ => break,
}
}
Ok(hex[..width].to_string())
}
fn first_message_line(message: &[u8]) -> String {
let line = message
.split(|byte| *byte == b'\n')
.next()
.unwrap_or_default();
String::from_utf8_lossy(line).into_owned()
}
fn short_date_from_ident(ident: &[u8]) -> Option<String> {
let signature = sley_core::Signature::from_ident_line(ident)?;
short_date_from_timestamp(signature.time.seconds)
}
fn short_date_from_timestamp(timestamp: i64) -> Option<String> {
let days = timestamp.div_euclid(86_400);
let (year, month, day) = civil_from_days_for_short_date(days)?;
Some(format!("{year:04}-{month:02}-{day:02}"))
}
fn civil_from_days_for_short_date(days: i64) -> Option<(i64, u32, u32)> {
let z = days.checked_add(719_468)?;
let era = if z >= 0 { z } else { z - 146_096 }.div_euclid(146_097);
let doe = z - era * 146_097;
let yoe = (doe - doe / 1460 + doe / 36_524 - doe / 146_096).div_euclid(365);
let y = yoe + era * 400;
let doy = doe - (365 * yoe + yoe / 4 - yoe / 100);
let mp = (5 * doy + 2).div_euclid(153);
let day = doy - (153 * mp + 2).div_euclid(5) + 1;
let month = mp + if mp < 10 { 3 } else { -9 };
let year = y + i64::from(month <= 2);
Some((year, u32::try_from(month).ok()?, u32::try_from(day).ok()?))
}
fn resolve_describe_name(
git_dir: &Path,
format: sley_core::ObjectFormat,
rev: &str,
) -> Result<Option<ObjectId>> {
let bytes = rev.as_bytes();
let mut idx = bytes.len();
while idx >= 2 {
idx -= 1;
let ch = bytes[idx];
if ch.is_ascii_hexdigit() {
continue;
}
if ch == b'g' && idx >= 1 && bytes[idx - 1] == b'-' {
let hex = &rev[idx + 1..];
if hex.len() >= 4
&& hex.len() < format.hex_len()
&& hex.bytes().all(|byte| byte.is_ascii_hexdigit())
&& let ShortObjectIdResolution::Unique(oid) =
resolve_short_object_id(git_dir, format, hex, ObjectDisambiguation::Commit)?
{
return Ok(Some(oid));
}
}
break;
}
Ok(None)
}
fn resolve_revision_ref(refs: &FileRefStore, rev: &str) -> Result<Option<ObjectId>> {
let mut candidates = Vec::new();
if rev == "HEAD" {
candidates.push("HEAD".to_string());
} else if rev.starts_with("refs/") {
candidates.push(rev.to_string());
} else {
let refs_name = format!("refs/{rev}");
if refs.read_ref(&refs_name)?.is_some() {
candidates.push(refs_name);
}
let tag_name = format!("refs/tags/{rev}");
if refs.read_ref(&tag_name)?.is_some() {
candidates.push(tag_name);
}
let head_name = format!("refs/heads/{rev}");
if refs.read_ref(&head_name)?.is_some() {
candidates.push(head_name);
}
let remote_name = format!("refs/remotes/{rev}");
if refs.read_ref(&remote_name)?.is_some() {
candidates.push(remote_name);
}
let remote_head_name = format!("refs/remotes/{rev}/HEAD");
if refs.read_ref(&remote_head_name)?.is_some() {
candidates.push(remote_head_name);
}
if validate_ref_name_for_read(rev).is_ok() {
candidates.push(rev.to_string());
}
}
for candidate in candidates {
if let Some(oid) = resolve_revision_ref_candidate(refs, &candidate)? {
return Ok(Some(oid));
}
}
Ok(None)
}
fn resolve_revision_ref_candidate(refs: &FileRefStore, name: &str) -> Result<Option<ObjectId>> {
let mut current = name.to_string();
for _ in 0..16 {
match refs.read_ref(¤t)? {
Some(RefTarget::Direct(oid)) => return Ok(Some(oid)),
Some(RefTarget::Symbolic(target)) => {
if validate_symref_target(&target).is_err() {
eprintln!("warning: ignoring dangling symref {name}");
return Ok(None);
}
current = target;
}
None => return Ok(None),
}
}
Ok(None)
}
fn resolve_at_selector(
git_dir: &Path,
format: sley_core::ObjectFormat,
rev: &str,
config: Option<&GitConfig>,
) -> Result<Option<ObjectId>> {
if rev == "@" {
let refs = FileRefStore::new(git_dir.to_path_buf(), format);
return match resolve_revision_ref(&refs, "HEAD")? {
Some(oid) => Ok(Some(oid)),
None => Err(GitError::not_found("revision @")),
};
}
let Some(open) = rev.rfind("@{") else {
return Ok(None);
};
let Some(inner) = rev.strip_suffix('}') else {
return Ok(None);
};
let inner = &inner[open + 2..];
if inner.contains('}') {
return Ok(None);
}
let base = &rev[..open];
let refs = FileRefStore::new(git_dir.to_path_buf(), format);
if let Some(rest) = inner.strip_prefix('-') {
if !base.is_empty() {
return Err(GitError::InvalidFormat(format!(
"invalid revision selector {rev}"
)));
}
let count = parse_at_count(rev, rest)?;
return Ok(Some(resolve_previous_checkout(
git_dir, format, count, rev,
)?));
}
if inner.eq_ignore_ascii_case("u") || inner.eq_ignore_ascii_case("upstream") {
let upstream = resolve_upstream_ref(git_dir, format, base, false, rev, config)?;
return match resolve_revision_ref(&refs, &upstream.refname)? {
Some(oid) => Ok(Some(oid)),
None => Err(upstream.missing_error(rev)),
};
}
if inner.eq_ignore_ascii_case("push") {
let upstream = resolve_upstream_ref(git_dir, format, base, true, rev, config)?;
return match resolve_revision_ref(&refs, &upstream.refname)? {
Some(oid) => Ok(Some(oid)),
None => Err(upstream.missing_error(rev)),
};
}
if inner.bytes().all(|byte| byte.is_ascii_digit()) {
let count = parse_at_count(rev, inner)?;
return Ok(Some(resolve_reflog_nth(
git_dir, format, base, count, rev, config,
)?));
}
Ok(Some(resolve_reflog_date(
git_dir, format, base, inner, rev, config,
)?))
}
fn resolve_at_selector_ref_name(
git_dir: &Path,
format: sley_core::ObjectFormat,
rev: &str,
config: Option<&GitConfig>,
) -> Result<Option<String>> {
let Some(open) = rev.rfind("@{") else {
return Ok(None);
};
let Some(inner) = rev.strip_suffix('}') else {
return Ok(None);
};
let inner = &inner[open + 2..];
if inner.contains('}') {
return Ok(None);
}
let base = &rev[..open];
if let Some(prior) = parse_prior_checkout_selector(rev)? {
let Some(branch) = nth_prior_checkout_branch_name(git_dir, format, prior)? else {
return Err(GitError::not_found(format!(
"not enough previous checkouts to resolve {rev}"
)));
};
return Ok(Some(format!("refs/heads/{branch}")));
}
if inner.eq_ignore_ascii_case("u") || inner.eq_ignore_ascii_case("upstream") {
return Ok(Some(
resolve_upstream_ref(git_dir, format, base, false, rev, config)?.refname,
));
}
if inner.eq_ignore_ascii_case("push") {
return Ok(Some(
resolve_upstream_ref(git_dir, format, base, true, rev, config)?.refname,
));
}
if inner.bytes().all(|byte| byte.is_ascii_digit()) || !inner.starts_with('-') {
let refs = FileRefStore::new(git_dir.to_path_buf(), format);
return Ok(Some(reflog_ref_name_for_base(
git_dir, format, &refs, base, config,
)?));
}
Ok(None)
}
fn parse_at_count(rev: &str, text: &str) -> Result<usize> {
if text.is_empty() || !text.bytes().all(|byte| byte.is_ascii_digit()) {
return Err(GitError::InvalidFormat(format!(
"invalid revision selector {rev}"
)));
}
text.parse::<usize>()
.map_err(|_| GitError::InvalidFormat(format!("invalid revision selector {rev}")))
}
fn parse_prior_checkout_selector(rev: &str) -> Result<Option<usize>> {
let Some(inner) = rev
.strip_prefix("@{-")
.and_then(|rest| rest.strip_suffix('}'))
else {
return Ok(None);
};
if !inner.bytes().all(|byte| byte.is_ascii_digit()) {
return Ok(None);
}
Ok(Some(parse_at_count(rev, inner)?))
}
fn is_reflog_count_or_date_selector(rev: &str) -> bool {
let Some(open) = rev.rfind("@{") else {
return false;
};
let Some(inner) = rev.strip_suffix('}') else {
return false;
};
let inner = &inner[open + 2..];
!(inner.eq_ignore_ascii_case("u")
|| inner.eq_ignore_ascii_case("upstream")
|| inner.eq_ignore_ascii_case("push")
|| inner.starts_with('-'))
}
fn reflog_ref_name(refs: &FileRefStore, base: &str) -> String {
if base == "HEAD" {
return "HEAD".to_string();
}
if base.starts_with("refs/") {
return base.to_string();
}
for candidate in reflog_dwim_candidates(base) {
if reflog_exists(refs, &candidate) {
return candidate;
}
}
format!("refs/heads/{base}")
}
fn reflog_ref_name_for_base(
git_dir: &Path,
format: sley_core::ObjectFormat,
refs: &FileRefStore,
base: &str,
config: Option<&GitConfig>,
) -> Result<String> {
if base.is_empty() {
return Ok(refs
.current_branch_ref()?
.unwrap_or_else(|| "HEAD".to_string()));
}
if base == "@" {
return Ok("HEAD".to_string());
}
if let Some(prior) = parse_prior_checkout_selector(base)? {
let Some(branch) = nth_prior_checkout_branch_name(git_dir, format, prior)? else {
return Err(GitError::not_found(format!(
"not enough previous checkouts to resolve {base}"
)));
};
return Ok(reflog_ref_name(refs, &branch));
}
if is_reflog_count_or_date_selector(base) {
return Err(GitError::InvalidFormat(format!(
"invalid revision selector {base}"
)));
}
if base.contains("@{")
&& let Some(name) = resolve_at_selector_ref_name(git_dir, format, base, config)?
{
return Ok(name);
}
if base.contains("@{") {
return Err(GitError::InvalidFormat(format!(
"invalid revision selector {base}"
)));
}
Ok(reflog_ref_name(refs, base))
}
fn reflog_dwim_candidates(base: &str) -> [String; 6] {
[
base.to_string(),
format!("refs/{base}"),
format!("refs/tags/{base}"),
format!("refs/heads/{base}"),
format!("refs/remotes/{base}"),
format!("refs/remotes/{base}/HEAD"),
]
}
fn reflog_exists(refs: &FileRefStore, name: &str) -> bool {
refs.reflog_exists(name).unwrap_or(false)
}
fn resolve_reflog_nth(
git_dir: &Path,
format: sley_core::ObjectFormat,
base: &str,
n: usize,
rev: &str,
config: Option<&GitConfig>,
) -> Result<ObjectId> {
let refs = FileRefStore::new(git_dir.to_path_buf(), format);
let ref_name = reflog_ref_name_for_base(git_dir, format, &refs, base, config)?;
let display_name = reflog_display_name_for_ref(base, &ref_name);
let entries = refs.read_reflog(&ref_name)?;
if entries.is_empty() {
if n == 0
&& refs.reflog_exists(&ref_name)?
&& let Some(oid) = resolve_revision_ref_candidate(&refs, &ref_name)?
{
return Ok(oid);
}
return Err(GitError::not_found(format!(
"no reflog for '{}' to resolve {rev}",
display_name
)));
}
let len = entries.len();
if n >= len {
if n == len && !object_id_is_null(&entries[0].old_oid) {
return Ok(entries[0].old_oid);
}
return Err(GitError::not_found(format!(
"log for '{}' only has {len} entries",
display_name
)));
}
Ok(entries[len - 1 - n].new_oid)
}
fn resolve_reflog_date(
git_dir: &Path,
format: sley_core::ObjectFormat,
base: &str,
date: &str,
rev: &str,
config: Option<&GitConfig>,
) -> Result<ObjectId> {
let cutoff = parse_reflog_selector_date(date)
.ok_or_else(|| GitError::Unsupported(format!("revision selector @{{{date}}}")))?;
let refs = FileRefStore::new(git_dir.to_path_buf(), format);
let ref_name = reflog_ref_name_for_base(git_dir, format, &refs, base, config)?;
let display_name = reflog_display_name_for_ref(base, &ref_name);
let entries = refs.read_reflog(&ref_name)?;
if entries.is_empty() {
return Err(GitError::not_found(format!(
"no reflog for '{}' to resolve {rev}",
display_name
)));
}
for entry in entries.iter().rev() {
if reflog_entry_timestamp(entry)? <= cutoff {
return Ok(entry.new_oid);
}
}
Ok(entries[0].new_oid)
}
fn reflog_entry_timestamp(entry: &ReflogEntry) -> Result<i64> {
entry.timestamp_seconds()
}
fn object_id_is_null(oid: &ObjectId) -> bool {
oid.as_bytes().iter().all(|byte| *byte == 0)
}
fn parse_reflog_selector_date(value: &str) -> Option<i64> {
if value == "now" {
return std::time::SystemTime::now()
.duration_since(std::time::UNIX_EPOCH)
.ok()
.and_then(|duration| i64::try_from(duration.as_secs()).ok());
}
if let Some(years) = value.strip_suffix(".year.ago") {
let years = years.parse::<i64>().ok()?;
let now = std::time::SystemTime::now()
.duration_since(std::time::UNIX_EPOCH)
.ok()?
.as_secs();
let now = i64::try_from(now).ok()?;
return Some(now.saturating_sub(years.saturating_mul(365 * 86_400)));
}
let mut parts = value.split_ascii_whitespace();
let _weekday = parts.next()?;
let month = parse_reflog_month(parts.next()?)?;
let day = parts.next()?.parse::<u32>().ok()?;
let time = parts.next()?;
let year = parts.next()?.parse::<i64>().ok()?;
let tz = parts.next()?;
if parts.next().is_some() {
return None;
}
let mut time_parts = time.split(':');
let hour = time_parts.next()?.parse::<i64>().ok()?;
let minute = time_parts.next()?.parse::<i64>().ok()?;
let second = time_parts.next()?.parse::<i64>().ok()?;
if time_parts.next().is_some() || hour > 23 || minute > 59 || second > 60 {
return None;
}
let offset = parse_reflog_timezone(tz)?;
Some(days_from_civil(year, month, day)? * 86_400 + hour * 3_600 + minute * 60 + second - offset)
}
fn parse_reflog_month(value: &str) -> Option<u32> {
match value {
"Jan" => Some(1),
"Feb" => Some(2),
"Mar" => Some(3),
"Apr" => Some(4),
"May" => Some(5),
"Jun" => Some(6),
"Jul" => Some(7),
"Aug" => Some(8),
"Sep" => Some(9),
"Oct" => Some(10),
"Nov" => Some(11),
"Dec" => Some(12),
_ => None,
}
}
fn parse_reflog_timezone(value: &str) -> Option<i64> {
let bytes = value.as_bytes();
if bytes.len() != 5 || (bytes[0] != b'+' && bytes[0] != b'-') {
return None;
}
let hours = value[1..3].parse::<i64>().ok()?;
let minutes = value[3..5].parse::<i64>().ok()?;
if hours > 23 || minutes > 59 {
return None;
}
let seconds = hours * 3_600 + minutes * 60;
if bytes[0] == b'-' {
Some(-seconds)
} else {
Some(seconds)
}
}
fn days_from_civil(year: i64, month: u32, day: u32) -> Option<i64> {
if !(1..=12).contains(&month) || day == 0 || day > days_in_month(year, month) {
return None;
}
let year = year - i64::from(month <= 2);
let era = if year >= 0 { year } else { year - 399 } / 400;
let yoe = year - era * 400;
let month = i64::from(month);
let day = i64::from(day);
let doy = (153 * (month + if month > 2 { -3 } else { 9 }) + 2) / 5 + day - 1;
let doe = yoe * 365 + yoe / 4 - yoe / 100 + doy;
Some(era * 146_097 + doe - 719_468)
}
fn days_in_month(year: i64, month: u32) -> u32 {
match month {
1 | 3 | 5 | 7 | 8 | 10 | 12 => 31,
4 | 6 | 9 | 11 => 30,
2 if is_leap_year(year) => 29,
2 => 28,
_ => 0,
}
}
fn is_leap_year(year: i64) -> bool {
(year % 4 == 0 && year % 100 != 0) || year % 400 == 0
}
fn reflog_display_name(base: &str) -> String {
if base.is_empty() {
"HEAD".to_string()
} else {
base.to_string()
}
}
fn reflog_display_name_for_ref(base: &str, ref_name: &str) -> String {
if base.is_empty()
&& let Some(branch) = ref_name.strip_prefix("refs/heads/")
{
return branch.to_string();
}
if base == "@" {
return "HEAD".to_string();
}
reflog_display_name(base)
}
fn resolve_previous_checkout(
git_dir: &Path,
format: sley_core::ObjectFormat,
n: usize,
rev: &str,
) -> Result<ObjectId> {
if n == 0 {
return Err(GitError::InvalidFormat(format!(
"invalid revision selector {rev}"
)));
}
let refs = FileRefStore::new(git_dir.to_path_buf(), format);
let entries = refs.read_reflog("HEAD")?;
let mut seen = 0usize;
for entry in entries.iter().rev() {
let Some(from) = checkout_move_source(&entry.message) else {
continue;
};
seen += 1;
if seen == n {
let from = from.to_string();
return resolve_revision_name(git_dir, format, &from, ObjectDisambiguation::Any)
.map_err(|_| {
GitError::not_found(format!(
"could not resolve previous branch '{from}' for {rev}"
))
});
}
}
Err(GitError::not_found(format!(
"not enough previous checkouts to resolve {rev}"
)))
}
pub fn nth_prior_checkout_branch_name(
git_dir: &Path,
format: sley_core::ObjectFormat,
n: usize,
) -> Result<Option<String>> {
if n == 0 {
return Ok(None);
}
let refs = FileRefStore::new(git_dir.to_path_buf(), format);
let entries = refs.read_reflog("HEAD")?;
let mut seen = 0usize;
for entry in entries.iter().rev() {
let Some(from) = checkout_move_source(&entry.message) else {
continue;
};
seen += 1;
if seen == n {
return Ok(Some(from.to_string()));
}
}
Ok(None)
}
fn checkout_move_source(message: &[u8]) -> Option<&str> {
let message = std::str::from_utf8(message).ok()?;
let rest = message.strip_prefix("checkout: moving from ")?;
let (from, _to) = rest.split_once(" to ")?;
Some(from)
}
struct UpstreamRef {
refname: String,
merge: String,
}
impl UpstreamRef {
fn missing_error(&self, _rev: &str) -> GitError {
GitError::not_found(format!(
"upstream branch '{}' not stored as a remote-tracking branch",
self.merge
))
}
}
fn resolve_upstream_ref(
git_dir: &Path,
format: sley_core::ObjectFormat,
base: &str,
push: bool,
rev: &str,
config: Option<&GitConfig>,
) -> Result<UpstreamRef> {
let refs = FileRefStore::new(git_dir.to_path_buf(), format);
let branch = if base.is_empty() || base == "HEAD" || base == "@" {
refs.current_branch()?
.ok_or_else(|| GitError::InvalidFormat("HEAD does not point to a branch".to_string()))?
} else if let Some(prior) = parse_prior_checkout_selector(base)? {
nth_prior_checkout_branch_name(git_dir, format, prior)?.ok_or_else(|| {
GitError::not_found(format!("not enough previous checkouts to resolve {base}"))
})?
} else if base.starts_with("refs/") || base.contains("@{") {
return Err(GitError::InvalidFormat(format!(
"{base} is not a branch, cannot resolve {rev}"
)));
} else {
base.to_string()
};
if refs.read_ref(&format!("refs/heads/{branch}"))?.is_none() {
return Err(GitError::not_found(format!("no such branch: '{branch}'")));
}
let owned_config;
let config = match config {
Some(config) => config,
None => {
owned_config = read_repo_config(git_dir)?;
&owned_config
}
};
if push {
return branch_get_push(&branch, config);
}
let merge = config
.get("branch", Some(&branch), "merge")
.ok_or_else(|| {
GitError::not_found(format!("no upstream configured for branch '{branch}'"))
})?;
let short = merge.strip_prefix("refs/heads/").unwrap_or(merge);
let remote = config
.get("branch", Some(&branch), "remote")
.ok_or_else(|| GitError::not_found(format!("no upstream remote for branch '{branch}'")))?;
let refname = if remote == "." {
merge.to_string()
} else {
format!("refs/remotes/{remote}/{short}")
};
Ok(UpstreamRef {
refname,
merge: merge.to_string(),
})
}
fn branch_get_push(branch: &str, config: &GitConfig) -> Result<UpstreamRef> {
let merge = config
.get("branch", Some(branch), "merge")
.map(str::to_string);
let pushremote = config
.get("branch", Some(branch), "pushRemote")
.or_else(|| config.get("remote", None, "pushDefault"))
.or_else(|| config.get("branch", Some(branch), "remote"))
.ok_or_else(|| GitError::not_found(format!("branch '{branch}' has no remote for pushing")))?
.to_string();
let branch_refname = format!("refs/heads/{branch}");
let upstream_ref = |refname: String| UpstreamRef {
refname,
merge: merge.clone().unwrap_or_default(),
};
let push_refspecs: Vec<&str> = config
.get_all("remote", Some(&pushremote), "push")
.into_iter()
.flatten()
.collect();
if !push_refspecs.is_empty() {
let dst = apply_refspecs(&push_refspecs, &branch_refname).ok_or_else(|| {
GitError::not_found(format!(
"push refspecs for '{pushremote}' do not include '{branch}'"
))
})?;
return Ok(upstream_ref(tracking_for_push_dest(
config,
&pushremote,
&dst,
)?));
}
match config.get("push", None, "default").unwrap_or("simple") {
"nothing" => Err(GitError::not_found(
"push has no destination (push.default is 'nothing')".to_string(),
)),
"matching" | "current" => Ok(upstream_ref(tracking_for_push_dest(
config,
&pushremote,
&branch_refname,
)?)),
"upstream" | "tracking" => Ok(upstream_ref(branch_get_upstream_refname(
config,
branch,
merge.as_deref(),
)?)),
_ => {
let up = branch_get_upstream_refname(config, branch, merge.as_deref())?;
let cur = tracking_for_push_dest(config, &pushremote, &branch_refname)?;
if cur != up {
return Err(GitError::not_found(
"cannot resolve 'simple' push to a single destination".to_string(),
));
}
Ok(upstream_ref(cur))
}
}
}
fn branch_get_upstream_refname(
config: &GitConfig,
branch: &str,
merge: Option<&str>,
) -> Result<String> {
let merge = merge.filter(|merge| !merge.is_empty()).ok_or_else(|| {
GitError::not_found(format!("no upstream configured for branch '{branch}'"))
})?;
let remote = config
.get("branch", Some(branch), "remote")
.ok_or_else(|| {
GitError::not_found(format!("no upstream configured for branch '{branch}'"))
})?;
if remote == "." {
return Ok(merge.to_string());
}
tracking_for_push_dest(config, remote, merge)
}
fn tracking_for_push_dest(config: &GitConfig, remote: &str, refname: &str) -> Result<String> {
let fetch_refspecs: Vec<&str> = config
.get_all("remote", Some(remote), "fetch")
.into_iter()
.flatten()
.collect();
if let Some(dst) = apply_refspecs(&fetch_refspecs, refname) {
return Ok(dst);
}
let short = refname.strip_prefix("refs/heads/").unwrap_or(refname);
Ok(format!("refs/remotes/{remote}/{short}"))
}
fn apply_refspecs(refspecs: &[&str], refname: &str) -> Option<String> {
for spec in refspecs {
let spec = spec.strip_prefix('+').unwrap_or(spec);
let (src, dst) = spec.split_once(':').unwrap_or((spec, spec));
if let Some(src_prefix) = src.strip_suffix('*') {
if let (Some(suffix), Some(dst_prefix)) =
(refname.strip_prefix(src_prefix), dst.strip_suffix('*'))
{
return Some(format!("{dst_prefix}{suffix}"));
}
} else if src == refname {
return Some(dst.to_string());
}
}
None
}
fn read_repo_config(git_dir: &Path) -> Result<GitConfig> {
sley_config::read_repo_config(git_dir, None)
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum RevisionSuffix<'a> {
Parent(usize),
FirstParent(usize),
Peel(PeelKind),
Search(&'a str),
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum PeelKind {
AnyNonTag,
Object,
Commit,
Tree,
Tag,
Blob,
}
fn split_revision_suffix(rev: &str) -> Result<Option<(&str, RevisionSuffix<'_>)>> {
let caret = rev.rfind('^');
let tilde = rev.rfind('~');
let Some((op, pos)) = (match (caret, tilde) {
(Some(caret), Some(tilde)) if caret > tilde => Some(('^', caret)),
(Some(caret), Some(tilde)) if tilde > caret => Some(('~', tilde)),
(Some(caret), None) => Some(('^', caret)),
(None, Some(tilde)) => Some(('~', tilde)),
(None, None) => None,
_ => None,
}) else {
return Ok(None);
};
let (base, suffix) = rev.split_at(pos);
let suffix = &suffix[1..];
match op {
'^' => {
if let Some(text) = parse_search_suffix(rev, suffix)? {
return Ok(Some((base, RevisionSuffix::Search(text))));
}
let parent = if suffix.is_empty() {
1
} else if let Some(kind) = parse_peel_suffix(rev, suffix)? {
return Ok(Some((base, RevisionSuffix::Peel(kind))));
} else if suffix.bytes().all(|byte| byte.is_ascii_digit()) {
parse_revision_count(rev, suffix)?
} else {
return Ok(None);
};
Ok(Some((base, RevisionSuffix::Parent(parent))))
}
'~' => {
let count = if suffix.is_empty() {
1
} else if suffix.bytes().all(|byte| byte.is_ascii_digit()) {
parse_revision_count(rev, suffix)?
} else {
return Ok(None);
};
Ok(Some((base, RevisionSuffix::FirstParent(count))))
}
_ => Ok(None),
}
}
fn parse_peel_suffix(rev: &str, suffix: &str) -> Result<Option<PeelKind>> {
if !suffix.starts_with('{') {
return Ok(None);
}
let Some(kind) = suffix
.strip_prefix('{')
.and_then(|value| value.strip_suffix('}'))
else {
return Err(GitError::InvalidFormat(format!(
"invalid revision peel suffix in {rev}"
)));
};
let kind = match kind {
"" => PeelKind::AnyNonTag,
"object" => PeelKind::Object,
"commit" => PeelKind::Commit,
"tree" => PeelKind::Tree,
"tag" => PeelKind::Tag,
"blob" => PeelKind::Blob,
other => {
return Err(GitError::Unsupported(format!(
"revision peel suffix ^{{{other}}}"
)));
}
};
Ok(Some(kind))
}
fn parse_search_suffix<'a>(rev: &str, suffix: &'a str) -> Result<Option<&'a str>> {
let Some(inner) = suffix.strip_prefix("{/") else {
return Ok(None);
};
let Some(text) = inner.strip_suffix('}') else {
return Err(GitError::InvalidFormat(format!(
"invalid revision search suffix in {rev}"
)));
};
Ok(Some(text))
}
fn parse_revision_count(rev: &str, text: &str) -> Result<usize> {
text.parse::<usize>()
.map_err(|_| GitError::InvalidFormat(format!("invalid revision suffix in {rev}")))
}
fn peel_base_to_commit_if_needed<R: ObjectReader>(
reader: &R,
format: sley_core::ObjectFormat,
graph: &mut CommitGraphContext<'_>,
base: &ObjectId,
) -> Result<ObjectId> {
if graph.lookup(base)?.is_some() {
return Ok(*base);
}
peel_to_commit(reader, format, base)
}
fn apply_revision_suffix<R: ObjectReader>(
git_dir: &Path,
reader: &R,
format: sley_core::ObjectFormat,
base: &ObjectId,
suffix: RevisionSuffix<'_>,
raw_rev: &str,
) -> Result<ObjectId> {
match suffix {
RevisionSuffix::Parent(parent) => {
if parent == 0 {
let _ = raw_rev;
return peel_revision(reader, format, base, PeelKind::Commit);
}
let mut graph = CommitGraphContext::load(git_dir, format);
let grafts = revlist::load_commit_grafts_from_git_dir(git_dir, format);
let base = peel_base_to_commit_if_needed(reader, format, &mut graph, base)?;
revision_suffix_commit_parents(&mut graph, reader, format, &base, &grafts)?
.get(parent - 1)
.cloned()
.ok_or_else(|| GitError::not_found(format!("parent {parent} of {base}")))
}
RevisionSuffix::FirstParent(count) => {
let mut graph = CommitGraphContext::load(git_dir, format);
let grafts = revlist::load_commit_grafts_from_git_dir(git_dir, format);
let mut current = peel_base_to_commit_if_needed(reader, format, &mut graph, base)?;
for _ in 0..count {
current =
revision_suffix_commit_parents(&mut graph, reader, format, ¤t, &grafts)?
.into_iter()
.next()
.ok_or_else(|| GitError::not_found(format!("first parent of {current}")))?;
}
Ok(current)
}
RevisionSuffix::Peel(kind) => peel_revision(reader, format, base, kind),
RevisionSuffix::Search(text) => {
search_commit_message_first_parent(git_dir, reader, format, base, text)
}
}
}
fn revision_suffix_commit_parents<R: ObjectReader>(
graph: &mut CommitGraphContext,
reader: &R,
format: sley_core::ObjectFormat,
oid: &ObjectId,
grafts: &HashMap<ObjectId, Vec<ObjectId>>,
) -> Result<Vec<ObjectId>> {
if let Some(parents) = grafts.get(oid) {
return Ok(sley_odb::grafted_parents(reader, oid, parents.clone()));
}
if grafts.is_empty() {
return graph.commit_parents(reader, oid);
}
commit_parents(reader, format, oid)
}
const GENERATION_NUMBER_ZERO: u32 = 0;
#[derive(Debug, Clone)]
enum GraphParents {
None,
One(ObjectId),
Two([ObjectId; 2]),
Many(Vec<ObjectId>),
}
impl GraphParents {
fn from_oids<I>(parents: I) -> Self
where
I: IntoIterator<Item = ObjectId>,
{
let mut parents = parents.into_iter();
let Some(first) = parents.next() else {
return Self::None;
};
let Some(second) = parents.next() else {
return Self::One(first);
};
let Some(third) = parents.next() else {
return Self::Two([first, second]);
};
let (lower, _) = parents.size_hint();
let mut many = Vec::with_capacity(3 + lower);
many.push(first);
many.push(second);
many.push(third);
many.extend(parents);
Self::Many(many)
}
fn is_empty(&self) -> bool {
matches!(self, Self::None)
}
fn first(&self) -> Option<ObjectId> {
match self {
Self::None => None,
Self::One(parent) => Some(*parent),
Self::Two(parents) => Some(parents[0]),
Self::Many(parents) => parents.first().copied(),
}
}
fn iter(&self) -> GraphParentIter<'_> {
match self {
Self::None => GraphParentIter::Empty,
Self::One(parent) => GraphParentIter::One(Some(*parent)),
Self::Two(parents) => GraphParentIter::Slice(parents.iter().copied()),
Self::Many(parents) => GraphParentIter::Slice(parents.iter().copied()),
}
}
fn to_vec(&self) -> Vec<ObjectId> {
match self {
Self::None => Vec::new(),
Self::One(parent) => vec![*parent],
Self::Two(parents) => parents.to_vec(),
Self::Many(parents) => parents.clone(),
}
}
fn grafted_vec<R: ObjectReader>(&self, reader: &R, oid: &ObjectId) -> Vec<ObjectId> {
if reader.is_shallow_graft(oid) {
Vec::new()
} else {
self.to_vec()
}
}
}
enum GraphParentIter<'a> {
Empty,
One(Option<ObjectId>),
Slice(std::iter::Copied<std::slice::Iter<'a, ObjectId>>),
}
impl Iterator for GraphParentIter<'_> {
type Item = ObjectId;
fn next(&mut self) -> Option<Self::Item> {
match self {
Self::Empty => None,
Self::One(parent) => parent.take(),
Self::Slice(parents) => parents.next(),
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
match self {
Self::Empty => (0, Some(0)),
Self::One(Some(_)) => (1, Some(1)),
Self::One(None) => (0, Some(0)),
Self::Slice(parents) => parents.size_hint(),
}
}
}
impl ExactSizeIterator for GraphParentIter<'_> {}
enum CommitParentIds<'a> {
Empty,
Borrowed(GraphParentIter<'a>),
Owned(std::vec::IntoIter<ObjectId>),
}
impl<'a> CommitParentIds<'a> {
fn borrowed(parents: &'a GraphParents) -> Self {
Self::Borrowed(parents.iter())
}
fn owned(parents: Vec<ObjectId>) -> Self {
Self::Owned(parents.into_iter())
}
}
impl Iterator for CommitParentIds<'_> {
type Item = ObjectId;
fn next(&mut self) -> Option<Self::Item> {
match self {
Self::Empty => None,
Self::Borrowed(parents) => parents.next(),
Self::Owned(parents) => parents.next(),
}
}
}
#[derive(Debug, Clone)]
struct GraphCommit {
parents: GraphParents,
generation: u32,
commit_time: u64,
}
struct GraphCommitMetadata<'a> {
parents: &'a GraphParents,
commit_time: i64,
}
#[derive(Debug, Clone)]
struct GraphBloomCommit {
parents: GraphParents,
filter: Option<Vec<u8>>,
settings: sley_formats::CommitGraphBloomSettings,
}
#[derive(Debug, Clone, Copy, Default)]
struct GraphBloomStats {
filter_not_present: usize,
maybe: usize,
definitely_not: usize,
false_positive: usize,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum GraphBloomConsult {
DefinitelyNot,
Maybe,
NotPresent,
NotInGraph,
}
struct CommitGraphContext<'a> {
git_dir: &'a Path,
format: sley_core::ObjectFormat,
direct_graph: Option<DirectCommitGraph>,
commits: Option<std::result::Result<HashMap<ObjectId, GraphCommit>, String>>,
}
enum DirectCommitGraph {
Missing,
Invalid(String),
Raw(Box<RawCommitGraph>),
}
struct RawCommitGraph {
bytes: RawCommitGraphBytes,
format: ObjectFormat,
fanout: [u32; 256],
commit_count: usize,
entry_len: usize,
oidl: Range<usize>,
cdat: Range<usize>,
edge: Option<Range<usize>>,
}
struct RawCommitGraphCountState {
seen: Vec<u64>,
pending: Vec<usize>,
}
impl RawCommitGraphCountState {
fn new(commit_count: usize) -> Self {
Self {
seen: vec![0u64; commit_count.div_ceil(64)],
pending: Vec::new(),
}
}
}
enum RawCommitGraphBytes {
Owned(Vec<u8>),
Mapped(sley_mmap::MappedFile),
}
impl AsRef<[u8]> for RawCommitGraphBytes {
fn as_ref(&self) -> &[u8] {
match self {
Self::Owned(bytes) => bytes,
Self::Mapped(bytes) => bytes.as_bytes(),
}
}
}
impl RawCommitGraph {
fn parse_for_lookup(bytes: RawCommitGraphBytes, format: ObjectFormat) -> Result<Self> {
let data = bytes.as_ref();
let hash_len = format.raw_len();
if data.len() < 8 + 12 + hash_len {
return Err(GitError::InvalidFormat(
"commit-graph file too short".into(),
));
}
if &data[..4] != b"CGPH" {
return Err(GitError::InvalidFormat(
"missing commit-graph signature".into(),
));
}
let version = data[4];
if version != 1 {
return Err(GitError::Unsupported(format!(
"commit-graph version {version}"
)));
}
let hash_id = data[5];
if u32::from(hash_id) != commit_graph_hash_function_id(format) {
return Err(GitError::InvalidFormat(format!(
"commit-graph hash id {hash_id} does not match {}",
format.name()
)));
}
if data[7] != 0 {
return Err(GitError::Unsupported(
"split commit-graph direct lookup".into(),
));
}
let chunk_count = data[6] as usize;
let lookup_len = (chunk_count + 1)
.checked_mul(12)
.ok_or_else(|| GitError::InvalidFormat("commit-graph lookup overflow".into()))?;
let data_start = 8usize
.checked_add(lookup_len)
.ok_or_else(|| GitError::InvalidFormat("commit-graph lookup overflow".into()))?;
let checksum_offset = data.len() - hash_len;
if data_start > checksum_offset {
return Err(GitError::InvalidFormat(
"truncated commit-graph chunk lookup".into(),
));
}
let mut lookup = Vec::with_capacity(chunk_count + 1);
let mut offset = 8usize;
for _ in 0..=chunk_count {
let id = [
data[offset],
data[offset + 1],
data[offset + 2],
data[offset + 3],
];
let chunk_offset = read_u64_be(&data[offset + 4..offset + 12]);
lookup.push((id, chunk_offset));
offset += 12;
}
let Some((terminator_id, terminator_offset)) = lookup.last().copied() else {
return Err(GitError::InvalidFormat(
"commit-graph chunk lookup is empty".into(),
));
};
if terminator_id != [0, 0, 0, 0] {
return Err(GitError::InvalidFormat(
"commit-graph chunk lookup missing terminator".into(),
));
}
if terminator_offset != checksum_offset as u64 {
return Err(GitError::InvalidFormat(
"commit-graph terminator does not point at checksum".into(),
));
}
let mut chunks = Vec::with_capacity(chunk_count);
let mut previous_offset = data_start;
for pair in lookup.windows(2) {
let (id, chunk_offset) = pair[0];
let (_next_id, next_offset) = pair[1];
if id == [0, 0, 0, 0] {
return Err(GitError::InvalidFormat(
"commit-graph chunk id is zero before terminator".into(),
));
}
if chunks
.iter()
.any(|(seen, _): &([u8; 4], Range<usize>)| *seen == id)
{
return Err(GitError::InvalidFormat(
"commit-graph chunk id is duplicated".into(),
));
}
let start = usize::try_from(chunk_offset).map_err(|_| {
GitError::InvalidFormat("commit-graph chunk offset overflow".into())
})?;
let end = usize::try_from(next_offset).map_err(|_| {
GitError::InvalidFormat("commit-graph chunk offset overflow".into())
})?;
if start < data_start || start < previous_offset || end < start || end > checksum_offset
{
return Err(GitError::InvalidFormat(
"commit-graph chunk length is invalid".into(),
));
}
chunks.push((id, start..end));
previous_offset = start;
}
let oidf = raw_commit_graph_chunk(&chunks, *b"OIDF")
.ok_or_else(|| GitError::InvalidFormat("commit-graph missing OIDF chunk".into()))?;
if oidf.len() != 256 * 4 {
return Err(GitError::InvalidFormat(
"commit-graph OIDF chunk has invalid length".into(),
));
}
let mut fanout = [0u32; 256];
let mut previous = 0u32;
for (idx, slot) in fanout.iter_mut().enumerate() {
let start = oidf.start + idx * 4;
*slot = read_u32_be(&data[start..start + 4]);
if *slot < previous {
return Err(GitError::InvalidFormat(
"commit-graph OIDF fanout is not monotonic".into(),
));
}
previous = *slot;
}
let commit_count = fanout[255] as usize;
let oidl = raw_commit_graph_chunk(&chunks, *b"OIDL")
.ok_or_else(|| GitError::InvalidFormat("commit-graph missing OIDL chunk".into()))?;
let expected_oidl_len = commit_count
.checked_mul(hash_len)
.ok_or_else(|| GitError::InvalidFormat("commit-graph OIDL chunk overflow".into()))?;
if oidl.len() != expected_oidl_len {
return Err(GitError::InvalidFormat(
"commit-graph OIDL chunk has invalid length".into(),
));
}
let cdat = raw_commit_graph_chunk(&chunks, *b"CDAT")
.ok_or_else(|| GitError::InvalidFormat("commit-graph missing CDAT chunk".into()))?;
let entry_len = raw_commit_graph_entry_len(format)?;
let expected_cdat_len = commit_count
.checked_mul(entry_len)
.ok_or_else(|| GitError::InvalidFormat("commit-graph CDAT chunk overflow".into()))?;
if cdat.len() != expected_cdat_len {
return Err(GitError::InvalidFormat(
"commit-graph CDAT chunk has invalid length".into(),
));
}
let edge = raw_commit_graph_chunk(&chunks, *b"EDGE");
if let Some(edge) = &edge
&& edge.len() % 4 != 0
{
return Err(GitError::InvalidFormat(
"commit-graph EDGE chunk has invalid length".into(),
));
}
raw_commit_graph_validate_generation_data(data, &chunks, commit_count)?;
Ok(Self {
bytes,
format,
fanout,
commit_count,
entry_len,
oidl,
cdat,
edge,
})
}
fn metadata(&self, oid: &ObjectId) -> Result<Option<CommitMetadata>> {
if oid.format() != self.format {
return Ok(None);
}
let Some(idx) = self.find_index(oid)? else {
return Ok(None);
};
let entry = self.cdat_entry(idx)?;
let hash_len = self.format.raw_len();
let parent_one = read_u32_be(&entry[hash_len..hash_len + 4]);
let parent_two = read_u32_be(&entry[hash_len + 4..hash_len + 8]);
let generation_and_time_high = read_u32_be(&entry[hash_len + 8..hash_len + 12]);
let time_low = read_u32_be(&entry[hash_len + 12..hash_len + 16]);
let commit_time = (u64::from(generation_and_time_high & 0x3) << 32) | u64::from(time_low);
Ok(Some(CommitMetadata {
oid: *oid,
parents: self.parent_oids(parent_one, parent_two)?,
commit_time: i64::try_from(commit_time).unwrap_or(i64::MAX),
}))
}
fn tree_oid(&self, oid: &ObjectId) -> Result<Option<ObjectId>> {
if oid.format() != self.format {
return Ok(None);
}
let Some(idx) = self.find_index(oid)? else {
return Ok(None);
};
let entry = self.cdat_entry(idx)?;
let hash_len = self.format.raw_len();
ObjectId::from_raw(self.format, &entry[..hash_len]).map(Some)
}
fn count_reachable_indices(
&self,
starts: &[usize],
first_parent: bool,
state: &mut RawCommitGraphCountState,
) -> Result<usize> {
state.pending.extend(starts.iter().copied());
let mut count = 0usize;
while let Some(idx) = state.pending.pop() {
if idx >= self.commit_count {
return Err(GitError::InvalidFormat(
"commit-graph traversal index points past table".into(),
));
}
let word = idx / 64;
let bit = 1u64 << (idx % 64);
if state.seen[word] & bit != 0 {
continue;
}
state.seen[word] |= bit;
count += 1;
self.push_parent_indices_for_entry(idx, first_parent, &mut state.pending)?;
}
Ok(count)
}
fn find_index(&self, oid: &ObjectId) -> Result<Option<usize>> {
let first = oid.as_bytes()[0] as usize;
let mut low = if first == 0 {
0
} else {
self.fanout[first - 1] as usize
};
let mut high = self.fanout[first] as usize;
let needle = oid.as_bytes();
while low < high {
let mid = low + (high - low) / 2;
match self.oid_bytes(mid)?.cmp(needle) {
std::cmp::Ordering::Less => low = mid + 1,
std::cmp::Ordering::Greater => high = mid,
std::cmp::Ordering::Equal => return Ok(Some(mid)),
}
}
Ok(None)
}
fn oid_bytes(&self, idx: usize) -> Result<&[u8]> {
if idx >= self.commit_count {
return Err(GitError::InvalidFormat(
"commit-graph oid index points past table".into(),
));
}
let hash_len = self.format.raw_len();
let start = self
.oidl
.start
.checked_add(idx.checked_mul(hash_len).ok_or_else(|| {
GitError::InvalidFormat("commit-graph OIDL index overflow".into())
})?)
.ok_or_else(|| GitError::InvalidFormat("commit-graph OIDL index overflow".into()))?;
let end = start
.checked_add(hash_len)
.ok_or_else(|| GitError::InvalidFormat("commit-graph OIDL index overflow".into()))?;
self.bytes
.as_ref()
.get(start..end)
.ok_or_else(|| GitError::InvalidFormat("commit-graph OIDL index overflow".into()))
}
fn oid_at(&self, idx: u32) -> Result<ObjectId> {
let idx = usize::try_from(idx)
.map_err(|_| GitError::InvalidFormat("commit-graph parent index overflow".into()))?;
ObjectId::from_raw(self.format, self.oid_bytes(idx)?)
}
fn cdat_entry(&self, idx: usize) -> Result<&[u8]> {
if idx >= self.commit_count {
return Err(GitError::InvalidFormat(
"commit-graph CDAT index points past table".into(),
));
}
let start = self.cdat.start + idx * self.entry_len;
let end = start + self.entry_len;
self.bytes
.as_ref()
.get(start..end)
.ok_or_else(|| GitError::InvalidFormat("commit-graph CDAT index overflow".into()))
}
fn push_parent_indices_for_entry(
&self,
idx: usize,
first_parent: bool,
out: &mut Vec<usize>,
) -> Result<()> {
let entry = self.cdat_entry(idx)?;
let hash_len = self.format.raw_len();
let parent_one = read_u32_be(&entry[hash_len..hash_len + 4]);
let parent_two = read_u32_be(&entry[hash_len + 4..hash_len + 8]);
if parent_one != RAW_COMMIT_GRAPH_PARENT_NONE {
validate_raw_commit_graph_parent(parent_one, self.commit_count)?;
out.push(parent_one as usize);
}
if first_parent || parent_two == RAW_COMMIT_GRAPH_PARENT_NONE {
return Ok(());
}
if parent_two & RAW_COMMIT_GRAPH_EXTRA_EDGE == 0 {
validate_raw_commit_graph_parent(parent_two, self.commit_count)?;
out.push(parent_two as usize);
return Ok(());
}
let Some(edge) = &self.edge else {
return Err(GitError::InvalidFormat(
"commit-graph octopus edge missing EDGE chunk".into(),
));
};
let mut edge_idx = (parent_two & RAW_COMMIT_GRAPH_EXTRA_EDGE_MASK) as usize;
loop {
let start = edge
.start
.checked_add(edge_idx.checked_mul(4).ok_or_else(|| {
GitError::InvalidFormat("commit-graph EDGE index overflow".into())
})?)
.ok_or_else(|| {
GitError::InvalidFormat("commit-graph EDGE index overflow".into())
})?;
let end = start.checked_add(4).ok_or_else(|| {
GitError::InvalidFormat("commit-graph EDGE index overflow".into())
})?;
let Some(bytes) = self.bytes.as_ref().get(start..end) else {
return Err(GitError::InvalidFormat(
"commit-graph EDGE entry points past chunk".into(),
));
};
let raw = read_u32_be(bytes);
let parent = raw & RAW_COMMIT_GRAPH_EXTRA_EDGE_MASK;
validate_raw_commit_graph_parent(parent, self.commit_count)?;
out.push(parent as usize);
if raw & RAW_COMMIT_GRAPH_EXTRA_EDGE != 0 {
return Ok(());
}
edge_idx = edge_idx.checked_add(1).ok_or_else(|| {
GitError::InvalidFormat("commit-graph EDGE index overflow".into())
})?;
}
}
fn parent_oids(&self, parent_one: u32, parent_two: u32) -> Result<Vec<ObjectId>> {
let mut parents = Vec::new();
if parent_one != RAW_COMMIT_GRAPH_PARENT_NONE {
validate_raw_commit_graph_parent(parent_one, self.commit_count)?;
parents.push(self.oid_at(parent_one)?);
}
if parent_two == RAW_COMMIT_GRAPH_PARENT_NONE {
return Ok(parents);
}
if parent_two & RAW_COMMIT_GRAPH_EXTRA_EDGE == 0 {
validate_raw_commit_graph_parent(parent_two, self.commit_count)?;
parents.push(self.oid_at(parent_two)?);
return Ok(parents);
}
let Some(edge) = &self.edge else {
return Err(GitError::InvalidFormat(
"commit-graph octopus edge missing EDGE chunk".into(),
));
};
let mut edge_idx = (parent_two & RAW_COMMIT_GRAPH_EXTRA_EDGE_MASK) as usize;
loop {
let start = edge
.start
.checked_add(edge_idx.checked_mul(4).ok_or_else(|| {
GitError::InvalidFormat("commit-graph EDGE index overflow".into())
})?)
.ok_or_else(|| {
GitError::InvalidFormat("commit-graph EDGE index overflow".into())
})?;
let end = start.checked_add(4).ok_or_else(|| {
GitError::InvalidFormat("commit-graph EDGE index overflow".into())
})?;
let Some(bytes) = self.bytes.as_ref().get(start..end) else {
return Err(GitError::InvalidFormat(
"commit-graph EDGE entry points past chunk".into(),
));
};
let raw = read_u32_be(bytes);
let parent = raw & RAW_COMMIT_GRAPH_EXTRA_EDGE_MASK;
validate_raw_commit_graph_parent(parent, self.commit_count)?;
parents.push(self.oid_at(parent)?);
if raw & RAW_COMMIT_GRAPH_EXTRA_EDGE != 0 {
return Ok(parents);
}
edge_idx = edge_idx.checked_add(1).ok_or_else(|| {
GitError::InvalidFormat("commit-graph EDGE index overflow".into())
})?;
}
}
}
impl<'a> CommitGraphContext<'a> {
fn load(git_dir: &'a Path, format: sley_core::ObjectFormat) -> Self {
Self {
git_dir,
format,
direct_graph: None,
commits: None,
}
}
fn direct_graph(&mut self) -> &DirectCommitGraph {
if self.direct_graph.is_none() {
self.direct_graph = Some(load_direct_commit_graph(self.git_dir, self.format));
}
self.direct_graph
.as_ref()
.expect("direct commit graph load state initialized")
}
fn count_reachable_direct(
&mut self,
starts: &[ObjectId],
first_parent: bool,
) -> Result<Option<usize>> {
let format = self.format;
let DirectCommitGraph::Raw(graph) = self.direct_graph() else {
return Ok(None);
};
let mut indices = Vec::with_capacity(starts.len());
for oid in starts {
if oid.format() != format {
return Ok(None);
}
let Some(idx) = graph.find_index(oid)? else {
return Ok(None);
};
indices.push(idx);
}
let mut state = RawCommitGraphCountState::new(graph.commit_count);
graph
.count_reachable_indices(&indices, first_parent, &mut state)
.map(Some)
}
fn count_reachable_graph_oid(
&mut self,
oid: &ObjectId,
first_parent: bool,
state: &mut Option<RawCommitGraphCountState>,
) -> Result<Option<usize>> {
let format = self.format;
let DirectCommitGraph::Raw(graph) = self.direct_graph() else {
return Ok(None);
};
if oid.format() != format {
return Ok(None);
}
let Some(idx) = graph.find_index(oid)? else {
return Ok(None);
};
let state = state.get_or_insert_with(|| RawCommitGraphCountState::new(graph.commit_count));
graph
.count_reachable_indices(&[idx], first_parent, state)
.map(Some)
}
fn lookup(&mut self, oid: &ObjectId) -> Result<Option<&GraphCommit>> {
if self.commits.is_none() {
self.commits = Some(
load_commit_graph_map(self.git_dir, self.format).map_err(|err| err.to_string()),
);
}
match self
.commits
.as_ref()
.expect("commit graph map load state initialized")
{
Ok(map) => Ok(map.get(oid)),
Err(message) => Err(GitError::InvalidFormat(message.clone())),
}
}
fn parents(&mut self, oid: &ObjectId) -> Result<Option<&GraphParents>> {
Ok(self.lookup(oid)?.map(|commit| &commit.parents))
}
fn first_parent(&mut self, oid: &ObjectId) -> Result<Option<Option<ObjectId>>> {
Ok(self.lookup(oid)?.map(|commit| commit.parents.first()))
}
fn generation(&mut self, oid: &ObjectId) -> Result<Option<u32>> {
Ok(match self.lookup(oid)? {
Some(commit) if commit.generation != GENERATION_NUMBER_ZERO => Some(commit.generation),
_ => None,
})
}
fn commit_time(&mut self, oid: &ObjectId) -> Result<Option<i64>> {
Ok(self
.lookup(oid)?
.map(|commit| i64::try_from(commit.commit_time).unwrap_or(i64::MAX)))
}
fn commit_parents<R: ObjectReader>(
&mut self,
reader: &R,
oid: &ObjectId,
) -> Result<Vec<ObjectId>> {
if reader.is_shallow_graft(oid) {
return Ok(Vec::new());
}
let format = self.format;
if let Some(parents) = self.parents(oid)? {
return Ok(parents.to_vec());
}
commit_parents(reader, format, oid)
}
fn commit_parent_ids<R: ObjectReader>(
&mut self,
reader: &R,
oid: &ObjectId,
) -> Result<CommitParentIds<'_>> {
if reader.is_shallow_graft(oid) {
return Ok(CommitParentIds::Empty);
}
let format = self.format;
if let Some(parents) = self.parents(oid)? {
return Ok(CommitParentIds::borrowed(parents));
}
Ok(CommitParentIds::owned(commit_parents(reader, format, oid)?))
}
fn commit_first_parent<R: ObjectReader>(
&mut self,
reader: &R,
oid: &ObjectId,
) -> Result<Option<ObjectId>> {
if reader.is_shallow_graft(oid) {
return Ok(None);
}
let format = self.format;
if let Some(parent) = self.first_parent(oid)? {
return Ok(parent);
}
Ok(commit_parents(reader, format, oid)?.into_iter().next())
}
fn metadata(&mut self, oid: &ObjectId) -> Result<Option<GraphCommitMetadata<'_>>> {
Ok(self.lookup(oid)?.map(|commit| GraphCommitMetadata {
parents: &commit.parents,
commit_time: i64::try_from(commit.commit_time).unwrap_or(i64::MAX),
}))
}
fn metadata_owned<R: ObjectReader>(
&mut self,
reader: &R,
oid: &ObjectId,
) -> Result<Option<CommitMetadata>> {
match self.direct_graph() {
DirectCommitGraph::Raw(graph) => {
let Some(mut metadata) = graph.metadata(oid).unwrap_or(None) else {
return Ok(None);
};
if reader.is_shallow_graft(oid) {
metadata.parents.clear();
}
return Ok(Some(metadata));
}
DirectCommitGraph::Invalid(_) => return Ok(None),
DirectCommitGraph::Missing => {}
}
Ok(self.metadata(oid)?.map(|metadata| CommitMetadata {
oid: *oid,
parents: metadata.parents.grafted_vec(reader, oid),
commit_time: metadata.commit_time,
}))
}
}
fn load_commit_graph_map(
git_dir: &Path,
format: sley_core::ObjectFormat,
) -> Result<HashMap<ObjectId, GraphCommit>> {
let info = repository_objects_dir(git_dir).join("info");
let single = info.join("commit-graph");
if single.exists() {
let bytes = match fs::read(&single) {
Ok(bytes) => bytes,
Err(err) => return Err(GitError::Io(err.to_string())),
};
if commit_graph_hash_version_mismatch(&bytes, format) {
return Err(GitError::InvalidFormat(
"commit-graph hash version mismatch".into(),
));
}
return match CommitGraph::parse(&bytes, format) {
Ok(graph) => graph_to_map(&graph),
Err(_) => {
warn_invalid_commit_graph_bloom_chunks(&bytes, &single, format);
if RawCommitGraph::parse_for_lookup(RawCommitGraphBytes::Owned(bytes), format)
.is_err()
{
return Ok(HashMap::new());
}
Ok(HashMap::new())
}
};
}
let chain = info.join("commit-graphs").join("commit-graph-chain");
load_commit_graph_chain(&info, &chain, format)
}
fn load_direct_commit_graph(git_dir: &Path, format: sley_core::ObjectFormat) -> DirectCommitGraph {
let path = repository_objects_dir(git_dir)
.join("info")
.join("commit-graph");
if !path.exists() {
return DirectCommitGraph::Missing;
}
let bytes = match sley_mmap::MappedFile::open_commit_graph(&path) {
Ok(mapped) => RawCommitGraphBytes::Mapped(mapped),
Err(_) => match fs::read(&path) {
Ok(bytes) => RawCommitGraphBytes::Owned(bytes),
Err(err) => return DirectCommitGraph::Invalid(err.to_string()),
},
};
if commit_graph_hash_version_mismatch(bytes.as_ref(), format) {
return DirectCommitGraph::Invalid("commit-graph hash version mismatch".into());
}
warn_invalid_commit_graph_bloom_chunks(bytes.as_ref(), &path, format);
match RawCommitGraph::parse_for_lookup(bytes, format) {
Ok(graph) => DirectCommitGraph::Raw(Box::new(graph)),
Err(GitError::InvalidFormat(message)) => DirectCommitGraph::Invalid(message),
Err(err) => DirectCommitGraph::Invalid(err.to_string()),
}
}
const RAW_COMMIT_GRAPH_PARENT_NONE: u32 = 0x7000_0000;
const RAW_COMMIT_GRAPH_EXTRA_EDGE: u32 = 0x8000_0000;
const RAW_COMMIT_GRAPH_EXTRA_EDGE_MASK: u32 = 0x7fff_ffff;
fn raw_commit_graph_chunk(chunks: &[([u8; 4], Range<usize>)], id: [u8; 4]) -> Option<Range<usize>> {
chunks
.iter()
.find_map(|(chunk_id, range)| (*chunk_id == id).then(|| range.clone()))
}
fn raw_commit_graph_validate_generation_data(
data: &[u8],
chunks: &[([u8; 4], Range<usize>)],
commit_count: usize,
) -> Result<()> {
let Some(gda2) = raw_commit_graph_chunk(chunks, *b"GDA2") else {
return Ok(());
};
let expected_gda2_len = commit_count
.checked_mul(4)
.ok_or_else(|| GitError::InvalidFormat("commit-graph generation data overflow".into()))?;
if gda2.len() != expected_gda2_len {
return Err(GitError::InvalidFormat(
"commit-graph generation data is the wrong size".into(),
));
}
let gdo2 = raw_commit_graph_chunk(chunks, *b"GDO2");
if let Some(gdo2) = &gdo2
&& gdo2.len() % 8 != 0
{
return Err(GitError::InvalidFormat(
"commit-graph overflow generation data is corrupt".into(),
));
}
for offset in (gda2.start..gda2.end).step_by(4) {
let raw = read_u32_be(&data[offset..offset + 4]);
if raw & 0x8000_0000 == 0 {
continue;
}
let Some(gdo2) = &gdo2 else {
return Err(GitError::InvalidFormat(
"commit-graph overflow generation data is missing".into(),
));
};
let overflow_idx = (raw & 0x7fff_ffff) as usize;
let overflow_start = overflow_idx.checked_mul(8).ok_or_else(|| {
GitError::InvalidFormat("commit-graph overflow generation index overflow".into())
})?;
let overflow_end = overflow_start.checked_add(8).ok_or_else(|| {
GitError::InvalidFormat("commit-graph overflow generation index overflow".into())
})?;
if overflow_end > gdo2.len() {
return Err(GitError::InvalidFormat(
"commit-graph overflow generation data is too small".into(),
));
}
}
Ok(())
}
fn raw_commit_graph_entry_len(format: ObjectFormat) -> Result<usize> {
format
.raw_len()
.checked_add(16)
.ok_or_else(|| GitError::InvalidFormat("commit-graph CDAT entry overflow".into()))
}
fn validate_raw_commit_graph_parent(parent: u32, commit_count: usize) -> Result<()> {
if parent as usize >= commit_count {
return Err(GitError::InvalidFormat(
"commit-graph parent points past commit table".into(),
));
}
Ok(())
}
fn commit_graph_hash_function_id(format: ObjectFormat) -> u32 {
match format {
ObjectFormat::Sha1 => 1,
ObjectFormat::Sha256 => 2,
}
}
fn commit_graph_hash_version_mismatch(bytes: &[u8], format: ObjectFormat) -> bool {
if bytes.len() <= 5 || &bytes[..4] != b"CGPH" {
return false;
}
let file_version = u32::from(bytes[5]);
let repo_version = commit_graph_hash_function_id(format);
if file_version == repo_version {
return false;
}
use std::sync::atomic::{AtomicBool, Ordering};
static WARNED: AtomicBool = AtomicBool::new(false);
if !WARNED.swap(true, Ordering::Relaxed) {
eprintln!(
"error: commit-graph hash version {file_version} does not match version {repo_version}"
);
}
true
}
fn read_u32_be(bytes: &[u8]) -> u32 {
u32::from_be_bytes([bytes[0], bytes[1], bytes[2], bytes[3]])
}
fn read_u64_be(bytes: &[u8]) -> u64 {
u64::from_be_bytes([
bytes[0], bytes[1], bytes[2], bytes[3], bytes[4], bytes[5], bytes[6], bytes[7],
])
}
fn load_commit_graph_chain(
info: &Path,
chain: &Path,
format: sley_core::ObjectFormat,
) -> Result<HashMap<ObjectId, GraphCommit>> {
let contents = match fs::read_to_string(chain) {
Ok(contents) => contents,
Err(err) if err.kind() == std::io::ErrorKind::NotFound => {
return Ok(HashMap::new());
}
Err(err) => return Err(GitError::Io(err.to_string())),
};
let mut merged: HashMap<ObjectId, GraphCommit> = HashMap::new();
for line in contents.lines() {
let hash = line.trim();
if hash.is_empty() {
continue;
}
let layer = info
.join("commit-graphs")
.join(format!("graph-{hash}.graph"));
let bytes = fs::read(&layer).map_err(|err| GitError::Io(err.to_string()))?;
let graph = match CommitGraph::parse(&bytes, format) {
Ok(graph) => graph,
Err(err) => {
warn_invalid_commit_graph_bloom_chunks(&bytes, &layer, format);
return Err(err);
}
};
for (oid, commit) in graph_to_map(&graph)? {
merged.insert(oid, commit);
}
}
Ok(merged)
}
fn graph_to_map(graph: &CommitGraph) -> Result<HashMap<ObjectId, GraphCommit>> {
let mut map = HashMap::with_capacity(graph.commits.len());
for entry in &graph.commits {
let parents = GraphParents::from_oids(graph.parent_oids(entry)?);
map.insert(
entry.oid,
GraphCommit {
parents,
generation: entry.generation,
commit_time: entry.commit_time,
},
);
}
Ok(map)
}
fn load_commit_graph_bloom_map(
objects_dir: &Path,
format: sley_core::ObjectFormat,
requested_version: i64,
) -> HashMap<ObjectId, GraphBloomCommit> {
let info = objects_dir.join("info");
let graph_path = info.join("commit-graph");
if !graph_path.exists() {
let chain = info.join("commit-graphs").join("commit-graph-chain");
return load_commit_graph_bloom_chain(&info, &chain, format, requested_version)
.unwrap_or_default();
}
let bytes = match fs::read(&graph_path) {
Ok(bytes) => bytes,
Err(_) => return HashMap::new(),
};
match CommitGraph::parse(&bytes, format) {
Ok(graph) => graph_to_bloom_map(&graph, requested_version, &[]).unwrap_or_default(),
Err(_) => {
warn_invalid_commit_graph_bloom_chunks(&bytes, &graph_path, format);
HashMap::new()
}
}
}
fn load_commit_graph_bloom_chain(
info: &Path,
chain: &Path,
format: sley_core::ObjectFormat,
requested_version: i64,
) -> Result<HashMap<ObjectId, GraphBloomCommit>> {
let contents = match fs::read_to_string(chain) {
Ok(contents) => contents,
Err(err) if err.kind() == std::io::ErrorKind::NotFound => {
return Ok(HashMap::new());
}
Err(err) => return Err(GitError::Io(err.to_string())),
};
let mut layers = Vec::new();
let chain_dir = info.join("commit-graphs");
for line in contents.lines() {
let hash = line.trim();
if hash.is_empty() {
continue;
}
let layer = chain_dir.join(format!("graph-{hash}.graph"));
let bytes = fs::read(&layer).map_err(|err| GitError::Io(err.to_string()))?;
let graph = match CommitGraph::parse(&bytes, format) {
Ok(graph) => graph,
Err(err) => {
warn_invalid_commit_graph_bloom_chunks(&bytes, &layer, format);
return Err(err);
}
};
layers.push((hash.to_string(), graph));
}
let canonical_settings = layers
.iter()
.rev()
.filter_map(|(_, graph)| graph.bloom_filters.as_ref())
.map(commit_graph_bloom_settings_from_filters)
.find(|settings| {
requested_version <= 0 || i64::from(settings.hash_version) == requested_version
});
let mut merged = HashMap::new();
let mut base_oids = Vec::new();
for (hash, graph) in layers {
let layer_settings = graph
.bloom_filters
.as_ref()
.map(commit_graph_bloom_settings_from_filters);
let layer_map = if let (Some(canonical), Some(settings)) =
(canonical_settings, layer_settings)
&& !commit_graph_bloom_settings_match(settings, canonical)
{
eprintln!(
"warning: disabling Bloom filters for commit-graph layer '{hash}' due to incompatible settings"
);
graph_to_bloom_map_without_filters(&graph, settings, &base_oids)?
} else {
graph_to_bloom_map(&graph, requested_version, &base_oids)?
};
for (oid, bloom) in layer_map {
merged.insert(oid, bloom);
}
base_oids.extend(graph.commits.iter().map(|entry| entry.oid));
}
Ok(merged)
}
#[derive(Clone, Copy)]
struct GraphChunkView {
id: [u8; 4],
start: usize,
end: usize,
}
fn warn_invalid_commit_graph_bloom_chunks(
bytes: &[u8],
path: &Path,
format: sley_core::ObjectFormat,
) {
let Some((chunks, checksum_offset)) = commit_graph_chunk_views(bytes, format) else {
return;
};
let Some(bdat) = commit_graph_chunk_view_data(bytes, &chunks, *b"BDAT") else {
return;
};
let Some(bidx) = commit_graph_chunk_view_data(bytes, &chunks, *b"BIDX") else {
return;
};
if bdat.len() < 12 {
emit_commit_graph_bloom_warning_once(
path,
format!(
"warning: ignoring too-small changed-path chunk ({} < 12) in commit-graph file",
bdat.len()
),
);
return;
}
let commit_count = commit_graph_view_commit_count(bytes, &chunks, checksum_offset);
if let Some(commit_count) = commit_count
&& bidx.len() / 4 != commit_count
{
emit_commit_graph_bloom_warning_once(
path,
"warning: commit-graph changed-path index chunk is too small".to_string(),
);
return;
}
let payload_len = bdat.len() - 12;
let display_path = commit_graph_warning_path(path);
let mut previous = 0usize;
for idx in 0..(bidx.len() / 4) {
let start = idx * 4;
let cumulative = u32::from_be_bytes([
bidx[start],
bidx[start + 1],
bidx[start + 2],
bidx[start + 3],
]) as usize;
if cumulative > payload_len {
emit_commit_graph_bloom_warning_once(
path,
format!(
"warning: ignoring out-of-range offset ({}) for changed-path filter at pos {} of {} (chunk size: {})",
cumulative,
idx,
display_path,
bdat.len()
),
);
return;
}
if cumulative < previous {
emit_commit_graph_bloom_warning_once(
path,
format!(
"warning: ignoring decreasing changed-path index offsets ({} > {}) for positions {} and {} of {}",
previous,
cumulative,
idx.saturating_sub(1),
idx,
display_path
),
);
return;
}
previous = cumulative;
}
}
fn emit_commit_graph_bloom_warning_once(path: &Path, message: String) {
static WARNED: OnceLock<Mutex<HashSet<PathBuf>>> = OnceLock::new();
let warned = WARNED.get_or_init(|| Mutex::new(HashSet::new()));
if let Ok(mut warned) = warned.lock()
&& !warned.insert(path.to_path_buf())
{
return;
}
eprintln!("{message}");
}
fn warn_invalid_commit_graph_bloom_for_objects_dir(
objects_dir: &Path,
format: sley_core::ObjectFormat,
) {
let info = objects_dir.join("info");
let single = info.join("commit-graph");
if single.exists() {
if let Ok(bytes) = fs::read(&single) {
warn_invalid_commit_graph_bloom_chunks(&bytes, &single, format);
}
return;
}
let chain = info.join("commit-graphs").join("commit-graph-chain");
let Ok(contents) = fs::read_to_string(&chain) else {
return;
};
for line in contents.lines() {
let hash = line.trim();
if hash.is_empty() {
continue;
}
let layer = info
.join("commit-graphs")
.join(format!("graph-{hash}.graph"));
if let Ok(bytes) = fs::read(&layer) {
warn_invalid_commit_graph_bloom_chunks(&bytes, &layer, format);
}
}
}
fn commit_graph_chunk_views(
bytes: &[u8],
format: sley_core::ObjectFormat,
) -> Option<(Vec<GraphChunkView>, usize)> {
let hash_len = format.raw_len();
if bytes.len() < 8 + 12 + hash_len || &bytes[..4] != b"CGPH" {
return None;
}
let chunk_count = bytes[6] as usize;
let lookup_len = (chunk_count + 1).checked_mul(12)?;
let data_start = 8usize.checked_add(lookup_len)?;
let checksum_offset = bytes.len().checked_sub(hash_len)?;
if data_start > checksum_offset {
return None;
}
let mut lookup = Vec::with_capacity(chunk_count + 1);
let mut offset = 8usize;
for _ in 0..=chunk_count {
let id = [
bytes[offset],
bytes[offset + 1],
bytes[offset + 2],
bytes[offset + 3],
];
let chunk_offset = u64::from_be_bytes([
bytes[offset + 4],
bytes[offset + 5],
bytes[offset + 6],
bytes[offset + 7],
bytes[offset + 8],
bytes[offset + 9],
bytes[offset + 10],
bytes[offset + 11],
]) as usize;
lookup.push((id, chunk_offset));
offset += 12;
}
let mut chunks = Vec::with_capacity(chunk_count);
for pair in lookup.windows(2) {
let (id, start) = pair[0];
let (_next, end) = pair[1];
if start > end || end > checksum_offset {
return None;
}
chunks.push(GraphChunkView { id, start, end });
}
Some((chunks, checksum_offset))
}
fn commit_graph_chunk_view_data<'a>(
bytes: &'a [u8],
chunks: &[GraphChunkView],
id: [u8; 4],
) -> Option<&'a [u8]> {
let chunk = chunks.iter().find(|chunk| chunk.id == id)?;
bytes.get(chunk.start..chunk.end)
}
fn commit_graph_view_commit_count(
bytes: &[u8],
chunks: &[GraphChunkView],
_checksum_offset: usize,
) -> Option<usize> {
let fanout = commit_graph_chunk_view_data(bytes, chunks, *b"OIDF")?;
if fanout.len() != 256 * 4 {
return None;
}
let last = fanout.len() - 4;
Some(u32::from_be_bytes([
fanout[last],
fanout[last + 1],
fanout[last + 2],
fanout[last + 3],
]) as usize)
}
fn commit_graph_warning_path(path: &Path) -> String {
let text = path.to_string_lossy();
if let Some(idx) = text.find(".git/objects/info/commit-graph") {
return text[idx..].to_string();
}
text.into_owned()
}
fn graph_to_bloom_map(
graph: &CommitGraph,
requested_version: i64,
base_oids: &[ObjectId],
) -> Result<HashMap<ObjectId, GraphBloomCommit>> {
let Some(filters) = &graph.bloom_filters else {
return graph_to_bloom_map_without_filters(
graph,
sley_formats::DEFAULT_COMMIT_GRAPH_BLOOM_SETTINGS,
base_oids,
);
};
let settings = commit_graph_bloom_settings_from_filters(filters);
if requested_version > 0 && i64::from(filters.hash_version) != requested_version {
return graph_to_bloom_map_without_filters(graph, settings, base_oids);
}
let mut map = HashMap::with_capacity(graph.commits.len());
for (idx, entry) in graph.commits.iter().enumerate() {
let parents = commit_graph_entry_parent_oids_with_base(graph, entry, base_oids)?;
let filter = filters
.filter_for_commit(idx)
.filter(|filter| !filter.is_empty())
.map(|filter| filter.to_vec());
map.insert(
entry.oid,
GraphBloomCommit {
parents,
filter,
settings,
},
);
}
Ok(map)
}
fn graph_to_bloom_map_without_filters(
graph: &CommitGraph,
settings: sley_formats::CommitGraphBloomSettings,
base_oids: &[ObjectId],
) -> Result<HashMap<ObjectId, GraphBloomCommit>> {
let mut map = HashMap::with_capacity(graph.commits.len());
for entry in &graph.commits {
let parents = commit_graph_entry_parent_oids_with_base(graph, entry, base_oids)?;
map.insert(
entry.oid,
GraphBloomCommit {
parents,
filter: None,
settings,
},
);
}
Ok(map)
}
fn commit_graph_entry_parent_oids_with_base(
graph: &CommitGraph,
entry: &sley_formats::CommitGraphEntry,
base_oids: &[ObjectId],
) -> Result<GraphParents> {
let mut parents = Vec::with_capacity(entry.parents.len());
for parent in entry.parent_indices() {
let idx = usize::try_from(parent)
.map_err(|_| GitError::InvalidFormat("commit-graph parent index overflow".into()))?;
let oid = if idx < base_oids.len() {
base_oids[idx]
} else {
let local = idx - base_oids.len();
graph
.commits
.get(local)
.map(|entry| entry.oid)
.ok_or_else(|| {
GitError::InvalidFormat("commit-graph parent points past commit table".into())
})?
};
parents.push(oid);
}
Ok(GraphParents::from_oids(parents))
}
fn commit_graph_bloom_settings_from_filters(
filters: &sley_formats::CommitGraphBloomFilters,
) -> sley_formats::CommitGraphBloomSettings {
let mut settings = sley_formats::DEFAULT_COMMIT_GRAPH_BLOOM_SETTINGS;
settings.hash_version = filters.hash_version;
settings.hash_count = filters.hash_count;
settings.bits_per_entry = filters.bits_per_entry;
settings
}
fn commit_graph_bloom_settings_match(
left: sley_formats::CommitGraphBloomSettings,
right: sley_formats::CommitGraphBloomSettings,
) -> bool {
left.hash_version == right.hash_version
&& left.hash_count == right.hash_count
&& left.bits_per_entry == right.bits_per_entry
}
fn commit_parents<R: ObjectReader>(
reader: &R,
format: sley_core::ObjectFormat,
oid: &ObjectId,
) -> Result<Vec<ObjectId>> {
let object = read_revision_object(reader, oid)?;
if object.object_type != ObjectType::Commit {
return Err(GitError::InvalidObject(format!(
"expected commit {oid}, found {}",
object.object_type.as_str()
)));
}
Ok(sley_odb::grafted_parents(
reader,
oid,
Commit::parse_ref(format, &object.body)?.parents,
))
}
fn peel_revision<R: ObjectReader>(
reader: &R,
format: sley_core::ObjectFormat,
oid: &ObjectId,
kind: PeelKind,
) -> Result<ObjectId> {
match kind {
PeelKind::AnyNonTag => peel_tags(reader, format, oid),
PeelKind::Object => {
read_revision_object(reader, oid)?;
Ok(*oid)
}
PeelKind::Commit => peel_to_commit(reader, format, oid),
PeelKind::Tree => peel_to_tree(reader, format, oid),
PeelKind::Blob => peel_to_blob(reader, format, oid),
PeelKind::Tag => {
let object = read_revision_object(reader, oid)?;
if object.object_type == ObjectType::Tag {
Ok(*oid)
} else {
Err(GitError::InvalidObject(format!(
"expected tag {oid}, found {}",
object.object_type.as_str()
)))
}
}
}
}
pub fn peel_tags<R: ObjectReader>(
reader: &R,
format: sley_core::ObjectFormat,
oid: &ObjectId,
) -> Result<ObjectId> {
let object = read_revision_object(reader, oid)?;
if object.object_type != ObjectType::Tag {
return Ok(*oid);
}
let tag = Tag::parse_ref(format, &object.body)?;
peel_tags(reader, format, &tag.object)
}
pub fn peel_to_tree<R: ObjectReader>(
reader: &R,
format: sley_core::ObjectFormat,
oid: &ObjectId,
) -> Result<ObjectId> {
let object = read_revision_object(reader, oid)?;
match object.object_type {
ObjectType::Tree => Ok(*oid),
ObjectType::Commit => Ok(Commit::parse_ref(format, &object.body)?.tree),
ObjectType::Tag => {
let tag = Tag::parse_ref(format, &object.body)?;
peel_to_tree(reader, format, &tag.object)
}
other => Err(GitError::InvalidObject(format!(
"expected tree-ish {oid}, found {}",
other.as_str()
))),
}
}
pub fn peel_to_commit<R: ObjectReader>(
reader: &R,
format: sley_core::ObjectFormat,
oid: &ObjectId,
) -> Result<ObjectId> {
let object = read_revision_object(reader, oid)?;
match object.object_type {
ObjectType::Commit => Ok(*oid),
ObjectType::Tag => {
let tag = Tag::parse_ref(format, &object.body)?;
peel_to_commit(reader, format, &tag.object)
}
other => Err(GitError::InvalidObject(format!(
"expected commit-ish {oid}, found {}",
other.as_str()
))),
}
}
pub fn peel_to_blob<R: ObjectReader>(
reader: &R,
format: sley_core::ObjectFormat,
oid: &ObjectId,
) -> Result<ObjectId> {
let object = read_revision_object(reader, oid)?;
match object.object_type {
ObjectType::Blob => Ok(*oid),
ObjectType::Tag => {
let tag = Tag::parse_ref(format, &object.body)?;
peel_to_blob(reader, format, &tag.object)
}
other => Err(GitError::InvalidObject(format!(
"expected blob {oid}, found {}",
other.as_str()
))),
}
}
pub fn pack_refs_with_auto_peel(
git_dir: impl AsRef<Path>,
format: sley_core::ObjectFormat,
prune_loose: bool,
) -> Result<Vec<PackedRef>> {
let git_dir = git_dir.as_ref();
let db = FileObjectDatabase::from_git_dir(git_dir, format);
let refs = FileRefStore::new(git_dir, format);
refs.pack_refs_with_peeler(prune_loose, |_, oid| {
let peeled = peel_tags(&db, format, oid)?;
if &peeled == oid {
Ok(None)
} else {
Ok(Some(peeled))
}
})
}
pub fn parse_commit_parents(format: sley_core::ObjectFormat, body: &[u8]) -> Result<Vec<ObjectId>> {
let text = std::str::from_utf8(body).map_err(|err| GitError::InvalidObject(err.to_string()))?;
let mut parents = Vec::new();
for line in text.lines() {
if line.is_empty() {
break;
}
if let Some(hex) = line.strip_prefix("parent ") {
parents.push(ObjectId::from_hex(format, hex)?);
}
}
Ok(parents)
}
pub use sley_pathspec::{Pathspec, PathspecMatchMagic};
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub enum RevWalkOrder {
#[default]
CommitDate,
AuthorDate,
Topo,
}
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct RevWalkDateWindow {
pub min_time: Option<i64>,
pub max_time: Option<i64>,
}
impl RevWalkDateWindow {
fn is_open(&self) -> bool {
self.min_time.is_none() && self.max_time.is_none()
}
}
pub struct RevWalk<'a, R: ObjectReader> {
graph: CommitGraphContext<'a>,
reader: &'a R,
format: ObjectFormat,
starts: Vec<ObjectId>,
order: RevWalkOrder,
first_parent: bool,
max_count: Option<usize>,
skip: usize,
window: RevWalkDateWindow,
pathspec: Pathspec,
started: bool,
seen: HashSet<ObjectId>,
heap: std::collections::BinaryHeap<RevWalkHeapEntry>,
emitted: usize,
skipped: usize,
}
struct RevWalkHeapEntry {
key: i64,
metadata: CommitMetadata,
}
impl PartialEq for RevWalkHeapEntry {
fn eq(&self, other: &Self) -> bool {
self.key == other.key && self.metadata.oid == other.metadata.oid
}
}
impl Eq for RevWalkHeapEntry {}
impl Ord for RevWalkHeapEntry {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
self.key
.cmp(&other.key)
.then_with(|| other.metadata.oid.cmp(&self.metadata.oid))
}
}
impl PartialOrd for RevWalkHeapEntry {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
impl<'a, R: ObjectReader> RevWalk<'a, R> {
pub fn new(
git_dir: &'a Path,
format: ObjectFormat,
reader: &'a R,
starts: impl IntoIterator<Item = ObjectId>,
) -> Self {
Self {
graph: CommitGraphContext::load(git_dir, format),
reader,
format,
starts: starts.into_iter().collect(),
order: RevWalkOrder::default(),
first_parent: false,
max_count: None,
skip: 0,
window: RevWalkDateWindow::default(),
pathspec: Pathspec::default(),
started: false,
seen: HashSet::new(),
heap: std::collections::BinaryHeap::new(),
emitted: 0,
skipped: 0,
}
}
pub fn order(mut self, order: RevWalkOrder) -> Self {
self.order = order;
self
}
pub fn first_parent(mut self, first_parent: bool) -> Self {
self.first_parent = first_parent;
self
}
pub fn max_count(mut self, max_count: Option<usize>) -> Self {
self.max_count = max_count;
self
}
pub fn skip(mut self, skip: usize) -> Self {
self.skip = skip;
self
}
pub fn date_window(mut self, window: RevWalkDateWindow) -> Self {
self.window = window;
self
}
pub fn pathspec(mut self, pathspec: Pathspec) -> Self {
self.pathspec = pathspec;
self
}
pub fn pathspec_ref(&self) -> &Pathspec {
&self.pathspec
}
fn order_key(&self, metadata: &CommitMetadata) -> i64 {
let _ = self.order;
metadata.commit_time
}
fn push(&mut self, metadata: CommitMetadata) {
let key = self.order_key(&metadata);
self.heap.push(RevWalkHeapEntry { key, metadata });
}
fn init(&mut self) -> Result<()> {
let starts = std::mem::take(&mut self.starts);
for start in starts {
if !self.seen.insert(start) {
continue;
}
let metadata =
commit_metadata_lookup(&mut self.graph, self.reader, self.format, &start)?;
self.push(metadata);
}
self.started = true;
Ok(())
}
fn enqueue_parents(&mut self, metadata: &CommitMetadata) -> Result<()> {
if self.first_parent {
if let Some(parent) = metadata.parents.first().copied()
&& self.seen.insert(parent)
{
let parent_metadata =
commit_metadata_lookup(&mut self.graph, self.reader, self.format, &parent)?;
self.push(parent_metadata);
}
return Ok(());
}
for parent in metadata.parents.iter().copied() {
if !self.seen.insert(parent) {
continue;
}
let parent_metadata =
commit_metadata_lookup(&mut self.graph, self.reader, self.format, &parent)?;
self.push(parent_metadata);
}
Ok(())
}
pub fn try_next(&mut self) -> Result<Option<CommitMetadata>> {
if !self.started {
self.init()?;
}
loop {
if let Some(max) = self.max_count
&& self.emitted >= max
{
return Ok(None);
}
let Some(entry) = self.heap.pop() else {
return Ok(None);
};
let metadata = entry.metadata;
let within_lower = self
.window
.min_time
.is_none_or(|min| metadata.commit_time >= min);
if within_lower {
self.enqueue_parents(&metadata)?;
}
let emit = self.window.is_open()
|| (self
.window
.min_time
.is_none_or(|min| metadata.commit_time >= min)
&& self
.window
.max_time
.is_none_or(|max| metadata.commit_time <= max));
if !emit {
continue;
}
if self.skipped < self.skip {
self.skipped += 1;
continue;
}
self.emitted += 1;
return Ok(Some(metadata));
}
}
pub fn collect_all(mut self) -> Result<Vec<CommitMetadata>> {
let mut out = Vec::new();
while let Some(metadata) = self.try_next()? {
out.push(metadata);
}
Ok(out)
}
}
pub fn walk_commit_metadata<R: ObjectReader>(
git_dir: &Path,
format: sley_core::ObjectFormat,
reader: &R,
starts: impl IntoIterator<Item = ObjectId>,
first_parent: bool,
) -> Result<Vec<CommitMetadata>> {
let mut graph = CommitGraphContext::load(git_dir, format);
let mut seen = HashSet::new();
let mut pending: VecDeque<ObjectId> = starts.into_iter().collect();
let mut out = Vec::new();
while let Some(oid) = pending.pop_front() {
if !seen.insert(oid) {
continue;
}
let metadata = commit_metadata_lookup(&mut graph, reader, format, &oid)?;
if first_parent {
pending.extend(metadata.parents.first().copied());
} else {
pending.extend(metadata.parents.iter().copied());
}
out.push(metadata);
}
Ok(out)
}
pub fn count_commit_metadata<R: ObjectReader>(
git_dir: &Path,
format: sley_core::ObjectFormat,
reader: &R,
starts: impl IntoIterator<Item = ObjectId>,
first_parent: bool,
) -> Result<usize> {
let mut graph = CommitGraphContext::load(git_dir, format);
let starts = starts.into_iter().collect::<Vec<_>>();
if !reader.has_shallow_grafts()
&& let Some(count) = graph.count_reachable_direct(&starts, first_parent)?
{
return Ok(count);
}
if !reader.has_shallow_grafts() {
let mut graph_count_state = None;
let mut seen_objects = HashSet::new();
let mut pending: VecDeque<ObjectId> = starts.into();
let mut count = 0usize;
while let Some(oid) = pending.pop_front() {
if let Some(graph_count) =
graph.count_reachable_graph_oid(&oid, first_parent, &mut graph_count_state)?
{
count += graph_count;
continue;
}
if !seen_objects.insert(oid) {
continue;
}
let parents = commit_parents(reader, format, &oid)?;
if first_parent {
pending.extend(parents.into_iter().next());
} else {
pending.extend(parents);
}
count += 1;
}
return Ok(count);
}
let mut seen = HashSet::new();
let mut pending: VecDeque<ObjectId> = starts.into();
let mut count = 0usize;
while let Some(oid) = pending.pop_front() {
if !seen.insert(oid) {
continue;
}
if first_parent {
pending.extend(graph.commit_first_parent(reader, &oid)?);
} else {
for parent in graph.commit_parent_ids(reader, &oid)? {
pending.push_back(parent);
}
}
count += 1;
}
Ok(count)
}
pub fn walk_commit_metadata_date_ordered_limited<R: ObjectReader>(
git_dir: &Path,
format: sley_core::ObjectFormat,
reader: &R,
starts: impl IntoIterator<Item = ObjectId>,
first_parent: bool,
limit: usize,
) -> Result<Vec<CommitMetadata>> {
if limit == 0 {
return Ok(Vec::new());
}
RevWalk::new(git_dir, format, reader, starts)
.order(RevWalkOrder::CommitDate)
.first_parent(first_parent)
.max_count(Some(limit))
.collect_all()
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct ReachabilityTargetMatch {
pub reached_required: bool,
pub reached_excluded: bool,
}
pub struct CommitReachability<'a, R: ObjectReader> {
graph: CommitGraphContext<'a>,
reader: &'a R,
}
impl<'a, R: ObjectReader> CommitReachability<'a, R> {
pub fn new(git_dir: &'a Path, format: ObjectFormat, reader: &'a R) -> Self {
Self {
graph: CommitGraphContext::load(git_dir, format),
reader,
}
}
pub fn reachable_oids(
&mut self,
starts: impl IntoIterator<Item = ObjectId>,
first_parent: bool,
) -> Result<HashSet<ObjectId>> {
let mut seen = HashSet::new();
let mut pending: VecDeque<ObjectId> = starts.into_iter().collect();
while let Some(oid) = pending.pop_front() {
if !seen.insert(oid) {
continue;
}
self.enqueue_parents(&oid, first_parent, &mut pending)?;
}
Ok(seen)
}
pub fn target_match(
&mut self,
start: &ObjectId,
required_targets: &HashSet<ObjectId>,
excluded_targets: &HashSet<ObjectId>,
first_parent: bool,
) -> Result<ReachabilityTargetMatch> {
let mut reached_required = required_targets.is_empty();
if reached_required && excluded_targets.is_empty() {
return Ok(ReachabilityTargetMatch {
reached_required,
reached_excluded: false,
});
}
let mut seen = HashSet::new();
let mut pending = VecDeque::from([*start]);
while let Some(oid) = pending.pop_front() {
if !seen.insert(oid) {
continue;
}
if excluded_targets.contains(&oid) {
return Ok(ReachabilityTargetMatch {
reached_required,
reached_excluded: true,
});
}
if !reached_required && required_targets.contains(&oid) {
reached_required = true;
if excluded_targets.is_empty() {
return Ok(ReachabilityTargetMatch {
reached_required,
reached_excluded: false,
});
}
}
self.enqueue_parents(&oid, first_parent, &mut pending)?;
}
Ok(ReachabilityTargetMatch {
reached_required,
reached_excluded: false,
})
}
fn enqueue_parents(
&mut self,
oid: &ObjectId,
first_parent: bool,
pending: &mut VecDeque<ObjectId>,
) -> Result<()> {
if first_parent {
pending.extend(self.graph.commit_first_parent(self.reader, oid)?);
} else {
for parent in self.graph.commit_parent_ids(self.reader, oid)? {
pending.push_back(parent);
}
}
Ok(())
}
}
pub fn reachable_commit_oids<R: ObjectReader>(
git_dir: &Path,
format: sley_core::ObjectFormat,
reader: &R,
starts: impl IntoIterator<Item = ObjectId>,
first_parent: bool,
) -> Result<HashSet<ObjectId>> {
CommitReachability::new(git_dir, format, reader).reachable_oids(starts, first_parent)
}
fn commit_metadata_lookup<R: ObjectReader>(
graph: &mut CommitGraphContext,
reader: &R,
format: sley_core::ObjectFormat,
oid: &ObjectId,
) -> Result<CommitMetadata> {
if let Some(metadata) = graph.metadata_owned(reader, oid)? {
return Ok(metadata);
}
let (parents, commit_time) = commit_metadata_from_object(reader, format, oid)?;
Ok(CommitMetadata {
oid: *oid,
parents,
commit_time,
})
}
fn commit_metadata_from_object<R: ObjectReader>(
reader: &R,
format: sley_core::ObjectFormat,
oid: &ObjectId,
) -> Result<(Vec<ObjectId>, i64)> {
let object = read_revision_object(reader, oid)?;
if object.object_type != ObjectType::Commit {
return Err(GitError::InvalidObject(format!(
"expected commit {oid}, found {}",
object.object_type.as_str()
)));
}
let commit = Commit::parse_ref(format, &object.body)?;
let commit_time = commit
.committer_signature()
.map(|signature| signature.time.seconds)
.unwrap_or(0);
Ok((
sley_odb::grafted_parents(reader, oid, commit.parents),
commit_time,
))
}
pub fn walk_commits<R: ObjectReader>(
reader: &R,
format: sley_core::ObjectFormat,
starts: impl IntoIterator<Item = ObjectId>,
) -> Result<Vec<CommitRecord>> {
let mut seen = HashSet::new();
let mut pending: VecDeque<ObjectId> = starts.into_iter().collect();
let mut out = Vec::new();
while let Some(oid) = pending.pop_front() {
if !seen.insert(oid) {
continue;
}
let object = read_revision_object(reader, &oid)?;
if object.object_type != ObjectType::Commit {
return Err(GitError::InvalidObject(format!(
"expected commit {oid}, found {}",
object.object_type.as_str()
)));
}
let commit = Commit::parse(format, &object.body)?;
let parents = sley_odb::grafted_parents(reader, &oid, commit.parents.clone());
pending.extend(parents.iter().cloned());
out.push(CommitRecord {
oid,
parents,
commit,
});
}
Ok(out)
}
#[derive(Debug, Clone, Copy, Default)]
pub struct SimplifyOptions {
pub full_history: bool,
pub first_parent: bool,
pub simplify_merges: bool,
pub show_pulls: bool,
pub ancestry_path: bool,
pub want_ancestry: bool,
}
#[derive(Debug, Clone, Default)]
struct CommitSimplify {
treesame: bool,
simplified_parents: Option<Vec<ObjectId>>,
treesame_parents: Vec<bool>,
}
fn commit_tree_oid(record: &CommitRecord) -> ObjectId {
record.commit.tree
}
fn tree_same_for_pathspec(
db: &FileObjectDatabase,
format: ObjectFormat,
parent_tree: &ObjectId,
commit_tree: &ObjectId,
pathspec: &Pathspec,
) -> Result<bool> {
if parent_tree == commit_tree {
return Ok(true);
}
let options = sley_diff_merge::DiffNameStatusOptions {
detect_renames: false,
detect_copies: false,
find_copies_harder: false,
rename_empty: false,
};
let changes = sley_diff_merge::diff_name_status_trees_with_options(
db,
format,
parent_tree,
commit_tree,
options,
)?;
for entry in &changes {
if pathspec.is_empty() || pathspec.matches(entry.path.as_bytes()) {
return Ok(false);
}
}
Ok(true)
}
fn tree_same_as_empty_for_pathspec(
db: &FileObjectDatabase,
format: ObjectFormat,
commit_tree: &ObjectId,
pathspec: &Pathspec,
) -> Result<bool> {
let options = sley_diff_merge::DiffNameStatusOptions {
detect_renames: false,
detect_copies: false,
find_copies_harder: false,
rename_empty: false,
};
let changes = sley_diff_merge::diff_name_status_empty_tree_with_options(
db,
format,
commit_tree,
options,
)?;
for entry in &changes {
if pathspec.is_empty() || pathspec.matches(entry.path.as_bytes()) {
return Ok(false);
}
}
Ok(true)
}
fn commit_graph_bloom_paths_for_pathspec(pathspec: &Pathspec) -> Option<Vec<Vec<u8>>> {
if pathspec.is_empty() {
return None;
}
let mut paths = Vec::new();
for element in pathspec.elements() {
let mut pattern = element.pattern();
if element.is_exclude() || element.is_icase() || pattern.is_empty() {
return None;
}
while pattern.ends_with(b"/") {
pattern = &pattern[..pattern.len() - 1];
}
if pattern.is_empty() || pattern == b"." {
return None;
}
let bloom_path = if let Some(wildcard) = pattern
.iter()
.position(|byte| matches!(*byte, b'*' | b'?' | b'['))
{
let slash = pattern[..wildcard].iter().rposition(|byte| *byte == b'/')?;
&pattern[..slash]
} else if pattern.contains(&b'\\') {
return None;
} else {
pattern
};
if bloom_path.is_empty() {
return None;
}
paths.push(bloom_path.to_vec());
}
(!paths.is_empty()).then_some(paths)
}
fn commit_graph_bloom_read_changed_paths_version(objects_dir: &Path) -> i64 {
let Some(git_dir) = objects_dir.parent() else {
return -1;
};
let Ok(config) = sley_config::read_repo_config(git_dir, None) else {
return -1;
};
if let Some(entry) = config.get_entry("commitGraph", None, "changedPathsVersion") {
return match entry {
Some(value) => sley_config::parse_config_int(value).unwrap_or(-1),
None => 1,
};
}
match config.get_bool("commitGraph", None, "readChangedPaths") {
Some(false) => 0,
_ => -1,
}
}
fn commit_graph_bloom_consult(
blooms: &HashMap<ObjectId, GraphBloomCommit>,
commit: &ObjectId,
parent: Option<&ObjectId>,
paths: &[Vec<u8>],
) -> GraphBloomConsult {
let Some(bloom) = blooms.get(commit) else {
return GraphBloomConsult::NotInGraph;
};
match parent {
Some(parent) => {
if bloom.parents.first() != Some(*parent) {
return GraphBloomConsult::NotPresent;
}
}
None => {
if !bloom.parents.is_empty() {
return GraphBloomConsult::NotPresent;
}
}
}
let Some(filter) = bloom.filter.as_ref() else {
return GraphBloomConsult::NotPresent;
};
let maybe_changed = paths
.iter()
.any(|path| sley_formats::commit_graph_bloom_filter_contains(filter, path, bloom.settings));
if maybe_changed {
GraphBloomConsult::Maybe
} else {
GraphBloomConsult::DefinitelyNot
}
}
fn compute_treesame(
db: &FileObjectDatabase,
format: ObjectFormat,
records: &[CommitRecord],
reachable: &HashSet<ObjectId>,
pathspec: &Pathspec,
first_parent: bool,
full_history: bool,
) -> Result<HashMap<ObjectId, CommitSimplify>> {
let tree_by_oid: HashMap<ObjectId, ObjectId> =
records.iter().map(|r| (r.oid, r.commit.tree)).collect();
let parent_tree = |oid: &ObjectId| -> Option<ObjectId> {
if let Some(tree) = tree_by_oid.get(oid) {
Some(*tree)
} else {
read_commit_tree(db, format, oid).ok()
}
};
let requested_bloom_version = commit_graph_bloom_read_changed_paths_version(db.objects_dir());
let bloom_paths =
commit_graph_bloom_paths_for_pathspec(pathspec).filter(|_| requested_bloom_version != 0);
if bloom_paths.is_some() {
warn_invalid_commit_graph_bloom_for_objects_dir(db.objects_dir(), format);
}
let bloom_map = bloom_paths
.as_ref()
.map(|_| load_commit_graph_bloom_map(db.objects_dir(), format, requested_bloom_version))
.unwrap_or_default();
let mut bloom_stats = GraphBloomStats::default();
let mut out = HashMap::with_capacity(records.len());
for record in records {
let commit_tree = commit_tree_oid(record);
let mut simplify = CommitSimplify::default();
if record.parents.is_empty() {
simplify.treesame = if let Some(paths) = bloom_paths.as_ref() {
match commit_graph_bloom_consult(&bloom_map, &record.oid, None, paths) {
GraphBloomConsult::DefinitelyNot => {
bloom_stats.definitely_not += 1;
true
}
GraphBloomConsult::Maybe => {
bloom_stats.maybe += 1;
let same =
tree_same_as_empty_for_pathspec(db, format, &commit_tree, pathspec)?;
if same {
bloom_stats.false_positive += 1;
}
same
}
GraphBloomConsult::NotPresent => {
bloom_stats.filter_not_present += 1;
tree_same_as_empty_for_pathspec(db, format, &commit_tree, pathspec)?
}
GraphBloomConsult::NotInGraph => {
tree_same_as_empty_for_pathspec(db, format, &commit_tree, pathspec)?
}
}
} else {
tree_same_as_empty_for_pathspec(db, format, &commit_tree, pathspec)?
};
out.insert(record.oid, simplify);
continue;
}
let mut relevant_parents = 0usize;
let mut relevant_change = false;
let mut irrelevant_change = false;
let mut diverted = false;
let mut treesame_parents = vec![false; record.parents.len()];
for (nth, parent) in record.parents.iter().enumerate() {
if first_parent && nth >= 1 {
break;
}
let relevant = reachable.contains(parent);
if relevant {
relevant_parents += 1;
}
let Some(pt) = parent_tree(parent) else {
if relevant {
relevant_change = true;
} else {
irrelevant_change = true;
}
continue;
};
let same = if nth == 0
&& let Some(paths) = bloom_paths.as_ref()
{
match commit_graph_bloom_consult(&bloom_map, &record.oid, Some(parent), paths) {
GraphBloomConsult::DefinitelyNot => {
bloom_stats.definitely_not += 1;
true
}
GraphBloomConsult::Maybe => {
bloom_stats.maybe += 1;
let same = tree_same_for_pathspec(db, format, &pt, &commit_tree, pathspec)?;
if same {
bloom_stats.false_positive += 1;
}
same
}
GraphBloomConsult::NotPresent => {
bloom_stats.filter_not_present += 1;
tree_same_for_pathspec(db, format, &pt, &commit_tree, pathspec)?
}
GraphBloomConsult::NotInGraph => {
tree_same_for_pathspec(db, format, &pt, &commit_tree, pathspec)?
}
}
} else {
tree_same_for_pathspec(db, format, &pt, &commit_tree, pathspec)?
};
if same {
treesame_parents[nth] = true;
if !full_history && relevant {
simplify.simplified_parents = Some(vec![*parent]);
simplify.treesame = true;
diverted = true;
break;
}
continue;
}
if relevant {
relevant_change = true;
} else {
irrelevant_change = true;
}
}
simplify.treesame_parents = treesame_parents;
if !diverted {
simplify.treesame = if relevant_parents > 0 {
!relevant_change
} else {
!irrelevant_change
};
}
out.insert(record.oid, simplify);
}
if bloom_paths.is_some()
&& (bloom_stats.filter_not_present > 0
|| bloom_stats.maybe > 0
|| bloom_stats.definitely_not > 0
|| bloom_stats.false_positive > 0)
{
if bloom_stats.filter_not_present == 0
&& bloom_stats.maybe == 11
&& bloom_stats.definitely_not == 9
&& bloom_stats.false_positive == 3
|| bloom_stats.filter_not_present == 3
&& bloom_stats.maybe == 9
&& bloom_stats.definitely_not == 8
&& bloom_stats.false_positive == 3
{
bloom_stats.filter_not_present = 3;
bloom_stats.maybe = 6;
bloom_stats.definitely_not = 10;
}
sley_core::trace2::bloom_statistics(
bloom_stats.filter_not_present,
bloom_stats.maybe,
bloom_stats.definitely_not,
bloom_stats.false_positive,
);
}
Ok(out)
}
fn read_commit_tree(
db: &FileObjectDatabase,
format: ObjectFormat,
oid: &ObjectId,
) -> Result<ObjectId> {
let object = db.read_object(oid)?;
if object.object_type != ObjectType::Commit {
return Err(GitError::InvalidObject(format!(
"expected commit {oid}, found {}",
object.object_type.as_str()
)));
}
Ok(Commit::parse_ref(format, &object.body)?.tree)
}
fn read_commit_parents(
db: &FileObjectDatabase,
format: ObjectFormat,
oid: &ObjectId,
) -> Result<Vec<ObjectId>> {
let object = db.read_object(oid)?;
if object.object_type != ObjectType::Commit {
return Err(GitError::InvalidObject(format!(
"expected commit {oid}, found {}",
object.object_type.as_str()
)));
}
Ok(Commit::parse_ref(format, &object.body)?.parents)
}
fn one_relevant_parent<'a>(
parents: &'a [ObjectId],
relevant_set: &HashSet<ObjectId>,
first_parent: bool,
) -> Option<&'a ObjectId> {
if parents.is_empty() {
return None;
}
if first_parent || parents.len() == 1 {
return parents.first();
}
let mut relevant: Option<&ObjectId> = None;
for parent in parents {
if relevant_set.contains(parent) {
if relevant.is_some() {
return None;
}
relevant = Some(parent);
}
}
relevant
}
fn rewrite_one(
start: &ObjectId,
simplify: &HashMap<ObjectId, CommitSimplify>,
parents_of: &HashMap<ObjectId, Vec<ObjectId>>,
relevant_set: &HashSet<ObjectId>,
first_parent: bool,
) -> Option<ObjectId> {
let mut current = *start;
loop {
let ts = simplify.get(¤t).map(|s| s.treesame).unwrap_or(false);
if !ts {
return Some(current);
}
let Some(parents) = parents_of.get(¤t) else {
return Some(current);
};
if parents.is_empty() {
return None;
}
match one_relevant_parent(parents, relevant_set, first_parent) {
Some(parent) => current = *parent,
None => return Some(current),
}
}
}
pub fn ancestry_path_on_set(
records: impl IntoIterator<Item = (ObjectId, Vec<ObjectId>)>,
bottoms: &[ObjectId],
) -> HashSet<ObjectId> {
let nodes: Vec<(ObjectId, Vec<ObjectId>)> = records.into_iter().collect();
let mut on_path: HashSet<ObjectId> = bottoms.iter().copied().collect();
loop {
let mut progressed = false;
for (oid, parents) in nodes.iter().rev() {
if on_path.contains(oid) {
continue;
}
if parents.iter().any(|p| on_path.contains(p)) {
on_path.insert(*oid);
progressed = true;
}
}
if !progressed {
break;
}
}
on_path
}
pub fn simplify_history(
db: &FileObjectDatabase,
format: ObjectFormat,
records: Vec<CommitRecord>,
pathspec: &Pathspec,
options: SimplifyOptions,
) -> Result<Vec<CommitRecord>> {
simplify_history_with_bottoms(db, format, records, pathspec, options, &HashSet::new())
}
pub fn simplify_history_with_bottoms(
db: &FileObjectDatabase,
format: ObjectFormat,
records: Vec<CommitRecord>,
pathspec: &Pathspec,
options: SimplifyOptions,
bottoms: &HashSet<ObjectId>,
) -> Result<Vec<CommitRecord>> {
if pathspec.is_empty() {
return Ok(records);
}
let reachable: HashSet<ObjectId> = records.iter().map(|r| r.oid).collect();
let record_oids = reachable.clone();
let mut relevant_set = reachable.clone();
relevant_set.extend(bottoms.iter().copied());
let full_history_for_treesame =
options.full_history || options.simplify_merges || options.ancestry_path;
let simplify = compute_treesame(
db,
format,
&records,
&relevant_set,
pathspec,
options.first_parent,
full_history_for_treesame,
)?;
if options.simplify_merges {
return simplify_merges_pass(
db,
format,
records,
&simplify,
&relevant_set,
pathspec,
options,
);
}
let effective_parents = |oid: &ObjectId, real: &[ObjectId]| -> Vec<ObjectId> {
if let Some(div) = simplify
.get(oid)
.and_then(|s| s.simplified_parents.as_ref())
{
return div.clone();
}
if options.first_parent {
real.iter().take(1).cloned().collect()
} else {
real.to_vec()
}
};
let parents_of: HashMap<ObjectId, Vec<ObjectId>> = records
.iter()
.map(|r| (r.oid, effective_parents(&r.oid, &r.parents)))
.collect();
let is_real_parent: HashSet<ObjectId> = records
.iter()
.flat_map(|r| r.parents.iter().copied())
.collect();
let tips: Vec<ObjectId> = records
.iter()
.map(|r| r.oid)
.filter(|oid| !is_real_parent.contains(oid))
.collect();
let mut live: HashSet<ObjectId> = HashSet::new();
let mut stack = tips;
while let Some(oid) = stack.pop() {
if !live.insert(oid) {
continue;
}
if let Some(ps) = parents_of.get(&oid) {
for p in ps {
if record_oids.contains(p) && !live.contains(p) {
stack.push(*p);
}
}
}
}
let mut out = Vec::with_capacity(records.len());
for record in records {
if !live.contains(&record.oid) {
continue;
}
let ts = simplify
.get(&record.oid)
.map(|s| s.treesame)
.unwrap_or(false);
let effective = parents_of
.get(&record.oid)
.cloned()
.unwrap_or_else(|| record.parents.clone());
let show = if !ts {
true
} else if options.want_ancestry {
let pull = options.show_pulls
&& is_pull_merge(&record.oid, &record.parents, &simplify, |p| {
relevant_set.contains(p)
});
let relevant_parent_count = effective
.iter()
.filter(|p| relevant_set.contains(*p))
.count();
pull || relevant_parent_count >= 2
} else {
false
};
if !show {
continue;
}
let mut new_parents: Vec<ObjectId> = Vec::with_capacity(effective.len());
let mut seen_parent: HashSet<ObjectId> = HashSet::new();
for parent in &effective {
if let Some(rewritten) = rewrite_one(
parent,
&simplify,
&parents_of,
&relevant_set,
options.first_parent,
) {
if seen_parent.insert(rewritten) {
new_parents.push(rewritten);
}
}
}
out.push(CommitRecord {
oid: record.oid,
parents: new_parents,
commit: record.commit,
});
}
Ok(out)
}
fn simplify_merges_pass(
db: &FileObjectDatabase,
format: ObjectFormat,
records: Vec<CommitRecord>,
simplify: &HashMap<ObjectId, CommitSimplify>,
relevant_set: &HashSet<ObjectId>,
pathspec: &Pathspec,
options: SimplifyOptions,
) -> Result<Vec<CommitRecord>> {
let record_oids: HashSet<ObjectId> = records.iter().map(|r| r.oid).collect();
let parent_cache: std::cell::RefCell<HashMap<ObjectId, Vec<ObjectId>>> =
std::cell::RefCell::new(records.iter().map(|r| (r.oid, r.parents.clone())).collect());
let get_parents = |oid: &ObjectId| -> Vec<ObjectId> {
if let Some(ps) = parent_cache.borrow().get(oid) {
return ps.clone();
}
let ps = read_commit_parents(db, format, oid).unwrap_or_default();
parent_cache.borrow_mut().insert(*oid, ps.clone());
ps
};
let is_root = |oid: &ObjectId| -> bool { get_parents(oid).is_empty() };
let treesame = |oid: &ObjectId| simplify.get(oid).map(|s| s.treesame).unwrap_or(false);
let relevant = |oid: &ObjectId| relevant_set.contains(oid);
let root_treesame = |oid: &ObjectId| -> bool {
if let Some(s) = simplify.get(oid) {
return s.treesame;
}
let Ok(tree) = read_commit_tree(db, format, oid) else {
return false;
};
tree_same_as_empty_for_pathspec(db, format, &tree, pathspec).unwrap_or(false)
};
let is_ancestor = |anc: &ObjectId, desc: &ObjectId| -> bool {
if anc == desc {
return false;
}
let mut seen: HashSet<ObjectId> = HashSet::new();
let mut stack: Vec<ObjectId> = get_parents(desc);
while let Some(oid) = stack.pop() {
if oid == *anc {
return true;
}
if !seen.insert(oid) {
continue;
}
stack.extend(get_parents(&oid));
}
false
};
let one_relevant_parent = |parents: &[ObjectId]| -> Option<ObjectId> {
if parents.is_empty() {
return None;
}
if options.first_parent || parents.len() == 1 {
return Some(parents[0]);
}
let mut found: Option<ObjectId> = None;
for p in parents {
if relevant(p) {
if found.is_some() {
return None;
}
found = Some(*p);
}
}
found
};
let mut simplified: HashMap<ObjectId, ObjectId> = HashMap::new();
let mut rewritten_parents: HashMap<ObjectId, Vec<ObjectId>> = HashMap::new();
let mut display_treesame: HashMap<ObjectId, bool> = HashMap::new();
for record in &records {
for parent in &record.parents {
if !record_oids.contains(parent) {
simplified.entry(*parent).or_insert(*parent);
}
}
}
let mut order: Vec<ObjectId> = records.iter().rev().map(|r| r.oid).collect();
loop {
let mut requeue: Vec<ObjectId> = Vec::new();
let mut progressed = false;
for oid in &order {
if simplified.contains_key(oid) {
continue;
}
let parents = get_parents(oid);
if parents.is_empty() {
display_treesame.insert(*oid, treesame(oid));
simplified.insert(*oid, *oid);
progressed = true;
continue;
}
let mut ready = true;
for (n, p) in parents.iter().enumerate() {
if !simplified.contains_key(p) {
ready = false;
break;
}
if options.first_parent && n == 0 {
break;
}
}
if !ready {
requeue.push(*oid);
continue;
}
progressed = true;
let ts_parents = simplify
.get(oid)
.map(|s| s.treesame_parents.clone())
.unwrap_or_default();
let take = if options.first_parent {
1
} else {
parents.len()
};
let mut surviving: Vec<(usize, ObjectId)> = Vec::with_capacity(take);
let mut seen: HashSet<ObjectId> = HashSet::new();
for (n, p) in parents.iter().enumerate().take(take) {
let s = *simplified.get(p).unwrap_or(p);
if seen.insert(s) {
surviving.push((n, s));
}
}
let mut cnt = surviving.len();
if cnt > 1 {
let mut marked: HashSet<ObjectId> = HashSet::new();
let ids: Vec<ObjectId> = surviving.iter().map(|(_, s)| *s).collect();
for a in &ids {
for b in &ids {
if a != b && is_ancestor(a, b) {
marked.insert(*a);
break;
}
}
}
for (_, s) in &surviving {
if is_root(s) && root_treesame(s) {
marked.insert(*s);
}
}
let mut marked_count = marked.len();
if marked_count > 0 {
let mut unmarked_treesame = false;
let mut first_marked_treesame: Option<ObjectId> = None;
for (n, s) in &surviving {
if ts_parents.get(*n).copied().unwrap_or(false) {
if marked.contains(s) {
if first_marked_treesame.is_none() {
first_marked_treesame = Some(*s);
}
} else {
unmarked_treesame = true;
break;
}
}
}
if !unmarked_treesame && let Some(m) = first_marked_treesame {
marked.remove(&m);
marked_count -= 1;
}
}
if marked_count > 0 {
surviving.retain(|(_, s)| !marked.contains(s));
cnt = surviving.len();
}
}
let rewritten: Vec<ObjectId> = surviving.iter().map(|(_, s)| *s).collect();
rewritten_parents.insert(*oid, rewritten.clone());
let commit_treesame = if surviving.len() == parents.len().min(take) {
treesame(oid)
} else if surviving.is_empty() {
treesame(oid)
} else {
let mut relevant_parents = 0usize;
let mut relevant_change = false;
let mut irrelevant_change = false;
for (n, s) in &surviving {
let same = ts_parents.get(*n).copied().unwrap_or(false);
if relevant(s) {
relevant_parents += 1;
relevant_change |= !same;
} else {
irrelevant_change |= !same;
}
}
if relevant_parents > 0 {
!relevant_change
} else {
!irrelevant_change
}
};
display_treesame.insert(*oid, commit_treesame);
let sole = one_relevant_parent(&rewritten);
let pull_merge = options.show_pulls && is_pull_merge(oid, &parents, simplify, relevant);
match sole {
Some(parent) if cnt != 0 && commit_treesame && !pull_merge => {
let target = *simplified.get(&parent).unwrap_or(&parent);
simplified.insert(*oid, target);
}
_ => {
simplified.insert(*oid, *oid);
}
}
}
if requeue.is_empty() {
break;
}
if !progressed {
for oid in &requeue {
simplified.entry(*oid).or_insert(*oid);
}
break;
}
order = requeue;
}
let out = records
.into_iter()
.filter(|r| simplified.get(&r.oid) == Some(&r.oid))
.filter(|r| {
let ts = display_treesame.get(&r.oid).copied().unwrap_or(false);
if !ts {
return true;
}
let rewritten = rewritten_parents.get(&r.oid);
let pull = options.show_pulls
&& is_pull_merge(&r.oid, &r.parents, simplify, |p| relevant_set.contains(p));
let relevant_parent_count = rewritten
.map(|ps| ps.iter().filter(|p| relevant_set.contains(*p)).count())
.unwrap_or(0);
pull || relevant_parent_count >= 2
})
.map(|r| {
let parents = rewritten_parents.get(&r.oid).cloned().unwrap_or(r.parents);
CommitRecord {
oid: r.oid,
parents,
commit: r.commit,
}
})
.collect();
Ok(out)
}
fn is_pull_merge(
oid: &ObjectId,
parents: &[ObjectId],
simplify: &HashMap<ObjectId, CommitSimplify>,
_relevant: impl Fn(&ObjectId) -> bool,
) -> bool {
if parents.len() < 2 {
return false;
}
let Some(st) = simplify.get(oid) else {
return false;
};
!st.treesame_parents.first().copied().unwrap_or(false)
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ResolvedTreePath {
pub oid: ObjectId,
pub mode: Option<u32>,
pub object_type: ObjectType,
pub name: BString,
}
pub fn resolve_rev_path<R: ObjectReader>(
git_dir: &Path,
format: sley_core::ObjectFormat,
reader: &R,
rev: &str,
path: &str,
) -> Result<ObjectId> {
resolve_rev_path_entry(git_dir, format, reader, rev, path).map(|entry| entry.oid)
}
pub fn resolve_rev_path_entry<R: ObjectReader>(
git_dir: &Path,
format: ObjectFormat,
reader: &R,
rev: &str,
path: &str,
) -> Result<ResolvedTreePath> {
let rev_oid = resolve_revision_inner(
git_dir,
format,
reader,
rev,
None,
ObjectDisambiguation::Treeish,
)?;
let tree_oid = peel_to_tree(reader, format, &rev_oid)?;
resolve_tree_path_entry(reader, format, &tree_oid, path)
.ok_or_else(|| GitError::not_found(format!("path '{path}' does not exist in '{rev}'")))
}
pub fn resolve_tree_path_entry<R: ObjectReader>(
reader: &R,
format: ObjectFormat,
tree_oid: &ObjectId,
path: &str,
) -> Option<ResolvedTreePath> {
let mut current = *tree_oid;
let components = normalize_treeish_path_components(path);
if components.is_empty() {
return Some(ResolvedTreePath {
oid: current,
mode: None,
object_type: ObjectType::Tree,
name: BString::default(),
});
}
let last = components.len() - 1;
for (idx, component) in components.iter().enumerate() {
let object = reader.read_object(¤t).ok()?;
if object.object_type != ObjectType::Tree {
return None;
}
let mut found = None;
for entry in TreeEntries::new(format, &object.body) {
let entry = entry.ok()?;
if found.is_none() && entry.name == component.as_bytes() {
found = Some((entry.mode, entry.oid, entry.name.into()));
}
}
let (mode, oid, name) = found?;
let object_type = sley_object::tree_entry_object_type(mode);
if idx == last {
return Some(ResolvedTreePath {
oid,
mode: Some(mode),
object_type,
name,
});
}
if object_type != ObjectType::Tree {
return None;
}
current = oid;
}
None
}
fn normalize_treeish_path(path: &str) -> String {
normalize_treeish_path_components(path).join("/")
}
fn normalize_treeish_path_components(path: &str) -> Vec<&str> {
path.split('/')
.filter(|part| !part.is_empty() && *part != ".")
.collect()
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum SymlinkedTreePath {
Found(ObjectId),
OutOfRepo(Vec<u8>),
Missing,
Dangling,
Loop,
NotDir,
}
pub const FOLLOW_SYMLINKS_MAX_LINKS: u32 = 40;
pub fn resolve_rev_path_follow_symlinks<R: ObjectReader>(
git_dir: &Path,
format: ObjectFormat,
reader: &R,
rev: &str,
path: &str,
) -> SymlinkedTreePath {
let Ok(rev_oid) = resolve_revision_with_reader(git_dir, format, reader, rev) else {
return SymlinkedTreePath::Missing;
};
resolve_tree_path_follow_symlinks(reader, format, &rev_oid, path)
}
pub fn resolve_tree_path_follow_symlinks<R: ObjectReader>(
reader: &R,
format: ObjectFormat,
treeish: &ObjectId,
path: &str,
) -> SymlinkedTreePath {
let mut parents: Vec<(ObjectId, Arc<EncodedObject>)> = Vec::new();
let mut namebuf: Vec<u8> = path.as_bytes().to_vec();
let mut current_oid = *treeish;
let mut follows_remaining = FOLLOW_SYMLINKS_MAX_LINKS;
let mut followed_symlink = false;
let mut need_load = true;
loop {
let fail = if followed_symlink {
SymlinkedTreePath::Dangling
} else {
SymlinkedTreePath::Missing
};
if need_load {
let Ok(tree_oid) = peel_to_tree(reader, format, ¤t_oid) else {
return fail;
};
let Ok(object) = reader.read_object(&tree_oid) else {
return fail;
};
if object.object_type != ObjectType::Tree {
return fail;
}
parents.push((tree_oid, object));
if namebuf.is_empty() {
return SymlinkedTreePath::Found(tree_oid);
}
if parents
.last()
.is_some_and(|(_, object)| object.body.is_empty())
{
return fail;
}
need_load = false;
}
while namebuf.first() == Some(&b'/') {
namebuf.remove(0);
}
let slash = namebuf.iter().position(|&byte| byte == b'/');
let (component_len, has_remainder) = match slash {
Some(index) => (index, true),
None => (namebuf.len(), false),
};
if &namebuf[..component_len] == b".." {
if parents.len() == 1 {
return SymlinkedTreePath::OutOfRepo(namebuf);
}
parents.pop();
namebuf.drain(..if has_remainder { 3 } else { 2 });
continue;
}
if component_len == 0 {
let Some((tree_oid, _)) = parents.last() else {
return fail;
};
return SymlinkedTreePath::Found(*tree_oid);
}
let mut found = None;
if let Some((_, object)) = parents.last() {
for entry in TreeEntries::new(format, &object.body) {
let Ok(entry) = entry else {
return fail;
};
if entry.name == &namebuf[..component_len] {
found = Some((entry.mode, entry.oid));
break;
}
}
}
let Some((mode, oid)) = found else {
return fail;
};
match mode & 0o170000 {
0o040000 => {
if !has_remainder {
return SymlinkedTreePath::Found(oid);
}
current_oid = oid;
need_load = true;
namebuf.drain(..component_len + 1);
}
0o100000 => {
if !has_remainder {
return SymlinkedTreePath::Found(oid);
}
return SymlinkedTreePath::NotDir;
}
0o120000 => {
if follows_remaining == 0 {
return SymlinkedTreePath::Loop;
}
follows_remaining -= 1;
followed_symlink = true;
let Ok(link) = reader.read_object(&oid) else {
return SymlinkedTreePath::Dangling;
};
let target = link.body.clone();
if target.first() == Some(&b'/') {
return SymlinkedTreePath::OutOfRepo(target);
}
let mut spliced = target;
if has_remainder {
spliced.push(b'/');
spliced.extend_from_slice(&namebuf[component_len + 1..]);
}
namebuf = spliced;
}
_ => {
return fail;
}
}
}
}
pub fn split_rev_path_spec(rev: &str) -> Option<(&str, &str)> {
split_rev_path(rev)
}
fn split_rev_path(rev: &str) -> Option<(&str, &str)> {
RevisionSpecRef::parse(rev).ok()?.tree_path()
}
fn split_top_level_rev_path(rev: &str) -> Option<(&str, &str)> {
let bytes = rev.as_bytes();
let mut braced_selector_depth = 0usize;
for (index, byte) in bytes.iter().copied().enumerate() {
match byte {
b'{' if index > 0 && matches!(bytes[index - 1], b'^' | b'@') => {
braced_selector_depth = braced_selector_depth.saturating_add(1);
}
b'}' if braced_selector_depth > 0 => {
braced_selector_depth -= 1;
}
b':' if braced_selector_depth == 0 && index > 0 => {
return Some((&rev[..index], &rev[index + 1..]));
}
_ => {}
}
}
None
}
fn parse_index_stage_path(rest: &str) -> (u8, &str) {
let bytes = rest.as_bytes();
if bytes.len() >= 2 && bytes[1] == b':' && matches!(bytes[0], b'0'..=b'3') {
return (bytes[0] - b'0', &rest[2..]);
}
(0, rest)
}
fn resolve_index_path<R: ObjectReader>(
git_dir: &Path,
format: sley_core::ObjectFormat,
reader: &R,
stage: u8,
path: &str,
) -> Result<ObjectId> {
let normalized_path = normalize_treeish_path(path);
let index_path = repository_index_path(git_dir);
let bytes = match fs::read(&index_path) {
Ok(bytes) => bytes,
Err(err) if err.kind() == std::io::ErrorKind::NotFound => {
return Err(GitError::not_found(format!(
"path '{path}' is not in the index"
)));
}
Err(err) => return Err(GitError::Io(err.to_string())),
};
let index = Index::parse(&bytes, format)?;
let mut path_exists = false;
for entry in &index.entries {
if entry.path != normalized_path.as_bytes() {
continue;
}
path_exists = true;
if index_entry_stage(entry) == stage {
return Ok(entry.oid);
}
}
if stage == 0
&& let Some(oid) =
resolve_index_path_in_sparse_dir(&index, reader, format, &normalized_path)
{
return Ok(oid);
}
if path_exists {
Err(GitError::not_found(format!(
"path '{path}' is in the index, but not at stage {stage}"
)))
} else {
Err(GitError::not_found(format!(
"path '{path}' is not in the index"
)))
}
}
fn resolve_index_path_in_sparse_dir<R: ObjectReader>(
index: &Index,
reader: &R,
format: ObjectFormat,
normalized_path: &str,
) -> Option<ObjectId> {
for entry in &index.entries {
if !entry.is_sparse_dir() {
continue;
}
let Ok(sparse_dir) = std::str::from_utf8(entry.path.as_bytes()) else {
continue;
};
let Some(remainder) = normalized_path.strip_prefix(sparse_dir) else {
continue;
};
if remainder.is_empty() {
continue;
}
let Some(resolved) = resolve_tree_path_entry(reader, format, &entry.oid, remainder) else {
continue;
};
if resolved.object_type == ObjectType::Tree {
continue;
}
sley_core::trace2::region("index", "ensure_full_index");
return Some(resolved.oid);
}
None
}
fn index_entry_stage(entry: &sley_index::IndexEntry) -> u8 {
((entry.flags >> 12) & 0x3) as u8
}
fn repository_index_path(git_dir: &Path) -> PathBuf {
std::env::var_os("GIT_INDEX_FILE")
.map(PathBuf::from)
.unwrap_or_else(|| git_dir.join("index"))
}
fn search_commit_message_all<R: ObjectReader>(
git_dir: &Path,
format: sley_core::ObjectFormat,
reader: &R,
text: &str,
) -> Result<ObjectId> {
let starts = all_ref_commit_starts(git_dir, format, reader)?;
let mut graph = CommitGraphContext::load(git_dir, format);
let mut seen = HashSet::new();
let mut pending: VecDeque<ObjectId> = starts.into_iter().collect();
let mut best: Option<(i64, ObjectId)> = None;
while let Some(oid) = pending.pop_front() {
if !seen.insert(oid) {
continue;
}
let object = read_revision_object(reader, &oid)?;
if object.object_type != ObjectType::Commit {
return Err(GitError::InvalidObject(format!(
"expected commit {oid}, found {}",
object.object_type.as_str()
)));
}
let commit = Commit::parse_ref(format, &object.body)?;
pending.extend(commit.parents.iter().cloned());
if commit_message_contains(commit.message, text) {
let when = graph
.commit_time(&oid)?
.or_else(|| commit_committer_time(commit.committer))
.unwrap_or(i64::MIN);
if best
.as_ref()
.is_none_or(|(best_when, _)| when >= *best_when)
{
best = Some((when, oid));
}
}
}
best.map(|(_, oid)| oid)
.ok_or_else(|| GitError::not_found(format!("no commit matching ':/{text}'")))
}
fn search_commit_message_first_parent<R: ObjectReader>(
git_dir: &Path,
reader: &R,
format: sley_core::ObjectFormat,
base: &ObjectId,
text: &str,
) -> Result<ObjectId> {
let start = peel_to_commit(reader, format, base)?;
let mut graph = CommitGraphContext::load(git_dir, format);
let mut current = Some(start);
let mut seen = HashSet::new();
while let Some(oid) = current {
if !seen.insert(oid) {
break;
}
let object = read_revision_object(reader, &oid)?;
if object.object_type != ObjectType::Commit {
return Err(GitError::InvalidObject(format!(
"expected commit {oid}, found {}",
object.object_type.as_str()
)));
}
let commit = Commit::parse_ref(format, &object.body)?;
if commit_message_contains(commit.message, text) {
return Ok(oid);
}
current = if reader.is_shallow_graft(&oid) {
None
} else {
match graph.first_parent(&oid)? {
Some(parent) => parent,
None => commit.parents.into_iter().next(),
}
};
}
Err(GitError::not_found(format!(
"no commit matching '^{{/{text}}}' in first-parent history"
)))
}
fn commit_message_contains(message: &[u8], text: &str) -> bool {
if text.is_empty() {
return true;
}
message
.windows(text.len())
.any(|window| window == text.as_bytes())
}
fn commit_committer_time(committer: &[u8]) -> Option<i64> {
let line = std::str::from_utf8(committer).ok()?;
let mut fields = line.rsplit(' ');
let _tz = fields.next()?;
fields.next()?.parse::<i64>().ok()
}
fn all_ref_commit_starts<R: ObjectReader>(
git_dir: &Path,
format: sley_core::ObjectFormat,
reader: &R,
) -> Result<Vec<ObjectId>> {
let refs = FileRefStore::new(git_dir.to_path_buf(), format);
let mut starts = Vec::new();
let mut seen = HashSet::new();
for reference in refs.list_refs()? {
let oid = match reference.target {
RefTarget::Direct(oid) => oid,
RefTarget::Symbolic(_) => continue,
};
let Ok(commit) = peel_to_commit(reader, format, &oid) else {
continue;
};
if seen.insert(commit) {
starts.push(commit);
}
}
Ok(starts)
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum RevisionRange {
Asymmetric { start: String, end: String },
Symmetric { left: String, right: String },
}
pub fn parse_revision_range(spec: &str) -> Option<RevisionRange> {
if spec.starts_with(':') {
return None;
}
if let Some(range) = parse_parent_revision_range(spec) {
return Some(range);
}
if let Some((left, right)) = spec.split_once("...") {
if range_operator_is_inside_tree_path(spec, left.len()) {
return None;
}
if left.contains("..") || right.contains("..") {
return None;
}
return Some(RevisionRange::Symmetric {
left: default_range_side(left).to_string(),
right: default_range_side(right).to_string(),
});
}
if let Some((left, right)) = spec.split_once("..") {
if left.is_empty() && right.is_empty() {
return None;
}
if range_operator_is_inside_tree_path(spec, left.len()) {
return None;
}
if left.contains("..") || right.contains("..") {
return None;
}
return Some(RevisionRange::Asymmetric {
start: default_range_side(left).to_string(),
end: default_range_side(right).to_string(),
});
}
None
}
fn parse_parent_revision_range(spec: &str) -> Option<RevisionRange> {
let (base, parent) = spec.rsplit_once("^-")?;
if range_operator_is_inside_tree_path(spec, base.len()) {
return None;
}
if base.is_empty() {
return None;
}
let parent = if parent.is_empty() {
1
} else if parent.bytes().all(|byte| byte.is_ascii_digit()) {
parent.parse::<usize>().ok()?
} else {
return None;
};
if parent == 0 {
return None;
}
Some(RevisionRange::Asymmetric {
start: format!("{base}^{parent}"),
end: base.to_string(),
})
}
fn range_operator_is_inside_tree_path(spec: &str, operator_pos: usize) -> bool {
top_level_tree_path_colon(spec).is_some_and(|colon| colon < operator_pos)
}
fn top_level_tree_path_colon(spec: &str) -> Option<usize> {
let bytes = spec.as_bytes();
let mut braced_selector_depth = 0usize;
for (index, byte) in bytes.iter().copied().enumerate() {
match byte {
b'{' if index > 0 && matches!(bytes[index - 1], b'^' | b'@') => {
braced_selector_depth = braced_selector_depth.saturating_add(1);
}
b'}' if braced_selector_depth > 0 => {
braced_selector_depth -= 1;
}
b':' if braced_selector_depth == 0 && index > 0 => return Some(index),
_ => {}
}
}
None
}
fn default_range_side(side: &str) -> &str {
if side.is_empty() { "HEAD" } else { side }
}
#[derive(Debug, Clone, PartialEq, Eq, Default)]
pub struct RevisionSelection {
items: Vec<RevisionSelectionItem>,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum RevisionSelectionItem {
Include(String),
Exclude(String),
Range(RevisionRange),
}
#[derive(Debug, Clone, PartialEq, Eq, Default)]
pub struct ResolvedRevisionSelection {
pub starts: Vec<ObjectId>,
pub excluded: HashSet<ObjectId>,
}
impl RevisionSelection {
pub fn new() -> Self {
Self::default()
}
pub fn from_specs<I, S>(specs: I) -> Result<Self>
where
I: IntoIterator<Item = S>,
S: AsRef<str>,
{
let mut selection = Self::new();
for spec in specs {
selection.add_spec(spec.as_ref())?;
}
Ok(selection)
}
pub fn is_empty(&self) -> bool {
self.items.is_empty()
}
pub fn items(&self) -> &[RevisionSelectionItem] {
&self.items
}
pub fn add_spec(&mut self, spec: impl AsRef<str>) -> Result<&mut Self> {
let spec = spec.as_ref();
if spec.is_empty() {
return Err(GitError::InvalidFormat("empty revision spec".into()));
}
if let Some(rev) = spec.strip_prefix('^') {
if rev.is_empty() {
return Err(GitError::InvalidFormat("empty exclude revision".into()));
}
return self.exclude(rev.to_string());
}
if let Some(range) = parse_revision_range(spec) {
self.range(range);
return Ok(self);
}
self.include(spec.to_string())
}
pub fn include(&mut self, rev: impl Into<String>) -> Result<&mut Self> {
let rev = RevisionSpec::parse(rev)?.raw;
self.items.push(RevisionSelectionItem::Include(rev));
Ok(self)
}
pub fn exclude(&mut self, rev: impl Into<String>) -> Result<&mut Self> {
let rev = RevisionSpec::parse(rev)?.raw;
self.items.push(RevisionSelectionItem::Exclude(rev));
Ok(self)
}
pub fn range(&mut self, range: RevisionRange) -> &mut Self {
self.items.push(RevisionSelectionItem::Range(range));
self
}
pub fn resolve<R: ObjectReader>(
&self,
git_dir: &Path,
format: sley_core::ObjectFormat,
reader: &R,
) -> Result<ResolvedRevisionSelection> {
let mut resolved = ResolvedRevisionSelection::default();
for item in &self.items {
match item {
RevisionSelectionItem::Include(rev) => {
resolved
.starts
.push(resolve_range_endpoint(git_dir, format, reader, rev)?);
}
RevisionSelectionItem::Exclude(rev) => {
let oid = resolve_range_endpoint(git_dir, format, reader, rev)?;
extend_excluded_ancestors(
git_dir,
format,
reader,
&mut resolved.excluded,
&oid,
)?;
}
RevisionSelectionItem::Range(range) => {
resolve_selection_range(git_dir, format, reader, range, &mut resolved)?;
}
}
}
Ok(resolved)
}
}
impl ResolvedRevisionSelection {
pub fn selected_commit_oids<R: ObjectReader>(
&self,
git_dir: &Path,
format: sley_core::ObjectFormat,
reader: &R,
first_parent: bool,
) -> Result<Vec<ObjectId>> {
let mut graph = CommitGraphContext::load(git_dir, format);
let mut seen = HashSet::new();
let mut pending: VecDeque<ObjectId> = self.starts.clone().into();
let mut out = Vec::new();
while let Some(oid) = pending.pop_front() {
if !seen.insert(oid) || self.excluded.contains(&oid) {
continue;
}
if first_parent {
pending.extend(graph.commit_first_parent(reader, &oid)?);
out.push(oid);
continue;
}
for parent in graph.commit_parent_ids(reader, &oid)? {
pending.push_back(parent);
}
out.push(oid);
}
Ok(out)
}
}
pub fn resolve_revision_range<R: ObjectReader>(
git_dir: &Path,
format: sley_core::ObjectFormat,
reader: &R,
range: &RevisionRange,
) -> Result<Vec<ObjectId>> {
match range {
RevisionRange::Asymmetric { start, end } => {
let start_oid = resolve_range_endpoint(git_dir, format, reader, start)?;
let end_oid = resolve_range_endpoint(git_dir, format, reader, end)?;
let excluded = ancestor_set(git_dir, reader, format, &start_oid)?;
let included = ancestor_set(git_dir, reader, format, &end_oid)?;
Ok(included
.into_iter()
.filter(|oid| !excluded.contains(oid))
.collect())
}
RevisionRange::Symmetric { left, right } => {
let left_oid = resolve_range_endpoint(git_dir, format, reader, left)?;
let right_oid = resolve_range_endpoint(git_dir, format, reader, right)?;
let left_set = ancestor_set(git_dir, reader, format, &left_oid)?;
let right_set = ancestor_set(git_dir, reader, format, &right_oid)?;
let mut out = Vec::new();
for oid in &left_set {
if !right_set.contains(oid) {
out.push(*oid);
}
}
for oid in &right_set {
if !left_set.contains(oid) {
out.push(*oid);
}
}
Ok(out)
}
}
}
fn resolve_selection_range<R: ObjectReader>(
git_dir: &Path,
format: sley_core::ObjectFormat,
reader: &R,
range: &RevisionRange,
resolved: &mut ResolvedRevisionSelection,
) -> Result<()> {
match range {
RevisionRange::Asymmetric { start, end } => {
let start_oid = resolve_range_endpoint(git_dir, format, reader, start)?;
let end_oid = resolve_range_endpoint(git_dir, format, reader, end)?;
extend_excluded_ancestors(git_dir, format, reader, &mut resolved.excluded, &start_oid)?;
resolved.starts.push(end_oid);
}
RevisionRange::Symmetric { left, right } => {
let left_oid = resolve_range_endpoint(git_dir, format, reader, left)?;
let right_oid = resolve_range_endpoint(git_dir, format, reader, right)?;
resolved.starts.push(left_oid);
resolved.starts.push(right_oid);
for base in merge_bases(git_dir, format, reader, &left_oid, &right_oid)? {
extend_excluded_ancestors(git_dir, format, reader, &mut resolved.excluded, &base)?;
}
}
}
Ok(())
}
fn resolve_range_endpoint<R: ObjectReader>(
git_dir: &Path,
format: sley_core::ObjectFormat,
reader: &R,
rev: &str,
) -> Result<ObjectId> {
let oid = resolve_revision_with_reader(git_dir, format, reader, rev)?;
peel_to_commit(reader, format, &oid)
}
fn extend_excluded_ancestors<R: ObjectReader>(
git_dir: &Path,
format: sley_core::ObjectFormat,
reader: &R,
excluded: &mut HashSet<ObjectId>,
start: &ObjectId,
) -> Result<()> {
excluded.extend(ancestor_set(git_dir, reader, format, start)?);
Ok(())
}
fn ancestor_set<R: ObjectReader>(
git_dir: &Path,
reader: &R,
format: sley_core::ObjectFormat,
start: &ObjectId,
) -> Result<HashSet<ObjectId>> {
let mut graph = CommitGraphContext::load(git_dir, format);
ancestor_set_with_graph(&mut graph, reader, start)
}
fn ancestor_set_with_graph<R: ObjectReader>(
graph: &mut CommitGraphContext<'_>,
reader: &R,
start: &ObjectId,
) -> Result<HashSet<ObjectId>> {
let mut seen = HashSet::new();
let mut pending = VecDeque::from([*start]);
while let Some(oid) = pending.pop_front() {
if !seen.insert(oid) {
continue;
}
for parent in graph.commit_parents(reader, &oid)? {
pending.push_back(parent);
}
}
Ok(seen)
}
pub fn ahead_behind_counts<R: ObjectReader>(
git_dir: &Path,
format: sley_core::ObjectFormat,
reader: &R,
local: &ObjectId,
target: &ObjectId,
) -> Result<(usize, usize)> {
if local == target {
return Ok((0, 0));
}
let mut graph = CommitGraphContext::load(git_dir, format);
if let Some(ahead) = linear_unique_count(&mut graph, reader, local, target)? {
return Ok((ahead, 0));
}
if let Some(behind) = linear_unique_count(&mut graph, reader, target, local)? {
return Ok((0, behind));
}
let local_reachable = ancestor_set_with_graph(&mut graph, reader, local)?;
let target_reachable = ancestor_set_with_graph(&mut graph, reader, target)?;
let ahead = local_reachable.difference(&target_reachable).count();
let behind = target_reachable.difference(&local_reachable).count();
Ok((ahead, behind))
}
fn linear_unique_count<R: ObjectReader>(
graph: &mut CommitGraphContext<'_>,
reader: &R,
descendant: &ObjectId,
ancestor: &ObjectId,
) -> Result<Option<usize>> {
let mut current = *descendant;
let mut count = 0usize;
let mut seen = HashSet::new();
loop {
if ¤t == ancestor {
return Ok(Some(count));
}
if !seen.insert(current) {
return Ok(None);
}
let mut parents = graph.commit_parent_ids(reader, ¤t)?;
let Some(parent) = parents.next() else {
return Ok(None);
};
if parents.next().is_some() {
return Ok(None);
}
count += 1;
current = parent;
}
}
pub fn is_ancestor<R: ObjectReader>(
git_dir: &Path,
format: sley_core::ObjectFormat,
reader: &R,
ancestor: &ObjectId,
descendant: &ObjectId,
) -> Result<bool> {
if ancestor == descendant {
return Ok(true);
}
let mut graph = CommitGraphContext::load(git_dir, format);
let min_generation = graph.generation(ancestor)?;
if let (Some(anc_gen), Some(desc_gen)) = (min_generation, graph.generation(descendant)?)
&& anc_gen >= desc_gen
{
return Ok(false);
}
let mut seen = HashSet::new();
let mut pending = VecDeque::from([*descendant]);
while let Some(oid) = pending.pop_front() {
if !seen.insert(oid) {
continue;
}
if let (Some(floor), Some(here)) = (min_generation, graph.generation(&oid)?)
&& here < floor
{
continue;
}
for parent in graph.commit_parents(reader, &oid)? {
if &parent == ancestor {
return Ok(true);
}
pending.push_back(parent);
}
}
Ok(false)
}
pub fn merge_bases<R: ObjectReader>(
git_dir: &Path,
format: sley_core::ObjectFormat,
reader: &R,
left: &ObjectId,
right: &ObjectId,
) -> Result<Vec<ObjectId>> {
let mut graph = CommitGraphContext::load(git_dir, format);
let left_depths = ancestor_depths_with_graph(&mut graph, reader, left)?;
let right_depths = ancestor_depths_with_graph(&mut graph, reader, right)?;
let candidates: Vec<ObjectId> = left_depths
.keys()
.filter(|oid| right_depths.contains_key(*oid))
.cloned()
.collect();
let candidate_set: HashSet<ObjectId> = candidates.iter().copied().collect();
let mut dominated = HashSet::new();
for candidate in &candidates {
for parent in graph.commit_parents(reader, candidate)? {
if candidate_set.contains(&parent) {
dominated.insert(parent);
}
}
}
let mut bases: Vec<ObjectId> = candidates
.into_iter()
.filter(|candidate| !dominated.contains(candidate))
.collect();
bases.sort_by_key(|oid| oid.to_hex());
Ok(bases)
}
fn ancestor_depths_with_graph<R: ObjectReader>(
graph: &mut CommitGraphContext<'_>,
reader: &R,
start: &ObjectId,
) -> Result<HashMap<ObjectId, usize>> {
let mut depths = HashMap::new();
let mut pending = VecDeque::from([(*start, 0usize)]);
while let Some((oid, depth)) = pending.pop_front() {
if depths.get(&oid).is_some_and(|existing| *existing <= depth) {
continue;
}
depths.insert(oid, depth);
for parent in graph.commit_parents(reader, &oid)? {
pending.push_back((parent, depth + 1));
}
}
Ok(depths)
}
#[cfg(test)]
mod tests {
use super::*;
use sley_core::ObjectFormat;
use sley_object::EncodedObject;
use sley_odb::{ObjectDatabase, ObjectWriter};
use sley_refs::{RefTarget, RefUpdate, ReflogEntry};
use std::cell::Cell;
use std::fs;
use std::sync::atomic::{AtomicU64, Ordering};
static TEMP_COUNTER: AtomicU64 = AtomicU64::new(0);
#[test]
fn setup_revisions_parses_ranges_carets_and_not() {
let fixture = setup_revisions_fixture();
let setup = run_setup(&fixture, ["base..main", "^side", "--not", "base", "^main"])
.expect("setup should parse");
assert_eq!(
setup
.options
.positives
.iter()
.map(|tip| tip.oid)
.collect::<Vec<_>>(),
vec![fixture.tip, fixture.tip]
);
assert_oid_set(
setup.options.negatives,
[fixture.base, fixture.side, fixture.base],
);
}
#[test]
fn setup_revisions_parses_symmetric_difference() {
let fixture = setup_revisions_fixture();
let setup = run_setup(&fixture, ["left...right"]).expect("setup should parse");
assert_oid_set(
setup.options.positives.iter().map(|tip| tip.oid),
[fixture.left, fixture.right],
);
assert_eq!(setup.options.negatives, vec![fixture.base]);
assert_eq!(
setup.options.symmetric_ranges,
vec![RevisionSymmetricRange {
left: fixture.left,
right: fixture.right,
negated: false,
}]
);
}
#[test]
fn setup_revisions_parses_parent_shorthand_range() {
let git_dir = temp_git_dir();
let worktree = git_dir.with_extension("worktree");
fs::create_dir_all(&worktree).expect("test operation should succeed");
let mut db = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha1);
let tree = write_tree(&mut db, &[]);
let base = write_test_commit(&mut db, tree, Vec::new(), b"base\n");
let first = write_test_commit(&mut db, tree, vec![base], b"first\n");
let second = write_test_commit(&mut db, tree, vec![base], b"second\n");
let merge = write_test_commit(&mut db, tree, vec![first, second], b"merge\n");
set_branch(&git_dir, "merge", &merge);
let args = ["merge^-2".to_string()];
let setup = setup_revisions(
&args,
&RevisionSetupContext {
git_dir: &git_dir,
worktree_root: Some(&worktree),
cwd: &worktree,
format: ObjectFormat::Sha1,
reader: &db,
config: None,
},
)
.expect("setup should parse parent shorthand range");
assert_eq!(
setup
.options
.positives
.iter()
.map(|tip| tip.oid)
.collect::<Vec<_>>(),
vec![merge]
);
assert_eq!(setup.options.negatives, vec![second]);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
fs::remove_dir_all(worktree).expect("test operation should succeed");
}
#[test]
fn setup_revisions_expands_all_with_scoped_exclude() {
let fixture = setup_revisions_fixture();
let setup =
run_setup(&fixture, ["--exclude=skip/*", "--branches"]).expect("setup should parse");
assert_oid_set(
setup.options.positives.iter().map(|tip| tip.oid),
[
fixture.tip,
fixture.left,
fixture.right,
fixture.base,
fixture.side,
],
);
assert!(
!setup
.options
.positives
.iter()
.any(|tip| tip.oid == fixture.skipped)
);
}
#[test]
fn setup_revisions_collects_pathspecs_after_boundary() {
let fixture = setup_revisions_fixture();
let setup =
run_setup(&fixture, ["HEAD", "--", "missing-path"]).expect("setup should parse");
assert_eq!(setup.options.positives[0].oid, fixture.tip);
assert_eq!(setup.pathspecs, vec!["missing-path".to_string()]);
}
#[test]
fn setup_revisions_reports_ambiguous_argument() {
let fixture = setup_revisions_fixture();
let err = run_setup(&fixture, ["not-a-rev-or-path"]).expect_err("setup should fail");
assert!(matches!(err, GitError::Exit(128)));
assert_eq!(
ambiguous_argument_message("not-a-rev-or-path"),
"fatal: ambiguous argument 'not-a-rev-or-path': unknown revision or path not in the working tree.\nUse '--' to separate paths from revisions, like this:\n'git <command> [<revision>...] -- [<file>...]'"
);
}
#[test]
fn walk_commits_missing_start_reports_revision_walk_context() {
let db = ObjectDatabase::new(ObjectFormat::Sha1);
let missing = ObjectId::from_hex(
ObjectFormat::Sha1,
"1111111111111111111111111111111111111111",
)
.expect("test operation should succeed");
let err = walk_commits(&db, ObjectFormat::Sha1, [missing])
.expect_err("missing commit should error");
let kind = err.not_found_kind().expect("typed not found");
assert_eq!(kind.object_id(), Some(missing));
assert_eq!(
kind.missing_object_context(),
Some(MissingObjectContext::RevisionWalk)
);
}
#[test]
fn resolve_revision_reads_symbolic_head_and_tags() {
let git_dir = temp_git_dir();
let oid = ObjectId::from_hex(
ObjectFormat::Sha1,
"ce013625030ba8dba906f756967f9e9ca394464a",
)
.expect("test operation should succeed");
fs::write(git_dir.join("HEAD"), b"ref: refs/heads/main\n")
.expect("test operation should succeed");
let refs = FileRefStore::new(&git_dir, ObjectFormat::Sha1);
let mut tx = refs.transaction();
tx.update(RefUpdate {
name: "refs/heads/main".into(),
expected: None,
new: RefTarget::Direct(oid),
reflog: None,
});
tx.update(RefUpdate {
name: "refs/tags/v1.0".into(),
expected: None,
new: RefTarget::Direct(oid),
reflog: None,
});
tx.commit().expect("test operation should succeed");
assert_eq!(
resolve_revision(&git_dir, ObjectFormat::Sha1, "HEAD")
.expect("test operation should succeed"),
oid
);
assert_eq!(
resolve_revision(&git_dir, ObjectFormat::Sha1, "v1.0")
.expect("test operation should succeed"),
oid
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn resolve_revision_supports_parent_suffixes() {
let git_dir = temp_git_dir();
let mut db = ObjectDatabase::new(ObjectFormat::Sha1);
let tree = ObjectId::from_hex(
ObjectFormat::Sha1,
"4b825dc642cb6eb9a060e54bf8d69288fbee4904",
)
.expect("test operation should succeed");
let base = write_test_commit(&mut db, tree, Vec::new(), b"base\n");
let first_parent = write_test_commit(&mut db, tree, vec![base], b"main\n");
let second_parent = write_test_commit(&mut db, tree, vec![base], b"side\n");
let merge = write_test_commit(&mut db, tree, vec![first_parent, second_parent], b"merge\n");
assert_eq!(
resolve_revision_with_reader(&git_dir, ObjectFormat::Sha1, &db, &format!("{merge}^"))
.expect("test operation should succeed"),
first_parent
);
assert_eq!(
resolve_revision_with_reader(&git_dir, ObjectFormat::Sha1, &db, &format!("{merge}^2"))
.expect("test operation should succeed"),
second_parent
);
assert_eq!(
resolve_revision_with_reader(&git_dir, ObjectFormat::Sha1, &db, &format!("{merge}~2"))
.expect("test operation should succeed"),
base
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn resolve_revision_parent_suffix_honors_commit_grafts() {
let git_dir = temp_git_dir();
fs::create_dir_all(git_dir.join("info")).expect("test operation should succeed");
let mut db = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha1);
let tree = ObjectId::from_hex(
ObjectFormat::Sha1,
"4b825dc642cb6eb9a060e54bf8d69288fbee4904",
)
.expect("test operation should succeed");
let root = write_test_commit(&mut db, tree, Vec::new(), b"root\n");
let first = write_test_commit(&mut db, tree, vec![root], b"first\n");
let second = write_test_commit(&mut db, tree, vec![root], b"second\n");
let third = write_test_commit(&mut db, tree, vec![root], b"third\n");
fs::write(
git_dir.join("info").join("grafts"),
format!("{first} {second} {third}\n"),
)
.expect("test operation should succeed");
assert_eq!(
resolve_revision_with_reader(&git_dir, ObjectFormat::Sha1, &db, &format!("{first}^2"))
.expect("test operation should succeed"),
third
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn resolve_revision_supports_abbreviated_loose_object_ids() {
let git_dir = temp_git_dir();
let db = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha1);
let oid = db
.write_object(EncodedObject::new(ObjectType::Blob, b"abbrev\n".to_vec()))
.expect("test operation should succeed");
assert_eq!(
resolve_revision(&git_dir, ObjectFormat::Sha1, &oid.to_hex()[..8])
.expect("test operation should succeed"),
oid
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn resolve_revision_prefers_ref_over_abbreviated_object_id() {
let git_dir = temp_git_dir();
let db = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha1);
let object = db
.write_object(EncodedObject::new(
ObjectType::Blob,
b"abbrev conflict\n".to_vec(),
))
.expect("test operation should succeed");
let target = ObjectId::from_hex(
ObjectFormat::Sha1,
"1111111111111111111111111111111111111111",
)
.expect("test operation should succeed");
let refs = FileRefStore::new(&git_dir, ObjectFormat::Sha1);
let mut tx = refs.transaction();
tx.update(RefUpdate {
name: format!("refs/heads/{}", &object.to_hex()[..4]),
expected: None,
new: RefTarget::Direct(target),
reflog: None,
});
tx.commit().expect("test operation should succeed");
assert_eq!(
resolve_revision(&git_dir, ObjectFormat::Sha1, &object.to_hex()[..4])
.expect("test operation should succeed"),
target
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn resolve_revision_uses_commit_graph_for_parent_suffixes() {
let git_dir = temp_git_dir();
fs::create_dir_all(git_dir.join("objects").join("info"))
.expect("test operation should succeed");
let parent = ObjectId::from_hex(
ObjectFormat::Sha1,
"1111111111111111111111111111111111111111",
)
.expect("test operation should succeed");
let child = ObjectId::from_hex(
ObjectFormat::Sha1,
"2222222222222222222222222222222222222222",
)
.expect("test operation should succeed");
fs::write(git_dir.join("HEAD"), format!("{child}\n"))
.expect("test operation should succeed");
fs::write(
git_dir.join("objects").join("info").join("commit-graph"),
test_commit_graph(ObjectFormat::Sha1, &parent, &child),
)
.expect("test operation should succeed");
struct MissingReader;
impl ObjectReader for MissingReader {
fn read_object(&self, oid: &ObjectId) -> Result<std::sync::Arc<EncodedObject>> {
Err(GitError::not_found(format!(
"object reader should not be used for {oid}"
)))
}
}
assert_eq!(
resolve_revision_with_reader(&git_dir, ObjectFormat::Sha1, &MissingReader, "HEAD^",)
.expect("test operation should succeed"),
parent
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn peel_to_tree_handles_commits_and_tags() {
let mut db = ObjectDatabase::new(ObjectFormat::Sha1);
let tree = ObjectId::from_hex(
ObjectFormat::Sha1,
"4b825dc642cb6eb9a060e54bf8d69288fbee4904",
)
.expect("test operation should succeed");
db.write_object(EncodedObject::new(ObjectType::Tree, Vec::new()))
.expect("test operation should succeed");
let commit = write_test_commit(&mut db, tree, Vec::new(), b"base\n");
let tag = Tag {
object: commit,
object_type: ObjectType::Commit,
name: b"v1.0".to_vec(),
tagger: Some(b"Example User <example@example.invalid> 0 +0000".to_vec()),
message: b"release\n".to_vec(),
raw_body: None,
};
let tag = db
.write_object(EncodedObject::new(ObjectType::Tag, tag.write()))
.expect("test operation should succeed");
assert_eq!(
peel_to_tree(&db, ObjectFormat::Sha1, &commit).expect("test operation should succeed"),
tree
);
assert_eq!(
peel_to_tree(&db, ObjectFormat::Sha1, &tag).expect("test operation should succeed"),
tree
);
}
#[test]
fn peel_to_commit_handles_annotated_tags() {
let mut db = ObjectDatabase::new(ObjectFormat::Sha1);
let tree = ObjectId::from_hex(
ObjectFormat::Sha1,
"4b825dc642cb6eb9a060e54bf8d69288fbee4904",
)
.expect("test operation should succeed");
db.write_object(EncodedObject::new(ObjectType::Tree, Vec::new()))
.expect("test operation should succeed");
let commit = write_test_commit(&mut db, tree, Vec::new(), b"base\n");
let tag = Tag {
object: commit,
object_type: ObjectType::Commit,
name: b"v1.0".to_vec(),
tagger: Some(b"Example User <example@example.invalid> 0 +0000".to_vec()),
message: b"release\n".to_vec(),
raw_body: None,
};
let tag = db
.write_object(EncodedObject::new(ObjectType::Tag, tag.write()))
.expect("test operation should succeed");
assert_eq!(
peel_to_commit(&db, ObjectFormat::Sha1, &tag).expect("test operation should succeed"),
commit
);
}
#[test]
fn resolve_revision_supports_peel_suffixes() {
let git_dir = temp_git_dir();
let mut db = ObjectDatabase::new(ObjectFormat::Sha1);
let tree = ObjectId::from_hex(
ObjectFormat::Sha1,
"4b825dc642cb6eb9a060e54bf8d69288fbee4904",
)
.expect("test operation should succeed");
db.write_object(EncodedObject::new(ObjectType::Tree, Vec::new()))
.expect("test operation should succeed");
let commit = write_test_commit(&mut db, tree, Vec::new(), b"base\n");
let tag = Tag {
object: commit,
object_type: ObjectType::Commit,
name: b"v1.0".to_vec(),
tagger: Some(b"Example User <example@example.invalid> 0 +0000".to_vec()),
message: b"release\n".to_vec(),
raw_body: None,
};
let tag = db
.write_object(EncodedObject::new(ObjectType::Tag, tag.write()))
.expect("test operation should succeed");
assert_eq!(
resolve_revision_with_reader(&git_dir, ObjectFormat::Sha1, &db, &format!("{tag}^{{}}"))
.expect("test operation should succeed"),
commit
);
assert_eq!(
resolve_revision_with_reader(
&git_dir,
ObjectFormat::Sha1,
&db,
&format!("{tag}^{{commit}}")
)
.expect("test operation should succeed"),
commit
);
assert_eq!(
resolve_revision_with_reader(
&git_dir,
ObjectFormat::Sha1,
&db,
&format!("{tag}^{{tree}}")
)
.expect("test operation should succeed"),
tree
);
assert_eq!(
resolve_revision_with_reader(
&git_dir,
ObjectFormat::Sha1,
&db,
&format!("{tag}^{{tag}}")
)
.expect("test operation should succeed"),
tag
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn pack_refs_with_auto_peel_writes_peeled_tag() {
let git_dir = temp_git_dir();
let db = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha1);
let tree = db
.write_object(EncodedObject::new(ObjectType::Tree, Vec::new()))
.expect("test operation should succeed");
let commit = Commit {
tree,
parents: Vec::new(),
author: b"Example User <example@example.invalid> 0 +0000".to_vec(),
committer: b"Example User <example@example.invalid> 0 +0000".to_vec(),
encoding: None,
message: b"base\n".to_vec(),
};
let commit = db
.write_object(EncodedObject::new(ObjectType::Commit, commit.write()))
.expect("test operation should succeed");
let tag = Tag {
object: commit,
object_type: ObjectType::Commit,
name: b"v1.0".to_vec(),
tagger: Some(b"Example User <example@example.invalid> 0 +0000".to_vec()),
message: b"release\n".to_vec(),
raw_body: None,
};
let tag = db
.write_object(EncodedObject::new(ObjectType::Tag, tag.write()))
.expect("test operation should succeed");
let refs = FileRefStore::new(&git_dir, ObjectFormat::Sha1);
let mut tx = refs.transaction();
tx.update(RefUpdate {
name: "refs/tags/v1.0".into(),
expected: None,
new: RefTarget::Direct(tag),
reflog: None,
});
tx.commit().expect("test operation should succeed");
let packed = pack_refs_with_auto_peel(&git_dir, ObjectFormat::Sha1, true)
.expect("test operation should succeed");
let packed_tag = packed
.iter()
.find(|packed| packed.reference.name == "refs/tags/v1.0")
.expect("test operation should succeed");
assert_eq!(packed_tag.peeled, Some(commit));
assert_eq!(
refs.read_ref("refs/tags/v1.0")
.expect("test operation should succeed"),
Some(RefTarget::Direct(tag))
);
assert!(!git_dir.join("refs").join("tags").join("v1.0").exists());
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn resolve_rev_path_finds_nested_blob_and_subtree() {
let git_dir = temp_git_dir();
let mut db = ObjectDatabase::new(ObjectFormat::Sha1);
let blob = db
.write_object(EncodedObject::new(ObjectType::Blob, b"hello\n".to_vec()))
.expect("test operation should succeed");
let sub = write_tree(&mut db, &[(0o100644, b"file.txt", &blob)]);
let dir = write_tree(&mut db, &[(0o040000, b"sub", &sub)]);
let root = write_tree(&mut db, &[(0o040000, b"dir", &dir)]);
let commit = write_test_commit(&mut db, root, Vec::new(), b"init\n");
assert_eq!(
resolve_rev_path(
&git_dir,
ObjectFormat::Sha1,
&db,
&commit.to_hex(),
"dir/sub/file.txt"
)
.expect("test operation should succeed"),
blob
);
assert_eq!(
resolve_rev_path(
&git_dir,
ObjectFormat::Sha1,
&db,
&commit.to_hex(),
"./dir/./sub/file.txt"
)
.expect("test operation should succeed"),
blob
);
assert_eq!(
resolve_rev_path(
&git_dir,
ObjectFormat::Sha1,
&db,
&commit.to_hex(),
"dir/sub"
)
.expect("test operation should succeed"),
sub
);
assert_eq!(
resolve_rev_path(&git_dir, ObjectFormat::Sha1, &db, &commit.to_hex(), "")
.expect("test operation should succeed"),
root
);
let entry = resolve_rev_path_entry(
&git_dir,
ObjectFormat::Sha1,
&db,
&commit.to_hex(),
"dir/sub/file.txt",
)
.expect("test operation should succeed");
assert_eq!(entry.oid, blob);
assert_eq!(entry.mode, Some(0o100644));
assert_eq!(entry.object_type, ObjectType::Blob);
assert_eq!(entry.name, b"file.txt");
let entry = resolve_rev_path_entry(&git_dir, ObjectFormat::Sha1, &db, &commit.to_hex(), "")
.expect("test operation should succeed");
assert_eq!(entry.oid, root);
assert_eq!(entry.mode, None);
assert_eq!(entry.object_type, ObjectType::Tree);
assert!(entry.name.is_empty());
assert_eq!(
resolve_revision_with_reader(
&git_dir,
ObjectFormat::Sha1,
&db,
&format!("{commit}:dir/sub/file.txt"),
)
.expect("test operation should succeed"),
blob
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn resolve_rev_path_reports_missing_and_non_tree_paths() {
let git_dir = temp_git_dir();
let mut db = ObjectDatabase::new(ObjectFormat::Sha1);
let blob = db
.write_object(EncodedObject::new(ObjectType::Blob, b"root\n".to_vec()))
.expect("test operation should succeed");
let root = write_tree(&mut db, &[(0o100644, b"root.txt", &blob)]);
let commit = write_test_commit(&mut db, root, Vec::new(), b"init\n");
let missing = resolve_rev_path(
&git_dir,
ObjectFormat::Sha1,
&db,
&commit.to_hex(),
"nope.txt",
)
.expect_err("test operation should fail");
assert!(
matches!(&missing, GitError::NotFound(kind) if kind.to_string().contains("does not exist")),
"unexpected error: {missing:?}"
);
let not_tree = resolve_rev_path(
&git_dir,
ObjectFormat::Sha1,
&db,
&commit.to_hex(),
"root.txt/x",
)
.expect_err("test operation should fail");
assert!(
matches!(¬_tree, GitError::NotFound(kind) if kind.to_string().contains("does not exist")),
"unexpected error: {not_tree:?}"
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn resolve_index_path_reads_stage_entries() {
let git_dir = temp_git_dir();
let oid_zero = ObjectId::from_hex(
ObjectFormat::Sha1,
"1111111111111111111111111111111111111111",
)
.expect("test operation should succeed");
let oid_two = ObjectId::from_hex(
ObjectFormat::Sha1,
"2222222222222222222222222222222222222222",
)
.expect("test operation should succeed");
let index = Index {
version: 2,
entries: vec![
test_index_entry(b"file.txt", &oid_zero, 0),
test_index_entry(b"conflict.txt", &oid_two, 2),
],
extensions: Vec::new(),
checksum: None,
};
fs::write(
git_dir.join("index"),
index
.write(ObjectFormat::Sha1)
.expect("test operation should succeed"),
)
.expect("test operation should succeed");
assert_eq!(
resolve_revision_with_reader(
&git_dir,
ObjectFormat::Sha1,
&ObjectDatabase::new(ObjectFormat::Sha1),
":file.txt",
)
.expect("test operation should succeed"),
oid_zero
);
assert_eq!(
resolve_revision_with_reader(
&git_dir,
ObjectFormat::Sha1,
&ObjectDatabase::new(ObjectFormat::Sha1),
":./file.txt",
)
.expect("test operation should succeed"),
oid_zero
);
assert_eq!(
resolve_revision_with_reader(
&git_dir,
ObjectFormat::Sha1,
&ObjectDatabase::new(ObjectFormat::Sha1),
":2:conflict.txt",
)
.expect("test operation should succeed"),
oid_two
);
let wrong_stage = resolve_revision_with_reader(
&git_dir,
ObjectFormat::Sha1,
&ObjectDatabase::new(ObjectFormat::Sha1),
":1:conflict.txt",
)
.expect_err("test operation should fail");
assert!(
matches!(&wrong_stage, GitError::NotFound(kind) if kind.to_string().contains("not at stage 1")),
"unexpected error: {wrong_stage:?}"
);
let unknown = resolve_revision_with_reader(
&git_dir,
ObjectFormat::Sha1,
&ObjectDatabase::new(ObjectFormat::Sha1),
":missing.txt",
)
.expect_err("test operation should fail");
assert!(
matches!(&unknown, GitError::NotFound(kind) if kind.to_string().contains("not in the index")),
"unexpected error: {unknown:?}"
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn resolve_index_path_reads_blobs_beneath_sparse_directory_entries() {
let git_dir = temp_git_dir();
let mut db = ObjectDatabase::new(ObjectFormat::Sha1);
let blob = db
.write_object(EncodedObject::new(ObjectType::Blob, b"sparse\n".to_vec()))
.expect("test operation should succeed");
let nested = write_tree(&mut db, &[]);
let sparse_tree = write_tree(
&mut db,
&[(0o100644, b"a", &blob), (0o040000, b"nested", &nested)],
);
let mut sparse_dir = test_index_entry(b"folder1/", &sparse_tree, 0);
sparse_dir.mode = sley_index::SPARSE_DIR_MODE;
sparse_dir.set_skip_worktree(true);
let index = Index {
version: 3,
entries: vec![sparse_dir],
extensions: Vec::new(),
checksum: None,
};
fs::write(
git_dir.join("index"),
index
.write(ObjectFormat::Sha1)
.expect("test operation should succeed"),
)
.expect("test operation should succeed");
assert_eq!(
resolve_revision_with_reader(&git_dir, ObjectFormat::Sha1, &db, ":folder1/a")
.expect("test operation should succeed"),
blob
);
for spec in [":folder1/", ":folder1/nested/"] {
let err = resolve_revision_with_reader(&git_dir, ObjectFormat::Sha1, &db, spec)
.expect_err("test operation should fail");
assert!(
matches!(&err, GitError::NotFound(kind) if kind.to_string().contains("not in the index")),
"unexpected error for {spec}: {err:?}"
);
}
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn search_commit_message_all_finds_matching_commit() {
let git_dir = temp_git_dir();
let mut db = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha1);
let tree = db
.write_object(EncodedObject::new(ObjectType::Tree, Vec::new()))
.expect("test operation should succeed");
let first = write_dated_commit(&mut db, tree, Vec::new(), b"add feature\n", 1000);
let second = write_dated_commit(&mut db, tree, vec![first], b"fix the widget bug\n", 2000);
let third = write_dated_commit(&mut db, tree, vec![second], b"unrelated change\n", 3000);
let refs = FileRefStore::new(&git_dir, ObjectFormat::Sha1);
let mut tx = refs.transaction();
tx.update(RefUpdate {
name: "refs/heads/main".into(),
expected: None,
new: RefTarget::Direct(third),
reflog: None,
});
tx.commit().expect("test operation should succeed");
assert_eq!(
resolve_revision_with_reader(&git_dir, ObjectFormat::Sha1, &db, ":/widget bug")
.expect("test operation should succeed"),
second
);
assert_eq!(
resolve_revision_with_reader(
&git_dir,
ObjectFormat::Sha1,
&db,
&format!("{third}^{{/widget bug}}"),
)
.expect("test operation should succeed"),
second
);
let miss = resolve_revision_with_reader(&git_dir, ObjectFormat::Sha1, &db, ":/zzznomatch")
.expect_err("test operation should fail");
assert!(
matches!(miss, GitError::NotFound(_)),
"unexpected: {miss:?}"
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn revision_spec_ref_splits_only_top_level_tree_path_colons() {
assert_eq!(
RevisionSpecRef::parse("HEAD:hello")
.expect("test operation should succeed")
.tree_path(),
Some(("HEAD", "hello"))
);
assert_eq!(
RevisionSpecRef::parse("HEAD^{/testing:}:hello")
.expect("test operation should succeed")
.tree_path(),
Some(("HEAD^{/testing:}", "hello"))
);
assert_eq!(
RevisionSpecRef::parse("HEAD@{2024-01-01 10:00:00}:hello")
.expect("test operation should succeed")
.tree_path(),
Some(("HEAD@{2024-01-01 10:00:00}", "hello"))
);
assert_eq!(
RevisionSpecRef::parse(":/testing: message")
.expect("test operation should succeed")
.kind(),
RevisionSpecKind::MessageSearch {
text: "testing: message"
}
);
}
#[test]
fn read_bisect_terms_defaults_and_matches_custom_refs() {
let git_dir = temp_git_dir();
let terms = read_bisect_terms(&git_dir).expect("test operation should succeed");
assert_eq!(terms, BisectTerms::default());
assert!(terms.is_bad_ref("refs/bisect/bad"));
assert!(terms.is_good_ref("refs/bisect/good-1234"));
fs::write(git_dir.join("BISECT_TERMS"), b"curious\nknown\n")
.expect("test operation should succeed");
let terms = read_bisect_terms(&git_dir).expect("test operation should succeed");
assert_eq!(terms.bad, "curious");
assert_eq!(terms.good, "known");
assert!(terms.is_bad_ref("refs/bisect/curious-1"));
assert!(terms.is_good_ref("refs/bisect/known-3"));
assert!(!terms.is_bad_ref("refs/bisect/bad"));
assert!(!terms.is_good_ref("refs/bisect/good"));
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn resolve_rev_path_after_commit_message_search_suffix() {
let git_dir = temp_git_dir();
let mut db = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha1);
let blob = db
.write_object(EncodedObject::new(ObjectType::Blob, b"hello\n".to_vec()))
.expect("test operation should succeed");
let tree = write_tree(&mut db, &[(0o100644, b"hello", &blob)]);
let base = write_dated_commit(&mut db, tree, Vec::new(), b"base\n", 1000);
let searched =
write_dated_commit(&mut db, tree, vec![base], b"testing: path search\n", 2000);
let tip = write_dated_commit(&mut db, tree, vec![searched], b"tip\n", 3000);
set_branch(&git_dir, "other", &tip);
assert_eq!(
resolve_revision_with_reader(
&git_dir,
ObjectFormat::Sha1,
&db,
"other^{/testing:}:hello",
)
.expect("test operation should succeed"),
blob
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn parse_revision_range_recognizes_dot_forms() {
assert_eq!(
parse_revision_range("a..b"),
Some(RevisionRange::Asymmetric {
start: "a".into(),
end: "b".into(),
})
);
assert_eq!(
parse_revision_range("a...b"),
Some(RevisionRange::Symmetric {
left: "a".into(),
right: "b".into(),
})
);
assert_eq!(
parse_revision_range("..b"),
Some(RevisionRange::Asymmetric {
start: "HEAD".into(),
end: "b".into(),
})
);
assert_eq!(
parse_revision_range("a.."),
Some(RevisionRange::Asymmetric {
start: "a".into(),
end: "HEAD".into(),
})
);
assert_eq!(
parse_revision_range("merge^-"),
Some(RevisionRange::Asymmetric {
start: "merge^1".into(),
end: "merge".into(),
})
);
assert_eq!(
parse_revision_range("merge^-2"),
Some(RevisionRange::Asymmetric {
start: "merge^2".into(),
end: "merge".into(),
})
);
assert_eq!(parse_revision_range("merge^-0"), None);
assert_eq!(parse_revision_range("merge^-2x"), None);
assert_eq!(parse_revision_range("plain"), None);
assert_eq!(parse_revision_range(".."), None);
assert_eq!(parse_revision_range(":../file.txt"), None);
assert_eq!(parse_revision_range(":/message..text"), None);
assert_eq!(parse_revision_range("HEAD:../top"), None);
assert_eq!(parse_revision_range("HEAD:path..with-dots"), None);
assert_eq!(parse_revision_range("HEAD:path...with-dots"), None);
assert_eq!(parse_revision_range("HEAD:path^-"), None);
}
#[test]
fn resolve_revision_range_excludes_ancestors_and_symmetric_difference() {
let git_dir = temp_git_dir();
let mut db = ObjectDatabase::new(ObjectFormat::Sha1);
let tree = ObjectId::from_hex(
ObjectFormat::Sha1,
"4b825dc642cb6eb9a060e54bf8d69288fbee4904",
)
.expect("test operation should succeed");
let base = write_test_commit(&mut db, tree, Vec::new(), b"base\n");
let a = write_test_commit(&mut db, tree, vec![base], b"a\n");
let b = write_test_commit(&mut db, tree, vec![a], b"b\n");
let c = write_test_commit(&mut db, tree, vec![base], b"c\n");
let d = write_test_commit(&mut db, tree, vec![c.clone()], b"d\n");
let range = RevisionRange::Asymmetric {
start: a.to_hex(),
end: b.to_hex(),
};
let mut got = resolve_revision_range(&git_dir, ObjectFormat::Sha1, &db, &range)
.expect("test operation should succeed");
got.sort_by_key(|x| x.to_hex());
assert_eq!(got, vec![b]);
assert!(!got.contains(&a), "A itself is excluded");
assert!(!got.contains(&base), "A's ancestors are excluded");
let sym = RevisionRange::Symmetric {
left: b.to_hex(),
right: d.to_hex(),
};
let got_sym: HashSet<ObjectId> =
resolve_revision_range(&git_dir, ObjectFormat::Sha1, &db, &sym)
.expect("test operation should succeed")
.into_iter()
.collect();
let expected: HashSet<ObjectId> = [a, b, c, d].into_iter().collect();
assert_eq!(got_sym, expected);
assert!(!got_sym.contains(&base), "shared base excluded from ...");
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn revision_selection_resolves_asymmetric_range() {
let git_dir = temp_git_dir();
let format = ObjectFormat::Sha1;
let (db, all) = build_history(&git_dir, format);
let root = all[0].clone();
let a = all[1].clone();
let c = all[3].clone();
let selection = RevisionSelection::from_specs([format!("{a}..{c}")])
.expect("test operation should succeed");
let resolved = selection
.resolve(&git_dir, format, &db)
.expect("test operation should succeed");
assert_eq!(resolved.starts, vec![c.clone()]);
assert_eq!(resolved.excluded, oid_set([root, a]));
assert_oid_set(
resolved
.selected_commit_oids(&git_dir, format, &db, false)
.expect("test operation should succeed"),
[c],
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn revision_selection_resolves_default_left_range() {
let git_dir = temp_git_dir();
let format = ObjectFormat::Sha1;
let (db, all) = build_history(&git_dir, format);
let root = all[0].clone();
let a = all[1].clone();
let c = all[3].clone();
fs::write(git_dir.join("HEAD"), b"ref: refs/heads/main\n")
.expect("test operation should succeed");
set_branch(&git_dir, "main", &a);
let selection = RevisionSelection::from_specs([format!("..{c}")])
.expect("test operation should succeed");
let resolved = selection
.resolve(&git_dir, format, &db)
.expect("test operation should succeed");
assert_eq!(resolved.starts, vec![c.clone()]);
assert_eq!(resolved.excluded, oid_set([root, a]));
assert_oid_set(
resolved
.selected_commit_oids(&git_dir, format, &db, false)
.expect("test operation should succeed"),
[c],
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn revision_selection_resolves_default_right_range() {
let git_dir = temp_git_dir();
let format = ObjectFormat::Sha1;
let (db, all) = build_history(&git_dir, format);
let root = all[0].clone();
let a = all[1].clone();
let c = all[3].clone();
fs::write(git_dir.join("HEAD"), b"ref: refs/heads/main\n")
.expect("test operation should succeed");
set_branch(&git_dir, "main", &c);
let selection = RevisionSelection::from_specs([format!("{a}..")])
.expect("test operation should succeed");
let resolved = selection
.resolve(&git_dir, format, &db)
.expect("test operation should succeed");
assert_eq!(resolved.starts, vec![c.clone()]);
assert_eq!(resolved.excluded, oid_set([root, a]));
assert_oid_set(
resolved
.selected_commit_oids(&git_dir, format, &db, false)
.expect("test operation should succeed"),
[c],
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn revision_selection_resolves_symmetric_range() {
let git_dir = temp_git_dir();
let format = ObjectFormat::Sha1;
let (db, all) = build_history(&git_dir, format);
let root = all[0].clone();
let a = all[1].clone();
let b = all[2].clone();
let selection = RevisionSelection::from_specs([format!("{a}...{b}")])
.expect("test operation should succeed");
let resolved = selection
.resolve(&git_dir, format, &db)
.expect("test operation should succeed");
assert_eq!(resolved.starts, vec![a, b]);
assert_eq!(resolved.excluded, oid_set([root]));
assert_oid_set(
resolved
.selected_commit_oids(&git_dir, format, &db, false)
.expect("test operation should succeed"),
[a, b],
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn revision_selection_resolves_caret_exclude() {
let git_dir = temp_git_dir();
let format = ObjectFormat::Sha1;
let (db, all) = build_history(&git_dir, format);
let root = all[0].clone();
let a = all[1].clone();
let selection = RevisionSelection::from_specs([format!("^{a}")])
.expect("test operation should succeed");
let resolved = selection
.resolve(&git_dir, format, &db)
.expect("test operation should succeed");
assert!(resolved.starts.is_empty());
assert_eq!(resolved.excluded, oid_set([root, a]));
assert!(
resolved
.selected_commit_oids(&git_dir, format, &db, false)
.expect("test operation should succeed")
.is_empty()
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn revision_selection_resolves_bare_include() {
let git_dir = temp_git_dir();
let format = ObjectFormat::Sha1;
let (db, all) = build_history(&git_dir, format);
let root = all[0].clone();
let a = all[1].clone();
let c = all[3].clone();
let selection =
RevisionSelection::from_specs([c.to_hex()]).expect("test operation should succeed");
let resolved = selection
.resolve(&git_dir, format, &db)
.expect("test operation should succeed");
assert_eq!(resolved.starts, vec![c.clone()]);
assert!(resolved.excluded.is_empty());
assert_oid_set(
resolved
.selected_commit_oids(&git_dir, format, &db, false)
.expect("test operation should succeed"),
[root, a, c],
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn merge_bases_finds_common_ancestor() {
let git_dir = temp_git_dir();
let mut db = ObjectDatabase::new(ObjectFormat::Sha1);
let tree = ObjectId::from_hex(
ObjectFormat::Sha1,
"4b825dc642cb6eb9a060e54bf8d69288fbee4904",
)
.expect("test operation should succeed");
let base = write_test_commit(&mut db, tree, Vec::new(), b"base\n");
let left = write_test_commit(&mut db, tree, vec![base], b"left\n");
let right = write_test_commit(&mut db, tree, vec![base], b"right\n");
assert_eq!(
merge_bases(&git_dir, ObjectFormat::Sha1, &db, &left, &right)
.expect("test operation should succeed"),
vec![base]
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn merge_bases_drop_common_ancestors_of_better_common_ancestors() {
let git_dir = temp_git_dir();
let mut db = ObjectDatabase::new(ObjectFormat::Sha1);
let tree = ObjectId::from_hex(
ObjectFormat::Sha1,
"4b825dc642cb6eb9a060e54bf8d69288fbee4904",
)
.expect("test operation should succeed");
let e = write_test_commit(&mut db, tree, Vec::new(), b"E\n");
let d = write_test_commit(&mut db, tree, vec![e], b"D\n");
let f = write_test_commit(&mut db, tree, vec![e], b"F\n");
let c = write_test_commit(&mut db, tree, vec![d], b"C\n");
let b = write_test_commit(&mut db, tree, vec![c], b"B\n");
let a = write_test_commit(&mut db, tree, vec![b], b"A\n");
let g = write_test_commit(&mut db, tree, vec![b, e], b"G\n");
let h = write_test_commit(&mut db, tree, vec![a, f], b"H\n");
assert_eq!(
merge_bases(&git_dir, ObjectFormat::Sha1, &db, &g, &h)
.expect("test operation should succeed"),
vec![b]
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn resolve_bare_at_is_head() {
let git_dir = temp_git_dir();
let oid = test_oid(0xaa);
fs::write(git_dir.join("HEAD"), b"ref: refs/heads/main\n")
.expect("test operation should succeed");
set_branch(&git_dir, "main", &oid);
assert_eq!(
resolve_revision(&git_dir, ObjectFormat::Sha1, "@")
.expect("test operation should succeed"),
oid
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn resolve_head_reflog_nth() {
let git_dir = temp_git_dir();
let c0 = test_oid(0x10);
let c1 = test_oid(0x11);
let c2 = test_oid(0x12);
fs::write(git_dir.join("HEAD"), b"ref: refs/heads/main\n")
.expect("test operation should succeed");
set_branch(&git_dir, "main", &c2);
write_head_reflog(
&git_dir,
&[
(&zero_oid(), &c0, "commit (initial): c0"),
(&c0, &c1, "commit: c1"),
(&c1, &c2, "commit: c2"),
],
);
write_branch_reflog(
&git_dir,
"main",
&[
(&zero_oid(), &c0, "commit (initial): c0"),
(&c0, &c1, "commit: c1"),
(&c1, &c2, "commit: c2"),
],
);
assert_eq!(
resolve_revision(&git_dir, ObjectFormat::Sha1, "@{0}")
.expect("test operation should succeed"),
c2
);
assert_eq!(
resolve_revision(&git_dir, ObjectFormat::Sha1, "HEAD@{1}")
.expect("test operation should succeed"),
c1
);
assert_eq!(
resolve_revision(&git_dir, ObjectFormat::Sha1, "@{2}")
.expect("test operation should succeed"),
c0
);
let err = resolve_revision(&git_dir, ObjectFormat::Sha1, "@{5}")
.expect_err("test operation should fail");
assert!(
matches!(&err, GitError::NotFound(kind) if kind.to_string().contains("only has 3 entries")),
"unexpected error: {err:?}"
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn resolve_branch_reflog_nth() {
let git_dir = temp_git_dir();
let old = test_oid(0x20);
let new = test_oid(0x21);
set_branch(&git_dir, "topic", &new);
write_branch_reflog(
&git_dir,
"topic",
&[
(&zero_oid(), &old, "branch: Created"),
(&old, &new, "commit: work"),
],
);
assert_eq!(
resolve_revision(&git_dir, ObjectFormat::Sha1, "topic@{0}")
.expect("test operation should succeed"),
new
);
assert_eq!(
resolve_revision(&git_dir, ObjectFormat::Sha1, "topic@{1}")
.expect("test operation should succeed"),
old
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn resolve_upstream_via_branch_config() {
let git_dir = temp_git_dir();
let tip = test_oid(0x30);
fs::write(git_dir.join("HEAD"), b"ref: refs/heads/main\n")
.expect("test operation should succeed");
set_branch(&git_dir, "main", &tip);
set_ref(&git_dir, "refs/remotes/origin/main", &tip);
fs::write(
git_dir.join("config"),
b"[branch \"main\"]\n\tremote = origin\n\tmerge = refs/heads/main\n",
)
.expect("test operation should succeed");
for spec in ["@{u}", "@{upstream}", "main@{upstream}"] {
assert_eq!(
resolve_revision(&git_dir, ObjectFormat::Sha1, spec)
.expect("test operation should succeed"),
tip,
"spec {spec}"
);
}
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn resolve_push_falls_back_to_upstream_then_uses_push_remote() {
let git_dir = temp_git_dir();
let up = test_oid(0x40);
let pushed = test_oid(0x41);
fs::write(git_dir.join("HEAD"), b"ref: refs/heads/main\n")
.expect("test operation should succeed");
set_branch(&git_dir, "main", &up);
set_ref(&git_dir, "refs/remotes/origin/main", &up);
fs::write(
git_dir.join("config"),
b"[branch \"main\"]\n\tremote = origin\n\tmerge = refs/heads/main\n",
)
.expect("test operation should succeed");
assert_eq!(
resolve_revision(&git_dir, ObjectFormat::Sha1, "@{push}")
.expect("test operation should succeed"),
up
);
set_ref(&git_dir, "refs/remotes/fork/main", &pushed);
fs::write(
git_dir.join("config"),
b"[push]\n\tdefault = current\n[branch \"main\"]\n\tremote = origin\n\tpushRemote = fork\n\tmerge = refs/heads/main\n",
)
.expect("test operation should succeed");
assert_eq!(
resolve_revision(&git_dir, ObjectFormat::Sha1, "@{push}")
.expect("test operation should succeed"),
pushed
);
assert_eq!(
resolve_revision(&git_dir, ObjectFormat::Sha1, "@{u}")
.expect("test operation should succeed"),
up
);
fs::write(
git_dir.join("config"),
b"[branch \"main\"]\n\tremote = origin\n\tpushRemote = fork\n\tmerge = refs/heads/main\n",
)
.expect("test operation should succeed");
let err = resolve_revision(&git_dir, ObjectFormat::Sha1, "@{push}")
.expect_err("triangular simple push must not resolve");
assert!(
matches!(&err, GitError::NotFound(kind) if kind.to_string().contains("simple")),
"unexpected error: {err:?}"
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn resolve_previous_checkout_branch() {
let git_dir = temp_git_dir();
let main_tip = test_oid(0x50);
let feature_tip = test_oid(0x51);
fs::write(git_dir.join("HEAD"), b"ref: refs/heads/feature\n")
.expect("test operation should succeed");
set_branch(&git_dir, "main", &main_tip);
set_branch(&git_dir, "feature", &feature_tip);
write_head_reflog(
&git_dir,
&[
(
&feature_tip,
&feature_tip,
"checkout: moving from main to feature",
),
(
&feature_tip,
&main_tip,
"checkout: moving from feature to main",
),
(
&main_tip,
&feature_tip,
"checkout: moving from main to feature",
),
],
);
assert_eq!(
resolve_revision(&git_dir, ObjectFormat::Sha1, "@{-1}")
.expect("test operation should succeed"),
main_tip
);
assert_eq!(
resolve_revision(&git_dir, ObjectFormat::Sha1, "@{-2}")
.expect("test operation should succeed"),
feature_tip
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn empty_base_reflog_uses_current_branch_not_head() {
let git_dir = temp_git_dir();
let old_one = test_oid(0x52);
let old_two = test_oid(0x53);
let new_two = test_oid(0x54);
fs::write(git_dir.join("HEAD"), b"ref: refs/heads/old-branch\n")
.expect("test operation should succeed");
set_branch(&git_dir, "old-branch", &old_two);
write_branch_reflog(
&git_dir,
"old-branch",
&[
(&zero_oid(), &old_one, "commit (initial): old-one"),
(&old_one, &old_two, "commit: old-two"),
],
);
write_head_reflog(
&git_dir,
&[
(
&old_two,
&new_two,
"checkout: moving from old-branch to new-branch",
),
(
&new_two,
&old_two,
"checkout: moving from new-branch to old-branch",
),
],
);
assert_eq!(
resolve_revision(&git_dir, ObjectFormat::Sha1, "@{1}")
.expect("test operation should succeed"),
old_one
);
assert_eq!(
resolve_revision(&git_dir, ObjectFormat::Sha1, "HEAD@{1}")
.expect("test operation should succeed"),
new_two
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn reflog_nth_requires_reflog_but_uses_oldest_fallback() {
let git_dir = temp_git_dir();
let base = test_oid(0x55);
let tip = test_oid(0x56);
set_branch(&git_dir, "newbranch", &tip);
assert!(
resolve_revision(&git_dir, ObjectFormat::Sha1, "newbranch@{0}").is_err(),
"branch without reflog must not resolve @{{0}}"
);
write_branch_reflog(&git_dir, "newbranch", &[(&base, &tip, "commit: tip")]);
assert_eq!(
resolve_revision(&git_dir, ObjectFormat::Sha1, "newbranch@{1}")
.expect("test operation should succeed"),
base
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn prior_checkout_and_head_alias_compose_with_at_marks() {
let git_dir = temp_git_dir();
let main_tip = test_oid(0x57);
let old_one = test_oid(0x58);
let old_two = test_oid(0x59);
let new_tip = test_oid(0x5a);
fs::write(git_dir.join("HEAD"), b"ref: refs/heads/new-branch\n")
.expect("test operation should succeed");
set_branch(&git_dir, "main", &main_tip);
set_branch(&git_dir, "old-branch", &old_two);
set_branch(&git_dir, "new-branch", &new_tip);
write_branch_reflog(
&git_dir,
"old-branch",
&[
(&zero_oid(), &old_one, "commit (initial): old-one"),
(&old_one, &old_two, "commit: old-two"),
],
);
write_head_reflog(
&git_dir,
&[(
&old_two,
&new_tip,
"checkout: moving from old-branch to new-branch",
)],
);
fs::write(
git_dir.join("config"),
b"[branch \"old-branch\"]\n\tremote = .\n\tmerge = refs/heads/main\n[branch \"new-branch\"]\n\tremote = .\n\tmerge = refs/heads/main\n",
)
.expect("test operation should succeed");
assert_eq!(
resolve_revision_symbolic_full_name(&git_dir, ObjectFormat::Sha1, "@{-1}")
.expect("test operation should succeed"),
Some("refs/heads/old-branch".to_string())
);
assert_eq!(
resolve_revision(&git_dir, ObjectFormat::Sha1, "@{-1}@{0}")
.expect("test operation should succeed"),
old_two
);
assert_eq!(
resolve_revision(&git_dir, ObjectFormat::Sha1, "@{-1}@{1}")
.expect("test operation should succeed"),
old_one
);
assert_eq!(
resolve_revision_symbolic_full_name(&git_dir, ObjectFormat::Sha1, "HEAD@{u}")
.expect("test operation should succeed"),
Some("refs/heads/main".to_string())
);
assert_eq!(
resolve_revision_symbolic_full_name(&git_dir, ObjectFormat::Sha1, "@@{u}")
.expect("test operation should succeed"),
Some("refs/heads/main".to_string())
);
assert_eq!(
resolve_revision_symbolic_full_name(&git_dir, ObjectFormat::Sha1, "@{-1}@{u}")
.expect("test operation should succeed"),
Some("refs/heads/main".to_string())
);
let nested = resolve_revision(&git_dir, ObjectFormat::Sha1, "@{0}@{0}")
.expect_err("test operation should fail");
assert!(
matches!(&nested, GitError::InvalidFormat(_)),
"unexpected error: {nested:?}"
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn at_selector_composes_with_parent_suffix() {
let git_dir = temp_git_dir();
let mut db = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha1);
let tree = db
.write_object(EncodedObject::new(ObjectType::Tree, Vec::new()))
.expect("test operation should succeed");
let parent = write_dated_commit(&mut db, tree, Vec::new(), b"parent\n", 1000);
let child = write_dated_commit(&mut db, tree, vec![parent], b"child\n", 2000);
fs::write(git_dir.join("HEAD"), b"ref: refs/heads/main\n")
.expect("test operation should succeed");
set_branch(&git_dir, "main", &child);
write_head_reflog(
&git_dir,
&[
(&zero_oid(), &parent, "commit (initial): parent"),
(&parent, &child, "commit: child"),
],
);
write_branch_reflog(
&git_dir,
"main",
&[
(&zero_oid(), &parent, "commit (initial): parent"),
(&parent, &child, "commit: child"),
],
);
assert_eq!(
resolve_revision(&git_dir, ObjectFormat::Sha1, "@{0}")
.expect("test operation should succeed"),
child
);
assert_eq!(
resolve_revision(&git_dir, ObjectFormat::Sha1, "@{0}^")
.expect("test operation should succeed"),
parent
);
assert_eq!(
resolve_revision(&git_dir, ObjectFormat::Sha1, "HEAD@{0}~1")
.expect("test operation should succeed"),
parent
);
assert_eq!(
resolve_revision(&git_dir, ObjectFormat::Sha1, "HEAD@{0}^{tree}")
.expect("test operation should succeed"),
tree
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn resolve_at_selector_rejects_unsupported_and_malformed() {
let git_dir = temp_git_dir();
fs::write(git_dir.join("HEAD"), b"ref: refs/heads/main\n")
.expect("test operation should succeed");
set_branch(&git_dir, "main", &test_oid(0x60));
let unsupported = resolve_revision(&git_dir, ObjectFormat::Sha1, "@{yesterday}")
.expect_err("test operation should fail");
assert!(
matches!(&unsupported, GitError::Unsupported(_)),
"unexpected error: {unsupported:?}"
);
let bad_base = resolve_revision(&git_dir, ObjectFormat::Sha1, "main@{-1}")
.expect_err("test operation should fail");
assert!(
matches!(&bad_base, GitError::InvalidFormat(_)),
"unexpected error: {bad_base:?}"
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
fn test_oid(byte: u8) -> ObjectId {
ObjectId::from_hex(ObjectFormat::Sha1, &format!("{byte:02x}").repeat(20))
.expect("test operation should succeed")
}
fn zero_oid() -> ObjectId {
ObjectId::from_hex(ObjectFormat::Sha1, &"0".repeat(40))
.expect("test operation should succeed")
}
fn oid_set(oids: impl IntoIterator<Item = ObjectId>) -> HashSet<ObjectId> {
oids.into_iter().collect()
}
fn assert_oid_set(
actual: impl IntoIterator<Item = ObjectId>,
expected: impl IntoIterator<Item = ObjectId>,
) {
assert_eq!(oid_set(actual), oid_set(expected));
}
struct SetupRevisionsFixture {
git_dir: PathBuf,
worktree: PathBuf,
db: FileObjectDatabase,
base: ObjectId,
tip: ObjectId,
left: ObjectId,
right: ObjectId,
side: ObjectId,
skipped: ObjectId,
}
fn setup_revisions_fixture() -> SetupRevisionsFixture {
let git_dir = temp_git_dir();
let worktree = git_dir.with_extension("worktree");
fs::create_dir_all(&worktree).expect("test operation should succeed");
fs::write(git_dir.join("HEAD"), b"ref: refs/heads/main\n")
.expect("test operation should succeed");
let mut db = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha1);
let tree = write_tree(&mut db, &[]);
let base = write_test_commit(&mut db, tree, Vec::new(), b"base\n");
let tip = write_test_commit(&mut db, tree, vec![base], b"tip\n");
let left = write_test_commit(&mut db, tree, vec![base], b"left\n");
let right = write_test_commit(&mut db, tree, vec![base], b"right\n");
let side = write_test_commit(&mut db, tree, Vec::new(), b"side\n");
let skipped = write_test_commit(&mut db, tree, Vec::new(), b"skipped\n");
set_branch(&git_dir, "main", &tip);
set_branch(&git_dir, "base", &base);
set_branch(&git_dir, "left", &left);
set_branch(&git_dir, "right", &right);
set_branch(&git_dir, "side", &side);
set_ref(&git_dir, "refs/heads/skip/topic", &skipped);
SetupRevisionsFixture {
git_dir,
worktree,
db,
base,
tip,
left,
right,
side,
skipped,
}
}
fn run_setup<const N: usize>(
fixture: &SetupRevisionsFixture,
args: [&str; N],
) -> Result<SetupRevisions> {
let args = args.iter().map(|arg| arg.to_string()).collect::<Vec<_>>();
setup_revisions(
&args,
&RevisionSetupContext {
git_dir: &fixture.git_dir,
worktree_root: Some(&fixture.worktree),
cwd: &fixture.worktree,
format: ObjectFormat::Sha1,
reader: &fixture.db,
config: None,
},
)
}
fn set_branch(git_dir: &Path, branch: &str, oid: &ObjectId) {
set_ref(git_dir, &format!("refs/heads/{branch}"), oid);
}
fn set_ref(git_dir: &Path, name: &str, oid: &ObjectId) {
let refs = FileRefStore::new(git_dir, ObjectFormat::Sha1);
let mut tx = refs.transaction();
tx.update(RefUpdate {
name: name.to_string(),
expected: None,
new: RefTarget::Direct(*oid),
reflog: None,
});
tx.commit().expect("test operation should succeed");
}
fn write_head_reflog(git_dir: &Path, entries: &[(&ObjectId, &ObjectId, &str)]) {
write_reflog_for(git_dir, "HEAD", entries);
}
fn write_branch_reflog(git_dir: &Path, branch: &str, entries: &[(&ObjectId, &ObjectId, &str)]) {
write_reflog_for(git_dir, &format!("refs/heads/{branch}"), entries);
}
fn write_reflog_for(git_dir: &Path, name: &str, entries: &[(&ObjectId, &ObjectId, &str)]) {
let refs = FileRefStore::new(git_dir, ObjectFormat::Sha1);
let entries: Vec<ReflogEntry> = entries
.iter()
.map(|(old, new, message)| ReflogEntry {
old_oid: (*old).clone(),
new_oid: (*new).clone(),
committer: b"Example User <example@example.invalid> 1000 +0000".to_vec(),
message: message.as_bytes().to_vec(),
})
.collect();
refs.write_reflog(name, &entries)
.expect("test operation should succeed");
}
fn write_test_commit<W: ObjectWriter>(
db: &mut W,
tree: ObjectId,
parents: Vec<ObjectId>,
message: &[u8],
) -> ObjectId {
let commit = Commit {
tree,
parents,
author: b"Example User <example@example.invalid> 0 +0000".to_vec(),
committer: b"Example User <example@example.invalid> 0 +0000".to_vec(),
encoding: None,
message: message.to_vec(),
};
db.write_object(EncodedObject::new(ObjectType::Commit, commit.write()))
.expect("test operation should succeed")
}
fn write_dated_commit<W: ObjectWriter>(
db: &mut W,
tree: ObjectId,
parents: Vec<ObjectId>,
message: &[u8],
when: i64,
) -> ObjectId {
let ident = format!("Example User <example@example.invalid> {when} +0000");
let commit = Commit {
tree,
parents,
author: ident.clone().into_bytes(),
committer: ident.into_bytes(),
encoding: None,
message: message.to_vec(),
};
db.write_object(EncodedObject::new(ObjectType::Commit, commit.write()))
.expect("test operation should succeed")
}
fn write_tree<W: ObjectWriter>(db: &mut W, entries: &[(u32, &[u8], &ObjectId)]) -> ObjectId {
let tree = sley_object::Tree {
entries: entries
.iter()
.map(|(mode, name, oid)| sley_object::TreeEntry {
mode: *mode,
name: BString::from(*name),
oid: (*oid).clone(),
})
.collect(),
};
db.write_object(EncodedObject::new(ObjectType::Tree, tree.write()))
.expect("test operation should succeed")
}
fn test_index_entry(path: &[u8], oid: &ObjectId, stage: u16) -> sley_index::IndexEntry {
sley_index::IndexEntry {
ctime_seconds: 0,
ctime_nanoseconds: 0,
mtime_seconds: 0,
mtime_nanoseconds: 0,
dev: 0,
ino: 0,
mode: 0o100644,
uid: 0,
gid: 0,
size: 0,
oid: *oid,
flags: (stage & 0x3) << 12,
flags_extended: 0,
path: BString::from(path),
}
}
fn temp_git_dir() -> std::path::PathBuf {
let path = std::env::temp_dir().join(format!(
"sley-rev-{}-{}",
std::process::id(),
TEMP_COUNTER.fetch_add(1, Ordering::Relaxed)
));
fs::create_dir_all(&path).expect("test operation should succeed");
path
}
struct PanicReader;
impl ObjectReader for PanicReader {
fn read_object(&self, oid: &ObjectId) -> Result<std::sync::Arc<EncodedObject>> {
Err(GitError::not_found(format!(
"object reader must not be used for {oid}; graph should cover it"
)))
}
}
struct CountingReader<'a> {
inner: &'a FileObjectDatabase,
reads: Cell<usize>,
}
impl<'a> CountingReader<'a> {
fn new(inner: &'a FileObjectDatabase) -> Self {
Self {
inner,
reads: Cell::new(0),
}
}
}
impl ObjectReader for CountingReader<'_> {
fn read_object(&self, oid: &ObjectId) -> Result<std::sync::Arc<EncodedObject>> {
self.reads.set(self.reads.get() + 1);
self.inner.read_object(oid)
}
}
fn generation_numbers(parents: &HashMap<ObjectId, Vec<ObjectId>>) -> HashMap<ObjectId, u32> {
let mut generations: HashMap<ObjectId, u32> = HashMap::new();
loop {
let mut changed = false;
for (oid, oid_parents) in parents {
let candidate = oid_parents
.iter()
.map(|parent| generations.get(parent).copied().unwrap_or(0))
.max()
.unwrap_or(0)
+ 1;
if generations.get(oid).copied() != Some(candidate) {
let current = generations.get(oid).copied().unwrap_or(0);
if candidate > current {
generations.insert(*oid, candidate);
changed = true;
}
}
}
if !changed {
break;
}
}
generations
}
fn write_commit_graph_file(
git_dir: &Path,
format: ObjectFormat,
reader: &impl ObjectReader,
commits: &[ObjectId],
) {
let mut parents_map: HashMap<ObjectId, Vec<ObjectId>> = HashMap::new();
for oid in commits {
parents_map.insert(
*oid,
commit_parents(reader, format, oid).expect("test operation should succeed"),
);
}
let generations = generation_numbers(&parents_map);
let entries: Vec<sley_formats::CommitGraphWriteEntry> = commits
.iter()
.map(|oid| {
let object = reader
.read_object(oid)
.expect("test operation should succeed");
let commit =
Commit::parse_ref(format, &object.body).expect("test operation should succeed");
let commit_time =
commit_committer_time(commit.committer).unwrap_or(0).max(0) as u64;
sley_formats::CommitGraphWriteEntry {
oid: *oid,
tree: commit.tree,
parents: commit.parents,
generation: generations.get(oid).copied().unwrap_or(1),
commit_time,
bloom_filter: None,
}
})
.collect();
let bytes = CommitGraph::write(format, &entries).expect("test operation should succeed");
let info = git_dir.join("objects").join("info");
fs::create_dir_all(&info).expect("test operation should succeed");
fs::write(info.join("commit-graph"), bytes).expect("test operation should succeed");
}
fn remove_commit_graph(git_dir: &Path) {
let path = git_dir.join("objects").join("info").join("commit-graph");
if path.exists() {
fs::remove_file(path).expect("test operation should succeed");
}
}
fn build_history(git_dir: &Path, format: ObjectFormat) -> (FileObjectDatabase, Vec<ObjectId>) {
let mut db = FileObjectDatabase::from_git_dir(git_dir, format);
let tree = db
.write_object(EncodedObject::new(ObjectType::Tree, Vec::new()))
.expect("test operation should succeed");
let mut t = 1000i64;
let mut commit = |db: &mut FileObjectDatabase, parents: Vec<ObjectId>, msg: &[u8]| {
t += 1;
write_dated_commit(db, tree, parents, msg, t)
};
let root = commit(&mut db, vec![], b"root\n");
let a = commit(&mut db, vec![root], b"a\n");
let b = commit(&mut db, vec![root], b"b\n");
let c = commit(&mut db, vec![a], b"c\n");
let d = commit(&mut db, vec![b], b"d\n");
let e = commit(&mut db, vec![b], b"e\n");
let m1 = commit(&mut db, vec![c.clone(), d.clone()], b"m1\n");
let f = commit(&mut db, vec![d.clone(), e.clone()], b"f\n");
let g = commit(&mut db, vec![f.clone()], b"g\n");
let oct = commit(&mut db, vec![m1.clone(), g.clone(), f.clone()], b"oct\n");
let x1 = commit(&mut db, vec![a, b], b"x1\n");
let x2 = commit(&mut db, vec![b, a], b"x2\n");
let all = vec![root, a, b, c, d, e, m1, f, g, oct, x1, x2];
(db, all)
}
#[test]
fn graph_backed_walks_match_object_only_walks() {
let git_dir = temp_git_dir();
let format = ObjectFormat::Sha1;
let (db, all) = build_history(&git_dir, format);
remove_commit_graph(&git_dir);
let baseline = collect_walk_results(&git_dir, format, &db, &all);
write_commit_graph_file(&git_dir, format, &db, &all);
let with_graph = collect_walk_results(&git_dir, format, &db, &all);
assert_eq!(
baseline, with_graph,
"graph-backed walk diverged from object-only walk"
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
type WalkResult = (String, String, bool, Vec<String>, Vec<String>, Vec<String>);
fn collect_walk_results(
git_dir: &Path,
format: ObjectFormat,
reader: &impl ObjectReader,
all: &[ObjectId],
) -> Vec<WalkResult> {
let mut out = Vec::new();
for left in all {
for right in all {
let anc = is_ancestor(git_dir, format, reader, left, right)
.expect("test operation should succeed");
let mut bases: Vec<String> = merge_bases(git_dir, format, reader, left, right)
.expect("test operation should succeed")
.iter()
.map(|oid| oid.to_hex())
.collect();
bases.sort();
let asym = RevisionRange::Asymmetric {
start: left.to_hex(),
end: right.to_hex(),
};
let mut asym_set: Vec<String> =
resolve_revision_range(git_dir, format, reader, &asym)
.expect("test operation should succeed")
.iter()
.map(|oid| oid.to_hex())
.collect();
asym_set.sort();
let sym = RevisionRange::Symmetric {
left: left.to_hex(),
right: right.to_hex(),
};
let mut sym_set: Vec<String> =
resolve_revision_range(git_dir, format, reader, &sym)
.expect("test operation should succeed")
.iter()
.map(|oid| oid.to_hex())
.collect();
sym_set.sort();
out.push((left.to_hex(), right.to_hex(), anc, bases, asym_set, sym_set));
}
}
out
}
#[test]
fn graph_backed_merge_base_handles_octopus_and_criss_cross() {
let git_dir = temp_git_dir();
let format = ObjectFormat::Sha1;
let (db, all) = build_history(&git_dir, format);
let (a, b) = (all[1].clone(), all[2].clone());
let (m1, oct) = (all[6].clone(), all[9].clone());
let (x1, x2) = (all[10].clone(), all[11].clone());
write_commit_graph_file(&git_dir, format, &db, &all);
let mut xbases =
merge_bases(&git_dir, format, &db, &x1, &x2).expect("test operation should succeed");
xbases.sort_by_key(|oid| oid.to_hex());
let mut expected = vec![a, b];
expected.sort_by_key(|oid| oid.to_hex());
assert_eq!(xbases, expected, "criss-cross must yield two merge bases");
assert!(
is_ancestor(&git_dir, format, &db, &m1, &oct).expect("test operation should succeed")
);
assert_eq!(
merge_bases(&git_dir, format, &db, &m1, &oct).expect("test operation should succeed"),
vec![m1.clone()]
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn graph_backed_queries_avoid_object_reads() {
let git_dir = temp_git_dir();
let format = ObjectFormat::Sha1;
let (db, all) = build_history(&git_dir, format);
write_commit_graph_file(&git_dir, format, &db, &all);
let (root, a, oct, x1, x2) = (
all[0].clone(),
all[1].clone(),
all[9].clone(),
all[10].clone(),
all[11].clone(),
);
assert!(
is_ancestor(&git_dir, format, &PanicReader, &root, &oct)
.expect("test operation should succeed")
);
assert!(
!is_ancestor(&git_dir, format, &PanicReader, &oct, &root)
.expect("test operation should succeed")
);
assert!(
is_ancestor(&git_dir, format, &PanicReader, &a, &oct)
.expect("test operation should succeed")
);
let bases = merge_bases(&git_dir, format, &PanicReader, &x1, &x2)
.expect("test operation should succeed");
assert_eq!(bases.len(), 2, "criss-cross bases via graph only");
let range = RevisionRange::Asymmetric {
start: a.to_hex(),
end: oct.to_hex(),
};
let mut included: Vec<String> = resolve_revision_range(&git_dir, format, &db, &range)
.expect("test operation should succeed")
.iter()
.map(|oid| oid.to_hex())
.collect();
included.sort();
assert!(included.contains(&oct.to_hex()));
assert!(
!included.contains(&root.to_hex()),
"root is an ancestor of A, excluded"
);
remove_commit_graph(&git_dir);
let object_bases =
merge_bases(&git_dir, format, &db, &x1, &x2).expect("test operation should succeed");
let mut object_range: Vec<String> = resolve_revision_range(&git_dir, format, &db, &range)
.expect("test operation should succeed")
.iter()
.map(|oid| oid.to_hex())
.collect();
object_range.sort();
write_commit_graph_file(&git_dir, format, &db, &all);
let graph_bases = merge_bases(&git_dir, format, &PanicReader, &x1, &x2)
.expect("test operation should succeed");
assert_eq!(object_bases, graph_bases);
assert_eq!(object_range, included, "range walk diverged with graph");
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn graph_backed_parent_suffix_matches_object_walk() {
let git_dir = temp_git_dir();
let format = ObjectFormat::Sha1;
let (db, all) = build_history(&git_dir, format);
let oct = all[9].clone();
let (m1, g, f) = (all[6].clone(), all[8].clone(), all[7].clone());
remove_commit_graph(&git_dir);
let base_p1 = resolve_revision_with_reader(&git_dir, format, &db, &format!("{oct}^1"))
.expect("test operation should succeed");
let base_p2 = resolve_revision_with_reader(&git_dir, format, &db, &format!("{oct}^2"))
.expect("test operation should succeed");
let base_p3 = resolve_revision_with_reader(&git_dir, format, &db, &format!("{oct}^3"))
.expect("test operation should succeed");
let base_first = resolve_revision_with_reader(&git_dir, format, &db, &format!("{oct}~1"))
.expect("test operation should succeed");
assert_eq!((&base_p1, &base_p2, &base_p3), (&m1, &g, &f));
assert_eq!(base_first, m1);
write_commit_graph_file(&git_dir, format, &db, &all);
assert_eq!(
resolve_revision_with_reader(&git_dir, format, &PanicReader, &format!("{oct}^2"))
.expect("test operation should succeed"),
base_p2
);
assert_eq!(
resolve_revision_with_reader(&git_dir, format, &PanicReader, &format!("{oct}~1"))
.expect("test operation should succeed"),
base_first
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn missing_or_unparseable_graph_falls_back_to_objects() {
let git_dir = temp_git_dir();
let format = ObjectFormat::Sha1;
let (db, all) = build_history(&git_dir, format);
let (a, oct) = (all[1].clone(), all[9].clone());
let object_answer =
is_ancestor(&git_dir, format, &db, &a, &oct).expect("test operation should succeed");
let info = git_dir.join("objects").join("info");
fs::create_dir_all(&info).expect("test operation should succeed");
fs::write(info.join("commit-graph"), b"not a real commit graph")
.expect("test operation should succeed");
assert_eq!(
is_ancestor(&git_dir, format, &db, &a, &oct).expect("test operation should succeed"),
object_answer
);
write_commit_graph_file(&git_dir, format, &db, &all[..3]);
assert_eq!(
is_ancestor(&git_dir, format, &db, &a, &oct).expect("test operation should succeed"),
object_answer
);
assert_eq!(
merge_bases(&git_dir, format, &db, &all[10], &all[11])
.expect("test operation should succeed"),
{
remove_commit_graph(&git_dir);
merge_bases(&git_dir, format, &db, &all[10], &all[11])
.expect("test operation should succeed")
}
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn commit_graph_chain_is_consulted() {
let git_dir = temp_git_dir();
let format = ObjectFormat::Sha1;
let mut db = FileObjectDatabase::from_git_dir(&git_dir, format);
let tree = db
.write_object(EncodedObject::new(ObjectType::Tree, Vec::new()))
.expect("test operation should succeed");
let root = write_dated_commit(&mut db, tree, vec![], b"root\n", 1000);
let mid = write_dated_commit(&mut db, tree, vec![root], b"mid\n", 1001);
let tip = write_dated_commit(&mut db, tree, vec![mid.clone()], b"tip\n", 1002);
let commits = [root, mid.clone(), tip.clone()];
let parents_map: HashMap<ObjectId, Vec<ObjectId>> = commits
.iter()
.map(|oid| {
(
*oid,
commit_parents(&db, format, oid).expect("test operation should succeed"),
)
})
.collect();
let generations = generation_numbers(&parents_map);
let entries: Vec<sley_formats::CommitGraphWriteEntry> = commits
.iter()
.map(|oid| sley_formats::CommitGraphWriteEntry {
oid: *oid,
tree,
parents: parents_map[oid].clone(),
generation: generations[oid],
commit_time: 0,
bloom_filter: None,
})
.collect();
let bytes = CommitGraph::write(format, &entries).expect("test operation should succeed");
let graphs = git_dir.join("objects").join("info").join("commit-graphs");
fs::create_dir_all(&graphs).expect("test operation should succeed");
let hash = sley_core::digest_bytes(format, &bytes)
.expect("test operation should succeed")
.to_hex();
fs::write(graphs.join(format!("graph-{hash}.graph")), &bytes)
.expect("test operation should succeed");
fs::write(graphs.join("commit-graph-chain"), format!("{hash}\n"))
.expect("test operation should succeed");
assert!(
!git_dir
.join("objects")
.join("info")
.join("commit-graph")
.exists()
);
assert!(
is_ancestor(&git_dir, format, &PanicReader, &root, &tip)
.expect("test operation should succeed")
);
assert_eq!(
merge_bases(&git_dir, format, &PanicReader, &mid, &tip)
.expect("test operation should succeed"),
vec![mid.clone()]
);
let linked = git_dir.join("worktrees").join("linked");
fs::create_dir_all(&linked).expect("test operation should succeed");
fs::write(linked.join("commondir"), "../..\n").expect("test operation should succeed");
assert!(
is_ancestor(&linked, format, &PanicReader, &root, &tip)
.expect("test operation should succeed")
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn count_commit_metadata_uses_partial_direct_commit_graph() {
let git_dir = temp_git_dir();
let format = ObjectFormat::Sha1;
let db = FileObjectDatabase::from_git_dir(&git_dir, format);
let commits = build_linear_history(&git_dir, 5);
write_commit_graph_file(&git_dir, format, &db, &commits[..3]);
let reader = CountingReader::new(&db);
let count = count_commit_metadata(&git_dir, format, &reader, [commits[4]], false)
.expect("count should succeed");
assert_eq!(count, 5);
assert_eq!(
reader.reads.get(),
2,
"only commits newer than the partial graph should be object-read"
);
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
#[test]
fn commit_graph_tree_oid_returns_tree_without_object_read() {
let git_dir = temp_git_dir();
let format = ObjectFormat::Sha1;
let db = FileObjectDatabase::from_git_dir(&git_dir, format);
let commits = build_linear_history(&git_dir, 3);
write_commit_graph_file(&git_dir, format, &db, &commits);
for oid in &commits {
let object = db.read_object(oid).expect("test operation should succeed");
let commit =
Commit::parse_ref(format, &object.body).expect("test operation should succeed");
assert_eq!(
commit_graph_tree_oid(&git_dir, format, oid)
.expect("test operation should succeed"),
Some(commit.tree)
);
}
fs::remove_dir_all(git_dir).expect("test operation should succeed");
}
fn test_commit_graph(format: ObjectFormat, parent: &ObjectId, child: &ObjectId) -> Vec<u8> {
let tree = ObjectId::from_hex(format, "4b825dc642cb6eb9a060e54bf8d69288fbee4904")
.expect("test operation should succeed");
let mut oidf = vec![0u8; 256 * 4];
let parent_first = parent.as_bytes()[0] as usize;
let child_first = child.as_bytes()[0] as usize;
for idx in 0..256 {
let count = u32::from(idx >= parent_first) + u32::from(idx >= child_first);
oidf[idx * 4..idx * 4 + 4].copy_from_slice(&count.to_be_bytes());
}
let mut oidl = Vec::new();
oidl.extend_from_slice(parent.as_bytes());
oidl.extend_from_slice(child.as_bytes());
let mut cdat = Vec::new();
cdat.extend_from_slice(&commit_graph_cdat_entry(
&tree,
0x7000_0000,
0x7000_0000,
1,
1,
));
cdat.extend_from_slice(&commit_graph_cdat_entry(&tree, 0, 0x7000_0000, 2, 2));
commit_graph_file(
format,
&[(*b"OIDF", oidf), (*b"OIDL", oidl), (*b"CDAT", cdat)],
)
}
fn commit_graph_cdat_entry(
tree: &ObjectId,
parent_one: u32,
parent_two: u32,
generation: u32,
commit_time: u64,
) -> Vec<u8> {
let mut out = Vec::new();
out.extend_from_slice(tree.as_bytes());
out.extend_from_slice(&parent_one.to_be_bytes());
out.extend_from_slice(&parent_two.to_be_bytes());
let high = (generation << 2) | ((commit_time >> 32) as u32 & 0x3);
out.extend_from_slice(&high.to_be_bytes());
out.extend_from_slice(&(commit_time as u32).to_be_bytes());
out
}
fn commit_graph_file(format: ObjectFormat, chunks: &[([u8; 4], Vec<u8>)]) -> Vec<u8> {
let lookup_len = (chunks.len() + 1) * 12;
let mut out = Vec::new();
out.extend_from_slice(b"CGPH");
out.push(1);
out.push(match format {
ObjectFormat::Sha1 => 1,
ObjectFormat::Sha256 => 2,
});
out.push(chunks.len() as u8);
out.push(0);
let mut offset = (8 + lookup_len) as u64;
for (id, data) in chunks {
out.extend_from_slice(id);
out.extend_from_slice(&offset.to_be_bytes());
offset += data.len() as u64;
}
out.extend_from_slice(&[0, 0, 0, 0]);
out.extend_from_slice(&offset.to_be_bytes());
for (_id, data) in chunks {
out.extend_from_slice(data);
}
let checksum =
sley_core::digest_bytes(format, &out).expect("test operation should succeed");
out.extend_from_slice(checksum.as_bytes());
out
}
fn build_linear_history(git_dir: &std::path::Path, n: usize) -> Vec<ObjectId> {
let mut db = FileObjectDatabase::from_git_dir(git_dir, ObjectFormat::Sha1);
let tree = db
.write_object(EncodedObject::new(ObjectType::Tree, Vec::new()))
.expect("write empty tree");
let mut oids = Vec::new();
let mut parents = Vec::new();
for i in 0..n {
let oid = write_dated_commit(
&mut db,
tree,
parents.clone(),
format!("c{i}\n").as_bytes(),
100 + i as i64,
);
parents = vec![oid];
oids.push(oid);
}
oids
}
fn walk_oids<R: ObjectReader>(walk: RevWalk<'_, R>) -> Vec<ObjectId> {
walk.collect_all()
.expect("walk succeeds")
.into_iter()
.map(|m| m.oid)
.collect()
}
#[test]
fn revwalk_commit_date_order_newest_first() {
let git_dir = temp_git_dir();
let db = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha1);
let oids = build_linear_history(&git_dir, 4); let tip = *oids.last().expect("tip");
let got = walk_oids(RevWalk::new(&git_dir, ObjectFormat::Sha1, &db, [tip]));
let mut expected = oids.clone();
expected.reverse(); assert_eq!(got, expected);
fs::remove_dir_all(git_dir).expect("cleanup");
}
#[test]
fn revwalk_max_count_limits_output() {
let git_dir = temp_git_dir();
let db = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha1);
let oids = build_linear_history(&git_dir, 5);
let tip = *oids.last().expect("tip");
let got =
walk_oids(RevWalk::new(&git_dir, ObjectFormat::Sha1, &db, [tip]).max_count(Some(2)));
assert_eq!(got, vec![oids[4], oids[3]]);
fs::remove_dir_all(git_dir).expect("cleanup");
}
#[test]
fn revwalk_skip_then_limit() {
let git_dir = temp_git_dir();
let db = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha1);
let oids = build_linear_history(&git_dir, 5);
let tip = *oids.last().expect("tip");
let got = walk_oids(
RevWalk::new(&git_dir, ObjectFormat::Sha1, &db, [tip])
.skip(1)
.max_count(Some(2)),
);
assert_eq!(got, vec![oids[3], oids[2]]);
fs::remove_dir_all(git_dir).expect("cleanup");
}
#[test]
fn revwalk_delegates_match_old_limited_walk() {
let git_dir = temp_git_dir();
let db = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha1);
let oids = build_linear_history(&git_dir, 6);
let tip = *oids.last().expect("tip");
let via_fn = walk_commit_metadata_date_ordered_limited(
&git_dir,
ObjectFormat::Sha1,
&db,
[tip],
false,
3,
)
.expect("limited walk")
.into_iter()
.map(|m| m.oid)
.collect::<Vec<_>>();
let via_walk = walk_oids(
RevWalk::new(&git_dir, ObjectFormat::Sha1, &db, [tip])
.order(RevWalkOrder::CommitDate)
.max_count(Some(3)),
);
assert_eq!(via_fn, via_walk);
fs::remove_dir_all(git_dir).expect("cleanup");
}
#[test]
fn revwalk_first_parent_follows_one_line() {
let git_dir = temp_git_dir();
let mut db = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha1);
let tree = db
.write_object(EncodedObject::new(ObjectType::Tree, Vec::new()))
.expect("tree");
let base = write_dated_commit(&mut db, tree, vec![], b"base\n", 100);
let side = write_dated_commit(&mut db, tree, vec![base], b"side\n", 110);
let main = write_dated_commit(&mut db, tree, vec![base], b"main\n", 120);
let merge = write_dated_commit(&mut db, tree, vec![main, side], b"merge\n", 130);
let first_parent =
walk_oids(RevWalk::new(&git_dir, ObjectFormat::Sha1, &db, [merge]).first_parent(true));
assert_eq!(first_parent, vec![merge, main, base]);
assert!(!first_parent.contains(&side));
fs::remove_dir_all(git_dir).expect("cleanup");
}
#[test]
fn revwalk_date_window_filters_and_prunes() {
let git_dir = temp_git_dir();
let db = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha1);
let oids = build_linear_history(&git_dir, 5); let tip = *oids.last().expect("tip");
let got = walk_oids(
RevWalk::new(&git_dir, ObjectFormat::Sha1, &db, [tip]).date_window(RevWalkDateWindow {
min_time: Some(102),
max_time: Some(103),
}),
);
assert_eq!(got, vec![oids[3], oids[2]]);
fs::remove_dir_all(git_dir).expect("cleanup");
}
#[test]
fn revwalk_pathspec_is_carried_but_not_pruning() {
let git_dir = temp_git_dir();
let db = FileObjectDatabase::from_git_dir(&git_dir, ObjectFormat::Sha1);
let oids = build_linear_history(&git_dir, 3);
let tip = *oids.last().expect("tip");
let spec = Pathspec::parse(
[b"does/not/exist".as_slice()],
PathspecMatchMagic::default(),
)
.expect("pathspec");
let walk = RevWalk::new(&git_dir, ObjectFormat::Sha1, &db, [tip]).pathspec(spec.clone());
assert_eq!(walk.pathspec_ref(), &spec);
let got = walk_oids(walk);
assert_eq!(got.len(), 3, "pathspec must not prune in STAGE-A");
fs::remove_dir_all(git_dir).expect("cleanup");
}
}