reratui 1.1.0

//! Tree diffing and reconciliation.
//!
//! This module implements a React-like reconciliation algorithm for efficiently
//! updating the component tree. It compares old and new element trees and generates
//! a minimal set of patches to transform the old tree into the new tree.
//!
//! # Reconciliation Strategy
//!
//! The reconciliation algorithm follows these steps:
//!
//! 1. **Key-based matching**: If elements have keys, match by key first
//! 2. **Type + position matching**: For elements without keys, match by type and position
//! 3. **Patch generation**: Generate Create, Update, Delete, and Move patches
//! 4. **Patch application**: Apply patches to the fiber tree
//!
//! # Example
//!
//! ```rust,ignore
//! use reratui::scheduler::reconciler::{Reconciler, ElementTree};
//!
//! let old_tree = ElementTree::from_elements(old_elements);
//! let new_tree = ElementTree::from_elements(new_elements);
//!
//! let reconciler = Reconciler::new(Some(old_tree), new_tree);
//! let patches = reconciler.diff();
//! reconciler.apply(patches, &mut fiber_tree);
//! ```

use std::collections::HashMap;

use crate::element::Element;
use crate::fiber::FiberId;
use crate::fiber_tree::FiberTree;

/// Represents a change to be applied to the fiber tree.
///
/// Patches are generated by comparing old and new element trees and
/// represent the minimal set of operations needed to transform the
/// old tree into the new tree.
#[derive(Debug, Clone, PartialEq)]
pub enum Patch {
    /// Create a new fiber for an element that didn't exist before.
    ///
    /// # Fields
    ///
    /// * `element` - The element to create a fiber for
    /// * `parent` - The parent fiber ID (if any)
    /// * `position` - The position in the parent's children list
    Create {
        element: Element,
        parent: Option<FiberId>,
        position: usize,
    },

    /// Update an existing fiber because the element changed.
    ///
    /// # Fields
    ///
    /// * `old_index` - The index in the old tree (for fiber lookup)
    /// * `element` - The new element
    Update { old_index: usize, element: Element },

    /// Delete a fiber because the element no longer exists.
    ///
    /// # Fields
    ///
    /// * `old_index` - The index in the old tree (for fiber lookup)
    Delete { old_index: usize },

    /// Move a fiber to a new position in the tree.
    ///
    /// # Fields
    ///
    /// * `old_index` - The index in the old tree (for fiber lookup)
    /// * `new_position` - The new position in the parent's children list
    Move {
        old_index: usize,
        new_position: usize,
    },
}

/// Represents a tree of elements for reconciliation.
///
/// This structure holds a collection of elements and provides methods
/// for comparing with another tree to generate patches.
#[derive(Debug, Clone)]
pub struct ElementTree {
    /// The root elements of the tree
    pub elements: Vec<Element>,
    /// Map of keys to element indices for efficient key-based lookup
    pub key_map: HashMap<String, usize>,
}

impl ElementTree {
    /// Create a new element tree from a vector of elements.
    ///
    /// This builds the key map for efficient key-based matching during reconciliation.
    ///
    /// # Arguments
    ///
    /// * `elements` - The elements to include in the tree
    ///
    /// # Example
    ///
    /// ```rust,ignore
    /// let tree = ElementTree::from_elements(vec![
    ///     Element::text("Hello"),
    ///     Element::widget(Paragraph::new("World")).with_key("para"),
    /// ]);
    /// ```
    pub fn from_elements(elements: Vec<Element>) -> Self {
        let mut key_map = HashMap::new();

        for (index, element) in elements.iter().enumerate() {
            if let Some(key) = element.key() {
                key_map.insert(key.to_string(), index);
            }
        }

        Self { elements, key_map }
    }

    /// Create an empty element tree.
    pub fn empty() -> Self {
        Self {
            elements: Vec::new(),
            key_map: HashMap::new(),
        }
    }

    /// Get the number of elements in the tree.
    pub fn len(&self) -> usize {
        self.elements.len()
    }

    /// Check if the tree is empty.
    pub fn is_empty(&self) -> bool {
        self.elements.is_empty()
    }

    /// Get an element by index.
    pub fn get(&self, index: usize) -> Option<&Element> {
        self.elements.get(index)
    }

    /// Get an element by key.
    pub fn get_by_key(&self, key: &str) -> Option<&Element> {
        self.key_map.get(key).and_then(|&index| self.get(index))
    }
}

/// Represents a match between an old element and a new element.
///
/// This is used during reconciliation to determine which elements
/// correspond to each other between the old and new trees.
#[derive(Debug, Clone, PartialEq)]
pub enum Match {
    /// Both old and new elements exist and match (same key or same type + position).
    ///
    /// # Fields
    ///
    /// * `old_index` - Index in the old tree
    /// * `new_index` - Index in the new tree
    /// * `fiber_id` - The existing fiber ID (if known)
    Matched {
        old_index: usize,
        new_index: usize,
        fiber_id: Option<FiberId>,
    },

    /// A new element exists but no corresponding old element.
    ///
    /// # Fields
    ///
    /// * `new_index` - Index in the new tree
    New { new_index: usize },

    /// An old element exists but no corresponding new element.
    ///
    /// # Fields
    ///
    /// * `old_index` - Index in the old tree
    /// * `fiber_id` - The existing fiber ID (if known)
    Removed {
        old_index: usize,
        fiber_id: Option<FiberId>,
    },
}

