//! Three-way merges: text line by line, JSON by key, and whole trees.
//!
//! The orientation is the same everywhere: `ours` is main and `theirs` is
//! the change being landed or synced. On the server ([`Mode::Land`]) any
//! conflict stops the landing. In a workspace ([`Mode::Sync`]) text conflicts
//! are written into the file with markers, and conflicts that can't be marked
//! (binary files, a file deleted on one side) keep the change's side and say
//! so.

use std::collections::BTreeMap;

use serde_json::Value;

use crate::{chunk, rename, smart};
use crate::diff::{Hunk, hunks, is_binary, lines};
use crate::object::{Kind, Object};
use crate::tree::{self, EntryKind, TreeEntry};
use crate::{Id, Layered, MemSource, Result, Source};

/// The result of a text merge.
pub struct TextMerge {
    pub content: Vec<u8>,
    pub conflicts: usize,
}

/// Line-by-line three-way merge. Changes on both sides to the same or
/// touching lines are a conflict unless they're identical.
pub fn text(base: &[u8], ours: &[u8], theirs: &[u8], ours_label: &str, theirs_label: &str) -> TextMerge {
    text_with(base, ours, theirs, ours_label, theirs_label, &|_, _, _, _| None, &|_| false)
}

/// Settles a spot both sides changed, from the base's lines there, each
/// side's text and the base's lines just before and after the spot: the
/// merged text, or None for a conflict.
type Resolve<'a> = &'a dyn Fn(&[&[u8]], &[u8], &[u8], (Option<&[u8]>, Option<&[u8]>)) -> Option<Vec<u8>>;

/// `force`: the change's hunks to show as conflicts even where main didn't
/// change those lines (see `mark_twice`).
fn text_with(base: &[u8], ours: &[u8], theirs: &[u8], ours_label: &str, theirs_label: &str, resolve: Resolve, force: &dyn Fn(&Hunk) -> bool) -> TextMerge {
    let b = lines(base);
    let o = lines(ours);
    let t = lines(theirs);
    let ho = hunks(base, ours);
    let ht = hunks(base, theirs);
    let mut out = Vec::with_capacity(ours.len().max(theirs.len()));
    let mut conflicts = 0;
    let (mut i, mut j) = (0, 0);
    let mut pos: u32 = 0;
    while i < ho.len() || j < ht.len() {
        // Start a group at the earliest hunk.
        let take_ours = j >= ht.len() || (i < ho.len() && ho[i].before.start <= ht[j].before.start);
        let first = if take_ours { &ho[i] } else { &ht[j] };
        let lo = first.before.start;
        let mut hi = first.before.end;
        let (gi, gj) = (i, j);
        if take_ours {
            i += 1;
        } else {
            j += 1;
        }
        // Absorb every hunk that overlaps or touches the group.
        loop {
            if i < ho.len() && ho[i].before.start <= hi {
                hi = hi.max(ho[i].before.end);
                i += 1;
            } else if j < ht.len() && ht[j].before.start <= hi {
                hi = hi.max(ht[j].before.end);
                j += 1;
            } else {
                break;
            }
        }
        for line in &b[pos as usize..lo as usize] {
            out.extend_from_slice(line);
        }
        let ours_hunks = &ho[gi..i];
        let theirs_hunks = &ht[gj..j];
        let side = |hs: &[Hunk], other: &[&[u8]]| -> Vec<u8> {
            let mut text = Vec::new();
            let mut p = lo;
            for h in hs {
                for line in &b[p as usize..h.before.start as usize] {
                    text.extend_from_slice(line);
                }
                for line in &other[h.after.start as usize..h.after.end as usize] {
                    text.extend_from_slice(line);
                }
                p = h.before.end;
            }
            for line in &b[p as usize..hi as usize] {
                text.extend_from_slice(line);
            }
            text
        };
        let forced = theirs_hunks.iter().any(force);
        if theirs_hunks.is_empty() {
            out.extend_from_slice(&side(ours_hunks, &o));
        } else if ours_hunks.is_empty() && !forced {
            out.extend_from_slice(&side(theirs_hunks, &t));
        } else {
            let a = side(ours_hunks, &o);
            let c = side(theirs_hunks, &t);
            if a == c {
                out.extend_from_slice(&a);
            } else if let Some(merged) = (!forced)
                .then(|| resolve(&b[lo as usize..hi as usize], &a, &c, ((lo > 0).then(|| b[lo as usize - 1]), b.get(hi as usize).copied())))
                .flatten()
            {
                out.extend_from_slice(&merged);
            } else {
                conflicts += 1;
                if !out.is_empty() && !out.ends_with(b"\n") {
                    out.push(b'\n');
                }
                out.extend_from_slice(format!("<<<<<<< {ours_label}\n").as_bytes());
                out.extend_from_slice(&a);
                if !a.is_empty() && !a.ends_with(b"\n") {
                    out.push(b'\n');
                }
                out.extend_from_slice(b"=======\n");
                out.extend_from_slice(&c);
                if !c.is_empty() && !c.ends_with(b"\n") {
                    out.push(b'\n');
                }
                out.extend_from_slice(format!(">>>>>>> {theirs_label}\n").as_bytes());
            }
        }
        pos = hi;
    }
    for line in &b[pos as usize..] {
        out.extend_from_slice(line);
    }
    TextMerge { content: out, conflicts }
}

