rustc_next_trait_solver/solve/assembly/
structural_traits.rs

1//! Code which is used by built-in goals that match "structurally", such a auto
2//! traits, `Copy`/`Clone`.
3
4use derive_where::derive_where;
5use rustc_type_ir::data_structures::HashMap;
6use rustc_type_ir::inherent::*;
7use rustc_type_ir::lang_items::TraitSolverLangItem;
8use rustc_type_ir::solve::inspect::ProbeKind;
9use rustc_type_ir::{
10    self as ty, FallibleTypeFolder, Interner, Movability, Mutability, TypeFoldable,
11    TypeSuperFoldable, Upcast as _, elaborate,
12};
13use rustc_type_ir_macros::{TypeFoldable_Generic, TypeVisitable_Generic};
14use tracing::instrument;
15
16use crate::delegate::SolverDelegate;
17use crate::solve::{AdtDestructorKind, EvalCtxt, Goal, NoSolution};
18
19// Calculates the constituent types of a type for `auto trait` purposes.
20#[instrument(level = "trace", skip(ecx), ret)]
21pub(in crate::solve) fn instantiate_constituent_tys_for_auto_trait<D, I>(
22    ecx: &EvalCtxt<'_, D>,
23    ty: I::Ty,
24) -> Result<ty::Binder<I, Vec<I::Ty>>, NoSolution>
25where
26    D: SolverDelegate<Interner = I>,
27    I: Interner,
28{
29    let cx = ecx.cx();
30    match ty.kind() {
31        ty::Uint(_)
32        | ty::Int(_)
33        | ty::Bool
34        | ty::Float(_)
35        | ty::FnDef(..)
36        | ty::FnPtr(..)
37        | ty::Error(_)
38        | ty::Never
39        | ty::Char => Ok(ty::Binder::dummy(vec![])),
40
41        // This branch is only for `experimental_default_bounds`.
42        // Other foreign types were rejected earlier in
43        // `disqualify_auto_trait_candidate_due_to_possible_impl`.
44        ty::Foreign(..) => Ok(ty::Binder::dummy(vec![])),
45
46        // Treat `str` like it's defined as `struct str([u8]);`
47        ty::Str => Ok(ty::Binder::dummy(vec![Ty::new_slice(cx, Ty::new_u8(cx))])),
48
49        ty::Dynamic(..)
50        | ty::Param(..)
51        | ty::Alias(ty::Projection | ty::Inherent | ty::Free, ..)
52        | ty::Placeholder(..)
53        | ty::Bound(..)
54        | ty::Infer(_) => {
55            panic!("unexpected type `{ty:?}`")
56        }
57
58        ty::RawPtr(element_ty, _) | ty::Ref(_, element_ty, _) => {
59            Ok(ty::Binder::dummy(vec![element_ty]))
60        }
61
62        ty::Pat(element_ty, _) | ty::Array(element_ty, _) | ty::Slice(element_ty) => {
63            Ok(ty::Binder::dummy(vec![element_ty]))
64        }
65
66        ty::Tuple(tys) => {
67            // (T1, ..., Tn) -- meets any bound that all of T1...Tn meet
68            Ok(ty::Binder::dummy(tys.to_vec()))
69        }
70
71        ty::Closure(_, args) => Ok(ty::Binder::dummy(vec![args.as_closure().tupled_upvars_ty()])),
72
73        ty::CoroutineClosure(_, args) => {
74            Ok(ty::Binder::dummy(vec![args.as_coroutine_closure().tupled_upvars_ty()]))
75        }
76
77        ty::Coroutine(_, args) => {
78            let coroutine_args = args.as_coroutine();
79            Ok(ty::Binder::dummy(vec![coroutine_args.tupled_upvars_ty(), coroutine_args.witness()]))
80        }
81
82        ty::CoroutineWitness(def_id, args) => Ok(ecx
83            .cx()
84            .coroutine_hidden_types(def_id)
85            .instantiate(cx, args)
86            .map_bound(|bound| bound.types.to_vec())),
87
88        ty::UnsafeBinder(bound_ty) => Ok(bound_ty.map_bound(|ty| vec![ty])),
89
90        // For `PhantomData<T>`, we pass `T`.
91        ty::Adt(def, args) if def.is_phantom_data() => Ok(ty::Binder::dummy(vec![args.type_at(0)])),
92
93        ty::Adt(def, args) => {
94            Ok(ty::Binder::dummy(def.all_field_tys(cx).iter_instantiated(cx, args).collect()))
95        }
96
97        ty::Alias(ty::Opaque, ty::AliasTy { def_id, args, .. }) => {
98            // We can resolve the `impl Trait` to its concrete type,
99            // which enforces a DAG between the functions requiring
100            // the auto trait bounds in question.
101            Ok(ty::Binder::dummy(vec![cx.type_of(def_id).instantiate(cx, args)]))
102        }
103    }
104}
105
106#[instrument(level = "trace", skip(ecx), ret)]
107pub(in crate::solve) fn instantiate_constituent_tys_for_sized_trait<D, I>(
108    ecx: &EvalCtxt<'_, D>,
109    ty: I::Ty,
110) -> Result<ty::Binder<I, Vec<I::Ty>>, NoSolution>
111where
112    D: SolverDelegate<Interner = I>,
113    I: Interner,
114{
115    match ty.kind() {
116        // impl Sized for u*, i*, bool, f*, FnDef, FnPtr, *(const/mut) T, char, &mut? T, [T; N], dyn* Trait, !
117        // impl Sized for Coroutine, CoroutineWitness, Closure, CoroutineClosure
118        ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
119        | ty::Uint(_)
120        | ty::Int(_)
121        | ty::Bool
122        | ty::Float(_)
123        | ty::FnDef(..)
124        | ty::FnPtr(..)
125        | ty::RawPtr(..)
126        | ty::Char
127        | ty::Ref(..)
128        | ty::Coroutine(..)
129        | ty::CoroutineWitness(..)
130        | ty::Array(..)
131        | ty::Pat(..)
132        | ty::Closure(..)
133        | ty::CoroutineClosure(..)
134        | ty::Never
135        | ty::Dynamic(_, _, ty::DynStar)
136        | ty::Error(_) => Ok(ty::Binder::dummy(vec![])),
137
138        ty::Str
139        | ty::Slice(_)
140        | ty::Dynamic(..)
141        | ty::Foreign(..)
142        | ty::Alias(..)
143        | ty::Param(_)
144        | ty::Placeholder(..) => Err(NoSolution),
145
146        ty::Bound(..)
147        | ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => {
148            panic!("unexpected type `{ty:?}`")
149        }
150
151        ty::UnsafeBinder(bound_ty) => Ok(bound_ty.map_bound(|ty| vec![ty])),
152
153        // impl Sized for ()
154        // impl Sized for (T1, T2, .., Tn) where Tn: Sized if n >= 1
155        ty::Tuple(tys) => Ok(ty::Binder::dummy(tys.last().map_or_else(Vec::new, |ty| vec![ty]))),
156
157        // impl Sized for Adt<Args...> where sized_constraint(Adt)<Args...>: Sized
158        //   `sized_constraint(Adt)` is the deepest struct trail that can be determined
159        //   by the definition of `Adt`, independent of the generic args.
160        // impl Sized for Adt<Args...> if sized_constraint(Adt) == None
161        //   As a performance optimization, `sized_constraint(Adt)` can return `None`
162        //   if the ADTs definition implies that it is sized by for all possible args.
163        //   In this case, the builtin impl will have no nested subgoals. This is a
164        //   "best effort" optimization and `sized_constraint` may return `Some`, even
165        //   if the ADT is sized for all possible args.
166        ty::Adt(def, args) => {
167            if let Some(sized_crit) = def.sized_constraint(ecx.cx()) {
168                Ok(ty::Binder::dummy(vec![sized_crit.instantiate(ecx.cx(), args)]))
169            } else {
170                Ok(ty::Binder::dummy(vec![]))
171            }
172        }
173    }
174}
175
176#[instrument(level = "trace", skip(ecx), ret)]
177pub(in crate::solve) fn instantiate_constituent_tys_for_copy_clone_trait<D, I>(
178    ecx: &EvalCtxt<'_, D>,
179    ty: I::Ty,
180) -> Result<ty::Binder<I, Vec<I::Ty>>, NoSolution>
181where
182    D: SolverDelegate<Interner = I>,
183    I: Interner,
184{
185    match ty.kind() {
186        // impl Copy/Clone for FnDef, FnPtr
187        ty::FnDef(..) | ty::FnPtr(..) | ty::Error(_) => Ok(ty::Binder::dummy(vec![])),
188
189        // Implementations are provided in core
190        ty::Uint(_)
191        | ty::Int(_)
192        | ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
193        | ty::Bool
194        | ty::Float(_)
195        | ty::Char
196        | ty::RawPtr(..)
197        | ty::Never
198        | ty::Ref(_, _, Mutability::Not)
199        | ty::Array(..) => Err(NoSolution),
200
201        // Cannot implement in core, as we can't be generic over patterns yet,
202        // so we'd have to list all patterns and type combinations.
203        ty::Pat(ty, ..) => Ok(ty::Binder::dummy(vec![ty])),
204
205        ty::Dynamic(..)
206        | ty::Str
207        | ty::Slice(_)
208        | ty::Foreign(..)
209        | ty::Ref(_, _, Mutability::Mut)
210        | ty::Adt(_, _)
211        | ty::Alias(_, _)
212        | ty::Param(_)
213        | ty::Placeholder(..) => Err(NoSolution),
214
215        ty::Bound(..)
216        | ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => {
217            panic!("unexpected type `{ty:?}`")
218        }
219
220        // impl Copy/Clone for (T1, T2, .., Tn) where T1: Copy/Clone, T2: Copy/Clone, .. Tn: Copy/Clone
221        ty::Tuple(tys) => Ok(ty::Binder::dummy(tys.to_vec())),
222
223        // impl Copy/Clone for Closure where Self::TupledUpvars: Copy/Clone
224        ty::Closure(_, args) => Ok(ty::Binder::dummy(vec![args.as_closure().tupled_upvars_ty()])),
225
226        // impl Copy/Clone for CoroutineClosure where Self::TupledUpvars: Copy/Clone
227        ty::CoroutineClosure(_, args) => {
228            Ok(ty::Binder::dummy(vec![args.as_coroutine_closure().tupled_upvars_ty()]))
229        }
230
231        // only when `coroutine_clone` is enabled and the coroutine is movable
232        // impl Copy/Clone for Coroutine where T: Copy/Clone forall T in (upvars, witnesses)
233        ty::Coroutine(def_id, args) => match ecx.cx().coroutine_movability(def_id) {
234            Movability::Static => Err(NoSolution),
235            Movability::Movable => {
236                if ecx.cx().features().coroutine_clone() {
237                    let coroutine = args.as_coroutine();
238                    Ok(ty::Binder::dummy(vec![coroutine.tupled_upvars_ty(), coroutine.witness()]))
239                } else {
240                    Err(NoSolution)
241                }
242            }
243        },
244
245        ty::UnsafeBinder(_) => Err(NoSolution),
246
247        // impl Copy/Clone for CoroutineWitness where T: Copy/Clone forall T in coroutine_hidden_types
248        ty::CoroutineWitness(def_id, args) => Ok(ecx
249            .cx()
250            .coroutine_hidden_types(def_id)
251            .instantiate(ecx.cx(), args)
252            .map_bound(|bound| bound.types.to_vec())),
253    }
254}
255
256// Returns a binder of the tupled inputs types and output type from a builtin callable type.
257pub(in crate::solve) fn extract_tupled_inputs_and_output_from_callable<I: Interner>(
258    cx: I,
259    self_ty: I::Ty,
260    goal_kind: ty::ClosureKind,
261) -> Result<Option<ty::Binder<I, (I::Ty, I::Ty)>>, NoSolution> {
262    match self_ty.kind() {
263        // keep this in sync with assemble_fn_pointer_candidates until the old solver is removed.
264        ty::FnDef(def_id, args) => {
265            let sig = cx.fn_sig(def_id);
266            if sig.skip_binder().is_fn_trait_compatible() && !cx.has_target_features(def_id) {
267                Ok(Some(
268                    sig.instantiate(cx, args)
269                        .map_bound(|sig| (Ty::new_tup(cx, sig.inputs().as_slice()), sig.output())),
270                ))
271            } else {
272                Err(NoSolution)
273            }
274        }
275        // keep this in sync with assemble_fn_pointer_candidates until the old solver is removed.
276        ty::FnPtr(sig_tys, hdr) => {
277            let sig = sig_tys.with(hdr);
278            if sig.is_fn_trait_compatible() {
279                Ok(Some(
280                    sig.map_bound(|sig| (Ty::new_tup(cx, sig.inputs().as_slice()), sig.output())),
281                ))
282            } else {
283                Err(NoSolution)
284            }
285        }
286        ty::Closure(_, args) => {
287            let closure_args = args.as_closure();
288            match closure_args.kind_ty().to_opt_closure_kind() {
289                // If the closure's kind doesn't extend the goal kind,
290                // then the closure doesn't implement the trait.
291                Some(closure_kind) => {
292                    if !closure_kind.extends(goal_kind) {
293                        return Err(NoSolution);
294                    }
295                }
296                // Closure kind is not yet determined, so we return ambiguity unless
297                // the expected kind is `FnOnce` as that is always implemented.
298                None => {
299                    if goal_kind != ty::ClosureKind::FnOnce {
300                        return Ok(None);
301                    }
302                }
303            }
304            Ok(Some(
305                closure_args.sig().map_bound(|sig| (sig.inputs().get(0).unwrap(), sig.output())),
306            ))
307        }
308
309        // Coroutine-closures don't implement `Fn` traits the normal way.
310        // Instead, they always implement `FnOnce`, but only implement
311        // `FnMut`/`Fn` if they capture no upvars, since those may borrow
312        // from the closure.
313        ty::CoroutineClosure(def_id, args) => {
314            let args = args.as_coroutine_closure();
315            let kind_ty = args.kind_ty();
316            let sig = args.coroutine_closure_sig().skip_binder();
317
318            // FIXME: let_chains
319            let kind = kind_ty.to_opt_closure_kind();
320            let coroutine_ty = if kind.is_some() && !args.tupled_upvars_ty().is_ty_var() {
321                let closure_kind = kind.unwrap();
322                if !closure_kind.extends(goal_kind) {
323                    return Err(NoSolution);
324                }
325
326                // A coroutine-closure implements `FnOnce` *always*, since it may
327                // always be called once. It additionally implements `Fn`/`FnMut`
328                // only if it has no upvars referencing the closure-env lifetime,
329                // and if the closure kind permits it.
330                if goal_kind != ty::ClosureKind::FnOnce && args.has_self_borrows() {
331                    return Err(NoSolution);
332                }
333
334                coroutine_closure_to_certain_coroutine(
335                    cx,
336                    goal_kind,
337                    // No captures by ref, so this doesn't matter.
338                    Region::new_static(cx),
339                    def_id,
340                    args,
341                    sig,
342                )
343            } else {
344                // Closure kind is not yet determined, so we return ambiguity unless
345                // the expected kind is `FnOnce` as that is always implemented.
346                if goal_kind != ty::ClosureKind::FnOnce {
347                    return Ok(None);
348                }
349
350                coroutine_closure_to_ambiguous_coroutine(
351                    cx,
352                    goal_kind, // No captures by ref, so this doesn't matter.
353                    Region::new_static(cx),
354                    def_id,
355                    args,
356                    sig,
357                )
358            };
359
360            Ok(Some(args.coroutine_closure_sig().rebind((sig.tupled_inputs_ty, coroutine_ty))))
361        }
362
363        ty::Bool
364        | ty::Char
365        | ty::Int(_)
366        | ty::Uint(_)
367        | ty::Float(_)
368        | ty::Adt(_, _)
369        | ty::Foreign(_)
370        | ty::Str
371        | ty::Array(_, _)
372        | ty::Slice(_)
373        | ty::RawPtr(_, _)
374        | ty::Ref(_, _, _)
375        | ty::Dynamic(_, _, _)
376        | ty::Coroutine(_, _)
377        | ty::CoroutineWitness(..)
378        | ty::Never
379        | ty::Tuple(_)
380        | ty::Pat(_, _)
381        | ty::UnsafeBinder(_)
382        | ty::Alias(_, _)
383        | ty::Param(_)
384        | ty::Placeholder(..)
385        | ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
386        | ty::Error(_) => Err(NoSolution),
387
388        ty::Bound(..)
389        | ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => {
390            panic!("unexpected type `{self_ty:?}`")
391        }
392    }
393}
394
395/// Relevant types for an async callable, including its inputs, output,
396/// and the return type you get from awaiting the output.
397#[derive_where(Clone, Copy, Debug; I: Interner)]
398#[derive(TypeVisitable_Generic, TypeFoldable_Generic)]
399pub(in crate::solve) struct AsyncCallableRelevantTypes<I: Interner> {
400    pub tupled_inputs_ty: I::Ty,
401    /// Type returned by calling the closure
402    /// i.e. `f()`.
403    pub output_coroutine_ty: I::Ty,
404    /// Type returned by `await`ing the output
405    /// i.e. `f().await`.
406    pub coroutine_return_ty: I::Ty,
407}
408
409// Returns a binder of the tupled inputs types, output type, and coroutine type
410// from a builtin coroutine-closure type. If we don't yet know the closure kind of
411// the coroutine-closure, emit an additional trait predicate for `AsyncFnKindHelper`
412// which enforces the closure is actually callable with the given trait. When we
413// know the kind already, we can short-circuit this check.
414pub(in crate::solve) fn extract_tupled_inputs_and_output_from_async_callable<I: Interner>(
415    cx: I,
416    self_ty: I::Ty,
417    goal_kind: ty::ClosureKind,
418    env_region: I::Region,
419) -> Result<(ty::Binder<I, AsyncCallableRelevantTypes<I>>, Vec<I::Predicate>), NoSolution> {
420    match self_ty.kind() {
421        ty::CoroutineClosure(def_id, args) => {
422            let args = args.as_coroutine_closure();
423            let kind_ty = args.kind_ty();
424            let sig = args.coroutine_closure_sig().skip_binder();
425            let mut nested = vec![];
426
427            // FIXME: let_chains
428            let kind = kind_ty.to_opt_closure_kind();
429            let coroutine_ty = if kind.is_some() && !args.tupled_upvars_ty().is_ty_var() {
430                if !kind.unwrap().extends(goal_kind) {
431                    return Err(NoSolution);
432                }
433
434                coroutine_closure_to_certain_coroutine(cx, goal_kind, env_region, def_id, args, sig)
435            } else {
436                // When we don't know the closure kind (and therefore also the closure's upvars,
437                // which are computed at the same time), we must delay the computation of the
438                // generator's upvars. We do this using the `AsyncFnKindHelper`, which as a trait
439                // goal functions similarly to the old `ClosureKind` predicate, and ensures that
440                // the goal kind <= the closure kind. As a projection `AsyncFnKindHelper::Upvars`
441                // will project to the right upvars for the generator, appending the inputs and
442                // coroutine upvars respecting the closure kind.
443                nested.push(
444                    ty::TraitRef::new(
445                        cx,
446                        cx.require_lang_item(TraitSolverLangItem::AsyncFnKindHelper),
447                        [kind_ty, Ty::from_closure_kind(cx, goal_kind)],
448                    )
449                    .upcast(cx),
450                );
451
452                coroutine_closure_to_ambiguous_coroutine(
453                    cx, goal_kind, env_region, def_id, args, sig,
454                )
455            };
456
457            Ok((
458                args.coroutine_closure_sig().rebind(AsyncCallableRelevantTypes {
459                    tupled_inputs_ty: sig.tupled_inputs_ty,
460                    output_coroutine_ty: coroutine_ty,
461                    coroutine_return_ty: sig.return_ty,
462                }),
463                nested,
464            ))
465        }
466
467        ty::FnDef(def_id, _) => {
468            let sig = self_ty.fn_sig(cx);
469            if sig.is_fn_trait_compatible() && !cx.has_target_features(def_id) {
470                fn_item_to_async_callable(cx, sig)
471            } else {
472                Err(NoSolution)
473            }
474        }
475        ty::FnPtr(..) => {
476            let sig = self_ty.fn_sig(cx);
477            if sig.is_fn_trait_compatible() {
478                fn_item_to_async_callable(cx, sig)
479            } else {
480                Err(NoSolution)
481            }
482        }
483
484        ty::Closure(_, args) => {
485            let args = args.as_closure();
486            let bound_sig = args.sig();
487            let sig = bound_sig.skip_binder();
488            let future_trait_def_id = cx.require_lang_item(TraitSolverLangItem::Future);
489            // `Closure`s only implement `AsyncFn*` when their return type
490            // implements `Future`.
491            let mut nested = vec![
492                bound_sig
493                    .rebind(ty::TraitRef::new(cx, future_trait_def_id, [sig.output()]))
494                    .upcast(cx),
495            ];
496
497            // Additionally, we need to check that the closure kind
498            // is still compatible.
499            let kind_ty = args.kind_ty();
500            if let Some(closure_kind) = kind_ty.to_opt_closure_kind() {
501                if !closure_kind.extends(goal_kind) {
502                    return Err(NoSolution);
503                }
504            } else {
505                let async_fn_kind_trait_def_id =
506                    cx.require_lang_item(TraitSolverLangItem::AsyncFnKindHelper);
507                // When we don't know the closure kind (and therefore also the closure's upvars,
508                // which are computed at the same time), we must delay the computation of the
509                // generator's upvars. We do this using the `AsyncFnKindHelper`, which as a trait
510                // goal functions similarly to the old `ClosureKind` predicate, and ensures that
511                // the goal kind <= the closure kind. As a projection `AsyncFnKindHelper::Upvars`
512                // will project to the right upvars for the generator, appending the inputs and
513                // coroutine upvars respecting the closure kind.
514                nested.push(
515                    ty::TraitRef::new(
516                        cx,
517                        async_fn_kind_trait_def_id,
518                        [kind_ty, Ty::from_closure_kind(cx, goal_kind)],
519                    )
520                    .upcast(cx),
521                );
522            }
523
524            let future_output_def_id = cx.require_lang_item(TraitSolverLangItem::FutureOutput);
525            let future_output_ty = Ty::new_projection(cx, future_output_def_id, [sig.output()]);
526            Ok((
527                bound_sig.rebind(AsyncCallableRelevantTypes {
528                    tupled_inputs_ty: sig.inputs().get(0).unwrap(),
529                    output_coroutine_ty: sig.output(),
530                    coroutine_return_ty: future_output_ty,
531                }),
532                nested,
533            ))
534        }
535
536        ty::Bool
537        | ty::Char
538        | ty::Int(_)
539        | ty::Uint(_)
540        | ty::Float(_)
541        | ty::Adt(_, _)
542        | ty::Foreign(_)
543        | ty::Str
544        | ty::Array(_, _)
545        | ty::Pat(_, _)
546        | ty::Slice(_)
547        | ty::RawPtr(_, _)
548        | ty::Ref(_, _, _)
549        | ty::Dynamic(_, _, _)
550        | ty::Coroutine(_, _)
551        | ty::CoroutineWitness(..)
552        | ty::Never
553        | ty::UnsafeBinder(_)
554        | ty::Tuple(_)
555        | ty::Alias(_, _)
556        | ty::Param(_)
557        | ty::Placeholder(..)
558        | ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
559        | ty::Error(_) => Err(NoSolution),
560
561        ty::Bound(..)
562        | ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => {
563            panic!("unexpected type `{self_ty:?}`")
564        }
565    }
566}
567
568fn fn_item_to_async_callable<I: Interner>(
569    cx: I,
570    bound_sig: ty::Binder<I, ty::FnSig<I>>,
571) -> Result<(ty::Binder<I, AsyncCallableRelevantTypes<I>>, Vec<I::Predicate>), NoSolution> {
572    let sig = bound_sig.skip_binder();
573    let future_trait_def_id = cx.require_lang_item(TraitSolverLangItem::Future);
574    // `FnDef` and `FnPtr` only implement `AsyncFn*` when their
575    // return type implements `Future`.
576    let nested = vec![
577        bound_sig.rebind(ty::TraitRef::new(cx, future_trait_def_id, [sig.output()])).upcast(cx),
578    ];
579    let future_output_def_id = cx.require_lang_item(TraitSolverLangItem::FutureOutput);
580    let future_output_ty = Ty::new_projection(cx, future_output_def_id, [sig.output()]);
581    Ok((
582        bound_sig.rebind(AsyncCallableRelevantTypes {
583            tupled_inputs_ty: Ty::new_tup(cx, sig.inputs().as_slice()),
584            output_coroutine_ty: sig.output(),
585            coroutine_return_ty: future_output_ty,
586        }),
587        nested,
588    ))
589}
590
591/// Given a coroutine-closure, project to its returned coroutine when we are *certain*
592/// that the closure's kind is compatible with the goal.
593fn coroutine_closure_to_certain_coroutine<I: Interner>(
594    cx: I,
595    goal_kind: ty::ClosureKind,
596    goal_region: I::Region,
597    def_id: I::DefId,
598    args: ty::CoroutineClosureArgs<I>,
599    sig: ty::CoroutineClosureSignature<I>,
600) -> I::Ty {
601    sig.to_coroutine_given_kind_and_upvars(
602        cx,
603        args.parent_args(),
604        cx.coroutine_for_closure(def_id),
605        goal_kind,
606        goal_region,
607        args.tupled_upvars_ty(),
608        args.coroutine_captures_by_ref_ty(),
609    )
610}
611
612/// Given a coroutine-closure, project to its returned coroutine when we are *not certain*
613/// that the closure's kind is compatible with the goal, and therefore also don't know
614/// yet what the closure's upvars are.
615///
616/// Note that we do not also push a `AsyncFnKindHelper` goal here.
617fn coroutine_closure_to_ambiguous_coroutine<I: Interner>(
618    cx: I,
619    goal_kind: ty::ClosureKind,
620    goal_region: I::Region,
621    def_id: I::DefId,
622    args: ty::CoroutineClosureArgs<I>,
623    sig: ty::CoroutineClosureSignature<I>,
624) -> I::Ty {
625    let upvars_projection_def_id = cx.require_lang_item(TraitSolverLangItem::AsyncFnKindUpvars);
626    let tupled_upvars_ty = Ty::new_projection(
627        cx,
628        upvars_projection_def_id,
629        [
630            I::GenericArg::from(args.kind_ty()),
631            Ty::from_closure_kind(cx, goal_kind).into(),
632            goal_region.into(),
633            sig.tupled_inputs_ty.into(),
634            args.tupled_upvars_ty().into(),
635            args.coroutine_captures_by_ref_ty().into(),
636        ],
637    );
638    sig.to_coroutine(
639        cx,
640        args.parent_args(),
641        Ty::from_closure_kind(cx, goal_kind),
642        cx.coroutine_for_closure(def_id),
643        tupled_upvars_ty,
644    )
645}
646
647/// This duplicates `extract_tupled_inputs_and_output_from_callable` but needs
648/// to return different information (namely, the def id and args) so that we can
649/// create const conditions.
650///
651/// Doing so on all calls to `extract_tupled_inputs_and_output_from_callable`
652/// would be wasteful.
653pub(in crate::solve) fn extract_fn_def_from_const_callable<I: Interner>(
654    cx: I,
655    self_ty: I::Ty,
656) -> Result<(ty::Binder<I, (I::FnInputTys, I::Ty)>, I::DefId, I::GenericArgs), NoSolution> {
657    match self_ty.kind() {
658        ty::FnDef(def_id, args) => {
659            let sig = cx.fn_sig(def_id);
660            if sig.skip_binder().is_fn_trait_compatible()
661                && !cx.has_target_features(def_id)
662                && cx.fn_is_const(def_id)
663            {
664                Ok((
665                    sig.instantiate(cx, args).map_bound(|sig| (sig.inputs(), sig.output())),
666                    def_id,
667                    args,
668                ))
669            } else {
670                return Err(NoSolution);
671            }
672        }
673        // `FnPtr`s are not const for now.
674        ty::FnPtr(..) => {
675            return Err(NoSolution);
676        }
677        // `Closure`s are not const for now.
678        ty::Closure(..) => {
679            return Err(NoSolution);
680        }
681        // `CoroutineClosure`s are not const for now.
682        ty::CoroutineClosure(..) => {
683            return Err(NoSolution);
684        }
685
686        ty::Bool
687        | ty::Char
688        | ty::Int(_)
689        | ty::Uint(_)
690        | ty::Float(_)
691        | ty::Adt(_, _)
692        | ty::Foreign(_)
693        | ty::Str
694        | ty::Array(_, _)
695        | ty::Slice(_)
696        | ty::RawPtr(_, _)
697        | ty::Ref(_, _, _)
698        | ty::Dynamic(_, _, _)
699        | ty::Coroutine(_, _)
700        | ty::CoroutineWitness(..)
701        | ty::Never
702        | ty::Tuple(_)
703        | ty::Pat(_, _)
704        | ty::Alias(_, _)
705        | ty::Param(_)
706        | ty::Placeholder(..)
707        | ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
708        | ty::Error(_)
709        | ty::UnsafeBinder(_) => return Err(NoSolution),
710
711        ty::Bound(..)
712        | ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => {
713            panic!("unexpected type `{self_ty:?}`")
714        }
715    }
716}
717
718// NOTE: Keep this in sync with `evaluate_host_effect_for_destruct_goal` in
719// the old solver, for as long as that exists.
720pub(in crate::solve) fn const_conditions_for_destruct<I: Interner>(
721    cx: I,
722    self_ty: I::Ty,
723) -> Result<Vec<ty::TraitRef<I>>, NoSolution> {
724    let destruct_def_id = cx.require_lang_item(TraitSolverLangItem::Destruct);
725
726    match self_ty.kind() {
727        // `ManuallyDrop` is trivially `~const Destruct` as we do not run any drop glue on it.
728        ty::Adt(adt_def, _) if adt_def.is_manually_drop() => Ok(vec![]),
729
730        // An ADT is `~const Destruct` only if all of the fields are,
731        // *and* if there is a `Drop` impl, that `Drop` impl is also `~const`.
732        ty::Adt(adt_def, args) => {
733            let mut const_conditions: Vec<_> = adt_def
734                .all_field_tys(cx)
735                .iter_instantiated(cx, args)
736                .map(|field_ty| ty::TraitRef::new(cx, destruct_def_id, [field_ty]))
737                .collect();
738            match adt_def.destructor(cx) {
739                // `Drop` impl exists, but it's not const. Type cannot be `~const Destruct`.
740                Some(AdtDestructorKind::NotConst) => return Err(NoSolution),
741                // `Drop` impl exists, and it's const. Require `Ty: ~const Drop` to hold.
742                Some(AdtDestructorKind::Const) => {
743                    let drop_def_id = cx.require_lang_item(TraitSolverLangItem::Drop);
744                    let drop_trait_ref = ty::TraitRef::new(cx, drop_def_id, [self_ty]);
745                    const_conditions.push(drop_trait_ref);
746                }
747                // No `Drop` impl, no need to require anything else.
748                None => {}
749            }
750            Ok(const_conditions)
751        }
752
753        ty::Array(ty, _) | ty::Pat(ty, _) | ty::Slice(ty) => {
754            Ok(vec![ty::TraitRef::new(cx, destruct_def_id, [ty])])
755        }
756
757        ty::Tuple(tys) => Ok(tys
758            .iter()
759            .map(|field_ty| ty::TraitRef::new(cx, destruct_def_id, [field_ty]))
760            .collect()),
761
762        // Trivially implement `~const Destruct`
763        ty::Bool
764        | ty::Char
765        | ty::Int(..)
766        | ty::Uint(..)
767        | ty::Float(..)
768        | ty::Str
769        | ty::RawPtr(..)
770        | ty::Ref(..)
771        | ty::FnDef(..)
772        | ty::FnPtr(..)
773        | ty::Never
774        | ty::Infer(ty::InferTy::FloatVar(_) | ty::InferTy::IntVar(_))
775        | ty::Error(_) => Ok(vec![]),
776
777        // Coroutines and closures could implement `~const Drop`,
778        // but they don't really need to right now.
779        ty::Closure(_, _)
780        | ty::CoroutineClosure(_, _)
781        | ty::Coroutine(_, _)
782        | ty::CoroutineWitness(_, _) => Err(NoSolution),
783
784        // FIXME(unsafe_binders): Unsafe binders could implement `~const Drop`
785        // if their inner type implements it.
786        ty::UnsafeBinder(_) => Err(NoSolution),
787
788        ty::Dynamic(..) | ty::Param(_) | ty::Alias(..) | ty::Placeholder(_) | ty::Foreign(_) => {
789            Err(NoSolution)
790        }
791
792        ty::Bound(..)
793        | ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => {
794            panic!("unexpected type `{self_ty:?}`")
795        }
796    }
797}
798
799/// Assemble a list of predicates that would be present on a theoretical
800/// user impl for an object type. These predicates must be checked any time
801/// we assemble a built-in object candidate for an object type, since they
802/// are not implied by the well-formedness of the type.
803///
804/// For example, given the following traits:
805///
806/// ```rust,ignore (theoretical code)
807/// trait Foo: Baz {
808///     type Bar: Copy;
809/// }
810///
811/// trait Baz {}
812/// ```
813///
814/// For the dyn type `dyn Foo<Item = Ty>`, we can imagine there being a
815/// pair of theoretical impls:
816///
817/// ```rust,ignore (theoretical code)
818/// impl Foo for dyn Foo<Item = Ty>
819/// where
820///     Self: Baz,
821///     <Self as Foo>::Bar: Copy,
822/// {
823///     type Bar = Ty;
824/// }
825///
826/// impl Baz for dyn Foo<Item = Ty> {}
827/// ```
828///
829/// However, in order to make such impls non-cyclical, we need to do an
830/// additional step of eagerly folding the associated types in the where
831/// clauses of the impl. In this example, that means replacing
832/// `<Self as Foo>::Bar` with `Ty` in the first impl.
833pub(in crate::solve) fn predicates_for_object_candidate<D, I>(
834    ecx: &mut EvalCtxt<'_, D>,
835    param_env: I::ParamEnv,
836    trait_ref: ty::TraitRef<I>,
837    object_bounds: I::BoundExistentialPredicates,
838) -> Result<Vec<Goal<I, I::Predicate>>, Ambiguous>
839where
840    D: SolverDelegate<Interner = I>,
841    I: Interner,
842{
843    let cx = ecx.cx();
844    let mut requirements = vec![];
845    // Elaborating all supertrait outlives obligations here is not soundness critical,
846    // since if we just used the unelaborated set, then the transitive supertraits would
847    // be reachable when proving the former. However, since we elaborate all supertrait
848    // outlives obligations when confirming impls, we would end up with a different set
849    // of outlives obligations here if we didn't do the same, leading to ambiguity.
850    // FIXME(-Znext-solver=coinductive): Adding supertraits here can be removed once we
851    // make impls coinductive always, since they'll always need to prove their supertraits.
852    requirements.extend(elaborate::elaborate(
853        cx,
854        cx.explicit_super_predicates_of(trait_ref.def_id)
855            .iter_instantiated(cx, trait_ref.args)
856            .map(|(pred, _)| pred),
857    ));
858
859    // FIXME(associated_const_equality): Also add associated consts to
860    // the requirements here.
861    for associated_type_def_id in cx.associated_type_def_ids(trait_ref.def_id) {
862        // associated types that require `Self: Sized` do not show up in the built-in
863        // implementation of `Trait for dyn Trait`, and can be dropped here.
864        if cx.generics_require_sized_self(associated_type_def_id) {
865            continue;
866        }
867
868        requirements
869            .extend(cx.item_bounds(associated_type_def_id).iter_instantiated(cx, trait_ref.args));
870    }
871
872    let mut replace_projection_with: HashMap<_, Vec<_>> = HashMap::default();
873    for bound in object_bounds.iter() {
874        if let ty::ExistentialPredicate::Projection(proj) = bound.skip_binder() {
875            // FIXME: We *probably* should replace this with a dummy placeholder,
876            // b/c don't want to replace literal instances of this dyn type that
877            // show up in the bounds, but just ones that come from substituting
878            // `Self` with the dyn type.
879            let proj = proj.with_self_ty(cx, trait_ref.self_ty());
880            replace_projection_with.entry(proj.def_id()).or_default().push(bound.rebind(proj));
881        }
882    }
883
884    let mut folder = ReplaceProjectionWith {
885        ecx,
886        param_env,
887        self_ty: trait_ref.self_ty(),
888        mapping: &replace_projection_with,
889        nested: vec![],
890    };
891
892    let requirements = requirements.try_fold_with(&mut folder)?;
893    Ok(folder
894        .nested
895        .into_iter()
896        .chain(requirements.into_iter().map(|clause| Goal::new(cx, param_env, clause)))
897        .collect())
898}
899
900struct ReplaceProjectionWith<'a, 'b, I: Interner, D: SolverDelegate<Interner = I>> {
901    ecx: &'a mut EvalCtxt<'b, D>,
902    param_env: I::ParamEnv,
903    self_ty: I::Ty,
904    mapping: &'a HashMap<I::DefId, Vec<ty::Binder<I, ty::ProjectionPredicate<I>>>>,
905    nested: Vec<Goal<I, I::Predicate>>,
906}
907
908impl<D, I> ReplaceProjectionWith<'_, '_, I, D>
909where
910    D: SolverDelegate<Interner = I>,
911    I: Interner,
912{
913    fn projection_may_match(
914        &mut self,
915        source_projection: ty::Binder<I, ty::ProjectionPredicate<I>>,
916        target_projection: ty::AliasTerm<I>,
917    ) -> bool {
918        source_projection.item_def_id() == target_projection.def_id
919            && self
920                .ecx
921                .probe(|_| ProbeKind::ProjectionCompatibility)
922                .enter(|ecx| -> Result<_, NoSolution> {
923                    let source_projection = ecx.instantiate_binder_with_infer(source_projection);
924                    ecx.eq(self.param_env, source_projection.projection_term, target_projection)?;
925                    ecx.try_evaluate_added_goals()
926                })
927                .is_ok()
928    }
929
930    /// Try to replace an alias with the term present in the projection bounds of the self type.
931    /// Returns `Ok<None>` if this alias is not eligible to be replaced, or bail with
932    /// `Err(Ambiguous)` if it's uncertain which projection bound to replace the term with due
933    /// to multiple bounds applying.
934    fn try_eagerly_replace_alias(
935        &mut self,
936        alias_term: ty::AliasTerm<I>,
937    ) -> Result<Option<I::Term>, Ambiguous> {
938        if alias_term.self_ty() != self.self_ty {
939            return Ok(None);
940        }
941
942        let Some(replacements) = self.mapping.get(&alias_term.def_id) else {
943            return Ok(None);
944        };
945
946        // This is quite similar to the `projection_may_match` we use in unsizing,
947        // but here we want to unify a projection predicate against an alias term
948        // so we can replace it with the projection predicate's term.
949        let mut matching_projections = replacements
950            .iter()
951            .filter(|source_projection| self.projection_may_match(**source_projection, alias_term));
952        let Some(replacement) = matching_projections.next() else {
953            // This shouldn't happen.
954            panic!("could not replace {alias_term:?} with term from from {:?}", self.self_ty);
955        };
956        // FIXME: This *may* have issues with duplicated projections.
957        if matching_projections.next().is_some() {
958            // If there's more than one projection that we can unify here, then we
959            // need to stall until inference constrains things so that there's only
960            // one choice.
961            return Err(Ambiguous);
962        }
963
964        let replacement = self.ecx.instantiate_binder_with_infer(*replacement);
965        self.nested.extend(
966            self.ecx
967                .eq_and_get_goals(self.param_env, alias_term, replacement.projection_term)
968                .expect("expected to be able to unify goal projection with dyn's projection"),
969        );
970
971        Ok(Some(replacement.term))
972    }
973}
974
975/// Marker for bailing with ambiguity.
976pub(crate) struct Ambiguous;
977
978impl<D, I> FallibleTypeFolder<I> for ReplaceProjectionWith<'_, '_, I, D>
979where
980    D: SolverDelegate<Interner = I>,
981    I: Interner,
982{
983    type Error = Ambiguous;
984
985    fn cx(&self) -> I {
986        self.ecx.cx()
987    }
988
989    fn try_fold_ty(&mut self, ty: I::Ty) -> Result<I::Ty, Ambiguous> {
990        if let ty::Alias(ty::Projection, alias_ty) = ty.kind() {
991            if let Some(term) = self.try_eagerly_replace_alias(alias_ty.into())? {
992                return Ok(term.expect_ty());
993            }
994        }
995
996        ty.try_super_fold_with(self)
997    }
998}