hypen_engine/reconcile/

diff.rs

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

/// Replace ${item.x} 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 binding starts with "item"
                if binding.path.first().map(|s| s.as_str()) == Some("item") {
                    // Extract path after "item." (skip first segment)
                    let prop_path = binding.path[1..].join(".");

                    // Navigate nested path (e.g., "images.0" -> item["images"][0])
                    if let Some(val) = navigate_item_path(item, &prop_path) {
                        Value::Static(val.clone())
                    } else {
                        value.clone()
                    }
                } else {
                    value.clone()
                }
            }
            Value::Static(serde_json::Value::String(s)) => {
                // Check if static string contains ${item.property} pattern
                if s.contains("${item.") {
                    let mut result = s.clone();

                    // Find and replace all ${item.path} patterns
                    // Simple parser: look for ${item. and find the matching }
                    let mut pos = 0;
                    while let Some(start) = result[pos..].find("${item.") {
                        let abs_start = pos + start;
                        if let Some(end) = result[abs_start..].find('}') {
                            let abs_end = abs_start + end;
                            // Extract the path between ${item. and }
                            let path = &result[abs_start + 7..abs_end]; // 7 = "${item.".len()

                            if let Some(val) = navigate_item_path(item, path) {
                                let pattern = format!("${{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::to_string(val).unwrap_or_default(),
                                };
                                result = result.replace(&pattern, &replacement);
                                pos = 0; // Start over after replacement
                            } else {
                                pos = abs_end + 1; // Move past this pattern
                            }
                        } else {
                            break; // No closing brace found
                        }
                    }

                    Value::Static(serde_json::Value::String(result))
                } else {
                    value.clone()
                }
            }
            _ => 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> {
    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) => {
                // Evaluate binding against state using parsed path
                evaluate_binding(binding, state).unwrap_or(serde_json::Value::Null)
            }
            crate::ir::Value::TemplateString { template, bindings } => {
                // Interpolate all bindings in the template string
                let mut result = template.clone();
                for binding in bindings {
                    let binding_placeholder = format!("${{state.{}}}", binding.full_path());
                    let value = evaluate_binding(binding, state)
                        .map(|v| match v {
                            serde_json::Value::String(s) => s,
                            other => other.to_string(),
                        })
                        .unwrap_or_default();
                    result = result.replace(&binding_placeholder, &value);
                }
                serde_json::Value::String(result)
            }
            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 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");
    }
}