Rollup merge of #72586 - lcnr:winner-winnowing, r=nikomatsakis

split select into submodules

https://github.com/rust-lang/rust/blob/a0f06d11ae7fe29c8e263e2a5d8cd41b372f0283/src/librustc_trait_selection/traits/select.rs#L1

I extracted two submodules:

- confirmation: apart from `pub(super) fn confirm_candidate`, everything else is private
- candidate_assembly: exports `pub(super) fn candidate_from_obligation` and `pub(super) fn assemble_candidates`

I tried to change as little as possible while doing this and hopefully split this into well reviewable commits.

3 files changed, 1440 insertions, 1413 deletions

diff --git a/src/librustc_trait_selection/traits/select/candidate_assembly.rs b/src/librustc_trait_selection/traits/select/candidate_assembly.rs
new file mode 100644
index 00000000000..d42c31a5474
--- /dev/null
+++ b/src/librustc_trait_selection/traits/select/candidate_assembly.rs
@@ -0,0 +1,611 @@
+//! Candidate assembly.
+//!
+//! The selection process begins by examining all in-scope impls,
+//! caller obligations, and so forth and assembling a list of
+//! candidates. See the [rustc dev guide] for more details.
+//!
+//! [rustc dev guide]:https://rustc-dev-guide.rust-lang.org/traits/resolution.html#candidate-assembly
+use rustc_hir as hir;
+use rustc_infer::traits::{Obligation, SelectionError, TraitObligation};
+use rustc_middle::ty::{self, TypeFoldable};
+use rustc_target::spec::abi::Abi;
+
+use crate::traits::{util, SelectionResult};
+
+use super::BuiltinImplConditions;
+use super::SelectionCandidate::{self, *};
+use super::{SelectionCandidateSet, SelectionContext, TraitObligationStack};
+
+impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
+    pub(super) fn candidate_from_obligation<'o>(
+        &mut self,
+        stack: &TraitObligationStack<'o, 'tcx>,
+    ) -> SelectionResult<'tcx, SelectionCandidate<'tcx>> {
+        // Watch out for overflow. This intentionally bypasses (and does
+        // not update) the cache.
+        self.check_recursion_limit(&stack.obligation, &stack.obligation)?;
+
+        // Check the cache. Note that we freshen the trait-ref
+        // separately rather than using `stack.fresh_trait_ref` --
+        // this is because we want the unbound variables to be
+        // replaced with fresh types starting from index 0.
+        let cache_fresh_trait_pred = self.infcx.freshen(stack.obligation.predicate);
+        debug!(
+            "candidate_from_obligation(cache_fresh_trait_pred={:?}, obligation={:?})",
+            cache_fresh_trait_pred, stack
+        );
+        debug_assert!(!stack.obligation.predicate.has_escaping_bound_vars());
+
+        if let Some(c) =
+            self.check_candidate_cache(stack.obligation.param_env, cache_fresh_trait_pred)
+        {
+            debug!("CACHE HIT: SELECT({:?})={:?}", cache_fresh_trait_pred, c);
+            return c;
+        }
+
+        // If no match, compute result and insert into cache.
+        //
+        // FIXME(nikomatsakis) -- this cache is not taking into
+        // account cycles that may have occurred in forming the
+        // candidate. I don't know of any specific problems that
+        // result but it seems awfully suspicious.
+        let (candidate, dep_node) =
+            self.in_task(|this| this.candidate_from_obligation_no_cache(stack));
+
+        debug!("CACHE MISS: SELECT({:?})={:?}", cache_fresh_trait_pred, candidate);
+        self.insert_candidate_cache(
+            stack.obligation.param_env,
+            cache_fresh_trait_pred,
+            dep_node,
+            candidate.clone(),
+        );
+        candidate
+    }
+
+    pub(super) fn assemble_candidates<'o>(
+        &mut self,
+        stack: &TraitObligationStack<'o, 'tcx>,
+    ) -> Result<SelectionCandidateSet<'tcx>, SelectionError<'tcx>> {
+        let TraitObligationStack { obligation, .. } = *stack;
+        let obligation = &Obligation {
+            param_env: obligation.param_env,
+            cause: obligation.cause.clone(),
+            recursion_depth: obligation.recursion_depth,
+            predicate: self.infcx().resolve_vars_if_possible(&obligation.predicate),
+        };
+
+        if obligation.predicate.skip_binder().self_ty().is_ty_var() {
+            // Self is a type variable (e.g., `_: AsRef<str>`).
+            //
+            // This is somewhat problematic, as the current scheme can't really
+            // handle it turning to be a projection. This does end up as truly
+            // ambiguous in most cases anyway.
+            //
+            // Take the fast path out - this also improves
+            // performance by preventing assemble_candidates_from_impls from
+            // matching every impl for this trait.
+            return Ok(SelectionCandidateSet { vec: vec![], ambiguous: true });
+        }
+
+        let mut candidates = SelectionCandidateSet { vec: Vec::new(), ambiguous: false };
+
+        self.assemble_candidates_for_trait_alias(obligation, &mut candidates)?;
+
+        // Other bounds. Consider both in-scope bounds from fn decl
+        // and applicable impls. There is a certain set of precedence rules here.
+        let def_id = obligation.predicate.def_id();
+        let lang_items = self.tcx().lang_items();
+
+        if lang_items.copy_trait() == Some(def_id) {
+            debug!("obligation self ty is {:?}", obligation.predicate.skip_binder().self_ty());
+
+            // User-defined copy impls are permitted, but only for
+            // structs and enums.
+            self.assemble_candidates_from_impls(obligation, &mut candidates)?;
+
+            // For other types, we'll use the builtin rules.
+            let copy_conditions = self.copy_clone_conditions(obligation);
+            self.assemble_builtin_bound_candidates(copy_conditions, &mut candidates)?;
+        } else if lang_items.discriminant_kind_trait() == Some(def_id) {
+            // `DiscriminantKind` is automatically implemented for every type.
+            candidates.vec.push(DiscriminantKindCandidate);
+        } else if lang_items.sized_trait() == Some(def_id) {
+            // Sized is never implementable by end-users, it is
+            // always automatically computed.
+            let sized_conditions = self.sized_conditions(obligation);
+            self.assemble_builtin_bound_candidates(sized_conditions, &mut candidates)?;
+        } else if lang_items.unsize_trait() == Some(def_id) {
+            self.assemble_candidates_for_unsizing(obligation, &mut candidates);
+        } else {
+            if lang_items.clone_trait() == Some(def_id) {
+                // Same builtin conditions as `Copy`, i.e., every type which has builtin support
+                // for `Copy` also has builtin support for `Clone`, and tuples/arrays of `Clone`
+                // types have builtin support for `Clone`.
+                let clone_conditions = self.copy_clone_conditions(obligation);
+                self.assemble_builtin_bound_candidates(clone_conditions, &mut candidates)?;
+            }
+
+            self.assemble_generator_candidates(obligation, &mut candidates)?;
+            self.assemble_closure_candidates(obligation, &mut candidates)?;
+            self.assemble_fn_pointer_candidates(obligation, &mut candidates)?;
+            self.assemble_candidates_from_impls(obligation, &mut candidates)?;
+            self.assemble_candidates_from_object_ty(obligation, &mut candidates);
+        }
+
+        self.assemble_candidates_from_projected_tys(obligation, &mut candidates);
+        self.assemble_candidates_from_caller_bounds(stack, &mut candidates)?;
+        // Auto implementations have lower priority, so we only
+        // consider triggering a default if there is no other impl that can apply.
+        if candidates.vec.is_empty() {
+            self.assemble_candidates_from_auto_impls(obligation, &mut candidates)?;
+        }
+        debug!("candidate list size: {}", candidates.vec.len());
+        Ok(candidates)
+    }
+
+    fn assemble_candidates_from_projected_tys(
+        &mut self,
+        obligation: &TraitObligation<'tcx>,
+        candidates: &mut SelectionCandidateSet<'tcx>,
+    ) {
+        debug!("assemble_candidates_for_projected_tys({:?})", obligation);
+
+        // Before we go into the whole placeholder thing, just
+        // quickly check if the self-type is a projection at all.
+        match obligation.predicate.skip_binder().trait_ref.self_ty().kind {
+            ty::Projection(_) | ty::Opaque(..) => {}
+            ty::Infer(ty::TyVar(_)) => {
+                span_bug!(
+                    obligation.cause.span,
+                    "Self=_ should have been handled by assemble_candidates"
+                );
+            }
+            _ => return,
+        }
+
+        let result = self.infcx.probe(|snapshot| {
+            self.match_projection_obligation_against_definition_bounds(obligation, snapshot)
+        });
+
+        if result {
+            candidates.vec.push(ProjectionCandidate);
+        }
+    }
+
+    /// Given an obligation like `<SomeTrait for T>`, searches the obligations that the caller
+    /// supplied to find out whether it is listed among them.
+    ///
+    /// Never affects the inference environment.
+    fn assemble_candidates_from_caller_bounds<'o>(
+        &mut self,
+        stack: &TraitObligationStack<'o, 'tcx>,
+        candidates: &mut SelectionCandidateSet<'tcx>,
+    ) -> Result<(), SelectionError<'tcx>> {
+        debug!("assemble_candidates_from_caller_bounds({:?})", stack.obligation);
+
+        let all_bounds = stack
+            .obligation
+            .param_env
+            .caller_bounds
+            .iter()
+            .filter_map(|o| o.to_opt_poly_trait_ref());
+
+        // Micro-optimization: filter out predicates relating to different traits.
+        let matching_bounds =
+            all_bounds.filter(|p| p.def_id() == stack.obligation.predicate.def_id());
+
+        // Keep only those bounds which may apply, and propagate overflow if it occurs.
+        let mut param_candidates = vec![];
+        for bound in matching_bounds {
+            let wc = self.evaluate_where_clause(stack, bound)?;
+            if wc.may_apply() {
+                param_candidates.push(ParamCandidate(bound));
+            }
+        }
+
+        candidates.vec.extend(param_candidates);
+
+        Ok(())
+    }
+
+    fn assemble_generator_candidates(
+        &mut self,
+        obligation: &TraitObligation<'tcx>,
+        candidates: &mut SelectionCandidateSet<'tcx>,
+    ) -> Result<(), SelectionError<'tcx>> {
+        if self.tcx().lang_items().gen_trait() != Some(obligation.predicate.def_id()) {
+            return Ok(());
+        }
+
+        // Okay to skip binder because the substs on generator types never
+        // touch bound regions, they just capture the in-scope
+        // type/region parameters.
+        let self_ty = *obligation.self_ty().skip_binder();
+        match self_ty.kind {
+            ty::Generator(..) => {
+                debug!(
+                    "assemble_generator_candidates: self_ty={:?} obligation={:?}",
+                    self_ty, obligation
+                );
+
+                candidates.vec.push(GeneratorCandidate);
+            }
+            ty::Infer(ty::TyVar(_)) => {
+                debug!("assemble_generator_candidates: ambiguous self-type");
+                candidates.ambiguous = true;
+            }
+            _ => {}
+        }
+
+        Ok(())
+    }
+
+    /// Checks for the artificial impl that the compiler will create for an obligation like `X :
+    /// FnMut<..>` where `X` is a closure type.
+    ///
+    /// Note: the type parameters on a closure candidate are modeled as *output* type
+    /// parameters and hence do not affect whether this trait is a match or not. They will be
+    /// unified during the confirmation step.
+    fn assemble_closure_candidates(
+        &mut self,
+        obligation: &TraitObligation<'tcx>,
+        candidates: &mut SelectionCandidateSet<'tcx>,
+    ) -> Result<(), SelectionError<'tcx>> {
+        let kind = match self.tcx().fn_trait_kind_from_lang_item(obligation.predicate.def_id()) {
+            Some(k) => k,
+            None => {
+                return Ok(());
+            }
+        };
+
+        // Okay to skip binder because the substs on closure types never
+        // touch bound regions, they just capture the in-scope
+        // type/region parameters
+        match obligation.self_ty().skip_binder().kind {
+            ty::Closure(_, closure_substs) => {
+                debug!("assemble_unboxed_candidates: kind={:?} obligation={:?}", kind, obligation);
+                match self.infcx.closure_kind(closure_substs) {
+                    Some(closure_kind) => {
+                        debug!("assemble_unboxed_candidates: closure_kind = {:?}", closure_kind);
+                        if closure_kind.extends(kind) {
+                            candidates.vec.push(ClosureCandidate);
+                        }
+                    }
+                    None => {
+                        debug!("assemble_unboxed_candidates: closure_kind not yet known");
+                        candidates.vec.push(ClosureCandidate);
+                    }
+                }
+            }
+            ty::Infer(ty::TyVar(_)) => {
+                debug!("assemble_unboxed_closure_candidates: ambiguous self-type");
+                candidates.ambiguous = true;
+            }
+            _ => {}
+        }
+
+        Ok(())
+    }
+
+    /// Implements one of the `Fn()` family for a fn pointer.
+    fn assemble_fn_pointer_candidates(
+        &mut self,
+        obligation: &TraitObligation<'tcx>,
+        candidates: &mut SelectionCandidateSet<'tcx>,
+    ) -> Result<(), SelectionError<'tcx>> {
+        // We provide impl of all fn traits for fn pointers.
+        if self.tcx().fn_trait_kind_from_lang_item(obligation.predicate.def_id()).is_none() {
+            return Ok(());
+        }
+
+        // Okay to skip binder because what we are inspecting doesn't involve bound regions.
+        let self_ty = *obligation.self_ty().skip_binder();
+        match self_ty.kind {
+            ty::Infer(ty::TyVar(_)) => {
+                debug!("assemble_fn_pointer_candidates: ambiguous self-type");
+                candidates.ambiguous = true; // Could wind up being a fn() type.
+            }
+            // Provide an impl, but only for suitable `fn` pointers.
+            ty::FnDef(..) | ty::FnPtr(_) => {
+                if let ty::FnSig {
+                    unsafety: hir::Unsafety::Normal,
+                    abi: Abi::Rust,
+                    c_variadic: false,
+                    ..
+                } = self_ty.fn_sig(self.tcx()).skip_binder()
+                {
+                    candidates.vec.push(FnPointerCandidate);
+                }
+            }
+            _ => {}
+        }
+
+        Ok(())
+    }
+
+    /// Searches for impls that might apply to `obligation`.
+    fn assemble_candidates_from_impls(
+        &mut self,
+        obligation: &TraitObligation<'tcx>,
+        candidates: &mut SelectionCandidateSet<'tcx>,
+    ) -> Result<(), SelectionError<'tcx>> {
+        debug!("assemble_candidates_from_impls(obligation={:?})", obligation);
+
+        self.tcx().for_each_relevant_impl(
+            obligation.predicate.def_id(),
+            obligation.predicate.skip_binder().trait_ref.self_ty(),
+            |impl_def_id| {
+                self.infcx.probe(|snapshot| {
+                    if let Ok(_substs) = self.match_impl(impl_def_id, obligation, snapshot) {
+                        candidates.vec.push(ImplCandidate(impl_def_id));
+                    }
+                });
+            },
+        );
+
+        Ok(())
+    }
+
+    fn assemble_candidates_from_auto_impls(
+        &mut self,
+        obligation: &TraitObligation<'tcx>,
+        candidates: &mut SelectionCandidateSet<'tcx>,
+    ) -> Result<(), SelectionError<'tcx>> {
+        // Okay to skip binder here because the tests we do below do not involve bound regions.
+        let self_ty = *obligation.self_ty().skip_binder();
+        debug!("assemble_candidates_from_auto_impls(self_ty={:?})", self_ty);
+
+        let def_id = obligation.predicate.def_id();
+
+        if self.tcx().trait_is_auto(def_id) {
+            match self_ty.kind {
+                ty::Dynamic(..) => {
+                    // For object types, we don't know what the closed
+                    // over types are. This means we conservatively
+                    // say nothing; a candidate may be added by
+                    // `assemble_candidates_from_object_ty`.
+                }
+                ty::Foreign(..) => {
+                    // Since the contents of foreign types is unknown,
+                    // we don't add any `..` impl. Default traits could
+                    // still be provided by a manual implementation for
+                    // this trait and type.
+                }
+                ty::Param(..) | ty::Projection(..) => {
+                    // In these cases, we don't know what the actual
+                    // type is.  Therefore, we cannot break it down
+                    // into its constituent types. So we don't
+                    // consider the `..` impl but instead just add no
+                    // candidates: this means that typeck will only
+                    // succeed if there is another reason to believe
+                    // that this obligation holds. That could be a
+                    // where-clause or, in the case of an object type,
+                    // it could be that the object type lists the
+                    // trait (e.g., `Foo+Send : Send`). See
+                    // `compile-fail/typeck-default-trait-impl-send-param.rs`
+                    // for an example of a test case that exercises
+                    // this path.
+                }
+                ty::Infer(ty::TyVar(_)) => {
+                    // The auto impl might apply; we don't know.
+                    candidates.ambiguous = true;
+                }
+                ty::Generator(_, _, movability)
+                    if self.tcx().lang_items().unpin_trait() == Some(def_id) =>
+                {
+                    match movability {
+                        hir::Movability::Static => {
+                            // Immovable generators are never `Unpin`, so
+                            // suppress the normal auto-impl candidate for it.
+                        }
+                        hir::Movability::Movable => {
+                            // Movable generators are always `Unpin`, so add an
+                            // unconditional builtin candidate.
+                            candidates.vec.push(BuiltinCandidate { has_nested: false });
+                        }
+                    }
+                }
+
+                _ => candidates.vec.push(AutoImplCandidate(def_id)),
+            }
+        }
+
+        Ok(())
+    }
+
+    /// Searches for impls that might apply to `obligation`.
+    fn assemble_candidates_from_object_ty(
+        &mut self,
+        obligation: &TraitObligation<'tcx>,
+        candidates: &mut SelectionCandidateSet<'tcx>,
+    ) {
+        debug!(
+            "assemble_candidates_from_object_ty(self_ty={:?})",
+            obligation.self_ty().skip_binder()
+        );
+
+        self.infcx.probe(|_snapshot| {
+            // The code below doesn't care about regions, and the
+            // self-ty here doesn't escape this probe, so just erase
+            // any LBR.
+            let self_ty = self.tcx().erase_late_bound_regions(&obligation.self_ty());
+            let poly_trait_ref = match self_ty.kind {
+                ty::Dynamic(ref data, ..) => {
+                    if data.auto_traits().any(|did| did == obligation.predicate.def_id()) {
+                        debug!(
+                            "assemble_candidates_from_object_ty: matched builtin bound, \
+                             pushing candidate"
+                        );
+                        candidates.vec.push(BuiltinObjectCandidate);
+                        return;
+                    }
+
+                    if let Some(principal) = data.principal() {
+                        if !self.infcx.tcx.features().object_safe_for_dispatch {
+                            principal.with_self_ty(self.tcx(), self_ty)
+                        } else if self.tcx().is_object_safe(principal.def_id()) {
+                            principal.with_self_ty(self.tcx(), self_ty)
+                        } else {
+                            return;
+                        }
+                    } else {
+                        // Only auto trait bounds exist.
+                        return;
+                    }
+                }
+                ty::Infer(ty::TyVar(_)) => {
+                    debug!("assemble_candidates_from_object_ty: ambiguous");
+                    candidates.ambiguous = true; // could wind up being an object type
+                    return;
+                }
+                _ => return,
+            };
+
+            debug!("assemble_candidates_from_object_ty: poly_trait_ref={:?}", poly_trait_ref);
+
+            // Count only those upcast versions that match the trait-ref
+            // we are looking for. Specifically, do not only check for the
+            // correct trait, but also the correct type parameters.
+            // For example, we may be trying to upcast `Foo` to `Bar<i32>`,
+            // but `Foo` is declared as `trait Foo: Bar<u32>`.
+            let upcast_trait_refs = util::supertraits(self.tcx(), poly_trait_ref)
+                .filter(|upcast_trait_ref| {
+                    self.infcx
+                        .probe(|_| self.match_poly_trait_ref(obligation, *upcast_trait_ref).is_ok())
+                })
+                .count();
+
+            if upcast_trait_refs > 1 {
+                // Can be upcast in many ways; need more type information.
+                candidates.ambiguous = true;
+            } else if upcast_trait_refs == 1 {
+                candidates.vec.push(ObjectCandidate);
+            }
+        })
+    }
+
+    /// Searches for unsizing that might apply to `obligation`.
+    fn assemble_candidates_for_unsizing(
+        &mut self,
+        obligation: &TraitObligation<'tcx>,
+        candidates: &mut SelectionCandidateSet<'tcx>,
+    ) {
+        // We currently never consider higher-ranked obligations e.g.
+        // `for<'a> &'a T: Unsize<Trait+'a>` to be implemented. This is not
+        // because they are a priori invalid, and we could potentially add support
+        // for them later, it's just that there isn't really a strong need for it.
+        // A `T: Unsize<U>` obligation is always used as part of a `T: CoerceUnsize<U>`
+        // impl, and those are generally applied to concrete types.
+        //
+        // That said, one might try to write a fn with a where clause like
+        //     for<'a> Foo<'a, T>: Unsize<Foo<'a, Trait>>
+        // where the `'a` is kind of orthogonal to the relevant part of the `Unsize`.
+        // Still, you'd be more likely to write that where clause as
+        //     T: Trait
+        // so it seems ok if we (conservatively) fail to accept that `Unsize`
+        // obligation above. Should be possible to extend this in the future.
+        let source = match obligation.self_ty().no_bound_vars() {
+            Some(t) => t,
+            None => {
+                // Don't add any candidates if there are bound regions.
+                return;
+            }
+        };
+        let target = obligation.predicate.skip_binder().trait_ref.substs.type_at(1);
+
+        debug!("assemble_candidates_for_unsizing(source={:?}, target={:?})", source, target);
+
+        let may_apply = match (&source.kind, &target.kind) {
+            // Trait+Kx+'a -> Trait+Ky+'b (upcasts).
+            (&ty::Dynamic(ref data_a, ..), &ty::Dynamic(ref data_b, ..)) => {
+                // Upcasts permit two things:
+                //
+                // 1. Dropping auto traits, e.g., `Foo + Send` to `Foo`
+                // 2. Tightening the region bound, e.g., `Foo + 'a` to `Foo + 'b` if `'a: 'b`
+                //
+                // Note that neither of these changes requires any
+                // change at runtime. Eventually this will be
+                // generalized.
+                //
+                // We always upcast when we can because of reason
+                // #2 (region bounds).
+                data_a.principal_def_id() == data_b.principal_def_id()
+                    && data_b
+                        .auto_traits()
+                        // All of a's auto traits need to be in b's auto traits.
+                        .all(|b| data_a.auto_traits().any(|a| a == b))
+            }
+
+            // `T` -> `Trait`
+            (_, &ty::Dynamic(..)) => true,
+
+            // Ambiguous handling is below `T` -> `Trait`, because inference
+            // variables can still implement `Unsize<Trait>` and nested
+            // obligations will have the final say (likely deferred).
+            (&ty::Infer(ty::TyVar(_)), _) | (_, &ty::Infer(ty::TyVar(_))) => {
+                debug!("assemble_candidates_for_unsizing: ambiguous");
+                candidates.ambiguous = true;
+                false
+            }
+
+            // `[T; n]` -> `[T]`
+            (&ty::Array(..), &ty::Slice(_)) => true,
+
+            // `Struct<T>` -> `Struct<U>`
+            (&ty::Adt(def_id_a, _), &ty::Adt(def_id_b, _)) if def_id_a.is_struct() => {
+                def_id_a == def_id_b
+            }
+
+            // `(.., T)` -> `(.., U)`
+            (&ty::Tuple(tys_a), &ty::Tuple(tys_b)) => tys_a.len() == tys_b.len(),
+
+            _ => false,
+        };
+
+        if may_apply {
+            candidates.vec.push(BuiltinUnsizeCandidate);
+        }
+    }
+
+    fn assemble_candidates_for_trait_alias(
+        &mut self,
+        obligation: &TraitObligation<'tcx>,
+        candidates: &mut SelectionCandidateSet<'tcx>,
+    ) -> Result<(), SelectionError<'tcx>> {
+        // Okay to skip binder here because the tests we do below do not involve bound regions.
+        let self_ty = *obligation.self_ty().skip_binder();
+        debug!("assemble_candidates_for_trait_alias(self_ty={:?})", self_ty);
+
+        let def_id = obligation.predicate.def_id();
+
+        if self.tcx().is_trait_alias(def_id) {
+            candidates.vec.push(TraitAliasCandidate(def_id));
+        }
+
+        Ok(())
+    }
+
+    /// Assembles the trait which are built-in to the language itself:
+    /// `Copy`, `Clone` and `Sized`.
+    fn assemble_builtin_bound_candidates(
+        &mut self,
+        conditions: BuiltinImplConditions<'tcx>,
+        candidates: &mut SelectionCandidateSet<'tcx>,
+    ) -> Result<(), SelectionError<'tcx>> {
+        match conditions {
+            BuiltinImplConditions::Where(nested) => {
+                debug!("builtin_bound: nested={:?}", nested);
+                candidates
+                    .vec
+                    .push(BuiltinCandidate { has_nested: !nested.skip_binder().is_empty() });
+            }
+            BuiltinImplConditions::None => {}
+            BuiltinImplConditions::Ambiguous => {
+                debug!("assemble_builtin_bound_candidates: ambiguous builtin");
+                candidates.ambiguous = true;
+            }
+        }
+
+        Ok(())
+    }
+}
diff --git a/src/librustc_trait_selection/traits/select/confirmation.rs b/src/librustc_trait_selection/traits/select/confirmation.rs
new file mode 100644
index 00000000000..65bb9b7cda9
--- /dev/null
+++ b/src/librustc_trait_selection/traits/select/confirmation.rs
@@ -0,0 +1,820 @@
+//! Confirmation.
+//!
+//! Confirmation unifies the output type parameters of the trait
+//! with the values found in the obligation, possibly yielding a
+//! type error.  See the [rustc dev guide] for more details.
+//!
+//! [rustc dev guide]:
+//! https://rustc-dev-guide.rust-lang.org/traits/resolution.html#confirmation
+use rustc_data_structures::stack::ensure_sufficient_stack;
+use rustc_hir::lang_items;
+use rustc_index::bit_set::GrowableBitSet;
+use rustc_infer::infer::InferOk;
+use rustc_middle::ty::subst::{GenericArg, GenericArgKind, Subst, SubstsRef};
+use rustc_middle::ty::{self, Ty};
+use rustc_middle::ty::{ToPolyTraitRef, ToPredicate, WithConstness};
+use rustc_span::def_id::DefId;
+
+use crate::traits::project::{self, normalize_with_depth};
+use crate::traits::select::TraitObligationExt;
+use crate::traits::util;
+use crate::traits::util::{closure_trait_ref_and_return_type, predicate_for_trait_def};
+use crate::traits::Normalized;
+use crate::traits::OutputTypeParameterMismatch;
+use crate::traits::Selection;
+use crate::traits::TraitNotObjectSafe;
+use crate::traits::{BuiltinDerivedObligation, ImplDerivedObligation};
+use crate::traits::{ObjectCastObligation, PredicateObligation, TraitObligation};
+use crate::traits::{Obligation, ObligationCause};
+use crate::traits::{SelectionError, Unimplemented};
+use crate::traits::{
+    VtableAutoImpl, VtableBuiltin, VtableClosure, VtableDiscriminantKind, VtableFnPointer,
+    VtableGenerator, VtableImpl, VtableObject, VtableParam, VtableTraitAlias,
+};
+use crate::traits::{
+    VtableAutoImplData, VtableBuiltinData, VtableClosureData, VtableDiscriminantKindData,
+    VtableFnPointerData, VtableGeneratorData, VtableImplData, VtableObjectData,
+    VtableTraitAliasData,
+};
+
+use super::BuiltinImplConditions;
+use super::SelectionCandidate::{self, *};
+use super::SelectionContext;
+
+use std::iter;
+
+impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
+    pub(super) fn confirm_candidate(
+        &mut self,
+        obligation: &TraitObligation<'tcx>,
+        candidate: SelectionCandidate<'tcx>,
+    ) -> Result<Selection<'tcx>, SelectionError<'tcx>> {
+        debug!("confirm_candidate({:?}, {:?})", obligation, candidate);
+
+        match candidate {
+            BuiltinCandidate { has_nested } => {
+                let data = self.confirm_builtin_candidate(obligation, has_nested);
+                Ok(VtableBuiltin(data))
+            }
+
+            ParamCandidate(param) => {
+                let obligations = self.confirm_param_candidate(obligation, param);
+                Ok(VtableParam(obligations))
+            }
+
+            ImplCandidate(impl_def_id) => {
+                Ok(VtableImpl(self.confirm_impl_candidate(obligation, impl_def_id)))
+            }
+
+            AutoImplCandidate(trait_def_id) => {
+                let data = self.confirm_auto_impl_candidate(obligation, trait_def_id);
+                Ok(VtableAutoImpl(data))
+            }
+
+            ProjectionCandidate => {
+                self.confirm_projection_candidate(obligation);
+                Ok(VtableParam(Vec::new()))
+            }
+
+            ClosureCandidate => {
+                let vtable_closure = self.confirm_closure_candidate(obligation)?;
+                Ok(VtableClosure(vtable_closure))
+            }
+
+            GeneratorCandidate => {
+                let vtable_generator = self.confirm_generator_candidate(obligation)?;
+                Ok(VtableGenerator(vtable_generator))
+            }
+
+            FnPointerCandidate => {
+                let data = self.confirm_fn_pointer_candidate(obligation)?;
+                Ok(VtableFnPointer(data))
+            }
+
+            DiscriminantKindCandidate => Ok(VtableDiscriminantKind(VtableDiscriminantKindData)),
+
+            TraitAliasCandidate(alias_def_id) => {
+                let data = self.confirm_trait_alias_candidate(obligation, alias_def_id);
+                Ok(VtableTraitAlias(data))
+            }
+
+            ObjectCandidate => {
+                let data = self.confirm_object_candidate(obligation);
+                Ok(VtableObject(data))
+            }
+
+            BuiltinObjectCandidate => {
+                // This indicates something like `Trait + Send: Send`. In this case, we know that
+                // this holds because that's what the object type is telling us, and there's really
+                // no additional obligations to prove and no types in particular to unify, etc.
+                Ok(VtableParam(Vec::new()))
+            }
+
+            BuiltinUnsizeCandidate => {
+                let data = self.confirm_builtin_unsize_candidate(obligation)?;
+                Ok(VtableBuiltin(data))
+            }
+        }
+    }
+
+    fn confirm_projection_candidate(&mut self, obligation: &TraitObligation<'tcx>) {
+        self.infcx.commit_unconditionally(|snapshot| {
+            let result =
+                self.match_projection_obligation_against_definition_bounds(obligation, snapshot);
+            assert!(result);
+        })
+    }
+
+    fn confirm_param_candidate(
+        &mut self,
+        obligation: &TraitObligation<'tcx>,
+        param: ty::PolyTraitRef<'tcx>,
+    ) -> Vec<PredicateObligation<'tcx>> {
+        debug!("confirm_param_candidate({:?},{:?})", obligation, param);
+
+        // During evaluation, we already checked that this
+        // where-clause trait-ref could be unified with the obligation
+        // trait-ref. Repeat that unification now without any
+        // transactional boundary; it should not fail.
+        match self.match_where_clause_trait_ref(obligation, param) {
+            Ok(obligations) => obligations,
+            Err(()) => {
+                bug!(
+                    "Where clause `{:?}` was applicable to `{:?}` but now is not",
+                    param,
+                    obligation
+                );
+            }
+        }
+    }
+
+    fn confirm_builtin_candidate(
+        &mut self,
+        obligation: &TraitObligation<'tcx>,
+        has_nested: bool,
+    ) -> VtableBuiltinData<PredicateObligation<'tcx>> {
+        debug!("confirm_builtin_candidate({:?}, {:?})", obligation, has_nested);
+
+        let lang_items = self.tcx().lang_items();
+        let obligations = if has_nested {
+            let trait_def = obligation.predicate.def_id();
+            let conditions = if Some(trait_def) == lang_items.sized_trait() {
+                self.sized_conditions(obligation)
+            } else if Some(trait_def) == lang_items.copy_trait() {
+                self.copy_clone_conditions(obligation)
+            } else if Some(trait_def) == lang_items.clone_trait() {
+                self.copy_clone_conditions(obligation)
+            } else {
+                bug!("unexpected builtin trait {:?}", trait_def)
+            };
+            let nested = match conditions {
+                BuiltinImplConditions::Where(nested) => nested,
+                _ => bug!("obligation {:?} had matched a builtin impl but now doesn't", obligation),
+            };
+
+            let cause = obligation.derived_cause(BuiltinDerivedObligation);
+            ensure_sufficient_stack(|| {
+                self.collect_predicates_for_types(
+                    obligation.param_env,
+                    cause,
+                    obligation.recursion_depth + 1,
+                    trait_def,
+                    nested,
+                )
+            })
+        } else {
+            vec![]
+        };
+
+        debug!("confirm_builtin_candidate: obligations={:?}", obligations);
+
+        VtableBuiltinData { nested: obligations }
+    }
+
+    /// This handles the case where a `auto trait Foo` impl is being used.
+    /// The idea is that the impl applies to `X : Foo` if the following conditions are met:
+    ///
+    /// 1. For each constituent type `Y` in `X`, `Y : Foo` holds
+    /// 2. For each where-clause `C` declared on `Foo`, `[Self => X] C` holds.
+    fn confirm_auto_impl_candidate(
+        &mut self,
+        obligation: &TraitObligation<'tcx>,
+        trait_def_id: DefId,
+    ) -> VtableAutoImplData<PredicateObligation<'tcx>> {
+        debug!("confirm_auto_impl_candidate({:?}, {:?})", obligation, trait_def_id);
+
+        let types = obligation.predicate.map_bound(|inner| {
+            let self_ty = self.infcx.shallow_resolve(inner.self_ty());
+            self.constituent_types_for_ty(self_ty)
+        });
+        self.vtable_auto_impl(obligation, trait_def_id, types)
+    }
+
+    /// See `confirm_auto_impl_candidate`.
+    fn vtable_auto_impl(
+        &mut self,
+        obligation: &TraitObligation<'tcx>,
+        trait_def_id: DefId,
+        nested: ty::Binder<Vec<Ty<'tcx>>>,
+    ) -> VtableAutoImplData<PredicateObligation<'tcx>> {
+        debug!("vtable_auto_impl: nested={:?}", nested);
+        ensure_sufficient_stack(|| {
+            let cause = obligation.derived_cause(BuiltinDerivedObligation);
+            let mut obligations = self.collect_predicates_for_types(
+                obligation.param_env,
+                cause,
+                obligation.recursion_depth + 1,
+                trait_def_id,
+                nested,
+            );
+
+            let trait_obligations: Vec<PredicateObligation<'_>> =
+                self.infcx.commit_unconditionally(|_| {
+                    let poly_trait_ref = obligation.predicate.to_poly_trait_ref();
+                    let (trait_ref, _) =
+                        self.infcx.replace_bound_vars_with_placeholders(&poly_trait_ref);
+                    let cause = obligation.derived_cause(ImplDerivedObligation);
+                    self.impl_or_trait_obligations(
+                        cause,
+                        obligation.recursion_depth + 1,
+                        obligation.param_env,
+                        trait_def_id,
+                        &trait_ref.substs,
+                    )
+                });
+
+            // Adds the predicates from the trait.  Note that this contains a `Self: Trait`
+            // predicate as usual.  It won't have any effect since auto traits are coinductive.
+            obligations.extend(trait_obligations);
+
+            debug!("vtable_auto_impl: obligations={:?}", obligations);
+
+            VtableAutoImplData { trait_def_id, nested: obligations }
+        })
+    }
+
+    fn confirm_impl_candidate(
+        &mut self,
+        obligation: &TraitObligation<'tcx>,
+        impl_def_id: DefId,
+    ) -> VtableImplData<'tcx, PredicateObligation<'tcx>> {
+        debug!("confirm_impl_candidate({:?},{:?})", obligation, impl_def_id);
+
+        // First, create the substitutions by matching the impl again,
+        // this time not in a probe.
+        self.infcx.commit_unconditionally(|snapshot| {
+            let substs = self.rematch_impl(impl_def_id, obligation, snapshot);
+            debug!("confirm_impl_candidate: substs={:?}", substs);
+            let cause = obligation.derived_cause(ImplDerivedObligation);
+            ensure_sufficient_stack(|| {
+                self.vtable_impl(
+                    impl_def_id,
+                    substs,
+                    cause,
+                    obligation.recursion_depth + 1,
+                    obligation.param_env,
+                )
+            })
+        })
+    }
+
+    fn vtable_impl(
+        &mut self,
+        impl_def_id: DefId,
+        mut substs: Normalized<'tcx, SubstsRef<'tcx>>,
+        cause: ObligationCause<'tcx>,
+        recursion_depth: usize,
+        param_env: ty::ParamEnv<'tcx>,
+    ) -> VtableImplData<'tcx, PredicateObligation<'tcx>> {
+        debug!(
+            "vtable_impl(impl_def_id={:?}, substs={:?}, recursion_depth={})",
+            impl_def_id, substs, recursion_depth,
+        );
+
+        let mut impl_obligations = self.impl_or_trait_obligations(
+            cause,
+            recursion_depth,
+            param_env,
+            impl_def_id,
+            &substs.value,
+        );
+
+        debug!(
+            "vtable_impl: impl_def_id={:?} impl_obligations={:?}",
+            impl_def_id, impl_obligations
+        );
+
+        // Because of RFC447, the impl-trait-ref and obligations
+        // are sufficient to determine the impl substs, without
+        // relying on projections in the impl-trait-ref.
+        //
+        // e.g., `impl<U: Tr, V: Iterator<Item=U>> Foo<<U as Tr>::T> for V`
+        impl_obligations.append(&mut substs.obligations);
+
+        VtableImplData { impl_def_id, substs: substs.value, nested: impl_obligations }
+    }
+
+    fn confirm_object_candidate(
+        &mut self,
+        obligation: &TraitObligation<'tcx>,
+    ) -> VtableObjectData<'tcx, PredicateObligation<'tcx>> {
+        debug!("confirm_object_candidate({:?})", obligation);
+
+        // FIXME(nmatsakis) skipping binder here seems wrong -- we should
+        // probably flatten the binder from the obligation and the binder
+        // from the object. Have to try to make a broken test case that
+        // results.
+        let self_ty = self.infcx.shallow_resolve(*obligation.self_ty().skip_binder());
+        let poly_trait_ref = match self_ty.kind {
+            ty::Dynamic(ref data, ..) => data
+                .principal()
+                .unwrap_or_else(|| {
+                    span_bug!(obligation.cause.span, "object candidate with no principal")
+                })
+                .with_self_ty(self.tcx(), self_ty),
+            _ => span_bug!(obligation.cause.span, "object candidate with non-object"),
+        };
+
+        let mut upcast_trait_ref = None;
+        let mut nested = vec![];
+        let vtable_base;
+
+        {
+            let tcx = self.tcx();
+
+            // We want to find the first supertrait in the list of
+            // supertraits that we can unify with, and do that
+            // unification. We know that there is exactly one in the list
+            // where we can unify, because otherwise select would have
+            // reported an ambiguity. (When we do find a match, also
+            // record it for later.)
+            let nonmatching = util::supertraits(tcx, poly_trait_ref).take_while(|&t| {
+                match self.infcx.commit_if_ok(|_| self.match_poly_trait_ref(obligation, t)) {
+                    Ok(obligations) => {
+                        upcast_trait_ref = Some(t);
+                        nested.extend(obligations);
+                        false
+                    }
+                    Err(_) => true,
+                }
+            });
+
+            // Additionally, for each of the non-matching predicates that
+            // we pass over, we sum up the set of number of vtable
+            // entries, so that we can compute the offset for the selected
+            // trait.
+            vtable_base = nonmatching.map(|t| super::util::count_own_vtable_entries(tcx, t)).sum();
+        }
+
+        VtableObjectData { upcast_trait_ref: upcast_trait_ref.unwrap(), vtable_base, nested }
+    }
+
+    fn confirm_fn_pointer_candidate(
+        &mut self,
+        obligation: &TraitObligation<'tcx>,
+    ) -> Result<VtableFnPointerData<'tcx, PredicateObligation<'tcx>>, SelectionError<'tcx>> {
+        debug!("confirm_fn_pointer_candidate({:?})", obligation);
+
+        // Okay to skip binder; it is reintroduced below.
+        let self_ty = self.infcx.shallow_resolve(*obligation.self_ty().skip_binder());
+        let sig = self_ty.fn_sig(self.tcx());
+        let trait_ref = closure_trait_ref_and_return_type(
+            self.tcx(),
+            obligation.predicate.def_id(),
+            self_ty,
+            sig,
+            util::TupleArgumentsFlag::Yes,
+        )
+        .map_bound(|(trait_ref, _)| trait_ref);
+
+        let Normalized { value: trait_ref, obligations } = ensure_sufficient_stack(|| {
+            project::normalize_with_depth(
+                self,
+                obligation.param_env,
+                obligation.cause.clone(),
+                obligation.recursion_depth + 1,
+                &trait_ref,
+            )
+        });
+
+        self.confirm_poly_trait_refs(
+            obligation.cause.clone(),
+            obligation.param_env,
+            obligation.predicate.to_poly_trait_ref(),
+            trait_ref,
+        )?;
+        Ok(VtableFnPointerData { fn_ty: self_ty, nested: obligations })
+    }
+
+    fn confirm_trait_alias_candidate(
+        &mut self,
+        obligation: &TraitObligation<'tcx>,
+        alias_def_id: DefId,
+    ) -> VtableTraitAliasData<'tcx, PredicateObligation<'tcx>> {
+        debug!("confirm_trait_alias_candidate({:?}, {:?})", obligation, alias_def_id);
+
+        self.infcx.commit_unconditionally(|_| {
+            let (predicate, _) =
+                self.infcx().replace_bound_vars_with_placeholders(&obligation.predicate);
+            let trait_ref = predicate.trait_ref;
+            let trait_def_id = trait_ref.def_id;
+            let substs = trait_ref.substs;
+
+            let trait_obligations = self.impl_or_trait_obligations(
+                obligation.cause.clone(),
+                obligation.recursion_depth,
+                obligation.param_env,
+                trait_def_id,
+                &substs,
+            );
+
+            debug!(
+                "confirm_trait_alias_candidate: trait_def_id={:?} trait_obligations={:?}",
+                trait_def_id, trait_obligations
+            );
+
+            VtableTraitAliasData { alias_def_id, substs, nested: trait_obligations }
+        })
+    }
+
+    fn confirm_generator_candidate(
+        &mut self,
+        obligation: &TraitObligation<'tcx>,
+    ) -> Result<VtableGeneratorData<'tcx, PredicateObligation<'tcx>>, SelectionError<'tcx>> {
+        // Okay to skip binder because the substs on generator types never
+        // touch bound regions, they just capture the in-scope
+        // type/region parameters.
+        let self_ty = self.infcx.shallow_resolve(*obligation.self_ty().skip_binder());
+        let (generator_def_id, substs) = match self_ty.kind {
+            ty::Generator(id, substs, _) => (id, substs),
+            _ => bug!("closure candidate for non-closure {:?}", obligation),
+        };
+
+        debug!("confirm_generator_candidate({:?},{:?},{:?})", obligation, generator_def_id, substs);
+
+        let trait_ref = self.generator_trait_ref_unnormalized(obligation, substs);
+        let Normalized { value: trait_ref, mut obligations } = ensure_sufficient_stack(|| {
+            normalize_with_depth(
+                self,
+                obligation.param_env,
+                obligation.cause.clone(),
+                obligation.recursion_depth + 1,
+                &trait_ref,
+            )
+        });
+
+        debug!(
+            "confirm_generator_candidate(generator_def_id={:?}, \
+             trait_ref={:?}, obligations={:?})",
+            generator_def_id, trait_ref, obligations
+        );
+
+        obligations.extend(self.confirm_poly_trait_refs(
+            obligation.cause.clone(),
+            obligation.param_env,
+            obligation.predicate.to_poly_trait_ref(),
+            trait_ref,
+        )?);
+
+        Ok(VtableGeneratorData { generator_def_id, substs, nested: obligations })
+    }
+
+    fn confirm_closure_candidate(
+        &mut self,
+        obligation: &TraitObligation<'tcx>,
+    ) -> Result<VtableClosureData<'tcx, PredicateObligation<'tcx>>, SelectionError<'tcx>> {
+        debug!("confirm_closure_candidate({:?})", obligation);
+
+        let kind = self
+            .tcx()
+            .fn_trait_kind_from_lang_item(obligation.predicate.def_id())
+            .unwrap_or_else(|| bug!("closure candidate for non-fn trait {:?}", obligation));
+
+        // Okay to skip binder because the substs on closure types never
+        // touch bound regions, they just capture the in-scope
+        // type/region parameters.
+        let self_ty = self.infcx.shallow_resolve(*obligation.self_ty().skip_binder());
+        let (closure_def_id, substs) = match self_ty.kind {
+            ty::Closure(id, substs) => (id, substs),
+            _ => bug!("closure candidate for non-closure {:?}", obligation),
+        };
+
+        let trait_ref = self.closure_trait_ref_unnormalized(obligation, substs);
+        let Normalized { value: trait_ref, mut obligations } = ensure_sufficient_stack(|| {
+            normalize_with_depth(
+                self,
+                obligation.param_env,
+                obligation.cause.clone(),
+                obligation.recursion_depth + 1,
+                &trait_ref,
+            )
+        });
+
+        debug!(
+            "confirm_closure_candidate(closure_def_id={:?}, trait_ref={:?}, obligations={:?})",
+            closure_def_id, trait_ref, obligations
+        );
+
+        obligations.extend(self.confirm_poly_trait_refs(
+            obligation.cause.clone(),
+            obligation.param_env,
+            obligation.predicate.to_poly_trait_ref(),
+            trait_ref,
+        )?);
+
+        // FIXME: Chalk
+
+        if !self.tcx().sess.opts.debugging_opts.chalk {
+            obligations.push(Obligation::new(
+                obligation.cause.clone(),
+                obligation.param_env,
+                ty::PredicateKind::ClosureKind(closure_def_id, substs, kind)
+                    .to_predicate(self.tcx()),
+            ));
+        }
+
+        Ok(VtableClosureData { closure_def_id, substs, nested: obligations })
+    }
+
+    /// In the case of closure types and fn pointers,
+    /// we currently treat the input type parameters on the trait as
+    /// outputs. This means that when we have a match we have only
+    /// considered the self type, so we have to go back and make sure
+    /// to relate the argument types too. This is kind of wrong, but
+    /// since we control the full set of impls, also not that wrong,
+    /// and it DOES yield better error messages (since we don't report
+    /// errors as if there is no applicable impl, but rather report
+    /// errors are about mismatched argument types.
+    ///
+    /// Here is an example. Imagine we have a closure expression
+    /// and we desugared it so that the type of the expression is
+    /// `Closure`, and `Closure` expects an int as argument. Then it
+    /// is "as if" the compiler generated this impl:
+    ///
+    ///     impl Fn(int) for Closure { ... }
+    ///
+    /// Now imagine our obligation is `Fn(usize) for Closure`. So far
+    /// we have matched the self type `Closure`. At this point we'll
+    /// compare the `int` to `usize` and generate an error.
+    ///
+    /// Note that this checking occurs *after* the impl has selected,
+    /// because these output type parameters should not affect the
+    /// selection of the impl. Therefore, if there is a mismatch, we
+    /// report an error to the user.
+    fn confirm_poly_trait_refs(
+        &mut self,
+        obligation_cause: ObligationCause<'tcx>,
+        obligation_param_env: ty::ParamEnv<'tcx>,
+        obligation_trait_ref: ty::PolyTraitRef<'tcx>,
+        expected_trait_ref: ty::PolyTraitRef<'tcx>,
+    ) -> Result<Vec<PredicateObligation<'tcx>>, SelectionError<'tcx>> {
+        self.infcx
+            .at(&obligation_cause, obligation_param_env)
+            .sup(obligation_trait_ref, expected_trait_ref)
+            .map(|InferOk { obligations, .. }| obligations)
+            .map_err(|e| OutputTypeParameterMismatch(expected_trait_ref, obligation_trait_ref, e))
+    }
+
+    fn confirm_builtin_unsize_candidate(
+        &mut self,
+        obligation: &TraitObligation<'tcx>,
+    ) -> Result<VtableBuiltinData<PredicateObligation<'tcx>>, SelectionError<'tcx>> {
+        let tcx = self.tcx();
+
+        // `assemble_candidates_for_unsizing` should ensure there are no late-bound
+        // regions here. See the comment there for more details.
+        let source = self.infcx.shallow_resolve(obligation.self_ty().no_bound_vars().unwrap());
+        let target = obligation.predicate.skip_binder().trait_ref.substs.type_at(1);
+        let target = self.infcx.shallow_resolve(target);
+
+        debug!("confirm_builtin_unsize_candidate(source={:?}, target={:?})", source, target);
+
+        let mut nested = vec![];
+        match (&source.kind, &target.kind) {
+            // Trait+Kx+'a -> Trait+Ky+'b (upcasts).
+            (&ty::Dynamic(ref data_a, r_a), &ty::Dynamic(ref data_b, r_b)) => {
+                // See `assemble_candidates_for_unsizing` for more info.
+                let existential_predicates = data_a.map_bound(|data_a| {
+                    let iter = data_a
+                        .principal()
+                        .map(ty::ExistentialPredicate::Trait)
+                        .into_iter()
+                        .chain(data_a.projection_bounds().map(ty::ExistentialPredicate::Projection))
+                        .chain(data_b.auto_traits().map(ty::ExistentialPredicate::AutoTrait));
+                    tcx.mk_existential_predicates(iter)
+                });
+                let source_trait = tcx.mk_dynamic(existential_predicates, r_b);
+
+                // Require that the traits involved in this upcast are **equal**;
+                // only the **lifetime bound** is changed.
+                //
+                // FIXME: This condition is arguably too strong -- it would
+                // suffice for the source trait to be a *subtype* of the target
+                // trait. In particular, changing from something like
+                // `for<'a, 'b> Foo<'a, 'b>` to `for<'a> Foo<'a, 'a>` should be
+                // permitted. And, indeed, in the in commit
+                // 904a0bde93f0348f69914ee90b1f8b6e4e0d7cbc, this
+                // condition was loosened. However, when the leak check was
+                // added back, using subtype here actually guides the coercion
+                // code in such a way that it accepts `old-lub-glb-object.rs`.
+                // This is probably a good thing, but I've modified this to `.eq`
+                // because I want to continue rejecting that test (as we have
+                // done for quite some time) before we are firmly comfortable
+                // with what our behavior should be there. -nikomatsakis
+                let InferOk { obligations, .. } = self
+                    .infcx
+                    .at(&obligation.cause, obligation.param_env)
+                    .eq(target, source_trait) // FIXME -- see below
+                    .map_err(|_| Unimplemented)?;
+                nested.extend(obligations);
+
+                // Register one obligation for 'a: 'b.
+                let cause = ObligationCause::new(
+                    obligation.cause.span,
+                    obligation.cause.body_id,
+                    ObjectCastObligation(target),
+                );
+                let outlives = ty::OutlivesPredicate(r_a, r_b);
+                nested.push(Obligation::with_depth(
+                    cause,
+                    obligation.recursion_depth + 1,
+                    obligation.param_env,
+                    ty::Binder::bind(outlives).to_predicate(tcx),
+                ));
+            }
+
+            // `T` -> `Trait`
+            (_, &ty::Dynamic(ref data, r)) => {
+                let mut object_dids = data.auto_traits().chain(data.principal_def_id());
+                if let Some(did) = object_dids.find(|did| !tcx.is_object_safe(*did)) {
+                    return Err(TraitNotObjectSafe(did));
+                }
+
+                let cause = ObligationCause::new(
+                    obligation.cause.span,
+                    obligation.cause.body_id,
+                    ObjectCastObligation(target),
+                );
+
+                let predicate_to_obligation = |predicate| {
+                    Obligation::with_depth(
+                        cause.clone(),
+                        obligation.recursion_depth + 1,
+                        obligation.param_env,
+                        predicate,
+                    )
+                };
+
+                // Create obligations:
+                //  - Casting `T` to `Trait`
+                //  - For all the various builtin bounds attached to the object cast. (In other
+                //  words, if the object type is `Foo + Send`, this would create an obligation for
+                //  the `Send` check.)
+                //  - Projection predicates
+                nested.extend(
+                    data.iter().map(|predicate| {
+                        predicate_to_obligation(predicate.with_self_ty(tcx, source))
+                    }),
+                );
+
+                // We can only make objects from sized types.
+                let tr = ty::TraitRef::new(
+                    tcx.require_lang_item(lang_items::SizedTraitLangItem, None),
+                    tcx.mk_substs_trait(source, &[]),
+                );
+                nested.push(predicate_to_obligation(tr.without_const().to_predicate(tcx)));
+
+                // If the type is `Foo + 'a`, ensure that the type
+                // being cast to `Foo + 'a` outlives `'a`:
+                let outlives = ty::OutlivesPredicate(source, r);
+                nested.push(predicate_to_obligation(ty::Binder::dummy(outlives).to_predicate(tcx)));
+            }
+
+            // `[T; n]` -> `[T]`
+            (&ty::Array(a, _), &ty::Slice(b)) => {
+                let InferOk { obligations, .. } = self
+                    .infcx
+                    .at(&obligation.cause, obligation.param_env)
+                    .eq(b, a)
+                    .map_err(|_| Unimplemented)?;
+                nested.extend(obligations);
+            }
+
+            // `Struct<T>` -> `Struct<U>`
+            (&ty::Adt(def, substs_a), &ty::Adt(_, substs_b)) => {
+                let maybe_unsizing_param_idx = |arg: GenericArg<'tcx>| match arg.unpack() {
+                    GenericArgKind::Type(ty) => match ty.kind {
+                        ty::Param(p) => Some(p.index),
+                        _ => None,
+                    },
+
+                    // Lifetimes aren't allowed to change during unsizing.
+                    GenericArgKind::Lifetime(_) => None,
+
+                    GenericArgKind::Const(ct) => match ct.val {
+                        ty::ConstKind::Param(p) => Some(p.index),
+                        _ => None,
+                    },
+                };
+
+                // The last field of the structure has to exist and contain type/const parameters.
+                let (tail_field, prefix_fields) =
+                    def.non_enum_variant().fields.split_last().ok_or(Unimplemented)?;
+                let tail_field_ty = tcx.type_of(tail_field.did);
+
+                let mut unsizing_params = GrowableBitSet::new_empty();
+                let mut found = false;
+                for arg in tail_field_ty.walk() {
+                    if let Some(i) = maybe_unsizing_param_idx(arg) {
+                        unsizing_params.insert(i);
+                        found = true;
+                    }
+                }
+                if !found {
+                    return Err(Unimplemented);
+                }
+
+                // Ensure none of the other fields mention the parameters used
+                // in unsizing.
+                // FIXME(eddyb) cache this (including computing `unsizing_params`)
+                // by putting it in a query; it would only need the `DefId` as it
+                // looks at declared field types, not anything substituted.
+                for field in prefix_fields {
+                    for arg in tcx.type_of(field.did).walk() {
+                        if let Some(i) = maybe_unsizing_param_idx(arg) {
+                            if unsizing_params.contains(i) {
+                                return Err(Unimplemented);
+                            }
+                        }
+                    }
+                }
+
+                // Extract `TailField<T>` and `TailField<U>` from `Struct<T>` and `Struct<U>`.
+                let source_tail = tail_field_ty.subst(tcx, substs_a);
+                let target_tail = tail_field_ty.subst(tcx, substs_b);
+
+                // Check that the source struct with the target's
+                // unsizing parameters is equal to the target.
+                let substs = tcx.mk_substs(substs_a.iter().enumerate().map(|(i, k)| {
+                    if unsizing_params.contains(i as u32) { substs_b[i] } else { k }
+                }));
+                let new_struct = tcx.mk_adt(def, substs);
+                let InferOk { obligations, .. } = self
+                    .infcx
+                    .at(&obligation.cause, obligation.param_env)
+                    .eq(target, new_struct)
+                    .map_err(|_| Unimplemented)?;
+                nested.extend(obligations);
+
+                // Construct the nested `TailField<T>: Unsize<TailField<U>>` predicate.
+                nested.push(predicate_for_trait_def(
+                    tcx,
+                    obligation.param_env,
+                    obligation.cause.clone(),
+                    obligation.predicate.def_id(),
+                    obligation.recursion_depth + 1,
+                    source_tail,
+                    &[target_tail.into()],
+                ));
+            }
+
+            // `(.., T)` -> `(.., U)`
+            (&ty::Tuple(tys_a), &ty::Tuple(tys_b)) => {
+                assert_eq!(tys_a.len(), tys_b.len());
+
+                // The last field of the tuple has to exist.
+                let (&a_last, a_mid) = tys_a.split_last().ok_or(Unimplemented)?;
+                let &b_last = tys_b.last().unwrap();
+
+                // Check that the source tuple with the target's
+                // last element is equal to the target.
+                let new_tuple = tcx.mk_tup(
+                    a_mid.iter().map(|k| k.expect_ty()).chain(iter::once(b_last.expect_ty())),
+                );
+                let InferOk { obligations, .. } = self
+                    .infcx
+                    .at(&obligation.cause, obligation.param_env)
+                    .eq(target, new_tuple)
+                    .map_err(|_| Unimplemented)?;
+                nested.extend(obligations);
+
+                // Construct the nested `T: Unsize<U>` predicate.
+                nested.push(ensure_sufficient_stack(|| {
+                    predicate_for_trait_def(
+                        tcx,
+                        obligation.param_env,
+                        obligation.cause.clone(),
+                        obligation.predicate.def_id(),
+                        obligation.recursion_depth + 1,
+                        a_last.expect_ty(),
+                        &[b_last],
+                    )
+                }));
+            }
+
+            _ => bug!(),
+        };
+
+        Ok(VtableBuiltinData { nested })
+    }
+}
diff --git a/src/librustc_trait_selection/traits/select.rs b/src/librustc_trait_selection/traits/select/mod.rs
index 517433b90ee..def99a7b5b5 100644
--- a/src/librustc_trait_selection/traits/select.rs
+++ b/src/librustc_trait_selection/traits/select/mod.rs
@@ -1,5 +1,3 @@
-// ignore-tidy-filelength
-
 //! Candidate selection. See the [rustc dev guide] for more information on how this works.
 //!
 //! [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/traits/resolution.html#selection
