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             // Leave out derives marker so we can use its absence to ensure it comes first
  49             @type         [$name]
  50             @pub          [pub]
  51             @max          [::std::u32::MAX]
  52             @debug_format ["{}"]);
  53     );
  54
  55     ($name:ident nopub) => (
  56         newtype_index!(
  57             // Leave out derives marker so we can use its absence to ensure it comes first
  58             @type         [$name]
  59             @pub          []
  60             @max          [::std::u32::MAX]
  61             @debug_format ["{}"]);
  62     );
  63
  64     // Define any constants
  65     ($name:ident { $($tokens:tt)+ }) => (
  66         newtype_index!(
  67             // Leave out derives marker so we can use its absence to ensure it comes first
  68             @type         [$name]
  69             @pub          [pub]
  70             @max          [::std::u32::MAX]
  71             @debug_format ["{}"]
  72                           $($tokens)+);
  73     );
  74
  75     // Define any constants
  76     ($name:ident nopub { $($tokens:tt)+ }) => (
  77         newtype_index!(
  78             // Leave out derives marker so we can use its absence to ensure it comes first
  79             @type         [$name]
  80             @pub          []
  81             @max          [::std::u32::MAX]
  82             @debug_format [unsafe {::std::intrinsics::type_name::<$name>() }]
  83                           $($tokens)+);
  84     );
  85
  86     // ---- private rules ----
  87
  88     // Base case, user-defined constants (if any) have already been defined
  89     (@derives      [$($derives:ident,)*]
  90      @type         [$type:ident]
  91      @pub          [$($pub:tt)*]
  92      @max          [$max:expr]
  93      @debug_format [$debug_format:expr]) => (
  94         #[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, $($derives),*)]
  95         pub struct $type($($pub)* u32);
  96
  97         impl Idx for $type {
  98             fn new(value: usize) -> Self {
  99                 assert!(value < ($max) as usize);
 100                 $type(value as u32)
 101             }
 102
 103             fn index(self) -> usize {
 104                 self.0 as usize
 105             }
 106         }
 107
 108         newtype_index!(
 109             @handle_debug
 110             @derives      [$($derives,)*]
 111             @type         [$type]
 112             @debug_format [$debug_format]);
 113     );
 114
 115     // base case for handle_debug where format is custom. No Debug implementation is emitted.
 116     (@handle_debug
 117      @derives      [$($_derives:ident,)*]
 118      @type         [$type:ident]
 119      @debug_format [custom]) => ();
 120
 121     // base case for handle_debug, no debug overrides found, so use default
 122     (@handle_debug
 123      @derives      []
 124      @type         [$type:ident]
 125      @debug_format [$debug_format:expr]) => (
 126         impl ::std::fmt::Debug for $type {
 127             fn fmt(&self, fmt: &mut ::std::fmt::Formatter) -> ::std::fmt::Result {
 128                 write!(fmt, $debug_format, self.0)
 129             }
 130         }
 131     );
 132
 133     // Debug is requested for derive, don't generate any Debug implementation.
 134     (@handle_debug
 135      @derives      [Debug, $($derives:ident,)*]
 136      @type         [$type:ident]
 137      @debug_format [$debug_format:expr]) => ();
 138
 139     // It's not Debug, so just pop it off the front of the derives stack and check the rest.
 140     (@handle_debug
 141      @derives      [$_derive:ident, $($derives:ident,)*]
 142      @type         [$type:ident]
 143      @debug_format [$debug_format:expr]) => (
 144         newtype_index!(
 145             @handle_debug
 146             @derives      [$($derives,)*]
 147             @type         [$type]
 148             @debug_format [$debug_format]);
 149     );
 150
 151     // Append comma to end of derives list if it's missing
 152     (@type         [$type:ident]
 153      @pub          [$($pub:tt)*]
 154      @max          [$max:expr]
 155      @debug_format [$debug_format:expr]
 156                    derive [$($derives:ident),*]
 157                    $($tokens:tt)*) => (
 158         newtype_index!(
 159             @type         [$type]
 160             @pub          [$($pub)*]
 161             @max          [$max]
 162             @debug_format [$debug_format]
 163                           derive [$($derives,)*]
 164                           $($tokens)*);
 165     );
 166
 167     // By not including the @derives marker in this list nor in the default args, we can force it
 168     // to come first if it exists. When encodable is custom, just use the derives list as-is.
 169     (@type         [$type:ident]
 170      @pub          [$($pub:tt)*]
 171      @max          [$max:expr]
 172      @debug_format [$debug_format:expr]
 173                    derive [$($derives:ident,)+]
 174                    ENCODABLE = custom
 175                    $($tokens:tt)*) => (
 176         newtype_index!(
 177             @derives      [$($derives,)+]
 178             @type         [$type]
 179             @pub          [$($pub)*]
 180             @max          [$max]
 181             @debug_format [$debug_format]
 182                           $($tokens)*);
 183     );
 184
 185     // By not including the @derives marker in this list nor in the default args, we can force it
 186     // to come first if it exists. When encodable isn't custom, add serialization traits by default.
 187     (@type         [$type:ident]
 188      @pub          [$($pub:tt)*]
 189      @max          [$max:expr]
 190      @debug_format [$debug_format:expr]
 191                    derive [$($derives:ident,)+]
 192                    $($tokens:tt)*) => (
 193         newtype_index!(
 194             @derives      [$($derives,)+ RustcDecodable, RustcEncodable,]
 195             @type         [$type]
 196             @pub          [$($pub)*]
 197             @max          [$max]
 198             @debug_format [$debug_format]
 199                           $($tokens)*);
 200     );
 201
 202     // The case where no derives are added, but encodable is overriden. Don't
 203     // derive serialization traits
 204     (@type         [$type:ident]
 205      @pub          [$($pub:tt)*]
 206      @max          [$max:expr]
 207      @debug_format [$debug_format:expr]
 208                    ENCODABLE = custom
 209                    $($tokens:tt)*) => (
 210         newtype_index!(
 211             @derives      []
 212             @type         [$type]
 213             @pub          [$($pub)*]
 214             @max          [$max]
 215             @debug_format [$debug_format]
 216                           $($tokens)*);
 217     );
 218
 219     // The case where no derives are added, add serialization derives by default
 220     (@type         [$type:ident]
 221      @pub          [$($pub:tt)*]
 222      @max          [$max:expr]
 223      @debug_format [$debug_format:expr]
 224                    $($tokens:tt)*) => (
 225         newtype_index!(
 226             @derives      [RustcDecodable, RustcEncodable,]
 227             @type         [$type]
 228             @pub          [$($pub)*]
 229             @max          [$max]
 230             @debug_format [$debug_format]
 231                           $($tokens)*);
 232     );
 233
 234     // Rewrite final without comma to one that includes comma
 235     (@derives      [$($derives:ident,)*]
 236      @type         [$type:ident]
 237      @pub          [$($pub:tt)*]
 238      @max          [$max:expr]
 239      @debug_format [$debug_format:expr]
 240                    $name:ident = $constant:expr) => (
 241         newtype_index!(
 242             @derives      [$($derives,)*]
 243             @type         [$type]
 244             @pub          [$($pub)*]
 245             @max          [$max]
 246             @debug_format [$debug_format]
 247                           $name = $constant,);
 248     );
 249
 250     // Rewrite final const without comma to one that includes comma
 251     (@derives      [$($derives:ident,)*]
 252      @type         [$type:ident]
 253      @pub          [$($pub:tt)*]
 254      @max          [$_max:expr]
 255      @debug_format [$debug_format:expr]
 256                    $(#[doc = $doc:expr])*
 257                    const $name:ident = $constant:expr) => (
 258         newtype_index!(
 259             @derives      [$($derives,)*]
 260             @type         [$type]
 261             @pub          [$($pub)*]
 262             @max          [$max]
 263             @debug_format [$debug_format]
 264                           $(#[doc = $doc])* const $name = $constant,);
 265     );
 266
 267     // Replace existing default for max
 268     (@derives      [$($derives:ident,)*]
 269      @type         [$type:ident]
 270      @pub          [$($pub:tt)*]
 271      @max          [$_max:expr]
 272      @debug_format [$debug_format:expr]
 273                    MAX = $max:expr,
 274                    $($tokens:tt)*) => (
 275         newtype_index!(
 276             @derives      [$($derives,)*]
 277             @type         [$type]
 278             @pub          [$($pub)*]
 279             @max          [$max]
 280             @debug_format [$debug_format]
 281                           $($tokens)*);
 282     );
 283
 284     // Replace existing default for debug_format
 285     (@derives      [$($derives:ident,)*]
 286      @type         [$type:ident]
 287      @pub          [$($pub:tt)*]
 288      @max          [$max:expr]
 289      @debug_format [$_debug_format:expr]
 290                    DEBUG_FORMAT = $debug_format:expr,
 291                    $($tokens:tt)*) => (
 292         newtype_index!(
 293             @derives      [$($derives,)*]
 294             @type         [$type]
 295             @pub          [$($pub)*]
 296             @max          [$max]
 297             @debug_format [$debug_format]
 298                           $($tokens)*);
 299     );
 300
 301     // Assign a user-defined constant
 302     (@derives      [$($derives:ident,)*]
 303      @type         [$type:ident]
 304      @pub          [$($pub:tt)*]
 305      @max          [$max:expr]
 306      @debug_format [$debug_format:expr]
 307                    $(#[doc = $doc:expr])*
 308                    const $name:ident = $constant:expr,
 309                    $($tokens:tt)*) => (
 310         $(#[doc = $doc])*
 311         pub const $name: $type = $type($constant);
 312         newtype_index!(
 313             @derives      [$($derives,)*]
 314             @type         [$type]
 315             @pub          [$($pub)*]
 316             @max          [$max]
 317             @debug_format [$debug_format]
 318                           $($tokens)*);
 319     );
 320 }
 321
 322 #[derive(Clone, PartialEq, Eq)]
 323 pub struct IndexVec<I: Idx, T> {
 324     pub raw: Vec<T>,
 325     _marker: PhantomData<Fn(&I)>
 326 }
 327
 328 impl<I: Idx, T: serialize::Encodable> serialize::Encodable for IndexVec<I, T> {
 329     fn encode<S: serialize::Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
 330         serialize::Encodable::encode(&self.raw, s)
 331     }
 332 }
 333
 334 impl<I: Idx, T: serialize::Decodable> serialize::Decodable for IndexVec<I, T> {
 335     fn decode<D: serialize::Decoder>(d: &mut D) -> Result<Self, D::Error> {
 336         serialize::Decodable::decode(d).map(|v| {
 337             IndexVec { raw: v, _marker: PhantomData }
 338         })
 339     }
 340 }
 341
 342 impl<I: Idx, T: fmt::Debug> fmt::Debug for IndexVec<I, T> {
 343     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
 344         fmt::Debug::fmt(&self.raw, fmt)
 345     }
 346 }
 347
 348 pub type Enumerated<I, J> = iter::Map<iter::Enumerate<J>, IntoIdx<I>>;
 349
 350 impl<I: Idx, T> IndexVec<I, T> {
 351     #[inline]
 352     pub fn new() -> Self {
 353         IndexVec { raw: Vec::new(), _marker: PhantomData }
 354     }
 355
 356     #[inline]
 357     pub fn with_capacity(capacity: usize) -> Self {
 358         IndexVec { raw: Vec::with_capacity(capacity), _marker: PhantomData }
 359     }
 360
 361     #[inline]
 362     pub fn from_elem<S>(elem: T, universe: &IndexVec<I, S>) -> Self
 363         where T: Clone
 364     {
 365         IndexVec { raw: vec![elem; universe.len()], _marker: PhantomData }
 366     }
 367
 368     #[inline]
 369     pub fn from_elem_n(elem: T, n: usize) -> Self
 370         where T: Clone
 371     {
 372         IndexVec { raw: vec![elem; n], _marker: PhantomData }
 373     }
 374
 375     #[inline]
 376     pub fn push(&mut self, d: T) -> I {
 377         let idx = I::new(self.len());
 378         self.raw.push(d);
 379         idx
 380     }
 381
 382     #[inline]
 383     pub fn len(&self) -> usize {
 384         self.raw.len()
 385     }
 386
 387     #[inline]
 388     pub fn is_empty(&self) -> bool {
 389         self.raw.is_empty()
 390     }
 391
 392     #[inline]
 393     pub fn into_iter(self) -> vec::IntoIter<T> {
 394         self.raw.into_iter()
 395     }
 396
 397     #[inline]
 398     pub fn into_iter_enumerated(self) -> Enumerated<I, vec::IntoIter<T>>
 399     {
 400         self.raw.into_iter().enumerate().map(IntoIdx { _marker: PhantomData })
 401     }
 402
 403     #[inline]
 404     pub fn iter(&self) -> slice::Iter<T> {
 405         self.raw.iter()
 406     }
 407
 408     #[inline]
 409     pub fn iter_enumerated(&self) -> Enumerated<I, slice::Iter<T>>
 410     {
 411         self.raw.iter().enumerate().map(IntoIdx { _marker: PhantomData })
 412     }
 413
 414     #[inline]
 415     pub fn indices(&self) -> iter::Map<Range<usize>, IntoIdx<I>> {
 416         (0..self.len()).map(IntoIdx { _marker: PhantomData })
 417     }
 418
 419     #[inline]
 420     pub fn iter_mut(&mut self) -> slice::IterMut<T> {
 421         self.raw.iter_mut()
 422     }
 423
 424     #[inline]
 425     pub fn iter_enumerated_mut(&mut self) -> Enumerated<I, slice::IterMut<T>>
 426     {
 427         self.raw.iter_mut().enumerate().map(IntoIdx { _marker: PhantomData })
 428     }
 429
 430     #[inline]
 431     pub fn drain<'a, R: RangeArgument<usize>>(
 432         &'a mut self, range: R) -> impl Iterator<Item=T> + 'a {
 433         self.raw.drain(range)
 434     }
 435
 436     #[inline]
 437     pub fn drain_enumerated<'a, R: RangeArgument<usize>>(
 438         &'a mut self, range: R) -> impl Iterator<Item=(I, T)> + 'a {
 439         self.raw.drain(range).enumerate().map(IntoIdx { _marker: PhantomData })
 440     }
 441
 442     #[inline]
 443     pub fn last(&self) -> Option<I> {
 444         self.len().checked_sub(1).map(I::new)
 445     }
 446
 447     #[inline]
 448     pub fn shrink_to_fit(&mut self) {
 449         self.raw.shrink_to_fit()
 450     }
 451
 452     #[inline]
 453     pub fn swap(&mut self, a: usize, b: usize) {
 454         self.raw.swap(a, b)
 455     }
 456
 457     #[inline]
 458     pub fn truncate(&mut self, a: usize) {
 459         self.raw.truncate(a)
 460     }
 461
 462     #[inline]
 463     pub fn get(&self, index: I) -> Option<&T> {
 464         self.raw.get(index.index())
 465     }
 466
 467     #[inline]
 468     pub fn get_mut(&mut self, index: I) -> Option<&mut T> {
 469         self.raw.get_mut(index.index())
 470     }
 471 }
 472
 473 impl<I: Idx, T: Clone> IndexVec<I, T> {
 474     #[inline]
 475     pub fn resize(&mut self, new_len: usize, value: T) {
 476         self.raw.resize(new_len, value)
 477     }
 478 }
 479
 480 impl<I: Idx, T: Ord> IndexVec<I, T> {
 481     #[inline]
 482     pub fn binary_search(&self, value: &T) -> Result<I, I> {
 483         match self.raw.binary_search(value) {
 484             Ok(i) => Ok(Idx::new(i)),
 485             Err(i) => Err(Idx::new(i)),
 486         }
 487     }
 488 }
 489
 490 impl<I: Idx, T> Index<I> for IndexVec<I, T> {
 491     type Output = T;
 492
 493     #[inline]
 494     fn index(&self, index: I) -> &T {
 495         &self.raw[index.index()]
 496     }
 497 }
 498
 499 impl<I: Idx, T> IndexMut<I> for IndexVec<I, T> {
 500     #[inline]
 501     fn index_mut(&mut self, index: I) -> &mut T {
 502         &mut self.raw[index.index()]
 503     }
 504 }
 505
 506 impl<I: Idx, T> Default for IndexVec<I, T> {
 507     #[inline]
 508     fn default() -> Self {
 509         Self::new()
 510     }
 511 }
 512
 513 impl<I: Idx, T> Extend<T> for IndexVec<I, T> {
 514     #[inline]
 515     fn extend<J: IntoIterator<Item = T>>(&mut self, iter: J) {
 516         self.raw.extend(iter);
 517     }
 518 }
 519
 520 impl<I: Idx, T> FromIterator<T> for IndexVec<I, T> {
 521     #[inline]
 522     fn from_iter<J>(iter: J) -> Self where J: IntoIterator<Item=T> {
 523         IndexVec { raw: FromIterator::from_iter(iter), _marker: PhantomData }
 524     }
 525 }
 526
 527 impl<I: Idx, T> IntoIterator for IndexVec<I, T> {
 528     type Item = T;
 529     type IntoIter = vec::IntoIter<T>;
 530
 531     #[inline]
 532     fn into_iter(self) -> vec::IntoIter<T> {
 533         self.raw.into_iter()
 534     }
 535
 536 }
 537
 538 impl<'a, I: Idx, T> IntoIterator for &'a IndexVec<I, T> {
 539     type Item = &'a T;
 540     type IntoIter = slice::Iter<'a, T>;
 541
 542     #[inline]
 543     fn into_iter(self) -> slice::Iter<'a, T> {
 544         self.raw.iter()
 545     }
 546 }
 547
 548 impl<'a, I: Idx, T> IntoIterator for &'a mut IndexVec<I, T> {
 549     type Item = &'a mut T;
 550     type IntoIter = slice::IterMut<'a, T>;
 551
 552     #[inline]
 553     fn into_iter(self) -> slice::IterMut<'a, T> {
 554         self.raw.iter_mut()
 555     }
 556 }
 557
 558 pub struct IntoIdx<I: Idx> { _marker: PhantomData<fn(&I)> }
 559 impl<I: Idx, T> FnOnce<((usize, T),)> for IntoIdx<I> {
 560     type Output = (I, T);
 561
 562     extern "rust-call" fn call_once(self, ((n, t),): ((usize, T),)) -> Self::Output {
 563         (I::new(n), t)
 564     }
 565 }
 566
 567 impl<I: Idx, T> FnMut<((usize, T),)> for IntoIdx<I> {
 568     extern "rust-call" fn call_mut(&mut self, ((n, t),): ((usize, T),)) -> Self::Output {
 569         (I::new(n), t)
 570     }
 571 }
 572
 573 impl<I: Idx> FnOnce<(usize,)> for IntoIdx<I> {
 574     type Output = I;
 575
 576     extern "rust-call" fn call_once(self, (n,): (usize,)) -> Self::Output {
 577         I::new(n)
 578     }
 579 }
 580
 581 impl<I: Idx> FnMut<(usize,)> for IntoIdx<I> {
 582     extern "rust-call" fn call_mut(&mut self, (n,): (usize,)) -> Self::Output {
 583         I::new(n)
 584     }
 585 }