gpui_kit_grid/
highlight.rs

1//! Change highlight: packed stamps, the sparse stamps of a row and the fade
2//! policy. No GPUI types.
3//!
4//! Stamps are written by the ingest task for every operation. The view reads
5//! them for visible cells only and fades them on one global tick, so every
6//! hot cell changes its step on the same frames. A row keeps only the
7//! stamps that are still hot.
8
9use std::{sync::Arc, time::Duration};
10
11use crate::model::{ColumnIx, ColumnSet};
12
13/// What happened to the row when the stamp was written.
14#[derive(Clone, Copy, Debug, PartialEq, Eq)]
15#[non_exhaustive]
16pub enum RowChange {
17    /// The row was inserted.
18    Inserted,
19    /// The row was replaced and this column changed.
20    Updated,
21    /// The row was removed and fades out
22    /// ([`HighlightPolicy::with_removal_fade`]). Never stored in a cell
23    /// stamp: a fading row ([`StoreSnapshot::fading_row`]) carries its
24    /// removal stamp, which reads back as `Updated` without a direction.
25    ///
26    /// [`StoreSnapshot::fading_row`]: crate::StoreSnapshot::fading_row
27    Removed,
28}
29
30/// The direction of a changed numeric value (`GridRow::change_direction`).
31#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
32pub enum ChangeDirection {
33    /// The value rose.
34    Up,
35    /// The value fell.
36    Down,
37}
38
39/// A packed change stamp: milliseconds since the store epoch in the upper 30
40/// bits, the change in bits 0–1: `00` updated without a direction, `01`
41/// inserted, `10` updated up, `11` updated down. Zero means "never changed".
42#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
43pub struct Stamp(u32);
44
45impl Stamp {
46    /// No change recorded.
47    pub const NONE: Self = Self(0);
48    const MAX_MS: u32 = (1 << 30) - 1;
49    const CHANGE_BITS: u32 = 0b11;
50    const INSERTED: u32 = 0b01;
51    const UP: u32 = 0b10;
52    const DOWN: u32 = 0b11;
53
54    /// Creates a stamp of `change` without a direction. `ms` wraps after ~12
55    /// days of store uptime.
56    pub fn new(ms: u32, change: RowChange) -> Self {
57        Self::with_direction(ms, change, None)
58    }
59
60    /// Creates a stamp of `change` with a direction; `direction` counts only
61    /// for [`RowChange::Updated`]. `ms` wraps after ~12 days of store uptime.
62    ///
63    /// [`RowChange::Removed`] is not a cell's change: the store writes a
64    /// removal stamp for a fading row itself (a debug assertion).
65    pub fn with_direction(ms: u32, change: RowChange, direction: Option<ChangeDirection>) -> Self {
66        debug_assert!(
67            change != RowChange::Removed,
68            "a removal stamp is written by the store for a fading row"
69        );
70        let bits = match (change, direction) {
71            (RowChange::Inserted, _) => Self::INSERTED,
72            (RowChange::Updated, Some(ChangeDirection::Up)) => Self::UP,
73            (RowChange::Updated, Some(ChangeDirection::Down)) => Self::DOWN,
74            _ => 0,
75        };
76        Self::packed(ms, bits)
77    }
78
79    /// The removal stamp of a fading row: the time of removal, read back as
80    /// `Updated` without a direction.
81    pub(crate) fn removal(ms: u32) -> Self {
82        Self::packed(ms, 0)
83    }
84
85    fn packed(ms: u32, bits: u32) -> Self {
86        // Never zero, which is `NONE`.
87        let ms = (ms & Self::MAX_MS).max(1);
88        Self((ms << 2) | bits)
89    }
90
91    /// Returns true if a change was recorded.
92    pub fn is_set(self) -> bool {
93        self.0 != 0
94    }
95
96    /// Milliseconds since the store epoch.
97    pub fn ms(self) -> u32 {
98        self.0 >> 2
99    }
100
101    /// What happened to the row.
102    pub fn change(self) -> RowChange {
103        if self.0 & Self::CHANGE_BITS == Self::INSERTED {
104            RowChange::Inserted
105        } else {
106            RowChange::Updated
107        }
108    }
109
110    /// The direction of an update; `None` for an insert or an update with
111    /// no direction.
112    pub fn direction(self) -> Option<ChangeDirection> {
113        match self.0 & Self::CHANGE_BITS {
114            Self::UP => Some(ChangeDirection::Up),
115            Self::DOWN => Some(ChangeDirection::Down),
116            _ => None,
117        }
118    }
119}
120
121/// The change stamps of one row's cells while any of them is hot
122/// ([`StoreSnapshot::stamps`]).
123///
124/// The store keeps them sparse: a stamp for the whole row (the flash of an
125/// insert) and the stamps of the columns written since, without the ones
126/// that expired. [`Self::get`] reads the stamp of any cell in O(1), without
127/// allocating.
128///
129/// [`StoreSnapshot::stamps`]: crate::StoreSnapshot::stamps
130#[derive(Clone, Copy, Debug, PartialEq, Eq)]
131pub struct RowStamps<'a> {
132    /// The row's stamp, the column mask and the places of its words
133    /// ([`SparseStamps`]).
134    header: &'a [Stamp; HEADER],
135    /// One stamp per stamped column, in schema order.
136    stamps: &'a [Stamp],
137}
138
139impl RowStamps<'_> {
140    const EMPTY: RowStamps<'static> = RowStamps {
141        header: &[Stamp::NONE; HEADER],
142        stamps: &[],
143    };
144
145    /// The stamp of the cell of `column`: its own if the column was written
146    /// since the row's stamp, else the row's; [`Stamp::NONE`] if neither.
147    #[inline]
148    pub fn get(self, column: ColumnIx) -> Stamp {
149        let (ix, row) = (column.get(), self.header[ROW]);
150        if ix >= MAX_COLUMNS {
151            return row;
152        }
153        // One 32-bit word of the mask, and the place of its first stamp:
154        // no `u128` arithmetic on the paint path.
155        let word = ix / 32;
156        let (mask, bit) = (self.header[MASK + word].0, 1u32 << (ix % 32));
157        if mask & bit == 0 {
158            return row;
159        }
160        let first = (self.header[PLACES].0 >> (8 * word)) & 0xff;
161        let rank = first + (mask & (bit - 1)).count_ones();
162        self.stamps.get(rank as usize).copied().unwrap_or(row)
163    }
164
165    /// The stamp of every cell without one of its own.
166    fn row(self) -> Stamp {
167        self.header[ROW]
168    }
169
170    /// The columns with a stamp of their own.
171    fn columns(self) -> ColumnSet {
172        let bits = (0..MASK_WORDS).fold(0u128, |bits, word| {
173            bits | u128::from(self.header[MASK + word].0) << (32 * word)
174        });
175        ColumnSet::from_bits(bits)
176    }
177}
178
179/// The header of [`SparseStamps`]: the whole row's stamp, the column mask
180/// in four words (the low word first), and the places: byte `w` is the
181/// number of stamped columns in the words before word `w`.
182const ROW: usize = 0;
183const MASK: usize = 1;
184const MASK_WORDS: usize = 4;
185const PLACES: usize = MASK + MASK_WORDS;
186const HEADER: usize = PLACES + 1;
187/// The most columns a row has ([`ColumnSet`]).
188const MAX_COLUMNS: usize = 32 * MASK_WORDS;
189
190/// The change stamps of a hot row as the store keeps them: one allocation of
191/// a header (the row's stamp and the column mask) and one stamp per column
192/// of the mask, in schema order.
193///
194/// An insert is the row stamp alone. A write keeps the stamps of the
195/// columns still hot and drops the expired ones, so a row holds only what
196/// can still show.
197#[derive(Clone, Debug, PartialEq, Eq)]
198pub(crate) struct SparseStamps(Arc<[Stamp]>);
199
200impl SparseStamps {
201    /// Every cell of the row stamped `stamp`: the flash of an insert.
202    pub(crate) fn whole_row(stamp: Stamp) -> Self {
203        Self(Arc::new(Self::header(stamp, ColumnSet::EMPTY)))
204    }
205
206    /// `existing` (or none) with each of `columns` stamped
207    /// `stamp(column)`, keeping of `existing` only the stamps `is_hot`
208    /// keeps. `every` is every column of the row; a column outside it is
209    /// not stamped. One allocation; `None` if no stamp is left.
210    pub(crate) fn written(
211        existing: Option<&Self>,
212        columns: ColumnSet,
213        every: ColumnSet,
214        is_hot: impl Fn(Stamp) -> bool,
215        mut stamp: impl FnMut(ColumnIx) -> Stamp,
216    ) -> Option<Self> {
217        let columns = columns.intersection(every);
218        let old = existing.map_or(RowStamps::EMPTY, Self::view);
219        let old_columns = old.columns();
220        let mut touched = old_columns;
221        touched.union_with(columns);
222        // Built on the stack, then copied once into the allocation.
223        let mut words = [Stamp::NONE; HEADER + MAX_COLUMNS];
224        let (mut kept, mut count, mut old_ix) = (ColumnSet::EMPTY, 0, 0);
225        for column in touched.iter() {
226            let own = old_columns.contains(column).then(|| {
227                old_ix += 1;
228                old.stamps.get(old_ix - 1).copied().unwrap_or(Stamp::NONE)
229            });
230            let value = if columns.contains(column) {
231                stamp(column)
232            } else {
233                match own {
234                    Some(own) if is_hot(own) => own,
235                    _ => continue,
236                }
237            };
238            words[HEADER + count] = value;
239            kept.insert(column);
240            count += 1;
241        }
242        let mut row = if is_hot(old.row()) {
243            old.row()
244        } else {
245            Stamp::NONE
246        };
247        if kept == every {
248            // Every cell has its own stamp: the row's is never read, and
249            // the same stamp in every cell is the row's alone.
250            let first = words[HEADER];
251            let uniform = words[HEADER..HEADER + count]
252                .iter()
253                .all(|&stamp| stamp == first);
254            (row, kept, count) = if uniform {
255                (first, ColumnSet::EMPTY, 0)
256            } else {
257                (Stamp::NONE, kept, count)
258            };
259        }
260        if count == 0 && !row.is_set() {
261            return None;
262        }
263        words[..HEADER].copy_from_slice(&Self::header(row, kept));
264        Some(Self(Arc::from(&words[..HEADER + count])))
265    }
266
267    fn header(row: Stamp, columns: ColumnSet) -> [Stamp; HEADER] {
268        let bits = columns.bits();
269        let mut header = [Stamp::NONE; HEADER];
270        header[ROW] = row;
271        let mut before = 0;
272        for word in 0..MASK_WORDS {
273            let mask = (bits >> (32 * word)) as u32;
274            header[MASK + word] = Stamp(mask);
275            // At most 96 columns before the last word: a byte holds it.
276            header[PLACES].0 |= before << (8 * word);
277            before += mask.count_ones();
278        }
279        header
280    }
281
282    /// The stamps for reading.
283    #[inline]
284    pub(crate) fn view(&self) -> RowStamps<'_> {
285        match self.0.split_first_chunk::<HEADER>() {
286            Some((header, stamps)) => RowStamps { header, stamps },
287            None => RowStamps::EMPTY,
288        }
289    }
290
291    /// Returns true if no stamp of the row is hot: the store frees them.
292    pub(crate) fn is_cold(&self, is_hot: impl Fn(Stamp) -> bool) -> bool {
293        let stamps = self.view();
294        !is_hot(stamps.row()) && !stamps.stamps.iter().any(|&stamp| is_hot(stamp))
295    }
296
297    /// The bytes of the allocation, with its reference counts.
298    pub(crate) fn heap_bytes(&self) -> usize {
299        2 * size_of::<usize>() + size_of_val::<[Stamp]>(&self.0)
300    }
301}
302
303/// How long a change stays highlighted, in how many steps it fades, and how
304/// long a removed row fades out.
305///
306/// This is the default implementation of the `HighlightPolicy` seam.
307#[derive(Clone, Copy, Debug, PartialEq, Eq)]
308pub struct HighlightPolicy {
309    duration_ms: u32,
310    steps: u32,
311    removal_fade_ms: u32,
312}
313
314impl Default for HighlightPolicy {
315    fn default() -> Self {
316        Self::new(Duration::from_secs(5), 8)
317    }
318}
319
320impl HighlightPolicy {
321    /// A highlight that lasts `duration` and fades in `steps` steps. Removed
322    /// rows go at once.
323    pub fn new(duration: Duration, steps: u32) -> Self {
324        // Ages live in the 30-bit stamp ring; keep durations well inside it.
325        let duration_ms = duration.as_millis().clamp(1, u128::from(Stamp::MAX_MS / 4)) as u32;
326        let steps = steps.clamp(1, duration_ms);
327        Self {
328            duration_ms,
329            steps,
330            removal_fade_ms: 0,
331        }
332    }
333
334    /// Keeps a removed row on screen, fading, for `fade`, on the global tick
335    /// and steps of this policy. `Duration::ZERO`, the default, removes at
336    /// once. A store setting, like the duration: the store keeps the row in
337    /// its snapshots while it fades ([`StoreSnapshot::fading_row`]).
338    ///
339    /// [`StoreSnapshot::fading_row`]: crate::StoreSnapshot::fading_row
340    pub fn with_removal_fade(mut self, fade: Duration) -> Self {
341        self.removal_fade_ms = fade.as_millis().min(u128::from(Stamp::MAX_MS / 4)) as u32;
342        self
343    }
344
345    /// How long a removed row fades out; zero when it goes at once.
346    pub fn removal_fade(&self) -> Duration {
347        Duration::from_millis(self.removal_fade_ms.into())
348    }
349
350    /// The highlight duration in milliseconds.
351    pub fn duration_ms(&self) -> u32 {
352        self.duration_ms
353    }
354
355    /// The number of fade steps.
356    pub fn steps(&self) -> u32 {
357        self.steps
358    }
359
360    fn step_ms(&self) -> u32 {
361        (self.duration_ms / self.steps).max(1)
362    }
363
364    /// The global tick at or before `now_ms`. All cells are evaluated at the
365    /// same tick, so they change steps on the same frames.
366    pub fn tick(&self, now_ms: u32) -> u32 {
367        now_ms - now_ms % self.step_ms()
368    }
369
370    /// The next global tick after `now_ms`: the single deadline the view
371    /// waits for while any visible cell is hot.
372    pub fn next_tick(&self, now_ms: u32) -> u32 {
373        self.tick(now_ms) + self.step_ms()
374    }
375
376    /// The age of `stamp` at `now_ms`, computed in the 30-bit ring of the
377    /// stamp clock, so it stays right after the clock wraps (~12 days).
378    /// A stamp written after `now_ms` (ticks are floored) has age 0.
379    fn age(stamp: Stamp, now_ms: u32) -> u32 {
380        let age = (now_ms & Stamp::MAX_MS).wrapping_sub(stamp.ms()) & Stamp::MAX_MS;
381        if age > Stamp::MAX_MS / 2 { 0 } else { age }
382    }
383
384    /// Highlight intensity at `tick_ms`, from 1.0 (just changed) down to
385    /// `1 / steps`; `None` once the highlight expired.
386    pub fn intensity(&self, stamp: Stamp, tick_ms: u32) -> Option<f32> {
387        if !stamp.is_set() {
388            return None;
389        }
390        let age = Self::age(stamp, tick_ms);
391        if age >= self.duration_ms {
392            return None;
393        }
394        // Never 0.0: a hot cell is always visible.
395        let step = (age / self.step_ms()).min(self.steps - 1);
396        Some(1.0 - step as f32 / self.steps as f32)
397    }
398
399    /// Returns true if the stamp no longer highlights at `now_ms`.
400    pub fn is_expired(&self, stamp: Stamp, now_ms: u32) -> bool {
401        !stamp.is_set() || Self::age(stamp, now_ms) >= self.duration_ms
402    }
403
404    /// Returns true if `stamp` highlights at no tick from `now_ms` on: it
405    /// expired at the global tick of `now_ms`, and a frame reads at that
406    /// tick or a later one. The store drops such stamps; a stamp expired at
407    /// `now_ms` itself may still show its last step until the next tick.
408    pub(crate) fn is_highlight_over(&self, stamp: Stamp, now_ms: u32) -> bool {
409        self.is_expired(stamp, self.tick(now_ms))
410    }
411
412    /// The intensity of a fading row with the removal stamp `removed` at
413    /// `tick_ms`: from 1.0 (just removed) down in the steps of the global
414    /// tick that fit in [`Self::removal_fade`]; `None` once the fade ended,
415    /// and always without a removal fade.
416    pub fn removal_intensity(&self, removed: Stamp, tick_ms: u32) -> Option<f32> {
417        if self.is_removal_over(removed, tick_ms) {
418            return None;
419        }
420        let step_ms = self.step_ms();
421        let steps = self.removal_fade_ms.div_ceil(step_ms);
422        // The age is below the fade, so the step is below `steps`: never 0.0.
423        let step = Self::age(removed, tick_ms) / step_ms;
424        Some(1.0 - step as f32 / steps as f32)
425    }
426
427    /// Returns true if a row removed at `removed` no longer fades at
428    /// `now_ms`: the store drops it from its snapshots.
429    pub(crate) fn is_removal_over(&self, removed: Stamp, now_ms: u32) -> bool {
430        !removed.is_set() || Self::age(removed, now_ms) >= self.removal_fade_ms
431    }
432
433    /// Returns true if removed rows fade out.
434    pub(crate) fn has_removal_fade(&self) -> bool {
435        self.removal_fade_ms > 0
436    }
437}
438
439#[cfg(test)]
440mod tests {
441    use super::*;
442
443    #[test]
444    fn test_highlight_policy_steps_on_global_tick() {
445        let policy = HighlightPolicy::new(Duration::from_millis(800), 8);
446        let stamp = Stamp::new(1_050, RowChange::Updated);
447        assert_eq!(stamp.ms(), 1_050);
448        assert_eq!(stamp.change(), RowChange::Updated);
449        assert_eq!(
450            Stamp::new(7, RowChange::Inserted).change(),
451            RowChange::Inserted
452        );
453
454        // Ticks are aligned to 100 ms, whatever the stamp's own phase is.
455        assert_eq!(policy.tick(1_099), 1_000);
456        assert_eq!(policy.next_tick(1_099), 1_100);
457        // A change after the current tick shows at full intensity.
458        assert_eq!(policy.intensity(stamp, policy.tick(1_060)), Some(1.0));
459        assert_eq!(policy.intensity(stamp, 1_200), Some(1.0 - 1.0 / 8.0));
460        assert_eq!(policy.intensity(stamp, 1_849), Some(1.0 - 7.0 / 8.0));
461        assert_eq!(policy.intensity(stamp, 1_850), None);
462        assert!(policy.is_expired(stamp, 1_850));
463        assert_eq!(policy.intensity(Stamp::NONE, 1_000), None);
464
465        // The stamp clock wraps at 2^30 ms; ages stay right across the wrap.
466        let wrap = 1u32 << 30;
467        let late = Stamp::new(wrap - 100, RowChange::Updated);
468        assert_eq!(policy.intensity(late, wrap + 200), Some(1.0 - 3.0 / 8.0));
469        assert!(!policy.is_expired(late, wrap + 200));
470        assert!(policy.is_expired(late, wrap + 800));
471
472        // Steps that do not divide the duration never reach intensity 0.
473        let uneven = HighlightPolicy::new(Duration::from_millis(1_000), 3);
474        let stamp = Stamp::new(10, RowChange::Updated);
475        assert!(uneven.intensity(stamp, 1_009).is_some_and(|i| i > 0.0));
476    }
477
478    #[test]
479    fn test_stamp_direction_bits() {
480        use ChangeDirection::{Down, Up};
481        use RowChange::{Inserted, Updated};
482
483        // Each of the four codes reads back, with the time unchanged.
484        for (stamp, change, direction) in [
485            (Stamp::with_direction(1_050, Updated, None), Updated, None),
486            (Stamp::with_direction(1_050, Inserted, None), Inserted, None),
487            (
488                Stamp::with_direction(1_050, Updated, Some(Up)),
489                Updated,
490                Some(Up),
491            ),
492            (
493                Stamp::with_direction(1_050, Updated, Some(Down)),
494                Updated,
495                Some(Down),
496            ),
497        ] {
498            assert_eq!(stamp.ms(), 1_050);
499            assert_eq!(stamp.change(), change);
500            assert_eq!(stamp.direction(), direction);
501            assert!(stamp.is_set());
502        }
503        // An insert has no direction; `new` writes none.
504        assert_eq!(
505            Stamp::with_direction(7, Inserted, Some(Up)),
506            Stamp::new(7, Inserted)
507        );
508        assert_eq!(Stamp::new(7, Updated).direction(), None);
509        assert_eq!(Stamp::NONE.direction(), None);
510        assert!(!Stamp::NONE.is_set());
511        // The removal stamp of a fading row reads as an update without a
512        // direction, and is never `NONE`, even at the epoch.
513        assert_eq!(Stamp::removal(1_050), Stamp::new(1_050, Updated));
514        assert!(Stamp::removal(0).is_set());
515        // The largest time keeps its direction.
516        let max = Stamp::with_direction(Stamp::MAX_MS, Updated, Some(Down));
517        assert_eq!((max.ms(), max.direction()), (Stamp::MAX_MS, Some(Down)));
518
519        // Steps and expiry do not depend on the change bits.
520        let policy = HighlightPolicy::new(Duration::from_millis(800), 8);
521        let plain = Stamp::new(1_050, Updated);
522        for stamp in [
523            Stamp::new(1_050, Inserted),
524            Stamp::with_direction(1_050, Updated, Some(Up)),
525            Stamp::with_direction(1_050, Updated, Some(Down)),
526        ] {
527            for now in [1_060, 1_200, 1_849, 1_850, 5_000] {
528                let tick = policy.tick(now);
529                assert_eq!(policy.intensity(stamp, tick), policy.intensity(plain, tick));
530                assert_eq!(policy.is_expired(stamp, now), policy.is_expired(plain, now));
531            }
532        }
533    }
534
535    #[test]
536    fn test_removal_fade_steps_on_global_tick() {
537        // Off by default: a removed row goes at once.
538        let policy = HighlightPolicy::new(Duration::from_millis(800), 8);
539        assert_eq!(policy.removal_fade(), Duration::ZERO);
540        assert!(!policy.has_removal_fade());
541        let removed = Stamp::removal(1_050);
542        assert_eq!(policy.removal_intensity(removed, 1_050), None);
543        assert!(policy.is_removal_over(removed, 1_050));
544
545        // 250 ms on the 100 ms tick: three steps, then gone. The highlight
546        // duration is not the fade's.
547        let policy = policy.with_removal_fade(Duration::from_millis(250));
548        assert_eq!(policy.removal_fade(), Duration::from_millis(250));
549        assert!(policy.has_removal_fade());
550        assert_eq!(policy.duration_ms(), 800);
551        assert_eq!(
552            policy.removal_intensity(removed, policy.tick(1_060)),
553            Some(1.0)
554        );
555        assert_eq!(
556            policy.removal_intensity(removed, 1_200),
557            Some(1.0 - 1.0 / 3.0)
558        );
559        assert_eq!(
560            policy.removal_intensity(removed, 1_299),
561            Some(1.0 - 2.0 / 3.0)
562        );
563        assert!(!policy.is_removal_over(removed, 1_299));
564        assert_eq!(policy.removal_intensity(removed, 1_300), None);
565        assert!(policy.is_removal_over(removed, 1_300));
566        assert_eq!(policy.removal_intensity(Stamp::NONE, 1_100), None);
567
568        // A fade shorter than a step shows at full intensity until it ends.
569        let short = policy.with_removal_fade(Duration::from_millis(40));
570        assert_eq!(short.removal_intensity(removed, 1_089), Some(1.0));
571        assert_eq!(short.removal_intensity(removed, 1_090), None);
572
573        // Across the 2^30 ms wrap of the stamp clock.
574        let wrap = 1u32 << 30;
575        let late = Stamp::removal(wrap - 100);
576        assert_eq!(
577            policy.removal_intensity(late, wrap + 100),
578            Some(1.0 - 2.0 / 3.0)
579        );
580        assert!(policy.is_removal_over(late, wrap + 150));
581
582        // Back to zero: off again.
583        let off = policy.with_removal_fade(Duration::ZERO);
584        assert_eq!(off, HighlightPolicy::new(Duration::from_millis(800), 8));
585    }
586
587    #[test]
588    #[cfg(debug_assertions)]
589    #[should_panic(expected = "a removal stamp is written by the store")]
590    fn test_removed_is_not_a_cell_stamp() {
591        Stamp::new(1_050, RowChange::Removed);
592    }
593
594    fn columns(ixs: &[u16]) -> ColumnSet {
595        let mut set = ColumnSet::EMPTY;
596        for &ix in ixs {
597            set.insert(ColumnIx::new(ix));
598        }
599        set
600    }
601
602    /// The stamps of a row of `every` written at `now_ms` under `policy`.
603    fn write(
604        policy: HighlightPolicy,
605        existing: Option<&SparseStamps>,
606        written: &[u16],
607        every: ColumnSet,
608        now_ms: u32,
609        stamp: Stamp,
610    ) -> Option<SparseStamps> {
611        SparseStamps::written(
612            existing,
613            columns(written),
614            every,
615            |stamp| !policy.is_highlight_over(stamp, now_ms),
616            |_| stamp,
617        )
618    }
619
620    /// The stamps a row holds: row stamp and column stamps, no header.
621    fn held(stamps: &SparseStamps) -> usize {
622        let view = stamps.view();
623        usize::from(view.row().is_set()) + view.stamps.len()
624    }
625
626    #[test]
627    fn test_sparse_stamps_keep_written_columns() {
628        let policy = HighlightPolicy::new(Duration::from_millis(800), 8);
629        let every = ColumnSet::first(40);
630        let first = Stamp::new(10, RowChange::Updated);
631        let stamps = write(policy, None, &[3, 7], every, 10, first).expect("stamped");
632        let view = stamps.view();
633        assert_eq!(view.get(ColumnIx::new(3)), first);
634        assert_eq!(view.get(ColumnIx::new(7)), first);
635        assert_eq!(view.get(ColumnIx::new(0)), Stamp::NONE);
636        assert_eq!(view.get(ColumnIx::new(39)), Stamp::NONE);
637        assert_eq!(held(&stamps), 2);
638        // Header and two stamps in one allocation with its counts.
639        assert_eq!(
640            stamps.heap_bytes(),
641            2 * size_of::<usize>() + (HEADER + 2) * 4
642        );
643
644        // Overwriting a column replaces its stamp; the others stay.
645        let second = Stamp::with_direction(20, RowChange::Updated, Some(ChangeDirection::Up));
646        let stamps = write(policy, Some(&stamps), &[7, 9], every, 20, second).expect("stamped");
647        let view = stamps.view();
648        assert_eq!(view.get(ColumnIx::new(3)), first);
649        assert_eq!(view.get(ColumnIx::new(7)), second);
650        assert_eq!(view.get(ColumnIx::new(9)), second);
651        assert_eq!(held(&stamps), 3);
652
653        // A column outside the row is not stamped; nothing written, nothing
654        // held.
655        assert_eq!(write(policy, None, &[40, 41], every, 20, second), None);
656        assert_eq!(
657            SparseStamps::written(None, ColumnSet::EMPTY, every, |_| true, |_| second),
658            None
659        );
660    }
661
662    #[test]
663    fn test_sparse_stamps_drop_expired_on_write() {
664        // 800 ms in 100 ms steps.
665        let policy = HighlightPolicy::new(Duration::from_millis(800), 8);
666        let every = ColumnSet::first(40);
667        let early = Stamp::new(100, RowChange::Updated);
668        let late = Stamp::new(150, RowChange::Updated);
669        let stamps = write(policy, None, &[1], every, 100, early).expect("stamped");
670        let stamps = write(policy, Some(&stamps), &[2], every, 150, late).expect("stamped");
671        assert_eq!(held(&stamps), 2);
672
673        // At 960 ms the tick is 900: the stamp of 100 ms is over and
674        // dropped; the stamp of 150 ms is in its last step at that tick, so
675        // it stays although it expired at 950 ms.
676        let now = Stamp::new(960, RowChange::Updated);
677        let stamps = write(policy, Some(&stamps), &[3], every, 960, now).expect("stamped");
678        let view = stamps.view();
679        assert_eq!(view.get(ColumnIx::new(1)), Stamp::NONE);
680        assert_eq!(view.get(ColumnIx::new(2)), late);
681        assert_eq!(view.get(ColumnIx::new(3)), now);
682        assert_eq!(held(&stamps), 2);
683        let is_hot = |at: u32| move |stamp| !policy.is_highlight_over(stamp, at);
684        assert!(!stamps.is_cold(is_hot(960)));
685
686        // At 1000 ms only the new stamps are hot.
687        let next = Stamp::new(1_000, RowChange::Updated);
688        let stamps = write(policy, Some(&stamps), &[4], every, 1_000, next).expect("stamped");
689        assert_eq!(held(&stamps), 2);
690        assert_eq!(stamps.view().get(ColumnIx::new(2)), Stamp::NONE);
691        assert_eq!(stamps.view().get(ColumnIx::new(3)), now);
692        // Cold once every stamp is over at the tick.
693        assert!(!stamps.is_cold(is_hot(1_799)));
694        assert!(stamps.is_cold(is_hot(1_800)));
695    }
696
697    #[test]
698    fn test_sparse_stamps_whole_row() {
699        let policy = HighlightPolicy::new(Duration::from_millis(800), 8);
700        let every = ColumnSet::first(40);
701        // An insert is one stamp for every cell.
702        let inserted = Stamp::new(10, RowChange::Inserted);
703        let stamps = SparseStamps::whole_row(inserted);
704        assert_eq!(held(&stamps), 1);
705        assert_eq!(stamps.heap_bytes(), 2 * size_of::<usize>() + HEADER * 4);
706        assert!((0..40).all(|ix| stamps.view().get(ColumnIx::new(ix)) == inserted));
707
708        // An update while it flashes: its columns over the row's flash.
709        let update = Stamp::with_direction(150, RowChange::Updated, Some(ChangeDirection::Down));
710        let stamps = write(policy, Some(&stamps), &[5], every, 150, update).expect("stamped");
711        assert_eq!(stamps.view().get(ColumnIx::new(5)), update);
712        assert_eq!(stamps.view().get(ColumnIx::new(4)), inserted);
713        assert_eq!(held(&stamps), 2);
714
715        // Past the flash, a write drops it: the other cells go dark.
716        let later = Stamp::new(900, RowChange::Updated);
717        let stamps = write(policy, Some(&stamps), &[6], every, 900, later).expect("stamped");
718        assert_eq!(stamps.view().get(ColumnIx::new(4)), Stamp::NONE);
719        assert_eq!(stamps.view().get(ColumnIx::new(5)), update);
720        assert_eq!(held(&stamps), 2);
721
722        // The same stamp in every cell is the row's alone; different ones
723        // are the cells' own, without a row stamp.
724        let all: Vec<u16> = (0..40).collect();
725        let mark = Stamp::new(950, RowChange::Updated);
726        let marked = write(policy, Some(&stamps), &all, every, 950, mark).expect("stamped");
727        assert_eq!(held(&marked), 1);
728        assert!((0..40).all(|ix| marked.view().get(ColumnIx::new(ix)) == mark));
729        let mixed = SparseStamps::written(
730            Some(&stamps),
731            every,
732            every,
733            |_| true,
734            |column| Stamp::new(950 + column.get() as u32, RowChange::Updated),
735        )
736        .expect("stamped");
737        assert_eq!(held(&mixed), 40);
738        assert_eq!(mixed.view().row(), Stamp::NONE);
739        assert_eq!(mixed.view().get(ColumnIx::new(39)).ms(), 989);
740
741        // The flash of 10 ms shows its last step at the tick of 800 ms and
742        // is over for every cell at the tick of 900 ms.
743        let is_hot = |at: u32| move |stamp| !policy.is_highlight_over(stamp, at);
744        let flash = SparseStamps::whole_row(inserted);
745        assert!(!flash.is_cold(is_hot(899)));
746        assert!(flash.is_cold(is_hot(900)));
747    }
748
749    #[test]
750    fn test_sparse_stamps_past_64_and_128_columns() {
751        let policy = HighlightPolicy::new(Duration::from_millis(800), 8);
752        for width in [70, 100, 128] {
753            let every = ColumnSet::first(width);
754            let last = width as u16 - 1;
755            let written = [0, 31, 32, 63, 64, 65, last];
756            // Each column its own stamp, so the order of the stamps shows.
757            let stamps = SparseStamps::written(
758                None,
759                columns(&written),
760                every,
761                |stamp| !policy.is_highlight_over(stamp, 0),
762                |column| Stamp::new(column.get() as u32 + 1, RowChange::Updated),
763            )
764            .expect("stamped");
765            let view = stamps.view();
766            assert_eq!(view.columns(), columns(&written));
767            // Word 0 stamps columns 0 and 31, word 1 columns 32 and 63: the
768            // first stamp of word 1 is the third, of word 2 the fifth.
769            assert_eq!(view.header[PLACES].0 & 0xff_ff_ff, 2 << 8 | 4 << 16);
770            for ix in 0..width as u16 {
771                let expected = if written.contains(&ix) {
772                    Stamp::new(u32::from(ix) + 1, RowChange::Updated)
773                } else {
774                    Stamp::NONE
775                };
776                assert_eq!(view.get(ColumnIx::new(ix)), expected, "{width}: {ix}");
777            }
778            // An update of the last column keeps the others in place.
779            let update = Stamp::new(500, RowChange::Updated);
780            let stamps =
781                write(policy, Some(&stamps), &[last], every, 500, update).expect("stamped");
782            assert_eq!(stamps.view().get(ColumnIx::new(last)), update);
783            assert_eq!(stamps.view().get(ColumnIx::new(64)).ms(), 65);
784            assert_eq!(held(&stamps), 7);
785        }
786    }
787}
gpui_kit_grid/highlight.rs

gpui_kit_grid/
highlight.rs