@@ -9,29 +7,19 @@ use self::SelectionCandidate::*;
 
 use super::coherence::{self, Conflict};
 use super::project;
-use super::project::{normalize_with_depth, normalize_with_depth_to};
+use super::project::normalize_with_depth_to;
 use super::util;
 use super::util::{closure_trait_ref_and_return_type, predicate_for_trait_def};
 use super::wf;
 use super::DerivedObligationCause;
+use super::Obligation;
+use super::ObligationCauseCode;
 use super::Selection;
 use super::SelectionResult;
-use super::TraitNotObjectSafe;
 use super::TraitQueryMode;
-use super::{BuiltinDerivedObligation, ImplDerivedObligation, ObligationCauseCode};
 use super::{Normalized, ProjectionCacheKey};
-use super::{ObjectCastObligation, Obligation};
 use super::{ObligationCause, PredicateObligation, TraitObligation};
-use super::{OutputTypeParameterMismatch, Overflow, SelectionError, Unimplemented};
-use super::{
-    VtableAutoImpl, VtableBuiltin, VtableClosure, VtableDiscriminantKind, VtableFnPointer,
-    VtableGenerator, VtableImpl, VtableObject, VtableParam, VtableTraitAlias,
-};
-use super::{
-    VtableAutoImplData, VtableBuiltinData, VtableClosureData, VtableDiscriminantKindData,
-    VtableFnPointerData, VtableGeneratorData, VtableImplData, VtableObjectData,
-    VtableTraitAliasData,
-};
+use super::{Overflow, SelectionError, Unimplemented};
 
 use crate::infer::{CombinedSnapshot, InferCtxt, InferOk, PlaceholderMap, TypeFreshener};
 use crate::traits::error_reporting::InferCtxtExt;
