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