src/librustc/middle/traits/select.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 //! See `doc.rs` for high-level documentation
  12 #![allow(dead_code)] // FIXME -- just temporarily
  13
  14 pub use self::MethodMatchResult::*;
  15 pub use self::MethodMatchedData::*;
  16 use self::Candidate::*;
  17 use self::BuiltinBoundConditions::*;
  18 use self::EvaluationResult::*;
  19
  20 use super::{Obligation, ObligationCause};
  21 use super::{SelectionError, Unimplemented, Overflow,
  22             OutputTypeParameterMismatch};
  23 use super::{Selection};
  24 use super::{SelectionResult};
  25 use super::{VtableBuiltin, VtableImpl, VtableParam, VtableUnboxedClosure, VtableFnPointer};
  26 use super::{VtableImplData, VtableParamData, VtableBuiltinData};
  27 use super::{util};
  28
  29 use middle::fast_reject;
  30 use middle::mem_categorization::Typer;
  31 use middle::subst::{Subst, Substs, VecPerParamSpace};
  32 use middle::ty::{mod, Ty};
  33 use middle::infer;
  34 use middle::infer::{InferCtxt, TypeSkolemizer};
  35 use middle::ty_fold::TypeFoldable;
  36 use std::cell::RefCell;
  37 use std::collections::hash_map::HashMap;
  38 use std::rc::Rc;
  39 use syntax::{abi, ast};
  40 use util::common::ErrorReported;
  41 use util::ppaux::Repr;
  42
  43 pub struct SelectionContext<'cx, 'tcx:'cx> {
  44     infcx: &'cx InferCtxt<'cx, 'tcx>,
  45     param_env: &'cx ty::ParameterEnvironment<'tcx>,
  46     typer: &'cx (Typer<'tcx>+'cx),
  47
  48     /// Skolemizer used specifically for skolemizing entries on the
  49     /// obligation stack. This ensures that all entries on the stack
  50     /// at one time will have the same set of skolemized entries,
  51     /// which is important for checking for trait bounds that
  52     /// recursively require themselves.
  53     skolemizer: TypeSkolemizer<'cx, 'tcx>,
  54
  55     /// If true, indicates that the evaluation should be conservative
  56     /// and consider the possibility of types outside this crate.
  57     /// This comes up primarily when resolving ambiguity. Imagine
  58     /// there is some trait reference `$0 : Bar` where `$0` is an
  59     /// inference variable. If `intercrate` is true, then we can never
  60     /// say for sure that this reference is not implemented, even if
  61     /// there are *no impls at all for `Bar`*, because `$0` could be
  62     /// bound to some type that in a downstream crate that implements
  63     /// `Bar`. This is the suitable mode for coherence. Elsewhere,
  64     /// though, we set this to false, because we are only interested
  65     /// in types that the user could actually have written --- in
  66     /// other words, we consider `$0 : Bar` to be unimplemented if
  67     /// there is no type that the user could *actually name* that
  68     /// would satisfy it. This avoids crippling inference, basically.
  69     intercrate: bool,
  70 }
  71
  72 // A stack that walks back up the stack frame.
  73 struct ObligationStack<'prev, 'tcx: 'prev> {
  74     obligation: &'prev Obligation<'tcx>,
  75
  76     /// Trait ref from `obligation` but skolemized with the
  77     /// selection-context's skolemizer. Used to check for recursion.
  78     skol_trait_ref: Rc<ty::TraitRef<'tcx>>,
  79
  80     previous: Option<&'prev ObligationStack<'prev, 'tcx>>
  81 }
  82
  83 pub struct SelectionCache<'tcx> {
  84     hashmap: RefCell<HashMap<Rc<ty::TraitRef<'tcx>>,
  85                              SelectionResult<'tcx, Candidate<'tcx>>>>,
  86 }
  87
  88 pub enum MethodMatchResult {
  89     MethodMatched(MethodMatchedData),
  90     MethodAmbiguous(/* list of impls that could apply */ Vec<ast::DefId>),
  91     MethodDidNotMatch,
  92 }
  93
  94 #[deriving(Show)]
  95 pub enum MethodMatchedData {
  96     // In the case of a precise match, we don't really need to store
  97     // how the match was found. So don't.
  98     PreciseMethodMatch,
  99
 100     // In the case of a coercion, we need to know the precise impl so
 101     // that we can determine the type to which things were coerced.
 102     CoerciveMethodMatch(/* impl we matched */ ast::DefId)
 103 }
 104
 105 /// The selection process begins by considering all impls, where
 106 /// clauses, and so forth that might resolve an obligation.  Sometimes
 107 /// we'll be able to say definitively that (e.g.) an impl does not
 108 /// apply to the obligation: perhaps it is defined for `uint` but the
 109 /// obligation is for `int`. In that case, we drop the impl out of the
 110 /// list.  But the other cases are considered *candidates*.
 111 ///
 112 /// Candidates can either be definitive or ambiguous. An ambiguous
 113 /// candidate is one that might match or might not, depending on how
 114 /// type variables wind up being resolved. This only occurs during inference.
 115 ///
 116 /// For selection to succeed, there must be exactly one non-ambiguous
 117 /// candidate.  Usually, it is not possible to have more than one
 118 /// definitive candidate, due to the coherence rules. However, there is
 119 /// one case where it could occur: if there is a blanket impl for a
 120 /// trait (that is, an impl applied to all T), and a type parameter
 121 /// with a where clause. In that case, we can have a candidate from the
 122 /// where clause and a second candidate from the impl. This is not a
 123 /// problem because coherence guarantees us that the impl which would
 124 /// be used to satisfy the where clause is the same one that we see
 125 /// now. To resolve this issue, therefore, we ignore impls if we find a
 126 /// matching where clause. Part of the reason for this is that where
 127 /// clauses can give additional information (like, the types of output
 128 /// parameters) that would have to be inferred from the impl.
 129 #[deriving(PartialEq,Eq,Show,Clone)]
 130 enum Candidate<'tcx> {
 131     BuiltinCandidate(ty::BuiltinBound),
 132     ParamCandidate(VtableParamData<'tcx>),
 133     ImplCandidate(ast::DefId),
 134
 135     /// Implementation of a `Fn`-family trait by one of the
 136     /// anonymous types generated for a `||` expression.
 137     UnboxedClosureCandidate(/* closure */ ast::DefId, Substs<'tcx>),
 138
 139     /// Implementation of a `Fn`-family trait by one of the anonymous
 140     /// types generated for a fn pointer type (e.g., `fn(int)->int`)
 141     FnPointerCandidate,
 142
 143     ErrorCandidate,
 144 }
 145
 146 struct CandidateSet<'tcx> {
 147     vec: Vec<Candidate<'tcx>>,
 148     ambiguous: bool
 149 }
 150
 151 enum BuiltinBoundConditions<'tcx> {
 152     If(Vec<Ty<'tcx>>),
 153     ParameterBuiltin,
 154     AmbiguousBuiltin
 155 }
 156
 157 #[deriving(Show)]
 158 enum EvaluationResult {
 159     EvaluatedToOk,
 160     EvaluatedToErr,
 161     EvaluatedToAmbig,
 162 }
 163
 164 impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 165     pub fn new(infcx: &'cx InferCtxt<'cx, 'tcx>,
 166                param_env: &'cx ty::ParameterEnvironment<'tcx>,
 167                typer: &'cx Typer<'tcx>)
 168                -> SelectionContext<'cx, 'tcx> {
 169         SelectionContext {
 170             infcx: infcx,
 171             param_env: param_env,
 172             typer: typer,
 173             skolemizer: infcx.skolemizer(),
 174             intercrate: false,
 175         }
 176     }
 177
 178     pub fn intercrate(infcx: &'cx InferCtxt<'cx, 'tcx>,
 179                       param_env: &'cx ty::ParameterEnvironment<'tcx>,
 180                       typer: &'cx Typer<'tcx>)
 181                       -> SelectionContext<'cx, 'tcx> {
 182         SelectionContext {
 183             infcx: infcx,
 184             param_env: param_env,
 185             typer: typer,
 186             skolemizer: infcx.skolemizer(),
 187             intercrate: true,
 188         }
 189     }
 190
 191     pub fn tcx(&self) -> &'cx ty::ctxt<'tcx> {
 192         self.infcx.tcx
 193     }
 194
 195     ///////////////////////////////////////////////////////////////////////////
 196     // Selection
 197     //
 198     // The selection phase tries to identify *how* an obligation will
 199     // be resolved. For example, it will identify which impl or
 200     // parameter bound is to be used. The process can be inconclusive
 201     // if the self type in the obligation is not fully inferred. Selection
 202     // can result in an error in one of two ways:
 203     //
 204     // 1. If no applicable impl or parameter bound can be found.
 205     // 2. If the output type parameters in the obligation do not match
 206     //    those specified by the impl/bound. For example, if the obligation
 207     //    is `Vec<Foo>:Iterable<Bar>`, but the impl specifies
 208     //    `impl<T> Iterable<T> for Vec<T>`, than an error would result.
 209
 210     /// Evaluates whether the obligation can be satisfied. Returns an indication of whether the
 211     /// obligation can be satisfied and, if so, by what means. Never affects surrounding typing
 212     /// environment.
 213     pub fn select(&mut self, obligation: &Obligation<'tcx>)
 214                   -> SelectionResult<'tcx, Selection<'tcx>> {
 215         debug!("select({})", obligation.repr(self.tcx()));
 216         assert!(!obligation.trait_ref.has_escaping_regions());
 217
 218         let stack = self.push_stack(None, obligation);
 219         match try!(self.candidate_from_obligation(&stack)) {
 220             None => Ok(None),
 221             Some(candidate) => Ok(Some(try!(self.confirm_candidate(obligation, candidate)))),
 222         }
 223     }
 224
 225     pub fn select_inherent_impl(&mut self,
 226                                 impl_def_id: ast::DefId,
 227                                 obligation_cause: ObligationCause<'tcx>,
 228                                 obligation_self_ty: Ty<'tcx>)
 229                                 -> SelectionResult<'tcx, VtableImplData<'tcx, Obligation<'tcx>>>
 230     {
 231         debug!("select_inherent_impl(impl_def_id={}, obligation_self_ty={})",
 232                impl_def_id.repr(self.tcx()),
 233                obligation_self_ty.repr(self.tcx()));
 234
 235         match self.match_inherent_impl(impl_def_id,
 236                                        obligation_cause,
 237                                        obligation_self_ty) {
 238             Ok(substs) => {
 239                 let vtable_impl = self.vtable_impl(impl_def_id, substs, obligation_cause, 0);
 240                 Ok(Some(vtable_impl))
 241             }
 242             Err(()) => {
 243                 Err(Unimplemented)
 244             }
 245         }
 246     }
 247
 248     ///////////////////////////////////////////////////////////////////////////
 249     // EVALUATION
 250     //
 251     // Tests whether an obligation can be selected or whether an impl
 252     // can be applied to particular types. It skips the "confirmation"
 253     // step and hence completely ignores output type parameters.
 254     //
 255     // The result is "true" if the obligation *may* hold and "false" if
 256     // we can be sure it does not.
 257
 258     /// Evaluates whether the obligation `obligation` can be satisfied (by any means).
 259     pub fn evaluate_obligation(&mut self,
 260                                obligation: &Obligation<'tcx>)
 261                                -> bool
 262     {
 263         debug!("evaluate_obligation({})",
 264                obligation.repr(self.tcx()));
 265         assert!(!obligation.trait_ref.has_escaping_regions());
 266
 267         let stack = self.push_stack(None, obligation);
 268         self.evaluate_stack(&stack).may_apply()
 269     }
 270
 271     fn evaluate_builtin_bound_recursively<'o>(&mut self,
 272                                               bound: ty::BuiltinBound,
 273                                               previous_stack: &ObligationStack<'o, 'tcx>,
 274                                               ty: Ty<'tcx>)
 275                                               -> EvaluationResult
 276     {
 277         let obligation =
 278             util::obligation_for_builtin_bound(
 279                 self.tcx(),
 280                 previous_stack.obligation.cause,
 281                 bound,
 282                 previous_stack.obligation.recursion_depth + 1,
 283                 ty);
 284
 285         match obligation {
 286             Ok(obligation) => {
 287                 self.evaluate_obligation_recursively(Some(previous_stack), &obligation)
 288             }
 289             Err(ErrorReported) => {
 290                 EvaluatedToOk
 291             }
 292         }
 293     }
 294
 295     fn evaluate_obligation_recursively<'o>(&mut self,
 296                                            previous_stack: Option<&ObligationStack<'o, 'tcx>>,
 297                                            obligation: &Obligation<'tcx>)
 298                                            -> EvaluationResult
 299     {
 300         debug!("evaluate_obligation_recursively({})",
 301                obligation.repr(self.tcx()));
 302
 303         let stack = self.push_stack(previous_stack.map(|x| x), obligation);
 304
 305         let result = self.evaluate_stack(&stack);
 306
 307         debug!("result: {}", result);
 308         result
 309     }
 310
 311     fn evaluate_stack<'o>(&mut self,
 312                           stack: &ObligationStack<'o, 'tcx>)
 313                           -> EvaluationResult
 314     {
 315         // In intercrate mode, whenever any of the types are unbound,
 316         // there can always be an impl. Even if there are no impls in
 317         // this crate, perhaps the type would be unified with
 318         // something from another crate that does provide an impl.
 319         //
 320         // In intracrate mode, we must still be conservative. The reason is
 321         // that we want to avoid cycles. Imagine an impl like:
 322         //
 323         //     impl<T:Eq> Eq for Vec<T>
 324         //
 325         // and a trait reference like `$0 : Eq` where `$0` is an
 326         // unbound variable. When we evaluate this trait-reference, we
 327         // will unify `$0` with `Vec<$1>` (for some fresh variable
 328         // `$1`), on the condition that `$1 : Eq`. We will then wind
 329         // up with many candidates (since that are other `Eq` impls
 330         // that apply) and try to winnow things down. This results in
 331         // a recurssive evaluation that `$1 : Eq` -- as you can
 332         // imagine, this is just where we started. To avoid that, we
 333         // check for unbound variables and return an ambiguous (hence possible)
 334         // match if we've seen this trait before.
 335         //
 336         // This suffices to allow chains like `FnMut` implemented in
 337         // terms of `Fn` etc, but we could probably make this more
 338         // precise still.
 339         let input_types = stack.skol_trait_ref.input_types();
 340         let unbound_input_types = input_types.iter().any(|&t| ty::type_is_skolemized(t));
 341         if
 342             unbound_input_types &&
 343              (self.intercrate ||
 344               stack.iter().skip(1).any(
 345                   |prev| stack.skol_trait_ref.def_id == prev.skol_trait_ref.def_id))
 346         {
 347             debug!("evaluate_stack_intracrate({}) --> unbound argument, recursion -->  ambiguous",
 348                    stack.skol_trait_ref.repr(self.tcx()));
 349             return EvaluatedToAmbig;
 350         }
 351
 352         // If there is any previous entry on the stack that precisely
 353         // matches this obligation, then we can assume that the
 354         // obligation is satisfied for now (still all other conditions
 355         // must be met of course). One obvious case this comes up is
 356         // marker traits like `Send`. Think of a linked list:
 357         //
 358         //    struct List<T> { data: T, next: Option<Box<List<T>>> {
 359         //
 360         // `Box<List<T>>` will be `Send` if `T` is `Send` and
 361         // `Option<Box<List<T>>>` is `Send`, and in turn
 362         // `Option<Box<List<T>>>` is `Send` if `Box<List<T>>` is
 363         // `Send`.
 364         //
 365         // Note that we do this comparison using the `skol_trait_ref`
 366         // fields. Because these have all been skolemized using
 367         // `self.skolemizer`, we can be sure that (a) this will not
 368         // affect the inferencer state and (b) that if we see two
 369         // skolemized types with the same index, they refer to the
 370         // same unbound type variable.
 371         if
 372             stack.iter()
 373             .skip(1) // skip top-most frame
 374             .any(|prev| stack.skol_trait_ref == prev.skol_trait_ref)
 375         {
 376             debug!("evaluate_stack_intracrate({}) --> recursive",
 377                    stack.skol_trait_ref.repr(self.tcx()));
 378             return EvaluatedToOk;
 379         }
 380
 381         match self.candidate_from_obligation(stack) {
 382             Ok(Some(c)) => self.winnow_candidate(stack, &c),
 383             Ok(None) => EvaluatedToAmbig,
 384             Err(_) => EvaluatedToErr,
 385         }
 386     }
 387
 388     /// Evaluates whether the impl with id `impl_def_id` could be applied to the self type
 389     /// `obligation_self_ty`. This can be used either for trait or inherent impls.
 390     pub fn evaluate_impl(&mut self,
 391                          impl_def_id: ast::DefId,
 392                          obligation: &Obligation<'tcx>)
 393                          -> bool
 394     {
 395         debug!("evaluate_impl(impl_def_id={}, obligation={})",
 396                impl_def_id.repr(self.tcx()),
 397                obligation.repr(self.tcx()));
 398
 399         self.infcx.probe(|| {
 400             match self.match_impl(impl_def_id, obligation) {
 401                 Ok(substs) => {
 402                     let vtable_impl = self.vtable_impl(impl_def_id,
 403                                                        substs,
 404                                                        obligation.cause,
 405                                                        obligation.recursion_depth + 1);
 406                     self.winnow_selection(None, VtableImpl(vtable_impl)).may_apply()
 407                 }
 408                 Err(()) => {
 409                     false
 410                 }
 411             }
 412         })
 413     }
 414
 415     ///////////////////////////////////////////////////////////////////////////
 416     // METHOD MATCHING
 417     //
 418     // Method matching is a variation on the normal select/evaluation
 419     // situation.  In this scenario, rather than having a full trait
 420     // reference to select from, we start with an expression like
 421     // `receiver.method(...)`. This means that we have `rcvr_ty`, the
 422     // type of the receiver, and we have a possible trait that
 423     // supplies `method`. We must determine whether the receiver is
 424     // applicable, taking into account the transformed self type
 425     // declared on `method`. We also must consider the possibility
 426     // that `receiver` can be *coerced* into a suitable type (for
 427     // example, a receiver type like `&(Any+Send)` might be coerced
 428     // into a receiver like `&Any` to allow for method dispatch).  See
 429     // the body of `evaluate_method_obligation()` for more details on
 430     // the algorithm.
 431
 432     /// Determine whether a trait-method is applicable to a receiver of
 433     /// type `rcvr_ty`. *Does not affect the inference state.*
 434     ///
 435     /// - `rcvr_ty` -- type of the receiver
 436     /// - `xform_self_ty` -- transformed self type declared on the method, with `Self`
 437     ///   to a fresh type variable
 438     /// - `obligation` -- a reference to the trait where the method is declared, with
 439     ///   the input types on the trait replaced with fresh type variables
 440     pub fn evaluate_method_obligation(&mut self,
 441                                       rcvr_ty: Ty<'tcx>,
 442                                       xform_self_ty: Ty<'tcx>,
 443                                       obligation: &Obligation<'tcx>)
 444                                       -> MethodMatchResult
 445     {
 446         // Here is the situation. We have a trait method declared (say) like so:
 447         //
 448         //     trait TheTrait {
 449         //         fn the_method(self: Rc<Self>, ...) { ... }
 450         //     }
 451         //
 452         // And then we have a call looking (say) like this:
 453         //
 454         //     let x: Rc<Foo> = ...;
 455         //     x.the_method()
 456         //
 457         // Now we want to decide if `TheTrait` is applicable. As a
 458         // human, we can see that `TheTrait` is applicable if there is
 459         // an impl for the type `Foo`. But how does the compiler know
 460         // what impl to look for, given that our receiver has type
 461         // `Rc<Foo>`? We need to take the method's self type into
 462         // account.
 463         //
 464         // On entry to this function, we have the following inputs:
 465         //
 466         // - `rcvr_ty = Rc<Foo>`
 467         // - `xform_self_ty = Rc<$0>`
 468         // - `obligation = $0 as TheTrait`
 469         //
 470         // We do the match in two phases. The first is a *precise
 471         // match*, which means that no coercion is required. This is
 472         // the preferred way to match. It works by first making
 473         // `rcvr_ty` a subtype of `xform_self_ty`. This unifies `$0`
 474         // and `Foo`. We can then evaluate (roughly as normal) the
 475         // trait reference `Foo as TheTrait`.
 476         //
 477         // If this fails, we fallback to a coercive match, described below.
 478
 479         match self.infcx.probe(|| self.match_method_precise(rcvr_ty, xform_self_ty, obligation)) {
 480             Ok(()) => { return MethodMatched(PreciseMethodMatch); }
 481             Err(_) => { }
 482         }
 483
 484         // Coercive matches work slightly differently and cannot
 485         // completely reuse the normal trait matching machinery
 486         // (though they employ many of the same bits and pieces). To
 487         // see how it works, let's continue with our previous example,
 488         // but with the following declarations:
 489         //
 490         // ```
 491         // trait Foo : Bar { .. }
 492         // trait Bar : Baz { ... }
 493         // trait Baz { ... }
 494         // impl TheTrait for Bar {
 495         //     fn the_method(self: Rc<Bar>, ...) { ... }
 496         // }
 497         // ```
 498         //
 499         // Now we see that the receiver type `Rc<Foo>` is actually an
 500         // object type. And in fact the impl we want is an impl on the
 501         // supertrait `Rc<Bar>`.  The precise matching procedure won't
 502         // find it, however, because `Rc<Foo>` is not a subtype of
 503         // `Rc<Bar>` -- it is *coercible* to `Rc<Bar>` (actually, such
 504         // coercions are not yet implemented, but let's leave that
 505         // aside for now).
 506         //
 507         // To handle this case, we employ a different procedure. Recall
 508         // that our initial state is as follows:
 509         //
 510         // - `rcvr_ty = Rc<Foo>`
 511         // - `xform_self_ty = Rc<$0>`
 512         // - `obligation = $0 as TheTrait`
 513         //
 514         // We now go through each impl and instantiate all of its type
 515         // variables, yielding the trait reference that the impl
 516         // provides. In our example, the impl would provide `Bar as
 517         // TheTrait`.  Next we (try to) unify the trait reference that
 518         // the impl provides with the input obligation. This would
 519         // unify `$0` and `Bar`. Now we can see whether the receiver
 520         // type (`Rc<Foo>`) is *coercible to* the transformed self
 521         // type (`Rc<$0> == Rc<Bar>`). In this case, the answer is
 522         // yes, so the impl is considered a candidate.
 523         //
 524         // Note that there is the possibility of ambiguity here, even
 525         // when all types are known. In our example, this might occur
 526         // if there was *also* an impl of `TheTrait` for `Baz`. In
 527         // this case, `Rc<Foo>` would be coercible to both `Rc<Bar>`
 528         // and `Rc<Baz>`. (Note that it is not a *coherence violation*
 529         // to have impls for both `Bar` and `Baz`, despite this
 530         // ambiguity).  In this case, we report an error, listing all
 531         // the applicable impls.  The user can explicitly "up-coerce"
 532         // to the type they want.
 533         //
 534         // Note that this coercion step only considers actual impls
 535         // found in the source. This is because all the
 536         // compiler-provided impls (such as those for unboxed
 537         // closures) do not have relevant coercions. This simplifies
 538         // life immensely.
 539
 540         let mut impls =
 541             self.assemble_method_candidates_from_impls(rcvr_ty, xform_self_ty, obligation);
 542
 543         if impls.len() > 1 {
 544             impls.retain(|&c| self.winnow_method_impl(c, rcvr_ty, xform_self_ty, obligation));
 545         }
 546
 547         if impls.len() > 1 {
 548             return MethodAmbiguous(impls);
 549         }
 550
 551         match impls.pop() {
 552             Some(def_id) => MethodMatched(CoerciveMethodMatch(def_id)),
 553             None => MethodDidNotMatch
 554         }
 555     }
 556
 557     /// Given the successful result of a method match, this function "confirms" the result, which
 558     /// basically repeats the various matching operations, but outside of any snapshot so that
 559     /// their effects are committed into the inference state.
 560     pub fn confirm_method_match(&mut self,
 561                                 rcvr_ty: Ty<'tcx>,
 562                                 xform_self_ty: Ty<'tcx>,
 563                                 obligation: &Obligation<'tcx>,
 564                                 data: MethodMatchedData)
 565     {
 566         let is_ok = match data {
 567             PreciseMethodMatch => {
 568                 self.match_method_precise(rcvr_ty, xform_self_ty, obligation).is_ok()
 569             }
 570
 571             CoerciveMethodMatch(impl_def_id) => {
 572                 self.match_method_coerce(impl_def_id, rcvr_ty, xform_self_ty, obligation).is_ok()
 573             }
 574         };
 575
 576         if !is_ok {
 577             self.tcx().sess.span_bug(
 578                 obligation.cause.span,
 579                 format!("match not repeatable: {}, {}, {}, {}",
 580                         rcvr_ty.repr(self.tcx()),
 581                         xform_self_ty.repr(self.tcx()),
 582                         obligation.repr(self.tcx()),
 583                         data)[]);
 584         }
 585     }
 586
 587     /// Implements the *precise method match* procedure described in
 588     /// `evaluate_method_obligation()`.
 589     fn match_method_precise(&mut self,
 590                             rcvr_ty: Ty<'tcx>,
 591                             xform_self_ty: Ty<'tcx>,
 592                             obligation: &Obligation<'tcx>)
 593                             -> Result<(),()>
 594     {
 595         self.infcx.commit_if_ok(|| {
 596             match self.infcx.sub_types(false, infer::RelateSelfType(obligation.cause.span),
 597                                        rcvr_ty, xform_self_ty) {
 598                 Ok(()) => { }
 599                 Err(_) => { return Err(()); }
 600             }
 601
 602             if self.evaluate_obligation(obligation) {
 603                 Ok(())
 604             } else {
 605                 Err(())
 606             }
 607         })
 608     }
 609
 610     /// Assembles a list of potentially applicable impls using the *coercive match* procedure
 611     /// described in `evaluate_method_obligation()`.
 612     fn assemble_method_candidates_from_impls(&mut self,
 613                                              rcvr_ty: Ty<'tcx>,
 614                                              xform_self_ty: Ty<'tcx>,
 615                                              obligation: &Obligation<'tcx>)
 616                                              -> Vec<ast::DefId>
 617     {
 618         let mut candidates = Vec::new();
 619
 620         let all_impls = self.all_impls(obligation.trait_ref.def_id);
 621         for &impl_def_id in all_impls.iter() {
 622             self.infcx.probe(|| {
 623                 match self.match_method_coerce(impl_def_id, rcvr_ty, xform_self_ty, obligation) {
 624                     Ok(_) => { candidates.push(impl_def_id); }
 625                     Err(_) => { }
 626                 }
 627             });
 628         }
 629
 630         candidates
 631     }
 632
 633     /// Applies the *coercive match* procedure described in `evaluate_method_obligation()` to a
 634     /// particular impl.
 635     fn match_method_coerce(&mut self,
 636                            impl_def_id: ast::DefId,
 637                            rcvr_ty: Ty<'tcx>,
 638                            xform_self_ty: Ty<'tcx>,
 639                            obligation: &Obligation<'tcx>)
 640                            -> Result<Substs<'tcx>, ()>
 641     {
 642         // This is almost always expected to succeed. It
 643         // causes the impl's self-type etc to be unified with
 644         // the type variable that is shared between
 645         // obligation/xform_self_ty. In our example, after
 646         // this is done, the type of `xform_self_ty` would
 647         // change from `Rc<$0>` to `Rc<Foo>` (because $0 is
 648         // unified with `Foo`).
 649         let substs = try!(self.match_impl(impl_def_id, obligation));
 650
 651         // Next, check whether we can coerce. For now we require
 652         // that the coercion be a no-op.
 653         let origin = infer::Misc(obligation.cause.span);
 654         match infer::mk_coercety(self.infcx, true, origin,
 655                                  rcvr_ty, xform_self_ty) {
 656             Ok(None) => { /* Fallthrough */ }
 657             Ok(Some(_)) | Err(_) => { return Err(()); }
 658         }
 659
 660         Ok(substs)
 661     }
 662
 663     /// A version of `winnow_impl` applicable to coerice method matching.  This is basically the
 664     /// same as `winnow_impl` but it uses the method matching procedure and is specific to impls.
 665     fn winnow_method_impl(&mut self,
 666                           impl_def_id: ast::DefId,
 667                           rcvr_ty: Ty<'tcx>,
 668                           xform_self_ty: Ty<'tcx>,
 669                           obligation: &Obligation<'tcx>)
 670                           -> bool
 671     {
 672         debug!("winnow_method_impl: impl_def_id={} rcvr_ty={} xform_self_ty={} obligation={}",
 673                impl_def_id.repr(self.tcx()),
 674                rcvr_ty.repr(self.tcx()),
 675                xform_self_ty.repr(self.tcx()),
 676                obligation.repr(self.tcx()));
 677
 678         self.infcx.probe(|| {
 679             match self.match_method_coerce(impl_def_id, rcvr_ty, xform_self_ty, obligation) {
 680                 Ok(substs) => {
 681                     let vtable_impl = self.vtable_impl(impl_def_id,
 682                                                        substs,
 683                                                        obligation.cause,
 684                                                        obligation.recursion_depth + 1);
 685                     self.winnow_selection(None, VtableImpl(vtable_impl)).may_apply()
 686                 }
 687                 Err(()) => {
 688                     false
 689                 }
 690             }
 691         })
 692     }
 693
 694     ///////////////////////////////////////////////////////////////////////////
 695     // CANDIDATE ASSEMBLY
 696     //
 697     // The selection process begins by examining all in-scope impls,
 698     // caller obligations, and so forth and assembling a list of
 699     // candidates. See `doc.rs` and the `Candidate` type for more details.
 700
 701     fn candidate_from_obligation<'o>(&mut self,
 702                                      stack: &ObligationStack<'o, 'tcx>)
 703                                      -> SelectionResult<'tcx, Candidate<'tcx>>
 704     {
 705         // Watch out for overflow. This intentionally bypasses (and does
 706         // not update) the cache.
 707         let recursion_limit = self.infcx.tcx.sess.recursion_limit.get();
 708         if stack.obligation.recursion_depth >= recursion_limit {
 709             debug!("{} --> overflow (limit={})",
 710                    stack.obligation.repr(self.tcx()),
 711                    recursion_limit);
 712             return Err(Overflow)
 713         }
 714
 715         // Check the cache. Note that we skolemize the trait-ref
 716         // separately rather than using `stack.skol_trait_ref` -- this
 717         // is because we want the unbound variables to be replaced
 718         // with fresh skolemized types starting from index 0.
 719         let cache_skol_trait_ref =
 720             self.infcx.skolemize(stack.obligation.trait_ref.clone());
 721         debug!("candidate_from_obligation(cache_skol_trait_ref={}, obligation={})",
 722                cache_skol_trait_ref.repr(self.tcx()),
 723                stack.repr(self.tcx()));
 724         assert!(!stack.obligation.trait_ref.has_escaping_regions());
 725
 726         match self.check_candidate_cache(cache_skol_trait_ref.clone()) {
 727             Some(c) => {
 728                 debug!("CACHE HIT: cache_skol_trait_ref={}, candidate={}",
 729                        cache_skol_trait_ref.repr(self.tcx()),
 730                        c.repr(self.tcx()));
 731                 return c;
 732             }
 733             None => { }
 734         }
 735
 736         // If no match, compute result and insert into cache.
 737         let candidate = self.candidate_from_obligation_no_cache(stack);
 738         debug!("CACHE MISS: cache_skol_trait_ref={}, candidate={}",
 739                cache_skol_trait_ref.repr(self.tcx()), candidate.repr(self.tcx()));
 740         self.insert_candidate_cache(cache_skol_trait_ref, candidate.clone());
 741         candidate
 742     }
 743
 744     fn candidate_from_obligation_no_cache<'o>(&mut self,
 745                                               stack: &ObligationStack<'o, 'tcx>)
 746                                               -> SelectionResult<'tcx, Candidate<'tcx>>
 747     {
 748         if ty::type_is_error(stack.obligation.self_ty()) {
 749             return Ok(Some(ErrorCandidate));
 750         }
 751
 752         let candidate_set = try!(self.assemble_candidates(stack));
 753
 754         if candidate_set.ambiguous {
 755             debug!("candidate set contains ambig");
 756             return Ok(None);
 757         }
 758
 759         let mut candidates = candidate_set.vec;
 760
 761         debug!("assembled {} candidates for {}",
 762                candidates.len(), stack.repr(self.tcx()));
 763
 764         // At this point, we know that each of the entries in the
 765         // candidate set is *individually* applicable. Now we have to
 766         // figure out if they contain mutual incompatibilities. This
 767         // frequently arises if we have an unconstrained input type --
 768         // for example, we are looking for $0:Eq where $0 is some
 769         // unconstrained type variable. In that case, we'll get a
 770         // candidate which assumes $0 == int, one that assumes $0 ==
 771         // uint, etc. This spells an ambiguity.
 772
 773         // If there is more than one candidate, first winnow them down
 774         // by considering extra conditions (nested obligations and so
 775         // forth). We don't winnow if there is exactly one
 776         // candidate. This is a relatively minor distinction but it
 777         // can lead to better inference and error-reporting. An
 778         // example would be if there was an impl:
 779         //
 780         //     impl<T:Clone> Vec<T> { fn push_clone(...) { ... } }
 781         //
 782         // and we were to see some code `foo.push_clone()` where `boo`
 783         // is a `Vec<Bar>` and `Bar` does not implement `Clone`.  If
 784         // we were to winnow, we'd wind up with zero candidates.
 785         // Instead, we select the right impl now but report `Bar does
 786         // not implement Clone`.
 787         if candidates.len() > 1 {
 788             candidates.retain(|c| self.winnow_candidate(stack, c).may_apply())
 789         }
 790
 791         // If there are STILL multiple candidate, we can further reduce
 792         // the list by dropping duplicates.
 793         if candidates.len() > 1 {
 794             let mut i = 0;
 795             while i < candidates.len() {
 796                 let is_dup =
 797                     range(0, candidates.len())
 798                     .filter(|&j| i != j)
 799                     .any(|j| self.candidate_should_be_dropped_in_favor_of(stack,
 800                                                                           &candidates[i],
 801                                                                           &candidates[j]));
 802                 if is_dup {
 803                     debug!("Dropping candidate #{}/{}: {}",
 804                            i, candidates.len(), candidates[i].repr(self.tcx()));
 805                     candidates.swap_remove(i);
 806                 } else {
 807                     debug!("Retaining candidate #{}/{}: {}",
 808                            i, candidates.len(), candidates[i].repr(self.tcx()));
 809                     i += 1;
 810                 }
 811             }
 812         }
 813
 814         // If there are *STILL* multiple candidates, give up and
 815         // report ambiguiuty.
 816         if candidates.len() > 1 {
 817             debug!("multiple matches, ambig");
 818             return Ok(None);
 819         }
 820
 821         // If there are *NO* candidates, that there are no impls --
 822         // that we know of, anyway. Note that in the case where there
 823         // are unbound type variables within the obligation, it might
 824         // be the case that you could still satisfy the obligation
 825         // from another crate by instantiating the type variables with
 826         // a type from another crate that does have an impl. This case
 827         // is checked for in `evaluate_stack` (and hence users
 828         // who might care about this case, like coherence, should use
 829         // that function).
 830         if candidates.len() == 0 {
 831             return Err(Unimplemented);
 832         }
 833
 834         // Just one candidate left.
 835         let candidate = candidates.pop().unwrap();
 836         Ok(Some(candidate))
 837     }
 838
 839     fn pick_candidate_cache(&self,
 840                             cache_skol_trait_ref: &Rc<ty::TraitRef<'tcx>>)
 841                             -> &SelectionCache<'tcx>
 842     {
 843         // High-level idea: we have to decide whether to consult the
 844         // cache that is specific to this scope, or to consult the
 845         // global cache. We want the cache that is specific to this
 846         // scope whenever where clauses might affect the result.
 847
 848         // Avoid using the master cache during coherence and just rely
 849         // on the local cache. This effectively disables caching
 850         // during coherence. It is really just a simplification to
 851         // avoid us having to fear that coherence results "pollute"
 852         // the master cache. Since coherence executes pretty quickly,
 853         // it's not worth going to more trouble to increase the
 854         // hit-rate I don't think.
 855         if self.intercrate {
 856             return &self.param_env.selection_cache;
 857         }
 858
 859         // If the trait refers to any parameters in scope, then use
 860         // the cache of the param-environment.
 861         if
 862             cache_skol_trait_ref.input_types().iter().any(
 863                 |&t| ty::type_has_self(t) || ty::type_has_params(t))
 864         {
 865             return &self.param_env.selection_cache;
 866         }
 867
 868         // If the trait refers to unbound type variables, and there
 869         // are where clauses in scope, then use the local environment.
 870         // If there are no where clauses in scope, which is a very
 871         // common case, then we can use the global environment.
 872         // See the discussion in doc.rs for more details.
 873         if
 874             !self.param_env.caller_obligations.is_empty()
 875             &&
 876             cache_skol_trait_ref.input_types().iter().any(
 877                 |&t| ty::type_has_ty_infer(t))
 878         {
 879             return &self.param_env.selection_cache;
 880         }
 881
 882         // Otherwise, we can use the global cache.
 883         &self.tcx().selection_cache
 884     }
 885
 886     fn check_candidate_cache(&mut self,
 887                              cache_skol_trait_ref: Rc<ty::TraitRef<'tcx>>)
 888                              -> Option<SelectionResult<'tcx, Candidate<'tcx>>>
 889     {
 890         let cache = self.pick_candidate_cache(&cache_skol_trait_ref);
 891         let hashmap = cache.hashmap.borrow();
 892         hashmap.get(&cache_skol_trait_ref).map(|c| (*c).clone())
 893     }
 894
 895     fn insert_candidate_cache(&mut self,
 896                               cache_skol_trait_ref: Rc<ty::TraitRef<'tcx>>,
 897                               candidate: SelectionResult<'tcx, Candidate<'tcx>>)
 898     {
 899         let cache = self.pick_candidate_cache(&cache_skol_trait_ref);
 900         let mut hashmap = cache.hashmap.borrow_mut();
 901         hashmap.insert(cache_skol_trait_ref, candidate);
 902     }
 903
 904     fn assemble_candidates<'o>(&mut self,
 905                                stack: &ObligationStack<'o, 'tcx>)
 906                                -> Result<CandidateSet<'tcx>, SelectionError<'tcx>>
 907     {
 908         // Check for overflow.
 909
 910         let ObligationStack { obligation, .. } = *stack;
 911
 912         let mut candidates = CandidateSet {
 913             vec: Vec::new(),
 914             ambiguous: false
 915         };
 916
 917         // Other bounds. Consider both in-scope bounds from fn decl
 918         // and applicable impls. There is a certain set of precedence rules here.
 919
 920         match self.tcx().lang_items.to_builtin_kind(obligation.trait_ref.def_id) {
 921             Some(bound) => {
 922                 try!(self.assemble_builtin_bound_candidates(bound, stack, &mut candidates));
 923             }
 924
 925             None => {
 926                 // For the time being, we ignore user-defined impls for builtin-bounds.
 927                 // (And unboxed candidates only apply to the Fn/FnMut/etc traits.)
 928                 try!(self.assemble_unboxed_closure_candidates(obligation, &mut candidates));
 929                 try!(self.assemble_fn_pointer_candidates(obligation, &mut candidates));
 930                 try!(self.assemble_candidates_from_impls(obligation, &mut candidates));
 931             }
 932         }
 933
 934         try!(self.assemble_candidates_from_caller_bounds(obligation, &mut candidates));
 935         Ok(candidates)
 936     }
 937
 938     /// Given an obligation like `<SomeTrait for T>`, search the obligations that the caller
 939     /// supplied to find out whether it is listed among them.
 940     ///
 941     /// Never affects inference environment.
 942     fn assemble_candidates_from_caller_bounds(&mut self,
 943                                               obligation: &Obligation<'tcx>,
 944                                               candidates: &mut CandidateSet<'tcx>)
 945                                               -> Result<(),SelectionError<'tcx>>
 946     {
 947         debug!("assemble_candidates_from_caller_bounds({})",
 948                obligation.repr(self.tcx()));
 949
 950         let caller_trait_refs: Vec<Rc<ty::TraitRef>> =
 951             self.param_env.caller_obligations.iter()
 952             .map(|o| o.trait_ref.clone())
 953             .collect();
 954
 955         let all_bounds =
 956             util::transitive_bounds(
 957                 self.tcx(), caller_trait_refs.as_slice());
 958
 959         let matching_bounds =
 960             all_bounds.filter(
 961                 |bound| self.infcx.probe(
 962                     || self.match_trait_refs(obligation,
 963                                              (*bound).clone())).is_ok());
 964
 965         let param_candidates =
 966             matching_bounds.map(
 967                 |bound| ParamCandidate(VtableParamData { bound: bound }));
 968
 969         candidates.vec.extend(param_candidates);
 970
 971         Ok(())
 972     }
 973
 974     /// Check for the artificial impl that the compiler will create for an obligation like `X :
 975     /// FnMut<..>` where `X` is an unboxed closure type.
 976     ///
 977     /// Note: the type parameters on an unboxed closure candidate are modeled as *output* type
 978     /// parameters and hence do not affect whether this trait is a match or not. They will be
 979     /// unified during the confirmation step.
 980     fn assemble_unboxed_closure_candidates(&mut self,
 981                                            obligation: &Obligation<'tcx>,
 982                                            candidates: &mut CandidateSet<'tcx>)
 983                                            -> Result<(),SelectionError<'tcx>>
 984     {
 985         let kind = match self.fn_family_trait_kind(obligation.trait_ref.def_id) {
 986             Some(k) => k,
 987             None => { return Ok(()); }
 988         };
 989
 990         let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
 991         let (closure_def_id, substs) = match self_ty.sty {
 992             ty::ty_unboxed_closure(id, _, ref substs) => (id, substs.clone()),
 993             ty::ty_infer(ty::TyVar(_)) => {
 994                 candidates.ambiguous = true;
 995                 return Ok(());
 996             }
 997             _ => { return Ok(()); }
 998         };
 999
1000         debug!("assemble_unboxed_candidates: self_ty={} obligation={}",
1001                self_ty.repr(self.tcx()),
1002                obligation.repr(self.tcx()));
1003
1004         let closure_kind = match self.typer.unboxed_closures().borrow().get(&closure_def_id) {
1005             Some(closure) => closure.kind,
1006             None => {
1007                 self.tcx().sess.span_bug(
1008                     obligation.cause.span,
1009                     format!("No entry for unboxed closure: {}",
1010                             closure_def_id.repr(self.tcx())).as_slice());
1011             }
1012         };
1013
1014         if closure_kind == kind {
1015             candidates.vec.push(UnboxedClosureCandidate(closure_def_id, substs.clone()));
1016         }
1017
1018         Ok(())
1019     }
1020
1021     /// Implement one of the `Fn()` family for a fn pointer.
1022     fn assemble_fn_pointer_candidates(&mut self,
1023                                       obligation: &Obligation<'tcx>,
1024                                       candidates: &mut CandidateSet<'tcx>)
1025                                       -> Result<(),SelectionError<'tcx>>
1026     {
1027         // We provide a `Fn` impl for fn pointers. There is no need to provide
1028         // the other traits (e.g. `FnMut`) since those are provided by blanket
1029         // impls.
1030         if Some(obligation.trait_ref.def_id) != self.tcx().lang_items.fn_trait() {
1031             return Ok(());
1032         }
1033
1034         let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
1035         match self_ty.sty {
1036             ty::ty_infer(..) => {
1037                 candidates.ambiguous = true; // could wind up being a fn() type
1038             }
1039
1040             // provide an impl, but only for suitable `fn` pointers
1041             ty::ty_bare_fn(ty::BareFnTy {
1042                 fn_style: ast::NormalFn,
1043                 abi: abi::Rust,
1044                 sig: ty::FnSig {
1045                     inputs: _,
1046                     output: ty::FnConverging(_),
1047                     variadic: false
1048                 }
1049             }) => {
1050                 candidates.vec.push(FnPointerCandidate);
1051             }
1052
1053             _ => { }
1054         }
1055
1056         Ok(())
1057     }
1058
1059     /// Search for impls that might apply to `obligation`.
1060     fn assemble_candidates_from_impls(&mut self,
1061                                       obligation: &Obligation<'tcx>,
1062                                       candidates: &mut CandidateSet<'tcx>)
1063                                       -> Result<(), SelectionError<'tcx>>
1064     {
1065         let all_impls = self.all_impls(obligation.trait_ref.def_id);
1066         for &impl_def_id in all_impls.iter() {
1067             self.infcx.probe(|| {
1068                 match self.match_impl(impl_def_id, obligation) {
1069                     Ok(_) => {
1070                         candidates.vec.push(ImplCandidate(impl_def_id));
1071                     }
1072                     Err(()) => { }
1073                 }
1074             });
1075         }
1076         Ok(())
1077     }
1078
1079     ///////////////////////////////////////////////////////////////////////////
1080     // WINNOW
1081     //
1082     // Winnowing is the process of attempting to resolve ambiguity by
1083     // probing further. During the winnowing process, we unify all
1084     // type variables (ignoring skolemization) and then we also
1085     // attempt to evaluate recursive bounds to see if they are
1086     // satisfied.
1087
1088     /// Further evaluate `candidate` to decide whether all type parameters match and whether nested
1089     /// obligations are met. Returns true if `candidate` remains viable after this further
1090     /// scrutiny.
1091     fn winnow_candidate<'o>(&mut self,
1092                             stack: &ObligationStack<'o, 'tcx>,
1093                             candidate: &Candidate<'tcx>)
1094                             -> EvaluationResult
1095     {
1096         debug!("winnow_candidate: candidate={}", candidate.repr(self.tcx()));
1097         self.infcx.probe(|| {
1098             let candidate = (*candidate).clone();
1099             match self.confirm_candidate(stack.obligation, candidate) {
1100                 Ok(selection) => self.winnow_selection(Some(stack), selection),
1101                 Err(_) => EvaluatedToErr,
1102             }
1103         })
1104     }
1105
1106     fn winnow_selection<'o>(&mut self,
1107                             stack: Option<&ObligationStack<'o, 'tcx>>,
1108                             selection: Selection<'tcx>)
1109                             -> EvaluationResult
1110     {
1111         let mut result = EvaluatedToOk;
1112         for obligation in selection.iter_nested() {
1113             match self.evaluate_obligation_recursively(stack, obligation) {
1114                 EvaluatedToErr => { return EvaluatedToErr; }
1115                 EvaluatedToAmbig => { result = EvaluatedToAmbig; }
1116                 EvaluatedToOk => { }
1117             }
1118         }
1119         result
1120     }
1121
1122     /// Returns true if `candidate_i` should be dropped in favor of `candidate_j`.
1123     ///
1124     /// This is generally true if either:
1125     /// - candidate i and candidate j are equivalent; or,
1126     /// - candidate i is a conrete impl and candidate j is a where clause bound,
1127     ///   and the concrete impl is applicable to the types in the where clause bound.
1128     ///
1129     /// The last case refers to cases where there are blanket impls (often conditional
1130     /// blanket impls) as well as a where clause. This can come down to one of two cases:
1131     ///
1132     /// - The impl is truly unconditional (it has no where clauses
1133     ///   of its own), in which case the where clause is
1134     ///   unnecessary, because coherence requires that we would
1135     ///   pick that particular impl anyhow (at least so long as we
1136     ///   don't have specialization).
1137     ///
1138     /// - The impl is conditional, in which case we may not have winnowed it out
1139     ///   because we don't know if the conditions apply, but the where clause is basically
1140     ///   telling us taht there is some impl, though not necessarily the one we see.
1141     ///
1142     /// In both cases we prefer to take the where clause, which is
1143     /// essentially harmless.  See issue #18453 for more details of
1144     /// a case where doing the opposite caused us harm.
1145     fn candidate_should_be_dropped_in_favor_of<'o>(&mut self,
1146                                                    stack: &ObligationStack<'o, 'tcx>,
1147                                                    candidate_i: &Candidate<'tcx>,
1148                                                    candidate_j: &Candidate<'tcx>)
1149                                                    -> bool
1150     {
1151         match (candidate_i, candidate_j) {
1152             (&ImplCandidate(impl_def_id), &ParamCandidate(ref vt)) => {
1153                 debug!("Considering whether to drop param {} in favor of impl {}",
1154                        candidate_i.repr(self.tcx()),
1155                        candidate_j.repr(self.tcx()));
1156
1157                 self.infcx.probe(|| {
1158                     let impl_substs =
1159                         self.rematch_impl(impl_def_id, stack.obligation);
1160                     let impl_trait_ref =
1161                         ty::impl_trait_ref(self.tcx(), impl_def_id).unwrap();
1162                     let impl_trait_ref =
1163                         impl_trait_ref.subst(self.tcx(), &impl_substs);
1164                     let origin =
1165                         infer::RelateOutputImplTypes(stack.obligation.cause.span);
1166                     self.infcx
1167                         .sub_trait_refs(false, origin,
1168                                         impl_trait_ref, vt.bound.clone())
1169                         .is_ok()
1170                 })
1171             }
1172             _ => {
1173                 *candidate_i == *candidate_j
1174             }
1175         }
1176     }
1177
1178     ///////////////////////////////////////////////////////////////////////////
1179     // BUILTIN BOUNDS
1180     //
1181     // These cover the traits that are built-in to the language
1182     // itself.  This includes `Copy` and `Sized` for sure. For the
1183     // moment, it also includes `Send` / `Sync` and a few others, but
1184     // those will hopefully change to library-defined traits in the
1185     // future.
1186
1187     fn assemble_builtin_bound_candidates<'o>(&mut self,
1188                                              bound: ty::BuiltinBound,
1189                                              stack: &ObligationStack<'o, 'tcx>,
1190                                              candidates: &mut CandidateSet<'tcx>)
1191                                              -> Result<(),SelectionError<'tcx>>
1192     {
1193         match self.builtin_bound(bound, stack.obligation.self_ty()) {
1194             Ok(If(_)) => {
1195                 debug!("builtin_bound: bound={}",
1196                        bound.repr(self.tcx()));
1197                 candidates.vec.push(BuiltinCandidate(bound));
1198                 Ok(())
1199             }
1200             Ok(ParameterBuiltin) => { Ok(()) }
1201             Ok(AmbiguousBuiltin) => { Ok(candidates.ambiguous = true) }
1202             Err(e) => { Err(e) }
1203         }
1204     }
1205
1206     fn builtin_bound(&mut self,
1207                      bound: ty::BuiltinBound,
1208                      self_ty: Ty<'tcx>)
1209                      -> Result<BuiltinBoundConditions<'tcx>,SelectionError<'tcx>>
1210     {
1211         let self_ty = self.infcx.shallow_resolve(self_ty);
1212         return match self_ty.sty {
1213             ty::ty_infer(ty::IntVar(_)) |
1214             ty::ty_infer(ty::FloatVar(_)) |
1215             ty::ty_uint(_) |
1216             ty::ty_int(_) |
1217             ty::ty_bool |
1218             ty::ty_float(_) |
1219             ty::ty_bare_fn(_) |
1220             ty::ty_char => {
1221                 // safe for everything
1222                 Ok(If(Vec::new()))
1223             }
1224
1225             ty::ty_uniq(referent_ty) => {  // Box<T>
1226                 match bound {
1227                     ty::BoundCopy => {
1228                         Err(Unimplemented)
1229                     }
1230
1231                     ty::BoundSized => {
1232                         Ok(If(Vec::new()))
1233                     }
1234
1235                     ty::BoundSync |
1236                     ty::BoundSend => {
1237                         Ok(If(vec![referent_ty]))
1238                     }
1239                 }
1240             }
1241
1242             ty::ty_ptr(ty::mt { ty: referent_ty, .. }) => {     // *const T, *mut T
1243                 match bound {
1244                     ty::BoundCopy |
1245                     ty::BoundSized => {
1246                         Ok(If(Vec::new()))
1247                     }
1248
1249                     ty::BoundSync |
1250                     ty::BoundSend => {
1251                         Ok(If(vec![referent_ty]))
1252                     }
1253                 }
1254             }
1255
1256             ty::ty_closure(ref c) => {
1257                 match c.store {
1258                     ty::UniqTraitStore => {
1259                         // proc: Equivalent to `Box<FnOnce>`
1260                         match bound {
1261                             ty::BoundCopy => {
1262                                 Err(Unimplemented)
1263                             }
1264
1265                             ty::BoundSized => {
1266                                 Ok(If(Vec::new()))
1267                             }
1268
1269                             ty::BoundSync |
1270                             ty::BoundSend => {
1271                                 if c.bounds.builtin_bounds.contains(&bound) {
1272                                     Ok(If(Vec::new()))
1273                                 } else {
1274                                     Err(Unimplemented)
1275                                 }
1276                             }
1277                         }
1278                     }
1279                     ty::RegionTraitStore(_, mutbl) => {
1280                         // ||: Equivalent to `&FnMut` or `&mut FnMut` or something like that.
1281                         match bound {
1282                             ty::BoundCopy => {
1283                                 match mutbl {
1284                                     ast::MutMutable => Err(Unimplemented),  // &mut T is affine
1285                                     ast::MutImmutable => Ok(If(Vec::new())),  // &T is copyable
1286                                 }
1287                             }
1288
1289                             ty::BoundSized => {
1290                                 Ok(If(Vec::new()))
1291                             }
1292
1293                             ty::BoundSync |
1294                             ty::BoundSend => {
1295                                 if c.bounds.builtin_bounds.contains(&bound) {
1296                                     Ok(If(Vec::new()))
1297                                 } else {
1298                                     Err(Unimplemented)
1299                                 }
1300                             }
1301                         }
1302                     }
1303                 }
1304             }
1305
1306             ty::ty_trait(box ty::TyTrait { ref principal, bounds }) => {
1307                 match bound {
1308                     ty::BoundSized => {
1309                         Err(Unimplemented)
1310                     }
1311                     ty::BoundCopy | ty::BoundSync | ty::BoundSend => {
1312                         if bounds.builtin_bounds.contains(&bound) {
1313                             Ok(If(Vec::new()))
1314                         } else {
1315                             // Recursively check all supertraits to find out if any further
1316                             // bounds are required and thus we must fulfill.
1317                             // We have to create a temp trait ref here since TyTraits don't
1318                             // have actual self type info (which is required for the
1319                             // supertraits iterator).
1320                             let tmp_tr = Rc::new(ty::TraitRef {
1321                                 def_id: principal.def_id,
1322                                 substs: principal.substs.with_self_ty(ty::mk_err())
1323                             });
1324                             for tr in util::supertraits(self.tcx(), tmp_tr) {
1325                                 let td = ty::lookup_trait_def(self.tcx(), tr.def_id);
1326
1327                                 if td.bounds.builtin_bounds.contains(&bound) {
1328                                     return Ok(If(Vec::new()))
1329                                 }
1330                             }
1331
1332                             Err(Unimplemented)
1333                         }
1334                     }
1335                 }
1336             }
1337
1338             ty::ty_rptr(_, ty::mt { ty: referent_ty, mutbl }) => {
1339                 // &mut T or &T
1340                 match bound {
1341                     ty::BoundCopy => {
1342                         match mutbl {
1343                             // &mut T is affine and hence never `Copy`
1344                             ast::MutMutable => Err(Unimplemented),
1345
1346                             // &T is always copyable
1347                             ast::MutImmutable => Ok(If(Vec::new())),
1348                         }
1349                     }
1350
1351                     ty::BoundSized => {
1352                         Ok(If(Vec::new()))
1353                     }
1354
1355                     ty::BoundSync |
1356                     ty::BoundSend => {
1357                         // Note: technically, a region pointer is only
1358                         // sendable if it has lifetime
1359                         // `'static`. However, we don't take regions
1360                         // into account when doing trait matching:
1361                         // instead, when we decide that `T : Send`, we
1362                         // will register a separate constraint with
1363                         // the region inferencer that `T : 'static`
1364                         // holds as well (because the trait `Send`
1365                         // requires it). This will ensure that there
1366                         // is no borrowed data in `T` (or else report
1367                         // an inference error). The reason we do it
1368                         // this way is that we do not yet *know* what
1369                         // lifetime the borrowed reference has, since
1370                         // we haven't finished running inference -- in
1371                         // other words, there's a kind of
1372                         // chicken-and-egg problem.
1373                         Ok(If(vec![referent_ty]))
1374                     }
1375                 }
1376             }
1377
1378             ty::ty_vec(element_ty, ref len) => {
1379                 // [T, ..n] and [T]
1380                 match bound {
1381                     ty::BoundCopy => {
1382                         match *len {
1383                             Some(_) => Ok(If(vec![element_ty])), // [T, ..n] is copy iff T is copy
1384                             None => Err(Unimplemented), // [T] is unsized and hence affine
1385                         }
1386                     }
1387
1388                     ty::BoundSized => {
1389                         if len.is_some() {
1390                             Ok(If(Vec::new()))
1391                         } else {
1392                             Err(Unimplemented)
1393                         }
1394                     }
1395
1396                     ty::BoundSync |
1397                     ty::BoundSend => {
1398                         Ok(If(vec![element_ty]))
1399                     }
1400                 }
1401             }
1402
1403             ty::ty_str => {
1404                 // Equivalent to [u8]
1405                 match bound {
1406                     ty::BoundSync |
1407                     ty::BoundSend => {
1408                         Ok(If(Vec::new()))
1409                     }
1410
1411                     ty::BoundCopy |
1412                     ty::BoundSized => {
1413                         Err(Unimplemented)
1414                     }
1415                 }
1416             }
1417
1418             ty::ty_tup(ref tys) => {
1419                 // (T1, ..., Tn) -- meets any bound that all of T1...Tn meet
1420                 Ok(If(tys.clone()))
1421             }
1422
1423             ty::ty_unboxed_closure(def_id, _, ref substs) => {
1424                 // FIXME -- This case is tricky. In the case of by-ref
1425                 // closures particularly, we need the results of
1426                 // inference to decide how to reflect the type of each
1427                 // upvar (the upvar may have type `T`, but the runtime
1428                 // type could be `&mut`, `&`, or just `T`). For now,
1429                 // though, we'll do this unsoundly and assume that all
1430                 // captures are by value. Really what we ought to do
1431                 // is reserve judgement and then intertwine this
1432                 // analysis with closure inference.
1433                 assert_eq!(def_id.krate, ast::LOCAL_CRATE);
1434                 match self.tcx().freevars.borrow().get(&def_id.node) {
1435                     None => {
1436                         // No upvars.
1437                         Ok(If(Vec::new()))
1438                     }
1439
1440                     Some(freevars) => {
1441                         let tys: Vec<Ty> =
1442                             freevars
1443                             .iter()
1444                             .map(|freevar| {
1445                                 let freevar_def_id = freevar.def.def_id();
1446                                 self.typer.node_ty(freevar_def_id.node)
1447                                     .unwrap_or(ty::mk_err()).subst(self.tcx(), substs)
1448                             })
1449                             .collect();
1450                         Ok(If(tys))
1451                     }
1452                 }
1453             }
1454
1455             ty::ty_struct(def_id, ref substs) => {
1456                 let types: Vec<Ty> =
1457                     ty::struct_fields(self.tcx(), def_id, substs)
1458                     .iter()
1459                     .map(|f| f.mt.ty)
1460                     .collect();
1461                 nominal(self, bound, def_id, types)
1462             }
1463
1464             ty::ty_enum(def_id, ref substs) => {
1465                 let types: Vec<Ty> =
1466                     ty::substd_enum_variants(self.tcx(), def_id, substs)
1467                     .iter()
1468                     .flat_map(|variant| variant.args.iter())
1469                     .map(|&ty| ty)
1470                     .collect();
1471                 nominal(self, bound, def_id, types)
1472             }
1473
1474             ty::ty_param(_) => {
1475                 // Note: A type parameter is only considered to meet a
1476                 // particular bound if there is a where clause telling
1477                 // us that it does, and that case is handled by
1478                 // `assemble_candidates_from_caller_bounds()`.
1479                 Ok(ParameterBuiltin)
1480             }
1481
1482             ty::ty_infer(ty::TyVar(_)) => {
1483                 // Unbound type variable. Might or might not have
1484                 // applicable impls and so forth, depending on what
1485                 // those type variables wind up being bound to.
1486                 Ok(AmbiguousBuiltin)
1487             }
1488
1489             ty::ty_err => {
1490                 Ok(If(Vec::new()))
1491             }
1492
1493             ty::ty_open(_) |
1494             ty::ty_infer(ty::SkolemizedTy(_)) |
1495             ty::ty_infer(ty::SkolemizedIntTy(_)) => {
1496                 self.tcx().sess.bug(
1497                     format!(
1498                         "asked to assemble builtin bounds of unexpected type: {}",
1499                         self_ty.repr(self.tcx())).as_slice());
1500             }
1501         };
1502
1503         fn nominal<'cx, 'tcx>(this: &mut SelectionContext<'cx, 'tcx>,
1504                               bound: ty::BuiltinBound,
1505                               def_id: ast::DefId,
1506                               types: Vec<Ty<'tcx>>)
1507                               -> Result<BuiltinBoundConditions<'tcx>,SelectionError<'tcx>>
1508         {
1509             // First check for markers and other nonsense.
1510             let tcx = this.tcx();
1511             match bound {
1512                 ty::BoundSend => {
1513                     if
1514                         Some(def_id) == tcx.lang_items.no_send_bound() ||
1515                         Some(def_id) == tcx.lang_items.managed_bound()
1516                     {
1517                         return Err(Unimplemented);
1518                     }
1519                 }
1520
1521                 ty::BoundCopy => {
1522                     if
1523                         Some(def_id) == tcx.lang_items.no_copy_bound() ||
1524                         Some(def_id) == tcx.lang_items.managed_bound() ||
1525                         ty::has_dtor(tcx, def_id)
1526                     {
1527                         return Err(Unimplemented);
1528                     }
1529                 }
1530
1531                 ty::BoundSync => {
1532                     if
1533                         Some(def_id) == tcx.lang_items.no_sync_bound() ||
1534                         Some(def_id) == tcx.lang_items.managed_bound()
1535                     {
1536                         return Err(Unimplemented);
1537                     } else if
1538                         Some(def_id) == tcx.lang_items.unsafe_type()
1539                     {
1540                         // FIXME(#13231) -- we currently consider `UnsafeCell<T>`
1541                         // to always be sync. This is allow for types like `Queue`
1542                         // and `Mutex`, where `Queue<T> : Sync` is `T : Send`.
1543                         return Ok(If(Vec::new()));
1544                     }
1545                 }
1546
1547                 ty::BoundSized => { }
1548             }
1549
1550             Ok(If(types))
1551         }
1552     }
1553
1554     ///////////////////////////////////////////////////////////////////////////
1555     // CONFIRMATION
1556     //
1557     // Confirmation unifies the output type parameters of the trait
1558     // with the values found in the obligation, possibly yielding a
1559     // type error.  See `doc.rs` for more details.
1560
1561     fn confirm_candidate(&mut self,
1562                          obligation: &Obligation<'tcx>,
1563                          candidate: Candidate<'tcx>)
1564                          -> Result<Selection<'tcx>,SelectionError<'tcx>>
1565     {
1566         debug!("confirm_candidate({}, {})",
1567                obligation.repr(self.tcx()),
1568                candidate.repr(self.tcx()));
1569
1570         match candidate {
1571             BuiltinCandidate(builtin_bound) => {
1572                 Ok(VtableBuiltin(
1573                     try!(self.confirm_builtin_candidate(obligation, builtin_bound))))
1574             }
1575
1576             ErrorCandidate => {
1577                 Ok(VtableBuiltin(VtableBuiltinData { nested: VecPerParamSpace::empty() }))
1578             }
1579
1580             ParamCandidate(param) => {
1581                 Ok(VtableParam(
1582                     try!(self.confirm_param_candidate(obligation, param))))
1583             }
1584
1585             ImplCandidate(impl_def_id) => {
1586                 let vtable_impl =
1587                     try!(self.confirm_impl_candidate(obligation, impl_def_id));
1588                 Ok(VtableImpl(vtable_impl))
1589             }
1590
1591             UnboxedClosureCandidate(closure_def_id, substs) => {
1592                 try!(self.confirm_unboxed_closure_candidate(obligation, closure_def_id, &substs));
1593                 Ok(VtableUnboxedClosure(closure_def_id, substs))
1594             }
1595
1596             FnPointerCandidate => {
1597                 let fn_type =
1598                     try!(self.confirm_fn_pointer_candidate(obligation));
1599                 Ok(VtableFnPointer(fn_type))
1600             }
1601         }
1602     }
1603
1604     fn confirm_param_candidate(&mut self,
1605                                obligation: &Obligation<'tcx>,
1606                                param: VtableParamData<'tcx>)
1607                                -> Result<VtableParamData<'tcx>,
1608                                          SelectionError<'tcx>>
1609     {
1610         debug!("confirm_param_candidate({},{})",
1611                obligation.repr(self.tcx()),
1612                param.repr(self.tcx()));
1613
1614         let () = try!(self.confirm(obligation.cause,
1615                                    obligation.trait_ref.clone(),
1616                                    param.bound.clone()));
1617         Ok(param)
1618     }
1619
1620     fn confirm_builtin_candidate(&mut self,
1621                                  obligation: &Obligation<'tcx>,
1622                                  bound: ty::BuiltinBound)
1623                                  -> Result<VtableBuiltinData<Obligation<'tcx>>,
1624                                            SelectionError<'tcx>>
1625     {
1626         debug!("confirm_builtin_candidate({})",
1627                obligation.repr(self.tcx()));
1628
1629         match try!(self.builtin_bound(bound, obligation.self_ty())) {
1630             If(nested) => Ok(self.vtable_builtin_data(obligation, bound, nested)),
1631             AmbiguousBuiltin | ParameterBuiltin => {
1632                 self.tcx().sess.span_bug(
1633                     obligation.cause.span,
1634                     format!("builtin bound for {} was ambig",
1635                             obligation.repr(self.tcx())).as_slice());
1636             }
1637         }
1638     }
1639
1640     fn vtable_builtin_data(&mut self,
1641                            obligation: &Obligation<'tcx>,
1642                            bound: ty::BuiltinBound,
1643                            nested: Vec<Ty<'tcx>>)
1644                            -> VtableBuiltinData<Obligation<'tcx>>
1645     {
1646         let obligations = nested.iter().map(|&t| {
1647             util::obligation_for_builtin_bound(
1648                 self.tcx(),
1649                 obligation.cause,
1650                 bound,
1651                 obligation.recursion_depth + 1,
1652                 t)
1653         }).collect::<Result<_, _>>();
1654         let obligations = match obligations {
1655             Ok(o) => o,
1656             Err(ErrorReported) => Vec::new()
1657         };
1658         let obligations = VecPerParamSpace::new(obligations, Vec::new(),
1659                                                 Vec::new(), Vec::new());
1660         VtableBuiltinData { nested: obligations }
1661     }
1662
1663     fn confirm_impl_candidate(&mut self,
1664                               obligation: &Obligation<'tcx>,
1665                               impl_def_id: ast::DefId)
1666                               -> Result<VtableImplData<'tcx, Obligation<'tcx>>,
1667                                         SelectionError<'tcx>>
1668     {
1669         debug!("confirm_impl_candidate({},{})",
1670                obligation.repr(self.tcx()),
1671                impl_def_id.repr(self.tcx()));
1672
1673         // First, create the substitutions by matching the impl again,
1674         // this time not in a probe.
1675         let substs = self.rematch_impl(impl_def_id, obligation);
1676         Ok(self.vtable_impl(impl_def_id, substs, obligation.cause, obligation.recursion_depth + 1))
1677     }
1678
1679     fn vtable_impl(&mut self,
1680                    impl_def_id: ast::DefId,
1681                    substs: Substs<'tcx>,
1682                    cause: ObligationCause<'tcx>,
1683                    recursion_depth: uint)
1684                    -> VtableImplData<'tcx, Obligation<'tcx>>
1685     {
1686         let impl_obligations =
1687             self.impl_obligations(cause,
1688                                   recursion_depth,
1689                                   impl_def_id,
1690                                   &substs);
1691         VtableImplData { impl_def_id: impl_def_id,
1692                          substs: substs,
1693                          nested: impl_obligations }
1694     }
1695
1696     fn confirm_fn_pointer_candidate(&mut self,
1697                                     obligation: &Obligation<'tcx>)
1698                                     -> Result<ty::Ty<'tcx>,SelectionError<'tcx>>
1699     {
1700         debug!("confirm_fn_pointer_candidate({})",
1701                obligation.repr(self.tcx()));
1702
1703         let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
1704         let sig = match self_ty.sty {
1705             ty::ty_bare_fn(ty::BareFnTy {
1706                 fn_style: ast::NormalFn,
1707                 abi: abi::Rust,
1708                 ref sig
1709             }) => {
1710                 sig
1711             }
1712             _ => {
1713                 self.tcx().sess.span_bug(
1714                     obligation.cause.span,
1715                     format!("Fn pointer candidate for inappropriate self type: {}",
1716                             self_ty.repr(self.tcx())).as_slice());
1717             }
1718         };
1719
1720         let arguments_tuple = ty::mk_tup(self.tcx(), sig.inputs.to_vec());
1721         let output_type = sig.output.unwrap();
1722         let substs =
1723             Substs::new_trait(
1724                 vec![arguments_tuple, output_type],
1725                 vec![],
1726                 vec![],
1727                 self_ty);
1728         let trait_ref = Rc::new(ty::TraitRef {
1729             def_id: obligation.trait_ref.def_id,
1730             substs: substs,
1731         });
1732
1733         let () =
1734             try!(self.confirm(obligation.cause,
1735                               obligation.trait_ref.clone(),
1736                               trait_ref));
1737
1738         Ok(self_ty)
1739     }
1740
1741     fn confirm_unboxed_closure_candidate(&mut self,
1742                                          obligation: &Obligation<'tcx>,
1743                                          closure_def_id: ast::DefId,
1744                                          substs: &Substs<'tcx>)
1745                                          -> Result<(),SelectionError<'tcx>>
1746     {
1747         debug!("confirm_unboxed_closure_candidate({},{},{})",
1748                obligation.repr(self.tcx()),
1749                closure_def_id.repr(self.tcx()),
1750                substs.repr(self.tcx()));
1751
1752         let closure_type = match self.typer.unboxed_closures().borrow().get(&closure_def_id) {
1753             Some(closure) => closure.closure_type.clone(),
1754             None => {
1755                 self.tcx().sess.span_bug(
1756                     obligation.cause.span,
1757                     format!("No entry for unboxed closure: {}",
1758                             closure_def_id.repr(self.tcx())).as_slice());
1759             }
1760         };
1761
1762         let closure_sig = &closure_type.sig;
1763         let arguments_tuple = closure_sig.inputs[0];
1764         let substs =
1765             Substs::new_trait(
1766                 vec![arguments_tuple.subst(self.tcx(), substs),
1767                      closure_sig.output.unwrap().subst(self.tcx(), substs)],
1768                 vec![],
1769                 vec![],
1770                 obligation.self_ty());
1771         let trait_ref = Rc::new(ty::TraitRef {
1772             def_id: obligation.trait_ref.def_id,
1773             substs: substs,
1774         });
1775
1776         self.confirm(obligation.cause,
1777                      obligation.trait_ref.clone(),
1778                      trait_ref)
1779     }
1780
1781     ///////////////////////////////////////////////////////////////////////////
1782     // Matching
1783     //
1784     // Matching is a common path used for both evaluation and
1785     // confirmation.  It basically unifies types that appear in impls
1786     // and traits. This does affect the surrounding environment;
1787     // therefore, when used during evaluation, match routines must be
1788     // run inside of a `probe()` so that their side-effects are
1789     // contained.
1790
1791     fn rematch_impl(&mut self,
1792                     impl_def_id: ast::DefId,
1793                     obligation: &Obligation<'tcx>)
1794                     -> Substs<'tcx>
1795     {
1796         match self.match_impl(impl_def_id, obligation) {
1797             Ok(substs) => {
1798                 substs
1799             }
1800             Err(()) => {
1801                 self.tcx().sess.bug(
1802                     format!("Impl {} was matchable against {} but now is not",
1803                             impl_def_id.repr(self.tcx()),
1804                             obligation.repr(self.tcx()))
1805                         .as_slice());
1806             }
1807         }
1808     }
1809
1810     fn match_impl(&mut self,
1811                   impl_def_id: ast::DefId,
1812                   obligation: &Obligation<'tcx>)
1813                   -> Result<Substs<'tcx>, ()>
1814     {
1815         let impl_trait_ref = ty::impl_trait_ref(self.tcx(),
1816                                                 impl_def_id).unwrap();
1817
1818         // Before we create the substitutions and everything, first
1819         // consider a "quick reject". This avoids creating more types
1820         // and so forth that we need to.
1821         if self.fast_reject_trait_refs(obligation, &*impl_trait_ref) {
1822             return Err(());
1823         }
1824
1825         let impl_substs = util::fresh_substs_for_impl(self.infcx,
1826                                                       obligation.cause.span,
1827                                                       impl_def_id);
1828
1829         let impl_trait_ref = impl_trait_ref.subst(self.tcx(),
1830                                                   &impl_substs);
1831
1832         match self.match_trait_refs(obligation, impl_trait_ref) {
1833             Ok(()) => Ok(impl_substs),
1834             Err(()) => Err(())
1835         }
1836     }
1837
1838     fn fast_reject_trait_refs(&mut self,
1839                               obligation: &Obligation,
1840                               impl_trait_ref: &ty::TraitRef)
1841                               -> bool
1842     {
1843         // We can avoid creating type variables and doing the full
1844         // substitution if we find that any of the input types, when
1845         // simplified, do not match.
1846
1847         obligation.trait_ref.input_types().iter()
1848             .zip(impl_trait_ref.input_types().iter())
1849             .any(|(&obligation_ty, &impl_ty)| {
1850                 let simplified_obligation_ty =
1851                     fast_reject::simplify_type(self.tcx(), obligation_ty, true);
1852                 let simplified_impl_ty =
1853                     fast_reject::simplify_type(self.tcx(), impl_ty, false);
1854
1855                 simplified_obligation_ty.is_some() &&
1856                     simplified_impl_ty.is_some() &&
1857                     simplified_obligation_ty != simplified_impl_ty
1858             })
1859     }
1860
1861     fn match_trait_refs(&mut self,
1862                         obligation: &Obligation<'tcx>,
1863                         trait_ref: Rc<ty::TraitRef<'tcx>>)
1864                         -> Result<(),()>
1865     {
1866         debug!("match_trait_refs: obligation={} trait_ref={}",
1867                obligation.repr(self.tcx()),
1868                trait_ref.repr(self.tcx()));
1869
1870         let origin = infer::RelateOutputImplTypes(obligation.cause.span);
1871         match self.infcx.sub_trait_refs(false,
1872                                         origin,
1873                                         trait_ref,
1874                                         obligation.trait_ref.clone()) {
1875             Ok(()) => Ok(()),
1876             Err(_) => Err(()),
1877         }
1878     }
1879
1880     /// Determines whether the self type declared against
1881     /// `impl_def_id` matches `obligation_self_ty`. If successful,
1882     /// returns the substitutions used to make them match. See
1883     /// `match_impl()`. For example, if `impl_def_id` is declared
1884     /// as:
1885     ///
1886     ///    impl<T:Copy> Foo for ~T { ... }
1887     ///
1888     /// and `obligation_self_ty` is `int`, we'd back an `Err(_)`
1889     /// result. But if `obligation_self_ty` were `~int`, we'd get
1890     /// back `Ok(T=int)`.
1891     fn match_inherent_impl(&mut self,
1892                            impl_def_id: ast::DefId,
1893                            obligation_cause: ObligationCause,
1894                            obligation_self_ty: Ty<'tcx>)
1895                            -> Result<Substs<'tcx>,()>
1896     {
1897         // Create fresh type variables for each type parameter declared
1898         // on the impl etc.
1899         let impl_substs = util::fresh_substs_for_impl(self.infcx,
1900                                                       obligation_cause.span,
1901                                                       impl_def_id);
1902
1903         // Find the self type for the impl.
1904         let impl_self_ty = ty::lookup_item_type(self.tcx(), impl_def_id).ty;
1905         let impl_self_ty = impl_self_ty.subst(self.tcx(), &impl_substs);
1906
1907         debug!("match_impl_self_types(obligation_self_ty={}, impl_self_ty={})",
1908                obligation_self_ty.repr(self.tcx()),
1909                impl_self_ty.repr(self.tcx()));
1910
1911         match self.match_self_types(obligation_cause,
1912                                     impl_self_ty,
1913                                     obligation_self_ty) {
1914             Ok(()) => {
1915                 debug!("Matched impl_substs={}", impl_substs.repr(self.tcx()));
1916                 Ok(impl_substs)
1917             }
1918             Err(()) => {
1919                 debug!("NoMatch");
1920                 Err(())
1921             }
1922         }
1923     }
1924
1925     fn match_self_types(&mut self,
1926                         cause: ObligationCause,
1927
1928                         // The self type provided by the impl/caller-obligation:
1929                         provided_self_ty: Ty<'tcx>,
1930
1931                         // The self type the obligation is for:
1932                         required_self_ty: Ty<'tcx>)
1933                         -> Result<(),()>
1934     {
1935         // FIXME(#5781) -- equating the types is stronger than
1936         // necessary. Should consider variance of trait w/r/t Self.
1937
1938         let origin = infer::RelateSelfType(cause.span);
1939         match self.infcx.eq_types(false,
1940                                   origin,
1941                                   provided_self_ty,
1942                                   required_self_ty) {
1943             Ok(()) => Ok(()),
1944             Err(_) => Err(()),
1945         }
1946     }
1947
1948     ///////////////////////////////////////////////////////////////////////////
1949     // Confirmation
1950     //
1951     // The final step of selection: once we know how an obligation is
1952     // is resolved, we confirm that selection in order to have
1953     // side-effects on the typing environment. This step also unifies
1954     // the output type parameters from the obligation with those found
1955     // on the impl/bound, which may yield type errors.
1956
1957     /// Relates the output type parameters from an impl to the
1958     /// trait.  This may lead to type errors. The confirmation step
1959     /// is separated from the main match procedure because these
1960     /// type errors do not cause us to select another impl.
1961     ///
1962     /// As an example, consider matching the obligation
1963     /// `Iterator<char> for Elems<int>` using the following impl:
1964     ///
1965     ///    impl<T> Iterator<T> for Elems<T> { ... }
1966     ///
1967     /// The match phase will succeed with substitution `T=int`.
1968     /// The confirm step will then try to unify `int` and `char`
1969     /// and yield an error.
1970     fn confirm_impl_vtable(&mut self,
1971                            impl_def_id: ast::DefId,
1972                            obligation_cause: ObligationCause<'tcx>,
1973                            obligation_trait_ref: Rc<ty::TraitRef<'tcx>>,
1974                            substs: &Substs<'tcx>)
1975                            -> Result<(), SelectionError<'tcx>>
1976     {
1977         let impl_trait_ref = ty::impl_trait_ref(self.tcx(),
1978                                                 impl_def_id).unwrap();
1979         let impl_trait_ref = impl_trait_ref.subst(self.tcx(),
1980                                                   substs);
1981         self.confirm(obligation_cause, obligation_trait_ref, impl_trait_ref)
1982     }
1983
1984     /// After we have determined which impl applies, and with what substitutions, there is one last
1985     /// step. We have to go back and relate the "output" type parameters from the obligation to the
1986     /// types that are specified in the impl.
1987     ///
1988     /// For example, imagine we have:
1989     ///
1990     ///     impl<T> Iterator<T> for Vec<T> { ... }
1991     ///
1992     /// and our obligation is `Iterator<Foo> for Vec<int>` (note the mismatch in the obligation
1993     /// types). Up until this step, no error would be reported: the self type is `Vec<int>`, and
1994     /// that matches `Vec<T>` with the substitution `T=int`. At this stage, we could then go and
1995     /// check that the type parameters to the `Iterator` trait match. (In terms of the parameters,
1996     /// the `expected_trait_ref` here would be `Iterator<int> for Vec<int>`, and the
1997     /// `obligation_trait_ref` would be `Iterator<Foo> for Vec<int>`.
1998     ///
1999     /// Note that this checking occurs *after* the impl has selected, because these output type
2000     /// parameters should not affect the selection of the impl. Therefore, if there is a mismatch,
2001     /// we report an error to the user.
2002     fn confirm(&mut self,
2003                obligation_cause: ObligationCause,
2004                obligation_trait_ref: Rc<ty::TraitRef<'tcx>>,
2005                expected_trait_ref: Rc<ty::TraitRef<'tcx>>)
2006                -> Result<(), SelectionError<'tcx>>
2007     {
2008         let origin = infer::RelateOutputImplTypes(obligation_cause.span);
2009
2010         let obligation_trait_ref = obligation_trait_ref.clone();
2011         match self.infcx.sub_trait_refs(false,
2012                                         origin,
2013                                         expected_trait_ref.clone(),
2014                                         obligation_trait_ref) {
2015             Ok(()) => Ok(()),
2016             Err(e) => Err(OutputTypeParameterMismatch(expected_trait_ref, e))
2017         }
2018     }
2019
2020     ///////////////////////////////////////////////////////////////////////////
2021     // Miscellany
2022
2023     fn push_stack<'o,'s:'o>(&mut self,
2024                             previous_stack: Option<&'s ObligationStack<'s, 'tcx>>,
2025                             obligation: &'o Obligation<'tcx>)
2026                             -> ObligationStack<'o, 'tcx>
2027     {
2028         let skol_trait_ref = obligation.trait_ref.fold_with(&mut self.skolemizer);
2029
2030         ObligationStack {
2031             obligation: obligation,
2032             skol_trait_ref: skol_trait_ref,
2033             previous: previous_stack.map(|p| p), // FIXME variance
2034         }
2035     }
2036
2037     /// Returns set of all impls for a given trait.
2038     fn all_impls(&self, trait_def_id: ast::DefId) -> Vec<ast::DefId> {
2039         ty::populate_implementations_for_trait_if_necessary(self.tcx(),
2040                                                             trait_def_id);
2041         match self.tcx().trait_impls.borrow().get(&trait_def_id) {
2042             None => Vec::new(),
2043             Some(impls) => impls.borrow().clone()
2044         }
2045     }
2046
2047     fn impl_obligations(&self,
2048                         cause: ObligationCause<'tcx>,
2049                         recursion_depth: uint,
2050                         impl_def_id: ast::DefId,
2051                         impl_substs: &Substs<'tcx>)
2052                         -> VecPerParamSpace<Obligation<'tcx>>
2053     {
2054         let impl_generics = ty::lookup_item_type(self.tcx(), impl_def_id).generics;
2055         let bounds = impl_generics.to_bounds(self.tcx(), impl_substs);
2056         util::obligations_for_generics(self.tcx(), cause, recursion_depth,
2057                                        &bounds, &impl_substs.types)
2058     }
2059
2060     fn fn_family_trait_kind(&self,
2061                             trait_def_id: ast::DefId)
2062                             -> Option<ty::UnboxedClosureKind>
2063     {
2064         let tcx = self.tcx();
2065         if Some(trait_def_id) == tcx.lang_items.fn_trait() {
2066             Some(ty::FnUnboxedClosureKind)
2067         } else if Some(trait_def_id) == tcx.lang_items.fn_mut_trait() {
2068             Some(ty::FnMutUnboxedClosureKind)
2069         } else if Some(trait_def_id) == tcx.lang_items.fn_once_trait() {
2070             Some(ty::FnOnceUnboxedClosureKind)
2071         } else {
2072             None
2073         }
2074     }
2075 }
2076
2077 impl<'tcx> Repr<'tcx> for Candidate<'tcx> {
2078     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
2079         match *self {
2080             ErrorCandidate => format!("ErrorCandidate"),
2081             BuiltinCandidate(b) => format!("BuiltinCandidate({})", b),
2082             UnboxedClosureCandidate(c, ref s) => {
2083                 format!("UnboxedClosureCandidate({},{})", c, s.repr(tcx))
2084             }
2085             FnPointerCandidate => {
2086                 format!("FnPointerCandidate")
2087             }
2088             ParamCandidate(ref a) => format!("ParamCandidate({})", a.repr(tcx)),
2089             ImplCandidate(a) => format!("ImplCandidate({})", a.repr(tcx)),
2090         }
2091     }
2092 }
2093
2094 impl<'tcx> SelectionCache<'tcx> {
2095     pub fn new() -> SelectionCache<'tcx> {
2096         SelectionCache {
2097             hashmap: RefCell::new(HashMap::new())
2098         }
2099     }
2100 }
2101
2102 impl<'o, 'tcx> ObligationStack<'o, 'tcx> {
2103     fn iter(&self) -> Option<&ObligationStack<'o, 'tcx>> {
2104         Some(self)
2105     }
2106 }
2107
2108 impl<'o, 'tcx> Iterator<&'o ObligationStack<'o, 'tcx>> for Option<&'o ObligationStack<'o, 'tcx>> {
2109     fn next(&mut self) -> Option<&'o ObligationStack<'o, 'tcx>> {
2110         match *self {
2111             Some(o) => {
2112                 *self = o.previous;
2113                 Some(o)
2114             }
2115             None => {
2116                 None
2117             }
2118         }
2119     }
2120 }
2121
2122 impl<'o, 'tcx> Repr<'tcx> for ObligationStack<'o, 'tcx> {
2123     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
2124         format!("ObligationStack({})",
2125                 self.obligation.repr(tcx))
2126     }
2127 }
2128
2129 impl EvaluationResult {
2130     fn may_apply(&self) -> bool {
2131         match *self {
2132             EvaluatedToOk | EvaluatedToAmbig => true,
2133             EvaluatedToErr => false,
2134         }
2135     }
2136 }
2137
2138 impl MethodMatchResult {
2139     pub fn may_apply(&self) -> bool {
2140         match *self {
2141             MethodMatched(_) => true,
2142             MethodAmbiguous(_) => true,
2143             MethodDidNotMatch => false,
2144         }
2145     }
2146 }