//! Turn a working-copy file into edits against the live atoms of a node.
//! Anchors follow the convention in spec §7.4: an insertion at old position
//! `i` is anchored after `old[i-1]` and before `old[i]`, both of which are
//! adjacent in the author's view.

use crate::graph::AtomKey;
use crate::ids::NodeId;
use crate::objects::{AtomRange, AtomRef, Edit};
use similar::DiffOp;

/// Split into lines, each keeping its terminator; a final unterminated line
/// is its own atom.
pub fn split_lines(b: &[u8]) -> Vec<&[u8]> {
    let mut out = Vec::new();
    let mut start = 0;
    for (i, &c) in b.iter().enumerate() {
        if c == b'\n' {
            out.push(&b[start..=i]);
            start = i + 1;
        }
    }
    if start < b.len() {
        out.push(&b[start..]);
    }
    out
}

/// Coalesce atom keys into half-open ranges of consecutive indices per change.
pub fn ranges(keys: &[AtomKey]) -> Vec<AtomRange> {
    let mut out: Vec<AtomRange> = Vec::new();
    for &(c, i) in keys {
        match out.last_mut() {
            Some(r) if r.change == c && r.to == i => r.to = i + 1,
            _ => out.push(AtomRange { change: c, from: i, to: i + 1 }),
        }
    }
    out
}

