diff options
| -rw-r--r-- | compiler/rustc_borrowck/src/member_constraints.rs | 46 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/region_infer/mod.rs | 4 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/type_check/mod.rs | 61 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/type_check/opaque_types.rs | 335 |
4 files changed, 375 insertions, 71 deletions
diff --git a/compiler/rustc_borrowck/src/member_constraints.rs b/compiler/rustc_borrowck/src/member_constraints.rs index fc621a3b828..60a6a37bc30 100644 --- a/compiler/rustc_borrowck/src/member_constraints.rs +++ b/compiler/rustc_borrowck/src/member_constraints.rs @@ -4,10 +4,9 @@ use std::ops::Index; use rustc_data_structures::captures::Captures; use rustc_data_structures::fx::FxIndexMap; use rustc_index::{IndexSlice, IndexVec}; -use rustc_middle::infer::MemberConstraint; use rustc_middle::ty::{self, Ty}; use rustc_span::Span; -use tracing::debug; +use tracing::instrument; /// Compactly stores a set of `R0 member of [R1...Rn]` constraints, /// indexed by the region `R0`. @@ -70,37 +69,42 @@ impl Default for MemberConstraintSet<'_, ty::RegionVid> { } impl<'tcx> MemberConstraintSet<'tcx, ty::RegionVid> { + pub(crate) fn is_empty(&self) -> bool { + self.constraints.is_empty() + } + /// Pushes a member constraint into the set. - /// - /// The input member constraint `m_c` is in the form produced by - /// the `rustc_middle::infer` code. - /// - /// The `to_region_vid` callback fn is used to convert the regions - /// within into `RegionVid` format -- it typically consults the - /// `UniversalRegions` data structure that is known to the caller - /// (but which this code is unaware of). - pub(crate) fn push_constraint( + #[instrument(level = "debug", skip(self))] + pub(crate) fn add_member_constraint( &mut self, - m_c: &MemberConstraint<'tcx>, - mut to_region_vid: impl FnMut(ty::Region<'tcx>) -> ty::RegionVid, + key: ty::OpaqueTypeKey<'tcx>, + hidden_ty: Ty<'tcx>, + definition_span: Span, + member_region_vid: ty::RegionVid, + choice_regions: &[ty::RegionVid], ) { - debug!("push_constraint(m_c={:?})", m_c); - let member_region_vid: ty::RegionVid = to_region_vid(m_c.member_region); let next_constraint = self.first_constraints.get(&member_region_vid).cloned(); let start_index = self.choice_regions.len(); - let end_index = start_index + m_c.choice_regions.len(); - debug!("push_constraint: member_region_vid={:?}", member_region_vid); + self.choice_regions.extend(choice_regions); + let end_index = self.choice_regions.len(); let constraint_index = self.constraints.push(NllMemberConstraint { next_constraint, member_region_vid, - definition_span: m_c.definition_span, - hidden_ty: m_c.hidden_ty, - key: m_c.key, + definition_span, + hidden_ty, + key, start_index, end_index, }); self.first_constraints.insert(member_region_vid, constraint_index); - self.choice_regions.extend(m_c.choice_regions.iter().map(|&r| to_region_vid(r))); + } + + // TODO: removed in the next commit + pub(crate) fn push_constraint( + &mut self, + _: &rustc_middle::infer::MemberConstraint<'tcx>, + _: impl FnMut(ty::Region<'tcx>) -> ty::RegionVid, + ) { } } diff --git a/compiler/rustc_borrowck/src/region_infer/mod.rs b/compiler/rustc_borrowck/src/region_infer/mod.rs index 0eecf98a6ed..65465181a80 100644 --- a/compiler/rustc_borrowck/src/region_infer/mod.rs +++ b/compiler/rustc_borrowck/src/region_infer/mod.rs @@ -571,7 +571,9 @@ impl<'tcx> RegionInferenceContext<'tcx> { /// Given a universal region in scope on the MIR, returns the /// corresponding index. /// - /// (Panics if `r` is not a registered universal region.) + /// Panics if `r` is not a registered universal region, most notably + /// if it is a placeholder. Handling placeholders requires access to the + /// `MirTypeckRegionConstraints`. pub(crate) fn to_region_vid(&self, r: ty::Region<'tcx>) -> RegionVid { self.universal_regions().to_region_vid(r) } diff --git a/compiler/rustc_borrowck/src/type_check/mod.rs b/compiler/rustc_borrowck/src/type_check/mod.rs index 0c59813d124..4d53c87e3fc 100644 --- a/compiler/rustc_borrowck/src/type_check/mod.rs +++ b/compiler/rustc_borrowck/src/type_check/mod.rs @@ -40,9 +40,7 @@ use rustc_mir_dataflow::points::DenseLocationMap; use rustc_span::def_id::CRATE_DEF_ID; use rustc_span::source_map::Spanned; use rustc_span::{DUMMY_SP, Span, sym}; -use rustc_trait_selection::traits::query::type_op::custom::{ - CustomTypeOp, scrape_region_constraints, -}; +use rustc_trait_selection::traits::query::type_op::custom::scrape_region_constraints; use rustc_trait_selection::traits::query::type_op::{TypeOp, TypeOpOutput}; use tracing::{debug, instrument, trace}; @@ -89,6 +87,7 @@ mod constraint_conversion; pub(crate) mod free_region_relations; mod input_output; pub(crate) mod liveness; +mod opaque_types; mod relate_tys; /// Type checks the given `mir` in the context of the inference @@ -179,52 +178,8 @@ pub(crate) fn type_check<'a, 'tcx>( liveness::generate(&mut typeck, body, &elements, flow_inits, move_data); - let opaque_type_values = infcx - .take_opaque_types() - .into_iter() - .map(|(opaque_type_key, decl)| { - let _: Result<_, ErrorGuaranteed> = typeck.fully_perform_op( - Locations::All(body.span), - ConstraintCategory::OpaqueType, - CustomTypeOp::new( - |ocx| { - ocx.infcx.register_member_constraints( - opaque_type_key, - decl.hidden_type.ty, - decl.hidden_type.span, - ); - Ok(()) - }, - "opaque_type_map", - ), - ); - let hidden_type = infcx.resolve_vars_if_possible(decl.hidden_type); - trace!("finalized opaque type {:?} to {:#?}", opaque_type_key, hidden_type.ty.kind()); - if hidden_type.has_non_region_infer() { - infcx.dcx().span_bug( - decl.hidden_type.span, - format!("could not resolve {:#?}", hidden_type.ty.kind()), - ); - } - - // Convert all regions to nll vars. - let (opaque_type_key, hidden_type) = - fold_regions(infcx.tcx, (opaque_type_key, hidden_type), |region, _| { - match region.kind() { - ty::ReVar(_) => region, - ty::RePlaceholder(placeholder) => { - typeck.constraints.placeholder_region(infcx, placeholder) - } - _ => ty::Region::new_var( - infcx.tcx, - typeck.universal_regions.to_region_vid(region), - ), - } - }); - - (opaque_type_key, hidden_type) - }) - .collect(); + let opaque_type_values = + opaque_types::take_opaques_and_register_member_constraints(&mut typeck); MirTypeckResults { constraints, universal_region_relations, opaque_type_values } } @@ -955,6 +910,14 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> { self.body } + fn to_region_vid(&mut self, r: ty::Region<'tcx>) -> RegionVid { + if let ty::RePlaceholder(placeholder) = r.kind() { + self.constraints.placeholder_region(self.infcx, placeholder).as_var() + } else { + self.universal_regions.to_region_vid(r) + } + } + fn unsized_feature_enabled(&self) -> bool { let features = self.tcx().features(); features.unsized_locals() || features.unsized_fn_params() diff --git a/compiler/rustc_borrowck/src/type_check/opaque_types.rs b/compiler/rustc_borrowck/src/type_check/opaque_types.rs new file mode 100644 index 00000000000..edf3b1ae092 --- /dev/null +++ b/compiler/rustc_borrowck/src/type_check/opaque_types.rs @@ -0,0 +1,335 @@ +use std::iter; + +use rustc_data_structures::fx::FxIndexMap; +use rustc_middle::span_bug; +use rustc_middle::ty::fold::fold_regions; +use rustc_middle::ty::{ + self, GenericArgKind, OpaqueHiddenType, OpaqueTypeKey, Ty, TyCtxt, TypeSuperVisitable, + TypeVisitable, TypeVisitableExt, TypeVisitor, +}; +use tracing::{debug, trace}; + +use super::{MemberConstraintSet, TypeChecker}; + +/// Once we're done with typechecking the body, we take all the opaque types +/// defined by this function and add their 'member constraints'. +pub(super) fn take_opaques_and_register_member_constraints<'tcx>( + typeck: &mut TypeChecker<'_, 'tcx>, +) -> FxIndexMap<OpaqueTypeKey<'tcx>, OpaqueHiddenType<'tcx>> { + let infcx = typeck.infcx; + // Annoying: to invoke `typeck.to_region_vid`, we need access to + // `typeck.constraints`, but we also want to be mutating + // `typeck.member_constraints`. For now, just swap out the value + // we want and replace at the end. + let mut member_constraints = std::mem::take(&mut typeck.constraints.member_constraints); + let opaque_types = infcx + .take_opaque_types() + .into_iter() + .map(|(opaque_type_key, decl)| { + let hidden_type = infcx.resolve_vars_if_possible(decl.hidden_type); + register_member_constraints( + typeck, + &mut member_constraints, + opaque_type_key, + hidden_type, + ); + trace!("finalized opaque type {:?} to {:#?}", opaque_type_key, hidden_type.ty.kind()); + if hidden_type.has_non_region_infer() { + span_bug!(hidden_type.span, "could not resolve {:?}", hidden_type.ty); + } + + // Convert all regions to nll vars. + let (opaque_type_key, hidden_type) = + fold_regions(infcx.tcx, (opaque_type_key, hidden_type), |r, _| { + ty::Region::new_var(infcx.tcx, typeck.to_region_vid(r)) + }); + + (opaque_type_key, hidden_type) + }) + .collect(); + assert!(typeck.constraints.member_constraints.is_empty()); + typeck.constraints.member_constraints = member_constraints; + opaque_types +} + +/// Given the map `opaque_types` containing the opaque +/// `impl Trait` types whose underlying, hidden types are being +/// inferred, this method adds constraints to the regions +/// appearing in those underlying hidden types to ensure that they +/// at least do not refer to random scopes within the current +/// function. These constraints are not (quite) sufficient to +/// guarantee that the regions are actually legal values; that +/// final condition is imposed after region inference is done. +/// +/// # The Problem +/// +/// Let's work through an example to explain how it works. Assume +/// the current function is as follows: +/// +/// ```text +/// fn foo<'a, 'b>(..) -> (impl Bar<'a>, impl Bar<'b>) +/// ``` +/// +/// Here, we have two `impl Trait` types whose values are being +/// inferred (the `impl Bar<'a>` and the `impl +/// Bar<'b>`). Conceptually, this is sugar for a setup where we +/// define underlying opaque types (`Foo1`, `Foo2`) and then, in +/// the return type of `foo`, we *reference* those definitions: +/// +/// ```text +/// type Foo1<'x> = impl Bar<'x>; +/// type Foo2<'x> = impl Bar<'x>; +/// fn foo<'a, 'b>(..) -> (Foo1<'a>, Foo2<'b>) { .. } +/// // ^^^^ ^^ +/// // | | +/// // | args +/// // def_id +/// ``` +/// +/// As indicating in the comments above, each of those references +/// is (in the compiler) basically generic parameters (`args`) +/// applied to the type of a suitable `def_id` (which identifies +/// `Foo1` or `Foo2`). +/// +/// Now, at this point in compilation, what we have done is to +/// replace each of the references (`Foo1<'a>`, `Foo2<'b>`) with +/// fresh inference variables C1 and C2. We wish to use the values +/// of these variables to infer the underlying types of `Foo1` and +/// `Foo2`. That is, this gives rise to higher-order (pattern) unification +/// constraints like: +/// +/// ```text +/// for<'a> (Foo1<'a> = C1) +/// for<'b> (Foo1<'b> = C2) +/// ``` +/// +/// For these equation to be satisfiable, the types `C1` and `C2` +/// can only refer to a limited set of regions. For example, `C1` +/// can only refer to `'static` and `'a`, and `C2` can only refer +/// to `'static` and `'b`. The job of this function is to impose that +/// constraint. +/// +/// Up to this point, C1 and C2 are basically just random type +/// inference variables, and hence they may contain arbitrary +/// regions. In fact, it is fairly likely that they do! Consider +/// this possible definition of `foo`: +/// +/// ```text +/// fn foo<'a, 'b>(x: &'a i32, y: &'b i32) -> (impl Bar<'a>, impl Bar<'b>) { +/// (&*x, &*y) +/// } +/// ``` +/// +/// Here, the values for the concrete types of the two impl +/// traits will include inference variables: +/// +/// ```text +/// &'0 i32 +/// &'1 i32 +/// ``` +/// +/// Ordinarily, the subtyping rules would ensure that these are +/// sufficiently large. But since `impl Bar<'a>` isn't a specific +/// type per se, we don't get such constraints by default. This +/// is where this function comes into play. It adds extra +/// constraints to ensure that all the regions which appear in the +/// inferred type are regions that could validly appear. +/// +/// This is actually a bit of a tricky constraint in general. We +/// want to say that each variable (e.g., `'0`) can only take on +/// values that were supplied as arguments to the opaque type +/// (e.g., `'a` for `Foo1<'a>`) or `'static`, which is always in +/// scope. We don't have a constraint quite of this kind in the current +/// region checker. +/// +/// # The Solution +/// +/// We generally prefer to make `<=` constraints, since they +/// integrate best into the region solver. To do that, we find the +/// "minimum" of all the arguments that appear in the args: that +/// is, some region which is less than all the others. In the case +/// of `Foo1<'a>`, that would be `'a` (it's the only choice, after +/// all). Then we apply that as a least bound to the variables +/// (e.g., `'a <= '0`). +/// +/// In some cases, there is no minimum. Consider this example: +/// +/// ```text +/// fn baz<'a, 'b>() -> impl Trait<'a, 'b> { ... } +/// ``` +/// +/// Here we would report a more complex "in constraint", like `'r +/// in ['a, 'b, 'static]` (where `'r` is some region appearing in +/// the hidden type). +/// +/// # Constrain regions, not the hidden concrete type +/// +/// Note that generating constraints on each region `Rc` is *not* +/// the same as generating an outlives constraint on `Tc` itself. +/// For example, if we had a function like this: +/// +/// ``` +/// # #![feature(type_alias_impl_trait)] +/// # fn main() {} +/// # trait Foo<'a> {} +/// # impl<'a, T> Foo<'a> for (&'a u32, T) {} +/// fn foo<'a, T>(x: &'a u32, y: T) -> impl Foo<'a> { +/// (x, y) +/// } +/// +/// // Equivalent to: +/// # mod dummy { use super::*; +/// type FooReturn<'a, T> = impl Foo<'a>; +/// fn foo<'a, T>(x: &'a u32, y: T) -> FooReturn<'a, T> { +/// (x, y) +/// } +/// # } +/// ``` +/// +/// then the hidden type `Tc` would be `(&'0 u32, T)` (where `'0` +/// is an inference variable). If we generated a constraint that +/// `Tc: 'a`, then this would incorrectly require that `T: 'a` -- +/// but this is not necessary, because the opaque type we +/// create will be allowed to reference `T`. So we only generate a +/// constraint that `'0: 'a`. +fn register_member_constraints<'tcx>( + typeck: &mut TypeChecker<'_, 'tcx>, + member_constraints: &mut MemberConstraintSet<'tcx, ty::RegionVid>, + opaque_type_key: OpaqueTypeKey<'tcx>, + OpaqueHiddenType { span, ty: hidden_ty }: OpaqueHiddenType<'tcx>, +) { + let tcx = typeck.tcx(); + let hidden_ty = typeck.infcx.resolve_vars_if_possible(hidden_ty); + debug!(?hidden_ty); + + let variances = tcx.variances_of(opaque_type_key.def_id); + debug!(?variances); + + // For a case like `impl Foo<'a, 'b>`, we would generate a constraint + // `'r in ['a, 'b, 'static]` for each region `'r` that appears in the + // hidden type (i.e., it must be equal to `'a`, `'b`, or `'static`). + // + // `conflict1` and `conflict2` are the two region bounds that we + // detected which were unrelated. They are used for diagnostics. + + // Create the set of choice regions: each region in the hidden + // type can be equal to any of the region parameters of the + // opaque type definition. + let fr_static = typeck.universal_regions.fr_static; + let choice_regions: Vec<_> = opaque_type_key + .args + .iter() + .enumerate() + .filter(|(i, _)| variances[*i] == ty::Invariant) + .filter_map(|(_, arg)| match arg.unpack() { + GenericArgKind::Lifetime(r) => Some(typeck.to_region_vid(r)), + GenericArgKind::Type(_) | GenericArgKind::Const(_) => None, + }) + .chain(iter::once(fr_static)) + .collect(); + + // FIXME(#42940): This should use the `FreeRegionsVisitor`, but that's + // not currently sound until we have existential regions. + hidden_ty.visit_with(&mut ConstrainOpaqueTypeRegionVisitor { + tcx, + op: |r| { + member_constraints.add_member_constraint( + opaque_type_key, + hidden_ty, + span, + typeck.to_region_vid(r), + &choice_regions, + ) + }, + }); +} + +/// Visitor that requires that (almost) all regions in the type visited outlive +/// `least_region`. We cannot use `push_outlives_components` because regions in +/// closure signatures are not included in their outlives components. We need to +/// ensure all regions outlive the given bound so that we don't end up with, +/// say, `ReVar` appearing in a return type and causing ICEs when other +/// functions end up with region constraints involving regions from other +/// functions. +/// +/// We also cannot use `for_each_free_region` because for closures it includes +/// the regions parameters from the enclosing item. +/// +/// We ignore any type parameters because impl trait values are assumed to +/// capture all the in-scope type parameters. +struct ConstrainOpaqueTypeRegionVisitor<'tcx, OP: FnMut(ty::Region<'tcx>)> { + tcx: TyCtxt<'tcx>, + op: OP, +} + +impl<'tcx, OP> TypeVisitor<TyCtxt<'tcx>> for ConstrainOpaqueTypeRegionVisitor<'tcx, OP> +where + OP: FnMut(ty::Region<'tcx>), +{ + fn visit_binder<T: TypeVisitable<TyCtxt<'tcx>>>(&mut self, t: &ty::Binder<'tcx, T>) { + t.super_visit_with(self); + } + + fn visit_region(&mut self, r: ty::Region<'tcx>) { + match *r { + // ignore bound regions, keep visiting + ty::ReBound(_, _) => {} + _ => (self.op)(r), + } + } + + fn visit_ty(&mut self, ty: Ty<'tcx>) { + // We're only interested in types involving regions + if !ty.flags().intersects(ty::TypeFlags::HAS_FREE_REGIONS) { + return; + } + + match ty.kind() { + ty::Closure(_, args) => { + // Skip lifetime parameters of the enclosing item(s) + + for upvar in args.as_closure().upvar_tys() { + upvar.visit_with(self); + } + args.as_closure().sig_as_fn_ptr_ty().visit_with(self); + } + + ty::CoroutineClosure(_, args) => { + // Skip lifetime parameters of the enclosing item(s) + + for upvar in args.as_coroutine_closure().upvar_tys() { + upvar.visit_with(self); + } + + args.as_coroutine_closure().signature_parts_ty().visit_with(self); + } + + ty::Coroutine(_, args) => { + // Skip lifetime parameters of the enclosing item(s) + // Also skip the witness type, because that has no free regions. + + for upvar in args.as_coroutine().upvar_tys() { + upvar.visit_with(self); + } + args.as_coroutine().return_ty().visit_with(self); + args.as_coroutine().yield_ty().visit_with(self); + args.as_coroutine().resume_ty().visit_with(self); + } + + ty::Alias(ty::Opaque, ty::AliasTy { def_id, args, .. }) => { + // Skip lifetime parameters that are not captures. + let variances = self.tcx.variances_of(*def_id); + + for (v, s) in std::iter::zip(variances, args.iter()) { + if *v != ty::Bivariant { + s.visit_with(self); + } + } + } + + _ => { + ty.super_visit_with(self); + } + } + } +} |