Auto merge of #29209 - arielb1:exponential-evaluation, r=nmatsakis

This fixes an exponential worst-case and also provides an additional 1% perf improvement.

r? @nikomatsakis

7 files changed, 150 insertions, 10 deletions

diff --git a/src/test/compile-fail/cast-rfc0401.rs b/src/test/compile-fail/cast-rfc0401.rs
index 4603ed00347..d14b0fa9e66 100644
--- a/src/test/compile-fail/cast-rfc0401.rs
+++ b/src/test/compile-fail/cast-rfc0401.rs
@@ -37,6 +37,7 @@ fn main()
     let f: f32 = 1.2;
     let v = 0 as *const u8;
     let fat_v : *const [u8] = unsafe { &*(0 as *const [u8; 1])};
+    let fat_sv : *const [i8] = unsafe { &*(0 as *const [i8; 1])};
     let foo: &Foo = &f;
 
     let _ = v as &u8; //~ ERROR non-scalar
@@ -94,7 +95,7 @@ fn main()
     let _ = main as *mut str; //~ ERROR casting
     let _ = &f as *mut f32; //~ ERROR casting
     let _ = &f as *const f64; //~ ERROR casting
-    let _ = fat_v as usize;
+    let _ = fat_sv as usize;
     //~^ ERROR casting
     //~^^ HELP through a thin pointer first
 
@@ -106,7 +107,7 @@ fn main()
     let _ = main.f as *const u32; //~ ERROR attempted access of field
 
     let cf: *const Foo = &0;
-    let _ = cf as *const [u8];
+    let _ = cf as *const [u16];
     //~^ ERROR casting
     //~^^ NOTE vtable kinds
     let _ = cf as *const Bar;
diff --git a/src/test/compile-fail/infinite-instantiation.rs b/src/test/compile-fail/infinite-instantiation.rs
index 9b02bf4cb85..28806b6e2ab 100644
--- a/src/test/compile-fail/infinite-instantiation.rs
+++ b/src/test/compile-fail/infinite-instantiation.rs
@@ -8,7 +8,6 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-//~^^^^^^^^^^ ERROR overflow
 //
 // We get an error message at the top of file (dummy span).
 // This is not helpful, but also kind of annoying to prevent,