/// Merges JSON objects key by key. None when the files aren't all JSON
/// objects or both sides changed the same key differently.
pub fn json(base: Option<&[u8]>, ours: &[u8], theirs: &[u8]) -> Option<Vec<u8>> {
    let parse = |b: &[u8]| serde_json::from_slice::<Value>(b).ok();
    let o = parse(ours)?;
    let t = parse(theirs)?;
    let b = match base {
        Some(b) => parse(b)?,
        None => Value::Object(Default::default()),
    };
    if !(o.is_object() && t.is_object() && b.is_object()) {
        return None;
    }
    let merged = json_value(Some(&b), Some(&o), Some(&t))??;
    // Write it back in ours' style.
    let text = String::from_utf8_lossy(ours);
    let indent = text
        .lines()
        .skip(1)
        .find(|l| l.starts_with([' ', '\t']))
        .map(|l| l.chars().take_while(|c| *c == ' ' || *c == '\t').collect::<String>())
        .unwrap_or_else(|| "  ".into());
    let mut out = Vec::new();
    let formatter = serde_json::ser::PrettyFormatter::with_indent(indent.as_bytes());
    let mut ser = serde_json::Serializer::with_formatter(&mut out, formatter);
    serde::Serialize::serialize(&merged, &mut ser).ok()?;
    if ours.ends_with(b"\n") {
        out.push(b'\n');
    }
    Some(out)
}

/// Some(None): the key is gone. None: a conflict.
fn json_value(b: Option<&Value>, o: Option<&Value>, t: Option<&Value>) -> Option<Option<Value>> {
    if o == t {
        return Some(o.cloned());
    }
    if b == o {
        return Some(t.cloned());
    }
    if b == t {
        return Some(o.cloned());
    }
    let (Some(Value::Object(om)), Some(Value::Object(tm))) = (o, t) else { return None };
    let empty = serde_json::Map::new();
    let bm = match b {
        Some(Value::Object(m)) => m,
        None => &empty,
        _ => return None,
    };
    let mut out = serde_json::Map::new();
    for (k, ov) in om {
        if let Some(v) = json_value(bm.get(k), Some(ov), tm.get(k))? {
            out.insert(k.clone(), v);
        }
    }
    // Keys only theirs has, placed after the key they follow in theirs.
    let keys: Vec<&String> = tm.keys().collect();
    for (idx, k) in keys.iter().enumerate() {
        if om.contains_key(*k) || bm.contains_key(*k) {
            if !om.contains_key(*k) {
                // Deleted on ours: handled above only for keys ours has.
                if let Some(v) = json_value(bm.get(*k), None, tm.get(*k))? {
                    out.insert((*k).clone(), v);
                }
            }
            continue;
        }
        let value = tm[*k].clone();
        let after = keys[..idx].iter().rev().find(|p| out.contains_key(**p)).map(|p| (*p).clone());
        insert_after(&mut out, after.as_deref(), (*k).clone(), value);
    }
    Some(Some(Value::Object(out)))
}

