diff options
| -rw-r--r-- | compiler/rustc_middle/src/ty/sty.rs | 90 | ||||
| -rw-r--r-- | compiler/rustc_trait_selection/src/solve/assembly.rs | 11 | ||||
| -rw-r--r-- | compiler/rustc_trait_selection/src/solve/cache.rs | 54 | ||||
| -rw-r--r-- | compiler/rustc_trait_selection/src/solve/fulfill.rs | 2 | ||||
| -rw-r--r-- | compiler/rustc_trait_selection/src/solve/mod.rs | 57 | ||||
| -rw-r--r-- | compiler/rustc_trait_selection/src/solve/overflow.rs | 13 |
6 files changed, 186 insertions, 41 deletions
diff --git a/compiler/rustc_middle/src/ty/sty.rs b/compiler/rustc_middle/src/ty/sty.rs index bd5b04d5b2b..e49e7e86da0 100644 --- a/compiler/rustc_middle/src/ty/sty.rs +++ b/compiler/rustc_middle/src/ty/sty.rs @@ -7,8 +7,8 @@ use crate::ty::subst::{GenericArg, InternalSubsts, SubstsRef}; use crate::ty::visit::ValidateBoundVars; use crate::ty::InferTy::*; use crate::ty::{ - self, AdtDef, DefIdTree, Discr, Term, Ty, TyCtxt, TypeFlags, TypeSuperVisitable, TypeVisitable, - TypeVisitor, + self, AdtDef, DefIdTree, Discr, FallibleTypeFolder, Term, Ty, TyCtxt, TypeFlags, TypeFoldable, + TypeSuperFoldable, TypeSuperVisitable, TypeVisitable, TypeVisitor, }; use crate::ty::{List, ParamEnv}; use hir::def::DefKind; @@ -1106,6 +1106,17 @@ impl<'tcx, T> Binder<'tcx, T> { if self.0.has_escaping_bound_vars() { None } else { Some(self.skip_binder()) } } + pub fn no_bound_vars_ignoring_escaping(self, tcx: TyCtxt<'tcx>) -> Option<T> + where + T: TypeFoldable<'tcx>, + { + if !self.0.has_escaping_bound_vars() { + Some(self.skip_binder()) + } else { + self.0.try_fold_with(&mut SkipBindersAt { index: ty::INNERMOST, tcx }).ok() + } + } + /// Splits the contents into two things that share the same binder /// level as the original, returning two distinct binders. /// @@ -1135,6 +1146,81 @@ impl<'tcx, T: IntoIterator> Binder<'tcx, T> { } } +struct SkipBindersAt<'tcx> { + tcx: TyCtxt<'tcx>, + index: ty::DebruijnIndex, +} + +impl<'tcx> FallibleTypeFolder<'tcx> for SkipBindersAt<'tcx> { + type Error = (); + + fn tcx(&self) -> TyCtxt<'tcx> { + self.tcx + } + + fn try_fold_binder<T>(&mut self, t: Binder<'tcx, T>) -> Result<Binder<'tcx, T>, Self::Error> + where + T: ty::TypeFoldable<'tcx>, + { + self.index.shift_in(1); + let value = t.try_map_bound(|t| t.try_fold_with(self)); + self.index.shift_out(1); + value + } + + fn try_fold_ty(&mut self, ty: Ty<'tcx>) -> Result<Ty<'tcx>, Self::Error> { + if !ty.has_escaping_bound_vars() { + Ok(ty) + } else if let ty::Bound(index, bv) = *ty.kind() { + if index == self.index { + Err(()) + } else { + Ok(self.tcx().mk_ty(ty::Bound(index.shifted_out(1), bv))) + } + } else { + ty.try_super_fold_with(self) + } + } + + fn try_fold_region(&mut self, r: ty::Region<'tcx>) -> Result<ty::Region<'tcx>, Self::Error> { + if !r.has_escaping_bound_vars() { + Ok(r) + } else if let ty::ReLateBound(index, bv) = r.kind() { + if index == self.index { + Err(()) + } else { + Ok(self.tcx().mk_region(ty::ReLateBound(index.shifted_out(1), bv))) + } + } else { + r.try_super_fold_with(self) + } + } + + fn try_fold_const(&mut self, ct: ty::Const<'tcx>) -> Result<ty::Const<'tcx>, Self::Error> { + if !ct.has_escaping_bound_vars() { + Ok(ct) + } else if let ty::ConstKind::Bound(index, bv) = ct.kind() { + if index == self.index { + Err(()) + } else { + Ok(self.tcx().mk_const( + ty::ConstKind::Bound(index.shifted_out(1), bv), + ct.ty().try_fold_with(self)?, + )) + } + } else { + ct.try_super_fold_with(self) + } + } + + fn try_fold_predicate( + &mut self, + p: ty::Predicate<'tcx>, + ) -> Result<ty::Predicate<'tcx>, Self::Error> { + if !p.has_escaping_bound_vars() { Ok(p) } else { p.try_super_fold_with(self) } + } +} + /// Represents the projection of an associated type. /// /// For a projection, this would be `<Ty as Trait<...>>::N`. diff --git a/compiler/rustc_trait_selection/src/solve/assembly.rs b/compiler/rustc_trait_selection/src/solve/assembly.rs index e9ddad11ff2..ba68da0686f 100644 --- a/compiler/rustc_trait_selection/src/solve/assembly.rs +++ b/compiler/rustc_trait_selection/src/solve/assembly.rs @@ -2,8 +2,8 @@ use super::infcx_ext::InferCtxtExt; use super::{ - fixme_instantiate_canonical_query_response, CanonicalGoal, CanonicalResponse, Certainty, - EvalCtxt, Goal, + instantiate_canonical_query_response, CanonicalGoal, CanonicalResponse, Certainty, EvalCtxt, + Goal, }; use rustc_hir::def_id::DefId; use rustc_infer::infer::TyCtxtInferExt; @@ -121,11 +121,8 @@ impl<'a, 'tcx, G: GoalKind<'tcx>> AssemblyCtxt<'a, 'tcx, G> { // canonical wrt the caller. for Candidate { source, result } in normalized_candidates { self.infcx.probe(|_| { - let candidate_certainty = fixme_instantiate_canonical_query_response( - &self.infcx, - &orig_values, - result, - ); + let candidate_certainty = + instantiate_canonical_query_response(&self.infcx, &orig_values, result); // FIXME: This is a bit scary if the `normalizes_to_goal` overflows. // diff --git a/compiler/rustc_trait_selection/src/solve/cache.rs b/compiler/rustc_trait_selection/src/solve/cache.rs index 993b7989066..f1ee73a5b85 100644 --- a/compiler/rustc_trait_selection/src/solve/cache.rs +++ b/compiler/rustc_trait_selection/src/solve/cache.rs @@ -9,11 +9,12 @@ //! FIXME(@lcnr): Write that section, feel free to ping me if you need help here //! before then or if I still haven't done that before January 2023. use super::overflow::OverflowData; -use super::CanonicalGoal; +use super::{CanonicalGoal, Certainty, MaybeCause, Response}; use super::{EvalCtxt, QueryResult}; use rustc_data_structures::fx::FxHashMap; -use rustc_middle::ty::TyCtxt; +use rustc_infer::infer::canonical::{Canonical, CanonicalVarKind, CanonicalVarValues}; +use rustc_middle::ty::{self, TyCtxt}; use std::{cmp::Ordering, collections::hash_map::Entry}; #[derive(Debug, Clone)] @@ -111,11 +112,11 @@ impl<'tcx> EvalCtxt<'tcx> { // No entry, simply push this goal on the stack after dealing with overflow. Entry::Vacant(v) => { if self.overflow_data.has_overflow(cache.stack.len()) { - return Err(self.deal_with_overflow()); + return Err(self.deal_with_overflow(goal)); } v.insert(ProvisionalEntry { - response: fixme_response_yes_no_constraints(), + response: response_no_constraints(self.tcx, goal, Certainty::Yes), depth: cache.stack.len(), }); cache.stack.push(StackElem { goal, has_been_used: false }); @@ -150,7 +151,11 @@ impl<'tcx> EvalCtxt<'tcx> { { Err(entry.response) } else { - Err(fixme_response_maybe_no_constraints()) + Err(response_no_constraints( + self.tcx, + goal, + Certainty::Maybe(MaybeCause::Ambiguity), + )) } } } @@ -248,10 +253,39 @@ impl<'tcx> EvalCtxt<'tcx> { } } -fn fixme_response_yes_no_constraints<'tcx>() -> QueryResult<'tcx> { - unimplemented!() -} +pub(super) fn response_no_constraints<'tcx>( + tcx: TyCtxt<'tcx>, + goal: Canonical<'tcx, impl Sized>, + certainty: Certainty, +) -> QueryResult<'tcx> { + let var_values = goal + .variables + .iter() + .enumerate() + .map(|(i, info)| match info.kind { + CanonicalVarKind::Ty(_) | CanonicalVarKind::PlaceholderTy(_) => { + tcx.mk_ty(ty::Bound(ty::INNERMOST, ty::BoundVar::from_usize(i).into())).into() + } + CanonicalVarKind::Region(_) | CanonicalVarKind::PlaceholderRegion(_) => { + let br = ty::BoundRegion { + var: ty::BoundVar::from_usize(i), + kind: ty::BrAnon(i as u32, None), + }; + tcx.mk_region(ty::ReLateBound(ty::INNERMOST, br)).into() + } + CanonicalVarKind::Const(_, ty) | CanonicalVarKind::PlaceholderConst(_, ty) => tcx + .mk_const(ty::ConstKind::Bound(ty::INNERMOST, ty::BoundVar::from_usize(i)), ty) + .into(), + }) + .collect(); -fn fixme_response_maybe_no_constraints<'tcx>() -> QueryResult<'tcx> { - unimplemented!() + Ok(Canonical { + max_universe: goal.max_universe, + variables: goal.variables, + value: Response { + var_values: CanonicalVarValues { var_values }, + external_constraints: Default::default(), + certainty, + }, + }) } diff --git a/compiler/rustc_trait_selection/src/solve/fulfill.rs b/compiler/rustc_trait_selection/src/solve/fulfill.rs index c014d682a9a..dfc2b5ed329 100644 --- a/compiler/rustc_trait_selection/src/solve/fulfill.rs +++ b/compiler/rustc_trait_selection/src/solve/fulfill.rs @@ -62,7 +62,7 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> { let mut errors = Vec::new(); for i in 0.. { if !infcx.tcx.recursion_limit().value_within_limit(i) { - unimplemented!("overflow") + unimplemented!("overflowed on pending obligations: {:?}", self.obligations); } let mut has_changed = false; diff --git a/compiler/rustc_trait_selection/src/solve/mod.rs b/compiler/rustc_trait_selection/src/solve/mod.rs index 7f5e3208f4e..042ba96b379 100644 --- a/compiler/rustc_trait_selection/src/solve/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/mod.rs @@ -19,15 +19,19 @@ use std::mem; -use rustc_infer::infer::canonical::OriginalQueryValues; -use rustc_infer::infer::{InferCtxt, TyCtxtInferExt}; +use rustc_infer::infer::canonical::{OriginalQueryValues, QueryRegionConstraints, QueryResponse}; +use rustc_infer::infer::{InferCtxt, InferOk, TyCtxtInferExt}; use rustc_infer::traits::query::NoSolution; use rustc_infer::traits::Obligation; +use rustc_middle::infer::canonical::Certainty as OldCertainty; use rustc_middle::infer::canonical::{Canonical, CanonicalVarValues}; use rustc_middle::ty::{self, Ty, TyCtxt}; use rustc_middle::ty::{RegionOutlivesPredicate, ToPredicate, TypeOutlivesPredicate}; use rustc_span::DUMMY_SP; +use crate::traits::ObligationCause; + +use self::cache::response_no_constraints; use self::infcx_ext::InferCtxtExt; mod assembly; @@ -119,7 +123,7 @@ pub enum MaybeCause { } /// Additional constraints returned on success. -#[derive(Debug, PartialEq, Eq, Clone, Hash, TypeFoldable, TypeVisitable)] +#[derive(Debug, PartialEq, Eq, Clone, Hash, TypeFoldable, TypeVisitable, Default)] pub struct ExternalConstraints<'tcx> { // FIXME: implement this. regions: (), @@ -175,7 +179,7 @@ impl<'tcx> EvalCtxt<'tcx> { let canonical_response = self.evaluate_canonical_goal(canonical_goal)?; Ok(( true, // FIXME: check whether `var_values` are an identity substitution. - fixme_instantiate_canonical_query_response(infcx, &orig_values, canonical_response), + instantiate_canonical_query_response(infcx, &orig_values, canonical_response), )) } @@ -208,7 +212,8 @@ impl<'tcx> EvalCtxt<'tcx> { // of `PredicateKind` this is the case and it is and faster than instantiating and // recanonicalizing. let Goal { param_env, predicate } = canonical_goal.value; - if let Some(kind) = predicate.kind().no_bound_vars() { + + if let Some(kind) = predicate.kind().no_bound_vars_ignoring_escaping(self.tcx) { match kind { ty::PredicateKind::Clause(ty::Clause::Trait(predicate)) => self.compute_trait_goal( canonical_goal.unchecked_rebind(Goal { param_env, predicate }), @@ -234,7 +239,10 @@ impl<'tcx> EvalCtxt<'tcx> { | ty::PredicateKind::ConstEvaluatable(_) | ty::PredicateKind::ConstEquate(_, _) | ty::PredicateKind::TypeWellFormedFromEnv(_) - | ty::PredicateKind::Ambiguous => unimplemented!(), + | ty::PredicateKind::Ambiguous => { + // FIXME + response_no_constraints(self.tcx, canonical_goal, Certainty::Yes) + } } } else { let (infcx, goal, var_values) = @@ -248,16 +256,18 @@ impl<'tcx> EvalCtxt<'tcx> { fn compute_type_outlives_goal( &mut self, - _goal: CanonicalGoal<'tcx, TypeOutlivesPredicate<'tcx>>, + goal: CanonicalGoal<'tcx, TypeOutlivesPredicate<'tcx>>, ) -> QueryResult<'tcx> { - todo!() + // FIXME + response_no_constraints(self.tcx, goal, Certainty::Yes) } fn compute_region_outlives_goal( &mut self, - _goal: CanonicalGoal<'tcx, RegionOutlivesPredicate<'tcx>>, + goal: CanonicalGoal<'tcx, RegionOutlivesPredicate<'tcx>>, ) -> QueryResult<'tcx> { - todo!() + // FIXME + response_no_constraints(self.tcx, goal, Certainty::Yes) } } @@ -300,10 +310,27 @@ impl<'tcx> EvalCtxt<'tcx> { } } -fn fixme_instantiate_canonical_query_response<'tcx>( - _: &InferCtxt<'tcx>, - _: &OriginalQueryValues<'tcx>, - _: CanonicalResponse<'tcx>, +fn instantiate_canonical_query_response<'tcx>( + infcx: &InferCtxt<'tcx>, + original_values: &OriginalQueryValues<'tcx>, + response: CanonicalResponse<'tcx>, ) -> Certainty { - unimplemented!() + let Ok(InferOk { value, obligations }) = infcx + .instantiate_query_response_and_region_obligations( + &ObligationCause::dummy(), + ty::ParamEnv::empty(), + original_values, + &response.unchecked_map(|resp| QueryResponse { + var_values: resp.var_values, + region_constraints: QueryRegionConstraints::default(), + certainty: match resp.certainty { + Certainty::Yes => OldCertainty::Proven, + Certainty::Maybe(_) => OldCertainty::Ambiguous, + }, + opaque_types: resp.external_constraints.opaque_types, + value: resp.certainty, + }), + ) else { bug!(); }; + assert!(obligations.is_empty()); + value } diff --git a/compiler/rustc_trait_selection/src/solve/overflow.rs b/compiler/rustc_trait_selection/src/solve/overflow.rs index fdd6adb681b..8bbb9f63e78 100644 --- a/compiler/rustc_trait_selection/src/solve/overflow.rs +++ b/compiler/rustc_trait_selection/src/solve/overflow.rs @@ -1,7 +1,9 @@ +use rustc_infer::infer::canonical::Canonical; use rustc_infer::traits::query::NoSolution; use rustc_middle::ty::TyCtxt; use rustc_session::Limit; +use super::cache::response_no_constraints; use super::{Certainty, EvalCtxt, MaybeCause, QueryResult}; /// When detecting a solver overflow, we return ambiguity. Overflow can be @@ -49,9 +51,12 @@ impl OverflowData { } impl<'tcx> EvalCtxt<'tcx> { - pub(super) fn deal_with_overflow(&mut self) -> QueryResult<'tcx> { + pub(super) fn deal_with_overflow( + &mut self, + goal: Canonical<'tcx, impl Sized>, + ) -> QueryResult<'tcx> { self.overflow_data.deal_with_overflow(); - fixme_response_overflow_no_constraints() + response_no_constraints(self.tcx, goal, Certainty::Maybe(MaybeCause::Overflow)) } /// A `while`-loop which tracks overflow. @@ -74,7 +79,3 @@ impl<'tcx> EvalCtxt<'tcx> { Ok(Certainty::Maybe(MaybeCause::Overflow)) } } - -fn fixme_response_overflow_no_constraints<'tcx>() -> QueryResult<'tcx> { - unimplemented!() -} |