Skip to content

Commit 66abdf7

Browse files
borsbors
committed
Auto merge of #116891 - aliemjay:opaque-region-infer-rework-2, r=<try>
rework opaque type region inference fixes #113971 Pass -> Error fixes #111906 ICE -> Pass fixes #110623 == fixes #109059 == fixes #112841 Pass -> Error fixes #110726 ICE->Error fixes #111935 Pass -> Error fixes #113916 == r? `@ghost`
2 parents aec4741 + 350b33e commit 66abdf7

26 files changed

+713
-123
lines changed

‎compiler/rustc_borrowck/src/region_infer/mod.rs

+19-12
Original file line numberDiff line numberDiff line change
@@ -97,9 +97,11 @@ pub struct RegionInferenceContext<'tcx> {
9797
/// visible from this index.
9898
scc_universes: IndexVec<ConstraintSccIndex, ty::UniverseIndex>,
9999

100-
/// Contains a "representative" from each SCC. This will be the
101-
/// minimal RegionVid belonging to that universe. It is used as a
102-
/// kind of hacky way to manage checking outlives relationships,
100+
/// Contains the "representative" region of each SCC.
101+
/// It is defined as the one with the minimal RegionVid, favoring
102+
/// free regions, then placeholders, then existential regions.
103+
///
104+
/// It is a hacky way to manage checking regions for equality,
103105
/// since we can 'canonicalize' each region to the representative
104106
/// of its SCC and be sure that -- if they have the same repr --
105107
/// they *must* be equal (though not having the same repr does not
@@ -487,22 +489,27 @@ impl<'tcx> RegionInferenceContext<'tcx> {
487489
scc_universes
488490
}
489491

