From 698f8c2f01ea549d77d7dc3338a12e04c11057b9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:02:58 +0200 Subject: Adding upstream version 1.64.0+dfsg1. Signed-off-by: Daniel Baumann --- compiler/rustc_middle/src/traits/chalk.rs | 403 ++++++++ compiler/rustc_middle/src/traits/mod.rs | 1026 ++++++++++++++++++++ compiler/rustc_middle/src/traits/query.rs | 230 +++++ compiler/rustc_middle/src/traits/select.rs | 312 ++++++ .../src/traits/specialization_graph.rs | 261 +++++ .../rustc_middle/src/traits/structural_impls.rs | 135 +++ compiler/rustc_middle/src/traits/util.rs | 49 + 7 files changed, 2416 insertions(+) create mode 100644 compiler/rustc_middle/src/traits/chalk.rs create mode 100644 compiler/rustc_middle/src/traits/mod.rs create mode 100644 compiler/rustc_middle/src/traits/query.rs create mode 100644 compiler/rustc_middle/src/traits/select.rs create mode 100644 compiler/rustc_middle/src/traits/specialization_graph.rs create mode 100644 compiler/rustc_middle/src/traits/structural_impls.rs create mode 100644 compiler/rustc_middle/src/traits/util.rs (limited to 'compiler/rustc_middle/src/traits') diff --git a/compiler/rustc_middle/src/traits/chalk.rs b/compiler/rustc_middle/src/traits/chalk.rs new file mode 100644 index 000000000..6d4af8bea --- /dev/null +++ b/compiler/rustc_middle/src/traits/chalk.rs @@ -0,0 +1,403 @@ +//! Types required for Chalk-related queries +//! +//! The primary purpose of this file is defining an implementation for the +//! `chalk_ir::interner::Interner` trait. The primary purpose of this trait, as +//! its name suggest, is to provide an abstraction boundary for creating +//! interned Chalk types. + +use rustc_middle::ty::{self, AdtDef, TyCtxt}; + +use rustc_hir::def_id::DefId; +use rustc_target::spec::abi::Abi; + +use std::cmp::Ordering; +use std::fmt; +use std::hash::{Hash, Hasher}; + +#[derive(Copy, Clone)] +pub struct RustInterner<'tcx> { + pub tcx: TyCtxt<'tcx>, +} + +/// We don't ever actually need this. It's only required for derives. +impl<'tcx> Hash for RustInterner<'tcx> { + fn hash(&self, _state: &mut H) {} +} + +/// We don't ever actually need this. It's only required for derives. +impl<'tcx> Ord for RustInterner<'tcx> { + fn cmp(&self, _other: &Self) -> Ordering { + Ordering::Equal + } +} + +/// We don't ever actually need this. It's only required for derives. +impl<'tcx> PartialOrd for RustInterner<'tcx> { + fn partial_cmp(&self, _other: &Self) -> Option { + None + } +} + +/// We don't ever actually need this. It's only required for derives. +impl<'tcx> PartialEq for RustInterner<'tcx> { + fn eq(&self, _other: &Self) -> bool { + false + } +} + +/// We don't ever actually need this. It's only required for derives. +impl<'tcx> Eq for RustInterner<'tcx> {} + +impl fmt::Debug for RustInterner<'_> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "RustInterner") + } +} + +// Right now, there is no interning at all. I was running into problems with +// adding interning in `ty/context.rs` for Chalk types with +// `parallel-compiler = true`. -jackh726 +impl<'tcx> chalk_ir::interner::Interner for RustInterner<'tcx> { + type InternedType = Box>; + type InternedLifetime = Box>; + type InternedConst = Box>; + type InternedConcreteConst = ty::ValTree<'tcx>; + type InternedGenericArg = Box>; + type InternedGoal = Box>; + type InternedGoals = Vec>; + type InternedSubstitution = Vec>; + type InternedProgramClause = Box>; + type InternedProgramClauses = Vec>; + type InternedQuantifiedWhereClauses = Vec>; + type InternedVariableKinds = Vec>; + type InternedCanonicalVarKinds = Vec>; + type InternedVariances = Vec; + type InternedConstraints = Vec>>; + type DefId = DefId; + type InternedAdtId = AdtDef<'tcx>; + type Identifier = (); + type FnAbi = Abi; + + fn debug_program_clause_implication( + pci: &chalk_ir::ProgramClauseImplication, + fmt: &mut fmt::Formatter<'_>, + ) -> Option { + let mut write = || { + write!(fmt, "{:?}", pci.consequence)?; + + let conditions = pci.conditions.interned(); + let constraints = pci.constraints.interned(); + + let conds = conditions.len(); + let consts = constraints.len(); + if conds == 0 && consts == 0 { + return Ok(()); + } + + write!(fmt, " :- ")?; + + if conds != 0 { + for cond in &conditions[..conds - 1] { + write!(fmt, "{:?}, ", cond)?; + } + write!(fmt, "{:?}", conditions[conds - 1])?; + } + + if conds != 0 && consts != 0 { + write!(fmt, " ; ")?; + } + + if consts != 0 { + for constraint in &constraints[..consts - 1] { + write!(fmt, "{:?}, ", constraint)?; + } + write!(fmt, "{:?}", constraints[consts - 1])?; + } + + Ok(()) + }; + Some(write()) + } + + fn debug_substitution( + substitution: &chalk_ir::Substitution, + fmt: &mut fmt::Formatter<'_>, + ) -> Option { + Some(write!(fmt, "{:?}", substitution.interned())) + } + + fn debug_separator_trait_ref( + separator_trait_ref: &chalk_ir::SeparatorTraitRef<'_, Self>, + fmt: &mut fmt::Formatter<'_>, + ) -> Option { + let substitution = &separator_trait_ref.trait_ref.substitution; + let parameters = substitution.interned(); + Some(write!( + fmt, + "{:?}{}{:?}{:?}", + parameters[0], + separator_trait_ref.separator, + separator_trait_ref.trait_ref.trait_id, + chalk_ir::debug::Angle(¶meters[1..]) + )) + } + + fn debug_quantified_where_clauses( + clauses: &chalk_ir::QuantifiedWhereClauses, + fmt: &mut fmt::Formatter<'_>, + ) -> Option { + Some(write!(fmt, "{:?}", clauses.interned())) + } + + fn debug_ty(ty: &chalk_ir::Ty, fmt: &mut fmt::Formatter<'_>) -> Option { + match &ty.interned().kind { + chalk_ir::TyKind::Ref(chalk_ir::Mutability::Not, lifetime, ty) => { + Some(write!(fmt, "(&{:?} {:?})", lifetime, ty)) + } + chalk_ir::TyKind::Ref(chalk_ir::Mutability::Mut, lifetime, ty) => { + Some(write!(fmt, "(&{:?} mut {:?})", lifetime, ty)) + } + chalk_ir::TyKind::Array(ty, len) => Some(write!(fmt, "[{:?}; {:?}]", ty, len)), + chalk_ir::TyKind::Slice(ty) => Some(write!(fmt, "[{:?}]", ty)), + chalk_ir::TyKind::Tuple(len, substs) => Some((|| { + write!(fmt, "(")?; + for (idx, substitution) in substs.interned().iter().enumerate() { + if idx == *len && *len != 1 { + // Don't add a trailing comma if the tuple has more than one element + write!(fmt, "{:?}", substitution)?; + } else { + write!(fmt, "{:?},", substitution)?; + } + } + write!(fmt, ")") + })()), + _ => None, + } + } + + fn debug_alias( + alias_ty: &chalk_ir::AliasTy, + fmt: &mut fmt::Formatter<'_>, + ) -> Option { + match alias_ty { + chalk_ir::AliasTy::Projection(projection_ty) => { + Self::debug_projection_ty(projection_ty, fmt) + } + chalk_ir::AliasTy::Opaque(opaque_ty) => Self::debug_opaque_ty(opaque_ty, fmt), + } + } + + fn debug_projection_ty( + projection_ty: &chalk_ir::ProjectionTy, + fmt: &mut fmt::Formatter<'_>, + ) -> Option { + Some(write!( + fmt, + "projection: {:?} {:?}", + projection_ty.associated_ty_id, projection_ty.substitution, + )) + } + + fn debug_opaque_ty( + opaque_ty: &chalk_ir::OpaqueTy, + fmt: &mut fmt::Formatter<'_>, + ) -> Option { + Some(write!(fmt, "{:?}", opaque_ty.opaque_ty_id)) + } + + fn intern_ty(self, ty: chalk_ir::TyKind) -> Self::InternedType { + let flags = ty.compute_flags(self); + Box::new(chalk_ir::TyData { kind: ty, flags: flags }) + } + + fn ty_data<'a>(self, ty: &'a Self::InternedType) -> &'a chalk_ir::TyData { + ty + } + + fn intern_lifetime(self, lifetime: chalk_ir::LifetimeData) -> Self::InternedLifetime { + Box::new(lifetime) + } + + fn lifetime_data<'a>( + self, + lifetime: &'a Self::InternedLifetime, + ) -> &'a chalk_ir::LifetimeData { + &lifetime + } + + fn intern_const(self, constant: chalk_ir::ConstData) -> Self::InternedConst { + Box::new(constant) + } + + fn const_data<'a>(self, constant: &'a Self::InternedConst) -> &'a chalk_ir::ConstData { + &constant + } + + fn const_eq( + self, + _ty: &Self::InternedType, + c1: &Self::InternedConcreteConst, + c2: &Self::InternedConcreteConst, + ) -> bool { + c1 == c2 + } + + fn intern_generic_arg(self, data: chalk_ir::GenericArgData) -> Self::InternedGenericArg { + Box::new(data) + } + + fn generic_arg_data<'a>( + self, + data: &'a Self::InternedGenericArg, + ) -> &'a chalk_ir::GenericArgData { + &data + } + + fn intern_goal(self, goal: chalk_ir::GoalData) -> Self::InternedGoal { + Box::new(goal) + } + + fn goal_data<'a>(self, goal: &'a Self::InternedGoal) -> &'a chalk_ir::GoalData { + &goal + } + + fn intern_goals( + self, + data: impl IntoIterator, E>>, + ) -> Result { + data.into_iter().collect::, _>>() + } + + fn goals_data<'a>(self, goals: &'a Self::InternedGoals) -> &'a [chalk_ir::Goal] { + goals + } + + fn intern_substitution( + self, + data: impl IntoIterator, E>>, + ) -> Result { + data.into_iter().collect::, _>>() + } + + fn substitution_data<'a>( + self, + substitution: &'a Self::InternedSubstitution, + ) -> &'a [chalk_ir::GenericArg] { + substitution + } + + fn intern_program_clause( + self, + data: chalk_ir::ProgramClauseData, + ) -> Self::InternedProgramClause { + Box::new(data) + } + + fn program_clause_data<'a>( + self, + clause: &'a Self::InternedProgramClause, + ) -> &'a chalk_ir::ProgramClauseData { + &clause + } + + fn intern_program_clauses( + self, + data: impl IntoIterator, E>>, + ) -> Result { + data.into_iter().collect::, _>>() + } + + fn program_clauses_data<'a>( + self, + clauses: &'a Self::InternedProgramClauses, + ) -> &'a [chalk_ir::ProgramClause] { + clauses + } + + fn intern_quantified_where_clauses( + self, + data: impl IntoIterator, E>>, + ) -> Result { + data.into_iter().collect::, _>>() + } + + fn quantified_where_clauses_data<'a>( + self, + clauses: &'a Self::InternedQuantifiedWhereClauses, + ) -> &'a [chalk_ir::QuantifiedWhereClause] { + clauses + } + + fn intern_generic_arg_kinds( + self, + data: impl IntoIterator, E>>, + ) -> Result { + data.into_iter().collect::, _>>() + } + + fn variable_kinds_data<'a>( + self, + parameter_kinds: &'a Self::InternedVariableKinds, + ) -> &'a [chalk_ir::VariableKind] { + parameter_kinds + } + + fn intern_canonical_var_kinds( + self, + data: impl IntoIterator, E>>, + ) -> Result { + data.into_iter().collect::, _>>() + } + + fn canonical_var_kinds_data<'a>( + self, + canonical_var_kinds: &'a Self::InternedCanonicalVarKinds, + ) -> &'a [chalk_ir::CanonicalVarKind] { + canonical_var_kinds + } + + fn intern_constraints( + self, + data: impl IntoIterator>, E>>, + ) -> Result { + data.into_iter().collect::, _>>() + } + + fn constraints_data<'a>( + self, + constraints: &'a Self::InternedConstraints, + ) -> &'a [chalk_ir::InEnvironment>] { + constraints + } + + fn intern_variances( + self, + data: impl IntoIterator>, + ) -> Result { + data.into_iter().collect::, _>>() + } + + fn variances_data<'a>( + self, + variances: &'a Self::InternedVariances, + ) -> &'a [chalk_ir::Variance] { + variances + } +} + +impl<'tcx> chalk_ir::interner::HasInterner for RustInterner<'tcx> { + type Interner = Self; +} + +/// A chalk environment and goal. +#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable, TypeFoldable, TypeVisitable)] +pub struct ChalkEnvironmentAndGoal<'tcx> { + pub environment: &'tcx ty::List>, + pub goal: ty::Predicate<'tcx>, +} + +impl<'tcx> fmt::Display for ChalkEnvironmentAndGoal<'tcx> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "environment: {:?}, goal: {}", self.environment, self.goal) + } +} diff --git a/compiler/rustc_middle/src/traits/mod.rs b/compiler/rustc_middle/src/traits/mod.rs new file mode 100644 index 000000000..72b848c3e --- /dev/null +++ b/compiler/rustc_middle/src/traits/mod.rs @@ -0,0 +1,1026 @@ +//! 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 chalk; +pub mod query; +pub mod select; +pub mod specialization_graph; +mod structural_impls; +pub mod util; + +use crate::infer::canonical::Canonical; +use crate::ty::abstract_const::NotConstEvaluatable; +use crate::ty::subst::SubstsRef; +use crate::ty::{self, AdtKind, Predicate, Ty, TyCtxt}; + +use rustc_data_structures::sync::Lrc; +use rustc_errors::{Applicability, Diagnostic}; +use rustc_hir as hir; +use rustc_hir::def_id::{DefId, LocalDefId}; +use rustc_span::symbol::Symbol; +use rustc_span::{Span, DUMMY_SP}; +use smallvec::SmallVec; + +use std::borrow::Cow; +use std::hash::{Hash, Hasher}; + +pub use self::select::{EvaluationCache, EvaluationResult, OverflowError, SelectionCache}; + +pub type CanonicalChalkEnvironmentAndGoal<'tcx> = Canonical<'tcx, ChalkEnvironmentAndGoal<'tcx>>; + +pub use self::ObligationCauseCode::*; + +pub use self::chalk::{ChalkEnvironmentAndGoal, RustInterner as ChalkRustInterner}; + +/// Depending on the stage of compilation, we want projection to be +/// more or less conservative. +#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, HashStable)] +pub enum Reveal { + /// At type-checking time, we refuse to project any associated + /// type that is marked `default`. Non-`default` ("final") types + /// are always projected. This is necessary in general for + /// soundness of specialization. However, we *could* allow + /// projections in fully-monomorphic cases. We choose not to, + /// because we prefer for `default type` to force the type + /// definition to be treated abstractly by any consumers of the + /// impl. Concretely, that means that the following example will + /// fail to compile: + /// + /// ```compile_fail,E0308 + /// #![feature(specialization)] + /// trait Assoc { + /// type Output; + /// } + /// + /// impl Assoc for T { + /// default type Output = bool; + /// } + /// + /// fn main() { + /// let x: <() as Assoc>::Output = true; + /// } + /// ``` + /// + /// We also do not reveal the hidden type of opaque types during + /// type-checking. + UserFacing, + + /// At codegen time, all monomorphic projections will succeed. + /// Also, `impl Trait` is normalized to the concrete type, + /// which has to be already collected by type-checking. + /// + /// NOTE: as `impl Trait`'s concrete type should *never* + /// be observable directly by the user, `Reveal::All` + /// should not be used by checks which may expose + /// type equality or type contents to the user. + /// There are some exceptions, e.g., around auto traits and + /// transmute-checking, which expose some details, but + /// not the whole concrete type of the `impl Trait`. + All, +} + +/// The reason why we incurred this obligation; used for error reporting. +/// +/// Non-misc `ObligationCauseCode`s are stored on the heap. This gives the +/// best trade-off between keeping the type small (which makes copies cheaper) +/// while not doing too many heap allocations. +/// +/// We do not want to intern this as there are a lot of obligation causes which +/// only live for a short period of time. +#[derive(Clone, Debug, PartialEq, Eq, Lift)] +pub struct ObligationCause<'tcx> { + pub span: Span, + + /// The ID of the fn body that triggered this obligation. This is + /// used for region obligations to determine the precise + /// environment in which the region obligation should be evaluated + /// (in particular, closures can add new assumptions). See the + /// field `region_obligations` of the `FulfillmentContext` for more + /// information. + pub body_id: hir::HirId, + + code: InternedObligationCauseCode<'tcx>, +} + +// This custom hash function speeds up hashing for `Obligation` deduplication +// greatly by skipping the `code` field, which can be large and complex. That +// shouldn't affect hash quality much since there are several other fields in +// `Obligation` which should be unique enough, especially the predicate itself +// which is hashed as an interned pointer. See #90996. +impl Hash for ObligationCause<'_> { + fn hash(&self, state: &mut H) { + self.body_id.hash(state); + self.span.hash(state); + } +} + +impl<'tcx> ObligationCause<'tcx> { + #[inline] + pub fn new( + span: Span, + body_id: hir::HirId, + code: ObligationCauseCode<'tcx>, + ) -> ObligationCause<'tcx> { + ObligationCause { span, body_id, code: code.into() } + } + + pub fn misc(span: Span, body_id: hir::HirId) -> ObligationCause<'tcx> { + ObligationCause::new(span, body_id, MiscObligation) + } + + #[inline(always)] + pub fn dummy() -> ObligationCause<'tcx> { + ObligationCause::dummy_with_span(DUMMY_SP) + } + + #[inline(always)] + pub fn dummy_with_span(span: Span) -> ObligationCause<'tcx> { + ObligationCause { span, body_id: hir::CRATE_HIR_ID, code: Default::default() } + } + + pub fn span(&self) -> Span { + match *self.code() { + ObligationCauseCode::MatchExpressionArm(box MatchExpressionArmCause { + arm_span, + .. + }) => arm_span, + _ => self.span, + } + } + + #[inline] + pub fn code(&self) -> &ObligationCauseCode<'tcx> { + &self.code + } + + pub fn map_code( + &mut self, + f: impl FnOnce(InternedObligationCauseCode<'tcx>) -> ObligationCauseCode<'tcx>, + ) { + self.code = f(std::mem::take(&mut self.code)).into(); + } + + pub fn derived_cause( + mut self, + parent_trait_pred: ty::PolyTraitPredicate<'tcx>, + variant: impl FnOnce(DerivedObligationCause<'tcx>) -> ObligationCauseCode<'tcx>, + ) -> ObligationCause<'tcx> { + /*! + * Creates a cause for obligations that are derived from + * `obligation` by a recursive search (e.g., for a builtin + * bound, or eventually a `auto trait Foo`). If `obligation` + * is itself a derived obligation, this is just a clone, but + * otherwise we create a "derived obligation" cause so as to + * keep track of the original root obligation for error + * reporting. + */ + + // NOTE(flaper87): As of now, it keeps track of the whole error + // chain. Ideally, we should have a way to configure this either + // by using -Z verbose or just a CLI argument. + self.code = + variant(DerivedObligationCause { parent_trait_pred, parent_code: self.code }).into(); + self + } +} + +#[derive(Clone, Debug, PartialEq, Eq, Hash, Lift)] +pub struct UnifyReceiverContext<'tcx> { + pub assoc_item: ty::AssocItem, + pub param_env: ty::ParamEnv<'tcx>, + pub substs: SubstsRef<'tcx>, +} + +#[derive(Clone, Debug, PartialEq, Eq, Hash, Lift, Default)] +pub struct InternedObligationCauseCode<'tcx> { + /// `None` for `ObligationCauseCode::MiscObligation` (a common case, occurs ~60% of + /// the time). `Some` otherwise. + code: Option>>, +} + +impl<'tcx> ObligationCauseCode<'tcx> { + #[inline(always)] + fn into(self) -> InternedObligationCauseCode<'tcx> { + InternedObligationCauseCode { + code: if let ObligationCauseCode::MiscObligation = self { + None + } else { + Some(Lrc::new(self)) + }, + } + } +} + +impl<'tcx> std::ops::Deref for InternedObligationCauseCode<'tcx> { + type Target = ObligationCauseCode<'tcx>; + + fn deref(&self) -> &Self::Target { + self.code.as_deref().unwrap_or(&ObligationCauseCode::MiscObligation) + } +} + +#[derive(Clone, Debug, PartialEq, Eq, Hash, Lift)] +pub enum ObligationCauseCode<'tcx> { + /// Not well classified or should be obvious from the span. + MiscObligation, + + /// A slice or array is WF only if `T: Sized`. + SliceOrArrayElem, + + /// A tuple is WF only if its middle elements are `Sized`. + TupleElem, + + /// This is the trait reference from the given projection. + ProjectionWf(ty::ProjectionTy<'tcx>), + + /// In an impl of trait `X` for type `Y`, type `Y` must + /// also implement all supertraits of `X`. + ItemObligation(DefId), + + /// Like `ItemObligation`, but with extra detail on the source of the obligation. + BindingObligation(DefId, Span), + + /// A type like `&'a T` is WF only if `T: 'a`. + ReferenceOutlivesReferent(Ty<'tcx>), + + /// A type like `Box + 'b>` is WF only if `'b: 'a`. + ObjectTypeBound(Ty<'tcx>, ty::Region<'tcx>), + + /// Obligation incurred due to an object cast. + ObjectCastObligation(/* Concrete type */ Ty<'tcx>, /* Object type */ Ty<'tcx>), + + /// Obligation incurred due to a coercion. + Coercion { + source: Ty<'tcx>, + target: Ty<'tcx>, + }, + + /// Various cases where expressions must be `Sized` / `Copy` / etc. + /// `L = X` implies that `L` is `Sized`. + AssignmentLhsSized, + /// `(x1, .., xn)` must be `Sized`. + TupleInitializerSized, + /// `S { ... }` must be `Sized`. + StructInitializerSized, + /// Type of each variable must be `Sized`. + VariableType(hir::HirId), + /// Argument type must be `Sized`. + SizedArgumentType(Option), + /// Return type must be `Sized`. + SizedReturnType, + /// Yield type must be `Sized`. + SizedYieldType, + /// Box expression result type must be `Sized`. + SizedBoxType, + /// Inline asm operand type must be `Sized`. + InlineAsmSized, + /// `[expr; N]` requires `type_of(expr): Copy`. + RepeatElementCopy { + /// If element is a `const fn` we display a help message suggesting to move the + /// function call to a new `const` item while saying that `T` doesn't implement `Copy`. + is_const_fn: bool, + }, + + /// Types of fields (other than the last, except for packed structs) in a struct must be sized. + FieldSized { + adt_kind: AdtKind, + span: Span, + last: bool, + }, + + /// Constant expressions must be sized. + ConstSized, + + /// `static` items must have `Sync` type. + SharedStatic, + + BuiltinDerivedObligation(DerivedObligationCause<'tcx>), + + ImplDerivedObligation(Box>), + + DerivedObligation(DerivedObligationCause<'tcx>), + + FunctionArgumentObligation { + /// The node of the relevant argument in the function call. + arg_hir_id: hir::HirId, + /// The node of the function call. + call_hir_id: hir::HirId, + /// The obligation introduced by this argument. + parent_code: InternedObligationCauseCode<'tcx>, + }, + + /// Error derived when matching traits/impls; see ObligationCause for more details + CompareImplItemObligation { + impl_item_def_id: LocalDefId, + trait_item_def_id: DefId, + kind: ty::AssocKind, + }, + + /// Checking that the bounds of a trait's associated type hold for a given impl + CheckAssociatedTypeBounds { + impl_item_def_id: LocalDefId, + trait_item_def_id: DefId, + }, + + /// Checking that this expression can be assigned to its target. + ExprAssignable, + + /// Computing common supertype in the arms of a match expression + MatchExpressionArm(Box>), + + /// Type error arising from type checking a pattern against an expected type. + Pattern { + /// The span of the scrutinee or type expression which caused the `root_ty` type. + span: Option, + /// The root expected type induced by a scrutinee or type expression. + root_ty: Ty<'tcx>, + /// Whether the `Span` came from an expression or a type expression. + origin_expr: bool, + }, + + /// Constants in patterns must have `Structural` type. + ConstPatternStructural, + + /// Computing common supertype in an if expression + IfExpression(Box>), + + /// Computing common supertype of an if expression with no else counter-part + IfExpressionWithNoElse, + + /// `main` has wrong type + MainFunctionType, + + /// `start` has wrong type + StartFunctionType, + + /// Intrinsic has wrong type + IntrinsicType, + + /// A let else block does not diverge + LetElse, + + /// Method receiver + MethodReceiver, + + UnifyReceiver(Box>), + + /// `return` with no expression + ReturnNoExpression, + + /// `return` with an expression + ReturnValue(hir::HirId), + + /// Return type of this function + ReturnType, + + /// Opaque return type of this function + OpaqueReturnType(Option<(Ty<'tcx>, Span)>), + + /// Block implicit return + BlockTailExpression(hir::HirId), + + /// #[feature(trivial_bounds)] is not enabled + TrivialBound, + + /// If `X` is the concrete type of an opaque type `impl Y`, then `X` must implement `Y` + OpaqueType, + + AwaitableExpr(Option), + + ForLoopIterator, + + QuestionMark, + + /// Well-formed checking. If a `WellFormedLoc` is provided, + /// then it will be used to perform HIR-based wf checking + /// after an error occurs, in order to generate a more precise error span. + /// This is purely for diagnostic purposes - it is always + /// correct to use `MiscObligation` instead, or to specify + /// `WellFormed(None)` + WellFormed(Option), + + /// From `match_impl`. The cause for us having to match an impl, and the DefId we are matching against. + MatchImpl(ObligationCause<'tcx>, DefId), + + BinOp { + rhs_span: Option, + is_lit: bool, + output_pred: Option>, + }, +} + +/// The 'location' at which we try to perform HIR-based wf checking. +/// This information is used to obtain an `hir::Ty`, which +/// we can walk in order to obtain precise spans for any +/// 'nested' types (e.g. `Foo` in `Option`). +#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, HashStable)] +pub enum WellFormedLoc { + /// Use the type of the provided definition. + Ty(LocalDefId), + /// Use the type of the parameter of the provided function. + /// We cannot use `hir::Param`, since the function may + /// not have a body (e.g. a trait method definition) + Param { + /// The function to lookup the parameter in + function: LocalDefId, + /// The index of the parameter to use. + /// Parameters are indexed from 0, with the return type + /// being the last 'parameter' + param_idx: u16, + }, +} + +#[derive(Clone, Debug, PartialEq, Eq, Hash, Lift)] +pub struct ImplDerivedObligationCause<'tcx> { + pub derived: DerivedObligationCause<'tcx>, + pub impl_def_id: DefId, + pub span: Span, +} + +impl<'tcx> ObligationCauseCode<'tcx> { + // Return the base obligation, ignoring derived obligations. + pub fn peel_derives(&self) -> &Self { + let mut base_cause = self; + while let Some((parent_code, _)) = base_cause.parent() { + base_cause = parent_code; + } + base_cause + } + + pub fn parent(&self) -> Option<(&Self, Option>)> { + match self { + FunctionArgumentObligation { parent_code, .. } => Some((parent_code, None)), + BuiltinDerivedObligation(derived) + | DerivedObligation(derived) + | ImplDerivedObligation(box ImplDerivedObligationCause { derived, .. }) => { + Some((&derived.parent_code, Some(derived.parent_trait_pred))) + } + _ => None, + } + } +} + +// `ObligationCauseCode` 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!(ObligationCauseCode<'_>, 48); + +#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)] +pub enum StatementAsExpression { + CorrectType, + NeedsBoxing, +} + +impl<'tcx> ty::Lift<'tcx> for StatementAsExpression { + type Lifted = StatementAsExpression; + fn lift_to_tcx(self, _tcx: TyCtxt<'tcx>) -> Option { + Some(self) + } +} + +#[derive(Clone, Debug, PartialEq, Eq, Hash, Lift)] +pub struct MatchExpressionArmCause<'tcx> { + pub arm_block_id: Option, + pub arm_ty: Ty<'tcx>, + pub arm_span: Span, + pub prior_arm_block_id: Option, + pub prior_arm_ty: Ty<'tcx>, + pub prior_arm_span: Span, + pub scrut_span: Span, + pub source: hir::MatchSource, + pub prior_arms: Vec, + pub scrut_hir_id: hir::HirId, + pub opt_suggest_box_span: Option, +} + +#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)] +#[derive(Lift, TypeFoldable, TypeVisitable)] +pub struct IfExpressionCause<'tcx> { + pub then_id: hir::HirId, + pub else_id: hir::HirId, + pub then_ty: Ty<'tcx>, + pub else_ty: Ty<'tcx>, + pub outer_span: Option, + pub opt_suggest_box_span: Option, +} + +#[derive(Clone, Debug, PartialEq, Eq, Hash, Lift)] +pub struct DerivedObligationCause<'tcx> { + /// The trait predicate of the parent obligation that led to the + /// current obligation. Note that only trait obligations lead to + /// derived obligations, so we just store the trait predicate here + /// directly. + pub parent_trait_pred: ty::PolyTraitPredicate<'tcx>, + + /// The parent trait had this cause. + pub parent_code: InternedObligationCauseCode<'tcx>, +} + +#[derive(Clone, Debug, TypeFoldable, TypeVisitable, Lift)] +pub enum SelectionError<'tcx> { + /// The trait is not implemented. + Unimplemented, + /// After a closure impl has selected, its "outputs" were evaluated + /// (which for closures includes the "input" type params) and they + /// didn't resolve. See `confirm_poly_trait_refs` for more. + OutputTypeParameterMismatch( + ty::PolyTraitRef<'tcx>, + ty::PolyTraitRef<'tcx>, + ty::error::TypeError<'tcx>, + ), + /// The trait pointed by `DefId` is not object safe. + TraitNotObjectSafe(DefId), + /// A given constant couldn't be evaluated. + NotConstEvaluatable(NotConstEvaluatable), + /// Exceeded the recursion depth during type projection. + Overflow(OverflowError), + /// Signaling that an error has already been emitted, to avoid + /// multiple errors being shown. + ErrorReporting, + /// Multiple applicable `impl`s where found. The `DefId`s correspond to + /// all the `impl`s' Items. + Ambiguous(Vec), +} + +/// When performing resolution, it is typically the case that there +/// can be one of three outcomes: +/// +/// - `Ok(Some(r))`: success occurred with result `r` +/// - `Ok(None)`: could not definitely determine anything, usually due +/// to inconclusive type inference. +/// - `Err(e)`: error `e` occurred +pub type SelectionResult<'tcx, T> = Result, SelectionError<'tcx>>; + +/// Given the successful resolution of an obligation, the `ImplSource` +/// indicates where the impl comes from. +/// +/// For example, the obligation may be satisfied by a specific impl (case A), +/// or it may be relative to some bound that is in scope (case B). +/// +/// ```ignore (illustrative) +/// impl Clone for Option { ... } // Impl_1 +/// impl Clone for Box { ... } // Impl_2 +/// impl Clone for i32 { ... } // Impl_3 +/// +/// fn foo(concrete: Option>, param: T, mixed: Option) { +/// // Case A: ImplSource points at a specific impl. Only possible when +/// // type is concretely known. If the impl itself has bounded +/// // type parameters, ImplSource will carry resolutions for those as well: +/// concrete.clone(); // ImplSource(Impl_1, [ImplSource(Impl_2, [ImplSource(Impl_3)])]) +/// +/// // Case A: ImplSource points at a specific impl. Only possible when +/// // type is concretely known. If the impl itself has bounded +/// // type parameters, ImplSource will carry resolutions for those as well: +/// concrete.clone(); // ImplSource(Impl_1, [ImplSource(Impl_2, [ImplSource(Impl_3)])]) +/// +/// // Case B: ImplSource must be provided by caller. This applies when +/// // type is a type parameter. +/// param.clone(); // ImplSource::Param +/// +/// // Case C: A mix of cases A and B. +/// mixed.clone(); // ImplSource(Impl_1, [ImplSource::Param]) +/// } +/// ``` +/// +/// ### The type parameter `N` +/// +/// See explanation on `ImplSourceUserDefinedData`. +#[derive(Clone, PartialEq, Eq, TyEncodable, TyDecodable, HashStable, Lift)] +#[derive(TypeFoldable, TypeVisitable)] +pub enum ImplSource<'tcx, N> { + /// ImplSource identifying a particular impl. + UserDefined(ImplSourceUserDefinedData<'tcx, N>), + + /// ImplSource for auto trait implementations. + /// This carries the information and nested obligations with regards + /// to an auto implementation for a trait `Trait`. The nested obligations + /// ensure the trait implementation holds for all the constituent types. + AutoImpl(ImplSourceAutoImplData), + + /// Successful resolution to an obligation provided by the caller + /// for some type parameter. The `Vec` represents the + /// obligations incurred from normalizing the where-clause (if + /// any). + Param(Vec, ty::BoundConstness), + + /// Virtual calls through an object. + Object(ImplSourceObjectData<'tcx, N>), + + /// Successful resolution for a builtin trait. + Builtin(ImplSourceBuiltinData), + + /// ImplSource for trait upcasting coercion + TraitUpcasting(ImplSourceTraitUpcastingData<'tcx, N>), + + /// ImplSource automatically generated for a closure. The `DefId` is the ID + /// of the closure expression. This is an `ImplSource::UserDefined` in spirit, but the + /// impl is generated by the compiler and does not appear in the source. + Closure(ImplSourceClosureData<'tcx, N>), + + /// Same as above, but for a function pointer type with the given signature. + FnPointer(ImplSourceFnPointerData<'tcx, N>), + + /// ImplSource for a builtin `DeterminantKind` trait implementation. + DiscriminantKind(ImplSourceDiscriminantKindData), + + /// ImplSource for a builtin `Pointee` trait implementation. + Pointee(ImplSourcePointeeData), + + /// ImplSource automatically generated for a generator. + Generator(ImplSourceGeneratorData<'tcx, N>), + + /// ImplSource for a trait alias. + TraitAlias(ImplSourceTraitAliasData<'tcx, N>), + + /// ImplSource for a `const Drop` implementation. + ConstDestruct(ImplSourceConstDestructData), +} + +impl<'tcx, N> ImplSource<'tcx, N> { + pub fn nested_obligations(self) -> Vec { + match self { + ImplSource::UserDefined(i) => i.nested, + ImplSource::Param(n, _) => n, + ImplSource::Builtin(i) => i.nested, + ImplSource::AutoImpl(d) => d.nested, + ImplSource::Closure(c) => c.nested, + ImplSource::Generator(c) => c.nested, + ImplSource::Object(d) => d.nested, + ImplSource::FnPointer(d) => d.nested, + ImplSource::DiscriminantKind(ImplSourceDiscriminantKindData) + | ImplSource::Pointee(ImplSourcePointeeData) => Vec::new(), + ImplSource::TraitAlias(d) => d.nested, + ImplSource::TraitUpcasting(d) => d.nested, + ImplSource::ConstDestruct(i) => i.nested, + } + } + + pub fn borrow_nested_obligations(&self) -> &[N] { + match &self { + ImplSource::UserDefined(i) => &i.nested[..], + ImplSource::Param(n, _) => &n, + ImplSource::Builtin(i) => &i.nested, + ImplSource::AutoImpl(d) => &d.nested, + ImplSource::Closure(c) => &c.nested, + ImplSource::Generator(c) => &c.nested, + ImplSource::Object(d) => &d.nested, + ImplSource::FnPointer(d) => &d.nested, + ImplSource::DiscriminantKind(ImplSourceDiscriminantKindData) + | ImplSource::Pointee(ImplSourcePointeeData) => &[], + ImplSource::TraitAlias(d) => &d.nested, + ImplSource::TraitUpcasting(d) => &d.nested, + ImplSource::ConstDestruct(i) => &i.nested, + } + } + + pub fn map(self, f: F) -> ImplSource<'tcx, M> + where + F: FnMut(N) -> M, + { + match self { + ImplSource::UserDefined(i) => ImplSource::UserDefined(ImplSourceUserDefinedData { + impl_def_id: i.impl_def_id, + substs: i.substs, + nested: i.nested.into_iter().map(f).collect(), + }), + ImplSource::Param(n, ct) => ImplSource::Param(n.into_iter().map(f).collect(), ct), + ImplSource::Builtin(i) => ImplSource::Builtin(ImplSourceBuiltinData { + nested: i.nested.into_iter().map(f).collect(), + }), + ImplSource::Object(o) => ImplSource::Object(ImplSourceObjectData { + upcast_trait_ref: o.upcast_trait_ref, + vtable_base: o.vtable_base, + nested: o.nested.into_iter().map(f).collect(), + }), + ImplSource::AutoImpl(d) => ImplSource::AutoImpl(ImplSourceAutoImplData { + trait_def_id: d.trait_def_id, + nested: d.nested.into_iter().map(f).collect(), + }), + ImplSource::Closure(c) => ImplSource::Closure(ImplSourceClosureData { + closure_def_id: c.closure_def_id, + substs: c.substs, + nested: c.nested.into_iter().map(f).collect(), + }), + ImplSource::Generator(c) => ImplSource::Generator(ImplSourceGeneratorData { + generator_def_id: c.generator_def_id, + substs: c.substs, + nested: c.nested.into_iter().map(f).collect(), + }), + ImplSource::FnPointer(p) => ImplSource::FnPointer(ImplSourceFnPointerData { + fn_ty: p.fn_ty, + nested: p.nested.into_iter().map(f).collect(), + }), + ImplSource::DiscriminantKind(ImplSourceDiscriminantKindData) => { + ImplSource::DiscriminantKind(ImplSourceDiscriminantKindData) + } + ImplSource::Pointee(ImplSourcePointeeData) => { + ImplSource::Pointee(ImplSourcePointeeData) + } + ImplSource::TraitAlias(d) => ImplSource::TraitAlias(ImplSourceTraitAliasData { + alias_def_id: d.alias_def_id, + substs: d.substs, + nested: d.nested.into_iter().map(f).collect(), + }), + ImplSource::TraitUpcasting(d) => { + ImplSource::TraitUpcasting(ImplSourceTraitUpcastingData { + upcast_trait_ref: d.upcast_trait_ref, + vtable_vptr_slot: d.vtable_vptr_slot, + nested: d.nested.into_iter().map(f).collect(), + }) + } + ImplSource::ConstDestruct(i) => { + ImplSource::ConstDestruct(ImplSourceConstDestructData { + nested: i.nested.into_iter().map(f).collect(), + }) + } + } + } +} + +/// Identifies a particular impl in the source, along with a set of +/// substitutions from the impl's type/lifetime parameters. The +/// `nested` vector corresponds to the nested obligations attached to +/// the impl's type parameters. +/// +/// The type parameter `N` indicates the type used for "nested +/// obligations" that are required by the impl. During type-check, this +/// is `Obligation`, as one might expect. During codegen, however, this +/// is `()`, because codegen only requires a shallow resolution of an +/// impl, and nested obligations are satisfied later. +#[derive(Clone, PartialEq, Eq, TyEncodable, TyDecodable, HashStable, Lift)] +#[derive(TypeFoldable, TypeVisitable)] +pub struct ImplSourceUserDefinedData<'tcx, N> { + pub impl_def_id: DefId, + pub substs: SubstsRef<'tcx>, + pub nested: Vec, +} + +#[derive(Clone, PartialEq, Eq, TyEncodable, TyDecodable, HashStable, Lift)] +#[derive(TypeFoldable, TypeVisitable)] +pub struct ImplSourceGeneratorData<'tcx, N> { + pub generator_def_id: DefId, + pub substs: SubstsRef<'tcx>, + /// Nested obligations. This can be non-empty if the generator + /// signature contains associated types. + pub nested: Vec, +} + +#[derive(Clone, PartialEq, Eq, TyEncodable, TyDecodable, HashStable, Lift)] +#[derive(TypeFoldable, TypeVisitable)] +pub struct ImplSourceClosureData<'tcx, N> { + pub closure_def_id: DefId, + pub substs: SubstsRef<'tcx>, + /// Nested obligations. This can be non-empty if the closure + /// signature contains associated types. + pub nested: Vec, +} + +#[derive(Clone, PartialEq, Eq, TyEncodable, TyDecodable, HashStable, Lift)] +#[derive(TypeFoldable, TypeVisitable)] +pub struct ImplSourceAutoImplData { + pub trait_def_id: DefId, + pub nested: Vec, +} + +#[derive(Clone, PartialEq, Eq, TyEncodable, TyDecodable, HashStable, Lift)] +#[derive(TypeFoldable, TypeVisitable)] +pub struct ImplSourceTraitUpcastingData<'tcx, N> { + /// `Foo` upcast to the obligation trait. This will be some supertrait of `Foo`. + pub upcast_trait_ref: ty::PolyTraitRef<'tcx>, + + /// The vtable is formed by concatenating together the method lists of + /// the base object trait and all supertraits, pointers to supertrait vtable will + /// be provided when necessary; this is the position of `upcast_trait_ref`'s vtable + /// within that vtable. + pub vtable_vptr_slot: Option, + + pub nested: Vec, +} + +#[derive(Clone, PartialEq, Eq, TyEncodable, TyDecodable, HashStable, Lift)] +#[derive(TypeFoldable, TypeVisitable)] +pub struct ImplSourceBuiltinData { + pub nested: Vec, +} + +#[derive(PartialEq, Eq, Clone, TyEncodable, TyDecodable, HashStable, Lift)] +#[derive(TypeFoldable, TypeVisitable)] +pub struct ImplSourceObjectData<'tcx, N> { + /// `Foo` upcast to the obligation trait. This will be some supertrait of `Foo`. + pub upcast_trait_ref: ty::PolyTraitRef<'tcx>, + + /// The vtable is formed by concatenating together the method lists of + /// the base object trait and all supertraits, pointers to supertrait vtable will + /// be provided when necessary; this is the start of `upcast_trait_ref`'s methods + /// in that vtable. + pub vtable_base: usize, + + pub nested: Vec, +} + +#[derive(Clone, PartialEq, Eq, TyEncodable, TyDecodable, HashStable, Lift)] +#[derive(TypeFoldable, TypeVisitable)] +pub struct ImplSourceFnPointerData<'tcx, N> { + pub fn_ty: Ty<'tcx>, + pub nested: Vec, +} + +// FIXME(@lcnr): This should be refactored and merged with other builtin vtables. +#[derive(Clone, Debug, PartialEq, Eq, TyEncodable, TyDecodable, HashStable)] +pub struct ImplSourceDiscriminantKindData; + +#[derive(Clone, Debug, PartialEq, Eq, TyEncodable, TyDecodable, HashStable)] +pub struct ImplSourcePointeeData; + +#[derive(Clone, PartialEq, Eq, TyEncodable, TyDecodable, HashStable, Lift)] +#[derive(TypeFoldable, TypeVisitable)] +pub struct ImplSourceConstDestructData { + pub nested: Vec, +} + +#[derive(Clone, PartialEq, Eq, TyEncodable, TyDecodable, HashStable, Lift)] +#[derive(TypeFoldable, TypeVisitable)] +pub struct ImplSourceTraitAliasData<'tcx, N> { + pub alias_def_id: DefId, + pub substs: SubstsRef<'tcx>, + pub nested: Vec, +} + +#[derive(Clone, Debug, PartialEq, Eq, Hash, HashStable, PartialOrd, Ord)] +pub enum ObjectSafetyViolation { + /// `Self: Sized` declared on the trait. + SizedSelf(SmallVec<[Span; 1]>), + + /// Supertrait reference references `Self` an in illegal location + /// (e.g., `trait Foo : Bar`). + SupertraitSelf(SmallVec<[Span; 1]>), + + /// Method has something illegal. + Method(Symbol, MethodViolationCode, Span), + + /// Associated const. + AssocConst(Symbol, Span), + + /// GAT + GAT(Symbol, Span), +} + +impl ObjectSafetyViolation { + pub fn error_msg(&self) -> Cow<'static, str> { + match self { + ObjectSafetyViolation::SizedSelf(_) => "it requires `Self: Sized`".into(), + ObjectSafetyViolation::SupertraitSelf(ref spans) => { + if spans.iter().any(|sp| *sp != DUMMY_SP) { + "it uses `Self` as a type parameter".into() + } else { + "it cannot use `Self` as a type parameter in a supertrait or `where`-clause" + .into() + } + } + ObjectSafetyViolation::Method(name, MethodViolationCode::StaticMethod(_), _) => { + format!("associated function `{}` has no `self` parameter", name).into() + } + ObjectSafetyViolation::Method( + name, + MethodViolationCode::ReferencesSelfInput(_), + DUMMY_SP, + ) => format!("method `{}` references the `Self` type in its parameters", name).into(), + ObjectSafetyViolation::Method(name, MethodViolationCode::ReferencesSelfInput(_), _) => { + format!("method `{}` references the `Self` type in this parameter", name).into() + } + ObjectSafetyViolation::Method(name, MethodViolationCode::ReferencesSelfOutput, _) => { + format!("method `{}` references the `Self` type in its return type", name).into() + } + ObjectSafetyViolation::Method( + name, + MethodViolationCode::WhereClauseReferencesSelf, + _, + ) => { + format!("method `{}` references the `Self` type in its `where` clause", name).into() + } + ObjectSafetyViolation::Method(name, MethodViolationCode::Generic, _) => { + format!("method `{}` has generic type parameters", name).into() + } + ObjectSafetyViolation::Method( + name, + MethodViolationCode::UndispatchableReceiver(_), + _, + ) => format!("method `{}`'s `self` parameter cannot be dispatched on", name).into(), + ObjectSafetyViolation::AssocConst(name, DUMMY_SP) => { + format!("it contains associated `const` `{}`", name).into() + } + ObjectSafetyViolation::AssocConst(..) => "it contains this associated `const`".into(), + ObjectSafetyViolation::GAT(name, _) => { + format!("it contains the generic associated type `{}`", name).into() + } + } + } + + pub fn solution(&self, err: &mut Diagnostic) { + match self { + ObjectSafetyViolation::SizedSelf(_) | ObjectSafetyViolation::SupertraitSelf(_) => {} + ObjectSafetyViolation::Method( + name, + MethodViolationCode::StaticMethod(Some((add_self_sugg, make_sized_sugg))), + _, + ) => { + err.span_suggestion( + add_self_sugg.1, + format!( + "consider turning `{}` into a method by giving it a `&self` argument", + name + ), + add_self_sugg.0.to_string(), + Applicability::MaybeIncorrect, + ); + err.span_suggestion( + make_sized_sugg.1, + format!( + "alternatively, consider constraining `{}` so it does not apply to \ + trait objects", + name + ), + make_sized_sugg.0.to_string(), + Applicability::MaybeIncorrect, + ); + } + ObjectSafetyViolation::Method( + name, + MethodViolationCode::UndispatchableReceiver(Some(span)), + _, + ) => { + err.span_suggestion( + *span, + &format!( + "consider changing method `{}`'s `self` parameter to be `&self`", + name + ), + "&Self", + Applicability::MachineApplicable, + ); + } + ObjectSafetyViolation::AssocConst(name, _) + | ObjectSafetyViolation::GAT(name, _) + | ObjectSafetyViolation::Method(name, ..) => { + err.help(&format!("consider moving `{}` to another trait", name)); + } + } + } + + pub fn spans(&self) -> SmallVec<[Span; 1]> { + // When `span` comes from a separate crate, it'll be `DUMMY_SP`. Treat it as `None` so + // diagnostics use a `note` instead of a `span_label`. + match self { + ObjectSafetyViolation::SupertraitSelf(spans) + | ObjectSafetyViolation::SizedSelf(spans) => spans.clone(), + ObjectSafetyViolation::AssocConst(_, span) + | ObjectSafetyViolation::GAT(_, span) + | ObjectSafetyViolation::Method(_, _, span) + if *span != DUMMY_SP => + { + smallvec![*span] + } + _ => smallvec![], + } + } +} + +/// Reasons a method might not be object-safe. +#[derive(Clone, Debug, PartialEq, Eq, Hash, HashStable, PartialOrd, Ord)] +pub enum MethodViolationCode { + /// e.g., `fn foo()` + StaticMethod(Option<(/* add &self */ (String, Span), /* add Self: Sized */ (String, Span))>), + + /// e.g., `fn foo(&self, x: Self)` + ReferencesSelfInput(Option), + + /// e.g., `fn foo(&self) -> Self` + ReferencesSelfOutput, + + /// e.g., `fn foo(&self) where Self: Clone` + WhereClauseReferencesSelf, + + /// e.g., `fn foo()` + Generic, + + /// the method's receiver (`self` argument) can't be dispatched on + UndispatchableReceiver(Option), +} + +/// These are the error cases for `codegen_fulfill_obligation`. +#[derive(Copy, Clone, Debug, Hash, HashStable, Encodable, Decodable)] +pub enum CodegenObligationError { + /// Ambiguity can happen when monomorphizing during trans + /// expands to some humongous type that never occurred + /// statically -- this humongous type can then overflow, + /// leading to an ambiguous result. So report this as an + /// overflow bug, since I believe this is the only case + /// where ambiguity can result. + Ambiguity, + /// This can trigger when we probe for the source of a `'static` lifetime requirement + /// on a trait object: `impl Foo for dyn Trait {}` has an implicit `'static` bound. + /// This can also trigger when we have a global bound that is not actually satisfied, + /// but was included during typeck due to the trivial_bounds feature. + Unimplemented, + FulfillmentError, +} diff --git a/compiler/rustc_middle/src/traits/query.rs b/compiler/rustc_middle/src/traits/query.rs new file mode 100644 index 000000000..1f9b474ad --- /dev/null +++ b/compiler/rustc_middle/src/traits/query.rs @@ -0,0 +1,230 @@ +//! Experimental types for the trait query interface. The methods +//! defined in this module are all based on **canonicalization**, +//! which makes a canonical query by replacing unbound inference +//! variables and regions, so that results can be reused more broadly. +//! The providers for the queries defined here can be found in +//! `rustc_traits`. + +use crate::infer::canonical::{Canonical, QueryResponse}; +use crate::ty::error::TypeError; +use crate::ty::subst::GenericArg; +use crate::ty::{self, Ty, TyCtxt}; +use rustc_errors::struct_span_err; +use rustc_span::source_map::Span; +use std::iter::FromIterator; + +pub mod type_op { + use crate::ty::fold::TypeFoldable; + use crate::ty::subst::UserSubsts; + use crate::ty::{Predicate, Ty}; + use rustc_hir::def_id::DefId; + use std::fmt; + + #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, HashStable, Lift)] + #[derive(TypeFoldable, TypeVisitable)] + pub struct AscribeUserType<'tcx> { + pub mir_ty: Ty<'tcx>, + pub def_id: DefId, + pub user_substs: UserSubsts<'tcx>, + } + + impl<'tcx> AscribeUserType<'tcx> { + pub fn new(mir_ty: Ty<'tcx>, def_id: DefId, user_substs: UserSubsts<'tcx>) -> Self { + Self { mir_ty, def_id, user_substs } + } + } + + #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, HashStable, Lift)] + #[derive(TypeFoldable, TypeVisitable)] + pub struct Eq<'tcx> { + pub a: Ty<'tcx>, + pub b: Ty<'tcx>, + } + + #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, HashStable, Lift)] + #[derive(TypeFoldable, TypeVisitable)] + pub struct Subtype<'tcx> { + pub sub: Ty<'tcx>, + pub sup: Ty<'tcx>, + } + + #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, HashStable, Lift)] + #[derive(TypeFoldable, TypeVisitable)] + pub struct ProvePredicate<'tcx> { + pub predicate: Predicate<'tcx>, + } + + impl<'tcx> ProvePredicate<'tcx> { + pub fn new(predicate: Predicate<'tcx>) -> Self { + ProvePredicate { predicate } + } + } + + #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, HashStable, Lift)] + #[derive(TypeFoldable, TypeVisitable)] + pub struct Normalize { + pub value: T, + } + + impl<'tcx, T> Normalize + where + T: fmt::Debug + TypeFoldable<'tcx>, + { + pub fn new(value: T) -> Self { + Self { value } + } + } +} + +pub type CanonicalProjectionGoal<'tcx> = + Canonical<'tcx, ty::ParamEnvAnd<'tcx, ty::ProjectionTy<'tcx>>>; + +pub type CanonicalTyGoal<'tcx> = Canonical<'tcx, ty::ParamEnvAnd<'tcx, Ty<'tcx>>>; + +pub type CanonicalPredicateGoal<'tcx> = Canonical<'tcx, ty::ParamEnvAnd<'tcx, ty::Predicate<'tcx>>>; + +pub type CanonicalTypeOpAscribeUserTypeGoal<'tcx> = + Canonical<'tcx, ty::ParamEnvAnd<'tcx, type_op::AscribeUserType<'tcx>>>; + +pub type CanonicalTypeOpEqGoal<'tcx> = Canonical<'tcx, ty::ParamEnvAnd<'tcx, type_op::Eq<'tcx>>>; + +pub type CanonicalTypeOpSubtypeGoal<'tcx> = + Canonical<'tcx, ty::ParamEnvAnd<'tcx, type_op::Subtype<'tcx>>>; + +pub type CanonicalTypeOpProvePredicateGoal<'tcx> = + Canonical<'tcx, ty::ParamEnvAnd<'tcx, type_op::ProvePredicate<'tcx>>>; + +pub type CanonicalTypeOpNormalizeGoal<'tcx, T> = + Canonical<'tcx, ty::ParamEnvAnd<'tcx, type_op::Normalize>>; + +#[derive(Copy, Clone, Debug, HashStable)] +pub struct NoSolution; + +pub type Fallible = Result; + +impl<'tcx> From> for NoSolution { + fn from(_: TypeError<'tcx>) -> NoSolution { + NoSolution + } +} + +#[derive(Clone, Debug, Default, HashStable, TypeFoldable, TypeVisitable, Lift)] +pub struct DropckOutlivesResult<'tcx> { + pub kinds: Vec>, + pub overflows: Vec>, +} + +impl<'tcx> DropckOutlivesResult<'tcx> { + pub fn report_overflows(&self, tcx: TyCtxt<'tcx>, span: Span, ty: Ty<'tcx>) { + if let Some(overflow_ty) = self.overflows.get(0) { + let mut err = struct_span_err!( + tcx.sess, + span, + E0320, + "overflow while adding drop-check rules for {}", + ty, + ); + err.note(&format!("overflowed on {}", overflow_ty)); + err.emit(); + } + } + + pub fn into_kinds_reporting_overflows( + self, + tcx: TyCtxt<'tcx>, + span: Span, + ty: Ty<'tcx>, + ) -> Vec> { + self.report_overflows(tcx, span, ty); + let DropckOutlivesResult { kinds, overflows: _ } = self; + kinds + } +} + +/// A set of constraints that need to be satisfied in order for +/// a type to be valid for destruction. +#[derive(Clone, Debug, HashStable)] +pub struct DropckConstraint<'tcx> { + /// Types that are required to be alive in order for this + /// type to be valid for destruction. + pub outlives: Vec>, + + /// Types that could not be resolved: projections and params. + pub dtorck_types: Vec>, + + /// If, during the computation of the dtorck constraint, we + /// overflow, that gets recorded here. The caller is expected to + /// report an error. + pub overflows: Vec>, +} + +impl<'tcx> DropckConstraint<'tcx> { + pub fn empty() -> DropckConstraint<'tcx> { + DropckConstraint { outlives: vec![], dtorck_types: vec![], overflows: vec![] } + } +} + +impl<'tcx> FromIterator> for DropckConstraint<'tcx> { + fn from_iter>>(iter: I) -> Self { + let mut result = Self::empty(); + + for DropckConstraint { outlives, dtorck_types, overflows } in iter { + result.outlives.extend(outlives); + result.dtorck_types.extend(dtorck_types); + result.overflows.extend(overflows); + } + + result + } +} + +#[derive(Debug, HashStable)] +pub struct CandidateStep<'tcx> { + pub self_ty: Canonical<'tcx, QueryResponse<'tcx, Ty<'tcx>>>, + pub autoderefs: usize, + /// `true` if the type results from a dereference of a raw pointer. + /// when assembling candidates, we include these steps, but not when + /// picking methods. This so that if we have `foo: *const Foo` and `Foo` has methods + /// `fn by_raw_ptr(self: *const Self)` and `fn by_ref(&self)`, then + /// `foo.by_raw_ptr()` will work and `foo.by_ref()` won't. + pub from_unsafe_deref: bool, + pub unsize: bool, +} + +#[derive(Copy, Clone, Debug, HashStable)] +pub struct MethodAutoderefStepsResult<'tcx> { + /// The valid autoderef steps that could be find. + pub steps: &'tcx [CandidateStep<'tcx>], + /// If Some(T), a type autoderef reported an error on. + pub opt_bad_ty: Option<&'tcx MethodAutoderefBadTy<'tcx>>, + /// If `true`, `steps` has been truncated due to reaching the + /// recursion limit. + pub reached_recursion_limit: bool, +} + +#[derive(Debug, HashStable)] +pub struct MethodAutoderefBadTy<'tcx> { + pub reached_raw_pointer: bool, + pub ty: Canonical<'tcx, QueryResponse<'tcx, Ty<'tcx>>>, +} + +/// Result from the `normalize_projection_ty` query. +#[derive(Clone, Debug, HashStable, TypeFoldable, TypeVisitable, Lift)] +pub struct NormalizationResult<'tcx> { + /// Result of normalization. + pub normalized_ty: Ty<'tcx>, +} + +/// Outlives bounds are relationships between generic parameters, +/// whether they both be regions (`'a: 'b`) or whether types are +/// involved (`T: 'a`). These relationships can be extracted from the +/// full set of predicates we understand or also from types (in which +/// case they are called implied bounds). They are fed to the +/// `OutlivesEnv` which in turn is supplied to the region checker and +/// other parts of the inference system. +#[derive(Clone, Debug, TypeFoldable, TypeVisitable, Lift, HashStable)] +pub enum OutlivesBound<'tcx> { + RegionSubRegion(ty::Region<'tcx>, ty::Region<'tcx>), + RegionSubParam(ty::Region<'tcx>, ty::ParamTy), + RegionSubProjection(ty::Region<'tcx>, ty::ProjectionTy<'tcx>), +} diff --git a/compiler/rustc_middle/src/traits/select.rs b/compiler/rustc_middle/src/traits/select.rs new file mode 100644 index 000000000..e836ba47e --- /dev/null +++ b/compiler/rustc_middle/src/traits/select.rs @@ -0,0 +1,312 @@ +//! Candidate selection. 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#selection + +use self::EvaluationResult::*; + +use super::{SelectionError, SelectionResult}; +use rustc_errors::ErrorGuaranteed; + +use crate::ty; + +use rustc_hir::def_id::DefId; +use rustc_query_system::cache::Cache; + +pub type SelectionCache<'tcx> = Cache< + // This cache does not use `ParamEnvAnd` in its keys because `ParamEnv::and` can replace + // caller bounds with an empty list if the `TraitPredicate` looks global, which may happen + // after erasing lifetimes from the predicate. + (ty::ParamEnv<'tcx>, ty::TraitPredicate<'tcx>), + SelectionResult<'tcx, SelectionCandidate<'tcx>>, +>; + +pub type EvaluationCache<'tcx> = Cache< + // See above: this cache does not use `ParamEnvAnd` in its keys due to sometimes incorrectly + // caching with the wrong `ParamEnv`. + (ty::ParamEnv<'tcx>, ty::PolyTraitPredicate<'tcx>), + EvaluationResult, +>; + +/// The selection process begins by considering all impls, where +/// clauses, and so forth that might resolve an obligation. Sometimes +/// we'll be able to say definitively that (e.g.) an impl does not +/// apply to the obligation: perhaps it is defined for `usize` but the +/// obligation is for `i32`. In that case, we drop the impl out of the +/// list. But the other cases are considered *candidates*. +/// +/// For selection to succeed, there must be exactly one matching +/// candidate. If the obligation is fully known, this is guaranteed +/// by coherence. However, if the obligation contains type parameters +/// or variables, there may be multiple such impls. +/// +/// It is not a real problem if multiple matching impls exist because +/// of type variables - it just means the obligation isn't sufficiently +/// elaborated. In that case we report an ambiguity, and the caller can +/// try again after more type information has been gathered or report a +/// "type annotations needed" error. +/// +/// However, with type parameters, this can be a real problem - type +/// parameters don't unify with regular types, but they *can* unify +/// with variables from blanket impls, and (unless we know its bounds +/// will always be satisfied) picking the blanket impl will be wrong +/// for at least *some* substitutions. To make this concrete, if we have +/// +/// ```rust, ignore +/// trait AsDebug { type Out: fmt::Debug; fn debug(self) -> Self::Out; } +/// impl AsDebug for T { +/// type Out = T; +/// fn debug(self) -> fmt::Debug { self } +/// } +/// fn foo(t: T) { println!("{:?}", ::debug(t)); } +/// ``` +/// +/// we can't just use the impl to resolve the `` obligation +/// -- a type from another crate (that doesn't implement `fmt::Debug`) could +/// implement `AsDebug`. +/// +/// Because where-clauses match the type exactly, multiple clauses can +/// only match if there are unresolved variables, and we can mostly just +/// report this ambiguity in that case. This is still a problem - we can't +/// *do anything* with ambiguities that involve only regions. This is issue +/// #21974. +/// +/// If a single where-clause matches and there are no inference +/// variables left, then it definitely matches and we can just select +/// it. +/// +/// In fact, we even select the where-clause when the obligation contains +/// inference variables. The can lead to inference making "leaps of logic", +/// for example in this situation: +/// +/// ```rust, ignore +/// pub trait Foo { fn foo(&self) -> T; } +/// impl Foo<()> for T { fn foo(&self) { } } +/// impl Foo for bool { fn foo(&self) -> bool { *self } } +/// +/// pub fn foo(t: T) where T: Foo { +/// println!("{:?}", >::foo(&t)); +/// } +/// fn main() { foo(false); } +/// ``` +/// +/// Here the obligation `>` can be matched by both the blanket +/// impl and the where-clause. We select the where-clause and unify `$0=bool`, +/// so the program prints "false". However, if the where-clause is omitted, +/// the blanket impl is selected, we unify `$0=()`, and the program prints +/// "()". +/// +/// Exactly the same issues apply to projection and object candidates, except +/// that we can have both a projection candidate and a where-clause candidate +/// for the same obligation. In that case either would do (except that +/// different "leaps of logic" would occur if inference variables are +/// present), and we just pick the where-clause. This is, for example, +/// required for associated types to work in default impls, as the bounds +/// are visible both as projection bounds and as where-clauses from the +/// parameter environment. +#[derive(PartialEq, Eq, Debug, Clone, TypeFoldable, TypeVisitable)] +pub enum SelectionCandidate<'tcx> { + BuiltinCandidate { + /// `false` if there are no *further* obligations. + has_nested: bool, + }, + + /// Implementation of transmutability trait. + TransmutabilityCandidate, + + ParamCandidate(ty::PolyTraitPredicate<'tcx>), + ImplCandidate(DefId), + AutoImplCandidate(DefId), + + /// This is a trait matching with a projected type as `Self`, and we found + /// an applicable bound in the trait definition. The `usize` is an index + /// into the list returned by `tcx.item_bounds`. + ProjectionCandidate(usize), + + /// Implementation of a `Fn`-family trait by one of the anonymous types + /// generated for an `||` expression. + ClosureCandidate, + + /// Implementation of a `Generator` trait by one of the anonymous types + /// generated for a generator. + GeneratorCandidate, + + /// Implementation of a `Fn`-family trait by one of the anonymous + /// types generated for a fn pointer type (e.g., `fn(int) -> int`) + FnPointerCandidate { + is_const: bool, + }, + + /// Builtin implementation of `DiscriminantKind`. + DiscriminantKindCandidate, + + /// Builtin implementation of `Pointee`. + PointeeCandidate, + + TraitAliasCandidate(DefId), + + /// Matching `dyn Trait` with a supertrait of `Trait`. The index is the + /// position in the iterator returned by + /// `rustc_infer::traits::util::supertraits`. + ObjectCandidate(usize), + + /// Perform trait upcasting coercion of `dyn Trait` to a supertrait of `Trait`. + /// The index is the position in the iterator returned by + /// `rustc_infer::traits::util::supertraits`. + TraitUpcastingUnsizeCandidate(usize), + + BuiltinObjectCandidate, + + BuiltinUnsizeCandidate, + + /// Implementation of `const Destruct`, optionally from a custom `impl const Drop`. + ConstDestructCandidate(Option), +} + +/// The result of trait evaluation. The order is important +/// here as the evaluation of a list is the maximum of the +/// evaluations. +/// +/// The evaluation results are ordered: +/// - `EvaluatedToOk` implies `EvaluatedToOkModuloRegions` +/// implies `EvaluatedToAmbig` implies `EvaluatedToUnknown` +/// - `EvaluatedToErr` implies `EvaluatedToRecur` +/// - the "union" of evaluation results is equal to their maximum - +/// all the "potential success" candidates can potentially succeed, +/// so they are noops when unioned with a definite error, and within +/// the categories it's easy to see that the unions are correct. +#[derive(Copy, Clone, Debug, PartialOrd, Ord, PartialEq, Eq, HashStable)] +pub enum EvaluationResult { + /// Evaluation successful. + EvaluatedToOk, + /// Evaluation successful, but there were unevaluated region obligations. + EvaluatedToOkModuloRegions, + /// Evaluation successful, but need to rerun because opaque types got + /// hidden types assigned without it being known whether the opaque types + /// are within their defining scope + EvaluatedToOkModuloOpaqueTypes, + /// Evaluation is known to be ambiguous -- it *might* hold for some + /// assignment of inference variables, but it might not. + /// + /// While this has the same meaning as `EvaluatedToUnknown` -- we can't + /// know whether this obligation holds or not -- it is the result we + /// would get with an empty stack, and therefore is cacheable. + EvaluatedToAmbig, + /// Evaluation failed because of recursion involving inference + /// variables. We are somewhat imprecise there, so we don't actually + /// know the real result. + /// + /// This can't be trivially cached for the same reason as `EvaluatedToRecur`. + EvaluatedToUnknown, + /// Evaluation failed because we encountered an obligation we are already + /// trying to prove on this branch. + /// + /// We know this branch can't be a part of a minimal proof-tree for + /// the "root" of our cycle, because then we could cut out the recursion + /// and maintain a valid proof tree. However, this does not mean + /// that all the obligations on this branch do not hold -- it's possible + /// that we entered this branch "speculatively", and that there + /// might be some other way to prove this obligation that does not + /// go through this cycle -- so we can't cache this as a failure. + /// + /// For example, suppose we have this: + /// + /// ```rust,ignore (pseudo-Rust) + /// pub trait Trait { fn xyz(); } + /// // This impl is "useless", but we can still have + /// // an `impl Trait for SomeUnsizedType` somewhere. + /// impl Trait for T { fn xyz() {} } + /// + /// pub fn foo() { + /// ::xyz(); + /// } + /// ``` + /// + /// When checking `foo`, we have to prove `T: Trait`. This basically + /// translates into this: + /// + /// ```plain,ignore + /// (T: Trait + Sized →_\impl T: Trait), T: Trait ⊢ T: Trait + /// ``` + /// + /// When we try to prove it, we first go the first option, which + /// recurses. This shows us that the impl is "useless" -- it won't + /// tell us that `T: Trait` unless it already implemented `Trait` + /// by some other means. However, that does not prevent `T: Trait` + /// does not hold, because of the bound (which can indeed be satisfied + /// by `SomeUnsizedType` from another crate). + // + // FIXME: when an `EvaluatedToRecur` goes past its parent root, we + // ought to convert it to an `EvaluatedToErr`, because we know + // there definitely isn't a proof tree for that obligation. Not + // doing so is still sound -- there isn't any proof tree, so the + // branch still can't be a part of a minimal one -- but does not re-enable caching. + EvaluatedToRecur, + /// Evaluation failed. + EvaluatedToErr, +} + +impl EvaluationResult { + /// Returns `true` if this evaluation result is known to apply, even + /// considering outlives constraints. + pub fn must_apply_considering_regions(self) -> bool { + self == EvaluatedToOk + } + + /// Returns `true` if this evaluation result is known to apply, ignoring + /// outlives constraints. + pub fn must_apply_modulo_regions(self) -> bool { + self <= EvaluatedToOkModuloRegions + } + + pub fn may_apply(self) -> bool { + match self { + EvaluatedToOkModuloOpaqueTypes + | EvaluatedToOk + | EvaluatedToOkModuloRegions + | EvaluatedToAmbig + | EvaluatedToUnknown => true, + + EvaluatedToErr | EvaluatedToRecur => false, + } + } + + pub fn is_stack_dependent(self) -> bool { + match self { + EvaluatedToUnknown | EvaluatedToRecur => true, + + EvaluatedToOkModuloOpaqueTypes + | EvaluatedToOk + | EvaluatedToOkModuloRegions + | EvaluatedToAmbig + | EvaluatedToErr => false, + } + } +} + +/// Indicates that trait evaluation caused overflow and in which pass. +#[derive(Copy, Clone, Debug, PartialEq, Eq, HashStable)] +pub enum OverflowError { + Error(ErrorGuaranteed), + Canonical, + ErrorReporting, +} + +impl From for OverflowError { + fn from(e: ErrorGuaranteed) -> OverflowError { + OverflowError::Error(e) + } +} + +TrivialTypeTraversalAndLiftImpls! { + OverflowError, +} + +impl<'tcx> From for SelectionError<'tcx> { + fn from(overflow_error: OverflowError) -> SelectionError<'tcx> { + match overflow_error { + OverflowError::Error(e) => SelectionError::Overflow(OverflowError::Error(e)), + OverflowError::Canonical => SelectionError::Overflow(OverflowError::Canonical), + OverflowError::ErrorReporting => SelectionError::ErrorReporting, + } + } +} diff --git a/compiler/rustc_middle/src/traits/specialization_graph.rs b/compiler/rustc_middle/src/traits/specialization_graph.rs new file mode 100644 index 000000000..2465f8e25 --- /dev/null +++ b/compiler/rustc_middle/src/traits/specialization_graph.rs @@ -0,0 +1,261 @@ +use crate::ty::fast_reject::SimplifiedType; +use crate::ty::visit::TypeVisitable; +use crate::ty::{self, TyCtxt}; +use rustc_data_structures::fx::FxIndexMap; +use rustc_errors::ErrorGuaranteed; +use rustc_hir::def_id::{DefId, DefIdMap}; +use rustc_span::symbol::sym; + +/// A per-trait graph of impls in specialization order. At the moment, this +/// graph forms a tree rooted with the trait itself, with all other nodes +/// representing impls, and parent-child relationships representing +/// specializations. +/// +/// The graph provides two key services: +/// +/// - Construction. This implicitly checks for overlapping impls (i.e., impls +/// that overlap but where neither specializes the other -- an artifact of the +/// simple "chain" rule. +/// +/// - Parent extraction. In particular, the graph can give you the *immediate* +/// parents of a given specializing impl, which is needed for extracting +/// default items amongst other things. In the simple "chain" rule, every impl +/// has at most one parent. +#[derive(TyEncodable, TyDecodable, HashStable, Debug)] +pub struct Graph { + /// All impls have a parent; the "root" impls have as their parent the `def_id` + /// of the trait. + pub parent: DefIdMap, + + /// The "root" impls are found by looking up the trait's def_id. + pub children: DefIdMap, + + /// Whether an error was emitted while constructing the graph. + pub has_errored: Option, +} + +impl Graph { + pub fn new() -> Graph { + Graph { parent: Default::default(), children: Default::default(), has_errored: None } + } + + /// The parent of a given impl, which is the `DefId` of the trait when the + /// impl is a "specialization root". + pub fn parent(&self, child: DefId) -> DefId { + *self.parent.get(&child).unwrap_or_else(|| panic!("Failed to get parent for {:?}", child)) + } +} + +/// What kind of overlap check are we doing -- this exists just for testing and feature-gating +/// purposes. +#[derive(Copy, Clone, PartialEq, Eq, Hash, HashStable, Debug, TyEncodable, TyDecodable)] +pub enum OverlapMode { + /// The 1.0 rules (either types fail to unify, or where clauses are not implemented for crate-local types) + Stable, + /// Feature-gated test: Stable, *or* there is an explicit negative impl that rules out one of the where-clauses. + WithNegative, + /// Just check for negative impls, not for "where clause not implemented": used for testing. + Strict, +} + +impl OverlapMode { + pub fn get<'tcx>(tcx: TyCtxt<'tcx>, trait_id: DefId) -> OverlapMode { + let with_negative_coherence = tcx.features().with_negative_coherence; + let strict_coherence = tcx.has_attr(trait_id, sym::rustc_strict_coherence); + + if with_negative_coherence { + if strict_coherence { OverlapMode::Strict } else { OverlapMode::WithNegative } + } else if strict_coherence { + bug!("To use strict_coherence you need to set with_negative_coherence feature flag"); + } else { + OverlapMode::Stable + } + } + + pub fn use_negative_impl(&self) -> bool { + *self == OverlapMode::Strict || *self == OverlapMode::WithNegative + } + + pub fn use_implicit_negative(&self) -> bool { + *self == OverlapMode::Stable || *self == OverlapMode::WithNegative + } +} + +/// Children of a given impl, grouped into blanket/non-blanket varieties as is +/// done in `TraitDef`. +#[derive(Default, TyEncodable, TyDecodable, Debug, HashStable)] +pub struct Children { + // Impls of a trait (or specializations of a given impl). To allow for + // quicker lookup, the impls are indexed by a simplified version of their + // `Self` type: impls with a simplifiable `Self` are stored in + // `non_blanket_impls` keyed by it, while all other impls are stored in + // `blanket_impls`. + // + // A similar division is used within `TraitDef`, but the lists there collect + // together *all* the impls for a trait, and are populated prior to building + // the specialization graph. + /// Impls of the trait. + pub non_blanket_impls: FxIndexMap>, + + /// Blanket impls associated with the trait. + pub blanket_impls: Vec, +} + +/// A node in the specialization graph is either an impl or a trait +/// definition; either can serve as a source of item definitions. +/// There is always exactly one trait definition node: the root. +#[derive(Debug, Copy, Clone)] +pub enum Node { + Impl(DefId), + Trait(DefId), +} + +impl Node { + pub fn is_from_trait(&self) -> bool { + matches!(self, Node::Trait(..)) + } + + /// Trys to find the associated item that implements `trait_item_def_id` + /// defined in this node. + /// + /// If this returns `None`, the item can potentially still be found in + /// parents of this node. + pub fn item<'tcx>( + &self, + tcx: TyCtxt<'tcx>, + trait_item_def_id: DefId, + ) -> Option<&'tcx ty::AssocItem> { + match *self { + Node::Trait(_) => Some(tcx.associated_item(trait_item_def_id)), + Node::Impl(impl_def_id) => { + let id = tcx.impl_item_implementor_ids(impl_def_id).get(&trait_item_def_id)?; + Some(tcx.associated_item(*id)) + } + } + } + + pub fn def_id(&self) -> DefId { + match *self { + Node::Impl(did) => did, + Node::Trait(did) => did, + } + } +} + +#[derive(Copy, Clone)] +pub struct Ancestors<'tcx> { + trait_def_id: DefId, + specialization_graph: &'tcx Graph, + current_source: Option, +} + +impl Iterator for Ancestors<'_> { + type Item = Node; + fn next(&mut self) -> Option { + let cur = self.current_source.take(); + if let Some(Node::Impl(cur_impl)) = cur { + let parent = self.specialization_graph.parent(cur_impl); + + self.current_source = if parent == self.trait_def_id { + Some(Node::Trait(parent)) + } else { + Some(Node::Impl(parent)) + }; + } + cur + } +} + +/// Information about the most specialized definition of an associated item. +pub struct LeafDef { + /// The associated item described by this `LeafDef`. + pub item: ty::AssocItem, + + /// The node in the specialization graph containing the definition of `item`. + pub defining_node: Node, + + /// The "top-most" (ie. least specialized) specialization graph node that finalized the + /// definition of `item`. + /// + /// Example: + /// + /// ``` + /// #![feature(specialization)] + /// trait Tr { + /// fn assoc(&self); + /// } + /// + /// impl Tr for T { + /// default fn assoc(&self) {} + /// } + /// + /// impl Tr for u8 {} + /// ``` + /// + /// If we start the leaf definition search at `impl Tr for u8`, that impl will be the + /// `finalizing_node`, while `defining_node` will be the generic impl. + /// + /// If the leaf definition search is started at the generic impl, `finalizing_node` will be + /// `None`, since the most specialized impl we found still allows overriding the method + /// (doesn't finalize it). + pub finalizing_node: Option, +} + +impl LeafDef { + /// Returns whether this definition is known to not be further specializable. + pub fn is_final(&self) -> bool { + self.finalizing_node.is_some() + } +} + +impl<'tcx> Ancestors<'tcx> { + /// Finds the bottom-most (ie. most specialized) definition of an associated + /// item. + pub fn leaf_def(mut self, tcx: TyCtxt<'tcx>, trait_item_def_id: DefId) -> Option { + let mut finalizing_node = None; + + self.find_map(|node| { + if let Some(item) = node.item(tcx, trait_item_def_id) { + if finalizing_node.is_none() { + let is_specializable = item.defaultness(tcx).is_default() + || tcx.impl_defaultness(node.def_id()).is_default(); + + if !is_specializable { + finalizing_node = Some(node); + } + } + + Some(LeafDef { item: *item, defining_node: node, finalizing_node }) + } else { + // Item not mentioned. This "finalizes" any defaulted item provided by an ancestor. + finalizing_node = Some(node); + None + } + }) + } +} + +/// Walk up the specialization ancestors of a given impl, starting with that +/// impl itself. +/// +/// Returns `Err` if an error was reported while building the specialization +/// graph. +pub fn ancestors<'tcx>( + tcx: TyCtxt<'tcx>, + trait_def_id: DefId, + start_from_impl: DefId, +) -> Result, ErrorGuaranteed> { + let specialization_graph = tcx.specialization_graph_of(trait_def_id); + + if let Some(reported) = specialization_graph.has_errored { + Err(reported) + } else if let Some(reported) = tcx.type_of(start_from_impl).error_reported() { + Err(reported) + } else { + Ok(Ancestors { + trait_def_id, + specialization_graph, + current_source: Some(Node::Impl(start_from_impl)), + }) + } +} diff --git a/compiler/rustc_middle/src/traits/structural_impls.rs b/compiler/rustc_middle/src/traits/structural_impls.rs new file mode 100644 index 000000000..7fbd57ac7 --- /dev/null +++ b/compiler/rustc_middle/src/traits/structural_impls.rs @@ -0,0 +1,135 @@ +use crate::traits; + +use std::fmt; + +// Structural impls for the structs in `traits`. + +impl<'tcx, N: fmt::Debug> fmt::Debug for traits::ImplSource<'tcx, N> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match *self { + super::ImplSource::UserDefined(ref v) => write!(f, "{:?}", v), + + super::ImplSource::AutoImpl(ref t) => write!(f, "{:?}", t), + + super::ImplSource::Closure(ref d) => write!(f, "{:?}", d), + + super::ImplSource::Generator(ref d) => write!(f, "{:?}", d), + + super::ImplSource::FnPointer(ref d) => write!(f, "({:?})", d), + + super::ImplSource::DiscriminantKind(ref d) => write!(f, "{:?}", d), + + super::ImplSource::Pointee(ref d) => write!(f, "{:?}", d), + + super::ImplSource::Object(ref d) => write!(f, "{:?}", d), + + super::ImplSource::Param(ref n, ct) => { + write!(f, "ImplSourceParamData({:?}, {:?})", n, ct) + } + + super::ImplSource::Builtin(ref d) => write!(f, "{:?}", d), + + super::ImplSource::TraitAlias(ref d) => write!(f, "{:?}", d), + + super::ImplSource::TraitUpcasting(ref d) => write!(f, "{:?}", d), + + super::ImplSource::ConstDestruct(ref d) => write!(f, "{:?}", d), + } + } +} + +impl<'tcx, N: fmt::Debug> fmt::Debug for traits::ImplSourceUserDefinedData<'tcx, N> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!( + f, + "ImplSourceUserDefinedData(impl_def_id={:?}, substs={:?}, nested={:?})", + self.impl_def_id, self.substs, self.nested + ) + } +} + +impl<'tcx, N: fmt::Debug> fmt::Debug for traits::ImplSourceGeneratorData<'tcx, N> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!( + f, + "ImplSourceGeneratorData(generator_def_id={:?}, substs={:?}, nested={:?})", + self.generator_def_id, self.substs, self.nested + ) + } +} + +impl<'tcx, N: fmt::Debug> fmt::Debug for traits::ImplSourceClosureData<'tcx, N> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!( + f, + "ImplSourceClosureData(closure_def_id={:?}, substs={:?}, nested={:?})", + self.closure_def_id, self.substs, self.nested + ) + } +} + +impl fmt::Debug for traits::ImplSourceBuiltinData { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "ImplSourceBuiltinData(nested={:?})", self.nested) + } +} + +impl<'tcx, N: fmt::Debug> fmt::Debug for traits::ImplSourceTraitUpcastingData<'tcx, N> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!( + f, + "ImplSourceTraitUpcastingData(upcast={:?}, vtable_vptr_slot={:?}, nested={:?})", + self.upcast_trait_ref, self.vtable_vptr_slot, self.nested + ) + } +} + +impl fmt::Debug for traits::ImplSourceAutoImplData { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!( + f, + "ImplSourceAutoImplData(trait_def_id={:?}, nested={:?})", + self.trait_def_id, self.nested + ) + } +} + +impl<'tcx, N: fmt::Debug> fmt::Debug for traits::ImplSourceObjectData<'tcx, N> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!( + f, + "ImplSourceObjectData(upcast={:?}, vtable_base={}, nested={:?})", + self.upcast_trait_ref, self.vtable_base, self.nested + ) + } +} + +impl<'tcx, N: fmt::Debug> fmt::Debug for traits::ImplSourceFnPointerData<'tcx, N> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "ImplSourceFnPointerData(fn_ty={:?}, nested={:?})", self.fn_ty, self.nested) + } +} + +impl<'tcx, N: fmt::Debug> fmt::Debug for traits::ImplSourceTraitAliasData<'tcx, N> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!( + f, + "ImplSourceTraitAliasData(alias_def_id={:?}, substs={:?}, nested={:?})", + self.alias_def_id, self.substs, self.nested + ) + } +} + +impl fmt::Debug for traits::ImplSourceConstDestructData { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "ImplSourceConstDestructData(nested={:?})", self.nested) + } +} + +/////////////////////////////////////////////////////////////////////////// +// Lift implementations + +TrivialTypeTraversalAndLiftImpls! { + super::ImplSourceDiscriminantKindData, + super::ImplSourcePointeeData, +} diff --git a/compiler/rustc_middle/src/traits/util.rs b/compiler/rustc_middle/src/traits/util.rs new file mode 100644 index 000000000..d54b8c599 --- /dev/null +++ b/compiler/rustc_middle/src/traits/util.rs @@ -0,0 +1,49 @@ +use rustc_data_structures::fx::FxHashSet; + +use crate::ty::{PolyTraitRef, TyCtxt}; + +/// Given a PolyTraitRef, get the PolyTraitRefs of the trait's (transitive) supertraits. +/// +/// A simplified version of the same function at `rustc_infer::traits::util::supertraits`. +pub fn supertraits<'tcx>( + tcx: TyCtxt<'tcx>, + trait_ref: PolyTraitRef<'tcx>, +) -> impl Iterator> { + Elaborator { tcx, visited: FxHashSet::from_iter([trait_ref]), stack: vec![trait_ref] } +} + +struct Elaborator<'tcx> { + tcx: TyCtxt<'tcx>, + visited: FxHashSet>, + stack: Vec>, +} + +impl<'tcx> Elaborator<'tcx> { + fn elaborate(&mut self, trait_ref: PolyTraitRef<'tcx>) { + let supertrait_refs = self + .tcx + .super_predicates_of(trait_ref.def_id()) + .predicates + .into_iter() + .flat_map(|(pred, _)| { + pred.subst_supertrait(self.tcx, &trait_ref).to_opt_poly_trait_pred() + }) + .map(|t| t.map_bound(|pred| pred.trait_ref)) + .filter(|supertrait_ref| self.visited.insert(*supertrait_ref)); + + self.stack.extend(supertrait_refs); + } +} + +impl<'tcx> Iterator for Elaborator<'tcx> { + type Item = PolyTraitRef<'tcx>; + + fn next(&mut self) -> Option> { + if let Some(trait_ref) = self.stack.pop() { + self.elaborate(trait_ref); + Some(trait_ref) + } else { + None + } + } +} -- cgit v1.2.3