rustc_index/
vec.rs

1use std::borrow::{Borrow, BorrowMut};
2use std::hash::Hash;
3use std::marker::PhantomData;
4use std::ops::{Deref, DerefMut, RangeBounds};
5use std::{fmt, slice, vec};
6
7#[cfg(feature = "nightly")]
8use rustc_serialize::{Decodable, Decoder, Encodable, Encoder};
9
10use crate::{Idx, IndexSlice};
11
12/// An owned contiguous collection of `T`s, indexed by `I` rather than by `usize`.
13///
14/// ## Why use this instead of a `Vec`?
15///
16/// An `IndexVec` allows element access only via a specific associated index type, meaning that
17/// trying to use the wrong index type (possibly accessing an invalid element) will fail at
18/// compile time.
19///
20/// It also documents what the index is indexing: in a `HashMap<usize, Something>` it's not
21/// immediately clear what the `usize` means, while a `HashMap<FieldIdx, Something>` makes it obvious.
22///
23/// ```compile_fail
24/// use rustc_index::{Idx, IndexVec};
25///
26/// fn f<I1: Idx, I2: Idx>(vec1: IndexVec<I1, u8>, idx1: I1, idx2: I2) {
27///   &vec1[idx1]; // Ok
28///   &vec1[idx2]; // Compile error!
29/// }
30/// ```
31///
32/// While it's possible to use `u32` or `usize` directly for `I`,
33/// you almost certainly want to use a [`newtype_index!`]-generated type instead.
34///
35/// This allows to index the IndexVec with the new index type.
36///
37/// [`newtype_index!`]: ../macro.newtype_index.html
38#[derive(Clone, PartialEq, Eq, Hash)]
39#[repr(transparent)]
40pub struct IndexVec<I: Idx, T> {
41    pub raw: Vec<T>,
42    _marker: PhantomData<fn(&I)>,
43}
44
45impl<I: Idx, T> IndexVec<I, T> {
46    /// Constructs a new, empty `IndexVec<I, T>`.
47    #[inline]
48    pub const fn new() -> Self {
49        IndexVec::from_raw(Vec::new())
50    }
51
52    /// Constructs a new `IndexVec<I, T>` from a `Vec<T>`.
53    #[inline]
54    pub const fn from_raw(raw: Vec<T>) -> Self {
55        IndexVec { raw, _marker: PhantomData }
56    }
57
58    #[inline]
59    pub fn with_capacity(capacity: usize) -> Self {
60        IndexVec::from_raw(Vec::with_capacity(capacity))
61    }
62
63    /// Creates a new vector with a copy of `elem` for each index in `universe`.
64    ///
65    /// Thus `IndexVec::from_elem(elem, &universe)` is equivalent to
66    /// `IndexVec::<I, _>::from_elem_n(elem, universe.len())`. That can help
67    /// type inference as it ensures that the resulting vector uses the same
68    /// index type as `universe`, rather than something potentially surprising.
69    ///
70    /// For example, if you want to store data for each local in a MIR body,
71    /// using `let mut uses = IndexVec::from_elem(vec![], &body.local_decls);`
72    /// ensures that `uses` is an `IndexVec<Local, _>`, and thus can give
73    /// better error messages later if one accidentally mismatches indices.
74    #[inline]
75    pub fn from_elem<S>(elem: T, universe: &IndexSlice<I, S>) -> Self
76    where
77        T: Clone,
78    {
79        IndexVec::from_raw(vec![elem; universe.len()])
80    }
81
82    /// Creates a new IndexVec with n copies of the `elem`.
83    #[inline]
84    pub fn from_elem_n(elem: T, n: usize) -> Self
85    where
86        T: Clone,
87    {
88        IndexVec::from_raw(vec![elem; n])
89    }
90
91    /// Create an `IndexVec` with `n` elements, where the value of each
92    /// element is the result of `func(i)`. (The underlying vector will
93    /// be allocated only once, with a capacity of at least `n`.)
94    #[inline]
95    pub fn from_fn_n(func: impl FnMut(I) -> T, n: usize) -> Self {
96        // Allow the optimizer to elide the bounds checking when creating each index.
97        let _ = I::new(n);
98        IndexVec::from_raw((0..n).map(I::new).map(func).collect())
99    }
100
101    #[inline]
102    pub fn as_slice(&self) -> &IndexSlice<I, T> {
103        IndexSlice::from_raw(&self.raw)
104    }
105
106    #[inline]
107    pub fn as_mut_slice(&mut self) -> &mut IndexSlice<I, T> {
108        IndexSlice::from_raw_mut(&mut self.raw)
109    }
110
111    /// Pushes an element to the array returning the index where it was pushed to.
112    #[inline]
113    pub fn push(&mut self, d: T) -> I {
114        let idx = self.next_index();
115        self.raw.push(d);
116        idx
117    }
118
119    #[inline]
120    pub fn pop(&mut self) -> Option<T> {
121        self.raw.pop()
122    }
123
124    #[inline]
125    pub fn into_iter(self) -> vec::IntoIter<T> {
126        self.raw.into_iter()
127    }
128
129    #[inline]
130    pub fn into_iter_enumerated(
131        self,
132    ) -> impl DoubleEndedIterator<Item = (I, T)> + ExactSizeIterator {
133        // Allow the optimizer to elide the bounds checking when creating each index.
134        let _ = I::new(self.len());
135        self.raw.into_iter().enumerate().map(|(n, t)| (I::new(n), t))
136    }
137
138    #[inline]
139    pub fn drain<R: RangeBounds<usize>>(&mut self, range: R) -> impl Iterator<Item = T> {
140        self.raw.drain(range)
141    }
142
143    #[inline]
144    pub fn drain_enumerated<R: RangeBounds<usize>>(
145        &mut self,
146        range: R,
147    ) -> impl Iterator<Item = (I, T)> {
148        let begin = match range.start_bound() {
149            std::ops::Bound::Included(i) => *i,
150            std::ops::Bound::Excluded(i) => i.checked_add(1).unwrap(),
151            std::ops::Bound::Unbounded => 0,
152        };
153        self.raw.drain(range).enumerate().map(move |(n, t)| (I::new(begin + n), t))
154    }
155
156    #[inline]
157    pub fn shrink_to_fit(&mut self) {
158        self.raw.shrink_to_fit()
159    }
160
161    #[inline]
162    pub fn truncate(&mut self, a: usize) {
163        self.raw.truncate(a)
164    }
165
166    /// Grows the index vector so that it contains an entry for
167    /// `elem`; if that is already true, then has no
168    /// effect. Otherwise, inserts new values as needed by invoking
169    /// `fill_value`.
170    ///
171    /// Returns a reference to the `elem` entry.
172    #[inline]
173    pub fn ensure_contains_elem(&mut self, elem: I, fill_value: impl FnMut() -> T) -> &mut T {
174        let min_new_len = elem.index() + 1;
175        if self.len() < min_new_len {
176            self.raw.resize_with(min_new_len, fill_value);
177        }
178
179        &mut self[elem]
180    }
181
182    #[inline]
183    pub fn resize(&mut self, new_len: usize, value: T)
184    where
185        T: Clone,
186    {
187        self.raw.resize(new_len, value)
188    }
189
190    #[inline]
191    pub fn resize_to_elem(&mut self, elem: I, fill_value: impl FnMut() -> T) {
192        let min_new_len = elem.index() + 1;
193        self.raw.resize_with(min_new_len, fill_value);
194    }
195
196    #[inline]
197    pub fn append(&mut self, other: &mut Self) {
198        self.raw.append(&mut other.raw);
199    }
200}
201
202/// `IndexVec` is often used as a map, so it provides some map-like APIs.
203impl<I: Idx, T> IndexVec<I, Option<T>> {
204    #[inline]
205    pub fn insert(&mut self, index: I, value: T) -> Option<T> {
206        self.ensure_contains_elem(index, || None).replace(value)
207    }
208
209    #[inline]
210    pub fn get_or_insert_with(&mut self, index: I, value: impl FnOnce() -> T) -> &mut T {
211        self.ensure_contains_elem(index, || None).get_or_insert_with(value)
212    }
213
214    #[inline]
215    pub fn remove(&mut self, index: I) -> Option<T> {
216        self.get_mut(index)?.take()
217    }
218
219    #[inline]
220    pub fn contains(&self, index: I) -> bool {
221        self.get(index).and_then(Option::as_ref).is_some()
222    }
223}
224
225impl<I: Idx, T: fmt::Debug> fmt::Debug for IndexVec<I, T> {
226    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
227        fmt::Debug::fmt(&self.raw, fmt)
228    }
229}
230
231impl<I: Idx, T> Deref for IndexVec<I, T> {
232    type Target = IndexSlice<I, T>;
233
234    #[inline]
235    fn deref(&self) -> &Self::Target {
236        self.as_slice()
237    }
238}
239
240impl<I: Idx, T> DerefMut for IndexVec<I, T> {
241    #[inline]
242    fn deref_mut(&mut self) -> &mut Self::Target {
243        self.as_mut_slice()
244    }
245}
246
247impl<I: Idx, T> Borrow<IndexSlice<I, T>> for IndexVec<I, T> {
248    fn borrow(&self) -> &IndexSlice<I, T> {
249        self
250    }
251}
252
253impl<I: Idx, T> BorrowMut<IndexSlice<I, T>> for IndexVec<I, T> {
254    fn borrow_mut(&mut self) -> &mut IndexSlice<I, T> {
255        self
256    }
257}
258
259impl<I: Idx, T> Extend<T> for IndexVec<I, T> {
260    #[inline]
261    fn extend<J: IntoIterator<Item = T>>(&mut self, iter: J) {
262        self.raw.extend(iter);
263    }
264
265    #[inline]
266    #[cfg(feature = "nightly")]
267    fn extend_one(&mut self, item: T) {
268        self.raw.push(item);
269    }
270
271    #[inline]
272    #[cfg(feature = "nightly")]
273    fn extend_reserve(&mut self, additional: usize) {
274        self.raw.reserve(additional);
275    }
276}
277
278impl<I: Idx, T> FromIterator<T> for IndexVec<I, T> {
279    #[inline]
280    fn from_iter<J>(iter: J) -> Self
281    where
282        J: IntoIterator<Item = T>,
283    {
284        IndexVec::from_raw(Vec::from_iter(iter))
285    }
286}
287
288impl<I: Idx, T> IntoIterator for IndexVec<I, T> {
289    type Item = T;
290    type IntoIter = vec::IntoIter<T>;
291
292    #[inline]
293    fn into_iter(self) -> vec::IntoIter<T> {
294        self.raw.into_iter()
295    }
296}
297
298impl<'a, I: Idx, T> IntoIterator for &'a IndexVec<I, T> {
299    type Item = &'a T;
300    type IntoIter = slice::Iter<'a, T>;
301
302    #[inline]
303    fn into_iter(self) -> slice::Iter<'a, T> {
304        self.iter()
305    }
306}
307
308impl<'a, I: Idx, T> IntoIterator for &'a mut IndexVec<I, T> {
309    type Item = &'a mut T;
310    type IntoIter = slice::IterMut<'a, T>;
311
312    #[inline]
313    fn into_iter(self) -> slice::IterMut<'a, T> {
314        self.iter_mut()
315    }
316}
317
318impl<I: Idx, T> Default for IndexVec<I, T> {
319    #[inline]
320    fn default() -> Self {
321        IndexVec::new()
322    }
323}
324
325impl<I: Idx, T, const N: usize> From<[T; N]> for IndexVec<I, T> {
326    #[inline]
327    fn from(array: [T; N]) -> Self {
328        IndexVec::from_raw(array.into())
329    }
330}
331
332#[cfg(feature = "nightly")]
333impl<S: Encoder, I: Idx, T: Encodable<S>> Encodable<S> for IndexVec<I, T> {
334    fn encode(&self, s: &mut S) {
335        Encodable::encode(&self.raw, s);
336    }
337}
338
339#[cfg(feature = "nightly")]
340impl<D: Decoder, I: Idx, T: Decodable<D>> Decodable<D> for IndexVec<I, T> {
341    fn decode(d: &mut D) -> Self {
342        IndexVec::from_raw(Vec::<T>::decode(d))
343    }
344}
345
346// Whether `IndexVec` is `Send` depends only on the data,
347// not the phantom data.
348unsafe impl<I: Idx, T> Send for IndexVec<I, T> where T: Send {}
349
350#[cfg(test)]
351mod tests;
rustc_index/vec.rs

rustc_index/
vec.rs
