//! A mirror's objects read in process, for pages that must be quick:
//! starting a git process costs more than these reads take. Each mirror is
//! opened again only once its packs have changed: an open repository has
//! room for only as many packs as it was opened with, and some more.

use anyhow::{Context, Result};
use gix::ObjectId;
use gix::revision::walk::Sorting;
use gix::traverse::commit::simple::CommitTimeOrder;
use knotless::read::{Author, Commit, Entry};
use std::collections::{HashMap, HashSet};
use std::hash::Hash;
use std::path::{Path, PathBuf};
use std::sync::{Arc, LazyLock, Mutex};
use std::time::SystemTime;

/// Each mirror open, with when its packs last changed as it was opened.
type Open = HashMap<PathBuf, (gix::ThreadSafeRepository, Option<SystemTime>)>;

static OPEN: LazyLock<Mutex<Open>> = LazyLock::new(Mutex::default);

pub struct Objects(gix::Repository);

/// The newest commit to change each entry of a directory, by name, in the
/// tree's order.
type Changes = Arc<Vec<(String, ObjectId)>>;

/// What `last_changes` finds: each entry of a directory, by name, with the
/// sha of its commit, and each of those commits once.
pub type LastChanges = (Vec<(String, String)>, Vec<Commit>);

/// The directories whose entries' last changes are kept, in each of the
/// cache's two generations.
const CHANGES_KEPT: usize = 2048;

/// The most commits along a line of single parents looked through for one
/// whose answer is kept, before history is walked instead.
const LINE_MAX: usize = 256;

/// What a walk of history keeps of the packs' bases, as git's
/// `core.deltaBaseCacheLimit` does: it reads each version of a directory,
/// most of them stored as a delta on another.
const WALK_PACK_CACHE: usize = 64 << 20;

/// Each directory's changes, by the commit and the path. A commit's
/// history never changes, and is the same in any repository that has it,
/// so they are kept for good, and for any repository that asks.
static CHANGES: LazyLock<Mutex<Kept<(ObjectId, String), Changes>>> =
    LazyLock::new(|| Mutex::new(Kept::new(CHANGES_KEPT)));

/// A cache of at most twice `max` values: once `max` are new, the ones
/// before them go, and one asked for again is new again.
pub(crate) struct Kept<K, V> {
    max: usize,
    new: HashMap<K, V>,
    old: HashMap<K, V>,
}

impl<K: Hash + Eq + Clone, V: Clone> Kept<K, V> {
    pub(crate) fn new(max: usize) -> Self {
        Kept {
            max,
            new: HashMap::new(),
            old: HashMap::new(),
        }
    }

    pub(crate) fn get(&mut self, key: &K) -> Option<V> {
        if let Some(v) = self.new.get(key) {
            return Some(v.clone());
        }
        let v = self.old.remove(key)?;
        self.put(key.clone(), v.clone());
        Some(v)
    }

    pub(crate) fn put(&mut self, key: K, value: V) {
        if self.new.len() >= self.max {
            self.old = std::mem::take(&mut self.new);
        }
        self.new.insert(key, value);
    }
}

/// The histories whose length is kept, in each of the cache's two
/// generations: a tip and a number each, so many fit in little room.
const COUNTS_KEPT: usize = 16384;

/// How many commits each tip's history holds. A commit's history never
/// changes, so a count is kept for good, and for any repository that
/// asks, as `CHANGES` are.
static COUNTED: LazyLock<Mutex<Kept<ObjectId, usize>>> =
    LazyLock::new(|| Mutex::new(Kept::new(COUNTS_KEPT)));

fn kept(tip: ObjectId, path: &str) -> Option<Changes> {
    CHANGES.lock().unwrap().get(&(tip, path.to_string()))
}

/// The repository at `dir`, a bare mirror.
pub fn open(dir: &Path) -> Result<Objects> {
    let changed = std::fs::metadata(dir.join("objects/pack"))
        .and_then(|m| m.modified())
        .ok();
    let mut open = OPEN.lock().unwrap();
    let safe = match open.get(dir) {
        Some((safe, at)) if *at == changed => safe.clone(),
        _ => {
            let safe = gix::ThreadSafeRepository::open(dir)?;
            open.insert(dir.to_path_buf(), (safe.clone(), changed));
            safe
        }
    };
    let mut repo = safe.to_thread_local();
    repo.object_cache_size_if_unset(4 << 20);
    // An object not found is not looked for again among the packs on disk:
    // it is opened anew above when they change, and the feed asks after a
    // hundred commits at a time that a mirror may never have had.
    repo.objects.refresh_never();
    Ok(Objects(repo))
}

