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