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     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::Trait, ast::TypeParam>>,
  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         let generics = 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         generics
 155     }
 156
 157     fn new(db: &dyn DefDatabase, def: GenericDefId) -> (GenericParams, InFile<SourceMap>) {
 158         let mut generics = GenericParams::default();
 159         let mut sm = SourceMap::default();
 160
 161         // FIXME: add `: Sized` bound for everything except for `Self` in traits
 162         let file_id = match def {
 163             GenericDefId::FunctionId(it) => {
 164                 let src = it.lookup(db).source(db);
 165                 let lower_ctx = LowerCtx::new(db, src.file_id);
 166                 generics.fill(&lower_ctx, &mut sm, &src.value);
 167                 // lower `impl Trait` in arguments
 168                 let data = db.function_data(it);
 169                 for param in &data.params {
 170                     generics.fill_implicit_impl_trait_args(param);
 171                 }
 172                 src.file_id
 173             }
 174             GenericDefId::AdtId(AdtId::StructId(it)) => {
 175                 let src = it.lookup(db).source(db);
 176                 let lower_ctx = LowerCtx::new(db, src.file_id);
 177                 generics.fill(&lower_ctx, &mut sm, &src.value);
 178                 src.file_id
 179             }
 180             GenericDefId::AdtId(AdtId::UnionId(it)) => {
 181                 let src = it.lookup(db).source(db);
 182                 let lower_ctx = LowerCtx::new(db, src.file_id);
 183                 generics.fill(&lower_ctx, &mut sm, &src.value);
 184                 src.file_id
 185             }
 186             GenericDefId::AdtId(AdtId::EnumId(it)) => {
 187                 let src = it.lookup(db).source(db);
 188                 let lower_ctx = LowerCtx::new(db, src.file_id);
 189                 generics.fill(&lower_ctx, &mut sm, &src.value);
 190                 src.file_id
 191             }
 192             GenericDefId::TraitId(it) => {
 193                 let src = it.lookup(db).source(db);
 194                 let lower_ctx = LowerCtx::new(db, src.file_id);
 195
 196                 // traits get the Self type as an implicit first type parameter
 197                 let self_param_id = generics.types.alloc(TypeParamData {
 198                     name: Some(name![Self]),
 199                     default: None,
 200                     provenance: TypeParamProvenance::TraitSelf,
 201                 });
 202                 sm.type_params.insert(self_param_id, Either::Left(src.value.clone()));
 203                 // add super traits as bounds on Self
 204                 // i.e., trait Foo: Bar is equivalent to trait Foo where Self: Bar
 205                 let self_param = TypeRef::Path(name![Self].into());
 206                 generics.fill_bounds(&lower_ctx, &src.value, Either::Left(self_param));
 207
 208                 generics.fill(&lower_ctx, &mut sm, &src.value);
 209                 src.file_id
 210             }
 211             GenericDefId::TypeAliasId(it) => {
 212                 let src = it.lookup(db).source(db);
 213                 let lower_ctx = LowerCtx::new(db, src.file_id);
 214
 215                 generics.fill(&lower_ctx, &mut sm, &src.value);
 216                 src.file_id
 217             }
 218             // Note that we don't add `Self` here: in `impl`s, `Self` is not a
 219             // type-parameter, but rather is a type-alias for impl's target
 220             // type, so this is handled by the resolver.
 221             GenericDefId::ImplId(it) => {
 222                 let src = it.lookup(db).source(db);
 223                 let lower_ctx = LowerCtx::new(db, src.file_id);
 224
 225                 generics.fill(&lower_ctx, &mut sm, &src.value);
 226                 src.file_id
 227             }
 228             // We won't be using this ID anyway
 229             GenericDefId::EnumVariantId(_) | GenericDefId::ConstId(_) => FileId(!0).into(),
 230         };
 231
 232         generics.shrink_to_fit();
 233         (generics, InFile::new(file_id, sm))
 234     }
 235
 236     pub(crate) fn fill(
 237         &mut self,
 238         lower_ctx: &LowerCtx,
 239         sm: &mut SourceMap,
 240         node: &dyn GenericParamsOwner,
 241     ) {
 242         if let Some(params) = node.generic_param_list() {
 243             self.fill_params(lower_ctx, sm, params)
 244         }
 245         if let Some(where_clause) = node.where_clause() {
 246             self.fill_where_predicates(lower_ctx, where_clause);
 247         }
 248     }
 249
 250     pub(crate) fn fill_bounds(
 251         &mut self,
 252         lower_ctx: &LowerCtx,
 253         node: &dyn ast::TypeBoundsOwner,
 254         target: Either<TypeRef, LifetimeRef>,
 255     ) {
 256         for bound in
 257             node.type_bound_list().iter().flat_map(|type_bound_list| type_bound_list.bounds())
 258         {
 259             self.add_where_predicate_from_bound(lower_ctx, bound, None, target.clone());
 260         }
 261     }
 262
 263     fn fill_params(
 264         &mut self,
 265         lower_ctx: &LowerCtx,
 266         sm: &mut SourceMap,
 267         params: ast::GenericParamList,
 268     ) {
 269         for type_param in params.type_params() {
 270             let name = type_param.name().map_or_else(Name::missing, |it| it.as_name());
 271             // FIXME: Use `Path::from_src`
 272             let default =
 273                 type_param.default_type().map(|it| Interned::new(TypeRef::from_ast(lower_ctx, it)));
 274             let param = TypeParamData {
 275                 name: Some(name.clone()),
 276                 default,
 277                 provenance: TypeParamProvenance::TypeParamList,
 278             };
 279             let param_id = self.types.alloc(param);
 280             sm.type_params.insert(param_id, Either::Right(type_param.clone()));
 281
 282             let type_ref = TypeRef::Path(name.into());
 283             self.fill_bounds(&lower_ctx, &type_param, Either::Left(type_ref));
 284         }
 285         for lifetime_param in params.lifetime_params() {
 286             let name =
 287                 lifetime_param.lifetime().map_or_else(Name::missing, |lt| Name::new_lifetime(&lt));
 288             let param = LifetimeParamData { name: name.clone() };
 289             let param_id = self.lifetimes.alloc(param);
 290             sm.lifetime_params.insert(param_id, lifetime_param.clone());
 291             let lifetime_ref = LifetimeRef::new_name(name);
 292             self.fill_bounds(&lower_ctx, &lifetime_param, Either::Right(lifetime_ref));
 293         }
 294         for const_param in params.const_params() {
 295             let name = const_param.name().map_or_else(Name::missing, |it| it.as_name());
 296             let ty = const_param.ty().map_or(TypeRef::Error, |it| TypeRef::from_ast(lower_ctx, it));
 297             let param = ConstParamData { name, ty: Interned::new(ty) };
 298             let param_id = self.consts.alloc(param);
 299             sm.const_params.insert(param_id, const_param.clone());
 300         }
 301     }
 302
 303     fn fill_where_predicates(&mut self, lower_ctx: &LowerCtx, where_clause: ast::WhereClause) {
 304         for pred in where_clause.predicates() {
 305             let target = if let Some(type_ref) = pred.ty() {
 306                 Either::Left(TypeRef::from_ast(lower_ctx, type_ref))
 307             } else if let Some(lifetime) = pred.lifetime() {
 308                 Either::Right(LifetimeRef::new(&lifetime))
 309             } else {
 310                 continue;
 311             };
 312
 313             let lifetimes: Option<Box<_>> = pred.generic_param_list().map(|param_list| {
 314                 // Higher-Ranked Trait Bounds
 315                 param_list
 316                     .lifetime_params()
 317                     .map(|lifetime_param| {
 318                         lifetime_param
 319                             .lifetime()
 320                             .map_or_else(Name::missing, |lt| Name::new_lifetime(&lt))
 321                     })
 322                     .collect()
 323             });
 324             for bound in pred.type_bound_list().iter().flat_map(|l| l.bounds()) {
 325                 self.add_where_predicate_from_bound(
 326                     lower_ctx,
 327                     bound,
 328                     lifetimes.as_ref(),
 329                     target.clone(),
 330                 );
 331             }
 332         }
 333     }
 334
 335     fn add_where_predicate_from_bound(
 336         &mut self,
 337         lower_ctx: &LowerCtx,
 338         bound: ast::TypeBound,
 339         hrtb_lifetimes: Option<&Box<[Name]>>,
 340         target: Either<TypeRef, LifetimeRef>,
 341     ) {
 342         if bound.question_mark_token().is_some() {
 343             // FIXME: remove this bound
 344             return;
 345         }
 346         let bound = TypeBound::from_ast(lower_ctx, bound);
 347         let predicate = match (target, bound) {
 348             (Either::Left(type_ref), bound) => match hrtb_lifetimes {
 349                 Some(hrtb_lifetimes) => WherePredicate::ForLifetime {
 350                     lifetimes: hrtb_lifetimes.clone(),
 351                     target: WherePredicateTypeTarget::TypeRef(Interned::new(type_ref)),
 352                     bound: Interned::new(bound),
 353                 },
 354                 None => WherePredicate::TypeBound {
 355                     target: WherePredicateTypeTarget::TypeRef(Interned::new(type_ref)),
 356                     bound: Interned::new(bound),
 357                 },
 358             },
 359             (Either::Right(lifetime), TypeBound::Lifetime(bound)) => {
 360                 WherePredicate::Lifetime { target: lifetime, bound }
 361             }
 362             _ => return,
 363         };
 364         self.where_predicates.push(predicate);
 365     }
 366
 367     pub(crate) fn fill_implicit_impl_trait_args(&mut self, type_ref: &TypeRef) {
 368         type_ref.walk(&mut |type_ref| {
 369             if let TypeRef::ImplTrait(bounds) = type_ref {
 370                 let param = TypeParamData {
 371                     name: None,
 372                     default: None,
 373                     provenance: TypeParamProvenance::ArgumentImplTrait,
 374                 };
 375                 let param_id = self.types.alloc(param);
 376                 for bound in bounds {
 377                     self.where_predicates.push(WherePredicate::TypeBound {
 378                         target: WherePredicateTypeTarget::TypeParam(param_id),
 379                         bound: bound.clone(),
 380                     });
 381                 }
 382             }
 383         });
 384     }
 385
 386     pub(crate) fn shrink_to_fit(&mut self) {
 387         let Self { consts, lifetimes, types, where_predicates } = self;
 388         consts.shrink_to_fit();
 389         lifetimes.shrink_to_fit();
 390         types.shrink_to_fit();
 391         where_predicates.shrink_to_fit();
 392     }
 393
 394     pub fn find_type_by_name(&self, name: &Name) -> Option<LocalTypeParamId> {
 395         self.types
 396             .iter()
 397             .find_map(|(id, p)| if p.name.as_ref() == Some(name) { Some(id) } else { None })
 398     }
 399
 400     pub fn find_const_by_name(&self, name: &Name) -> Option<LocalConstParamId> {
 401         self.consts.iter().find_map(|(id, p)| if p.name == *name { Some(id) } else { None })
 402     }
 403
 404     pub fn find_trait_self_param(&self) -> Option<LocalTypeParamId> {
 405         self.types.iter().find_map(|(id, p)| {
 406             if p.provenance == TypeParamProvenance::TraitSelf {
 407                 Some(id)
 408             } else {
 409                 None
 410             }
 411         })
 412     }
 413 }
 414
 415 impl HasChildSource<LocalTypeParamId> for GenericDefId {
 416     type Value = Either<ast::Trait, ast::TypeParam>;
 417     fn child_source(
 418         &self,
 419         db: &dyn DefDatabase,
 420     ) -> InFile<ArenaMap<LocalTypeParamId, Self::Value>> {
 421         GenericParams::new(db, *self).1.map(|source_maps| source_maps.type_params)
 422     }
 423 }
 424
 425 impl HasChildSource<LocalLifetimeParamId> for GenericDefId {
 426     type Value = ast::LifetimeParam;
 427     fn child_source(
 428         &self,
 429         db: &dyn DefDatabase,
 430     ) -> InFile<ArenaMap<LocalLifetimeParamId, Self::Value>> {
 431         GenericParams::new(db, *self).1.map(|source_maps| source_maps.lifetime_params)
 432     }
 433 }
 434
 435 impl HasChildSource<LocalConstParamId> for GenericDefId {
 436     type Value = ast::ConstParam;
 437     fn child_source(
 438         &self,
 439         db: &dyn DefDatabase,
 440     ) -> InFile<ArenaMap<LocalConstParamId, Self::Value>> {
 441         GenericParams::new(db, *self).1.map(|source_maps| source_maps.const_params)
 442     }
 443 }
 444
 445 impl ChildBySource for GenericDefId {
 446     fn child_by_source_to(&self, db: &dyn DefDatabase, res: &mut DynMap) {
 447         let (_, sm) = GenericParams::new(db, *self);
 448
 449         let sm = sm.as_ref();
 450         for (local_id, src) in sm.value.type_params.iter() {
 451             let id = TypeParamId { parent: *self, local_id };
 452             if let Either::Right(type_param) = src {
 453                 res[keys::TYPE_PARAM].insert(sm.with_value(type_param.clone()), id)
 454             }
 455         }
 456         for (local_id, src) in sm.value.lifetime_params.iter() {
 457             let id = LifetimeParamId { parent: *self, local_id };
 458             res[keys::LIFETIME_PARAM].insert(sm.with_value(src.clone()), id);
 459         }
 460         for (local_id, src) in sm.value.const_params.iter() {
 461             let id = ConstParamId { parent: *self, local_id };
 462             res[keys::CONST_PARAM].insert(sm.with_value(src.clone()), id);
 463         }
 464     }
 465 }