//! vcs-core for the hosted service, through a C ABI.
//!
//! The Worker owns storage. It loads objects into this module's cache
//! (`cache_put`), then calls an operation. Each project gets its own cache
//! slot (`cache_use`), since one isolate can serve several projects. An operation that reaches an
//! object the cache doesn't have answers `{"need": [ids]}`; the Worker loads
//! them and calls again (operations are deterministic). Answers are JSON in
//! the result buffer (`result_ptr`/`result_len`); objects an operation made
//! come back as a bundle from `take_new`.

use std::cell::RefCell;
use std::collections::{HashMap, HashSet, VecDeque};
use std::io::{Read, Write};

use serde::Deserialize;
use serde_json::{Value, json};
use sha1::{Digest, Sha1};
use vcs_core::bundle::{self, Frame, RAW, ZSTD};
use vcs_core::merge::{self, Mode};
use vcs_core::object::{Kind, Object, decode_chunks};
use vcs_core::tree::{self, EntryKind};
use vcs_core::{Error, Id, MemSource, Source, filter};

thread_local! {
    static CACHES: RefCell<HashMap<u32, Slot>> = RefCell::new(HashMap::new());
    static SLOT: std::cell::Cell<u32> = const { std::cell::Cell::new(0) };
    static NEW: RefCell<MemSource> = RefCell::new(MemSource::default());
    static RESULT: RefCell<Vec<u8>> = const { RefCell::new(Vec::new()) };
}

#[unsafe(no_mangle)]
pub extern "C" fn alloc(len: usize) -> *mut u8 {
    let mut buf = Vec::<u8>::with_capacity(len.max(1));
    let ptr = buf.as_mut_ptr();
    std::mem::forget(buf);
    ptr
}

/// # Safety
/// `ptr` and `len` must come from `alloc`.
#[unsafe(no_mangle)]
pub unsafe extern "C" fn dealloc(ptr: *mut u8, len: usize) {
    unsafe { drop(Vec::from_raw_parts(ptr, 0, len.max(1))) };
}

#[unsafe(no_mangle)]
pub extern "C" fn result_ptr() -> *const u8 {
    RESULT.with(|r| r.borrow().as_ptr())
}

#[unsafe(no_mangle)]
pub extern "C" fn result_len() -> usize {
    RESULT.with(|r| r.borrow().len())
}

fn set_result(bytes: Vec<u8>) {
    RESULT.with(|r| *r.borrow_mut() = bytes);
}

fn answer(value: Value) -> i32 {
    set_result(serde_json::to_vec(&value).unwrap_or_default());
    0
}

fn fail(message: String) -> i32 {
    set_result(serde_json::to_vec(&json!({ "error": message })).unwrap_or_default());
    -1
}

fn input<'a>(ptr: *const u8, len: usize) -> &'a [u8] {
    // SAFETY: the Worker passes a buffer it allocated with `alloc` and filled.
    unsafe { std::slice::from_raw_parts(ptr, len) }
}

struct Cache;

impl Source for Cache {
    fn get(&self, id: &Id) -> vcs_core::Result<Option<Object>> {
        if let Some(o) = NEW.with(|n| n.borrow().objects.get(id).cloned()) {
            return Ok(Some(o));
        }
        Ok(CACHES.with(|c| c.borrow().get(&SLOT.get()).and_then(|s| s.objects.get(id).cloned())))
    }
}

fn decode(frame: &Frame) -> Result<Vec<u8>, String> {
    match frame.codec {
        RAW => Ok(frame.payload.clone()),
        ZSTD => {
            let mut out = Vec::with_capacity(frame.raw_len as usize);
            ruzstd::decoding::StreamingDecoder::new(&frame.payload[..])
                .map_err(|e| format!("damaged object {}: {e}", frame.id.short()))?
                .read_to_end(&mut out)
                .map_err(|e| format!("damaged object {}: {e}", frame.id.short()))?;
            Ok(out)
        }
        _ => Err("unknown codec".into()),
    }
}

#[derive(Default)]
struct Slot {
    objects: HashMap<Id, Object>,
    bytes: usize,
}

fn insert(id: Id, object: Object) {
    let size = object.data.len() + 64;
    CACHES.with(|c| {
        let mut caches = c.borrow_mut();
        let slot = caches.entry(SLOT.get()).or_default();
        if slot.objects.insert(id, object).is_none() {
            slot.bytes += size;
        }
    });
}

