1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
//! Contains the definition for the "Rust IR" -- this is basically a "lowered"
//! version of the AST, roughly corresponding to [the HIR] in the Rust
//! compiler.

use chalk_derive::{HasInterner, TypeFoldable, TypeVisitable};
use chalk_ir::cast::Cast;
use chalk_ir::fold::shift::Shift;
use chalk_ir::interner::Interner;
use chalk_ir::{
    try_break, visit::TypeVisitable, AdtId, AliasEq, AliasTy, AssocTypeId, Binders, DebruijnIndex,
    FnDefId, GenericArg, ImplId, OpaqueTyId, ProjectionTy, QuantifiedWhereClause, Substitution,
    ToGenericArg, TraitId, TraitRef, Ty, TyKind, VariableKind, WhereClause, WithKind,
};
use std::iter;
use std::ops::ControlFlow;

/// Identifier for an "associated type value" found in some impl.
#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct AssociatedTyValueId<I: Interner>(pub I::DefId);

chalk_ir::id_visit!(AssociatedTyValueId);
chalk_ir::id_fold!(AssociatedTyValueId);

#[derive(Clone, Debug, PartialEq, Eq, Hash, TypeVisitable)]
pub struct ImplDatum<I: Interner> {
    pub polarity: Polarity,
    pub binders: Binders<ImplDatumBound<I>>,
    pub impl_type: ImplType,
    pub associated_ty_value_ids: Vec<AssociatedTyValueId<I>>,
}

impl<I: Interner> ImplDatum<I> {
    pub fn is_positive(&self) -> bool {
        self.polarity.is_positive()
    }

    pub fn trait_id(&self) -> TraitId<I> {
        self.binders.skip_binders().trait_ref.trait_id
    }

    pub fn self_type_adt_id(&self, interner: I) -> Option<AdtId<I>> {
        match self
            .binders
            .skip_binders()
            .trait_ref
            .self_type_parameter(interner)
            .kind(interner)
        {
            TyKind::Adt(id, _) => Some(*id),
            _ => None,
        }
    }
}

#[derive(Clone, Debug, PartialEq, Eq, Hash, HasInterner, TypeFoldable, TypeVisitable)]
pub struct ImplDatumBound<I: Interner> {
    pub trait_ref: TraitRef<I>,
    pub where_clauses: Vec<QuantifiedWhereClause<I>>,
}

#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
pub enum ImplType {
    Local,
    External,
}

chalk_ir::const_visit!(ImplType);

#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct DefaultImplDatum<I: Interner> {
    pub binders: Binders<DefaultImplDatumBound<I>>,
}

#[derive(Clone, Debug, PartialEq, Eq, Hash, HasInterner)]
pub struct DefaultImplDatumBound<I: Interner> {
    pub trait_ref: TraitRef<I>,
    pub accessible_tys: Vec<Ty<I>>,
}

#[derive(Clone, Debug, PartialEq, Eq, Hash, TypeVisitable)]
pub struct AdtDatum<I: Interner> {
    pub binders: Binders<AdtDatumBound<I>>,
    pub id: AdtId<I>,
    pub flags: AdtFlags,
    pub kind: AdtKind,
}

#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
pub enum AdtKind {
    Struct,
    Enum,
    Union,
}

chalk_ir::const_visit!(AdtKind);

#[derive(Clone, Debug, PartialEq, Eq, Hash, TypeFoldable, HasInterner, TypeVisitable)]
pub struct AdtDatumBound<I: Interner> {
    pub variants: Vec<AdtVariantDatum<I>>,
    pub where_clauses: Vec<QuantifiedWhereClause<I>>,
}

#[derive(Clone, Debug, PartialEq, Eq, Hash, TypeFoldable, HasInterner, TypeVisitable)]
pub struct AdtVariantDatum<I: Interner> {
    pub fields: Vec<Ty<I>>,
}

#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct AdtFlags {
    pub upstream: bool,
    pub fundamental: bool,
    pub phantom_data: bool,
}

