Auto merge of #122747 - Urgau:non-local-defs_perfect_impl, r=lcnr

Implement T-types suggested logic for perfect non-local impl detection

This implement [T-types suggested logic](https://github.com/rust-lang/rust/issues/121621#issuecomment-1976826895) for perfect non-local impl detection:

> for each impl, instantiate all local types with inference vars and then assemble candidates for that goal, if there are more than 1 (non-private impls), it does not leak

This extension to the current logic is meant to address issues reported in https://github.com/rust-lang/rust/issues/121621.

This PR also re-enables the lint `non_local_definitions` to warn-by-default.

Implementation was discussed in this [zulip thread](https://rust-lang.zulipchat.com/#narrow/stream/144729-t-types/topic/Implementing.20new.20non-local.20impl.20defs.20logic).

Fixes https://github.com/rust-lang/rust/issues/121621
Fixes https://github.com/rust-lang/rust/issues/121746

r? `@lcnr` *(feel free to re-roll)*

5 files changed, 194 insertions, 51 deletions

diff --git a/compiler/rustc_lint/messages.ftl b/compiler/rustc_lint/messages.ftl
index d938a0ccb39..797c0df4d73 100644
--- a/compiler/rustc_lint/messages.ftl
+++ b/compiler/rustc_lint/messages.ftl
@@ -443,7 +443,7 @@ lint_non_local_definitions_impl = non-local `impl` definition, they should be av
             [one] `{$body_name}`
            *[other] `{$body_name}` and up {$depth} bodies
         }
-    .non_local = an `impl` definition is non-local if it is nested inside an item and neither the type nor the trait are at the same nesting level as the `impl` block
+    .non_local = an `impl` definition is non-local if it is nested inside an item and may impact type checking outside of that item. This can be the case if neither the trait or the self type are at the same nesting level as the `impl`
     .exception = one exception to the rule are anon-const (`const _: () = {"{"} ... {"}"}`) at top-level module and anon-const at the same nesting as the trait or type
     .const_anon = use a const-anon item to suppress this lint
 
diff --git a/compiler/rustc_lint/src/non_local_def.rs b/compiler/rustc_lint/src/non_local_def.rs
index 7c4d92d3ce0..1e9c60a540d 100644
--- a/compiler/rustc_lint/src/non_local_def.rs
+++ b/compiler/rustc_lint/src/non_local_def.rs
@@ -1,6 +1,18 @@
-use rustc_hir::{def::DefKind, Body, Item, ItemKind, Node, Path, QPath, TyKind};
+use rustc_hir::{def::DefKind, Body, Item, ItemKind, Node, TyKind};
+use rustc_hir::{Path, QPath};
+use rustc_infer::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind};
+use rustc_infer::infer::InferCtxt;
+use rustc_infer::traits::{Obligation, ObligationCause};
+use rustc_middle::query::Key;
+use rustc_middle::ty::{self, Binder, Ty, TyCtxt, TypeFoldable, TypeFolder};
+use rustc_middle::ty::{EarlyBinder, TraitRef, TypeSuperFoldable};
 use rustc_span::def_id::{DefId, LOCAL_CRATE};
+use rustc_span::Span;
 use rustc_span::{sym, symbol::kw, ExpnKind, MacroKind};
+use rustc_trait_selection::infer::TyCtxtInferExt;
+use rustc_trait_selection::traits::error_reporting::ambiguity::{
+    compute_applicable_impls_for_diagnostics, CandidateSource,
+};
 
 use crate::lints::{NonLocalDefinitionsCargoUpdateNote, NonLocalDefinitionsDiag};
 use crate::{LateContext, LateLintPass, LintContext};
@@ -35,7 +47,7 @@ declare_lint! {
     /// All nested bodies (functions, enum discriminant, array length, consts) (expect for
     /// `const _: Ty = { ... }` in top-level module, which is still undecided) are checked.
     pub NON_LOCAL_DEFINITIONS,
-    Allow,
+    Warn,
     "checks for non-local definitions",
     report_in_external_macro
 }