/// Checks every object in a bundle, caching them when `cache`. Answers each
/// frame's place in the bundle, for the Worker's index.
fn take_bundle(bytes: &[u8], cache: bool) -> Result<Vec<Value>, String> {
    let frames = bundle::read(bytes).map_err(|e| e.to_string())?;
    let mut out = Vec::with_capacity(frames.len());
    let mut at = bundle::MAGIC.len();
    for frame in frames {
        let len = 50 + frame.payload.len();
        let data = decode(&frame)?;
        bundle::verify(&frame, &data).map_err(|e| e.to_string())?;
        out.push(json!({ "id": frame.id.hex(), "kind": frame.kind as u8, "off": at, "len": len, "raw": frame.raw_len }));
        at += len;
        if cache {
            insert(frame.id, Object::new(frame.kind, data));
        }
    }
    Ok(out)
}

/// Verifies a bundle (an upload) and answers where each frame is.
#[unsafe(no_mangle)]
pub extern "C" fn verify(ptr: *const u8, len: usize) -> i32 {
    match take_bundle(input(ptr, len), false) {
        Ok(frames) => answer(json!({ "frames": frames })),
        Err(e) => fail(e),
    }
}

/// Caches every object in a bundle (frames loaded from storage).
#[unsafe(no_mangle)]
pub extern "C" fn cache_put(ptr: *const u8, len: usize) -> i32 {
    match take_bundle(input(ptr, len), true) {
        Ok(frames) => answer(json!({ "cached": frames.len() })),
        Err(e) => fail(e),
    }
}

/// Selects the cache slot (one per project) later calls use.
#[unsafe(no_mangle)]
pub extern "C" fn cache_use(slot: u32) {
    SLOT.set(slot);
}

/// Empties one slot.
#[unsafe(no_mangle)]
pub extern "C" fn cache_drop(slot: u32) {
    CACHES.with(|c| c.borrow_mut().remove(&slot));
}

/// Cached bytes in every slot, in KiB.
#[unsafe(no_mangle)]
pub extern "C" fn cache_kib() -> u32 {
    CACHES.with(|c| (c.borrow().values().map(|s| s.bytes).sum::<usize>() / 1024) as u32)
}

/// The objects the last operation made, as a bundle (and forgets them).
#[unsafe(no_mangle)]
pub extern "C" fn take_new() -> i32 {
    let objects = NEW.with(|n| std::mem::take(&mut *n.borrow_mut()));
    let mut out = Vec::new();
    bundle::write_header(&mut out);
    for (id, o) in objects.objects {
        insert(id, o.clone());
        bundle::write_frame(&mut out, &Frame::raw(&o));
    }
    bundle::write_end(&mut out);
    set_result(out);
    0
}

fn parse<T: for<'de> Deserialize<'de>>(ptr: *const u8, len: usize) -> Result<T, String> {
    serde_json::from_slice(input(ptr, len)).map_err(|e| format!("bad request: {e}"))
}

fn id(text: &str) -> Result<Id, String> {
    Id::parse(text).ok_or_else(|| format!("not an object id: {text}"))
}

/// Runs an operation; a missing object becomes `{"need": [id]}`.
fn run(op: impl FnOnce() -> Result<Value, Error>) -> i32 {
    match op() {
        Ok(v) => answer(v),
        Err(Error::Missing(missing)) => answer(json!({ "need": [missing.hex()] })),
        Err(e) => fail(e.to_string()),
    }
}

#[derive(Deserialize)]
struct Roots {
    roots: Vec<String>,
}

/// Trees (and chunk lists) under `roots` that the cache doesn't have yet,
/// nearest first: the Worker loads these before an operation that walks
/// whole trees.
#[unsafe(no_mangle)]
pub extern "C" fn need_trees(ptr: *const u8, len: usize) -> i32 {
    let req: Roots = match parse(ptr, len) {
        Ok(r) => r,
        Err(e) => return fail(e),
    };
    let mut need = Vec::new();
    let mut seen = HashSet::new();
    let mut queue: VecDeque<Id> = VecDeque::new();
    for r in &req.roots {
        match id(r) {
            Ok(i) => queue.push_back(i),
            Err(e) => return fail(e),
        }
    }
    while let Some(t) = queue.pop_front() {
        if !seen.insert(t) {
            continue;
        }
        match Cache.get(&t) {
            Ok(Some(o)) if o.kind == Kind::Tree => {
                if let Ok(entries) = tree::decode(&o.data) {
                    for e in entries {
                        if e.kind == EntryKind::Tree {
                            queue.push_back(e.id);
                        }
                    }
                }
            }
            Ok(Some(_)) => {}
            _ => need.push(t.hex()),
        }
        if need.len() >= 2000 {
            break;
        }
    }
    answer(json!({ "need": need }))
}

