vendor/chalk-solve-0.55.0/src/rust_ir.rs

   1 //! Contains the definition for the "Rust IR" -- this is basically a "lowered"
   2 //! version of the AST, roughly corresponding to [the HIR] in the Rust
   3 //! compiler.
   4
   5 use chalk_derive::{Fold, HasInterner, Visit};
   6 use chalk_ir::cast::Cast;
   7 use chalk_ir::fold::shift::Shift;
   8 use chalk_ir::interner::Interner;
   9 use chalk_ir::{
  10     try_break,
  11     visit::{ControlFlow, Visit},
  12     AdtId, AliasEq, AliasTy, AssocTypeId, Binders, DebruijnIndex, FnDefId, GenericArg, ImplId,
  13     OpaqueTyId, ProjectionTy, QuantifiedWhereClause, Substitution, ToGenericArg, TraitId, TraitRef,
  14     Ty, TyKind, VariableKind, WhereClause, WithKind,
  15 };
  16 use std::iter;
  17
  18 /// Identifier for an "associated type value" found in some impl.
  19 #[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
  20 pub struct AssociatedTyValueId<I: Interner>(pub I::DefId);
  21
  22 chalk_ir::id_visit!(AssociatedTyValueId);
  23 chalk_ir::id_fold!(AssociatedTyValueId);
  24
  25 #[derive(Clone, Debug, PartialEq, Eq, Hash, Visit)]
  26 pub struct ImplDatum<I: Interner> {
  27     pub polarity: Polarity,
  28     pub binders: Binders<ImplDatumBound<I>>,
  29     pub impl_type: ImplType,
  30     pub associated_ty_value_ids: Vec<AssociatedTyValueId<I>>,
  31 }
  32
  33 impl<I: Interner> ImplDatum<I> {
  34     pub fn is_positive(&self) -> bool {
  35         self.polarity.is_positive()
  36     }
  37
  38     pub fn trait_id(&self) -> TraitId<I> {
  39         self.binders.skip_binders().trait_ref.trait_id
  40     }
  41
  42     pub fn self_type_adt_id(&self, interner: &I) -> Option<AdtId<I>> {
  43         match self
  44             .binders
  45             .skip_binders()
  46             .trait_ref
  47             .self_type_parameter(interner)
  48             .kind(interner)
  49         {
  50             TyKind::Adt(id, _) => Some(*id),
  51             _ => None,
  52         }
  53     }
  54 }
  55
  56 #[derive(Clone, Debug, PartialEq, Eq, Hash, HasInterner, Fold, Visit)]
  57 pub struct ImplDatumBound<I: Interner> {
  58     pub trait_ref: TraitRef<I>,
  59     pub where_clauses: Vec<QuantifiedWhereClause<I>>,
  60 }
  61
  62 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
  63 pub enum ImplType {
  64     Local,
  65     External,
  66 }
  67
  68 chalk_ir::const_visit!(ImplType);
  69
  70 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
  71 pub struct DefaultImplDatum<I: Interner> {
  72     pub binders: Binders<DefaultImplDatumBound<I>>,
  73 }
  74
  75 #[derive(Clone, Debug, PartialEq, Eq, Hash, HasInterner)]
  76 pub struct DefaultImplDatumBound<I: Interner> {
  77     pub trait_ref: TraitRef<I>,
  78     pub accessible_tys: Vec<Ty<I>>,
  79 }
  80
  81 #[derive(Clone, Debug, PartialEq, Eq, Hash, Visit)]
  82 pub struct AdtDatum<I: Interner> {
  83     pub binders: Binders<AdtDatumBound<I>>,
  84     pub id: AdtId<I>,
  85     pub flags: AdtFlags,
  86     pub kind: AdtKind,
  87 }
  88
  89 #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
  90 pub enum AdtKind {
  91     Struct,
  92     Enum,
  93     Union,
  94 }
  95
  96 chalk_ir::const_visit!(AdtKind);
  97
  98 #[derive(Clone, Debug, PartialEq, Eq, Hash, Fold, HasInterner, Visit)]
  99 pub struct AdtDatumBound<I: Interner> {
 100     pub variants: Vec<AdtVariantDatum<I>>,
 101     pub where_clauses: Vec<QuantifiedWhereClause<I>>,
 102 }
 103
 104 #[derive(Clone, Debug, PartialEq, Eq, Hash, Fold, HasInterner, Visit)]
 105 pub struct AdtVariantDatum<I: Interner> {
 106     pub fields: Vec<Ty<I>>,
 107 }
 108
 109 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
 110 pub struct AdtFlags {
 111     pub upstream: bool,
 112     pub fundamental: bool,
 113     pub phantom_data: bool,
 114 }
 115
 116 chalk_ir::const_visit!(AdtFlags);
 117
 118 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
 119 pub struct AdtRepr<I: Interner> {
 120     pub c: bool,
 121     pub packed: bool,
 122     pub int: Option<chalk_ir::Ty<I>>,
 123 }
 124
 125 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
 126 /// A rust intermediate represention (rust_ir) of a function definition/declaration.
 127 /// For example, in the following rust code:
 128 ///
 129 /// ```ignore
 130 /// fn foo<T>() -> i32 where T: Eq;
 131 /// ```
 132 ///
 133 /// This would represent the declaration of `foo`.
 134 ///
 135 /// Note this is distinct from a function pointer, which points to
 136 /// a function with a given type signature, whereas this represents
 137 /// a specific function definition.
 138 pub struct FnDefDatum<I: Interner> {
 139     pub id: FnDefId<I>,
 140     pub sig: chalk_ir::FnSig<I>,
 141     pub binders: Binders<FnDefDatumBound<I>>,
 142 }
 143
 144 /// Avoids visiting `I::FnAbi`
 145 impl<I: Interner> Visit<I> for FnDefDatum<I> {
 146     fn visit_with<'i, B>(
 147         &self,
 148         visitor: &mut dyn chalk_ir::visit::Visitor<'i, I, BreakTy = B>,
 149         outer_binder: DebruijnIndex,
 150     ) -> ControlFlow<B>
 151     where
 152         I: 'i,
 153     {
 154         try_break!(self.id.visit_with(visitor, outer_binder));
 155         self.binders.visit_with(visitor, outer_binder)
 156     }
 157 }
 158
 159 /// Represents the inputs and outputs on a `FnDefDatum`. This is split
 160 /// from the where clauses, since these can contain bound lifetimes.
 161 #[derive(Clone, Debug, PartialEq, Eq, Hash, Fold, HasInterner, Visit)]
 162 pub struct FnDefInputsAndOutputDatum<I: Interner> {
 163     /// Types of the function's arguments
 164     /// ```ignore
 165     /// fn foo<T>(bar: i32, baz: T);
 166     ///                ^^^       ^
 167     /// ```
 168     ///
 169     pub argument_types: Vec<Ty<I>>,
 170     /// Return type of the function
 171     /// ```ignore
 172     /// fn foo<T>() -> i32;
 173     ///                ^^^
 174     /// ```
 175     pub return_type: Ty<I>,
 176 }
 177
 178 #[derive(Clone, Debug, PartialEq, Eq, Hash, Fold, HasInterner, Visit)]
 179 /// Represents the bounds on a `FnDefDatum`, including
 180 /// the function definition's type signature and where clauses.
 181 pub struct FnDefDatumBound<I: Interner> {
 182     /// Inputs and outputs defined on a function
 183     /// These are needed for late-bound regions in rustc. For example the
 184     /// lifetime `'a` in
 185     /// ```ignore
 186     /// fn foo<'a, T>(&'a T);
 187     ///        ^^
 188     /// ```
 189     /// Rustc doesn't pass in late-bound the regions in substs, but the inputs
 190     /// and outputs may use them. `where_clauses` don't need an extra set of
 191     /// `Binders`, since any lifetimes found in where clauses are not late-bound.
 192     ///
 193     /// For more information, see [this rustc-dev-guide chapter](https://rustc-dev-guide.rust-lang.org/early-late-bound.html).
 194     pub inputs_and_output: Binders<FnDefInputsAndOutputDatum<I>>,
 195
 196     /// Where clauses defined on the function
 197     /// ```ignore
 198     /// fn foo<T>() where T: Eq;
 199     ///             ^^^^^^^^^^^
 200     /// ```
 201     pub where_clauses: Vec<QuantifiedWhereClause<I>>,
 202 }
 203
 204 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
 205 /// A rust intermediate representation (rust_ir) of a Trait Definition. For
 206 /// example, given the following rust code:
 207 ///
 208 /// ```compile_fail
 209 /// use std::fmt::Debug;
 210 ///
 211 /// trait Foo<T>
 212 /// where
 213 ///     T: Debug,
 214 /// {
 215 ///     type Bar<U>;
 216 /// }
 217 /// ```
 218 ///
 219 /// This would represent the `trait Foo` declaration. Note that the details of
 220 /// the trait members (e.g., the associated type declaration (`type Bar<U>`) are
 221 /// not contained in this type, and are represented separately (e.g., in
 222 /// [`AssociatedTyDatum`]).
 223 ///
 224 /// Not to be confused with the rust_ir for a Trait Implementation, which is
 225 /// represented by [`ImplDatum`]
 226 ///
 227 /// [`ImplDatum`]: struct.ImplDatum.html
 228 /// [`AssociatedTyDatum`]: struct.AssociatedTyDatum.html
 229 #[derive(Visit)]
 230 pub struct TraitDatum<I: Interner> {
 231     pub id: TraitId<I>,
 232
 233     pub binders: Binders<TraitDatumBound<I>>,
 234
 235     /// "Flags" indicate special kinds of traits, like auto traits.
 236     /// In Rust syntax these are represented in different ways, but in
 237     /// chalk we add annotations like `#[auto]`.
 238     pub flags: TraitFlags,
 239
 240     pub associated_ty_ids: Vec<AssocTypeId<I>>,
 241
 242     /// If this is a well-known trait, which one? If `None`, this is a regular,
 243     /// user-defined trait.
 244     pub well_known: Option<WellKnownTrait>,
 245 }
 246
 247 /// A list of the traits that are "well known" to chalk, which means that
 248 /// the chalk-solve crate has special, hard-coded impls for them.
 249 #[derive(Copy, Clone, Debug, PartialEq, Eq, Ord, PartialOrd, Hash)]
 250 pub enum WellKnownTrait {
 251     Sized,
 252     Copy,
 253     Clone,
 254     Drop,
 255     /// The trait `FnOnce<Args>` - the generic argument `Args` is always a tuple
 256     /// corresponding to the arguments of a function implementing this trait.
 257     /// E.g. `fn(u8, bool): FnOnce<(u8, bool)>`
 258     FnOnce,
 259     FnMut,
 260     Fn,
 261     Unsize,
 262     Unpin,
 263     CoerceUnsized,
 264     DiscriminantKind,
 265 }
 266
 267 chalk_ir::const_visit!(WellKnownTrait);
 268
 269 impl<I: Interner> TraitDatum<I> {
 270     pub fn is_auto_trait(&self) -> bool {
 271         self.flags.auto
 272     }
 273
 274     pub fn is_non_enumerable_trait(&self) -> bool {
 275         self.flags.non_enumerable
 276     }
 277
 278     pub fn is_coinductive_trait(&self) -> bool {
 279         self.flags.coinductive
 280     }
 281
 282     /// Gives access to the where clauses of the trait, quantified over the type parameters of the trait:
 283     ///
 284     /// ```ignore
 285     /// trait Foo<T> where T: Debug { }
 286     ///              ^^^^^^^^^^^^^^
 287     /// ```
 288     pub fn where_clauses(&self) -> Binders<&Vec<QuantifiedWhereClause<I>>> {
 289         self.binders.as_ref().map(|td| &td.where_clauses)
 290     }
 291 }
 292
 293 #[derive(Clone, Debug, PartialEq, Eq, Hash, HasInterner, Visit)]
 294 pub struct TraitDatumBound<I: Interner> {
 295     /// Where clauses defined on the trait:
 296     ///
 297     /// ```ignore
 298     /// trait Foo<T> where T: Debug { }
 299     ///              ^^^^^^^^^^^^^^
 300     /// ```
 301     pub where_clauses: Vec<QuantifiedWhereClause<I>>,
 302 }
 303
 304 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
 305 pub struct TraitFlags {
 306     /// An "auto trait" is one that is "automatically implemented" for every
 307     /// struct, so long as no explicit impl is given.
 308     ///
 309     /// Examples are `Send` and `Sync`.
 310     pub auto: bool,
 311
 312     pub marker: bool,
 313
 314     /// Indicate that a trait is defined upstream (in a dependency), used during
 315     /// coherence checking.
 316     pub upstream: bool,
 317
 318     /// A fundamental trait is a trait where adding an impl for an existing type
 319     /// is considered a breaking change. Examples of fundamental traits are the
 320     /// closure traits like `Fn` and `FnMut`.
 321     ///
 322     /// As of this writing (2020-03-27), fundamental traits are declared by the
 323     /// unstable `#[fundamental]` attribute in rustc, and hence cannot appear
 324     /// outside of the standard library.
 325     pub fundamental: bool,
 326
 327     /// Indicates that chalk cannot list all of the implementations of the given
 328     /// trait, likely because it is a publicly exported trait in a library.
 329     ///
 330     /// Currently (2020-03-27) rustc and rust-analyzer mark all traits as
 331     /// non_enumerable, and in the future it may become the only option.
 332     pub non_enumerable: bool,
 333
 334     pub coinductive: bool,
 335 }
 336
 337 chalk_ir::const_visit!(TraitFlags);
 338
 339 /// An inline bound, e.g. `: Foo<K>` in `impl<K, T: Foo<K>> SomeType<T>`.
 340 #[derive(Clone, Debug, PartialEq, Eq, Hash, Fold, Visit, HasInterner)]
 341 pub enum InlineBound<I: Interner> {
 342     TraitBound(TraitBound<I>),
 343     AliasEqBound(AliasEqBound<I>),
 344 }
 345
 346 #[allow(type_alias_bounds)]
 347 pub type QuantifiedInlineBound<I: Interner> = Binders<InlineBound<I>>;
 348
 349 pub trait IntoWhereClauses<I: Interner> {
 350     type Output;
 351
 352     fn into_where_clauses(&self, interner: &I, self_ty: Ty<I>) -> Vec<Self::Output>;
 353 }
 354
 355 impl<I: Interner> IntoWhereClauses<I> for InlineBound<I> {
 356     type Output = WhereClause<I>;
 357
 358     /// Applies the `InlineBound` to `self_ty` and lowers to a
 359     /// [`chalk_ir::DomainGoal`].
 360     ///
 361     /// Because an `InlineBound` does not know anything about what it's binding,
 362     /// you must provide that type as `self_ty`.
 363     fn into_where_clauses(&self, interner: &I, self_ty: Ty<I>) -> Vec<WhereClause<I>> {
 364         match self {
 365             InlineBound::TraitBound(b) => b.into_where_clauses(interner, self_ty),
 366             InlineBound::AliasEqBound(b) => b.into_where_clauses(interner, self_ty),
 367         }
 368     }
 369 }
 370
 371 impl<I: Interner> IntoWhereClauses<I> for QuantifiedInlineBound<I> {
 372     type Output = QuantifiedWhereClause<I>;
 373
 374     fn into_where_clauses(&self, interner: &I, self_ty: Ty<I>) -> Vec<QuantifiedWhereClause<I>> {
 375         let self_ty = self_ty.shifted_in(interner);
 376         self.map_ref(|b| b.into_where_clauses(interner, self_ty))
 377             .into_iter()
 378             .collect()
 379     }
 380 }
 381
 382 /// Represents a trait bound on e.g. a type or type parameter.
 383 /// Does not know anything about what it's binding.
 384 #[derive(Clone, Debug, PartialEq, Eq, Hash, Fold, Visit)]
 385 pub struct TraitBound<I: Interner> {
 386     pub trait_id: TraitId<I>,
 387     pub args_no_self: Vec<GenericArg<I>>,
 388 }
 389
 390 impl<I: Interner> TraitBound<I> {
 391     fn into_where_clauses(&self, interner: &I, self_ty: Ty<I>) -> Vec<WhereClause<I>> {
 392         let trait_ref = self.as_trait_ref(interner, self_ty);
 393         vec![WhereClause::Implemented(trait_ref)]
 394     }
 395
 396     pub fn as_trait_ref(&self, interner: &I, self_ty: Ty<I>) -> TraitRef<I> {
 397         TraitRef {
 398             trait_id: self.trait_id,
 399             substitution: Substitution::from_iter(
 400                 interner,
 401                 iter::once(self_ty.cast(interner)).chain(self.args_no_self.iter().cloned()),
 402             ),
 403         }
 404     }
 405 }
 406
 407 /// Represents an alias equality bound on e.g. a type or type parameter.
 408 /// Does not know anything about what it's binding.
 409 #[derive(Clone, Debug, PartialEq, Eq, Hash, Fold, Visit)]
 410 pub struct AliasEqBound<I: Interner> {
 411     pub trait_bound: TraitBound<I>,
 412     pub associated_ty_id: AssocTypeId<I>,
 413     /// Does not include trait parameters.
 414     pub parameters: Vec<GenericArg<I>>,
 415     pub value: Ty<I>,
 416 }
 417
 418 impl<I: Interner> AliasEqBound<I> {
 419     fn into_where_clauses(&self, interner: &I, self_ty: Ty<I>) -> Vec<WhereClause<I>> {
 420         let trait_ref = self.trait_bound.as_trait_ref(interner, self_ty);
 421
 422         let substitution = Substitution::from_iter(
 423             interner,
 424             self.parameters
 425                 .iter()
 426                 .cloned()
 427                 .chain(trait_ref.substitution.iter(interner).cloned()),
 428         );
 429
 430         vec![
 431             WhereClause::Implemented(trait_ref),
 432             WhereClause::AliasEq(AliasEq {
 433                 alias: AliasTy::Projection(ProjectionTy {
 434                     associated_ty_id: self.associated_ty_id,
 435                     substitution,
 436                 }),
 437                 ty: self.value.clone(),
 438             }),
 439         ]
 440     }
 441 }
 442
 443 pub trait Anonymize<I: Interner> {
 444     /// Utility function that converts from a list of generic arguments
 445     /// which *have* associated data (`WithKind<I, T>`) to a list of
 446     /// "anonymous" generic parameters that just preserves their
 447     /// kinds (`VariableKind<I>`). Often convenient in lowering.
 448     fn anonymize(&self) -> Vec<VariableKind<I>>;
 449 }
 450
 451 impl<I: Interner, T> Anonymize<I> for [WithKind<I, T>] {
 452     fn anonymize(&self) -> Vec<VariableKind<I>> {
 453         self.iter().map(|pk| pk.kind.clone()).collect()
 454     }
 455 }
 456
 457 /// Represents an associated type declaration found inside of a trait:
 458 ///
 459 /// ```notrust
 460 /// trait Foo<P1..Pn> { // P0 is Self
 461 ///     type Bar<Pn..Pm>: [bounds]
 462 ///     where
 463 ///         [where_clauses];
 464 /// }
 465 /// ```
 466 ///
 467 /// The meaning of each of these parts:
 468 ///
 469 /// * The *parameters* `P0...Pm` are all in scope for this associated type.
 470 /// * The *bounds* `bounds` are things that the impl must prove to be true.
 471 /// * The *where clauses* `where_clauses` are things that the impl can *assume* to be true
 472 ///   (but which projectors must prove).
 473 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
 474 pub struct AssociatedTyDatum<I: Interner> {
 475     /// The trait this associated type is defined in.
 476     pub trait_id: TraitId<I>,
 477
 478     /// The ID of this associated type
 479     pub id: AssocTypeId<I>,
 480
 481     /// Name of this associated type.
 482     pub name: I::Identifier,
 483
 484     /// These binders represent the `P0...Pm` variables.  The binders
 485     /// are in the order `[Pn..Pm; P0..Pn]`. That is, the variables
 486     /// from `Bar` come first (corresponding to the de bruijn concept
 487     /// that "inner" binders are lower indices, although within a
 488     /// given binder we do not have an ordering).
 489     pub binders: Binders<AssociatedTyDatumBound<I>>,
 490 }
 491
 492 // Manual implementation to avoid I::Identifier type.
 493 impl<I: Interner> Visit<I> for AssociatedTyDatum<I> {
 494     fn visit_with<'i, B>(
 495         &self,
 496         visitor: &mut dyn chalk_ir::visit::Visitor<'i, I, BreakTy = B>,
 497         outer_binder: DebruijnIndex,
 498     ) -> ControlFlow<B>
 499     where
 500         I: 'i,
 501     {
 502         try_break!(self.trait_id.visit_with(visitor, outer_binder));
 503         try_break!(self.id.visit_with(visitor, outer_binder));
 504         self.binders.visit_with(visitor, outer_binder)
 505     }
 506 }
 507
 508 /// Encodes the parts of `AssociatedTyDatum` where the parameters
 509 /// `P0..Pm` are in scope (`bounds` and `where_clauses`).
 510 #[derive(Clone, Debug, PartialEq, Eq, Hash, Fold, Visit, HasInterner)]
 511 pub struct AssociatedTyDatumBound<I: Interner> {
 512     /// Bounds on the associated type itself.
 513     ///
 514     /// These must be proven by the implementer, for all possible parameters that
 515     /// would result in a well-formed projection.
 516     pub bounds: Vec<QuantifiedInlineBound<I>>,
 517
 518     /// Where clauses that must hold for the projection to be well-formed.
 519     pub where_clauses: Vec<QuantifiedWhereClause<I>>,
 520 }
 521
 522 impl<I: Interner> AssociatedTyDatum<I> {
 523     /// Returns the associated ty's bounds applied to the projection type, e.g.:
 524     ///
 525     /// ```notrust
 526     /// Implemented(<?0 as Foo>::Item<?1>: Sized)
 527     /// ```
 528     ///
 529     /// these quantified where clauses are in the scope of the
 530     /// `binders` field.
 531     pub fn bounds_on_self(&self, interner: &I) -> Vec<QuantifiedWhereClause<I>> {
 532         let (binders, assoc_ty_datum) = self.binders.as_ref().into();
 533         // Create a list `P0...Pn` of references to the binders in
 534         // scope for this associated type:
 535         let substitution = Substitution::from_iter(
 536             interner,
 537             binders
 538                 .iter(interner)
 539                 .enumerate()
 540                 .map(|p| p.to_generic_arg(interner)),
 541         );
 542
 543         // The self type will be `<P0 as Foo<P1..Pn>>::Item<Pn..Pm>` etc
 544         let self_ty = TyKind::Alias(AliasTy::Projection(ProjectionTy {
 545             associated_ty_id: self.id,
 546             substitution,
 547         }))
 548         .intern(interner);
 549
 550         // Now use that as the self type for the bounds, transforming
 551         // something like `type Bar<Pn..Pm>: Debug` into
 552         //
 553         // ```
 554         // <P0 as Foo<P1..Pn>>::Item<Pn..Pm>: Debug
 555         // ```
 556         assoc_ty_datum
 557             .bounds
 558             .iter()
 559             .flat_map(|b| b.into_where_clauses(interner, self_ty.clone()))
 560             .collect()
 561     }
 562 }
 563
 564 /// Represents the *value* of an associated type that is assigned
 565 /// from within some impl.
 566 ///
 567 /// ```ignore
 568 /// impl Iterator for Foo {
 569 ///     type Item = XXX; // <-- represents this line!
 570 /// }
 571 /// ```
 572 #[derive(Clone, Debug, PartialEq, Eq, Hash, Fold, Visit)]
 573 pub struct AssociatedTyValue<I: Interner> {
 574     /// Impl in which this associated type value is found.  You might
 575     /// need to look at this to find the generic parameters defined on
 576     /// the impl, for example.
 577     ///
 578     /// ```ignore
 579     /// impl Iterator for Foo { // <-- refers to this impl
 580     ///     type Item = XXX; // <-- (where this is self)
 581     /// }
 582     /// ```
 583     pub impl_id: ImplId<I>,
 584
 585     /// Associated type being defined.
 586     ///
 587     /// ```ignore
 588     /// impl Iterator for Foo {
 589     ///     type Item = XXX; // <-- (where this is self)
 590     /// }
 591     /// ...
 592     /// trait Iterator {
 593     ///     type Item; // <-- refers to this declaration here!
 594     /// }
 595     /// ```
 596     pub associated_ty_id: AssocTypeId<I>,
 597
 598     /// Additional binders declared on the associated type itself,
 599     /// beyond those from the impl. This would be empty for normal
 600     /// associated types, but non-empty for generic associated types.
 601     ///
 602     /// ```ignore
 603     /// impl<T> Iterable for Vec<T> {
 604     ///     type Iter<'a> = vec::Iter<'a, T>;
 605     ///           // ^^^^ refers to these generics here
 606     /// }
 607     /// ```
 608     pub value: Binders<AssociatedTyValueBound<I>>,
 609 }
 610
 611 #[derive(Clone, Debug, PartialEq, Eq, Hash, Fold, Visit, HasInterner)]
 612 pub struct AssociatedTyValueBound<I: Interner> {
 613     /// Type that we normalize to. The X in `type Foo<'a> = X`.
 614     pub ty: Ty<I>,
 615 }
 616
 617 /// Represents the bounds for an `impl Trait` type.
 618 ///
 619 /// ```ignore
 620 /// opaque type T: A + B = HiddenTy;
 621 /// ```
 622 #[derive(Clone, Debug, PartialEq, Eq, Hash, Fold, Visit)]
 623 pub struct OpaqueTyDatum<I: Interner> {
 624     /// The placeholder `!T` that corresponds to the opaque type `T`.
 625     pub opaque_ty_id: OpaqueTyId<I>,
 626
 627     /// The type bound to when revealed.
 628     pub bound: Binders<OpaqueTyDatumBound<I>>,
 629 }
 630
 631 #[derive(Clone, Debug, PartialEq, Eq, Hash, Fold, HasInterner, Visit)]
 632 pub struct OpaqueTyDatumBound<I: Interner> {
 633     /// Trait bounds for the opaque type. These are bounds that the hidden type must meet.
 634     pub bounds: Binders<Vec<QuantifiedWhereClause<I>>>,
 635     /// Where clauses that inform well-formedness conditions for the opaque type.
 636     /// These are conditions on the generic parameters of the opaque type which must be true
 637     /// for a reference to the opaque type to be well-formed.
 638     pub where_clauses: Binders<Vec<QuantifiedWhereClause<I>>>,
 639 }
 640
 641 /// Represents a generator type.
 642 #[derive(Clone, Debug, PartialEq, Eq, Hash, Fold, HasInterner)]
 643 pub struct GeneratorDatum<I: Interner> {
 644     /// All of the nested types for this generator. The `Binder`
 645     /// represents the types and lifetimes that this generator is generic over -
 646     /// this behaves in the same way as `AdtDatun.binders`
 647     pub input_output: Binders<GeneratorInputOutputDatum<I>>,
 648 }
 649
 650 /// The nested types for a generator. This always appears inside a `GeneratorDatum`
 651 #[derive(Clone, Debug, PartialEq, Eq, Hash, Fold, HasInterner)]
 652 pub struct GeneratorInputOutputDatum<I: Interner> {
 653     /// The generator resume type - a value of this type
 654     /// is supplied by the caller when resuming the generator.
 655     /// Currently, this plays no rule in goal resolution.
 656     pub resume_type: Ty<I>,
 657     /// The generator yield type - a value of this type
 658     /// is supplied by the generator during a yield.
 659     /// Currently, this plays no role in goal resolution.
 660     pub yield_type: Ty<I>,
 661     /// The generator return type - a value of this type
 662     /// is supplied by the generator when it returns.
 663     /// Currently, this plays no role in goal resolution
 664     pub return_type: Ty<I>,
 665     /// The upvars stored by the generator. These represent
 666     /// types captured from the generator's environment,
 667     /// and are stored across all yields. These types (along with the witness types)
 668     /// are considered 'constituent types' for the purposes of determining auto trait
 669     /// implementations - that its, a generator impls an auto trait A
 670     /// iff all of its constituent types implement A.
 671     pub upvars: Vec<Ty<I>>,
 672 }
 673
 674 /// The generator witness data. Each `GeneratorId` has both a `GeneratorDatum`
 675 /// and a `GeneratorWitnessDatum` - these represent two distinct types in Rust.
 676 /// `GeneratorWitnessDatum` is logically 'inside' a generator - this only
 677 /// matters when we treat the witness type as a 'constituent type for the
 678 /// purposes of determining auto trait implementations.
 679 #[derive(Clone, Debug, PartialEq, Eq, Hash, Fold, HasInterner)]
 680 pub struct GeneratorWitnessDatum<I: Interner> {
 681     /// This binder is identical to the `input_output` binder in `GeneratorWitness` -
 682     /// it binds the types and lifetimes that the generator is generic over.
 683     /// There is an additional binder inside `GeneratorWitnessExistential`, which
 684     /// is treated specially.
 685     pub inner_types: Binders<GeneratorWitnessExistential<I>>,
 686 }
 687
 688 /// The generator witness types, together with existentially bound lifetimes.
 689 /// Each 'witness type' represents a type stored inside the generator across
 690 /// a yield. When a generator type is constructed, the precise region relationships
 691 /// found in the generator body are erased. As a result, we are left with existential
 692 /// lifetimes - each type is parameterized over *some* lifetimes, but we do not
 693 /// know their precise values.
 694 ///
 695 /// Unlike the binder in `GeneratorWitnessDatum`, this `Binder` never gets substituted
 696 /// via an `Ty`. Instead, we handle this `Binders` specially when determining
 697 /// auto trait impls. See `push_auto_trait_impls_generator_witness` for more details.
 698 #[derive(Clone, Debug, PartialEq, Eq, Hash, Fold, HasInterner)]
 699 pub struct GeneratorWitnessExistential<I: Interner> {
 700     pub types: Binders<Vec<Ty<I>>>,
 701 }
 702
 703 #[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, Debug)]
 704 pub enum Polarity {
 705     Positive,
 706     Negative,
 707 }
 708
 709 chalk_ir::const_visit!(Polarity);
 710
 711 impl Polarity {
 712     pub fn is_positive(&self) -> bool {
 713         match *self {
 714             Polarity::Positive => true,
 715             Polarity::Negative => false,
 716         }
 717     }
 718 }
 719
 720 /// Indicates the "most permissive" Fn-like trait that the closure implements.
 721 /// If the closure kind for a closure is FnMut, for example, then the closure
 722 /// implements FnMut and FnOnce.
 723 #[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, Debug)]
 724 pub enum ClosureKind {
 725     Fn,
 726     FnMut,
 727     FnOnce,
 728 }