//! 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;
use std::collections::HashMap;

/// 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
}

/// The lines `old` and `new` keep in common, as (old index, new index) in
/// order: a longest common subsequence, found by Myers' algorithm. A line
/// found on one side only cannot be in it, so such lines are set aside
/// before the diff, as Git's xdiff does: a file rewritten whole (every
/// line ending changed, say) then costs time linear in its length rather
/// than quadratic. Lines are compared as small numbers, not bytes.
fn kept_lines<'a>(old: &[&'a [u8]], new: &[&'a [u8]]) -> Vec<(usize, usize)> {
    let mut ids: HashMap<&'a [u8], u32> = HashMap::new();
    let mut intern = |l: &'a [u8]| -> u32 {
        let next = ids.len() as u32;
        *ids.entry(l).or_insert(next)
    };
    let o: Vec<u32> = old.iter().map(|l| intern(l)).collect();
    let n: Vec<u32> = new.iter().map(|l| intern(l)).collect();
    let mut in_old = vec![false; ids.len()];
    let mut in_new = vec![false; ids.len()];
    for &x in &o {
        in_old[x as usize] = true;
    }
    for &x in &n {
        in_new[x as usize] = true;
    }
    let oi: Vec<usize> = (0..o.len()).filter(|&i| in_new[o[i] as usize]).collect();
    let ni: Vec<usize> = (0..n.len()).filter(|&j| in_old[n[j] as usize]).collect();
    let os: Vec<u32> = oi.iter().map(|&i| o[i]).collect();
    let ns: Vec<u32> = ni.iter().map(|&j| n[j]).collect();
    let mut capture = similar::algorithms::Capture::new();
    let _ = similar::algorithms::myers::diff(&mut capture, &os, 0..os.len(), &ns, 0..ns.len());
    let mut kept = Vec::new();
    for op in capture.into_ops() {
        if let DiffOp::Equal {
            old_index,
            new_index,
            len,
        } = op
        {
            kept.extend((0..len).map(|k| (oi[old_index + k], ni[new_index + k])));
        }
    }
    kept
}

/// 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 keys: Vec<AtomKey> = old.iter().map(|(k, _)| *k).collect();
    let old_lines: Vec<&[u8]> = old.iter().map(|(_, l)| l.as_slice()).collect();
    text_edits_of(node, &keys, &old_lines, new)
}

/// `text_edits` for live lines given as their atoms and, apart, their
/// text (`old[i]` is the text of `keys[i]`).
pub fn text_edits_of(node: NodeId, keys: &[AtomKey], old_lines: &[&[u8]], new: &[u8]) -> Vec<Edit> {
    let new_lines = split_lines(new);

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

    // Each run of lines between two kept ones is deleted, and the new
    // lines there are inserted where the first deleted line was.
    let mut deleted: Vec<AtomKey> = Vec::new();
    let mut inserts: Vec<Edit> = Vec::new();
    let (mut i, mut j) = (0, 0);
    let end = (old_lines.len(), new_lines.len());
    for (ki, kj) in kept_lines(old_lines, &new_lines).into_iter().chain([end]) {
        deleted.extend_from_slice(&keys[i..ki]);
        if kj > j {
            let (after, before) = anchor(i);
            inserts.push(Edit::Insert {
                node,
                after,
                before,
                lines: new_lines[j..kj].iter().copied().collect(),
            });
        }
        (i, j) = (ki + 1, kj + 1);
    }
    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()].into()
                },
            ]
        );
        // 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()].into()
            }]
        );
    }
}