cranpose_foundation/lazy/

lazy_list_scope.rs

//! DSL scope for building lazy list content.
//!
//! Provides [`LazyListScope`] trait and implementation for the ergonomic
//! `item {}` / `items {}` API used in `LazyColumn` and `LazyRow`.
//!
//! Based on JC's `LazyLayoutIntervalContent` pattern.

use std::{cell::RefCell, collections::HashMap, rc::Rc};

/// Key type for lazy list items.
///
/// Separates user-provided keys from default index-based keys to prevent collisions.
/// This matches JC's `getDefaultLazyLayoutKey()` pattern where a wrapper type
/// (`DefaultLazyKey`) ensures default keys never collide with user-provided keys.
///
/// # JC Reference
/// - `LazyLayoutIntervalContent.getKey()` returns `content.key?.invoke(localIndex) ?: getDefaultLazyLayoutKey(index)`
/// - `Lazy.android.kt` defines `DefaultLazyKey(index)` as a wrapper data class
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum LazyLayoutKey {
    /// User-provided key (from `scope.item(key: Some(k), ...)` or `scope.items(key: Some(|i| ...), ...)`)
    User(u64),
    /// Default key based on global index. Cannot collide with User keys due to enum separation.
    Index(usize),
}

impl LazyLayoutKey {
    const USER_TAG: u64 = 0b00 << 62;
    const INDEX_TAG: u64 = 0b01 << 62;
    const VALUE_MASK: u64 = (1u64 << 62) - 1;

    /// Converts to u64 for slot ID usage with guaranteed non-overlapping ranges.
    ///
    /// # Encoding
    /// Uses high 2 bits of the 64-bit slot ID as a type tag:
    /// - User keys: `0b00` tag + 62-bit value (range: 0x0000... - 0x3FFF...)
    /// - Index keys: `0b01` tag + 62-bit value (range: 0x4000... - 0x7FFF...)
    ///
    /// # ⚠️ Large Key Handling
    /// Values larger than 62 bits are **mixed down to 62 bits**. This avoids panics
    /// for extreme indices (e.g. `usize::MAX`) but introduces a small chance of
    /// collisions for out-of-range keys. Prefer keys that fit in 62 bits when
    /// you need guaranteed collision-free IDs.
    ///
    /// # Cross-Platform Safety
    /// The slot ID is always `u64` regardless of target platform.
    #[inline]
    pub fn to_slot_id(self) -> u64 {
        match self {
            LazyLayoutKey::User(k) => {
                let value = Self::normalize_value(k, "User");
                Self::USER_TAG | value
            }
            LazyLayoutKey::Index(i) => {
                let value = Self::normalize_value(i as u64, "Index");
                Self::INDEX_TAG | value
            }
        }
    }

    #[inline]
    fn normalize_value(value: u64, kind: &'static str) -> u64 {
        if value <= Self::VALUE_MASK {
            value
        } else {
            log::warn!(
                "LazyList {kind} key {value:#018x} exceeds 62 bits; mixing to 62 bits to avoid overflow"
            );
            Self::mix_to_value_bits(value)
        }
    }

    #[inline]
    fn mix_to_value_bits(mut value: u64) -> u64 {
        value ^= value >> 33;
        value = value.wrapping_mul(0xff51afd7ed558ccd);
        value ^= value >> 33;
        value = value.wrapping_mul(0xc4ceb9fe1a85ec53);
        value ^= value >> 33;
        value & Self::VALUE_MASK
    }

    /// Returns true if this is a user-provided key.
    #[inline]
    pub fn is_user_key(self) -> bool {
        matches!(self, LazyLayoutKey::User(_))
    }
}

#[doc(hidden)]
pub struct LazyScopeMarker;

/// A run of lazy items: how many, and optionally how they are identified and
/// reused.
///
/// A count converts into this on its own, so the ordinary list reads as
/// `scope.items(20, |index| ...)` — the shape Compose gets from default
/// arguments, which Rust does not have. A list whose contents move between
/// compositions names a key so item state follows the item rather than the
/// slot it happened to occupy:
///
/// ```rust,ignore
/// scope.items(LazyItems::new(rows.len()).key(|index| rows[index].id), |index| {
///     Row(&rows[index]);
/// });
/// ```
#[derive(Clone, Default)]
pub struct LazyItems {
    count: usize,
    key: Option<Rc<dyn Fn(usize) -> u64>>,
    content_type: Option<Rc<dyn Fn(usize) -> u64>>,
}

