Merge #3656

3656: Simplify arenas r=matklad a=matklad

At the moment, Arena is paranetrized by two types: index and data. The original motivation was to allow index to be defined in the downstream crate, so that you can add inherent impls to the index. 

However, it seems like we've never actually used that capability, so perhaps we should switch to a generic Index impl? This PR tries this out, switching only `raw.rs` and parts of `hir_def`. 

wdyt?

Co-authored-by: Aleksey Kladov <[email protected]>

2 files changed, 79 insertions, 54 deletions

diff --git a/crates/ra_arena/src/lib.rs b/crates/ra_arena/src/lib.rs
index fc0f7c12f..ea98d5444 100644
--- a/crates/ra_arena/src/lib.rs
+++ b/crates/ra_arena/src/lib.rs
@@ -2,6 +2,7 @@
 
 use std::{
     fmt,
+    hash::{Hash, Hasher},
     iter::FromIterator,
     marker::PhantomData,
     ops::{Index, IndexMut},
@@ -36,86 +37,110 @@ impl fmt::Display for RawId {
     }
 }
 
-#[derive(Clone, PartialEq, Eq)]
-pub struct Arena<ID, T> {
-    data: Vec<T>,
-    _ty: PhantomData<ID>,
+pub struct Idx<T> {
+    raw: RawId,
+    _ty: PhantomData<fn() -> T>,
 }
 
-impl<ID: ArenaId, T: fmt::Debug> fmt::Debug for Arena<ID, 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> Clone for Idx<T> {
+    fn clone(&self) -> Self {
+        *self
     }
 }
+impl<T> Copy for Idx<T> {}
 
-#[macro_export]
-macro_rules! impl_arena_id {
-    ($name:ident) => {
-        impl $crate::ArenaId for $name {
-            fn from_raw(raw: $crate::RawId) -> Self {
-                $name(raw)
-            }
-            fn into_raw(self) -> $crate::RawId {
-                self.0
-            }
+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)
+    }
 }
 
-pub trait ArenaId {
-    fn from_raw(raw: RawId) -> Self;
-    fn into_raw(self) -> RawId;
+impl<T> Idx<T> {
+    pub fn from_raw(raw: RawId) -> Self {
+        Idx { raw, _ty: PhantomData }
+    }
+    pub fn into_raw(self) -> RawId {
+        self.raw
+    }
+}
+
+#[derive(Clone, PartialEq, Eq)]
+pub struct Arena<T> {
+    data: Vec<T>,
 }
 
-impl<ID, T> Arena<ID, T> {
-    pub const fn new() -> Arena<ID, T> {
-        Arena { data: Vec::new(), _ty: PhantomData }
+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<ID: ArenaId, T> Arena<ID, T> {
+impl<T> Arena<T> {
+    pub const fn new() -> Arena<T> {
+        Arena { data: Vec::new() }
+    }
+
     pub fn len(&self) -> usize {
         self.data.len()
     }
     pub fn is_empty(&self) -> bool {
         self.data.is_empty()
     }
-    pub fn alloc(&mut self, value: T) -> ID {
+    pub fn alloc(&mut self, value: T) -> Idx<T> {
         let id = RawId(self.data.len() as u32);
         self.data.push(value);
-        ID::from_raw(id)
+        Idx::from_raw(id)
     }
-    pub fn iter(&self) -> impl Iterator<Item = (ID, &T)> + ExactSizeIterator + DoubleEndedIterator {
-        self.data.iter().enumerate().map(|(idx, value)| (ID::from_raw(RawId(idx as u32)), value))
+    pub fn iter(
+        &self,
+    ) -> impl Iterator<Item = (Idx<T>, &T)> + ExactSizeIterator + DoubleEndedIterator {
+        self.data.iter().enumerate().map(|(idx, value)| (Idx::from_raw(RawId(idx as u32)), value))
     }
 }
 
-impl<ID: ArenaId, T> Default for Arena<ID, T> {
-    fn default() -> Arena<ID, T> {
-        Arena { data: Vec::new(), _ty: PhantomData }
+impl<T> Default for Arena<T> {
+    fn default() -> Arena<T> {
+        Arena { data: Vec::new() }
     }
 }
 
-impl<ID: ArenaId, T> Index<ID> for Arena<ID, T> {
+impl<T> Index<Idx<T>> for Arena<T> {
     type Output = T;
-    fn index(&self, idx: ID) -> &T {
+    fn index(&self, idx: Idx<T>) -> &T {
         let idx = idx.into_raw().0 as usize;
         &self.data[idx]
     }
 }
 
-impl<ID: ArenaId, T> IndexMut<ID> for Arena<ID, T> {
-    fn index_mut(&mut self, idx: ID) -> &mut T {
+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<ID: ArenaId, T> FromIterator<T> for Arena<ID, T> {
+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), _ty: PhantomData }
+        Arena { data: Vec::from_iter(iter) }
     }
 }
diff --git a/crates/ra_arena/src/map.rs b/crates/ra_arena/src/map.rs
index b73d4e365..5e764113d 100644
--- a/crates/ra_arena/src/map.rs
+++ b/crates/ra_arena/src/map.rs
@@ -2,17 +2,17 @@
 
 use std::marker::PhantomData;
 
-use super::ArenaId;
+use crate::Idx;
 
 /// A map from arena IDs to some other type. Space requirement is O(highest ID).
 #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
-pub struct ArenaMap<ID, T> {
-    v: Vec<Option<T>>,
+pub struct ArenaMap<ID, V> {
+    v: Vec<Option<V>>,
     _ty: PhantomData<ID>,
 }
 
-impl<ID: ArenaId, T> ArenaMap<ID, T> {
-    pub fn insert(&mut self, id: ID, t: T) {
+impl<T, V> ArenaMap<Idx<T>, V> {
+    pub fn insert(&mut self, id: Idx<T>, t: V) {
         let idx = Self::to_idx(id);
         if self.v.capacity() <= idx {
             self.v.reserve(idx + 1 - self.v.capacity());
@@ -25,43 +25,43 @@ impl<ID: ArenaId, T> ArenaMap<ID, T> {
         self.v[idx] = Some(t);
     }
 
-    pub fn get(&self, id: ID) -> Option<&T> {
+    pub fn get(&self, id: Idx<T>) -> Option<&V> {
         self.v.get(Self::to_idx(id)).and_then(|it| it.as_ref())
     }
 
-    pub fn get_mut(&mut self, id: ID) -> Option<&mut T> {
+    pub fn get_mut(&mut self, id: Idx<T>) -> Option<&mut V> {
         self.v.get_mut(Self::to_idx(id)).and_then(|it| it.as_mut())
     }
 
-    pub fn values(&self) -> impl Iterator<Item = &T> {
+    pub fn values(&self) -> impl Iterator<Item = &V> {
         self.v.iter().filter_map(|o| o.as_ref())
     }
 
-    pub fn values_mut(&mut self) -> impl Iterator<Item = &mut T> {
+    pub fn values_mut(&mut self) -> impl Iterator<Item = &mut V> {
         self.v.iter_mut().filter_map(|o| o.as_mut())
     }
 
-    pub fn iter(&self) -> impl Iterator<Item = (ID, &T)> {
+    pub fn iter(&self) -> impl Iterator<Item = (Idx<T>, &V)> {
         self.v.iter().enumerate().filter_map(|(idx, o)| Some((Self::from_idx(idx), o.as_ref()?)))
     }
 
-    fn to_idx(id: ID) -> usize {
+    fn to_idx(id: Idx<T>) -> usize {
         u32::from(id.into_raw()) as usize
     }
 
-    fn from_idx(idx: usize) -> ID {
-        ID::from_raw((idx as u32).into())
+    fn from_idx(idx: usize) -> Idx<T> {
+        Idx::from_raw((idx as u32).into())
     }
 }
 
-impl<ID: ArenaId, T> std::ops::Index<ID> for ArenaMap<ID, T> {
+impl<T, V> std::ops::Index<Idx<V>> for ArenaMap<Idx<V>, T> {
     type Output = T;
-    fn index(&self, id: ID) -> &T {
+    fn index(&self, id: Idx<V>) -> &T {
         self.v[Self::to_idx(id)].as_ref().unwrap()
     }
 }
 
-impl<ID, T> Default for ArenaMap<ID, T> {
+impl<T, V> Default for ArenaMap<Idx<V>, T> {
     fn default() -> Self {
         ArenaMap { v: Vec::new(), _ty: PhantomData }
     }