Suggest cloning and point out obligation errors on move error

When encountering a move error, look for implementations of `Clone` for
the moved type. If there is one, check if all its obligations are met.
If they are, we suggest cloning without caveats. If they aren't, we
suggest cloning while mentioning the unmet obligations, potentially
suggesting `#[derive(Clone)]` when appropriate.

```
error[E0507]: cannot move out of a shared reference
  --> $DIR/suggest-clone-when-some-obligation-is-unmet.rs:20:28
   |
LL |     let mut copy: Vec<U> = map.clone().into_values().collect();
   |                            ^^^^^^^^^^^ ------------- value moved due to this method call
   |                            |
   |                            move occurs because value has type `HashMap<T, U, Hash128_1>`, which does not implement the `Copy` trait
   |
note: `HashMap::<K, V, S>::into_values` takes ownership of the receiver `self`, which moves value
  --> $SRC_DIR/std/src/collections/hash/map.rs:LL:COL
help: you could `clone` the value and consume it, if the `Hash128_1: Clone` trait bound could be satisfied
   |
LL |     let mut copy: Vec<U> = <HashMap<T, U, Hash128_1> as Clone>::clone(&map.clone()).into_values().collect();
   |                            ++++++++++++++++++++++++++++++++++++++++++++           +
help: consider annotating `Hash128_1` with `#[derive(Clone)]`
   |
LL + #[derive(Clone)]
LL | pub struct Hash128_1;
   |
