Consider outlives assumptions when proving auto traits for coroutine interiors

6 files changed, 95 insertions, 6 deletions

diff --git a/compiler/rustc_infer/src/infer/canonical/query_response.rs b/compiler/rustc_infer/src/infer/canonical/query_response.rs
index d5d49e3188a..fed56976128 100644
--- a/compiler/rustc_infer/src/infer/canonical/query_response.rs
+++ b/compiler/rustc_infer/src/infer/canonical/query_response.rs
@@ -116,9 +116,15 @@ impl<'tcx> InferCtxt<'tcx> {
         }
 
         let region_obligations = self.take_registered_region_obligations();
+        let region_assumptions = self.take_registered_region_assumptions();
         debug!(?region_obligations);
         let region_constraints = self.with_region_constraints(|region_constraints| {
-            make_query_region_constraints(tcx, region_obligations, region_constraints)
+            make_query_region_constraints(
+                tcx,
+                region_obligations,
+                region_constraints,
+                region_assumptions,
+            )
         });
         debug!(?region_constraints);
 
@@ -169,6 +175,11 @@ impl<'tcx> InferCtxt<'tcx> {
             self.register_outlives_constraint(predicate, cause);
         }
 
+        for assumption in &query_response.value.region_constraints.assumptions {
+            let assumption = instantiate_value(self.tcx, &result_args, *assumption);
+            self.register_region_assumption(assumption);
+        }
+
         let user_result: R =
             query_response.instantiate_projected(self.tcx, &result_args, |q_r| q_r.value.clone());
 
@@ -292,6 +303,18 @@ impl<'tcx> InferCtxt<'tcx> {
             }),
         );
 
+        // FIXME(higher_ranked_auto): Optimize this to instantiate all assumptions
+        // at once, rather than calling `instantiate_value` repeatedly which may
+        // create more universes.
+        output_query_region_constraints.assumptions.extend(
+            query_response
+                .value
+                .region_constraints
+                .assumptions
+                .iter()
+                .map(|&r_c| instantiate_value(self.tcx, &result_args, r_c)),
+        );
+
         let user_result: R =
             query_response.instantiate_projected(self.tcx, &result_args, |q_r| q_r.value.clone());
 
@@ -567,6 +590,7 @@ pub fn make_query_region_constraints<'tcx>(
     tcx: TyCtxt<'tcx>,
     outlives_obligations: Vec<TypeOutlivesConstraint<'tcx>>,
     region_constraints: &RegionConstraintData<'tcx>,
+    assumptions: Vec<ty::OutlivesPredicate<'tcx, ty::GenericArg<'tcx>>>,
 ) -> QueryRegionConstraints<'tcx> {
     let RegionConstraintData { constraints, verifys } = region_constraints;
 
@@ -602,5 +626,5 @@ pub fn make_query_region_constraints<'tcx>(
         }))
         .collect();
 
-    QueryRegionConstraints { outlives }
+    QueryRegionConstraints { outlives, assumptions }
 }
diff --git a/compiler/rustc_infer/src/infer/mod.rs b/compiler/rustc_infer/src/infer/mod.rs
index cc3ad921489..458b21da6ce 100644
--- a/compiler/rustc_infer/src/infer/mod.rs
+++ b/compiler/rustc_infer/src/infer/mod.rs
@@ -149,6 +149,13 @@ pub struct InferCtxtInner<'tcx> {
     /// that all type inference variables have been bound and so forth.
     region_obligations: Vec<TypeOutlivesConstraint<'tcx>>,
 
+    /// The outlives bounds that we assume must hold about placeholders that
+    /// come from instantiating the binder of coroutine-witnesses. These bounds
+    /// are deduced from the well-formedness of the witness's types, and are
+    /// necessary because of the way we anonymize the regions in a coroutine,
+    /// which may cause types to no longer be considered well-formed.
+    region_assumptions: Vec<ty::OutlivesPredicate<'tcx, ty::GenericArg<'tcx>>>,
+
     /// Caches for opaque type inference.
     opaque_type_storage: OpaqueTypeStorage<'tcx>,
 }
@@ -164,7 +171,8 @@ impl<'tcx> InferCtxtInner<'tcx> {
             int_unification_storage: Default::default(),
             float_unification_storage: Default::default(),
             region_constraint_storage: Some(Default::default()),
-            region_obligations: vec![],
+            region_obligations: Default::default(),
+            region_assumptions: Default::default(),
             opaque_type_storage: Default::default(),
         }
     }
