Fix coherence checking for impl trait in type aliases

Fixes #63677

RFC #2071 (impl-trait-existential-types) does not explicitly state how
impl trait type alises should interact with coherence. However, there's
only one choice which makes sense - coherence should look at the
underlying type (i.e. the 'defining' type of the impl trait) of the type
alias, just like we do for non-impl-trait type aliases.

Specifically, impl trait type alises which resolve to a local type
should be treated like a local type with respect to coherence (e.g.
impl trait type aliases which resolve to a forieign type should be
treated as a foreign type, and those that resolve to a local type should
be treated as a local type).

Since neither inherent impls nor direct trait impl (i.e. `impl MyType`
or `impl MyTrait for MyType`) are allowd for type aliases, this
usually does not come up. Before we ever attempt to do coherence
checking, we will have errored out if an impl trait type alias was used
directly in an 'impl' clause.

However, during trait selection, we sometimes need to prove bounds like
'T: Sized' for some type 'T'. If 'T' is an impl trait type alias, this
requires to know the coherence behavior for impl trait type aliases when
we perform coherence checking.

Note: Since determining the underlying type of an impl trait type alias
requires us to perform body type checking, this commit causes us to type
check some bodies easlier than we otherwise would have. However, since
this is done through a query, this shouldn't cause any problems

For completeness, I've added an additional test of the coherence-related
behavior of impl trait type aliases.

6 files changed, 63 insertions, 6 deletions

