//! A retained node tree, painted into a character grid.
//!
//! The same arena glimmer's reconciler expects everywhere else: nodes are
//! integer handles, `create` / `apply-props!` / `append-child!` mutate them,
//! and nothing is drawn until the frame call walks the whole thing at once.
//! Interactions come back as a queue the caller drains, because a jolt closure
//! cannot be a callback down here — identity crosses the boundary instead.
//!
//! This module knows nothing about terminals. It is the data; [`crate::layout`]
//! measures it and [`crate::paint`] draws it.

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

/// A prop value: the three types the ABI can carry, which is all glimmer needs.
/// Keywords and colours arrive as strings, numbers as doubles, flags as ints.
#[derive(Clone, Debug, PartialEq)]
pub enum Value {
    Str(String),
    Num(f64),
    Bool(bool),
}

/// What a node renders as.
///
/// An unknown tag is kept rather than refused — it paints as a vertical box, so
/// a component written against a tag this backend has not grown yet still shows
/// its children instead of nothing.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Tag {
    Window,
    Box,
    Frame,
    Scroll,
    Overlay,
    Label,
    Title,
    DimLabel,
    Button,
    CheckButton,
    Entry,
    Separator,
    Spacer,
    Listbox,
    Progress,
    Spinner,
    Reaction,
    Emoji,
    Image,
    Unknown(String),
}

impl Default for Tag {
    fn default() -> Self {
        Self::Unknown(String::new())
    }
}

impl Tag {
    fn parse(name: &str) -> Self {
        match name {
            "window" => Self::Window,
            "box" | "hbox" | "vbox" => Self::Box,
            "frame" => Self::Frame,
            "scroll" => Self::Scroll,
            "overlay" => Self::Overlay,
            "label" => Self::Label,
            "title" | "title-2" => Self::Title,
            "dim-label" => Self::DimLabel,
            "button" => Self::Button,
            "checkbutton" | "checkbox" => Self::CheckButton,
            "entry" => Self::Entry,
            "separator" => Self::Separator,
            "spacer" | "gap" => Self::Spacer,
            "listbox" => Self::Listbox,
            "progress" => Self::Progress,
            "spinner" => Self::Spinner,
            // The two glyph nodes. A reaction is a pill somebody can press —
            // the count of who is on it, and whether you are one of them; an
            // emoji is the same glyph with none of that, a character in a
            // sentence. Both carry what to draw in `:emoji` rather than in a
            // label, which is why an unknown tag painted neither.
            "reaction" => Self::Reaction,
            "emoji" => Self::Emoji,
            // A picture, which a cell grid cannot hold: the painter reserves
            // the cells and the terminal draws it over them, where it has the
            // protocol for that. See `crate::graphics`.
            "image" => Self::Image,
            other => Self::Unknown(other.to_owned()),
        }
    }

    /// The canonical name: `hbox` and `vbox` are one node, so both answer
    /// `box` and carry their orientation in a prop.
    pub fn name(&self) -> &str {
        match self {
            Self::Window => "window",
            Self::Box => "box",
            Self::Frame => "frame",
            Self::Scroll => "scroll",
            Self::Overlay => "overlay",
            Self::Label => "label",
            Self::Title => "title",
            Self::DimLabel => "dim-label",
            Self::Button => "button",
            Self::CheckButton => "checkbutton",
            Self::Entry => "entry",
            Self::Separator => "separator",
            Self::Spacer => "spacer",
            Self::Listbox => "listbox",
            Self::Progress => "progress",
            Self::Spinner => "spinner",
            Self::Reaction => "reaction",
            Self::Emoji => "emoji",
            Self::Image => "image",
            Self::Unknown(name) => name,
        }
    }

    /// Whether the focus ring stops here. A container never takes focus of its
    /// own; a control that does nothing with a key does not either.
    pub fn focusable(&self) -> bool {
        matches!(
            self,
            Self::Button | Self::CheckButton | Self::Entry | Self::Listbox | Self::Reaction
        )
    }
}

