9 files changed, 221 insertions, 225 deletions

diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs
index bda02d3cc..11cdf9c34 100644
--- a/crates/ra_hir/src/db.rs
+++ b/crates/ra_hir/src/db.rs
@@ -126,7 +126,7 @@ pub trait HirDatabase: DefDatabase {
     #[salsa::invoke(ExprScopes::expr_scopes_query)]
     fn expr_scopes(&self, def: DefWithBody) -> Arc<ExprScopes>;
 
-    #[salsa::invoke(crate::ty::infer)]
+    #[salsa::invoke(crate::ty::infer_query)]
     fn infer(&self, def: DefWithBody) -> Arc<InferenceResult>;
 
     #[salsa::invoke(crate::ty::type_for_def)]
@@ -156,7 +156,7 @@ pub trait HirDatabase: DefDatabase {
     #[salsa::invoke(crate::ty::method_resolution::CrateImplBlocks::impls_in_crate_query)]
     fn impls_in_crate(&self, krate: Crate) -> Arc<CrateImplBlocks>;
 
-    #[salsa::invoke(crate::ty::traits::impls_for_trait)]
+    #[salsa::invoke(crate::ty::traits::impls_for_trait_query)]
     fn impls_for_trait(&self, krate: Crate, trait_: Trait) -> Arc<[ImplBlock]>;
 
     /// This provides the Chalk trait solver instance. Because Chalk always
@@ -164,11 +164,11 @@ pub trait HirDatabase: DefDatabase {
     /// because Chalk does its own internal caching, the solver is wrapped in a
     /// Mutex and the query is marked volatile, to make sure the cached state is
     /// thrown away when input facts change.
-    #[salsa::invoke(crate::ty::traits::solver)]
+    #[salsa::invoke(crate::ty::traits::solver_query)]
     #[salsa::volatile]
     fn solver(&self, krate: Crate) -> Arc<Mutex<crate::ty::traits::Solver>>;
 
-    #[salsa::invoke(crate::ty::traits::implements)]
+    #[salsa::invoke(crate::ty::traits::implements_query)]
     fn implements(
         &self,
         krate: Crate,
diff --git a/crates/ra_hir/src/mock.rs b/crates/ra_hir/src/mock.rs
index fa5882dea..b84cb7503 100644
--- a/crates/ra_hir/src/mock.rs
+++ b/crates/ra_hir/src/mock.rs
@@ -236,7 +236,7 @@ impl MockDatabase {
 }
 
 #[derive(Default)]
-pub struct CrateGraphFixture(pub FxHashMap<String, (String, Edition, Vec<String>)>);
+pub struct CrateGraphFixture(pub Vec<(String, (String, Edition, Vec<String>))>);
 
 #[macro_export]
 macro_rules! crate_graph {
@@ -246,10 +246,10 @@ macro_rules! crate_graph {
             #[allow(unused_mut, unused_assignments)]
             let mut edition = ra_db::Edition::Edition2018;
             $(edition = ra_db::Edition::from_string($edition);)?
-            res.0.insert(
+            res.0.push((
                 $crate_name.to_string(),
                 ($crate_path.to_string(), edition, vec![$($dep.to_string()),*])
-            );
+            ));
         )*
         res
     }}
diff --git a/crates/ra_hir/src/name.rs b/crates/ra_hir/src/name.rs
index 9a999e66c..e3a82cf03 100644
--- a/crates/ra_hir/src/name.rs
+++ b/crates/ra_hir/src/name.rs
@@ -5,7 +5,7 @@ use ra_syntax::{ast, SmolStr};
 /// `Name` is a wrapper around string, which is used in hir for both references
 /// and declarations. In theory, names should also carry hygiene info, but we are
 /// not there yet!
-#[derive(Clone, PartialEq, Eq, Hash)]
+#[derive(Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
 pub struct Name {
     text: SmolStr,
 }
diff --git a/crates/ra_hir/src/nameres/tests.rs b/crates/ra_hir/src/nameres/tests.rs
index 572bd1bf7..14c8ee50b 100644
--- a/crates/ra_hir/src/nameres/tests.rs
+++ b/crates/ra_hir/src/nameres/tests.rs
@@ -8,7 +8,11 @@ use ra_db::SourceDatabase;
 use test_utils::covers;
 use insta::assert_snapshot_matches;
 
-use crate::{Crate, mock::{MockDatabase, CrateGraphFixture}, nameres::Resolution};
+use crate::{
+    Crate,
+    mock::{MockDatabase, CrateGraphFixture},
+    nameres::Resolution,
+};
 
 use super::*;
 
@@ -25,12 +29,15 @@ fn compute_crate_def_map(fixture: &str, graph: Option<CrateGraphFixture>) -> Arc
 fn render_crate_def_map(map: &CrateDefMap) -> String {
     let mut buf = String::new();
     go(&mut buf, map, "\ncrate", map.root);
-    return buf;
+    return buf.trim().to_string();
 
     fn go(buf: &mut String, map: &CrateDefMap, path: &str, module: CrateModuleId) {
         *buf += path;
         *buf += "\n";
-        for (name, res) in map.modules[module].scope.items.iter() {
+
+        let mut entries = map.modules[module].scope.items.iter().collect::<Vec<_>>();
+        entries.sort_by_key(|(name, _)| *name);
+        for (name, res) in entries {
             *buf += &format!("{}: {}\n", name, dump_resolution(res))
         }
         for (name, child) in map.modules[module].children.iter() {
@@ -54,8 +61,8 @@ fn def_map(fixtute: &str) -> String {
     render_crate_def_map(&dm)
 }
 
-fn def_map_with_crate_graph(fixtute: &str, graph: CrateGraphFixture) -> String {
-    let dm = compute_crate_def_map(fixtute, Some(graph));
+fn def_map_with_crate_graph(fixture: &str, graph: CrateGraphFixture) -> String {
+    let dm = compute_crate_def_map(fixture, Some(graph));
     render_crate_def_map(&dm)
 }
 
@@ -79,21 +86,20 @@ fn crate_def_map_smoke_test() {
         ",
     );
     assert_snapshot_matches!(map, @r###"
-crate
-V: t v
-E: t
-foo: t
-S: t v
-
-crate::foo
-bar: t
-f: v
-
-crate::foo::bar
-Baz: t v
-E: t
-"###
-    )
+        ⋮crate
+        ⋮E: t
+        ⋮S: t v
+        ⋮V: t v
+        ⋮foo: t
+        ⋮
+        ⋮crate::foo
+        ⋮bar: t
+        ⋮f: v
+        ⋮
+        ⋮crate::foo::bar
+        ⋮Baz: t v
+        ⋮E: t
+    "###)
 }
 
 #[test]
@@ -113,12 +119,12 @@ fn bogus_paths() {
         ",
     );
     assert_snapshot_matches!(map, @r###"
-crate
-foo: t
-S: t v
-
-crate::foo
-"###
+   ⋮crate
+   ⋮S: t v
+   ⋮foo: t
+   ⋮
+   ⋮crate::foo
+    "###
     )
 }
 
@@ -137,13 +143,13 @@ fn use_as() {
     );
     assert_snapshot_matches!(map,
         @r###"
-crate
-Foo: t v
-foo: t
-
-crate::foo
-Baz: t v
-"###
+   ⋮crate
+   ⋮Foo: t v
+   ⋮foo: t
+   ⋮
+   ⋮crate::foo
+   ⋮Baz: t v
+    "###
     );
 }
 
@@ -164,21 +170,19 @@ fn use_trees() {
         pub enum Quux {};
         ",
     );
-    assert_snapshot_matches!(map,
-        @r###"
-crate
-Quux: t
-Baz: t v
-foo: t
-
-crate::foo
-bar: t
-
-crate::foo::bar
-Quux: t
-Baz: t v
-"###
-    );
+    assert_snapshot_matches!(map, @r###"
+        ⋮crate
+        ⋮Baz: t v
+        ⋮Quux: t
+        ⋮foo: t
+        ⋮
+        ⋮crate::foo
+        ⋮bar: t
+        ⋮
+        ⋮crate::foo::bar
+        ⋮Baz: t v
+        ⋮Quux: t
+    "###);
 }
 
 #[test]
@@ -199,20 +203,18 @@ fn re_exports() {
         pub struct Baz;
         ",
     );
-    assert_snapshot_matches!(map,
-        @r###"
-crate
-Baz: t v
-foo: t
-
-crate::foo
-bar: t
-Baz: t v
-
-crate::foo::bar
-Baz: t v
-"###
-    );
+    assert_snapshot_matches!(map, @r###"
+        ⋮crate
+        ⋮Baz: t v
+        ⋮foo: t
+        ⋮
+        ⋮crate::foo
+        ⋮Baz: t v
+        ⋮bar: t
+        ⋮
+        ⋮crate::foo::bar
+        ⋮Baz: t v
+    "###);
 }
 
 #[test]
@@ -237,10 +239,10 @@ fn std_prelude() {
         },
     );
     assert_snapshot_matches!(map, @r###"
-crate
-Bar: t v
-Baz: t v
-"###);
+        ⋮crate
+        ⋮Bar: t v
+        ⋮Baz: t v
+    "###);
 }
 
 #[test]
@@ -254,10 +256,10 @@ fn can_import_enum_variant() {
         ",
     );
     assert_snapshot_matches!(map, @r###"
-crate
-V: t v
-E: t
-"###
+        ⋮crate
+        ⋮E: t
+        ⋮V: t v
+    "###
     );
 }
 
@@ -285,20 +287,18 @@ fn edition_2015_imports() {
         },
     );
 
-    assert_snapshot_matches!(map,
-        @r###"
-crate
-bar: t
-foo: t
-
-crate::bar
-Bar: t v
-
-crate::foo
-FromLib: t v
-Bar: t v
-"###
-    );
+    assert_snapshot_matches!(map, @r###"
+        ⋮crate
+        ⋮bar: t
+        ⋮foo: t
+        ⋮
+        ⋮crate::bar
+        ⋮Bar: t v
+        ⋮
+        ⋮crate::foo
+        ⋮Bar: t v
+        ⋮FromLib: t v
+    "###);
 }
 
 #[test]
@@ -317,16 +317,14 @@ fn module_resolution_works_for_non_standard_filenames() {
         },
     );
 
-    assert_snapshot_matches!(map,
-        @r###"
-crate
-Bar: t v
-foo: t
-
-crate::foo
-Bar: t v
-"###
-    );
+    assert_snapshot_matches!(map, @r###"
+        ⋮crate
+        ⋮Bar: t v
+        ⋮foo: t
+        ⋮
+        ⋮crate::foo
+        ⋮Bar: t v
+    "###);
 }
 
 #[test]
@@ -348,12 +346,10 @@ fn name_res_works_for_broken_modules() {
         pub struct Baz;
         ",
     );
-    assert_snapshot_matches!(map,
-        @r###"
-crate
-Baz: _
-"###
-    );
+    assert_snapshot_matches!(map, @r###"
+        ⋮crate
+        ⋮Baz: _
+    "###);
 }
 
 #[test]
@@ -369,19 +365,17 @@ fn item_map_using_self() {
         pub struct Baz;
         ",
     );
-    assert_snapshot_matches!(map,
-        @r###"
-crate
-Baz: t v
-foo: t
-
-crate::foo
-bar: t
-
-crate::foo::bar
-Baz: t v
-"###
-    );
+    assert_snapshot_matches!(map, @r###"
+        ⋮crate
+        ⋮Baz: t v
+        ⋮foo: t
+        ⋮
+        ⋮crate::foo
+        ⋮bar: t
+        ⋮
+        ⋮crate::foo::bar
+        ⋮Baz: t v
+    "###);
 }
 
 #[test]
@@ -400,12 +394,10 @@ fn item_map_across_crates() {
         },
     );
 
