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

            }]

        );

    }

}