Allow writing types which "can't" be instantiated.

The borrow checker doesn't allow constructing such a type at runtime
using safe code, but there isn't any reason to ban them in the type checker.

Included in this commit is an example of a neat static doubly-linked list.

Feature-gated under the static_recursion gate to be on the safe side, but
there are unlikely to be any reasons this shouldn't be turned on by
default.

7 files changed, 72 insertions, 46 deletions

diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index 9486e4953f8..082dafc72bc 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -115,6 +115,7 @@ use syntax::attr::AttrMetaMethods;
 use syntax::ast::{self, DefId, Visibility};
 use syntax::ast_util::{self, local_def};
 use syntax::codemap::{self, Span};
+use syntax::feature_gate::emit_feature_err;
 use syntax::owned_slice::OwnedSlice;
 use syntax::parse::token;
 use syntax::print::pprust;
@@ -4009,9 +4010,7 @@ fn check_const_with_ty<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
 
 /// Checks whether a type can be represented in memory. In particular, it
 /// identifies types that contain themselves without indirection through a
-/// pointer, which would mean their size is unbounded. This is different from
-/// the question of whether a type can be instantiated. See the definition of
-/// `check_instantiable`.
+/// pointer, which would mean their size is unbounded.
 pub fn check_representable(tcx: &ty::ctxt,
                            sp: Span,
                            item_id: ast::NodeId,
@@ -4036,31 +4035,19 @@ pub fn check_representable(tcx: &ty::ctxt,
     return true
 }
 
-/// Checks whether a type can be created without an instance of itself.
-/// This is similar but different from the question of whether a type
-/// can be represented.  For example, the following type:
-///
-///     enum foo { None, Some(foo) }
-///
-/// is instantiable but is not representable.  Similarly, the type
-///
-///     enum foo { Some(@foo) }
-///
-/// is representable, but not instantiable.
+/// Checks whether a type can be constructed at runtime without
+/// an existing instance of that type.
 pub fn check_instantiable(tcx: &ty::ctxt,
                           sp: Span,
-                          item_id: ast::NodeId)
-                          -> bool {
+                          item_id: ast::NodeId) {
     let item_ty = tcx.node_id_to_type(item_id);
-    if !item_ty.is_instantiable(tcx) {
-        span_err!(tcx.sess, sp, E0073,
-            "this type cannot be instantiated without an \
-             instance of itself");
-        fileline_help!(tcx.sess, sp, "consider using `Option<{:?}>`",
-             item_ty);
-        false
-    } else {
-        true
+    if !item_ty.is_instantiable(tcx) &&
+            !tcx.sess.features.borrow().static_recursion {
+        emit_feature_err(&tcx.sess.parse_sess.span_diagnostic,
+                         "static_recursion",
+                         sp,
+                         "this type cannot be instantiated at runtime \
+                          without an instance of itself");
     }
 }
 
@@ -4199,11 +4186,6 @@ pub fn check_enum_variants<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
     do_check(ccx, vs, id, hint);
 
     check_representable(ccx.tcx, sp, id, "enum");
-
-    // Check that it is possible to instantiate this enum:
-    //
-    // This *sounds* like the same that as representable, but it's
-    // not.  See def'n of `check_instantiable()` for details.
     check_instantiable(ccx.tcx, sp, id);
 }
 
diff --git a/src/test/compile-fail/issue-3008-2.rs b/src/test/compile-fail/issue-3008-2.rs
index c744dff0c04..2f1fa6780ab 100644
--- a/src/test/compile-fail/issue-3008-2.rs
+++ b/src/test/compile-fail/issue-3008-2.rs
@@ -8,10 +8,11 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+#![feature(static_recursion)]
+
 enum foo { foo_(bar) }
 struct bar { x: bar }
 //~^ ERROR illegal recursive struct type; wrap the inner value in a box to make it representable
-//~^^ ERROR this type cannot be instantiated without an instance of itself
 
 fn main() {
 }
diff --git a/src/test/compile-fail/static-recursion-gate-2.rs b/src/test/compile-fail/static-recursion-gate-2.rs
new file mode 100644
index 00000000000..de038924840
--- /dev/null
+++ b/src/test/compile-fail/static-recursion-gate-2.rs
@@ -0,0 +1,14 @@
+// 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.
+
+struct Z(&'static Z);
+//~^ ERROR this type cannot be instantiated
+
+pub fn main() {}
diff --git a/src/test/compile-fail/type-recursive.rs b/src/test/compile-fail/type-recursive.rs
index 9dcb60628a9..b972934d060 100644
--- a/src/test/compile-fail/type-recursive.rs
+++ b/src/test/compile-fail/type-recursive.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-// error-pattern:this type cannot be instantiated
+// error-pattern:illegal recursive struct type
 struct t1 {
     foo: isize,
     foolish: t1
diff --git a/src/test/compile-fail/issue-2063-resource.rs b/src/test/run-pass/issue-2063-resource.rs
index 30cf7ee7d88..aa9a7afc37f 100644
--- a/src/test/compile-fail/issue-2063-resource.rs
+++ b/src/test/run-pass/issue-2063-resource.rs
@@ -8,15 +8,17 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+#![feature(static_recursion)]
 
 // test that autoderef of a type like this does not
 // cause compiler to loop.  Note that no instances
 // of such a type could ever be constructed.
-struct S { //~ ERROR this type cannot be instantiated
+
+struct S {
   x: X,
   to_str: (),
 }
 
-struct X(Box<S>); //~ ERROR this type cannot be instantiated
+struct X(Box<S>);
 
 fn main() {}
diff --git a/src/test/compile-fail/issue-2063.rs b/src/test/run-pass/issue-2063.rs
index 20bd8af7c3e..48da7ecc508 100644
--- a/src/test/compile-fail/issue-2063.rs
+++ b/src/test/run-pass/issue-2063.rs
@@ -8,28 +8,25 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+#![feature(static_recursion)]
+
 // test that autoderef of a type like this does not
 // cause compiler to loop.  Note that no instances
 // of such a type could ever be constructed.
 
-struct t(Box<t>); //~ ERROR this type cannot be instantiated
+struct T(Box<T>);
 
-trait to_str_2 {
-    fn my_to_string() -> String;
+trait ToStr2 {
+    fn my_to_string(&self) -> String;
 }
 
-// I use an impl here because it will cause
-// the compiler to attempt autoderef and then
-// try to resolve the method.
-impl to_str_2 for t {
-    fn my_to_string() -> String { "t".to_string() }
+impl ToStr2 for T {
+    fn my_to_string(&self) -> String { "t".to_string() }
 }
 
-fn new_t(x: t) {
+#[allow(dead_code)]
+fn new_t(x: T) {
     x.my_to_string();
-    // (there used to be an error emitted right here as well. It was
-    // spurious, at best; if `t` did exist as a type, it clearly would
-    // have an impl of the `to_str_2` trait.)
 }
 
 fn main() {
diff --git a/src/test/run-pass/static-recursive.rs b/src/test/run-pass/static-recursive.rs
index 171aef522d4..f3db102ea5a 100644
--- a/src/test/run-pass/static-recursive.rs
+++ b/src/test/run-pass/static-recursive.rs
@@ -12,6 +12,36 @@
 
 static mut S: *const u8 = unsafe { &S as *const *const u8 as *const u8 };
 
+struct StaticDoubleLinked {
+    prev: &'static StaticDoubleLinked,
+    next: &'static StaticDoubleLinked,
+    data: i32,
+    head: bool
+}
+
+static L1: StaticDoubleLinked = StaticDoubleLinked{prev: &L3, next: &L2, data: 1, head: true};
+static L2: StaticDoubleLinked = StaticDoubleLinked{prev: &L1, next: &L3, data: 2, head: false};
+static L3: StaticDoubleLinked = StaticDoubleLinked{prev: &L2, next: &L1, data: 3, head: false};
+
+
 pub fn main() {
     unsafe { assert_eq!(S, *(S as *const *const u8)); }
+
+    let mut test_vec = Vec::new();
+    let mut cur = &L1;
+    loop {
+        test_vec.push(cur.data);
+        cur = cur.next;
+        if cur.head { break }
+    }
+    assert_eq!(&test_vec, &[1,2,3]);
+
+    let mut test_vec = Vec::new();
+    let mut cur = &L1;
+    loop {
+        cur = cur.prev;
+        test_vec.push(cur.data);
+        if cur.head { break }
+    }
+    assert_eq!(&test_vec, &[3,2,1]);
 }