-    assert_snapshot_matches!(map,
-        @r###"
-crate
-Baz: t v
-"###
-    );
+    assert_snapshot_matches!(map, @r###"
+        ⋮crate
+        ⋮Baz: t v
+    "###);
 }
 
 #[test]
@@ -430,12 +422,14 @@ fn extern_crate_rename() {
         },
     );
 
-    assert_snapshot_matches!(map,
-        @r###"
-crate
-Arc: t v
-"###
-    );
+    assert_snapshot_matches!(map, @r###"
+   ⋮crate
+   ⋮alloc_crate: t
+   ⋮sync: t
+   ⋮
+   ⋮crate::sync
+   ⋮Arc: t v
+    "###);
 }
 
 #[test]
@@ -462,9 +456,13 @@ fn extern_crate_rename_2015_edition() {
 
     assert_snapshot_matches!(map,
         @r###"
-crate
-Arc: t v
-"###
+   ⋮crate
+   ⋮alloc_crate: t
+   ⋮sync: t
+   ⋮
+   ⋮crate::sync
+   ⋮Arc: t v
+    "###
     );
 }
 
@@ -490,12 +488,10 @@ fn import_across_source_roots() {
         },
     );
 
-    assert_snapshot_matches!(map,
-        @r###"
-crate
-C: t v
-"###
-    );
+    assert_snapshot_matches!(map, @r###"
+        ⋮crate
+        ⋮C: t v
+    "###);
 }
 
 #[test]
