hypen_engine/reconcile/

diff.rs

use super::{InstanceTree, Patch, ControlFlowKind};
use crate::ir::{Element, NodeId, Value, IRNode, ConditionalBranch, Props};
use crate::reactive::{DependencyGraph, evaluate_template_string, Binding};
use indexmap::IndexMap;

/// Reconcile an element tree against the instance tree and generate patches
pub fn reconcile(
    tree: &mut InstanceTree,
    element: &Element,
    parent_id: Option<NodeId>,
    state: &serde_json::Value,
    dependencies: &mut DependencyGraph,
) -> Vec<Patch> {
    let mut patches = Vec::new();

    // For initial render, just create the tree
    if tree.root().is_none() {
        let node_id = create_tree(tree, element, parent_id, state, &mut patches, true, dependencies);
        tree.set_root(node_id);
        return patches;
    }

    // Incremental update: reconcile root against existing tree
    if let Some(root_id) = tree.root() {
        reconcile_node(tree, root_id, element, state, &mut patches, dependencies);
    }

    patches
}

/// Reconcile an IRNode tree against the instance tree and generate patches
/// This is the primary entry point for the IRNode-based reconciliation system,
/// which supports first-class ForEach, When/If, and custom item variable names.
pub fn reconcile_ir(
    tree: &mut InstanceTree,
    node: &IRNode,
    parent_id: Option<NodeId>,
    state: &serde_json::Value,
    dependencies: &mut DependencyGraph,
) -> Vec<Patch> {
    let mut patches = Vec::new();

    // For initial render, create the tree
    if tree.root().is_none() {
        let node_id = create_ir_node_tree(tree, node, parent_id, state, &mut patches, true, dependencies);
        tree.set_root(node_id);
        return patches;
    }

    // Incremental update: reconcile root against existing tree
    if let Some(root_id) = tree.root() {
        reconcile_ir_node(tree, root_id, node, state, &mut patches, dependencies);
    }

    patches
}

/// Create a new subtree from an element
pub fn create_tree(
    tree: &mut InstanceTree,
    element: &Element,
    parent_id: Option<NodeId>,
    state: &serde_json::Value,
    patches: &mut Vec<Patch>,
    is_root: bool,
    dependencies: &mut DependencyGraph,
) -> NodeId {
    // Special handling for iterable elements (List, Grid, etc.)
    // An element is iterable if it has BOTH:
    // 1. prop "0" with a Binding (like @state.items) - not a static value
    // 2. children (the template to repeat for each item)
    // This distinguishes iterables from:
    // - Text elements (prop "0" but no children)
    // - Route/Link elements (prop "0" with static path, not a binding)
    if let Some(Value::Binding(_)) = element.props.get("0") {
        if !element.children.is_empty() {
            return create_list_tree(tree, element, parent_id, state, patches, is_root, dependencies);
        }
    }

    // Create the node
    let node_id = tree.create_node(element, state);

    // Register dependencies for this node
    for value in element.props.values() {
        match value {
            Value::Binding(binding) => {
                dependencies.add_dependency(node_id, binding);
            }
            Value::TemplateString { bindings, .. } => {
                // Register all bindings in the template string
                for binding in bindings {
                    dependencies.add_dependency(node_id, binding);
                }
            }
            _ => {}
        }
    }

    // Generate Create patch
    let node = tree.get(node_id).unwrap();
    
    // For lazy elements, add child component name as a prop
    let mut props = node.props.clone();
    if let Some(Value::Static(val)) = element.props.get("__lazy") {
        if val.as_bool().unwrap_or(false) && !element.children.is_empty() {
            // Store the first child's element type so renderer knows what component to load
            let child_component = &element.children[0].element_type;
            props.insert("__lazy_child".to_string(), serde_json::json!(child_component));
        }
    }
    
    patches.push(Patch::create(
        node_id,
        node.element_type.clone(),
        props,
    ));

    // Event handling is now done at the renderer level

    // If there's a parent, insert this node
    if let Some(parent) = parent_id {
        tree.add_child(parent, node_id, None);
        patches.push(Patch::insert(parent, node_id, None));
    } else if is_root {
        // This is the root node - insert into "root" container
        patches.push(Patch::insert_root(node_id));
    }

    // Create children (skip if element is marked as lazy)
    let is_lazy = element.props.get("__lazy")
        .and_then(|v| {
            if let Value::Static(val) = v {
                val.as_bool()
            } else {
                None
            }
        })
        .unwrap_or(false);
    
    if !is_lazy {
        for child_element in &element.children {
            create_tree(tree, child_element, Some(node_id), state, patches, false, dependencies);
        }
    }

    node_id
}

/// Create an iterable element (List, Grid, etc.) that iterates over an array in state
/// Iterable elements are identified by having prop "0" with an array binding
fn create_list_tree(
    tree: &mut InstanceTree,
    element: &Element,
    parent_id: Option<NodeId>,
    state: &serde_json::Value,
    patches: &mut Vec<Patch>,
    is_root: bool,
    dependencies: &mut DependencyGraph,
) -> NodeId {
    // Get the array binding from first prop (prop "0")
    let array = if let Some(Value::Binding(binding)) = element.props.get("0") {
        evaluate_binding(binding, state).unwrap_or(serde_json::Value::Array(vec![]))
    } else {
        serde_json::Value::Array(vec![])
    };

    // Create a container element - use the original element type (List, Grid, etc.)
    // but remove the "0" prop since it's only for iteration, not rendering
    let mut list_element = Element::new(&element.element_type);
    for (key, value) in &element.props {
        // Skip prop "0" - it's only for array binding, not for rendering
        if key != "0" {
            list_element.props.insert(key.clone(), value.clone());
        }
    }
    
    let node_id = tree.create_node(&list_element, state);

    // Register the List node as depending on the array binding
    // This is critical for reactive updates when the array changes
    if let Some(Value::Binding(binding)) = element.props.get("0") {
        dependencies.add_dependency(node_id, binding);
    }

    // Store the original element template for re-reconciliation
    // This allows us to rebuild the list when the array changes
    if let Some(node) = tree.get_mut(node_id) {
        node.raw_props = element.props.clone();
        node.element_template = Some(std::sync::Arc::new(element.clone()));
    }

    // Generate Create patch for container
    let node = tree.get(node_id).unwrap();
    patches.push(Patch::create(
        node_id,
        node.element_type.clone(),
        node.props.clone(),
    ));

    // Insert container
    if let Some(parent) = parent_id {
        tree.add_child(parent, node_id, None);
        patches.push(Patch::insert(parent, node_id, None));
    } else if is_root {
        patches.push(Patch::insert_root(node_id));
    }

    // If array is empty, return early
    if let serde_json::Value::Array(items) = &array {
        // Create children for each item in the array
        for (index, item) in items.iter().enumerate() {
            for child_template in &element.children {
                // Clone child and replace ${item.x} bindings with actual item data
                let child_with_item = replace_item_bindings(child_template, item, index);
                create_tree(tree, &child_with_item, Some(node_id), state, patches, false, dependencies);
            }
        }
    }

    node_id
}

/// Navigate a nested path in a JSON value (e.g., "images.0" or "category.name")
/// Supports both object keys and array indices
fn navigate_item_path<'a>(item: &'a serde_json::Value, path: &str) -> Option<&'a serde_json::Value> {
    let mut current = item;

    for segment in path.split('.') {
        // Try to parse as array index first
        if let Ok(index) = segment.parse::<usize>() {
            current = current.get(index)?;
        } else {
            // Otherwise treat as object key
            current = current.get(segment)?;
        }
    }

    Some(current)
}

/// A replacement to be applied: (start_index, end_index, replacement_string)
/// Using a struct for clarity
#[derive(Debug)]
struct Replacement {
    start: usize,
    end: usize,
    text: String,
}

