hypen_engine/reconcile/

diff.rs

use super::{InstanceTree, Patch};
use crate::ir::{Element, NodeId, Value};
use crate::reactive::{DependencyGraph, evaluate_template_string};
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
}

/// 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(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)
}

/// Check if a string is a simple item path (e.g., "item.name" or "item.user.profile")
/// Simple paths contain only alphanumeric chars, underscores, and dots for nesting.
/// Complex expressions contain operators like ?, :, +, -, etc.
fn is_simple_path(s: &str) -> bool {
    // Must start with "item" followed by valid path characters
    if !s.starts_with("item") {
        return false;
    }

    let after_item = &s[4..]; // Skip "item"
    if after_item.is_empty() {
        return true; // Just "item"
    }

    // Must be "item.something" - check rest is valid path
    if !after_item.starts_with('.') {
        return false;
    }

    // Check all characters after "item." are valid path chars
    after_item[1..].chars().all(|c| c.is_alphanumeric() || c == '_' || c == '.')
}

/// Replace item bindings (Value::Binding with is_item() or TemplateString with item bindings) with actual item values
pub fn replace_item_bindings(element: &Element, item: &serde_json::Value, index: usize) -> Element {
    let mut new_element = element.clone();

    // Replace bindings in props
    let mut new_props = IndexMap::new();
    for (key, value) in &element.props {
        let new_value = match value {
            Value::Binding(binding) => {
                // Check if this is an item binding
                if binding.is_item() {
                    // For bare @item, return the whole item
                    if binding.path.is_empty() {
                        Value::Static(item.clone())
                    } else {
                        // Navigate the path (e.g., ["name"] or ["user", "profile"])
                        let prop_path = binding.full_path();
                        if let Some(val) = navigate_item_path(item, &prop_path) {
                            Value::Static(val.clone())
                        } else {
                            value.clone()
                        }
                    }
                } else {
                    value.clone()
                }
            }
            Value::TemplateString { template, bindings } => {
                // Check if any bindings are item bindings
                let has_item_bindings = bindings.iter().any(|b| b.is_item());

                if has_item_bindings {
                    let mut result = template.clone();

                    for binding in bindings {
                        if binding.is_item() {
                            let pattern = format!("${{{}}}", binding.full_path_with_source());
                            let replacement = if binding.path.is_empty() {
                                // Bare ${item}
                                match item {
                                    serde_json::Value::String(s) => s.clone(),
                                    serde_json::Value::Number(n) => n.to_string(),
                                    serde_json::Value::Bool(b) => b.to_string(),
                                    _ => serde_json::to_string(item).unwrap_or_default(),
                                }
                            } else if let Some(val) = navigate_item_path(item, &binding.full_path()) {
                                match val {
                                    serde_json::Value::String(s) => s.clone(),
                                    serde_json::Value::Number(n) => n.to_string(),
                                    serde_json::Value::Bool(b) => b.to_string(),
                                    _ => serde_json::to_string(val).unwrap_or_default(),
                                }
                            } else {
                                continue; // Skip if path not found
                            };
                            result = result.replace(&pattern, &replacement);
                        }
                    }

                    // 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() {
                        // Check if result still contains ${...} expressions that need evaluation
                        if result.contains("${") {
                            // Evaluate the expression (item values have been substituted)
                            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,
                        }
                    }
                } else {
                    value.clone()
                }
            }
            // Handle static strings containing ${item.xxx} pattern (legacy/fallback)
            // This handles both simple patterns like ${item.name} and complex expressions
            // like ${item.selected ? '2px' : '1px'}
            Value::Static(serde_json::Value::String(s)) if s.contains("${item.") || s.contains("${item}") => {
                let mut result = s.clone();

                // Strategy: Process ${...} blocks one at a time
                // - If block is simple (just ${item} or ${item.path}), replace entire block with value
                // - If block is complex (contains operators like ?, :, +, etc.), replace item refs then evaluate

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

                    // Find matching closing brace
                    if let Some(end) = result[abs_start..].find('}') {
                        let abs_end = abs_start + end;
                        let content = &result[abs_start + 2..abs_end]; // Content between ${ and }

                        // Check if this is a simple item reference or a complex expression
                        if content == "item" {
                            // Bare ${item} - replace with full item value
                            let replacement = match item {
                                serde_json::Value::String(s) => s.clone(),
                                serde_json::Value::Number(n) => n.to_string(),
                                serde_json::Value::Bool(b) => b.to_string(),
                                _ => serde_json::to_string(item).unwrap_or_default(),
                            };
                            result = format!("{}{}{}", &result[..abs_start], replacement, &result[abs_end + 1..]);
                            pos = 0;
                            continue;
                        } else if content.starts_with("item.") && is_simple_path(content) {
                            // Simple ${item.path.to.value} - replace entire block with value
                            let path = &content[5..]; // Skip "item."
                            if let Some(val) = navigate_item_path(item, path) {
                                let replacement = match val {
                                    serde_json::Value::String(s) => 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(),
                                };
                                result = format!("{}{}{}", &result[..abs_start], replacement, &result[abs_end + 1..]);
                                pos = 0;
                                continue;
                            }
                        } else if content.contains("item.") || content.contains("item ") {
                            // Complex expression with item references - replace item refs within the expression
                            let mut expr_content = content.to_string();

                            // Replace all item.xxx references within this expression
                            let mut expr_pos = 0;
                            while let Some(item_start) = expr_content[expr_pos..].find("item.") {
                                let item_abs_start = expr_pos + item_start;
                                let path_start = item_abs_start + 5; // Skip "item."

                                // Find the end of the path (valid identifier chars only)
                                let mut path_end = path_start;
                                let chars: Vec<char> = expr_content[path_start..].chars().collect();

                                for (i, ch) in chars.iter().enumerate() {
                                    if ch.is_alphanumeric() || *ch == '_' || *ch == '.' {
                                        if *ch == '.' {
                                            if i + 1 >= chars.len() || {
                                                let next = chars[i + 1];
                                                !next.is_alphanumeric() && next != '_'
                                            } {
                                                break;
                                            }
                                        }
                                        path_end = path_start + i + 1;
                                    } else {
                                        break;
                                    }
                                }

                                if path_end > path_start {
                                    let path = &expr_content[path_start..path_end];
                                    if let Some(val) = navigate_item_path(item, path) {
                                        let replacement = match val {
                                            serde_json::Value::String(s) => format!("'{}'", s),
                                            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(),
                                        };
                                        expr_content = format!(
                                            "{}{}{}",
                                            &expr_content[..item_abs_start],
                                            replacement,
                                            &expr_content[path_end..]
                                        );
                                        expr_pos = 0;
                                        continue;
                                    }
                                }
                                expr_pos = item_abs_start + 5;
                            }

                            // Reconstruct the expression block and evaluate
                            let new_expr = format!("${{{}}}", expr_content);
                            match evaluate_template_string(&new_expr, &serde_json::Value::Null, None) {
                                Ok(evaluated) => {
                                    result = format!("{}{}{}", &result[..abs_start], evaluated, &result[abs_end + 1..]);
                                    pos = 0;
                                    continue;
                                }
                                Err(_) => {
                                    // If evaluation fails, leave as-is and move on
                                    pos = abs_end + 1;
                                    continue;
                                }
                            }
                        }

                        // Not an item-related block, skip it
                        pos = abs_end + 1;
                    } else {
                        break;
                    }
                }

                Value::Static(serde_json::Value::String(result))
            }
            _ => value.clone(),
        };
        new_props.insert(key.clone(), new_value);
    }
    new_element.props = new_props;

    // Add a key for reconciliation (use array index)
    new_element.key = Some(format!("list-item-{}", index));

    // Recursively replace in children
    new_element.children = element.children.iter()
        .map(|child| replace_item_bindings(child, item, index))
        .collect();

    new_element
}

