//! Git, read without git: a pack as a git server sends it, commits and
//! trees, and git trees turned into Onset trees the way `on import` makes
//! them, so the same git tree always becomes the same Onset tree.

use std::collections::HashMap;

use sha1::{Digest, Sha1};

use crate::tree::{self, EntryKind, TreeEntry};
use crate::{Error, Id, Object, Result, chunk, corrupt};

pub type GitId = [u8; 20];

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum GitKind {
    Commit,
    Tree,
    Blob,
    Tag,
}

impl GitKind {
    fn from_code(code: u8) -> Option<GitKind> {
        Some(match code {
            1 => GitKind::Commit,
            2 => GitKind::Tree,
            3 => GitKind::Blob,
            4 => GitKind::Tag,
            _ => return None,
        })
    }

    fn name(self) -> &'static str {
        match self {
            GitKind::Commit => "commit",
            GitKind::Tree => "tree",
            GitKind::Blob => "blob",
            GitKind::Tag => "tag",
        }
    }
}

/// A git object's ID: SHA-1 of its header and content.
pub fn object_id(kind: GitKind, data: &[u8]) -> GitId {
    let mut h = Sha1::new();
    h.update(format!("{} {}\0", kind.name(), data.len()));
    h.update(data);
    h.finalize().into()
}

pub fn hex(id: &GitId) -> String {
    id.iter().map(|b| format!("{b:02x}")).collect()
}

pub fn parse_id(text: &str) -> Option<GitId> {
    let t = text.trim();
    if t.len() != 40 {
        return None;
    }
    let mut out = [0u8; 20];
    for (i, b) in out.iter_mut().enumerate() {
        *b = u8::from_str_radix(t.get(i * 2..i * 2 + 2)?, 16).ok()?;
    }
    Some(out)
}

/// Every object in a pack, deltas applied.
#[derive(Default)]
pub struct Pack {
    pub objects: HashMap<GitId, (GitKind, Vec<u8>)>,
}

enum Raw {
    Whole(GitKind, Vec<u8>),
    /// A delta on the object at this offset in the pack.
    OnOffset(usize, Vec<u8>),
    /// A delta on the object with this ID.
    OnId(GitId, Vec<u8>),
}

