smart_string/str_stack/
mod.rs

1use std::str::from_utf8_unchecked;
2
3mod iter;
4#[cfg(feature = "serde")]
5mod with_serde;
6
7pub use iter::StrStackIter;
8
9#[derive(Clone, Default, PartialEq, Eq)]
10pub struct StrStack {
11    data: Vec<u8>,
12    ends: Vec<usize>,
13}
14
15impl StrStack {
16    #[inline]
17    pub fn new() -> Self {
18        Self::default()
19    }
20
21    #[inline]
22    pub fn len(&self) -> usize {
23        self.ends.len()
24    }
25
26    #[inline]
27    pub fn is_empty(&self) -> bool {
28        self.ends.is_empty()
29    }
30
31    #[inline]
32    pub fn as_str(&self) -> &str {
33        // SAFETY: `self.data` is only appended to via `push(&str)` and truncated via `remove_top()`,
34        // so it is always valid UTF-8.
35        unsafe { from_utf8_unchecked(&self.data) }
36    }
37
38    #[inline]
39    pub fn get(&self, index: usize) -> Option<&str> {
40        let (begin, end) = self.get_bounds(index)?;
41        // SAFETY: `get_bounds` ensures `begin <= end <= self.data.len()`, and the stack stores only UTF-8 segments
42        // pushed via `push(&str)`.
43        Some(unsafe { self.get_unchecked_internal(begin, end) })
44    }
45
46    #[inline]
47    /// Returns a `&str` slice without bounds checks.
48    ///
49    /// # Safety
50    ///
51    /// - `begin <= end`
52    /// - `end <= self.data.len()`
53    /// - `self.data[begin..end]` must be valid UTF-8
54    #[deprecated(note = "Use `get()` instead. This will be removed in a future version.")]
55    pub unsafe fn get_unchecked(&self, begin: usize, end: usize) -> &str {
56        // SAFETY: caller upholds bounds + UTF-8 preconditions (see doc comment).
57        unsafe {
58            let slice = self.data.get_unchecked(begin..end);
59            from_utf8_unchecked(slice)
60        }
61    }
62
63    /// Internal unchecked slice access. Not public — callers within the crate
64    /// must uphold bounds + UTF-8 preconditions.
65    #[inline]
66    pub(crate) unsafe fn get_unchecked_internal(&self, begin: usize, end: usize) -> &str {
67        // SAFETY: caller upholds bounds + UTF-8 preconditions.
68        unsafe {
69            let slice = self.data.get_unchecked(begin..end);
70            from_utf8_unchecked(slice)
71        }
72    }
73
74    #[inline]
75    pub fn get_bounds(&self, index: usize) -> Option<(usize, usize)> {
76        if index + 1 > self.ends.len() {
77            return None;
78        }
79        let (start, end) = if index > 0 {
80            (self.ends[index - 1], self.ends[index])
81        } else {
82            (0, self.ends[0])
83        };
84        debug_assert!(start <= end);
85        debug_assert!(end <= self.data.len());
86        Some((start, end))
87    }
88
89    #[inline]
90    pub fn get_top(&self) -> Option<&str> {
91        match self.ends.len() {
92            0 => None,
93            len => self.get(len - 1),
94        }
95    }
96
97    #[inline]
98    pub fn remove_top(&mut self) -> Option<()> {
99        self.ends.pop()?;
100        let end = self.ends.last().copied().unwrap_or(0);
101        self.data.truncate(end);
102        Some(())
103    }
104
105    #[inline]
106    pub fn pop_owned<T>(&mut self) -> Option<T>
107    where
108        T: for<'a> From<&'a str>,
109    {
110        let s = self.get_top()?.into();
111        self.remove_top();
112        Some(s)
113    }
114
115    #[inline]
116    pub fn push(&mut self, s: &str) {
117        self.data.extend_from_slice(s.as_bytes());
118        self.ends.push(self.data.len());
119    }
120
121    #[inline]
122    fn clear(&mut self) {
123        self.data.clear();
124        self.ends.clear();
125    }
126
127    #[inline]
128    pub fn iter(&self) -> StrStackIter<'_> {
129        StrStackIter::new(self)
130    }
131}
132
133#[cfg(test)]
134mod tests {
135    use std::rc::Rc;
136
137    use super::*;
138    use crate::SmartString;
139
140    #[test]
141    fn test_create() {
142        let stack = StrStack::new();
143        assert_eq!(stack.len(), 0);
144        assert!(stack.is_empty());
145        assert_eq!(stack.get_top(), None);
146        assert_eq!(stack.get(0), None);
147        assert_eq!(stack.get_bounds(0), None);
148    }
149
150    #[test]
151    fn test_push() {
152        let mut stack = StrStack::new();
153
154        stack.push("123");
155        assert_eq!(stack.len(), 1);
156        assert!(!stack.is_empty());
157        assert_eq!(stack.get_top(), Some("123"));
158        assert_eq!(stack.get(0), Some("123"));
159        assert_eq!(stack.get_bounds(0), Some((0, 3)));
160        assert_eq!(stack.get(1), None);
161        assert_eq!(stack.get_bounds(1), None);
162
163        stack.push("456");
164        assert_eq!(stack.len(), 2);
165        assert!(!stack.is_empty());
166        assert_eq!(stack.get_top(), Some("456"));
167        assert_eq!(stack.get(0), Some("123"));
168        assert_eq!(stack.get_bounds(0), Some((0, 3)));
169        assert_eq!(stack.get(1), Some("456"));
170        assert_eq!(stack.get_bounds(1), Some((3, 6)));
171        assert_eq!(stack.get(2), None);
172        assert_eq!(stack.get_bounds(2), None);
173    }
174
175    #[test]
176    fn test_remove_top() {
177        let mut stack = StrStack::new();
178
179        stack.push("123");
180        stack.push("456");
181        stack.push("789");
182        assert_eq!(stack.len(), 3);
183
184        assert!(stack.remove_top().is_some());
185        assert_eq!(stack.len(), 2);
186        assert!(!stack.is_empty());
187        assert_eq!(stack.get_top(), Some("456"));
188        assert_eq!(stack.get(0), Some("123"));
189        assert_eq!(stack.get(1), Some("456"));
190        assert!(stack.get(2).is_none());
191        assert!(stack.get_bounds(2).is_none());
192
193        assert!(stack.remove_top().is_some());
194        assert_eq!(stack.len(), 1);
195        assert!(!stack.is_empty());
196        assert_eq!(stack.get_top(), Some("123"));
197        assert_eq!(stack.get(0), Some("123"));
198        assert!(stack.get(1).is_none());
199        assert!(stack.get_bounds(1).is_none());
200
201        assert!(stack.remove_top().is_some());
202        assert_eq!(stack.len(), 0);
203        assert!(stack.is_empty());
204        assert!(stack.get_top().is_none());
205        assert!(stack.get(0).is_none());
206        assert!(stack.get_bounds(0).is_none());
207
208        assert!(stack.remove_top().is_none());
209    }
210
211    #[test]
212    fn test_pop_owned() {
213        let mut stack = StrStack::new();
214
215        stack.push("123");
216        stack.push("456");
217        stack.push("789");
218        assert_eq!(stack.len(), 3);
219
220        assert_eq!(stack.pop_owned::<String>(), Some("789".into()));
221        assert_eq!(stack.len(), 2);
222        assert_eq!(stack.get_top(), Some("456"));
223        assert_eq!(stack.get(0), Some("123"));
224        assert_eq!(stack.get(1), Some("456"));
225        assert!(stack.get(2).is_none());
226        assert!(stack.get_bounds(2).is_none());
227
228        assert_eq!(stack.pop_owned::<SmartString>(), Some("456".into()));
229        assert_eq!(stack.len(), 1);
230        assert_eq!(stack.get_top(), Some("123"));
231        assert_eq!(stack.get(0), Some("123"));
232        assert!(stack.get(1).is_none());
233        assert!(stack.get_bounds(1).is_none());
234
235        assert_eq!(stack.pop_owned::<Rc<str>>(), Some("123".into()));
236        assert_eq!(stack.len(), 0);
237        assert!(stack.get_top().is_none());
238        assert!(stack.get(0).is_none());
239        assert!(stack.get_bounds(0).is_none());
240
241        assert!(stack.pop_owned::<Box<str>>().is_none());
242    }
243
244    #[test]
245    fn test_iter() {
246        let mut stack = StrStack::new();
247
248        stack.push("123");
249        stack.push("456");
250        stack.push("789");
251
252        let mut iter = stack.iter();
253        assert_eq!(iter.next(), Some("123"));
254        assert_eq!(iter.next(), Some("456"));
255        assert_eq!(iter.next(), Some("789"));
256        assert_eq!(iter.next(), None);
257        assert_eq!(iter.next(), None);
258    }
259
260    #[test]
261    fn test_unicode_push_get_bounds_and_as_str() {
262        let mut stack = StrStack::new();
263        stack.push("€"); // 3 bytes
264        stack.push("a"); // 1 byte
265        stack.push("😊"); // 4 bytes
266
267        assert_eq!(stack.as_str(), "€a😊");
268
269        assert_eq!(stack.get(0), Some("€"));
270        assert_eq!(stack.get(1), Some("a"));
271        assert_eq!(stack.get(2), Some("😊"));
272
273        assert_eq!(stack.get_bounds(0), Some((0, 3)));
274        assert_eq!(stack.get_bounds(1), Some((3, 4)));
275        assert_eq!(stack.get_bounds(2), Some((4, 8)));
276    }
277
278    #[test]
279    fn test_unicode_remove_top_truncates_byte_buffer() {
280        let mut stack = StrStack::new();
281        stack.push("€"); // 3 bytes
282        stack.push("😊"); // 4 bytes
283        stack.push("a"); // 1 byte
284
285        assert_eq!(stack.as_str(), "€😊a");
286        assert_eq!(stack.len(), 3);
287
288        stack.remove_top().unwrap();
289        assert_eq!(stack.as_str(), "€😊");
290        assert_eq!(stack.len(), 2);
291        assert_eq!(stack.get_top(), Some("😊"));
292
293        stack.remove_top().unwrap();
294        assert_eq!(stack.as_str(), "€");
295        assert_eq!(stack.len(), 1);
296        assert_eq!(stack.get_top(), Some("€"));
297    }
298
299    // -- push/remove/push mutation sequences ---------------------------------------------------------
300
301    #[test]
302    fn test_push_remove_push_sequence() {
303        let mut stack = StrStack::new();
304        stack.push("aaa");
305        stack.push("bbb");
306        stack.push("ccc");
307        assert_eq!(stack.len(), 3);
308
309        // Remove top two
310        stack.remove_top();
311        stack.remove_top();
312        assert_eq!(stack.len(), 1);
313        assert_eq!(stack.as_str(), "aaa");
314        assert_eq!(stack.get(0), Some("aaa"));
315
316        // Push again after removal
317        stack.push("ddd");
318        stack.push("eee");
319        assert_eq!(stack.len(), 3);
320        assert_eq!(stack.as_str(), "aaadddeee");
321        assert_eq!(stack.get(0), Some("aaa"));
322        assert_eq!(stack.get(1), Some("ddd"));
323        assert_eq!(stack.get(2), Some("eee"));
324
325        // Iterator should yield the correct segments
326        let collected: Vec<&str> = stack.iter().collect();
327        assert_eq!(collected, vec!["aaa", "ddd", "eee"]);
328    }
329
330    #[test]
331    fn test_push_remove_all_push_again() {
332        let mut stack = StrStack::new();
333        stack.push("first");
334        stack.push("second");
335
336        stack.remove_top();
337        stack.remove_top();
338        assert!(stack.is_empty());
339        assert_eq!(stack.as_str(), "");
340
341        stack.push("third");
342        assert_eq!(stack.len(), 1);
343        assert_eq!(stack.get(0), Some("third"));
344        assert_eq!(stack.as_str(), "third");
345    }
346
347    #[test]
348    fn test_push_remove_push_unicode() {
349        let mut stack = StrStack::new();
350        stack.push("你好"); // 6 bytes
351        stack.push("世界"); // 6 bytes
352        assert_eq!(stack.as_str(), "你好世界");
353
354        stack.remove_top();
355        assert_eq!(stack.as_str(), "你好");
356
357        stack.push("🦀"); // 4 bytes
358        assert_eq!(stack.as_str(), "你好🦀");
359        assert_eq!(stack.get(0), Some("你好"));
360        assert_eq!(stack.get(1), Some("🦀"));
361
362        let collected: Vec<&str> = stack.iter().collect();
363        assert_eq!(collected, vec!["你好", "🦀"]);
364    }
365
366    #[test]
367    fn test_as_str_equals_iter_concatenation() {
368        let mut stack = StrStack::new();
369        stack.push("abc");
370        stack.push("€");
371        stack.push("def");
372        stack.remove_top();
373        stack.push("ghi");
374        stack.push("😊");
375
376        let concatenated: String = stack.iter().collect();
377        assert_eq!(stack.as_str(), concatenated.as_str());
378    }
379
380    // -- clear ---------------------------------------------------------------------------------------
381
382    #[test]
383    fn test_clear() {
384        let mut stack = StrStack::new();
385        stack.push("hello");
386        stack.push("world");
387        assert_eq!(stack.len(), 2);
388
389        // clear is private, but we can test it via the serde roundtrip
390        // or through repeated remove_top. Let's test the invariant:
391        // after removing all items, the stack is fully clean.
392        stack.remove_top();
393        stack.remove_top();
394        assert!(stack.is_empty());
395        assert_eq!(stack.len(), 0);
396        assert_eq!(stack.as_str(), "");
397        assert!(stack.iter().next().is_none());
398
399        // Can push again
400        stack.push("new");
401        assert_eq!(stack.len(), 1);
402        assert_eq!(stack.get(0), Some("new"));
403    }
404
405    // -- empty string segments -----------------------------------------------------------------------
406
407    #[test]
408    fn test_push_empty_strings() {
409        let mut stack = StrStack::new();
410        stack.push("");
411        stack.push("abc");
412        stack.push("");
413
414        assert_eq!(stack.len(), 3);
415        assert_eq!(stack.get(0), Some(""));
416        assert_eq!(stack.get(1), Some("abc"));
417        assert_eq!(stack.get(2), Some(""));
418        assert_eq!(stack.as_str(), "abc");
419
420        let collected: Vec<&str> = stack.iter().collect();
421        assert_eq!(collected, vec!["", "abc", ""]);
422    }
423}
smart_string/str_stack/mod.rs

smart_string/str_stack/
mod.rs