/// One interaction, waiting to be drained by the caller. Names are glimmer's
/// handler props with the `on-` dropped.
#[derive(Clone, Debug, PartialEq)]
pub struct Event {
    pub node: u32,
    pub name: &'static str,
    pub text: String,
    pub num: f64,
}

#[derive(Clone, Debug, Default)]
struct Node {
    tag: Tag,
    props: Props,
    children: Vec<u32>,
    /// When this node or anything under it last changed. A size measured of
    /// this subtree is good for exactly as long as this number holds still,
    /// which is what lets one outlive the frame it was taken in.
    rev: u64,
    /// 0 when unparented. The root's parent is 0 as well, which is what stops
    /// the ancestor walk in [`Tree::would_cycle`].
    parent: u32,
}

/// A node's props.
///
/// Reading them through this rather than the map means a missing prop and a
/// prop of the wrong type answer the same thing: the default. Nothing a caller
/// can write should be able to make a widget vanish.
#[derive(Clone, Debug, Default)]
pub struct Props(pub HashMap<String, Value>);

impl Props {
    pub fn str(&self, key: &str) -> &str {
        match self.0.get(key) {
            Some(Value::Str(s)) => s,
            _ => "",
        }
    }

    pub fn num(&self, key: &str, fallback: f64) -> f64 {
        match self.0.get(key) {
            Some(Value::Num(n)) => *n,
            Some(Value::Bool(b)) => {
                if *b {
                    1.0
                } else {
                    0.0
                }
            }
            _ => fallback,
        }
    }

    /// A count of cells. Negative and absurd values are clamped rather than
    /// cast, since `as u16` on a negative double is a silent 0 or 65535.
    pub fn cells(&self, key: &str, fallback: u16) -> u16 {
        match self.0.get(key) {
            Some(Value::Num(n)) if n.is_finite() => n.clamp(0.0, u16::MAX as f64) as u16,
            _ => fallback,
        }
    }

    pub fn bool(&self, key: &str, fallback: bool) -> bool {
        match self.0.get(key) {
            Some(Value::Bool(b)) => *b,
            Some(Value::Num(n)) => *n != 0.0,
            Some(Value::Str(s)) => s == "true",
            _ => fallback,
        }
    }

    pub fn has(&self, key: &str) -> bool {
        self.0.contains_key(key)
    }

    /// The text a widget shows. `:label` and `:text` are the same prop to every
    /// glimmer backend; whichever the caller wrote is the one that shows.
    pub fn label(&self) -> &str {
        if self.has("label") {
            self.str("label")
        } else {
            self.str("text")
        }
    }
}

/// One prop value as EDN. Whole numbers print without a trailing `.0`: every
/// number crossed the boundary as a double, and `{:spacing 8}` reads better
/// than `{:spacing 8.0}`.
fn write_value(value: &Value, out: &mut String) {
    match value {
        Value::Bool(b) => out.push_str(if *b { "true" } else { "false" }),
        Value::Num(n) => {
            if n.is_finite() && n.fract() == 0.0 && n.abs() < 1e15 {
                out.push_str(&format!("{}", *n as i64));
            } else if n.is_finite() {
                out.push_str(&format!("{n}"));
            } else {
                // EDN has no infinity or NaN literal; say nil rather than emit
                // something no reader will take.
                out.push_str("nil");
            }
        }
        Value::Str(text) => {
            out.push('"');
            for c in text.chars() {
                match c {
                    '"' => out.push_str("\\\""),
                    '\\' => out.push_str("\\\\"),
                    '\n' => out.push_str("\\n"),
                    '\r' => out.push_str("\\r"),
                    '\t' => out.push_str("\\t"),
                    _ => out.push(c),
                }
            }
            out.push('"');
        }
    }
}

