arctic/raw/key/unsized/
slice.rs

1//! Support for borrowed dynamically sized `&[u8]` keys.
2
3use core::ffi::CStr;
4use core::fmt::Debug;
5use core::marker::PhantomData;
6
7use ribbit::u13;
8
9use crate::key::Terminated;
10use crate::raw::edge;
11use crate::raw::edge::Len as _;
12use crate::raw::key;
13use crate::raw::key::Byte;
14use crate::raw::key::Len as _;
15use crate::raw::key::Read as _;
16use crate::raw::key::r#unsized;
17use crate::raw::key::r#unsized::Terminate;
18use crate::raw::key::r#unsized::boxed_slice::BoxedSlice;
19
20/// # Safety
21///
22/// Implementer must guarantee that `Raw` is unsized
23/// and repr(transparent) with `[u8]`.
24pub unsafe trait Raw: 'static + AsRef<[u8]> + Debug {
25    #[expect(clippy::wrong_self_convention)]
26    fn into_boxed(&self) -> Box<Self>;
27}
28unsafe impl Raw for [u8] {
29    #[inline]
30    fn into_boxed(&self) -> Box<Self> {
31        Box::from(self)
32    }
33}
34unsafe impl Raw for str {
35    #[inline]
36    fn into_boxed(&self) -> Box<Self> {
37        Box::from(self)
38    }
39}
40
41/// A borrowed, dynamically sized key that satisfies an [`Invariant`][crate::key::unsized::Invariant].
42#[repr(transparent)]
43#[derive(Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
44pub struct Slice<I, R: ?Sized = [u8]> {
45    invariant: PhantomData<I>,
46    raw: R,
47}
48
49impl<I, R> Slice<I, R>
50where
51    I: r#unsized::Invariant,
52    R: ?Sized + Raw,
53{
54    /// Construct a slice after validating.
55    ///
56    /// Returns `Ok` if the input `key` satisfies the invariant.
57    pub fn new(key: &R) -> Result<&Self, I::Error> {
58        I::validate(key.as_ref())?;
59        // Invariants checked above
60        Ok(unsafe { Self::new_unchecked(key) })
61    }
62}
63
64impl<I, R: ?Sized> Slice<I, R> {
65    /// # Safety
66    ///
67    /// Caller must ensure `key` upholds invariants, i.e., `I::validate(key)` would return `Ok`.
68    #[inline]
69    pub const unsafe fn new_unchecked(key: &R) -> &Self {
70        unsafe { core::mem::transmute::<&R, &Self>(key) }
71    }
72
73    /// Get a reference to the underlying buffer.
74    #[doc(hidden)]
75    #[inline]
76    pub const fn as_raw(&self) -> &R {
77        &self.raw
78    }
79}
80
81impl<I> Slice<I, str> {
82    /// Get a reference to the underlying `str`.
83    #[inline]
84    pub const fn as_str(&self) -> &str {
85        self.as_raw()
86    }
87}
88
89impl<I> Slice<I, [u8]> {
90    /// Get a reference to the underlying `[u8]`.
91    #[inline]
92    pub const fn as_bytes(&self) -> &[u8] {
93        self.as_raw()
94    }
95}
96
97impl<I, R: ?Sized> AsRef<R> for Slice<I, R> {
98    #[inline]
99    fn as_ref(&self) -> &R {
100        self.as_raw()
101    }
102}
103
104impl<I, R> ToOwned for Slice<I, R>
105where
106    R: ?Sized + Raw,
107{
108    type Owned = BoxedSlice<I, R>;
109    fn to_owned(&self) -> Self::Owned {
110        unsafe { BoxedSlice::new_unchecked(self.as_raw().into_boxed()) }
111    }
112}
113
114impl<'a> From<&'a CStr> for &'a Slice<Terminated<0>, [u8]> {
115    fn from(str: &'a CStr) -> Self {
116        // SAFETY: `CStr` is null terminated
117        unsafe { Slice::new_unchecked(str.to_bytes_with_nul()) }
118    }
119}
120
121impl<'a, I, R> crate::Key for &'a Slice<I, R>
122where
123    I: r#unsized::Invariant,
124    R: ?Sized + Raw,
125{
126    type Borrowed = Slice<I, R>;
127
128    type Insert<'k>
129        = &'a Slice<I, R>
130    where
131        Self: 'k;
132
133    type Read<'k> = Reader<'k, I::Terminate>;
134    type Write = Writer<I>;
135    type Edge = edge::Slice<I::Terminate>;
136    type Len = Byte;
137
138    fn as_insert(&self) -> Self::Insert<'_> {
139        self
140    }
141
142    fn insert_as_read<'k>(insert: Self::Insert<'k>) -> Self::Read<'k>
143    where
144        Self: 'k,
145    {
146        Self::Read::from(insert)
147    }
148
149    fn insert_to_key<'k>(insert: Self::Insert<'k>) -> Self
150    where
151        Self: 'k,
152    {
153        insert
154    }
155
156    unsafe fn write_as_insert<'k>(writer: &'k Self::Write) -> Self::Insert<'k>
157    where
158        Self: 'k,
159    {
160        unsafe { writer.as_slice_unchecked() }
161    }
162}
163
164#[derive(Copy, Clone, Debug, Default, PartialEq, Eq)]
165pub struct Reader<'k, T>(pub(crate) r#unsized::boxed_slice::Reader<'k, T>);
166
167impl<'k, I, R> From<&'k Slice<I, R>> for Reader<'k, I::Terminate>
168where
169    I: r#unsized::Invariant,
170    R: ?Sized + Raw,
171{
172    #[inline]
173    fn from(key: &'k Slice<I, R>) -> Self {
174        Self(r#unsized::boxed_slice::Reader::from(key))
175    }
176}
177
178impl<'k, T: Terminate> From<&'k [u8]> for Reader<'k, T> {
179    #[inline]
180    fn from(prefix: &'k [u8]) -> Self {
181        Self(r#unsized::boxed_slice::Reader::from(prefix))
182    }
183}
184
185impl<'k, T: Terminate> From<&'k str> for Reader<'k, T> {
186    #[inline]
187    fn from(prefix: &'k str) -> Self {
188        Self::from(prefix.as_bytes())
189    }
190}
191
192impl<'k, const N: usize, T: Terminate> From<&'k [u8; N]> for Reader<'k, T> {
193    #[inline]
194    fn from(prefix: &'k [u8; N]) -> Self {
195        Self::from(prefix.as_slice())
196    }
197}
198
199impl<T: Terminate> key::Read for Reader<'_, T> {
200    const LEN: Option<Byte> = None;
201
202    type Edge = edge::Slice<T>;
203    type Len = Byte;
204
205    fn len(&self) -> Self::Len {
206        self.0.len()
207    }
208
209    fn get_edge(
210        &self,
211        len: <ribbit::Packed<Self::Edge> as edge::Meta>::Len,
212    ) -> ribbit::Packed<Self::Edge> {
213        let min = len.bytes().min(self.0.len);
214        edge::Slice::new(self.0.as_non_null(), min)
215            .with_terminate(T::new(self.0.terminate.get() && len.bytes() > self.0.len))
216    }
217
218    fn get_byte(&self, index: u13) -> Option<u8> {
219        self.0.get_byte(index.bytes())
220    }
221
222    fn match_prefix(&self, meta: ribbit::Packed<edge::Slice<T>>) -> Self::Len {
223        let other = unsafe { meta.as_slice() };
224
225        let index = r#unsized::common_prefix(self.0.as_slice(), other);
226        let terminate = self.0.terminate.get()
227            && index == self.0.len
228            && index == other.len()
229            && meta.terminate().get();
230
231        Byte(index + terminate as usize)
232    }
233
234    #[inline]
235    fn prefix(self, end: Byte) -> Self {
236        Self(self.0.prefix(end))
237    }
238
239    #[inline]
240    fn suffix(self, start: Byte) -> Self {
241        Self(self.0.suffix(start))
242    }
243
244    #[inline]
245    fn common_prefix(self, other: Self) -> Self {
246        Self(self.0.common_prefix(other.0))
247    }
248}
249
250#[doc(hidden)]
251#[derive(Clone, Default, Debug)]
252pub struct Writer<I: r#unsized::Invariant> {
253    last: ribbit::Packed<edge::Slice<I::Terminate>>,
254    len: Byte,
255}
256
257impl<I: r#unsized::Invariant> Writer<I> {
258    unsafe fn as_slice_unchecked<'a, R: ?Sized>(&self) -> &'a Slice<I, R> {
259        let len_total = self.len.bytes();
260        // NOTE: calling inherent method `len` here to ignore implicit terminator byte
261        let len_suffix = self.last.len().bytes();
262
263        validate!(len_total >= len_suffix);
264
265        let raw = I::Terminate::trim(unsafe {
266            core::slice::from_raw_parts(
267                // NOTE: requires provenance of original slice
268                self.last.as_ptr().byte_sub(len_total - len_suffix),
269                len_total,
270            )
271        });
272        unsafe { Slice::<I, R>::new_unchecked(core::mem::transmute_copy::<&[u8], &R>(&raw)) }
273    }
274}
275
276impl<I: r#unsized::Invariant> key::Write<Reader<'_, I::Terminate>> for Writer<I> {
277    type Len = Byte;
278
279    fn new(
280        prefix: Reader<'_, I::Terminate>,
281        key: ribbit::Packed<edge::Slice<I::Terminate>>,
282    ) -> (Self, Self::Len) {
283        let len = prefix.len() + key.len().into();
284        (Writer { last: key, len }, len)
285    }
286
287    fn replace(
288        &mut self,
289        start: Self::Len,
290        _: u8,
291        edge: ribbit::Packed<edge::Slice<I::Terminate>>,
292    ) -> Self::Len {
293        validate!(start <= self.len);
294        self.len = start + Byte::BYTE + edge.len().into();
295        self.last = edge;
296        self.len
297    }
298}
arctic/raw/key/unsized/slice.rs

arctic/raw/key/unsized/
slice.rs