chalk_ir::const_visit!(AdtFlags);

#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct AdtRepr<I: Interner> {
    pub c: bool,
    pub packed: bool,
    pub int: Option<chalk_ir::Ty<I>>,
}

/// Information about the size and alignment of an ADT.
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct AdtSizeAlign {
    one_zst: bool,
}

impl AdtSizeAlign {
    pub fn from_one_zst(one_zst: bool) -> AdtSizeAlign {
        AdtSizeAlign { one_zst }
    }

    pub fn one_zst(&self) -> bool {
        self.one_zst
    }
}

#[derive(Clone, Debug, PartialEq, Eq, Hash)]
/// A rust intermediate representation (rust_ir) of a function definition/declaration.
/// For example, in the following rust code:
///
/// ```ignore
/// fn foo<T>() -> i32 where T: Eq;
/// ```
///
/// This would represent the declaration of `foo`.
///
/// Note this is distinct from a function pointer, which points to
/// a function with a given type signature, whereas this represents
/// a specific function definition.
pub struct FnDefDatum<I: Interner> {
    pub id: FnDefId<I>,
    pub sig: chalk_ir::FnSig<I>,
    pub binders: Binders<FnDefDatumBound<I>>,
}

/// Avoids visiting `I::FnAbi`
impl<I: Interner> TypeVisitable<I> for FnDefDatum<I> {
    fn visit_with<B>(
        &self,
        visitor: &mut dyn chalk_ir::visit::TypeVisitor<I, BreakTy = B>,
        outer_binder: DebruijnIndex,
    ) -> ControlFlow<B> {
        try_break!(self.id.visit_with(visitor, outer_binder));
        self.binders.visit_with(visitor, outer_binder)
    }
}

/// Represents the inputs and outputs on a `FnDefDatum`. This is split
/// from the where clauses, since these can contain bound lifetimes.
#[derive(Clone, Debug, PartialEq, Eq, Hash, TypeFoldable, HasInterner, TypeVisitable)]
pub struct FnDefInputsAndOutputDatum<I: Interner> {
    /// Types of the function's arguments
    /// ```ignore
    /// fn foo<T>(bar: i32, baz: T);
    ///                ^^^       ^
    /// ```
    ///
    pub argument_types: Vec<Ty<I>>,
    /// Return type of the function
    /// ```ignore
    /// fn foo<T>() -> i32;
    ///                ^^^
    /// ```
    pub return_type: Ty<I>,
}

#[derive(Clone, Debug, PartialEq, Eq, Hash, TypeFoldable, HasInterner, TypeVisitable)]
/// Represents the bounds on a `FnDefDatum`, including
/// the function definition's type signature and where clauses.
pub struct FnDefDatumBound<I: Interner> {
    /// Inputs and outputs defined on a function
    /// These are needed for late-bound regions in rustc. For example the
    /// lifetime `'a` in
    /// ```ignore
    /// fn foo<'a, T>(&'a T);
    ///        ^^
    /// ```
    /// Rustc doesn't pass in late-bound the regions in substs, but the inputs
    /// and outputs may use them. `where_clauses` don't need an extra set of
    /// `Binders`, since any lifetimes found in where clauses are not late-bound.
    ///
    /// For more information, see [this rustc-dev-guide chapter](https://rustc-dev-guide.rust-lang.org/early-late-bound.html).
    pub inputs_and_output: Binders<FnDefInputsAndOutputDatum<I>>,

    /// Where clauses defined on the function
    /// ```ignore
    /// fn foo<T>() where T: Eq;
    ///             ^^^^^^^^^^^
    /// ```
    pub where_clauses: Vec<QuantifiedWhereClause<I>>,
}