/// Reads a pack. It has to carry every object its deltas are made on (a
/// thin pack doesn't), and its objects can add up to at most `max_bytes`.
pub fn read_pack(bytes: &[u8], max_bytes: usize) -> Result<Pack> {
    if bytes.len() < 32 || &bytes[..4] != b"PACK" {
        return Err(corrupt("not a git pack"));
    }
    let version = u32::from_be_bytes(bytes[4..8].try_into().unwrap());
    if version != 2 && version != 3 {
        return Err(corrupt(format!("git pack version {version}")));
    }
    let count = u32::from_be_bytes(bytes[8..12].try_into().unwrap()) as usize;
    let end = bytes.len() - 20;
    if Sha1::digest(&bytes[..end]).as_slice() != &bytes[end..] {
        return Err(corrupt("git pack checksum doesn't match"));
    }
    let byte = |at: usize| bytes.get(at).copied().filter(|_| at < end).ok_or_else(|| corrupt("git pack ends early"));
    let mut inflater = flate2::Decompress::new(true);
    let mut raws: Vec<Raw> = Vec::with_capacity(count.min(1 << 20));
    let mut at_offset: HashMap<usize, usize> = HashMap::with_capacity(count.min(1 << 20));
    let mut total = 0usize;
    let mut at = 12;
    for i in 0..count {
        let start = at;
        let mut c = byte(at)?;
        at += 1;
        let code = (c >> 4) & 7;
        let mut size = (c & 15) as usize;
        let mut shift = 4;
        while c & 0x80 != 0 {
            c = byte(at)?;
            at += 1;
            if shift > 60 {
                return Err(corrupt("bad size in git pack"));
            }
            size |= ((c & 0x7f) as usize) << shift;
            shift += 7;
        }
        total = total.saturating_add(size);
        if total > max_bytes {
            return Err(Error::Limit(format!("git objects over {max_bytes} bytes")));
        }
        let raw = match code {
            1..=4 => {
                let (data, used) = inflate(&mut inflater, &bytes[at..end], size)?;
                at += used;
                Raw::Whole(GitKind::from_code(code).unwrap(), data)
            }
            6 => {
                let mut c = byte(at)?;
                at += 1;
                let mut back = (c & 0x7f) as usize;
                while c & 0x80 != 0 {
                    c = byte(at)?;
                    at += 1;
                    back = back.checked_add(1).and_then(|b| b.checked_mul(128)).ok_or_else(|| corrupt("bad delta offset"))? | (c & 0x7f) as usize;
                }
                let base = start.checked_sub(back).ok_or_else(|| corrupt("delta before the pack"))?;
                let (data, used) = inflate(&mut inflater, &bytes[at..end], size)?;
                at += used;
                Raw::OnOffset(base, data)
            }
            7 => {
                let base: GitId = bytes.get(at..at + 20).filter(|_| at + 20 <= end).ok_or_else(|| corrupt("git pack ends early"))?.try_into().unwrap();
                at += 20;
                let (data, used) = inflate(&mut inflater, &bytes[at..end], size)?;
                at += used;
                Raw::OnId(base, data)
            }
            _ => return Err(corrupt(format!("git object type {code}"))),
        };
        at_offset.insert(start, i);
        raws.push(raw);
    }
    // Deltas on earlier objects resolve in one pass; deltas on later ones
    // (allowed, by ID) take more.
    let mut done: Vec<Option<(GitKind, GitId)>> = vec![None; raws.len()];
    let mut pack = Pack::default();
    let mut made = 0usize;
    let mut left = raws.len();
    while left > 0 {
        let before = left;
        for i in 0..raws.len() {
            if done[i].is_some() {
                continue;
            }
            let resolved = match &mut raws[i] {
                Raw::Whole(kind, data) => Some((*kind, std::mem::take(data))),
                Raw::OnOffset(base, delta) => {
                    let b = *at_offset.get(base).ok_or_else(|| corrupt("delta on a missing object"))?;
                    match done[b] {
                        Some((kind, id)) => Some((kind, apply_delta(&pack.objects[&id].1, delta, max_bytes - made)?)),
                        None => None,
                    }
                }
                Raw::OnId(base, delta) => match pack.objects.get(base) {
                    Some((kind, data)) => Some((*kind, apply_delta(data, delta, max_bytes - made)?)),
                    None => None,
                },
            };
            if let Some((kind, data)) = resolved {
                made = made.saturating_add(data.len());
                if made > max_bytes {
                    return Err(Error::Limit(format!("git objects over {max_bytes} bytes")));
                }
                // The delta isn't needed once applied.
                raws[i] = Raw::Whole(kind, Vec::new());
                let id = object_id(kind, &data);
                pack.objects.insert(id, (kind, data));
                done[i] = Some((kind, id));
                left -= 1;
            }
        }
        if left == before {
            return Err(corrupt("a delta's base isn't in the pack"));
        }
    }
    Ok(pack)
}

fn inflate(z: &mut flate2::Decompress, input: &[u8], size: usize) -> Result<(Vec<u8>, usize)> {
    z.reset(true);
    let mut out = Vec::with_capacity(size + 64);
    loop {
        let used = z.total_in() as usize;
        let status = z.decompress_vec(&input[used..], &mut out, flate2::FlushDecompress::Finish).map_err(|e| corrupt(format!("git pack: {e}")))?;
        if status == flate2::Status::StreamEnd {
            break;
        }
        if out.len() > size {
            return Err(corrupt("git object bigger than its header says"));
        }
        if z.total_in() as usize == input.len() {
            return Err(corrupt("git pack ends early"));
        }
        out.reserve(64);
    }
    if out.len() != size {
        return Err(corrupt("git object's size doesn't match its header"));
    }
    Ok((out, z.total_in() as usize))
}

fn varint(data: &[u8], at: &mut usize) -> Result<usize> {
    let mut value = 0usize;
    let mut shift = 0;
    loop {
        let b = *data.get(*at).ok_or_else(|| corrupt("bad delta"))?;
        *at += 1;
        if shift > 60 {
            return Err(corrupt("bad delta"));
        }
        value |= ((b & 0x7f) as usize) << shift;
        shift += 7;
        if b & 0x80 == 0 {
            return Ok(value);
        }
    }
}