@@ -519,12 +515,10 @@ fn reexport_across_crates() {
         },
     );
 
-    assert_snapshot_matches!(map,
-        @r###"
-crate
-Baz: t v
-"###
-    );
+    assert_snapshot_matches!(map, @r###"
+        ⋮crate
+        ⋮Baz: t v
+    "###);
 }
 
 #[test]
@@ -544,13 +538,11 @@ fn values_dont_shadow_extern_crates() {
         },
     );
 
-    assert_snapshot_matches!(map,
-        @r###"
-crate
-Bar: t v
-foo: v
-"###
-    );
+    assert_snapshot_matches!(map, @r###"
+        ⋮crate
+        ⋮Bar: t v
+        ⋮foo: v
+    "###);
 }
 
 #[test]
diff --git a/crates/ra_hir/src/nameres/tests/globs.rs b/crates/ra_hir/src/nameres/tests/globs.rs
index 6e50c7ff6..e1519ca6b 100644
--- a/crates/ra_hir/src/nameres/tests/globs.rs
+++ b/crates/ra_hir/src/nameres/tests/globs.rs
@@ -18,20 +18,20 @@ fn glob_1() {
         ",
     );
     assert_snapshot_matches!(map, @r###"
-crate
-bar: t
-Foo: t v
-Baz: t v
-foo: t
-
-crate::foo
-bar: t
-Foo: t v
-Baz: t v
-
-crate::foo::bar
-Baz: t v
-"###
+   ⋮crate
+   ⋮Baz: t v
+   ⋮Foo: t v
+   ⋮bar: t
+   ⋮foo: t
+   ⋮
+   ⋮crate::foo
+   ⋮Baz: t v
+   ⋮Foo: t v
+   ⋮bar: t
+   ⋮
+   ⋮crate::foo::bar
+   ⋮Baz: t v
+    "###
     );
 }
 