#[derive(Clone, Debug, PartialEq, Eq, Hash)]
/// A rust intermediate representation (rust_ir) of a Trait Definition. For
/// example, given the following rust code:
///
/// ```
/// use std::fmt::Debug;
///
/// trait Foo<T>
/// where
///     T: Debug,
/// {
///     type Bar<U>;
/// }
/// ```
///
/// This would represent the `trait Foo` declaration. Note that the details of
/// the trait members (e.g., the associated type declaration (`type Bar<U>`) are
/// not contained in this type, and are represented separately (e.g., in
/// [`AssociatedTyDatum`]).
///
/// Not to be confused with the rust_ir for a Trait Implementation, which is
/// represented by [`ImplDatum`]
///
/// [`ImplDatum`]: struct.ImplDatum.html
/// [`AssociatedTyDatum`]: struct.AssociatedTyDatum.html
#[derive(TypeVisitable)]
pub struct TraitDatum<I: Interner> {
    pub id: TraitId<I>,

    pub binders: Binders<TraitDatumBound<I>>,

    /// "Flags" indicate special kinds of traits, like auto traits.
    /// In Rust syntax these are represented in different ways, but in
    /// chalk we add annotations like `#[auto]`.
    pub flags: TraitFlags,

    pub associated_ty_ids: Vec<AssocTypeId<I>>,

    /// If this is a well-known trait, which one? If `None`, this is a regular,
    /// user-defined trait.
    pub well_known: Option<WellKnownTrait>,
}

/// A list of the traits that are "well known" to chalk, which means that
/// the chalk-solve crate has special, hard-coded impls for them.
#[derive(Copy, Clone, Debug, PartialEq, Eq, Ord, PartialOrd, Hash)]
pub enum WellKnownTrait {
    Sized,
    Copy,
    Clone,
    Drop,
    /// The trait `FnOnce<Args>` - the generic argument `Args` is always a tuple
    /// corresponding to the arguments of a function implementing this trait.
    /// E.g. `fn(u8, bool): FnOnce<(u8, bool)>`
    FnOnce,
    FnMut,
    Fn,
    Unsize,
    Unpin,
    CoerceUnsized,
    DiscriminantKind,
    Coroutine,
    DispatchFromDyn,
    Tuple,
    Pointee,
    FnPtr,
}

chalk_ir::const_visit!(WellKnownTrait);

impl<I: Interner> TraitDatum<I> {
    pub fn is_auto_trait(&self) -> bool {
        self.flags.auto
    }

    pub fn is_non_enumerable_trait(&self) -> bool {
        self.flags.non_enumerable
    }

    pub fn is_coinductive_trait(&self) -> bool {
        self.flags.coinductive
    }

    /// Gives access to the where clauses of the trait, quantified over the type parameters of the trait:
    ///
    /// ```ignore
    /// trait Foo<T> where T: Debug { }
    ///              ^^^^^^^^^^^^^^
    /// ```
    pub fn where_clauses(&self) -> Binders<&Vec<QuantifiedWhereClause<I>>> {
        self.binders.as_ref().map(|td| &td.where_clauses)
    }
}

#[derive(Clone, Debug, PartialEq, Eq, Hash, HasInterner, TypeVisitable)]
pub struct TraitDatumBound<I: Interner> {
    /// Where clauses defined on the trait:
    ///
    /// ```ignore
    /// trait Foo<T> where T: Debug { }
    ///              ^^^^^^^^^^^^^^
    /// ```
    pub where_clauses: Vec<QuantifiedWhereClause<I>>,
}

#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct TraitFlags {
    /// An "auto trait" is one that is "automatically implemented" for every
    /// struct, so long as no explicit impl is given.
    ///
    /// Examples are `Send` and `Sync`.
    pub auto: bool,

    pub marker: bool,

    /// Indicate that a trait is defined upstream (in a dependency), used during
    /// coherence checking.
    pub upstream: bool,

    /// A fundamental trait is a trait where adding an impl for an existing type
    /// is considered a breaking change. Examples of fundamental traits are the
    /// closure traits like `Fn` and `FnMut`.
    ///
    /// As of this writing (2020-03-27), fundamental traits are declared by the
    /// unstable `#[fundamental]` attribute in rustc, and hence cannot appear
    /// outside of the standard library.
    pub fundamental: bool,

    /// Indicates that chalk cannot list all of the implementations of the given
    /// trait, likely because it is a publicly exported trait in a library.
    ///
    /// Currently (2020-03-27) rustc and rust-analyzer mark all traits as
    /// non_enumerable, and in the future it may become the only option.
    pub non_enumerable: bool,

    pub coinductive: bool,
}

