Auto merge of #117164 - fmease:orphan-norm, r=lcnr

Lazily normalize inside trait ref during orphan check & consider ty params in rigid alias types to be uncovered

Fixes #99554, fixes rust-lang/types-team#104.
Fixes #114061.

Supersedes #100555.

Tracking issue for the future compatibility lint: #124559.

r? lcnr

2 files changed, 115 insertions, 67 deletions

diff --git a/compiler/rustc_trait_selection/src/traits/coherence.rs b/compiler/rustc_trait_selection/src/traits/coherence.rs
index c430da10b0c..730b7ea70c6 100644
--- a/compiler/rustc_trait_selection/src/traits/coherence.rs
+++ b/compiler/rustc_trait_selection/src/traits/coherence.rs
@@ -20,15 +20,15 @@ use crate::traits::{
 use rustc_data_structures::fx::FxIndexSet;
 use rustc_errors::{Diag, EmissionGuarantee};
 use rustc_hir::def::DefKind;
-use rustc_hir::def_id::{DefId, LOCAL_CRATE};
+use rustc_hir::def_id::DefId;
 use rustc_infer::infer::{DefineOpaqueTypes, InferCtxt, TyCtxtInferExt};
 use rustc_infer::traits::{util, FulfillmentErrorCode, TraitEngine, TraitEngineExt};
 use rustc_middle::traits::query::NoSolution;
 use rustc_middle::traits::solve::{CandidateSource, Certainty, Goal};
 use rustc_middle::traits::specialization_graph::OverlapMode;
 use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams};
-use rustc_middle::ty::visit::{TypeVisitable, TypeVisitableExt};
-use rustc_middle::ty::{self, Ty, TyCtxt, TypeSuperVisitable, TypeVisitor};
+use rustc_middle::ty::visit::{TypeSuperVisitable, TypeVisitable, TypeVisitableExt, TypeVisitor};
+use rustc_middle::ty::{self, Ty, TyCtxt};
 use rustc_span::symbol::sym;
 use rustc_span::{Span, DUMMY_SP};
 use std::fmt::Debug;
@@ -36,14 +36,28 @@ use std::ops::ControlFlow;
 
 use super::error_reporting::suggest_new_overflow_limit;
 
-/// Whether we do the orphan check relative to this crate or
-/// to some remote crate.
+/// Whether we do the orphan check relative to this crate or to some remote crate.
 #[derive(Copy, Clone, Debug)]
