Merging upstream version 1.73.0+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

4 files changed, 856 insertions, 0 deletions

diff --git a/vendor/la-arena/.cargo-checksum.json b/vendor/la-arena/.cargo-checksum.json
new file mode 100644
index 000000000..15724b475
--- /dev/null
+++ b/vendor/la-arena/.cargo-checksum.json
@@ -0,0 +1 @@
+{"files":{"Cargo.toml":"e0ab2202ba612192387ce7931e940310ea6e80890fab03085f9398242ea91f6e","src/lib.rs":"3bb0569f60631442a07c9ebc31dc93d15ee34ee4ffdcdd6f8e5d527acae87d3f","src/map.rs":"c771c4921050eb5256759214995cbe3343217178efe9df14885cc715eaa0fc99"},"package":"3752f229dcc5a481d60f385fa479ff46818033d881d2d801aa27dffcfb5e8306"}
\ No newline at end of file
diff --git a/vendor/la-arena/Cargo.toml b/vendor/la-arena/Cargo.toml
new file mode 100644
index 000000000..f38dc4311
--- /dev/null
+++ b/vendor/la-arena/Cargo.toml
@@ -0,0 +1,25 @@
+# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO
+#
+# When uploading crates to the registry Cargo will automatically
+# "normalize" Cargo.toml files for maximal compatibility
+# with all versions of Cargo and also rewrite `path` dependencies
+# to registry (e.g., crates.io) dependencies.
+#
+# If you are reading this file be aware that the original Cargo.toml
+# will likely look very different (and much more reasonable).
+# See Cargo.toml.orig for the original contents.
+
+[package]
+edition = "2021"
+rust-version = "1.56"
+name = "la-arena"
+version = "0.3.1"
+description = "Simple index-based arena without deletion."
+documentation = "https://docs.rs/la-arena"
+categories = [
+    "data-structures",
+    "memory-management",
+    "rust-patterns",
+]
+license = "MIT OR Apache-2.0"
+repository = "https://github.com/rust-lang/rust-analyzer/tree/master/lib/la-arena"
diff --git a/vendor/la-arena/src/lib.rs b/vendor/la-arena/src/lib.rs
new file mode 100644
index 000000000..f39c3a3e4
--- /dev/null
+++ b/vendor/la-arena/src/lib.rs
@@ -0,0 +1,526 @@
+//! Yet another index-based arena.
+
+#![warn(rust_2018_idioms, unused_lifetimes, semicolon_in_expressions_from_macros)]
+#![warn(missing_docs)]
+
+use std::{
+    cmp, fmt,
+    hash::{Hash, Hasher},
+    iter::{Enumerate, FusedIterator},
+    marker::PhantomData,
+    ops::{Index, IndexMut, Range, RangeInclusive},
+};
+
+mod map;
+pub use map::{ArenaMap, Entry, OccupiedEntry, VacantEntry};
+
+/// The raw index of a value in an arena.
+#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
+pub struct RawIdx(u32);
+
+impl RawIdx {
+    /// Constructs a [`RawIdx`] from a u32.
+    pub const fn from_u32(u32: u32) -> Self {
+        RawIdx(u32)
+    }
+
+    /// Deconstructs a [`RawIdx`] into the underlying u32.
+    pub const fn into_u32(self) -> u32 {
+        self.0
+    }
+}
+
+impl From<RawIdx> for u32 {
+    #[inline]
+    fn from(raw: RawIdx) -> u32 {
+        raw.0
+    }
+}
+
+impl From<u32> for RawIdx {
+    #[inline]
+    fn from(idx: u32) -> RawIdx {
+        RawIdx(idx)
+    }
+}
+
+impl fmt::Debug for RawIdx {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        self.0.fmt(f)
+    }
+}
+
+impl fmt::Display for RawIdx {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        self.0.fmt(f)
+    }
+}
+
+/// The index of a value allocated in an arena that holds `T`s.
+pub struct Idx<T> {
+    raw: RawIdx,
+    _ty: PhantomData<fn() -> T>,
+}
+
+impl<T> Ord for Idx<T> {
+    fn cmp(&self, other: &Self) -> cmp::Ordering {
+        self.raw.cmp(&other.raw)
+    }
+}
+
+impl<T> PartialOrd for Idx<T> {
+    fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
+        self.raw.partial_cmp(&other.raw)
+    }
+}
+
+impl<T> Clone for Idx<T> {
+    fn clone(&self) -> Self {
+        *self
+    }
+}
+impl<T> Copy for Idx<T> {}
+
+impl<T> PartialEq for Idx<T> {
+    fn eq(&self, other: &Idx<T>) -> bool {
+        self.raw == other.raw
+    }
+}
+impl<T> Eq for Idx<T> {}
+
+impl<T> Hash for Idx<T> {
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        self.raw.hash(state);
+    }
+}
+
+impl<T> fmt::Debug for Idx<T> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        let mut type_name = std::any::type_name::<T>();
+        if let Some(idx) = type_name.rfind(':') {
+            type_name = &type_name[idx + 1..];
+        }
+        write!(f, "Idx::<{}>({})", type_name, self.raw)
+    }
+}
+
+impl<T> Idx<T> {
+    /// Creates a new index from a [`RawIdx`].
+    pub const fn from_raw(raw: RawIdx) -> Self {
+        Idx { raw, _ty: PhantomData }
+    }
+
+    /// Converts this index into the underlying [`RawIdx`].
+    pub const fn into_raw(self) -> RawIdx {
+        self.raw
+    }
+}
+
+/// A range of densely allocated arena values.
+pub struct IdxRange<T> {
+    range: Range<u32>,
+    _p: PhantomData<T>,
+}
+
+impl<T> IdxRange<T> {
+    /// Creates a new index range
+    /// inclusive of the start value and exclusive of the end value.
+    ///
+    /// ```
+    /// let mut arena = la_arena::Arena::new();
+    /// let a = arena.alloc("a");
+    /// let b = arena.alloc("b");
+    /// let c = arena.alloc("c");
+    /// let d = arena.alloc("d");
+    ///
+    /// let range = la_arena::IdxRange::new(b..d);
+    /// assert_eq!(&arena[range], &["b", "c"]);
+    /// ```
+    pub fn new(range: Range<Idx<T>>) -> Self {
+        Self { range: range.start.into_raw().into()..range.end.into_raw().into(), _p: PhantomData }
+    }
+
+    /// Creates a new index range
+    /// inclusive of the start value and end value.
+    ///
+    /// ```
+    /// let mut arena = la_arena::Arena::new();
+    /// let foo = arena.alloc("foo");
+    /// let bar = arena.alloc("bar");
+    /// let baz = arena.alloc("baz");
+    ///
+    /// let range = la_arena::IdxRange::new_inclusive(foo..=baz);
+    /// assert_eq!(&arena[range], &["foo", "bar", "baz"]);
+    ///
+    /// let range = la_arena::IdxRange::new_inclusive(foo..=foo);
+    /// assert_eq!(&arena[range], &["foo"]);
+    /// ```
+    pub fn new_inclusive(range: RangeInclusive<Idx<T>>) -> Self {
+        Self {
+            range: u32::from(range.start().into_raw())..u32::from(range.end().into_raw()) + 1,
+            _p: PhantomData,
+        }
+    }
+
+    /// Returns whether the index range is empty.
+    ///
+    /// ```
+    /// let mut arena = la_arena::Arena::new();
+    /// let one = arena.alloc(1);
+    /// let two = arena.alloc(2);
+    ///
+    /// assert!(la_arena::IdxRange::new(one..one).is_empty());
+    /// ```
+    pub fn is_empty(&self) -> bool {
+        self.range.is_empty()
+    }
+
+    /// Returns the start of the index range.
+    pub fn start(&self) -> Idx<T> {
+        Idx::from_raw(RawIdx::from(self.range.start))
+    }
+
+    /// Returns the end of the index range.
+    pub fn end(&self) -> Idx<T> {
+        Idx::from_raw(RawIdx::from(self.range.end))
+    }
+}
+
+impl<T> Iterator for IdxRange<T> {
+    type Item = Idx<T>;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.range.next().map(|raw| Idx::from_raw(raw.into()))
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.range.size_hint()
+    }
+
+    fn count(self) -> usize
+    where
+        Self: Sized,
+    {
+        self.range.count()
+    }
+
+    fn last(self) -> Option<Self::Item>
+    where
+        Self: Sized,
+    {
+        self.range.last().map(|raw| Idx::from_raw(raw.into()))
+    }
+
+    fn nth(&mut self, n: usize) -> Option<Self::Item> {
+        self.range.nth(n).map(|raw| Idx::from_raw(raw.into()))
+    }
+}
+
+impl<T> DoubleEndedIterator for IdxRange<T> {
+    fn next_back(&mut self) -> Option<Self::Item> {
+        self.range.next_back().map(|raw| Idx::from_raw(raw.into()))
+    }
+}
+
+impl<T> ExactSizeIterator for IdxRange<T> {}
+
+impl<T> FusedIterator for IdxRange<T> {}
+
+impl<T> fmt::Debug for IdxRange<T> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.debug_tuple(&format!("IdxRange::<{}>", std::any::type_name::<T>()))
+            .field(&self.range)
+            .finish()
+    }
+}
+
+impl<T> Clone for IdxRange<T> {
+    fn clone(&self) -> Self {
+        Self { range: self.range.clone(), _p: PhantomData }
+    }
+}
+
+impl<T> PartialEq for IdxRange<T> {
+    fn eq(&self, other: &Self) -> bool {
+        self.range == other.range
+    }
+}
+
+impl<T> Eq for IdxRange<T> {}
+
+/// Yet another index-based arena.
+#[derive(Clone, PartialEq, Eq, Hash)]
+pub struct Arena<T> {
+    data: Vec<T>,
+}
+
+impl<T: fmt::Debug> fmt::Debug for Arena<T> {
+    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
+        fmt.debug_struct("Arena").field("len", &self.len()).field("data", &self.data).finish()
+    }
+}
+
+impl<T> Arena<T> {
+    /// Creates a new empty arena.
+    ///
+    /// ```
+    /// let arena: la_arena::Arena<i32> = la_arena::Arena::new();
+    /// assert!(arena.is_empty());
+    /// ```
+    pub const fn new() -> Arena<T> {
+        Arena { data: Vec::new() }
+    }
+
+    /// Create a new empty arena with specific capacity.
+    ///
+    /// ```
+    /// let arena: la_arena::Arena<i32> = la_arena::Arena::with_capacity(42);
+    /// assert!(arena.is_empty());
+    /// ```
+    pub fn with_capacity(capacity: usize) -> Arena<T> {
+        Arena { data: Vec::with_capacity(capacity) }
+    }
+
+    /// Empties the arena, removing all contained values.
+    ///
+    /// ```
+    /// let mut arena = la_arena::Arena::new();
+    ///
+    /// arena.alloc(1);
+    /// arena.alloc(2);
+    /// arena.alloc(3);
+    /// assert_eq!(arena.len(), 3);
+    ///
+    /// arena.clear();
+    /// assert!(arena.is_empty());
+    /// ```
+    pub fn clear(&mut self) {
+        self.data.clear();
+    }
+
+    /// Returns the length of the arena.
+    ///
+    /// ```
+    /// let mut arena = la_arena::Arena::new();
+    /// assert_eq!(arena.len(), 0);
+    ///
+    /// arena.alloc("foo");
+    /// assert_eq!(arena.len(), 1);
+    ///
+    /// arena.alloc("bar");
+    /// assert_eq!(arena.len(), 2);
+    ///
+    /// arena.alloc("baz");
+    /// assert_eq!(arena.len(), 3);
+    /// ```
+    pub fn len(&self) -> usize {
+        self.data.len()
+    }
+
+    /// Returns whether the arena contains no elements.
+    ///
+    /// ```
+    /// let mut arena = la_arena::Arena::new();
+    /// assert!(arena.is_empty());
+    ///
+    /// arena.alloc(0.5);
+    /// assert!(!arena.is_empty());
+    /// ```
+    pub fn is_empty(&self) -> bool {
+        self.data.is_empty()
+    }
+
+    /// Allocates a new value on the arena, returning the value’s index.
+    ///
+    /// ```
+    /// let mut arena = la_arena::Arena::new();
+    /// let idx = arena.alloc(50);
+    ///
+    /// assert_eq!(arena[idx], 50);
+    /// ```
+    pub fn alloc(&mut self, value: T) -> Idx<T> {
+        let idx = self.next_idx();
+        self.data.push(value);
+        idx
+    }
+
+    /// Densely allocates multiple values, returning the values’ index range.
+    ///
+    /// ```
+    /// let mut arena = la_arena::Arena::new();
+    /// let range = arena.alloc_many(0..4);
+    ///
+    /// assert_eq!(arena[range], [0, 1, 2, 3]);
+    /// ```
+    pub fn alloc_many<II: IntoIterator<Item = T>>(&mut self, iter: II) -> IdxRange<T> {
+        let start = self.next_idx();
+        self.extend(iter);
+        let end = self.next_idx();
+        IdxRange::new(start..end)
+    }
+
+    /// Returns an iterator over the arena’s elements.
+    ///
+    /// ```
+    /// let mut arena = la_arena::Arena::new();
+    /// let idx1 = arena.alloc(20);
+    /// let idx2 = arena.alloc(40);
+    /// let idx3 = arena.alloc(60);
+    ///
+    /// let mut iterator = arena.iter();
+    /// assert_eq!(iterator.next(), Some((idx1, &20)));
+    /// assert_eq!(iterator.next(), Some((idx2, &40)));
+    /// assert_eq!(iterator.next(), Some((idx3, &60)));
+    /// ```
+    pub fn iter(
+        &self,
+    ) -> impl Iterator<Item = (Idx<T>, &T)> + ExactSizeIterator + DoubleEndedIterator + Clone {
+        self.data.iter().enumerate().map(|(idx, value)| (Idx::from_raw(RawIdx(idx as u32)), value))
+    }
+
+    /// Returns an iterator over the arena’s mutable elements.
+    ///
+    /// ```
+    /// let mut arena = la_arena::Arena::new();
+    /// let idx1 = arena.alloc(20);
+    ///
+    /// assert_eq!(arena[idx1], 20);
+    ///
+    /// let mut iterator = arena.iter_mut();
+    /// *iterator.next().unwrap().1 = 10;
+    /// drop(iterator);
+    ///
+    /// assert_eq!(arena[idx1], 10);
+    /// ```
+    pub fn iter_mut(
+        &mut self,
+    ) -> impl Iterator<Item = (Idx<T>, &mut T)> + ExactSizeIterator + DoubleEndedIterator {
+        self.data
+            .iter_mut()
+            .enumerate()
+            .map(|(idx, value)| (Idx::from_raw(RawIdx(idx as u32)), value))
+    }
+
+    /// Returns an iterator over the arena’s values.
+    ///
+    /// ```
+    /// let mut arena = la_arena::Arena::new();
+    /// let idx1 = arena.alloc(20);
+    /// let idx2 = arena.alloc(40);
+    /// let idx3 = arena.alloc(60);
+    ///
+    /// let mut iterator = arena.values();
+    /// assert_eq!(iterator.next(), Some(&20));
+    /// assert_eq!(iterator.next(), Some(&40));
+    /// assert_eq!(iterator.next(), Some(&60));
+    /// ```
+    pub fn values(&self) -> impl Iterator<Item = &T> + ExactSizeIterator + DoubleEndedIterator {
+        self.data.iter()
+    }
+
+    /// Returns an iterator over the arena’s mutable values.
+    ///
+    /// ```
+    /// let mut arena = la_arena::Arena::new();
+    /// let idx1 = arena.alloc(20);
+    ///
+    /// assert_eq!(arena[idx1], 20);
+    ///
+    /// let mut iterator = arena.values_mut();
+    /// *iterator.next().unwrap() = 10;
+    /// drop(iterator);
+    ///
+    /// assert_eq!(arena[idx1], 10);
+    /// ```
+    pub fn values_mut(
+        &mut self,
+    ) -> impl Iterator<Item = &mut T> + ExactSizeIterator + DoubleEndedIterator {
+        self.data.iter_mut()
+    }
+
+    /// Reallocates the arena to make it take up as little space as possible.
+    pub fn shrink_to_fit(&mut self) {
+        self.data.shrink_to_fit();
+    }
+
+    /// Returns the index of the next value allocated on the arena.
+    ///
+    /// This method should remain private to make creating invalid `Idx`s harder.
+    fn next_idx(&self) -> Idx<T> {
+        Idx::from_raw(RawIdx(self.data.len() as u32))
+    }
+}
+
+impl<T> AsMut<[T]> for Arena<T> {
+    fn as_mut(&mut self) -> &mut [T] {
+        self.data.as_mut()
+    }
+}
+
+impl<T> Default for Arena<T> {
+    fn default() -> Arena<T> {
+        Arena { data: Vec::new() }
+    }
+}
+
+impl<T> Index<Idx<T>> for Arena<T> {
+    type Output = T;
+    fn index(&self, idx: Idx<T>) -> &T {
+        let idx = idx.into_raw().0 as usize;
+        &self.data[idx]
+    }
+}
+
+impl<T> IndexMut<Idx<T>> for Arena<T> {
+    fn index_mut(&mut self, idx: Idx<T>) -> &mut T {
+        let idx = idx.into_raw().0 as usize;
+        &mut self.data[idx]
+    }
+}
+
+impl<T> Index<IdxRange<T>> for Arena<T> {
+    type Output = [T];
+    fn index(&self, range: IdxRange<T>) -> &[T] {
+        let start = range.range.start as usize;
+        let end = range.range.end as usize;
+        &self.data[start..end]
+    }
+}
+
+impl<T> FromIterator<T> for Arena<T> {
+    fn from_iter<I>(iter: I) -> Self
+    where
+        I: IntoIterator<Item = T>,
+    {
+        Arena { data: Vec::from_iter(iter) }
+    }
+}
+
+/// An iterator over the arena’s elements.
+pub struct IntoIter<T>(Enumerate<<Vec<T> as IntoIterator>::IntoIter>);
+
+impl<T> Iterator for IntoIter<T> {
+    type Item = (Idx<T>, T);
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.0.next().map(|(idx, value)| (Idx::from_raw(RawIdx(idx as u32)), value))
+    }
+}
+
+impl<T> IntoIterator for Arena<T> {
+    type Item = (Idx<T>, T);
+
+    type IntoIter = IntoIter<T>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        IntoIter(self.data.into_iter().enumerate())
+    }
+}
+
+impl<T> Extend<T> for Arena<T> {
+    fn extend<II: IntoIterator<Item = T>>(&mut self, iter: II) {
+        for t in iter {
+            self.alloc(t);
+        }
+    }
+}
diff --git a/vendor/la-arena/src/map.rs b/vendor/la-arena/src/map.rs
new file mode 100644
index 000000000..750f345b5
--- /dev/null
+++ b/vendor/la-arena/src/map.rs
@@ -0,0 +1,304 @@
+use std::iter::Enumerate;
+use std::marker::PhantomData;
+
+use crate::Idx;
+
+/// A map from arena indexes to some other type.
+/// Space requirement is O(highest index).
+#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
+pub struct ArenaMap<IDX, V> {
+    v: Vec<Option<V>>,
+    _ty: PhantomData<IDX>,
+}
+
+impl<T, V> ArenaMap<Idx<T>, V> {
+    /// Creates a new empty map.
+    pub const fn new() -> Self {
+        Self { v: Vec::new(), _ty: PhantomData }
+    }
+
+    /// Create a new empty map with specific capacity.
+    pub fn with_capacity(capacity: usize) -> Self {
+        Self { v: Vec::with_capacity(capacity), _ty: PhantomData }
+    }
+
+    /// Reserves capacity for at least additional more elements to be inserted in the map.
+    pub fn reserve(&mut self, additional: usize) {
+        self.v.reserve(additional);
+    }
+
+    /// Clears the map, removing all elements.
+    pub fn clear(&mut self) {
+        self.v.clear();
+    }
+
+    /// Shrinks the capacity of the map as much as possible.
+    pub fn shrink_to_fit(&mut self) {
+        let min_len = self.v.iter().rposition(|slot| slot.is_some()).map_or(0, |i| i + 1);
+        self.v.truncate(min_len);
+        self.v.shrink_to_fit();
+    }
+
+    /// Returns whether the map contains a value for the specified index.
+    pub fn contains_idx(&self, idx: Idx<T>) -> bool {
+        matches!(self.v.get(Self::to_idx(idx)), Some(Some(_)))
+    }
+
+    /// Removes an index from the map, returning the value at the index if the index was previously in the map.
+    pub fn remove(&mut self, idx: Idx<T>) -> Option<V> {
+        self.v.get_mut(Self::to_idx(idx))?.take()
+    }
+
+    /// Inserts a value associated with a given arena index into the map.
+    ///
+    /// If the map did not have this index present, None is returned.
+    /// Otherwise, the value is updated, and the old value is returned.
+    pub fn insert(&mut self, idx: Idx<T>, t: V) -> Option<V> {
+        let idx = Self::to_idx(idx);
+
+        self.v.resize_with((idx + 1).max(self.v.len()), || None);
+        self.v[idx].replace(t)
+    }
+
+    /// Returns a reference to the value associated with the provided index
+    /// if it is present.
+    pub fn get(&self, idx: Idx<T>) -> Option<&V> {
+        self.v.get(Self::to_idx(idx)).and_then(|it| it.as_ref())
+    }
+
+    /// Returns a mutable reference to the value associated with the provided index
+    /// if it is present.
+    pub fn get_mut(&mut self, idx: Idx<T>) -> Option<&mut V> {
+        self.v.get_mut(Self::to_idx(idx)).and_then(|it| it.as_mut())
+    }
+
+    /// Returns an iterator over the values in the map.
+    pub fn values(&self) -> impl Iterator<Item = &V> + DoubleEndedIterator {
+        self.v.iter().filter_map(|o| o.as_ref())
+    }
+
+    /// Returns an iterator over mutable references to the values in the map.
+    pub fn values_mut(&mut self) -> impl Iterator<Item = &mut V> + DoubleEndedIterator {
+        self.v.iter_mut().filter_map(|o| o.as_mut())
+    }
+
+    /// Returns an iterator over the arena indexes and values in the map.
+    pub fn iter(&self) -> impl Iterator<Item = (Idx<T>, &V)> + DoubleEndedIterator {
+        self.v.iter().enumerate().filter_map(|(idx, o)| Some((Self::from_idx(idx), o.as_ref()?)))
+    }
+
+    /// Returns an iterator over the arena indexes and values in the map.
+    pub fn iter_mut(&mut self) -> impl Iterator<Item = (Idx<T>, &mut V)> {
+        self.v
+            .iter_mut()
+            .enumerate()
+            .filter_map(|(idx, o)| Some((Self::from_idx(idx), o.as_mut()?)))
+    }
+
+    /// Gets the given key's corresponding entry in the map for in-place manipulation.
+    pub fn entry(&mut self, idx: Idx<T>) -> Entry<'_, Idx<T>, V> {
+        let idx = Self::to_idx(idx);
+        self.v.resize_with((idx + 1).max(self.v.len()), || None);
+        match &mut self.v[idx] {
+            slot @ Some(_) => Entry::Occupied(OccupiedEntry { slot, _ty: PhantomData }),
+            slot @ None => Entry::Vacant(VacantEntry { slot, _ty: PhantomData }),
+        }
+    }
+
+    fn to_idx(idx: Idx<T>) -> usize {
+        u32::from(idx.into_raw()) as usize
+    }
+
+    fn from_idx(idx: usize) -> Idx<T> {
+        Idx::from_raw((idx as u32).into())
+    }
+}
+
+impl<T, V> std::ops::Index<Idx<V>> for ArenaMap<Idx<V>, T> {
+    type Output = T;
+    fn index(&self, idx: Idx<V>) -> &T {
+        self.v[Self::to_idx(idx)].as_ref().unwrap()
+    }
+}
+
+impl<T, V> std::ops::IndexMut<Idx<V>> for ArenaMap<Idx<V>, T> {
+    fn index_mut(&mut self, idx: Idx<V>) -> &mut T {
+        self.v[Self::to_idx(idx)].as_mut().unwrap()
+    }
+}
+
+impl<T, V> Default for ArenaMap<Idx<V>, T> {
+    fn default() -> Self {
+        Self::new()
+    }
+}
+
+impl<T, V> Extend<(Idx<V>, T)> for ArenaMap<Idx<V>, T> {
+    fn extend<I: IntoIterator<Item = (Idx<V>, T)>>(&mut self, iter: I) {
+        iter.into_iter().for_each(move |(k, v)| {
+            self.insert(k, v);
+        });
+    }
+}
+
+impl<T, V> FromIterator<(Idx<V>, T)> for ArenaMap<Idx<V>, T> {
+    fn from_iter<I: IntoIterator<Item = (Idx<V>, T)>>(iter: I) -> Self {
+        let mut this = Self::new();
+        this.extend(iter);
+        this
+    }
+}
+
+pub struct ArenaMapIter<IDX, V> {
+    iter: Enumerate<std::vec::IntoIter<Option<V>>>,
+    _ty: PhantomData<IDX>,
+}
+
+impl<T, V> IntoIterator for ArenaMap<Idx<T>, V> {
+    type Item = (Idx<T>, V);
+
+    type IntoIter = ArenaMapIter<Idx<T>, V>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        let iter = self.v.into_iter().enumerate();
+        Self::IntoIter { iter, _ty: PhantomData }
+    }
+}
+
+impl<T, V> ArenaMapIter<Idx<T>, V> {
+    fn mapper((idx, o): (usize, Option<V>)) -> Option<(Idx<T>, V)> {
+        Some((ArenaMap::<Idx<T>, V>::from_idx(idx), o?))
+    }
+}
+
+impl<T, V> Iterator for ArenaMapIter<Idx<T>, V> {
+    type Item = (Idx<T>, V);
+
+    #[inline]
+    fn next(&mut self) -> Option<Self::Item> {
+        for next in self.iter.by_ref() {
+            match Self::mapper(next) {
+                Some(r) => return Some(r),
+                None => continue,
+            }
+        }
+
+        None
+    }
+
+    #[inline]
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.iter.size_hint()
+    }
+}
+
+impl<T, V> DoubleEndedIterator for ArenaMapIter<Idx<T>, V> {
+    #[inline]
+    fn next_back(&mut self) -> Option<Self::Item> {
+        while let Some(next_back) = self.iter.next_back() {
+            match Self::mapper(next_back) {
+                Some(r) => return Some(r),
+                None => continue,
+            }
+        }
+
+        None
+    }
+}
+
+/// A view into a single entry in a map, which may either be vacant or occupied.
+///
+/// This `enum` is constructed from the [`entry`] method on [`ArenaMap`].
+///
+/// [`entry`]: ArenaMap::entry
+pub enum Entry<'a, IDX, V> {
+    /// A vacant entry.
+    Vacant(VacantEntry<'a, IDX, V>),
+    /// An occupied entry.
+    Occupied(OccupiedEntry<'a, IDX, V>),
+}
+
+impl<'a, IDX, V> Entry<'a, IDX, V> {
+    /// Ensures a value is in the entry by inserting the default if empty, and returns a mutable reference to
+    /// the value in the entry.
+    pub fn or_insert(self, default: V) -> &'a mut V {
+        match self {
+            Self::Vacant(ent) => ent.insert(default),
+            Self::Occupied(ent) => ent.into_mut(),
+        }
+    }
+
+    /// Ensures a value is in the entry by inserting the result of the default function if empty, and returns
+    /// a mutable reference to the value in the entry.
+    pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
+        match self {
+            Self::Vacant(ent) => ent.insert(default()),
+            Self::Occupied(ent) => ent.into_mut(),
+        }
+    }
+
+    /// Provides in-place mutable access to an occupied entry before any potential inserts into the map.
+    pub fn and_modify<F: FnOnce(&mut V)>(mut self, f: F) -> Self {
+        if let Self::Occupied(ent) = &mut self {
+            f(ent.get_mut());
+        }
+        self
+    }
+}
+
+impl<'a, IDX, V> Entry<'a, IDX, V>
+where
+    V: Default,
+{
+    /// Ensures a value is in the entry by inserting the default value if empty, and returns a mutable reference
+    /// to the value in the entry.
+    pub fn or_default(self) -> &'a mut V {
+        self.or_insert_with(Default::default)
+    }
+}
+
+/// A view into an vacant entry in a [`ArenaMap`]. It is part of the [`Entry`] enum.
+pub struct VacantEntry<'a, IDX, V> {
+    slot: &'a mut Option<V>,
+    _ty: PhantomData<IDX>,
+}
+
+impl<'a, IDX, V> VacantEntry<'a, IDX, V> {
+    /// Sets the value of the entry with the `VacantEntry`’s key, and returns a mutable reference to it.
+    pub fn insert(self, value: V) -> &'a mut V {
+        self.slot.insert(value)
+    }
+}
+
+/// A view into an occupied entry in a [`ArenaMap`]. It is part of the [`Entry`] enum.
+pub struct OccupiedEntry<'a, IDX, V> {
+    slot: &'a mut Option<V>,
+    _ty: PhantomData<IDX>,
+}
+
+impl<'a, IDX, V> OccupiedEntry<'a, IDX, V> {
+    /// Gets a reference to the value in the entry.
+    pub fn get(&self) -> &V {
+        self.slot.as_ref().expect("Occupied")
+    }
+
+    /// Gets a mutable reference to the value in the entry.
+    pub fn get_mut(&mut self) -> &mut V {
+        self.slot.as_mut().expect("Occupied")
+    }
+
+    /// Converts the entry into a mutable reference to its value.
+    pub fn into_mut(self) -> &'a mut V {
+        self.slot.as_mut().expect("Occupied")
+    }
+
+    /// Sets the value of the entry with the `OccupiedEntry`’s key, and returns the entry’s old value.
+    pub fn insert(&mut self, value: V) -> V {
+        self.slot.replace(value).expect("Occupied")
+    }
+
+    /// Takes the value of the entry out of the map, and returns it.
+    pub fn remove(self) -> V {
+        self.slot.take().expect("Occupied")
+    }
+}