crates/ra_hir/src/ty.rs

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