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
  13 use super::{Obligation, ObligationCause};
  14 use super::{EvaluationResult, EvaluatedToMatch,
  15             EvaluatedToAmbiguity, EvaluatedToUnmatch};
  16 use super::{SelectionError, Unimplemented, Overflow,
  17             OutputTypeParameterMismatch};
  18 use super::{Selection};
  19 use super::{SelectionResult};
  20 use super::{VtableBuiltin, VtableImpl, VtableParam, VtableUnboxedClosure};
  21 use super::{VtableImplData, VtableParamData};
  22 use super::{util};
  23
  24 use middle::subst::{Subst, Substs, VecPerParamSpace};
  25 use middle::ty;
  26 use middle::typeck::check::regionmanip;
  27 use middle::typeck::infer;
  28 use middle::typeck::infer::InferCtxt;
  29 use std::rc::Rc;
  30 use syntax::ast;
  31 use util::nodemap::DefIdMap;
  32 use util::ppaux::Repr;
  33
  34 pub struct SelectionContext<'cx, 'tcx:'cx> {
  35     infcx: &'cx InferCtxt<'cx, 'tcx>,
  36     param_env: &'cx ty::ParameterEnvironment,
  37     unboxed_closures: &'cx DefIdMap<ty::UnboxedClosure>,
  38 }
  39
  40 // pub struct SelectionCache {
  41 //     hashmap: RefCell<HashMap<CacheKey, Candidate>>,
  42 // }
  43
  44 // #[deriving(Hash,Eq,PartialEq)]
  45 // struct CacheKey {
  46 //     trait_def_id: ast::DefId,
  47 //     skol_obligation_self_ty: ty::t,
  48 // }
  49
  50 enum MatchResult<T> {
  51     Matched(T),
  52     AmbiguousMatch,
  53     NoMatch
  54 }
  55
  56 /**
  57  * The selection process begins by considering all impls, where
  58  * clauses, and so forth that might resolve an obligation.  Sometimes
  59  * we'll be able to say definitively that (e.g.) an impl does not
  60  * apply to the obligation: perhaps it is defined for `uint` but the
  61  * obligation is for `int`. In that case, we drop the impl out of the
  62  * list.  But the other cases are considered *candidates*.
  63  *
  64  * Candidates can either be definitive or ambiguous. An ambiguous
  65  * candidate is one that might match or might not, depending on how
  66  * type variables wind up being resolved. This only occurs during inference.
  67  *
  68  * For selection to suceed, there must be exactly one non-ambiguous
  69  * candidate.  Usually, it is not possible to have more than one
  70  * definitive candidate, due to the coherence rules. However, there is
  71  * one case where it could occur: if there is a blanket impl for a
  72  * trait (that is, an impl applied to all T), and a type parameter
  73  * with a where clause. In that case, we can have a candidate from the
  74  * where clause and a second candidate from the impl. This is not a
  75  * problem because coherence guarantees us that the impl which would
  76  * be used to satisfy the where clause is the same one that we see
  77  * now. To resolve this issue, therefore, we ignore impls if we find a
  78  * matching where clause. Part of the reason for this is that where
  79  * clauses can give additional information (like, the types of output
  80  * parameters) that would have to be inferred from the impl.
  81  */
  82 #[deriving(Clone)]
  83 enum Candidate {
  84     MatchedBuiltinCandidate,
  85     AmbiguousBuiltinCandidate,
  86     MatchedParamCandidate(VtableParamData),
  87     AmbiguousParamCandidate,
  88     Impl(ImplCandidate),
  89     MatchedUnboxedClosureCandidate(/* closure */ ast::DefId)
  90 }
  91
  92 #[deriving(Clone)]
  93 enum ImplCandidate {
  94     MatchedImplCandidate(ast::DefId),
  95     AmbiguousImplCandidate(ast::DefId),
  96 }
  97
  98 impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
  99     pub fn new(infcx: &'cx InferCtxt<'cx, 'tcx>,
 100                param_env: &'cx ty::ParameterEnvironment,
 101                unboxed_closures: &'cx DefIdMap<ty::UnboxedClosure>)
 102                -> SelectionContext<'cx, 'tcx> {
 103         SelectionContext { infcx: infcx, param_env: param_env,
 104                            unboxed_closures: unboxed_closures }
 105     }
 106
 107     pub fn tcx(&self) -> &'cx ty::ctxt<'tcx> {
 108         self.infcx.tcx
 109     }
 110
 111     ///////////////////////////////////////////////////////////////////////////
 112     // Selection
 113     //
 114     // The selection phase tries to identify *how* an obligation will
 115     // be resolved. For example, it will identify which impl or
 116     // parameter bound is to be used. The process can be inconclusive
 117     // if the self type in the obligation is not fully inferred. Selection
 118     // can result in an error in one of two ways:
 119     //
 120     // 1. If no applicable impl or parameter bound can be found.
 121     // 2. If the output type parameters in the obligation do not match
 122     //    those specified by the impl/bound. For example, if the obligation
 123     //    is `Vec<Foo>:Iterable<Bar>`, but the impl specifies
 124     //    `impl<T> Iterable<T> for Vec<T>`, than an error would result.
 125
 126     pub fn select(&self, obligation: &Obligation) -> SelectionResult<Selection> {
 127         /*!
 128          * Evaluates whether the obligation can be satisfied. Returns
 129          * an indication of whether the obligation can be satisfied
 130          * and, if so, by what means. Never affects surrounding typing
 131          * environment.
 132          */
 133
 134         debug!("select({})", obligation.repr(self.tcx()));
 135
 136         match try!(self.candidate_from_obligation(obligation)) {
 137             None => Ok(None),
 138             Some(candidate) => self.confirm_candidate(obligation, candidate),
 139         }
 140     }
 141
 142     pub fn select_inherent_impl(&self,
 143                                 impl_def_id: ast::DefId,
 144                                 obligation_cause: ObligationCause,
 145                                 obligation_self_ty: ty::t)
 146                                 -> SelectionResult<VtableImplData<Obligation>>
 147     {
 148         debug!("select_inherent_impl(impl_def_id={}, obligation_self_ty={})",
 149                impl_def_id.repr(self.tcx()),
 150                obligation_self_ty.repr(self.tcx()));
 151
 152         match self.candidate_from_impl(impl_def_id,
 153                                        obligation_cause,
 154                                        obligation_self_ty) {
 155             Some(MatchedImplCandidate(impl_def_id)) => {
 156                 let vtable_impl =
 157                     try!(self.confirm_inherent_impl_candidate(
 158                         impl_def_id,
 159                         obligation_cause,
 160                         obligation_self_ty,
 161                         0));
 162                 Ok(Some(vtable_impl))
 163             }
 164             Some(AmbiguousImplCandidate(_)) => {
 165                 Ok(None)
 166             }
 167             None => {
 168                 Err(Unimplemented)
 169             }
 170         }
 171     }
 172
 173     ///////////////////////////////////////////////////////////////////////////
 174     // EVALUATION
 175     //
 176     // Tests whether an obligation can be selected or whether an impl can be
 177     // applied to particular types. It skips the "confirmation" step and
 178     // hence completely ignores output type parameters.
 179
 180     pub fn evaluate_obligation(&self,
 181                                obligation: &Obligation)
 182                                -> EvaluationResult
 183     {
 184         /*!
 185          * Evaluates whether the obligation `obligation` can be
 186          * satisfied (by any means).
 187          */
 188
 189         debug!("evaluate_obligation({})",
 190                obligation.repr(self.tcx()));
 191
 192         match self.candidate_from_obligation(obligation) {
 193             Ok(Some(c)) => c.to_evaluation_result(),
 194             Ok(None) => EvaluatedToAmbiguity,
 195             Err(_) => EvaluatedToUnmatch,
 196         }
 197     }
 198
 199     pub fn evaluate_impl(&self,
 200                          impl_def_id: ast::DefId,
 201                          obligation_cause: ObligationCause,
 202                          obligation_self_ty: ty::t)
 203                          -> EvaluationResult
 204     {
 205         /*!
 206          * Evaluates whether the impl with id `impl_def_id` could be
 207          * applied to the self type `obligation_self_ty`. This can be
 208          * used either for trait or inherent impls.
 209          */
 210
 211         debug!("evaluate_impl(impl_def_id={}, obligation_self_ty={})",
 212                impl_def_id.repr(self.tcx()),
 213                obligation_self_ty.repr(self.tcx()));
 214
 215         match self.candidate_from_impl(impl_def_id,
 216                                        obligation_cause,
 217                                        obligation_self_ty) {
 218             Some(c) => c.to_evaluation_result(),
 219             None => EvaluatedToUnmatch,
 220         }
 221     }
 222
 223     ///////////////////////////////////////////////////////////////////////////
 224     // CANDIDATE ASSEMBLY
 225     //
 226     // The selection process begins by examining all in-scope impls,
 227     // caller obligations, and so forth and assembling a list of
 228     // candidates. See `doc.rs` and the `Candidate` type for more details.
 229
 230     fn candidate_from_obligation(&self, obligation: &Obligation)
 231                                  -> SelectionResult<Candidate>
 232     {
 233         debug!("candidate_from_obligation({}, self_ty={})",
 234                obligation.repr(self.tcx()),
 235                self.infcx.ty_to_string(obligation.self_ty()));
 236
 237         let skol_obligation_self_ty =
 238             infer::skolemize(self.infcx, obligation.self_ty());
 239
 240         // First, check the cache.
 241         match self.check_candidate_cache(obligation, skol_obligation_self_ty) {
 242             Some(c) => {
 243                 return Ok(Some(c));
 244             }
 245             None => { }
 246         }
 247
 248         let mut candidates =
 249             try!(self.assemble_candidates(obligation,
 250                                           skol_obligation_self_ty));
 251
 252         debug!("candidate_from_obligation: {} candidates for {}",
 253                candidates.len(), obligation.repr(self.tcx()));
 254
 255         // Examine candidates to determine outcome. Ideally we will
 256         // have exactly one candidate that is definitively applicable.
 257
 258         if candidates.len() == 0 {
 259             // Annoying edge case: if there are no impls, then there
 260             // is no way that this trait reference is implemented,
 261             // *unless* it contains unbound variables. In that case,
 262             // it is possible that one of those unbound variables will
 263             // be bound to a new type from some other crate which will
 264             // also contain impls.
 265             let trait_ref = &*obligation.trait_ref;
 266             return if !self.trait_ref_unconstrained(trait_ref) {
 267                 debug!("candidate_from_obligation({}) -> 0 matches, unimpl",
 268                        obligation.repr(self.tcx()));
 269                 Err(Unimplemented)
 270             } else {
 271                 debug!("candidate_from_obligation({}) -> 0 matches, ambig",
 272                        obligation.repr(self.tcx()));
 273                 Ok(None)
 274             };
 275         }
 276
 277         if candidates.len() > 1 {
 278             // Ambiguity. Possibly we should report back more
 279             // information on the potential candidates so we can give
 280             // a better error message.
 281             debug!("candidate_from_obligation({}) -> multiple matches, ambig",
 282                    obligation.repr(self.tcx()));
 283
 284             return Ok(None);
 285         }
 286
 287         let candidate = candidates.pop().unwrap();
 288         self.insert_candidate_cache(obligation, skol_obligation_self_ty,
 289                                     candidate.clone());
 290         Ok(Some(candidate))
 291     }
 292
 293     fn check_candidate_cache(&self,
 294                              _obligation: &Obligation,
 295                              _skol_obligation_self_ty: ty::t)
 296                              -> Option<Candidate>
 297     {
 298         // let cache_key = CacheKey::new(obligation.trait_ref.def_id,
 299         //                               skol_obligation_self_ty);
 300         // let hashmap = self.tcx().selection_cache.hashmap.borrow();
 301         // hashmap.find(&cache_key).map(|c| (*c).clone())
 302         None
 303     }
 304
 305     fn insert_candidate_cache(&self,
 306                               _obligation: &Obligation,
 307                               _skol_obligation_self_ty: ty::t,
 308                               _candidate: Candidate)
 309     {
 310         // FIXME -- Enable caching. I think the right place to put the cache
 311         // is in the ParameterEnvironment, not the tcx, because otherwise
 312         // when there are distinct where clauses in scope the cache can get
 313         // confused.
 314         //
 315         //let cache_key = CacheKey::new(obligation.trait_ref.def_id,
 316         //                              skol_obligation_self_ty);
 317         //let mut hashmap = self.tcx().selection_cache.hashmap.borrow_mut();
 318         //hashmap.insert(cache_key, candidate);
 319     }
 320
 321     fn assemble_candidates(&self,
 322                            obligation: &Obligation,
 323                            skol_obligation_self_ty: ty::t)
 324                            -> Result<Vec<Candidate>, SelectionError>
 325     {
 326         // Check for overflow.
 327
 328         let recursion_limit = self.infcx.tcx.sess.recursion_limit.get();
 329         if obligation.recursion_depth >= recursion_limit {
 330             debug!("{} --> overflow", obligation.repr(self.tcx()));
 331             return Err(Overflow);
 332         }
 333
 334         let mut candidates = Vec::new();
 335
 336         match self.tcx().lang_items.to_builtin_kind(obligation.trait_ref.def_id) {
 337             Some(_) => {
 338                 // FIXME -- The treatment of builtin bounds is a bit
 339                 // hacky right now. Eventually, the idea is to move
 340                 // the logic for selection out of type_contents and
 341                 // into this module (And make it based on the generic
 342                 // mechanisms of OIBTT2).  However, I want to land
 343                 // some code today, so we're going to cut a few
 344                 // corners. What we do now is that the trait selection
 345                 // code always considers builtin obligations to
 346                 // match. The fulfillment code (which also has the job
 347                 // of tracking all the traits that must hold) will
 348                 // then just accumulate the various
 349                 // builtin-bound-related obligations that must be met.
 350                 // Later, at the end of typeck, after writeback etc,
 351                 // we will rewalk this list and extract all the
 352                 // builtin-bound-related obligations and test them
 353                 // again using type contents. Part of the motivation
 354                 // for this is that the type contents code requires
 355                 // that writeback has been completed in some cases.
 356
 357                 candidates.push(AmbiguousBuiltinCandidate);
 358             }
 359
 360             None => {
 361                 // Other bounds. Consider both in-scope bounds from fn decl
 362                 // and applicable impls.
 363
 364                 try!(self.assemble_candidates_from_caller_bounds(
 365                     obligation,
 366                     skol_obligation_self_ty,
 367                     &mut candidates));
 368
 369                 try!(self.assemble_unboxed_candidates(
 370                     obligation,
 371                     skol_obligation_self_ty,
 372                     &mut candidates));
 373
 374                 // If there is a fn bound that applies, forego the
 375                 // impl search. It can only generate conflicts.
 376
 377                 if candidates.len() == 0 {
 378                     try!(self.assemble_candidates_from_impls(
 379                         obligation,
 380                         skol_obligation_self_ty,
 381                         &mut candidates));
 382                 }
 383             }
 384         }
 385
 386         Ok(candidates)
 387     }
 388
 389     fn assemble_candidates_from_caller_bounds(&self,
 390                                               obligation: &Obligation,
 391                                               skol_obligation_self_ty: ty::t,
 392                                               candidates: &mut Vec<Candidate>)
 393                                               -> Result<(),SelectionError>
 394     {
 395         /*!
 396          * Given an obligation like `<SomeTrait for T>`, search the obligations
 397          * that the caller supplied to find out whether it is listed among
 398          * them.
 399          *
 400          * Never affects inference environment.
 401 v         */
 402
 403         debug!("assemble_candidates_from_caller_bounds({})",
 404                obligation.repr(self.tcx()));
 405
 406         for caller_obligation in self.param_env.caller_obligations.iter() {
 407             debug!("caller_obligation={}",
 408                    caller_obligation.repr(self.tcx()));
 409
 410             // Skip over obligations that don't apply to
 411             // `self_ty`.
 412             let caller_bound = &caller_obligation.trait_ref;
 413             let caller_self_ty = caller_bound.substs.self_ty().unwrap();
 414             match self.match_self_types(obligation.cause,
 415                                         caller_self_ty,
 416                                         skol_obligation_self_ty) {
 417                 AmbiguousMatch => {
 418                     debug!("-> AmbiguousParamCandidate");
 419                     candidates.push(AmbiguousParamCandidate);
 420                     return Ok(());
 421                 }
 422                 NoMatch => {
 423                     continue;
 424                 }
 425                 Matched(()) => { }
 426             }
 427
 428             // Search through the trait (and its supertraits) to
 429             // see if it matches the def-id we are looking for.
 430             let caller_bound = (*caller_bound).clone();
 431             match util::search_trait_and_supertraits_from_bound(
 432                 self.infcx.tcx, caller_bound,
 433                 |d| d == obligation.trait_ref.def_id)
 434             {
 435                 Some(vtable_param) => {
 436                     // If so, we're done!
 437                     debug!("-> MatchedParamCandidate({})", vtable_param);
 438                     candidates.push(MatchedParamCandidate(vtable_param));
 439                     return Ok(());
 440                 }
 441
 442                 None => {
 443                 }
 444             }
 445         }
 446
 447         Ok(())
 448     }
 449
 450     fn assemble_unboxed_candidates(&self,
 451                                    obligation: &Obligation,
 452                                    skol_obligation_self_ty: ty::t,
 453                                    candidates: &mut Vec<Candidate>)
 454                                    -> Result<(),SelectionError>
 455     {
 456         /*!
 457          * Check for the artificial impl that the compiler will create
 458          * for an obligation like `X : FnMut<..>` where `X` is an
 459          * unboxed closure type.
 460          */
 461
 462         let closure_def_id = match ty::get(skol_obligation_self_ty).sty {
 463             ty::ty_unboxed_closure(id, _) => id,
 464             _ => { return Ok(()); }
 465         };
 466
 467         let tcx = self.tcx();
 468         let fn_traits = [
 469             (ty::FnUnboxedClosureKind, tcx.lang_items.fn_trait()),
 470             (ty::FnMutUnboxedClosureKind, tcx.lang_items.fn_mut_trait()),
 471             (ty::FnOnceUnboxedClosureKind, tcx.lang_items.fn_once_trait()),
 472             ];
 473         for tuple in fn_traits.iter() {
 474             let kind = match tuple {
 475                 &(kind, Some(ref fn_trait))
 476                     if *fn_trait == obligation.trait_ref.def_id =>
 477                 {
 478                     kind
 479                 }
 480                 _ => continue,
 481             };
 482
 483             // Check to see whether the argument and return types match.
 484             let closure_kind = match self.unboxed_closures.find(&closure_def_id) {
 485                 Some(closure) => closure.kind,
 486                 None => {
 487                     self.tcx().sess.span_bug(
 488                         obligation.cause.span,
 489                         format!("No entry for unboxed closure: {}",
 490                                 closure_def_id.repr(self.tcx())).as_slice());
 491                 }
 492             };
 493
 494             if closure_kind != kind {
 495                 continue;
 496             }
 497
 498             candidates.push(MatchedUnboxedClosureCandidate(closure_def_id));
 499         }
 500
 501         Ok(())
 502     }
 503
 504     fn assemble_candidates_from_impls(&self,
 505                                       obligation: &Obligation,
 506                                       skol_obligation_self_ty: ty::t,
 507                                       candidates: &mut Vec<Candidate>)
 508                                       -> Result<(), SelectionError>
 509     {
 510         /*!
 511          * Search for impls that might apply to `obligation`.
 512          */
 513
 514         let all_impls = self.all_impls(obligation.trait_ref.def_id);
 515         for &impl_def_id in all_impls.iter() {
 516             self.infcx.probe(|| {
 517                 match self.candidate_from_impl(impl_def_id,
 518                                                obligation.cause,
 519                                                skol_obligation_self_ty) {
 520                     Some(c) => {
 521                         candidates.push(Impl(c));
 522                     }
 523
 524                     None => { }
 525                 }
 526             });
 527         }
 528         Ok(())
 529     }
 530
 531     fn candidate_from_impl(&self,
 532                            impl_def_id: ast::DefId,
 533                            obligation_cause: ObligationCause,
 534                            skol_obligation_self_ty: ty::t)
 535                            -> Option<ImplCandidate>
 536     {
 537         match self.match_impl_self_types(impl_def_id,
 538                                          obligation_cause,
 539                                          skol_obligation_self_ty) {
 540             Matched(_) => {
 541                 Some(MatchedImplCandidate(impl_def_id))
 542             }
 543
 544             AmbiguousMatch => {
 545                 Some(AmbiguousImplCandidate(impl_def_id))
 546             }
 547
 548             NoMatch => {
 549                 None
 550             }
 551         }
 552     }
 553
 554     ///////////////////////////////////////////////////////////////////////////
 555     // CONFIRMATION
 556     //
 557     // Confirmation unifies the output type parameters of the trait
 558     // with the values found in the obligation, possibly yielding a
 559     // type error.  See `doc.rs` for more details.
 560
 561     fn confirm_candidate(&self,
 562                          obligation: &Obligation,
 563                          candidate: Candidate)
 564                          -> SelectionResult<Selection>
 565     {
 566         debug!("confirm_candidate({}, {})",
 567                obligation.repr(self.tcx()),
 568                candidate.repr(self.tcx()));
 569
 570         match candidate {
 571             AmbiguousBuiltinCandidate |
 572             AmbiguousParamCandidate |
 573             Impl(AmbiguousImplCandidate(_)) => {
 574                 Ok(None)
 575             }
 576
 577             MatchedBuiltinCandidate => {
 578                 Ok(Some(VtableBuiltin))
 579             }
 580
 581             MatchedParamCandidate(param) => {
 582                 Ok(Some(VtableParam(
 583                     try!(self.confirm_param_candidate(obligation, param)))))
 584             }
 585
 586             Impl(MatchedImplCandidate(impl_def_id)) => {
 587                 let vtable_impl = try!(self.confirm_impl_candidate(obligation,
 588                                                                    impl_def_id));
 589                 Ok(Some(VtableImpl(vtable_impl)))
 590             }
 591
 592             MatchedUnboxedClosureCandidate(closure_def_id) => {
 593                 try!(self.confirm_unboxed_closure_candidate(obligation, closure_def_id));
 594                 Ok(Some(VtableUnboxedClosure(closure_def_id)))
 595             }
 596         }
 597     }
 598
 599     fn confirm_param_candidate(&self,
 600                                obligation: &Obligation,
 601                                param: VtableParamData)
 602                                -> Result<VtableParamData,SelectionError>
 603     {
 604         debug!("confirm_param_candidate({},{})",
 605                obligation.repr(self.tcx()),
 606                param.repr(self.tcx()));
 607
 608         let () = try!(self.confirm(obligation.cause,
 609                                    obligation.trait_ref.clone(),
 610                                    param.bound.clone()));
 611         Ok(param)
 612     }
 613
 614     fn confirm_impl_candidate(&self,
 615                               obligation: &Obligation,
 616                               impl_def_id: ast::DefId)
 617                               -> Result<VtableImplData<Obligation>,SelectionError>
 618     {
 619         debug!("confirm_impl_candidate({},{})",
 620                obligation.repr(self.tcx()),
 621                impl_def_id.repr(self.tcx()));
 622
 623         // For a non-inhernet impl, we begin the same way as an
 624         // inherent impl, by matching the self-type and assembling
 625         // list of nested obligations.
 626         let vtable_impl =
 627             try!(self.confirm_inherent_impl_candidate(
 628                 impl_def_id,
 629                 obligation.cause,
 630                 obligation.trait_ref.self_ty(),
 631                 obligation.recursion_depth));
 632
 633         // But then we must also match the output types.
 634         let () = try!(self.confirm_impl_vtable(impl_def_id,
 635                                                obligation.cause,
 636                                                obligation.trait_ref.clone(),
 637                                                &vtable_impl.substs));
 638         Ok(vtable_impl)
 639     }
 640
 641     fn confirm_inherent_impl_candidate(&self,
 642                                        impl_def_id: ast::DefId,
 643                                        obligation_cause: ObligationCause,
 644                                        obligation_self_ty: ty::t,
 645                                        obligation_recursion_depth: uint)
 646                                        -> Result<VtableImplData<Obligation>,
 647                                                  SelectionError>
 648     {
 649         let substs = match self.match_impl_self_types(impl_def_id,
 650                                                       obligation_cause,
 651                                                       obligation_self_ty) {
 652             Matched(substs) => substs,
 653             AmbiguousMatch | NoMatch => {
 654                 self.tcx().sess.bug(
 655                     format!("Impl {} was matchable against {} but now is not",
 656                             impl_def_id.repr(self.tcx()),
 657                             obligation_self_ty.repr(self.tcx()))
 658                         .as_slice());
 659             }
 660         };
 661
 662         let impl_obligations =
 663             self.impl_obligations(obligation_cause,
 664                                   obligation_recursion_depth,
 665                                   impl_def_id,
 666                                   &substs);
 667         let vtable_impl = VtableImplData { impl_def_id: impl_def_id,
 668                                        substs: substs,
 669                                        nested: impl_obligations };
 670
 671         Ok(vtable_impl)
 672     }
 673
 674     fn confirm_unboxed_closure_candidate(&self,
 675                                          obligation: &Obligation,
 676                                          closure_def_id: ast::DefId)
 677                                          -> Result<(),SelectionError>
 678     {
 679         debug!("confirm_unboxed_closure_candidate({},{})",
 680                obligation.repr(self.tcx()),
 681                closure_def_id.repr(self.tcx()));
 682
 683         let closure_type = match self.unboxed_closures.find(&closure_def_id) {
 684             Some(closure) => closure.closure_type.clone(),
 685             None => {
 686                 self.tcx().sess.span_bug(
 687                     obligation.cause.span,
 688                     format!("No entry for unboxed closure: {}",
 689                             closure_def_id.repr(self.tcx())).as_slice());
 690             }
 691         };
 692
 693         // FIXME(pcwalton): This is a bogus thing to do, but
 694         // it'll do for now until we get the new trait-bound
 695         // region skolemization working.
 696         let (_, new_signature) =
 697             regionmanip::replace_late_bound_regions_in_fn_sig(
 698                 self.tcx(),
 699                 &closure_type.sig,
 700                 |br| self.infcx.next_region_var(
 701                          infer::LateBoundRegion(obligation.cause.span, br)));
 702
 703         let arguments_tuple = *new_signature.inputs.get(0);
 704         let trait_ref = Rc::new(ty::TraitRef {
 705             def_id: obligation.trait_ref.def_id,
 706             substs: Substs::new_trait(
 707                 vec![arguments_tuple, new_signature.output],
 708                 vec![],
 709                 obligation.self_ty())
 710         });
 711
 712         self.confirm(obligation.cause,
 713                      obligation.trait_ref.clone(),
 714                      trait_ref)
 715     }
 716
 717     ///////////////////////////////////////////////////////////////////////////
 718     // Matching
 719     //
 720     // Matching is a common path used for both evaluation and
 721     // confirmation.  It basically unifies types that appear in impls
 722     // and traits. This does affect the surrounding environment;
 723     // therefore, when used during evaluation, match routines must be
 724     // run inside of a `probe()` so that their side-effects are
 725     // contained.
 726
 727     fn match_impl_self_types(&self,
 728                              impl_def_id: ast::DefId,
 729                              obligation_cause: ObligationCause,
 730                              obligation_self_ty: ty::t)
 731                              -> MatchResult<Substs>
 732     {
 733         /*!
 734          * Determines whether the self type declared against
 735          * `impl_def_id` matches `obligation_self_ty`. If successful,
 736          * returns the substitutions used to make them match. See
 737          * `match_impl()`.  For example, if `impl_def_id` is declared
 738          * as:
 739          *
 740          *    impl<T:Copy> Foo for ~T { ... }
 741          *
 742          * and `obligation_self_ty` is `int`, we'd back an `Err(_)`
 743          * result. But if `obligation_self_ty` were `~int`, we'd get
 744          * back `Ok(T=int)`.
 745          */
 746
 747         // Create fresh type variables for each type parameter declared
 748         // on the impl etc.
 749         let impl_substs = util::fresh_substs_for_impl(self.infcx,
 750                                                       obligation_cause.span,
 751                                                       impl_def_id);
 752
 753         // Find the self type for the impl.
 754         let impl_self_ty = ty::lookup_item_type(self.tcx(), impl_def_id).ty;
 755         let impl_self_ty = impl_self_ty.subst(self.tcx(), &impl_substs);
 756
 757         debug!("match_impl_self_types(obligation_self_ty={}, impl_self_ty={})",
 758                obligation_self_ty.repr(self.tcx()),
 759                impl_self_ty.repr(self.tcx()));
 760
 761         match self.match_self_types(obligation_cause,
 762                                     impl_self_ty,
 763                                     obligation_self_ty) {
 764             Matched(()) => {
 765                 debug!("Matched impl_substs={}", impl_substs.repr(self.tcx()));
 766                 Matched(impl_substs)
 767             }
 768             AmbiguousMatch => {
 769                 debug!("AmbiguousMatch");
 770                 AmbiguousMatch
 771             }
 772             NoMatch => {
 773                 debug!("NoMatch");
 774                 NoMatch
 775             }
 776         }
 777     }
 778
 779     fn match_self_types(&self,
 780                         cause: ObligationCause,
 781
 782                         // The self type provided by the impl/caller-obligation:
 783                         provided_self_ty: ty::t,
 784
 785                         // The self type the obligation is for:
 786                         required_self_ty: ty::t)
 787                         -> MatchResult<()>
 788     {
 789         // FIXME(#5781) -- equating the types is stronger than
 790         // necessary. Should consider variance of trait w/r/t Self.
 791
 792         let origin = infer::RelateSelfType(cause.span);
 793         match self.infcx.eq_types(false,
 794                                   origin,
 795                                   provided_self_ty,
 796                                   required_self_ty) {
 797             Ok(()) => Matched(()),
 798             Err(ty::terr_sorts(ty::expected_found{expected: t1, found: t2})) => {
 799                 // This error occurs when there is an unresolved type
 800                 // variable in the `required_self_ty` that was forced
 801                 // to unify with a non-type-variable. That basically
 802                 // means we don't know enough to say with certainty
 803                 // whether there is a match or not -- it depends on
 804                 // how that type variable is ultimately resolved.
 805                 if ty::type_is_skolemized(t1) || ty::type_is_skolemized(t2) {
 806                     AmbiguousMatch
 807                 } else {
 808                     NoMatch
 809                 }
 810             }
 811             Err(_) => NoMatch,
 812         }
 813     }
 814
 815     ///////////////////////////////////////////////////////////////////////////
 816     // Confirmation
 817     //
 818     // The final step of selection: once we know how an obligation is
 819     // is resolved, we confirm that selection in order to have
 820     // side-effects on the typing environment. This step also unifies
 821     // the output type parameters from the obligation with those found
 822     // on the impl/bound, which may yield type errors.
 823
 824     fn confirm_impl_vtable(&self,
 825                            impl_def_id: ast::DefId,
 826                            obligation_cause: ObligationCause,
 827                            obligation_trait_ref: Rc<ty::TraitRef>,
 828                            substs: &Substs)
 829                            -> Result<(), SelectionError>
 830     {
 831         /*!
 832          * Relates the output type parameters from an impl to the
 833          * trait.  This may lead to type errors. The confirmation step
 834          * is separated from the main match procedure because these
 835          * type errors do not cause us to select another impl.
 836          *
 837          * As an example, consider matching the obligation
 838          * `Iterator<char> for Elems<int>` using the following impl:
 839          *
 840          *    impl<T> Iterator<T> for Elems<T> { ... }
 841          *
 842          * The match phase will succeed with substitution `T=int`.
 843          * The confirm step will then try to unify `int` and `char`
 844          * and yield an error.
 845          */
 846
 847         let impl_trait_ref = ty::impl_trait_ref(self.tcx(),
 848                                                 impl_def_id).unwrap();
 849         let impl_trait_ref = impl_trait_ref.subst(self.tcx(),
 850                                                   substs);
 851         self.confirm(obligation_cause, obligation_trait_ref, impl_trait_ref)
 852     }
 853
 854     fn confirm(&self,
 855                obligation_cause: ObligationCause,
 856                obligation_trait_ref: Rc<ty::TraitRef>,
 857                expected_trait_ref: Rc<ty::TraitRef>)
 858                -> Result<(), SelectionError>
 859     {
 860         /*!
 861          * After we have determined which impl applies, and with what
 862          * substitutions, there is one last step. We have to go back
 863          * and relate the "output" type parameters from the obligation
 864          * to the types that are specified in the impl.
 865          *
 866          * For example, imagine we have:
 867          *
 868          *     impl<T> Iterator<T> for Vec<T> { ... }
 869          *
 870          * and our obligation is `Iterator<Foo> for Vec<int>` (note
 871          * the mismatch in the obligation types). Up until this step,
 872          * no error would be reported: the self type is `Vec<int>`,
 873          * and that matches `Vec<T>` with the substitution `T=int`.
 874          * At this stage, we could then go and check that the type
 875          * parameters to the `Iterator` trait match.
 876          * (In terms of the parameters, the `expected_trait_ref`
 877          * here would be `Iterator<int> for Vec<int>`, and the
 878          * `obligation_trait_ref` would be `Iterator<Foo> for Vec<int>`.
 879          *
 880          * Note that this checking occurs *after* the impl has
 881          * selected, because these output type parameters should not
 882          * affect the selection of the impl. Therefore, if there is a
 883          * mismatch, we report an error to the user.
 884          */
 885
 886         let origin = infer::RelateOutputImplTypes(obligation_cause.span);
 887
 888         let obligation_trait_ref = obligation_trait_ref.clone();
 889         match self.infcx.sub_trait_refs(false,
 890                                         origin,
 891                                         expected_trait_ref.clone(),
 892                                         obligation_trait_ref) {
 893             Ok(()) => Ok(()),
 894             Err(e) => Err(OutputTypeParameterMismatch(expected_trait_ref, e))
 895         }
 896     }
 897
 898     ///////////////////////////////////////////////////////////////////////////
 899     // Miscellany
 900
 901     fn all_impls(&self, trait_def_id: ast::DefId) -> Vec<ast::DefId> {
 902         /*!
 903          * Returns se tof all impls for a given trait.
 904          */
 905
 906         ty::populate_implementations_for_trait_if_necessary(self.tcx(),
 907                                                             trait_def_id);
 908         match self.tcx().trait_impls.borrow().find(&trait_def_id) {
 909             None => Vec::new(),
 910             Some(impls) => impls.borrow().clone()
 911         }
 912     }
 913
 914     fn impl_obligations(&self,
 915                         cause: ObligationCause,
 916                         recursion_depth: uint,
 917                         impl_def_id: ast::DefId,
 918                         impl_substs: &Substs)
 919                         -> VecPerParamSpace<Obligation>
 920     {
 921         let impl_generics = ty::lookup_item_type(self.tcx(),
 922                                                  impl_def_id).generics;
 923         util::obligations_for_generics(self.tcx(), cause, recursion_depth,
 924                                        &impl_generics, impl_substs)
 925     }
 926
 927     fn trait_ref_unconstrained(&self,
 928                                trait_ref: &ty::TraitRef)
 929                                -> bool
 930     {
 931         /*!
 932          * True if the self type of the trait-ref contains
 933          * unconstrained type variables.
 934          */
 935
 936         let mut found_skol = false;
 937
 938         // Skolemization replaces all unconstrained type vars with
 939         // a SkolemizedTy instance. Then we search to see if we
 940         // found any.
 941         let skol_ty = infer::skolemize(self.infcx, trait_ref.self_ty());
 942         ty::walk_ty(skol_ty, |t| {
 943             match ty::get(t).sty {
 944                 ty::ty_infer(ty::SkolemizedTy(_)) => { found_skol = true; }
 945                 _ => { }
 946             }
 947         });
 948
 949         found_skol
 950     }
 951 }
 952
 953 impl Candidate {
 954     fn to_evaluation_result(&self) -> EvaluationResult {
 955         match *self {
 956             Impl(ref i) => i.to_evaluation_result(),
 957
 958             MatchedUnboxedClosureCandidate(..) |
 959             MatchedBuiltinCandidate |
 960             MatchedParamCandidate(..) => {
 961                 EvaluatedToMatch
 962             }
 963
 964             AmbiguousBuiltinCandidate |
 965             AmbiguousParamCandidate => {
 966                 EvaluatedToAmbiguity
 967             }
 968         }
 969     }
 970 }
 971
 972 impl ImplCandidate {
 973     fn to_evaluation_result(&self) -> EvaluationResult {
 974         match *self {
 975             MatchedImplCandidate(..) => EvaluatedToMatch,
 976             AmbiguousImplCandidate(..) => EvaluatedToAmbiguity
 977         }
 978     }
 979 }
 980
 981 impl Repr for Candidate {
 982     fn repr(&self, tcx: &ty::ctxt) -> String {
 983         match *self {
 984             MatchedBuiltinCandidate => format!("MatchedBuiltinCandidate"),
 985             AmbiguousBuiltinCandidate => format!("AmbiguousBuiltinCandidate"),
 986             MatchedUnboxedClosureCandidate(c) => format!("MatchedUnboxedClosureCandidate({})", c),
 987             MatchedParamCandidate(ref r) => format!("MatchedParamCandidate({})",
 988                                                     r.repr(tcx)),
 989             AmbiguousParamCandidate => format!("AmbiguousParamCandidate"),
 990             Impl(ref i) => i.repr(tcx)
 991         }
 992     }
 993 }
 994
 995 impl Repr for ImplCandidate {
 996     fn repr(&self, tcx: &ty::ctxt) -> String {
 997         match *self {
 998             MatchedImplCandidate(ref d) => format!("MatchedImplCandidate({})",
 999                                                    d.repr(tcx)),
1000             AmbiguousImplCandidate(ref d) => format!("AmbiguousImplCandidate({})",
1001                                                      d.repr(tcx)),
1002         }
1003     }
1004 }
1005
1006
1007 // impl SelectionCache {
1008 //     pub fn new() -> SelectionCache {
1009 //         SelectionCache {
1010 //             hashmap: RefCell::new(HashMap::new())
1011 //         }
1012 //     }
1013 // }
1014
1015 // impl CacheKey {
1016 //     pub fn new(trait_def_id: ast::DefId,
1017 //                skol_obligation_self_ty: ty::t)
1018 //                -> CacheKey
1019 //     {
1020 //         CacheKey {
1021 //             trait_def_id: trait_def_id,
1022 //             skol_obligation_self_ty: skol_obligation_self_ty
1023 //         }
1024 //     }
1025 // }