compiler/rustc_index/src/vec.rs

   1 use rustc_serialize::{Decodable, Decoder, Encodable, Encoder};
   2
   3 use std::fmt;
   4 use std::fmt::Debug;
   5 use std::hash::Hash;
   6 use std::iter::{self, FromIterator};
   7 use std::marker::PhantomData;
   8 use std::ops::{Index, IndexMut, Range, 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 + Ord + Debug + Hash {
  16     fn new(idx: usize) -> Self;
  17
  18     fn index(self) -> usize;
  19
  20     fn increment_by(&mut self, amount: usize) {
  21         *self = self.plus(amount);
  22     }
  23
  24     fn plus(self, amount: usize) -> Self {
  25         Self::new(self.index() + amount)
  26     }
  27 }
  28
  29 impl Idx for usize {
  30     #[inline]
  31     fn new(idx: usize) -> Self {
  32         idx
  33     }
  34     #[inline]
  35     fn index(self) -> usize {
  36         self
  37     }
  38 }
  39
  40 impl Idx for u32 {
  41     #[inline]
  42     fn new(idx: usize) -> Self {
  43         assert!(idx <= u32::MAX as usize);
  44         idx as u32
  45     }
  46     #[inline]
  47     fn index(self) -> usize {
  48         self as usize
  49     }
  50 }
  51
  52 /// Creates a struct type `S` that can be used as an index with
  53 /// `IndexVec` and so on.
  54 ///
  55 /// There are two ways of interacting with these indices:
  56 ///
  57 /// - The `From` impls are the preferred way. So you can do
  58 ///   `S::from(v)` with a `usize` or `u32`. And you can convert back
  59 ///   to an integer with `u32::from(s)`.
  60 ///
  61 /// - Alternatively, you can use the methods `S::new(v)` and `s.index()`
  62 ///   to create/return a value.
  63 ///
  64 /// Internally, the index uses a u32, so the index must not exceed
  65 /// `u32::MAX`. You can also customize things like the `Debug` impl,
  66 /// what traits are derived, and so forth via the macro.
  67 #[macro_export]
  68 #[allow_internal_unstable(step_trait, step_trait_ext, rustc_attrs)]
  69 macro_rules! newtype_index {
  70     // ---- public rules ----
  71
  72     // Use default constants
  73     ($(#[$attrs:meta])* $v:vis struct $name:ident { .. }) => (
  74         $crate::newtype_index!(
  75             // Leave out derives marker so we can use its absence to ensure it comes first
  76             @attrs        [$(#[$attrs])*]
  77             @type         [$name]
  78             // shave off 256 indices at the end to allow space for packing these indices into enums
  79             @max          [0xFFFF_FF00]
  80             @vis          [$v]
  81             @debug_format ["{}"]);
  82     );
  83
  84     // Define any constants
  85     ($(#[$attrs:meta])* $v:vis struct $name:ident { $($tokens:tt)+ }) => (
  86         $crate::newtype_index!(
  87             // Leave out derives marker so we can use its absence to ensure it comes first
  88             @attrs        [$(#[$attrs])*]
  89             @type         [$name]
  90             // shave off 256 indices at the end to allow space for packing these indices into enums
  91             @max          [0xFFFF_FF00]
  92             @vis          [$v]
  93             @debug_format ["{}"]
  94                           $($tokens)+);
  95     );
  96
  97     // ---- private rules ----
  98
  99     // Base case, user-defined constants (if any) have already been defined
 100     (@derives      [$($derives:ident,)*]
 101      @attrs        [$(#[$attrs:meta])*]
 102      @type         [$type:ident]
 103      @max          [$max:expr]
 104      @vis          [$v:vis]
 105      @debug_format [$debug_format:tt]) => (
 106         $(#[$attrs])*
 107         #[derive(Copy, PartialEq, Eq, Hash, PartialOrd, Ord, $($derives),*)]
 108         #[rustc_layout_scalar_valid_range_end($max)]
 109         $v struct $type {
 110             private: u32
 111         }
 112
 113         impl Clone for $type {
 114             #[inline]
 115             fn clone(&self) -> Self {
 116                 *self
 117             }
 118         }
 119
 120         impl $type {
 121             $v const MAX_AS_U32: u32 = $max;
 122
 123             $v const MAX: Self = Self::from_u32($max);
 124
 125             #[inline]
 126             $v const fn from_usize(value: usize) -> Self {
 127                 assert!(value <= ($max as usize));
 128                 unsafe {
 129                     Self::from_u32_unchecked(value as u32)
 130                 }
 131             }
 132
 133             #[inline]
 134             $v const fn from_u32(value: u32) -> Self {
 135                 assert!(value <= $max);
 136                 unsafe {
 137                     Self::from_u32_unchecked(value)
 138                 }
 139             }
 140
 141             #[inline]
 142             $v const unsafe fn from_u32_unchecked(value: u32) -> Self {
 143                 Self { private: value }
 144             }
 145
 146             /// Extracts the value of this index as an integer.
 147             #[inline]
 148             $v const fn index(self) -> usize {
 149                 self.as_usize()
 150             }
 151
 152             /// Extracts the value of this index as a `u32`.
 153             #[inline]
 154             $v const fn as_u32(self) -> u32 {
 155                 self.private
 156             }
 157
 158             /// Extracts the value of this index as a `usize`.
 159             #[inline]
 160             $v const fn as_usize(self) -> usize {
 161                 self.as_u32() as usize
 162             }
 163         }
 164
 165         impl std::ops::Add<usize> for $type {
 166             type Output = Self;
 167
 168             fn add(self, other: usize) -> Self {
 169                 Self::from_usize(self.index() + other)
 170             }
 171         }
 172
 173         impl $crate::vec::Idx for $type {
 174             #[inline]
 175             fn new(value: usize) -> Self {
 176                 Self::from_usize(value)
 177             }
 178
 179             #[inline]
 180             fn index(self) -> usize {
 181                 self.as_usize()
 182             }
 183         }
 184
 185         unsafe impl ::std::iter::Step for $type {
 186             #[inline]
 187             fn steps_between(start: &Self, end: &Self) -> Option<usize> {
 188                 <usize as ::std::iter::Step>::steps_between(
 189                     &Self::index(*start),
 190                     &Self::index(*end),
 191                 )
 192             }
 193
 194             #[inline]
 195             fn forward_checked(start: Self, u: usize) -> Option<Self> {
 196                 Self::index(start).checked_add(u).map(Self::from_usize)
 197             }
 198
 199             #[inline]
 200             fn backward_checked(start: Self, u: usize) -> Option<Self> {
 201                 Self::index(start).checked_sub(u).map(Self::from_usize)
 202             }
 203         }
 204
 205         impl From<$type> for u32 {
 206             #[inline]
 207             fn from(v: $type) -> u32 {
 208                 v.as_u32()
 209             }
 210         }
 211
 212         impl From<$type> for usize {
 213             #[inline]
 214             fn from(v: $type) -> usize {
 215                 v.as_usize()
 216             }
 217         }
 218
 219         impl From<usize> for $type {
 220             #[inline]
 221             fn from(value: usize) -> Self {
 222                 Self::from_usize(value)
 223             }
 224         }
 225
 226         impl From<u32> for $type {
 227             #[inline]
 228             fn from(value: u32) -> Self {
 229                 Self::from_u32(value)
 230             }
 231         }
 232
 233         $crate::newtype_index!(
 234             @handle_debug
 235             @derives      [$($derives,)*]
 236             @type         [$type]
 237             @debug_format [$debug_format]);
 238     );
 239
 240     // base case for handle_debug where format is custom. No Debug implementation is emitted.
 241     (@handle_debug
 242      @derives      [$($_derives:ident,)*]
 243      @type         [$type:ident]
 244      @debug_format [custom]) => ();
 245
 246     // base case for handle_debug, no debug overrides found, so use default
 247     (@handle_debug
 248      @derives      []
 249      @type         [$type:ident]
 250      @debug_format [$debug_format:tt]) => (
 251         impl ::std::fmt::Debug for $type {
 252             fn fmt(&self, fmt: &mut ::std::fmt::Formatter<'_>) -> ::std::fmt::Result {
 253                 write!(fmt, $debug_format, self.as_u32())
 254             }
 255         }
 256     );
 257
 258     // Debug is requested for derive, don't generate any Debug implementation.
 259     (@handle_debug
 260      @derives      [Debug, $($derives:ident,)*]
 261      @type         [$type:ident]
 262      @debug_format [$debug_format:tt]) => ();
 263
 264     // It's not Debug, so just pop it off the front of the derives stack and check the rest.
 265     (@handle_debug
 266      @derives      [$_derive:ident, $($derives:ident,)*]
 267      @type         [$type:ident]
 268      @debug_format [$debug_format:tt]) => (
 269         $crate::newtype_index!(
 270             @handle_debug
 271             @derives      [$($derives,)*]
 272             @type         [$type]
 273             @debug_format [$debug_format]);
 274     );
 275
 276     // Append comma to end of derives list if it's missing
 277     (@attrs        [$(#[$attrs:meta])*]
 278      @type         [$type:ident]
 279      @max          [$max:expr]
 280      @vis          [$v:vis]
 281      @debug_format [$debug_format:tt]
 282                    derive [$($derives:ident),*]
 283                    $($tokens:tt)*) => (
 284         $crate::newtype_index!(
 285             @attrs        [$(#[$attrs])*]
 286             @type         [$type]
 287             @max          [$max]
 288             @vis          [$v]
 289             @debug_format [$debug_format]
 290                           derive [$($derives,)*]
 291                           $($tokens)*);
 292     );
 293
 294     // By not including the @derives marker in this list nor in the default args, we can force it
 295     // to come first if it exists. When encodable is custom, just use the derives list as-is.
 296     (@attrs        [$(#[$attrs:meta])*]
 297      @type         [$type:ident]
 298      @max          [$max:expr]
 299      @vis          [$v:vis]
 300      @debug_format [$debug_format:tt]
 301                    derive [$($derives:ident,)+]
 302                    ENCODABLE = custom
 303                    $($tokens:tt)*) => (
 304         $crate::newtype_index!(
 305             @attrs        [$(#[$attrs])*]
 306             @derives      [$($derives,)+]
 307             @type         [$type]
 308             @max          [$max]
 309             @vis          [$v]
 310             @debug_format [$debug_format]
 311                           $($tokens)*);
 312     );
 313
 314     // By not including the @derives marker in this list nor in the default args, we can force it
 315     // to come first if it exists. When encodable isn't custom, add serialization traits by default.
 316     (@attrs        [$(#[$attrs:meta])*]
 317      @type         [$type:ident]
 318      @max          [$max:expr]
 319      @vis          [$v:vis]
 320      @debug_format [$debug_format:tt]
 321                    derive [$($derives:ident,)+]
 322                    $($tokens:tt)*) => (
 323         $crate::newtype_index!(
 324             @derives      [$($derives,)+]
 325             @attrs        [$(#[$attrs])*]
 326             @type         [$type]
 327             @max          [$max]
 328             @vis          [$v]
 329             @debug_format [$debug_format]
 330                           $($tokens)*);
 331         $crate::newtype_index!(@serializable $type);
 332     );
 333
 334     // The case where no derives are added, but encodable is overridden. Don't
 335     // derive serialization traits
 336     (@attrs        [$(#[$attrs:meta])*]
 337      @type         [$type:ident]
 338      @max          [$max:expr]
 339      @vis          [$v:vis]
 340      @debug_format [$debug_format:tt]
 341                    ENCODABLE = custom
 342                    $($tokens:tt)*) => (
 343         $crate::newtype_index!(
 344             @derives      []
 345             @attrs        [$(#[$attrs])*]
 346             @type         [$type]
 347             @max          [$max]
 348             @vis          [$v]
 349             @debug_format [$debug_format]
 350                           $($tokens)*);
 351     );
 352
 353     // The case where no derives are added, add serialization derives by default
 354     (@attrs        [$(#[$attrs:meta])*]
 355      @type         [$type:ident]
 356      @max          [$max:expr]
 357      @vis          [$v:vis]
 358      @debug_format [$debug_format:tt]
 359                    $($tokens:tt)*) => (
 360         $crate::newtype_index!(
 361             @derives      []
 362             @attrs        [$(#[$attrs])*]
 363             @type         [$type]
 364             @max          [$max]
 365             @vis          [$v]
 366             @debug_format [$debug_format]
 367                           $($tokens)*);
 368         $crate::newtype_index!(@serializable $type);
 369     );
 370
 371     (@serializable $type:ident) => (
 372         impl<D: ::rustc_serialize::Decoder> ::rustc_serialize::Decodable<D> for $type {
 373             fn decode(d: &mut D) -> Result<Self, D::Error> {
 374                 d.read_u32().map(Self::from_u32)
 375             }
 376         }
 377         impl<E: ::rustc_serialize::Encoder> ::rustc_serialize::Encodable<E> for $type {
 378             fn encode(&self, e: &mut E) -> Result<(), E::Error> {
 379                 e.emit_u32(self.private)
 380             }
 381         }
 382     );
 383
 384     // Rewrite final without comma to one that includes comma
 385     (@derives      [$($derives:ident,)*]
 386      @attrs        [$(#[$attrs:meta])*]
 387      @type         [$type:ident]
 388      @max          [$max:expr]
 389      @vis          [$v:vis]
 390      @debug_format [$debug_format:tt]
 391                    $name:ident = $constant:expr) => (
 392         $crate::newtype_index!(
 393             @derives      [$($derives,)*]
 394             @attrs        [$(#[$attrs])*]
 395             @type         [$type]
 396             @max          [$max]
 397             @vis          [$v]
 398             @debug_format [$debug_format]
 399                           $name = $constant,);
 400     );
 401
 402     // Rewrite final const without comma to one that includes comma
 403     (@derives      [$($derives:ident,)*]
 404      @attrs        [$(#[$attrs:meta])*]
 405      @type         [$type:ident]
 406      @max          [$max:expr]
 407      @vis          [$v:vis]
 408      @debug_format [$debug_format:tt]
 409                    $(#[doc = $doc:expr])*
 410                    const $name:ident = $constant:expr) => (
 411         $crate::newtype_index!(
 412             @derives      [$($derives,)*]
 413             @attrs        [$(#[$attrs])*]
 414             @type         [$type]
 415             @max          [$max]
 416             @vis          [$v]
 417             @debug_format [$debug_format]
 418                           $(#[doc = $doc])* const $name = $constant,);
 419     );
 420
 421     // Replace existing default for max
 422     (@derives      [$($derives:ident,)*]
 423      @attrs        [$(#[$attrs:meta])*]
 424      @type         [$type:ident]
 425      @max          [$_max:expr]
 426      @vis          [$v:vis]
 427      @debug_format [$debug_format:tt]
 428                    MAX = $max:expr,
 429                    $($tokens:tt)*) => (
 430         $crate::newtype_index!(
 431             @derives      [$($derives,)*]
 432             @attrs        [$(#[$attrs])*]
 433             @type         [$type]
 434             @max          [$max]
 435             @vis          [$v]
 436             @debug_format [$debug_format]
 437                           $($tokens)*);
 438     );
 439
 440     // Replace existing default for debug_format
 441     (@derives      [$($derives:ident,)*]
 442      @attrs        [$(#[$attrs:meta])*]
 443      @type         [$type:ident]
 444      @max          [$max:expr]
 445      @vis          [$v:vis]
 446      @debug_format [$_debug_format:tt]
 447                    DEBUG_FORMAT = $debug_format:tt,
 448                    $($tokens:tt)*) => (
 449         $crate::newtype_index!(
 450             @derives      [$($derives,)*]
 451             @attrs        [$(#[$attrs])*]
 452             @type         [$type]
 453             @max          [$max]
 454             @vis          [$v]
 455             @debug_format [$debug_format]
 456                           $($tokens)*);
 457     );
 458
 459     // Assign a user-defined constant
 460     (@derives      [$($derives:ident,)*]
 461      @attrs        [$(#[$attrs:meta])*]
 462      @type         [$type:ident]
 463      @max          [$max:expr]
 464      @vis          [$v:vis]
 465      @debug_format [$debug_format:tt]
 466                    $(#[doc = $doc:expr])*
 467                    const $name:ident = $constant:expr,
 468                    $($tokens:tt)*) => (
 469         $(#[doc = $doc])*
 470         $v const $name: $type = $type::from_u32($constant);
 471         $crate::newtype_index!(
 472             @derives      [$($derives,)*]
 473             @attrs        [$(#[$attrs])*]
 474             @type         [$type]
 475             @max          [$max]
 476             @vis          [$v]
 477             @debug_format [$debug_format]
 478                           $($tokens)*);
 479     );
 480 }
 481
 482 #[derive(Clone, PartialEq, Eq, Hash)]
 483 pub struct IndexVec<I: Idx, T> {
 484     pub raw: Vec<T>,
 485     _marker: PhantomData<fn(&I)>,
 486 }
 487
 488 // Whether `IndexVec` is `Send` depends only on the data,
 489 // not the phantom data.
 490 unsafe impl<I: Idx, T> Send for IndexVec<I, T> where T: Send {}
 491
 492 impl<S: Encoder, I: Idx, T: Encodable<S>> Encodable<S> for IndexVec<I, T> {
 493     fn encode(&self, s: &mut S) -> Result<(), S::Error> {
 494         Encodable::encode(&self.raw, s)
 495     }
 496 }
 497
 498 impl<S: Encoder, I: Idx, T: Encodable<S>> Encodable<S> for &IndexVec<I, T> {
 499     fn encode(&self, s: &mut S) -> Result<(), S::Error> {
 500         Encodable::encode(&self.raw, s)
 501     }
 502 }
 503
 504 impl<D: Decoder, I: Idx, T: Decodable<D>> Decodable<D> for IndexVec<I, T> {
 505     fn decode(d: &mut D) -> Result<Self, D::Error> {
 506         Decodable::decode(d).map(|v| IndexVec { raw: v, _marker: PhantomData })
 507     }
 508 }
 509
 510 impl<I: Idx, T: fmt::Debug> fmt::Debug for IndexVec<I, T> {
 511     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
 512         fmt::Debug::fmt(&self.raw, fmt)
 513     }
 514 }
 515
 516 pub type Enumerated<I, J> = iter::Map<iter::Enumerate<J>, IntoIdx<I>>;
 517
 518 impl<I: Idx, T> IndexVec<I, T> {
 519     #[inline]
 520     pub fn new() -> Self {
 521         IndexVec { raw: Vec::new(), _marker: PhantomData }
 522     }
 523
 524     #[inline]
 525     pub fn from_raw(raw: Vec<T>) -> Self {
 526         IndexVec { raw, _marker: PhantomData }
 527     }
 528
 529     #[inline]
 530     pub fn with_capacity(capacity: usize) -> Self {
 531         IndexVec { raw: Vec::with_capacity(capacity), _marker: PhantomData }
 532     }
 533
 534     #[inline]
 535     pub fn from_elem<S>(elem: T, universe: &IndexVec<I, S>) -> Self
 536     where
 537         T: Clone,
 538     {
 539         IndexVec { raw: vec![elem; universe.len()], _marker: PhantomData }
 540     }
 541
 542     #[inline]
 543     pub fn from_elem_n(elem: T, n: usize) -> Self
 544     where
 545         T: Clone,
 546     {
 547         IndexVec { raw: vec![elem; n], _marker: PhantomData }
 548     }
 549
 550     /// Create an `IndexVec` with `n` elements, where the value of each
 551     /// element is the result of `func(i)`. (The underlying vector will
 552     /// be allocated only once, with a capacity of at least `n`.)
 553     #[inline]
 554     pub fn from_fn_n(func: impl FnMut(I) -> T, n: usize) -> Self {
 555         let indices = (0..n).map(I::new);
 556         Self::from_raw(indices.map(func).collect())
 557     }
 558
 559     #[inline]
 560     pub fn push(&mut self, d: T) -> I {
 561         let idx = I::new(self.len());
 562         self.raw.push(d);
 563         idx
 564     }
 565
 566     #[inline]
 567     pub fn pop(&mut self) -> Option<T> {
 568         self.raw.pop()
 569     }
 570
 571     #[inline]
 572     pub fn len(&self) -> usize {
 573         self.raw.len()
 574     }
 575
 576     /// Gives the next index that will be assigned when `push` is
 577     /// called.
 578     #[inline]
 579     pub fn next_index(&self) -> I {
 580         I::new(self.len())
 581     }
 582
 583     #[inline]
 584     pub fn is_empty(&self) -> bool {
 585         self.raw.is_empty()
 586     }
 587
 588     #[inline]
 589     pub fn into_iter(self) -> vec::IntoIter<T> {
 590         self.raw.into_iter()
 591     }
 592
 593     #[inline]
 594     pub fn into_iter_enumerated(self) -> Enumerated<I, vec::IntoIter<T>> {
 595         self.raw.into_iter().enumerate().map(IntoIdx { _marker: PhantomData })
 596     }
 597
 598     #[inline]
 599     pub fn iter(&self) -> slice::Iter<'_, T> {
 600         self.raw.iter()
 601     }
 602
 603     #[inline]
 604     pub fn iter_enumerated(&self) -> Enumerated<I, slice::Iter<'_, T>> {
 605         self.raw.iter().enumerate().map(IntoIdx { _marker: PhantomData })
 606     }
 607
 608     #[inline]
 609     pub fn indices(&self) -> iter::Map<Range<usize>, IntoIdx<I>> {
 610         (0..self.len()).map(IntoIdx { _marker: PhantomData })
 611     }
 612
 613     #[inline]
 614     pub fn iter_mut(&mut self) -> slice::IterMut<'_, T> {
 615         self.raw.iter_mut()
 616     }
 617
 618     #[inline]
 619     pub fn iter_enumerated_mut(&mut self) -> Enumerated<I, slice::IterMut<'_, T>> {
 620         self.raw.iter_mut().enumerate().map(IntoIdx { _marker: PhantomData })
 621     }
 622
 623     #[inline]
 624     pub fn drain<'a, R: RangeBounds<usize>>(
 625         &'a mut self,
 626         range: R,
 627     ) -> impl Iterator<Item = T> + 'a {
 628         self.raw.drain(range)
 629     }
 630
 631     #[inline]
 632     pub fn drain_enumerated<'a, R: RangeBounds<usize>>(
 633         &'a mut self,
 634         range: R,
 635     ) -> impl Iterator<Item = (I, T)> + 'a {
 636         self.raw.drain(range).enumerate().map(IntoIdx { _marker: PhantomData })
 637     }
 638
 639     #[inline]
 640     pub fn last(&self) -> Option<I> {
 641         self.len().checked_sub(1).map(I::new)
 642     }
 643
 644     #[inline]
 645     pub fn shrink_to_fit(&mut self) {
 646         self.raw.shrink_to_fit()
 647     }
 648
 649     #[inline]
 650     pub fn swap(&mut self, a: I, b: I) {
 651         self.raw.swap(a.index(), b.index())
 652     }
 653
 654     #[inline]
 655     pub fn truncate(&mut self, a: usize) {
 656         self.raw.truncate(a)
 657     }
 658
 659     #[inline]
 660     pub fn get(&self, index: I) -> Option<&T> {
 661         self.raw.get(index.index())
 662     }
 663
 664     #[inline]
 665     pub fn get_mut(&mut self, index: I) -> Option<&mut T> {
 666         self.raw.get_mut(index.index())
 667     }
 668
 669     /// Returns mutable references to two distinct elements, a and b. Panics if a == b.
 670     #[inline]
 671     pub fn pick2_mut(&mut self, a: I, b: I) -> (&mut T, &mut T) {
 672         let (ai, bi) = (a.index(), b.index());
 673         assert!(ai != bi);
 674
 675         if ai < bi {
 676             let (c1, c2) = self.raw.split_at_mut(bi);
 677             (&mut c1[ai], &mut c2[0])
 678         } else {
 679             let (c2, c1) = self.pick2_mut(b, a);
 680             (c1, c2)
 681         }
 682     }
 683
 684     /// Returns mutable references to three distinct elements or panics otherwise.
 685     #[inline]
 686     pub fn pick3_mut(&mut self, a: I, b: I, c: I) -> (&mut T, &mut T, &mut T) {
 687         let (ai, bi, ci) = (a.index(), b.index(), c.index());
 688         assert!(ai != bi && bi != ci && ci != ai);
 689         let len = self.raw.len();
 690         assert!(ai < len && bi < len && ci < len);
 691         let ptr = self.raw.as_mut_ptr();
 692         unsafe { (&mut *ptr.add(ai), &mut *ptr.add(bi), &mut *ptr.add(ci)) }
 693     }
 694
 695     pub fn convert_index_type<Ix: Idx>(self) -> IndexVec<Ix, T> {
 696         IndexVec { raw: self.raw, _marker: PhantomData }
 697     }
 698
 699     /// Grows the index vector so that it contains an entry for
 700     /// `elem`; if that is already true, then has no
 701     /// effect. Otherwise, inserts new values as needed by invoking
 702     /// `fill_value`.
 703     #[inline]
 704     pub fn ensure_contains_elem(&mut self, elem: I, fill_value: impl FnMut() -> T) {
 705         let min_new_len = elem.index() + 1;
 706         if self.len() < min_new_len {
 707             self.raw.resize_with(min_new_len, fill_value);
 708         }
 709     }
 710
 711     #[inline]
 712     pub fn resize_to_elem(&mut self, elem: I, fill_value: impl FnMut() -> T) {
 713         let min_new_len = elem.index() + 1;
 714         self.raw.resize_with(min_new_len, fill_value);
 715     }
 716 }
 717
 718 impl<I: Idx, T: Clone> IndexVec<I, T> {
 719     #[inline]
 720     pub fn resize(&mut self, new_len: usize, value: T) {
 721         self.raw.resize(new_len, value)
 722     }
 723 }
 724
 725 impl<I: Idx, T: Ord> IndexVec<I, T> {
 726     #[inline]
 727     pub fn binary_search(&self, value: &T) -> Result<I, I> {
 728         match self.raw.binary_search(value) {
 729             Ok(i) => Ok(Idx::new(i)),
 730             Err(i) => Err(Idx::new(i)),
 731         }
 732     }
 733 }
 734
 735 impl<I: Idx, T> Index<I> for IndexVec<I, T> {
 736     type Output = T;
 737
 738     #[inline]
 739     fn index(&self, index: I) -> &T {
 740         &self.raw[index.index()]
 741     }
 742 }
 743
 744 impl<I: Idx, T> IndexMut<I> for IndexVec<I, T> {
 745     #[inline]
 746     fn index_mut(&mut self, index: I) -> &mut T {
 747         &mut self.raw[index.index()]
 748     }
 749 }
 750
 751 impl<I: Idx, T> Default for IndexVec<I, T> {
 752     #[inline]
 753     fn default() -> Self {
 754         Self::new()
 755     }
 756 }
 757
 758 impl<I: Idx, T> Extend<T> for IndexVec<I, T> {
 759     #[inline]
 760     fn extend<J: IntoIterator<Item = T>>(&mut self, iter: J) {
 761         self.raw.extend(iter);
 762     }
 763
 764     #[inline]
 765     fn extend_one(&mut self, item: T) {
 766         self.raw.push(item);
 767     }
 768
 769     #[inline]
 770     fn extend_reserve(&mut self, additional: usize) {
 771         self.raw.reserve(additional);
 772     }
 773 }
 774
 775 impl<I: Idx, T> FromIterator<T> for IndexVec<I, T> {
 776     #[inline]
 777     fn from_iter<J>(iter: J) -> Self
 778     where
 779         J: IntoIterator<Item = T>,
 780     {
 781         IndexVec { raw: FromIterator::from_iter(iter), _marker: PhantomData }
 782     }
 783 }
 784
 785 impl<I: Idx, T> IntoIterator for IndexVec<I, T> {
 786     type Item = T;
 787     type IntoIter = vec::IntoIter<T>;
 788
 789     #[inline]
 790     fn into_iter(self) -> vec::IntoIter<T> {
 791         self.raw.into_iter()
 792     }
 793 }
 794
 795 impl<'a, I: Idx, T> IntoIterator for &'a IndexVec<I, T> {
 796     type Item = &'a T;
 797     type IntoIter = slice::Iter<'a, T>;
 798
 799     #[inline]
 800     fn into_iter(self) -> slice::Iter<'a, T> {
 801         self.raw.iter()
 802     }
 803 }
 804
 805 impl<'a, I: Idx, T> IntoIterator for &'a mut IndexVec<I, T> {
 806     type Item = &'a mut T;
 807     type IntoIter = slice::IterMut<'a, T>;
 808
 809     #[inline]
 810     fn into_iter(self) -> slice::IterMut<'a, T> {
 811         self.raw.iter_mut()
 812     }
 813 }
 814
 815 pub struct IntoIdx<I: Idx> {
 816     _marker: PhantomData<fn(&I)>,
 817 }
 818 impl<I: Idx, T> FnOnce<((usize, T),)> for IntoIdx<I> {
 819     type Output = (I, T);
 820
 821     extern "rust-call" fn call_once(self, ((n, t),): ((usize, T),)) -> Self::Output {
 822         (I::new(n), t)
 823     }
 824 }
 825
 826 impl<I: Idx, T> FnMut<((usize, T),)> for IntoIdx<I> {
 827     extern "rust-call" fn call_mut(&mut self, ((n, t),): ((usize, T),)) -> Self::Output {
 828         (I::new(n), t)
 829     }
 830 }
 831
 832 impl<I: Idx> FnOnce<(usize,)> for IntoIdx<I> {
 833     type Output = I;
 834
 835     extern "rust-call" fn call_once(self, (n,): (usize,)) -> Self::Output {
 836         I::new(n)
 837     }
 838 }
 839
 840 impl<I: Idx> FnMut<(usize,)> for IntoIdx<I> {
 841     extern "rust-call" fn call_mut(&mut self, (n,): (usize,)) -> Self::Output {
 842         I::new(n)
 843     }
 844 }
 845
 846 #[cfg(test)]
 847 mod tests;