grit_lib/

reflog.rs

//! Reflog reading and management.
//!
//! The reflog records updates to refs.  Each ref's log is stored at
//! `<git-dir>/logs/<refname>` (e.g. `logs/HEAD`, `logs/refs/heads/main`).
//! Each line has the format:
//!
//! ```text
//! <old-sha> <new-sha> <name> <<email>> <timestamp> <timezone>\t<message>
//! ```

use std::collections::{HashMap, HashSet};
use std::fs;
use std::io;
use std::path::{Path, PathBuf};

use crate::config::ConfigSet;
use crate::diff::zero_oid;
use crate::error::{Error, Result};
use crate::merge_base;
use crate::objects::{parse_commit, parse_tree, ObjectId, ObjectKind};
use crate::refs::{self, reflog_file_path};
use crate::repo::Repository;
use crate::wildmatch::{wildmatch, WM_PATHNAME};

/// A single reflog entry.
#[derive(Debug, Clone)]
pub struct ReflogEntry {
    /// Previous object ID.
    pub old_oid: ObjectId,
    /// New object ID.
    pub new_oid: ObjectId,
    /// Identity string: `"Name <email> timestamp tz"`.
    pub identity: String,
    /// The log message.
    pub message: String,
}

/// Return the filesystem path for a ref's reflog.
///
/// Uses the same storage rules as [`refs::append_reflog`] (branch reflogs under the
/// repository common directory for linked worktrees).
pub fn reflog_path(git_dir: &Path, refname: &str) -> PathBuf {
    reflog_file_path(git_dir, refname)
}

/// Check whether a reflog exists for the given ref.
pub fn reflog_exists(git_dir: &Path, refname: &str) -> bool {
    if crate::reftable::is_reftable_repo(git_dir) {
        return crate::reftable::reftable_reflog_exists(git_dir, refname);
    }
    let path = reflog_path(git_dir, refname);
    path.is_file()
}

/// Read a reflog using Git's loose ref DWIM rules when the direct path is missing.
///
/// Tries `refname`, then `refs/<refname>`, then `refs/heads/<refname>` (when `refname` is not
/// already under `refs/`). Matches `read_complete_reflog` in Git's `reflog-walk.c`.
pub fn read_reflog_dwim(git_dir: &Path, refname: &str) -> Result<Vec<ReflogEntry>> {
    let mut entries = read_reflog(git_dir, refname)?;
    if !entries.is_empty() {
        return Ok(entries);
    }
    if !refname.starts_with("refs/") {
        entries = read_reflog(git_dir, &format!("refs/{refname}"))?;
        if !entries.is_empty() {
            return Ok(entries);
        }
        entries = read_reflog(git_dir, &format!("refs/heads/{refname}"))?;
    }
    Ok(entries)
}

/// Read all reflog entries for the given ref, in file order (oldest first).
///
/// Returns an empty vec if the reflog file does not exist.
pub fn read_reflog(git_dir: &Path, refname: &str) -> Result<Vec<ReflogEntry>> {
    if crate::reftable::is_reftable_repo(git_dir) {
        return crate::reftable::reftable_read_reflog(git_dir, refname);
    }
    let path = reflog_path(git_dir, refname);
    let content = match fs::read_to_string(&path) {
        Ok(c) => c,
        Err(e) if e.kind() == io::ErrorKind::NotFound => return Ok(Vec::new()),
        Err(e) => return Err(Error::Io(e)),
    };

    let mut entries = Vec::new();
    for line in content.lines() {
        if line.is_empty() {
            continue;
        }
        if let Some(entry) = parse_reflog_line(line) {
            entries.push(entry);
        }
    }
    Ok(entries)
}