-enum InCrate {
-    Local,
+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,
@@ -633,7 +647,13 @@ pub fn trait_ref_is_knowable<'tcx, E: Debug>(
     // 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(trait_ref, InCrate::Local, &mut lazily_normalize_ty)?.is_ok() {
+    if orphan_check_trait_ref(
+        trait_ref,
+        InCrate::Local { mode: OrphanCheckMode::Proper },
+        &mut lazily_normalize_ty,
+    )?
+    .is_ok()
+    {
         Ok(Ok(()))
     } else {
         Ok(Err(Conflict::Upstream))
@@ -644,7 +664,7 @@ pub fn trait_ref_is_local_or_fundamental<'tcx>(
     tcx: TyCtxt<'tcx>,
     trait_ref: ty::TraitRef<'tcx>,
 ) -> bool {
-    trait_ref.def_id.krate == LOCAL_CRATE || tcx.has_attr(trait_ref.def_id, sym::fundamental)
+    trait_ref.def_id.is_local() || tcx.has_attr(trait_ref.def_id, sym::fundamental)
 }
 
 #[derive(Debug, Copy, Clone)]
@@ -663,31 +683,15 @@ impl From<bool> for IsFirstInputType {
 }
 
 #[derive(Debug)]
-pub enum OrphanCheckErr<'tcx> {
+pub enum OrphanCheckErr<'tcx, T> {
     NonLocalInputType(Vec<(Ty<'tcx>, IsFirstInputType)>),
-    UncoveredTy(Ty<'tcx>, Option<Ty<'tcx>>),
+    UncoveredTyParams(UncoveredTyParams<'tcx, T>),
 }
 
-/// Checks the coherence orphan rules. `impl_def_id` should be the
-/// `DefId` of a trait impl. To pass, either the trait must be local, or else
-/// two conditions must be satisfied:
-///
-/// 1. All type parameters in `Self` must be "covered" by some local type constructor.
-/// 2. Some local type must appear in `Self`.
-#[instrument(level = "debug", skip(tcx), ret)]
-pub fn orphan_check(tcx: TyCtxt<'_>, impl_def_id: DefId) -> Result<(), OrphanCheckErr<'_>> {
-    // We only except this routine to be invoked on implementations
-    // of a trait, not inherent implementations.
-    let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap().instantiate_identity();
-    debug!(?trait_ref);
-
-    // If the *trait* is local to the crate, ok.
-    if trait_ref.def_id.is_local() {
-        debug!("trait {:?} is local to current crate", trait_ref.def_id);
-        return Ok(());
-    }
-
-    orphan_check_trait_ref::<!>(trait_ref, InCrate::Local, |ty| Ok(ty)).unwrap()
+#[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.
@@ -735,6 +739,9 @@ pub fn orphan_check(tcx: TyCtxt<'_>, impl_def_id: DefId) -> Result<(), OrphanChe
 ///    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
@@ -753,6 +760,9 @@ pub fn orphan_check(tcx: TyCtxt<'_>, impl_def_id: DefId) -> Result<(), OrphanChe
 ///    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.
@@ -777,11 +787,11 @@ pub fn orphan_check(tcx: TyCtxt<'_>, impl_def_id: DefId) -> Result<(), OrphanChe
 /// Note that this function is never called for types that have both type
 /// parameters and inference variables.
 #[instrument(level = "trace", skip(lazily_normalize_ty), ret)]
-fn orphan_check_trait_ref<'tcx, E: Debug>(
+pub fn orphan_check_trait_ref<'tcx, E: Debug>(
     trait_ref: ty::TraitRef<'tcx>,
     in_crate: InCrate,
     lazily_normalize_ty: impl FnMut(Ty<'tcx>) -> Result<Ty<'tcx>, E>,
-) -> Result<Result<(), OrphanCheckErr<'tcx>>, E> {
+) -> Result<Result<(), OrphanCheckErr<'tcx, Ty<'tcx>>>, E> {
     if trait_ref.has_infer() && trait_ref.has_param() {
         bug!(
             "can't orphan check a trait ref with both params and inference variables {:?}",
@@ -790,21 +800,28 @@ fn orphan_check_trait_ref<'tcx, E: Debug>(
     }
 
     let mut checker = OrphanChecker::new(in_crate, lazily_normalize_ty);
+
+    // Does there exist some local type after the `ParamTy`.
+    let search_first_local_ty = |checker: &mut OrphanChecker<'tcx, _>| {
+        checker.search_first_local_ty = true;
+        match trait_ref.visit_with(checker).break_value() {
+            Some(OrphanCheckEarlyExit::LocalTy(local_ty)) => Some(local_ty),
+            _ => None,
+        }
+    };
+
     Ok(match trait_ref.visit_with(&mut checker) {
         ControlFlow::Continue(()) => Err(OrphanCheckErr::NonLocalInputType(checker.non_local_tys)),
-        ControlFlow::Break(OrphanCheckEarlyExit::NormalizationFailure(err)) => return Err(err),
-        ControlFlow::Break(OrphanCheckEarlyExit::ParamTy(ty)) => {
-            // Does there exist some local type after the `ParamTy`.
-            checker.search_first_local_ty = true;
-            if let Some(OrphanCheckEarlyExit::LocalTy(local_ty)) =
-                trait_ref.visit_with(&mut checker).break_value()
-            {
-                Err(OrphanCheckErr::UncoveredTy(ty, Some(local_ty)))
-            } else {
-                Err(OrphanCheckErr::UncoveredTy(ty, None))
+        ControlFlow::Break(residual) => match residual {
+            OrphanCheckEarlyExit::NormalizationFailure(err) => return Err(err),
+            OrphanCheckEarlyExit::UncoveredTyParam(ty) => {
+                Err(OrphanCheckErr::UncoveredTyParams(UncoveredTyParams {
+                    uncovered: ty,
+                    local_ty: search_first_local_ty(&mut checker),
+                }))
             }
-        }
-        ControlFlow::Break(OrphanCheckEarlyExit::LocalTy(_)) => Ok(()),
+            OrphanCheckEarlyExit::LocalTy(_) => Ok(()),
+        },
     })
 }
 
@@ -812,8 +829,7 @@ struct OrphanChecker<'tcx, F> {
     in_crate: InCrate,
     in_self_ty: bool,
     lazily_normalize_ty: F,
-    /// Ignore orphan check failures and exclusively search for the first
-    /// local type.
+    /// Ignore orphan check failures and exclusively search for the first local type.
     search_first_local_ty: bool,
     non_local_tys: Vec<(Ty<'tcx>, IsFirstInputType)>,
 }
@@ -837,17 +853,20 @@ where
         ControlFlow::Continue(())
     }
 
-    fn found_param_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<OrphanCheckEarlyExit<'tcx, E>> {
+    fn found_uncovered_ty_param(
+        &mut self,
+        ty: Ty<'tcx>,
+    ) -> ControlFlow<OrphanCheckEarlyExit<'tcx, E>> {
         if self.search_first_local_ty {
-            ControlFlow::Continue(())
-        } else {
-            ControlFlow::Break(OrphanCheckEarlyExit::ParamTy(t))
+            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::Local { .. } => def_id.is_local(),
             InCrate::Remote => false,
         }
     }
@@ -855,7 +874,7 @@ where
 
 enum OrphanCheckEarlyExit<'tcx, E> {
     NormalizationFailure(E),
-    ParamTy(Ty<'tcx>),
+    UncoveredTyParam(Ty<'tcx>),
     LocalTy(Ty<'tcx>),
 }
 
@@ -864,14 +883,15 @@ 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 {
-        // Need to lazily normalize here in with `-Znext-solver=coherence`.
         let ty = match (self.lazily_normalize_ty)(ty) {
-            Ok(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)),
         };
 
@@ -889,19 +909,46 @@ where
             | ty::Slice(..)
             | ty::RawPtr(..)
             | ty::Never
-            | ty::Tuple(..)
-            | ty::Alias(ty::Projection | ty::Inherent | ty::Weak, ..) => {
-                self.found_non_local_ty(ty)
+            | 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)),
+                }
             }
 
-            ty::Param(..) => self.found_param_ty(ty),
+            ty::Alias(kind @ (ty::Projection | ty::Inherent | ty::Weak), ..) => {
+                if ty.has_type_flags(ty::TypeFlags::HAS_TY_PARAM) {
+                    bug!("unexpected ty param in alias ty");
+                }
 
-            ty::Placeholder(..) | ty::Bound(..) | ty::Infer(..) => match self.in_crate {
-                InCrate::Local => self.found_non_local_ty(ty),
-                // The inference variable might be unified with a local
-                // type in that remote crate.
-                InCrate::Remote => ControlFlow::Break(OrphanCheckEarlyExit::LocalTy(ty)),
-            },
+                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 {
+                    ControlFlow::Continue(())
+                }
+            }
 
             // For fundamental types, we just look inside of them.
             ty::Ref(_, ty, _) => ty.visit_with(self),
diff --git a/compiler/rustc_trait_selection/src/traits/mod.rs b/compiler/rustc_trait_selection/src/traits/mod.rs
index 88ebf8754d3..56f8b4b9cdb 100644
--- a/compiler/rustc_trait_selection/src/traits/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/mod.rs
@@ -41,8 +41,9 @@ use rustc_span::Span;
 use std::fmt::Debug;
 use std::ops::ControlFlow;
 
-pub use self::coherence::{add_placeholder_note, orphan_check, overlapping_impls};
-pub use self::coherence::{IsFirstInputType, OrphanCheckErr, OverlapResult};
+pub use self::coherence::{add_placeholder_note, orphan_check_trait_ref, overlapping_impls};
+pub use self::coherence::{InCrate, IsFirstInputType, UncoveredTyParams};
+pub use self::coherence::{OrphanCheckErr, OrphanCheckMode, OverlapResult};
 pub use self::engine::{ObligationCtxt, TraitEngineExt};
 pub use self::fulfill::{FulfillmentContext, PendingPredicateObligation};
 pub use self::normalize::NormalizeExt;