/// The id of whatever `path` names in `tree`, if anything.
fn id_at(tree: &gix::Tree<'_>, path: &str) -> Result<Option<gix::ObjectId>> {
    Ok(tree.lookup_entry_by_path(path)?.map(|e| e.oid().to_owned()))
}

/// What an entry of a tree is: a directory, a submodule's commit, or a
/// file, as links are taken to be.
fn kind(mode: gix::object::tree::EntryMode) -> &'static str {
    if mode.is_tree() {
        "tree"
    } else if mode.is_commit() {
        "commit"
    } else {
        "blob"
    }
}

impl Objects {
    /// The branch HEAD names, if it names one.
    pub fn head(&self) -> Option<String> {
        let name = self.0.head_name().ok()??;
        Some(name.shorten().to_string())
    }

    /// Every branch and tag, by its short name.
    pub fn names(&self) -> Result<Vec<String>> {
        let platform = self.0.references()?;
        let mut names = Vec::new();
        for r in platform.all()? {
            let r = r?;
            let full = r.name().as_bstr().to_string();
            if let Some(short) = full
                .strip_prefix("refs/heads/")
                .or(full.strip_prefix("refs/tags/"))
            {
                names.push(short.to_string());
            }
        }
        Ok(names)
    }

    /// Every branch, by its short name, in order.
    pub fn branches(&self) -> Result<Vec<String>> {
        let platform = self.0.references()?;
        let mut names = Vec::new();
        for r in platform.local_branches()? {
            names.push(r?.name().shorten().to_string());
        }
        names.sort();
        Ok(names)
    }