@@ -42,18 +30,13 @@ use rustc_data_structures::stack::ensure_sufficient_stack;
 use rustc_errors::ErrorReported;
 use rustc_hir as hir;
 use rustc_hir::def_id::DefId;
-use rustc_hir::lang_items;
-use rustc_index::bit_set::GrowableBitSet;
 use rustc_middle::dep_graph::{DepKind, DepNodeIndex};
 use rustc_middle::mir::interpret::ErrorHandled;
 use rustc_middle::ty::fast_reject;
 use rustc_middle::ty::relate::TypeRelation;
-use rustc_middle::ty::subst::{GenericArg, GenericArgKind, Subst, SubstsRef};
-use rustc_middle::ty::{
-    self, ToPolyTraitRef, ToPredicate, Ty, TyCtxt, TypeFoldable, WithConstness,
-};
+use rustc_middle::ty::subst::{GenericArgKind, Subst, SubstsRef};
+use rustc_middle::ty::{self, ToPolyTraitRef, ToPredicate, Ty, TyCtxt, TypeFoldable};
 use rustc_span::symbol::sym;
-use rustc_target::spec::abi::Abi;
 
 use std::cell::{Cell, RefCell};
 use std::cmp;
@@ -63,6 +46,9 @@ use std::rc::Rc;
 
 pub use rustc_middle::traits::select::*;
 
