Correct regression in type-inference caused by failing to reconfirm that

the object trait matches the required trait during trait selection.  The
existing code was checking that the object trait WOULD match (in a
probe), but never executing the match outside of a probe.

This corrects various regressions observed in the wild, including
issue #26952. Fixes #26952.

4 files changed, 80 insertions, 31 deletions

diff --git a/src/librustc/middle/infer/mod.rs b/src/librustc/middle/infer/mod.rs
index a293170966a..8190327794b 100644
--- a/src/librustc/middle/infer/mod.rs
+++ b/src/librustc/middle/infer/mod.rs
@@ -698,8 +698,8 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
         }
     }
 
-    fn rollback_to(&self, snapshot: CombinedSnapshot) {
-        debug!("rollback!");
+    fn rollback_to(&self, cause: &str, snapshot: CombinedSnapshot) {
+        debug!("rollback_to(cause={})", cause);
         let CombinedSnapshot { type_snapshot,
                                int_snapshot,
                                float_snapshot,
@@ -759,7 +759,7 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
         debug!("commit_if_ok() -- r.is_ok() = {}", r.is_ok());
         match r {
             Ok(_) => { self.commit_from(snapshot); }
-            Err(_) => { self.rollback_to(snapshot); }
+            Err(_) => { self.rollback_to("commit_if_ok -- error", snapshot); }
         }
         r
     }
@@ -778,6 +778,8 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
 
         let r = self.commit_if_ok(|_| f());
 
+        debug!("commit_regions_if_ok: rolling back everything but regions");
+
         // Roll back any non-region bindings - they should be resolved
         // inside `f`, with, e.g. `resolve_type_vars_if_possible`.
         self.type_variables
@@ -804,7 +806,7 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
         debug!("probe()");
         let snapshot = self.start_snapshot();
         let r = f(&snapshot);
-        self.rollback_to(snapshot);
+        self.rollback_to("probe", snapshot);
         r
     }
 
diff --git a/src/librustc/middle/traits/select.rs b/src/librustc/middle/traits/select.rs
index 81e59f57ae7..79f030ab31e 100644
--- a/src/librustc/middle/traits/select.rs
+++ b/src/librustc/middle/traits/select.rs
@@ -1367,11 +1367,15 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             // 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(|_| {
-                    let upcast_trait_ref = upcast_trait_ref.clone();
-                    self.match_poly_trait_ref(obligation, upcast_trait_ref).is_ok()
-                })).count();
+            let upcast_trait_refs =
+                util::supertraits(self.tcx(), poly_trait_ref)
+                .filter(|upcast_trait_ref| {
+                    self.infcx.probe(|_| {
+                        let upcast_trait_ref = upcast_trait_ref.clone();
+                        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
@@ -1643,9 +1647,9 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                             let principal =
                                 data.principal_trait_ref_with_self_ty(self.tcx(),
                                                                       self.tcx().types.err);
-                            let desired_def_id = obligation.predicate.def_id();
+                            let copy_def_id = obligation.predicate.def_id();
                             for tr in util::supertraits(self.tcx(), principal) {
-                                if tr.def_id() == desired_def_id {
+                                if tr.def_id() == copy_def_id {
                                     return ok_if(Vec::new())
                                 }
                             }
@@ -2310,31 +2314,41 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             }
         };
 
-        // Upcast the object type to the obligation type. There must
-        // be exactly one applicable trait-reference; if this were not
-        // the case, we would have reported an ambiguity error rather
-        // than successfully selecting one of the candidates.
-        let mut upcast_trait_refs = util::supertraits(self.tcx(), poly_trait_ref)
-            .map(|upcast_trait_ref| {
-                (upcast_trait_ref.clone(), self.infcx.probe(|_| {
-                    self.match_poly_trait_ref(obligation, upcast_trait_ref)
-                }).is_ok())
-            });
         let mut upcast_trait_ref = None;
-        let mut vtable_base = 0;
+        let vtable_base;
+
+        {
+            // 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(self.tcx(), poly_trait_ref)
+                .take_while(|&t| {
+                    match
+                        self.infcx.commit_if_ok(
+                            |_| self.match_poly_trait_ref(obligation, t))
+                    {
+                        Ok(_) => { upcast_trait_ref = Some(t); false }
+                        Err(_) => { true }
+                    }
+                });
+
+            // Additionally, for each of the nonmatching 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| util::count_own_vtable_entries(self.tcx(), t))
+                           .sum();
 
-        while let Some((supertrait, matches)) = upcast_trait_refs.next() {
-            if matches {
-                upcast_trait_ref = Some(supertrait);
-                break;
-            }
-            vtable_base += util::count_own_vtable_entries(self.tcx(), supertrait);
         }
-        assert!(upcast_trait_refs.all(|(_, matches)| !matches));
 
         VtableObjectData {
             upcast_trait_ref: upcast_trait_ref.unwrap(),
-            vtable_base: vtable_base
+            vtable_base: vtable_base,
         }
     }
 
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 17a76f6eed9..14c501b0049 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -1898,7 +1898,7 @@ impl<'tcx> PolyTraitRef<'tcx> {
 /// erase, or otherwise "discharge" these bound regions, we change the
 /// type from `Binder<T>` to just `T` (see
 /// e.g. `liberate_late_bound_regions`).
-#[derive(Clone, PartialEq, Eq, Hash, Debug)]
+#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
 pub struct Binder<T>(pub T);
 
 impl<T> Binder<T> {
diff --git a/src/test/run-pass/infer-from-object-trait-issue-26952.rs b/src/test/run-pass/infer-from-object-trait-issue-26952.rs
new file mode 100644
index 00000000000..d5ca90c1a28
--- /dev/null
+++ b/src/test/run-pass/infer-from-object-trait-issue-26952.rs
@@ -0,0 +1,33 @@
+// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Test that when we match a trait reference like `Foo<A>: Foo<_#0t>`,
+// we unify with `_#0t` with `A`. In this code, if we failed to do
+// that, then you get an unconstrained type-variable in `call`.
+//
+// Also serves as a regression test for issue #26952, though the test
+// was derived from another reported regression with the same cause.
+
+use std::marker::PhantomData;
+
+trait Trait<A> { fn foo(&self); }
+
+struct Type<A> { a: PhantomData<A> }
+
+fn as_trait<A>(t: &Type<A>) -> &Trait<A> { loop {  } }
+
+fn want<A,T:Trait<A>+?Sized>(t: &T) { }
+
+fn call<A>(p: Type<A>) {
+    let q = as_trait(&p);
+    want(q); // parameter A to `want` *would* be unconstrained
+}
+
+fn main() { }