//! Git objects and packs, as far as a commit without a checkout needs: read a pack (deltas
//! included), hash objects, read and write trees, write a pack of whole objects.

use std::collections::BTreeMap;

use miniz_oxide::inflate::TINFLStatus;
use miniz_oxide::inflate::core::{DecompressorOxide, decompress, inflate_flags};

pub const COMMIT: u8 = 1;
pub const TREE: u8 = 2;
pub const BLOB: u8 = 3;
const TAG: u8 = 4;
const OFS_DELTA: u8 = 6;
const REF_DELTA: u8 = 7;

pub const DIR: &str = "40000";

/// An object by hex id: its kind and content.
pub type Objects = BTreeMap<String, (u8, Vec<u8>)>;

fn kind_name(kind: u8) -> Result<&'static str, String> {
    Ok(match kind {
        COMMIT => "commit",
        TREE => "tree",
        BLOB => "blob",
        TAG => "tag",
        _ => return Err(format!("not an object kind: {kind}")),
    })
}

pub fn hex(bytes: &[u8]) -> String {
    bytes.iter().map(|b| format!("{b:02x}")).collect()
}

fn unhex(text: &str) -> Result<Vec<u8>, String> {
    let bad = || format!("not a hex object id: {text}");
    if text.len() != 40 {
        return Err(bad());
    }
    (0..40).step_by(2).map(|i| u8::from_str_radix(&text[i..i + 2], 16).map_err(|_| bad())).collect()
}

/// The object id git gives `data` of `kind`.
pub fn id(kind: u8, data: &[u8]) -> Result<String, String> {
    let mut sha = sha1_smol::Sha1::new();
    sha.update(format!("{} {}\0", kind_name(kind)?, data.len()).as_bytes());
    sha.update(data);
    Ok(sha.digest().to_string())
}

/// Every object in a pack, deltas resolved. A REF_DELTA base may come from `outside`.
pub fn read_pack(pack: &[u8], outside: &Objects) -> Result<Objects, String> {
    if pack.len() < 32 || &pack[..4] != b"PACK" {
        return Err("not a git pack".into());
    }
    let count = u32::from_be_bytes(pack[8..12].try_into().unwrap()) as usize;
    let body = &pack[..pack.len() - 20];
    if sha1_smol::Sha1::from(body).digest().bytes() != pack[pack.len() - 20..] {
        return Err("the pack's checksum does not match".into());
    }
    enum Raw {
        Whole(u8, Vec<u8>),
        Ofs(usize, Vec<u8>),
        Ref(String, Vec<u8>),
    }
    let mut at = 12;
    let next = |at: &mut usize| -> Result<u8, String> {
        let b = *body.get(*at).ok_or("the pack ends early")?;
        *at += 1;
        Ok(b)
    };
    let mut raws: Vec<(usize, Raw)> = Vec::with_capacity(count);
    for _ in 0..count {
        let start = at;
        let mut c = next(&mut at)?;
        let kind = (c >> 4) & 7;
        let mut size = (c & 15) as usize;
        let mut shift = 4;
        while c & 0x80 != 0 {
            c = next(&mut at)?;
            size |= ((c & 0x7f) as usize) << shift;
            shift += 7;
        }
        let (ofs, sha) = match kind {
            OFS_DELTA => {
                let mut c = next(&mut at)?;
                let mut off = (c & 0x7f) as usize;
                while c & 0x80 != 0 {
                    c = next(&mut at)?;
                    off = ((off + 1) << 7) | (c & 0x7f) as usize;
                }
                (Some(start.checked_sub(off).ok_or("a delta's base is before the pack")?), None)
            }
            REF_DELTA => {
                let sha = body.get(at..at + 20).ok_or("the pack ends early")?;
                at += 20;
                (None, Some(hex(sha)))
            }
            _ => (None, None),
        };
        let (data, used) = inflate(&body[at..], size)?;
        at += used;
        raws.push((
            start,
            match (ofs, sha) {
                (Some(base), _) => Raw::Ofs(base, data),
                (_, Some(sha)) => Raw::Ref(sha, data),
                _ => Raw::Whole(kind, data),
            },
        ));
    }
    // Resolve in rounds: each round settles the deltas whose base has settled.
    let mut by_pos: BTreeMap<usize, (u8, Vec<u8>)> = BTreeMap::new();
    let mut objects = Objects::new();
    let mut pending: Vec<(usize, Raw)> = Vec::new();
    for (pos, raw) in raws {
        match raw {
            Raw::Whole(kind, data) => {
                objects.insert(id(kind, &data)?, (kind, data.clone()));
                by_pos.insert(pos, (kind, data));
            }
            raw => pending.push((pos, raw)),
        }
    }
    while !pending.is_empty() {
        let before = pending.len();
        let mut left = Vec::new();
        for (pos, raw) in pending {
            let base = match &raw {
                Raw::Ofs(base, _) => by_pos.get(base).cloned(),
                Raw::Ref(sha, _) => objects.get(sha).or_else(|| outside.get(sha)).cloned(),
                Raw::Whole(..) => unreachable!(),
            };
            let Some((kind, base)) = base else {
                left.push((pos, raw));
                continue;
            };
            let (Raw::Ofs(_, delta) | Raw::Ref(_, delta)) = &raw else { unreachable!() };
            let data = undelta(&base, delta)?;
            objects.insert(id(kind, &data)?, (kind, data.clone()));
            by_pos.insert(pos, (kind, data));
        }
        if left.len() == before {
            return Err("the pack has deltas against objects it does not hold".into());
        }
        pending = left;
    }
    Ok(objects)
}

