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