icu_locale_core/shortvec/
mod.rs

1// This file is part of ICU4X. For terms of use, please see the file
2// called LICENSE at the top level of the ICU4X source tree
3// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ).
4
5//! This module includes variable-length data types that are const-constructible for single
6//! values and overflow to the heap.
7//!
8//! # Why?
9//!
10//! This module is far from the first stack-or-heap vector in the Rust ecosystem. It was created
11//! with the following value proposition:
12//!
13//! 1. Enable safe const construction of stack collections.
14//! 2. Avoid stack size penalties common with stack-or-heap collections.
15//!
16//! As of this writing, `heapless` and `tinyvec` don't support const construction except
17//! for empty vectors, and `smallvec` supports it on unstable.
18//!
19//! Additionally, [`ShortBoxSlice`] has a smaller stack size than any of these:
20//!
21//! ```ignore
22//! // NonZeroU64 has a niche that this module utilizes
23//! use core::num::NonZeroU64;
24//!
25//! // ShortBoxSlice is the same size as `Box<[]>` for small or nichey values
26//! assert_eq!(16, size_of::<shortvec::ShortBoxSlice::<NonZeroU64>>());
27//!
28//! // Note: SmallVec supports pushing and therefore has a capacity field
29//! assert_eq!(24, size_of::<smallvec::SmallVec::<[NonZeroU64; 1]>>());
30//!
31//! // Note: heapless doesn't support spilling to the heap
32//! assert_eq!(16, size_of::<heapless::Vec::<NonZeroU64, 1>>());
33//!
34//! // Note: TinyVec only supports types that implement `Default`
35//! assert_eq!(24, size_of::<tinyvec::TinyVec::<[u64; 1]>>());
36//! ```
37//!
38//! The module is `no_std` with `alloc`.
39
40mod litemap;
41
42#[cfg(feature = "alloc")]
43use alloc::boxed::Box;
44#[cfg(feature = "alloc")]
45use alloc::vec;
46#[cfg(feature = "alloc")]
47use alloc::vec::Vec;
48use core::ops::Deref;
49use core::ops::DerefMut;
50
51/// A boxed slice that supports no-allocation, constant values if length 0 or 1.
52/// Using `ZeroOne(Option<T>)` saves 8 bytes in [`ShortBoxSlice`] via niche optimization.
53#[derive(Debug, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
54pub(crate) enum ShortBoxSliceInner<T> {
55    ZeroOne(Option<T>),
56    #[cfg(feature = "alloc")]
57    Multi(Box<[T]>),
58    #[cfg(not(feature = "alloc"))]
59    Two([T; 2]),
60}
61
62impl<T> Default for ShortBoxSliceInner<T> {
63    fn default() -> Self {
64        use ShortBoxSliceInner::*;
65        ZeroOne(None)
66    }
67}
68
69/// A boxed slice that supports no-allocation, constant values if length 0 or 1.
70///
71/// Supports mutation but always reallocs when mutated.
72#[derive(Debug, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
73pub(crate) struct ShortBoxSlice<T>(ShortBoxSliceInner<T>);
74
75impl<T> Default for ShortBoxSlice<T> {
76    fn default() -> Self {
77        Self(Default::default())
78    }
79}
80
81impl<T> ShortBoxSlice<T> {
82    /// Creates a new, empty [`ShortBoxSlice`].
83    #[inline]
84    pub const fn new() -> Self {
85        use ShortBoxSliceInner::*;
86        Self(ZeroOne(None))
87    }
88
89    /// Creates a new [`ShortBoxSlice`] containing a single element.
90    #[inline]
91    pub const fn new_single(item: T) -> Self {
92        use ShortBoxSliceInner::*;
93        Self(ZeroOne(Some(item)))
94    }
95
96    pub fn new_double(first: T, second: T) -> Self {
97        use ShortBoxSliceInner::*;
98        #[cfg(feature = "alloc")]
99        return Self(Multi(vec![first, second].into_boxed_slice()));
100        #[cfg(not(feature = "alloc"))]
101        return Self(Two([first, second]));
102    }
103
104    /// Pushes an element onto this [`ShortBoxSlice`].
105    ///
106    /// Reallocs if more than 1 item is already in the collection.
107    #[cfg(feature = "alloc")]
108    pub fn push(&mut self, item: T) {
109        use ShortBoxSliceInner::*;
110        self.0 = match core::mem::replace(&mut self.0, ZeroOne(None)) {
111            ZeroOne(None) => ZeroOne(Some(item)),
112            ZeroOne(Some(prev_item)) => Multi(vec![prev_item, item].into_boxed_slice()),
113            Multi(items) => {
114                let mut items = items.into_vec();
115                items.push(item);
116                Multi(items.into_boxed_slice())
117            }
118        };
119    }
120
121    /// Gets a single element from the [`ShortBoxSlice`].
122    ///
123    /// Returns `None` if empty or more than one element.
124    #[inline]
125    pub const fn single(&self) -> Option<&T> {
126        use ShortBoxSliceInner::*;
127        match self.0 {
128            ZeroOne(Some(ref v)) => Some(v),
129            _ => None,
130        }
131    }
132
133    /// Destruct into a single element of the [`ShortBoxSlice`].
134    ///
135    /// Returns `None` if empty or more than one element.
136    pub fn into_single(self) -> Option<T> {
137        use ShortBoxSliceInner::*;
138        match self.0 {
139            ZeroOne(Some(v)) => Some(v),
140            _ => None,
141        }
142    }
143
144    /// Returns the number of elements in the collection.
145    #[inline]
146    pub fn len(&self) -> usize {
147        use ShortBoxSliceInner::*;
148        match self.0 {
149            ZeroOne(None) => 0,
150            ZeroOne(_) => 1,
151            #[cfg(feature = "alloc")]
152            Multi(ref v) => v.len(),
153            #[cfg(not(feature = "alloc"))]
154            Two(_) => 2,
155        }
156    }
157
158    /// Returns whether the collection is empty.
159    #[inline]
160    pub const fn is_empty(&self) -> bool {
161        use ShortBoxSliceInner::*;
162        matches!(self.0, ZeroOne(None))
163    }
164
165    /// Inserts an element at the specified index into the collection.
166    ///
167    /// Reallocs if more than 1 item is already in the collection.
168    #[cfg(feature = "alloc")]
169    pub fn insert(&mut self, index: usize, elt: T) {
170        use ShortBoxSliceInner::*;
171        assert!(
172            index <= self.len(),
173            "insertion index (is {}) should be <= len (is {})",
174            index,
175            self.len()
176        );
177
178        self.0 = match core::mem::replace(&mut self.0, ZeroOne(None)) {
179            ZeroOne(None) => ZeroOne(Some(elt)),
180            ZeroOne(Some(item)) => {
181                let items = if index == 0 {
182                    vec![elt, item].into_boxed_slice()
183                } else {
184                    vec![item, elt].into_boxed_slice()
185                };
186                Multi(items)
187            }
188            Multi(items) => {
189                let mut items = items.into_vec();
190                items.insert(index, elt);
191                Multi(items.into_boxed_slice())
192            }
193        }
194    }
195
196    /// Removes the element at the specified index from the collection.
197    ///
198    /// Reallocs if more than 2 items are in the collection.
199    pub fn remove(&mut self, index: usize) -> T {
200        use ShortBoxSliceInner::*;
201        assert!(
202            index < self.len(),
203            "removal index (is {}) should be < len (is {})",
204            index,
205            self.len()
206        );
207
208        let (replaced, removed_item) = match core::mem::replace(&mut self.0, ZeroOne(None)) {
209            ZeroOne(None) => unreachable!(),
210            ZeroOne(Some(v)) => (ZeroOne(None), v),
211            #[cfg(feature = "alloc")]
212            Multi(v) => {
213                let mut v = v.into_vec();
214                let removed_item = v.remove(index);
215                match v.len() {
216                    #[expect(clippy::unwrap_used)]
217                    // we know that the vec has exactly one element left
218                    1 => (ZeroOne(Some(v.pop().unwrap())), removed_item),
219                    // v has at least 2 elements, create a Multi variant
220                    _ => (Multi(v.into_boxed_slice()), removed_item),
221                }
222            }
223            #[cfg(not(feature = "alloc"))]
224            Two([f, s]) => (ZeroOne(Some(f)), s),
225        };
226        self.0 = replaced;
227        removed_item
228    }
229
230    /// Removes all elements from the collection.
231    #[inline]
232    pub fn clear(&mut self) {
233        use ShortBoxSliceInner::*;
234        let _ = core::mem::replace(&mut self.0, ZeroOne(None));
235    }
236
237    /// Retains only the elements specified by the predicate.
238    #[allow(dead_code)]
239    pub fn retain<F>(&mut self, mut f: F)
240    where
241        F: FnMut(&T) -> bool,
242    {
243        use ShortBoxSliceInner::*;
244        match core::mem::take(&mut self.0) {
245            ZeroOne(Some(one)) if f(&one) => self.0 = ZeroOne(Some(one)),
246            ZeroOne(_) => self.0 = ZeroOne(None),
247            #[cfg(feature = "alloc")]
248            Multi(slice) => {
249                let mut vec = slice.into_vec();
250                vec.retain(f);
251                *self = ShortBoxSlice::from(vec)
252            }
253            #[cfg(not(feature = "alloc"))]
254            Two([first, second]) => {
255                *self = match (Some(first).filter(&mut f), Some(second).filter(&mut f)) {
256                    (None, None) => ShortBoxSlice::new(),
257                    (None, Some(x)) | (Some(x), None) => ShortBoxSlice::new_single(x),
258                    (Some(f), Some(s)) => ShortBoxSlice::new_double(f, s),
259                }
260            }
261        };
262    }
263}
264
265impl<T> Deref for ShortBoxSlice<T> {
266    type Target = [T];
267
268    fn deref(&self) -> &Self::Target {
269        use ShortBoxSliceInner::*;
270        match self.0 {
271            ZeroOne(None) => &[],
272            ZeroOne(Some(ref v)) => core::slice::from_ref(v),
273            #[cfg(feature = "alloc")]
274            Multi(ref v) => v,
275            #[cfg(not(feature = "alloc"))]
276            Two(ref v) => v,
277        }
278    }
279}
280
281impl<T> DerefMut for ShortBoxSlice<T> {
282    fn deref_mut(&mut self) -> &mut Self::Target {
283        use ShortBoxSliceInner::*;
284        match self.0 {
285            ZeroOne(None) => &mut [],
286            ZeroOne(Some(ref mut v)) => core::slice::from_mut(v),
287            #[cfg(feature = "alloc")]
288            Multi(ref mut v) => v,
289            #[cfg(not(feature = "alloc"))]
290            Two(ref mut v) => v,
291        }
292    }
293}
294
295#[cfg(feature = "alloc")]
296impl<T> From<Vec<T>> for ShortBoxSlice<T> {
297    fn from(v: Vec<T>) -> Self {
298        use ShortBoxSliceInner::*;
299        match v.len() {
300            0 => Self(ZeroOne(None)),
301            #[expect(clippy::unwrap_used)] // we know that the vec is not empty
302            1 => Self(ZeroOne(Some(v.into_iter().next().unwrap()))),
303            _ => Self(Multi(v.into_boxed_slice())),
304        }
305    }
306}
307
308#[cfg(feature = "alloc")]
309impl<T> FromIterator<T> for ShortBoxSlice<T> {
310    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
311        use ShortBoxSliceInner::*;
312        let mut iter = iter.into_iter();
313        match (iter.next(), iter.next()) {
314            (Some(first), Some(second)) => {
315                // Size hint behaviour same as `Vec::extend` + 2
316                let mut vec = Vec::with_capacity(iter.size_hint().0.saturating_add(3));
317                vec.push(first);
318                vec.push(second);
319                vec.extend(iter);
320                Self(Multi(vec.into_boxed_slice()))
321            }
322            (first, _) => Self(ZeroOne(first)),
323        }
324    }
325}
326
327/// An iterator that yields elements from a [`ShortBoxSlice`].
328#[derive(Debug)]
329pub struct ShortBoxSliceIntoIter<T>(ShortBoxSliceIntoIterInner<T>);
330
331#[derive(Debug)]
332pub(crate) enum ShortBoxSliceIntoIterInner<T> {
333    ZeroOne(Option<T>),
334    #[cfg(feature = "alloc")]
335    Multi(vec::IntoIter<T>),
336    #[cfg(not(feature = "alloc"))]
337    Two(core::array::IntoIter<T, 2>),
338}
339
340impl<T> Iterator for ShortBoxSliceIntoIter<T> {
341    type Item = T;
342    fn next(&mut self) -> Option<T> {
343        use ShortBoxSliceIntoIterInner::*;
344        match &mut self.0 {
345            ZeroOne(option) => option.take(),
346            #[cfg(feature = "alloc")]
347            Multi(into_iter) => into_iter.next(),
348            #[cfg(not(feature = "alloc"))]
349            Two(into_iter) => into_iter.next(),
350        }
351    }
352}
353
354impl<T> IntoIterator for ShortBoxSlice<T> {
355    type Item = T;
356    type IntoIter = ShortBoxSliceIntoIter<T>;
357
358    fn into_iter(self) -> Self::IntoIter {
359        match self.0 {
360            ShortBoxSliceInner::ZeroOne(option) => {
361                ShortBoxSliceIntoIter(ShortBoxSliceIntoIterInner::ZeroOne(option))
362            }
363            // TODO: Use a boxed slice IntoIter impl when available:
364            // <https://github.com/rust-lang/rust/issues/59878>
365            #[cfg(feature = "alloc")]
366            ShortBoxSliceInner::Multi(boxed_slice) => ShortBoxSliceIntoIter(
367                ShortBoxSliceIntoIterInner::Multi(boxed_slice.into_vec().into_iter()),
368            ),
369            #[cfg(not(feature = "alloc"))]
370            ShortBoxSliceInner::Two(arr) => {
371                ShortBoxSliceIntoIter(ShortBoxSliceIntoIterInner::Two(arr.into_iter()))
372            }
373        }
374    }
375}
376
377#[cfg(test)]
378mod tests {
379    use super::*;
380
381    #[test]
382    #[expect(clippy::get_first)]
383    fn test_new_single_const() {
384        const MY_CONST_SLICE: ShortBoxSlice<i32> = ShortBoxSlice::new_single(42);
385
386        assert_eq!(MY_CONST_SLICE.len(), 1);
387        assert_eq!(MY_CONST_SLICE.get(0), Some(&42));
388    }
389
390    #[test]
391    #[expect(clippy::redundant_pattern_matching)]
392    fn test_get_single() {
393        let mut vec = ShortBoxSlice::new();
394        assert!(matches!(vec.single(), None));
395
396        vec.push(100);
397        assert!(matches!(vec.single(), Some(_)));
398
399        vec.push(200);
400        assert!(matches!(vec.single(), None));
401    }
402}
icu_locale_core/shortvec/mod.rs

icu_locale_core/shortvec/
mod.rs