chalk_ir::const_visit!(TraitFlags);

/// An inline bound, e.g. `: Foo<K>` in `impl<K, T: Foo<K>> SomeType<T>`.
#[derive(Clone, Debug, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable, HasInterner)]
pub enum InlineBound<I: Interner> {
    TraitBound(TraitBound<I>),
    AliasEqBound(AliasEqBound<I>),
}

#[allow(type_alias_bounds)]
pub type QuantifiedInlineBound<I: Interner> = Binders<InlineBound<I>>;

pub trait IntoWhereClauses<I: Interner> {
    type Output;

    fn into_where_clauses(&self, interner: I, self_ty: Ty<I>) -> Vec<Self::Output>;
}

impl<I: Interner> IntoWhereClauses<I> for InlineBound<I> {
    type Output = WhereClause<I>;

    /// Applies the `InlineBound` to `self_ty` and lowers to a
    /// [`chalk_ir::DomainGoal`].
    ///
    /// Because an `InlineBound` does not know anything about what it's binding,
    /// you must provide that type as `self_ty`.
    fn into_where_clauses(&self, interner: I, self_ty: Ty<I>) -> Vec<WhereClause<I>> {
        match self {
            InlineBound::TraitBound(b) => b.into_where_clauses(interner, self_ty),
            InlineBound::AliasEqBound(b) => b.into_where_clauses(interner, self_ty),
        }
    }
}

impl<I: Interner> IntoWhereClauses<I> for QuantifiedInlineBound<I> {
    type Output = QuantifiedWhereClause<I>;

    fn into_where_clauses(&self, interner: I, self_ty: Ty<I>) -> Vec<QuantifiedWhereClause<I>> {
        let self_ty = self_ty.shifted_in(interner);
        self.map_ref(|b| b.into_where_clauses(interner, self_ty))
            .into_iter()
            .collect()
    }
}

/// Represents a trait bound on e.g. a type or type parameter.
/// Does not know anything about what it's binding.
#[derive(Clone, Debug, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable)]
pub struct TraitBound<I: Interner> {
    pub trait_id: TraitId<I>,
    pub args_no_self: Vec<GenericArg<I>>,
}

impl<I: Interner> TraitBound<I> {
    fn into_where_clauses(&self, interner: I, self_ty: Ty<I>) -> Vec<WhereClause<I>> {
        let trait_ref = self.as_trait_ref(interner, self_ty);
        vec![WhereClause::Implemented(trait_ref)]
    }

    pub fn as_trait_ref(&self, interner: I, self_ty: Ty<I>) -> TraitRef<I> {
        TraitRef {
            trait_id: self.trait_id,
            substitution: Substitution::from_iter(
                interner,
                iter::once(self_ty.cast(interner)).chain(self.args_no_self.iter().cloned()),
            ),
        }
    }
}

/// Represents an alias equality bound on e.g. a type or type parameter.
/// Does not know anything about what it's binding.
#[derive(Clone, Debug, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable)]
pub struct AliasEqBound<I: Interner> {
    pub trait_bound: TraitBound<I>,
    pub associated_ty_id: AssocTypeId<I>,
    /// Does not include trait parameters.
    pub parameters: Vec<GenericArg<I>>,
    pub value: Ty<I>,
}