/// Apply all collected replacements to a string in a single pass.
/// Builds result by copying segments between replacements - true O(n + m) complexity.
fn apply_replacements(s: &str, mut replacements: Vec<Replacement>) -> String {
    if replacements.is_empty() {
        return s.to_string();
    }

    // Sort by start position ascending
    replacements.sort_by(|a, b| a.start.cmp(&b.start));

    // Filter invalid replacements and calculate result size
    let valid_replacements: Vec<_> = replacements
        .into_iter()
        .filter(|r| r.start <= s.len() && r.end <= s.len() && r.start <= r.end)
        .collect();

    if valid_replacements.is_empty() {
        return s.to_string();
    }

    // Calculate total size: original - removed + added
    let removed: usize = valid_replacements.iter().map(|r| r.end - r.start).sum();
    let added: usize = valid_replacements.iter().map(|r| r.text.len()).sum();
    let capacity = s.len() - removed + added;

    let mut result = String::with_capacity(capacity);
    let mut pos = 0;

    for r in valid_replacements {
        // Push the segment before this replacement
        if r.start > pos {
            result.push_str(&s[pos..r.start]);
        }
        // Push the replacement text
        result.push_str(&r.text);
        pos = r.end;
    }

    // Push remaining segment after last replacement
    if pos < s.len() {
        result.push_str(&s[pos..]);
    }

    result
}

/// Find the end of a path (valid identifier chars: alphanumeric, _, and . for nesting)
fn find_path_end(s: &str, start: usize) -> usize {
    let chars: Vec<char> = s[start..].chars().collect();
    let mut end = start;

    for (i, ch) in chars.iter().enumerate() {
        if ch.is_alphanumeric() || *ch == '_' {
            end = start + i + 1;
        } else if *ch == '.' {
            // Dot is valid only if followed by alphanumeric or underscore
            if i + 1 < chars.len() {
                let next = chars[i + 1];
                if next.is_alphanumeric() || next == '_' {
                    end = start + i + 1;
                    continue;
                }
            }
            break;
        } else {
            break;
        }
    }

    end
}

/// Format a JSON value for replacement in expressions
fn format_value_for_replacement(val: &serde_json::Value, quote_strings: bool) -> String {
    match val {
        serde_json::Value::String(s) => {
            if quote_strings {
                format!("'{}'", s)
            } else {
                s.clone()
            }
        }
        serde_json::Value::Number(n) => n.to_string(),
        serde_json::Value::Bool(b) => b.to_string(),
        serde_json::Value::Null => "null".to_string(),
        _ => serde_json::to_string(val).unwrap_or_default(),
    }
}

/// Replace item bindings (Value::Binding with is_item() or TemplateString with item bindings) with actual item values
/// OPTIMIZED: Uses single-pass replacement instead of O(n²) repeated scans
/// This is a convenience wrapper that uses "item" as the default item name.
pub fn replace_item_bindings(element: &Element, item: &serde_json::Value, index: usize) -> Element {
    replace_item_bindings_with_name(element, item, index, "item")
}

/// Reconcile a single node with a new element
pub fn reconcile_node(
    tree: &mut InstanceTree,
    node_id: NodeId,
    element: &Element,
    state: &serde_json::Value,
    patches: &mut Vec<Patch>,
    dependencies: &mut DependencyGraph,
) {
    let node = tree.get(node_id).cloned();
    if node.is_none() {
        return;
    }
    let node = node.unwrap();

    // Special handling for iterable elements (List, Grid, etc.)
    // An element is iterable if it has BOTH prop "0" (array binding) AND children (template)
    // This distinguishes iterables from Text elements, which also use prop "0" but have no children
    let is_iterable = element.props.get("0").is_some() && !element.children.is_empty();
    
    if is_iterable {
        // Get the array binding from first prop (prop "0")
        let array = if let Some(Value::Binding(binding)) = element.props.get("0") {
            evaluate_binding(binding, state).unwrap_or(serde_json::Value::Array(vec![]))
        } else {
            serde_json::Value::Array(vec![])
        };

        // Regenerate iterable children
        if let serde_json::Value::Array(items) = &array {
            let old_children = node.children.clone();
            
            // Calculate expected number of children
            let expected_children_count = items.len() * element.children.len();
            
            // Remove old children if count doesn't match
            if old_children.len() != expected_children_count {
                for &old_child_id in &old_children {
                    patches.push(Patch::remove(old_child_id));
                }
                
                // Clear children from node
                if let Some(node) = tree.get_mut(node_id) {
                    node.children.clear();
                }
                
                // Create new children
                for (index, item) in items.iter().enumerate() {
                    for child_template in &element.children {
                        let child_with_item = replace_item_bindings(child_template, item, index);
                        create_tree(tree, &child_with_item, Some(node_id), state, patches, false, dependencies);
                    }
                }
            } else {
                // Reconcile existing children
                let mut child_index = 0;
                for (item_index, item) in items.iter().enumerate() {
                    for child_template in &element.children {
                        if let Some(&old_child_id) = old_children.get(child_index) {
                            let child_with_item = replace_item_bindings(child_template, item, item_index);
                            reconcile_node(tree, old_child_id, &child_with_item, state, patches, dependencies);
                        }
                        child_index += 1;
                    }
                }
            }
        }
        
        return; // Done with List reconciliation
    }

    // If element type changed, replace the entire subtree
    if node.element_type != element.element_type {
        replace_subtree(tree, node_id, &node, element, state, patches, dependencies);
        return;
    }

    // Register dependencies for this node (same as create_tree)
    for value in element.props.values() {
        if let Value::Binding(binding) = value {
            dependencies.add_dependency(node_id, binding);
        }
    }

    // Diff props
    let new_props = resolve_props(&element.props, state);
    let prop_patches = diff_props(node_id, &node.props, &new_props);
    patches.extend(prop_patches);

    // Update node props in tree
    if let Some(node) = tree.get_mut(node_id) {
        node.props = new_props.clone();
        node.raw_props = element.props.clone();
    }

    // Reconcile children (skip if element is marked as lazy)
    let is_lazy = element.props.get("__lazy")
        .and_then(|v| {
            if let Value::Static(val) = v {
                val.as_bool()
            } else {
                None
            }
        })
        .unwrap_or(false);
    
    if !is_lazy {
        let old_children = node.children.clone();
        let new_children = &element.children;

        // Simple strategy: match children by index
        for (i, new_child_element) in new_children.iter().enumerate() {
            if let Some(&old_child_id) = old_children.get(i) {
                // Reconcile existing child
                reconcile_node(tree, old_child_id, new_child_element, state, patches, dependencies);
            } else {
                // Create new child
                let new_child_id = create_tree(tree, new_child_element, Some(node_id), state, patches, false, dependencies);
                if let Some(node) = tree.get_mut(node_id) {
                    node.children.push_back(new_child_id);
                }
            }
        }

        // Remove extra old children
        if old_children.len() > new_children.len() {
            for old_child_id in old_children.iter().skip(new_children.len()).copied() {
                // Collect all nodes in subtree first (for Remove patches)
                let subtree_ids = collect_subtree_ids(tree, old_child_id);
                for &id in &subtree_ids {
                    patches.push(Patch::remove(id));
                    dependencies.remove_node(id);
                }
                // Remove from parent's children and from tree
                tree.remove_child(node_id, old_child_id);
                tree.remove(old_child_id);
            }
        }
    }
}

