euv-core 0.21.3

use super::*;

/// Returns the indices of a longest strictly increasing subsequence
/// of the input values, as positions in the input slice.
///
/// Uses the O(N log N) patience-sort variant: for each input value,
/// binary-search the smallest tail-end value that is greater-or-equal
/// to it (equal values REPLACE rather than extend, so equal-length
/// LIS choices resolve to the earliest possible positions in the
/// input). For inputs of length N the running time is
/// `O(N log N)` and the result has length `LIS(N)`.
///
/// The returned indices satisfy `result[0] < result[1] < ...` and
/// `keys[result[0]] < keys[result[1]] < ...`.
///
/// The "leftmost LIS" convention matters for the keyed-diff caller:
/// when walking the new children forward and skipping LIS positions,
/// the live DOM at each LIS position still holds the right child by
/// the time we get there (earlier non-LIS inserts anchor relative to
/// the LIS elements without disturbing them).
///
/// # Arguments
///
/// - `&[T]` - The values to compute the LIS over.
///
/// # Returns
///
/// - `Vec<usize>` - Indices into the input slice that form an LIS.
///   Empty when `keys.is_empty()`.
pub(crate) fn lis_indices<T: Ord>(keys: &[T]) -> Vec<usize> {
    let n: usize = keys.len();
    if n == 0 {
        return Vec::new();
    }
    let mut tails: Vec<usize> = Vec::with_capacity(n);
    let mut tail_min: Vec<&T> = Vec::with_capacity(n);
    let mut predecessors: Vec<usize> = vec![0_usize; n];
    for (i, key) in keys.iter().enumerate() {
        // Binary search for the first tail-end value `>` key (strict).
        // `binary_search` returns `Err(idx)` with the insertion point
        // when the value is absent; that insertion point is exactly
        // the position of the first tail-end `> key`. When the value
        // IS present at `Ok(idx)`, we replace the same-length slot
        // (ties go to the leftmost / earliest index in the LIS).
        // `tail_min` holds `&T`, so the search needle must also be `&T`.
        let pos: usize = match tail_min.binary_search(&key) {
            Ok(idx) => idx,
            Err(idx) => idx,
        };
        if pos == tails.len() {
            tails.push(i);
            tail_min.push(key);
        } else {
            tails[pos] = i;
            tail_min[pos] = key;
        }
        predecessors[i] = if pos == 0 { usize::MAX } else { tails[pos - 1] };
    }
    let mut result: Vec<usize> = Vec::with_capacity(tails.len());
    let mut k: usize = match tails.last() {
        Some(last) => *last,
        None => return result,
    };
    while k != usize::MAX {
        result.push(k);
        match predecessors.get(k) {
            Some(&next) if next != usize::MAX => k = next,
            _ => break,
        }
    }
    result.reverse();
    result
}

/// Returns the cached `Document` for the current page, falling back to
/// `window().document()` on the first call. `Document` is page-scoped (it
/// stays valid until the document is replaced), so a single resolved
/// reference is safe to reuse across the lifetime of an `euv-example`
/// mount. Subsequent calls just clone the cached handle, eliminating the
/// two JS-boundary crossings (`window()` + `document()`) every DOM node
/// creation used to pay.
///
/// OPT 8: per-page `Document` cache via `thread_local!`. The lazy
/// `OnceCell`-style fallback makes this safe even before
/// `App::mount` has finished initialising.
///
/// # Returns
///
/// - `Option<Document>` - `Some(...)` on success, `None` otherwise.
pub(crate) fn cached_document() -> Option<Document> {
    DOCUMENT_CACHE.with(|cell: &UnsafeCell<Option<Document>>| {
        let cached_ptr: *mut Option<Document> = cell.get();
        unsafe {
            if let Some(doc) = &*cached_ptr {
                return Some(doc.clone());
            }
        }
        let window_value: Window = window()?;
        let document: Document = window_value.document()?;
        DOCUMENT_CACHE.with(|cell: &UnsafeCell<Option<Document>>| unsafe {
            *cell.get() = Some(document.clone());
        });
        Some(document)
    })
}

/// Appends a sequence of pre-built DOM nodes to a parent element.
///
/// OPT 13: when the input contains two or more nodes, the writes are
/// funnelled through a `DocumentFragment` so the parent only sees a
/// single `append_child` call. The browser then performs one layout
/// invalidation for the whole batch instead of one per node — typically
/// a 2-10× wall-clock win on tree mounts with many siblings (e.g.
/// euv-example's 77-div initial render).
///
/// When the input has zero or one nodes the helper falls back to the
/// direct `append_child` path so the single-child case pays zero
/// fragment-allocation overhead.
///
/// Detached-parent guard: when `parent.is_connected()` is `false` (i.e.
/// the parent is being mounted from scratch and has not yet been grafted
/// into the live DOM), appending to a `DocumentFragment` only adds N+2
/// JS crossings (create + N×append + graft) without saving any layout
/// invalidations — the fragment and the parent are both detached, so
/// neither triggers reflow. In that case we loop-append directly and
/// save the +2 round-trips and the auxiliary `Vec<Node>`.
///
/// # Arguments
///
/// - `&Element` - The parent DOM element receiving the children.
/// - `impl IntoIterator<Item = Node>` - The DOM nodes to attach, in
///   their final sibling order.
///
/// # Returns
///
/// - `()` - The appends are best-effort; per-call JS errors are dropped
///   to match the previous per-node behaviour.
pub(crate) fn append_nodes(parent: &Element, nodes: impl IntoIterator<Item = Node>) {
    if !parent.is_connected() {
        for node in nodes {
            let _: Result<Node, JsValue> = parent.append_child(&node);
        }
        return;
    }
    let mut iter = nodes.into_iter();
    let Some(first) = iter.next() else {
        return;
    };
    let Some(second) = iter.next() else {
        let _: Result<Node, JsValue> = parent.append_child(&first);
        return;
    };
    // Two or more children: build a fragment, append every node into it,
    // then graft the fragment onto the parent in a single JS round-trip.
    let document: Document = match cached_document() {
        Some(doc) => doc,
        None => {
            // Without a Document we can't make a fragment — fall back
            // to per-node appends to preserve the old behaviour rather
            // than silently dropping children.
            let _: Result<Node, JsValue> = parent.append_child(&first);
            let _: Result<Node, JsValue> = parent.append_child(&second);
            for node in iter {
                let _: Result<Node, JsValue> = parent.append_child(&node);
            }
            return;
        }
    };
    let fragment: DocumentFragment = document.create_document_fragment();
    let _: Result<Node, JsValue> = fragment.append_child(&first);
    let _: Result<Node, JsValue> = fragment.append_child(&second);
    for node in iter {
        let _: Result<Node, JsValue> = fragment.append_child(&node);
    }
    let fragment_node: Node = fragment.into();
    let _: Result<Node, JsValue> = parent.append_child(&fragment_node);
}