compiler/rustc_index/src/vec.rs

   1 #[cfg(feature = "rustc_serialize")]
   2 use rustc_serialize::{Decodable, Decoder, Encodable, Encoder};
   3
   4 use std::fmt;
   5 use std::fmt::Debug;
   6 use std::hash::Hash;
   7 use std::marker::PhantomData;
   8 use std::ops::{Index, IndexMut, RangeBounds};
   9 use std::slice;
  10 use std::vec;
  11
  12 /// Represents some newtyped `usize` wrapper.
  13 ///
  14 /// Purpose: avoid mixing indexes for different bitvector domains.
  15 pub trait Idx: Copy + 'static + Eq + PartialEq + Debug + Hash {
  16     fn new(idx: usize) -> Self;
  17
  18     fn index(self) -> usize;
  19
  20     #[inline]
  21     fn increment_by(&mut self, amount: usize) {
  22         *self = self.plus(amount);
  23     }
  24
  25     #[inline]
  26     fn plus(self, amount: usize) -> Self {
  27         Self::new(self.index() + amount)
  28     }
  29 }
  30
  31 impl Idx for usize {
  32     #[inline]
  33     fn new(idx: usize) -> Self {
  34         idx
  35     }
  36     #[inline]
  37     fn index(self) -> usize {
  38         self
  39     }
  40 }
  41
  42 impl Idx for u32 {
  43     #[inline]
  44     fn new(idx: usize) -> Self {
  45         assert!(idx <= u32::MAX as usize);
  46         idx as u32
  47     }
  48     #[inline]
  49     fn index(self) -> usize {
  50         self as usize
  51     }
  52 }
  53
  54 #[derive(Clone, PartialEq, Eq, Hash)]
  55 pub struct IndexVec<I: Idx, T> {
  56     pub raw: Vec<T>,
  57     _marker: PhantomData<fn(&I)>,
  58 }
  59
  60 // Whether `IndexVec` is `Send` depends only on the data,
  61 // not the phantom data.
  62 unsafe impl<I: Idx, T> Send for IndexVec<I, T> where T: Send {}
  63
  64 #[cfg(feature = "rustc_serialize")]
  65 impl<S: Encoder, I: Idx, T: Encodable<S>> Encodable<S> for IndexVec<I, T> {
  66     fn encode(&self, s: &mut S) {
  67         Encodable::encode(&self.raw, s);
  68     }
  69 }
  70
  71 #[cfg(feature = "rustc_serialize")]
  72 impl<D: Decoder, I: Idx, T: Decodable<D>> Decodable<D> for IndexVec<I, T> {
  73     fn decode(d: &mut D) -> Self {
  74         IndexVec { raw: Decodable::decode(d), _marker: PhantomData }
  75     }
  76 }
  77
  78 impl<I: Idx, T: fmt::Debug> fmt::Debug for IndexVec<I, T> {
  79     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
  80         fmt::Debug::fmt(&self.raw, fmt)
  81     }
  82 }
  83
  84 impl<I: Idx, T> IndexVec<I, T> {
  85     #[inline]
  86     pub fn new() -> Self {
  87         IndexVec { raw: Vec::new(), _marker: PhantomData }
  88     }
  89
  90     #[inline]
  91     pub fn from_raw(raw: Vec<T>) -> Self {
  92         IndexVec { raw, _marker: PhantomData }
  93     }
  94
  95     #[inline]
  96     pub fn with_capacity(capacity: usize) -> Self {
  97         IndexVec { raw: Vec::with_capacity(capacity), _marker: PhantomData }
  98     }
  99
 100     #[inline]
 101     pub fn from_elem<S>(elem: T, universe: &IndexVec<I, S>) -> Self
 102     where
 103         T: Clone,
 104     {
 105         IndexVec { raw: vec![elem; universe.len()], _marker: PhantomData }
 106     }
 107
 108     #[inline]
 109     pub fn from_elem_n(elem: T, n: usize) -> Self
 110     where
 111         T: Clone,
 112     {
 113         IndexVec { raw: vec![elem; n], _marker: PhantomData }
 114     }
 115
 116     /// Create an `IndexVec` with `n` elements, where the value of each
 117     /// element is the result of `func(i)`. (The underlying vector will
 118     /// be allocated only once, with a capacity of at least `n`.)
 119     #[inline]
 120     pub fn from_fn_n(func: impl FnMut(I) -> T, n: usize) -> Self {
 121         let indices = (0..n).map(I::new);
 122         Self::from_raw(indices.map(func).collect())
 123     }
 124
 125     #[inline]
 126     pub fn push(&mut self, d: T) -> I {
 127         let idx = I::new(self.len());
 128         self.raw.push(d);
 129         idx
 130     }
 131
 132     #[inline]
 133     pub fn pop(&mut self) -> Option<T> {
 134         self.raw.pop()
 135     }
 136
 137     #[inline]
 138     pub fn len(&self) -> usize {
 139         self.raw.len()
 140     }
 141
 142     /// Gives the next index that will be assigned when `push` is
 143     /// called.
 144     #[inline]
 145     pub fn next_index(&self) -> I {
 146         I::new(self.len())
 147     }
 148
 149     #[inline]
 150     pub fn is_empty(&self) -> bool {
 151         self.raw.is_empty()
 152     }
 153
 154     #[inline]
 155     pub fn into_iter(self) -> vec::IntoIter<T> {
 156         self.raw.into_iter()
 157     }
 158
 159     #[inline]
 160     pub fn into_iter_enumerated(
 161         self,
 162     ) -> impl DoubleEndedIterator<Item = (I, T)> + ExactSizeIterator {
 163         self.raw.into_iter().enumerate().map(|(n, t)| (I::new(n), t))
 164     }
 165
 166     #[inline]
 167     pub fn iter(&self) -> slice::Iter<'_, T> {
 168         self.raw.iter()
 169     }
 170
 171     #[inline]
 172     pub fn iter_enumerated(
 173         &self,
 174     ) -> impl DoubleEndedIterator<Item = (I, &T)> + ExactSizeIterator + '_ {
 175         self.raw.iter().enumerate().map(|(n, t)| (I::new(n), t))
 176     }
 177
 178     #[inline]
 179     pub fn indices(
 180         &self,
 181     ) -> impl DoubleEndedIterator<Item = I> + ExactSizeIterator + Clone + 'static {
 182         (0..self.len()).map(|n| I::new(n))
 183     }
 184
 185     #[inline]
 186     pub fn iter_mut(&mut self) -> slice::IterMut<'_, T> {
 187         self.raw.iter_mut()
 188     }
 189
 190     #[inline]
 191     pub fn iter_enumerated_mut(
 192         &mut self,
 193     ) -> impl DoubleEndedIterator<Item = (I, &mut T)> + ExactSizeIterator + '_ {
 194         self.raw.iter_mut().enumerate().map(|(n, t)| (I::new(n), t))
 195     }
 196
 197     #[inline]
 198     pub fn drain<'a, R: RangeBounds<usize>>(
 199         &'a mut self,
 200         range: R,
 201     ) -> impl Iterator<Item = T> + 'a {
 202         self.raw.drain(range)
 203     }
 204
 205     #[inline]
 206     pub fn drain_enumerated<'a, R: RangeBounds<usize>>(
 207         &'a mut self,
 208         range: R,
 209     ) -> impl Iterator<Item = (I, T)> + 'a {
 210         let begin = match range.start_bound() {
 211             std::ops::Bound::Included(i) => *i,
 212             std::ops::Bound::Excluded(i) => i.checked_add(1).unwrap(),
 213             std::ops::Bound::Unbounded => 0,
 214         };
 215         self.raw.drain(range).enumerate().map(move |(n, t)| (I::new(begin + n), t))
 216     }
 217
 218     #[inline]
 219     pub fn last(&self) -> Option<I> {
 220         self.len().checked_sub(1).map(I::new)
 221     }
 222
 223     #[inline]
 224     pub fn shrink_to_fit(&mut self) {
 225         self.raw.shrink_to_fit()
 226     }
 227
 228     #[inline]
 229     pub fn swap(&mut self, a: I, b: I) {
 230         self.raw.swap(a.index(), b.index())
 231     }
 232
 233     #[inline]
 234     pub fn truncate(&mut self, a: usize) {
 235         self.raw.truncate(a)
 236     }
 237
 238     #[inline]
 239     pub fn get(&self, index: I) -> Option<&T> {
 240         self.raw.get(index.index())
 241     }
 242
 243     #[inline]
 244     pub fn get_mut(&mut self, index: I) -> Option<&mut T> {
 245         self.raw.get_mut(index.index())
 246     }
 247
 248     /// Returns mutable references to two distinct elements, `a` and `b`.
 249     ///
 250     /// Panics if `a == b`.
 251     #[inline]
 252     pub fn pick2_mut(&mut self, a: I, b: I) -> (&mut T, &mut T) {
 253         let (ai, bi) = (a.index(), b.index());
 254         assert!(ai != bi);
 255
 256         if ai < bi {
 257             let (c1, c2) = self.raw.split_at_mut(bi);
 258             (&mut c1[ai], &mut c2[0])
 259         } else {
 260             let (c2, c1) = self.pick2_mut(b, a);
 261             (c1, c2)
 262         }
 263     }
 264
 265     /// Returns mutable references to three distinct elements.
 266     ///
 267     /// Panics if the elements are not distinct.
 268     #[inline]
 269     pub fn pick3_mut(&mut self, a: I, b: I, c: I) -> (&mut T, &mut T, &mut T) {
 270         let (ai, bi, ci) = (a.index(), b.index(), c.index());
 271         assert!(ai != bi && bi != ci && ci != ai);
 272         let len = self.raw.len();
 273         assert!(ai < len && bi < len && ci < len);
 274         let ptr = self.raw.as_mut_ptr();
 275         unsafe { (&mut *ptr.add(ai), &mut *ptr.add(bi), &mut *ptr.add(ci)) }
 276     }
 277
 278     pub fn convert_index_type<Ix: Idx>(self) -> IndexVec<Ix, T> {
 279         IndexVec { raw: self.raw, _marker: PhantomData }
 280     }
 281
 282     /// Grows the index vector so that it contains an entry for
 283     /// `elem`; if that is already true, then has no
 284     /// effect. Otherwise, inserts new values as needed by invoking
 285     /// `fill_value`.
 286     #[inline]
 287     pub fn ensure_contains_elem(&mut self, elem: I, fill_value: impl FnMut() -> T) {
 288         let min_new_len = elem.index() + 1;
 289         if self.len() < min_new_len {
 290             self.raw.resize_with(min_new_len, fill_value);
 291         }
 292     }
 293
 294     #[inline]
 295     pub fn resize_to_elem(&mut self, elem: I, fill_value: impl FnMut() -> T) {
 296         let min_new_len = elem.index() + 1;
 297         self.raw.resize_with(min_new_len, fill_value);
 298     }
 299 }
 300
 301 /// `IndexVec` is often used as a map, so it provides some map-like APIs.
 302 impl<I: Idx, T> IndexVec<I, Option<T>> {
 303     #[inline]
 304     pub fn insert(&mut self, index: I, value: T) -> Option<T> {
 305         self.ensure_contains_elem(index, || None);
 306         self[index].replace(value)
 307     }
 308
 309     #[inline]
 310     pub fn get_or_insert_with(&mut self, index: I, value: impl FnOnce() -> T) -> &mut T {
 311         self.ensure_contains_elem(index, || None);
 312         self[index].get_or_insert_with(value)
 313     }
 314
 315     #[inline]
 316     pub fn remove(&mut self, index: I) -> Option<T> {
 317         self.ensure_contains_elem(index, || None);
 318         self[index].take()
 319     }
 320 }
 321
 322 impl<I: Idx, T: Clone> IndexVec<I, T> {
 323     #[inline]
 324     pub fn resize(&mut self, new_len: usize, value: T) {
 325         self.raw.resize(new_len, value)
 326     }
 327 }
 328
 329 impl<I: Idx, T: Ord> IndexVec<I, T> {
 330     #[inline]
 331     pub fn binary_search(&self, value: &T) -> Result<I, I> {
 332         match self.raw.binary_search(value) {
 333             Ok(i) => Ok(Idx::new(i)),
 334             Err(i) => Err(Idx::new(i)),
 335         }
 336     }
 337 }
 338
 339 impl<I: Idx, T> Index<I> for IndexVec<I, T> {
 340     type Output = T;
 341
 342     #[inline]
 343     fn index(&self, index: I) -> &T {
 344         &self.raw[index.index()]
 345     }
 346 }
 347
 348 impl<I: Idx, T> IndexMut<I> for IndexVec<I, T> {
 349     #[inline]
 350     fn index_mut(&mut self, index: I) -> &mut T {
 351         &mut self.raw[index.index()]
 352     }
 353 }
 354
 355 impl<I: Idx, T> Default for IndexVec<I, T> {
 356     #[inline]
 357     fn default() -> Self {
 358         Self::new()
 359     }
 360 }
 361
 362 impl<I: Idx, T> Extend<T> for IndexVec<I, T> {
 363     #[inline]
 364     fn extend<J: IntoIterator<Item = T>>(&mut self, iter: J) {
 365         self.raw.extend(iter);
 366     }
 367
 368     #[inline]
 369     #[cfg(feature = "nightly")]
 370     fn extend_one(&mut self, item: T) {
 371         self.raw.push(item);
 372     }
 373
 374     #[inline]
 375     #[cfg(feature = "nightly")]
 376     fn extend_reserve(&mut self, additional: usize) {
 377         self.raw.reserve(additional);
 378     }
 379 }
 380
 381 impl<I: Idx, T> FromIterator<T> for IndexVec<I, T> {
 382     #[inline]
 383     fn from_iter<J>(iter: J) -> Self
 384     where
 385         J: IntoIterator<Item = T>,
 386     {
 387         IndexVec { raw: FromIterator::from_iter(iter), _marker: PhantomData }
 388     }
 389 }
 390
 391 impl<I: Idx, T> IntoIterator for IndexVec<I, T> {
 392     type Item = T;
 393     type IntoIter = vec::IntoIter<T>;
 394
 395     #[inline]
 396     fn into_iter(self) -> vec::IntoIter<T> {
 397         self.raw.into_iter()
 398     }
 399 }
 400
 401 impl<'a, I: Idx, T> IntoIterator for &'a IndexVec<I, T> {
 402     type Item = &'a T;
 403     type IntoIter = slice::Iter<'a, T>;
 404
 405     #[inline]
 406     fn into_iter(self) -> slice::Iter<'a, T> {
 407         self.raw.iter()
 408     }
 409 }
 410
 411 impl<'a, I: Idx, T> IntoIterator for &'a mut IndexVec<I, T> {
 412     type Item = &'a mut T;
 413     type IntoIter = slice::IterMut<'a, T>;
 414
 415     #[inline]
 416     fn into_iter(self) -> slice::IterMut<'a, T> {
 417         self.raw.iter_mut()
 418     }
 419 }
 420
 421 #[cfg(test)]
 422 mod tests;