arctic/raw/key/unsized/
boxed_slice.rs

1//! Support for owned dynamically sized keys ([`Vec<u8>`], [`Box<[u8]>`][Box]).
2
3use core::borrow::Borrow;
4use core::fmt::Debug;
5use core::marker::PhantomData;
6use core::ops::Deref;
7use std::ffi::CString;
8
9#[cfg(feature = "proptest")]
10use proptest::prelude::Strategy;
11use ribbit::u6;
12
13use crate::Key;
14#[cfg(feature = "proptest")]
15use crate::key::Invariant;
16use crate::key::Terminated;
17use crate::raw::edge;
18use crate::raw::edge::Len as _;
19use crate::raw::edge::Meta as _;
20use crate::raw::key;
21use crate::raw::key::Byte;
22use crate::raw::key::Len as _;
23use crate::raw::key::Read as _;
24use crate::raw::key::r#unsized;
25use crate::raw::key::r#unsized::Terminate;
26use crate::raw::key::r#unsized::slice::Slice;
27
28/// An owned, dynamically sized key that satisfies an [`Invariant`][crate::key::unsized::Invariant].
29#[repr(transparent)]
30#[derive(Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
31pub struct BoxedSlice<I, R: ?Sized = [u8]> {
32    invariant: PhantomData<I>,
33    raw: Box<R>,
34}
35
36impl<I, R: ?Sized> Clone for BoxedSlice<I, R>
37where
38    Box<R>: Clone,
39{
40    #[inline]
41    fn clone(&self) -> Self {
42        Self {
43            invariant: PhantomData,
44            raw: self.raw.clone(),
45        }
46    }
47}
48
49impl<I, R: ?Sized> Default for BoxedSlice<I, R>
50where
51    Box<R>: Default,
52{
53    fn default() -> Self {
54        Self {
55            invariant: PhantomData,
56            raw: Default::default(),
57        }
58    }
59}
60
61impl<I, R> BoxedSlice<I, R>
62where
63    I: r#unsized::Invariant,
64    R: ?Sized + r#unsized::slice::Raw,
65{
66    /// Construct a boxed slice after validating.
67    ///
68    /// Returns `Ok` if the input boxed slice satisfies the invariant.
69    #[inline]
70    pub fn new(key: impl Into<Box<R>>) -> Result<Self, (Box<R>, I::Error)> {
71        let key = key.into();
72        match Slice::<I, R>::new(&key) {
73            Ok(_) => Ok(unsafe { Self::new_unchecked(key) }),
74            Err(error) => Err((key, error)),
75        }
76    }
77}
78
79impl<I, R: ?Sized> BoxedSlice<I, R> {
80    /// Construct a boxed slice without validating.
81    ///
82    /// # SAFETY
83    ///
84    /// Caller must guarantee that `raw` satisfies the invariant, i.e.,
85    /// `I::validate(key)` would return `Ok(())`.
86    #[inline]
87    pub const unsafe fn new_unchecked(key: Box<R>) -> Self {
88        Self {
89            invariant: PhantomData,
90            raw: key,
91        }
92    }
93
94    /// Get a borrowed [`Slice`] that preserves the invariant.
95    #[inline]
96    pub const fn as_slice(&self) -> &Slice<I, R> {
97        unsafe { Slice::new_unchecked(&self.raw) }
98    }
99
100    /// Get an owned boxed slice.
101    #[inline]
102    pub fn into_boxed_slice(self) -> Box<R> {
103        self.raw
104    }
105}
106
107impl<I, R: ?Sized> Deref for BoxedSlice<I, R> {
108    type Target = Slice<I, R>;
109    #[inline]
110    fn deref(&self) -> &Self::Target {
111        self.as_slice()
112    }
113}
114
115impl<I, R: ?Sized> Borrow<Slice<I, R>> for BoxedSlice<I, R> {
116    #[inline]
117    fn borrow(&self) -> &Slice<I, R> {
118        self.as_slice()
119    }
120}
121
122impl<I, R: ?Sized> AsRef<Slice<I, R>> for BoxedSlice<I, R> {
123    #[inline]
124    fn as_ref(&self) -> &Slice<I, R> {
125        self.as_slice()
126    }
127}
128
129impl From<CString> for BoxedSlice<Terminated<0>, [u8]> {
130    fn from(string: CString) -> Self {
131        // SAFETY: `CString` is null terminated
132        unsafe { Self::new_unchecked(string.into_bytes_with_nul().into_boxed_slice()) }
133    }
134}
135
136#[cfg(feature = "proptest")]
137impl<I, R> proptest::arbitrary::Arbitrary for BoxedSlice<I, R>
138where
139    I: Invariant,
140    R: ?Sized + r#unsized::slice::Raw + core::fmt::Debug,
141    Box<R>: proptest::arbitrary::Arbitrary,
142{
143    type Parameters = <Box<R> as proptest::arbitrary::Arbitrary>::Parameters;
144    type Strategy = proptest::strategy::BoxedStrategy<Self>;
145
146    fn arbitrary_with(args: Self::Parameters) -> Self::Strategy {
147        <Box<R>>::arbitrary_with(args)
148            .prop_filter_map("Invariant violated", |boxed_slice| {
149                Self::new(boxed_slice).ok()
150            })
151            .boxed()
152    }
153}
154
155#[cfg(feature = "rand")]
156impl rand::distr::Distribution<BoxedSlice<r#unsized::NonNull, str>>
157    for rand::distr::StandardUniform
158{
159    fn sample<R: rand::Rng + ?Sized>(&self, rng: &mut R) -> BoxedSlice<r#unsized::NonNull, str> {
160        let uniform = rand::distr::Uniform::new_inclusive(1 as char, char::MAX).unwrap();
161        let string = rand::distr::SampleString::sample_string(&uniform, rng, 32);
162        unsafe { BoxedSlice::new_unchecked(string.into_boxed_str()) }
163    }
164}
165
166impl<I, R> Key for BoxedSlice<I, R>
167where
168    I: r#unsized::Invariant,
169    R: ?Sized + r#unsized::slice::Raw,
170{
171    type Read<'k> = Reader<'k, I::Terminate>;
172    type Write = Writer;
173    type Borrowed = Slice<I, R>;
174    type Insert<'k> = &'k Slice<I, R>;
175    type Edge = edge::Le;
176    type Len = Byte;
177
178    #[inline]
179    fn as_insert(&self) -> Self::Insert<'_> {
180        self.as_slice()
181    }
182
183    #[inline]
184    fn insert_as_read<'k>(insert: Self::Insert<'k>) -> Self::Read<'k>
185    where
186        Self: 'k,
187    {
188        Reader::from(insert)
189    }
190
191    #[inline]
192    fn insert_to_key<'k>(insert: Self::Insert<'k>) -> Self
193    where
194        Self: 'k,
195    {
196        insert.to_owned()
197    }
198
199    #[inline]
200    unsafe fn write_as_insert<'k>(writer: &'k Self::Write) -> Self::Insert<'k>
201    where
202        Self: 'k,
203    {
204        unsafe { writer.as_slice_unchecked() }
205    }
206}
207
208impl<'k, I, R> From<&'k Slice<I, R>> for Reader<'k, I::Terminate>
209where
210    I: r#unsized::Invariant,
211    R: ?Sized + r#unsized::slice::Raw,
212{
213    #[inline]
214    fn from(slice: &'k Slice<I, R>) -> Self {
215        Self {
216            slice: slice.as_raw().as_ref(),
217            terminate: I::Terminate::TRUE,
218        }
219    }
220}
221
222impl<'k, T: Terminate> From<&'k [u8]> for Reader<'k, T> {
223    #[inline]
224    fn from(prefix: &'k [u8]) -> Self {
225        Reader::new_prefix(prefix)
226    }
227}
228
229impl<'k, T: Terminate> From<&'k str> for Reader<'k, T> {
230    #[inline]
231    fn from(prefix: &'k str) -> Self {
232        Self::from(prefix.as_bytes())
233    }
234}
235
236impl<'k, const N: usize, T: Terminate> From<&'k [u8; N]> for Reader<'k, T> {
237    #[inline]
238    fn from(prefix: &'k [u8; N]) -> Self {
239        Self::from(prefix.as_slice())
240    }
241}
242
243#[derive(Copy, Clone, Debug, PartialEq, Eq)]
244pub struct Reader<'k, T> {
245    pub(crate) slice: &'k [u8],
246    pub(super) terminate: T,
247}
248
249impl<'k, T: Default> Reader<'k, T> {
250    #[inline]
251    pub(crate) fn new_prefix(prefix: &'k [u8]) -> Self {
252        Self {
253            slice: prefix,
254            terminate: T::default(),
255        }
256    }
257}
258
259#[expect(private_bounds)]
260impl<'k, T: Terminate> Reader<'k, T> {
261    #[inline]
262    pub(crate) fn get_byte(&self, index: usize) -> Option<u8> {
263        if let Some(byte) = self.slice.get(index) {
264            return Some(*byte);
265        }
266
267        (self.terminate.get() && index == self.slice.len()).then_some(0)
268    }
269}
270
271impl<T: Default> Default for Reader<'_, T> {
272    #[inline]
273    fn default() -> Self {
274        Self::new_prefix(&[])
275    }
276}
277
278impl<T: Terminate> key::Read for Reader<'_, T> {
279    const LEN: Option<Self::Len> = None;
280    type Edge = edge::Le;
281    type Len = Byte;
282
283    #[inline]
284    fn len(&self) -> Self::Len {
285        Byte(self.slice.len() + self.terminate.get() as usize)
286    }
287
288    #[inline]
289    fn get_edge(
290        &self,
291        len: <ribbit::Packed<Self::Edge> as edge::Meta>::Len,
292    ) -> ribbit::Packed<Self::Edge> {
293        let len = u6::new((self.len().bits()).min(len.bits()) as u8);
294        edge::Le::new(r#unsized::read_u64(self.slice), len)
295    }
296
297    #[inline]
298    fn get_byte(&self, index: u6) -> Option<u8> {
299        self.get_byte(index.bytes())
300    }
301
302    #[inline]
303    fn match_exact(
304        &self,
305        edge: <Self::Edge as ribbit::Pack>::Packed,
306    ) -> Option<<ribbit::Packed<Self::Edge> as edge::Meta>::Len> {
307        // Avoid bit <-> byte conversion
308        let len_edge = edge.len();
309        let len_match = (edge.raw() ^ r#unsized::read_u64(self.slice)).trailing_zeros() as u8;
310        (len_match >= len_edge.value()).then_some(len_edge)
311    }
312
313    #[inline]
314    fn match_prefix(&self, edge: <Self::Edge as ribbit::Pack>::Packed) -> Self::Len {
315        Byte(((edge.raw() ^ r#unsized::read_u64(self.slice)).trailing_zeros() as usize) >> 3)
316    }
317
318    #[inline]
319    fn prefix(self, end: Self::Len) -> Self {
320        validate!(end <= self.len());
321        let end = end.bytes();
322
323        Self {
324            slice: self.slice.get(..end).unwrap_or(self.slice),
325            terminate: T::new(self.terminate.get() && (end > self.slice.len())),
326        }
327    }
328
329    #[inline]
330    fn suffix(self, start: Self::Len) -> Self {
331        validate!(start <= self.len());
332        let start = start.bytes();
333
334        Self {
335            // NOTE: slice key implementation requires us to preserve the
336            // `self.slice` pointer, even if the slice is empty.
337            slice: self
338                .slice
339                .get(start..)
340                .unwrap_or(&self.slice[self.slice.len()..]),
341            terminate: T::new(self.terminate.get() && (start <= self.slice.len())),
342        }
343    }
344
345    #[inline]
346    fn common_prefix(self, other: Self) -> Self {
347        let index = r#unsized::common_prefix(self.slice, other.slice);
348
349        Self {
350            slice: &self.slice[..index],
351            terminate: T::new(
352                self.terminate.get()
353                    && other.terminate.get()
354                    && index == self.slice.len()
355                    && index == other.slice.len(),
356            ),
357        }
358    }
359}
360
361#[doc(hidden)]
362#[repr(transparent)]
363#[derive(Debug, Default)]
364pub struct Writer(Vec<u8>);
365
366impl Writer {
367    unsafe fn as_slice_unchecked<I: r#unsized::Invariant, R: ?Sized>(&self) -> &Slice<I, R> {
368        let raw = I::Terminate::trim(self.0.as_slice());
369        unsafe { Slice::<I, R>::new_unchecked(core::mem::transmute_copy::<&[u8], &R>(&raw)) }
370    }
371}
372
373impl<'k, T: Terminate> key::Write<Reader<'k, T>> for Writer {
374    type Len = Byte;
375
376    #[inline]
377    fn new(prefix: Reader<'k, T>, key: ribbit::Packed<edge::Le>) -> (Self, Self::Len) {
378        let len = prefix.len() + key.len().into();
379        let mut buffer = Vec::new();
380        buffer.extend_from_slice(prefix.slice);
381        if prefix.terminate.get() {
382            buffer.push(u8::MIN);
383            validate_eq!(key.len().bits(), 0);
384        } else {
385            buffer.extend(key);
386        }
387        (Writer(buffer), len)
388    }
389
390    #[inline]
391    fn replace(&mut self, start: Self::Len, node: u8, edge: ribbit::Packed<edge::Le>) -> Self::Len {
392        validate!(start.0 <= self.0.len());
393        self.0.truncate(start.0);
394        self.0.push(node);
395        self.0.extend(edge);
396        Byte(self.0.len())
397    }
398}
arctic/raw/key/unsized/boxed_slice.rs

arctic/raw/key/unsized/
boxed_slice.rs
