index_vec/
lib.rs

1//! This crate helps with defining "newtype"-style wrappers around `usize` (or
2//! other integers), `Vec<T>`, and `[T]` so that some additional type safety can
3//! be gained at zero cost.
4//!
5//! ## Example / Overview
6//! ```rust
7//! use index_vec::{IndexVec, IndexSlice, index_vec};
8//!
9//! index_vec::define_index_type! {
10//!     // Define StrIdx to use only 32 bits internally (you can use usize, u16,
11//!     // and even u8).
12//!     pub struct StrIdx = u32;
13//!
14//!     // The defaults are very reasonable, but this macro can let
15//!     // you customize things quite a bit:
16//!
17//!     // By default, creating a StrIdx would check an incoming `usize against
18//!     // `u32::max_value()`, as u32 is the wrapped index type. Lets imagine that
19//!     // StrIdx has to interface with an external system that uses signed ints.
20//!     // We can change the checking behavior to complain on i32::max_value()
21//!     // instead:
22//!     MAX_INDEX = i32::max_value() as usize;
23//!
24//!     // We can also disable checking all-together if we are more concerned with perf
25//!     // than any overflow problems, or even do so, but only for debug builds: Quite
26//!     // pointless here, but an okay example
27//!     DISABLE_MAX_INDEX_CHECK = cfg!(not(debug_assertions));
28//!
29//!     // And more too, see this macro's docs for more info.
30//! }
31//!
32//! // Create a vector which can be accessed using `StrIdx`s.
33//! let mut strs: IndexVec<StrIdx, &'static str> = index_vec!["strs", "bar", "baz"];
34//!
35//! // l is a `StrIdx`
36//! let l = strs.last_idx();
37//! assert_eq!(strs[l], "baz");
38//!
39//! let new_i = strs.push("quux");
40//! assert_eq!(strs[new_i], "quux");
41//!
42//! // The slice APIs are wrapped as well.
43//! let s: &IndexSlice<StrIdx, [&'static str]> = &strs[StrIdx::new(1)..];
44//! assert_eq!(s[0], "bar");
45//!
46//! // Indices are mostly interoperable with `usize`, and support
47//! // a lot of what you might want to do to an index.
48//!
49//! // Comparison
50//! assert_eq!(StrIdx::new(0), 0usize);
51//!
52//! // Addition
53//! assert_eq!(StrIdx::new(0) + 1, 1usize);
54//!
55//! // Subtraction
56//! assert_eq!(StrIdx::new(1) - 1, 0usize);
57//!
58//! // Wrapping
59//! assert_eq!(StrIdx::new(5) % strs.len(), 1usize);
60//! // ...
61//! ```
62//! ## Background
63//!
64//! The goal is to help with the pattern of using a `type FooIdx = usize` to
65//! access a `Vec<Foo>` with something that can statically prevent using a
66//! `FooIdx` in a `Vec<Bar>`. It's most useful if you have a bunch of indices
67//! referring to different sorts of vectors.
68//!
69//! The code was originally based on `rustc`'s `IndexVec` code, however that has
70//! been almost entirely rewritten (except for the cases where it's trivial,
71//! e.g. the Vec wrapper).
72//!
73//! ## Other crates
74//!
75//! The [`indexed_vec`](https://crates.io/crates/indexed_vec) crate predates
76//! this, and is a much closer copy of the code from `rustc`. Unfortunately,
77//! this means it does not compile on stable.
78//!
79//! If you're looking for something further from a vec and closer to a map, you
80//! might find [`handy`](https://crates.io/crates/handy),
81//! [`slotmap`](https://crates.io/crates/slotmap), or
82//! [`slab`](https://crates.io/crates/slab) to be closer what you want.
83//!
84//! ## FAQ
85//!
86//! #### Wouldn't `define_index_type` be better as a proc macro?
87//!
88//! Probably. It's not a proc macro because I tend to avoid them where possible
89//! due to wanting to minimize compile times. If the issues around proc-macro
90//! compile times are fixed, then I'll revisit this.
91//!
92//! I also may eventually add a proc-macro feature which is not required, but
93//! avoids some of the grossness.
94//!
95//! #### Does `define_index_type` do too much?
96//!
97//! Possibly. It defines a type, implements a bunch of functions on it, and
98//! quite a few traits. That said, it's intended to be a very painless journey
99//! from `Vec<T>` + `usize` to `IndexVec<I, T>`. If it left it up to the
100//! developer to do those things, it would be too annoying to be worth using.
101//!
102//! #### The syntax for the options in `define_index_type` is terrible.
103//!
104//! I'm open to suggestions.
105//!
106//! #### Does it support no_std?
107//!
108//! Yes, although it uses `extern crate alloc;`, of course.
109//!
110//! #### Does it support serde?
111//!
112//! Yes, but only if you turn on the `serde` feature.
113//!
114//! #### What features are planned?
115//!
116//! Planned is a bit strong but here are the things I would find useful.
117//!
118//! - Support any remaining parts of the slice/vec api.
119//! - Add typesafe wrappers for SmallVec/ArrayVec (behind a cargo `feature`, of
120//!   course).
121//! - Better syntax for the define_index_type macro (no concrete ideas).
122//! - Allow the generated type to be a tuple struct, or use a specific field
123//!   name.
124//! - Allow use of indices for string types (the primary benefit here would
125//!   probably be the ability to e.g. use u32 without too much pain rather than
126//!   mixing up indices from different strings -- but you never know!)
127//! - Allow index types such as NonZeroU32 and such, if it can be done sanely.
128//! - ...
129//!
130#![allow(clippy::partialeq_ne_impl)]
131#![no_std]
132extern crate alloc;
133
134use alloc::borrow::{Cow, ToOwned};
135use alloc::boxed::Box;
136use alloc::vec;
137use alloc::vec::Vec;
138use core::borrow::{Borrow, BorrowMut};
139use core::fmt;
140use core::fmt::Debug;
141use core::hash::Hash;
142use core::iter::{self, FromIterator};
143use core::marker::PhantomData;
144use core::ops::Range;
145use core::slice;
146mod idxslice;
147mod indexing;
148pub use idxslice::{IndexBox, IndexSlice};
149pub use indexing::{IdxRangeBounds, IdxSliceIndex};
150
151#[macro_use]
152mod macros;
153
154#[cfg(any(test, feature = "example_generated"))]
155pub mod example_generated;
156
157/// Represents a wrapped value convertable to and from a `usize`.
158///
159/// Generally you implement this via the [`define_index_type!`] macro, rather
160/// than manually implementing it.
161///
162/// # Overflow
163///
164/// `Idx` impls are allowed to be smaller than `usize`, which means converting
165/// `usize` to an `Idx` implementation might have to handle overflow.
166///
167/// The way overflow is handled is up to the implementation of `Idx`, but it's
168/// generally panicing, unless it was turned off via the
169/// `DISABLE_MAX_INDEX_CHECK` option in [`define_index_type!`]. If you need more
170/// subtle handling than this, then you're on your own (or, well, either handle
171/// it earlier, or pick a bigger index type).
172///
173/// Note: I'm open for suggestions on how to handle this case, but do not want
174/// the typical cases (E.g. Idx is a newtyped usize or u32), to become more
175/// complex.
176pub trait Idx: Copy + 'static + Ord + Debug + Hash {
177    /// Construct an Index from a usize. This is equivalent to `From<usize>`.
178    ///
179    /// Note that this will panic if `idx` does not fit (unless checking has
180    /// been disabled, as mentioned above). Also note that `Idx` implementations
181    /// are free to define what "fit" means as they desire.
182    fn from_usize(idx: usize) -> Self;
183
184    /// Get the underlying index. This is equivalent to `Into<usize>`
185    fn index(self) -> usize;
186}
187
188/// A macro equivalent to the stdlib's `vec![]`, but producing an `IndexVec`.
189#[macro_export]
190macro_rules! index_vec {
191    ($($tokens:tt)*) => {
192        $crate::IndexVec::from_vec(vec![$($tokens)*])
193    }
194}
195
196/// A macro similar to the stdlib's `vec![]`, but producing an
197/// `Box<IndexSlice<I, [T]>>` (That is, an `IndexBox<I, [T]>`).
198#[macro_export]
199macro_rules! index_box {
200    ($($tokens:tt)*) => {
201        $crate::IndexVec::from_vec(vec![$($tokens)*]).into_boxed_slice()
202    }
203}
204
205/// A Vec that only accepts indices of a specific type.
206///
207/// This is a thin wrapper around `Vec`, to the point where the backing vec is a
208/// public property (called `raw`). This is in part because I know this API is
209/// not a complete mirror of Vec's (patches welcome). In the worst case, you can
210/// always do what you need to the Vec itself.
211///
212/// Note that this implements Deref/DerefMut to [`IndexSlice`], and so all the
213/// methods on IndexSlice are available as well. See it's documentation for some
214/// further information.
215///
216/// The following extensions to the Vec APIs are added (in addition to the ones
217/// mentioned in IndexSlice's documentation):
218///
219/// - [`IndexVec::next_idx`], [`IndexSlice::last_idx`] give the next and most
220///   recent index returned by `push`.
221/// - [`IndexVec::push`] returns the index the item was inserted at.
222#[derive(PartialEq, Eq, PartialOrd, Ord, Hash)]
223pub struct IndexVec<I: Idx, T> {
224    /// Our wrapped Vec.
225    pub raw: Vec<T>,
226    _marker: PhantomData<fn(&I)>,
227}
228
229// Whether `IndexVec` is `Send` depends only on the data,
230// not the phantom data.
231#[allow(renamed_and_removed_lints, suspicious_auto_trait_impls)]
232unsafe impl<I: Idx, T> Send for IndexVec<I, T> where T: Send {}
233
234impl<I: Idx, T: fmt::Debug> fmt::Debug for IndexVec<I, T> {
235    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
236        fmt::Debug::fmt(&self.raw, fmt)
237    }
238}
239type Enumerated<Iter, I, T> = iter::Map<iter::Enumerate<Iter>, fn((usize, T)) -> (I, T)>;
240
241impl<I: Idx, T> IndexVec<I, T> {
242    /// Construct a new IndexVec.
243    #[inline]
244    pub fn new() -> Self {
245        IndexVec {
246            raw: Vec::new(),
247            _marker: PhantomData,
248        }
249    }
250
251    /// Construct a `IndexVec` from a `Vec<T>`.
252    ///
253    /// Panics if it's length is too large for our index type.
254    #[inline]
255    pub fn from_vec(vec: Vec<T>) -> Self {
256        // See if `I::from_usize` might be upset by this length.
257        let _ = I::from_usize(vec.len());
258        IndexVec {
259            raw: vec,
260            _marker: PhantomData,
261        }
262    }
263
264    /// Construct an IndexVec that can hold at least `capacity` items before
265    /// reallocating. See [`Vec::with_capacity`].
266    #[inline]
267    pub fn with_capacity(capacity: usize) -> Self {
268        IndexVec {
269            raw: Vec::with_capacity(capacity),
270            _marker: PhantomData,
271        }
272    }
273
274    /// Similar to `self.into_iter().enumerate()` but with indices of `I` and
275    /// not `usize`.
276    #[inline(always)]
277    pub fn into_iter_enumerated(self) -> Enumerated<vec::IntoIter<T>, I, T> {
278        self.raw
279            .into_iter()
280            .enumerate()
281            .map(|(i, t)| (I::from_usize(i), t))
282    }
283
284    /// Creates a splicing iterator that replaces the specified range in the
285    /// vector with the given `replace_with` iterator and yields the removed
286    /// items. See [`Vec::splice`]
287    #[inline]
288    pub fn splice<R, It>(
289        &mut self,
290        range: R,
291        replace_with: It,
292    ) -> vec::Splice<<It as IntoIterator>::IntoIter>
293    where
294        It: IntoIterator<Item = T>,
295        R: IdxRangeBounds<I>,
296    {
297        self.raw.splice(range.into_range(), replace_with)
298    }
299
300    /// Similar to `self.drain(r).enumerate()` but with indices of `I` and not
301    /// `usize`.
302    #[inline]
303    pub fn drain_enumerated<R: IdxRangeBounds<I>>(
304        &mut self,
305        range: R,
306    ) -> Enumerated<vec::Drain<'_, T>, I, T> {
307        self.raw
308            .drain(range.into_range())
309            .enumerate()
310            .map(|(i, t)| (I::from_usize(i), t))
311    }
312
313    /// Gives the next index that will be assigned when `push` is
314    /// called.
315    #[inline]
316    pub fn next_idx(&self) -> I {
317        I::from_usize(self.len())
318    }
319
320    /// Get a the storage as a `&[T]`
321    #[inline(always)]
322    pub fn as_raw_slice(&self) -> &[T] {
323        &self.raw
324    }
325
326    /// Get a the storage as a `&mut [T]`
327    #[inline(always)]
328    pub fn as_raw_slice_mut(&mut self) -> &mut [T] {
329        &mut self.raw
330    }
331
332    /// Equivalent to accessing our `raw` field, but as a function.
333    #[inline(always)]
334    pub fn as_vec(&self) -> &Vec<T> {
335        &self.raw
336    }
337
338    /// Equivalent to accessing our `raw` field mutably, but as a function, if
339    /// that's what you'd prefer.
340    #[inline(always)]
341    pub fn as_mut_vec(&mut self) -> &mut Vec<T> {
342        &mut self.raw
343    }
344
345    /// Push a new item onto the vector, and return it's index.
346    #[inline]
347    pub fn push(&mut self, d: T) -> I {
348        let idx = I::from_usize(self.len());
349        self.raw.push(d);
350        idx
351    }
352
353    /// Pops the last item off, returning it. See [`Vec::pop`].
354    #[inline]
355    pub fn pop(&mut self) -> Option<T> {
356        self.raw.pop()
357    }
358
359    /// Converts the vector into an owned IdxSlice, dropping excess capacity.
360    #[inline]
361    pub fn into_boxed_slice(self) -> alloc::boxed::Box<IndexSlice<I, [T]>> {
362        let b = self.raw.into_boxed_slice();
363        unsafe { Box::from_raw(Box::into_raw(b) as *mut IndexSlice<I, [T]>) }
364    }
365
366    /// Return an iterator that removes the items from the requested range. See
367    /// [`Vec::drain`].
368    ///
369    /// See also [`IndexVec::drain_enumerated`], which gives you indices (of the
370    /// correct type) as you iterate.
371    #[inline]
372    pub fn drain<R: IdxRangeBounds<I>>(&mut self, range: R) -> vec::Drain<'_, T> {
373        self.raw.drain(range.into_range())
374    }
375
376    /// Shrinks the capacity of the vector as much as possible.
377    #[inline]
378    pub fn shrink_to_fit(&mut self) {
379        self.raw.shrink_to_fit()
380    }
381
382    /// Shortens the vector, keeping the first `len` elements and dropping
383    /// the rest. See [`Vec::truncate`]
384    #[inline]
385    pub fn truncate(&mut self, a: usize) {
386        self.raw.truncate(a)
387    }
388
389    /// Clear our vector. See [`Vec::clear`].
390    #[inline]
391    pub fn clear(&mut self) {
392        self.raw.clear()
393    }
394
395    /// Reserve capacity for `c` more elements. See [`Vec::reserve`]
396    #[inline]
397    pub fn reserve(&mut self, c: usize) {
398        self.raw.reserve(c)
399    }
400
401    /// Get a ref to the item at the provided index, or None for out of bounds.
402    #[inline]
403    pub fn get<J: IdxSliceIndex<I, T>>(&self, index: J) -> Option<&J::Output> {
404        index.get(self.as_slice())
405    }
406
407    /// Get a mut ref to the item at the provided index, or None for out of
408    /// bounds
409    #[inline]
410    pub fn get_mut<J: IdxSliceIndex<I, T>>(&mut self, index: J) -> Option<&mut J::Output> {
411        index.get_mut(self.as_mut_slice())
412    }
413
414    /// Resize ourselves in-place to `new_len`. See [`Vec::resize`].
415    #[inline]
416    pub fn resize(&mut self, new_len: usize, value: T)
417    where
418        T: Clone,
419    {
420        self.raw.resize(new_len, value)
421    }
422
423    /// Resize ourselves in-place to `new_len`. See [`Vec::resize_with`].
424    #[inline]
425    pub fn resize_with<F: FnMut() -> T>(&mut self, new_len: usize, f: F) {
426        self.raw.resize_with(new_len, f)
427    }
428
429    /// Moves all the elements of `other` into `Self`, leaving `other` empty.
430    /// See [`Vec::append`].
431    #[inline]
432    pub fn append(&mut self, other: &mut Self) {
433        self.raw.append(&mut other.raw)
434    }
435
436    /// Splits the collection into two at the given index. See
437    /// [`Vec::split_off`].
438    #[inline]
439    pub fn split_off(&mut self, idx: I) -> Self {
440        Self::from_vec(self.raw.split_off(idx.index()))
441    }
442
443    /// Remove the item at `index`. See [`Vec::remove`].
444    #[inline]
445    pub fn remove(&mut self, index: I) -> T {
446        self.raw.remove(index.index())
447    }
448
449    /// Remove the item at `index` without maintaining order. See
450    /// [`Vec::swap_remove`].
451    #[inline]
452    pub fn swap_remove(&mut self, index: I) -> T {
453        self.raw.swap_remove(index.index())
454    }
455
456    /// Insert an item at `index`. See [`Vec::insert`].
457    #[inline]
458    pub fn insert(&mut self, index: I, element: T) {
459        self.raw.insert(index.index(), element)
460    }
461
462    /// Append all items in the slice to the end of our vector.
463    ///
464    /// See [`Vec::extend_from_slice`].
465    #[inline]
466    pub fn extend_from_slice(&mut self, other: &IndexSlice<I, [T]>)
467    where
468        T: Clone,
469    {
470        self.raw.extend_from_slice(&other.raw)
471    }
472
473    /// Forwards to the `Vec::retain` implementation.
474    #[inline]
475    pub fn retain<F: FnMut(&T) -> bool>(&mut self, f: F) {
476        self.raw.retain(f)
477    }
478
479    /// Forwards to the `Vec::dedup_by_key` implementation.
480    #[inline]
481    pub fn dedup_by_key<F: FnMut(&mut T) -> K, K: PartialEq>(&mut self, key: F) {
482        self.raw.dedup_by_key(key)
483    }
484
485    /// Forwards to the `Vec::dedup` implementation.
486    #[inline]
487    pub fn dedup(&mut self)
488    where
489        T: PartialEq,
490    {
491        self.raw.dedup()
492    }
493
494    /// Forwards to the `Vec::dedup_by` implementation.
495    #[inline]
496    pub fn dedup_by<F: FnMut(&mut T, &mut T) -> bool>(&mut self, same_bucket: F) {
497        self.raw.dedup_by(same_bucket)
498    }
499
500    /// Get a IndexSlice over this vector. See `as_raw_slice` for converting to
501    /// a `&[T]` (or access `self.raw`).
502    #[inline(always)]
503    pub fn as_slice(&self) -> &IndexSlice<I, [T]> {
504        IndexSlice::new(&self.raw)
505    }
506
507    /// Get a mutable IndexSlice over this vector. See `as_raw_slice_mut` for
508    /// converting to a `&mut [T]` (or access `self.raw`).
509    #[inline(always)]
510    pub fn as_mut_slice(&mut self) -> &mut IndexSlice<I, [T]> {
511        IndexSlice::new_mut(&mut self.raw)
512    }
513}
514
515impl<I: Idx, T> Default for IndexVec<I, T> {
516    #[inline]
517    fn default() -> Self {
518        Self::new()
519    }
520}
521
522impl<I: Idx, T> Extend<T> for IndexVec<I, T> {
523    #[inline]
524    fn extend<J: IntoIterator<Item = T>>(&mut self, iter: J) {
525        self.raw.extend(iter);
526    }
527}
528
529impl<'a, I: Idx, T: 'a + Copy> Extend<&'a T> for IndexVec<I, T> {
530    #[inline]
531    fn extend<J: IntoIterator<Item = &'a T>>(&mut self, iter: J) {
532        self.raw.extend(iter);
533    }
534}
535
536impl<I: Idx, T> FromIterator<T> for IndexVec<I, T> {
537    #[inline]
538    fn from_iter<J>(iter: J) -> Self
539    where
540        J: IntoIterator<Item = T>,
541    {
542        IndexVec {
543            raw: FromIterator::from_iter(iter),
544            _marker: PhantomData,
545        }
546    }
547}
548
549impl<I: Idx, T> IntoIterator for IndexVec<I, T> {
550    type Item = T;
551    type IntoIter = vec::IntoIter<T>;
552
553    #[inline]
554    fn into_iter(self) -> vec::IntoIter<T> {
555        self.raw.into_iter()
556    }
557}
558
559impl<'a, I: Idx, T> IntoIterator for &'a IndexVec<I, T> {
560    type Item = &'a T;
561    type IntoIter = slice::Iter<'a, T>;
562
563    #[inline]
564    fn into_iter(self) -> slice::Iter<'a, T> {
565        self.raw.iter()
566    }
567}
568
569impl<'a, I: Idx, T> IntoIterator for &'a mut IndexVec<I, T> {
570    type Item = &'a mut T;
571    type IntoIter = slice::IterMut<'a, T>;
572
573    #[inline]
574    fn into_iter(self) -> slice::IterMut<'a, T> {
575        self.raw.iter_mut()
576    }
577}
578
579impl<I: Idx, T> From<IndexVec<I, T>> for Box<IndexSlice<I, [T]>> {
580    #[inline]
581    fn from(src: IndexVec<I, T>) -> Self {
582        src.into_boxed_slice()
583    }
584}
585
586impl<I: Idx, T> From<Box<IndexSlice<I, [T]>>> for IndexVec<I, T> {
587    #[inline]
588    fn from(src: Box<IndexSlice<I, [T]>>) -> Self {
589        src.into_vec()
590    }
591}
592
593impl<'a, I: Idx, T> From<Cow<'a, IndexSlice<I, [T]>>> for IndexVec<I, T>
594where
595    IndexSlice<I, [T]>: ToOwned<Owned = IndexVec<I, T>>,
596{
597    #[inline]
598    fn from(s: Cow<'a, IndexSlice<I, [T]>>) -> IndexVec<I, T> {
599        s.into_owned()
600    }
601}
602
603impl<'a, I: Idx, T: Clone> From<&'a IndexSlice<I, [T]>> for IndexVec<I, T> {
604    #[inline]
605    fn from(src: &'a IndexSlice<I, [T]>) -> Self {
606        src.to_owned()
607    }
608}
609impl<'a, I: Idx, T: Clone> From<&'a mut IndexSlice<I, [T]>> for IndexVec<I, T> {
610    #[inline]
611    fn from(src: &'a mut IndexSlice<I, [T]>) -> Self {
612        src.to_owned()
613    }
614}
615
616impl<I: Idx, T> From<Vec<T>> for IndexVec<I, T> {
617    #[inline]
618    fn from(v: Vec<T>) -> Self {
619        Self {
620            raw: v,
621            _marker: PhantomData,
622        }
623    }
624}
625
626impl<I: Idx, T: Clone> Clone for IndexVec<I, T> {
627    #[inline]
628    fn clone(&self) -> Self {
629        Self {
630            raw: self.raw.clone(),
631            _marker: PhantomData,
632        }
633    }
634    #[inline]
635    fn clone_from(&mut self, o: &Self) {
636        self.raw.clone_from(&o.raw);
637    }
638}
639
640impl<I: Idx, A> AsRef<[A]> for IndexVec<I, A> {
641    #[inline]
642    fn as_ref(&self) -> &[A] {
643        &self.raw
644    }
645}
646
647impl<I: Idx, A> AsMut<[A]> for IndexVec<I, A> {
648    #[inline]
649    fn as_mut(&mut self) -> &mut [A] {
650        &mut self.raw
651    }
652}
653
654impl<I: Idx, A> AsRef<IndexSlice<I, [A]>> for IndexVec<I, A> {
655    #[inline]
656    fn as_ref(&self) -> &IndexSlice<I, [A]> {
657        IndexSlice::new(&self.raw)
658    }
659}
660
661impl<I: Idx, A> AsMut<IndexSlice<I, [A]>> for IndexVec<I, A> {
662    #[inline]
663    fn as_mut(&mut self) -> &mut IndexSlice<I, [A]> {
664        IndexSlice::new_mut(&mut self.raw)
665    }
666}
667
668impl<I: Idx, A> core::ops::Deref for IndexVec<I, A> {
669    type Target = IndexSlice<I, [A]>;
670    #[inline]
671    fn deref(&self) -> &IndexSlice<I, [A]> {
672        IndexSlice::new(&self.raw)
673    }
674}
675
676impl<I: Idx, A> core::ops::DerefMut for IndexVec<I, A> {
677    #[inline]
678    fn deref_mut(&mut self) -> &mut IndexSlice<I, [A]> {
679        IndexSlice::new_mut(&mut self.raw)
680    }
681}
682
683impl<I: Idx, T> Borrow<IndexSlice<I, [T]>> for IndexVec<I, T> {
684    #[inline]
685    fn borrow(&self) -> &IndexSlice<I, [T]> {
686        self.as_slice()
687    }
688}
689
690impl<I: Idx, T> BorrowMut<IndexSlice<I, [T]>> for IndexVec<I, T> {
691    #[inline]
692    fn borrow_mut(&mut self) -> &mut IndexSlice<I, [T]> {
693        self.as_mut_slice()
694    }
695}
696
697macro_rules! impl_partialeq {
698    ($Lhs: ty, $Rhs: ty) => {
699        impl<'a, 'b, A, B, I: Idx> PartialEq<$Rhs> for $Lhs
700        where
701            A: PartialEq<B>,
702        {
703            #[inline]
704            fn eq(&self, other: &$Rhs) -> bool {
705                self[..] == other[..]
706            }
707            #[inline]
708            fn ne(&self, other: &$Rhs) -> bool {
709                self[..] != other[..]
710            }
711        }
712    };
713}
714
715macro_rules! impl_partialeq2 {
716    ($Lhs: ty, $Rhs: ty) => {
717        impl<'a, 'b, A, B, I: Idx, J: Idx> PartialEq<$Rhs> for $Lhs
718        where
719            A: PartialEq<B>,
720        {
721            #[inline]
722            fn eq(&self, other: &$Rhs) -> bool {
723                self.raw[..] == other.raw[..]
724            }
725            #[inline]
726            fn ne(&self, other: &$Rhs) -> bool {
727                self.raw[..] != other.raw[..]
728            }
729        }
730    };
731}
732
733impl_partialeq! { IndexVec<I, A>, Vec<B> }
734impl_partialeq! { IndexVec<I, A>, &'b [B] }
735impl_partialeq! { IndexVec<I, A>, &'b mut [B] }
736
737impl_partialeq2! { IndexVec<I, A>, &'b IndexSlice<J, [B]> }
738impl_partialeq2! { IndexVec<I, A>, &'b mut IndexSlice<J, [B]> }
739
740impl_partialeq! { &'a IndexSlice<I, [A]>, Vec<B> }
741impl_partialeq! { &'a mut IndexSlice<I, [A]>, Vec<B> }
742
743impl_partialeq! { IndexSlice<I, [A]>, &'b [B] }
744impl_partialeq! { IndexSlice<I, [A]>, &'b mut [B] }
745
746impl_partialeq2! { &'a IndexSlice<I, [A]>, IndexVec<J, B> }
747impl_partialeq2! { &'a mut IndexSlice<I, [A]>, IndexVec<J, B> }
748
749impl_partialeq2! { IndexSlice<I, [A]>, &'a IndexSlice<J, [B]> }
750impl_partialeq2! { IndexSlice<I, [A]>, &'a mut IndexSlice<J, [B]> }
751
752macro_rules! array_impls {
753    ($($N: expr)+) => {$(
754        impl_partialeq! { IndexVec<I, A>, [B; $N] }
755        impl_partialeq! { IndexVec<I, A>, &'b [B; $N] }
756        impl_partialeq! { IndexSlice<I, [A]>, [B; $N] }
757        impl_partialeq! { IndexSlice<I, [A]>, &'b [B; $N] }
758        // impl_partialeq! { &'a IndexSlice<I, [A]>, [B; $N] }
759        // impl_partialeq! { &'a IndexSlice<I, [A]>, &'b [B; $N] }
760    )+};
761}
762
763array_impls! {
764     0  1  2  3  4  5  6  7  8  9
765    10 11 12 13 14 15 16 17 18 19
766    20 21 22 23 24 25 26 27 28 29
767    30 31 32
768}
769
770#[inline(never)]
771#[cold]
772#[doc(hidden)]
773pub fn __max_check_fail(u: usize, max: usize) -> ! {
774    panic!(
775        "index_vec index overflow: {} is outside the range [0, {})",
776        u, max,
777    )
778}
779
780#[cfg(feature = "serde")]
781impl<I: Idx, T: serde::ser::Serialize> serde::ser::Serialize for IndexVec<I, T> {
782    fn serialize<S: serde::ser::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
783        self.raw.serialize(serializer)
784    }
785}
786
787#[cfg(feature = "serde")]
788impl<'de, I: Idx, T: serde::de::Deserialize<'de>> serde::de::Deserialize<'de> for IndexVec<I, T> {
789    fn deserialize<D: serde::de::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
790        Vec::deserialize(deserializer).map(Self::from_vec)
791    }
792}
793
794#[cfg(feature = "serde")]
795impl<I: Idx, T: serde::ser::Serialize> serde::ser::Serialize for IndexBox<I, T> {
796    fn serialize<S: serde::ser::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
797        self.raw.serialize(serializer)
798    }
799}
800
801#[cfg(feature = "serde")]
802impl<'de, I: Idx, T: serde::de::Deserialize<'de>> serde::de::Deserialize<'de> for IndexBox<I, [T]> {
803    fn deserialize<D: serde::de::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
804        Box::<[T]>::deserialize(deserializer).map(Into::into)
805    }
806}
807
808#[cfg(feature = "rkyv")]
809impl<I: Idx, T: rkyv::Archive> rkyv::Archive for IndexVec<I, T> {
810    type Archived = <Vec<T> as rkyv::Archive>::Archived;
811    type Resolver = <Vec<T> as rkyv::Archive>::Resolver;
812
813    #[inline]
814    unsafe fn resolve(&self, pos: usize, resolver: Self::Resolver, out: *mut Self::Archived) {
815        self.raw.resolve(pos, resolver, out)
816    }
817}
818
819#[cfg(feature = "rkyv")]
820impl<
821        I: Idx,
822        T: rkyv::Serialize<S>,
823        S: rkyv::ser::ScratchSpace + rkyv::ser::Serializer + ?Sized,
824    > rkyv::Serialize<S> for IndexVec<I, T>
825{
826    #[inline]
827    fn serialize(
828        &self,
829        serializer: &mut S,
830    ) -> Result<Self::Resolver, <S as rkyv::Fallible>::Error> {
831        self.raw.serialize(serializer)
832    }
833}
834
835#[cfg(feature = "rkyv")]
836impl<I: Idx, T: rkyv::Archive, D: rkyv::Fallible + ?Sized> rkyv::Deserialize<IndexVec<I, T>, D>
837    for rkyv::vec::ArchivedVec<T::Archived>
838where
839    [T::Archived]: rkyv::DeserializeUnsized<[T], D>,
840{
841    #[inline]
842    fn deserialize(&self, deserializer: &mut D) -> Result<IndexVec<I, T>, D::Error> {
843        let raw = rkyv::vec::ArchivedVec::deserialize(self, deserializer)?;
844
845        Ok(IndexVec::from_vec(raw))
846    }
847}