/// Parse a single reflog line.
///
/// Format: `<old-hex> <new-hex> <identity>\t<message>`
fn parse_reflog_line(line: &str) -> Option<ReflogEntry> {
    // Split on tab first to separate identity from message
    let (before_tab, message) = if let Some(pos) = line.find('\t') {
        (&line[..pos], line[pos + 1..].to_string())
    } else {
        (line, String::new())
    };

    // The first 40 chars are old OID, then space, then 40 chars new OID, then space, then identity
    if before_tab.len() < 83 {
        // 40 + 1 + 40 + 1 + at least 1 char identity
        return None;
    }

    let old_hex = &before_tab[..40];
    let new_hex = &before_tab[41..81];
    let identity = before_tab[82..].to_string();

    let old_oid = old_hex.parse::<ObjectId>().ok()?;
    let new_oid = new_hex.parse::<ObjectId>().ok()?;

    Some(ReflogEntry {
        old_oid,
        new_oid,
        identity,
        message,
    })
}

/// Collect every non-null object ID mentioned in any file under `logs/` (recursive).
///
/// Used by `fsck` to validate reflog entries. Skips reftable-backed repos (no file logs).
pub fn all_reflog_oids(git_dir: &Path) -> Result<HashSet<ObjectId>> {
    if crate::reftable::is_reftable_repo(git_dir) {
        return Ok(HashSet::new());
    }
    let mut out = HashSet::new();
    let logs = git_dir.join("logs");
    if !logs.is_dir() {
        return Ok(out);
    }
    let z = zero_oid();
    walk_reflog_files(&logs, &mut out, &z)?;
    Ok(out)
}

fn walk_reflog_files(dir: &Path, out: &mut HashSet<ObjectId>, zero: &ObjectId) -> Result<()> {
    for entry in fs::read_dir(dir).map_err(Error::Io)? {
        let entry = entry.map_err(Error::Io)?;
        let path = entry.path();
        if path.is_dir() {
            walk_reflog_files(&path, out, zero)?;
        } else if path.is_file() {
            let content = fs::read_to_string(&path).map_err(Error::Io)?;
            for line in content.lines() {
                if let Some(e) = parse_reflog_line(line) {
                    if e.old_oid != *zero {
                        out.insert(e.old_oid);
                    }
                    if e.new_oid != *zero {
                        out.insert(e.new_oid);
                    }
                }
            }
        }
    }
    Ok(())
}

/// Delete specific reflog entries by index (0-based, newest-first order).
///
/// Rewrites the reflog file, omitting entries at the given indices.
pub fn delete_reflog_entries(git_dir: &Path, refname: &str, indices: &[usize]) -> Result<()> {
    let mut entries = read_reflog(git_dir, refname)?;
    if entries.is_empty() {
        return Ok(());
    }

    // Indices are in newest-first order (like show), so reverse the entries
    // to map indices correctly.
    entries.reverse();

    let indices_set: std::collections::HashSet<usize> = indices.iter().copied().collect();

    let path = reflog_path(git_dir, refname);
    let remaining: Vec<&ReflogEntry> = entries
        .iter()
        .enumerate()
        .filter(|(i, _)| !indices_set.contains(i))
        .map(|(_, e)| e)
        .collect();

    // Write back in file order (oldest first), so reverse again
    let mut lines = Vec::new();
    for entry in remaining.iter().rev() {
        lines.push(format_reflog_entry(entry));
    }

    fs::write(&path, lines.join(""))?;
    Ok(())
}

/// Expire (prune) reflog entries older than a given timestamp (Unix seconds).
///
/// If `expire_time` is `None`, removes all entries.
pub fn expire_reflog(git_dir: &Path, refname: &str, expire_time: Option<i64>) -> Result<usize> {
    let entries = read_reflog(git_dir, refname)?;
    if entries.is_empty() {
        return Ok(0);
    }

    let path = reflog_path(git_dir, refname);
    let mut kept = Vec::new();
    let mut pruned = 0usize;

    for entry in &entries {
        let ts = parse_timestamp_from_identity(&entry.identity);
        let dominated = match (expire_time, ts) {
            (Some(cutoff), Some(t)) => t < cutoff,
            (None, _) => true,        // expire all
            (Some(_), None) => false, // can't parse => keep
        };
        if dominated {
            pruned += 1;
        } else {
            kept.push(format_reflog_entry(entry));
        }
    }

    fs::write(&path, kept.join(""))?;
    Ok(pruned)
}