/// A git delta making `target` from `base`: what they start and end with in
/// common is copied, the middle inserted. That's all a folder with one entry
/// changed needs; None when the delta wouldn't be much smaller than `target`.
pub fn make_delta(base: &[u8], target: &[u8]) -> Option<Vec<u8>> {
    let prefix = base.iter().zip(target).take_while(|(a, b)| a == b).count();
    let room = base.len().min(target.len()) - prefix;
    let suffix = base.iter().rev().zip(target.iter().rev()).take(room).take_while(|(a, b)| a == b).count();
    let middle = &target[prefix..target.len() - suffix];
    if middle.len() + 64 > target.len() / 2 {
        return None;
    }
    let mut out = Vec::with_capacity(middle.len() + middle.len() / 127 + 32);
    let size = |out: &mut Vec<u8>, mut n: usize| {
        loop {
            let byte = (n & 0x7f) as u8;
            n >>= 7;
            if n == 0 {
                out.push(byte);
                break;
            }
            out.push(byte | 0x80);
        }
    };
    size(&mut out, base.len());
    size(&mut out, target.len());
    let copy = |out: &mut Vec<u8>, mut off: usize, mut len: usize| {
        while len > 0 {
            let n = len.min(0xff_ffff);
            let mut op = 0x80u8;
            let mut args = Vec::with_capacity(7);
            for i in 0..4 {
                let b = ((off >> (8 * i)) & 0xff) as u8;
                if b != 0 {
                    op |= 1 << i;
                    args.push(b);
                }
            }
            for i in 0..3 {
                let b = ((n >> (8 * i)) & 0xff) as u8;
                if b != 0 {
                    op |= 0x10 << i;
                    args.push(b);
                }
            }
            out.push(op);
            out.extend_from_slice(&args);
            off += n;
            len -= n;
        }
    };
    copy(&mut out, 0, prefix);
    for part in middle.chunks(127) {
        out.push(part.len() as u8);
        out.extend_from_slice(part);
    }
    copy(&mut out, base.len() - suffix, suffix);
    Some(out)
}

/// Git's delta format: copies from the base and inserted bytes. What it
/// makes can be at most `max` bytes.
pub fn apply_delta(base: &[u8], delta: &[u8], max: usize) -> Result<Vec<u8>> {
    let mut at = 0;
    if varint(delta, &mut at)? != base.len() {
        return Err(corrupt("delta made on another object"));
    }
    let size = varint(delta, &mut at)?;
    if size > max {
        return Err(Error::Limit(format!("a git object over {max} bytes")));
    }
    // The size it claims is only room to start with, not trusted.
    let mut out = Vec::with_capacity(size.min(base.len().saturating_add(delta.len())));
    while at < delta.len() {
        let op = delta[at];
        at += 1;
        if op & 0x80 != 0 {
            let mut off = 0usize;
            let mut len = 0usize;
            for i in 0..4 {
                if op & (1 << i) != 0 {
                    off |= (*delta.get(at).ok_or_else(|| corrupt("bad delta"))? as usize) << (8 * i);
                    at += 1;
                }
            }
            for i in 0..3 {
                if op & (0x10 << i) != 0 {
                    len |= (*delta.get(at).ok_or_else(|| corrupt("bad delta"))? as usize) << (8 * i);
                    at += 1;
                }
            }
            if len == 0 {
                len = 0x10000;
            }
            out.extend_from_slice(base.get(off..off.checked_add(len).ok_or_else(|| corrupt("bad delta"))?).ok_or_else(|| corrupt("delta copies past its base"))?);
        } else if op != 0 {
            out.extend_from_slice(delta.get(at..at + op as usize).ok_or_else(|| corrupt("bad delta"))?);
            at += op as usize;
        } else {
            return Err(corrupt("bad delta"));
        }
        if out.len() > size {
            return Err(corrupt("delta makes more than it says"));
        }
    }
    if out.len() != size {
        return Err(corrupt("delta makes less than it says"));
    }
    Ok(out)
}

