Auto merge of #88811 - jackh726:issue-88446, r=nikomatsakis

Use a HashMap for UniverseInfo in mir borrowck

Fixes #88446

r? `@nikomatsakis`

6 files changed, 59 insertions, 15 deletions

diff --git a/compiler/rustc_borrowck/src/region_infer/mod.rs b/compiler/rustc_borrowck/src/region_infer/mod.rs
index b28f8ce1d8b..128faab8d72 100644
--- a/compiler/rustc_borrowck/src/region_infer/mod.rs
+++ b/compiler/rustc_borrowck/src/region_infer/mod.rs
@@ -85,7 +85,7 @@ pub struct RegionInferenceContext<'tcx> {
         FxHashMap<Location, FxHashMap<(RegionVid, RegionVid), (ConstraintCategory, Span)>>,
 
     /// Map universe indexes to information on why we created it.
-    universe_causes: IndexVec<ty::UniverseIndex, UniverseInfo<'tcx>>,
+    universe_causes: FxHashMap<ty::UniverseIndex, UniverseInfo<'tcx>>,
 
     /// Contains the minimum universe of any variable within the same
     /// SCC. We will ensure that no SCC contains values that are not
@@ -256,7 +256,7 @@ impl<'tcx> RegionInferenceContext<'tcx> {
             Location,
             FxHashMap<(RegionVid, RegionVid), (ConstraintCategory, Span)>,
         >,
-        universe_causes: IndexVec<ty::UniverseIndex, UniverseInfo<'tcx>>,
+        universe_causes: FxHashMap<ty::UniverseIndex, UniverseInfo<'tcx>>,
         type_tests: Vec<TypeTest<'tcx>>,
         liveness_constraints: LivenessValues<RegionVid>,
         elements: &Rc<RegionValueElements>,
@@ -2149,7 +2149,7 @@ impl<'tcx> RegionInferenceContext<'tcx> {
     }
 
     crate fn universe_info(&self, universe: ty::UniverseIndex) -> UniverseInfo<'tcx> {
-        self.universe_causes[universe].clone()
+        self.universe_causes[&universe].clone()
     }
 }
 
diff --git a/compiler/rustc_borrowck/src/type_check/canonical.rs b/compiler/rustc_borrowck/src/type_check/canonical.rs
index 7a8c0a3da1f..18070164e82 100644
--- a/compiler/rustc_borrowck/src/type_check/canonical.rs
+++ b/compiler/rustc_borrowck/src/type_check/canonical.rs
@@ -50,9 +50,10 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
                 None => UniverseInfo::other(),
             };
             for u in old_universe..universe {
-                let info_universe =
-                    self.borrowck_context.constraints.universe_causes.push(universe_info.clone());
-                assert_eq!(u.as_u32() + 1, info_universe.as_u32());
+                self.borrowck_context
+                    .constraints
+                    .universe_causes
+                    .insert(u + 1, universe_info.clone());
             }
         }
 
@@ -70,9 +71,12 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
         let (instantiated, _) =
             self.infcx.instantiate_canonical_with_fresh_inference_vars(span, canonical);
 
-        for _ in 0..canonical.max_universe.as_u32() {
+        for u in 0..canonical.max_universe.as_u32() {
             let info = UniverseInfo::other();
-            self.borrowck_context.constraints.universe_causes.push(info);
+            self.borrowck_context
+                .constraints
+                .universe_causes
+                .insert(ty::UniverseIndex::from_u32(u), info);
         }
 
         instantiated
diff --git a/compiler/rustc_borrowck/src/type_check/input_output.rs b/compiler/rustc_borrowck/src/type_check/input_output.rs
index 9d6f6f60a94..46d30a188ed 100644
--- a/compiler/rustc_borrowck/src/type_check/input_output.rs
+++ b/compiler/rustc_borrowck/src/type_check/input_output.rs
@@ -194,6 +194,8 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
                     b
                 }
             };