490-
/// For each SCC, we compute a unique `RegionVid` (in fact, the
491-
/// minimal one that belongs to the SCC). See
492+
/// For each SCC, we compute a unique `RegionVid`. See
492493
/// `scc_representatives` field of `RegionInferenceContext` for
493494
/// more details.
494495
fn compute_scc_representatives(
495496
constraints_scc: &Sccs<RegionVid, ConstraintSccIndex>,
496497
definitions: &IndexSlice<RegionVid, RegionDefinition<'tcx>>,
497498
) -> IndexVec<ConstraintSccIndex, ty::RegionVid> {
498499
let num_sccs = constraints_scc.num_sccs();
499-
let next_region_vid = definitions.next_index();
500-
let mut scc_representatives = IndexVec::from_elem_n(next_region_vid, num_sccs);
501-
502-
for region_vid in definitions.indices() {
503-
let scc = constraints_scc.scc(region_vid);
504-
let prev_min = scc_representatives[scc];
505-
scc_representatives[scc] = region_vid.min(prev_min);
500+
let mut scc_representatives = IndexVec::from_elem_n(ty::RegionVid::MAX, num_sccs);
501+
502+
for (vid, def) in definitions.iter_enumerated() {
503+
use NllRegionVariableOrigin as VarOrigin;
504+
let scc = constraints_scc.scc(vid);
505+
let repr = &mut scc_representatives[scc];
506+
if *repr == ty::RegionVid::MAX {
507+
*repr = vid;
508+
} else if matches!(def.origin, VarOrigin::Placeholder(_))
509+
&& matches!(definitions[*repr].origin, VarOrigin::Existential { .. })
510+
{
511+
*repr = vid;
512+
}
506513
}
507514

508515
scc_representatives

‎compiler/rustc_borrowck/src/region_infer/opaque_types.rs

+132-84
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,10 @@
1-
use rustc_data_structures::fx::{FxIndexMap, FxIndexSet};
1+
use rustc_data_structures::fx::FxIndexMap;
22
use rustc_errors::ErrorGuaranteed;
33
use rustc_hir::def::DefKind;
44
use rustc_hir::def_id::LocalDefId;
55
use rustc_hir::OpaqueTyOrigin;
6-
use rustc_infer::infer::InferCtxt;
76
use rustc_infer::infer::TyCtxtInferExt as _;
7+
use rustc_infer::infer::{InferCtxt, NllRegionVariableOrigin};
88
use rustc_infer::traits::{Obligation, ObligationCause};
99
use rustc_middle::traits::DefiningAnchor;
1010
use rustc_middle::ty::visit::TypeVisitableExt;
@@ -66,85 +66,60 @@ impl<'tcx> RegionInferenceContext<'tcx> {
6666
) -> FxIndexMap<LocalDefId, OpaqueHiddenType<'tcx>> {
6767
let mut result: FxIndexMap<LocalDefId, OpaqueHiddenType<'tcx>> = FxIndexMap::default();
6868

69-
let member_constraints: FxIndexMap<_, _> = self
70-
.member_constraints
71-
.all_indices()
72-
.map(|ci| (self.member_constraints[ci].key, ci))
73-
.collect();
74-
debug!(?member_constraints);
75-
7669
for (opaque_type_key, concrete_type) in opaque_ty_decls {
77-
let args = opaque_type_key.args;
78-
debug!(?concrete_type, ?args);
70+
debug!(?opaque_type_key, ?concrete_type);
7971

80-
let mut subst_regions = vec![self.universal_regions.fr_static];
72+
let mut arg_regions: Vec<(ty::RegionVid, ty::Region<'_>)> =
73+
vec![(self.universal_regions.fr_static, infcx.tcx.lifetimes.re_static)];
8174

82-
let to_universal_region = |vid, subst_regions: &mut Vec<_>| {
83-
trace!(?vid);
84-
let scc = self.constraint_sccs.scc(vid);
85-
trace!(?scc);
86-
match self.scc_values.universal_regions_outlived_by(scc).find_map(|lb| {
87-
self.eval_equal(vid, lb).then_some(self.definitions[lb].external_name?)
88-
}) {
89-
Some(region) => {
90-
let vid = self.universal_regions.to_region_vid(region);
91-
subst_regions.push(vid);
92-
region
75+
let opaque_type_key =
76+
opaque_type_key.fold_captured_lifetime_args(infcx.tcx, |region| {
77+
let scc = self.constraint_sccs.scc(self.to_region_vid(region));
78+
let vid = self.scc_representatives[scc];
79+
let named = match self.definitions[vid].origin {
80+
NllRegionVariableOrigin::FreeRegion => self
81+
.universal_regions
82+
.universal_regions()
83+
.filter(|&ur| {
84+
use crate::universal_regions::RegionClassification as Class;
85+
matches!(
86+
self.universal_regions.region_classification(ur),
87+
Some(Class::Global | Class::Local)
88+
)
89+
})
90+
.filter(|&ur| ur != self.universal_regions.fr_fn_body)
91+
.find(|&ur| self.universal_region_relations.equal(vid, ur))
92+
.map(|ur| self.definitions[ur].external_name.unwrap()),
93+
NllRegionVariableOrigin::Placeholder(placeholder) => {
94+
Some(ty::Region::new_placeholder(infcx.tcx, placeholder))
95+
}
96+
NllRegionVariableOrigin::Existential { .. } => None,
9397
}
94-
None => {
95-
subst_regions.push(vid);
98+
.unwrap_or_else(|| {
9699
ty::Region::new_error_with_message(
97100
infcx.tcx,
98101
concrete_type.span,
99102
"opaque type with non-universal region args",
100103
)
101-
}
102-
}
103-
};
104+
});
104105

105-
// Start by inserting universal regions from the member_constraint choice regions.
106-
// This will ensure they get precedence when folding the regions in the concrete type.
107-
if let Some(&ci) = member_constraints.get(&opaque_type_key) {
108-
for &vid in self.member_constraints.choice_regions(ci) {
109-
to_universal_region(vid, &mut subst_regions);
110-
}
111-
}
112-
debug!(?subst_regions);
113-
114-
// Next, insert universal regions from args, so we can translate regions that appear
115-
// in them but are not subject to member constraints, for instance closure args.
116-
let universal_args = infcx.tcx.fold_regions(args, |region, _| {
117-
if let ty::RePlaceholder(..) = region.kind() {
118-
// Higher kinded regions don't need remapping, they don't refer to anything outside of this the args.
119-
return region;
120-
}
106+
arg_regions.push((vid, named));
107+
named
108+
});
109+
debug!(?opaque_type_key, ?arg_regions);
110+
111+
let concrete_type = infcx.tcx.fold_regions(concrete_type, |region, _| {
121112
let vid = self.to_region_vid(region);
122-
to_universal_region(vid, &mut subst_regions)
113+
arg_regions
114+
.iter()
115+
.find(|&&(ur_vid, _)| self.eval_equal(vid, ur_vid))
116+
.map(|&(_, ur_name)| ur_name)
117+
.unwrap_or(infcx.tcx.lifetimes.re_erased)
123118
});
124-
debug!(?universal_args);
125-
debug!(?subst_regions);
126-
127-
// Deduplicate the set of regions while keeping the chosen order.
128-
let subst_regions = subst_regions.into_iter().collect::<FxIndexSet<_>>();
129-
debug!(?subst_regions);
130-
131-
let universal_concrete_type =
132-
infcx.tcx.fold_regions(concrete_type, |region, _| match *region {
133-
ty::ReVar(vid) => subst_regions
134-
.iter()
135-
.find(|ur_vid| self.eval_equal(vid, **ur_vid))
136-
.and_then(|ur_vid| self.definitions[*ur_vid].external_name)
137-
.unwrap_or(infcx.tcx.lifetimes.re_erased),
138-
_ => region,
139-
});
140-
debug!(?universal_concrete_type);
119+
debug!(?concrete_type);
141120

142-
let opaque_type_key =
143-
OpaqueTypeKey { def_id: opaque_type_key.def_id, args: universal_args };
144-
let ty = infcx.infer_opaque_definition_from_instantiation(
145-
opaque_type_key,
146-
universal_concrete_type,
147-
);
121+
let ty =
122+
infcx.infer_opaque_definition_from_instantiation(opaque_type_key, concrete_type);
148123
// Sometimes two opaque types are the same only after we remap the generic parameters
149124
// back to the opaque type definition. E.g. we may have `OpaqueType<X, Y>` mapped to `(X, Y)`
150125
// and `OpaqueType<Y, X>` mapped to `(Y, X)`, and those are the same, but we only know that
@@ -365,38 +340,33 @@ fn check_opaque_type_well_formed<'tcx>(
365340
}
366341
}
367342

368-
fn check_opaque_type_parameter_valid(
369-
tcx: TyCtxt<'_>,
370-
opaque_type_key: OpaqueTypeKey<'_>,
343+
fn check_opaque_type_parameter_valid<'tcx>(
344+
tcx: TyCtxt<'tcx>,
345+
opaque_type_key: OpaqueTypeKey<'tcx>,
371346
span: Span,
372347
) -> Result<(), ErrorGuaranteed> {
373-
let opaque_ty_hir = tcx.hir().expect_item(opaque_type_key.def_id);
374-
let is_ty_alias = match opaque_ty_hir.expect_opaque_ty().origin {
375-
OpaqueTyOrigin::TyAlias { .. } => true,
376-
OpaqueTyOrigin::AsyncFn(..) | OpaqueTyOrigin::FnReturn(..) => false,
377-
};
378-
348+
let opaque_env = LazyOpaqueTyEnv::new(tcx, opaque_type_key.def_id);
379349
let opaque_generics = tcx.generics_of(opaque_type_key.def_id);
380350
let mut seen_params: FxIndexMap<_, Vec<_>> = FxIndexMap::default();
381-
for (i, arg) in opaque_type_key.args.iter().enumerate() {
351+
for (i, arg) in opaque_type_key.iter_captured_args(tcx) {
382352
if let Err(guar) = arg.error_reported() {
383353
return Err(guar);
384354
}
385355

386356
let arg_is_param = match arg.unpack() {
387357
GenericArgKind::Type(ty) => matches!(ty.kind(), ty::Param(_)),
388-
GenericArgKind::Lifetime(lt) if is_ty_alias => {
358+
GenericArgKind::Lifetime(lt) => {
389359
matches!(*lt, ty::ReEarlyBound(_) | ty::ReFree(_))
360+
|| (lt.is_static() && opaque_env.param_equal_static(i))
390361
}
391-
// FIXME(#113916): we can't currently check for unique lifetime params,
392-
// see that issue for more. We will also have to ignore unused lifetime
393-
// params for RPIT, but that's comparatively trivial ✨
394-
GenericArgKind::Lifetime(_) => continue,
395362
GenericArgKind::Const(ct) => matches!(ct.kind(), ty::ConstKind::Param(_)),
396363
};
397364

398365
if arg_is_param {
399-
seen_params.entry(arg).or_default().push(i);
366+
let seen_where = seen_params.entry(arg).or_default();
367+
if !seen_where.first().is_some_and(|&prev_i| opaque_env.params_equal(i, prev_i)) {
368+
seen_where.push(i);
369+
}
400370
} else {
401371
// Prevent `fn foo() -> Foo<u32>` from being defining.
402372
let opaque_param = opaque_generics.param_at(i, tcx);
@@ -428,3 +398,81 @@ fn check_opaque_type_parameter_valid(
428398

429399
Ok(())
430400
}
401+
402+
struct LazyOpaqueTyEnv<'tcx> {
403+
tcx: TyCtxt<'tcx>,
404+
def_id: LocalDefId,
405+
canonical_args: std::cell::Cell<Option<ty::GenericArgsRef<'tcx>>>,
406+
}
407+
408+
impl<'tcx> LazyOpaqueTyEnv<'tcx> {
409+
pub fn new(tcx: TyCtxt<'tcx>, def_id: LocalDefId) -> Self {
410+
Self { tcx, def_id, canonical_args: std::cell::Cell::new(None) }
411+
}
412+
413+
pub fn param_equal_static(&self, param_index: usize) -> bool {
414+
self.get_canonical_args()[param_index].expect_region().is_static()
415+
}
416+
417+
pub fn params_equal(&self, param1: usize, param2: usize) -> bool {
418+
let canonical_args = self.get_canonical_args();
419+
canonical_args[param1] == canonical_args[param2]
420+
}
421+
422+
fn get_canonical_args(&self) -> ty::GenericArgsRef<'tcx> {
423+
use rustc_hir as hir;
424+
use rustc_infer::infer::outlives::env::OutlivesEnvironment;
425+
use rustc_trait_selection::traits::outlives_bounds::InferCtxtExt as _;
426+
427+
if let Some(canonical_args) = self.canonical_args.get() {
428+
return canonical_args;
429+
}
430+
431+
let &Self { tcx, def_id, .. } = self;
432+
let origin = tcx.opaque_type_origin(def_id);
433+
let defining_use_anchor = match origin {
434+
hir::OpaqueTyOrigin::FnReturn(did) | hir::OpaqueTyOrigin::AsyncFn(did) => did,
435+
hir::OpaqueTyOrigin::TyAlias { .. } => tcx.impl_trait_parent(def_id),
436+
};
437+
let param_env = tcx.param_env(defining_use_anchor);
438+
439+
let infcx = tcx.infer_ctxt().build();
440+
let ocx = ObligationCtxt::new(&infcx);
441+
442+
let args = match origin {
443+
hir::OpaqueTyOrigin::FnReturn(parent) | hir::OpaqueTyOrigin::AsyncFn(parent) => {
444+
GenericArgs::identity_for_item(tcx, parent).extend_to(
445+
tcx,
446+
def_id.to_def_id(),
447+
|param, _| {
448+
tcx.map_rpit_lifetime_to_fn_lifetime(param.def_id.expect_local()).into()
449+
},
450+
)
451+
}
452+
hir::OpaqueTyOrigin::TyAlias { .. } => GenericArgs::identity_for_item(tcx, def_id),
453+
};
454+
455+
let wf_tys = ocx.assumed_wf_types(param_env, defining_use_anchor).unwrap_or_else(|_| {
456+
tcx.sess.delay_span_bug(tcx.def_span(def_id), "error getting implied bounds");
457+
Default::default()
458+
});
459+
let implied_bounds = infcx.implied_bounds_tys(param_env, defining_use_anchor, wf_tys);
460+
let outlives_env = OutlivesEnvironment::with_bounds(param_env, implied_bounds);
461+
462+
let mut seen = vec![tcx.lifetimes.re_static];
463+
let canonical_args = tcx.fold_regions(args, |r1, _| {
464+
if let Some(&r2) = seen.iter().find(|&&r2| {
465+
let free_regions = outlives_env.free_region_map();
466+
free_regions.sub_free_regions(tcx, r1, r2)
467+
&& free_regions.sub_free_regions(tcx, r2, r1)
468+
}) {
469+
r2
470+
} else {
471+
seen.push(r1);
472+
r1
473+
}
474+
});
475+
self.canonical_args.set(Some(canonical_args));
476+
canonical_args
477+
}
478+
}

‎compiler/rustc_borrowck/src/type_check/free_region_relations.rs

+7
Original file line numberDiff line numberDiff line change
@@ -159,6 +159,13 @@ impl UniversalRegionRelations<'_> {
159159
self.outlives.contains(fr1, fr2)
160160
}
161161

162+
/// Returns `true` if fr1 is known to equal fr2.
163+
///
164+
/// This will only ever be true for universally quantified regions.
165+
pub(crate) fn equal(&self, fr1: RegionVid, fr2: RegionVid) -> bool {
166+
self.outlives.contains(fr1, fr2) && self.outlives.contains(fr2, fr1)
167+
}
168+
162169
/// Returns a vector of free regions `x` such that `fr1: x` is
163170
/// known to hold.
164171
pub(crate) fn regions_outlived_by(&self, fr1: RegionVid) -> Vec<RegionVid> {

‎compiler/rustc_borrowck/src/type_check/mod.rs

+16
Original file line numberDiff line numberDiff line change
@@ -243,6 +243,22 @@ pub(crate) fn type_check<'mir, 'tcx>(
243243
hidden_type.ty = Ty::new_error(infcx.tcx, reported);
244244
}
245245

246+
// Convert all regions to nll vars.
247+
let (opaque_type_key, hidden_type) =
248+
infcx.tcx.fold_regions((opaque_type_key, hidden_type), |region, _| {
249+
match region.kind() {
250+
ty::ReVar(_) => region,
251+
ty::RePlaceholder(placeholder) => checker
252+
.borrowck_context
253+
.constraints
254+
.placeholder_region(infcx, placeholder),
255+
_ => ty::Region::new_var(
256+
infcx.tcx,
257+
checker.borrowck_context.universal_regions.to_region_vid(region),
258+
),
259+
}
260+
});
261+
246262
(opaque_type_key, hidden_type)
247263
})
248264
.collect();

‎compiler/rustc_middle/src/ty/mod.rs

+32
Original file line numberDiff line numberDiff line change
@@ -1504,6 +1504,38 @@ pub struct OpaqueTypeKey<'tcx> {
15041504
pub args: GenericArgsRef<'tcx>,
15051505
}
15061506

1507+
impl<'tcx> OpaqueTypeKey<'tcx> {
1508+
pub fn fold_captured_lifetime_args(
1509+
self,
1510+
tcx: TyCtxt<'tcx>,
1511+
mut f: impl FnMut(Region<'tcx>) -> Region<'tcx>,
1512+
) -> Self {
1513+
let Self { def_id, args } = self;
1514+
let args = std::iter::zip(args, tcx.variances_of(def_id)).map(|(arg, v)| {
1515+
match (arg.unpack(), v) {
1516+
(ty::GenericArgKind::Lifetime(_), ty::Bivariant) => arg,
1517+
(ty::GenericArgKind::Lifetime(lt), _) => f(lt).into(),
1518+
_ => arg,
1519+
}
1520+
});
1521+
let args = tcx.mk_args_from_iter(args);
1522+
Self { def_id, args }
1523+
}
1524+
1525+
pub fn iter_captured_args(
1526+
self,
1527+
tcx: TyCtxt<'tcx>,
1528+
) -> impl Iterator<Item = (usize, GenericArg<'tcx>)> {
1529+
std::iter::zip(self.args, tcx.variances_of(self.def_id)).enumerate().filter_map(
1530+
|(i, (arg, v))| match (arg.unpack(), v) {
1531+
(_, ty::Invariant) => Some((i, arg)),
1532+
(ty::GenericArgKind::Lifetime(_), ty::Bivariant) => None,
1533+
_ => bug!("unexpected opaque type arg variance"),
1534+
},
1535+
)
1536+
}
1537+
}
1538+
15071539
#[derive(Copy, Clone, Debug, TypeFoldable, TypeVisitable, HashStable, TyEncodable, TyDecodable)]
15081540
pub struct OpaqueHiddenType<'tcx> {
15091541
/// The span of this particular definition of the opaque type. So

0 commit comments

Comments
 (0)