Skip to main content

sui_widgets/
collection.rs

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