diff options
Diffstat (limited to 'compiler/rustc_trait_selection/src/traits/query')
14 files changed, 1121 insertions, 0 deletions
diff --git a/compiler/rustc_trait_selection/src/traits/query/dropck_outlives.rs b/compiler/rustc_trait_selection/src/traits/query/dropck_outlives.rs new file mode 100644 index 000000000..aad3c37f8 --- /dev/null +++ b/compiler/rustc_trait_selection/src/traits/query/dropck_outlives.rs @@ -0,0 +1,73 @@ +use rustc_middle::ty::{self, Ty, TyCtxt}; + +pub use rustc_middle::traits::query::{DropckConstraint, DropckOutlivesResult}; + +/// This returns true if the type `ty` is "trivial" for +/// dropck-outlives -- that is, if it doesn't require any types to +/// outlive. This is similar but not *quite* the same as the +/// `needs_drop` test in the compiler already -- that is, for every +/// type T for which this function return true, needs-drop would +/// return `false`. But the reverse does not hold: in particular, +/// `needs_drop` returns false for `PhantomData`, but it is not +/// trivial for dropck-outlives. +/// +/// Note also that `needs_drop` requires a "global" type (i.e., one +/// with erased regions), but this function does not. +/// +// FIXME(@lcnr): remove this module and move this function somewhere else. +pub fn trivial_dropck_outlives<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> bool { + match ty.kind() { + // None of these types have a destructor and hence they do not + // require anything in particular to outlive the dtor's + // execution. + ty::Infer(ty::FreshIntTy(_)) + | ty::Infer(ty::FreshFloatTy(_)) + | ty::Bool + | ty::Int(_) + | ty::Uint(_) + | ty::Float(_) + | ty::Never + | ty::FnDef(..) + | ty::FnPtr(_) + | ty::Char + | ty::GeneratorWitness(..) + | ty::RawPtr(_) + | ty::Ref(..) + | ty::Str + | ty::Foreign(..) + | ty::Error(_) => true, + + // [T; N] and [T] have same properties as T. + ty::Array(ty, _) | ty::Slice(ty) => trivial_dropck_outlives(tcx, *ty), + + // (T1..Tn) and closures have same properties as T1..Tn -- + // check if *all* of them are trivial. + ty::Tuple(tys) => tys.iter().all(|t| trivial_dropck_outlives(tcx, t)), + ty::Closure(_, ref substs) => { + trivial_dropck_outlives(tcx, substs.as_closure().tupled_upvars_ty()) + } + + ty::Adt(def, _) => { + if Some(def.did()) == tcx.lang_items().manually_drop() { + // `ManuallyDrop` never has a dtor. + true + } else { + // Other types might. Moreover, PhantomData doesn't + // have a dtor, but it is considered to own its + // content, so it is non-trivial. Unions can have `impl Drop`, + // and hence are non-trivial as well. + false + } + } + + // The following *might* require a destructor: needs deeper inspection. + ty::Dynamic(..) + | ty::Projection(..) + | ty::Param(_) + | ty::Opaque(..) + | ty::Placeholder(..) + | ty::Infer(_) + | ty::Bound(..) + | ty::Generator(..) => false, + } +} diff --git a/compiler/rustc_trait_selection/src/traits/query/evaluate_obligation.rs b/compiler/rustc_trait_selection/src/traits/query/evaluate_obligation.rs new file mode 100644 index 000000000..32669e23d --- /dev/null +++ b/compiler/rustc_trait_selection/src/traits/query/evaluate_obligation.rs @@ -0,0 +1,118 @@ +use rustc_middle::ty; + +use crate::infer::canonical::OriginalQueryValues; +use crate::infer::InferCtxt; +use crate::traits::{ + EvaluationResult, OverflowError, PredicateObligation, SelectionContext, TraitQueryMode, +}; + +pub trait InferCtxtExt<'tcx> { + fn predicate_may_hold(&self, obligation: &PredicateObligation<'tcx>) -> bool; + + fn predicate_must_hold_considering_regions( + &self, + obligation: &PredicateObligation<'tcx>, + ) -> bool; + + fn predicate_must_hold_modulo_regions(&self, obligation: &PredicateObligation<'tcx>) -> bool; + + fn evaluate_obligation( + &self, + obligation: &PredicateObligation<'tcx>, + ) -> Result<EvaluationResult, OverflowError>; + + // Helper function that canonicalizes and runs the query. If an + // overflow results, we re-run it in the local context so we can + // report a nice error. + /*crate*/ + fn evaluate_obligation_no_overflow( + &self, + obligation: &PredicateObligation<'tcx>, + ) -> EvaluationResult; +} + +impl<'cx, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'cx, 'tcx> { + /// Evaluates whether the predicate can be satisfied (by any means) + /// in the given `ParamEnv`. + fn predicate_may_hold(&self, obligation: &PredicateObligation<'tcx>) -> bool { + self.evaluate_obligation_no_overflow(obligation).may_apply() + } + + /// Evaluates whether the predicate can be satisfied in the given + /// `ParamEnv`, and returns `false` if not certain. However, this is + /// not entirely accurate if inference variables are involved. + /// + /// This version may conservatively fail when outlives obligations + /// are required. + fn predicate_must_hold_considering_regions( + &self, + obligation: &PredicateObligation<'tcx>, + ) -> bool { + self.evaluate_obligation_no_overflow(obligation).must_apply_considering_regions() + } + + /// Evaluates whether the predicate can be satisfied in the given + /// `ParamEnv`, and returns `false` if not certain. However, this is + /// not entirely accurate if inference variables are involved. + /// + /// This version ignores all outlives constraints. + fn predicate_must_hold_modulo_regions(&self, obligation: &PredicateObligation<'tcx>) -> bool { + self.evaluate_obligation_no_overflow(obligation).must_apply_modulo_regions() + } + + /// Evaluate a given predicate, capturing overflow and propagating it back. + fn evaluate_obligation( + &self, + obligation: &PredicateObligation<'tcx>, + ) -> Result<EvaluationResult, OverflowError> { + let mut _orig_values = OriginalQueryValues::default(); + + let param_env = match obligation.predicate.kind().skip_binder() { + ty::PredicateKind::Trait(pred) => { + // we ignore the value set to it. + let mut _constness = pred.constness; + obligation + .param_env + .with_constness(_constness.and(obligation.param_env.constness())) + } + // constness has no effect on the given predicate. + _ => obligation.param_env.without_const(), + }; + + let c_pred = self + .canonicalize_query_keep_static(param_env.and(obligation.predicate), &mut _orig_values); + // Run canonical query. If overflow occurs, rerun from scratch but this time + // in standard trait query mode so that overflow is handled appropriately + // within `SelectionContext`. + self.tcx.at(obligation.cause.span()).evaluate_obligation(c_pred) + } + + // Helper function that canonicalizes and runs the query. If an + // overflow results, we re-run it in the local context so we can + // report a nice error. + fn evaluate_obligation_no_overflow( + &self, + obligation: &PredicateObligation<'tcx>, + ) -> EvaluationResult { + match self.evaluate_obligation(obligation) { + Ok(result) => result, + Err(OverflowError::Canonical) => { + let mut selcx = SelectionContext::with_query_mode(&self, TraitQueryMode::Standard); + selcx.evaluate_root_obligation(obligation).unwrap_or_else(|r| match r { + OverflowError::Canonical => { + span_bug!( + obligation.cause.span, + "Overflow should be caught earlier in standard query mode: {:?}, {:?}", + obligation, + r, + ) + } + OverflowError::ErrorReporting => EvaluationResult::EvaluatedToErr, + OverflowError::Error(_) => EvaluationResult::EvaluatedToErr, + }) + } + Err(OverflowError::ErrorReporting) => EvaluationResult::EvaluatedToErr, + Err(OverflowError::Error(_)) => EvaluationResult::EvaluatedToErr, + } + } +} diff --git a/compiler/rustc_trait_selection/src/traits/query/method_autoderef.rs b/compiler/rustc_trait_selection/src/traits/query/method_autoderef.rs new file mode 100644 index 000000000..3c0ebec93 --- /dev/null +++ b/compiler/rustc_trait_selection/src/traits/query/method_autoderef.rs @@ -0,0 +1,3 @@ +pub use rustc_middle::traits::query::{ + CandidateStep, MethodAutoderefBadTy, MethodAutoderefStepsResult, +}; diff --git a/compiler/rustc_trait_selection/src/traits/query/mod.rs b/compiler/rustc_trait_selection/src/traits/query/mod.rs new file mode 100644 index 000000000..ef3493678 --- /dev/null +++ b/compiler/rustc_trait_selection/src/traits/query/mod.rs @@ -0,0 +1,14 @@ +//! Experimental types for the trait query interface. The methods +//! defined in this module are all based on **canonicalization**, +//! which makes a canonical query by replacing unbound inference +//! variables and regions, so that results can be reused more broadly. +//! The providers for the queries defined here can be found in +//! `rustc_traits`. + +pub mod dropck_outlives; +pub mod evaluate_obligation; +pub mod method_autoderef; +pub mod normalize; +pub mod type_op; + +pub use rustc_middle::traits::query::*; diff --git a/compiler/rustc_trait_selection/src/traits/query/normalize.rs b/compiler/rustc_trait_selection/src/traits/query/normalize.rs new file mode 100644 index 000000000..449d7a7b4 --- /dev/null +++ b/compiler/rustc_trait_selection/src/traits/query/normalize.rs @@ -0,0 +1,354 @@ +//! Code for the 'normalization' query. This consists of a wrapper +//! which folds deeply, invoking the underlying +//! `normalize_projection_ty` query when it encounters projections. + +use crate::infer::at::At; +use crate::infer::canonical::OriginalQueryValues; +use crate::infer::{InferCtxt, InferOk}; +use crate::traits::error_reporting::InferCtxtExt; +use crate::traits::project::needs_normalization; +use crate::traits::{Obligation, ObligationCause, PredicateObligation, Reveal}; +use rustc_data_structures::sso::SsoHashMap; +use rustc_data_structures::stack::ensure_sufficient_stack; +use rustc_infer::traits::Normalized; +use rustc_middle::mir; +use rustc_middle::ty::fold::{FallibleTypeFolder, TypeFoldable, TypeSuperFoldable}; +use rustc_middle::ty::subst::Subst; +use rustc_middle::ty::visit::{TypeSuperVisitable, TypeVisitable}; +use rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitor}; + +use std::ops::ControlFlow; + +use super::NoSolution; + +pub use rustc_middle::traits::query::NormalizationResult; + +pub trait AtExt<'tcx> { + fn normalize<T>(&self, value: T) -> Result<Normalized<'tcx, T>, NoSolution> + where + T: TypeFoldable<'tcx>; +} + +impl<'cx, 'tcx> AtExt<'tcx> for At<'cx, 'tcx> { + /// Normalize `value` in the context of the inference context, + /// yielding a resulting type, or an error if `value` cannot be + /// normalized. If you don't care about regions, you should prefer + /// `normalize_erasing_regions`, which is more efficient. + /// + /// If the normalization succeeds and is unambiguous, returns back + /// the normalized value along with various outlives relations (in + /// the form of obligations that must be discharged). + /// + /// N.B., this will *eventually* be the main means of + /// normalizing, but for now should be used only when we actually + /// know that normalization will succeed, since error reporting + /// and other details are still "under development". + fn normalize<T>(&self, value: T) -> Result<Normalized<'tcx, T>, NoSolution> + where + T: TypeFoldable<'tcx>, + { + debug!( + "normalize::<{}>(value={:?}, param_env={:?})", + std::any::type_name::<T>(), + value, + self.param_env, + ); + if !needs_normalization(&value, self.param_env.reveal()) { + return Ok(Normalized { value, obligations: vec![] }); + } + + let mut normalizer = QueryNormalizer { + infcx: self.infcx, + cause: self.cause, + param_env: self.param_env, + obligations: vec![], + cache: SsoHashMap::new(), + anon_depth: 0, + universes: vec![], + }; + + // This is actually a consequence by the way `normalize_erasing_regions` works currently. + // Because it needs to call the `normalize_generic_arg_after_erasing_regions`, it folds + // through tys and consts in a `TypeFoldable`. Importantly, it skips binders, leaving us + // with trying to normalize with escaping bound vars. + // + // Here, we just add the universes that we *would* have created had we passed through the binders. + // + // We *could* replace escaping bound vars eagerly here, but it doesn't seem really necessary. + // The rest of the code is already set up to be lazy about replacing bound vars, + // and only when we actually have to normalize. + if value.has_escaping_bound_vars() { + let mut max_visitor = + MaxEscapingBoundVarVisitor { outer_index: ty::INNERMOST, escaping: 0 }; + value.visit_with(&mut max_visitor); + if max_visitor.escaping > 0 { + normalizer.universes.extend((0..max_visitor.escaping).map(|_| None)); + } + } + let result = value.try_fold_with(&mut normalizer); + info!( + "normalize::<{}>: result={:?} with {} obligations", + std::any::type_name::<T>(), + result, + normalizer.obligations.len(), + ); + debug!( + "normalize::<{}>: obligations={:?}", + std::any::type_name::<T>(), + normalizer.obligations, + ); + result.map(|value| Normalized { value, obligations: normalizer.obligations }) + } +} + +// Visitor to find the maximum escaping bound var +struct MaxEscapingBoundVarVisitor { + // The index which would count as escaping + outer_index: ty::DebruijnIndex, + escaping: usize, +} + +impl<'tcx> TypeVisitor<'tcx> for MaxEscapingBoundVarVisitor { + fn visit_binder<T: TypeVisitable<'tcx>>( + &mut self, + t: &ty::Binder<'tcx, T>, + ) -> ControlFlow<Self::BreakTy> { + self.outer_index.shift_in(1); + let result = t.super_visit_with(self); + self.outer_index.shift_out(1); + result + } + + #[inline] + fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> { + if t.outer_exclusive_binder() > self.outer_index { + self.escaping = self + .escaping + .max(t.outer_exclusive_binder().as_usize() - self.outer_index.as_usize()); + } + ControlFlow::CONTINUE + } + + #[inline] + fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> { + match *r { + ty::ReLateBound(debruijn, _) if debruijn > self.outer_index => { + self.escaping = + self.escaping.max(debruijn.as_usize() - self.outer_index.as_usize()); + } + _ => {} + } + ControlFlow::CONTINUE + } + + fn visit_const(&mut self, ct: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> { + match ct.kind() { + ty::ConstKind::Bound(debruijn, _) if debruijn >= self.outer_index => { + self.escaping = + self.escaping.max(debruijn.as_usize() - self.outer_index.as_usize()); + ControlFlow::CONTINUE + } + _ => ct.super_visit_with(self), + } + } +} + +struct QueryNormalizer<'cx, 'tcx> { + infcx: &'cx InferCtxt<'cx, 'tcx>, + cause: &'cx ObligationCause<'tcx>, + param_env: ty::ParamEnv<'tcx>, + obligations: Vec<PredicateObligation<'tcx>>, + cache: SsoHashMap<Ty<'tcx>, Ty<'tcx>>, + anon_depth: usize, + universes: Vec<Option<ty::UniverseIndex>>, +} + +impl<'cx, 'tcx> FallibleTypeFolder<'tcx> for QueryNormalizer<'cx, 'tcx> { + type Error = NoSolution; + + fn tcx<'c>(&'c self) -> TyCtxt<'tcx> { + self.infcx.tcx + } + + fn try_fold_binder<T: TypeFoldable<'tcx>>( + &mut self, + t: ty::Binder<'tcx, T>, + ) -> Result<ty::Binder<'tcx, T>, Self::Error> { + self.universes.push(None); + let t = t.try_super_fold_with(self); + self.universes.pop(); + t + } + + #[instrument(level = "debug", skip(self))] + fn try_fold_ty(&mut self, ty: Ty<'tcx>) -> Result<Ty<'tcx>, Self::Error> { + if !needs_normalization(&ty, self.param_env.reveal()) { + return Ok(ty); + } + + if let Some(ty) = self.cache.get(&ty) { + return Ok(*ty); + } + + // See note in `rustc_trait_selection::traits::project` about why we + // wait to fold the substs. + + // Wrap this in a closure so we don't accidentally return from the outer function + let res = (|| match *ty.kind() { + // This is really important. While we *can* handle this, this has + // severe performance implications for large opaque types with + // late-bound regions. See `issue-88862` benchmark. + ty::Opaque(def_id, substs) if !substs.has_escaping_bound_vars() => { + // Only normalize `impl Trait` outside of type inference, usually in codegen. + match self.param_env.reveal() { + Reveal::UserFacing => ty.try_super_fold_with(self), + + Reveal::All => { + let substs = substs.try_fold_with(self)?; + let recursion_limit = self.tcx().recursion_limit(); + if !recursion_limit.value_within_limit(self.anon_depth) { + let obligation = Obligation::with_depth( + self.cause.clone(), + recursion_limit.0, + self.param_env, + ty, + ); + self.infcx.report_overflow_error(&obligation, true); + } + + let generic_ty = self.tcx().bound_type_of(def_id); + let concrete_ty = generic_ty.subst(self.tcx(), substs); + self.anon_depth += 1; + if concrete_ty == ty { + bug!( + "infinite recursion generic_ty: {:#?}, substs: {:#?}, \ + concrete_ty: {:#?}, ty: {:#?}", + generic_ty, + substs, + concrete_ty, + ty + ); + } + let folded_ty = ensure_sufficient_stack(|| self.try_fold_ty(concrete_ty)); + self.anon_depth -= 1; + folded_ty + } + } + } + + ty::Projection(data) if !data.has_escaping_bound_vars() => { + // This branch is just an optimization: when we don't have escaping bound vars, + // we don't need to replace them with placeholders (see branch below). + + let tcx = self.infcx.tcx; + let data = data.try_fold_with(self)?; + + let mut orig_values = OriginalQueryValues::default(); + // HACK(matthewjasper) `'static` is special-cased in selection, + // so we cannot canonicalize it. + let c_data = self + .infcx + .canonicalize_query_keep_static(self.param_env.and(data), &mut orig_values); + debug!("QueryNormalizer: c_data = {:#?}", c_data); + debug!("QueryNormalizer: orig_values = {:#?}", orig_values); + let result = tcx.normalize_projection_ty(c_data)?; + // We don't expect ambiguity. + if result.is_ambiguous() { + bug!("unexpected ambiguity: {:?} {:?}", c_data, result); + } + let InferOk { value: result, obligations } = + self.infcx.instantiate_query_response_and_region_obligations( + self.cause, + self.param_env, + &orig_values, + result, + )?; + debug!("QueryNormalizer: result = {:#?}", result); + debug!("QueryNormalizer: obligations = {:#?}", obligations); + self.obligations.extend(obligations); + Ok(result.normalized_ty) + } + + ty::Projection(data) => { + // See note in `rustc_trait_selection::traits::project` + + let tcx = self.infcx.tcx; + let infcx = self.infcx; + let (data, mapped_regions, mapped_types, mapped_consts) = + crate::traits::project::BoundVarReplacer::replace_bound_vars( + infcx, + &mut self.universes, + data, + ); + let data = data.try_fold_with(self)?; + + let mut orig_values = OriginalQueryValues::default(); + // HACK(matthewjasper) `'static` is special-cased in selection, + // so we cannot canonicalize it. + let c_data = self + .infcx + .canonicalize_query_keep_static(self.param_env.and(data), &mut orig_values); + debug!("QueryNormalizer: c_data = {:#?}", c_data); + debug!("QueryNormalizer: orig_values = {:#?}", orig_values); + let result = tcx.normalize_projection_ty(c_data)?; + // We don't expect ambiguity. + if result.is_ambiguous() { + bug!("unexpected ambiguity: {:?} {:?}", c_data, result); + } + let InferOk { value: result, obligations } = + self.infcx.instantiate_query_response_and_region_obligations( + self.cause, + self.param_env, + &orig_values, + result, + )?; + debug!("QueryNormalizer: result = {:#?}", result); + debug!("QueryNormalizer: obligations = {:#?}", obligations); + self.obligations.extend(obligations); + Ok(crate::traits::project::PlaceholderReplacer::replace_placeholders( + infcx, + mapped_regions, + mapped_types, + mapped_consts, + &self.universes, + result.normalized_ty, + )) + } + + _ => ty.try_super_fold_with(self), + })()?; + self.cache.insert(ty, res); + Ok(res) + } + + fn try_fold_const( + &mut self, + constant: ty::Const<'tcx>, + ) -> Result<ty::Const<'tcx>, Self::Error> { + let constant = constant.try_super_fold_with(self)?; + Ok(constant.eval(self.infcx.tcx, self.param_env)) + } + + fn try_fold_mir_const( + &mut self, + constant: mir::ConstantKind<'tcx>, + ) -> Result<mir::ConstantKind<'tcx>, Self::Error> { + Ok(match constant { + mir::ConstantKind::Ty(c) => { + let const_folded = c.try_super_fold_with(self)?; + match const_folded.kind() { + ty::ConstKind::Value(valtree) => { + let tcx = self.infcx.tcx; + let ty = const_folded.ty(); + let const_val = tcx.valtree_to_const_val((ty, valtree)); + debug!(?ty, ?valtree, ?const_val); + + mir::ConstantKind::Val(const_val, ty) + } + _ => mir::ConstantKind::Ty(const_folded), + } + } + mir::ConstantKind::Val(_, _) => constant.try_super_fold_with(self)?, + }) + } +} diff --git a/compiler/rustc_trait_selection/src/traits/query/type_op/ascribe_user_type.rs b/compiler/rustc_trait_selection/src/traits/query/type_op/ascribe_user_type.rs new file mode 100644 index 000000000..86b015767 --- /dev/null +++ b/compiler/rustc_trait_selection/src/traits/query/type_op/ascribe_user_type.rs @@ -0,0 +1,23 @@ +use crate::infer::canonical::{Canonicalized, CanonicalizedQueryResponse}; +use crate::traits::query::Fallible; +use rustc_middle::ty::{ParamEnvAnd, TyCtxt}; + +pub use rustc_middle::traits::query::type_op::AscribeUserType; + +impl<'tcx> super::QueryTypeOp<'tcx> for AscribeUserType<'tcx> { + type QueryResponse = (); + + fn try_fast_path( + _tcx: TyCtxt<'tcx>, + _key: &ParamEnvAnd<'tcx, Self>, + ) -> Option<Self::QueryResponse> { + None + } + + fn perform_query( + tcx: TyCtxt<'tcx>, + canonicalized: Canonicalized<'tcx, ParamEnvAnd<'tcx, Self>>, + ) -> Fallible<CanonicalizedQueryResponse<'tcx, ()>> { + tcx.type_op_ascribe_user_type(canonicalized) + } +} diff --git a/compiler/rustc_trait_selection/src/traits/query/type_op/custom.rs b/compiler/rustc_trait_selection/src/traits/query/type_op/custom.rs new file mode 100644 index 000000000..c99564936 --- /dev/null +++ b/compiler/rustc_trait_selection/src/traits/query/type_op/custom.rs @@ -0,0 +1,117 @@ +use crate::infer::canonical::query_response; +use crate::infer::{InferCtxt, InferOk}; +use crate::traits::engine::TraitEngineExt as _; +use crate::traits::query::type_op::TypeOpOutput; +use crate::traits::query::Fallible; +use crate::traits::TraitEngine; +use rustc_infer::infer::region_constraints::RegionConstraintData; +use rustc_infer::traits::TraitEngineExt as _; +use rustc_span::source_map::DUMMY_SP; + +use std::fmt; + +pub struct CustomTypeOp<F, G> { + closure: F, + description: G, +} + +impl<F, G> CustomTypeOp<F, G> { + pub fn new<'tcx, R>(closure: F, description: G) -> Self + where + F: FnOnce(&InferCtxt<'_, 'tcx>) -> Fallible<InferOk<'tcx, R>>, + G: Fn() -> String, + { + CustomTypeOp { closure, description } + } +} + +impl<'tcx, F, R, G> super::TypeOp<'tcx> for CustomTypeOp<F, G> +where + F: for<'a, 'cx> FnOnce(&'a InferCtxt<'cx, 'tcx>) -> Fallible<InferOk<'tcx, R>>, + G: Fn() -> String, +{ + type Output = R; + /// We can't do any custom error reporting for `CustomTypeOp`, so + /// we can use `!` to enforce that the implementation never provides it. + type ErrorInfo = !; + + /// Processes the operation and all resulting obligations, + /// returning the final result along with any region constraints + /// (they will be given over to the NLL region solver). + fn fully_perform(self, infcx: &InferCtxt<'_, 'tcx>) -> Fallible<TypeOpOutput<'tcx, Self>> { + if cfg!(debug_assertions) { + info!("fully_perform({:?})", self); + } + + Ok(scrape_region_constraints(infcx, || (self.closure)(infcx))?.0) + } +} + +impl<F, G> fmt::Debug for CustomTypeOp<F, G> +where + G: Fn() -> String, +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "{}", (self.description)()) + } +} + +/// Executes `op` and then scrapes out all the "old style" region +/// constraints that result, creating query-region-constraints. +pub fn scrape_region_constraints<'tcx, Op: super::TypeOp<'tcx, Output = R>, R>( + infcx: &InferCtxt<'_, 'tcx>, + op: impl FnOnce() -> Fallible<InferOk<'tcx, R>>, +) -> Fallible<(TypeOpOutput<'tcx, Op>, RegionConstraintData<'tcx>)> { + let mut fulfill_cx = <dyn TraitEngine<'_>>::new(infcx.tcx); + + // During NLL, we expect that nobody will register region + // obligations **except** as part of a custom type op (and, at the + // end of each custom type op, we scrape out the region + // obligations that resulted). So this vector should be empty on + // entry. + let pre_obligations = infcx.take_registered_region_obligations(); + assert!( + pre_obligations.is_empty(), + "scrape_region_constraints: incoming region obligations = {:#?}", + pre_obligations, + ); + + let InferOk { value, obligations } = infcx.commit_if_ok(|_| op())?; + fulfill_cx.register_predicate_obligations(infcx, obligations); + let errors = fulfill_cx.select_all_or_error(infcx); + if !errors.is_empty() { + infcx.tcx.sess.diagnostic().delay_span_bug( + DUMMY_SP, + &format!("errors selecting obligation during MIR typeck: {:?}", errors), + ); + } + + let region_obligations = infcx.take_registered_region_obligations(); + + let region_constraint_data = infcx.take_and_reset_region_constraints(); + + let region_constraints = query_response::make_query_region_constraints( + infcx.tcx, + region_obligations + .iter() + .map(|r_o| (r_o.sup_type, r_o.sub_region)) + .map(|(ty, r)| (infcx.resolve_vars_if_possible(ty), r)), + ®ion_constraint_data, + ); + + if region_constraints.is_empty() { + Ok(( + TypeOpOutput { output: value, constraints: None, error_info: None }, + region_constraint_data, + )) + } else { + Ok(( + TypeOpOutput { + output: value, + constraints: Some(infcx.tcx.arena.alloc(region_constraints)), + error_info: None, + }, + region_constraint_data, + )) + } +} diff --git a/compiler/rustc_trait_selection/src/traits/query/type_op/eq.rs b/compiler/rustc_trait_selection/src/traits/query/type_op/eq.rs new file mode 100644 index 000000000..490114aac --- /dev/null +++ b/compiler/rustc_trait_selection/src/traits/query/type_op/eq.rs @@ -0,0 +1,23 @@ +use crate::infer::canonical::{Canonicalized, CanonicalizedQueryResponse}; +use crate::traits::query::Fallible; +use rustc_middle::ty::{ParamEnvAnd, TyCtxt}; + +pub use rustc_middle::traits::query::type_op::Eq; + +impl<'tcx> super::QueryTypeOp<'tcx> for Eq<'tcx> { + type QueryResponse = (); + + fn try_fast_path( + _tcx: TyCtxt<'tcx>, + key: &ParamEnvAnd<'tcx, Eq<'tcx>>, + ) -> Option<Self::QueryResponse> { + if key.value.a == key.value.b { Some(()) } else { None } + } + + fn perform_query( + tcx: TyCtxt<'tcx>, + canonicalized: Canonicalized<'tcx, ParamEnvAnd<'tcx, Self>>, + ) -> Fallible<CanonicalizedQueryResponse<'tcx, ()>> { + tcx.type_op_eq(canonicalized) + } +} diff --git a/compiler/rustc_trait_selection/src/traits/query/type_op/implied_outlives_bounds.rs b/compiler/rustc_trait_selection/src/traits/query/type_op/implied_outlives_bounds.rs new file mode 100644 index 000000000..2a3319f0f --- /dev/null +++ b/compiler/rustc_trait_selection/src/traits/query/type_op/implied_outlives_bounds.rs @@ -0,0 +1,42 @@ +use crate::infer::canonical::{Canonicalized, CanonicalizedQueryResponse}; +use crate::traits::query::Fallible; +use rustc_infer::traits::query::OutlivesBound; +use rustc_middle::ty::{self, ParamEnvAnd, Ty, TyCtxt}; + +#[derive(Copy, Clone, Debug, HashStable, TypeFoldable, TypeVisitable, Lift)] +pub struct ImpliedOutlivesBounds<'tcx> { + pub ty: Ty<'tcx>, +} + +impl<'tcx> super::QueryTypeOp<'tcx> for ImpliedOutlivesBounds<'tcx> { + type QueryResponse = Vec<OutlivesBound<'tcx>>; + + fn try_fast_path( + _tcx: TyCtxt<'tcx>, + key: &ParamEnvAnd<'tcx, Self>, + ) -> Option<Self::QueryResponse> { + // Don't go into the query for things that can't possibly have lifetimes. + match key.value.ty.kind() { + ty::Tuple(elems) if elems.is_empty() => Some(vec![]), + ty::Never | ty::Str | ty::Bool | ty::Char | ty::Int(_) | ty::Uint(_) | ty::Float(_) => { + Some(vec![]) + } + _ => None, + } + } + + fn perform_query( + tcx: TyCtxt<'tcx>, + canonicalized: Canonicalized<'tcx, ParamEnvAnd<'tcx, Self>>, + ) -> Fallible<CanonicalizedQueryResponse<'tcx, Self::QueryResponse>> { + // FIXME this `unchecked_map` is only necessary because the + // query is defined as taking a `ParamEnvAnd<Ty>`; it should + // take an `ImpliedOutlivesBounds` instead + let canonicalized = canonicalized.unchecked_map(|ParamEnvAnd { param_env, value }| { + let ImpliedOutlivesBounds { ty } = value; + param_env.and(ty) + }); + + tcx.implied_outlives_bounds(canonicalized) + } +} diff --git a/compiler/rustc_trait_selection/src/traits/query/type_op/mod.rs b/compiler/rustc_trait_selection/src/traits/query/type_op/mod.rs new file mode 100644 index 000000000..578e1d00c --- /dev/null +++ b/compiler/rustc_trait_selection/src/traits/query/type_op/mod.rs @@ -0,0 +1,168 @@ +use crate::infer::canonical::{ + Canonicalized, CanonicalizedQueryResponse, OriginalQueryValues, QueryRegionConstraints, +}; +use crate::infer::{InferCtxt, InferOk}; +use crate::traits::query::Fallible; +use crate::traits::ObligationCause; +use rustc_infer::infer::canonical::{Canonical, Certainty}; +use rustc_infer::traits::query::NoSolution; +use rustc_infer::traits::PredicateObligations; +use rustc_middle::ty::fold::TypeFoldable; +use rustc_middle::ty::{ParamEnvAnd, TyCtxt}; +use std::fmt; + +pub mod ascribe_user_type; +pub mod custom; +pub mod eq; +pub mod implied_outlives_bounds; +pub mod normalize; +pub mod outlives; +pub mod prove_predicate; +pub mod subtype; + +pub use rustc_middle::traits::query::type_op::*; + +/// "Type ops" are used in NLL to perform some particular action and +/// extract out the resulting region constraints (or an error if it +/// cannot be completed). +pub trait TypeOp<'tcx>: Sized + fmt::Debug { + type Output; + type ErrorInfo; + + /// Processes the operation and all resulting obligations, + /// returning the final result along with any region constraints + /// (they will be given over to the NLL region solver). + fn fully_perform(self, infcx: &InferCtxt<'_, 'tcx>) -> Fallible<TypeOpOutput<'tcx, Self>>; +} + +/// The output from performing a type op +pub struct TypeOpOutput<'tcx, Op: TypeOp<'tcx>> { + /// The output from the type op. + pub output: Op::Output, + /// Any region constraints from performing the type op. + pub constraints: Option<&'tcx QueryRegionConstraints<'tcx>>, + /// Used for error reporting to be able to rerun the query + pub error_info: Option<Op::ErrorInfo>, +} + +/// "Query type ops" are type ops that are implemented using a +/// [canonical query][c]. The `Self` type here contains the kernel of +/// information needed to do the operation -- `TypeOp` is actually +/// implemented for `ParamEnvAnd<Self>`, since we always need to bring +/// along a parameter environment as well. For query type-ops, we will +/// first canonicalize the key and then invoke the query on the tcx, +/// which produces the resulting query region constraints. +/// +/// [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html +pub trait QueryTypeOp<'tcx>: fmt::Debug + Copy + TypeFoldable<'tcx> + 'tcx { + type QueryResponse: TypeFoldable<'tcx>; + + /// Give query the option for a simple fast path that never + /// actually hits the tcx cache lookup etc. Return `Some(r)` with + /// a final result or `None` to do the full path. + fn try_fast_path( + tcx: TyCtxt<'tcx>, + key: &ParamEnvAnd<'tcx, Self>, + ) -> Option<Self::QueryResponse>; + + /// Performs the actual query with the canonicalized key -- the + /// real work happens here. This method is not given an `infcx` + /// because it shouldn't need one -- and if it had access to one, + /// it might do things like invoke `sub_regions`, which would be + /// bad, because it would create subregion relationships that are + /// not captured in the return value. + fn perform_query( + tcx: TyCtxt<'tcx>, + canonicalized: Canonicalized<'tcx, ParamEnvAnd<'tcx, Self>>, + ) -> Fallible<CanonicalizedQueryResponse<'tcx, Self::QueryResponse>>; + + fn fully_perform_into( + query_key: ParamEnvAnd<'tcx, Self>, + infcx: &InferCtxt<'_, 'tcx>, + output_query_region_constraints: &mut QueryRegionConstraints<'tcx>, + ) -> Fallible<( + Self::QueryResponse, + Option<Canonical<'tcx, ParamEnvAnd<'tcx, Self>>>, + PredicateObligations<'tcx>, + Certainty, + )> { + if let Some(result) = QueryTypeOp::try_fast_path(infcx.tcx, &query_key) { + return Ok((result, None, vec![], Certainty::Proven)); + } + + // FIXME(#33684) -- We need to use + // `canonicalize_query_keep_static` here because of things + // like the subtype query, which go awry around + // `'static` otherwise. + let mut canonical_var_values = OriginalQueryValues::default(); + let old_param_env = query_key.param_env; + let canonical_self = + infcx.canonicalize_query_keep_static(query_key, &mut canonical_var_values); + let canonical_result = Self::perform_query(infcx.tcx, canonical_self)?; + + let InferOk { value, obligations } = infcx + .instantiate_nll_query_response_and_region_obligations( + &ObligationCause::dummy(), + old_param_env, + &canonical_var_values, + canonical_result, + output_query_region_constraints, + )?; + + Ok((value, Some(canonical_self), obligations, canonical_result.value.certainty)) + } +} + +impl<'tcx, Q> TypeOp<'tcx> for ParamEnvAnd<'tcx, Q> +where + Q: QueryTypeOp<'tcx>, +{ + type Output = Q::QueryResponse; + type ErrorInfo = Canonical<'tcx, ParamEnvAnd<'tcx, Q>>; + + fn fully_perform(self, infcx: &InferCtxt<'_, 'tcx>) -> Fallible<TypeOpOutput<'tcx, Self>> { + let mut region_constraints = QueryRegionConstraints::default(); + let (output, error_info, mut obligations, _) = + Q::fully_perform_into(self, infcx, &mut region_constraints)?; + + // Typically, instantiating NLL query results does not + // create obligations. However, in some cases there + // are unresolved type variables, and unify them *can* + // create obligations. In that case, we have to go + // fulfill them. We do this via a (recursive) query. + while !obligations.is_empty() { + trace!("{:#?}", obligations); + let mut progress = false; + for obligation in std::mem::take(&mut obligations) { + let obligation = infcx.resolve_vars_if_possible(obligation); + match ProvePredicate::fully_perform_into( + obligation.param_env.and(ProvePredicate::new(obligation.predicate)), + infcx, + &mut region_constraints, + ) { + Ok(((), _, new, certainty)) => { + obligations.extend(new); + progress = true; + if let Certainty::Ambiguous = certainty { + obligations.push(obligation); + } + } + Err(_) => obligations.push(obligation), + } + } + if !progress { + return Err(NoSolution); + } + } + + Ok(TypeOpOutput { + output, + constraints: if region_constraints.is_empty() { + None + } else { + Some(infcx.tcx.arena.alloc(region_constraints)) + }, + error_info, + }) + } +} diff --git a/compiler/rustc_trait_selection/src/traits/query/type_op/normalize.rs b/compiler/rustc_trait_selection/src/traits/query/type_op/normalize.rs new file mode 100644 index 000000000..e92ca7325 --- /dev/null +++ b/compiler/rustc_trait_selection/src/traits/query/type_op/normalize.rs @@ -0,0 +1,68 @@ +use crate::infer::canonical::{Canonicalized, CanonicalizedQueryResponse}; +use crate::traits::query::Fallible; +use rustc_middle::ty::fold::TypeFoldable; +use rustc_middle::ty::{self, Lift, ParamEnvAnd, Ty, TyCtxt}; +use std::fmt; + +pub use rustc_middle::traits::query::type_op::Normalize; + +impl<'tcx, T> super::QueryTypeOp<'tcx> for Normalize<T> +where + T: Normalizable<'tcx> + 'tcx, +{ + type QueryResponse = T; + + fn try_fast_path(_tcx: TyCtxt<'tcx>, key: &ParamEnvAnd<'tcx, Self>) -> Option<T> { + if !key.value.value.has_projections() { Some(key.value.value) } else { None } + } + + fn perform_query( + tcx: TyCtxt<'tcx>, + canonicalized: Canonicalized<'tcx, ParamEnvAnd<'tcx, Self>>, + ) -> Fallible<CanonicalizedQueryResponse<'tcx, Self::QueryResponse>> { + T::type_op_method(tcx, canonicalized) + } +} + +pub trait Normalizable<'tcx>: fmt::Debug + TypeFoldable<'tcx> + Lift<'tcx> + Copy { + fn type_op_method( + tcx: TyCtxt<'tcx>, + canonicalized: Canonicalized<'tcx, ParamEnvAnd<'tcx, Normalize<Self>>>, + ) -> Fallible<CanonicalizedQueryResponse<'tcx, Self>>; +} + +impl<'tcx> Normalizable<'tcx> for Ty<'tcx> { + fn type_op_method( + tcx: TyCtxt<'tcx>, + canonicalized: Canonicalized<'tcx, ParamEnvAnd<'tcx, Normalize<Self>>>, + ) -> Fallible<CanonicalizedQueryResponse<'tcx, Self>> { + tcx.type_op_normalize_ty(canonicalized) + } +} + +impl<'tcx> Normalizable<'tcx> for ty::Predicate<'tcx> { + fn type_op_method( + tcx: TyCtxt<'tcx>, + canonicalized: Canonicalized<'tcx, ParamEnvAnd<'tcx, Normalize<Self>>>, + ) -> Fallible<CanonicalizedQueryResponse<'tcx, Self>> { + tcx.type_op_normalize_predicate(canonicalized) + } +} + +impl<'tcx> Normalizable<'tcx> for ty::PolyFnSig<'tcx> { + fn type_op_method( + tcx: TyCtxt<'tcx>, + canonicalized: Canonicalized<'tcx, ParamEnvAnd<'tcx, Normalize<Self>>>, + ) -> Fallible<CanonicalizedQueryResponse<'tcx, Self>> { + tcx.type_op_normalize_poly_fn_sig(canonicalized) + } +} + +impl<'tcx> Normalizable<'tcx> for ty::FnSig<'tcx> { + fn type_op_method( + tcx: TyCtxt<'tcx>, + canonicalized: Canonicalized<'tcx, ParamEnvAnd<'tcx, Normalize<Self>>>, + ) -> Fallible<CanonicalizedQueryResponse<'tcx, Self>> { + tcx.type_op_normalize_fn_sig(canonicalized) + } +} diff --git a/compiler/rustc_trait_selection/src/traits/query/type_op/outlives.rs b/compiler/rustc_trait_selection/src/traits/query/type_op/outlives.rs new file mode 100644 index 000000000..b63382429 --- /dev/null +++ b/compiler/rustc_trait_selection/src/traits/query/type_op/outlives.rs @@ -0,0 +1,55 @@ +use crate::infer::canonical::{Canonicalized, CanonicalizedQueryResponse}; +use crate::traits::query::dropck_outlives::{trivial_dropck_outlives, DropckOutlivesResult}; +use crate::traits::query::Fallible; +use rustc_middle::ty::{ParamEnvAnd, Ty, TyCtxt}; + +#[derive(Copy, Clone, Debug, HashStable, TypeFoldable, TypeVisitable, Lift)] +pub struct DropckOutlives<'tcx> { + dropped_ty: Ty<'tcx>, +} + +impl<'tcx> DropckOutlives<'tcx> { + pub fn new(dropped_ty: Ty<'tcx>) -> Self { + DropckOutlives { dropped_ty } + } +} + +impl<'tcx> super::QueryTypeOp<'tcx> for DropckOutlives<'tcx> { + type QueryResponse = DropckOutlivesResult<'tcx>; + + fn try_fast_path( + tcx: TyCtxt<'tcx>, + key: &ParamEnvAnd<'tcx, Self>, + ) -> Option<Self::QueryResponse> { + if trivial_dropck_outlives(tcx, key.value.dropped_ty) { + Some(DropckOutlivesResult::default()) + } else { + None + } + } + + fn perform_query( + tcx: TyCtxt<'tcx>, + canonicalized: Canonicalized<'tcx, ParamEnvAnd<'tcx, Self>>, + ) -> Fallible<CanonicalizedQueryResponse<'tcx, Self::QueryResponse>> { + // Subtle: note that we are not invoking + // `infcx.at(...).dropck_outlives(...)` here, but rather the + // underlying `dropck_outlives` query. This same underlying + // query is also used by the + // `infcx.at(...).dropck_outlives(...)` fn. Avoiding the + // wrapper means we don't need an infcx in this code, which is + // good because the interface doesn't give us one (so that we + // know we are not registering any subregion relations or + // other things). + + // FIXME convert to the type expected by the `dropck_outlives` + // query. This should eventually be fixed by changing the + // *underlying query*. + let canonicalized = canonicalized.unchecked_map(|ParamEnvAnd { param_env, value }| { + let DropckOutlives { dropped_ty } = value; + param_env.and(dropped_ty) + }); + + tcx.dropck_outlives(canonicalized) + } +} diff --git a/compiler/rustc_trait_selection/src/traits/query/type_op/prove_predicate.rs b/compiler/rustc_trait_selection/src/traits/query/type_op/prove_predicate.rs new file mode 100644 index 000000000..081308ac7 --- /dev/null +++ b/compiler/rustc_trait_selection/src/traits/query/type_op/prove_predicate.rs @@ -0,0 +1,43 @@ +use crate::infer::canonical::{Canonicalized, CanonicalizedQueryResponse}; +use crate::traits::query::Fallible; +use rustc_middle::ty::{self, ParamEnvAnd, TyCtxt}; + +pub use rustc_middle::traits::query::type_op::ProvePredicate; + +impl<'tcx> super::QueryTypeOp<'tcx> for ProvePredicate<'tcx> { + type QueryResponse = (); + + fn try_fast_path( + tcx: TyCtxt<'tcx>, + key: &ParamEnvAnd<'tcx, Self>, + ) -> Option<Self::QueryResponse> { + // Proving Sized, very often on "obviously sized" types like + // `&T`, accounts for about 60% percentage of the predicates + // we have to prove. No need to canonicalize and all that for + // such cases. + if let ty::PredicateKind::Trait(trait_ref) = key.value.predicate.kind().skip_binder() { + if let Some(sized_def_id) = tcx.lang_items().sized_trait() { + if trait_ref.def_id() == sized_def_id { + if trait_ref.self_ty().is_trivially_sized(tcx) { + return Some(()); + } + } + } + } + + None + } + + fn perform_query( + tcx: TyCtxt<'tcx>, + mut canonicalized: Canonicalized<'tcx, ParamEnvAnd<'tcx, Self>>, + ) -> Fallible<CanonicalizedQueryResponse<'tcx, ()>> { + match canonicalized.value.value.predicate.kind().skip_binder() { + ty::PredicateKind::Trait(pred) => { + canonicalized.value.param_env.remap_constness_with(pred.constness); + } + _ => canonicalized.value.param_env = canonicalized.value.param_env.without_const(), + } + tcx.type_op_prove_predicate(canonicalized) + } +} diff --git a/compiler/rustc_trait_selection/src/traits/query/type_op/subtype.rs b/compiler/rustc_trait_selection/src/traits/query/type_op/subtype.rs new file mode 100644 index 000000000..57290b669 --- /dev/null +++ b/compiler/rustc_trait_selection/src/traits/query/type_op/subtype.rs @@ -0,0 +1,20 @@ +use crate::infer::canonical::{Canonicalized, CanonicalizedQueryResponse}; +use crate::traits::query::Fallible; +use rustc_middle::ty::{ParamEnvAnd, TyCtxt}; + +pub use rustc_middle::traits::query::type_op::Subtype; + +impl<'tcx> super::QueryTypeOp<'tcx> for Subtype<'tcx> { + type QueryResponse = (); + + fn try_fast_path(_tcx: TyCtxt<'tcx>, key: &ParamEnvAnd<'tcx, Self>) -> Option<()> { + if key.value.sub == key.value.sup { Some(()) } else { None } + } + + fn perform_query( + tcx: TyCtxt<'tcx>, + canonicalized: Canonicalized<'tcx, ParamEnvAnd<'tcx, Self>>, + ) -> Fallible<CanonicalizedQueryResponse<'tcx, ()>> { + tcx.type_op_subtype(canonicalized) + } +} |