Auto merge of #17541 - ShoyuVanilla:nested-impl-traits, r=Veykril

Disallow nested impl traits

Fixes #17498

The above issue is due to formatting self referencing, recursive bound like `Implemented(^0.0: TraitId(0)<[?0 := ^0.0]>)` on the codes like;

```rust
trait Foo<T> {}

trait Bar {}

fn test(foo: impl Foo<impl Bar>) { ... }
```

When lowering predicate `impl Foo<impl Bar>` in `trait_environment_query`, the outer `impl Foo<...>` is treated as predicates, so the first `TypeRef` that passes the following code is `impl Bar`;

https://github.com/rust-lang/rust-analyzer/blob/cae997e3380363a906588f14c7b4587f39cf09f5/crates/hir-ty/src/lower.rs#L376-L400

and thus the `idx` is `0` in the above context.

But the following code sets `self_ty` as the `BoundVar` with `idx = 0` because the target param id for predicate  `impl Foo<...>` is `0` since `impl Foo` is the first generic-like parameter of `fn test`;

https://github.com/rust-lang/rust-analyzer/blob/cae997e3380363a906588f14c7b4587f39cf09f5/crates/hir-ty/src/lower.rs#L998-L1025

For the codes like;

```rust
trait Foo {
    type Assoc;
}

trait Bar {}

fn test(foo: impl Foo<Assoc = impl Bar>) { ... }
```

similar recursive bound doesn't happen because the following codes ***"count the number of `impl Trait` things that appear before the target of our `bound`."***

https://github.com/rust-lang/rust-analyzer/blob/cae997e3380363a906588f14c7b4587f39cf09f5/crates/hir-ty/src/lower.rs#L1168-L1199

Instead of doing similar thing like nested `impl Foo<impl Bar>` thing, this PR lowers such nested impl traits into error types in the similar manner as the rustc does in the following lines (and of course, allows lowering and inferencing nested impl traits for the cases that rustc permits);

- https://github.com/rust-lang/rust/blob/e2cf31a6148725bde4ea48acf1e4fe72675257a2/compiler/rustc_ast_passes/src/ast_validation.rs#L802-L813
- https://github.com/rust-lang/rust/blob/7b21c18fe4de32a7d2faa468e6ef69abff013f85/compiler/rustc_ast_passes/src/ast_validation.rs#L1299-L1314

