//! 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()

            }]

        );

    }

}