zerotrie/builder/konst/
store.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 contains internal collections for the const builder.
6
7use super::super::branch_meta::BranchMeta;
8
9/// A const-friendly slice type. It is backed by a full slice but is primarily intended
10/// to represent subslices of the full slice. We need this only because we can't take
11/// subslices in const Rust.
12#[derive(Debug, Copy, Clone)]
13pub(crate) struct ConstSlice<'a, T> {
14    /// The full slice.
15    full_slice: &'a [T],
16    /// The start index of the slice represented by this [`ConstSlice`].
17    start: usize,
18    /// The non-inclusive end index of the slice represented by this [`ConstSlice`].
19    limit: usize,
20}
21
22impl<'a, T> ConstSlice<'a, T> {
23    /// Creates a [`ConstSlice`] representing an entire slice.
24    pub const fn from_slice(other: &'a [T]) -> Self {
25        ConstSlice {
26            full_slice: other,
27            start: 0,
28            limit: other.len(),
29        }
30    }
31
32    /// Creates a [`ConstSlice`] with the given start and limit.
33    pub const fn from_manual_slice(full_slice: &'a [T], start: usize, limit: usize) -> Self {
34        ConstSlice {
35            full_slice,
36            start,
37            limit,
38        }
39    }
40
41    /// Returns the length of the [`ConstSlice`].
42    pub const fn len(&self) -> usize {
43        self.limit - self.start
44    }
45
46    /// Gets the element at `index`, panicking if not present.
47    pub const fn get_or_panic(&self, index: usize) -> &T {
48        &self.full_slice[index + self.start]
49    }
50
51    /// Gets the first element or `None` if empty.
52    #[cfg(test)]
53    pub const fn first(&self) -> Option<&T> {
54        if self.len() == 0 {
55            None
56        } else {
57            Some(self.get_or_panic(0))
58        }
59    }
60
61    /// Gets the last element or `None` if empty.
62    pub const fn last(&self) -> Option<&T> {
63        if self.len() == 0 {
64            None
65        } else {
66            Some(self.get_or_panic(self.len() - 1))
67        }
68    }
69
70    /// Gets a subslice of this slice.
71    #[cfg(test)]
72    pub const fn get_subslice_or_panic(
73        &self,
74        new_start: usize,
75        new_limit: usize,
76    ) -> ConstSlice<'a, T> {
77        assert!(new_start <= new_limit);
78        assert!(new_limit <= self.len());
79        ConstSlice {
80            full_slice: self.full_slice,
81            start: self.start + new_start,
82            limit: self.start + new_limit,
83        }
84    }
85
86    /// Non-const function that returns this [`ConstSlice`] as a regular slice.
87    #[cfg(any(test, feature = "alloc"))]
88    pub fn as_slice(&self) -> &'a [T] {
89        &self.full_slice[self.start..self.limit]
90    }
91}
92
93impl<'a, T> From<&'a [T]> for ConstSlice<'a, T> {
94    fn from(other: &'a [T]) -> Self {
95        Self::from_slice(other)
96    }
97}
98
99/// A const-friendly mutable data structure backed by an array.
100#[derive(Debug, Copy, Clone)]
101pub(crate) struct ConstArrayBuilder<const N: usize, T> {
102    full_array: [T; N],
103    start: usize,
104    limit: usize,
105}
106
107impl<const N: usize, T: Default> Default for ConstArrayBuilder<N, T> {
108    fn default() -> Self {
109        Self::new_empty([(); N].map(|_| Default::default()), 0)
110    }
111}
112
113impl<const N: usize, T> ConstArrayBuilder<N, T> {
114    /// Creates a new, empty builder of the given size. `cursor` indicates where in the
115    /// array new elements will be inserted first. Since we use a lot of prepend operations,
116    /// it is common to set `cursor` to `N`.
117    pub const fn new_empty(full_array: [T; N], cursor: usize) -> Self {
118        assert!(cursor <= N);
119        Self {
120            full_array,
121            start: cursor,
122            limit: cursor,
123        }
124    }
125
126    /// Creates a new builder with some initial content in `[start, limit)`.
127    pub const fn from_manual_slice(full_array: [T; N], start: usize, limit: usize) -> Self {
128        assert!(start <= limit);
129        assert!(limit <= N);
130        Self {
131            full_array,
132            start,
133            limit,
134        }
135    }
136
137    /// Returns the number of initialized elements in the builder.
138    pub const fn len(&self) -> usize {
139        self.limit - self.start
140    }
141
142    /// Whether there are no initialized elements in the builder.
143    #[allow(dead_code)]
144    pub const fn is_empty(&self) -> bool {
145        self.len() == 0
146    }
147
148    /// Returns the initialized elements as a [`ConstSlice`].
149    pub const fn as_const_slice(&self) -> ConstSlice<T> {
150        ConstSlice::from_manual_slice(&self.full_array, self.start, self.limit)
151    }
152
153    /// Non-const function that returns a slice of the initialized elements.
154    #[cfg(any(test, feature = "alloc"))]
155    pub fn as_slice(&self) -> &[T] {
156        &self.full_array[self.start..self.limit]
157    }
158}
159
160// Certain functions that involve dropping `T` require that it be `Copy`
161impl<const N: usize, T: Copy> ConstArrayBuilder<N, T> {
162    /// Takes a fully initialized builder as an array. Panics if the builder is not
163    /// fully initialized.
164    pub const fn const_build_or_panic(self) -> [T; N] {
165        if self.start != 0 || self.limit != N {
166            let actual_len = self.limit - self.start;
167            const PREFIX: &[u8; 31] = b"Buffer too large. Size needed: ";
168            let len_bytes: [u8; PREFIX.len() + crate::helpers::MAX_USIZE_LEN_AS_DIGITS] =
169                crate::helpers::const_fmt_int(*PREFIX, actual_len);
170            let Ok(len_str) = core::str::from_utf8(&len_bytes) else {
171                unreachable!()
172            };
173            panic!("{}", len_str);
174        }
175        self.full_array
176    }
177
178    /// Prepends an element to the front of the builder, panicking if there is no room.
179    pub const fn const_push_front_or_panic(mut self, value: T) -> Self {
180        if self.start == 0 {
181            panic!("Buffer too small");
182        }
183        self.start -= 1;
184        self.full_array[self.start] = value;
185        self
186    }
187
188    /// Prepends multiple elements to the front of the builder, panicking if there is no room.
189    pub const fn const_extend_front_or_panic(mut self, other: ConstSlice<T>) -> Self {
190        if self.start < other.len() {
191            panic!("Buffer too small");
192        }
193        self.start -= other.len();
194        let mut i = self.start;
195        const_for_each!(other, byte, {
196            self.full_array[i] = *byte;
197            i += 1;
198        });
199        self
200    }
201}
202
203impl<const N: usize> ConstArrayBuilder<N, u8> {
204    /// Specialized function that performs `self[index] |= bits`
205    pub const fn const_bitor_assign(mut self, index: usize, bits: u8) -> Self {
206        self.full_array[self.start + index] |= bits;
207        self
208    }
209}
210
211impl<const N: usize, T: Copy> ConstArrayBuilder<N, T> {
212    /// Swaps the elements at positions `i` and `j`.
213    #[cfg(feature = "alloc")]
214    pub fn swap_or_panic(mut self, i: usize, j: usize) -> Self {
215        self.full_array.swap(self.start + i, self.start + j);
216        self
217    }
218}
219
220/// Evaluates a block over each element of a const slice. Takes three arguments:
221///
222/// 1. Expression that resolves to the [`ConstSlice`].
223/// 2. Token that will be assigned the value of the element.
224/// 3. Block to evaluate for each element.
225macro_rules! const_for_each {
226    ($safe_const_slice:expr, $item:tt, $inner:expr) => {{
227        let mut i = 0;
228        while i < $safe_const_slice.len() {
229            let $item = $safe_const_slice.get_or_panic(i);
230            $inner;
231            i += 1;
232        }
233    }};
234}
235
236pub(crate) use const_for_each;
237
238/// A data structure that holds up to K [`BranchMeta`] items.
239///
240/// Note: It should be possible to store the required data in the builder buffer itself,
241/// which would eliminate the need for this helper struct and the limit it imposes.
242pub(crate) struct ConstLengthsStack<const K: usize> {
243    data: [Option<BranchMeta>; K],
244    idx: usize,
245}
246
247impl<const K: usize> core::fmt::Debug for ConstLengthsStack<K> {
248    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
249        self.as_slice().fmt(f)
250    }
251}
252
253impl<const K: usize> ConstLengthsStack<K> {
254    /// Creates a new empty [`ConstLengthsStack`].
255    pub const fn new() -> Self {
256        Self {
257            data: [None; K],
258            idx: 0,
259        }
260    }
261
262    /// Returns whether the stack is empty.
263    pub const fn is_empty(&self) -> bool {
264        self.idx == 0
265    }
266
267    /// Adds a [`BranchMeta`] to the stack, panicking if there is no room.
268    #[must_use]
269    pub const fn push_or_panic(mut self, meta: BranchMeta) -> Self {
270        if self.idx >= K {
271            panic!(concat!(
272                "AsciiTrie Builder: Need more stack (max ",
273                stringify!(K),
274                ")"
275            ));
276        }
277        self.data[self.idx] = Some(meta);
278        self.idx += 1;
279        self
280    }
281
282    /// Returns a copy of the [`BranchMeta`] on the top of the stack, panicking if
283    /// the stack is empty.
284    pub const fn peek_or_panic(&self) -> BranchMeta {
285        if self.idx == 0 {
286            panic!("AsciiTrie Builder: Attempted to peek from an empty stack");
287        }
288        self.get_or_panic(0)
289    }
290
291    /// Returns a copy of the [`BranchMeta`] at the specified index.
292    const fn get_or_panic(&self, index: usize) -> BranchMeta {
293        if self.idx <= index {
294            panic!("AsciiTrie Builder: Attempted to get too deep in a stack");
295        }
296        match self.data[self.idx - index - 1] {
297            Some(x) => x,
298            None => unreachable!(),
299        }
300    }
301
302    /// Removes many [`BranchMeta`]s from the stack, returning them in a [`ConstArrayBuilder`].
303    pub const fn pop_many_or_panic(
304        mut self,
305        len: usize,
306    ) -> (Self, ConstArrayBuilder<256, BranchMeta>) {
307        debug_assert!(len <= 256);
308        let mut result = ConstArrayBuilder::new_empty([BranchMeta::default(); 256], 256);
309        let mut ix = 0;
310        loop {
311            if ix == len {
312                break;
313            }
314            let i = self.idx - ix - 1;
315            result = result.const_push_front_or_panic(match self.data[i] {
316                Some(x) => x,
317                None => panic!("Not enough items in the ConstLengthsStack"),
318            });
319            ix += 1;
320        }
321        self.idx -= len;
322        (self, result)
323    }
324
325    /// Non-const function that returns the initialized elements as a slice.
326    fn as_slice(&self) -> &[Option<BranchMeta>] {
327        &self.data[0..self.idx]
328    }
329}
330
331impl<const K: usize> ConstArrayBuilder<K, BranchMeta> {
332    /// Converts this builder-array of [`BranchMeta`] to one of the `ascii` fields.
333    pub const fn map_to_ascii_bytes(&self) -> ConstArrayBuilder<K, u8> {
334        let mut result = ConstArrayBuilder::new_empty([0; K], K);
335        let self_as_slice = self.as_const_slice();
336        const_for_each!(self_as_slice, value, {
337            result = result.const_push_front_or_panic(value.ascii);
338        });
339        result
340    }
341}
zerotrie/builder/konst/store.rs

zerotrie/builder/konst/
store.rs
