hir_ty/
builtin_derive.rs

1//! Implementation of builtin derive impls.
2
3use std::ops::ControlFlow;
4
5use hir_def::{
6    AdtId, BuiltinDeriveImplId, BuiltinDeriveImplLoc, HasModule, LocalFieldId, TraitId,
7    TypeOrConstParamId, TypeParamId,
8    attrs::AttrFlags,
9    builtin_derive::BuiltinDeriveImplTrait,
10    hir::generics::{GenericParams, TypeOrConstParamData},
11};
12use itertools::Itertools;
13use la_arena::ArenaMap;
14use rustc_type_ir::{
15    AliasTyKind, BoundVar, BoundVarIndexKind, DebruijnIndex, INNERMOST, TypeFlags, TypeFoldable,
16    TypeFolder, TypeSuperFoldable, TypeSuperVisitable, TypeVisitable, TypeVisitableExt,
17    TypeVisitor, Upcast,
18    inherent::{GenericArgs as _, IntoKind, Ty as _},
19};
20
21use crate::{
22    FieldType, GenericPredicates,
23    db::HirDatabase,
24    next_solver::{
25        AliasTy, Binder, BoundConst, BoundRegion, BoundTy, BoundVarKinds, Clause, Clauses, Const,
26        ConstKind, DbInterner, EarlyBinder, GenericArgs, ParamEnv, Region, RegionKind,
27        StoredEarlyBinder, TraitRef, Ty, TyKind, Unnormalized, fold::fold_tys, generics::Generics,
28    },
29};
30
31fn coerce_pointee_new_type_param(trait_id: TraitId) -> TypeParamId {
32    // HACK: Fake the param.
33    // We cannot use a dummy param here, because it can leak into the IDE layer and that'll cause panics
34    // when e.g. trying to display it. So we use an existing param.
35    TypeParamId::from_unchecked(TypeOrConstParamId {
36        parent: trait_id.into(),
37        local_id: la_arena::Idx::from_raw(la_arena::RawIdx::from_u32(1)),
38    })
39}
40
41fn trait_args(trait_: BuiltinDeriveImplTrait, self_ty: Ty<'_>) -> GenericArgs<'_> {
42    match trait_ {
43        BuiltinDeriveImplTrait::Copy
44        | BuiltinDeriveImplTrait::Reborrow
45        | BuiltinDeriveImplTrait::Clone
46        | BuiltinDeriveImplTrait::Default
47        | BuiltinDeriveImplTrait::Debug
48        | BuiltinDeriveImplTrait::Hash
49        | BuiltinDeriveImplTrait::Eq
50        | BuiltinDeriveImplTrait::Ord => GenericArgs::new_from_slice(&[self_ty.into()]),
51        BuiltinDeriveImplTrait::PartialOrd | BuiltinDeriveImplTrait::PartialEq => {
52            GenericArgs::new_from_slice(&[self_ty.into(), self_ty.into()])
53        }
54        BuiltinDeriveImplTrait::CoerceUnsized | BuiltinDeriveImplTrait::DispatchFromDyn => {
55            panic!("`CoerceUnsized` and `DispatchFromDyn` have special generics")
56        }
57    }
58}
59
60pub(crate) fn generics_of<'db>(
61    interner: DbInterner<'db>,
62    id: BuiltinDeriveImplId,
63) -> Generics<'db> {
64    let db = interner.db;
65    let loc = id.loc(db);
66    match loc.trait_ {
67        BuiltinDeriveImplTrait::Copy
68        | BuiltinDeriveImplTrait::Reborrow
69        | BuiltinDeriveImplTrait::Clone
70        | BuiltinDeriveImplTrait::Default
71        | BuiltinDeriveImplTrait::Debug
72        | BuiltinDeriveImplTrait::Hash
73        | BuiltinDeriveImplTrait::Ord
74        | BuiltinDeriveImplTrait::PartialOrd
75        | BuiltinDeriveImplTrait::Eq
76        | BuiltinDeriveImplTrait::PartialEq => {
77            Generics::from_generic_def(db, loc.adt.into(), false)
78        }
79        BuiltinDeriveImplTrait::CoerceUnsized | BuiltinDeriveImplTrait::DispatchFromDyn => {
80            let trait_id = loc
81                .trait_
82                .get_id(interner.lang_items())
83                .expect("we don't pass the impl to the solver if we can't resolve the trait");
84            let additional_param = coerce_pointee_new_type_param(trait_id);
85            Generics::from_generic_def_plus_one(db, loc.adt.into(), additional_param, false)
86        }
87    }
88}
89
90pub fn generic_params_count(db: &dyn HirDatabase, id: BuiltinDeriveImplId) -> usize {
91    let loc = id.loc(db);
92    let adt_params = GenericParams::of(db, loc.adt.into());
93    let extra_params_count = match loc.trait_ {
94        BuiltinDeriveImplTrait::Copy
95        | BuiltinDeriveImplTrait::Reborrow
96        | BuiltinDeriveImplTrait::Clone
97        | BuiltinDeriveImplTrait::Default
98        | BuiltinDeriveImplTrait::Debug
99        | BuiltinDeriveImplTrait::Hash
100        | BuiltinDeriveImplTrait::Ord
101        | BuiltinDeriveImplTrait::PartialOrd
102        | BuiltinDeriveImplTrait::Eq
103        | BuiltinDeriveImplTrait::PartialEq => 0,
104        BuiltinDeriveImplTrait::CoerceUnsized | BuiltinDeriveImplTrait::DispatchFromDyn => 1,
105    };
106    adt_params.len() + extra_params_count
107}
108
109pub fn impl_trait<'db>(
110    interner: DbInterner<'db>,
111    id: BuiltinDeriveImplId,
112) -> EarlyBinder<'db, TraitRef<'db>> {
113    let db = interner.db;
114    let loc = id.loc(db);
115    let trait_id = loc
116        .trait_
117        .get_id(interner.lang_items())
118        .expect("we don't pass the impl to the solver if we can't resolve the trait");
119    match loc.trait_ {
120        BuiltinDeriveImplTrait::Copy
121        | BuiltinDeriveImplTrait::Reborrow
122        | BuiltinDeriveImplTrait::Clone
123        | BuiltinDeriveImplTrait::Default
124        | BuiltinDeriveImplTrait::Debug
125        | BuiltinDeriveImplTrait::Hash
126        | BuiltinDeriveImplTrait::Ord
127        | BuiltinDeriveImplTrait::Eq
128        | BuiltinDeriveImplTrait::PartialOrd
129        | BuiltinDeriveImplTrait::PartialEq => {
130            let self_ty = Ty::new_adt(
131                interner,
132                loc.adt,
133                GenericArgs::identity_for_item(interner, loc.adt.into()),
134            );
135            EarlyBinder::bind(TraitRef::new_from_args(
136                interner,
137                trait_id.into(),
138                trait_args(loc.trait_, self_ty),
139            ))
140        }
141        BuiltinDeriveImplTrait::CoerceUnsized | BuiltinDeriveImplTrait::DispatchFromDyn => {
142            let generic_params = GenericParams::of(db, loc.adt.into());
143            let interner = DbInterner::new_no_crate(db);
144            let args = GenericArgs::identity_for_item(interner, loc.adt.into());
145            let self_ty = Ty::new_adt(interner, loc.adt, args);
146            let Some((pointee_param_idx, _, new_param_ty)) =
147                coerce_pointee_params(interner, loc, generic_params, trait_id)
148            else {
149                // Malformed derive.
150                return EarlyBinder::bind(TraitRef::new(
151                    interner,
152                    trait_id.into(),
153                    [self_ty, self_ty],
154                ));
155            };
156            let changed_args = replace_pointee(interner, pointee_param_idx, new_param_ty, args);
157            let changed_self_ty = Ty::new_adt(interner, loc.adt, changed_args);
158            EarlyBinder::bind(TraitRef::new(interner, trait_id.into(), [self_ty, changed_self_ty]))
159        }
160    }
161}
162
163#[inline]
164pub fn impl_super_outlives<'db>(
165    _interner: DbInterner<'db>,
166    _id: BuiltinDeriveImplId,
167) -> EarlyBinder<'db, &'db [Clause<'db>]> {
168    // Currently no builtin-derived traits have super outlive bounds.
169    EarlyBinder::bind(&[])
170}
171
172#[salsa::tracked(returns(ref))]
173pub fn predicates(db: &dyn HirDatabase, impl_: BuiltinDeriveImplId) -> GenericPredicates {
174    let loc = impl_.loc(db);
175    let generic_params = GenericParams::of(db, loc.adt.into());
176    let interner = DbInterner::new_with(db, loc.module(db).krate(db));
177    let adt_predicates = GenericPredicates::query(db, loc.adt.into());
178    let trait_id = loc
179        .trait_
180        .get_id(interner.lang_items())
181        .expect("we don't pass the impl to the solver if we can't resolve the trait");
182    match loc.trait_ {
183        BuiltinDeriveImplTrait::Copy
184        | BuiltinDeriveImplTrait::Clone
185        | BuiltinDeriveImplTrait::Debug
186        | BuiltinDeriveImplTrait::Hash
187        | BuiltinDeriveImplTrait::Ord
188        | BuiltinDeriveImplTrait::PartialOrd
189        | BuiltinDeriveImplTrait::Eq
190        | BuiltinDeriveImplTrait::PartialEq => {
191            simple_trait_predicates(interner, loc, generic_params, adt_predicates, trait_id)
192        }
193        BuiltinDeriveImplTrait::Reborrow => {
194            explicit_own_predicates(adt_predicates.own_explicit_predicates())
195        }
196        BuiltinDeriveImplTrait::Default => {
197            if matches!(loc.adt, AdtId::EnumId(_)) {
198                // Enums don't have extra bounds.
199                explicit_own_predicates(adt_predicates.own_explicit_predicates())
200            } else {
201                simple_trait_predicates(interner, loc, generic_params, adt_predicates, trait_id)
202            }
203        }
204        BuiltinDeriveImplTrait::CoerceUnsized | BuiltinDeriveImplTrait::DispatchFromDyn => {
205            let Some((pointee_param_idx, pointee_param_id, new_param_ty)) =
206                coerce_pointee_params(interner, loc, generic_params, trait_id)
207            else {
208                // Malformed derive.
209                return GenericPredicates::from_explicit_own_predicates(StoredEarlyBinder::bind(
210                    Clauses::empty().store(),
211                ));
212            };
213            let duplicated_bounds =
214                adt_predicates.explicit_predicates().iter_identity().filter_map(|pred| {
215                    let pred = pred.skip_norm_wip();
216                    let mentions_pointee =
217                        pred.visit_with(&mut MentionsPointee { pointee_param_idx }).is_break();
218                    if !mentions_pointee {
219                        return None;
220                    }
221                    let transformed =
222                        replace_pointee(interner, pointee_param_idx, new_param_ty, pred);
223                    Some(transformed)
224                });
225            let unsize_trait = interner.lang_items().Unsize;
226            let unsize_bound = unsize_trait.map(|unsize_trait| {
227                let pointee_param_ty = Ty::new_param(interner, pointee_param_id, pointee_param_idx);
228                TraitRef::new(interner, unsize_trait.into(), [pointee_param_ty, new_param_ty])
229                    .upcast(interner)
230            });
231            GenericPredicates::from_explicit_own_predicates(StoredEarlyBinder::bind(
232                Clauses::new_from_iter(
233                    adt_predicates
234                        .explicit_predicates()
235                        .iter_identity()
236                        .map(Unnormalized::skip_norm_wip)
237                        .chain(duplicated_bounds)
238                        .chain(unsize_bound),
239                )
240                .store(),
241            ))
242        }
243    }
244}
245
246fn explicit_own_predicates<'db>(
247    predicates: EarlyBinder<'db, impl Iterator<Item = Clause<'db>>>,
248) -> GenericPredicates {
249    GenericPredicates::from_explicit_own_predicates(StoredEarlyBinder::bind(
250        Clauses::new_from_iter(predicates.skip_binder()).store(),
251    ))
252}
253
254/// Not cached in a query, currently used in `hir` only. If you need this in `hir-ty` consider introducing a query.
255pub fn param_env<'db>(interner: DbInterner<'db>, id: BuiltinDeriveImplId) -> ParamEnv<'db> {
256    let predicates = predicates(interner.db, id);
257    crate::lower::param_env_from_predicates(interner, predicates)
258}
259
260struct MentionsPointee {
261    pointee_param_idx: u32,
262}
263
264impl<'db> TypeVisitor<DbInterner<'db>> for MentionsPointee {
265    type Result = ControlFlow<()>;
266
267    fn visit_ty(&mut self, t: Ty<'db>) -> Self::Result {
268        if let TyKind::Param(param) = t.kind()
269            && param.index == self.pointee_param_idx
270        {
271            ControlFlow::Break(())
272        } else {
273            t.super_visit_with(self)
274        }
275    }
276}
277
278fn replace_pointee<'db, T: TypeFoldable<DbInterner<'db>>>(
279    interner: DbInterner<'db>,
280    pointee_param_idx: u32,
281    new_param_ty: Ty<'db>,
282    t: T,
283) -> T {
284    fold_tys(interner, t, |ty| match ty.kind() {
285        TyKind::Param(param) if param.index == pointee_param_idx => new_param_ty,
286        _ => ty,
287    })
288}
289
290fn simple_trait_predicates<'db>(
291    interner: DbInterner<'db>,
292    loc: &BuiltinDeriveImplLoc,
293    generic_params: &GenericParams,
294    adt_predicates: &GenericPredicates,
295    trait_id: TraitId,
296) -> GenericPredicates {
297    let extra_predicates = generic_params
298        .iter_type_or_consts()
299        .filter(|(_, data)| matches!(data, TypeOrConstParamData::TypeParamData(_)))
300        .map(|(param_idx, _)| {
301            let param_id = TypeParamId::from_unchecked(TypeOrConstParamId {
302                parent: loc.adt.into(),
303                local_id: param_idx,
304            });
305            let param_idx = param_idx.into_raw().into_u32()
306                + (generic_params.len_early_bound_lifetimes() as u32);
307            let param_ty = Ty::new_param(interner, param_id, param_idx);
308            let trait_args = trait_args(loc.trait_, param_ty);
309            let trait_ref = TraitRef::new_from_args(interner, trait_id.into(), trait_args);
310            trait_ref.upcast(interner)
311        });
312    let mut assoc_type_bounds = Vec::new();
313    match loc.adt {
314        AdtId::StructId(id) => extend_assoc_type_bounds(
315            interner,
316            &mut assoc_type_bounds,
317            interner.db.field_types(id.into()),
318            trait_id,
319            loc.trait_,
320        ),
321        AdtId::UnionId(id) => extend_assoc_type_bounds(
322            interner,
323            &mut assoc_type_bounds,
324            interner.db.field_types(id.into()),
325            trait_id,
326            loc.trait_,
327        ),
328        AdtId::EnumId(id) => {
329            for &(variant_id, _) in id.enum_variants(interner.db).variants.values() {
330                extend_assoc_type_bounds(
331                    interner,
332                    &mut assoc_type_bounds,
333                    interner.db.field_types(variant_id.into()),
334                    trait_id,
335                    loc.trait_,
336                )
337            }
338        }
339    }
340    GenericPredicates::from_explicit_own_predicates(StoredEarlyBinder::bind(
341        Clauses::new_from_iter(
342            adt_predicates
343                .explicit_predicates()
344                .iter_identity()
345                .map(Unnormalized::skip_norm_wip)
346                .chain(extra_predicates)
347                .chain(assoc_type_bounds),
348        )
349        .store(),
350    ))
351}
352
353fn extend_assoc_type_bounds<'db>(
354    interner: DbInterner<'db>,
355    assoc_type_bounds: &mut Vec<Clause<'db>>,
356    fields: &ArenaMap<LocalFieldId, FieldType>,
357    trait_id: TraitId,
358    trait_: BuiltinDeriveImplTrait,
359) {
360    struct ProjectionFinder<'a, 'db> {
361        interner: DbInterner<'db>,
362        assoc_type_bounds: &'a mut Vec<Clause<'db>>,
363        trait_id: TraitId,
364        trait_: BuiltinDeriveImplTrait,
365        bound_generic_params_stack: Vec<BoundVarKinds<'db>>,
366    }
367
368    impl<'db> TypeVisitor<DbInterner<'db>> for ProjectionFinder<'_, 'db> {
369        type Result = ();
370
371        fn visit_ty(&mut self, t: Ty<'db>) -> Self::Result {
372            if !t.has_type_flags(TypeFlags::HAS_TY_PROJECTION) {
373                return;
374            }
375            if let TyKind::Alias(alias @ AliasTy { kind: AliasTyKind::Projection { .. }, .. }) =
376                t.kind()
377                && let TyKind::Param(_) = alias.self_ty().kind()
378            {
379                // rustc flattens binders before lowering, so the corresponding rustc
380                // logic just has a flat vec already:
381                // https://github.com/rust-lang/rust/blob/cabb1ea4ced589dfee40c08aeffff3cac78af43b/compiler/rustc_builtin_macros/src/deriving/generic/mod.rs#L396
382                let t = t.fold_with(&mut FlattenBinders {
383                    interner: self.interner,
384                    enclosing_binders: &self.bound_generic_params_stack,
385                    nested_binder_depth: INNERMOST,
386                });
387                let bound_vars = BoundVarKinds::new_from_iter(
388                    self.bound_generic_params_stack.iter().flat_map(|it| it.iter()),
389                );
390                self.assoc_type_bounds.push(
391                    Binder::bind_with_vars(
392                        TraitRef::new_from_args(
393                            self.interner,
394                            self.trait_id.into(),
395                            trait_args(self.trait_, t),
396                        ),
397                        bound_vars,
398                    )
399                    .upcast(self.interner),
400                );
401            }
402
403            t.super_visit_with(self)
404        }
405
406        // Place bound generic params on a stack, to extract them when a type is encountered.
407        fn visit_binder<T: TypeVisitable<DbInterner<'db>>>(
408            &mut self,
409            binder: &Binder<'db, T>,
410        ) -> Self::Result {
411            let stack_len = self.bound_generic_params_stack.len();
412            // Given a field `x: for<'a> fn(T::SomeType<'a>)`, we want to account for `'a` so
413            // that we generate `where for<'a> T::SomeType<'a>: ::core::clone::Clone`. #122622
414            self.bound_generic_params_stack.push(binder.bound_vars());
415
416            binder.super_visit_with(self);
417
418            self.bound_generic_params_stack.truncate(stack_len);
419        }
420    }
421
422    let mut visitor = ProjectionFinder {
423        interner,
424        assoc_type_bounds,
425        trait_id,
426        trait_,
427        bound_generic_params_stack: Vec::new(),
428    };
429    for (_, field) in fields.iter() {
430        field.ty().instantiate_identity().skip_norm_wip().visit_with(&mut visitor);
431    }
432}
433
434/// Transform a projection `for<'a> for<'b> F::Foo<'a, 'b, X>` into
435/// `for<'a, 'b> F::Foo<'a, 'b, X>`. Update de Bruijn indexes for
436/// enclosing binders, but preserve nested binders.
437struct FlattenBinders<'a, 'db> {
438    interner: DbInterner<'db>,
439    enclosing_binders: &'a [BoundVarKinds<'db>],
440    nested_binder_depth: DebruijnIndex,
441}
442
443impl FlattenBinders<'_, '_> {
444    fn flattened_var(&self, debruijn: DebruijnIndex, var: BoundVar) -> Option<BoundVar> {
445        let depth = debruijn.as_usize().checked_sub(self.nested_binder_depth.as_usize())?;
446        let binder = self.enclosing_binders.len().checked_sub(depth + 1)?;
447        let offset = self.enclosing_binders[..binder].iter().map(|it| it.len()).sum::<usize>();
448        Some(BoundVar::from_usize(offset + var.as_usize()))
449    }
450}
451
452impl<'db> TypeFolder<DbInterner<'db>> for FlattenBinders<'_, 'db> {
453    fn cx(&self) -> DbInterner<'db> {
454        self.interner
455    }
456
457    fn fold_binder<T: TypeFoldable<DbInterner<'db>>>(
458        &mut self,
459        binder: Binder<'db, T>,
460    ) -> Binder<'db, T> {
461        self.nested_binder_depth.shift_in(1);
462        let binder = binder.super_fold_with(self);
463        self.nested_binder_depth.shift_out(1);
464        binder
465    }
466
467    fn fold_ty(&mut self, ty: Ty<'db>) -> Ty<'db> {
468        if !ty.has_bound_vars() {
469            return ty;
470        }
471        if let TyKind::Bound(BoundVarIndexKind::Bound(debruijn), bound_ty) = ty.kind()
472            && let Some(var) = self.flattened_var(debruijn, bound_ty.var)
473        {
474            return Ty::new_bound(
475                self.interner,
476                self.nested_binder_depth,
477                BoundTy { var, kind: bound_ty.kind },
478            );
479        }
480        ty.super_fold_with(self)
481    }
482
483    fn fold_region(&mut self, region: Region<'db>) -> Region<'db> {
484        if !region.has_bound_vars() {
485            return region;
486        }
487        if let RegionKind::ReBound(BoundVarIndexKind::Bound(debruijn), bound_region) = region.kind()
488            && let Some(var) = self.flattened_var(debruijn, bound_region.var)
489        {
490            return Region::new_bound(
491                self.interner,
492                self.nested_binder_depth,
493                BoundRegion { var, kind: bound_region.kind },
494            );
495        }
496        region
497    }
498
499    fn fold_const(&mut self, konst: Const<'db>) -> Const<'db> {
500        if !konst.has_bound_vars() {
501            return konst;
502        }
503        if let ConstKind::Bound(BoundVarIndexKind::Bound(debruijn), bound_const) = konst.kind()
504            && let Some(var) = self.flattened_var(debruijn, bound_const.var)
505        {
506            return Const::new_bound(self.interner, self.nested_binder_depth, BoundConst::new(var));
507        }
508        konst.super_fold_with(self)
509    }
510}
511
512fn coerce_pointee_params<'db>(
513    interner: DbInterner<'db>,
514    loc: &BuiltinDeriveImplLoc,
515    generic_params: &GenericParams,
516    trait_id: TraitId,
517) -> Option<(u32, TypeParamId, Ty<'db>)> {
518    let pointee_param = {
519        if let Ok((pointee_param, _)) = generic_params
520            .iter_type_or_consts()
521            .filter(|param| matches!(param.1, TypeOrConstParamData::TypeParamData(_)))
522            .exactly_one()
523        {
524            pointee_param
525        } else {
526            let (_, generic_param_attrs) =
527                AttrFlags::query_generic_params(interner.db, loc.adt.into());
528            generic_param_attrs
529                .iter()
530                .find(|param| param.1.contains(AttrFlags::IS_POINTEE))
531                .map(|(param, _)| param)
532                .or_else(|| {
533                    generic_params
534                        .iter_type_or_consts()
535                        .find(|param| matches!(param.1, TypeOrConstParamData::TypeParamData(_)))
536                        .map(|(idx, _)| idx)
537                })?
538        }
539    };
540    let pointee_param_id = TypeParamId::from_unchecked(TypeOrConstParamId {
541        parent: loc.adt.into(),
542        local_id: pointee_param,
543    });
544    let pointee_param_idx =
545        pointee_param.into_raw().into_u32() + (generic_params.len_early_bound_lifetimes() as u32);
546    let new_param_idx = generic_params.len() as u32;
547    let new_param_id = coerce_pointee_new_type_param(trait_id);
548    let new_param_ty = Ty::new_param(interner, new_param_id, new_param_idx);
549    Some((pointee_param_idx, pointee_param_id, new_param_ty))
550}
hir_ty/builtin_derive.rs

hir_ty/
builtin_derive.rs
