Auto merge of #108080 - oli-obk:FnPtr-trait, r=lcnr

Add a builtin `FnPtr` trait that is implemented for all function pointers

r? `@ghost`

Rebased version of https://github.com/rust-lang/rust/pull/99531 (plus adjustments mentioned in the PR).

If perf is happy with this version, I would like to land it, even if the diagnostics fix in 9df8e1befb5031a5bf9d8dfe25170620642d3c59 only works for `FnPtr` specifically, and does not generally improve blanket impls.

3 files changed, 162 insertions, 12 deletions

diff --git a/compiler/rustc_trait_selection/src/traits/coherence.rs b/compiler/rustc_trait_selection/src/traits/coherence.rs
index 03ba125cf2b..b7fafb0dca7 100644
--- a/compiler/rustc_trait_selection/src/traits/coherence.rs
+++ b/compiler/rustc_trait_selection/src/traits/coherence.rs
@@ -411,11 +411,24 @@ fn resolve_negative_obligation<'tcx>(
     infcx.resolve_regions(&outlives_env).is_empty()
 }
 
+/// 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(tcx), ret)]
 pub fn trait_ref_is_knowable<'tcx>(
     tcx: TyCtxt<'tcx>,
     trait_ref: ty::TraitRef<'tcx>,
 ) -> Result<(), Conflict> {
+    if Some(trait_ref.def_id) == tcx.lang_items().fn_ptr_trait() {
+        // The only types implementing `FnPtr` are function pointers,
+        // so if there's no impl of `FnPtr` in the current crate,
+        // then such an impl will never be added in the future.
+        return Ok(());
+    }
+
     if orphan_check_trait_ref(trait_ref, InCrate::Remote).is_ok() {
         // A downstream or cousin crate is allowed to implement some
         // substitution of this trait-ref.
diff --git a/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs b/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs
index e06eff34df2..234d773d64d 100644
--- a/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs
@@ -5,6 +5,8 @@
 //! candidates. See the [rustc dev guide] for more details.
 //!
 //! [rustc dev guide]:https://rustc-dev-guide.rust-lang.org/traits/resolution.html#candidate-assembly
+
+use hir::def_id::DefId;
 use hir::LangItem;
 use rustc_hir as hir;
 use rustc_infer::traits::ObligationCause;
@@ -96,6 +98,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                 self.assemble_candidate_for_tuple(obligation, &mut candidates);
             } else if lang_items.pointer_like() == Some(def_id) {
                 self.assemble_candidate_for_ptr_sized(obligation, &mut candidates);
+            } else if lang_items.fn_ptr_trait() == Some(def_id) {
+                self.assemble_candidates_for_fn_ptr_trait(obligation, &mut candidates);
             } else {
                 if lang_items.clone_trait() == Some(def_id) {
                     // Same builtin conditions as `Copy`, i.e., every type which has builtin support
@@ -321,13 +325,12 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     }
 
     /// Searches for impls that might apply to `obligation`.
+    #[instrument(level = "debug", skip(self, candidates))]
     fn assemble_candidates_from_impls(
         &mut self,
         obligation: &TraitObligation<'tcx>,
         candidates: &mut SelectionCandidateSet<'tcx>,
     ) {
-        debug!(?obligation, "assemble_candidates_from_impls");
-
         // Essentially any user-written impl will match with an error type,
         // so creating `ImplCandidates` isn't useful. However, we might
         // end up finding a candidate elsewhere (e.g. a `BuiltinCandidate` for `Sized`)
@@ -352,6 +355,13 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                 if self.fast_reject_trait_refs(obligation, &impl_trait_ref.0) {
                     return;
                 }
+                if self.reject_fn_ptr_impls(
+                    impl_def_id,
+                    obligation,
+                    impl_trait_ref.skip_binder().self_ty(),
+                ) {
+                    return;
+                }
 
                 self.infcx.probe(|_| {
                     if let Ok(_substs) = self.match_impl(impl_def_id, impl_trait_ref, obligation) {
@@ -362,6 +372,99 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         );
     }
 
+    /// The various `impl<T: FnPtr> Trait for T` in libcore are more like builtin impls for all function items
+    /// and function pointers and less like blanket impls. Rejecting them when they can't possibly apply (because
+    /// the obligation's self-type does not implement `FnPtr`) avoids reporting that the self type does not implement
+    /// `FnPtr`, when we wanted to report that it doesn't implement `Trait`.
+    #[instrument(level = "trace", skip(self), ret)]
+    fn reject_fn_ptr_impls(
+        &self,
+        impl_def_id: DefId,
+        obligation: &TraitObligation<'tcx>,
+        impl_self_ty: Ty<'tcx>,
+    ) -> bool {
+        // Let `impl<T: FnPtr> Trait for Vec<T>` go through the normal rejection path.
+        if !matches!(impl_self_ty.kind(), ty::Param(..)) {
+            return false;
+        }
+        let Some(fn_ptr_trait) = self.tcx().lang_items().fn_ptr_trait() else {
+            return false;
+        };
+
+        for &(predicate, _) in self.tcx().predicates_of(impl_def_id).predicates {
+            let ty::PredicateKind::Clause(ty::Clause::Trait(pred))
+                = predicate.kind().skip_binder() else { continue };
+            if fn_ptr_trait != pred.trait_ref.def_id {
+                continue;
+            }
+            trace!(?pred);
+            // Not the bound we're looking for
+            if pred.self_ty() != impl_self_ty {
+                continue;
+            }
+
+            match obligation.self_ty().skip_binder().kind() {
+                // Fast path to avoid evaluating an obligation that trivally holds.
+                // There may be more bounds, but these are checked by the regular path.
+                ty::FnPtr(..) => return false,
+                // These may potentially implement `FnPtr`
+                ty::Placeholder(..)
+                | ty::Dynamic(_, _, _)
+                | ty::Alias(_, _)
+                | ty::Infer(_)
+                | ty::Param(..) => {}
+
+                ty::Bound(_, _) => span_bug!(
+                    obligation.cause.span(),
+                    "cannot have escaping bound var in self type of {obligation:#?}"
+                ),
+                // These can't possibly implement `FnPtr` as they are concrete types
+                // and not `FnPtr`
+                ty::Bool
+                | ty::Char
+                | ty::Int(_)
+                | ty::Uint(_)
+                | ty::Float(_)
+                | ty::Adt(_, _)
+                | ty::Foreign(_)
+                | ty::Str
+                | ty::Array(_, _)
+                | ty::Slice(_)
+                | ty::RawPtr(_)
+                | ty::Ref(_, _, _)
+                | ty::Closure(_, _)
+                | ty::Generator(_, _, _)
+                | ty::GeneratorWitness(_)
+                | ty::GeneratorWitnessMIR(_, _)
+                | ty::Never
+                | ty::Tuple(_)
+                | ty::Error(_) => return true,
+                // FIXME: Function definitions could actually implement `FnPtr` by
+                // casting the ZST function def to a function pointer.
+                ty::FnDef(_, _) => return true,
+            }
+
+            // Generic params can implement `FnPtr` if the predicate
+            // holds within its own environment.
+            let obligation = Obligation::new(
+                self.tcx(),
+                obligation.cause.clone(),
+                obligation.param_env,
+                self.tcx().mk_predicate(obligation.predicate.map_bound(|mut pred| {
+                    pred.trait_ref =
+                        self.tcx().mk_trait_ref(fn_ptr_trait, [pred.trait_ref.self_ty()]);
+                    ty::PredicateKind::Clause(ty::Clause::Trait(pred))
+                })),
+            );
+            if let Ok(r) = self.infcx.evaluate_obligation(&obligation) {
+                if !r.may_apply() {
+                    return true;
+                }
+            }
+        }
+        false
+    }
+
     fn assemble_candidates_from_auto_impls(
         &mut self,
         obligation: &TraitObligation<'tcx>,
@@ -853,13 +956,50 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             return;
         }
 
-        let usize_layout =
-            self.tcx().layout_of(ty::ParamEnv::empty().and(self.tcx().types.usize)).unwrap().layout;
         if let Ok(layout) = self.tcx().layout_of(obligation.param_env.and(self_ty))
-            && layout.layout.size() == usize_layout.size()
-            && layout.layout.align().abi == usize_layout.align().abi
+            && layout.layout.size() == self.tcx().data_layout.pointer_size
+            && layout.layout.align().abi == self.tcx().data_layout.pointer_align.abi
         {
             candidates.vec.push(BuiltinCandidate { has_nested: false });
         }
     }
+
+    fn assemble_candidates_for_fn_ptr_trait(
+        &mut self,
+        obligation: &TraitObligation<'tcx>,
+        candidates: &mut SelectionCandidateSet<'tcx>,
+    ) {
+        let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
+        match self_ty.skip_binder().kind() {
+            ty::FnPtr(_) => candidates.vec.push(BuiltinCandidate { has_nested: false }),
+            ty::Bool
+            | ty::Char
+            | ty::Int(_)
+            | ty::Uint(_)
+            | ty::Float(_)
+            | ty::Adt(..)
+            | ty::Foreign(..)
+            | ty::Str
+            | ty::Array(..)
+            | ty::Slice(_)
+            | ty::RawPtr(_)
+            | ty::Ref(..)
+            | ty::FnDef(..)
+            | ty::Placeholder(..)
+            | ty::Dynamic(..)
+            | ty::Closure(..)
+            | ty::Generator(..)
+            | ty::GeneratorWitness(..)
+            | ty::GeneratorWitnessMIR(..)
+            | ty::Never
+            | ty::Tuple(..)
+            | ty::Alias(..)
+            | ty::Param(..)
+            | ty::Bound(..)
+            | ty::Error(_) => {}
+            ty::Infer(_) => {
+                candidates.ambiguous = true;
+            }
+        }
+    }
 }
diff --git a/compiler/rustc_trait_selection/src/traits/specialize/specialization_graph.rs b/compiler/rustc_trait_selection/src/traits/specialize/specialization_graph.rs
index 11eb968a415..aa5c624f471 100644
--- a/compiler/rustc_trait_selection/src/traits/specialize/specialization_graph.rs
+++ b/compiler/rustc_trait_selection/src/traits/specialize/specialization_graph.rs
@@ -21,6 +21,7 @@ pub struct FutureCompatOverlapError<'tcx> {
 }
 
 /// The result of attempting to insert an impl into a group of children.
+#[derive(Debug)]
 enum Inserted<'tcx> {
     /// The impl was inserted as a new child in this group of children.
     BecameNewSibling(Option<FutureCompatOverlapError<'tcx>>),
@@ -82,6 +83,7 @@ impl<'tcx> ChildrenExt<'tcx> for Children {
 
     /// Attempt to insert an impl into this set of children, while comparing for
     /// specialization relationships.
+    #[instrument(level = "debug", skip(self, tcx), ret)]
     fn insert(
         &mut self,
         tcx: TyCtxt<'tcx>,
@@ -92,18 +94,13 @@ impl<'tcx> ChildrenExt<'tcx> for Children {
         let mut last_lint = None;
         let mut replace_children = Vec::new();
 
-        debug!("insert(impl_def_id={:?}, simplified_self={:?})", impl_def_id, simplified_self,);
-
         let possible_siblings = match simplified_self {
             Some(st) => PotentialSiblings::Filtered(filtered_children(self, st)),
             None => PotentialSiblings::Unfiltered(iter_children(self)),
         };
 
         for possible_sibling in possible_siblings {
-            debug!(
-                "insert: impl_def_id={:?}, simplified_self={:?}, possible_sibling={:?}",
-                impl_def_id, simplified_self, possible_sibling,
-            );
+            debug!(?possible_sibling);
 
             let create_overlap_error = |overlap: traits::coherence::OverlapResult<'tcx>| {
                 let trait_ref = overlap.impl_header.trait_ref.unwrap();