/// The reconciler compares old and new element trees and generates patches.
///
/// This implements a React-like reconciliation algorithm that efficiently
/// determines the minimal set of changes needed to transform the old tree
/// into the new tree.
pub struct Reconciler {
    /// The old element tree (if any)
    old_tree: Option<ElementTree>,
    /// The new element tree
    new_tree: ElementTree,
}

impl Reconciler {
    /// Create a new reconciler with old and new element trees.
    ///
    /// # Arguments
    ///
    /// * `old_tree` - The previous element tree (None for initial render)
    /// * `new_tree` - The new element tree to reconcile to
    ///
    /// # Example
    ///
    /// ```rust,ignore
    /// let reconciler = Reconciler::new(Some(old_tree), new_tree);
    /// ```
    pub fn new(old_tree: Option<ElementTree>, new_tree: ElementTree) -> Self {
        Self { old_tree, new_tree }
    }

    /// Compare the old and new trees and generate a list of patches.
    ///
    /// This method implements the core reconciliation algorithm:
    /// 1. Match elements by key (if available)
    /// 2. Match remaining elements by type + position
    /// 3. Generate patches for differences
    ///
    /// The algorithm handles flat lists of elements at each level. For nested
    /// structures (like fragments), each component is responsible for reconciling
    /// its own children. This matches React's reconciliation model where each
    /// component manages its own subtree.
    ///
    /// # Returns
    ///
    /// A vector of patches to apply to transform the old tree into the new tree.
    ///
    /// # Example
    ///
    /// ```rust,ignore
    /// let patches = reconciler.diff();
    /// ```
    pub fn diff(&self) -> Vec<Patch> {
        let mut patches = Vec::new();

        // If there's no old tree, everything is new
        let old_tree = match &self.old_tree {
            Some(tree) => tree,
            None => {
                // Create patches for all new elements
                for (index, element) in self.new_tree.elements.iter().enumerate() {
                    patches.push(Patch::Create {
                        element: element.clone(),
                        parent: None,
                        position: index,
                    });
                }

                // Check for missing keys in new tree (development mode only)
                #[cfg(debug_assertions)]
                self.check_missing_keys(&self.new_tree);

                return patches;
            }
        };

        // Match elements between old and new trees
        let matches = self.match_elements(old_tree, &self.new_tree);

        // Generate patches based on matches
        for m in matches {
            match m {
                Match::Matched {
                    old_index,
                    new_index,
                    ..
                } => {
                    let old_elem = old_tree.get(old_index).unwrap();
                    let new_elem = self.new_tree.get(new_index).unwrap();

                    // Check if elements are different (need update)
                    if !self.elements_equal(old_elem, new_elem) {
                        patches.push(Patch::Update {
                            old_index,
                            element: new_elem.clone(),
                        });
                    }

                    // Check if position changed (need move)
                    if old_index != new_index {
                        patches.push(Patch::Move {
                            old_index,
                            new_position: new_index,
                        });
                    }
                }
                Match::New { new_index } => {
                    let new_elem = self.new_tree.get(new_index).unwrap();
                    patches.push(Patch::Create {
                        element: new_elem.clone(),
                        parent: None,
                        position: new_index,
                    });
                }
                Match::Removed { old_index, .. } => {
                    patches.push(Patch::Delete { old_index });
                }
            }
        }

        // Check for missing keys in new tree (development mode only)
        #[cfg(debug_assertions)]
        self.check_missing_keys(&self.new_tree);

        patches
    }

    /// Match elements between old and new trees.
    ///
    /// This implements the matching strategy:
    /// 1. Match by key (if both have keys)
    /// 2. Match by type + position (for elements without keys)
    ///
    /// # Arguments
    ///
    /// * `old_tree` - The old element tree
    /// * `new_tree` - The new element tree
    ///
    /// # Returns
    ///
    /// A vector of matches describing the correspondence between old and new elements.
    fn match_elements(&self, old_tree: &ElementTree, new_tree: &ElementTree) -> Vec<Match> {
        let mut matches = Vec::new();
        let mut old_matched = vec![false; old_tree.len()];
        let mut new_matched = vec![false; new_tree.len()];

        // Phase 1: Match by key
        for (new_index, new_elem) in new_tree.elements.iter().enumerate() {
            if let Some(key) = new_elem.key() {
                if let Some(&old_index) = old_tree.key_map.get(key) {
                    matches.push(Match::Matched {
                        old_index,
                        new_index,
                        fiber_id: None, // Fiber ID would be looked up during application
                    });
                    old_matched[old_index] = true;
                    new_matched[new_index] = true;
                }
            }
        }

        // Phase 2: Match by type + position for unmatched elements
        let mut old_pos = 0;
        for (new_index, item) in new_matched.iter_mut().enumerate().take(new_tree.len()) {
            if *item {
                continue; // Already matched by key
            }

            // Find next unmatched old element of same type
            while old_pos < old_tree.len() && old_matched[old_pos] {
                old_pos += 1;
            }

            if old_pos < old_tree.len() {
                let old_elem = old_tree.get(old_pos).unwrap();
                let new_elem = new_tree.get(new_index).unwrap();

                if self.same_type(old_elem, new_elem) {
                    matches.push(Match::Matched {
                        old_index: old_pos,
                        new_index,
                        fiber_id: None,
                    });
                    old_matched[old_pos] = true;
                    *item = true;
                    old_pos += 1;
                } else {
                    // Type mismatch - this is a new element
                    matches.push(Match::New { new_index });
                    *item = true;
                }
            } else {
                // No more old elements - this is new
                matches.push(Match::New { new_index });
                *item = true;
            }
        }

        // Phase 3: Mark remaining old elements as removed
        for (old_index, &matched) in old_matched.iter().enumerate() {
            if !matched {
                matches.push(Match::Removed {
                    old_index,
                    fiber_id: None,
                });
            }
        }

        matches
    }

