]> git.lizzy.rs Git - rust.git/blob - src/librustc_data_structures/indexed_vec.rs
Auto merge of #45359 - arielb1:escaping-borrow, r=eddyb
[rust.git] / src / librustc_data_structures / indexed_vec.rs
1 // Copyright 2016 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
4 //
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
10
11 use std::collections::range::RangeArgument;
12 use std::fmt::Debug;
13 use std::iter::{self, FromIterator};
14 use std::slice;
15 use std::marker::PhantomData;
16 use std::ops::{Index, IndexMut, Range};
17 use std::fmt;
18 use std::vec;
19 use std::u32;
20
21 use rustc_serialize as serialize;
22
23 /// Represents some newtyped `usize` wrapper.
24 ///
25 /// (purpose: avoid mixing indexes for different bitvector domains.)
26 pub trait Idx: Copy + 'static + Eq + Debug {
27     fn new(idx: usize) -> Self;
28     fn index(self) -> usize;
29 }
30
31 impl Idx for usize {
32     fn new(idx: usize) -> Self { idx }
33     fn index(self) -> usize { self }
34 }
35
36 impl Idx for u32 {
37     fn new(idx: usize) -> Self { assert!(idx <= u32::MAX as usize); idx as u32 }
38     fn index(self) -> usize { self as usize }
39 }
40
41 #[macro_export]
42 macro_rules! newtype_index {
43     // ---- public rules ----
44
45     // Use default constants
46     ($name:ident) => (
47         newtype_index!(
48             @type[$name]
49             @max[::std::u32::MAX]
50             @debug_name[unsafe {::std::intrinsics::type_name::<$name>() }]);
51     );
52
53     // Define any constants
54     ($name:ident { $($tokens:tt)+ }) => (
55         newtype_index!(
56             @type[$name]
57             @max[::std::u32::MAX]
58             @debug_name[unsafe {::std::intrinsics::type_name::<$name>() }]
59             $($tokens)+);
60     );
61
62     // ---- private rules ----
63
64     // Base case, user-defined constants (if any) have already been defined
65     (@type[$type:ident] @max[$max:expr] @debug_name[$debug_name:expr]) => (
66         #[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord,
67             RustcEncodable, RustcDecodable)]
68         pub struct $type(pub u32);
69
70         impl Idx for $type {
71             fn new(value: usize) -> Self {
72                 assert!(value < ($max) as usize);
73                 $type(value as u32)
74             }
75             fn index(self) -> usize {
76                 self.0 as usize
77             }
78         }
79
80         impl ::std::fmt::Debug for $type {
81             fn fmt(&self, fmt: &mut ::std::fmt::Formatter) -> ::std::fmt::Result {
82                 write!(fmt, "{}{}", $debug_name, self.0)
83             }
84         }
85     );
86
87     // Rewrite final without comma to one that includes comma
88     (@type[$type:ident] @max[$max:expr] @debug_name[$debug_name:expr]
89             $name:ident = $constant:expr) => (
90         newtype_index!(@type[$type] @max[$max] @debug_name[$debug_name] $name = $constant,);
91     );
92
93     // Rewrite final const without comma to one that includes comma
94     (@type[$type:ident] @max[$_max:expr] @debug_name[$debug_name:expr]
95             const $name:ident = $constant:expr) => (
96         newtype_index!(@type[$type] @max[$max] @debug_name[$debug_name] const $name = $constant,);
97     );
98
99     // Replace existing default for max
100     (@type[$type:ident] @max[$_max:expr] @debug_name[$debug_name:expr]
101             MAX = $max:expr, $($tokens:tt)*) => (
102         newtype_index!(@type[$type] @max[$max] @debug_name[$debug_name] $($tokens)*);
103     );
104
105     // Replace existing default for debug_name
106     (@type[$type:ident] @max[$max:expr] @debug_name[$_debug_name:expr]
107             DEBUG_NAME = $debug_name:expr, $($tokens:tt)*) => (
108         newtype_index!(@type[$type] @max[$max] @debug_name[$debug_name] $($tokens)*);
109     );
110
111     // Assign a user-defined constant (as final param)
112     (@type[$type:ident] @max[$max:expr] @debug_name[$debug_name:expr]
113             const $name:ident = $constant:expr, $($tokens:tt)*) => (
114         pub const $name: $type = $type($constant);
115         newtype_index!(@type[$type] @max[$max] @debug_name[$debug_name] $($tokens)*);
116     );
117 }
118
119 #[derive(Clone, PartialEq, Eq)]
120 pub struct IndexVec<I: Idx, T> {
121     pub raw: Vec<T>,
122     _marker: PhantomData<Fn(&I)>
123 }
124
125 impl<I: Idx, T: serialize::Encodable> serialize::Encodable for IndexVec<I, T> {
126     fn encode<S: serialize::Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
127         serialize::Encodable::encode(&self.raw, s)
128     }
129 }
130
131 impl<I: Idx, T: serialize::Decodable> serialize::Decodable for IndexVec<I, T> {
132     fn decode<D: serialize::Decoder>(d: &mut D) -> Result<Self, D::Error> {
133         serialize::Decodable::decode(d).map(|v| {
134             IndexVec { raw: v, _marker: PhantomData }
135         })
136     }
137 }
138
139 impl<I: Idx, T: fmt::Debug> fmt::Debug for IndexVec<I, T> {
140     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
141         fmt::Debug::fmt(&self.raw, fmt)
142     }
143 }
144
145 pub type Enumerated<I, J> = iter::Map<iter::Enumerate<J>, IntoIdx<I>>;
146
147 impl<I: Idx, T> IndexVec<I, T> {
148     #[inline]
149     pub fn new() -> Self {
150         IndexVec { raw: Vec::new(), _marker: PhantomData }
151     }
152
153     #[inline]
154     pub fn with_capacity(capacity: usize) -> Self {
155         IndexVec { raw: Vec::with_capacity(capacity), _marker: PhantomData }
156     }
157
158     #[inline]
159     pub fn from_elem<S>(elem: T, universe: &IndexVec<I, S>) -> Self
160         where T: Clone
161     {
162         IndexVec { raw: vec![elem; universe.len()], _marker: PhantomData }
163     }
164
165     #[inline]
166     pub fn from_elem_n(elem: T, n: usize) -> Self
167         where T: Clone
168     {
169         IndexVec { raw: vec![elem; n], _marker: PhantomData }
170     }
171
172     #[inline]
173     pub fn push(&mut self, d: T) -> I {
174         let idx = I::new(self.len());
175         self.raw.push(d);
176         idx
177     }
178
179     #[inline]
180     pub fn len(&self) -> usize {
181         self.raw.len()
182     }
183
184     #[inline]
185     pub fn is_empty(&self) -> bool {
186         self.raw.is_empty()
187     }
188
189     #[inline]
190     pub fn into_iter(self) -> vec::IntoIter<T> {
191         self.raw.into_iter()
192     }
193
194     #[inline]
195     pub fn into_iter_enumerated(self) -> Enumerated<I, vec::IntoIter<T>>
196     {
197         self.raw.into_iter().enumerate().map(IntoIdx { _marker: PhantomData })
198     }
199
200     #[inline]
201     pub fn iter(&self) -> slice::Iter<T> {
202         self.raw.iter()
203     }
204
205     #[inline]
206     pub fn iter_enumerated(&self) -> Enumerated<I, slice::Iter<T>>
207     {
208         self.raw.iter().enumerate().map(IntoIdx { _marker: PhantomData })
209     }
210
211     #[inline]
212     pub fn indices(&self) -> iter::Map<Range<usize>, IntoIdx<I>> {
213         (0..self.len()).map(IntoIdx { _marker: PhantomData })
214     }
215
216     #[inline]
217     pub fn iter_mut(&mut self) -> slice::IterMut<T> {
218         self.raw.iter_mut()
219     }
220
221     #[inline]
222     pub fn iter_enumerated_mut(&mut self) -> Enumerated<I, slice::IterMut<T>>
223     {
224         self.raw.iter_mut().enumerate().map(IntoIdx { _marker: PhantomData })
225     }
226
227     #[inline]
228     pub fn drain<'a, R: RangeArgument<usize>>(
229         &'a mut self, range: R) -> impl Iterator<Item=T> + 'a {
230         self.raw.drain(range)
231     }
232
233     #[inline]
234     pub fn drain_enumerated<'a, R: RangeArgument<usize>>(
235         &'a mut self, range: R) -> impl Iterator<Item=(I, T)> + 'a {
236         self.raw.drain(range).enumerate().map(IntoIdx { _marker: PhantomData })
237     }
238
239     #[inline]
240     pub fn last(&self) -> Option<I> {
241         self.len().checked_sub(1).map(I::new)
242     }
243
244     #[inline]
245     pub fn shrink_to_fit(&mut self) {
246         self.raw.shrink_to_fit()
247     }
248
249     #[inline]
250     pub fn swap(&mut self, a: usize, b: usize) {
251         self.raw.swap(a, b)
252     }
253
254     #[inline]
255     pub fn truncate(&mut self, a: usize) {
256         self.raw.truncate(a)
257     }
258
259     #[inline]
260     pub fn get(&self, index: I) -> Option<&T> {
261         self.raw.get(index.index())
262     }
263
264     #[inline]
265     pub fn get_mut(&mut self, index: I) -> Option<&mut T> {
266         self.raw.get_mut(index.index())
267     }
268 }
269
270 impl<I: Idx, T: Clone> IndexVec<I, T> {
271     #[inline]
272     pub fn resize(&mut self, new_len: usize, value: T) {
273         self.raw.resize(new_len, value)
274     }
275 }
276
277 impl<I: Idx, T: Ord> IndexVec<I, T> {
278     #[inline]
279     pub fn binary_search(&self, value: &T) -> Result<I, I> {
280         match self.raw.binary_search(value) {
281             Ok(i) => Ok(Idx::new(i)),
282             Err(i) => Err(Idx::new(i)),
283         }
284     }
285 }
286
287 impl<I: Idx, T> Index<I> for IndexVec<I, T> {
288     type Output = T;
289
290     #[inline]
291     fn index(&self, index: I) -> &T {
292         &self.raw[index.index()]
293     }
294 }
295
296 impl<I: Idx, T> IndexMut<I> for IndexVec<I, T> {
297     #[inline]
298     fn index_mut(&mut self, index: I) -> &mut T {
299         &mut self.raw[index.index()]
300     }
301 }
302
303 impl<I: Idx, T> Default for IndexVec<I, T> {
304     #[inline]
305     fn default() -> Self {
306         Self::new()
307     }
308 }
309
310 impl<I: Idx, T> Extend<T> for IndexVec<I, T> {
311     #[inline]
312     fn extend<J: IntoIterator<Item = T>>(&mut self, iter: J) {
313         self.raw.extend(iter);
314     }
315 }
316
317 impl<I: Idx, T> FromIterator<T> for IndexVec<I, T> {
318     #[inline]
319     fn from_iter<J>(iter: J) -> Self where J: IntoIterator<Item=T> {
320         IndexVec { raw: FromIterator::from_iter(iter), _marker: PhantomData }
321     }
322 }
323
324 impl<I: Idx, T> IntoIterator for IndexVec<I, T> {
325     type Item = T;
326     type IntoIter = vec::IntoIter<T>;
327
328     #[inline]
329     fn into_iter(self) -> vec::IntoIter<T> {
330         self.raw.into_iter()
331     }
332
333 }
334
335 impl<'a, I: Idx, T> IntoIterator for &'a IndexVec<I, T> {
336     type Item = &'a T;
337     type IntoIter = slice::Iter<'a, T>;
338
339     #[inline]
340     fn into_iter(self) -> slice::Iter<'a, T> {
341         self.raw.iter()
342     }
343 }
344
345 impl<'a, I: Idx, T> IntoIterator for &'a mut IndexVec<I, T> {
346     type Item = &'a mut T;
347     type IntoIter = slice::IterMut<'a, T>;
348
349     #[inline]
350     fn into_iter(self) -> slice::IterMut<'a, T> {
351         self.raw.iter_mut()
352     }
353 }
354
355 pub struct IntoIdx<I: Idx> { _marker: PhantomData<fn(&I)> }
356 impl<I: Idx, T> FnOnce<((usize, T),)> for IntoIdx<I> {
357     type Output = (I, T);
358
359     extern "rust-call" fn call_once(self, ((n, t),): ((usize, T),)) -> Self::Output {
360         (I::new(n), t)
361     }
362 }
363
364 impl<I: Idx, T> FnMut<((usize, T),)> for IntoIdx<I> {
365     extern "rust-call" fn call_mut(&mut self, ((n, t),): ((usize, T),)) -> Self::Output {
366         (I::new(n), t)
367     }
368 }
369
370 impl<I: Idx> FnOnce<(usize,)> for IntoIdx<I> {
371     type Output = I;
372
373     extern "rust-call" fn call_once(self, (n,): (usize,)) -> Self::Output {
374         I::new(n)
375     }
376 }
377
378 impl<I: Idx> FnMut<(usize,)> for IntoIdx<I> {
379     extern "rust-call" fn call_mut(&mut self, (n,): (usize,)) -> Self::Output {
380         I::new(n)
381     }
382 }