//! The tree graph: nodes, placements, and modes as atoms (spec §7.1, §7.2),

//! with tree conflict detection and path assignment (spec §9.2).

use crate::hash::ChangeHash;

use crate::ids::NodeId;

use crate::objects::{Mode, NodeKind, OpRef, TreeOp};

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

/// `(change, index into that change's tree_ops)`.

pub type OpKey = (ChangeHash, u32);

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

pub struct Placement {

    pub node: NodeId,

    pub parent: NodeId,

    pub name: String,

}

#[derive(Clone, Debug, Default)]

pub struct TreeGraph {

    kinds: HashMap<NodeId, NodeKind>,

    introduced: HashMap<NodeId, ChangeHash>,

    placements: HashMap<OpKey, Placement>,

    modes: HashMap<OpKey, (NodeId, Mode)>,

    /// Placement atoms retired by `RemoveNode`/`Move`, and mode atoms retired

    /// by `SetMode`. Kept apart because `AddNode` introduces one of each

    /// under the same key.

    deleted_placements: HashMap<OpKey, BTreeSet<ChangeHash>>,

    deleted_modes: HashMap<OpKey, BTreeSet<ChangeHash>>,

    placements_of: HashMap<NodeId, BTreeSet<OpKey>>,

    modes_of: HashMap<NodeId, BTreeSet<OpKey>>,

}

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

pub enum TreeConflict {

    /// Two live nodes share `(parent, name)`.

    Name { parent: NodeId, name: String, nodes: Vec<NodeId> },

    /// One node has several live placements.

    MultiPlacement { node: NodeId, placements: Vec<OpKey> },

    /// A live node's parent is not live.

    Orphan { node: NodeId, parent: NodeId },

    /// A directory is placed inside its own descendant.

    Cycle { node: NodeId },

    /// Several live mode atoms.

    Mode { node: NodeId, modes: Vec<Mode> },

}

/// A node as it appears in the working copy.

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

pub struct TreeEntry {

    pub path: String,

    pub node: NodeId,

    pub kind: NodeKind,

    pub mode: Mode,

    /// The placement this entry materializes (for building `RemoveNode`/`Move`).

    pub placement: OpKey,

    /// The live mode atom (for building `SetMode`).

    pub mode_atom: Option<OpKey>,

}

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

pub struct TreeView {

    /// Path → entry, paths use `/` and have no leading slash; conflicted

    /// entries carry a `.oxy-conflict-<n>` suffix.

    pub entries: BTreeMap<String, TreeEntry>,

    pub conflicts: Vec<TreeConflict>,

}

impl TreeView {

    pub fn is_conflicted(&self) -> bool {

        !self.conflicts.is_empty()

    }

    pub fn by_node(&self) -> HashMap<NodeId, &TreeEntry> {

        self.entries.values().map(|e| (e.node, e)).collect()

    }

}

impl TreeGraph {

    pub fn new() -> Self {

        Self::default()

    }

    /// Apply tree op `index` of `change`; `OpRef` self references must already be resolved.

    pub fn apply(&mut self, change: ChangeHash, index: u32, op: &TreeOp) {

        let key = (change, index);

        match op {

            TreeOp::AddNode { node, kind, mode, parent, name } => {

                self.kinds.insert(*node, *kind);

                self.introduced.insert(*node, change);

                self.placements.insert(key, Placement { node: *node, parent: *parent, name: name.clone() });

                self.placements_of.entry(*node).or_default().insert(key);

                if *kind != NodeKind::Dir {

                    self.modes.insert(key, (*node, *mode));

                    self.modes_of.entry(*node).or_default().insert(key);

                }

            }

            TreeOp::RemoveNode { placement, .. } => {

                self.deleted_placements.entry(op_key(*placement)).or_default().insert(change);

            }

            TreeOp::Move { node, old, parent, name } => {

                self.deleted_placements.entry(op_key(*old)).or_default().insert(change);

                self.placements.insert(key, Placement { node: *node, parent: *parent, name: name.clone() });

                self.placements_of.entry(*node).or_default().insert(key);

            }

            TreeOp::SetMode { node, old, mode } => {

                self.deleted_modes.entry(op_key(*old)).or_default().insert(change);

                self.modes.insert(key, (*node, *mode));

                self.modes_of.entry(*node).or_default().insert(key);

            }

        }

    }

    fn placement_live(&self, k: &OpKey) -> bool {

        self.deleted_placements.get(k).is_none_or(|d| d.is_empty())

    }