#[derive(Debug, Clone, PartialEq)]
pub struct Commit {
    pub tree: GitId,
    pub parents: Vec<GitId>,
    /// "Name <email>"
    pub author: String,
    pub time: i64,
    pub title: String,
    pub body: String,
}

impl Commit {
    pub fn parse(data: &[u8]) -> Result<Commit> {
        let text = String::from_utf8_lossy(data);
        let (head, message) = text.split_once("\n\n").unwrap_or((&text, ""));
        let mut tree = None;
        let mut parents = Vec::new();
        let mut author = String::new();
        let mut time = 0;
        for line in head.lines() {
            if let Some(t) = line.strip_prefix("tree ") {
                tree = parse_id(t);
            } else if let Some(p) = line.strip_prefix("parent ") {
                parents.push(parse_id(p).ok_or_else(|| corrupt("bad parent in a git commit"))?);
            } else if let Some(a) = line.strip_prefix("author ") {
                // "Name <email> 1700000000 +0000"
                let mut parts = a.rsplitn(3, ' ');
                let _zone = parts.next();
                time = parts.next().and_then(|t| t.parse().ok()).unwrap_or(0);
                author = parts.next().unwrap_or("").to_string();
            }
        }
        let mut lines = message.trim().splitn(2, '\n');
        Ok(Commit {
            tree: tree.ok_or_else(|| corrupt("git commit without a tree"))?,
            parents,
            author,
            time,
            title: lines.next().unwrap_or("").trim().to_string(),
            body: lines.next().unwrap_or("").trim().to_string(),
        })
    }
}

/// A git tree's entries: (mode, name, id).
pub fn tree_entries(data: &[u8]) -> Result<Vec<(Vec<u8>, Vec<u8>, GitId)>> {
    let mut out = Vec::new();
    let mut at = 0;
    while at < data.len() {
        let space = data[at..].iter().position(|&b| b == b' ').ok_or_else(|| corrupt("bad git tree"))? + at;
        let nul = data[space + 1..].iter().position(|&b| b == 0).ok_or_else(|| corrupt("bad git tree"))? + space + 1;
        let id: GitId = data.get(nul + 1..nul + 21).ok_or_else(|| corrupt("bad git tree"))?.try_into().unwrap();
        out.push((data[at..space].to_vec(), data[space + 1..nul].to_vec(), id));
        at = nul + 21;
    }
    Ok(out)
}

/// The commits from `to` back to `from` on the first-parent line, oldest
/// first. None when `from` isn't on that line.
pub fn first_parents(pack: &Pack, from: &GitId, to: &GitId, limit: usize) -> Result<Option<Vec<(GitId, Commit)>>> {
    let mut out = Vec::new();
    let mut at = *to;
    while at != *from {
        let Some((GitKind::Commit, data)) = pack.objects.get(&at) else { return Ok(None) };
        if out.len() >= limit {
            return Ok(None);
        }
        let commit = Commit::parse(data)?;
        let next = commit.parents.first().copied();
        out.push((at, commit));
        match next {
            Some(p) => at = p,
            None => return Ok(None),
        }
    }
    out.reverse();
    Ok(Some(out))
}

/// Whether `to` has `from` in its history. The pack holds every commit
/// `to` has that `from` doesn't, so a line that leaves the pack anywhere
/// but at `from` reached history `from` already had.
pub fn descends(pack: &Pack, from: &GitId, to: &GitId) -> Result<bool> {
    let mut stack = vec![*to];
    let mut seen = std::collections::HashSet::new();
    while let Some(c) = stack.pop() {
        if c == *from {
            return Ok(true);
        }
        if !seen.insert(c) {
            continue;
        }
        if let Some((GitKind::Commit, data)) = pack.objects.get(&c) {
            stack.extend(Commit::parse(data)?.parents);
        }
    }
    Ok(false)
}

/// Git trees as Onset trees. Trees and files outside the pack come from
/// `known` (git ID → Onset ID); ones in neither are listed in `unknown`.
pub struct ToOnset<'a> {
    pack: &'a Pack,
    known: &'a HashMap<GitId, Id>,
    trees: HashMap<GitId, Option<Id>>,
    files: HashMap<GitId, Id>,
    /// New Onset objects.
    pub objects: Vec<Object>,
    /// Onset ID → git ID of what was converted, for the git view.
    pub ids: Vec<(Id, GitId)>,
    pub unknown: Vec<GitId>,
}

