char/sorcery

git clone https://git.t4t.associates/char/sorcery

Charlotte Somfix path-history smart query type (+ add a new obj frame type)5d40e972026-09-03

//! `git log -- path` with git's default history simplification: walk commits
//! newest-first, and at each merge that is TREESAME to a parent follow only
//! that parent, so the walk never leaves the side of a merge that touched the
//! path. The walk state is just the frontier, so a page can be resumed from
//! whatever it hands back.

use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashMap, HashSet};

use anyhow::Result;

const TREE: u16 = 0o040000;

#[derive(Clone, Copy, PartialEq, Eq)]
struct Located {
    oid: gix::ObjectId,
    mode: u16,
}

pub struct Page {
    /// Commits that changed the path, in walk order.
    pub changes: Vec<gix::ObjectId>,
    /// Where to resume; empty once history is exhausted.
    pub frontier: Vec<gix::ObjectId>,
}

/// Walks from `frontier` until `limit` changes are found, `scan_limit` commits
/// have been examined, or history is exhausted (empty returned frontier).
pub fn page(
    repo: &gix::Repository,
    frontier: &[gix::ObjectId],
    path: &[String],
    limit: usize,
    scan_limit: usize,
) -> Result<Page> {
    // committer-date order with FIFO ties, like git's commit_list_insert_by_date
    let mut heap = BinaryHeap::new();
    let mut seen = HashSet::new();
    let mut located = HashMap::new();
    let mut changes = Vec::new();
    let mut scanned = 0;

    let mut push = |heap: &mut BinaryHeap<_>, mut oid: gix::ObjectId| -> Result<()> {
        let commit = loop {
            let object = repo.find_object(oid)?;
            match object.kind {
                gix::object::Kind::Tag => oid = object.into_tag().target_id()?.detach(),
                _ => break object.try_into_commit()?,
            }
        };
        if seen.insert(oid) {
            heap.push((commit.time()?.seconds, Reverse(seen.len()), oid));
        }
        Ok(())
    };
    for &oid in frontier {
        push(&mut heap, oid)?;
    }

    while changes.len() < limit && scanned < scan_limit {
        let Some((_, _, oid)) = heap.pop() else {
            break;
        };
        scanned += 1;
        let commit = repo.find_object(oid)?.into_commit();
        let object = locate(repo, &mut located, commit.tree_id()?.detach(), path)?;
        let parents = commit.parent_ids().map(|id| id.detach()).collect::<Vec<_>>();

        let mut treesame = None;
        for &parent in &parents {
            let tree = repo.find_object(parent)?.try_into_commit()?.tree_id()?.detach();
            if locate(repo, &mut located, tree, path)? == object {
                treesame = Some(parent);
                break;
            }
        }
        match treesame {
            Some(parent) => push(&mut heap, parent)?,
            None => {
                if parents.is_empty() && object.is_none() {
                    continue;
                }
                changes.push(oid);
                for parent in parents {
                    push(&mut heap, parent)?;
                }
            }
        }
    }

    Ok(Page {
        changes,
        // in walk order, so resuming re-pushes ties in the same order
        frontier: heap.into_sorted_vec().into_iter().rev().map(|(_, _, oid)| oid).collect(),
    })
}

/// The entry at `path` within `tree`, memoised per tree since consecutive
/// commits share nearly all of theirs.
fn locate(
    repo: &gix::Repository,
    memo: &mut HashMap<gix::ObjectId, Option<Located>>,
    tree: gix::ObjectId,
    path: &[String],
) -> Result<Option<Located>> {
    if let Some(&found) = memo.get(&tree) {
        return Ok(found);
    }
    let mut found = Some(Located { oid: tree, mode: TREE });
    for component in path {
        let Some(Located { oid, mode: TREE }) = found else {
            found = None;
            break;
        };
        found = None;
        for entry in repo.find_object(oid)?.try_into_tree()?.iter() {
            let entry = entry?;
            if entry.filename() == component.as_bytes() {
                found = Some(Located { oid: entry.oid().to_owned(), mode: entry.mode().value() });
                break;
            }
        }
    }
    memo.insert(tree, found);
    Ok(found)
}

#[cfg(test)]
mod tests {
    use std::fs;

    use anyhow::Result;

    use crate::testutil::{TempDir, commit, git, init_repo};

    use super::page;

    /// A merge where the path changed on the side branch only, a merge that
    /// changed it on both sides, and a deletion.
    #[test]
    fn matches_git_log_simplification() -> Result<()> {
        let root = TempDir::new("history");
        let repo = root.join("repo");
        init_repo(&repo)?;
        fs::create_dir(repo.join("src"))?;
        fs::write(repo.join("src/a.txt"), "1")?;
        fs::write(repo.join("other"), "x")?;
        commit(&repo, "one")?;
        git(&repo, &["checkout", "-qb", "side"])?;
        fs::write(repo.join("src/a.txt"), "2")?;
        commit(&repo, "two (side)")?;
        git(&repo, &["checkout", "-q", "main"])?;
        fs::write(repo.join("other"), "y")?;
        commit(&repo, "unrelated")?;
        git(&repo, &["merge", "-q", "--no-ff", "-m", "merge side", "side"])?;
        git(&repo, &["checkout", "-qb", "conflict"])?;
        fs::write(repo.join("src/a.txt"), "3")?;
        commit(&repo, "three (conflict)")?;
        git(&repo, &["checkout", "-q", "main"])?;
        fs::write(repo.join("src/a.txt"), "4")?;
        commit(&repo, "four")?;
        git(&repo, &["merge", "-q", "conflict"]).ok();
        fs::write(repo.join("src/a.txt"), "5")?;
        commit(&repo, "resolve")?;
        git(&repo, &["rm", "-q", "src/a.txt"])?;
        commit(&repo, "delete")?;
        let head = git(&repo, &["rev-parse", "HEAD"])?;
        let expected = git(&repo, &["log", "--format=%H", "--", "src/a.txt"])?;
        let expected = expected.lines().collect::<Vec<_>>();

        let gix = gix::open(&repo)?;
        let path = ["src".to_owned(), "a.txt".to_owned()];
        let head = gix::ObjectId::from_hex(head.as_bytes())?;

        let whole = page(&gix, &[head], &path, 100, 1000)?;
        assert_eq!(
            whole.changes.iter().map(ToString::to_string).collect::<Vec<_>>(),
            expected,
        );
        assert!(whole.frontier.is_empty());

        // resuming through the frontier reproduces the same sequence
        let mut frontier = vec![head];
        let mut paged = Vec::new();
        while !frontier.is_empty() {
            let result = page(&gix, &frontier, &path, 2, 2)?;
            paged.extend(result.changes.iter().map(ToString::to_string));
            frontier = result.frontier;
        }
        assert_eq!(paged, expected);
        Ok(())
    }
}