+mod candidate_assembly;
+mod confirmation;
+
 pub struct SelectionContext<'cx, 'tcx> {
     infcx: &'cx InferCtxt<'cx, 'tcx>,
 
@@ -932,61 +918,6 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         Ok(())
     }
 
-    ///////////////////////////////////////////////////////////////////////////
-    // CANDIDATE ASSEMBLY
-    //
-    // The selection process begins by examining all in-scope impls,
-    // caller obligations, and so forth and assembling a list of
-    // candidates. See the [rustc dev guide] for more details.
-    //
-    // [rustc dev guide]:
-    // https://rustc-dev-guide.rust-lang.org/traits/resolution.html#candidate-assembly
-
-    fn candidate_from_obligation<'o>(
-        &mut self,
-        stack: &TraitObligationStack<'o, 'tcx>,
-    ) -> SelectionResult<'tcx, SelectionCandidate<'tcx>> {
-        // Watch out for overflow. This intentionally bypasses (and does
-        // not update) the cache.
-        self.check_recursion_limit(&stack.obligation, &stack.obligation)?;
-
-        // Check the cache. Note that we freshen the trait-ref
-        // separately rather than using `stack.fresh_trait_ref` --
-        // this is because we want the unbound variables to be
-        // replaced with fresh types starting from index 0.
-        let cache_fresh_trait_pred = self.infcx.freshen(stack.obligation.predicate);
-        debug!(
-            "candidate_from_obligation(cache_fresh_trait_pred={:?}, obligation={:?})",
-            cache_fresh_trait_pred, stack
-        );
-        debug_assert!(!stack.obligation.predicate.has_escaping_bound_vars());
-
-        if let Some(c) =
-            self.check_candidate_cache(stack.obligation.param_env, cache_fresh_trait_pred)
-        {
-            debug!("CACHE HIT: SELECT({:?})={:?}", cache_fresh_trait_pred, c);
-            return c;
-        }
-
-        // If no match, compute result and insert into cache.
-        //
-        // FIXME(nikomatsakis) -- this cache is not taking into
-        // account cycles that may have occurred in forming the
-        // candidate. I don't know of any specific problems that
-        // result but it seems awfully suspicious.
-        let (candidate, dep_node) =
-            self.in_task(|this| this.candidate_from_obligation_no_cache(stack));
-
-        debug!("CACHE MISS: SELECT({:?})={:?}", cache_fresh_trait_pred, candidate);
-        self.insert_candidate_cache(
-            stack.obligation.param_env,
-            cache_fresh_trait_pred,
-            dep_node,
-            candidate.clone(),
-        );
-        candidate
-    }
-
     fn in_task<OP, R>(&mut self, op: OP) -> (R, DepNodeIndex)
     where
         OP: FnOnce(&mut Self) -> R,