impl LazyItems {
    /// A run of `count` items with no key and no reuse class.
    pub fn new(count: usize) -> Self {
        Self {
            count,
            key: None,
            content_type: None,
        }
    }

    /// Gives each item a stable identity, so state, animations and scroll
    /// position follow the item when the list is reordered or edited.
    pub fn key(mut self, key: impl Fn(usize) -> u64 + 'static) -> Self {
        self.key = Some(Rc::new(key));
        self
    }

    /// Groups items into reuse classes, so a scrolling list recycles a row
    /// into another row of the same shape rather than rebuilding it.
    pub fn content_type(mut self, content_type: impl Fn(usize) -> u64 + 'static) -> Self {
        self.content_type = Some(Rc::new(content_type));
        self
    }

    /// How many items this run declares.
    pub fn count(&self) -> usize {
        self.count
    }

    /// The identity function, if the caller named one.
    pub fn key_fn(&self) -> Option<Rc<dyn Fn(usize) -> u64>> {
        self.key.clone()
    }

    /// The reuse-class function, if the caller named one.
    pub fn content_type_fn(&self) -> Option<Rc<dyn Fn(usize) -> u64>> {
        self.content_type.clone()
    }
}

impl From<usize> for LazyItems {
    fn from(count: usize) -> Self {
        Self::new(count)
    }
}

/// Receiver scope for lazy list content definition.
///
/// Used by `LazyColumn` and `LazyRow` to define list items.
/// Matches Jetpack Compose's `LazyListScope`.
///
/// # Example
///
/// ```rust,ignore
/// lazy_column(modifier, state, |scope| {
///     // Single item
///     scope.item_keyed(Some(0), None, || {
///         Text::new("Header")
///     });
///
///     // Multiple items
///     scope.items(data.len(), Some(|i| data[i].id), None, |i| {
///         Text::new(data[i].name.clone())
///     });
/// });
/// ```
pub trait LazyListScope {
    /// Adds one item.
    fn item<F>(&mut self, content: F)
    where
        F: Fn() + 'static,
    {
        self.item_keyed(None, None, content);
    }

    /// Adds one item with a stable identity and/or a reuse class.
    ///
    /// `key` makes item state follow the item across reorders; `content_type`
    /// groups it with the rows it may be recycled into.
    fn item_keyed<F>(&mut self, key: Option<u64>, content_type: Option<u64>, content: F)
    where
        F: Fn() + 'static;

    /// Adds a run of items.
    ///
    /// A count is enough for the ordinary list — `scope.items(20, |index| ...)`.
    /// Pass a [`LazyItems`] to name keys or reuse classes.
    fn items<I, F>(&mut self, items: I, item_content: F)
    where
        I: Into<LazyItems>,
        F: Fn(usize) + 'static;
}

/// Internal representation of a lazy list item interval.
///
/// Based on JC's `LazyLayoutIntervalContent.Interval`.
/// Uses Rc for shared ownership of closures (not Clone).
pub struct LazyListInterval {
    /// Start index of this interval in the total item list.
    pub start_index: usize,

    /// Number of items in this interval.
    pub count: usize,

    /// Key generator for items in this interval.
    /// Based on JC's `Interval.key: ((index: Int) -> Any)?`
    pub key: Option<Rc<dyn Fn(usize) -> u64>>,

    /// Content type generator for items in this interval.
    /// Based on JC's `Interval.type: ((index: Int) -> Any?)`
    pub content_type: Option<Rc<dyn Fn(usize) -> u64>>,

    /// Content generator for items in this interval.
    /// Takes the local index within the interval.
    pub content: Rc<dyn Fn(usize)>,
}

impl std::fmt::Debug for LazyListInterval {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("LazyListInterval")
            .field("start_index", &self.start_index)
            .field("count", &self.count)
            .finish_non_exhaustive()
    }
}