#[derive(Deserialize)]
struct MergeReq {
    base: String,
    ours: String,
    theirs: String,
    #[serde(default)]
    labels: Vec<String>,
}

/// A landing's merge: `{"tree", "conflicts"}`.
#[unsafe(no_mangle)]
pub extern "C" fn merge(ptr: *const u8, len: usize) -> i32 {
    let req: MergeReq = match parse(ptr, len) {
        Ok(r) => r,
        Err(e) => return fail(e),
    };
    let (base, ours, theirs) = match (id(&req.base), id(&req.ours), id(&req.theirs)) {
        (Ok(a), Ok(b), Ok(c)) => (a, b, c),
        _ => return fail("bad ids".into()),
    };
    let labels = (req.labels.first().cloned().unwrap_or_else(|| "main".into()), req.labels.get(1).cloned().unwrap_or_else(|| "change".into()));
    run(|| {
        let m = merge::trees(&Cache, Some(&base), &ours, &theirs, Mode::Land, (&labels.0, &labels.1))?;
        if m.clean() {
            NEW.with(|n| *n.borrow_mut() = m.objects);
        }
        Ok(json!({ "tree": m.tree.hex(), "conflicts": m.conflicts }))
    })
}

#[derive(Deserialize)]
struct FilterReq {
    tree: String,
    hidden: Vec<String>,
}

#[unsafe(no_mangle)]
pub extern "C" fn filter_tree(ptr: *const u8, len: usize) -> i32 {
    let req: FilterReq = match parse(ptr, len) {
        Ok(r) => r,
        Err(e) => return fail(e),
    };
    let t = match id(&req.tree) {
        Ok(t) => t,
        Err(e) => return fail(e),
    };
    run(|| {
        let (out, objects) = filter::filter(&Cache, &t, &req.hidden)?;
        NEW.with(|n| {
            let mut n = n.borrow_mut();
            for o in objects {
                n.put(o);
            }
        });
        Ok(json!({ "tree": out.hex() }))
    })
}

#[derive(Deserialize)]
struct GraftReq {
    visible: String,
    full: String,
    hidden: Vec<String>,
}

#[unsafe(no_mangle)]
pub extern "C" fn graft_tree(ptr: *const u8, len: usize) -> i32 {
    let req: GraftReq = match parse(ptr, len) {
        Ok(r) => r,
        Err(e) => return fail(e),
    };
    let (v, f) = match (id(&req.visible), id(&req.full)) {
        (Ok(a), Ok(b)) => (a, b),
        _ => return fail("bad ids".into()),
    };
    run(|| match filter::graft(&Cache, &v, &f, &req.hidden)? {
        Ok((out, objects)) => {
            NEW.with(|n| {
                let mut n = n.borrow_mut();
                for o in objects {
                    n.put(o);
                }
            });
            Ok(json!({ "tree": out.hex() }))
        }
        Err(path) => Ok(json!({ "refused": path })),
    })
}

#[derive(Deserialize)]
struct SinceReq {
    tree: String,
    #[serde(default)]
    have: Option<String>,
}

/// Every object under `tree` that `have` doesn't share, chunks included.
#[unsafe(no_mangle)]
pub extern "C" fn new_since(ptr: *const u8, len: usize) -> i32 {
    let req: SinceReq = match parse(ptr, len) {
        Ok(r) => r,
        Err(e) => return fail(e),
    };
    let t = match id(&req.tree) {
        Ok(t) => t,
        Err(e) => return fail(e),
    };
    let have = match req.have.as_deref().map(id) {
        Some(Ok(h)) => Some(h),
        Some(Err(e)) => return fail(e),
        None => None,
    };
    run(|| {
        let mut ids = Vec::new();
        tree::new_since(&Cache, have.as_ref(), &t, &mut ids)?;
        let mut out = Vec::with_capacity(ids.len());
        let mut need = Vec::new();
        for i in ids {
            out.push(i.hex());
            // Chunk lists name chunks; the Worker knows a file's kind from
            // its index, so it asks for those lists separately.
            if let Some(o) = Cache.get(&i)?
                && o.kind == Kind::Chunks
            {
                for (c, _) in decode_chunks(&o.data)? {
                    out.push(c.hex());
                }
            } else if Cache.get(&i)?.is_none() {
                need.push(i.hex());
            }
        }
        Ok(json!({ "ids": out, "files_not_loaded": need }))
    })
}