fn insert_after(map: &mut serde_json::Map<String, Value>, after: Option<&str>, key: String, value: Value) {
    let Some(after) = after else {
        // Theirs put it first.
        let rest = std::mem::take(map);
        map.insert(key, value);
        map.extend(rest);
        return;
    };
    let rest: Vec<(String, Value)> = std::mem::take(map).into_iter().collect();
    for (k, v) in rest {
        let hit = k == after;
        map.insert(k, v);
        if hit {
            map.insert(key.clone(), value.clone());
        }
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Mode {
    /// Landing on the server: any conflict stops it.
    Land,
    /// Syncing a workspace: conflicts are written into files.
    Sync,
}

/// A conflict the merge found.
#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
pub struct Conflict {
    pub path: String,
    /// text, binary, deleted, type, or duplicate (both sides declare one thing).
    pub kind: String,
    /// What a duplicate is ("both sides declare helper").
    #[serde(default, skip_serializing_if = "Option::is_none")]
    pub detail: Option<String>,
}

/// Something sync resolved on its own that the person should know about.
#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
pub struct Note {
    pub path: String,
    pub message: String,
}

pub struct TreeMerge {
    pub tree: Id,
    /// Objects the merge created (merged blobs and trees).
    pub objects: MemSource,
    pub conflicts: Vec<Conflict>,
    pub notes: Vec<Note>,
}

impl TreeMerge {
    pub fn clean(&self) -> bool {
        self.conflicts.is_empty()
    }
}

/// Merges trees: `base` is where the change started, `ours` is main and
/// `theirs` is the change.
pub fn trees(src: &dyn Source, base: Option<&Id>, ours: &Id, theirs: &Id, mode: Mode, labels: (&str, &str)) -> Result<TreeMerge> {
    let mut m = Merger { src, mode, labels, objects: MemSource::default(), conflicts: Vec::new(), notes: Vec::new() };
    let empty = tree::empty_id();
    m.objects.put(tree::empty());
    let base = base.copied().unwrap_or(empty);
    // A file one side moved and the other edited: the edit moves with it.
    let (base, ours, theirs) = m.follow_renames(&base, ours, theirs)?;
    let tree = m.merge_tree(&base, &ours, &theirs, "")?;
    Ok(TreeMerge { tree, objects: m.objects, conflicts: m.conflicts, notes: m.notes })
}

struct Merger<'a> {
    src: &'a dyn Source,
    mode: Mode,
    labels: (&'a str, &'a str),
    objects: MemSource,
    conflicts: Vec<Conflict>,
    notes: Vec<Note>,
}

impl Merger<'_> {
    fn read(&self, id: &Id) -> Result<Vec<TreeEntry>> {
        let src = Layered { first: &self.objects, second: self.src };
        tree::read(&src, id)
    }

    fn file(&self, id: &Id) -> Result<Object> {
        let src = Layered { first: &self.objects, second: self.src };
        src.must(id)
    }

    /// Where one side moved a file the other side edited (and didn't move),
    /// the edited side and the base get the file at its new name too, so the
    /// edit merges there instead of conflicting with a delete.
    fn follow_renames(&mut self, base: &Id, ours: &Id, theirs: &Id) -> Result<(Id, Id, Id)> {
        if base == ours || base == theirs || ours == theirs {
            return Ok((*base, *ours, *theirs));
        }
        let (mut b, mut o, mut t) = (*base, *ours, *theirs);
        let src = Layered { first: &self.objects, second: self.src };
        let ours_changes = tree::diff_trees(&src, base, ours)?;
        let theirs_changes = tree::diff_trees(&src, base, theirs)?;
        let mut moves: Vec<(bool, String, String, tree::Entry, tree::Entry)> = Vec::new();
        for (theirs_moved, moved, edited) in [(true, &theirs_changes, &ours_changes), (false, &ours_changes, &theirs_changes)] {
            for (from, to) in rename::renames(&src, moved)? {
                if let Some(tree::Change::Modified(before, after)) = edited.get(&from)
                    && !edited.contains_key(&to)
                {
                    moves.push((theirs_moved, from, to, *before, *after));
                }
            }
        }
        for (theirs_moved, from, to, before, after) in moves {
            let src = Layered { first: &self.objects, second: self.src };
            let (nb, made_b) = rename::moved(&src, &b, &from, &to, before)?;
            let (ne, made_e) = rename::moved(&src, if theirs_moved { &o } else { &t }, &from, &to, after)?;
            for obj in made_b.into_iter().chain(made_e) {
                self.objects.put(obj);
            }
            b = nb;
            if theirs_moved {
                o = ne;
            } else {
                t = ne;
            }
            let who = if theirs_moved { "your change" } else { "main" };
            self.notes.push(Note { path: to.clone(), message: format!("{who} moved {from} to {to}; the other side's edits to it came along") });
        }
        Ok((b, o, t))
    }

    fn merge_tree(&mut self, base: &Id, ours: &Id, theirs: &Id, prefix: &str) -> Result<Id> {
        if ours == theirs || base == theirs {
            return Ok(*ours);
        }
        if base == ours {
            return Ok(*theirs);
        }
        let map = |es: Vec<TreeEntry>| es.into_iter().map(|e| (e.name.clone(), e)).collect::<BTreeMap<_, _>>();
        let b = map(self.read(base)?);
        let o = map(self.read(ours)?);
        let t = map(self.read(theirs)?);
        let mut names: Vec<&String> = b.keys().chain(o.keys()).chain(t.keys()).collect();
        names.sort();
        names.dedup();
        let mut out = Vec::new();
        for name in names {
            let path = if prefix.is_empty() { name.clone() } else { format!("{prefix}/{name}") };
            if let Some(e) = self.merge_entry(b.get(name), o.get(name), t.get(name), &path)? {
                out.push(TreeEntry { name: name.clone(), kind: e.0, id: e.1 });
            }
        }
        Ok(self.objects.put(Object::new(Kind::Tree, tree::encode(&out))))
    }

    fn merge_entry(&mut self, b: Option<&TreeEntry>, o: Option<&TreeEntry>, t: Option<&TreeEntry>, path: &str) -> Result<Option<(EntryKind, Id)>> {
        let key = |e: Option<&TreeEntry>| e.map(|e| (e.kind, e.id));
        let (kb, ko, kt) = (key(b), key(o), key(t));
        if ko == kt || kb == kt {
            return Ok(ko);
        }
        if kb == ko {
            return Ok(kt);
        }
        let is_tree = |e: Option<&TreeEntry>| e.is_some_and(|e| e.kind == EntryKind::Tree);
        let is_file = |e: Option<&TreeEntry>| e.is_some_and(|e| e.kind != EntryKind::Tree);
        match (o, t) {
            (Some(oe), Some(te)) if is_tree(o) && is_tree(t) => {
                let base = if is_tree(b) { b.unwrap().id } else { tree::empty_id() };
                Ok(Some((EntryKind::Tree, self.merge_tree(&base, &oe.id, &te.id, path)?)))
            }
            (Some(oe), Some(te)) if is_file(o) && is_file(t) => self.merge_file(b.filter(|e| e.kind != EntryKind::Tree), oe, te, path),
            (None, Some(te)) => {
                // Main deleted what the change edited.
                self.unmarkable(path, "deleted", Some(te), format!("main deleted {path}; kept your version"))
            }
            (Some(_), None) => {
                // The change deleted what main edited.
                self.unmarkable(path, "deleted", None, format!("you deleted {path}, which main also changed; `on restore {path} --from main` brings main's back"))
            }
            _ => {
                // A file on one side, a folder on the other.
                self.unmarkable(path, "type", t, format!("{path} is a file on one side and a folder on the other; kept yours"))
            }
        }
    }

    /// A conflict that can't be written with markers: landing stops; sync
    /// keeps the change's side (`keep`) and says so.
    fn unmarkable(&mut self, path: &str, kind: &'static str, keep: Option<&TreeEntry>, note: String) -> Result<Option<(EntryKind, Id)>> {
        self.conflicts.push(Conflict { path: path.to_string(), kind: kind.to_string(), detail: None });
        if self.mode == Mode::Sync {
            self.conflicts.pop();
            self.notes.push(Note { path: path.to_string(), message: note });
        }
        Ok(keep.map(|e| (e.kind, e.id)))
    }

    fn merge_file(&mut self, b: Option<&TreeEntry>, o: &TreeEntry, t: &TreeEntry, path: &str) -> Result<Option<(EntryKind, Id)>> {
        // The kind (exec bit, link) merges on its own.
        let kind = if o.kind == t.kind {
            o.kind
        } else if b.is_some_and(|b| b.kind == o.kind) {
            t.kind
        } else if b.is_some_and(|b| b.kind == t.kind) {
            o.kind
        } else {
            t.kind
        };
        if o.id == t.id {
            return Ok(Some((kind, o.id)));
        }
        if b.is_some_and(|b| b.id == o.id) {
            return Ok(Some((kind, t.id)));
        }
        if b.is_some_and(|b| b.id == t.id) {
            return Ok(Some((kind, o.id)));
        }
        let oo = self.file(&o.id)?;
        let to = self.file(&t.id)?;
        let bo = match b {
            Some(b) => Some(self.file(&b.id)?),
            None => None,
        };
        let text = |obj: &Object| obj.kind == Kind::Blob && !is_binary(&obj.data);
        let all_text = text(&oo) && text(&to) && bo.as_ref().is_none_or(text) && o.kind != EntryKind::Link && t.kind != EntryKind::Link && o.kind != EntryKind::Gitlink && t.kind != EntryKind::Gitlink;
        if !all_text {
            return self.unmarkable(path, "binary", Some(t), format!("{path} changed on main and in your change and can't be merged line by line; kept yours, `on restore {path} --from main` takes main's"));
        }
        let base_bytes: &[u8] = bo.as_ref().map(|b| b.data.as_slice()).unwrap_or(b"");
        // Two new files at one path stay a conflict, as in git; smart merges are for files that were there.
        let merged = if bo.is_some() { text_for(path, base_bytes, &oo.data, &to.data, self.labels.0, self.labels.1) } else { crate::merge::text(base_bytes, &oo.data, &to.data, self.labels.0, self.labels.1) };
        // A merge that declares something twice that neither side did alone
        // (two `def helper`, `timeout:` twice in one map) isn't clean, even
        // where the lines didn't touch.
        let twice = if merged.conflicts == 0 { suspect(path, &oo.data, &to.data, &merged.content) } else { Vec::new() };
        if merged.conflicts == 0 && twice.is_empty() {
            let id = self.put_file(merged.content);
            return Ok(Some((kind, id)));
        }
        if path.ends_with(".json")
            && let Some(content) = json(bo.as_ref().map(|b| b.data.as_slice()), &oo.data, &to.data)
        {
            let id = self.put_file(content);
            return Ok(Some((kind, id)));
        }
        if path.ends_with(".toml")
            && let Some(content) = smart::toml(bo.as_ref().map(|b| b.data.as_slice()), &oo.data, &to.data)
            && suspect(path, &oo.data, &to.data, &content).is_empty()
        {
            let id = self.put_file(content);
            return Ok(Some((kind, id)));
        }
        let detail = (!twice.is_empty()).then(|| format!("both sides declare {}", twice.iter().map(|k| crate::decls::short(k)).collect::<Vec<_>>().join(", ")));
        self.conflicts.push(Conflict { path: path.to_string(), kind: if twice.is_empty() { "text" } else { "duplicate" }.into(), detail: detail.clone() });
        match self.mode {
            Mode::Land => Ok(Some((kind, t.id))),
            Mode::Sync => {
                let content = if twice.is_empty() { merged.content } else { mark_twice(path, base_bytes, &oo.data, &to.data, self.labels, &twice) };
                if let Some(d) = detail {
                    self.notes.push(Note { path: path.to_string(), message: format!("{path}: {d}; keep one, then land") });
                }
                let id = self.put_file(content);
                Ok(Some((kind, id)))
            }
        }
    }

    fn put_file(&mut self, content: Vec<u8>) -> Id {
        let objects = chunk::file_objects(&content);
        let id = objects[0].id();
        for o in objects {
            self.objects.put(o);
        }
        id
    }
}