/// Expire reflog entries whose `new_oid` is not an ancestor of the current ref tip
/// and whose identity timestamp is older than `cutoff` (Unix seconds).
///
/// Entries with an all-zero `new_oid` are never removed by this pass.
///
/// When `cutoff` is `None`, no entries are removed.
///
/// Reftable-backed repositories are skipped until reflog rewrite is implemented there.
pub fn expire_reflog_unreachable(
    repo: &Repository,
    git_dir: &Path,
    refname: &str,
    cutoff: Option<i64>,
) -> Result<usize> {
    let Some(cutoff) = cutoff else {
        return Ok(0);
    };
    if crate::reftable::is_reftable_repo(git_dir) {
        return Ok(0);
    }
    let tip = match refs::resolve_ref(git_dir, refname) {
        Ok(o) => o,
        Err(_) => return Ok(0),
    };
    let ancestors = match merge_base::ancestor_closure(repo, tip) {
        Ok(a) => a,
        Err(_) => return Ok(0),
    };

    let entries = read_reflog(git_dir, refname)?;
    if entries.is_empty() {
        return Ok(0);
    }

    let path = reflog_path(git_dir, refname);
    let mut kept = Vec::new();
    let mut pruned = 0usize;

    for entry in &entries {
        let ts = parse_timestamp_from_identity(&entry.identity);
        let unreachable = !entry.new_oid.is_zero() && !ancestors.contains(&entry.new_oid);
        let should_prune = unreachable && matches!(ts, Some(t) if t < cutoff);
        if should_prune {
            pruned += 1;
        } else {
            kept.push(format_reflog_entry(entry));
        }
    }

    fs::write(&path, kept.join(""))?;
    Ok(pruned)
}

/// Format a reflog entry back into the on-disk line format.
fn format_reflog_entry(entry: &ReflogEntry) -> String {
    if entry.message.is_empty() {
        format!("{} {} {}\n", entry.old_oid, entry.new_oid, entry.identity)
    } else {
        format!(
            "{} {} {}\t{}\n",
            entry.old_oid, entry.new_oid, entry.identity, entry.message
        )
    }
}

/// Extract the Unix timestamp from an identity string.
///
/// Identity format: `Name <email> <timestamp> <tz>`
fn parse_timestamp_from_identity(identity: &str) -> Option<i64> {
    // Walk backwards: last token is tz (+0000), second-to-last is timestamp
    let parts: Vec<&str> = identity.rsplitn(3, ' ').collect();
    if parts.len() >= 2 {
        parts[1].parse::<i64>().ok()
    } else {
        None
    }
}

/// Copy `logs/<branch_refname>` to `logs/HEAD` when keeping symbolic-HEAD reflogs aligned with
/// the checked-out branch (matches Git).
pub fn mirror_branch_reflog_to_head(git_dir: &Path, branch_refname: &str) -> Result<()> {
    if crate::reftable::is_reftable_repo(git_dir) {
        return Ok(());
    }
    let src = reflog_path(git_dir, branch_refname);
    if !src.is_file() {
        return Ok(());
    }
    let content = fs::read_to_string(&src).map_err(Error::Io)?;
    let dst = reflog_path(git_dir, "HEAD");
    if let Some(parent) = dst.parent() {
        fs::create_dir_all(parent).map_err(Error::Io)?;
    }
    fs::write(&dst, content).map_err(Error::Io)?;
    Ok(())
}

