Skip to main content

sui_widgets/
collection.rs

1use crate::draw::inset_rect;
2use std::{
3    cell::RefCell,
4    collections::{HashMap, HashSet, VecDeque},
5    fmt,
6    hash::Hash,
7    ops::Range,
8    rc::Rc,
9    sync::{
10        Arc, RwLock,
11        atomic::{AtomicU64, Ordering},
12    },
13};
14
15use sui_core::{
16    Event, InvalidationKind, InvalidationRequest, InvalidationTarget, KeyState, Point,
17    PointerButton, PointerEvent, PointerEventKind, PointerKind, Rect, ScrollDelta, SemanticsAction,
18    SemanticsActionRequest, SemanticsNode, SemanticsRole, SemanticsValue, Size, Vector, WidgetId,
19};
20use sui_layout::{Constraints, Padding as Insets};
21use sui_reactive::{Observable, Observer, Signal, SourceId, Subscription};
22use sui_runtime::{
23    ArrangeCtx, EventCtx, EventPhase, LayerOptions, MeasureCtx, PaintBoundaryMode, PaintCtx,
24    SemanticsCtx, Widget, WidgetDiagnosticsCtx, WidgetPod, WidgetPodMutVisitor, WidgetPodVisitor,
25};
26use sui_scene::LayerCompositionMode;
27
28use crate::{
29    DefaultTheme,
30    containers::{
31        ScrollAxes, ScrollBars, ScrollInvalidationCtx, ScrollState, ScrollWidgetCtx,
32        request_scroll_bar_refresh,
33    },
34    data::{draw_surface, paint_data_row_state},
35};
36
37const COLLECTION_JOURNAL_LIMIT: usize = 512;
38const DEFAULT_CACHE_CAPACITY: usize = 64;
39const DEFAULT_OVERSCAN_VIEWPORTS: f32 = 0.75;
40const DEFAULT_UNBOUNDED_VIEWPORT_HEIGHT: f32 = 420.0;
41const FOLLOW_END_THRESHOLD: f32 = 24.0;
42const SYNTHETIC_COLLECTION_ITEM_TAG: u64 = 6_u64 << 60;
43
44static NEXT_COLLECTION_ITEM_ID: AtomicU64 = AtomicU64::new(1);
45
46/// Incremental mutation accepted by [`VirtualCollectionModel`].
47#[derive(Clone, Debug, PartialEq)]
48pub enum CollectionChange<K, T> {
49    Insert { index: usize, items: Vec<(K, T)> },
50    Remove { keys: Vec<K> },
51    Move { key: K, index: usize },
52    Update { key: K, item: T },
53    Reset { items: Vec<(K, T)> },
54}
55
56/// Key-only change journal consumed by virtual collection widgets.
57#[derive(Clone, Debug, PartialEq, Eq)]
58pub enum CollectionDelta<K> {
59    Inserted { index: usize, keys: Vec<K> },
60    Removed { keys: Vec<K> },
61    Moved { key: K, index: usize },
62    Updated { key: K },
63}
64
65/// Result of asking a collection source for changes after a known revision.
66#[derive(Clone, Debug, PartialEq, Eq)]
67pub enum CollectionSync<K> {
68    Unchanged {
69        revision: u64,
70    },
71    Incremental {
72        revision: u64,
73        changes: Vec<CollectionDelta<K>>,
74    },
75    Reset {
76        revision: u64,
77        keys: Vec<K>,
78    },
79}
80
81/// Describes the loaded slice of a potentially larger collection.
82///
83/// Indices are zero-based and `loaded_range` is expressed in dataset space,
84/// not in the source's local `keys()` vector. A complete in-memory collection
85/// therefore uses `0..len`. Windowed sources can report, for example,
86/// `400..800` with a larger `total_count` while exposing 400 loaded keys.
87#[derive(Clone, Debug, PartialEq, Eq)]
88pub struct CollectionWindow {
89    pub loaded_range: Range<usize>,
90    pub total_count: Option<usize>,
91    pub has_before: bool,
92    pub has_after: bool,
93}
94
95impl CollectionWindow {
96    pub fn complete(count: usize) -> Self {
97        Self {
98            loaded_range: 0..count,
99            total_count: Some(count),
100            has_before: false,
101            has_after: false,
102        }
103    }
104
105    pub fn loaded(
106        loaded_range: Range<usize>,
107        total_count: Option<usize>,
108        has_before: bool,
109        has_after: bool,
110    ) -> Self {
111        Self {
112            loaded_range,
113            total_count,
114            has_before,
115            has_after,
116        }
117    }
118
119    pub fn loaded_count(&self) -> usize {
120        self.loaded_range
121            .end
122            .saturating_sub(self.loaded_range.start)
123    }
124
125    pub(crate) fn normalized_for_loaded_count(mut self, loaded_count: usize) -> Self {
126        self.loaded_range.end = self.loaded_range.start.saturating_add(loaded_count);
127        if let Some(total_count) = &mut self.total_count {
128            *total_count = (*total_count).max(self.loaded_range.end);
129        }
130        self
131    }
132}
133
134impl Default for CollectionWindow {
135    fn default() -> Self {
136        Self::complete(0)
137    }
138}
139
140#[derive(Clone, Debug, PartialEq, Eq)]
141pub enum CollectionModelError {
142    DuplicateKey,
143    MissingKey,
144    IndexOutOfBounds { index: usize, len: usize },
145}
146
147impl fmt::Display for CollectionModelError {
148    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
149        match self {
150            Self::DuplicateKey => formatter.write_str("collection keys must be unique"),
151            Self::MissingKey => formatter.write_str("collection key was not found"),
152            Self::IndexOutOfBounds { index, len } => {
153                write!(formatter, "collection index {index} exceeds length {len}")
154            }
155        }
156    }
157}
158
159impl std::error::Error for CollectionModelError {}
160
161/// Architecture-neutral data source consumed by [`VirtualList`].
162///
163/// Sources without an incremental journal may always return
164/// [`CollectionSync::Reset`]. The default [`VirtualCollectionModel`] keeps a
165/// bounded key-only journal so normal insert, remove, move, and update
166/// operations do not require rebuilding collection metrics.
167pub trait VirtualCollectionSource<K, T>: Observable<u64> {
168    fn revision(&self) -> u64;
169    fn keys(&self) -> Vec<K>;
170    fn item(&self, key: &K) -> Option<T>;
171    fn changes_since(&self, revision: u64) -> CollectionSync<K>;
172
173    fn window(&self) -> CollectionWindow {
174        CollectionWindow::complete(self.keys().len())
175    }
176}
177
178#[derive(Clone)]
179struct CollectionJournalEntry<K> {
180    revision: u64,
181    delta: Option<CollectionDelta<K>>,
182    reset: bool,
183}
184
185struct CollectionModelInner<K, T> {
186    entries: Vec<(K, T)>,
187    index_by_key: HashMap<K, usize>,
188    revision: u64,
189    journal: VecDeque<CollectionJournalEntry<K>>,
190}
191
192/// Cloneable observable collection with stable keys and incremental changes.
193pub struct VirtualCollectionModel<K, T> {
194    inner: Arc<RwLock<CollectionModelInner<K, T>>>,
195    revision: Signal<u64>,
196}
197
198impl<K, T> Clone for VirtualCollectionModel<K, T> {
199    fn clone(&self) -> Self {
200        Self {
201            inner: Arc::clone(&self.inner),
202            revision: self.revision.clone(),
203        }
204    }
205}
206
207impl<K, T> fmt::Debug for VirtualCollectionModel<K, T>
208where
209    K: fmt::Debug,
210    T: fmt::Debug,
211{
212    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
213        let inner = self
214            .inner
215            .read()
216            .unwrap_or_else(std::sync::PoisonError::into_inner);
217        formatter
218            .debug_struct("VirtualCollectionModel")
219            .field("entries", &inner.entries)
220            .field("revision", &inner.revision)
221            .finish()
222    }
223}
224
225impl<K, T> VirtualCollectionModel<K, T>
226where
227    K: Clone + Eq + Hash,
228    T: Clone + PartialEq,
229{
230    pub fn new() -> Self {
231        Self::named("Virtual collection")
232    }
233
234    pub fn named(name: impl Into<Arc<str>>) -> Self {
235        Self {
236            inner: Arc::new(RwLock::new(CollectionModelInner {
237                entries: Vec::new(),
238                index_by_key: HashMap::new(),
239                revision: 0,
240                journal: VecDeque::new(),
241            })),
242            revision: Signal::named(name, 0),
243        }
244    }
245
246    pub fn from_items(
247        name: impl Into<Arc<str>>,
248        items: impl IntoIterator<Item = (K, T)>,
249    ) -> Result<Self, CollectionModelError> {
250        let model = Self::named(name);
251        model.apply(CollectionChange::Reset {
252            items: items.into_iter().collect(),
253        })?;
254        Ok(model)
255    }
256
257    pub fn len(&self) -> usize {
258        self.inner
259            .read()
260            .unwrap_or_else(std::sync::PoisonError::into_inner)
261            .entries
262            .len()
263    }
264
265    pub fn is_empty(&self) -> bool {
266        self.len() == 0
267    }
268
269    pub fn append(&self, key: K, item: T) -> Result<bool, CollectionModelError> {
270        let index = self.len();
271        self.apply(CollectionChange::Insert {
272            index,
273            items: vec![(key, item)],
274        })
275    }
276
277    pub fn prepend(
278        &self,
279        items: impl IntoIterator<Item = (K, T)>,
280    ) -> Result<bool, CollectionModelError> {
281        self.apply(CollectionChange::Insert {
282            index: 0,
283            items: items.into_iter().collect(),
284        })
285    }
286
287    pub fn remove(&self, key: K) -> Result<bool, CollectionModelError> {
288        self.apply(CollectionChange::Remove { keys: vec![key] })
289    }
290
291    pub fn update(&self, key: K, item: T) -> Result<bool, CollectionModelError> {
292        self.apply(CollectionChange::Update { key, item })
293    }
294
295    pub fn move_to(&self, key: K, index: usize) -> Result<bool, CollectionModelError> {
296        self.apply(CollectionChange::Move { key, index })
297    }
298
299    pub fn replace(
300        &self,
301        items: impl IntoIterator<Item = (K, T)>,
302    ) -> Result<bool, CollectionModelError> {
303        self.apply(CollectionChange::Reset {
304            items: items.into_iter().collect(),
305        })
306    }
307
308    pub fn apply(&self, change: CollectionChange<K, T>) -> Result<bool, CollectionModelError> {
309        let next_revision = {
310            let mut inner = self
311                .inner
312                .write()
313                .unwrap_or_else(std::sync::PoisonError::into_inner);
314
315            let journal = match change {
316                CollectionChange::Insert { index, items } => {
317                    if index > inner.entries.len() {
318                        return Err(CollectionModelError::IndexOutOfBounds {
319                            index,
320                            len: inner.entries.len(),
321                        });
322                    }
323                    if items.is_empty() {
324                        return Ok(false);
325                    }
326                    let mut inserted = HashSet::with_capacity(items.len());
327                    if items.iter().any(|(key, _)| {
328                        !inserted.insert(key.clone()) || inner.index_by_key.contains_key(key)
329                    }) {
330                        return Err(CollectionModelError::DuplicateKey);
331                    }
332                    let keys = items.iter().map(|(key, _)| key.clone()).collect::<Vec<_>>();
333                    inner.entries.splice(index..index, items);
334                    // Appends leave all existing indices intact. Middle inserts
335                    // only shift the suffix; never rebuild the unchanged prefix.
336                    Self::reindex_from(&mut inner, index);
337                    CollectionJournalEntry {
338                        revision: 0,
339                        delta: Some(CollectionDelta::Inserted { index, keys }),
340                        reset: false,
341                    }
342                }
343                CollectionChange::Remove { keys } => {
344                    if keys.is_empty() {
345                        return Ok(false);
346                    }
347                    let unique = keys.iter().cloned().collect::<HashSet<_>>();
348                    if unique.len() != keys.len() {
349                        return Err(CollectionModelError::DuplicateKey);
350                    }
351                    if keys.iter().any(|key| !inner.index_by_key.contains_key(key)) {
352                        return Err(CollectionModelError::MissingKey);
353                    }
354                    inner.entries.retain(|(key, _)| !unique.contains(key));
355                    Self::reindex(&mut inner);
356                    CollectionJournalEntry {
357                        revision: 0,
358                        delta: Some(CollectionDelta::Removed { keys }),
359                        reset: false,
360                    }
361                }
362                CollectionChange::Move { key, index } => {
363                    let Some(from) = inner.index_by_key.get(&key).copied() else {
364                        return Err(CollectionModelError::MissingKey);
365                    };
366                    let target_len = inner.entries.len().saturating_sub(1);
367                    if index > target_len {
368                        return Err(CollectionModelError::IndexOutOfBounds {
369                            index,
370                            len: target_len,
371                        });
372                    }
373                    if from == index {
374                        return Ok(false);
375                    }
376                    let entry = inner.entries.remove(from);
377                    inner.entries.insert(index, entry);
378                    Self::reindex(&mut inner);
379                    CollectionJournalEntry {
380                        revision: 0,
381                        delta: Some(CollectionDelta::Moved { key, index }),
382                        reset: false,
383                    }
384                }
385                CollectionChange::Update { key, item } => {
386                    let Some(index) = inner.index_by_key.get(&key).copied() else {
387                        return Err(CollectionModelError::MissingKey);
388                    };
389                    if inner.entries[index].1 == item {
390                        return Ok(false);
391                    }
392                    inner.entries[index].1 = item;
393                    CollectionJournalEntry {
394                        revision: 0,
395                        delta: Some(CollectionDelta::Updated { key }),
396                        reset: false,
397                    }
398                }
399                CollectionChange::Reset { items } => {
400                    let mut keys = HashSet::with_capacity(items.len());
401                    if items.iter().any(|(key, _)| !keys.insert(key.clone())) {
402                        return Err(CollectionModelError::DuplicateKey);
403                    }
404                    if inner.entries == items {
405                        return Ok(false);
406                    }
407                    inner.entries = items;
408                    Self::reindex(&mut inner);
409                    CollectionJournalEntry {
410                        revision: 0,
411                        delta: None,
412                        reset: true,
413                    }
414                }
415            };
416
417            inner.revision = inner.revision.wrapping_add(1);
418            let revision = inner.revision;
419            inner.journal.push_back(CollectionJournalEntry {
420                revision,
421                ..journal
422            });
423            while inner.journal.len() > COLLECTION_JOURNAL_LIMIT {
424                inner.journal.pop_front();
425            }
426            revision
427        };
428
429        let _ = self.revision.set(next_revision);
430        Ok(true)
431    }
432
433    fn reindex(inner: &mut CollectionModelInner<K, T>) {
434        inner.index_by_key.clear();
435        Self::reindex_from(inner, 0);
436    }
437
438    fn reindex_from(inner: &mut CollectionModelInner<K, T>, start: usize) {
439        inner.index_by_key.extend(
440            inner
441                .entries
442                .iter()
443                .enumerate()
444                .skip(start)
445                .map(|(index, (key, _))| (key.clone(), index)),
446        );
447    }
448}
449
450impl<K, T> Default for VirtualCollectionModel<K, T>
451where
452    K: Clone + Eq + Hash,
453    T: Clone + PartialEq,
454{
455    fn default() -> Self {
456        Self::new()
457    }
458}
459
460impl<K, T> Observable<u64> for VirtualCollectionModel<K, T>
461where
462    K: Clone + Eq + Hash + 'static,
463    T: Clone + PartialEq + 'static,
464{
465    fn source_id(&self) -> SourceId {
466        self.revision.source_id()
467    }
468
469    fn source_name(&self) -> Arc<str> {
470        self.revision.source_name()
471    }
472
473    fn get(&self) -> u64 {
474        self.revision.get()
475    }
476
477    fn subscribe(&self, observer: Observer) -> Subscription {
478        self.revision.subscribe(observer)
479    }
480}
481
482impl<K, T> VirtualCollectionSource<K, T> for VirtualCollectionModel<K, T>
483where
484    K: Clone + Eq + Hash + 'static,
485    T: Clone + PartialEq + 'static,
486{
487    fn revision(&self) -> u64 {
488        self.inner
489            .read()
490            .unwrap_or_else(std::sync::PoisonError::into_inner)
491            .revision
492    }
493
494    fn keys(&self) -> Vec<K> {
495        self.inner
496            .read()
497            .unwrap_or_else(std::sync::PoisonError::into_inner)
498            .entries
499            .iter()
500            .map(|(key, _)| key.clone())
501            .collect()
502    }
503
504    fn item(&self, key: &K) -> Option<T> {
505        let inner = self
506            .inner
507            .read()
508            .unwrap_or_else(std::sync::PoisonError::into_inner);
509        inner
510            .index_by_key
511            .get(key)
512            .and_then(|index| inner.entries.get(*index))
513            .map(|(_, item)| item.clone())
514    }
515
516    fn window(&self) -> CollectionWindow {
517        CollectionWindow::complete(self.len())
518    }
519
520    fn changes_since(&self, revision: u64) -> CollectionSync<K> {
521        let inner = self
522            .inner
523            .read()
524            .unwrap_or_else(std::sync::PoisonError::into_inner);
525        if revision == inner.revision {
526            return CollectionSync::Unchanged {
527                revision: inner.revision,
528            };
529        }
530
531        let Some(oldest) = inner.journal.front().map(|entry| entry.revision) else {
532            return CollectionSync::Reset {
533                revision: inner.revision,
534                keys: inner.entries.iter().map(|(key, _)| key.clone()).collect(),
535            };
536        };
537        if revision.wrapping_add(1) < oldest {
538            return CollectionSync::Reset {
539                revision: inner.revision,
540                keys: inner.entries.iter().map(|(key, _)| key.clone()).collect(),
541            };
542        }
543
544        let entries = inner
545            .journal
546            .iter()
547            .filter(|entry| entry.revision > revision)
548            .collect::<Vec<_>>();
549        if entries.iter().any(|entry| entry.reset) {
550            return CollectionSync::Reset {
551                revision: inner.revision,
552                keys: inner.entries.iter().map(|(key, _)| key.clone()).collect(),
553            };
554        }
555
556        CollectionSync::Incremental {
557            revision: inner.revision,
558            changes: entries
559                .into_iter()
560                .filter_map(|entry| entry.delta.clone())
561                .collect(),
562        }
563    }
564}
565
566type ExtentLink = Option<Box<ExtentNode>>;
567
568struct ExtentNode {
569    extent: f32,
570    priority: u64,
571    len: usize,
572    sum: f32,
573    left: ExtentLink,
574    right: ExtentLink,
575}
576
577impl ExtentNode {
578    fn new(extent: f32, priority: u64) -> Box<Self> {
579        Box::new(Self {
580            extent: extent.max(0.0),
581            priority,
582            len: 1,
583            sum: extent.max(0.0),
584            left: None,
585            right: None,
586        })
587    }
588
589    fn update(&mut self) {
590        self.len = 1 + link_len(&self.left) + link_len(&self.right);
591        self.sum = self.extent + link_sum(&self.left) + link_sum(&self.right);
592    }
593}
594
595fn link_len(link: &ExtentLink) -> usize {
596    link.as_ref().map_or(0, |node| node.len)
597}
598
599fn link_sum(link: &ExtentLink) -> f32 {
600    link.as_ref().map_or(0.0, |node| node.sum)
601}
602
603fn split_extent(root: ExtentLink, left_len: usize) -> (ExtentLink, ExtentLink) {
604    let Some(mut root) = root else {
605        return (None, None);
606    };
607    let root_left_len = link_len(&root.left);
608    if left_len <= root_left_len {
609        let (left, right) = split_extent(root.left.take(), left_len);
610        root.left = right;
611        root.update();
612        (left, Some(root))
613    } else {
614        let (left, right) = split_extent(
615            root.right.take(),
616            left_len.saturating_sub(root_left_len + 1),
617        );
618        root.right = left;
619        root.update();
620        (Some(root), right)
621    }
622}
623
624fn merge_extent(left: ExtentLink, right: ExtentLink) -> ExtentLink {
625    match (left, right) {
626        (None, right) => right,
627        (left, None) => left,
628        (Some(mut left), Some(mut right)) => {
629            if left.priority <= right.priority {
630                left.right = merge_extent(left.right.take(), Some(right));
631                left.update();
632                Some(left)
633            } else {
634                right.left = merge_extent(Some(left), right.left.take());
635                right.update();
636                Some(right)
637            }
638        }
639    }
640}
641
642/// Variable-height prefix-sum index used by virtual collection policies.
643///
644/// It supports offset lookup, prefix sums, insertion, removal, movement, and
645/// extent correction in expected logarithmic time.
646#[derive(Default)]
647pub struct CollectionExtentIndex {
648    root: ExtentLink,
649    next_priority: u64,
650}
651
652impl fmt::Debug for CollectionExtentIndex {
653    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
654        formatter
655            .debug_struct("CollectionExtentIndex")
656            .field("len", &self.len())
657            .field("total", &self.total())
658            .finish()
659    }
660}
661
662impl CollectionExtentIndex {
663    pub const fn new() -> Self {
664        Self {
665            root: None,
666            next_priority: 0,
667        }
668    }
669
670    pub fn len(&self) -> usize {
671        link_len(&self.root)
672    }
673
674    pub fn is_empty(&self) -> bool {
675        self.root.is_none()
676    }
677
678    pub fn total(&self) -> f32 {
679        link_sum(&self.root)
680    }
681
682    pub fn clear(&mut self) {
683        self.root = None;
684    }
685
686    pub fn rebuild(&mut self, extents: impl IntoIterator<Item = f32>) {
687        self.clear();
688        for extent in extents {
689            self.insert(self.len(), extent);
690        }
691    }
692
693    pub fn insert(&mut self, index: usize, extent: f32) {
694        let index = index.min(self.len());
695        let priority = splitmix64(self.next_priority);
696        self.next_priority = self.next_priority.wrapping_add(1);
697        let (left, right) = split_extent(self.root.take(), index);
698        self.root = merge_extent(
699            merge_extent(left, Some(ExtentNode::new(extent, priority))),
700            right,
701        );
702    }
703
704    pub fn insert_many(&mut self, index: usize, extents: impl IntoIterator<Item = f32>) {
705        let index = index.min(self.len());
706        for (offset, extent) in extents.into_iter().enumerate() {
707            self.insert(index + offset, extent);
708        }
709    }
710
711    pub fn remove(&mut self, index: usize) -> Option<f32> {
712        if index >= self.len() {
713            return None;
714        }
715        let (left, rest) = split_extent(self.root.take(), index);
716        let (removed, right) = split_extent(rest, 1);
717        self.root = merge_extent(left, right);
718        removed.map(|node| node.extent)
719    }
720
721    pub fn move_item(&mut self, from: usize, to: usize) -> bool {
722        if from >= self.len() || to >= self.len() || from == to {
723            return false;
724        }
725        let Some(extent) = self.remove(from) else {
726            return false;
727        };
728        self.insert(to, extent);
729        true
730    }
731
732    pub fn update(&mut self, index: usize, extent: f32) -> bool {
733        fn update_at(node: &mut ExtentLink, index: usize, extent: f32) -> bool {
734            let Some(node) = node else {
735                return false;
736            };
737            let left_len = link_len(&node.left);
738            let changed = if index < left_len {
739                update_at(&mut node.left, index, extent)
740            } else if index == left_len {
741                let extent = extent.max(0.0);
742                if (node.extent - extent).abs() <= f32::EPSILON {
743                    false
744                } else {
745                    node.extent = extent;
746                    true
747                }
748            } else {
749                update_at(&mut node.right, index - left_len - 1, extent)
750            };
751            if changed {
752                node.update();
753            }
754            changed
755        }
756
757        update_at(&mut self.root, index, extent)
758    }
759
760    pub fn extent(&self, index: usize) -> Option<f32> {
761        let mut node = self.root.as_deref();
762        let mut index = index;
763        while let Some(current) = node {
764            let left_len = link_len(&current.left);
765            if index < left_len {
766                node = current.left.as_deref();
767            } else if index == left_len {
768                return Some(current.extent);
769            } else {
770                index -= left_len + 1;
771                node = current.right.as_deref();
772            }
773        }
774        None
775    }
776
777    pub fn offset_of(&self, index: usize) -> f32 {
778        fn prefix(node: &ExtentLink, index: usize) -> f32 {
779            let Some(node) = node else {
780                return 0.0;
781            };
782            let left_len = link_len(&node.left);
783            if index <= left_len {
784                prefix(&node.left, index)
785            } else {
786                link_sum(&node.left) + node.extent + prefix(&node.right, index - left_len - 1)
787            }
788        }
789
790        prefix(&self.root, index.min(self.len()))
791    }
792
793    pub fn index_at_offset(&self, offset: f32) -> Option<usize> {
794        if self.is_empty() {
795            return None;
796        }
797        let mut offset = offset.max(0.0).min((self.total() - f32::EPSILON).max(0.0));
798        let mut base = 0;
799        let mut node = self.root.as_deref();
800        while let Some(current) = node {
801            let left_sum = link_sum(&current.left);
802            let left_len = link_len(&current.left);
803            if offset < left_sum {
804                node = current.left.as_deref();
805            } else if offset < left_sum + current.extent {
806                return Some(base + left_len);
807            } else {
808                offset -= left_sum + current.extent;
809                base += left_len + 1;
810                node = current.right.as_deref();
811            }
812        }
813        Some(self.len() - 1)
814    }
815}
816
817fn splitmix64(mut value: u64) -> u64 {
818    value = value.wrapping_add(0x9e37_79b9_7f4a_7c15);
819    value = (value ^ (value >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
820    value = (value ^ (value >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
821    value ^ (value >> 31)
822}
823
824#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
825pub enum CollectionAnchorGravity {
826    #[default]
827    Start,
828    End,
829}
830
831#[derive(Clone, Debug, PartialEq)]
832pub struct CollectionAnchor<K> {
833    pub key: K,
834    pub offset_within_item: f32,
835    pub gravity: CollectionAnchorGravity,
836}
837
838#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
839pub enum ScrollAlignment {
840    #[default]
841    Nearest,
842    Start,
843    Center,
844    End,
845}
846
847/// Observable projection of a virtual collection viewport.
848///
849/// `loaded_range` and `visible_range` use dataset-space indices. The key list
850/// only contains items intersecting the viewport, making this snapshot
851/// suitable for paging UI, diagnostics, and prefetch decisions without
852/// exposing internal widget pods.
853#[derive(Clone, Debug, PartialEq)]
854pub struct VirtualViewportSnapshot<K> {
855    pub loaded_range: Range<usize>,
856    pub visible_range: Range<usize>,
857    pub visible_keys: Vec<K>,
858    pub total_count: Option<usize>,
859    pub has_before: bool,
860    pub has_after: bool,
861    pub anchor: Option<CollectionAnchor<K>>,
862    pub offset: f32,
863    pub max_offset: f32,
864    pub at_loaded_start: bool,
865    pub at_loaded_end: bool,
866    pub following_end: bool,
867}
868
869impl<K> Default for VirtualViewportSnapshot<K> {
870    fn default() -> Self {
871        Self {
872            loaded_range: 0..0,
873            visible_range: 0..0,
874            visible_keys: Vec::new(),
875            total_count: Some(0),
876            has_before: false,
877            has_after: false,
878            anchor: None,
879            offset: 0.0,
880            max_offset: 0.0,
881            at_loaded_start: true,
882            at_loaded_end: true,
883            following_end: false,
884        }
885    }
886}
887
888#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
889pub enum VirtualListSelectionMode {
890    None,
891    #[default]
892    Single,
893}
894
895#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
896pub enum VirtualListChrome {
897    #[default]
898    Default,
899    Transparent,
900}
901
902#[derive(Clone)]
903pub struct VirtualListState<K> {
904    inner: Rc<RefCell<VirtualListStateInner<K>>>,
905    revision: Signal<u64>,
906    viewport: Signal<VirtualViewportSnapshot<K>>,
907    scroll: ScrollState,
908}
909
910struct VirtualListStateInner<K> {
911    selected: Option<K>,
912    pending_scroll: Option<(K, ScrollAlignment)>,
913    pinned: HashSet<K>,
914    follow_end_enabled: bool,
915    following_end: bool,
916}
917
918impl<K> VirtualListState<K>
919where
920    K: Clone + Eq + Hash + PartialEq + 'static,
921{
922    pub fn new() -> Self {
923        Self {
924            inner: Rc::new(RefCell::new(VirtualListStateInner {
925                selected: None,
926                pending_scroll: None,
927                pinned: HashSet::new(),
928                follow_end_enabled: false,
929                following_end: false,
930            })),
931            revision: Signal::named("Virtual list state", 0),
932            viewport: Signal::named("Virtual list viewport", VirtualViewportSnapshot::default()),
933            scroll: ScrollState::new(),
934        }
935    }
936
937    pub fn selected_key(&self) -> Option<K> {
938        self.inner.borrow().selected.clone()
939    }
940
941    pub fn select(&self, key: Option<K>) -> bool {
942        let changed = {
943            let mut inner = self.inner.borrow_mut();
944            if inner.selected == key {
945                false
946            } else {
947                inner.selected = key;
948                true
949            }
950        };
951        if changed {
952            self.bump();
953        }
954        changed
955    }
956
957    pub fn scroll_to(&self, key: K, alignment: ScrollAlignment) {
958        self.inner.borrow_mut().pending_scroll = Some((key, alignment));
959        self.bump();
960    }
961
962    pub fn pin(&self, key: K) -> bool {
963        let changed = self.inner.borrow_mut().pinned.insert(key);
964        if changed {
965            self.bump();
966        }
967        changed
968    }
969
970    pub fn unpin(&self, key: &K) -> bool {
971        let changed = self.inner.borrow_mut().pinned.remove(key);
972        if changed {
973            self.bump();
974        }
975        changed
976    }
977
978    pub fn set_follow_end(&self, enabled: bool) {
979        let changed = {
980            let mut inner = self.inner.borrow_mut();
981            if inner.follow_end_enabled == enabled && (!enabled || inner.following_end == enabled) {
982                false
983            } else {
984                inner.follow_end_enabled = enabled;
985                inner.following_end = enabled;
986                true
987            }
988        };
989        if changed {
990            self.bump();
991        }
992    }
993
994    pub fn resume_follow_end(&self) {
995        let changed = {
996            let mut inner = self.inner.borrow_mut();
997            if !inner.follow_end_enabled || inner.following_end {
998                false
999            } else {
1000                inner.following_end = true;
1001                true
1002            }
1003        };
1004        if changed {
1005            self.bump();
1006        }
1007    }
1008
1009    pub fn is_following_end(&self) -> bool {
1010        let inner = self.inner.borrow();
1011        inner.follow_end_enabled && inner.following_end
1012    }
1013
1014    pub fn scroll_state(&self) -> ScrollState {
1015        self.scroll.clone()
1016    }
1017
1018    pub fn viewport(&self) -> VirtualViewportSnapshot<K> {
1019        self.viewport.get()
1020    }
1021
1022    pub fn viewport_signal(&self) -> Signal<VirtualViewportSnapshot<K>> {
1023        self.viewport.clone()
1024    }
1025
1026    fn bump(&self) {
1027        let _ = self.revision.update(|revision| {
1028            *revision = revision.wrapping_add(1);
1029        });
1030    }
1031
1032    fn take_pending_scroll(&self) -> Option<(K, ScrollAlignment)> {
1033        self.inner.borrow_mut().pending_scroll.take()
1034    }
1035
1036    fn pinned(&self) -> HashSet<K> {
1037        self.inner.borrow().pinned.clone()
1038    }
1039
1040    fn update_following_for_offset(&self, offset: f32, max_offset: f32) {
1041        let mut inner = self.inner.borrow_mut();
1042        if inner.follow_end_enabled {
1043            inner.following_end = max_offset - offset <= FOLLOW_END_THRESHOLD;
1044        }
1045    }
1046
1047    fn clear_removed_selection(&self, live_keys: &HashSet<K>) {
1048        let changed = {
1049            let mut inner = self.inner.borrow_mut();
1050            if inner
1051                .selected
1052                .as_ref()
1053                .is_some_and(|selected| !live_keys.contains(selected))
1054            {
1055                inner.selected = None;
1056                true
1057            } else {
1058                false
1059            }
1060        };
1061        if changed {
1062            self.bump();
1063        }
1064    }
1065
1066    fn publish_viewport(&self, viewport: VirtualViewportSnapshot<K>) {
1067        let _ = self.viewport.set(viewport);
1068    }
1069}
1070
1071impl<K> Default for VirtualListState<K>
1072where
1073    K: Clone + Eq + Hash + PartialEq + 'static,
1074{
1075    fn default() -> Self {
1076        Self::new()
1077    }
1078}
1079
1080struct RealizedRow<T> {
1081    value: Signal<T>,
1082    pod: WidgetPod,
1083    last_used: u64,
1084}
1085
1086#[derive(Clone, Copy)]
1087struct TouchGesture {
1088    pointer_id: u64,
1089    origin: Point,
1090    dragging: bool,
1091}
1092
1093impl TouchGesture {
1094    fn new(pointer: &PointerEvent) -> Self {
1095        Self {
1096            pointer_id: pointer.pointer_id,
1097            origin: pointer.position,
1098            dragging: false,
1099        }
1100    }
1101
1102    fn matches(self, pointer: &PointerEvent) -> bool {
1103        self.pointer_id == pointer.pointer_id
1104    }
1105
1106    fn passed_threshold(self, pointer: &PointerEvent) -> bool {
1107        (pointer.position.y - self.origin.y).abs() >= 6.0
1108    }
1109}
1110
1111struct CapturedAnchor<K> {
1112    anchor: CollectionAnchor<K>,
1113    fallback_index: usize,
1114}
1115
1116type VirtualListChange<K> = Box<dyn FnMut(K)>;
1117type VirtualListContextChange<K> = Box<dyn FnMut(&mut EventCtx, K)>;
1118type VirtualListEdge = Box<dyn FnMut()>;
1119type VirtualListContextEdge = Box<dyn FnMut(&mut EventCtx)>;
1120
1121/// Data-backed retained virtual list with stable keyed row identity.
1122///
1123/// Only the visible and overscanned rows are realized and measured. Recently
1124/// hidden rows are retained in a bounded keyed cache; focused and explicitly
1125/// pinned rows are never recycled.
1126pub struct VirtualList<K, T> {
1127    theme: Box<DefaultTheme>,
1128    theme_reader: Option<Rc<dyn Fn() -> DefaultTheme>>,
1129    scroll_bar_theme: Rc<RefCell<DefaultTheme>>,
1130    name: String,
1131    source: Arc<dyn VirtualCollectionSource<K, T>>,
1132    state: VirtualListState<K>,
1133    row_builder: Box<dyn Fn(&K, Signal<T>) -> WidgetPod>,
1134    row_name: Option<Box<dyn Fn(&K, &T) -> String>>,
1135    row_description: Option<Box<dyn Fn(&K, &T) -> String>>,
1136    on_change: Option<VirtualListChange<K>>,
1137    on_change_with_ctx: Option<VirtualListContextChange<K>>,
1138    on_near_start: Option<VirtualListEdge>,
1139    on_near_start_with_ctx: Option<VirtualListContextEdge>,
1140    on_near_end: Option<VirtualListEdge>,
1141    on_near_end_with_ctx: Option<VirtualListContextEdge>,
1142    keys: Vec<K>,
1143    window: CollectionWindow,
1144    index_by_key: HashMap<K, usize>,
1145    semantic_ids: HashMap<K, WidgetId>,
1146    realized: HashMap<K, RealizedRow<T>>,
1147    extents: CollectionExtentIndex,
1148    initialized: bool,
1149    source_revision: u64,
1150    offset_y: f32,
1151    active_range: Range<usize>,
1152    estimated_row_height: Option<f32>,
1153    spacing: f32,
1154    padding: Option<Insets>,
1155    row_padding: Option<Insets>,
1156    overscan_viewports: f32,
1157    cache_capacity: usize,
1158    selection_mode: VirtualListSelectionMode,
1159    chrome: VirtualListChrome,
1160    epoch: u64,
1161    hovered: Option<K>,
1162    pressed: Option<K>,
1163    focused_row: RefCell<Option<K>>,
1164    near_start_notified: bool,
1165    near_end_notified: bool,
1166    scroll_bars: bool,
1167    bars: Option<ScrollBars>,
1168    touch_scroll: Option<TouchGesture>,
1169}
1170
1171impl<K, T> VirtualList<K, T>
1172where
1173    K: Clone + Eq + Hash + PartialEq + 'static,
1174    T: Clone + PartialEq + 'static,
1175{
1176    pub fn new<S, F, W>(name: impl Into<String>, source: S, row_builder: F) -> VirtualList<K, T>
1177    where
1178        S: VirtualCollectionSource<K, T> + 'static,
1179        F: Fn(&K, Signal<T>) -> W + 'static,
1180        W: Widget + 'static,
1181    {
1182        let theme = DefaultTheme::default();
1183        Self {
1184            theme: Box::new(theme),
1185            theme_reader: None,
1186            scroll_bar_theme: Rc::new(RefCell::new(theme)),
1187            name: name.into(),
1188            source: Arc::new(source),
1189            state: VirtualListState::new(),
1190            row_builder: Box::new(move |key, value| WidgetPod::new(row_builder(key, value))),
1191            row_name: None,
1192            row_description: None,
1193            on_change: None,
1194            on_change_with_ctx: None,
1195            on_near_start: None,
1196            on_near_start_with_ctx: None,
1197            on_near_end: None,
1198            on_near_end_with_ctx: None,
1199            keys: Vec::new(),
1200            window: CollectionWindow::default(),
1201            index_by_key: HashMap::new(),
1202            semantic_ids: HashMap::new(),
1203            realized: HashMap::new(),
1204            extents: CollectionExtentIndex::new(),
1205            initialized: false,
1206            source_revision: 0,
1207            offset_y: 0.0,
1208            active_range: 0..0,
1209            estimated_row_height: None,
1210            spacing: 0.0,
1211            padding: None,
1212            row_padding: None,
1213            overscan_viewports: DEFAULT_OVERSCAN_VIEWPORTS,
1214            cache_capacity: DEFAULT_CACHE_CAPACITY,
1215            selection_mode: VirtualListSelectionMode::Single,
1216            chrome: VirtualListChrome::Default,
1217            epoch: 0,
1218            hovered: None,
1219            pressed: None,
1220            focused_row: RefCell::new(None),
1221            near_start_notified: false,
1222            near_end_notified: false,
1223            scroll_bars: true,
1224            bars: None,
1225            touch_scroll: None,
1226        }
1227    }
1228
1229    pub fn state(mut self, state: VirtualListState<K>) -> Self {
1230        self.state = state;
1231        self.bars = None;
1232        self
1233    }
1234
1235    pub fn theme(mut self, theme: DefaultTheme) -> Self {
1236        self.theme = Box::new(theme);
1237        self.theme_reader = None;
1238        *self.scroll_bar_theme.borrow_mut() = theme;
1239        self
1240    }
1241
1242    pub fn theme_when<F>(mut self, reader: F) -> Self
1243    where
1244        F: Fn() -> DefaultTheme + 'static,
1245    {
1246        self.theme_reader = Some(Rc::new(reader));
1247        self
1248    }
1249
1250    pub fn estimated_row_height(mut self, height: f32) -> Self {
1251        self.estimated_row_height = Some(height.max(1.0));
1252        self
1253    }
1254
1255    pub fn gap(mut self, gap: f32) -> Self {
1256        self.spacing = gap.max(0.0);
1257        self
1258    }
1259
1260    pub fn padding(mut self, padding: Insets) -> Self {
1261        self.padding = Some(padding);
1262        self
1263    }
1264
1265    /// Overrides the theme-provided padding around each row's custom content.
1266    ///
1267    /// Virtual lists apply `data_row_padding` automatically so row builders do
1268    /// not need to repeat edge padding. Pass `Insets::ZERO` for full-bleed row
1269    /// content while preserving the list's viewport padding.
1270    pub fn row_padding(mut self, padding: Insets) -> Self {
1271        self.row_padding = Some(padding);
1272        self
1273    }
1274
1275    pub fn overscan_viewports(mut self, viewports: f32) -> Self {
1276        self.overscan_viewports = viewports.max(0.0);
1277        self
1278    }
1279
1280    pub fn cache_capacity(mut self, capacity: usize) -> Self {
1281        self.cache_capacity = capacity;
1282        self
1283    }
1284
1285    pub fn selection_mode(mut self, mode: VirtualListSelectionMode) -> Self {
1286        self.selection_mode = mode;
1287        if mode == VirtualListSelectionMode::None {
1288            let _ = self.state.select(None);
1289        }
1290        self
1291    }
1292
1293    pub fn chrome(mut self, chrome: VirtualListChrome) -> Self {
1294        self.chrome = chrome;
1295        self
1296    }
1297
1298    pub fn stick_to_end(self, enabled: bool) -> Self {
1299        self.state.set_follow_end(enabled);
1300        self
1301    }
1302
1303    /// Compatibility name for `scroll_bars`. Built-in bars reserve layout space.
1304    pub fn overlay_scroll_bars(self, enabled: bool) -> Self {
1305        self.scroll_bars(enabled)
1306    }
1307
1308    /// Show built-in scrollbars in their own gutters when content overflows.
1309    pub fn scroll_bars(mut self, enabled: bool) -> Self {
1310        self.scroll_bars = enabled;
1311        if !enabled {
1312            self.bars = None;
1313        }
1314        self
1315    }
1316
1317    pub fn row_name<F>(mut self, name: F) -> Self
1318    where
1319        F: Fn(&K, &T) -> String + 'static,
1320    {
1321        self.row_name = Some(Box::new(name));
1322        self
1323    }
1324
1325    pub fn row_description<F>(mut self, description: F) -> Self
1326    where
1327        F: Fn(&K, &T) -> String + 'static,
1328    {
1329        self.row_description = Some(Box::new(description));
1330        self
1331    }
1332
1333    pub fn on_change<F>(mut self, on_change: F) -> Self
1334    where
1335        F: FnMut(K) + 'static,
1336    {
1337        self.on_change = Some(Box::new(on_change));
1338        self.on_change_with_ctx = None;
1339        self
1340    }
1341
1342    pub fn on_change_with_ctx<F>(mut self, on_change: F) -> Self
1343    where
1344        F: FnMut(&mut EventCtx, K) + 'static,
1345    {
1346        self.on_change = None;
1347        self.on_change_with_ctx = Some(Box::new(on_change));
1348        self
1349    }
1350
1351    pub fn on_near_start<F>(mut self, on_near_start: F) -> Self
1352    where
1353        F: FnMut() + 'static,
1354    {
1355        self.on_near_start = Some(Box::new(on_near_start));
1356        self.on_near_start_with_ctx = None;
1357        self
1358    }
1359
1360    pub fn on_near_start_with_ctx<F>(mut self, on_near_start: F) -> Self
1361    where
1362        F: FnMut(&mut EventCtx) + 'static,
1363    {
1364        self.on_near_start = None;
1365        self.on_near_start_with_ctx = Some(Box::new(on_near_start));
1366        self
1367    }
1368
1369    pub fn on_near_end<F>(mut self, on_near_end: F) -> Self
1370    where
1371        F: FnMut() + 'static,
1372    {
1373        self.on_near_end = Some(Box::new(on_near_end));
1374        self.on_near_end_with_ctx = None;
1375        self
1376    }
1377
1378    pub fn on_near_end_with_ctx<F>(mut self, on_near_end: F) -> Self
1379    where
1380        F: FnMut(&mut EventCtx) + 'static,
1381    {
1382        self.on_near_end = None;
1383        self.on_near_end_with_ctx = Some(Box::new(on_near_end));
1384        self
1385    }
1386
1387    pub fn current_offset(&self) -> Vector {
1388        Vector::new(0.0, self.offset_y)
1389    }
1390
1391    pub fn realized_count(&self) -> usize {
1392        self.realized.len()
1393    }
1394
1395    fn resolved_theme(&self) -> DefaultTheme {
1396        self.theme_reader
1397            .as_ref()
1398            .map(|reader| reader())
1399            .unwrap_or_else(|| *self.theme)
1400    }
1401
1402    fn sync_scroll_bar_theme(&self) -> DefaultTheme {
1403        let theme = self.resolved_theme();
1404        *self.scroll_bar_theme.borrow_mut() = theme;
1405        theme
1406    }
1407
1408    fn ensure_scroll_bars(&mut self) {
1409        if self.scroll_bars && self.bars.is_none() {
1410            self.bars = Some(ScrollBars::new(
1411                self.state.scroll.clone(),
1412                Rc::clone(&self.scroll_bar_theme),
1413                Some(&self.name),
1414                ScrollAxes::Vertical,
1415            ));
1416        }
1417    }
1418
1419    fn resolved_padding(&self) -> Insets {
1420        self.padding
1421            .unwrap_or(self.resolved_theme().metrics.data_viewport_padding)
1422    }
1423
1424    fn resolved_row_padding(&self) -> Insets {
1425        self.row_padding
1426            .unwrap_or(self.resolved_theme().metrics.data_row_padding)
1427    }
1428
1429    fn estimated_extent(&self) -> f32 {
1430        self.estimated_row_height
1431            .unwrap_or(self.resolved_theme().metrics.list_row_height)
1432            .max(1.0)
1433            + self.spacing
1434    }
1435
1436    fn content_height(&self) -> f32 {
1437        if self.extents.is_empty() {
1438            0.0
1439        } else {
1440            (self.extents.total() - self.spacing).max(0.0)
1441        }
1442    }
1443
1444    fn viewport_rect(&self, bounds: Rect) -> Rect {
1445        let viewport = inset_rect(bounds, self.resolved_padding());
1446        let gutter = crate::containers::scroll_bar_gutter(
1447            self.scroll_bars,
1448            ScrollAxes::Vertical,
1449            viewport.size,
1450            Size::new(0.0, self.content_height()),
1451            self.resolved_theme().metrics.scroll_bar_thickness,
1452        );
1453        Rect::from_origin_size(
1454            viewport.origin,
1455            crate::containers::scroll_viewport_size(viewport.size, gutter),
1456        )
1457    }
1458
1459    fn rebuild_index(&mut self) {
1460        self.index_by_key.clear();
1461        self.index_by_key.extend(
1462            self.keys
1463                .iter()
1464                .cloned()
1465                .enumerate()
1466                .map(|(index, key)| (key, index)),
1467        );
1468    }
1469
1470    fn next_semantic_id() -> WidgetId {
1471        WidgetId::new(
1472            SYNTHETIC_COLLECTION_ITEM_TAG | NEXT_COLLECTION_ITEM_ID.fetch_add(1, Ordering::Relaxed),
1473        )
1474    }
1475
1476    fn ensure_semantic_ids(&mut self) {
1477        for key in &self.keys {
1478            self.semantic_ids
1479                .entry(key.clone())
1480                .or_insert_with(Self::next_semantic_id);
1481        }
1482    }
1483
1484    fn reset_keys(&mut self, keys: Vec<K>) {
1485        let old_extents = self
1486            .keys
1487            .iter()
1488            .enumerate()
1489            .filter_map(|(index, key)| {
1490                self.extents
1491                    .extent(index)
1492                    .map(|extent| (key.clone(), extent))
1493            })
1494            .collect::<HashMap<_, _>>();
1495        let live = keys.iter().cloned().collect::<HashSet<_>>();
1496        self.realized.retain(|key, row| {
1497            if !live.contains(key) {
1498                return false;
1499            }
1500            if let Some(item) = self.source.item(key) {
1501                let _ = row.value.set(item);
1502            }
1503            true
1504        });
1505        self.semantic_ids.retain(|key, _| live.contains(key));
1506        self.keys = keys;
1507        let estimate = self.estimated_extent();
1508        self.extents.rebuild(
1509            self.keys
1510                .iter()
1511                .map(|key| old_extents.get(key).copied().unwrap_or(estimate)),
1512        );
1513        self.rebuild_index();
1514        self.ensure_semantic_ids();
1515        self.state.clear_removed_selection(&live);
1516        self.hovered.take_if(|hovered| !live.contains(hovered));
1517        self.pressed.take_if(|pressed| !live.contains(pressed));
1518        self.focused_row
1519            .borrow_mut()
1520            .take_if(|focused| !live.contains(focused));
1521    }
1522
1523    fn apply_delta(&mut self, delta: CollectionDelta<K>) -> bool {
1524        match delta {
1525            CollectionDelta::Inserted { index, keys } => {
1526                if index > self.keys.len()
1527                    || keys.iter().any(|key| self.index_by_key.contains_key(key))
1528                {
1529                    return false;
1530                }
1531                let estimate = self.estimated_extent();
1532                self.keys.splice(index..index, keys.iter().cloned());
1533                self.extents
1534                    .insert_many(index, std::iter::repeat_n(estimate, keys.len()));
1535                for key in keys {
1536                    self.semantic_ids
1537                        .entry(key)
1538                        .or_insert_with(Self::next_semantic_id);
1539                }
1540                self.rebuild_index();
1541            }
1542            CollectionDelta::Removed { keys } => {
1543                let removed = keys.iter().cloned().collect::<HashSet<_>>();
1544                if keys.iter().any(|key| !self.index_by_key.contains_key(key)) {
1545                    return false;
1546                }
1547                let mut indices = keys
1548                    .iter()
1549                    .filter_map(|key| self.index_by_key.get(key).copied())
1550                    .collect::<Vec<_>>();
1551                indices.sort_unstable_by(|left, right| right.cmp(left));
1552                for index in indices {
1553                    self.keys.remove(index);
1554                    let _ = self.extents.remove(index);
1555                }
1556                for key in &keys {
1557                    self.realized.remove(key);
1558                    self.semantic_ids.remove(key);
1559                }
1560                self.rebuild_index();
1561                let live = self.keys.iter().cloned().collect::<HashSet<_>>();
1562                self.state.clear_removed_selection(&live);
1563                self.hovered.take_if(|key| removed.contains(key));
1564                self.pressed.take_if(|key| removed.contains(key));
1565                self.focused_row
1566                    .borrow_mut()
1567                    .take_if(|key| removed.contains(key));
1568            }
1569            CollectionDelta::Moved { key, index } => {
1570                let Some(from) = self.index_by_key.get(&key).copied() else {
1571                    return false;
1572                };
1573                if index >= self.keys.len() {
1574                    return false;
1575                }
1576                if from != index {
1577                    let key = self.keys.remove(from);
1578                    self.keys.insert(index, key);
1579                    let _ = self.extents.move_item(from, index);
1580                    self.rebuild_index();
1581                }
1582            }
1583            CollectionDelta::Updated { key } => {
1584                let Some(row) = self.realized.get_mut(&key) else {
1585                    return true;
1586                };
1587                let Some(item) = self.source.item(&key) else {
1588                    return false;
1589                };
1590                let _ = row.value.set(item);
1591            }
1592        }
1593        true
1594    }
1595
1596    fn sync_source(&mut self) -> bool {
1597        let sync = if self.initialized {
1598            self.source.changes_since(self.source_revision)
1599        } else {
1600            CollectionSync::Reset {
1601                revision: self.source.revision(),
1602                keys: self.source.keys(),
1603            }
1604        };
1605
1606        let changed = match sync {
1607            CollectionSync::Unchanged { revision } => {
1608                self.source_revision = revision;
1609                self.initialized = true;
1610                false
1611            }
1612            CollectionSync::Incremental { revision, changes } => {
1613                let mut valid = true;
1614                for change in changes {
1615                    valid &= self.apply_delta(change);
1616                }
1617                if !valid {
1618                    self.reset_keys(self.source.keys());
1619                }
1620                self.source_revision = revision;
1621                self.initialized = true;
1622                true
1623            }
1624            CollectionSync::Reset { revision, keys } => {
1625                self.reset_keys(keys);
1626                self.source_revision = revision;
1627                self.initialized = true;
1628                true
1629            }
1630        };
1631        let window = self
1632            .source
1633            .window()
1634            .normalized_for_loaded_count(self.keys.len());
1635        let window_changed = self.window != window;
1636        self.window = window;
1637        changed || window_changed
1638    }
1639
1640    fn capture_anchor(&self) -> Option<CapturedAnchor<K>> {
1641        let index = self.extents.index_at_offset(self.offset_y)?;
1642        let key = self.keys.get(index)?.clone();
1643        let item_start = self.extents.offset_of(index);
1644        Some(CapturedAnchor {
1645            anchor: CollectionAnchor {
1646                key,
1647                offset_within_item: self.offset_y - item_start,
1648                gravity: CollectionAnchorGravity::Start,
1649            },
1650            fallback_index: index,
1651        })
1652    }
1653
1654    fn restore_anchor(&mut self, captured: &CapturedAnchor<K>) {
1655        let offset = if let Some(index) = self.index_by_key.get(&captured.anchor.key).copied() {
1656            let start = self.extents.offset_of(index);
1657            match captured.anchor.gravity {
1658                CollectionAnchorGravity::Start => {
1659                    start + captured.anchor.offset_within_item.max(0.0)
1660                }
1661                CollectionAnchorGravity::End => {
1662                    let extent = self.extents.extent(index).unwrap_or(0.0);
1663                    start + extent - captured.anchor.offset_within_item.max(0.0)
1664                }
1665            }
1666        } else if self.keys.is_empty() {
1667            0.0
1668        } else {
1669            self.extents
1670                .offset_of(captured.fallback_index.min(self.keys.len() - 1))
1671        };
1672        self.offset_y = offset.max(0.0);
1673    }
1674
1675    fn visible_range(&self, viewport_height: f32, offset_y: f32) -> Range<usize> {
1676        self.range_at_offset(
1677            viewport_height,
1678            offset_y,
1679            viewport_height * self.overscan_viewports,
1680        )
1681    }
1682
1683    fn viewport_item_range(&self, viewport_height: f32) -> Range<usize> {
1684        self.range_at_offset(viewport_height, self.offset_y, 0.0)
1685    }
1686
1687    fn range_at_offset(&self, viewport_height: f32, offset_y: f32, overdraw: f32) -> Range<usize> {
1688        if self.keys.is_empty() {
1689            return 0..0;
1690        }
1691        let top = (offset_y - overdraw).max(0.0);
1692        let bottom = offset_y + viewport_height + overdraw;
1693        let start = self.extents.index_at_offset(top).unwrap_or(0);
1694        let end = self
1695            .extents
1696            .index_at_offset(bottom)
1697            .map_or(self.keys.len(), |index| index + 1)
1698            .min(self.keys.len());
1699        start..end.max(start + 1).min(self.keys.len())
1700    }
1701
1702    fn ensure_realized(&mut self, index: usize) -> bool {
1703        let Some(key) = self.keys.get(index).cloned() else {
1704            return false;
1705        };
1706        self.epoch = self.epoch.wrapping_add(1);
1707        if let Some(row) = self.realized.get_mut(&key) {
1708            row.last_used = self.epoch;
1709            return true;
1710        }
1711        let Some(item) = self.source.item(&key) else {
1712            return false;
1713        };
1714        let value = Signal::named("Virtual collection row", item);
1715        let pod = (self.row_builder)(&key, value.clone());
1716        self.realized.insert(
1717            key,
1718            RealizedRow {
1719                value,
1720                pod,
1721                last_used: self.epoch,
1722            },
1723        );
1724        true
1725    }
1726
1727    fn measure_active_rows(
1728        &mut self,
1729        ctx: &mut MeasureCtx,
1730        viewport_width: f32,
1731        viewport_height: f32,
1732    ) -> bool {
1733        let next_range = self.visible_range(viewport_height, self.offset_y);
1734        let mut extent_changed = false;
1735        let row_padding = self.resolved_row_padding();
1736        let content_width = (viewport_width - row_padding.left - row_padding.right).max(0.0);
1737        let constraints = Constraints::new(
1738            Size::new(content_width, 0.0),
1739            Size::new(content_width, f32::INFINITY),
1740        );
1741        for index in next_range.clone() {
1742            if !self.ensure_realized(index) {
1743                continue;
1744            }
1745            let key = self.keys[index].clone();
1746            let Some(row) = self.realized.get_mut(&key) else {
1747                continue;
1748            };
1749            let size = row.pod.measure(ctx, constraints);
1750            let row_height = size.height + row_padding.top + row_padding.bottom;
1751            extent_changed |= self
1752                .extents
1753                .update(index, row_height.max(1.0) + self.spacing);
1754        }
1755        self.active_range = next_range;
1756        extent_changed
1757    }
1758
1759    fn sync_scroll_state<C>(&mut self, ctx: &mut C, viewport: Size)
1760    where
1761        C: ScrollInvalidationCtx + ScrollWidgetCtx,
1762    {
1763        let content = Size::new(viewport.width, self.content_height());
1764        self.state
1765            .scroll
1766            .bind_scroll_view(ctx.widget_id(), ctx.widget_id());
1767        let mut changed = self
1768            .state
1769            .scroll
1770            .sync_metrics(ScrollAxes::Vertical, viewport, content);
1771        let max_offset = self.state.scroll.max_offset().y;
1772        self.offset_y = self.offset_y.clamp(0.0, max_offset);
1773        changed |= self
1774            .state
1775            .scroll
1776            .set_offset(Vector::new(0.0, self.offset_y));
1777        if changed {
1778            for scroll_bar_id in self.state.scroll.subscribers().scroll_bar_ids {
1779                request_scroll_bar_refresh(ctx, scroll_bar_id);
1780            }
1781        }
1782    }
1783
1784    fn offset_for_alignment(
1785        &self,
1786        index: usize,
1787        viewport_height: f32,
1788        alignment: ScrollAlignment,
1789    ) -> f32 {
1790        let top = self.extents.offset_of(index);
1791        let extent = self
1792            .extents
1793            .extent(index)
1794            .unwrap_or(self.estimated_extent())
1795            .saturating_sub(self.spacing);
1796        let bottom = top + extent;
1797        match alignment {
1798            ScrollAlignment::Start => top,
1799            ScrollAlignment::Center => top - (viewport_height - extent) * 0.5,
1800            ScrollAlignment::End => bottom - viewport_height,
1801            ScrollAlignment::Nearest => {
1802                if top < self.offset_y {
1803                    top
1804                } else if bottom > self.offset_y + viewport_height {
1805                    bottom - viewport_height
1806                } else {
1807                    self.offset_y
1808                }
1809            }
1810        }
1811        .max(0.0)
1812    }
1813
1814    fn apply_pending_scroll(&mut self, viewport_height: f32) {
1815        if let Some((key, alignment)) = self.state.take_pending_scroll()
1816            && let Some(index) = self.index_by_key.get(&key).copied()
1817        {
1818            self.offset_y = self.offset_for_alignment(index, viewport_height, alignment);
1819            self.state
1820                .update_following_for_offset(self.offset_y, self.state.scroll.max_offset().y);
1821        }
1822        if let Some(index) = self.state.scroll.take_pending_virtual_item()
1823            && index < self.keys.len()
1824        {
1825            self.offset_y =
1826                self.offset_for_alignment(index, viewport_height, ScrollAlignment::Start);
1827        }
1828    }
1829
1830    fn clamp_offset(&mut self, viewport_height: f32) {
1831        let max_offset = (self.content_height() - viewport_height).max(0.0);
1832        self.offset_y = self.offset_y.clamp(0.0, max_offset);
1833        let _ = self
1834            .state
1835            .scroll
1836            .set_offset(Vector::new(0.0, self.offset_y));
1837    }
1838
1839    fn row_at_position(&self, bounds: Rect, position: Point) -> Option<usize> {
1840        let viewport = self.viewport_rect(bounds);
1841        if !viewport.contains(position) {
1842            return None;
1843        }
1844        let offset = position.y - viewport.y() + self.offset_y;
1845        self.extents.index_at_offset(offset)
1846    }
1847
1848    fn row_rect(&self, bounds: Rect, index: usize) -> Option<Rect> {
1849        let viewport = self.viewport_rect(bounds);
1850        let top = self.extents.offset_of(index);
1851        let extent = self.extents.extent(index)?;
1852        Some(Rect::new(
1853            viewport.x(),
1854            viewport.y() + top - self.offset_y,
1855            viewport.width(),
1856            (extent - self.spacing).max(0.0),
1857        ))
1858    }
1859
1860    fn activate_index(&mut self, index: usize, ctx: &mut EventCtx) {
1861        if self.selection_mode == VirtualListSelectionMode::None {
1862            return;
1863        }
1864        let Some(key) = self.keys.get(index).cloned() else {
1865            return;
1866        };
1867        let changed = self.state.select(Some(key.clone()));
1868        if changed {
1869            if let Some(on_change) = &mut self.on_change_with_ctx {
1870                on_change(ctx, key);
1871            } else if let Some(on_change) = &mut self.on_change {
1872                on_change(key);
1873            }
1874            ctx.request_paint();
1875            ctx.request_semantics();
1876        }
1877    }
1878
1879    fn ensure_index_visible(&mut self, index: usize, viewport_height: f32) {
1880        self.offset_y = self.offset_for_alignment(index, viewport_height, ScrollAlignment::Nearest);
1881        self.clamp_offset(viewport_height);
1882    }
1883
1884    fn move_selection(&mut self, delta: isize, viewport_height: f32, ctx: &mut EventCtx) {
1885        if self.keys.is_empty() {
1886            return;
1887        }
1888        let current = self
1889            .state
1890            .selected_key()
1891            .as_ref()
1892            .and_then(|key| self.index_by_key.get(key).copied())
1893            .unwrap_or(0);
1894        let next = (current as isize + delta).clamp(0, self.keys.len() as isize - 1) as usize;
1895        self.activate_index(next, ctx);
1896        self.ensure_index_visible(next, viewport_height);
1897    }
1898
1899    fn scroll_by(&mut self, viewport: Rect, delta_y: f32, ctx: &mut EventCtx) -> bool {
1900        let previous = self.offset_y;
1901        let max_offset = (self.content_height() - viewport.height()).max(0.0);
1902        let next = (previous + delta_y).clamp(0.0, max_offset);
1903        if (next - previous).abs() <= f32::EPSILON {
1904            return false;
1905        }
1906        self.offset_y = next;
1907        let _ = self
1908            .state
1909            .scroll
1910            .set_offset(Vector::new(0.0, self.offset_y));
1911        self.state
1912            .update_following_for_offset(self.offset_y, max_offset);
1913        ctx.request_measure();
1914        ctx.request_arrange();
1915        ctx.request_paint();
1916        ctx.request_semantics();
1917        for index in self.active_range.clone() {
1918            if let Some(key) = self.keys.get(index)
1919                && let Some(row) = self.realized.get(key)
1920            {
1921                ctx.request(InvalidationRequest::new(
1922                    InvalidationTarget::Widget(row.pod.id()),
1923                    InvalidationKind::Transform,
1924                ));
1925            }
1926        }
1927        for scroll_bar_id in self.state.scroll.subscribers().scroll_bar_ids {
1928            request_scroll_bar_refresh(ctx, scroll_bar_id);
1929        }
1930        self.notify_near_edges(viewport.height(), ctx);
1931        true
1932    }
1933
1934    fn notify_near_edges(&mut self, viewport_height: f32, ctx: &mut EventCtx) {
1935        let threshold = viewport_height.max(self.estimated_extent() * 8.0);
1936        let near_start = self.offset_y <= threshold;
1937        let remaining = (self.content_height() - viewport_height - self.offset_y).max(0.0);
1938        let near_end = remaining <= threshold;
1939
1940        if near_start && !self.near_start_notified {
1941            self.near_start_notified = true;
1942            if let Some(on_near_start) = &mut self.on_near_start_with_ctx {
1943                on_near_start(ctx);
1944            } else if let Some(on_near_start) = &mut self.on_near_start {
1945                on_near_start();
1946            }
1947        } else if !near_start {
1948            self.near_start_notified = false;
1949        }
1950
1951        if near_end && !self.near_end_notified {
1952            self.near_end_notified = true;
1953            if let Some(on_near_end) = &mut self.on_near_end_with_ctx {
1954                on_near_end(ctx);
1955            } else if let Some(on_near_end) = &mut self.on_near_end {
1956                on_near_end();
1957            }
1958        } else if !near_end {
1959            self.near_end_notified = false;
1960        }
1961    }
1962
1963    fn publish_viewport(&self, viewport_height: f32) {
1964        let local = self.viewport_item_range(viewport_height);
1965        let global_start = self.window.loaded_range.start.saturating_add(local.start);
1966        let global_end = self.window.loaded_range.start.saturating_add(local.end);
1967        let max_offset = (self.content_height() - viewport_height).max(0.0);
1968        self.state.publish_viewport(VirtualViewportSnapshot {
1969            loaded_range: self.window.loaded_range.clone(),
1970            visible_range: global_start..global_end,
1971            visible_keys: local
1972                .clone()
1973                .filter_map(|index| self.keys.get(index).cloned())
1974                .collect(),
1975            total_count: self.window.total_count,
1976            has_before: self.window.has_before,
1977            has_after: self.window.has_after,
1978            anchor: self.capture_anchor().map(|captured| captured.anchor),
1979            offset: self.offset_y,
1980            max_offset,
1981            at_loaded_start: self.offset_y <= f32::EPSILON,
1982            at_loaded_end: max_offset - self.offset_y <= f32::EPSILON,
1983            following_end: self.state.is_following_end(),
1984        });
1985    }
1986
1987    fn sync_focused_row(&self, focused: Option<WidgetId>) {
1988        let Some(focused) = focused else {
1989            *self.focused_row.borrow_mut() = None;
1990            return;
1991        };
1992        *self.focused_row.borrow_mut() = self
1993            .realized
1994            .iter()
1995            .find_map(|(key, row)| pod_contains_widget(&row.pod, focused).then(|| key.clone()));
1996    }
1997
1998    fn retained_keys(&self) -> HashSet<K> {
1999        let mut retained = self.state.pinned();
2000        if let Some(focused) = self.focused_row.borrow().as_ref() {
2001            retained.insert(focused.clone());
2002        }
2003        retained
2004    }
2005
2006    fn evict_rows(&mut self) {
2007        let retained = self.retained_keys();
2008        let active = self
2009            .active_range
2010            .clone()
2011            .filter_map(|index| self.keys.get(index).cloned())
2012            .collect::<HashSet<_>>();
2013        let maximum = active.len() + retained.len() + self.cache_capacity;
2014        if self.realized.len() <= maximum {
2015            return;
2016        }
2017        let mut candidates = self
2018            .realized
2019            .iter()
2020            .filter(|(key, _)| !active.contains(*key) && !retained.contains(*key))
2021            .map(|(key, row)| (key.clone(), row.last_used))
2022            .collect::<Vec<_>>();
2023        candidates.sort_unstable_by_key(|(_, last_used)| *last_used);
2024        let remove_count = self.realized.len().saturating_sub(maximum);
2025        for (key, _) in candidates.into_iter().take(remove_count) {
2026            self.realized.remove(&key);
2027        }
2028    }
2029
2030    fn semantic_key(&self, target: WidgetId) -> Option<K> {
2031        self.semantic_ids
2032            .iter()
2033            .find_map(|(key, id)| (*id == target).then(|| key.clone()))
2034    }
2035
2036    fn handle_touch_pointer(&mut self, ctx: &mut EventCtx, pointer: &PointerEvent, viewport: Rect) {
2037        if pointer.pointer_kind != PointerKind::Touch || ctx.phase() == EventPhase::Capture {
2038            return;
2039        }
2040        match pointer.kind {
2041            PointerEventKind::Down
2042                if pointer.is_primary
2043                    && pointer.button == Some(PointerButton::Primary)
2044                    && viewport.contains(pointer.position)
2045                    && self.content_height() > viewport.height() =>
2046            {
2047                self.touch_scroll = Some(TouchGesture::new(pointer));
2048            }
2049            PointerEventKind::Move => {
2050                let Some(gesture) = self.touch_scroll else {
2051                    return;
2052                };
2053                if !gesture.matches(pointer)
2054                    || (!gesture.dragging && !gesture.passed_threshold(pointer))
2055                {
2056                    return;
2057                }
2058                if !gesture.dragging {
2059                    if let Some(gesture) = &mut self.touch_scroll {
2060                        gesture.dragging = true;
2061                    }
2062                    self.pressed = None;
2063                    ctx.request_pointer_capture(pointer.pointer_id);
2064                }
2065                if self.scroll_by(viewport, -pointer.delta.y, ctx) {
2066                    ctx.set_handled();
2067                }
2068            }
2069            PointerEventKind::Up | PointerEventKind::Cancel => {
2070                let Some(gesture) = self.touch_scroll else {
2071                    return;
2072                };
2073                if gesture.matches(pointer) {
2074                    self.touch_scroll = None;
2075                    if gesture.dragging {
2076                        ctx.release_pointer_capture(pointer.pointer_id);
2077                        ctx.set_handled();
2078                    }
2079                }
2080            }
2081            _ => {}
2082        }
2083    }
2084
2085    fn child_keys_for_graph(&self) -> Vec<K> {
2086        let mut keys = self
2087            .active_range
2088            .clone()
2089            .filter_map(|index| self.keys.get(index).cloned())
2090            .collect::<Vec<_>>();
2091        let active = keys.iter().cloned().collect::<HashSet<_>>();
2092        for key in self.retained_keys() {
2093            if !active.contains(&key) && self.realized.contains_key(&key) {
2094                keys.push(key);
2095            }
2096        }
2097        keys
2098    }
2099}
2100
2101impl<K, T> Widget for VirtualList<K, T>
2102where
2103    K: Clone + Eq + Hash + PartialEq + 'static,
2104    T: Clone + PartialEq + 'static,
2105{
2106    fn diagnostics(&self, ctx: &mut WidgetDiagnosticsCtx) {
2107        let viewport = self.state.viewport();
2108        let active_realized = self
2109            .active_range
2110            .clone()
2111            .filter(|index| {
2112                self.keys
2113                    .get(*index)
2114                    .is_some_and(|key| self.realized.contains_key(key))
2115            })
2116            .count();
2117        ctx.record("name", self.name.clone());
2118        ctx.record(
2119            "loaded range",
2120            format!(
2121                "{}..{}",
2122                self.window.loaded_range.start, self.window.loaded_range.end
2123            ),
2124        );
2125        ctx.record(
2126            "visible range",
2127            format!(
2128                "{}..{}",
2129                viewport.visible_range.start, viewport.visible_range.end
2130            ),
2131        );
2132        ctx.record(
2133            "total items",
2134            self.window
2135                .total_count
2136                .map_or_else(|| "unknown".to_string(), |count| count.to_string()),
2137        );
2138        ctx.record("realized rows", self.realized.len().to_string());
2139        ctx.record(
2140            "cached rows",
2141            self.realized
2142                .len()
2143                .saturating_sub(active_realized)
2144                .to_string(),
2145        );
2146        ctx.record("cache capacity", self.cache_capacity.to_string());
2147        ctx.record(
2148            "scroll offset",
2149            format!("{:.1} / {:.1}", viewport.offset, viewport.max_offset),
2150        );
2151        ctx.record("following end", viewport.following_end.to_string());
2152        ctx.record("source revision", self.source_revision.to_string());
2153    }
2154
2155    fn event(&mut self, ctx: &mut EventCtx, event: &Event) {
2156        self.sync_focused_row(ctx.focused_widget_id());
2157        let viewport = self.viewport_rect(ctx.bounds());
2158        if let Event::Pointer(pointer) = event {
2159            self.handle_touch_pointer(ctx, pointer, viewport);
2160        }
2161        if ctx.phase() == EventPhase::Capture {
2162            return;
2163        }
2164
2165        match event {
2166            Event::Pointer(pointer)
2167                if pointer.kind == PointerEventKind::Scroll
2168                    && viewport.contains(pointer.position) =>
2169            {
2170                let delta = pointer
2171                    .scroll_delta
2172                    .map(scroll_delta_to_offset)
2173                    .unwrap_or(pointer.delta);
2174                if self.scroll_by(viewport, -delta.y, ctx) {
2175                    ctx.set_handled();
2176                }
2177            }
2178            Event::Pointer(pointer) if pointer.kind == PointerEventKind::Move => {
2179                let hovered = self
2180                    .row_at_position(ctx.bounds(), pointer.position)
2181                    .and_then(|index| self.keys.get(index).cloned());
2182                if self.hovered != hovered {
2183                    self.hovered = hovered;
2184                    ctx.request_paint();
2185                    ctx.request_semantics();
2186                }
2187            }
2188            Event::Pointer(pointer)
2189                if pointer.kind == PointerEventKind::Down
2190                    && pointer.button == Some(PointerButton::Primary)
2191                    && viewport.contains(pointer.position)
2192                    && self.selection_mode != VirtualListSelectionMode::None
2193                    && !ctx.is_handled() =>
2194            {
2195                self.pressed = self
2196                    .row_at_position(ctx.bounds(), pointer.position)
2197                    .and_then(|index| self.keys.get(index).cloned());
2198                if self.pressed.is_some() {
2199                    ctx.request_focus();
2200                    ctx.request_pointer_capture(pointer.pointer_id);
2201                    ctx.request_paint();
2202                    ctx.request_semantics();
2203                    ctx.set_handled();
2204                }
2205            }
2206            Event::Pointer(pointer)
2207                if pointer.kind == PointerEventKind::Up
2208                    && pointer.button == Some(PointerButton::Primary)
2209                    && self.pressed.is_some() =>
2210            {
2211                let hovered = self
2212                    .row_at_position(ctx.bounds(), pointer.position)
2213                    .and_then(|index| self.keys.get(index).cloned());
2214                let activate = self
2215                    .pressed
2216                    .as_ref()
2217                    .zip(hovered.as_ref())
2218                    .filter(|(pressed, hovered)| pressed == hovered)
2219                    .and_then(|(_, key)| self.index_by_key.get(key).copied());
2220                self.pressed = None;
2221                self.hovered = hovered;
2222                ctx.release_pointer_capture(pointer.pointer_id);
2223                if let Some(index) = activate {
2224                    self.activate_index(index, ctx);
2225                }
2226                ctx.request_paint();
2227                ctx.request_semantics();
2228                ctx.set_handled();
2229            }
2230            Event::Pointer(pointer)
2231                if matches!(
2232                    pointer.kind,
2233                    PointerEventKind::Leave | PointerEventKind::Cancel
2234                ) =>
2235            {
2236                let changed = self.hovered.take().is_some() || self.pressed.take().is_some();
2237                if pointer.kind == PointerEventKind::Cancel {
2238                    ctx.release_pointer_capture(pointer.pointer_id);
2239                }
2240                if changed {
2241                    ctx.request_paint();
2242                    ctx.request_semantics();
2243                }
2244            }
2245            Event::Keyboard(key) if ctx.is_focused() && key.state == KeyState::Pressed => {
2246                match key.key.as_str() {
2247                    "ArrowUp" if self.selection_mode == VirtualListSelectionMode::Single => {
2248                        self.move_selection(-1, viewport.height(), ctx);
2249                    }
2250                    "ArrowDown" if self.selection_mode == VirtualListSelectionMode::Single => {
2251                        self.move_selection(1, viewport.height(), ctx);
2252                    }
2253                    "Home"
2254                        if self.selection_mode == VirtualListSelectionMode::Single
2255                            && !self.keys.is_empty() =>
2256                    {
2257                        self.activate_index(0, ctx);
2258                        self.ensure_index_visible(0, viewport.height());
2259                    }
2260                    "End"
2261                        if self.selection_mode == VirtualListSelectionMode::Single
2262                            && !self.keys.is_empty() =>
2263                    {
2264                        let last = self.keys.len() - 1;
2265                        self.activate_index(last, ctx);
2266                        self.ensure_index_visible(last, viewport.height());
2267                    }
2268                    "PageUp" => {
2269                        let _ = self.scroll_by(viewport, -viewport.height() * 0.85, ctx);
2270                    }
2271                    "PageDown" => {
2272                        let _ = self.scroll_by(viewport, viewport.height() * 0.85, ctx);
2273                    }
2274                    _ => return,
2275                }
2276                let _ = self
2277                    .state
2278                    .scroll
2279                    .set_offset(Vector::new(0.0, self.offset_y));
2280                ctx.request_measure();
2281                ctx.request_arrange();
2282                ctx.request_paint();
2283                ctx.request_semantics();
2284                ctx.set_handled();
2285            }
2286            Event::Semantics(semantics) => {
2287                if semantics.target == ctx.widget_id() {
2288                    let delta = match semantics.action {
2289                        SemanticsActionRequest::Increment => Some(viewport.height() * 0.85),
2290                        SemanticsActionRequest::Decrement => Some(-viewport.height() * 0.85),
2291                        _ => None,
2292                    };
2293                    if let Some(delta) = delta
2294                        && self.scroll_by(viewport, delta, ctx)
2295                    {
2296                        ctx.set_handled();
2297                    }
2298                    return;
2299                }
2300                let Some(key) = self.semantic_key(semantics.target) else {
2301                    return;
2302                };
2303                let Some(index) = self.index_by_key.get(&key).copied() else {
2304                    return;
2305                };
2306                match semantics.action {
2307                    SemanticsActionRequest::Activate
2308                        if self.selection_mode == VirtualListSelectionMode::Single =>
2309                    {
2310                        self.activate_index(index, ctx);
2311                        self.ensure_index_visible(index, viewport.height());
2312                        ctx.request_focus();
2313                        ctx.request_measure();
2314                        ctx.request_arrange();
2315                        ctx.set_handled();
2316                    }
2317                    SemanticsActionRequest::Focus => {
2318                        self.ensure_index_visible(index, viewport.height());
2319                        ctx.request_focus();
2320                        ctx.request_measure();
2321                        ctx.request_arrange();
2322                        ctx.set_handled();
2323                    }
2324                    _ => {}
2325                }
2326            }
2327            _ => {}
2328        }
2329    }
2330
2331    fn measure(&mut self, ctx: &mut MeasureCtx, constraints: Constraints) -> Size {
2332        let theme = self.sync_scroll_bar_theme();
2333        self.ensure_scroll_bars();
2334        let _ = ctx.observe_with(self.source.as_ref(), InvalidationKind::Measure);
2335        let _ = ctx.observe(&self.state.revision);
2336        self.offset_y = self.state.scroll.current_offset().y;
2337
2338        let was_following = self.state.is_following_end();
2339        let anchor = (!was_following).then(|| self.capture_anchor()).flatten();
2340        let source_changed = self.sync_source();
2341
2342        let padding = self.resolved_padding();
2343        let estimated_height = self.content_height() + padding.top + padding.bottom;
2344        let width = if constraints.max.width.is_finite() {
2345            constraints.max.width
2346        } else {
2347            320.0
2348        };
2349        let height = if constraints.max.height.is_finite() {
2350            constraints.max.height
2351        } else {
2352            estimated_height.min(DEFAULT_UNBOUNDED_VIEWPORT_HEIGHT)
2353        };
2354        let size = constraints.clamp(Size::new(width, height));
2355        let mut viewport = self.viewport_rect(Rect::from_origin_size(Point::ZERO, size));
2356
2357        if source_changed {
2358            if was_following {
2359                self.offset_y = (self.content_height() - viewport.height()).max(0.0);
2360            } else if let Some(anchor) = &anchor {
2361                self.restore_anchor(anchor);
2362            }
2363        }
2364
2365        self.sync_scroll_state(ctx, viewport.size);
2366        self.apply_pending_scroll(viewport.height());
2367        if was_following {
2368            self.offset_y = (self.content_height() - viewport.height()).max(0.0);
2369        }
2370        self.clamp_offset(viewport.height());
2371
2372        let measurement_anchor = (!was_following)
2373            .then(|| self.capture_anchor())
2374            .flatten()
2375            .or(anchor);
2376        for _ in 0..5 {
2377            let changed = self.measure_active_rows(ctx, viewport.width(), viewport.height());
2378            let next_viewport = self.viewport_rect(Rect::from_origin_size(Point::ZERO, size));
2379            let viewport_changed = next_viewport != viewport;
2380            viewport = next_viewport;
2381            if !changed && !viewport_changed {
2382                break;
2383            }
2384            if was_following {
2385                self.offset_y = (self.content_height() - viewport.height()).max(0.0);
2386            } else if let Some(anchor) = &measurement_anchor {
2387                self.restore_anchor(anchor);
2388            }
2389            self.clamp_offset(viewport.height());
2390        }
2391
2392        self.sync_scroll_state(ctx, viewport.size);
2393        self.apply_pending_scroll(viewport.height());
2394        if self.state.is_following_end() {
2395            self.offset_y = (self.content_height() - viewport.height()).max(0.0);
2396        }
2397        self.clamp_offset(viewport.height());
2398        self.active_range = self.visible_range(viewport.height(), self.offset_y);
2399        self.evict_rows();
2400        self.publish_viewport(viewport.height());
2401
2402        let max_offset = self.state.scroll.max_offset();
2403        if let Some(bars) = &mut self.bars {
2404            bars.set_visibility(ScrollAxes::Vertical, max_offset);
2405            bars.measure(ctx, size, theme.metrics.scroll_bar_thickness);
2406        }
2407        size
2408    }
2409
2410    fn arrange(&mut self, ctx: &mut ArrangeCtx, bounds: Rect) {
2411        let theme = self.sync_scroll_bar_theme();
2412        let viewport = self.viewport_rect(bounds);
2413        let row_padding = self.resolved_row_padding();
2414        self.offset_y = self.state.scroll.current_offset().y;
2415        let previous_offset = self.offset_y;
2416        self.sync_scroll_state(ctx, viewport.size);
2417        self.apply_pending_scroll(viewport.height());
2418        if self.state.is_following_end() {
2419            self.offset_y = (self.content_height() - viewport.height()).max(0.0);
2420        }
2421        self.clamp_offset(viewport.height());
2422        let next_range = self.visible_range(viewport.height(), self.offset_y);
2423        if next_range != self.active_range
2424            && next_range.clone().any(|index| {
2425                self.keys
2426                    .get(index)
2427                    .is_some_and(|key| !self.realized.contains_key(key))
2428            })
2429        {
2430            ctx.request(InvalidationRequest::new(
2431                InvalidationTarget::Widget(ctx.widget_id()),
2432                InvalidationKind::Measure,
2433            ));
2434        }
2435        self.active_range = next_range;
2436        if (previous_offset - self.offset_y).abs() > f32::EPSILON {
2437            ctx.request_paint();
2438            ctx.request_semantics();
2439        }
2440
2441        for key in self.child_keys_for_graph() {
2442            let Some(index) = self.index_by_key.get(&key).copied() else {
2443                continue;
2444            };
2445            let Some(rect) = self.row_rect(bounds, index) else {
2446                continue;
2447            };
2448            if let Some(row) = self.realized.get_mut(&key) {
2449                let child_height = row.pod.measured_size().height;
2450                row.pod.arrange(
2451                    ctx,
2452                    Rect::from_origin_size(
2453                        Point::new(rect.x() + row_padding.left, rect.y() + row_padding.top),
2454                        Size::new(
2455                            (rect.width() - row_padding.left - row_padding.right).max(0.0),
2456                            child_height,
2457                        ),
2458                    ),
2459                );
2460            }
2461        }
2462
2463        let max_offset = self.state.scroll.max_offset();
2464        if let Some(bars) = &mut self.bars {
2465            bars.set_visibility(ScrollAxes::Vertical, max_offset);
2466            bars.arrange(ctx, bounds, theme.metrics.scroll_bar_thickness);
2467        }
2468        self.publish_viewport(viewport.height());
2469    }
2470
2471    fn paint(&self, ctx: &mut PaintCtx) {
2472        self.sync_focused_row(ctx.focused_widget_id());
2473        self.sync_scroll_bar_theme();
2474        let theme = self.resolved_theme();
2475        let viewport = self.viewport_rect(ctx.bounds());
2476        let selected = self.state.selected_key();
2477        if self.chrome == VirtualListChrome::Default {
2478            draw_surface(ctx, ctx.bounds(), &theme, 0.0);
2479        }
2480        ctx.push_clip_rect(viewport);
2481        for index in self.active_range.clone() {
2482            let Some(key) = self.keys.get(index) else {
2483                continue;
2484            };
2485            let Some(row) = self.realized.get(key) else {
2486                continue;
2487            };
2488            let Some(rect) = self.row_rect(ctx.bounds(), index) else {
2489                continue;
2490            };
2491            if self.chrome == VirtualListChrome::Default {
2492                paint_data_row_state(
2493                    ctx,
2494                    rect,
2495                    viewport,
2496                    &theme,
2497                    self.selection_mode == VirtualListSelectionMode::Single
2498                        && selected.as_ref() == Some(key),
2499                    (self.hovered.as_ref() == Some(key)) as u8 as f32,
2500                    (self.pressed.as_ref() == Some(key)) as u8 as f32,
2501                );
2502            }
2503            row.pod.paint(ctx);
2504        }
2505        ctx.pop_clip();
2506        if let Some(bars) = &self.bars {
2507            ctx.push_clip_rect(ctx.bounds());
2508            bars.paint(ctx);
2509            ctx.pop_clip();
2510        }
2511    }
2512
2513    fn layer_options(&self) -> LayerOptions {
2514        LayerOptions {
2515            paint_boundary: PaintBoundaryMode::Explicit,
2516            composition_mode: LayerCompositionMode::Scroll,
2517        }
2518    }
2519
2520    fn semantics(&self, ctx: &mut SemanticsCtx) {
2521        let loaded_count = self.keys.len();
2522        let visible_start = self.active_range.start.min(loaded_count);
2523        let visible_end = self.active_range.end.min(loaded_count);
2524        let global_start = self.window.loaded_range.start.saturating_add(visible_start);
2525        let global_end = self.window.loaded_range.start.saturating_add(visible_end);
2526        let mut list = SemanticsNode::new(ctx.widget_id(), SemanticsRole::List, ctx.bounds());
2527        list.name = Some(self.name.clone());
2528        list.state.focused = ctx.is_focused();
2529        list.value = Some(SemanticsValue::Text(match self.window.total_count {
2530            Some(total_count) => format!("{total_count} items"),
2531            None => format!("{loaded_count} loaded items"),
2532        }));
2533        list.description = Some(match (loaded_count, self.window.total_count) {
2534            (0, Some(0)) => "Empty collection".to_string(),
2535            (0, Some(total_count)) => {
2536                format!("No loaded items of {total_count}; more items are available")
2537            }
2538            (0, None) => "No loaded items".to_string(),
2539            (_, Some(total_count)) => format!(
2540                "Showing items {} through {} of {}; loaded window {} through {}",
2541                global_start.saturating_add(1).min(total_count),
2542                global_end
2543                    .max(global_start.saturating_add(1))
2544                    .min(total_count),
2545                total_count,
2546                self.window.loaded_range.start.saturating_add(1),
2547                self.window.loaded_range.end,
2548            ),
2549            (_, None) => format!(
2550                "Showing loaded items {} through {}; {} loaded",
2551                global_start + 1,
2552                global_end.max(global_start + 1),
2553                loaded_count,
2554            ),
2555        });
2556        list.actions = vec![
2557            SemanticsAction::Focus,
2558            SemanticsAction::Increment,
2559            SemanticsAction::Decrement,
2560        ];
2561        ctx.push(list);
2562
2563        let selected = self.state.selected_key();
2564        for index in self.active_range.clone() {
2565            let Some(key) = self.keys.get(index) else {
2566                continue;
2567            };
2568            let Some(row) = self.realized.get(key) else {
2569                continue;
2570            };
2571            let Some(id) = self.semantic_ids.get(key).copied() else {
2572                continue;
2573            };
2574            let Some(rect) = self.row_rect(ctx.bounds(), index) else {
2575                continue;
2576            };
2577            let item = row.value.get();
2578            let mut node = SemanticsNode::new(id, SemanticsRole::ListItem, rect);
2579            node.parent = Some(ctx.widget_id());
2580            node.name = Some(
2581                self.row_name
2582                    .as_ref()
2583                    .map(|name| name(key, &item))
2584                    .unwrap_or_else(|| format!("Item {}", index + 1)),
2585            );
2586            let global_index = self.window.loaded_range.start.saturating_add(index);
2587            let position = self.window.total_count.map_or_else(
2588                || format!("Loaded item {}", global_index + 1),
2589                |total_count| format!("Item {} of {total_count}", global_index + 1),
2590            );
2591            node.description = Some(
2592                self.row_description
2593                    .as_ref()
2594                    .map(|description| format!("{}; {position}", description(key, &item)))
2595                    .unwrap_or(position),
2596            );
2597            node.state.selected = self.selection_mode == VirtualListSelectionMode::Single
2598                && selected.as_ref() == Some(key);
2599            node.state.hovered = self.hovered.as_ref() == Some(key);
2600            node.actions = vec![SemanticsAction::Focus];
2601            if self.selection_mode == VirtualListSelectionMode::Single {
2602                node.actions.push(SemanticsAction::Activate);
2603            }
2604            ctx.push(node);
2605            row.pod.semantics(ctx);
2606        }
2607        if let Some(bars) = &self.bars {
2608            bars.semantics(ctx);
2609        }
2610    }
2611
2612    fn accepts_focus(&self) -> bool {
2613        true
2614    }
2615
2616    fn focus_changed(&mut self, ctx: &mut EventCtx, _focused: bool) {
2617        ctx.request_paint();
2618        ctx.request_semantics();
2619    }
2620
2621    fn visit_children(&self, visitor: &mut dyn WidgetPodVisitor) {
2622        for key in self.child_keys_for_graph() {
2623            if let Some(row) = self.realized.get(&key) {
2624                visitor.visit(&row.pod);
2625            }
2626        }
2627        if let Some(bars) = &self.bars {
2628            bars.visit_children(visitor);
2629        }
2630    }
2631
2632    fn visit_children_mut(&mut self, visitor: &mut dyn WidgetPodMutVisitor) {
2633        let keys = self.child_keys_for_graph();
2634        for key in keys {
2635            if let Some(row) = self.realized.get_mut(&key) {
2636                visitor.visit(&mut row.pod);
2637            }
2638        }
2639        if let Some(bars) = &mut self.bars {
2640            bars.visit_children_mut(visitor);
2641        }
2642    }
2643}
2644
2645fn scroll_delta_to_offset(delta: ScrollDelta) -> Vector {
2646    match delta {
2647        ScrollDelta::Lines(delta) => Vector::new(delta.x * 40.0, delta.y * 40.0),
2648        ScrollDelta::Pixels(delta) => delta,
2649    }
2650}
2651
2652fn pod_contains_widget(pod: &WidgetPod, target: WidgetId) -> bool {
2653    struct Finder {
2654        target: WidgetId,
2655        found: bool,
2656    }
2657
2658    impl WidgetPodVisitor for Finder {
2659        fn visit(&mut self, child: &WidgetPod) {
2660            if self.found {
2661                return;
2662            }
2663            if child.id() == self.target {
2664                self.found = true;
2665            } else {
2666                child.visit_children(self);
2667            }
2668        }
2669    }
2670
2671    if pod.id() == target {
2672        return true;
2673    }
2674    let mut finder = Finder {
2675        target,
2676        found: false,
2677    };
2678    pod.visit_children(&mut finder);
2679    finder.found
2680}
2681
2682trait SaturatingSubF32 {
2683    fn saturating_sub(self, other: Self) -> Self;
2684}
2685
2686impl SaturatingSubF32 for f32 {
2687    fn saturating_sub(self, other: Self) -> Self {
2688        (self - other).max(0.0)
2689    }
2690}
2691
2692#[cfg(test)]
2693mod tests {
2694    use std::{cell::Cell, rc::Rc, sync::Arc};
2695
2696    use super::{
2697        CollectionChange, CollectionDelta, CollectionExtentIndex, CollectionSync, CollectionWindow,
2698        ScrollAlignment, VirtualCollectionModel, VirtualCollectionSource, VirtualList,
2699        VirtualListChrome, VirtualListSelectionMode, VirtualListState,
2700    };
2701    use crate::{DefaultTheme, SizedBox};
2702    use sui_core::{
2703        Color, Event, KeyState, KeyboardEvent, Point, PointerEvent, PointerEventKind, Rect, Result,
2704        ScrollDelta, SemanticsActionRequest, SemanticsNode, SemanticsRole, Size, Vector,
2705    };
2706    use sui_layout::Constraints;
2707    use sui_reactive::{Observable, Observer, SourceId, Subscription};
2708    use sui_runtime::{
2709        Application, MeasureCtx, PaintCtx, Runtime, SemanticsCtx, Widget, WindowBuilder,
2710    };
2711
2712    struct RowBox {
2713        value: sui_reactive::Signal<(u64, f32)>,
2714    }
2715
2716    #[derive(Clone)]
2717    struct WindowedRows {
2718        model: VirtualCollectionModel<u64, (u64, f32)>,
2719        window: CollectionWindow,
2720    }
2721
2722    impl Observable<u64> for WindowedRows {
2723        fn source_id(&self) -> SourceId {
2724            self.model.source_id()
2725        }
2726
2727        fn source_name(&self) -> Arc<str> {
2728            self.model.source_name()
2729        }
2730
2731        fn get(&self) -> u64 {
2732            self.model.get()
2733        }
2734
2735        fn subscribe(&self, observer: Observer) -> Subscription {
2736            self.model.subscribe(observer)
2737        }
2738    }
2739
2740    impl VirtualCollectionSource<u64, (u64, f32)> for WindowedRows {
2741        fn revision(&self) -> u64 {
2742            self.model.revision()
2743        }
2744
2745        fn keys(&self) -> Vec<u64> {
2746            self.model.keys()
2747        }
2748
2749        fn item(&self, key: &u64) -> Option<(u64, f32)> {
2750            self.model.item(key)
2751        }
2752
2753        fn changes_since(&self, revision: u64) -> CollectionSync<u64> {
2754            self.model.changes_since(revision)
2755        }
2756
2757        fn window(&self) -> CollectionWindow {
2758            self.window.clone()
2759        }
2760    }
2761
2762    impl Widget for RowBox {
2763        fn measure(&mut self, ctx: &mut MeasureCtx, constraints: Constraints) -> Size {
2764            let (_, height) = ctx.observe(&self.value);
2765            constraints.clamp(Size::new(constraints.max.width, height))
2766        }
2767
2768        fn paint(&self, ctx: &mut PaintCtx) {
2769            let (index, _) = self.value.get();
2770            let color = if index.is_multiple_of(2) {
2771                Color::rgba(0.2, 0.4, 0.8, 1.0)
2772            } else {
2773                Color::rgba(0.3, 0.6, 0.4, 1.0)
2774            };
2775            ctx.fill_rect(ctx.bounds(), color);
2776        }
2777
2778        fn semantics(&self, ctx: &mut SemanticsCtx) {
2779            let (index, _) = self.value.get();
2780            let mut node = SemanticsNode::new(
2781                ctx.widget_id(),
2782                SemanticsRole::GenericContainer,
2783                ctx.bounds(),
2784            );
2785            node.name = Some(format!("Row {index}"));
2786            ctx.push(node);
2787        }
2788    }
2789
2790    fn build_runtime<W>(root: W) -> (Runtime, sui_core::WindowId)
2791    where
2792        W: Widget + 'static,
2793    {
2794        let runtime = Application::new()
2795            .window(WindowBuilder::new().title("Virtual list").root(root))
2796            .build()
2797            .unwrap();
2798        let window_id = runtime.window_ids()[0];
2799        (runtime, window_id)
2800    }
2801
2802    #[test]
2803    fn extent_index_supports_incremental_prefix_operations() {
2804        let mut index = CollectionExtentIndex::new();
2805        index.rebuild([10.0, 20.0, 30.0]);
2806        assert_eq!(index.total(), 60.0);
2807        assert_eq!(index.offset_of(2), 30.0);
2808        assert_eq!(index.index_at_offset(29.0), Some(1));
2809
2810        index.insert(1, 5.0);
2811        assert_eq!(index.total(), 65.0);
2812        assert_eq!(index.offset_of(2), 15.0);
2813        assert_eq!(index.remove(2), Some(20.0));
2814        assert_eq!(index.total(), 45.0);
2815        assert!(index.update(1, 15.0));
2816        assert_eq!(index.total(), 55.0);
2817        assert!(index.move_item(0, 2));
2818        assert_eq!(index.offset_of(2), 45.0);
2819    }
2820
2821    #[test]
2822    fn collection_window_normalizes_count_without_inventing_page_availability() {
2823        let window = CollectionWindow::loaded(50..60, Some(100), false, false)
2824            .normalized_for_loaded_count(5);
2825        assert_eq!(window.loaded_range, 50..55);
2826        assert_eq!(window.total_count, Some(100));
2827        assert!(!window.has_before);
2828        assert!(!window.has_after);
2829    }
2830
2831    #[test]
2832    fn extent_index_matches_vec_under_mixed_edits() {
2833        let mut index = CollectionExtentIndex::new();
2834        let mut expected = Vec::<f32>::new();
2835        let mut random = 0x5eed_cafe_f00d_u64;
2836        let mut next_random = || {
2837            random = random
2838                .wrapping_mul(6_364_136_223_846_793_005)
2839                .wrapping_add(1_442_695_040_888_963_407);
2840            random
2841        };
2842
2843        for _ in 0..2_000 {
2844            match next_random() % 4 {
2845                0 | 1 => {
2846                    let insertion = (next_random() as usize) % (expected.len() + 1);
2847                    let extent = (next_random() % 96 + 1) as f32;
2848                    expected.insert(insertion, extent);
2849                    index.insert(insertion, extent);
2850                }
2851                2 if !expected.is_empty() => {
2852                    let removal = (next_random() as usize) % expected.len();
2853                    assert_eq!(index.remove(removal), Some(expected.remove(removal)));
2854                }
2855                3 if !expected.is_empty() => {
2856                    let changed = (next_random() as usize) % expected.len();
2857                    let extent = (next_random() % 96 + 1) as f32;
2858                    let expected_changed = expected[changed] != extent;
2859                    expected[changed] = extent;
2860                    assert_eq!(index.update(changed, extent), expected_changed);
2861                }
2862                _ => {}
2863            }
2864
2865            if expected.len() > 1 && next_random().is_multiple_of(5) {
2866                let from = (next_random() as usize) % expected.len();
2867                let to = (next_random() as usize) % expected.len();
2868                if from != to {
2869                    let extent = expected.remove(from);
2870                    expected.insert(to, extent);
2871                    assert!(index.move_item(from, to));
2872                }
2873            }
2874
2875            assert_eq!(index.len(), expected.len());
2876            assert_eq!(index.total(), expected.iter().sum::<f32>());
2877            for offset_index in 0..=expected.len() {
2878                assert_eq!(
2879                    index.offset_of(offset_index),
2880                    expected[..offset_index].iter().sum::<f32>()
2881                );
2882            }
2883            for (item_index, extent) in expected.iter().enumerate() {
2884                let midpoint = expected[..item_index].iter().sum::<f32>() + (*extent * 0.5);
2885                assert_eq!(index.index_at_offset(midpoint), Some(item_index));
2886            }
2887        }
2888    }
2889
2890    #[test]
2891    fn model_reports_incremental_key_changes() {
2892        let model =
2893            VirtualCollectionModel::from_items("items", [(1_u64, "one"), (2, "two")]).unwrap();
2894        let revision = model.revision();
2895        assert!(model.append(3, "three").unwrap());
2896        assert!(model.update(2, "second").unwrap());
2897        assert!(model.move_to(3, 0).unwrap());
2898
2899        assert_eq!(
2900            model.changes_since(revision),
2901            CollectionSync::Incremental {
2902                revision: model.revision(),
2903                changes: vec![
2904                    CollectionDelta::Inserted {
2905                        index: 2,
2906                        keys: vec![3],
2907                    },
2908                    CollectionDelta::Updated { key: 2 },
2909                    CollectionDelta::Moved { key: 3, index: 0 },
2910                ],
2911            }
2912        );
2913    }
2914
2915    #[test]
2916    fn model_rejects_duplicate_keys_atomically() {
2917        let model = VirtualCollectionModel::<u64, String>::new();
2918        assert!(
2919            model
2920                .apply(CollectionChange::Insert {
2921                    index: 0,
2922                    items: vec![(1, "one".into()), (1, "duplicate".into())],
2923                })
2924                .is_err()
2925        );
2926        assert!(model.is_empty());
2927    }
2928
2929    #[test]
2930    fn appending_rows_does_not_rehash_the_existing_collection() {
2931        use std::hash::{Hash, Hasher};
2932        use std::sync::atomic::{AtomicUsize, Ordering};
2933
2934        static HASHES: AtomicUsize = AtomicUsize::new(0);
2935        #[derive(Clone, PartialEq, Eq)]
2936        struct Key(usize);
2937        impl Hash for Key {
2938            fn hash<H: Hasher>(&self, state: &mut H) {
2939                HASHES.fetch_add(1, Ordering::Relaxed);
2940                self.0.hash(state);
2941            }
2942        }
2943
2944        for count in [1_024, 8_192] {
2945            let model = VirtualCollectionModel::from_items(
2946                "rows",
2947                (0..count).map(|index| (Key(index), index)),
2948            )
2949            .unwrap();
2950            HASHES.store(0, Ordering::Relaxed);
2951            model.append(Key(count), count).unwrap();
2952            assert!(HASHES.load(Ordering::Relaxed) < 32);
2953            assert_eq!(model.item(&Key(0)), Some(0));
2954            assert_eq!(model.item(&Key(count - 1)), Some(count - 1));
2955            assert_eq!(model.item(&Key(count)), Some(count));
2956        }
2957    }
2958
2959    #[test]
2960    fn middle_insert_preserves_key_lookups_and_reports_the_inserted_range() {
2961        let model = VirtualCollectionModel::from_items("rows", [(1, "one"), (4, "four")]).unwrap();
2962        let revision = model.revision();
2963        model
2964            .apply(CollectionChange::Insert {
2965                index: 1,
2966                items: vec![(2, "two"), (3, "three")],
2967            })
2968            .unwrap();
2969        assert_eq!(model.keys(), vec![1, 2, 3, 4]);
2970        for (key, value) in [(1, "one"), (2, "two"), (3, "three"), (4, "four")] {
2971            assert_eq!(model.item(&key), Some(value));
2972        }
2973        assert_eq!(
2974            model.changes_since(revision),
2975            CollectionSync::Incremental {
2976                revision: model.revision(),
2977                changes: vec![CollectionDelta::Inserted {
2978                    index: 1,
2979                    keys: vec![2, 3]
2980                }],
2981            }
2982        );
2983    }
2984
2985    #[test]
2986    fn model_resets_consumers_that_fall_behind_the_bounded_journal() {
2987        let model = VirtualCollectionModel::<u64, u64>::new();
2988        let revision = model.revision();
2989        for key in 0..=super::COLLECTION_JOURNAL_LIMIT as u64 {
2990            model.append(key, key).unwrap();
2991        }
2992
2993        assert!(matches!(
2994            model.changes_since(revision),
2995            CollectionSync::Reset { keys, .. }
2996                if keys.len() == super::COLLECTION_JOURNAL_LIMIT + 1
2997        ));
2998    }
2999
3000    #[test]
3001    fn virtual_list_scrollbar_gutter_resizes_retained_rows_without_losing_selection() {
3002        let model = VirtualCollectionModel::from_items(
3003            "rows",
3004            [(1_u64, (1, 40.0)), (2, (2, 40.0)), (3, (3, 40.0))],
3005        )
3006        .unwrap();
3007        let state = VirtualListState::new();
3008        state.select(Some(1));
3009        let (mut runtime, window_id) = build_runtime(
3010            SizedBox::new().size(Size::new(120.0, 80.0)).child(
3011                VirtualList::new("Rows", model.clone(), |_key, value| RowBox { value })
3012                    .padding(sui_layout::Padding::ZERO)
3013                    .row_padding(sui_layout::Padding::ZERO)
3014                    .state(state.clone()),
3015            ),
3016        );
3017        let before = runtime.render(window_id).unwrap();
3018        let row = before
3019            .semantics
3020            .iter()
3021            .find(|node| node.name.as_deref() == Some("Row 1"))
3022            .unwrap();
3023        let row_id = row.id;
3024        let bar = before
3025            .semantics
3026            .iter()
3027            .find(|node| node.name.as_deref() == Some("Rows vertical scroll bar"))
3028            .unwrap();
3029        assert_eq!(row.bounds.max_x(), bar.bounds.x());
3030        assert_eq!(state.selected_key(), Some(1));
3031        model.replace([(1, (1, 40.0))]).unwrap();
3032        let after = runtime.render(window_id).unwrap();
3033        let row = after
3034            .semantics
3035            .iter()
3036            .find(|node| node.id == row_id)
3037            .expect("row retained");
3038        assert_eq!(row.bounds.width(), 120.0);
3039        assert_eq!(state.selected_key(), Some(1));
3040        assert!(
3041            after
3042                .semantics
3043                .iter()
3044                .all(|node| node.role != SemanticsRole::Slider)
3045        );
3046    }
3047
3048    #[test]
3049    fn virtual_list_realizes_only_a_bounded_visible_window() {
3050        let model = VirtualCollectionModel::from_items(
3051            "rows",
3052            (0_u64..1_000).map(|index| (index, (index, 20.0))),
3053        )
3054        .unwrap();
3055        let builds = Rc::new(Cell::new(0));
3056        let build_count = Rc::clone(&builds);
3057        let list = VirtualList::new("Rows", model, move |_key, value| {
3058            build_count.set(build_count.get() + 1);
3059            RowBox { value }
3060        })
3061        .estimated_row_height(20.0)
3062        .overscan_viewports(0.5);
3063        let (mut runtime, window_id) =
3064            build_runtime(SizedBox::new().size(Size::new(240.0, 100.0)).child(list));
3065
3066        runtime.render(window_id).unwrap();
3067        assert!(
3068            builds.get() < 30,
3069            "virtual list should not realize all rows; realized {}",
3070            builds.get()
3071        );
3072        let inspector = runtime.inspector_snapshot(window_id).unwrap();
3073        let diagnostics = inspector
3074            .widget_diagnostics
3075            .iter()
3076            .find(|diagnostics| diagnostics.widget_name.contains("VirtualList"))
3077            .expect("virtual list should publish on-demand inspector counters");
3078        assert!(
3079            diagnostics
3080                .entries
3081                .iter()
3082                .any(|entry| entry.name == "realized rows")
3083        );
3084        assert!(
3085            diagnostics
3086                .entries
3087                .iter()
3088                .any(|entry| { entry.name == "total items" && entry.value == "1000" })
3089        );
3090    }
3091
3092    #[test]
3093    fn virtual_list_applies_theme_row_padding_to_custom_content() {
3094        let theme = DefaultTheme::default();
3095        let viewport_padding = theme.metrics.data_viewport_padding;
3096        let row_padding = theme.metrics.data_row_padding;
3097        let model = VirtualCollectionModel::from_items("rows", [(0_u64, (0_u64, 20.0))]).unwrap();
3098        let list = VirtualList::new("Rows", model, |_key, value| RowBox { value })
3099            .estimated_row_height(20.0);
3100        let (mut runtime, window_id) =
3101            build_runtime(SizedBox::new().size(Size::new(240.0, 100.0)).child(list));
3102
3103        let output = runtime.render(window_id).unwrap();
3104        let row = output
3105            .semantics
3106            .iter()
3107            .find(|node| node.name.as_deref() == Some("Row 0"))
3108            .expect("custom row semantics");
3109
3110        assert_eq!(row.bounds.x(), viewport_padding.left + row_padding.left);
3111        assert_eq!(
3112            row.bounds.width(),
3113            240.0
3114                - viewport_padding.left
3115                - viewport_padding.right
3116                - row_padding.left
3117                - row_padding.right
3118        );
3119        assert_eq!(row.bounds.y(), viewport_padding.top + row_padding.top);
3120        assert_eq!(row.bounds.height(), 20.0);
3121    }
3122
3123    #[test]
3124    fn prepend_preserves_the_visible_key_anchor() {
3125        let model = VirtualCollectionModel::from_items(
3126            "rows",
3127            (10_u64..30).map(|index| (index, (index, 20.0))),
3128        )
3129        .unwrap();
3130        let state = VirtualListState::new();
3131        state.scroll_to(15, ScrollAlignment::Start);
3132        let list = VirtualList::new("Rows", model.clone(), |_key, value| RowBox { value })
3133            .state(state.clone())
3134            .estimated_row_height(20.0)
3135            .overscan_viewports(0.0);
3136        let (mut runtime, window_id) =
3137            build_runtime(SizedBox::new().size(Size::new(240.0, 100.0)).child(list));
3138        runtime.render(window_id).unwrap();
3139        let before = state.scroll_state().current_offset().y;
3140        assert_eq!(before, 100.0);
3141
3142        model
3143            .prepend((0_u64..10).map(|index| (index, (index, 20.0))))
3144            .unwrap();
3145        runtime.render(window_id).unwrap();
3146
3147        assert_eq!(state.scroll_state().current_offset().y, before + 200.0);
3148    }
3149
3150    #[test]
3151    fn follow_end_tracks_appends_until_user_scrolls_away() -> Result<()> {
3152        let model = VirtualCollectionModel::from_items(
3153            "rows",
3154            (0_u64..20).map(|index| (index, (index, 20.0))),
3155        )
3156        .unwrap();
3157        let state = VirtualListState::new();
3158        let list = VirtualList::new("Rows", model.clone(), |_key, value| RowBox { value })
3159            .state(state.clone())
3160            .stick_to_end(true)
3161            .estimated_row_height(20.0);
3162        let (mut runtime, window_id) =
3163            build_runtime(SizedBox::new().size(Size::new(240.0, 100.0)).child(list));
3164        runtime.render(window_id)?;
3165        assert_eq!(
3166            state.scroll_state().current_offset().y,
3167            state.scroll_state().max_offset().y
3168        );
3169
3170        model.append(20, (20, 20.0)).unwrap();
3171        runtime.render(window_id)?;
3172        assert_eq!(
3173            state.scroll_state().current_offset().y,
3174            state.scroll_state().max_offset().y
3175        );
3176
3177        let mut scroll = PointerEvent::new(PointerEventKind::Scroll, Point::new(100.0, 50.0));
3178        scroll.scroll_delta = Some(ScrollDelta::Pixels(Vector::new(0.0, 80.0)));
3179        runtime.handle_event(window_id, Event::Pointer(scroll))?;
3180        runtime.render(window_id)?;
3181        assert!(!state.is_following_end());
3182        let away = state.scroll_state().current_offset().y;
3183
3184        model.append(21, (21, 20.0)).unwrap();
3185        runtime.render(window_id)?;
3186        assert_eq!(state.scroll_state().current_offset().y, away);
3187        Ok(())
3188    }
3189
3190    #[test]
3191    fn keyboard_selection_uses_stable_keys_and_semantics_reports_range() -> Result<()> {
3192        let model = VirtualCollectionModel::from_items(
3193            "rows",
3194            (0_u64..20).map(|index| (index, (index, 20.0))),
3195        )
3196        .unwrap();
3197        let state = VirtualListState::new();
3198        let list = VirtualList::new("Rows", model, |_key, value| RowBox { value })
3199            .state(state.clone())
3200            .estimated_row_height(20.0)
3201            .row_name(|key, _| format!("Row {key}"));
3202        let (mut runtime, window_id) =
3203            build_runtime(SizedBox::new().size(Size::new(240.0, 100.0)).child(list));
3204        let output = runtime.render(window_id)?;
3205        let list_id = output
3206            .semantics
3207            .iter()
3208            .find(|node| node.role == SemanticsRole::List)
3209            .expect("list semantics")
3210            .id;
3211        runtime.handle_semantics_action(window_id, list_id, SemanticsActionRequest::Focus)?;
3212        runtime.handle_event(
3213            window_id,
3214            Event::Keyboard(KeyboardEvent::new("ArrowDown", KeyState::Pressed)),
3215        )?;
3216        assert_eq!(state.selected_key(), Some(1));
3217
3218        let output = runtime.render(window_id)?;
3219        let list = output
3220            .semantics
3221            .iter()
3222            .find(|node| node.role == SemanticsRole::List)
3223            .expect("list semantics");
3224        assert_eq!(
3225            list.value,
3226            Some(sui_core::SemanticsValue::Text("20 items".into()))
3227        );
3228        assert!(
3229            list.description
3230                .as_deref()
3231                .is_some_and(|description| description.contains("of 20"))
3232        );
3233        Ok(())
3234    }
3235
3236    #[test]
3237    fn windowed_list_reports_dataset_space_viewport_and_total() -> Result<()> {
3238        let model = VirtualCollectionModel::from_items(
3239            "rows",
3240            (400_u64..800).map(|index| (index, (index, 20.0))),
3241        )
3242        .unwrap();
3243        let source = WindowedRows {
3244            model,
3245            window: CollectionWindow::loaded(400..800, Some(1_200), true, true),
3246        };
3247        let state = VirtualListState::new();
3248        let list = VirtualList::new("History", source, |_key, value| RowBox { value })
3249            .state(state.clone())
3250            .estimated_row_height(20.0)
3251            .overscan_viewports(0.0);
3252        let (mut runtime, window_id) =
3253            build_runtime(SizedBox::new().size(Size::new(240.0, 100.0)).child(list));
3254
3255        let output = runtime.render(window_id)?;
3256        let viewport = state.viewport();
3257        assert_eq!(viewport.loaded_range, 400..800);
3258        assert_eq!(viewport.visible_range.start, 400);
3259        assert!(viewport.visible_range.end <= 406);
3260        assert_eq!(viewport.total_count, Some(1_200));
3261        assert!(viewport.has_before);
3262        assert!(viewport.has_after);
3263
3264        let list = output
3265            .semantics
3266            .iter()
3267            .find(|node| node.role == SemanticsRole::List)
3268            .expect("list semantics");
3269        assert_eq!(
3270            list.value,
3271            Some(sui_core::SemanticsValue::Text("1200 items".into()))
3272        );
3273        assert!(
3274            list.description
3275                .as_deref()
3276                .is_some_and(|description| description.contains("loaded window 401 through 800"))
3277        );
3278        Ok(())
3279    }
3280
3281    #[test]
3282    fn presentation_list_disables_selection_but_keeps_focus_semantics() -> Result<()> {
3283        let model = VirtualCollectionModel::from_items(
3284            "rows",
3285            (0_u64..4).map(|index| (index, (index, 20.0))),
3286        )
3287        .unwrap();
3288        let state = VirtualListState::new();
3289        let list = VirtualList::new("Transcript", model, |_key, value| RowBox { value })
3290            .state(state.clone())
3291            .selection_mode(VirtualListSelectionMode::None)
3292            .chrome(VirtualListChrome::Transparent)
3293            .estimated_row_height(20.0);
3294        let (mut runtime, window_id) =
3295            build_runtime(SizedBox::new().size(Size::new(240.0, 100.0)).child(list));
3296
3297        let output = runtime.render(window_id)?;
3298        let first_item = output
3299            .semantics
3300            .iter()
3301            .find(|node| node.role == SemanticsRole::ListItem)
3302            .expect("virtual row semantics");
3303        assert!(
3304            first_item
3305                .actions
3306                .contains(&sui_core::SemanticsAction::Focus)
3307        );
3308        assert!(
3309            !first_item
3310                .actions
3311                .contains(&sui_core::SemanticsAction::Activate)
3312        );
3313        assert!(!first_item.state.selected);
3314        assert_eq!(state.selected_key(), None);
3315        Ok(())
3316    }
3317
3318    #[test]
3319    fn contextual_selection_callback_receives_the_event_context() -> Result<()> {
3320        let model = VirtualCollectionModel::from_items("rows", [(7_u64, (7, 20.0))]).unwrap();
3321        let selected = Rc::new(Cell::new(None));
3322        let selected_key = Rc::clone(&selected);
3323        let list = VirtualList::new("Rows", model, |_key, value| RowBox { value })
3324            .estimated_row_height(20.0)
3325            .on_change_with_ctx(move |ctx, key| {
3326                selected_key.set(Some(key));
3327                ctx.request_semantics();
3328            });
3329        let (mut runtime, window_id) =
3330            build_runtime(SizedBox::new().size(Size::new(240.0, 100.0)).child(list));
3331
3332        let output = runtime.render(window_id)?;
3333        let item_id = output
3334            .semantics
3335            .iter()
3336            .find(|node| node.role == SemanticsRole::ListItem)
3337            .expect("virtual row semantics")
3338            .id;
3339        assert!(runtime.handle_semantics_action(
3340            window_id,
3341            item_id,
3342            SemanticsActionRequest::Activate,
3343        )?);
3344        assert_eq!(selected.get(), Some(7));
3345        Ok(())
3346    }
3347
3348    #[test]
3349    fn row_update_preserves_realized_widget_identity() {
3350        let model = VirtualCollectionModel::from_items("rows", [(1_u64, (1_u64, 20.0))]).unwrap();
3351        let list = VirtualList::new("Rows", model.clone(), |_key, value| RowBox { value })
3352            .estimated_row_height(20.0);
3353        let (mut runtime, window_id) =
3354            build_runtime(SizedBox::new().size(Size::new(240.0, 100.0)).child(list));
3355        let before_output = runtime.render(window_id).unwrap();
3356        let before = before_output
3357            .semantics
3358            .iter()
3359            .find(|node| node.name.as_deref() == Some("Row 1"))
3360            .expect("row widget")
3361            .id;
3362
3363        model.update(1, (1, 36.0)).unwrap();
3364        let output = runtime.render(window_id).unwrap();
3365        let after = output
3366            .semantics
3367            .iter()
3368            .find(|node| node.name.as_deref() == Some("Row 1"))
3369            .expect("row widget")
3370            .id;
3371        assert_eq!(before, after);
3372    }
3373
3374    #[test]
3375    fn pinned_rows_survive_cache_eviction() {
3376        let model = VirtualCollectionModel::from_items(
3377            "rows",
3378            (0_u64..100).map(|index| (index, (index, 20.0))),
3379        )
3380        .unwrap();
3381        let state = VirtualListState::new();
3382        state.pin(0);
3383        let list = VirtualList::new("Rows", model, |_key, value| RowBox { value })
3384            .state(state.clone())
3385            .estimated_row_height(20.0)
3386            .cache_capacity(0);
3387        let (mut runtime, window_id) =
3388            build_runtime(SizedBox::new().size(Size::new(240.0, 100.0)).child(list));
3389        let before = runtime.render(window_id).unwrap();
3390        let before_id = before
3391            .semantics
3392            .iter()
3393            .find(|node| node.name.as_deref() == Some("Row 0"))
3394            .expect("pinned row initially visible")
3395            .id;
3396        state.scroll_to(90, ScrollAlignment::Start);
3397        runtime.render(window_id).unwrap();
3398        state.scroll_to(0, ScrollAlignment::Start);
3399        let after = runtime.render(window_id).unwrap();
3400        let after_id = after
3401            .semantics
3402            .iter()
3403            .find(|node| node.name.as_deref() == Some("Row 0"))
3404            .expect("pinned row visible again")
3405            .id;
3406        assert_eq!(before_id, after_id);
3407    }
3408
3409    #[test]
3410    fn row_rects_use_variable_measured_heights() {
3411        let model = VirtualCollectionModel::from_items(
3412            "rows",
3413            [(0_u64, (0, 20.0)), (1, (1, 40.0)), (2, (2, 30.0))],
3414        )
3415        .unwrap();
3416        let list = VirtualList::new("Rows", model, |_key, value| RowBox { value })
3417            .estimated_row_height(24.0)
3418            .overscan_viewports(2.0);
3419        let (mut runtime, window_id) =
3420            build_runtime(SizedBox::new().size(Size::new(240.0, 100.0)).child(list));
3421        runtime.render(window_id).unwrap();
3422        let mut rows = runtime
3423            .render(window_id)
3424            .unwrap()
3425            .semantics
3426            .into_iter()
3427            .filter(|node| {
3428                node.role == SemanticsRole::GenericContainer
3429                    && node
3430                        .name
3431                        .as_deref()
3432                        .is_some_and(|name| name.starts_with("Row "))
3433            })
3434            .map(|node| node.bounds)
3435            .collect::<Vec<Rect>>();
3436        rows.sort_by(|left, right| left.y().total_cmp(&right.y()));
3437        assert_eq!(rows[0].height(), 20.0);
3438        assert_eq!(rows[1].height(), 40.0);
3439        assert_eq!(rows[2].height(), 30.0);
3440    }
3441}