src/tools/rust-analyzer/crates/hir-ty/src/utils.rs

   1 //! Helper functions for working with def, which don't need to be a separate
   2 //! query, but can't be computed directly from `*Data` (ie, which need a `db`).
   3
   4 use std::iter;
   5
   6 use base_db::CrateId;
   7 use chalk_ir::{cast::Cast, fold::Shift, BoundVar, DebruijnIndex};
   8 use hir_def::{
   9     db::DefDatabase,
  10     generics::{
  11         GenericParams, TypeOrConstParamData, TypeParamProvenance, WherePredicate,
  12         WherePredicateTypeTarget,
  13     },
  14     intern::Interned,
  15     resolver::{HasResolver, TypeNs},
  16     type_ref::{TraitBoundModifier, TypeRef},
  17     ConstParamId, FunctionId, GenericDefId, ItemContainerId, Lookup, TraitId, TypeAliasId,
  18     TypeOrConstParamId, TypeParamId,
  19 };
  20 use hir_expand::name::Name;
  21 use itertools::Either;
  22 use rustc_hash::FxHashSet;
  23 use smallvec::{smallvec, SmallVec};
  24 use syntax::SmolStr;
  25
  26 use crate::{
  27     db::HirDatabase, ChalkTraitId, Interner, Substitution, TraitRef, TraitRefExt, WhereClause,
  28 };
  29
  30 pub(crate) fn fn_traits(db: &dyn DefDatabase, krate: CrateId) -> impl Iterator<Item = TraitId> {
  31     [
  32         db.lang_item(krate, SmolStr::new_inline("fn")),
  33         db.lang_item(krate, SmolStr::new_inline("fn_mut")),
  34         db.lang_item(krate, SmolStr::new_inline("fn_once")),
  35     ]
  36     .into_iter()
  37     .flatten()
  38     .flat_map(|it| it.as_trait())
  39 }
  40
  41 fn direct_super_traits(db: &dyn DefDatabase, trait_: TraitId) -> SmallVec<[TraitId; 4]> {
  42     let resolver = trait_.resolver(db);
  43     // returning the iterator directly doesn't easily work because of
  44     // lifetime problems, but since there usually shouldn't be more than a
  45     // few direct traits this should be fine (we could even use some kind of
  46     // SmallVec if performance is a concern)
  47     let generic_params = db.generic_params(trait_.into());
  48     let trait_self = generic_params.find_trait_self_param();
  49     generic_params
  50         .where_predicates
  51         .iter()
  52         .filter_map(|pred| match pred {
  53             WherePredicate::ForLifetime { target, bound, .. }
  54             | WherePredicate::TypeBound { target, bound } => {
  55                 let is_trait = match target {
  56                     WherePredicateTypeTarget::TypeRef(type_ref) => match &**type_ref {
  57                         TypeRef::Path(p) => p.is_self_type(),
  58                         _ => false,
  59                     },
  60                     WherePredicateTypeTarget::TypeOrConstParam(local_id) => {
  61                         Some(*local_id) == trait_self
  62                     }
  63                 };
  64                 match is_trait {
  65                     true => bound.as_path(),
  66                     false => None,
  67                 }
  68             }
  69             WherePredicate::Lifetime { .. } => None,
  70         })
  71         .filter(|(_, bound_modifier)| matches!(bound_modifier, TraitBoundModifier::None))
  72         .filter_map(|(path, _)| match resolver.resolve_path_in_type_ns_fully(db, path.mod_path()) {
  73             Some(TypeNs::TraitId(t)) => Some(t),
  74             _ => None,
  75         })
  76         .collect()
  77 }
  78
  79 fn direct_super_trait_refs(db: &dyn HirDatabase, trait_ref: &TraitRef) -> Vec<TraitRef> {
  80     // returning the iterator directly doesn't easily work because of
  81     // lifetime problems, but since there usually shouldn't be more than a
  82     // few direct traits this should be fine (we could even use some kind of
  83     // SmallVec if performance is a concern)
  84     let generic_params = db.generic_params(trait_ref.hir_trait_id().into());
  85     let trait_self = match generic_params.find_trait_self_param() {
  86         Some(p) => TypeOrConstParamId { parent: trait_ref.hir_trait_id().into(), local_id: p },
  87         None => return Vec::new(),
  88     };
  89     db.generic_predicates_for_param(trait_self.parent, trait_self, None)
  90         .iter()
  91         .filter_map(|pred| {
  92             pred.as_ref().filter_map(|pred| match pred.skip_binders() {
  93                 // FIXME: how to correctly handle higher-ranked bounds here?
  94                 WhereClause::Implemented(tr) => Some(
  95                     tr.clone()
  96                         .shifted_out_to(Interner, DebruijnIndex::ONE)
  97                         .expect("FIXME unexpected higher-ranked trait bound"),
  98                 ),
  99                 _ => None,
 100             })
 101         })
 102         .map(|pred| pred.substitute(Interner, &trait_ref.substitution))
 103         .collect()
 104 }
 105
 106 /// Returns an iterator over the whole super trait hierarchy (including the
 107 /// trait itself).
 108 pub fn all_super_traits(db: &dyn DefDatabase, trait_: TraitId) -> SmallVec<[TraitId; 4]> {
 109     // we need to take care a bit here to avoid infinite loops in case of cycles
 110     // (i.e. if we have `trait A: B; trait B: A;`)
 111
 112     let mut result = smallvec![trait_];
 113     let mut i = 0;
 114     while let Some(&t) = result.get(i) {
 115         // yeah this is quadratic, but trait hierarchies should be flat
 116         // enough that this doesn't matter
 117         for tt in direct_super_traits(db, t) {
 118             if !result.contains(&tt) {
 119                 result.push(tt);
 120             }
 121         }
 122         i += 1;
 123     }
 124     result
 125 }
 126
 127 /// Given a trait ref (`Self: Trait`), builds all the implied trait refs for
 128 /// super traits. The original trait ref will be included. So the difference to
 129 /// `all_super_traits` is that we keep track of type parameters; for example if
 130 /// we have `Self: Trait<u32, i32>` and `Trait<T, U>: OtherTrait<U>` we'll get
 131 /// `Self: OtherTrait<i32>`.
 132 pub(super) fn all_super_trait_refs(db: &dyn HirDatabase, trait_ref: TraitRef) -> SuperTraits<'_> {
 133     SuperTraits { db, seen: iter::once(trait_ref.trait_id).collect(), stack: vec![trait_ref] }
 134 }
 135
 136 pub(super) struct SuperTraits<'a> {
 137     db: &'a dyn HirDatabase,
 138     stack: Vec<TraitRef>,
 139     seen: FxHashSet<ChalkTraitId>,
 140 }
 141
 142 impl<'a> SuperTraits<'a> {
 143     fn elaborate(&mut self, trait_ref: &TraitRef) {
 144         let mut trait_refs = direct_super_trait_refs(self.db, trait_ref);
 145         trait_refs.retain(|tr| !self.seen.contains(&tr.trait_id));
 146         self.stack.extend(trait_refs);
 147     }
 148 }
 149
 150 impl<'a> Iterator for SuperTraits<'a> {
 151     type Item = TraitRef;
 152
 153     fn next(&mut self) -> Option<Self::Item> {
 154         if let Some(next) = self.stack.pop() {
 155             self.elaborate(&next);
 156             Some(next)
 157         } else {
 158             None
 159         }
 160     }
 161 }
 162
 163 pub(super) fn associated_type_by_name_including_super_traits(
 164     db: &dyn HirDatabase,
 165     trait_ref: TraitRef,
 166     name: &Name,
 167 ) -> Option<(TraitRef, TypeAliasId)> {
 168     all_super_trait_refs(db, trait_ref).find_map(|t| {
 169         let assoc_type = db.trait_data(t.hir_trait_id()).associated_type_by_name(name)?;
 170         Some((t, assoc_type))
 171     })
 172 }
 173
 174 pub(crate) fn generics(db: &dyn DefDatabase, def: GenericDefId) -> Generics {
 175     let parent_generics = parent_generic_def(db, def).map(|def| Box::new(generics(db, def)));
 176     Generics { def, params: db.generic_params(def), parent_generics }
 177 }
 178
 179 #[derive(Debug)]
 180 pub(crate) struct Generics {
 181     def: GenericDefId,
 182     pub(crate) params: Interned<GenericParams>,
 183     parent_generics: Option<Box<Generics>>,
 184 }
 185
 186 impl Generics {
 187     pub(crate) fn iter_id(&self) -> impl Iterator<Item = Either<TypeParamId, ConstParamId>> + '_ {
 188         self.iter().map(|(id, data)| match data {
 189             TypeOrConstParamData::TypeParamData(_) => Either::Left(TypeParamId::from_unchecked(id)),
 190             TypeOrConstParamData::ConstParamData(_) => {
 191                 Either::Right(ConstParamId::from_unchecked(id))
 192             }
 193         })
 194     }
 195
 196     /// Iterator over types and const params of self, then parent.
 197     pub(crate) fn iter<'a>(
 198         &'a self,
 199     ) -> impl DoubleEndedIterator<Item = (TypeOrConstParamId, &'a TypeOrConstParamData)> + 'a {
 200         let to_toc_id = |it: &'a Generics| {
 201             move |(local_id, p)| (TypeOrConstParamId { parent: it.def, local_id }, p)
 202         };
 203         self.params.iter().map(to_toc_id(self)).chain(self.iter_parent())
 204     }
 205
 206     /// Iterate over types and const params without parent params.
 207     pub(crate) fn iter_self<'a>(
 208         &'a self,
 209     ) -> impl DoubleEndedIterator<Item = (TypeOrConstParamId, &'a TypeOrConstParamData)> + 'a {
 210         let to_toc_id = |it: &'a Generics| {
 211             move |(local_id, p)| (TypeOrConstParamId { parent: it.def, local_id }, p)
 212         };
 213         self.params.iter().map(to_toc_id(self))
 214     }
 215
 216     /// Iterator over types and const params of parent.
 217     pub(crate) fn iter_parent(
 218         &self,
 219     ) -> impl DoubleEndedIterator<Item = (TypeOrConstParamId, &TypeOrConstParamData)> {
 220         self.parent_generics().into_iter().flat_map(|it| {
 221             let to_toc_id =
 222                 move |(local_id, p)| (TypeOrConstParamId { parent: it.def, local_id }, p);
 223             it.params.iter().map(to_toc_id)
 224         })
 225     }
 226
 227     /// Returns total number of generic parameters in scope, including those from parent.
 228     pub(crate) fn len(&self) -> usize {
 229         let parent = self.parent_generics().map_or(0, Generics::len);
 230         let child = self.params.type_or_consts.len();
 231         parent + child
 232     }
 233
 234     /// Returns numbers of generic parameters excluding those from parent.
 235     pub(crate) fn len_self(&self) -> usize {
 236         self.params.type_or_consts.len()
 237     }
 238
 239     /// (parent total, self param, type param list, const param list, impl trait)
 240     pub(crate) fn provenance_split(&self) -> (usize, usize, usize, usize, usize) {
 241         let ty_iter = || self.params.iter().filter_map(|x| x.1.type_param());
 242
 243         let self_params =
 244             ty_iter().filter(|p| p.provenance == TypeParamProvenance::TraitSelf).count();
 245         let type_params =
 246             ty_iter().filter(|p| p.provenance == TypeParamProvenance::TypeParamList).count();
 247         let impl_trait_params =
 248             ty_iter().filter(|p| p.provenance == TypeParamProvenance::ArgumentImplTrait).count();
 249         let const_params = self.params.iter().filter_map(|x| x.1.const_param()).count();
 250
 251         let parent_len = self.parent_generics().map_or(0, Generics::len);
 252         (parent_len, self_params, type_params, const_params, impl_trait_params)
 253     }
 254
 255     pub(crate) fn param_idx(&self, param: TypeOrConstParamId) -> Option<usize> {
 256         Some(self.find_param(param)?.0)
 257     }
 258
 259     fn find_param(&self, param: TypeOrConstParamId) -> Option<(usize, &TypeOrConstParamData)> {
 260         if param.parent == self.def {
 261             let (idx, (_local_id, data)) =
 262                 self.params.iter().enumerate().find(|(_, (idx, _))| *idx == param.local_id)?;
 263             Some((idx, data))
 264         } else {
 265             self.parent_generics()
 266                 .and_then(|g| g.find_param(param))
 267                 // Remember that parent parameters come after parameters for self.
 268                 .map(|(idx, data)| (self.len_self() + idx, data))
 269         }
 270     }
 271
 272     pub(crate) fn parent_generics(&self) -> Option<&Generics> {
 273         self.parent_generics.as_deref()
 274     }
 275
 276     /// Returns a Substitution that replaces each parameter by a bound variable.
 277     pub(crate) fn bound_vars_subst(
 278         &self,
 279         db: &dyn HirDatabase,
 280         debruijn: DebruijnIndex,
 281     ) -> Substitution {
 282         Substitution::from_iter(
 283             Interner,
 284             self.iter_id().enumerate().map(|(idx, id)| match id {
 285                 Either::Left(_) => BoundVar::new(debruijn, idx).to_ty(Interner).cast(Interner),
 286                 Either::Right(id) => BoundVar::new(debruijn, idx)
 287                     .to_const(Interner, db.const_param_ty(id))
 288                     .cast(Interner),
 289             }),
 290         )
 291     }
 292
 293     /// Returns a Substitution that replaces each parameter by itself (i.e. `Ty::Param`).
 294     pub(crate) fn placeholder_subst(&self, db: &dyn HirDatabase) -> Substitution {
 295         Substitution::from_iter(
 296             Interner,
 297             self.iter_id().map(|id| match id {
 298                 Either::Left(id) => {
 299                     crate::to_placeholder_idx(db, id.into()).to_ty(Interner).cast(Interner)
 300                 }
 301                 Either::Right(id) => crate::to_placeholder_idx(db, id.into())
 302                     .to_const(Interner, db.const_param_ty(id))
 303                     .cast(Interner),
 304             }),
 305         )
 306     }
 307 }
 308
 309 fn parent_generic_def(db: &dyn DefDatabase, def: GenericDefId) -> Option<GenericDefId> {
 310     let container = match def {
 311         GenericDefId::FunctionId(it) => it.lookup(db).container,
 312         GenericDefId::TypeAliasId(it) => it.lookup(db).container,
 313         GenericDefId::ConstId(it) => it.lookup(db).container,
 314         GenericDefId::EnumVariantId(it) => return Some(it.parent.into()),
 315         GenericDefId::AdtId(_) | GenericDefId::TraitId(_) | GenericDefId::ImplId(_) => return None,
 316     };
 317
 318     match container {
 319         ItemContainerId::ImplId(it) => Some(it.into()),
 320         ItemContainerId::TraitId(it) => Some(it.into()),
 321         ItemContainerId::ModuleId(_) | ItemContainerId::ExternBlockId(_) => None,
 322     }
 323 }
 324
 325 pub fn is_fn_unsafe_to_call(db: &dyn HirDatabase, func: FunctionId) -> bool {
 326     let data = db.function_data(func);
 327     if data.has_unsafe_kw() {
 328         return true;
 329     }
 330
 331     match func.lookup(db.upcast()).container {
 332         hir_def::ItemContainerId::ExternBlockId(block) => {
 333             // Function in an `extern` block are always unsafe to call, except when it has
 334             // `"rust-intrinsic"` ABI there are a few exceptions.
 335             let id = block.lookup(db.upcast()).id;
 336
 337             let is_intrinsic =
 338                 id.item_tree(db.upcast())[id.value].abi.as_deref() == Some("rust-intrinsic");
 339
 340             if is_intrinsic {
 341                 // Intrinsics are unsafe unless they have the rustc_safe_intrinsic attribute
 342                 !data.attrs.by_key("rustc_safe_intrinsic").exists()
 343             } else {
 344                 // Extern items are always unsafe
 345                 true
 346             }
 347         }
 348         _ => false,
 349     }
 350 }