/// One zlib stream of `size` bytes, and how many input bytes it took.
fn inflate(input: &[u8], size: usize) -> Result<(Vec<u8>, usize), String> {
    let mut out = vec![0; size.max(1)];
    let mut state = DecompressorOxide::new();
    let flags = inflate_flags::TINFL_FLAG_PARSE_ZLIB_HEADER | inflate_flags::TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF;
    let (status, used, written) = decompress(&mut state, input, &mut out, 0, flags);
    if status != TINFLStatus::Done || written != size {
        return Err(format!("a pack object does not inflate ({status:?})"));
    }
    out.truncate(size);
    Ok((out, used))
}

fn undelta(base: &[u8], delta: &[u8]) -> Result<Vec<u8>, String> {
    let bad = || "a broken delta".to_string();
    let mut at = 0;
    let varint = |at: &mut usize| -> Result<usize, String> {
        let (mut n, mut shift) = (0usize, 0);
        loop {
            let b = *delta.get(*at).ok_or_else(bad)?;
            *at += 1;
            n |= ((b & 0x7f) as usize) << shift;
            shift += 7;
            if b & 0x80 == 0 {
                return Ok(n);
            }
        }
    };
    if varint(&mut at)? != base.len() {
        return Err(bad());
    }
    let size = varint(&mut at)?;
    let mut out = Vec::with_capacity(size);
    while at < delta.len() {
        let op = delta[at];
        at += 1;
        if op & 0x80 != 0 {
            let (mut off, mut len) = (0usize, 0usize);
            for i in 0..4 {
                if op & (1 << i) != 0 {
                    off |= (*delta.get(at).ok_or_else(bad)? as usize) << (8 * i);
                    at += 1;
                }
            }
            for i in 0..3 {
                if op & (0x10 << i) != 0 {
                    len |= (*delta.get(at).ok_or_else(bad)? as usize) << (8 * i);
                    at += 1;
                }
            }
            if len == 0 {
                len = 0x10000;
            }
            out.extend_from_slice(base.get(off..off + len).ok_or_else(bad)?);
        } else if op != 0 {
            out.extend_from_slice(delta.get(at..at + op as usize).ok_or_else(bad)?);
            at += op as usize;
        } else {
            return Err(bad());
        }
    }
    if out.len() != size {
        return Err(bad());
    }
    Ok(out)
}

/// A pack of whole objects (no deltas), as `git index-pack` takes it.
pub fn write_pack(objects: &[(u8, Vec<u8>)]) -> Vec<u8> {
    let mut pack = b"PACK".to_vec();
    pack.extend_from_slice(&2u32.to_be_bytes());
    pack.extend_from_slice(&(objects.len() as u32).to_be_bytes());
    for (kind, data) in objects {
        let mut size = data.len();
        let mut c = (kind << 4) | (size & 15) as u8;
        size >>= 4;
        while size > 0 {
            pack.push(c | 0x80);
            c = (size & 0x7f) as u8;
            size >>= 7;
        }
        pack.push(c);
        pack.extend(miniz_oxide::deflate::compress_to_vec_zlib(data, 6));
    }
    let sum = sha1_smol::Sha1::from(&pack).digest().bytes();
    pack.extend_from_slice(&sum);
    pack
}

/// One tree entry: mode (as git writes it, `40000` for a tree) and hex id.
#[derive(Clone, Debug, PartialEq)]
pub struct Entry {
    pub mode: String,
    pub id: String,
}

pub fn read_tree(data: &[u8]) -> Result<BTreeMap<String, Entry>, String> {
    let mut entries = BTreeMap::new();
    let mut at = 0;
    while at < data.len() {
        let space = data[at..].iter().position(|&b| b == b' ').ok_or("a broken tree")? + at;
        let nul = data[space..].iter().position(|&b| b == 0).ok_or("a broken tree")? + space;
        let id = data.get(nul + 1..nul + 21).ok_or("a broken tree")?;
        let mode = String::from_utf8_lossy(&data[at..space]).into_owned();
        let name = String::from_utf8(data[space + 1..nul].to_vec()).map_err(|_| "a tree entry's name is not UTF-8")?;
        entries.insert(name, Entry { mode, id: hex(id) });
        at = nul + 21;
    }
    Ok(entries)
}

/// A tree's bytes, in git's order: a tree's name sorts as if it ended in `/`.
pub fn write_tree(entries: &BTreeMap<String, Entry>) -> Result<Vec<u8>, String> {
    let mut sorted: Vec<_> = entries.iter().collect();
    let key = |(name, e): &(&String, &Entry)| {
        let mut k = name.as_bytes().to_vec();
        if e.mode == DIR {
            k.push(b'/');
        }
        k
    };
    sorted.sort_by_key(key);
    let mut out = Vec::new();
    for (name, e) in sorted {
        out.extend_from_slice(format!("{} {name}\0", e.mode).as_bytes());
        out.extend(unhex(&e.id)?);
    }
    Ok(out)
}

/// A commit's tree.
pub fn commit_tree(data: &[u8]) -> Result<String, String> {
    let text = String::from_utf8_lossy(data);
    let id = text.lines().next().and_then(|l| l.strip_prefix("tree ")).ok_or("a commit with no tree")?;
    unhex(id)?;
    Ok(id.to_string())
}