Skip to main content

gpui_base/
history.rs

1use std::fmt::Debug;
2
3/// A browser-style linear trail with a current entry.
4///
5/// Entries before the current one can be revisited with [`back`](Self::back),
6/// and entries left behind by going back can be restored with
7/// [`forward`](Self::forward). Pushing after going back starts a new branch
8/// and drops the forward entries.
9#[derive(Debug)]
10pub struct History<T> {
11    entries: Vec<T>,
12    forward_entries: Vec<T>,
13    max_entries: usize,
14}
15
16impl<T> History<T> {
17    pub fn new() -> Self {
18        Self {
19            entries: Vec::new(),
20            forward_entries: Vec::new(),
21            max_entries: 1000,
22        }
23    }
24
25    /// Sets the maximum number of root-to-current entries to keep, defaults to 1000.
26    ///
27    /// Lowering the limit immediately removes the oldest entries.
28    pub fn max_entries(mut self, max_entries: usize) -> Self {
29        self.max_entries = max_entries;
30        self.enforce_max_entries();
31        self
32    }
33
34    /// Pushes an entry and drops the forward branch.
35    pub fn push(&mut self, entry: T) {
36        self.forward_entries.clear();
37        if self.max_entries == 0 {
38            return;
39        }
40        self.entries.push(entry);
41        self.enforce_max_entries();
42    }
43
44    /// Returns the current entry.
45    pub fn current(&self) -> Option<&T> {
46        self.entries.last()
47    }
48
49    /// Replaces the current entry, or pushes when the trail is empty.
50    pub fn replace_current(&mut self, entry: T) {
51        match self.entries.last_mut() {
52            Some(current) => *current = entry,
53            None => self.push(entry),
54        }
55    }
56
57    /// Removes and returns the current entry without changing the forward branch.
58    pub fn remove_current(&mut self) -> Option<T> {
59        self.entries.pop()
60    }
61
62    /// Returns whether moving back would keep a root entry current.
63    pub fn can_back(&self) -> bool {
64        self.entries.len() > 1
65    }
66
67    /// Returns whether a forward entry is available.
68    pub fn can_forward(&self) -> bool {
69        !self.forward_entries.is_empty()
70    }
71
72    /// Moves back one entry and returns the new current entry.
73    pub fn back(&mut self) -> Option<T>
74    where
75        T: Clone,
76    {
77        if self.entries.len() <= 1 {
78            return None;
79        }
80        self.forward_entries.push(self.entries.pop().unwrap());
81        self.current().cloned()
82    }
83
84    /// Moves forward one entry and returns the restored entry.
85    pub fn forward(&mut self) -> Option<T>
86    where
87        T: Clone,
88    {
89        if self.max_entries == 0 {
90            return None;
91        }
92        let entry = self.forward_entries.pop()?;
93        self.entries.push(entry);
94        self.enforce_max_entries();
95        self.current().cloned()
96    }
97
98    /// Iterates from the root entry to the current entry.
99    pub fn entries(&self) -> impl DoubleEndedIterator<Item = &T> + ExactSizeIterator {
100        self.entries.iter()
101    }
102
103    /// Iterates from the nearest forward entry to the furthest.
104    pub fn forward_entries(&self) -> impl DoubleEndedIterator<Item = &T> + ExactSizeIterator {
105        self.forward_entries.iter().rev()
106    }
107
108    /// Keeps only entries accepted by `keep` on both sides of the current position.
109    pub fn retain(&mut self, mut keep: impl FnMut(&T) -> bool) {
110        self.entries.retain(&mut keep);
111        self.forward_entries.retain(&mut keep);
112    }
113
114    /// Clears current, back, and forward entries.
115    pub fn clear(&mut self) {
116        self.entries.clear();
117        self.forward_entries.clear();
118    }
119
120    fn enforce_max_entries(&mut self) {
121        let excess = self.entries.len().saturating_sub(self.max_entries);
122        if excess > 0 {
123            self.entries.drain(..excess);
124        }
125    }
126}
127
128impl<T> Default for History<T> {
129    fn default() -> Self {
130        Self::new()
131    }
132}
133
134#[cfg(test)]
135mod tests {
136    use super::*;
137
138    #[test]
139    fn navigation_moves_between_entries_without_backing_past_the_root() {
140        let mut history = History::new().max_entries(3);
141        history.push(1);
142        history.push(2);
143        history.push(3);
144
145        assert_eq!(history.current(), Some(&3));
146        assert_eq!(history.back(), Some(2));
147        assert_eq!(history.back(), Some(1));
148        assert_eq!(history.back(), None);
149        assert_eq!(history.forward(), Some(2));
150        assert_eq!(history.entries().copied().collect::<Vec<_>>(), [1, 2]);
151        assert_eq!(history.entries().rev().copied().collect::<Vec<_>>(), [2, 1]);
152        assert_eq!(history.forward_entries().copied().collect::<Vec<_>>(), [3]);
153        assert!(history.can_back());
154        assert!(history.can_forward());
155    }
156
157    #[test]
158    fn pushing_after_back_truncates_the_forward_branch() {
159        let mut history = History::new();
160        history.push(1);
161        history.push(2);
162        history.push(3);
163        assert_eq!(history.back(), Some(2));
164
165        history.push(4);
166
167        assert_eq!(history.entries().copied().collect::<Vec<_>>(), [1, 2, 4]);
168        assert!(!history.can_forward());
169        assert_eq!(history.forward(), None);
170    }
171
172    #[test]
173    fn repeated_entries_preserve_every_navigation_step() {
174        let mut history = History::new();
175        history.push(1);
176        history.push(2);
177        history.push(1);
178
179        assert_eq!(history.entries().copied().collect::<Vec<_>>(), [1, 2, 1]);
180        assert_eq!(history.back(), Some(2));
181        assert_eq!(history.back(), Some(1));
182    }
183
184    #[test]
185    fn max_entries_evicts_the_oldest_entry() {
186        let mut history = History::new().max_entries(2);
187        history.push(1);
188        history.push(2);
189        history.push(3);
190
191        assert_eq!(history.entries().copied().collect::<Vec<_>>(), [2, 3]);
192        assert_eq!(history.back(), Some(2));
193        assert_eq!(history.back(), None);
194    }
195
196    #[test]
197    fn lowering_max_entries_truncates_populated_entries_and_caps_forward_restores() {
198        let mut history = History::new();
199        history.push(1);
200        history.push(2);
201        history.push(3);
202        assert_eq!(history.back(), Some(2));
203
204        history = history.max_entries(1);
205
206        assert_eq!(history.entries().copied().collect::<Vec<_>>(), [2]);
207        assert_eq!(history.forward(), Some(3));
208        assert_eq!(history.entries().copied().collect::<Vec<_>>(), [3]);
209        assert_eq!(history.back(), None);
210    }
211
212    #[test]
213    fn zero_max_entries_retains_nothing() {
214        let mut history = History::new().max_entries(0);
215        history.push(1);
216
217        assert_eq!(history.current(), None);
218        assert_eq!(history.entries().len(), 0);
219        assert!(!history.can_back());
220        assert!(!history.can_forward());
221    }
222
223    #[test]
224    fn replace_current_updates_in_place_and_pushes_when_empty() {
225        let mut history = History::new();
226        history.replace_current(1);
227        history.push(2);
228        history.replace_current(3);
229
230        assert_eq!(history.entries().copied().collect::<Vec<_>>(), [1, 3]);
231    }
232
233    #[test]
234    fn remove_current_preserves_forward_entries() {
235        let mut history = History::new();
236        history.push(1);
237        history.push(2);
238        history.push(3);
239        assert_eq!(history.back(), Some(2));
240
241        assert_eq!(history.remove_current(), Some(2));
242
243        assert_eq!(history.current(), Some(&1));
244        assert_eq!(history.forward_entries().copied().collect::<Vec<_>>(), [3]);
245        assert_eq!(history.forward(), Some(3));
246    }
247
248    #[test]
249    fn retain_filters_back_and_forward_entries_without_reordering() {
250        let mut history = History::new();
251        for entry in 1..=8 {
252            history.push(entry);
253        }
254        history.back();
255        history.back();
256        history.back();
257        history.back();
258
259        history.retain(|entry| entry % 2 == 0);
260
261        assert_eq!(history.entries().copied().collect::<Vec<_>>(), [2, 4]);
262        assert_eq!(
263            history.forward_entries().copied().collect::<Vec<_>>(),
264            [6, 8]
265        );
266        assert_eq!(history.forward(), Some(6));
267        assert_eq!(history.forward(), Some(8));
268    }
269
270    #[test]
271    fn clear_removes_back_and_forward_entries() {
272        let mut history = History::new();
273        history.push(1);
274        history.push(2);
275        history.back();
276
277        history.clear();
278
279        assert_eq!(history.current(), None);
280        assert_eq!(history.entries().len(), 0);
281        assert_eq!(history.forward_entries().len(), 0);
282        assert!(!history.can_back());
283        assert!(!history.can_forward());
284    }
285}