@@ -1320,116 +1251,6 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             .insert(param_env.and(trait_ref), WithDepNode::new(dep_node, candidate));
     }
 
-    fn assemble_candidates<'o>(
-        &mut self,
-        stack: &TraitObligationStack<'o, 'tcx>,
-    ) -> Result<SelectionCandidateSet<'tcx>, SelectionError<'tcx>> {
-        let TraitObligationStack { obligation, .. } = *stack;
-        let obligation = &Obligation {
-            param_env: obligation.param_env,
-            cause: obligation.cause.clone(),
-            recursion_depth: obligation.recursion_depth,
-            predicate: self.infcx().resolve_vars_if_possible(&obligation.predicate),
-        };
-
-        if obligation.predicate.skip_binder().self_ty().is_ty_var() {
-            // Self is a type variable (e.g., `_: AsRef<str>`).
-            //
-            // This is somewhat problematic, as the current scheme can't really
-            // handle it turning to be a projection. This does end up as truly
-            // ambiguous in most cases anyway.
-            //
-            // Take the fast path out - this also improves
-            // performance by preventing assemble_candidates_from_impls from
-            // matching every impl for this trait.
-            return Ok(SelectionCandidateSet { vec: vec![], ambiguous: true });
-        }
-
-        let mut candidates = SelectionCandidateSet { vec: Vec::new(), ambiguous: false };
-
-        self.assemble_candidates_for_trait_alias(obligation, &mut candidates)?;
-
-        // Other bounds. Consider both in-scope bounds from fn decl
-        // and applicable impls. There is a certain set of precedence rules here.
-        let def_id = obligation.predicate.def_id();
-        let lang_items = self.tcx().lang_items();
-
-        if lang_items.copy_trait() == Some(def_id) {
-            debug!("obligation self ty is {:?}", obligation.predicate.skip_binder().self_ty());
-
-            // User-defined copy impls are permitted, but only for
-            // structs and enums.
-            self.assemble_candidates_from_impls(obligation, &mut candidates)?;
-
-            // For other types, we'll use the builtin rules.
-            let copy_conditions = self.copy_clone_conditions(obligation);
-            self.assemble_builtin_bound_candidates(copy_conditions, &mut candidates)?;
-        } else if lang_items.discriminant_kind_trait() == Some(def_id) {
-            // `DiscriminantKind` is automatically implemented for every type.
-            candidates.vec.push(DiscriminantKindCandidate);
-        } else if lang_items.sized_trait() == Some(def_id) {
-            // Sized is never implementable by end-users, it is
-            // always automatically computed.
-            let sized_conditions = self.sized_conditions(obligation);
-            self.assemble_builtin_bound_candidates(sized_conditions, &mut candidates)?;
-        } else if lang_items.unsize_trait() == Some(def_id) {
-            self.assemble_candidates_for_unsizing(obligation, &mut candidates);
-        } else {
-            if lang_items.clone_trait() == Some(def_id) {
-                // Same builtin conditions as `Copy`, i.e., every type which has builtin support
-                // for `Copy` also has builtin support for `Clone`, and tuples/arrays of `Clone`
-                // types have builtin support for `Clone`.
-                let clone_conditions = self.copy_clone_conditions(obligation);
-                self.assemble_builtin_bound_candidates(clone_conditions, &mut candidates)?;
-            }
-
-            self.assemble_generator_candidates(obligation, &mut candidates)?;
-            self.assemble_closure_candidates(obligation, &mut candidates)?;
-            self.assemble_fn_pointer_candidates(obligation, &mut candidates)?;
-            self.assemble_candidates_from_impls(obligation, &mut candidates)?;
-            self.assemble_candidates_from_object_ty(obligation, &mut candidates);
-        }
-
-        self.assemble_candidates_from_projected_tys(obligation, &mut candidates);
-        self.assemble_candidates_from_caller_bounds(stack, &mut candidates)?;
-        // Auto implementations have lower priority, so we only
-        // consider triggering a default if there is no other impl that can apply.
-        if candidates.vec.is_empty() {
-            self.assemble_candidates_from_auto_impls(obligation, &mut candidates)?;
-        }
-        debug!("candidate list size: {}", candidates.vec.len());
-        Ok(candidates)
-    }
-
-    fn assemble_candidates_from_projected_tys(
-        &mut self,
-        obligation: &TraitObligation<'tcx>,
-        candidates: &mut SelectionCandidateSet<'tcx>,
-    ) {
-        debug!("assemble_candidates_for_projected_tys({:?})", obligation);
-
-        // Before we go into the whole placeholder thing, just
-        // quickly check if the self-type is a projection at all.
-        match obligation.predicate.skip_binder().trait_ref.self_ty().kind {
-            ty::Projection(_) | ty::Opaque(..) => {}
-            ty::Infer(ty::TyVar(_)) => {
-                span_bug!(
-                    obligation.cause.span,
-                    "Self=_ should have been handled by assemble_candidates"
-                );
-            }
-            _ => return,
-        }
-
-        let result = self.infcx.probe(|snapshot| {
-            self.match_projection_obligation_against_definition_bounds(obligation, snapshot)
-        });
-
-        if result {
-            candidates.vec.push(ProjectionCandidate);
-        }
-    }
-
     fn match_projection_obligation_against_definition_bounds(
         &mut self,
         obligation: &TraitObligation<'tcx>,
@@ -1523,42 +1344,6 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             && self.infcx.leak_check(false, placeholder_map, snapshot).is_ok()
     }
 
-    /// Given an obligation like `<SomeTrait for T>`, searches the obligations that the caller
-    /// supplied to find out whether it is listed among them.
-    ///
-    /// Never affects the inference environment.
-    fn assemble_candidates_from_caller_bounds<'o>(
-        &mut self,
-        stack: &TraitObligationStack<'o, 'tcx>,
-        candidates: &mut SelectionCandidateSet<'tcx>,
-    ) -> Result<(), SelectionError<'tcx>> {
-        debug!("assemble_candidates_from_caller_bounds({:?})", stack.obligation);
-
-        let all_bounds = stack
-            .obligation
-            .param_env
-            .caller_bounds
-            .iter()
-            .filter_map(|o| o.to_opt_poly_trait_ref());
-
-        // Micro-optimization: filter out predicates relating to different traits.
-        let matching_bounds =
-            all_bounds.filter(|p| p.def_id() == stack.obligation.predicate.def_id());
-
-        // Keep only those bounds which may apply, and propagate overflow if it occurs.
-        let mut param_candidates = vec![];
-        for bound in matching_bounds {
-            let wc = self.evaluate_where_clause(stack, bound)?;
-            if wc.may_apply() {
-                param_candidates.push(ParamCandidate(bound));
-            }
-        }
-
-        candidates.vec.extend(param_candidates);
-
-        Ok(())
-    }
-
     fn evaluate_where_clause<'o>(
         &mut self,
         stack: &TraitObligationStack<'o, 'tcx>,
@@ -1574,383 +1359,6 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         })
     }
 