    fn mode_live(&self, k: &OpKey) -> bool {

        self.deleted_modes.get(k).is_none_or(|d| d.is_empty())

    }

    pub fn kind(&self, node: &NodeId) -> Option<NodeKind> {

        if node.is_root() { Some(NodeKind::Dir) } else { self.kinds.get(node).copied() }

    }

    /// The change whose `AddNode` introduced `node`.

    pub fn introducer(&self, node: &NodeId) -> Option<ChangeHash> {

        self.introduced.get(node).copied()

    }

    pub fn placement(&self, k: &OpKey) -> Option<&Placement> {

        self.placements.get(k)

    }

    pub fn live_placements(&self, node: &NodeId) -> Vec<(OpKey, &Placement)> {

        self.placements_of

            .get(node)

            .into_iter()

            .flat_map(|ks| ks.iter())

            .filter(|k| self.placement_live(k))

            .filter_map(|k| self.placements.get(k).map(|p| (*k, p)))

            .collect()

    }

    pub fn live_modes(&self, node: &NodeId) -> Vec<(OpKey, Mode)> {

        self.modes_of

            .get(node)

            .into_iter()

            .flat_map(|ks| ks.iter())

            .filter(|k| self.mode_live(k))

            .filter_map(|k| self.modes.get(k).map(|(_, m)| (*k, *m)))

            .collect()

    }

    /// Every node that has at least one live placement.

    pub fn placed_nodes(&self) -> impl Iterator<Item = NodeId> + '_ {

        self.placements_of.keys().copied().filter(|n| !self.live_placements(n).is_empty())

    }

    /// Resolve the tree: assign paths, find conflicts.

    pub fn view(&self) -> TreeView {

        let mut view = TreeView::default();

        // Live placements grouped by parent.

        let mut children: HashMap<NodeId, Vec<(OpKey, &Placement)>> = HashMap::new();

        for (k, p) in &self.placements {

            if self.placement_live(k) {

                children.entry(p.parent).or_default().push((*k, p));

            }

        }

        for c in children.values_mut() {

            c.sort_by(|a, b| a.1.name.cmp(&b.1.name).then(a.0.cmp(&b.0)));

        }

        // Multi-placement and mode conflicts.

        let mut nodes: Vec<NodeId> = self.placements_of.keys().copied().collect();

        nodes.sort();

        let mut multi: HashSet<NodeId> = HashSet::new();

        for n in &nodes {

            let lp = self.live_placements(n);

            let distinct_places: BTreeSet<(&NodeId, &str)> = lp.iter().map(|(_, p)| (&p.parent, p.name.as_str())).collect();

            if distinct_places.len() > 1 {

                multi.insert(*n);

                view.conflicts.push(TreeConflict::MultiPlacement { node: *n, placements: lp.iter().map(|(k, _)| *k).collect() });

            }

            let lm = self.live_modes(n);

            let distinct_modes: BTreeSet<Mode> = lm.iter().map(|(_, m)| *m).collect();

            if distinct_modes.len() > 1 {

                view.conflicts.push(TreeConflict::Mode { node: *n, modes: distinct_modes.into_iter().collect() });

            }

        }

        // BFS from the root, assigning paths.

        let mut reached: HashSet<NodeId> = HashSet::new();

        reached.insert(NodeId::ROOT);

        let mut queue: Vec<(NodeId, String)> = vec![(NodeId::ROOT, String::new())];

        let mut on_path: HashSet<NodeId> = HashSet::new();

        while let Some((dir, dir_path)) = queue.pop() {

            let Some(kids) = children.get(&dir) else { continue };

            // Name conflicts within this directory.

            let mut by_name: BTreeMap<&str, Vec<(OpKey, &Placement)>> = BTreeMap::new();

            for (k, p) in kids {

                by_name.entry(p.name.as_str()).or_default().push((*k, p));

            }

            for (name, group) in by_name {

                let distinct: BTreeSet<NodeId> = group.iter().map(|(_, p)| p.node).collect();

                if distinct.len() > 1 {

                    view.conflicts.push(TreeConflict::Name { parent: dir, name: name.to_string(), nodes: distinct.iter().copied().collect() });

                }

                let suffixed = distinct.len() > 1;

                for (i, (k, p)) in group.iter().enumerate() {

                    let node = p.node;

                    if node == dir || on_path.contains(&node) {

                        view.conflicts.push(TreeConflict::Cycle { node });

                        continue;

                    }

                    let needs_suffix = suffixed || multi.contains(&node);

                    let leaf = if needs_suffix { format!("{name}.oxy-conflict-{}", i + 1) } else { name.to_string() };

                    let path = if dir_path.is_empty() { leaf } else { format!("{dir_path}/{leaf}") };

                    let kind = self.kind(&node).unwrap_or(NodeKind::File);

                    let modes = self.live_modes(&node);

                    let mode_atom = modes.iter().map(|(k, _)| *k).max();

                    let mode = mode_atom.and_then(|k| self.modes.get(&k).map(|(_, m)| *m)).unwrap_or_default();

                    view.entries.insert(path.clone(), TreeEntry { path: path.clone(), node, kind, mode, placement: *k, mode_atom });

                    if kind == NodeKind::Dir && reached.insert(node) {

                        on_path.insert(dir);

                        queue.push((node, path));

                    } else {

                        reached.insert(node);

                    }

                }

            }

        }

        // Nodes with live placements that were never reached: orphans or cycles.

        for n in &nodes {

            if reached.contains(n) {

                continue;

            }

            let lp = self.live_placements(n);

            if lp.is_empty() {

                continue;

            }

            let mut seen = HashSet::new();

            let mut cur = *n;

            let conflict = loop {

                if !seen.insert(cur) {

                    break TreeConflict::Cycle { node: *n };

                }

                let lp = self.live_placements(&cur);

                let Some((_, p)) = lp.first() else {

                    break TreeConflict::Orphan { node: *n, parent: cur };

                };

                if reached.contains(&p.parent) {

                    // Parent reached but this node was not: the parent is not a

                    // directory, so this is a name/kind problem surfaced as orphan.

                    break TreeConflict::Orphan { node: *n, parent: p.parent };

                }

                cur = p.parent;

            };

            if !view.conflicts.contains(&conflict) {

                view.conflicts.push(conflict);

            }

        }

        view

    }

}

