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//! use core::mem::size_of;
23//!
24//! // NonZeroU64 has a niche that this module utilizes
25//! use core::num::NonZeroU64;
26//!
27//! // ShortBoxSlice is the same size as `Box<[]>` for small or nichey values
28//! assert_eq!(16, size_of::<shortvec::ShortBoxSlice::<NonZeroU64>>());
29//!
30//! // Note: SmallVec supports pushing and therefore has a capacity field
31//! assert_eq!(24, size_of::<smallvec::SmallVec::<[NonZeroU64; 1]>>());
32//!
33//! // Note: heapless doesn't support spilling to the heap
34//! assert_eq!(16, size_of::<heapless::Vec::<NonZeroU64, 1>>());
35//!
36//! // Note: TinyVec only supports types that implement `Default`
37//! assert_eq!(24, size_of::<tinyvec::TinyVec::<[u64; 1]>>());
38//! ```
39//!
40//! The module is `no_std` with `alloc`.
41
42mod litemap;
43
44use alloc::boxed::Box;
45use alloc::vec;
46use alloc::vec::Vec;
47use core::ops::Deref;
48use core::ops::DerefMut;
49
50/// A boxed slice that supports no-allocation, constant values if length 0 or 1.
51/// Using ZeroOne(Option<T>) saves 8 bytes in ShortBoxSlice via niche optimization.
52#[derive(Debug, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
53pub(crate) enum ShortBoxSliceInner<T> {
54 ZeroOne(Option<T>),
55 Multi(Box<[T]>),
56}
57
58impl<T> Default for ShortBoxSliceInner<T> {
59 fn default() -> Self {
60 use ShortBoxSliceInner::*;
61 ZeroOne(None)
62 }
63}
64
65/// A boxed slice that supports no-allocation, constant values if length 0 or 1.
66///
67/// Supports mutation but always reallocs when mutated.
68#[derive(Debug, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
69pub(crate) struct ShortBoxSlice<T>(ShortBoxSliceInner<T>);
70
71impl<T> Default for ShortBoxSlice<T> {
72 fn default() -> Self {
73 Self(Default::default())
74 }
75}
76
77impl<T> ShortBoxSlice<T> {
78 /// Creates a new, empty [`ShortBoxSlice`].
79 #[inline]
80 pub const fn new() -> Self {
81 use ShortBoxSliceInner::*;
82 Self(ZeroOne(None))
83 }
84
85 /// Creates a new [`ShortBoxSlice`] containing a single element.
86 #[inline]
87 pub const fn new_single(item: T) -> Self {
88 use ShortBoxSliceInner::*;
89 Self(ZeroOne(Some(item)))
90 }
91
92 /// Pushes an element onto this [`ShortBoxSlice`].
93 ///
94 /// Reallocs if more than 1 item is already in the collection.
95 pub fn push(&mut self, item: T) {
96 use ShortBoxSliceInner::*;
97 self.0 = match core::mem::replace(&mut self.0, ZeroOne(None)) {
98 ZeroOne(None) => ZeroOne(Some(item)),
99 ZeroOne(Some(prev_item)) => Multi(vec![prev_item, item].into_boxed_slice()),
100 Multi(items) => {
101 let mut items = items.into_vec();
102 items.push(item);
103 Multi(items.into_boxed_slice())
104 }
105 };
106 }
107
108 /// Gets a single element from the [`ShortBoxSlice`].
109 ///
110 /// Returns `None` if empty or more than one element.
111 #[inline]
112 pub const fn single(&self) -> Option<&T> {
113 use ShortBoxSliceInner::*;
114 match self.0 {
115 ZeroOne(Some(ref v)) => Some(v),
116 _ => None,
117 }
118 }
119
120 /// Returns the number of elements in the collection.
121 #[inline]
122 pub fn len(&self) -> usize {
123 use ShortBoxSliceInner::*;
124 match self.0 {
125 ZeroOne(None) => 0,
126 ZeroOne(_) => 1,
127 Multi(ref v) => v.len(),
128 }
129 }
130
131 /// Returns whether the collection is empty.
132 #[inline]
133 pub fn is_empty(&self) -> bool {
134 use ShortBoxSliceInner::*;
135 matches!(self.0, ZeroOne(None))
136 }
137
138 /// Inserts an element at the specified index into the collection.
139 ///
140 /// Reallocs if more than 1 item is already in the collection.
141 pub fn insert(&mut self, index: usize, elt: T) {
142 use ShortBoxSliceInner::*;
143 assert!(
144 index <= self.len(),
145 "insertion index (is {}) should be <= len (is {})",
146 index,
147 self.len()
148 );
149
150 self.0 = match core::mem::replace(&mut self.0, ZeroOne(None)) {
151 ZeroOne(None) => ZeroOne(Some(elt)),
152 ZeroOne(Some(item)) => {
153 let items = if index == 0 {
154 vec![elt, item].into_boxed_slice()
155 } else {
156 vec![item, elt].into_boxed_slice()
157 };
158 Multi(items)
159 }
160 Multi(items) => {
161 let mut items = items.into_vec();
162 items.insert(index, elt);
163 Multi(items.into_boxed_slice())
164 }
165 }
166 }
167
168 /// Removes the element at the specified index from the collection.
169 ///
170 /// Reallocs if more than 2 items are in the collection.
171 pub fn remove(&mut self, index: usize) -> T {
172 use ShortBoxSliceInner::*;
173 assert!(
174 index < self.len(),
175 "removal index (is {}) should be < len (is {})",
176 index,
177 self.len()
178 );
179
180 let (replaced, removed_item) = match core::mem::replace(&mut self.0, ZeroOne(None)) {
181 ZeroOne(None) => unreachable!(),
182 ZeroOne(Some(v)) => (ZeroOne(None), v),
183 Multi(v) => {
184 let mut v = v.into_vec();
185 let removed_item = v.remove(index);
186 match v.len() {
187 #[allow(clippy::unwrap_used)]
188 // we know that the vec has exactly one element left
189 1 => (ZeroOne(Some(v.pop().unwrap())), removed_item),
190 // v has at least 2 elements, create a Multi variant
191 _ => (Multi(v.into_boxed_slice()), removed_item),
192 }
193 }
194 };
195 self.0 = replaced;
196 removed_item
197 }
198
199 /// Removes all elements from the collection.
200 #[inline]
201 pub fn clear(&mut self) {
202 use ShortBoxSliceInner::*;
203 let _ = core::mem::replace(&mut self.0, ZeroOne(None));
204 }
205
206 /// Retains only the elements specified by the predicate.
207 pub fn retain<F>(&mut self, mut f: F)
208 where
209 F: FnMut(&T) -> bool,
210 {
211 use ShortBoxSliceInner::*;
212 match core::mem::take(&mut self.0) {
213 ZeroOne(Some(one)) if f(&one) => self.0 = ZeroOne(Some(one)),
214 ZeroOne(_) => self.0 = ZeroOne(None),
215 Multi(slice) => {
216 let mut vec = slice.into_vec();
217 vec.retain(f);
218 *self = ShortBoxSlice::from(vec)
219 }
220 };
221 }
222}
223
224impl<T> Deref for ShortBoxSlice<T> {
225 type Target = [T];
226
227 fn deref(&self) -> &Self::Target {
228 use ShortBoxSliceInner::*;
229 match self.0 {
230 ZeroOne(None) => &[],
231 ZeroOne(Some(ref v: &T)) => core::slice::from_ref(v),
232 Multi(ref v: &Box<[T]>) => v,
233 }
234 }
235}
236
237impl<T> DerefMut for ShortBoxSlice<T> {
238 fn deref_mut(&mut self) -> &mut Self::Target {
239 use ShortBoxSliceInner::*;
240 match self.0 {
241 ZeroOne(None) => &mut [],
242 ZeroOne(Some(ref mut v: &mut T)) => core::slice::from_mut(v),
243 Multi(ref mut v: &mut Box<[T]>) => v,
244 }
245 }
246}
247
248impl<T> From<Vec<T>> for ShortBoxSlice<T> {
249 fn from(v: Vec<T>) -> Self {
250 use ShortBoxSliceInner::*;
251 match v.len() {
252 0 => Self(ZeroOne(None)),
253 #[allow(clippy::unwrap_used)] // we know that the vec is not empty
254 1 => Self(ZeroOne(Some(v.into_iter().next().unwrap()))),
255 _ => Self(Multi(v.into_boxed_slice())),
256 }
257 }
258}
259
260impl<T> FromIterator<T> for ShortBoxSlice<T> {
261 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
262 use ShortBoxSliceInner::*;
263 let mut iter: ::IntoIter = iter.into_iter();
264 match (iter.next(), iter.next()) {
265 (Some(first: T), Some(second: T)) => {
266 // Size hint behaviour same as `Vec::extend` + 2
267 let mut vec: Vec = Vec::with_capacity(iter.size_hint().0.saturating_add(3));
268 vec.push(first);
269 vec.push(second);
270 vec.extend(iter);
271 Self(Multi(vec.into_boxed_slice()))
272 }
273 (first: Option, _) => Self(ZeroOne(first)),
274 }
275 }
276}
277
278/// An iterator that yields elements from a [`ShortBoxSlice`].
279#[derive(Debug)]
280pub struct ShortBoxSliceIntoIter<T>(ShortBoxSliceIntoIterInner<T>);
281
282#[derive(Debug)]
283pub(crate) enum ShortBoxSliceIntoIterInner<T> {
284 ZeroOne(Option<T>),
285 Multi(alloc::vec::IntoIter<T>),
286}
287
288impl<T> Iterator for ShortBoxSliceIntoIter<T> {
289 type Item = T;
290 fn next(&mut self) -> Option<T> {
291 use ShortBoxSliceIntoIterInner::*;
292 match &mut self.0 {
293 ZeroOne(option: &mut Option) => option.take(),
294 Multi(into_iter: &mut IntoIter) => into_iter.next(),
295 }
296 }
297}
298
299impl<T> IntoIterator for ShortBoxSlice<T> {
300 type Item = T;
301 type IntoIter = ShortBoxSliceIntoIter<T>;
302
303 fn into_iter(self) -> Self::IntoIter {
304 match self.0 {
305 ShortBoxSliceInner::ZeroOne(option: Option) => {
306 ShortBoxSliceIntoIter(ShortBoxSliceIntoIterInner::ZeroOne(option))
307 }
308 // TODO: Use a boxed slice IntoIter impl when available:
309 // <https://github.com/rust-lang/rust/issues/59878>
310 ShortBoxSliceInner::Multi(boxed_slice: Box<[T]>) => ShortBoxSliceIntoIter(
311 ShortBoxSliceIntoIterInner::Multi(boxed_slice.into_vec().into_iter()),
312 ),
313 }
314 }
315}
316
317#[cfg(test)]
318mod tests {
319 use super::*;
320
321 #[test]
322 #[allow(clippy::get_first)]
323 fn test_new_single_const() {
324 const MY_CONST_SLICE: ShortBoxSlice<i32> = ShortBoxSlice::new_single(42);
325
326 assert_eq!(MY_CONST_SLICE.len(), 1);
327 assert_eq!(MY_CONST_SLICE.get(0), Some(&42));
328 }
329
330 #[test]
331 #[allow(clippy::redundant_pattern_matching)]
332 fn test_get_single() {
333 let mut vec = ShortBoxSlice::new();
334 assert!(matches!(vec.single(), None));
335
336 vec.push(100);
337 assert!(matches!(vec.single(), Some(_)));
338
339 vec.push(200);
340 assert!(matches!(vec.single(), None));
341 }
342}
343