Rollup merge of #61488 - matthewjasper:fix-nll-typeck-ices, r=pnkfelix

Fix NLL typeck ICEs

* Don't ICE when a type containing a region is constrained by nothing
* Don't ICE trying to normalize a type in a `ParamEnv` containing global bounds.

To explain what was happening in the `issue-61311-normalize.rs` case:

* When borrow checking the `the_fn` in the last `impl` we would try to normalize `Self::Proj` (`<Unit as HasProjFn>::Proj`).
* We would find the `impl` that we're checking and and check its `where` clause.
* This would need us to check `<Box<dyn Obj + 'static> as HasProj>::Proj: Bound`
* We find two possible implementations, the blanket impl and the bound in our `ParamEnv`.
* The bound in our `ParamEnv` was canonicalized, so we don't see it as a global bound. As such we prefer it to the `impl`.
* This means that we cannot normalize `<Box<dyn Obj + 'static> as HasProj>::Proj` to `Unit`.
* The `<Box<dyn Obj + 'static> as HasProj>::Proj: Bound` bound, which looks like it should be in our `ParamEnv` has been normalized to `Unit: Bound`.
* We fail to prove `<Box<dyn Obj + 'static> as HasProj>::Proj: Bound`.
* We ICE, since we believe typeck have errored.

Closes #61311
Closes #61315
Closes #61320

r? @pnkfelix
cc @nikomatsakis

6 files changed, 222 insertions, 4 deletions

diff --git a/src/librustc/infer/canonical/canonicalizer.rs b/src/librustc/infer/canonical/canonicalizer.rs
index 0e9dbcac5cd..ae4bfcaa903 100644
--- a/src/librustc/infer/canonical/canonicalizer.rs
+++ b/src/librustc/infer/canonical/canonicalizer.rs
@@ -115,13 +115,17 @@ impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
 
     /// A hacky variant of `canonicalize_query` that does not
     /// canonicalize `'static`. Unfortunately, the existing leak
-    /// check treaks `'static` differently in some cases (see also
+    /// check treats `'static` differently in some cases (see also
     /// #33684), so if we are performing an operation that may need to
     /// prove "leak-check" related things, we leave `'static`
     /// alone.
+    ///
+    /// `'static` is also special cased when winnowing candidates when
+    /// selecting implementation candidates, so we also have to leave `'static`
+    /// alone for queries that do selection.
     //