#[derive(Deserialize)]
struct FlattenReq {
    tree: String,
}

/// Every file under a tree: `[[path, kind, id]]`.
#[unsafe(no_mangle)]
pub extern "C" fn flatten(ptr: *const u8, len: usize) -> i32 {
    let req: FlattenReq = match parse(ptr, len) {
        Ok(r) => r,
        Err(e) => return fail(e),
    };
    let t = match id(&req.tree) {
        Ok(t) => t,
        Err(e) => return fail(e),
    };
    run(|| {
        let files = tree::flatten(&Cache, &t)?;
        Ok(json!({ "files": files.iter().map(|(p, e)| json!([p, e.kind as u8, e.id.hex()])).collect::<Vec<_>>() }))
    })
}

// The git view: versions written as git objects, streamed as one pack.
//
// The Worker plans a version (`git_plan`) and looks up git IDs it already
// knows. It starts a pack (`pack_begin`), hashes each new file (`blob_begin`
// with write 0, `blob_feed` one stored frame at a time, `blob_end`), writes
// the trees and the commit (`git_trees`), which names the commit it pushes,
// then writes each new file into the pack (`blob_begin` with write 1) and
// closes it (`pack_end`). Pack bytes collect in a buffer the Worker drains
// with `pack_take`.

struct GitPack {
    sha: Sha1,
    out: Vec<u8>,
    blob: Option<GitBlob>,
}

struct GitBlob {
    sha: Sha1,
    /// None: only hashing (the git ID is needed before the pack is sent).
    z: Option<flate2::write::ZlibEncoder<Vec<u8>>>,
    size: u64,
    fed: u64,
}

thread_local! {
    static PACK: RefCell<Option<GitPack>> = const { RefCell::new(None) };
}

fn emit(pack: &mut GitPack, bytes: &[u8]) {
    pack.sha.update(bytes);
    pack.out.extend_from_slice(bytes);
}

/// A pack entry's header: type and size.
fn entry_header(kind: u8, size: u64) -> Vec<u8> {
    let mut out = Vec::with_capacity(10);
    let mut byte = (kind << 4) | (size & 0x0f) as u8;
    let mut rest = size >> 4;
    while rest > 0 {
        out.push(byte | 0x80);
        byte = (rest & 0x7f) as u8;
        rest >>= 7;
    }
    out.push(byte);
    out
}

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

fn git_header(kind: &str, size: u64) -> Vec<u8> {
    format!("{kind} {size}\0").into_bytes()
}

/// Adds a whole object (trees, commits) to the pack; answers its git ID.
fn emit_object(pack: &mut GitPack, kind: &str, type_code: u8, data: &[u8]) -> String {
    let mut h = Sha1::new();
    h.update(git_header(kind, data.len() as u64));
    h.update(data);
    let id = hex(&h.finalize());
    let mut z = flate2::write::ZlibEncoder::new(Vec::new(), flate2::Compression::fast());
    let _ = z.write_all(data);
    let deflated = z.finish().unwrap_or_default();
    emit(pack, &entry_header(type_code, data.len() as u64));
    emit(pack, &deflated);
    id
}

fn with_pack(f: impl FnOnce(&mut GitPack) -> Result<Value, String>) -> i32 {
    let result = PACK.with(|p| match p.borrow_mut().as_mut() {
        Some(pack) => f(pack),
        None => Err("no pack started".into()),
    });
    match result {
        Ok(v) => answer(v),
        Err(e) => fail(e),
    }
}

#[unsafe(no_mangle)]
pub extern "C" fn pack_begin(count: u32) -> i32 {
    let mut pack = GitPack { sha: Sha1::new(), out: Vec::new(), blob: None };
    let mut head = b"PACK".to_vec();
    head.extend_from_slice(&2u32.to_be_bytes());
    head.extend_from_slice(&count.to_be_bytes());
    emit(&mut pack, &head);
    PACK.with(|p| *p.borrow_mut() = Some(pack));
    answer(json!({}))
}

