//! Rewrite propagation (spec §8.4): when change `old` is replaced by `new`,

//! every change that depends on `old` is rewritten with its references

//! translated through a correspondence from `old`'s atoms and tree operations

//! to `new`'s. Rewritten changes keep their ChangeIds.

//!

//! Where a reference has no counterpart it is reified rather than refused:

//! an insert anchor moves to the nearest surviving atom of the same insert

//! chain in `old`, else to that chain's own anchors (an order conflict then

//! arises naturally if `new` placed other content there); deletions of

//! vanished atoms are dropped; operations and edits on nodes that vanished

//! are dropped. Every such adjustment is reported as a note.

use crate::hash::ChangeHash;

use crate::objects::{AtomRange, AtomRef, Change, Edit, OpRef, TreeOp};

use crate::state::State;

use std::collections::{BTreeSet, HashMap};

/// How `old`'s atoms and tree operations map onto `new`'s.

#[derive(Clone, Debug, Default, PartialEq, Eq)]

pub struct Correspondence {

    /// Old atom index → new atom index, per node the old change edited.

    /// Absent means the atom no longer exists.

    pub atoms: HashMap<u32, u32>,

    /// Old tree-op index → new tree-op index.

    pub ops: HashMap<u32, u32>,

}

impl Correspondence {

    /// Every atom and operation keeps its index: `new` has the same edits as `old`.

    pub fn identity(change: &Change) -> Correspondence {

        let mut atoms = HashMap::new();

        let mut per_node: HashMap<crate::ids::NodeId, u32> = HashMap::new();

        for e in &change.edits {

            if let Edit::Insert { node, lines, .. } = e {

                let idx = per_node.entry(*node).or_default();

                for _ in lines {

                    atoms.insert(*idx, *idx);

                    *idx += 1;

                }

            }

        }

        // Atom indices are per node, so the identity map is index → index for

        // the largest index any node uses.

        let max = per_node.values().copied().max().unwrap_or(0);

        for i in 0..max {

            atoms.insert(i, i);

        }

        let ops = (0..change.tree_ops.len() as u32).map(|i| (i, i)).collect();

        Correspondence { atoms, ops }

    }

}

#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]

pub enum RewriteError {

    #[error("change {0} is not in the state")]

    Missing(ChangeHash),

}

/// The result of propagating a rewrite.

#[derive(Clone, Debug, Default)]

pub struct Propagation {

    /// `(old hash, rewritten change)` in dependency order.

    pub changes: Vec<(ChangeHash, Change)>,

    /// Human-readable descriptions of reified orphaned references.

    pub notes: Vec<String>,

}

/// Where each atom of a change was inserted: the chain it belongs to.

struct Chain {

    first: u32,

    last: u32,

    after: AtomRef,

    before: AtomRef,

}

fn chains_of(c: &Change) -> Vec<Chain> {

    let mut per_node: HashMap<crate::ids::NodeId, u32> = HashMap::new();

    let mut out = Vec::new();

    for e in &c.edits {

        if let Edit::Insert { node, after, before, lines } = e {

            let idx = per_node.entry(*node).or_default();

            out.push(Chain { first: *idx, last: *idx + lines.len() as u32 - 1, after: *after, before: *before });

            *idx += lines.len() as u32;

        }

    }

    out

}

/// What a rewritten change was replaced by.

#[derive(Clone, Debug)]

enum Replacement {

    Change(ChangeHash),

    /// Removed: dependents inherit these dependencies instead.

    Removed(Vec<ChangeHash>),

}

/// Rewrite every change in `state` that depends on `old`, given `new` (or

/// `None` when `old` is removed) and the correspondence between them.

/// The result lists `(old hash, rewritten change)` pairs in dependency

/// order, not including `old` → `new` itself, plus notes about reified

/// orphaned references.

///

/// `load` fetches a change's full object (a state keeps only metadata).