    /// Check if two elements are of the same type.
    ///
    /// Elements are considered the same type if they are both:
    /// - Component elements
    /// - Widget elements
    /// - Text elements
    ///
    /// # Arguments
    ///
    /// * `a` - First element
    /// * `b` - Second element
    ///
    /// # Returns
    ///
    /// `true` if the elements are the same type, `false` otherwise.
    fn same_type(&self, a: &Element, b: &Element) -> bool {
        matches!(
            (a, b),
            (Element::Component { .. }, Element::Component { .. })
                | (Element::Widget { .. }, Element::Widget { .. })
                | (Element::Text(_), Element::Text(_))
        )
    }

    /// Check if two elements are equal (no update needed).
    ///
    /// For text elements, compares the text content.
    /// For other elements, assumes they need updating if types match.
    ///
    /// # Arguments
    ///
    /// * `a` - First element
    /// * `b` - Second element
    ///
    /// # Returns
    ///
    /// `true` if the elements are equal, `false` otherwise.
    fn elements_equal(&self, a: &Element, b: &Element) -> bool {
        match (a, b) {
            (Element::Text(a_text), Element::Text(b_text)) => a_text == b_text,
            // For components and widgets, we assume they need updating
            // A more sophisticated implementation could compare props
            _ => false,
        }
    }

    /// Check for missing keys in lists (development mode only).
    ///
    /// This method detects when multiple children of the same type lack keys,
    /// which can lead to incorrect reconciliation and state loss when lists are reordered.
    ///
    /// # Arguments
    ///
    /// * `tree` - The element tree to check
    #[cfg(debug_assertions)]
    fn check_missing_keys(&self, tree: &ElementTree) {
        use std::collections::HashMap;

        // Count elements by type (discriminant)
        let mut type_counts: HashMap<std::mem::Discriminant<Element>, usize> = HashMap::new();
        let mut unkeyed_by_type: HashMap<std::mem::Discriminant<Element>, Vec<usize>> =
            HashMap::new();

        for (index, element) in tree.elements.iter().enumerate() {
            let discriminant = std::mem::discriminant(element);
            *type_counts.entry(discriminant).or_insert(0) += 1;

            if element.key().is_none() {
                unkeyed_by_type.entry(discriminant).or_default().push(index);
            }
        }

        // Warn about types with multiple unkeyed elements
        for (_discriminant, unkeyed_indices) in unkeyed_by_type {
            if unkeyed_indices.len() > 1 {
                let type_name = match tree.elements.get(unkeyed_indices[0]) {
                    Some(Element::Text(_)) => "Text",
                    Some(Element::Widget { .. }) => "Widget",
                    Some(Element::Component { .. }) => "Component",
                    None => "Unknown",
                };

                tracing::warn!(
                    element_type = type_name,
                    count = unkeyed_indices.len(),
                    indices = ?unkeyed_indices,
                    "Multiple children of the same type lack keys. Consider adding unique keys to list items to preserve component state during reordering. \
                    Example: element.with_key(\"unique-id\")"
                );
            }
        }
    }