@@ -66,7 +78,8 @@ impl<'tcx> LateLintPass<'tcx> for NonLocalDefinitions {
             return;
         }
 
-        let parent = cx.tcx.parent(item.owner_id.def_id.into());
+        let def_id = item.owner_id.def_id.into();
+        let parent = cx.tcx.parent(def_id);
         let parent_def_kind = cx.tcx.def_kind(parent);
         let parent_opt_item_name = cx.tcx.opt_item_name(parent);
 
@@ -121,6 +134,7 @@ impl<'tcx> LateLintPass<'tcx> for NonLocalDefinitions {
                     None
                 };
 
+                // Part 1: Is the Self type local?
                 let self_ty_has_local_parent = match impl_.self_ty.kind {
                     TyKind::Path(QPath::Resolved(_, ty_path)) => {
                         path_has_local_parent(ty_path, cx, parent, parent_parent)
@@ -150,41 +164,70 @@ impl<'tcx> LateLintPass<'tcx> for NonLocalDefinitions {
                     | TyKind::Err(_) => false,
                 };
 
+                if self_ty_has_local_parent {
+                    return;
+                }
+
+                // Part 2: Is the Trait local?
                 let of_trait_has_local_parent = impl_
                     .of_trait
                     .map(|of_trait| path_has_local_parent(of_trait.path, cx, parent, parent_parent))
                     .unwrap_or(false);
 
-                // If none of them have a local parent (LOGICAL NOR) this means that
-                // this impl definition is a non-local definition and so we lint on it.
-                if !(self_ty_has_local_parent || of_trait_has_local_parent) {
-                    let const_anon = if self.body_depth == 1
-                        && parent_def_kind == DefKind::Const
-                        && parent_opt_item_name != Some(kw::Underscore)
-                        && let Some(parent) = parent.as_local()
-                        && let Node::Item(item) = cx.tcx.hir_node_by_def_id(parent)
-                        && let ItemKind::Const(ty, _, _) = item.kind
-                        && let TyKind::Tup(&[]) = ty.kind
-                    {
-                        Some(item.ident.span)
-                    } else {
-                        None
-                    };
-
-                    cx.emit_span_lint(
-                        NON_LOCAL_DEFINITIONS,
-                        item.span,
-                        NonLocalDefinitionsDiag::Impl {
-                            depth: self.body_depth,
-                            body_kind_descr: cx.tcx.def_kind_descr(parent_def_kind, parent),
-                            body_name: parent_opt_item_name
-                                .map(|s| s.to_ident_string())
-                                .unwrap_or_else(|| "<unnameable>".to_string()),
-                            cargo_update: cargo_update(),
-                            const_anon,
-                        },
-                    )
+                if of_trait_has_local_parent {
+                    return;
+                }
+
+                // Part 3: Is the impl definition leaking outside it's defining scope?
+                //
+                // We always consider inherent impls to be leaking.
+                let impl_has_enough_non_local_candidates = cx
+                    .tcx
+                    .impl_trait_ref(def_id)
+                    .map(|binder| {
+                        impl_trait_ref_has_enough_non_local_candidates(
+                            cx.tcx,
+                            item.span,
+                            def_id,
+                            binder,
+                            |did| did_has_local_parent(did, cx.tcx, parent, parent_parent),
+                        )
+                    })
+                    .unwrap_or(false);
+
+                if impl_has_enough_non_local_candidates {
+                    return;
                 }
+
+                // Get the span of the parent const item ident (if it's a not a const anon).
+                //
+                // Used to suggest changing the const item to a const anon.
+                let span_for_const_anon_suggestion = if self.body_depth == 1
+                    && parent_def_kind == DefKind::Const
+                    && parent_opt_item_name != Some(kw::Underscore)
+                    && let Some(parent) = parent.as_local()
+                    && let Node::Item(item) = cx.tcx.hir_node_by_def_id(parent)
+                    && let ItemKind::Const(ty, _, _) = item.kind
+                    && let TyKind::Tup(&[]) = ty.kind
+                {
+                    Some(item.ident.span)
+                } else {
+                    None
+                };
+
+                cx.emit_span_lint(
+                    NON_LOCAL_DEFINITIONS,
+                    item.span,
+                    NonLocalDefinitionsDiag::Impl {
+                        depth: self.body_depth,
+                        body_kind_descr: cx.tcx.def_kind_descr(parent_def_kind, parent),
+                        body_name: parent_opt_item_name
+                            .map(|s| s.to_ident_string())
+                            .unwrap_or_else(|| "<unnameable>".to_string()),
+                        cargo_update: cargo_update(),
+                        const_anon: span_for_const_anon_suggestion,
+                    },
+                )
             }
             ItemKind::Macro(_macro, MacroKind::Bang)
                 if cx.tcx.has_attr(item.owner_id.def_id, sym::macro_export) =>
@@ -207,6 +250,81 @@ impl<'tcx> LateLintPass<'tcx> for NonLocalDefinitions {
     }
 }
 
+// Detecting if the impl definition is leaking outside of it's defining scope.
+//
+// Rule: for each impl, instantiate all local types with inference vars and
+// then assemble candidates for that goal, if there are more than 1 (non-private
+// impls), it does not leak.
+//
+// https://github.com/rust-lang/rust/issues/121621#issuecomment-1976826895
+fn impl_trait_ref_has_enough_non_local_candidates<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    infer_span: Span,
+    trait_def_id: DefId,
+    binder: EarlyBinder<TraitRef<'tcx>>,
+    mut did_has_local_parent: impl FnMut(DefId) -> bool,
+) -> bool {
+    let infcx = tcx.infer_ctxt().build();
+    let trait_ref = binder.instantiate(tcx, infcx.fresh_args_for_item(infer_span, trait_def_id));
+
+    let trait_ref = trait_ref.fold_with(&mut ReplaceLocalTypesWithInfer {
+        infcx: &infcx,
+        infer_span,
+        did_has_local_parent: &mut did_has_local_parent,
+    });
+
+    let poly_trait_obligation = Obligation::new(
+        tcx,
+        ObligationCause::dummy(),
+        ty::ParamEnv::empty(),
+        Binder::dummy(trait_ref),
+    );
+
+    let ambiguities = compute_applicable_impls_for_diagnostics(&infcx, &poly_trait_obligation);
+
+    let mut it = ambiguities.iter().filter(|ambi| match ambi {
+        CandidateSource::DefId(did) => !did_has_local_parent(*did),
+        CandidateSource::ParamEnv(_) => unreachable!(),
+    });
+
+    let _ = it.next();
+    it.next().is_some()
+}
+
+/// Replace every local type by inference variable.
+///
+/// ```text
+/// <Global<Local> as std::cmp::PartialEq<Global<Local>>>
+/// to
+/// <Global<_> as std::cmp::PartialEq<Global<_>>>
+/// ```
+struct ReplaceLocalTypesWithInfer<'a, 'tcx, F: FnMut(DefId) -> bool> {
+    infcx: &'a InferCtxt<'tcx>,
+    did_has_local_parent: F,
+    infer_span: Span,
+}
+
+impl<'a, 'tcx, F: FnMut(DefId) -> bool> TypeFolder<TyCtxt<'tcx>>
+    for ReplaceLocalTypesWithInfer<'a, 'tcx, F>
+{
+    fn interner(&self) -> TyCtxt<'tcx> {
+        self.infcx.tcx
+    }
+
+    fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
+        if let Some(ty_did) = t.ty_def_id()
+            && (self.did_has_local_parent)(ty_did)
+        {
+            self.infcx.next_ty_var(TypeVariableOrigin {
+                kind: TypeVariableOriginKind::TypeInference,
+                span: self.infer_span,
+            })
+        } else {
+            t.super_fold_with(self)
+        }
+    }
+}
+
 /// Given a path and a parent impl def id, this checks if the if parent resolution
 /// def id correspond to the def id of the parent impl definition.
 ///