impl<I: Interner> AliasEqBound<I> {
    fn into_where_clauses(&self, interner: I, self_ty: Ty<I>) -> Vec<WhereClause<I>> {
        let trait_ref = self.trait_bound.as_trait_ref(interner, self_ty);

        let substitution = Substitution::from_iter(
            interner,
            self.parameters
                .iter()
                .cloned()
                .chain(trait_ref.substitution.iter(interner).cloned()),
        );

        vec![
            WhereClause::Implemented(trait_ref),
            WhereClause::AliasEq(AliasEq {
                alias: AliasTy::Projection(ProjectionTy {
                    associated_ty_id: self.associated_ty_id,
                    substitution,
                }),
                ty: self.value.clone(),
            }),
        ]
    }
}

pub trait Anonymize<I: Interner> {
    /// Utility function that converts from a list of generic arguments
    /// which *have* associated data (`WithKind<I, T>`) to a list of
    /// "anonymous" generic parameters that just preserves their
    /// kinds (`VariableKind<I>`). Often convenient in lowering.
    fn anonymize(&self) -> Vec<VariableKind<I>>;
}

impl<I: Interner, T> Anonymize<I> for [WithKind<I, T>] {
    fn anonymize(&self) -> Vec<VariableKind<I>> {
        self.iter().map(|pk| pk.kind.clone()).collect()
    }
}

/// Represents an associated type declaration found inside of a trait:
///
/// ```notrust
/// trait Foo<P1..Pn> { // P0 is Self
///     type Bar<Pn..Pm>: [bounds]
///     where
///         [where_clauses];
/// }
/// ```
///
/// The meaning of each of these parts:
///
/// * The *parameters* `P0...Pm` are all in scope for this associated type.
/// * The *bounds* `bounds` are things that the impl must prove to be true.
/// * The *where clauses* `where_clauses` are things that the impl can *assume* to be true
///   (but which projectors must prove).
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct AssociatedTyDatum<I: Interner> {
    /// The trait this associated type is defined in.
    pub trait_id: TraitId<I>,

    /// The ID of this associated type
    pub id: AssocTypeId<I>,

    /// Name of this associated type.
    pub name: I::Identifier,

    /// These binders represent the `P0...Pm` variables.  The binders
    /// are in the order `[Pn..Pm; P0..Pn]`. That is, the variables
    /// from `Bar` come first (corresponding to the de bruijn concept
    /// that "inner" binders are lower indices, although within a
    /// given binder we do not have an ordering).
    pub binders: Binders<AssociatedTyDatumBound<I>>,
}

// Manual implementation to avoid I::Identifier type.
impl<I: Interner> TypeVisitable<I> for AssociatedTyDatum<I> {
    fn visit_with<B>(
        &self,
        visitor: &mut dyn chalk_ir::visit::TypeVisitor<I, BreakTy = B>,
        outer_binder: DebruijnIndex,
    ) -> ControlFlow<B> {
        try_break!(self.trait_id.visit_with(visitor, outer_binder));
        try_break!(self.id.visit_with(visitor, outer_binder));
        self.binders.visit_with(visitor, outer_binder)
    }
}

/// Encodes the parts of `AssociatedTyDatum` where the parameters
/// `P0..Pm` are in scope (`bounds` and `where_clauses`).
#[derive(Clone, Debug, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable, HasInterner)]
pub struct AssociatedTyDatumBound<I: Interner> {
    /// Bounds on the associated type itself.
    ///
    /// These must be proven by the implementer, for all possible parameters that
    /// would result in a well-formed projection.
    pub bounds: Vec<QuantifiedInlineBound<I>>,

    /// Where clauses that must hold for the projection to be well-formed.
    pub where_clauses: Vec<QuantifiedWhereClause<I>>,
}

