src/librustc/traits/structural_impls.rs

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