rollup merge of #20757: nikomatsakis/issue-20624-assoc-types-coherence

11 files changed, 276 insertions, 33 deletions

diff --git a/src/librustc/lib.rs b/src/librustc/lib.rs
index 48e0d40bb5d..fb7c5296d02 100644
--- a/src/librustc/lib.rs
+++ b/src/librustc/lib.rs
@@ -29,7 +29,6 @@
 #![feature(box_syntax)]
 #![allow(unknown_features)] #![feature(int_uint)]
 #![feature(rustc_diagnostic_macros)]
-#![feature(old_impl_check)]
 
 extern crate arena;
 extern crate flate;
diff --git a/src/librustc/middle/subst.rs b/src/librustc/middle/subst.rs
index 5fbae6c359d..9ac6b8a86b6 100644
--- a/src/librustc/middle/subst.rs
+++ b/src/librustc/middle/subst.rs
@@ -313,6 +313,17 @@ impl<T> VecPerParamSpace<T> {
         self.content.insert(limit, value);
     }
 
+    /// Appends `values` to the vector associated with `space`.
+    ///
+    /// Unlike the `extend` method in `Vec`, this should not be assumed
+    /// to be a cheap operation (even when amortized over many calls).
+    pub fn extend<I:Iterator<Item=T>>(&mut self, space: ParamSpace, mut values: I) {
+        // This could be made more efficient, obviously.
+        for item in values {
+            self.push(space, item);
+        }
+    }
+
     pub fn pop(&mut self, space: ParamSpace) -> Option<T> {
         let (start, limit) = self.limits(space);
         if start == limit {
diff --git a/src/librustc/middle/traits/coherence.rs b/src/librustc/middle/traits/coherence.rs
index 489731e7554..b6d45ab89e7 100644
--- a/src/librustc/middle/traits/coherence.rs
+++ b/src/librustc/middle/traits/coherence.rs
@@ -12,6 +12,7 @@
 
 use super::SelectionContext;
 use super::{Obligation, ObligationCause};
+use super::project;
 use super::util;
 
 use middle::subst::{Subst};
@@ -34,22 +35,28 @@ pub fn impl_can_satisfy(infcx: &InferCtxt,
            impl1_def_id.repr(infcx.tcx),
            impl2_def_id.repr(infcx.tcx));
 
+    let param_env = ty::empty_parameter_environment(infcx.tcx);
+    let mut selcx = SelectionContext::intercrate(infcx, &param_env);
+    let cause = ObligationCause::dummy();
+
     // `impl1` provides an implementation of `Foo<X,Y> for Z`.
     let impl1_substs =
         util::fresh_substs_for_impl(infcx, DUMMY_SP, impl1_def_id);
     let impl1_trait_ref =
         (*ty::impl_trait_ref(infcx.tcx, impl1_def_id).unwrap()).subst(infcx.tcx, &impl1_substs);
+    let impl1_trait_ref =
+        project::normalize(&mut selcx, cause.clone(), &impl1_trait_ref);
 
     // Determine whether `impl2` can provide an implementation for those
     // same types.
-    let param_env = ty::empty_parameter_environment(infcx.tcx);
-    let mut selcx = SelectionContext::intercrate(infcx, &param_env);
-    let obligation = Obligation::new(ObligationCause::dummy(),
+    let obligation = Obligation::new(cause,
                                      ty::Binder(ty::TraitPredicate {
-                                         trait_ref: Rc::new(impl1_trait_ref),
+                                         trait_ref: Rc::new(impl1_trait_ref.value),
                                      }));
     debug!("impl_can_satisfy(obligation={})", obligation.repr(infcx.tcx));
-    selcx.evaluate_impl(impl2_def_id, &obligation)
+    selcx.evaluate_impl(impl2_def_id, &obligation) &&
+        impl1_trait_ref.obligations.iter().all(
+            |o| selcx.evaluate_obligation(o))
 }
 
 #[allow(missing_copy_implementations)]
diff --git a/src/librustc/middle/traits/project.rs b/src/librustc/middle/traits/project.rs
index aaf5df4ce4a..95a938328cf 100644
--- a/src/librustc/middle/traits/project.rs
+++ b/src/librustc/middle/traits/project.rs
@@ -206,6 +206,7 @@ impl<'a,'b,'tcx> TypeFolder<'tcx> for AssociatedTypeNormalizer<'a,'b,'tcx> {
         // normalize it when we instantiate those bound regions (which
         // should occur eventually).
 
+        let ty = ty_fold::super_fold_ty(self, ty);
         match ty.sty {
             ty::ty_projection(ref data) if !data.has_escaping_regions() => { // (*)
 
@@ -229,8 +230,9 @@ impl<'a,'b,'tcx> TypeFolder<'tcx> for AssociatedTypeNormalizer<'a,'b,'tcx> {
                 self.obligations.extend(obligations.into_iter());
                 ty
             }
+
             _ => {
-                ty_fold::super_fold_ty(self, ty)
+                ty
             }
         }
     }
@@ -243,6 +245,12 @@ pub struct Normalized<'tcx,T> {
 
 pub type NormalizedTy<'tcx> = Normalized<'tcx, Ty<'tcx>>;
 
+impl<'tcx,T> Normalized<'tcx,T> {
+    pub fn with<U>(self, value: U) -> Normalized<'tcx,U> {
+        Normalized { value: value, obligations: self.obligations }
+    }
+}
+
 pub fn normalize_projection_type<'a,'b,'tcx>(
     selcx: &'a mut SelectionContext<'b,'tcx>,
     projection_ty: ty::ProjectionTy<'tcx>,
