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