pub fn propagate(state: &State, old: ChangeHash, new: Option<&Change>, corr: &Correspondence, load: &dyn Fn(&ChangeHash) -> Option<Change>) -> Result<Propagation, RewriteError> {

    let old_meta = state.get(&old).ok_or(RewriteError::Missing(old))?;

    let old_full = load(&old);

    let mut mapping: HashMap<ChangeHash, Replacement> = HashMap::new();

    mapping.insert(old, match new {

        Some(n) => Replacement::Change(n.hash()),

        None => Replacement::Removed(old_meta.deps.clone()),

    });

    let mut corrs: HashMap<ChangeHash, Correspondence> = HashMap::new();

    corrs.insert(old, corr.clone());

    // Chains of the rewritten change, for re-anchoring; vanished nodes.

    let chains: HashMap<ChangeHash, Vec<Chain>> = old_full.as_ref().map(|c| (old, chains_of(c))).into_iter().collect();

    let mut vanished_nodes: BTreeSet<crate::ids::NodeId> = BTreeSet::new();

    if let Some(c) = &old_full {

        for (i, op) in c.tree_ops.iter().enumerate() {

            if let TreeOp::AddNode { node, .. } = op {

                let survives = new.is_some() && corr.ops.contains_key(&(i as u32));

                if !survives {

                    vanished_nodes.insert(*node);

                }

            }

        }

    }

    let mut notes = Vec::new();

    // Dependents in topological order: every change whose closure has `old`,

    // sorted so that dependencies come first.

    let mut dependents: Vec<ChangeHash> = state.changes().filter(|(h, _)| **h != old && state.closure(h).contains(&old)).map(|(h, _)| *h).collect();

    dependents.sort_by_key(|h| (state.closure(h).len(), *h));

    let mut out = Vec::new();

    for h in dependents {

        let c = load(&h).ok_or(RewriteError::Missing(h))?;

        let rewritten = rewrite_one(&h, &c, &mapping, &corrs, &chains, &vanished_nodes, &mut notes);

        let rh = rewritten.hash();

        corrs.insert(h, Correspondence::identity(&rewritten));

        mapping.insert(h, Replacement::Change(rh));

        out.push((h, rewritten));

    }

    Ok(Propagation { changes: out, notes })

}

/// Re-anchor a reference to a vanished atom of `change`: the nearest

/// surviving atom of its chain (before it for `after` anchors, after it for

/// `before` anchors), else the chain's own anchor.

fn reanchor(change: &ChangeHash, index: u32, want_after: bool, mapping: &HashMap<ChangeHash, Replacement>, corrs: &HashMap<ChangeHash, Correspondence>, chains: &HashMap<ChangeHash, Vec<Chain>>) -> AtomRef {

    let corr = corrs.get(change);

    let chain = chains.get(change).and_then(|cs| cs.iter().find(|ch| ch.first <= index && index <= ch.last));

    if let (Some(Replacement::Change(nh)), Some(corr), Some(ch)) = (mapping.get(change), corr, chain) {

        let candidates: Box<dyn Iterator<Item = u32>> = if want_after { Box::new((ch.first..index).rev()) } else { Box::new(index + 1..=ch.last) };

        for j in candidates {

            if let Some(nj) = corr.atoms.get(&j) {

                return AtomRef::Atom { change: *nh, index: *nj };

            }

        }

    }

    match chain {

        Some(ch) => if want_after { ch.after } else { ch.before },

        None => if want_after { AtomRef::Start } else { AtomRef::End },

    }

}

