2 files changed, 94 insertions, 61 deletions

diff --git a/crates/ra_hir/src/ids.rs b/crates/ra_hir/src/ids.rs
index 2e10e5516..0aa687a08 100644
--- a/crates/ra_hir/src/ids.rs
+++ b/crates/ra_hir/src/ids.rs
@@ -253,13 +253,17 @@ impl SourceFileItems {
     }
 
     fn init(&mut self, source_file: &SourceFile) {
-        source_file.syntax().descendants().for_each(|it| {
+        // By walking the tree in bread-first order we make sure that parents
+        // get lower ids then children. That is, addding a new child does not
+        // change parent's id. This means that, say, adding a new function to a
+        // trait does not chage ids of top-level items, which helps caching.
+        bfs(source_file.syntax(), |it| {
             if let Some(module_item) = ast::ModuleItem::cast(it) {
                 self.alloc(module_item.syntax().to_owned());
             } else if let Some(macro_call) = ast::MacroCall::cast(it) {
                 self.alloc(macro_call.syntax().to_owned());
             }
-        });
+        })
     }
 
     fn alloc(&mut self, item: TreePtr<SyntaxNode>) -> SourceFileItemId {
@@ -305,3 +309,16 @@ impl std::ops::Index<SourceFileItemId> for SourceFileItems {
         &self.arena[idx]
     }
 }
+
+/// Walks the subtree in bfs order, calling `f` for each node.
+fn bfs(node: &SyntaxNode, mut f: impl FnMut(&SyntaxNode)) {
+    let mut curr_layer = vec![node];
+    let mut next_layer = vec![];
+    while !curr_layer.is_empty() {
+        curr_layer.drain(..).for_each(|node| {
+            next_layer.extend(node.children());
+            f(node);
+        });
+        std::mem::swap(&mut curr_layer, &mut next_layer);
+    }
+}
diff --git a/crates/ra_hir/src/nameres/tests.rs b/crates/ra_hir/src/nameres/tests.rs
index c511c40b2..17de54b44 100644
--- a/crates/ra_hir/src/nameres/tests.rs
+++ b/crates/ra_hir/src/nameres/tests.rs
@@ -322,27 +322,8 @@ fn reexport_across_crates() {
     );
 }
 
-#[test]
-fn typing_inside_a_function_should_not_invalidate_item_map() {
-    let (mut db, pos) = MockDatabase::with_position(
-        "
-        //- /lib.rs
-        mod foo;
-
-        use crate::foo::bar::Baz;
-
-        //- /foo/mod.rs
-        pub mod bar;
-
-        //- /foo/bar.rs
-        <|>
-        salsa::query_group! {
-            trait Baz {
-                fn foo() -> i32 { 1 + 1 }
-            }
-        }
-        ",
-    );
+fn check_item_map_is_not_recomputed(initial: &str, file_change: &str) {
+    let (mut db, pos) = MockDatabase::with_position(initial);
     let source_root = db.file_source_root(pos.file_id);
     {
         let events = db.log_executed(|| {
@@ -350,18 +331,8 @@ fn typing_inside_a_function_should_not_invalidate_item_map() {
         });
         assert!(format!("{:?}", events).contains("item_map"))
     }
-
-    let new_text = "
-        salsa::query_group! {
-            trait Baz {
-                fn foo() -> i32 { 92 }
-            }
-        }
-    "
-    .to_string();
-
     db.query_mut(ra_db::FileTextQuery)
-        .set(pos.file_id, Arc::new(new_text));
+        .set(pos.file_id, Arc::new(file_change.to_string()));
 
     {
         let events = db.log_executed(|| {
@@ -376,8 +347,8 @@ fn typing_inside_a_function_should_not_invalidate_item_map() {
 }
 
 #[test]
-fn typing_inside_a_function_inside_a_macro_should_not_invalidate_item_map() {
-    let (mut db, pos) = MockDatabase::with_position(
+fn typing_inside_a_function_should_not_invalidate_item_map() {
+    check_item_map_is_not_recomputed(
         "
         //- /lib.rs
         mod foo;<|>
@@ -392,36 +363,81 @@ fn typing_inside_a_function_inside_a_macro_should_not_invalidate_item_map() {
 
         //- /foo/bar.rs
         pub struct Baz;
-    ",
-    );
-    let source_root = db.file_source_root(pos.file_id);
-    {
-        let events = db.log_executed(|| {
-            db.item_map(source_root).unwrap();
-        });
-        assert!(format!("{:?}", events).contains("item_map"))
-    }
-
-    let new_text = "
+        ",
+        "
         mod foo;
 
         use crate::foo::bar::Baz;
 
         fn foo() -> i32 { 92 }
-    "
-    .to_string();
+        ",
+    );
+}
 
-    db.query_mut(ra_db::FileTextQuery)
-        .set(pos.file_id, Arc::new(new_text));
+#[test]
+fn adding_inner_items_should_not_invalidate_item_map() {
+    check_item_map_is_not_recomputed(
+        "
+        //- /lib.rs
+        struct S { a: i32}
+        enum E { A }
+        trait T {
+            fn a() {}
+        }
+        mod foo;<|>
+        impl S {
+            fn a() {}
+        }
+        use crate::foo::bar::Baz;
+        //- /foo/mod.rs
+        pub mod bar;
 
-    {
-        let events = db.log_executed(|| {
-            db.item_map(source_root).unwrap();
-        });
-        assert!(
-            !format!("{:?}", events).contains("item_map"),
-            "{:#?}",
-            events
-        )
-    }
+        //- /foo/bar.rs
+        pub struct Baz;
+        ",
+        "
+        struct S { a: i32, b: () }
+        enum E { A, B }
+        trait T {
+            fn a() {}
+            fn b() {}
+        }
+        mod foo;<|>
+        impl S {
+            fn a() {}
+            fn b() {}
+        }
+        use crate::foo::bar::Baz;
+        ",
+    );
+}
+
+#[test]
+fn typing_inside_a_function_inside_a_macro_should_not_invalidate_item_map() {
+    check_item_map_is_not_recomputed(
+        "
+        //- /lib.rs
+        mod foo;
+
+        use crate::foo::bar::Baz;
+
+        //- /foo/mod.rs
+        pub mod bar;
+
+        //- /foo/bar.rs
+        <|>
+        salsa::query_group! {
+            trait Baz {
+                fn foo() -> i32 { 1 + 1 }
+            }
+        }
+        ",
+        "
+        salsa::query_group! {
+            trait Baz {
+                fn foo() -> i32 { 92 }
+            }
+        }
+        ",
+    );
 }