-    fn assemble_generator_candidates(
-        &mut self,
-        obligation: &TraitObligation<'tcx>,
-        candidates: &mut SelectionCandidateSet<'tcx>,
-    ) -> Result<(), SelectionError<'tcx>> {
-        if self.tcx().lang_items().gen_trait() != Some(obligation.predicate.def_id()) {
-            return Ok(());
-        }
-
-        // Okay to skip binder because the substs on generator types never
-        // touch bound regions, they just capture the in-scope
-        // type/region parameters.
-        let self_ty = *obligation.self_ty().skip_binder();
-        match self_ty.kind {
-            ty::Generator(..) => {
-                debug!(
-                    "assemble_generator_candidates: self_ty={:?} obligation={:?}",
-                    self_ty, obligation
-                );
-
-                candidates.vec.push(GeneratorCandidate);
-            }
-            ty::Infer(ty::TyVar(_)) => {
-                debug!("assemble_generator_candidates: ambiguous self-type");
-                candidates.ambiguous = true;
-            }
-            _ => {}
-        }
-
-        Ok(())
-    }
-
-    /// Checks for the artificial impl that the compiler will create for an obligation like `X :
-    /// FnMut<..>` where `X` is a closure type.
-    ///
-    /// Note: the type parameters on a closure candidate are modeled as *output* type
-    /// parameters and hence do not affect whether this trait is a match or not. They will be
-    /// unified during the confirmation step.
-    fn assemble_closure_candidates(
-        &mut self,
-        obligation: &TraitObligation<'tcx>,
-        candidates: &mut SelectionCandidateSet<'tcx>,
-    ) -> Result<(), SelectionError<'tcx>> {
-        let kind = match self.tcx().fn_trait_kind_from_lang_item(obligation.predicate.def_id()) {
-            Some(k) => k,
-            None => {
-                return Ok(());
-            }
-        };
-
-        // Okay to skip binder because the substs on closure types never
-        // touch bound regions, they just capture the in-scope
-        // type/region parameters
-        match obligation.self_ty().skip_binder().kind {
-            ty::Closure(_, closure_substs) => {
-                debug!("assemble_unboxed_candidates: kind={:?} obligation={:?}", kind, obligation);
-                match self.infcx.closure_kind(closure_substs) {
-                    Some(closure_kind) => {
-                        debug!("assemble_unboxed_candidates: closure_kind = {:?}", closure_kind);
-                        if closure_kind.extends(kind) {
-                            candidates.vec.push(ClosureCandidate);
-                        }
-                    }
-                    None => {
-                        debug!("assemble_unboxed_candidates: closure_kind not yet known");
-                        candidates.vec.push(ClosureCandidate);
-                    }
-                }
-            }
-            ty::Infer(ty::TyVar(_)) => {
-                debug!("assemble_unboxed_closure_candidates: ambiguous self-type");
-                candidates.ambiguous = true;
-            }
-            _ => {}
-        }
-
-        Ok(())
-    }
-
-    /// Implements one of the `Fn()` family for a fn pointer.
-    fn assemble_fn_pointer_candidates(
-        &mut self,
-        obligation: &TraitObligation<'tcx>,
-        candidates: &mut SelectionCandidateSet<'tcx>,
-    ) -> Result<(), SelectionError<'tcx>> {
-        // We provide impl of all fn traits for fn pointers.
-        if self.tcx().fn_trait_kind_from_lang_item(obligation.predicate.def_id()).is_none() {
-            return Ok(());
-        }
-
-        // Okay to skip binder because what we are inspecting doesn't involve bound regions.
-        let self_ty = *obligation.self_ty().skip_binder();
-        match self_ty.kind {
-            ty::Infer(ty::TyVar(_)) => {
-                debug!("assemble_fn_pointer_candidates: ambiguous self-type");
-                candidates.ambiguous = true; // Could wind up being a fn() type.
-            }
-            // Provide an impl, but only for suitable `fn` pointers.
-            ty::FnDef(..) | ty::FnPtr(_) => {
-                if let ty::FnSig {
-                    unsafety: hir::Unsafety::Normal,
-                    abi: Abi::Rust,
-                    c_variadic: false,
-                    ..
-                } = self_ty.fn_sig(self.tcx()).skip_binder()
-                {
-                    candidates.vec.push(FnPointerCandidate);
-                }
-            }
-            _ => {}
-        }
-
-        Ok(())
-    }
-
-    /// Searches for impls that might apply to `obligation`.
-    fn assemble_candidates_from_impls(
-        &mut self,
-        obligation: &TraitObligation<'tcx>,
-        candidates: &mut SelectionCandidateSet<'tcx>,
-    ) -> Result<(), SelectionError<'tcx>> {
-        debug!("assemble_candidates_from_impls(obligation={:?})", obligation);
-
-        self.tcx().for_each_relevant_impl(
-            obligation.predicate.def_id(),
-            obligation.predicate.skip_binder().trait_ref.self_ty(),
-            |impl_def_id| {
-                self.infcx.probe(|snapshot| {
-                    if let Ok(_substs) = self.match_impl(impl_def_id, obligation, snapshot) {
-                        candidates.vec.push(ImplCandidate(impl_def_id));
-                    }
-                });
-            },
-        );
-
-        Ok(())
-    }
-
-    fn assemble_candidates_from_auto_impls(
-        &mut self,
-        obligation: &TraitObligation<'tcx>,
-        candidates: &mut SelectionCandidateSet<'tcx>,
-    ) -> Result<(), SelectionError<'tcx>> {
-        // Okay to skip binder here because the tests we do below do not involve bound regions.
-        let self_ty = *obligation.self_ty().skip_binder();
-        debug!("assemble_candidates_from_auto_impls(self_ty={:?})", self_ty);
-
-        let def_id = obligation.predicate.def_id();
-
-        if self.tcx().trait_is_auto(def_id) {
-            match self_ty.kind {
-                ty::Dynamic(..) => {
-                    // For object types, we don't know what the closed
-                    // over types are. This means we conservatively
-                    // say nothing; a candidate may be added by
-                    // `assemble_candidates_from_object_ty`.
-                }
-                ty::Foreign(..) => {
-                    // Since the contents of foreign types is unknown,
-                    // we don't add any `..` impl. Default traits could
-                    // still be provided by a manual implementation for
-                    // this trait and type.
-                }
-                ty::Param(..) | ty::Projection(..) => {
-                    // In these cases, we don't know what the actual
-                    // type is.  Therefore, we cannot break it down
-                    // into its constituent types. So we don't
-                    // consider the `..` impl but instead just add no
-                    // candidates: this means that typeck will only
-                    // succeed if there is another reason to believe
-                    // that this obligation holds. That could be a
-                    // where-clause or, in the case of an object type,
-                    // it could be that the object type lists the
-                    // trait (e.g., `Foo+Send : Send`). See
-                    // `compile-fail/typeck-default-trait-impl-send-param.rs`
-                    // for an example of a test case that exercises
-                    // this path.
-                }
-                ty::Infer(ty::TyVar(_)) => {
-                    // The auto impl might apply; we don't know.
-                    candidates.ambiguous = true;
-                }
-                ty::Generator(_, _, movability)
-                    if self.tcx().lang_items().unpin_trait() == Some(def_id) =>
-                {
-                    match movability {
-                        hir::Movability::Static => {
-                            // Immovable generators are never `Unpin`, so
-                            // suppress the normal auto-impl candidate for it.
-                        }
-                        hir::Movability::Movable => {
-                            // Movable generators are always `Unpin`, so add an
-                            // unconditional builtin candidate.
-                            candidates.vec.push(BuiltinCandidate { has_nested: false });
-                        }
-                    }
-                }
-
-                _ => candidates.vec.push(AutoImplCandidate(def_id)),
-            }
-        }
-
-        Ok(())
-    }
-
-    /// Searches for impls that might apply to `obligation`.
-    fn assemble_candidates_from_object_ty(
-        &mut self,
-        obligation: &TraitObligation<'tcx>,
-        candidates: &mut SelectionCandidateSet<'tcx>,
-    ) {
-        debug!(
-            "assemble_candidates_from_object_ty(self_ty={:?})",
-            obligation.self_ty().skip_binder()
-        );
-
-        self.infcx.probe(|_snapshot| {
-            // The code below doesn't care about regions, and the
-            // self-ty here doesn't escape this probe, so just erase
-            // any LBR.
-            let self_ty = self.tcx().erase_late_bound_regions(&obligation.self_ty());
-            let poly_trait_ref = match self_ty.kind {
-                ty::Dynamic(ref data, ..) => {
-                    if data.auto_traits().any(|did| did == obligation.predicate.def_id()) {
-                        debug!(
-                            "assemble_candidates_from_object_ty: matched builtin bound, \
-                             pushing candidate"
-                        );
-                        candidates.vec.push(BuiltinObjectCandidate);
-                        return;
-                    }
-
-                    if let Some(principal) = data.principal() {
-                        if !self.infcx.tcx.features().object_safe_for_dispatch {
-                            principal.with_self_ty(self.tcx(), self_ty)
-                        } else if self.tcx().is_object_safe(principal.def_id()) {
-                            principal.with_self_ty(self.tcx(), self_ty)
-                        } else {
-                            return;
-                        }
-                    } else {
-                        // Only auto trait bounds exist.
-                        return;
-                    }
-                }
-                ty::Infer(ty::TyVar(_)) => {
-                    debug!("assemble_candidates_from_object_ty: ambiguous");
-                    candidates.ambiguous = true; // could wind up being an object type
-                    return;
-                }
-                _ => return,
-            };
-
-            debug!("assemble_candidates_from_object_ty: poly_trait_ref={:?}", poly_trait_ref);
-
-            // Count only those upcast versions that match the trait-ref
-            // we are looking for. Specifically, do not only check for the
-            // correct trait, but also the correct type parameters.
-            // For example, we may be trying to upcast `Foo` to `Bar<i32>`,
-            // but `Foo` is declared as `trait Foo: Bar<u32>`.
-            let upcast_trait_refs = util::supertraits(self.tcx(), poly_trait_ref)
-                .filter(|upcast_trait_ref| {
-                    self.infcx
-                        .probe(|_| self.match_poly_trait_ref(obligation, *upcast_trait_ref).is_ok())
-                })
-                .count();
-
-            if upcast_trait_refs > 1 {
-                // Can be upcast in many ways; need more type information.
-                candidates.ambiguous = true;
-            } else if upcast_trait_refs == 1 {
-                candidates.vec.push(ObjectCandidate);
-            }
-        })
-    }
-
-    /// Searches for unsizing that might apply to `obligation`.
-    fn assemble_candidates_for_unsizing(
-        &mut self,
-        obligation: &TraitObligation<'tcx>,
-        candidates: &mut SelectionCandidateSet<'tcx>,
-    ) {
-        // We currently never consider higher-ranked obligations e.g.
-        // `for<'a> &'a T: Unsize<Trait+'a>` to be implemented. This is not
-        // because they are a priori invalid, and we could potentially add support
-        // for them later, it's just that there isn't really a strong need for it.
-        // A `T: Unsize<U>` obligation is always used as part of a `T: CoerceUnsize<U>`
-        // impl, and those are generally applied to concrete types.
-        //
-        // That said, one might try to write a fn with a where clause like
-        //     for<'a> Foo<'a, T>: Unsize<Foo<'a, Trait>>
-        // where the `'a` is kind of orthogonal to the relevant part of the `Unsize`.
-        // Still, you'd be more likely to write that where clause as
-        //     T: Trait
-        // so it seems ok if we (conservatively) fail to accept that `Unsize`
-        // obligation above. Should be possible to extend this in the future.
-        let source = match obligation.self_ty().no_bound_vars() {
-            Some(t) => t,
-            None => {
-                // Don't add any candidates if there are bound regions.
-                return;
-            }
-        };
-        let target = obligation.predicate.skip_binder().trait_ref.substs.type_at(1);
-
-        debug!("assemble_candidates_for_unsizing(source={:?}, target={:?})", source, target);
-
-        let may_apply = match (&source.kind, &target.kind) {
-            // Trait+Kx+'a -> Trait+Ky+'b (upcasts).
-            (&ty::Dynamic(ref data_a, ..), &ty::Dynamic(ref data_b, ..)) => {
-                // Upcasts permit two things:
-                //
-                // 1. Dropping auto traits, e.g., `Foo + Send` to `Foo`
-                // 2. Tightening the region bound, e.g., `Foo + 'a` to `Foo + 'b` if `'a: 'b`
-                //
-                // Note that neither of these changes requires any
-                // change at runtime. Eventually this will be
-                // generalized.
-                //
-                // We always upcast when we can because of reason
-                // #2 (region bounds).
-                data_a.principal_def_id() == data_b.principal_def_id()
-                    && data_b
-                        .auto_traits()
-                        // All of a's auto traits need to be in b's auto traits.
-                        .all(|b| data_a.auto_traits().any(|a| a == b))
-            }
-
-            // `T` -> `Trait`
-            (_, &ty::Dynamic(..)) => true,
-
-            // Ambiguous handling is below `T` -> `Trait`, because inference
-            // variables can still implement `Unsize<Trait>` and nested
-            // obligations will have the final say (likely deferred).
-            (&ty::Infer(ty::TyVar(_)), _) | (_, &ty::Infer(ty::TyVar(_))) => {
-                debug!("assemble_candidates_for_unsizing: ambiguous");
-                candidates.ambiguous = true;
-                false
-            }
-
-            // `[T; n]` -> `[T]`
-            (&ty::Array(..), &ty::Slice(_)) => true,
-
-            // `Struct<T>` -> `Struct<U>`
-            (&ty::Adt(def_id_a, _), &ty::Adt(def_id_b, _)) if def_id_a.is_struct() => {
-                def_id_a == def_id_b
-            }
-
-            // `(.., T)` -> `(.., U)`
-            (&ty::Tuple(tys_a), &ty::Tuple(tys_b)) => tys_a.len() == tys_b.len(),
-
-            _ => false,
-        };
-
-        if may_apply {
-            candidates.vec.push(BuiltinUnsizeCandidate);
-        }
-    }
-
-    fn assemble_candidates_for_trait_alias(
-        &mut self,
-        obligation: &TraitObligation<'tcx>,
-        candidates: &mut SelectionCandidateSet<'tcx>,
-    ) -> Result<(), SelectionError<'tcx>> {
-        // Okay to skip binder here because the tests we do below do not involve bound regions.
-        let self_ty = *obligation.self_ty().skip_binder();
-        debug!("assemble_candidates_for_trait_alias(self_ty={:?})", self_ty);
-
-        let def_id = obligation.predicate.def_id();
-
-        if self.tcx().is_trait_alias(def_id) {
-            candidates.vec.push(TraitAliasCandidate(def_id));
-        }
-
-        Ok(())
-    }
-
     ///////////////////////////////////////////////////////////////////////////
     // WINNOW
     //
@@ -2128,34 +1536,6 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         }
     }
 
-    ///////////////////////////////////////////////////////////////////////////
-    // BUILTIN BOUNDS
-    //
-    // These cover the traits that are built-in to the language
-    // itself: `Copy`, `Clone` and `Sized`.
-
-    fn assemble_builtin_bound_candidates(
-        &mut self,
-        conditions: BuiltinImplConditions<'tcx>,
-        candidates: &mut SelectionCandidateSet<'tcx>,
-    ) -> Result<(), SelectionError<'tcx>> {
-        match conditions {
-            BuiltinImplConditions::Where(nested) => {
-                debug!("builtin_bound: nested={:?}", nested);
-                candidates
-                    .vec
-                    .push(BuiltinCandidate { has_nested: !nested.skip_binder().is_empty() });
-            }
-            BuiltinImplConditions::None => {}
-            BuiltinImplConditions::Ambiguous => {
-                debug!("assemble_builtin_bound_candidates: ambiguous builtin");
-                candidates.ambiguous = true;
-            }
-        }
-
-        Ok(())
-    }
-
     fn sized_conditions(
         &mut self,
         obligation: &TraitObligation<'tcx>,
@@ -2414,790 +1794,6 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     }
 
     ///////////////////////////////////////////////////////////////////////////