/// Replace an entire subtree when element types don't match.
/// This removes the old node and its descendants, then creates a new subtree in its place.
fn replace_subtree(
    tree: &mut InstanceTree,
    old_node_id: NodeId,
    old_node: &super::InstanceNode,
    new_element: &Element,
    state: &serde_json::Value,
    patches: &mut Vec<Patch>,
    dependencies: &mut DependencyGraph,
) {
    let parent_id = old_node.parent;

    // Remember the position of the old node in its parent's children list
    let old_position = if let Some(pid) = parent_id {
        tree.get(pid).and_then(|parent| {
            parent.children.iter().position(|&id| id == old_node_id)
        })
    } else {
        None
    };

    // Collect all node IDs in the old subtree (depth-first, children before parents)
    let ids_to_remove = collect_subtree_ids(tree, old_node_id);

    // Generate Remove patches and clear dependencies in one pass
    for &id in &ids_to_remove {
        patches.push(Patch::remove(id));
        dependencies.remove_node(id);
    }

    // Remove old node from parent's children list
    if let Some(pid) = parent_id {
        if let Some(parent) = tree.get_mut(pid) {
            parent.children = parent.children.iter().filter(|&&id| id != old_node_id).copied().collect();
        }
    }

    // Remove the old subtree from the tree
    tree.remove(old_node_id);

    // Create the new subtree
    let is_root = parent_id.is_none();
    let new_node_id = create_tree(tree, new_element, parent_id, state, patches, is_root, dependencies);

    // If this was the root, update it
    if is_root {
        tree.set_root(new_node_id);
    } else if let Some(pid) = parent_id {
        if let Some(pos) = old_position {
            if let Some(parent) = tree.get_mut(pid) {
                let current_len = parent.children.len();
                // create_tree appended at end, so new node is at current_len - 1
                // We want it at position `pos`
                if pos < current_len - 1 {
                    // Pop from end (O(log n) for im::Vector) and insert at correct position
                    let new_id = parent.children.pop_back().unwrap();
                    parent.children.insert(pos, new_id);

                    // Get the next sibling for the Move patch
                    let next_sibling = parent.children.get(pos + 1).copied();
                    patches.push(Patch::move_node(pid, new_node_id, next_sibling));
                }
                // If pos == current_len - 1, it's already in the right place (was last child)
            }
        }
    }
}

/// Collect all node IDs in a subtree (post-order: children before parents)
/// Uses iterative approach to avoid stack overflow on deep trees
fn collect_subtree_ids(tree: &InstanceTree, root_id: NodeId) -> Vec<NodeId> {
    let mut result = Vec::new();
    let mut stack: Vec<(NodeId, bool)> = vec![(root_id, false)];

    while let Some((node_id, children_processed)) = stack.pop() {
        if children_processed {
            // Children already processed, add this node
            result.push(node_id);
        } else {
            // Push self back with flag, then push children
            stack.push((node_id, true));
            if let Some(node) = tree.get(node_id) {
                // Push children in reverse order so they're processed left-to-right
                for &child_id in node.children.iter().rev() {
                    stack.push((child_id, false));
                }
            }
        }
    }

    result
}

/// Resolve props by evaluating bindings against state
fn resolve_props(props: &IndexMap<String, crate::ir::Value>, state: &serde_json::Value) -> IndexMap<String, serde_json::Value> {
    resolve_props_with_item(props, state, None)
}

/// Resolve props with optional item context (for list iteration)
fn resolve_props_with_item(
    props: &IndexMap<String, crate::ir::Value>,
    state: &serde_json::Value,
    item: Option<&serde_json::Value>,
) -> IndexMap<String, serde_json::Value> {
    let mut resolved = IndexMap::new();

    for (key, value) in props {
        let resolved_value = match value {
            crate::ir::Value::Static(v) => v.clone(),
            crate::ir::Value::Binding(binding) => {
                if binding.is_item() {
                    // Evaluate item binding
                    if let Some(item_value) = item {
                        evaluate_item_binding(binding, item_value).unwrap_or(serde_json::Value::Null)
                    } else {
                        serde_json::Value::Null
                    }
                } else {
                    // Evaluate state binding
                    evaluate_binding(binding, state).unwrap_or(serde_json::Value::Null)
                }
            }
            crate::ir::Value::TemplateString { template, .. } => {
                // Use expression evaluation for template strings - handles both
                // simple bindings and complex expressions like ternaries
                match crate::reactive::evaluate_template_string(template, state, item) {
                    Ok(result) => serde_json::Value::String(result),
                    Err(_) => serde_json::Value::String(template.clone()),
                }
            }
            crate::ir::Value::Action(action) => {
                // Actions are serialized with @ prefix for renderer to detect
                serde_json::Value::String(format!("@{}", action))
            }
        };
        resolved.insert(key.clone(), resolved_value);
    }

    resolved
}

/// Navigate a binding path against a root JSON value.
/// If the path is empty, returns the root value itself.
fn evaluate_binding_path(binding: &crate::reactive::Binding, root: &serde_json::Value) -> Option<serde_json::Value> {
    if binding.path.is_empty() {
        return Some(root.clone());
    }

    let mut current = root;
    for segment in &binding.path {
        current = current.get(segment)?;
    }
    Some(current.clone())
}

/// Evaluate a binding against state
fn evaluate_binding(binding: &crate::reactive::Binding, state: &serde_json::Value) -> Option<serde_json::Value> {
    evaluate_binding_path(binding, state)
}

/// Evaluate an item binding against the item object
fn evaluate_item_binding(binding: &crate::reactive::Binding, item: &serde_json::Value) -> Option<serde_json::Value> {
    evaluate_binding_path(binding, item)
}

/// Generate a stable key for a list item.
/// Tries to use a key_path (e.g., "id") from the item, falling back to index-based key.
fn generate_item_key(item: &serde_json::Value, key_path: Option<&str>, item_name: &str, index: usize) -> String {
    if let Some(kp) = key_path {
        item.get(kp)
            .map(|v| match v {
                serde_json::Value::String(s) => s.clone(),
                serde_json::Value::Number(n) => n.to_string(),
                _ => format!("{}-{}", item_name, index),
            })
            .unwrap_or_else(|| format!("{}-{}", item_name, index))
    } else {
        format!("{}-{}", item_name, index)
    }
}

/// Reconcile children using keys for efficient updates
/// Uses LIS (Longest Increasing Subsequence) algorithm to minimize DOM moves
pub fn reconcile_keyed_children(
    tree: &mut InstanceTree,
    parent_id: NodeId,
    old_children: &[NodeId],
    new_children: &[Element],
    state: &serde_json::Value,
    dependencies: &mut DependencyGraph,
) -> Vec<Patch> {
    let mut patches = Vec::new();

    // Build a map of old children by key
    let mut old_keyed: IndexMap<String, NodeId> = IndexMap::new();
    let mut old_unkeyed: Vec<NodeId> = Vec::new();

    for &child_id in old_children {
        if let Some(node) = tree.get(child_id) {
            if let Some(key) = &node.key {
                old_keyed.insert(key.clone(), child_id);
            } else {
                old_unkeyed.push(child_id);
            }
        }
    }

    let mut new_child_ids: Vec<NodeId> = Vec::new();
    let mut unkeyed_idx = 0;

    // First pass: match children by key or create new ones
    for new_element in new_children {
        let new_key = new_element.key.as_ref();

        let child_id = if let Some(key) = new_key {
            // Try to find matching keyed child
            if let Some(&old_id) = old_keyed.get(key) {
                // Found a match - reconcile it
                reconcile_node(tree, old_id, new_element, state, &mut patches, dependencies);
                old_keyed.shift_remove(key); // Mark as used
                old_id
            } else {
                // No match - create new child
                create_tree(tree, new_element, Some(parent_id), state, &mut patches, false, dependencies)
            }
        } else {
            // Unkeyed child - try to reuse unkeyed old child
            if let Some(&old_id) = old_unkeyed.get(unkeyed_idx) {
                reconcile_node(tree, old_id, new_element, state, &mut patches, dependencies);
                unkeyed_idx += 1;
                old_id
            } else {
                // No unkeyed child available - create new
                create_tree(tree, new_element, Some(parent_id), state, &mut patches, false, dependencies)
            }
        };

        new_child_ids.push(child_id);
    }

    // Second pass: generate move/insert patches using LIS algorithm
    // Build list of old positions for children that were reused
    let mut old_positions: Vec<Option<usize>> = Vec::new();
    for &new_id in &new_child_ids {
        let old_pos = old_children.iter().position(|&old_id| old_id == new_id);
        old_positions.push(old_pos);
    }

    // Find longest increasing subsequence to minimize moves
    let lis = longest_increasing_subsequence(&old_positions);

    // Update parent's children list
    if let Some(parent_node) = tree.get_mut(parent_id) {
        parent_node.children = new_child_ids.iter().copied().collect();
    }

    // Generate move/insert patches for children not in LIS
    for (new_idx, &child_id) in new_child_ids.iter().enumerate() {
        // Check if this child needs to be moved
        if !lis.contains(&new_idx) {
            // Calculate before_id (the next child in the list, or None for last position)
            let before_id = new_child_ids.get(new_idx + 1).copied();
            patches.push(Patch::move_node(parent_id, child_id, before_id));
        }
    }

    // Third pass: remove old children that weren't reused
    // Also clean up their dependencies to prevent memory leaks
    for &old_id in old_keyed.values() {
        dependencies.remove_node(old_id);
        tree.remove(old_id);
        patches.push(Patch::remove(old_id));
    }
    for &old_id in &old_unkeyed[unkeyed_idx..] {
        dependencies.remove_node(old_id);
        tree.remove(old_id);
        patches.push(Patch::remove(old_id));
    }

    patches
}

