1 //! Defines the IR for types and logical predicates.
2
3 #![deny(rust_2018_idioms)]
4 #![warn(missing_docs)]
5
6 // Allows macros to refer to this crate as `::chalk_ir`
7 extern crate self as chalk_ir;
8
9 use crate::cast::{Cast, CastTo, Caster};
10 use crate::fold::shift::Shift;
11 use crate::fold::{Fold, Folder, Subst, SuperFold};
12 use crate::visit::{ControlFlow, SuperVisit, Visit, VisitExt, Visitor};
13 use chalk_derive::{Fold, HasInterner, SuperVisit, Visit, Zip};
14 use std::marker::PhantomData;
15
16 pub use crate::debug::SeparatorTraitRef;
17 #[macro_use(bitflags)]
18 extern crate bitflags;
19 /// Uninhabited (empty) type, used in combination with `PhantomData`.
20 #[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
21 pub enum Void {}
22
23 /// Many of our internal operations (e.g., unification) are an attempt
24 /// to perform some operation which may not complete.
25 pub type Fallible<T> = Result<T, NoSolution>;
26
27 /// A combination of `Fallible` and `Floundered`.
28 pub enum FallibleOrFloundered<T> {
29 /// Success
30 Ok(T),
31 /// No solution. See `chalk_ir::NoSolution`.
32 NoSolution,
33 /// Floundered. See `chalk_ir::Floundered`.
34 Floundered,
35 }
36
37 /// Indicates that the attempted operation has "no solution" -- i.e.,
38 /// cannot be performed.
39 #[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
40 pub struct NoSolution;
41
42 /// Indicates that the complete set of program clauses for this goal
43 /// cannot be enumerated.
44 pub struct Floundered;
45
46 macro_rules! impl_debugs {
47 ($($id:ident), *) => {
48 $(
49 impl<I: Interner> std::fmt::Debug for $id<I> {
50 fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
51 write!(fmt, "{}({:?})", stringify!($id), self.0)
52 }
53 }
54 )*
55 };
56 }
57
58 #[macro_use]
59 pub mod zip;
60
61 #[macro_use]
62 pub mod fold;
63
64 #[macro_use]
65 pub mod visit;
66
67 pub mod cast;
68
69 pub mod interner;
70 use interner::{HasInterner, Interner};
71
72 pub mod could_match;
73 pub mod debug;
74
75 /// Variance
76 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
77 pub enum Variance {
78 /// a <: b
79 Covariant,
80 /// a == b
81 Invariant,
82 /// b <: a
83 Contravariant,
84 }
85
86 impl Variance {
87 /// `a.xform(b)` combines the variance of a context with the
88 /// variance of a type with the following meaning. If we are in a
89 /// context with variance `a`, and we encounter a type argument in
90 /// a position with variance `b`, then `a.xform(b)` is the new
91 /// variance with which the argument appears.
92 ///
93 /// Example 1:
94 ///
95 /// ```ignore
96 /// *mut Vec<i32>
97 /// ```
98 ///
99 /// Here, the "ambient" variance starts as covariant. `*mut T` is
100 /// invariant with respect to `T`, so the variance in which the
101 /// `Vec<i32>` appears is `Covariant.xform(Invariant)`, which
102 /// yields `Invariant`. Now, the type `Vec<T>` is covariant with
103 /// respect to its type argument `T`, and hence the variance of
104 /// the `i32` here is `Invariant.xform(Covariant)`, which results
105 /// (again) in `Invariant`.
106 ///
107 /// Example 2:
108 ///
109 /// ```ignore
110 /// fn(*const Vec<i32>, *mut Vec<i32)
111 /// ```
112 ///
113 /// The ambient variance is covariant. A `fn` type is
114 /// contravariant with respect to its parameters, so the variance
115 /// within which both pointer types appear is
116 /// `Covariant.xform(Contravariant)`, or `Contravariant`. `*const
117 /// T` is covariant with respect to `T`, so the variance within
118 /// which the first `Vec<i32>` appears is
119 /// `Contravariant.xform(Covariant)` or `Contravariant`. The same
120 /// is true for its `i32` argument. In the `*mut T` case, the
121 /// variance of `Vec<i32>` is `Contravariant.xform(Invariant)`,
122 /// and hence the outermost type is `Invariant` with respect to
123 /// `Vec<i32>` (and its `i32` argument).
124 ///
125 /// Source: Figure 1 of "Taming the Wildcards:
126 /// Combining Definition- and Use-Site Variance" published in PLDI'11.
127 /// (Doc from rustc)
xform(self, other: Variance) -> Variance128 pub fn xform(self, other: Variance) -> Variance {
129 match (self, other) {
130 (Variance::Invariant, _) => Variance::Invariant,
131 (_, Variance::Invariant) => Variance::Invariant,
132 (_, Variance::Covariant) => self,
133 (Variance::Covariant, Variance::Contravariant) => Variance::Contravariant,
134 (Variance::Contravariant, Variance::Contravariant) => Variance::Covariant,
135 }
136 }
137
138 /// Converts `Covariant` into `Contravariant` and vice-versa. `Invariant`
139 /// stays the same.
invert(self) -> Variance140 pub fn invert(self) -> Variance {
141 match self {
142 Variance::Invariant => Variance::Invariant,
143 Variance::Covariant => Variance::Contravariant,
144 Variance::Contravariant => Variance::Covariant,
145 }
146 }
147 }
148
149 #[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, HasInterner)]
150 /// The set of assumptions we've made so far, and the current number of
151 /// universal (forall) quantifiers we're within.
152 pub struct Environment<I: Interner> {
153 /// The clauses in the environment.
154 pub clauses: ProgramClauses<I>,
155 }
156
157 impl<I: Interner> Copy for Environment<I> where I::InternedProgramClauses: Copy {}
158
159 impl<I: Interner> Environment<I> {
160 /// Creates a new environment.
new(interner: &I) -> Self161 pub fn new(interner: &I) -> Self {
162 Environment {
163 clauses: ProgramClauses::empty(interner),
164 }
165 }
166
167 /// Adds (an iterator of) clauses to the environment.
add_clauses<II>(&self, interner: &I, clauses: II) -> Self where II: IntoIterator<Item = ProgramClause<I>>,168 pub fn add_clauses<II>(&self, interner: &I, clauses: II) -> Self
169 where
170 II: IntoIterator<Item = ProgramClause<I>>,
171 {
172 let mut env = self.clone();
173 env.clauses =
174 ProgramClauses::from_iter(interner, env.clauses.iter(interner).cloned().chain(clauses));
175 env
176 }
177
178 /// True if any of the clauses in the environment have a consequence of `Compatible`.
179 /// Panics if the conditions or constraints of that clause are not empty.
has_compatible_clause(&self, interner: &I) -> bool180 pub fn has_compatible_clause(&self, interner: &I) -> bool {
181 self.clauses.as_slice(interner).iter().any(|c| {
182 let ProgramClauseData(implication) = c.data(interner);
183 match implication.skip_binders().consequence {
184 DomainGoal::Compatible => {
185 // We currently don't generate `Compatible` with any conditions or constraints
186 // If this was needed, for whatever reason, then a third "yes, but must evaluate"
187 // return value would have to be added.
188 assert!(implication.skip_binders().conditions.is_empty(interner));
189 assert!(implication.skip_binders().constraints.is_empty(interner));
190 true
191 }
192 _ => false,
193 }
194 })
195 }
196 }
197
198 /// A goal with an environment to solve it in.
199 #[derive(Clone, Debug, PartialEq, Eq, Hash, Fold, Visit)]
200 #[allow(missing_docs)]
201 pub struct InEnvironment<G: HasInterner> {
202 pub environment: Environment<G::Interner>,
203 pub goal: G,
204 }
205
206 impl<G: HasInterner<Interner = I> + Copy, I: Interner> Copy for InEnvironment<G> where
207 I::InternedProgramClauses: Copy
208 {
209 }
210
211 impl<G: HasInterner> InEnvironment<G> {
212 /// Creates a new environment/goal pair.
new(environment: &Environment<G::Interner>, goal: G) -> Self213 pub fn new(environment: &Environment<G::Interner>, goal: G) -> Self {
214 InEnvironment {
215 environment: environment.clone(),
216 goal,
217 }
218 }
219
220 /// Maps the goal without touching the environment.
map<OP, H>(self, op: OP) -> InEnvironment<H> where OP: FnOnce(G) -> H, H: HasInterner<Interner = G::Interner>,221 pub fn map<OP, H>(self, op: OP) -> InEnvironment<H>
222 where
223 OP: FnOnce(G) -> H,
224 H: HasInterner<Interner = G::Interner>,
225 {
226 InEnvironment {
227 environment: self.environment,
228 goal: op(self.goal),
229 }
230 }
231 }
232
233 impl<G: HasInterner> HasInterner for InEnvironment<G> {
234 type Interner = G::Interner;
235 }
236
237 /// Different signed int types.
238 #[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
239 #[allow(missing_docs)]
240 pub enum IntTy {
241 Isize,
242 I8,
243 I16,
244 I32,
245 I64,
246 I128,
247 }
248
249 /// Different unsigned int types.
250 #[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
251 #[allow(missing_docs)]
252 pub enum UintTy {
253 Usize,
254 U8,
255 U16,
256 U32,
257 U64,
258 U128,
259 }
260
261 /// Different kinds of float types.
262 #[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
263 #[allow(missing_docs)]
264 pub enum FloatTy {
265 F32,
266 F64,
267 }
268
269 /// Types of scalar values.
270 #[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
271 #[allow(missing_docs)]
272 pub enum Scalar {
273 Bool,
274 Char,
275 Int(IntTy),
276 Uint(UintTy),
277 Float(FloatTy),
278 }
279
280 /// Whether a function is safe or not.
281 #[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
282 pub enum Safety {
283 /// Safe
284 Safe,
285 /// Unsafe
286 Unsafe,
287 }
288
289 /// Whether a type is mutable or not.
290 #[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
291 pub enum Mutability {
292 /// Mutable
293 Mut,
294 /// Immutable
295 Not,
296 }
297
298 /// An universe index is how a universally quantified parameter is
299 /// represented when it's binder is moved into the environment.
300 /// An example chain of transformations would be:
301 /// `forall<T> { Goal(T) }` (syntactical representation)
302 /// `forall { Goal(?0) }` (used a DeBruijn index)
303 /// `Goal(!U1)` (the quantifier was moved to the environment and replaced with a universe index)
304 /// See https://rustc-dev-guide.rust-lang.org/borrow_check/region_inference.html#placeholders-and-universes for more.
305 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
306 pub struct UniverseIndex {
307 /// The counter for the universe index, starts with 0.
308 pub counter: usize,
309 }
310
311 impl UniverseIndex {
312 /// Root universe index (0).
313 pub const ROOT: UniverseIndex = UniverseIndex { counter: 0 };
314
315 /// Root universe index (0).
root() -> UniverseIndex316 pub fn root() -> UniverseIndex {
317 Self::ROOT
318 }
319
320 /// Whether one universe can "see" another.
can_see(self, ui: UniverseIndex) -> bool321 pub fn can_see(self, ui: UniverseIndex) -> bool {
322 self.counter >= ui.counter
323 }
324
325 /// Increases the index counter.
next(self) -> UniverseIndex326 pub fn next(self) -> UniverseIndex {
327 UniverseIndex {
328 counter: self.counter + 1,
329 }
330 }
331 }
332
333 /// Maps the universes found in the `u_canonicalize` result (the
334 /// "canonical" universes) to the universes found in the original
335 /// value (and vice versa). When used as a folder -- i.e., from
336 /// outside this module -- converts from "canonical" universes to the
337 /// original (but see the `UMapToCanonical` folder).
338 #[derive(Clone, Debug)]
339 pub struct UniverseMap {
340 /// A reverse map -- for each universe Ux that appears in
341 /// `quantified`, the corresponding universe in the original was
342 /// `universes[x]`.
343 pub universes: Vec<UniverseIndex>,
344 }
345
346 impl UniverseMap {
347 /// Creates a new universe map.
new() -> Self348 pub fn new() -> Self {
349 UniverseMap {
350 universes: vec![UniverseIndex::root()],
351 }
352 }
353
354 /// Number of canonical universes.
num_canonical_universes(&self) -> usize355 pub fn num_canonical_universes(&self) -> usize {
356 self.universes.len()
357 }
358 }
359
360 /// The id for an Abstract Data Type (i.e. structs, unions and enums).
361 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
362 pub struct AdtId<I: Interner>(pub I::InternedAdtId);
363
364 /// The id of a trait definition; could be used to load the trait datum by
365 /// invoking the [`trait_datum`] method.
366 ///
367 /// [`trait_datum`]: ../chalk_solve/trait.RustIrDatabase.html#tymethod.trait_datum
368 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
369 pub struct TraitId<I: Interner>(pub I::DefId);
370
371 /// The id for an impl.
372 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
373 pub struct ImplId<I: Interner>(pub I::DefId);
374
375 /// Id for a specific clause.
376 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
377 pub struct ClauseId<I: Interner>(pub I::DefId);
378
379 /// The id for the associated type member of a trait. The details of the type
380 /// can be found by invoking the [`associated_ty_data`] method.
381 ///
382 /// [`associated_ty_data`]: ../chalk_solve/trait.RustIrDatabase.html#tymethod.associated_ty_data
383 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
384 pub struct AssocTypeId<I: Interner>(pub I::DefId);
385
386 /// Id for an opaque type.
387 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
388 pub struct OpaqueTyId<I: Interner>(pub I::DefId);
389
390 /// Function definition id.
391 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
392 pub struct FnDefId<I: Interner>(pub I::DefId);
393
394 /// Id for Rust closures.
395 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
396 pub struct ClosureId<I: Interner>(pub I::DefId);
397
398 /// Id for Rust generators.
399 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
400 pub struct GeneratorId<I: Interner>(pub I::DefId);
401
402 /// Id for foreign types.
403 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
404 pub struct ForeignDefId<I: Interner>(pub I::DefId);
405
406 impl_debugs!(ImplId, ClauseId);
407
408 /// A Rust type. The actual type data is stored in `TyKind`.
409 #[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, HasInterner)]
410 pub struct Ty<I: Interner> {
411 interned: I::InternedType,
412 }
413
414 ///compute type flags for Lifetime
compute_lifetime_flags<I: Interner>(lifetime: &Lifetime<I>, interner: &I) -> TypeFlags415 fn compute_lifetime_flags<I: Interner>(lifetime: &Lifetime<I>, interner: &I) -> TypeFlags {
416 match lifetime.data(&interner) {
417 LifetimeData::InferenceVar(_) => {
418 TypeFlags::HAS_RE_INFER
419 | TypeFlags::HAS_FREE_LOCAL_REGIONS
420 | TypeFlags::HAS_FREE_REGIONS
421 }
422 LifetimeData::Placeholder(_) => {
423 TypeFlags::HAS_RE_PLACEHOLDER
424 | TypeFlags::HAS_FREE_LOCAL_REGIONS
425 | TypeFlags::HAS_FREE_REGIONS
426 }
427 LifetimeData::Static | LifetimeData::Empty(_) => TypeFlags::HAS_FREE_REGIONS,
428 LifetimeData::Phantom(_, _) => TypeFlags::empty(),
429 LifetimeData::BoundVar(_) => TypeFlags::HAS_RE_LATE_BOUND,
430 LifetimeData::Erased => TypeFlags::HAS_RE_ERASED,
431 }
432 }
433
434 /// Compute type flags for Substitution<I>
compute_substitution_flags<I: Interner>( substitution: &Substitution<I>, interner: &I, ) -> TypeFlags435 fn compute_substitution_flags<I: Interner>(
436 substitution: &Substitution<I>,
437 interner: &I,
438 ) -> TypeFlags {
439 let mut flags = TypeFlags::empty();
440 for generic_arg in substitution.iter(&interner) {
441 flags |= compute_generic_arg_flags(generic_arg, &interner);
442 }
443 flags
444 }
445
446 /// Compute type flags for GenericArg<I>
compute_generic_arg_flags<I: Interner>(generic_arg: &GenericArg<I>, interner: &I) -> TypeFlags447 fn compute_generic_arg_flags<I: Interner>(generic_arg: &GenericArg<I>, interner: &I) -> TypeFlags {
448 match generic_arg.data(&interner) {
449 GenericArgData::Ty(ty) => ty.data(interner).flags,
450 GenericArgData::Lifetime(lifetime) => compute_lifetime_flags(lifetime, interner),
451 GenericArgData::Const(constant) => {
452 let data = constant.data(&interner);
453 let flags = data.ty.data(interner).flags;
454 match data.value {
455 ConstValue::BoundVar(_) => flags,
456 ConstValue::InferenceVar(_) => {
457 flags | TypeFlags::HAS_CT_INFER | TypeFlags::STILL_FURTHER_SPECIALIZABLE
458 }
459 ConstValue::Placeholder(_) => {
460 flags | TypeFlags::HAS_CT_PLACEHOLDER | TypeFlags::STILL_FURTHER_SPECIALIZABLE
461 }
462 ConstValue::Concrete(_) => flags,
463 }
464 }
465 }
466 }
467
468 /// Compute type flags for aliases
compute_alias_flags<I: Interner>(alias_ty: &AliasTy<I>, interner: &I) -> TypeFlags469 fn compute_alias_flags<I: Interner>(alias_ty: &AliasTy<I>, interner: &I) -> TypeFlags {
470 match alias_ty {
471 AliasTy::Projection(projection_ty) => {
472 TypeFlags::HAS_TY_PROJECTION
473 | compute_substitution_flags(&(projection_ty.substitution), interner)
474 }
475 AliasTy::Opaque(opaque_ty) => {
476 TypeFlags::HAS_TY_OPAQUE
477 | compute_substitution_flags(&(opaque_ty.substitution), interner)
478 }
479 }
480 }
481
482 /// Compute type flags for a TyKind
compute_flags<I: Interner>(kind: &TyKind<I>, interner: &I) -> TypeFlags483 fn compute_flags<I: Interner>(kind: &TyKind<I>, interner: &I) -> TypeFlags {
484 match kind {
485 TyKind::Adt(_, substitution)
486 | TyKind::AssociatedType(_, substitution)
487 | TyKind::Tuple(_, substitution)
488 | TyKind::Closure(_, substitution)
489 | TyKind::Generator(_, substitution)
490 | TyKind::GeneratorWitness(_, substitution)
491 | TyKind::FnDef(_, substitution)
492 | TyKind::OpaqueType(_, substitution) => compute_substitution_flags(substitution, interner),
493 TyKind::Scalar(_) | TyKind::Str | TyKind::Never | TyKind::Foreign(_) => TypeFlags::empty(),
494 TyKind::Error => TypeFlags::HAS_ERROR,
495 TyKind::Slice(ty) | TyKind::Raw(_, ty) => ty.data(interner).flags,
496 TyKind::Ref(_, lifetime, ty) => {
497 compute_lifetime_flags(lifetime, interner) | ty.data(interner).flags
498 }
499 TyKind::Array(ty, const_ty) => {
500 let flags = ty.data(interner).flags;
501 let const_data = const_ty.data(interner);
502 flags
503 | const_data.ty.data(interner).flags
504 | match const_data.value {
505 ConstValue::BoundVar(_) | ConstValue::Concrete(_) => TypeFlags::empty(),
506 ConstValue::InferenceVar(_) => {
507 TypeFlags::HAS_CT_INFER | TypeFlags::STILL_FURTHER_SPECIALIZABLE
508 }
509 ConstValue::Placeholder(_) => {
510 TypeFlags::HAS_CT_PLACEHOLDER | TypeFlags::STILL_FURTHER_SPECIALIZABLE
511 }
512 }
513 }
514 TyKind::Placeholder(_) => TypeFlags::HAS_TY_PLACEHOLDER,
515 TyKind::Dyn(dyn_ty) => {
516 let lifetime_flags = compute_lifetime_flags(&(dyn_ty.lifetime), &interner);
517 let mut dyn_flags = TypeFlags::empty();
518 for var_kind in dyn_ty.bounds.value.iter(&interner) {
519 match &(var_kind.value) {
520 WhereClause::Implemented(trait_ref) => {
521 dyn_flags |= compute_substitution_flags(&(trait_ref.substitution), interner)
522 }
523 WhereClause::AliasEq(alias_eq) => {
524 dyn_flags |= compute_alias_flags(&(alias_eq.alias), &interner);
525 dyn_flags |= alias_eq.ty.data(&interner).flags;
526 }
527 WhereClause::LifetimeOutlives(lifetime_outlives) => {
528 dyn_flags |= compute_lifetime_flags(&(lifetime_outlives.a), &interner)
529 | compute_lifetime_flags(&(lifetime_outlives.b), &interner);
530 }
531 WhereClause::TypeOutlives(type_outlives) => {
532 dyn_flags |= type_outlives.ty.data(&interner).flags;
533 dyn_flags |= compute_lifetime_flags(&(type_outlives.lifetime), &interner);
534 }
535 }
536 }
537 lifetime_flags | dyn_flags
538 }
539 TyKind::Alias(alias_ty) => compute_alias_flags(&alias_ty, &interner),
540 TyKind::BoundVar(_) => TypeFlags::empty(),
541 TyKind::InferenceVar(_, _) => TypeFlags::HAS_TY_INFER,
542 TyKind::Function(fn_pointer) => {
543 compute_substitution_flags(&fn_pointer.substitution.0, interner)
544 }
545 }
546 }
547
548 impl<I: Interner> Ty<I> {
549 /// Creates a type from `TyKind`.
new(interner: &I, data: impl CastTo<TyKind<I>>) -> Self550 pub fn new(interner: &I, data: impl CastTo<TyKind<I>>) -> Self {
551 let ty_kind = data.cast(&interner);
552 let data = TyData {
553 flags: compute_flags(&ty_kind, &interner),
554 kind: ty_kind,
555 };
556 Ty {
557 interned: I::intern_ty(interner, data),
558 }
559 }
560
561 /// Gets the interned type.
interned(&self) -> &I::InternedType562 pub fn interned(&self) -> &I::InternedType {
563 &self.interned
564 }
565
566 /// Gets the underlying type data.
data(&self, interner: &I) -> &TyData<I>567 pub fn data(&self, interner: &I) -> &TyData<I> {
568 I::ty_data(interner, &self.interned)
569 }
570
571 /// Gets the underlying type kind.
kind(&self, interner: &I) -> &TyKind<I>572 pub fn kind(&self, interner: &I) -> &TyKind<I> {
573 &I::ty_data(interner, &self.interned).kind
574 }
575
576 /// Creates a `FromEnv` constraint using this type.
from_env(&self) -> FromEnv<I>577 pub fn from_env(&self) -> FromEnv<I> {
578 FromEnv::Ty(self.clone())
579 }
580
581 /// Creates a WF-constraint for this type.
well_formed(&self) -> WellFormed<I>582 pub fn well_formed(&self) -> WellFormed<I> {
583 WellFormed::Ty(self.clone())
584 }
585
586 /// Creates a domain goal `FromEnv(T)` where `T` is this type.
into_from_env_goal(self, interner: &I) -> DomainGoal<I>587 pub fn into_from_env_goal(self, interner: &I) -> DomainGoal<I> {
588 self.from_env().cast(interner)
589 }
590
591 /// If this is a `TyKind::BoundVar(d)`, returns `Some(d)` else `None`.
bound_var(&self, interner: &I) -> Option<BoundVar>592 pub fn bound_var(&self, interner: &I) -> Option<BoundVar> {
593 if let TyKind::BoundVar(bv) = self.kind(interner) {
594 Some(*bv)
595 } else {
596 None
597 }
598 }
599
600 /// If this is a `TyKind::InferenceVar(d)`, returns `Some(d)` else `None`.
inference_var(&self, interner: &I) -> Option<InferenceVar>601 pub fn inference_var(&self, interner: &I) -> Option<InferenceVar> {
602 if let TyKind::InferenceVar(depth, _) = self.kind(interner) {
603 Some(*depth)
604 } else {
605 None
606 }
607 }
608
609 /// Returns true if this is a `BoundVar` or an `InferenceVar` of `TyVariableKind::General`.
is_general_var(&self, interner: &I, binders: &CanonicalVarKinds<I>) -> bool610 pub fn is_general_var(&self, interner: &I, binders: &CanonicalVarKinds<I>) -> bool {
611 match self.kind(interner) {
612 TyKind::BoundVar(bv)
613 if bv.debruijn == DebruijnIndex::INNERMOST
614 && binders.at(interner, bv.index).kind
615 == VariableKind::Ty(TyVariableKind::General) =>
616 {
617 true
618 }
619 TyKind::InferenceVar(_, TyVariableKind::General) => true,
620 _ => false,
621 }
622 }
623
624 /// Returns true if this is an `Alias`.
is_alias(&self, interner: &I) -> bool625 pub fn is_alias(&self, interner: &I) -> bool {
626 match self.kind(interner) {
627 TyKind::Alias(..) => true,
628 _ => false,
629 }
630 }
631
632 /// Returns true if this is an `IntTy` or `UintTy`.
is_integer(&self, interner: &I) -> bool633 pub fn is_integer(&self, interner: &I) -> bool {
634 match self.kind(interner) {
635 TyKind::Scalar(Scalar::Int(_)) | TyKind::Scalar(Scalar::Uint(_)) => true,
636 _ => false,
637 }
638 }
639
640 /// Returns true if this is a `FloatTy`.
is_float(&self, interner: &I) -> bool641 pub fn is_float(&self, interner: &I) -> bool {
642 match self.kind(interner) {
643 TyKind::Scalar(Scalar::Float(_)) => true,
644 _ => false,
645 }
646 }
647
648 /// Returns `Some(adt_id)` if this is an ADT, `None` otherwise
adt_id(&self, interner: &I) -> Option<AdtId<I>>649 pub fn adt_id(&self, interner: &I) -> Option<AdtId<I>> {
650 match self.kind(interner) {
651 TyKind::Adt(adt_id, _) => Some(*adt_id),
652 _ => None,
653 }
654 }
655
656 /// True if this type contains "bound" types/lifetimes, and hence
657 /// needs to be shifted across binders. This is a very inefficient
658 /// check, intended only for debug assertions, because I am lazy.
needs_shift(&self, interner: &I) -> bool659 pub fn needs_shift(&self, interner: &I) -> bool {
660 self.has_free_vars(interner)
661 }
662 }
663
664 /// Contains the data for a Ty
665 #[derive(Clone, PartialEq, Eq, Hash, HasInterner)]
666 pub struct TyData<I: Interner> {
667 /// The kind
668 pub kind: TyKind<I>,
669 /// Type flags
670 pub flags: TypeFlags,
671 }
672
673 bitflags! {
674 /// Contains flags indicating various properties of a Ty
675 pub struct TypeFlags : u16 {
676 /// Does the type contain an InferenceVar
677 const HAS_TY_INFER = 1;
678 /// Does the type contain a lifetime with an InferenceVar
679 const HAS_RE_INFER = 1 << 1;
680 /// Does the type contain a ConstValue with an InferenceVar
681 const HAS_CT_INFER = 1 << 2;
682 /// Does the type contain a Placeholder TyKind
683 const HAS_TY_PLACEHOLDER = 1 << 3;
684 /// Does the type contain a lifetime with a Placeholder
685 const HAS_RE_PLACEHOLDER = 1 << 4;
686 /// Does the type contain a ConstValue Placeholder
687 const HAS_CT_PLACEHOLDER = 1 << 5;
688 /// True when the type has free lifetimes related to a local context
689 const HAS_FREE_LOCAL_REGIONS = 1 << 6;
690 /// Does the type contain a projection of an associated type
691 const HAS_TY_PROJECTION = 1 << 7;
692 /// Does the type contain an opaque type
693 const HAS_TY_OPAQUE = 1 << 8;
694 /// Does the type contain an unevaluated const projection
695 const HAS_CT_PROJECTION = 1 << 9;
696 /// Does the type contain an error
697 const HAS_ERROR = 1 << 10;
698 /// Does the type contain any free lifetimes
699 const HAS_FREE_REGIONS = 1 << 11;
700 /// True when the type contains lifetimes that will be substituted when function is called
701 const HAS_RE_LATE_BOUND = 1 << 12;
702 /// True when the type contains an erased lifetime
703 const HAS_RE_ERASED = 1 << 13;
704 /// Does the type contain placeholders or inference variables that could be replaced later
705 const STILL_FURTHER_SPECIALIZABLE = 1 << 14;
706
707 /// True when the type contains free names local to a particular context
708 const HAS_FREE_LOCAL_NAMES = TypeFlags::HAS_TY_INFER.bits
709 | TypeFlags::HAS_CT_INFER.bits
710 | TypeFlags::HAS_TY_PLACEHOLDER.bits
711 | TypeFlags::HAS_CT_PLACEHOLDER.bits
712 | TypeFlags::HAS_FREE_LOCAL_REGIONS.bits;
713
714 /// Does the type contain any form of projection
715 const HAS_PROJECTION = TypeFlags::HAS_TY_PROJECTION.bits
716 | TypeFlags::HAS_TY_OPAQUE.bits
717 | TypeFlags::HAS_CT_PROJECTION.bits;
718 }
719 }
720 /// Type data, which holds the actual type information.
721 #[derive(Clone, PartialEq, Eq, Hash, HasInterner)]
722 pub enum TyKind<I: Interner> {
723 /// Abstract data types, i.e., structs, unions, or enumerations.
724 /// For example, a type like `Vec<T>`.
725 Adt(AdtId<I>, Substitution<I>),
726
727 /// an associated type like `Iterator::Item`; see `AssociatedType` for details
728 AssociatedType(AssocTypeId<I>, Substitution<I>),
729
730 /// a scalar type like `bool` or `u32`
731 Scalar(Scalar),
732
733 /// a tuple of the given arity
734 Tuple(usize, Substitution<I>),
735
736 /// an array type like `[T; N]`
737 Array(Ty<I>, Const<I>),
738
739 /// a slice type like `[T]`
740 Slice(Ty<I>),
741
742 /// a raw pointer type like `*const T` or `*mut T`
743 Raw(Mutability, Ty<I>),
744
745 /// a reference type like `&T` or `&mut T`
746 Ref(Mutability, Lifetime<I>, Ty<I>),
747
748 /// a placeholder for opaque types like `impl Trait`
749 OpaqueType(OpaqueTyId<I>, Substitution<I>),
750
751 /// a function definition
752 FnDef(FnDefId<I>, Substitution<I>),
753
754 /// the string primitive type
755 Str,
756
757 /// the never type `!`
758 Never,
759
760 /// A closure.
761 Closure(ClosureId<I>, Substitution<I>),
762
763 /// A generator.
764 Generator(GeneratorId<I>, Substitution<I>),
765
766 /// A generator witness.
767 GeneratorWitness(GeneratorId<I>, Substitution<I>),
768
769 /// foreign types
770 Foreign(ForeignDefId<I>),
771
772 /// This can be used to represent an error, e.g. during name resolution of a type.
773 /// Chalk itself will not produce this, just pass it through when given.
774 Error,
775
776 /// instantiated from a universally quantified type, e.g., from
777 /// `forall<T> { .. }`. Stands in as a representative of "some
778 /// unknown type".
779 Placeholder(PlaceholderIndex),
780
781 /// A "dyn" type is a trait object type created via the "dyn Trait" syntax.
782 /// In the chalk parser, the traits that the object represents is parsed as
783 /// a QuantifiedInlineBound, and is then changed to a list of where clauses
784 /// during lowering.
785 ///
786 /// See the `Opaque` variant for a discussion about the use of
787 /// binders here.
788 Dyn(DynTy<I>),
789
790 /// An "alias" type represents some form of type alias, such as:
791 /// - An associated type projection like `<T as Iterator>::Item`
792 /// - `impl Trait` types
793 /// - Named type aliases like `type Foo<X> = Vec<X>`
794 Alias(AliasTy<I>),
795
796 /// A function type such as `for<'a> fn(&'a u32)`.
797 /// Note that "higher-ranked" types (starting with `for<>`) are either
798 /// function types or dyn types, and do not appear otherwise in Rust
799 /// surface syntax.
800 Function(FnPointer<I>),
801
802 /// References the binding at the given depth. The index is a [de
803 /// Bruijn index], so it counts back through the in-scope binders.
804 BoundVar(BoundVar),
805
806 /// Inference variable defined in the current inference context.
807 InferenceVar(InferenceVar, TyVariableKind),
808 }
809
810 impl<I: Interner> Copy for TyKind<I>
811 where
812 I::InternedLifetime: Copy,
813 I::InternedSubstitution: Copy,
814 I::InternedVariableKinds: Copy,
815 I::InternedQuantifiedWhereClauses: Copy,
816 I::InternedType: Copy,
817 I::InternedConst: Copy,
818 {
819 }
820
821 impl<I: Interner> TyKind<I> {
822 /// Casts the type data to a type.
intern(self, interner: &I) -> Ty<I>823 pub fn intern(self, interner: &I) -> Ty<I> {
824 Ty::new(interner, self)
825 }
826 }
827
828 /// Identifies a particular bound variable within a binder.
829 /// Variables are identified by the combination of a [`DebruijnIndex`],
830 /// which identifies the *binder*, and an index within that binder.
831 ///
832 /// Consider this case:
833 ///
834 /// ```ignore
835 /// forall<'a, 'b> { forall<'c, 'd> { ... } }
836 /// ```
837 ///
838 /// Within the `...` term:
839 ///
840 /// * the variable `'a` have a debruijn index of 1 and index 0
841 /// * the variable `'b` have a debruijn index of 1 and index 1
842 /// * the variable `'c` have a debruijn index of 0 and index 0
843 /// * the variable `'d` have a debruijn index of 0 and index 1
844 ///
845 /// The variables `'a` and `'b` both have debruijn index of 1 because,
846 /// counting out, they are the 2nd binder enclosing `...`. The indices
847 /// identify the location *within* that binder.
848 ///
849 /// The variables `'c` and `'d` both have debruijn index of 0 because
850 /// they appear in the *innermost* binder enclosing the `...`. The
851 /// indices identify the location *within* that binder.
852 #[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
853 pub struct BoundVar {
854 /// Debruijn index, which identifies the binder.
855 pub debruijn: DebruijnIndex,
856 /// Index within the binder.
857 pub index: usize,
858 }
859
860 impl BoundVar {
861 /// Creates a new bound variable.
new(debruijn: DebruijnIndex, index: usize) -> Self862 pub fn new(debruijn: DebruijnIndex, index: usize) -> Self {
863 Self { debruijn, index }
864 }
865
866 /// Casts the bound variable to a type.
to_ty<I: Interner>(self, interner: &I) -> Ty<I>867 pub fn to_ty<I: Interner>(self, interner: &I) -> Ty<I> {
868 TyKind::<I>::BoundVar(self).intern(interner)
869 }
870
871 /// Wrap the bound variable in a lifetime.
to_lifetime<I: Interner>(self, interner: &I) -> Lifetime<I>872 pub fn to_lifetime<I: Interner>(self, interner: &I) -> Lifetime<I> {
873 LifetimeData::<I>::BoundVar(self).intern(interner)
874 }
875
876 /// Wraps the bound variable in a constant.
to_const<I: Interner>(self, interner: &I, ty: Ty<I>) -> Const<I>877 pub fn to_const<I: Interner>(self, interner: &I, ty: Ty<I>) -> Const<I> {
878 ConstData {
879 ty,
880 value: ConstValue::<I>::BoundVar(self),
881 }
882 .intern(interner)
883 }
884
885 /// True if this variable is bound within the `amount` innermost binders.
bound_within(self, outer_binder: DebruijnIndex) -> bool886 pub fn bound_within(self, outer_binder: DebruijnIndex) -> bool {
887 self.debruijn.within(outer_binder)
888 }
889
890 /// Adjusts the debruijn index (see [`DebruijnIndex::shifted_in`]).
891 #[must_use]
shifted_in(self) -> Self892 pub fn shifted_in(self) -> Self {
893 BoundVar::new(self.debruijn.shifted_in(), self.index)
894 }
895
896 /// Adjusts the debruijn index (see [`DebruijnIndex::shifted_in`]).
897 #[must_use]
shifted_in_from(self, outer_binder: DebruijnIndex) -> Self898 pub fn shifted_in_from(self, outer_binder: DebruijnIndex) -> Self {
899 BoundVar::new(self.debruijn.shifted_in_from(outer_binder), self.index)
900 }
901
902 /// Adjusts the debruijn index (see [`DebruijnIndex::shifted_in`]).
903 #[must_use]
shifted_out(self) -> Option<Self>904 pub fn shifted_out(self) -> Option<Self> {
905 self.debruijn
906 .shifted_out()
907 .map(|db| BoundVar::new(db, self.index))
908 }
909
910 /// Adjusts the debruijn index (see [`DebruijnIndex::shifted_in`]).
911 #[must_use]
shifted_out_to(self, outer_binder: DebruijnIndex) -> Option<Self>912 pub fn shifted_out_to(self, outer_binder: DebruijnIndex) -> Option<Self> {
913 self.debruijn
914 .shifted_out_to(outer_binder)
915 .map(|db| BoundVar::new(db, self.index))
916 }
917
918 /// Return the index of the bound variable, but only if it is bound
919 /// at the innermost binder. Otherwise, returns `None`.
index_if_innermost(self) -> Option<usize>920 pub fn index_if_innermost(self) -> Option<usize> {
921 self.index_if_bound_at(DebruijnIndex::INNERMOST)
922 }
923
924 /// Return the index of the bound variable, but only if it is bound
925 /// at the innermost binder. Otherwise, returns `None`.
index_if_bound_at(self, debruijn: DebruijnIndex) -> Option<usize>926 pub fn index_if_bound_at(self, debruijn: DebruijnIndex) -> Option<usize> {
927 if self.debruijn == debruijn {
928 Some(self.index)
929 } else {
930 None
931 }
932 }
933 }
934
935 /// References the binder at the given depth. The index is a [de
936 /// Bruijn index], so it counts back through the in-scope binders,
937 /// with 0 being the innermost binder. This is used in impls and
938 /// the like. For example, if we had a rule like `for<T> { (T:
939 /// Clone) :- (T: Copy) }`, then `T` would be represented as a
940 /// `BoundVar(0)` (as the `for` is the innermost binder).
941 ///
942 /// [de Bruijn index]: https://en.wikipedia.org/wiki/De_Bruijn_index
943 #[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
944 pub struct DebruijnIndex {
945 depth: u32,
946 }
947
948 impl DebruijnIndex {
949 /// Innermost index.
950 pub const INNERMOST: DebruijnIndex = DebruijnIndex { depth: 0 };
951 /// One level higher than the innermost index.
952 pub const ONE: DebruijnIndex = DebruijnIndex { depth: 1 };
953
954 /// Creates a new de Bruijn index with a given depth.
new(depth: u32) -> Self955 pub fn new(depth: u32) -> Self {
956 DebruijnIndex { depth }
957 }
958
959 /// Depth of the De Bruijn index, counting from 0 starting with
960 /// the innermost binder.
depth(self) -> u32961 pub fn depth(self) -> u32 {
962 self.depth
963 }
964
965 /// True if the binder identified by this index is within the
966 /// binder identified by the index `outer_binder`.
967 ///
968 /// # Example
969 ///
970 /// Imagine you have the following binders in scope
971 ///
972 /// ```ignore
973 /// forall<a> forall<b> forall<c>
974 /// ```
975 ///
976 /// then the Debruijn index for `c` would be `0`, the index for
977 /// `b` would be 1, and so on. Now consider the following calls:
978 ///
979 /// * `c.within(a) = true`
980 /// * `b.within(a) = true`
981 /// * `a.within(a) = false`
982 /// * `a.within(c) = false`
within(self, outer_binder: DebruijnIndex) -> bool983 pub fn within(self, outer_binder: DebruijnIndex) -> bool {
984 self < outer_binder
985 }
986
987 /// Returns the resulting index when this value is moved into
988 /// through one binder.
989 #[must_use]
shifted_in(self) -> DebruijnIndex990 pub fn shifted_in(self) -> DebruijnIndex {
991 self.shifted_in_from(DebruijnIndex::ONE)
992 }
993
994 /// Update this index in place by shifting it "in" through
995 /// `amount` number of binders.
shift_in(&mut self)996 pub fn shift_in(&mut self) {
997 *self = self.shifted_in();
998 }
999
1000 /// Adds `outer_binder` levels to the `self` index. Intuitively, this
1001 /// shifts the `self` index, which was valid at the outer binder,
1002 /// so that it is valid at the innermost binder.
1003 ///
1004 /// Example: Assume that the following binders are in scope:
1005 ///
1006 /// ```ignore
1007 /// for<A> for<B> for<C> for<D>
1008 /// ^ outer binder
1009 /// ```
1010 ///
1011 /// Assume further that the `outer_binder` argument is 2,
1012 /// which means that it is referring to the `for<B>` binder
1013 /// (since `D` would be the innermost binder).
1014 ///
1015 /// This means that `self` is relative to the binder `B` -- so
1016 /// if `self` is 0 (`INNERMOST`), then it refers to `B`,
1017 /// and if `self` is 1, then it refers to `A`.
1018 ///
1019 /// We will return as follows:
1020 ///
1021 /// * `0.shifted_in_from(2) = 2` -- i.e., `B`, when shifted in to the binding level `D`, has index 2
1022 /// * `1.shifted_in_from(2) = 3` -- i.e., `A`, when shifted in to the binding level `D`, has index 3
1023 /// * `2.shifted_in_from(1) = 3` -- here, we changed the `outer_binder` to refer to `C`.
1024 /// Therefore `2` (relative to `C`) refers to `A`, so the result is still 3 (since `A`, relative to the
1025 /// innermost binder, has index 3).
1026 #[must_use]
shifted_in_from(self, outer_binder: DebruijnIndex) -> DebruijnIndex1027 pub fn shifted_in_from(self, outer_binder: DebruijnIndex) -> DebruijnIndex {
1028 DebruijnIndex::new(self.depth() + outer_binder.depth())
1029 }
1030
1031 /// Returns the resulting index when this value is moved out from
1032 /// `amount` number of new binders.
1033 #[must_use]
shifted_out(self) -> Option<DebruijnIndex>1034 pub fn shifted_out(self) -> Option<DebruijnIndex> {
1035 self.shifted_out_to(DebruijnIndex::ONE)
1036 }
1037
1038 /// Update in place by shifting out from `amount` binders.
shift_out(&mut self)1039 pub fn shift_out(&mut self) {
1040 *self = self.shifted_out().unwrap();
1041 }
1042
1043 /// Subtracts `outer_binder` levels from the `self` index. Intuitively, this
1044 /// shifts the `self` index, which was valid at the innermost
1045 /// binder, to one that is valid at the binder `outer_binder`.
1046 ///
1047 /// This will return `None` if the `self` index is internal to the
1048 /// outer binder (i.e., if `self < outer_binder`).
1049 ///
1050 /// Example: Assume that the following binders are in scope:
1051 ///
1052 /// ```ignore
1053 /// for<A> for<B> for<C> for<D>
1054 /// ^ outer binder
1055 /// ```
1056 ///
1057 /// Assume further that the `outer_binder` argument is 2,
1058 /// which means that it is referring to the `for<B>` binder
1059 /// (since `D` would be the innermost binder).
1060 ///
1061 /// This means that the result is relative to the binder `B` -- so
1062 /// if `self` is 0 (`INNERMOST`), then it refers to `B`,
1063 /// and if `self` is 1, then it refers to `A`.
1064 ///
1065 /// We will return as follows:
1066 ///
1067 /// * `1.shifted_out_to(2) = None` -- i.e., the binder for `C` can't be named from the binding level `B`
1068 /// * `3.shifted_out_to(2) = Some(1)` -- i.e., `A`, when shifted out to the binding level `B`, has index 1
shifted_out_to(self, outer_binder: DebruijnIndex) -> Option<DebruijnIndex>1069 pub fn shifted_out_to(self, outer_binder: DebruijnIndex) -> Option<DebruijnIndex> {
1070 if self.within(outer_binder) {
1071 None
1072 } else {
1073 Some(DebruijnIndex::new(self.depth() - outer_binder.depth()))
1074 }
1075 }
1076 }
1077
1078 /// A "DynTy" represents a trait object (`dyn Trait`). Trait objects
1079 /// are conceptually very related to an "existential type" of the form
1080 /// `exists<T> { T: Trait }` (another example of such type is `impl Trait`).
1081 /// `DynTy` represents the bounds on that type.
1082 ///
1083 /// The "bounds" here represents the unknown self type. So, a type like
1084 /// `dyn for<'a> Fn(&'a u32)` would be represented with two-levels of
1085 /// binder, as "depicted" here:
1086 ///
1087 /// ```notrust
1088 /// exists<type> {
1089 /// vec![
1090 /// // A QuantifiedWhereClause:
1091 /// forall<region> { ^1.0: Fn(&^0.0 u32) }
1092 /// ]
1093 /// }
1094 /// ```
1095 ///
1096 /// The outer `exists<type>` binder indicates that there exists
1097 /// some type that meets the criteria within, but that type is not
1098 /// known. It is referenced within the type using `^1.0`, indicating
1099 /// a bound type with debruijn index 1 (i.e., skipping through one
1100 /// level of binder).
1101 #[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, HasInterner)]
1102 pub struct DynTy<I: Interner> {
1103 /// The unknown self type.
1104 pub bounds: Binders<QuantifiedWhereClauses<I>>,
1105 /// Lifetime of the `DynTy`.
1106 pub lifetime: Lifetime<I>,
1107 }
1108
1109 impl<I: Interner> Copy for DynTy<I>
1110 where
1111 I::InternedLifetime: Copy,
1112 I::InternedQuantifiedWhereClauses: Copy,
1113 I::InternedVariableKinds: Copy,
1114 {
1115 }
1116
1117 /// A type, lifetime or constant whose value is being inferred.
1118 #[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
1119 pub struct InferenceVar {
1120 index: u32,
1121 }
1122
1123 impl From<u32> for InferenceVar {
from(index: u32) -> InferenceVar1124 fn from(index: u32) -> InferenceVar {
1125 InferenceVar { index }
1126 }
1127 }
1128
1129 impl InferenceVar {
1130 /// Gets the underlying index value.
index(self) -> u321131 pub fn index(self) -> u32 {
1132 self.index
1133 }
1134
1135 /// Wraps the inference variable in a type.
to_ty<I: Interner>(self, interner: &I, kind: TyVariableKind) -> Ty<I>1136 pub fn to_ty<I: Interner>(self, interner: &I, kind: TyVariableKind) -> Ty<I> {
1137 TyKind::<I>::InferenceVar(self, kind).intern(interner)
1138 }
1139
1140 /// Wraps the inference variable in a lifetime.
to_lifetime<I: Interner>(self, interner: &I) -> Lifetime<I>1141 pub fn to_lifetime<I: Interner>(self, interner: &I) -> Lifetime<I> {
1142 LifetimeData::<I>::InferenceVar(self).intern(interner)
1143 }
1144
1145 /// Wraps the inference variable in a constant.
to_const<I: Interner>(self, interner: &I, ty: Ty<I>) -> Const<I>1146 pub fn to_const<I: Interner>(self, interner: &I, ty: Ty<I>) -> Const<I> {
1147 ConstData {
1148 ty,
1149 value: ConstValue::<I>::InferenceVar(self),
1150 }
1151 .intern(interner)
1152 }
1153 }
1154
1155 /// A function signature.
1156 #[derive(Clone, Copy, PartialEq, Eq, Hash, HasInterner, Debug)]
1157 #[allow(missing_docs)]
1158 pub struct FnSig<I: Interner> {
1159 pub abi: I::FnAbi,
1160 pub safety: Safety,
1161 pub variadic: bool,
1162 }
1163 /// A wrapper for the substs on a Fn.
1164 #[derive(Clone, PartialEq, Eq, Hash, HasInterner, Fold, Visit)]
1165 pub struct FnSubst<I: Interner>(pub Substitution<I>);
1166
1167 impl<I: Interner> Copy for FnSubst<I> where I::InternedSubstitution: Copy {}
1168
1169 /// for<'a...'z> X -- all binders are instantiated at once,
1170 /// and we use deBruijn indices within `self.ty`
1171 #[derive(Clone, PartialEq, Eq, Hash, HasInterner)]
1172 #[allow(missing_docs)]
1173 pub struct FnPointer<I: Interner> {
1174 pub num_binders: usize,
1175 pub sig: FnSig<I>,
1176 pub substitution: FnSubst<I>,
1177 }
1178
1179 impl<I: Interner> Copy for FnPointer<I> where I::InternedSubstitution: Copy {}
1180
1181 impl<I: Interner> FnPointer<I> {
1182 /// Represent the current `Fn` as if it was wrapped in `Binders`
into_binders(self, interner: &I) -> Binders<FnSubst<I>>1183 pub fn into_binders(self, interner: &I) -> Binders<FnSubst<I>> {
1184 Binders::new(
1185 VariableKinds::from_iter(
1186 interner,
1187 (0..self.num_binders).map(|_| VariableKind::Lifetime),
1188 ),
1189 self.substitution,
1190 )
1191 }
1192
1193 /// Represent the current `Fn` as if it was wrapped in `Binders`
as_binders(&self, interner: &I) -> Binders<&FnSubst<I>>1194 pub fn as_binders(&self, interner: &I) -> Binders<&FnSubst<I>> {
1195 Binders::new(
1196 VariableKinds::from_iter(
1197 interner,
1198 (0..self.num_binders).map(|_| VariableKind::Lifetime),
1199 ),
1200 &self.substitution,
1201 )
1202 }
1203 }
1204
1205 /// Constants.
1206 #[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, HasInterner)]
1207 pub struct Const<I: Interner> {
1208 interned: I::InternedConst,
1209 }
1210
1211 impl<I: Interner> Const<I> {
1212 /// Create a `Const` using something that can be cast to const data.
new(interner: &I, data: impl CastTo<ConstData<I>>) -> Self1213 pub fn new(interner: &I, data: impl CastTo<ConstData<I>>) -> Self {
1214 Const {
1215 interned: I::intern_const(interner, data.cast(interner)),
1216 }
1217 }
1218
1219 /// Gets the interned constant.
interned(&self) -> &I::InternedConst1220 pub fn interned(&self) -> &I::InternedConst {
1221 &self.interned
1222 }
1223
1224 /// Gets the constant data from the interner.
data(&self, interner: &I) -> &ConstData<I>1225 pub fn data(&self, interner: &I) -> &ConstData<I> {
1226 I::const_data(interner, &self.interned)
1227 }
1228
1229 /// If this is a `ConstData::BoundVar(d)`, returns `Some(d)` else `None`.
bound_var(&self, interner: &I) -> Option<BoundVar>1230 pub fn bound_var(&self, interner: &I) -> Option<BoundVar> {
1231 if let ConstValue::BoundVar(bv) = &self.data(interner).value {
1232 Some(*bv)
1233 } else {
1234 None
1235 }
1236 }
1237
1238 /// If this is a `ConstData::InferenceVar(d)`, returns `Some(d)` else `None`.
inference_var(&self, interner: &I) -> Option<InferenceVar>1239 pub fn inference_var(&self, interner: &I) -> Option<InferenceVar> {
1240 if let ConstValue::InferenceVar(iv) = &self.data(interner).value {
1241 Some(*iv)
1242 } else {
1243 None
1244 }
1245 }
1246
1247 /// True if this const is a "bound" const, and hence
1248 /// needs to be shifted across binders. Meant for debug assertions.
needs_shift(&self, interner: &I) -> bool1249 pub fn needs_shift(&self, interner: &I) -> bool {
1250 match &self.data(interner).value {
1251 ConstValue::BoundVar(_) => true,
1252 ConstValue::InferenceVar(_) => false,
1253 ConstValue::Placeholder(_) => false,
1254 ConstValue::Concrete(_) => false,
1255 }
1256 }
1257 }
1258
1259 /// Constant data, containing the constant's type and value.
1260 #[derive(Clone, PartialEq, Eq, Hash, HasInterner)]
1261 pub struct ConstData<I: Interner> {
1262 /// Type that holds the constant.
1263 pub ty: Ty<I>,
1264 /// The value of the constant.
1265 pub value: ConstValue<I>,
1266 }
1267
1268 /// A constant value, not necessarily concrete.
1269 #[derive(Clone, PartialEq, Eq, Hash, HasInterner)]
1270 pub enum ConstValue<I: Interner> {
1271 /// Bound var (e.g. a parameter).
1272 BoundVar(BoundVar),
1273 /// Constant whose value is being inferred.
1274 InferenceVar(InferenceVar),
1275 /// Lifetime on some yet-unknown placeholder.
1276 Placeholder(PlaceholderIndex),
1277 /// Concrete constant value.
1278 Concrete(ConcreteConst<I>),
1279 }
1280
1281 impl<I: Interner> Copy for ConstValue<I> where I::InternedConcreteConst: Copy {}
1282
1283 impl<I: Interner> ConstData<I> {
1284 /// Wraps the constant data in a `Const`.
intern(self, interner: &I) -> Const<I>1285 pub fn intern(self, interner: &I) -> Const<I> {
1286 Const::new(interner, self)
1287 }
1288 }
1289
1290 /// Concrete constant, whose value is known (as opposed to
1291 /// inferred constants and placeholders).
1292 #[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, HasInterner)]
1293 pub struct ConcreteConst<I: Interner> {
1294 /// The interned constant.
1295 pub interned: I::InternedConcreteConst,
1296 }
1297
1298 impl<I: Interner> ConcreteConst<I> {
1299 /// Checks whether two concrete constants are equal.
const_eq(&self, ty: &Ty<I>, other: &ConcreteConst<I>, interner: &I) -> bool1300 pub fn const_eq(&self, ty: &Ty<I>, other: &ConcreteConst<I>, interner: &I) -> bool {
1301 interner.const_eq(&ty.interned, &self.interned, &other.interned)
1302 }
1303 }
1304
1305 /// A Rust lifetime.
1306 #[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, HasInterner)]
1307 pub struct Lifetime<I: Interner> {
1308 interned: I::InternedLifetime,
1309 }
1310
1311 impl<I: Interner> Lifetime<I> {
1312 /// Create a lifetime from lifetime data
1313 /// (or something that can be cast to lifetime data).
new(interner: &I, data: impl CastTo<LifetimeData<I>>) -> Self1314 pub fn new(interner: &I, data: impl CastTo<LifetimeData<I>>) -> Self {
1315 Lifetime {
1316 interned: I::intern_lifetime(interner, data.cast(interner)),
1317 }
1318 }
1319
1320 /// Gets the interned value.
interned(&self) -> &I::InternedLifetime1321 pub fn interned(&self) -> &I::InternedLifetime {
1322 &self.interned
1323 }
1324
1325 /// Gets the lifetime data.
data(&self, interner: &I) -> &LifetimeData<I>1326 pub fn data(&self, interner: &I) -> &LifetimeData<I> {
1327 I::lifetime_data(interner, &self.interned)
1328 }
1329
1330 /// If this is a `Lifetime::BoundVar(d)`, returns `Some(d)` else `None`.
bound_var(&self, interner: &I) -> Option<BoundVar>1331 pub fn bound_var(&self, interner: &I) -> Option<BoundVar> {
1332 if let LifetimeData::BoundVar(bv) = self.data(interner) {
1333 Some(*bv)
1334 } else {
1335 None
1336 }
1337 }
1338
1339 /// If this is a `Lifetime::InferenceVar(d)`, returns `Some(d)` else `None`.
inference_var(&self, interner: &I) -> Option<InferenceVar>1340 pub fn inference_var(&self, interner: &I) -> Option<InferenceVar> {
1341 if let LifetimeData::InferenceVar(depth) = self.data(interner) {
1342 Some(*depth)
1343 } else {
1344 None
1345 }
1346 }
1347
1348 /// True if this lifetime is a "bound" lifetime, and hence
1349 /// needs to be shifted across binders. Meant for debug assertions.
needs_shift(&self, interner: &I) -> bool1350 pub fn needs_shift(&self, interner: &I) -> bool {
1351 match self.data(interner) {
1352 LifetimeData::BoundVar(_) => true,
1353 LifetimeData::InferenceVar(_) => false,
1354 LifetimeData::Placeholder(_) => false,
1355 LifetimeData::Static => false,
1356 LifetimeData::Empty(_) => false,
1357 LifetimeData::Erased => false,
1358 LifetimeData::Phantom(..) => unreachable!(),
1359 }
1360 }
1361 }
1362
1363 /// Lifetime data, including what kind of lifetime it is and what it points to.
1364 #[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, HasInterner)]
1365 pub enum LifetimeData<I: Interner> {
1366 /// See TyKind::BoundVar.
1367 BoundVar(BoundVar),
1368 /// Lifetime whose value is being inferred.
1369 InferenceVar(InferenceVar),
1370 /// Lifetime on some yet-unknown placeholder.
1371 Placeholder(PlaceholderIndex),
1372 /// Static lifetime
1373 Static,
1374 /// An empty lifetime: a lifetime shorter than any other lifetime in a
1375 /// universe with a lesser or equal index. The universe only non-zero in
1376 /// lexical region resolve in rustc, so chalk shouldn't ever see a non-zero
1377 /// index.
1378 Empty(UniverseIndex),
1379 /// An erased lifetime, used by rustc to improve caching when we doesn't
1380 /// care about lifetimes
1381 Erased,
1382 /// Lifetime on phantom data.
1383 Phantom(Void, PhantomData<I>),
1384 }
1385
1386 impl<I: Interner> LifetimeData<I> {
1387 /// Wrap the lifetime data in a lifetime.
intern(self, interner: &I) -> Lifetime<I>1388 pub fn intern(self, interner: &I) -> Lifetime<I> {
1389 Lifetime::new(interner, self)
1390 }
1391 }
1392
1393 /// Index of an universally quantified parameter in the environment.
1394 /// Two indexes are required, the one of the universe itself
1395 /// and the relative index inside the universe.
1396 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
1397 pub struct PlaceholderIndex {
1398 /// Index *of* the universe.
1399 pub ui: UniverseIndex,
1400 /// Index *in* the universe.
1401 pub idx: usize,
1402 }
1403
1404 impl PlaceholderIndex {
1405 /// Wrap the placeholder instance in a lifetime.
to_lifetime<I: Interner>(self, interner: &I) -> Lifetime<I>1406 pub fn to_lifetime<I: Interner>(self, interner: &I) -> Lifetime<I> {
1407 LifetimeData::<I>::Placeholder(self).intern(interner)
1408 }
1409
1410 /// Create an interned type.
to_ty<I: Interner>(self, interner: &I) -> Ty<I>1411 pub fn to_ty<I: Interner>(self, interner: &I) -> Ty<I> {
1412 TyKind::Placeholder(self).intern(interner)
1413 }
1414
1415 /// Wrap the placeholder index in a constant.
to_const<I: Interner>(self, interner: &I, ty: Ty<I>) -> Const<I>1416 pub fn to_const<I: Interner>(self, interner: &I, ty: Ty<I>) -> Const<I> {
1417 ConstData {
1418 ty,
1419 value: ConstValue::Placeholder(self),
1420 }
1421 .intern(interner)
1422 }
1423 }
1424 /// Represents some extra knowledge we may have about the type variable.
1425 /// ```ignore
1426 /// let x: &[u32];
1427 /// let i = 1;
1428 /// x[i]
1429 /// ```
1430 /// In this example, `i` is known to be some type of integer. We can infer that
1431 /// it is `usize` because that is the only integer type that slices have an
1432 /// `Index` impl for. `i` would have a `TyVariableKind` of `Integer` to guide the
1433 /// inference process.
1434 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
1435 #[allow(missing_docs)]
1436 pub enum TyVariableKind {
1437 General,
1438 Integer,
1439 Float,
1440 }
1441
1442 /// The "kind" of variable. Type, lifetime or constant.
1443 #[derive(Clone, PartialEq, Eq, Hash)]
1444 #[allow(missing_docs)]
1445 pub enum VariableKind<I: Interner> {
1446 Ty(TyVariableKind),
1447 Lifetime,
1448 Const(Ty<I>),
1449 }
1450
1451 impl<I: Interner> interner::HasInterner for VariableKind<I> {
1452 type Interner = I;
1453 }
1454
1455 impl<I: Interner> Copy for VariableKind<I> where I::InternedType: Copy {}
1456
1457 impl<I: Interner> VariableKind<I> {
to_bound_variable(&self, interner: &I, bound_var: BoundVar) -> GenericArg<I>1458 fn to_bound_variable(&self, interner: &I, bound_var: BoundVar) -> GenericArg<I> {
1459 match self {
1460 VariableKind::Ty(_) => {
1461 GenericArgData::Ty(TyKind::BoundVar(bound_var).intern(interner)).intern(interner)
1462 }
1463 VariableKind::Lifetime => {
1464 GenericArgData::Lifetime(LifetimeData::BoundVar(bound_var).intern(interner))
1465 .intern(interner)
1466 }
1467 VariableKind::Const(ty) => GenericArgData::Const(
1468 ConstData {
1469 ty: ty.clone(),
1470 value: ConstValue::BoundVar(bound_var),
1471 }
1472 .intern(interner),
1473 )
1474 .intern(interner),
1475 }
1476 }
1477 }
1478
1479 /// A generic argument, see `GenericArgData` for more information.
1480 #[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, HasInterner)]
1481 pub struct GenericArg<I: Interner> {
1482 interned: I::InternedGenericArg,
1483 }
1484
1485 impl<I: Interner> GenericArg<I> {
1486 /// Constructs a generic argument using `GenericArgData`.
new(interner: &I, data: GenericArgData<I>) -> Self1487 pub fn new(interner: &I, data: GenericArgData<I>) -> Self {
1488 let interned = I::intern_generic_arg(interner, data);
1489 GenericArg { interned }
1490 }
1491
1492 /// Gets the interned value.
interned(&self) -> &I::InternedGenericArg1493 pub fn interned(&self) -> &I::InternedGenericArg {
1494 &self.interned
1495 }
1496
1497 /// Gets the underlying data.
data(&self, interner: &I) -> &GenericArgData<I>1498 pub fn data(&self, interner: &I) -> &GenericArgData<I> {
1499 I::generic_arg_data(interner, &self.interned)
1500 }
1501
1502 /// Asserts that this is a type argument.
assert_ty_ref(&self, interner: &I) -> &Ty<I>1503 pub fn assert_ty_ref(&self, interner: &I) -> &Ty<I> {
1504 self.ty(interner).unwrap()
1505 }
1506
1507 /// Asserts that this is a lifetime argument.
assert_lifetime_ref(&self, interner: &I) -> &Lifetime<I>1508 pub fn assert_lifetime_ref(&self, interner: &I) -> &Lifetime<I> {
1509 self.lifetime(interner).unwrap()
1510 }
1511
1512 /// Asserts that this is a constant argument.
assert_const_ref(&self, interner: &I) -> &Const<I>1513 pub fn assert_const_ref(&self, interner: &I) -> &Const<I> {
1514 self.constant(interner).unwrap()
1515 }
1516
1517 /// Checks whether the generic argument is a type.
is_ty(&self, interner: &I) -> bool1518 pub fn is_ty(&self, interner: &I) -> bool {
1519 match self.data(interner) {
1520 GenericArgData::Ty(_) => true,
1521 GenericArgData::Lifetime(_) => false,
1522 GenericArgData::Const(_) => false,
1523 }
1524 }
1525
1526 /// Returns the type if it is one, `None` otherwise.
ty(&self, interner: &I) -> Option<&Ty<I>>1527 pub fn ty(&self, interner: &I) -> Option<&Ty<I>> {
1528 match self.data(interner) {
1529 GenericArgData::Ty(t) => Some(t),
1530 _ => None,
1531 }
1532 }
1533
1534 /// Returns the lifetime if it is one, `None` otherwise.
lifetime(&self, interner: &I) -> Option<&Lifetime<I>>1535 pub fn lifetime(&self, interner: &I) -> Option<&Lifetime<I>> {
1536 match self.data(interner) {
1537 GenericArgData::Lifetime(t) => Some(t),
1538 _ => None,
1539 }
1540 }
1541
1542 /// Returns the constant if it is one, `None` otherwise.
constant(&self, interner: &I) -> Option<&Const<I>>1543 pub fn constant(&self, interner: &I) -> Option<&Const<I>> {
1544 match self.data(interner) {
1545 GenericArgData::Const(c) => Some(c),
1546 _ => None,
1547 }
1548 }
1549 }
1550
1551 /// Generic arguments data.
1552 #[derive(Clone, PartialEq, Eq, Hash, Visit, Fold, Zip)]
1553 pub enum GenericArgData<I: Interner> {
1554 /// Type argument
1555 Ty(Ty<I>),
1556 /// Lifetime argument
1557 Lifetime(Lifetime<I>),
1558 /// Constant argument
1559 Const(Const<I>),
1560 }
1561
1562 impl<I: Interner> Copy for GenericArgData<I>
1563 where
1564 I::InternedType: Copy,
1565 I::InternedLifetime: Copy,
1566 I::InternedConst: Copy,
1567 {
1568 }
1569
1570 impl<I: Interner> GenericArgData<I> {
1571 /// Create an interned type.
intern(self, interner: &I) -> GenericArg<I>1572 pub fn intern(self, interner: &I) -> GenericArg<I> {
1573 GenericArg::new(interner, self)
1574 }
1575 }
1576
1577 /// A value with an associated variable kind.
1578 #[derive(Clone, PartialEq, Eq, Hash)]
1579 pub struct WithKind<I: Interner, T> {
1580 /// The associated variable kind.
1581 pub kind: VariableKind<I>,
1582 /// The wrapped value.
1583 value: T,
1584 }
1585
1586 impl<I: Interner, T: Copy> Copy for WithKind<I, T> where I::InternedType: Copy {}
1587
1588 impl<I: Interner, T> HasInterner for WithKind<I, T> {
1589 type Interner = I;
1590 }
1591
1592 impl<I: Interner, T> From<WithKind<I, T>> for (VariableKind<I>, T) {
from(with_kind: WithKind<I, T>) -> Self1593 fn from(with_kind: WithKind<I, T>) -> Self {
1594 (with_kind.kind, with_kind.value)
1595 }
1596 }
1597
1598 impl<I: Interner, T> WithKind<I, T> {
1599 /// Creates a `WithKind` from a variable kind and a value.
new(kind: VariableKind<I>, value: T) -> Self1600 pub fn new(kind: VariableKind<I>, value: T) -> Self {
1601 Self { kind, value }
1602 }
1603
1604 /// Maps the value in `WithKind`.
map<U, OP>(self, op: OP) -> WithKind<I, U> where OP: FnOnce(T) -> U,1605 pub fn map<U, OP>(self, op: OP) -> WithKind<I, U>
1606 where
1607 OP: FnOnce(T) -> U,
1608 {
1609 WithKind {
1610 kind: self.kind,
1611 value: op(self.value),
1612 }
1613 }
1614
1615 /// Maps a function taking `WithKind<I, &T>` over `&WithKind<I, T>`.
map_ref<U, OP>(&self, op: OP) -> WithKind<I, U> where OP: FnOnce(&T) -> U,1616 pub fn map_ref<U, OP>(&self, op: OP) -> WithKind<I, U>
1617 where
1618 OP: FnOnce(&T) -> U,
1619 {
1620 WithKind {
1621 kind: self.kind.clone(),
1622 value: op(&self.value),
1623 }
1624 }
1625
1626 /// Extract the value, ignoring the variable kind.
skip_kind(&self) -> &T1627 pub fn skip_kind(&self) -> &T {
1628 &self.value
1629 }
1630 }
1631
1632 /// A variable kind with universe index.
1633 #[allow(type_alias_bounds)]
1634 pub type CanonicalVarKind<I: Interner> = WithKind<I, UniverseIndex>;
1635
1636 /// An alias, which is a trait indirection such as a projection or opaque type.
1637 #[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, HasInterner, Zip)]
1638 pub enum AliasTy<I: Interner> {
1639 /// An associated type projection.
1640 Projection(ProjectionTy<I>),
1641 /// An opaque type.
1642 Opaque(OpaqueTy<I>),
1643 }
1644
1645 impl<I: Interner> Copy for AliasTy<I> where I::InternedSubstitution: Copy {}
1646
1647 impl<I: Interner> AliasTy<I> {
1648 /// Create an interned type for this alias.
intern(self, interner: &I) -> Ty<I>1649 pub fn intern(self, interner: &I) -> Ty<I> {
1650 Ty::new(interner, self)
1651 }
1652
1653 /// Gets the type parameters of the `Self` type in this alias type.
self_type_parameter(&self, interner: &I) -> Ty<I>1654 pub fn self_type_parameter(&self, interner: &I) -> Ty<I> {
1655 match self {
1656 AliasTy::Projection(projection_ty) => projection_ty.self_type_parameter(interner),
1657 _ => todo!(),
1658 }
1659 }
1660 }
1661
1662 /// A projection `<P0 as TraitName<P1..Pn>>::AssocItem<Pn+1..Pm>`.
1663 #[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, HasInterner)]
1664 pub struct ProjectionTy<I: Interner> {
1665 /// The id for the associated type member.
1666 pub associated_ty_id: AssocTypeId<I>,
1667 /// The substitution for the projection.
1668 pub substitution: Substitution<I>,
1669 }
1670
1671 impl<I: Interner> Copy for ProjectionTy<I> where I::InternedSubstitution: Copy {}
1672
1673 impl<I: Interner> ProjectionTy<I> {
1674 /// Gets the type parameters of the `Self` type in this alias type.
self_type_parameter(&self, interner: &I) -> Ty<I>1675 pub fn self_type_parameter(&self, interner: &I) -> Ty<I> {
1676 self.substitution
1677 .iter(interner)
1678 .find_map(move |p| p.ty(interner))
1679 .unwrap()
1680 .clone()
1681 }
1682 }
1683
1684 /// An opaque type `opaque type T<..>: Trait = HiddenTy`.
1685 #[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, HasInterner)]
1686 pub struct OpaqueTy<I: Interner> {
1687 /// The id for the opaque type.
1688 pub opaque_ty_id: OpaqueTyId<I>,
1689 /// The substitution for the opaque type.
1690 pub substitution: Substitution<I>,
1691 }
1692
1693 impl<I: Interner> Copy for OpaqueTy<I> where I::InternedSubstitution: Copy {}
1694
1695 /// A trait reference describes the relationship between a type and a trait.
1696 /// This can be used in two forms:
1697 /// - `P0: Trait<P1..Pn>` (e.g. `i32: Copy`), which mentions that the type
1698 /// implements the trait.
1699 /// - `<P0 as Trait<P1..Pn>>` (e.g. `i32 as Copy`), which casts the type to
1700 /// that specific trait.
1701 #[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, HasInterner)]
1702 pub struct TraitRef<I: Interner> {
1703 /// The trait id.
1704 pub trait_id: TraitId<I>,
1705 /// The substitution, containing both the `Self` type and the parameters.
1706 pub substitution: Substitution<I>,
1707 }
1708
1709 impl<I: Interner> Copy for TraitRef<I> where I::InternedSubstitution: Copy {}
1710
1711 impl<I: Interner> TraitRef<I> {
1712 /// Gets all type parameters in this trait ref, including `Self`.
type_parameters<'a>(&'a self, interner: &'a I) -> impl Iterator<Item = Ty<I>> + 'a1713 pub fn type_parameters<'a>(&'a self, interner: &'a I) -> impl Iterator<Item = Ty<I>> + 'a {
1714 self.substitution
1715 .iter(interner)
1716 .filter_map(move |p| p.ty(interner))
1717 .cloned()
1718 }
1719
1720 /// Gets the type parameters of the `Self` type in this trait ref.
self_type_parameter(&self, interner: &I) -> Ty<I>1721 pub fn self_type_parameter(&self, interner: &I) -> Ty<I> {
1722 self.type_parameters(interner).next().unwrap()
1723 }
1724
1725 /// Construct a `FromEnv` using this trait ref.
from_env(self) -> FromEnv<I>1726 pub fn from_env(self) -> FromEnv<I> {
1727 FromEnv::Trait(self)
1728 }
1729
1730 /// Construct a `WellFormed` using this trait ref.
well_formed(self) -> WellFormed<I>1731 pub fn well_formed(self) -> WellFormed<I> {
1732 WellFormed::Trait(self)
1733 }
1734 }
1735
1736 /// Lifetime outlives, which for `'a: 'b`` checks that the lifetime `'a`
1737 /// is a superset of the value of `'b`.
1738 #[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, HasInterner, Zip)]
1739 #[allow(missing_docs)]
1740 pub struct LifetimeOutlives<I: Interner> {
1741 pub a: Lifetime<I>,
1742 pub b: Lifetime<I>,
1743 }
1744
1745 impl<I: Interner> Copy for LifetimeOutlives<I> where I::InternedLifetime: Copy {}
1746
1747 /// Type outlives, which for `T: 'a` checks that the type `T`
1748 /// lives at least as long as the lifetime `'a`
1749 #[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, HasInterner, Zip)]
1750 pub struct TypeOutlives<I: Interner> {
1751 /// The type which must outlive the given lifetime.
1752 pub ty: Ty<I>,
1753 /// The lifetime which the type must outlive.
1754 pub lifetime: Lifetime<I>,
1755 }
1756
1757 impl<I: Interner> Copy for TypeOutlives<I>
1758 where
1759 I::InternedLifetime: Copy,
1760 I::InternedType: Copy,
1761 {
1762 }
1763
1764 /// Where clauses that can be written by a Rust programmer.
1765 #[derive(Clone, PartialEq, Eq, Hash, Fold, SuperVisit, HasInterner, Zip)]
1766 pub enum WhereClause<I: Interner> {
1767 /// Type implements a trait.
1768 Implemented(TraitRef<I>),
1769 /// Type is equal to an alias.
1770 AliasEq(AliasEq<I>),
1771 /// One lifetime outlives another.
1772 LifetimeOutlives(LifetimeOutlives<I>),
1773 /// Type outlives a lifetime.
1774 TypeOutlives(TypeOutlives<I>),
1775 }
1776
1777 impl<I: Interner> Copy for WhereClause<I>
1778 where
1779 I::InternedSubstitution: Copy,
1780 I::InternedLifetime: Copy,
1781 I::InternedType: Copy,
1782 {
1783 }
1784
1785 /// Checks whether a type or trait ref is well-formed.
1786 #[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, HasInterner, Zip)]
1787 pub enum WellFormed<I: Interner> {
1788 /// A predicate which is true when some trait ref is well-formed.
1789 /// For example, given the following trait definitions:
1790 ///
1791 /// ```notrust
1792 /// trait Clone { ... }
1793 /// trait Copy where Self: Clone { ... }
1794 /// ```
1795 ///
1796 /// then we have the following rule:
1797 ///
1798 /// ```notrust
1799 /// WellFormed(?Self: Copy) :- ?Self: Copy, WellFormed(?Self: Clone)
1800 /// ```
1801 Trait(TraitRef<I>),
1802
1803 /// A predicate which is true when some type is well-formed.
1804 /// For example, given the following type definition:
1805 ///
1806 /// ```notrust
1807 /// struct Set<K> where K: Hash {
1808 /// ...
1809 /// }
1810 /// ```
1811 ///
1812 /// then we have the following rule: `WellFormedTy(Set<K>) :- Implemented(K: Hash)`.
1813 Ty(Ty<I>),
1814 }
1815
1816 impl<I: Interner> Copy for WellFormed<I>
1817 where
1818 I::InternedType: Copy,
1819 I::InternedSubstitution: Copy,
1820 {
1821 }
1822
1823 /// Checks whether a type or trait ref can be derived from the contents of the environment.
1824 #[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, HasInterner, Zip)]
1825 pub enum FromEnv<I: Interner> {
1826 /// A predicate which enables deriving everything which should be true if we *know* that
1827 /// some trait ref is well-formed. For example given the above trait definitions, we can use
1828 /// `FromEnv(T: Copy)` to derive that `T: Clone`, like in:
1829 ///
1830 /// ```notrust
1831 /// forall<T> {
1832 /// if (FromEnv(T: Copy)) {
1833 /// T: Clone
1834 /// }
1835 /// }
1836 /// ```
1837 Trait(TraitRef<I>),
1838
1839 /// A predicate which enables deriving everything which should be true if we *know* that
1840 /// some type is well-formed. For example given the above type definition, we can use
1841 /// `FromEnv(Set<K>)` to derive that `K: Hash`, like in:
1842 ///
1843 /// ```notrust
1844 /// forall<K> {
1845 /// if (FromEnv(Set<K>)) {
1846 /// K: Hash
1847 /// }
1848 /// }
1849 /// ```
1850 Ty(Ty<I>),
1851 }
1852
1853 impl<I: Interner> Copy for FromEnv<I>
1854 where
1855 I::InternedType: Copy,
1856 I::InternedSubstitution: Copy,
1857 {
1858 }
1859
1860 /// A "domain goal" is a goal that is directly about Rust, rather than a pure
1861 /// logical statement. As much as possible, the Chalk solver should avoid
1862 /// decomposing this enum, and instead treat its values opaquely.
1863 #[derive(Clone, PartialEq, Eq, Hash, Fold, SuperVisit, HasInterner, Zip)]
1864 pub enum DomainGoal<I: Interner> {
1865 /// Simple goal that is true if the where clause is true.
1866 Holds(WhereClause<I>),
1867
1868 /// True if the type or trait ref is well-formed.
1869 WellFormed(WellFormed<I>),
1870
1871 /// True if the trait ref can be derived from in-scope where clauses.
1872 FromEnv(FromEnv<I>),
1873
1874 /// True if the alias type can be normalized to some other type
1875 Normalize(Normalize<I>),
1876
1877 /// True if a type is considered to have been "defined" by the current crate. This is true for
1878 /// a `struct Foo { }` but false for a `#[upstream] struct Foo { }`. However, for fundamental types
1879 /// like `Box<T>`, it is true if `T` is local.
1880 IsLocal(Ty<I>),
1881
1882 /// True if a type is *not* considered to have been "defined" by the current crate. This is
1883 /// false for a `struct Foo { }` but true for a `#[upstream] struct Foo { }`. However, for
1884 /// fundamental types like `Box<T>`, it is true if `T` is upstream.
1885 IsUpstream(Ty<I>),
1886
1887 /// True if a type and its input types are fully visible, known types. That is, there are no
1888 /// unknown type parameters anywhere in this type.
1889 ///
1890 /// More formally, for each struct S<P0..Pn>:
1891 /// forall<P0..Pn> {
1892 /// IsFullyVisible(S<P0...Pn>) :-
1893 /// IsFullyVisible(P0),
1894 /// ...
1895 /// IsFullyVisible(Pn)
1896 /// }
1897 ///
1898 /// Note that any of these types can have lifetimes in their parameters too, but we only
1899 /// consider type parameters.
1900 IsFullyVisible(Ty<I>),
1901
1902 /// Used to dictate when trait impls are allowed in the current (local) crate based on the
1903 /// orphan rules.
1904 ///
1905 /// `LocalImplAllowed(T: Trait)` is true if the type T is allowed to impl trait Trait in
1906 /// the current crate. Under the current rules, this is unconditionally true for all types if
1907 /// the Trait is considered to be "defined" in the current crate. If that is not the case, then
1908 /// `LocalImplAllowed(T: Trait)` can still be true if `IsLocal(T)` is true.
1909 LocalImplAllowed(TraitRef<I>),
1910
1911 /// Used to activate the "compatible modality" rules. Rules that introduce predicates that have
1912 /// to do with "all compatible universes" should depend on this clause so that they only apply
1913 /// if this is present.
1914 Compatible,
1915
1916 /// Used to indicate that a given type is in a downstream crate. Downstream crates contain the
1917 /// current crate at some level of their dependencies.
1918 ///
1919 /// Since chalk does not actually see downstream types, this is usually introduced with
1920 /// implication on a fresh, universally quantified type.
1921 ///
1922 /// forall<T> { if (DownstreamType(T)) { /* ... */ } }
1923 ///
1924 /// This makes a new type `T` available and makes `DownstreamType(T)` provable for that type.
1925 DownstreamType(Ty<I>),
1926
1927 /// Used to activate the "reveal mode", in which opaque (`impl Trait`) types can be equated
1928 /// to their actual type.
1929 Reveal,
1930
1931 /// Used to indicate that a trait is object safe.
1932 ObjectSafe(TraitId<I>),
1933 }
1934
1935 impl<I: Interner> Copy for DomainGoal<I>
1936 where
1937 I::InternedSubstitution: Copy,
1938 I::InternedLifetime: Copy,
1939 I::InternedType: Copy,
1940 {
1941 }
1942
1943 /// A where clause that can contain `forall<>` or `exists<>` quantifiers.
1944 pub type QuantifiedWhereClause<I> = Binders<WhereClause<I>>;
1945
1946 impl<I: Interner> WhereClause<I> {
1947 /// Turn a where clause into the WF version of it i.e.:
1948 /// * `Implemented(T: Trait)` maps to `WellFormed(T: Trait)`
1949 /// * `ProjectionEq(<T as Trait>::Item = Foo)` maps to `WellFormed(<T as Trait>::Item = Foo)`
1950 /// * any other clause maps to itself
into_well_formed_goal(self, interner: &I) -> DomainGoal<I>1951 pub fn into_well_formed_goal(self, interner: &I) -> DomainGoal<I> {
1952 match self {
1953 WhereClause::Implemented(trait_ref) => WellFormed::Trait(trait_ref).cast(interner),
1954 wc => wc.cast(interner),
1955 }
1956 }
1957
1958 /// Same as `into_well_formed_goal` but with the `FromEnv` predicate instead of `WellFormed`.
into_from_env_goal(self, interner: &I) -> DomainGoal<I>1959 pub fn into_from_env_goal(self, interner: &I) -> DomainGoal<I> {
1960 match self {
1961 WhereClause::Implemented(trait_ref) => FromEnv::Trait(trait_ref).cast(interner),
1962 wc => wc.cast(interner),
1963 }
1964 }
1965
1966 /// If where clause is a `TraitRef`, returns its trait id.
trait_id(&self) -> Option<TraitId<I>>1967 pub fn trait_id(&self) -> Option<TraitId<I>> {
1968 match self {
1969 WhereClause::Implemented(trait_ref) => Some(trait_ref.trait_id),
1970 WhereClause::AliasEq(_) => None,
1971 WhereClause::LifetimeOutlives(_) => None,
1972 WhereClause::TypeOutlives(_) => None,
1973 }
1974 }
1975 }
1976
1977 impl<I: Interner> QuantifiedWhereClause<I> {
1978 /// As with `WhereClause::into_well_formed_goal`, but for a
1979 /// quantified where clause. For example, `forall<T> {
1980 /// Implemented(T: Trait)}` would map to `forall<T> {
1981 /// WellFormed(T: Trait) }`.
into_well_formed_goal(self, interner: &I) -> Binders<DomainGoal<I>>1982 pub fn into_well_formed_goal(self, interner: &I) -> Binders<DomainGoal<I>> {
1983 self.map(|wc| wc.into_well_formed_goal(interner))
1984 }
1985
1986 /// As with `WhereClause::into_from_env_goal`, but mapped over any
1987 /// binders. For example, `forall<T> {
1988 /// Implemented(T: Trait)}` would map to `forall<T> {
1989 /// FromEnv(T: Trait) }`.
into_from_env_goal(self, interner: &I) -> Binders<DomainGoal<I>>1990 pub fn into_from_env_goal(self, interner: &I) -> Binders<DomainGoal<I>> {
1991 self.map(|wc| wc.into_from_env_goal(interner))
1992 }
1993
1994 /// If the underlying where clause is a `TraitRef`, returns its trait id.
trait_id(&self) -> Option<TraitId<I>>1995 pub fn trait_id(&self) -> Option<TraitId<I>> {
1996 self.skip_binders().trait_id()
1997 }
1998 }
1999
2000 impl<I: Interner> DomainGoal<I> {
2001 /// Convert `Implemented(...)` into `FromEnv(...)`, but leave other
2002 /// goals unchanged.
into_from_env_goal(self, interner: &I) -> DomainGoal<I>2003 pub fn into_from_env_goal(self, interner: &I) -> DomainGoal<I> {
2004 match self {
2005 DomainGoal::Holds(wc) => wc.into_from_env_goal(interner),
2006 goal => goal,
2007 }
2008 }
2009
2010 /// Lists generic arguments that are inputs to this domain goal.
inputs(&self, interner: &I) -> Vec<GenericArg<I>>2011 pub fn inputs(&self, interner: &I) -> Vec<GenericArg<I>> {
2012 match self {
2013 DomainGoal::Holds(WhereClause::AliasEq(alias_eq)) => {
2014 vec![GenericArgData::Ty(alias_eq.alias.clone().intern(interner)).intern(interner)]
2015 }
2016 _ => Vec::new(),
2017 }
2018 }
2019 }
2020
2021 /// Equality goal: tries to prove that two values are equal.
2022 #[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, Zip)]
2023 #[allow(missing_docs)]
2024 pub struct EqGoal<I: Interner> {
2025 pub a: GenericArg<I>,
2026 pub b: GenericArg<I>,
2027 }
2028
2029 impl<I: Interner> Copy for EqGoal<I> where I::InternedGenericArg: Copy {}
2030
2031 /// Subtype goal: tries to prove that `a` is a subtype of `b`
2032 #[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, Zip)]
2033 #[allow(missing_docs)]
2034 pub struct SubtypeGoal<I: Interner> {
2035 pub a: Ty<I>,
2036 pub b: Ty<I>,
2037 }
2038
2039 impl<I: Interner> Copy for SubtypeGoal<I> where I::InternedType: Copy {}
2040
2041 /// Proves that the given type alias **normalizes** to the given
2042 /// type. A projection `T::Foo` normalizes to the type `U` if we can
2043 /// **match it to an impl** and that impl has a `type Foo = V` where
2044 /// `U = V`.
2045 #[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, Zip)]
2046 #[allow(missing_docs)]
2047 pub struct Normalize<I: Interner> {
2048 pub alias: AliasTy<I>,
2049 pub ty: Ty<I>,
2050 }
2051
2052 impl<I: Interner> Copy for Normalize<I>
2053 where
2054 I::InternedSubstitution: Copy,
2055 I::InternedType: Copy,
2056 {
2057 }
2058
2059 /// Proves **equality** between an alias and a type.
2060 #[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, Zip)]
2061 #[allow(missing_docs)]
2062 pub struct AliasEq<I: Interner> {
2063 pub alias: AliasTy<I>,
2064 pub ty: Ty<I>,
2065 }
2066
2067 impl<I: Interner> Copy for AliasEq<I>
2068 where
2069 I::InternedSubstitution: Copy,
2070 I::InternedType: Copy,
2071 {
2072 }
2073
2074 impl<I: Interner> HasInterner for AliasEq<I> {
2075 type Interner = I;
2076 }
2077
2078 /// Indicates that the `value` is universally quantified over `N`
2079 /// parameters of the given kinds, where `N == self.binders.len()`. A
2080 /// variable with depth `i < N` refers to the value at
2081 /// `self.binders[i]`. Variables with depth `>= N` are free.
2082 ///
2083 /// (IOW, we use deBruijn indices, where binders are introduced in reverse order
2084 /// of `self.binders`.)
2085 #[derive(Clone, PartialEq, Eq, Hash)]
2086 pub struct Binders<T: HasInterner> {
2087 /// The binders that quantify over the value.
2088 pub binders: VariableKinds<T::Interner>,
2089
2090 /// The value being quantified over.
2091 value: T,
2092 }
2093
2094 impl<T: HasInterner + Copy> Copy for Binders<T> where
2095 <T::Interner as Interner>::InternedVariableKinds: Copy
2096 {
2097 }
2098
2099 impl<T: HasInterner> HasInterner for Binders<T> {
2100 type Interner = T::Interner;
2101 }
2102
2103 impl<T: Clone + HasInterner> Binders<&T> {
2104 /// Converts a `Binders<&T>` to a `Binders<T>` by cloning `T`.
cloned(self) -> Binders<T>2105 pub fn cloned(self) -> Binders<T> {
2106 self.map(Clone::clone)
2107 }
2108 }
2109
2110 impl<T: HasInterner> Binders<T> {
2111 /// Create new binders.
new(binders: VariableKinds<T::Interner>, value: T) -> Self2112 pub fn new(binders: VariableKinds<T::Interner>, value: T) -> Self {
2113 Self { binders, value }
2114 }
2115
2116 /// Wraps the given value in a binder without variables, i.e. `for<>
2117 /// (value)`. Since our deBruijn indices count binders, not variables, this
2118 /// is sometimes useful.
empty(interner: &T::Interner, value: T) -> Self2119 pub fn empty(interner: &T::Interner, value: T) -> Self {
2120 let binders = VariableKinds::empty(interner);
2121 Self { binders, value }
2122 }
2123
2124 /// Skips the binder and returns the "bound" value. This is a
2125 /// risky thing to do because it's easy to get confused about
2126 /// De Bruijn indices and the like. `skip_binder` is only valid
2127 /// when you are either extracting data that has nothing to
2128 /// do with bound vars, or you are being very careful about
2129 /// your depth accounting.
2130 ///
2131 /// Some examples where `skip_binder` is reasonable:
2132 ///
2133 /// - extracting the `TraitId` from a TraitRef;
2134 /// - checking if there are any fields in a StructDatum
skip_binders(&self) -> &T2135 pub fn skip_binders(&self) -> &T {
2136 &self.value
2137 }
2138
2139 /// Skips the binder and returns the "bound" value as well as the skipped free variables. This
2140 /// is just as risky as [`skip_binders`].
into_value_and_skipped_binders(self) -> (T, VariableKinds<T::Interner>)2141 pub fn into_value_and_skipped_binders(self) -> (T, VariableKinds<T::Interner>) {
2142 (self.value, self.binders)
2143 }
2144
2145 /// Converts `&Binders<T>` to `Binders<&T>`. Produces new `Binders`
2146 /// with cloned quantifiers containing a reference to the original
2147 /// value, leaving the original in place.
as_ref(&self) -> Binders<&T>2148 pub fn as_ref(&self) -> Binders<&T> {
2149 Binders {
2150 binders: self.binders.clone(),
2151 value: &self.value,
2152 }
2153 }
2154
2155 /// Maps the binders by applying a function.
map<U, OP>(self, op: OP) -> Binders<U> where OP: FnOnce(T) -> U, U: HasInterner<Interner = T::Interner>,2156 pub fn map<U, OP>(self, op: OP) -> Binders<U>
2157 where
2158 OP: FnOnce(T) -> U,
2159 U: HasInterner<Interner = T::Interner>,
2160 {
2161 let value = op(self.value);
2162 Binders {
2163 binders: self.binders,
2164 value,
2165 }
2166 }
2167
2168 /// Transforms the inner value according to the given function; returns
2169 /// `None` if the function returns `None`.
filter_map<U, OP>(self, op: OP) -> Option<Binders<U>> where OP: FnOnce(T) -> Option<U>, U: HasInterner<Interner = T::Interner>,2170 pub fn filter_map<U, OP>(self, op: OP) -> Option<Binders<U>>
2171 where
2172 OP: FnOnce(T) -> Option<U>,
2173 U: HasInterner<Interner = T::Interner>,
2174 {
2175 let value = op(self.value)?;
2176 Some(Binders {
2177 binders: self.binders,
2178 value,
2179 })
2180 }
2181
2182 /// Maps a function taking `Binders<&T>` over `&Binders<T>`.
map_ref<'a, U, OP>(&'a self, op: OP) -> Binders<U> where OP: FnOnce(&'a T) -> U, U: HasInterner<Interner = T::Interner>,2183 pub fn map_ref<'a, U, OP>(&'a self, op: OP) -> Binders<U>
2184 where
2185 OP: FnOnce(&'a T) -> U,
2186 U: HasInterner<Interner = T::Interner>,
2187 {
2188 self.as_ref().map(op)
2189 }
2190
2191 /// Creates a `Substitution` containing bound vars such that applying this
2192 /// substitution will not change the value, i.e. `^0.0, ^0.1, ^0.2` and so
2193 /// on.
identity_substitution(&self, interner: &T::Interner) -> Substitution<T::Interner>2194 pub fn identity_substitution(&self, interner: &T::Interner) -> Substitution<T::Interner> {
2195 Substitution::from_iter(
2196 interner,
2197 self.binders
2198 .iter(interner)
2199 .enumerate()
2200 .map(|p| p.to_generic_arg(interner)),
2201 )
2202 }
2203
2204 /// Creates a fresh binders that contains a single type
2205 /// variable. The result of the closure will be embedded in this
2206 /// binder. Note that you should be careful with what you return
2207 /// from the closure to account for the binder that will be added.
2208 ///
2209 /// XXX FIXME -- this is potentially a pretty footgun-y function.
with_fresh_type_var( interner: &T::Interner, op: impl FnOnce(Ty<T::Interner>) -> T, ) -> Binders<T>2210 pub fn with_fresh_type_var(
2211 interner: &T::Interner,
2212 op: impl FnOnce(Ty<T::Interner>) -> T,
2213 ) -> Binders<T> {
2214 // The new variable is at the front and everything afterwards is shifted up by 1
2215 let new_var = TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, 0)).intern(interner);
2216 let value = op(new_var);
2217 let binders = VariableKinds::from1(interner, VariableKind::Ty(TyVariableKind::General));
2218 Binders { binders, value }
2219 }
2220
2221 /// Returns the number of binders.
len(&self, interner: &T::Interner) -> usize2222 pub fn len(&self, interner: &T::Interner) -> usize {
2223 self.binders.len(interner)
2224 }
2225 }
2226
2227 impl<T, I> Binders<Binders<T>>
2228 where
2229 T: Fold<I> + HasInterner<Interner = I>,
2230 T::Result: HasInterner<Interner = I>,
2231 I: Interner,
2232 {
2233 /// This turns two levels of binders (`for<A> for<B>`) into one level (`for<A, B>`).
fuse_binders(self, interner: &T::Interner) -> Binders<T::Result>2234 pub fn fuse_binders(self, interner: &T::Interner) -> Binders<T::Result> {
2235 let num_binders = self.len(interner);
2236 // generate a substitution to shift the indexes of the inner binder:
2237 let subst = Substitution::from_iter(
2238 interner,
2239 self.value
2240 .binders
2241 .iter(interner)
2242 .enumerate()
2243 .map(|(i, pk)| (i + num_binders, pk).to_generic_arg(interner)),
2244 );
2245 let binders = VariableKinds::from_iter(
2246 interner,
2247 self.binders
2248 .iter(interner)
2249 .chain(self.value.binders.iter(interner))
2250 .cloned(),
2251 );
2252 let value = self.value.substitute(interner, &subst);
2253 Binders { binders, value }
2254 }
2255 }
2256
2257 impl<T: HasInterner> From<Binders<T>> for (VariableKinds<T::Interner>, T) {
from(binders: Binders<T>) -> Self2258 fn from(binders: Binders<T>) -> Self {
2259 (binders.binders, binders.value)
2260 }
2261 }
2262
2263 impl<T, I> Binders<T>
2264 where
2265 T: Fold<I> + HasInterner<Interner = I>,
2266 I: Interner,
2267 {
2268 /// Substitute `parameters` for the variables introduced by these
2269 /// binders. So if the binders represent (e.g.) `<X, Y> { T }` and
2270 /// parameters is the slice `[A, B]`, then returns `[X => A, Y =>
2271 /// B] T`.
substitute( self, interner: &I, parameters: &(impl AsParameters<I> + ?Sized), ) -> T::Result2272 pub fn substitute(
2273 self,
2274 interner: &I,
2275 parameters: &(impl AsParameters<I> + ?Sized),
2276 ) -> T::Result {
2277 let parameters = parameters.as_parameters(interner);
2278 assert_eq!(self.binders.len(interner), parameters.len());
2279 Subst::apply(interner, parameters, self.value)
2280 }
2281 }
2282
2283 /// Allows iterating over a Binders<Vec<T>>, for instance.
2284 /// Each element will include the same set of parameter bounds.
2285 impl<V, U> IntoIterator for Binders<V>
2286 where
2287 V: HasInterner + IntoIterator<Item = U>,
2288 U: HasInterner<Interner = V::Interner>,
2289 {
2290 type Item = Binders<U>;
2291 type IntoIter = BindersIntoIterator<V>;
2292
into_iter(self) -> Self::IntoIter2293 fn into_iter(self) -> Self::IntoIter {
2294 BindersIntoIterator {
2295 iter: self.value.into_iter(),
2296 binders: self.binders,
2297 }
2298 }
2299 }
2300
2301 /// `IntoIterator` for binders.
2302 pub struct BindersIntoIterator<V: HasInterner + IntoIterator> {
2303 iter: <V as IntoIterator>::IntoIter,
2304 binders: VariableKinds<V::Interner>,
2305 }
2306
2307 impl<V> Iterator for BindersIntoIterator<V>
2308 where
2309 V: HasInterner + IntoIterator,
2310 <V as IntoIterator>::Item: HasInterner<Interner = V::Interner>,
2311 {
2312 type Item = Binders<<V as IntoIterator>::Item>;
next(&mut self) -> Option<Self::Item>2313 fn next(&mut self) -> Option<Self::Item> {
2314 self.iter
2315 .next()
2316 .map(|v| Binders::new(self.binders.clone(), v))
2317 }
2318 }
2319
2320 /// Represents one clause of the form `consequence :- conditions` where
2321 /// `conditions = cond_1 && cond_2 && ...` is the conjunction of the individual
2322 /// conditions.
2323 #[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, HasInterner, Zip)]
2324 pub struct ProgramClauseImplication<I: Interner> {
2325 /// The consequence of the clause, which holds if the conditions holds.
2326 pub consequence: DomainGoal<I>,
2327
2328 /// The condition goals that should hold.
2329 pub conditions: Goals<I>,
2330
2331 /// The lifetime constraints that should be proven.
2332 pub constraints: Constraints<I>,
2333
2334 /// The relative priority of the implication.
2335 pub priority: ClausePriority,
2336 }
2337
2338 /// Specifies how important an implication is.
2339 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
2340 pub enum ClausePriority {
2341 /// High priority, the solver should prioritize this.
2342 High,
2343
2344 /// Low priority, this implication has lower chance to be relevant to the goal.
2345 Low,
2346 }
2347
2348 impl std::ops::BitAnd for ClausePriority {
2349 type Output = ClausePriority;
bitand(self, rhs: ClausePriority) -> Self::Output2350 fn bitand(self, rhs: ClausePriority) -> Self::Output {
2351 match (self, rhs) {
2352 (ClausePriority::High, ClausePriority::High) => ClausePriority::High,
2353 _ => ClausePriority::Low,
2354 }
2355 }
2356 }
2357
2358 /// Contains the data for a program clause.
2359 #[derive(Clone, PartialEq, Eq, Hash, Fold, HasInterner, Zip)]
2360 pub struct ProgramClauseData<I: Interner>(pub Binders<ProgramClauseImplication<I>>);
2361
2362 impl<I: Interner> ProgramClauseImplication<I> {
2363 /// Change the implication into an application holding a `FromEnv` goal.
into_from_env_clause(self, interner: &I) -> ProgramClauseImplication<I>2364 pub fn into_from_env_clause(self, interner: &I) -> ProgramClauseImplication<I> {
2365 if self.conditions.is_empty(interner) {
2366 ProgramClauseImplication {
2367 consequence: self.consequence.into_from_env_goal(interner),
2368 conditions: self.conditions.clone(),
2369 constraints: self.constraints.clone(),
2370 priority: self.priority,
2371 }
2372 } else {
2373 self
2374 }
2375 }
2376 }
2377
2378 impl<I: Interner> ProgramClauseData<I> {
2379 /// Change the program clause data into a `FromEnv` program clause.
into_from_env_clause(self, interner: &I) -> ProgramClauseData<I>2380 pub fn into_from_env_clause(self, interner: &I) -> ProgramClauseData<I> {
2381 ProgramClauseData(self.0.map(|i| i.into_from_env_clause(interner)))
2382 }
2383
2384 /// Intern the program clause data.
intern(self, interner: &I) -> ProgramClause<I>2385 pub fn intern(self, interner: &I) -> ProgramClause<I> {
2386 ProgramClause {
2387 interned: interner.intern_program_clause(self),
2388 }
2389 }
2390 }
2391
2392 /// A program clause is a logic expression used to describe a part of the program.
2393 #[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, HasInterner)]
2394 pub struct ProgramClause<I: Interner> {
2395 interned: I::InternedProgramClause,
2396 }
2397
2398 impl<I: Interner> ProgramClause<I> {
2399 /// Create a new program clause using `ProgramClauseData`.
new(interner: &I, clause: ProgramClauseData<I>) -> Self2400 pub fn new(interner: &I, clause: ProgramClauseData<I>) -> Self {
2401 let interned = interner.intern_program_clause(clause);
2402 Self { interned }
2403 }
2404
2405 /// Change the clause into a `FromEnv` clause.
into_from_env_clause(self, interner: &I) -> ProgramClause<I>2406 pub fn into_from_env_clause(self, interner: &I) -> ProgramClause<I> {
2407 let program_clause_data = self.data(interner);
2408 let new_clause = program_clause_data.clone().into_from_env_clause(interner);
2409 Self::new(interner, new_clause)
2410 }
2411
2412 /// Get the interned program clause.
interned(&self) -> &I::InternedProgramClause2413 pub fn interned(&self) -> &I::InternedProgramClause {
2414 &self.interned
2415 }
2416
2417 /// Get the program clause data.
data(&self, interner: &I) -> &ProgramClauseData<I>2418 pub fn data(&self, interner: &I) -> &ProgramClauseData<I> {
2419 interner.program_clause_data(&self.interned)
2420 }
2421 }
2422
2423 /// Wraps a "canonicalized item". Items are canonicalized as follows:
2424 ///
2425 /// All unresolved existential variables are "renumbered" according to their
2426 /// first appearance; the kind/universe of the variable is recorded in the
2427 /// `binders` field.
2428 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
2429 pub struct Canonical<T: HasInterner> {
2430 /// The item that is canonicalized.
2431 pub value: T,
2432
2433 /// The kind/universe of the variable.
2434 pub binders: CanonicalVarKinds<T::Interner>,
2435 }
2436
2437 impl<T: HasInterner> HasInterner for Canonical<T> {
2438 type Interner = T::Interner;
2439 }
2440
2441 /// A "universe canonical" value. This is a wrapper around a
2442 /// `Canonical`, indicating that the universes within have been
2443 /// "renumbered" to start from 0 and collapse unimportant
2444 /// distinctions.
2445 ///
2446 /// To produce one of these values, use the `u_canonicalize` method.
2447 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
2448 pub struct UCanonical<T: HasInterner> {
2449 /// The wrapped `Canonical`.
2450 pub canonical: Canonical<T>,
2451
2452 /// The number of universes that have been collapsed.
2453 pub universes: usize,
2454 }
2455
2456 impl<T: HasInterner> UCanonical<T> {
2457 /// Checks whether the universe canonical value is a trivial
2458 /// substitution (e.g. an identity substitution).
is_trivial_substitution( &self, interner: &T::Interner, canonical_subst: &Canonical<AnswerSubst<T::Interner>>, ) -> bool2459 pub fn is_trivial_substitution(
2460 &self,
2461 interner: &T::Interner,
2462 canonical_subst: &Canonical<AnswerSubst<T::Interner>>,
2463 ) -> bool {
2464 let subst = &canonical_subst.value.subst;
2465 assert_eq!(
2466 self.canonical.binders.len(interner),
2467 subst.as_slice(interner).len()
2468 );
2469 subst.is_identity_subst(interner)
2470 }
2471
2472 /// Creates an identity substitution.
trivial_substitution(&self, interner: &T::Interner) -> Substitution<T::Interner>2473 pub fn trivial_substitution(&self, interner: &T::Interner) -> Substitution<T::Interner> {
2474 let binders = &self.canonical.binders;
2475 Substitution::from_iter(
2476 interner,
2477 binders
2478 .iter(interner)
2479 .enumerate()
2480 .map(|(index, pk)| {
2481 let bound_var = BoundVar::new(DebruijnIndex::INNERMOST, index);
2482 match &pk.kind {
2483 VariableKind::Ty(_) => {
2484 GenericArgData::Ty(TyKind::BoundVar(bound_var).intern(interner))
2485 .intern(interner)
2486 }
2487 VariableKind::Lifetime => GenericArgData::Lifetime(
2488 LifetimeData::BoundVar(bound_var).intern(interner),
2489 )
2490 .intern(interner),
2491 VariableKind::Const(ty) => GenericArgData::Const(
2492 ConstData {
2493 ty: ty.clone(),
2494 value: ConstValue::BoundVar(bound_var),
2495 }
2496 .intern(interner),
2497 )
2498 .intern(interner),
2499 }
2500 })
2501 .collect::<Vec<_>>(),
2502 )
2503 }
2504 }
2505
2506 #[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, HasInterner)]
2507 /// A general goal; this is the full range of questions you can pose to Chalk.
2508 pub struct Goal<I: Interner> {
2509 interned: I::InternedGoal,
2510 }
2511
2512 impl<I: Interner> Goal<I> {
2513 /// Create a new goal using `GoalData`.
new(interner: &I, interned: GoalData<I>) -> Self2514 pub fn new(interner: &I, interned: GoalData<I>) -> Self {
2515 let interned = I::intern_goal(interner, interned);
2516 Self { interned }
2517 }
2518
2519 /// Gets the interned goal.
interned(&self) -> &I::InternedGoal2520 pub fn interned(&self) -> &I::InternedGoal {
2521 &self.interned
2522 }
2523
2524 /// Gets the interned goal data.
data(&self, interner: &I) -> &GoalData<I>2525 pub fn data(&self, interner: &I) -> &GoalData<I> {
2526 interner.goal_data(&self.interned)
2527 }
2528
2529 /// Create a goal using a `forall` or `exists` quantifier.
quantify( self, interner: &I, kind: QuantifierKind, binders: VariableKinds<I>, ) -> Goal<I>2530 pub fn quantify(
2531 self,
2532 interner: &I,
2533 kind: QuantifierKind,
2534 binders: VariableKinds<I>,
2535 ) -> Goal<I> {
2536 GoalData::Quantified(kind, Binders::new(binders, self)).intern(interner)
2537 }
2538
2539 /// Takes a goal `G` and turns it into `not { G }`.
negate(self, interner: &I) -> Self2540 pub fn negate(self, interner: &I) -> Self {
2541 GoalData::Not(self).intern(interner)
2542 }
2543
2544 /// Takes a goal `G` and turns it into `compatible { G }`.
compatible(self, interner: &I) -> Self2545 pub fn compatible(self, interner: &I) -> Self {
2546 // compatible { G } desugars into: forall<T> { if (Compatible, DownstreamType(T)) { G } }
2547 // This activates the compatible modality rules and introduces an anonymous downstream type
2548 GoalData::Quantified(
2549 QuantifierKind::ForAll,
2550 Binders::with_fresh_type_var(interner, |ty| {
2551 GoalData::Implies(
2552 ProgramClauses::from_iter(
2553 interner,
2554 vec![DomainGoal::Compatible, DomainGoal::DownstreamType(ty)],
2555 ),
2556 self.shifted_in(interner),
2557 )
2558 .intern(interner)
2559 }),
2560 )
2561 .intern(interner)
2562 }
2563
2564 /// Create an implication goal that holds if the predicates are true.
implied_by(self, interner: &I, predicates: ProgramClauses<I>) -> Goal<I>2565 pub fn implied_by(self, interner: &I, predicates: ProgramClauses<I>) -> Goal<I> {
2566 GoalData::Implies(predicates, self).intern(interner)
2567 }
2568
2569 /// True if this goal is "trivially true" -- i.e., no work is
2570 /// required to prove it.
is_trivially_true(&self, interner: &I) -> bool2571 pub fn is_trivially_true(&self, interner: &I) -> bool {
2572 match self.data(interner) {
2573 GoalData::All(goals) => goals.is_empty(interner),
2574 _ => false,
2575 }
2576 }
2577 }
2578
2579 impl<I> Goal<I>
2580 where
2581 I: Interner,
2582 {
2583 /// Creates a single goal that only holds if a list of goals holds.
all<II>(interner: &I, iter: II) -> Self where II: IntoIterator<Item = Goal<I>>,2584 pub fn all<II>(interner: &I, iter: II) -> Self
2585 where
2586 II: IntoIterator<Item = Goal<I>>,
2587 {
2588 let mut iter = iter.into_iter();
2589 if let Some(goal0) = iter.next() {
2590 if let Some(goal1) = iter.next() {
2591 // More than one goal to prove
2592 let goals = Goals::from_iter(
2593 interner,
2594 Some(goal0).into_iter().chain(Some(goal1)).chain(iter),
2595 );
2596 GoalData::All(goals).intern(interner)
2597 } else {
2598 // One goal to prove
2599 goal0
2600 }
2601 } else {
2602 // No goals to prove, always true
2603 GoalData::All(Goals::empty(interner)).intern(interner)
2604 }
2605 }
2606 }
2607
2608 #[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, HasInterner, Zip)]
2609 /// A general goal; this is the full range of questions you can pose to Chalk.
2610 pub enum GoalData<I: Interner> {
2611 /// Introduces a binding at depth 0, shifting other bindings up
2612 /// (deBruijn index).
2613 Quantified(QuantifierKind, Binders<Goal<I>>),
2614
2615 /// A goal that holds given some clauses (like an if-statement).
2616 Implies(ProgramClauses<I>, Goal<I>),
2617
2618 /// List of goals that all should hold.
2619 All(Goals<I>),
2620
2621 /// Negation: the inner goal should not hold.
2622 Not(Goal<I>),
2623
2624 /// Make two things equal; the rules for doing so are well known to the logic
2625 EqGoal(EqGoal<I>),
2626
2627 /// Make one thing a subtype of another; the rules for doing so are well known to the logic
2628 SubtypeGoal(SubtypeGoal<I>),
2629
2630 /// A "domain goal" indicates some base sort of goal that can be
2631 /// proven via program clauses
2632 DomainGoal(DomainGoal<I>),
2633
2634 /// Indicates something that cannot be proven to be true or false
2635 /// definitively. This can occur with overflow but also with
2636 /// unifications of skolemized variables like `forall<X,Y> { X = Y
2637 /// }`. Of course, that statement is false, as there exist types
2638 /// X, Y where `X = Y` is not true. But we treat it as "cannot
2639 /// prove" so that `forall<X,Y> { not { X = Y } }` also winds up
2640 /// as cannot prove.
2641 CannotProve,
2642 }
2643
2644 impl<I: Interner> Copy for GoalData<I>
2645 where
2646 I::InternedType: Copy,
2647 I::InternedLifetime: Copy,
2648 I::InternedGenericArg: Copy,
2649 I::InternedSubstitution: Copy,
2650 I::InternedGoal: Copy,
2651 I::InternedGoals: Copy,
2652 I::InternedProgramClauses: Copy,
2653 I::InternedVariableKinds: Copy,
2654 {
2655 }
2656
2657 impl<I: Interner> GoalData<I> {
2658 /// Create an interned goal.
intern(self, interner: &I) -> Goal<I>2659 pub fn intern(self, interner: &I) -> Goal<I> {
2660 Goal::new(interner, self)
2661 }
2662 }
2663
2664 /// Kinds of quantifiers in the logic, such as `forall` and `exists`.
2665 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
2666 pub enum QuantifierKind {
2667 /// Universal quantifier `ForAll`.
2668 ///
2669 /// A formula with the universal quantifier `forall(x). P(x)` is satisfiable
2670 /// if and only if the subformula `P(x)` is true for all possible values for x.
2671 ForAll,
2672
2673 /// Existential quantifier `Exists`.
2674 ///
2675 /// A formula with the existential quantifier `exists(x). P(x)` is satisfiable
2676 /// if and only if there exists at least one value for all possible values of x
2677 /// which satisfies the subformula `P(x)`.
2678
2679 /// In the context of chalk, the existential quantifier usually demands the
2680 /// existence of exactly one instance (i.e. type) that satisfies the formula
2681 /// (i.e. type constraints). More than one instance means that the result is ambiguous.
2682 Exists,
2683 }
2684
2685 /// A constraint on lifetimes.
2686 ///
2687 /// When we search for solutions within the trait system, we essentially ignore
2688 /// lifetime constraints, instead gathering them up to return with our solution
2689 /// for later checking. This allows for decoupling between type and region
2690 /// checking in the compiler.
2691 #[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, HasInterner, Zip)]
2692 pub enum Constraint<I: Interner> {
2693 /// Outlives constraint `'a: 'b`, indicating that the value of `'a` must be
2694 /// a superset of the value of `'b`.
2695 LifetimeOutlives(Lifetime<I>, Lifetime<I>),
2696
2697 /// Type outlives constraint `T: 'a`, indicating that the type `T` must live
2698 /// at least as long as the value of `'a`.
2699 TypeOutlives(Ty<I>, Lifetime<I>),
2700 }
2701
2702 impl<I: Interner> Copy for Constraint<I>
2703 where
2704 I::InternedLifetime: Copy,
2705 I::InternedType: Copy,
2706 {
2707 }
2708
2709 impl<I: Interner> Substitution<I> {
2710 /// A substitution is an **identity substitution** if it looks
2711 /// like this
2712 ///
2713 /// ```text
2714 /// ?0 := ?0
2715 /// ?1 := ?1
2716 /// ?2 := ?2
2717 /// ...
2718 /// ```
2719 ///
2720 /// Basically, each value is mapped to a type or lifetime with its
2721 /// same index.
is_identity_subst(&self, interner: &I) -> bool2722 pub fn is_identity_subst(&self, interner: &I) -> bool {
2723 self.iter(interner).zip(0..).all(|(generic_arg, index)| {
2724 let index_db = BoundVar::new(DebruijnIndex::INNERMOST, index);
2725 match generic_arg.data(interner) {
2726 GenericArgData::Ty(ty) => match ty.kind(interner) {
2727 TyKind::BoundVar(depth) => index_db == *depth,
2728 _ => false,
2729 },
2730 GenericArgData::Lifetime(lifetime) => match lifetime.data(interner) {
2731 LifetimeData::BoundVar(depth) => index_db == *depth,
2732 _ => false,
2733 },
2734 GenericArgData::Const(constant) => match &constant.data(interner).value {
2735 ConstValue::BoundVar(depth) => index_db == *depth,
2736 _ => false,
2737 },
2738 }
2739 })
2740 }
2741
2742 /// Apply the substitution to a value.
apply<T>(&self, value: T, interner: &I) -> T::Result where T: Fold<I>,2743 pub fn apply<T>(&self, value: T, interner: &I) -> T::Result
2744 where
2745 T: Fold<I>,
2746 {
2747 Substitute::apply(self, value, interner)
2748 }
2749
2750 /// Gets an iterator of all type parameters.
type_parameters<'a>(&'a self, interner: &'a I) -> impl Iterator<Item = Ty<I>> + 'a2751 pub fn type_parameters<'a>(&'a self, interner: &'a I) -> impl Iterator<Item = Ty<I>> + 'a {
2752 self.iter(interner)
2753 .filter_map(move |p| p.ty(interner))
2754 .cloned()
2755 }
2756 }
2757
2758 struct SubstFolder<'i, I: Interner, A: AsParameters<I>> {
2759 interner: &'i I,
2760 subst: &'i A,
2761 }
2762
2763 impl<I: Interner, A: AsParameters<I>> SubstFolder<'_, I, A> {
2764 /// Index into the list of parameters.
at(&self, index: usize) -> &GenericArg<I>2765 pub fn at(&self, index: usize) -> &GenericArg<I> {
2766 let interner = self.interner;
2767 &self.subst.as_parameters(interner)[index]
2768 }
2769 }
2770
2771 /// Convert a value to a list of parameters.
2772 pub trait AsParameters<I: Interner> {
2773 /// Convert the current value to parameters.
as_parameters(&self, interner: &I) -> &[GenericArg<I>]2774 fn as_parameters(&self, interner: &I) -> &[GenericArg<I>];
2775 }
2776
2777 impl<I: Interner> AsParameters<I> for Substitution<I> {
2778 #[allow(unreachable_code, unused_variables)]
as_parameters(&self, interner: &I) -> &[GenericArg<I>]2779 fn as_parameters(&self, interner: &I) -> &[GenericArg<I>] {
2780 self.as_slice(interner)
2781 }
2782 }
2783
2784 impl<I: Interner> AsParameters<I> for [GenericArg<I>] {
as_parameters(&self, _interner: &I) -> &[GenericArg<I>]2785 fn as_parameters(&self, _interner: &I) -> &[GenericArg<I>] {
2786 self
2787 }
2788 }
2789
2790 impl<I: Interner> AsParameters<I> for [GenericArg<I>; 1] {
as_parameters(&self, _interner: &I) -> &[GenericArg<I>]2791 fn as_parameters(&self, _interner: &I) -> &[GenericArg<I>] {
2792 self
2793 }
2794 }
2795
2796 impl<I: Interner> AsParameters<I> for Vec<GenericArg<I>> {
as_parameters(&self, _interner: &I) -> &[GenericArg<I>]2797 fn as_parameters(&self, _interner: &I) -> &[GenericArg<I>] {
2798 self
2799 }
2800 }
2801
2802 impl<T, I: Interner> AsParameters<I> for &T
2803 where
2804 T: ?Sized + AsParameters<I>,
2805 {
as_parameters(&self, interner: &I) -> &[GenericArg<I>]2806 fn as_parameters(&self, interner: &I) -> &[GenericArg<I>] {
2807 T::as_parameters(self, interner)
2808 }
2809 }
2810
2811 /// An extension trait to anything that can be represented as list of `GenericArg`s that signifies
2812 /// that it can applied as a substituion to a value
2813 pub trait Substitute<I: Interner>: AsParameters<I> {
2814 /// Apply the substitution to a value.
apply<T: Fold<I>>(&self, value: T, interner: &I) -> T::Result2815 fn apply<T: Fold<I>>(&self, value: T, interner: &I) -> T::Result;
2816 }
2817
2818 impl<I: Interner, A: AsParameters<I>> Substitute<I> for A {
apply<T>(&self, value: T, interner: &I) -> T::Result where T: Fold<I>,2819 fn apply<T>(&self, value: T, interner: &I) -> T::Result
2820 where
2821 T: Fold<I>,
2822 {
2823 value
2824 .fold_with(
2825 &mut &SubstFolder {
2826 interner,
2827 subst: self,
2828 },
2829 DebruijnIndex::INNERMOST,
2830 )
2831 .unwrap()
2832 }
2833 }
2834
2835 /// Utility for converting a list of all the binders into scope
2836 /// into references to those binders. Simply pair the binders with
2837 /// the indices, and invoke `to_generic_arg()` on the `(binder,
2838 /// index)` pair. The result will be a reference to a bound
2839 /// variable of appropriate kind at the corresponding index.
2840 pub trait ToGenericArg<I: Interner> {
2841 /// Converts the binders in scope to references to those binders.
to_generic_arg(&self, interner: &I) -> GenericArg<I>2842 fn to_generic_arg(&self, interner: &I) -> GenericArg<I> {
2843 self.to_generic_arg_at_depth(interner, DebruijnIndex::INNERMOST)
2844 }
2845
2846 /// Converts the binders at the specified depth to references to those binders.
to_generic_arg_at_depth(&self, interner: &I, debruijn: DebruijnIndex) -> GenericArg<I>2847 fn to_generic_arg_at_depth(&self, interner: &I, debruijn: DebruijnIndex) -> GenericArg<I>;
2848 }
2849
2850 impl<'a, I: Interner> ToGenericArg<I> for (usize, &'a VariableKind<I>) {
to_generic_arg_at_depth(&self, interner: &I, debruijn: DebruijnIndex) -> GenericArg<I>2851 fn to_generic_arg_at_depth(&self, interner: &I, debruijn: DebruijnIndex) -> GenericArg<I> {
2852 let &(index, binder) = self;
2853 let bound_var = BoundVar::new(debruijn, index);
2854 binder.to_bound_variable(interner, bound_var)
2855 }
2856 }
2857
2858 impl<'i, I: Interner, A: AsParameters<I>> Folder<'i, I> for &SubstFolder<'i, I, A> {
as_dyn(&mut self) -> &mut dyn Folder<'i, I>2859 fn as_dyn(&mut self) -> &mut dyn Folder<'i, I> {
2860 self
2861 }
2862
fold_free_var_ty( &mut self, bound_var: BoundVar, outer_binder: DebruijnIndex, ) -> Fallible<Ty<I>>2863 fn fold_free_var_ty(
2864 &mut self,
2865 bound_var: BoundVar,
2866 outer_binder: DebruijnIndex,
2867 ) -> Fallible<Ty<I>> {
2868 assert_eq!(bound_var.debruijn, DebruijnIndex::INNERMOST);
2869 let ty = self.at(bound_var.index);
2870 let ty = ty.assert_ty_ref(self.interner());
2871 Ok(ty.clone().shifted_in_from(self.interner(), outer_binder))
2872 }
2873
fold_free_var_lifetime( &mut self, bound_var: BoundVar, outer_binder: DebruijnIndex, ) -> Fallible<Lifetime<I>>2874 fn fold_free_var_lifetime(
2875 &mut self,
2876 bound_var: BoundVar,
2877 outer_binder: DebruijnIndex,
2878 ) -> Fallible<Lifetime<I>> {
2879 assert_eq!(bound_var.debruijn, DebruijnIndex::INNERMOST);
2880 let l = self.at(bound_var.index);
2881 let l = l.assert_lifetime_ref(self.interner());
2882 Ok(l.clone().shifted_in_from(self.interner(), outer_binder))
2883 }
2884
fold_free_var_const( &mut self, _ty: Ty<I>, bound_var: BoundVar, outer_binder: DebruijnIndex, ) -> Fallible<Const<I>>2885 fn fold_free_var_const(
2886 &mut self,
2887 _ty: Ty<I>,
2888 bound_var: BoundVar,
2889 outer_binder: DebruijnIndex,
2890 ) -> Fallible<Const<I>> {
2891 assert_eq!(bound_var.debruijn, DebruijnIndex::INNERMOST);
2892 let c = self.at(bound_var.index);
2893 let c = c.assert_const_ref(self.interner());
2894 Ok(c.clone().shifted_in_from(self.interner(), outer_binder))
2895 }
2896
interner(&self) -> &'i I2897 fn interner(&self) -> &'i I {
2898 self.interner
2899 }
2900 }
2901
2902 macro_rules! interned_slice_common {
2903 ($seq:ident, $data:ident => $elem:ty, $intern:ident => $interned:ident) => {
2904 /// List of interned elements.
2905 #[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, HasInterner)]
2906 pub struct $seq<I: Interner> {
2907 interned: I::$interned,
2908 }
2909
2910 impl<I: Interner> $seq<I> {
2911 /// Get the interned elements.
2912 pub fn interned(&self) -> &I::$interned {
2913 &self.interned
2914 }
2915
2916 /// Returns a slice containing the elements.
2917 pub fn as_slice(&self, interner: &I) -> &[$elem] {
2918 Interner::$data(interner, &self.interned)
2919 }
2920
2921 /// Index into the sequence.
2922 pub fn at(&self, interner: &I, index: usize) -> &$elem {
2923 &self.as_slice(interner)[index]
2924 }
2925
2926 /// Create an empty sequence.
2927 pub fn empty(interner: &I) -> Self {
2928 Self::from_iter(interner, None::<$elem>)
2929 }
2930
2931 /// Check whether this is an empty sequence.
2932 pub fn is_empty(&self, interner: &I) -> bool {
2933 self.as_slice(interner).is_empty()
2934 }
2935
2936 /// Get an iterator over the elements of the sequence.
2937 pub fn iter(&self, interner: &I) -> std::slice::Iter<'_, $elem> {
2938 self.as_slice(interner).iter()
2939 }
2940
2941 /// Get the length of the sequence.
2942 pub fn len(&self, interner: &I) -> usize {
2943 self.as_slice(interner).len()
2944 }
2945 }
2946 };
2947 }
2948
2949 macro_rules! interned_slice {
2950 ($seq:ident, $data:ident => $elem:ty, $intern:ident => $interned:ident) => {
2951 interned_slice_common!($seq, $data => $elem, $intern => $interned);
2952
2953 impl<I: Interner> $seq<I> {
2954 /// Tries to create a sequence using an iterator of element-like things.
2955 pub fn from_fallible<E>(
2956 interner: &I,
2957 elements: impl IntoIterator<Item = Result<impl CastTo<$elem>, E>>,
2958 ) -> Result<Self, E> {
2959 Ok(Self {
2960 interned: I::$intern(interner, elements.into_iter().casted(interner))?,
2961 })
2962 }
2963
2964 /// Create a sequence from elements
2965 pub fn from_iter(
2966 interner: &I,
2967 elements: impl IntoIterator<Item = impl CastTo<$elem>>,
2968 ) -> Self {
2969 Self::from_fallible(
2970 interner,
2971 elements
2972 .into_iter()
2973 .map(|el| -> Result<$elem, ()> { Ok(el.cast(interner)) }),
2974 )
2975 .unwrap()
2976 }
2977
2978 /// Create a sequence from a single element.
2979 pub fn from1(interner: &I, element: impl CastTo<$elem>) -> Self {
2980 Self::from_iter(interner, Some(element))
2981 }
2982 }
2983 };
2984 }
2985
2986 interned_slice!(
2987 QuantifiedWhereClauses,
2988 quantified_where_clauses_data => QuantifiedWhereClause<I>,
2989 intern_quantified_where_clauses => InternedQuantifiedWhereClauses
2990 );
2991
2992 interned_slice!(
2993 ProgramClauses,
2994 program_clauses_data => ProgramClause<I>,
2995 intern_program_clauses => InternedProgramClauses
2996 );
2997
2998 interned_slice!(
2999 VariableKinds,
3000 variable_kinds_data => VariableKind<I>,
3001 intern_generic_arg_kinds => InternedVariableKinds
3002 );
3003
3004 interned_slice!(
3005 CanonicalVarKinds,
3006 canonical_var_kinds_data => CanonicalVarKind<I>,
3007 intern_canonical_var_kinds => InternedCanonicalVarKinds
3008 );
3009
3010 interned_slice!(Goals, goals_data => Goal<I>, intern_goals => InternedGoals);
3011
3012 interned_slice!(
3013 Constraints,
3014 constraints_data => InEnvironment<Constraint<I>>,
3015 intern_constraints => InternedConstraints
3016 );
3017
3018 interned_slice!(
3019 Substitution,
3020 substitution_data => GenericArg<I>,
3021 intern_substitution => InternedSubstitution
3022 );
3023
3024 interned_slice_common!(
3025 Variances,
3026 variances_data => Variance,
3027 intern_variance => InternedVariances
3028 );
3029
3030 impl<I: Interner> Variances<I> {
3031 /// Tries to create a list of canonical variable kinds using an iterator.
from_fallible<E>( interner: &I, variances: impl IntoIterator<Item = Result<Variance, E>>, ) -> Result<Self, E>3032 pub fn from_fallible<E>(
3033 interner: &I,
3034 variances: impl IntoIterator<Item = Result<Variance, E>>,
3035 ) -> Result<Self, E> {
3036 Ok(Variances {
3037 interned: I::intern_variances(interner, variances.into_iter())?,
3038 })
3039 }
3040
3041 /// Creates a list of canonical variable kinds using an iterator.
from_iter(interner: &I, variances: impl IntoIterator<Item = Variance>) -> Self3042 pub fn from_iter(interner: &I, variances: impl IntoIterator<Item = Variance>) -> Self {
3043 Self::from_fallible(
3044 interner,
3045 variances
3046 .into_iter()
3047 .map(|p| -> Result<Variance, ()> { Ok(p) }),
3048 )
3049 .unwrap()
3050 }
3051
3052 /// Creates a list of canonical variable kinds from a single canonical variable kind.
from1(interner: &I, variance: Variance) -> Self3053 pub fn from1(interner: &I, variance: Variance) -> Self {
3054 Self::from_iter(interner, Some(variance))
3055 }
3056 }
3057
3058 /// Combines a substitution (`subst`) with a set of region constraints
3059 /// (`constraints`). This represents the result of a query; the
3060 /// substitution stores the values for the query's unknown variables,
3061 /// and the constraints represents any region constraints that must
3062 /// additionally be solved.
3063 #[derive(Clone, Debug, PartialEq, Eq, Hash, Fold, Visit, HasInterner)]
3064 pub struct ConstrainedSubst<I: Interner> {
3065 /// The substitution that is being constrained.
3066 ///
3067 /// NB: The `is_trivial` routine relies on the fact that `subst` is folded first.
3068 pub subst: Substitution<I>,
3069
3070 /// Region constraints that constrain the substitution.
3071 pub constraints: Constraints<I>,
3072 }
3073
3074 /// The resulting substitution after solving a goal.
3075 #[derive(Clone, Debug, PartialEq, Eq, Hash, Fold, Visit, HasInterner)]
3076 pub struct AnswerSubst<I: Interner> {
3077 /// The substitution result.
3078 ///
3079 /// NB: The `is_trivial` routine relies on the fact that `subst` is folded first.
3080 pub subst: Substitution<I>,
3081
3082 /// List of constraints that are part of the answer.
3083 pub constraints: Constraints<I>,
3084
3085 /// Delayed subgoals, used when the solver answered with an (incomplete) `Answer` (instead of a `CompleteAnswer`).
3086 pub delayed_subgoals: Vec<InEnvironment<Goal<I>>>,
3087 }
3088
3089 /// Logic to decide the Variance for a given subst
3090 pub trait UnificationDatabase<I>
3091 where
3092 Self: std::fmt::Debug,
3093 I: Interner,
3094 {
3095 /// Gets the variances for the substitution of a fn def
fn_def_variance(&self, fn_def_id: FnDefId<I>) -> Variances<I>3096 fn fn_def_variance(&self, fn_def_id: FnDefId<I>) -> Variances<I>;
3097
3098 /// Gets the variances for the substitution of a adt
adt_variance(&self, adt_id: AdtId<I>) -> Variances<I>3099 fn adt_variance(&self, adt_id: AdtId<I>) -> Variances<I>;
3100 }
3101