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

arctic/raw/key/unsized/
slice.rs
