Make nameresolution resilient to reparsing

We now store item id's instead of local syntax ptrs, and item ids
don't change if you type inside a single function.

3 files changed, 130 insertions, 76 deletions

diff --git a/crates/ra_analysis/src/descriptors/mod.rs b/crates/ra_analysis/src/descriptors/mod.rs
index f6b9102e7..a5e956024 100644
--- a/crates/ra_analysis/src/descriptors/mod.rs
+++ b/crates/ra_analysis/src/descriptors/mod.rs
@@ -13,7 +13,7 @@ use crate::{
     FileId,
     db::SyntaxDatabase,
     descriptors::function::{resolve_local_name, FnId, FnScopes},
-    descriptors::module::{ModuleId, ModuleTree, ModuleSource, nameres::{ItemMap, InputModuleItems, FileItemId}},
+    descriptors::module::{ModuleId, ModuleTree, ModuleSource, nameres::{ItemMap, InputModuleItems, FileItems}},
     input::SourceRootId,
     loc2id::IdDatabase,
     syntax_ptr::LocalSyntaxPtr,
@@ -21,6 +21,7 @@ use crate::{
 };
 
 pub(crate) use self::path::{Path, PathKind};
+pub(crate) use self::module::nameres::FileItemId;
 
 salsa::query_group! {
     pub(crate) trait DescriptorDatabase: SyntaxDatabase + IdDatabase {
@@ -29,7 +30,7 @@ salsa::query_group! {
             use fn function::imp::fn_scopes;
         }
 
-        fn _file_items(file_id: FileId) -> Arc<Vec<SyntaxNode>> {
+        fn _file_items(file_id: FileId) -> Arc<FileItems> {
             type FileItemsQuery;
             storage volatile;
             use fn module::nameres::file_items;
diff --git a/crates/ra_analysis/src/descriptors/module/nameres.rs b/crates/ra_analysis/src/descriptors/module/nameres.rs
index 6e327e374..d347a69b0 100644
--- a/crates/ra_analysis/src/descriptors/module/nameres.rs
+++ b/crates/ra_analysis/src/descriptors/module/nameres.rs
@@ -17,12 +17,13 @@
 use std::{
     sync::Arc,
     time::Instant,
+    ops::Index,
 };
 
 use rustc_hash::FxHashMap;
 
 use ra_syntax::{
-    SyntaxNode,
+    SyntaxNode, SyntaxNodeRef, TextRange,
     SmolStr, SyntaxKind::{self, *},
     ast::{self, ModuleItemOwner, AstNode}
 };
@@ -35,28 +36,62 @@ use crate::{
         DescriptorDatabase,
         module::{ModuleId, ModuleTree, ModuleSourceNode},
     },
-    syntax_ptr::{LocalSyntaxPtr},
     input::SourceRootId,
+    arena::{Arena, Id}
 };
 
+/// Identifier of item within a specific file. This is stable over reparses, so
+/// it's OK to use it as a salsa key/value.
+pub(crate) type FileItemId = Id<SyntaxNode>;
 
-#[derive(Clone, Copy, Hash, PartialEq, Eq, Debug)]
-pub(crate) struct FileItemId(u32);
+/// Maps item's `SyntaxNode`s to `FileItemId` and back.
+#[derive(Debug, PartialEq, Eq, Default)]
+pub(crate) struct FileItems {
+    arena: Arena<SyntaxNode>,
+}
+
+impl FileItems {
+    fn alloc(&mut self, item: SyntaxNode) -> FileItemId {
+        self.arena.alloc(item)
+    }
+    fn id_of(&self, item: SyntaxNodeRef) -> FileItemId {
+        let (id, _item) = self
+            .arena
+            .iter()
+            .find(|(_id, i)| i.borrowed() == item)
+            .unwrap();
+        id
+    }
+}
 
-pub(crate) fn file_items(db: &impl DescriptorDatabase, file_id: FileId) -> Arc<Vec<SyntaxNode>> {
+impl Index<FileItemId> for FileItems {
+    type Output = SyntaxNode;
+    fn index(&self, idx: FileItemId) -> &SyntaxNode {
+        &self.arena[idx]
+    }
+}
+
+pub(crate) fn file_items(db: &impl DescriptorDatabase, file_id: FileId) -> Arc<FileItems> {
     let source_file = db.file_syntax(file_id);
     let source_file = source_file.borrowed();
-    let res = source_file.syntax().descendants()
+    let mut res = FileItems::default();
+    source_file
+        .syntax()
+        .descendants()
         .filter_map(ast::ModuleItem::cast)
         .map(|it| it.syntax().owned())
-        .collect::<Vec<_>>();
+        .for_each(|it| {
+            res.alloc(it);
+        });
     Arc::new(res)
 }
 
-pub(crate) fn file_item(db: &impl DescriptorDatabase, file_id: FileId, file_item_id: FileItemId) -> SyntaxNode {
-    let items = db._file_items(file_id);
-    let idx = file_item_id.0 as usize;
-    items[idx].clone()
+pub(crate) fn file_item(
+    db: &impl DescriptorDatabase,
+    file_id: FileId,
+    file_item_id: FileItemId,
+) -> SyntaxNode {
+    db._file_items(file_id)[file_item_id].clone()
 }
 
 /// Item map is the result of the name resolution. Item map contains, for each
@@ -83,17 +118,44 @@ pub(crate) struct InputModuleItems {
     imports: Vec<Import>,
 }
 
+#[derive(Debug, PartialEq, Eq)]
+struct ModuleItem {
+    id: FileItemId,
+    name: SmolStr,
+    kind: SyntaxKind,
+    vis: Vis,
+}
+
+#[derive(Debug, PartialEq, Eq)]
+enum Vis {
+    // Priv,
+    Other,
+}
+
 #[derive(Debug, Clone, PartialEq, Eq)]
 struct Import {
     path: Path,
     kind: ImportKind,
 }
 
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub(crate) struct NamedImport {
+    file_item_id: FileItemId,
+    relative_range: TextRange,
+}
+
+impl NamedImport {
+    pub(crate) fn range(&self, db: &impl DescriptorDatabase, file_id: FileId) -> TextRange {
+        let syntax = db._file_item(file_id, self.file_item_id);
+        let offset = syntax.borrowed().range().start();
+        self.relative_range + offset
+    }
+}
+
 #[derive(Debug, Clone, PartialEq, Eq)]
 enum ImportKind {
     Glob,
-    // TODO: make offset independent
-    Named(LocalSyntaxPtr),
+    Named(NamedImport),
 }
 
 pub(crate) fn input_module_items(
@@ -103,10 +165,11 @@ pub(crate) fn input_module_items(
 ) -> Cancelable<Arc<InputModuleItems>> {
     let module_tree = db._module_tree(source_root)?;
     let source = module_id.source(&module_tree);
+    let file_items = db._file_items(source.file_id());
     let res = match source.resolve(db) {
         ModuleSourceNode::SourceFile(it) => {
             let items = it.borrowed().items();
-            InputModuleItems::new(items)
+            InputModuleItems::new(&file_items, items)
         }
         ModuleSourceNode::Module(it) => {
             let items = it
@@ -114,7 +177,7 @@ pub(crate) fn input_module_items(
                 .item_list()
                 .into_iter()
                 .flat_map(|it| it.items());
-            InputModuleItems::new(items)
+            InputModuleItems::new(&file_items, items)
         }
     };
     Ok(Arc::new(res))
@@ -133,7 +196,6 @@ pub(crate) fn item_map(
             Ok((id, items))
         })
         .collect::<Cancelable<FxHashMap<_, _>>>()?;
-
     let mut resolver = Resolver {
         db: db,
         input: &input,
@@ -155,8 +217,7 @@ pub(crate) struct Resolution {
     /// None for unresolved
     pub(crate) def_id: Option<DefId>,
     /// ident by whitch this is imported into local scope.
-    /// TODO: make this offset-independent.
-    pub(crate) import_name: Option<LocalSyntaxPtr>,
+    pub(crate) import: Option<NamedImport>,
 }
 
 // #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
@@ -171,55 +232,49 @@ pub(crate) struct Resolution {
 //     values: Option<T>,
 // }
 
-#[derive(Debug, PartialEq, Eq)]
-struct ModuleItem {
-    ptr: LocalSyntaxPtr,
-    name: SmolStr,
-    kind: SyntaxKind,
-    vis: Vis,
-}
-
-#[derive(Debug, PartialEq, Eq)]
-enum Vis {
-    // Priv,
-    Other,
-}
-
 impl InputModuleItems {
-    fn new<'a>(items: impl Iterator<Item = ast::ModuleItem<'a>>) -> InputModuleItems {
+    fn new<'a>(
+        file_items: &FileItems,
+        items: impl Iterator<Item = ast::ModuleItem<'a>>,
+    ) -> InputModuleItems {
         let mut res = InputModuleItems::default();
         for item in items {
-            res.add_item(item);
+            res.add_item(file_items, item);
         }
         res
     }
 
-    fn add_item(&mut self, item: ast::ModuleItem) -> Option<()> {
+    fn add_item(&mut self, file_items: &FileItems, item: ast::ModuleItem) -> Option<()> {
         match item {
-            ast::ModuleItem::StructDef(it) => self.items.push(ModuleItem::new(it)?),
-            ast::ModuleItem::EnumDef(it) => self.items.push(ModuleItem::new(it)?),
-            ast::ModuleItem::FnDef(it) => self.items.push(ModuleItem::new(it)?),
-            ast::ModuleItem::TraitDef(it) => self.items.push(ModuleItem::new(it)?),
-            ast::ModuleItem::TypeDef(it) => self.items.push(ModuleItem::new(it)?),
+            ast::ModuleItem::StructDef(it) => self.items.push(ModuleItem::new(file_items, it)?),
+            ast::ModuleItem::EnumDef(it) => self.items.push(ModuleItem::new(file_items, it)?),
+            ast::ModuleItem::FnDef(it) => self.items.push(ModuleItem::new(file_items, it)?),
+            ast::ModuleItem::TraitDef(it) => self.items.push(ModuleItem::new(file_items, it)?),
+            ast::ModuleItem::TypeDef(it) => self.items.push(ModuleItem::new(file_items, it)?),
             ast::ModuleItem::ImplItem(_) => {
                 // impls don't define items
             }
-            ast::ModuleItem::UseItem(it) => self.add_use_item(it),
+            ast::ModuleItem::UseItem(it) => self.add_use_item(file_items, it),
             ast::ModuleItem::ExternCrateItem(_) => {
                 // TODO
             }
-            ast::ModuleItem::ConstDef(it) => self.items.push(ModuleItem::new(it)?),
-            ast::ModuleItem::StaticDef(it) => self.items.push(ModuleItem::new(it)?),
-            ast::ModuleItem::Module(it) => self.items.push(ModuleItem::new(it)?),
+            ast::ModuleItem::ConstDef(it) => self.items.push(ModuleItem::new(file_items, it)?),
+            ast::ModuleItem::StaticDef(it) => self.items.push(ModuleItem::new(file_items, it)?),
+            ast::ModuleItem::Module(it) => self.items.push(ModuleItem::new(file_items, it)?),
         }
         Some(())
     }
 
-    fn add_use_item(&mut self, item: ast::UseItem) {
-        Path::expand_use_item(item, |path, ptr| {
-            let kind = match ptr {
+    fn add_use_item(&mut self, file_items: &FileItems, item: ast::UseItem) {
+        let file_item_id = file_items.id_of(item.syntax());
+        let start_offset = item.syntax().range().start();
+        Path::expand_use_item(item, |path, range| {
+            let kind = match range {
                 None => ImportKind::Glob,
-                Some(ptr) => ImportKind::Named(ptr),
+                Some(range) => ImportKind::Named(NamedImport {
+                    file_item_id,
+                    relative_range: range - start_offset,
+                }),
             };
             self.imports.push(Import { kind, path })
         })
@@ -227,13 +282,13 @@ impl InputModuleItems {
 }
 
 impl ModuleItem {
-    fn new<'a>(item: impl ast::NameOwner<'a>) -> Option<ModuleItem> {
+    fn new<'a>(file_items: &FileItems, item: impl ast::NameOwner<'a>) -> Option<ModuleItem> {
         let name = item.name()?.text();
-        let ptr = LocalSyntaxPtr::new(item.syntax());
         let kind = item.syntax().kind();
         let vis = Vis::Other;
+        let id = file_items.id_of(item.syntax());
         let res = ModuleItem {
-            ptr,
+            id,
             name,
             kind,
             vis,
@@ -273,12 +328,12 @@ where
 
         for import in input.imports.iter() {
             if let Some(name) = import.path.segments.iter().last() {
-                if let ImportKind::Named(ptr) = import.kind {
+                if let ImportKind::Named(import) = import.kind {
                     module_items.items.insert(
                         name.clone(),
                         Resolution {
                             def_id: None,
-                            import_name: Some(ptr),
+                            import: Some(import),
                         },
                     );
                 }
@@ -290,12 +345,14 @@ where
                 // handle submodules separatelly
                 continue;
             }
-            let ptr = item.ptr.into_global(file_id);
-            let def_loc = DefLoc::Item { ptr };
+            let def_loc = DefLoc::Item {
+                file_id,
+                id: item.id,
+            };
             let def_id = self.db.id_maps().def_id(def_loc);
             let resolution = Resolution {
                 def_id: Some(def_id),
-                import_name: None,
+                import: None,
             };
             module_items.items.insert(item.name.clone(), resolution);
         }
@@ -308,7 +365,7 @@ where
             let def_id = self.db.id_maps().def_id(def_loc);
             let resolution = Resolution {
                 def_id: Some(def_id),
-                import_name: None,
+                import: None,
             };
             module_items.items.insert(name, resolution);
         }
@@ -362,7 +419,7 @@ where
                 self.update(module_id, |items| {
                     let res = Resolution {
                         def_id: Some(def_id),
-                        import_name: Some(ptr),
+                        import: Some(ptr),
                     };
                     items.items.insert(name.clone(), res);
                 })
@@ -473,10 +530,11 @@ mod tests {
             let events = db.log_executed(|| {
                 db._item_map(source_root).unwrap();
             });
-            // assert!(
-            //     !format!("{:?}", events).contains("_item_map"),
-            //     "{:#?}", events
-            // )
+            assert!(
+                !format!("{:?}", events).contains("_item_map"),
+                "{:#?}",
+                events
+            )
         }
     }
 }
diff --git a/crates/ra_analysis/src/descriptors/path.rs b/crates/ra_analysis/src/descriptors/path.rs
index 99fca18b1..8279daf4b 100644
--- a/crates/ra_analysis/src/descriptors/path.rs
+++ b/crates/ra_analysis/src/descriptors/path.rs
@@ -1,6 +1,4 @@
-use ra_syntax::{SmolStr, ast, AstNode};
-
-use crate::syntax_ptr::LocalSyntaxPtr;
+use ra_syntax::{SmolStr, ast, AstNode, TextRange};
 
 #[derive(Debug, Clone, PartialEq, Eq)]
 pub(crate) struct Path {
@@ -18,10 +16,7 @@ pub(crate) enum PathKind {
 
 impl Path {
     /// Calls `cb` with all paths, represented by this use item.
-    pub(crate) fn expand_use_item(
-        item: ast::UseItem,
-        mut cb: impl FnMut(Path, Option<LocalSyntaxPtr>),
-    ) {
+    pub(crate) fn expand_use_item(item: ast::UseItem, mut cb: impl FnMut(Path, Option<TextRange>)) {
         if let Some(tree) = item.use_tree() {
             expand_use_tree(None, tree, &mut cb);
         }
@@ -77,7 +72,7 @@ impl Path {
 fn expand_use_tree(
     prefix: Option<Path>,
     tree: ast::UseTree,
-    cb: &mut impl FnMut(Path, Option<LocalSyntaxPtr>),
+    cb: &mut impl FnMut(Path, Option<TextRange>),
 ) {
     if let Some(use_tree_list) = tree.use_tree_list() {
         let prefix = match tree.path() {
@@ -93,13 +88,13 @@ fn expand_use_tree(
     } else {
         if let Some(ast_path) = tree.path() {
             if let Some(path) = convert_path(prefix, ast_path) {
-                let ptr = if tree.has_star() {
+                let range = if tree.has_star() {
                     None
                 } else {
-                    let ptr = LocalSyntaxPtr::new(ast_path.segment().unwrap().syntax());
-                    Some(ptr)
+                    let range = ast_path.segment().unwrap().syntax().range();
+                    Some(range)
                 };
-                cb(path, ptr)
+                cb(path, range)
             }
         }
     }