Improve autocompletion by looking on the type and name

Signed-off-by: Benjamin Coenen <[email protected]>

12 files changed, 558 insertions, 125 deletions

diff --git a/crates/ra_hir_ty/Cargo.toml b/crates/ra_hir_ty/Cargo.toml
index 9a4a7aa6f..59efc1c31 100644
--- a/crates/ra_hir_ty/Cargo.toml
+++ b/crates/ra_hir_ty/Cargo.toml
@@ -24,6 +24,8 @@ ra_prof = { path = "../ra_prof" }
 ra_syntax = { path = "../ra_syntax" }
 test_utils = { path = "../test_utils" }
 
+scoped-tls = "1"
+
 chalk-solve =   { git = "https://github.com/rust-lang/chalk.git", rev = "039fc904a05f8cb3d0c682c9a57a63dda7a35356" }
 chalk-rust-ir = { git = "https://github.com/rust-lang/chalk.git", rev = "039fc904a05f8cb3d0c682c9a57a63dda7a35356" }
 chalk-ir =      { git = "https://github.com/rust-lang/chalk.git", rev = "039fc904a05f8cb3d0c682c9a57a63dda7a35356" }
diff --git a/crates/ra_hir_ty/src/db.rs b/crates/ra_hir_ty/src/db.rs
index 1462b053f..33da16b48 100644
--- a/crates/ra_hir_ty/src/db.rs
+++ b/crates/ra_hir_ty/src/db.rs
@@ -11,7 +11,7 @@ use ra_db::{impl_intern_key, salsa, CrateId, Upcast};
 use ra_prof::profile;
 
 use crate::{
-    method_resolution::CrateImplDefs,
+    method_resolution::{CrateImplDefs, TyFingerprint},
     traits::{chalk, AssocTyValue, Impl},
     Binders, CallableDef, GenericPredicate, InferenceResult, PolyFnSig, Substs, TraitRef, Ty,
     TyDefId, TypeCtor, ValueTyDefId,
@@ -65,7 +65,12 @@ pub trait HirDatabase: DefDatabase + Upcast<dyn DefDatabase> {
     fn impls_in_crate(&self, krate: CrateId) -> Arc<CrateImplDefs>;
 
     #[salsa::invoke(crate::traits::impls_for_trait_query)]
-    fn impls_for_trait(&self, krate: CrateId, trait_: TraitId) -> Arc<[ImplId]>;
+    fn impls_for_trait(
+        &self,
+        krate: CrateId,
+        trait_: TraitId,
+        self_ty_fp: Option<TyFingerprint>,
+    ) -> Arc<[ImplId]>;
 
     // Interned IDs for Chalk integration
     #[salsa::interned]
diff --git a/crates/ra_hir_ty/src/diagnostics.rs b/crates/ra_hir_ty/src/diagnostics.rs
index 8cbce1168..927896d6f 100644
--- a/crates/ra_hir_ty/src/diagnostics.rs
+++ b/crates/ra_hir_ty/src/diagnostics.rs
@@ -21,7 +21,7 @@ impl Diagnostic for NoSuchField {
     }
 
     fn source(&self) -> InFile<SyntaxNodePtr> {
-        InFile { file_id: self.file, value: self.field.into() }
+        InFile { file_id: self.file, value: self.field.clone().into() }
     }
 
     fn as_any(&self) -> &(dyn Any + Send + 'static) {
@@ -45,7 +45,7 @@ impl Diagnostic for MissingFields {
         buf
     }
     fn source(&self) -> InFile<SyntaxNodePtr> {
-        InFile { file_id: self.file, value: self.field_list.into() }
+        InFile { file_id: self.file, value: self.field_list.clone().into() }
     }
     fn as_any(&self) -> &(dyn Any + Send + 'static) {
         self
@@ -63,6 +63,29 @@ impl AstDiagnostic for MissingFields {
 }
 
 #[derive(Debug)]
+pub struct MissingPatFields {
+    pub file: HirFileId,
+    pub field_list: AstPtr<ast::RecordFieldPatList>,
+    pub missed_fields: Vec<Name>,
+}
+
+impl Diagnostic for MissingPatFields {
+    fn message(&self) -> String {
+        let mut buf = String::from("Missing structure fields:\n");
+        for field in &self.missed_fields {
+            format_to!(buf, "- {}", field);
+        }
+        buf
+    }
+    fn source(&self) -> InFile<SyntaxNodePtr> {
+        InFile { file_id: self.file, value: self.field_list.clone().into() }
+    }
+    fn as_any(&self) -> &(dyn Any + Send + 'static) {
+        self
+    }
+}
+
+#[derive(Debug)]
 pub struct MissingMatchArms {
     pub file: HirFileId,
     pub match_expr: AstPtr<ast::Expr>,
@@ -74,7 +97,7 @@ impl Diagnostic for MissingMatchArms {
         String::from("Missing match arm")
     }
     fn source(&self) -> InFile<SyntaxNodePtr> {
-        InFile { file_id: self.file, value: self.match_expr.into() }
+        InFile { file_id: self.file, value: self.match_expr.clone().into() }
     }
     fn as_any(&self) -> &(dyn Any + Send + 'static) {
         self
@@ -92,7 +115,7 @@ impl Diagnostic for MissingOkInTailExpr {
         "wrap return expression in Ok".to_string()
     }
     fn source(&self) -> InFile<SyntaxNodePtr> {
-        InFile { file_id: self.file, value: self.expr.into() }
+        InFile { file_id: self.file, value: self.expr.clone().into() }
     }
     fn as_any(&self) -> &(dyn Any + Send + 'static) {
         self
diff --git a/crates/ra_hir_ty/src/display.rs b/crates/ra_hir_ty/src/display.rs
index 0e9313aa1..d03bbd5a7 100644
--- a/crates/ra_hir_ty/src/display.rs
+++ b/crates/ra_hir_ty/src/display.rs
@@ -247,19 +247,21 @@ impl HirDisplay for ApplicationTy {
                 }
             }
             TypeCtor::Closure { .. } => {
-                let sig = self.parameters[0]
-                    .callable_sig(f.db)
-                    .expect("first closure parameter should contain signature");
-                if sig.params().is_empty() {
-                    write!(f, "||")?;
-                } else if f.omit_verbose_types() {
-                    write!(f, "|{}|", TYPE_HINT_TRUNCATION)?;
+                let sig = self.parameters[0].callable_sig(f.db);
+                if let Some(sig) = sig {
+                    if sig.params().is_empty() {
+                        write!(f, "||")?;
+                    } else if f.omit_verbose_types() {
+                        write!(f, "|{}|", TYPE_HINT_TRUNCATION)?;
+                    } else {
+                        write!(f, "|")?;
+                        f.write_joined(sig.params(), ", ")?;
+                        write!(f, "|")?;
+                    };
+                    write!(f, " -> {}", sig.ret().display(f.db))?;
                 } else {
-                    write!(f, "|")?;
-                    f.write_joined(sig.params(), ", ")?;
-                    write!(f, "|")?;
-                };
-                write!(f, " -> {}", sig.ret().display(f.db))?;
+                    write!(f, "{{closure}}")?;
+                }
             }
         }
         Ok(())
diff --git a/crates/ra_hir_ty/src/expr.rs b/crates/ra_hir_ty/src/expr.rs
index e45e9ea14..69b527f74 100644
--- a/crates/ra_hir_ty/src/expr.rs
+++ b/crates/ra_hir_ty/src/expr.rs
@@ -9,7 +9,7 @@ use rustc_hash::FxHashSet;
 
 use crate::{
     db::HirDatabase,
-    diagnostics::{MissingFields, MissingMatchArms, MissingOkInTailExpr},
+    diagnostics::{MissingFields, MissingMatchArms, MissingOkInTailExpr, MissingPatFields},
     utils::variant_data,
     ApplicationTy, InferenceResult, Ty, TypeCtor,
     _match::{is_useful, MatchCheckCtx, Matrix, PatStack, Usefulness},
@@ -49,39 +49,95 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
             if let Some((variant_def, missed_fields, true)) =
                 record_literal_missing_fields(db, &self.infer, id, expr)
             {
-                // XXX: only look at source_map if we do have missing fields
-                let (_, source_map) = db.body_with_source_map(self.func.into());
-
-                if let Ok(source_ptr) = source_map.expr_syntax(id) {
-                    if let Some(expr) = source_ptr.value.left() {
-                        let root = source_ptr.file_syntax(db.upcast());
-                        if let ast::Expr::RecordLit(record_lit) = expr.to_node(&root) {
-                            if let Some(field_list) = record_lit.record_field_list() {
-                                let variant_data = variant_data(db.upcast(), variant_def);
-                                let missed_fields = missed_fields
-                                    .into_iter()
-                                    .map(|idx| variant_data.fields()[idx].name.clone())
-                                    .collect();
-                                self.sink.push(MissingFields {
-                                    file: source_ptr.file_id,
-                                    field_list: AstPtr::new(&field_list),
-                                    missed_fields,
-                                })
-                            }
-                        }
-                    }
-                }
+                self.create_record_literal_missing_fields_diagnostic(
+                    id,
+                    db,
+                    variant_def,
+                    missed_fields,
+                );
             }
             if let Expr::Match { expr, arms } = expr {
                 self.validate_match(id, *expr, arms, db, self.infer.clone());
             }
         }
+        for (id, pat) in body.pats.iter() {
+            if let Some((variant_def, missed_fields, true)) =
+                record_pattern_missing_fields(db, &self.infer, id, pat)
+            {
+                self.create_record_pattern_missing_fields_diagnostic(
+                    id,
+                    db,
+                    variant_def,
+                    missed_fields,
+                );
+            }
+        }
         let body_expr = &body[body.body_expr];
         if let Expr::Block { tail: Some(t), .. } = body_expr {
             self.validate_results_in_tail_expr(body.body_expr, *t, db);
         }
     }
 
+    fn create_record_literal_missing_fields_diagnostic(
+        &mut self,
+        id: ExprId,
+        db: &dyn HirDatabase,
+        variant_def: VariantId,
+        missed_fields: Vec<LocalStructFieldId>,
+    ) {
+        // XXX: only look at source_map if we do have missing fields
+        let (_, source_map) = db.body_with_source_map(self.func.into());
+
+        if let Ok(source_ptr) = source_map.expr_syntax(id) {
+            let root = source_ptr.file_syntax(db.upcast());
+            if let ast::Expr::RecordLit(record_lit) = &source_ptr.value.to_node(&root) {
+                if let Some(field_list) = record_lit.record_field_list() {
+                    let variant_data = variant_data(db.upcast(), variant_def);
+                    let missed_fields = missed_fields
+                        .into_iter()
+                        .map(|idx| variant_data.fields()[idx].name.clone())
+                        .collect();
+                    self.sink.push(MissingFields {
+                        file: source_ptr.file_id,
+                        field_list: AstPtr::new(&field_list),
+                        missed_fields,
+                    })
+                }
+            }
+        }
+    }
+
+    fn create_record_pattern_missing_fields_diagnostic(
+        &mut self,
+        id: PatId,
+        db: &dyn HirDatabase,
+        variant_def: VariantId,
+        missed_fields: Vec<LocalStructFieldId>,
+    ) {
+        // XXX: only look at source_map if we do have missing fields
+        let (_, source_map) = db.body_with_source_map(self.func.into());
+
+        if let Ok(source_ptr) = source_map.pat_syntax(id) {
+            if let Some(expr) = source_ptr.value.as_ref().left() {
+                let root = source_ptr.file_syntax(db.upcast());
+                if let ast::Pat::RecordPat(record_pat) = expr.to_node(&root) {
+                    if let Some(field_list) = record_pat.record_field_pat_list() {
+                        let variant_data = variant_data(db.upcast(), variant_def);
+                        let missed_fields = missed_fields
+                            .into_iter()
+                            .map(|idx| variant_data.fields()[idx].name.clone())
+                            .collect();
+                        self.sink.push(MissingPatFields {
+                            file: source_ptr.file_id,
+                            field_list: AstPtr::new(&field_list),
+                            missed_fields,
+                        })
+                    }
+                }
+            }
+        }
+    }
+
     fn validate_match(
         &mut self,
         id: ExprId,
@@ -147,18 +203,16 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
         }
 
         if let Ok(source_ptr) = source_map.expr_syntax(id) {
-            if let Some(expr) = source_ptr.value.left() {
-                let root = source_ptr.file_syntax(db.upcast());
-                if let ast::Expr::MatchExpr(match_expr) = expr.to_node(&root) {
-                    if let (Some(match_expr), Some(arms)) =
-                        (match_expr.expr(), match_expr.match_arm_list())
-                    {
-                        self.sink.push(MissingMatchArms {
-                            file: source_ptr.file_id,
-                            match_expr: AstPtr::new(&match_expr),
-                            arms: AstPtr::new(&arms),
-                        })
-                    }
+            let root = source_ptr.file_syntax(db.upcast());
+            if let ast::Expr::MatchExpr(match_expr) = &source_ptr.value.to_node(&root) {
+                if let (Some(match_expr), Some(arms)) =
+                    (match_expr.expr(), match_expr.match_arm_list())
+                {
+                    self.sink.push(MissingMatchArms {
+                        file: source_ptr.file_id,
+                        match_expr: AstPtr::new(&match_expr),
+                        arms: AstPtr::new(&arms),
+                    })
                 }
             }
         }
@@ -189,9 +243,8 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
             let (_, source_map) = db.body_with_source_map(self.func.into());
 
             if let Ok(source_ptr) = source_map.expr_syntax(id) {
-                if let Some(expr) = source_ptr.value.left() {
-                    self.sink.push(MissingOkInTailExpr { file: source_ptr.file_id, expr });
-                }
+                self.sink
+                    .push(MissingOkInTailExpr { file: source_ptr.file_id, expr: source_ptr.value });
             }
         }
     }
@@ -232,9 +285,9 @@ pub fn record_pattern_missing_fields(
     infer: &InferenceResult,
     id: PatId,
     pat: &Pat,
-) -> Option<(VariantId, Vec<LocalStructFieldId>)> {
-    let fields = match pat {
-        Pat::Record { path: _, args } => args,
+) -> Option<(VariantId, Vec<LocalStructFieldId>, /*exhaustive*/ bool)> {
+    let (fields, exhaustive) = match pat {
+        Pat::Record { path: _, args, ellipsis } => (args, !ellipsis),
         _ => return None,
     };
 
@@ -254,5 +307,5 @@ pub fn record_pattern_missing_fields(
     if missed_fields.is_empty() {
         return None;
     }
-    Some((variant_def, missed_fields))
+    Some((variant_def, missed_fields, exhaustive))
 }
diff --git a/crates/ra_hir_ty/src/infer/pat.rs b/crates/ra_hir_ty/src/infer/pat.rs
index 69bbb4307..078476f76 100644
--- a/crates/ra_hir_ty/src/infer/pat.rs
+++ b/crates/ra_hir_ty/src/infer/pat.rs
@@ -158,7 +158,7 @@ impl<'a> InferenceContext<'a> {
             Pat::TupleStruct { path: p, args: subpats } => {
                 self.infer_tuple_struct_pat(p.as_ref(), subpats, expected, default_bm, pat)
             }
-            Pat::Record { path: p, args: fields } => {
+            Pat::Record { path: p, args: fields, ellipsis: _ } => {
                 self.infer_record_pat(p.as_ref(), fields, expected, default_bm, pat)
             }
             Pat::Path(path) => {
diff --git a/crates/ra_hir_ty/src/method_resolution.rs b/crates/ra_hir_ty/src/method_resolution.rs
index 74a0bc7db..657284fd0 100644
--- a/crates/ra_hir_ty/src/method_resolution.rs
+++ b/crates/ra_hir_ty/src/method_resolution.rs
@@ -34,7 +34,7 @@ impl TyFingerprint {
     /// Creates a TyFingerprint for looking up an impl. Only certain types can
     /// have impls: if we have some `struct S`, we can have an `impl S`, but not
     /// `impl &S`. Hence, this will return `None` for reference types and such.
-    fn for_impl(ty: &Ty) -> Option<TyFingerprint> {
+    pub(crate) fn for_impl(ty: &Ty) -> Option<TyFingerprint> {
         match ty {
             Ty::Apply(a_ty) => Some(TyFingerprint::Apply(a_ty.ctor)),
             _ => None,
@@ -45,7 +45,7 @@ impl TyFingerprint {
 #[derive(Debug, PartialEq, Eq)]
 pub struct CrateImplDefs {
     impls: FxHashMap<TyFingerprint, Vec<ImplId>>,
-    impls_by_trait: FxHashMap<TraitId, Vec<ImplId>>,
+    impls_by_trait: FxHashMap<TraitId, FxHashMap<Option<TyFingerprint>, Vec<ImplId>>>,
 }
 
 impl CrateImplDefs {
@@ -59,7 +59,14 @@ impl CrateImplDefs {
             for impl_id in module_data.scope.impls() {
                 match db.impl_trait(impl_id) {
                     Some(tr) => {
-                        res.impls_by_trait.entry(tr.value.trait_).or_default().push(impl_id);
+                        let self_ty = db.impl_self_ty(impl_id);
+                        let self_ty_fp = TyFingerprint::for_impl(&self_ty.value);
+                        res.impls_by_trait
+                            .entry(tr.value.trait_)
+                            .or_default()
+                            .entry(self_ty_fp)
+                            .or_default()
+                            .push(impl_id);
                     }
                     None => {
                         let self_ty = db.impl_self_ty(impl_id);
@@ -79,11 +86,39 @@ impl CrateImplDefs {
     }
 
     pub fn lookup_impl_defs_for_trait(&self, tr: TraitId) -> impl Iterator<Item = ImplId> + '_ {
-        self.impls_by_trait.get(&tr).into_iter().flatten().copied()
+        self.impls_by_trait
+            .get(&tr)
+            .into_iter()
+            .flat_map(|m| m.values().flat_map(|v| v.iter().copied()))
+    }
+
+    pub fn lookup_impl_defs_for_trait_and_ty(
+        &self,
+        tr: TraitId,
+        fp: TyFingerprint,
+    ) -> impl Iterator<Item = ImplId> + '_ {
+        self.impls_by_trait
+            .get(&tr)
+            .and_then(|m| m.get(&Some(fp)))
+            .into_iter()
+            .flatten()
+            .copied()
+            .chain(
+                self.impls_by_trait
+                    .get(&tr)
+                    .and_then(|m| m.get(&None))
+                    .into_iter()
+                    .flatten()
+                    .copied(),
+            )
     }
 
     pub fn all_impls<'a>(&'a self) -> impl Iterator<Item = ImplId> + 'a {
-        self.impls.values().chain(self.impls_by_trait.values()).flatten().copied()
+        self.impls
+            .values()
+            .chain(self.impls_by_trait.values().flat_map(|m| m.values()))
+            .flatten()
+            .copied()
     }
 }
 
diff --git a/crates/ra_hir_ty/src/tests.rs b/crates/ra_hir_ty/src/tests.rs
index 08723068f..81fc0f63a 100644
--- a/crates/ra_hir_ty/src/tests.rs
+++ b/crates/ra_hir_ty/src/tests.rs
@@ -23,7 +23,7 @@ use insta::assert_snapshot;
 use ra_db::{fixture::WithFixture, salsa::Database, FilePosition, SourceDatabase};
 use ra_syntax::{
     algo,
-    ast::{self, AstNode, AstToken},
+    ast::{self, AstNode},
 };
 use stdx::format_to;
 
@@ -82,12 +82,10 @@ fn infer_with_mismatches(content: &str, include_mismatches: bool) -> String {
 
         for (expr, ty) in inference_result.type_of_expr.iter() {
             let syntax_ptr = match body_source_map.expr_syntax(expr) {
-                Ok(sp) => {
-                    sp.map(|ast| ast.either(|it| it.syntax_node_ptr(), |it| it.syntax_node_ptr()))
-                }
+                Ok(sp) => sp.map(|ast| ast.syntax_node_ptr()),
                 Err(SyntheticSyntax) => continue,
             };
-            types.push((syntax_ptr, ty));
+            types.push((syntax_ptr.clone(), ty));
             if let Some(mismatch) = inference_result.type_mismatch_for_expr(expr) {
                 mismatches.push((syntax_ptr, mismatch));
             }
@@ -101,7 +99,7 @@ fn infer_with_mismatches(content: &str, include_mismatches: bool) -> String {
             let node = src_ptr.value.to_node(&src_ptr.file_syntax(&db));
 
             let (range, text) = if let Some(self_param) = ast::SelfParam::cast(node.clone()) {
-                (self_param.self_kw().unwrap().syntax().text_range(), "self".to_string())
+                (self_param.self_token().unwrap().text_range(), "self".to_string())
             } else {
                 (src_ptr.value.range(), node.text().to_string().replace("\n", " "))
             };
@@ -409,3 +407,43 @@ fn no_such_field_with_feature_flag_diagnostics_on_struct_fields() {
 
     assert_snapshot!(diagnostics, @r###""###);
 }
+
+#[test]
+fn missing_record_pat_field_diagnostic() {
+    let diagnostics = TestDB::with_files(
+        r"
+        //- /lib.rs
+        struct S { foo: i32, bar: () }
+        fn baz(s: S) {
+            let S { foo: _ } = s;
+        }
+        ",
+    )
+    .diagnostics()
+    .0;
+
+    assert_snapshot!(diagnostics, @r###"
+    "{ foo: _ }": Missing structure fields:
+    - bar
+    "###
+    );
+}
+
+#[test]
+fn missing_record_pat_field_no_diagnostic_if_not_exhaustive() {
+    let diagnostics = TestDB::with_files(
+        r"
+        //- /lib.rs
+        struct S { foo: i32, bar: () }
+        fn baz(s: S) -> i32 {
+            match s {
+                S { foo, .. } => foo,
+            }
+        }
+        ",
+    )
+    .diagnostics()
+    .0;
+
+    assert_snapshot!(diagnostics, @"");
+}
diff --git a/crates/ra_hir_ty/src/tests/macros.rs b/crates/ra_hir_ty/src/tests/macros.rs
index ff4599b71..f2a9b1c40 100644
--- a/crates/ra_hir_ty/src/tests/macros.rs
+++ b/crates/ra_hir_ty/src/tests/macros.rs
@@ -1,10 +1,13 @@
+use std::fs;
+
 use insta::assert_snapshot;
 use ra_db::fixture::WithFixture;
-
-use super::{infer, type_at, type_at_pos};
+use test_utils::project_dir;
 
 use crate::test_db::TestDB;
 
+use super::{infer, type_at, type_at_pos};
+
 #[test]
 fn cfg_impl_def() {
     let (db, pos) = TestDB::with_position(
@@ -482,6 +485,30 @@ fn bar() -> u32 {0}
 }
 
 #[test]
+#[ignore]
+fn include_accidentally_quadratic() {
+    let file = project_dir().join("crates/ra_syntax/test_data/accidentally_quadratic");
+    let big_file = fs::read_to_string(file).unwrap();
+    let big_file = vec![big_file; 10].join("\n");
+
+    let fixture = r#"
+//- /main.rs
+#[rustc_builtin_macro]
+macro_rules! include {() => {}}
+
+include!("foo.rs");
+
+fn main() {
+    RegisterBlock { }<|>;
+}
+    "#;
+    let fixture = format!("{}\n//- /foo.rs\n{}", fixture, big_file);
+
+    let (db, pos) = TestDB::with_position(&fixture);
+    assert_eq!("RegisterBlock", type_at_pos(&db, pos));
+}
+
+#[test]
 fn infer_builtin_macros_include_concat() {
     let (db, pos) = TestDB::with_position(
         r#"
diff --git a/crates/ra_hir_ty/src/traits.rs b/crates/ra_hir_ty/src/traits.rs
index 5a1e12ce9..43d8d1e80 100644
--- a/crates/ra_hir_ty/src/traits.rs
+++ b/crates/ra_hir_ty/src/traits.rs
@@ -7,7 +7,7 @@ use ra_db::{impl_intern_key, salsa, CrateId};
 use ra_prof::profile;
 use rustc_hash::FxHashSet;
 
-use crate::{db::HirDatabase, DebruijnIndex};
+use crate::{db::HirDatabase, method_resolution::TyFingerprint, DebruijnIndex};
 
 use super::{Canonical, GenericPredicate, HirDisplay, ProjectionTy, TraitRef, Ty, TypeWalk};
 
@@ -40,7 +40,12 @@ pub(crate) fn impls_for_trait_query(
     db: &dyn HirDatabase,
     krate: CrateId,
     trait_: TraitId,
+    self_ty_fp: Option<TyFingerprint>,
 ) -> Arc<[ImplId]> {
+    // FIXME: We could be a lot smarter here - because of the orphan rules and
+    // the fact that the trait and the self type need to be in the dependency
+    // tree of a crate somewhere for an impl to exist, we could skip looking in
+    // a lot of crates completely
     let mut impls = FxHashSet::default();
     // We call the query recursively here. On the one hand, this means we can
     // reuse results from queries for different crates; on the other hand, this
@@ -48,10 +53,13 @@ pub(crate) fn impls_for_trait_query(
     // ones the user is editing), so this may actually be a waste of memory. I'm
     // doing it like this mainly for simplicity for now.
     for dep in &db.crate_graph()[krate].dependencies {
-        impls.extend(db.impls_for_trait(dep.crate_id, trait_).iter());
+        impls.extend(db.impls_for_trait(dep.crate_id, trait_, self_ty_fp).iter());
     }
     let crate_impl_defs = db.impls_in_crate(krate);
-    impls.extend(crate_impl_defs.lookup_impl_defs_for_trait(trait_));
+    match self_ty_fp {
+        Some(fp) => impls.extend(crate_impl_defs.lookup_impl_defs_for_trait_and_ty(trait_, fp)),
+        None => impls.extend(crate_impl_defs.lookup_impl_defs_for_trait(trait_)),
+    }
     impls.into_iter().collect()
 }
 
@@ -177,7 +185,7 @@ fn solve(
 
     let fuel = std::cell::Cell::new(CHALK_SOLVER_FUEL);
 
-    let solution = solver.solve_limited(&context, goal, || {
+    let should_continue = || {
         context.db.check_canceled();
         let remaining = fuel.get();
         fuel.set(remaining - 1);
@@ -185,12 +193,21 @@ fn solve(
             log::debug!("fuel exhausted");
         }
         remaining > 0
-    });
+    };
+    let mut solve = || solver.solve_limited(&context, goal, should_continue);
+    // don't set the TLS for Chalk unless Chalk debugging is active, to make
+    // extra sure we only use it for debugging
+    let solution =
+        if is_chalk_debug() { chalk::tls::set_current_program(db, solve) } else { solve() };
 
     log::debug!("solve({:?}) => {:?}", goal, solution);
     solution
 }
 
+fn is_chalk_debug() -> bool {
+    std::env::var("CHALK_DEBUG").is_ok()
+}
+
 fn solution_from_chalk(
     db: &dyn HirDatabase,
     solution: chalk_solve::Solution<Interner>,
diff --git a/crates/ra_hir_ty/src/traits/chalk.rs b/crates/ra_hir_ty/src/traits/chalk.rs
index 1bc0f0713..e05fea843 100644
--- a/crates/ra_hir_ty/src/traits/chalk.rs
+++ b/crates/ra_hir_ty/src/traits/chalk.rs
@@ -16,10 +16,12 @@ use ra_db::{
 
 use super::{builtin, AssocTyValue, Canonical, ChalkContext, Impl, Obligation};
 use crate::{
-    db::HirDatabase, display::HirDisplay, utils::generics, ApplicationTy, GenericPredicate,
-    ProjectionTy, Substs, TraitRef, Ty, TypeCtor,
+    db::HirDatabase, display::HirDisplay, method_resolution::TyFingerprint, utils::generics,
+    ApplicationTy, GenericPredicate, ProjectionTy, Substs, TraitRef, Ty, TypeCtor,
 };
 
+pub(super) mod tls;
+
 #[derive(Debug, Copy, Clone, Hash, PartialOrd, Ord, PartialEq, Eq)]
 pub struct Interner;
 
@@ -33,90 +35,85 @@ impl chalk_ir::interner::Interner for Interner {
     type Identifier = TypeAliasId;
     type DefId = InternId;
 
-    // FIXME: implement these
     fn debug_struct_id(
-        _type_kind_id: chalk_ir::StructId<Self>,
-        _fmt: &mut fmt::Formatter<'_>,
+        type_kind_id: StructId,
+        fmt: &mut fmt::Formatter<'_>,
     ) -> Option<fmt::Result> {
-        None
+        tls::with_current_program(|prog| Some(prog?.debug_struct_id(type_kind_id, fmt)))
     }
 
-    fn debug_trait_id(
-        _type_kind_id: chalk_ir::TraitId<Self>,
-        _fmt: &mut fmt::Formatter<'_>,
-    ) -> Option<fmt::Result> {
-        None
+    fn debug_trait_id(type_kind_id: TraitId, fmt: &mut fmt::Formatter<'_>) -> Option<fmt::Result> {
+        tls::with_current_program(|prog| Some(prog?.debug_trait_id(type_kind_id, fmt)))
     }
 
-    fn debug_assoc_type_id(
-        _id: chalk_ir::AssocTypeId<Self>,
-        _fmt: &mut fmt::Formatter<'_>,
-    ) -> Option<fmt::Result> {
-        None
+    fn debug_assoc_type_id(id: AssocTypeId, fmt: &mut fmt::Formatter<'_>) -> Option<fmt::Result> {
+        tls::with_current_program(|prog| Some(prog?.debug_assoc_type_id(id, fmt)))
     }
 
     fn debug_alias(
-        _projection: &chalk_ir::AliasTy<Self>,
-        _fmt: &mut fmt::Formatter<'_>,
+        alias: &chalk_ir::AliasTy<Interner>,
+        fmt: &mut fmt::Formatter<'_>,
     ) -> Option<fmt::Result> {
-        None
+        tls::with_current_program(|prog| Some(prog?.debug_alias(alias, fmt)))
     }
 
-    fn debug_ty(_ty: &chalk_ir::Ty<Self>, _fmt: &mut fmt::Formatter<'_>) -> Option<fmt::Result> {
-        None
+    fn debug_ty(ty: &chalk_ir::Ty<Interner>, fmt: &mut fmt::Formatter<'_>) -> Option<fmt::Result> {
+        tls::with_current_program(|prog| Some(prog?.debug_ty(ty, fmt)))
     }
 
     fn debug_lifetime(
-        _lifetime: &chalk_ir::Lifetime<Self>,
-        _fmt: &mut fmt::Formatter<'_>,
+        lifetime: &chalk_ir::Lifetime<Interner>,
+        fmt: &mut fmt::Formatter<'_>,
     ) -> Option<fmt::Result> {
-        None
+        tls::with_current_program(|prog| Some(prog?.debug_lifetime(lifetime, fmt)))
     }
 
     fn debug_parameter(
-        _parameter: &Parameter<Self>,
-        _fmt: &mut fmt::Formatter<'_>,
+        parameter: &Parameter<Interner>,
+        fmt: &mut fmt::Formatter<'_>,
     ) -> Option<fmt::Result> {
-        None
+        tls::with_current_program(|prog| Some(prog?.debug_parameter(parameter, fmt)))
     }
 
-    fn debug_goal(_goal: &Goal<Self>, _fmt: &mut fmt::Formatter<'_>) -> Option<fmt::Result> {
-        None
+    fn debug_goal(goal: &Goal<Interner>, fmt: &mut fmt::Formatter<'_>) -> Option<fmt::Result> {
+        tls::with_current_program(|prog| Some(prog?.debug_goal(goal, fmt)))
     }
 
     fn debug_goals(
-        _goals: &chalk_ir::Goals<Self>,
-        _fmt: &mut fmt::Formatter<'_>,
+        goals: &chalk_ir::Goals<Interner>,
+        fmt: &mut fmt::Formatter<'_>,
     ) -> Option<fmt::Result> {
-        None
+        tls::with_current_program(|prog| Some(prog?.debug_goals(goals, fmt)))
     }
 
     fn debug_program_clause_implication(
-        _pci: &chalk_ir::ProgramClauseImplication<Self>,
-        _fmt: &mut fmt::Formatter<'_>,
+        pci: &chalk_ir::ProgramClauseImplication<Interner>,
+        fmt: &mut fmt::Formatter<'_>,
     ) -> Option<fmt::Result> {
-        None
+        tls::with_current_program(|prog| Some(prog?.debug_program_clause_implication(pci, fmt)))
     }
 
     fn debug_application_ty(
-        _application_ty: &chalk_ir::ApplicationTy<Self>,
-        _fmt: &mut fmt::Formatter<'_>,
+        application_ty: &chalk_ir::ApplicationTy<Interner>,
+        fmt: &mut fmt::Formatter<'_>,
     ) -> Option<fmt::Result> {
-        None
+        tls::with_current_program(|prog| Some(prog?.debug_application_ty(application_ty, fmt)))
     }
 
     fn debug_substitution(
-        _substitution: &chalk_ir::Substitution<Self>,
-        _fmt: &mut fmt::Formatter<'_>,
+        substitution: &chalk_ir::Substitution<Interner>,
+        fmt: &mut fmt::Formatter<'_>,
     ) -> Option<fmt::Result> {
-        None
+        tls::with_current_program(|prog| Some(prog?.debug_substitution(substitution, fmt)))
     }
 
     fn debug_separator_trait_ref(
-        _separator_trait_ref: &chalk_ir::SeparatorTraitRef<Self>,
-        _fmt: &mut fmt::Formatter<'_>,
+        separator_trait_ref: &chalk_ir::SeparatorTraitRef<Interner>,
+        fmt: &mut fmt::Formatter<'_>,
     ) -> Option<fmt::Result> {
-        None
+        tls::with_current_program(|prog| {
+            Some(prog?.debug_separator_trait_ref(separator_trait_ref, fmt))
+        })
     }
 
     fn intern_ty(&self, ty: chalk_ir::TyData<Self>) -> Box<chalk_ir::TyData<Self>> {
@@ -650,19 +647,22 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
         debug!("impls_for_trait {:?}", trait_id);
         let trait_: hir_def::TraitId = from_chalk(self.db, trait_id);
 
+        let ty: Ty = from_chalk(self.db, parameters[0].assert_ty_ref(&Interner).clone());
+
+        let self_ty_fp = TyFingerprint::for_impl(&ty);
+
         // Note: Since we're using impls_for_trait, only impls where the trait
         // can be resolved should ever reach Chalk. `impl_datum` relies on that
         // and will panic if the trait can't be resolved.
         let mut result: Vec<_> = self
             .db
-            .impls_for_trait(self.krate, trait_)
+            .impls_for_trait(self.krate, trait_, self_ty_fp)
             .iter()
             .copied()
             .map(Impl::ImplDef)
             .map(|impl_| impl_.to_chalk(self.db))
             .collect();
 
-        let ty: Ty = from_chalk(self.db, parameters[0].assert_ty_ref(&Interner).clone());
         let arg: Option<Ty> =
             parameters.get(1).map(|p| from_chalk(self.db, p.assert_ty_ref(&Interner).clone()));
 
diff --git a/crates/ra_hir_ty/src/traits/chalk/tls.rs b/crates/ra_hir_ty/src/traits/chalk/tls.rs
new file mode 100644
index 000000000..d9bbb54a5
--- /dev/null
+++ b/crates/ra_hir_ty/src/traits/chalk/tls.rs
@@ -0,0 +1,231 @@
+//! Implementation of Chalk debug helper functions using TLS.
+use std::fmt;
+
+use chalk_ir::{AliasTy, Goal, Goals, Lifetime, Parameter, ProgramClauseImplication, TypeName};
+
+use super::{from_chalk, Interner};
+use crate::{db::HirDatabase, CallableDef, TypeCtor};
+use hir_def::{AdtId, AssocContainerId, Lookup, TypeAliasId};
+
+pub use unsafe_tls::{set_current_program, with_current_program};
+
+pub struct DebugContext<'a>(&'a (dyn HirDatabase + 'a));
+
+impl DebugContext<'_> {
+    pub fn debug_struct_id(
+        &self,
+        id: super::StructId,
+        f: &mut fmt::Formatter<'_>,
+    ) -> Result<(), fmt::Error> {
+        let type_ctor: TypeCtor = from_chalk(self.0, TypeName::Struct(id));
+        match type_ctor {
+            TypeCtor::Bool => write!(f, "bool")?,
+            TypeCtor::Char => write!(f, "char")?,
+            TypeCtor::Int(t) => write!(f, "{}", t)?,
+            TypeCtor::Float(t) => write!(f, "{}", t)?,
+            TypeCtor::Str => write!(f, "str")?,
+            TypeCtor::Slice => write!(f, "slice")?,
+            TypeCtor::Array => write!(f, "array")?,
+            TypeCtor::RawPtr(m) => write!(f, "*{}", m.as_keyword_for_ptr())?,
+            TypeCtor::Ref(m) => write!(f, "&{}", m.as_keyword_for_ref())?,
+            TypeCtor::Never => write!(f, "!")?,
+            TypeCtor::Tuple { .. } => {
+                write!(f, "()")?;
+            }
+            TypeCtor::FnPtr { .. } => {
+                write!(f, "fn")?;
+            }
+            TypeCtor::FnDef(def) => {
+                let name = match def {
+                    CallableDef::FunctionId(ff) => self.0.function_data(ff).name.clone(),
+                    CallableDef::StructId(s) => self.0.struct_data(s).name.clone(),
+                    CallableDef::EnumVariantId(e) => {
+                        let enum_data = self.0.enum_data(e.parent);
+                        enum_data.variants[e.local_id].name.clone()
+                    }
+                };
+                match def {
+                    CallableDef::FunctionId(_) => write!(f, "{{fn {}}}", name)?,
+                    CallableDef::StructId(_) | CallableDef::EnumVariantId(_) => {
+                        write!(f, "{{ctor {}}}", name)?
+                    }
+                }
+            }
+            TypeCtor::Adt(def_id) => {
+                let name = match def_id {
+                    AdtId::StructId(it) => self.0.struct_data(it).name.clone(),
+                    AdtId::UnionId(it) => self.0.union_data(it).name.clone(),
+                    AdtId::EnumId(it) => self.0.enum_data(it).name.clone(),
+                };
+                write!(f, "{}", name)?;
+            }
+            TypeCtor::AssociatedType(type_alias) => {
+                let trait_ = match type_alias.lookup(self.0.upcast()).container {
+                    AssocContainerId::TraitId(it) => it,
+                    _ => panic!("not an associated type"),
+                };
+                let trait_name = self.0.trait_data(trait_).name.clone();
+                let name = self.0.type_alias_data(type_alias).name.clone();
+                write!(f, "{}::{}", trait_name, name)?;
+            }
+            TypeCtor::Closure { def, expr } => {
+                write!(f, "{{closure {:?} in {:?}}}", expr.into_raw(), def)?;
+            }
+        }
+        Ok(())
+    }
+
+    pub fn debug_trait_id(
+        &self,
+        id: super::TraitId,
+        fmt: &mut fmt::Formatter<'_>,
+    ) -> Result<(), fmt::Error> {
+        let trait_: hir_def::TraitId = from_chalk(self.0, id);
+        let trait_data = self.0.trait_data(trait_);
+        write!(fmt, "{}", trait_data.name)
+    }
+
+    pub fn debug_assoc_type_id(
+        &self,
+        id: super::AssocTypeId,
+        fmt: &mut fmt::Formatter<'_>,
+    ) -> Result<(), fmt::Error> {
+        let type_alias: TypeAliasId = from_chalk(self.0, id);
+        let type_alias_data = self.0.type_alias_data(type_alias);
+        let trait_ = match type_alias.lookup(self.0.upcast()).container {
+            AssocContainerId::TraitId(t) => t,
+            _ => panic!("associated type not in trait"),
+        };
+        let trait_data = self.0.trait_data(trait_);
+        write!(fmt, "{}::{}", trait_data.name, type_alias_data.name)
+    }
+
+    pub fn debug_alias(
+        &self,
+        alias: &AliasTy<Interner>,
+        fmt: &mut fmt::Formatter<'_>,
+    ) -> Result<(), fmt::Error> {
+        let type_alias: TypeAliasId = from_chalk(self.0, alias.associated_ty_id);
+        let type_alias_data = self.0.type_alias_data(type_alias);
+        let trait_ = match type_alias.lookup(self.0.upcast()).container {
+            AssocContainerId::TraitId(t) => t,
+            _ => panic!("associated type not in trait"),
+        };
+        let trait_data = self.0.trait_data(trait_);
+        let params = alias.substitution.parameters(&Interner);
+        write!(
+            fmt,
+            "<{:?} as {}<{:?}>>::{}",
+            &params[0],
+            trait_data.name,
+            &params[1..],
+            type_alias_data.name
+        )
+    }
+
+    pub fn debug_ty(
+        &self,
+        ty: &chalk_ir::Ty<Interner>,
+        fmt: &mut fmt::Formatter<'_>,
+    ) -> Result<(), fmt::Error> {
+        write!(fmt, "{:?}", ty.data(&Interner))
+    }
+
+    pub fn debug_lifetime(
+        &self,
+        lifetime: &Lifetime<Interner>,
+        fmt: &mut fmt::Formatter<'_>,
+    ) -> Result<(), fmt::Error> {
+        write!(fmt, "{:?}", lifetime.data(&Interner))
+    }
+
+    pub fn debug_parameter(
+        &self,
+        parameter: &Parameter<Interner>,
+        fmt: &mut fmt::Formatter<'_>,
+    ) -> Result<(), fmt::Error> {
+        write!(fmt, "{:?}", parameter.data(&Interner).inner_debug())
+    }
+
+    pub fn debug_goal(
+        &self,
+        goal: &Goal<Interner>,
+        fmt: &mut fmt::Formatter<'_>,
+    ) -> Result<(), fmt::Error> {
+        let goal_data = goal.data(&Interner);
+        write!(fmt, "{:?}", goal_data)
+    }
+
+    pub fn debug_goals(
+        &self,
+        goals: &Goals<Interner>,
+        fmt: &mut fmt::Formatter<'_>,
+    ) -> Result<(), fmt::Error> {
+        write!(fmt, "{:?}", goals.debug(&Interner))
+    }
+
+    pub fn debug_program_clause_implication(
+        &self,
+        pci: &ProgramClauseImplication<Interner>,
+        fmt: &mut fmt::Formatter<'_>,
+    ) -> Result<(), fmt::Error> {
+        write!(fmt, "{:?}", pci.debug(&Interner))
+    }
+
+    pub fn debug_application_ty(
+        &self,
+        application_ty: &chalk_ir::ApplicationTy<Interner>,
+        fmt: &mut fmt::Formatter<'_>,
+    ) -> Result<(), fmt::Error> {
+        write!(fmt, "{:?}", application_ty.debug(&Interner))
+    }
+
+    pub fn debug_substitution(
+        &self,
+        substitution: &chalk_ir::Substitution<Interner>,
+        fmt: &mut fmt::Formatter<'_>,
+    ) -> Result<(), fmt::Error> {
+        write!(fmt, "{:?}", substitution.debug(&Interner))
+    }
+
+    pub fn debug_separator_trait_ref(
+        &self,
+        separator_trait_ref: &chalk_ir::SeparatorTraitRef<Interner>,
+        fmt: &mut fmt::Formatter<'_>,
+    ) -> Result<(), fmt::Error> {
+        write!(fmt, "{:?}", separator_trait_ref.debug(&Interner))
+    }
+}
+
+mod unsafe_tls {
+    use super::DebugContext;
+    use crate::db::HirDatabase;
+    use scoped_tls::scoped_thread_local;
+
+    scoped_thread_local!(static PROGRAM: DebugContext);
+
+    pub fn with_current_program<R>(
+        op: impl for<'a> FnOnce(Option<&'a DebugContext<'a>>) -> R,
+    ) -> R {
+        if PROGRAM.is_set() {
+            PROGRAM.with(|prog| op(Some(prog)))
+        } else {
+            op(None)
+        }
+    }
+
+    pub fn set_current_program<OP, R>(p: &dyn HirDatabase, op: OP) -> R
+    where
+        OP: FnOnce() -> R,
+    {
+        let ctx = DebugContext(p);
+        // we're transmuting the lifetime in the DebugContext to static. This is
+        // fine because we only keep the reference for the lifetime of this
+        // function, *and* the only way to access the context is through
+        // `with_current_program`, which hides the lifetime through the `for`
+        // type.
+        let static_p: &DebugContext<'static> =
+            unsafe { std::mem::transmute::<&DebugContext, &DebugContext<'static>>(&ctx) };
+        PROGRAM.set(static_p, || op())
+    }
+}