    fn commit(&self, rev: &str) -> Result<gix::Commit<'_>> {
        let id = self
            .0
            .rev_parse_single(rev)
            .with_context(|| format!("no revision {rev}"))?;
        Ok(id.object()?.peel_to_commit()?)
    }

    /// The commit `rev` names, by its full id.
    pub fn resolve(&self, rev: &str) -> Result<String> {
        Ok(self.commit(rev)?.id.to_string())
    }

    /// The commit `rev` names.
    pub fn tip(&self, rev: &str) -> Result<Commit> {
        let commit = self.commit(rev)?;
        summary(&commit)
    }

    /// Every tag that names a commit, by its short name, with that commit:
    /// the newest commit first, and the tags of one commit by name.
    pub fn tags(&self) -> Result<Vec<(String, Commit)>> {
        let platform = self.0.references()?;
        let mut tags = Vec::new();
        for r in platform.tags()? {
            let r = r?;
            let full = r.name().as_bstr().to_string();
            if let Ok(commit) = self.commit(&full) {
                let at = commit.time()?.seconds;
                let shown = summary(&commit)?;
                tags.push((at, r.name().shorten().to_string(), shown));
            }
        }
        tags.sort_by(|a, b| b.0.cmp(&a.0).then_with(|| a.1.cmp(&b.1)));
        Ok(tags.into_iter().map(|(_, name, c)| (name, c)).collect())
    }

    pub fn tree(&self, rev: &str, path: &str) -> Result<Vec<Entry>> {
        let mut tree = self.commit(rev)?.tree()?;
        if !path.is_empty() {
            let entry = tree
                .lookup_entry_by_path(path)?
                .with_context(|| format!("no {path} at {rev}"))?;
            tree = entry
                .object()?
                .try_into_tree()
                .with_context(|| format!("{path} is not a directory"))?;
        }
        let mut out = Vec::new();
        for e in tree.iter() {
            let e = e?;
            let mode = e.mode();
            let kind = kind(mode);
            let size = match kind {
                "blob" => Some(self.0.find_header(e.oid())?.size()),
                _ => None,
            };
            out.push(Entry {
                name: e.filename().to_string(),
                mode: mode.kind().as_octal_str().to_string(),
                kind: kind.into(),
                sha: e.oid().to_string(),
                size,
            });
        }
        Ok(out)
    }

    /// The id of the tree at `rev`.
    pub fn tree_id(&self, rev: &str) -> Result<String> {
        Ok(self.commit(rev)?.tree_id()?.to_string())
    }

    /// Each file in the whole tree at `rev` that `pick` makes something
    /// of, by its path, with its size: read from the object's header, not
    /// its contents. Links and submodules are not files.
    pub fn files<T>(&self, rev: &str, pick: impl Fn(&str) -> Option<T>) -> Result<Vec<(T, u64)>> {
        let mut found = gix::traverse::tree::Recorder::default();
        self.commit(rev)?
            .tree()?
            .traverse()
            .breadthfirst(&mut found)?;
        let mut out = Vec::new();
        for e in found.records.iter().filter(|e| e.mode.is_blob()) {
            if let Some(picked) = pick(&e.filepath.to_string()) {
                out.push((picked, self.0.find_header(e.oid)?.size()));
            }
        }
        Ok(out)
    }

    /// Every path in the whole tree at `rev`, folders as well as files,
    /// each with its kind as `tree` names them: the shallowest first, so
    /// that what `limit` cuts off is the deepest. And whether it cut any.
    pub fn paths(&self, rev: &str, limit: usize) -> Result<(Vec<(String, &'static str)>, bool)> {
        let mut found = gix::traverse::tree::Recorder::default();
        self.commit(rev)?
            .tree()?
            .traverse()
            .breadthfirst(&mut found)?;
        let cut = found.records.len() > limit;
        let out = found
            .records
            .into_iter()
            .take(limit)
            .map(|e| (e.filepath.to_string(), kind(e.mode)))
            .collect();
        Ok((out, cut))
    }

    /// Whether `path` is a directory at `rev`: the root is one.
    pub fn is_dir(&self, rev: &str, path: &str) -> bool {
        let tree = self.commit(rev).and_then(|c| Ok(c.tree()?));
        let entry = tree.map(|t| t.lookup_entry_by_path(path));
        path.is_empty() || matches!(entry, Ok(Ok(Some(e))) if e.mode().is_tree())
    }

    pub fn blob(&self, rev: &str, path: &str) -> Result<Vec<u8>> {
        let tree = self.commit(rev)?.tree()?;
        let entry = tree
            .lookup_entry_by_path(path)?
            .with_context(|| format!("no {path} at {rev}"))?;
        let object = entry.object()?;
        anyhow::ensure!(
            object.kind == gix::object::Kind::Blob,
            "{path} is not a file"
        );
        Ok(object.detach().data)
    }

    /// Whether `commit` changed `path` from each of its parents: a commit
    /// that left it as one parent had it is not part of its history.
    fn touches(&self, commit: &gix::Commit<'_>, path: &str) -> Result<bool> {
        let here = id_at(&commit.tree()?, path)?;
        let mut parents = commit.parent_ids().peekable();
        if parents.peek().is_none() {
            return Ok(here.is_some());
        }
        for parent in parents {
            if id_at(&parent.object()?.peel_to_commit()?.tree()?, path)? == here {
                return Ok(false);
            }
        }
        Ok(true)
    }

    /// History from `rev`, newest first, touching `path` if it is not
    /// empty, after its first `skip` commits.
    pub fn log(&self, rev: &str, path: &str, skip: usize, limit: usize) -> Result<Vec<Commit>> {
        let tip = self.commit(rev)?.id;
        let walk = self
            .0
            .rev_walk([tip])
            .sorting(Sorting::ByCommitTime(CommitTimeOrder::NewestFirst))
            .all()?;
        let mut out = Vec::new();
        let mut skipped = 0;
        for info in walk {
            let commit = info?.object()?;
            if !path.is_empty() && !self.touches(&commit, path)? {
                continue;
            }
            if skipped < skip {
                skipped += 1;
                continue;
            }
            out.push(summary(&commit)?);
            if out.len() == limit {
                break;
            }
        }
        Ok(out)
    }

    /// How many commits the history of `rev` holds, its own among them.
    /// The walk reads the mirror's commit-graph, not the packs, and is
    /// made once for each tip.
    pub fn count(&self, rev: &str) -> Result<usize> {
        let tip = self.commit(rev)?.id;
        if let Some(n) = COUNTED.lock().unwrap().get(&tip) {
            return Ok(n);
        }
        let walk = self.0.rev_walk([tip]).sorting(Sorting::BreadthFirst);
        let mut n = 0;
        for info in walk.all()? {
            info?;
            n += 1;
        }
        COUNTED.lock().unwrap().put(tip, n);
        Ok(n)
    }

    /// The newest commit to change each entry of the directory `path` at
    /// `rev`, as `log` finds each entry's history, in the tree's order, and
    /// each of those commits once, newest first.
    pub fn last_changes(&self, rev: &str, path: &str) -> Result<LastChanges> {
        let tip = self.commit(rev)?.id;
        self.dir(tip, path)?
            .with_context(|| format!("no directory {path} at {rev}"))?;
        let found = self.changes(tip, path)?;
        let mut ids: Vec<ObjectId> = found.iter().map(|(_, id)| *id).collect();
        let mut seen = HashSet::new();
        ids.retain(|id| seen.insert(*id));
        let mut commits = Vec::new();
        for id in ids {
            let commit = self.0.find_commit(id)?;
            commits.push((commit.time()?.seconds, summary(&commit)?));
        }
        commits.sort_by_key(|(at, _)| std::cmp::Reverse(*at));
        let commits = commits.into_iter().map(|(_, c)| c).collect();
        let entries = found.iter().map(|(n, id)| (n.clone(), id.to_string()));
        Ok((entries.collect(), commits))
    }

    /// `last_changes` of `tip`, kept, else made from those of a commit
    /// before it along a line of single parents, a push being only its own
    /// changes on top of the one before, else found walking history.
    fn changes(&self, tip: ObjectId, path: &str) -> Result<Changes> {
        if let Some(known) = kept(tip, path) {
            return Ok(known);
        }
        let mut line = Vec::new();
        let mut at = tip;
        let mut base = None;
        while line.len() < LINE_MAX {
            let parents: Vec<ObjectId> = self
                .0
                .find_commit(at)?
                .parent_ids()
                .map(|p| p.detach())
                .collect();
            let [parent] = parents[..] else { break };
            line.push((at, parent));
            base = kept(parent, path);
            if base.is_some() {
                break;
            }
            at = parent;
        }
        let found = match base {
            Some(base) => self.on_top(base, &line, path)?,
            None => self.walk(tip, path)?,
        };
        CHANGES
            .lock()
            .unwrap()
            .put((tip, path.to_string()), found.clone());
        Ok(found)
    }

    /// The changes of `base`, the answer for the parent of the oldest of
    /// `line`'s commits, newest first, with each one's own on top.
    fn on_top(&self, base: Changes, line: &[(ObjectId, ObjectId)], path: &str) -> Result<Changes> {
        let mut found = base;
        for &(commit, parent) in line.iter().rev() {
            let before: HashMap<String, ObjectId> =
                self.listed(self.dir(parent, path)?)?.into_iter().collect();
            let was: HashMap<&str, ObjectId> =
                found.iter().map(|(n, id)| (n.as_str(), *id)).collect();
            let mut now = Vec::new();
            for (name, id) in self.listed(self.dir(commit, path)?)? {
                let last = match was.get(name.as_str()) {
                    Some(last) if before.get(&name) == Some(&id) => *last,
                    _ => commit,
                };
                now.push((name, last));
            }
            found = Arc::new(now);
        }
        Ok(found)
    }

    /// `last_changes` of `tip`, walking its history once for all of the
    /// directory's entries: a commit that left the directory as one of its
    /// parents had it is passed over unread, and the walk ends once every
    /// entry has its commit.
    fn walk(&self, tip: ObjectId, path: &str) -> Result<Changes> {
        let mut repo = self.0.clone();
        repo.objects.set_pack_cache(|| {
            Box::new(gix::odb::pack::cache::lru::MemoryCappedHashmap::new(
                WALK_PACK_CACHE,
            ))
        });
        let at = Objects(repo);
        let top =
            at.0.find_object(at.dir(tip, path)?.context("no directory")?)?;
        let top = top.try_into_tree()?;
        let mut pending = Vec::new();
        for e in top.iter() {
            let e = e?;
            pending.push((e.filename().to_owned(), e.mode().is_tree()));
        }
        let order: Vec<String> = pending.iter().map(|(n, _)| n.to_string()).collect();
        let mut found = HashMap::new();
        let mut dirs = HashMap::new();
        let mut trees = HashMap::new();
        let kind = at.0.object_hash();
        let walk =
            at.0.rev_walk([tip])
                .sorting(Sorting::ByCommitTime(CommitTimeOrder::NewestFirst))
                .all()?;
        for info in walk {
            let info = info?;
            let here = at.dir_kept(info.id, path, &mut dirs)?;
            let mut parents = Vec::new();
            for p in info.parent_ids.iter() {
                parents.push(at.dir_kept(*p, path, &mut dirs)?);
            }
            if parents.contains(&here) {
                continue;
            }
            let now = at.raw(here, &mut trees)?;
            let now = gix::objs::TreeRef::from_bytes(&now, kind)?;
            let mut before = Vec::new();
            for p in parents {
                before.push(at.raw(p, &mut trees)?);
            }
            let before = before
                .iter()
                .map(|b| gix::objs::TreeRef::from_bytes(b, kind))
                .collect::<std::result::Result<Vec<_>, _>>()?;
            let id = |t: &gix::objs::TreeRef<'_>, name: &gix::bstr::BString, dir: bool| {
                t.bisect_entry(name.as_ref(), dir).map(|e| e.oid.to_owned())
            };
            pending.retain(|(name, dir)| {
                let mine = id(&now, name, *dir);
                let changed = if before.is_empty() {
                    mine.is_some()
                } else {
                    before.iter().all(|b| id(b, name, *dir) != mine)
                };
                if changed {
                    found.insert(name.to_string(), info.id);
                }
                !changed
            });
            if pending.is_empty() {
                break;
            }
        }
        let changes = order
            .into_iter()
            .filter_map(|name| found.get(&name).map(|id| (name, *id)))
            .collect();
        Ok(Arc::new(changes))
    }

    /// The directory `path` names in `commit`, if it names one.
    fn dir(&self, commit: ObjectId, path: &str) -> Result<Option<ObjectId>> {
        let commit = self.0.find_commit(commit)?;
        if path.is_empty() {
            return Ok(Some(commit.tree_id()?.detach()));
        }
        let entry = commit.tree()?.lookup_entry_by_path(path)?;
        Ok(entry
            .filter(|e| e.mode().is_tree())
            .map(|e| e.oid().to_owned()))
    }

    /// `dir`, each commit's read once.
    fn dir_kept(
        &self,
        commit: ObjectId,
        path: &str,
        seen: &mut HashMap<ObjectId, Option<ObjectId>>,
    ) -> Result<Option<ObjectId>> {
        if let Some(dir) = seen.get(&commit) {
            return Ok(*dir);
        }
        let dir = self.dir(commit, path)?;
        seen.insert(commit, dir);
        Ok(dir)
    }

    /// A directory's bytes, empty for none, kept while the walk is near
    /// it: a commit's parent is most often the next one walked.
    fn raw(
        &self,
        tree: Option<ObjectId>,
        seen: &mut HashMap<ObjectId, Arc<Vec<u8>>>,
    ) -> Result<Arc<Vec<u8>>> {
        let Some(tree) = tree else {
            return Ok(Arc::default());
        };
        if let Some(bytes) = seen.get(&tree) {
            return Ok(bytes.clone());
        }
        if seen.len() > 64 {
            seen.clear();
        }
        let bytes = Arc::new(self.0.find_object(tree)?.detach().data);
        seen.insert(tree, bytes.clone());
        Ok(bytes)
    }

    /// Each entry of a directory, by name, none for no directory.
    fn listed(&self, tree: Option<ObjectId>) -> Result<Vec<(String, ObjectId)>> {
        let Some(tree) = tree else {
            return Ok(Vec::new());
        };
        let mut out = Vec::new();
        for e in self.0.find_tree(tree)?.iter() {
            let e = e?;
            out.push((e.filename().to_string(), e.oid().to_owned()));
        }
        Ok(out)
    }

    /// What moving a ref to `to` brought: the commits it reaches that none
    /// of `known` does, newest first, at most `limit` of them. A revision
    /// in `known` that is not here is passed over.
    pub fn brought(&self, to: &str, known: &[&str], limit: usize) -> Result<Vec<Commit>> {
        let tip = self.commit(to)?.id;
        let hidden: Vec<gix::ObjectId> = known
            .iter()
            .filter_map(|k| self.commit(k).ok().map(|c| c.id))
            .collect();
        let walk = self
            .0
            .rev_walk([tip])
            .with_hidden(hidden)
            .sorting(Sorting::ByCommitTime(CommitTimeOrder::NewestFirst))
            .all()?;
        let mut out = Vec::new();
        for info in walk.take(limit) {
            out.push(summary(&info?.object()?)?);
        }
        Ok(out)
    }

    /// The commits `to` reaches that `from` does not, as `git rev-list
    /// from..to` lists them, by id. An error when either is not here.
    pub fn between(&self, from: &str, to: &str) -> Result<HashSet<String>> {
        let tip = self.commit(to)?.id;
        let hidden = self.commit(from)?.id;
        let mut out = HashSet::new();
        for info in self.0.rev_walk([tip]).with_hidden([hidden]).all()? {
            out.insert(info?.id.to_string());
        }
        Ok(out)
    }
}

