1 use rustc_serialize
::{Decodable, Decoder, Encodable, Encoder}
;
6 use std
::iter
::{self, FromIterator}
;
7 use std
::marker
::PhantomData
;
8 use std
::ops
::{Index, IndexMut, Range, RangeBounds}
;
12 /// Represents some newtyped `usize` wrapper.
14 /// Purpose: avoid mixing indexes for different bitvector domains.
15 pub trait Idx
: Copy
+ '
static + Ord
+ Debug
+ Hash
{
16 fn new(idx
: usize) -> Self;
18 fn index(self) -> usize;
20 fn increment_by(&mut self, amount
: usize) {
21 *self = self.plus(amount
);
24 fn plus(self, amount
: usize) -> Self {
25 Self::new(self.index() + amount
)
31 fn new(idx
: usize) -> Self {
35 fn index(self) -> usize {
42 fn new(idx
: usize) -> Self {
43 assert
!(idx
<= u32::MAX
as usize);
47 fn index(self) -> usize {
52 /// Creates a struct type `S` that can be used as an index with
53 /// `IndexVec` and so on.
55 /// There are two ways of interacting with these indices:
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)`.
61 /// - Alternatively, you can use the methods `S::new(v)` and `s.index()`
62 /// to create/return a value.
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.
68 #[allow_internal_unstable(step_trait, rustc_attrs)]
69 macro_rules
! newtype_index
{
70 // ---- public rules ----
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])*]
78 // shave off 256 indices at the end to allow space for packing these indices into enums
81 @debug_format
["{}"]);
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])*]
90 // shave off 256 indices at the end to allow space for packing these indices into enums
97 // ---- private rules ----
99 // Base case, user-defined constants (if any) have already been defined
100 (@derives
[$
($derives
:ident
,)*]
101 @attrs
[$
(#[$attrs:meta])*]
105 @debug_format
[$debug_format
:tt
]) => (
107 #[derive(Copy, PartialEq, Eq, Hash, PartialOrd, Ord, $($derives),*)]
108 #[rustc_layout_scalar_valid_range_end($max)]
113 impl Clone
for $
type {
114 fn clone(&self) -> Self {
120 $v
const MAX_AS_U32
: u32 = $max
;
122 $v
const MAX
: Self = Self::from_u32($max
);
125 $v
const fn from_usize(value
: usize) -> Self {
126 assert
!(value
<= ($max
as usize));
128 Self::from_u32_unchecked(value
as u32)
133 $v
const fn from_u32(value
: u32) -> Self {
134 assert
!(value
<= $max
);
136 Self::from_u32_unchecked(value
)
141 $v
const unsafe fn from_u32_unchecked(value
: u32) -> Self {
142 Self { private: value }
145 /// Extracts the value of this index as an integer.
147 $v
const fn index(self) -> usize {
151 /// Extracts the value of this index as a `u32`.
153 $v
const fn as_u32(self) -> u32 {
157 /// Extracts the value of this index as a `usize`.
159 $v
const fn as_usize(self) -> usize {
160 self.as_u32() as usize
164 impl std
::ops
::Add
<usize> for $
type {
167 fn add(self, other
: usize) -> Self {
168 Self::from_usize(self.index() + other
)
172 impl $
crate::vec
::Idx
for $
type {
174 fn new(value
: usize) -> Self {
175 Self::from_usize(value
)
179 fn index(self) -> usize {
184 impl ::std
::iter
::Step
for $
type {
186 fn steps_between(start
: &Self, end
: &Self) -> Option
<usize> {
187 <usize as ::std
::iter
::Step
>::steps_between(
188 &Self::index(*start
),
194 fn replace_one(&mut self) -> Self {
195 ::std
::mem
::replace(self, Self::from_u32(1))
199 fn replace_zero(&mut self) -> Self {
200 ::std
::mem
::replace(self, Self::from_u32(0))
204 fn add_one(&self) -> Self {
205 Self::from_usize(Self::index(*self) + 1)
209 fn sub_one(&self) -> Self {
210 Self::from_usize(Self::index(*self) - 1)
214 fn add_usize(&self, u
: usize) -> Option
<Self> {
215 Self::index(*self).checked_add(u
).map(Self::from_usize
)
219 fn sub_usize(&self, u
: usize) -> Option
<Self> {
220 Self::index(*self).checked_sub(u
).map(Self::from_usize
)
224 impl From
<$
type> for u32 {
226 fn from(v
: $
type) -> u32 {
231 impl From
<$
type> for usize {
233 fn from(v
: $
type) -> usize {
238 impl From
<usize> for $
type {
240 fn from(value
: usize) -> Self {
241 Self::from_usize(value
)
245 impl From
<u32> for $
type {
247 fn from(value
: u32) -> Self {
248 Self::from_u32(value
)
252 $
crate::newtype_index
!(
254 @derives
[$
($derives
,)*]
256 @debug_format
[$debug_format
]);
259 // base case for handle_debug where format is custom. No Debug implementation is emitted.
261 @derives
[$
($_derives
:ident
,)*]
263 @debug_format
[custom
]) => ();
265 // base case for handle_debug, no debug overrides found, so use default
269 @debug_format
[$debug_format
:tt
]) => (
270 impl ::std
::fmt
::Debug
for $
type {
271 fn fmt(&self, fmt
: &mut ::std
::fmt
::Formatter
<'_
>) -> ::std
::fmt
::Result
{
272 write
!(fmt
, $debug_format
, self.as_u32())
277 // Debug is requested for derive, don't generate any Debug implementation.
279 @derives
[Debug
, $
($derives
:ident
,)*]
281 @debug_format
[$debug_format
:tt
]) => ();
283 // It's not Debug, so just pop it off the front of the derives stack and check the rest.
285 @derives
[$_derive
:ident
, $
($derives
:ident
,)*]
287 @debug_format
[$debug_format
:tt
]) => (
288 $
crate::newtype_index
!(
290 @derives
[$
($derives
,)*]
292 @debug_format
[$debug_format
]);
295 // Append comma to end of derives list if it's missing
296 (@attrs
[$
(#[$attrs:meta])*]
300 @debug_format
[$debug_format
:tt
]
301 derive
[$
($derives
:ident
),*]
303 $
crate::newtype_index
!(
304 @attrs
[$
(#[$attrs])*]
308 @debug_format
[$debug_format
]
309 derive
[$
($derives
,)*]
313 // By not including the @derives marker in this list nor in the default args, we can force it
314 // to come first if it exists. When encodable is custom, just use the derives list as-is.
315 (@attrs
[$
(#[$attrs:meta])*]
319 @debug_format
[$debug_format
:tt
]
320 derive
[$
($derives
:ident
,)+]
323 $
crate::newtype_index
!(
324 @attrs
[$
(#[$attrs])*]
325 @derives
[$
($derives
,)+]
329 @debug_format
[$debug_format
]
333 // By not including the @derives marker in this list nor in the default args, we can force it
334 // to come first if it exists. When encodable isn't custom, add serialization traits by default.
335 (@attrs
[$
(#[$attrs:meta])*]
339 @debug_format
[$debug_format
:tt
]
340 derive
[$
($derives
:ident
,)+]
342 $
crate::newtype_index
!(
343 @derives
[$
($derives
,)+ RustcEncodable
,]
344 @attrs
[$
(#[$attrs])*]
348 @debug_format
[$debug_format
]
350 $
crate::newtype_index
!(@decodable $
type);
353 // The case where no derives are added, but encodable is overridden. Don't
354 // derive serialization traits
355 (@attrs
[$
(#[$attrs:meta])*]
359 @debug_format
[$debug_format
:tt
]
362 $
crate::newtype_index
!(
364 @attrs
[$
(#[$attrs])*]
368 @debug_format
[$debug_format
]
372 // The case where no derives are added, add serialization derives by default
373 (@attrs
[$
(#[$attrs:meta])*]
377 @debug_format
[$debug_format
:tt
]
379 $
crate::newtype_index
!(
380 @derives
[RustcEncodable
,]
381 @attrs
[$
(#[$attrs])*]
385 @debug_format
[$debug_format
]
387 $
crate::newtype_index
!(@decodable $
type);
390 (@decodable $
type:ident
) => (
391 impl ::rustc_serialize
::Decodable
for $
type {
392 fn decode
<D
: ::rustc_serialize
::Decoder
>(d
: &mut D
) -> Result
<Self, D
::Error
> {
393 d
.read_u32().map(Self::from_u32
)
398 // Rewrite final without comma to one that includes comma
399 (@derives
[$
($derives
:ident
,)*]
400 @attrs
[$
(#[$attrs:meta])*]
404 @debug_format
[$debug_format
:tt
]
405 $name
:ident
= $constant
:expr
) => (
406 $
crate::newtype_index
!(
407 @derives
[$
($derives
,)*]
408 @attrs
[$
(#[$attrs])*]
412 @debug_format
[$debug_format
]
416 // Rewrite final const without comma to one that includes comma
417 (@derives
[$
($derives
:ident
,)*]
418 @attrs
[$
(#[$attrs:meta])*]
422 @debug_format
[$debug_format
:tt
]
423 $
(#[doc = $doc:expr])*
424 const $name
:ident
= $constant
:expr
) => (
425 $
crate::newtype_index
!(
426 @derives
[$
($derives
,)*]
427 @attrs
[$
(#[$attrs])*]
431 @debug_format
[$debug_format
]
432 $
(#[doc = $doc])* const $name = $constant,);
435 // Replace existing default for max
436 (@derives
[$
($derives
:ident
,)*]
437 @attrs
[$
(#[$attrs:meta])*]
441 @debug_format
[$debug_format
:tt
]
444 $
crate::newtype_index
!(
445 @derives
[$
($derives
,)*]
446 @attrs
[$
(#[$attrs])*]
450 @debug_format
[$debug_format
]
454 // Replace existing default for debug_format
455 (@derives
[$
($derives
:ident
,)*]
456 @attrs
[$
(#[$attrs:meta])*]
460 @debug_format
[$_debug_format
:tt
]
461 DEBUG_FORMAT
= $debug_format
:tt
,
463 $
crate::newtype_index
!(
464 @derives
[$
($derives
,)*]
465 @attrs
[$
(#[$attrs])*]
469 @debug_format
[$debug_format
]
473 // Assign a user-defined constant
474 (@derives
[$
($derives
:ident
,)*]
475 @attrs
[$
(#[$attrs:meta])*]
479 @debug_format
[$debug_format
:tt
]
480 $
(#[doc = $doc:expr])*
481 const $name
:ident
= $constant
:expr
,
484 $v
const $name
: $
type = $
type::from_u32($constant
);
485 $
crate::newtype_index
!(
486 @derives
[$
($derives
,)*]
487 @attrs
[$
(#[$attrs])*]
491 @debug_format
[$debug_format
]
496 #[derive(Clone, PartialEq, Eq, Hash)]
497 pub struct IndexVec
<I
: Idx
, T
> {
499 _marker
: PhantomData
<fn(&I
)>,
502 // Whether `IndexVec` is `Send` depends only on the data,
503 // not the phantom data.
504 unsafe impl<I
: Idx
, T
> Send
for IndexVec
<I
, T
> where T
: Send {}
506 impl<I
: Idx
, T
: Encodable
> Encodable
for IndexVec
<I
, T
> {
507 fn encode
<S
: Encoder
>(&self, s
: &mut S
) -> Result
<(), S
::Error
> {
508 Encodable
::encode(&self.raw
, s
)
512 impl<I
: Idx
, T
: Decodable
> Decodable
for IndexVec
<I
, T
> {
513 fn decode
<D
: Decoder
>(d
: &mut D
) -> Result
<Self, D
::Error
> {
514 Decodable
::decode(d
).map(|v
| IndexVec { raw: v, _marker: PhantomData }
)
518 impl<I
: Idx
, T
: fmt
::Debug
> fmt
::Debug
for IndexVec
<I
, T
> {
519 fn fmt(&self, fmt
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
520 fmt
::Debug
::fmt(&self.raw
, fmt
)
524 pub type Enumerated
<I
, J
> = iter
::Map
<iter
::Enumerate
<J
>, IntoIdx
<I
>>;
526 impl<I
: Idx
, T
> IndexVec
<I
, T
> {
528 pub fn new() -> Self {
529 IndexVec { raw: Vec::new(), _marker: PhantomData }
533 pub fn from_raw(raw
: Vec
<T
>) -> Self {
534 IndexVec { raw, _marker: PhantomData }
538 pub fn with_capacity(capacity
: usize) -> Self {
539 IndexVec { raw: Vec::with_capacity(capacity), _marker: PhantomData }
543 pub fn from_elem
<S
>(elem
: T
, universe
: &IndexVec
<I
, S
>) -> Self
547 IndexVec { raw: vec![elem; universe.len()], _marker: PhantomData }
551 pub fn from_elem_n(elem
: T
, n
: usize) -> Self
555 IndexVec { raw: vec![elem; n], _marker: PhantomData }
558 /// Create an `IndexVec` with `n` elements, where the value of each
559 /// element is the result of `func(i)`
561 pub fn from_fn_n(func
: impl FnMut(I
) -> T
, n
: usize) -> Self {
562 let indices
= (0..n
).map(I
::new
);
563 Self::from_raw(indices
.map(func
).collect())
567 pub fn push(&mut self, d
: T
) -> I
{
568 let idx
= I
::new(self.len());
574 pub fn pop(&mut self) -> Option
<T
> {
579 pub fn len(&self) -> usize {
583 /// Gives the next index that will be assigned when `push` is
586 pub fn next_index(&self) -> I
{
591 pub fn is_empty(&self) -> bool
{
596 pub fn into_iter(self) -> vec
::IntoIter
<T
> {
601 pub fn into_iter_enumerated(self) -> Enumerated
<I
, vec
::IntoIter
<T
>> {
602 self.raw
.into_iter().enumerate().map(IntoIdx { _marker: PhantomData }
)
606 pub fn iter(&self) -> slice
::Iter
<'_
, T
> {
611 pub fn iter_enumerated(&self) -> Enumerated
<I
, slice
::Iter
<'_
, T
>> {
612 self.raw
.iter().enumerate().map(IntoIdx { _marker: PhantomData }
)
616 pub fn indices(&self) -> iter
::Map
<Range
<usize>, IntoIdx
<I
>> {
617 (0..self.len()).map(IntoIdx { _marker: PhantomData }
)
621 pub fn iter_mut(&mut self) -> slice
::IterMut
<'_
, T
> {
626 pub fn iter_enumerated_mut(&mut self) -> Enumerated
<I
, slice
::IterMut
<'_
, T
>> {
627 self.raw
.iter_mut().enumerate().map(IntoIdx { _marker: PhantomData }
)
631 pub fn drain
<'a
, R
: RangeBounds
<usize>>(
634 ) -> impl Iterator
<Item
= T
> + 'a
{
635 self.raw
.drain(range
)
639 pub fn drain_enumerated
<'a
, R
: RangeBounds
<usize>>(
642 ) -> impl Iterator
<Item
= (I
, T
)> + 'a
{
643 self.raw
.drain(range
).enumerate().map(IntoIdx { _marker: PhantomData }
)
647 pub fn last(&self) -> Option
<I
> {
648 self.len().checked_sub(1).map(I
::new
)
652 pub fn shrink_to_fit(&mut self) {
653 self.raw
.shrink_to_fit()
657 pub fn swap(&mut self, a
: I
, b
: I
) {
658 self.raw
.swap(a
.index(), b
.index())
662 pub fn truncate(&mut self, a
: usize) {
667 pub fn get(&self, index
: I
) -> Option
<&T
> {
668 self.raw
.get(index
.index())
672 pub fn get_mut(&mut self, index
: I
) -> Option
<&mut T
> {
673 self.raw
.get_mut(index
.index())
676 /// Returns mutable references to two distinct elements, a and b. Panics if a == b.
678 pub fn pick2_mut(&mut self, a
: I
, b
: I
) -> (&mut T
, &mut T
) {
679 let (ai
, bi
) = (a
.index(), b
.index());
683 let (c1
, c2
) = self.raw
.split_at_mut(bi
);
684 (&mut c1
[ai
], &mut c2
[0])
686 let (c2
, c1
) = self.pick2_mut(b
, a
);
691 pub fn convert_index_type
<Ix
: Idx
>(self) -> IndexVec
<Ix
, T
> {
692 IndexVec { raw: self.raw, _marker: PhantomData }
696 impl<I
: Idx
, T
: Clone
> IndexVec
<I
, T
> {
697 /// Grows the index vector so that it contains an entry for
698 /// `elem`; if that is already true, then has no
699 /// effect. Otherwise, inserts new values as needed by invoking
702 pub fn ensure_contains_elem(&mut self, elem
: I
, fill_value
: impl FnMut() -> T
) {
703 let min_new_len
= elem
.index() + 1;
704 if self.len() < min_new_len
{
705 self.raw
.resize_with(min_new_len
, fill_value
);
710 pub fn resize(&mut self, new_len
: usize, value
: T
) {
711 self.raw
.resize(new_len
, value
)
715 pub fn resize_to_elem(&mut self, elem
: I
, fill_value
: impl FnMut() -> T
) {
716 let min_new_len
= elem
.index() + 1;
717 self.raw
.resize_with(min_new_len
, fill_value
);
721 impl<I
: Idx
, T
: Ord
> IndexVec
<I
, T
> {
723 pub fn binary_search(&self, value
: &T
) -> Result
<I
, I
> {
724 match self.raw
.binary_search(value
) {
725 Ok(i
) => Ok(Idx
::new(i
)),
726 Err(i
) => Err(Idx
::new(i
)),
731 impl<I
: Idx
, T
> Index
<I
> for IndexVec
<I
, T
> {
735 fn index(&self, index
: I
) -> &T
{
736 &self.raw
[index
.index()]
740 impl<I
: Idx
, T
> IndexMut
<I
> for IndexVec
<I
, T
> {
742 fn index_mut(&mut self, index
: I
) -> &mut T
{
743 &mut self.raw
[index
.index()]
747 impl<I
: Idx
, T
> Default
for IndexVec
<I
, T
> {
749 fn default() -> Self {
754 impl<I
: Idx
, T
> Extend
<T
> for IndexVec
<I
, T
> {
756 fn extend
<J
: IntoIterator
<Item
= T
>>(&mut self, iter
: J
) {
757 self.raw
.extend(iter
);
761 impl<I
: Idx
, T
> FromIterator
<T
> for IndexVec
<I
, T
> {
763 fn from_iter
<J
>(iter
: J
) -> Self
765 J
: IntoIterator
<Item
= T
>,
767 IndexVec { raw: FromIterator::from_iter(iter), _marker: PhantomData }
771 impl<I
: Idx
, T
> IntoIterator
for IndexVec
<I
, T
> {
773 type IntoIter
= vec
::IntoIter
<T
>;
776 fn into_iter(self) -> vec
::IntoIter
<T
> {
781 impl<'a
, I
: Idx
, T
> IntoIterator
for &'a IndexVec
<I
, T
> {
783 type IntoIter
= slice
::Iter
<'a
, T
>;
786 fn into_iter(self) -> slice
::Iter
<'a
, T
> {
791 impl<'a
, I
: Idx
, T
> IntoIterator
for &'a
mut IndexVec
<I
, T
> {
792 type Item
= &'a
mut T
;
793 type IntoIter
= slice
::IterMut
<'a
, T
>;
796 fn into_iter(self) -> slice
::IterMut
<'a
, T
> {
801 pub struct IntoIdx
<I
: Idx
> {
802 _marker
: PhantomData
<fn(&I
)>,
804 impl<I
: Idx
, T
> FnOnce
<((usize, T
),)> for IntoIdx
<I
> {
805 type Output
= (I
, T
);
807 extern "rust-call" fn call_once(self, ((n
, t
),): ((usize, T
),)) -> Self::Output
{
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
{
818 impl<I
: Idx
> FnOnce
<(usize,)> for IntoIdx
<I
> {
821 extern "rust-call" fn call_once(self, (n
,): (usize,)) -> Self::Output
{
826 impl<I
: Idx
> FnMut
<(usize,)> for IntoIdx
<I
> {
827 extern "rust-call" fn call_mut(&mut self, (n
,): (usize,)) -> Self::Output
{