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