From 6f946f96563bac1f214f86f463287d94968e3688 Mon Sep 17 00:00:00 2001
From: Florian Diebold <flodiebold@gmail.com>
Date: Sun, 12 May 2019 17:53:33 +0200
Subject: Add test for Deref

---
 crates/ra_hir/src/ty/tests.rs | 29 +++++++++++++++++++++++++++++
 1 file changed, 29 insertions(+)

(limited to 'crates/ra_hir/src')

diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index 54b2a8c16..e587dca31 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -2737,6 +2737,35 @@ fn main() {
     assert_eq!(t, "Foo");
 }
 
+#[test]
+fn deref_trait() {
+    let t = type_at(
+        r#"
+//- /main.rs
+#[lang = "deref"]
+trait Deref {
+    type Target;
+    fn deref(&self) -> &Self::Target;
+}
+
+struct Arc<T>;
+impl<T> Deref for Arc<T> {
+    type Target = T;
+}
+
+struct S;
+impl S {
+    fn foo(&self) -> u128 {}
+}
+
+fn test(s: Arc<S>) {
+    (*s, s.foo())<|>
+}
+"#,
+    );
+    assert_eq!(t, "(S, u128)");
+}
+
 fn type_at_pos(db: &MockDatabase, pos: FilePosition) -> String {
     let file = db.parse(pos.file_id).ok().unwrap();
     let expr = algo::find_node_at_offset::<ast::Expr>(file.syntax(), pos.offset).unwrap();
-- 
cgit v1.2.3


From 49489dc20cc9f340d43acb467677b9bc59495ed2 Mon Sep 17 00:00:00 2001
From: Florian Diebold <flodiebold@gmail.com>
Date: Sun, 12 May 2019 17:53:44 +0200
Subject: Add basic infrastructure for assoc type projection

---
 crates/ra_hir/src/code_model.rs      |  21 ++++++-
 crates/ra_hir/src/db.rs              |  14 +++--
 crates/ra_hir/src/ty.rs              |  11 +++-
 crates/ra_hir/src/ty/lower.rs        |   2 +-
 crates/ra_hir/src/ty/traits.rs       |  33 ++++++++++-
 crates/ra_hir/src/ty/traits/chalk.rs | 110 ++++++++++++++++++++++++++++++++---
 crates/ra_hir/src/type_alias.rs      |  18 ++++--
 7 files changed, 188 insertions(+), 21 deletions(-)

(limited to 'crates/ra_hir/src')

diff --git a/crates/ra_hir/src/code_model.rs b/crates/ra_hir/src/code_model.rs
index 830aea1f3..4fbb1fc8f 100644
--- a/crates/ra_hir/src/code_model.rs
+++ b/crates/ra_hir/src/code_model.rs
@@ -779,6 +779,19 @@ impl Trait {
         self.trait_data(db).items().to_vec()
     }
 
+    pub fn associated_type_by_name(self, db: &impl DefDatabase, name: Name) -> Option<TypeAlias> {
+        let trait_data = self.trait_data(db);
+        trait_data
+            .items()
+            .iter()
+            .filter_map(|item| match item {
+                TraitItem::TypeAlias(t) => Some(*t),
+                _ => None,
+            })
+            .filter(|t| t.name(db) == name)
+            .next()
+    }
+
     pub(crate) fn trait_data(self, db: &impl DefDatabase) -> Arc<TraitData> {
         db.trait_data(self)
     }
@@ -831,8 +844,12 @@ impl TypeAlias {
         }
     }
 