@@ -54,22 +54,22 @@ fn glob_2() {
         ",
     );
     assert_snapshot_matches!(map, @r###"
-crate
-bar: t
-Foo: t v
-Baz: t v
-foo: t
-
-crate::foo
-bar: t
-Foo: t v
-Baz: t v
-
-crate::foo::bar
-bar: t
-Foo: t v
-Baz: t v
-"###
+   ⋮crate
+   ⋮Baz: t v
+   ⋮Foo: t v
+   ⋮bar: t
+   ⋮foo: t
+   ⋮
+   ⋮crate::foo
+   ⋮Baz: t v
+   ⋮Foo: t v
+   ⋮bar: t
+   ⋮
+   ⋮crate::foo::bar
+   ⋮Baz: t v
+   ⋮Foo: t v
+   ⋮bar: t
+    "###
     );
 }
 
@@ -90,9 +90,9 @@ fn glob_across_crates() {
         },
     );
     assert_snapshot_matches!(map, @r###"
-crate
-Baz: t v
-"###
+   ⋮crate
+   ⋮Baz: t v
+    "###
     );
 }
 
@@ -109,10 +109,10 @@ fn glob_enum() {
         ",
     );
     assert_snapshot_matches!(map, @r###"
-crate
-Foo: t
-Bar: t v
-Baz: t v
-"###
+   ⋮crate
+   ⋮Bar: t v
+   ⋮Baz: t v
+   ⋮Foo: t
+    "###
     );
 }
diff --git a/crates/ra_hir/src/nameres/tests/macros.rs b/crates/ra_hir/src/nameres/tests/macros.rs
index 8781b026b..f7ca380ad 100644
--- a/crates/ra_hir/src/nameres/tests/macros.rs
+++ b/crates/ra_hir/src/nameres/tests/macros.rs
@@ -18,14 +18,14 @@ fn macro_rules_are_globally_visible() {
         ",
     );
     assert_snapshot_matches!(map, @r###"
-crate
-nested: t
-Foo: t v
-
-crate::nested
-Bar: t v
-Baz: t v
-"###);
+   ⋮crate
+   ⋮Foo: t v
+   ⋮nested: t
+   ⋮
+   ⋮crate::nested
+   ⋮Bar: t v
+   ⋮Baz: t v
+    "###);
 }
 
 #[test]
@@ -45,15 +45,15 @@ fn macro_rules_can_define_modules() {
         ",
     );
     assert_snapshot_matches!(map, @r###"
-crate
-n1: t
-
-crate::n1
-n2: t
-
-crate::n1::n2
-X: t v
-"###);
+   ⋮crate
+   ⋮n1: t
+   ⋮
+   ⋮crate::n1
+   ⋮n2: t
+   ⋮
+   ⋮crate::n1::n2
+   ⋮X: t v
+    "###);
 }
 
 #[test]