/// Builder that collects intervals during scope execution.
///
/// Based on JC's `LazyLayoutIntervalContent` with `IntervalList`.
pub struct LazyListIntervalContent {
    intervals: Vec<LazyListInterval>,
    total_count: usize,
    range_index: RefCell<Option<RangeKeyIndex>>,
}

/// The slot ids of one range of items mapped to their indices: the nearest
/// range around the viewport that lookups ask for, mapped once however many
/// keys a measure looks up in it and however long the list is.
struct RangeKeyIndex {
    range: std::ops::Range<usize>,
    indices: HashMap<u64, usize>,
}

impl LazyListIntervalContent {
    /// Creates a new empty interval content.
    pub fn new() -> Self {
        Self {
            intervals: Vec::new(),
            total_count: 0,
            range_index: RefCell::new(None),
        }
    }

    fn invalidate_cache(&self) {
        *self.range_index.borrow_mut() = None;
    }

    #[cfg(test)]
    fn mapped_keys(&self) -> usize {
        self.range_index
            .borrow()
            .as_ref()
            .map_or(0, |index| index.indices.len())
    }

    /// Returns the total number of items across all intervals.
    /// Matches JC's `LazyLayoutIntervalContent.itemCount`.
    pub fn item_count(&self) -> usize {
        self.total_count
    }

    /// Returns the intervals.
    pub fn intervals(&self) -> &[LazyListInterval] {
        &self.intervals
    }

    /// Gets the key for an item at the given global index.
    ///
    /// Returns a [`LazyLayoutKey`] that distinguishes between user-provided keys
    /// and default index-based keys to prevent collisions.
    ///
    /// Matches JC's `LazyLayoutIntervalContent.getKey(index)` pattern.
    pub fn get_key(&self, index: usize) -> LazyLayoutKey {
        if let Some((interval, local_index)) = self.find_interval(index)
            && let Some(key_fn) = &interval.key
        {
            return LazyLayoutKey::User(key_fn(local_index));
        }
        LazyLayoutKey::Index(index)
    }

    /// Gets the content type for an item at the given global index.
    /// Matches JC's `LazyLayoutIntervalContent.getContentType(index)`.
    pub fn get_content_type(&self, index: usize) -> Option<u64> {
        if let Some((interval, local_index)) = self.find_interval(index)
            && let Some(type_fn) = &interval.content_type
        {
            return Some(type_fn(local_index));
        }
        None
    }

    /// Invokes the content closure for an item at the given global index.
    ///
    /// Matches JC's `withInterval` pattern where block is called with
    /// local index and interval content.
    pub fn invoke_content(&self, index: usize) {
        if let Some((interval, local_index)) = self.find_interval(index) {
            (interval.content)(local_index);
        }
    }

    /// Executes a block with the interval containing the given global index.
    /// Matches JC's `withInterval(globalIndex, block)`.
    pub fn with_interval<T, F>(&self, global_index: usize, block: F) -> Option<T>
    where
        F: FnOnce(usize, &LazyListInterval) -> T,
    {
        self.find_interval(global_index)
            .map(|(interval, local_index)| block(local_index, interval))
    }

    /// Returns the index of an item with the given key, or None if not found.
    /// Matches JC's `LazyLayoutItemProvider.getIndex(key: Any): Int`.
    ///
    /// This is used for scroll position stability - when items are added/removed,
    /// the scroll position can be maintained by finding the new index of the
    /// item that was previously at the scroll position (identified by key).
    ///
    /// Uses cached HashMap for O(1) lookup when the list has <= 10000 items.
    /// For larger lists, use `get_index_by_key_in_range` with a `NearestRangeState`.
    #[must_use]
    pub fn get_index_by_key(&self, key: LazyLayoutKey) -> Option<usize> {
        let slot_id = key.to_slot_id();
        self.get_index_by_slot_id(slot_id)
    }

    /// Returns the index of an item with the given key, searching only within the range.
    /// Used with NearestRangeState for O(1) key lookup in large lists.
    pub fn get_index_by_key_in_range(
        &self,
        key: LazyLayoutKey,
        range: std::ops::Range<usize>,
    ) -> Option<usize> {
        self.get_index_by_slot_id_in_range(key.to_slot_id(), range)
    }

