summaryrefslogtreecommitdiffstats
path: root/compiler/rustc_infer/src/traits
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-17 12:02:58 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-17 12:02:58 +0000
commit698f8c2f01ea549d77d7dc3338a12e04c11057b9 (patch)
tree173a775858bd501c378080a10dca74132f05bc50 /compiler/rustc_infer/src/traits
parentInitial commit. (diff)
downloadrustc-698f8c2f01ea549d77d7dc3338a12e04c11057b9.tar.xz
rustc-698f8c2f01ea549d77d7dc3338a12e04c11057b9.zip
Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'compiler/rustc_infer/src/traits')
-rw-r--r--compiler/rustc_infer/src/traits/engine.rs76
-rw-r--r--compiler/rustc_infer/src/traits/error_reporting/mod.rs108
-rw-r--r--compiler/rustc_infer/src/traits/mod.rs170
-rw-r--r--compiler/rustc_infer/src/traits/project.rs255
-rw-r--r--compiler/rustc_infer/src/traits/structural_impls.rs79
-rw-r--r--compiler/rustc_infer/src/traits/util.rs390
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)
+ }
+}