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 use std::sync::Arc;
   4
   5 use hir_def::{
   6     adt::VariantData,
   7     db::DefDatabase,
   8     generics::{
   9         GenericParams, TypeParamData, TypeParamProvenance, WherePredicate, WherePredicateTypeTarget,
  10     },
  11     path::Path,
  12     resolver::{HasResolver, TypeNs},
  13     type_ref::TypeRef,
  14     AssocContainerId, GenericDefId, Lookup, TraitId, TypeAliasId, TypeParamId, VariantId,
  15 };
  16 use hir_expand::name::{name, Name};
  17
  18 use crate::{db::HirDatabase, GenericPredicate, TraitRef};
  19
  20 fn direct_super_traits(db: &dyn DefDatabase, trait_: TraitId) -> Vec<TraitId> {
  21     let resolver = trait_.resolver(db);
  22     // returning the iterator directly doesn't easily work because of
  23     // lifetime problems, but since there usually shouldn't be more than a
  24     // few direct traits this should be fine (we could even use some kind of
  25     // SmallVec if performance is a concern)
  26     let generic_params = db.generic_params(trait_.into());
  27     let trait_self = generic_params.find_trait_self_param();
  28     generic_params
  29         .where_predicates
  30         .iter()
  31         .filter_map(|pred| match pred {
  32             WherePredicate::ForLifetime { target, bound, .. }
  33             | WherePredicate::TypeBound { target, bound } => match target {
  34                 WherePredicateTypeTarget::TypeRef(TypeRef::Path(p))
  35                     if p == &Path::from(name![Self]) =>
  36                 {
  37                     bound.as_path()
  38                 }
  39                 WherePredicateTypeTarget::TypeParam(local_id) if Some(*local_id) == trait_self => {
  40                     bound.as_path()
  41                 }
  42                 _ => None,
  43             },
  44             WherePredicate::Lifetime { .. } => None,
  45         })
  46         .filter_map(|path| match resolver.resolve_path_in_type_ns_fully(db, path.mod_path()) {
  47             Some(TypeNs::TraitId(t)) => Some(t),
  48             _ => None,
  49         })
  50         .collect()
  51 }
  52
  53 fn direct_super_trait_refs(db: &dyn HirDatabase, trait_ref: &TraitRef) -> Vec<TraitRef> {
  54     // returning the iterator directly doesn't easily work because of
  55     // lifetime problems, but since there usually shouldn't be more than a
  56     // few direct traits this should be fine (we could even use some kind of
  57     // SmallVec if performance is a concern)
  58     let generic_params = db.generic_params(trait_ref.trait_.into());
  59     let trait_self = match generic_params.find_trait_self_param() {
  60         Some(p) => TypeParamId { parent: trait_ref.trait_.into(), local_id: p },
  61         None => return Vec::new(),
  62     };
  63     db.generic_predicates_for_param(trait_self)
  64         .iter()
  65         .filter_map(|pred| {
  66             pred.as_ref().filter_map(|pred| match pred {
  67                 GenericPredicate::Implemented(tr) => Some(tr.clone()),
  68                 _ => None,
  69             })
  70         })
  71         .map(|pred| pred.subst(&trait_ref.substs))
  72         .collect()
  73 }
  74
  75 /// Returns an iterator over the whole super trait hierarchy (including the
  76 /// trait itself).
  77 pub(super) fn all_super_traits(db: &dyn DefDatabase, trait_: TraitId) -> Vec<TraitId> {
  78     // we need to take care a bit here to avoid infinite loops in case of cycles
  79     // (i.e. if we have `trait A: B; trait B: A;`)
  80     let mut result = vec![trait_];
  81     let mut i = 0;
  82     while i < result.len() {
  83         let t = result[i];
  84         // yeah this is quadratic, but trait hierarchies should be flat
  85         // enough that this doesn't matter
  86         for tt in direct_super_traits(db, t) {
  87             if !result.contains(&tt) {
  88                 result.push(tt);
  89             }
  90         }
  91         i += 1;
  92     }
  93     result
  94 }
  95
  96 /// Given a trait ref (`Self: Trait`), builds all the implied trait refs for
  97 /// super traits. The original trait ref will be included. So the difference to
  98 /// `all_super_traits` is that we keep track of type parameters; for example if
  99 /// we have `Self: Trait<u32, i32>` and `Trait<T, U>: OtherTrait<U>` we'll get
 100 /// `Self: OtherTrait<i32>`.
 101 pub(super) fn all_super_trait_refs(db: &dyn HirDatabase, trait_ref: TraitRef) -> Vec<TraitRef> {
 102     // we need to take care a bit here to avoid infinite loops in case of cycles
 103     // (i.e. if we have `trait A: B; trait B: A;`)
 104     let mut result = vec![trait_ref];
 105     let mut i = 0;
 106     while i < result.len() {
 107         let t = &result[i];
 108         // yeah this is quadratic, but trait hierarchies should be flat
 109         // enough that this doesn't matter
 110         for tt in direct_super_trait_refs(db, t) {
 111             if !result.iter().any(|tr| tr.trait_ == tt.trait_) {
 112                 result.push(tt);
 113             }
 114         }
 115         i += 1;
 116     }
 117     result
 118 }
 119
 120 pub(super) fn associated_type_by_name_including_super_traits(
 121     db: &dyn HirDatabase,
 122     trait_ref: TraitRef,
 123     name: &Name,
 124 ) -> Option<(TraitRef, TypeAliasId)> {
 125     all_super_trait_refs(db, trait_ref).into_iter().find_map(|t| {
 126         let assoc_type = db.trait_data(t.trait_).associated_type_by_name(name)?;
 127         Some((t, assoc_type))
 128     })
 129 }
 130
 131 pub(super) fn variant_data(db: &dyn DefDatabase, var: VariantId) -> Arc<VariantData> {
 132     match var {
 133         VariantId::StructId(it) => db.struct_data(it).variant_data.clone(),
 134         VariantId::UnionId(it) => db.union_data(it).variant_data.clone(),
 135         VariantId::EnumVariantId(it) => {
 136             db.enum_data(it.parent).variants[it.local_id].variant_data.clone()
 137         }
 138     }
 139 }
 140
 141 /// Helper for mutating `Arc<[T]>` (i.e. `Arc::make_mut` for Arc slices).
 142 /// The underlying values are cloned if there are other strong references.
 143 pub(crate) fn make_mut_slice<T: Clone>(a: &mut Arc<[T]>) -> &mut [T] {
 144     if Arc::get_mut(a).is_none() {
 145         *a = a.iter().cloned().collect();
 146     }
 147     Arc::get_mut(a).unwrap()
 148 }
 149
 150 pub(crate) fn generics(db: &dyn DefDatabase, def: GenericDefId) -> Generics {
 151     let parent_generics = parent_generic_def(db, def).map(|def| Box::new(generics(db, def)));
 152     Generics { def, params: db.generic_params(def), parent_generics }
 153 }
 154
 155 #[derive(Debug)]
 156 pub(crate) struct Generics {
 157     def: GenericDefId,
 158     pub(crate) params: Arc<GenericParams>,
 159     parent_generics: Option<Box<Generics>>,
 160 }
 161
 162 impl Generics {
 163     pub(crate) fn iter<'a>(
 164         &'a self,
 165     ) -> impl Iterator<Item = (TypeParamId, &'a TypeParamData)> + 'a {
 166         self.parent_generics
 167             .as_ref()
 168             .into_iter()
 169             .flat_map(|it| {
 170                 it.params
 171                     .types
 172                     .iter()
 173                     .map(move |(local_id, p)| (TypeParamId { parent: it.def, local_id }, p))
 174             })
 175             .chain(
 176                 self.params
 177                     .types
 178                     .iter()
 179                     .map(move |(local_id, p)| (TypeParamId { parent: self.def, local_id }, p)),
 180             )
 181     }
 182
 183     pub(crate) fn iter_parent<'a>(
 184         &'a self,
 185     ) -> impl Iterator<Item = (TypeParamId, &'a TypeParamData)> + 'a {
 186         self.parent_generics.as_ref().into_iter().flat_map(|it| {
 187             it.params
 188                 .types
 189                 .iter()
 190                 .map(move |(local_id, p)| (TypeParamId { parent: it.def, local_id }, p))
 191         })
 192     }
 193
 194     pub(crate) fn len(&self) -> usize {
 195         self.len_split().0
 196     }
 197
 198     /// (total, parents, child)
 199     pub(crate) fn len_split(&self) -> (usize, usize, usize) {
 200         let parent = self.parent_generics.as_ref().map_or(0, |p| p.len());
 201         let child = self.params.types.len();
 202         (parent + child, parent, child)
 203     }
 204
 205     /// (parent total, self param, type param list, impl trait)
 206     pub(crate) fn provenance_split(&self) -> (usize, usize, usize, usize) {
 207         let parent = self.parent_generics.as_ref().map_or(0, |p| p.len());
 208         let self_params = self
 209             .params
 210             .types
 211             .iter()
 212             .filter(|(_, p)| p.provenance == TypeParamProvenance::TraitSelf)
 213             .count();
 214         let list_params = self
 215             .params
 216             .types
 217             .iter()
 218             .filter(|(_, p)| p.provenance == TypeParamProvenance::TypeParamList)
 219             .count();
 220         let impl_trait_params = self
 221             .params
 222             .types
 223             .iter()
 224             .filter(|(_, p)| p.provenance == TypeParamProvenance::ArgumentImplTrait)
 225             .count();
 226         (parent, self_params, list_params, impl_trait_params)
 227     }
 228
 229     pub(crate) fn param_idx(&self, param: TypeParamId) -> Option<usize> {
 230         Some(self.find_param(param)?.0)
 231     }
 232
 233     fn find_param(&self, param: TypeParamId) -> Option<(usize, &TypeParamData)> {
 234         if param.parent == self.def {
 235             let (idx, (_local_id, data)) = self
 236                 .params
 237                 .types
 238                 .iter()
 239                 .enumerate()
 240                 .find(|(_, (idx, _))| *idx == param.local_id)
 241                 .unwrap();
 242             let (_total, parent_len, _child) = self.len_split();
 243             Some((parent_len + idx, data))
 244         } else {
 245             self.parent_generics.as_ref().and_then(|g| g.find_param(param))
 246         }
 247     }
 248 }
 249
 250 fn parent_generic_def(db: &dyn DefDatabase, def: GenericDefId) -> Option<GenericDefId> {
 251     let container = match def {
 252         GenericDefId::FunctionId(it) => it.lookup(db).container,
 253         GenericDefId::TypeAliasId(it) => it.lookup(db).container,
 254         GenericDefId::ConstId(it) => it.lookup(db).container,
 255         GenericDefId::EnumVariantId(it) => return Some(it.parent.into()),
 256         GenericDefId::AdtId(_) | GenericDefId::TraitId(_) | GenericDefId::ImplId(_) => return None,
 257     };
 258
 259     match container {
 260         AssocContainerId::ImplId(it) => Some(it.into()),
 261         AssocContainerId::TraitId(it) => Some(it.into()),
 262         AssocContainerId::ContainerId(_) => None,
 263     }
 264 }