/// List all refs that have reflogs.
pub fn list_reflog_refs(git_dir: &Path) -> Result<Vec<String>> {
    let mut refs = Vec::new();
    let mut seen = HashSet::new();

    fn collect_from_logs_root(
        logs_dir: &Path,
        out: &mut Vec<String>,
        seen: &mut HashSet<String>,
    ) -> Result<()> {
        if logs_dir.join("HEAD").is_file() && seen.insert("HEAD".to_string()) {
            out.push("HEAD".to_string());
        }
        let refs_logs = logs_dir.join("refs");
        if refs_logs.is_dir() {
            collect_reflog_refs(&refs_logs, "refs", out, seen)?;
        }
        Ok(())
    }

    collect_from_logs_root(&git_dir.join("logs"), &mut refs, &mut seen)?;
    if let Some(common) = refs::common_dir(git_dir) {
        if common != git_dir {
            collect_from_logs_root(&common.join("logs"), &mut refs, &mut seen)?;
        }
    }

    Ok(refs)
}

fn collect_reflog_refs(
    dir: &Path,
    prefix: &str,
    out: &mut Vec<String>,
    seen: &mut HashSet<String>,
) -> Result<()> {
    let read_dir = match fs::read_dir(dir) {
        Ok(rd) => rd,
        Err(e) if e.kind() == io::ErrorKind::NotFound => return Ok(()),
        Err(e) => return Err(Error::Io(e)),
    };

    for entry in read_dir {
        let entry = entry.map_err(Error::Io)?;
        let name = entry.file_name().to_string_lossy().to_string();
        let full_name = format!("{prefix}/{name}");
        let ft = entry.file_type().map_err(Error::Io)?;
        if ft.is_dir() {
            collect_reflog_refs(&entry.path(), &full_name, out, seen)?;
        } else if ft.is_file() && seen.insert(full_name.clone()) {
            out.push(full_name);
        }
    }
    Ok(())
}

// --- `git reflog expire` -----------------------------------------------------

/// Options for [`expire_reflog_git`].
#[derive(Debug, Clone)]
pub struct ReflogExpireParams {
    /// Prune entries whose commits fail a completeness walk (missing objects).
    pub stale_fix: bool,
    pub dry_run: bool,
    pub verbose: bool,
}

/// Per-ref `gc.<pattern>.reflogExpire*` rule from config.
#[derive(Debug, Clone)]
pub struct GcReflogPattern {
    pattern: String,
    expire_total: i64,
    expire_unreachable: i64,
}

fn collect_gc_reflog_patterns(config: &ConfigSet, now: i64) -> Vec<GcReflogPattern> {
    let mut by_pattern: HashMap<String, GcReflogPattern> = HashMap::new();
    for e in config.entries() {
        let key = e.key.as_str();
        let Some(rest) = key.strip_prefix("gc.") else {
            continue;
        };
        // Per-ref: `gc.<wildmatch-pattern>.reflogExpire` (pattern may contain dots).
        // Global `gc.reflogExpire` has no pattern segment — see [`global_gc_reflog_expiry`].
        let Some((pat, suffix)) = rest.rsplit_once('.') else {
            continue;
        };
        if !suffix.eq_ignore_ascii_case("reflogexpire")
            && !suffix.eq_ignore_ascii_case("reflogexpireunreachable")
        {
            continue;
        }
        let Some(val) = e.value.as_deref() else {
            continue;
        };
        let Ok(ts) = parse_gc_reflog_expiry(val, now) else {
            continue;
        };
        let ent = by_pattern
            .entry(pat.to_string())
            .or_insert(GcReflogPattern {
                pattern: pat.to_string(),
                expire_total: i64::MAX,
                expire_unreachable: i64::MAX,
            });
        if suffix.eq_ignore_ascii_case("reflogexpire") {
            ent.expire_total = ts;
        } else {
            ent.expire_unreachable = ts;
        }
    }
    by_pattern.into_values().collect()
}

