ra_ap_rustc_index/
slice.rs

1use std::fmt;
2use std::marker::PhantomData;
3use std::ops::{Index, IndexMut};
4use std::slice::{self, SliceIndex};
5
6use crate::{Idx, IndexVec, IntoSliceIdx};
7
8/// A view into contiguous `T`s, indexed by `I` rather than by `usize`.
9///
10/// One common pattern you'll see is code that uses [`IndexVec::from_elem`]
11/// to create the storage needed for a particular "universe" (aka the set of all
12/// the possible keys that need an associated value) then passes that working
13/// area as `&mut IndexSlice<I, T>` to clarify that nothing will be added nor
14/// removed during processing (and, as a bonus, to chase fewer pointers).
15#[derive(PartialEq, Eq, Hash)]
16#[repr(transparent)]
17pub struct IndexSlice<I: Idx, T> {
18    _marker: PhantomData<fn(&I)>,
19    pub raw: [T],
20}
21
22impl<I: Idx, T> IndexSlice<I, T> {
23    #[inline]
24    pub const fn empty<'a>() -> &'a Self {
25        Self::from_raw(&[])
26    }
27
28    #[inline]
29    pub const fn from_raw(raw: &[T]) -> &Self {
30        let ptr: *const [T] = raw;
31        // SAFETY: `IndexSlice` is `repr(transparent)` over a normal slice
32        unsafe { &*(ptr as *const Self) }
33    }
34
35    #[inline]
36    pub fn from_raw_mut(raw: &mut [T]) -> &mut Self {
37        let ptr: *mut [T] = raw;
38        // SAFETY: `IndexSlice` is `repr(transparent)` over a normal slice
39        unsafe { &mut *(ptr as *mut Self) }
40    }
41
42    #[inline]
43    pub const fn len(&self) -> usize {
44        self.raw.len()
45    }
46
47    #[inline]
48    pub const fn is_empty(&self) -> bool {
49        self.raw.is_empty()
50    }
51
52    /// Gives the next index that will be assigned when `push` is called.
53    ///
54    /// Manual bounds checks can be done using `idx < slice.next_index()`
55    /// (as opposed to `idx.index() < slice.len()`).
56    #[inline]
57    pub fn next_index(&self) -> I {
58        I::new(self.len())
59    }
60
61    #[inline]
62    pub fn iter(&self) -> slice::Iter<'_, T> {
63        self.raw.iter()
64    }
65
66    #[inline]
67    pub fn iter_enumerated(&self) -> impl DoubleEndedIterator<Item = (I, &T)> + ExactSizeIterator {
68        self.raw.iter().enumerate().map(|(n, t)| (I::new(n), t))
69    }
70
71    #[inline]
72    pub fn indices(
73        &self,
74    ) -> impl DoubleEndedIterator<Item = I> + ExactSizeIterator + Clone + 'static {
75        (0..self.len()).map(|n| I::new(n))
76    }
77
78    #[inline]
79    pub fn iter_mut(&mut self) -> slice::IterMut<'_, T> {
80        self.raw.iter_mut()
81    }
82
83    #[inline]
84    pub fn iter_enumerated_mut(
85        &mut self,
86    ) -> impl DoubleEndedIterator<Item = (I, &mut T)> + ExactSizeIterator {
87        self.raw.iter_mut().enumerate().map(|(n, t)| (I::new(n), t))
88    }
89
90    #[inline]
91    pub fn last_index(&self) -> Option<I> {
92        self.len().checked_sub(1).map(I::new)
93    }
94
95    #[inline]
96    pub fn swap(&mut self, a: I, b: I) {
97        self.raw.swap(a.index(), b.index())
98    }
99
100    #[inline]
101    pub fn get<R: IntoSliceIdx<I, [T]>>(
102        &self,
103        index: R,
104    ) -> Option<&<R::Output as SliceIndex<[T]>>::Output> {
105        self.raw.get(index.into_slice_idx())
106    }
107
108    #[inline]
109    pub fn get_mut<R: IntoSliceIdx<I, [T]>>(
110        &mut self,
111        index: R,
112    ) -> Option<&mut <R::Output as SliceIndex<[T]>>::Output> {
113        self.raw.get_mut(index.into_slice_idx())
114    }
115
116    /// Returns mutable references to two distinct elements, `a` and `b`.
117    ///
118    /// Panics if `a == b`.
119    #[inline]
120    pub fn pick2_mut(&mut self, a: I, b: I) -> (&mut T, &mut T) {
121        let (ai, bi) = (a.index(), b.index());
122        assert!(ai != bi);
123
124        if ai < bi {
125            let (c1, c2) = self.raw.split_at_mut(bi);
126            (&mut c1[ai], &mut c2[0])
127        } else {
128            let (c2, c1) = self.pick2_mut(b, a);
129            (c1, c2)
130        }
131    }
132
133    /// Returns mutable references to three distinct elements.
134    ///
135    /// Panics if the elements are not distinct.
136    #[inline]
137    pub fn pick3_mut(&mut self, a: I, b: I, c: I) -> (&mut T, &mut T, &mut T) {
138        let (ai, bi, ci) = (a.index(), b.index(), c.index());
139        assert!(ai != bi && bi != ci && ci != ai);
140        let len = self.raw.len();
141        assert!(ai < len && bi < len && ci < len);
142        let ptr = self.raw.as_mut_ptr();
143        unsafe { (&mut *ptr.add(ai), &mut *ptr.add(bi), &mut *ptr.add(ci)) }
144    }
145
146    #[inline]
147    pub fn binary_search(&self, value: &T) -> Result<I, I>
148    where
149        T: Ord,
150    {
151        match self.raw.binary_search(value) {
152            Ok(i) => Ok(Idx::new(i)),
153            Err(i) => Err(Idx::new(i)),
154        }
155    }
156}
157
158impl<I: Idx, J: Idx> IndexSlice<I, J> {
159    /// Invert a bijective mapping, i.e. `invert(map)[y] = x` if `map[x] = y`,
160    /// assuming the values in `self` are a permutation of `0..self.len()`.
161    ///
162    /// This is used to go between `memory_index` (source field order to memory order)
163    /// and `inverse_memory_index` (memory order to source field order).
164    /// See also `FieldsShape::Arbitrary::memory_index` for more details.
165    // FIXME(eddyb) build a better abstraction for permutations, if possible.
166    pub fn invert_bijective_mapping(&self) -> IndexVec<J, I> {
167        debug_assert_eq!(
168            self.iter().map(|x| x.index() as u128).sum::<u128>(),
169            (0..self.len() as u128).sum::<u128>(),
170            "The values aren't 0..N in input {self:?}",
171        );
172
173        let mut inverse = IndexVec::from_elem_n(Idx::new(0), self.len());
174        for (i1, &i2) in self.iter_enumerated() {
175            inverse[i2] = i1;
176        }
177
178        debug_assert_eq!(
179            inverse.iter().map(|x| x.index() as u128).sum::<u128>(),
180            (0..inverse.len() as u128).sum::<u128>(),
181            "The values aren't 0..N in result {self:?}",
182        );
183
184        inverse
185    }
186}
187
188impl<I: Idx, T: fmt::Debug> fmt::Debug for IndexSlice<I, T> {
189    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
190        fmt::Debug::fmt(&self.raw, fmt)
191    }
192}
193
194impl<I: Idx, T, R: IntoSliceIdx<I, [T]>> Index<R> for IndexSlice<I, T> {
195    type Output = <R::Output as SliceIndex<[T]>>::Output;
196
197    #[inline]
198    fn index(&self, index: R) -> &Self::Output {
199        &self.raw[index.into_slice_idx()]
200    }
201}
202
203impl<I: Idx, T, R: IntoSliceIdx<I, [T]>> IndexMut<R> for IndexSlice<I, T> {
204    #[inline]
205    fn index_mut(&mut self, index: R) -> &mut Self::Output {
206        &mut self.raw[index.into_slice_idx()]
207    }
208}
209
210impl<'a, I: Idx, T> IntoIterator for &'a IndexSlice<I, T> {
211    type Item = &'a T;
212    type IntoIter = slice::Iter<'a, T>;
213
214    #[inline]
215    fn into_iter(self) -> slice::Iter<'a, T> {
216        self.raw.iter()
217    }
218}
219
220impl<'a, I: Idx, T> IntoIterator for &'a mut IndexSlice<I, T> {
221    type Item = &'a mut T;
222    type IntoIter = slice::IterMut<'a, T>;
223
224    #[inline]
225    fn into_iter(self) -> slice::IterMut<'a, T> {
226        self.raw.iter_mut()
227    }
228}
229
230impl<I: Idx, T: Clone> ToOwned for IndexSlice<I, T> {
231    type Owned = IndexVec<I, T>;
232
233    fn to_owned(&self) -> IndexVec<I, T> {
234        IndexVec::from_raw(self.raw.to_owned())
235    }
236
237    fn clone_into(&self, target: &mut IndexVec<I, T>) {
238        self.raw.clone_into(&mut target.raw)
239    }
240}
241
242impl<I: Idx, T> Default for &IndexSlice<I, T> {
243    #[inline]
244    fn default() -> Self {
245        IndexSlice::from_raw(Default::default())
246    }
247}
248
249impl<I: Idx, T> Default for &mut IndexSlice<I, T> {
250    #[inline]
251    fn default() -> Self {
252        IndexSlice::from_raw_mut(Default::default())
253    }
254}
255
256// Whether `IndexSlice` is `Send` depends only on the data,
257// not the phantom data.
258unsafe impl<I: Idx, T> Send for IndexSlice<I, T> where T: Send {}
ra_ap_rustc_index/slice.rs

ra_ap_rustc_index/
slice.rs
