Skip to main content

ferrochart_core/data/
change_log.rs

1//! Per-series generation counter and change log for pull-based incremental sync.
2//!
3//! Consumers outside the core (GPU buffers of a renderer, binding-layer caches)
4//! remember which generation they last synced and ask [`ChangeLog::changes_since`]
5//! what changed since then. Skipped frames, failed renders and several renderers
6//! on one chart therefore never lose updates.
7//!
8
9use super::IdxSpan;
10
11/// Number of entries in the fixed-size log.
12const CAPACITY: usize = 64;
13
14/// What changed in a series since a given generation.
15///
16///
17/// # Examples
18///
19/// ```
20/// use ferrochart_core::data::{ChangeLog, DataDelta, IdxSpan};
21///
22/// let mut log = ChangeLog::new();
23/// let synced = log.generation();
24/// log.record(IdxSpan { start: 9, end: 10 }); // update_last on bar 9
25/// assert_eq!(log.changes_since(synced), DataDelta::Range(IdxSpan { start: 9, end: 10 }));
26/// assert_eq!(log.changes_since(log.generation()), DataDelta::None);
27/// ```
28#[derive(Clone, Copy, Debug, PartialEq, Eq)]
29pub enum DataDelta {
30    /// Nothing changed.
31    None,
32    /// Every change lies within this logical index span (based on the fixed
33    /// logical index origin, so it stays valid after `Prepend`). It may be larger
34    /// than the exact set of changed slots, never smaller.
35    Range(IdxSpan),
36    /// The data was replaced (or the consumer never synced): re-upload everything.
37    Full,
38}
39
40#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
41struct Entry {
42    /// Oldest generation folded into this entry.
43    gen_lo: u64,
44    /// Newest generation folded into this entry.
45    gen_hi: u64,
46    /// Hull of the spans of generations `gen_lo..=gen_hi`.
47    span: IdxSpan,
48}
49
50/// Generation counter plus a fixed-size log of changed logical index spans.
51///
52/// - Generations start at 1, so a consumer that has never synced asks with
53///   `since_gen = 0` and gets [`DataDelta::Full`].
54/// - A change whose span intersects or touches the newest entry is folded into it,
55///   so a stream of ticks and appends at the end of a series occupies one entry.
56/// - When all 64 entries are used, the two oldest are merged into their hull.
57///   Results only get more conservative, never wrong.
58/// - Only a `Replace` (or never having synced) produces `Full`; staying away for a
59///   long time does not.
60///
61/// Recording and querying never allocate (the log is a fixed array), so this is
62/// safe on the `update_last` hot path.
63///
64/// # Examples
65///
66/// ```
67/// use ferrochart_core::data::{ChangeLog, DataDelta, IdxSpan};
68///
69/// let mut log = ChangeLog::new();
70/// let renderer_a = log.generation();
71/// log.record(IdxSpan { start: 100, end: 101 }); // tick on the last bar
72/// let renderer_b = log.generation();
73/// log.record(IdxSpan { start: 101, end: 103 }); // two bars appended
74///
75/// assert_eq!(log.changes_since(renderer_a), DataDelta::Range(IdxSpan { start: 100, end: 103 }));
76/// assert_eq!(log.changes_since(0), DataDelta::Full); // never synced
77///
78/// log.replace();
79/// assert_eq!(log.changes_since(renderer_b), DataDelta::Full);
80/// ```
81#[derive(Clone, Debug)]
82pub struct ChangeLog {
83    generation: u64,
84    /// Generation of the creation or of the last `Replace`.
85    base: u64,
86    entries: [Entry; CAPACITY],
87    /// Number of used entries, oldest first.
88    len: usize,
89}
90
91impl ChangeLog {
92    /// Creates a log at generation 1 with no recorded changes.
93    ///
94    /// # Examples
95    ///
96    /// ```
97    /// use ferrochart_core::data::ChangeLog;
98    ///
99    /// assert_eq!(ChangeLog::new().generation(), 1);
100    /// ```
101    pub const fn new() -> Self {
102        Self {
103            generation: 1,
104            base: 1,
105            entries: [Entry {
106                gen_lo: 0,
107                gen_hi: 0,
108                span: IdxSpan { start: 0, end: 0 },
109            }; CAPACITY],
110            len: 0,
111        }
112    }
113
114    /// Current generation. Increases by one on every recorded change.
115    ///
116    /// # Examples
117    ///
118    /// ```
119    /// use ferrochart_core::data::{ChangeLog, IdxSpan};
120    ///
121    /// let mut log = ChangeLog::new();
122    /// log.record(IdxSpan { start: 0, end: 1 });
123    /// assert_eq!(log.generation(), 2);
124    /// ```
125    pub fn generation(&self) -> u64 {
126        self.generation
127    }
128
129    /// Records that the slots in `span` changed (`Append`, `UpdateLast`,
130    /// `Prepend`) and returns the new generation. An empty span still advances
131    /// the generation but logs nothing.
132    ///
133    /// # Examples
134    ///
135    /// ```
136    /// use ferrochart_core::data::{ChangeLog, DataDelta, IdxSpan};
137    ///
138    /// let mut log = ChangeLog::new();
139    /// for _ in 0..1000 {
140    ///     log.record(IdxSpan { start: 41, end: 42 }); // 1000 ticks on one bar
141    /// }
142    /// assert_eq!(log.changes_since(1), DataDelta::Range(IdxSpan { start: 41, end: 42 }));
143    /// ```
144    pub fn record(&mut self, span: IdxSpan) -> u64 {
145        self.generation += 1;
146        let generation = self.generation;
147        if span.is_empty() {
148            return generation;
149        }
150        if let Some(newest) = self.len.checked_sub(1).map(|i| &mut self.entries[i])
151            && newest.span.touches(span)
152        {
153            newest.gen_hi = generation;
154            newest.span = newest.span.hull(span);
155            return generation;
156        }
157        if self.len == CAPACITY {
158            // Fold the two oldest entries together to free a slot.
159            let (a, b) = (self.entries[0], self.entries[1]);
160            self.entries[1] = Entry {
161                gen_lo: a.gen_lo,
162                gen_hi: b.gen_hi,
163                span: a.span.hull(b.span),
164            };
165            self.entries.copy_within(1.., 0);
166            self.len -= 1;
167        }
168        self.entries[self.len] = Entry {
169            gen_lo: generation,
170            gen_hi: generation,
171            span,
172        };
173        self.len += 1;
174        generation
175    }
176
177    /// Records a `Replace`: everything changed. Consumers synced to an earlier
178    /// generation get [`DataDelta::Full`]. Returns the new generation.
179    ///
180    /// # Examples
181    ///
182    /// ```
183    /// use ferrochart_core::data::{ChangeLog, DataDelta};
184    ///
185    /// let mut log = ChangeLog::new();
186    /// let synced = log.replace();
187    /// assert_eq!(log.changes_since(synced), DataDelta::None);
188    /// assert_eq!(log.changes_since(synced - 1), DataDelta::Full);
189    /// ```
190    pub fn replace(&mut self) -> u64 {
191        self.generation += 1;
192        self.base = self.generation;
193        self.len = 0;
194        self.generation
195    }
196
197    /// What changed after generation `since_gen`. O(64), no allocation.
198    ///
199    /// Returns [`DataDelta::Full`] if `since_gen` is older than the last `Replace`
200    /// (or the creation), or newer than the current generation (an invalid value,
201    /// treated conservatively).
202    ///
203    /// # Examples
204    ///
205    /// ```
206    /// use ferrochart_core::data::{ChangeLog, DataDelta, IdxSpan};
207    ///
208    /// let mut log = ChangeLog::new();
209    /// log.record(IdxSpan { start: 0, end: 10 });
210    /// log.record(IdxSpan { start: 50, end: 60 });
211    /// assert_eq!(log.changes_since(1), DataDelta::Range(IdxSpan { start: 0, end: 60 }));
212    /// assert_eq!(log.changes_since(2), DataDelta::Range(IdxSpan { start: 50, end: 60 }));
213    /// ```
214    pub fn changes_since(&self, since_gen: u64) -> DataDelta {
215        if since_gen < self.base || since_gen > self.generation {
216            return DataDelta::Full;
217        }
218        let mut hull: Option<IdxSpan> = None;
219        for e in &self.entries[..self.len] {
220            if e.gen_hi > since_gen {
221                hull = Some(hull.map_or(e.span, |h| h.hull(e.span)));
222            }
223        }
224        hull.map_or(DataDelta::None, DataDelta::Range)
225    }
226}
227
228impl Default for ChangeLog {
229    fn default() -> Self {
230        Self::new()
231    }
232}
233
234#[cfg(test)]
235mod tests {
236    use super::*;
237    use proptest::prelude::*;
238
239    fn span(start: i64, end: i64) -> IdxSpan {
240        IdxSpan { start, end }
241    }
242
243    #[test]
244    fn disjoint_changes_use_separate_entries() {
245        let mut log = ChangeLog::new();
246        log.record(span(0, 1));
247        log.record(span(10, 11));
248        log.record(span(5, 6));
249        assert_eq!(log.len, 3);
250        assert_eq!(log.changes_since(3), DataDelta::Range(span(5, 6)));
251    }
252
253    #[test]
254    fn realtime_stream_stays_in_one_entry() {
255        let mut log = ChangeLog::new();
256        log.record(span(500, 600)); // unrelated older change
257        let mut last = 999;
258        for i in 0..10_000 {
259            if i % 10 == 0 {
260                last += 1; // append a bar
261            }
262            log.record(span(last, last + 1)); // tick on the last bar
263        }
264        assert_eq!(log.len, 2);
265        assert_eq!(log.changes_since(2), DataDelta::Range(span(1000, last + 1)));
266    }
267
268    #[test]
269    fn overflow_merges_oldest_and_never_goes_full() {
270        let mut log = ChangeLog::new();
271        for i in 0..1000 {
272            log.record(span(i * 10, i * 10 + 1)); // disjoint
273        }
274        assert_eq!(log.len, CAPACITY);
275        // Very old consumer: still a range, not Full.
276        assert_eq!(log.changes_since(1), DataDelta::Range(span(0, 9991)));
277        // Recent consumer: exact, unaffected by merging of old entries.
278        assert_eq!(log.changes_since(1000), DataDelta::Range(span(9990, 9991)));
279    }
280
281    #[test]
282    fn future_generation_is_full() {
283        let log = ChangeLog::new();
284        assert_eq!(log.changes_since(2), DataDelta::Full);
285    }
286
287    #[test]
288    fn empty_span_advances_generation_only() {
289        let mut log = ChangeLog::new();
290        assert_eq!(log.record(span(3, 3)), 2);
291        assert_eq!(log.changes_since(1), DataDelta::None);
292    }
293
294    #[derive(Clone, Debug)]
295    enum Op {
296        Change(i64, i64),
297        Replace,
298    }
299
300    fn op() -> impl Strategy<Value = Op> {
301        prop_oneof![
302            20 => (-500i64..500, 0i64..20).prop_map(|(s, l)| Op::Change(s, s + l)),
303            1 => Just(Op::Replace),
304        ]
305    }
306
307    proptest! {
308        /// For every consumer generation, the result covers every change after it
309        /// (never misses data), stays within the hull of all changes since the last
310        /// replace, and is `Full` exactly when a replace happened after it.
311        #[test]
312        fn never_misses_a_change(ops in prop::collection::vec(op(), 0..400)) {
313            let mut log = ChangeLog::new();
314            // (generation, span) of every change since the last replace.
315            let mut history: Vec<(u64, IdxSpan)> = Vec::new();
316            let mut base = 1;
317            for op in ops {
318                match op {
319                    Op::Change(s, e) => {
320                        let g = log.record(span(s, e));
321                        if s < e { history.push((g, span(s, e))); }
322                    }
323                    Op::Replace => { base = log.replace(); history.clear(); }
324                }
325            }
326            for since in 0..=log.generation() + 1 {
327                let got = log.changes_since(since);
328                if since < base || since > log.generation() {
329                    prop_assert_eq!(got, DataDelta::Full);
330                    continue;
331                }
332                let after: Vec<IdxSpan> =
333                    history.iter().filter(|(g, _)| *g > since).map(|(_, s)| *s).collect();
334                match got {
335                    DataDelta::None => prop_assert!(after.is_empty()),
336                    DataDelta::Range(r) => {
337                        prop_assert!(!after.is_empty());
338                        for s in &after {
339                            prop_assert!(r.start <= s.start && s.end <= r.end);
340                        }
341                        let all = history.iter().map(|(_, s)| *s).reduce(IdxSpan::hull);
342                        let all = all.unwrap_or_default();
343                        prop_assert!(all.start <= r.start && r.end <= all.end);
344                    }
345                    DataDelta::Full => prop_assert!(false, "unexpected Full"),
346                }
347            }
348        }
349    }
350}