    /// Returns the index of an item with the given slot ID, or None if not found.
    ///
    /// Slot IDs are generated by `LazyLayoutKey::to_slot_id()`. This scans the
    /// whole list and keeps nothing: a list may hold a million items, and a map
    /// of every key would hold tens of megabytes. Lookups near the viewport
    /// belong to `get_index_by_slot_id_in_range`, which maps its range once.
    #[must_use]
    pub fn get_index_by_slot_id(&self, slot_id: u64) -> Option<usize> {
        (0..self.total_count).find(|&index| self.get_key(index).to_slot_id() == slot_id)
    }

    /// Returns the index of an item with the given slot ID, searching only
    /// within the range. The range's keys are mapped on the first lookup in it
    /// and kept until another range is asked for or the content changes.
    pub fn get_index_by_slot_id_in_range(
        &self,
        slot_id: u64,
        range: std::ops::Range<usize>,
    ) -> Option<usize> {
        let start = range.start.min(self.total_count);
        let range = start..range.end.clamp(start, self.total_count);
        let mut cached = self.range_index.borrow_mut();
        if cached.as_ref().is_none_or(|index| index.range != range) {
            let indices = range
                .clone()
                .map(|index| (self.get_key(index).to_slot_id(), index))
                .collect();
            *cached = Some(RangeKeyIndex { range, indices });
        }
        cached
            .as_ref()
            .and_then(|index| index.indices.get(&slot_id).copied())
    }

    fn find_interval(&self, index: usize) -> Option<(&LazyListInterval, usize)> {
        if self.intervals.is_empty() || index >= self.total_count {
            return None;
        }

        let pos = self
            .intervals
            .partition_point(|interval| interval.start_index + interval.count <= index);

        if pos < self.intervals.len() {
            let interval = &self.intervals[pos];
            if index >= interval.start_index && index < interval.start_index + interval.count {
                let local_index = index - interval.start_index;
                return Some((interval, local_index));
            }
        }
        None
    }
}

impl Default for LazyListIntervalContent {
    fn default() -> Self {
        Self::new()
    }
}

impl LazyListScope for LazyListIntervalContent {
    fn item_keyed<F>(&mut self, key: Option<u64>, content_type: Option<u64>, content: F)
    where
        F: Fn() + 'static,
    {
        self.invalidate_cache();
        let start_index = self.total_count;
        self.intervals.push(LazyListInterval {
            start_index,
            count: 1,
            key: key.map(|k| Rc::new(move |_| k) as Rc<dyn Fn(usize) -> u64>),
            content_type: content_type.map(|t| Rc::new(move |_| t) as Rc<dyn Fn(usize) -> u64>),
            content: Rc::new(move |_| content()),
        });
        self.total_count += 1;
    }

    fn items<I, F>(&mut self, items: I, item_content: F)
    where
        I: Into<LazyItems>,
        F: Fn(usize) + 'static,
    {
        let items = items.into();
        let count = items.count();
        if count == 0 {
            return;
        }

        self.invalidate_cache();
        let start_index = self.total_count;
        self.intervals.push(LazyListInterval {
            start_index,
            count,
            key: items.key_fn(),
            content_type: items.content_type_fn(),
            content: Rc::new(item_content),
        });
        self.total_count += count;
    }
}

use crate::lazy::item_provider::LazyLayoutItemProvider;

/// Implements [`LazyLayoutItemProvider`] to formalize the item factory contract.
/// This provides the same functionality as the existing methods but through
/// the standardized trait interface.
impl LazyLayoutItemProvider for LazyListIntervalContent {
    fn item_count(&self) -> usize {
        self.total_count
    }

    fn get_key(&self, index: usize) -> u64 {
        LazyListIntervalContent::get_key(self, index).to_slot_id()
    }

    fn get_content_type(&self, index: usize) -> Option<u64> {
        LazyListIntervalContent::get_content_type(self, index)
    }

    fn get_index(&self, key: u64) -> Option<usize> {
        self.get_index_by_slot_id(key)
    }
}

