Skip to content

Commit c679690

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 r? `@ghost`
2 parents a01382d + 14ce42a commit c679690

20 files changed

+498
-117
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

+58-80
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,9 +340,9 @@ 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> {
373348
let opaque_ty_hir = tcx.hir().expect_item(opaque_type_key.def_id);
@@ -378,25 +353,28 @@ fn check_opaque_type_parameter_valid(
378353

379354
let opaque_generics = tcx.generics_of(opaque_type_key.def_id);
380355
let mut seen_params: FxIndexMap<_, Vec<_>> = FxIndexMap::default();
381-
for (i, arg) in opaque_type_key.args.iter().enumerate() {
356+
for (i, arg) in opaque_type_key.iter_captured_args(tcx) {
382357
if let Err(guar) = arg.error_reported() {
383358
return Err(guar);
384359
}
385360

386361
let arg_is_param = match arg.unpack() {
387362
GenericArgKind::Type(ty) => matches!(ty.kind(), ty::Param(_)),
388-
GenericArgKind::Lifetime(lt) if is_ty_alias => {
389-
matches!(*lt, ty::ReEarlyBound(_) | ty::ReFree(_))
390-
}
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,
363+
GenericArgKind::Lifetime(lt) => match is_ty_alias {
364+
true => matches!(*lt, ty::ReEarlyBound(_) | ty::ReFree(_)),
365+
// FIXME(#111935, #113916): For RPIT, we currently accept ReStatic as well.
366+
// This is a back-compat hack, see the issue for more.
367+
false => matches!(*lt, ty::ReEarlyBound(_) | ty::ReFree(_) | ty::ReStatic),
368+
},
395369
GenericArgKind::Const(ct) => matches!(ct.kind(), ty::ConstKind::Param(_)),
396370
};
397371

398372
if arg_is_param {
399-
seen_params.entry(arg).or_default().push(i);
373+
// FIXME(#113916): For RPIT, we can't currently check for unique lifetime
374+
// params, see that issue for more. We limit this to TAIT for now.
375+
if is_ty_alias {
376+
seen_params.entry(arg).or_default().push(i);
377+
}
400378
} else {
401379
// Prevent `fn foo() -> Foo<u32>` from being defining.
402380
let opaque_param = opaque_generics.param_at(i, tcx);

‎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

‎tests/ui/impl-trait/defining-use-captured-non-universal-region.infer.stderr

+12
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
error[E0792]: expected generic lifetime parameter, found `'_`
2+
--> $DIR/defining-use-captured-non-universal-region.rs:15:18
3+
|
4+
LL | fn foo<'a>() -> impl Sized + 'a {
5+
| -- this generic parameter must be used with a generic lifetime parameter
6+
...
7+
LL | let i: i32 = foo::<'_>();
8+
| ^^^^^^^^^^^
9+
10+
error: aborting due to previous error
11+
12+
For more information about this error, try `rustc --explain E0792`.

‎tests/ui/impl-trait/defining-use-captured-non-universal-region.rs

+24
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
// This was an ICE. See #110726.
2+
//
3+
// FIXME(#111935) revision `statik` should not pass.
4+
5+
// revisions: statik infer fixed
6+
//[fixed] check-pass
7+
//[statik] check-pass
8+
#![allow(unconditional_recursion)]
9+
10+
fn foo<'a>() -> impl Sized + 'a {
11+
#[cfg(statik)]
12+
let i: i32 = foo::<'static>();
13+
14+
#[cfg(infer)]
15+
let i: i32 = foo::<'_>();
16+
//[infer]~^ ERROR expected generic lifetime parameter, found `'_`
17+
18+
#[cfg(fixed)]
19+
let i: i32 = foo::<'a>();
20+
21+
i
22+
}
23+
24+
fn main() {}

0 commit comments

Comments
 (0)