| use std::fmt::Debug; |
| use std::ops::ControlFlow; |
| |
| use derive_where::derive_where; |
| use rustc_type_ir::inherent::*; |
| use rustc_type_ir::{ |
| self as ty, InferCtxtLike, Interner, TrivialTypeTraversalImpls, TypeVisitable, |
| TypeVisitableExt, TypeVisitor, |
| }; |
| use tracing::instrument; |
| |
| /// Whether we do the orphan check relative to this crate or to some remote crate. |
| #[derive(Copy, Clone, Debug)] |
| pub enum InCrate { |
| Local { mode: OrphanCheckMode }, |
| Remote, |
| } |
| |
| #[derive(Copy, Clone, Debug)] |
| pub enum OrphanCheckMode { |
| /// Proper orphan check. |
| Proper, |
| /// Improper orphan check for backward compatibility. |
| /// |
| /// In this mode, type params inside projections are considered to be covered |
| /// even if the projection may normalize to a type that doesn't actually cover |
| /// them. This is unsound. See also [#124559] and [#99554]. |
| /// |
| /// [#124559]: https://github.com/rust-lang/rust/issues/124559 |
| /// [#99554]: https://github.com/rust-lang/rust/issues/99554 |
| Compat, |
| } |
| |
| #[derive(Debug, Copy, Clone)] |
| pub enum Conflict { |
| Upstream, |
| Downstream, |
| } |
| |
| /// Returns whether all impls which would apply to the `trait_ref` |
| /// e.g. `Ty: Trait<Arg>` are already known in the local crate. |
| /// |
| /// This both checks whether any downstream or sibling crates could |
| /// implement it and whether an upstream crate can add this impl |
| /// without breaking backwards compatibility. |
| #[instrument(level = "debug", skip(infcx, lazily_normalize_ty), ret)] |
| pub fn trait_ref_is_knowable<Infcx, I, E>( |
| infcx: &Infcx, |
| trait_ref: ty::TraitRef<I>, |
| mut lazily_normalize_ty: impl FnMut(I::Ty) -> Result<I::Ty, E>, |
| ) -> Result<Result<(), Conflict>, E> |
| where |
| Infcx: InferCtxtLike<Interner = I>, |
| I: Interner, |
| E: Debug, |
| { |
| if orphan_check_trait_ref(infcx, trait_ref, InCrate::Remote, &mut lazily_normalize_ty)?.is_ok() |
| { |
| // A downstream or cousin crate is allowed to implement some |
| // generic parameters of this trait-ref. |
| return Ok(Err(Conflict::Downstream)); |
| } |
| |
| if trait_ref_is_local_or_fundamental(infcx.cx(), trait_ref) { |
| // This is a local or fundamental trait, so future-compatibility |
| // is no concern. We know that downstream/cousin crates are not |
| // allowed to implement a generic parameter of this trait ref, |
| // which means impls could only come from dependencies of this |
| // crate, which we already know about. |
| return Ok(Ok(())); |
| } |
| |
| // This is a remote non-fundamental trait, so if another crate |
| // can be the "final owner" of the generic parameters of this trait-ref, |
| // they are allowed to implement it future-compatibly. |
| // |
| // However, if we are a final owner, then nobody else can be, |
| // and if we are an intermediate owner, then we don't care |
| // about future-compatibility, which means that we're OK if |
| // we are an owner. |
| if orphan_check_trait_ref( |
| infcx, |
| trait_ref, |
| InCrate::Local { mode: OrphanCheckMode::Proper }, |
| &mut lazily_normalize_ty, |
| )? |
| .is_ok() |
| { |
| Ok(Ok(())) |
| } else { |
| Ok(Err(Conflict::Upstream)) |
| } |
| } |
| |
| pub fn trait_ref_is_local_or_fundamental<I: Interner>(tcx: I, trait_ref: ty::TraitRef<I>) -> bool { |
| trait_ref.def_id.is_local() || tcx.trait_is_fundamental(trait_ref.def_id) |
| } |
| |
| TrivialTypeTraversalImpls! { IsFirstInputType, } |
| |
| #[derive(Debug, Copy, Clone)] |
| pub enum IsFirstInputType { |
| No, |
| Yes, |
| } |
| |
| impl From<bool> for IsFirstInputType { |
| fn from(b: bool) -> IsFirstInputType { |
| match b { |
| false => IsFirstInputType::No, |
| true => IsFirstInputType::Yes, |
| } |
| } |
| } |
| |
| #[derive_where(Debug; I: Interner, T: Debug)] |
| pub enum OrphanCheckErr<I: Interner, T> { |
| NonLocalInputType(Vec<(I::Ty, IsFirstInputType)>), |
| UncoveredTyParams(UncoveredTyParams<I, T>), |
| } |
| |
| #[derive_where(Debug; I: Interner, T: Debug)] |
| pub struct UncoveredTyParams<I: Interner, T> { |
| pub uncovered: T, |
| pub local_ty: Option<I::Ty>, |
| } |
| |
| /// Checks whether a trait-ref is potentially implementable by a crate. |
| /// |
| /// The current rule is that a trait-ref orphan checks in a crate C: |
| /// |
| /// 1. Order the parameters in the trait-ref in generic parameters order |
| /// - Self first, others linearly (e.g., `<U as Foo<V, W>>` is U < V < W). |
| /// 2. Of these type parameters, there is at least one type parameter |
| /// in which, walking the type as a tree, you can reach a type local |
| /// to C where all types in-between are fundamental types. Call the |
| /// first such parameter the "local key parameter". |
| /// - e.g., `Box<LocalType>` is OK, because you can visit LocalType |
| /// going through `Box`, which is fundamental. |
| /// - similarly, `FundamentalPair<Vec<()>, Box<LocalType>>` is OK for |
| /// the same reason. |
| /// - but (knowing that `Vec<T>` is non-fundamental, and assuming it's |
| /// not local), `Vec<LocalType>` is bad, because `Vec<->` is between |
| /// the local type and the type parameter. |
| /// 3. Before this local type, no generic type parameter of the impl must |
| /// be reachable through fundamental types. |
| /// - e.g. `impl<T> Trait<LocalType> for Vec<T>` is fine, as `Vec` is not fundamental. |
| /// - while `impl<T> Trait<LocalType> for Box<T>` results in an error, as `T` is |
| /// reachable through the fundamental type `Box`. |
| /// 4. Every type in the local key parameter not known in C, going |
| /// through the parameter's type tree, must appear only as a subtree of |
| /// a type local to C, with only fundamental types between the type |
| /// local to C and the local key parameter. |
| /// - e.g., `Vec<LocalType<T>>>` (or equivalently `Box<Vec<LocalType<T>>>`) |
| /// is bad, because the only local type with `T` as a subtree is |
| /// `LocalType<T>`, and `Vec<->` is between it and the type parameter. |
| /// - similarly, `FundamentalPair<LocalType<T>, T>` is bad, because |
| /// the second occurrence of `T` is not a subtree of *any* local type. |
| /// - however, `LocalType<Vec<T>>` is OK, because `T` is a subtree of |
| /// `LocalType<Vec<T>>`, which is local and has no types between it and |
| /// the type parameter. |
| /// |
| /// The orphan rules actually serve several different purposes: |
| /// |
| /// 1. They enable link-safety - i.e., 2 mutually-unknowing crates (where |
| /// every type local to one crate is unknown in the other) can't implement |
| /// the same trait-ref. This follows because it can be seen that no such |
| /// type can orphan-check in 2 such crates. |
| /// |
| /// To check that a local impl follows the orphan rules, we check it in |
| /// InCrate::Local mode, using type parameters for the "generic" types. |
| /// |
| /// In InCrate::Local mode the orphan check succeeds if the current crate |
| /// is definitely allowed to implement the given trait (no false positives). |
| /// |
| /// 2. They ground negative reasoning for coherence. If a user wants to |
| /// write both a conditional blanket impl and a specific impl, we need to |
| /// make sure they do not overlap. For example, if we write |
| /// ```ignore (illustrative) |
| /// impl<T> IntoIterator for Vec<T> |
| /// impl<T: Iterator> IntoIterator for T |
| /// ``` |
| /// We need to be able to prove that `Vec<$0>: !Iterator` for every type $0. |
| /// We can observe that this holds in the current crate, but we need to make |
| /// sure this will also hold in all unknown crates (both "independent" crates, |
| /// which we need for link-safety, and also child crates, because we don't want |
| /// child crates to get error for impl conflicts in a *dependency*). |
| /// |
| /// For that, we only allow negative reasoning if, for every assignment to the |
| /// inference variables, every unknown crate would get an orphan error if they |
| /// try to implement this trait-ref. To check for this, we use InCrate::Remote |
| /// mode. That is sound because we already know all the impls from known crates. |
| /// |
| /// In InCrate::Remote mode the orphan check succeeds if a foreign crate |
| /// *could* implement the given trait (no false negatives). |
| /// |
| /// 3. For non-`#[fundamental]` traits, they guarantee that parent crates can |
| /// add "non-blanket" impls without breaking negative reasoning in dependent |
| /// crates. This is the "rebalancing coherence" (RFC 1023) restriction. |
| /// |
| /// For that, we only allow a crate to perform negative reasoning on |
| /// non-local-non-`#[fundamental]` if there's a local key parameter as per (2). |
| /// |
| /// Because we never perform negative reasoning generically (coherence does |
| /// not involve type parameters), this can be interpreted as doing the full |
| /// orphan check (using InCrate::Local mode), instantiating non-local known |
| /// types for all inference variables. |
| /// |
| /// This allows for crates to future-compatibly add impls as long as they |
| /// can't apply to types with a key parameter in a child crate - applying |
| /// the rules, this basically means that every type parameter in the impl |
| /// must appear behind a non-fundamental type (because this is not a |
| /// type-system requirement, crate owners might also go for "semantic |
| /// future-compatibility" involving things such as sealed traits, but |
| /// the above requirement is sufficient, and is necessary in "open world" |
| /// cases). |
| /// |
| /// Note that this function is never called for types that have both type |
| /// parameters and inference variables. |
| #[instrument(level = "trace", skip(infcx, lazily_normalize_ty), ret)] |
| pub fn orphan_check_trait_ref<Infcx, I, E: Debug>( |
| infcx: &Infcx, |
| trait_ref: ty::TraitRef<I>, |
| in_crate: InCrate, |
| lazily_normalize_ty: impl FnMut(I::Ty) -> Result<I::Ty, E>, |
| ) -> Result<Result<(), OrphanCheckErr<I, I::Ty>>, E> |
| where |
| Infcx: InferCtxtLike<Interner = I>, |
| I: Interner, |
| E: Debug, |
| { |
| if trait_ref.has_param() { |
| panic!("orphan check only expects inference variables: {trait_ref:?}"); |
| } |
| |
| let mut checker = OrphanChecker::new(infcx, in_crate, lazily_normalize_ty); |
| Ok(match trait_ref.visit_with(&mut checker) { |
| ControlFlow::Continue(()) => Err(OrphanCheckErr::NonLocalInputType(checker.non_local_tys)), |
| ControlFlow::Break(residual) => match residual { |
| OrphanCheckEarlyExit::NormalizationFailure(err) => return Err(err), |
| OrphanCheckEarlyExit::UncoveredTyParam(ty) => { |
| // Does there exist some local type after the `ParamTy`. |
| checker.search_first_local_ty = true; |
| let local_ty = match trait_ref.visit_with(&mut checker) { |
| ControlFlow::Break(OrphanCheckEarlyExit::LocalTy(local_ty)) => Some(local_ty), |
| _ => None, |
| }; |
| Err(OrphanCheckErr::UncoveredTyParams(UncoveredTyParams { |
| uncovered: ty, |
| local_ty, |
| })) |
| } |
| OrphanCheckEarlyExit::LocalTy(_) => Ok(()), |
| }, |
| }) |
| } |
| |
| struct OrphanChecker<'a, Infcx, I: Interner, F> { |
| infcx: &'a Infcx, |
| in_crate: InCrate, |
| in_self_ty: bool, |
| lazily_normalize_ty: F, |
| /// Ignore orphan check failures and exclusively search for the first local type. |
| search_first_local_ty: bool, |
| non_local_tys: Vec<(I::Ty, IsFirstInputType)>, |
| } |
| |
| impl<'a, Infcx, I, F, E> OrphanChecker<'a, Infcx, I, F> |
| where |
| Infcx: InferCtxtLike<Interner = I>, |
| I: Interner, |
| F: FnOnce(I::Ty) -> Result<I::Ty, E>, |
| { |
| fn new(infcx: &'a Infcx, in_crate: InCrate, lazily_normalize_ty: F) -> Self { |
| OrphanChecker { |
| infcx, |
| in_crate, |
| in_self_ty: true, |
| lazily_normalize_ty, |
| search_first_local_ty: false, |
| non_local_tys: Vec::new(), |
| } |
| } |
| |
| fn found_non_local_ty(&mut self, t: I::Ty) -> ControlFlow<OrphanCheckEarlyExit<I, E>> { |
| self.non_local_tys.push((t, self.in_self_ty.into())); |
| ControlFlow::Continue(()) |
| } |
| |
| fn found_uncovered_ty_param(&mut self, ty: I::Ty) -> ControlFlow<OrphanCheckEarlyExit<I, E>> { |
| if self.search_first_local_ty { |
| return ControlFlow::Continue(()); |
| } |
| |
| ControlFlow::Break(OrphanCheckEarlyExit::UncoveredTyParam(ty)) |
| } |
| |
| fn def_id_is_local(&mut self, def_id: impl DefId<I>) -> bool { |
| match self.in_crate { |
| InCrate::Local { .. } => def_id.is_local(), |
| InCrate::Remote => false, |
| } |
| } |
| } |
| |
| enum OrphanCheckEarlyExit<I: Interner, E> { |
| NormalizationFailure(E), |
| UncoveredTyParam(I::Ty), |
| LocalTy(I::Ty), |
| } |
| |
| impl<'a, Infcx, I, F, E> TypeVisitor<I> for OrphanChecker<'a, Infcx, I, F> |
| where |
| Infcx: InferCtxtLike<Interner = I>, |
| I: Interner, |
| F: FnMut(I::Ty) -> Result<I::Ty, E>, |
| { |
| type Result = ControlFlow<OrphanCheckEarlyExit<I, E>>; |
| |
| fn visit_region(&mut self, _r: I::Region) -> Self::Result { |
| ControlFlow::Continue(()) |
| } |
| |
| fn visit_ty(&mut self, ty: I::Ty) -> Self::Result { |
| let ty = self.infcx.shallow_resolve(ty); |
| let ty = match (self.lazily_normalize_ty)(ty) { |
| Ok(norm_ty) if norm_ty.is_ty_var() => ty, |
| Ok(norm_ty) => norm_ty, |
| Err(err) => return ControlFlow::Break(OrphanCheckEarlyExit::NormalizationFailure(err)), |
| }; |
| |
| let result = match ty.kind() { |
| ty::Bool |
| | ty::Char |
| | ty::Int(..) |
| | ty::Uint(..) |
| | ty::Float(..) |
| | ty::Str |
| | ty::FnDef(..) |
| | ty::Pat(..) |
| | ty::FnPtr(..) |
| | ty::Array(..) |
| | ty::Slice(..) |
| | ty::RawPtr(..) |
| | ty::Never |
| | ty::Tuple(..) |
| // FIXME(unsafe_binders): Non-local? |
| | ty::UnsafeBinder(_) => self.found_non_local_ty(ty), |
| |
| ty::Param(..) => panic!("unexpected ty param"), |
| |
| ty::Placeholder(..) | ty::Bound(..) | ty::Infer(..) => { |
| match self.in_crate { |
| InCrate::Local { .. } => self.found_uncovered_ty_param(ty), |
| // The inference variable might be unified with a local |
| // type in that remote crate. |
| InCrate::Remote => ControlFlow::Break(OrphanCheckEarlyExit::LocalTy(ty)), |
| } |
| } |
| |
| // A rigid alias may normalize to anything. |
| // * If it references an infer var, placeholder or bound ty, it may |
| // normalize to that, so we have to treat it as an uncovered ty param. |
| // * Otherwise it may normalize to any non-type-generic type |
| // be it local or non-local. |
| ty::Alias(kind, _) => { |
| if ty.has_type_flags( |
| ty::TypeFlags::HAS_TY_PLACEHOLDER |
| | ty::TypeFlags::HAS_TY_BOUND |
| | ty::TypeFlags::HAS_TY_INFER, |
| ) { |
| match self.in_crate { |
| InCrate::Local { mode } => match kind { |
| ty::Projection => { |
| if let OrphanCheckMode::Compat = mode { |
| ControlFlow::Continue(()) |
| } else { |
| self.found_uncovered_ty_param(ty) |
| } |
| } |
| _ => self.found_uncovered_ty_param(ty), |
| }, |
| InCrate::Remote => { |
| // The inference variable might be unified with a local |
| // type in that remote crate. |
| ControlFlow::Break(OrphanCheckEarlyExit::LocalTy(ty)) |
| } |
| } |
| } else { |
| // Regarding *opaque types* specifically, we choose to treat them as non-local, |
| // even those that appear within the same crate. This seems somewhat surprising |
| // at first, but makes sense when you consider that opaque types are supposed |
| // to hide the underlying type *within the same crate*. When an opaque type is |
| // used from outside the module where it is declared, it should be impossible to |
| // observe anything about it other than the traits that it implements. |
| // |
| // The alternative would be to look at the underlying type to determine whether |
| // or not the opaque type itself should be considered local. |
| // |
| // However, this could make it a breaking change to switch the underlying hidden |
| // type from a local type to a remote type. This would violate the rule that |
| // opaque types should be completely opaque apart from the traits that they |
| // implement, so we don't use this behavior. |
| // Addendum: Moreover, revealing the underlying type is likely to cause cycle |
| // errors as we rely on coherence / the specialization graph during typeck. |
| |
| self.found_non_local_ty(ty) |
| } |
| } |
| |
| // For fundamental types, we just look inside of them. |
| ty::Ref(_, ty, _) => ty.visit_with(self), |
| ty::Adt(def, args) => { |
| if self.def_id_is_local(def.def_id()) { |
| ControlFlow::Break(OrphanCheckEarlyExit::LocalTy(ty)) |
| } else if def.is_fundamental() { |
| args.visit_with(self) |
| } else { |
| self.found_non_local_ty(ty) |
| } |
| } |
| ty::Foreign(def_id) => { |
| if self.def_id_is_local(def_id) { |
| ControlFlow::Break(OrphanCheckEarlyExit::LocalTy(ty)) |
| } else { |
| self.found_non_local_ty(ty) |
| } |
| } |
| ty::Dynamic(tt, ..) => { |
| let principal = tt.principal().map(|p| p.def_id()); |
| if principal.is_some_and(|p| self.def_id_is_local(p)) { |
| ControlFlow::Break(OrphanCheckEarlyExit::LocalTy(ty)) |
| } else { |
| self.found_non_local_ty(ty) |
| } |
| } |
| ty::Error(_) => ControlFlow::Break(OrphanCheckEarlyExit::LocalTy(ty)), |
| ty::Closure(did, ..) => { |
| if self.def_id_is_local(did) { |
| ControlFlow::Break(OrphanCheckEarlyExit::LocalTy(ty)) |
| } else { |
| self.found_non_local_ty(ty) |
| } |
| } |
| ty::CoroutineClosure(did, ..) => { |
| if self.def_id_is_local(did) { |
| ControlFlow::Break(OrphanCheckEarlyExit::LocalTy(ty)) |
| } else { |
| self.found_non_local_ty(ty) |
| } |
| } |
| ty::Coroutine(did, ..) => { |
| if self.def_id_is_local(did) { |
| ControlFlow::Break(OrphanCheckEarlyExit::LocalTy(ty)) |
| } else { |
| self.found_non_local_ty(ty) |
| } |
| } |
| // This should only be created when checking whether we have to check whether some |
| // auto trait impl applies. There will never be multiple impls, so we can just |
| // act as if it were a local type here. |
| ty::CoroutineWitness(..) => ControlFlow::Break(OrphanCheckEarlyExit::LocalTy(ty)), |
| }; |
| // A bit of a hack, the `OrphanChecker` is only used to visit a `TraitRef`, so |
| // the first type we visit is always the self type. |
| self.in_self_ty = false; |
| result |
| } |
| |
| /// All possible values for a constant parameter already exist |
| /// in the crate defining the trait, so they are always non-local[^1]. |
| /// |
| /// Because there's no way to have an impl where the first local |
| /// generic argument is a constant, we also don't have to fail |
| /// the orphan check when encountering a parameter or a generic constant. |
| /// |
| /// This means that we can completely ignore constants during the orphan check. |
| /// |
| /// See `tests/ui/coherence/const-generics-orphan-check-ok.rs` for examples. |
| /// |
| /// [^1]: This might not hold for function pointers or trait objects in the future. |
| /// As these should be quite rare as const arguments and especially rare as impl |
| /// parameters, allowing uncovered const parameters in impls seems more useful |
| /// than allowing `impl<T> Trait<local_fn_ptr, T> for i32` to compile. |
| fn visit_const(&mut self, _c: I::Const) -> Self::Result { |
| ControlFlow::Continue(()) |
| } |
| } |
