hypen-engine 0.4.46

//! Keyed child reconciliation using the LIS algorithm.
//!
//! When children carry stable keys, we can reorder them with minimal
//! DOM moves by computing the Longest Increasing Subsequence (LIS) of
//! old-to-new position mappings.

use super::diff::{create_tree, reconcile_node};
use super::{InstanceTree, Patch};
use crate::ir::{Element, NodeId};
use crate::reactive::DependencyGraph;
use indexmap::IndexMap;

/// Data sources type alias for readability
type DataSources = indexmap::IndexMap<String, serde_json::Value>;

/// 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.
pub(crate) 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,
    data_sources: Option<&DataSources>,
) -> 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, data_sources);
                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,
                    data_sources,
                )
            }
        } 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, data_sources);
                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,
                    data_sources,
                )
            }
        };

        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.
/// Uses the patience-sort / binary-search algorithm for O(n log n) performance.
/// Returns indices (into the original `positions` slice) of elements that are
/// already in correct relative order, minimizing DOM moves during reconciliation.
fn longest_increasing_subsequence(positions: &[Option<usize>]) -> Vec<usize> {
    // Extract valid positions with their original 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();
    }

    let n = valid.len();
    // `tails[i]` holds the index (into `valid`) of the smallest tail element for
    // an increasing subsequence of length `i + 1`.
    let mut tails: Vec<usize> = Vec::with_capacity(n);
    // `prev[i]` links back to the predecessor of valid[i] in the LIS.
    let mut prev: Vec<Option<usize>> = vec![None; n];

    for i in 0..n {
        let val = valid[i].1;
        // Binary search for the leftmost tail >= val
        let pos = tails.partition_point(|&t| valid[t].1 < val);

        if pos == tails.len() {
            tails.push(i);
        } else {
            tails[pos] = i;
        }

        if pos > 0 {
            prev[i] = Some(tails[pos - 1]);
        }
    }

    // Reconstruct: walk backwards from the last tail entry
    let mut result = Vec::with_capacity(tails.len());
    let mut idx = Some(*tails.last().unwrap());
    while let Some(i) = idx {
        result.push(valid[i].0);
        idx = prev[i];
    }
    result.reverse();

    result
}

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

    #[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,
            None,
        );

        // 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,
            None,
        );

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

    #[test]
    fn test_lis_large_sequence() {
        // Test that the O(n log n) algorithm handles longer sequences correctly
        // [3, 1, 4, 1, 5, 9, 2, 6] has LIS of length 4: 1,4,5,9 or 1,4,5,6
        let positions: Vec<Option<usize>> = vec![
            Some(3),
            Some(1),
            Some(4),
            Some(1),
            Some(5),
            Some(9),
            Some(2),
            Some(6),
        ];
        let lis = longest_increasing_subsequence(&positions);
        assert_eq!(lis.len(), 4);
        // Verify the subsequence is actually increasing
        let values: Vec<usize> = lis.iter().map(|&i| positions[i].unwrap()).collect();
        for w in values.windows(2) {
            assert!(w[0] < w[1], "LIS must be strictly increasing: {:?}", values);
        }
    }
}