vendor/chalk-solve-0.55.0/src/clauses/dyn_ty.rs

   1 use rustc_hash::FxHashSet;
   2
   3 use super::{builder::ClauseBuilder, generalize};
   4 use crate::RustIrDatabase;
   5 use chalk_ir::{
   6     cast::Cast, fold::shift::Shift, interner::Interner, Binders, BoundVar, DebruijnIndex, TraitId,
   7     TraitRef, Ty, TyKind, WhereClause,
   8 };
   9
  10 /// If the self type `S` of an `Implemented` goal is a `dyn trait` type, we wish
  11 /// to generate program-clauses that indicates that it implements its own
  12 /// traits. For example, a `dyn Write` type implements `Write` and so on.
  13 ///
  14 /// To see how this works, consider as an example the type `dyn Fn(&u8)`. This
  15 /// is really shorthand for `dyn for<'a> Fn<(&'a u8), Output = ()>`, and we
  16 /// represent that type as something like this:
  17 ///
  18 /// ```ignore
  19 /// dyn(exists<T> {
  20 ///     forall<'a> { Implemented(T: Fn<'a>) },
  21 ///     forall<'a> { AliasEq(<T as Fn<'a>>::Output, ()) },
  22 /// })
  23 /// ```
  24 ///
  25 /// so what we will do is to generate one program clause for each of the
  26 /// conditions. Thus we get two program clauses:
  27 ///
  28 /// ```ignore
  29 /// forall<'a> { Implemented(dyn Fn(&u8): Fn<(&'a u8)>) }
  30 /// ```
  31 ///
  32 /// and
  33 ///
  34 /// ```ignore
  35 /// forall<'a> { AliasEq(<dyn Fn(&u8) as Fn<'a>>::Output, ()) },
  36 /// ```
  37 pub(super) fn build_dyn_self_ty_clauses<I: Interner>(
  38     db: &dyn RustIrDatabase<I>,
  39     builder: &mut ClauseBuilder<'_, I>,
  40     self_ty: Ty<I>,
  41 ) {
  42     let interner = db.interner();
  43     let dyn_ty = match self_ty.kind(interner) {
  44         TyKind::Dyn(dyn_ty) => dyn_ty.clone(),
  45         _ => return,
  46     };
  47     let generalized_dyn_ty = generalize::Generalize::apply(db.interner(), dyn_ty);
  48
  49     // Here, `self_ty` is the `dyn Fn(&u8)`, and `dyn_ty` is the `exists<T> { ..
  50     // }` clauses shown above.
  51
  52     // Turn free BoundVars in the type into new existentials. E.g.
  53     // we might get some `dyn Foo<?X>`, and we don't want to return
  54     // a clause with a free variable. We can instead return a
  55     // slightly more general clause by basically turning this into
  56     // `exists<A> dyn Foo<A>`.
  57
  58     builder.push_binders(generalized_dyn_ty, |builder, dyn_ty| {
  59         for exists_qwc in dyn_ty.bounds.map_ref(|r| r.iter(interner)) {
  60             // Replace the `T` from `exists<T> { .. }` with `self_ty`,
  61             // yielding clases like
  62             //
  63             // ```
  64             // forall<'a> { Implemented(dyn Fn(&u8): Fn<(&'a u8)>) }
  65             // ```
  66             let qwc = exists_qwc
  67                 .cloned()
  68                 .substitute(interner, &[self_ty.clone().cast(interner)]);
  69
  70             builder.push_binders(qwc, |builder, wc| match &wc {
  71                 // For the implemented traits, we need to elaborate super traits and add where clauses from the trait
  72                 WhereClause::Implemented(trait_ref) => {
  73                     push_dyn_ty_impl_clauses(db, builder, trait_ref.clone())
  74                 }
  75                 // Associated item bindings are just taken as facts (?)
  76                 WhereClause::AliasEq(_) => builder.push_fact(wc),
  77                 WhereClause::LifetimeOutlives(..) => {}
  78                 WhereClause::TypeOutlives(..) => {}
  79             });
  80         }
  81     });
  82 }
  83
  84 /// Generate `Implemented` clauses for a `dyn Trait` type. We need to generate
  85 /// `Implemented` clauses for all super traits, and for each trait we require
  86 /// its where clauses. (See #203.)
  87 fn push_dyn_ty_impl_clauses<I: Interner>(
  88     db: &dyn RustIrDatabase<I>,
  89     builder: &mut ClauseBuilder<'_, I>,
  90     trait_ref: TraitRef<I>,
  91 ) {
  92     let interner = db.interner();
  93     // We have some `dyn Trait`, and some `trait SuperTrait: WC`
  94     // which is a super trait of `Trait` (including actually
  95     // just being the same trait); then we want to push
  96     // `Implemented(dyn Trait: SuperTrait) :- WC`.
  97
  98     let super_trait_refs =
  99         super_traits(db, trait_ref.trait_id).substitute(interner, &trait_ref.substitution);
 100
 101     for q_super_trait_ref in super_trait_refs {
 102         builder.push_binders(q_super_trait_ref.clone(), |builder, super_trait_ref| {
 103             let trait_datum = db.trait_datum(super_trait_ref.trait_id);
 104             let wc = trait_datum
 105                 .where_clauses()
 106                 .cloned()
 107                 .substitute(interner, &super_trait_ref.substitution);
 108             builder.push_clause(super_trait_ref, wc);
 109         });
 110     }
 111 }
 112
 113 pub fn super_traits<I: Interner>(
 114     db: &dyn RustIrDatabase<I>,
 115     trait_id: TraitId<I>,
 116 ) -> Binders<Vec<Binders<TraitRef<I>>>> {
 117     let interner = db.interner();
 118     let mut seen_traits = FxHashSet::default();
 119     let trait_datum = db.trait_datum(trait_id);
 120     let trait_ref = Binders::empty(
 121         db.interner(),
 122         TraitRef {
 123             trait_id,
 124             substitution: trait_datum
 125                 .binders
 126                 .identity_substitution(interner)
 127                 .shifted_in(interner),
 128         },
 129     );
 130     let mut trait_refs = Vec::new();
 131     go(db, trait_ref, &mut seen_traits, &mut trait_refs);
 132
 133     fn go<I: Interner>(
 134         db: &dyn RustIrDatabase<I>,
 135         trait_ref: Binders<TraitRef<I>>,
 136         seen_traits: &mut FxHashSet<TraitId<I>>,
 137         trait_refs: &mut Vec<Binders<TraitRef<I>>>,
 138     ) {
 139         let interner = db.interner();
 140         let trait_id = trait_ref.skip_binders().trait_id;
 141         // Avoid cycles
 142         if !seen_traits.insert(trait_id) {
 143             return;
 144         }
 145         trait_refs.push(trait_ref.clone());
 146         let trait_datum = db.trait_datum(trait_id);
 147         let super_trait_refs = trait_datum
 148             .binders
 149             .map_ref(|td| {
 150                 td.where_clauses
 151                     .iter()
 152                     .filter_map(|qwc| {
 153                         qwc.as_ref().filter_map(|wc| match wc {
 154                             WhereClause::Implemented(tr) => {
 155                                 let self_ty = tr.self_type_parameter(db.interner());
 156
 157                                 // We're looking for where clauses
 158                                 // of the form `Self: Trait`. That's
 159                                 // ^1.0 because we're one binder in.
 160                                 if self_ty.bound_var(db.interner())
 161                                     != Some(BoundVar::new(DebruijnIndex::ONE, 0))
 162                                 {
 163                                     return None;
 164                                 }
 165                                 Some(tr.clone())
 166                             }
 167                             WhereClause::AliasEq(_) => None,
 168                             WhereClause::LifetimeOutlives(..) => None,
 169                             WhereClause::TypeOutlives(..) => None,
 170                         })
 171                     })
 172                     .collect::<Vec<_>>()
 173             })
 174             // we skip binders on the trait_ref here and add them to the binders
 175             // on the trait ref in the loop below. We could probably avoid this if
 176             // we could turn the `Binders<Vec<>>` into a `Vec<Binders<>>` easily.
 177             .substitute(db.interner(), &trait_ref.skip_binders().substitution);
 178         for q_super_trait_ref in super_trait_refs {
 179             // So now we need to combine the binders of trait_ref with the
 180             // binders of super_trait_ref.
 181             let actual_binders = Binders::new(trait_ref.binders.clone(), q_super_trait_ref);
 182             let q_super_trait_ref = actual_binders.fuse_binders(interner);
 183             go(db, q_super_trait_ref, seen_traits, trait_refs);
 184         }
 185         seen_traits.remove(&trait_id);
 186     }
 187
 188     Binders::new(trait_datum.binders.binders.clone(), trait_refs)
 189 }