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