6 files changed, 168 insertions, 22 deletions

diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs
index f7f124904..05259dcbb 100644
--- a/crates/ra_hir/src/db.rs
+++ b/crates/ra_hir/src/db.rs
@@ -164,6 +164,13 @@ pub trait HirDatabase: DefDatabase + AstDatabase {
     #[salsa::invoke(crate::ty::callable_item_sig)]
     fn callable_item_signature(&self, def: CallableDef) -> FnSig;
 
+    #[salsa::invoke(crate::ty::generic_predicates_for_param_query)]
+    fn generic_predicates_for_param(
+        &self,
+        def: GenericDef,
+        param_idx: u32,
+    ) -> Arc<[GenericPredicate]>;
+
     #[salsa::invoke(crate::ty::generic_predicates_query)]
     fn generic_predicates(&self, def: GenericDef) -> Arc<[GenericPredicate]>;
 
diff --git a/crates/ra_hir/src/generics.rs b/crates/ra_hir/src/generics.rs
index 77fb76bfc..ccb777492 100644
--- a/crates/ra_hir/src/generics.rs
+++ b/crates/ra_hir/src/generics.rs
@@ -26,8 +26,9 @@ pub struct GenericParam {
 }
 
 /// Data about the generic parameters of a function, struct, impl, etc.
-#[derive(Clone, PartialEq, Eq, Debug, Default)]
+#[derive(Clone, PartialEq, Eq, Debug)]
 pub struct GenericParams {
+    pub(crate) def: GenericDef,
     pub(crate) parent_params: Option<Arc<GenericParams>>,
     pub(crate) params: Vec<GenericParam>,
     pub(crate) where_predicates: Vec<WherePredicate>,
@@ -69,7 +70,6 @@ impl GenericParams {
         db: &(impl DefDatabase + AstDatabase),
         def: GenericDef,
     ) -> Arc<GenericParams> {
-        let mut generics = GenericParams::default();
         let parent = match def {
             GenericDef::Function(it) => it.container(db).map(GenericDef::from),
             GenericDef::TypeAlias(it) => it.container(db).map(GenericDef::from),
@@ -77,7 +77,12 @@ impl GenericParams {
             GenericDef::Adt(_) | GenericDef::Trait(_) => None,
             GenericDef::ImplBlock(_) => None,
         };
-        generics.parent_params = parent.map(|p| db.generic_params(p));
+        let mut generics = GenericParams {
+            def,
+            params: Vec::new(),
+            parent_params: parent.map(|p| db.generic_params(p)),
+            where_predicates: Vec::new(),
+        };
         let start = generics.parent_params.as_ref().map(|p| p.params.len()).unwrap_or(0) as u32;
         // FIXME: add `: Sized` bound for everything except for `Self` in traits
         match def {
diff --git a/crates/ra_hir/src/resolve.rs b/crates/ra_hir/src/resolve.rs
index 254d1a964..39f8e1d8a 100644
--- a/crates/ra_hir/src/resolve.rs
+++ b/crates/ra_hir/src/resolve.rs
@@ -344,6 +344,13 @@ impl Resolver {
             })
             .flat_map(|params| params.where_predicates.iter())
     }
+
+    pub(crate) fn generic_def(&self) -> Option<crate::generics::GenericDef> {
+        self.scopes.iter().find_map(|scope| match scope {
+            Scope::GenericParams(params) => Some(params.def),
+            _ => None,
+        })
+    }
 }
 
 impl Resolver {
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index a223e120a..36bfb10ce 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -23,8 +23,8 @@ pub(crate) use autoderef::autoderef;
 pub(crate) use infer::{infer_query, InferTy, InferenceResult};
 pub use lower::CallableDef;
 pub(crate) use lower::{
-    callable_item_sig, generic_defaults_query, generic_predicates_query, type_for_def,
-    type_for_field, TypableDef,
+    callable_item_sig, generic_defaults_query, generic_predicates_for_param_query,
+    generic_predicates_query, type_for_def, type_for_field, TypableDef,
 };
 pub(crate) use traits::{InEnvironment, Obligation, ProjectionPredicate, TraitEnvironment};
 
diff --git a/crates/ra_hir/src/ty/lower.rs b/crates/ra_hir/src/ty/lower.rs
index a83842b0f..8d71abc95 100644
--- a/crates/ra_hir/src/ty/lower.rs
+++ b/crates/ra_hir/src/ty/lower.rs
@@ -86,6 +86,35 @@ impl Ty {
         }
     }
 
+    /// This is only for `generic_predicates_for_param`, where we can't just
+    /// lower the self types of the predicates since that could lead to cycles.
+    /// So we just check here if the `type_ref` resolves to a generic param, and which.
+    fn from_hir_only_param(
+        db: &impl HirDatabase,
+        resolver: &Resolver,
+        type_ref: &TypeRef,
+    ) -> Option<u32> {
+        let path = match type_ref {
+            TypeRef::Path(path) => path,
+            _ => return None,
+        };
+        if let crate::PathKind::Type(_) = &path.kind {
+            return None;
+        }
+        if path.segments.len() > 1 {
+            return None;
+        }
+        let resolution = match resolver.resolve_path_in_type_ns(db, path) {
+            Some((it, None)) => it,
+            _ => return None,
+        };
+        if let TypeNs::GenericParam(idx) = resolution {
+            Some(idx)
+        } else {
+            None
+        }
+    }
+
     pub(crate) fn from_type_relative_path(
         db: &impl HirDatabase,
         resolver: &Resolver,
@@ -189,11 +218,37 @@ impl Ty {
     }
 
     fn select_associated_type(
-        _db: &impl HirDatabase,
-        _resolver: &Resolver,
-        _self_ty: Ty,
-        _segment: &PathSegment,
+        db: &impl HirDatabase,
+        resolver: &Resolver,
+        self_ty: Ty,
+        segment: &PathSegment,
     ) -> Ty {
+        let param_idx = match self_ty {
+            Ty::Param { idx, .. } => idx,
+            _ => return Ty::Unknown, // Error: Ambiguous associated type
+        };
+        let def = match resolver.generic_def() {
+            Some(def) => def,
+            None => return Ty::Unknown, // this can't actually happen
+        };
+        let predicates = db.generic_predicates_for_param(def, param_idx);
+        let traits_from_env = predicates.iter().filter_map(|pred| match pred {
+            GenericPredicate::Implemented(tr) if tr.self_ty() == &self_ty => Some(tr.trait_),
+            _ => None,
+        });
+        let traits = traits_from_env.flat_map(|t| t.all_super_traits(db));
+        for t in traits {
+            if let Some(associated_ty) = t.associated_type_by_name(db, &segment.name) {
+                let generics = t.generic_params(db);
+                let mut substs = Vec::new();
+                substs.push(self_ty.clone());
+                substs.extend(
+                    iter::repeat(Ty::Unknown).take(generics.count_params_including_parent() - 1),
+                );
+                // FIXME handle type parameters on the segment
+                return Ty::Projection(ProjectionTy { associated_ty, parameters: substs.into() });
+            }
+        }
         Ty::Unknown
     }
 
@@ -269,9 +324,10 @@ pub(super) fn substs_from_path_segment(
     add_self_param: bool,
 ) -> Substs {
     let mut substs = Vec::new();
-    let def_generics = def_generic.map(|def| def.generic_params(db)).unwrap_or_default();
+    let def_generics = def_generic.map(|def| def.generic_params(db));
 
-    let parent_param_count = def_generics.count_parent_params();
+    let (parent_param_count, param_count) =
+        def_generics.map_or((0, 0), |g| (g.count_parent_params(), g.params.len()));
     substs.extend(iter::repeat(Ty::Unknown).take(parent_param_count));
     if add_self_param {
         // FIXME this add_self_param argument is kind of a hack: Traits have the
@@ -283,7 +339,7 @@ pub(super) fn substs_from_path_segment(
     if let Some(generic_args) = &segment.args_and_bindings {
         // if args are provided, it should be all of them, but we can't rely on that
         let self_param_correction = if add_self_param { 1 } else { 0 };
-        let param_count = def_generics.params.len() - self_param_correction;
+        let param_count = param_count - self_param_correction;
         for arg in generic_args.args.iter().take(param_count) {
             match arg {
                 GenericArg::Type(type_ref) => {
@@ -295,10 +351,10 @@ pub(super) fn substs_from_path_segment(
     }
     // add placeholders for args that were not provided
     let supplied_params = substs.len();
-    for _ in supplied_params..def_generics.count_params_including_parent() {
+    for _ in supplied_params..parent_param_count + param_count {
         substs.push(Ty::Unknown);
     }
-    assert_eq!(substs.len(), def_generics.count_params_including_parent());
+    assert_eq!(substs.len(), parent_param_count + param_count);
 
     // handle defaults
     if let Some(def_generic) = def_generic {
@@ -491,6 +547,29 @@ pub(crate) fn type_for_field(db: &impl HirDatabase, field: StructField) -> Ty {
     Ty::from_hir(db, &resolver, type_ref)
 }
 
+/// This query exists only to be used when resolving short-hand associated types
+/// like `T::Item`.
+///
+/// See the analogous query in rustc and its comment:
+/// https://github.com/rust-lang/rust/blob/9150f844e2624eb013ec78ca08c1d416e6644026/src/librustc_typeck/astconv.rs#L46
+/// This is a query mostly to handle cycles somewhat gracefully; e.g. the
+/// following bounds are disallowed: `T: Foo<U::Item>, U: Foo<T::Item>`, but
+/// these are fine: `T: Foo<U::Item>, U: Foo<()>`.
+pub(crate) fn generic_predicates_for_param_query(
+    db: &impl HirDatabase,
+    def: GenericDef,
+    param_idx: u32,
+) -> Arc<[GenericPredicate]> {
+    let resolver = def.resolver(db);
+    let predicates = resolver
+        .where_predicates_in_scope()
+        // we have to filter out all other predicates *first*, before attempting to lower them
+        .filter(|pred| Ty::from_hir_only_param(db, &resolver, &pred.type_ref) == Some(param_idx))
+        .flat_map(|pred| GenericPredicate::from_where_predicate(db, &resolver, pred))
+        .collect::<Vec<_>>();
+    predicates.into()
+}
+
 pub(crate) fn trait_env(
     db: &impl HirDatabase,
     resolver: &Resolver,
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index 3b0a99460..3ac1fbdd5 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -2740,17 +2740,17 @@ fn test() {
     [202; 203) 't': T
     [221; 223) '{}': ()
     [234; 300) '{     ...(S); }': ()
-    [244; 245) 'x': {unknown}
-    [248; 252) 'foo1': fn foo1<S>(T) -> {unknown}
-    [248; 255) 'foo1(S)': {unknown}
+    [244; 245) 'x': u32
+    [248; 252) 'foo1': fn foo1<S>(T) -> <T as Iterable>::Item
+    [248; 255) 'foo1(S)': u32
     [253; 254) 'S': S
     [265; 266) 'y': u32
     [269; 273) 'foo2': fn foo2<S>(T) -> <T as Iterable>::Item
     [269; 276) 'foo2(S)': u32
     [274; 275) 'S': S
-    [286; 287) 'z': {unknown}
-    [290; 294) 'foo3': fn foo3<S>(T) -> {unknown}
-    [290; 297) 'foo3(S)': {unknown}
+    [286; 287) 'z': u32
+    [290; 294) 'foo3': fn foo3<S>(T) -> <T as Iterable>::Item
+    [290; 297) 'foo3(S)': u32
     [295; 296) 'S': S
     "###
     );
@@ -4080,7 +4080,7 @@ fn test<F: FnOnce(u32) -> u64>(f: F) {
 }
 
 #[test]
-fn unselected_projection_in_trait_env() {
+fn unselected_projection_in_trait_env_1() {
     let t = type_at(
         r#"
 //- /main.rs
@@ -4102,7 +4102,33 @@ fn test<T: Trait>() where T::Item: Trait2 {
 }
 
 #[test]
-fn unselected_projection_in_trait_env_cycle() {
+fn unselected_projection_in_trait_env_2() {
+    let t = type_at(
+        r#"
+//- /main.rs
+trait Trait<T> {
+    type Item;
+}
+
+trait Trait2 {
+    fn foo(&self) -> u32;
+}
+
+fn test<T, U>() where T::Item: Trait2, T: Trait<U::Item>, U: Trait<()> {
+    let x: T::Item = no_matter;
+    x.foo()<|>;
+}
+"#,
+    );
+    assert_eq!(t, "u32");
+}
+
+#[test]
+// FIXME this is currently a Salsa panic; it would be nicer if it just returned
+// in Unknown, and we should be able to do that once Salsa allows us to handle
+// the cycle. But at least it doesn't overflow for now.
+#[should_panic]
+fn unselected_projection_in_trait_env_cycle_1() {
     let t = type_at(
         r#"
 //- /main.rs
@@ -4121,6 +4147,28 @@ fn test<T: Trait>() where T: Trait2<T::Item> {
     assert_eq!(t, "{unknown}");
 }
 
+#[test]
+// FIXME this is currently a Salsa panic; it would be nicer if it just returned
+// in Unknown, and we should be able to do that once Salsa allows us to handle
+// the cycle. But at least it doesn't overflow for now.
+#[should_panic]
+fn unselected_projection_in_trait_env_cycle_2() {
+    let t = type_at(
+        r#"
+//- /main.rs
+trait Trait<T> {
+    type Item;
+}
+
+fn test<T, U>() where T: Trait<U::Item>, U: Trait<T::Item> {
+    let x: T::Item = no_matter<|>;
+}
+"#,
+    );
+    // this is a legitimate cycle
+    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();