/// Find the longest increasing subsequence (LIS) indices
/// This is used to minimize DOM moves during reconciliation
/// Returns indices of elements that are already in correct relative order
fn longest_increasing_subsequence(positions: &[Option<usize>]) -> Vec<usize> {
    // Extract valid positions with their indices
    let valid: Vec<(usize, usize)> = positions
        .iter()
        .enumerate()
        .filter_map(|(idx, &pos)| pos.map(|p| (idx, p)))
        .collect();

    if valid.is_empty() {
        return Vec::new();
    }

    // Use dynamic programming to find LIS
    let n = valid.len();
    let mut dp: Vec<usize> = vec![1; n];
    let mut prev: Vec<Option<usize>> = vec![None; n];

    for i in 1..n {
        for j in 0..i {
            if valid[j].1 < valid[i].1 && dp[j] + 1 > dp[i] {
                dp[i] = dp[j] + 1;
                prev[i] = Some(j);
            }
        }
    }

    // Find the index with maximum LIS length
    let mut max_idx = 0;
    for i in 1..n {
        if dp[i] > dp[max_idx] {
            max_idx = i;
        }
    }

    // Reconstruct the LIS indices
    let mut result = Vec::new();
    let mut idx = Some(max_idx);
    while let Some(i) = idx {
        result.push(valid[i].0);
        idx = prev[i];
    }
    result.reverse();

    result
}

/// Diff two sets of props and generate SetProp patches
pub fn diff_props(
    node_id: NodeId,
    old_props: &IndexMap<String, serde_json::Value>,
    new_props: &IndexMap<String, serde_json::Value>,
) -> Vec<Patch> {
    let mut patches = Vec::new();

    // Check for changed or new props
    for (key, new_value) in new_props {
        if old_props.get(key) != Some(new_value) {
            patches.push(Patch::set_prop(node_id, key.clone(), new_value.clone()));
        }
    }

    // Note: We don't remove old props, just set new ones
    // Platforms should handle prop removal if needed

    patches
}

// ============================================================================
// IRNode-based reconciliation (first-class control flow constructs)
// ============================================================================

/// Create a tree from an IRNode (supports ForEach, When/If, and regular elements)
pub fn create_ir_node_tree(
    tree: &mut InstanceTree,
    node: &IRNode,
    parent_id: Option<NodeId>,
    state: &serde_json::Value,
    patches: &mut Vec<Patch>,
    is_root: bool,
    dependencies: &mut DependencyGraph,
) -> NodeId {
    match node {
        IRNode::Element(element) => {
            // Regular element - use existing create_tree logic
            create_tree(tree, element, parent_id, state, patches, is_root, dependencies)
        }
        IRNode::ForEach { source, item_name, key_path, template, props } => {
            create_foreach_ir_tree(
                tree,
                source,
                item_name,
                key_path.as_deref(),
                template,
                props,
                node,
                parent_id,
                state,
                patches,
                is_root,
                dependencies,
            )
        }
        IRNode::Conditional { value, branches, fallback } => {
            create_conditional_tree(
                tree,
                value,
                branches,
                fallback.as_deref(),
                node,
                parent_id,
                state,
                patches,
                is_root,
                dependencies,
            )
        }
    }
}

/// Create an IRNode tree with separate logical and render parents.
///
/// This is used for control flow children where:
/// - `logical_parent`: Where the node goes in the InstanceTree (the control flow node)
/// - `render_parent`: Where Insert patches should target (the grandparent)
///
/// Control flow nodes are transparent - they exist in the tree for bookkeeping
/// but don't create DOM elements. Their children render directly into the grandparent.
fn create_ir_node_tree_with_render_parent(
    tree: &mut InstanceTree,
    node: &IRNode,
    logical_parent: Option<NodeId>,
    render_parent: Option<NodeId>,
    state: &serde_json::Value,
    patches: &mut Vec<Patch>,
    is_root: bool,
    dependencies: &mut DependencyGraph,
) -> NodeId {
    match node {
        IRNode::Element(element) => {
            // Create element and add to logical parent in tree
            let node_id = tree.create_node(element, state);

            // Add to logical parent's children list
            if let Some(parent) = logical_parent {
                tree.add_child(parent, node_id, None);
            }

            // Emit patches targeting the render parent
            patches.push(Patch::create(
                node_id,
                element.element_type.clone(),
                tree.get(node_id).map(|n| n.props.clone()).unwrap_or_default(),
            ));

            if let Some(render_p) = render_parent {
                patches.push(Patch::insert(render_p, node_id, None));
            } else if is_root {
                patches.push(Patch::insert_root(node_id));
            }

            // Register dependencies
            for (_, value) in &element.props {
                if let Value::Binding(binding) = value {
                    dependencies.add_dependency(node_id, binding);
                }
            }

            // Recursively create children - they use this node as both logical and render parent
            for child in &element.children {
                let child_ir = IRNode::Element((**child).clone());
                create_ir_node_tree(tree, &child_ir, Some(node_id), state, patches, false, dependencies);
            }

            node_id
        }
        IRNode::ForEach { source, item_name, key_path, template, props } => {
            // ForEach within control flow - still uses grandparent for its own children
            create_foreach_ir_tree(
                tree,
                source,
                item_name,
                key_path.as_deref(),
                template,
                props,
                node,
                logical_parent,  // ForEach goes into logical parent
                state,
                patches,
                is_root,
                dependencies,
            )
        }
        IRNode::Conditional { value, branches, fallback } => {
            // Nested conditional - also transparent
            create_conditional_tree(
                tree,
                value,
                branches,
                fallback.as_deref(),
                node,
                logical_parent,  // Conditional goes into logical parent
                state,
                patches,
                is_root,
                dependencies,
            )
        }
    }
}