pub struct Tree {
    /// Index 0 is never handed out: 0 is "no node" throughout the ABI.
    nodes: Vec<Option<Node>>,
    free: Vec<u32>,
    root: u32,
    pending: VecDeque<Event>,
    current: Option<Event>,
    /// Counts every change to any node. Never read for itself — it is what
    /// stamps `Node::rev`, so that two changes are never confused for one.
    revision: u64,
}

impl Default for Tree {
    fn default() -> Self {
        Self::new()
    }
}

impl Tree {
    pub fn new() -> Self {
        let mut tree = Self {
            nodes: vec![None],
            free: Vec::new(),
            root: 0,
            pending: VecDeque::new(),
            current: None,
            revision: 0,
        };
        tree.root = tree.new_node("window");
        tree
    }

    pub fn root(&self) -> u32 {
        self.root
    }

    fn slot(&self, id: u32) -> Option<&Node> {
        self.nodes.get(id as usize).and_then(|n| n.as_ref())
    }

    /// The one way to a node that can be changed — so it is the one place a
    /// change has to be recorded. Handing the caller a `&mut Node` is handing
    /// them everything a measurement of it depended on; whether they write to
    /// it or not, this is where a cache has to assume they did.
    fn slot_mut(&mut self, id: u32) -> Option<&mut Node> {
        self.touch(id);
        self.nodes.get_mut(id as usize).and_then(|n| n.as_mut())
    }

    /// Mark `id` and every node above it as changed.
    ///
    /// Upwards, because that is the direction sizes travel: how tall a message
    /// is depends on its own words, and how tall the backlog is depends on the
    /// message — so a word typed into one line makes every ancestor's measured
    /// size a lie, and no sibling's. Walking the parents is what keeps a new
    /// message at the bottom of a long backlog from throwing away the
    /// measurements of the hundred above it that did not move.
    fn touch(&mut self, id: u32) {
        self.revision = self.revision.wrapping_add(1);
        let now = self.revision;
        let mut at = id;
        // Bounded by the depth of the tree, and by the node count besides: a
        // parent chain cannot revisit a node, since `would_cycle` is what stops
        // one being built.
        while at != 0 {
            match self.nodes.get_mut(at as usize).and_then(|n| n.as_mut()) {
                Some(node) => {
                    node.rev = now;
                    at = node.parent;
                }
                None => break,
            }
        }
    }

    /// When this node's subtree last changed. A measurement of it taken at the
    /// same number is still the right answer.
    pub fn revision_of(&self, id: u32) -> u64 {
        self.slot(id).map_or(0, |n| n.rev)
    }

    pub fn exists(&self, id: u32) -> bool {
        self.slot(id).is_some()
    }

    pub fn new_node(&mut self, tag: &str) -> u32 {
        self.revision = self.revision.wrapping_add(1);
        let node = Node {
            tag: Tag::parse(tag),
            rev: self.revision,
            ..Node::default()
        };
        match self.free.pop() {
            Some(id) => {
                self.nodes[id as usize] = Some(node);
                id
            }
            None => {
                self.nodes.push(Some(node));
                (self.nodes.len() - 1) as u32
            }
        }
    }

    /// Free `id` and everything under it. The root is refused: the window node
    /// is the one thing a caller cannot drop out from under itself.
    pub fn free_node(&mut self, id: u32) {
        if id == self.root || !self.exists(id) {
            return;
        }
        let parent = self.slot(id).map(|n| n.parent).unwrap_or(0);
        if parent != 0 {
            if let Some(node) = self.slot_mut(parent) {
                node.children.retain(|c| *c != id);
            }
        }
        self.free_subtree(id);
    }

    fn free_subtree(&mut self, id: u32) {
        let children = self
            .slot(id)
            .map(|n| n.children.clone())
            .unwrap_or_default();
        for child in children {
            self.free_subtree(child);
        }
        if self.nodes[id as usize].take().is_some() {
            self.revision = self.revision.wrapping_add(1);
            self.free.push(id);
        }
        // An event queued against a node that has since gone would be routed to
        // a handler the reconciler has already dropped. Drop it here instead.
        self.pending.retain(|e| e.node != id);
    }