diff --git a/src/librustc/middle/traits/select.rs b/src/librustc/middle/traits/select.rs
index dad74612369..d6302976b9f 100644
--- a/src/librustc/middle/traits/select.rs
+++ b/src/librustc/middle/traits/select.rs
@@ -19,6 +19,7 @@ use self::EvaluationResult::*;
 
 use super::{DerivedObligationCause};
 use super::{project};
+use super::project::Normalized;
 use super::{PredicateObligation, Obligation, TraitObligation, ObligationCause};
 use super::{ObligationCauseCode, BuiltinDerivedObligation};
 use super::{SelectionError, Unimplemented, Overflow, OutputTypeParameterMismatch};
@@ -1155,7 +1156,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                     let impl_trait_ref =
                         ty::impl_trait_ref(self.tcx(), impl_def_id).unwrap();
                     let impl_trait_ref =
-                        impl_trait_ref.subst(self.tcx(), &impl_substs);
+                        impl_trait_ref.subst(self.tcx(), &impl_substs.value);
                     let poly_impl_trait_ref =
                         ty::Binder(impl_trait_ref);
                     let origin =
@@ -1712,7 +1713,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             let substs =
                 self.rematch_impl(impl_def_id, obligation,
                                   snapshot, &skol_map, skol_obligation_trait_ref.trait_ref);
-            debug!("confirm_impl_candidate substs={:?}", substs);
+            debug!("confirm_impl_candidate substs={}", substs.repr(self.tcx()));
             Ok(self.vtable_impl(impl_def_id, substs, obligation.cause.clone(),
                                 obligation.recursion_depth + 1, skol_map, snapshot))
         })
@@ -1720,7 +1721,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
     fn vtable_impl(&mut self,
                    impl_def_id: ast::DefId,
-                   substs: Substs<'tcx>,
+                   substs: Normalized<'tcx, Substs<'tcx>>,
                    cause: ObligationCause<'tcx>,
                    recursion_depth: uint,
                    skol_map: infer::SkolemizationMap,
@@ -1733,21 +1734,23 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                recursion_depth,
                skol_map.repr(self.tcx()));
 
