diff options
7 files changed, 356 insertions, 21 deletions
diff --git a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs index 9e8dbd0cde2..15e08166a8b 100644 --- a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs @@ -49,7 +49,7 @@ pub(super) enum CandidateSource { /// Notable examples are auto traits, `Sized`, and `DiscriminantKind`. /// For a list of all traits with builtin impls, check out the /// [`EvalCtxt::assemble_builtin_impl_candidates`] method. Not - BuiltinImpl, + BuiltinImpl(BuiltinImplSource), /// An assumption from the environment. /// /// More precisely we've used the `n-th` assumption in the `param_env`. @@ -87,6 +87,16 @@ pub(super) enum CandidateSource { AliasBound, } +/// Records additional information about what kind of built-in impl this is. +/// This should only be used by selection. +#[derive(Debug, Clone, Copy)] +pub(super) enum BuiltinImplSource { + TraitUpcasting, + Object, + Misc, + Ambiguity, +} + /// Methods used to assemble candidates for either trait or projection goals. pub(super) trait GoalKind<'tcx>: TypeFoldable<TyCtxt<'tcx>> + Copy + Eq + std::fmt::Display @@ -295,7 +305,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { // least structurally resolve the type one layer. if goal.predicate.self_ty().is_ty_var() { return vec![Candidate { - source: CandidateSource::BuiltinImpl, + source: CandidateSource::BuiltinImpl(BuiltinImplSource::Ambiguity), result: self .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS) .unwrap(), @@ -344,7 +354,10 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { let result = ecx.evaluate_added_goals_and_make_canonical_response( Certainty::Maybe(MaybeCause::Overflow), )?; - Ok(vec![Candidate { source: CandidateSource::BuiltinImpl, result }]) + Ok(vec![Candidate { + source: CandidateSource::BuiltinImpl(BuiltinImplSource::Ambiguity), + result, + }]) }, |ecx| { let normalized_ty = ecx.next_ty_infer(); @@ -447,9 +460,10 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { }; match result { - Ok(result) => { - candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result }) - } + Ok(result) => candidates.push(Candidate { + source: CandidateSource::BuiltinImpl(BuiltinImplSource::Misc), + result, + }), Err(NoSolution) => (), } @@ -457,7 +471,10 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { // `trait Foo: Bar<A> + Bar<B>` and `dyn Foo: Unsize<dyn Bar<_>>` if lang_items.unsize_trait() == Some(trait_def_id) { for result in G::consider_builtin_dyn_upcast_candidates(self, goal) { - candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result }); + candidates.push(Candidate { + source: CandidateSource::BuiltinImpl(BuiltinImplSource::TraitUpcasting), + result, + }); } } } @@ -621,9 +638,10 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { }; match result { - Ok(result) => { - candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result }) - } + Ok(result) => candidates.push(Candidate { + source: CandidateSource::BuiltinImpl(BuiltinImplSource::Misc), + result, + }), Err(NoSolution) => (), } } @@ -688,9 +706,10 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { } match G::consider_object_bound_candidate(self, goal, assumption) { - Ok(result) => { - candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result }) - } + Ok(result) => candidates.push(Candidate { + source: CandidateSource::BuiltinImpl(BuiltinImplSource::Object), + result, + }), Err(NoSolution) => (), } } @@ -711,8 +730,10 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { Err(_) => match self .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS) { - Ok(result) => candidates - .push(Candidate { source: CandidateSource::BuiltinImpl, result }), + Ok(result) => candidates.push(Candidate { + source: CandidateSource::BuiltinImpl(BuiltinImplSource::Ambiguity), + result, + }), // FIXME: This will be reachable at some point if we're in // `assemble_candidates_after_normalizing_self_ty` and we get a // universe error. We'll deal with it at this point. diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs index 6aca40b8dbd..0db2ecb517a 100644 --- a/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs +++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs @@ -28,9 +28,11 @@ use super::inspect::ProofTreeBuilder; use super::search_graph::{self, OverflowHandler}; use super::SolverMode; use super::{search_graph::SearchGraph, Goal}; +pub use select::InferCtxtSelectExt; mod canonical; mod probe; +mod select; pub struct EvalCtxt<'a, 'tcx> { /// The inference context that backs (mostly) inference and placeholder terms diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs index 851edf1fa1c..637d458882c 100644 --- a/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs +++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs @@ -20,7 +20,7 @@ use rustc_middle::traits::query::NoSolution; use rustc_middle::traits::solve::{ ExternalConstraints, ExternalConstraintsData, MaybeCause, PredefinedOpaquesData, QueryInput, }; -use rustc_middle::ty::{self, BoundVar, GenericArgKind, Ty}; +use rustc_middle::ty::{self, BoundVar, GenericArgKind, Ty, TyCtxt, TypeFoldable}; use rustc_span::DUMMY_SP; use std::iter; use std::ops::Deref; @@ -28,10 +28,10 @@ use std::ops::Deref; impl<'tcx> EvalCtxt<'_, 'tcx> { /// Canonicalizes the goal remembering the original values /// for each bound variable. - pub(super) fn canonicalize_goal( + pub(super) fn canonicalize_goal<T: TypeFoldable<TyCtxt<'tcx>>>( &self, - goal: Goal<'tcx, ty::Predicate<'tcx>>, - ) -> (Vec<ty::GenericArg<'tcx>>, CanonicalInput<'tcx>) { + goal: Goal<'tcx, T>, + ) -> (Vec<ty::GenericArg<'tcx>>, CanonicalInput<'tcx, T>) { let mut orig_values = Default::default(); let canonical_goal = Canonicalizer::canonicalize( self.infcx, diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt/select.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt/select.rs new file mode 100644 index 00000000000..7680df13802 --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/select.rs @@ -0,0 +1,303 @@ +use std::ops::ControlFlow; + +use rustc_hir::def_id::DefId; +use rustc_infer::infer::{DefineOpaqueTypes, InferCtxt, InferOk, TyCtxtInferExt}; +use rustc_infer::traits::util::supertraits; +use rustc_infer::traits::{ + Obligation, PredicateObligation, Selection, SelectionResult, TraitObligation, +}; +use rustc_middle::infer::canonical::{Canonical, CanonicalVarValues}; +use rustc_middle::traits::solve::{Certainty, Goal, PredefinedOpaquesData, QueryInput}; +use rustc_middle::traits::{ + DefiningAnchor, ImplSource, ImplSourceObjectData, ImplSourceTraitUpcastingData, + ImplSourceUserDefinedData, ObligationCause, SelectionError, +}; +use rustc_middle::ty::{self, TyCtxt}; +use rustc_span::DUMMY_SP; + +use crate::solve::assembly::{BuiltinImplSource, Candidate, CandidateSource}; +use crate::solve::eval_ctxt::{EvalCtxt, NestedGoals}; +use crate::solve::inspect::ProofTreeBuilder; +use crate::solve::search_graph::SearchGraph; +use crate::solve::SolverMode; +use crate::traits::vtable::{count_own_vtable_entries, prepare_vtable_segments, VtblSegment}; + +pub trait InferCtxtSelectExt<'tcx> { + fn select_in_new_trait_solver( + &self, + obligation: &TraitObligation<'tcx>, + ) -> SelectionResult<'tcx, Selection<'tcx>>; +} + +impl<'tcx> InferCtxtSelectExt<'tcx> for InferCtxt<'tcx> { + fn select_in_new_trait_solver( + &self, + obligation: &TraitObligation<'tcx>, + ) -> SelectionResult<'tcx, Selection<'tcx>> { + assert!(self.next_trait_solver()); + + let goal = Goal::new( + self.tcx, + obligation.param_env, + self.instantiate_binder_with_placeholders(obligation.predicate), + ); + + let mode = if self.intercrate { SolverMode::Coherence } else { SolverMode::Normal }; + let mut search_graph = SearchGraph::new(self.tcx, mode); + let mut ecx = EvalCtxt { + search_graph: &mut search_graph, + infcx: self, + // Only relevant when canonicalizing the response, + // which we don't do within this evaluation context. + predefined_opaques_in_body: self + .tcx + .mk_predefined_opaques_in_body(PredefinedOpaquesData::default()), + // Only relevant when canonicalizing the response. + max_input_universe: ty::UniverseIndex::ROOT, + var_values: CanonicalVarValues::dummy(), + nested_goals: NestedGoals::new(), + tainted: Ok(()), + inspect: ProofTreeBuilder::new_noop(), + }; + + let (orig_values, canonical_goal) = ecx.canonicalize_goal(goal); + let mut candidates = ecx.compute_canonical_trait_candidates(canonical_goal); + + // pseudo-winnow + if candidates.len() == 0 { + return Err(SelectionError::Unimplemented); + } else if candidates.len() > 1 { + let mut i = 0; + while i < candidates.len() { + let should_drop_i = (0..candidates.len()).filter(|&j| i != j).any(|j| { + candidate_should_be_dropped_in_favor_of(&candidates[i], &candidates[j]) + }); + if should_drop_i { + candidates.swap_remove(i); + } else { + i += 1; + if i > 1 { + return Ok(None); + } + } + } + } + + let candidate = candidates.pop().unwrap(); + let (certainty, nested_goals) = ecx + .instantiate_and_apply_query_response(goal.param_env, orig_values, candidate.result) + .map_err(|_| SelectionError::Unimplemented)?; + + let goal = self.resolve_vars_if_possible(goal); + + let nested_obligations: Vec<_> = nested_goals + .into_iter() + .map(|goal| { + Obligation::new(self.tcx, ObligationCause::dummy(), goal.param_env, goal.predicate) + }) + .collect(); + + if let Certainty::Maybe(_) = certainty { + return Ok(None); + } + + match (certainty, candidate.source) { + (_, CandidateSource::Impl(def_id)) => { + rematch_impl(self, goal, def_id, nested_obligations) + } + + ( + _, + CandidateSource::BuiltinImpl( + BuiltinImplSource::Object | BuiltinImplSource::TraitUpcasting, + ), + ) => rematch_object(self, goal, nested_obligations), + + (Certainty::Yes, CandidateSource::BuiltinImpl(BuiltinImplSource::Misc)) => { + // technically some builtin impls have nested obligations, but if + // `Certainty::Yes`, then they should've all been verified by the + // evaluation above. + Ok(Some(ImplSource::Builtin(nested_obligations))) + } + + (Certainty::Yes, CandidateSource::ParamEnv(_) | CandidateSource::AliasBound) => { + // It's fine not to do anything to rematch these, since there are no + // nested obligations. + Ok(Some(ImplSource::Param(nested_obligations, ty::BoundConstness::NotConst))) + } + + (_, CandidateSource::BuiltinImpl(BuiltinImplSource::Ambiguity)) + | (Certainty::Maybe(_), _) => Ok(None), + } + } +} + +impl<'tcx> EvalCtxt<'_, 'tcx> { + fn compute_canonical_trait_candidates( + &mut self, + canonical_input: Canonical<'tcx, QueryInput<'tcx, ty::TraitPredicate<'tcx>>>, + ) -> Vec<Candidate<'tcx>> { + let intercrate = match self.search_graph.solver_mode() { + SolverMode::Normal => false, + SolverMode::Coherence => true, + }; + let (canonical_infcx, input, var_values) = self + .tcx() + .infer_ctxt() + .intercrate(intercrate) + .with_next_trait_solver(true) + .with_opaque_type_inference(canonical_input.value.anchor) + .build_with_canonical(DUMMY_SP, &canonical_input); + + let mut ecx = EvalCtxt { + infcx: &canonical_infcx, + var_values, + predefined_opaques_in_body: input.predefined_opaques_in_body, + max_input_universe: canonical_input.max_universe, + search_graph: &mut self.search_graph, + nested_goals: NestedGoals::new(), + tainted: Ok(()), + inspect: ProofTreeBuilder::new_noop(), + }; + + for &(key, ty) in &input.predefined_opaques_in_body.opaque_types { + ecx.insert_hidden_type(key, input.goal.param_env, ty) + .expect("failed to prepopulate opaque types"); + } + + let candidates = ecx.assemble_and_evaluate_candidates(input.goal); + + // We don't need the canonicalized context anymore + if input.anchor != DefiningAnchor::Error { + let _ = canonical_infcx.take_opaque_types(); + } + + candidates + } +} + +fn candidate_should_be_dropped_in_favor_of<'tcx>( + victim: &Candidate<'tcx>, + other: &Candidate<'tcx>, +) -> bool { + match (victim.source, other.source) { + (CandidateSource::ParamEnv(i), CandidateSource::ParamEnv(j)) => i >= j, + (_, CandidateSource::ParamEnv(_)) => true, + _ => false, + } +} + +fn rematch_impl<'tcx>( + infcx: &InferCtxt<'tcx>, + goal: Goal<'tcx, ty::TraitPredicate<'tcx>>, + impl_def_id: DefId, + mut nested: Vec<PredicateObligation<'tcx>>, +) -> SelectionResult<'tcx, Selection<'tcx>> { + let substs = infcx.fresh_substs_for_item(DUMMY_SP, impl_def_id); + let impl_trait_ref = infcx.tcx.impl_trait_ref(impl_def_id).unwrap().subst(infcx.tcx, substs); + + nested.extend( + infcx + .at(&ObligationCause::dummy(), goal.param_env) + .eq(DefineOpaqueTypes::No, goal.predicate.trait_ref, impl_trait_ref) + .map_err(|_| SelectionError::Unimplemented)? + .into_obligations(), + ); + + nested.extend( + infcx.tcx.predicates_of(impl_def_id).instantiate(infcx.tcx, substs).into_iter().map( + |(pred, _)| Obligation::new(infcx.tcx, ObligationCause::dummy(), goal.param_env, pred), + ), + ); + + Ok(Some(ImplSource::UserDefined(ImplSourceUserDefinedData { impl_def_id, substs, nested }))) +} + +fn rematch_object<'tcx>( + infcx: &InferCtxt<'tcx>, + goal: Goal<'tcx, ty::TraitPredicate<'tcx>>, + mut nested: Vec<PredicateObligation<'tcx>>, +) -> SelectionResult<'tcx, Selection<'tcx>> { + let self_ty = goal.predicate.self_ty(); + let source_trait_ref = if let ty::Dynamic(data, _, ty::Dyn) = self_ty.kind() { + data.principal().unwrap().with_self_ty(infcx.tcx, self_ty) + } else { + bug!() + }; + + let (is_upcasting, target_trait_ref_unnormalized) = if Some(goal.predicate.def_id()) + == infcx.tcx.lang_items().unsize_trait() + { + if let ty::Dynamic(data, _, ty::Dyn) = goal.predicate.trait_ref.substs.type_at(1).kind() { + (true, data.principal().unwrap().with_self_ty(infcx.tcx, self_ty)) + } else { + bug!() + } + } else { + (false, ty::Binder::dummy(goal.predicate.trait_ref)) + }; + + let mut target_trait_ref = None; + for candidate_trait_ref in supertraits(infcx.tcx, source_trait_ref) { + let result = infcx.commit_if_ok(|_| { + infcx.at(&ObligationCause::dummy(), goal.param_env).eq( + DefineOpaqueTypes::No, + target_trait_ref_unnormalized, + candidate_trait_ref, + ) + + // FIXME: We probably should at least shallowly verify these... + }); + + match result { + Ok(InferOk { value: (), obligations }) => { + target_trait_ref = Some(candidate_trait_ref); + nested.extend(obligations); + break; + } + Err(_) => continue, + } + } + + let target_trait_ref = target_trait_ref.unwrap(); + + let mut offset = 0; + let Some((vtable_base, vtable_vptr_slot)) = + prepare_vtable_segments(infcx.tcx, source_trait_ref, |segment| { + match segment { + VtblSegment::MetadataDSA => { + offset += TyCtxt::COMMON_VTABLE_ENTRIES.len(); + } + VtblSegment::TraitOwnEntries { trait_ref, emit_vptr } => { + let own_vtable_entries = count_own_vtable_entries(infcx.tcx, trait_ref); + + if trait_ref == target_trait_ref { + if emit_vptr { + return ControlFlow::Break(( + offset, + Some(offset + count_own_vtable_entries(infcx.tcx, trait_ref)), + )); + } else { + return ControlFlow::Break((offset, None)); + } + } + + offset += own_vtable_entries; + if emit_vptr { + offset += 1; + } + } + } + ControlFlow::Continue(()) + }) + else { + bug!(); + }; + + // If we're upcasting, get the offset of the vtable pointer, which is + Ok(Some(if is_upcasting { + ImplSource::TraitUpcasting(ImplSourceTraitUpcastingData { vtable_vptr_slot, nested }) + } else { + ImplSource::Object(ImplSourceObjectData { vtable_base, nested }) + })) +} diff --git a/compiler/rustc_trait_selection/src/solve/mod.rs b/compiler/rustc_trait_selection/src/solve/mod.rs index 769d002fcc0..f3f78cdf09d 100644 --- a/compiler/rustc_trait_selection/src/solve/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/mod.rs @@ -33,7 +33,7 @@ mod search_graph; mod trait_goals; mod weak_types; -pub use eval_ctxt::{EvalCtxt, InferCtxtEvalExt}; +pub use eval_ctxt::{EvalCtxt, InferCtxtEvalExt, InferCtxtSelectExt}; pub use fulfill::FulfillmentCtxt; pub(crate) use normalize::deeply_normalize; diff --git a/compiler/rustc_trait_selection/src/traits/select/mod.rs b/compiler/rustc_trait_selection/src/traits/select/mod.rs index 7cf8479b803..c12d92b9012 100644 --- a/compiler/rustc_trait_selection/src/traits/select/mod.rs +++ b/compiler/rustc_trait_selection/src/traits/select/mod.rs @@ -20,6 +20,7 @@ use super::{ }; use crate::infer::{InferCtxt, InferOk, TypeFreshener}; +use crate::solve::InferCtxtSelectExt; use crate::traits::error_reporting::TypeErrCtxtExt; use crate::traits::project::try_normalize_with_depth_to; use crate::traits::project::ProjectAndUnifyResult; @@ -264,6 +265,10 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { &mut self, obligation: &TraitObligation<'tcx>, ) -> SelectionResult<'tcx, Selection<'tcx>> { + if self.infcx.next_trait_solver() { + return self.infcx.select_in_new_trait_solver(obligation); + } + let candidate = match self.select_from_obligation(obligation) { Err(SelectionError::Overflow(OverflowError::Canonical)) => { // In standard mode, overflow must have been caught and reported @@ -290,7 +295,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { } } - pub(crate) fn select_from_obligation( + fn select_from_obligation( &mut self, obligation: &TraitObligation<'tcx>, ) -> SelectionResult<'tcx, SelectionCandidate<'tcx>> { diff --git a/tests/ui/for/issue-20605.next.stderr b/tests/ui/for/issue-20605.next.stderr index d55efedfcbe..de60555ae3c 100644 --- a/tests/ui/for/issue-20605.next.stderr +++ b/tests/ui/for/issue-20605.next.stderr @@ -13,6 +13,10 @@ LL | for item in *things { *item = 0 } = help: the trait `Sized` is not implemented for `<dyn Iterator<Item = &'a mut u8> as IntoIterator>::IntoIter` = note: all local variables must have a statically known size = help: unsized locals are gated as an unstable feature +help: consider further restricting the associated type + | +LL | fn changer<'a>(mut things: Box<dyn Iterator<Item=&'a mut u8>>) where <dyn Iterator<Item = &'a mut u8> as IntoIterator>::IntoIter: Sized { + | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ error: the type `<dyn Iterator<Item = &'a mut u8> as IntoIterator>::IntoIter` is not well-formed --> $DIR/issue-20605.rs:5:17 |