    /// Whether making `child` a child of `parent` would make a loop — `child`
    /// being `parent` or one of its ancestors.
    fn would_cycle(&self, parent: u32, child: u32) -> bool {
        let mut at = parent;
        while at != 0 {
            if at == child {
                return true;
            }
            at = match self.slot(at) {
                Some(node) => node.parent,
                None => return false,
            };
        }
        false
    }

    fn unparent(&mut self, child: u32) {
        let parent = self.slot(child).map(|n| n.parent).unwrap_or(0);
        if parent != 0 {
            if let Some(node) = self.slot_mut(parent) {
                node.children.retain(|c| *c != child);
            }
        }
        if let Some(node) = self.slot_mut(child) {
            node.parent = 0;
        }
    }

    pub fn append(&mut self, parent: u32, child: u32) -> bool {
        if !self.exists(parent) || !self.exists(child) || self.would_cycle(parent, child) {
            return false;
        }
        self.unparent(child);
        self.slot_mut(parent).unwrap().children.push(child);
        self.slot_mut(child).unwrap().parent = parent;
        true
    }

    /// Unparent *and* free `child`, which is what the reconciler means by
    /// remove: a node it has taken out of the tree is a node it has dropped.
    pub fn remove(&mut self, parent: u32, child: u32) {
        if self.slot(child).map(|n| n.parent) == Some(parent) {
            self.free_node(child);
        }
    }

    /// Move `child` after `sibling`; `sibling` 0 means the first position.
    pub fn insert_after(&mut self, parent: u32, child: u32, sibling: u32) -> bool {
        if !self.exists(parent) || !self.exists(child) || self.would_cycle(parent, child) {
            return false;
        }
        if sibling != 0 && self.slot(sibling).map(|n| n.parent) != Some(parent) {
            return false;
        }
        self.unparent(child);
        let at = match sibling {
            0 => 0,
            _ => {
                let children = &self.slot(parent).unwrap().children;
                children
                    .iter()
                    .position(|c| *c == sibling)
                    .map_or(0, |i| i + 1)
            }
        };
        self.slot_mut(parent).unwrap().children.insert(at, child);
        self.slot_mut(child).unwrap().parent = parent;
        true
    }

    /// Put `new` where `old` was, and free `old`.
    pub fn replace(&mut self, parent: u32, old: u32, new: u32) -> bool {
        if self.slot(old).map(|n| n.parent) != Some(parent) || !self.exists(new) {
            return false;
        }
        if self.would_cycle(parent, new) {
            return false;
        }
        self.unparent(new);
        let at = self
            .slot(parent)
            .and_then(|n| n.children.iter().position(|c| *c == old));
        let Some(at) = at else { return false };
        self.slot_mut(parent).unwrap().children[at] = new;
        self.slot_mut(new).unwrap().parent = parent;
        if let Some(node) = self.slot_mut(old) {
            node.parent = 0;
        }
        self.free_subtree(old);
        true
    }

    // ── reading it back ─────────────────────────────────────────────────────

    pub fn tag(&self, id: u32) -> Tag {
        self.slot(id).map(|n| n.tag.clone()).unwrap_or_default()
    }

    pub fn tag_name(&self, id: u32) -> &str {
        self.slot(id).map_or("", |n| n.tag.name())
    }

    pub fn children(&self, id: u32) -> Vec<u32> {
        self.slot(id)
            .map(|n| n.children.clone())
            .unwrap_or_default()
    }

    pub fn child_count(&self, id: u32) -> usize {
        self.slot(id).map_or(0, |n| n.children.len())
    }

    pub fn child_at(&self, id: u32, index: usize) -> u32 {
        self.slot(id)
            .and_then(|n| n.children.get(index).copied())
            .unwrap_or(0)
    }

    pub fn parent(&self, id: u32) -> u32 {
        self.slot(id).map_or(0, |n| n.parent)
    }