/// Pack bytes made so far (and forgets them).
#[unsafe(no_mangle)]
pub extern "C" fn pack_take() -> i32 {
    let bytes = PACK.with(|p| p.borrow_mut().as_mut().map(|pack| std::mem::take(&mut pack.out)).unwrap_or_default());
    set_result(bytes);
    0
}

/// Ends the pack: the last bytes, with the checksum.
#[unsafe(no_mangle)]
pub extern "C" fn pack_end() -> i32 {
    let Some(mut pack) = PACK.with(|p| p.borrow_mut().take()) else { return fail("no pack started".into()) };
    if pack.blob.is_some() {
        return fail("a file is still open".into());
    }
    let sum = pack.sha.finalize();
    pack.out.extend_from_slice(&sum);
    set_result(pack.out);
    0
}

/// Starts a file of `size` bytes (a JS number: files under 2^53 bytes).
/// With `write` 0 the file is only hashed; with 1 it goes into the pack.
#[unsafe(no_mangle)]
pub extern "C" fn blob_begin(size: f64, write: u32) -> i32 {
    let size = size as u64;
    with_pack(|pack| {
        if pack.blob.is_some() {
            return Err("a file is already open".into());
        }
        let mut sha = Sha1::new();
        sha.update(git_header("blob", size));
        let z = if write != 0 {
            emit(pack, &entry_header(3, size));
            Some(flate2::write::ZlibEncoder::new(Vec::new(), flate2::Compression::fast()))
        } else {
            None
        };
        pack.blob = Some(GitBlob { sha, z, size, fed: 0 });
        Ok(json!({}))
    })
}

/// One stored frame of the open file: the whole blob, or its next chunk.
#[unsafe(no_mangle)]
pub extern "C" fn blob_feed(ptr: *const u8, len: usize) -> i32 {
    let frame = match one_frame(input(ptr, len)) {
        Ok(f) => f,
        Err(e) => return fail(e),
    };
    with_pack(|pack| {
        let data = decode(&frame)?;
        bundle::verify(&frame, &data).map_err(|e| e.to_string())?;
        let blob = pack.blob.as_mut().ok_or("no file open")?;
        blob.sha.update(&data);
        blob.fed += data.len() as u64;
        if let Some(z) = blob.z.as_mut() {
            z.write_all(&data).map_err(|e| e.to_string())?;
            let out = std::mem::take(z.get_mut());
            emit(pack, &out);
        }
        Ok(json!({}))
    })
}

#[unsafe(no_mangle)]
pub extern "C" fn blob_end() -> i32 {
    with_pack(|pack| {
        let blob = pack.blob.take().ok_or("no file open")?;
        if blob.fed != blob.size {
            return Err(format!("file was {} bytes, expected {}", blob.fed, blob.size));
        }
        if let Some(z) = blob.z {
            let rest = z.finish().map_err(|e| e.to_string())?;
            emit(pack, &rest);
        }
        Ok(json!({ "git": hex(&blob.sha.finalize()) }))
    })
}

/// One frame as stored in a pack (no bundle header).
fn one_frame(bytes: &[u8]) -> Result<Frame, String> {
    let mut b = Vec::with_capacity(bundle::MAGIC.len() + bytes.len() + 32);
    bundle::write_header(&mut b);
    b.extend_from_slice(bytes);
    bundle::write_end(&mut b);
    let mut frames = bundle::read(&b).map_err(|e| e.to_string())?;
    if frames.len() != 1 {
        return Err("expected one object".into());
    }
    Ok(frames.remove(0))
}

/// A big file's chunk list (one stored frame): `{"chunks": [[id, size]], "size"}`.
#[unsafe(no_mangle)]
pub extern "C" fn chunk_list(ptr: *const u8, len: usize) -> i32 {
    let result = (|| {
        let frame = one_frame(input(ptr, len))?;
        let data = decode(&frame)?;
        bundle::verify(&frame, &data).map_err(|e| e.to_string())?;
        if frame.kind != Kind::Chunks {
            return Err("not a chunk list".to_string());
        }
        let chunks = decode_chunks(&data).map_err(|e| e.to_string())?;
        let size: u64 = chunks.iter().map(|(_, n)| n).sum();
        Ok(json!({ "chunks": chunks.iter().map(|(c, n)| json!([c.hex(), n])).collect::<Vec<_>>(), "size": size }))
    })();
    match result {
        Ok(v) => answer(v),
        Err(e) => fail(e),
    }
}