/// Extension trait for adding convenience methods to [`LazyListScope`].
///
/// Provides ergonomic APIs for common use cases with different performance tradeoffs:
///
/// | Method | Upfront Cost | Use Case |
/// |--------|--------------|----------|
/// | `items_slice` | O(n) copy | Convenience, small data |
/// | `items_slice_rc` | O(1) | Data already in `Rc<[T]>` |
/// | `items_with_provider` | O(1) | Lazy on-demand access |
pub trait LazyListScopeExt: LazyListScope {
    /// Adds items from a slice with an item-aware content closure.
    ///
    /// # ⚠️ Performance Warning
    ///
    /// **This method performs an O(n) allocation and copy of the entire slice upfront.**
    ///
    /// This copy is required to satisfy Rust's `'static` closure requirements for
    /// the lazy list item factory. For small lists (< 1000 items) this is typically
    /// acceptable, but for large datasets consider these alternatives:
    ///
    /// | Alternative | When to Use |
    /// |-------------|-------------|
    /// | `items_slice_rc` | Data is already in `Rc<[T]>` - **zero copy** |
    /// | `items_vec` | Data is in a `Vec<T>` you can give up ownership of - **efficient** |
    /// | `items_with_provider` | Need lazy on-demand access - **zero copy** |
    ///
    /// After the initial copy, the closure captures a reference-counted pointer,
    /// so subsequent Rc clones are O(1).
    ///
    /// # Example
    ///
    /// ```rust,ignore
    /// let data = vec!["Apple", "Banana", "Cherry"];
    /// scope.items_slice(&data, |item| {
    ///     Text(item.to_string(), Modifier::empty());
    /// });
    /// ```
    fn items_slice<T, F>(&mut self, items: &[T], item_content: F)
    where
        T: Clone + 'static,
        F: Fn(&T) + 'static,
    {
        let items_rc: Rc<[T]> = items.to_vec().into();
        self.items(items.len(), move |index| {
            if let Some(item) = items_rc.get(index) {
                item_content(item);
            }
        });
    }

    /// Adds items from a `Vec<T>`, taking ownership.
    ///
    /// **Efficient ownership transfer**: Uses `Rc::from(vec)` which avoids copying
    /// elements if the allocation fits (or does a simple realloc).
    /// Use this when you have a `Vec` and want to pass it to the list.
    ///
    /// # Example
    ///
    /// ```rust,ignore
    /// let data = vec!["Apple".to_string(), "Banana".to_string()];
    /// scope.items_vec(data, |item| {
    ///     Text(item.to_string(), Modifier::empty());
    /// });
    /// ```
    fn items_vec<T, F>(&mut self, items: Vec<T>, item_content: F)
    where
        T: 'static,
        F: Fn(&T) + 'static,
    {
        let len = items.len();
        let items_rc: Rc<[T]> = Rc::from(items);
        self.items(len, move |index| {
            if let Some(item) = items_rc.get(index) {
                item_content(item);
            }
        });
    }

    /// Adds indexed items from a collection (Slice, Vec, or Rc).
    ///
    /// This method is generic over the input type `L` which must be convertible to `Rc<[T]>`.
    /// This allows for efficient ownership transfer (zero-copy for `Vec` and `Rc`) or
    /// convenient usage with slices (which will perform a copy).
    ///
    /// # Performance Note
    ///
    /// - **`Vec<T>`**: Zero-copy (ownership transfer). Efficient.
    /// - **`Rc<[T]>`**: Zero-copy (ownership transfer). Efficient.
    /// - **`&[T]`**: **O(N) copy**. Convenient for small lists, but avoid for large datasets.
    ///
    /// # Example
    ///
    /// ```rust,ignore
    /// // Efficient Vec usage (zero-copy)
    /// let data = vec!["Apple".to_string(), "Banana".to_string()];
    /// scope.items_indexed(data, |index, item| { ... });
    ///
    /// // Slice usage (performs copy)
    /// let data_slice = &["Apple", "Banana"];
    /// scope.items_indexed(data_slice, |index, item| { ... });
    /// ```
    fn items_indexed<T, L, F>(&mut self, items: L, item_content: F)
    where
        T: 'static,
        L: Into<Rc<[T]>>,
        F: Fn(usize, &T) + 'static,
    {
        let items_rc: Rc<[T]> = items.into();
        self.items(items_rc.len(), move |index| {
            if let Some(item) = items_rc.get(index) {
                item_content(index, item);
            }
        });
    }