    /// A node's props, borrowed. A node that is not there lends the empty set,
    /// which reads as every default — the same answer `props` has always given
    /// for a missing node, without the copy.
    ///
    /// The copying `props` below is what a caller that needs to keep them past
    /// the borrow uses. Measuring and painting do not: they read a handful of
    /// values and are done, and cloning a whole map per node per question was
    /// most of what a frame cost.
    pub fn props_of(&self, id: u32) -> &Props {
        static NONE: std::sync::OnceLock<Props> = std::sync::OnceLock::new();
        match self.slot(id) {
            Some(node) => &node.props,
            None => NONE.get_or_init(Props::default),
        }
    }

    /// A node's tag, borrowed. `Tag::Unknown` carries the name it was given,
    /// so `tag` is a string copy per call where this is a look.
    pub fn tag_of(&self, id: u32) -> &Tag {
        static NONE: std::sync::OnceLock<Tag> = std::sync::OnceLock::new();
        match self.slot(id) {
            Some(node) => &node.tag,
            None => NONE.get_or_init(Tag::default),
        }
    }

    /// A node's children, borrowed.
    pub fn children_of(&self, id: u32) -> &[u32] {
        self.slot(id).map_or(&[], |n| n.children.as_slice())
    }

    pub fn props(&self, id: u32) -> Props {
        self.props_of(id).clone()
    }

    pub fn set(&mut self, id: u32, key: &str, value: Value) {
        if let Some(node) = self.slot_mut(id) {
            node.props.0.insert(key.to_owned(), value);
        }
    }

    pub fn clear_props(&mut self, id: u32) {
        if let Some(node) = self.slot_mut(id) {
            node.props.0.clear();
        }
    }

    pub fn get(&self, id: u32, key: &str) -> Option<&Value> {
        self.slot(id).and_then(|n| n.props.0.get(key))
    }

    /// The subtree at `id` as pretty-printed hiccup — what the tree *is*, read
    /// back from the arena, rather than what a component meant to build.
    ///
    /// Props are sorted, so two dumps of the same tree compare as text.
    pub fn dump(&self, id: u32) -> String {
        let mut out = String::new();
        self.dump_into(id, 0, &mut out);
        out
    }

    fn dump_into(&self, id: u32, depth: usize, out: &mut String) {
        let Some(node) = self.slot(id) else {
            out.push_str("nil");
            return;
        };
        let indent = "  ".repeat(depth);
        out.push_str("[:");
        out.push_str(node.tag.name());

        let mut keys: Vec<&String> = node.props.0.keys().collect();
        keys.sort();
        out.push_str(" {");
        for (i, key) in keys.iter().enumerate() {
            if i > 0 {
                out.push(' ');
            }
            out.push(':');
            out.push_str(key);
            out.push(' ');
            write_value(&node.props.0[*key], out);
        }
        out.push('}');

        for child in &node.children {
            out.push('\n');
            out.push_str(&indent);
            out.push_str("  ");
            self.dump_into(*child, depth + 1, out);
        }
        out.push(']');
    }

    // ── events ──────────────────────────────────────────────────────────────

    pub fn emit(&mut self, node: u32, name: &'static str, text: String, num: f64) {
        self.pending.push_back(Event {
            node,
            name,
            text,
            num,
        });
    }

    /// Dequeue one event into the accessor slot. False when the queue is empty.
    pub fn poll(&mut self) -> bool {
        self.current = self.pending.pop_front();
        self.current.is_some()
    }