@@ -175,6 +183,11 @@ impl<'tcx> InferCtxtInner<'tcx> {
     }
 
     #[inline]
+    pub fn region_assumptions(&self) -> &[ty::OutlivesPredicate<'tcx, ty::GenericArg<'tcx>>] {
+        &self.region_assumptions
+    }
+
+    #[inline]
     pub fn projection_cache(&mut self) -> traits::ProjectionCache<'_, 'tcx> {
         self.projection_cache.with_log(&mut self.undo_log)
     }
diff --git a/compiler/rustc_infer/src/infer/outlives/env.rs b/compiler/rustc_infer/src/infer/outlives/env.rs
index cb5a33c5c97..2175ff1b4ae 100644
--- a/compiler/rustc_infer/src/infer/outlives/env.rs
+++ b/compiler/rustc_infer/src/infer/outlives/env.rs
@@ -1,4 +1,4 @@
-use rustc_data_structures::fx::FxIndexSet;
+use rustc_data_structures::fx::{FxHashSet, FxIndexSet};
 use rustc_data_structures::transitive_relation::TransitiveRelationBuilder;
 use rustc_middle::{bug, ty};
 use tracing::debug;
@@ -39,6 +39,9 @@ pub struct OutlivesEnvironment<'tcx> {
     /// optimized in the future, though.
     region_bound_pairs: RegionBoundPairs<'tcx>,
     known_type_outlives: Vec<ty::PolyTypeOutlivesPredicate<'tcx>>,
+    /// Assumptions that come from the well-formedness of coroutines that we prove
+    /// auto trait bounds for during the type checking of this body.
+    higher_ranked_assumptions: FxHashSet<ty::OutlivesPredicate<'tcx, ty::GenericArg<'tcx>>>,
 }
 
 /// "Region-bound pairs" tracks outlives relations that are known to
@@ -52,6 +55,7 @@ impl<'tcx> OutlivesEnvironment<'tcx> {
         param_env: ty::ParamEnv<'tcx>,
         known_type_outlives: Vec<ty::PolyTypeOutlivesPredicate<'tcx>>,
         extra_bounds: impl IntoIterator<Item = OutlivesBound<'tcx>>,
+        higher_ranked_assumptions: FxHashSet<ty::OutlivesPredicate<'tcx, ty::GenericArg<'tcx>>>,
     ) -> Self {
         let mut region_relation = TransitiveRelationBuilder::default();
         let mut region_bound_pairs = RegionBoundPairs::default();
@@ -88,6 +92,7 @@ impl<'tcx> OutlivesEnvironment<'tcx> {
             known_type_outlives,
             free_region_map: FreeRegionMap { relation: region_relation.freeze() },
             region_bound_pairs,
+            higher_ranked_assumptions,
         }
     }
 
@@ -102,4 +107,10 @@ impl<'tcx> OutlivesEnvironment<'tcx> {
     pub fn known_type_outlives(&self) -> &[ty::PolyTypeOutlivesPredicate<'tcx>] {
         &self.known_type_outlives
     }
+
+    pub fn higher_ranked_assumptions(
+        &self,
+    ) -> &FxHashSet<ty::OutlivesPredicate<'tcx, ty::GenericArg<'tcx>>> {
+        &self.higher_ranked_assumptions
+    }
 }
diff --git a/compiler/rustc_infer/src/infer/outlives/mod.rs b/compiler/rustc_infer/src/infer/outlives/mod.rs
index 2a4544c1140..db668032f1f 100644
--- a/compiler/rustc_infer/src/infer/outlives/mod.rs
+++ b/compiler/rustc_infer/src/infer/outlives/mod.rs
@@ -10,6 +10,7 @@ use super::region_constraints::{RegionConstraintData, UndoLog};
 use super::{InferCtxt, RegionResolutionError, SubregionOrigin};
 use crate::infer::free_regions::RegionRelations;
 use crate::infer::lexical_region_resolve;
+use crate::infer::region_constraints::Constraint;
 
 pub mod env;
 pub mod for_liveness;
@@ -54,18 +55,27 @@ impl<'tcx> InferCtxt<'tcx> {
             }
         };
 