fn global_gc_reflog_expiry(config: &ConfigSet, now: i64) -> (Option<i64>, Option<i64>) {
    let total = config
        .get("gc.reflogExpire")
        .and_then(|v| parse_gc_reflog_expiry(&v, now).ok());
    let unreach = config
        .get("gc.reflogExpireUnreachable")
        .and_then(|v| parse_gc_reflog_expiry(&v, now).ok());
    (total, unreach)
}

/// Parse `gc.reflogExpire` values: `never` / `false` → keep forever (`0`), else days or epoch.
fn parse_gc_reflog_expiry(raw: &str, now: i64) -> Result<i64> {
    let s = raw.trim();
    if s.eq_ignore_ascii_case("never") || s.eq_ignore_ascii_case("false") {
        return Ok(0);
    }
    if let Ok(days) = s.parse::<u64>() {
        if days == 0 {
            return Ok(0);
        }
        return Ok(now - (days as i64 * 86400));
    }
    s.parse::<i64>()
        .map_err(|_| Error::Message(format!("invalid reflog expiry: {raw:?}")))
}

fn default_expire_total(now: i64) -> i64 {
    now - 30 * 86400
}

fn default_expire_unreachable(now: i64) -> i64 {
    now - 90 * 86400
}

fn resolve_expire_for_ref(
    refname: &str,
    explicit_total: Option<i64>,
    explicit_unreachable: Option<i64>,
    patterns: &[GcReflogPattern],
    default_total: i64,
    default_unreachable: i64,
) -> (i64, i64) {
    let mut expire_total = explicit_total.unwrap_or(default_total);
    let mut expire_unreachable = explicit_unreachable.unwrap_or(default_unreachable);
    if explicit_total.is_some() && explicit_unreachable.is_some() {
        return (expire_total, expire_unreachable);
    }
    for ent in patterns {
        if wildmatch(ent.pattern.as_bytes(), refname.as_bytes(), WM_PATHNAME) {
            // Partial per-pattern config only sets one key; the other stays `i64::MAX` as sentinel.
            if explicit_total.is_none() && ent.expire_total != i64::MAX {
                expire_total = ent.expire_total;
            }
            if explicit_unreachable.is_none() && ent.expire_unreachable != i64::MAX {
                expire_unreachable = ent.expire_unreachable;
            }
            return (expire_total, expire_unreachable);
        }
    }
    if refname == "refs/stash" {
        if explicit_total.is_none() {
            expire_total = 0;
        }
        if explicit_unreachable.is_none() {
            expire_unreachable = 0;
        }
    }
    (expire_total, expire_unreachable)
}

fn tree_fully_complete(repo: &Repository, oid: ObjectId, depth: usize) -> bool {
    if depth > 65536 {
        return false;
    }
    let Ok(obj) = repo.odb.read(&oid) else {
        return false;
    };
    match obj.kind {
        ObjectKind::Blob => true,
        ObjectKind::Tree => {
            let Ok(entries) = parse_tree(&obj.data) else {
                return false;
            };
            for e in entries {
                if !tree_fully_complete(repo, e.oid, depth + 1) {
                    return false;
                }
            }
            true
        }
        _ => false,
    }
}

