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
9 name::{name, AsName, Name},
12 use la_arena::{Arena, ArenaMap};
13 use syntax::ast::{self, GenericParamsOwner, NameOwner, TypeBoundsOwner};
17 child_by_source::ChildBySource,
22 src::{HasChildSource, HasSource},
23 type_ref::{LifetimeRef, TypeBound, TypeRef},
24 AdtId, ConstParamId, GenericDefId, LifetimeParamId, LocalConstParamId, LocalLifetimeParamId,
25 LocalTypeParamId, Lookup, TypeParamId,
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,
36 /// Data about a generic lifetime parameter (to a function, struct, impl, ...).
37 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
38 pub struct LifetimeParamData {
42 /// Data about a generic const parameter (to a function, struct, impl, ...).
43 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
44 pub struct ConstParamData {
46 pub ty: Interned<TypeRef>,
49 #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
50 pub enum TypeParamProvenance {
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>,
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 {
72 target: WherePredicateTypeTarget,
73 bound: Interned<TypeBound>,
80 lifetimes: Box<[Name]>,
81 target: WherePredicateTypeTarget,
82 bound: Interned<TypeBound>,
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),
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>,
101 pub(crate) fn generic_params_query(
102 db: &dyn DefDatabase,
104 ) -> Interned<GenericParams> {
105 let _p = profile::span("generic_params_query");
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()
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()
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()
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()
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()
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()
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()
150 GenericDefId::EnumVariantId(_) | GenericDefId::ConstId(_) => {
151 Interned::new(GenericParams::default())
157 fn new(db: &dyn DefDatabase, def: GenericDefId) -> (GenericParams, InFile<SourceMap>) {
158 let mut generics = GenericParams::default();
159 let mut sm = SourceMap::default();
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);
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);
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);
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);
192 GenericDefId::TraitId(it) => {
193 let src = it.lookup(db).source(db);
194 let lower_ctx = LowerCtx::new(db, src.file_id);
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]),
200 provenance: TypeParamProvenance::TraitSelf,
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));
208 generics.fill(&lower_ctx, &mut sm, &src.value);
211 GenericDefId::TypeAliasId(it) => {
212 let src = it.lookup(db).source(db);
213 let lower_ctx = LowerCtx::new(db, src.file_id);
215 generics.fill(&lower_ctx, &mut sm, &src.value);
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);
225 generics.fill(&lower_ctx, &mut sm, &src.value);
228 // We won't be using this ID anyway
229 GenericDefId::EnumVariantId(_) | GenericDefId::ConstId(_) => FileId(!0).into(),
232 generics.shrink_to_fit();
233 (generics, InFile::new(file_id, sm))
238 lower_ctx: &LowerCtx,
240 node: &dyn GenericParamsOwner,
242 if let Some(params) = node.generic_param_list() {
243 self.fill_params(lower_ctx, sm, params)
245 if let Some(where_clause) = node.where_clause() {
246 self.fill_where_predicates(lower_ctx, where_clause);
250 pub(crate) fn fill_bounds(
252 lower_ctx: &LowerCtx,
253 node: &dyn ast::TypeBoundsOwner,
254 target: Either<TypeRef, LifetimeRef>,
257 node.type_bound_list().iter().flat_map(|type_bound_list| type_bound_list.bounds())
259 self.add_where_predicate_from_bound(lower_ctx, bound, None, target.clone());
265 lower_ctx: &LowerCtx,
267 params: ast::GenericParamList,
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`
273 type_param.default_type().map(|it| Interned::new(TypeRef::from_ast(lower_ctx, it)));
274 let param = TypeParamData {
275 name: Some(name.clone()),
277 provenance: TypeParamProvenance::TypeParamList,
279 let param_id = self.types.alloc(param);
280 sm.type_params.insert(param_id, Either::Right(type_param.clone()));
282 let type_ref = TypeRef::Path(name.into());
283 self.fill_bounds(&lower_ctx, &type_param, Either::Left(type_ref));
285 for lifetime_param in params.lifetime_params() {
287 lifetime_param.lifetime().map_or_else(Name::missing, |lt| Name::new_lifetime(<));
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));
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());
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))
313 let lifetimes: Option<Box<_>> = pred.generic_param_list().map(|param_list| {
314 // Higher-Ranked Trait Bounds
317 .map(|lifetime_param| {
320 .map_or_else(Name::missing, |lt| Name::new_lifetime(<))
324 for bound in pred.type_bound_list().iter().flat_map(|l| l.bounds()) {
325 self.add_where_predicate_from_bound(
335 fn add_where_predicate_from_bound(
337 lower_ctx: &LowerCtx,
338 bound: ast::TypeBound,
339 hrtb_lifetimes: Option<&Box<[Name]>>,
340 target: Either<TypeRef, LifetimeRef>,
342 if bound.question_mark_token().is_some() {
343 // FIXME: remove this bound
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),
354 None => WherePredicate::TypeBound {
355 target: WherePredicateTypeTarget::TypeRef(Interned::new(type_ref)),
356 bound: Interned::new(bound),
359 (Either::Right(lifetime), TypeBound::Lifetime(bound)) => {
360 WherePredicate::Lifetime { target: lifetime, bound }
364 self.where_predicates.push(predicate);
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 {
373 provenance: TypeParamProvenance::ArgumentImplTrait,
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(),
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();
394 pub fn find_type_by_name(&self, name: &Name) -> Option<LocalTypeParamId> {
397 .find_map(|(id, p)| if p.name.as_ref() == Some(name) { Some(id) } else { None })
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 })
404 pub fn find_trait_self_param(&self) -> Option<LocalTypeParamId> {
405 self.types.iter().find_map(|(id, p)| {
406 if p.provenance == TypeParamProvenance::TraitSelf {
415 impl HasChildSource<LocalTypeParamId> for GenericDefId {
416 type Value = Either<ast::Trait, ast::TypeParam>;
419 db: &dyn DefDatabase,
420 ) -> InFile<ArenaMap<LocalTypeParamId, Self::Value>> {
421 GenericParams::new(db, *self).1.map(|source_maps| source_maps.type_params)
425 impl HasChildSource<LocalLifetimeParamId> for GenericDefId {
426 type Value = ast::LifetimeParam;
429 db: &dyn DefDatabase,
430 ) -> InFile<ArenaMap<LocalLifetimeParamId, Self::Value>> {
431 GenericParams::new(db, *self).1.map(|source_maps| source_maps.lifetime_params)
435 impl HasChildSource<LocalConstParamId> for GenericDefId {
436 type Value = ast::ConstParam;
439 db: &dyn DefDatabase,
440 ) -> InFile<ArenaMap<LocalConstParamId, Self::Value>> {
441 GenericParams::new(db, *self).1.map(|source_maps| source_maps.const_params)
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);
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)
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);
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);