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

chalk_solve/
rust_ir.rs