    /// Adds items from a pre-existing `Rc<[T]>` without cloning.
    ///
    /// **Zero-copy optimization**: If you already have your data in an `Rc<[T]>`,
    /// use this method to avoid the O(n) clone that `items_slice` performs.
    ///
    /// # Example
    ///
    /// ```rust,ignore
    /// let data: Rc<[String]> = Rc::from(vec!["Apple".into(), "Banana".into()]);
    /// scope.items_slice_rc(Rc::clone(&data), |item| {
    ///     Text(item.to_string(), Modifier::empty());
    /// });
    /// ```
    fn items_slice_rc<T, F>(&mut self, items: Rc<[T]>, item_content: F)
    where
        T: 'static,
        F: Fn(&T) + 'static,
    {
        let len = items.len();
        self.items(len, move |index| {
            if let Some(item) = items.get(index) {
                item_content(item);
            }
        });
    }

    /// Adds indexed items from a pre-existing `Rc<[T]>` without cloning.
    ///
    /// **Zero-copy optimization**: If you already have your data in an `Rc<[T]>`,
    /// use this method to avoid the O(n) clone that `items_indexed` performs.
    ///
    /// # Example
    ///
    /// ```rust,ignore
    /// let data: Rc<[String]> = Rc::from(vec!["Apple".into(), "Banana".into()]);
    /// scope.items_indexed_rc(Rc::clone(&data), |index, item| {
    ///     Text(format!("{}. {}", index + 1, item), Modifier::empty());
    /// });
    /// ```
    fn items_indexed_rc<T, F>(&mut self, items: Rc<[T]>, item_content: F)
    where
        T: 'static,
        F: Fn(usize, &T) + 'static,
    {
        let len = items.len();
        self.items(len, move |index| {
            if let Some(item) = items.get(index) {
                item_content(index, item);
            }
        });
    }

    /// Adds items using a provider function for on-demand data access.
    ///
    /// **Zero-allocation pattern**: Instead of storing data, the provider function
    /// is called lazily when each item is rendered. This avoids any upfront
    /// allocation or cloning.
    ///
    /// The provider should return `Some(T)` for valid indices and `None` for
    /// out-of-bounds access. The item is passed by value to the content closure.
    ///
    /// # Example
    ///
    /// ```rust,ignore
    /// let data = vec!["Apple", "Banana", "Cherry"];
    /// scope.items_with_provider(
    ///     data.len(),
    ///     move |index| data.get(index).copied(),
    ///     |item| {
    ///         Text(item.to_string(), Modifier::empty());
    ///     },
    /// );
    /// ```
    fn items_with_provider<T, P, F>(&mut self, count: usize, provider: P, item_content: F)
    where
        T: 'static,
        P: Fn(usize) -> Option<T> + 'static,
        F: Fn(T) + 'static,
    {
        self.items(count, move |index| {
            if let Some(item) = provider(index) {
                item_content(item);
            }
        });
    }

    /// Adds indexed items using a provider function for on-demand data access.
    ///
    /// **Zero-allocation pattern**: Instead of storing data, the provider function
    /// is called lazily when each item is rendered. This avoids any upfront
    /// allocation or cloning.
    ///
    /// # Example
    ///
    /// ```rust,ignore
    /// let data = vec!["Apple", "Banana", "Cherry"];
    /// scope.items_indexed_with_provider(
    ///     data.len(),
    ///     move |index| data.get(index).copied(),
    ///     |index, item| {
    ///         Text(format!("{}. {}", index + 1, item), Modifier::empty());
    ///     },
    /// );
    /// ```
    fn items_indexed_with_provider<T, P, F>(&mut self, count: usize, provider: P, item_content: F)
    where
        T: 'static,
        P: Fn(usize) -> Option<T> + 'static,
        F: Fn(usize, T) + 'static,
    {
        self.items(count, move |index| {
            if let Some(item) = provider(index) {
                item_content(index, item);
            }
        });
    }
}

impl<T: LazyListScope + ?Sized> LazyListScopeExt for T {}

#[cfg(test)]
#[path = "tests/lazy_list_scope_tests.rs"]
mod tests;