crates/hir_ty/src/autoderef.rs

   1 //! In certain situations, rust automatically inserts derefs as necessary: for
   2 //! example, field accesses `foo.bar` still work when `foo` is actually a
   3 //! reference to a type with the field `bar`. This is an approximation of the
   4 //! logic in rustc (which lives in librustc_typeck/check/autoderef.rs).
   5
   6 use std::iter::successors;
   7
   8 use base_db::CrateId;
   9 use chalk_ir::{cast::Cast, fold::Fold, interner::HasInterner, VariableKind};
  10 use hir_def::lang_item::LangItemTarget;
  11 use hir_expand::name::name;
  12 use limit::Limit;
  13 use tracing::{info, warn};
  14
  15 use crate::{
  16     db::HirDatabase, static_lifetime, AliasEq, AliasTy, BoundVar, Canonical, CanonicalVarKinds,
  17     ConstrainedSubst, DebruijnIndex, Environment, Guidance, InEnvironment, Interner,
  18     ProjectionTyExt, Solution, Substitution, Ty, TyBuilder, TyKind,
  19 };
  20
  21 const AUTODEREF_RECURSION_LIMIT: Limit = Limit::new(10);
  22
  23 pub(crate) enum AutoderefKind {
  24     Builtin,
  25     Overloaded,
  26 }
  27
  28 pub(crate) struct Autoderef<'db> {
  29     db: &'db dyn HirDatabase,
  30     ty: Canonical<Ty>,
  31     at_start: bool,
  32     krate: Option<CrateId>,
  33     environment: Environment,
  34     steps: Vec<(AutoderefKind, Ty)>,
  35 }
  36
  37 impl<'db> Autoderef<'db> {
  38     pub(crate) fn new(
  39         db: &'db dyn HirDatabase,
  40         krate: Option<CrateId>,
  41         ty: InEnvironment<Canonical<Ty>>,
  42     ) -> Self {
  43         let InEnvironment { goal: ty, environment } = ty;
  44         Autoderef { db, ty, at_start: true, environment, krate, steps: Vec::new() }
  45     }
  46
  47     pub(crate) fn step_count(&self) -> usize {
  48         self.steps.len()
  49     }
  50
  51     pub(crate) fn steps(&self) -> &[(AutoderefKind, chalk_ir::Ty<Interner>)] {
  52         &self.steps
  53     }
  54
  55     pub(crate) fn final_ty(&self) -> Ty {
  56         self.ty.value.clone()
  57     }
  58 }
  59
  60 impl Iterator for Autoderef<'_> {
  61     type Item = (Canonical<Ty>, usize);
  62
  63     fn next(&mut self) -> Option<Self::Item> {
  64         if self.at_start {
  65             self.at_start = false;
  66             return Some((self.ty.clone(), 0));
  67         }
  68
  69         if AUTODEREF_RECURSION_LIMIT.check(self.steps.len() + 1).is_err() {
  70             return None;
  71         }
  72
  73         let (kind, new_ty) = if let Some(derefed) = builtin_deref(&self.ty.value) {
  74             (AutoderefKind::Builtin, Canonical { value: derefed, binders: self.ty.binders.clone() })
  75         } else {
  76             (
  77                 AutoderefKind::Overloaded,
  78                 deref_by_trait(
  79                     self.db,
  80                     self.krate?,
  81                     InEnvironment { goal: &self.ty, environment: self.environment.clone() },
  82                 )?,
  83             )
  84         };
  85
  86         self.steps.push((kind, self.ty.value.clone()));
  87         self.ty = new_ty;
  88
  89         Some((self.ty.clone(), self.step_count()))
  90     }
  91 }
  92
  93 // FIXME: replace uses of this with Autoderef above
  94 pub fn autoderef<'a>(
  95     db: &'a dyn HirDatabase,
  96     krate: Option<CrateId>,
  97     ty: InEnvironment<Canonical<Ty>>,
  98 ) -> impl Iterator<Item = Canonical<Ty>> + 'a {
  99     let InEnvironment { goal: ty, environment } = ty;
 100     successors(Some(ty), move |ty| {
 101         deref(db, krate?, InEnvironment { goal: ty, environment: environment.clone() })
 102     })
 103     .take(AUTODEREF_RECURSION_LIMIT.inner())
 104 }
 105
 106 pub(crate) fn deref(
 107     db: &dyn HirDatabase,
 108     krate: CrateId,
 109     ty: InEnvironment<&Canonical<Ty>>,
 110 ) -> Option<Canonical<Ty>> {
 111     let _p = profile::span("deref");
 112     match builtin_deref(&ty.goal.value) {
 113         Some(derefed) => Some(Canonical { value: derefed, binders: ty.goal.binders.clone() }),
 114         None => deref_by_trait(db, krate, ty),
 115     }
 116 }
 117
 118 fn builtin_deref(ty: &Ty) -> Option<Ty> {
 119     match ty.kind(&Interner) {
 120         TyKind::Ref(.., ty) => Some(ty.clone()),
 121         TyKind::Raw(.., ty) => Some(ty.clone()),
 122         _ => None,
 123     }
 124 }
 125
 126 fn deref_by_trait(
 127     db: &dyn HirDatabase,
 128     krate: CrateId,
 129     ty: InEnvironment<&Canonical<Ty>>,
 130 ) -> Option<Canonical<Ty>> {
 131     let _p = profile::span("deref_by_trait");
 132     let deref_trait = match db.lang_item(krate, "deref".into())? {
 133         LangItemTarget::TraitId(it) => it,
 134         _ => return None,
 135     };
 136     let target = db.trait_data(deref_trait).associated_type_by_name(&name![Target])?;
 137
 138     let projection = {
 139         let b = TyBuilder::assoc_type_projection(db, target);
 140         if b.remaining() != 1 {
 141             // the Target type + Deref trait should only have one generic parameter,
 142             // namely Deref's Self type
 143             return None;
 144         }
 145         b.push(ty.goal.value.clone()).build()
 146     };
 147
 148     // FIXME make the Canonical / bound var handling nicer
 149
 150     // Check that the type implements Deref at all
 151     let trait_ref = projection.trait_ref(db);
 152     let implements_goal = Canonical {
 153         binders: ty.goal.binders.clone(),
 154         value: InEnvironment {
 155             goal: trait_ref.cast(&Interner),
 156             environment: ty.environment.clone(),
 157         },
 158     };
 159     if db.trait_solve(krate, implements_goal).is_none() {
 160         return None;
 161     }
 162
 163     // Now do the assoc type projection
 164     let alias_eq = AliasEq {
 165         alias: AliasTy::Projection(projection),
 166         ty: TyKind::BoundVar(BoundVar::new(
 167             DebruijnIndex::INNERMOST,
 168             ty.goal.binders.len(&Interner),
 169         ))
 170         .intern(&Interner),
 171     };
 172
 173     let in_env = InEnvironment { goal: alias_eq.cast(&Interner), environment: ty.environment };
 174
 175     let canonical = Canonical {
 176         value: in_env,
 177         binders: CanonicalVarKinds::from_iter(
 178             &Interner,
 179             ty.goal.binders.iter(&Interner).cloned().chain(Some(chalk_ir::WithKind::new(
 180                 VariableKind::Ty(chalk_ir::TyVariableKind::General),
 181                 chalk_ir::UniverseIndex::ROOT,
 182             ))),
 183         ),
 184     };
 185
 186     let solution = db.trait_solve(krate, canonical)?;
 187
 188     match &solution {
 189         Solution::Unique(Canonical { value: ConstrainedSubst { subst, .. }, binders })
 190         | Solution::Ambig(Guidance::Definite(Canonical { value: subst, binders })) => {
 191             // FIXME: vars may contain solutions for any inference variables
 192             // that happened to be inside ty. To correctly handle these, we
 193             // would have to pass the solution up to the inference context, but
 194             // that requires a larger refactoring (especially if the deref
 195             // happens during method resolution). So for the moment, we just
 196             // check that we're not in the situation where we would actually
 197             // need to handle the values of the additional variables, i.e.
 198             // they're just being 'passed through'. In the 'standard' case where
 199             // we have `impl<T> Deref for Foo<T> { Target = T }`, that should be
 200             // the case.
 201
 202             // FIXME: if the trait solver decides to truncate the type, these
 203             // assumptions will be broken. We would need to properly introduce
 204             // new variables in that case
 205
 206             for i in 1..binders.len(&Interner) {
 207                 if subst.at(&Interner, i - 1).assert_ty_ref(&Interner).kind(&Interner)
 208                     != &TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, i - 1))
 209                 {
 210                     warn!("complex solution for derefing {:?}: {:?}, ignoring", ty.goal, solution);
 211                     return None;
 212                 }
 213             }
 214             // FIXME: we remove lifetime variables here since they can confuse
 215             // the method resolution code later
 216             Some(fixup_lifetime_variables(Canonical {
 217                 value: subst
 218                     .at(&Interner, subst.len(&Interner) - 1)
 219                     .assert_ty_ref(&Interner)
 220                     .clone(),
 221                 binders: binders.clone(),
 222             }))
 223         }
 224         Solution::Ambig(_) => {
 225             info!("Ambiguous solution for derefing {:?}: {:?}", ty.goal, solution);
 226             None
 227         }
 228     }
 229 }
 230
 231 fn fixup_lifetime_variables<T: Fold<Interner, Result = T> + HasInterner<Interner = Interner>>(
 232     c: Canonical<T>,
 233 ) -> Canonical<T> {
 234     // Removes lifetime variables from the Canonical, replacing them by static lifetimes.
 235     let mut i = 0;
 236     let subst = Substitution::from_iter(
 237         &Interner,
 238         c.binders.iter(&Interner).map(|vk| match vk.kind {
 239             VariableKind::Ty(_) => {
 240                 let index = i;
 241                 i += 1;
 242                 BoundVar::new(DebruijnIndex::INNERMOST, index).to_ty(&Interner).cast(&Interner)
 243             }
 244             VariableKind::Lifetime => static_lifetime().cast(&Interner),
 245             VariableKind::Const(_) => unimplemented!(),
 246         }),
 247     );
 248     let binders = CanonicalVarKinds::from_iter(
 249         &Interner,
 250         c.binders.iter(&Interner).filter(|vk| match vk.kind {
 251             VariableKind::Ty(_) => true,
 252             VariableKind::Lifetime => false,
 253             VariableKind::Const(_) => true,
 254         }),
 255     );
 256     let value = subst.apply(c.value, &Interner);
 257     Canonical { binders, value }
 258 }