/// Create a ForEach iteration tree from IRNode::ForEach
fn create_foreach_ir_tree(
    tree: &mut InstanceTree,
    source: &Binding,
    item_name: &str,
    key_path: Option<&str>,
    template: &[IRNode],
    props: &Props,
    original_node: &IRNode,
    parent_id: Option<NodeId>,
    state: &serde_json::Value,
    patches: &mut Vec<Patch>,
    is_root: bool,
    dependencies: &mut DependencyGraph,
) -> NodeId {
    // Evaluate the source array binding
    let array = evaluate_binding(source, state).unwrap_or(serde_json::Value::Array(vec![]));

    // Resolve container props
    let resolved_props = resolve_props(props, state);

    // Create the ForEach container node (internal bookkeeping only - no DOM element)
    let node_id = tree.create_control_flow_node(
        "__ForEach",
        resolved_props.clone(),
        props.clone(),
        ControlFlowKind::ForEach {
            item_name: item_name.to_string(),
            key_path: key_path.map(|s| s.to_string()),
        },
        original_node.clone(),
    );

    // Register dependency on the source array binding
    dependencies.add_dependency(node_id, source);

    // Add to parent's children list (for tree structure) but NO patches for the container itself
    // Control flow nodes are transparent - they don't create DOM elements
    if let Some(parent) = parent_id {
        tree.add_child(parent, node_id, None);
    }

    // Render children for each item in the array
    // Children are inserted into the GRANDPARENT for rendering purposes
    let render_parent = parent_id; // Children render directly into ForEach's parent

    if let serde_json::Value::Array(items) = &array {
        for (index, item) in items.iter().enumerate() {
            let item_key = generate_item_key(item, key_path, item_name, index);

            // Create each template child with item bindings replaced
            for child_template in template {
                let child_with_item = replace_ir_node_item_bindings(
                    child_template,
                    item,
                    index,
                    item_name,
                    &item_key,
                );
                // Children are added to ForEach node in tree, but patches go to grandparent
                let child_id = create_ir_node_tree_with_render_parent(
                    tree,
                    &child_with_item,
                    Some(node_id),  // logical parent (ForEach)
                    render_parent,   // render parent (grandparent)
                    state,
                    patches,
                    is_root && render_parent.is_none(),
                    dependencies
                );
                let _ = child_id; // silence unused warning
            }
        }
    }

    node_id
}

/// Create a Conditional (When/If) tree from IRNode::Conditional
fn create_conditional_tree(
    tree: &mut InstanceTree,
    value: &Value,
    branches: &[ConditionalBranch],
    fallback: Option<&[IRNode]>,
    original_node: &IRNode,
    parent_id: Option<NodeId>,
    state: &serde_json::Value,
    patches: &mut Vec<Patch>,
    is_root: bool,
    dependencies: &mut DependencyGraph,
) -> NodeId {
    // Evaluate the condition value
    let evaluated_value = evaluate_value(value, state);

    // Create the Conditional container node (internal bookkeeping only - no DOM element)
    let mut raw_props = Props::new();
    raw_props.insert("__condition".to_string(), value.clone());

    let node_id = tree.create_control_flow_node(
        "__Conditional",
        IndexMap::new(),
        raw_props,
        ControlFlowKind::Conditional,
        original_node.clone(),
    );

    // Register dependency on the condition binding
    if let Value::Binding(binding) = value {
        dependencies.add_dependency(node_id, binding);
    } else if let Value::TemplateString { bindings, .. } = value {
        for binding in bindings {
            dependencies.add_dependency(node_id, binding);
        }
    }

    // Add to parent's children list (for tree structure) but NO patches for the container itself
    // Control flow nodes are transparent - they don't create DOM elements
    if let Some(parent) = parent_id {
        tree.add_child(parent, node_id, None);
    }

    // Find matching branch
    let matched_children = find_matching_branch(&evaluated_value, branches, fallback);

    // Render matched children - insert directly into grandparent for rendering
    let render_parent = parent_id; // Children render directly into Conditional's parent

    if let Some(children) = matched_children {
        for child in children {
            // Children are added to Conditional node in tree, but patches go to grandparent
            create_ir_node_tree_with_render_parent(
                tree,
                child,
                Some(node_id),  // logical parent (Conditional)
                render_parent,   // render parent (grandparent)
                state,
                patches,
                is_root && render_parent.is_none(),
                dependencies
            );
        }
    }

    node_id
}

/// Find the matching branch for a conditional value
fn find_matching_branch<'a>(
    evaluated_value: &serde_json::Value,
    branches: &'a [ConditionalBranch],
    fallback: Option<&'a [IRNode]>,
) -> Option<&'a [IRNode]> {
    for branch in branches {
        if pattern_matches(evaluated_value, &branch.pattern) {
            return Some(&branch.children);
        }
    }

    fallback
}

/// Check if a pattern matches an evaluated value
/// Supports:
/// - Static values: exact equality matching
/// - Bindings: evaluate the binding as a boolean expression
/// - TemplateStrings: evaluate as expression with `value` available
fn pattern_matches(evaluated_value: &serde_json::Value, pattern: &Value) -> bool {
    match pattern {
        Value::Static(pattern_value) => {
            values_match(evaluated_value, pattern_value)
        }
        Value::Binding(_binding) => {
            // Binding patterns are evaluated as boolean expressions
            // The binding itself should resolve to true/false
            // This allows: Case(match: @state.isAdmin)
            false // Bindings in patterns need state context, handled elsewhere
        }
        Value::TemplateString { template, .. } => {
            // Expression pattern: evaluate with `value` variable available
            // This allows: Case(when: "${value > 100}") or Case(match: "${value == 'loading'}")
            evaluate_expression_pattern(template, evaluated_value)
        }
        Value::Action(_) => false, // Actions don't make sense as patterns
    }
}

/// Evaluate an expression pattern against a value
/// The expression has access to `value` which is the evaluated When condition
fn evaluate_expression_pattern(template: &str, value: &serde_json::Value) -> bool {
    use crate::reactive::evaluate_expression;
    use std::collections::HashMap;

    // Build a context with the value available
    let mut context: HashMap<String, serde_json::Value> = HashMap::new();
    context.insert("value".to_string(), value.clone());

    // Extract the expression from the template (e.g., "${value > 100}" -> "value > 100")
    let expr = if template.starts_with("${") && template.ends_with("}") {
        &template[2..template.len()-1]
    } else if template.contains("${") {
        // Template with embedded expression - evaluate the whole thing
        // Build a JSON context for evaluate_template_string
        let json_context = serde_json::json!({ "value": value });
        match evaluate_template_string(template, &json_context, None) {
            Ok(result) => {
                // Check if result is truthy
                return is_truthy_string(&result);
            }
            Err(_) => return false,
        }
    } else {
        // Plain expression without ${} wrapper
        template
    };

    // Evaluate the expression
    match evaluate_expression(expr, &context) {
        Ok(result) => is_truthy(&result),
        Err(_) => false,
    }
}

/// Check if a string value is truthy
fn is_truthy_string(s: &str) -> bool {
    !s.is_empty() && s != "false" && s != "0" && s != "null" && s != "undefined"
}

/// Check if a JSON value is truthy
fn is_truthy(value: &serde_json::Value) -> bool {
    match value {
        serde_json::Value::Null => false,
        serde_json::Value::Bool(b) => *b,
        serde_json::Value::Number(n) => n.as_f64().map(|f| f != 0.0).unwrap_or(false),
        serde_json::Value::String(s) => is_truthy_string(s),
        serde_json::Value::Array(arr) => !arr.is_empty(),
        serde_json::Value::Object(obj) => !obj.is_empty(),
    }
}

