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

rustc_next_trait_solver/solve/assembly/
structural_traits.rs