impl<I: Interner> AssociatedTyDatum<I> {
    /// Returns the associated ty's bounds applied to the projection type, e.g.:
    ///
    /// ```notrust
    /// Implemented(<?0 as Foo>::Item<?1>: Sized)
    /// ```
    ///
    /// these quantified where clauses are in the scope of the
    /// `binders` field.
    pub fn bounds_on_self(&self, interner: I) -> Vec<QuantifiedWhereClause<I>> {
        let (binders, assoc_ty_datum) = self.binders.as_ref().into();
        // Create a list `P0...Pn` of references to the binders in
        // scope for this associated type:
        let substitution = Substitution::from_iter(
            interner,
            binders
                .iter(interner)
                .enumerate()
                .map(|p| p.to_generic_arg(interner)),
        );

        // The self type will be `<P0 as Foo<P1..Pn>>::Item<Pn..Pm>` etc
        let self_ty = TyKind::Alias(AliasTy::Projection(ProjectionTy {
            associated_ty_id: self.id,
            substitution,
        }))
        .intern(interner);

        // Now use that as the self type for the bounds, transforming
        // something like `type Bar<Pn..Pm>: Debug` into
        //
        // ```
        // <P0 as Foo<P1..Pn>>::Item<Pn..Pm>: Debug
        // ```
        assoc_ty_datum
            .bounds
            .iter()
            .flat_map(|b| b.into_where_clauses(interner, self_ty.clone()))
            .collect()
    }
}

/// Represents the *value* of an associated type that is assigned
/// from within some impl.
///
/// ```ignore
/// impl Iterator for Foo {
///     type Item = XXX; // <-- represents this line!
/// }
/// ```
#[derive(Clone, Debug, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable)]
pub struct AssociatedTyValue<I: Interner> {
    /// Impl in which this associated type value is found.  You might
    /// need to look at this to find the generic parameters defined on
    /// the impl, for example.
    ///
    /// ```ignore
    /// impl Iterator for Foo { // <-- refers to this impl
    ///     type Item = XXX; // <-- (where this is self)
    /// }
    /// ```
    pub impl_id: ImplId<I>,

    /// Associated type being defined.
    ///
    /// ```ignore
    /// impl Iterator for Foo {
    ///     type Item = XXX; // <-- (where this is self)
    /// }
    /// ...
    /// trait Iterator {
    ///     type Item; // <-- refers to this declaration here!
    /// }
    /// ```
    pub associated_ty_id: AssocTypeId<I>,

    /// Additional binders declared on the associated type itself,
    /// beyond those from the impl. This would be empty for normal
    /// associated types, but non-empty for generic associated types.
    ///
    /// ```ignore
    /// impl<T> Iterable for Vec<T> {
    ///     type Iter<'a> = vec::Iter<'a, T>;
    ///           // ^^^^ refers to these generics here
    /// }
    /// ```
    pub value: Binders<AssociatedTyValueBound<I>>,
}

#[derive(Clone, Debug, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable, HasInterner)]
pub struct AssociatedTyValueBound<I: Interner> {
    /// Type that we normalize to. The X in `type Foo<'a> = X`.
    pub ty: Ty<I>,
}

/// Represents the bounds for an `impl Trait` type.
///
/// ```ignore
/// opaque type T: A + B = HiddenTy;
/// ```
#[derive(Clone, Debug, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable)]
pub struct OpaqueTyDatum<I: Interner> {
    /// The placeholder `!T` that corresponds to the opaque type `T`.
    pub opaque_ty_id: OpaqueTyId<I>,

    /// The type bound to when revealed.
    pub bound: Binders<OpaqueTyDatumBound<I>>,
}

#[derive(Clone, Debug, PartialEq, Eq, Hash, TypeFoldable, HasInterner, TypeVisitable)]
pub struct OpaqueTyDatumBound<I: Interner> {
    /// Trait bounds for the opaque type. These are bounds that the hidden type must meet.
    pub bounds: Binders<Vec<QuantifiedWhereClause<I>>>,
    /// Where clauses that inform well-formedness conditions for the opaque type.
    /// These are conditions on the generic parameters of the opaque type which must be true
    /// for a reference to the opaque type to be well-formed.
    pub where_clauses: Binders<Vec<QuantifiedWhereClause<I>>>,
}

// The movability of a coroutine: whether a coroutine contains self-references,
// causing it to be !Unpin
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum Movability {
    Static,
    Movable,
}
chalk_ir::copy_fold!(Movability);