fn rewrite_one(

    hash: &ChangeHash,

    c: &Change,

    mapping: &HashMap<ChangeHash, Replacement>,

    corrs: &HashMap<ChangeHash, Correspondence>,

    chains: &HashMap<ChangeHash, Vec<Chain>>,

    vanished_nodes: &BTreeSet<crate::ids::NodeId>,

    notes: &mut Vec<String>,

) -> Change {

    let short = hash.short(12);

    // An anchor: translate, or re-anchor when its counterpart is gone.

    let map_anchor = |r: AtomRef, want_after: bool, notes: &mut Vec<String>| -> AtomRef {

        match r {

            AtomRef::Atom { change, index } => match mapping.get(&change) {

                Some(Replacement::Change(nh)) => match corrs[&change].atoms.get(&index) {

                    Some(idx) => AtomRef::Atom { change: *nh, index: *idx },

                    None => {

                        notes.push(format!("change {short}: an anchor line of the rewritten change vanished; re-anchored to its nearest neighbour"));

                        reanchor(&change, index, want_after, mapping, corrs, chains)

                    }

                },

                Some(Replacement::Removed(_)) => {

                    notes.push(format!("change {short}: an anchor line of the removed change vanished; re-anchored to its neighbours"));

                    reanchor(&change, index, want_after, mapping, corrs, chains)

                }

                None => r,

            },

            other => other,

        }

    };

    // A tree-operation reference: translate, or `None` when gone.

    let map_op = |r: OpRef| -> Option<OpRef> {

        match mapping.get(&r.change) {

            Some(Replacement::Change(nh)) => corrs[&r.change].ops.get(&r.index).map(|idx| OpRef { change: *nh, index: *idx }),

            Some(Replacement::Removed(_)) => None,

            None => Some(r),

        }

    };

    let mut out = c.clone();

    let mut deps: BTreeSet<ChangeHash> = BTreeSet::new();

    for d in &c.deps {

        match mapping.get(d) {

            Some(Replacement::Change(nh)) => {

                deps.insert(*nh);

            }

            Some(Replacement::Removed(inherited)) => deps.extend(inherited.iter().copied()),

            None => {

                deps.insert(*d);

            }

        }

    }

    out.deps = deps.into_iter().collect();

    let mut ops = Vec::new();

    for op in &out.tree_ops {

        let node = op.node();

        if vanished_nodes.contains(&node) || matches!(op, TreeOp::AddNode { parent, .. } if vanished_nodes.contains(parent)) {

            notes.push(format!("change {short}: an operation on a file that vanished with the rewritten change was dropped"));

            continue;

        }

        match op {

            TreeOp::RemoveNode { node, placement } => match map_op(*placement) {

                Some(p) => ops.push(TreeOp::RemoveNode { node: *node, placement: p }),

                None => notes.push(format!("change {short}: removal of a placement that vanished was dropped")),

            },

            TreeOp::Move { node, old, parent, name } => match map_op(*old) {

                Some(o) => ops.push(TreeOp::Move { node: *node, old: o, parent: *parent, name: name.clone() }),

                None => notes.push(format!("change {short}: a move of {name} lost its origin and was dropped")),

            },

            TreeOp::SetMode { node, old, mode } => match map_op(*old) {

                Some(o) => ops.push(TreeOp::SetMode { node: *node, old: o, mode: *mode }),

                None => notes.push(format!("change {short}: a mode change lost its origin and was dropped")),

            },

            add @ TreeOp::AddNode { .. } => ops.push(add.clone()),

        }

    }

    out.tree_ops = ops;

    let mut edits = Vec::new();

    for e in &out.edits {

        if vanished_nodes.contains(&e.node()) {

            notes.push(format!("change {short}: an edit of a file that vanished with the rewritten change was dropped"));

            continue;

        }

        match e {

            Edit::Insert { node, after, before, lines } => edits.push(Edit::Insert {

                node: *node,

                after: map_anchor(*after, true, notes),

                before: map_anchor(*before, false, notes),

                lines: lines.clone(),

            }),

            Edit::Delete { node, atoms } => {

                let mut mapped: Vec<(ChangeHash, u32)> = Vec::new();

                let mut dropped = 0;

                for r in atoms.iter() {

                    for i in r.from..r.to {

                        match mapping.get(&r.change) {

                            Some(Replacement::Change(nh)) => match corrs[&r.change].atoms.get(&i) {

                                Some(idx) => mapped.push((*nh, *idx)),

                                None => dropped += 1,

                            },

                            Some(Replacement::Removed(_)) => dropped += 1,

                            None => mapped.push((r.change, i)),

                        }

                    }

                }

                if dropped > 0 {

                    notes.push(format!("change {short}: {dropped} deletion(s) of lines that vanished were dropped"));

                }

                let mut ranges: Vec<AtomRange> = Vec::new();

                for (ch, i) in mapped {

                    match ranges.last_mut() {

                        Some(r) if r.change == ch && r.to == i => r.to = i + 1,

                        _ => ranges.push(AtomRange { change: ch, from: i, to: i + 1 }),

                    }

                }

                if !ranges.is_empty() {

                    edits.push(Edit::Delete { node: *node, atoms: ranges });

                }

            }

            other => edits.push(other.clone()),

        }

    }

    out.edits = edits;

    out.normalize();

    out

}

