perl_lexer/checkpoint/
cache.rs

1use crate::checkpoint::LexerCheckpoint;
2
3/// A checkpoint cache for efficient incremental parsing
4pub struct CheckpointCache {
5    /// Cached checkpoints at various positions
6    checkpoints: Vec<(usize, LexerCheckpoint)>,
7    /// Maximum number of checkpoints to cache
8    max_checkpoints: usize,
9}
10
11impl CheckpointCache {
12    /// Create a new checkpoint cache.
13    pub fn new(max_checkpoints: usize) -> Self {
14        Self { checkpoints: Vec::new(), max_checkpoints }
15    }
16
17    /// Number of checkpoints currently held in the cache.
18    pub fn len(&self) -> usize {
19        self.checkpoints.len()
20    }
21
22    /// Whether the cache currently holds zero checkpoints.
23    pub fn is_empty(&self) -> bool {
24        self.checkpoints.is_empty()
25    }
26
27    /// Add a checkpoint to the cache.
28    ///
29    /// If a checkpoint already exists at the same byte position, it is
30    /// replaced in place. Otherwise the new checkpoint is inserted at the
31    /// correct sorted index so [`Self::find_before`] and [`Self::find_after`]
32    /// can use binary search.
33    ///
34    /// When the cache exceeds `max_checkpoints`, entries are evicted while
35    /// preserving the earliest and latest checkpoints as boundary anchors for
36    /// incremental parsing windows.
37    pub fn add(&mut self, checkpoint: LexerCheckpoint) {
38        if self.max_checkpoints == 0 {
39            return;
40        }
41
42        let position = checkpoint.position;
43        match self.checkpoints.binary_search_by_key(&position, |(pos, _)| *pos) {
44            Ok(idx) => self.checkpoints[idx] = (position, checkpoint),
45            Err(idx) => self.checkpoints.insert(idx, (position, checkpoint)),
46        }
47
48        if self.checkpoints.len() > self.max_checkpoints {
49            let total = self.checkpoints.len();
50            if self.max_checkpoints == 1 {
51                if let Some(last) = self.checkpoints.last().cloned() {
52                    self.checkpoints = vec![last];
53                }
54                return;
55            }
56
57            let denominator = self.max_checkpoints - 1;
58            let mut kept = Vec::with_capacity(self.max_checkpoints);
59            for i in 0..self.max_checkpoints {
60                let idx = i * (total - 1) / denominator;
61                kept.push(self.checkpoints[idx].clone());
62            }
63            self.checkpoints = kept;
64        }
65    }
66
67    /// Find the nearest checkpoint at or before a given position.
68    ///
69    /// Uses binary search over the sorted `checkpoints` vector (invariant
70    /// maintained by [`Self::add`]) for O(log N) rather than the previous
71    /// O(N) linear scan. This matters when the checkpoint limit is large
72    /// (50+) for big documents (#2080).
73    pub fn find_before(&self, position: usize) -> Option<&LexerCheckpoint> {
74        // `partition_point` returns the index of the first element for which
75        // the predicate is false (i.e. the first entry with pos > position).
76        // The entry just before that index is the last one with pos <= position.
77        let idx = self.checkpoints.partition_point(|(pos, _)| *pos <= position);
78        if idx == 0 { None } else { self.checkpoints.get(idx - 1).map(|(_, cp)| cp) }
79    }
80
81    /// Find the nearest checkpoint at or after a given position.
82    ///
83    /// Uses binary search over the sorted `checkpoints` vector (invariant
84    /// maintained by [`Self::add`]) for O(log N) performance. This is the
85    /// counterpart to [`Self::find_before`] and is needed for two-sided
86    /// checkpoint windows in incremental parsing (#3527).
87    ///
88    /// # Arguments
89    ///
90    /// * `position` - The byte position to search from
91    ///
92    /// # Returns
93    ///
94    /// * `Some(&LexerCheckpoint)` - The checkpoint at or after the given position
95    /// * `None` - If no checkpoint exists at or after the position
96    ///
97    /// # Examples
98    ///
99    /// ```
100    /// # use perl_lexer::checkpoint::{CheckpointCache, LexerCheckpoint};
101    /// let mut cache = CheckpointCache::new(10);
102    /// cache.add(LexerCheckpoint::at_position(100));
103    /// cache.add(LexerCheckpoint::at_position(200));
104    /// cache.add(LexerCheckpoint::at_position(300));
105    ///
106    /// // Find checkpoint at or after position 150
107    /// let cp = cache.find_after(150);
108    /// assert!(matches!(cp, Some(found) if found.position == 200));
109    ///
110    /// // Find checkpoint at exact position
111    /// let cp = cache.find_after(200);
112    /// assert!(matches!(cp, Some(found) if found.position == 200));
113    ///
114    /// // Position beyond last checkpoint returns None
115    /// let cp = cache.find_after(400);
116    /// assert!(cp.is_none());
117    /// ```
118    pub fn find_after(&self, position: usize) -> Option<&LexerCheckpoint> {
119        // `partition_point` returns the index of the first element for which
120        // the predicate is false (i.e. the first entry with pos >= position).
121        let idx = self.checkpoints.partition_point(|(pos, _)| *pos < position);
122        self.checkpoints.get(idx).map(|(_, cp)| cp)
123    }
124
125    /// Clear all cached checkpoints.
126    pub fn clear(&mut self) {
127        self.checkpoints.clear();
128    }
129
130    /// Apply an edit to all cached checkpoints, shifting or invalidating each
131    /// entry and re-sorting to preserve the binary-search invariant.
132    pub fn apply_edit(&mut self, start: usize, old_len: usize, new_len: usize) {
133        for (pos, checkpoint) in &mut self.checkpoints {
134            checkpoint.apply_edit(start, old_len, new_len);
135            *pos = checkpoint.position;
136        }
137
138        // Edits can move checkpoints backward (or to the same position), so
139        // restore the sorted-order invariant required by binary-search lookups.
140        self.checkpoints.sort_unstable_by_key(|(pos, _)| *pos);
141    }
142}
perl_lexer/checkpoint/cache.rs

perl_lexer/checkpoint/
cache.rs
