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