-        let impl_predicates =
-            self.impl_predicates(cause,
+        let mut impl_obligations =
+            self.impl_obligations(cause,
                                  recursion_depth,
                                  impl_def_id,
-                                 &substs,
+                                 &substs.value,
                                  skol_map,
                                  snapshot);
 
-        debug!("vtable_impl: impl_def_id={} impl_predicates={}",
+        debug!("vtable_impl: impl_def_id={} impl_obligations={}",
                impl_def_id.repr(self.tcx()),
-               impl_predicates.repr(self.tcx()));
+               impl_obligations.repr(self.tcx()));
+
+        impl_obligations.extend(TypeSpace, substs.obligations.into_iter());
 
         VtableImplData { impl_def_id: impl_def_id,
-                         substs: substs,
-                         nested: impl_predicates }
+                         substs: substs.value,
+                         nested: impl_obligations }
     }
 
     fn confirm_object_candidate(&mut self,
@@ -1931,7 +1934,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                     snapshot: &infer::CombinedSnapshot,
                     skol_map: &infer::SkolemizationMap,
                     skol_obligation_trait_ref: Rc<ty::TraitRef<'tcx>>)
-                    -> Substs<'tcx>
+                    -> Normalized<'tcx, Substs<'tcx>>
     {
         match self.match_impl(impl_def_id, obligation, snapshot,
                               skol_map, skol_obligation_trait_ref) {
@@ -1953,7 +1956,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                   snapshot: &infer::CombinedSnapshot,
                   skol_map: &infer::SkolemizationMap,
                   skol_obligation_trait_ref: Rc<ty::TraitRef<'tcx>>)
-                  -> Result<Substs<'tcx>, ()>
+                  -> Result<Normalized<'tcx, Substs<'tcx>>, ()>
     {
         let impl_trait_ref = ty::impl_trait_ref(self.tcx(), impl_def_id).unwrap();
 
@@ -1971,6 +1974,12 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         let impl_trait_ref = impl_trait_ref.subst(self.tcx(),
                                                   &impl_substs);
 
+        let impl_trait_ref =
+            project::normalize_with_depth(self,
+                                          obligation.cause.clone(),
+                                          obligation.recursion_depth + 1,
+                                          &impl_trait_ref);
+
         debug!("match_impl(impl_def_id={}, obligation={}, \
                impl_trait_ref={}, skol_obligation_trait_ref={})",
                impl_def_id.repr(self.tcx()),
@@ -1981,7 +1990,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         let origin = infer::RelateOutputImplTypes(obligation.cause.span);
         match self.infcx.sub_trait_refs(false,
                                         origin,
-                                        impl_trait_ref,
+                                        impl_trait_ref.value.clone(),
                                         skol_obligation_trait_ref) {
             Ok(()) => { }
             Err(e) => {
@@ -2001,7 +2010,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         }
 
         debug!("match_impl: success impl_substs={}", impl_substs.repr(self.tcx()));
-        Ok(impl_substs)
+        Ok(Normalized { value: impl_substs,
+                        obligations: impl_trait_ref.obligations })
     }
 
     fn fast_reject_trait_refs(&mut self,
@@ -2142,14 +2152,14 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         }
     }
 
-    fn impl_predicates(&mut self,
-                       cause: ObligationCause<'tcx>,
-                       recursion_depth: uint,
-                       impl_def_id: ast::DefId,
-                       impl_substs: &Substs<'tcx>,
-                       skol_map: infer::SkolemizationMap,
-                       snapshot: &infer::CombinedSnapshot)
-                       -> VecPerParamSpace<PredicateObligation<'tcx>>
+    fn impl_obligations(&mut self,
+                        cause: ObligationCause<'tcx>,
+                        recursion_depth: uint,
+                        impl_def_id: ast::DefId,
+                        impl_substs: &Substs<'tcx>,
+                        skol_map: infer::SkolemizationMap,
+                        snapshot: &infer::CombinedSnapshot)
+                        -> VecPerParamSpace<PredicateObligation<'tcx>>
     {
         let impl_generics = ty::lookup_item_type(self.tcx(), impl_def_id).generics;
         let bounds = impl_generics.to_bounds(self.tcx(), impl_substs);
@@ -2162,9 +2172,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                                           cause,
                                           recursion_depth,
                                           &normalized_bounds.value);
-        for obligation in normalized_bounds.obligations.into_iter() {
-            impl_obligations.push(TypeSpace, obligation);
-        }
+        impl_obligations.extend(TypeSpace, normalized_bounds.obligations.into_iter());
         impl_obligations
     }
 
diff --git a/src/librustc_typeck/check/wf.rs b/src/librustc_typeck/check/wf.rs
index b17ecdaf59c..89de1ea80fc 100644
--- a/src/librustc_typeck/check/wf.rs
+++ b/src/librustc_typeck/check/wf.rs
@@ -235,9 +235,16 @@ impl<'ccx, 'tcx> CheckTypeWellFormedVisitor<'ccx, 'tcx> {
             // Find the supertrait bounds. This will add `int:Bar`.
             let poly_trait_ref = ty::Binder(trait_ref);
             let predicates = ty::predicates_for_trait_ref(fcx.tcx(), &poly_trait_ref);
-            for predicate in predicates.into_iter() {
+            let predicates = {
+                let selcx = &mut traits::SelectionContext::new(fcx.infcx(), fcx);
+                traits::normalize(selcx, cause.clone(), &predicates)
+            };
+            for predicate in predicates.value.into_iter() {
                 fcx.register_predicate(traits::Obligation::new(cause.clone(), predicate));
             }
+            for obligation in predicates.obligations.into_iter() {
+                fcx.register_predicate(obligation);
+            }
         });
     }
 }
diff --git a/src/test/compile-fail/associated-types-coherence-failure.rs b/src/test/compile-fail/associated-types-coherence-failure.rs
new file mode 100644
index 00000000000..95a68dd6698
--- /dev/null
+++ b/src/test/compile-fail/associated-types-coherence-failure.rs
@@ -0,0 +1,59 @@
+// Copyright 2014 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 coherence detects overlap when some of the types in the
+// impls are projections of associated type. Issue #20624.
+
+use std::ops::Deref;
+
+pub struct Cow<'a, B: ?Sized>;
+
+/// Trait for moving into a `Cow`
+pub trait IntoCow<'a, B: ?Sized> {
+    /// Moves `self` into `Cow`
+    fn into_cow(self) -> Cow<'a, B>;
+}
+
+impl<'a, B: ?Sized> IntoCow<'a, B> for Cow<'a, B> where B: ToOwned {
+//~^ ERROR E0119
+    fn into_cow(self) -> Cow<'a, B> {
+        self
+    }
+}
+
+impl<'a, B: ?Sized> IntoCow<'a, B> for <B as ToOwned>::Owned where B: ToOwned {
+//~^ ERROR E0119
+    fn into_cow(self) -> Cow<'a, B> {
+        Cow
+    }
+}
+
+impl<'a, B: ?Sized> IntoCow<'a, B> for &'a B where B: ToOwned {
+    fn into_cow(self) -> Cow<'a, B> {
+        Cow
+    }
+}
+
+impl ToOwned for u8 {
+    type Owned = &'static u8;
+    fn to_owned(&self) -> &'static u8 { panic!() }
+}
+
+/// A generalization of Clone to borrowed data.
+pub trait ToOwned {
+    type Owned;
+
+    /// Create owned data from borrowed data, usually by copying.
+    fn to_owned(&self) -> Self::Owned;
+}
+
+
+fn main() {}
+
diff --git a/src/test/run-pass/associated-type-doubleendediterator-object.rs b/src/test/run-pass/associated-types-doubleendediterator-object.rs
index 7365e052171..7365e052171 100644
--- a/src/test/run-pass/associated-type-doubleendediterator-object.rs
+++ b/src/test/run-pass/associated-types-doubleendediterator-object.rs
diff --git a/src/test/run-pass/associated-types-nested-projections.rs b/src/test/run-pass/associated-types-nested-projections.rs
new file mode 100644
index 00000000000..a907b9fcde5
--- /dev/null
+++ b/src/test/run-pass/associated-types-nested-projections.rs
@@ -0,0 +1,50 @@
+// Copyright 2015 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 we can resolve nested projection types. Issue #20666.
+
+use std::slice;
+
+trait Bound {}
+
+impl<'a> Bound for &'a int {}
+
+trait IntoIterator {
+    type Iter: Iterator;
+
+    fn into_iter(self) -> Self::Iter;
+}
+
+impl<'a, T> IntoIterator for &'a [T; 3] {
+    type Iter = slice::Iter<'a, T>;
+
+    fn into_iter(self) -> slice::Iter<'a, T> {
+        self.iter()
+    }
+}
+
+fn foo<X>(x: X) where
+    X: IntoIterator,
+    <<X as IntoIterator>::Iter as Iterator>::Item: Bound,
+{
+}
+
+fn bar<T, I, X>(x: X) where
+    T: Bound,
+    I: Iterator<Item=T>,
+    X: IntoIterator<Iter=I>,
+{
+
+}
+
+fn main() {
+    foo(&[0i, 1, 2]);
+    bar(&[0i, 1, 2]);
+}
diff --git a/src/test/run-pass/associated-types-projection-from-known-type-in-impl.rs b/src/test/run-pass/associated-types-projection-from-known-type-in-impl.rs
new file mode 100644
index 00000000000..0a1a8589dec
--- /dev/null
+++ b/src/test/run-pass/associated-types-projection-from-known-type-in-impl.rs
@@ -0,0 +1,44 @@
+// Copyright 2015 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 where the impl self type uses a projection from a constant type.
+
+trait Int
+{
+    type T;
+}
+
+trait NonZero
+{
+    fn non_zero(self) -> bool;
+}
+
+impl Int for i32 { type T = i32; }
+impl Int for i64 { type T = i64; }
+impl Int for u32 { type T = u32; }
+impl Int for u64 { type T = u64; }
+
+impl NonZero for <i32 as Int>::T { fn non_zero(self) -> bool { self != 0 } }
+impl NonZero for <i64 as Int>::T { fn non_zero(self) -> bool { self != 0 } }
+impl NonZero for <u32 as Int>::T { fn non_zero(self) -> bool { self != 0 } }
+impl NonZero for <u64 as Int>::T { fn non_zero(self) -> bool { self != 0 } }
+
+fn main ()
+{
+    assert!(NonZero::non_zero(22_i32));
+    assert!(NonZero::non_zero(22_i64));
+    assert!(NonZero::non_zero(22_u32));
+    assert!(NonZero::non_zero(22_u64));
+
+    assert!(!NonZero::non_zero(0_i32));
+    assert!(!NonZero::non_zero(0_i64));
+    assert!(!NonZero::non_zero(0_u32));
+    assert!(!NonZero::non_zero(0_u64));
+}
diff --git a/src/test/run-pass/associated-types-projection-in-supertrait.rs b/src/test/run-pass/associated-types-projection-in-supertrait.rs
new file mode 100644
index 00000000000..e6fec675b03
--- /dev/null
+++ b/src/test/run-pass/associated-types-projection-in-supertrait.rs
@@ -0,0 +1,50 @@
+// Copyright 2015 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 we are handle to correctly handle a projection type
+// that appears in a supertrait bound. Issue #20559.
+
+trait A
+{
+    type TA;
+}
+
+trait B<TB>
+{
+    fn foo (&self, t : TB) -> String;
+}
+
+trait C<TC : A> : B<<TC as A>::TA> { }
+
+struct X;
+
+impl A for X
+{
+    type TA = i32;
+}
+
+struct Y;
+
+impl C<X> for Y { }
+
+// Both of these impls are required for successful compilation
+impl B<i32> for Y
+{
+    fn foo (&self, t : i32) -> String
+    {
+        format!("First {}", t)
+    }
+}
+
+fn main ()
+{
+    let y = Y;
+    assert_eq!(y.foo(5), format!("First 5"));
+}