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         self.raw.drain(range).enumerate().map(|(n, t)| (I::new(n), t))
 211     }
 212
 213     #[inline]
 214     pub fn last(&self) -> Option<I> {
 215         self.len().checked_sub(1).map(I::new)
 216     }
 217
 218     #[inline]
 219     pub fn shrink_to_fit(&mut self) {
 220         self.raw.shrink_to_fit()
 221     }
 222
 223     #[inline]
 224     pub fn swap(&mut self, a: I, b: I) {
 225         self.raw.swap(a.index(), b.index())
 226     }
 227
 228     #[inline]
 229     pub fn truncate(&mut self, a: usize) {
 230         self.raw.truncate(a)
 231     }
 232
 233     #[inline]
 234     pub fn get(&self, index: I) -> Option<&T> {
 235         self.raw.get(index.index())
 236     }
 237
 238     #[inline]
 239     pub fn get_mut(&mut self, index: I) -> Option<&mut T> {
 240         self.raw.get_mut(index.index())
 241     }
 242
 243     /// Returns mutable references to two distinct elements, `a` and `b`.
 244     ///
 245     /// Panics if `a == b`.
 246     #[inline]
 247     pub fn pick2_mut(&mut self, a: I, b: I) -> (&mut T, &mut T) {
 248         let (ai, bi) = (a.index(), b.index());
 249         assert!(ai != bi);
 250
 251         if ai < bi {
 252             let (c1, c2) = self.raw.split_at_mut(bi);
 253             (&mut c1[ai], &mut c2[0])
 254         } else {
 255             let (c2, c1) = self.pick2_mut(b, a);
 256             (c1, c2)
 257         }
 258     }
 259
 260     /// Returns mutable references to three distinct elements.
 261     ///
 262     /// Panics if the elements are not distinct.
 263     #[inline]
 264     pub fn pick3_mut(&mut self, a: I, b: I, c: I) -> (&mut T, &mut T, &mut T) {
 265         let (ai, bi, ci) = (a.index(), b.index(), c.index());
 266         assert!(ai != bi && bi != ci && ci != ai);
 267         let len = self.raw.len();
 268         assert!(ai < len && bi < len && ci < len);
 269         let ptr = self.raw.as_mut_ptr();
 270         unsafe { (&mut *ptr.add(ai), &mut *ptr.add(bi), &mut *ptr.add(ci)) }
 271     }
 272
 273     pub fn convert_index_type<Ix: Idx>(self) -> IndexVec<Ix, T> {
 274         IndexVec { raw: self.raw, _marker: PhantomData }
 275     }
 276
 277     /// Grows the index vector so that it contains an entry for
 278     /// `elem`; if that is already true, then has no
 279     /// effect. Otherwise, inserts new values as needed by invoking
 280     /// `fill_value`.
 281     #[inline]
 282     pub fn ensure_contains_elem(&mut self, elem: I, fill_value: impl FnMut() -> T) {
 283         let min_new_len = elem.index() + 1;
 284         if self.len() < min_new_len {
 285             self.raw.resize_with(min_new_len, fill_value);
 286         }
 287     }
 288
 289     #[inline]
 290     pub fn resize_to_elem(&mut self, elem: I, fill_value: impl FnMut() -> T) {
 291         let min_new_len = elem.index() + 1;
 292         self.raw.resize_with(min_new_len, fill_value);
 293     }
 294 }
 295
 296 /// `IndexVec` is often used as a map, so it provides some map-like APIs.
 297 impl<I: Idx, T> IndexVec<I, Option<T>> {
 298     #[inline]
 299     pub fn insert(&mut self, index: I, value: T) -> Option<T> {
 300         self.ensure_contains_elem(index, || None);
 301         self[index].replace(value)
 302     }
 303
 304     #[inline]
 305     pub fn get_or_insert_with(&mut self, index: I, value: impl FnOnce() -> T) -> &mut T {
 306         self.ensure_contains_elem(index, || None);
 307         self[index].get_or_insert_with(value)
 308     }
 309
 310     #[inline]
 311     pub fn remove(&mut self, index: I) -> Option<T> {
 312         self.ensure_contains_elem(index, || None);
 313         self[index].take()
 314     }
 315 }
 316
 317 impl<I: Idx, T: Clone> IndexVec<I, T> {
 318     #[inline]
 319     pub fn resize(&mut self, new_len: usize, value: T) {
 320         self.raw.resize(new_len, value)
 321     }
 322 }
 323
 324 impl<I: Idx, T: Ord> IndexVec<I, T> {
 325     #[inline]
 326     pub fn binary_search(&self, value: &T) -> Result<I, I> {
 327         match self.raw.binary_search(value) {
 328             Ok(i) => Ok(Idx::new(i)),
 329             Err(i) => Err(Idx::new(i)),
 330         }
 331     }
 332 }
 333
 334 impl<I: Idx, T> Index<I> for IndexVec<I, T> {
 335     type Output = T;
 336
 337     #[inline]
 338     fn index(&self, index: I) -> &T {
 339         &self.raw[index.index()]
 340     }
 341 }
 342
 343 impl<I: Idx, T> IndexMut<I> for IndexVec<I, T> {
 344     #[inline]
 345     fn index_mut(&mut self, index: I) -> &mut T {
 346         &mut self.raw[index.index()]
 347     }
 348 }
 349
 350 impl<I: Idx, T> Default for IndexVec<I, T> {
 351     #[inline]
 352     fn default() -> Self {
 353         Self::new()
 354     }
 355 }
 356
 357 impl<I: Idx, T> Extend<T> for IndexVec<I, T> {
 358     #[inline]
 359     fn extend<J: IntoIterator<Item = T>>(&mut self, iter: J) {
 360         self.raw.extend(iter);
 361     }
 362
 363     #[inline]
 364     #[cfg(feature = "nightly")]
 365     fn extend_one(&mut self, item: T) {
 366         self.raw.push(item);
 367     }
 368
 369     #[inline]
 370     #[cfg(feature = "nightly")]
 371     fn extend_reserve(&mut self, additional: usize) {
 372         self.raw.reserve(additional);
 373     }
 374 }
 375
 376 impl<I: Idx, T> FromIterator<T> for IndexVec<I, T> {
 377     #[inline]
 378     fn from_iter<J>(iter: J) -> Self
 379     where
 380         J: IntoIterator<Item = T>,
 381     {
 382         IndexVec { raw: FromIterator::from_iter(iter), _marker: PhantomData }
 383     }
 384 }
 385
 386 impl<I: Idx, T> IntoIterator for IndexVec<I, T> {
 387     type Item = T;
 388     type IntoIter = vec::IntoIter<T>;
 389
 390     #[inline]
 391     fn into_iter(self) -> vec::IntoIter<T> {
 392         self.raw.into_iter()
 393     }
 394 }
 395
 396 impl<'a, I: Idx, T> IntoIterator for &'a IndexVec<I, T> {
 397     type Item = &'a T;
 398     type IntoIter = slice::Iter<'a, T>;
 399
 400     #[inline]
 401     fn into_iter(self) -> slice::Iter<'a, T> {
 402         self.raw.iter()
 403     }
 404 }
 405
 406 impl<'a, I: Idx, T> IntoIterator for &'a mut IndexVec<I, T> {
 407     type Item = &'a mut T;
 408     type IntoIter = slice::IterMut<'a, T>;
 409
 410     #[inline]
 411     fn into_iter(self) -> slice::IterMut<'a, T> {
 412         self.raw.iter_mut()
 413     }
 414 }
 415
 416 #[cfg(test)]
 417 mod tests;