src/librustc/traits/mod.rs

   1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! Trait Resolution. See [rustc guide] for more info on how this works.
  12 //!
  13 //! [rustc guide]: https://rust-lang-nursery.github.io/rustc-guide/trait-resolution.html
  14
  15 pub use self::SelectionError::*;
  16 pub use self::FulfillmentErrorCode::*;
  17 pub use self::Vtable::*;
  18 pub use self::ObligationCauseCode::*;
  19
  20 use hir;
  21 use hir::def_id::DefId;
  22 use infer::outlives::env::OutlivesEnvironment;
  23 use middle::const_val::ConstEvalErr;
  24 use middle::region;
  25 use ty::subst::Substs;
  26 use ty::{self, AdtKind, Ty, TyCtxt, TypeFoldable, ToPredicate};
  27 use ty::error::{ExpectedFound, TypeError};
  28 use infer::{InferCtxt};
  29
  30 use std::rc::Rc;
  31 use syntax::ast;
  32 use syntax_pos::{Span, DUMMY_SP};
  33
  34 pub use self::coherence::{orphan_check, overlapping_impls, OrphanCheckErr, OverlapResult};
  35 pub use self::fulfill::FulfillmentContext;
  36 pub use self::project::MismatchedProjectionTypes;
  37 pub use self::project::{normalize, normalize_projection_type, poly_project_and_unify_type};
  38 pub use self::project::{ProjectionCache, ProjectionCacheSnapshot, Reveal, Normalized};
  39 pub use self::object_safety::ObjectSafetyViolation;
  40 pub use self::object_safety::MethodViolationCode;
  41 pub use self::on_unimplemented::{OnUnimplementedDirective, OnUnimplementedNote};
  42 pub use self::select::{EvaluationCache, SelectionContext, SelectionCache};
  43 pub use self::select::IntercrateAmbiguityCause;
  44 pub use self::specialize::{OverlapError, specialization_graph, translate_substs};
  45 pub use self::specialize::{SpecializesCache, find_associated_item};
  46 pub use self::util::elaborate_predicates;
  47 pub use self::util::supertraits;
  48 pub use self::util::Supertraits;
  49 pub use self::util::supertrait_def_ids;
  50 pub use self::util::SupertraitDefIds;
  51 pub use self::util::transitive_bounds;
  52
  53 mod coherence;
  54 pub mod error_reporting;
  55 mod fulfill;
  56 mod project;
  57 mod object_safety;
  58 mod on_unimplemented;
  59 mod select;
  60 mod specialize;
  61 mod structural_impls;
  62 pub mod trans;
  63 mod util;
  64
  65 // Whether to enable bug compatibility with issue #43355
  66 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
  67 pub enum IntercrateMode {
  68     Issue43355,
  69     Fixed
  70 }
  71
  72 /// An `Obligation` represents some trait reference (e.g. `int:Eq`) for
  73 /// which the vtable must be found.  The process of finding a vtable is
  74 /// called "resolving" the `Obligation`. This process consists of
  75 /// either identifying an `impl` (e.g., `impl Eq for int`) that
  76 /// provides the required vtable, or else finding a bound that is in
  77 /// scope. The eventual result is usually a `Selection` (defined below).
  78 #[derive(Clone, PartialEq, Eq, Hash)]
  79 pub struct Obligation<'tcx, T> {
  80     pub cause: ObligationCause<'tcx>,
  81     pub param_env: ty::ParamEnv<'tcx>,
  82     pub recursion_depth: usize,
  83     pub predicate: T,
  84 }
  85
  86 pub type PredicateObligation<'tcx> = Obligation<'tcx, ty::Predicate<'tcx>>;
  87 pub type TraitObligation<'tcx> = Obligation<'tcx, ty::PolyTraitPredicate<'tcx>>;
  88
  89 /// Why did we incur this obligation? Used for error reporting.
  90 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
  91 pub struct ObligationCause<'tcx> {
  92     pub span: Span,
  93
  94     // The id of the fn body that triggered this obligation. This is
  95     // used for region obligations to determine the precise
  96     // environment in which the region obligation should be evaluated
  97     // (in particular, closures can add new assumptions). See the
  98     // field `region_obligations` of the `FulfillmentContext` for more
  99     // information.
 100     pub body_id: ast::NodeId,
 101
 102     pub code: ObligationCauseCode<'tcx>
 103 }
 104
 105 impl<'tcx> ObligationCause<'tcx> {
 106     pub fn span<'a, 'gcx>(&self, tcx: &TyCtxt<'a, 'gcx, 'tcx>) -> Span {
 107         match self.code {
 108             ObligationCauseCode::CompareImplMethodObligation { .. } |
 109             ObligationCauseCode::MainFunctionType |
 110             ObligationCauseCode::StartFunctionType => {
 111                 tcx.sess.codemap().def_span(self.span)
 112             }
 113             _ => self.span,
 114         }
 115     }
 116 }
 117
 118 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
 119 pub enum ObligationCauseCode<'tcx> {
 120     /// Not well classified or should be obvious from span.
 121     MiscObligation,
 122
 123     /// A slice or array is WF only if `T: Sized`
 124     SliceOrArrayElem,
 125
 126     /// A tuple is WF only if its middle elements are Sized
 127     TupleElem,
 128
 129     /// This is the trait reference from the given projection
 130     ProjectionWf(ty::ProjectionTy<'tcx>),
 131
 132     /// In an impl of trait X for type Y, type Y must
 133     /// also implement all supertraits of X.
 134     ItemObligation(DefId),
 135
 136     /// A type like `&'a T` is WF only if `T: 'a`.
 137     ReferenceOutlivesReferent(Ty<'tcx>),
 138
 139     /// A type like `Box<Foo<'a> + 'b>` is WF only if `'b: 'a`.
 140     ObjectTypeBound(Ty<'tcx>, ty::Region<'tcx>),
 141
 142     /// Obligation incurred due to an object cast.
 143     ObjectCastObligation(/* Object type */ Ty<'tcx>),
 144
 145     // Various cases where expressions must be sized/copy/etc:
 146     /// L = X implies that L is Sized
 147     AssignmentLhsSized,
 148     /// (x1, .., xn) must be Sized
 149     TupleInitializerSized,
 150     /// S { ... } must be Sized
 151     StructInitializerSized,
 152     /// Type of each variable must be Sized
 153     VariableType(ast::NodeId),
 154     /// Return type must be Sized
 155     SizedReturnType,
 156     /// Yield type must be Sized
 157     SizedYieldType,
 158     /// [T,..n] --> T must be Copy
 159     RepeatVec,
 160
 161     /// Types of fields (other than the last) in a struct must be sized.
 162     FieldSized(AdtKind),
 163
 164     /// Constant expressions must be sized.
 165     ConstSized,
 166
 167     /// static items must have `Sync` type
 168     SharedStatic,
 169
 170     BuiltinDerivedObligation(DerivedObligationCause<'tcx>),
 171
 172     ImplDerivedObligation(DerivedObligationCause<'tcx>),
 173
 174     /// error derived when matching traits/impls; see ObligationCause for more details
 175     CompareImplMethodObligation {
 176         item_name: ast::Name,
 177         impl_item_def_id: DefId,
 178         trait_item_def_id: DefId,
 179     },
 180
 181     /// Checking that this expression can be assigned where it needs to be
 182     // FIXME(eddyb) #11161 is the original Expr required?
 183     ExprAssignable,
 184
 185     /// Computing common supertype in the arms of a match expression
 186     MatchExpressionArm { arm_span: Span,
 187                          source: hir::MatchSource },
 188
 189     /// Computing common supertype in an if expression
 190     IfExpression,
 191
 192     /// Computing common supertype of an if expression with no else counter-part
 193     IfExpressionWithNoElse,
 194
 195     /// `where a == b`
 196     EquatePredicate,
 197
 198     /// `main` has wrong type
 199     MainFunctionType,
 200
 201     /// `start` has wrong type
 202     StartFunctionType,
 203
 204     /// intrinsic has wrong type
 205     IntrinsicType,
 206
 207     /// method receiver
 208     MethodReceiver,
 209
 210     /// `return` with no expression
 211     ReturnNoExpression,
 212
 213     /// `return` with an expression
 214     ReturnType(ast::NodeId),
 215
 216     /// Block implicit return
 217     BlockTailExpression(ast::NodeId),
 218 }
 219
 220 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
 221 pub struct DerivedObligationCause<'tcx> {
 222     /// The trait reference of the parent obligation that led to the
 223     /// current obligation. Note that only trait obligations lead to
 224     /// derived obligations, so we just store the trait reference here
 225     /// directly.
 226     parent_trait_ref: ty::PolyTraitRef<'tcx>,
 227
 228     /// The parent trait had this cause
 229     parent_code: Rc<ObligationCauseCode<'tcx>>
 230 }
 231
 232 pub type Obligations<'tcx, O> = Vec<Obligation<'tcx, O>>;
 233 pub type PredicateObligations<'tcx> = Vec<PredicateObligation<'tcx>>;
 234 pub type TraitObligations<'tcx> = Vec<TraitObligation<'tcx>>;
 235
 236 pub type Selection<'tcx> = Vtable<'tcx, PredicateObligation<'tcx>>;
 237
 238 #[derive(Clone,Debug)]
 239 pub enum SelectionError<'tcx> {
 240     Unimplemented,
 241     OutputTypeParameterMismatch(ty::PolyTraitRef<'tcx>,
 242                                 ty::PolyTraitRef<'tcx>,
 243                                 ty::error::TypeError<'tcx>),
 244     TraitNotObjectSafe(DefId),
 245     ConstEvalFailure(ConstEvalErr<'tcx>),
 246 }
 247
 248 pub struct FulfillmentError<'tcx> {
 249     pub obligation: PredicateObligation<'tcx>,
 250     pub code: FulfillmentErrorCode<'tcx>
 251 }
 252
 253 #[derive(Clone)]
 254 pub enum FulfillmentErrorCode<'tcx> {
 255     CodeSelectionError(SelectionError<'tcx>),
 256     CodeProjectionError(MismatchedProjectionTypes<'tcx>),
 257     CodeSubtypeError(ExpectedFound<Ty<'tcx>>,
 258                      TypeError<'tcx>), // always comes from a SubtypePredicate
 259     CodeAmbiguity,
 260 }
 261
 262 /// When performing resolution, it is typically the case that there
 263 /// can be one of three outcomes:
 264 ///
 265 /// - `Ok(Some(r))`: success occurred with result `r`
 266 /// - `Ok(None)`: could not definitely determine anything, usually due
 267 ///   to inconclusive type inference.
 268 /// - `Err(e)`: error `e` occurred
 269 pub type SelectionResult<'tcx, T> = Result<Option<T>, SelectionError<'tcx>>;
 270
 271 /// Given the successful resolution of an obligation, the `Vtable`
 272 /// indicates where the vtable comes from. Note that while we call this
 273 /// a "vtable", it does not necessarily indicate dynamic dispatch at
 274 /// runtime. `Vtable` instances just tell the compiler where to find
 275 /// methods, but in generic code those methods are typically statically
 276 /// dispatched -- only when an object is constructed is a `Vtable`
 277 /// instance reified into an actual vtable.
 278 ///
 279 /// For example, the vtable may be tied to a specific impl (case A),
 280 /// or it may be relative to some bound that is in scope (case B).
 281 ///
 282 ///
 283 /// ```
 284 /// impl<T:Clone> Clone<T> for Option<T> { ... } // Impl_1
 285 /// impl<T:Clone> Clone<T> for Box<T> { ... }    // Impl_2
 286 /// impl Clone for int { ... }             // Impl_3
 287 ///
 288 /// fn foo<T:Clone>(concrete: Option<Box<int>>,
 289 ///                 param: T,
 290 ///                 mixed: Option<T>) {
 291 ///
 292 ///    // Case A: Vtable points at a specific impl. Only possible when
 293 ///    // type is concretely known. If the impl itself has bounded
 294 ///    // type parameters, Vtable will carry resolutions for those as well:
 295 ///    concrete.clone(); // Vtable(Impl_1, [Vtable(Impl_2, [Vtable(Impl_3)])])
 296 ///
 297 ///    // Case B: Vtable must be provided by caller. This applies when
 298 ///    // type is a type parameter.
 299 ///    param.clone();    // VtableParam
 300 ///
 301 ///    // Case C: A mix of cases A and B.
 302 ///    mixed.clone();    // Vtable(Impl_1, [VtableParam])
 303 /// }
 304 /// ```
 305 ///
 306 /// ### The type parameter `N`
 307 ///
 308 /// See explanation on `VtableImplData`.
 309 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable)]
 310 pub enum Vtable<'tcx, N> {
 311     /// Vtable identifying a particular impl.
 312     VtableImpl(VtableImplData<'tcx, N>),
 313
 314     /// Vtable for auto trait implementations
 315     /// This carries the information and nested obligations with regards
 316     /// to an auto implementation for a trait `Trait`. The nested obligations
 317     /// ensure the trait implementation holds for all the constituent types.
 318     VtableAutoImpl(VtableAutoImplData<N>),
 319
 320     /// Successful resolution to an obligation provided by the caller
 321     /// for some type parameter. The `Vec<N>` represents the
 322     /// obligations incurred from normalizing the where-clause (if
 323     /// any).
 324     VtableParam(Vec<N>),
 325
 326     /// Virtual calls through an object
 327     VtableObject(VtableObjectData<'tcx, N>),
 328
 329     /// Successful resolution for a builtin trait.
 330     VtableBuiltin(VtableBuiltinData<N>),
 331
 332     /// Vtable automatically generated for a closure. The def ID is the ID
 333     /// of the closure expression. This is a `VtableImpl` in spirit, but the
 334     /// impl is generated by the compiler and does not appear in the source.
 335     VtableClosure(VtableClosureData<'tcx, N>),
 336
 337     /// Same as above, but for a fn pointer type with the given signature.
 338     VtableFnPointer(VtableFnPointerData<'tcx, N>),
 339
 340     /// Vtable automatically generated for a generator
 341     VtableGenerator(VtableGeneratorData<'tcx, N>),
 342 }
 343
 344 /// Identifies a particular impl in the source, along with a set of
 345 /// substitutions from the impl's type/lifetime parameters. The
 346 /// `nested` vector corresponds to the nested obligations attached to
 347 /// the impl's type parameters.
 348 ///
 349 /// The type parameter `N` indicates the type used for "nested
 350 /// obligations" that are required by the impl. During type check, this
 351 /// is `Obligation`, as one might expect. During trans, however, this
 352 /// is `()`, because trans only requires a shallow resolution of an
 353 /// impl, and nested obligations are satisfied later.
 354 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable)]
 355 pub struct VtableImplData<'tcx, N> {
 356     pub impl_def_id: DefId,
 357     pub substs: &'tcx Substs<'tcx>,
 358     pub nested: Vec<N>
 359 }
 360
 361 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable)]
 362 pub struct VtableGeneratorData<'tcx, N> {
 363     pub closure_def_id: DefId,
 364     pub substs: ty::ClosureSubsts<'tcx>,
 365     /// Nested obligations. This can be non-empty if the generator
 366     /// signature contains associated types.
 367     pub nested: Vec<N>
 368 }
 369
 370 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable)]
 371 pub struct VtableClosureData<'tcx, N> {
 372     pub closure_def_id: DefId,
 373     pub substs: ty::ClosureSubsts<'tcx>,
 374     /// Nested obligations. This can be non-empty if the closure
 375     /// signature contains associated types.
 376     pub nested: Vec<N>
 377 }
 378
 379 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable)]
 380 pub struct VtableAutoImplData<N> {
 381     pub trait_def_id: DefId,
 382     pub nested: Vec<N>
 383 }
 384
 385 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable)]
 386 pub struct VtableBuiltinData<N> {
 387     pub nested: Vec<N>
 388 }
 389
 390 /// A vtable for some object-safe trait `Foo` automatically derived
 391 /// for the object type `Foo`.
 392 #[derive(PartialEq, Eq, Clone, RustcEncodable, RustcDecodable)]
 393 pub struct VtableObjectData<'tcx, N> {
 394     /// `Foo` upcast to the obligation trait. This will be some supertrait of `Foo`.
 395     pub upcast_trait_ref: ty::PolyTraitRef<'tcx>,
 396
 397     /// The vtable is formed by concatenating together the method lists of
 398     /// the base object trait and all supertraits; this is the start of
 399     /// `upcast_trait_ref`'s methods in that vtable.
 400     pub vtable_base: usize,
 401
 402     pub nested: Vec<N>,
 403 }
 404
 405 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable)]
 406 pub struct VtableFnPointerData<'tcx, N> {
 407     pub fn_ty: Ty<'tcx>,
 408     pub nested: Vec<N>
 409 }
 410
 411 /// Creates predicate obligations from the generic bounds.
 412 pub fn predicates_for_generics<'tcx>(cause: ObligationCause<'tcx>,
 413                                      param_env: ty::ParamEnv<'tcx>,
 414                                      generic_bounds: &ty::InstantiatedPredicates<'tcx>)
 415                                      -> PredicateObligations<'tcx>
 416 {
 417     util::predicates_for_generics(cause, 0, param_env, generic_bounds)
 418 }
 419
 420 /// Determines whether the type `ty` is known to meet `bound` and
 421 /// returns true if so. Returns false if `ty` either does not meet
 422 /// `bound` or is not known to meet bound (note that this is
 423 /// conservative towards *no impl*, which is the opposite of the
 424 /// `evaluate` methods).
 425 pub fn type_known_to_meet_bound<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
 426                                                 param_env: ty::ParamEnv<'tcx>,
 427                                                 ty: Ty<'tcx>,
 428                                                 def_id: DefId,
 429                                                 span: Span)
 430 -> bool
 431 {
 432     debug!("type_known_to_meet_bound(ty={:?}, bound={:?})",
 433            ty,
 434            infcx.tcx.item_path_str(def_id));
 435
 436     let trait_ref = ty::TraitRef {
 437         def_id,
 438         substs: infcx.tcx.mk_substs_trait(ty, &[]),
 439     };
 440     let obligation = Obligation {
 441         param_env,
 442         cause: ObligationCause::misc(span, ast::DUMMY_NODE_ID),
 443         recursion_depth: 0,
 444         predicate: trait_ref.to_predicate(),
 445     };
 446
 447     let result = SelectionContext::new(infcx)
 448         .evaluate_obligation_conservatively(&obligation);
 449     debug!("type_known_to_meet_ty={:?} bound={} => {:?}",
 450            ty, infcx.tcx.item_path_str(def_id), result);
 451
 452     if result && (ty.has_infer_types() || ty.has_closure_types()) {
 453         // Because of inference "guessing", selection can sometimes claim
 454         // to succeed while the success requires a guess. To ensure
 455         // this function's result remains infallible, we must confirm
 456         // that guess. While imperfect, I believe this is sound.
 457
 458         // The handling of regions in this area of the code is terrible,
 459         // see issue #29149. We should be able to improve on this with
 460         // NLL.
 461         let mut fulfill_cx = FulfillmentContext::new_ignoring_regions();
 462
 463         // We can use a dummy node-id here because we won't pay any mind
 464         // to region obligations that arise (there shouldn't really be any
 465         // anyhow).
 466         let cause = ObligationCause::misc(span, ast::DUMMY_NODE_ID);
 467
 468         fulfill_cx.register_bound(infcx, param_env, ty, def_id, cause);
 469
 470         // Note: we only assume something is `Copy` if we can
 471         // *definitively* show that it implements `Copy`. Otherwise,
 472         // assume it is move; linear is always ok.
 473         match fulfill_cx.select_all_or_error(infcx) {
 474             Ok(()) => {
 475                 debug!("type_known_to_meet_bound: ty={:?} bound={} success",
 476                        ty,
 477                        infcx.tcx.item_path_str(def_id));
 478                 true
 479             }
 480             Err(e) => {
 481                 debug!("type_known_to_meet_bound: ty={:?} bound={} errors={:?}",
 482                        ty,
 483                        infcx.tcx.item_path_str(def_id),
 484                        e);
 485                 false
 486             }
 487         }
 488     } else {
 489         result
 490     }
 491 }
 492
 493 // FIXME: this is gonna need to be removed ...
 494 /// Normalizes the parameter environment, reporting errors if they occur.
 495 pub fn normalize_param_env_or_error<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 496                                               region_context: DefId,
 497                                               unnormalized_env: ty::ParamEnv<'tcx>,
 498                                               cause: ObligationCause<'tcx>)
 499                                               -> ty::ParamEnv<'tcx>
 500 {
 501     // I'm not wild about reporting errors here; I'd prefer to
 502     // have the errors get reported at a defined place (e.g.,
 503     // during typeck). Instead I have all parameter
 504     // environments, in effect, going through this function
 505     // and hence potentially reporting errors. This ensurse of
 506     // course that we never forget to normalize (the
 507     // alternative seemed like it would involve a lot of
 508     // manual invocations of this fn -- and then we'd have to
 509     // deal with the errors at each of those sites).
 510     //
 511     // In any case, in practice, typeck constructs all the
 512     // parameter environments once for every fn as it goes,
 513     // and errors will get reported then; so after typeck we
 514     // can be sure that no errors should occur.
 515
 516     let span = cause.span;
 517
 518     debug!("normalize_param_env_or_error(unnormalized_env={:?})",
 519            unnormalized_env);
 520
 521     let predicates: Vec<_> =
 522         util::elaborate_predicates(tcx, unnormalized_env.caller_bounds.to_vec())
 523         .filter(|p| !p.is_global()) // (*)
 524         .collect();
 525
 526     // (*) Any predicate like `i32: Trait<u32>` or whatever doesn't
 527     // need to be in the *environment* to be proven, so screen those
 528     // out. This is important for the soundness of inter-fn
 529     // caching. Note though that we should probably check that these
 530     // predicates hold at the point where the environment is
 531     // constructed, but I am not currently doing so out of laziness.
 532     // -nmatsakis
 533
 534     debug!("normalize_param_env_or_error: elaborated-predicates={:?}",
 535            predicates);
 536
 537     let elaborated_env = ty::ParamEnv::new(tcx.intern_predicates(&predicates),
 538                                            unnormalized_env.reveal);
 539
 540     tcx.infer_ctxt().enter(|infcx| {
 541         // FIXME. We should really... do something with these region
 542         // obligations. But this call just continues the older
 543         // behavior (i.e., doesn't cause any new bugs), and it would
 544         // take some further refactoring to actually solve them. In
 545         // particular, we would have to handle implied bounds
 546         // properly, and that code is currently largely confined to
 547         // regionck (though I made some efforts to extract it
 548         // out). -nmatsakis
 549         //
 550         // @arielby: In any case, these obligations are checked
 551         // by wfcheck anyway, so I'm not sure we have to check
 552         // them here too, and we will remove this function when
 553         // we move over to lazy normalization *anyway*.
 554         let fulfill_cx = FulfillmentContext::new_ignoring_regions();
 555
 556         let predicates = match fully_normalize_with_fulfillcx(
 557             &infcx,
 558             fulfill_cx,
 559             cause,
 560             elaborated_env,
 561             // You would really want to pass infcx.param_env.caller_bounds here,
 562             // but that is an interned slice, and fully_normalize takes &T and returns T, so
 563             // without further refactoring, a slice can't be used. Luckily, we still have the
 564             // predicate vector from which we created the ParamEnv in infcx, so we
 565             // can pass that instead. It's roundabout and a bit brittle, but this code path
 566             // ought to be refactored anyway, and until then it saves us from having to copy.
 567             &predicates,
 568         ) {
 569             Ok(predicates) => predicates,
 570             Err(errors) => {
 571                 infcx.report_fulfillment_errors(&errors, None);
 572                 // An unnormalized env is better than nothing.
 573                 return elaborated_env;
 574             }
 575         };
 576
 577         debug!("normalize_param_env_or_error: normalized predicates={:?}",
 578             predicates);
 579
 580         let region_scope_tree = region::ScopeTree::default();
 581
 582         // We can use the `elaborated_env` here; the region code only
 583         // cares about declarations like `'a: 'b`.
 584         let outlives_env = OutlivesEnvironment::new(elaborated_env);
 585
 586         infcx.resolve_regions_and_report_errors(region_context, &region_scope_tree, &outlives_env);
 587
 588         let predicates = match infcx.fully_resolve(&predicates) {
 589             Ok(predicates) => predicates,
 590             Err(fixup_err) => {
 591                 // If we encounter a fixup error, it means that some type
 592                 // variable wound up unconstrained. I actually don't know
 593                 // if this can happen, and I certainly don't expect it to
 594                 // happen often, but if it did happen it probably
 595                 // represents a legitimate failure due to some kind of
 596                 // unconstrained variable, and it seems better not to ICE,
 597                 // all things considered.
 598                 tcx.sess.span_err(span, &fixup_err.to_string());
 599                 // An unnormalized env is better than nothing.
 600                 return elaborated_env;
 601             }
 602         };
 603
 604         let predicates = match tcx.lift_to_global(&predicates) {
 605             Some(predicates) => predicates,
 606             None => return elaborated_env,
 607         };
 608
 609         debug!("normalize_param_env_or_error: resolved predicates={:?}",
 610                predicates);
 611
 612         ty::ParamEnv::new(tcx.intern_predicates(&predicates), unnormalized_env.reveal)
 613     })
 614 }
 615
 616 pub fn fully_normalize<'a, 'gcx, 'tcx, T>(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
 617                                           cause: ObligationCause<'tcx>,
 618                                           param_env: ty::ParamEnv<'tcx>,
 619                                           value: &T)
 620                                           -> Result<T, Vec<FulfillmentError<'tcx>>>
 621     where T : TypeFoldable<'tcx>
 622 {
 623     // FIXME (@jroesch) ISSUE 26721
 624     // I'm not sure if this is a bug or not, needs further investigation.
 625     // It appears that by reusing the fulfillment_cx here we incur more
 626     // obligations and later trip an assertion on regionck.rs line 337.
 627     //
 628     // The two possibilities I see is:
 629     //      - normalization is not actually fully happening and we
 630     //        have a bug else where
 631     //      - we are adding a duplicate bound into the list causing
 632     //        its size to change.
 633     //
 634     // I think we should probably land this refactor and then come
 635     // back to this is a follow-up patch.
 636     let fulfillcx = FulfillmentContext::new();
 637     fully_normalize_with_fulfillcx(infcx, fulfillcx, cause, param_env, value)
 638 }
 639
 640 pub fn fully_normalize_with_fulfillcx<'a, 'gcx, 'tcx, T>(
 641     infcx: &InferCtxt<'a, 'gcx, 'tcx>,
 642     mut fulfill_cx: FulfillmentContext<'tcx>,
 643     cause: ObligationCause<'tcx>,
 644     param_env: ty::ParamEnv<'tcx>,
 645     value: &T)
 646     -> Result<T, Vec<FulfillmentError<'tcx>>>
 647     where T : TypeFoldable<'tcx>
 648 {
 649     debug!("fully_normalize_with_fulfillcx(value={:?})", value);
 650     let selcx = &mut SelectionContext::new(infcx);
 651     let Normalized { value: normalized_value, obligations } =
 652         project::normalize(selcx, param_env, cause, value);
 653     debug!("fully_normalize: normalized_value={:?} obligations={:?}",
 654            normalized_value,
 655            obligations);
 656     for obligation in obligations {
 657         fulfill_cx.register_predicate_obligation(selcx.infcx(), obligation);
 658     }
 659
 660     debug!("fully_normalize: select_all_or_error start");
 661     match fulfill_cx.select_all_or_error(infcx) {
 662         Ok(()) => { }
 663         Err(e) => {
 664             debug!("fully_normalize: error={:?}", e);
 665             return Err(e);
 666         }
 667     }
 668     debug!("fully_normalize: select_all_or_error complete");
 669     let resolved_value = infcx.resolve_type_vars_if_possible(&normalized_value);
 670     debug!("fully_normalize: resolved_value={:?}", resolved_value);
 671     Ok(resolved_value)
 672 }
 673
 674 /// Normalizes the predicates and checks whether they hold in an empty
 675 /// environment. If this returns false, then either normalize
 676 /// encountered an error or one of the predicates did not hold. Used
 677 /// when creating vtables to check for unsatisfiable methods.
 678 fn normalize_and_test_predicates<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 679                                            predicates: Vec<ty::Predicate<'tcx>>)
 680                                            -> bool
 681 {
 682     debug!("normalize_and_test_predicates(predicates={:?})",
 683            predicates);
 684
 685     let result = tcx.infer_ctxt().enter(|infcx| {
 686         let param_env = ty::ParamEnv::empty(Reveal::All);
 687         let mut selcx = SelectionContext::new(&infcx);
 688         let mut fulfill_cx = FulfillmentContext::new();
 689         let cause = ObligationCause::dummy();
 690         let Normalized { value: predicates, obligations } =
 691             normalize(&mut selcx, param_env, cause.clone(), &predicates);
 692         for obligation in obligations {
 693             fulfill_cx.register_predicate_obligation(&infcx, obligation);
 694         }
 695         for predicate in predicates {
 696             let obligation = Obligation::new(cause.clone(), param_env, predicate);
 697             fulfill_cx.register_predicate_obligation(&infcx, obligation);
 698         }
 699
 700         fulfill_cx.select_all_or_error(&infcx).is_ok()
 701     });
 702     debug!("normalize_and_test_predicates(predicates={:?}) = {:?}",
 703            predicates, result);
 704     result
 705 }
 706
 707 fn substitute_normalize_and_test_predicates<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 708                                                       key: (DefId, &'tcx Substs<'tcx>))
 709                                                       -> bool
 710 {
 711     use ty::subst::Subst;
 712     debug!("substitute_normalize_and_test_predicates(key={:?})",
 713            key);
 714
 715     let predicates = tcx.predicates_of(key.0).predicates.subst(tcx, key.1);
 716     let result = normalize_and_test_predicates(tcx, predicates);
 717
 718     debug!("substitute_normalize_and_test_predicates(key={:?}) = {:?}",
 719            key, result);
 720     result
 721 }
 722
 723 /// Given a trait `trait_ref`, iterates the vtable entries
 724 /// that come from `trait_ref`, including its supertraits.
 725 #[inline] // FIXME(#35870) Avoid closures being unexported due to impl Trait.
 726 fn vtable_methods<'a, 'tcx>(
 727     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 728     trait_ref: ty::PolyTraitRef<'tcx>)
 729     -> Rc<Vec<Option<(DefId, &'tcx Substs<'tcx>)>>>
 730 {
 731     debug!("vtable_methods({:?})", trait_ref);
 732
 733     Rc::new(
 734         supertraits(tcx, trait_ref).flat_map(move |trait_ref| {
 735             let trait_methods = tcx.associated_items(trait_ref.def_id())
 736                 .filter(|item| item.kind == ty::AssociatedKind::Method);
 737
 738             // Now list each method's DefId and Substs (for within its trait).
 739             // If the method can never be called from this object, produce None.
 740             trait_methods.map(move |trait_method| {
 741                 debug!("vtable_methods: trait_method={:?}", trait_method);
 742                 let def_id = trait_method.def_id;
 743
 744                 // Some methods cannot be called on an object; skip those.
 745                 if !tcx.is_vtable_safe_method(trait_ref.def_id(), &trait_method) {
 746                     debug!("vtable_methods: not vtable safe");
 747                     return None;
 748                 }
 749
 750                 // the method may have some early-bound lifetimes, add
 751                 // regions for those
 752                 let substs = Substs::for_item(tcx, def_id,
 753                                               |_, _| tcx.types.re_erased,
 754                                               |def, _| trait_ref.substs().type_for_def(def));
 755
 756                 // the trait type may have higher-ranked lifetimes in it;
 757                 // so erase them if they appear, so that we get the type
 758                 // at some particular call site
 759                 let substs = tcx.erase_late_bound_regions_and_normalize(&ty::Binder(substs));
 760
 761                 // It's possible that the method relies on where clauses that
 762                 // do not hold for this particular set of type parameters.
 763                 // Note that this method could then never be called, so we
 764                 // do not want to try and trans it, in that case (see #23435).
 765                 let predicates = tcx.predicates_of(def_id).instantiate_own(tcx, substs);
 766                 if !normalize_and_test_predicates(tcx, predicates.predicates) {
 767                     debug!("vtable_methods: predicates do not hold");
 768                     return None;
 769                 }
 770
 771                 Some((def_id, substs))
 772             })
 773         }).collect()
 774     )
 775 }
 776
 777 impl<'tcx,O> Obligation<'tcx,O> {
 778     pub fn new(cause: ObligationCause<'tcx>,
 779                param_env: ty::ParamEnv<'tcx>,
 780                predicate: O)
 781                -> Obligation<'tcx, O>
 782     {
 783         Obligation { cause, param_env, recursion_depth: 0, predicate }
 784     }
 785
 786     fn with_depth(cause: ObligationCause<'tcx>,
 787                   recursion_depth: usize,
 788                   param_env: ty::ParamEnv<'tcx>,
 789                   predicate: O)
 790                   -> Obligation<'tcx, O>
 791     {
 792         Obligation { cause, param_env, recursion_depth, predicate }
 793     }
 794
 795     pub fn misc(span: Span,
 796                 body_id: ast::NodeId,
 797                 param_env: ty::ParamEnv<'tcx>,
 798                 trait_ref: O)
 799                 -> Obligation<'tcx, O> {
 800         Obligation::new(ObligationCause::misc(span, body_id), param_env, trait_ref)
 801     }
 802
 803     pub fn with<P>(&self, value: P) -> Obligation<'tcx,P> {
 804         Obligation { cause: self.cause.clone(),
 805                      param_env: self.param_env,
 806                      recursion_depth: self.recursion_depth,
 807                      predicate: value }
 808     }
 809 }
 810
 811 impl<'tcx> ObligationCause<'tcx> {
 812     pub fn new(span: Span,
 813                body_id: ast::NodeId,
 814                code: ObligationCauseCode<'tcx>)
 815                -> ObligationCause<'tcx> {
 816         ObligationCause { span: span, body_id: body_id, code: code }
 817     }
 818
 819     pub fn misc(span: Span, body_id: ast::NodeId) -> ObligationCause<'tcx> {
 820         ObligationCause { span: span, body_id: body_id, code: MiscObligation }
 821     }
 822
 823     pub fn dummy() -> ObligationCause<'tcx> {
 824         ObligationCause { span: DUMMY_SP, body_id: ast::CRATE_NODE_ID, code: MiscObligation }
 825     }
 826 }
 827
 828 impl<'tcx, N> Vtable<'tcx, N> {
 829     pub fn nested_obligations(self) -> Vec<N> {
 830         match self {
 831             VtableImpl(i) => i.nested,
 832             VtableParam(n) => n,
 833             VtableBuiltin(i) => i.nested,
 834             VtableAutoImpl(d) => d.nested,
 835             VtableClosure(c) => c.nested,
 836             VtableGenerator(c) => c.nested,
 837             VtableObject(d) => d.nested,
 838             VtableFnPointer(d) => d.nested,
 839         }
 840     }
 841
 842     fn nested_obligations_mut(&mut self) -> &mut Vec<N> {
 843         match self {
 844             &mut VtableImpl(ref mut i) => &mut i.nested,
 845             &mut VtableParam(ref mut n) => n,
 846             &mut VtableBuiltin(ref mut i) => &mut i.nested,
 847             &mut VtableAutoImpl(ref mut d) => &mut d.nested,
 848             &mut VtableGenerator(ref mut c) => &mut c.nested,
 849             &mut VtableClosure(ref mut c) => &mut c.nested,
 850             &mut VtableObject(ref mut d) => &mut d.nested,
 851             &mut VtableFnPointer(ref mut d) => &mut d.nested,
 852         }
 853     }
 854
 855     pub fn map<M, F>(self, f: F) -> Vtable<'tcx, M> where F: FnMut(N) -> M {
 856         match self {
 857             VtableImpl(i) => VtableImpl(VtableImplData {
 858                 impl_def_id: i.impl_def_id,
 859                 substs: i.substs,
 860                 nested: i.nested.into_iter().map(f).collect(),
 861             }),
 862             VtableParam(n) => VtableParam(n.into_iter().map(f).collect()),
 863             VtableBuiltin(i) => VtableBuiltin(VtableBuiltinData {
 864                 nested: i.nested.into_iter().map(f).collect(),
 865             }),
 866             VtableObject(o) => VtableObject(VtableObjectData {
 867                 upcast_trait_ref: o.upcast_trait_ref,
 868                 vtable_base: o.vtable_base,
 869                 nested: o.nested.into_iter().map(f).collect(),
 870             }),
 871             VtableAutoImpl(d) => VtableAutoImpl(VtableAutoImplData {
 872                 trait_def_id: d.trait_def_id,
 873                 nested: d.nested.into_iter().map(f).collect(),
 874             }),
 875             VtableFnPointer(p) => VtableFnPointer(VtableFnPointerData {
 876                 fn_ty: p.fn_ty,
 877                 nested: p.nested.into_iter().map(f).collect(),
 878             }),
 879             VtableGenerator(c) => VtableGenerator(VtableGeneratorData {
 880                 closure_def_id: c.closure_def_id,
 881                 substs: c.substs,
 882                 nested: c.nested.into_iter().map(f).collect(),
 883             }),
 884             VtableClosure(c) => VtableClosure(VtableClosureData {
 885                 closure_def_id: c.closure_def_id,
 886                 substs: c.substs,
 887                 nested: c.nested.into_iter().map(f).collect(),
 888             })
 889         }
 890     }
 891 }
 892
 893 impl<'tcx> FulfillmentError<'tcx> {
 894     fn new(obligation: PredicateObligation<'tcx>,
 895            code: FulfillmentErrorCode<'tcx>)
 896            -> FulfillmentError<'tcx>
 897     {
 898         FulfillmentError { obligation: obligation, code: code }
 899     }
 900 }
 901
 902 impl<'tcx> TraitObligation<'tcx> {
 903     fn self_ty(&self) -> ty::Binder<Ty<'tcx>> {
 904         ty::Binder(self.predicate.skip_binder().self_ty())
 905     }
 906 }
 907
 908 pub fn provide(providers: &mut ty::maps::Providers) {
 909     *providers = ty::maps::Providers {
 910         is_object_safe: object_safety::is_object_safe_provider,
 911         specialization_graph_of: specialize::specialization_graph_provider,
 912         specializes: specialize::specializes,
 913         trans_fulfill_obligation: trans::trans_fulfill_obligation,
 914         vtable_methods,
 915         substitute_normalize_and_test_predicates,
 916         ..*providers
 917     };
 918 }