Switch crate graph to use an Arena instead of a hashmap

1 files changed, 44 insertions, 2 deletions

diff --git a/lib/la-arena/src/lib.rs b/lib/la-arena/src/lib.rs
index f6597efd8fd..07608a41857 100644
--- a/lib/la-arena/src/lib.rs
+++ b/lib/la-arena/src/lib.rs
@@ -4,8 +4,9 @@
 #![warn(missing_docs)]
 
 use std::{
-    fmt,
+    cmp, fmt,
     hash::{Hash, Hasher},
+    iter::Enumerate,
     marker::PhantomData,
     ops::{Index, IndexMut, Range, RangeInclusive},
 };
@@ -47,6 +48,18 @@ pub struct Idx<T> {
     _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
@@ -335,7 +348,7 @@ impl<T> Arena<T> {
     /// assert_eq!(iterator.next(), Some(&40));
     /// assert_eq!(iterator.next(), Some(&60));
     /// ```
-    pub fn values(&mut self) -> impl Iterator<Item = &T> + ExactSizeIterator + DoubleEndedIterator {
+    pub fn values(&self) -> impl Iterator<Item = &T> + ExactSizeIterator + DoubleEndedIterator {
         self.data.iter()
     }
 
@@ -410,3 +423,32 @@ impl<T> FromIterator<T> for Arena<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);
+        }
+    }
+}