crates/hir_def/src/generics.rs

   1 //! Many kinds of items or constructs can have generic parameters: functions,
   2 //! structs, impls, traits, etc. This module provides a common HIR for these
   3 //! generic parameters. See also the `Generics` type and the `generics_of` query
   4 //! in rustc.
   5 use std::sync::Arc;
   6
   7 use arena::{map::ArenaMap, Arena};
   8 use base_db::FileId;
   9 use either::Either;
  10 use hir_expand::{
  11     name::{name, AsName, Name},
  12     InFile,
  13 };
  14 use syntax::ast::{self, GenericParamsOwner, NameOwner, TypeBoundsOwner};
  15
  16 use crate::{
  17     body::LowerCtx,
  18     child_by_source::ChildBySource,
  19     db::DefDatabase,
  20     dyn_map::DynMap,
  21     keys,
  22     src::{HasChildSource, HasSource},
  23     type_ref::{LifetimeRef, TypeBound, TypeRef},
  24     AdtId, GenericDefId, LifetimeParamId, LocalLifetimeParamId, LocalTypeParamId, Lookup,
  25     TypeParamId,
  26 };
  27
  28 /// Data about a generic parameter (to a function, struct, impl, ...).
  29 #[derive(Clone, PartialEq, Eq, Debug)]
  30 pub struct TypeParamData {
  31     pub name: Option<Name>,
  32     pub default: Option<TypeRef>,
  33     pub provenance: TypeParamProvenance,
  34 }
  35
  36 /// Data about a generic parameter (to a function, struct, impl, ...).
  37 #[derive(Clone, PartialEq, Eq, Debug)]
  38 pub struct LifetimeParamData {
  39     pub name: Name,
  40 }
  41
  42 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
  43 pub enum TypeParamProvenance {
  44     TypeParamList,
  45     TraitSelf,
  46     ArgumentImplTrait,
  47 }
  48
  49 /// Data about the generic parameters of a function, struct, impl, etc.
  50 #[derive(Clone, PartialEq, Eq, Debug, Default)]
  51 pub struct GenericParams {
  52     pub types: Arena<TypeParamData>,
  53     pub lifetimes: Arena<LifetimeParamData>,
  54     pub where_predicates: Vec<WherePredicate>,
  55 }
  56
  57 /// A single predicate from a where clause, i.e. `where Type: Trait`. Combined
  58 /// where clauses like `where T: Foo + Bar` are turned into multiple of these.
  59 /// It might still result in multiple actual predicates though, because of
  60 /// associated type bindings like `Iterator<Item = u32>`.
  61 #[derive(Clone, PartialEq, Eq, Debug)]
  62 pub enum WherePredicate {
  63     TypeBound { target: WherePredicateTypeTarget, bound: TypeBound },
  64     Lifetime { target: LifetimeRef, bound: LifetimeRef },
  65     ForLifetime { lifetimes: Box<[Name]>, target: WherePredicateTypeTarget, bound: TypeBound },
  66 }
  67
  68 #[derive(Clone, PartialEq, Eq, Debug)]
  69 pub enum WherePredicateTypeTarget {
  70     TypeRef(TypeRef),
  71     /// For desugared where predicates that can directly refer to a type param.
  72     TypeParam(LocalTypeParamId),
  73 }
  74
  75 #[derive(Default)]
  76 pub(crate) struct SourceMap {
  77     pub(crate) type_params: ArenaMap<LocalTypeParamId, Either<ast::Trait, ast::TypeParam>>,
  78     lifetime_params: ArenaMap<LocalLifetimeParamId, ast::LifetimeParam>,
  79 }
  80
  81 impl GenericParams {
  82     pub(crate) fn generic_params_query(
  83         db: &dyn DefDatabase,
  84         def: GenericDefId,
  85     ) -> Arc<GenericParams> {
  86         let _p = profile::span("generic_params_query");
  87
  88         let generics = match def {
  89             GenericDefId::FunctionId(id) => {
  90                 let id = id.lookup(db).id;
  91                 let tree = db.item_tree(id.file_id);
  92                 let item = &tree[id.value];
  93                 tree[item.generic_params].clone()
  94             }
  95             GenericDefId::AdtId(AdtId::StructId(id)) => {
  96                 let id = id.lookup(db).id;
  97                 let tree = db.item_tree(id.file_id);
  98                 let item = &tree[id.value];
  99                 tree[item.generic_params].clone()
 100             }
 101             GenericDefId::AdtId(AdtId::EnumId(id)) => {
 102                 let id = id.lookup(db).id;
 103                 let tree = db.item_tree(id.file_id);
 104                 let item = &tree[id.value];
 105                 tree[item.generic_params].clone()
 106             }
 107             GenericDefId::AdtId(AdtId::UnionId(id)) => {
 108                 let id = id.lookup(db).id;
 109                 let tree = db.item_tree(id.file_id);
 110                 let item = &tree[id.value];
 111                 tree[item.generic_params].clone()
 112             }
 113             GenericDefId::TraitId(id) => {
 114                 let id = id.lookup(db).id;
 115                 let tree = db.item_tree(id.file_id);
 116                 let item = &tree[id.value];
 117                 tree[item.generic_params].clone()
 118             }
 119             GenericDefId::TypeAliasId(id) => {
 120                 let id = id.lookup(db).id;
 121                 let tree = db.item_tree(id.file_id);
 122                 let item = &tree[id.value];
 123                 tree[item.generic_params].clone()
 124             }
 125             GenericDefId::ImplId(id) => {
 126                 let id = id.lookup(db).id;
 127                 let tree = db.item_tree(id.file_id);
 128                 let item = &tree[id.value];
 129                 tree[item.generic_params].clone()
 130             }
 131             GenericDefId::EnumVariantId(_) | GenericDefId::ConstId(_) => GenericParams::default(),
 132         };
 133         Arc::new(generics)
 134     }
 135
 136     fn new(db: &dyn DefDatabase, def: GenericDefId) -> (GenericParams, InFile<SourceMap>) {
 137         let mut generics = GenericParams::default();
 138         let mut sm = SourceMap::default();
 139
 140         // FIXME: add `: Sized` bound for everything except for `Self` in traits
 141         let file_id = match def {
 142             GenericDefId::FunctionId(it) => {
 143                 let src = it.lookup(db).source(db);
 144                 let lower_ctx = LowerCtx::new(db, src.file_id);
 145                 generics.fill(&lower_ctx, &mut sm, &src.value);
 146                 // lower `impl Trait` in arguments
 147                 let data = db.function_data(it);
 148                 for param in &data.params {
 149                     generics.fill_implicit_impl_trait_args(param);
 150                 }
 151                 src.file_id
 152             }
 153             GenericDefId::AdtId(AdtId::StructId(it)) => {
 154                 let src = it.lookup(db).source(db);
 155                 let lower_ctx = LowerCtx::new(db, src.file_id);
 156                 generics.fill(&lower_ctx, &mut sm, &src.value);
 157                 src.file_id
 158             }
 159             GenericDefId::AdtId(AdtId::UnionId(it)) => {
 160                 let src = it.lookup(db).source(db);
 161                 let lower_ctx = LowerCtx::new(db, src.file_id);
 162                 generics.fill(&lower_ctx, &mut sm, &src.value);
 163                 src.file_id
 164             }
 165             GenericDefId::AdtId(AdtId::EnumId(it)) => {
 166                 let src = it.lookup(db).source(db);
 167                 let lower_ctx = LowerCtx::new(db, src.file_id);
 168                 generics.fill(&lower_ctx, &mut sm, &src.value);
 169                 src.file_id
 170             }
 171             GenericDefId::TraitId(it) => {
 172                 let src = it.lookup(db).source(db);
 173                 let lower_ctx = LowerCtx::new(db, src.file_id);
 174
 175                 // traits get the Self type as an implicit first type parameter
 176                 let self_param_id = generics.types.alloc(TypeParamData {
 177                     name: Some(name![Self]),
 178                     default: None,
 179                     provenance: TypeParamProvenance::TraitSelf,
 180                 });
 181                 sm.type_params.insert(self_param_id, Either::Left(src.value.clone()));
 182                 // add super traits as bounds on Self
 183                 // i.e., trait Foo: Bar is equivalent to trait Foo where Self: Bar
 184                 let self_param = TypeRef::Path(name![Self].into());
 185                 generics.fill_bounds(&lower_ctx, &src.value, Either::Left(self_param));
 186
 187                 generics.fill(&lower_ctx, &mut sm, &src.value);
 188                 src.file_id
 189             }
 190             GenericDefId::TypeAliasId(it) => {
 191                 let src = it.lookup(db).source(db);
 192                 let lower_ctx = LowerCtx::new(db, src.file_id);
 193
 194                 generics.fill(&lower_ctx, &mut sm, &src.value);
 195                 src.file_id
 196             }
 197             // Note that we don't add `Self` here: in `impl`s, `Self` is not a
 198             // type-parameter, but rather is a type-alias for impl's target
 199             // type, so this is handled by the resolver.
 200             GenericDefId::ImplId(it) => {
 201                 let src = it.lookup(db).source(db);
 202                 let lower_ctx = LowerCtx::new(db, src.file_id);
 203
 204                 generics.fill(&lower_ctx, &mut sm, &src.value);
 205                 src.file_id
 206             }
 207             // We won't be using this ID anyway
 208             GenericDefId::EnumVariantId(_) | GenericDefId::ConstId(_) => FileId(!0).into(),
 209         };
 210
 211         (generics, InFile::new(file_id, sm))
 212     }
 213
 214     pub(crate) fn fill(
 215         &mut self,
 216         lower_ctx: &LowerCtx,
 217         sm: &mut SourceMap,
 218         node: &dyn GenericParamsOwner,
 219     ) {
 220         if let Some(params) = node.generic_param_list() {
 221             self.fill_params(lower_ctx, sm, params)
 222         }
 223         if let Some(where_clause) = node.where_clause() {
 224             self.fill_where_predicates(lower_ctx, where_clause);
 225         }
 226     }
 227
 228     pub(crate) fn fill_bounds(
 229         &mut self,
 230         lower_ctx: &LowerCtx,
 231         node: &dyn ast::TypeBoundsOwner,
 232         target: Either<TypeRef, LifetimeRef>,
 233     ) {
 234         for bound in
 235             node.type_bound_list().iter().flat_map(|type_bound_list| type_bound_list.bounds())
 236         {
 237             self.add_where_predicate_from_bound(lower_ctx, bound, None, target.clone());
 238         }
 239     }
 240
 241     fn fill_params(
 242         &mut self,
 243         lower_ctx: &LowerCtx,
 244         sm: &mut SourceMap,
 245         params: ast::GenericParamList,
 246     ) {
 247         for type_param in params.type_params() {
 248             let name = type_param.name().map_or_else(Name::missing, |it| it.as_name());
 249             // FIXME: Use `Path::from_src`
 250             let default = type_param.default_type().map(|it| TypeRef::from_ast(lower_ctx, it));
 251             let param = TypeParamData {
 252                 name: Some(name.clone()),
 253                 default,
 254                 provenance: TypeParamProvenance::TypeParamList,
 255             };
 256             let param_id = self.types.alloc(param);
 257             sm.type_params.insert(param_id, Either::Right(type_param.clone()));
 258
 259             let type_ref = TypeRef::Path(name.into());
 260             self.fill_bounds(&lower_ctx, &type_param, Either::Left(type_ref));
 261         }
 262         for lifetime_param in params.lifetime_params() {
 263             let name =
 264                 lifetime_param.lifetime().map_or_else(Name::missing, |lt| Name::new_lifetime(&lt));
 265             let param = LifetimeParamData { name: name.clone() };
 266             let param_id = self.lifetimes.alloc(param);
 267             sm.lifetime_params.insert(param_id, lifetime_param.clone());
 268             let lifetime_ref = LifetimeRef::new_name(name);
 269             self.fill_bounds(&lower_ctx, &lifetime_param, Either::Right(lifetime_ref));
 270         }
 271     }
 272
 273     fn fill_where_predicates(&mut self, lower_ctx: &LowerCtx, where_clause: ast::WhereClause) {
 274         for pred in where_clause.predicates() {
 275             let target = if let Some(type_ref) = pred.ty() {
 276                 Either::Left(TypeRef::from_ast(lower_ctx, type_ref))
 277             } else if let Some(lifetime) = pred.lifetime() {
 278                 Either::Right(LifetimeRef::new(&lifetime))
 279             } else {
 280                 continue;
 281             };
 282
 283             let lifetimes: Option<Box<_>> = pred.generic_param_list().map(|param_list| {
 284                 // Higher-Ranked Trait Bounds
 285                 param_list
 286                     .lifetime_params()
 287                     .map(|lifetime_param| {
 288                         lifetime_param
 289                             .lifetime()
 290                             .map_or_else(Name::missing, |lt| Name::new_lifetime(&lt))
 291                     })
 292                     .collect()
 293             });
 294             for bound in pred.type_bound_list().iter().flat_map(|l| l.bounds()) {
 295                 self.add_where_predicate_from_bound(
 296                     lower_ctx,
 297                     bound,
 298                     lifetimes.as_ref(),
 299                     target.clone(),
 300                 );
 301             }
 302         }
 303     }
 304
 305     fn add_where_predicate_from_bound(
 306         &mut self,
 307         lower_ctx: &LowerCtx,
 308         bound: ast::TypeBound,
 309         hrtb_lifetimes: Option<&Box<[Name]>>,
 310         target: Either<TypeRef, LifetimeRef>,
 311     ) {
 312         if bound.question_mark_token().is_some() {
 313             // FIXME: remove this bound
 314             return;
 315         }
 316         let bound = TypeBound::from_ast(lower_ctx, bound);
 317         let predicate = match (target, bound) {
 318             (Either::Left(type_ref), bound) => match hrtb_lifetimes {
 319                 Some(hrtb_lifetimes) => WherePredicate::ForLifetime {
 320                     lifetimes: hrtb_lifetimes.clone(),
 321                     target: WherePredicateTypeTarget::TypeRef(type_ref),
 322                     bound,
 323                 },
 324                 None => WherePredicate::TypeBound {
 325                     target: WherePredicateTypeTarget::TypeRef(type_ref),
 326                     bound,
 327                 },
 328             },
 329             (Either::Right(lifetime), TypeBound::Lifetime(bound)) => {
 330                 WherePredicate::Lifetime { target: lifetime, bound }
 331             }
 332             _ => return,
 333         };
 334         self.where_predicates.push(predicate);
 335     }
 336
 337     pub(crate) fn fill_implicit_impl_trait_args(&mut self, type_ref: &TypeRef) {
 338         type_ref.walk(&mut |type_ref| {
 339             if let TypeRef::ImplTrait(bounds) = type_ref {
 340                 let param = TypeParamData {
 341                     name: None,
 342                     default: None,
 343                     provenance: TypeParamProvenance::ArgumentImplTrait,
 344                 };
 345                 let param_id = self.types.alloc(param);
 346                 for bound in bounds {
 347                     self.where_predicates.push(WherePredicate::TypeBound {
 348                         target: WherePredicateTypeTarget::TypeParam(param_id),
 349                         bound: bound.clone(),
 350                     });
 351                 }
 352             }
 353         });
 354     }
 355
 356     pub fn find_by_name(&self, name: &Name) -> Option<LocalTypeParamId> {
 357         self.types
 358             .iter()
 359             .find_map(|(id, p)| if p.name.as_ref() == Some(name) { Some(id) } else { None })
 360     }
 361
 362     pub fn find_trait_self_param(&self) -> Option<LocalTypeParamId> {
 363         self.types.iter().find_map(|(id, p)| {
 364             if p.provenance == TypeParamProvenance::TraitSelf {
 365                 Some(id)
 366             } else {
 367                 None
 368             }
 369         })
 370     }
 371 }
 372
 373 impl HasChildSource<LocalTypeParamId> for GenericDefId {
 374     type Value = Either<ast::Trait, ast::TypeParam>;
 375     fn child_source(
 376         &self,
 377         db: &dyn DefDatabase,
 378     ) -> InFile<ArenaMap<LocalTypeParamId, Self::Value>> {
 379         GenericParams::new(db, *self).1.map(|source_maps| source_maps.type_params)
 380     }
 381 }
 382
 383 impl HasChildSource<LocalLifetimeParamId> for GenericDefId {
 384     type Value = ast::LifetimeParam;
 385     fn child_source(
 386         &self,
 387         db: &dyn DefDatabase,
 388     ) -> InFile<ArenaMap<LocalLifetimeParamId, Self::Value>> {
 389         GenericParams::new(db, *self).1.map(|source_maps| source_maps.lifetime_params)
 390     }
 391 }
 392
 393 impl ChildBySource for GenericDefId {
 394     fn child_by_source(&self, db: &dyn DefDatabase) -> DynMap {
 395         let mut res = DynMap::default();
 396         let (_, sm) = GenericParams::new(db, *self);
 397
 398         let sm = sm.as_ref();
 399         for (local_id, src) in sm.value.type_params.iter() {
 400             let id = TypeParamId { parent: *self, local_id };
 401             if let Either::Right(type_param) = src {
 402                 res[keys::TYPE_PARAM].insert(sm.with_value(type_param.clone()), id)
 403             }
 404         }
 405         for (local_id, src) in sm.value.lifetime_params.iter() {
 406             let id = LifetimeParamId { parent: *self, local_id };
 407             res[keys::LIFETIME_PARAM].insert(sm.with_value(src.clone()), id);
 408         }
 409         res
 410     }
 411 }