#[derive(Deserialize)]
struct PlanReq {
    tree: String,
    #[serde(default)]
    have: Option<String>,
    /// IDs whose git form isn't known: treated as new.
    #[serde(default)]
    force: Vec<String>,
}

#[derive(Default)]
struct Plan {
    trees: Vec<Id>,
    files: Vec<Id>,
    lookup: Vec<Id>,
    seen: HashSet<Id>,
    looked: HashSet<Id>,
}

fn plan_tree(t: &Id, have: Option<&Id>, force: &HashSet<Id>, plan: &mut Plan) -> Result<(), Error> {
    if !plan.seen.insert(*t) {
        return Ok(());
    }
    plan.trees.push(*t);
    let old: HashMap<String, tree::TreeEntry> = match have {
        Some(h) => tree::read(&Cache, h)?.into_iter().map(|e| (e.name.clone(), e)).collect(),
        None => HashMap::new(),
    };
    for e in tree::read(&Cache, t)? {
        let before = old.get(&e.name);
        if before.is_some_and(|b| b.id == e.id) && !force.contains(&e.id) {
            if plan.looked.insert(e.id) {
                plan.lookup.push(e.id);
            }
            continue;
        }
        if e.kind == EntryKind::Tree {
            // A forced tree is rebuilt whole.
            let old_sub = if force.contains(&e.id) { None } else { before.filter(|b| b.kind == EntryKind::Tree).map(|b| b.id) };
            plan_tree(&e.id, old_sub.as_ref(), force, plan)?;
        } else if plan.seen.insert(e.id) {
            plan.files.push(e.id);
        }
    }
    Ok(())
}

/// What a version adds over the one before it, for git: new trees, new
/// files, and unchanged entries whose git IDs the Worker looks up.
#[unsafe(no_mangle)]
pub extern "C" fn git_plan(ptr: *const u8, len: usize) -> i32 {
    let req: PlanReq = match parse(ptr, len) {
        Ok(r) => r,
        Err(e) => return fail(e),
    };
    let root = match id(&req.tree) {
        Ok(t) => t,
        Err(e) => return fail(e),
    };
    let have = match req.have.as_deref().map(id) {
        Some(Ok(h)) => Some(h),
        Some(Err(e)) => return fail(e),
        None => None,
    };
    let force: HashSet<Id> = req.force.iter().filter_map(|f| Id::parse(f)).collect();
    run(|| {
        let mut plan = Plan::default();
        if have == Some(root) && !force.contains(&root) {
            plan.lookup.push(root);
        } else {
            let have = if force.contains(&root) { None } else { have };
            plan_tree(&root, have.as_ref(), &force, &mut plan)?;
        }
        let list = |ids: &[Id]| ids.iter().map(|i| i.hex()).collect::<Vec<_>>();
        Ok(json!({ "trees": list(&plan.trees), "files": list(&plan.files), "lookup": list(&plan.lookup) }))
    })
}

#[derive(Deserialize)]
struct TreesReq {
    tree: String,
    /// The plan's new trees: each is written to the pack once.
    trees: Vec<String>,
    /// Native ID → git ID for everything else the trees name.
    known: HashMap<String, String>,
    parent: Option<String>,
    message: String,
    author: String,
    time: i64,
}

fn git_tree(t: &Id, fresh: &HashSet<Id>, known: &HashMap<String, String>, made: &mut HashMap<Id, String>, pack: &mut GitPack) -> Result<String, Error> {
    if let Some(g) = made.get(t) {
        return Ok(g.clone());
    }
    if !fresh.contains(t) {
        return known.get(&t.hex()).cloned().ok_or_else(|| Error::Corrupt(format!("git id of tree {} isn't known", t.short())));
    }
    // Git sorts entries by name, with folders compared as if they end in '/'.
    let mut rows: Vec<(Vec<u8>, Vec<u8>)> = Vec::new();
    for e in tree::read(&Cache, t)? {
        let (mode, gid) = match e.kind {
            EntryKind::Tree => ("40000", git_tree(&e.id, fresh, known, made, pack)?),
            kind => {
                let gid = known.get(&e.id.hex()).cloned().ok_or_else(|| Error::Corrupt(format!("git id of file {} isn't known", e.id.short())))?;
                (match kind {
                    EntryKind::Exec => "100755",
                    EntryKind::Link => "120000",
                    _ => "100644",
                }, gid)
            }
        };
        let mut key = e.name.as_bytes().to_vec();
        if mode == "40000" {
            key.push(b'/');
        }
        let mut row = format!("{mode} {}", e.name).into_bytes();
        row.push(0);
        for i in (0..gid.len()).step_by(2) {
            row.push(u8::from_str_radix(&gid[i..i + 2], 16).map_err(|_| Error::Corrupt("bad git id".into()))?);
        }
        rows.push((key, row));
    }
    rows.sort_by(|a, b| a.0.cmp(&b.0));
    let data: Vec<u8> = rows.into_iter().flat_map(|(_, r)| r).collect();
    let g = emit_object(pack, "tree", 2, &data);
    made.insert(*t, g.clone());
    Ok(g)
}

