Add a builtin `FnPtr` trait

5 files changed, 187 insertions, 9 deletions

diff --git a/compiler/rustc_trait_selection/src/solve/assembly.rs b/compiler/rustc_trait_selection/src/solve/assembly.rs
index 995fec78c40..8dad3f312c9 100644
--- a/compiler/rustc_trait_selection/src/solve/assembly.rs
+++ b/compiler/rustc_trait_selection/src/solve/assembly.rs
@@ -153,6 +153,12 @@ pub(super) trait GoalKind<'tcx>: TypeFoldable<TyCtxt<'tcx>> + Copy + Eq {
         goal: Goal<'tcx, Self>,
     ) -> QueryResult<'tcx>;
 
+    // A type is a `FnPtr` if it is of `FnPtr` type.
+    fn consider_builtin_fn_ptr_trait_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx>;
+
     // A callable type (a closure, fn def, or fn ptr) is known to implement the `Fn<A>`
     // family of traits where `A` is given by the signature of the type.
     fn consider_builtin_fn_trait_candidates(
@@ -331,6 +337,8 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
             G::consider_builtin_copy_clone_candidate(self, goal)
         } else if lang_items.pointer_like() == Some(trait_def_id) {
             G::consider_builtin_pointer_like_candidate(self, goal)
+        } else if lang_items.fn_ptr_trait() == Some(trait_def_id) {
+            G::consider_builtin_fn_ptr_trait_candidate(self, goal)
         } else if let Some(kind) = self.tcx().fn_trait_kind_from_def_id(trait_def_id) {
             G::consider_builtin_fn_trait_candidates(self, goal, kind)
         } else if lang_items.tuple_trait() == Some(trait_def_id) {
diff --git a/compiler/rustc_trait_selection/src/solve/project_goals.rs b/compiler/rustc_trait_selection/src/solve/project_goals.rs
index 14c5b83c6ca..2b104703aab 100644
--- a/compiler/rustc_trait_selection/src/solve/project_goals.rs
+++ b/compiler/rustc_trait_selection/src/solve/project_goals.rs
@@ -261,6 +261,13 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
         bug!("`PointerLike` does not have an associated type: {:?}", goal);
     }
 
+    fn consider_builtin_fn_ptr_trait_candidate(
+        _ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx> {
+        bug!("`FnPtr` does not have an associated type: {:?}", goal);
+    }
+
     fn consider_builtin_fn_trait_candidates(
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
diff --git a/compiler/rustc_trait_selection/src/solve/trait_goals.rs b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
index ade45d199f0..718c82c8f1f 100644
--- a/compiler/rustc_trait_selection/src/solve/trait_goals.rs
+++ b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
@@ -222,9 +222,8 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         let self_ty = tcx.erase_regions(goal.predicate.self_ty());
 
         if let Ok(layout) = tcx.layout_of(goal.param_env.and(self_ty))
-            &&  let usize_layout = tcx.layout_of(ty::ParamEnv::empty().and(tcx.types.usize)).unwrap().layout
-            && layout.layout.size() == usize_layout.size()
-            && layout.layout.align().abi == usize_layout.align().abi
+            && layout.layout.size() == tcx.data_layout.pointer_size
+            && layout.layout.align().abi == tcx.data_layout.pointer_align.abi
         {
             // FIXME: We could make this faster by making a no-constraints response
             ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
@@ -233,6 +232,17 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         }
     }
 
+    fn consider_builtin_fn_ptr_trait_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx> {
+        if let ty::FnPtr(..) = goal.predicate.self_ty().kind() {
+            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+        } else {
+            Err(NoSolution)
+        }
+    }
+
     fn consider_builtin_fn_trait_candidates(
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
diff --git a/compiler/rustc_trait_selection/src/traits/coherence.rs b/compiler/rustc_trait_selection/src/traits/coherence.rs
index 98e00e8223b..89e91eb298b 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;
+            }
+        }
+    }
 }