    /// Apply patches to the fiber tree.
    ///
    /// This method takes the generated patches and applies them to the fiber tree,
    /// creating, updating, deleting, and moving fibers as needed.
    ///
    /// # Current Implementation
    ///
    /// The current implementation provides basic patch application:
    /// - **Create patches**: Mount new fibers with the provided parent
    /// - **Update patches**: Mark fibers as dirty (requires fiber ID lookup)
    /// - **Delete patches**: Schedule fibers for unmount (requires fiber ID lookup)
    /// - **Move patches**: Update parent/child relationships (requires fiber ID lookup)
    ///
    /// # Limitations
    ///
    /// The reconciler generates patches with element indices, but applying them
    /// requires mapping indices to fiber IDs. In a full implementation, the caller
    /// would need to provide:
    /// - A mapping from old element indices to fiber IDs
    /// - A way to update the fiber tree's parent/child relationships
    ///
    /// For now, this method provides a basic implementation that works for Create
    /// patches. Update, Delete, and Move patches require additional context that
    /// would be provided by the runtime integration.
    ///
    /// # Arguments
    ///
    /// * `patches` - The patches to apply
    /// * `fiber_tree` - The fiber tree to modify
    ///
    /// # Example
    ///
    /// ```rust,ignore
    /// let patches = reconciler.diff();
    /// reconciler.apply(patches, &mut fiber_tree);
    /// ```
    pub fn apply(&self, patches: Vec<Patch>, fiber_tree: &mut FiberTree) {
        for patch in patches {
            match patch {
                Patch::Create {
                    element,
                    parent,
                    position,
                } => {
                    // Create a new fiber for this element
                    // The element's key (if any) is passed to the fiber
                    let key = element.key().map(|k| k.to_string());
                    let _fiber_id = fiber_tree.mount(parent, key);

                    // Note: Fibers created via mount() are not automatically marked as seen.
                    // In a full runtime integration, the reconciler would need access to
                    // a public API like mark_fiber_seen() to mark fibers as seen during render.
                    // For now, we just create the fiber.

                    // Position tracking would be handled by updating parent's children list
                    // This requires additional FiberTree API that doesn't exist yet
                    let _ = position;
                }
                Patch::Update { old_index, element } => {
                    // To apply an update, we need to:
                    // 1. Look up the fiber ID from old_index
                    // 2. Mark the fiber as dirty
                    // 3. Store the new element for re-rendering
                    //
                    // This requires a mapping from indices to fiber IDs that
                    // would be provided by the caller in a full implementation.
                    let _ = (old_index, element);
                }
                Patch::Delete { old_index } => {
                    // To apply a delete, we need to:
                    // 1. Look up the fiber ID from old_index
                    // 2. Schedule the fiber for unmount
                    //
                    // This requires a mapping from indices to fiber IDs.
                    let _ = old_index;
                }
                Patch::Move {
                    old_index,
                    new_position,
                } => {
                    // To apply a move, we need to:
                    // 1. Look up the fiber ID from old_index
                    // 2. Update the fiber's position in parent's children list
                    // 3. Update parent/child relationships if parent changed
                    //
                    // This requires both a mapping and additional FiberTree API.
                    let _ = (old_index, new_position);
                }
            }
        }
    }
}

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

    #[test]
    fn test_element_tree_creation() {
        let elements = vec![Element::text("Hello"), Element::text("World")];
        let tree = ElementTree::from_elements(elements);

        assert_eq!(tree.len(), 2);
        assert!(!tree.is_empty());
    }

    #[test]
    fn test_element_tree_empty() {
        let tree = ElementTree::empty();

        assert_eq!(tree.len(), 0);
        assert!(tree.is_empty());
    }

    #[test]
    fn test_element_tree_get() {
        let elements = vec![Element::text("Hello"), Element::text("World")];
        let tree = ElementTree::from_elements(elements);

        assert!(tree.get(0).is_some());
        assert!(tree.get(1).is_some());
        assert!(tree.get(2).is_none());
    }

    #[test]
    fn test_reconciler_no_old_tree() {
        let new_tree =
            ElementTree::from_elements(vec![Element::text("Hello"), Element::text("World")]);

        let reconciler = Reconciler::new(None, new_tree);
        let patches = reconciler.diff();

        // Should create patches for all new elements
        assert_eq!(patches.len(), 2);
        assert!(matches!(patches[0], Patch::Create { .. }));
        assert!(matches!(patches[1], Patch::Create { .. }));
    }

    #[test]
    fn test_reconciler_same_trees() {
        let elements = vec![Element::text("Hello"), Element::text("World")];
        let old_tree = ElementTree::from_elements(elements.clone());
        let new_tree = ElementTree::from_elements(elements);

        let reconciler = Reconciler::new(Some(old_tree), new_tree);
        let patches = reconciler.diff();

        // Text elements with same content should not generate patches
        // (they match and are equal)
        assert_eq!(patches.len(), 0);
    }

    #[test]
    fn test_reconciler_text_change() {
        let old_tree = ElementTree::from_elements(vec![Element::text("Hello")]);
        let new_tree = ElementTree::from_elements(vec![Element::text("World")]);

        let reconciler = Reconciler::new(Some(old_tree), new_tree);
        let patches = reconciler.diff();

        // Should generate an update patch for changed text
        assert_eq!(patches.len(), 1);
        assert!(matches!(patches[0], Patch::Update { .. }));
    }

    #[test]
    fn test_reconciler_element_added() {
        let old_tree = ElementTree::from_elements(vec![Element::text("Hello")]);
        let new_tree =
            ElementTree::from_elements(vec![Element::text("Hello"), Element::text("World")]);

        let reconciler = Reconciler::new(Some(old_tree), new_tree);
        let patches = reconciler.diff();

        // Should generate a create patch for the new element
        assert_eq!(patches.len(), 1);
        assert!(matches!(patches[0], Patch::Create { .. }));
    }

    #[test]
    fn test_reconciler_element_removed() {
        let old_tree =
            ElementTree::from_elements(vec![Element::text("Hello"), Element::text("World")]);
        let new_tree = ElementTree::from_elements(vec![Element::text("Hello")]);

        let reconciler = Reconciler::new(Some(old_tree), new_tree);
        let patches = reconciler.diff();

        // Should generate a delete patch for the removed element
        assert_eq!(patches.len(), 1);
        assert!(matches!(patches[0], Patch::Delete { .. }));
    }

    #[test]
    fn test_same_type_text() {
        let reconciler = Reconciler::new(None, ElementTree::empty());
        let a = Element::text("Hello");
        let b = Element::text("World");

        assert!(reconciler.same_type(&a, &b));
    }

    #[test]
    fn test_elements_equal_text() {
        let reconciler = Reconciler::new(None, ElementTree::empty());
        let a = Element::text("Hello");
        let b = Element::text("Hello");
        let c = Element::text("World");

        assert!(reconciler.elements_equal(&a, &b));
        assert!(!reconciler.elements_equal(&a, &c));
    }

    #[test]
    fn test_key_based_matching_preserves_identity() {
        use ratatui::widgets::Paragraph;

        // Create elements with keys
        let old_tree = ElementTree::from_elements(vec![
            Element::widget(Paragraph::new("First")).with_key("item-1"),
            Element::widget(Paragraph::new("Second")).with_key("item-2"),
            Element::widget(Paragraph::new("Third")).with_key("item-3"),
        ]);

        // Reorder elements but keep same keys
        let new_tree = ElementTree::from_elements(vec![
            Element::widget(Paragraph::new("Third")).with_key("item-3"),
            Element::widget(Paragraph::new("First")).with_key("item-1"),
            Element::widget(Paragraph::new("Second")).with_key("item-2"),
        ]);

        let reconciler = Reconciler::new(Some(old_tree), new_tree);
        let patches = reconciler.diff();

        // Should generate update patches (content changed) and move patches (position changed)
        // Elements matched by key should be recognized as the same
        let update_count = patches
            .iter()
            .filter(|p| matches!(p, Patch::Update { .. }))
            .count();
        let move_count = patches
            .iter()
            .filter(|p| matches!(p, Patch::Move { .. }))
            .count();

        // All 3 elements changed position, so 3 move patches
        assert_eq!(
            move_count, 3,
            "Should have 3 move patches for reordered elements"
        );
        // Widget elements always generate updates (we don't compare widget content)
        assert_eq!(
            update_count, 3,
            "Should have 3 update patches for widget content"
        );
    }

    #[test]
    fn test_key_based_matching_with_additions() {
        use ratatui::widgets::Paragraph;

        let old_tree = ElementTree::from_elements(vec![
            Element::widget(Paragraph::new("First")).with_key("item-1"),
            Element::widget(Paragraph::new("Second")).with_key("item-2"),
        ]);

        let new_tree = ElementTree::from_elements(vec![
            Element::widget(Paragraph::new("First")).with_key("item-1"),
            Element::widget(Paragraph::new("New")).with_key("item-3"),
            Element::widget(Paragraph::new("Second")).with_key("item-2"),
        ]);

        let reconciler = Reconciler::new(Some(old_tree), new_tree);
        let patches = reconciler.diff();

        // Should have 1 create patch for the new element and 1 move patch for item-2
        let create_count = patches
            .iter()
            .filter(|p| matches!(p, Patch::Create { .. }))
            .count();
        let move_count = patches
            .iter()
            .filter(|p| matches!(p, Patch::Move { .. }))
            .count();

        assert_eq!(create_count, 1, "Should have 1 create patch");
        assert_eq!(move_count, 1, "Should have 1 move patch for item-2");
    }

    #[test]
    fn test_key_based_matching_with_removals() {
        use ratatui::widgets::Paragraph;

        let old_tree = ElementTree::from_elements(vec![
            Element::widget(Paragraph::new("First")).with_key("item-1"),
            Element::widget(Paragraph::new("Second")).with_key("item-2"),
            Element::widget(Paragraph::new("Third")).with_key("item-3"),
        ]);

        let new_tree = ElementTree::from_elements(vec![
            Element::widget(Paragraph::new("First")).with_key("item-1"),
            Element::widget(Paragraph::new("Third")).with_key("item-3"),
        ]);

        let reconciler = Reconciler::new(Some(old_tree), new_tree);
        let patches = reconciler.diff();

        // Should have 1 delete patch for item-2 and 1 move patch for item-3
        let delete_count = patches
            .iter()
            .filter(|p| matches!(p, Patch::Delete { .. }))
            .count();
        let move_count = patches
            .iter()
            .filter(|p| matches!(p, Patch::Move { .. }))
            .count();

        assert_eq!(delete_count, 1, "Should have 1 delete patch");
        assert_eq!(move_count, 1, "Should have 1 move patch for item-3");
    }

    #[test]
    fn test_key_based_matching_mixed_with_position() {
        use ratatui::widgets::Paragraph;

        // Mix of keyed and non-keyed elements
        let old_tree = ElementTree::from_elements(vec![
            Element::widget(Paragraph::new("Keyed")).with_key("item-1"),
            Element::text("Unkeyed"),
        ]);

        let new_tree = ElementTree::from_elements(vec![
            Element::text("Unkeyed"),
            Element::widget(Paragraph::new("Keyed")).with_key("item-1"),
        ]);

        let reconciler = Reconciler::new(Some(old_tree), new_tree);
        let patches = reconciler.diff();

        // Keyed element should be matched by key (moved)
        // Unkeyed element should be matched by type+position
        assert!(
            patches.iter().any(|p| matches!(p, Patch::Move { .. })),
            "Should have move patch for keyed element"
        );
    }

    #[test]
    fn test_element_tree_key_map() {
        use ratatui::widgets::Paragraph;

        let tree = ElementTree::from_elements(vec![
            Element::text("No key"),
            Element::widget(Paragraph::new("Has key")).with_key("my-key"),
            Element::text("Also no key"),
        ]);

        assert_eq!(tree.key_map.len(), 1, "Should have 1 key in map");
        assert!(
            tree.key_map.contains_key("my-key"),
            "Should contain 'my-key'"
        );
        assert_eq!(
            tree.key_map.get("my-key"),
            Some(&1),
            "Key should map to index 1"
        );
    }

    #[test]
    fn test_element_tree_get_by_key() {
        use ratatui::widgets::Paragraph;

        let tree = ElementTree::from_elements(vec![
            Element::text("First"),
            Element::widget(Paragraph::new("Second")).with_key("item-2"),
            Element::text("Third"),
        ]);

        let elem = tree.get_by_key("item-2");
        assert!(elem.is_some(), "Should find element by key");
        assert_eq!(elem.unwrap().key(), Some("item-2"));

        let missing = tree.get_by_key("nonexistent");
        assert!(missing.is_none(), "Should return None for missing key");
    }

    #[test]
    fn test_complex_diff_scenario() {
        use ratatui::widgets::Paragraph;

        // Complex scenario: mix of additions, removals, moves, and updates
        let old_tree = ElementTree::from_elements(vec![
            Element::widget(Paragraph::new("A")).with_key("a"),
            Element::widget(Paragraph::new("B")).with_key("b"),
            Element::text("Unkeyed 1"),
            Element::widget(Paragraph::new("C")).with_key("c"),
            Element::text("Unkeyed 2"),
        ]);

        let new_tree = ElementTree::from_elements(vec![
            Element::widget(Paragraph::new("C")).with_key("c"), // Moved from position 3 to 0
            Element::text("Unkeyed 1"),                         // Stayed at relative position
            Element::widget(Paragraph::new("D")).with_key("d"), // New element
            Element::widget(Paragraph::new("A")).with_key("a"), // Moved from position 0 to 3
                                                                // "B" removed
                                                                // "Unkeyed 2" removed
        ]);

        let reconciler = Reconciler::new(Some(old_tree), new_tree);
        let patches = reconciler.diff();

        // Verify we have the right mix of patches
        let create_count = patches
            .iter()
            .filter(|p| matches!(p, Patch::Create { .. }))
            .count();
        let _update_count = patches
            .iter()
            .filter(|p| matches!(p, Patch::Update { .. }))
            .count();
        let delete_count = patches
            .iter()
            .filter(|p| matches!(p, Patch::Delete { .. }))
            .count();
        let move_count = patches
            .iter()
            .filter(|p| matches!(p, Patch::Move { .. }))
            .count();

        assert_eq!(create_count, 1, "Should create 1 new element (D)");
        assert_eq!(delete_count, 2, "Should delete 2 elements (B, Unkeyed 2)");
        assert!(move_count >= 2, "Should move at least 2 elements (C, A)");
        // Widget elements always generate updates (we don't compare widget content deeply)
    }

    #[test]
    fn test_diff_all_elements_replaced() {
        use ratatui::widgets::Paragraph;

        let old_tree = ElementTree::from_elements(vec![
            Element::widget(Paragraph::new("Old 1")),
            Element::widget(Paragraph::new("Old 2")),
        ]);

        let new_tree =
            ElementTree::from_elements(vec![Element::text("New 1"), Element::text("New 2")]);

        let reconciler = Reconciler::new(Some(old_tree), new_tree);
        let patches = reconciler.diff();

        // Different types, so should be delete + create
        let create_count = patches
            .iter()
            .filter(|p| matches!(p, Patch::Create { .. }))
            .count();
        let delete_count = patches
            .iter()
            .filter(|p| matches!(p, Patch::Delete { .. }))
            .count();

        assert_eq!(create_count, 2, "Should create 2 new elements");
        assert_eq!(delete_count, 2, "Should delete 2 old elements");
    }

    #[test]
    fn test_diff_empty_to_populated() {
        use ratatui::widgets::Paragraph;

        let old_tree = ElementTree::empty();
        let new_tree = ElementTree::from_elements(vec![
            Element::text("First"),
            Element::widget(Paragraph::new("Second")),
        ]);

        let reconciler = Reconciler::new(Some(old_tree), new_tree);
        let patches = reconciler.diff();

        assert_eq!(patches.len(), 2, "Should create 2 elements");
        assert!(
            patches.iter().all(|p| matches!(p, Patch::Create { .. })),
            "All patches should be Create"
        );
    }

    #[test]
    fn test_diff_populated_to_empty() {
        use ratatui::widgets::Paragraph;

        let old_tree = ElementTree::from_elements(vec![
            Element::text("First"),
            Element::widget(Paragraph::new("Second")),
        ]);
        let new_tree = ElementTree::empty();

        let reconciler = Reconciler::new(Some(old_tree), new_tree);
        let patches = reconciler.diff();

        assert_eq!(patches.len(), 2, "Should delete 2 elements");
        assert!(
            patches.iter().all(|p| matches!(p, Patch::Delete { .. })),
            "All patches should be Delete"
        );
    }

    #[test]
    fn test_diff_maintains_patch_order() {
        use ratatui::widgets::Paragraph;

        // Ensure patches are generated in a consistent order
        let old_tree = ElementTree::from_elements(vec![
            Element::widget(Paragraph::new("A")).with_key("a"),
            Element::widget(Paragraph::new("B")).with_key("b"),
        ]);

        let new_tree = ElementTree::from_elements(vec![
            Element::widget(Paragraph::new("B")).with_key("b"),
            Element::widget(Paragraph::new("A")).with_key("a"),
        ]);

        let reconciler = Reconciler::new(Some(old_tree), new_tree);
        let patches = reconciler.diff();

        // Patches should be generated in a predictable order
        // (implementation detail, but useful for debugging)
        assert!(
            !patches.is_empty(),
            "Should generate patches for reordering"
        );
    }

    #[test]
    fn test_apply_create_patches() {
        use crate::fiber_tree::FiberTree;

        let new_tree =
            ElementTree::from_elements(vec![Element::text("First"), Element::text("Second")]);

        let reconciler = Reconciler::new(None, new_tree);
        let patches = reconciler.diff();

        let mut fiber_tree = FiberTree::new();
        let initial_fiber_count = fiber_tree.fibers.len();

        reconciler.apply(patches, &mut fiber_tree);

        // Should have created 2 new fibers
        assert_eq!(
            fiber_tree.fibers.len(),
            initial_fiber_count + 2,
            "Should create 2 fibers"
        );
    }

    #[test]
    fn test_apply_create_patches_with_keys() {
        use crate::fiber_tree::FiberTree;
        use ratatui::widgets::Paragraph;

        let new_tree = ElementTree::from_elements(vec![
            Element::widget(Paragraph::new("A")).with_key("item-a"),
            Element::widget(Paragraph::new("B")).with_key("item-b"),
        ]);

        let reconciler = Reconciler::new(None, new_tree);
        let patches = reconciler.diff();

        let mut fiber_tree = FiberTree::new();
        reconciler.apply(patches, &mut fiber_tree);

        // Should have created 2 fibers with keys
        assert_eq!(fiber_tree.fibers.len(), 2, "Should create 2 fibers");

        // Verify fibers have keys
        let fibers_with_keys = fiber_tree
            .fibers
            .values()
            .filter(|f| f.key.is_some())
            .count();
        assert_eq!(fibers_with_keys, 2, "Both fibers should have keys");
    }

    #[test]
    fn test_apply_empty_patches() {
        use crate::fiber_tree::FiberTree;

        let old_tree = ElementTree::from_elements(vec![Element::text("Same")]);
        let new_tree = ElementTree::from_elements(vec![Element::text("Same")]);

        let reconciler = Reconciler::new(Some(old_tree), new_tree);
        let patches = reconciler.diff();

        let mut fiber_tree = FiberTree::new();
        let initial_fiber_count = fiber_tree.fibers.len();

        reconciler.apply(patches, &mut fiber_tree);

        // No patches, so no changes
        assert_eq!(
            fiber_tree.fibers.len(),
            initial_fiber_count,
            "Should not create any fibers"
        );
    }
}