/// Represents a coroutine type.
#[derive(Clone, Debug, PartialEq, Eq, Hash, TypeFoldable, HasInterner)]
pub struct CoroutineDatum<I: Interner> {
    // Can the coroutine be moved (is Unpin or not)
    pub movability: Movability,
    /// All of the nested types for this coroutine. The `Binder`
    /// represents the types and lifetimes that this coroutine is generic over -
    /// this behaves in the same way as `AdtDatum.binders`
    pub input_output: Binders<CoroutineInputOutputDatum<I>>,
}

/// The nested types for a coroutine. This always appears inside a `CoroutineDatum`
#[derive(Clone, Debug, PartialEq, Eq, Hash, TypeFoldable, HasInterner)]
pub struct CoroutineInputOutputDatum<I: Interner> {
    /// The coroutine resume type - a value of this type
    /// is supplied by the caller when resuming the coroutine.
    /// Currently, this plays no rule in goal resolution.
    pub resume_type: Ty<I>,
    /// The coroutine yield type - a value of this type
    /// is supplied by the coroutine during a yield.
    /// Currently, this plays no role in goal resolution.
    pub yield_type: Ty<I>,
    /// The coroutine return type - a value of this type
    /// is supplied by the coroutine when it returns.
    /// Currently, this plays no role in goal resolution
    pub return_type: Ty<I>,
    /// The upvars stored by the coroutine. These represent
    /// types captured from the coroutine's environment,
    /// and are stored across all yields. These types (along with the witness types)
    /// are considered 'constituent types' for the purposes of determining auto trait
    /// implementations - that its, a coroutine impls an auto trait A
    /// iff all of its constituent types implement A.
    pub upvars: Vec<Ty<I>>,
}

/// The coroutine witness data. Each `CoroutineId` has both a `CoroutineDatum`
/// and a `CoroutineWitnessDatum` - these represent two distinct types in Rust.
/// `CoroutineWitnessDatum` is logically 'inside' a coroutine - this only
/// matters when we treat the witness type as a 'constituent type for the
/// purposes of determining auto trait implementations.
#[derive(Clone, Debug, PartialEq, Eq, Hash, TypeFoldable, HasInterner)]
pub struct CoroutineWitnessDatum<I: Interner> {
    /// This binder is identical to the `input_output` binder in `CoroutineWitness` -
    /// it binds the types and lifetimes that the coroutine is generic over.
    /// There is an additional binder inside `CoroutineWitnessExistential`, which
    /// is treated specially.
    pub inner_types: Binders<CoroutineWitnessExistential<I>>,
}

/// The coroutine witness types, together with existentially bound lifetimes.
/// Each 'witness type' represents a type stored inside the coroutine across
/// a yield. When a coroutine type is constructed, the precise region relationships
/// found in the coroutine body are erased. As a result, we are left with existential
/// lifetimes - each type is parameterized over *some* lifetimes, but we do not
/// know their precise values.
///
/// Unlike the binder in `CoroutineWitnessDatum`, this `Binder` never gets substituted
/// via an `Ty`. Instead, we handle this `Binders` specially when determining
/// auto trait impls. See `push_auto_trait_impls_coroutine_witness` for more details.
#[derive(Clone, Debug, PartialEq, Eq, Hash, TypeFoldable, HasInterner)]
pub struct CoroutineWitnessExistential<I: Interner> {
    pub types: Binders<Vec<Ty<I>>>,
}

#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, Debug)]
pub enum Polarity {
    Positive,
    Negative,
}

chalk_ir::const_visit!(Polarity);

impl Polarity {
    pub fn is_positive(&self) -> bool {
        match *self {
            Polarity::Positive => true,
            Polarity::Negative => false,
        }
    }
}

/// Indicates the "most permissive" Fn-like trait that the closure implements.
/// If the closure kind for a closure is FnMut, for example, then the closure
/// implements FnMut and FnOnce.
#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, Debug)]
pub enum ClosureKind {
    Fn,
    FnMut,
    FnOnce,
}