/// A text merge for the file at `path`, settling what smart merges can (see `smart`).
pub fn text_for(path: &str, base: &[u8], ours: &[u8], theirs: &[u8], ol: &str, tl: &str) -> TextMerge {
    text_with(base, ours, theirs, ol, tl, &smart::resolver(path), &|_| false)
}

/// What a clean-looking merge of `path` declares twice that neither side did
/// alone, and JSON that doesn't parse where both sides did.
pub fn suspect(path: &str, ours: &[u8], theirs: &[u8], merged: &[u8]) -> Vec<String> {
    let mut out = crate::decls::new_duplicates(path, ours, theirs, merged);
    if path.ends_with(".json") {
        let parses = |b: &[u8]| serde_json::from_slice::<Value>(b).is_ok();
        if parses(ours) && parses(theirs) && !parses(merged) {
            out.push("valid JSON".into());
        }
    }
    out
}

/// The merge with each spot where the change added a second one of `twice`
/// marked as a conflict (main's side empty), so sync can show it. If none can
/// be placed, the whole file is the conflict.
fn mark_twice(path: &str, base: &[u8], ours: &[u8], theirs: &[u8], labels: (&str, &str), twice: &[String]) -> Vec<u8> {
    let mut lines: Vec<usize> = twice.iter().flat_map(|k| crate::decls::lines_of(path, theirs, k)).collect();
    lines.sort_unstable();
    let force = |h: &Hunk| lines.iter().any(|&l| (h.after.start as usize..h.after.end as usize).contains(&l));
    let marked = text_with(base, ours, theirs, labels.0, labels.1, &smart::resolver(path), &force);
    if marked.conflicts > 0 {
        return marked.content;
    }
    let mut out = format!("<<<<<<< {}\n", labels.0).into_bytes();
    out.extend_from_slice(ours);
    if !ours.ends_with(b"\n") {
        out.push(b'\n');
    }
    out.extend_from_slice(b"=======\n");
    out.extend_from_slice(theirs);
    if !theirs.ends_with(b"\n") {
        out.push(b'\n');
    }
    out.extend_from_slice(format!(">>>>>>> {}\n", labels.1).as_bytes());
    out
}

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

    #[test]
    fn clean_text_merge() {
        let base = b"a\nb\nc\nd\ne\nf\n";
        let ours = b"A\nb\nc\nd\ne\nf\n";
        let theirs = b"a\nb\nc\nd\ne\nF\n";
        let m = text(base, ours, theirs, "main", "change");
        assert_eq!(m.conflicts, 0);
        assert_eq!(m.content, b"A\nb\nc\nd\ne\nF\n");
    }

    #[test]
    fn conflicting_text_merge() {
        let base = b"a\nb\nc\n";
        let ours = b"a\nB1\nc\n";
        let theirs = b"a\nB2\nc\n";
        let m = text(base, ours, theirs, "main 4", "your change bcdf");
        assert_eq!(m.conflicts, 1);
        assert_eq!(String::from_utf8(m.content).unwrap(), "a\n<<<<<<< main 4\nB1\n=======\nB2\n>>>>>>> your change bcdf\nc\n");
    }

    #[test]
    fn same_change_both_sides() {
        let m = text(b"a\nb\n", b"a\nX\n", b"a\nX\n", "o", "t");
        assert_eq!(m.conflicts, 0);
        assert_eq!(m.content, b"a\nX\n");
    }

    #[test]
    fn json_keys_merge() {
        let base = b"{\n  \"a\": \"1\"\n}\n";
        let ours = b"{\n  \"a\": \"1\",\n  \"b\": \"2\"\n}\n";
        let theirs = b"{\n  \"a\": \"1\",\n  \"c\": \"3\"\n}\n";
        // Line by line this is a conflict (both added after "a").
        assert_eq!(text(base, ours, theirs, "o", "t").conflicts, 1);
        let merged = json(Some(base), ours, theirs).unwrap();
        let v: Value = serde_json::from_slice(&merged).unwrap();
        assert_eq!(v["b"], "2");
        assert_eq!(v["c"], "3");
        assert!(json(Some(base), b"{\"a\": \"x\"}", b"{\"a\": \"y\"}").is_none());
    }

    fn put_files(src: &mut MemSource, list: &[(&str, &str)]) -> Id {
        let files: Files = list
            .iter()
            .map(|(p, c)| (p.to_string(), Entry { kind: EntryKind::File, id: src.put(Object::blob(c.as_bytes().to_vec())) }))
            .collect();
        let (root, trees) = build(&files);
        for t in trees {
            src.put(t);
        }
        root
    }

    #[test]
    fn tree_merges() {
        let mut src = MemSource::default();
        let base = put_files(&mut src, &[("a.txt", "a\nb\nc\n"), ("src/x.rs", "x\n"), ("keys.json", "{\n  \"a\": 1\n}\n")]);
        let ours = put_files(&mut src, &[("a.txt", "A\nb\nc\n"), ("src/x.rs", "x\n"), ("src/new.rs", "n\n"), ("keys.json", "{\n  \"a\": 1,\n  \"b\": 2\n}\n")]);
        let theirs = put_files(&mut src, &[("a.txt", "a\nb\nC\n"), ("src/x.rs", "x2\n"), ("keys.json", "{\n  \"a\": 1,\n  \"c\": 3\n}\n")]);
        let m = trees(&src, Some(&base), &ours, &theirs, Mode::Land, ("main", "change")).unwrap();
        assert!(m.clean(), "{:?}", m.conflicts);
        let layered = Layered { first: &m.objects, second: &src };
        let files = flatten(&layered, &m.tree).unwrap();
        let read = |p: &str| String::from_utf8(layered.must(&files[p].id).unwrap().data).unwrap();
        assert_eq!(read("a.txt"), "A\nb\nC\n");
        assert_eq!(read("src/x.rs"), "x2\n");
        assert_eq!(read("src/new.rs"), "n\n");
        let keys: Value = serde_json::from_str(&read("keys.json")).unwrap();
        assert_eq!((keys["b"].as_i64(), keys["c"].as_i64()), (Some(2), Some(3)));
    }

    /// Merges one file three ways through `trees`: its conflicts' kinds, and the file sync writes.
    fn merge_one(path: &str, base: &str, ours: &str, theirs: &str) -> (Vec<String>, String) {
        let mut src = MemSource::default();
        let b = put_files(&mut src, &[(path, base)]);
        let o = put_files(&mut src, &[(path, ours)]);
        let t = put_files(&mut src, &[(path, theirs)]);
        let land = trees(&src, Some(&b), &o, &t, Mode::Land, ("main", "change")).unwrap();
        let sync = trees(&src, Some(&b), &o, &t, Mode::Sync, ("main", "change")).unwrap();
        assert_eq!(land.conflicts.len(), sync.conflicts.len(), "land and sync agree");
        let layered = Layered { first: &sync.objects, second: &src };
        let files = flatten(&layered, &sync.tree).unwrap();
        let text = String::from_utf8(layered.must(&files[path].id).unwrap().data).unwrap();
        (land.conflicts.iter().map(|c| c.kind.clone()).collect(), text)
    }

    #[test]
    fn never_two_of_one_thing() {
        // Two new functions at the end of a file both go in (git: a conflict).
        let base = "export function one() {\n  return 1;\n}\n";
        let (kinds, text) = merge_one(
            "app.js",
            base,
            &format!("{base}\nexport function two() {{\n  return 2;\n}}\n"),
            &format!("{base}\nexport function three() {{\n  return 3;\n}}\n"),
        );
        assert!(kinds.is_empty(), "{kinds:?}");
        assert!(text.contains("function two") && text.contains("function three"));
        // Two different `def helper` in one module: a conflict, never both.
        let base = "def base():\n    return 0\n";
        let (kinds, text) = merge_one(
            "util.py",
            base,
            &format!("{base}\ndef helper(x):\n    return x + 1\n"),
            &format!("{base}\ndef helper(items):\n    return len(items)\n"),
        );
        assert_eq!(kinds.len(), 1);
        assert!(text.contains("<<<<<<< main"));
        // The same key twice in one YAML map: a conflict.
        let (kinds, _) = merge_one("config.yaml", "server:\n  port: 80\n", "server:\n  port: 80\n  timeout: 30\n", "server:\n  port: 80\n  timeout: 5\n");
        assert_eq!(kinds.len(), 1);
        // Git merges these cleanly (the lines don't touch), but the module ends up with two `total`.
        let base = "def a():\n    return 1\n\n\ndef b():\n    return 2\n";
        let (kinds, text) = merge_one(
            "shop.py",
            base,
            &format!("def total():\n    return 0\n\n\n{base}"),
            &format!("{base}\n\n\ndef total():\n    return 9\n"),
        );
        assert_eq!(kinds, vec!["duplicate"]);
        assert_eq!(text.matches("<<<<<<<").count(), 1);
        assert!(text.contains("def total():\n    return 0"), "main's stays where it was");
        // Statements added at one spot keep git's conflict: their order matters.
        let base = "function run() {\n  start();\n}\n";
        let (kinds, _) = merge_one("run.js", base, "function run() {\n  start();\n  save();\n}\n", "function run() {\n  start();\n  send();\n}\n");
        assert_eq!(kinds, vec!["text"]);
        // Two imports binding one name don't merge into two.
        let (kinds, _) = merge_one(
            "app.ts",
            "import { a } from \"x\";\n\nrun();\n",
            "import { a, b } from \"x\";\n\nrun();\n",
            "import { a, c } from \"x\";\n\nrun();\n",
        );
        assert_eq!(kinds.len(), 1);
        // Two scripts with one name in package.json: a conflict, not a silent last-one-wins.
        let base = "{\n  \"scripts\": {\n    \"build\": \"x\"\n  }\n}\n";
        let (kinds, _) = merge_one(
            "package.json",
            base,
            "{\n  \"scripts\": {\n    \"build\": \"x\",\n    \"test\": \"jest\"\n  }\n}\n",
            "{\n  \"scripts\": {\n    \"build\": \"x\",\n    \"test\": \"vitest\"\n  }\n}\n",
        );
        assert_eq!(kinds.len(), 1);
        // Two new tests at one spot both go in.
        let base = "describe(\"cart\", () => {\n  it(\"adds\", () => {\n    add();\n  });\n});\n";
        let (kinds, text) = merge_one(
            "cart.test.ts",
            base,
            "describe(\"cart\", () => {\n  it(\"adds\", () => {\n    add();\n  });\n  it(\"removes\", () => {\n    remove();\n  });\n});\n",
            "describe(\"cart\", () => {\n  it(\"adds\", () => {\n    add();\n  });\n  it(\"empties\", () => {\n    empty();\n  });\n});\n",
        );
        assert!(kinds.is_empty(), "{kinds:?}\n{text}");
        assert!(text.contains("removes") && text.contains("empties"));
    }

    /// Random three-way merges against the plain line merge (what git does):
    /// where it's clean, the smart merge gives the very same file; where the
    /// smart merge settles more, every line either side added is kept, and a
    /// clean merge never carries markers.
    #[test]
    fn smart_merges_never_differ_where_git_is_clean() {
        let mut seed: u64 = 0x9E37_79B9_7F4A_7C15;
        let mut next = move |n: u64| {
            seed ^= seed << 13;
            seed ^= seed >> 7;
            seed ^= seed << 17;
            seed % n
        };
        let vocab = [
            "import { a } from \"a\";",
            "import { b } from \"b\";",
            "import os",
            "def f():",
            "    return 1",
            "function g() {",
            "  return 2;",
            "}",
            "key: 1",
            "other: 2",
            "",
            "x = 1",
            "y = 2",
            "// note",
            "fn h() {}",
        ];
        let rand_text = |len: u64, next: &mut dyn FnMut(u64) -> u64| -> Vec<String> { (0..len).map(|_| vocab[next(vocab.len() as u64) as usize].to_string()).collect() };
        let mut checked = 0;
        for case in 0..4000 {
            let base = rand_text(next(12), &mut next);
            let edit = |next: &mut dyn FnMut(u64) -> u64, lines: &Vec<String>| -> Vec<String> {
                let mut out = lines.clone();
                for _ in 0..next(4) {
                    let at = if out.is_empty() { 0 } else { next(out.len() as u64 + 1) as usize };
                    match next(3) {
                        0 if at < out.len() => {
                            out.remove(at);
                        }
                        1 if at < out.len() => out[at] = format!("{} {}", out[at], next(9)),
                        _ => out.insert(at, vocab[next(vocab.len() as u64) as usize].to_string()),
                    }
                }
                out
            };
            let ours = edit(&mut next, &base);
            let theirs = edit(&mut next, &base);
            let join = |l: &Vec<String>| l.iter().map(|s| format!("{s}\n")).collect::<String>();
            let (b, o, t) = (join(&base), join(&ours), join(&theirs));
            for path in ["f.txt", "f.py", "f.js", "f.rs", "f.yaml"] {
                let plain = text(b.as_bytes(), o.as_bytes(), t.as_bytes(), "main", "change");
                let smart = text_for(path, b.as_bytes(), o.as_bytes(), t.as_bytes(), "main", "change");
                if plain.conflicts == 0 {
                    assert_eq!(smart.conflicts, 0, "case {case} {path}");
                    assert_eq!(smart.content, plain.content, "case {case} {path}: smart differs where git is clean");
                    checked += 1;
                } else if smart.conflicts == 0 {
                    let merged = String::from_utf8(smart.content.clone()).unwrap();
                    assert!(!merged.contains("<<<<<<<"), "case {case} {path}");
                    let lines: std::collections::HashSet<&str> = merged.lines().collect();
                    for side in [&ours, &theirs] {
                        for l in side.iter().filter(|l| !base.contains(l)) {
                            assert!(lines.contains(l.as_str()), "case {case} {path}: lost {l:?}\nbase:\n{b}\nours:\n{o}\ntheirs:\n{t}\nmerged:\n{merged}");
                        }
                    }
                }
            }
        }
        assert!(checked > 1000);
    }

    #[test]
    fn tree_conflicts() {
        let mut src = MemSource::default();
        let base = put_files(&mut src, &[("a.txt", "a\n"), ("gone.txt", "g\n")]);
        let ours = put_files(&mut src, &[("a.txt", "main\n")]);
        let theirs = put_files(&mut src, &[("a.txt", "change\n"), ("gone.txt", "edited\n")]);
        let land = trees(&src, Some(&base), &ours, &theirs, Mode::Land, ("main", "change")).unwrap();
        let mut paths: Vec<_> = land.conflicts.iter().map(|c| (c.path.as_str(), c.kind.as_str())).collect();
        paths.sort();
        assert_eq!(paths, vec![("a.txt", "text"), ("gone.txt", "deleted")]);
        let sync = trees(&src, Some(&base), &ours, &theirs, Mode::Sync, ("main 2", "your change x")).unwrap();
        assert_eq!(sync.conflicts.len(), 1);
        assert_eq!(sync.notes.len(), 1);
        let layered = Layered { first: &sync.objects, second: &src };
        let files = flatten(&layered, &sync.tree).unwrap();
        let a = String::from_utf8(layered.must(&files["a.txt"].id).unwrap().data).unwrap();
        assert!(a.contains("<<<<<<< main 2"));
        assert!(files.contains_key("gone.txt"));
    }

    #[test]
    fn fast_paths() {
        let mut src = MemSource::default();
        let base = put_files(&mut src, &[("a.txt", "a\n")]);
        let theirs = put_files(&mut src, &[("a.txt", "b\n")]);
        let m = trees(&src, Some(&base), &base, &theirs, Mode::Land, ("main", "change")).unwrap();
        assert_eq!(m.tree, theirs);
    }
}

