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