fn summary(commit: &gix::Commit<'_>) -> Result<Commit> {
    Ok(Commit {
        sha: commit.id.to_string(),
        parents: commit.parent_ids().map(|p| p.to_string()).collect(),
        author: who(commit.author()?)?,
        committer: who(commit.committer()?)?,
        message: commit.message_raw()?.to_string().trim_end().to_string(),
    })
}

/// A commit's author or committer, with when.
fn who(sig: gix::actor::SignatureRef<'_>) -> Result<Author> {
    let date = sig
        .time()?
        .format(gix::date::time::format::ISO8601_STRICT)?;
    Ok(Author {
        name: sig.name.to_string(),
        email: sig.email.to_string(),
        date,
    })
}

#[cfg(test)]
mod tests {
    use super::*;
    use knotless::git::Git;

    async fn git(dir: &Path, args: &[&str]) -> String {
        Git::new(dir).text(args, None).await.unwrap()
    }

    #[tokio::test]
    async fn reads_as_git_does() {
        let dir = tempfile::tempdir().unwrap();
        let d = dir.path();
        let run = |args: Vec<&str>| {
            let out = std::process::Command::new("git")
                .args(args)
                .current_dir(d)
                .env("GIT_CONFIG_GLOBAL", "/dev/null")
                .env("GIT_AUTHOR_NAME", "A")
                .env("GIT_AUTHOR_EMAIL", "a@x")
                .env("GIT_COMMITTER_NAME", "A")
                .env("GIT_COMMITTER_EMAIL", "a@x")
                .output()
                .unwrap();
            assert!(out.status.success(), "{out:?}");
        };
        run(vec!["init", "-q", "-b", "main"]);
        std::fs::create_dir(d.join("src")).unwrap();
        std::fs::write(d.join("src/a.rs"), "fn a() {}\n").unwrap();
        std::fs::write(d.join("b"), "b\n").unwrap();
        run(vec!["add", "-A"]);
        run(vec!["commit", "-q", "-m", "one\n\nwith a body"]);
        std::fs::write(d.join("b"), "bb\n").unwrap();
        run(vec!["commit", "-qam", "two"]);
        run(vec!["checkout", "-q", "-b", "side", "HEAD~1"]);
        std::fs::write(d.join("src/a.rs"), "fn a() { 1 }\n").unwrap();
        run(vec!["commit", "-qam", "three"]);
        run(vec!["checkout", "-q", "main"]);
        run(vec!["merge", "-q", "--no-edit", "side"]);
        let one = git(&d.join(".git"), &["rev-parse", "HEAD~1"]).await;
        run(vec![
            "update-index",
            "--add",
            "--cacheinfo",
            &format!("160000,{one},vendored"),
        ]);
        run(vec!["commit", "-qm", "vendor"]);
        run(vec!["tag", "v1"]);
        run(vec!["update-ref", "refs/notes/x", "HEAD"]);

        open(&d.join(".git")).unwrap();
        // New packs: opened again, with room for them.
        run(vec!["repack", "-q"]);
        let again = open(&d.join(".git")).unwrap();
        let o = open(&d.join(".git")).unwrap();
        assert_eq!(o.head().as_deref(), Some("main"));
        assert_eq!(
            again.resolve("v1").unwrap(),
            git(&d.join(".git"), &["rev-parse", "HEAD"]).await
        );
        let mut names = o.names().unwrap();
        names.sort();
        assert_eq!(names, ["main", "side", "v1"]);
        assert_eq!(o.branches().unwrap(), ["main", "side"]);
        // one, two, three on side, the merge and vendor; again, as kept.
        assert_eq!(o.count("main").unwrap(), 5);
        assert_eq!(o.count("main").unwrap(), 5);
        assert_eq!(o.count("side").unwrap(), 2);
        assert!(o.count("no-such").is_err());

        let tree = o.tree("main", "").unwrap();
        let shown: Vec<(&str, &str, Option<u64>)> = tree
            .iter()
            .map(|e| (e.name.as_str(), e.kind.as_str(), e.size))
            .collect();
        assert_eq!(
            shown,
            [
                ("b", "blob", Some(3)),
                ("src", "tree", None),
                ("vendored", "commit", None)
            ]
        );
        assert_eq!(tree[1].mode, "40000");
        assert_eq!(o.tree("main", "src").unwrap()[0].name, "a.rs");
        assert!(o.tree("main", "b").is_err());
        assert!(o.tree("main", "nope").is_err());
        assert!(o.tree("nope", "").is_err());
        assert_eq!(o.blob("main", "src/a.rs").unwrap(), b"fn a() { 1 }\n");
        assert!(o.blob("main", "src").is_err());
        assert!(o.blob("main", "nope").is_err());
        let sized = |p: &str| (p != "b").then(|| p.to_string());
        assert_eq!(o.files("main", sized).unwrap(), [("src/a.rs".into(), 13)]);
        assert!(o.files("nope", sized).is_err());
        assert!(o.tree_id("nope").is_err());

        let subjects = |log: Vec<Commit>| {
            log.iter()
                .map(|c| c.message.lines().next().unwrap().to_string())
                .collect::<Vec<_>>()
        };
        let all = o.log("main", "", 0, 10).unwrap();
        assert_eq!(all.len(), 5);
        assert_eq!(all[1].parents.len(), 2);
        assert_eq!(all[4].message, "one\n\nwith a body");
        assert_eq!(all[4].author.name, "A");
        assert!(all[4].author.date.contains('T'), "{}", all[4].author.date);
        let committed = &all[4].committer.date;
        assert!(committed.contains('T'), "{committed}");
        assert_eq!(o.log("main", "", 1, 2).unwrap().len(), 2);
        assert_eq!(subjects(o.log("main", "b", 0, 10).unwrap()), ["two", "one"]);
        assert_eq!(
            subjects(o.log("main", "src", 0, 10).unwrap()),
            ["three", "one"]
        );
        assert_eq!(subjects(o.log("main", "src", 1, 10).unwrap()), ["one"]);
        assert!(o.log("main", "nowhere", 0, 10).unwrap().is_empty());
        assert!(o.log("nope", "", 0, 10).is_err());
        assert!(open(&d.join("missing")).is_err());

        // What a push of main brought, past side and a ref it never saw.
        assert_eq!(
            subjects(o.brought("main", &["side", "gone"], 10).unwrap()),
            ["vendor", "Merge branch 'side'", "two"]
        );
        assert_eq!(o.brought("main", &[], 10).unwrap().len(), 5);
        assert_eq!(o.brought("main", &[], 2).unwrap().len(), 2);
        assert!(o.brought("main", &["main"], 10).unwrap().is_empty());
        assert!(o.brought("nope", &[], 10).is_err());
        let past_side = o.brought("main", &["side"], 10).unwrap();
        let past_side: HashSet<String> = past_side.into_iter().map(|c| c.sha).collect();
        assert_eq!(o.between("side", "main").unwrap(), past_side);
        assert!(o.between("main", "main").unwrap().is_empty());
        assert!(o.between("gone", "main").is_err());
        assert!(o.between("side", "nope").is_err());

        run(vec!["checkout", "-q", "--detach"]);
        assert_eq!(open(&d.join(".git")).unwrap().head(), None);
    }