@@ -32,6 +31,7 @@ impl<T:Clone> ToOpt for Option<T> {
 }
 
 fn function<T:ToOpt + Clone>(counter: usize, t: T) {
+//~^ ERROR reached the recursion limit during monomorphization
     if counter > 0 {
         function(counter - 1, t.to_option());
         // FIXME(#4287) Error message should be here. It should be
diff --git a/src/test/compile-fail/issue-29147.rs b/src/test/compile-fail/issue-29147.rs
new file mode 100644
index 00000000000..64bfa232f3f
--- /dev/null
+++ b/src/test/compile-fail/issue-29147.rs
@@ -0,0 +1,32 @@
+// 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.
+
+#![recursion_limit="1024"]
+
+pub struct S0<T>(T,T);
+pub struct S1<T>(Option<Box<S0<S0<T>>>>,Option<Box<S0<S0<T>>>>);
+pub struct S2<T>(Option<Box<S1<S1<T>>>>,Option<Box<S1<S1<T>>>>);
+pub struct S3<T>(Option<Box<S2<S2<T>>>>,Option<Box<S2<S2<T>>>>);
+pub struct S4<T>(Option<Box<S3<S3<T>>>>,Option<Box<S3<S3<T>>>>);
+pub struct S5<T>(Option<Box<S4<S4<T>>>>,Option<Box<S4<S4<T>>>>,Option<T>);
+
+trait Foo { fn xxx(&self); }
+trait Bar {} // anything local or #[fundamental]
+
+impl<T> Foo for T where T: Bar, T: Sync {
+    fn xxx(&self) {}
+}
+
+impl Foo for S5<u32> { fn xxx(&self) {} }
+impl Foo for S5<u64> { fn xxx(&self) {} }
+
+fn main() {
+    let _ = <S5<_>>::xxx; //~ ERROR cannot resolve `S5<_> : Foo`
+}
diff --git a/src/test/compile-fail/recursion.rs b/src/test/compile-fail/recursion.rs
index 55f3b995336..b1d45a82276 100644
--- a/src/test/compile-fail/recursion.rs
+++ b/src/test/compile-fail/recursion.rs
@@ -8,12 +8,6 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-//~^^^^^^^^^^ ERROR overflow
-//
-// We get an error message at the top of file (dummy span).
-// This is not helpful, but also kind of annoying to prevent,
-// so for now just live with it.
-
 enum Nil {NilValue}
 struct Cons<T> {head:isize, tail:T}
 trait Dot {fn dot(&self, other:Self) -> isize;}
@@ -26,7 +20,7 @@ impl<T:Dot> Dot for Cons<T> {
   }
 }
 fn test<T:Dot> (n:isize, i:isize, first:T, second:T) ->isize {
-  match n {    0 => {first.dot(second)}
+  match n {    0 => {first.dot(second)} //~ ERROR overflow
       // FIXME(#4287) Error message should be here. It should be
       // a type error to instantiate `test` at a type other than T.
     _ => {test (n-1, i+1, Cons {head:2*i+1, tail:first}, Cons{head:i*i, tail:second})}
diff --git a/src/test/run-pass/coherence-rfc447-constrained.rs b/src/test/run-pass/coherence-rfc447-constrained.rs
new file mode 100644
index 00000000000..4b52378e508
--- /dev/null
+++ b/src/test/run-pass/coherence-rfc447-constrained.rs
@@ -0,0 +1,31 @@
+// 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.
+
+// check that trait matching can handle impls whose types are only
+// constrained by a projection.
+
+trait IsU32 {}
+impl IsU32 for u32 {}
+
+trait Mirror { type Image: ?Sized; }
+impl<T: ?Sized> Mirror for T { type Image = T; }
+
+trait Bar {}
+impl<U: Mirror, V: Mirror<Image=L>, L: Mirror<Image=U>> Bar for V
+    where U::Image: IsU32 {}
+
+trait Foo { fn name() -> &'static str; }
+impl Foo for u64 { fn name() -> &'static str { "u64" } }
+impl<T: Bar> Foo for T { fn name() -> &'static str { "Bar" }}
+
+fn main() {
+    assert_eq!(<u64 as Foo>::name(), "u64");
+    assert_eq!(<u32 as Foo>::name(), "Bar");
+}
diff --git a/src/test/run-pass/issue-29147.rs b/src/test/run-pass/issue-29147.rs
new file mode 100644
index 00000000000..026b98905d0
--- /dev/null
+++ b/src/test/run-pass/issue-29147.rs
@@ -0,0 +1,36 @@
+// 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.
+
+#![recursion_limit="1024"]
+
+use std::mem;
+
+pub struct S0<T>(T,T);
+pub struct S1<T>(Option<Box<S0<S0<T>>>>,Option<Box<S0<S0<T>>>>);
+pub struct S2<T>(Option<Box<S1<S1<T>>>>,Option<Box<S1<S1<T>>>>);
+pub struct S3<T>(Option<Box<S2<S2<T>>>>,Option<Box<S2<S2<T>>>>);
+pub struct S4<T>(Option<Box<S3<S3<T>>>>,Option<Box<S3<S3<T>>>>);
+pub struct S5<T>(Option<Box<S4<S4<T>>>>,Option<Box<S4<S4<T>>>>,Option<T>);
+
+trait Foo { fn xxx(&self); }
+/// some local of #[fundamental] trait
+trait Bar {}
+
+impl<T> Foo for T where T: Bar, T: Sync {
+    fn xxx(&self) {}
+}
+
+impl Foo for S5<u8> { fn xxx(&self) {} }
+
+fn main() {
+    let s = S5(None,None,None);
+    s.xxx();
+    assert_eq!(mem::size_of_val(&s.2), mem::size_of::<Option<u8>>());
+}
diff --git a/src/test/run-pass/trait-copy-guessing.rs b/src/test/run-pass/trait-copy-guessing.rs
new file mode 100644
index 00000000000..71cd3c9441e
--- /dev/null
+++ b/src/test/run-pass/trait-copy-guessing.rs
@@ -0,0 +1,46 @@
+// 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.
+
+// "guessing" in trait selection can affect `copy_or_move`. Check that this
+// is correctly handled. I am not sure what is the "correct" behaviour,
+// but we should at least not ICE.
+
+use std::mem;
+
+struct U([u8; 1337]);
+
+struct S<'a,T:'a>(&'a T);
+impl<'a, T> Clone for S<'a, T> { fn clone(&self) -> Self { S(self.0) } }
+/// This impl triggers inference "guessing" - S<_>: Copy => _ = U
+impl<'a> Copy for S<'a, Option<U>> {}
+
+fn assert_impls_fn<R,T: Fn()->R>(_: &T){}
+
+fn main() {
+    let n = None;
+    let e = S(&n);
+    let f = || {
+        // S being copy is critical for this to work
+        drop(e);
+        mem::size_of_val(e.0)
+    };
+    assert_impls_fn(&f);
+    assert_eq!(f(), 1337+1);
+
+    assert_eq!((|| {
+        // S being Copy is not critical here, but
+        // we check it anyway.
+        let n = None;
+        let e = S(&n);
+        let ret = mem::size_of_val(e.0);
+        drop(e);
+        ret
+    })(), 1337+1);
+}