/// Edits that transform the live lines `old` of `node` into `new`.
pub fn text_edits(node: NodeId, old: &[(AtomKey, Vec<u8>)], new: &[u8]) -> Vec<Edit> {
    let old_lines: Vec<&[u8]> = old.iter().map(|(_, l)| l.as_slice()).collect();
    let new_lines = split_lines(new);
    // Myers ops in file order. `capture_diff_slices` also runs the `Compact`
    // hook, which slides deletions along runs of equal lines and can leave
    // an insertion with the old index of a line before an equal one: the
    // insertion was then anchored a line too early and landed on the wrong
    // side of it (found by verifying a real Git import commit by commit).
    let mut hook = similar::algorithms::Replace::new(similar::algorithms::Capture::new());
    let _ = similar::algorithms::diff_deadline(
        similar::Algorithm::Myers,
        &mut hook,
        &old_lines,
        0..old_lines.len(),
        &new_lines,
        0..new_lines.len(),
        None,
    );
    let ops = hook.into_inner().into_ops();

    let anchor = |i: usize| -> (AtomRef, AtomRef) {
        let after = if i == 0 { AtomRef::Start } else { AtomRef::Atom { change: old[i - 1].0 .0, index: old[i - 1].0 .1 } };
        let before = if i >= old.len() { AtomRef::End } else { AtomRef::Atom { change: old[i].0 .0, index: old[i].0 .1 } };
        (after, before)
    };

    let mut deleted: Vec<AtomKey> = Vec::new();
    let mut inserts: Vec<Edit> = Vec::new();
    for op in ops {
        match op {
            DiffOp::Equal { .. } => {}
            DiffOp::Delete { old_index, old_len, .. } => {
                deleted.extend(old[old_index..old_index + old_len].iter().map(|(k, _)| *k));
            }
            DiffOp::Insert { old_index, new_index, new_len } => {
                let (after, before) = anchor(old_index);
                inserts.push(Edit::Insert {
                    node,
                    after,
                    before,
                    lines: new_lines[new_index..new_index + new_len].iter().map(|l| l.to_vec()).collect(),
                });
            }
            DiffOp::Replace { old_index, old_len, new_index, new_len } => {
                deleted.extend(old[old_index..old_index + old_len].iter().map(|(k, _)| *k));
                let (after, before) = anchor(old_index);
                inserts.push(Edit::Insert {
                    node,
                    after,
                    before,
                    lines: new_lines[new_index..new_index + new_len].iter().map(|l| l.to_vec()).collect(),
                });
            }
        }
    }
    let mut edits = Vec::new();
    if !deleted.is_empty() {
        edits.push(Edit::Delete { node, atoms: ranges(&deleted) });
    }
    edits.extend(inserts);
    edits
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::hash::ObjectRef;

    fn h(n: u8) -> ObjectRef {
        ObjectRef([n; 32])
    }

    /// Replaying `text_edits` by position must give the new text, on files
    /// full of repeated lines, where a diff has many equally good
    /// alignments to choose between.
    #[test]
    fn edits_replay_to_the_new_text_on_repetitive_files() {
        use rand::{Rng, SeedableRng};
        let words: [&[u8]; 5] = [b"}\n", b"    }\n", b"\n", b"a\n", b"    b\n"];
        let mut rng = rand::rngs::StdRng::seed_from_u64(11);
        for _ in 0..2000 {
            let old: Vec<Vec<u8>> = (0..rng.gen_range(0..30))
                .map(|_| words[rng.gen_range(0..5)].to_vec())
                .collect();
            let new: Vec<u8> = (0..rng.gen_range(0..30))
                .flat_map(|_| words[rng.gen_range(0..5)].to_vec())
                .collect();
            let keyed: Vec<(AtomKey, Vec<u8>)> = old
                .iter()
                .enumerate()
                .map(|(i, l)| ((h(1), i as u32), l.clone()))
                .collect();
            let edits = text_edits(NodeId::ROOT, &keyed, &new);
            let mut dead = vec![false; old.len()];
            let mut after: std::collections::BTreeMap<i64, Vec<u8>> = Default::default();
            for e in &edits {
                match e {
                    Edit::Delete { atoms, .. } => atoms
                        .iter()
                        .for_each(|r| (r.from..r.to).for_each(|i| dead[i as usize] = true)),
                    Edit::Insert {
                        after: a,
                        before: b,
                        lines,
                        ..
                    } => {
                        let at = match a {
                            AtomRef::Start => -1,
                            AtomRef::Atom { index, .. } => *index as i64,
                            AtomRef::End => unreachable!(),
                        };
                        let next = match b {
                            AtomRef::End => old.len() as i64,
                            AtomRef::Atom { index, .. } => *index as i64,
                            AtomRef::Start => unreachable!(),
                        };
                        assert_eq!(next, at + 1, "anchors adjacent");
                        after.entry(at).or_default().extend(lines.iter().flatten());
                    }
                    _ => {}
                }
            }
            let mut out = after.get(&-1).cloned().unwrap_or_default();
            for (i, l) in old.iter().enumerate() {
                if !dead[i] {
                    out.extend(l);
                }
                out.extend(after.get(&(i as i64)).cloned().unwrap_or_default());
            }
            assert_eq!(
                String::from_utf8_lossy(&out),
                String::from_utf8_lossy(&new),
                "old {old:?}"
            );
        }
    }

    #[test]
    fn split_keeps_terminators() {
        assert_eq!(split_lines(b"a\nb\n"), vec![&b"a\n"[..], &b"b\n"[..]]);
        assert_eq!(split_lines(b"a\nb"), vec![&b"a\n"[..], &b"b"[..]]);
        assert_eq!(split_lines(b""), Vec::<&[u8]>::new());
        assert_eq!(split_lines(b"\n\n"), vec![&b"\n"[..], &b"\n"[..]]);
    }

    #[test]
    fn ranges_coalesce() {
        let r = ranges(&[(h(1), 0), (h(1), 1), (h(1), 3), (h(2), 0)]);
        assert_eq!(
            r,
            vec![
                AtomRange { change: h(1), from: 0, to: 2 },
                AtomRange { change: h(1), from: 3, to: 4 },
                AtomRange { change: h(2), from: 0, to: 1 }
            ]
        );
    }

    #[test]
    fn edits_for_typical_changes() {
        let node = NodeId::random();
        let old: Vec<(AtomKey, Vec<u8>)> = ["a\n", "b\n", "c\n"].iter().enumerate().map(|(i, l)| ((h(1), i as u32), l.as_bytes().to_vec())).collect();
        // No change.
        assert!(text_edits(node, &old, b"a\nb\nc\n").is_empty());
        // Replace middle line.
        let e = text_edits(node, &old, b"a\nB\nc\n");
        assert_eq!(
            e,
            vec![
                Edit::Delete { node, atoms: vec![AtomRange { change: h(1), from: 1, to: 2 }] },
                Edit::Insert { node, after: AtomRef::Atom { change: h(1), index: 0 }, before: AtomRef::Atom { change: h(1), index: 1 }, lines: vec![b"B\n".to_vec()] },
            ]
        );
        // Prepend and append.
        let e = text_edits(node, &old, b"top\na\nb\nc\nend\n");
        assert_eq!(e.len(), 2);
        assert!(matches!(&e[0], Edit::Insert { after: AtomRef::Start, before: AtomRef::Atom { index: 0, .. }, .. }));
        assert!(matches!(&e[1], Edit::Insert { after: AtomRef::Atom { index: 2, .. }, before: AtomRef::End, .. }));
        // Delete everything.
        let e = text_edits(node, &old, b"");
        assert_eq!(e, vec![Edit::Delete { node, atoms: vec![AtomRange { change: h(1), from: 0, to: 3 }] }]);
        // From empty.
        let e = text_edits(node, &[], b"x\n");
        assert_eq!(e, vec![Edit::Insert { node, after: AtomRef::Start, before: AtomRef::End, lines: vec![b"x\n".to_vec()] }]);
    }
}