/// Writes the version's new trees and its commit to the pack.
#[unsafe(no_mangle)]
pub extern "C" fn git_trees(ptr: *const u8, len: usize) -> i32 {
    let req: TreesReq = match parse(ptr, len) {
        Ok(r) => r,
        Err(e) => return fail(e),
    };
    let root = match id(&req.tree) {
        Ok(t) => t,
        Err(e) => return fail(e),
    };
    let fresh: HashSet<Id> = req.trees.iter().filter_map(|t| Id::parse(t)).collect();
    // Every new tree is loaded first, so nothing reaches the pack twice.
    let need: Vec<String> = fresh.iter().filter(|t| Cache.get(t).ok().flatten().is_none()).map(|t| t.hex()).collect();
    if !need.is_empty() {
        return answer(json!({ "need": need }));
    }
    with_pack(|pack| {
        let mut made = HashMap::new();
        let tree_id = git_tree(&root, &fresh, &req.known, &mut made, pack).map_err(|e| e.to_string())?;
        if made.len() != fresh.len() {
            return Err(format!("wrote {} trees, planned {}", made.len(), fresh.len()));
        }
        let (name, email) = match req.author.split_once(" <") {
            Some((n, e)) => (n.to_string(), e.trim_end_matches('>').to_string()),
            None => (req.author.clone(), "vcs@localhost".into()),
        };
        let mut commit = format!("tree {tree_id}\n");
        if let Some(p) = &req.parent {
            commit.push_str(&format!("parent {p}\n"));
        }
        commit.push_str(&format!("author {name} <{email}> {} +0000\ncommitter {name} <{email}> {} +0000\n\n{}", req.time, req.time, req.message));
        if !commit.ends_with('\n') {
            commit.push('\n');
        }
        let commit_id = emit_object(pack, "commit", 1, commit.as_bytes());
        let trees: HashMap<String, String> = made.into_iter().map(|(k, v)| (k.hex(), v)).collect();
        Ok(json!({ "commit": commit_id, "tree": tree_id, "trees": trees }))
    })
}


#[cfg(test)]
mod tests {
    use super::*;
    use vcs_core::tree::{Entry, Files};

    fn sha1_git(kind: &str, data: &[u8]) -> String {
        let mut h = Sha1::new();
        h.update(git_header(kind, data.len() as u64));
        h.update(data);
        hex(&h.finalize())
    }

    #[test]
    fn git_ids_match_git() {
        // `printf 'hello\n' | git hash-object --stdin`
        assert_eq!(sha1_git("blob", b"hello\n"), "ce013625030ba8dba906f756967f9e9ca394464a");
    }

    fn feed(o: &Object) {
        let mut b = Vec::new();
        bundle::write_frame(&mut b, &Frame::raw(o));
        assert_eq!(blob_feed(b.as_ptr(), b.len()), 0);
    }

    fn result() -> Vec<u8> {
        RESULT.with(|r| r.borrow().clone())
    }

    fn call_json(f: extern "C" fn(*const u8, usize) -> i32, v: Value) -> Value {
        let b = serde_json::to_vec(&v).unwrap();
        assert_eq!(f(b.as_ptr(), b.len()), 0, "{}", String::from_utf8_lossy(&result()));
        serde_json::from_slice(&result()).unwrap()
    }