/// Check if two JSON values match for conditional branching
/// Supports:
/// - Exact equality: Case(match: "loading"), Case(match: 42), Case(match: true), Case(match: null)
/// - Wildcard patterns: Case(match: "_") or Case(match: "*") matches anything
/// - Multiple values: Case(match: ["loading", "pending"]) matches any in the array
/// - Expression patterns: Case(match: "${value > 100}")
fn values_match(value: &serde_json::Value, pattern: &serde_json::Value) -> bool {
    match pattern {
        // Array pattern - match any value in the array
        serde_json::Value::Array(patterns) => {
            patterns.iter().any(|p| values_match(value, p))
        }

        // String pattern with special syntax
        serde_json::Value::String(pattern_str) => {
            // Wildcard patterns
            if pattern_str == "_" || pattern_str == "*" {
                return true;
            }

            // Expression pattern (${...})
            if pattern_str.contains("${") {
                return evaluate_expression_pattern(pattern_str, value);
            }

            // Exact string equality
            matches!(value, serde_json::Value::String(s) if s == pattern_str)
        }

        // Exact equality for non-string primitives
        _ => {
            if value == pattern {
                return true;
            }

            // Boolean coercion for truthy/falsy matching
            match (value, pattern) {
                (serde_json::Value::Bool(b), serde_json::Value::Bool(p)) => b == p,
                (serde_json::Value::Null, serde_json::Value::Null) => true,
                _ => false,
            }
        }
    }
}

/// Evaluate a Value against state
fn evaluate_value(value: &Value, state: &serde_json::Value) -> serde_json::Value {
    match value {
        Value::Static(v) => v.clone(),
        Value::Binding(binding) => {
            evaluate_binding(binding, state).unwrap_or(serde_json::Value::Null)
        }
        Value::TemplateString { template, .. } => {
            match evaluate_template_string(template, state, None) {
                Ok(result) => serde_json::Value::String(result),
                Err(_) => serde_json::Value::String(template.clone()),
            }
        }
        Value::Action(action) => serde_json::Value::String(format!("@{}", action)),
    }
}

/// Replace item bindings in an IRNode with actual item values
/// Supports configurable item variable names (e.g., "todo", "user" instead of "item")
fn replace_ir_node_item_bindings(
    node: &IRNode,
    item: &serde_json::Value,
    index: usize,
    item_name: &str,
    item_key: &str,
) -> IRNode {
    match node {
        IRNode::Element(element) => {
            let mut new_element = replace_item_bindings_with_name(element, item, index, item_name);
            // Override key with the computed item key
            new_element.key = Some(item_key.to_string());
            IRNode::Element(new_element)
        }
        IRNode::ForEach { source, item_name: inner_item_name, key_path, template, props } => {
            // Note: source binding is kept as-is; nested ForEach maintains its own iteration context
            // Replace in props
            let new_props = replace_props_item_bindings(props, item, item_name);

            // Recursively replace in template (but inner ForEach has its own item context)
            let new_template: Vec<IRNode> = template.iter()
                .map(|child| replace_ir_node_item_bindings(child, item, index, item_name, item_key))
                .collect();

            IRNode::ForEach {
                source: source.clone(),
                item_name: inner_item_name.clone(),
                key_path: key_path.clone(),
                template: new_template,
                props: new_props,
            }
        }
        IRNode::Conditional { value, branches, fallback } => {
            // Replace in condition value
            let new_value = replace_value_item_bindings(value, item, item_name);

            // Replace in branches
            let new_branches: Vec<ConditionalBranch> = branches.iter()
                .map(|branch| {
                    let new_pattern = replace_value_item_bindings(&branch.pattern, item, item_name);
                    let new_children: Vec<IRNode> = branch.children.iter()
                        .map(|child| replace_ir_node_item_bindings(child, item, index, item_name, item_key))
                        .collect();
                    ConditionalBranch::new(new_pattern, new_children)
                })
                .collect();

            // Replace in fallback
            let new_fallback = fallback.as_ref().map(|f| {
                f.iter()
                    .map(|child| replace_ir_node_item_bindings(child, item, index, item_name, item_key))
                    .collect()
            });

            IRNode::Conditional {
                value: new_value,
                branches: new_branches,
                fallback: new_fallback,
            }
        }
    }
}

/// Replace item bindings in Props
fn replace_props_item_bindings(props: &Props, item: &serde_json::Value, item_name: &str) -> Props {
    let mut new_props = Props::new();
    for (key, value) in props {
        new_props.insert(key.clone(), replace_value_item_bindings(value, item, item_name));
    }
    new_props
}

/// Replace item bindings in a Value
/// Uses optimized single-pass replacement to avoid O(n²) string operations.
/// `item_name` allows custom iteration variable names (e.g., "todo", "user" instead of "item").
fn replace_value_item_bindings(value: &Value, item: &serde_json::Value, item_name: &str) -> Value {
    match value {
        Value::Binding(binding) => {
            if binding.is_item() {
                if binding.path.is_empty() {
                    Value::Static(item.clone())
                } else {
                    let path = binding.full_path();
                    if let Some(val) = navigate_item_path(item, &path) {
                        Value::Static(val.clone())
                    } else {
                        value.clone()
                    }
                }
            } else {
                value.clone()
            }
        }
        Value::TemplateString { template, bindings } => {
            let has_item_bindings = bindings.iter().any(|b| b.is_item());
            if !has_item_bindings {
                return value.clone();
            }

            // PHASE 1: Collect all replacements for explicit bindings (single pass)
            let mut replacements = Vec::new();
            for binding in bindings {
                if binding.is_item() {
                    let pattern = format!("${{{}}}", binding.full_path_with_source());
                    if let Some(start) = template.find(&pattern) {
                        let replacement = if binding.path.is_empty() {
                            format_value_for_replacement(item, false)
                        } else if let Some(val) = navigate_item_path(item, &binding.full_path()) {
                            format_value_for_replacement(val, false)
                        } else {
                            continue;
                        };
                        replacements.push(Replacement {
                            start,
                            end: start + pattern.len(),
                            text: replacement,
                        });
                    }
                }
            }

            // PHASE 2: Apply explicit binding replacements
            let mut result = apply_replacements(template, replacements);

            // PHASE 3: Replace item.xxx references in expressions (e.g., ternary operators)
            // Uses the configurable item_name for custom iteration variables
            let expr_replacements = collect_item_replacements_with_name(&result, item, true, item_name);
            result = apply_replacements(&result, expr_replacements);

            // Filter out resolved item bindings, keep state bindings
            let remaining_bindings: Vec<_> = bindings.iter()
                .filter(|b| b.is_state())
                .cloned()
                .collect();

            if remaining_bindings.is_empty() {
                if result.contains("${") {
                    match evaluate_template_string(&result, &serde_json::Value::Null, None) {
                        Ok(evaluated) => Value::Static(serde_json::Value::String(evaluated)),
                        Err(_) => Value::Static(serde_json::Value::String(result)),
                    }
                } else {
                    Value::Static(serde_json::Value::String(result))
                }
            } else {
                Value::TemplateString {
                    template: result,
                    bindings: remaining_bindings,
                }
            }
        }
        // Handle static strings containing ${item.xxx} pattern (legacy/fallback)
        Value::Static(serde_json::Value::String(s)) if s.contains(&format!("${{{}.", item_name)) || s.contains(&format!("${{{}}}", item_name)) => {
            replace_static_item_bindings_with_name(s, item, item_name)
        }
        _ => value.clone(),
    }
}

/// Find all item.xxx references in a string with configurable item name.
fn collect_item_replacements_with_name(s: &str, item: &serde_json::Value, quote_strings: bool, item_name: &str) -> Vec<Replacement> {
    let mut replacements = Vec::new();
    let mut pos = 0;

    while pos < s.len() {
        if let Some(rel_start) = s[pos..].find(item_name) {
            let abs_start = pos + rel_start;
            let after_item = abs_start + item_name.len();

            if after_item < s.len() && s.as_bytes()[after_item] == b'.' {
                let path_start = after_item + 1;
                let path_end = find_path_end(s, path_start);

                if path_end > path_start {
                    let path = &s[path_start..path_end];
                    if let Some(val) = navigate_item_path(item, path) {
                        let replacement = format_value_for_replacement(val, quote_strings);
                        replacements.push(Replacement {
                            start: abs_start,
                            end: path_end,
                            text: replacement,
                        });
                    }
                }
                pos = path_end.max(after_item + 1);
            } else {
                pos = after_item;
            }
        } else {
            break;
        }
    }

    replacements
}