    #[test]
    fn keeping() {
        let mut kept = Kept::new(2);
        kept.put(1, "one");
        kept.put(2, "two");
        // A third: the first two are old, and the one asked for is new.
        kept.put(3, "three");
        assert_eq!(kept.get(&1), Some("one"));
        kept.put(4, "four");
        assert_eq!(kept.get(&2), None);
        assert_eq!(kept.get(&1), Some("one"));
        assert_eq!(kept.get(&4), Some("four"));
    }

    #[test]
    fn last_changes_as_log_finds_them() {
        let dir = tempfile::tempdir().unwrap();
        let d = dir.path();
        // Each commit a second after the one before, as history is made.
        let clock = std::cell::Cell::new(1_700_000_000);
        let run = |args: &[&str]| {
            clock.set(clock.get() + 1);
            let at = format!("{} +0000", clock.get());
            let out = std::process::Command::new("git")
                .args(args)
                .current_dir(d)
                .env("GIT_AUTHOR_DATE", &at)
                .env("GIT_COMMITTER_DATE", &at)
                .env("GIT_CONFIG_GLOBAL", "/dev/null")
                .env("GIT_AUTHOR_NAME", "A")
                .env("GIT_AUTHOR_EMAIL", "a@x")
                .env("GIT_COMMITTER_NAME", "A")
                .env("GIT_COMMITTER_EMAIL", "a@x")
                .output()
                .unwrap();
            assert!(out.status.success(), "{out:?}");
            String::from_utf8(out.stdout).unwrap().trim().to_string()
        };
        let put = |path: &str, text: &str| {
            let path = d.join(path);
            std::fs::create_dir_all(path.parent().unwrap()).unwrap();
            std::fs::write(path, text).unwrap();
        };
        let commit = |message: &str| {
            run(&["add", "-A"]);
            run(&["commit", "-qm", message]);
        };
        run(&["init", "-q", "-b", "main"]);
        put("a", "a");
        put("b", "b");
        put("docs", "a file, at first");
        put("src/x", "x");
        put("src/y", "y");
        commit("one");
        put("a", "aa");
        commit("two");
        run(&["checkout", "-q", "-b", "side"]);
        put("src/x", "xx");
        commit("three");
        run(&["checkout", "-q", "main"]);
        put("b", "bb");
        commit("four");
        run(&["merge", "-q", "--no-edit", "side"]);
        std::fs::remove_file(d.join("docs")).unwrap();
        put("docs/guide", "guide");
        commit("docs");
        // Enough versions of a directory that the walk lets go of some.
        for n in 0..70 {
            put("many/n", &n.to_string());
            commit(&format!("n{n}"));
        }
        // The merge again, side ahead of main: its entries as either had them.
        run(&["checkout", "-q", "side"]);
        put("src/z", "z");
        commit("five");
        run(&["checkout", "-q", "main"]);
        run(&["merge", "-q", "--no-edit", "side"]);

        let o = open(&d.join(".git")).unwrap();
        let subject = |sha: &str| {
            let c = o.log(sha, "", 0, 1).unwrap().remove(0);
            c.message.lines().next().unwrap().to_string()
        };
        // Each entry's commit is the one log finds first for it.
        let as_log = |rev: &str, path: &str| {
            let (entries, commits) = o.last_changes(rev, path).unwrap();
            let mut shas: Vec<&str> = entries.iter().map(|(_, s)| s.as_str()).collect();
            shas.sort();
            shas.dedup();
            assert_eq!(commits.len(), shas.len());
            for (name, sha) in &entries {
                let at = if path.is_empty() {
                    name.clone()
                } else {
                    format!("{path}/{name}")
                };
                assert_eq!(
                    subject(&o.log(rev, &at, 0, 1).unwrap()[0].sha),
                    subject(sha),
                    "{at} at {rev}"
                );
            }
            let named = |(name, sha): &(String, String)| (name.clone(), subject(sha));
            entries.iter().map(named).collect::<Vec<_>>()
        };
        let pairs = |list: &[(&str, &str)]| {
            list.iter()
                .map(|(n, s)| (n.to_string(), s.to_string()))
                .collect::<Vec<_>>()
        };
        assert_eq!(
            as_log("main", ""),
            pairs(&[
                ("a", "two"),
                ("b", "four"),
                ("docs", "docs"),
                ("many", "n69"),
                ("src", "five")
            ])
        );
        // Asked again: kept.
        assert_eq!(as_log("main", "").len(), 5);
        assert_eq!(
            as_log("main", "src"),
            pairs(&[("x", "three"), ("y", "one"), ("z", "five")])
        );
        assert_eq!(as_log("main", "docs"), pairs(&[("guide", "docs")]));
        assert_eq!(
            as_log("main~1", "src"),
            pairs(&[("x", "three"), ("y", "one")])
        );
        let (_, commits) = o.last_changes("main", "src").unwrap();
        assert_eq!(subject(&commits[0].sha), "five");
        assert!(o.last_changes("main", "a").is_err());
        assert!(o.last_changes("main", "nope").is_err());
        assert!(o.last_changes("nope", "").is_err());

        // Pushes on top of what is kept: each commit's own changes on the
        // answer before it, an entry gone, another new, the directory gone
        // and back.
        put("src/x", "xxx");
        std::fs::remove_file(d.join("src/y")).unwrap();
        put("src/w", "w");
        commit("six");
        put("a", "aaa");
        commit("seven");
        let o = open(&d.join(".git")).unwrap();
        let (entries, _) = o.last_changes("main", "src").unwrap();
        let six = o.resolve("main~1").unwrap();
        let five = o.log("main", "src/z", 0, 1).unwrap().remove(0).sha;
        assert_eq!(
            entries,
            [
                ("w".into(), six.clone()),
                ("x".into(), six),
                ("z".into(), five)
            ]
        );
        std::fs::remove_dir_all(d.join("src")).unwrap();
        commit("src gone");
        put("src/v", "v");
        commit("src back");
        let o = open(&d.join(".git")).unwrap();
        let (entries, _) = o.last_changes("main", "src").unwrap();
        assert_eq!(entries, [("v".into(), o.resolve("main").unwrap())]);
        let (entries, _) = o.last_changes("main", "").unwrap();
        let names: Vec<_> = entries
            .iter()
            .map(|(n, s)| (n.as_str(), subject(s)))
            .collect();
        assert_eq!(names[0], ("a", "seven".into()));
        assert_eq!(names[4], ("src", "src back".into()));
    }
}