(Though rustc emits [E0666😈](https://doc.rust-lang.org/error_codes/E0666.html), I skipped diagnostics since gathering diagnostics in `hir-def` has no conventions so far 😅)

4 files changed, 112 insertions, 1 deletions

diff --git a/src/tools/rust-analyzer/crates/hir-def/src/hir/type_ref.rs b/src/tools/rust-analyzer/crates/hir-def/src/hir/type_ref.rs
index ec207a7f965..741ae41c743 100644
--- a/src/tools/rust-analyzer/crates/hir-def/src/hir/type_ref.rs
+++ b/src/tools/rust-analyzer/crates/hir-def/src/hir/type_ref.rs
@@ -245,7 +245,13 @@ impl TypeRef {
             // for types are close enough for our purposes to the inner type for now...
             ast::Type::ForType(inner) => TypeRef::from_ast_opt(ctx, inner.ty()),
             ast::Type::ImplTraitType(inner) => {
-                TypeRef::ImplTrait(type_bounds_from_ast(ctx, inner.type_bound_list()))
+                if ctx.outer_impl_trait() {
+                    // Disallow nested impl traits
+                    TypeRef::Error
+                } else {
+                    let _guard = ctx.outer_impl_trait_scope(true);
+                    TypeRef::ImplTrait(type_bounds_from_ast(ctx, inner.type_bound_list()))
+                }
             }
             ast::Type::DynTraitType(inner) => {
                 TypeRef::DynTrait(type_bounds_from_ast(ctx, inner.type_bound_list()))
diff --git a/src/tools/rust-analyzer/crates/hir-def/src/lower.rs b/src/tools/rust-analyzer/crates/hir-def/src/lower.rs
index ecd8d79f20b..e4786a1dd40 100644
--- a/src/tools/rust-analyzer/crates/hir-def/src/lower.rs
+++ b/src/tools/rust-analyzer/crates/hir-def/src/lower.rs
@@ -18,6 +18,26 @@ pub struct LowerCtx<'a> {
     span_map: OnceCell<SpanMap>,
     ast_id_map: OnceCell<Arc<AstIdMap>>,
     impl_trait_bounds: RefCell<Vec<Vec<Interned<TypeBound>>>>,
+    // Prevent nested impl traits like `impl Foo<impl Bar>`.
+    outer_impl_trait: RefCell<bool>,
+}
+
+pub(crate) struct OuterImplTraitGuard<'a> {
+    ctx: &'a LowerCtx<'a>,
+    old: bool,
+}
+
+impl<'a> OuterImplTraitGuard<'a> {
+    fn new(ctx: &'a LowerCtx<'a>, impl_trait: bool) -> Self {
+        let old = ctx.outer_impl_trait.replace(impl_trait);
+        Self { ctx, old }
+    }
+}
+
+impl<'a> Drop for OuterImplTraitGuard<'a> {
+    fn drop(&mut self) {
+        self.ctx.outer_impl_trait.replace(self.old);
+    }
 }
 
 impl<'a> LowerCtx<'a> {
@@ -28,6 +48,7 @@ impl<'a> LowerCtx<'a> {
             span_map: OnceCell::new(),
             ast_id_map: OnceCell::new(),
             impl_trait_bounds: RefCell::new(Vec::new()),
+            outer_impl_trait: RefCell::default(),
         }
     }
 
@@ -42,6 +63,7 @@ impl<'a> LowerCtx<'a> {
             span_map,
             ast_id_map: OnceCell::new(),
             impl_trait_bounds: RefCell::new(Vec::new()),
+            outer_impl_trait: RefCell::default(),
         }
     }
 
@@ -67,4 +89,12 @@ impl<'a> LowerCtx<'a> {
     pub fn take_impl_traits_bounds(&self) -> Vec<Vec<Interned<TypeBound>>> {
         self.impl_trait_bounds.take()
     }
+
+    pub(crate) fn outer_impl_trait(&self) -> bool {
+        *self.outer_impl_trait.borrow()
+    }
+
+    pub(crate) fn outer_impl_trait_scope(&'a self, impl_trait: bool) -> OuterImplTraitGuard<'a> {
+        OuterImplTraitGuard::new(self, impl_trait)
+    }
 }
diff --git a/src/tools/rust-analyzer/crates/hir-def/src/path/lower.rs b/src/tools/rust-analyzer/crates/hir-def/src/path/lower.rs
index 2b555b3998a..a710c2dacaa 100644
--- a/src/tools/rust-analyzer/crates/hir-def/src/path/lower.rs
+++ b/src/tools/rust-analyzer/crates/hir-def/src/path/lower.rs
@@ -202,6 +202,8 @@ pub(super) fn lower_generic_args(
                     continue;
                 }
                 if let Some(name_ref) = assoc_type_arg.name_ref() {
+                    // Nested impl traits like `impl Foo<Assoc = impl Bar>` are allowed
+                    let _guard = lower_ctx.outer_impl_trait_scope(false);
                     let name = name_ref.as_name();
                     let args = assoc_type_arg
                         .generic_arg_list()
diff --git a/src/tools/rust-analyzer/crates/hir-ty/src/tests/traits.rs b/src/tools/rust-analyzer/crates/hir-ty/src/tests/traits.rs
index 18fc8afd183..fb07e718d10 100644
--- a/src/tools/rust-analyzer/crates/hir-ty/src/tests/traits.rs
+++ b/src/tools/rust-analyzer/crates/hir-ty/src/tests/traits.rs
@@ -4824,3 +4824,76 @@ fn foo() {
 "#,
     )
 }
+
+#[test]
+fn nested_impl_traits() {
+    check_infer(
+        r#"
+//- minicore: fn
+trait Foo {}
+
+trait Bar<T> {}
+
+trait Baz {
+    type Assoc;
+}
+
+struct Qux<T> {
+    qux: T,
+}
+
+struct S;
+
+impl Foo for S {}
+
+fn not_allowed1(f: impl Fn(impl Foo)) {
+    let foo = S;
+    f(foo);
+}
+
+// This caused stack overflow in #17498
+fn not_allowed2(f: impl Fn(&impl Foo)) {
+    let foo = S;
+    f(&foo);
+}
+
+fn not_allowed3(bar: impl Bar<impl Foo>) {}
+
+// This also caused stack overflow
+fn not_allowed4(bar: impl Bar<&impl Foo>) {}
+
+fn allowed1(baz: impl Baz<Assoc = impl Foo>) {}
+
+fn allowed2<'a>(baz: impl Baz<Assoc = &'a (impl Foo + 'a)>) {}
+
+fn allowed3(baz: impl Baz<Assoc = Qux<impl Foo>>) {}
+"#,
+        expect![[r#"
+            139..140 'f': impl Fn({unknown}) + ?Sized
+            161..193 '{     ...oo); }': ()
+            171..174 'foo': S
+            177..178 'S': S
+            184..185 'f': impl Fn({unknown}) + ?Sized
+            184..190 'f(foo)': ()
+            186..189 'foo': S
+            251..252 'f': impl Fn(&'? {unknown}) + ?Sized
+            274..307 '{     ...oo); }': ()
+            284..287 'foo': S
+            290..291 'S': S
+            297..298 'f': impl Fn(&'? {unknown}) + ?Sized
+            297..304 'f(&foo)': ()
+            299..303 '&foo': &'? S
+            300..303 'foo': S
+            325..328 'bar': impl Bar<{unknown}> + ?Sized
+            350..352 '{}': ()
+            405..408 'bar': impl Bar<&'? {unknown}> + ?Sized
+            431..433 '{}': ()
+            447..450 'baz': impl Baz<Assoc = impl Foo + ?Sized> + ?Sized
+            480..482 '{}': ()
+            500..503 'baz': impl Baz<Assoc = &'a impl Foo + 'a + ?Sized> + ?Sized
+            544..546 '{}': ()
+            560..563 'baz': impl Baz<Assoc = Qux<impl Foo + ?Sized>> + ?Sized
+            598..600 '{}': ()
+        "#]],
+    )
+}