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