-    // CONFIRMATION
-    //
-    // Confirmation unifies the output type parameters of the trait
-    // with the values found in the obligation, possibly yielding a
-    // type error.  See the [rustc dev guide] for more details.
-    //
-    // [rustc dev guide]:
-    // https://rustc-dev-guide.rust-lang.org/traits/resolution.html#confirmation
-
-    fn confirm_candidate(
-        &mut self,
-        obligation: &TraitObligation<'tcx>,
-        candidate: SelectionCandidate<'tcx>,
-    ) -> Result<Selection<'tcx>, SelectionError<'tcx>> {
-        debug!("confirm_candidate({:?}, {:?})", obligation, candidate);
-
-        match candidate {
-            BuiltinCandidate { has_nested } => {
-                let data = self.confirm_builtin_candidate(obligation, has_nested);
-                Ok(VtableBuiltin(data))
-            }
-
-            ParamCandidate(param) => {
-                let obligations = self.confirm_param_candidate(obligation, param);
-                Ok(VtableParam(obligations))
-            }
-
-            ImplCandidate(impl_def_id) => {
-                Ok(VtableImpl(self.confirm_impl_candidate(obligation, impl_def_id)))
-            }
-
-            AutoImplCandidate(trait_def_id) => {
-                let data = self.confirm_auto_impl_candidate(obligation, trait_def_id);
-                Ok(VtableAutoImpl(data))
-            }
-
-            ProjectionCandidate => {
-                self.confirm_projection_candidate(obligation);
-                Ok(VtableParam(Vec::new()))
-            }
-
-            ClosureCandidate => {
-                let vtable_closure = self.confirm_closure_candidate(obligation)?;
-                Ok(VtableClosure(vtable_closure))
-            }
-
-            GeneratorCandidate => {
-                let vtable_generator = self.confirm_generator_candidate(obligation)?;
-                Ok(VtableGenerator(vtable_generator))
-            }
-
-            FnPointerCandidate => {
-                let data = self.confirm_fn_pointer_candidate(obligation)?;
-                Ok(VtableFnPointer(data))
-            }
-
-            DiscriminantKindCandidate => Ok(VtableDiscriminantKind(VtableDiscriminantKindData)),
-
-            TraitAliasCandidate(alias_def_id) => {
-                let data = self.confirm_trait_alias_candidate(obligation, alias_def_id);
-                Ok(VtableTraitAlias(data))
-            }
-
-            ObjectCandidate => {
-                let data = self.confirm_object_candidate(obligation);
-                Ok(VtableObject(data))
-            }
-
-            BuiltinObjectCandidate => {
-                // This indicates something like `Trait + Send: Send`. In this case, we know that
-                // this holds because that's what the object type is telling us, and there's really
-                // no additional obligations to prove and no types in particular to unify, etc.
-                Ok(VtableParam(Vec::new()))
-            }
-
-            BuiltinUnsizeCandidate => {
-                let data = self.confirm_builtin_unsize_candidate(obligation)?;
-                Ok(VtableBuiltin(data))
-            }
-        }
-    }
-
-    fn confirm_projection_candidate(&mut self, obligation: &TraitObligation<'tcx>) {
-        self.infcx.commit_unconditionally(|snapshot| {
-            let result =
-                self.match_projection_obligation_against_definition_bounds(obligation, snapshot);
-            assert!(result);
-        })
-    }
-
-    fn confirm_param_candidate(
-        &mut self,
-        obligation: &TraitObligation<'tcx>,
-        param: ty::PolyTraitRef<'tcx>,
-    ) -> Vec<PredicateObligation<'tcx>> {
-        debug!("confirm_param_candidate({:?},{:?})", obligation, param);
-
-        // During evaluation, we already checked that this
-        // where-clause trait-ref could be unified with the obligation
-        // trait-ref. Repeat that unification now without any
-        // transactional boundary; it should not fail.
-        match self.match_where_clause_trait_ref(obligation, param) {
-            Ok(obligations) => obligations,
-            Err(()) => {
-                bug!(
-                    "Where clause `{:?}` was applicable to `{:?}` but now is not",
-                    param,
-                    obligation
-                );
-            }
-        }
-    }
-
-    fn confirm_builtin_candidate(
-        &mut self,
-        obligation: &TraitObligation<'tcx>,
-        has_nested: bool,
-    ) -> VtableBuiltinData<PredicateObligation<'tcx>> {
-        debug!("confirm_builtin_candidate({:?}, {:?})", obligation, has_nested);
-
-        let lang_items = self.tcx().lang_items();
-        let obligations = if has_nested {
-            let trait_def = obligation.predicate.def_id();
-            let conditions = if Some(trait_def) == lang_items.sized_trait() {
-                self.sized_conditions(obligation)
-            } else if Some(trait_def) == lang_items.copy_trait() {
-                self.copy_clone_conditions(obligation)
-            } else if Some(trait_def) == lang_items.clone_trait() {
-                self.copy_clone_conditions(obligation)
-            } else {
-                bug!("unexpected builtin trait {:?}", trait_def)
-            };
-            let nested = match conditions {
-                BuiltinImplConditions::Where(nested) => nested,
-                _ => bug!("obligation {:?} had matched a builtin impl but now doesn't", obligation),
-            };
-
-            let cause = obligation.derived_cause(BuiltinDerivedObligation);
-            ensure_sufficient_stack(|| {
-                self.collect_predicates_for_types(
-                    obligation.param_env,
-                    cause,
-                    obligation.recursion_depth + 1,
-                    trait_def,
-                    nested,
-                )
-            })
-        } else {
-            vec![]
-        };
-
-        debug!("confirm_builtin_candidate: obligations={:?}", obligations);
-
-        VtableBuiltinData { nested: obligations }
-    }
-
-    /// This handles the case where a `auto trait Foo` impl is being used.
-    /// The idea is that the impl applies to `X : Foo` if the following conditions are met:
-    ///
-    /// 1. For each constituent type `Y` in `X`, `Y : Foo` holds
-    /// 2. For each where-clause `C` declared on `Foo`, `[Self => X] C` holds.
-    fn confirm_auto_impl_candidate(
-        &mut self,
-        obligation: &TraitObligation<'tcx>,
-        trait_def_id: DefId,
-    ) -> VtableAutoImplData<PredicateObligation<'tcx>> {
-        debug!("confirm_auto_impl_candidate({:?}, {:?})", obligation, trait_def_id);
-
-        let types = obligation.predicate.map_bound(|inner| {
-            let self_ty = self.infcx.shallow_resolve(inner.self_ty());
-            self.constituent_types_for_ty(self_ty)
-        });
-        self.vtable_auto_impl(obligation, trait_def_id, types)
-    }
-
-    /// See `confirm_auto_impl_candidate`.
-    fn vtable_auto_impl(
-        &mut self,
-        obligation: &TraitObligation<'tcx>,
-        trait_def_id: DefId,
-        nested: ty::Binder<Vec<Ty<'tcx>>>,
-    ) -> VtableAutoImplData<PredicateObligation<'tcx>> {
-        debug!("vtable_auto_impl: nested={:?}", nested);
-        ensure_sufficient_stack(|| {
-            let cause = obligation.derived_cause(BuiltinDerivedObligation);
-            let mut obligations = self.collect_predicates_for_types(
-                obligation.param_env,
-                cause,
-                obligation.recursion_depth + 1,
-                trait_def_id,
-                nested,
-            );
-
-            let trait_obligations: Vec<PredicateObligation<'_>> =
-                self.infcx.commit_unconditionally(|_| {
-                    let poly_trait_ref = obligation.predicate.to_poly_trait_ref();
-                    let (trait_ref, _) =
-                        self.infcx.replace_bound_vars_with_placeholders(&poly_trait_ref);
-                    let cause = obligation.derived_cause(ImplDerivedObligation);
-                    self.impl_or_trait_obligations(
-                        cause,
-                        obligation.recursion_depth + 1,
-                        obligation.param_env,
-                        trait_def_id,
-                        &trait_ref.substs,
-                    )
-                });
-
-            // Adds the predicates from the trait.  Note that this contains a `Self: Trait`
-            // predicate as usual.  It won't have any effect since auto traits are coinductive.
-            obligations.extend(trait_obligations);
-
-            debug!("vtable_auto_impl: obligations={:?}", obligations);
-
-            VtableAutoImplData { trait_def_id, nested: obligations }
-        })
-    }
-
-    fn confirm_impl_candidate(
-        &mut self,
-        obligation: &TraitObligation<'tcx>,
-        impl_def_id: DefId,
-    ) -> VtableImplData<'tcx, PredicateObligation<'tcx>> {
-        debug!("confirm_impl_candidate({:?},{:?})", obligation, impl_def_id);
-
-        // First, create the substitutions by matching the impl again,
-        // this time not in a probe.
-        self.infcx.commit_unconditionally(|snapshot| {
-            let substs = self.rematch_impl(impl_def_id, obligation, snapshot);
-            debug!("confirm_impl_candidate: substs={:?}", substs);
-            let cause = obligation.derived_cause(ImplDerivedObligation);
-            ensure_sufficient_stack(|| {
-                self.vtable_impl(
-                    impl_def_id,
-                    substs,
-                    cause,
-                    obligation.recursion_depth + 1,
-                    obligation.param_env,
-                )
-            })
-        })
-    }
-
-    fn vtable_impl(
-        &mut self,
-        impl_def_id: DefId,
-        mut substs: Normalized<'tcx, SubstsRef<'tcx>>,
-        cause: ObligationCause<'tcx>,
-        recursion_depth: usize,
-        param_env: ty::ParamEnv<'tcx>,
-    ) -> VtableImplData<'tcx, PredicateObligation<'tcx>> {
-        debug!(
-            "vtable_impl(impl_def_id={:?}, substs={:?}, recursion_depth={})",
-            impl_def_id, substs, recursion_depth,
-        );
-
-        let mut impl_obligations = self.impl_or_trait_obligations(
-            cause,
-            recursion_depth,
-            param_env,
-            impl_def_id,
-            &substs.value,
-        );
-
-        debug!(
-            "vtable_impl: impl_def_id={:?} impl_obligations={:?}",
-            impl_def_id, impl_obligations
-        );
-
-        // Because of RFC447, the impl-trait-ref and obligations
-        // are sufficient to determine the impl substs, without
-        // relying on projections in the impl-trait-ref.
-        //
-        // e.g., `impl<U: Tr, V: Iterator<Item=U>> Foo<<U as Tr>::T> for V`
-        impl_obligations.append(&mut substs.obligations);
-
-        VtableImplData { impl_def_id, substs: substs.value, nested: impl_obligations }
-    }
-
-    fn confirm_object_candidate(
-        &mut self,
-        obligation: &TraitObligation<'tcx>,
-    ) -> VtableObjectData<'tcx, PredicateObligation<'tcx>> {
-        debug!("confirm_object_candidate({:?})", obligation);
-
-        // FIXME(nmatsakis) skipping binder here seems wrong -- we should
-        // probably flatten the binder from the obligation and the binder
-        // from the object. Have to try to make a broken test case that
-        // results.
-        let self_ty = self.infcx.shallow_resolve(*obligation.self_ty().skip_binder());
-        let poly_trait_ref = match self_ty.kind {
-            ty::Dynamic(ref data, ..) => data
-                .principal()
-                .unwrap_or_else(|| {
-                    span_bug!(obligation.cause.span, "object candidate with no principal")
-                })
-                .with_self_ty(self.tcx(), self_ty),
-            _ => span_bug!(obligation.cause.span, "object candidate with non-object"),
-        };
-
-        let mut upcast_trait_ref = None;
-        let mut nested = vec![];
-        let vtable_base;
-
-        {
-            let tcx = self.tcx();
-
-            // We want to find the first supertrait in the list of
-            // supertraits that we can unify with, and do that
-            // unification. We know that there is exactly one in the list
-            // where we can unify, because otherwise select would have
-            // reported an ambiguity. (When we do find a match, also
-            // record it for later.)
-            let nonmatching = util::supertraits(tcx, poly_trait_ref).take_while(|&t| {
-                match self.infcx.commit_if_ok(|_| self.match_poly_trait_ref(obligation, t)) {
-                    Ok(obligations) => {
-                        upcast_trait_ref = Some(t);
-                        nested.extend(obligations);
-                        false
-                    }
-                    Err(_) => true,
-                }
-            });
-
-            // Additionally, for each of the non-matching predicates that
-            // we pass over, we sum up the set of number of vtable
-            // entries, so that we can compute the offset for the selected
-            // trait.
-            vtable_base = nonmatching.map(|t| super::util::count_own_vtable_entries(tcx, t)).sum();
-        }
-
-        VtableObjectData { upcast_trait_ref: upcast_trait_ref.unwrap(), vtable_base, nested }
-    }
-
-    fn confirm_fn_pointer_candidate(
-        &mut self,
-        obligation: &TraitObligation<'tcx>,
-    ) -> Result<VtableFnPointerData<'tcx, PredicateObligation<'tcx>>, SelectionError<'tcx>> {
-        debug!("confirm_fn_pointer_candidate({:?})", obligation);
-
-        // Okay to skip binder; it is reintroduced below.
-        let self_ty = self.infcx.shallow_resolve(*obligation.self_ty().skip_binder());
-        let sig = self_ty.fn_sig(self.tcx());
-        let trait_ref = closure_trait_ref_and_return_type(
-            self.tcx(),
-            obligation.predicate.def_id(),
-            self_ty,
-            sig,
-            util::TupleArgumentsFlag::Yes,
-        )
-        .map_bound(|(trait_ref, _)| trait_ref);
-
-        let Normalized { value: trait_ref, obligations } = ensure_sufficient_stack(|| {
-            project::normalize_with_depth(
-                self,
-                obligation.param_env,
-                obligation.cause.clone(),
-                obligation.recursion_depth + 1,
-                &trait_ref,
-            )
-        });
-
-        self.confirm_poly_trait_refs(
-            obligation.cause.clone(),
-            obligation.param_env,
-            obligation.predicate.to_poly_trait_ref(),
-            trait_ref,
-        )?;
-        Ok(VtableFnPointerData { fn_ty: self_ty, nested: obligations })
-    }
-
-    fn confirm_trait_alias_candidate(
-        &mut self,
-        obligation: &TraitObligation<'tcx>,
-        alias_def_id: DefId,
-    ) -> VtableTraitAliasData<'tcx, PredicateObligation<'tcx>> {
-        debug!("confirm_trait_alias_candidate({:?}, {:?})", obligation, alias_def_id);
-
-        self.infcx.commit_unconditionally(|_| {
-            let (predicate, _) =
-                self.infcx().replace_bound_vars_with_placeholders(&obligation.predicate);
-            let trait_ref = predicate.trait_ref;
-            let trait_def_id = trait_ref.def_id;
-            let substs = trait_ref.substs;
-
-            let trait_obligations = self.impl_or_trait_obligations(
-                obligation.cause.clone(),
-                obligation.recursion_depth,
-                obligation.param_env,
-                trait_def_id,
-                &substs,
-            );
-
-            debug!(
-                "confirm_trait_alias_candidate: trait_def_id={:?} trait_obligations={:?}",
-                trait_def_id, trait_obligations
-            );
-
-            VtableTraitAliasData { alias_def_id, substs, nested: trait_obligations }
-        })
-    }
-
-    fn confirm_generator_candidate(
-        &mut self,
-        obligation: &TraitObligation<'tcx>,
-    ) -> Result<VtableGeneratorData<'tcx, PredicateObligation<'tcx>>, SelectionError<'tcx>> {
-        // Okay to skip binder because the substs on generator types never
-        // touch bound regions, they just capture the in-scope
-        // type/region parameters.
-        let self_ty = self.infcx.shallow_resolve(*obligation.self_ty().skip_binder());
-        let (generator_def_id, substs) = match self_ty.kind {
-            ty::Generator(id, substs, _) => (id, substs),
-            _ => bug!("closure candidate for non-closure {:?}", obligation),
-        };
-
-        debug!("confirm_generator_candidate({:?},{:?},{:?})", obligation, generator_def_id, substs);
-
-        let trait_ref = self.generator_trait_ref_unnormalized(obligation, substs);
-        let Normalized { value: trait_ref, mut obligations } = ensure_sufficient_stack(|| {
-            normalize_with_depth(
-                self,
-                obligation.param_env,
-                obligation.cause.clone(),
-                obligation.recursion_depth + 1,
-                &trait_ref,
-            )
-        });
-
-        debug!(
-            "confirm_generator_candidate(generator_def_id={:?}, \
-             trait_ref={:?}, obligations={:?})",
-            generator_def_id, trait_ref, obligations
-        );
-
-        obligations.extend(self.confirm_poly_trait_refs(
-            obligation.cause.clone(),
-            obligation.param_env,
-            obligation.predicate.to_poly_trait_ref(),
-            trait_ref,
-        )?);
-
-        Ok(VtableGeneratorData { generator_def_id, substs, nested: obligations })
-    }
-
-    fn confirm_closure_candidate(
-        &mut self,
-        obligation: &TraitObligation<'tcx>,
-    ) -> Result<VtableClosureData<'tcx, PredicateObligation<'tcx>>, SelectionError<'tcx>> {
-        debug!("confirm_closure_candidate({:?})", obligation);
-
-        let kind = self
-            .tcx()
-            .fn_trait_kind_from_lang_item(obligation.predicate.def_id())
-            .unwrap_or_else(|| bug!("closure candidate for non-fn trait {:?}", obligation));
-
-        // Okay to skip binder because the substs on closure types never
-        // touch bound regions, they just capture the in-scope
-        // type/region parameters.
-        let self_ty = self.infcx.shallow_resolve(*obligation.self_ty().skip_binder());
-        let (closure_def_id, substs) = match self_ty.kind {
-            ty::Closure(id, substs) => (id, substs),
-            _ => bug!("closure candidate for non-closure {:?}", obligation),
-        };
-
-        let trait_ref = self.closure_trait_ref_unnormalized(obligation, substs);
-        let Normalized { value: trait_ref, mut obligations } = ensure_sufficient_stack(|| {
-            normalize_with_depth(
-                self,
-                obligation.param_env,
-                obligation.cause.clone(),
-                obligation.recursion_depth + 1,
-                &trait_ref,
-            )
-        });
-
-        debug!(
-            "confirm_closure_candidate(closure_def_id={:?}, trait_ref={:?}, obligations={:?})",
-            closure_def_id, trait_ref, obligations
-        );
-
-        obligations.extend(self.confirm_poly_trait_refs(
-            obligation.cause.clone(),
-            obligation.param_env,
-            obligation.predicate.to_poly_trait_ref(),
-            trait_ref,
-        )?);
-
-        // FIXME: Chalk
-
-        if !self.tcx().sess.opts.debugging_opts.chalk {
-            obligations.push(Obligation::new(
-                obligation.cause.clone(),
-                obligation.param_env,
-                ty::PredicateKind::ClosureKind(closure_def_id, substs, kind)
-                    .to_predicate(self.tcx()),
-            ));
-        }
-
-        Ok(VtableClosureData { closure_def_id, substs, nested: obligations })
-    }
-
-    /// In the case of closure types and fn pointers,
-    /// we currently treat the input type parameters on the trait as
-    /// outputs. This means that when we have a match we have only
-    /// considered the self type, so we have to go back and make sure
-    /// to relate the argument types too. This is kind of wrong, but
-    /// since we control the full set of impls, also not that wrong,
-    /// and it DOES yield better error messages (since we don't report
-    /// errors as if there is no applicable impl, but rather report
-    /// errors are about mismatched argument types.
-    ///
-    /// Here is an example. Imagine we have a closure expression
-    /// and we desugared it so that the type of the expression is
-    /// `Closure`, and `Closure` expects an int as argument. Then it
-    /// is "as if" the compiler generated this impl:
-    ///
-    ///     impl Fn(int) for Closure { ... }
-    ///
-    /// Now imagine our obligation is `Fn(usize) for Closure`. So far
-    /// we have matched the self type `Closure`. At this point we'll
-    /// compare the `int` to `usize` and generate an error.
-    ///
-    /// Note that this checking occurs *after* the impl has selected,
-    /// because these output type parameters should not affect the
-    /// selection of the impl. Therefore, if there is a mismatch, we
-    /// report an error to the user.
-    fn confirm_poly_trait_refs(
-        &mut self,
-        obligation_cause: ObligationCause<'tcx>,
-        obligation_param_env: ty::ParamEnv<'tcx>,
-        obligation_trait_ref: ty::PolyTraitRef<'tcx>,
-        expected_trait_ref: ty::PolyTraitRef<'tcx>,
-    ) -> Result<Vec<PredicateObligation<'tcx>>, SelectionError<'tcx>> {
-        self.infcx
-            .at(&obligation_cause, obligation_param_env)
-            .sup(obligation_trait_ref, expected_trait_ref)
-            .map(|InferOk { obligations, .. }| obligations)
-            .map_err(|e| OutputTypeParameterMismatch(expected_trait_ref, obligation_trait_ref, e))
-    }
-
-    fn confirm_builtin_unsize_candidate(
-        &mut self,
-        obligation: &TraitObligation<'tcx>,
-    ) -> Result<VtableBuiltinData<PredicateObligation<'tcx>>, SelectionError<'tcx>> {
-        let tcx = self.tcx();
-
-        // `assemble_candidates_for_unsizing` should ensure there are no late-bound
-        // regions here. See the comment there for more details.
-        let source = self.infcx.shallow_resolve(obligation.self_ty().no_bound_vars().unwrap());
-        let target = obligation.predicate.skip_binder().trait_ref.substs.type_at(1);
-        let target = self.infcx.shallow_resolve(target);
-
-        debug!("confirm_builtin_unsize_candidate(source={:?}, target={:?})", source, target);
-
-        let mut nested = vec![];
-        match (&source.kind, &target.kind) {
-            // Trait+Kx+'a -> Trait+Ky+'b (upcasts).
-            (&ty::Dynamic(ref data_a, r_a), &ty::Dynamic(ref data_b, r_b)) => {
-                // See `assemble_candidates_for_unsizing` for more info.
-                let existential_predicates = data_a.map_bound(|data_a| {
-                    let iter = data_a
-                        .principal()
-                        .map(ty::ExistentialPredicate::Trait)
-                        .into_iter()
-                        .chain(data_a.projection_bounds().map(ty::ExistentialPredicate::Projection))
-                        .chain(data_b.auto_traits().map(ty::ExistentialPredicate::AutoTrait));
-                    tcx.mk_existential_predicates(iter)
-                });
-                let source_trait = tcx.mk_dynamic(existential_predicates, r_b);
-
-                // Require that the traits involved in this upcast are **equal**;
-                // only the **lifetime bound** is changed.
-                //
-                // FIXME: This condition is arguably too strong -- it would
-                // suffice for the source trait to be a *subtype* of the target
-                // trait. In particular, changing from something like
-                // `for<'a, 'b> Foo<'a, 'b>` to `for<'a> Foo<'a, 'a>` should be
-                // permitted. And, indeed, in the in commit
-                // 904a0bde93f0348f69914ee90b1f8b6e4e0d7cbc, this
-                // condition was loosened. However, when the leak check was
-                // added back, using subtype here actually guides the coercion
-                // code in such a way that it accepts `old-lub-glb-object.rs`.
-                // This is probably a good thing, but I've modified this to `.eq`
-                // because I want to continue rejecting that test (as we have
-                // done for quite some time) before we are firmly comfortable
-                // with what our behavior should be there. -nikomatsakis
-                let InferOk { obligations, .. } = self
-                    .infcx
-                    .at(&obligation.cause, obligation.param_env)
-                    .eq(target, source_trait) // FIXME -- see below
-                    .map_err(|_| Unimplemented)?;
-                nested.extend(obligations);
-
-                // Register one obligation for 'a: 'b.
-                let cause = ObligationCause::new(
-                    obligation.cause.span,
-                    obligation.cause.body_id,
-                    ObjectCastObligation(target),
-                );
-                let outlives = ty::OutlivesPredicate(r_a, r_b);
-                nested.push(Obligation::with_depth(
-                    cause,
-                    obligation.recursion_depth + 1,
-                    obligation.param_env,
-                    ty::Binder::bind(outlives).to_predicate(tcx),
-                ));
-            }
-
-            // `T` -> `Trait`
-            (_, &ty::Dynamic(ref data, r)) => {
-                let mut object_dids = data.auto_traits().chain(data.principal_def_id());
-                if let Some(did) = object_dids.find(|did| !tcx.is_object_safe(*did)) {
-                    return Err(TraitNotObjectSafe(did));
-                }
-
-                let cause = ObligationCause::new(
-                    obligation.cause.span,
-                    obligation.cause.body_id,
-                    ObjectCastObligation(target),
-                );
-
-                let predicate_to_obligation = |predicate| {
-                    Obligation::with_depth(
-                        cause.clone(),
-                        obligation.recursion_depth + 1,
-                        obligation.param_env,
-                        predicate,
-                    )
-                };
-
-                // Create obligations:
-                //  - Casting `T` to `Trait`
-                //  - For all the various builtin bounds attached to the object cast. (In other
-                //  words, if the object type is `Foo + Send`, this would create an obligation for
-                //  the `Send` check.)
-                //  - Projection predicates
-                nested.extend(
-                    data.iter().map(|predicate| {
-                        predicate_to_obligation(predicate.with_self_ty(tcx, source))
-                    }),
-                );
-
-                // We can only make objects from sized types.
-                let tr = ty::TraitRef::new(
-                    tcx.require_lang_item(lang_items::SizedTraitLangItem, None),
-                    tcx.mk_substs_trait(source, &[]),
-                );
-                nested.push(predicate_to_obligation(tr.without_const().to_predicate(tcx)));
-
-                // If the type is `Foo + 'a`, ensure that the type
-                // being cast to `Foo + 'a` outlives `'a`:
-                let outlives = ty::OutlivesPredicate(source, r);
-                nested.push(predicate_to_obligation(ty::Binder::dummy(outlives).to_predicate(tcx)));
-            }
-
-            // `[T; n]` -> `[T]`
-            (&ty::Array(a, _), &ty::Slice(b)) => {
-                let InferOk { obligations, .. } = self
-                    .infcx
-                    .at(&obligation.cause, obligation.param_env)
-                    .eq(b, a)
-                    .map_err(|_| Unimplemented)?;
-                nested.extend(obligations);
-            }
-
-            // `Struct<T>` -> `Struct<U>`
-            (&ty::Adt(def, substs_a), &ty::Adt(_, substs_b)) => {
-                let maybe_unsizing_param_idx = |arg: GenericArg<'tcx>| match arg.unpack() {
-                    GenericArgKind::Type(ty) => match ty.kind {
-                        ty::Param(p) => Some(p.index),
-                        _ => None,
-                    },
-
-                    // Lifetimes aren't allowed to change during unsizing.
-                    GenericArgKind::Lifetime(_) => None,
-
-                    GenericArgKind::Const(ct) => match ct.val {
-                        ty::ConstKind::Param(p) => Some(p.index),
-                        _ => None,
-                    },
-                };
-
-                // The last field of the structure has to exist and contain type/const parameters.
-                let (tail_field, prefix_fields) =
-                    def.non_enum_variant().fields.split_last().ok_or(Unimplemented)?;
-                let tail_field_ty = tcx.type_of(tail_field.did);
-
-                let mut unsizing_params = GrowableBitSet::new_empty();
-                let mut found = false;
-                for arg in tail_field_ty.walk() {
-                    if let Some(i) = maybe_unsizing_param_idx(arg) {
-                        unsizing_params.insert(i);
-                        found = true;
-                    }
-                }
-                if !found {
-                    return Err(Unimplemented);
-                }
-
-                // Ensure none of the other fields mention the parameters used
-                // in unsizing.
-                // FIXME(eddyb) cache this (including computing `unsizing_params`)
-                // by putting it in a query; it would only need the `DefId` as it
-                // looks at declared field types, not anything substituted.
-                for field in prefix_fields {
-                    for arg in tcx.type_of(field.did).walk() {
-                        if let Some(i) = maybe_unsizing_param_idx(arg) {
-                            if unsizing_params.contains(i) {
-                                return Err(Unimplemented);
-                            }
-                        }
-                    }
-                }
-
-                // Extract `TailField<T>` and `TailField<U>` from `Struct<T>` and `Struct<U>`.
-                let source_tail = tail_field_ty.subst(tcx, substs_a);
-                let target_tail = tail_field_ty.subst(tcx, substs_b);
-
-                // Check that the source struct with the target's
-                // unsizing parameters is equal to the target.
-                let substs = tcx.mk_substs(substs_a.iter().enumerate().map(|(i, k)| {
-                    if unsizing_params.contains(i as u32) { substs_b[i] } else { k }
-                }));
-                let new_struct = tcx.mk_adt(def, substs);
-                let InferOk { obligations, .. } = self
-                    .infcx
-                    .at(&obligation.cause, obligation.param_env)
-                    .eq(target, new_struct)
-                    .map_err(|_| Unimplemented)?;
-                nested.extend(obligations);
-
-                // Construct the nested `TailField<T>: Unsize<TailField<U>>` predicate.
-                nested.push(predicate_for_trait_def(
-                    tcx,
-                    obligation.param_env,
-                    obligation.cause.clone(),
-                    obligation.predicate.def_id(),
-                    obligation.recursion_depth + 1,
-                    source_tail,
-                    &[target_tail.into()],
-                ));
-            }
-
-            // `(.., T)` -> `(.., U)`
-            (&ty::Tuple(tys_a), &ty::Tuple(tys_b)) => {
-                assert_eq!(tys_a.len(), tys_b.len());
-
-                // The last field of the tuple has to exist.
-                let (&a_last, a_mid) = tys_a.split_last().ok_or(Unimplemented)?;
-                let &b_last = tys_b.last().unwrap();
-
-                // Check that the source tuple with the target's
-                // last element is equal to the target.
-                let new_tuple = tcx.mk_tup(
-                    a_mid.iter().map(|k| k.expect_ty()).chain(iter::once(b_last.expect_ty())),
-                );
-                let InferOk { obligations, .. } = self
-                    .infcx
-                    .at(&obligation.cause, obligation.param_env)
-                    .eq(target, new_tuple)
-                    .map_err(|_| Unimplemented)?;
-                nested.extend(obligations);
-
-                // Construct the nested `T: Unsize<U>` predicate.
-                nested.push(ensure_sufficient_stack(|| {
-                    predicate_for_trait_def(
-                        tcx,
-                        obligation.param_env,
-                        obligation.cause.clone(),
-                        obligation.predicate.def_id(),
-                        obligation.recursion_depth + 1,
-                        a_last.expect_ty(),
-                        &[b_last],
-                    )
-                }));
-            }
-
-            _ => bug!(),
-        };
-
-        Ok(VtableBuiltinData { nested })
-    }
-
-    ///////////////////////////////////////////////////////////////////////////
     // Matching
     //
     // Matching is a common path used for both evaluation and