11 files changed, 102 insertions, 38 deletions

diff --git a/Cargo.lock b/Cargo.lock
index f93f11a82..7f7de3bf4 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -1007,6 +1007,7 @@ dependencies = [
  "chalk-solve 0.1.0 (git+https://github.com/rust-lang/chalk.git)",
  "ena 0.13.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "insta 0.11.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "itertools 0.8.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "lalrpop-intern 0.15.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "log 0.4.8 (registry+https://github.com/rust-lang/crates.io-index)",
  "once_cell 1.0.2 (registry+https://github.com/rust-lang/crates.io-index)",
diff --git a/crates/ra_hir/Cargo.toml b/crates/ra_hir/Cargo.toml
index d9bed4dda..e89b97daf 100644
--- a/crates/ra_hir/Cargo.toml
+++ b/crates/ra_hir/Cargo.toml
@@ -12,6 +12,7 @@ rustc-hash = "1.0"
 parking_lot = "0.9.0"
 ena = "0.13"
 once_cell = "1.0.1"
+itertools = "0.8.0"
 
 ra_syntax = { path = "../ra_syntax" }
 ra_arena = { path = "../ra_arena" }
diff --git a/crates/ra_hir/src/code_model.rs b/crates/ra_hir/src/code_model.rs
index f7efc1b66..4739246cb 100644
--- a/crates/ra_hir/src/code_model.rs
+++ b/crates/ra_hir/src/code_model.rs
@@ -1,8 +1,11 @@
 pub(crate) mod src;
 pub(crate) mod docs;
 
+use std::iter;
 use std::sync::Arc;
 
+use itertools::Itertools;
+
 use ra_db::{CrateId, Edition, FileId, SourceRootId};
 use ra_syntax::ast::{self, NameOwner, TypeAscriptionOwner};
 
@@ -820,7 +823,43 @@ impl Trait {
         self.trait_data(db).items().to_vec()
     }
 
-    pub fn associated_type_by_name(self, db: &impl DefDatabase, name: Name) -> Option<TypeAlias> {
+    fn direct_super_traits(self, db: &impl HirDatabase) -> Vec<Trait> {
+        let resolver = self.resolver(db);
+        // returning the iterator directly doesn't easily work because of
+        // lifetime problems, but since there usually shouldn't be more than a
+        // few direct traits this should be fine (we could even use some kind of
+        // SmallVec if performance is a concern)
+        self.generic_params(db)
+            .where_predicates
+            .iter()
+            .filter_map(|pred| match &pred.type_ref {
+                TypeRef::Path(p) if p.as_ident() == Some(&crate::name::SELF_TYPE) => {
+                    pred.bound.as_path()
+                }
+                _ => None,
+            })
+            .filter_map(|path| {
+                match resolver.resolve_path_without_assoc_items(db, path).take_types() {
+                    Some(crate::Resolution::Def(ModuleDef::Trait(t))) => Some(t),
+                    _ => None,
+                }
+            })
+            .collect()
+    }
+
+    /// Returns an iterator over the whole super trait hierarchy (not including
+    /// the trait itself). (This iterator may be infinite in case of circular
+    /// super trait dependencies, which are possible in malformed code.)
+    pub fn all_super_traits<'a>(
+        self,
+        db: &'a impl HirDatabase,
+    ) -> impl Iterator<Item = Trait> + 'a {
+        self.direct_super_traits(db).into_iter().flat_map(move |t| {
+            iter::once(t).chain(Box::new(t.all_super_traits(db)) as Box<dyn Iterator<Item = Trait>>)
+        })
+    }
+
+    pub fn associated_type_by_name(self, db: &impl DefDatabase, name: &Name) -> Option<TypeAlias> {
         let trait_data = self.trait_data(db);
         trait_data
             .items()
@@ -829,7 +868,18 @@ impl Trait {
                 TraitItem::TypeAlias(t) => Some(*t),
                 _ => None,
             })
-            .find(|t| t.name(db) == name)
+            .find(|t| &t.name(db) == name)
+    }
+
+    pub fn associated_type_by_name_including_super_traits(
+        self,
+        db: &impl HirDatabase,
+        name: &Name,
+    ) -> Option<TypeAlias> {
+        iter::once(self)
+            .chain(self.all_super_traits(db))
+            .unique()
+            .find_map(|t| t.associated_type_by_name(db, name))
     }
 
     pub(crate) fn trait_data(self, db: &impl DefDatabase) -> Arc<TraitData> {
diff --git a/crates/ra_hir/src/generics.rs b/crates/ra_hir/src/generics.rs
index d6728cc9f..c76df0698 100644
--- a/crates/ra_hir/src/generics.rs
+++ b/crates/ra_hir/src/generics.rs
@@ -87,11 +87,15 @@ impl GenericParams {
                 // traits get the Self type as an implicit first type parameter
                 generics.params.push(GenericParam { idx: start, name: SELF_TYPE, default: None });
                 generics.fill(&it.source(db).ast, start + 1);
+                // add super traits as bounds on Self
+                // i.e., trait Foo: Bar is equivalent to trait Foo where Self: Bar
+                let self_param = TypeRef::Path(SELF_TYPE.into());
+                generics.fill_bounds(&it.source(db).ast, self_param);
             }
             GenericDef::TypeAlias(it) => generics.fill(&it.source(db).ast, start),
             // Note that we don't add `Self` here: in `impl`s, `Self` is not a
             // type-parameter, but rather is a type-alias for impl's target
-            // type, so this is handled by the resovler.
+            // type, so this is handled by the resolver.
             GenericDef::ImplBlock(it) => generics.fill(&it.source(db).ast, start),
             GenericDef::EnumVariant(_) => {}
         }