+            // Note: if we have to introduce new placeholders during normalization above, then we won't have
+            // added those universes to the universe info, which we would want in `relate_tys`.
             if let Err(terr) =
                 self.eq_types(a, b, Locations::All(span), ConstraintCategory::BoringNoLocation)
             {
diff --git a/compiler/rustc_borrowck/src/type_check/mod.rs b/compiler/rustc_borrowck/src/type_check/mod.rs
index 2c8ff45b00d..3e757827a5e 100644
--- a/compiler/rustc_borrowck/src/type_check/mod.rs
+++ b/compiler/rustc_borrowck/src/type_check/mod.rs
@@ -136,6 +136,8 @@ pub(crate) fn type_check<'mir, 'tcx>(
     upvars: &[Upvar<'tcx>],
 ) -> MirTypeckResults<'tcx> {
     let implicit_region_bound = infcx.tcx.mk_region(ty::ReVar(universal_regions.fr_fn_body));
+    let mut universe_causes = FxHashMap::default();
+    universe_causes.insert(ty::UniverseIndex::from_u32(0), UniverseInfo::other());
     let mut constraints = MirTypeckRegionConstraints {
         placeholder_indices: PlaceholderIndices::default(),
         placeholder_index_to_region: IndexVec::default(),
@@ -144,7 +146,7 @@ pub(crate) fn type_check<'mir, 'tcx>(
         member_constraints: MemberConstraintSet::default(),
         closure_bounds_mapping: Default::default(),
         type_tests: Vec::default(),
-        universe_causes: IndexVec::from_elem_n(UniverseInfo::other(), 1),
+        universe_causes,
     };
 
     let CreateResult {
@@ -159,9 +161,9 @@ pub(crate) fn type_check<'mir, 'tcx>(
         &mut constraints,
     );
 
-    for _ in ty::UniverseIndex::ROOT..infcx.universe() {
+    for u in ty::UniverseIndex::ROOT..infcx.universe() {
         let info = UniverseInfo::other();
-        constraints.universe_causes.push(info);
+        constraints.universe_causes.insert(u, info);
     }
 
     let mut borrowck_context = BorrowCheckContext {
@@ -924,7 +926,7 @@ crate struct MirTypeckRegionConstraints<'tcx> {
     crate closure_bounds_mapping:
         FxHashMap<Location, FxHashMap<(RegionVid, RegionVid), (ConstraintCategory, Span)>>,
 
-    crate universe_causes: IndexVec<ty::UniverseIndex, UniverseInfo<'tcx>>,
+    crate universe_causes: FxHashMap<ty::UniverseIndex, UniverseInfo<'tcx>>,
 
     crate type_tests: Vec<TypeTest<'tcx>>,
 }
diff --git a/compiler/rustc_borrowck/src/type_check/relate_tys.rs b/compiler/rustc_borrowck/src/type_check/relate_tys.rs
index 0b9c33ccb77..de86d39cc37 100644
--- a/compiler/rustc_borrowck/src/type_check/relate_tys.rs
+++ b/compiler/rustc_borrowck/src/type_check/relate_tys.rs
@@ -80,10 +80,11 @@ impl TypeRelatingDelegate<'tcx> for NllTypeRelatingDelegate<'_, '_, 'tcx> {
     }
 
     fn create_next_universe(&mut self) -> ty::UniverseIndex {
-        let info_universe =
-            self.borrowck_context.constraints.universe_causes.push(self.universe_info.clone());
         let universe = self.infcx.create_next_universe();
-        assert_eq!(info_universe, universe);
+        self.borrowck_context
+            .constraints
+            .universe_causes
+            .insert(universe, self.universe_info.clone());
         universe
     }
 
diff --git a/src/test/ui/hrtb/issue-88446.rs b/src/test/ui/hrtb/issue-88446.rs
new file mode 100644
index 00000000000..571b8531757
--- /dev/null
+++ b/src/test/ui/hrtb/issue-88446.rs
@@ -0,0 +1,35 @@
+// check-pass
+
+trait Yokeable<'a> {
+    type Output: 'a;
+}
+impl<'a> Yokeable<'a> for () {
+    type Output = ();
+}
+
+trait DataMarker<'data> {
+    type Yokeable: for<'a> Yokeable<'a>;
+}
+impl<'data> DataMarker<'data> for () {
+    type Yokeable = ();
+}
+
+struct DataPayload<'data, M>(&'data M);
+
+impl DataPayload<'static, ()> {
+    pub fn map_project_with_capture<M2, T>(
+        _: for<'a> fn(
+            capture: T,
+            std::marker::PhantomData<&'a ()>,
+        ) -> <M2::Yokeable as Yokeable<'a>>::Output,
+    ) -> DataPayload<'static, M2>
+    where
+        M2: DataMarker<'static>,
+    {
+        todo!()
+    }
+}
+
+fn main() {
+    let _: DataPayload<()> = DataPayload::<()>::map_project_with_capture::<_, &()>(|_, _| todo!());
+}