#[cfg(test)]
mod property_tests {
    use super::*;
    use crate::fiber_tree::FiberTree;
    use proptest::prelude::*;

    /// Generate arbitrary elements for property testing
    fn arb_element() -> impl Strategy<Value = Element> {
        any::<String>().prop_map(Element::text)
    }

    /// Generate arbitrary element trees
    fn arb_element_tree() -> impl Strategy<Value = ElementTree> {
        prop::collection::vec(arb_element(), 0..10).prop_map(ElementTree::from_elements)
    }

    proptest! {
        #![proptest_config(ProptestConfig::with_cases(100))]

        /// **Property 2: Render Stack Integrity**
        /// **Validates: Requirements 2.4, 2.5**
        ///
        /// For any sequence of begin_render/end_render calls, the render stack SHALL
        /// maintain LIFO ordering, and current_fiber() SHALL return the most recently
        /// begun fiber.
        #[test]
        fn prop_render_stack_integrity(
            num_fibers in 1usize..20,
            operations in prop::collection::vec(prop::bool::ANY, 1..100)
        ) {
            let mut fiber_tree = FiberTree::new();
            let mut expected_stack: Vec<crate::fiber::FiberId> = Vec::new();

            // Create fibers
            let fiber_ids: Vec<_> = (0..num_fibers)
                .map(|_| fiber_tree.mount(None, None))
                .collect();

            // Simulate begin_render/end_render operations
            for &should_begin in &operations {
                if should_begin && !fiber_ids.is_empty() {
                    // Begin render on a random fiber
                    let fiber_id = fiber_ids[expected_stack.len() % fiber_ids.len()];
                    fiber_tree.begin_render(fiber_id);
                    expected_stack.push(fiber_id);

                    // Property: current_fiber() returns the most recently begun fiber
                    prop_assert_eq!(
                        fiber_tree.current_fiber(),
                        Some(fiber_id),
                        "current_fiber should return the most recently begun fiber"
                    );
                } else if !expected_stack.is_empty() {
                    // End render
                    expected_stack.pop();
                    fiber_tree.end_render();

                    // Property: current_fiber() returns the previous fiber (or None)
                    prop_assert_eq!(
                        fiber_tree.current_fiber(),
                        expected_stack.last().copied(),
                        "current_fiber should return the previous fiber after end_render"
                    );
                }
            }

            // Clean up remaining renders
            while !expected_stack.is_empty() {
                expected_stack.pop();
                fiber_tree.end_render();
            }

            // Property: Stack is empty after all end_render calls
            prop_assert!(
                fiber_tree.current_fiber().is_none(),
                "current_fiber should be None after all renders complete"
            );
        }

        /// **Property 3: Unseen Fiber Unmount Scheduling**
        /// **Validates: Requirement 2.6**
        ///
        /// For any fiber that was rendered in a previous frame but not in the current
        /// frame, the fiber SHALL be scheduled for unmount after mark_unseen_for_unmount()
        /// is called.
        #[test]
        fn prop_unseen_fiber_unmount_scheduling(
            initial_component_ids in prop::collection::vec(1u64..10000, 1..20),
            surviving_component_ids in prop::collection::vec(1u64..10000, 0..10)
        ) {
            let mut fiber_tree = FiberTree::new();

            // First render: Create fibers for all initial component IDs
            // Note: Duplicate component IDs will map to the same fiber
            let mut fiber_map = std::collections::HashMap::new();
            for &component_id in &initial_component_ids {
                let fiber_id = fiber_tree.get_or_create_fiber_by_component_id(component_id);
                fiber_map.insert(component_id, fiber_id);
            }
            fiber_tree.mark_unseen_for_unmount();

            // Property: No fibers should be scheduled for unmount after first render
            prop_assert_eq!(
                fiber_tree.pending_unmount_count(),
                0,
                "No fibers should be scheduled for unmount after first render"
            );

            // Second render: Only render surviving component IDs
            for &component_id in &surviving_component_ids {
                fiber_tree.get_or_create_fiber_by_component_id(component_id);
            }
            fiber_tree.mark_unseen_for_unmount();

            // Property: Fibers not in surviving_ids should be scheduled for unmount
            for (&component_id, &fiber_id) in &fiber_map {
                let should_survive = surviving_component_ids.contains(&component_id);
                let is_pending_unmount = fiber_tree.pending_unmount.contains(&fiber_id);

                if !should_survive {
                    prop_assert!(
                        is_pending_unmount,
                        "Fiber for component {} should be scheduled for unmount", component_id
                    );
                } else {
                    prop_assert!(
                        !is_pending_unmount,
                        "Fiber for component {} should NOT be scheduled for unmount", component_id
                    );
                }
            }

            // Property: Unmount count matches expected (based on unique component IDs)
            // fiber_map contains unique component IDs, so we count based on that
            let expected_unmount_count = fiber_map
                .keys()
                .filter(|id| !surviving_component_ids.contains(id))
                .count();
            prop_assert_eq!(
                fiber_tree.pending_unmount_count(),
                expected_unmount_count,
                "Unmount count should match number of unique unseen fibers"
            );
        }

        /// **Property: Reconciliation Produces Valid Patches**
        ///
        /// For any old and new element trees, the reconciler SHALL produce patches
        /// that can be applied without panicking.
        #[test]
        fn prop_reconciliation_produces_valid_patches(
            old_tree in prop::option::of(arb_element_tree()),
            new_tree in arb_element_tree()
        ) {
            let reconciler = Reconciler::new(old_tree, new_tree);
            let patches = reconciler.diff();

            // Property: Patches can be applied without panicking
            let mut fiber_tree = FiberTree::new();
            reconciler.apply(patches, &mut fiber_tree);

            // If we got here without panicking, the property holds
            prop_assert!(true);
        }

        /// **Property: Key-Based Matching Preserves Identity**
        ///
        /// For any element with a key, if the key appears in both old and new trees,
        /// the reconciler SHALL match them together (not create a Delete + Create).
        #[test]
        fn prop_key_based_matching_preserves_identity(
            keys in prop::collection::vec("[a-z]{1,5}", 1..10),
            shuffle_indices in prop::collection::vec(0usize..10, 1..10)
        ) {
            // Create old tree with keyed elements
            let old_elements: Vec<Element> = keys
                .iter()
                .map(|k| Element::text("text").with_key(k))
                .collect();
            let old_tree = ElementTree::from_elements(old_elements.clone());

            // Create new tree with same keys but potentially reordered
            let mut new_elements = old_elements.clone();
            for (i, &shuffle_idx) in shuffle_indices.iter().enumerate() {
                if i < new_elements.len() && shuffle_idx < new_elements.len() {
                    new_elements.swap(i, shuffle_idx);
                }
            }
            let new_tree = ElementTree::from_elements(new_elements);

            let reconciler = Reconciler::new(Some(old_tree), new_tree);
            let patches = reconciler.diff();

            // Property: No Delete patches for elements that still exist with same key
            let delete_count = patches.iter().filter(|p| matches!(p, Patch::Delete { .. })).count();
            prop_assert_eq!(
                delete_count,
                0,
                "Should not delete elements that still exist with same key"
            );

            // Property: No Create patches for elements that already existed with same key
            let create_count = patches.iter().filter(|p| matches!(p, Patch::Create { .. })).count();
            prop_assert_eq!(
                create_count,
                0,
                "Should not create elements that already existed with same key"
            );
        }

        /// **Property: Reconciliation is Deterministic**
        ///
        /// For any old and new element trees, running diff() multiple times SHALL
        /// produce the same patches.
        #[test]
        fn prop_reconciliation_is_deterministic(
            old_tree in prop::option::of(arb_element_tree()),
            new_tree in arb_element_tree()
        ) {
            let reconciler1 = Reconciler::new(old_tree.clone(), new_tree.clone());
            let patches1 = reconciler1.diff();

            let reconciler2 = Reconciler::new(old_tree, new_tree);
            let patches2 = reconciler2.diff();

            // Property: Same input produces same output
            prop_assert_eq!(
                patches1.len(),
                patches2.len(),
                "Should produce same number of patches"
            );

            for (p1, p2) in patches1.iter().zip(patches2.iter()) {
                prop_assert_eq!(
                    std::mem::discriminant(p1),
                    std::mem::discriminant(p2),
                    "Patches should have same variant"
                );
            }
        }
    }
}