```

Fix #109429.

1 files changed, 124 insertions, 48 deletions

diff --git a/compiler/rustc_borrowck/src/diagnostics/mod.rs b/compiler/rustc_borrowck/src/diagnostics/mod.rs
index 31cb732cfd1..08c2a690b30 100644
--- a/compiler/rustc_borrowck/src/diagnostics/mod.rs
+++ b/compiler/rustc_borrowck/src/diagnostics/mod.rs
@@ -11,6 +11,7 @@ use rustc_hir::def::{CtorKind, Namespace};
 use rustc_hir::CoroutineKind;
 use rustc_index::IndexSlice;
 use rustc_infer::infer::BoundRegionConversionTime;
+use rustc_infer::traits::{FulfillmentErrorCode, SelectionError, TraitEngineExt};
 use rustc_middle::mir::tcx::PlaceTy;
 use rustc_middle::mir::{
     AggregateKind, CallSource, ConstOperand, FakeReadCause, Local, LocalInfo, LocalKind, Location,
@@ -24,7 +25,8 @@ use rustc_mir_dataflow::move_paths::{InitLocation, LookupResult};
 use rustc_span::def_id::LocalDefId;
 use rustc_span::{symbol::sym, Span, Symbol, DUMMY_SP};
 use rustc_target::abi::{FieldIdx, VariantIdx};
-use rustc_trait_selection::traits::query::evaluate_obligation::InferCtxtExt;
+use rustc_trait_selection::solve::FulfillmentCtxt;
+use rustc_trait_selection::traits::error_reporting::suggestions::TypeErrCtxtExt as _;
 use rustc_trait_selection::traits::{
     type_known_to_meet_bound_modulo_regions, Obligation, ObligationCause,
 };
@@ -1043,7 +1045,38 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
                 }
                 CallKind::Normal { self_arg, desugaring, method_did, method_args } => {
                     let self_arg = self_arg.unwrap();
+                    let mut has_sugg = false;
                     let tcx = self.infcx.tcx;
+                    // Avoid pointing to the same function in multiple different
+                    // error messages.
+                    if span != DUMMY_SP && self.fn_self_span_reported.insert(self_arg.span) {
+                        self.explain_iterator_advancement_in_for_loop_if_applicable(
+                            err,
+                            span,
+                            &move_spans,
+                        );
+
+                        let func = tcx.def_path_str(method_did);
+                        err.subdiagnostic(CaptureReasonNote::FuncTakeSelf {
+                            func,
+                            place_name: place_name.clone(),
+                            span: self_arg.span,
+                        });
+                    }
+                    let parent_did = tcx.parent(method_did);
+                    let parent_self_ty =
+                        matches!(tcx.def_kind(parent_did), rustc_hir::def::DefKind::Impl { .. })
+                            .then_some(parent_did)
+                            .and_then(|did| match tcx.type_of(did).instantiate_identity().kind() {
+                                ty::Adt(def, ..) => Some(def.did()),
+                                _ => None,
+                            });
+                    let is_option_or_result = parent_self_ty.is_some_and(|def_id| {
+                        matches!(tcx.get_diagnostic_name(def_id), Some(sym::Option | sym::Result))
+                    });
+                    if is_option_or_result && maybe_reinitialized_locations_is_empty {
+                        err.subdiagnostic(CaptureReasonLabel::BorrowContent { var_span });
+                    }
                     if let Some((CallDesugaringKind::ForLoopIntoIter, _)) = desugaring {
                         let ty = moved_place.ty(self.body, tcx).ty;
                         let suggest = match tcx.get_diagnostic_item(sym::IntoIterator) {
@@ -1108,7 +1141,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
                         // Erase and shadow everything that could be passed to the new infcx.
                         let ty = moved_place.ty(self.body, tcx).ty;
 
-                        if let ty::Adt(def, args) = ty.kind()
+                        if let ty::Adt(def, args) = ty.peel_refs().kind()
                             && Some(def.did()) == tcx.lang_items().pin_type()
                             && let ty::Ref(_, _, hir::Mutability::Mut) = args.type_at(0).kind()
                             && let self_ty = self.infcx.instantiate_binder_with_fresh_vars(
@@ -1124,17 +1157,9 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
                                     span: move_span.shrink_to_hi(),
                                 },
                             );
+                            has_sugg = true;
                         }
-                        if let Some(clone_trait) = tcx.lang_items().clone_trait()
-                            && let trait_ref = ty::TraitRef::new(tcx, clone_trait, [ty])
-                            && let o = Obligation::new(
-                                tcx,
-                                ObligationCause::dummy(),
-                                self.param_env,
-                                ty::Binder::dummy(trait_ref),
-                            )
-                            && self.infcx.predicate_must_hold_modulo_regions(&o)
-                        {
+                        if let Some(clone_trait) = tcx.lang_items().clone_trait() {
                             let sugg = if moved_place
                                 .iter_projections()
                                 .any(|(_, elem)| matches!(elem, ProjectionElem::Deref))
@@ -1150,43 +1175,94 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
                             } else {
                                 vec![(move_span.shrink_to_hi(), ".clone()".to_string())]
                             };
-                            err.multipart_suggestion_verbose(
-                                "you can `clone` the value and consume it, but this might not be \
-                                 your desired behavior",
-                                sugg,
-                                Applicability::MaybeIncorrect,
-                            );
-                        }
-                    }
-                    // Avoid pointing to the same function in multiple different
-                    // error messages.
-                    if span != DUMMY_SP && self.fn_self_span_reported.insert(self_arg.span) {
-                        self.explain_iterator_advancement_in_for_loop_if_applicable(
-                            err,
-                            span,
-                            &move_spans,
-                        );
-
-                        let func = tcx.def_path_str(method_did);
-                        err.subdiagnostic(CaptureReasonNote::FuncTakeSelf {
-                            func,
-                            place_name,
-                            span: self_arg.span,
-                        });
-                    }
-                    let parent_did = tcx.parent(method_did);
-                    let parent_self_ty =
-                        matches!(tcx.def_kind(parent_did), rustc_hir::def::DefKind::Impl { .. })
-                            .then_some(parent_did)
-                            .and_then(|did| match tcx.type_of(did).instantiate_identity().kind() {
-                                ty::Adt(def, ..) => Some(def.did()),
-                                _ => None,
+                            self.infcx.probe(|_snapshot| {
+                                if let ty::Adt(def, args) = ty.kind()
+                                    && !has_sugg
+                                    && let Some((def_id, _imp)) = tcx
+                                        .all_impls(clone_trait)
+                                        .filter_map(|def_id| {
+                                            tcx.impl_trait_ref(def_id).map(|r| (def_id, r))
+                                        })
+                                        .map(|(def_id, imp)| (def_id, imp.skip_binder()))
+                                        .filter(|(_, imp)| match imp.self_ty().peel_refs().kind() {
+                                            ty::Adt(i_def, _) if i_def.did() == def.did() => true,
+                                            _ => false,
+                                        })
+                                        .next()
+                                {
+                                    let mut fulfill_cx = FulfillmentCtxt::new(self.infcx);
+                                    // We get all obligations from the impl to talk about specific
+                                    // trait bounds.
+                                    let obligations = tcx
+                                        .predicates_of(def_id)
+                                        .instantiate(tcx, args)
+                                        .into_iter()
+                                        .map(|(clause, span)| {
+                                            Obligation::new(
+                                                tcx,
+                                                ObligationCause::misc(
+                                                    span,
+                                                    self.body.source.def_id().expect_local(),
+                                                ),
+                                                self.param_env,
+                                                clause,
+                                            )
+                                        })
+                                        .collect::<Vec<_>>();
+                                    fulfill_cx
+                                        .register_predicate_obligations(self.infcx, obligations);
+                                    let errors = fulfill_cx.select_all_or_error(self.infcx);
+                                    let msg = match &errors[..] {
+                                        [] => "you can `clone` the value and consume it, but this \
+                                               might not be your desired behavior"
+                                            .to_string(),
+                                        [error] => {
+                                            format!(
+                                                "you could `clone` the value and consume it, if \
+                                                 the `{}` trait bound could be satisfied",
+                                                error.obligation.predicate,
+                                            )
+                                        }
+                                        [errors @ .., last] => {
+                                            format!(
+                                                "you could `clone` the value and consume it, if \
+                                                 the following trait bounds could be satisfied: {} \
+                                                 and `{}`",
+                                                errors
+                                                    .iter()
+                                                    .map(|e| format!(
+                                                        "`{}`",
+                                                        e.obligation.predicate
+                                                    ))
+                                                    .collect::<Vec<_>>()
+                                                    .join(", "),
+                                                last.obligation.predicate,
+                                            )
+                                        }
+                                    };
+                                    err.multipart_suggestion_verbose(
+                                        msg,
+                                        sugg.clone(),
+                                        Applicability::MaybeIncorrect,
+                                    );
+                                    for error in errors {
+                                        if let FulfillmentErrorCode::CodeSelectionError(
+                                            SelectionError::Unimplemented,
+                                        ) = error.code
+                                            && let ty::PredicateKind::Clause(ty::ClauseKind::Trait(
+                                                pred,
+                                            )) = error.obligation.predicate.kind().skip_binder()
+                                        {
+                                            self.infcx.err_ctxt().suggest_derive(
+                                                &error.obligation,
+                                                err,
+                                                error.obligation.predicate.kind().rebind(pred),
+                                            );
+                                        }
+                                    }
+                                }
                             });
-                    let is_option_or_result = parent_self_ty.is_some_and(|def_id| {
-                        matches!(tcx.get_diagnostic_name(def_id), Some(sym::Option | sym::Result))
-                    });
-                    if is_option_or_result && maybe_reinitialized_locations_is_empty {
-                        err.subdiagnostic(CaptureReasonLabel::BorrowContent { var_span });
+                        }
                     }
                 }
                 // Other desugarings takes &self, which cannot cause a move