diff --git a/src/librustc/traits/coherence.rs b/src/librustc/traits/coherence.rs
index b6f0addd771..ee318b127ae 100644
--- a/src/librustc/traits/coherence.rs
+++ b/src/librustc/traits/coherence.rs
@@ -432,7 +432,7 @@ fn orphan_check_trait_ref<'tcx>(
 }
 
 fn uncovered_tys<'tcx>(tcx: TyCtxt<'_>, ty: Ty<'tcx>, in_crate: InCrate) -> Vec<Ty<'tcx>> {
-    if ty_is_local_constructor(ty, in_crate) {
+    if ty_is_local_constructor(tcx, ty, in_crate) {
         vec![]
     } else if fundamental_ty(ty) {
         ty.walk_shallow()
@@ -451,7 +451,7 @@ fn is_possibly_remote_type(ty: Ty<'_>, _in_crate: InCrate) -> bool {
 }
 
 fn ty_is_local(tcx: TyCtxt<'_>, ty: Ty<'_>, in_crate: InCrate) -> bool {
-    ty_is_local_constructor(ty, in_crate) ||
+    ty_is_local_constructor(tcx, ty, in_crate) ||
         fundamental_ty(ty) && ty.walk_shallow().any(|t| ty_is_local(tcx, t, in_crate))
 }
 
@@ -472,7 +472,7 @@ fn def_id_is_local(def_id: DefId, in_crate: InCrate) -> bool {
     }
 }
 
-fn ty_is_local_constructor(ty: Ty<'_>, in_crate: InCrate) -> bool {
+fn ty_is_local_constructor(tcx: TyCtxt<'_>, ty: Ty<'_>, in_crate: InCrate) -> bool {
     debug!("ty_is_local_constructor({:?})", ty);
 
     match ty.sty {
@@ -504,6 +504,15 @@ fn ty_is_local_constructor(ty: Ty<'_>, in_crate: InCrate) -> bool {
 
         ty::Adt(def, _) => def_id_is_local(def.did, in_crate),
         ty::Foreign(did) => def_id_is_local(did, in_crate),
+        ty::Opaque(did, _) => {
+            // Check the underlying type that this opaque
+            // type resolves to.
+            // This recursion will eventually terminate,
+            // since we've already managed to successfully
+            // resolve all opaque types by this point
+            let real_ty = tcx.type_of(did);
+            ty_is_local_constructor(tcx, real_ty, in_crate)
+        }
 
         ty::Dynamic(ref tt, ..) => {
             if let Some(principal) = tt.principal() {
@@ -518,8 +527,7 @@ fn ty_is_local_constructor(ty: Ty<'_>, in_crate: InCrate) -> bool {
         ty::UnnormalizedProjection(..) |
         ty::Closure(..) |
         ty::Generator(..) |
-        ty::GeneratorWitness(..) |
-        ty::Opaque(..) => {
+        ty::GeneratorWitness(..) => {
             bug!("ty_is_local invoked on unexpected type: {:?}", ty)
         }
     }
diff --git a/src/librustc/traits/specialize/specialization_graph.rs b/src/librustc/traits/specialize/specialization_graph.rs
index b43881defdb..c9a40db41df 100644
--- a/src/librustc/traits/specialize/specialization_graph.rs
+++ b/src/librustc/traits/specialize/specialization_graph.rs
@@ -395,7 +395,7 @@ impl<'tcx> Graph {
     /// The parent of a given impl, which is the `DefId` of the trait when the
     /// impl is a "specialization root".
     pub fn parent(&self, child: DefId) -> DefId {
-        *self.parent.get(&child).unwrap()
+        *self.parent.get(&child).unwrap_or_else(|| panic!("Failed to get parent for {:?}", child))
     }
 }
 
diff --git a/src/test/ui/type-alias-impl-trait/auxiliary/foreign-crate.rs b/src/test/ui/type-alias-impl-trait/auxiliary/foreign-crate.rs
new file mode 100644
index 00000000000..52802dd8fbb
--- /dev/null
+++ b/src/test/ui/type-alias-impl-trait/auxiliary/foreign-crate.rs
@@ -0,0 +1,2 @@
+pub trait ForeignTrait {}
+pub struct ForeignType<T>(pub T);
diff --git a/src/test/ui/type-alias-impl-trait/coherence.rs b/src/test/ui/type-alias-impl-trait/coherence.rs
new file mode 100644
index 00000000000..1c0f83d6c12
--- /dev/null
+++ b/src/test/ui/type-alias-impl-trait/coherence.rs
@@ -0,0 +1,17 @@
+// aux-build:foreign-crate.rs
+#![feature(type_alias_impl_trait)]
+
+extern crate foreign_crate;
+
+trait LocalTrait {}
+impl<T> LocalTrait for foreign_crate::ForeignType<T> {}
+
+type AliasOfForeignType<T> = impl LocalTrait;
+fn use_alias<T>(val: T) -> AliasOfForeignType<T> {
+    foreign_crate::ForeignType(val)
+}
+
+impl<T> foreign_crate::ForeignTrait for AliasOfForeignType<T> {}
+//~^ ERROR the type parameter `T` is not constrained by the impl trait, self type, or predicates
+
+fn main() {}
diff --git a/src/test/ui/type-alias-impl-trait/coherence.stderr b/src/test/ui/type-alias-impl-trait/coherence.stderr
new file mode 100644
index 00000000000..6ede0fa14ba
--- /dev/null
+++ b/src/test/ui/type-alias-impl-trait/coherence.stderr
@@ -0,0 +1,9 @@
+error[E0207]: the type parameter `T` is not constrained by the impl trait, self type, or predicates
+  --> $DIR/coherence.rs:14:6
+   |
+LL | impl<T> foreign_crate::ForeignTrait for AliasOfForeignType<T> {}
+   |      ^ unconstrained type parameter
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0207`.
diff --git a/src/test/ui/type-alias-impl-trait/issue-63677-type-alias-coherence.rs b/src/test/ui/type-alias-impl-trait/issue-63677-type-alias-coherence.rs
new file mode 100644
index 00000000000..28f4a85c9f2
--- /dev/null
+++ b/src/test/ui/type-alias-impl-trait/issue-63677-type-alias-coherence.rs
@@ -0,0 +1,21 @@
+// check-pass
+// Regression test for issue #63677 - ensure that
+// coherence checking can properly handle 'impl trait'
+// in type aliases
+#![feature(type_alias_impl_trait)]
+
+pub trait Trait {}
+pub struct S1<T>(T);
+pub struct S2<T>(T);
+
+pub type T1 = impl Trait;
+pub type T2 = S1<T1>;
+pub type T3 = S2<T2>;
+
+impl<T> Trait for S1<T> {}
+impl<T: Trait> S2<T> {}
+impl T3 {}
+
+pub fn use_t1() -> T1 { S1(()) }
+
+fn main() {}