diff options
Diffstat (limited to 'crates/hir_ty/src/lib.rs')
-rw-r--r-- | crates/hir_ty/src/lib.rs | 843 |
1 files changed, 24 insertions, 819 deletions
diff --git a/crates/hir_ty/src/lib.rs b/crates/hir_ty/src/lib.rs index 4c3d904bf..76609e2df 100644 --- a/crates/hir_ty/src/lib.rs +++ b/crates/hir_ty/src/lib.rs | |||
@@ -14,6 +14,10 @@ mod lower; | |||
14 | pub(crate) mod infer; | 14 | pub(crate) mod infer; |
15 | pub(crate) mod utils; | 15 | pub(crate) mod utils; |
16 | mod chalk_cast; | 16 | mod chalk_cast; |
17 | mod chalk_ext; | ||
18 | mod builder; | ||
19 | mod walk; | ||
20 | mod types; | ||
17 | 21 | ||
18 | pub mod display; | 22 | pub mod display; |
19 | pub mod db; | 23 | pub mod db; |
@@ -24,30 +28,30 @@ mod tests; | |||
24 | #[cfg(test)] | 28 | #[cfg(test)] |
25 | mod test_db; | 29 | mod test_db; |
26 | 30 | ||
27 | use std::{iter, mem, sync::Arc}; | 31 | use std::sync::Arc; |
28 | 32 | ||
29 | use base_db::salsa; | ||
30 | use chalk_ir::cast::{CastTo, Caster}; | ||
31 | use hir_def::{ | ||
32 | builtin_type::BuiltinType, expr::ExprId, type_ref::Rawness, AssocContainerId, FunctionId, | ||
33 | GenericDefId, HasModule, LifetimeParamId, Lookup, TraitId, TypeAliasId, TypeParamId, | ||
34 | }; | ||
35 | use itertools::Itertools; | 33 | use itertools::Itertools; |
36 | use smallvec::SmallVec; | 34 | use smallvec::SmallVec; |
37 | 35 | ||
38 | use crate::{ | 36 | use base_db::salsa; |
39 | db::HirDatabase, | 37 | use hir_def::{ |
40 | display::HirDisplay, | 38 | expr::ExprId, type_ref::Rawness, AssocContainerId, FunctionId, GenericDefId, HasModule, Lookup, |
41 | utils::{generics, make_mut_slice, Generics}, | 39 | TraitId, TypeAliasId, TypeParamId, |
42 | }; | 40 | }; |
43 | 41 | ||
42 | use crate::{db::HirDatabase, display::HirDisplay, utils::generics}; | ||
43 | |||
44 | pub use autoderef::autoderef; | 44 | pub use autoderef::autoderef; |
45 | pub use builder::TyBuilder; | ||
46 | pub use chalk_ext::TyExt; | ||
45 | pub use infer::{could_unify, InferenceResult, InferenceVar}; | 47 | pub use infer::{could_unify, InferenceResult, InferenceVar}; |
46 | pub use lower::{ | 48 | pub use lower::{ |
47 | associated_type_shorthand_candidates, callable_item_sig, CallableDefId, ImplTraitLoweringMode, | 49 | associated_type_shorthand_candidates, callable_item_sig, CallableDefId, ImplTraitLoweringMode, |
48 | TyDefId, TyLoweringContext, ValueTyDefId, | 50 | TyDefId, TyLoweringContext, ValueTyDefId, |
49 | }; | 51 | }; |
50 | pub use traits::{AliasEq, DomainGoal, InEnvironment, TraitEnvironment}; | 52 | pub use traits::TraitEnvironment; |
53 | pub use types::*; | ||
54 | pub use walk::TypeWalk; | ||
51 | 55 | ||
52 | pub use chalk_ir::{ | 56 | pub use chalk_ir::{ |
53 | cast::Cast, AdtId, BoundVar, DebruijnIndex, Mutability, Safety, Scalar, TyVariableKind, | 57 | cast::Cast, AdtId, BoundVar, DebruijnIndex, Mutability, Safety, Scalar, TyVariableKind, |
@@ -66,41 +70,6 @@ pub type CanonicalVarKinds = chalk_ir::CanonicalVarKinds<Interner>; | |||
66 | 70 | ||
67 | pub type ChalkTraitId = chalk_ir::TraitId<Interner>; | 71 | pub type ChalkTraitId = chalk_ir::TraitId<Interner>; |
68 | 72 | ||
69 | #[derive(Clone, PartialEq, Eq, Debug, Hash)] | ||
70 | pub enum Lifetime { | ||
71 | Parameter(LifetimeParamId), | ||
72 | Static, | ||
73 | } | ||
74 | |||
75 | #[derive(Clone, PartialEq, Eq, Debug, Hash)] | ||
76 | pub struct OpaqueTy { | ||
77 | pub opaque_ty_id: OpaqueTyId, | ||
78 | pub substitution: Substitution, | ||
79 | } | ||
80 | |||
81 | impl TypeWalk for OpaqueTy { | ||
82 | fn walk(&self, f: &mut impl FnMut(&Ty)) { | ||
83 | self.substitution.walk(f); | ||
84 | } | ||
85 | |||
86 | fn walk_mut_binders( | ||
87 | &mut self, | ||
88 | f: &mut impl FnMut(&mut Ty, DebruijnIndex), | ||
89 | binders: DebruijnIndex, | ||
90 | ) { | ||
91 | self.substitution.walk_mut_binders(f, binders); | ||
92 | } | ||
93 | } | ||
94 | |||
95 | /// A "projection" type corresponds to an (unnormalized) | ||
96 | /// projection like `<P0 as Trait<P1..Pn>>::Foo`. Note that the | ||
97 | /// trait and all its parameters are fully known. | ||
98 | #[derive(Clone, PartialEq, Eq, Debug, Hash)] | ||
99 | pub struct ProjectionTy { | ||
100 | pub associated_ty_id: AssocTypeId, | ||
101 | pub substitution: Substitution, | ||
102 | } | ||
103 | |||
104 | impl ProjectionTy { | 73 | impl ProjectionTy { |
105 | pub fn trait_ref(&self, db: &dyn HirDatabase) -> TraitRef { | 74 | pub fn trait_ref(&self, db: &dyn HirDatabase) -> TraitRef { |
106 | TraitRef { | 75 | TraitRef { |
@@ -110,7 +79,7 @@ impl ProjectionTy { | |||
110 | } | 79 | } |
111 | 80 | ||
112 | pub fn self_type_parameter(&self) -> &Ty { | 81 | pub fn self_type_parameter(&self) -> &Ty { |
113 | &self.substitution.interned(&Interner)[0].assert_ty_ref(&Interner) | 82 | &self.substitution.interned()[0].assert_ty_ref(&Interner) |
114 | } | 83 | } |
115 | 84 | ||
116 | fn trait_(&self, db: &dyn HirDatabase) -> TraitId { | 85 | fn trait_(&self, db: &dyn HirDatabase) -> TraitId { |
@@ -121,322 +90,11 @@ impl ProjectionTy { | |||
121 | } | 90 | } |
122 | } | 91 | } |
123 | 92 | ||
124 | impl TypeWalk for ProjectionTy { | ||
125 | fn walk(&self, f: &mut impl FnMut(&Ty)) { | ||
126 | self.substitution.walk(f); | ||
127 | } | ||
128 | |||
129 | fn walk_mut_binders( | ||
130 | &mut self, | ||
131 | f: &mut impl FnMut(&mut Ty, DebruijnIndex), | ||
132 | binders: DebruijnIndex, | ||
133 | ) { | ||
134 | self.substitution.walk_mut_binders(f, binders); | ||
135 | } | ||
136 | } | ||
137 | |||
138 | #[derive(Clone, PartialEq, Eq, Debug, Hash)] | ||
139 | pub struct DynTy { | ||
140 | /// The unknown self type. | ||
141 | pub bounds: Binders<QuantifiedWhereClauses>, | ||
142 | } | ||
143 | |||
144 | pub type FnSig = chalk_ir::FnSig<Interner>; | 93 | pub type FnSig = chalk_ir::FnSig<Interner>; |
145 | 94 | ||
146 | #[derive(Clone, PartialEq, Eq, Debug, Hash)] | ||
147 | pub struct FnPointer { | ||
148 | pub num_args: usize, | ||
149 | pub sig: FnSig, | ||
150 | pub substs: Substitution, | ||
151 | } | ||
152 | |||
153 | #[derive(Clone, PartialEq, Eq, Debug, Hash)] | ||
154 | pub enum AliasTy { | ||
155 | /// A "projection" type corresponds to an (unnormalized) | ||
156 | /// projection like `<P0 as Trait<P1..Pn>>::Foo`. Note that the | ||
157 | /// trait and all its parameters are fully known. | ||
158 | Projection(ProjectionTy), | ||
159 | /// An opaque type (`impl Trait`). | ||
160 | /// | ||
161 | /// This is currently only used for return type impl trait; each instance of | ||
162 | /// `impl Trait` in a return type gets its own ID. | ||
163 | Opaque(OpaqueTy), | ||
164 | } | ||
165 | |||
166 | impl TypeWalk for AliasTy { | ||
167 | fn walk(&self, f: &mut impl FnMut(&Ty)) { | ||
168 | match self { | ||
169 | AliasTy::Projection(it) => it.walk(f), | ||
170 | AliasTy::Opaque(it) => it.walk(f), | ||
171 | } | ||
172 | } | ||
173 | |||
174 | fn walk_mut_binders( | ||
175 | &mut self, | ||
176 | f: &mut impl FnMut(&mut Ty, DebruijnIndex), | ||
177 | binders: DebruijnIndex, | ||
178 | ) { | ||
179 | match self { | ||
180 | AliasTy::Projection(it) => it.walk_mut_binders(f, binders), | ||
181 | AliasTy::Opaque(it) => it.walk_mut_binders(f, binders), | ||
182 | } | ||
183 | } | ||
184 | } | ||
185 | /// A type. | ||
186 | /// | ||
187 | /// See also the `TyKind` enum in rustc (librustc/ty/sty.rs), which represents | ||
188 | /// the same thing (but in a different way). | ||
189 | /// | ||
190 | /// This should be cheap to clone. | ||
191 | #[derive(Clone, PartialEq, Eq, Debug, Hash)] | ||
192 | pub enum TyKind { | ||
193 | /// Structures, enumerations and unions. | ||
194 | Adt(AdtId<Interner>, Substitution), | ||
195 | |||
196 | /// Represents an associated item like `Iterator::Item`. This is used | ||
197 | /// when we have tried to normalize a projection like `T::Item` but | ||
198 | /// couldn't find a better representation. In that case, we generate | ||
199 | /// an **application type** like `(Iterator::Item)<T>`. | ||
200 | AssociatedType(AssocTypeId, Substitution), | ||
201 | |||
202 | /// a scalar type like `bool` or `u32` | ||
203 | Scalar(Scalar), | ||
204 | |||
205 | /// A tuple type. For example, `(i32, bool)`. | ||
206 | Tuple(usize, Substitution), | ||
207 | |||
208 | /// An array with the given length. Written as `[T; n]`. | ||
209 | Array(Ty), | ||
210 | |||
211 | /// The pointee of an array slice. Written as `[T]`. | ||
212 | Slice(Ty), | ||
213 | |||
214 | /// A raw pointer. Written as `*mut T` or `*const T` | ||
215 | Raw(Mutability, Ty), | ||
216 | |||
217 | /// A reference; a pointer with an associated lifetime. Written as | ||
218 | /// `&'a mut T` or `&'a T`. | ||
219 | Ref(Mutability, Ty), | ||
220 | |||
221 | /// This represents a placeholder for an opaque type in situations where we | ||
222 | /// don't know the hidden type (i.e. currently almost always). This is | ||
223 | /// analogous to the `AssociatedType` type constructor. | ||
224 | /// It is also used as the type of async block, with one type parameter | ||
225 | /// representing the Future::Output type. | ||
226 | OpaqueType(OpaqueTyId, Substitution), | ||
227 | |||
228 | /// The anonymous type of a function declaration/definition. Each | ||
229 | /// function has a unique type, which is output (for a function | ||
230 | /// named `foo` returning an `i32`) as `fn() -> i32 {foo}`. | ||
231 | /// | ||
232 | /// This includes tuple struct / enum variant constructors as well. | ||
233 | /// | ||
234 | /// For example the type of `bar` here: | ||
235 | /// | ||
236 | /// ``` | ||
237 | /// fn foo() -> i32 { 1 } | ||
238 | /// let bar = foo; // bar: fn() -> i32 {foo} | ||
239 | /// ``` | ||
240 | FnDef(FnDefId, Substitution), | ||
241 | |||
242 | /// The pointee of a string slice. Written as `str`. | ||
243 | Str, | ||
244 | |||
245 | /// The never type `!`. | ||
246 | Never, | ||
247 | |||
248 | /// The type of a specific closure. | ||
249 | /// | ||
250 | /// The closure signature is stored in a `FnPtr` type in the first type | ||
251 | /// parameter. | ||
252 | Closure(ClosureId, Substitution), | ||
253 | |||
254 | /// Represents a foreign type declared in external blocks. | ||
255 | ForeignType(ForeignDefId), | ||
256 | |||
257 | /// A pointer to a function. Written as `fn() -> i32`. | ||
258 | /// | ||
259 | /// For example the type of `bar` here: | ||
260 | /// | ||
261 | /// ``` | ||
262 | /// fn foo() -> i32 { 1 } | ||
263 | /// let bar: fn() -> i32 = foo; | ||
264 | /// ``` | ||
265 | Function(FnPointer), | ||
266 | |||
267 | /// An "alias" type represents some form of type alias, such as: | ||
268 | /// - An associated type projection like `<T as Iterator>::Item` | ||
269 | /// - `impl Trait` types | ||
270 | /// - Named type aliases like `type Foo<X> = Vec<X>` | ||
271 | Alias(AliasTy), | ||
272 | |||
273 | /// A placeholder for a type parameter; for example, `T` in `fn f<T>(x: T) | ||
274 | /// {}` when we're type-checking the body of that function. In this | ||
275 | /// situation, we know this stands for *some* type, but don't know the exact | ||
276 | /// type. | ||
277 | Placeholder(PlaceholderIndex), | ||
278 | |||
279 | /// A bound type variable. This is used in various places: when representing | ||
280 | /// some polymorphic type like the type of function `fn f<T>`, the type | ||
281 | /// parameters get turned into variables; during trait resolution, inference | ||
282 | /// variables get turned into bound variables and back; and in `Dyn` the | ||
283 | /// `Self` type is represented with a bound variable as well. | ||
284 | BoundVar(BoundVar), | ||
285 | |||
286 | /// A type variable used during type checking. | ||
287 | InferenceVar(InferenceVar, TyVariableKind), | ||
288 | |||
289 | /// A trait object (`dyn Trait` or bare `Trait` in pre-2018 Rust). | ||
290 | /// | ||
291 | /// The predicates are quantified over the `Self` type, i.e. `Ty::Bound(0)` | ||
292 | /// represents the `Self` type inside the bounds. This is currently | ||
293 | /// implicit; Chalk has the `Binders` struct to make it explicit, but it | ||
294 | /// didn't seem worth the overhead yet. | ||
295 | Dyn(DynTy), | ||
296 | |||
297 | /// A placeholder for a type which could not be computed; this is propagated | ||
298 | /// to avoid useless error messages. Doubles as a placeholder where type | ||
299 | /// variables are inserted before type checking, since we want to try to | ||
300 | /// infer a better type here anyway -- for the IDE use case, we want to try | ||
301 | /// to infer as much as possible even in the presence of type errors. | ||
302 | Unknown, | ||
303 | } | ||
304 | |||
305 | #[derive(Clone, PartialEq, Eq, Debug, Hash)] | ||
306 | pub struct Ty(Arc<TyKind>); | ||
307 | |||
308 | impl TyKind { | ||
309 | pub fn intern(self, _interner: &Interner) -> Ty { | ||
310 | Ty(Arc::new(self)) | ||
311 | } | ||
312 | } | ||
313 | |||
314 | impl Ty { | ||
315 | pub fn kind(&self, _interner: &Interner) -> &TyKind { | ||
316 | &self.0 | ||
317 | } | ||
318 | |||
319 | pub fn interned_mut(&mut self) -> &mut TyKind { | ||
320 | Arc::make_mut(&mut self.0) | ||
321 | } | ||
322 | |||
323 | pub fn into_inner(self) -> TyKind { | ||
324 | Arc::try_unwrap(self.0).unwrap_or_else(|a| (*a).clone()) | ||
325 | } | ||
326 | } | ||
327 | |||
328 | #[derive(Clone, PartialEq, Eq, Debug, Hash)] | ||
329 | pub struct GenericArg { | ||
330 | interned: GenericArgData, | ||
331 | } | ||
332 | |||
333 | #[derive(Clone, PartialEq, Eq, Debug, Hash)] | ||
334 | pub enum GenericArgData { | ||
335 | Ty(Ty), | ||
336 | } | ||
337 | |||
338 | impl GenericArg { | ||
339 | /// Constructs a generic argument using `GenericArgData`. | ||
340 | pub fn new(_interner: &Interner, data: GenericArgData) -> Self { | ||
341 | GenericArg { interned: data } | ||
342 | } | ||
343 | |||
344 | /// Gets the interned value. | ||
345 | pub fn interned(&self) -> &GenericArgData { | ||
346 | &self.interned | ||
347 | } | ||
348 | |||
349 | /// Asserts that this is a type argument. | ||
350 | pub fn assert_ty_ref(&self, interner: &Interner) -> &Ty { | ||
351 | self.ty(interner).unwrap() | ||
352 | } | ||
353 | |||
354 | /// Checks whether the generic argument is a type. | ||
355 | pub fn is_ty(&self, _interner: &Interner) -> bool { | ||
356 | match self.interned() { | ||
357 | GenericArgData::Ty(_) => true, | ||
358 | } | ||
359 | } | ||
360 | |||
361 | /// Returns the type if it is one, `None` otherwise. | ||
362 | pub fn ty(&self, _interner: &Interner) -> Option<&Ty> { | ||
363 | match self.interned() { | ||
364 | GenericArgData::Ty(t) => Some(t), | ||
365 | } | ||
366 | } | ||
367 | } | ||
368 | |||
369 | impl TypeWalk for GenericArg { | ||
370 | fn walk(&self, f: &mut impl FnMut(&Ty)) { | ||
371 | match &self.interned { | ||
372 | GenericArgData::Ty(ty) => { | ||
373 | ty.walk(f); | ||
374 | } | ||
375 | } | ||
376 | } | ||
377 | |||
378 | fn walk_mut_binders( | ||
379 | &mut self, | ||
380 | f: &mut impl FnMut(&mut Ty, DebruijnIndex), | ||
381 | binders: DebruijnIndex, | ||
382 | ) { | ||
383 | match &mut self.interned { | ||
384 | GenericArgData::Ty(ty) => { | ||
385 | ty.walk_mut_binders(f, binders); | ||
386 | } | ||
387 | } | ||
388 | } | ||
389 | } | ||
390 | |||
391 | /// A list of substitutions for generic parameters. | ||
392 | #[derive(Clone, PartialEq, Eq, Debug, Hash)] | ||
393 | pub struct Substitution(SmallVec<[GenericArg; 2]>); | ||
394 | |||
395 | impl TypeWalk for Substitution { | ||
396 | fn walk(&self, f: &mut impl FnMut(&Ty)) { | ||
397 | for t in self.0.iter() { | ||
398 | t.walk(f); | ||
399 | } | ||
400 | } | ||
401 | |||
402 | fn walk_mut_binders( | ||
403 | &mut self, | ||
404 | f: &mut impl FnMut(&mut Ty, DebruijnIndex), | ||
405 | binders: DebruijnIndex, | ||
406 | ) { | ||
407 | for t in &mut self.0 { | ||
408 | t.walk_mut_binders(f, binders); | ||
409 | } | ||
410 | } | ||
411 | } | ||
412 | |||
413 | impl Substitution { | 95 | impl Substitution { |
414 | pub fn interned(&self, _: &Interner) -> &[GenericArg] { | ||
415 | &self.0 | ||
416 | } | ||
417 | |||
418 | pub fn len(&self, _: &Interner) -> usize { | ||
419 | self.0.len() | ||
420 | } | ||
421 | |||
422 | pub fn is_empty(&self, _: &Interner) -> bool { | ||
423 | self.0.is_empty() | ||
424 | } | ||
425 | |||
426 | pub fn at(&self, _: &Interner, i: usize) -> &GenericArg { | ||
427 | &self.0[i] | ||
428 | } | ||
429 | |||
430 | pub fn empty(_: &Interner) -> Substitution { | ||
431 | Substitution(SmallVec::new()) | ||
432 | } | ||
433 | |||
434 | pub fn iter(&self, _: &Interner) -> std::slice::Iter<'_, GenericArg> { | ||
435 | self.0.iter() | ||
436 | } | ||
437 | |||
438 | pub fn single(ty: Ty) -> Substitution { | 96 | pub fn single(ty: Ty) -> Substitution { |
439 | Substitution({ | 97 | Substitution::intern({ |
440 | let mut v = SmallVec::new(); | 98 | let mut v = SmallVec::new(); |
441 | v.push(ty.cast(&Interner)); | 99 | v.push(ty.cast(&Interner)); |
442 | v | 100 | v |
@@ -444,64 +102,14 @@ impl Substitution { | |||
444 | } | 102 | } |
445 | 103 | ||
446 | pub fn prefix(&self, n: usize) -> Substitution { | 104 | pub fn prefix(&self, n: usize) -> Substitution { |
447 | Substitution(self.0[..std::cmp::min(self.0.len(), n)].into()) | 105 | Substitution::intern(self.interned()[..std::cmp::min(self.len(&Interner), n)].into()) |
448 | } | 106 | } |
449 | 107 | ||
450 | pub fn suffix(&self, n: usize) -> Substitution { | 108 | pub fn suffix(&self, n: usize) -> Substitution { |
451 | Substitution(self.0[self.0.len() - std::cmp::min(self.0.len(), n)..].into()) | 109 | Substitution::intern( |
452 | } | 110 | self.interned()[self.len(&Interner) - std::cmp::min(self.len(&Interner), n)..].into(), |
453 | |||
454 | pub fn from_iter( | ||
455 | interner: &Interner, | ||
456 | elements: impl IntoIterator<Item = impl CastTo<GenericArg>>, | ||
457 | ) -> Self { | ||
458 | Substitution(elements.into_iter().casted(interner).collect()) | ||
459 | } | ||
460 | |||
461 | /// Return Substs that replace each parameter by itself (i.e. `Ty::Param`). | ||
462 | pub(crate) fn type_params_for_generics( | ||
463 | db: &dyn HirDatabase, | ||
464 | generic_params: &Generics, | ||
465 | ) -> Substitution { | ||
466 | Substitution::from_iter( | ||
467 | &Interner, | ||
468 | generic_params | ||
469 | .iter() | ||
470 | .map(|(id, _)| TyKind::Placeholder(to_placeholder_idx(db, id)).intern(&Interner)), | ||
471 | ) | ||
472 | } | ||
473 | |||
474 | /// Return Substs that replace each parameter by itself (i.e. `Ty::Param`). | ||
475 | pub fn type_params(db: &dyn HirDatabase, def: impl Into<GenericDefId>) -> Substitution { | ||
476 | let params = generics(db.upcast(), def.into()); | ||
477 | Substitution::type_params_for_generics(db, ¶ms) | ||
478 | } | ||
479 | |||
480 | /// Return Substs that replace each parameter by a bound variable. | ||
481 | pub(crate) fn bound_vars(generic_params: &Generics, debruijn: DebruijnIndex) -> Substitution { | ||
482 | Substitution::from_iter( | ||
483 | &Interner, | ||
484 | generic_params | ||
485 | .iter() | ||
486 | .enumerate() | ||
487 | .map(|(idx, _)| TyKind::BoundVar(BoundVar::new(debruijn, idx)).intern(&Interner)), | ||
488 | ) | 111 | ) |
489 | } | 112 | } |
490 | |||
491 | pub fn build_for_def(db: &dyn HirDatabase, def: impl Into<GenericDefId>) -> SubstsBuilder { | ||
492 | let def = def.into(); | ||
493 | let params = generics(db.upcast(), def); | ||
494 | let param_count = params.len(); | ||
495 | Substitution::builder(param_count) | ||
496 | } | ||
497 | |||
498 | pub(crate) fn build_for_generics(generic_params: &Generics) -> SubstsBuilder { | ||
499 | Substitution::builder(generic_params.len()) | ||
500 | } | ||
501 | |||
502 | fn builder(param_count: usize) -> SubstsBuilder { | ||
503 | SubstsBuilder { vec: Vec::with_capacity(param_count), param_count } | ||
504 | } | ||
505 | } | 113 | } |
506 | 114 | ||
507 | /// Return an index of a parameter in the generic type parameter list by it's id. | 115 | /// Return an index of a parameter in the generic type parameter list by it's id. |
@@ -509,58 +117,6 @@ pub fn param_idx(db: &dyn HirDatabase, id: TypeParamId) -> Option<usize> { | |||
509 | generics(db.upcast(), id.parent).param_idx(id) | 117 | generics(db.upcast(), id.parent).param_idx(id) |
510 | } | 118 | } |
511 | 119 | ||
512 | #[derive(Debug, Clone)] | ||
513 | pub struct SubstsBuilder { | ||
514 | vec: Vec<GenericArg>, | ||
515 | param_count: usize, | ||
516 | } | ||
517 | |||
518 | impl SubstsBuilder { | ||
519 | pub fn build(self) -> Substitution { | ||
520 | assert_eq!(self.vec.len(), self.param_count); | ||
521 | Substitution::from_iter(&Interner, self.vec) | ||
522 | } | ||
523 | |||
524 | pub fn push(mut self, ty: impl CastTo<GenericArg>) -> Self { | ||
525 | self.vec.push(ty.cast(&Interner)); | ||
526 | self | ||
527 | } | ||
528 | |||
529 | fn remaining(&self) -> usize { | ||
530 | self.param_count - self.vec.len() | ||
531 | } | ||
532 | |||
533 | pub fn fill_with_bound_vars(self, debruijn: DebruijnIndex, starting_from: usize) -> Self { | ||
534 | self.fill( | ||
535 | (starting_from..) | ||
536 | .map(|idx| TyKind::BoundVar(BoundVar::new(debruijn, idx)).intern(&Interner)), | ||
537 | ) | ||
538 | } | ||
539 | |||
540 | pub fn fill_with_unknown(self) -> Self { | ||
541 | self.fill(iter::repeat(TyKind::Unknown.intern(&Interner))) | ||
542 | } | ||
543 | |||
544 | pub fn fill(mut self, filler: impl Iterator<Item = impl CastTo<GenericArg>>) -> Self { | ||
545 | self.vec.extend(filler.take(self.remaining()).casted(&Interner)); | ||
546 | assert_eq!(self.remaining(), 0); | ||
547 | self | ||
548 | } | ||
549 | |||
550 | pub fn use_parent_substs(mut self, parent_substs: &Substitution) -> Self { | ||
551 | assert!(self.vec.is_empty()); | ||
552 | assert!(parent_substs.len(&Interner) <= self.param_count); | ||
553 | self.vec.extend(parent_substs.iter(&Interner).cloned()); | ||
554 | self | ||
555 | } | ||
556 | } | ||
557 | |||
558 | #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)] | ||
559 | pub struct Binders<T> { | ||
560 | pub num_binders: usize, | ||
561 | pub value: T, | ||
562 | } | ||
563 | |||
564 | impl<T> Binders<T> { | 120 | impl<T> Binders<T> { |
565 | pub fn new(num_binders: usize, value: T) -> Self { | 121 | pub fn new(num_binders: usize, value: T) -> Self { |
566 | Self { num_binders, value } | 122 | Self { num_binders, value } |
@@ -608,27 +164,6 @@ impl<T: TypeWalk> Binders<T> { | |||
608 | } | 164 | } |
609 | } | 165 | } |
610 | 166 | ||
611 | impl<T: TypeWalk> TypeWalk for Binders<T> { | ||
612 | fn walk(&self, f: &mut impl FnMut(&Ty)) { | ||
613 | self.value.walk(f); | ||
614 | } | ||
615 | |||
616 | fn walk_mut_binders( | ||
617 | &mut self, | ||
618 | f: &mut impl FnMut(&mut Ty, DebruijnIndex), | ||
619 | binders: DebruijnIndex, | ||
620 | ) { | ||
621 | self.value.walk_mut_binders(f, binders.shifted_in()) | ||
622 | } | ||
623 | } | ||
624 | |||
625 | /// A trait with type parameters. This includes the `Self`, so this represents a concrete type implementing the trait. | ||
626 | #[derive(Clone, PartialEq, Eq, Debug, Hash)] | ||
627 | pub struct TraitRef { | ||
628 | pub trait_id: ChalkTraitId, | ||
629 | pub substitution: Substitution, | ||
630 | } | ||
631 | |||
632 | impl TraitRef { | 167 | impl TraitRef { |
633 | pub fn self_type_parameter(&self) -> &Ty { | 168 | pub fn self_type_parameter(&self) -> &Ty { |
634 | &self.substitution.at(&Interner, 0).assert_ty_ref(&Interner) | 169 | &self.substitution.at(&Interner, 0).assert_ty_ref(&Interner) |
@@ -639,30 +174,6 @@ impl TraitRef { | |||
639 | } | 174 | } |
640 | } | 175 | } |
641 | 176 | ||
642 | impl TypeWalk for TraitRef { | ||
643 | fn walk(&self, f: &mut impl FnMut(&Ty)) { | ||
644 | self.substitution.walk(f); | ||
645 | } | ||
646 | |||
647 | fn walk_mut_binders( | ||
648 | &mut self, | ||
649 | f: &mut impl FnMut(&mut Ty, DebruijnIndex), | ||
650 | binders: DebruijnIndex, | ||
651 | ) { | ||
652 | self.substitution.walk_mut_binders(f, binders); | ||
653 | } | ||
654 | } | ||
655 | |||
656 | /// Like `generics::WherePredicate`, but with resolved types: A condition on the | ||
657 | /// parameters of a generic item. | ||
658 | #[derive(Debug, Clone, PartialEq, Eq, Hash)] | ||
659 | pub enum WhereClause { | ||
660 | /// The given trait needs to be implemented for its type parameters. | ||
661 | Implemented(TraitRef), | ||
662 | /// An associated type bindings like in `Iterator<Item = T>`. | ||
663 | AliasEq(AliasEq), | ||
664 | } | ||
665 | |||
666 | impl WhereClause { | 177 | impl WhereClause { |
667 | pub fn is_implemented(&self) -> bool { | 178 | pub fn is_implemented(&self) -> bool { |
668 | matches!(self, WhereClause::Implemented(_)) | 179 | matches!(self, WhereClause::Implemented(_)) |
@@ -679,56 +190,6 @@ impl WhereClause { | |||
679 | } | 190 | } |
680 | } | 191 | } |
681 | 192 | ||
682 | impl TypeWalk for WhereClause { | ||
683 | fn walk(&self, f: &mut impl FnMut(&Ty)) { | ||
684 | match self { | ||
685 | WhereClause::Implemented(trait_ref) => trait_ref.walk(f), | ||
686 | WhereClause::AliasEq(alias_eq) => alias_eq.walk(f), | ||
687 | } | ||
688 | } | ||
689 | |||
690 | fn walk_mut_binders( | ||
691 | &mut self, | ||
692 | f: &mut impl FnMut(&mut Ty, DebruijnIndex), | ||
693 | binders: DebruijnIndex, | ||
694 | ) { | ||
695 | match self { | ||
696 | WhereClause::Implemented(trait_ref) => trait_ref.walk_mut_binders(f, binders), | ||
697 | WhereClause::AliasEq(alias_eq) => alias_eq.walk_mut_binders(f, binders), | ||
698 | } | ||
699 | } | ||
700 | } | ||
701 | |||
702 | pub type QuantifiedWhereClause = Binders<WhereClause>; | ||
703 | |||
704 | #[derive(Debug, Clone, PartialEq, Eq, Hash)] | ||
705 | pub struct QuantifiedWhereClauses(Arc<[QuantifiedWhereClause]>); | ||
706 | |||
707 | impl QuantifiedWhereClauses { | ||
708 | pub fn from_iter( | ||
709 | _interner: &Interner, | ||
710 | elements: impl IntoIterator<Item = QuantifiedWhereClause>, | ||
711 | ) -> Self { | ||
712 | QuantifiedWhereClauses(elements.into_iter().collect()) | ||
713 | } | ||
714 | |||
715 | pub fn interned(&self) -> &Arc<[QuantifiedWhereClause]> { | ||
716 | &self.0 | ||
717 | } | ||
718 | } | ||
719 | |||
720 | /// Basically a claim (currently not validated / checked) that the contained | ||
721 | /// type / trait ref contains no inference variables; any inference variables it | ||
722 | /// contained have been replaced by bound variables, and `kinds` tells us how | ||
723 | /// many there are and whether they were normal or float/int variables. This is | ||
724 | /// used to erase irrelevant differences between types before using them in | ||
725 | /// queries. | ||
726 | #[derive(Debug, Clone, PartialEq, Eq, Hash)] | ||
727 | pub struct Canonical<T> { | ||
728 | pub value: T, | ||
729 | pub binders: CanonicalVarKinds, | ||
730 | } | ||
731 | |||
732 | impl<T> Canonical<T> { | 193 | impl<T> Canonical<T> { |
733 | pub fn new(value: T, kinds: impl IntoIterator<Item = TyVariableKind>) -> Self { | 194 | pub fn new(value: T, kinds: impl IntoIterator<Item = TyVariableKind>) -> Self { |
734 | let kinds = kinds.into_iter().map(|tk| { | 195 | let kinds = kinds.into_iter().map(|tk| { |
@@ -760,12 +221,12 @@ impl CallableSig { | |||
760 | 221 | ||
761 | pub fn from_fn_ptr(fn_ptr: &FnPointer) -> CallableSig { | 222 | pub fn from_fn_ptr(fn_ptr: &FnPointer) -> CallableSig { |
762 | CallableSig { | 223 | CallableSig { |
763 | // FIXME: what to do about lifetime params? | 224 | // FIXME: what to do about lifetime params? -> return PolyFnSig |
764 | params_and_return: fn_ptr | 225 | params_and_return: fn_ptr |
765 | .substs | 226 | .substs |
766 | .clone() | 227 | .clone() |
767 | .shift_bound_vars_out(DebruijnIndex::ONE) | 228 | .shift_bound_vars_out(DebruijnIndex::ONE) |
768 | .interned(&Interner) | 229 | .interned() |
769 | .iter() | 230 | .iter() |
770 | .map(|arg| arg.assert_ty_ref(&Interner).clone()) | 231 | .map(|arg| arg.assert_ty_ref(&Interner).clone()) |
771 | .collect(), | 232 | .collect(), |
@@ -773,16 +234,6 @@ impl CallableSig { | |||
773 | } | 234 | } |
774 | } | 235 | } |
775 | 236 | ||
776 | pub fn from_substs(substs: &Substitution) -> CallableSig { | ||
777 | CallableSig { | ||
778 | params_and_return: substs | ||
779 | .iter(&Interner) | ||
780 | .map(|arg| arg.assert_ty_ref(&Interner).clone()) | ||
781 | .collect(), | ||
782 | is_varargs: false, | ||
783 | } | ||
784 | } | ||
785 | |||
786 | pub fn params(&self) -> &[Ty] { | 237 | pub fn params(&self) -> &[Ty] { |
787 | &self.params_and_return[0..self.params_and_return.len() - 1] | 238 | &self.params_and_return[0..self.params_and_return.len() - 1] |
788 | } | 239 | } |
@@ -792,59 +243,7 @@ impl CallableSig { | |||
792 | } | 243 | } |
793 | } | 244 | } |
794 | 245 | ||
795 | impl TypeWalk for CallableSig { | ||
796 | fn walk(&self, f: &mut impl FnMut(&Ty)) { | ||
797 | for t in self.params_and_return.iter() { | ||
798 | t.walk(f); | ||
799 | } | ||
800 | } | ||
801 | |||
802 | fn walk_mut_binders( | ||
803 | &mut self, | ||
804 | f: &mut impl FnMut(&mut Ty, DebruijnIndex), | ||
805 | binders: DebruijnIndex, | ||
806 | ) { | ||
807 | for t in make_mut_slice(&mut self.params_and_return) { | ||
808 | t.walk_mut_binders(f, binders); | ||
809 | } | ||
810 | } | ||
811 | } | ||
812 | |||
813 | impl Ty { | 246 | impl Ty { |
814 | pub fn unit() -> Self { | ||
815 | TyKind::Tuple(0, Substitution::empty(&Interner)).intern(&Interner) | ||
816 | } | ||
817 | |||
818 | pub fn adt_ty(adt: hir_def::AdtId, substs: Substitution) -> Ty { | ||
819 | TyKind::Adt(AdtId(adt), substs).intern(&Interner) | ||
820 | } | ||
821 | |||
822 | pub fn fn_ptr(sig: CallableSig) -> Self { | ||
823 | TyKind::Function(FnPointer { | ||
824 | num_args: sig.params().len(), | ||
825 | sig: FnSig { abi: (), safety: Safety::Safe, variadic: sig.is_varargs }, | ||
826 | substs: Substitution::from_iter(&Interner, sig.params_and_return.iter().cloned()), | ||
827 | }) | ||
828 | .intern(&Interner) | ||
829 | } | ||
830 | |||
831 | pub fn builtin(builtin: BuiltinType) -> Self { | ||
832 | match builtin { | ||
833 | BuiltinType::Char => TyKind::Scalar(Scalar::Char).intern(&Interner), | ||
834 | BuiltinType::Bool => TyKind::Scalar(Scalar::Bool).intern(&Interner), | ||
835 | BuiltinType::Str => TyKind::Str.intern(&Interner), | ||
836 | BuiltinType::Int(t) => { | ||
837 | TyKind::Scalar(Scalar::Int(primitive::int_ty_from_builtin(t))).intern(&Interner) | ||
838 | } | ||
839 | BuiltinType::Uint(t) => { | ||
840 | TyKind::Scalar(Scalar::Uint(primitive::uint_ty_from_builtin(t))).intern(&Interner) | ||
841 | } | ||
842 | BuiltinType::Float(t) => { | ||
843 | TyKind::Scalar(Scalar::Float(primitive::float_ty_from_builtin(t))).intern(&Interner) | ||
844 | } | ||
845 | } | ||
846 | } | ||
847 | |||
848 | pub fn as_reference(&self) -> Option<(&Ty, Mutability)> { | 247 | pub fn as_reference(&self) -> Option<(&Ty, Mutability)> { |
849 | match self.kind(&Interner) { | 248 | match self.kind(&Interner) { |
850 | TyKind::Ref(mutability, ty) => Some((ty, *mutability)), | 249 | TyKind::Ref(mutability, ty) => Some((ty, *mutability)), |
@@ -1068,7 +467,7 @@ impl Ty { | |||
1068 | let param_data = &generic_params.types[id.local_id]; | 467 | let param_data = &generic_params.types[id.local_id]; |
1069 | match param_data.provenance { | 468 | match param_data.provenance { |
1070 | hir_def::generics::TypeParamProvenance::ArgumentImplTrait => { | 469 | hir_def::generics::TypeParamProvenance::ArgumentImplTrait => { |
1071 | let substs = Substitution::type_params(db, id.parent); | 470 | let substs = TyBuilder::type_params_subst(db, id.parent); |
1072 | let predicates = db | 471 | let predicates = db |
1073 | .generic_predicates(id.parent) | 472 | .generic_predicates(id.parent) |
1074 | .into_iter() | 473 | .into_iter() |
@@ -1114,200 +513,6 @@ impl Ty { | |||
1114 | } | 513 | } |
1115 | } | 514 | } |
1116 | 515 | ||
1117 | /// This allows walking structures that contain types to do something with those | ||
1118 | /// types, similar to Chalk's `Fold` trait. | ||
1119 | pub trait TypeWalk { | ||
1120 | fn walk(&self, f: &mut impl FnMut(&Ty)); | ||
1121 | fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) { | ||
1122 | self.walk_mut_binders(&mut |ty, _binders| f(ty), DebruijnIndex::INNERMOST); | ||
1123 | } | ||
1124 | /// Walk the type, counting entered binders. | ||
1125 | /// | ||
1126 | /// `TyKind::Bound` variables use DeBruijn indexing, which means that 0 refers | ||
1127 | /// to the innermost binder, 1 to the next, etc.. So when we want to | ||
1128 | /// substitute a certain bound variable, we can't just walk the whole type | ||
1129 | /// and blindly replace each instance of a certain index; when we 'enter' | ||
1130 | /// things that introduce new bound variables, we have to keep track of | ||
1131 | /// that. Currently, the only thing that introduces bound variables on our | ||
1132 | /// side are `TyKind::Dyn` and `TyKind::Opaque`, which each introduce a bound | ||
1133 | /// variable for the self type. | ||
1134 | fn walk_mut_binders( | ||
1135 | &mut self, | ||
1136 | f: &mut impl FnMut(&mut Ty, DebruijnIndex), | ||
1137 | binders: DebruijnIndex, | ||
1138 | ); | ||
1139 | |||
1140 | fn fold_binders( | ||
1141 | mut self, | ||
1142 | f: &mut impl FnMut(Ty, DebruijnIndex) -> Ty, | ||
1143 | binders: DebruijnIndex, | ||
1144 | ) -> Self | ||
1145 | where | ||
1146 | Self: Sized, | ||
1147 | { | ||
1148 | self.walk_mut_binders( | ||
1149 | &mut |ty_mut, binders| { | ||
1150 | let ty = mem::replace(ty_mut, TyKind::Unknown.intern(&Interner)); | ||
1151 | *ty_mut = f(ty, binders); | ||
1152 | }, | ||
1153 | binders, | ||
1154 | ); | ||
1155 | self | ||
1156 | } | ||
1157 | |||
1158 | fn fold(mut self, f: &mut impl FnMut(Ty) -> Ty) -> Self | ||
1159 | where | ||
1160 | Self: Sized, | ||
1161 | { | ||
1162 | self.walk_mut(&mut |ty_mut| { | ||
1163 | let ty = mem::replace(ty_mut, TyKind::Unknown.intern(&Interner)); | ||
1164 | *ty_mut = f(ty); | ||
1165 | }); | ||
1166 | self | ||
1167 | } | ||
1168 | |||
1169 | /// Substitutes `TyKind::Bound` vars with the given substitution. | ||
1170 | fn subst_bound_vars(self, substs: &Substitution) -> Self | ||
1171 | where | ||
1172 | Self: Sized, | ||
1173 | { | ||
1174 | self.subst_bound_vars_at_depth(substs, DebruijnIndex::INNERMOST) | ||
1175 | } | ||
1176 | |||
1177 | /// Substitutes `TyKind::Bound` vars with the given substitution. | ||
1178 | fn subst_bound_vars_at_depth(mut self, substs: &Substitution, depth: DebruijnIndex) -> Self | ||
1179 | where | ||
1180 | Self: Sized, | ||
1181 | { | ||
1182 | self.walk_mut_binders( | ||
1183 | &mut |ty, binders| { | ||
1184 | if let &mut TyKind::BoundVar(bound) = ty.interned_mut() { | ||
1185 | if bound.debruijn >= binders { | ||
1186 | *ty = substs.0[bound.index] | ||
1187 | .assert_ty_ref(&Interner) | ||
1188 | .clone() | ||
1189 | .shift_bound_vars(binders); | ||
1190 | } | ||
1191 | } | ||
1192 | }, | ||
1193 | depth, | ||
1194 | ); | ||
1195 | self | ||
1196 | } | ||
1197 | |||
1198 | /// Shifts up debruijn indices of `TyKind::Bound` vars by `n`. | ||
1199 | fn shift_bound_vars(self, n: DebruijnIndex) -> Self | ||
1200 | where | ||
1201 | Self: Sized, | ||
1202 | { | ||
1203 | self.fold_binders( | ||
1204 | &mut |ty, binders| match ty.kind(&Interner) { | ||
1205 | TyKind::BoundVar(bound) if bound.debruijn >= binders => { | ||
1206 | TyKind::BoundVar(bound.shifted_in_from(n)).intern(&Interner) | ||
1207 | } | ||
1208 | _ => ty, | ||
1209 | }, | ||
1210 | DebruijnIndex::INNERMOST, | ||
1211 | ) | ||
1212 | } | ||
1213 | |||
1214 | /// Shifts debruijn indices of `TyKind::Bound` vars out (down) by `n`. | ||
1215 | fn shift_bound_vars_out(self, n: DebruijnIndex) -> Self | ||
1216 | where | ||
1217 | Self: Sized + std::fmt::Debug, | ||
1218 | { | ||
1219 | self.fold_binders( | ||
1220 | &mut |ty, binders| match ty.kind(&Interner) { | ||
1221 | TyKind::BoundVar(bound) if bound.debruijn >= binders => { | ||
1222 | TyKind::BoundVar(bound.shifted_out_to(n).unwrap_or(bound.clone())) | ||
1223 | .intern(&Interner) | ||
1224 | } | ||
1225 | _ => ty, | ||
1226 | }, | ||
1227 | DebruijnIndex::INNERMOST, | ||
1228 | ) | ||
1229 | } | ||
1230 | } | ||
1231 | |||
1232 | impl TypeWalk for Ty { | ||
1233 | fn walk(&self, f: &mut impl FnMut(&Ty)) { | ||
1234 | match self.kind(&Interner) { | ||
1235 | TyKind::Alias(AliasTy::Projection(p_ty)) => { | ||
1236 | for t in p_ty.substitution.iter(&Interner) { | ||
1237 | t.walk(f); | ||
1238 | } | ||
1239 | } | ||
1240 | TyKind::Alias(AliasTy::Opaque(o_ty)) => { | ||
1241 | for t in o_ty.substitution.iter(&Interner) { | ||
1242 | t.walk(f); | ||
1243 | } | ||
1244 | } | ||
1245 | TyKind::Dyn(dyn_ty) => { | ||
1246 | for p in dyn_ty.bounds.value.interned().iter() { | ||
1247 | p.walk(f); | ||
1248 | } | ||
1249 | } | ||
1250 | TyKind::Slice(ty) | TyKind::Array(ty) | TyKind::Ref(_, ty) | TyKind::Raw(_, ty) => { | ||
1251 | ty.walk(f); | ||
1252 | } | ||
1253 | _ => { | ||
1254 | if let Some(substs) = self.substs() { | ||
1255 | for t in substs.iter(&Interner) { | ||
1256 | t.walk(f); | ||
1257 | } | ||
1258 | } | ||
1259 | } | ||
1260 | } | ||
1261 | f(self); | ||
1262 | } | ||
1263 | |||
1264 | fn walk_mut_binders( | ||
1265 | &mut self, | ||
1266 | f: &mut impl FnMut(&mut Ty, DebruijnIndex), | ||
1267 | binders: DebruijnIndex, | ||
1268 | ) { | ||
1269 | match self.interned_mut() { | ||
1270 | TyKind::Alias(AliasTy::Projection(p_ty)) => { | ||
1271 | p_ty.substitution.walk_mut_binders(f, binders); | ||
1272 | } | ||
1273 | TyKind::Dyn(dyn_ty) => { | ||
1274 | for p in make_mut_slice(&mut dyn_ty.bounds.value.0) { | ||
1275 | p.walk_mut_binders(f, binders.shifted_in()); | ||
1276 | } | ||
1277 | } | ||
1278 | TyKind::Alias(AliasTy::Opaque(o_ty)) => { | ||
1279 | o_ty.substitution.walk_mut_binders(f, binders); | ||
1280 | } | ||
1281 | TyKind::Slice(ty) | TyKind::Array(ty) | TyKind::Ref(_, ty) | TyKind::Raw(_, ty) => { | ||
1282 | ty.walk_mut_binders(f, binders); | ||
1283 | } | ||
1284 | _ => { | ||
1285 | if let Some(substs) = self.substs_mut() { | ||
1286 | substs.walk_mut_binders(f, binders); | ||
1287 | } | ||
1288 | } | ||
1289 | } | ||
1290 | f(self, binders); | ||
1291 | } | ||
1292 | } | ||
1293 | |||
1294 | impl<T: TypeWalk> TypeWalk for Vec<T> { | ||
1295 | fn walk(&self, f: &mut impl FnMut(&Ty)) { | ||
1296 | for t in self { | ||
1297 | t.walk(f); | ||
1298 | } | ||
1299 | } | ||
1300 | fn walk_mut_binders( | ||
1301 | &mut self, | ||
1302 | f: &mut impl FnMut(&mut Ty, DebruijnIndex), | ||
1303 | binders: DebruijnIndex, | ||
1304 | ) { | ||
1305 | for t in self { | ||
1306 | t.walk_mut_binders(f, binders); | ||
1307 | } | ||
1308 | } | ||
1309 | } | ||
1310 | |||
1311 | #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)] | 516 | #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)] |
1312 | pub enum ImplTraitId { | 517 | pub enum ImplTraitId { |
1313 | ReturnTypeImplTrait(hir_def::FunctionId, u16), | 518 | ReturnTypeImplTrait(hir_def::FunctionId, u16), |