aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_hir/src/ty.rs
diff options
context:
space:
mode:
Diffstat (limited to 'crates/ra_hir/src/ty.rs')
-rw-r--r--crates/ra_hir/src/ty.rs77
1 files changed, 58 insertions, 19 deletions
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index 4ebd44d27..719b3f7cd 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -1,3 +1,18 @@
1//! The type system. We currently use this to infer types for completion.
2//!
3//! For type inference, compare the implementations in rustc (the various
4//! check_* methods in librustc_typeck/check/mod.rs are a good entry point) and
5//! IntelliJ-Rust (org.rust.lang.core.types.infer). Our entry point for
6//! inference here is the `infer` function, which infers the types of all
7//! expressions in a given function.
8//!
9//! The central struct here is `Ty`, which represents a type. During inference,
10//! it can contain type 'variables' which represent currently unknown types; as
11//! we walk through the expressions, we might determine that certain variables
12//! need to be equal to each other, or to certain types. To record this, we use
13//! the union-find implementation from the `ena` crate, which is extracted from
14//! rustc.
15
1mod primitive; 16mod primitive;
2#[cfg(test)] 17#[cfg(test)]
3mod tests; 18mod tests;
@@ -21,6 +36,7 @@ use crate::{
21 type_ref::{TypeRef, Mutability}, 36 type_ref::{TypeRef, Mutability},
22}; 37};
23 38
39/// The ID of a type variable.
24#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)] 40#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
25pub struct TypeVarId(u32); 41pub struct TypeVarId(u32);
26 42
@@ -40,6 +56,8 @@ impl UnifyKey for TypeVarId {
40 } 56 }
41} 57}
42 58
59/// The value of a type variable: either we already know the type, or we don't
60/// know it yet.
43#[derive(Clone, PartialEq, Eq, Debug)] 61#[derive(Clone, PartialEq, Eq, Debug)]
44pub enum TypeVarValue { 62pub enum TypeVarValue {
45 Known(Ty), 63 Known(Ty),
@@ -47,7 +65,7 @@ pub enum TypeVarValue {
47} 65}
48 66
49impl TypeVarValue { 67impl TypeVarValue {
50 pub fn known(&self) -> Option<&Ty> { 68 fn known(&self) -> Option<&Ty> {
51 match self { 69 match self {
52 TypeVarValue::Known(ty) => Some(ty), 70 TypeVarValue::Known(ty) => Some(ty),
53 TypeVarValue::Unknown => None, 71 TypeVarValue::Unknown => None,
@@ -75,10 +93,13 @@ impl UnifyValue for TypeVarValue {
75 } 93 }
76} 94}
77 95
96/// The kinds of placeholders we need during type inference. Currently, we only
97/// have type variables; in the future, we will probably also need int and float
98/// variables, for inference of literal values (e.g. `100` could be one of
99/// several integer types).
78#[derive(Clone, PartialEq, Eq, Hash, Debug)] 100#[derive(Clone, PartialEq, Eq, Hash, Debug)]
79pub enum InferTy { 101pub enum InferTy {
80 TypeVar(TypeVarId), 102 TypeVar(TypeVarId),
81 // later we'll have IntVar and FloatVar as well
82} 103}
83 104
84/// When inferring an expression, we propagate downward whatever type hint we 105/// When inferring an expression, we propagate downward whatever type hint we
@@ -92,15 +113,21 @@ struct Expectation {
92} 113}
93 114
94impl Expectation { 115impl Expectation {
116 /// The expectation that the type of the expression needs to equal the given
117 /// type.
95 fn has_type(ty: Ty) -> Self { 118 fn has_type(ty: Ty) -> Self {
96 Expectation { ty } 119 Expectation { ty }
97 } 120 }
98 121
122 /// This expresses no expectation on the type.
99 fn none() -> Self { 123 fn none() -> Self {
100 Expectation { ty: Ty::Unknown } 124 Expectation { ty: Ty::Unknown }
101 } 125 }
102} 126}
103 127
128/// A type. This is based on the `TyKind` enum in rustc (librustc/ty/sty.rs).
129///
130/// This should be cheap to clone.
104#[derive(Clone, PartialEq, Eq, Hash, Debug)] 131#[derive(Clone, PartialEq, Eq, Hash, Debug)]
105pub enum Ty { 132pub enum Ty {
106 /// The primitive boolean type. Written as `bool`. 133 /// The primitive boolean type. Written as `bool`.
@@ -134,14 +161,14 @@ pub enum Ty {
134 // An array with the given length. Written as `[T; n]`. 161 // An array with the given length. Written as `[T; n]`.
135 // Array(Ty, ty::Const), 162 // Array(Ty, ty::Const),
136 /// The pointee of an array slice. Written as `[T]`. 163 /// The pointee of an array slice. Written as `[T]`.
137 Slice(TyRef), 164 Slice(Arc<Ty>),
138 165
139 /// A raw pointer. Written as `*mut T` or `*const T` 166 /// A raw pointer. Written as `*mut T` or `*const T`
140 RawPtr(TyRef, Mutability), 167 RawPtr(Arc<Ty>, Mutability),
141 168
142 /// A reference; a pointer with an associated lifetime. Written as 169 /// A reference; a pointer with an associated lifetime. Written as
143 /// `&'a mut T` or `&'a T`. 170 /// `&'a mut T` or `&'a T`.
144 Ref(TyRef, Mutability), 171 Ref(Arc<Ty>, Mutability),
145 172
146 /// A pointer to a function. Written as `fn() -> i32`. 173 /// A pointer to a function. Written as `fn() -> i32`.
147 /// 174 ///
@@ -153,6 +180,10 @@ pub enum Ty {
153 /// ``` 180 /// ```
154 FnPtr(Arc<FnSig>), 181 FnPtr(Arc<FnSig>),
155 182
183 // rustc has a separate type for each function, which just coerces to the
184 // above function pointer type. Once we implement generics, we will probably
185 // need this as well.
186
156 // A trait, defined with `dyn trait`. 187 // A trait, defined with `dyn trait`.
157 // Dynamic(), 188 // Dynamic(),
158 // The anonymous type of a closure. Used to represent the type of 189 // The anonymous type of a closure. Used to represent the type of
@@ -166,7 +197,7 @@ pub enum Ty {
166 // A type representin the types stored inside a generator. 197 // A type representin the types stored inside a generator.
167 // This should only appear in GeneratorInteriors. 198 // This should only appear in GeneratorInteriors.
168 // GeneratorWitness(Binder<&'tcx List<Ty<'tcx>>>), 199 // GeneratorWitness(Binder<&'tcx List<Ty<'tcx>>>),
169 /// The never type `!` 200 /// The never type `!`.
170 Never, 201 Never,
171 202
172 /// A tuple type. For example, `(i32, bool)`. 203 /// A tuple type. For example, `(i32, bool)`.
@@ -177,10 +208,6 @@ pub enum Ty {
177 // Projection(ProjectionTy), 208 // Projection(ProjectionTy),
178 209
179 // Opaque (`impl Trait`) type found in a return type. 210 // Opaque (`impl Trait`) type found in a return type.
180 // The `DefId` comes either from
181 // * the `impl Trait` ast::Ty node,
182 // * or the `existential type` declaration
183 // The substitutions are for the generics of the function in question.
184 // Opaque(DefId, Substs), 211 // Opaque(DefId, Substs),
185 212
186 // A type parameter; for example, `T` in `fn f<T>(x: T) {} 213 // A type parameter; for example, `T` in `fn f<T>(x: T) {}
@@ -192,12 +219,12 @@ pub enum Ty {
192 /// A placeholder for a type which could not be computed; this is propagated 219 /// A placeholder for a type which could not be computed; this is propagated
193 /// to avoid useless error messages. Doubles as a placeholder where type 220 /// to avoid useless error messages. Doubles as a placeholder where type
194 /// variables are inserted before type checking, since we want to try to 221 /// variables are inserted before type checking, since we want to try to
195 /// infer a better type here anyway. 222 /// infer a better type here anyway -- for the IDE use case, we want to try
223 /// to infer as much as possible even in the presence of type errors.
196 Unknown, 224 Unknown,
197} 225}
198 226
199type TyRef = Arc<Ty>; 227/// A function signature.
200
201#[derive(Clone, PartialEq, Eq, Hash, Debug)] 228#[derive(Clone, PartialEq, Eq, Hash, Debug)]
202pub struct FnSig { 229pub struct FnSig {
203 input: Vec<Ty>, 230 input: Vec<Ty>,
@@ -368,7 +395,11 @@ impl fmt::Display for Ty {
368 } 395 }
369} 396}
370 397
371pub fn type_for_fn(db: &impl HirDatabase, f: Function) -> Cancelable<Ty> { 398// Functions returning declared types for items
399
400/// Compute the declared type of a function. This should not need to look at the
401/// function body (but currently uses the function AST, so does anyway - TODO).
402fn type_for_fn(db: &impl HirDatabase, f: Function) -> Cancelable<Ty> {
372 let syntax = f.syntax(db); 403 let syntax = f.syntax(db);
373 let module = f.module(db)?; 404 let module = f.module(db)?;
374 let node = syntax.borrowed(); 405 let node = syntax.borrowed();
@@ -390,7 +421,7 @@ pub fn type_for_fn(db: &impl HirDatabase, f: Function) -> Cancelable<Ty> {
390 Ok(Ty::FnPtr(Arc::new(sig))) 421 Ok(Ty::FnPtr(Arc::new(sig)))
391} 422}
392 423
393pub fn type_for_struct(db: &impl HirDatabase, s: Struct) -> Cancelable<Ty> { 424fn type_for_struct(db: &impl HirDatabase, s: Struct) -> Cancelable<Ty> {
394 Ok(Ty::Adt { 425 Ok(Ty::Adt {
395 def_id: s.def_id(), 426 def_id: s.def_id(),
396 name: s.name(db)?.unwrap_or_else(Name::missing), 427 name: s.name(db)?.unwrap_or_else(Name::missing),
@@ -404,7 +435,7 @@ pub fn type_for_enum(db: &impl HirDatabase, s: Enum) -> Cancelable<Ty> {
404 }) 435 })
405} 436}
406 437
407pub fn type_for_def(db: &impl HirDatabase, def_id: DefId) -> Cancelable<Ty> { 438pub(super) fn type_for_def(db: &impl HirDatabase, def_id: DefId) -> Cancelable<Ty> {
408 let def = def_id.resolve(db)?; 439 let def = def_id.resolve(db)?;
409 match def { 440 match def {
410 Def::Module(..) => { 441 Def::Module(..) => {
@@ -444,19 +475,25 @@ pub(super) fn type_for_field(db: &impl HirDatabase, def_id: DefId, field: Name)
444 Ty::from_hir(db, &module, &type_ref) 475 Ty::from_hir(db, &module, &type_ref)
445} 476}
446 477
478/// The result of type inference: A mapping from expressions and patterns to types.
447#[derive(Clone, PartialEq, Eq, Debug)] 479#[derive(Clone, PartialEq, Eq, Debug)]
448pub struct InferenceResult { 480pub struct InferenceResult {
449 type_of: FxHashMap<LocalSyntaxPtr, Ty>, 481 type_of: FxHashMap<LocalSyntaxPtr, Ty>,
450} 482}
451 483
452impl InferenceResult { 484impl InferenceResult {
485 /// Returns the type of the given syntax node, if it was inferred. Will
486 /// return `None` for syntax nodes not in the inferred function or not
487 /// pointing to an expression/pattern, `Some(Ty::Unknown)` for
488 /// expressions/patterns that could not be inferred.
453 pub fn type_of_node(&self, node: SyntaxNodeRef) -> Option<Ty> { 489 pub fn type_of_node(&self, node: SyntaxNodeRef) -> Option<Ty> {
454 self.type_of.get(&LocalSyntaxPtr::new(node)).cloned() 490 self.type_of.get(&LocalSyntaxPtr::new(node)).cloned()
455 } 491 }
456} 492}
457 493
494/// The inference context contains all information needed during type inference.
458#[derive(Clone, Debug)] 495#[derive(Clone, Debug)]
459pub struct InferenceContext<'a, D: HirDatabase> { 496struct InferenceContext<'a, D: HirDatabase> {
460 db: &'a D, 497 db: &'a D,
461 scopes: Arc<FnScopes>, 498 scopes: Arc<FnScopes>,
462 module: Module, 499 module: Module,
@@ -738,6 +775,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
738 ast::Expr::ParenExpr(e) => self.infer_expr_opt(e.expr(), expected)?, 775 ast::Expr::ParenExpr(e) => self.infer_expr_opt(e.expr(), expected)?,
739 ast::Expr::Label(_e) => Ty::Unknown, 776 ast::Expr::Label(_e) => Ty::Unknown,
740 ast::Expr::ReturnExpr(e) => { 777 ast::Expr::ReturnExpr(e) => {
778 // TODO expect return type of function
741 self.infer_expr_opt(e.expr(), &Expectation::none())?; 779 self.infer_expr_opt(e.expr(), &Expectation::none())?;
742 Ty::Never 780 Ty::Never
743 } 781 }
@@ -870,7 +908,8 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
870 } 908 }
871} 909}
872 910
873pub fn infer(db: &impl HirDatabase, function: Function) -> Cancelable<InferenceResult> { 911pub fn infer(db: &impl HirDatabase, def_id: DefId) -> Cancelable<Arc<InferenceResult>> {
912 let function = Function::new(def_id); // TODO: consts also need inference
874 let scopes = function.scopes(db); 913 let scopes = function.scopes(db);
875 let module = function.module(db)?; 914 let module = function.module(db)?;
876 let mut ctx = InferenceContext::new(db, scopes, module); 915 let mut ctx = InferenceContext::new(db, scopes, module);
@@ -909,5 +948,5 @@ pub fn infer(db: &impl HirDatabase, function: Function) -> Cancelable<InferenceR
909 ctx.infer_block(block, &Expectation::has_type(ret_ty))?; 948 ctx.infer_block(block, &Expectation::has_type(ret_ty))?;
910 } 949 }
911 950
912 Ok(ctx.resolve_all()) 951 Ok(Arc::new(ctx.resolve_all()))
913} 952}