indexing/
traits.rs

1use {
2    crate::{
3        proof::{NonEmpty, Unknown},
4        Container, Index, IndexError,
5    },
6    core::{convert::TryFrom, fmt, hash::Hash, ops},
7};
8
9/// Unsigned integers able to be used as a trusted index.
10pub unsafe trait Idx: Copy + Ord + Hash
11where
12    Self: fmt::Debug,
13{
14    //noinspection RsSelfConvention
15    fn as_usize(self) -> usize;
16    fn from_usize(i: usize) -> Option<Self>;
17    fn zero() -> Self;
18    fn add(self, increment: usize) -> Self;
19    fn sub(self, decrement: usize) -> Self;
20}
21
22#[allow(non_snake_case)]
23macro_rules! impl_Idx {
24    ($($ty:ty),*$(,)?) => {
25        $(unsafe impl Idx for $ty {
26            fn as_usize(self) -> usize { self as usize } // we need u32 support, 64 KiB isn't enough
27            fn from_usize(i: usize) -> Option<Self> { Self::try_from(i).ok() }
28            fn zero() -> Self { 0 }
29            fn add(self, increment: usize) -> Self {
30                // FUTURE: See if this is always sound in the face of wrapping arithmetic
31                Self::from_usize(increment).and_then(|i| self.checked_add(i)).expect("increment")
32            }
33            fn sub(self, decrement: usize) -> Self {
34                self - Self::from_usize(decrement).expect("increment")
35            }
36        })*
37    };
38}
39
40impl_Idx! {
41    u8,
42    u16,
43    u32,
44    usize,
45}
46
47/// Types that can back a trusted container: it can have
48/// indices and ranges that are trusted to be in bounds.
49///
50/// It must have a continuously addressable range.
51pub unsafe trait TrustedContainer {
52    type Item: ?Sized + TrustedItem<Self>;
53    type Slice: ?Sized;
54
55    /// The length of the container in base item units.
56    fn unit_len(&self) -> usize;
57
58    unsafe fn get_unchecked(&self, i: usize) -> &Self::Item;
59    unsafe fn slice_unchecked(&self, r: ops::Range<usize>) -> &Self::Slice;
60}
61
62/// An item within a trusted container.
63pub unsafe trait TrustedItem<Array: TrustedContainer<Item = Self> + ?Sized> {
64    type Unit;
65
66    /// Vet an index for being on item boundaries.
67    ///
68    /// The index for the end of the container should pass.
69    /// This function does not imply a nonempty proof.
70    fn vet<'id, I: Idx>(
71        idx: I,
72        container: &Container<'id, Array>,
73    ) -> Result<Index<'id, I, Unknown>, IndexError>;
74
75    /// Increment an index to the next item, potentially leaving the container.
76    fn after<'id, I: Idx>(
77        this: Index<'id, I, NonEmpty>,
78        container: &Container<'id, Array>,
79    ) -> Index<'id, I, Unknown>;
80
81    /// Advance an index to the next item, if a next item exists.
82    fn advance<'id, I: Idx>(
83        this: Index<'id, I, NonEmpty>,
84        container: &Container<'id, Array>,
85    ) -> Option<Index<'id, I, NonEmpty>>;
86}
87
88unsafe impl<T: TrustedContainer + ?Sized> TrustedContainer for &T {
89    type Item = T::Item;
90    type Slice = T::Slice;
91
92    fn unit_len(&self) -> usize {
93        T::unit_len(self)
94    }
95
96    unsafe fn get_unchecked(&self, i: usize) -> &Self::Item {
97        T::get_unchecked(self, i)
98    }
99
100    unsafe fn slice_unchecked(&self, r: ops::Range<usize>) -> &Self::Slice {
101        T::slice_unchecked(self, r)
102    }
103}
104
105unsafe impl<T> TrustedContainer for [T] {
106    type Item = T;
107    type Slice = [T];
108
109    fn unit_len(&self) -> usize {
110        self.len()
111    }
112
113    unsafe fn get_unchecked(&self, i: usize) -> &Self::Item {
114        debug_assert!(i < self.len());
115        self.get_unchecked(i)
116    }
117
118    unsafe fn slice_unchecked(&self, r: ops::Range<usize>) -> &Self::Slice {
119        debug_assert!(r.start <= self.len());
120        debug_assert!(r.end <= self.len());
121        debug_assert!(r.start <= r.end);
122        self.get_unchecked(r)
123    }
124}
125
126unsafe impl<T: TrustedItem<Array> + ?Sized, Array: TrustedContainer<Item = T> + ?Sized>
127    TrustedItem<&Array> for T
128{
129    type Unit = T::Unit;
130
131    fn vet<'id, I: Idx>(
132        idx: I,
133        container: &Container<'id, &Array>,
134    ) -> Result<Index<'id, I, Unknown>, IndexError> {
135        T::vet(idx, container.project())
136    }
137
138    fn after<'id, I: Idx>(
139        this: Index<'id, I, NonEmpty>,
140        container: &Container<'id, &Array>,
141    ) -> Index<'id, I, Unknown> {
142        T::after(this, container.project())
143    }
144
145    fn advance<'id, I: Idx>(
146        this: Index<'id, I, NonEmpty>,
147        container: &Container<'id, &Array>,
148    ) -> Option<Index<'id, I, NonEmpty>> {
149        T::advance(this, container.project())
150    }
151}
152
153unsafe impl<T> TrustedItem<[T]> for T {
154    type Unit = T;
155
156    fn vet<'id, I: Idx>(
157        idx: I,
158        container: &Container<'id, [T]>,
159    ) -> Result<Index<'id, I, Unknown>, IndexError> {
160        if idx.as_usize() <= container.unit_len() {
161            Ok(unsafe { Index::new(idx) })
162        } else {
163            Err(IndexError::OutOfBounds)
164        }
165    }
166
167    fn after<'id, I: Idx>(
168        this: Index<'id, I, NonEmpty>,
169        _: &Container<'id, [T]>,
170    ) -> Index<'id, I, Unknown> {
171        unsafe { Index::new(this.untrusted().add(1)) }
172    }
173
174    fn advance<'id, I: Idx>(
175        this: Index<'id, I, NonEmpty>,
176        container: &Container<'id, [T]>,
177    ) -> Option<Index<'id, I, NonEmpty>> {
178        container.vet(Self::after(this, container).untrusted()).ok()
179    }
180}
181
182#[cfg(feature = "std")]
183mod std_impls {
184    use super::*;
185    use std::{boxed::Box, vec::Vec};
186
187    #[cfg_attr(feature = "doc", doc(cfg(feature = "std")))]
188    unsafe impl<T: TrustedContainer + ?Sized> TrustedContainer for Box<T> {
189        type Item = T::Item;
190        type Slice = T::Slice;
191
192        fn unit_len(&self) -> usize {
193            T::unit_len(&self)
194        }
195
196        unsafe fn get_unchecked(&self, i: usize) -> &Self::Item {
197            T::get_unchecked(self, i)
198        }
199
200        unsafe fn slice_unchecked(&self, r: ops::Range<usize>) -> &Self::Slice {
201            T::slice_unchecked(self, r)
202        }
203    }
204
205    #[cfg_attr(feature = "doc", doc(cfg(feature = "std")))]
206    unsafe impl<T: TrustedItem<Array> + ?Sized, Array: TrustedContainer<Item = T> + ?Sized>
207        TrustedItem<Box<Array>> for T
208    {
209        type Unit = T::Unit;
210
211        fn vet<'id, I: Idx>(
212            idx: I,
213            container: &Container<'id, Box<Array>>,
214        ) -> Result<Index<'id, I, Unknown>, IndexError> {
215            T::vet(idx, container.project())
216        }
217
218        fn after<'id, I: Idx>(
219            this: Index<'id, I, NonEmpty>,
220            container: &Container<'id, Box<Array>>,
221        ) -> Index<'id, I, Unknown> {
222            T::after(this, container.project())
223        }
224
225        fn advance<'id, I: Idx>(
226            this: Index<'id, I, NonEmpty>,
227            container: &Container<'id, Box<Array>>,
228        ) -> Option<Index<'id, I, NonEmpty>> {
229            T::advance(this, container.project())
230        }
231    }
232
233    #[cfg_attr(feature = "doc", doc(cfg(feature = "std")))]
234    impl<'id, Array: TrustedContainer + ?Sized> Container<'id, Box<Array>> {
235        pub fn project(&self) -> &Container<'id, Array> {
236            unsafe { &*(&**self.untrusted() as *const Array as *const Container<'id, Array>) }
237        }
238    }
239
240    #[cfg_attr(feature = "doc", doc(cfg(feature = "std")))]
241    unsafe impl<T> TrustedContainer for Vec<T> {
242        type Item = T;
243        type Slice = [T];
244
245        fn unit_len(&self) -> usize {
246            self.len()
247        }
248
249        unsafe fn get_unchecked(&self, i: usize) -> &Self::Item {
250            <[T]>::get_unchecked(self, i)
251        }
252
253        unsafe fn slice_unchecked(&self, r: ops::Range<usize>) -> &Self::Slice {
254            <[T]>::slice_unchecked(self, r)
255        }
256    }
257
258    #[cfg_attr(feature = "doc", doc(cfg(feature = "std")))]
259    unsafe impl<T: TrustedItem<[T]>> TrustedItem<Vec<T>> for T {
260        type Unit = T::Unit;
261
262        fn vet<'id, I: Idx>(
263            idx: I,
264            container: &Container<'id, Vec<T>>,
265        ) -> Result<Index<'id, I, Unknown>, IndexError> {
266            T::vet(idx, container.project())
267        }
268
269        fn after<'id, I: Idx>(
270            this: Index<'id, I, NonEmpty>,
271            container: &Container<'id, Vec<T>>,
272        ) -> Index<'id, I, Unknown> {
273            T::after(this, container.project())
274        }
275
276        fn advance<'id, I: Idx>(
277            this: Index<'id, I, NonEmpty>,
278            container: &Container<'id, Vec<T>>,
279        ) -> Option<Index<'id, I, NonEmpty>> {
280            T::advance(this, container.project())
281        }
282    }
283
284    #[cfg_attr(feature = "doc", doc(cfg(feature = "std")))]
285    impl<'id, T> Container<'id, Vec<T>> {
286        pub fn project(&self) -> &Container<'id, [T]> {
287            unsafe { &*(&**self.untrusted() as *const [T] as *const Container<'id, [T]>) }
288        }
289    }
290}
indexing/traits.rs

indexing/
traits.rs
