indexing/
index.rs

1#[cfg(feature = "doc")]
2use crate::scope;
3use {
4    crate::{
5        container::Container,
6        proof::{Id, NonEmpty, ProofAdd, Unknown},
7        traits::{Idx, TrustedContainer},
8    },
9    core::{
10        cmp, fmt,
11        hash::{self, Hash},
12        marker::PhantomData,
13        ops,
14    },
15};
16
17/// A branded index.
18///
19/// `Index<'id>` only indexes the container instantiated with the exact same
20/// lifetime for the parameter `'id` created by the [`scope`] function.
21///
22/// The type parameter `Emptiness` determines if the index is followable.
23/// A `NonEmpty` index points to a valid element. An `Unknown` index is
24/// unknown, or it points to an edge index (one past the end).
25pub struct Index<'id, I: Idx = u32, Emptiness = NonEmpty> {
26    #[allow(unused)]
27    id: Id<'id>,
28    idx: I,
29    phantom: PhantomData<Emptiness>,
30}
31
32impl<'id, I: Idx> Index<'id, I, Unknown> {
33    pub(crate) unsafe fn new(idx: I) -> Self {
34        Index::new_any(idx)
35    }
36}
37
38impl<'id, I: Idx> Index<'id, I, NonEmpty> {
39    pub(crate) unsafe fn new_nonempty(idx: I) -> Self {
40        Index::new_any(idx)
41    }
42}
43
44impl<'id, I: Idx, Emptiness> Index<'id, I, Emptiness> {
45    pub(crate) unsafe fn new_any(idx: I) -> Self {
46        Index {
47            id: Id::default(),
48            idx,
49            phantom: PhantomData,
50        }
51    }
52}
53
54impl<'id, I: Idx, Emptiness> Index<'id, I, Emptiness> {
55    /// This index without the branding.
56    pub fn untrusted(&self) -> I {
57        self.idx
58    }
59
60    /// This index without the emptiness proof.
61    pub fn erased(&self) -> Index<'id, I, Unknown> {
62        unsafe { Index::new(self.idx) }
63    }
64}
65
66impl<'id, I: Idx> Index<'id, I, NonEmpty> {
67    #[doc(hidden)]
68    pub fn observe_proof(&self) {}
69}
70
71impl<'id, I: Idx, Emptiness> fmt::Debug for Index<'id, I, Emptiness> {
72    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
73        f.debug_tuple("Index<'id>").field(&self.idx).finish()
74    }
75}
76
77impl<'id, I: Idx, Emptiness> Copy for Index<'id, I, Emptiness> {}
78impl<'id, I: Idx, Emptiness> Clone for Index<'id, I, Emptiness> {
79    fn clone(&self) -> Self {
80        *self
81    }
82}
83
84impl<'id, I: Idx, Emptiness> Ord for Index<'id, I, Emptiness> {
85    fn cmp(&self, other: &Self) -> cmp::Ordering {
86        self.idx.cmp(&other.idx)
87    }
88}
89
90impl<'id, I: Idx, P, Q> PartialOrd<Index<'id, I, Q>> for Index<'id, I, P> {
91    fn partial_cmp(&self, other: &Index<'id, I, Q>) -> Option<cmp::Ordering> {
92        self.idx.partial_cmp(&other.idx)
93    }
94}
95
96impl<'id, I: Idx, Emptiness> Eq for Index<'id, I, Emptiness> {}
97impl<'id, I: Idx, P, Q> PartialEq<Index<'id, I, Q>> for Index<'id, I, P> {
98    fn eq(&self, other: &Index<'id, I, Q>) -> bool {
99        self.idx.eq(&other.idx)
100    }
101}
102
103impl<'id, I: Idx, Emptiness> Hash for Index<'id, I, Emptiness> {
104    fn hash<H: hash::Hasher>(&self, state: &mut H) {
105        self.idx.hash(state);
106    }
107}
108
109/// A branded range.
110///
111/// `Range<'id>` only indexes the container instantiated with the exact same
112/// lifetime for the parameter `'id` created by the [`scope`] function.
113///
114/// The range may carry a proof of non-emptiness (`Emptiness`),
115/// which enables further operations.
116pub struct Range<'id, I: Idx = u32, Emptiness = Unknown> {
117    start: Index<'id, I, Unknown>,
118    end: Index<'id, I, Unknown>,
119    phantom: PhantomData<Emptiness>,
120}
121
122impl<'id, I: Idx> Range<'id, I, Unknown> {
123    pub(crate) unsafe fn new(start: I, end: I) -> Self {
124        Range::new_any(start, end)
125    }
126}
127
128impl<'id, I: Idx> Range<'id, I, NonEmpty> {
129    pub(crate) unsafe fn new_nonempty(start: I, end: I) -> Self {
130        Range::new_any(start, end)
131    }
132}
133
134impl<'id, I: Idx, Emptiness> Range<'id, I, Emptiness> {
135    pub(crate) unsafe fn new_any(start: I, end: I) -> Self {
136        Range {
137            start: Index::new(start),
138            end: Index::new(end),
139            phantom: PhantomData,
140        }
141    }
142}
143
144impl<'id, I: Idx> Range<'id, I, Unknown> {
145    /// Construct a range from two trusted indices.
146    pub fn from<P, Q>(start: Index<'id, I, P>, end: Index<'id, I, Q>) -> Self {
147        unsafe { Range::new(start.untrusted(), end.untrusted()) }
148    }
149}
150
151impl<'id, I: Idx, Emptiness> Range<'id, I, Emptiness> {
152    /// This range without the branding.
153    pub fn untrusted(&self) -> ops::Range<I> {
154        self.start.idx..self.end.idx
155    }
156
157    /// This range without the emptiness proof.
158    pub fn erased(&self) -> Range<'id, I, Unknown> {
159        unsafe { Range::new(self.start.idx, self.end.idx) }
160    }
161
162    /// The length of the range.
163    pub fn len(&self) -> I {
164        if self.is_empty() {
165            I::zero()
166        } else {
167            self.end.idx.sub(self.start.idx.as_usize())
168        }
169    }
170
171    /// `true` if the range is empty.
172    pub fn is_empty(&self) -> bool {
173        self.start.idx >= self.end.idx
174    }
175
176    /// Try to create a proof that the range is nonempty.
177    pub fn nonempty(&self) -> Option<Range<'id, I, NonEmpty>> {
178        if self.is_empty() {
179            None
180        } else {
181            unsafe { Some(Range::new_nonempty(self.start.idx, self.end.idx)) }
182        }
183    }
184
185    /// The starting index. (Accessible if the range is `NonEmpty`.)
186    pub fn start(&self) -> Index<'id, I, Emptiness> {
187        unsafe { Index::new_any(self.start.idx) }
188    }
189
190    /// The ending index.
191    pub fn end(&self) -> Index<'id, I, Unknown> {
192        self.end
193    }
194
195    /// Split around the middle `index` if it is in this range.
196    pub fn split_at<E>(&self, index: Index<'id, I, E>) -> Option<(Range<'id, I>, Range<'id, I>)> {
197        if index >= self.start && index <= self.end {
198            unsafe {
199                Some((
200                    Range::new(self.start.idx, index.idx),
201                    Range::new(index.idx, self.end.idx),
202                ))
203            }
204        } else {
205            None
206        }
207    }
208
209    /// If the index is a valid absolute index within this range.
210    pub fn contains_in<Array: TrustedContainer>(
211        &self,
212        index: I,
213        container: &Container<'id, Array>,
214    ) -> Option<Index<'id, I, NonEmpty>> {
215        if index >= self.start().untrusted() && index < self.end().untrusted() {
216            container.vet(index).ok()
217        } else {
218            None
219        }
220    }
221
222    /// If the index is within this range. Provides a nonempty proof.
223    pub fn contains<P>(&self, index: Index<'id, I, P>) -> Option<Index<'id, I, NonEmpty>> {
224        if index >= self.start() && index < self.end() {
225            unsafe { Some(Index::new_nonempty(index.untrusted())) }
226        } else {
227            None
228        }
229    }
230
231    /// Join together two adjacent ranges.
232    /// (They must be exactly touching, non-overlapping, and in order.)
233    pub fn join<Q>(
234        &self,
235        other: Range<'id, I, Q>,
236    ) -> Option<Range<'id, I, <(Emptiness, Q) as ProofAdd>::Sum>>
237    where
238        (Emptiness, Q): ProofAdd,
239    {
240        if self.end == other.start {
241            unsafe { Some(Range::new_any(self.start.idx, other.end.idx)) }
242        } else {
243            None
244        }
245    }
246
247    /// Extend the range to cover all of `other`, including any space between.
248    pub fn join_cover<Q>(
249        &self,
250        other: Range<'id, I, Q>,
251    ) -> Range<'id, I, <(Emptiness, Q) as ProofAdd>::Sum>
252    where
253        (Emptiness, Q): ProofAdd,
254    {
255        let start = cmp::min(self.start, other.start);
256        let end = cmp::max(self.end, other.end);
257        unsafe { Range::new_any(start.idx, end.idx) }
258    }
259
260    /// Create two empty ranges, at the front and the back of this range.
261    pub fn frontiers(&self) -> (Range<'id, I, Unknown>, Range<'id, I, Unknown>) {
262        (
263            Range::from(self.start(), self.start()),
264            Range::from(self.end(), self.end()),
265        )
266    }
267}
268
269impl<'id, I: Idx> Range<'id, I, NonEmpty> {
270    #[doc(hidden)]
271    pub fn observe_proof(&self) {}
272
273    /// Increase the range's start, if the result is still a non-empty range.
274    ///
275    /// `true` if stepped successfully, `false` if the range would be empty.
276    pub fn advance_in<Array: TrustedContainer>(
277        &mut self,
278        container: &Container<'id, Array>,
279    ) -> bool {
280        if let Some(next) = container.advance(self.start()) {
281            if next < self.end() {
282                *self = unsafe { Range::new_nonempty(next.untrusted(), self.end().untrusted()) };
283                true
284            } else {
285                false
286            }
287        } else {
288            false
289        }
290    }
291}
292
293/// # Note
294///
295/// In order to use this impl, you'll likely need to erase the emptiness proof
296/// from the indices to create the range. This doesn't lose any `Range` proof.
297impl<'id, I: Idx, Emptiness> From<ops::Range<Index<'id, I, Emptiness>>> for Range<'id, I, Unknown> {
298    fn from(r: ops::Range<Index<'id, I, Emptiness>>) -> Self {
299        Range::from(r.start, r.end)
300    }
301}
302
303impl<'id, I: Idx, Emptiness> fmt::Debug for Range<'id, I, Emptiness> {
304    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
305        f.debug_tuple("Range<'id>")
306            .field(&self.start.idx)
307            .field(&self.end.idx)
308            .finish()
309    }
310}
311
312impl<'id, I: Idx, Emptiness> Copy for Range<'id, I, Emptiness> {}
313impl<'id, I: Idx, Emptiness> Clone for Range<'id, I, Emptiness> {
314    fn clone(&self) -> Self {
315        *self
316    }
317}
318
319impl<'id, I: Idx, Emptiness> Eq for Range<'id, I, Emptiness> {}
320impl<'id, I: Idx, P, Q> PartialEq<Range<'id, I, Q>> for Range<'id, I, P> {
321    fn eq(&self, other: &Range<'id, I, Q>) -> bool {
322        self.start.eq(&other.start) && self.end.eq(&other.end)
323    }
324}
325
326impl<'id, I: Idx, Emptiness> Hash for Range<'id, I, Emptiness> {
327    fn hash<H: hash::Hasher>(&self, state: &mut H) {
328        self.start.hash(state);
329        self.end.hash(state);
330    }
331}
332
333/// The error returned when failing to construct an arbitrary index.
334#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash)]
335pub enum IndexError {
336    /// The provided raw index was out of bounds of the container.
337    OutOfBounds,
338    /// The provided raw index was in bounds but not on an item border.
339    Invalid,
340}
indexing/index.rs

indexing/
index.rs
