Forbid impl Trait from referring to unnamable recursive types

There is no type T, such that `T = [T; 2]`, we should not allow this
to be circumvented by impl Trait.

7 files changed, 340 insertions, 11 deletions

diff --git a/src/librustc/ty/util.rs b/src/librustc/ty/util.rs
index ac062a23786..e989ef823e9 100644
--- a/src/librustc/ty/util.rs
+++ b/src/librustc/ty/util.rs
@@ -7,7 +7,7 @@ use hir::{self, Node};
 use ich::NodeIdHashingMode;
 use traits::{self, ObligationCause};
 use ty::{self, Ty, TyCtxt, GenericParamDefKind, TypeFoldable};
-use ty::subst::{Substs, UnpackedKind};
+use ty::subst::{Subst, Substs, UnpackedKind};
 use ty::query::TyCtxtAt;
 use ty::TyKind::*;
 use ty::layout::{Integer, IntegerExt};
@@ -15,7 +15,7 @@ use util::common::ErrorReported;
 use middle::lang_items;
 
 use rustc_data_structures::stable_hasher::{StableHasher, HashStable};
-use rustc_data_structures::fx::FxHashMap;
+use rustc_data_structures::fx::{FxHashMap, FxHashSet};
 use std::{cmp, fmt};
 use syntax::ast;
 use syntax::attr::{self, SignedInt, UnsignedInt};
@@ -618,6 +618,76 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
             }
         }
     }
+
+    /// Expands the given impl trait type, stopping if the type is recursive.
+    pub fn try_expand_impl_trait_type(
+        self,
+        def_id: DefId,
+        substs: &'tcx Substs<'tcx>,
+    ) -> Result<Ty<'tcx>, Ty<'tcx>> {
+        use crate::ty::fold::TypeFolder;
+
+        struct OpaqueTypeExpander<'a, 'gcx, 'tcx> {
+            // Contains the DefIds of the opaque types that are currently being
+            // expanded. When we expand an opaque type we insert the DefId of
+            // that type, and when we finish expanding that type we remove the
+            // its DefId.
+            seen_opaque_tys: FxHashSet<DefId>,
+            primary_def_id: DefId,
+            found_recursion: bool,
+            tcx: TyCtxt<'a, 'gcx, 'tcx>,
+        }
+
+        impl<'a, 'gcx, 'tcx> OpaqueTypeExpander<'a, 'gcx, 'tcx> {
+            fn expand_opaque_ty(
+                &mut self,
+                def_id: DefId,
+                substs: &'tcx Substs<'tcx>,
+            ) -> Option<Ty<'tcx>> {
+                if self.found_recursion {
+                    None
+                } else if self.seen_opaque_tys.insert(def_id) {
+                    let generic_ty = self.tcx.type_of(def_id);
+                    let concrete_ty = generic_ty.subst(self.tcx, substs);
+                    let expanded_ty = self.fold_ty(concrete_ty);
+                    self.seen_opaque_tys.remove(&def_id);
+                    Some(expanded_ty)
+                } else {
+                    // If another opaque type that we contain is recursive, then it
+                    // will report the error, so we don't have to.
+                    self.found_recursion = def_id == self.primary_def_id;
+                    None
+                }
+            }
+        }
+
+        impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for OpaqueTypeExpander<'a, 'gcx, 'tcx> {
+            fn tcx(&self) -> TyCtxt<'_, 'gcx, 'tcx> {
+                self.tcx
+            }
+
+            fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
+                if let ty::Opaque(def_id, substs) = t.sty {
+                    self.expand_opaque_ty(def_id, substs).unwrap_or(t)
+                } else {
+                    t.super_fold_with(self)
+                }
+            }
+        }
+
+        let mut visitor = OpaqueTypeExpander {
+            seen_opaque_tys: FxHashSet::default(),
+            primary_def_id: def_id,
+            found_recursion: false,
+            tcx: self,
+        };
+        let expanded_type = visitor.expand_opaque_ty(def_id, substs).unwrap();
+        if visitor.found_recursion {
+            Err(expanded_type)
+        } else {
+            Ok(expanded_type)
+        }
+    }
 }
 
 impl<'a, 'tcx> ty::TyS<'tcx> {
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index d78d7273a36..8262c306796 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -1305,6 +1305,27 @@ fn check_union<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
     check_packed(tcx, span, def_id);
 }
 