/// 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(new_child_id);
                }
            }
        }

        // Remove extra old children
        if old_children.len() > new_children.len() {
            for &old_child_id in &old_children[new_children.len()..] {
                patches.push(Patch::remove(old_child_id));
                // TODO: Remove from tree
            }
        }
    }
}

/// 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.retain(|&id| id != old_node_id);
        }
    }

    // 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(1)) and insert at correct position (O(n))
                    let new_id = parent.children.pop().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
}

/// Evaluate an item binding against the item object
fn evaluate_item_binding(binding: &crate::reactive::Binding, item: &serde_json::Value) -> Option<serde_json::Value> {
    if binding.path.is_empty() {
        return Some(item.clone());
    }

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

/// Evaluate a binding against state using its parsed path
fn evaluate_binding(binding: &crate::reactive::Binding, state: &serde_json::Value) -> Option<serde_json::Value> {
    let mut current = state;

    for segment in &binding.path {
        current = current.get(segment)?;
    }

    Some(current.clone())
}

/// Reconcile children using keys for efficient updates
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.clone();
    }

    // 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
    for old_id in old_keyed.values() {
        patches.push(Patch::remove(*old_id));
    }
    for &old_id in &old_unkeyed[unkeyed_idx..] {
        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
}

#[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");
    }
}