5 files changed, 27 insertions, 49 deletions

diff --git a/Cargo.lock b/Cargo.lock
index c6ed5107c..b4d466fb6 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -351,6 +351,11 @@ version = "1.1.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
+name = "id-arena"
+version = "1.0.2"
+source = "git+https://github.com/fitzgen/id-arena/?rev=43ecd67#43ecd67d81f707dfdc1b0d067b96c17f7a7ef9b8"
+
+[[package]]
 name = "idna"
 version = "0.1.5"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -599,6 +604,7 @@ name = "ra_analysis"
 version = "0.1.0"
 dependencies = [
  "fst 0.3.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "id-arena 1.0.2 (git+https://github.com/fitzgen/id-arena/?rev=43ecd67)",
  "log 0.4.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "parking_lot 0.6.4 (registry+https://github.com/rust-lang/crates.io-index)",
  "ra_editor 0.1.0",
@@ -1301,6 +1307,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 "checksum glob 0.2.11 (registry+https://github.com/rust-lang/crates.io-index)" = "8be18de09a56b60ed0edf84bc9df007e30040691af7acd1c41874faac5895bfb"
 "checksum heck 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ea04fa3ead4e05e51a7c806fc07271fdbde4e246a6c6d1efd52e72230b771b82"
 "checksum humansize 1.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "b6cab2627acfc432780848602f3f558f7e9dd427352224b0d9324025796d2a5e"
+"checksum id-arena 1.0.2 (git+https://github.com/fitzgen/id-arena/?rev=43ecd67)" = "<none>"
 "checksum idna 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)" = "38f09e0f0b1fb55fdee1f17470ad800da77af5186a1a76c026b679358b7e844e"
 "checksum im 12.2.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ae9c7f9bb8aee47fc16d535a705f7867a9fc83bb822e5e1043bb98e77ffeed3c"
 "checksum indexmap 1.0.2 (registry+https://github.com/rust-lang/crates.io-index)" = "7e81a7c05f79578dbc15793d8b619db9ba32b4577003ef3af1a91c416798c58d"
diff --git a/crates/ra_analysis/Cargo.toml b/crates/ra_analysis/Cargo.toml
index b4a1a09b5..5dae45857 100644
--- a/crates/ra_analysis/Cargo.toml
+++ b/crates/ra_analysis/Cargo.toml
@@ -12,6 +12,7 @@ fst = "0.3.1"
 salsa = "0.8.0"
 rustc-hash = "1.0"
 parking_lot = "0.6.4"
+id-arena = { git = "https://github.com/fitzgen/id-arena/", rev = "43ecd67" }
 ra_syntax = { path = "../ra_syntax" }
 ra_editor = { path = "../ra_editor" }
 test_utils = { path = "../test_utils" }
diff --git a/crates/ra_analysis/src/arena.rs b/crates/ra_analysis/src/arena.rs
index 98ed89274..a752ec0c1 100644
--- a/crates/ra_analysis/src/arena.rs
+++ b/crates/ra_analysis/src/arena.rs
@@ -4,7 +4,6 @@
 
 use std::{
     fmt,
-    ops::{Index, IndexMut},
     hash::{Hash, Hasher},
     marker::PhantomData,
 };
@@ -41,56 +40,27 @@ impl<T> Hash for Id<T> {
 }
 
 #[derive(Debug, PartialEq, Eq)]
-pub(crate) struct Arena<T> {
-    data: Vec<T>,
+pub(crate) struct ArenaBehavior<T> {
+    _ty: PhantomData<T>,
 }
 
-impl<T> Default for Arena<T> {
-    fn default() -> Arena<T> {
-        Arena { data: Vec::new() }
+impl<T> id_arena::ArenaBehavior for ArenaBehavior<T> {
+    type Id = Id<T>;
+    fn new_arena_id() -> usize {
+        0
     }
-}
-
-impl<T> Arena<T> {
-    pub(crate) fn push(&mut self, value: T) -> Id<T> {
-        let id = self.data.len() as u32;
-        self.data.push(value);
+    fn new_id(_arena_id: usize, index: usize) -> Id<T> {
         Id {
-            idx: id as u32,
+            idx: index as u32,
             _ty: PhantomData,
         }
     }
-
-    pub(crate) fn keys<'a>(&'a self) -> impl Iterator<Item = Id<T>> + 'a {
-        (0..(self.data.len() as u32)).into_iter().map(|idx| Id {
-            idx,
-            _ty: PhantomData,
-        })
-    }
-
-    pub(crate) fn items<'a>(&'a self) -> impl Iterator<Item = (Id<T>, &T)> + 'a {
-        self.data.iter().enumerate().map(|(idx, item)| {
-            let idx = idx as u32;
-            (
-                Id {
-                    idx,
-                    _ty: PhantomData,
-                },
-                item,
-            )
-        })
+    fn index(id: Id<T>) -> usize {
+        id.idx as usize
     }
-}
-
-impl<T> Index<Id<T>> for Arena<T> {
-    type Output = T;
-    fn index(&self, id: Id<T>) -> &T {
-        &self.data[id.idx as usize]
+    fn arena_id(_id: Id<T>) -> usize {
+        0
     }
 }
 
-impl<T> IndexMut<Id<T>> for Arena<T> {
-    fn index_mut(&mut self, id: Id<T>) -> &mut T {
-        &mut self.data[id.idx as usize]
-    }
-}
+pub(crate) type Arena<T> = id_arena::Arena<T, ArenaBehavior<T>>;
diff --git a/crates/ra_analysis/src/descriptors/function/scope.rs b/crates/ra_analysis/src/descriptors/function/scope.rs
index 54d7fa456..5307a0a8e 100644
--- a/crates/ra_analysis/src/descriptors/function/scope.rs
+++ b/crates/ra_analysis/src/descriptors/function/scope.rs
@@ -58,13 +58,13 @@ impl FnScopes {
         })
     }
     fn root_scope(&mut self) -> ScopeId {
-        self.scopes.push(ScopeData {
+        self.scopes.alloc(ScopeData {
             parent: None,
             entries: vec![],
         })
     }
     fn new_scope(&mut self, parent: ScopeId) -> ScopeId {
-        self.scopes.push(ScopeData {
+        self.scopes.alloc(ScopeData {
             parent: Some(parent),
             entries: vec![],
         })
diff --git a/crates/ra_analysis/src/descriptors/module/mod.rs b/crates/ra_analysis/src/descriptors/module/mod.rs
index 54ff95b66..a6eaec178 100644
--- a/crates/ra_analysis/src/descriptors/module/mod.rs
+++ b/crates/ra_analysis/src/descriptors/module/mod.rs
@@ -166,12 +166,12 @@ pub(crate) struct ModuleTree {
 
 impl ModuleTree {
     fn modules<'a>(&'a self) -> impl Iterator<Item = ModuleId> + 'a {
-        self.mods.keys()
+        self.mods.iter().map(|(id, _)| id)
     }
 
     fn modules_for_source(&self, source: ModuleSource) -> Vec<ModuleId> {
         self.mods
-            .items()
+            .iter()
             .filter(|(_idx, it)| it.source == source)
             .map(|(idx, _)| idx)
             .collect()
@@ -333,11 +333,11 @@ struct LinkData {
 
 impl ModuleTree {
     fn push_mod(&mut self, data: ModuleData) -> ModuleId {
-        self.mods.push(data)
+        self.mods.alloc(data)
     }
     fn push_link(&mut self, data: LinkData) -> LinkId {
         let owner = data.owner;
-        let id = self.links.push(data);
+        let id = self.links.alloc(data);
         self.mods[owner].children.push(id);
         id
     }