+fn check_opaque<'a, 'tcx>(
+    tcx: TyCtxt<'a, 'tcx, 'tcx>,
+    def_id: DefId,
+    substs: &'tcx Substs<'tcx>,
+    span: Span,
+) {
+    if let Err(partially_expanded_type) = tcx.try_expand_impl_trait_type(def_id, substs) {
+        let mut err = struct_span_err!(
+            tcx.sess, span, E0720,
+            "opaque type expands to a recursive type",
+        );
+        err.span_label(span, "expands to self-referential type");
+        if let ty::Opaque(..) = partially_expanded_type.sty {
+            err.note("type resolves to itself");
+        } else {
+            err.note(&format!("expanded type is `{}`", partially_expanded_type));
+        }
+        err.emit();
+    }
+}
+
 pub fn check_item_type<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, it: &'tcx hir::Item) {
     debug!(
         "check_item_type(it.id={}, it.name={})",
@@ -1351,7 +1372,16 @@ pub fn check_item_type<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, it: &'tcx hir::Ite
         hir::ItemKind::Union(..) => {
             check_union(tcx, it.id, it.span);
         }
-        hir::ItemKind::Existential(..) | hir::ItemKind::Ty(..) => {
+        hir::ItemKind::Existential(..) => {
+            let def_id = tcx.hir().local_def_id(it.id);
+            let pty_ty = tcx.type_of(def_id);
+            let generics = tcx.generics_of(def_id);
+
+            check_bounds_are_used(tcx, &generics, pty_ty);
+            let substs = Substs::identity_for_item(tcx, def_id);
+            check_opaque(tcx, def_id, substs, it.span);
+        }
+        hir::ItemKind::Ty(..) => {
             let def_id = tcx.hir().local_def_id(it.id);
             let pty_ty = tcx.type_of(def_id);
             let generics = tcx.generics_of(def_id);
diff --git a/src/librustc_typeck/diagnostics.rs b/src/librustc_typeck/diagnostics.rs
index 5910a8b3110..387dabe747a 100644
--- a/src/librustc_typeck/diagnostics.rs
+++ b/src/librustc_typeck/diagnostics.rs
@@ -4816,6 +4816,21 @@ type, it's not allowed to override anything in those implementations, as it
 would be ambiguous which override should actually be used.
 "##,
 
+
+E0720: r##"
+An `impl Trait` type expands to a recursive type.
+
+An `impl Trait` type must be expandable to a concrete type that contains no
+`impl Trait` types. For example the following example tries to create an
+`impl Trait` type `T` that is equal to `[T, T]`:
+
+```compile_fail,E0720
+fn make_recursive_type() -> impl Sized {
+    [make_recursive_type(), make_recursive_type()]
+}
+```
+"##,
+
 }
 
 register_diagnostics! {
diff --git a/src/test/ui/impl-trait/infinite-impl-trait-issue-38064.rs b/src/test/ui/impl-trait/infinite-impl-trait-issue-38064.rs
index c84e5883bb2..150a8015cbc 100644
--- a/src/test/ui/impl-trait/infinite-impl-trait-issue-38064.rs
+++ b/src/test/ui/impl-trait/infinite-impl-trait-issue-38064.rs
@@ -3,17 +3,15 @@
 //
 // Regression test for #38064.
 
-// error-pattern:overflow evaluating the requirement `impl Quux`
-
 trait Quux {}
 
-fn foo() -> impl Quux {
+fn foo() -> impl Quux { //~ opaque type expands to a recursive type
     struct Foo<T>(T);
     impl<T> Quux for Foo<T> {}
     Foo(bar())
 }
 
-fn bar() -> impl Quux {
+fn bar() -> impl Quux { //~ opaque type expands to a recursive type
     struct Bar<T>(T);
     impl<T> Quux for Bar<T> {}
     Bar(foo())
diff --git a/src/test/ui/impl-trait/infinite-impl-trait-issue-38064.stderr b/src/test/ui/impl-trait/infinite-impl-trait-issue-38064.stderr
index f260cce647b..99c8fe35c66 100644
--- a/src/test/ui/impl-trait/infinite-impl-trait-issue-38064.stderr
+++ b/src/test/ui/impl-trait/infinite-impl-trait-issue-38064.stderr
@@ -1,7 +1,19 @@
-error[E0275]: overflow evaluating the requirement `impl Quux`
+error[E0720]: opaque type expands to a recursive type
+  --> $DIR/infinite-impl-trait-issue-38064.rs:8:13
    |
-   = help: consider adding a `#![recursion_limit="128"]` attribute to your crate
+LL | fn foo() -> impl Quux { //~ opaque type expands to a recursive type
+   |             ^^^^^^^^^ expands to self-referential type
+   |
+   = note: expanded type is `foo::Foo<bar::Bar<impl Quux>>`
+
+error[E0720]: opaque type expands to a recursive type
+  --> $DIR/infinite-impl-trait-issue-38064.rs:14:13
+   |
+LL | fn bar() -> impl Quux { //~ opaque type expands to a recursive type
+   |             ^^^^^^^^^ expands to self-referential type
+   |
+   = note: expanded type is `bar::Bar<foo::Foo<impl Quux>>`
 
-error: aborting due to previous error
+error: aborting due to 2 previous errors
 
-For more information about this error, try `rustc --explain E0275`.
+For more information about this error, try `rustc --explain E0720`.
diff --git a/src/test/ui/impl-trait/recursive-impl-trait-type.rs b/src/test/ui/impl-trait/recursive-impl-trait-type.rs
new file mode 100644
index 00000000000..facb191a370
--- /dev/null
+++ b/src/test/ui/impl-trait/recursive-impl-trait-type.rs
@@ -0,0 +1,81 @@
+// Test that impl trait does not allow creating recursive types that are
+// otherwise forbidden.
+
+#![feature(await_macro, async_await, futures_api, generators)]
+
+fn option(i: i32) -> impl Sized { //~ ERROR
+    if i < 0 {
+        None
+    } else {
+        Some((option(i - 1), i))
+    }
+}
+
+fn tuple() -> impl Sized { //~ ERROR
+    (tuple(),)
+}
+
+fn array() -> impl Sized { //~ ERROR
+    [array()]
+}
+
+fn ptr() -> impl Sized { //~ ERROR
+    &ptr() as *const _
+}
+
+fn fn_ptr() -> impl Sized { //~ ERROR
+    fn_ptr as fn() -> _
+}
+
+fn closure_capture() -> impl Sized { //~ ERROR
+    let x = closure_capture();
+    move || { x; }
+}
+
+fn closure_ref_capture() -> impl Sized { //~ ERROR
+    let x = closure_ref_capture();
+    move || { &x; }
+}
+
+fn closure_sig() -> impl Sized { //~ ERROR
+    || closure_sig()
+}
+
+fn generator_sig() -> impl Sized { //~ ERROR
+    || generator_sig()
+}
+
+fn generator_capture() -> impl Sized { //~ ERROR
+    let x = generator_capture();
+    move || { yield; x; }
+}
+
+fn substs_change<T>() -> impl Sized { //~ ERROR
+    (substs_change::<&T>(),)
+}
+
+fn generator_hold() -> impl Sized { //~ ERROR
+    move || {
+        let x = generator_hold();
+        yield;
+        x;
+    }
+}
+
+async fn recursive_async_function() -> () { //~ ERROR
+    await!(recursive_async_function());
+}
+
+fn use_fn_ptr() -> impl Sized { // OK, error already reported
+    fn_ptr()
+}
+
+fn mutual_recursion() -> impl Sync { //~ ERROR
+    mutual_recursion_b()
+}
+
+fn mutual_recursion_b() -> impl Sized { //~ ERROR
+    mutual_recursion()
+}
+
+fn main() {}
diff --git a/src/test/ui/impl-trait/recursive-impl-trait-type.stderr b/src/test/ui/impl-trait/recursive-impl-trait-type.stderr
new file mode 100644
index 00000000000..8a878912057
--- /dev/null
+++ b/src/test/ui/impl-trait/recursive-impl-trait-type.stderr
@@ -0,0 +1,123 @@
+error[E0720]: opaque type expands to a recursive type
+  --> $DIR/recursive-impl-trait-type.rs:6:22
+   |
+LL | fn option(i: i32) -> impl Sized { //~ ERROR
+   |                      ^^^^^^^^^^ expands to self-referential type
+   |
+   = note: expanded type is `std::option::Option<(impl Sized, i32)>`
+
+error[E0720]: opaque type expands to a recursive type
+  --> $DIR/recursive-impl-trait-type.rs:14:15
+   |
+LL | fn tuple() -> impl Sized { //~ ERROR
+   |               ^^^^^^^^^^ expands to self-referential type
+   |
+   = note: expanded type is `(impl Sized,)`
+
+error[E0720]: opaque type expands to a recursive type
+  --> $DIR/recursive-impl-trait-type.rs:18:15
+   |
+LL | fn array() -> impl Sized { //~ ERROR
+   |               ^^^^^^^^^^ expands to self-referential type
+   |
+   = note: expanded type is `[impl Sized; 1]`
+
+error[E0720]: opaque type expands to a recursive type
+  --> $DIR/recursive-impl-trait-type.rs:22:13
+   |
+LL | fn ptr() -> impl Sized { //~ ERROR
+   |             ^^^^^^^^^^ expands to self-referential type
+   |
+   = note: expanded type is `*const impl Sized`
+
+error[E0720]: opaque type expands to a recursive type
+  --> $DIR/recursive-impl-trait-type.rs:26:16
+   |
+LL | fn fn_ptr() -> impl Sized { //~ ERROR
+   |                ^^^^^^^^^^ expands to self-referential type
+   |
+   = note: expanded type is `fn() -> impl Sized`
+
+error[E0720]: opaque type expands to a recursive type
+  --> $DIR/recursive-impl-trait-type.rs:30:25
+   |
+LL | fn closure_capture() -> impl Sized { //~ ERROR
+   |                         ^^^^^^^^^^ expands to self-referential type
+   |
+   = note: expanded type is `[closure@$DIR/recursive-impl-trait-type.rs:32:5: 32:19 x:impl Sized]`
+
+error[E0720]: opaque type expands to a recursive type
+  --> $DIR/recursive-impl-trait-type.rs:35:29
+   |
+LL | fn closure_ref_capture() -> impl Sized { //~ ERROR
+   |                             ^^^^^^^^^^ expands to self-referential type
+   |
+   = note: expanded type is `[closure@$DIR/recursive-impl-trait-type.rs:37:5: 37:20 x:impl Sized]`
+
+error[E0720]: opaque type expands to a recursive type
+  --> $DIR/recursive-impl-trait-type.rs:40:21
+   |
+LL | fn closure_sig() -> impl Sized { //~ ERROR
+   |                     ^^^^^^^^^^ expands to self-referential type
+   |
+   = note: expanded type is `[closure@$DIR/recursive-impl-trait-type.rs:41:5: 41:21]`
+
+error[E0720]: opaque type expands to a recursive type
+  --> $DIR/recursive-impl-trait-type.rs:44:23
+   |
+LL | fn generator_sig() -> impl Sized { //~ ERROR
+   |                       ^^^^^^^^^^ expands to self-referential type
+   |
+   = note: expanded type is `[closure@$DIR/recursive-impl-trait-type.rs:45:5: 45:23]`
+
+error[E0720]: opaque type expands to a recursive type
+  --> $DIR/recursive-impl-trait-type.rs:48:27
+   |
+LL | fn generator_capture() -> impl Sized { //~ ERROR
+   |                           ^^^^^^^^^^ expands to self-referential type
+   |
+   = note: expanded type is `[generator@$DIR/recursive-impl-trait-type.rs:50:5: 50:26 x:impl Sized {()}]`
+
+error[E0720]: opaque type expands to a recursive type
+  --> $DIR/recursive-impl-trait-type.rs:53:26
+   |
+LL | fn substs_change<T>() -> impl Sized { //~ ERROR
+   |                          ^^^^^^^^^^ expands to self-referential type
+   |
+   = note: expanded type is `(impl Sized,)`
+
+error[E0720]: opaque type expands to a recursive type
+  --> $DIR/recursive-impl-trait-type.rs:57:24
+   |
+LL | fn generator_hold() -> impl Sized { //~ ERROR
+   |                        ^^^^^^^^^^ expands to self-referential type
+   |
+   = note: expanded type is `[generator@$DIR/recursive-impl-trait-type.rs:58:5: 62:6 {impl Sized, ()}]`
+
+error[E0720]: opaque type expands to a recursive type
+  --> $DIR/recursive-impl-trait-type.rs:65:40
+   |
+LL | async fn recursive_async_function() -> () { //~ ERROR
+   |                                        ^^ expands to self-referential type
+   |
+   = note: expanded type is `std::future::GenFuture<[static generator@$DIR/recursive-impl-trait-type.rs:65:43: 67:2 {impl std::future::Future, ()}]>`
+
+error[E0720]: opaque type expands to a recursive type
+  --> $DIR/recursive-impl-trait-type.rs:73:26
+   |
+LL | fn mutual_recursion() -> impl Sync { //~ ERROR
+   |                          ^^^^^^^^^ expands to self-referential type
+   |
+   = note: type resolves to itself
+
+error[E0720]: opaque type expands to a recursive type
+  --> $DIR/recursive-impl-trait-type.rs:77:28
+   |
+LL | fn mutual_recursion_b() -> impl Sized { //~ ERROR
+   |                            ^^^^^^^^^^ expands to self-referential type
+   |
+   = note: type resolves to itself
+
+error: aborting due to 15 previous errors
+
+For more information about this error, try `rustc --explain E0720`.