fn commit_chain_complete(repo: &Repository, oid: ObjectId, depth: usize) -> bool {
    if oid.is_zero() {
        return true;
    }
    if depth > 65536 {
        return false;
    }
    let Ok(obj) = repo.odb.read(&oid) else {
        return false;
    };
    if obj.kind != ObjectKind::Commit {
        return false;
    }
    let Ok(c) = parse_commit(&obj.data) else {
        return false;
    };
    if !tree_fully_complete(repo, c.tree, depth + 1) {
        return false;
    }
    for p in &c.parents {
        if !commit_chain_complete(repo, *p, depth + 1) {
            return false;
        }
    }
    true
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum UnreachableKind {
    Always,
    Normal,
    Head,
}

fn is_head_ref(refname: &str) -> bool {
    refname == "HEAD" || refname.ends_with("/HEAD")
}

fn tip_commits_for_reflog(repo: &Repository, git_dir: &Path, refname: &str) -> Vec<ObjectId> {
    let mut tips = Vec::new();
    if is_head_ref(refname) {
        if let Ok(oid) = refs::resolve_ref(git_dir, "HEAD") {
            tips.push(oid);
        }
        if let Ok(refs) = refs::list_refs(git_dir, "refs/") {
            for (_, oid) in refs {
                tips.push(oid);
            }
        }
    } else if let Ok(oid) = refs::resolve_ref(git_dir, refname) {
        tips.push(oid);
    }
    tips.sort();
    tips.dedup();
    tips.retain(|o| commit_chain_complete(repo, *o, 0));
    tips
}

fn reachable_commit_set(repo: &Repository, tips: &[ObjectId]) -> HashSet<ObjectId> {
    let mut acc = HashSet::new();
    for t in tips {
        if let Ok(cl) = merge_base::ancestor_closure(repo, *t) {
            acc.extend(cl);
        }
    }
    acc
}

fn is_unreachable_oid(
    repo: &Repository,
    reachable: &HashSet<ObjectId>,
    kind: UnreachableKind,
    oid: ObjectId,
) -> bool {
    if oid.is_zero() {
        return false;
    }
    if reachable.contains(&oid) {
        return false;
    }
    if kind == UnreachableKind::Always {
        return true;
    }
    let Ok(obj) = repo.odb.read(&oid) else {
        return true;
    };
    obj.kind == ObjectKind::Commit
}

fn should_drop_reflog_entry(
    repo: &Repository,
    entry: &ReflogEntry,
    expire_total: i64,
    expire_unreachable: i64,
    unreachable_kind: UnreachableKind,
    reachable: &HashSet<ObjectId>,
    stale_fix: bool,
) -> bool {
    let ts = parse_timestamp_from_identity(&entry.identity).unwrap_or(i64::MAX);
    if expire_total > 0 && ts < expire_total {
        return true;
    }
    if stale_fix
        && (!commit_chain_complete(repo, entry.old_oid, 0)
            || !commit_chain_complete(repo, entry.new_oid, 0))
    {
        return true;
    }
    if expire_unreachable > 0 && ts < expire_unreachable {
        match unreachable_kind {
            UnreachableKind::Always => return true,
            UnreachableKind::Normal | UnreachableKind::Head => {
                if is_unreachable_oid(repo, reachable, unreachable_kind, entry.old_oid)
                    || is_unreachable_oid(repo, reachable, unreachable_kind, entry.new_oid)
                {
                    return true;
                }
            }
        }
    }
    false
}

/// Git-compatible reflog expiry for one ref.
pub fn expire_reflog_git(
    repo: &Repository,
    git_dir: &Path,
    refname: &str,
    params: &ReflogExpireParams,
    explicit_total: Option<i64>,
    explicit_unreachable: Option<i64>,
    gc_patterns: &[GcReflogPattern],
    gc_global_total: Option<i64>,
    gc_global_unreachable: Option<i64>,
    now: i64,
) -> Result<usize> {
    if crate::reftable::is_reftable_repo(git_dir) {
        return Ok(0);
    }
    let base_total = gc_global_total.unwrap_or_else(|| default_expire_total(now));
    let base_unreachable = gc_global_unreachable.unwrap_or_else(|| default_expire_unreachable(now));
    let (expire_total, expire_unreachable) = resolve_expire_for_ref(
        refname,
        explicit_total,
        explicit_unreachable,
        gc_patterns,
        base_total,
        base_unreachable,
    );

    let unreachable_kind = if expire_unreachable <= expire_total {
        UnreachableKind::Always
    } else if expire_unreachable == 0 || is_head_ref(refname) {
        UnreachableKind::Head
    } else {
        match refs::resolve_ref(git_dir, refname) {
            Ok(t) if commit_chain_complete(repo, t, 0) => UnreachableKind::Normal,
            _ => UnreachableKind::Always,
        }
    };

    let tips = tip_commits_for_reflog(repo, git_dir, refname);
    let reachable = if matches!(unreachable_kind, UnreachableKind::Always) {
        HashSet::new()
    } else {
        reachable_commit_set(repo, &tips)
    };

    let entries = read_reflog(git_dir, refname)?;
    if entries.is_empty() {
        return Ok(0);
    }
    let path = reflog_path(git_dir, refname);
    let mut kept = Vec::new();
    let mut pruned = 0usize;

    for entry in &entries {
        let drop = should_drop_reflog_entry(
            repo,
            entry,
            expire_total,
            expire_unreachable,
            unreachable_kind,
            &reachable,
            params.stale_fix,
        );
        if drop {
            pruned += 1;
            if params.verbose {
                if params.dry_run {
                    println!("would prune {}", entry.message);
                } else {
                    println!("prune {}", entry.message);
                }
            }
        } else {
            if params.verbose {
                println!("keep {}", entry.message);
            }
            kept.push(format_reflog_entry(entry));
        }
    }

    if !params.dry_run && pruned > 0 {
        if kept.is_empty() {
            let _ = fs::remove_file(&path);
        } else {
            fs::write(&path, kept.join(""))?;
        }
    }
    Ok(pruned)
}

/// Per-ref `gc.<pattern>.reflogExpire*` rules plus global `gc.reflogExpire` / `gc.reflogExpireUnreachable`.
#[derive(Debug, Clone)]
pub struct GcReflogExpireConfig {
    pub patterns: Vec<GcReflogPattern>,
    pub global_total: Option<i64>,
    pub global_unreachable: Option<i64>,
}

/// Load gc reflog expiry rules from merged config (same layering as Git `reflog_expire_config`).
#[must_use]
pub fn load_gc_reflog_expire_config(config: &ConfigSet, now: i64) -> GcReflogExpireConfig {
    let (global_total, global_unreachable) = global_gc_reflog_expiry(config, now);
    GcReflogExpireConfig {
        patterns: collect_gc_reflog_patterns(config, now),
        global_total,
        global_unreachable,
    }
}

/// Best-effort object set for `--stale-fix` (refs + reflog mentions).
pub fn mark_stalefix_reachable(repo: &Repository, git_dir: &Path) -> Result<HashSet<ObjectId>> {
    let mut seeds: Vec<ObjectId> = Vec::new();
    if let Ok(oid) = refs::resolve_ref(git_dir, "HEAD") {
        seeds.push(oid);
    }
    if let Ok(refs) = refs::list_refs(git_dir, "refs/") {
        for (_, oid) in refs {
            seeds.push(oid);
        }
    }
    if let Ok(names) = list_reflog_refs(git_dir) {
        for r in names {
            if let Ok(ent) = read_reflog(git_dir, &r) {
                for e in ent {
                    if !e.old_oid.is_zero() {
                        seeds.push(e.old_oid);
                    }
                    if !e.new_oid.is_zero() {
                        seeds.push(e.new_oid);
                    }
                }
            }
        }
    }
    seeds.sort();
    seeds.dedup();

    let mut seen = HashSet::new();
    let mut queue: std::collections::VecDeque<ObjectId> = seeds.into_iter().collect();
    while let Some(oid) = queue.pop_front() {
        if oid.is_zero() || !seen.insert(oid) {
            continue;
        }
        let Ok(obj) = repo.odb.read(&oid) else {
            continue;
        };
        match obj.kind {
            ObjectKind::Commit => {
                if let Ok(c) = parse_commit(&obj.data) {
                    queue.push_back(c.tree);
                    for p in c.parents {
                        queue.push_back(p);
                    }
                }
            }
            ObjectKind::Tree => {
                if let Ok(entries) = parse_tree(&obj.data) {
                    for te in entries {
                        queue.push_back(te.oid);
                    }
                }
            }
            ObjectKind::Tag | ObjectKind::Blob => {}
        }
    }
    Ok(seen)
}