impl<'a> ToOnset<'a> {
    pub fn new(pack: &'a Pack, known: &'a HashMap<GitId, Id>) -> ToOnset<'a> {
        ToOnset { pack, known, trees: HashMap::new(), files: HashMap::new(), objects: Vec::new(), ids: Vec::new(), unknown: Vec::new() }
    }

    /// A git tree as a Onset tree (None: nothing left in it, for a folder
    /// other than the root). Names that aren't UTF-8 or aren't a
    /// [`tree::safe_name`] are left out, as `on import` does.
    pub fn tree(&mut self, sha: GitId, root: bool) -> Result<Option<Id>> {
        if let Some(t) = self.trees.get(&sha) {
            return Ok(*t);
        }
        let data = match self.pack.objects.get(&sha) {
            Some((GitKind::Tree, data)) => data,
            Some(_) => return Err(corrupt(format!("git object {} isn't a tree", hex(&sha)))),
            None => {
                return Ok(match self.known.get(&sha) {
                    Some(id) => Some(*id),
                    None => {
                        self.unknown.push(sha);
                        None
                    }
                });
            }
        };
        let mut entries = Vec::new();
        for (mode, name, id) in tree_entries(data)? {
            let Ok(name) = String::from_utf8(name) else { continue };
            if !tree::safe_name(&name) {
                continue;
            }
            let (kind, id) = match mode.as_slice() {
                b"40000" | b"040000" => match self.tree(id, false)? {
                    Some(t) => (EntryKind::Tree, t),
                    None => continue,
                },
                // A submodule: the commit it points at, kept as it is.
                b"160000" => (EntryKind::Gitlink, self.content(hex(&id).as_bytes())),
                b"120000" => (EntryKind::Link, self.file(id)),
                m if m.ends_with(b"755") => (EntryKind::Exec, self.file(id)),
                _ => (EntryKind::File, self.file(id)),
            };
            entries.push(TreeEntry { name, kind, id });
        }
        let out = if entries.is_empty() && !root {
            None
        } else {
            let object = Object::new(crate::Kind::Tree, tree::encode(&entries));
            let id = object.id();
            self.objects.push(object);
            self.ids.push((id, sha));
            Some(id)
        };
        self.trees.insert(sha, out);
        Ok(out)
    }

    fn file(&mut self, sha: GitId) -> Id {
        if let Some(f) = self.files.get(&sha) {
            return *f;
        }
        let id = match self.pack.objects.get(&sha) {
            Some((_, data)) => {
                let data = data.clone();
                let id = self.content(&data);
                self.ids.push((id, sha));
                id
            }
            None => match self.known.get(&sha) {
                Some(id) => *id,
                None => {
                    self.unknown.push(sha);
                    tree::empty_id()
                }
            },
        };
        self.files.insert(sha, id);
        id
    }

    fn content(&mut self, data: &[u8]) -> Id {
        let parts = chunk::file_objects(data);
        let id = parts[0].id();
        self.objects.extend(parts);
        id
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::io::Write;

    fn deflate(data: &[u8]) -> Vec<u8> {
        let mut z = flate2::write::ZlibEncoder::new(Vec::new(), flate2::Compression::fast());
        z.write_all(data).unwrap();
        z.finish().unwrap()
    }

    fn header(code: u8, size: usize) -> Vec<u8> {
        let mut out = Vec::new();
        let mut b = (code << 4) | (size & 15) as u8;
        let mut rest = size >> 4;
        while rest > 0 {
            out.push(b | 0x80);
            b = (rest & 0x7f) as u8;
            rest >>= 7;
        }
        out.push(b);
        out
    }

    fn finish(mut pack: Vec<u8>, count: u32) -> Vec<u8> {
        pack[8..12].copy_from_slice(&count.to_be_bytes());
        let sum = Sha1::digest(&pack);
        pack.extend_from_slice(&sum);
        pack
    }

    #[test]
    fn made_deltas_apply() {
        let base: Vec<u8> = (0..200_000u32).map(|i| (i * 7 % 251) as u8).collect();
        let mut target = base.clone();
        target.splice(70_000..70_040, b"one entry changed, a little longer than it was".iter().copied());
        let delta = make_delta(&base, &target).unwrap();
        assert!(delta.len() < 200);
        assert_eq!(apply_delta(&base, &delta, usize::MAX).unwrap(), target);
        // Changed at the start, at the end, grown, shrunk.
        for t in [[b"x".to_vec(), base[1..].to_vec()].concat(), [base[..base.len() - 1].to_vec(), b"yz".to_vec()].concat(), base[..150_000].to_vec(), [base.clone(), base[..70_000].to_vec()].concat()] {
            if let Some(d) = make_delta(&base, &t) {
                assert_eq!(apply_delta(&base, &d, usize::MAX).unwrap(), t);
            }
        }
        // Nothing in common: no delta.
        assert!(make_delta(b"abcdefgh", b"zyxwvuts").is_none());
    }

    #[test]
    fn reads_whole_objects_and_deltas() {
        let base = b"hello world, hello git\n".repeat(10);
        let target = [&base[..], b"one more line\n"].concat();
        // A delta: copy all of base, then insert the new line.
        let mut delta = vec![base.len() as u8 | 0x80, (base.len() >> 7) as u8, target.len() as u8 | 0x80, (target.len() >> 7) as u8];
        delta.extend_from_slice(&[0x80 | 0x01 | 0x10, 0, base.len() as u8]);
        delta.push(14);
        delta.extend_from_slice(b"one more line\n");
        assert_eq!(apply_delta(&base, &delta, 1 << 20).unwrap(), target);

        let mut pack = b"PACK\0\0\0\x02\0\0\0\0".to_vec();
        let base_at = pack.len();
        pack.extend(header(3, base.len()));
        pack.extend(deflate(&base));
        let delta_at = pack.len();
        pack.extend(header(6, delta.len()));
        let back = delta_at - base_at;
        assert!(back < 128);
        pack.push(back as u8);
        pack.extend(deflate(&delta));
        pack.extend(header(7, delta.len()));
        pack.extend(object_id(GitKind::Blob, &base));
        pack.extend(deflate(&delta));
        let pack = finish(pack, 3);
        let read = read_pack(&pack, 1 << 20).unwrap();
        assert_eq!(read.objects.len(), 2);
        assert_eq!(read.objects[&object_id(GitKind::Blob, &target)].1, target);
        assert!(read_pack(&pack, 100).is_err());
        let mut bad = pack.clone();
        bad[20] ^= 1;
        assert!(read_pack(&bad, 1 << 20).is_err());
    }

    /// A pack git itself makes, deltas and all, reads back to every object.
    #[test]
    fn reads_what_git_packs() {
        use std::process::Command;
        let dir = std::env::temp_dir().join(format!("onset-git-pack-{}", std::process::id()));
        let _ = std::fs::remove_dir_all(&dir);
        std::fs::create_dir_all(&dir).unwrap();
        let git = |args: &[&str]| Command::new("git").args(["-c", "user.name=T", "-c", "user.email=t@example.com", "-c", "commit.gpgsign=false"]).args(args).current_dir(&dir).output();
        if git(&["init", "-q"]).is_err() {
            return; // No git here.
        }
        let mut text = String::new();
        for i in 0..40 {
            text.push_str(&format!("line {i} of a file that changes a little each time\n"));
            std::fs::write(dir.join("a.txt"), &text).unwrap();
            std::fs::write(dir.join(format!("f{}.txt", i % 5)), format!("{i}\n")).unwrap();
            git(&["add", "-A"]).unwrap();
            git(&["commit", "-qm", &format!("Commit {i}")]).unwrap();
        }
        let pack = Command::new("sh").arg("-c").arg("echo HEAD | git pack-objects --stdout --revs --delta-base-offset").current_dir(&dir).output().unwrap().stdout;
        let all = String::from_utf8(git(&["rev-list", "--objects", "--all"]).unwrap().stdout).unwrap();
        let read = read_pack(&pack, 1 << 24).unwrap();
        assert_eq!(read.objects.len(), all.lines().count());
        for line in all.lines() {
            assert!(read.objects.contains_key(&parse_id(&line[..40]).unwrap()), "{line}");
        }
        let head = parse_id(&String::from_utf8(git(&["rev-parse", "HEAD"]).unwrap().stdout).unwrap()).unwrap();
        let line = first_parents(&read, &[0; 20], &head, 100).unwrap();
        assert!(line.is_none(), "the root commit has no parent to stop at");
        let root = parse_id(&String::from_utf8(git(&["rev-list", "--max-parents=0", "HEAD"]).unwrap().stdout).unwrap()).unwrap();
        let line = first_parents(&read, &root, &head, 100).unwrap().unwrap();
        assert_eq!(line.len(), 39);
        assert_eq!(line.last().unwrap().1.title, "Commit 39");
        assert!(descends(&read, &root, &head).unwrap());
        let _ = std::fs::remove_dir_all(&dir);
    }

    #[test]
    fn commits_and_trees_become_onset_trees() {
        let blob = b"fn main() {}\n".to_vec();
        let blob_id = object_id(GitKind::Blob, &blob);
        let mut sub = Vec::new();
        sub.extend_from_slice(b"100755 run.sh\0");
        sub.extend_from_slice(&blob_id);
        let sub_id = object_id(GitKind::Tree, &sub);
        let outside: GitId = [7; 20];
        let mut root = Vec::new();
        root.extend_from_slice(b"100644 main.rs\0");
        root.extend_from_slice(&blob_id);
        root.extend_from_slice(b"40000 bin\0");
        root.extend_from_slice(&sub_id);
        root.extend_from_slice(b"160000 lib\0");
        root.extend_from_slice(&[9; 20]);
        root.extend_from_slice(b"100644 old.txt\0");
        root.extend_from_slice(&outside);
        let root_id = object_id(GitKind::Tree, &root);
        let commit = format!("tree {}\nparent {}\nauthor Ada <ada@example.com> 1700000000 +0100\ncommitter Ada <ada@example.com> 1700000000 +0100\n\nFix the build\n\nIt was broken.\n", hex(&root_id), hex(&[1; 20]));
        let parsed = Commit::parse(commit.as_bytes()).unwrap();
        assert_eq!((parsed.tree, parsed.parents.clone(), parsed.author.as_str(), parsed.time), (root_id, vec![[1; 20]], "Ada <ada@example.com>", 1_700_000_000));
        assert_eq!((parsed.title.as_str(), parsed.body.as_str()), ("Fix the build", "It was broken."));

        let mut pack = Pack::default();
        for (kind, data) in [(GitKind::Blob, blob.clone()), (GitKind::Tree, sub), (GitKind::Tree, root)] {
            pack.objects.insert(object_id(kind, &data), (kind, data));
        }
        let none = HashMap::new();
        let mut first = ToOnset::new(&pack, &none);
        first.tree(root_id, true).unwrap();
        assert_eq!(first.unknown, vec![outside]);

        let old = Object::blob(b"old\n".to_vec()).id();
        let known = HashMap::from([(outside, old)]);
        let mut to = ToOnset::new(&pack, &known);
        let out = to.tree(root_id, true).unwrap().unwrap();
        assert!(to.unknown.is_empty());
        let mut src = crate::MemSource::default();
        for o in to.objects.drain(..) {
            src.put(o);
        }
        src.put(Object::blob(b"old\n".to_vec()));
        let files = tree::flatten(&src, &out).unwrap();
        assert_eq!(files.keys().cloned().collect::<Vec<_>>(), vec!["bin/run.sh", "lib", "main.rs", "old.txt"]);
        assert_eq!(files["bin/run.sh"].kind, EntryKind::Exec);
        assert_eq!(files["lib"].kind, EntryKind::Gitlink);
        assert_eq!(chunk::read_file(&src, &files["lib"].id).unwrap(), hex(&[9; 20]).as_bytes());
        assert_eq!(files["main.rs"].id, Object::blob(blob).id());
        assert!(to.ids.contains(&(out, root_id)));
    }
}