14 files changed, 141 insertions, 40 deletions

diff --git a/crates/hir/src/display.rs b/crates/hir/src/display.rs
index 01a4d205f..508ac37c2 100644
--- a/crates/hir/src/display.rs
+++ b/crates/hir/src/display.rs
@@ -170,7 +170,7 @@ impl HirDisplay for Field {
     fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
         write_visibility(self.parent.module(f.db).id, self.visibility(f.db), f)?;
         write!(f, "{}: ", self.name(f.db))?;
-        self.signature_ty(f.db).hir_fmt(f)
+        self.ty(f.db).hir_fmt(f)
     }
 }
 
diff --git a/crates/hir/src/lib.rs b/crates/hir/src/lib.rs
index 0acfa582a..d8ccfde0c 100644
--- a/crates/hir/src/lib.rs
+++ b/crates/hir/src/lib.rs
@@ -509,7 +509,7 @@ impl Field {
     /// placeholder types for type parameters). This is good for showing
     /// signature help, but not so good to actually get the type of the field
     /// when you actually have a variable of the struct.
-    pub fn signature_ty(&self, db: &dyn HirDatabase) -> Type {
+    pub fn ty(&self, db: &dyn HirDatabase) -> Type {
         let var_id = self.parent.into();
         let generic_def_id: GenericDefId = match self.parent {
             VariantDef::Struct(it) => it.id.into(),
@@ -1984,7 +1984,7 @@ impl Type {
         None
     }
 
-    pub fn type_parameters(&self) -> impl Iterator<Item = Type> + '_ {
+    pub fn type_arguments(&self) -> impl Iterator<Item = Type> + '_ {
         self.ty
             .strip_references()
             .as_adt()
diff --git a/crates/hir_def/src/find_path.rs b/crates/hir_def/src/find_path.rs
index dc3f2908f..c06a37294 100644
--- a/crates/hir_def/src/find_path.rs
+++ b/crates/hir_def/src/find_path.rs
@@ -130,7 +130,8 @@ fn find_path_inner(
     }
 
     // - if the item is the crate root of a dependency crate, return the name from the extern prelude
-    for (name, def_id) in root.def_map(db).extern_prelude() {
+    let root_def_map = root.def_map(db);
+    for (name, def_id) in root_def_map.extern_prelude() {
         if item == ItemInNs::Types(*def_id) {
             let name = scope_name.unwrap_or_else(|| name.clone());
             return Some(ModPath::from_segments(PathKind::Plain, vec![name]));
@@ -138,7 +139,8 @@ fn find_path_inner(
     }
 
     // - if the item is in the prelude, return the name from there
-    if let Some(prelude_module) = def_map.prelude() {
+    if let Some(prelude_module) = root_def_map.prelude() {
+        // Preludes in block DefMaps are ignored, only the crate DefMap is searched
         let prelude_def_map = prelude_module.def_map(db);
         let prelude_scope: &crate::item_scope::ItemScope =
             &prelude_def_map[prelude_module.local_id].scope;
@@ -1057,4 +1059,28 @@ fn f() {
             "dep",
         );
     }
+
+    #[test]
+    fn prelude_with_inner_items() {
+        check_found_path(
+            r#"
+//- /main.rs crate:main deps:std
+fn f() {
+    fn inner() {}
+    $0
+}
+//- /std.rs crate:std
+pub mod prelude {
+    pub enum Option { None }
+    pub use Option::*;
+}
+#[prelude_import]
+pub use prelude::*;
+        "#,
+            "None",
+            "None",
+            "None",
+            "None",
+        );
+    }
 }
diff --git a/crates/hir_ty/src/db.rs b/crates/hir_ty/src/db.rs
index cf67d4266..9da0a02e3 100644
--- a/crates/hir_ty/src/db.rs
+++ b/crates/hir_ty/src/db.rs
@@ -70,6 +70,7 @@ pub trait HirDatabase: DefDatabase + Upcast<dyn DefDatabase> {
     fn trait_environment(&self, def: GenericDefId) -> Arc<crate::TraitEnvironment>;
 
     #[salsa::invoke(crate::lower::generic_defaults_query)]
+    #[salsa::cycle(crate::lower::generic_defaults_recover)]
     fn generic_defaults(&self, def: GenericDefId) -> Arc<[Binders<Ty>]>;
 
     #[salsa::invoke(InherentImpls::inherent_impls_in_crate_query)]
diff --git a/crates/hir_ty/src/lower.rs b/crates/hir_ty/src/lower.rs
index 7fd46becd..c99dd8d0a 100644
--- a/crates/hir_ty/src/lower.rs
+++ b/crates/hir_ty/src/lower.rs
@@ -414,17 +414,16 @@ impl<'a> TyLoweringContext<'a> {
                     self.lower_trait_ref_from_resolved_path(trait_, resolved_segment, self_ty);
                 let ty = if remaining_segments.len() == 1 {
                     let segment = remaining_segments.first().unwrap();
-                    let found = associated_type_by_name_including_super_traits(
-                        self.db,
-                        trait_ref,
-                        &segment.name,
-                    );
+                    let found = self
+                        .db
+                        .trait_data(trait_ref.hir_trait_id())
+                        .associated_type_by_name(&segment.name);
                     match found {
-                        Some((super_trait_ref, associated_ty)) => {
+                        Some(associated_ty) => {
                             // FIXME handle type parameters on the segment
                             TyKind::Alias(AliasTy::Projection(ProjectionTy {
                                 associated_ty_id: to_assoc_type_id(associated_ty),
-                                substitution: super_trait_ref.substitution,
+                                substitution: trait_ref.substitution,
                             }))
                             .intern(&Interner)
                         }
@@ -1089,6 +1088,27 @@ pub(crate) fn generic_defaults_query(
     defaults
 }
 
+pub(crate) fn generic_defaults_recover(
+    db: &dyn HirDatabase,
+    _cycle: &[String],
+    def: &GenericDefId,
+) -> Arc<[Binders<Ty>]> {
+    let generic_params = generics(db.upcast(), *def);
+
+    // we still need one default per parameter
+    let defaults = generic_params
+        .iter()
+        .enumerate()
+        .map(|(idx, _)| {
+            let ty = TyKind::Error.intern(&Interner);
+
+            crate::make_only_type_binders(idx, ty)
+        })
+        .collect();
+
+    defaults
+}
+
 fn fn_sig_for_fn(db: &dyn HirDatabase, def: FunctionId) -> PolyFnSig {
     let data = db.function_data(def);
     let resolver = def.resolver(db.upcast());
diff --git a/crates/hir_ty/src/tests/regression.rs b/crates/hir_ty/src/tests/regression.rs
index 9cd9f473d..d14f5c9bb 100644
--- a/crates/hir_ty/src/tests/regression.rs
+++ b/crates/hir_ty/src/tests/regression.rs
@@ -1012,3 +1012,41 @@ fn lifetime_from_chalk_during_deref() {
         "#,
     )
 }
+
+#[test]
+fn issue_8686() {
+    check_infer(
+        r#"
+pub trait Try: FromResidual {
+    type Output;
+    type Residual;
+}
+pub trait FromResidual<R = <Self as Try>::Residual> {
+     fn from_residual(residual: R) -> Self;
+}
+
+struct ControlFlow<B, C>;
+impl<B, C> Try for ControlFlow<B, C> {
+    type Output = C;
+    type Residual = ControlFlow<B, !>;
+}
+impl<B, C> FromResidual for ControlFlow<B, C> {
+    fn from_residual(r: ControlFlow<B, !>) -> Self { ControlFlow }
+}
+
+fn test() {
+    ControlFlow::from_residual(ControlFlow::<u32, !>);
+}
+        "#,
+        expect![[r#"
+            144..152 'residual': R
+            365..366 'r': ControlFlow<B, !>
+            395..410 '{ ControlFlow }': ControlFlow<B, C>
+            397..408 'ControlFlow': ControlFlow<B, C>
+            424..482 '{     ...!>); }': ()
+            430..456 'Contro...sidual': fn from_residual<ControlFlow<u32, {unknown}>, ControlFlow<u32, !>>(ControlFlow<u32, !>) -> ControlFlow<u32, {unknown}>
+            430..479 'Contro...2, !>)': ControlFlow<u32, {unknown}>
+            457..478 'Contro...32, !>': ControlFlow<u32, !>
+        "#]],
+    );
+}
diff --git a/crates/hir_ty/src/utils.rs b/crates/hir_ty/src/utils.rs
index 2f04ee57a..2f490fb92 100644
--- a/crates/hir_ty/src/utils.rs
+++ b/crates/hir_ty/src/utils.rs
@@ -1,6 +1,8 @@
 //! Helper functions for working with def, which don't need to be a separate
 //! query, but can't be computed directly from `*Data` (ie, which need a `db`).
 
+use std::iter;
+
 use chalk_ir::{fold::Shift, BoundVar, DebruijnIndex};
 use hir_def::{
     db::DefDatabase,
@@ -14,8 +16,12 @@ use hir_def::{
     AssocContainerId, GenericDefId, Lookup, TraitId, TypeAliasId, TypeParamId,
 };
 use hir_expand::name::{name, Name};
+use rustc_hash::FxHashSet;
 
-use crate::{db::HirDatabase, Interner, Substitution, TraitRef, TraitRefExt, TyKind, WhereClause};
+use crate::{
+    db::HirDatabase, ChalkTraitId, Interner, Substitution, TraitRef, TraitRefExt, TyKind,
+    WhereClause,
+};
 
 fn direct_super_traits(db: &dyn DefDatabase, trait_: TraitId) -> Vec<TraitId> {
     let resolver = trait_.resolver(db);
@@ -102,25 +108,35 @@ pub fn all_super_traits(db: &dyn DefDatabase, trait_: TraitId) -> Vec<TraitId> {
 /// `all_super_traits` is that we keep track of type parameters; for example if
 /// we have `Self: Trait<u32, i32>` and `Trait<T, U>: OtherTrait<U>` we'll get
 /// `Self: OtherTrait<i32>`.
-pub(super) fn all_super_trait_refs(db: &dyn HirDatabase, trait_ref: TraitRef) -> Vec<TraitRef> {
-    // FIXME: replace by Chalk's `super_traits`, maybe make this a query
+pub(super) fn all_super_trait_refs(db: &dyn HirDatabase, trait_ref: TraitRef) -> SuperTraits {
+    SuperTraits { db, seen: iter::once(trait_ref.trait_id).collect(), stack: vec![trait_ref] }
+}
 
-    // we need to take care a bit here to avoid infinite loops in case of cycles
-    // (i.e. if we have `trait A: B; trait B: A;`)
-    let mut result = vec![trait_ref];
-    let mut i = 0;
-    while i < result.len() {
-        let t = &result[i];
-        // yeah this is quadratic, but trait hierarchies should be flat
-        // enough that this doesn't matter
-        for tt in direct_super_trait_refs(db, t) {
-            if !result.iter().any(|tr| tr.trait_id == tt.trait_id) {
-                result.push(tt);
-            }
+pub(super) struct SuperTraits<'a> {
+    db: &'a dyn HirDatabase,
+    stack: Vec<TraitRef>,
+    seen: FxHashSet<ChalkTraitId>,
+}
+
+impl<'a> SuperTraits<'a> {
+    fn elaborate(&mut self, trait_ref: &TraitRef) {
+        let mut trait_refs = direct_super_trait_refs(self.db, trait_ref);
+        trait_refs.retain(|tr| !self.seen.contains(&tr.trait_id));
+        self.stack.extend(trait_refs);
+    }
+}
+
+impl<'a> Iterator for SuperTraits<'a> {
+    type Item = TraitRef;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        if let Some(next) = self.stack.pop() {
+            self.elaborate(&next);
+            Some(next)
+        } else {
+            None
         }
-        i += 1;
     }
-    result
 }
 
 pub(super) fn associated_type_by_name_including_super_traits(
@@ -128,7 +144,7 @@ pub(super) fn associated_type_by_name_including_super_traits(
     trait_ref: TraitRef,
     name: &Name,
 ) -> Option<(TraitRef, TypeAliasId)> {
-    all_super_trait_refs(db, trait_ref).into_iter().find_map(|t| {
+    all_super_trait_refs(db, trait_ref).find_map(|t| {
         let assoc_type = db.trait_data(t.hir_trait_id()).associated_type_by_name(name)?;
         Some((t, assoc_type))
     })
diff --git a/crates/ide/src/runnables.rs b/crates/ide/src/runnables.rs
index 3eb9e27ee..f76715d84 100644
--- a/crates/ide/src/runnables.rs
+++ b/crates/ide/src/runnables.rs
@@ -304,11 +304,11 @@ fn module_def_doctest(sema: &Semantics<RootDatabase>, def: hir::ModuleDef) -> Op
                         let name = adt.name(sema.db);
                         let idx = path.rfind(':').map_or(0, |idx| idx + 1);
                         let (prefix, suffix) = path.split_at(idx);
-                        let mut ty_params = ty.type_parameters().peekable();
-                        let params = if ty_params.peek().is_some() {
+                        let mut ty_args = ty.type_arguments().peekable();
+                        let params = if ty_args.peek().is_some() {
                             format!(
                                 "<{}>",
-                                ty_params.format_with(", ", |ty, cb| cb(&ty.display(sema.db)))
+                                ty_args.format_with(", ", |ty, cb| cb(&ty.display(sema.db)))
                             )
                         } else {
                             String::new()
diff --git a/crates/ide_assists/src/handlers/extract_function.rs b/crates/ide_assists/src/handlers/extract_function.rs
index 5f80a40c8..b30652a9d 100644
--- a/crates/ide_assists/src/handlers/extract_function.rs
+++ b/crates/ide_assists/src/handlers/extract_function.rs
@@ -1183,7 +1183,7 @@ fn make_ret_ty(ctx: &AssistContext, module: hir::Module, fun: &Function) -> Opti
         }
         FlowHandler::Try { kind: TryKind::Result { ty: parent_ret_ty } } => {
             let handler_ty = parent_ret_ty
-                .type_parameters()
+                .type_arguments()
                 .nth(1)
                 .map(|ty| make_ty(&ty, ctx, module))
                 .unwrap_or_else(make::ty_unit);
diff --git a/crates/ide_assists/src/handlers/generate_from_impl_for_enum.rs b/crates/ide_assists/src/handlers/generate_from_impl_for_enum.rs
index c13c6eebe..ce6998d82 100644
--- a/crates/ide_assists/src/handlers/generate_from_impl_for_enum.rs
+++ b/crates/ide_assists/src/handlers/generate_from_impl_for_enum.rs
@@ -91,7 +91,7 @@ fn existing_from_impl(
 
     let enum_type = enum_.ty(sema.db);
 
-    let wrapped_type = variant.fields(sema.db).get(0)?.signature_ty(sema.db);
+    let wrapped_type = variant.fields(sema.db).get(0)?.ty(sema.db);
 
     if enum_type.impls_trait(sema.db, from_trait, &[wrapped_type]) {
         Some(())
diff --git a/crates/ide_assists/src/utils/suggest_name.rs b/crates/ide_assists/src/utils/suggest_name.rs
index 533624c1f..deafcd630 100644
--- a/crates/ide_assists/src/utils/suggest_name.rs
+++ b/crates/ide_assists/src/utils/suggest_name.rs
@@ -227,7 +227,7 @@ fn name_of_type(ty: &hir::Type, db: &RootDatabase) -> Option<String> {
         let name = adt.name(db).to_string();
 
         if WRAPPER_TYPES.contains(&name.as_str()) {
-            let inner_ty = ty.type_parameters().next()?;
+            let inner_ty = ty.type_arguments().next()?;
             return name_of_type(&inner_ty, db);
         }
 
diff --git a/crates/ide_completion/src/completions/postfix/format_like.rs b/crates/ide_completion/src/completions/postfix/format_like.rs
index e86ffa8f8..0dcb3e898 100644
--- a/crates/ide_completion/src/completions/postfix/format_like.rs
+++ b/crates/ide_completion/src/completions/postfix/format_like.rs
@@ -1,4 +1,4 @@
-// Feature: Format String Completion.
+// Feature: Format String Completion
 //
 // `"Result {result} is {2 + 2}"` is expanded to the `"Result {} is {}", result, 2 + 2`.
 //
diff --git a/crates/ide_completion/src/context.rs b/crates/ide_completion/src/context.rs
index 32f81aec1..b005bd773 100644
--- a/crates/ide_completion/src/context.rs
+++ b/crates/ide_completion/src/context.rs
@@ -347,7 +347,7 @@ impl<'a> CompletionContext<'a> {
                                 .and_then(|node| ast::RecordExprField::cast(node))
                                 .and_then(|rf| self.sema.resolve_record_field(&rf).zip(Some(rf)))
                                 .map(|(f, rf)|(
-                                    Some(f.0.signature_ty(self.db)),
+                                    Some(f.0.ty(self.db)),
                                     rf.field_name().map(NameOrNameRef::NameRef),
                                 ))
                                 .unwrap_or((None, None))
@@ -357,7 +357,7 @@ impl<'a> CompletionContext<'a> {
                             self.sema
                                 .resolve_record_field(&it)
                                 .map(|f|(
-                                    Some(f.0.signature_ty(self.db)),
+                                    Some(f.0.ty(self.db)),
                                     it.field_name().map(NameOrNameRef::NameRef),
                                 ))
                                 .unwrap_or((None, None))
diff --git a/crates/ide_completion/src/render/enum_variant.rs b/crates/ide_completion/src/render/enum_variant.rs
index 832f5ced1..0c0c71134 100644
--- a/crates/ide_completion/src/render/enum_variant.rs
+++ b/crates/ide_completion/src/render/enum_variant.rs
@@ -93,7 +93,7 @@ impl<'a> EnumRender<'a> {
             .variant
             .fields(self.ctx.db())
             .into_iter()
-            .map(|field| (field.name(self.ctx.db()), field.signature_ty(self.ctx.db())));
+            .map(|field| (field.name(self.ctx.db()), field.ty(self.ctx.db())));
 
         match self.variant_kind {
             StructKind::Tuple | StructKind::Unit => format!(