aboutsummaryrefslogtreecommitdiff
path: root/crates/hir_ty/src/lib.rs
diff options
context:
space:
mode:
Diffstat (limited to 'crates/hir_ty/src/lib.rs')
-rw-r--r--crates/hir_ty/src/lib.rs1078
1 files changed, 1078 insertions, 0 deletions
diff --git a/crates/hir_ty/src/lib.rs b/crates/hir_ty/src/lib.rs
new file mode 100644
index 000000000..1e748476a
--- /dev/null
+++ b/crates/hir_ty/src/lib.rs
@@ -0,0 +1,1078 @@
1//! The type system. We currently use this to infer types for completion, hover
2//! information and various assists.
3
4#[allow(unused)]
5macro_rules! eprintln {
6 ($($tt:tt)*) => { stdx::eprintln!($($tt)*) };
7}
8
9mod autoderef;
10pub mod primitive;
11pub mod traits;
12pub mod method_resolution;
13mod op;
14mod lower;
15pub(crate) mod infer;
16pub(crate) mod utils;
17
18pub mod display;
19pub mod db;
20pub mod diagnostics;
21
22#[cfg(test)]
23mod tests;
24#[cfg(test)]
25mod test_db;
26
27use std::{iter, mem, ops::Deref, sync::Arc};
28
29use base_db::{salsa, CrateId};
30use hir_def::{
31 expr::ExprId,
32 type_ref::{Mutability, Rawness},
33 AdtId, AssocContainerId, DefWithBodyId, GenericDefId, HasModule, Lookup, TraitId, TypeAliasId,
34 TypeParamId,
35};
36use itertools::Itertools;
37
38use crate::{
39 db::HirDatabase,
40 display::HirDisplay,
41 primitive::{FloatTy, IntTy},
42 utils::{generics, make_mut_slice, Generics},
43};
44
45pub use autoderef::autoderef;
46pub use infer::{InferTy, InferenceResult};
47pub use lower::CallableDefId;
48pub use lower::{
49 associated_type_shorthand_candidates, callable_item_sig, ImplTraitLoweringMode, TyDefId,
50 TyLoweringContext, ValueTyDefId,
51};
52pub use traits::{InEnvironment, Obligation, ProjectionPredicate, TraitEnvironment};
53
54pub use chalk_ir::{BoundVar, DebruijnIndex};
55
56/// A type constructor or type name: this might be something like the primitive
57/// type `bool`, a struct like `Vec`, or things like function pointers or
58/// tuples.
59#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
60pub enum TypeCtor {
61 /// The primitive boolean type. Written as `bool`.
62 Bool,
63
64 /// The primitive character type; holds a Unicode scalar value
65 /// (a non-surrogate code point). Written as `char`.
66 Char,
67
68 /// A primitive integer type. For example, `i32`.
69 Int(IntTy),
70
71 /// A primitive floating-point type. For example, `f64`.
72 Float(FloatTy),
73
74 /// Structures, enumerations and unions.
75 Adt(AdtId),
76
77 /// The pointee of a string slice. Written as `str`.
78 Str,
79
80 /// The pointee of an array slice. Written as `[T]`.
81 Slice,
82
83 /// An array with the given length. Written as `[T; n]`.
84 Array,
85
86 /// A raw pointer. Written as `*mut T` or `*const T`
87 RawPtr(Mutability),
88
89 /// A reference; a pointer with an associated lifetime. Written as
90 /// `&'a mut T` or `&'a T`.
91 Ref(Mutability),
92
93 /// The anonymous type of a function declaration/definition. Each
94 /// function has a unique type, which is output (for a function
95 /// named `foo` returning an `i32`) as `fn() -> i32 {foo}`.
96 ///
97 /// This includes tuple struct / enum variant constructors as well.
98 ///
99 /// For example the type of `bar` here:
100 ///
101 /// ```
102 /// fn foo() -> i32 { 1 }
103 /// let bar = foo; // bar: fn() -> i32 {foo}
104 /// ```
105 FnDef(CallableDefId),
106
107 /// A pointer to a function. Written as `fn() -> i32`.
108 ///
109 /// For example the type of `bar` here:
110 ///
111 /// ```
112 /// fn foo() -> i32 { 1 }
113 /// let bar: fn() -> i32 = foo;
114 /// ```
115 // FIXME make this a Ty variant like in Chalk
116 FnPtr { num_args: u16, is_varargs: bool },
117
118 /// The never type `!`.
119 Never,
120
121 /// A tuple type. For example, `(i32, bool)`.
122 Tuple { cardinality: u16 },
123
124 /// Represents an associated item like `Iterator::Item`. This is used
125 /// when we have tried to normalize a projection like `T::Item` but
126 /// couldn't find a better representation. In that case, we generate
127 /// an **application type** like `(Iterator::Item)<T>`.
128 AssociatedType(TypeAliasId),
129
130 /// This represents a placeholder for an opaque type in situations where we
131 /// don't know the hidden type (i.e. currently almost always). This is
132 /// analogous to the `AssociatedType` type constructor. As with that one,
133 /// these are only produced by Chalk.
134 OpaqueType(OpaqueTyId),
135
136 /// The type of a specific closure.
137 ///
138 /// The closure signature is stored in a `FnPtr` type in the first type
139 /// parameter.
140 Closure { def: DefWithBodyId, expr: ExprId },
141}
142
143impl TypeCtor {
144 pub fn num_ty_params(self, db: &dyn HirDatabase) -> usize {
145 match self {
146 TypeCtor::Bool
147 | TypeCtor::Char
148 | TypeCtor::Int(_)
149 | TypeCtor::Float(_)
150 | TypeCtor::Str
151 | TypeCtor::Never => 0,
152 TypeCtor::Slice
153 | TypeCtor::Array
154 | TypeCtor::RawPtr(_)
155 | TypeCtor::Ref(_)
156 | TypeCtor::Closure { .. } // 1 param representing the signature of the closure
157 => 1,
158 TypeCtor::Adt(adt) => {
159 let generic_params = generics(db.upcast(), adt.into());
160 generic_params.len()
161 }
162 TypeCtor::FnDef(callable) => {
163 let generic_params = generics(db.upcast(), callable.into());
164 generic_params.len()
165 }
166 TypeCtor::AssociatedType(type_alias) => {
167 let generic_params = generics(db.upcast(), type_alias.into());
168 generic_params.len()
169 }
170 TypeCtor::OpaqueType(opaque_ty_id) => {
171 match opaque_ty_id {
172 OpaqueTyId::ReturnTypeImplTrait(func, _) => {
173 let generic_params = generics(db.upcast(), func.into());
174 generic_params.len()
175 }
176 }
177 }
178 TypeCtor::FnPtr { num_args, is_varargs: _ } => num_args as usize + 1,
179 TypeCtor::Tuple { cardinality } => cardinality as usize,
180 }
181 }
182
183 pub fn krate(self, db: &dyn HirDatabase) -> Option<CrateId> {
184 match self {
185 TypeCtor::Bool
186 | TypeCtor::Char
187 | TypeCtor::Int(_)
188 | TypeCtor::Float(_)
189 | TypeCtor::Str
190 | TypeCtor::Never
191 | TypeCtor::Slice
192 | TypeCtor::Array
193 | TypeCtor::RawPtr(_)
194 | TypeCtor::Ref(_)
195 | TypeCtor::FnPtr { .. }
196 | TypeCtor::Tuple { .. } => None,
197 // Closure's krate is irrelevant for coherence I would think?
198 TypeCtor::Closure { .. } => None,
199 TypeCtor::Adt(adt) => Some(adt.module(db.upcast()).krate),
200 TypeCtor::FnDef(callable) => Some(callable.krate(db)),
201 TypeCtor::AssociatedType(type_alias) => {
202 Some(type_alias.lookup(db.upcast()).module(db.upcast()).krate)
203 }
204 TypeCtor::OpaqueType(opaque_ty_id) => match opaque_ty_id {
205 OpaqueTyId::ReturnTypeImplTrait(func, _) => {
206 Some(func.lookup(db.upcast()).module(db.upcast()).krate)
207 }
208 },
209 }
210 }
211
212 pub fn as_generic_def(self) -> Option<GenericDefId> {
213 match self {
214 TypeCtor::Bool
215 | TypeCtor::Char
216 | TypeCtor::Int(_)
217 | TypeCtor::Float(_)
218 | TypeCtor::Str
219 | TypeCtor::Never
220 | TypeCtor::Slice
221 | TypeCtor::Array
222 | TypeCtor::RawPtr(_)
223 | TypeCtor::Ref(_)
224 | TypeCtor::FnPtr { .. }
225 | TypeCtor::Tuple { .. }
226 | TypeCtor::Closure { .. } => None,
227 TypeCtor::Adt(adt) => Some(adt.into()),
228 TypeCtor::FnDef(callable) => Some(callable.into()),
229 TypeCtor::AssociatedType(type_alias) => Some(type_alias.into()),
230 TypeCtor::OpaqueType(_impl_trait_id) => None,
231 }
232 }
233}
234
235/// A nominal type with (maybe 0) type parameters. This might be a primitive
236/// type like `bool`, a struct, tuple, function pointer, reference or
237/// several other things.
238#[derive(Clone, PartialEq, Eq, Debug, Hash)]
239pub struct ApplicationTy {
240 pub ctor: TypeCtor,
241 pub parameters: Substs,
242}
243
244#[derive(Clone, PartialEq, Eq, Debug, Hash)]
245pub struct OpaqueTy {
246 pub opaque_ty_id: OpaqueTyId,
247 pub parameters: Substs,
248}
249
250/// A "projection" type corresponds to an (unnormalized)
251/// projection like `<P0 as Trait<P1..Pn>>::Foo`. Note that the
252/// trait and all its parameters are fully known.
253#[derive(Clone, PartialEq, Eq, Debug, Hash)]
254pub struct ProjectionTy {
255 pub associated_ty: TypeAliasId,
256 pub parameters: Substs,
257}
258
259impl ProjectionTy {
260 pub fn trait_ref(&self, db: &dyn HirDatabase) -> TraitRef {
261 TraitRef { trait_: self.trait_(db), substs: self.parameters.clone() }
262 }
263
264 fn trait_(&self, db: &dyn HirDatabase) -> TraitId {
265 match self.associated_ty.lookup(db.upcast()).container {
266 AssocContainerId::TraitId(it) => it,
267 _ => panic!("projection ty without parent trait"),
268 }
269 }
270}
271
272impl TypeWalk for ProjectionTy {
273 fn walk(&self, f: &mut impl FnMut(&Ty)) {
274 self.parameters.walk(f);
275 }
276
277 fn walk_mut_binders(
278 &mut self,
279 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
280 binders: DebruijnIndex,
281 ) {
282 self.parameters.walk_mut_binders(f, binders);
283 }
284}
285
286/// A type.
287///
288/// See also the `TyKind` enum in rustc (librustc/ty/sty.rs), which represents
289/// the same thing (but in a different way).
290///
291/// This should be cheap to clone.
292#[derive(Clone, PartialEq, Eq, Debug, Hash)]
293pub enum Ty {
294 /// A nominal type with (maybe 0) type parameters. This might be a primitive
295 /// type like `bool`, a struct, tuple, function pointer, reference or
296 /// several other things.
297 Apply(ApplicationTy),
298
299 /// A "projection" type corresponds to an (unnormalized)
300 /// projection like `<P0 as Trait<P1..Pn>>::Foo`. Note that the
301 /// trait and all its parameters are fully known.
302 Projection(ProjectionTy),
303
304 /// An opaque type (`impl Trait`).
305 ///
306 /// This is currently only used for return type impl trait; each instance of
307 /// `impl Trait` in a return type gets its own ID.
308 Opaque(OpaqueTy),
309
310 /// A placeholder for a type parameter; for example, `T` in `fn f<T>(x: T)
311 /// {}` when we're type-checking the body of that function. In this
312 /// situation, we know this stands for *some* type, but don't know the exact
313 /// type.
314 Placeholder(TypeParamId),
315
316 /// A bound type variable. This is used in various places: when representing
317 /// some polymorphic type like the type of function `fn f<T>`, the type
318 /// parameters get turned into variables; during trait resolution, inference
319 /// variables get turned into bound variables and back; and in `Dyn` the
320 /// `Self` type is represented with a bound variable as well.
321 Bound(BoundVar),
322
323 /// A type variable used during type checking.
324 Infer(InferTy),
325
326 /// A trait object (`dyn Trait` or bare `Trait` in pre-2018 Rust).
327 ///
328 /// The predicates are quantified over the `Self` type, i.e. `Ty::Bound(0)`
329 /// represents the `Self` type inside the bounds. This is currently
330 /// implicit; Chalk has the `Binders` struct to make it explicit, but it
331 /// didn't seem worth the overhead yet.
332 Dyn(Arc<[GenericPredicate]>),
333
334 /// A placeholder for a type which could not be computed; this is propagated
335 /// to avoid useless error messages. Doubles as a placeholder where type
336 /// variables are inserted before type checking, since we want to try to
337 /// infer a better type here anyway -- for the IDE use case, we want to try
338 /// to infer as much as possible even in the presence of type errors.
339 Unknown,
340}
341
342/// A list of substitutions for generic parameters.
343#[derive(Clone, PartialEq, Eq, Debug, Hash)]
344pub struct Substs(Arc<[Ty]>);
345
346impl TypeWalk for Substs {
347 fn walk(&self, f: &mut impl FnMut(&Ty)) {
348 for t in self.0.iter() {
349 t.walk(f);
350 }
351 }
352
353 fn walk_mut_binders(
354 &mut self,
355 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
356 binders: DebruijnIndex,
357 ) {
358 for t in make_mut_slice(&mut self.0) {
359 t.walk_mut_binders(f, binders);
360 }
361 }
362}
363
364impl Substs {
365 pub fn empty() -> Substs {
366 Substs(Arc::new([]))
367 }
368
369 pub fn single(ty: Ty) -> Substs {
370 Substs(Arc::new([ty]))
371 }
372
373 pub fn prefix(&self, n: usize) -> Substs {
374 Substs(self.0[..std::cmp::min(self.0.len(), n)].into())
375 }
376
377 pub fn suffix(&self, n: usize) -> Substs {
378 Substs(self.0[self.0.len() - std::cmp::min(self.0.len(), n)..].into())
379 }
380
381 pub fn as_single(&self) -> &Ty {
382 if self.0.len() != 1 {
383 panic!("expected substs of len 1, got {:?}", self);
384 }
385 &self.0[0]
386 }
387
388 /// Return Substs that replace each parameter by itself (i.e. `Ty::Param`).
389 pub(crate) fn type_params_for_generics(generic_params: &Generics) -> Substs {
390 Substs(generic_params.iter().map(|(id, _)| Ty::Placeholder(id)).collect())
391 }
392
393 /// Return Substs that replace each parameter by itself (i.e. `Ty::Param`).
394 pub fn type_params(db: &dyn HirDatabase, def: impl Into<GenericDefId>) -> Substs {
395 let params = generics(db.upcast(), def.into());
396 Substs::type_params_for_generics(&params)
397 }
398
399 /// Return Substs that replace each parameter by a bound variable.
400 pub(crate) fn bound_vars(generic_params: &Generics, debruijn: DebruijnIndex) -> Substs {
401 Substs(
402 generic_params
403 .iter()
404 .enumerate()
405 .map(|(idx, _)| Ty::Bound(BoundVar::new(debruijn, idx)))
406 .collect(),
407 )
408 }
409
410 pub fn build_for_def(db: &dyn HirDatabase, def: impl Into<GenericDefId>) -> SubstsBuilder {
411 let def = def.into();
412 let params = generics(db.upcast(), def);
413 let param_count = params.len();
414 Substs::builder(param_count)
415 }
416
417 pub(crate) fn build_for_generics(generic_params: &Generics) -> SubstsBuilder {
418 Substs::builder(generic_params.len())
419 }
420
421 pub fn build_for_type_ctor(db: &dyn HirDatabase, type_ctor: TypeCtor) -> SubstsBuilder {
422 Substs::builder(type_ctor.num_ty_params(db))
423 }
424
425 fn builder(param_count: usize) -> SubstsBuilder {
426 SubstsBuilder { vec: Vec::with_capacity(param_count), param_count }
427 }
428}
429
430/// Return an index of a parameter in the generic type parameter list by it's id.
431pub fn param_idx(db: &dyn HirDatabase, id: TypeParamId) -> Option<usize> {
432 generics(db.upcast(), id.parent).param_idx(id)
433}
434
435#[derive(Debug, Clone)]
436pub struct SubstsBuilder {
437 vec: Vec<Ty>,
438 param_count: usize,
439}
440
441impl SubstsBuilder {
442 pub fn build(self) -> Substs {
443 assert_eq!(self.vec.len(), self.param_count);
444 Substs(self.vec.into())
445 }
446
447 pub fn push(mut self, ty: Ty) -> Self {
448 self.vec.push(ty);
449 self
450 }
451
452 fn remaining(&self) -> usize {
453 self.param_count - self.vec.len()
454 }
455
456 pub fn fill_with_bound_vars(self, debruijn: DebruijnIndex, starting_from: usize) -> Self {
457 self.fill((starting_from..).map(|idx| Ty::Bound(BoundVar::new(debruijn, idx))))
458 }
459
460 pub fn fill_with_unknown(self) -> Self {
461 self.fill(iter::repeat(Ty::Unknown))
462 }
463
464 pub fn fill(mut self, filler: impl Iterator<Item = Ty>) -> Self {
465 self.vec.extend(filler.take(self.remaining()));
466 assert_eq!(self.remaining(), 0);
467 self
468 }
469
470 pub fn use_parent_substs(mut self, parent_substs: &Substs) -> Self {
471 assert!(self.vec.is_empty());
472 assert!(parent_substs.len() <= self.param_count);
473 self.vec.extend(parent_substs.iter().cloned());
474 self
475 }
476}
477
478impl Deref for Substs {
479 type Target = [Ty];
480
481 fn deref(&self) -> &[Ty] {
482 &self.0
483 }
484}
485
486#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
487pub struct Binders<T> {
488 pub num_binders: usize,
489 pub value: T,
490}
491
492impl<T> Binders<T> {
493 pub fn new(num_binders: usize, value: T) -> Self {
494 Self { num_binders, value }
495 }
496
497 pub fn as_ref(&self) -> Binders<&T> {
498 Binders { num_binders: self.num_binders, value: &self.value }
499 }
500
501 pub fn map<U>(self, f: impl FnOnce(T) -> U) -> Binders<U> {
502 Binders { num_binders: self.num_binders, value: f(self.value) }
503 }
504
505 pub fn filter_map<U>(self, f: impl FnOnce(T) -> Option<U>) -> Option<Binders<U>> {
506 Some(Binders { num_binders: self.num_binders, value: f(self.value)? })
507 }
508}
509
510impl<T: Clone> Binders<&T> {
511 pub fn cloned(&self) -> Binders<T> {
512 Binders { num_binders: self.num_binders, value: self.value.clone() }
513 }
514}
515
516impl<T: TypeWalk> Binders<T> {
517 /// Substitutes all variables.
518 pub fn subst(self, subst: &Substs) -> T {
519 assert_eq!(subst.len(), self.num_binders);
520 self.value.subst_bound_vars(subst)
521 }
522
523 /// Substitutes just a prefix of the variables (shifting the rest).
524 pub fn subst_prefix(self, subst: &Substs) -> Binders<T> {
525 assert!(subst.len() < self.num_binders);
526 Binders::new(self.num_binders - subst.len(), self.value.subst_bound_vars(subst))
527 }
528}
529
530impl<T: TypeWalk> TypeWalk for Binders<T> {
531 fn walk(&self, f: &mut impl FnMut(&Ty)) {
532 self.value.walk(f);
533 }
534
535 fn walk_mut_binders(
536 &mut self,
537 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
538 binders: DebruijnIndex,
539 ) {
540 self.value.walk_mut_binders(f, binders.shifted_in())
541 }
542}
543
544/// A trait with type parameters. This includes the `Self`, so this represents a concrete type implementing the trait.
545/// Name to be bikeshedded: TraitBound? TraitImplements?
546#[derive(Clone, PartialEq, Eq, Debug, Hash)]
547pub struct TraitRef {
548 /// FIXME name?
549 pub trait_: TraitId,
550 pub substs: Substs,
551}
552
553impl TraitRef {
554 pub fn self_ty(&self) -> &Ty {
555 &self.substs[0]
556 }
557}
558
559impl TypeWalk for TraitRef {
560 fn walk(&self, f: &mut impl FnMut(&Ty)) {
561 self.substs.walk(f);
562 }
563
564 fn walk_mut_binders(
565 &mut self,
566 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
567 binders: DebruijnIndex,
568 ) {
569 self.substs.walk_mut_binders(f, binders);
570 }
571}
572
573/// Like `generics::WherePredicate`, but with resolved types: A condition on the
574/// parameters of a generic item.
575#[derive(Debug, Clone, PartialEq, Eq, Hash)]
576pub enum GenericPredicate {
577 /// The given trait needs to be implemented for its type parameters.
578 Implemented(TraitRef),
579 /// An associated type bindings like in `Iterator<Item = T>`.
580 Projection(ProjectionPredicate),
581 /// We couldn't resolve the trait reference. (If some type parameters can't
582 /// be resolved, they will just be Unknown).
583 Error,
584}
585
586impl GenericPredicate {
587 pub fn is_error(&self) -> bool {
588 matches!(self, GenericPredicate::Error)
589 }
590
591 pub fn is_implemented(&self) -> bool {
592 matches!(self, GenericPredicate::Implemented(_))
593 }
594
595 pub fn trait_ref(&self, db: &dyn HirDatabase) -> Option<TraitRef> {
596 match self {
597 GenericPredicate::Implemented(tr) => Some(tr.clone()),
598 GenericPredicate::Projection(proj) => Some(proj.projection_ty.trait_ref(db)),
599 GenericPredicate::Error => None,
600 }
601 }
602}
603
604impl TypeWalk for GenericPredicate {
605 fn walk(&self, f: &mut impl FnMut(&Ty)) {
606 match self {
607 GenericPredicate::Implemented(trait_ref) => trait_ref.walk(f),
608 GenericPredicate::Projection(projection_pred) => projection_pred.walk(f),
609 GenericPredicate::Error => {}
610 }
611 }
612
613 fn walk_mut_binders(
614 &mut self,
615 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
616 binders: DebruijnIndex,
617 ) {
618 match self {
619 GenericPredicate::Implemented(trait_ref) => trait_ref.walk_mut_binders(f, binders),
620 GenericPredicate::Projection(projection_pred) => {
621 projection_pred.walk_mut_binders(f, binders)
622 }
623 GenericPredicate::Error => {}
624 }
625 }
626}
627
628/// Basically a claim (currently not validated / checked) that the contained
629/// type / trait ref contains no inference variables; any inference variables it
630/// contained have been replaced by bound variables, and `kinds` tells us how
631/// many there are and whether they were normal or float/int variables. This is
632/// used to erase irrelevant differences between types before using them in
633/// queries.
634#[derive(Debug, Clone, PartialEq, Eq, Hash)]
635pub struct Canonical<T> {
636 pub value: T,
637 pub kinds: Arc<[TyKind]>,
638}
639
640impl<T> Canonical<T> {
641 pub fn new(value: T, kinds: impl IntoIterator<Item = TyKind>) -> Self {
642 Self { value, kinds: kinds.into_iter().collect() }
643 }
644}
645
646#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
647pub enum TyKind {
648 General,
649 Integer,
650 Float,
651}
652
653/// A function signature as seen by type inference: Several parameter types and
654/// one return type.
655#[derive(Clone, PartialEq, Eq, Debug)]
656pub struct FnSig {
657 params_and_return: Arc<[Ty]>,
658 is_varargs: bool,
659}
660
661/// A polymorphic function signature.
662pub type PolyFnSig = Binders<FnSig>;
663
664impl FnSig {
665 pub fn from_params_and_return(mut params: Vec<Ty>, ret: Ty, is_varargs: bool) -> FnSig {
666 params.push(ret);
667 FnSig { params_and_return: params.into(), is_varargs }
668 }
669
670 pub fn from_fn_ptr_substs(substs: &Substs, is_varargs: bool) -> FnSig {
671 FnSig { params_and_return: Arc::clone(&substs.0), is_varargs }
672 }
673
674 pub fn params(&self) -> &[Ty] {
675 &self.params_and_return[0..self.params_and_return.len() - 1]
676 }
677
678 pub fn ret(&self) -> &Ty {
679 &self.params_and_return[self.params_and_return.len() - 1]
680 }
681}
682
683impl TypeWalk for FnSig {
684 fn walk(&self, f: &mut impl FnMut(&Ty)) {
685 for t in self.params_and_return.iter() {
686 t.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 for t in make_mut_slice(&mut self.params_and_return) {
696 t.walk_mut_binders(f, binders);
697 }
698 }
699}
700
701impl Ty {
702 pub fn simple(ctor: TypeCtor) -> Ty {
703 Ty::Apply(ApplicationTy { ctor, parameters: Substs::empty() })
704 }
705 pub fn apply_one(ctor: TypeCtor, param: Ty) -> Ty {
706 Ty::Apply(ApplicationTy { ctor, parameters: Substs::single(param) })
707 }
708 pub fn apply(ctor: TypeCtor, parameters: Substs) -> Ty {
709 Ty::Apply(ApplicationTy { ctor, parameters })
710 }
711 pub fn unit() -> Self {
712 Ty::apply(TypeCtor::Tuple { cardinality: 0 }, Substs::empty())
713 }
714 pub fn fn_ptr(sig: FnSig) -> Self {
715 Ty::apply(
716 TypeCtor::FnPtr { num_args: sig.params().len() as u16, is_varargs: sig.is_varargs },
717 Substs(sig.params_and_return),
718 )
719 }
720
721 pub fn as_reference(&self) -> Option<(&Ty, Mutability)> {
722 match self {
723 Ty::Apply(ApplicationTy { ctor: TypeCtor::Ref(mutability), parameters }) => {
724 Some((parameters.as_single(), *mutability))
725 }
726 _ => None,
727 }
728 }
729
730 pub fn as_reference_or_ptr(&self) -> Option<(&Ty, Rawness, Mutability)> {
731 match self {
732 Ty::Apply(ApplicationTy { ctor: TypeCtor::Ref(mutability), parameters }) => {
733 Some((parameters.as_single(), Rawness::Ref, *mutability))
734 }
735 Ty::Apply(ApplicationTy { ctor: TypeCtor::RawPtr(mutability), parameters }) => {
736 Some((parameters.as_single(), Rawness::RawPtr, *mutability))
737 }
738 _ => None,
739 }
740 }
741
742 pub fn strip_references(&self) -> &Ty {
743 let mut t: &Ty = self;
744
745 while let Ty::Apply(ApplicationTy { ctor: TypeCtor::Ref(_mutability), parameters }) = t {
746 t = parameters.as_single();
747 }
748
749 t
750 }
751
752 pub fn as_adt(&self) -> Option<(AdtId, &Substs)> {
753 match self {
754 Ty::Apply(ApplicationTy { ctor: TypeCtor::Adt(adt_def), parameters }) => {
755 Some((*adt_def, parameters))
756 }
757 _ => None,
758 }
759 }
760
761 pub fn as_tuple(&self) -> Option<&Substs> {
762 match self {
763 Ty::Apply(ApplicationTy { ctor: TypeCtor::Tuple { .. }, parameters }) => {
764 Some(parameters)
765 }
766 _ => None,
767 }
768 }
769
770 pub fn is_never(&self) -> bool {
771 matches!(self, Ty::Apply(ApplicationTy { ctor: TypeCtor::Never, .. }))
772 }
773
774 /// If this is a `dyn Trait` type, this returns the `Trait` part.
775 pub fn dyn_trait_ref(&self) -> Option<&TraitRef> {
776 match self {
777 Ty::Dyn(bounds) => bounds.get(0).and_then(|b| match b {
778 GenericPredicate::Implemented(trait_ref) => Some(trait_ref),
779 _ => None,
780 }),
781 _ => None,
782 }
783 }
784
785 /// If this is a `dyn Trait`, returns that trait.
786 pub fn dyn_trait(&self) -> Option<TraitId> {
787 self.dyn_trait_ref().map(|it| it.trait_)
788 }
789
790 fn builtin_deref(&self) -> Option<Ty> {
791 match self {
792 Ty::Apply(a_ty) => match a_ty.ctor {
793 TypeCtor::Ref(..) => Some(Ty::clone(a_ty.parameters.as_single())),
794 TypeCtor::RawPtr(..) => Some(Ty::clone(a_ty.parameters.as_single())),
795 _ => None,
796 },
797 _ => None,
798 }
799 }
800
801 pub fn callable_sig(&self, db: &dyn HirDatabase) -> Option<FnSig> {
802 match self {
803 Ty::Apply(a_ty) => match a_ty.ctor {
804 TypeCtor::FnPtr { is_varargs, .. } => {
805 Some(FnSig::from_fn_ptr_substs(&a_ty.parameters, is_varargs))
806 }
807 TypeCtor::FnDef(def) => {
808 let sig = db.callable_item_signature(def);
809 Some(sig.subst(&a_ty.parameters))
810 }
811 TypeCtor::Closure { .. } => {
812 let sig_param = &a_ty.parameters[0];
813 sig_param.callable_sig(db)
814 }
815 _ => None,
816 },
817 _ => None,
818 }
819 }
820
821 /// If this is a type with type parameters (an ADT or function), replaces
822 /// the `Substs` for these type parameters with the given ones. (So e.g. if
823 /// `self` is `Option<_>` and the substs contain `u32`, we'll have
824 /// `Option<u32>` afterwards.)
825 pub fn apply_substs(self, substs: Substs) -> Ty {
826 match self {
827 Ty::Apply(ApplicationTy { ctor, parameters: previous_substs }) => {
828 assert_eq!(previous_substs.len(), substs.len());
829 Ty::Apply(ApplicationTy { ctor, parameters: substs })
830 }
831 _ => self,
832 }
833 }
834
835 /// Returns the type parameters of this type if it has some (i.e. is an ADT
836 /// or function); so if `self` is `Option<u32>`, this returns the `u32`.
837 pub fn substs(&self) -> Option<Substs> {
838 match self {
839 Ty::Apply(ApplicationTy { parameters, .. }) => Some(parameters.clone()),
840 _ => None,
841 }
842 }
843
844 pub fn impl_trait_bounds(&self, db: &dyn HirDatabase) -> Option<Vec<GenericPredicate>> {
845 match self {
846 Ty::Opaque(opaque_ty) => {
847 let predicates = match opaque_ty.opaque_ty_id {
848 OpaqueTyId::ReturnTypeImplTrait(func, idx) => {
849 db.return_type_impl_traits(func).map(|it| {
850 let data = (*it)
851 .as_ref()
852 .map(|rpit| rpit.impl_traits[idx as usize].bounds.clone());
853 data.subst(&opaque_ty.parameters)
854 })
855 }
856 };
857
858 predicates.map(|it| it.value)
859 }
860 Ty::Placeholder(id) => {
861 let generic_params = db.generic_params(id.parent);
862 let param_data = &generic_params.types[id.local_id];
863 match param_data.provenance {
864 hir_def::generics::TypeParamProvenance::ArgumentImplTrait => {
865 let predicates = db
866 .generic_predicates_for_param(*id)
867 .into_iter()
868 .map(|pred| pred.value.clone())
869 .collect_vec();
870
871 Some(predicates)
872 }
873 _ => None,
874 }
875 }
876 _ => None,
877 }
878 }
879
880 pub fn associated_type_parent_trait(&self, db: &dyn HirDatabase) -> Option<TraitId> {
881 match self {
882 Ty::Apply(ApplicationTy { ctor: TypeCtor::AssociatedType(type_alias_id), .. }) => {
883 match type_alias_id.lookup(db.upcast()).container {
884 AssocContainerId::TraitId(trait_id) => Some(trait_id),
885 _ => None,
886 }
887 }
888 Ty::Projection(projection_ty) => {
889 match projection_ty.associated_ty.lookup(db.upcast()).container {
890 AssocContainerId::TraitId(trait_id) => Some(trait_id),
891 _ => None,
892 }
893 }
894 _ => None,
895 }
896 }
897}
898
899/// This allows walking structures that contain types to do something with those
900/// types, similar to Chalk's `Fold` trait.
901pub trait TypeWalk {
902 fn walk(&self, f: &mut impl FnMut(&Ty));
903 fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
904 self.walk_mut_binders(&mut |ty, _binders| f(ty), DebruijnIndex::INNERMOST);
905 }
906 /// Walk the type, counting entered binders.
907 ///
908 /// `Ty::Bound` variables use DeBruijn indexing, which means that 0 refers
909 /// to the innermost binder, 1 to the next, etc.. So when we want to
910 /// substitute a certain bound variable, we can't just walk the whole type
911 /// and blindly replace each instance of a certain index; when we 'enter'
912 /// things that introduce new bound variables, we have to keep track of
913 /// that. Currently, the only thing that introduces bound variables on our
914 /// side are `Ty::Dyn` and `Ty::Opaque`, which each introduce a bound
915 /// variable for the self type.
916 fn walk_mut_binders(
917 &mut self,
918 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
919 binders: DebruijnIndex,
920 );
921
922 fn fold_binders(
923 mut self,
924 f: &mut impl FnMut(Ty, DebruijnIndex) -> Ty,
925 binders: DebruijnIndex,
926 ) -> Self
927 where
928 Self: Sized,
929 {
930 self.walk_mut_binders(
931 &mut |ty_mut, binders| {
932 let ty = mem::replace(ty_mut, Ty::Unknown);
933 *ty_mut = f(ty, binders);
934 },
935 binders,
936 );
937 self
938 }
939
940 fn fold(mut self, f: &mut impl FnMut(Ty) -> Ty) -> Self
941 where
942 Self: Sized,
943 {
944 self.walk_mut(&mut |ty_mut| {
945 let ty = mem::replace(ty_mut, Ty::Unknown);
946 *ty_mut = f(ty);
947 });
948 self
949 }
950
951 /// Substitutes `Ty::Bound` vars with the given substitution.
952 fn subst_bound_vars(self, substs: &Substs) -> Self
953 where
954 Self: Sized,
955 {
956 self.subst_bound_vars_at_depth(substs, DebruijnIndex::INNERMOST)
957 }
958
959 /// Substitutes `Ty::Bound` vars with the given substitution.
960 fn subst_bound_vars_at_depth(mut self, substs: &Substs, depth: DebruijnIndex) -> Self
961 where
962 Self: Sized,
963 {
964 self.walk_mut_binders(
965 &mut |ty, binders| {
966 if let &mut Ty::Bound(bound) = ty {
967 if bound.debruijn >= binders {
968 *ty = substs.0[bound.index].clone().shift_bound_vars(binders);
969 }
970 }
971 },
972 depth,
973 );
974 self
975 }
976
977 /// Shifts up debruijn indices of `Ty::Bound` vars by `n`.
978 fn shift_bound_vars(self, n: DebruijnIndex) -> Self
979 where
980 Self: Sized,
981 {
982 self.fold_binders(
983 &mut |ty, binders| match ty {
984 Ty::Bound(bound) if bound.debruijn >= binders => {
985 Ty::Bound(bound.shifted_in_from(n))
986 }
987 ty => ty,
988 },
989 DebruijnIndex::INNERMOST,
990 )
991 }
992}
993
994impl TypeWalk for Ty {
995 fn walk(&self, f: &mut impl FnMut(&Ty)) {
996 match self {
997 Ty::Apply(a_ty) => {
998 for t in a_ty.parameters.iter() {
999 t.walk(f);
1000 }
1001 }
1002 Ty::Projection(p_ty) => {
1003 for t in p_ty.parameters.iter() {
1004 t.walk(f);
1005 }
1006 }
1007 Ty::Dyn(predicates) => {
1008 for p in predicates.iter() {
1009 p.walk(f);
1010 }
1011 }
1012 Ty::Opaque(o_ty) => {
1013 for t in o_ty.parameters.iter() {
1014 t.walk(f);
1015 }
1016 }
1017 Ty::Placeholder { .. } | Ty::Bound(_) | Ty::Infer(_) | Ty::Unknown => {}
1018 }
1019 f(self);
1020 }
1021
1022 fn walk_mut_binders(
1023 &mut self,
1024 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
1025 binders: DebruijnIndex,
1026 ) {
1027 match self {
1028 Ty::Apply(a_ty) => {
1029 a_ty.parameters.walk_mut_binders(f, binders);
1030 }
1031 Ty::Projection(p_ty) => {
1032 p_ty.parameters.walk_mut_binders(f, binders);
1033 }
1034 Ty::Dyn(predicates) => {
1035 for p in make_mut_slice(predicates) {
1036 p.walk_mut_binders(f, binders.shifted_in());
1037 }
1038 }
1039 Ty::Opaque(o_ty) => {
1040 o_ty.parameters.walk_mut_binders(f, binders);
1041 }
1042 Ty::Placeholder { .. } | Ty::Bound(_) | Ty::Infer(_) | Ty::Unknown => {}
1043 }
1044 f(self, binders);
1045 }
1046}
1047
1048impl<T: TypeWalk> TypeWalk for Vec<T> {
1049 fn walk(&self, f: &mut impl FnMut(&Ty)) {
1050 for t in self {
1051 t.walk(f);
1052 }
1053 }
1054 fn walk_mut_binders(
1055 &mut self,
1056 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
1057 binders: DebruijnIndex,
1058 ) {
1059 for t in self {
1060 t.walk_mut_binders(f, binders);
1061 }
1062 }
1063}
1064
1065#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
1066pub enum OpaqueTyId {
1067 ReturnTypeImplTrait(hir_def::FunctionId, u16),
1068}
1069
1070#[derive(Clone, PartialEq, Eq, Debug, Hash)]
1071pub struct ReturnTypeImplTraits {
1072 pub(crate) impl_traits: Vec<ReturnTypeImplTrait>,
1073}
1074
1075#[derive(Clone, PartialEq, Eq, Debug, Hash)]
1076pub(crate) struct ReturnTypeImplTrait {
1077 pub bounds: Binders<Vec<GenericPredicate>>,
1078}