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