diff options
Diffstat (limited to 'compiler/rustc_borrowck/src/type_check')
10 files changed, 4929 insertions, 0 deletions
diff --git a/compiler/rustc_borrowck/src/type_check/canonical.rs b/compiler/rustc_borrowck/src/type_check/canonical.rs new file mode 100644 index 000000000..6cfe5efb6 --- /dev/null +++ b/compiler/rustc_borrowck/src/type_check/canonical.rs @@ -0,0 +1,171 @@ +use std::fmt; + +use rustc_infer::infer::canonical::Canonical; +use rustc_infer::traits::query::NoSolution; +use rustc_middle::mir::ConstraintCategory; +use rustc_middle::ty::{self, ToPredicate, TypeFoldable}; +use rustc_span::def_id::DefId; +use rustc_span::Span; +use rustc_trait_selection::traits::query::type_op::{self, TypeOpOutput}; +use rustc_trait_selection::traits::query::Fallible; + +use crate::diagnostics::{ToUniverseInfo, UniverseInfo}; + +use super::{Locations, NormalizeLocation, TypeChecker}; + +impl<'a, 'tcx> TypeChecker<'a, 'tcx> { + /// Given some operation `op` that manipulates types, proves + /// predicates, or otherwise uses the inference context, executes + /// `op` and then executes all the further obligations that `op` + /// returns. This will yield a set of outlives constraints amongst + /// regions which are extracted and stored as having occurred at + /// `locations`. + /// + /// **Any `rustc_infer::infer` operations that might generate region + /// constraints should occur within this method so that those + /// constraints can be properly localized!** + #[instrument(skip(self, category, op), level = "trace")] + pub(super) fn fully_perform_op<R, Op>( + &mut self, + locations: Locations, + category: ConstraintCategory<'tcx>, + op: Op, + ) -> Fallible<R> + where + Op: type_op::TypeOp<'tcx, Output = R>, + Op::ErrorInfo: ToUniverseInfo<'tcx>, + { + let old_universe = self.infcx.universe(); + + let TypeOpOutput { output, constraints, error_info } = op.fully_perform(self.infcx)?; + + if let Some(data) = constraints { + self.push_region_constraints(locations, category, data); + } + + let universe = self.infcx.universe(); + + if old_universe != universe { + let universe_info = match error_info { + Some(error_info) => error_info.to_universe_info(old_universe), + None => UniverseInfo::other(), + }; + for u in old_universe..universe { + self.borrowck_context + .constraints + .universe_causes + .insert(u + 1, universe_info.clone()); + } + } + + Ok(output) + } + + pub(super) fn instantiate_canonical_with_fresh_inference_vars<T>( + &mut self, + span: Span, + canonical: &Canonical<'tcx, T>, + ) -> T + where + T: TypeFoldable<'tcx>, + { + let (instantiated, _) = + self.infcx.instantiate_canonical_with_fresh_inference_vars(span, canonical); + + for u in 0..canonical.max_universe.as_u32() { + let info = UniverseInfo::other(); + self.borrowck_context + .constraints + .universe_causes + .insert(ty::UniverseIndex::from_u32(u), info); + } + + instantiated + } + + #[instrument(skip(self), level = "debug")] + pub(super) fn prove_trait_ref( + &mut self, + trait_ref: ty::TraitRef<'tcx>, + locations: Locations, + category: ConstraintCategory<'tcx>, + ) { + self.prove_predicates( + Some(ty::Binder::dummy(ty::PredicateKind::Trait(ty::TraitPredicate { + trait_ref, + constness: ty::BoundConstness::NotConst, + polarity: ty::ImplPolarity::Positive, + }))), + locations, + category, + ); + } + + pub(super) fn normalize_and_prove_instantiated_predicates( + &mut self, + // Keep this parameter for now, in case we start using + // it in `ConstraintCategory` at some point. + _def_id: DefId, + instantiated_predicates: ty::InstantiatedPredicates<'tcx>, + locations: Locations, + ) { + for (predicate, span) in instantiated_predicates + .predicates + .into_iter() + .zip(instantiated_predicates.spans.into_iter()) + { + debug!(?predicate); + let predicate = self.normalize(predicate, locations); + self.prove_predicate(predicate, locations, ConstraintCategory::Predicate(span)); + } + } + + pub(super) fn prove_predicates( + &mut self, + predicates: impl IntoIterator<Item = impl ToPredicate<'tcx>>, + locations: Locations, + category: ConstraintCategory<'tcx>, + ) { + for predicate in predicates { + let predicate = predicate.to_predicate(self.tcx()); + debug!("prove_predicates(predicate={:?}, locations={:?})", predicate, locations,); + + self.prove_predicate(predicate, locations, category); + } + } + + #[instrument(skip(self), level = "debug")] + pub(super) fn prove_predicate( + &mut self, + predicate: ty::Predicate<'tcx>, + locations: Locations, + category: ConstraintCategory<'tcx>, + ) { + let param_env = self.param_env; + self.fully_perform_op( + locations, + category, + param_env.and(type_op::prove_predicate::ProvePredicate::new(predicate)), + ) + .unwrap_or_else(|NoSolution| { + span_mirbug!(self, NoSolution, "could not prove {:?}", predicate); + }) + } + + #[instrument(skip(self), level = "debug")] + pub(super) fn normalize<T>(&mut self, value: T, location: impl NormalizeLocation) -> T + where + T: type_op::normalize::Normalizable<'tcx> + fmt::Display + Copy + 'tcx, + { + let param_env = self.param_env; + self.fully_perform_op( + location.to_locations(), + ConstraintCategory::Boring, + param_env.and(type_op::normalize::Normalize::new(value)), + ) + .unwrap_or_else(|NoSolution| { + span_mirbug!(self, NoSolution, "failed to normalize `{:?}`", value); + value + }) + } +} diff --git a/compiler/rustc_borrowck/src/type_check/constraint_conversion.rs b/compiler/rustc_borrowck/src/type_check/constraint_conversion.rs new file mode 100644 index 000000000..167960918 --- /dev/null +++ b/compiler/rustc_borrowck/src/type_check/constraint_conversion.rs @@ -0,0 +1,204 @@ +use rustc_infer::infer::canonical::QueryOutlivesConstraint; +use rustc_infer::infer::canonical::QueryRegionConstraints; +use rustc_infer::infer::outlives::env::RegionBoundPairs; +use rustc_infer::infer::outlives::obligations::{TypeOutlives, TypeOutlivesDelegate}; +use rustc_infer::infer::region_constraints::{GenericKind, VerifyBound}; +use rustc_infer::infer::{self, InferCtxt, SubregionOrigin}; +use rustc_middle::mir::ConstraintCategory; +use rustc_middle::ty::subst::GenericArgKind; +use rustc_middle::ty::TypeVisitable; +use rustc_middle::ty::{self, TyCtxt}; +use rustc_span::{Span, DUMMY_SP}; + +use crate::{ + constraints::OutlivesConstraint, + nll::ToRegionVid, + region_infer::TypeTest, + type_check::{Locations, MirTypeckRegionConstraints}, + universal_regions::UniversalRegions, +}; + +pub(crate) struct ConstraintConversion<'a, 'tcx> { + infcx: &'a InferCtxt<'a, 'tcx>, + tcx: TyCtxt<'tcx>, + universal_regions: &'a UniversalRegions<'tcx>, + /// Each RBP `GK: 'a` is assumed to be true. These encode + /// relationships like `T: 'a` that are added via implicit bounds + /// or the `param_env`. + /// + /// Each region here is guaranteed to be a key in the `indices` + /// map. We use the "original" regions (i.e., the keys from the + /// map, and not the values) because the code in + /// `process_registered_region_obligations` has some special-cased + /// logic expecting to see (e.g.) `ReStatic`, and if we supplied + /// our special inference variable there, we would mess that up. + region_bound_pairs: &'a RegionBoundPairs<'tcx>, + implicit_region_bound: ty::Region<'tcx>, + param_env: ty::ParamEnv<'tcx>, + locations: Locations, + span: Span, + category: ConstraintCategory<'tcx>, + constraints: &'a mut MirTypeckRegionConstraints<'tcx>, +} + +impl<'a, 'tcx> ConstraintConversion<'a, 'tcx> { + pub(crate) fn new( + infcx: &'a InferCtxt<'a, 'tcx>, + universal_regions: &'a UniversalRegions<'tcx>, + region_bound_pairs: &'a RegionBoundPairs<'tcx>, + implicit_region_bound: ty::Region<'tcx>, + param_env: ty::ParamEnv<'tcx>, + locations: Locations, + span: Span, + category: ConstraintCategory<'tcx>, + constraints: &'a mut MirTypeckRegionConstraints<'tcx>, + ) -> Self { + Self { + infcx, + tcx: infcx.tcx, + universal_regions, + region_bound_pairs, + implicit_region_bound, + param_env, + locations, + span, + category, + constraints, + } + } + + #[instrument(skip(self), level = "debug")] + pub(super) fn convert_all(&mut self, query_constraints: &QueryRegionConstraints<'tcx>) { + let QueryRegionConstraints { outlives, member_constraints } = query_constraints; + + // Annoying: to invoke `self.to_region_vid`, we need access to + // `self.constraints`, but we also want to be mutating + // `self.member_constraints`. For now, just swap out the value + // we want and replace at the end. + let mut tmp = std::mem::take(&mut self.constraints.member_constraints); + for member_constraint in member_constraints { + tmp.push_constraint(member_constraint, |r| self.to_region_vid(r)); + } + self.constraints.member_constraints = tmp; + + for query_constraint in outlives { + self.convert(query_constraint); + } + } + + pub(super) fn convert(&mut self, query_constraint: &QueryOutlivesConstraint<'tcx>) { + debug!("generate: constraints at: {:#?}", self.locations); + + // Extract out various useful fields we'll need below. + let ConstraintConversion { + tcx, region_bound_pairs, implicit_region_bound, param_env, .. + } = *self; + + // At the moment, we never generate any "higher-ranked" + // region constraints like `for<'a> 'a: 'b`. At some point + // when we move to universes, we will, and this assertion + // will start to fail. + let ty::OutlivesPredicate(k1, r2) = query_constraint.no_bound_vars().unwrap_or_else(|| { + bug!("query_constraint {:?} contained bound vars", query_constraint,); + }); + + match k1.unpack() { + GenericArgKind::Lifetime(r1) => { + let r1_vid = self.to_region_vid(r1); + let r2_vid = self.to_region_vid(r2); + self.add_outlives(r1_vid, r2_vid); + } + + GenericArgKind::Type(mut t1) => { + // we don't actually use this for anything, but + // the `TypeOutlives` code needs an origin. + let origin = infer::RelateParamBound(DUMMY_SP, t1, None); + + // Placeholder regions need to be converted now because it may + // create new region variables, which can't be done later when + // verifying these bounds. + if t1.has_placeholders() { + t1 = tcx.fold_regions(t1, |r, _| match *r { + ty::RePlaceholder(placeholder) => { + self.constraints.placeholder_region(self.infcx, placeholder) + } + _ => r, + }); + } + + TypeOutlives::new( + &mut *self, + tcx, + region_bound_pairs, + Some(implicit_region_bound), + param_env, + ) + .type_must_outlive(origin, t1, r2); + } + + GenericArgKind::Const(_) => { + // Consts cannot outlive one another, so we + // don't need to handle any relations here. + } + } + } + + fn verify_to_type_test( + &mut self, + generic_kind: GenericKind<'tcx>, + region: ty::Region<'tcx>, + verify_bound: VerifyBound<'tcx>, + ) -> TypeTest<'tcx> { + let lower_bound = self.to_region_vid(region); + + TypeTest { generic_kind, lower_bound, locations: self.locations, verify_bound } + } + + fn to_region_vid(&mut self, r: ty::Region<'tcx>) -> ty::RegionVid { + if let ty::RePlaceholder(placeholder) = *r { + self.constraints.placeholder_region(self.infcx, placeholder).to_region_vid() + } else { + self.universal_regions.to_region_vid(r) + } + } + + fn add_outlives(&mut self, sup: ty::RegionVid, sub: ty::RegionVid) { + self.constraints.outlives_constraints.push(OutlivesConstraint { + locations: self.locations, + category: self.category, + span: self.span, + sub, + sup, + variance_info: ty::VarianceDiagInfo::default(), + }); + } + + fn add_type_test(&mut self, type_test: TypeTest<'tcx>) { + debug!("add_type_test(type_test={:?})", type_test); + self.constraints.type_tests.push(type_test); + } +} + +impl<'a, 'b, 'tcx> TypeOutlivesDelegate<'tcx> for &'a mut ConstraintConversion<'b, 'tcx> { + fn push_sub_region_constraint( + &mut self, + _origin: SubregionOrigin<'tcx>, + a: ty::Region<'tcx>, + b: ty::Region<'tcx>, + ) { + let b = self.to_region_vid(b); + let a = self.to_region_vid(a); + self.add_outlives(b, a); + } + + fn push_verify( + &mut self, + _origin: SubregionOrigin<'tcx>, + kind: GenericKind<'tcx>, + a: ty::Region<'tcx>, + bound: VerifyBound<'tcx>, + ) { + let type_test = self.verify_to_type_test(kind, a, bound); + self.add_type_test(type_test); + } +} diff --git a/compiler/rustc_borrowck/src/type_check/free_region_relations.rs b/compiler/rustc_borrowck/src/type_check/free_region_relations.rs new file mode 100644 index 000000000..cc0318ede --- /dev/null +++ b/compiler/rustc_borrowck/src/type_check/free_region_relations.rs @@ -0,0 +1,374 @@ +use rustc_data_structures::frozen::Frozen; +use rustc_data_structures::transitive_relation::TransitiveRelation; +use rustc_infer::infer::canonical::QueryRegionConstraints; +use rustc_infer::infer::outlives; +use rustc_infer::infer::outlives::env::RegionBoundPairs; +use rustc_infer::infer::region_constraints::GenericKind; +use rustc_infer::infer::InferCtxt; +use rustc_middle::mir::ConstraintCategory; +use rustc_middle::traits::query::OutlivesBound; +use rustc_middle::ty::{self, RegionVid, Ty}; +use rustc_span::DUMMY_SP; +use rustc_trait_selection::traits::query::type_op::{self, TypeOp}; +use std::rc::Rc; +use type_op::TypeOpOutput; + +use crate::{ + type_check::constraint_conversion, + type_check::{Locations, MirTypeckRegionConstraints}, + universal_regions::UniversalRegions, +}; + +#[derive(Debug)] +pub(crate) struct UniversalRegionRelations<'tcx> { + universal_regions: Rc<UniversalRegions<'tcx>>, + + /// Stores the outlives relations that are known to hold from the + /// implied bounds, in-scope where-clauses, and that sort of + /// thing. + outlives: TransitiveRelation<RegionVid>, + + /// This is the `<=` relation; that is, if `a: b`, then `b <= a`, + /// and we store that here. This is useful when figuring out how + /// to express some local region in terms of external regions our + /// caller will understand. + inverse_outlives: TransitiveRelation<RegionVid>, +} + +/// As part of computing the free region relations, we also have to +/// normalize the input-output types, which we then need later. So we +/// return those. This vector consists of first the input types and +/// then the output type as the last element. +type NormalizedInputsAndOutput<'tcx> = Vec<Ty<'tcx>>; + +pub(crate) struct CreateResult<'tcx> { + pub(crate) universal_region_relations: Frozen<UniversalRegionRelations<'tcx>>, + pub(crate) region_bound_pairs: RegionBoundPairs<'tcx>, + pub(crate) normalized_inputs_and_output: NormalizedInputsAndOutput<'tcx>, +} + +pub(crate) fn create<'tcx>( + infcx: &InferCtxt<'_, 'tcx>, + param_env: ty::ParamEnv<'tcx>, + implicit_region_bound: ty::Region<'tcx>, + universal_regions: &Rc<UniversalRegions<'tcx>>, + constraints: &mut MirTypeckRegionConstraints<'tcx>, +) -> CreateResult<'tcx> { + UniversalRegionRelationsBuilder { + infcx, + param_env, + implicit_region_bound, + constraints, + universal_regions: universal_regions.clone(), + region_bound_pairs: Default::default(), + relations: UniversalRegionRelations { + universal_regions: universal_regions.clone(), + outlives: Default::default(), + inverse_outlives: Default::default(), + }, + } + .create() +} + +impl UniversalRegionRelations<'_> { + /// Records in the `outlives_relation` (and + /// `inverse_outlives_relation`) that `fr_a: fr_b`. Invoked by the + /// builder below. + fn relate_universal_regions(&mut self, fr_a: RegionVid, fr_b: RegionVid) { + debug!("relate_universal_regions: fr_a={:?} outlives fr_b={:?}", fr_a, fr_b); + self.outlives.add(fr_a, fr_b); + self.inverse_outlives.add(fr_b, fr_a); + } + + /// Given two universal regions, returns the postdominating + /// upper-bound (effectively the least upper bound). + /// + /// (See `TransitiveRelation::postdom_upper_bound` for details on + /// the postdominating upper bound in general.) + pub(crate) fn postdom_upper_bound(&self, fr1: RegionVid, fr2: RegionVid) -> RegionVid { + assert!(self.universal_regions.is_universal_region(fr1)); + assert!(self.universal_regions.is_universal_region(fr2)); + self.inverse_outlives + .postdom_upper_bound(fr1, fr2) + .unwrap_or(self.universal_regions.fr_static) + } + + /// Finds an "upper bound" for `fr` that is not local. In other + /// words, returns the smallest (*) known region `fr1` that (a) + /// outlives `fr` and (b) is not local. + /// + /// (*) If there are multiple competing choices, we return all of them. + pub(crate) fn non_local_upper_bounds<'a>(&'a self, fr: RegionVid) -> Vec<RegionVid> { + debug!("non_local_upper_bound(fr={:?})", fr); + let res = self.non_local_bounds(&self.inverse_outlives, fr); + assert!(!res.is_empty(), "can't find an upper bound!?"); + res + } + + /// Returns the "postdominating" bound of the set of + /// `non_local_upper_bounds` for the given region. + pub(crate) fn non_local_upper_bound(&self, fr: RegionVid) -> RegionVid { + let upper_bounds = self.non_local_upper_bounds(fr); + + // In case we find more than one, reduce to one for + // convenience. This is to prevent us from generating more + // complex constraints, but it will cause spurious errors. + let post_dom = self.inverse_outlives.mutual_immediate_postdominator(upper_bounds); + + debug!("non_local_bound: post_dom={:?}", post_dom); + + post_dom + .and_then(|post_dom| { + // If the mutual immediate postdom is not local, then + // there is no non-local result we can return. + if !self.universal_regions.is_local_free_region(post_dom) { + Some(post_dom) + } else { + None + } + }) + .unwrap_or(self.universal_regions.fr_static) + } + + /// Finds a "lower bound" for `fr` that is not local. In other + /// words, returns the largest (*) known region `fr1` that (a) is + /// outlived by `fr` and (b) is not local. + /// + /// (*) If there are multiple competing choices, we pick the "postdominating" + /// one. See `TransitiveRelation::postdom_upper_bound` for details. + pub(crate) fn non_local_lower_bound(&self, fr: RegionVid) -> Option<RegionVid> { + debug!("non_local_lower_bound(fr={:?})", fr); + let lower_bounds = self.non_local_bounds(&self.outlives, fr); + + // In case we find more than one, reduce to one for + // convenience. This is to prevent us from generating more + // complex constraints, but it will cause spurious errors. + let post_dom = self.outlives.mutual_immediate_postdominator(lower_bounds); + + debug!("non_local_bound: post_dom={:?}", post_dom); + + post_dom.and_then(|post_dom| { + // If the mutual immediate postdom is not local, then + // there is no non-local result we can return. + if !self.universal_regions.is_local_free_region(post_dom) { + Some(post_dom) + } else { + None + } + }) + } + + /// Helper for `non_local_upper_bounds` and `non_local_lower_bounds`. + /// Repeatedly invokes `postdom_parent` until we find something that is not + /// local. Returns `None` if we never do so. + fn non_local_bounds<'a>( + &self, + relation: &'a TransitiveRelation<RegionVid>, + fr0: RegionVid, + ) -> Vec<RegionVid> { + // This method assumes that `fr0` is one of the universally + // quantified region variables. + assert!(self.universal_regions.is_universal_region(fr0)); + + let mut external_parents = vec![]; + let mut queue = vec![fr0]; + + // Keep expanding `fr` into its parents until we reach + // non-local regions. + while let Some(fr) = queue.pop() { + if !self.universal_regions.is_local_free_region(fr) { + external_parents.push(fr); + continue; + } + + queue.extend(relation.parents(fr)); + } + + debug!("non_local_bound: external_parents={:?}", external_parents); + + external_parents + } + + /// Returns `true` if fr1 is known to outlive fr2. + /// + /// This will only ever be true for universally quantified regions. + pub(crate) fn outlives(&self, fr1: RegionVid, fr2: RegionVid) -> bool { + self.outlives.contains(fr1, fr2) + } + + /// Returns a vector of free regions `x` such that `fr1: x` is + /// known to hold. + pub(crate) fn regions_outlived_by(&self, fr1: RegionVid) -> Vec<RegionVid> { + self.outlives.reachable_from(fr1) + } + + /// Returns the _non-transitive_ set of known `outlives` constraints between free regions. + pub(crate) fn known_outlives(&self) -> impl Iterator<Item = (RegionVid, RegionVid)> + '_ { + self.outlives.base_edges() + } +} + +struct UniversalRegionRelationsBuilder<'this, 'tcx> { + infcx: &'this InferCtxt<'this, 'tcx>, + param_env: ty::ParamEnv<'tcx>, + universal_regions: Rc<UniversalRegions<'tcx>>, + implicit_region_bound: ty::Region<'tcx>, + constraints: &'this mut MirTypeckRegionConstraints<'tcx>, + + // outputs: + relations: UniversalRegionRelations<'tcx>, + region_bound_pairs: RegionBoundPairs<'tcx>, +} + +impl<'tcx> UniversalRegionRelationsBuilder<'_, 'tcx> { + pub(crate) fn create(mut self) -> CreateResult<'tcx> { + let unnormalized_input_output_tys = self + .universal_regions + .unnormalized_input_tys + .iter() + .cloned() + .chain(Some(self.universal_regions.unnormalized_output_ty)); + + // For each of the input/output types: + // - Normalize the type. This will create some region + // constraints, which we buffer up because we are + // not ready to process them yet. + // - Then compute the implied bounds. This will adjust + // the `region_bound_pairs` and so forth. + // - After this is done, we'll process the constraints, once + // the `relations` is built. + let mut normalized_inputs_and_output = + Vec::with_capacity(self.universal_regions.unnormalized_input_tys.len() + 1); + let constraint_sets: Vec<_> = unnormalized_input_output_tys + .flat_map(|ty| { + debug!("build: input_or_output={:?}", ty); + // We only add implied bounds for the normalized type as the unnormalized + // type may not actually get checked by the caller. + // + // Can otherwise be unsound, see #91068. + let TypeOpOutput { output: norm_ty, constraints: constraints1, .. } = self + .param_env + .and(type_op::normalize::Normalize::new(ty)) + .fully_perform(self.infcx) + .unwrap_or_else(|_| { + self.infcx + .tcx + .sess + .delay_span_bug(DUMMY_SP, &format!("failed to normalize {:?}", ty)); + TypeOpOutput { + output: self.infcx.tcx.ty_error(), + constraints: None, + error_info: None, + } + }); + // Note: we need this in examples like + // ``` + // trait Foo { + // type Bar; + // fn foo(&self) -> &Self::Bar; + // } + // impl Foo for () { + // type Bar = (); + // fn foo(&self) ->&() {} + // } + // ``` + // Both &Self::Bar and &() are WF + let constraints_implied = self.add_implied_bounds(norm_ty); + normalized_inputs_and_output.push(norm_ty); + constraints1.into_iter().chain(constraints_implied) + }) + .collect(); + + // Insert the facts we know from the predicates. Why? Why not. + let param_env = self.param_env; + self.add_outlives_bounds(outlives::explicit_outlives_bounds(param_env)); + + // Finally: + // - outlives is reflexive, so `'r: 'r` for every region `'r` + // - `'static: 'r` for every region `'r` + // - `'r: 'fn_body` for every (other) universally quantified + // region `'r`, all of which are provided by our caller + let fr_static = self.universal_regions.fr_static; + let fr_fn_body = self.universal_regions.fr_fn_body; + for fr in self.universal_regions.universal_regions() { + debug!("build: relating free region {:?} to itself and to 'static", fr); + self.relations.relate_universal_regions(fr, fr); + self.relations.relate_universal_regions(fr_static, fr); + self.relations.relate_universal_regions(fr, fr_fn_body); + } + + for data in &constraint_sets { + constraint_conversion::ConstraintConversion::new( + self.infcx, + &self.universal_regions, + &self.region_bound_pairs, + self.implicit_region_bound, + self.param_env, + Locations::All(DUMMY_SP), + DUMMY_SP, + ConstraintCategory::Internal, + &mut self.constraints, + ) + .convert_all(data); + } + + CreateResult { + universal_region_relations: Frozen::freeze(self.relations), + region_bound_pairs: self.region_bound_pairs, + normalized_inputs_and_output, + } + } + + /// Update the type of a single local, which should represent + /// either the return type of the MIR or one of its arguments. At + /// the same time, compute and add any implied bounds that come + /// from this local. + #[instrument(level = "debug", skip(self))] + fn add_implied_bounds(&mut self, ty: Ty<'tcx>) -> Option<&'tcx QueryRegionConstraints<'tcx>> { + let TypeOpOutput { output: bounds, constraints, .. } = self + .param_env + .and(type_op::implied_outlives_bounds::ImpliedOutlivesBounds { ty }) + .fully_perform(self.infcx) + .unwrap_or_else(|_| bug!("failed to compute implied bounds {:?}", ty)); + self.add_outlives_bounds(bounds); + constraints + } + + /// Registers the `OutlivesBound` items from `outlives_bounds` in + /// the outlives relation as well as the region-bound pairs + /// listing. + fn add_outlives_bounds<I>(&mut self, outlives_bounds: I) + where + I: IntoIterator<Item = OutlivesBound<'tcx>>, + { + for outlives_bound in outlives_bounds { + debug!("add_outlives_bounds(bound={:?})", outlives_bound); + + match outlives_bound { + OutlivesBound::RegionSubRegion(r1, r2) => { + // `where Type:` is lowered to `where Type: 'empty` so that + // we check `Type` is well formed, but there's no use for + // this bound here. + if r1.is_empty() { + return; + } + + // The bound says that `r1 <= r2`; we store `r2: r1`. + let r1 = self.universal_regions.to_region_vid(r1); + let r2 = self.universal_regions.to_region_vid(r2); + self.relations.relate_universal_regions(r2, r1); + } + + OutlivesBound::RegionSubParam(r_a, param_b) => { + self.region_bound_pairs + .insert(ty::OutlivesPredicate(GenericKind::Param(param_b), r_a)); + } + + OutlivesBound::RegionSubProjection(r_a, projection_b) => { + self.region_bound_pairs + .insert(ty::OutlivesPredicate(GenericKind::Projection(projection_b), r_a)); + } + } + } + } +} diff --git a/compiler/rustc_borrowck/src/type_check/input_output.rs b/compiler/rustc_borrowck/src/type_check/input_output.rs new file mode 100644 index 000000000..4431a2e8e --- /dev/null +++ b/compiler/rustc_borrowck/src/type_check/input_output.rs @@ -0,0 +1,245 @@ +//! This module contains code to equate the input/output types appearing +//! in the MIR with the expected input/output types from the function +//! signature. This requires a bit of processing, as the expected types +//! are supplied to us before normalization and may contain opaque +//! `impl Trait` instances. In contrast, the input/output types found in +//! the MIR (specifically, in the special local variables for the +//! `RETURN_PLACE` the MIR arguments) are always fully normalized (and +//! contain revealed `impl Trait` values). + +use crate::type_check::constraint_conversion::ConstraintConversion; +use rustc_index::vec::Idx; +use rustc_infer::infer::LateBoundRegionConversionTime; +use rustc_middle::mir::*; +use rustc_middle::ty::Ty; +use rustc_span::Span; +use rustc_span::DUMMY_SP; +use rustc_trait_selection::traits::query::type_op::{self, TypeOp}; +use rustc_trait_selection::traits::query::Fallible; +use type_op::TypeOpOutput; + +use crate::universal_regions::UniversalRegions; + +use super::{Locations, TypeChecker}; + +impl<'a, 'tcx> TypeChecker<'a, 'tcx> { + #[instrument(skip(self, body, universal_regions), level = "debug")] + pub(super) fn equate_inputs_and_outputs( + &mut self, + body: &Body<'tcx>, + universal_regions: &UniversalRegions<'tcx>, + normalized_inputs_and_output: &[Ty<'tcx>], + ) { + let (&normalized_output_ty, normalized_input_tys) = + normalized_inputs_and_output.split_last().unwrap(); + + debug!(?normalized_output_ty); + debug!(?normalized_input_tys); + + let mir_def_id = body.source.def_id().expect_local(); + + // If the user explicitly annotated the input types, extract + // those. + // + // e.g., `|x: FxHashMap<_, &'static u32>| ...` + let user_provided_sig; + if !self.tcx().is_closure(mir_def_id.to_def_id()) { + user_provided_sig = None; + } else { + let typeck_results = self.tcx().typeck(mir_def_id); + user_provided_sig = typeck_results.user_provided_sigs.get(&mir_def_id.to_def_id()).map( + |user_provided_poly_sig| { + // Instantiate the canonicalized variables from + // user-provided signature (e.g., the `_` in the code + // above) with fresh variables. + let poly_sig = self.instantiate_canonical_with_fresh_inference_vars( + body.span, + &user_provided_poly_sig, + ); + + // Replace the bound items in the fn sig with fresh + // variables, so that they represent the view from + // "inside" the closure. + self.infcx.replace_bound_vars_with_fresh_vars( + body.span, + LateBoundRegionConversionTime::FnCall, + poly_sig, + ) + }, + ); + } + + debug!(?normalized_input_tys, ?body.local_decls); + + // Equate expected input tys with those in the MIR. + for (argument_index, &normalized_input_ty) in normalized_input_tys.iter().enumerate() { + if argument_index + 1 >= body.local_decls.len() { + self.tcx() + .sess + .delay_span_bug(body.span, "found more normalized_input_ty than local_decls"); + break; + } + + // In MIR, argument N is stored in local N+1. + let local = Local::new(argument_index + 1); + + let mir_input_ty = body.local_decls[local].ty; + + let mir_input_span = body.local_decls[local].source_info.span; + self.equate_normalized_input_or_output( + normalized_input_ty, + mir_input_ty, + mir_input_span, + ); + } + + if let Some(user_provided_sig) = user_provided_sig { + for (argument_index, &user_provided_input_ty) in + user_provided_sig.inputs().iter().enumerate() + { + // In MIR, closures begin an implicit `self`, so + // argument N is stored in local N+2. + let local = Local::new(argument_index + 2); + let mir_input_ty = body.local_decls[local].ty; + let mir_input_span = body.local_decls[local].source_info.span; + + // If the user explicitly annotated the input types, enforce those. + let user_provided_input_ty = + self.normalize(user_provided_input_ty, Locations::All(mir_input_span)); + + self.equate_normalized_input_or_output( + user_provided_input_ty, + mir_input_ty, + mir_input_span, + ); + } + } + + debug!( + "equate_inputs_and_outputs: body.yield_ty {:?}, universal_regions.yield_ty {:?}", + body.yield_ty(), + universal_regions.yield_ty + ); + + // We will not have a universal_regions.yield_ty if we yield (by accident) + // outside of a generator and return an `impl Trait`, so emit a delay_span_bug + // because we don't want to panic in an assert here if we've already got errors. + if body.yield_ty().is_some() != universal_regions.yield_ty.is_some() { + self.tcx().sess.delay_span_bug( + body.span, + &format!( + "Expected body to have yield_ty ({:?}) iff we have a UR yield_ty ({:?})", + body.yield_ty(), + universal_regions.yield_ty, + ), + ); + } + + if let (Some(mir_yield_ty), Some(ur_yield_ty)) = + (body.yield_ty(), universal_regions.yield_ty) + { + let yield_span = body.local_decls[RETURN_PLACE].source_info.span; + self.equate_normalized_input_or_output(ur_yield_ty, mir_yield_ty, yield_span); + } + + // Return types are a bit more complex. They may contain opaque `impl Trait` types. + let mir_output_ty = body.local_decls[RETURN_PLACE].ty; + let output_span = body.local_decls[RETURN_PLACE].source_info.span; + if let Err(terr) = self.eq_types( + normalized_output_ty, + mir_output_ty, + Locations::All(output_span), + ConstraintCategory::BoringNoLocation, + ) { + span_mirbug!( + self, + Location::START, + "equate_inputs_and_outputs: `{:?}=={:?}` failed with `{:?}`", + normalized_output_ty, + mir_output_ty, + terr + ); + }; + + // If the user explicitly annotated the output types, enforce those. + // Note that this only happens for closures. + if let Some(user_provided_sig) = user_provided_sig { + let user_provided_output_ty = user_provided_sig.output(); + let user_provided_output_ty = + self.normalize(user_provided_output_ty, Locations::All(output_span)); + if let Err(err) = self.eq_types( + user_provided_output_ty, + mir_output_ty, + Locations::All(output_span), + ConstraintCategory::BoringNoLocation, + ) { + span_mirbug!( + self, + Location::START, + "equate_inputs_and_outputs: `{:?}=={:?}` failed with `{:?}`", + mir_output_ty, + user_provided_output_ty, + err + ); + } + } + } + + #[instrument(skip(self, span), level = "debug")] + fn equate_normalized_input_or_output(&mut self, a: Ty<'tcx>, b: Ty<'tcx>, span: Span) { + if let Err(_) = + self.eq_types(a, b, Locations::All(span), ConstraintCategory::BoringNoLocation) + { + // FIXME(jackh726): This is a hack. It's somewhat like + // `rustc_traits::normalize_after_erasing_regions`. Ideally, we'd + // like to normalize *before* inserting into `local_decls`, but + // doing so ends up causing some other trouble. + let b = match self.normalize_and_add_constraints(b) { + Ok(n) => n, + Err(_) => { + debug!("equate_inputs_and_outputs: NoSolution"); + 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) + { + span_mirbug!( + self, + Location::START, + "equate_normalized_input_or_output: `{:?}=={:?}` failed with `{:?}`", + a, + b, + terr + ); + } + } + } + + pub(crate) fn normalize_and_add_constraints(&mut self, t: Ty<'tcx>) -> Fallible<Ty<'tcx>> { + let TypeOpOutput { output: norm_ty, constraints, .. } = + self.param_env.and(type_op::normalize::Normalize::new(t)).fully_perform(self.infcx)?; + + debug!("{:?} normalized to {:?}", t, norm_ty); + + for data in constraints { + ConstraintConversion::new( + self.infcx, + &self.borrowck_context.universal_regions, + &self.region_bound_pairs, + self.implicit_region_bound, + self.param_env, + Locations::All(DUMMY_SP), + DUMMY_SP, + ConstraintCategory::Internal, + &mut self.borrowck_context.constraints, + ) + .convert_all(&*data); + } + + Ok(norm_ty) + } +} diff --git a/compiler/rustc_borrowck/src/type_check/liveness/local_use_map.rs b/compiler/rustc_borrowck/src/type_check/liveness/local_use_map.rs new file mode 100644 index 000000000..fda2cee43 --- /dev/null +++ b/compiler/rustc_borrowck/src/type_check/liveness/local_use_map.rs @@ -0,0 +1,170 @@ +use rustc_data_structures::vec_linked_list as vll; +use rustc_index::vec::IndexVec; +use rustc_middle::mir::visit::{PlaceContext, Visitor}; +use rustc_middle::mir::{Body, Local, Location}; + +use crate::def_use::{self, DefUse}; +use crate::region_infer::values::{PointIndex, RegionValueElements}; + +/// A map that cross references each local with the locations where it +/// is defined (assigned), used, or dropped. Used during liveness +/// computation. +/// +/// We keep track only of `Local`s we'll do the liveness analysis later, +/// this means that our internal `IndexVec`s will only be sparsely populated. +/// In the time-memory trade-off between keeping compact vectors with new +/// indexes (and needing to continuously map the `Local` index to its compact +/// counterpart) and having `IndexVec`s that we only use a fraction of, time +/// (and code simplicity) was favored. The rationale is that we only keep +/// a small number of `IndexVec`s throughout the entire analysis while, in +/// contrast, we're accessing each `Local` *many* times. +pub(crate) struct LocalUseMap { + /// Head of a linked list of **definitions** of each variable -- + /// definition in this context means assignment, e.g., `x` is + /// defined in `x = y` but not `y`; that first def is the head of + /// a linked list that lets you enumerate all places the variable + /// is assigned. + first_def_at: IndexVec<Local, Option<AppearanceIndex>>, + + /// Head of a linked list of **uses** of each variable -- use in + /// this context means that the existing value of the variable is + /// read or modified. e.g., `y` is used in `x = y` but not `x`. + /// Note that `DROP(x)` terminators are excluded from this list. + first_use_at: IndexVec<Local, Option<AppearanceIndex>>, + + /// Head of a linked list of **drops** of each variable -- these + /// are a special category of uses corresponding to the drop that + /// we add for each local variable. + first_drop_at: IndexVec<Local, Option<AppearanceIndex>>, + + appearances: IndexVec<AppearanceIndex, Appearance>, +} + +struct Appearance { + point_index: PointIndex, + next: Option<AppearanceIndex>, +} + +rustc_index::newtype_index! { + pub struct AppearanceIndex { .. } +} + +impl vll::LinkElem for Appearance { + type LinkIndex = AppearanceIndex; + + fn next(elem: &Self) -> Option<AppearanceIndex> { + elem.next + } +} + +impl LocalUseMap { + pub(crate) fn build( + live_locals: &[Local], + elements: &RegionValueElements, + body: &Body<'_>, + ) -> Self { + let nones = IndexVec::from_elem_n(None, body.local_decls.len()); + let mut local_use_map = LocalUseMap { + first_def_at: nones.clone(), + first_use_at: nones.clone(), + first_drop_at: nones, + appearances: IndexVec::new(), + }; + + if live_locals.is_empty() { + return local_use_map; + } + + let mut locals_with_use_data: IndexVec<Local, bool> = + IndexVec::from_elem_n(false, body.local_decls.len()); + live_locals.iter().for_each(|&local| locals_with_use_data[local] = true); + + LocalUseMapBuild { local_use_map: &mut local_use_map, elements, locals_with_use_data } + .visit_body(&body); + + local_use_map + } + + pub(crate) fn defs(&self, local: Local) -> impl Iterator<Item = PointIndex> + '_ { + vll::iter(self.first_def_at[local], &self.appearances) + .map(move |aa| self.appearances[aa].point_index) + } + + pub(crate) fn uses(&self, local: Local) -> impl Iterator<Item = PointIndex> + '_ { + vll::iter(self.first_use_at[local], &self.appearances) + .map(move |aa| self.appearances[aa].point_index) + } + + pub(crate) fn drops(&self, local: Local) -> impl Iterator<Item = PointIndex> + '_ { + vll::iter(self.first_drop_at[local], &self.appearances) + .map(move |aa| self.appearances[aa].point_index) + } +} + +struct LocalUseMapBuild<'me> { + local_use_map: &'me mut LocalUseMap, + elements: &'me RegionValueElements, + + // Vector used in `visit_local` to signal which `Local`s do we need + // def/use/drop information on, constructed from `live_locals` (that + // contains the variables we'll do the liveness analysis for). + // This vector serves optimization purposes only: we could have + // obtained the same information from `live_locals` but we want to + // avoid repeatedly calling `Vec::contains()` (see `LocalUseMap` for + // the rationale on the time-memory trade-off we're favoring here). + locals_with_use_data: IndexVec<Local, bool>, +} + +impl LocalUseMapBuild<'_> { + fn insert_def(&mut self, local: Local, location: Location) { + Self::insert( + self.elements, + &mut self.local_use_map.first_def_at[local], + &mut self.local_use_map.appearances, + location, + ); + } + + fn insert_use(&mut self, local: Local, location: Location) { + Self::insert( + self.elements, + &mut self.local_use_map.first_use_at[local], + &mut self.local_use_map.appearances, + location, + ); + } + + fn insert_drop(&mut self, local: Local, location: Location) { + Self::insert( + self.elements, + &mut self.local_use_map.first_drop_at[local], + &mut self.local_use_map.appearances, + location, + ); + } + + fn insert( + elements: &RegionValueElements, + first_appearance: &mut Option<AppearanceIndex>, + appearances: &mut IndexVec<AppearanceIndex, Appearance>, + location: Location, + ) { + let point_index = elements.point_from_location(location); + let appearance_index = + appearances.push(Appearance { point_index, next: *first_appearance }); + *first_appearance = Some(appearance_index); + } +} + +impl Visitor<'_> for LocalUseMapBuild<'_> { + fn visit_local(&mut self, local: Local, context: PlaceContext, location: Location) { + if self.locals_with_use_data[local] { + match def_use::categorize(context) { + Some(DefUse::Def) => self.insert_def(local, location), + Some(DefUse::Use) => self.insert_use(local, location), + Some(DefUse::Drop) => self.insert_drop(local, location), + _ => (), + } + } + } +} diff --git a/compiler/rustc_borrowck/src/type_check/liveness/mod.rs b/compiler/rustc_borrowck/src/type_check/liveness/mod.rs new file mode 100644 index 000000000..d5c401ae1 --- /dev/null +++ b/compiler/rustc_borrowck/src/type_check/liveness/mod.rs @@ -0,0 +1,139 @@ +use itertools::{Either, Itertools}; +use rustc_data_structures::fx::FxHashSet; +use rustc_middle::mir::{Body, Local}; +use rustc_middle::ty::{RegionVid, TyCtxt}; +use rustc_mir_dataflow::impls::MaybeInitializedPlaces; +use rustc_mir_dataflow::move_paths::MoveData; +use rustc_mir_dataflow::ResultsCursor; +use std::rc::Rc; + +use crate::{ + constraints::OutlivesConstraintSet, + facts::{AllFacts, AllFactsExt}, + location::LocationTable, + nll::ToRegionVid, + region_infer::values::RegionValueElements, + universal_regions::UniversalRegions, +}; + +use super::TypeChecker; + +mod local_use_map; +mod polonius; +mod trace; + +/// Combines liveness analysis with initialization analysis to +/// determine which variables are live at which points, both due to +/// ordinary uses and drops. Returns a set of (ty, location) pairs +/// that indicate which types must be live at which point in the CFG. +/// This vector is consumed by `constraint_generation`. +/// +/// N.B., this computation requires normalization; therefore, it must be +/// performed before +pub(super) fn generate<'mir, 'tcx>( + typeck: &mut TypeChecker<'_, 'tcx>, + body: &Body<'tcx>, + elements: &Rc<RegionValueElements>, + flow_inits: &mut ResultsCursor<'mir, 'tcx, MaybeInitializedPlaces<'mir, 'tcx>>, + move_data: &MoveData<'tcx>, + location_table: &LocationTable, + use_polonius: bool, +) { + debug!("liveness::generate"); + + let free_regions = regions_that_outlive_free_regions( + typeck.infcx.num_region_vars(), + &typeck.borrowck_context.universal_regions, + &typeck.borrowck_context.constraints.outlives_constraints, + ); + let (relevant_live_locals, boring_locals) = + compute_relevant_live_locals(typeck.tcx(), &free_regions, &body); + let facts_enabled = use_polonius || AllFacts::enabled(typeck.tcx()); + + let polonius_drop_used = if facts_enabled { + let mut drop_used = Vec::new(); + polonius::populate_access_facts(typeck, body, location_table, move_data, &mut drop_used); + Some(drop_used) + } else { + None + }; + + trace::trace( + typeck, + body, + elements, + flow_inits, + move_data, + relevant_live_locals, + boring_locals, + polonius_drop_used, + ); +} + +// The purpose of `compute_relevant_live_locals` is to define the subset of `Local` +// variables for which we need to do a liveness computation. We only need +// to compute whether a variable `X` is live if that variable contains +// some region `R` in its type where `R` is not known to outlive a free +// region (i.e., where `R` may be valid for just a subset of the fn body). +fn compute_relevant_live_locals<'tcx>( + tcx: TyCtxt<'tcx>, + free_regions: &FxHashSet<RegionVid>, + body: &Body<'tcx>, +) -> (Vec<Local>, Vec<Local>) { + let (boring_locals, relevant_live_locals): (Vec<_>, Vec<_>) = + body.local_decls.iter_enumerated().partition_map(|(local, local_decl)| { + if tcx.all_free_regions_meet(&local_decl.ty, |r| { + free_regions.contains(&r.to_region_vid()) + }) { + Either::Left(local) + } else { + Either::Right(local) + } + }); + + debug!("{} total variables", body.local_decls.len()); + debug!("{} variables need liveness", relevant_live_locals.len()); + debug!("{} regions outlive free regions", free_regions.len()); + + (relevant_live_locals, boring_locals) +} + +/// Computes all regions that are (currently) known to outlive free +/// regions. For these regions, we do not need to compute +/// liveness, since the outlives constraints will ensure that they +/// are live over the whole fn body anyhow. +fn regions_that_outlive_free_regions<'tcx>( + num_region_vars: usize, + universal_regions: &UniversalRegions<'tcx>, + constraint_set: &OutlivesConstraintSet<'tcx>, +) -> FxHashSet<RegionVid> { + // Build a graph of the outlives constraints thus far. This is + // a reverse graph, so for each constraint `R1: R2` we have an + // edge `R2 -> R1`. Therefore, if we find all regions + // reachable from each free region, we will have all the + // regions that are forced to outlive some free region. + let rev_constraint_graph = constraint_set.reverse_graph(num_region_vars); + let fr_static = universal_regions.fr_static; + let rev_region_graph = rev_constraint_graph.region_graph(constraint_set, fr_static); + + // Stack for the depth-first search. Start out with all the free regions. + let mut stack: Vec<_> = universal_regions.universal_regions().collect(); + + // Set of all free regions, plus anything that outlives them. Initially + // just contains the free regions. + let mut outlives_free_region: FxHashSet<_> = stack.iter().cloned().collect(); + + // Do the DFS -- for each thing in the stack, find all things + // that outlive it and add them to the set. If they are not, + // push them onto the stack for later. + while let Some(sub_region) = stack.pop() { + stack.extend( + rev_region_graph + .outgoing_regions(sub_region) + .filter(|&r| outlives_free_region.insert(r)), + ); + } + + // Return the final set of things we visited. + outlives_free_region +} diff --git a/compiler/rustc_borrowck/src/type_check/liveness/polonius.rs b/compiler/rustc_borrowck/src/type_check/liveness/polonius.rs new file mode 100644 index 000000000..bc76a465e --- /dev/null +++ b/compiler/rustc_borrowck/src/type_check/liveness/polonius.rs @@ -0,0 +1,140 @@ +use crate::def_use::{self, DefUse}; +use crate::location::{LocationIndex, LocationTable}; +use rustc_middle::mir::visit::{MutatingUseContext, PlaceContext, Visitor}; +use rustc_middle::mir::{Body, Local, Location, Place}; +use rustc_middle::ty::subst::GenericArg; +use rustc_mir_dataflow::move_paths::{LookupResult, MoveData, MovePathIndex}; + +use super::TypeChecker; + +type VarPointRelation = Vec<(Local, LocationIndex)>; +type PathPointRelation = Vec<(MovePathIndex, LocationIndex)>; + +struct UseFactsExtractor<'me, 'tcx> { + var_defined_at: &'me mut VarPointRelation, + var_used_at: &'me mut VarPointRelation, + location_table: &'me LocationTable, + var_dropped_at: &'me mut VarPointRelation, + move_data: &'me MoveData<'tcx>, + path_accessed_at_base: &'me mut PathPointRelation, +} + +// A Visitor to walk through the MIR and extract point-wise facts +impl UseFactsExtractor<'_, '_> { + fn location_to_index(&self, location: Location) -> LocationIndex { + self.location_table.mid_index(location) + } + + fn insert_def(&mut self, local: Local, location: Location) { + debug!("UseFactsExtractor::insert_def()"); + self.var_defined_at.push((local, self.location_to_index(location))); + } + + fn insert_use(&mut self, local: Local, location: Location) { + debug!("UseFactsExtractor::insert_use()"); + self.var_used_at.push((local, self.location_to_index(location))); + } + + fn insert_drop_use(&mut self, local: Local, location: Location) { + debug!("UseFactsExtractor::insert_drop_use()"); + self.var_dropped_at.push((local, self.location_to_index(location))); + } + + fn insert_path_access(&mut self, path: MovePathIndex, location: Location) { + debug!("UseFactsExtractor::insert_path_access({:?}, {:?})", path, location); + self.path_accessed_at_base.push((path, self.location_to_index(location))); + } + + fn place_to_mpi(&self, place: &Place<'_>) -> Option<MovePathIndex> { + match self.move_data.rev_lookup.find(place.as_ref()) { + LookupResult::Exact(mpi) => Some(mpi), + LookupResult::Parent(mmpi) => mmpi, + } + } +} + +impl<'a, 'tcx> Visitor<'tcx> for UseFactsExtractor<'a, 'tcx> { + fn visit_local(&mut self, local: Local, context: PlaceContext, location: Location) { + match def_use::categorize(context) { + Some(DefUse::Def) => self.insert_def(local, location), + Some(DefUse::Use) => self.insert_use(local, location), + Some(DefUse::Drop) => self.insert_drop_use(local, location), + _ => (), + } + } + + fn visit_place(&mut self, place: &Place<'tcx>, context: PlaceContext, location: Location) { + self.super_place(place, context, location); + match context { + PlaceContext::NonMutatingUse(_) => { + if let Some(mpi) = self.place_to_mpi(place) { + self.insert_path_access(mpi, location); + } + } + + PlaceContext::MutatingUse(MutatingUseContext::Borrow) => { + if let Some(mpi) = self.place_to_mpi(place) { + self.insert_path_access(mpi, location); + } + } + _ => (), + } + } +} + +pub(super) fn populate_access_facts<'a, 'tcx>( + typeck: &mut TypeChecker<'a, 'tcx>, + body: &Body<'tcx>, + location_table: &LocationTable, + move_data: &MoveData<'tcx>, + dropped_at: &mut Vec<(Local, Location)>, +) { + debug!("populate_access_facts()"); + + if let Some(facts) = typeck.borrowck_context.all_facts.as_mut() { + let mut extractor = UseFactsExtractor { + var_defined_at: &mut facts.var_defined_at, + var_used_at: &mut facts.var_used_at, + var_dropped_at: &mut facts.var_dropped_at, + path_accessed_at_base: &mut facts.path_accessed_at_base, + location_table, + move_data, + }; + extractor.visit_body(&body); + + facts.var_dropped_at.extend( + dropped_at.iter().map(|&(local, location)| (local, location_table.mid_index(location))), + ); + + for (local, local_decl) in body.local_decls.iter_enumerated() { + debug!( + "add use_of_var_derefs_origin facts - local={:?}, type={:?}", + local, local_decl.ty + ); + let _prof_timer = typeck.infcx.tcx.prof.generic_activity("polonius_fact_generation"); + let universal_regions = &typeck.borrowck_context.universal_regions; + typeck.infcx.tcx.for_each_free_region(&local_decl.ty, |region| { + let region_vid = universal_regions.to_region_vid(region); + facts.use_of_var_derefs_origin.push((local, region_vid)); + }); + } + } +} + +// For every potentially drop()-touched region `region` in `local`'s type +// (`kind`), emit a Polonius `use_of_var_derefs_origin(local, origin)` fact. +pub(super) fn add_drop_of_var_derefs_origin<'tcx>( + typeck: &mut TypeChecker<'_, 'tcx>, + local: Local, + kind: &GenericArg<'tcx>, +) { + debug!("add_drop_of_var_derefs_origin(local={:?}, kind={:?}", local, kind); + if let Some(facts) = typeck.borrowck_context.all_facts.as_mut() { + let _prof_timer = typeck.infcx.tcx.prof.generic_activity("polonius_fact_generation"); + let universal_regions = &typeck.borrowck_context.universal_regions; + typeck.infcx.tcx.for_each_free_region(kind, |drop_live_region| { + let region_vid = universal_regions.to_region_vid(drop_live_region); + facts.drop_of_var_derefs_origin.push((local, region_vid)); + }); + } +} diff --git a/compiler/rustc_borrowck/src/type_check/liveness/trace.rs b/compiler/rustc_borrowck/src/type_check/liveness/trace.rs new file mode 100644 index 000000000..42b577175 --- /dev/null +++ b/compiler/rustc_borrowck/src/type_check/liveness/trace.rs @@ -0,0 +1,578 @@ +use rustc_data_structures::fx::{FxHashMap, FxHashSet}; +use rustc_index::bit_set::HybridBitSet; +use rustc_index::interval::IntervalSet; +use rustc_infer::infer::canonical::QueryRegionConstraints; +use rustc_middle::mir::{BasicBlock, Body, ConstraintCategory, Local, Location}; +use rustc_middle::ty::{Ty, TypeVisitable}; +use rustc_trait_selection::traits::query::dropck_outlives::DropckOutlivesResult; +use rustc_trait_selection::traits::query::type_op::outlives::DropckOutlives; +use rustc_trait_selection::traits::query::type_op::{TypeOp, TypeOpOutput}; +use std::rc::Rc; + +use rustc_mir_dataflow::impls::MaybeInitializedPlaces; +use rustc_mir_dataflow::move_paths::{HasMoveData, MoveData, MovePathIndex}; +use rustc_mir_dataflow::ResultsCursor; + +use crate::{ + region_infer::values::{self, PointIndex, RegionValueElements}, + type_check::liveness::local_use_map::LocalUseMap, + type_check::liveness::polonius, + type_check::NormalizeLocation, + type_check::TypeChecker, +}; + +/// This is the heart of the liveness computation. For each variable X +/// that requires a liveness computation, it walks over all the uses +/// of X and does a reverse depth-first search ("trace") through the +/// MIR. This search stops when we find a definition of that variable. +/// The points visited in this search is the USE-LIVE set for the variable; +/// of those points is added to all the regions that appear in the variable's +/// type. +/// +/// We then also walks through each *drop* of those variables and does +/// another search, stopping when we reach a use or definition. This +/// is the DROP-LIVE set of points. Each of the points in the +/// DROP-LIVE set are to the liveness sets for regions found in the +/// `dropck_outlives` result of the variable's type (in particular, +/// this respects `#[may_dangle]` annotations). +pub(super) fn trace<'mir, 'tcx>( + typeck: &mut TypeChecker<'_, 'tcx>, + body: &Body<'tcx>, + elements: &Rc<RegionValueElements>, + flow_inits: &mut ResultsCursor<'mir, 'tcx, MaybeInitializedPlaces<'mir, 'tcx>>, + move_data: &MoveData<'tcx>, + relevant_live_locals: Vec<Local>, + boring_locals: Vec<Local>, + polonius_drop_used: Option<Vec<(Local, Location)>>, +) { + debug!("trace()"); + + let local_use_map = &LocalUseMap::build(&relevant_live_locals, elements, body); + + let cx = LivenessContext { + typeck, + body, + flow_inits, + elements, + local_use_map, + move_data, + drop_data: FxHashMap::default(), + }; + + let mut results = LivenessResults::new(cx); + + if let Some(drop_used) = polonius_drop_used { + results.add_extra_drop_facts(drop_used, relevant_live_locals.iter().copied().collect()) + } + + results.compute_for_all_locals(relevant_live_locals); + + results.dropck_boring_locals(boring_locals); +} + +/// Contextual state for the type-liveness generator. +struct LivenessContext<'me, 'typeck, 'flow, 'tcx> { + /// Current type-checker, giving us our inference context etc. + typeck: &'me mut TypeChecker<'typeck, 'tcx>, + + /// Defines the `PointIndex` mapping + elements: &'me RegionValueElements, + + /// MIR we are analyzing. + body: &'me Body<'tcx>, + + /// Mapping to/from the various indices used for initialization tracking. + move_data: &'me MoveData<'tcx>, + + /// Cache for the results of `dropck_outlives` query. + drop_data: FxHashMap<Ty<'tcx>, DropData<'tcx>>, + + /// Results of dataflow tracking which variables (and paths) have been + /// initialized. + flow_inits: &'me mut ResultsCursor<'flow, 'tcx, MaybeInitializedPlaces<'flow, 'tcx>>, + + /// Index indicating where each variable is assigned, used, or + /// dropped. + local_use_map: &'me LocalUseMap, +} + +struct DropData<'tcx> { + dropck_result: DropckOutlivesResult<'tcx>, + region_constraint_data: Option<&'tcx QueryRegionConstraints<'tcx>>, +} + +struct LivenessResults<'me, 'typeck, 'flow, 'tcx> { + cx: LivenessContext<'me, 'typeck, 'flow, 'tcx>, + + /// Set of points that define the current local. + defs: HybridBitSet<PointIndex>, + + /// Points where the current variable is "use live" -- meaning + /// that there is a future "full use" that may use its value. + use_live_at: IntervalSet<PointIndex>, + + /// Points where the current variable is "drop live" -- meaning + /// that there is no future "full use" that may use its value, but + /// there is a future drop. + drop_live_at: IntervalSet<PointIndex>, + + /// Locations where drops may occur. + drop_locations: Vec<Location>, + + /// Stack used when doing (reverse) DFS. + stack: Vec<PointIndex>, +} + +impl<'me, 'typeck, 'flow, 'tcx> LivenessResults<'me, 'typeck, 'flow, 'tcx> { + fn new(cx: LivenessContext<'me, 'typeck, 'flow, 'tcx>) -> Self { + let num_points = cx.elements.num_points(); + LivenessResults { + cx, + defs: HybridBitSet::new_empty(num_points), + use_live_at: IntervalSet::new(num_points), + drop_live_at: IntervalSet::new(num_points), + drop_locations: vec![], + stack: vec![], + } + } + + fn compute_for_all_locals(&mut self, relevant_live_locals: Vec<Local>) { + for local in relevant_live_locals { + self.reset_local_state(); + self.add_defs_for(local); + self.compute_use_live_points_for(local); + self.compute_drop_live_points_for(local); + + let local_ty = self.cx.body.local_decls[local].ty; + + if !self.use_live_at.is_empty() { + self.cx.add_use_live_facts_for(local_ty, &self.use_live_at); + } + + if !self.drop_live_at.is_empty() { + self.cx.add_drop_live_facts_for( + local, + local_ty, + &self.drop_locations, + &self.drop_live_at, + ); + } + } + } + + // Runs dropck for locals whose liveness isn't relevant. This is + // necessary to eagerly detect unbound recursion during drop glue computation. + fn dropck_boring_locals(&mut self, boring_locals: Vec<Local>) { + for local in boring_locals { + let local_ty = self.cx.body.local_decls[local].ty; + let drop_data = self.cx.drop_data.entry(local_ty).or_insert_with({ + let typeck = &mut self.cx.typeck; + move || LivenessContext::compute_drop_data(typeck, local_ty) + }); + + drop_data.dropck_result.report_overflows( + self.cx.typeck.infcx.tcx, + self.cx.body.local_decls[local].source_info.span, + local_ty, + ); + } + } + + /// Add extra drop facts needed for Polonius. + /// + /// Add facts for all locals with free regions, since regions may outlive + /// the function body only at certain nodes in the CFG. + fn add_extra_drop_facts( + &mut self, + drop_used: Vec<(Local, Location)>, + relevant_live_locals: FxHashSet<Local>, + ) { + let locations = IntervalSet::new(self.cx.elements.num_points()); + + for (local, location) in drop_used { + if !relevant_live_locals.contains(&local) { + let local_ty = self.cx.body.local_decls[local].ty; + if local_ty.has_free_regions() { + self.cx.add_drop_live_facts_for(local, local_ty, &[location], &locations); + } + } + } + } + + /// Clear the value of fields that are "per local variable". + fn reset_local_state(&mut self) { + self.defs.clear(); + self.use_live_at.clear(); + self.drop_live_at.clear(); + self.drop_locations.clear(); + assert!(self.stack.is_empty()); + } + + /// Adds the definitions of `local` into `self.defs`. + fn add_defs_for(&mut self, local: Local) { + for def in self.cx.local_use_map.defs(local) { + debug!("- defined at {:?}", def); + self.defs.insert(def); + } + } + + /// Computes all points where local is "use live" -- meaning its + /// current value may be used later (except by a drop). This is + /// done by walking backwards from each use of `local` until we + /// find a `def` of local. + /// + /// Requires `add_defs_for(local)` to have been executed. + fn compute_use_live_points_for(&mut self, local: Local) { + debug!("compute_use_live_points_for(local={:?})", local); + + self.stack.extend(self.cx.local_use_map.uses(local)); + while let Some(p) = self.stack.pop() { + // We are live in this block from the closest to us of: + // + // * Inclusively, the block start + // * Exclusively, the previous definition (if it's in this block) + // * Exclusively, the previous live_at setting (an optimization) + let block_start = self.cx.elements.to_block_start(p); + let previous_defs = self.defs.last_set_in(block_start..=p); + let previous_live_at = self.use_live_at.last_set_in(block_start..=p); + + let exclusive_start = match (previous_defs, previous_live_at) { + (Some(a), Some(b)) => Some(std::cmp::max(a, b)), + (Some(a), None) | (None, Some(a)) => Some(a), + (None, None) => None, + }; + + if let Some(exclusive) = exclusive_start { + self.use_live_at.insert_range(exclusive + 1..=p); + + // If we have a bound after the start of the block, we should + // not add the predecessors for this block. + continue; + } else { + // Add all the elements of this block. + self.use_live_at.insert_range(block_start..=p); + + // Then add the predecessors for this block, which are the + // terminators of predecessor basic blocks. Push those onto the + // stack so that the next iteration(s) will process them. + + let block = self.cx.elements.to_location(block_start).block; + self.stack.extend( + self.cx.body.basic_blocks.predecessors()[block] + .iter() + .map(|&pred_bb| self.cx.body.terminator_loc(pred_bb)) + .map(|pred_loc| self.cx.elements.point_from_location(pred_loc)), + ); + } + } + } + + /// Computes all points where local is "drop live" -- meaning its + /// current value may be dropped later (but not used). This is + /// done by iterating over the drops of `local` where `local` (or + /// some subpart of `local`) is initialized. For each such drop, + /// we walk backwards until we find a point where `local` is + /// either defined or use-live. + /// + /// Requires `compute_use_live_points_for` and `add_defs_for` to + /// have been executed. + fn compute_drop_live_points_for(&mut self, local: Local) { + debug!("compute_drop_live_points_for(local={:?})", local); + + let mpi = self.cx.move_data.rev_lookup.find_local(local); + debug!("compute_drop_live_points_for: mpi = {:?}", mpi); + + // Find the drops where `local` is initialized. + for drop_point in self.cx.local_use_map.drops(local) { + let location = self.cx.elements.to_location(drop_point); + debug_assert_eq!(self.cx.body.terminator_loc(location.block), location,); + + if self.cx.initialized_at_terminator(location.block, mpi) { + if self.drop_live_at.insert(drop_point) { + self.drop_locations.push(location); + self.stack.push(drop_point); + } + } + } + + debug!("compute_drop_live_points_for: drop_locations={:?}", self.drop_locations); + + // Reverse DFS. But for drops, we do it a bit differently. + // The stack only ever stores *terminators of blocks*. Within + // a block, we walk back the statements in an inner loop. + while let Some(term_point) = self.stack.pop() { + self.compute_drop_live_points_for_block(mpi, term_point); + } + } + + /// Executes one iteration of the drop-live analysis loop. + /// + /// The parameter `mpi` is the `MovePathIndex` of the local variable + /// we are currently analyzing. + /// + /// The point `term_point` represents some terminator in the MIR, + /// where the local `mpi` is drop-live on entry to that terminator. + /// + /// This method adds all drop-live points within the block and -- + /// where applicable -- pushes the terminators of preceding blocks + /// onto `self.stack`. + fn compute_drop_live_points_for_block(&mut self, mpi: MovePathIndex, term_point: PointIndex) { + debug!( + "compute_drop_live_points_for_block(mpi={:?}, term_point={:?})", + self.cx.move_data.move_paths[mpi].place, + self.cx.elements.to_location(term_point), + ); + + // We are only invoked with terminators where `mpi` is + // drop-live on entry. + debug_assert!(self.drop_live_at.contains(term_point)); + + // Otherwise, scan backwards through the statements in the + // block. One of them may be either a definition or use + // live point. + let term_location = self.cx.elements.to_location(term_point); + debug_assert_eq!(self.cx.body.terminator_loc(term_location.block), term_location,); + let block = term_location.block; + let entry_point = self.cx.elements.entry_point(term_location.block); + for p in (entry_point..term_point).rev() { + debug!("compute_drop_live_points_for_block: p = {:?}", self.cx.elements.to_location(p)); + + if self.defs.contains(p) { + debug!("compute_drop_live_points_for_block: def site"); + return; + } + + if self.use_live_at.contains(p) { + debug!("compute_drop_live_points_for_block: use-live at {:?}", p); + return; + } + + if !self.drop_live_at.insert(p) { + debug!("compute_drop_live_points_for_block: already drop-live"); + return; + } + } + + let body = self.cx.body; + for &pred_block in body.basic_blocks.predecessors()[block].iter() { + debug!("compute_drop_live_points_for_block: pred_block = {:?}", pred_block,); + + // Check whether the variable is (at least partially) + // initialized at the exit of this predecessor. If so, we + // want to enqueue it on our list. If not, go check the + // next block. + // + // Note that we only need to check whether `live_local` + // became de-initialized at basic block boundaries. If it + // were to become de-initialized within the block, that + // would have been a "use-live" transition in the earlier + // loop, and we'd have returned already. + // + // NB. It's possible that the pred-block ends in a call + // which stores to the variable; in that case, the + // variable may be uninitialized "at exit" because this + // call only considers the *unconditional effects* of the + // terminator. *But*, in that case, the terminator is also + // a *definition* of the variable, in which case we want + // to stop the search anyhow. (But see Note 1 below.) + if !self.cx.initialized_at_exit(pred_block, mpi) { + debug!("compute_drop_live_points_for_block: not initialized"); + continue; + } + + let pred_term_loc = self.cx.body.terminator_loc(pred_block); + let pred_term_point = self.cx.elements.point_from_location(pred_term_loc); + + // If the terminator of this predecessor either *assigns* + // our value or is a "normal use", then stop. + if self.defs.contains(pred_term_point) { + debug!("compute_drop_live_points_for_block: defined at {:?}", pred_term_loc); + continue; + } + + if self.use_live_at.contains(pred_term_point) { + debug!("compute_drop_live_points_for_block: use-live at {:?}", pred_term_loc); + continue; + } + + // Otherwise, we are drop-live on entry to the terminator, + // so walk it. + if self.drop_live_at.insert(pred_term_point) { + debug!("compute_drop_live_points_for_block: pushed to stack"); + self.stack.push(pred_term_point); + } + } + + // Note 1. There is a weird scenario that you might imagine + // being problematic here, but which actually cannot happen. + // The problem would be if we had a variable that *is* initialized + // (but dead) on entry to the terminator, and where the current value + // will be dropped in the case of unwind. In that case, we ought to + // consider `X` to be drop-live in between the last use and call. + // Here is the example: + // + // ``` + // BB0 { + // X = ... + // use(X); // last use + // ... // <-- X ought to be drop-live here + // X = call() goto BB1 unwind BB2 + // } + // + // BB1 { + // DROP(X) + // } + // + // BB2 { + // DROP(X) + // } + // ``` + // + // However, the current code would, when walking back from BB2, + // simply stop and never explore BB0. This seems bad! But it turns + // out this code is flawed anyway -- note that the existing value of + // `X` would leak in the case where unwinding did *not* occur. + // + // What we *actually* generate is a store to a temporary + // for the call (`TMP = call()...`) and then a + // `DropAndReplace` to swap that with `X` + // (`DropAndReplace` has very particular semantics). + } +} + +impl<'tcx> LivenessContext<'_, '_, '_, 'tcx> { + /// Returns `true` if the local variable (or some part of it) is initialized at the current + /// cursor position. Callers should call one of the `seek` methods immediately before to point + /// the cursor to the desired location. + fn initialized_at_curr_loc(&self, mpi: MovePathIndex) -> bool { + let state = self.flow_inits.get(); + if state.contains(mpi) { + return true; + } + + let move_paths = &self.flow_inits.analysis().move_data().move_paths; + move_paths[mpi].find_descendant(&move_paths, |mpi| state.contains(mpi)).is_some() + } + + /// Returns `true` if the local variable (or some part of it) is initialized in + /// the terminator of `block`. We need to check this to determine if a + /// DROP of some local variable will have an effect -- note that + /// drops, as they may unwind, are always terminators. + fn initialized_at_terminator(&mut self, block: BasicBlock, mpi: MovePathIndex) -> bool { + self.flow_inits.seek_before_primary_effect(self.body.terminator_loc(block)); + self.initialized_at_curr_loc(mpi) + } + + /// Returns `true` if the path `mpi` (or some part of it) is initialized at + /// the exit of `block`. + /// + /// **Warning:** Does not account for the result of `Call` + /// instructions. + fn initialized_at_exit(&mut self, block: BasicBlock, mpi: MovePathIndex) -> bool { + self.flow_inits.seek_after_primary_effect(self.body.terminator_loc(block)); + self.initialized_at_curr_loc(mpi) + } + + /// Stores the result that all regions in `value` are live for the + /// points `live_at`. + fn add_use_live_facts_for( + &mut self, + value: impl TypeVisitable<'tcx>, + live_at: &IntervalSet<PointIndex>, + ) { + debug!("add_use_live_facts_for(value={:?})", value); + + Self::make_all_regions_live(self.elements, &mut self.typeck, value, live_at) + } + + /// Some variable with type `live_ty` is "drop live" at `location` + /// -- i.e., it may be dropped later. This means that *some* of + /// the regions in its type must be live at `location`. The + /// precise set will depend on the dropck constraints, and in + /// particular this takes `#[may_dangle]` into account. + fn add_drop_live_facts_for( + &mut self, + dropped_local: Local, + dropped_ty: Ty<'tcx>, + drop_locations: &[Location], + live_at: &IntervalSet<PointIndex>, + ) { + debug!( + "add_drop_live_constraint(\ + dropped_local={:?}, \ + dropped_ty={:?}, \ + drop_locations={:?}, \ + live_at={:?})", + dropped_local, + dropped_ty, + drop_locations, + values::location_set_str(self.elements, live_at.iter()), + ); + + let drop_data = self.drop_data.entry(dropped_ty).or_insert_with({ + let typeck = &mut self.typeck; + move || Self::compute_drop_data(typeck, dropped_ty) + }); + + if let Some(data) = &drop_data.region_constraint_data { + for &drop_location in drop_locations { + self.typeck.push_region_constraints( + drop_location.to_locations(), + ConstraintCategory::Boring, + data, + ); + } + } + + drop_data.dropck_result.report_overflows( + self.typeck.infcx.tcx, + self.body.source_info(*drop_locations.first().unwrap()).span, + dropped_ty, + ); + + // All things in the `outlives` array may be touched by + // the destructor and must be live at this point. + for &kind in &drop_data.dropck_result.kinds { + Self::make_all_regions_live(self.elements, &mut self.typeck, kind, live_at); + + polonius::add_drop_of_var_derefs_origin(&mut self.typeck, dropped_local, &kind); + } + } + + fn make_all_regions_live( + elements: &RegionValueElements, + typeck: &mut TypeChecker<'_, 'tcx>, + value: impl TypeVisitable<'tcx>, + live_at: &IntervalSet<PointIndex>, + ) { + debug!("make_all_regions_live(value={:?})", value); + debug!( + "make_all_regions_live: live_at={}", + values::location_set_str(elements, live_at.iter()), + ); + + let tcx = typeck.tcx(); + tcx.for_each_free_region(&value, |live_region| { + let live_region_vid = + typeck.borrowck_context.universal_regions.to_region_vid(live_region); + typeck + .borrowck_context + .constraints + .liveness_constraints + .add_elements(live_region_vid, live_at); + }); + } + + fn compute_drop_data( + typeck: &mut TypeChecker<'_, 'tcx>, + dropped_ty: Ty<'tcx>, + ) -> DropData<'tcx> { + debug!("compute_drop_data(dropped_ty={:?})", dropped_ty,); + + let param_env = typeck.param_env; + let TypeOpOutput { output, constraints, .. } = + param_env.and(DropckOutlives::new(dropped_ty)).fully_perform(typeck.infcx).unwrap(); + + DropData { dropck_result: output, region_constraint_data: constraints } + } +} diff --git a/compiler/rustc_borrowck/src/type_check/mod.rs b/compiler/rustc_borrowck/src/type_check/mod.rs new file mode 100644 index 000000000..d32b1edcd --- /dev/null +++ b/compiler/rustc_borrowck/src/type_check/mod.rs @@ -0,0 +1,2721 @@ +//! This pass type-checks the MIR to ensure it is not broken. + +use std::rc::Rc; +use std::{fmt, iter, mem}; + +use either::Either; + +use hir::OpaqueTyOrigin; +use rustc_data_structures::frozen::Frozen; +use rustc_data_structures::fx::{FxHashMap, FxHashSet}; +use rustc_data_structures::vec_map::VecMap; +use rustc_hir as hir; +use rustc_hir::def::DefKind; +use rustc_hir::def_id::LocalDefId; +use rustc_hir::lang_items::LangItem; +use rustc_index::vec::{Idx, IndexVec}; +use rustc_infer::infer::canonical::QueryRegionConstraints; +use rustc_infer::infer::outlives::env::RegionBoundPairs; +use rustc_infer::infer::region_constraints::RegionConstraintData; +use rustc_infer::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind}; +use rustc_infer::infer::{ + InferCtxt, InferOk, LateBoundRegion, LateBoundRegionConversionTime, NllRegionVariableOrigin, +}; +use rustc_middle::mir::tcx::PlaceTy; +use rustc_middle::mir::visit::{NonMutatingUseContext, PlaceContext, Visitor}; +use rustc_middle::mir::AssertKind; +use rustc_middle::mir::*; +use rustc_middle::ty::adjustment::PointerCast; +use rustc_middle::ty::cast::CastTy; +use rustc_middle::ty::subst::{GenericArgKind, SubstsRef, UserSubsts}; +use rustc_middle::ty::visit::TypeVisitable; +use rustc_middle::ty::{ + self, CanonicalUserTypeAnnotation, CanonicalUserTypeAnnotations, OpaqueHiddenType, + OpaqueTypeKey, RegionVid, ToPredicate, Ty, TyCtxt, UserType, UserTypeAnnotationIndex, +}; +use rustc_span::def_id::CRATE_DEF_ID; +use rustc_span::{Span, DUMMY_SP}; +use rustc_target::abi::VariantIdx; +use rustc_trait_selection::traits::query::type_op; +use rustc_trait_selection::traits::query::type_op::custom::scrape_region_constraints; +use rustc_trait_selection::traits::query::type_op::custom::CustomTypeOp; +use rustc_trait_selection::traits::query::type_op::{TypeOp, TypeOpOutput}; +use rustc_trait_selection::traits::query::Fallible; +use rustc_trait_selection::traits::PredicateObligation; + +use rustc_mir_dataflow::impls::MaybeInitializedPlaces; +use rustc_mir_dataflow::move_paths::MoveData; +use rustc_mir_dataflow::ResultsCursor; + +use crate::session_diagnostics::MoveUnsized; +use crate::{ + borrow_set::BorrowSet, + constraints::{OutlivesConstraint, OutlivesConstraintSet}, + diagnostics::UniverseInfo, + facts::AllFacts, + location::LocationTable, + member_constraints::MemberConstraintSet, + nll::ToRegionVid, + path_utils, + region_infer::values::{ + LivenessValues, PlaceholderIndex, PlaceholderIndices, RegionValueElements, + }, + region_infer::{ClosureRegionRequirementsExt, TypeTest}, + type_check::free_region_relations::{CreateResult, UniversalRegionRelations}, + universal_regions::{DefiningTy, UniversalRegions}, + Upvar, +}; + +macro_rules! span_mirbug { + ($context:expr, $elem:expr, $($message:tt)*) => ({ + $crate::type_check::mirbug( + $context.tcx(), + $context.last_span, + &format!( + "broken MIR in {:?} ({:?}): {}", + $context.body().source.def_id(), + $elem, + format_args!($($message)*), + ), + ) + }) +} + +macro_rules! span_mirbug_and_err { + ($context:expr, $elem:expr, $($message:tt)*) => ({ + { + span_mirbug!($context, $elem, $($message)*); + $context.error() + } + }) +} + +mod canonical; +mod constraint_conversion; +pub mod free_region_relations; +mod input_output; +pub(crate) mod liveness; +mod relate_tys; + +/// Type checks the given `mir` in the context of the inference +/// context `infcx`. Returns any region constraints that have yet to +/// be proven. This result includes liveness constraints that +/// ensure that regions appearing in the types of all local variables +/// are live at all points where that local variable may later be +/// used. +/// +/// This phase of type-check ought to be infallible -- this is because +/// the original, HIR-based type-check succeeded. So if any errors +/// occur here, we will get a `bug!` reported. +/// +/// # Parameters +/// +/// - `infcx` -- inference context to use +/// - `param_env` -- parameter environment to use for trait solving +/// - `body` -- MIR body to type-check +/// - `promoted` -- map of promoted constants within `body` +/// - `universal_regions` -- the universal regions from `body`s function signature +/// - `location_table` -- MIR location map of `body` +/// - `borrow_set` -- information about borrows occurring in `body` +/// - `all_facts` -- when using Polonius, this is the generated set of Polonius facts +/// - `flow_inits` -- results of a maybe-init dataflow analysis +/// - `move_data` -- move-data constructed when performing the maybe-init dataflow analysis +/// - `elements` -- MIR region map +pub(crate) fn type_check<'mir, 'tcx>( + infcx: &InferCtxt<'_, 'tcx>, + param_env: ty::ParamEnv<'tcx>, + body: &Body<'tcx>, + promoted: &IndexVec<Promoted, Body<'tcx>>, + universal_regions: &Rc<UniversalRegions<'tcx>>, + location_table: &LocationTable, + borrow_set: &BorrowSet<'tcx>, + all_facts: &mut Option<AllFacts>, + flow_inits: &mut ResultsCursor<'mir, 'tcx, MaybeInitializedPlaces<'mir, 'tcx>>, + move_data: &MoveData<'tcx>, + elements: &Rc<RegionValueElements>, + upvars: &[Upvar<'tcx>], + use_polonius: bool, +) -> 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(), + liveness_constraints: LivenessValues::new(elements.clone()), + outlives_constraints: OutlivesConstraintSet::default(), + member_constraints: MemberConstraintSet::default(), + closure_bounds_mapping: Default::default(), + type_tests: Vec::default(), + universe_causes, + }; + + let CreateResult { + universal_region_relations, + region_bound_pairs, + normalized_inputs_and_output, + } = free_region_relations::create( + infcx, + param_env, + implicit_region_bound, + universal_regions, + &mut constraints, + ); + + debug!(?normalized_inputs_and_output); + + for u in ty::UniverseIndex::ROOT..infcx.universe() { + let info = UniverseInfo::other(); + constraints.universe_causes.insert(u, info); + } + + let mut borrowck_context = BorrowCheckContext { + universal_regions, + location_table, + borrow_set, + all_facts, + constraints: &mut constraints, + upvars, + }; + + let opaque_type_values = type_check_internal( + infcx, + param_env, + body, + promoted, + ®ion_bound_pairs, + implicit_region_bound, + &mut borrowck_context, + |mut cx| { + debug!("inside extra closure of type_check_internal"); + cx.equate_inputs_and_outputs(&body, universal_regions, &normalized_inputs_and_output); + liveness::generate( + &mut cx, + body, + elements, + flow_inits, + move_data, + location_table, + use_polonius, + ); + + translate_outlives_facts(&mut cx); + let opaque_type_values = + infcx.inner.borrow_mut().opaque_type_storage.take_opaque_types(); + + opaque_type_values + .into_iter() + .map(|(opaque_type_key, decl)| { + cx.fully_perform_op( + Locations::All(body.span), + ConstraintCategory::OpaqueType, + CustomTypeOp::new( + |infcx| { + infcx.register_member_constraints( + param_env, + opaque_type_key, + decl.hidden_type.ty, + decl.hidden_type.span, + ); + Ok(InferOk { value: (), obligations: vec![] }) + }, + || "opaque_type_map".to_string(), + ), + ) + .unwrap(); + let mut 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_infer_types_or_consts() { + infcx.tcx.sess.delay_span_bug( + decl.hidden_type.span, + &format!("could not resolve {:#?}", hidden_type.ty.kind()), + ); + hidden_type.ty = infcx.tcx.ty_error(); + } + + (opaque_type_key, (hidden_type, decl.origin)) + }) + .collect() + }, + ); + + MirTypeckResults { constraints, universal_region_relations, opaque_type_values } +} + +#[instrument( + skip(infcx, body, promoted, region_bound_pairs, borrowck_context, extra), + level = "debug" +)] +fn type_check_internal<'a, 'tcx, R>( + infcx: &'a InferCtxt<'a, 'tcx>, + param_env: ty::ParamEnv<'tcx>, + body: &'a Body<'tcx>, + promoted: &'a IndexVec<Promoted, Body<'tcx>>, + region_bound_pairs: &'a RegionBoundPairs<'tcx>, + implicit_region_bound: ty::Region<'tcx>, + borrowck_context: &'a mut BorrowCheckContext<'a, 'tcx>, + extra: impl FnOnce(TypeChecker<'a, 'tcx>) -> R, +) -> R { + debug!("body: {:#?}", body); + let mut checker = TypeChecker::new( + infcx, + body, + param_env, + region_bound_pairs, + implicit_region_bound, + borrowck_context, + ); + let errors_reported = { + let mut verifier = TypeVerifier::new(&mut checker, promoted); + verifier.visit_body(&body); + verifier.errors_reported + }; + + if !errors_reported { + // if verifier failed, don't do further checks to avoid ICEs + checker.typeck_mir(body); + } + + extra(checker) +} + +fn translate_outlives_facts(typeck: &mut TypeChecker<'_, '_>) { + let cx = &mut typeck.borrowck_context; + if let Some(facts) = cx.all_facts { + let _prof_timer = typeck.infcx.tcx.prof.generic_activity("polonius_fact_generation"); + let location_table = cx.location_table; + facts.subset_base.extend(cx.constraints.outlives_constraints.outlives().iter().flat_map( + |constraint: &OutlivesConstraint<'_>| { + if let Some(from_location) = constraint.locations.from_location() { + Either::Left(iter::once(( + constraint.sup, + constraint.sub, + location_table.mid_index(from_location), + ))) + } else { + Either::Right( + location_table + .all_points() + .map(move |location| (constraint.sup, constraint.sub, location)), + ) + } + }, + )); + } +} + +#[track_caller] +fn mirbug(tcx: TyCtxt<'_>, span: Span, msg: &str) { + // We sometimes see MIR failures (notably predicate failures) due to + // the fact that we check rvalue sized predicates here. So use `delay_span_bug` + // to avoid reporting bugs in those cases. + tcx.sess.diagnostic().delay_span_bug(span, msg); +} + +enum FieldAccessError { + OutOfRange { field_count: usize }, +} + +/// Verifies that MIR types are sane to not crash further checks. +/// +/// The sanitize_XYZ methods here take an MIR object and compute its +/// type, calling `span_mirbug` and returning an error type if there +/// is a problem. +struct TypeVerifier<'a, 'b, 'tcx> { + cx: &'a mut TypeChecker<'b, 'tcx>, + promoted: &'b IndexVec<Promoted, Body<'tcx>>, + last_span: Span, + errors_reported: bool, +} + +impl<'a, 'b, 'tcx> Visitor<'tcx> for TypeVerifier<'a, 'b, 'tcx> { + fn visit_span(&mut self, span: Span) { + if !span.is_dummy() { + self.last_span = span; + } + } + + fn visit_place(&mut self, place: &Place<'tcx>, context: PlaceContext, location: Location) { + self.sanitize_place(place, location, context); + } + + fn visit_constant(&mut self, constant: &Constant<'tcx>, location: Location) { + self.super_constant(constant, location); + let ty = self.sanitize_type(constant, constant.literal.ty()); + + self.cx.infcx.tcx.for_each_free_region(&ty, |live_region| { + let live_region_vid = + self.cx.borrowck_context.universal_regions.to_region_vid(live_region); + self.cx + .borrowck_context + .constraints + .liveness_constraints + .add_element(live_region_vid, location); + }); + + // HACK(compiler-errors): Constants that are gathered into Body.required_consts + // have their locations erased... + let locations = if location != Location::START { + location.to_locations() + } else { + Locations::All(constant.span) + }; + + if let Some(annotation_index) = constant.user_ty { + if let Err(terr) = self.cx.relate_type_and_user_type( + constant.literal.ty(), + ty::Variance::Invariant, + &UserTypeProjection { base: annotation_index, projs: vec![] }, + locations, + ConstraintCategory::Boring, + ) { + let annotation = &self.cx.user_type_annotations[annotation_index]; + span_mirbug!( + self, + constant, + "bad constant user type {:?} vs {:?}: {:?}", + annotation, + constant.literal.ty(), + terr, + ); + } + } else { + let tcx = self.tcx(); + let maybe_uneval = match constant.literal { + ConstantKind::Ty(ct) => match ct.kind() { + ty::ConstKind::Unevaluated(uv) => Some(uv), + _ => None, + }, + _ => None, + }; + if let Some(uv) = maybe_uneval { + if let Some(promoted) = uv.promoted { + let check_err = |verifier: &mut TypeVerifier<'a, 'b, 'tcx>, + promoted: &Body<'tcx>, + ty, + san_ty| { + if let Err(terr) = + verifier.cx.eq_types(ty, san_ty, locations, ConstraintCategory::Boring) + { + span_mirbug!( + verifier, + promoted, + "bad promoted type ({:?}: {:?}): {:?}", + ty, + san_ty, + terr + ); + }; + }; + + if !self.errors_reported { + let promoted_body = &self.promoted[promoted]; + self.sanitize_promoted(promoted_body, location); + + let promoted_ty = promoted_body.return_ty(); + check_err(self, promoted_body, ty, promoted_ty); + } + } else { + if let Err(terr) = self.cx.fully_perform_op( + locations, + ConstraintCategory::Boring, + self.cx.param_env.and(type_op::ascribe_user_type::AscribeUserType::new( + constant.literal.ty(), + uv.def.did, + UserSubsts { substs: uv.substs, user_self_ty: None }, + )), + ) { + span_mirbug!( + self, + constant, + "bad constant type {:?} ({:?})", + constant, + terr + ); + } + } + } else if let Some(static_def_id) = constant.check_static_ptr(tcx) { + let unnormalized_ty = tcx.type_of(static_def_id); + let normalized_ty = self.cx.normalize(unnormalized_ty, locations); + let literal_ty = constant.literal.ty().builtin_deref(true).unwrap().ty; + + if let Err(terr) = self.cx.eq_types( + literal_ty, + normalized_ty, + locations, + ConstraintCategory::Boring, + ) { + span_mirbug!(self, constant, "bad static type {:?} ({:?})", constant, terr); + } + } + + if let ty::FnDef(def_id, substs) = *constant.literal.ty().kind() { + let instantiated_predicates = tcx.predicates_of(def_id).instantiate(tcx, substs); + self.cx.normalize_and_prove_instantiated_predicates( + def_id, + instantiated_predicates, + locations, + ); + } + } + } + + fn visit_rvalue(&mut self, rvalue: &Rvalue<'tcx>, location: Location) { + self.super_rvalue(rvalue, location); + let rval_ty = rvalue.ty(self.body(), self.tcx()); + self.sanitize_type(rvalue, rval_ty); + } + + fn visit_local_decl(&mut self, local: Local, local_decl: &LocalDecl<'tcx>) { + self.super_local_decl(local, local_decl); + self.sanitize_type(local_decl, local_decl.ty); + + if let Some(user_ty) = &local_decl.user_ty { + for (user_ty, span) in user_ty.projections_and_spans() { + let ty = if !local_decl.is_nonref_binding() { + // If we have a binding of the form `let ref x: T = ..` + // then remove the outermost reference so we can check the + // type annotation for the remaining type. + if let ty::Ref(_, rty, _) = local_decl.ty.kind() { + *rty + } else { + bug!("{:?} with ref binding has wrong type {}", local, local_decl.ty); + } + } else { + local_decl.ty + }; + + if let Err(terr) = self.cx.relate_type_and_user_type( + ty, + ty::Variance::Invariant, + user_ty, + Locations::All(*span), + ConstraintCategory::TypeAnnotation, + ) { + span_mirbug!( + self, + local, + "bad user type on variable {:?}: {:?} != {:?} ({:?})", + local, + local_decl.ty, + local_decl.user_ty, + terr, + ); + } + } + } + } + + fn visit_body(&mut self, body: &Body<'tcx>) { + self.sanitize_type(&"return type", body.return_ty()); + for local_decl in &body.local_decls { + self.sanitize_type(local_decl, local_decl.ty); + } + if self.errors_reported { + return; + } + self.super_body(body); + } +} + +impl<'a, 'b, 'tcx> TypeVerifier<'a, 'b, 'tcx> { + fn new( + cx: &'a mut TypeChecker<'b, 'tcx>, + promoted: &'b IndexVec<Promoted, Body<'tcx>>, + ) -> Self { + TypeVerifier { promoted, last_span: cx.body.span, cx, errors_reported: false } + } + + fn body(&self) -> &Body<'tcx> { + self.cx.body + } + + fn tcx(&self) -> TyCtxt<'tcx> { + self.cx.infcx.tcx + } + + fn sanitize_type(&mut self, parent: &dyn fmt::Debug, ty: Ty<'tcx>) -> Ty<'tcx> { + if ty.has_escaping_bound_vars() || ty.references_error() { + span_mirbug_and_err!(self, parent, "bad type {:?}", ty) + } else { + ty + } + } + + /// Checks that the types internal to the `place` match up with + /// what would be expected. + fn sanitize_place( + &mut self, + place: &Place<'tcx>, + location: Location, + context: PlaceContext, + ) -> PlaceTy<'tcx> { + debug!("sanitize_place: {:?}", place); + + let mut place_ty = PlaceTy::from_ty(self.body().local_decls[place.local].ty); + + for elem in place.projection.iter() { + if place_ty.variant_index.is_none() { + if place_ty.ty.references_error() { + assert!(self.errors_reported); + return PlaceTy::from_ty(self.tcx().ty_error()); + } + } + place_ty = self.sanitize_projection(place_ty, elem, place, location); + } + + if let PlaceContext::NonMutatingUse(NonMutatingUseContext::Copy) = context { + let tcx = self.tcx(); + let trait_ref = ty::TraitRef { + def_id: tcx.require_lang_item(LangItem::Copy, Some(self.last_span)), + substs: tcx.mk_substs_trait(place_ty.ty, &[]), + }; + + // To have a `Copy` operand, the type `T` of the + // value must be `Copy`. Note that we prove that `T: Copy`, + // rather than using the `is_copy_modulo_regions` + // test. This is important because + // `is_copy_modulo_regions` ignores the resulting region + // obligations and assumes they pass. This can result in + // bounds from `Copy` impls being unsoundly ignored (e.g., + // #29149). Note that we decide to use `Copy` before knowing + // whether the bounds fully apply: in effect, the rule is + // that if a value of some type could implement `Copy`, then + // it must. + self.cx.prove_trait_ref( + trait_ref, + location.to_locations(), + ConstraintCategory::CopyBound, + ); + } + + place_ty + } + + fn sanitize_promoted(&mut self, promoted_body: &'b Body<'tcx>, location: Location) { + // Determine the constraints from the promoted MIR by running the type + // checker on the promoted MIR, then transfer the constraints back to + // the main MIR, changing the locations to the provided location. + + let parent_body = mem::replace(&mut self.cx.body, promoted_body); + + // Use new sets of constraints and closure bounds so that we can + // modify their locations. + let all_facts = &mut None; + let mut constraints = Default::default(); + let mut closure_bounds = Default::default(); + let mut liveness_constraints = + LivenessValues::new(Rc::new(RegionValueElements::new(&promoted_body))); + // Don't try to add borrow_region facts for the promoted MIR + + let mut swap_constraints = |this: &mut Self| { + mem::swap(this.cx.borrowck_context.all_facts, all_facts); + mem::swap( + &mut this.cx.borrowck_context.constraints.outlives_constraints, + &mut constraints, + ); + mem::swap( + &mut this.cx.borrowck_context.constraints.closure_bounds_mapping, + &mut closure_bounds, + ); + mem::swap( + &mut this.cx.borrowck_context.constraints.liveness_constraints, + &mut liveness_constraints, + ); + }; + + swap_constraints(self); + + self.visit_body(&promoted_body); + + if !self.errors_reported { + // if verifier failed, don't do further checks to avoid ICEs + self.cx.typeck_mir(promoted_body); + } + + self.cx.body = parent_body; + // Merge the outlives constraints back in, at the given location. + swap_constraints(self); + + let locations = location.to_locations(); + for constraint in constraints.outlives().iter() { + let mut constraint = constraint.clone(); + constraint.locations = locations; + if let ConstraintCategory::Return(_) + | ConstraintCategory::UseAsConst + | ConstraintCategory::UseAsStatic = constraint.category + { + // "Returning" from a promoted is an assignment to a + // temporary from the user's point of view. + constraint.category = ConstraintCategory::Boring; + } + self.cx.borrowck_context.constraints.outlives_constraints.push(constraint) + } + for region in liveness_constraints.rows() { + // If the region is live at at least one location in the promoted MIR, + // then add a liveness constraint to the main MIR for this region + // at the location provided as an argument to this method + if liveness_constraints.get_elements(region).next().is_some() { + self.cx + .borrowck_context + .constraints + .liveness_constraints + .add_element(region, location); + } + } + + if !closure_bounds.is_empty() { + let combined_bounds_mapping = + closure_bounds.into_iter().flat_map(|(_, value)| value).collect(); + let existing = self + .cx + .borrowck_context + .constraints + .closure_bounds_mapping + .insert(location, combined_bounds_mapping); + assert!(existing.is_none(), "Multiple promoteds/closures at the same location."); + } + } + + fn sanitize_projection( + &mut self, + base: PlaceTy<'tcx>, + pi: PlaceElem<'tcx>, + place: &Place<'tcx>, + location: Location, + ) -> PlaceTy<'tcx> { + debug!("sanitize_projection: {:?} {:?} {:?}", base, pi, place); + let tcx = self.tcx(); + let base_ty = base.ty; + match pi { + ProjectionElem::Deref => { + let deref_ty = base_ty.builtin_deref(true); + PlaceTy::from_ty(deref_ty.map(|t| t.ty).unwrap_or_else(|| { + span_mirbug_and_err!(self, place, "deref of non-pointer {:?}", base_ty) + })) + } + ProjectionElem::Index(i) => { + let index_ty = Place::from(i).ty(self.body(), tcx).ty; + if index_ty != tcx.types.usize { + PlaceTy::from_ty(span_mirbug_and_err!(self, i, "index by non-usize {:?}", i)) + } else { + PlaceTy::from_ty(base_ty.builtin_index().unwrap_or_else(|| { + span_mirbug_and_err!(self, place, "index of non-array {:?}", base_ty) + })) + } + } + ProjectionElem::ConstantIndex { .. } => { + // consider verifying in-bounds + PlaceTy::from_ty(base_ty.builtin_index().unwrap_or_else(|| { + span_mirbug_and_err!(self, place, "index of non-array {:?}", base_ty) + })) + } + ProjectionElem::Subslice { from, to, from_end } => { + PlaceTy::from_ty(match base_ty.kind() { + ty::Array(inner, _) => { + assert!(!from_end, "array subslices should not use from_end"); + tcx.mk_array(*inner, to - from) + } + ty::Slice(..) => { + assert!(from_end, "slice subslices should use from_end"); + base_ty + } + _ => span_mirbug_and_err!(self, place, "slice of non-array {:?}", base_ty), + }) + } + ProjectionElem::Downcast(maybe_name, index) => match base_ty.kind() { + ty::Adt(adt_def, _substs) if adt_def.is_enum() => { + if index.as_usize() >= adt_def.variants().len() { + PlaceTy::from_ty(span_mirbug_and_err!( + self, + place, + "cast to variant #{:?} but enum only has {:?}", + index, + adt_def.variants().len() + )) + } else { + PlaceTy { ty: base_ty, variant_index: Some(index) } + } + } + // We do not need to handle generators here, because this runs + // before the generator transform stage. + _ => { + let ty = if let Some(name) = maybe_name { + span_mirbug_and_err!( + self, + place, + "can't downcast {:?} as {:?}", + base_ty, + name + ) + } else { + span_mirbug_and_err!(self, place, "can't downcast {:?}", base_ty) + }; + PlaceTy::from_ty(ty) + } + }, + ProjectionElem::Field(field, fty) => { + let fty = self.sanitize_type(place, fty); + let fty = self.cx.normalize(fty, location); + match self.field_ty(place, base, field, location) { + Ok(ty) => { + let ty = self.cx.normalize(ty, location); + if let Err(terr) = self.cx.eq_types( + ty, + fty, + location.to_locations(), + ConstraintCategory::Boring, + ) { + span_mirbug!( + self, + place, + "bad field access ({:?}: {:?}): {:?}", + ty, + fty, + terr + ); + } + } + Err(FieldAccessError::OutOfRange { field_count }) => span_mirbug!( + self, + place, + "accessed field #{} but variant only has {}", + field.index(), + field_count + ), + } + PlaceTy::from_ty(fty) + } + } + } + + fn error(&mut self) -> Ty<'tcx> { + self.errors_reported = true; + self.tcx().ty_error() + } + + fn field_ty( + &mut self, + parent: &dyn fmt::Debug, + base_ty: PlaceTy<'tcx>, + field: Field, + location: Location, + ) -> Result<Ty<'tcx>, FieldAccessError> { + let tcx = self.tcx(); + + let (variant, substs) = match base_ty { + PlaceTy { ty, variant_index: Some(variant_index) } => match *ty.kind() { + ty::Adt(adt_def, substs) => (adt_def.variant(variant_index), substs), + ty::Generator(def_id, substs, _) => { + let mut variants = substs.as_generator().state_tys(def_id, tcx); + let Some(mut variant) = variants.nth(variant_index.into()) else { + bug!( + "variant_index of generator out of range: {:?}/{:?}", + variant_index, + substs.as_generator().state_tys(def_id, tcx).count() + ); + }; + return match variant.nth(field.index()) { + Some(ty) => Ok(ty), + None => Err(FieldAccessError::OutOfRange { field_count: variant.count() }), + }; + } + _ => bug!("can't have downcast of non-adt non-generator type"), + }, + PlaceTy { ty, variant_index: None } => match *ty.kind() { + ty::Adt(adt_def, substs) if !adt_def.is_enum() => { + (adt_def.variant(VariantIdx::new(0)), substs) + } + ty::Closure(_, substs) => { + return match substs + .as_closure() + .tupled_upvars_ty() + .tuple_fields() + .get(field.index()) + { + Some(&ty) => Ok(ty), + None => Err(FieldAccessError::OutOfRange { + field_count: substs.as_closure().upvar_tys().count(), + }), + }; + } + ty::Generator(_, substs, _) => { + // Only prefix fields (upvars and current state) are + // accessible without a variant index. + return match substs.as_generator().prefix_tys().nth(field.index()) { + Some(ty) => Ok(ty), + None => Err(FieldAccessError::OutOfRange { + field_count: substs.as_generator().prefix_tys().count(), + }), + }; + } + ty::Tuple(tys) => { + return match tys.get(field.index()) { + Some(&ty) => Ok(ty), + None => Err(FieldAccessError::OutOfRange { field_count: tys.len() }), + }; + } + _ => { + return Ok(span_mirbug_and_err!( + self, + parent, + "can't project out of {:?}", + base_ty + )); + } + }, + }; + + if let Some(field) = variant.fields.get(field.index()) { + Ok(self.cx.normalize(field.ty(tcx, substs), location)) + } else { + Err(FieldAccessError::OutOfRange { field_count: variant.fields.len() }) + } + } +} + +/// The MIR type checker. Visits the MIR and enforces all the +/// constraints needed for it to be valid and well-typed. Along the +/// way, it accrues region constraints -- these can later be used by +/// NLL region checking. +struct TypeChecker<'a, 'tcx> { + infcx: &'a InferCtxt<'a, 'tcx>, + param_env: ty::ParamEnv<'tcx>, + last_span: Span, + body: &'a Body<'tcx>, + /// User type annotations are shared between the main MIR and the MIR of + /// all of the promoted items. + user_type_annotations: &'a CanonicalUserTypeAnnotations<'tcx>, + region_bound_pairs: &'a RegionBoundPairs<'tcx>, + implicit_region_bound: ty::Region<'tcx>, + reported_errors: FxHashSet<(Ty<'tcx>, Span)>, + borrowck_context: &'a mut BorrowCheckContext<'a, 'tcx>, +} + +struct BorrowCheckContext<'a, 'tcx> { + pub(crate) universal_regions: &'a UniversalRegions<'tcx>, + location_table: &'a LocationTable, + all_facts: &'a mut Option<AllFacts>, + borrow_set: &'a BorrowSet<'tcx>, + pub(crate) constraints: &'a mut MirTypeckRegionConstraints<'tcx>, + upvars: &'a [Upvar<'tcx>], +} + +pub(crate) struct MirTypeckResults<'tcx> { + pub(crate) constraints: MirTypeckRegionConstraints<'tcx>, + pub(crate) universal_region_relations: Frozen<UniversalRegionRelations<'tcx>>, + pub(crate) opaque_type_values: + VecMap<OpaqueTypeKey<'tcx>, (OpaqueHiddenType<'tcx>, OpaqueTyOrigin)>, +} + +/// A collection of region constraints that must be satisfied for the +/// program to be considered well-typed. +pub(crate) struct MirTypeckRegionConstraints<'tcx> { + /// Maps from a `ty::Placeholder` to the corresponding + /// `PlaceholderIndex` bit that we will use for it. + /// + /// To keep everything in sync, do not insert this set + /// directly. Instead, use the `placeholder_region` helper. + pub(crate) placeholder_indices: PlaceholderIndices, + + /// Each time we add a placeholder to `placeholder_indices`, we + /// also create a corresponding "representative" region vid for + /// that wraps it. This vector tracks those. This way, when we + /// convert the same `ty::RePlaceholder(p)` twice, we can map to + /// the same underlying `RegionVid`. + pub(crate) placeholder_index_to_region: IndexVec<PlaceholderIndex, ty::Region<'tcx>>, + + /// In general, the type-checker is not responsible for enforcing + /// liveness constraints; this job falls to the region inferencer, + /// which performs a liveness analysis. However, in some limited + /// cases, the MIR type-checker creates temporary regions that do + /// not otherwise appear in the MIR -- in particular, the + /// late-bound regions that it instantiates at call-sites -- and + /// hence it must report on their liveness constraints. + pub(crate) liveness_constraints: LivenessValues<RegionVid>, + + pub(crate) outlives_constraints: OutlivesConstraintSet<'tcx>, + + pub(crate) member_constraints: MemberConstraintSet<'tcx, RegionVid>, + + pub(crate) closure_bounds_mapping: + FxHashMap<Location, FxHashMap<(RegionVid, RegionVid), (ConstraintCategory<'tcx>, Span)>>, + + pub(crate) universe_causes: FxHashMap<ty::UniverseIndex, UniverseInfo<'tcx>>, + + pub(crate) type_tests: Vec<TypeTest<'tcx>>, +} + +impl<'tcx> MirTypeckRegionConstraints<'tcx> { + fn placeholder_region( + &mut self, + infcx: &InferCtxt<'_, 'tcx>, + placeholder: ty::PlaceholderRegion, + ) -> ty::Region<'tcx> { + let placeholder_index = self.placeholder_indices.insert(placeholder); + match self.placeholder_index_to_region.get(placeholder_index) { + Some(&v) => v, + None => { + let origin = NllRegionVariableOrigin::Placeholder(placeholder); + let region = infcx.next_nll_region_var_in_universe(origin, placeholder.universe); + self.placeholder_index_to_region.push(region); + region + } + } + } +} + +/// The `Locations` type summarizes *where* region constraints are +/// required to hold. Normally, this is at a particular point which +/// created the obligation, but for constraints that the user gave, we +/// want the constraint to hold at all points. +#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)] +pub enum Locations { + /// Indicates that a type constraint should always be true. This + /// is particularly important in the new borrowck analysis for + /// things like the type of the return slot. Consider this + /// example: + /// + /// ```compile_fail,E0515 + /// fn foo<'a>(x: &'a u32) -> &'a u32 { + /// let y = 22; + /// return &y; // error + /// } + /// ``` + /// + /// Here, we wind up with the signature from the return type being + /// something like `&'1 u32` where `'1` is a universal region. But + /// the type of the return slot `_0` is something like `&'2 u32` + /// where `'2` is an existential region variable. The type checker + /// requires that `&'2 u32 = &'1 u32` -- but at what point? In the + /// older NLL analysis, we required this only at the entry point + /// to the function. By the nature of the constraints, this wound + /// up propagating to all points reachable from start (because + /// `'1` -- as a universal region -- is live everywhere). In the + /// newer analysis, though, this doesn't work: `_0` is considered + /// dead at the start (it has no usable value) and hence this type + /// equality is basically a no-op. Then, later on, when we do `_0 + /// = &'3 y`, that region `'3` never winds up related to the + /// universal region `'1` and hence no error occurs. Therefore, we + /// use Locations::All instead, which ensures that the `'1` and + /// `'2` are equal everything. We also use this for other + /// user-given type annotations; e.g., if the user wrote `let mut + /// x: &'static u32 = ...`, we would ensure that all values + /// assigned to `x` are of `'static` lifetime. + /// + /// The span points to the place the constraint arose. For example, + /// it points to the type in a user-given type annotation. If + /// there's no sensible span then it's DUMMY_SP. + All(Span), + + /// An outlives constraint that only has to hold at a single location, + /// usually it represents a point where references flow from one spot to + /// another (e.g., `x = y`) + Single(Location), +} + +impl Locations { + pub fn from_location(&self) -> Option<Location> { + match self { + Locations::All(_) => None, + Locations::Single(from_location) => Some(*from_location), + } + } + + /// Gets a span representing the location. + pub fn span(&self, body: &Body<'_>) -> Span { + match self { + Locations::All(span) => *span, + Locations::Single(l) => body.source_info(*l).span, + } + } +} + +impl<'a, 'tcx> TypeChecker<'a, 'tcx> { + fn new( + infcx: &'a InferCtxt<'a, 'tcx>, + body: &'a Body<'tcx>, + param_env: ty::ParamEnv<'tcx>, + region_bound_pairs: &'a RegionBoundPairs<'tcx>, + implicit_region_bound: ty::Region<'tcx>, + borrowck_context: &'a mut BorrowCheckContext<'a, 'tcx>, + ) -> Self { + let mut checker = Self { + infcx, + last_span: DUMMY_SP, + body, + user_type_annotations: &body.user_type_annotations, + param_env, + region_bound_pairs, + implicit_region_bound, + borrowck_context, + reported_errors: Default::default(), + }; + checker.check_user_type_annotations(); + checker + } + + fn body(&self) -> &Body<'tcx> { + self.body + } + + fn unsized_feature_enabled(&self) -> bool { + let features = self.tcx().features(); + features.unsized_locals || features.unsized_fn_params + } + + /// Equate the inferred type and the annotated type for user type annotations + #[instrument(skip(self), level = "debug")] + fn check_user_type_annotations(&mut self) { + debug!(?self.user_type_annotations); + for user_annotation in self.user_type_annotations { + let CanonicalUserTypeAnnotation { span, ref user_ty, inferred_ty } = *user_annotation; + let inferred_ty = self.normalize(inferred_ty, Locations::All(span)); + let annotation = self.instantiate_canonical_with_fresh_inference_vars(span, user_ty); + match annotation { + UserType::Ty(mut ty) => { + ty = self.normalize(ty, Locations::All(span)); + + if let Err(terr) = self.eq_types( + ty, + inferred_ty, + Locations::All(span), + ConstraintCategory::BoringNoLocation, + ) { + span_mirbug!( + self, + user_annotation, + "bad user type ({:?} = {:?}): {:?}", + ty, + inferred_ty, + terr + ); + } + + self.prove_predicate( + ty::Binder::dummy(ty::PredicateKind::WellFormed(inferred_ty.into())) + .to_predicate(self.tcx()), + Locations::All(span), + ConstraintCategory::TypeAnnotation, + ); + } + UserType::TypeOf(def_id, user_substs) => { + if let Err(terr) = self.fully_perform_op( + Locations::All(span), + ConstraintCategory::BoringNoLocation, + self.param_env.and(type_op::ascribe_user_type::AscribeUserType::new( + inferred_ty, + def_id, + user_substs, + )), + ) { + span_mirbug!( + self, + user_annotation, + "bad user type AscribeUserType({:?}, {:?} {:?}, type_of={:?}): {:?}", + inferred_ty, + def_id, + user_substs, + self.tcx().type_of(def_id), + terr, + ); + } + } + } + } + } + + #[instrument(skip(self, data), level = "debug")] + fn push_region_constraints( + &mut self, + locations: Locations, + category: ConstraintCategory<'tcx>, + data: &QueryRegionConstraints<'tcx>, + ) { + debug!("constraints generated: {:#?}", data); + + constraint_conversion::ConstraintConversion::new( + self.infcx, + self.borrowck_context.universal_regions, + self.region_bound_pairs, + self.implicit_region_bound, + self.param_env, + locations, + locations.span(self.body), + category, + &mut self.borrowck_context.constraints, + ) + .convert_all(data); + } + + /// Try to relate `sub <: sup` + fn sub_types( + &mut self, + sub: Ty<'tcx>, + sup: Ty<'tcx>, + locations: Locations, + category: ConstraintCategory<'tcx>, + ) -> Fallible<()> { + // Use this order of parameters because the sup type is usually the + // "expected" type in diagnostics. + self.relate_types(sup, ty::Variance::Contravariant, sub, locations, category) + } + + #[instrument(skip(self, category), level = "debug")] + fn eq_types( + &mut self, + expected: Ty<'tcx>, + found: Ty<'tcx>, + locations: Locations, + category: ConstraintCategory<'tcx>, + ) -> Fallible<()> { + self.relate_types(expected, ty::Variance::Invariant, found, locations, category) + } + + #[instrument(skip(self), level = "debug")] + fn relate_type_and_user_type( + &mut self, + a: Ty<'tcx>, + v: ty::Variance, + user_ty: &UserTypeProjection, + locations: Locations, + category: ConstraintCategory<'tcx>, + ) -> Fallible<()> { + let annotated_type = self.user_type_annotations[user_ty.base].inferred_ty; + let mut curr_projected_ty = PlaceTy::from_ty(annotated_type); + + let tcx = self.infcx.tcx; + + for proj in &user_ty.projs { + let projected_ty = curr_projected_ty.projection_ty_core( + tcx, + self.param_env, + proj, + |this, field, ()| { + let ty = this.field_ty(tcx, field); + self.normalize(ty, locations) + }, + ); + curr_projected_ty = projected_ty; + } + debug!( + "user_ty base: {:?} freshened: {:?} projs: {:?} yields: {:?}", + user_ty.base, annotated_type, user_ty.projs, curr_projected_ty + ); + + let ty = curr_projected_ty.ty; + self.relate_types(ty, v.xform(ty::Variance::Contravariant), a, locations, category)?; + + Ok(()) + } + + fn tcx(&self) -> TyCtxt<'tcx> { + self.infcx.tcx + } + + #[instrument(skip(self, body, location), level = "debug")] + fn check_stmt(&mut self, body: &Body<'tcx>, stmt: &Statement<'tcx>, location: Location) { + let tcx = self.tcx(); + debug!("stmt kind: {:?}", stmt.kind); + match stmt.kind { + StatementKind::Assign(box (ref place, ref rv)) => { + // Assignments to temporaries are not "interesting"; + // they are not caused by the user, but rather artifacts + // of lowering. Assignments to other sorts of places *are* interesting + // though. + let category = match place.as_local() { + Some(RETURN_PLACE) => { + let defining_ty = &self.borrowck_context.universal_regions.defining_ty; + if defining_ty.is_const() { + if tcx.is_static(defining_ty.def_id()) { + ConstraintCategory::UseAsStatic + } else { + ConstraintCategory::UseAsConst + } + } else { + ConstraintCategory::Return(ReturnConstraint::Normal) + } + } + Some(l) + if matches!( + body.local_decls[l].local_info, + Some(box LocalInfo::AggregateTemp) + ) => + { + ConstraintCategory::Usage + } + Some(l) if !body.local_decls[l].is_user_variable() => { + ConstraintCategory::Boring + } + _ => ConstraintCategory::Assignment, + }; + debug!( + "assignment category: {:?} {:?}", + category, + place.as_local().map(|l| &body.local_decls[l]) + ); + + let place_ty = place.ty(body, tcx).ty; + debug!(?place_ty); + let place_ty = self.normalize(place_ty, location); + debug!("place_ty normalized: {:?}", place_ty); + let rv_ty = rv.ty(body, tcx); + debug!(?rv_ty); + let rv_ty = self.normalize(rv_ty, location); + debug!("normalized rv_ty: {:?}", rv_ty); + if let Err(terr) = + self.sub_types(rv_ty, place_ty, location.to_locations(), category) + { + span_mirbug!( + self, + stmt, + "bad assignment ({:?} = {:?}): {:?}", + place_ty, + rv_ty, + terr + ); + } + + if let Some(annotation_index) = self.rvalue_user_ty(rv) { + if let Err(terr) = self.relate_type_and_user_type( + rv_ty, + ty::Variance::Invariant, + &UserTypeProjection { base: annotation_index, projs: vec![] }, + location.to_locations(), + ConstraintCategory::Boring, + ) { + let annotation = &self.user_type_annotations[annotation_index]; + span_mirbug!( + self, + stmt, + "bad user type on rvalue ({:?} = {:?}): {:?}", + annotation, + rv_ty, + terr + ); + } + } + + self.check_rvalue(body, rv, location); + if !self.unsized_feature_enabled() { + let trait_ref = ty::TraitRef { + def_id: tcx.require_lang_item(LangItem::Sized, Some(self.last_span)), + substs: tcx.mk_substs_trait(place_ty, &[]), + }; + self.prove_trait_ref( + trait_ref, + location.to_locations(), + ConstraintCategory::SizedBound, + ); + } + } + StatementKind::AscribeUserType(box (ref place, ref projection), variance) => { + let place_ty = place.ty(body, tcx).ty; + if let Err(terr) = self.relate_type_and_user_type( + place_ty, + variance, + projection, + Locations::All(stmt.source_info.span), + ConstraintCategory::TypeAnnotation, + ) { + let annotation = &self.user_type_annotations[projection.base]; + span_mirbug!( + self, + stmt, + "bad type assert ({:?} <: {:?} with projections {:?}): {:?}", + place_ty, + annotation, + projection.projs, + terr + ); + } + } + StatementKind::CopyNonOverlapping(box rustc_middle::mir::CopyNonOverlapping { + .. + }) => span_bug!( + stmt.source_info.span, + "Unexpected StatementKind::CopyNonOverlapping, should only appear after lowering_intrinsics", + ), + StatementKind::FakeRead(..) + | StatementKind::StorageLive(..) + | StatementKind::StorageDead(..) + | StatementKind::Retag { .. } + | StatementKind::Coverage(..) + | StatementKind::Nop => {} + StatementKind::Deinit(..) | StatementKind::SetDiscriminant { .. } => { + bug!("Statement not allowed in this MIR phase") + } + } + } + + #[instrument(skip(self, body, term_location), level = "debug")] + fn check_terminator( + &mut self, + body: &Body<'tcx>, + term: &Terminator<'tcx>, + term_location: Location, + ) { + let tcx = self.tcx(); + debug!("terminator kind: {:?}", term.kind); + match term.kind { + TerminatorKind::Goto { .. } + | TerminatorKind::Resume + | TerminatorKind::Abort + | TerminatorKind::Return + | TerminatorKind::GeneratorDrop + | TerminatorKind::Unreachable + | TerminatorKind::Drop { .. } + | TerminatorKind::FalseEdge { .. } + | TerminatorKind::FalseUnwind { .. } + | TerminatorKind::InlineAsm { .. } => { + // no checks needed for these + } + + TerminatorKind::DropAndReplace { ref place, ref value, target: _, unwind: _ } => { + let place_ty = place.ty(body, tcx).ty; + let rv_ty = value.ty(body, tcx); + + let locations = term_location.to_locations(); + if let Err(terr) = + self.sub_types(rv_ty, place_ty, locations, ConstraintCategory::Assignment) + { + span_mirbug!( + self, + term, + "bad DropAndReplace ({:?} = {:?}): {:?}", + place_ty, + rv_ty, + terr + ); + } + } + TerminatorKind::SwitchInt { ref discr, switch_ty, .. } => { + self.check_operand(discr, term_location); + + let discr_ty = discr.ty(body, tcx); + if let Err(terr) = self.sub_types( + discr_ty, + switch_ty, + term_location.to_locations(), + ConstraintCategory::Assignment, + ) { + span_mirbug!( + self, + term, + "bad SwitchInt ({:?} on {:?}): {:?}", + switch_ty, + discr_ty, + terr + ); + } + if !switch_ty.is_integral() && !switch_ty.is_char() && !switch_ty.is_bool() { + span_mirbug!(self, term, "bad SwitchInt discr ty {:?}", switch_ty); + } + // FIXME: check the values + } + TerminatorKind::Call { + ref func, + ref args, + ref destination, + from_hir_call, + target, + .. + } => { + self.check_operand(func, term_location); + for arg in args { + self.check_operand(arg, term_location); + } + + let func_ty = func.ty(body, tcx); + debug!("func_ty.kind: {:?}", func_ty.kind()); + + let sig = match func_ty.kind() { + ty::FnDef(..) | ty::FnPtr(_) => func_ty.fn_sig(tcx), + _ => { + span_mirbug!(self, term, "call to non-function {:?}", func_ty); + return; + } + }; + let (sig, map) = tcx.replace_late_bound_regions(sig, |br| { + self.infcx.next_region_var(LateBoundRegion( + term.source_info.span, + br.kind, + LateBoundRegionConversionTime::FnCall, + )) + }); + debug!(?sig); + let sig = self.normalize(sig, term_location); + self.check_call_dest(body, term, &sig, *destination, target, term_location); + + self.prove_predicates( + sig.inputs_and_output + .iter() + .map(|ty| ty::Binder::dummy(ty::PredicateKind::WellFormed(ty.into()))), + term_location.to_locations(), + ConstraintCategory::Boring, + ); + + // The ordinary liveness rules will ensure that all + // regions in the type of the callee are live here. We + // then further constrain the late-bound regions that + // were instantiated at the call site to be live as + // well. The resulting is that all the input (and + // output) types in the signature must be live, since + // all the inputs that fed into it were live. + for &late_bound_region in map.values() { + let region_vid = + self.borrowck_context.universal_regions.to_region_vid(late_bound_region); + self.borrowck_context + .constraints + .liveness_constraints + .add_element(region_vid, term_location); + } + + self.check_call_inputs(body, term, &sig, args, term_location, from_hir_call); + } + TerminatorKind::Assert { ref cond, ref msg, .. } => { + self.check_operand(cond, term_location); + + let cond_ty = cond.ty(body, tcx); + if cond_ty != tcx.types.bool { + span_mirbug!(self, term, "bad Assert ({:?}, not bool", cond_ty); + } + + if let AssertKind::BoundsCheck { ref len, ref index } = *msg { + if len.ty(body, tcx) != tcx.types.usize { + span_mirbug!(self, len, "bounds-check length non-usize {:?}", len) + } + if index.ty(body, tcx) != tcx.types.usize { + span_mirbug!(self, index, "bounds-check index non-usize {:?}", index) + } + } + } + TerminatorKind::Yield { ref value, .. } => { + self.check_operand(value, term_location); + + let value_ty = value.ty(body, tcx); + match body.yield_ty() { + None => span_mirbug!(self, term, "yield in non-generator"), + Some(ty) => { + if let Err(terr) = self.sub_types( + value_ty, + ty, + term_location.to_locations(), + ConstraintCategory::Yield, + ) { + span_mirbug!( + self, + term, + "type of yield value is {:?}, but the yield type is {:?}: {:?}", + value_ty, + ty, + terr + ); + } + } + } + } + } + } + + fn check_call_dest( + &mut self, + body: &Body<'tcx>, + term: &Terminator<'tcx>, + sig: &ty::FnSig<'tcx>, + destination: Place<'tcx>, + target: Option<BasicBlock>, + term_location: Location, + ) { + let tcx = self.tcx(); + match target { + Some(_) => { + let dest_ty = destination.ty(body, tcx).ty; + let dest_ty = self.normalize(dest_ty, term_location); + let category = match destination.as_local() { + Some(RETURN_PLACE) => { + if let BorrowCheckContext { + universal_regions: + UniversalRegions { + defining_ty: + DefiningTy::Const(def_id, _) + | DefiningTy::InlineConst(def_id, _), + .. + }, + .. + } = self.borrowck_context + { + if tcx.is_static(*def_id) { + ConstraintCategory::UseAsStatic + } else { + ConstraintCategory::UseAsConst + } + } else { + ConstraintCategory::Return(ReturnConstraint::Normal) + } + } + Some(l) if !body.local_decls[l].is_user_variable() => { + ConstraintCategory::Boring + } + _ => ConstraintCategory::Assignment, + }; + + let locations = term_location.to_locations(); + + if let Err(terr) = self.sub_types(sig.output(), dest_ty, locations, category) { + span_mirbug!( + self, + term, + "call dest mismatch ({:?} <- {:?}): {:?}", + dest_ty, + sig.output(), + terr + ); + } + + // When `unsized_fn_params` and `unsized_locals` are both not enabled, + // this check is done at `check_local`. + if self.unsized_feature_enabled() { + let span = term.source_info.span; + self.ensure_place_sized(dest_ty, span); + } + } + None => { + if !self + .tcx() + .conservative_is_privately_uninhabited(self.param_env.and(sig.output())) + { + span_mirbug!(self, term, "call to converging function {:?} w/o dest", sig); + } + } + } + } + + fn check_call_inputs( + &mut self, + body: &Body<'tcx>, + term: &Terminator<'tcx>, + sig: &ty::FnSig<'tcx>, + args: &[Operand<'tcx>], + term_location: Location, + from_hir_call: bool, + ) { + debug!("check_call_inputs({:?}, {:?})", sig, args); + if args.len() < sig.inputs().len() || (args.len() > sig.inputs().len() && !sig.c_variadic) { + span_mirbug!(self, term, "call to {:?} with wrong # of args", sig); + } + + let func_ty = if let TerminatorKind::Call { func, .. } = &term.kind { + Some(func.ty(body, self.infcx.tcx)) + } else { + None + }; + debug!(?func_ty); + + for (n, (fn_arg, op_arg)) in iter::zip(sig.inputs(), args).enumerate() { + let op_arg_ty = op_arg.ty(body, self.tcx()); + + let op_arg_ty = self.normalize(op_arg_ty, term_location); + let category = if from_hir_call { + ConstraintCategory::CallArgument(func_ty) + } else { + ConstraintCategory::Boring + }; + if let Err(terr) = + self.sub_types(op_arg_ty, *fn_arg, term_location.to_locations(), category) + { + span_mirbug!( + self, + term, + "bad arg #{:?} ({:?} <- {:?}): {:?}", + n, + fn_arg, + op_arg_ty, + terr + ); + } + } + } + + fn check_iscleanup(&mut self, body: &Body<'tcx>, block_data: &BasicBlockData<'tcx>) { + let is_cleanup = block_data.is_cleanup; + self.last_span = block_data.terminator().source_info.span; + match block_data.terminator().kind { + TerminatorKind::Goto { target } => { + self.assert_iscleanup(body, block_data, target, is_cleanup) + } + TerminatorKind::SwitchInt { ref targets, .. } => { + for target in targets.all_targets() { + self.assert_iscleanup(body, block_data, *target, is_cleanup); + } + } + TerminatorKind::Resume => { + if !is_cleanup { + span_mirbug!(self, block_data, "resume on non-cleanup block!") + } + } + TerminatorKind::Abort => { + if !is_cleanup { + span_mirbug!(self, block_data, "abort on non-cleanup block!") + } + } + TerminatorKind::Return => { + if is_cleanup { + span_mirbug!(self, block_data, "return on cleanup block") + } + } + TerminatorKind::GeneratorDrop { .. } => { + if is_cleanup { + span_mirbug!(self, block_data, "generator_drop in cleanup block") + } + } + TerminatorKind::Yield { resume, drop, .. } => { + if is_cleanup { + span_mirbug!(self, block_data, "yield in cleanup block") + } + self.assert_iscleanup(body, block_data, resume, is_cleanup); + if let Some(drop) = drop { + self.assert_iscleanup(body, block_data, drop, is_cleanup); + } + } + TerminatorKind::Unreachable => {} + TerminatorKind::Drop { target, unwind, .. } + | TerminatorKind::DropAndReplace { target, unwind, .. } + | TerminatorKind::Assert { target, cleanup: unwind, .. } => { + self.assert_iscleanup(body, block_data, target, is_cleanup); + if let Some(unwind) = unwind { + if is_cleanup { + span_mirbug!(self, block_data, "unwind on cleanup block") + } + self.assert_iscleanup(body, block_data, unwind, true); + } + } + TerminatorKind::Call { ref target, cleanup, .. } => { + if let &Some(target) = target { + self.assert_iscleanup(body, block_data, target, is_cleanup); + } + if let Some(cleanup) = cleanup { + if is_cleanup { + span_mirbug!(self, block_data, "cleanup on cleanup block") + } + self.assert_iscleanup(body, block_data, cleanup, true); + } + } + TerminatorKind::FalseEdge { real_target, imaginary_target } => { + self.assert_iscleanup(body, block_data, real_target, is_cleanup); + self.assert_iscleanup(body, block_data, imaginary_target, is_cleanup); + } + TerminatorKind::FalseUnwind { real_target, unwind } => { + self.assert_iscleanup(body, block_data, real_target, is_cleanup); + if let Some(unwind) = unwind { + if is_cleanup { + span_mirbug!(self, block_data, "cleanup in cleanup block via false unwind"); + } + self.assert_iscleanup(body, block_data, unwind, true); + } + } + TerminatorKind::InlineAsm { destination, cleanup, .. } => { + if let Some(target) = destination { + self.assert_iscleanup(body, block_data, target, is_cleanup); + } + if let Some(cleanup) = cleanup { + if is_cleanup { + span_mirbug!(self, block_data, "cleanup on cleanup block") + } + self.assert_iscleanup(body, block_data, cleanup, true); + } + } + } + } + + fn assert_iscleanup( + &mut self, + body: &Body<'tcx>, + ctxt: &dyn fmt::Debug, + bb: BasicBlock, + iscleanuppad: bool, + ) { + if body[bb].is_cleanup != iscleanuppad { + span_mirbug!(self, ctxt, "cleanuppad mismatch: {:?} should be {:?}", bb, iscleanuppad); + } + } + + fn check_local(&mut self, body: &Body<'tcx>, local: Local, local_decl: &LocalDecl<'tcx>) { + match body.local_kind(local) { + LocalKind::ReturnPointer | LocalKind::Arg => { + // return values of normal functions are required to be + // sized by typeck, but return values of ADT constructors are + // not because we don't include a `Self: Sized` bounds on them. + // + // Unbound parts of arguments were never required to be Sized + // - maybe we should make that a warning. + return; + } + LocalKind::Var | LocalKind::Temp => {} + } + + // When `unsized_fn_params` or `unsized_locals` is enabled, only function calls + // and nullary ops are checked in `check_call_dest`. + if !self.unsized_feature_enabled() { + let span = local_decl.source_info.span; + let ty = local_decl.ty; + self.ensure_place_sized(ty, span); + } + } + + fn ensure_place_sized(&mut self, ty: Ty<'tcx>, span: Span) { + let tcx = self.tcx(); + + // Erase the regions from `ty` to get a global type. The + // `Sized` bound in no way depends on precise regions, so this + // shouldn't affect `is_sized`. + let erased_ty = tcx.erase_regions(ty); + if !erased_ty.is_sized(tcx.at(span), self.param_env) { + // in current MIR construction, all non-control-flow rvalue + // expressions evaluate through `as_temp` or `into` a return + // slot or local, so to find all unsized rvalues it is enough + // to check all temps, return slots and locals. + if self.reported_errors.replace((ty, span)).is_none() { + // While this is located in `nll::typeck` this error is not + // an NLL error, it's a required check to prevent creation + // of unsized rvalues in a call expression. + self.tcx().sess.emit_err(MoveUnsized { ty, span }); + } + } + } + + fn aggregate_field_ty( + &mut self, + ak: &AggregateKind<'tcx>, + field_index: usize, + location: Location, + ) -> Result<Ty<'tcx>, FieldAccessError> { + let tcx = self.tcx(); + + match *ak { + AggregateKind::Adt(adt_did, variant_index, substs, _, active_field_index) => { + let def = tcx.adt_def(adt_did); + let variant = &def.variant(variant_index); + let adj_field_index = active_field_index.unwrap_or(field_index); + if let Some(field) = variant.fields.get(adj_field_index) { + Ok(self.normalize(field.ty(tcx, substs), location)) + } else { + Err(FieldAccessError::OutOfRange { field_count: variant.fields.len() }) + } + } + AggregateKind::Closure(_, substs) => { + match substs.as_closure().upvar_tys().nth(field_index) { + Some(ty) => Ok(ty), + None => Err(FieldAccessError::OutOfRange { + field_count: substs.as_closure().upvar_tys().count(), + }), + } + } + AggregateKind::Generator(_, substs, _) => { + // It doesn't make sense to look at a field beyond the prefix; + // these require a variant index, and are not initialized in + // aggregate rvalues. + match substs.as_generator().prefix_tys().nth(field_index) { + Some(ty) => Ok(ty), + None => Err(FieldAccessError::OutOfRange { + field_count: substs.as_generator().prefix_tys().count(), + }), + } + } + AggregateKind::Array(ty) => Ok(ty), + AggregateKind::Tuple => { + unreachable!("This should have been covered in check_rvalues"); + } + } + } + + fn check_operand(&mut self, op: &Operand<'tcx>, location: Location) { + if let Operand::Constant(constant) = op { + let maybe_uneval = match constant.literal { + ConstantKind::Ty(ct) => match ct.kind() { + ty::ConstKind::Unevaluated(uv) => Some(uv), + _ => None, + }, + _ => None, + }; + if let Some(uv) = maybe_uneval { + if uv.promoted.is_none() { + let tcx = self.tcx(); + let def_id = uv.def.def_id_for_type_of(); + if tcx.def_kind(def_id) == DefKind::InlineConst { + let def_id = def_id.expect_local(); + let predicates = + self.prove_closure_bounds(tcx, def_id, uv.substs, location); + self.normalize_and_prove_instantiated_predicates( + def_id.to_def_id(), + predicates, + location.to_locations(), + ); + } + } + } + } + } + + #[instrument(skip(self, body), level = "debug")] + fn check_rvalue(&mut self, body: &Body<'tcx>, rvalue: &Rvalue<'tcx>, location: Location) { + let tcx = self.tcx(); + + match rvalue { + Rvalue::Aggregate(ak, ops) => { + for op in ops { + self.check_operand(op, location); + } + self.check_aggregate_rvalue(&body, rvalue, ak, ops, location) + } + + Rvalue::Repeat(operand, len) => { + self.check_operand(operand, location); + + // If the length cannot be evaluated we must assume that the length can be larger + // than 1. + // If the length is larger than 1, the repeat expression will need to copy the + // element, so we require the `Copy` trait. + if len.try_eval_usize(tcx, self.param_env).map_or(true, |len| len > 1) { + match operand { + Operand::Copy(..) | Operand::Constant(..) => { + // These are always okay: direct use of a const, or a value that can evidently be copied. + } + Operand::Move(place) => { + // Make sure that repeated elements implement `Copy`. + let span = body.source_info(location).span; + let ty = place.ty(body, tcx).ty; + let trait_ref = ty::TraitRef::new( + tcx.require_lang_item(LangItem::Copy, Some(span)), + tcx.mk_substs_trait(ty, &[]), + ); + + self.prove_trait_ref( + trait_ref, + Locations::Single(location), + ConstraintCategory::CopyBound, + ); + } + } + } + } + + &Rvalue::NullaryOp(_, ty) => { + let trait_ref = ty::TraitRef { + def_id: tcx.require_lang_item(LangItem::Sized, Some(self.last_span)), + substs: tcx.mk_substs_trait(ty, &[]), + }; + + self.prove_trait_ref( + trait_ref, + location.to_locations(), + ConstraintCategory::SizedBound, + ); + } + + Rvalue::ShallowInitBox(operand, ty) => { + self.check_operand(operand, location); + + let trait_ref = ty::TraitRef { + def_id: tcx.require_lang_item(LangItem::Sized, Some(self.last_span)), + substs: tcx.mk_substs_trait(*ty, &[]), + }; + + self.prove_trait_ref( + trait_ref, + location.to_locations(), + ConstraintCategory::SizedBound, + ); + } + + Rvalue::Cast(cast_kind, op, ty) => { + self.check_operand(op, location); + + match cast_kind { + CastKind::Pointer(PointerCast::ReifyFnPointer) => { + let fn_sig = op.ty(body, tcx).fn_sig(tcx); + + // The type that we see in the fcx is like + // `foo::<'a, 'b>`, where `foo` is the path to a + // function definition. When we extract the + // signature, it comes from the `fn_sig` query, + // and hence may contain unnormalized results. + let fn_sig = self.normalize(fn_sig, location); + + let ty_fn_ptr_from = tcx.mk_fn_ptr(fn_sig); + + if let Err(terr) = self.eq_types( + *ty, + ty_fn_ptr_from, + location.to_locations(), + ConstraintCategory::Cast, + ) { + span_mirbug!( + self, + rvalue, + "equating {:?} with {:?} yields {:?}", + ty_fn_ptr_from, + ty, + terr + ); + } + } + + CastKind::Pointer(PointerCast::ClosureFnPointer(unsafety)) => { + let sig = match op.ty(body, tcx).kind() { + ty::Closure(_, substs) => substs.as_closure().sig(), + _ => bug!(), + }; + let ty_fn_ptr_from = tcx.mk_fn_ptr(tcx.signature_unclosure(sig, *unsafety)); + + if let Err(terr) = self.eq_types( + *ty, + ty_fn_ptr_from, + location.to_locations(), + ConstraintCategory::Cast, + ) { + span_mirbug!( + self, + rvalue, + "equating {:?} with {:?} yields {:?}", + ty_fn_ptr_from, + ty, + terr + ); + } + } + + CastKind::Pointer(PointerCast::UnsafeFnPointer) => { + let fn_sig = op.ty(body, tcx).fn_sig(tcx); + + // The type that we see in the fcx is like + // `foo::<'a, 'b>`, where `foo` is the path to a + // function definition. When we extract the + // signature, it comes from the `fn_sig` query, + // and hence may contain unnormalized results. + let fn_sig = self.normalize(fn_sig, location); + + let ty_fn_ptr_from = tcx.safe_to_unsafe_fn_ty(fn_sig); + + if let Err(terr) = self.eq_types( + *ty, + ty_fn_ptr_from, + location.to_locations(), + ConstraintCategory::Cast, + ) { + span_mirbug!( + self, + rvalue, + "equating {:?} with {:?} yields {:?}", + ty_fn_ptr_from, + ty, + terr + ); + } + } + + CastKind::Pointer(PointerCast::Unsize) => { + let &ty = ty; + let trait_ref = ty::TraitRef { + def_id: tcx + .require_lang_item(LangItem::CoerceUnsized, Some(self.last_span)), + substs: tcx.mk_substs_trait(op.ty(body, tcx), &[ty.into()]), + }; + + self.prove_trait_ref( + trait_ref, + location.to_locations(), + ConstraintCategory::Cast, + ); + } + + CastKind::Pointer(PointerCast::MutToConstPointer) => { + let ty::RawPtr(ty::TypeAndMut { + ty: ty_from, + mutbl: hir::Mutability::Mut, + }) = op.ty(body, tcx).kind() else { + span_mirbug!( + self, + rvalue, + "unexpected base type for cast {:?}", + ty, + ); + return; + }; + let ty::RawPtr(ty::TypeAndMut { + ty: ty_to, + mutbl: hir::Mutability::Not, + }) = ty.kind() else { + span_mirbug!( + self, + rvalue, + "unexpected target type for cast {:?}", + ty, + ); + return; + }; + if let Err(terr) = self.sub_types( + *ty_from, + *ty_to, + location.to_locations(), + ConstraintCategory::Cast, + ) { + span_mirbug!( + self, + rvalue, + "relating {:?} with {:?} yields {:?}", + ty_from, + ty_to, + terr + ); + } + } + + CastKind::Pointer(PointerCast::ArrayToPointer) => { + let ty_from = op.ty(body, tcx); + + let opt_ty_elem_mut = match ty_from.kind() { + ty::RawPtr(ty::TypeAndMut { mutbl: array_mut, ty: array_ty }) => { + match array_ty.kind() { + ty::Array(ty_elem, _) => Some((ty_elem, *array_mut)), + _ => None, + } + } + _ => None, + }; + + let Some((ty_elem, ty_mut)) = opt_ty_elem_mut else { + span_mirbug!( + self, + rvalue, + "ArrayToPointer cast from unexpected type {:?}", + ty_from, + ); + return; + }; + + let (ty_to, ty_to_mut) = match ty.kind() { + ty::RawPtr(ty::TypeAndMut { mutbl: ty_to_mut, ty: ty_to }) => { + (ty_to, *ty_to_mut) + } + _ => { + span_mirbug!( + self, + rvalue, + "ArrayToPointer cast to unexpected type {:?}", + ty, + ); + return; + } + }; + + if ty_to_mut == Mutability::Mut && ty_mut == Mutability::Not { + span_mirbug!( + self, + rvalue, + "ArrayToPointer cast from const {:?} to mut {:?}", + ty, + ty_to + ); + return; + } + + if let Err(terr) = self.sub_types( + *ty_elem, + *ty_to, + location.to_locations(), + ConstraintCategory::Cast, + ) { + span_mirbug!( + self, + rvalue, + "relating {:?} with {:?} yields {:?}", + ty_elem, + ty_to, + terr + ) + } + } + + CastKind::PointerExposeAddress => { + let ty_from = op.ty(body, tcx); + let cast_ty_from = CastTy::from_ty(ty_from); + let cast_ty_to = CastTy::from_ty(*ty); + match (cast_ty_from, cast_ty_to) { + (Some(CastTy::Ptr(_) | CastTy::FnPtr), Some(CastTy::Int(_))) => (), + _ => { + span_mirbug!( + self, + rvalue, + "Invalid PointerExposeAddress cast {:?} -> {:?}", + ty_from, + ty + ) + } + } + } + + CastKind::PointerFromExposedAddress => { + let ty_from = op.ty(body, tcx); + let cast_ty_from = CastTy::from_ty(ty_from); + let cast_ty_to = CastTy::from_ty(*ty); + match (cast_ty_from, cast_ty_to) { + (Some(CastTy::Int(_)), Some(CastTy::Ptr(_))) => (), + _ => { + span_mirbug!( + self, + rvalue, + "Invalid PointerFromExposedAddress cast {:?} -> {:?}", + ty_from, + ty + ) + } + } + } + + CastKind::Misc => { + let ty_from = op.ty(body, tcx); + let cast_ty_from = CastTy::from_ty(ty_from); + let cast_ty_to = CastTy::from_ty(*ty); + // Misc casts are either between floats and ints, or one ptr type to another. + match (cast_ty_from, cast_ty_to) { + ( + Some(CastTy::Int(_) | CastTy::Float), + Some(CastTy::Int(_) | CastTy::Float), + ) + | (Some(CastTy::Ptr(_) | CastTy::FnPtr), Some(CastTy::Ptr(_))) => (), + _ => { + span_mirbug!( + self, + rvalue, + "Invalid Misc cast {:?} -> {:?}", + ty_from, + ty, + ) + } + } + } + } + } + + Rvalue::Ref(region, _borrow_kind, borrowed_place) => { + self.add_reborrow_constraint(&body, location, *region, borrowed_place); + } + + Rvalue::BinaryOp( + BinOp::Eq | BinOp::Ne | BinOp::Lt | BinOp::Le | BinOp::Gt | BinOp::Ge, + box (left, right), + ) => { + self.check_operand(left, location); + self.check_operand(right, location); + + let ty_left = left.ty(body, tcx); + match ty_left.kind() { + // Types with regions are comparable if they have a common super-type. + ty::RawPtr(_) | ty::FnPtr(_) => { + let ty_right = right.ty(body, tcx); + let common_ty = self.infcx.next_ty_var(TypeVariableOrigin { + kind: TypeVariableOriginKind::MiscVariable, + span: body.source_info(location).span, + }); + self.sub_types( + ty_left, + common_ty, + location.to_locations(), + ConstraintCategory::Boring, + ) + .unwrap_or_else(|err| { + bug!("Could not equate type variable with {:?}: {:?}", ty_left, err) + }); + if let Err(terr) = self.sub_types( + ty_right, + common_ty, + location.to_locations(), + ConstraintCategory::Boring, + ) { + span_mirbug!( + self, + rvalue, + "unexpected comparison types {:?} and {:?} yields {:?}", + ty_left, + ty_right, + terr + ) + } + } + // For types with no regions we can just check that the + // both operands have the same type. + ty::Int(_) | ty::Uint(_) | ty::Bool | ty::Char | ty::Float(_) + if ty_left == right.ty(body, tcx) => {} + // Other types are compared by trait methods, not by + // `Rvalue::BinaryOp`. + _ => span_mirbug!( + self, + rvalue, + "unexpected comparison types {:?} and {:?}", + ty_left, + right.ty(body, tcx) + ), + } + } + + Rvalue::Use(operand) | Rvalue::UnaryOp(_, operand) => { + self.check_operand(operand, location); + } + Rvalue::CopyForDeref(place) => { + let op = &Operand::Copy(*place); + self.check_operand(op, location); + } + + Rvalue::BinaryOp(_, box (left, right)) + | Rvalue::CheckedBinaryOp(_, box (left, right)) => { + self.check_operand(left, location); + self.check_operand(right, location); + } + + Rvalue::AddressOf(..) + | Rvalue::ThreadLocalRef(..) + | Rvalue::Len(..) + | Rvalue::Discriminant(..) => {} + } + } + + /// If this rvalue supports a user-given type annotation, then + /// extract and return it. This represents the final type of the + /// rvalue and will be unified with the inferred type. + fn rvalue_user_ty(&self, rvalue: &Rvalue<'tcx>) -> Option<UserTypeAnnotationIndex> { + match rvalue { + Rvalue::Use(_) + | Rvalue::ThreadLocalRef(_) + | Rvalue::Repeat(..) + | Rvalue::Ref(..) + | Rvalue::AddressOf(..) + | Rvalue::Len(..) + | Rvalue::Cast(..) + | Rvalue::ShallowInitBox(..) + | Rvalue::BinaryOp(..) + | Rvalue::CheckedBinaryOp(..) + | Rvalue::NullaryOp(..) + | Rvalue::CopyForDeref(..) + | Rvalue::UnaryOp(..) + | Rvalue::Discriminant(..) => None, + + Rvalue::Aggregate(aggregate, _) => match **aggregate { + AggregateKind::Adt(_, _, _, user_ty, _) => user_ty, + AggregateKind::Array(_) => None, + AggregateKind::Tuple => None, + AggregateKind::Closure(_, _) => None, + AggregateKind::Generator(_, _, _) => None, + }, + } + } + + fn check_aggregate_rvalue( + &mut self, + body: &Body<'tcx>, + rvalue: &Rvalue<'tcx>, + aggregate_kind: &AggregateKind<'tcx>, + operands: &[Operand<'tcx>], + location: Location, + ) { + let tcx = self.tcx(); + + self.prove_aggregate_predicates(aggregate_kind, location); + + if *aggregate_kind == AggregateKind::Tuple { + // tuple rvalue field type is always the type of the op. Nothing to check here. + return; + } + + for (i, operand) in operands.iter().enumerate() { + let field_ty = match self.aggregate_field_ty(aggregate_kind, i, location) { + Ok(field_ty) => field_ty, + Err(FieldAccessError::OutOfRange { field_count }) => { + span_mirbug!( + self, + rvalue, + "accessed field #{} but variant only has {}", + i, + field_count + ); + continue; + } + }; + let operand_ty = operand.ty(body, tcx); + let operand_ty = self.normalize(operand_ty, location); + + if let Err(terr) = self.sub_types( + operand_ty, + field_ty, + location.to_locations(), + ConstraintCategory::Boring, + ) { + span_mirbug!( + self, + rvalue, + "{:?} is not a subtype of {:?}: {:?}", + operand_ty, + field_ty, + terr + ); + } + } + } + + /// Adds the constraints that arise from a borrow expression `&'a P` at the location `L`. + /// + /// # Parameters + /// + /// - `location`: the location `L` where the borrow expression occurs + /// - `borrow_region`: the region `'a` associated with the borrow + /// - `borrowed_place`: the place `P` being borrowed + fn add_reborrow_constraint( + &mut self, + body: &Body<'tcx>, + location: Location, + borrow_region: ty::Region<'tcx>, + borrowed_place: &Place<'tcx>, + ) { + // These constraints are only meaningful during borrowck: + let BorrowCheckContext { borrow_set, location_table, all_facts, constraints, .. } = + self.borrowck_context; + + // In Polonius mode, we also push a `loan_issued_at` fact + // linking the loan to the region (in some cases, though, + // there is no loan associated with this borrow expression -- + // that occurs when we are borrowing an unsafe place, for + // example). + if let Some(all_facts) = all_facts { + let _prof_timer = self.infcx.tcx.prof.generic_activity("polonius_fact_generation"); + if let Some(borrow_index) = borrow_set.get_index_of(&location) { + let region_vid = borrow_region.to_region_vid(); + all_facts.loan_issued_at.push(( + region_vid, + borrow_index, + location_table.mid_index(location), + )); + } + } + + // If we are reborrowing the referent of another reference, we + // need to add outlives relationships. In a case like `&mut + // *p`, where the `p` has type `&'b mut Foo`, for example, we + // need to ensure that `'b: 'a`. + + debug!( + "add_reborrow_constraint({:?}, {:?}, {:?})", + location, borrow_region, borrowed_place + ); + + let mut cursor = borrowed_place.projection.as_ref(); + let tcx = self.infcx.tcx; + let field = path_utils::is_upvar_field_projection( + tcx, + &self.borrowck_context.upvars, + borrowed_place.as_ref(), + body, + ); + let category = if let Some(field) = field { + ConstraintCategory::ClosureUpvar(field) + } else { + ConstraintCategory::Boring + }; + + while let [proj_base @ .., elem] = cursor { + cursor = proj_base; + + debug!("add_reborrow_constraint - iteration {:?}", elem); + + match elem { + ProjectionElem::Deref => { + let base_ty = Place::ty_from(borrowed_place.local, proj_base, body, tcx).ty; + + debug!("add_reborrow_constraint - base_ty = {:?}", base_ty); + match base_ty.kind() { + ty::Ref(ref_region, _, mutbl) => { + constraints.outlives_constraints.push(OutlivesConstraint { + sup: ref_region.to_region_vid(), + sub: borrow_region.to_region_vid(), + locations: location.to_locations(), + span: location.to_locations().span(body), + category, + variance_info: ty::VarianceDiagInfo::default(), + }); + + match mutbl { + hir::Mutability::Not => { + // Immutable reference. We don't need the base + // to be valid for the entire lifetime of + // the borrow. + break; + } + hir::Mutability::Mut => { + // Mutable reference. We *do* need the base + // to be valid, because after the base becomes + // invalid, someone else can use our mutable deref. + + // This is in order to make the following function + // illegal: + // ``` + // fn unsafe_deref<'a, 'b>(x: &'a &'b mut T) -> &'b mut T { + // &mut *x + // } + // ``` + // + // As otherwise you could clone `&mut T` using the + // following function: + // ``` + // fn bad(x: &mut T) -> (&mut T, &mut T) { + // let my_clone = unsafe_deref(&'a x); + // ENDREGION 'a; + // (my_clone, x) + // } + // ``` + } + } + } + ty::RawPtr(..) => { + // deref of raw pointer, guaranteed to be valid + break; + } + ty::Adt(def, _) if def.is_box() => { + // deref of `Box`, need the base to be valid - propagate + } + _ => bug!("unexpected deref ty {:?} in {:?}", base_ty, borrowed_place), + } + } + ProjectionElem::Field(..) + | ProjectionElem::Downcast(..) + | ProjectionElem::Index(..) + | ProjectionElem::ConstantIndex { .. } + | ProjectionElem::Subslice { .. } => { + // other field access + } + } + } + } + + fn prove_aggregate_predicates( + &mut self, + aggregate_kind: &AggregateKind<'tcx>, + location: Location, + ) { + let tcx = self.tcx(); + + debug!( + "prove_aggregate_predicates(aggregate_kind={:?}, location={:?})", + aggregate_kind, location + ); + + let (def_id, instantiated_predicates) = match *aggregate_kind { + AggregateKind::Adt(adt_did, _, substs, _, _) => { + (adt_did, tcx.predicates_of(adt_did).instantiate(tcx, substs)) + } + + // For closures, we have some **extra requirements** we + // + // have to check. In particular, in their upvars and + // signatures, closures often reference various regions + // from the surrounding function -- we call those the + // closure's free regions. When we borrow-check (and hence + // region-check) closures, we may find that the closure + // requires certain relationships between those free + // regions. However, because those free regions refer to + // portions of the CFG of their caller, the closure is not + // in a position to verify those relationships. In that + // case, the requirements get "propagated" to us, and so + // we have to solve them here where we instantiate the + // closure. + // + // Despite the opacity of the previous paragraph, this is + // actually relatively easy to understand in terms of the + // desugaring. A closure gets desugared to a struct, and + // these extra requirements are basically like where + // clauses on the struct. + AggregateKind::Closure(def_id, substs) + | AggregateKind::Generator(def_id, substs, _) => { + (def_id.to_def_id(), self.prove_closure_bounds(tcx, def_id, substs, location)) + } + + AggregateKind::Array(_) | AggregateKind::Tuple => { + (CRATE_DEF_ID.to_def_id(), ty::InstantiatedPredicates::empty()) + } + }; + + self.normalize_and_prove_instantiated_predicates( + def_id, + instantiated_predicates, + location.to_locations(), + ); + } + + fn prove_closure_bounds( + &mut self, + tcx: TyCtxt<'tcx>, + def_id: LocalDefId, + substs: SubstsRef<'tcx>, + location: Location, + ) -> ty::InstantiatedPredicates<'tcx> { + if let Some(ref closure_region_requirements) = tcx.mir_borrowck(def_id).closure_requirements + { + let closure_constraints = QueryRegionConstraints { + outlives: closure_region_requirements.apply_requirements( + tcx, + def_id.to_def_id(), + substs, + ), + + // Presently, closures never propagate member + // constraints to their parents -- they are enforced + // locally. This is largely a non-issue as member + // constraints only come from `-> impl Trait` and + // friends which don't appear (thus far...) in + // closures. + member_constraints: vec![], + }; + + let bounds_mapping = closure_constraints + .outlives + .iter() + .enumerate() + .filter_map(|(idx, constraint)| { + let ty::OutlivesPredicate(k1, r2) = + constraint.no_bound_vars().unwrap_or_else(|| { + bug!("query_constraint {:?} contained bound vars", constraint,); + }); + + match k1.unpack() { + GenericArgKind::Lifetime(r1) => { + // constraint is r1: r2 + let r1_vid = self.borrowck_context.universal_regions.to_region_vid(r1); + let r2_vid = self.borrowck_context.universal_regions.to_region_vid(r2); + let outlives_requirements = + &closure_region_requirements.outlives_requirements[idx]; + Some(( + (r1_vid, r2_vid), + (outlives_requirements.category, outlives_requirements.blame_span), + )) + } + GenericArgKind::Type(_) | GenericArgKind::Const(_) => None, + } + }) + .collect(); + + let existing = self + .borrowck_context + .constraints + .closure_bounds_mapping + .insert(location, bounds_mapping); + assert!(existing.is_none(), "Multiple closures at the same location."); + + self.push_region_constraints( + location.to_locations(), + ConstraintCategory::ClosureBounds, + &closure_constraints, + ); + } + + // Now equate closure substs to regions inherited from `typeck_root_def_id`. Fixes #98589. + let typeck_root_def_id = tcx.typeck_root_def_id(self.body.source.def_id()); + let typeck_root_substs = ty::InternalSubsts::identity_for_item(tcx, typeck_root_def_id); + + let parent_substs = match tcx.def_kind(def_id) { + DefKind::Closure => substs.as_closure().parent_substs(), + DefKind::Generator => substs.as_generator().parent_substs(), + DefKind::InlineConst => substs.as_inline_const().parent_substs(), + other => bug!("unexpected item {:?}", other), + }; + let parent_substs = tcx.mk_substs(parent_substs.iter()); + + assert_eq!(typeck_root_substs.len(), parent_substs.len()); + if let Err(_) = self.eq_substs( + typeck_root_substs, + parent_substs, + location.to_locations(), + ConstraintCategory::BoringNoLocation, + ) { + span_mirbug!( + self, + def_id, + "could not relate closure to parent {:?} != {:?}", + typeck_root_substs, + parent_substs + ); + } + + tcx.predicates_of(def_id).instantiate(tcx, substs) + } + + #[instrument(skip(self, body), level = "debug")] + fn typeck_mir(&mut self, body: &Body<'tcx>) { + self.last_span = body.span; + debug!(?body.span); + + for (local, local_decl) in body.local_decls.iter_enumerated() { + self.check_local(&body, local, local_decl); + } + + for (block, block_data) in body.basic_blocks().iter_enumerated() { + let mut location = Location { block, statement_index: 0 }; + for stmt in &block_data.statements { + if !stmt.source_info.span.is_dummy() { + self.last_span = stmt.source_info.span; + } + self.check_stmt(body, stmt, location); + location.statement_index += 1; + } + + self.check_terminator(&body, block_data.terminator(), location); + self.check_iscleanup(&body, block_data); + } + } +} + +trait NormalizeLocation: fmt::Debug + Copy { + fn to_locations(self) -> Locations; +} + +impl NormalizeLocation for Locations { + fn to_locations(self) -> Locations { + self + } +} + +impl NormalizeLocation for Location { + fn to_locations(self) -> Locations { + Locations::Single(self) + } +} + +/// Runs `infcx.instantiate_opaque_types`. Unlike other `TypeOp`s, +/// this is not canonicalized - it directly affects the main `InferCtxt` +/// that we use during MIR borrowchecking. +#[derive(Debug)] +pub(super) struct InstantiateOpaqueType<'tcx> { + pub base_universe: Option<ty::UniverseIndex>, + pub region_constraints: Option<RegionConstraintData<'tcx>>, + pub obligations: Vec<PredicateObligation<'tcx>>, +} + +impl<'tcx> TypeOp<'tcx> for InstantiateOpaqueType<'tcx> { + type Output = (); + /// We use this type itself to store the information used + /// when reporting errors. Since this is not a query, we don't + /// re-run anything during error reporting - we just use the information + /// we saved to help extract an error from the already-existing region + /// constraints in our `InferCtxt` + type ErrorInfo = InstantiateOpaqueType<'tcx>; + + fn fully_perform(mut self, infcx: &InferCtxt<'_, 'tcx>) -> Fallible<TypeOpOutput<'tcx, Self>> { + let (mut output, region_constraints) = scrape_region_constraints(infcx, || { + Ok(InferOk { value: (), obligations: self.obligations.clone() }) + })?; + self.region_constraints = Some(region_constraints); + output.error_info = Some(self); + Ok(output) + } +} diff --git a/compiler/rustc_borrowck/src/type_check/relate_tys.rs b/compiler/rustc_borrowck/src/type_check/relate_tys.rs new file mode 100644 index 000000000..c97a6a1a6 --- /dev/null +++ b/compiler/rustc_borrowck/src/type_check/relate_tys.rs @@ -0,0 +1,187 @@ +use rustc_infer::infer::nll_relate::{NormalizationStrategy, TypeRelating, TypeRelatingDelegate}; +use rustc_infer::infer::NllRegionVariableOrigin; +use rustc_infer::traits::ObligationCause; +use rustc_middle::mir::ConstraintCategory; +use rustc_middle::ty::error::TypeError; +use rustc_middle::ty::relate::TypeRelation; +use rustc_middle::ty::{self, Const, Ty}; +use rustc_span::Span; +use rustc_trait_selection::traits::query::Fallible; + +use crate::constraints::OutlivesConstraint; +use crate::diagnostics::UniverseInfo; +use crate::type_check::{InstantiateOpaqueType, Locations, TypeChecker}; + +impl<'a, 'tcx> TypeChecker<'a, 'tcx> { + /// Adds sufficient constraints to ensure that `a R b` where `R` depends on `v`: + /// + /// - "Covariant" `a <: b` + /// - "Invariant" `a == b` + /// - "Contravariant" `a :> b` + /// + /// N.B., the type `a` is permitted to have unresolved inference + /// variables, but not the type `b`. + #[instrument(skip(self), level = "debug")] + pub(super) fn relate_types( + &mut self, + a: Ty<'tcx>, + v: ty::Variance, + b: Ty<'tcx>, + locations: Locations, + category: ConstraintCategory<'tcx>, + ) -> Fallible<()> { + TypeRelating::new( + self.infcx, + NllTypeRelatingDelegate::new(self, locations, category, UniverseInfo::relate(a, b)), + v, + ) + .relate(a, b)?; + Ok(()) + } + + /// Add sufficient constraints to ensure `a == b`. See also [Self::relate_types]. + pub(super) fn eq_substs( + &mut self, + a: ty::SubstsRef<'tcx>, + b: ty::SubstsRef<'tcx>, + locations: Locations, + category: ConstraintCategory<'tcx>, + ) -> Fallible<()> { + TypeRelating::new( + self.infcx, + NllTypeRelatingDelegate::new(self, locations, category, UniverseInfo::other()), + ty::Variance::Invariant, + ) + .relate(a, b)?; + Ok(()) + } +} + +struct NllTypeRelatingDelegate<'me, 'bccx, 'tcx> { + type_checker: &'me mut TypeChecker<'bccx, 'tcx>, + + /// Where (and why) is this relation taking place? + locations: Locations, + + /// What category do we assign the resulting `'a: 'b` relationships? + category: ConstraintCategory<'tcx>, + + /// Information so that error reporting knows what types we are relating + /// when reporting a bound region error. + universe_info: UniverseInfo<'tcx>, +} + +impl<'me, 'bccx, 'tcx> NllTypeRelatingDelegate<'me, 'bccx, 'tcx> { + fn new( + type_checker: &'me mut TypeChecker<'bccx, 'tcx>, + locations: Locations, + category: ConstraintCategory<'tcx>, + universe_info: UniverseInfo<'tcx>, + ) -> Self { + Self { type_checker, locations, category, universe_info } + } +} + +impl<'tcx> TypeRelatingDelegate<'tcx> for NllTypeRelatingDelegate<'_, '_, 'tcx> { + fn span(&self) -> Span { + self.locations.span(self.type_checker.body) + } + + fn param_env(&self) -> ty::ParamEnv<'tcx> { + self.type_checker.param_env + } + + fn create_next_universe(&mut self) -> ty::UniverseIndex { + let universe = self.type_checker.infcx.create_next_universe(); + self.type_checker + .borrowck_context + .constraints + .universe_causes + .insert(universe, self.universe_info.clone()); + universe + } + + fn next_existential_region_var(&mut self, from_forall: bool) -> ty::Region<'tcx> { + let origin = NllRegionVariableOrigin::Existential { from_forall }; + self.type_checker.infcx.next_nll_region_var(origin) + } + + fn next_placeholder_region(&mut self, placeholder: ty::PlaceholderRegion) -> ty::Region<'tcx> { + self.type_checker + .borrowck_context + .constraints + .placeholder_region(self.type_checker.infcx, placeholder) + } + + fn generalize_existential(&mut self, universe: ty::UniverseIndex) -> ty::Region<'tcx> { + self.type_checker.infcx.next_nll_region_var_in_universe( + NllRegionVariableOrigin::Existential { from_forall: false }, + universe, + ) + } + + fn push_outlives( + &mut self, + sup: ty::Region<'tcx>, + sub: ty::Region<'tcx>, + info: ty::VarianceDiagInfo<'tcx>, + ) { + let sub = self.type_checker.borrowck_context.universal_regions.to_region_vid(sub); + let sup = self.type_checker.borrowck_context.universal_regions.to_region_vid(sup); + self.type_checker.borrowck_context.constraints.outlives_constraints.push( + OutlivesConstraint { + sup, + sub, + locations: self.locations, + span: self.locations.span(self.type_checker.body), + category: self.category, + variance_info: info, + }, + ); + } + + // We don't have to worry about the equality of consts during borrow checking + // as consts always have a static lifetime. + // FIXME(oli-obk): is this really true? We can at least have HKL and with + // inline consts we may have further lifetimes that may be unsound to treat as + // 'static. + fn const_equate(&mut self, _a: Const<'tcx>, _b: Const<'tcx>) {} + + fn normalization() -> NormalizationStrategy { + NormalizationStrategy::Eager + } + + fn forbid_inference_vars() -> bool { + true + } + + fn register_opaque_type( + &mut self, + a: Ty<'tcx>, + b: Ty<'tcx>, + a_is_expected: bool, + ) -> Result<(), TypeError<'tcx>> { + let param_env = self.param_env(); + let span = self.span(); + let def_id = self.type_checker.body.source.def_id().expect_local(); + let body_id = self.type_checker.tcx().hir().local_def_id_to_hir_id(def_id); + let cause = ObligationCause::misc(span, body_id); + self.type_checker + .fully_perform_op( + self.locations, + self.category, + InstantiateOpaqueType { + obligations: self + .type_checker + .infcx + .handle_opaque_type(a, b, a_is_expected, &cause, param_env)? + .obligations, + // These fields are filled in during execution of the operation + base_universe: None, + region_constraints: None, + }, + ) + .unwrap(); + Ok(()) + } +} |