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}