#[cfg(test)]

mod tests {

    use super::*;

    use crate::hash::ObjectRef;

    use crate::ids::{ChangeId, NodeId};

    use crate::objects::{ChangeKind, Hlc, Mode, NodeKind};

    use crate::state::FileContent;

    fn change(deps: Vec<ChangeHash>, tree_ops: Vec<TreeOp>, edits: Vec<Edit>, msg: &str) -> Change {

        let mut c = Change { change_id: ChangeId::random(), deps, author: ObjectRef::ZERO, hlc: Hlc { wall_ms: 1, logical: 0 }, message: msg.into(), tree_ops, edits, kind: ChangeKind::Normal };

        c.normalize();

        c

    }

    #[test]

    fn describe_propagates_through_dependents() {

        let mut st = State::new();

        let f = NodeId::random();

        let c1 = change(vec![], vec![TreeOp::AddNode { node: f, kind: NodeKind::File, mode: Mode::TEXT, parent: NodeId::ROOT, name: "f".into() }], vec![Edit::Insert { node: f, after: AtomRef::Start, before: AtomRef::End, lines: vec![b"a\n".to_vec(), b"b\n".to_vec()] }], "one");

        let h1 = st.add(c1.clone()).unwrap();

        let c2 = change(vec![h1], vec![], vec![Edit::Delete { node: f, atoms: vec![AtomRange { change: h1, from: 0, to: 1 }] }, Edit::Insert { node: f, after: AtomRef::Atom { change: h1, index: 1 }, before: AtomRef::End, lines: vec![b"c\n".to_vec()] }], "two");

        let h2 = st.add(c2.clone()).unwrap();

        let c3 = change(vec![h2], vec![TreeOp::SetMode { node: f, old: OpRef { change: h1, index: 0 }, mode: Mode { exec: true, opaque: false } }], vec![Edit::Insert { node: f, after: AtomRef::Atom { change: h2, index: 0 }, before: AtomRef::End, lines: vec![b"d\n".to_vec()] }], "three");

        let h3 = st.add(c3.clone()).unwrap();

        let before = st.materialize();

        // Rewrite c1's message; everything downstream follows.

        let mut n1 = c1.clone();

        n1.message = "one, described".into();

        let all: HashMap<ChangeHash, Change> = [(h1, c1.clone()), (h2, c2.clone()), (h3, c3.clone())].into_iter().collect();

        let load = |h: &ChangeHash| all.get(h).cloned();

        let rewritten = propagate(&st, h1, Some(&n1), &Correspondence::identity(&c1), &load).unwrap().changes;

        assert_eq!(rewritten.iter().map(|(h, _)| *h).collect::<Vec<_>>(), vec![h2, h3]);

        let mut st2 = State::new();

        st2.add(n1.clone()).unwrap();

        for (_, c) in &rewritten {

            st2.add(c.clone()).unwrap();

        }

        assert_eq!(st2.len(), 3);

        let after = st2.materialize();

        assert_eq!(after.files["f"].mode, before.files["f"].mode);

        match (&after.files["f"].content, &before.files["f"].content) {

            (FileContent::Text { bytes: a, .. }, FileContent::Text { bytes: b, .. }) => assert_eq!(a, b),

            _ => panic!(),

        }

        assert!(matches!(&after.files["f"].content, FileContent::Text { bytes, .. } if bytes == b"b\nc\nd\n"));

        // ChangeIds survive; hashes change; deps point at the new hashes.

        assert_eq!(rewritten[0].1.change_id, c2.change_id);

        assert_eq!(rewritten[0].1.deps, vec![n1.hash()]);

        assert_ne!(rewritten[0].1.hash(), h2);

        assert_eq!(rewritten[1].1.deps, vec![rewritten[0].1.hash()]);

    }

