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