@@ -108,6 +112,14 @@ impl GenericParams {
         }
     }
 
+    fn fill_bounds(&mut self, node: &impl ast::TypeBoundsOwner, type_ref: TypeRef) {
+        for bound in
+            node.type_bound_list().iter().flat_map(|type_bound_list| type_bound_list.bounds())
+        {
+            self.add_where_predicate_from_bound(bound, type_ref.clone());
+        }
+    }
+
     fn fill_params(&mut self, params: ast::TypeParamList, start: u32) {
         for (idx, type_param) in params.type_params().enumerate() {
             let name = type_param.name().map_or_else(Name::missing, |it| it.as_name());
@@ -117,13 +129,7 @@ impl GenericParams {
             self.params.push(param);
 
             let type_ref = TypeRef::Path(name.into());
-            for bound in type_param
-                .type_bound_list()
-                .iter()
-                .flat_map(|type_bound_list| type_bound_list.bounds())
-            {
-                self.add_where_predicate_from_bound(bound, type_ref.clone());
-            }
+            self.fill_bounds(&type_param, type_ref);
         }
     }
 
diff --git a/crates/ra_hir/src/name.rs b/crates/ra_hir/src/name.rs
index 9c4822d91..13bc901bc 100644
--- a/crates/ra_hir/src/name.rs
+++ b/crates/ra_hir/src/name.rs
@@ -38,11 +38,6 @@ 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.
@@ -123,6 +118,7 @@ pub(crate) const FUTURE_TYPE: Name = Name::new(SmolStr::new_inline_from_ascii(6,
 pub(crate) const RESULT_MOD: Name = Name::new(SmolStr::new_inline_from_ascii(6, b"result"));
 pub(crate) const RESULT_TYPE: Name = Name::new(SmolStr::new_inline_from_ascii(6, b"Result"));
 pub(crate) const OUTPUT: Name = Name::new(SmolStr::new_inline_from_ascii(6, b"Output"));
+pub(crate) const TARGET: Name = Name::new(SmolStr::new_inline_from_ascii(6, b"Target"));
 
 fn resolve_name(text: &SmolStr) -> SmolStr {
     let raw_start = "r#";
diff --git a/crates/ra_hir/src/ty/autoderef.rs b/crates/ra_hir/src/ty/autoderef.rs
index 08f52a53b..caa17f64e 100644
--- a/crates/ra_hir/src/ty/autoderef.rs
+++ b/crates/ra_hir/src/ty/autoderef.rs
@@ -8,7 +8,7 @@ use std::iter::successors;
 use log::{info, warn};
 
 use super::{traits::Solution, Canonical, Ty, TypeWalk};
-use crate::{HasGenericParams, HirDatabase, Name, Resolver};
+use crate::{name, HasGenericParams, HirDatabase, Resolver};
 
 const AUTODEREF_RECURSION_LIMIT: usize = 10;
 
@@ -42,7 +42,7 @@ fn deref_by_trait(
         crate::lang_item::LangItemTarget::Trait(t) => t,
         _ => return None,
     };
-    let target = deref_trait.associated_type_by_name(db, Name::target())?;
+    let target = deref_trait.associated_type_by_name(db, &name::TARGET)?;
 
     if target.generic_params(db).count_params_including_parent() != 1 {
         // the Target type + Deref trait should only have one generic parameter,
diff --git a/crates/ra_hir/src/ty/infer.rs b/crates/ra_hir/src/ty/infer.rs
index ec3b7ffef..0e6ebd365 100644
--- a/crates/ra_hir/src/ty/infer.rs
+++ b/crates/ra_hir/src/ty/infer.rs
@@ -1453,7 +1453,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
 
         match self.resolver.resolve_path_segments(self.db, &into_iter_path).into_fully_resolved() {
             PerNs { types: Some(Def(Trait(trait_))), .. } => {
-                Some(trait_.associated_type_by_name(self.db, name::ITEM)?)
+                Some(trait_.associated_type_by_name(self.db, &name::ITEM)?)
             }
             _ => None,
         }
@@ -1471,7 +1471,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
 
         match self.resolver.resolve_path_segments(self.db, &ops_try_path).into_fully_resolved() {
             PerNs { types: Some(Def(Trait(trait_))), .. } => {
-                Some(trait_.associated_type_by_name(self.db, name::OK)?)
+                Some(trait_.associated_type_by_name(self.db, &name::OK)?)
             }
             _ => None,
         }
@@ -1493,7 +1493,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
             .into_fully_resolved()
         {
             PerNs { types: Some(Def(Trait(trait_))), .. } => {
-                Some(trait_.associated_type_by_name(self.db, name::OUTPUT)?)
+                Some(trait_.associated_type_by_name(self.db, &name::OUTPUT)?)
             }
             _ => None,
         }
diff --git a/crates/ra_hir/src/ty/lower.rs b/crates/ra_hir/src/ty/lower.rs
index f6f0137cf..480bae740 100644
--- a/crates/ra_hir/src/ty/lower.rs
+++ b/crates/ra_hir/src/ty/lower.rs
@@ -132,14 +132,16 @@ impl Ty {
             if let Some(remaining_index) = remaining_index {
                 if remaining_index == path.segments.len() - 1 {
                     let segment = &path.segments[remaining_index];
-                    let associated_ty =
-                        match trait_ref.trait_.associated_type_by_name(db, segment.name.clone()) {
-                            Some(t) => t,
-                            None => {
-                                // associated type not found
-                                return Ty::Unknown;
-                            }
-                        };
+                    let associated_ty = match trait_ref
+                        .trait_
+                        .associated_type_by_name_including_super_traits(db, &segment.name)
+                    {
+                        Some(t) => t,
+                        None => {
+                            // associated type not found
+                            return Ty::Unknown;
+                        }
+                    };
                     // FIXME handle type parameters on the segment
                     Ty::Projection(ProjectionTy { associated_ty, parameters: trait_ref.substs })
                 } else {
@@ -387,10 +389,11 @@ fn assoc_type_bindings_from_type_bound<'a>(
         .flat_map(|segment| segment.args_and_bindings.iter())
         .flat_map(|args_and_bindings| args_and_bindings.bindings.iter())
         .map(move |(name, type_ref)| {
-            let associated_ty = match trait_ref.trait_.associated_type_by_name(db, name.clone()) {
-                None => return GenericPredicate::Error,
-                Some(t) => t,
-            };
+            let associated_ty =
+                match trait_ref.trait_.associated_type_by_name_including_super_traits(db, &name) {
+                    None => return GenericPredicate::Error,
+                    Some(t) => t,
+                };
             let projection_ty =
                 ProjectionTy { associated_ty, parameters: trait_ref.substs.clone() };
             let ty = Ty::from_hir(db, resolver, type_ref);
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index cb5540cb6..17c4e3556 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -3720,11 +3720,11 @@ fn test() {
     [157; 160) '{t}': T
     [158; 159) 't': T
     [259; 280) '{     ...S)); }': ()
-    [265; 269) 'get2': fn get2<{unknown}, S<{unknown}>>(T) -> U
-    [265; 277) 'get2(set(S))': {unknown}
-    [270; 273) 'set': fn set<S<{unknown}>>(T) -> T
-    [270; 276) 'set(S)': S<{unknown}>
-    [274; 275) 'S': S<{unknown}>
+    [265; 269) 'get2': fn get2<u64, S<u64>>(T) -> U
+    [265; 277) 'get2(set(S))': u64
+    [270; 273) 'set': fn set<S<u64>>(T) -> T
+    [270; 276) 'set(S)': S<u64>
+    [274; 275) 'S': S<u64>
     "###
     );
 }
diff --git a/crates/ra_hir/src/ty/traits/chalk.rs b/crates/ra_hir/src/ty/traits/chalk.rs
index c201c5e50..cfe0cab16 100644
--- a/crates/ra_hir/src/ty/traits/chalk.rs
+++ b/crates/ra_hir/src/ty/traits/chalk.rs
@@ -636,7 +636,7 @@ pub(crate) fn impl_datum_query(
             _ => None,
         })
         .filter_map(|t| {
-            let assoc_ty = trait_.associated_type_by_name(db, t.name(db))?;
+            let assoc_ty = trait_.associated_type_by_name(db, &t.name(db))?;
             let ty = db.type_for_def(t.into(), crate::Namespace::Types).subst(&bound_vars);
             Some(chalk_rust_ir::AssociatedTyValue {
                 impl_id,
diff --git a/crates/ra_hir/src/type_ref.rs b/crates/ra_hir/src/type_ref.rs
index fa91bfb22..bc8acc7ee 100644
--- a/crates/ra_hir/src/type_ref.rs
+++ b/crates/ra_hir/src/type_ref.rs
@@ -150,4 +150,11 @@ impl TypeBound {
             ast::TypeBoundKind::ForType(_) | ast::TypeBoundKind::Lifetime(_) => TypeBound::Error,
         }
     }
+
+    pub fn as_path(&self) -> Option<&Path> {
+        match self {
+            TypeBound::Path(p) => Some(p),
+            _ => None,
+        }
+    }
 }