    /// A version's pack is one git accepts, with the IDs git computes.
    #[test]
    fn git_pack_is_git() {
        let small = Object::blob(b"fn main() {}\n".to_vec());
        let big: Vec<u8> = (0..3_000_000u32).map(|i| (i.wrapping_mul(2654435761) >> 13) as u8).collect();
        let big_parts = vcs_core::chunk::file_objects(&big);
        let big_id = big_parts[0].id();
        let mut files = Files::new();
        files.insert("src/main.rs".into(), Entry { kind: EntryKind::File, id: small.id() });
        files.insert("run.sh".into(), Entry { kind: EntryKind::Exec, id: small.id() });
        files.insert("data/big.bin".into(), Entry { kind: EntryKind::File, id: big_id });
        let (root, trees) = tree::build(&files);
        cache_drop(0);
        for t in &trees {
            insert(t.id(), t.clone());
        }
        let plan = call_json(git_plan, json!({ "tree": root.hex() }));
        let new_trees: Vec<String> = serde_json::from_value(plan["trees"].clone()).unwrap();
        let new_files: Vec<String> = serde_json::from_value(plan["files"].clone()).unwrap();
        assert_eq!(new_trees.len(), 3);
        assert_eq!(new_files.len(), 2);

        assert_eq!(pack_begin((new_trees.len() + new_files.len() + 1) as u32), 0);
        let mut known = HashMap::new();
        let list = big_parts.iter().find(|o| o.kind == Kind::Chunks).unwrap();
        let chunks: HashMap<Id, &Object> = big_parts.iter().map(|o| (o.id(), o)).collect();
        let mut files_pass = |write: u32, pack: &mut Vec<u8>| -> Vec<String> {
            let mut ids = Vec::new();
            assert_eq!(blob_begin(small.data.len() as f64, write), 0);
            feed(&small);
            assert_eq!(blob_end(), 0);
            let v: Value = serde_json::from_slice(&result()).unwrap();
            ids.push(v["git"].as_str().unwrap().to_string());
            assert_eq!(blob_begin(big.len() as f64, write), 0);
            for (c, _) in decode_chunks(&list.data).unwrap() {
                feed(chunks[&c]);
                pack_take();
                pack.extend(result());
            }
            assert_eq!(blob_end(), 0);
            let v: Value = serde_json::from_slice(&result()).unwrap();
            ids.push(v["git"].as_str().unwrap().to_string());
            ids
        };
        let mut pack = Vec::new();
        let hashed = files_pass(0, &mut pack);
        known.insert(small.id().hex(), hashed[0].clone());
        known.insert(big_id.hex(), hashed[1].clone());
        let done = call_json(
            git_trees,
            json!({ "tree": root.hex(), "trees": new_trees, "known": known, "parent": null, "message": "First\n", "author": "Ada <ada@example.com>", "time": 1700000000 }),
        );
        let written = files_pass(1, &mut pack);
        assert_eq!(hashed, written);
        pack_take();
        pack.extend(result());
        assert_eq!(pack_end(), 0);
        pack.extend(result());
        let dir = std::env::temp_dir().join(format!("vcs-wasm-git-{}", std::process::id()));
        let _ = std::fs::remove_dir_all(&dir);
        std::fs::create_dir_all(&dir).unwrap();
        let git = |args: &[&str], input: Option<&[u8]>| -> String {
            let mut c = std::process::Command::new("git");
            c.args(args).current_dir(&dir).stdin(std::process::Stdio::piped()).stdout(std::process::Stdio::piped());
            let mut child = c.spawn().unwrap();
            if let Some(i) = input {
                child.stdin.take().unwrap().write_all(i).unwrap();
            } else {
                drop(child.stdin.take());
            }
            let out = child.wait_with_output().unwrap();
            assert!(out.status.success(), "git {args:?} failed");
            String::from_utf8(out.stdout).unwrap()
        };
        git(&["init", "-q", "--bare", "."], None);
        git(&["index-pack", "--stdin", "--strict"], Some(&pack));
        let commit = done["commit"].as_str().unwrap();
        git(&["update-ref", "refs/heads/main", commit], None);
        git(&["fsck", "--strict", "--no-dangling"], None);
        let listing = git(&["ls-tree", "-r", "main"], None);
        assert!(listing.contains("100755 blob") && listing.contains("run.sh"), "{listing}");
        assert_eq!(git(&["cat-file", "-p", "main:src/main.rs"], None), "fn main() {}\n");
        assert_eq!(git(&["cat-file", "-s", "main:data/big.bin"], None).trim(), big.len().to_string());
        let _ = std::fs::remove_dir_all(&dir);
    }
}