1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

use super::{builder::ClauseBuilder, generalize};
use crate::{
    rust_ir::AdtKind, CanonicalVarKinds, Interner, RustIrDatabase, TraitRef, WellKnownTrait,
};
use chalk_ir::{Floundered, Substitution, Ty, TyKind};

mod clone;
mod copy;
mod coroutine;
mod discriminant_kind;
mod fn_family;
mod pointee;
mod sized;
mod tuple;
mod unsize;

/// For well known traits we have special hard-coded impls, either as an
/// optimization or to enforce special rules for correctness.
pub fn add_builtin_program_clauses<I: Interner>(
    db: &dyn RustIrDatabase<I>,
    builder: &mut ClauseBuilder<'_, I>,
    well_known: WellKnownTrait,
    trait_ref: TraitRef<I>,
    binders: &CanonicalVarKinds<I>,
) -> Result<(), Floundered> {
    // If `trait_ref` contains bound vars, we want to universally quantify them.
    // `Generalize` collects them for us.
    let generalized = generalize::Generalize::apply(db.interner(), trait_ref);

    builder.push_binders(generalized, |builder, trait_ref| {
        let self_ty = trait_ref.self_type_parameter(db.interner());
        let ty = self_ty.kind(db.interner()).clone();

        match well_known {
            // Built-in traits are non-enumerable.
            _ if self_ty.is_general_var(db.interner(), binders) => return Err(Floundered),
            WellKnownTrait::Sized => {
                sized::add_sized_program_clauses(db, builder, trait_ref, ty, binders)?;
            }
            WellKnownTrait::Copy => {
                copy::add_copy_program_clauses(db, builder, trait_ref, ty, binders)?;
            }
            WellKnownTrait::Clone => {
                clone::add_clone_program_clauses(db, builder, trait_ref, ty, binders)?;
            }
            WellKnownTrait::FnOnce | WellKnownTrait::FnMut | WellKnownTrait::Fn => {
                fn_family::add_fn_trait_program_clauses(db, builder, well_known, self_ty);
            }
            WellKnownTrait::Unsize => {
                unsize::add_unsize_program_clauses(db, builder, trait_ref, ty)
            }
            // DiscriminantKind is automatically implemented for all types
            WellKnownTrait::DiscriminantKind => builder.push_fact(trait_ref),
            WellKnownTrait::Coroutine => {
                coroutine::add_coroutine_program_clauses(db, builder, self_ty)?;
            }
            WellKnownTrait::Tuple => {
                tuple::add_tuple_program_clauses(db, builder, self_ty)?;
            }
            WellKnownTrait::Pointee => {
                pointee::add_pointee_program_clauses(db, builder, self_ty)?;
            }
            WellKnownTrait::FnPtr => {
                if let TyKind::Function(_) = self_ty.kind(db.interner()) {
                    builder.push_fact(trait_ref);
                }
            }
            // There are no builtin impls provided for the following traits:
            WellKnownTrait::Unpin
            | WellKnownTrait::Drop
            | WellKnownTrait::CoerceUnsized
            | WellKnownTrait::DispatchFromDyn => (),
        }
        Ok(())
    })
}

/// Like `add_builtin_program_clauses`, but for `DomainGoal::Normalize` involving
/// a projection (e.g. `<fn(u8) as FnOnce<(u8,)>>::Output`)
pub fn add_builtin_assoc_program_clauses<I: Interner>(
    db: &dyn RustIrDatabase<I>,
    builder: &mut ClauseBuilder<'_, I>,
    well_known: WellKnownTrait,
    self_ty: Ty<I>,
) -> Result<(), Floundered> {
    // If `self_ty` contains bound vars, we want to universally quantify them.
    // `Generalize` collects them for us.
    let generalized = generalize::Generalize::apply(db.interner(), self_ty);
    builder.push_binders(generalized, |builder, self_ty| match well_known {
        WellKnownTrait::FnOnce => {
            fn_family::add_fn_trait_program_clauses(db, builder, well_known, self_ty);
            Ok(())
        }
        WellKnownTrait::Pointee => pointee::add_pointee_program_clauses(db, builder, self_ty),
        WellKnownTrait::DiscriminantKind => {
            discriminant_kind::add_discriminant_clauses(db, builder, self_ty)
        }
        WellKnownTrait::Coroutine => coroutine::add_coroutine_program_clauses(db, builder, self_ty),
        _ => Ok(()),
    })
}

/// Returns type of the last field of the input struct, which is useful for `Sized` and related
/// traits. Returns `None` if the input is not a struct or it has no fields.
fn last_field_of_struct<I: Interner>(
    db: &dyn RustIrDatabase<I>,
    id: chalk_ir::AdtId<I>,
    subst: &Substitution<I>,
) -> Option<Ty<I>> {
    let adt_datum = db.adt_datum(id);
    let interner = db.interner();
    if adt_datum.kind != AdtKind::Struct {
        return None;
    }
    let last_field_ty = adt_datum
        .binders
        .map_ref(|b| b.variants.last()?.fields.last().cloned())
        .filter_map(|x| x)?
        .substitute(interner, subst);
    Some(last_field_ty)
}

/// Given a trait ref `T0: Trait` and a list of types `U0..Un`, pushes a clause of the form
/// `Implemented(T0: Trait) :- Implemented(U0: Trait) .. Implemented(Un: Trait)`
pub fn needs_impl_for_tys<I: Interner>(
    db: &dyn RustIrDatabase<I>,
    builder: &mut ClauseBuilder<'_, I>,
    trait_ref: TraitRef<I>,
    tys: impl Iterator<Item = Ty<I>>,
) {
    let trait_id = trait_ref.trait_id;

    // The trait must take one parameter (a type)
    debug_assert_eq!(db.trait_datum(trait_id).binders.len(db.interner()), 1,);
    builder.push_clause(
        trait_ref,
        tys.map(|ty| TraitRef {
            trait_id,
            substitution: Substitution::from1(db.interner(), ty),
        }),
    );
}