Detect and report types which could never be instantiated.

Fixes #2063.

2 files changed, 163 insertions, 3 deletions

diff --git a/src/rustc/middle/ty.rs b/src/rustc/middle/ty.rs
index 93ddbee1656..bfaf356a3e5 100644
--- a/src/rustc/middle/ty.rs
+++ b/src/rustc/middle/ty.rs
@@ -15,6 +15,7 @@ import util::ppaux::ty_to_str;
 import util::ppaux::ty_constr_to_str;
 import syntax::print::pprust::*;
 
+export is_instantiable;
 export node_id_to_type;
 export node_id_to_type_params;
 export arg;
@@ -1007,6 +1008,136 @@ fn type_kind(cx: ctxt, ty: t) -> kind {
     ret result;
 }
 
+// True if instantiating an instance of `ty` requires an instead of `r_ty`.
+fn is_instantiable(cx: ctxt, r_ty: t) -> bool {
+
+    fn type_requires(cx: ctxt, seen: @mut [def_id],
+                     r_ty: t, ty: t) -> bool {
+        #debug["type_requires(%s, %s)?",
+               ty_to_str(cx, r_ty),
+               ty_to_str(cx, ty)];
+
+        let r = {
+            get(r_ty).struct == get(ty).struct ||
+                subtypes_require(cx, seen, r_ty, ty)
+        };
+
+        #debug["type_requires(%s, %s)? %b",
+               ty_to_str(cx, r_ty),
+               ty_to_str(cx, ty),
+               r];
+        ret r;
+    }
+
+    fn subtypes_require(cx: ctxt, seen: @mut [def_id],
+                        r_ty: t, ty: t) -> bool {
+        #debug["subtypes_require(%s, %s)?",
+               ty_to_str(cx, r_ty),
+               ty_to_str(cx, ty)];
+
+        let r = alt get(ty).struct {
+          ty_nil |
+          ty_bot |
+          ty_bool |
+          ty_int(_) |
+          ty_uint(_) |
+          ty_float(_) |
+          ty_str |
+          ty_fn(_) |
+          ty_var(_) |
+          ty_param(_, _) |
+          ty_self(_) |
+          ty_type |
+          ty_opaque_box |
+          ty_opaque_closure_ptr(_) |
+          ty_vec(_) {
+            false
+          }
+
+          ty_constr(t, _) {
+            type_requires(cx, seen, r_ty, t)
+          }
+
+          ty_box(mt) |
+          ty_uniq(mt) |
+          ty_ptr(mt) |
+          ty_rptr(_, mt) {
+            be type_requires(cx, seen, r_ty, mt.ty);
+          }
+
+          ty_rec(fields) {
+            vec::any(fields) {|field|
+                type_requires(cx, seen, r_ty, field.mt.ty)
+            }
+          }
+
+          ty_iface(_, _) {
+            false
+          }
+
+          ty_class(did, _) if vec::contains(*seen, did) {
+            false
+          }
+
+          ty_class(did, tps) {
+            vec::push(*seen, did);
+            let r = vec::any(lookup_class_fields(cx, did)) {|f|
+                let fty = ty::lookup_item_type(cx, f.id);
+                let sty = substitute_type_params(cx, tps, fty.ty);
+                type_requires(cx, seen, r_ty, sty)
+            };
+            vec::pop(*seen);
+            r
+          }
+
+          ty_res(did, _, _) if vec::contains(*seen, did) {
+            false
+          }
+
+          ty_res(did, sub, tps) {
+            vec::push(*seen, did);
+            let sty = substitute_type_params(cx, tps, sub);
+            let r = type_requires(cx, seen, r_ty, sty);
+            vec::pop(*seen);
+            r
+          }
+
+          ty_tup(ts) {
+            vec::any(ts) {|t|
+                type_requires(cx, seen, r_ty, t)
+            }
+          }
+
+          ty_enum(did, _) if vec::contains(*seen, did) {
+            false
+          }
+
+          ty_enum(did, tps) {
+            vec::push(*seen, did);
+            let vs = enum_variants(cx, did);
+            let r = vec::len(*vs) > 0u && vec::all(*vs) {|variant|
+                vec::any(variant.args) {|aty|
+                    let sty = substitute_type_params(cx, tps, aty);
+                    type_requires(cx, seen, r_ty, sty)
+                }
+            };
+            vec::pop(*seen);
+            r
+          }
+        };
+
+        #debug["subtypes_require(%s, %s)? %b",
+               ty_to_str(cx, r_ty),
+               ty_to_str(cx, ty),
+               r];
+
+        ret r;
+    }
+
+    let seen = @mut [];
+    !subtypes_require(cx, seen, r_ty, r_ty)
+}
+
 fn type_structurally_contains(cx: ctxt, ty: t, test: fn(sty) -> bool) ->
    bool {
     let sty = get(ty).struct;
diff --git a/src/rustc/middle/typeck.rs b/src/rustc/middle/typeck.rs
index 6e11e483ecf..7d89091d475 100644
--- a/src/rustc/middle/typeck.rs
+++ b/src/rustc/middle/typeck.rs
@@ -1145,6 +1145,7 @@ mod unify {
 // instead of ty::struct.
 fn do_autoderef(fcx: @fn_ctxt, sp: span, t: ty::t) -> ty::t {
     let mut t1 = t;
+    let mut enum_dids = [];
     loop {
         alt structure_of(fcx, sp, t1) {
           ty::ty_box(inner) | ty::ty_uniq(inner) | ty::ty_rptr(_, inner) {
@@ -1161,6 +1162,16 @@ fn do_autoderef(fcx: @fn_ctxt, sp: span, t: ty::t) -> ty::t {
             t1 = ty::substitute_type_params(fcx.ccx.tcx, tps, inner);
           }
           ty::ty_enum(did, tps) {
+            // Watch out for a type like `enum t = @t`.  Such a type would
+            // otherwise infinitely auto-deref.  This is the only autoderef
+            // loop that needs to be concerned with this, as an error will be
+            // reported on the enum definition as well because the enum is not
+            // instantiable.
+            if vec::contains(enum_dids, did) {
+                ret t1;
+            }
+            vec::push(enum_dids, did);
+
             let variants = ty::enum_variants(fcx.ccx.tcx, did);
             if vec::len(*variants) != 1u || vec::len(variants[0].args) != 1u {
                 ret t1;
@@ -3396,6 +3407,18 @@ fn check_const(ccx: @crate_ctxt, _sp: span, e: @ast::expr, id: ast::node_id) {
     demand::simple(fcx, e.span, declty, cty);
 }
 
+fn check_instantiable(tcx: ty::ctxt,
+                      sp: span,
+                      item_id: ast::node_id) {
+    let rty = ty::node_id_to_type(tcx, item_id);
+    if !ty::is_instantiable(tcx, rty) {
+        tcx.sess.span_err(sp, #fmt["this type cannot be instantiated \
+                                    without an instance of itself. \
+                                    Consider using option<%s>.",
+                                   ty_to_str(tcx, rty)]);
+    }
+}
+
 fn check_enum_variants(ccx: @crate_ctxt, sp: span, vs: [ast::variant],
                       id: ast::node_id) {
     // FIXME: this is kinda a kludge; we manufacture a fake function context
@@ -3443,6 +3466,8 @@ fn check_enum_variants(ccx: @crate_ctxt, sp: span, vs: [ast::variant],
         disr_vals += [disr_val];
         disr_val += 1;
     }
+
+    // Check that it is possible to represent this enum:
     let mut outer = true, did = local_def(id);
     if ty::type_structurally_contains(ccx.tcx, rty, {|sty|
         alt sty {
@@ -3453,10 +3478,13 @@ fn check_enum_variants(ccx: @crate_ctxt, sp: span, vs: [ast::variant],
           _ { false }
         }
     }) {
-        ccx.tcx.sess.span_fatal(sp, "illegal recursive enum type. \
-                                     wrap the inner value in a box to \
-                                     make it represenable");
+        ccx.tcx.sess.span_err(sp, "illegal recursive enum type. \
+                                   wrap the inner value in a box to \
+                                   make it represenable");
     }
+
+    // Check that it is possible to instantiate this enum:
+    check_instantiable(ccx.tcx, sp, id);
 }
 
 // A generic function for checking the pred in a check
@@ -3672,6 +3700,7 @@ fn check_item(ccx: @crate_ctxt, it: @ast::item) {
         check_fn(ccx, ast::proto_bare, decl, body, it.id, false, none);
       }
       ast::item_res(decl, tps, body, dtor_id, _) {
+        check_instantiable(ccx.tcx, it.span, it.id);
         check_fn(ccx, ast::proto_bare, decl, body, dtor_id, false, none);
       }
       ast::item_impl(tps, _, ty, ms) {