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::{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::{known, 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, ConstData, ConstValue, GenericArgData, Interner, Substitution,
  28     TraitRef, TraitRefExt, TyKind, WhereClause,
  29 };
  30
  31 pub(crate) fn fn_traits(db: &dyn DefDatabase, krate: CrateId) -> impl Iterator<Item = TraitId> {
  32     [
  33         db.lang_item(krate, SmolStr::new_inline("fn")),
  34         db.lang_item(krate, SmolStr::new_inline("fn_mut")),
  35         db.lang_item(krate, SmolStr::new_inline("fn_once")),
  36     ]
  37     .into_iter()
  38     .flatten()
  39     .flat_map(|it| it.as_trait())
  40 }
  41
  42 fn direct_super_traits(db: &dyn DefDatabase, trait_: TraitId) -> SmallVec<[TraitId; 4]> {
  43     let resolver = trait_.resolver(db);
  44     // returning the iterator directly doesn't easily work because of
  45     // lifetime problems, but since there usually shouldn't be more than a
  46     // few direct traits this should be fine (we could even use some kind of
  47     // SmallVec if performance is a concern)
  48     let generic_params = db.generic_params(trait_.into());
  49     let trait_self = generic_params.find_trait_self_param();
  50     generic_params
  51         .where_predicates
  52         .iter()
  53         .filter_map(|pred| match pred {
  54             WherePredicate::ForLifetime { target, bound, .. }
  55             | WherePredicate::TypeBound { target, bound } => {
  56                 let is_trait = match target {
  57                     WherePredicateTypeTarget::TypeRef(type_ref) => match &**type_ref {
  58                         TypeRef::Path(p) => p.is_self_type(),
  59                         _ => false,
  60                     },
  61                     WherePredicateTypeTarget::TypeOrConstParam(local_id) => {
  62                         Some(*local_id) == trait_self
  63                     }
  64                 };
  65                 match is_trait {
  66                     true => bound.as_path(),
  67                     false => None,
  68                 }
  69             }
  70             WherePredicate::Lifetime { .. } => None,
  71         })
  72         .filter(|(_, bound_modifier)| matches!(bound_modifier, TraitBoundModifier::None))
  73         .filter_map(|(path, _)| match resolver.resolve_path_in_type_ns_fully(db, path.mod_path()) {
  74             Some(TypeNs::TraitId(t)) => Some(t),
  75             _ => None,
  76         })
  77         .collect()
  78 }
  79
  80 fn direct_super_trait_refs(db: &dyn HirDatabase, trait_ref: &TraitRef) -> Vec<TraitRef> {
  81     // returning the iterator directly doesn't easily work because of
  82     // lifetime problems, but since there usually shouldn't be more than a
  83     // few direct traits this should be fine (we could even use some kind of
  84     // SmallVec if performance is a concern)
  85     let generic_params = db.generic_params(trait_ref.hir_trait_id().into());
  86     let trait_self = match generic_params.find_trait_self_param() {
  87         Some(p) => TypeOrConstParamId { parent: trait_ref.hir_trait_id().into(), local_id: p },
  88         None => return Vec::new(),
  89     };
  90     db.generic_predicates_for_param(trait_self.parent, trait_self, None)
  91         .iter()
  92         .filter_map(|pred| {
  93             pred.as_ref().filter_map(|pred| match pred.skip_binders() {
  94                 // FIXME: how to correctly handle higher-ranked bounds here?
  95                 WhereClause::Implemented(tr) => Some(
  96                     tr.clone()
  97                         .shifted_out_to(Interner, DebruijnIndex::ONE)
  98                         .expect("FIXME unexpected higher-ranked trait bound"),
  99                 ),
 100                 _ => None,
 101             })
 102         })
 103         .map(|pred| pred.substitute(Interner, &trait_ref.substitution))
 104         .collect()
 105 }
 106
 107 /// Returns an iterator over the whole super trait hierarchy (including the
 108 /// trait itself).
 109 pub fn all_super_traits(db: &dyn DefDatabase, trait_: TraitId) -> SmallVec<[TraitId; 4]> {
 110     // we need to take care a bit here to avoid infinite loops in case of cycles
 111     // (i.e. if we have `trait A: B; trait B: A;`)
 112
 113     let mut result = smallvec![trait_];
 114     let mut i = 0;
 115     while let Some(&t) = result.get(i) {
 116         // yeah this is quadratic, but trait hierarchies should be flat
 117         // enough that this doesn't matter
 118         for tt in direct_super_traits(db, t) {
 119             if !result.contains(&tt) {
 120                 result.push(tt);
 121             }
 122         }
 123         i += 1;
 124     }
 125     result
 126 }
 127
 128 /// Given a trait ref (`Self: Trait`), builds all the implied trait refs for
 129 /// super traits. The original trait ref will be included. So the difference to
 130 /// `all_super_traits` is that we keep track of type parameters; for example if
 131 /// we have `Self: Trait<u32, i32>` and `Trait<T, U>: OtherTrait<U>` we'll get
 132 /// `Self: OtherTrait<i32>`.
 133 pub(super) fn all_super_trait_refs(db: &dyn HirDatabase, trait_ref: TraitRef) -> SuperTraits<'_> {
 134     SuperTraits { db, seen: iter::once(trait_ref.trait_id).collect(), stack: vec![trait_ref] }
 135 }
 136
 137 pub(super) struct SuperTraits<'a> {
 138     db: &'a dyn HirDatabase,
 139     stack: Vec<TraitRef>,
 140     seen: FxHashSet<ChalkTraitId>,
 141 }
 142
 143 impl<'a> SuperTraits<'a> {
 144     fn elaborate(&mut self, trait_ref: &TraitRef) {
 145         let mut trait_refs = direct_super_trait_refs(self.db, trait_ref);
 146         trait_refs.retain(|tr| !self.seen.contains(&tr.trait_id));
 147         self.stack.extend(trait_refs);
 148     }
 149 }
 150
 151 impl<'a> Iterator for SuperTraits<'a> {
 152     type Item = TraitRef;
 153
 154     fn next(&mut self) -> Option<Self::Item> {
 155         if let Some(next) = self.stack.pop() {
 156             self.elaborate(&next);
 157             Some(next)
 158         } else {
 159             None
 160         }
 161     }
 162 }
 163
 164 pub(super) fn associated_type_by_name_including_super_traits(
 165     db: &dyn HirDatabase,
 166     trait_ref: TraitRef,
 167     name: &Name,
 168 ) -> Option<(TraitRef, TypeAliasId)> {
 169     all_super_trait_refs(db, trait_ref).find_map(|t| {
 170         let assoc_type = db.trait_data(t.hir_trait_id()).associated_type_by_name(name)?;
 171         Some((t, assoc_type))
 172     })
 173 }
 174
 175 pub(crate) fn generics(db: &dyn DefDatabase, def: GenericDefId) -> Generics {
 176     let parent_generics = parent_generic_def(db, def).map(|def| Box::new(generics(db, def)));
 177     if parent_generics.is_some() && matches!(def, GenericDefId::TypeAliasId(_)) {
 178         let params = db.generic_params(def);
 179         let parent_params = &parent_generics.as_ref().unwrap().params;
 180         let has_consts =
 181             params.iter().any(|(_, x)| matches!(x, TypeOrConstParamData::ConstParamData(_)));
 182         let parent_has_consts =
 183             parent_params.iter().any(|(_, x)| matches!(x, TypeOrConstParamData::ConstParamData(_)));
 184         return if has_consts || parent_has_consts {
 185             // XXX: treat const generic associated types as not existing to avoid crashes
 186             // (#11769)
 187             //
 188             // Note: Also crashes when the parent has const generics (also even if the GAT
 189             // doesn't use them), see `tests::regression::gat_crash_3` for an example.
 190             // Avoids that by disabling GATs when the parent (i.e. `impl` block) has
 191             // const generics (#12193).
 192             //
 193             // Chalk expects the inner associated type's parameters to come
 194             // *before*, not after the trait's generics as we've always done it.
 195             // Adapting to this requires a larger refactoring
 196             cov_mark::hit!(ignore_gats);
 197             Generics { def, params: Interned::new(Default::default()), parent_generics }
 198         } else {
 199             Generics { def, params, parent_generics }
 200         };
 201     }
 202     Generics { def, params: db.generic_params(def), parent_generics }
 203 }
 204
 205 #[derive(Debug)]
 206 pub(crate) struct Generics {
 207     def: GenericDefId,
 208     pub(crate) params: Interned<GenericParams>,
 209     parent_generics: Option<Box<Generics>>,
 210 }
 211
 212 impl Generics {
 213     pub(crate) fn iter_id<'a>(
 214         &'a self,
 215     ) -> impl Iterator<Item = Either<TypeParamId, ConstParamId>> + 'a {
 216         self.iter().map(|(id, data)| match data {
 217             TypeOrConstParamData::TypeParamData(_) => Either::Left(TypeParamId::from_unchecked(id)),
 218             TypeOrConstParamData::ConstParamData(_) => {
 219                 Either::Right(ConstParamId::from_unchecked(id))
 220             }
 221         })
 222     }
 223
 224     /// Iterator over types and const params of parent, then self.
 225     pub(crate) fn iter<'a>(
 226         &'a self,
 227     ) -> impl DoubleEndedIterator<Item = (TypeOrConstParamId, &'a TypeOrConstParamData)> + 'a {
 228         let to_toc_id = |it: &'a Generics| {
 229             move |(local_id, p)| (TypeOrConstParamId { parent: it.def, local_id }, p)
 230         };
 231         self.parent_generics()
 232             .into_iter()
 233             .flat_map(move |it| it.params.iter().map(to_toc_id(it)))
 234             .chain(self.params.iter().map(to_toc_id(self)))
 235     }
 236
 237     /// Iterator over types and const params of parent.
 238     pub(crate) fn iter_parent<'a>(
 239         &'a self,
 240     ) -> impl Iterator<Item = (TypeOrConstParamId, &'a TypeOrConstParamData)> + 'a {
 241         self.parent_generics().into_iter().flat_map(|it| {
 242             let to_toc_id =
 243                 move |(local_id, p)| (TypeOrConstParamId { parent: it.def, local_id }, p);
 244             it.params.iter().map(to_toc_id)
 245         })
 246     }
 247
 248     pub(crate) fn len(&self) -> usize {
 249         let parent = self.parent_generics().map_or(0, Generics::len);
 250         let child = self.params.type_or_consts.len();
 251         parent + child
 252     }
 253
 254     /// (parent total, self param, type param list, const param list, impl trait)
 255     pub(crate) fn provenance_split(&self) -> (usize, usize, usize, usize, usize) {
 256         let ty_iter = || self.params.iter().filter_map(|x| x.1.type_param());
 257
 258         let self_params =
 259             ty_iter().filter(|p| p.provenance == TypeParamProvenance::TraitSelf).count();
 260         let type_params =
 261             ty_iter().filter(|p| p.provenance == TypeParamProvenance::TypeParamList).count();
 262         let impl_trait_params =
 263             ty_iter().filter(|p| p.provenance == TypeParamProvenance::ArgumentImplTrait).count();
 264         let const_params = self.params.iter().filter_map(|x| x.1.const_param()).count();
 265
 266         let parent_len = self.parent_generics().map_or(0, Generics::len);
 267         (parent_len, self_params, type_params, const_params, impl_trait_params)
 268     }
 269
 270     pub(crate) fn param_idx(&self, param: TypeOrConstParamId) -> Option<usize> {
 271         Some(self.find_param(param)?.0)
 272     }
 273
 274     fn find_param(&self, param: TypeOrConstParamId) -> Option<(usize, &TypeOrConstParamData)> {
 275         if param.parent == self.def {
 276             let (idx, (_local_id, data)) =
 277                 self.params.iter().enumerate().find(|(_, (idx, _))| *idx == param.local_id)?;
 278             let parent_len = self.parent_generics().map_or(0, Generics::len);
 279             Some((parent_len + idx, data))
 280         } else {
 281             self.parent_generics().and_then(|g| g.find_param(param))
 282         }
 283     }
 284
 285     fn parent_generics(&self) -> Option<&Generics> {
 286         self.parent_generics.as_ref().map(|it| &**it)
 287     }
 288
 289     /// Returns a Substitution that replaces each parameter by a bound variable.
 290     pub(crate) fn bound_vars_subst(
 291         &self,
 292         db: &dyn HirDatabase,
 293         debruijn: DebruijnIndex,
 294     ) -> Substitution {
 295         Substitution::from_iter(
 296             Interner,
 297             self.iter_id().enumerate().map(|(idx, id)| match id {
 298                 Either::Left(_) => GenericArgData::Ty(
 299                     TyKind::BoundVar(BoundVar::new(debruijn, idx)).intern(Interner),
 300                 )
 301                 .intern(Interner),
 302                 Either::Right(id) => GenericArgData::Const(
 303                     ConstData {
 304                         value: ConstValue::BoundVar(BoundVar::new(debruijn, idx)),
 305                         ty: db.const_param_ty(id),
 306                     }
 307                     .intern(Interner),
 308                 )
 309                 .intern(Interner),
 310             }),
 311         )
 312     }
 313
 314     /// Returns a Substitution that replaces each parameter by itself (i.e. `Ty::Param`).
 315     pub(crate) fn placeholder_subst(&self, db: &dyn HirDatabase) -> Substitution {
 316         Substitution::from_iter(
 317             Interner,
 318             self.iter_id().map(|id| match id {
 319                 Either::Left(id) => GenericArgData::Ty(
 320                     TyKind::Placeholder(crate::to_placeholder_idx(db, id.into())).intern(Interner),
 321                 )
 322                 .intern(Interner),
 323                 Either::Right(id) => GenericArgData::Const(
 324                     ConstData {
 325                         value: ConstValue::Placeholder(crate::to_placeholder_idx(db, id.into())),
 326                         ty: db.const_param_ty(id),
 327                     }
 328                     .intern(Interner),
 329                 )
 330                 .intern(Interner),
 331             }),
 332         )
 333     }
 334 }
 335
 336 fn parent_generic_def(db: &dyn DefDatabase, def: GenericDefId) -> Option<GenericDefId> {
 337     let container = match def {
 338         GenericDefId::FunctionId(it) => it.lookup(db).container,
 339         GenericDefId::TypeAliasId(it) => it.lookup(db).container,
 340         GenericDefId::ConstId(it) => it.lookup(db).container,
 341         GenericDefId::EnumVariantId(it) => return Some(it.parent.into()),
 342         GenericDefId::AdtId(_) | GenericDefId::TraitId(_) | GenericDefId::ImplId(_) => return None,
 343     };
 344
 345     match container {
 346         ItemContainerId::ImplId(it) => Some(it.into()),
 347         ItemContainerId::TraitId(it) => Some(it.into()),
 348         ItemContainerId::ModuleId(_) | ItemContainerId::ExternBlockId(_) => None,
 349     }
 350 }
 351
 352 pub fn is_fn_unsafe_to_call(db: &dyn HirDatabase, func: FunctionId) -> bool {
 353     let data = db.function_data(func);
 354     if data.has_unsafe_kw() {
 355         return true;
 356     }
 357
 358     match func.lookup(db.upcast()).container {
 359         hir_def::ItemContainerId::ExternBlockId(block) => {
 360             // Function in an `extern` block are always unsafe to call, except when it has
 361             // `"rust-intrinsic"` ABI there are a few exceptions.
 362             let id = block.lookup(db.upcast()).id;
 363             !matches!(
 364                 id.item_tree(db.upcast())[id.value].abi.as_deref(),
 365                 Some("rust-intrinsic") if !is_intrinsic_fn_unsafe(&data.name)
 366             )
 367         }
 368         _ => false,
 369     }
 370 }
 371
 372 /// Returns `true` if the given intrinsic is unsafe to call, or false otherwise.
 373 fn is_intrinsic_fn_unsafe(name: &Name) -> bool {
 374     // Should be kept in sync with https://github.com/rust-lang/rust/blob/532d2b14c05f9bc20b2d27cbb5f4550d28343a36/compiler/rustc_typeck/src/check/intrinsic.rs#L72-L106
 375     ![
 376         known::abort,
 377         known::add_with_overflow,
 378         known::bitreverse,
 379         known::black_box,
 380         known::bswap,
 381         known::caller_location,
 382         known::ctlz,
 383         known::ctpop,
 384         known::cttz,
 385         known::discriminant_value,
 386         known::forget,
 387         known::likely,
 388         known::maxnumf32,
 389         known::maxnumf64,
 390         known::min_align_of,
 391         known::minnumf32,
 392         known::minnumf64,
 393         known::mul_with_overflow,
 394         known::needs_drop,
 395         known::ptr_guaranteed_eq,
 396         known::ptr_guaranteed_ne,
 397         known::rotate_left,
 398         known::rotate_right,
 399         known::rustc_peek,
 400         known::saturating_add,
 401         known::saturating_sub,
 402         known::size_of,
 403         known::sub_with_overflow,
 404         known::type_id,
 405         known::type_name,
 406         known::unlikely,
 407         known::variant_count,
 408         known::wrapping_add,
 409         known::wrapping_mul,
 410         known::wrapping_sub,
 411     ]
 412     .contains(name)
 413 }