2 use std
::iter
::{self, FromIterator}
;
4 use std
::marker
::PhantomData
;
5 use std
::ops
::{Index, IndexMut, Range, RangeBounds}
;
11 use rustc_serialize
as serialize
;
13 /// Represents some newtyped `usize` wrapper.
15 /// Purpose: avoid mixing indexes for different bitvector domains.
16 pub trait Idx
: Copy
+ '
static + Ord
+ Debug
+ Hash
{
17 fn new(idx
: usize) -> Self;
19 fn index(self) -> usize;
21 fn increment_by(&mut self, amount
: usize) {
22 let v
= self.index() + amount
;
29 fn new(idx
: usize) -> Self { idx }
31 fn index(self) -> usize { self }
36 fn new(idx
: usize) -> Self { assert!(idx <= u32::MAX as usize); idx as u32 }
38 fn index(self) -> usize { self as usize }
41 /// Creates a struct type `S` that can be used as an index with
42 /// `IndexVec` and so on.
44 /// There are two ways of interacting with these indices:
46 /// - The `From` impls are the preferred way. So you can do
47 /// `S::from(v)` with a `usize` or `u32`. And you can convert back
48 /// to an integer with `u32::from(s)`.
50 /// - Alternatively, you can use the methods `S::new(v)` and `s.index()`
51 /// to create/return a value.
53 /// Internally, the index uses a u32, so the index must not exceed
54 /// `u32::MAX`. You can also customize things like the `Debug` impl,
55 /// what traits are derived, and so forth via the macro.
57 macro_rules
! newtype_index
{
58 // ---- public rules ----
60 // Use default constants
61 ($
(#[$attrs:meta])* $v:vis struct $name:ident { .. }) => (
63 // Leave out derives marker so we can use its absence to ensure it comes first
64 @attrs
[$
(#[$attrs])*]
66 // shave off 256 indices at the end to allow space for packing these indices into enums
69 @debug_format
["{}"]);
72 // Define any constants
73 ($
(#[$attrs:meta])* $v:vis struct $name:ident { $($tokens:tt)+ }) => (
75 // Leave out derives marker so we can use its absence to ensure it comes first
76 @attrs
[$
(#[$attrs])*]
78 // shave off 256 indices at the end to allow space for packing these indices into enums
85 // ---- private rules ----
87 // Base case, user-defined constants (if any) have already been defined
88 (@derives
[$
($derives
:ident
,)*]
89 @attrs
[$
(#[$attrs:meta])*]
93 @debug_format
[$debug_format
:tt
]) => (
95 #[derive(Copy, PartialEq, Eq, Hash, PartialOrd, Ord, $($derives),*)]
96 #[rustc_layout_scalar_valid_range_end($max)]
101 impl Clone
for $
type {
102 fn clone(&self) -> Self {
108 $v
const MAX_AS_U32
: u32 = $max
;
110 $v
const MAX
: $
type = $
type::from_u32_const($max
);
113 $v
fn from_usize(value
: usize) -> Self {
114 assert
!(value
<= ($max
as usize));
116 $
type::from_u32_unchecked(value
as u32)
121 $v
fn from_u32(value
: u32) -> Self {
122 assert
!(value
<= $max
);
124 $
type::from_u32_unchecked(value
)
128 /// Hacky variant of `from_u32` for use in constants.
129 /// This version checks the "max" constraint by using an
130 /// invalid array dereference.
132 $v
const fn from_u32_const(value
: u32) -> Self {
133 // This will fail at const eval time unless `value <=
134 // max` is true (in which case we get the index 0).
135 // It will also fail at runtime, of course, but in a
136 // kind of wacky way.
137 let _
= ["out of range value used"][
138 !(value
<= $max
) as usize
142 $
type { private: value }
147 $v
const unsafe fn from_u32_unchecked(value
: u32) -> Self {
148 unsafe { $type { private: value }
}
151 /// Extracts the value of this index as an integer.
153 $v
fn index(self) -> usize {
157 /// Extracts the value of this index as a `u32`.
159 $v
fn as_u32(self) -> u32 {
163 /// Extracts the value of this index as a `usize`.
165 $v
fn as_usize(self) -> usize {
166 self.as_u32() as usize
172 fn new(value
: usize) -> Self {
177 fn index(self) -> usize {
182 impl ::std
::iter
::Step
for $
type {
184 fn steps_between(start
: &Self, end
: &Self) -> Option
<usize> {
185 <usize as ::std
::iter
::Step
>::steps_between(
192 fn replace_one(&mut self) -> Self {
193 ::std
::mem
::replace(self, Self::new(1))
197 fn replace_zero(&mut self) -> Self {
198 ::std
::mem
::replace(self, Self::new(0))
202 fn add_one(&self) -> Self {
203 Self::new(Idx
::index(*self) + 1)
207 fn sub_one(&self) -> Self {
208 Self::new(Idx
::index(*self) - 1)
212 fn add_usize(&self, u
: usize) -> Option
<Self> {
213 Idx
::index(*self).checked_add(u
).map(Self::new
)
217 impl From
<$
type> for u32 {
219 fn from(v
: $
type) -> u32 {
224 impl From
<$
type> for usize {
226 fn from(v
: $
type) -> usize {
231 impl From
<usize> for $
type {
233 fn from(value
: usize) -> Self {
234 $
type::from_usize(value
)
238 impl From
<u32> for $
type {
240 fn from(value
: u32) -> Self {
241 $
type::from_u32(value
)
247 @derives
[$
($derives
,)*]
249 @debug_format
[$debug_format
]);
252 // base case for handle_debug where format is custom. No Debug implementation is emitted.
254 @derives
[$
($_derives
:ident
,)*]
256 @debug_format
[custom
]) => ();
258 // base case for handle_debug, no debug overrides found, so use default
262 @debug_format
[$debug_format
:tt
]) => (
263 impl ::std
::fmt
::Debug
for $
type {
264 fn fmt(&self, fmt
: &mut ::std
::fmt
::Formatter
<'_
>) -> ::std
::fmt
::Result
{
265 write
!(fmt
, $debug_format
, self.as_u32())
270 // Debug is requested for derive, don't generate any Debug implementation.
272 @derives
[Debug
, $
($derives
:ident
,)*]
274 @debug_format
[$debug_format
:tt
]) => ();
276 // It's not Debug, so just pop it off the front of the derives stack and check the rest.
278 @derives
[$_derive
:ident
, $
($derives
:ident
,)*]
280 @debug_format
[$debug_format
:tt
]) => (
283 @derives
[$
($derives
,)*]
285 @debug_format
[$debug_format
]);
288 // Append comma to end of derives list if it's missing
289 (@attrs
[$
(#[$attrs:meta])*]
293 @debug_format
[$debug_format
:tt
]
294 derive
[$
($derives
:ident
),*]
297 @attrs
[$
(#[$attrs])*]
301 @debug_format
[$debug_format
]
302 derive
[$
($derives
,)*]
306 // By not including the @derives marker in this list nor in the default args, we can force it
307 // to come first if it exists. When encodable is custom, just use the derives list as-is.
308 (@attrs
[$
(#[$attrs:meta])*]
312 @debug_format
[$debug_format
:tt
]
313 derive
[$
($derives
:ident
,)+]
317 @attrs
[$
(#[$attrs])*]
318 @derives
[$
($derives
,)+]
322 @debug_format
[$debug_format
]
326 // By not including the @derives marker in this list nor in the default args, we can force it
327 // to come first if it exists. When encodable isn't custom, add serialization traits by default.
328 (@attrs
[$
(#[$attrs:meta])*]
332 @debug_format
[$debug_format
:tt
]
333 derive
[$
($derives
:ident
,)+]
336 @derives
[$
($derives
,)+ RustcEncodable
,]
337 @attrs
[$
(#[$attrs])*]
341 @debug_format
[$debug_format
]
343 newtype_index
!(@decodable $
type);
346 // The case where no derives are added, but encodable is overridden. Don't
347 // derive serialization traits
348 (@attrs
[$
(#[$attrs:meta])*]
352 @debug_format
[$debug_format
:tt
]
357 @attrs
[$
(#[$attrs])*]
361 @debug_format
[$debug_format
]
365 // The case where no derives are added, add serialization derives by default
366 (@attrs
[$
(#[$attrs:meta])*]
370 @debug_format
[$debug_format
:tt
]
373 @derives
[RustcEncodable
,]
374 @attrs
[$
(#[$attrs])*]
378 @debug_format
[$debug_format
]
380 newtype_index
!(@decodable $
type);
383 (@decodable $
type:ident
) => (
385 fn __decodable__impl__hack() {
386 mod __more_hacks_because__self_doesnt_work_in_functions
{
387 extern crate serialize
;
388 use self::serialize
::{Decodable, Decoder}
;
389 impl Decodable
for super::$
type {
390 fn decode
<D
: Decoder
>(d
: &mut D
) -> Result
<Self, D
::Error
> {
391 d
.read_u32().map(Self::from
)
399 // Rewrite final without comma to one that includes comma
400 (@derives
[$
($derives
:ident
,)*]
401 @attrs
[$
(#[$attrs:meta])*]
405 @debug_format
[$debug_format
:tt
]
406 $name
:ident
= $constant
:expr
) => (
408 @derives
[$
($derives
,)*]
409 @attrs
[$
(#[$attrs])*]
413 @debug_format
[$debug_format
]
417 // Rewrite final const without comma to one that includes comma
418 (@derives
[$
($derives
:ident
,)*]
419 @attrs
[$
(#[$attrs:meta])*]
423 @debug_format
[$debug_format
:tt
]
424 $
(#[doc = $doc:expr])*
425 const $name
:ident
= $constant
:expr
) => (
427 @derives
[$
($derives
,)*]
428 @attrs
[$
(#[$attrs])*]
432 @debug_format
[$debug_format
]
433 $
(#[doc = $doc])* const $name = $constant,);
436 // Replace existing default for max
437 (@derives
[$
($derives
:ident
,)*]
438 @attrs
[$
(#[$attrs:meta])*]
442 @debug_format
[$debug_format
:tt
]
446 @derives
[$
($derives
,)*]
447 @attrs
[$
(#[$attrs])*]
451 @debug_format
[$debug_format
]
455 // Replace existing default for debug_format
456 (@derives
[$
($derives
:ident
,)*]
457 @attrs
[$
(#[$attrs:meta])*]
461 @debug_format
[$_debug_format
:tt
]
462 DEBUG_FORMAT
= $debug_format
:tt
,
465 @derives
[$
($derives
,)*]
466 @attrs
[$
(#[$attrs])*]
470 @debug_format
[$debug_format
]
474 // Assign a user-defined constant
475 (@derives
[$
($derives
:ident
,)*]
476 @attrs
[$
(#[$attrs:meta])*]
480 @debug_format
[$debug_format
:tt
]
481 $
(#[doc = $doc:expr])*
482 const $name
:ident
= $constant
:expr
,
485 pub const $name
: $
type = $
type::from_u32_const($constant
);
487 @derives
[$
($derives
,)*]
488 @attrs
[$
(#[$attrs])*]
492 @debug_format
[$debug_format
]
497 #[derive(Clone, PartialEq, Eq, Hash)]
498 pub struct IndexVec
<I
: Idx
, T
> {
500 _marker
: PhantomData
<fn(&I
)>
503 // Whether `IndexVec` is `Send` depends only on the data,
504 // not the phantom data.
505 unsafe impl<I
: Idx
, T
> Send
for IndexVec
<I
, T
> where T
: Send {}
507 impl<I
: Idx
, T
: serialize
::Encodable
> serialize
::Encodable
for IndexVec
<I
, T
> {
508 fn encode
<S
: serialize
::Encoder
>(&self, s
: &mut S
) -> Result
<(), S
::Error
> {
509 serialize
::Encodable
::encode(&self.raw
, s
)
513 impl<I
: Idx
, T
: serialize
::Decodable
> serialize
::Decodable
for IndexVec
<I
, T
> {
514 fn decode
<D
: serialize
::Decoder
>(d
: &mut D
) -> Result
<Self, D
::Error
> {
515 serialize
::Decodable
::decode(d
).map(|v
| {
516 IndexVec { raw: v, _marker: PhantomData }
521 impl<I
: Idx
, T
: fmt
::Debug
> fmt
::Debug
for IndexVec
<I
, T
> {
522 fn fmt(&self, fmt
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
523 fmt
::Debug
::fmt(&self.raw
, fmt
)
527 pub type Enumerated
<I
, J
> = iter
::Map
<iter
::Enumerate
<J
>, IntoIdx
<I
>>;
529 impl<I
: Idx
, T
> IndexVec
<I
, T
> {
531 pub fn new() -> Self {
532 IndexVec { raw: Vec::new(), _marker: PhantomData }
536 pub fn from_raw(raw
: Vec
<T
>) -> Self {
537 IndexVec { raw, _marker: PhantomData }
541 pub fn with_capacity(capacity
: usize) -> Self {
542 IndexVec { raw: Vec::with_capacity(capacity), _marker: PhantomData }
546 pub fn from_elem
<S
>(elem
: T
, universe
: &IndexVec
<I
, S
>) -> Self
549 IndexVec { raw: vec![elem; universe.len()], _marker: PhantomData }
553 pub fn from_elem_n(elem
: T
, n
: usize) -> Self
556 IndexVec { raw: vec![elem; n], _marker: PhantomData }
560 pub fn push(&mut self, d
: T
) -> I
{
561 let idx
= I
::new(self.len());
567 pub fn pop(&mut self) -> Option
<T
> {
572 pub fn len(&self) -> usize {
576 /// Gives the next index that will be assigned when `push` is
579 pub fn next_index(&self) -> I
{
584 pub fn is_empty(&self) -> bool
{
589 pub fn into_iter(self) -> vec
::IntoIter
<T
> {
594 pub fn into_iter_enumerated(self) -> Enumerated
<I
, vec
::IntoIter
<T
>>
596 self.raw
.into_iter().enumerate().map(IntoIdx { _marker: PhantomData }
)
600 pub fn iter(&self) -> slice
::Iter
<'_
, T
> {
605 pub fn iter_enumerated(&self) -> Enumerated
<I
, slice
::Iter
<'_
, T
>>
607 self.raw
.iter().enumerate().map(IntoIdx { _marker: PhantomData }
)
611 pub fn indices(&self) -> iter
::Map
<Range
<usize>, IntoIdx
<I
>> {
612 (0..self.len()).map(IntoIdx { _marker: PhantomData }
)
616 pub fn iter_mut(&mut self) -> slice
::IterMut
<'_
, T
> {
621 pub fn iter_enumerated_mut(&mut self) -> Enumerated
<I
, slice
::IterMut
<'_
, T
>>
623 self.raw
.iter_mut().enumerate().map(IntoIdx { _marker: PhantomData }
)
627 pub fn drain
<'a
, R
: RangeBounds
<usize>>(
628 &'a
mut self, range
: R
) -> impl Iterator
<Item
=T
> + 'a
{
629 self.raw
.drain(range
)
633 pub fn drain_enumerated
<'a
, R
: RangeBounds
<usize>>(
634 &'a
mut self, range
: R
) -> impl Iterator
<Item
=(I
, T
)> + 'a
{
635 self.raw
.drain(range
).enumerate().map(IntoIdx { _marker: PhantomData }
)
639 pub fn last(&self) -> Option
<I
> {
640 self.len().checked_sub(1).map(I
::new
)
644 pub fn shrink_to_fit(&mut self) {
645 self.raw
.shrink_to_fit()
649 pub fn swap(&mut self, a
: I
, b
: I
) {
650 self.raw
.swap(a
.index(), b
.index())
654 pub fn truncate(&mut self, a
: usize) {
659 pub fn get(&self, index
: I
) -> Option
<&T
> {
660 self.raw
.get(index
.index())
664 pub fn get_mut(&mut self, index
: I
) -> Option
<&mut T
> {
665 self.raw
.get_mut(index
.index())
668 /// Returns mutable references to two distinct elements, a and b. Panics if a == b.
670 pub fn pick2_mut(&mut self, a
: I
, b
: I
) -> (&mut T
, &mut T
) {
671 let (ai
, bi
) = (a
.index(), b
.index());
675 let (c1
, c2
) = self.raw
.split_at_mut(bi
);
676 (&mut c1
[ai
], &mut c2
[0])
678 let (c2
, c1
) = self.pick2_mut(b
, a
);
683 pub fn convert_index_type
<Ix
: Idx
>(self) -> IndexVec
<Ix
, T
> {
686 _marker
: PhantomData
,
691 impl<I
: Idx
, T
: Clone
> IndexVec
<I
, T
> {
692 /// Grows the index vector so that it contains an entry for
693 /// `elem`; if that is already true, then has no
694 /// effect. Otherwise, inserts new values as needed by invoking
697 pub fn ensure_contains_elem(&mut self, elem
: I
, fill_value
: impl FnMut() -> T
) {
698 let min_new_len
= elem
.index() + 1;
699 if self.len() < min_new_len
{
700 self.raw
.resize_with(min_new_len
, fill_value
);
705 pub fn resize(&mut self, new_len
: usize, value
: T
) {
706 self.raw
.resize(new_len
, value
)
710 pub fn resize_to_elem(&mut self, elem
: I
, fill_value
: impl FnMut() -> T
) {
711 let min_new_len
= elem
.index() + 1;
712 self.raw
.resize_with(min_new_len
, fill_value
);
716 impl<I
: Idx
, T
: Ord
> IndexVec
<I
, T
> {
718 pub fn binary_search(&self, value
: &T
) -> Result
<I
, I
> {
719 match self.raw
.binary_search(value
) {
720 Ok(i
) => Ok(Idx
::new(i
)),
721 Err(i
) => Err(Idx
::new(i
)),
726 impl<I
: Idx
, T
> Index
<I
> for IndexVec
<I
, T
> {
730 fn index(&self, index
: I
) -> &T
{
731 &self.raw
[index
.index()]
735 impl<I
: Idx
, T
> IndexMut
<I
> for IndexVec
<I
, T
> {
737 fn index_mut(&mut self, index
: I
) -> &mut T
{
738 &mut self.raw
[index
.index()]
742 impl<I
: Idx
, T
> Default
for IndexVec
<I
, T
> {
744 fn default() -> Self {
749 impl<I
: Idx
, T
> Extend
<T
> for IndexVec
<I
, T
> {
751 fn extend
<J
: IntoIterator
<Item
= T
>>(&mut self, iter
: J
) {
752 self.raw
.extend(iter
);
756 impl<I
: Idx
, T
> FromIterator
<T
> for IndexVec
<I
, T
> {
758 fn from_iter
<J
>(iter
: J
) -> Self where J
: IntoIterator
<Item
=T
> {
759 IndexVec { raw: FromIterator::from_iter(iter), _marker: PhantomData }
763 impl<I
: Idx
, T
> IntoIterator
for IndexVec
<I
, T
> {
765 type IntoIter
= vec
::IntoIter
<T
>;
768 fn into_iter(self) -> vec
::IntoIter
<T
> {
774 impl<'a
, I
: Idx
, T
> IntoIterator
for &'a IndexVec
<I
, T
> {
776 type IntoIter
= slice
::Iter
<'a
, T
>;
779 fn into_iter(self) -> slice
::Iter
<'a
, T
> {
784 impl<'a
, I
: Idx
, T
> IntoIterator
for &'a
mut IndexVec
<I
, T
> {
785 type Item
= &'a
mut T
;
786 type IntoIter
= slice
::IterMut
<'a
, T
>;
789 fn into_iter(self) -> slice
::IterMut
<'a
, T
> {
794 pub struct IntoIdx
<I
: Idx
> { _marker: PhantomData<fn(&I)> }
795 impl<I
: Idx
, T
> FnOnce
<((usize, T
),)> for IntoIdx
<I
> {
796 type Output
= (I
, T
);
798 extern "rust-call" fn call_once(self, ((n
, t
),): ((usize, T
),)) -> Self::Output
{
803 impl<I
: Idx
, T
> FnMut
<((usize, T
),)> for IntoIdx
<I
> {
804 extern "rust-call" fn call_mut(&mut self, ((n
, t
),): ((usize, T
),)) -> Self::Output
{
809 impl<I
: Idx
> FnOnce
<(usize,)> for IntoIdx
<I
> {
812 extern "rust-call" fn call_once(self, (n
,): (usize,)) -> Self::Output
{
817 impl<I
: Idx
> FnMut
<(usize,)> for IntoIdx
<I
> {
818 extern "rust-call" fn call_mut(&mut self, (n
,): (usize,)) -> Self::Output
{