    pub fn current(&self) -> Option<&Event> {
        self.current.as_ref()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn tree_with_button() -> (Tree, u32) {
        let mut tree = Tree::new();
        let button = tree.new_node("button");
        tree.set(button, "label", Value::Str("go".into()));
        let root = tree.root();
        tree.append(root, button);
        (tree, button)
    }

    #[test]
    fn a_dump_is_the_tree_as_hiccup_with_sorted_props() {
        let (mut tree, button) = tree_with_button();
        tree.set(button, "kind", Value::Str("primary".into()));
        assert_eq!(
            tree.dump(tree.root()),
            "[:window {}\n  [:button {:kind \"primary\" :label \"go\"}]]"
        );
    }

    #[test]
    fn hbox_and_vbox_are_one_node() {
        let mut tree = Tree::new();
        let h = tree.new_node("hbox");
        let v = tree.new_node("vbox");
        assert_eq!(tree.tag_name(h), "box");
        assert_eq!(tree.tag_name(v), "box");
    }

    #[test]
    fn an_unknown_tag_keeps_its_name() {
        let mut tree = Tree::new();
        let node = tree.new_node("sparkline");
        assert_eq!(tree.tag_name(node), "sparkline");
        assert_eq!(tree.tag(node), Tag::Unknown("sparkline".into()));
    }

    #[test]
    fn removing_a_node_frees_its_subtree_and_reuses_the_handles() {
        let mut tree = Tree::new();
        let outer = tree.new_node("vbox");
        let inner = tree.new_node("label");
        tree.append(outer, inner);
        tree.append(tree.root(), outer);
        tree.remove(tree.root(), outer);
        assert!(!tree.exists(outer));
        assert!(!tree.exists(inner));
        assert_eq!(tree.child_count(tree.root()), 0);
        // The arena hands the slots back out rather than growing forever.
        assert!([outer, inner].contains(&tree.new_node("label")));
    }

    #[test]
    fn a_node_cannot_become_its_own_ancestor() {
        let mut tree = Tree::new();
        let outer = tree.new_node("vbox");
        let inner = tree.new_node("vbox");
        tree.append(outer, inner);
        assert!(!tree.append(inner, outer));
        assert_eq!(tree.parent(outer), 0);
    }

    #[test]
    fn insert_after_zero_is_the_first_position() {
        let mut tree = Tree::new();
        let (a, b, c) = (
            tree.new_node("label"),
            tree.new_node("label"),
            tree.new_node("label"),
        );
        let root = tree.root();
        tree.append(root, a);
        tree.append(root, b);
        tree.insert_after(root, c, 0);
        assert_eq!(tree.children(root), vec![c, a, b]);
        tree.insert_after(root, c, a);
        assert_eq!(tree.children(root), vec![a, c, b]);
    }

    #[test]
    fn replace_keeps_the_position_and_frees_the_old_node() {
        let mut tree = Tree::new();
        let root = tree.root();
        let (a, b) = (tree.new_node("label"), tree.new_node("label"));
        tree.append(root, a);
        tree.append(root, b);
        let fresh = tree.new_node("button");
        assert!(tree.replace(root, a, fresh));
        assert_eq!(tree.children(root), vec![fresh, b]);
        assert!(!tree.exists(a));
    }

    #[test]
    fn the_root_cannot_be_freed() {
        let mut tree = Tree::new();
        let root = tree.root();
        tree.free_node(root);
        assert!(tree.exists(root));
    }

    #[test]
    fn an_event_for_a_freed_node_never_reaches_the_caller() {
        let (mut tree, button) = tree_with_button();
        tree.emit(button, "click", String::new(), 0.0);
        tree.remove(tree.root(), button);
        assert!(!tree.poll());
    }

    #[test]
    fn props_of_the_wrong_type_read_as_the_default() {
        let mut tree = Tree::new();
        let node = tree.new_node("progress");
        tree.set(node, "value", Value::Str("lots".into()));
        let props = tree.props(node);
        assert_eq!(props.num("value", 0.5), 0.5);
        assert_eq!(props.cells("width-request", 7), 7);
    }

    #[test]
    fn label_and_text_are_the_same_prop() {
        let mut tree = Tree::new();
        let node = tree.new_node("label");
        tree.set(node, "text", Value::Str("hello".into()));
        assert_eq!(tree.props(node).label(), "hello");
        tree.set(node, "label", Value::Str("hi".into()));
        assert_eq!(tree.props(node).label(), "hi");
    }
}