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::TypeParam, ast::Trait>>,
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");
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())
156 fn new(db: &dyn DefDatabase, def: GenericDefId) -> (GenericParams, InFile<SourceMap>) {
157 let mut generics = GenericParams::default();
158 let mut sm = SourceMap::default();
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);
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);
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);
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);
191 GenericDefId::TraitId(it) => {
192 let src = it.lookup(db).source(db);
193 let lower_ctx = LowerCtx::new(db, src.file_id);
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]),
199 provenance: TypeParamProvenance::TraitSelf,
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));
207 generics.fill(&lower_ctx, &mut sm, &src.value);
210 GenericDefId::TypeAliasId(it) => {
211 let src = it.lookup(db).source(db);
212 let lower_ctx = LowerCtx::new(db, src.file_id);
214 generics.fill(&lower_ctx, &mut sm, &src.value);
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);
224 generics.fill(&lower_ctx, &mut sm, &src.value);
227 // We won't be using this ID anyway
228 GenericDefId::EnumVariantId(_) | GenericDefId::ConstId(_) => FileId(!0).into(),
231 generics.shrink_to_fit();
232 (generics, InFile::new(file_id, sm))
237 lower_ctx: &LowerCtx,
239 node: &dyn GenericParamsOwner,
241 if let Some(params) = node.generic_param_list() {
242 self.fill_params(lower_ctx, sm, params)
244 if let Some(where_clause) = node.where_clause() {
245 self.fill_where_predicates(lower_ctx, where_clause);
249 pub(crate) fn fill_bounds(
251 lower_ctx: &LowerCtx,
252 node: &dyn ast::TypeBoundsOwner,
253 target: Either<TypeRef, LifetimeRef>,
256 node.type_bound_list().iter().flat_map(|type_bound_list| type_bound_list.bounds())
258 self.add_where_predicate_from_bound(lower_ctx, bound, None, target.clone());
264 lower_ctx: &LowerCtx,
266 params: ast::GenericParamList,
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`
272 type_param.default_type().map(|it| Interned::new(TypeRef::from_ast(lower_ctx, it)));
273 let param = TypeParamData {
274 name: Some(name.clone()),
276 provenance: TypeParamProvenance::TypeParamList,
278 let param_id = self.types.alloc(param);
279 sm.type_params.insert(param_id, Either::Left(type_param.clone()));
281 let type_ref = TypeRef::Path(name.into());
282 self.fill_bounds(lower_ctx, &type_param, Either::Left(type_ref));
284 for lifetime_param in params.lifetime_params() {
286 lifetime_param.lifetime().map_or_else(Name::missing, |lt| Name::new_lifetime(<));
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));
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());
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))
312 let lifetimes: Option<Box<_>> = pred.generic_param_list().map(|param_list| {
313 // Higher-Ranked Trait Bounds
316 .map(|lifetime_param| {
319 .map_or_else(Name::missing, |lt| Name::new_lifetime(<))
323 for bound in pred.type_bound_list().iter().flat_map(|l| l.bounds()) {
324 self.add_where_predicate_from_bound(
334 fn add_where_predicate_from_bound(
336 lower_ctx: &LowerCtx,
337 bound: ast::TypeBound,
338 hrtb_lifetimes: Option<&Box<[Name]>>,
339 target: Either<TypeRef, LifetimeRef>,
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),
349 None => WherePredicate::TypeBound {
350 target: WherePredicateTypeTarget::TypeRef(Interned::new(type_ref)),
351 bound: Interned::new(bound),
354 (Either::Right(lifetime), TypeBound::Lifetime(bound)) => {
355 WherePredicate::Lifetime { target: lifetime, bound }
359 self.where_predicates.push(predicate);
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 {
368 provenance: TypeParamProvenance::ArgumentImplTrait,
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(),
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();
389 pub fn find_type_by_name(&self, name: &Name) -> Option<LocalTypeParamId> {
392 .find_map(|(id, p)| if p.name.as_ref() == Some(name) { Some(id) } else { None })
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 })
399 pub fn find_trait_self_param(&self) -> Option<LocalTypeParamId> {
400 self.types.iter().find_map(|(id, p)| {
401 if p.provenance == TypeParamProvenance::TraitSelf {
410 impl HasChildSource<LocalTypeParamId> for GenericDefId {
411 type Value = Either<ast::TypeParam, ast::Trait>;
414 db: &dyn DefDatabase,
415 ) -> InFile<ArenaMap<LocalTypeParamId, Self::Value>> {
416 GenericParams::new(db, *self).1.map(|source_maps| source_maps.type_params)
420 impl HasChildSource<LocalLifetimeParamId> for GenericDefId {
421 type Value = ast::LifetimeParam;
424 db: &dyn DefDatabase,
425 ) -> InFile<ArenaMap<LocalLifetimeParamId, Self::Value>> {
426 GenericParams::new(db, *self).1.map(|source_maps| source_maps.lifetime_params)
430 impl HasChildSource<LocalConstParamId> for GenericDefId {
431 type Value = ast::ConstParam;
434 db: &dyn DefDatabase,
435 ) -> InFile<ArenaMap<LocalConstParamId, Self::Value>> {
436 GenericParams::new(db, *self).1.map(|source_maps| source_maps.const_params)
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);
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)
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);
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);