]>
Commit | Line | Data |
---|---|---|
f035d41b XL |
1 | use rustc_hash::FxHashSet; |
2 | ||
a2a8927a | 3 | use super::builder::ClauseBuilder; |
f035d41b XL |
4 | use crate::RustIrDatabase; |
5 | use chalk_ir::{ | |
a2a8927a XL |
6 | fold::shift::Shift, interner::Interner, Binders, BoundVar, DebruijnIndex, TraitId, TraitRef, |
7 | WhereClause, | |
f035d41b XL |
8 | }; |
9 | ||
a2a8927a | 10 | /// Generate `Implemented` clauses for `dyn Trait` and opaque types. We need to generate |
f035d41b XL |
11 | /// `Implemented` clauses for all super traits, and for each trait we require |
12 | /// its where clauses. (See #203.) | |
a2a8927a | 13 | pub(super) fn push_trait_super_clauses<I: Interner>( |
f035d41b XL |
14 | db: &dyn RustIrDatabase<I>, |
15 | builder: &mut ClauseBuilder<'_, I>, | |
16 | trait_ref: TraitRef<I>, | |
17 | ) { | |
18 | let interner = db.interner(); | |
a2a8927a XL |
19 | // Given`trait SuperTrait: WC`, which is a super trait |
20 | // of `Trait` (including actually just being the same trait); | |
21 | // then we want to push | |
22 | // - for `dyn Trait`: | |
23 | // `Implemented(dyn Trait: SuperTrait) :- WC`. | |
24 | // - for placeholder `!T` of `opaque type T: Trait = HiddenTy`: | |
25 | // `Implemented(!T: SuperTrait) :- WC` | |
f035d41b XL |
26 | |
27 | let super_trait_refs = | |
28 | super_traits(db, trait_ref.trait_id).substitute(interner, &trait_ref.substitution); | |
29 | ||
30 | for q_super_trait_ref in super_trait_refs { | |
5869c6ff | 31 | builder.push_binders(q_super_trait_ref.clone(), |builder, super_trait_ref| { |
f035d41b XL |
32 | let trait_datum = db.trait_datum(super_trait_ref.trait_id); |
33 | let wc = trait_datum | |
34 | .where_clauses() | |
5869c6ff | 35 | .cloned() |
f035d41b XL |
36 | .substitute(interner, &super_trait_ref.substitution); |
37 | builder.push_clause(super_trait_ref, wc); | |
38 | }); | |
39 | } | |
40 | } | |
41 | ||
42 | pub fn super_traits<I: Interner>( | |
43 | db: &dyn RustIrDatabase<I>, | |
44 | trait_id: TraitId<I>, | |
45 | ) -> Binders<Vec<Binders<TraitRef<I>>>> { | |
46 | let interner = db.interner(); | |
47 | let mut seen_traits = FxHashSet::default(); | |
48 | let trait_datum = db.trait_datum(trait_id); | |
49 | let trait_ref = Binders::empty( | |
50 | db.interner(), | |
51 | TraitRef { | |
52 | trait_id, | |
53 | substitution: trait_datum | |
54 | .binders | |
55 | .identity_substitution(interner) | |
56 | .shifted_in(interner), | |
57 | }, | |
58 | ); | |
59 | let mut trait_refs = Vec::new(); | |
60 | go(db, trait_ref, &mut seen_traits, &mut trait_refs); | |
61 | ||
62 | fn go<I: Interner>( | |
63 | db: &dyn RustIrDatabase<I>, | |
64 | trait_ref: Binders<TraitRef<I>>, | |
65 | seen_traits: &mut FxHashSet<TraitId<I>>, | |
66 | trait_refs: &mut Vec<Binders<TraitRef<I>>>, | |
67 | ) { | |
68 | let interner = db.interner(); | |
69 | let trait_id = trait_ref.skip_binders().trait_id; | |
70 | // Avoid cycles | |
71 | if !seen_traits.insert(trait_id) { | |
72 | return; | |
73 | } | |
74 | trait_refs.push(trait_ref.clone()); | |
75 | let trait_datum = db.trait_datum(trait_id); | |
76 | let super_trait_refs = trait_datum | |
77 | .binders | |
78 | .map_ref(|td| { | |
79 | td.where_clauses | |
80 | .iter() | |
81 | .filter_map(|qwc| { | |
82 | qwc.as_ref().filter_map(|wc| match wc { | |
83 | WhereClause::Implemented(tr) => { | |
84 | let self_ty = tr.self_type_parameter(db.interner()); | |
85 | ||
86 | // We're looking for where clauses | |
87 | // of the form `Self: Trait`. That's | |
88 | // ^1.0 because we're one binder in. | |
89 | if self_ty.bound_var(db.interner()) | |
90 | != Some(BoundVar::new(DebruijnIndex::ONE, 0)) | |
91 | { | |
92 | return None; | |
93 | } | |
94 | Some(tr.clone()) | |
95 | } | |
96 | WhereClause::AliasEq(_) => None, | |
97 | WhereClause::LifetimeOutlives(..) => None, | |
3dfed10e | 98 | WhereClause::TypeOutlives(..) => None, |
f035d41b XL |
99 | }) |
100 | }) | |
101 | .collect::<Vec<_>>() | |
102 | }) | |
103 | // we skip binders on the trait_ref here and add them to the binders | |
104 | // on the trait ref in the loop below. We could probably avoid this if | |
105 | // we could turn the `Binders<Vec<>>` into a `Vec<Binders<>>` easily. | |
106 | .substitute(db.interner(), &trait_ref.skip_binders().substitution); | |
107 | for q_super_trait_ref in super_trait_refs { | |
108 | // So now we need to combine the binders of trait_ref with the | |
109 | // binders of super_trait_ref. | |
110 | let actual_binders = Binders::new(trait_ref.binders.clone(), q_super_trait_ref); | |
111 | let q_super_trait_ref = actual_binders.fuse_binders(interner); | |
112 | go(db, q_super_trait_ref, seen_traits, trait_refs); | |
113 | } | |
114 | seen_traits.remove(&trait_id); | |
115 | } | |
116 | ||
117 | Binders::new(trait_datum.binders.binders.clone(), trait_refs) | |
118 | } |