pub fn op_key(r: OpRef) -> OpKey {

    (r.change, r.index)

}

#[cfg(test)]

mod tests {

    use super::*;

    use crate::hash::ObjectRef;

    fn h(n: u8) -> ChangeHash {

        ObjectRef([n; 32])

    }

    fn nid(n: u8) -> NodeId {

        NodeId([n; 16])

    }

    fn add(g: &mut TreeGraph, c: u8, i: u32, node: u8, kind: NodeKind, parent: NodeId, name: &str) {

        g.apply(h(c), i, &TreeOp::AddNode { node: nid(node), kind, mode: Mode::TEXT, parent, name: name.into() });

    }

    fn paths(v: &TreeView) -> Vec<String> {

        v.entries.keys().cloned().collect()

    }

    #[test]

    fn nested_paths_and_rename() {

        let mut g = TreeGraph::new();

        add(&mut g, 1, 0, 1, NodeKind::Dir, NodeId::ROOT, "src");

        add(&mut g, 1, 1, 2, NodeKind::File, nid(1), "main.rs");

        add(&mut g, 1, 2, 3, NodeKind::File, NodeId::ROOT, "README");

        let v = g.view();

        assert_eq!(paths(&v), ["README", "src", "src/main.rs"]);

        assert!(!v.is_conflicted());

        // Rename src/main.rs → src/lib.rs, move src → lib (subtree follows).

        g.apply(h(2), 0, &TreeOp::Move { node: nid(2), old: OpRef { change: h(1), index: 1 }, parent: nid(1), name: "lib.rs".into() });

        g.apply(h(2), 1, &TreeOp::Move { node: nid(1), old: OpRef { change: h(1), index: 0 }, parent: NodeId::ROOT, name: "lib".into() });

        let v = g.view();

        assert_eq!(paths(&v), ["README", "lib", "lib/lib.rs"]);

        assert_eq!(v.entries["lib/lib.rs"].placement, (h(2), 0));

        g.apply(h(3), 0, &TreeOp::RemoveNode { node: nid(3), placement: OpRef { change: h(1), index: 2 } });

        assert_eq!(paths(&g.view()), ["lib", "lib/lib.rs"]);

    }

    #[test]