/// Replace item bindings in a static string value with configurable item name
fn replace_static_item_bindings_with_name(s: &str, item: &serde_json::Value, item_name: &str) -> Value {
    let mut replacements = Vec::new();
    let mut pos = 0;

    while let Some(start) = s[pos..].find("${") {
        let abs_start = pos + start;

        if let Some(end) = s[abs_start..].find('}') {
            let abs_end = abs_start + end;
            let content = &s[abs_start + 2..abs_end];

            if content == item_name {
                // Bare ${item}
                replacements.push(Replacement {
                    start: abs_start,
                    end: abs_end + 1,
                    text: format_value_for_replacement(item, false),
                });
                pos = abs_end + 1;
            } else if content.starts_with(&format!("{}.", item_name)) && is_simple_path_with_name(content, item_name) {
                // Simple ${item.path}
                let path = &content[item_name.len() + 1..];
                if let Some(val) = navigate_item_path(item, path) {
                    replacements.push(Replacement {
                        start: abs_start,
                        end: abs_end + 1,
                        text: format_value_for_replacement(val, false),
                    });
                }
                pos = abs_end + 1;
            } else if content.contains(&format!("{}.", item_name)) || content.contains(&format!("{} ", item_name)) {
                // Complex expression - replace item refs within, then evaluate
                let expr_replacements = collect_item_replacements_with_name(content, item, true, item_name);
                let substituted_content = apply_replacements(content, expr_replacements);
                let new_expr = format!("${{{}}}", substituted_content);

                match evaluate_template_string(&new_expr, &serde_json::Value::Null, None) {
                    Ok(evaluated) => {
                        replacements.push(Replacement {
                            start: abs_start,
                            end: abs_end + 1,
                            text: evaluated,
                        });
                    }
                    Err(_) => {}
                }
                pos = abs_end + 1;
            } else {
                pos = abs_end + 1;
            }
        } else {
            break;
        }
    }

    let result = apply_replacements(s, replacements);
    Value::Static(serde_json::Value::String(result))
}

/// Check if a string is a simple path with configurable item name
fn is_simple_path_with_name(s: &str, item_name: &str) -> bool {
    if !s.starts_with(item_name) {
        return false;
    }

    let after_item = &s[item_name.len()..];
    if after_item.is_empty() {
        return true;
    }

    if !after_item.starts_with('.') {
        return false;
    }

    after_item[1..].chars().all(|c| c.is_alphanumeric() || c == '_' || c == '.')
}

/// Replace item bindings in an Element with a configurable item name
/// This is the full implementation that supports custom iteration variable names.
pub fn replace_item_bindings_with_name(
    element: &Element,
    item: &serde_json::Value,
    index: usize,
    item_name: &str,
) -> Element {
    let mut new_element = element.clone();

    // Replace bindings in props using the unified Value replacement logic
    let mut new_props = Props::new();
    for (key, value) in &element.props {
        new_props.insert(key.clone(), replace_value_item_bindings(value, item, item_name));
    }
    new_element.props = new_props;

    // Generate key using the item name
    let key = item.get("id")
        .and_then(|v| v.as_str().map(|s| s.to_string()).or_else(|| v.as_i64().map(|n| n.to_string())))
        .or_else(|| item.get("key").and_then(|v| v.as_str().map(|s| s.to_string())))
        .map(|id| format!("{}-{}", item_name, id))
        .unwrap_or_else(|| format!("{}-{}", item_name, index));
    new_element.key = Some(key);

    // Recursively replace in children
    new_element.children = element.children.iter()
        .map(|child| std::sync::Arc::new(replace_item_bindings_with_name(child, item, index, item_name)))
        .collect();

    new_element
}

/// Reconcile an existing tree against a new IRNode
pub fn reconcile_ir_node(
    tree: &mut InstanceTree,
    node_id: NodeId,
    node: &IRNode,
    state: &serde_json::Value,
    patches: &mut Vec<Patch>,
    dependencies: &mut DependencyGraph,
) {
    let existing_node = tree.get(node_id).cloned();
    if existing_node.is_none() {
        return;
    }
    let existing = existing_node.unwrap();

    match node {
        IRNode::Element(element) => {
            // Regular element reconciliation
            reconcile_node(tree, node_id, element, state, patches, dependencies);
        }
        IRNode::ForEach { source, item_name, key_path, template, props: _ } => {
            // ForEach reconciliation
            if !existing.is_foreach() {
                // Type mismatch - replace entire subtree
                let parent_id = existing.parent;
                remove_subtree(tree, node_id, patches, dependencies);
                create_ir_node_tree(tree, node, parent_id, state, patches, parent_id.is_none(), dependencies);
                return;
            }

            // Re-evaluate the array
            let array = evaluate_binding(source, state).unwrap_or(serde_json::Value::Array(vec![]));

            if let serde_json::Value::Array(items) = &array {
                let old_children = existing.children.clone();
                let expected_children_count = items.len() * template.len();

                // If child count changed, rebuild
                if old_children.len() != expected_children_count {
                    // Remove old children
                    for &old_child_id in &old_children {
                        patches.push(Patch::remove(old_child_id));
                    }

                    if let Some(node) = tree.get_mut(node_id) {
                        node.children.clear();
                    }

                    // Create new children
                    for (index, item) in items.iter().enumerate() {
                        let item_key = generate_item_key(item, key_path.as_deref(), item_name, index);

                        for child_template in template {
                            let child_with_item = replace_ir_node_item_bindings(
                                child_template,
                                item,
                                index,
                                item_name,
                                &item_key,
                            );
                            create_ir_node_tree(tree, &child_with_item, Some(node_id), state, patches, false, dependencies);
                        }
                    }
                } else {
                    // Reconcile existing children
                    let mut child_index = 0;
                    for (item_index, item) in items.iter().enumerate() {
                        let item_key = generate_item_key(item, key_path.as_deref(), item_name, item_index);

                        for child_template in template {
                            if let Some(&old_child_id) = old_children.get(child_index) {
                                let child_with_item = replace_ir_node_item_bindings(
                                    child_template,
                                    item,
                                    item_index,
                                    item_name,
                                    &item_key,
                                );
                                reconcile_ir_node(tree, old_child_id, &child_with_item, state, patches, dependencies);
                            }
                            child_index += 1;
                        }
                    }
                }
            }
        }
        IRNode::Conditional { value, branches, fallback } => {
            // Conditional reconciliation
            if !existing.is_conditional() {
                // Type mismatch - replace entire subtree
                let parent_id = existing.parent;
                remove_subtree(tree, node_id, patches, dependencies);
                create_ir_node_tree(tree, node, parent_id, state, patches, parent_id.is_none(), dependencies);
                return;
            }

            // Re-evaluate the condition
            let evaluated_value = evaluate_value(value, state);
            let matched_children = find_matching_branch(&evaluated_value, branches, fallback.as_deref());

            let old_children = existing.children.clone();

            // For simplicity, if the branch changed, we remove old children and create new ones
            // A more sophisticated approach would diff the branches
            if let Some(children) = matched_children {
                if old_children.len() != children.len() {
                    // Clear old children
                    for &old_child_id in &old_children {
                        patches.push(Patch::remove(old_child_id));
                    }

                    if let Some(node) = tree.get_mut(node_id) {
                        node.children.clear();
                    }

                    // Create new children
                    for child in children {
                        create_ir_node_tree(tree, child, Some(node_id), state, patches, false, dependencies);
                    }
                } else {
                    // Reconcile children
                    for (i, child) in children.iter().enumerate() {
                        if let Some(&old_child_id) = old_children.get(i) {
                            reconcile_ir_node(tree, old_child_id, child, state, patches, dependencies);
                        }
                    }
                }
            } else {
                // No matched branch - remove all children
                for &old_child_id in &old_children {
                    patches.push(Patch::remove(old_child_id));
                }

                if let Some(node) = tree.get_mut(node_id) {
                    node.children.clear();
                }
            }
        }
    }
}

