]> git.lizzy.rs Git - rust.git/blob - src/librustc/traits/structural_impls.rs
MatchExpressionArmPattern -> Pattern
[rust.git] / src / librustc / traits / structural_impls.rs
1 use crate::traits;
2 use crate::traits::project::Normalized;
3 use crate::ty::fold::{TypeFoldable, TypeFolder, TypeVisitor};
4 use crate::ty::{self, Lift, Ty, TyCtxt};
5 use chalk_engine;
6 use smallvec::SmallVec;
7 use syntax::symbol::Symbol;
8
9 use std::collections::{BTreeMap, BTreeSet};
10 use std::fmt;
11 use std::rc::Rc;
12
13 // Structural impls for the structs in `traits`.
14
15 impl<'tcx, T: fmt::Debug> fmt::Debug for Normalized<'tcx, T> {
16     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
17         write!(f, "Normalized({:?}, {:?})", self.value, self.obligations)
18     }
19 }
20
21 impl<'tcx, O: fmt::Debug> fmt::Debug for traits::Obligation<'tcx, O> {
22     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
23         if ty::tls::with(|tcx| tcx.sess.verbose()) {
24             write!(
25                 f,
26                 "Obligation(predicate={:?}, cause={:?}, param_env={:?}, depth={})",
27                 self.predicate, self.cause, self.param_env, self.recursion_depth
28             )
29         } else {
30             write!(f, "Obligation(predicate={:?}, depth={})", self.predicate, self.recursion_depth)
31         }
32     }
33 }
34
35 impl<'tcx, N: fmt::Debug> fmt::Debug for traits::Vtable<'tcx, N> {
36     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
37         match *self {
38             super::VtableImpl(ref v) => write!(f, "{:?}", v),
39
40             super::VtableAutoImpl(ref t) => write!(f, "{:?}", t),
41
42             super::VtableClosure(ref d) => write!(f, "{:?}", d),
43
44             super::VtableGenerator(ref d) => write!(f, "{:?}", d),
45
46             super::VtableFnPointer(ref d) => write!(f, "VtableFnPointer({:?})", d),
47
48             super::VtableObject(ref d) => write!(f, "{:?}", d),
49
50             super::VtableParam(ref n) => write!(f, "VtableParam({:?})", n),
51
52             super::VtableBuiltin(ref d) => write!(f, "{:?}", d),
53
54             super::VtableTraitAlias(ref d) => write!(f, "{:?}", d),
55         }
56     }
57 }
58
59 impl<'tcx, N: fmt::Debug> fmt::Debug for traits::VtableImplData<'tcx, N> {
60     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
61         write!(
62             f,
63             "VtableImplData(impl_def_id={:?}, substs={:?}, nested={:?})",
64             self.impl_def_id, self.substs, self.nested
65         )
66     }
67 }
68
69 impl<'tcx, N: fmt::Debug> fmt::Debug for traits::VtableGeneratorData<'tcx, N> {
70     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
71         write!(
72             f,
73             "VtableGeneratorData(generator_def_id={:?}, substs={:?}, nested={:?})",
74             self.generator_def_id, self.substs, self.nested
75         )
76     }
77 }
78
79 impl<'tcx, N: fmt::Debug> fmt::Debug for traits::VtableClosureData<'tcx, N> {
80     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
81         write!(
82             f,
83             "VtableClosureData(closure_def_id={:?}, substs={:?}, nested={:?})",
84             self.closure_def_id, self.substs, self.nested
85         )
86     }
87 }
88
89 impl<N: fmt::Debug> fmt::Debug for traits::VtableBuiltinData<N> {
90     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
91         write!(f, "VtableBuiltinData(nested={:?})", self.nested)
92     }
93 }
94
95 impl<N: fmt::Debug> fmt::Debug for traits::VtableAutoImplData<N> {
96     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
97         write!(
98             f,
99             "VtableAutoImplData(trait_def_id={:?}, nested={:?})",
100             self.trait_def_id, self.nested
101         )
102     }
103 }
104
105 impl<'tcx, N: fmt::Debug> fmt::Debug for traits::VtableObjectData<'tcx, N> {
106     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
107         write!(
108             f,
109             "VtableObjectData(upcast={:?}, vtable_base={}, nested={:?})",
110             self.upcast_trait_ref, self.vtable_base, self.nested
111         )
112     }
113 }
114
115 impl<'tcx, N: fmt::Debug> fmt::Debug for traits::VtableFnPointerData<'tcx, N> {
116     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
117         write!(f, "VtableFnPointerData(fn_ty={:?}, nested={:?})", self.fn_ty, self.nested)
118     }
119 }
120
121 impl<'tcx, N: fmt::Debug> fmt::Debug for traits::VtableTraitAliasData<'tcx, N> {
122     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
123         write!(
124             f,
125             "VtableTraitAlias(alias_def_id={:?}, substs={:?}, nested={:?})",
126             self.alias_def_id, self.substs, self.nested
127         )
128     }
129 }
130
131 impl<'tcx> fmt::Debug for traits::FulfillmentError<'tcx> {
132     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
133         write!(f, "FulfillmentError({:?},{:?})", self.obligation, self.code)
134     }
135 }
136
137 impl<'tcx> fmt::Debug for traits::FulfillmentErrorCode<'tcx> {
138     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
139         match *self {
140             super::CodeSelectionError(ref e) => write!(f, "{:?}", e),
141             super::CodeProjectionError(ref e) => write!(f, "{:?}", e),
142             super::CodeSubtypeError(ref a, ref b) => {
143                 write!(f, "CodeSubtypeError({:?}, {:?})", a, b)
144             }
145             super::CodeAmbiguity => write!(f, "Ambiguity"),
146         }
147     }
148 }
149
150 impl<'tcx> fmt::Debug for traits::MismatchedProjectionTypes<'tcx> {
151     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
152         write!(f, "MismatchedProjectionTypes({:?})", self.err)
153     }
154 }
155
156 impl<'tcx> fmt::Display for traits::WhereClause<'tcx> {
157     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
158         use crate::traits::WhereClause::*;
159
160         // Bypass `ty::print` because it does not print out anonymous regions.
161         // FIXME(eddyb) implement a custom `PrettyPrinter`, or move this to `ty::print`.
162         fn write_region_name<'tcx>(
163             r: ty::Region<'tcx>,
164             fmt: &mut fmt::Formatter<'_>,
165         ) -> fmt::Result {
166             match r {
167                 ty::ReLateBound(index, br) => match br {
168                     ty::BoundRegion::BrNamed(_, name) => write!(fmt, "{}", name),
169                     ty::BoundRegion::BrAnon(var) => {
170                         if *index == ty::INNERMOST {
171                             write!(fmt, "'^{}", var)
172                         } else {
173                             write!(fmt, "'^{}_{}", index.index(), var)
174                         }
175                     }
176                     _ => write!(fmt, "'_"),
177                 },
178
179                 _ => write!(fmt, "{}", r),
180             }
181         }
182
183         match self {
184             Implemented(trait_ref) => write!(fmt, "Implemented({})", trait_ref),
185             ProjectionEq(projection) => write!(fmt, "ProjectionEq({})", projection),
186             RegionOutlives(predicate) => {
187                 write!(fmt, "RegionOutlives({}: ", predicate.0)?;
188                 write_region_name(predicate.1, fmt)?;
189                 write!(fmt, ")")
190             }
191             TypeOutlives(predicate) => {
192                 write!(fmt, "TypeOutlives({}: ", predicate.0)?;
193                 write_region_name(predicate.1, fmt)?;
194                 write!(fmt, ")")
195             }
196         }
197     }
198 }
199
200 impl<'tcx> fmt::Display for traits::WellFormed<'tcx> {
201     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
202         use crate::traits::WellFormed::*;
203
204         match self {
205             Trait(trait_ref) => write!(fmt, "WellFormed({})", trait_ref),
206             Ty(ty) => write!(fmt, "WellFormed({})", ty),
207         }
208     }
209 }
210
211 impl<'tcx> fmt::Display for traits::FromEnv<'tcx> {
212     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
213         use crate::traits::FromEnv::*;
214
215         match self {
216             Trait(trait_ref) => write!(fmt, "FromEnv({})", trait_ref),
217             Ty(ty) => write!(fmt, "FromEnv({})", ty),
218         }
219     }
220 }
221
222 impl<'tcx> fmt::Display for traits::DomainGoal<'tcx> {
223     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
224         use crate::traits::DomainGoal::*;
225
226         match self {
227             Holds(wc) => write!(fmt, "{}", wc),
228             WellFormed(wf) => write!(fmt, "{}", wf),
229             FromEnv(from_env) => write!(fmt, "{}", from_env),
230             Normalize(projection) => {
231                 write!(fmt, "Normalize({} -> {})", projection.projection_ty, projection.ty)
232             }
233         }
234     }
235 }
236
237 impl fmt::Display for traits::QuantifierKind {
238     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
239         use crate::traits::QuantifierKind::*;
240
241         match self {
242             Universal => write!(fmt, "forall"),
243             Existential => write!(fmt, "exists"),
244         }
245     }
246 }
247
248 /// Collect names for regions / types bound by a quantified goal / clause.
249 /// This collector does not try to do anything clever like in `ty::print`, it's just used
250 /// for debug output in tests anyway.
251 struct BoundNamesCollector {
252     // Just sort by name because `BoundRegion::BrNamed` does not have a `BoundVar` index anyway.
253     regions: BTreeSet<Symbol>,
254
255     // Sort by `BoundVar` index, so usually this should be equivalent to the order given
256     // by the list of type parameters.
257     types: BTreeMap<u32, Symbol>,
258
259     binder_index: ty::DebruijnIndex,
260 }
261
262 impl BoundNamesCollector {
263     fn new() -> Self {
264         BoundNamesCollector {
265             regions: BTreeSet::new(),
266             types: BTreeMap::new(),
267             binder_index: ty::INNERMOST,
268         }
269     }
270
271     fn is_empty(&self) -> bool {
272         self.regions.is_empty() && self.types.is_empty()
273     }
274
275     fn write_names(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
276         let mut start = true;
277         for r in &self.regions {
278             if !start {
279                 write!(fmt, ", ")?;
280             }
281             start = false;
282             write!(fmt, "{}", r)?;
283         }
284         for (_, t) in &self.types {
285             if !start {
286                 write!(fmt, ", ")?;
287             }
288             start = false;
289             write!(fmt, "{}", t)?;
290         }
291         Ok(())
292     }
293 }
294
295 impl<'tcx> TypeVisitor<'tcx> for BoundNamesCollector {
296     fn visit_binder<T: TypeFoldable<'tcx>>(&mut self, t: &ty::Binder<T>) -> bool {
297         self.binder_index.shift_in(1);
298         let result = t.super_visit_with(self);
299         self.binder_index.shift_out(1);
300         result
301     }
302
303     fn visit_ty(&mut self, t: Ty<'tcx>) -> bool {
304         match t.kind {
305             ty::Bound(debruijn, bound_ty) if debruijn == self.binder_index => {
306                 self.types.insert(
307                     bound_ty.var.as_u32(),
308                     match bound_ty.kind {
309                         ty::BoundTyKind::Param(name) => name,
310                         ty::BoundTyKind::Anon => {
311                             Symbol::intern(&format!("^{}", bound_ty.var.as_u32()))
312                         }
313                     },
314                 );
315             }
316
317             _ => (),
318         };
319
320         t.super_visit_with(self)
321     }
322
323     fn visit_region(&mut self, r: ty::Region<'tcx>) -> bool {
324         match r {
325             ty::ReLateBound(index, br) if *index == self.binder_index => match br {
326                 ty::BoundRegion::BrNamed(_, name) => {
327                     self.regions.insert(*name);
328                 }
329
330                 ty::BoundRegion::BrAnon(var) => {
331                     self.regions.insert(Symbol::intern(&format!("'^{}", var)));
332                 }
333
334                 _ => (),
335             },
336
337             _ => (),
338         };
339
340         r.super_visit_with(self)
341     }
342 }
343
344 impl<'tcx> fmt::Display for traits::Goal<'tcx> {
345     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
346         use crate::traits::GoalKind::*;
347
348         match self {
349             Implies(hypotheses, goal) => {
350                 write!(fmt, "if (")?;
351                 for (index, hyp) in hypotheses.iter().enumerate() {
352                     if index > 0 {
353                         write!(fmt, ", ")?;
354                     }
355                     write!(fmt, "{}", hyp)?;
356                 }
357                 write!(fmt, ") {{ {} }}", goal)
358             }
359             And(goal1, goal2) => write!(fmt, "({} && {})", goal1, goal2),
360             Not(goal) => write!(fmt, "not {{ {} }}", goal),
361             DomainGoal(goal) => write!(fmt, "{}", goal),
362             Quantified(qkind, goal) => {
363                 let mut collector = BoundNamesCollector::new();
364                 goal.skip_binder().visit_with(&mut collector);
365
366                 if !collector.is_empty() {
367                     write!(fmt, "{}<", qkind)?;
368                     collector.write_names(fmt)?;
369                     write!(fmt, "> {{ ")?;
370                 }
371
372                 write!(fmt, "{}", goal.skip_binder())?;
373
374                 if !collector.is_empty() {
375                     write!(fmt, " }}")?;
376                 }
377
378                 Ok(())
379             }
380             Subtype(a, b) => write!(fmt, "{} <: {}", a, b),
381             CannotProve => write!(fmt, "CannotProve"),
382         }
383     }
384 }
385
386 impl<'tcx> fmt::Display for traits::ProgramClause<'tcx> {
387     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
388         let traits::ProgramClause { goal, hypotheses, .. } = self;
389         write!(fmt, "{}", goal)?;
390         if !hypotheses.is_empty() {
391             write!(fmt, " :- ")?;
392             for (index, condition) in hypotheses.iter().enumerate() {
393                 if index > 0 {
394                     write!(fmt, ", ")?;
395                 }
396                 write!(fmt, "{}", condition)?;
397             }
398         }
399         write!(fmt, ".")
400     }
401 }
402
403 impl<'tcx> fmt::Display for traits::Clause<'tcx> {
404     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
405         use crate::traits::Clause::*;
406
407         match self {
408             Implies(clause) => write!(fmt, "{}", clause),
409             ForAll(clause) => {
410                 let mut collector = BoundNamesCollector::new();
411                 clause.skip_binder().visit_with(&mut collector);
412
413                 if !collector.is_empty() {
414                     write!(fmt, "forall<")?;
415                     collector.write_names(fmt)?;
416                     write!(fmt, "> {{ ")?;
417                 }
418
419                 write!(fmt, "{}", clause.skip_binder())?;
420
421                 if !collector.is_empty() {
422                     write!(fmt, " }}")?;
423                 }
424
425                 Ok(())
426             }
427         }
428     }
429 }
430
431 ///////////////////////////////////////////////////////////////////////////
432 // Lift implementations
433
434 impl<'a, 'tcx> Lift<'tcx> for traits::SelectionError<'a> {
435     type Lifted = traits::SelectionError<'tcx>;
436     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
437         match *self {
438             super::Unimplemented => Some(super::Unimplemented),
439             super::OutputTypeParameterMismatch(a, b, ref err) => {
440                 tcx.lift(&(a, b)).and_then(|(a, b)| {
441                     tcx.lift(err).map(|err| super::OutputTypeParameterMismatch(a, b, err))
442                 })
443             }
444             super::TraitNotObjectSafe(def_id) => Some(super::TraitNotObjectSafe(def_id)),
445             super::ConstEvalFailure(err) => Some(super::ConstEvalFailure(err)),
446             super::Overflow => Some(super::Overflow),
447         }
448     }
449 }
450
451 impl<'a, 'tcx> Lift<'tcx> for traits::ObligationCauseCode<'a> {
452     type Lifted = traits::ObligationCauseCode<'tcx>;
453     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
454         match *self {
455             super::ReturnNoExpression => Some(super::ReturnNoExpression),
456             super::MiscObligation => Some(super::MiscObligation),
457             super::SliceOrArrayElem => Some(super::SliceOrArrayElem),
458             super::TupleElem => Some(super::TupleElem),
459             super::ProjectionWf(proj) => tcx.lift(&proj).map(super::ProjectionWf),
460             super::ItemObligation(def_id) => Some(super::ItemObligation(def_id)),
461             super::BindingObligation(def_id, span) => Some(super::BindingObligation(def_id, span)),
462             super::ReferenceOutlivesReferent(ty) => {
463                 tcx.lift(&ty).map(super::ReferenceOutlivesReferent)
464             }
465             super::ObjectTypeBound(ty, r) => tcx
466                 .lift(&ty)
467                 .and_then(|ty| tcx.lift(&r).and_then(|r| Some(super::ObjectTypeBound(ty, r)))),
468             super::ObjectCastObligation(ty) => tcx.lift(&ty).map(super::ObjectCastObligation),
469             super::Coercion { source, target } => {
470                 Some(super::Coercion { source: tcx.lift(&source)?, target: tcx.lift(&target)? })
471             }
472             super::AssignmentLhsSized => Some(super::AssignmentLhsSized),
473             super::TupleInitializerSized => Some(super::TupleInitializerSized),
474             super::StructInitializerSized => Some(super::StructInitializerSized),
475             super::VariableType(id) => Some(super::VariableType(id)),
476             super::ReturnValue(id) => Some(super::ReturnValue(id)),
477             super::ReturnType => Some(super::ReturnType),
478             super::SizedArgumentType => Some(super::SizedArgumentType),
479             super::SizedReturnType => Some(super::SizedReturnType),
480             super::SizedYieldType => Some(super::SizedYieldType),
481             super::RepeatVec(suggest_flag) => Some(super::RepeatVec(suggest_flag)),
482             super::FieldSized { adt_kind, last } => Some(super::FieldSized { adt_kind, last }),
483             super::ConstSized => Some(super::ConstSized),
484             super::ConstPatternStructural => Some(super::ConstPatternStructural),
485             super::SharedStatic => Some(super::SharedStatic),
486             super::BuiltinDerivedObligation(ref cause) => {
487                 tcx.lift(cause).map(super::BuiltinDerivedObligation)
488             }
489             super::ImplDerivedObligation(ref cause) => {
490                 tcx.lift(cause).map(super::ImplDerivedObligation)
491             }
492             super::CompareImplMethodObligation {
493                 item_name,
494                 impl_item_def_id,
495                 trait_item_def_id,
496             } => Some(super::CompareImplMethodObligation {
497                 item_name,
498                 impl_item_def_id,
499                 trait_item_def_id,
500             }),
501             super::CompareImplTypeObligation { item_name, impl_item_def_id, trait_item_def_id } => {
502                 Some(super::CompareImplTypeObligation {
503                     item_name,
504                     impl_item_def_id,
505                     trait_item_def_id,
506                 })
507             }
508             super::ExprAssignable => Some(super::ExprAssignable),
509             super::MatchExpressionArm(box super::MatchExpressionArmCause {
510                 arm_span,
511                 source,
512                 ref prior_arms,
513                 last_ty,
514                 discrim_hir_id,
515             }) => tcx.lift(&last_ty).map(|last_ty| {
516                 super::MatchExpressionArm(box super::MatchExpressionArmCause {
517                     arm_span,
518                     source,
519                     prior_arms: prior_arms.clone(),
520                     last_ty,
521                     discrim_hir_id,
522                 })
523             }),
524             super::Pattern { span, ty } => tcx.lift(&ty).map(|ty| super::Pattern { span, ty }),
525             super::IfExpression(box super::IfExpressionCause { then, outer, semicolon }) => {
526                 Some(super::IfExpression(box super::IfExpressionCause { then, outer, semicolon }))
527             }
528             super::IfExpressionWithNoElse => Some(super::IfExpressionWithNoElse),
529             super::MainFunctionType => Some(super::MainFunctionType),
530             super::StartFunctionType => Some(super::StartFunctionType),
531             super::IntrinsicType => Some(super::IntrinsicType),
532             super::MethodReceiver => Some(super::MethodReceiver),
533             super::BlockTailExpression(id) => Some(super::BlockTailExpression(id)),
534             super::TrivialBound => Some(super::TrivialBound),
535             super::AssocTypeBound(ref data) => Some(super::AssocTypeBound(data.clone())),
536         }
537     }
538 }
539
540 impl<'a, 'tcx> Lift<'tcx> for traits::DerivedObligationCause<'a> {
541     type Lifted = traits::DerivedObligationCause<'tcx>;
542     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
543         tcx.lift(&self.parent_trait_ref).and_then(|trait_ref| {
544             tcx.lift(&*self.parent_code).map(|code| traits::DerivedObligationCause {
545                 parent_trait_ref: trait_ref,
546                 parent_code: Rc::new(code),
547             })
548         })
549     }
550 }
551
552 impl<'a, 'tcx> Lift<'tcx> for traits::ObligationCause<'a> {
553     type Lifted = traits::ObligationCause<'tcx>;
554     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
555         tcx.lift(&self.code).map(|code| traits::ObligationCause {
556             span: self.span,
557             body_id: self.body_id,
558             code,
559         })
560     }
561 }
562
563 // For codegen only.
564 impl<'a, 'tcx> Lift<'tcx> for traits::Vtable<'a, ()> {
565     type Lifted = traits::Vtable<'tcx, ()>;
566     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
567         match self.clone() {
568             traits::VtableImpl(traits::VtableImplData { impl_def_id, substs, nested }) => {
569                 tcx.lift(&substs).map(|substs| {
570                     traits::VtableImpl(traits::VtableImplData { impl_def_id, substs, nested })
571                 })
572             }
573             traits::VtableAutoImpl(t) => Some(traits::VtableAutoImpl(t)),
574             traits::VtableGenerator(traits::VtableGeneratorData {
575                 generator_def_id,
576                 substs,
577                 nested,
578             }) => tcx.lift(&substs).map(|substs| {
579                 traits::VtableGenerator(traits::VtableGeneratorData {
580                     generator_def_id: generator_def_id,
581                     substs: substs,
582                     nested: nested,
583                 })
584             }),
585             traits::VtableClosure(traits::VtableClosureData { closure_def_id, substs, nested }) => {
586                 tcx.lift(&substs).map(|substs| {
587                     traits::VtableClosure(traits::VtableClosureData {
588                         closure_def_id,
589                         substs,
590                         nested,
591                     })
592                 })
593             }
594             traits::VtableFnPointer(traits::VtableFnPointerData { fn_ty, nested }) => {
595                 tcx.lift(&fn_ty).map(|fn_ty| {
596                     traits::VtableFnPointer(traits::VtableFnPointerData { fn_ty, nested })
597                 })
598             }
599             traits::VtableParam(n) => Some(traits::VtableParam(n)),
600             traits::VtableBuiltin(n) => Some(traits::VtableBuiltin(n)),
601             traits::VtableObject(traits::VtableObjectData {
602                 upcast_trait_ref,
603                 vtable_base,
604                 nested,
605             }) => tcx.lift(&upcast_trait_ref).map(|trait_ref| {
606                 traits::VtableObject(traits::VtableObjectData {
607                     upcast_trait_ref: trait_ref,
608                     vtable_base,
609                     nested,
610                 })
611             }),
612             traits::VtableTraitAlias(traits::VtableTraitAliasData {
613                 alias_def_id,
614                 substs,
615                 nested,
616             }) => tcx.lift(&substs).map(|substs| {
617                 traits::VtableTraitAlias(traits::VtableTraitAliasData {
618                     alias_def_id,
619                     substs,
620                     nested,
621                 })
622             }),
623         }
624     }
625 }
626
627 impl<'a, 'tcx> Lift<'tcx> for traits::Environment<'a> {
628     type Lifted = traits::Environment<'tcx>;
629     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
630         tcx.lift(&self.clauses).map(|clauses| traits::Environment { clauses })
631     }
632 }
633
634 impl<'a, 'tcx, G: Lift<'tcx>> Lift<'tcx> for traits::InEnvironment<'a, G> {
635     type Lifted = traits::InEnvironment<'tcx, G::Lifted>;
636     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
637         tcx.lift(&self.environment).and_then(|environment| {
638             tcx.lift(&self.goal).map(|goal| traits::InEnvironment { environment, goal })
639         })
640     }
641 }
642
643 impl<'tcx, C> Lift<'tcx> for chalk_engine::ExClause<C>
644 where
645     C: chalk_engine::context::Context + Clone,
646     C: traits::ChalkContextLift<'tcx>,
647 {
648     type Lifted = C::LiftedExClause;
649
650     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
651         <C as traits::ChalkContextLift>::lift_ex_clause_to_tcx(self, tcx)
652     }
653 }
654
655 impl<'tcx, C> Lift<'tcx> for chalk_engine::DelayedLiteral<C>
656 where
657     C: chalk_engine::context::Context + Clone,
658     C: traits::ChalkContextLift<'tcx>,
659 {
660     type Lifted = C::LiftedDelayedLiteral;
661
662     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
663         <C as traits::ChalkContextLift>::lift_delayed_literal_to_tcx(self, tcx)
664     }
665 }
666
667 impl<'tcx, C> Lift<'tcx> for chalk_engine::Literal<C>
668 where
669     C: chalk_engine::context::Context + Clone,
670     C: traits::ChalkContextLift<'tcx>,
671 {
672     type Lifted = C::LiftedLiteral;
673
674     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
675         <C as traits::ChalkContextLift>::lift_literal_to_tcx(self, tcx)
676     }
677 }
678
679 ///////////////////////////////////////////////////////////////////////////
680 // TypeFoldable implementations.
681
682 impl<'tcx, O: TypeFoldable<'tcx>> TypeFoldable<'tcx> for traits::Obligation<'tcx, O> {
683     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
684         traits::Obligation {
685             cause: self.cause.clone(),
686             recursion_depth: self.recursion_depth,
687             predicate: self.predicate.fold_with(folder),
688             param_env: self.param_env.fold_with(folder),
689         }
690     }
691
692     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
693         self.predicate.visit_with(visitor)
694     }
695 }
696
697 CloneTypeFoldableAndLiftImpls! {
698     traits::QuantifierKind,
699 }
700
701 impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::List<traits::Goal<'tcx>> {
702     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
703         let v = self.iter().map(|t| t.fold_with(folder)).collect::<SmallVec<[_; 8]>>();
704         folder.tcx().intern_goals(&v)
705     }
706
707     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
708         self.iter().any(|t| t.visit_with(visitor))
709     }
710 }
711
712 impl<'tcx> TypeFoldable<'tcx> for traits::Goal<'tcx> {
713     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
714         let v = (**self).fold_with(folder);
715         folder.tcx().mk_goal(v)
716     }
717
718     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
719         (**self).visit_with(visitor)
720     }
721 }
722
723 CloneTypeFoldableAndLiftImpls! {
724     traits::ProgramClauseCategory,
725 }
726
727 impl<'tcx> TypeFoldable<'tcx> for traits::Clauses<'tcx> {
728     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
729         let v = self.iter().map(|t| t.fold_with(folder)).collect::<SmallVec<[_; 8]>>();
730         folder.tcx().intern_clauses(&v)
731     }
732
733     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
734         self.iter().any(|t| t.visit_with(visitor))
735     }
736 }
737
738 impl<'tcx, C> TypeFoldable<'tcx> for chalk_engine::ExClause<C>
739 where
740     C: traits::ExClauseFold<'tcx>,
741     C::Substitution: Clone,
742     C::RegionConstraint: Clone,
743 {
744     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
745         <C as traits::ExClauseFold>::fold_ex_clause_with(self, folder)
746     }
747
748     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
749         <C as traits::ExClauseFold>::visit_ex_clause_with(self, visitor)
750     }
751 }
752
753 EnumTypeFoldableImpl! {
754     impl<'tcx, C> TypeFoldable<'tcx> for chalk_engine::DelayedLiteral<C> {
755         (chalk_engine::DelayedLiteral::CannotProve)(a),
756         (chalk_engine::DelayedLiteral::Negative)(a),
757         (chalk_engine::DelayedLiteral::Positive)(a, b),
758     } where
759         C: chalk_engine::context::Context<CanonicalConstrainedSubst: TypeFoldable<'tcx>> + Clone,
760 }
761
762 EnumTypeFoldableImpl! {
763     impl<'tcx, C> TypeFoldable<'tcx> for chalk_engine::Literal<C> {
764         (chalk_engine::Literal::Negative)(a),
765         (chalk_engine::Literal::Positive)(a),
766     } where
767         C: chalk_engine::context::Context<GoalInEnvironment: Clone + TypeFoldable<'tcx>> + Clone,
768 }
769
770 CloneTypeFoldableAndLiftImpls! {
771     chalk_engine::TableIndex,
772 }