Uplift trait_ref_is_knowable and friends

3 files changed, 3 insertions, 450 deletions

diff --git a/compiler/rustc_trait_selection/src/lib.rs b/compiler/rustc_trait_selection/src/lib.rs
index 50c618bb3bd..37008baca28 100644
--- a/compiler/rustc_trait_selection/src/lib.rs
+++ b/compiler/rustc_trait_selection/src/lib.rs
@@ -26,6 +26,7 @@
 #![feature(never_type)]
 #![feature(rustdoc_internals)]
 #![feature(type_alias_impl_trait)]
+#![feature(unwrap_infallible)]
 #![recursion_limit = "512"] // For rustdoc
 // tidy-alphabetical-end
 
diff --git a/compiler/rustc_trait_selection/src/traits/coherence.rs b/compiler/rustc_trait_selection/src/traits/coherence.rs
index 57ba6c33ac5..fc390bf318d 100644
--- a/compiler/rustc_trait_selection/src/traits/coherence.rs
+++ b/compiler/rustc_trait_selection/src/traits/coherence.rs
@@ -25,42 +25,14 @@ use rustc_middle::traits::specialization_graph::OverlapMode;
 use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams};
 use rustc_middle::ty::visit::{TypeSuperVisitable, TypeVisitable, TypeVisitableExt, TypeVisitor};
 use rustc_middle::ty::{self, Ty, TyCtxt};
+pub use rustc_next_trait_solver::coherence::*;
 use rustc_span::symbol::sym;
 use rustc_span::{Span, DUMMY_SP};
 use std::fmt::Debug;
-use std::ops::ControlFlow;
 
 use super::error_reporting::suggest_new_overflow_limit;
 use super::ObligationCtxt;
 
-/// 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,
-}
-
 pub struct OverlapResult<'tcx> {
     pub impl_header: ty::ImplHeader<'tcx>,
     pub intercrate_ambiguity_causes: FxIndexSet<IntercrateAmbiguityCause<'tcx>>,
@@ -612,426 +584,6 @@ fn try_prove_negated_where_clause<'tcx>(
     true
 }
 
-/// 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<'tcx, E: Debug>(
-    infcx: &InferCtxt<'tcx>,
-    trait_ref: ty::TraitRef<'tcx>,
-    mut lazily_normalize_ty: impl FnMut(Ty<'tcx>) -> Result<Ty<'tcx>, E>,
-) -> Result<Result<(), Conflict>, E> {
-    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.tcx, 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<'tcx>(
-    tcx: TyCtxt<'tcx>,
-    trait_ref: ty::TraitRef<'tcx>,
-) -> bool {
-    trait_ref.def_id.is_local() || tcx.trait_def(trait_ref.def_id).is_fundamental
-}
-
-#[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(Debug)]
-pub enum OrphanCheckErr<'tcx, T> {
-    NonLocalInputType(Vec<(Ty<'tcx>, IsFirstInputType)>),
-    UncoveredTyParams(UncoveredTyParams<'tcx, T>),
-}
-
-#[derive(Debug)]
-pub struct UncoveredTyParams<'tcx, T> {
-    pub uncovered: T,
-    pub local_ty: Option<Ty<'tcx>>,
-}
-
-/// 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<'tcx, E: Debug>(
-    infcx: &InferCtxt<'tcx>,
-    trait_ref: ty::TraitRef<'tcx>,
-    in_crate: InCrate,
-    lazily_normalize_ty: impl FnMut(Ty<'tcx>) -> Result<Ty<'tcx>, E>,
-) -> Result<Result<(), OrphanCheckErr<'tcx, Ty<'tcx>>>, E> {
-    if trait_ref.has_param() {
-        bug!("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).break_value() {
-                    Some(OrphanCheckEarlyExit::LocalTy(local_ty)) => Some(local_ty),
-                    _ => None,
-                };
-                Err(OrphanCheckErr::UncoveredTyParams(UncoveredTyParams {
-                    uncovered: ty,
-                    local_ty,
-                }))
-            }
-            OrphanCheckEarlyExit::LocalTy(_) => Ok(()),
-        },
-    })
-}
-
-struct OrphanChecker<'a, 'tcx, F> {
-    infcx: &'a InferCtxt<'tcx>,
-    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<(Ty<'tcx>, IsFirstInputType)>,
-}
-
-impl<'a, 'tcx, F, E> OrphanChecker<'a, 'tcx, F>
-where
-    F: FnOnce(Ty<'tcx>) -> Result<Ty<'tcx>, E>,
-{
-    fn new(infcx: &'a InferCtxt<'tcx>, 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: Ty<'tcx>) -> ControlFlow<OrphanCheckEarlyExit<'tcx, E>> {
-        self.non_local_tys.push((t, self.in_self_ty.into()));
-        ControlFlow::Continue(())
-    }
-
-    fn found_uncovered_ty_param(
-        &mut self,
-        ty: Ty<'tcx>,
-    ) -> ControlFlow<OrphanCheckEarlyExit<'tcx, E>> {
-        if self.search_first_local_ty {
-            return ControlFlow::Continue(());
-        }
-
-        ControlFlow::Break(OrphanCheckEarlyExit::UncoveredTyParam(ty))
-    }
-
-    fn def_id_is_local(&mut self, def_id: DefId) -> bool {
-        match self.in_crate {
-            InCrate::Local { .. } => def_id.is_local(),
-            InCrate::Remote => false,
-        }
-    }
-}
-
-enum OrphanCheckEarlyExit<'tcx, E> {
-    NormalizationFailure(E),
-    UncoveredTyParam(Ty<'tcx>),
-    LocalTy(Ty<'tcx>),
-}
-
-impl<'a, 'tcx, F, E> TypeVisitor<TyCtxt<'tcx>> for OrphanChecker<'a, 'tcx, F>
-where
-    F: FnMut(Ty<'tcx>) -> Result<Ty<'tcx>, E>,
-{
-    type Result = ControlFlow<OrphanCheckEarlyExit<'tcx, E>>;
-
-    fn visit_region(&mut self, _r: ty::Region<'tcx>) -> Self::Result {
-        ControlFlow::Continue(())
-    }
-
-    fn visit_ty(&mut self, ty: Ty<'tcx>) -> 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(..) => self.found_non_local_ty(ty),
-
-            ty::Param(..) => bug!("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(())
-                            }
-                            _ => 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.did()) {
-                    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, ..) | ty::CoroutineClosure(did, ..) | 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: ty::Const<'tcx>) -> Self::Result {
-        ControlFlow::Continue(())
-    }
-}
-
 /// Compute the `intercrate_ambiguity_causes` for the new solver using
 /// "proof trees".
 ///
diff --git a/compiler/rustc_trait_selection/src/traits/select/mod.rs b/compiler/rustc_trait_selection/src/traits/select/mod.rs
index 68cc04bc8e6..460c4c3cbb3 100644
--- a/compiler/rustc_trait_selection/src/traits/select/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/mod.rs
@@ -1523,7 +1523,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         // bound regions.
         let trait_ref = predicate.skip_binder().trait_ref;
 
-        coherence::trait_ref_is_knowable::<!>(self.infcx, trait_ref, |ty| Ok(ty)).unwrap()
+        coherence::trait_ref_is_knowable(self.infcx, trait_ref, |ty| Ok::<_, !>(ty)).into_ok()
     }
 
     /// Returns `true` if the global caches can be used.