diff options
Diffstat (limited to 'compiler/rustc_infer/src/traits')
| -rw-r--r-- | compiler/rustc_infer/src/traits/engine.rs | 76 | ||||
| -rw-r--r-- | compiler/rustc_infer/src/traits/error_reporting/mod.rs | 108 | ||||
| -rw-r--r-- | compiler/rustc_infer/src/traits/mod.rs | 170 | ||||
| -rw-r--r-- | compiler/rustc_infer/src/traits/project.rs | 255 | ||||
| -rw-r--r-- | compiler/rustc_infer/src/traits/structural_impls.rs | 79 | ||||
| -rw-r--r-- | compiler/rustc_infer/src/traits/util.rs | 390 |
6 files changed, 1078 insertions, 0 deletions
diff --git a/compiler/rustc_infer/src/traits/engine.rs b/compiler/rustc_infer/src/traits/engine.rs new file mode 100644 index 000000000..736278ba0 --- /dev/null +++ b/compiler/rustc_infer/src/traits/engine.rs @@ -0,0 +1,76 @@ +use crate::infer::InferCtxt; +use crate::traits::Obligation; +use rustc_data_structures::fx::FxHashMap; +use rustc_hir::def_id::DefId; +use rustc_middle::ty::{self, ToPredicate, Ty}; + +use super::FulfillmentError; +use super::{ObligationCause, PredicateObligation}; + +pub trait TraitEngine<'tcx>: 'tcx { + fn normalize_projection_type( + &mut self, + infcx: &InferCtxt<'_, 'tcx>, + param_env: ty::ParamEnv<'tcx>, + projection_ty: ty::ProjectionTy<'tcx>, + cause: ObligationCause<'tcx>, + ) -> Ty<'tcx>; + + /// Requires that `ty` must implement the trait with `def_id` in + /// the given environment. This trait must not have any type + /// parameters (except for `Self`). + fn register_bound( + &mut self, + infcx: &InferCtxt<'_, 'tcx>, + param_env: ty::ParamEnv<'tcx>, + ty: Ty<'tcx>, + def_id: DefId, + cause: ObligationCause<'tcx>, + ) { + let trait_ref = ty::TraitRef { def_id, substs: infcx.tcx.mk_substs_trait(ty, &[]) }; + self.register_predicate_obligation( + infcx, + Obligation { + cause, + recursion_depth: 0, + param_env, + predicate: ty::Binder::dummy(trait_ref).without_const().to_predicate(infcx.tcx), + }, + ); + } + + fn register_predicate_obligation( + &mut self, + infcx: &InferCtxt<'_, 'tcx>, + obligation: PredicateObligation<'tcx>, + ); + + fn select_all_or_error(&mut self, infcx: &InferCtxt<'_, 'tcx>) -> Vec<FulfillmentError<'tcx>>; + + fn select_where_possible(&mut self, infcx: &InferCtxt<'_, 'tcx>) + -> Vec<FulfillmentError<'tcx>>; + + fn pending_obligations(&self) -> Vec<PredicateObligation<'tcx>>; + + fn relationships(&mut self) -> &mut FxHashMap<ty::TyVid, ty::FoundRelationships>; +} + +pub trait TraitEngineExt<'tcx> { + fn register_predicate_obligations( + &mut self, + infcx: &InferCtxt<'_, 'tcx>, + obligations: impl IntoIterator<Item = PredicateObligation<'tcx>>, + ); +} + +impl<'tcx, T: ?Sized + TraitEngine<'tcx>> TraitEngineExt<'tcx> for T { + fn register_predicate_obligations( + &mut self, + infcx: &InferCtxt<'_, 'tcx>, + obligations: impl IntoIterator<Item = PredicateObligation<'tcx>>, + ) { + for obligation in obligations { + self.register_predicate_obligation(infcx, obligation); + } + } +} diff --git a/compiler/rustc_infer/src/traits/error_reporting/mod.rs b/compiler/rustc_infer/src/traits/error_reporting/mod.rs new file mode 100644 index 000000000..95b6c4ce1 --- /dev/null +++ b/compiler/rustc_infer/src/traits/error_reporting/mod.rs @@ -0,0 +1,108 @@ +use super::ObjectSafetyViolation; + +use crate::infer::InferCtxt; +use rustc_data_structures::fx::FxHashSet; +use rustc_errors::{struct_span_err, DiagnosticBuilder, ErrorGuaranteed, MultiSpan}; +use rustc_hir as hir; +use rustc_hir::def_id::{DefId, LocalDefId}; +use rustc_middle::ty::TyCtxt; +use rustc_span::Span; +use std::fmt; +use std::iter; + +impl<'a, 'tcx> InferCtxt<'a, 'tcx> { + pub fn report_extra_impl_obligation( + &self, + error_span: Span, + impl_item_def_id: LocalDefId, + trait_item_def_id: DefId, + requirement: &dyn fmt::Display, + ) -> DiagnosticBuilder<'tcx, ErrorGuaranteed> { + let mut err = struct_span_err!( + self.tcx.sess, + error_span, + E0276, + "impl has stricter requirements than trait" + ); + + if let Some(span) = self.tcx.hir().span_if_local(trait_item_def_id) { + let item_name = self.tcx.item_name(impl_item_def_id.to_def_id()); + err.span_label(span, format!("definition of `{}` from trait", item_name)); + } + + err.span_label(error_span, format!("impl has extra requirement {}", requirement)); + + err + } +} + +pub fn report_object_safety_error<'tcx>( + tcx: TyCtxt<'tcx>, + span: Span, + trait_def_id: DefId, + violations: &[ObjectSafetyViolation], +) -> DiagnosticBuilder<'tcx, ErrorGuaranteed> { + let trait_str = tcx.def_path_str(trait_def_id); + let trait_span = tcx.hir().get_if_local(trait_def_id).and_then(|node| match node { + hir::Node::Item(item) => Some(item.ident.span), + _ => None, + }); + let mut err = struct_span_err!( + tcx.sess, + span, + E0038, + "the trait `{}` cannot be made into an object", + trait_str + ); + err.span_label(span, format!("`{}` cannot be made into an object", trait_str)); + + let mut reported_violations = FxHashSet::default(); + let mut multi_span = vec![]; + let mut messages = vec![]; + for violation in violations { + if let ObjectSafetyViolation::SizedSelf(sp) = &violation && !sp.is_empty() { + // Do not report `SizedSelf` without spans pointing at `SizedSelf` obligations + // with a `Span`. + reported_violations.insert(ObjectSafetyViolation::SizedSelf(vec![].into())); + } + if reported_violations.insert(violation.clone()) { + let spans = violation.spans(); + let msg = if trait_span.is_none() || spans.is_empty() { + format!("the trait cannot be made into an object because {}", violation.error_msg()) + } else { + format!("...because {}", violation.error_msg()) + }; + if spans.is_empty() { + err.note(&msg); + } else { + for span in spans { + multi_span.push(span); + messages.push(msg.clone()); + } + } + } + } + let has_multi_span = !multi_span.is_empty(); + let mut note_span = MultiSpan::from_spans(multi_span.clone()); + if let (Some(trait_span), true) = (trait_span, has_multi_span) { + note_span.push_span_label(trait_span, "this trait cannot be made into an object..."); + } + for (span, msg) in iter::zip(multi_span, messages) { + note_span.push_span_label(span, msg); + } + err.span_note( + note_span, + "for a trait to be \"object safe\" it needs to allow building a vtable to allow the call \ + to be resolvable dynamically; for more information visit \ + <https://doc.rust-lang.org/reference/items/traits.html#object-safety>", + ); + if trait_span.is_some() { + let mut reported_violations: Vec<_> = reported_violations.into_iter().collect(); + reported_violations.sort(); + for violation in reported_violations { + // Only provide the help if its a local trait, otherwise it's not actionable. + violation.solution(&mut err); + } + } + err +} diff --git a/compiler/rustc_infer/src/traits/mod.rs b/compiler/rustc_infer/src/traits/mod.rs new file mode 100644 index 000000000..4df4de21a --- /dev/null +++ b/compiler/rustc_infer/src/traits/mod.rs @@ -0,0 +1,170 @@ +//! Trait Resolution. See the [rustc-dev-guide] for more information on how this works. +//! +//! [rustc-dev-guide]: https://rustc-dev-guide.rust-lang.org/traits/resolution.html + +mod engine; +pub mod error_reporting; +mod project; +mod structural_impls; +pub mod util; + +use rustc_hir as hir; +use rustc_middle::ty::error::{ExpectedFound, TypeError}; +use rustc_middle::ty::{self, Const, Ty, TyCtxt}; +use rustc_span::Span; + +pub use self::FulfillmentErrorCode::*; +pub use self::ImplSource::*; +pub use self::ObligationCauseCode::*; +pub use self::SelectionError::*; + +pub use self::engine::{TraitEngine, TraitEngineExt}; +pub use self::project::MismatchedProjectionTypes; +pub(crate) use self::project::UndoLog; +pub use self::project::{ + Normalized, NormalizedTy, ProjectionCache, ProjectionCacheEntry, ProjectionCacheKey, + ProjectionCacheStorage, Reveal, +}; +pub use rustc_middle::traits::*; + +/// An `Obligation` represents some trait reference (e.g., `i32: Eq`) for +/// which the "impl_source" must be found. The process of finding an "impl_source" is +/// called "resolving" the `Obligation`. This process consists of +/// either identifying an `impl` (e.g., `impl Eq for i32`) that +/// satisfies the obligation, or else finding a bound that is in +/// scope. The eventual result is usually a `Selection` (defined below). +#[derive(Clone, PartialEq, Eq, Hash)] +pub struct Obligation<'tcx, T> { + /// The reason we have to prove this thing. + pub cause: ObligationCause<'tcx>, + + /// The environment in which we should prove this thing. + pub param_env: ty::ParamEnv<'tcx>, + + /// The thing we are trying to prove. + pub predicate: T, + + /// If we started proving this as a result of trying to prove + /// something else, track the total depth to ensure termination. + /// If this goes over a certain threshold, we abort compilation -- + /// in such cases, we can not say whether or not the predicate + /// holds for certain. Stupid halting problem; such a drag. + pub recursion_depth: usize, +} + +pub type PredicateObligation<'tcx> = Obligation<'tcx, ty::Predicate<'tcx>>; +pub type TraitObligation<'tcx> = Obligation<'tcx, ty::PolyTraitPredicate<'tcx>>; + +impl<'tcx> PredicateObligation<'tcx> { + /// Flips the polarity of the inner predicate. + /// + /// Given `T: Trait` predicate it returns `T: !Trait` and given `T: !Trait` returns `T: Trait`. + pub fn flip_polarity(&self, tcx: TyCtxt<'tcx>) -> Option<PredicateObligation<'tcx>> { + Some(PredicateObligation { + cause: self.cause.clone(), + param_env: self.param_env, + predicate: self.predicate.flip_polarity(tcx)?, + recursion_depth: self.recursion_depth, + }) + } +} + +impl<'tcx> TraitObligation<'tcx> { + /// Returns `true` if the trait predicate is considered `const` in its ParamEnv. + pub fn is_const(&self) -> bool { + match (self.predicate.skip_binder().constness, self.param_env.constness()) { + (ty::BoundConstness::ConstIfConst, hir::Constness::Const) => true, + _ => false, + } + } + + pub fn derived_cause( + &self, + variant: impl FnOnce(DerivedObligationCause<'tcx>) -> ObligationCauseCode<'tcx>, + ) -> ObligationCause<'tcx> { + self.cause.clone().derived_cause(self.predicate, variant) + } +} + +// `PredicateObligation` is used a lot. Make sure it doesn't unintentionally get bigger. +#[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))] +static_assert_size!(PredicateObligation<'_>, 48); + +pub type PredicateObligations<'tcx> = Vec<PredicateObligation<'tcx>>; + +pub type Selection<'tcx> = ImplSource<'tcx, PredicateObligation<'tcx>>; + +pub struct FulfillmentError<'tcx> { + pub obligation: PredicateObligation<'tcx>, + pub code: FulfillmentErrorCode<'tcx>, + /// Diagnostics only: the 'root' obligation which resulted in + /// the failure to process `obligation`. This is the obligation + /// that was initially passed to `register_predicate_obligation` + pub root_obligation: PredicateObligation<'tcx>, +} + +#[derive(Clone)] +pub enum FulfillmentErrorCode<'tcx> { + CodeSelectionError(SelectionError<'tcx>), + CodeProjectionError(MismatchedProjectionTypes<'tcx>), + CodeSubtypeError(ExpectedFound<Ty<'tcx>>, TypeError<'tcx>), // always comes from a SubtypePredicate + CodeConstEquateError(ExpectedFound<Const<'tcx>>, TypeError<'tcx>), + CodeAmbiguity, +} + +impl<'tcx, O> Obligation<'tcx, O> { + pub fn new( + cause: ObligationCause<'tcx>, + param_env: ty::ParamEnv<'tcx>, + predicate: O, + ) -> Obligation<'tcx, O> { + Obligation { cause, param_env, recursion_depth: 0, predicate } + } + + pub fn with_depth( + cause: ObligationCause<'tcx>, + recursion_depth: usize, + param_env: ty::ParamEnv<'tcx>, + predicate: O, + ) -> Obligation<'tcx, O> { + Obligation { cause, param_env, recursion_depth, predicate } + } + + pub fn misc( + span: Span, + body_id: hir::HirId, + param_env: ty::ParamEnv<'tcx>, + trait_ref: O, + ) -> Obligation<'tcx, O> { + Obligation::new(ObligationCause::misc(span, body_id), param_env, trait_ref) + } + + pub fn with<P>(&self, value: P) -> Obligation<'tcx, P> { + Obligation { + cause: self.cause.clone(), + param_env: self.param_env, + recursion_depth: self.recursion_depth, + predicate: value, + } + } +} + +impl<'tcx> FulfillmentError<'tcx> { + pub fn new( + obligation: PredicateObligation<'tcx>, + code: FulfillmentErrorCode<'tcx>, + root_obligation: PredicateObligation<'tcx>, + ) -> FulfillmentError<'tcx> { + FulfillmentError { obligation, code, root_obligation } + } +} + +impl<'tcx> TraitObligation<'tcx> { + pub fn polarity(&self) -> ty::ImplPolarity { + self.predicate.skip_binder().polarity + } + + pub fn self_ty(&self) -> ty::Binder<'tcx, Ty<'tcx>> { + self.predicate.map_bound(|p| p.self_ty()) + } +} diff --git a/compiler/rustc_infer/src/traits/project.rs b/compiler/rustc_infer/src/traits/project.rs new file mode 100644 index 000000000..5d22f9f97 --- /dev/null +++ b/compiler/rustc_infer/src/traits/project.rs @@ -0,0 +1,255 @@ +//! Code for projecting associated types out of trait references. + +use super::PredicateObligation; + +use crate::infer::InferCtxtUndoLogs; + +use rustc_data_structures::{ + snapshot_map::{self, SnapshotMapRef, SnapshotMapStorage}, + undo_log::Rollback, +}; +use rustc_middle::ty::{self, Ty}; + +pub use rustc_middle::traits::{EvaluationResult, Reveal}; + +pub(crate) type UndoLog<'tcx> = + snapshot_map::UndoLog<ProjectionCacheKey<'tcx>, ProjectionCacheEntry<'tcx>>; + +#[derive(Clone)] +pub struct MismatchedProjectionTypes<'tcx> { + pub err: ty::error::TypeError<'tcx>, +} + +#[derive(Clone, TypeFoldable, TypeVisitable)] +pub struct Normalized<'tcx, T> { + pub value: T, + pub obligations: Vec<PredicateObligation<'tcx>>, +} + +pub type NormalizedTy<'tcx> = Normalized<'tcx, Ty<'tcx>>; + +impl<'tcx, T> Normalized<'tcx, T> { + pub fn with<U>(self, value: U) -> Normalized<'tcx, U> { + Normalized { value, obligations: self.obligations } + } +} + +// # Cache + +/// The projection cache. Unlike the standard caches, this can include +/// infcx-dependent type variables, therefore we have to roll the +/// cache back each time we roll a snapshot back, to avoid assumptions +/// on yet-unresolved inference variables. Types with placeholder +/// regions also have to be removed when the respective snapshot ends. +/// +/// Because of that, projection cache entries can be "stranded" and left +/// inaccessible when type variables inside the key are resolved. We make no +/// attempt to recover or remove "stranded" entries, but rather let them be +/// (for the lifetime of the infcx). +/// +/// Entries in the projection cache might contain inference variables +/// that will be resolved by obligations on the projection cache entry (e.g., +/// when a type parameter in the associated type is constrained through +/// an "RFC 447" projection on the impl). +/// +/// When working with a fulfillment context, the derived obligations of each +/// projection cache entry will be registered on the fulfillcx, so any users +/// that can wait for a fulfillcx fixed point need not care about this. However, +/// users that don't wait for a fixed point (e.g., trait evaluation) have to +/// resolve the obligations themselves to make sure the projected result is +/// ok and avoid issues like #43132. +/// +/// If that is done, after evaluation the obligations, it is a good idea to +/// call `ProjectionCache::complete` to make sure the obligations won't be +/// re-evaluated and avoid an exponential worst-case. +// +// FIXME: we probably also want some sort of cross-infcx cache here to +// reduce the amount of duplication. Let's see what we get with the Chalk reforms. +pub struct ProjectionCache<'a, 'tcx> { + map: &'a mut SnapshotMapStorage<ProjectionCacheKey<'tcx>, ProjectionCacheEntry<'tcx>>, + undo_log: &'a mut InferCtxtUndoLogs<'tcx>, +} + +#[derive(Clone, Default)] +pub struct ProjectionCacheStorage<'tcx> { + map: SnapshotMapStorage<ProjectionCacheKey<'tcx>, ProjectionCacheEntry<'tcx>>, +} + +#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)] +pub struct ProjectionCacheKey<'tcx> { + ty: ty::ProjectionTy<'tcx>, +} + +impl<'tcx> ProjectionCacheKey<'tcx> { + pub fn new(ty: ty::ProjectionTy<'tcx>) -> Self { + Self { ty } + } +} + +#[derive(Clone, Debug)] +pub enum ProjectionCacheEntry<'tcx> { + InProgress, + Ambiguous, + Recur, + Error, + NormalizedTy { + ty: Normalized<'tcx, ty::Term<'tcx>>, + /// If we were able to successfully evaluate the + /// corresponding cache entry key during predicate + /// evaluation, then this field stores the final + /// result obtained from evaluating all of the projection + /// sub-obligations. During evaluation, we will skip + /// evaluating the cached sub-obligations in `ty` + /// if this field is set. Evaluation only + /// cares about the final result, so we don't + /// care about any region constraint side-effects + /// produced by evaluating the sub-boligations. + /// + /// Additionally, we will clear out the sub-obligations + /// entirely if we ever evaluate the cache entry (along + /// with all its sub obligations) to `EvaluatedToOk`. + /// This affects all users of the cache, not just evaluation. + /// Since a result of `EvaluatedToOk` means that there were + /// no region obligations that need to be tracked, it's + /// fine to forget about the sub-obligations - they + /// don't provide any additional information. However, + /// we do *not* discard any obligations when we see + /// `EvaluatedToOkModuloRegions` - we don't know + /// which sub-obligations may introduce region constraints, + /// so we keep them all to be safe. + /// + /// When we are not performing evaluation + /// (e.g. in `FulfillmentContext`), we ignore this field, + /// and always re-process the cached sub-obligations + /// (which may have been cleared out - see the above + /// paragraph). + /// This ensures that we do not lose any regions + /// constraints that arise from processing the + /// sub-obligations. + complete: Option<EvaluationResult>, + }, +} + +impl<'tcx> ProjectionCacheStorage<'tcx> { + #[inline] + pub(crate) fn with_log<'a>( + &'a mut self, + undo_log: &'a mut InferCtxtUndoLogs<'tcx>, + ) -> ProjectionCache<'a, 'tcx> { + ProjectionCache { map: &mut self.map, undo_log } + } +} + +impl<'tcx> ProjectionCache<'_, 'tcx> { + #[inline] + fn map( + &mut self, + ) -> SnapshotMapRef< + '_, + ProjectionCacheKey<'tcx>, + ProjectionCacheEntry<'tcx>, + InferCtxtUndoLogs<'tcx>, + > { + self.map.with_log(self.undo_log) + } + + pub fn clear(&mut self) { + self.map().clear(); + } + + /// Try to start normalize `key`; returns an error if + /// normalization already occurred (this error corresponds to a + /// cache hit, so it's actually a good thing). + pub fn try_start( + &mut self, + key: ProjectionCacheKey<'tcx>, + ) -> Result<(), ProjectionCacheEntry<'tcx>> { + let mut map = self.map(); + if let Some(entry) = map.get(&key) { + return Err(entry.clone()); + } + + map.insert(key, ProjectionCacheEntry::InProgress); + Ok(()) + } + + /// Indicates that `key` was normalized to `value`. + pub fn insert_term( + &mut self, + key: ProjectionCacheKey<'tcx>, + value: Normalized<'tcx, ty::Term<'tcx>>, + ) { + debug!( + "ProjectionCacheEntry::insert_ty: adding cache entry: key={:?}, value={:?}", + key, value + ); + let mut map = self.map(); + if let Some(ProjectionCacheEntry::Recur) = map.get(&key) { + debug!("Not overwriting Recur"); + return; + } + let fresh_key = + map.insert(key, ProjectionCacheEntry::NormalizedTy { ty: value, complete: None }); + assert!(!fresh_key, "never started projecting `{:?}`", key); + } + + /// Mark the relevant projection cache key as having its derived obligations + /// complete, so they won't have to be re-computed (this is OK to do in a + /// snapshot - if the snapshot is rolled back, the obligations will be + /// marked as incomplete again). + pub fn complete(&mut self, key: ProjectionCacheKey<'tcx>, result: EvaluationResult) { + let mut map = self.map(); + match map.get(&key) { + Some(&ProjectionCacheEntry::NormalizedTy { ref ty, complete: _ }) => { + info!("ProjectionCacheEntry::complete({:?}) - completing {:?}", key, ty); + let mut ty = ty.clone(); + if result.must_apply_considering_regions() { + ty.obligations = vec![]; + } + map.insert(key, ProjectionCacheEntry::NormalizedTy { ty, complete: Some(result) }); + } + ref value => { + // Type inference could "strand behind" old cache entries. Leave + // them alone for now. + info!("ProjectionCacheEntry::complete({:?}) - ignoring {:?}", key, value); + } + }; + } + + pub fn is_complete(&mut self, key: ProjectionCacheKey<'tcx>) -> Option<EvaluationResult> { + self.map().get(&key).and_then(|res| match res { + ProjectionCacheEntry::NormalizedTy { ty: _, complete } => *complete, + _ => None, + }) + } + + /// Indicates that trying to normalize `key` resulted in + /// ambiguity. No point in trying it again then until we gain more + /// type information (in which case, the "fully resolved" key will + /// be different). + pub fn ambiguous(&mut self, key: ProjectionCacheKey<'tcx>) { + let fresh = self.map().insert(key, ProjectionCacheEntry::Ambiguous); + assert!(!fresh, "never started projecting `{:?}`", key); + } + + /// Indicates that while trying to normalize `key`, `key` was required to + /// be normalized again. Selection or evaluation should eventually report + /// an error here. + pub fn recur(&mut self, key: ProjectionCacheKey<'tcx>) { + let fresh = self.map().insert(key, ProjectionCacheEntry::Recur); + assert!(!fresh, "never started projecting `{:?}`", key); + } + + /// Indicates that trying to normalize `key` resulted in + /// error. + pub fn error(&mut self, key: ProjectionCacheKey<'tcx>) { + let fresh = self.map().insert(key, ProjectionCacheEntry::Error); + assert!(!fresh, "never started projecting `{:?}`", key); + } +} + +impl<'tcx> Rollback<UndoLog<'tcx>> for ProjectionCacheStorage<'tcx> { + fn reverse(&mut self, undo: UndoLog<'tcx>) { + self.map.reverse(undo); + } +} diff --git a/compiler/rustc_infer/src/traits/structural_impls.rs b/compiler/rustc_infer/src/traits/structural_impls.rs new file mode 100644 index 000000000..573d2d1e3 --- /dev/null +++ b/compiler/rustc_infer/src/traits/structural_impls.rs @@ -0,0 +1,79 @@ +use crate::traits; +use crate::traits::project::Normalized; +use rustc_middle::ty; +use rustc_middle::ty::fold::{FallibleTypeFolder, TypeFoldable}; +use rustc_middle::ty::visit::{TypeVisitable, TypeVisitor}; + +use std::fmt; +use std::ops::ControlFlow; + +// Structural impls for the structs in `traits`. + +impl<'tcx, T: fmt::Debug> fmt::Debug for Normalized<'tcx, T> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "Normalized({:?}, {:?})", self.value, self.obligations) + } +} + +impl<'tcx, O: fmt::Debug> fmt::Debug for traits::Obligation<'tcx, O> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + if ty::tls::with(|tcx| tcx.sess.verbose()) { + write!( + f, + "Obligation(predicate={:?}, cause={:?}, param_env={:?}, depth={})", + self.predicate, self.cause, self.param_env, self.recursion_depth + ) + } else { + write!(f, "Obligation(predicate={:?}, depth={})", self.predicate, self.recursion_depth) + } + } +} + +impl<'tcx> fmt::Debug for traits::FulfillmentError<'tcx> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "FulfillmentError({:?},{:?})", self.obligation, self.code) + } +} + +impl<'tcx> fmt::Debug for traits::FulfillmentErrorCode<'tcx> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match *self { + super::CodeSelectionError(ref e) => write!(f, "{:?}", e), + super::CodeProjectionError(ref e) => write!(f, "{:?}", e), + super::CodeSubtypeError(ref a, ref b) => { + write!(f, "CodeSubtypeError({:?}, {:?})", a, b) + } + super::CodeConstEquateError(ref a, ref b) => { + write!(f, "CodeConstEquateError({:?}, {:?})", a, b) + } + super::CodeAmbiguity => write!(f, "Ambiguity"), + } + } +} + +impl<'tcx> fmt::Debug for traits::MismatchedProjectionTypes<'tcx> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "MismatchedProjectionTypes({:?})", self.err) + } +} + +/////////////////////////////////////////////////////////////////////////// +// TypeFoldable implementations. + +impl<'tcx, O: TypeFoldable<'tcx>> TypeFoldable<'tcx> for traits::Obligation<'tcx, O> { + fn try_fold_with<F: FallibleTypeFolder<'tcx>>(self, folder: &mut F) -> Result<Self, F::Error> { + Ok(traits::Obligation { + cause: self.cause, + recursion_depth: self.recursion_depth, + predicate: self.predicate.try_fold_with(folder)?, + param_env: self.param_env.try_fold_with(folder)?, + }) + } +} + +impl<'tcx, O: TypeVisitable<'tcx>> TypeVisitable<'tcx> for traits::Obligation<'tcx, O> { + fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> { + self.predicate.visit_with(visitor)?; + self.param_env.visit_with(visitor) + } +} diff --git a/compiler/rustc_infer/src/traits/util.rs b/compiler/rustc_infer/src/traits/util.rs new file mode 100644 index 000000000..f5a1edf6d --- /dev/null +++ b/compiler/rustc_infer/src/traits/util.rs @@ -0,0 +1,390 @@ +use smallvec::smallvec; + +use crate::infer::outlives::components::{push_outlives_components, Component}; +use crate::traits::{Obligation, ObligationCause, PredicateObligation}; +use rustc_data_structures::fx::{FxHashSet, FxIndexSet}; +use rustc_middle::ty::{self, ToPredicate, TyCtxt}; +use rustc_span::symbol::Ident; +use rustc_span::Span; + +pub fn anonymize_predicate<'tcx>( + tcx: TyCtxt<'tcx>, + pred: ty::Predicate<'tcx>, +) -> ty::Predicate<'tcx> { + let new = tcx.anonymize_bound_vars(pred.kind()); + tcx.reuse_or_mk_predicate(pred, new) +} + +pub struct PredicateSet<'tcx> { + tcx: TyCtxt<'tcx>, + set: FxHashSet<ty::Predicate<'tcx>>, +} + +impl<'tcx> PredicateSet<'tcx> { + pub fn new(tcx: TyCtxt<'tcx>) -> Self { + Self { tcx, set: Default::default() } + } + + pub fn insert(&mut self, pred: ty::Predicate<'tcx>) -> bool { + // We have to be careful here because we want + // + // for<'a> Foo<&'a i32> + // + // and + // + // for<'b> Foo<&'b i32> + // + // to be considered equivalent. So normalize all late-bound + // regions before we throw things into the underlying set. + self.set.insert(anonymize_predicate(self.tcx, pred)) + } +} + +impl<'tcx> Extend<ty::Predicate<'tcx>> for PredicateSet<'tcx> { + fn extend<I: IntoIterator<Item = ty::Predicate<'tcx>>>(&mut self, iter: I) { + for pred in iter { + self.insert(pred); + } + } + + fn extend_one(&mut self, pred: ty::Predicate<'tcx>) { + self.insert(pred); + } + + fn extend_reserve(&mut self, additional: usize) { + Extend::<ty::Predicate<'tcx>>::extend_reserve(&mut self.set, additional); + } +} + +/////////////////////////////////////////////////////////////////////////// +// `Elaboration` iterator +/////////////////////////////////////////////////////////////////////////// + +/// "Elaboration" is the process of identifying all the predicates that +/// are implied by a source predicate. Currently, this basically means +/// walking the "supertraits" and other similar assumptions. For example, +/// if we know that `T: Ord`, the elaborator would deduce that `T: PartialOrd` +/// holds as well. Similarly, if we have `trait Foo: 'static`, and we know that +/// `T: Foo`, then we know that `T: 'static`. +pub struct Elaborator<'tcx> { + stack: Vec<PredicateObligation<'tcx>>, + visited: PredicateSet<'tcx>, +} + +pub fn elaborate_trait_ref<'tcx>( + tcx: TyCtxt<'tcx>, + trait_ref: ty::PolyTraitRef<'tcx>, +) -> Elaborator<'tcx> { + elaborate_predicates(tcx, std::iter::once(trait_ref.without_const().to_predicate(tcx))) +} + +pub fn elaborate_trait_refs<'tcx>( + tcx: TyCtxt<'tcx>, + trait_refs: impl Iterator<Item = ty::PolyTraitRef<'tcx>>, +) -> Elaborator<'tcx> { + let predicates = trait_refs.map(|trait_ref| trait_ref.without_const().to_predicate(tcx)); + elaborate_predicates(tcx, predicates) +} + +pub fn elaborate_predicates<'tcx>( + tcx: TyCtxt<'tcx>, + predicates: impl Iterator<Item = ty::Predicate<'tcx>>, +) -> Elaborator<'tcx> { + let obligations = predicates + .map(|predicate| { + predicate_obligation(predicate, ty::ParamEnv::empty(), ObligationCause::dummy()) + }) + .collect(); + elaborate_obligations(tcx, obligations) +} + +pub fn elaborate_predicates_with_span<'tcx>( + tcx: TyCtxt<'tcx>, + predicates: impl Iterator<Item = (ty::Predicate<'tcx>, Span)>, +) -> Elaborator<'tcx> { + let obligations = predicates + .map(|(predicate, span)| { + predicate_obligation( + predicate, + ty::ParamEnv::empty(), + ObligationCause::dummy_with_span(span), + ) + }) + .collect(); + elaborate_obligations(tcx, obligations) +} + +pub fn elaborate_obligations<'tcx>( + tcx: TyCtxt<'tcx>, + mut obligations: Vec<PredicateObligation<'tcx>>, +) -> Elaborator<'tcx> { + let mut visited = PredicateSet::new(tcx); + obligations.retain(|obligation| visited.insert(obligation.predicate)); + Elaborator { stack: obligations, visited } +} + +fn predicate_obligation<'tcx>( + predicate: ty::Predicate<'tcx>, + param_env: ty::ParamEnv<'tcx>, + cause: ObligationCause<'tcx>, +) -> PredicateObligation<'tcx> { + Obligation { cause, param_env, recursion_depth: 0, predicate } +} + +impl<'tcx> Elaborator<'tcx> { + pub fn filter_to_traits(self) -> FilterToTraits<Self> { + FilterToTraits::new(self) + } + + fn elaborate(&mut self, obligation: &PredicateObligation<'tcx>) { + let tcx = self.visited.tcx; + + let bound_predicate = obligation.predicate.kind(); + match bound_predicate.skip_binder() { + ty::PredicateKind::Trait(data) => { + // Get predicates declared on the trait. + let predicates = tcx.super_predicates_of(data.def_id()); + + let obligations = predicates.predicates.iter().map(|&(mut pred, _)| { + // when parent predicate is non-const, elaborate it to non-const predicates. + if data.constness == ty::BoundConstness::NotConst { + pred = pred.without_const(tcx); + } + + predicate_obligation( + pred.subst_supertrait(tcx, &bound_predicate.rebind(data.trait_ref)), + obligation.param_env, + obligation.cause.clone(), + ) + }); + debug!(?data, ?obligations, "super_predicates"); + + // Only keep those bounds that we haven't already seen. + // This is necessary to prevent infinite recursion in some + // cases. One common case is when people define + // `trait Sized: Sized { }` rather than `trait Sized { }`. + let visited = &mut self.visited; + let obligations = obligations.filter(|o| visited.insert(o.predicate)); + + self.stack.extend(obligations); + } + ty::PredicateKind::WellFormed(..) => { + // Currently, we do not elaborate WF predicates, + // although we easily could. + } + ty::PredicateKind::ObjectSafe(..) => { + // Currently, we do not elaborate object-safe + // predicates. + } + ty::PredicateKind::Subtype(..) => { + // Currently, we do not "elaborate" predicates like `X <: Y`, + // though conceivably we might. + } + ty::PredicateKind::Coerce(..) => { + // Currently, we do not "elaborate" predicates like `X -> Y`, + // though conceivably we might. + } + ty::PredicateKind::Projection(..) => { + // Nothing to elaborate in a projection predicate. + } + ty::PredicateKind::ClosureKind(..) => { + // Nothing to elaborate when waiting for a closure's kind to be inferred. + } + ty::PredicateKind::ConstEvaluatable(..) => { + // Currently, we do not elaborate const-evaluatable + // predicates. + } + ty::PredicateKind::ConstEquate(..) => { + // Currently, we do not elaborate const-equate + // predicates. + } + ty::PredicateKind::RegionOutlives(..) => { + // Nothing to elaborate from `'a: 'b`. + } + ty::PredicateKind::TypeOutlives(ty::OutlivesPredicate(ty_max, r_min)) => { + // We know that `T: 'a` for some type `T`. We can + // often elaborate this. For example, if we know that + // `[U]: 'a`, that implies that `U: 'a`. Similarly, if + // we know `&'a U: 'b`, then we know that `'a: 'b` and + // `U: 'b`. + // + // We can basically ignore bound regions here. So for + // example `for<'c> Foo<'a,'c>: 'b` can be elaborated to + // `'a: 'b`. + + // Ignore `for<'a> T: 'a` -- we might in the future + // consider this as evidence that `T: 'static`, but + // I'm a bit wary of such constructions and so for now + // I want to be conservative. --nmatsakis + if r_min.is_late_bound() { + return; + } + + let visited = &mut self.visited; + let mut components = smallvec![]; + push_outlives_components(tcx, ty_max, &mut components); + self.stack.extend( + components + .into_iter() + .filter_map(|component| match component { + Component::Region(r) => { + if r.is_late_bound() { + None + } else { + Some(ty::PredicateKind::RegionOutlives(ty::OutlivesPredicate( + r, r_min, + ))) + } + } + + Component::Param(p) => { + let ty = tcx.mk_ty_param(p.index, p.name); + Some(ty::PredicateKind::TypeOutlives(ty::OutlivesPredicate( + ty, r_min, + ))) + } + + Component::UnresolvedInferenceVariable(_) => None, + + Component::Projection(projection) => { + // We might end up here if we have `Foo<<Bar as Baz>::Assoc>: 'a`. + // With this, we can deduce that `<Bar as Baz>::Assoc: 'a`. + let ty = + tcx.mk_projection(projection.item_def_id, projection.substs); + Some(ty::PredicateKind::TypeOutlives(ty::OutlivesPredicate( + ty, r_min, + ))) + } + + Component::EscapingProjection(_) => { + // We might be able to do more here, but we don't + // want to deal with escaping vars right now. + None + } + }) + .map(ty::Binder::dummy) + .map(|predicate_kind| predicate_kind.to_predicate(tcx)) + .filter(|&predicate| visited.insert(predicate)) + .map(|predicate| { + predicate_obligation( + predicate, + obligation.param_env, + obligation.cause.clone(), + ) + }), + ); + } + ty::PredicateKind::TypeWellFormedFromEnv(..) => { + // Nothing to elaborate + } + } + } +} + +impl<'tcx> Iterator for Elaborator<'tcx> { + type Item = PredicateObligation<'tcx>; + + fn size_hint(&self) -> (usize, Option<usize>) { + (self.stack.len(), None) + } + + fn next(&mut self) -> Option<Self::Item> { + // Extract next item from top-most stack frame, if any. + if let Some(obligation) = self.stack.pop() { + self.elaborate(&obligation); + Some(obligation) + } else { + None + } + } +} + +/////////////////////////////////////////////////////////////////////////// +// Supertrait iterator +/////////////////////////////////////////////////////////////////////////// + +pub type Supertraits<'tcx> = FilterToTraits<Elaborator<'tcx>>; + +pub fn supertraits<'tcx>( + tcx: TyCtxt<'tcx>, + trait_ref: ty::PolyTraitRef<'tcx>, +) -> Supertraits<'tcx> { + elaborate_trait_ref(tcx, trait_ref).filter_to_traits() +} + +pub fn transitive_bounds<'tcx>( + tcx: TyCtxt<'tcx>, + bounds: impl Iterator<Item = ty::PolyTraitRef<'tcx>>, +) -> Supertraits<'tcx> { + elaborate_trait_refs(tcx, bounds).filter_to_traits() +} + +/// A specialized variant of `elaborate_trait_refs` that only elaborates trait references that may +/// define the given associated type `assoc_name`. It uses the +/// `super_predicates_that_define_assoc_type` query to avoid enumerating super-predicates that +/// aren't related to `assoc_item`. This is used when resolving types like `Self::Item` or +/// `T::Item` and helps to avoid cycle errors (see e.g. #35237). +pub fn transitive_bounds_that_define_assoc_type<'tcx>( + tcx: TyCtxt<'tcx>, + bounds: impl Iterator<Item = ty::PolyTraitRef<'tcx>>, + assoc_name: Ident, +) -> impl Iterator<Item = ty::PolyTraitRef<'tcx>> { + let mut stack: Vec<_> = bounds.collect(); + let mut visited = FxIndexSet::default(); + + std::iter::from_fn(move || { + while let Some(trait_ref) = stack.pop() { + let anon_trait_ref = tcx.anonymize_bound_vars(trait_ref); + if visited.insert(anon_trait_ref) { + let super_predicates = tcx.super_predicates_that_define_assoc_type(( + trait_ref.def_id(), + Some(assoc_name), + )); + for (super_predicate, _) in super_predicates.predicates { + let subst_predicate = super_predicate.subst_supertrait(tcx, &trait_ref); + if let Some(binder) = subst_predicate.to_opt_poly_trait_pred() { + stack.push(binder.map_bound(|t| t.trait_ref)); + } + } + + return Some(trait_ref); + } + } + + return None; + }) +} + +/////////////////////////////////////////////////////////////////////////// +// Other +/////////////////////////////////////////////////////////////////////////// + +/// A filter around an iterator of predicates that makes it yield up +/// just trait references. +pub struct FilterToTraits<I> { + base_iterator: I, +} + +impl<I> FilterToTraits<I> { + fn new(base: I) -> FilterToTraits<I> { + FilterToTraits { base_iterator: base } + } +} + +impl<'tcx, I: Iterator<Item = PredicateObligation<'tcx>>> Iterator for FilterToTraits<I> { + type Item = ty::PolyTraitRef<'tcx>; + + fn next(&mut self) -> Option<ty::PolyTraitRef<'tcx>> { + while let Some(obligation) = self.base_iterator.next() { + if let Some(data) = obligation.predicate.to_opt_poly_trait_pred() { + return Some(data.map_bound(|t| t.trait_ref)); + } + } + None + } + + fn size_hint(&self) -> (usize, Option<usize>) { + let (_, upper) = self.base_iterator.size_hint(); + (0, upper) + } +} |