-    pub fn type_ref(self, db: &impl DefDatabase) -> Arc<TypeRef> {
-        db.type_alias_ref(self)
+    pub fn type_ref(self, db: &impl DefDatabase) -> Option<TypeRef> {
+        db.type_alias_data(self).type_ref.clone()
+    }
+
+    pub fn name(self, db: &impl DefDatabase) -> Name {
+        db.type_alias_data(self).name.clone()
     }
 
     /// Builds a resolver for the type references in this type alias.
diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs
index d2d6f95b7..651f0d4ca 100644
--- a/crates/ra_hir/src/db.rs
+++ b/crates/ra_hir/src/db.rs
@@ -16,9 +16,8 @@ use crate::{
     adt::{StructData, EnumData},
     impl_block::{ModuleImplBlocks, ImplSourceMap, ImplBlock},
     generics::{GenericParams, GenericDef},
-    type_ref::TypeRef,
     traits::TraitData,
-    lang_item::{LangItems, LangItemTarget},
+    lang_item::{LangItems, LangItemTarget}, type_alias::TypeAliasData,
 };
 
 // This database has access to source code, so queries here are not really
@@ -113,8 +112,8 @@ pub trait DefDatabase: SourceDatabase {
     #[salsa::invoke(crate::FnSignature::fn_signature_query)]
     fn fn_signature(&self, func: Function) -> Arc<FnSignature>;
 
-    #[salsa::invoke(crate::type_alias::type_alias_ref_query)]
-    fn type_alias_ref(&self, typ: TypeAlias) -> Arc<TypeRef>;
+    #[salsa::invoke(crate::type_alias::type_alias_data_query)]
+    fn type_alias_data(&self, typ: TypeAlias) -> Arc<TypeAliasData>;
 
     #[salsa::invoke(crate::ConstSignature::const_signature_query)]
     fn const_signature(&self, konst: Const) -> Arc<ConstSignature>;
@@ -185,6 +184,13 @@ pub trait HirDatabase: DefDatabase + AstDatabase {
         krate: Crate,
         goal: crate::ty::Canonical<crate::ty::TraitRef>,
     ) -> Option<crate::ty::traits::Solution>;
+
+    #[salsa::invoke(crate::ty::traits::normalize)]
+    fn normalize(
+        &self,
+        krate: Crate,
+        goal: crate::ty::Canonical<crate::ty::traits::ProjectionPredicate>,
+    ) -> Option<crate::ty::traits::Solution>;
 }
 
 #[test]
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index 4a37e0268..d9a50b230 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -16,7 +16,7 @@ use std::sync::Arc;
 use std::ops::Deref;
 use std::{fmt, mem};
 
-use crate::{Name, AdtDef, type_ref::Mutability, db::HirDatabase, Trait, GenericParams};
+use crate::{Name, AdtDef, type_ref::Mutability, db::HirDatabase, Trait, GenericParams, TypeAlias};
 use display::{HirDisplay, HirFormatter};
 
 pub(crate) use lower::{TypableDef, type_for_def, type_for_field, callable_item_sig, generic_predicates, generic_defaults};
@@ -100,6 +100,15 @@ pub struct ApplicationTy {
     pub parameters: Substs,
 }
 
+/// A "projection" type corresponds to an (unnormalized)
+/// projection like `<P0 as Trait<P1..Pn>>::Foo`. Note that the
+/// trait and all its parameters are fully known.
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
+pub struct ProjectionTy {
+    pub associated_ty: TypeAlias,
+    pub parameters: Substs,
+}
+
 /// A type.
 ///
 /// See also the `TyKind` enum in rustc (librustc/ty/sty.rs), which represents
diff --git a/crates/ra_hir/src/ty/lower.rs b/crates/ra_hir/src/ty/lower.rs
index 26c213a41..300616a53 100644
--- a/crates/ra_hir/src/ty/lower.rs
+++ b/crates/ra_hir/src/ty/lower.rs
@@ -460,7 +460,7 @@ fn type_for_type_alias(db: &impl HirDatabase, t: TypeAlias) -> Ty {
     let resolver = t.resolver(db);
     let type_ref = t.type_ref(db);
     let substs = Substs::identity(&generics);
-    let inner = Ty::from_hir(db, &resolver, &type_ref);
+    let inner = Ty::from_hir(db, &resolver, &type_ref.unwrap_or(TypeRef::Error));
     inner.subst(&substs)
 }
 
diff --git a/crates/ra_hir/src/ty/traits.rs b/crates/ra_hir/src/ty/traits.rs
index fda7f9c04..f3e488403 100644
--- a/crates/ra_hir/src/ty/traits.rs
+++ b/crates/ra_hir/src/ty/traits.rs
@@ -8,7 +8,7 @@ use chalk_ir::cast::Cast;
 use ra_prof::profile;
 
 use crate::{Crate, Trait, db::HirDatabase, ImplBlock};
-use super::{TraitRef, Ty, Canonical};
+use super::{TraitRef, Ty, Canonical, ProjectionTy};
 
 use self::chalk::{ToChalk, from_chalk};
 
@@ -75,6 +75,13 @@ pub enum Obligation {
     /// Prove that a certain type implements a trait (the type is the `Self` type
     /// parameter to the `TraitRef`).
     Trait(TraitRef),
+    // Projection(ProjectionPredicate),
+}
+
+#[derive(Clone, Debug, PartialEq, Eq, Hash)]
+pub struct ProjectionPredicate {
+    projection_ty: ProjectionTy,
+    ty: Ty,
 }
 
 /// Check using Chalk whether trait is implemented for given parameters including `Self` type.
@@ -98,6 +105,30 @@ pub(crate) fn implements_query(
     solution.map(|solution| solution_from_chalk(db, solution))
 }
 
+pub(crate) fn normalize(
+    db: &impl HirDatabase,
+    krate: Crate,
+    projection: Canonical<ProjectionPredicate>,
+) -> Option<Solution> {
+    let goal: chalk_ir::Goal = chalk_ir::Normalize {
+        projection: projection.value.projection_ty.to_chalk(db),
+        ty: projection.value.ty.to_chalk(db),
+    }
+    .cast();
+    debug!("goal: {:?}", goal);
+    // FIXME unify with `implements`
+    let env = chalk_ir::Environment::new();
+    let in_env = chalk_ir::InEnvironment::new(&env, goal);
+    let parameter = chalk_ir::ParameterKind::Ty(chalk_ir::UniverseIndex::ROOT);
+    let canonical =
+        chalk_ir::Canonical { value: in_env, binders: vec![parameter; projection.num_vars] };
+    // We currently don't deal with universes (I think / hope they're not yet
+    // relevant for our use cases?)
+    let u_canonical = chalk_ir::UCanonical { canonical, universes: 1 };
+    let solution = solve(db, krate, &u_canonical);
+    solution.map(|solution| solution_from_chalk(db, solution))
+}
+
 fn solution_from_chalk(db: &impl HirDatabase, solution: chalk_solve::Solution) -> Solution {
     let convert_subst = |subst: chalk_ir::Canonical<chalk_ir::Substitution>| {
         let value = subst
diff --git a/crates/ra_hir/src/ty/traits/chalk.rs b/crates/ra_hir/src/ty/traits/chalk.rs
index 1e4806db0..1e1b6f406 100644
--- a/crates/ra_hir/src/ty/traits/chalk.rs
+++ b/crates/ra_hir/src/ty/traits/chalk.rs
@@ -3,7 +3,7 @@ use std::sync::Arc;
 
 use log::debug;
 
-use chalk_ir::{TypeId, ImplId, TypeKindId, ProjectionTy, Parameter, Identifier, cast::Cast, PlaceholderIndex, UniverseIndex, TypeName};
+use chalk_ir::{TypeId, ImplId, TypeKindId, Parameter, Identifier, cast::Cast, PlaceholderIndex, UniverseIndex, TypeName};
 use chalk_rust_ir::{AssociatedTyDatum, TraitDatum, StructDatum, ImplDatum};
 
 use test_utils::tested_by;
@@ -12,9 +12,9 @@ use ra_db::salsa::{InternId, InternKey};
 use crate::{
     Trait, HasGenericParams, ImplBlock,
     db::HirDatabase,
-    ty::{TraitRef, Ty, ApplicationTy, TypeCtor, Substs, GenericPredicate, CallableDef},
+    ty::{TraitRef, Ty, ApplicationTy, TypeCtor, Substs, GenericPredicate, CallableDef, ProjectionTy},
     ty::display::HirDisplay,
-    generics::GenericDef,
+    generics::GenericDef, TypeAlias, ImplItem,
 };
 use super::ChalkContext;
 
@@ -156,6 +156,18 @@ impl ToChalk for ImplBlock {
     }
 }
 
+impl ToChalk for TypeAlias {
+    type Chalk = chalk_ir::TypeId;
+
+    fn to_chalk(self, _db: &impl HirDatabase) -> chalk_ir::TypeId {
+        self.id.into()
+    }
+
+    fn from_chalk(_db: &impl HirDatabase, impl_id: chalk_ir::TypeId) -> TypeAlias {
+        TypeAlias { id: impl_id.into() }
+    }
+}
+
 impl ToChalk for GenericPredicate {
     type Chalk = chalk_ir::QuantifiedWhereClause;
 
@@ -183,6 +195,24 @@ impl ToChalk for GenericPredicate {
     }
 }
 
+impl ToChalk for ProjectionTy {
+    type Chalk = chalk_ir::ProjectionTy;
+
+    fn to_chalk(self, db: &impl HirDatabase) -> chalk_ir::ProjectionTy {
+        chalk_ir::ProjectionTy {
+            associated_ty_id: self.associated_ty.to_chalk(db),
+            parameters: self.parameters.to_chalk(db),
+        }
+    }
+
+    fn from_chalk(db: &impl HirDatabase, projection_ty: chalk_ir::ProjectionTy) -> ProjectionTy {
+        ProjectionTy {
+            associated_ty: from_chalk(db, projection_ty.associated_ty_id),
+            parameters: from_chalk(db, projection_ty.parameters),
+        }
+    }
+}
+
 fn make_binders<T>(value: T, num_vars: usize) -> chalk_ir::Binders<T> {
     chalk_ir::Binders {
         value,
@@ -225,8 +255,28 @@ impl<'a, DB> chalk_solve::RustIrDatabase for ChalkContext<'a, DB>
 where
     DB: HirDatabase,
 {
-    fn associated_ty_data(&self, _ty: TypeId) -> Arc<AssociatedTyDatum> {
-        unimplemented!()
+    fn associated_ty_data(&self, id: TypeId) -> Arc<AssociatedTyDatum> {
+        debug!("associated_ty_data {:?}", id);
+        let type_alias: TypeAlias = from_chalk(self.db, id);
+        let trait_ = match type_alias.container(self.db) {
+            Some(crate::Container::Trait(t)) => t,
+            _ => panic!("associated type not in trait"),
+        };
+        let generic_params = type_alias.generic_params(self.db);
+        let parameter_kinds = generic_params
+            .params_including_parent()
+            .into_iter()
+            .map(|p| chalk_ir::ParameterKind::Ty(lalrpop_intern::intern(&p.name.to_string())))
+            .collect();
+        let datum = AssociatedTyDatum {
+            trait_id: trait_.to_chalk(self.db),
+            id,
+            name: lalrpop_intern::intern(&type_alias.name(self.db).to_string()),
+            parameter_kinds,
+            bounds: vec![],        // FIXME
+            where_clauses: vec![], // FIXME
+        };
+        Arc::new(datum)
     }
     fn trait_datum(&self, trait_id: chalk_ir::TraitId) -> Arc<TraitDatum> {
         debug!("trait_datum {:?}", trait_id);
@@ -260,7 +310,15 @@ where
             fundamental: false,
         };
         let where_clauses = convert_where_clauses(self.db, trait_.into(), &bound_vars);
-        let associated_ty_ids = Vec::new(); // FIXME add associated tys
+        let associated_ty_ids = trait_
+            .items(self.db)
+            .into_iter()
+            .filter_map(|trait_item| match trait_item {
+                crate::traits::TraitItem::TypeAlias(type_alias) => Some(type_alias),
+                _ => None,
+            })
+            .map(|type_alias| type_alias.to_chalk(self.db))
+            .collect();
         let trait_datum_bound =
             chalk_rust_ir::TraitDatumBound { trait_ref, where_clauses, flags, associated_ty_ids };
         let trait_datum = TraitDatum { binders: make_binders(trait_datum_bound, bound_vars.len()) };
@@ -359,7 +417,30 @@ where
             trait_ref.display(self.db),
             where_clauses
         );
+        let trait_ = trait_ref.trait_;
         let trait_ref = trait_ref.to_chalk(self.db);
+        let associated_ty_values = impl_block
+            .items(self.db)
+            .into_iter()
+            .filter_map(|item| match item {
+                ImplItem::TypeAlias(t) => Some(t),
+                _ => None,
+            })
+            .filter_map(|t| {
+                let assoc_ty = trait_.associated_type_by_name(self.db, t.name(self.db))?;
+                let ty = self.db.type_for_def(t.into(), crate::Namespace::Types).subst(&bound_vars);
+                debug!("ty = {}", ty.display(self.db));
+                Some(chalk_rust_ir::AssociatedTyValue {
+                    impl_id,
+                    associated_ty_id: assoc_ty.to_chalk(self.db),
+                    value: chalk_ir::Binders {
+                        value: chalk_rust_ir::AssociatedTyValueBound { ty: ty.to_chalk(self.db) },
+                        binders: vec![], // FIXME add generic params (generic associated types)
+                    },
+                })
+            })
+            .collect();
+
         let impl_datum_bound = chalk_rust_ir::ImplDatumBound {
             trait_ref: if negative {
                 chalk_rust_ir::PolarizedTraitRef::Negative(trait_ref)
@@ -367,9 +448,10 @@ where
                 chalk_rust_ir::PolarizedTraitRef::Positive(trait_ref)
             },
             where_clauses,
-            associated_ty_values: Vec::new(), // FIXME add associated type values
+            associated_ty_values,
             impl_type,
         };
+        debug!("impl_datum: {:?}", impl_datum_bound);
         let impl_datum = ImplDatum { binders: make_binders(impl_datum_bound, bound_vars.len()) };
         Arc::new(impl_datum)
     }
@@ -405,7 +487,7 @@ where
     }
     fn split_projection<'p>(
         &self,
-        projection: &'p ProjectionTy,
+        projection: &'p chalk_ir::ProjectionTy,
     ) -> (Arc<AssociatedTyDatum>, &'p [Parameter], &'p [Parameter]) {
         debug!("split_projection {:?}", projection);
         unimplemented!()
@@ -440,6 +522,18 @@ impl From<crate::ids::TraitId> for chalk_ir::TraitId {
     }
 }
 
+impl From<chalk_ir::TypeId> for crate::ids::TypeAliasId {
+    fn from(type_id: chalk_ir::TypeId) -> Self {
+        id_from_chalk(type_id.0)
+    }
+}
+
+impl From<crate::ids::TypeAliasId> for chalk_ir::TypeId {
+    fn from(type_id: crate::ids::TypeAliasId) -> Self {
+        chalk_ir::TypeId(id_to_chalk(type_id))
+    }
+}
+
 impl From<chalk_ir::StructId> for crate::ids::TypeCtorId {
     fn from(struct_id: chalk_ir::StructId) -> Self {
         id_from_chalk(struct_id.0)
diff --git a/crates/ra_hir/src/type_alias.rs b/crates/ra_hir/src/type_alias.rs
index 87b9caa8a..eada37274 100644
--- a/crates/ra_hir/src/type_alias.rs
+++ b/crates/ra_hir/src/type_alias.rs
@@ -2,12 +2,22 @@
 
 use std::sync::Arc;
 
-use crate::{TypeAlias, DefDatabase, AstDatabase, HasSource, type_ref::TypeRef};
+use ra_syntax::ast::NameOwner;
 
-pub(crate) fn type_alias_ref_query(
+use crate::{TypeAlias, db::{DefDatabase, AstDatabase}, type_ref::TypeRef, name::{Name, AsName}, HasSource};
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct TypeAliasData {
+    pub(crate) name: Name,
+    pub(crate) type_ref: Option<TypeRef>,
+}
+
+pub(crate) fn type_alias_data_query(
     db: &(impl DefDatabase + AstDatabase),
     typ: TypeAlias,
-) -> Arc<TypeRef> {
+) -> Arc<TypeAliasData> {
     let node = typ.source(db).ast;
-    Arc::new(TypeRef::from_ast_opt(node.type_ref()))
+    let name = node.name().map_or_else(Name::missing, |n| n.as_name());
+    let type_ref = node.type_ref().map(TypeRef::from_ast);
+    Arc::new(TypeAliasData { name, type_ref })
 }
-- 
cgit v1.2.3


From 9c5e7dd849eff7bd6f20aa353feef083d089ff58 Mon Sep 17 00:00:00 2001
From: Florian Diebold <flodiebold@gmail.com>
Date: Sun, 12 May 2019 18:33:47 +0200
Subject: Implement autoderef using the Deref trait

 - add support for other lang item targets, since we need the Deref lang item
---
 crates/ra_hir/src/lang_item.rs            | 55 +++++++++++++++++++++----
 crates/ra_hir/src/name.rs                 |  5 +++
 crates/ra_hir/src/source_binder.rs        | 11 +++++
 crates/ra_hir/src/ty.rs                   |  5 ++-
 crates/ra_hir/src/ty/autoderef.rs         | 68 +++++++++++++++++++++++++++----
 crates/ra_hir/src/ty/infer.rs             | 40 +++++++++---------
 crates/ra_hir/src/ty/method_resolution.rs |  5 +--
 crates/ra_hir/src/ty/traits.rs            |  4 +-
 8 files changed, 149 insertions(+), 44 deletions(-)

(limited to 'crates/ra_hir/src')

diff --git a/crates/ra_hir/src/lang_item.rs b/crates/ra_hir/src/lang_item.rs
index cdc9182d6..ada8aeb5b 100644
--- a/crates/ra_hir/src/lang_item.rs
+++ b/crates/ra_hir/src/lang_item.rs
@@ -4,7 +4,7 @@ use rustc_hash::FxHashMap;
 use ra_syntax::{SmolStr, ast::AttrsOwner};
 
 use crate::{
-    Crate, DefDatabase, Enum, Function, HirDatabase, ImplBlock, Module, Static, Struct, Trait, AstDatabase,
+        Crate, DefDatabase, Enum, Function, HirDatabase, ImplBlock, Module, Static, Struct, Trait, ModuleDef, AstDatabase, HasSource
 };
 
 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
@@ -87,19 +87,48 @@ impl LangItems {
         let source = module.definition_source(db).ast;
         for (impl_id, _) in impl_blocks.impls.iter() {
             let impl_block = source_map.get(&source, impl_id);
-            let lang_item_name = impl_block
-                .attrs()
-                .filter_map(|a| a.as_key_value())
-                .filter(|(key, _)| key == "lang")
-                .map(|(_, val)| val)
-                .nth(0);
-            if let Some(lang_item_name) = lang_item_name {
+            if let Some(lang_item_name) = lang_item_name(&*impl_block) {
                 let imp = ImplBlock::from_id(*module, impl_id);
                 self.items.entry(lang_item_name).or_insert_with(|| LangItemTarget::ImplBlock(imp));
             }
         }
 
-        // FIXME we should look for the other lang item targets (traits, structs, ...)
+        // FIXME make this nicer
+        for def in module.declarations(db) {
+            match def {
+                ModuleDef::Trait(trait_) => {
+                    let node = trait_.source(db).ast;
+                    if let Some(lang_item_name) = lang_item_name(&*node) {
+                        self.items.entry(lang_item_name).or_insert(LangItemTarget::Trait(trait_));
+                    }
+                }
+                ModuleDef::Enum(e) => {
+                    let node = e.source(db).ast;
+                    if let Some(lang_item_name) = lang_item_name(&*node) {
+                        self.items.entry(lang_item_name).or_insert(LangItemTarget::Enum(e));
+                    }
+                }
+                ModuleDef::Struct(s) => {
+                    let node = s.source(db).ast;
+                    if let Some(lang_item_name) = lang_item_name(&*node) {
+                        self.items.entry(lang_item_name).or_insert(LangItemTarget::Struct(s));
+                    }
+                }
+                ModuleDef::Function(f) => {
+                    let node = f.source(db).ast;
+                    if let Some(lang_item_name) = lang_item_name(&*node) {
+                        self.items.entry(lang_item_name).or_insert(LangItemTarget::Function(f));
+                    }
+                }
+                ModuleDef::Static(s) => {
+                    let node = s.source(db).ast;
+                    if let Some(lang_item_name) = lang_item_name(&*node) {
+                        self.items.entry(lang_item_name).or_insert(LangItemTarget::Static(s));
+                    }
+                }
+                _ => {}
+            }
+        }
 
         // Look for lang items in the children
         for child in module.children(db) {
@@ -107,3 +136,11 @@ impl LangItems {
         }
     }
 }
+
+fn lang_item_name<T: AttrsOwner>(node: &T) -> Option<SmolStr> {
+    node.attrs()
+        .filter_map(|a| a.as_key_value())
+        .filter(|(key, _)| key == "lang")
+        .map(|(_, val)| val)
+        .nth(0)
+}
diff --git a/crates/ra_hir/src/name.rs b/crates/ra_hir/src/name.rs
index e9003e00b..ba17958eb 100644
--- a/crates/ra_hir/src/name.rs
+++ b/crates/ra_hir/src/name.rs
@@ -46,6 +46,11 @@ impl Name {
         Name::new(idx.to_string().into())
     }
 
+    // Needed for Deref
+    pub(crate) fn target() -> Name {
+        Name::new("Target".into())
+    }
+
     // There's should be no way to extract a string out of `Name`: `Name` in the
     // future, `Name` will include hygiene information, and you can't encode
     // hygiene into a String.
diff --git a/crates/ra_hir/src/source_binder.rs b/crates/ra_hir/src/source_binder.rs
index 4f9e8c5a9..08e86844d 100644
--- a/crates/ra_hir/src/source_binder.rs
+++ b/crates/ra_hir/src/source_binder.rs
@@ -369,6 +369,17 @@ impl SourceAnalyzer {
         )
     }
 
+    pub fn autoderef<'a>(
+        &'a self,
+        db: &'a impl HirDatabase,
+        ty: Ty,
+    ) -> impl Iterator<Item = Ty> + 'a {
+        // There should be no inference vars in types passed here
+        // FIXME check that?
+        let canonical = crate::ty::Canonical { value: ty, num_vars: 0 };
+        crate::ty::autoderef(db, &self.resolver, canonical).map(|canonical| canonical.value)
+    }
+
     #[cfg(test)]
     pub(crate) fn body_source_map(&self) -> Arc<BodySourceMap> {
         self.body_source_map.clone().unwrap()
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index d9a50b230..d2f92a1f2 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -22,6 +22,7 @@ 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_query, InferenceResult, InferTy};
 pub use lower::CallableDef;
+pub(crate) use autoderef::autoderef;
 
 /// A type constructor or type name: this might be something like the primitive
 /// type `bool`, a struct like `Vec`, or things like function pointers or
@@ -225,8 +226,8 @@ impl Deref for Substs {
 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 pub struct TraitRef {
     /// FIXME name?
-    trait_: Trait,
-    substs: Substs,
+    pub trait_: Trait,
+    pub substs: Substs,
 }
 
 impl TraitRef {
diff --git a/crates/ra_hir/src/ty/autoderef.rs b/crates/ra_hir/src/ty/autoderef.rs
index a442a856c..bee756d80 100644
--- a/crates/ra_hir/src/ty/autoderef.rs
+++ b/crates/ra_hir/src/ty/autoderef.rs
@@ -5,17 +5,67 @@
 
 use std::iter::successors;
 
-use crate::HirDatabase;
-use super::Ty;
+use log::info;
 
-impl Ty {
-    /// Iterates over the possible derefs of `ty`.
-    pub fn autoderef<'a>(self, db: &'a impl HirDatabase) -> impl Iterator<Item = Ty> + 'a {
-        successors(Some(self), move |ty| ty.autoderef_step(db))
+use crate::{HirDatabase, Name, Resolver};
+use super::{traits::Solution, Ty, Canonical};
+
+pub(crate) fn autoderef<'a>(
+    db: &'a impl HirDatabase,
+    resolver: &'a Resolver,
+    ty: Canonical<Ty>,
+) -> impl Iterator<Item = Canonical<Ty>> + 'a {
+    successors(Some(ty), move |ty| deref(db, resolver, ty))
+}
+
+pub(crate) fn deref(
+    db: &impl HirDatabase,
+    resolver: &Resolver,
+    ty: &Canonical<Ty>,
+) -> Option<Canonical<Ty>> {
+    if let Some(derefed) = ty.value.builtin_deref() {
+        Some(Canonical { value: derefed, num_vars: ty.num_vars })
+    } else {
+        deref_by_trait(db, resolver, ty)
     }
+}
+
+fn deref_by_trait(
+    db: &impl HirDatabase,
+    resolver: &Resolver,
+    ty: &Canonical<Ty>,
+) -> Option<Canonical<Ty>> {
+    let krate = resolver.krate()?;
+    let deref_trait = match db.lang_item(krate, "deref".into())? {
+        crate::lang_item::LangItemTarget::Trait(t) => t,
+        _ => return None,
+    };
+    let target = deref_trait.associated_type_by_name(db, Name::target())?;
+
+    // FIXME we should check that Deref has no type parameters, because we assume it below
+
+    // FIXME make the Canonical handling nicer
+    // TODO shift inference variables in ty
+
+    let projection = super::traits::ProjectionPredicate {
+        ty: Ty::Bound(0),
+        projection_ty: super::ProjectionTy {
+            associated_ty: target,
+            parameters: vec![ty.value.clone()].into(),
+        },
+    };
+
+    let canonical = super::Canonical { num_vars: 1 + ty.num_vars, value: projection };
+
+    let solution = db.normalize(krate, canonical)?;
 
-    fn autoderef_step(&self, _db: &impl HirDatabase) -> Option<Ty> {
-        // FIXME Deref::deref
-        self.builtin_deref()
+    match &solution {
+        Solution::Unique(vars) => {
+            Some(Canonical { value: vars.0.value[0].clone(), num_vars: vars.0.num_vars })
+        }
+        Solution::Ambig(_) => {
+            info!("Ambiguous solution for deref: {:?}", solution);
+            None
+        }
     }
 }
diff --git a/crates/ra_hir/src/ty/infer.rs b/crates/ra_hir/src/ty/infer.rs
index e150d7fd8..fdb444de2 100644
--- a/crates/ra_hir/src/ty/infer.rs
+++ b/crates/ra_hir/src/ty/infer.rs
@@ -46,7 +46,7 @@ use crate::{
 use super::{
     Ty, TypableDef, Substs, primitive, op, ApplicationTy, TypeCtor, CallableDef, TraitRef,
     traits::{Solution, Obligation, Guidance},
-    method_resolution,
+    method_resolution, autoderef,
 };
 
 mod unify;
@@ -1074,25 +1074,27 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
             }
             Expr::Field { expr, name } => {
                 let receiver_ty = self.infer_expr(*expr, &Expectation::none());
-                let ty = receiver_ty
-                    .autoderef(self.db)
-                    .find_map(|derefed_ty| match derefed_ty {
-                        Ty::Apply(a_ty) => match a_ty.ctor {
-                            TypeCtor::Tuple { .. } => {
-                                let i = name.to_string().parse::<usize>().ok();
-                                i.and_then(|i| a_ty.parameters.0.get(i).cloned())
-                            }
-                            TypeCtor::Adt(AdtDef::Struct(s)) => {
-                                s.field(self.db, name).map(|field| {
-                                    self.write_field_resolution(tgt_expr, field);
-                                    field.ty(self.db).subst(&a_ty.parameters)
-                                })
-                            }
-                            _ => None,
-                        },
+                let canonicalized = self.canonicalizer().canonicalize_ty(receiver_ty);
+                let ty = autoderef::autoderef(
+                    self.db,
+                    &self.resolver.clone(),
+                    canonicalized.value.clone(),
+                )
+                .find_map(|derefed_ty| match canonicalized.decanonicalize_ty(derefed_ty.value) {
+                    Ty::Apply(a_ty) => match a_ty.ctor {
+                        TypeCtor::Tuple { .. } => {
+                            let i = name.to_string().parse::<usize>().ok();
+                            i.and_then(|i| a_ty.parameters.0.get(i).cloned())
+                        }
+                        TypeCtor::Adt(AdtDef::Struct(s)) => s.field(self.db, name).map(|field| {
+                            self.write_field_resolution(tgt_expr, field);
+                            field.ty(self.db).subst(&a_ty.parameters)
+                        }),
                         _ => None,
-                    })
-                    .unwrap_or(Ty::Unknown);
+                    },
+                    _ => None,
+                })
+                .unwrap_or(Ty::Unknown);
                 self.insert_type_vars(ty)
             }
             Expr::Try { expr } => {
diff --git a/crates/ra_hir/src/ty/method_resolution.rs b/crates/ra_hir/src/ty/method_resolution.rs
index 646e58aa9..ad26d591c 100644
--- a/crates/ra_hir/src/ty/method_resolution.rs
+++ b/crates/ra_hir/src/ty/method_resolution.rs
@@ -16,7 +16,7 @@ use crate::{
     generics::HasGenericParams,
     ty::primitive::{UncertainIntTy, UncertainFloatTy}
 };
-use super::{TraitRef, Canonical};
+use super::{TraitRef, Canonical, autoderef};
 
 /// This is used as a key for indexing impls.
 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
@@ -162,8 +162,7 @@ pub(crate) fn iterate_method_candidates<T>(
     // rustc does an autoderef and then autoref again).
 
     let krate = resolver.krate()?;
-    for derefed_ty in ty.value.clone().autoderef(db) {
-        let derefed_ty = Canonical { value: derefed_ty, num_vars: ty.num_vars };
+    for derefed_ty in autoderef::autoderef(db, resolver, ty.clone()) {
         if let Some(result) = iterate_inherent_methods(&derefed_ty, db, name, krate, &mut callback)
         {
             return Some(result);
diff --git a/crates/ra_hir/src/ty/traits.rs b/crates/ra_hir/src/ty/traits.rs
index f3e488403..6cf3dd70a 100644
--- a/crates/ra_hir/src/ty/traits.rs
+++ b/crates/ra_hir/src/ty/traits.rs
@@ -80,8 +80,8 @@ pub enum Obligation {
 
 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
 pub struct ProjectionPredicate {
-    projection_ty: ProjectionTy,
-    ty: Ty,
+    pub projection_ty: ProjectionTy,
+    pub ty: Ty,
 }
 
 /// Check using Chalk whether trait is implemented for given parameters including `Self` type.
-- 
cgit v1.2.3


From ca5ed2307c6dd8396f58460652c77a6a63704e0b Mon Sep 17 00:00:00 2001
From: Florian Diebold <flodiebold@gmail.com>
Date: Wed, 12 Jun 2019 20:51:29 +0200
Subject: Implement * operation using Deref trait

---
 crates/ra_hir/src/ty/infer.rs | 8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)

(limited to 'crates/ra_hir/src')

diff --git a/crates/ra_hir/src/ty/infer.rs b/crates/ra_hir/src/ty/infer.rs
index fdb444de2..1ee40c70a 100644
--- a/crates/ra_hir/src/ty/infer.rs
+++ b/crates/ra_hir/src/ty/infer.rs
@@ -1126,10 +1126,12 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 let inner_ty = self.infer_expr(*expr, &Expectation::none());
                 match op {
                     UnaryOp::Deref => {
-                        if let Some(derefed_ty) = inner_ty.builtin_deref() {
-                            derefed_ty
+                        let canonicalized = self.canonicalizer().canonicalize_ty(inner_ty);
+                        if let Some(derefed_ty) =
+                            autoderef::deref(self.db, &self.resolver, &canonicalized.value)
+                        {
+                            canonicalized.decanonicalize_ty(derefed_ty.value)
                         } else {
-                            // FIXME Deref::deref
                             Ty::Unknown
                         }
                     }
-- 
cgit v1.2.3


From 3e78a6e3e0dbe5ad2ae712ec5c94a3792745f26c Mon Sep 17 00:00:00 2001
From: Florian Diebold <flodiebold@gmail.com>
Date: Sat, 15 Jun 2019 18:20:59 +0200
Subject: Somewhat handle variables in the derefed type, and add another test

---
 crates/ra_hir/src/ty.rs           | 11 +++++++++++
 crates/ra_hir/src/ty/autoderef.rs | 24 +++++++++++++++++++-----
 crates/ra_hir/src/ty/tests.rs     | 31 +++++++++++++++++++++++++++++++
 3 files changed, 61 insertions(+), 5 deletions(-)

(limited to 'crates/ra_hir/src')

diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index d2f92a1f2..4ed19f860 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -474,6 +474,17 @@ impl Ty {
             _ => None,
         }
     }
+
+    /// Shifts up `Ty::Bound` vars by `n`.
+    pub fn shift_bound_vars(self, n: i32) -> Ty {
+        self.fold(&mut |ty| match ty {
+            Ty::Bound(idx) => {
+                assert!(idx as i32 >= -n);
+                Ty::Bound((idx as i32 + n) as u32)
+            }
+            ty => ty,
+        })
+    }
 }
 
 impl HirDisplay for &Ty {
diff --git a/crates/ra_hir/src/ty/autoderef.rs b/crates/ra_hir/src/ty/autoderef.rs
index bee756d80..11f489489 100644
--- a/crates/ra_hir/src/ty/autoderef.rs
+++ b/crates/ra_hir/src/ty/autoderef.rs
@@ -5,7 +5,7 @@
 
 use std::iter::successors;
 
-use log::info;
+use log::{info, warn};
 
 use crate::{HirDatabase, Name, Resolver};
 use super::{traits::Solution, Ty, Canonical};
@@ -43,15 +43,13 @@ fn deref_by_trait(
     let target = deref_trait.associated_type_by_name(db, Name::target())?;
 
     // FIXME we should check that Deref has no type parameters, because we assume it below
-
     // FIXME make the Canonical handling nicer
-    // TODO shift inference variables in ty
 
     let projection = super::traits::ProjectionPredicate {
         ty: Ty::Bound(0),
         projection_ty: super::ProjectionTy {
             associated_ty: target,
-            parameters: vec![ty.value.clone()].into(),
+            parameters: vec![ty.value.clone().shift_bound_vars(1)].into(),
         },
     };
 
@@ -61,10 +59,26 @@ fn deref_by_trait(
 
     match &solution {
         Solution::Unique(vars) => {
+            // FIXME: vars may contain solutions for any inference variables
+            // that happened to be inside ty. To correctly handle these, we
+            // would have to pass the solution up to the inference context, but
+            // that requires a larger refactoring (especially if the deref
+            // happens during method resolution). So for the moment, we just
+            // check that we're not in the situation we're we would actually
+            // need to handle the values of the additional variables, i.e.
+            // they're just being 'passed through'. In the 'standard' case where
+            // we have `impl<T> Deref for Foo<T> { Target = T }`, that should be
+            // the case.
+            for i in 1..vars.0.num_vars {
+                if vars.0.value[i] != Ty::Bound((i - 1) as u32) {
+                    warn!("complex solution for derefing {:?}: {:?}, ignoring", ty, solution);
+                    return None;
+                }
+            }
             Some(Canonical { value: vars.0.value[0].clone(), num_vars: vars.0.num_vars })
         }
         Solution::Ambig(_) => {
-            info!("Ambiguous solution for deref: {:?}", solution);
+            info!("Ambiguous solution for derefing {:?}: {:?}", ty, solution);
             None
         }
     }
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index e587dca31..059a73900 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -2766,6 +2766,37 @@ fn test(s: Arc<S>) {
     assert_eq!(t, "(S, u128)");
 }
 
+#[test]
+fn deref_trait_with_inference_var() {
+    // std::env::set_var("RUST_BACKTRACE", "1");
+    let t = type_at(
+        r#"
+//- /main.rs
+#[lang = "deref"]
+trait Deref {
+    type Target;
+    fn deref(&self) -> &Self::Target;
+}
+
+struct Arc<T>;
+fn new_arc<T>() -> Arc<T> {}
+impl<T> Deref for Arc<T> {
+    type Target = T;
+}
+
+struct S;
+fn foo(a: Arc<S>) {}
+
+fn test() {
+    let a = new_arc();
+    let b = (*a)<|>;
+    foo(a);
+}
+"#,
+    );
+    assert_eq!(t, "S");
+}
+
 fn type_at_pos(db: &MockDatabase, pos: FilePosition) -> String {
     let file = db.parse(pos.file_id).ok().unwrap();
     let expr = algo::find_node_at_offset::<ast::Expr>(file.syntax(), pos.offset).unwrap();
-- 
cgit v1.2.3


From 94a6aff9f86de0b670670baf36b95bc881d87ccc Mon Sep 17 00:00:00 2001
From: Florian Diebold <flodiebold@gmail.com>
Date: Sat, 15 Jun 2019 18:33:30 +0200
Subject: Check that Deref has the right number of parameters

---
 crates/ra_hir/src/ty/autoderef.rs | 9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)

(limited to 'crates/ra_hir/src')

diff --git a/crates/ra_hir/src/ty/autoderef.rs b/crates/ra_hir/src/ty/autoderef.rs
index 11f489489..e85e558b2 100644
--- a/crates/ra_hir/src/ty/autoderef.rs
+++ b/crates/ra_hir/src/ty/autoderef.rs
@@ -7,7 +7,7 @@ use std::iter::successors;
 
 use log::{info, warn};
 
-use crate::{HirDatabase, Name, Resolver};
+use crate::{HirDatabase, Name, Resolver, HasGenericParams};
 use super::{traits::Solution, Ty, Canonical};
 
 pub(crate) fn autoderef<'a>(
@@ -42,7 +42,12 @@ fn deref_by_trait(
     };
     let target = deref_trait.associated_type_by_name(db, Name::target())?;
 
-    // FIXME we should check that Deref has no type parameters, because we assume it below
+    if target.generic_params(db).count_params_including_parent() != 1 {
+        // the Target type + Deref trait should only have one generic parameter,
+        // namely Deref's Self type
+        return None;
+    }
+
     // FIXME make the Canonical handling nicer
 
     let projection = super::traits::ProjectionPredicate {
-- 
cgit v1.2.3


From 30647cd195e29c77fd1248d49c750346ca5022ca Mon Sep 17 00:00:00 2001
From: Florian Diebold <flodiebold@gmail.com>
Date: Sat, 15 Jun 2019 18:36:58 +0200
Subject: Some more cleanup

---
 crates/ra_hir/src/ty/traits/chalk.rs | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

(limited to 'crates/ra_hir/src')

diff --git a/crates/ra_hir/src/ty/traits/chalk.rs b/crates/ra_hir/src/ty/traits/chalk.rs
index 1e1b6f406..5105588ee 100644
--- a/crates/ra_hir/src/ty/traits/chalk.rs
+++ b/crates/ra_hir/src/ty/traits/chalk.rs
@@ -273,8 +273,9 @@ where
             id,
             name: lalrpop_intern::intern(&type_alias.name(self.db).to_string()),
             parameter_kinds,
-            bounds: vec![],        // FIXME
-            where_clauses: vec![], // FIXME
+            // FIXME add bounds and where clauses
+            bounds: vec![],
+            where_clauses: vec![],
         };
         Arc::new(datum)
     }
@@ -429,13 +430,12 @@ where
             .filter_map(|t| {
                 let assoc_ty = trait_.associated_type_by_name(self.db, t.name(self.db))?;
                 let ty = self.db.type_for_def(t.into(), crate::Namespace::Types).subst(&bound_vars);
-                debug!("ty = {}", ty.display(self.db));
                 Some(chalk_rust_ir::AssociatedTyValue {
                     impl_id,
                     associated_ty_id: assoc_ty.to_chalk(self.db),
                     value: chalk_ir::Binders {
                         value: chalk_rust_ir::AssociatedTyValueBound { ty: ty.to_chalk(self.db) },
-                        binders: vec![], // FIXME add generic params (generic associated types)
+                        binders: vec![], // we don't support GATs yet
                     },
                 })
             })
-- 
cgit v1.2.3


From 96c2b9c41d85a8bd781e2b734cac1224eb7c4694 Mon Sep 17 00:00:00 2001
From: Florian Diebold <flodiebold@gmail.com>
Date: Sun, 16 Jun 2019 12:04:08 +0200
Subject: Simplifications / cleanup from review

---
 crates/ra_hir/src/code_model.rs   |  3 +--
 crates/ra_hir/src/db.rs           |  4 +--
 crates/ra_hir/src/lang_item.rs    | 54 +++++++++++++++++----------------------
 crates/ra_hir/src/ty.rs           |  1 +
 crates/ra_hir/src/ty/autoderef.rs |  4 ++-
 crates/ra_hir/src/ty/tests.rs     |  1 -
 crates/ra_hir/src/ty/traits.rs    |  2 +-
 7 files changed, 31 insertions(+), 38 deletions(-)

(limited to 'crates/ra_hir/src')

diff --git a/crates/ra_hir/src/code_model.rs b/crates/ra_hir/src/code_model.rs
index 4fbb1fc8f..6602d1220 100644
--- a/crates/ra_hir/src/code_model.rs
+++ b/crates/ra_hir/src/code_model.rs
@@ -788,8 +788,7 @@ impl Trait {
                 TraitItem::TypeAlias(t) => Some(*t),
                 _ => None,
             })
-            .filter(|t| t.name(db) == name)
-            .next()
+            .find(|t| t.name(db) == name)
     }
 
     pub(crate) fn trait_data(self, db: &impl DefDatabase) -> Arc<TraitData> {
diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs
index 651f0d4ca..c4dd54596 100644
--- a/crates/ra_hir/src/db.rs
+++ b/crates/ra_hir/src/db.rs
@@ -185,11 +185,11 @@ pub trait HirDatabase: DefDatabase + AstDatabase {
         goal: crate::ty::Canonical<crate::ty::TraitRef>,
     ) -> Option<crate::ty::traits::Solution>;
 
-    #[salsa::invoke(crate::ty::traits::normalize)]
+    #[salsa::invoke(crate::ty::traits::normalize_query)]
     fn normalize(
         &self,
         krate: Crate,
-        goal: crate::ty::Canonical<crate::ty::traits::ProjectionPredicate>,
+        goal: crate::ty::Canonical<crate::ty::ProjectionPredicate>,
     ) -> Option<crate::ty::traits::Solution>;
 }
 
diff --git a/crates/ra_hir/src/lang_item.rs b/crates/ra_hir/src/lang_item.rs
index ada8aeb5b..18ac0fcf9 100644
--- a/crates/ra_hir/src/lang_item.rs
+++ b/crates/ra_hir/src/lang_item.rs
@@ -1,10 +1,11 @@
 use std::sync::Arc;
 use rustc_hash::FxHashMap;
 
-use ra_syntax::{SmolStr, ast::AttrsOwner};
+use ra_syntax::{SmolStr, TreeArc, ast::AttrsOwner};
 
 use crate::{
-        Crate, DefDatabase, Enum, Function, HirDatabase, ImplBlock, Module, Static, Struct, Trait, ModuleDef, AstDatabase, HasSource
+    Crate, DefDatabase, Enum, Function, HirDatabase, ImplBlock, Module,
+    Static, Struct, Trait, ModuleDef, AstDatabase, HasSource
 };
 
 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
@@ -93,39 +94,15 @@ impl LangItems {
             }
         }
 
-        // FIXME make this nicer
         for def in module.declarations(db) {
             match def {
                 ModuleDef::Trait(trait_) => {
-                    let node = trait_.source(db).ast;
-                    if let Some(lang_item_name) = lang_item_name(&*node) {
-                        self.items.entry(lang_item_name).or_insert(LangItemTarget::Trait(trait_));
-                    }
-                }
-                ModuleDef::Enum(e) => {
-                    let node = e.source(db).ast;
-                    if let Some(lang_item_name) = lang_item_name(&*node) {
-                        self.items.entry(lang_item_name).or_insert(LangItemTarget::Enum(e));
-                    }
-                }
-                ModuleDef::Struct(s) => {
-                    let node = s.source(db).ast;
-                    if let Some(lang_item_name) = lang_item_name(&*node) {
-                        self.items.entry(lang_item_name).or_insert(LangItemTarget::Struct(s));
-                    }
-                }
-                ModuleDef::Function(f) => {
-                    let node = f.source(db).ast;
-                    if let Some(lang_item_name) = lang_item_name(&*node) {
-                        self.items.entry(lang_item_name).or_insert(LangItemTarget::Function(f));
-                    }
-                }
-                ModuleDef::Static(s) => {
-                    let node = s.source(db).ast;
-                    if let Some(lang_item_name) = lang_item_name(&*node) {
-                        self.items.entry(lang_item_name).or_insert(LangItemTarget::Static(s));
-                    }
+                    self.collect_lang_item(db, trait_, LangItemTarget::Trait)
                 }
+                ModuleDef::Enum(e) => self.collect_lang_item(db, e, LangItemTarget::Enum),
+                ModuleDef::Struct(s) => self.collect_lang_item(db, s, LangItemTarget::Struct),
+                ModuleDef::Function(f) => self.collect_lang_item(db, f, LangItemTarget::Function),
+                ModuleDef::Static(s) => self.collect_lang_item(db, s, LangItemTarget::Static),
                 _ => {}
             }
         }
@@ -135,6 +112,21 @@ impl LangItems {
             self.collect_lang_items_recursive(db, &child);
         }
     }
+
+    fn collect_lang_item<T, N>(
+        &mut self,
+        db: &(impl DefDatabase + AstDatabase),
+        item: T,
+        constructor: fn(T) -> LangItemTarget,
+    ) where
+        T: Copy + HasSource<Ast = TreeArc<N>>,
+        N: AttrsOwner,
+    {
+        let node = item.source(db).ast;
+        if let Some(lang_item_name) = lang_item_name(&*node) {
+            self.items.entry(lang_item_name).or_insert(constructor(item));
+        }
+    }
 }
 
 fn lang_item_name<T: AttrsOwner>(node: &T) -> Option<SmolStr> {
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index 4ed19f860..842d49e1f 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -23,6 +23,7 @@ pub(crate) use lower::{TypableDef, type_for_def, type_for_field, callable_item_s
 pub(crate) use infer::{infer_query, InferenceResult, InferTy};
 pub use lower::CallableDef;
 pub(crate) use autoderef::autoderef;
+pub(crate) use traits::ProjectionPredicate;
 
 /// A type constructor or type name: this might be something like the primitive
 /// type `bool`, a struct like `Vec`, or things like function pointers or
diff --git a/crates/ra_hir/src/ty/autoderef.rs b/crates/ra_hir/src/ty/autoderef.rs
index e85e558b2..1f443d49b 100644
--- a/crates/ra_hir/src/ty/autoderef.rs
+++ b/crates/ra_hir/src/ty/autoderef.rs
@@ -10,12 +10,14 @@ use log::{info, warn};
 use crate::{HirDatabase, Name, Resolver, HasGenericParams};
 use super::{traits::Solution, Ty, Canonical};
 
+const AUTODEREF_RECURSION_LIMIT: usize = 10;
+
 pub(crate) fn autoderef<'a>(
     db: &'a impl HirDatabase,
     resolver: &'a Resolver,
     ty: Canonical<Ty>,
 ) -> impl Iterator<Item = Canonical<Ty>> + 'a {
-    successors(Some(ty), move |ty| deref(db, resolver, ty))
+    successors(Some(ty), move |ty| deref(db, resolver, ty)).take(AUTODEREF_RECURSION_LIMIT)
 }
 
 pub(crate) fn deref(
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index 059a73900..7a101d981 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -2768,7 +2768,6 @@ fn test(s: Arc<S>) {
 
 #[test]
 fn deref_trait_with_inference_var() {
-    // std::env::set_var("RUST_BACKTRACE", "1");
     let t = type_at(
         r#"
 //- /main.rs
diff --git a/crates/ra_hir/src/ty/traits.rs b/crates/ra_hir/src/ty/traits.rs
index 6cf3dd70a..9a6349d4b 100644
--- a/crates/ra_hir/src/ty/traits.rs
+++ b/crates/ra_hir/src/ty/traits.rs
@@ -105,7 +105,7 @@ pub(crate) fn implements_query(
     solution.map(|solution| solution_from_chalk(db, solution))
 }
 
-pub(crate) fn normalize(
+pub(crate) fn normalize_query(
     db: &impl HirDatabase,
     krate: Crate,
     projection: Canonical<ProjectionPredicate>,
-- 
cgit v1.2.3


From ad3673d8d86a9b8f1a8dba858abd7cabaa1d5776 Mon Sep 17 00:00:00 2001
From: Florian Diebold <flodiebold@gmail.com>
Date: Sun, 16 Jun 2019 12:21:39 +0200
Subject: Add test for autoderef infinite recursion

---
 crates/ra_hir/src/ty/tests.rs | 25 +++++++++++++++++++++++++
 1 file changed, 25 insertions(+)

(limited to 'crates/ra_hir/src')

diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index 7a101d981..0fe7805e2 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -2796,6 +2796,31 @@ fn test() {
     assert_eq!(t, "S");
 }
 
+#[test]
+fn deref_trait_infinite_recursion() {
+    let t = type_at(
+        r#"
+//- /main.rs
+#[lang = "deref"]
+trait Deref {
+    type Target;
+    fn deref(&self) -> &Self::Target;
+}
+
+struct S;
+
+impl Deref for S {
+    type Target = S;
+}
+
+fn test(s: S) {
+    s.foo()<|>;
+}
+"#,
+    );
+    assert_eq!(t, "{unknown}");
+}
+
 fn type_at_pos(db: &MockDatabase, pos: FilePosition) -> String {
     let file = db.parse(pos.file_id).ok().unwrap();
     let expr = algo::find_node_at_offset::<ast::Expr>(file.syntax(), pos.offset).unwrap();
-- 
cgit v1.2.3