]>
Commit | Line | Data |
---|---|---|
dfeec247 | 1 | use rustc_serialize::{Decodable, Decoder, Encodable, Encoder}; |
416331ca | 2 | |
dfeec247 | 3 | use std::fmt; |
3157f602 | 4 | use std::fmt::Debug; |
dfeec247 | 5 | use std::hash::Hash; |
3157f602 | 6 | use std::iter::{self, FromIterator}; |
3157f602 | 7 | use std::marker::PhantomData; |
0531ce1d | 8 | use std::ops::{Index, IndexMut, Range, RangeBounds}; |
dfeec247 | 9 | use std::slice; |
3157f602 | 10 | use std::u32; |
dfeec247 | 11 | use std::vec; |
3157f602 | 12 | |
3157f602 XL |
13 | /// Represents some newtyped `usize` wrapper. |
14 | /// | |
9fa01778 | 15 | /// Purpose: avoid mixing indexes for different bitvector domains. |
8faf50e0 | 16 | pub trait Idx: Copy + 'static + Ord + Debug + Hash { |
7cac9316 | 17 | fn new(idx: usize) -> Self; |
8faf50e0 | 18 | |
3157f602 | 19 | fn index(self) -> usize; |
8faf50e0 XL |
20 | |
21 | fn increment_by(&mut self, amount: usize) { | |
dc9dc135 XL |
22 | *self = self.plus(amount); |
23 | } | |
24 | ||
25 | fn plus(self, amount: usize) -> Self { | |
26 | Self::new(self.index() + amount) | |
8faf50e0 | 27 | } |
3157f602 XL |
28 | } |
29 | ||
30 | impl Idx for usize { | |
0531ce1d | 31 | #[inline] |
dfeec247 XL |
32 | fn new(idx: usize) -> Self { |
33 | idx | |
34 | } | |
0531ce1d | 35 | #[inline] |
dfeec247 XL |
36 | fn index(self) -> usize { |
37 | self | |
38 | } | |
3157f602 XL |
39 | } |
40 | ||
41 | impl Idx for u32 { | |
0531ce1d | 42 | #[inline] |
dfeec247 XL |
43 | fn new(idx: usize) -> Self { |
44 | assert!(idx <= u32::MAX as usize); | |
45 | idx as u32 | |
46 | } | |
0531ce1d | 47 | #[inline] |
dfeec247 XL |
48 | fn index(self) -> usize { |
49 | self as usize | |
50 | } | |
3157f602 XL |
51 | } |
52 | ||
b7449926 XL |
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. | |
ea8adc8c | 68 | #[macro_export] |
416331ca | 69 | #[allow_internal_unstable(step_trait, rustc_attrs)] |
ea8adc8c | 70 | macro_rules! newtype_index { |
abe05a73 XL |
71 | // ---- public rules ---- |
72 | ||
73 | // Use default constants | |
532ac7d7 | 74 | ($(#[$attrs:meta])* $v:vis struct $name:ident { .. }) => ( |
416331ca | 75 | $crate::newtype_index!( |
abe05a73 | 76 | // Leave out derives marker so we can use its absence to ensure it comes first |
532ac7d7 | 77 | @attrs [$(#[$attrs])*] |
abe05a73 | 78 | @type [$name] |
b7449926 XL |
79 | // shave off 256 indices at the end to allow space for packing these indices into enums |
80 | @max [0xFFFF_FF00] | |
81 | @vis [$v] | |
abe05a73 | 82 | @debug_format ["{}"]); |
ea8adc8c XL |
83 | ); |
84 | ||
abe05a73 | 85 | // Define any constants |
532ac7d7 | 86 | ($(#[$attrs:meta])* $v:vis struct $name:ident { $($tokens:tt)+ }) => ( |
416331ca | 87 | $crate::newtype_index!( |
abe05a73 | 88 | // Leave out derives marker so we can use its absence to ensure it comes first |
532ac7d7 | 89 | @attrs [$(#[$attrs])*] |
abe05a73 | 90 | @type [$name] |
b7449926 XL |
91 | // shave off 256 indices at the end to allow space for packing these indices into enums |
92 | @max [0xFFFF_FF00] | |
93 | @vis [$v] | |
abe05a73 XL |
94 | @debug_format ["{}"] |
95 | $($tokens)+); | |
96 | ); | |
ea8adc8c | 97 | |
abe05a73 XL |
98 | // ---- private rules ---- |
99 | ||
100 | // Base case, user-defined constants (if any) have already been defined | |
101 | (@derives [$($derives:ident,)*] | |
532ac7d7 | 102 | @attrs [$(#[$attrs:meta])*] |
abe05a73 XL |
103 | @type [$type:ident] |
104 | @max [$max:expr] | |
b7449926 | 105 | @vis [$v:vis] |
abe05a73 | 106 | @debug_format [$debug_format:tt]) => ( |
532ac7d7 | 107 | $(#[$attrs])* |
0731742a | 108 | #[derive(Copy, PartialEq, Eq, Hash, PartialOrd, Ord, $($derives),*)] |
b7449926 XL |
109 | #[rustc_layout_scalar_valid_range_end($max)] |
110 | $v struct $type { | |
111 | private: u32 | |
112 | } | |
113 | ||
0731742a XL |
114 | impl Clone for $type { |
115 | fn clone(&self) -> Self { | |
116 | *self | |
117 | } | |
118 | } | |
119 | ||
b7449926 XL |
120 | impl $type { |
121 | $v const MAX_AS_U32: u32 = $max; | |
122 | ||
dfeec247 | 123 | $v const MAX: Self = Self::from_u32_const($max); |
b7449926 XL |
124 | |
125 | #[inline] | |
126 | $v fn from_usize(value: usize) -> Self { | |
127 | assert!(value <= ($max as usize)); | |
128 | unsafe { | |
dfeec247 | 129 | Self::from_u32_unchecked(value as u32) |
b7449926 XL |
130 | } |
131 | } | |
132 | ||
133 | #[inline] | |
134 | $v fn from_u32(value: u32) -> Self { | |
135 | assert!(value <= $max); | |
136 | unsafe { | |
dfeec247 | 137 | Self::from_u32_unchecked(value) |
b7449926 XL |
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 { | |
dfeec247 | 155 | Self { private: value } |
b7449926 XL |
156 | } |
157 | } | |
158 | ||
159 | #[inline] | |
160 | $v const unsafe fn from_u32_unchecked(value: u32) -> Self { | |
dfeec247 | 161 | Self { private: value } |
b7449926 XL |
162 | } |
163 | ||
9fa01778 | 164 | /// Extracts the value of this index as an integer. |
b7449926 XL |
165 | #[inline] |
166 | $v fn index(self) -> usize { | |
167 | self.as_usize() | |
168 | } | |
169 | ||
9fa01778 | 170 | /// Extracts the value of this index as a `u32`. |
b7449926 XL |
171 | #[inline] |
172 | $v fn as_u32(self) -> u32 { | |
173 | self.private | |
174 | } | |
175 | ||
9fa01778 | 176 | /// Extracts the value of this index as a `usize`. |
b7449926 XL |
177 | #[inline] |
178 | $v fn as_usize(self) -> usize { | |
179 | self.as_u32() as usize | |
180 | } | |
181 | } | |
ea8adc8c | 182 | |
dc9dc135 XL |
183 | impl std::ops::Add<usize> for $type { |
184 | type Output = Self; | |
185 | ||
186 | fn add(self, other: usize) -> Self { | |
dfeec247 | 187 | Self::from_usize(self.index() + other) |
dc9dc135 XL |
188 | } |
189 | } | |
190 | ||
dfeec247 | 191 | impl $crate::vec::Idx for $type { |
0531ce1d | 192 | #[inline] |
ea8adc8c | 193 | fn new(value: usize) -> Self { |
dfeec247 | 194 | Self::from_usize(value) |
ea8adc8c | 195 | } |
abe05a73 | 196 | |
0531ce1d | 197 | #[inline] |
ea8adc8c | 198 | fn index(self) -> usize { |
b7449926 | 199 | usize::from(self) |
ea8adc8c XL |
200 | } |
201 | } | |
202 | ||
8faf50e0 | 203 | impl ::std::iter::Step for $type { |
b7449926 | 204 | #[inline] |
8faf50e0 XL |
205 | fn steps_between(start: &Self, end: &Self) -> Option<usize> { |
206 | <usize as ::std::iter::Step>::steps_between( | |
dfeec247 XL |
207 | &Self::index(*start), |
208 | &Self::index(*end), | |
8faf50e0 XL |
209 | ) |
210 | } | |
211 | ||
b7449926 | 212 | #[inline] |
8faf50e0 | 213 | fn replace_one(&mut self) -> Self { |
dfeec247 | 214 | ::std::mem::replace(self, Self::from_u32(1)) |
8faf50e0 XL |
215 | } |
216 | ||
b7449926 | 217 | #[inline] |
8faf50e0 | 218 | fn replace_zero(&mut self) -> Self { |
dfeec247 | 219 | ::std::mem::replace(self, Self::from_u32(0)) |
8faf50e0 XL |
220 | } |
221 | ||
b7449926 | 222 | #[inline] |
8faf50e0 | 223 | fn add_one(&self) -> Self { |
dfeec247 | 224 | Self::from_usize(Self::index(*self) + 1) |
8faf50e0 XL |
225 | } |
226 | ||
b7449926 | 227 | #[inline] |
8faf50e0 | 228 | fn sub_one(&self) -> Self { |
dfeec247 | 229 | Self::from_usize(Self::index(*self) - 1) |
8faf50e0 XL |
230 | } |
231 | ||
b7449926 | 232 | #[inline] |
8faf50e0 | 233 | fn add_usize(&self, u: usize) -> Option<Self> { |
dfeec247 | 234 | Self::index(*self).checked_add(u).map(Self::from_usize) |
8faf50e0 | 235 | } |
dc9dc135 XL |
236 | |
237 | #[inline] | |
238 | fn sub_usize(&self, u: usize) -> Option<Self> { | |
dfeec247 | 239 | Self::index(*self).checked_sub(u).map(Self::from_usize) |
dc9dc135 | 240 | } |
8faf50e0 XL |
241 | } |
242 | ||
b7449926 XL |
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 { | |
dfeec247 | 260 | Self::from_usize(value) |
b7449926 XL |
261 | } |
262 | } | |
263 | ||
264 | impl From<u32> for $type { | |
265 | #[inline] | |
266 | fn from(value: u32) -> Self { | |
dfeec247 | 267 | Self::from_u32(value) |
b7449926 XL |
268 | } |
269 | } | |
270 | ||
416331ca | 271 | $crate::newtype_index!( |
abe05a73 XL |
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 { | |
9fa01778 | 290 | fn fmt(&self, fmt: &mut ::std::fmt::Formatter<'_>) -> ::std::fmt::Result { |
b7449926 | 291 | write!(fmt, $debug_format, self.as_u32()) |
ea8adc8c XL |
292 | } |
293 | } | |
abe05a73 XL |
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]) => ( | |
416331ca | 307 | $crate::newtype_index!( |
abe05a73 XL |
308 | @handle_debug |
309 | @derives [$($derives,)*] | |
310 | @type [$type] | |
311 | @debug_format [$debug_format]); | |
312 | ); | |
313 | ||
abe05a73 | 314 | // Append comma to end of derives list if it's missing |
532ac7d7 XL |
315 | (@attrs [$(#[$attrs:meta])*] |
316 | @type [$type:ident] | |
abe05a73 | 317 | @max [$max:expr] |
b7449926 | 318 | @vis [$v:vis] |
abe05a73 XL |
319 | @debug_format [$debug_format:tt] |
320 | derive [$($derives:ident),*] | |
321 | $($tokens:tt)*) => ( | |
416331ca | 322 | $crate::newtype_index!( |
532ac7d7 | 323 | @attrs [$(#[$attrs])*] |
abe05a73 XL |
324 | @type [$type] |
325 | @max [$max] | |
b7449926 | 326 | @vis [$v] |
abe05a73 XL |
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. | |
532ac7d7 XL |
334 | (@attrs [$(#[$attrs:meta])*] |
335 | @type [$type:ident] | |
abe05a73 | 336 | @max [$max:expr] |
b7449926 | 337 | @vis [$v:vis] |
abe05a73 XL |
338 | @debug_format [$debug_format:tt] |
339 | derive [$($derives:ident,)+] | |
340 | ENCODABLE = custom | |
341 | $($tokens:tt)*) => ( | |
416331ca | 342 | $crate::newtype_index!( |
532ac7d7 | 343 | @attrs [$(#[$attrs])*] |
abe05a73 | 344 | @derives [$($derives,)+] |
abe05a73 XL |
345 | @type [$type] |
346 | @max [$max] | |
b7449926 | 347 | @vis [$v] |
abe05a73 XL |
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. | |
532ac7d7 XL |
354 | (@attrs [$(#[$attrs:meta])*] |
355 | @type [$type:ident] | |
abe05a73 | 356 | @max [$max:expr] |
b7449926 | 357 | @vis [$v:vis] |
abe05a73 XL |
358 | @debug_format [$debug_format:tt] |
359 | derive [$($derives:ident,)+] | |
360 | $($tokens:tt)*) => ( | |
416331ca | 361 | $crate::newtype_index!( |
0731742a | 362 | @derives [$($derives,)+ RustcEncodable,] |
532ac7d7 | 363 | @attrs [$(#[$attrs])*] |
abe05a73 XL |
364 | @type [$type] |
365 | @max [$max] | |
b7449926 | 366 | @vis [$v] |
abe05a73 XL |
367 | @debug_format [$debug_format] |
368 | $($tokens)*); | |
416331ca | 369 | $crate::newtype_index!(@decodable $type); |
abe05a73 XL |
370 | ); |
371 | ||
0531ce1d | 372 | // The case where no derives are added, but encodable is overridden. Don't |
abe05a73 | 373 | // derive serialization traits |
532ac7d7 XL |
374 | (@attrs [$(#[$attrs:meta])*] |
375 | @type [$type:ident] | |
abe05a73 | 376 | @max [$max:expr] |
b7449926 | 377 | @vis [$v:vis] |
abe05a73 XL |
378 | @debug_format [$debug_format:tt] |
379 | ENCODABLE = custom | |
380 | $($tokens:tt)*) => ( | |
416331ca | 381 | $crate::newtype_index!( |
abe05a73 | 382 | @derives [] |
532ac7d7 | 383 | @attrs [$(#[$attrs])*] |
abe05a73 XL |
384 | @type [$type] |
385 | @max [$max] | |
b7449926 | 386 | @vis [$v] |
abe05a73 XL |
387 | @debug_format [$debug_format] |
388 | $($tokens)*); | |
389 | ); | |
390 | ||
391 | // The case where no derives are added, add serialization derives by default | |
532ac7d7 XL |
392 | (@attrs [$(#[$attrs:meta])*] |
393 | @type [$type:ident] | |
abe05a73 | 394 | @max [$max:expr] |
b7449926 | 395 | @vis [$v:vis] |
abe05a73 XL |
396 | @debug_format [$debug_format:tt] |
397 | $($tokens:tt)*) => ( | |
416331ca | 398 | $crate::newtype_index!( |
0731742a | 399 | @derives [RustcEncodable,] |
532ac7d7 | 400 | @attrs [$(#[$attrs])*] |
abe05a73 XL |
401 | @type [$type] |
402 | @max [$max] | |
b7449926 | 403 | @vis [$v] |
abe05a73 XL |
404 | @debug_format [$debug_format] |
405 | $($tokens)*); | |
416331ca | 406 | $crate::newtype_index!(@decodable $type); |
0731742a XL |
407 | ); |
408 | ||
409 | (@decodable $type:ident) => ( | |
416331ca XL |
410 | impl ::rustc_serialize::Decodable for $type { |
411 | fn decode<D: ::rustc_serialize::Decoder>(d: &mut D) -> Result<Self, D::Error> { | |
dfeec247 | 412 | d.read_u32().map(Self::from_u32) |
0731742a XL |
413 | } |
414 | } | |
abe05a73 XL |
415 | ); |
416 | ||
417 | // Rewrite final without comma to one that includes comma | |
418 | (@derives [$($derives:ident,)*] | |
532ac7d7 | 419 | @attrs [$(#[$attrs:meta])*] |
abe05a73 XL |
420 | @type [$type:ident] |
421 | @max [$max:expr] | |
b7449926 | 422 | @vis [$v:vis] |
abe05a73 XL |
423 | @debug_format [$debug_format:tt] |
424 | $name:ident = $constant:expr) => ( | |
416331ca | 425 | $crate::newtype_index!( |
abe05a73 | 426 | @derives [$($derives,)*] |
532ac7d7 | 427 | @attrs [$(#[$attrs])*] |
abe05a73 XL |
428 | @type [$type] |
429 | @max [$max] | |
b7449926 | 430 | @vis [$v] |
abe05a73 XL |
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,)*] | |
532ac7d7 | 437 | @attrs [$(#[$attrs:meta])*] |
abe05a73 | 438 | @type [$type:ident] |
dc9dc135 | 439 | @max [$max:expr] |
b7449926 | 440 | @vis [$v:vis] |
abe05a73 XL |
441 | @debug_format [$debug_format:tt] |
442 | $(#[doc = $doc:expr])* | |
443 | const $name:ident = $constant:expr) => ( | |
416331ca | 444 | $crate::newtype_index!( |
abe05a73 | 445 | @derives [$($derives,)*] |
532ac7d7 | 446 | @attrs [$(#[$attrs])*] |
abe05a73 XL |
447 | @type [$type] |
448 | @max [$max] | |
b7449926 | 449 | @vis [$v] |
abe05a73 XL |
450 | @debug_format [$debug_format] |
451 | $(#[doc = $doc])* const $name = $constant,); | |
452 | ); | |
453 | ||
454 | // Replace existing default for max | |
455 | (@derives [$($derives:ident,)*] | |
532ac7d7 | 456 | @attrs [$(#[$attrs:meta])*] |
abe05a73 XL |
457 | @type [$type:ident] |
458 | @max [$_max:expr] | |
b7449926 | 459 | @vis [$v:vis] |
abe05a73 XL |
460 | @debug_format [$debug_format:tt] |
461 | MAX = $max:expr, | |
462 | $($tokens:tt)*) => ( | |
416331ca | 463 | $crate::newtype_index!( |
abe05a73 | 464 | @derives [$($derives,)*] |
532ac7d7 | 465 | @attrs [$(#[$attrs])*] |
abe05a73 XL |
466 | @type [$type] |
467 | @max [$max] | |
b7449926 | 468 | @vis [$v] |
abe05a73 XL |
469 | @debug_format [$debug_format] |
470 | $($tokens)*); | |
471 | ); | |
472 | ||
473 | // Replace existing default for debug_format | |
474 | (@derives [$($derives:ident,)*] | |
532ac7d7 | 475 | @attrs [$(#[$attrs:meta])*] |
abe05a73 XL |
476 | @type [$type:ident] |
477 | @max [$max:expr] | |
b7449926 | 478 | @vis [$v:vis] |
abe05a73 XL |
479 | @debug_format [$_debug_format:tt] |
480 | DEBUG_FORMAT = $debug_format:tt, | |
481 | $($tokens:tt)*) => ( | |
416331ca | 482 | $crate::newtype_index!( |
abe05a73 | 483 | @derives [$($derives,)*] |
532ac7d7 | 484 | @attrs [$(#[$attrs])*] |
abe05a73 XL |
485 | @type [$type] |
486 | @max [$max] | |
b7449926 | 487 | @vis [$v] |
abe05a73 XL |
488 | @debug_format [$debug_format] |
489 | $($tokens)*); | |
490 | ); | |
491 | ||
492 | // Assign a user-defined constant | |
493 | (@derives [$($derives:ident,)*] | |
532ac7d7 | 494 | @attrs [$(#[$attrs:meta])*] |
abe05a73 XL |
495 | @type [$type:ident] |
496 | @max [$max:expr] | |
b7449926 | 497 | @vis [$v:vis] |
abe05a73 XL |
498 | @debug_format [$debug_format:tt] |
499 | $(#[doc = $doc:expr])* | |
500 | const $name:ident = $constant:expr, | |
501 | $($tokens:tt)*) => ( | |
502 | $(#[doc = $doc])* | |
dfeec247 | 503 | $v const $name: $type = $type::from_u32_const($constant); |
416331ca | 504 | $crate::newtype_index!( |
abe05a73 | 505 | @derives [$($derives,)*] |
532ac7d7 | 506 | @attrs [$(#[$attrs])*] |
abe05a73 XL |
507 | @type [$type] |
508 | @max [$max] | |
b7449926 | 509 | @vis [$v] |
abe05a73 XL |
510 | @debug_format [$debug_format] |
511 | $($tokens)*); | |
512 | ); | |
ea8adc8c XL |
513 | } |
514 | ||
0531ce1d | 515 | #[derive(Clone, PartialEq, Eq, Hash)] |
3157f602 XL |
516 | pub struct IndexVec<I: Idx, T> { |
517 | pub raw: Vec<T>, | |
dfeec247 | 518 | _marker: PhantomData<fn(&I)>, |
3157f602 XL |
519 | } |
520 | ||
ff7c6d11 XL |
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 | ||
416331ca XL |
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) | |
3157f602 XL |
528 | } |
529 | } | |
530 | ||
416331ca XL |
531 | impl<I: Idx, T: Decodable> Decodable for IndexVec<I, T> { |
532 | fn decode<D: Decoder>(d: &mut D) -> Result<Self, D::Error> { | |
dfeec247 | 533 | Decodable::decode(d).map(|v| IndexVec { raw: v, _marker: PhantomData }) |
3157f602 XL |
534 | } |
535 | } | |
536 | ||
537 | impl<I: Idx, T: fmt::Debug> fmt::Debug for IndexVec<I, T> { | |
9fa01778 | 538 | fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { |
3157f602 XL |
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] | |
94b46f34 XL |
552 | pub fn from_raw(raw: Vec<T>) -> Self { |
553 | IndexVec { raw, _marker: PhantomData } | |
554 | } | |
555 | ||
556 | #[inline] | |
3157f602 XL |
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 | |
dfeec247 XL |
563 | where |
564 | T: Clone, | |
3157f602 XL |
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 | |
dfeec247 XL |
571 | where |
572 | T: Clone, | |
3157f602 XL |
573 | { |
574 | IndexVec { raw: vec![elem; n], _marker: PhantomData } | |
575 | } | |
576 | ||
74b04a01 XL |
577 | /// Create an `IndexVec` with `n` elements, where the value of each |
578 | /// element is the result of `func(i)` | |
579 | #[inline] | |
580 | pub fn from_fn_n(func: impl FnMut(I) -> T, n: usize) -> Self { | |
581 | let indices = (0..n).map(I::new); | |
582 | Self::from_raw(indices.map(func).collect()) | |
583 | } | |
584 | ||
3157f602 XL |
585 | #[inline] |
586 | pub fn push(&mut self, d: T) -> I { | |
587 | let idx = I::new(self.len()); | |
588 | self.raw.push(d); | |
589 | idx | |
590 | } | |
591 | ||
abe05a73 XL |
592 | #[inline] |
593 | pub fn pop(&mut self) -> Option<T> { | |
594 | self.raw.pop() | |
595 | } | |
596 | ||
3157f602 XL |
597 | #[inline] |
598 | pub fn len(&self) -> usize { | |
599 | self.raw.len() | |
600 | } | |
601 | ||
0bf4aa26 XL |
602 | /// Gives the next index that will be assigned when `push` is |
603 | /// called. | |
604 | #[inline] | |
605 | pub fn next_index(&self) -> I { | |
606 | I::new(self.len()) | |
607 | } | |
608 | ||
3157f602 XL |
609 | #[inline] |
610 | pub fn is_empty(&self) -> bool { | |
611 | self.raw.is_empty() | |
612 | } | |
613 | ||
614 | #[inline] | |
615 | pub fn into_iter(self) -> vec::IntoIter<T> { | |
616 | self.raw.into_iter() | |
617 | } | |
618 | ||
619 | #[inline] | |
dfeec247 | 620 | pub fn into_iter_enumerated(self) -> Enumerated<I, vec::IntoIter<T>> { |
3157f602 XL |
621 | self.raw.into_iter().enumerate().map(IntoIdx { _marker: PhantomData }) |
622 | } | |
623 | ||
624 | #[inline] | |
9fa01778 | 625 | pub fn iter(&self) -> slice::Iter<'_, T> { |
3157f602 XL |
626 | self.raw.iter() |
627 | } | |
628 | ||
629 | #[inline] | |
dfeec247 | 630 | pub fn iter_enumerated(&self) -> Enumerated<I, slice::Iter<'_, T>> { |
3157f602 XL |
631 | self.raw.iter().enumerate().map(IntoIdx { _marker: PhantomData }) |
632 | } | |
633 | ||
634 | #[inline] | |
635 | pub fn indices(&self) -> iter::Map<Range<usize>, IntoIdx<I>> { | |
636 | (0..self.len()).map(IntoIdx { _marker: PhantomData }) | |
637 | } | |
638 | ||
639 | #[inline] | |
9fa01778 | 640 | pub fn iter_mut(&mut self) -> slice::IterMut<'_, T> { |
3157f602 XL |
641 | self.raw.iter_mut() |
642 | } | |
643 | ||
644 | #[inline] | |
dfeec247 | 645 | pub fn iter_enumerated_mut(&mut self) -> Enumerated<I, slice::IterMut<'_, T>> { |
3157f602 XL |
646 | self.raw.iter_mut().enumerate().map(IntoIdx { _marker: PhantomData }) |
647 | } | |
648 | ||
8bb4bdeb | 649 | #[inline] |
0531ce1d | 650 | pub fn drain<'a, R: RangeBounds<usize>>( |
dfeec247 XL |
651 | &'a mut self, |
652 | range: R, | |
653 | ) -> impl Iterator<Item = T> + 'a { | |
8bb4bdeb XL |
654 | self.raw.drain(range) |
655 | } | |
656 | ||
657 | #[inline] | |
0531ce1d | 658 | pub fn drain_enumerated<'a, R: RangeBounds<usize>>( |
dfeec247 XL |
659 | &'a mut self, |
660 | range: R, | |
661 | ) -> impl Iterator<Item = (I, T)> + 'a { | |
8bb4bdeb XL |
662 | self.raw.drain(range).enumerate().map(IntoIdx { _marker: PhantomData }) |
663 | } | |
664 | ||
3157f602 XL |
665 | #[inline] |
666 | pub fn last(&self) -> Option<I> { | |
667 | self.len().checked_sub(1).map(I::new) | |
668 | } | |
c30ab7b3 SL |
669 | |
670 | #[inline] | |
671 | pub fn shrink_to_fit(&mut self) { | |
672 | self.raw.shrink_to_fit() | |
673 | } | |
674 | ||
675 | #[inline] | |
8faf50e0 XL |
676 | pub fn swap(&mut self, a: I, b: I) { |
677 | self.raw.swap(a.index(), b.index()) | |
c30ab7b3 SL |
678 | } |
679 | ||
680 | #[inline] | |
681 | pub fn truncate(&mut self, a: usize) { | |
682 | self.raw.truncate(a) | |
683 | } | |
8bb4bdeb XL |
684 | |
685 | #[inline] | |
686 | pub fn get(&self, index: I) -> Option<&T> { | |
687 | self.raw.get(index.index()) | |
688 | } | |
689 | ||
690 | #[inline] | |
691 | pub fn get_mut(&mut self, index: I) -> Option<&mut T> { | |
692 | self.raw.get_mut(index.index()) | |
693 | } | |
0531ce1d | 694 | |
9fa01778 | 695 | /// Returns mutable references to two distinct elements, a and b. Panics if a == b. |
0531ce1d XL |
696 | #[inline] |
697 | pub fn pick2_mut(&mut self, a: I, b: I) -> (&mut T, &mut T) { | |
698 | let (ai, bi) = (a.index(), b.index()); | |
699 | assert!(ai != bi); | |
700 | ||
701 | if ai < bi { | |
702 | let (c1, c2) = self.raw.split_at_mut(bi); | |
703 | (&mut c1[ai], &mut c2[0]) | |
704 | } else { | |
705 | let (c2, c1) = self.pick2_mut(b, a); | |
706 | (c1, c2) | |
707 | } | |
708 | } | |
709 | ||
710 | pub fn convert_index_type<Ix: Idx>(self) -> IndexVec<Ix, T> { | |
dfeec247 | 711 | IndexVec { raw: self.raw, _marker: PhantomData } |
0531ce1d | 712 | } |
3157f602 XL |
713 | } |
714 | ||
cc61c64b | 715 | impl<I: Idx, T: Clone> IndexVec<I, T> { |
8faf50e0 XL |
716 | /// Grows the index vector so that it contains an entry for |
717 | /// `elem`; if that is already true, then has no | |
718 | /// effect. Otherwise, inserts new values as needed by invoking | |
719 | /// `fill_value`. | |
720 | #[inline] | |
721 | pub fn ensure_contains_elem(&mut self, elem: I, fill_value: impl FnMut() -> T) { | |
722 | let min_new_len = elem.index() + 1; | |
723 | if self.len() < min_new_len { | |
724 | self.raw.resize_with(min_new_len, fill_value); | |
725 | } | |
726 | } | |
727 | ||
cc61c64b XL |
728 | #[inline] |
729 | pub fn resize(&mut self, new_len: usize, value: T) { | |
730 | self.raw.resize(new_len, value) | |
731 | } | |
8faf50e0 XL |
732 | |
733 | #[inline] | |
734 | pub fn resize_to_elem(&mut self, elem: I, fill_value: impl FnMut() -> T) { | |
735 | let min_new_len = elem.index() + 1; | |
736 | self.raw.resize_with(min_new_len, fill_value); | |
737 | } | |
cc61c64b XL |
738 | } |
739 | ||
3b2f2976 XL |
740 | impl<I: Idx, T: Ord> IndexVec<I, T> { |
741 | #[inline] | |
742 | pub fn binary_search(&self, value: &T) -> Result<I, I> { | |
743 | match self.raw.binary_search(value) { | |
744 | Ok(i) => Ok(Idx::new(i)), | |
745 | Err(i) => Err(Idx::new(i)), | |
746 | } | |
747 | } | |
748 | } | |
749 | ||
3157f602 XL |
750 | impl<I: Idx, T> Index<I> for IndexVec<I, T> { |
751 | type Output = T; | |
752 | ||
753 | #[inline] | |
754 | fn index(&self, index: I) -> &T { | |
755 | &self.raw[index.index()] | |
756 | } | |
757 | } | |
758 | ||
759 | impl<I: Idx, T> IndexMut<I> for IndexVec<I, T> { | |
760 | #[inline] | |
761 | fn index_mut(&mut self, index: I) -> &mut T { | |
762 | &mut self.raw[index.index()] | |
763 | } | |
764 | } | |
765 | ||
7cac9316 XL |
766 | impl<I: Idx, T> Default for IndexVec<I, T> { |
767 | #[inline] | |
768 | fn default() -> Self { | |
769 | Self::new() | |
770 | } | |
771 | } | |
772 | ||
3157f602 XL |
773 | impl<I: Idx, T> Extend<T> for IndexVec<I, T> { |
774 | #[inline] | |
775 | fn extend<J: IntoIterator<Item = T>>(&mut self, iter: J) { | |
776 | self.raw.extend(iter); | |
777 | } | |
778 | } | |
779 | ||
780 | impl<I: Idx, T> FromIterator<T> for IndexVec<I, T> { | |
781 | #[inline] | |
dfeec247 XL |
782 | fn from_iter<J>(iter: J) -> Self |
783 | where | |
784 | J: IntoIterator<Item = T>, | |
785 | { | |
3157f602 XL |
786 | IndexVec { raw: FromIterator::from_iter(iter), _marker: PhantomData } |
787 | } | |
788 | } | |
789 | ||
790 | impl<I: Idx, T> IntoIterator for IndexVec<I, T> { | |
791 | type Item = T; | |
792 | type IntoIter = vec::IntoIter<T>; | |
793 | ||
794 | #[inline] | |
795 | fn into_iter(self) -> vec::IntoIter<T> { | |
796 | self.raw.into_iter() | |
797 | } | |
3157f602 XL |
798 | } |
799 | ||
800 | impl<'a, I: Idx, T> IntoIterator for &'a IndexVec<I, T> { | |
801 | type Item = &'a T; | |
802 | type IntoIter = slice::Iter<'a, T>; | |
803 | ||
804 | #[inline] | |
805 | fn into_iter(self) -> slice::Iter<'a, T> { | |
806 | self.raw.iter() | |
807 | } | |
808 | } | |
809 | ||
810 | impl<'a, I: Idx, T> IntoIterator for &'a mut IndexVec<I, T> { | |
811 | type Item = &'a mut T; | |
812 | type IntoIter = slice::IterMut<'a, T>; | |
813 | ||
814 | #[inline] | |
3b2f2976 | 815 | fn into_iter(self) -> slice::IterMut<'a, T> { |
3157f602 XL |
816 | self.raw.iter_mut() |
817 | } | |
818 | } | |
819 | ||
dfeec247 XL |
820 | pub struct IntoIdx<I: Idx> { |
821 | _marker: PhantomData<fn(&I)>, | |
822 | } | |
3157f602 XL |
823 | impl<I: Idx, T> FnOnce<((usize, T),)> for IntoIdx<I> { |
824 | type Output = (I, T); | |
825 | ||
826 | extern "rust-call" fn call_once(self, ((n, t),): ((usize, T),)) -> Self::Output { | |
827 | (I::new(n), t) | |
828 | } | |
829 | } | |
830 | ||
831 | impl<I: Idx, T> FnMut<((usize, T),)> for IntoIdx<I> { | |
832 | extern "rust-call" fn call_mut(&mut self, ((n, t),): ((usize, T),)) -> Self::Output { | |
833 | (I::new(n), t) | |
834 | } | |
835 | } | |
836 | ||
837 | impl<I: Idx> FnOnce<(usize,)> for IntoIdx<I> { | |
838 | type Output = I; | |
839 | ||
840 | extern "rust-call" fn call_once(self, (n,): (usize,)) -> Self::Output { | |
841 | I::new(n) | |
842 | } | |
843 | } | |
844 | ||
845 | impl<I: Idx> FnMut<(usize,)> for IntoIdx<I> { | |
846 | extern "rust-call" fn call_mut(&mut self, (n,): (usize,)) -> Self::Output { | |
847 | I::new(n) | |
848 | } | |
849 | } | |
dfeec247 XL |
850 | |
851 | #[cfg(test)] | |
852 | mod tests; |