From 698f8c2f01ea549d77d7dc3338a12e04c11057b9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:02:58 +0200 Subject: Adding upstream version 1.64.0+dfsg1. Signed-off-by: Daniel Baumann --- .../rustc_traits/src/implied_outlives_bounds.rs | 172 +++++++++++++++++++++ 1 file changed, 172 insertions(+) create mode 100644 compiler/rustc_traits/src/implied_outlives_bounds.rs (limited to 'compiler/rustc_traits/src/implied_outlives_bounds.rs') diff --git a/compiler/rustc_traits/src/implied_outlives_bounds.rs b/compiler/rustc_traits/src/implied_outlives_bounds.rs new file mode 100644 index 000000000..e3e78f70b --- /dev/null +++ b/compiler/rustc_traits/src/implied_outlives_bounds.rs @@ -0,0 +1,172 @@ +//! Provider for the `implied_outlives_bounds` query. +//! Do not call this query directory. See +//! [`rustc_trait_selection::traits::query::type_op::implied_outlives_bounds`]. + +use rustc_hir as hir; +use rustc_infer::infer::canonical::{self, Canonical}; +use rustc_infer::infer::outlives::components::{push_outlives_components, Component}; +use rustc_infer::infer::{InferCtxt, TyCtxtInferExt}; +use rustc_infer::traits::query::OutlivesBound; +use rustc_infer::traits::TraitEngineExt as _; +use rustc_middle::ty::query::Providers; +use rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitable}; +use rustc_span::source_map::DUMMY_SP; +use rustc_trait_selection::infer::InferCtxtBuilderExt; +use rustc_trait_selection::traits::query::{CanonicalTyGoal, Fallible, NoSolution}; +use rustc_trait_selection::traits::wf; +use rustc_trait_selection::traits::{TraitEngine, TraitEngineExt}; +use smallvec::{smallvec, SmallVec}; + +pub(crate) fn provide(p: &mut Providers) { + *p = Providers { implied_outlives_bounds, ..*p }; +} + +fn implied_outlives_bounds<'tcx>( + tcx: TyCtxt<'tcx>, + goal: CanonicalTyGoal<'tcx>, +) -> Result< + &'tcx Canonical<'tcx, canonical::QueryResponse<'tcx, Vec>>>, + NoSolution, +> { + tcx.infer_ctxt().enter_canonical_trait_query(&goal, |infcx, _fulfill_cx, key| { + let (param_env, ty) = key.into_parts(); + compute_implied_outlives_bounds(&infcx, param_env, ty) + }) +} + +fn compute_implied_outlives_bounds<'tcx>( + infcx: &InferCtxt<'_, 'tcx>, + param_env: ty::ParamEnv<'tcx>, + ty: Ty<'tcx>, +) -> Fallible>> { + let tcx = infcx.tcx; + + // Sometimes when we ask what it takes for T: WF, we get back that + // U: WF is required; in that case, we push U onto this stack and + // process it next. Because the resulting predicates aren't always + // guaranteed to be a subset of the original type, so we need to store the + // WF args we've computed in a set. + let mut checked_wf_args = rustc_data_structures::fx::FxHashSet::default(); + let mut wf_args = vec![ty.into()]; + + let mut implied_bounds = vec![]; + + let mut fulfill_cx = >::new(tcx); + + while let Some(arg) = wf_args.pop() { + if !checked_wf_args.insert(arg) { + continue; + } + + // Compute the obligations for `arg` to be well-formed. If `arg` is + // an unresolved inference variable, just substituted an empty set + // -- because the return type here is going to be things we *add* + // to the environment, it's always ok for this set to be smaller + // than the ultimate set. (Note: normally there won't be + // unresolved inference variables here anyway, but there might be + // during typeck under some circumstances.) + let obligations = wf::obligations(infcx, param_env, hir::CRATE_HIR_ID, 0, arg, DUMMY_SP) + .unwrap_or_default(); + + // N.B., all of these predicates *ought* to be easily proven + // true. In fact, their correctness is (mostly) implied by + // other parts of the program. However, in #42552, we had + // an annoying scenario where: + // + // - Some `T::Foo` gets normalized, resulting in a + // variable `_1` and a `T: Trait` constraint + // (not sure why it couldn't immediately get + // solved). This result of `_1` got cached. + // - These obligations were dropped on the floor here, + // rather than being registered. + // - Then later we would get a request to normalize + // `T::Foo` which would result in `_1` being used from + // the cache, but hence without the `T: Trait` + // constraint. As a result, `_1` never gets resolved, + // and we get an ICE (in dropck). + // + // Therefore, we register any predicates involving + // inference variables. We restrict ourselves to those + // involving inference variables both for efficiency and + // to avoids duplicate errors that otherwise show up. + fulfill_cx.register_predicate_obligations( + infcx, + obligations.iter().filter(|o| o.predicate.has_infer_types_or_consts()).cloned(), + ); + + // From the full set of obligations, just filter down to the + // region relationships. + implied_bounds.extend(obligations.into_iter().flat_map(|obligation| { + assert!(!obligation.has_escaping_bound_vars()); + match obligation.predicate.kind().no_bound_vars() { + None => vec![], + Some(pred) => match pred { + ty::PredicateKind::Trait(..) + | ty::PredicateKind::Subtype(..) + | ty::PredicateKind::Coerce(..) + | ty::PredicateKind::Projection(..) + | ty::PredicateKind::ClosureKind(..) + | ty::PredicateKind::ObjectSafe(..) + | ty::PredicateKind::ConstEvaluatable(..) + | ty::PredicateKind::ConstEquate(..) + | ty::PredicateKind::TypeWellFormedFromEnv(..) => vec![], + ty::PredicateKind::WellFormed(arg) => { + wf_args.push(arg); + vec![] + } + + ty::PredicateKind::RegionOutlives(ty::OutlivesPredicate(r_a, r_b)) => { + vec![OutlivesBound::RegionSubRegion(r_b, r_a)] + } + + ty::PredicateKind::TypeOutlives(ty::OutlivesPredicate(ty_a, r_b)) => { + let ty_a = infcx.resolve_vars_if_possible(ty_a); + let mut components = smallvec![]; + push_outlives_components(tcx, ty_a, &mut components); + implied_bounds_from_components(r_b, components) + } + }, + } + })); + } + + // Ensure that those obligations that we had to solve + // get solved *here*. + match fulfill_cx.select_all_or_error(infcx).as_slice() { + [] => Ok(implied_bounds), + _ => Err(NoSolution), + } +} + +/// When we have an implied bound that `T: 'a`, we can further break +/// this down to determine what relationships would have to hold for +/// `T: 'a` to hold. We get to assume that the caller has validated +/// those relationships. +fn implied_bounds_from_components<'tcx>( + sub_region: ty::Region<'tcx>, + sup_components: SmallVec<[Component<'tcx>; 4]>, +) -> Vec> { + sup_components + .into_iter() + .filter_map(|component| { + match component { + Component::Region(r) => Some(OutlivesBound::RegionSubRegion(sub_region, r)), + Component::Param(p) => Some(OutlivesBound::RegionSubParam(sub_region, p)), + Component::Projection(p) => Some(OutlivesBound::RegionSubProjection(sub_region, p)), + Component::EscapingProjection(_) => + // If the projection has escaping regions, don't + // try to infer any implied bounds even for its + // free components. This is conservative, because + // the caller will still have to prove that those + // free components outlive `sub_region`. But the + // idea is that the WAY that the caller proves + // that may change in the future and we want to + // give ourselves room to get smarter here. + { + None + } + Component::UnresolvedInferenceVariable(..) => None, + } + }) + .collect() +} -- cgit v1.2.3