src/librustc_index/vec.rs

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