/// Remove a subtree and generate Remove patches
fn remove_subtree(
    tree: &mut InstanceTree,
    node_id: NodeId,
    patches: &mut Vec<Patch>,
    dependencies: &mut DependencyGraph,
) {
    let ids = collect_subtree_ids(tree, node_id);
    for &id in &ids {
        patches.push(Patch::remove(id));
        dependencies.remove_node(id);
    }
    tree.remove(node_id);
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::ir::Value;
    use serde_json::json;

    #[test]
    fn test_create_simple_tree() {
        use crate::reactive::DependencyGraph;

        let mut tree = InstanceTree::new();
        let mut patches = Vec::new();
        let mut dependencies = DependencyGraph::new();

        let element = Element::new("Column")
            .with_child(Element::new("Text").with_prop("text", Value::Static(json!("Hello"))));

        let state = json!({});
        create_tree(&mut tree, &element, None, &state, &mut patches, true, &mut dependencies);

        // Should create 2 nodes (Column + Text) + 2 Inserts (root + child)
        // Create Column, Insert Column into root, Create Text, Insert Text into Column
        assert_eq!(patches.len(), 4);

        // Verify root insert patch exists
        let root_insert = patches.iter().find(|p| {
            matches!(p, Patch::Insert { parent_id, .. } if parent_id == "root")
        });
        assert!(root_insert.is_some(), "Root insert patch should exist");
    }

    #[test]
    fn test_diff_props() {
        let node_id = NodeId::default();
        let old = indexmap::indexmap! {
            "color".to_string() => json!("red"),
            "size".to_string() => json!(16),
        };
        let new = indexmap::indexmap! {
            "color".to_string() => json!("blue"),
            "size".to_string() => json!(16),
        };

        let patches = diff_props(node_id, &old, &new);

        // Only color changed
        assert_eq!(patches.len(), 1);
    }

    #[test]
    fn test_longest_increasing_subsequence_basic() {
        // Test case: [0, 1, 2, 3] - already in order, should select all
        let positions = vec![Some(0), Some(1), Some(2), Some(3)];
        let lis = longest_increasing_subsequence(&positions);
        assert_eq!(lis, vec![0, 1, 2, 3]);
    }

    #[test]
    fn test_longest_increasing_subsequence_reverse() {
        // Test case: [3, 2, 1, 0] - reversed, should select only one element
        let positions = vec![Some(3), Some(2), Some(1), Some(0)];
        let lis = longest_increasing_subsequence(&positions);
        assert_eq!(lis.len(), 1);
    }

    #[test]
    fn test_longest_increasing_subsequence_mixed() {
        // Test case: [0, 3, 1, 2] - should select [0, 1, 2]
        let positions = vec![Some(0), Some(3), Some(1), Some(2)];
        let lis = longest_increasing_subsequence(&positions);
        assert_eq!(lis.len(), 3);
        // Should contain indices of 0, 1, 2 in the original array
        assert!(lis.contains(&0));
        assert!(lis.contains(&2));
        assert!(lis.contains(&3));
    }

    #[test]
    fn test_longest_increasing_subsequence_with_new_items() {
        // Test case: [None, Some(0), None, Some(1)] - new items mixed with existing
        let positions = vec![None, Some(0), None, Some(1)];
        let lis = longest_increasing_subsequence(&positions);
        assert_eq!(lis, vec![1, 3]); // Only indices with existing positions
    }

    #[test]
    fn test_longest_increasing_subsequence_empty() {
        let positions: Vec<Option<usize>> = vec![];
        let lis = longest_increasing_subsequence(&positions);
        assert_eq!(lis, Vec::<usize>::new());
    }

    #[test]
    fn test_longest_increasing_subsequence_all_new() {
        // All new items (no old positions)
        let positions = vec![None, None, None];
        let lis = longest_increasing_subsequence(&positions);
        assert_eq!(lis, Vec::<usize>::new());
    }

    #[test]
    fn test_reconcile_keyed_children_basic() {
        let mut tree = InstanceTree::new();
        let mut dependencies = DependencyGraph::new();
        let state = json!({});

        // Create a parent node
        let parent = Element::new("Column");
        let parent_id = tree.create_node(&parent, &state);

        // Create old children
        let mut old_child_1 = Element::new("Text").with_prop("text", Value::Static(json!("Item 1")));
        old_child_1.key = Some("item-1".to_string());
        let old_id_1 = tree.create_node(&old_child_1, &state);

        let mut old_child_2 = Element::new("Text").with_prop("text", Value::Static(json!("Item 2")));
        old_child_2.key = Some("item-2".to_string());
        let old_id_2 = tree.create_node(&old_child_2, &state);

        tree.add_child(parent_id, old_id_1, None);
        tree.add_child(parent_id, old_id_2, None);

        // New children in reversed order
        let mut new_child_2 = Element::new("Text").with_prop("text", Value::Static(json!("Item 2")));
        new_child_2.key = Some("item-2".to_string());

        let mut new_child_1 = Element::new("Text").with_prop("text", Value::Static(json!("Item 1")));
        new_child_1.key = Some("item-1".to_string());

        let new_children = vec![new_child_2, new_child_1];
        let old_children = vec![old_id_1, old_id_2];

        let patches = reconcile_keyed_children(&mut tree, parent_id, &old_children, &new_children, &state, &mut dependencies);

        // Should have move patches but no create/remove patches (children are reused)
        let move_count = patches.iter().filter(|p| matches!(p, Patch::Move { .. })).count();
        let create_count = patches.iter().filter(|p| matches!(p, Patch::Create { .. })).count();
        let remove_count = patches.iter().filter(|p| matches!(p, Patch::Remove { .. })).count();

        assert_eq!(create_count, 0, "Should not create new children");
        assert_eq!(remove_count, 0, "Should not remove any children");
        assert!(move_count > 0, "Should have move patches for reordering");
    }

    #[test]
    fn test_reconcile_keyed_children_add_remove() {
        let mut tree = InstanceTree::new();
        let mut dependencies = DependencyGraph::new();
        let state = json!({});

        let parent = Element::new("Column");
        let parent_id = tree.create_node(&parent, &state);

        // Old: item-1, item-2
        let mut old_child_1 = Element::new("Text");
        old_child_1.key = Some("item-1".to_string());
        let old_id_1 = tree.create_node(&old_child_1, &state);

        let mut old_child_2 = Element::new("Text");
        old_child_2.key = Some("item-2".to_string());
        let old_id_2 = tree.create_node(&old_child_2, &state);

        tree.add_child(parent_id, old_id_1, None);
        tree.add_child(parent_id, old_id_2, None);

        // New: item-2, item-3 (removed item-1, added item-3)
        let mut new_child_2 = Element::new("Text");
        new_child_2.key = Some("item-2".to_string());

        let mut new_child_3 = Element::new("Text");
        new_child_3.key = Some("item-3".to_string());

        let new_children = vec![new_child_2, new_child_3];
        let old_children = vec![old_id_1, old_id_2];

        let patches = reconcile_keyed_children(&mut tree, parent_id, &old_children, &new_children, &state, &mut dependencies);

        let create_count = patches.iter().filter(|p| matches!(p, Patch::Create { .. })).count();
        let remove_count = patches.iter().filter(|p| matches!(p, Patch::Remove { .. })).count();

        assert_eq!(create_count, 1, "Should create item-3");
        assert_eq!(remove_count, 1, "Should remove item-1");
    }
}