@@ -81,14 +81,14 @@ fn macro_rules_from_other_crates_are_visible() {
         },
     );
     assert_snapshot_matches!(map, @r###"
-crate
-bar: t
-Foo: t v
-Bar: t v
-
-crate::bar
-bar: t
-Foo: t v
-Bar: t v
-"###);
+   ⋮crate
+   ⋮Bar: t v
+   ⋮Foo: t v
+   ⋮bar: t
+   ⋮
+   ⋮crate::bar
+   ⋮Bar: t v
+   ⋮Foo: t v
+   ⋮bar: t
+    "###);
 }
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index 9a65bf567..3679a2242 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -20,7 +20,7 @@ use crate::{Name, AdtDef, type_ref::Mutability, db::HirDatabase, Trait, GenericP
 use display::{HirDisplay, HirFormatter};
 
 pub(crate) use lower::{TypableDef, type_for_def, type_for_field, callable_item_sig, generic_predicates, generic_defaults};
-pub(crate) use infer::{infer, InferenceResult, InferTy};
+pub(crate) use infer::{infer_query, InferenceResult, InferTy};
 pub use lower::CallableDef;
 
 /// A type constructor or type name: this might be something like the primitive
diff --git a/crates/ra_hir/src/ty/infer.rs b/crates/ra_hir/src/ty/infer.rs
index 1e7d97f51..a48272981 100644
--- a/crates/ra_hir/src/ty/infer.rs
+++ b/crates/ra_hir/src/ty/infer.rs
@@ -23,6 +23,7 @@ use ena::unify::{InPlaceUnificationTable, UnifyKey, UnifyValue, NoError};
 use rustc_hash::FxHashMap;
 
 use ra_arena::map::ArenaMap;
+use ra_prof::profile;
 use test_utils::tested_by;
 
 use crate::{
@@ -51,7 +52,8 @@ use super::{
 mod unify;
 
 /// The entry point of type inference.
-pub fn infer(db: &impl HirDatabase, def: DefWithBody) -> Arc<InferenceResult> {
+pub fn infer_query(db: &impl HirDatabase, def: DefWithBody) -> Arc<InferenceResult> {
+    let _p = profile("infer_query");
     db.check_canceled();
     let body = def.body(db);
     let resolver = def.resolver(db);
diff --git a/crates/ra_hir/src/ty/traits.rs b/crates/ra_hir/src/ty/traits.rs
index 7de04c044..f39749cab 100644
--- a/crates/ra_hir/src/ty/traits.rs
+++ b/crates/ra_hir/src/ty/traits.rs
@@ -4,6 +4,7 @@ use std::sync::{Arc, Mutex};
 use rustc_hash::FxHashSet;
 use log::debug;
 use chalk_ir::cast::Cast;
+use ra_prof::profile;
 
 use crate::{Crate, Trait, db::HirDatabase, ImplBlock};
 use super::{TraitRef, Ty, Canonical};
@@ -25,7 +26,7 @@ struct ChalkContext<'a, DB> {
     krate: Crate,
 }
 
-pub(crate) fn solver(_db: &impl HirDatabase, _krate: Crate) -> Arc<Mutex<Solver>> {
+pub(crate) fn solver_query(_db: &impl HirDatabase, _krate: Crate) -> Arc<Mutex<Solver>> {
     // krate parameter is just so we cache a unique solver per crate
     let solver_choice = chalk_solve::SolverChoice::SLG { max_size: CHALK_SOLVER_MAX_SIZE };
     debug!("Creating new solver for crate {:?}", _krate);
@@ -33,7 +34,7 @@ pub(crate) fn solver(_db: &impl HirDatabase, _krate: Crate) -> Arc<Mutex<Solver>
 }
 
 /// Collects impls for the given trait in the whole dependency tree of `krate`.
-pub(crate) fn impls_for_trait(
+pub(crate) fn impls_for_trait_query(
     db: &impl HirDatabase,
     krate: Crate,
     trait_: Trait,
@@ -76,11 +77,12 @@ pub enum Obligation {
 }
 
 /// Check using Chalk whether trait is implemented for given parameters including `Self` type.
-pub(crate) fn implements(
+pub(crate) fn implements_query(
     db: &impl HirDatabase,
     krate: Crate,
     trait_ref: Canonical<TraitRef>,
 ) -> Option<Solution> {
+    let _p = profile("implements_query");
     let goal: chalk_ir::Goal = trait_ref.value.to_chalk(db).cast();
     debug!("goal: {:?}", goal);
     let env = chalk_ir::Environment::new();