    #[test]

    fn missing_counterpart_is_reanchored() {

        let mut st = State::new();

        let f = NodeId::random();

        let c1 = change(vec![], vec![TreeOp::AddNode { node: f, kind: NodeKind::File, mode: Mode::TEXT, parent: NodeId::ROOT, name: "f".into() }], vec![Edit::Insert { node: f, after: AtomRef::Start, before: AtomRef::End, lines: vec![b"a\n".to_vec(), b"b\n".to_vec()] }], "one");

        let h1 = st.add(c1.clone()).unwrap();

        let c2 = change(vec![h1], vec![], vec![Edit::Insert { node: f, after: AtomRef::Atom { change: h1, index: 1 }, before: AtomRef::End, lines: vec![b"c\n".to_vec()] }], "two");

        let h2 = st.add(c2.clone()).unwrap();

        let all: HashMap<ChangeHash, Change> = [(h1, c1.clone()), (h2, c2)].into_iter().collect();

        let load = |h: &ChangeHash| all.get(h).cloned();

        // The rewritten c1 drops line "b": atom 1 has no counterpart, so c2's

        // insert after "b" is re-anchored after "a", the nearest survivor.

        let mut n1 = c1.clone();

        n1.edits = vec![Edit::Insert { node: f, after: AtomRef::Start, before: AtomRef::End, lines: vec![b"a\n".to_vec()] }];

        let corr = Correspondence { atoms: [(0, 0)].into_iter().collect(), ops: [(0, 0)].into_iter().collect() };

        let p = propagate(&st, h1, Some(&n1), &corr, &load).unwrap();

        assert_eq!(p.notes.len(), 1, "{:?}", p.notes);

        let n1h = n1.hash();

        assert!(matches!(p.changes[0].1.edits[0], Edit::Insert { after: AtomRef::Atom { change, index: 0 }, before: AtomRef::End, .. } if change == n1h));

        let mut st2 = State::new();

        st2.add(n1.clone()).unwrap();

        st2.add(p.changes[0].1.clone()).unwrap();

        let m = st2.materialize();

        assert!(!m.is_conflicted());

        assert!(matches!(&m.files["f"].content, FileContent::Text { bytes, .. } if bytes == b"a\nc\n"));

        assert_eq!(propagate(&st, ObjectRef([9; 32]), Some(&n1), &corr, &load).unwrap_err(), RewriteError::Missing(ObjectRef([9; 32])));

        // Removing c1 altogether: f vanishes with it, so c2's edit is dropped.

        let p = propagate(&st, h1, None, &Correspondence::default(), &load).unwrap();

        assert_eq!(p.notes.len(), 1, "{:?}", p.notes);

        assert!(p.changes[0].1.edits.is_empty() && p.changes[0].1.deps.is_empty());

        // Rewriting c1 to keep the file but none of its lines: c2's line goes

        // to c1's chain anchors (START, END).

        let mut n2 = c1.clone();

        n2.edits = vec![];

        let corr = Correspondence { atoms: HashMap::new(), ops: [(0, 0)].into_iter().collect() };

        let p = propagate(&st, h1, Some(&n2), &corr, &load).unwrap();

        assert!(matches!(p.changes[0].1.edits[0], Edit::Insert { after: AtomRef::Start, before: AtomRef::End, .. }));

        let mut st3 = State::new();

        st3.add(n2.clone()).unwrap();

        st3.add(p.changes[0].1.clone()).unwrap();

        let m = st3.materialize();

        assert!(!m.is_conflicted());

        assert!(matches!(&m.files["f"].content, FileContent::Text { bytes, .. } if bytes == b"c\n"));

    }

    #[test]

    fn removal_rewires_dependencies_or_fails_on_references() {

        let mut st = State::new();

        let f = NodeId::random();

        let g = NodeId::random();

        let c1 = change(vec![], vec![TreeOp::AddNode { node: f, kind: NodeKind::File, mode: Mode::TEXT, parent: NodeId::ROOT, name: "f".into() }], vec![], "one");