-    // FIXME(#48536): once we have universes, we can remove this and just use
-    // `canonicalize_query`.
+    // FIXME(#48536): once the above issues are resolved, we can remove this
+    // and just use `canonicalize_query`.
     pub fn canonicalize_hr_query_hack<V>(
         &self,
         value: &V,
diff --git a/src/librustc/traits/query/normalize.rs b/src/librustc/traits/query/normalize.rs
index d09a9c10786..0b20ec884fc 100644
--- a/src/librustc/traits/query/normalize.rs
+++ b/src/librustc/traits/query/normalize.rs
@@ -145,7 +145,9 @@ impl<'cx, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for QueryNormalizer<'cx, 'gcx, 'tcx
                 let gcx = self.infcx.tcx.global_tcx();
 
                 let mut orig_values = OriginalQueryValues::default();
-                let c_data = self.infcx.canonicalize_query(
+                // HACK(matthewjasper) `'static` is special-cased in selection,
+                // so we cannot canonicalize it.
+                let c_data = self.infcx.canonicalize_hr_query_hack(
                     &self.param_env.and(*data), &mut orig_values);
                 debug!("QueryNormalizer: c_data = {:#?}", c_data);
                 debug!("QueryNormalizer: orig_values = {:#?}", orig_values);
diff --git a/src/librustc_mir/borrow_check/nll/type_check/free_region_relations.rs b/src/librustc_mir/borrow_check/nll/type_check/free_region_relations.rs
index 3b663ef6dad..361353f8df4 100644
--- a/src/librustc_mir/borrow_check/nll/type_check/free_region_relations.rs
+++ b/src/librustc_mir/borrow_check/nll/type_check/free_region_relations.rs
@@ -334,6 +334,13 @@ impl UniversalRegionRelationsBuilder<'cx, 'gcx, 'tcx> {
 
             match outlives_bound {
                 OutlivesBound::RegionSubRegion(r1, r2) => {
+                    // `where Type:` is lowered to `where Type: 'empty` so that
+                    // we check `Type` is well formed, but there's no use for
+                    // this bound here.
+                    if let ty::ReEmpty = r1 {
+                        return;
+                    }
+
                     // The bound says that `r1 <= r2`; we store `r2: r1`.
                     let r1 = self.universal_regions.to_region_vid(r1);
                     let r2 = self.universal_regions.to_region_vid(r2);
diff --git a/src/test/ui/nll/empty-type-predicate.rs b/src/test/ui/nll/empty-type-predicate.rs
new file mode 100644
index 00000000000..75431d40ce5
--- /dev/null
+++ b/src/test/ui/nll/empty-type-predicate.rs
@@ -0,0 +1,11 @@
+// Regression test for #61315
+//
+// `dyn T:` is lowered to `dyn T: ReEmpty` - check that we don't ICE in NLL for
+// the unexpected region.
+
+// compile-pass
+
+trait T {}
+fn f() where dyn T: {}
+
+fn main() {}
diff --git a/src/test/ui/nll/issue-61311-normalize.rs b/src/test/ui/nll/issue-61311-normalize.rs
new file mode 100644
index 00000000000..1164e9ef2d6
--- /dev/null
+++ b/src/test/ui/nll/issue-61311-normalize.rs
@@ -0,0 +1,34 @@
+// Regression test for #61311
+// We would ICE after failing to normalize `Self::Proj` in the `impl` below.
+
+// compile-pass
+
+pub struct Unit;
+trait Obj {}
+
+trait Bound {}
+impl Bound for Unit {}
+
+pub trait HasProj {
+    type Proj;
+}
+
+impl<T> HasProj for T {
+    type Proj = Unit;
+}
+
+trait HasProjFn {
+    type Proj;
+    fn the_fn(_: Self::Proj);
+}
+
+impl HasProjFn for Unit
+where
+    Box<dyn Obj + 'static>: HasProj,
+    <Box<dyn Obj + 'static> as HasProj>::Proj: Bound,
+{
+    type Proj = Unit;
+    fn the_fn(_: Self::Proj) {}
+}
+
+fn main() {}
diff --git a/src/test/ui/nll/issue-61320-normalize.rs b/src/test/ui/nll/issue-61320-normalize.rs
new file mode 100644
index 00000000000..a36ccd36113
--- /dev/null
+++ b/src/test/ui/nll/issue-61320-normalize.rs
@@ -0,0 +1,160 @@
+// Regression test for #61320
+// This is the same issue as #61311, just a larger test case.
+
+// compile-pass
+
+pub struct AndThen<A, B, F>
+where
+    A: Future,
+    B: IntoFuture,
+{
+    state: (A, B::Future, F),
+}
+
+pub struct FutureResult<T, E> {
+    inner: Option<Result<T, E>>,
+}
+
+impl<T, E> Future for FutureResult<T, E> {
+    type Item = T;
+    type Error = E;
+
+    fn poll(&mut self) -> Poll<T, E> {
+        unimplemented!()
+    }
+}
+
+pub type Poll<T, E> = Result<T, E>;
+
+impl<A, B, F> Future for AndThen<A, B, F>
+where
+    A: Future,
+    B: IntoFuture<Error = A::Error>,
+    F: FnOnce(A::Item) -> B,
+{
+    type Item = B::Item;
+    type Error = B::Error;
+
+    fn poll(&mut self) -> Poll<B::Item, B::Error> {
+        unimplemented!()
+    }
+}
+
+pub trait Future {
+    type Item;
+
+    type Error;
+
+    fn poll(&mut self) -> Poll<Self::Item, Self::Error>;
+
+    fn and_then<F, B>(self, f: F) -> AndThen<Self, B, F>
+    where
+        F: FnOnce(Self::Item) -> B,
+        B: IntoFuture<Error = Self::Error>,
+        Self: Sized,
+    {
+        unimplemented!()
+    }
+}
+
+pub trait IntoFuture {
+    /// The future that this type can be converted into.
+    type Future: Future<Item = Self::Item, Error = Self::Error>;
+
+    /// The item that the future may resolve with.
+    type Item;
+    /// The error that the future may resolve with.
+    type Error;
+
+    /// Consumes this object and produces a future.
+    fn into_future(self) -> Self::Future;
+}
+
+impl<F: Future> IntoFuture for F {
+    type Future = F;
+    type Item = F::Item;
+    type Error = F::Error;
+
+    fn into_future(self) -> F {
+        self
+    }
+}
+
+impl<F: ?Sized + Future> Future for ::std::boxed::Box<F> {
+    type Item = F::Item;
+    type Error = F::Error;
+
+    fn poll(&mut self) -> Poll<Self::Item, Self::Error> {
+        (**self).poll()
+    }
+}
+
+impl<T, E> IntoFuture for Result<T, E> {
+    type Future = FutureResult<T, E>;
+    type Item = T;
+    type Error = E;
+
+    fn into_future(self) -> FutureResult<T, E> {
+        unimplemented!()
+    }
+}
+
+struct Request<T>(T);
+
+trait RequestContext {}
+impl<T> RequestContext for T {}
+struct NoContext;
+impl AsRef<NoContext> for NoContext {
+    fn as_ref(&self) -> &Self {
+        &NoContext
+    }
+}
+
+type BoxedError = Box<dyn std::error::Error + Send + Sync>;
+type DefaultFuture<T, E> = Box<dyn Future<Item = T, Error = E> + Send>;
+
+trait Guard: Sized {
+    type Result: IntoFuture<Item = Self, Error = BoxedError>;
+    fn from_request(request: &Request<()>) -> Self::Result;
+}
+
+trait FromRequest: Sized {
+    type Context;
+    type Future: Future<Item = Self, Error = BoxedError> + Send;
+    fn from_request(request: Request<()>) -> Self::Future;
+}
+
+struct MyGuard;
+impl Guard for MyGuard {
+    type Result = Result<Self, BoxedError>;
+    fn from_request(_request: &Request<()>) -> Self::Result {
+        Ok(MyGuard)
+    }
+}
+
+struct Generic<I> {
+    _inner: I,
+}
+
+impl<I> FromRequest for Generic<I>
+where
+    MyGuard: Guard,
+    <MyGuard as Guard>::Result: IntoFuture<Item = MyGuard, Error = BoxedError>,
+    <<MyGuard as Guard>::Result as IntoFuture>::Future: Send,
+    I: FromRequest<Context = NoContext>,
+{
+    type Future = DefaultFuture<Self, BoxedError>;
+    type Context = NoContext;
+    fn from_request(headers: Request<()>) -> DefaultFuture<Self, BoxedError> {
+        let _future = <MyGuard as Guard>::from_request(&headers)
+            .into_future()
+            .and_then(move |_| {
+                <I as FromRequest>::from_request(headers)
+                    .into_future()
+                    .and_then(move |fld_inner| Ok(Generic { _inner: fld_inner }).into_future())
+            });
+        panic!();
+    }
+}
+
+fn main() {}