    fn name_conflict_gets_suffixes() {

        let mut g = TreeGraph::new();

        add(&mut g, 1, 0, 1, NodeKind::File, NodeId::ROOT, "a.txt");

        add(&mut g, 2, 0, 2, NodeKind::File, NodeId::ROOT, "a.txt");

        let v = g.view();

        assert_eq!(paths(&v), ["a.txt.oxy-conflict-1", "a.txt.oxy-conflict-2"]);

        assert_eq!(v.conflicts, vec![TreeConflict::Name { parent: NodeId::ROOT, name: "a.txt".into(), nodes: vec![nid(1), nid(2)] }]);

    }

    #[test]

    fn concurrent_renames_are_multi_placement() {

        let mut g = TreeGraph::new();

        add(&mut g, 1, 0, 1, NodeKind::File, NodeId::ROOT, "a");

        g.apply(h(2), 0, &TreeOp::Move { node: nid(1), old: OpRef { change: h(1), index: 0 }, parent: NodeId::ROOT, name: "b".into() });

        g.apply(h(3), 0, &TreeOp::Move { node: nid(1), old: OpRef { change: h(1), index: 0 }, parent: NodeId::ROOT, name: "c".into() });

        let v = g.view();

        assert_eq!(paths(&v), ["b.oxy-conflict-1", "c.oxy-conflict-1"]);

        assert!(matches!(v.conflicts[0], TreeConflict::MultiPlacement { node, .. } if node == nid(1)));

    }

    #[test]

    fn orphan_and_cycle() {

        let mut g = TreeGraph::new();

        add(&mut g, 1, 0, 1, NodeKind::Dir, NodeId::ROOT, "d");

        add(&mut g, 1, 1, 2, NodeKind::File, nid(1), "f");

        // Concurrently: 2 removes d, 3 adds d/g.

        g.apply(h(2), 0, &TreeOp::RemoveNode { node: nid(1), placement: OpRef { change: h(1), index: 0 } });

        add(&mut g, 3, 0, 3, NodeKind::File, nid(1), "g");

        let v = g.view();

        assert_eq!(paths(&v), Vec::<String>::new());

        assert!(v.conflicts.contains(&TreeConflict::Orphan { node: nid(2), parent: nid(1) }));

        assert!(v.conflicts.contains(&TreeConflict::Orphan { node: nid(3), parent: nid(1) }));

        // Cycle: a/b, then concurrently move a under b and b under a's parent... simplest: move a into b.

        let mut g = TreeGraph::new();

        add(&mut g, 1, 0, 1, NodeKind::Dir, NodeId::ROOT, "a");

        add(&mut g, 1, 1, 2, NodeKind::Dir, nid(1), "b");

        g.apply(h(2), 0, &TreeOp::Move { node: nid(1), old: OpRef { change: h(1), index: 0 }, parent: nid(2), name: "a".into() });

        let v = g.view();

        assert!(v.conflicts.iter().any(|c| matches!(c, TreeConflict::Cycle { .. })), "{:?}", v.conflicts);

    }

    #[test]

    fn mode_conflict_and_resolution() {

        let mut g = TreeGraph::new();

        add(&mut g, 1, 0, 1, NodeKind::File, NodeId::ROOT, "run.sh");

        g.apply(h(2), 0, &TreeOp::SetMode { node: nid(1), old: OpRef { change: h(1), index: 0 }, mode: Mode { exec: true, opaque: false } });

        g.apply(h(3), 0, &TreeOp::SetMode { node: nid(1), old: OpRef { change: h(1), index: 0 }, mode: Mode { exec: false, opaque: true } });

        let v = g.view();

        assert!(matches!(v.conflicts[0], TreeConflict::Mode { .. }));

        // Materialized with the greatest mode atom.

        assert_eq!(v.entries["run.sh"].mode, Mode { exec: false, opaque: true });

        // The placement introduced by the same AddNode is unaffected.

        assert_eq!(v.entries["run.sh"].placement, (h(1), 0));

        // Resolution: retire both live mode atoms; identical live values do not conflict.

        g.apply(h(4), 0, &TreeOp::SetMode { node: nid(1), old: OpRef { change: h(2), index: 0 }, mode: Mode { exec: true, opaque: false } });

        g.apply(h(4), 1, &TreeOp::SetMode { node: nid(1), old: OpRef { change: h(3), index: 0 }, mode: Mode { exec: true, opaque: false } });

        let v = g.view();

        assert!(!v.is_conflicted(), "{:?}", v.conflicts);

        assert_eq!(v.entries["run.sh"].mode, Mode { exec: true, opaque: false });

    }

}