gpui_liveplot/datasource/
mod.rs

1//! Data sources and append-only storage.
2//!
3//! The data layer is optimized for append-only workloads and fast range
4//! queries. It underpins streaming plots and decimation logic.
5
6mod store;
7mod summary;
8
9pub(crate) use store::SeriesStore;
10pub(crate) use summary::DecimationScratch;
11
12use crate::geom::Point;
13use crate::view::{Range, Viewport};
14
15/// Mode of the X axis data.
16#[derive(Debug, Clone, Copy, PartialEq, Eq)]
17pub(crate) enum XMode {
18    /// X values are implicit indices.
19    Index,
20    /// X values are explicitly provided.
21    Explicit,
22}
23
24/// Errors that can occur when appending data.
25///
26/// These errors indicate misuse of an append-only series (for example, mixing
27/// implicit and explicit X modes).
28#[derive(Debug, Clone, Copy, PartialEq, Eq)]
29pub enum AppendError {
30    /// Attempted to append with an incompatible X mode.
31    WrongMode,
32    /// Explicit X values are not monotonic.
33    ///
34    /// Non-monotonic X values disable fast range slicing.
35    NonMonotonicX,
36}
37
38/// Append-only data storage with incremental bounds tracking.
39#[derive(Debug, Clone)]
40pub(crate) struct AppendOnlyData {
41    points: Vec<Point>,
42    x_mode: XMode,
43    monotonic: bool,
44    bounds: Option<Viewport>,
45}
46
47impl AppendOnlyData {
48    /// Create an empty data set with implicit X indices.
49    pub fn indexed() -> Self {
50        Self {
51            points: Vec::new(),
52            x_mode: XMode::Index,
53            monotonic: true,
54            bounds: None,
55        }
56    }
57
58    /// Create an empty data set with explicit X values.
59    pub fn explicit() -> Self {
60        Self {
61            points: Vec::new(),
62            x_mode: XMode::Explicit,
63            monotonic: true,
64            bounds: None,
65        }
66    }
67
68    /// Build an indexed data set from an iterator of Y values.
69    pub fn from_iter_y<I, T>(iter: I) -> Self
70    where
71        I: IntoIterator<Item = T>,
72        T: Into<f64>,
73    {
74        let mut data = Self::indexed();
75        let _ = data.extend_y(iter);
76        data
77    }
78
79    /// Build an explicit data set from an iterator of points.
80    pub fn from_iter_points<I>(iter: I) -> Self
81    where
82        I: IntoIterator<Item = Point>,
83    {
84        let mut data = Self::explicit();
85        let _ = data.extend_points(iter);
86        data
87    }
88
89    /// Build an explicit data set by sampling a callback function.
90    pub fn from_explicit_callback(
91        function: impl Fn(f64) -> f64,
92        x_range: Range,
93        points: usize,
94    ) -> Self {
95        let mut data = Self::explicit();
96        if points == 0 {
97            return data;
98        }
99        let span = x_range.span();
100        let step = if points > 1 {
101            span / (points - 1) as f64
102        } else {
103            0.0
104        };
105        for i in 0..points {
106            let x = x_range.min + step * i as f64;
107            let y = function(x);
108            let _ = data.push_point(Point::new(x, y));
109        }
110        data
111    }
112
113    /// Append a Y value for indexed data.
114    pub fn push_y(&mut self, y: f64) -> Result<usize, AppendError> {
115        let index = self.points.len();
116        self.extend_y([y]).map(|_| index)
117    }
118
119    /// Append multiple Y values for indexed data.
120    pub fn extend_y<I, T>(&mut self, values: I) -> Result<usize, AppendError>
121    where
122        I: IntoIterator<Item = T>,
123        T: Into<f64>,
124    {
125        if self.x_mode != XMode::Index {
126            return Err(AppendError::WrongMode);
127        }
128
129        let values = values.into_iter();
130        let (reserve, _) = values.size_hint();
131        self.points.reserve(reserve);
132
133        let start_len = self.points.len();
134        for value in values {
135            let index = self.points.len();
136            let point = Point::new(index as f64, value.into());
137            self.points.push(point);
138            self.update_bounds(point);
139        }
140        Ok(self.points.len() - start_len)
141    }
142
143    /// Append a point with explicit X value.
144    pub fn push_point(&mut self, point: Point) -> Result<usize, AppendError> {
145        let index = self.points.len();
146        self.extend_points([point]).map(|_| index)
147    }
148
149    /// Append multiple points with explicit X values.
150    pub fn extend_points<I>(&mut self, points: I) -> Result<usize, AppendError>
151    where
152        I: IntoIterator<Item = Point>,
153    {
154        if self.x_mode != XMode::Explicit {
155            return Err(AppendError::WrongMode);
156        }
157
158        let points = points.into_iter();
159        let (reserve, _) = points.size_hint();
160        self.points.reserve(reserve);
161
162        let start_len = self.points.len();
163        let mut last_x = self.points.last().map(|point| point.x);
164        let mut non_monotonic = false;
165        for point in points {
166            if let Some(last_x) = last_x
167                && point.x < last_x
168            {
169                self.monotonic = false;
170                non_monotonic = true;
171            }
172            self.points.push(point);
173            self.update_bounds(point);
174            last_x = Some(point.x);
175        }
176
177        if non_monotonic {
178            Err(AppendError::NonMonotonicX)
179        } else {
180            Ok(self.points.len() - start_len)
181        }
182    }
183
184    /// Access all points as a slice.
185    pub fn points(&self) -> &[Point] {
186        &self.points
187    }
188
189    /// Access a single point by index.
190    pub fn point(&self, index: usize) -> Option<Point> {
191        self.points.get(index).copied()
192    }
193
194    /// Number of points stored.
195    pub fn len(&self) -> usize {
196        self.points.len()
197    }
198
199    /// Check if there are no points.
200    pub fn is_empty(&self) -> bool {
201        self.points.is_empty()
202    }
203
204    /// Get the bounds for all points.
205    pub fn bounds(&self) -> Option<Viewport> {
206        self.bounds
207    }
208
209    /// Access the X mode.
210    pub fn x_mode(&self) -> XMode {
211        self.x_mode
212    }
213
214    /// Check whether explicit X values are monotonic.
215    pub fn is_monotonic(&self) -> bool {
216        self.monotonic
217    }
218
219    /// Find the index range that intersects the X range.
220    pub fn range_by_x(&self, range: Range) -> std::ops::Range<usize> {
221        if self.points.is_empty() {
222            return 0..0;
223        }
224        match self.x_mode {
225            XMode::Index => index_range(range, self.points.len()),
226            XMode::Explicit => {
227                if !self.monotonic {
228                    return 0..self.points.len();
229                }
230                let start = lower_bound(&self.points, range.min);
231                let end = upper_bound(&self.points, range.max);
232                start..end
233            }
234        }
235    }
236
237    /// Find the index of the point with nearest X value.
238    pub fn nearest_index_by_x(&self, x: f64) -> Option<usize> {
239        if self.points.is_empty() || !x.is_finite() {
240            return None;
241        }
242
243        match self.x_mode {
244            XMode::Index => {
245                let max_index = self.points.len().saturating_sub(1) as f64;
246                let clamped = x.round().clamp(0.0, max_index);
247                Some(clamped as usize)
248            }
249            XMode::Explicit => {
250                if !self.monotonic {
251                    return self.nearest_index_linear(x);
252                }
253                let lower = lower_bound(&self.points, x);
254                if lower == 0 {
255                    return Some(0);
256                }
257                if lower >= self.points.len() {
258                    return Some(self.points.len() - 1);
259                }
260                let left = lower - 1;
261                let right = lower;
262                let left_dist = (self.points[left].x - x).abs();
263                let right_dist = (self.points[right].x - x).abs();
264                if left_dist <= right_dist {
265                    Some(left)
266                } else {
267                    Some(right)
268                }
269            }
270        }
271    }
272
273    fn update_bounds(&mut self, point: Point) {
274        match self.bounds {
275            None => {
276                self.bounds = Some(Viewport::new(
277                    Range::new(point.x, point.x),
278                    Range::new(point.y, point.y),
279                ));
280            }
281            Some(mut bounds) => {
282                bounds.x.expand_to_include(point.x);
283                bounds.y.expand_to_include(point.y);
284                self.bounds = Some(bounds);
285            }
286        }
287    }
288
289    fn nearest_index_linear(&self, x: f64) -> Option<usize> {
290        let mut best_index = None;
291        let mut best_distance = f64::INFINITY;
292        for (index, point) in self.points.iter().enumerate() {
293            let distance = (point.x - x).abs();
294            if distance < best_distance {
295                best_distance = distance;
296                best_index = Some(index);
297            }
298        }
299        best_index
300    }
301}
302
303fn index_range(range: Range, len: usize) -> std::ops::Range<usize> {
304    if len == 0 {
305        return 0..0;
306    }
307    let min = range.min.ceil() as isize;
308    let max = range.max.floor() as isize;
309    if max < 0 || min > max {
310        return 0..0;
311    }
312    let start = min.max(0) as usize;
313    let end = (max as usize).saturating_add(1).min(len);
314    start.min(end)..end
315}
316
317fn lower_bound(points: &[Point], target: f64) -> usize {
318    let mut left = 0;
319    let mut right = points.len();
320    while left < right {
321        let mid = (left + right) / 2;
322        if points[mid].x < target {
323            left = mid + 1;
324        } else {
325            right = mid;
326        }
327    }
328    left
329}
330
331fn upper_bound(points: &[Point], target: f64) -> usize {
332    let mut left = 0;
333    let mut right = points.len();
334    while left < right {
335        let mid = (left + right) / 2;
336        if points[mid].x <= target {
337            left = mid + 1;
338        } else {
339            right = mid;
340        }
341    }
342    left
343}
344
345#[cfg(test)]
346mod tests {
347    use super::*;
348
349    #[test]
350    fn indexed_range_matches_indices() {
351        let data = AppendOnlyData::from_iter_y([1.0, 2.0, 3.0, 4.0]);
352        let range = data.range_by_x(Range::new(1.0, 2.1));
353        let slice = &data.points()[range];
354        assert_eq!(slice.len(), 2);
355        assert_eq!(slice[0].x, 1.0);
356        assert_eq!(slice[1].x, 2.0);
357    }
358
359    #[test]
360    fn indexed_range_respects_fractional_bounds() {
361        let data = AppendOnlyData::from_iter_y([1.0, 2.0, 3.0, 4.0, 5.0]);
362        let range = data.range_by_x(Range::new(1.2, 3.8));
363        let slice = &data.points()[range];
364        assert_eq!(slice.len(), 2);
365        assert_eq!(slice[0].x, 2.0);
366        assert_eq!(slice[1].x, 3.0);
367    }
368
369    #[test]
370    fn explicit_range_uses_binary_search() {
371        let points = [
372            Point::new(0.0, 1.0),
373            Point::new(1.0, 2.0),
374            Point::new(2.0, 3.0),
375            Point::new(3.0, 4.0),
376        ];
377        let data = AppendOnlyData::from_iter_points(points);
378        let range = data.range_by_x(Range::new(0.5, 2.5));
379        let slice = &data.points()[range];
380        assert_eq!(slice.len(), 2);
381        assert_eq!(slice[0].x, 1.0);
382        assert_eq!(slice[1].x, 2.0);
383    }
384
385    #[test]
386    fn non_monotonic_explicit_marks_flag() {
387        let mut data = AppendOnlyData::explicit();
388        let _ = data.push_point(Point::new(1.0, 1.0));
389        let result = data.push_point(Point::new(0.5, 2.0));
390        assert_eq!(result, Err(AppendError::NonMonotonicX));
391        assert!(!data.is_monotonic());
392    }
393
394    #[test]
395    fn extend_y_appends_multiple_values() {
396        let mut data = AppendOnlyData::indexed();
397        let added = data.extend_y([1.0, 2.0, 3.0]).unwrap();
398        assert_eq!(added, 3);
399        assert_eq!(data.point(0), Some(Point::new(0.0, 1.0)));
400        assert_eq!(data.point(2), Some(Point::new(2.0, 3.0)));
401    }
402
403    #[test]
404    fn extend_points_non_monotonic_still_appends_batch() {
405        let mut data = AppendOnlyData::explicit();
406        let _ = data.extend_points([Point::new(1.0, 1.0), Point::new(2.0, 2.0)]);
407        let result = data.extend_points([Point::new(1.5, 3.0), Point::new(4.0, 4.0)]);
408
409        assert_eq!(result, Err(AppendError::NonMonotonicX));
410        assert_eq!(data.len(), 4);
411        assert_eq!(data.point(2), Some(Point::new(1.5, 3.0)));
412        assert_eq!(data.point(3), Some(Point::new(4.0, 4.0)));
413        assert!(!data.is_monotonic());
414    }
415
416    #[test]
417    fn extend_points_wrong_mode_does_not_append() {
418        let mut data = AppendOnlyData::indexed();
419        let result = data.extend_points([Point::new(0.0, 1.0)]);
420        assert_eq!(result, Err(AppendError::WrongMode));
421        assert!(data.is_empty());
422    }
423
424    #[test]
425    fn nearest_index_for_indexed_data_rounds() {
426        let data = AppendOnlyData::from_iter_y([0.0, 1.0, 2.0, 3.0]);
427        assert_eq!(data.nearest_index_by_x(2.4), Some(2));
428        assert_eq!(data.nearest_index_by_x(2.6), Some(3));
429        assert_eq!(data.nearest_index_by_x(-2.0), Some(0));
430        assert_eq!(data.nearest_index_by_x(99.0), Some(3));
431    }
432
433    #[test]
434    fn nearest_index_for_monotonic_explicit_data_uses_binary_search() {
435        let data = AppendOnlyData::from_iter_points([
436            Point::new(0.0, 0.0),
437            Point::new(1.0, 1.0),
438            Point::new(3.0, 3.0),
439            Point::new(10.0, 4.0),
440        ]);
441        assert_eq!(data.nearest_index_by_x(2.2), Some(2));
442        assert_eq!(data.nearest_index_by_x(8.0), Some(3));
443        assert_eq!(data.nearest_index_by_x(-5.0), Some(0));
444    }
445
446    #[test]
447    fn nearest_index_for_non_monotonic_explicit_data_falls_back_to_linear_scan() {
448        let mut data = AppendOnlyData::explicit();
449        let _ = data.extend_points([
450            Point::new(0.0, 0.0),
451            Point::new(5.0, 1.0),
452            Point::new(2.0, 2.0),
453            Point::new(10.0, 3.0),
454        ]);
455        assert_eq!(data.nearest_index_by_x(2.1), Some(2));
456    }
457}
gpui_liveplot/datasource/mod.rs

gpui_liveplot/datasource/
mod.rs