@@ -216,16 +334,29 @@ impl<'tcx> LateLintPass<'tcx> for NonLocalDefinitions {
 ///    std::convert::PartialEq<Foo<Bar>>
 ///    ^^^^^^^^^^^^^^^^^^^^^^^
 /// ```
+#[inline]
 fn path_has_local_parent(
     path: &Path<'_>,
     cx: &LateContext<'_>,
     impl_parent: DefId,
     impl_parent_parent: Option<DefId>,
 ) -> bool {
-    path.res.opt_def_id().is_some_and(|did| {
-        did.is_local() && {
-            let res_parent = cx.tcx.parent(did);
-            res_parent == impl_parent || Some(res_parent) == impl_parent_parent
-        }
-    })
+    path.res
+        .opt_def_id()
+        .is_some_and(|did| did_has_local_parent(did, cx.tcx, impl_parent, impl_parent_parent))
+}
+
+/// Given a def id and a parent impl def id, this checks if the parent
+/// def id correspond to the def id of the parent impl definition.
+#[inline]
+fn did_has_local_parent(
+    did: DefId,
+    tcx: TyCtxt<'_>,
+    impl_parent: DefId,
+    impl_parent_parent: Option<DefId>,
+) -> bool {
+    did.is_local() && {
+        let res_parent = tcx.parent(did);
+        res_parent == impl_parent || Some(res_parent) == impl_parent_parent
+    }
 }
diff --git a/compiler/rustc_trait_selection/src/traits/error_reporting/ambiguity.rs b/compiler/rustc_trait_selection/src/traits/error_reporting/ambiguity.rs
index c6f5af08013..ddb582ffab0 100644
--- a/compiler/rustc_trait_selection/src/traits/error_reporting/ambiguity.rs
+++ b/compiler/rustc_trait_selection/src/traits/error_reporting/ambiguity.rs
@@ -7,18 +7,21 @@ use rustc_span::{Span, DUMMY_SP};
 
 use crate::traits::ObligationCtxt;
 
-pub enum Ambiguity {
+#[derive(Debug)]
+pub enum CandidateSource {
     DefId(DefId),
     ParamEnv(Span),
 }
 
-pub fn recompute_applicable_impls<'tcx>(
+pub fn compute_applicable_impls_for_diagnostics<'tcx>(
     infcx: &InferCtxt<'tcx>,
     obligation: &PolyTraitObligation<'tcx>,
-) -> Vec<Ambiguity> {
+) -> Vec<CandidateSource> {
     let tcx = infcx.tcx;
     let param_env = obligation.param_env;
 
+    let predicate_polarity = obligation.predicate.skip_binder().polarity;
+
     let impl_may_apply = |impl_def_id| {
         let ocx = ObligationCtxt::new(infcx);
         infcx.enter_forall(obligation.predicate, |placeholder_obligation| {
@@ -40,6 +43,15 @@ pub fn recompute_applicable_impls<'tcx>(
                 return false;
             }
 
+            let impl_trait_header = tcx.impl_trait_header(impl_def_id).unwrap();
+            let impl_polarity = impl_trait_header.polarity;
+
+            match (impl_polarity, predicate_polarity) {
+                (ty::ImplPolarity::Positive, ty::PredicatePolarity::Positive)
+                | (ty::ImplPolarity::Negative, ty::PredicatePolarity::Negative) => {}
+                _ => return false,
+            }
+
             let impl_predicates = tcx.predicates_of(impl_def_id).instantiate(tcx, impl_args);
             ocx.register_obligations(impl_predicates.predicates.iter().map(|&predicate| {
                 Obligation::new(tcx, ObligationCause::dummy(), param_env, predicate)
@@ -86,7 +98,7 @@ pub fn recompute_applicable_impls<'tcx>(
         obligation.predicate.skip_binder().trait_ref.self_ty(),
         |impl_def_id| {
             if infcx.probe(|_| impl_may_apply(impl_def_id)) {
-                ambiguities.push(Ambiguity::DefId(impl_def_id))
+                ambiguities.push(CandidateSource::DefId(impl_def_id))
             }
         },
     );
@@ -101,9 +113,9 @@ pub fn recompute_applicable_impls<'tcx>(
             if kind.rebind(trait_pred.trait_ref)
                 == ty::Binder::dummy(ty::TraitRef::identity(tcx, trait_pred.def_id()))
             {
-                ambiguities.push(Ambiguity::ParamEnv(tcx.def_span(trait_pred.def_id())))
+                ambiguities.push(CandidateSource::ParamEnv(tcx.def_span(trait_pred.def_id())))
             } else {
-                ambiguities.push(Ambiguity::ParamEnv(span))
+                ambiguities.push(CandidateSource::ParamEnv(span))
             }
         }
     }
diff --git a/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs b/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs
index 0515b09ae46..10c03387a5b 100644
--- a/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs
@@ -1,6 +1,6 @@
 // ignore-tidy-filelength :(
 
-mod ambiguity;
+pub mod ambiguity;
 mod infer_ctxt_ext;
 pub mod on_unimplemented;
 pub mod suggestions;
diff --git a/compiler/rustc_trait_selection/src/traits/error_reporting/type_err_ctxt_ext.rs b/compiler/rustc_trait_selection/src/traits/error_reporting/type_err_ctxt_ext.rs
index aef98dbad5f..144971b63c0 100644
--- a/compiler/rustc_trait_selection/src/traits/error_reporting/type_err_ctxt_ext.rs
+++ b/compiler/rustc_trait_selection/src/traits/error_reporting/type_err_ctxt_ext.rs
@@ -10,7 +10,7 @@ use crate::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind};
 use crate::infer::InferCtxtExt as _;
 use crate::infer::{self, InferCtxt};
 use crate::traits::error_reporting::infer_ctxt_ext::InferCtxtExt;
-use crate::traits::error_reporting::{ambiguity, ambiguity::Ambiguity::*};
+use crate::traits::error_reporting::{ambiguity, ambiguity::CandidateSource::*};
 use crate::traits::query::evaluate_obligation::InferCtxtExt as _;
 use crate::traits::specialize::to_pretty_impl_header;
 use crate::traits::NormalizeExt;
@@ -2386,7 +2386,7 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
                     )
                 };
 
-                let mut ambiguities = ambiguity::recompute_applicable_impls(
+                let mut ambiguities = ambiguity::compute_applicable_impls_for_diagnostics(
                     self.infcx,
                     &obligation.with(self.tcx, trait_ref),
                 );
@@ -2702,7 +2702,7 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
     fn annotate_source_of_ambiguity(
         &self,
         err: &mut Diag<'_>,
-        ambiguities: &[ambiguity::Ambiguity],
+        ambiguities: &[ambiguity::CandidateSource],
         predicate: ty::Predicate<'tcx>,
     ) {
         let mut spans = vec![];
@@ -2711,7 +2711,7 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
         let mut has_param_env = false;
         for ambiguity in ambiguities {
             match ambiguity {
-                ambiguity::Ambiguity::DefId(impl_def_id) => {
+                ambiguity::CandidateSource::DefId(impl_def_id) => {
                     match self.tcx.span_of_impl(*impl_def_id) {
                         Ok(span) => spans.push(span),
                         Err(name) => {
@@ -2722,7 +2722,7 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
                         }
                     }
                 }
-                ambiguity::Ambiguity::ParamEnv(span) => {
+                ambiguity::CandidateSource::ParamEnv(span) => {
                     has_param_env = true;
                     spans.push(*span);
                 }