Merge #6818

6818: Add Lifetimes to the HIR r=matklad a=Veykril

This doesn't handle resolve yet as I don't know yet how that will be used. I'll get to that once I start moving the lifetime reference PR to the hir.

This also adds a new `hir` name type for lifetimes and labels, `hir::LifetimeName`.

Co-authored-by: Lukas Wirth <[email protected]>

7 files changed, 118 insertions, 46 deletions

diff --git a/crates/hir_def/src/generics.rs b/crates/hir_def/src/generics.rs
index 835fe3fbd..5189c7e9f 100644
--- a/crates/hir_def/src/generics.rs
+++ b/crates/hir_def/src/generics.rs
@@ -21,7 +21,7 @@ use crate::{
     keys,
     src::HasChildSource,
     src::HasSource,
-    type_ref::{TypeBound, TypeRef},
+    type_ref::{LifetimeRef, TypeBound, TypeRef},
     AdtId, GenericDefId, LocalTypeParamId, Lookup, TypeParamId,
 };
 
@@ -33,6 +33,12 @@ pub struct TypeParamData {
     pub provenance: TypeParamProvenance,
 }
 
+/// Data about a generic parameter (to a function, struct, impl, ...).
+#[derive(Clone, PartialEq, Eq, Debug)]
+pub struct LifetimeParamData {
+    pub name: Name,
+}
+
 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 pub enum TypeParamProvenance {
     TypeParamList,
@@ -44,7 +50,7 @@ pub enum TypeParamProvenance {
 #[derive(Clone, PartialEq, Eq, Debug, Default)]
 pub struct GenericParams {
     pub types: Arena<TypeParamData>,
-    // lifetimes: Arena<LocalLifetimeParamId, LifetimeParamData>,
+    pub lifetimes: Arena<LifetimeParamData>,
     pub where_predicates: Vec<WherePredicate>,
 }
 
@@ -53,16 +59,17 @@ pub struct GenericParams {
 /// It might still result in multiple actual predicates though, because of
 /// associated type bindings like `Iterator<Item = u32>`.
 #[derive(Clone, PartialEq, Eq, Debug)]
-pub struct WherePredicate {
-    pub target: WherePredicateTarget,
-    pub bound: TypeBound,
+pub enum WherePredicate {
+    TypeBound { target: WherePredicateTypeTarget, bound: TypeBound },
+    Lifetime { target: LifetimeRef, bound: LifetimeRef },
 }
 
 #[derive(Clone, PartialEq, Eq, Debug)]
-pub enum WherePredicateTarget {
+pub enum WherePredicateTypeTarget {
     TypeRef(TypeRef),
     /// For desugared where predicates that can directly refer to a type param.
     TypeParam(LocalTypeParamId),
+    // FIXME: ForLifetime(Vec<LifetimeParamId>, TypeRef)
 }
 
 type SourceMap = ArenaMap<LocalTypeParamId, Either<ast::Trait, ast::TypeParam>>;
@@ -123,7 +130,7 @@ impl GenericParams {
     }
 
     fn new(db: &dyn DefDatabase, def: GenericDefId) -> (GenericParams, InFile<SourceMap>) {
-        let mut generics = GenericParams { types: Arena::default(), where_predicates: Vec::new() };
+        let mut generics = GenericParams::default();
         let mut sm = ArenaMap::default();
 
         // FIXME: add `: Sized` bound for everything except for `Self` in traits
@@ -171,7 +178,7 @@ impl GenericParams {
                 // add super traits as bounds on Self
                 // i.e., trait Foo: Bar is equivalent to trait Foo where Self: Bar
                 let self_param = TypeRef::Path(name![Self].into());
-                generics.fill_bounds(&lower_ctx, &src.value, self_param);
+                generics.fill_bounds(&lower_ctx, &src.value, Either::Left(self_param));
 
                 generics.fill(&lower_ctx, &mut sm, &src.value);
                 src.file_id
@@ -218,12 +225,12 @@ impl GenericParams {
         &mut self,
         lower_ctx: &LowerCtx,
         node: &dyn ast::TypeBoundsOwner,
-        type_ref: TypeRef,
+        target: Either<TypeRef, LifetimeRef>,
     ) {
         for bound in
             node.type_bound_list().iter().flat_map(|type_bound_list| type_bound_list.bounds())
         {
-            self.add_where_predicate_from_bound(lower_ctx, bound, type_ref.clone());
+            self.add_where_predicate_from_bound(lower_ctx, bound, target.clone());
         }
     }
 
@@ -246,19 +253,30 @@ impl GenericParams {
             sm.insert(param_id, Either::Right(type_param.clone()));
 
             let type_ref = TypeRef::Path(name.into());
-            self.fill_bounds(&lower_ctx, &type_param, type_ref);
+            self.fill_bounds(&lower_ctx, &type_param, Either::Left(type_ref));
+        }
+        for lifetime_param in params.lifetime_params() {
+            let name = lifetime_param
+                .lifetime_token()
+                .map_or_else(Name::missing, |tok| Name::new_lifetime(&tok));
+            let param = LifetimeParamData { name: name.clone() };
+            let _param_id = self.lifetimes.alloc(param);
+            let lifetime_ref = LifetimeRef::new_name(name);
+            self.fill_bounds(&lower_ctx, &lifetime_param, Either::Right(lifetime_ref));
         }
     }
 
     fn fill_where_predicates(&mut self, lower_ctx: &LowerCtx, where_clause: ast::WhereClause) {
         for pred in where_clause.predicates() {
-            let type_ref = match pred.ty() {
-                Some(type_ref) => type_ref,
-                None => continue,
+            let target = if let Some(type_ref) = pred.ty() {
+                Either::Left(TypeRef::from_ast(lower_ctx, type_ref))
+            } else if let Some(lifetime_tok) = pred.lifetime_token() {
+                Either::Right(LifetimeRef::from_token(lifetime_tok))
+            } else {
+                continue;
             };
-            let type_ref = TypeRef::from_ast(lower_ctx, type_ref);
             for bound in pred.type_bound_list().iter().flat_map(|l| l.bounds()) {
-                self.add_where_predicate_from_bound(lower_ctx, bound, type_ref.clone());
+                self.add_where_predicate_from_bound(lower_ctx, bound, target.clone());
             }
         }
     }
@@ -267,15 +285,24 @@ impl GenericParams {
         &mut self,
         lower_ctx: &LowerCtx,
         bound: ast::TypeBound,
-        type_ref: TypeRef,
+        target: Either<TypeRef, LifetimeRef>,
     ) {
         if bound.question_mark_token().is_some() {
             // FIXME: remove this bound
             return;
         }
         let bound = TypeBound::from_ast(lower_ctx, bound);
-        self.where_predicates
-            .push(WherePredicate { target: WherePredicateTarget::TypeRef(type_ref), bound });
+        let predicate = match (target, bound) {
+            (Either::Left(type_ref), bound) => WherePredicate::TypeBound {
+                target: WherePredicateTypeTarget::TypeRef(type_ref),
+                bound,
+            },
+            (Either::Right(lifetime), TypeBound::Lifetime(bound)) => {
+                WherePredicate::Lifetime { target: lifetime, bound }
+            }
+            _ => return,
+        };
+        self.where_predicates.push(predicate);
     }
 
     pub(crate) fn fill_implicit_impl_trait_args(&mut self, type_ref: &TypeRef) {
@@ -288,8 +315,8 @@ impl GenericParams {
                 };
                 let param_id = self.types.alloc(param);
                 for bound in bounds {
-                    self.where_predicates.push(WherePredicate {
-                        target: WherePredicateTarget::TypeParam(param_id),
+                    self.where_predicates.push(WherePredicate::TypeBound {
+                        target: WherePredicateTypeTarget::TypeParam(param_id),
                         bound: bound.clone(),
                     });
                 }
diff --git a/crates/hir_def/src/item_tree.rs b/crates/hir_def/src/item_tree.rs
index c017b352d..c6ada271e 100644
--- a/crates/hir_def/src/item_tree.rs
+++ b/crates/hir_def/src/item_tree.rs
@@ -255,7 +255,7 @@ impl GenericParamsStorage {
 }
 
 static EMPTY_GENERICS: GenericParams =
-    GenericParams { types: Arena::new(), where_predicates: Vec::new() };
+    GenericParams { types: Arena::new(), lifetimes: Arena::new(), where_predicates: Vec::new() };
 
 #[derive(Default, Debug, Eq, PartialEq)]
 struct ItemTreeData {
diff --git a/crates/hir_def/src/item_tree/lower.rs b/crates/hir_def/src/item_tree/lower.rs
index 63b2826f8..f7ce2e26d 100644
--- a/crates/hir_def/src/item_tree/lower.rs
+++ b/crates/hir_def/src/item_tree/lower.rs
@@ -13,6 +13,7 @@ use syntax::{
 use crate::{
     attr::Attrs,
     generics::{GenericParams, TypeParamData, TypeParamProvenance},
+    type_ref::LifetimeRef,
 };
 
 use super::*;
@@ -292,12 +293,16 @@ impl Ctx {
                         let self_type = TypeRef::Path(name![Self].into());
                         match self_param.kind() {
                             ast::SelfParamKind::Owned => self_type,
-                            ast::SelfParamKind::Ref => {
-                                TypeRef::Reference(Box::new(self_type), Mutability::Shared)
-                            }
-                            ast::SelfParamKind::MutRef => {
-                                TypeRef::Reference(Box::new(self_type), Mutability::Mut)
-                            }
+                            ast::SelfParamKind::Ref => TypeRef::Reference(
+                                Box::new(self_type),
+                                self_param.lifetime_token().map(LifetimeRef::from_token),
+                                Mutability::Shared,
+                            ),
+                            ast::SelfParamKind::MutRef => TypeRef::Reference(
+                                Box::new(self_type),
+                                self_param.lifetime_token().map(LifetimeRef::from_token),
+                                Mutability::Mut,
+                            ),
                         }
                     }
                 };
@@ -629,8 +634,7 @@ impl Ctx {
                 // add super traits as bounds on Self
                 // i.e., trait Foo: Bar is equivalent to trait Foo where Self: Bar
                 let self_param = TypeRef::Path(name![Self].into());
-                generics.fill_bounds(&self.body_ctx, trait_def, self_param);
-
+                generics.fill_bounds(&self.body_ctx, trait_def, Either::Left(self_param));
                 generics.fill(&self.body_ctx, &mut sm, node);
             }
             GenericsOwner::Impl => {
diff --git a/crates/hir_def/src/lib.rs b/crates/hir_def/src/lib.rs
index a75d4d302..7e2199a9c 100644
--- a/crates/hir_def/src/lib.rs
+++ b/crates/hir_def/src/lib.rs
@@ -225,6 +225,13 @@ pub struct TypeParamId {
 pub type LocalTypeParamId = Idx<generics::TypeParamData>;
 
 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+pub struct LifetimeParamId {
+    pub parent: GenericDefId,
+    pub local_id: LocalLifetimeParamId,
+}
+pub type LocalLifetimeParamId = Idx<generics::LifetimeParamData>;
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
 pub enum ContainerId {
     ModuleId(ModuleId),
     DefWithBodyId(DefWithBodyId),
diff --git a/crates/hir_def/src/path.rs b/crates/hir_def/src/path.rs
index 5b8c1e449..00a69a8a6 100644
--- a/crates/hir_def/src/path.rs
+++ b/crates/hir_def/src/path.rs
@@ -7,7 +7,7 @@ use std::{
     sync::Arc,
 };
 
-use crate::body::LowerCtx;
+use crate::{body::LowerCtx, type_ref::LifetimeRef};
 use base_db::CrateId;
 use hir_expand::{
     hygiene::Hygiene,
@@ -145,7 +145,7 @@ pub struct AssociatedTypeBinding {
 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
 pub enum GenericArg {
     Type(TypeRef),
-    // or lifetime...
+    Lifetime(LifetimeRef),
 }
 
 impl Path {
diff --git a/crates/hir_def/src/path/lower.rs b/crates/hir_def/src/path/lower.rs
index 07b9723ce..60fa7646b 100644
--- a/crates/hir_def/src/path/lower.rs
+++ b/crates/hir_def/src/path/lower.rs
@@ -15,7 +15,7 @@ use super::AssociatedTypeBinding;
 use crate::{
     body::LowerCtx,
     path::{GenericArg, GenericArgs, ModPath, Path, PathKind},
-    type_ref::{TypeBound, TypeRef},
+    type_ref::{LifetimeRef, TypeBound, TypeRef},
 };
 
 pub(super) use lower_use::lower_use_tree;
@@ -170,8 +170,14 @@ pub(super) fn lower_generic_args(
                     bindings.push(AssociatedTypeBinding { name, type_ref, bounds });
                 }
             }
-            // Lifetimes and constants are ignored for now.
-            ast::GenericArg::LifetimeArg(_) | ast::GenericArg::ConstArg(_) => (),
+            ast::GenericArg::LifetimeArg(lifetime_arg) => {
+                if let Some(lifetime) = lifetime_arg.lifetime_token() {
+                    let lifetime_ref = LifetimeRef::from_token(lifetime);
+                    args.push(GenericArg::Lifetime(lifetime_ref))
+                }
+            }
+            // constants are ignored for now.
+            ast::GenericArg::ConstArg(_) => (),
         }
     }
 
diff --git a/crates/hir_def/src/type_ref.rs b/crates/hir_def/src/type_ref.rs
index 1a78c1444..347ceabb9 100644
--- a/crates/hir_def/src/type_ref.rs
+++ b/crates/hir_def/src/type_ref.rs
@@ -1,6 +1,7 @@
 //! HIR for references to types. Paths in these are not yet resolved. They can
 //! be directly created from an ast::TypeRef, without further queries.
-use syntax::ast::{self};
+use hir_expand::name::Name;
+use syntax::{ast, SyntaxToken};
 
 use crate::{body::LowerCtx, path::Path};
 
@@ -58,7 +59,7 @@ pub enum TypeRef {
     Tuple(Vec<TypeRef>),
     Path(Path),
     RawPtr(Box<TypeRef>, Mutability),
-    Reference(Box<TypeRef>, Mutability),
+    Reference(Box<TypeRef>, Option<LifetimeRef>, Mutability),
     Array(Box<TypeRef> /*, Expr*/),
     Slice(Box<TypeRef>),
     /// A fn pointer. Last element of the vector is the return type.
@@ -70,10 +71,29 @@ pub enum TypeRef {
 }
 
 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
+pub struct LifetimeRef {
+    pub name: Name,
+}
+
+impl LifetimeRef {
+    pub(crate) fn new_name(name: Name) -> Self {
+        LifetimeRef { name }
+    }
+
+    pub(crate) fn from_token(token: SyntaxToken) -> Self {
+        LifetimeRef { name: Name::new_lifetime(&token) }
+    }
+
+    pub fn missing() -> LifetimeRef {
+        LifetimeRef { name: Name::missing() }
+    }
+}
+
+#[derive(Clone, PartialEq, Eq, Hash, Debug)]
 pub enum TypeBound {
     Path(Path),
-    // also for<> bounds
-    // also Lifetimes
+    // ForLifetime(Vec<LifetimeRef>, Path), FIXME ForLifetime
+    Lifetime(LifetimeRef),
     Error,
 }
 
@@ -107,8 +127,9 @@ impl TypeRef {
             }
             ast::Type::RefType(inner) => {
                 let inner_ty = TypeRef::from_ast_opt(&ctx, inner.ty());
+                let lifetime = inner.lifetime_token().map(|t| LifetimeRef::from_token(t));
                 let mutability = Mutability::from_mutable(inner.mut_token().is_some());
-                TypeRef::Reference(Box::new(inner_ty), mutability)
+                TypeRef::Reference(Box::new(inner_ty), lifetime, mutability)
             }
             ast::Type::InferType(_inner) => TypeRef::Placeholder,
             ast::Type::FnPtrType(inner) => {
@@ -163,14 +184,14 @@ impl TypeRef {
                     types.iter().for_each(|t| go(t, f))
                 }
                 TypeRef::RawPtr(type_ref, _)
-                | TypeRef::Reference(type_ref, _)
+                | TypeRef::Reference(type_ref, ..)
                 | TypeRef::Array(type_ref)
                 | TypeRef::Slice(type_ref) => go(&type_ref, f),
                 TypeRef::ImplTrait(bounds) | TypeRef::DynTrait(bounds) => {
                     for bound in bounds {
                         match bound {
                             TypeBound::Path(path) => go_path(path, f),
-                            TypeBound::Error => (),
+                            TypeBound::Lifetime(_) | TypeBound::Error => (),
                         }
                     }
                 }
@@ -186,8 +207,12 @@ impl TypeRef {
             for segment in path.segments().iter() {
                 if let Some(args_and_bindings) = segment.args_and_bindings {
                     for arg in &args_and_bindings.args {
-                        let crate::path::GenericArg::Type(type_ref) = arg;
-                        go(type_ref, f);
+                        match arg {
+                            crate::path::GenericArg::Type(type_ref) => {
+                                go(type_ref, f);
+                            }
+                            crate::path::GenericArg::Lifetime(_) => {}
+                        }
                     }
                     for binding in &args_and_bindings.bindings {
                         if let Some(type_ref) = &binding.type_ref {
@@ -196,7 +221,7 @@ impl TypeRef {
                         for bound in &binding.bounds {
                             match bound {
                                 TypeBound::Path(path) => go_path(path, f),
-                                TypeBound::Error => (),
+                                TypeBound::Lifetime(_) | TypeBound::Error => (),
                             }
                         }
                     }
@@ -232,7 +257,10 @@ impl TypeBound {
                 };
                 TypeBound::Path(path)
             }
-            ast::TypeBoundKind::ForType(_) | ast::TypeBoundKind::Lifetime(_) => TypeBound::Error,
+            ast::TypeBoundKind::ForType(_) => TypeBound::Error, // FIXME ForType
+            ast::TypeBoundKind::Lifetime(lifetime) => {
+                TypeBound::Lifetime(LifetimeRef::from_token(lifetime))
+            }
         }
     }