crates/hir_ty/src/types.rs

   1 //! This is the home of `Ty` etc. until they get replaced by their chalk_ir
   2 //! equivalents.
   3
   4 use std::sync::Arc;
   5
   6 use chalk_ir::{
   7     cast::{CastTo, Caster},
   8     BoundVar, Mutability, Scalar, TyVariableKind,
   9 };
  10 use hir_def::LifetimeParamId;
  11 use smallvec::SmallVec;
  12
  13 use crate::{
  14     AssocTypeId, CanonicalVarKinds, ChalkTraitId, ClosureId, FnDefId, FnSig, ForeignDefId,
  15     InferenceVar, Interner, OpaqueTyId, PlaceholderIndex,
  16 };
  17
  18 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
  19 pub enum Lifetime {
  20     Parameter(LifetimeParamId),
  21     Static,
  22 }
  23
  24 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
  25 pub struct OpaqueTy {
  26     pub opaque_ty_id: OpaqueTyId,
  27     pub substitution: Substitution,
  28 }
  29
  30 /// A "projection" type corresponds to an (unnormalized)
  31 /// projection like `<P0 as Trait<P1..Pn>>::Foo`. Note that the
  32 /// trait and all its parameters are fully known.
  33 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
  34 pub struct ProjectionTy {
  35     pub associated_ty_id: AssocTypeId,
  36     pub substitution: Substitution,
  37 }
  38
  39 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
  40 pub struct DynTy {
  41     /// The unknown self type.
  42     pub bounds: Binders<QuantifiedWhereClauses>,
  43 }
  44
  45 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
  46 pub struct FnPointer {
  47     pub num_args: usize,
  48     pub sig: FnSig,
  49     pub substs: Substitution,
  50 }
  51
  52 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
  53 pub enum AliasTy {
  54     /// A "projection" type corresponds to an (unnormalized)
  55     /// projection like `<P0 as Trait<P1..Pn>>::Foo`. Note that the
  56     /// trait and all its parameters are fully known.
  57     Projection(ProjectionTy),
  58     /// An opaque type (`impl Trait`).
  59     ///
  60     /// This is currently only used for return type impl trait; each instance of
  61     /// `impl Trait` in a return type gets its own ID.
  62     Opaque(OpaqueTy),
  63 }
  64
  65 /// A type.
  66 ///
  67 /// See also the `TyKind` enum in rustc (librustc/ty/sty.rs), which represents
  68 /// the same thing (but in a different way).
  69 ///
  70 /// This should be cheap to clone.
  71 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
  72 pub enum TyKind {
  73     /// Structures, enumerations and unions.
  74     Adt(chalk_ir::AdtId<Interner>, Substitution),
  75
  76     /// Represents an associated item like `Iterator::Item`.  This is used
  77     /// when we have tried to normalize a projection like `T::Item` but
  78     /// couldn't find a better representation.  In that case, we generate
  79     /// an **application type** like `(Iterator::Item)<T>`.
  80     AssociatedType(AssocTypeId, Substitution),
  81
  82     /// a scalar type like `bool` or `u32`
  83     Scalar(Scalar),
  84
  85     /// A tuple type.  For example, `(i32, bool)`.
  86     Tuple(usize, Substitution),
  87
  88     /// An array with the given length. Written as `[T; n]`.
  89     Array(Ty),
  90
  91     /// The pointee of an array slice.  Written as `[T]`.
  92     Slice(Ty),
  93
  94     /// A raw pointer. Written as `*mut T` or `*const T`
  95     Raw(Mutability, Ty),
  96
  97     /// A reference; a pointer with an associated lifetime. Written as
  98     /// `&'a mut T` or `&'a T`.
  99     Ref(Mutability, Ty),
 100
 101     /// This represents a placeholder for an opaque type in situations where we
 102     /// don't know the hidden type (i.e. currently almost always). This is
 103     /// analogous to the `AssociatedType` type constructor.
 104     /// It is also used as the type of async block, with one type parameter
 105     /// representing the Future::Output type.
 106     OpaqueType(OpaqueTyId, Substitution),
 107
 108     /// The anonymous type of a function declaration/definition. Each
 109     /// function has a unique type, which is output (for a function
 110     /// named `foo` returning an `i32`) as `fn() -> i32 {foo}`.
 111     ///
 112     /// This includes tuple struct / enum variant constructors as well.
 113     ///
 114     /// For example the type of `bar` here:
 115     ///
 116     /// ```
 117     /// fn foo() -> i32 { 1 }
 118     /// let bar = foo; // bar: fn() -> i32 {foo}
 119     /// ```
 120     FnDef(FnDefId, Substitution),
 121
 122     /// The pointee of a string slice. Written as `str`.
 123     Str,
 124
 125     /// The never type `!`.
 126     Never,
 127
 128     /// The type of a specific closure.
 129     ///
 130     /// The closure signature is stored in a `FnPtr` type in the first type
 131     /// parameter.
 132     Closure(ClosureId, Substitution),
 133
 134     /// Represents a foreign type declared in external blocks.
 135     Foreign(ForeignDefId),
 136
 137     /// A pointer to a function.  Written as `fn() -> i32`.
 138     ///
 139     /// For example the type of `bar` here:
 140     ///
 141     /// ```
 142     /// fn foo() -> i32 { 1 }
 143     /// let bar: fn() -> i32 = foo;
 144     /// ```
 145     Function(FnPointer),
 146
 147     /// An "alias" type represents some form of type alias, such as:
 148     /// - An associated type projection like `<T as Iterator>::Item`
 149     /// - `impl Trait` types
 150     /// - Named type aliases like `type Foo<X> = Vec<X>`
 151     Alias(AliasTy),
 152
 153     /// A placeholder for a type parameter; for example, `T` in `fn f<T>(x: T)
 154     /// {}` when we're type-checking the body of that function. In this
 155     /// situation, we know this stands for *some* type, but don't know the exact
 156     /// type.
 157     Placeholder(PlaceholderIndex),
 158
 159     /// A bound type variable. This is used in various places: when representing
 160     /// some polymorphic type like the type of function `fn f<T>`, the type
 161     /// parameters get turned into variables; during trait resolution, inference
 162     /// variables get turned into bound variables and back; and in `Dyn` the
 163     /// `Self` type is represented with a bound variable as well.
 164     BoundVar(BoundVar),
 165
 166     /// A type variable used during type checking.
 167     InferenceVar(InferenceVar, TyVariableKind),
 168
 169     /// A trait object (`dyn Trait` or bare `Trait` in pre-2018 Rust).
 170     ///
 171     /// The predicates are quantified over the `Self` type, i.e. `Ty::Bound(0)`
 172     /// represents the `Self` type inside the bounds. This is currently
 173     /// implicit; Chalk has the `Binders` struct to make it explicit, but it
 174     /// didn't seem worth the overhead yet.
 175     Dyn(DynTy),
 176
 177     /// A placeholder for a type which could not be computed; this is propagated
 178     /// to avoid useless error messages. Doubles as a placeholder where type
 179     /// variables are inserted before type checking, since we want to try to
 180     /// infer a better type here anyway -- for the IDE use case, we want to try
 181     /// to infer as much as possible even in the presence of type errors.
 182     Error,
 183 }
 184
 185 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 186 pub struct Ty(Arc<TyKind>);
 187
 188 impl TyKind {
 189     pub fn intern(self, _interner: &Interner) -> Ty {
 190         Ty(Arc::new(self))
 191     }
 192 }
 193
 194 impl Ty {
 195     pub fn kind(&self, _interner: &Interner) -> &TyKind {
 196         &self.0
 197     }
 198
 199     pub fn interned_mut(&mut self) -> &mut TyKind {
 200         Arc::make_mut(&mut self.0)
 201     }
 202
 203     pub fn into_inner(self) -> TyKind {
 204         Arc::try_unwrap(self.0).unwrap_or_else(|a| (*a).clone())
 205     }
 206 }
 207
 208 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 209 pub struct GenericArg {
 210     interned: GenericArgData,
 211 }
 212
 213 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 214 pub enum GenericArgData {
 215     Ty(Ty),
 216 }
 217
 218 impl GenericArg {
 219     /// Constructs a generic argument using `GenericArgData`.
 220     pub fn new(_interner: &Interner, data: GenericArgData) -> Self {
 221         GenericArg { interned: data }
 222     }
 223
 224     /// Gets the interned value.
 225     pub fn interned(&self) -> &GenericArgData {
 226         &self.interned
 227     }
 228
 229     /// Asserts that this is a type argument.
 230     pub fn assert_ty_ref(&self, interner: &Interner) -> &Ty {
 231         self.ty(interner).unwrap()
 232     }
 233
 234     /// Checks whether the generic argument is a type.
 235     pub fn is_ty(&self, _interner: &Interner) -> bool {
 236         match self.interned() {
 237             GenericArgData::Ty(_) => true,
 238         }
 239     }
 240
 241     /// Returns the type if it is one, `None` otherwise.
 242     pub fn ty(&self, _interner: &Interner) -> Option<&Ty> {
 243         match self.interned() {
 244             GenericArgData::Ty(t) => Some(t),
 245         }
 246     }
 247
 248     pub fn interned_mut(&mut self) -> &mut GenericArgData {
 249         &mut self.interned
 250     }
 251 }
 252
 253 /// A list of substitutions for generic parameters.
 254 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 255 pub struct Substitution(SmallVec<[GenericArg; 2]>);
 256
 257 impl Substitution {
 258     pub fn interned(&self) -> &[GenericArg] {
 259         &self.0
 260     }
 261
 262     pub fn len(&self, _: &Interner) -> usize {
 263         self.0.len()
 264     }
 265
 266     pub fn is_empty(&self, _: &Interner) -> bool {
 267         self.0.is_empty()
 268     }
 269
 270     pub fn at(&self, _: &Interner, i: usize) -> &GenericArg {
 271         &self.0[i]
 272     }
 273
 274     pub fn empty(_: &Interner) -> Substitution {
 275         Substitution(SmallVec::new())
 276     }
 277
 278     pub fn iter(&self, _: &Interner) -> std::slice::Iter<'_, GenericArg> {
 279         self.0.iter()
 280     }
 281
 282     pub fn from_iter(
 283         interner: &Interner,
 284         elements: impl IntoIterator<Item = impl CastTo<GenericArg>>,
 285     ) -> Self {
 286         Substitution(elements.into_iter().casted(interner).collect())
 287     }
 288
 289     // We can hopefully add this to Chalk
 290     pub fn intern(interned: SmallVec<[GenericArg; 2]>) -> Substitution {
 291         Substitution(interned)
 292     }
 293
 294     pub fn interned_mut(&mut self) -> &mut SmallVec<[GenericArg; 2]> {
 295         &mut self.0
 296     }
 297 }
 298
 299 #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
 300 pub struct Binders<T> {
 301     pub num_binders: usize,
 302     pub value: T,
 303 }
 304
 305 /// A trait with type parameters. This includes the `Self`, so this represents a concrete type implementing the trait.
 306 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 307 pub struct TraitRef {
 308     pub trait_id: ChalkTraitId,
 309     pub substitution: Substitution,
 310 }
 311
 312 /// Like `generics::WherePredicate`, but with resolved types: A condition on the
 313 /// parameters of a generic item.
 314 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
 315 pub enum WhereClause {
 316     /// The given trait needs to be implemented for its type parameters.
 317     Implemented(TraitRef),
 318     /// An associated type bindings like in `Iterator<Item = T>`.
 319     AliasEq(AliasEq),
 320 }
 321
 322 pub type QuantifiedWhereClause = Binders<WhereClause>;
 323
 324 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
 325 pub struct QuantifiedWhereClauses(Arc<[QuantifiedWhereClause]>);
 326
 327 impl QuantifiedWhereClauses {
 328     pub fn from_iter(
 329         _interner: &Interner,
 330         elements: impl IntoIterator<Item = QuantifiedWhereClause>,
 331     ) -> Self {
 332         QuantifiedWhereClauses(elements.into_iter().collect())
 333     }
 334
 335     pub fn interned(&self) -> &Arc<[QuantifiedWhereClause]> {
 336         &self.0
 337     }
 338
 339     pub fn interned_mut(&mut self) -> &mut Arc<[QuantifiedWhereClause]> {
 340         &mut self.0
 341     }
 342 }
 343
 344 /// Basically a claim (currently not validated / checked) that the contained
 345 /// type / trait ref contains no inference variables; any inference variables it
 346 /// contained have been replaced by bound variables, and `kinds` tells us how
 347 /// many there are and whether they were normal or float/int variables. This is
 348 /// used to erase irrelevant differences between types before using them in
 349 /// queries.
 350 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
 351 pub struct Canonical<T> {
 352     pub value: T,
 353     pub binders: CanonicalVarKinds,
 354 }
 355
 356 /// Something (usually a goal), along with an environment.
 357 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
 358 pub struct InEnvironment<T> {
 359     pub environment: chalk_ir::Environment<Interner>,
 360     pub goal: T,
 361 }
 362
 363 impl<T> InEnvironment<T> {
 364     pub fn new(environment: chalk_ir::Environment<Interner>, value: T) -> InEnvironment<T> {
 365         InEnvironment { environment, goal: value }
 366     }
 367 }
 368
 369 /// Something that needs to be proven (by Chalk) during type checking, e.g. that
 370 /// a certain type implements a certain trait. Proving the Obligation might
 371 /// result in additional information about inference variables.
 372 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
 373 pub enum DomainGoal {
 374     Holds(WhereClause),
 375 }
 376
 377 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
 378 pub struct AliasEq {
 379     pub alias: AliasTy,
 380     pub ty: Ty,
 381 }
 382
 383 #[derive(Clone, Debug, PartialEq, Eq)]
 384 pub struct SolutionVariables(pub Canonical<Substitution>);
 385
 386 #[derive(Clone, Debug, PartialEq, Eq)]
 387 /// A (possible) solution for a proposed goal.
 388 pub enum Solution {
 389     /// The goal indeed holds, and there is a unique value for all existential
 390     /// variables.
 391     Unique(SolutionVariables),
 392
 393     /// The goal may be provable in multiple ways, but regardless we may have some guidance
 394     /// for type inference. In this case, we don't return any lifetime
 395     /// constraints, since we have not "committed" to any particular solution
 396     /// yet.
 397     Ambig(Guidance),
 398 }
 399
 400 #[derive(Clone, Debug, PartialEq, Eq)]
 401 /// When a goal holds ambiguously (e.g., because there are multiple possible
 402 /// solutions), we issue a set of *guidance* back to type inference.
 403 pub enum Guidance {
 404     /// The existential variables *must* have the given values if the goal is
 405     /// ever to hold, but that alone isn't enough to guarantee the goal will
 406     /// actually hold.
 407     Definite(SolutionVariables),
 408
 409     /// There are multiple plausible values for the existentials, but the ones
 410     /// here are suggested as the preferred choice heuristically. These should
 411     /// be used for inference fallback only.
 412     Suggested(SolutionVariables),
 413
 414     /// There's no useful information to feed back to type inference
 415     Unknown,
 416 }