#[cfg(test)]
mod rename_tests {
    use super::*;

    fn tree_of(src: &mut MemSource, list: &[(&str, &str)]) -> Id {
        let mut map = tree::Files::new();
        for (path, content) in list {
            let objects = chunk::file_objects(content.as_bytes());
            let id = objects[0].id();
            for o in objects {
                src.put(o);
            }
            map.insert(path.to_string(), tree::Entry { kind: EntryKind::File, id });
        }
        let (id, objects) = tree::build(&map);
        for o in objects {
            src.put(o);
        }
        id
    }

    #[test]
    fn edits_follow_a_moved_file() {
        let mut src = MemSource::default();
        let text: String = (0..30).map(|i| format!("line {i}\n")).collect();
        let base = tree_of(&mut src, &[("src/old.rs", &text)]);
        // Main moves the file; the change edits it where it was.
        let ours = tree_of(&mut src, &[("src/new.rs", &text)]);
        let theirs = tree_of(&mut src, &[("src/old.rs", &text.replace("line 20\n", "line twenty\n"))]);
        let m = trees(&src, Some(&base), &ours, &theirs, Mode::Land, ("main", "change")).unwrap();
        assert!(m.clean(), "{:?}", m.conflicts);
        let layered = Layered { first: &m.objects, second: &src };
        let flat = tree::flatten(&layered, &m.tree).unwrap();
        assert_eq!(flat.keys().cloned().collect::<Vec<_>>(), vec!["src/new.rs".to_string()]);
        let content = chunk::read_file(&layered, &flat["src/new.rs"].id).unwrap();
        assert!(String::from_utf8(content).unwrap().contains("line twenty"));
        // And the other way round: the change moves it, main edits it.
        let m = trees(&src, Some(&base), &theirs, &ours, Mode::Land, ("main", "change")).unwrap();
        assert!(m.clean(), "{:?}", m.conflicts);
        let layered = Layered { first: &m.objects, second: &src };
        let flat = tree::flatten(&layered, &m.tree).unwrap();
        assert_eq!(flat.keys().cloned().collect::<Vec<_>>(), vec!["src/new.rs".to_string()]);
    }
}