src/librustc/traits/mod.rs

   1 //! Trait Resolution. See the [rustc guide] for more information on how this works.
   2 //!
   3 //! [rustc guide]: https://rust-lang.github.io/rustc-guide/traits/resolution.html
   4
   5 #[allow(dead_code)]
   6 pub mod auto_trait;
   7 mod chalk_fulfill;
   8 mod coherence;
   9 pub mod error_reporting;
  10 mod engine;
  11 mod fulfill;
  12 mod project;
  13 mod object_safety;
  14 mod on_unimplemented;
  15 mod select;
  16 mod specialize;
  17 mod structural_impls;
  18 pub mod codegen;
  19 mod util;
  20 pub mod query;
  21
  22 use chalk_engine;
  23 use crate::hir;
  24 use crate::hir::def_id::DefId;
  25 use crate::infer::{InferCtxt, SuppressRegionErrors};
  26 use crate::infer::outlives::env::OutlivesEnvironment;
  27 use crate::middle::region;
  28 use crate::mir::interpret::ErrorHandled;
  29 use rustc_data_structures::sync::Lrc;
  30 use rustc_macros::HashStable;
  31 use syntax::ast;
  32 use syntax_pos::{Span, DUMMY_SP};
  33 use crate::ty::subst::{InternalSubsts, SubstsRef};
  34 use crate::ty::{self, AdtKind, List, Ty, TyCtxt, GenericParamDefKind, ToPredicate};
  35 use crate::ty::error::{ExpectedFound, TypeError};
  36 use crate::ty::fold::{TypeFolder, TypeFoldable, TypeVisitor};
  37 use crate::util::common::ErrorReported;
  38
  39 use std::fmt::Debug;
  40 use std::rc::Rc;
  41
  42 pub use self::SelectionError::*;
  43 pub use self::FulfillmentErrorCode::*;
  44 pub use self::Vtable::*;
  45 pub use self::ObligationCauseCode::*;
  46
  47 pub use self::coherence::{add_placeholder_note, orphan_check, overlapping_impls};
  48 pub use self::coherence::{OrphanCheckErr, OverlapResult};
  49 pub use self::fulfill::{FulfillmentContext, PendingPredicateObligation};
  50 pub use self::project::MismatchedProjectionTypes;
  51 pub use self::project::{normalize, normalize_projection_type, poly_project_and_unify_type};
  52 pub use self::project::{ProjectionCache, ProjectionCacheSnapshot, Reveal, Normalized};
  53 pub use self::object_safety::ObjectSafetyViolation;
  54 pub use self::object_safety::MethodViolationCode;
  55 pub use self::on_unimplemented::{OnUnimplementedDirective, OnUnimplementedNote};
  56 pub use self::select::{EvaluationCache, SelectionContext, SelectionCache};
  57 pub use self::select::{EvaluationResult, IntercrateAmbiguityCause, OverflowError};
  58 pub use self::specialize::{OverlapError, specialization_graph, translate_substs};
  59 pub use self::specialize::find_associated_item;
  60 pub use self::specialize::specialization_graph::FutureCompatOverlapError;
  61 pub use self::specialize::specialization_graph::FutureCompatOverlapErrorKind;
  62 pub use self::engine::{TraitEngine, TraitEngineExt};
  63 pub use self::util::{elaborate_predicates, elaborate_trait_ref, elaborate_trait_refs};
  64 pub use self::util::{supertraits, supertrait_def_ids, transitive_bounds,
  65                      Supertraits, SupertraitDefIds};
  66
  67 pub use self::chalk_fulfill::{
  68     CanonicalGoal as ChalkCanonicalGoal,
  69     FulfillmentContext as ChalkFulfillmentContext
  70 };
  71
  72 pub use self::ObligationCauseCode::*;
  73 pub use self::FulfillmentErrorCode::*;
  74 pub use self::SelectionError::*;
  75 pub use self::Vtable::*;
  76
  77 /// Whether to enable bug compatibility with issue #43355.
  78 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
  79 pub enum IntercrateMode {
  80     Issue43355,
  81     Fixed
  82 }
  83
  84 /// The mode that trait queries run in.
  85 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
  86 pub enum TraitQueryMode {
  87     // Standard/un-canonicalized queries get accurate
  88     // spans etc. passed in and hence can do reasonable
  89     // error reporting on their own.
  90     Standard,
  91     // Canonicalized queries get dummy spans and hence
  92     // must generally propagate errors to
  93     // pre-canonicalization callsites.
  94     Canonical,
  95 }
  96
  97 /// An `Obligation` represents some trait reference (e.g., `int: Eq`) for
  98 /// which the vtable must be found. The process of finding a vtable is
  99 /// called "resolving" the `Obligation`. This process consists of
 100 /// either identifying an `impl` (e.g., `impl Eq for int`) that
 101 /// provides the required vtable, or else finding a bound that is in
 102 /// scope. The eventual result is usually a `Selection` (defined below).
 103 #[derive(Clone, PartialEq, Eq, Hash)]
 104 pub struct Obligation<'tcx, T> {
 105     /// The reason we have to prove this thing.
 106     pub cause: ObligationCause<'tcx>,
 107
 108     /// The environment in which we should prove this thing.
 109     pub param_env: ty::ParamEnv<'tcx>,
 110
 111     /// The thing we are trying to prove.
 112     pub predicate: T,
 113
 114     /// If we started proving this as a result of trying to prove
 115     /// something else, track the total depth to ensure termination.
 116     /// If this goes over a certain threshold, we abort compilation --
 117     /// in such cases, we can not say whether or not the predicate
 118     /// holds for certain. Stupid halting problem; such a drag.
 119     pub recursion_depth: usize,
 120 }
 121
 122 pub type PredicateObligation<'tcx> = Obligation<'tcx, ty::Predicate<'tcx>>;
 123 pub type TraitObligation<'tcx> = Obligation<'tcx, ty::PolyTraitPredicate<'tcx>>;
 124
 125 /// The reason why we incurred this obligation; used for error reporting.
 126 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
 127 pub struct ObligationCause<'tcx> {
 128     pub span: Span,
 129
 130     /// The ID of the fn body that triggered this obligation. This is
 131     /// used for region obligations to determine the precise
 132     /// environment in which the region obligation should be evaluated
 133     /// (in particular, closures can add new assumptions). See the
 134     /// field `region_obligations` of the `FulfillmentContext` for more
 135     /// information.
 136     pub body_id: hir::HirId,
 137
 138     pub code: ObligationCauseCode<'tcx>
 139 }
 140
 141 impl<'tcx> ObligationCause<'tcx> {
 142     pub fn span<'a, 'gcx>(&self, tcx: &TyCtxt<'a, 'gcx, 'tcx>) -> Span {
 143         match self.code {
 144             ObligationCauseCode::CompareImplMethodObligation { .. } |
 145             ObligationCauseCode::MainFunctionType |
 146             ObligationCauseCode::StartFunctionType => {
 147                 tcx.sess.source_map().def_span(self.span)
 148             }
 149             ObligationCauseCode::MatchExpressionArm { arm_span, .. } => arm_span,
 150             _ => self.span,
 151         }
 152     }
 153 }
 154
 155 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
 156 pub enum ObligationCauseCode<'tcx> {
 157     /// Not well classified or should be obvious from the span.
 158     MiscObligation,
 159
 160     /// A slice or array is WF only if `T: Sized`.
 161     SliceOrArrayElem,
 162
 163     /// A tuple is WF only if its middle elements are `Sized`.
 164     TupleElem,
 165
 166     /// This is the trait reference from the given projection.
 167     ProjectionWf(ty::ProjectionTy<'tcx>),
 168
 169     /// In an impl of trait `X` for type `Y`, type `Y` must
 170     /// also implement all supertraits of `X`.
 171     ItemObligation(DefId),
 172
 173     /// A type like `&'a T` is WF only if `T: 'a`.
 174     ReferenceOutlivesReferent(Ty<'tcx>),
 175
 176     /// A type like `Box<Foo<'a> + 'b>` is WF only if `'b: 'a`.
 177     ObjectTypeBound(Ty<'tcx>, ty::Region<'tcx>),
 178
 179     /// Obligation incurred due to an object cast.
 180     ObjectCastObligation(/* Object type */ Ty<'tcx>),
 181
 182     // Various cases where expressions must be sized/copy/etc:
 183     /// L = X implies that L is Sized
 184     AssignmentLhsSized,
 185     /// (x1, .., xn) must be Sized
 186     TupleInitializerSized,
 187     /// S { ... } must be Sized
 188     StructInitializerSized,
 189     /// Type of each variable must be Sized
 190     VariableType(ast::NodeId),
 191     /// Argument type must be Sized
 192     SizedArgumentType,
 193     /// Return type must be Sized
 194     SizedReturnType,
 195     /// Yield type must be Sized
 196     SizedYieldType,
 197     /// [T,..n] --> T must be Copy
 198     RepeatVec,
 199
 200     /// Types of fields (other than the last, except for packed structs) in a struct must be sized.
 201     FieldSized { adt_kind: AdtKind, last: bool },
 202
 203     /// Constant expressions must be sized.
 204     ConstSized,
 205
 206     /// static items must have `Sync` type
 207     SharedStatic,
 208
 209     BuiltinDerivedObligation(DerivedObligationCause<'tcx>),
 210
 211     ImplDerivedObligation(DerivedObligationCause<'tcx>),
 212
 213     /// error derived when matching traits/impls; see ObligationCause for more details
 214     CompareImplMethodObligation {
 215         item_name: ast::Name,
 216         impl_item_def_id: DefId,
 217         trait_item_def_id: DefId,
 218     },
 219
 220     /// Checking that this expression can be assigned where it needs to be
 221     // FIXME(eddyb) #11161 is the original Expr required?
 222     ExprAssignable,
 223
 224     /// Computing common supertype in the arms of a match expression
 225     MatchExpressionArm {
 226         arm_span: Span,
 227         source: hir::MatchSource,
 228         prior_arms: Vec<Span>,
 229         last_ty: Ty<'tcx>,
 230     },
 231
 232     /// Computing common supertype in the pattern guard for the arms of a match expression
 233     MatchExpressionArmPattern { span: Span, ty: Ty<'tcx> },
 234
 235     /// Computing common supertype in an if expression
 236     IfExpression {
 237         then: Span,
 238         outer: Option<Span>,
 239         semicolon: Option<Span>,
 240     },
 241
 242     /// Computing common supertype of an if expression with no else counter-part
 243     IfExpressionWithNoElse,
 244
 245     /// `main` has wrong type
 246     MainFunctionType,
 247
 248     /// `start` has wrong type
 249     StartFunctionType,
 250
 251     /// intrinsic has wrong type
 252     IntrinsicType,
 253
 254     /// method receiver
 255     MethodReceiver,
 256
 257     /// `return` with no expression
 258     ReturnNoExpression,
 259
 260     /// `return` with an expression
 261     ReturnType(hir::HirId),
 262
 263     /// Block implicit return
 264     BlockTailExpression(hir::HirId),
 265
 266     /// #[feature(trivial_bounds)] is not enabled
 267     TrivialBound,
 268 }
 269
 270 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
 271 pub struct DerivedObligationCause<'tcx> {
 272     /// The trait reference of the parent obligation that led to the
 273     /// current obligation. Note that only trait obligations lead to
 274     /// derived obligations, so we just store the trait reference here
 275     /// directly.
 276     parent_trait_ref: ty::PolyTraitRef<'tcx>,
 277
 278     /// The parent trait had this cause.
 279     parent_code: Rc<ObligationCauseCode<'tcx>>
 280 }
 281
 282 pub type Obligations<'tcx, O> = Vec<Obligation<'tcx, O>>;
 283 pub type PredicateObligations<'tcx> = Vec<PredicateObligation<'tcx>>;
 284 pub type TraitObligations<'tcx> = Vec<TraitObligation<'tcx>>;
 285
 286 /// The following types:
 287 /// * `WhereClause`,
 288 /// * `WellFormed`,
 289 /// * `FromEnv`,
 290 /// * `DomainGoal`,
 291 /// * `Goal`,
 292 /// * `Clause`,
 293 /// * `Environment`,
 294 /// * `InEnvironment`,
 295 /// are used for representing the trait system in the form of
 296 /// logic programming clauses. They are part of the interface
 297 /// for the chalk SLG solver.
 298 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, HashStable)]
 299 pub enum WhereClause<'tcx> {
 300     Implemented(ty::TraitPredicate<'tcx>),
 301     ProjectionEq(ty::ProjectionPredicate<'tcx>),
 302     RegionOutlives(ty::RegionOutlivesPredicate<'tcx>),
 303     TypeOutlives(ty::TypeOutlivesPredicate<'tcx>),
 304 }
 305
 306 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, HashStable)]
 307 pub enum WellFormed<'tcx> {
 308     Trait(ty::TraitPredicate<'tcx>),
 309     Ty(Ty<'tcx>),
 310 }
 311
 312 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, HashStable)]
 313 pub enum FromEnv<'tcx> {
 314     Trait(ty::TraitPredicate<'tcx>),
 315     Ty(Ty<'tcx>),
 316 }
 317
 318 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, HashStable)]
 319 pub enum DomainGoal<'tcx> {
 320     Holds(WhereClause<'tcx>),
 321     WellFormed(WellFormed<'tcx>),
 322     FromEnv(FromEnv<'tcx>),
 323     Normalize(ty::ProjectionPredicate<'tcx>),
 324 }
 325
 326 pub type PolyDomainGoal<'tcx> = ty::Binder<DomainGoal<'tcx>>;
 327
 328 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable)]
 329 pub enum QuantifierKind {
 330     Universal,
 331     Existential,
 332 }
 333
 334 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable)]
 335 pub enum GoalKind<'tcx> {
 336     Implies(Clauses<'tcx>, Goal<'tcx>),
 337     And(Goal<'tcx>, Goal<'tcx>),
 338     Not(Goal<'tcx>),
 339     DomainGoal(DomainGoal<'tcx>),
 340     Quantified(QuantifierKind, ty::Binder<Goal<'tcx>>),
 341     Subtype(Ty<'tcx>, Ty<'tcx>),
 342     CannotProve,
 343 }
 344
 345 pub type Goal<'tcx> = &'tcx GoalKind<'tcx>;
 346
 347 pub type Goals<'tcx> = &'tcx List<Goal<'tcx>>;
 348
 349 impl<'tcx> DomainGoal<'tcx> {
 350     pub fn into_goal(self) -> GoalKind<'tcx> {
 351         GoalKind::DomainGoal(self)
 352     }
 353
 354     pub fn into_program_clause(self) -> ProgramClause<'tcx> {
 355         ProgramClause {
 356             goal: self,
 357             hypotheses: ty::List::empty(),
 358             category: ProgramClauseCategory::Other,
 359         }
 360     }
 361 }
 362
 363 impl<'tcx> GoalKind<'tcx> {
 364     pub fn from_poly_domain_goal<'a, 'gcx>(
 365         domain_goal: PolyDomainGoal<'tcx>,
 366         tcx: TyCtxt<'a, 'gcx, 'tcx>,
 367     ) -> GoalKind<'tcx> {
 368         match domain_goal.no_bound_vars() {
 369             Some(p) => p.into_goal(),
 370             None => GoalKind::Quantified(
 371                 QuantifierKind::Universal,
 372                 domain_goal.map_bound(|p| tcx.mk_goal(p.into_goal()))
 373             ),
 374         }
 375     }
 376 }
 377
 378 /// This matches the definition from Page 7 of "A Proof Procedure for the Logic of Hereditary
 379 /// Harrop Formulas".
 380 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable)]
 381 pub enum Clause<'tcx> {
 382     Implies(ProgramClause<'tcx>),
 383     ForAll(ty::Binder<ProgramClause<'tcx>>),
 384 }
 385
 386 impl Clause<'tcx> {
 387     pub fn category(self) -> ProgramClauseCategory {
 388         match self {
 389             Clause::Implies(clause) => clause.category,
 390             Clause::ForAll(clause) => clause.skip_binder().category,
 391         }
 392     }
 393 }
 394
 395 /// Multiple clauses.
 396 pub type Clauses<'tcx> = &'tcx List<Clause<'tcx>>;
 397
 398 /// A "program clause" has the form `D :- G1, ..., Gn`. It is saying
 399 /// that the domain goal `D` is true if `G1...Gn` are provable. This
 400 /// is equivalent to the implication `G1..Gn => D`; we usually write
 401 /// it with the reverse implication operator `:-` to emphasize the way
 402 /// that programs are actually solved (via backchaining, which starts
 403 /// with the goal to solve and proceeds from there).
 404 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable)]
 405 pub struct ProgramClause<'tcx> {
 406     /// This goal will be considered true ...
 407     pub goal: DomainGoal<'tcx>,
 408
 409     /// ... if we can prove these hypotheses (there may be no hypotheses at all):
 410     pub hypotheses: Goals<'tcx>,
 411
 412     /// Useful for filtering clauses.
 413     pub category: ProgramClauseCategory,
 414 }
 415
 416 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable)]
 417 pub enum ProgramClauseCategory {
 418     ImpliedBound,
 419     WellFormed,
 420     Other,
 421 }
 422
 423 /// A set of clauses that we assume to be true.
 424 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable)]
 425 pub struct Environment<'tcx> {
 426     pub clauses: Clauses<'tcx>,
 427 }
 428
 429 impl Environment<'tcx> {
 430     pub fn with<G>(self, goal: G) -> InEnvironment<'tcx, G> {
 431         InEnvironment {
 432             environment: self,
 433             goal,
 434         }
 435     }
 436 }
 437
 438 /// Something (usually a goal), along with an environment.
 439 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable)]
 440 pub struct InEnvironment<'tcx, G> {
 441     pub environment: Environment<'tcx>,
 442     pub goal: G,
 443 }
 444
 445 pub type Selection<'tcx> = Vtable<'tcx, PredicateObligation<'tcx>>;
 446
 447 #[derive(Clone,Debug)]
 448 pub enum SelectionError<'tcx> {
 449     Unimplemented,
 450     OutputTypeParameterMismatch(ty::PolyTraitRef<'tcx>,
 451                                 ty::PolyTraitRef<'tcx>,
 452                                 ty::error::TypeError<'tcx>),
 453     TraitNotObjectSafe(DefId),
 454     ConstEvalFailure(ErrorHandled),
 455     Overflow,
 456 }
 457
 458 pub struct FulfillmentError<'tcx> {
 459     pub obligation: PredicateObligation<'tcx>,
 460     pub code: FulfillmentErrorCode<'tcx>
 461 }
 462
 463 #[derive(Clone)]
 464 pub enum FulfillmentErrorCode<'tcx> {
 465     CodeSelectionError(SelectionError<'tcx>),
 466     CodeProjectionError(MismatchedProjectionTypes<'tcx>),
 467     CodeSubtypeError(ExpectedFound<Ty<'tcx>>,
 468                      TypeError<'tcx>), // always comes from a SubtypePredicate
 469     CodeAmbiguity,
 470 }
 471
 472 /// When performing resolution, it is typically the case that there
 473 /// can be one of three outcomes:
 474 ///
 475 /// - `Ok(Some(r))`: success occurred with result `r`
 476 /// - `Ok(None)`: could not definitely determine anything, usually due
 477 ///   to inconclusive type inference.
 478 /// - `Err(e)`: error `e` occurred
 479 pub type SelectionResult<'tcx, T> = Result<Option<T>, SelectionError<'tcx>>;
 480
 481 /// Given the successful resolution of an obligation, the `Vtable`
 482 /// indicates where the vtable comes from. Note that while we call this
 483 /// a "vtable", it does not necessarily indicate dynamic dispatch at
 484 /// runtime. `Vtable` instances just tell the compiler where to find
 485 /// methods, but in generic code those methods are typically statically
 486 /// dispatched -- only when an object is constructed is a `Vtable`
 487 /// instance reified into an actual vtable.
 488 ///
 489 /// For example, the vtable may be tied to a specific impl (case A),
 490 /// or it may be relative to some bound that is in scope (case B).
 491 ///
 492 /// ```
 493 /// impl<T:Clone> Clone<T> for Option<T> { ... } // Impl_1
 494 /// impl<T:Clone> Clone<T> for Box<T> { ... }    // Impl_2
 495 /// impl Clone for int { ... }             // Impl_3
 496 ///
 497 /// fn foo<T:Clone>(concrete: Option<Box<int>>,
 498 ///                 param: T,
 499 ///                 mixed: Option<T>) {
 500 ///
 501 ///    // Case A: Vtable points at a specific impl. Only possible when
 502 ///    // type is concretely known. If the impl itself has bounded
 503 ///    // type parameters, Vtable will carry resolutions for those as well:
 504 ///    concrete.clone(); // Vtable(Impl_1, [Vtable(Impl_2, [Vtable(Impl_3)])])
 505 ///
 506 ///    // Case B: Vtable must be provided by caller. This applies when
 507 ///    // type is a type parameter.
 508 ///    param.clone();    // VtableParam
 509 ///
 510 ///    // Case C: A mix of cases A and B.
 511 ///    mixed.clone();    // Vtable(Impl_1, [VtableParam])
 512 /// }
 513 /// ```
 514 ///
 515 /// ### The type parameter `N`
 516 ///
 517 /// See explanation on `VtableImplData`.
 518 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable)]
 519 pub enum Vtable<'tcx, N> {
 520     /// Vtable identifying a particular impl.
 521     VtableImpl(VtableImplData<'tcx, N>),
 522
 523     /// Vtable for auto trait implementations.
 524     /// This carries the information and nested obligations with regards
 525     /// to an auto implementation for a trait `Trait`. The nested obligations
 526     /// ensure the trait implementation holds for all the constituent types.
 527     VtableAutoImpl(VtableAutoImplData<N>),
 528
 529     /// Successful resolution to an obligation provided by the caller
 530     /// for some type parameter. The `Vec<N>` represents the
 531     /// obligations incurred from normalizing the where-clause (if
 532     /// any).
 533     VtableParam(Vec<N>),
 534
 535     /// Virtual calls through an object.
 536     VtableObject(VtableObjectData<'tcx, N>),
 537
 538     /// Successful resolution for a builtin trait.
 539     VtableBuiltin(VtableBuiltinData<N>),
 540
 541     /// Vtable automatically generated for a closure. The `DefId` is the ID
 542     /// of the closure expression. This is a `VtableImpl` in spirit, but the
 543     /// impl is generated by the compiler and does not appear in the source.
 544     VtableClosure(VtableClosureData<'tcx, N>),
 545
 546     /// Same as above, but for a function pointer type with the given signature.
 547     VtableFnPointer(VtableFnPointerData<'tcx, N>),
 548
 549     /// Vtable automatically generated for a generator.
 550     VtableGenerator(VtableGeneratorData<'tcx, N>),
 551
 552     /// Vtable for a trait alias.
 553     VtableTraitAlias(VtableTraitAliasData<'tcx, N>),
 554 }
 555
 556 /// Identifies a particular impl in the source, along with a set of
 557 /// substitutions from the impl's type/lifetime parameters. The
 558 /// `nested` vector corresponds to the nested obligations attached to
 559 /// the impl's type parameters.
 560 ///
 561 /// The type parameter `N` indicates the type used for "nested
 562 /// obligations" that are required by the impl. During type check, this
 563 /// is `Obligation`, as one might expect. During codegen, however, this
 564 /// is `()`, because codegen only requires a shallow resolution of an
 565 /// impl, and nested obligations are satisfied later.
 566 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable)]
 567 pub struct VtableImplData<'tcx, N> {
 568     pub impl_def_id: DefId,
 569     pub substs: SubstsRef<'tcx>,
 570     pub nested: Vec<N>
 571 }
 572
 573 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable)]
 574 pub struct VtableGeneratorData<'tcx, N> {
 575     pub generator_def_id: DefId,
 576     pub substs: ty::GeneratorSubsts<'tcx>,
 577     /// Nested obligations. This can be non-empty if the generator
 578     /// signature contains associated types.
 579     pub nested: Vec<N>
 580 }
 581
 582 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable)]
 583 pub struct VtableClosureData<'tcx, N> {
 584     pub closure_def_id: DefId,
 585     pub substs: ty::ClosureSubsts<'tcx>,
 586     /// Nested obligations. This can be non-empty if the closure
 587     /// signature contains associated types.
 588     pub nested: Vec<N>
 589 }
 590
 591 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable)]
 592 pub struct VtableAutoImplData<N> {
 593     pub trait_def_id: DefId,
 594     pub nested: Vec<N>
 595 }
 596
 597 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable)]
 598 pub struct VtableBuiltinData<N> {
 599     pub nested: Vec<N>
 600 }
 601
 602 /// A vtable for some object-safe trait `Foo` automatically derived
 603 /// for the object type `Foo`.
 604 #[derive(PartialEq, Eq, Clone, RustcEncodable, RustcDecodable, HashStable)]
 605 pub struct VtableObjectData<'tcx, N> {
 606     /// `Foo` upcast to the obligation trait. This will be some supertrait of `Foo`.
 607     pub upcast_trait_ref: ty::PolyTraitRef<'tcx>,
 608
 609     /// The vtable is formed by concatenating together the method lists of
 610     /// the base object trait and all supertraits; this is the start of
 611     /// `upcast_trait_ref`'s methods in that vtable.
 612     pub vtable_base: usize,
 613
 614     pub nested: Vec<N>,
 615 }
 616
 617 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable)]
 618 pub struct VtableFnPointerData<'tcx, N> {
 619     pub fn_ty: Ty<'tcx>,
 620     pub nested: Vec<N>
 621 }
 622
 623 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable)]
 624 pub struct VtableTraitAliasData<'tcx, N> {
 625     pub alias_def_id: DefId,
 626     pub substs: SubstsRef<'tcx>,
 627     pub nested: Vec<N>,
 628 }
 629
 630 /// Creates predicate obligations from the generic bounds.
 631 pub fn predicates_for_generics<'tcx>(cause: ObligationCause<'tcx>,
 632                                      param_env: ty::ParamEnv<'tcx>,
 633                                      generic_bounds: &ty::InstantiatedPredicates<'tcx>)
 634                                      -> PredicateObligations<'tcx>
 635 {
 636     util::predicates_for_generics(cause, 0, param_env, generic_bounds)
 637 }
 638
 639 /// Determines whether the type `ty` is known to meet `bound` and
 640 /// returns true if so. Returns false if `ty` either does not meet
 641 /// `bound` or is not known to meet bound (note that this is
 642 /// conservative towards *no impl*, which is the opposite of the
 643 /// `evaluate` methods).
 644 pub fn type_known_to_meet_bound_modulo_regions<'a, 'gcx, 'tcx>(
 645     infcx: &InferCtxt<'a, 'gcx, 'tcx>,
 646     param_env: ty::ParamEnv<'tcx>,
 647     ty: Ty<'tcx>,
 648     def_id: DefId,
 649     span: Span,
 650 ) -> bool {
 651     debug!("type_known_to_meet_bound_modulo_regions(ty={:?}, bound={:?})",
 652            ty,
 653            infcx.tcx.item_path_str(def_id));
 654
 655     let trait_ref = ty::TraitRef {
 656         def_id,
 657         substs: infcx.tcx.mk_substs_trait(ty, &[]),
 658     };
 659     let obligation = Obligation {
 660         param_env,
 661         cause: ObligationCause::misc(span, hir::DUMMY_HIR_ID),
 662         recursion_depth: 0,
 663         predicate: trait_ref.to_predicate(),
 664     };
 665
 666     let result = infcx.predicate_must_hold_modulo_regions(&obligation);
 667     debug!("type_known_to_meet_ty={:?} bound={} => {:?}",
 668            ty, infcx.tcx.item_path_str(def_id), result);
 669
 670     if result && (ty.has_infer_types() || ty.has_closure_types()) {
 671         // Because of inference "guessing", selection can sometimes claim
 672         // to succeed while the success requires a guess. To ensure
 673         // this function's result remains infallible, we must confirm
 674         // that guess. While imperfect, I believe this is sound.
 675
 676         // The handling of regions in this area of the code is terrible,
 677         // see issue #29149. We should be able to improve on this with
 678         // NLL.
 679         let mut fulfill_cx = FulfillmentContext::new_ignoring_regions();
 680
 681         // We can use a dummy node-id here because we won't pay any mind
 682         // to region obligations that arise (there shouldn't really be any
 683         // anyhow).
 684         let cause = ObligationCause::misc(span, hir::DUMMY_HIR_ID);
 685
 686         fulfill_cx.register_bound(infcx, param_env, ty, def_id, cause);
 687
 688         // Note: we only assume something is `Copy` if we can
 689         // *definitively* show that it implements `Copy`. Otherwise,
 690         // assume it is move; linear is always ok.
 691         match fulfill_cx.select_all_or_error(infcx) {
 692             Ok(()) => {
 693                 debug!("type_known_to_meet_bound_modulo_regions: ty={:?} bound={} success",
 694                        ty,
 695                        infcx.tcx.item_path_str(def_id));
 696                 true
 697             }
 698             Err(e) => {
 699                 debug!("type_known_to_meet_bound_modulo_regions: ty={:?} bound={} errors={:?}",
 700                        ty,
 701                        infcx.tcx.item_path_str(def_id),
 702                        e);
 703                 false
 704             }
 705         }
 706     } else {
 707         result
 708     }
 709 }
 710
 711 fn do_normalize_predicates<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 712                                      region_context: DefId,
 713                                      cause: ObligationCause<'tcx>,
 714                                      elaborated_env: ty::ParamEnv<'tcx>,
 715                                      predicates: Vec<ty::Predicate<'tcx>>)
 716                                      -> Result<Vec<ty::Predicate<'tcx>>, ErrorReported>
 717 {
 718     debug!(
 719         "do_normalize_predicates(predicates={:?}, region_context={:?}, cause={:?})",
 720         predicates,
 721         region_context,
 722         cause,
 723     );
 724     let span = cause.span;
 725     tcx.infer_ctxt().enter(|infcx| {
 726         // FIXME. We should really... do something with these region
 727         // obligations. But this call just continues the older
 728         // behavior (i.e., doesn't cause any new bugs), and it would
 729         // take some further refactoring to actually solve them. In
 730         // particular, we would have to handle implied bounds
 731         // properly, and that code is currently largely confined to
 732         // regionck (though I made some efforts to extract it
 733         // out). -nmatsakis
 734         //
 735         // @arielby: In any case, these obligations are checked
 736         // by wfcheck anyway, so I'm not sure we have to check
 737         // them here too, and we will remove this function when
 738         // we move over to lazy normalization *anyway*.
 739         let fulfill_cx = FulfillmentContext::new_ignoring_regions();
 740         let predicates = match fully_normalize(
 741             &infcx,
 742             fulfill_cx,
 743             cause,
 744             elaborated_env,
 745             &predicates,
 746         ) {
 747             Ok(predicates) => predicates,
 748             Err(errors) => {
 749                 infcx.report_fulfillment_errors(&errors, None, false);
 750                 return Err(ErrorReported)
 751             }
 752         };
 753
 754         debug!("do_normalize_predictes: normalized predicates = {:?}", predicates);
 755
 756         let region_scope_tree = region::ScopeTree::default();
 757
 758         // We can use the `elaborated_env` here; the region code only
 759         // cares about declarations like `'a: 'b`.
 760         let outlives_env = OutlivesEnvironment::new(elaborated_env);
 761
 762         infcx.resolve_regions_and_report_errors(
 763             region_context,
 764             &region_scope_tree,
 765             &outlives_env,
 766             SuppressRegionErrors::default(),
 767         );
 768
 769         let predicates = match infcx.fully_resolve(&predicates) {
 770             Ok(predicates) => predicates,
 771             Err(fixup_err) => {
 772                 // If we encounter a fixup error, it means that some type
 773                 // variable wound up unconstrained. I actually don't know
 774                 // if this can happen, and I certainly don't expect it to
 775                 // happen often, but if it did happen it probably
 776                 // represents a legitimate failure due to some kind of
 777                 // unconstrained variable, and it seems better not to ICE,
 778                 // all things considered.
 779                 tcx.sess.span_err(span, &fixup_err.to_string());
 780                 return Err(ErrorReported)
 781             }
 782         };
 783
 784         match tcx.lift_to_global(&predicates) {
 785             Some(predicates) => Ok(predicates),
 786             None => {
 787                 // FIXME: shouldn't we, you know, actually report an error here? or an ICE?
 788                 Err(ErrorReported)
 789             }
 790         }
 791     })
 792 }
 793
 794 // FIXME: this is gonna need to be removed ...
 795 /// Normalizes the parameter environment, reporting errors if they occur.
 796 pub fn normalize_param_env_or_error<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 797                                               region_context: DefId,
 798                                               unnormalized_env: ty::ParamEnv<'tcx>,
 799                                               cause: ObligationCause<'tcx>)
 800                                               -> ty::ParamEnv<'tcx>
 801 {
 802     // I'm not wild about reporting errors here; I'd prefer to
 803     // have the errors get reported at a defined place (e.g.,
 804     // during typeck). Instead I have all parameter
 805     // environments, in effect, going through this function
 806     // and hence potentially reporting errors. This ensures of
 807     // course that we never forget to normalize (the
 808     // alternative seemed like it would involve a lot of
 809     // manual invocations of this fn -- and then we'd have to
 810     // deal with the errors at each of those sites).
 811     //
 812     // In any case, in practice, typeck constructs all the
 813     // parameter environments once for every fn as it goes,
 814     // and errors will get reported then; so after typeck we
 815     // can be sure that no errors should occur.
 816
 817     debug!("normalize_param_env_or_error(region_context={:?}, unnormalized_env={:?}, cause={:?})",
 818            region_context, unnormalized_env, cause);
 819
 820     let mut predicates: Vec<_> =
 821         util::elaborate_predicates(tcx, unnormalized_env.caller_bounds.to_vec())
 822             .collect();
 823
 824     debug!("normalize_param_env_or_error: elaborated-predicates={:?}",
 825            predicates);
 826
 827     let elaborated_env = ty::ParamEnv::new(
 828         tcx.intern_predicates(&predicates),
 829         unnormalized_env.reveal,
 830         unnormalized_env.def_id
 831     );
 832
 833     // HACK: we are trying to normalize the param-env inside *itself*. The problem is that
 834     // normalization expects its param-env to be already normalized, which means we have
 835     // a circularity.
 836     //
 837     // The way we handle this is by normalizing the param-env inside an unnormalized version
 838     // of the param-env, which means that if the param-env contains unnormalized projections,
 839     // we'll have some normalization failures. This is unfortunate.
 840     //
 841     // Lazy normalization would basically handle this by treating just the
 842     // normalizing-a-trait-ref-requires-itself cycles as evaluation failures.
 843     //
 844     // Inferred outlives bounds can create a lot of `TypeOutlives` predicates for associated
 845     // types, so to make the situation less bad, we normalize all the predicates *but*
 846     // the `TypeOutlives` predicates first inside the unnormalized parameter environment, and
 847     // then we normalize the `TypeOutlives` bounds inside the normalized parameter environment.
 848     //
 849     // This works fairly well because trait matching  does not actually care about param-env
 850     // TypeOutlives predicates - these are normally used by regionck.
 851     let outlives_predicates: Vec<_> = predicates.drain_filter(|predicate| {
 852         match predicate {
 853             ty::Predicate::TypeOutlives(..) => true,
 854             _ => false
 855         }
 856     }).collect();
 857
 858     debug!("normalize_param_env_or_error: predicates=(non-outlives={:?}, outlives={:?})",
 859            predicates, outlives_predicates);
 860     let non_outlives_predicates =
 861         match do_normalize_predicates(tcx, region_context, cause.clone(),
 862                                       elaborated_env, predicates) {
 863             Ok(predicates) => predicates,
 864             // An unnormalized env is better than nothing.
 865             Err(ErrorReported) => {
 866                 debug!("normalize_param_env_or_error: errored resolving non-outlives predicates");
 867                 return elaborated_env
 868             }
 869         };
 870
 871     debug!("normalize_param_env_or_error: non-outlives predicates={:?}", non_outlives_predicates);
 872
 873     // Not sure whether it is better to include the unnormalized TypeOutlives predicates
 874     // here. I believe they should not matter, because we are ignoring TypeOutlives param-env
 875     // predicates here anyway. Keeping them here anyway because it seems safer.
 876     let outlives_env: Vec<_> =
 877         non_outlives_predicates.iter().chain(&outlives_predicates).cloned().collect();
 878     let outlives_env = ty::ParamEnv::new(
 879         tcx.intern_predicates(&outlives_env),
 880         unnormalized_env.reveal,
 881         None
 882     );
 883     let outlives_predicates =
 884         match do_normalize_predicates(tcx, region_context, cause,
 885                                       outlives_env, outlives_predicates) {
 886             Ok(predicates) => predicates,
 887             // An unnormalized env is better than nothing.
 888             Err(ErrorReported) => {
 889                 debug!("normalize_param_env_or_error: errored resolving outlives predicates");
 890                 return elaborated_env
 891             }
 892         };
 893     debug!("normalize_param_env_or_error: outlives predicates={:?}", outlives_predicates);
 894
 895     let mut predicates = non_outlives_predicates;
 896     predicates.extend(outlives_predicates);
 897     debug!("normalize_param_env_or_error: final predicates={:?}", predicates);
 898     ty::ParamEnv::new(
 899         tcx.intern_predicates(&predicates),
 900         unnormalized_env.reveal,
 901         unnormalized_env.def_id
 902     )
 903 }
 904
 905 pub fn fully_normalize<'a, 'gcx, 'tcx, T>(
 906     infcx: &InferCtxt<'a, 'gcx, 'tcx>,
 907     mut fulfill_cx: FulfillmentContext<'tcx>,
 908     cause: ObligationCause<'tcx>,
 909     param_env: ty::ParamEnv<'tcx>,
 910     value: &T)
 911     -> Result<T, Vec<FulfillmentError<'tcx>>>
 912     where T : TypeFoldable<'tcx>
 913 {
 914     debug!("fully_normalize_with_fulfillcx(value={:?})", value);
 915     let selcx = &mut SelectionContext::new(infcx);
 916     let Normalized { value: normalized_value, obligations } =
 917         project::normalize(selcx, param_env, cause, value);
 918     debug!("fully_normalize: normalized_value={:?} obligations={:?}",
 919            normalized_value,
 920            obligations);
 921     for obligation in obligations {
 922         fulfill_cx.register_predicate_obligation(selcx.infcx(), obligation);
 923     }
 924
 925     debug!("fully_normalize: select_all_or_error start");
 926     fulfill_cx.select_all_or_error(infcx)?;
 927     debug!("fully_normalize: select_all_or_error complete");
 928     let resolved_value = infcx.resolve_type_vars_if_possible(&normalized_value);
 929     debug!("fully_normalize: resolved_value={:?}", resolved_value);
 930     Ok(resolved_value)
 931 }
 932
 933 /// Normalizes the predicates and checks whether they hold in an empty
 934 /// environment. If this returns false, then either normalize
 935 /// encountered an error or one of the predicates did not hold. Used
 936 /// when creating vtables to check for unsatisfiable methods.
 937 fn normalize_and_test_predicates<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 938                                            predicates: Vec<ty::Predicate<'tcx>>)
 939                                            -> bool
 940 {
 941     debug!("normalize_and_test_predicates(predicates={:?})",
 942            predicates);
 943
 944     let result = tcx.infer_ctxt().enter(|infcx| {
 945         let param_env = ty::ParamEnv::reveal_all();
 946         let mut selcx = SelectionContext::new(&infcx);
 947         let mut fulfill_cx = FulfillmentContext::new();
 948         let cause = ObligationCause::dummy();
 949         let Normalized { value: predicates, obligations } =
 950             normalize(&mut selcx, param_env, cause.clone(), &predicates);
 951         for obligation in obligations {
 952             fulfill_cx.register_predicate_obligation(&infcx, obligation);
 953         }
 954         for predicate in predicates {
 955             let obligation = Obligation::new(cause.clone(), param_env, predicate);
 956             fulfill_cx.register_predicate_obligation(&infcx, obligation);
 957         }
 958
 959         fulfill_cx.select_all_or_error(&infcx).is_ok()
 960     });
 961     debug!("normalize_and_test_predicates(predicates={:?}) = {:?}",
 962            predicates, result);
 963     result
 964 }
 965
 966 fn substitute_normalize_and_test_predicates<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 967                                                       key: (DefId, SubstsRef<'tcx>))
 968                                                       -> bool
 969 {
 970     debug!("substitute_normalize_and_test_predicates(key={:?})",
 971            key);
 972
 973     let predicates = tcx.predicates_of(key.0).instantiate(tcx, key.1).predicates;
 974     let result = normalize_and_test_predicates(tcx, predicates);
 975
 976     debug!("substitute_normalize_and_test_predicates(key={:?}) = {:?}",
 977            key, result);
 978     result
 979 }
 980
 981 /// Given a trait `trait_ref`, iterates the vtable entries
 982 /// that come from `trait_ref`, including its supertraits.
 983 #[inline] // FIXME(#35870): avoid closures being unexported due to `impl Trait`.
 984 fn vtable_methods<'a, 'tcx>(
 985     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 986     trait_ref: ty::PolyTraitRef<'tcx>)
 987     -> Lrc<Vec<Option<(DefId, SubstsRef<'tcx>)>>>
 988 {
 989     debug!("vtable_methods({:?})", trait_ref);
 990
 991     Lrc::new(
 992         supertraits(tcx, trait_ref).flat_map(move |trait_ref| {
 993             let trait_methods = tcx.associated_items(trait_ref.def_id())
 994                 .filter(|item| item.kind == ty::AssociatedKind::Method);
 995
 996             // Now list each method's DefId and InternalSubsts (for within its trait).
 997             // If the method can never be called from this object, produce None.
 998             trait_methods.map(move |trait_method| {
 999                 debug!("vtable_methods: trait_method={:?}", trait_method);
1000                 let def_id = trait_method.def_id;
1001
1002                 // Some methods cannot be called on an object; skip those.
1003                 if !tcx.is_vtable_safe_method(trait_ref.def_id(), &trait_method) {
1004                     debug!("vtable_methods: not vtable safe");
1005                     return None;
1006                 }
1007
1008                 // the method may have some early-bound lifetimes, add
1009                 // regions for those
1010                 let substs = trait_ref.map_bound(|trait_ref|
1011                     InternalSubsts::for_item(tcx, def_id, |param, _|
1012                         match param.kind {
1013                             GenericParamDefKind::Lifetime => tcx.types.re_erased.into(),
1014                             GenericParamDefKind::Type { .. } |
1015                             GenericParamDefKind::Const => {
1016                                 trait_ref.substs[param.index as usize]
1017                             }
1018                         }
1019                     )
1020                 );
1021
1022                 // the trait type may have higher-ranked lifetimes in it;
1023                 // so erase them if they appear, so that we get the type
1024                 // at some particular call site
1025                 let substs = tcx.normalize_erasing_late_bound_regions(
1026                     ty::ParamEnv::reveal_all(),
1027                     &substs
1028                 );
1029
1030                 // It's possible that the method relies on where clauses that
1031                 // do not hold for this particular set of type parameters.
1032                 // Note that this method could then never be called, so we
1033                 // do not want to try and codegen it, in that case (see #23435).
1034                 let predicates = tcx.predicates_of(def_id).instantiate_own(tcx, substs);
1035                 if !normalize_and_test_predicates(tcx, predicates.predicates) {
1036                     debug!("vtable_methods: predicates do not hold");
1037                     return None;
1038                 }
1039
1040                 Some((def_id, substs))
1041             })
1042         }).collect()
1043     )
1044 }
1045
1046 impl<'tcx,O> Obligation<'tcx,O> {
1047     pub fn new(cause: ObligationCause<'tcx>,
1048                param_env: ty::ParamEnv<'tcx>,
1049                predicate: O)
1050                -> Obligation<'tcx, O>
1051     {
1052         Obligation { cause, param_env, recursion_depth: 0, predicate }
1053     }
1054
1055     fn with_depth(cause: ObligationCause<'tcx>,
1056                   recursion_depth: usize,
1057                   param_env: ty::ParamEnv<'tcx>,
1058                   predicate: O)
1059                   -> Obligation<'tcx, O>
1060     {
1061         Obligation { cause, param_env, recursion_depth, predicate }
1062     }
1063
1064     pub fn misc(span: Span,
1065                 body_id: hir::HirId,
1066                 param_env: ty::ParamEnv<'tcx>,
1067                 trait_ref: O)
1068                 -> Obligation<'tcx, O> {
1069         Obligation::new(ObligationCause::misc(span, body_id), param_env, trait_ref)
1070     }
1071
1072     pub fn with<P>(&self, value: P) -> Obligation<'tcx,P> {
1073         Obligation { cause: self.cause.clone(),
1074                      param_env: self.param_env,
1075                      recursion_depth: self.recursion_depth,
1076                      predicate: value }
1077     }
1078 }
1079
1080 impl<'tcx> ObligationCause<'tcx> {
1081     #[inline]
1082     pub fn new(span: Span,
1083                body_id: hir::HirId,
1084                code: ObligationCauseCode<'tcx>)
1085                -> ObligationCause<'tcx> {
1086         ObligationCause { span, body_id, code }
1087     }
1088
1089     pub fn misc(span: Span, body_id: hir::HirId) -> ObligationCause<'tcx> {
1090         ObligationCause { span, body_id, code: MiscObligation }
1091     }
1092
1093     pub fn dummy() -> ObligationCause<'tcx> {
1094         ObligationCause { span: DUMMY_SP, body_id: hir::CRATE_HIR_ID, code: MiscObligation }
1095     }
1096 }
1097
1098 impl<'tcx, N> Vtable<'tcx, N> {
1099     pub fn nested_obligations(self) -> Vec<N> {
1100         match self {
1101             VtableImpl(i) => i.nested,
1102             VtableParam(n) => n,
1103             VtableBuiltin(i) => i.nested,
1104             VtableAutoImpl(d) => d.nested,
1105             VtableClosure(c) => c.nested,
1106             VtableGenerator(c) => c.nested,
1107             VtableObject(d) => d.nested,
1108             VtableFnPointer(d) => d.nested,
1109             VtableTraitAlias(d) => d.nested,
1110         }
1111     }
1112
1113     pub fn map<M, F>(self, f: F) -> Vtable<'tcx, M> where F: FnMut(N) -> M {
1114         match self {
1115             VtableImpl(i) => VtableImpl(VtableImplData {
1116                 impl_def_id: i.impl_def_id,
1117                 substs: i.substs,
1118                 nested: i.nested.into_iter().map(f).collect(),
1119             }),
1120             VtableParam(n) => VtableParam(n.into_iter().map(f).collect()),
1121             VtableBuiltin(i) => VtableBuiltin(VtableBuiltinData {
1122                 nested: i.nested.into_iter().map(f).collect(),
1123             }),
1124             VtableObject(o) => VtableObject(VtableObjectData {
1125                 upcast_trait_ref: o.upcast_trait_ref,
1126                 vtable_base: o.vtable_base,
1127                 nested: o.nested.into_iter().map(f).collect(),
1128             }),
1129             VtableAutoImpl(d) => VtableAutoImpl(VtableAutoImplData {
1130                 trait_def_id: d.trait_def_id,
1131                 nested: d.nested.into_iter().map(f).collect(),
1132             }),
1133             VtableClosure(c) => VtableClosure(VtableClosureData {
1134                 closure_def_id: c.closure_def_id,
1135                 substs: c.substs,
1136                 nested: c.nested.into_iter().map(f).collect(),
1137             }),
1138             VtableGenerator(c) => VtableGenerator(VtableGeneratorData {
1139                 generator_def_id: c.generator_def_id,
1140                 substs: c.substs,
1141                 nested: c.nested.into_iter().map(f).collect(),
1142             }),
1143             VtableFnPointer(p) => VtableFnPointer(VtableFnPointerData {
1144                 fn_ty: p.fn_ty,
1145                 nested: p.nested.into_iter().map(f).collect(),
1146             }),
1147             VtableTraitAlias(d) => VtableTraitAlias(VtableTraitAliasData {
1148                 alias_def_id: d.alias_def_id,
1149                 substs: d.substs,
1150                 nested: d.nested.into_iter().map(f).collect(),
1151             }),
1152         }
1153     }
1154 }
1155
1156 impl<'tcx> FulfillmentError<'tcx> {
1157     fn new(obligation: PredicateObligation<'tcx>,
1158            code: FulfillmentErrorCode<'tcx>)
1159            -> FulfillmentError<'tcx>
1160     {
1161         FulfillmentError { obligation: obligation, code: code }
1162     }
1163 }
1164
1165 impl<'tcx> TraitObligation<'tcx> {
1166     fn self_ty(&self) -> ty::Binder<Ty<'tcx>> {
1167         self.predicate.map_bound(|p| p.self_ty())
1168     }
1169 }
1170
1171 pub fn provide(providers: &mut ty::query::Providers<'_>) {
1172     *providers = ty::query::Providers {
1173         is_object_safe: object_safety::is_object_safe_provider,
1174         specialization_graph_of: specialize::specialization_graph_provider,
1175         specializes: specialize::specializes,
1176         codegen_fulfill_obligation: codegen::codegen_fulfill_obligation,
1177         vtable_methods,
1178         substitute_normalize_and_test_predicates,
1179         ..*providers
1180     };
1181 }
1182
1183 pub trait ExClauseFold<'tcx>
1184 where
1185     Self: chalk_engine::context::Context + Clone,
1186 {
1187     fn fold_ex_clause_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(
1188         ex_clause: &chalk_engine::ExClause<Self>,
1189         folder: &mut F,
1190     ) -> chalk_engine::ExClause<Self>;
1191
1192     fn visit_ex_clause_with<'gcx: 'tcx, V: TypeVisitor<'tcx>>(
1193         ex_clause: &chalk_engine::ExClause<Self>,
1194         visitor: &mut V,
1195     ) -> bool;
1196 }
1197
1198 pub trait ChalkContextLift<'tcx>
1199 where
1200     Self: chalk_engine::context::Context + Clone,
1201 {
1202     type LiftedExClause: Debug + 'tcx;
1203     type LiftedDelayedLiteral: Debug + 'tcx;
1204     type LiftedLiteral: Debug + 'tcx;
1205
1206     fn lift_ex_clause_to_tcx<'a, 'gcx>(
1207         ex_clause: &chalk_engine::ExClause<Self>,
1208         tcx: TyCtxt<'a, 'gcx, 'tcx>,
1209     ) -> Option<Self::LiftedExClause>;
1210
1211     fn lift_delayed_literal_to_tcx<'a, 'gcx>(
1212         ex_clause: &chalk_engine::DelayedLiteral<Self>,
1213         tcx: TyCtxt<'a, 'gcx, 'tcx>,
1214     ) -> Option<Self::LiftedDelayedLiteral>;
1215
1216     fn lift_literal_to_tcx<'a, 'gcx>(
1217         ex_clause: &chalk_engine::Literal<Self>,
1218         tcx: TyCtxt<'a, 'gcx, 'tcx>,
1219     ) -> Option<Self::LiftedLiteral>;
1220 }