-        let storage = {
+        let mut storage = {
             let mut inner = self.inner.borrow_mut();
             let inner = &mut *inner;
             assert!(
                 self.tainted_by_errors().is_some() || inner.region_obligations.is_empty(),
                 "region_obligations not empty: {:#?}",
-                inner.region_obligations
+                inner.region_obligations,
             );
             assert!(!UndoLogs::<UndoLog<'_>>::in_snapshot(&inner.undo_log));
             inner.region_constraint_storage.take().expect("regions already resolved")
         };
 
+        // Filter out any region-region outlives assumptions that are implied by
+        // coroutine well-formedness.
+        storage.data.constraints.retain(|(constraint, _)| match *constraint {
+            Constraint::RegSubReg(r1, r2) => !outlives_env
+                .higher_ranked_assumptions()
+                .contains(&ty::OutlivesPredicate(r2.into(), r1)),
+            _ => true,
+        });
+
         let region_rels = &RegionRelations::new(self.tcx, outlives_env.free_region_map());
 
         let (lexical_region_resolutions, errors) =
@@ -93,6 +103,11 @@ impl<'tcx> InferCtxt<'tcx> {
             "region_obligations not empty: {:#?}",
             self.inner.borrow().region_obligations
         );
+        assert!(
+            self.inner.borrow().region_assumptions.is_empty(),
+            "region_assumptions not empty: {:#?}",
+            self.inner.borrow().region_assumptions
+        );
 
         self.inner.borrow_mut().unwrap_region_constraints().take_and_reset_data()
     }
diff --git a/compiler/rustc_infer/src/infer/outlives/obligations.rs b/compiler/rustc_infer/src/infer/outlives/obligations.rs
index 43504bd77c1..2066cdd717e 100644
--- a/compiler/rustc_infer/src/infer/outlives/obligations.rs
+++ b/compiler/rustc_infer/src/infer/outlives/obligations.rs
@@ -170,6 +170,21 @@ impl<'tcx> InferCtxt<'tcx> {
         std::mem::take(&mut self.inner.borrow_mut().region_obligations)
     }
 
+    pub fn register_region_assumption(
+        &self,
+        assumption: ty::OutlivesPredicate<'tcx, ty::GenericArg<'tcx>>,
+    ) {
+        let mut inner = self.inner.borrow_mut();
+        inner.undo_log.push(UndoLog::PushRegionAssumption);
+        inner.region_assumptions.push(assumption);
+    }
+
+    pub fn take_registered_region_assumptions(
+        &self,
+    ) -> Vec<ty::OutlivesPredicate<'tcx, ty::GenericArg<'tcx>>> {
+        std::mem::take(&mut self.inner.borrow_mut().region_assumptions)
+    }
+
     /// Process the region obligations that must be proven (during
     /// `regionck`) for the given `body_id`, given information about
     /// the region bounds in scope and so forth.
@@ -220,6 +235,13 @@ impl<'tcx> InferCtxt<'tcx> {
                 let (sup_type, sub_region) =
                     (sup_type, sub_region).fold_with(&mut OpportunisticRegionResolver::new(self));
 
+                if outlives_env
+                    .higher_ranked_assumptions()
+                    .contains(&ty::OutlivesPredicate(sup_type.into(), sub_region))
+                {
+                    continue;
+                }
+
                 debug!(?sup_type, ?sub_region, ?origin);
 
                 let outlives = &mut TypeOutlives::new(
diff --git a/compiler/rustc_infer/src/infer/snapshot/undo_log.rs b/compiler/rustc_infer/src/infer/snapshot/undo_log.rs
index 34e649afedc..40e4c329446 100644
--- a/compiler/rustc_infer/src/infer/snapshot/undo_log.rs
+++ b/compiler/rustc_infer/src/infer/snapshot/undo_log.rs
@@ -28,6 +28,7 @@ pub(crate) enum UndoLog<'tcx> {
     RegionUnificationTable(sv::UndoLog<ut::Delegate<RegionVidKey<'tcx>>>),
     ProjectionCache(traits::UndoLog<'tcx>),
     PushTypeOutlivesConstraint,
+    PushRegionAssumption,
 }
 
 macro_rules! impl_from {
@@ -77,6 +78,9 @@ impl<'tcx> Rollback<UndoLog<'tcx>> for InferCtxtInner<'tcx> {
                 let popped = self.region_obligations.pop();
                 assert_matches!(popped, Some(_), "pushed region constraint but could not pop it");
             }
+            UndoLog::PushRegionAssumption => {
+                self.region_assumptions.pop();
+            }
         }
     }
 }