Make occurs check in ty::fixup_vars more reliable

It wouldn't detect cycles that went through several type vars before.

Closes #1464

3 files changed, 21 insertions, 13 deletions

diff --git a/src/comp/middle/ty.rs b/src/comp/middle/ty.rs
index 944614ad03e..502510063df 100644
--- a/src/comp/middle/ty.rs
+++ b/src/comp/middle/ty.rs
@@ -2421,7 +2421,8 @@ mod unify {
     fn fixup_vars(tcx: ty_ctxt, sp: option::t<span>, vb: @var_bindings,
                   typ: t) -> fixup_result {
         fn subst_vars(tcx: ty_ctxt, sp: option::t<span>, vb: @var_bindings,
-                      unresolved: @mutable option::t<int>, vid: int) -> t {
+                      unresolved: @mutable option::t<int>,
+                      vars_seen: std::list::list<int>, vid: int) -> t {
             // Should really return a fixup_result instead of a t, but fold_ty
             // doesn't allow returning anything but a t.
             if vid as uint >= ufind::set_count(vb.sets) {
@@ -2432,21 +2433,28 @@ mod unify {
             alt smallintmap::find::<t>(vb.types, root_id) {
               none { *unresolved = some(vid); ret ty::mk_var(tcx, vid); }
               some(rt) {
-                if occurs_check_fails(tcx, sp, vid, rt) {
-                    // Return the type unchanged, so we can error out
-                    // downstream
-                    ret rt;
+                let give_up = false;
+                std::list::iter(vars_seen) {|v|
+                    if v == vid {
+                        give_up = true;
+                        option::may(sp) {|sp|
+                            tcx.sess.span_fatal(
+                                sp, "can not instantiate infinite type");
+                        }
+                    }
                 }
-                ret fold_ty(tcx,
-                            fm_var(bind subst_vars(tcx, sp, vb, unresolved,
-                                                   _)), rt);
+                // Return the type unchanged, so we can error out
+                // downstream
+                if give_up { ret rt; }
+                ret fold_ty(tcx, fm_var(bind subst_vars(
+                    tcx, sp, vb, unresolved, std::list::cons(vid, @vars_seen),
+                    _)), rt);
               }
             }
         }
         let unresolved = @mutable none::<int>;
-        let rty =
-            fold_ty(tcx, fm_var(bind subst_vars(tcx, sp, vb, unresolved, _)),
-                    typ);
+        let rty = fold_ty(tcx, fm_var(bind subst_vars(
+            tcx, sp, vb, unresolved, std::list::nil, _)), typ);
         let ur = *unresolved;
         alt ur {
           none { ret fix_ok(rty); }
diff --git a/src/libstd/list.rs b/src/libstd/list.rs
index 2081a21de23..e393b42b9f2 100644
--- a/src/libstd/list.rs
+++ b/src/libstd/list.rs
@@ -128,7 +128,7 @@ Function: tail
 
 Returns all but the first element of a list
 */
-pure fn tail<T: copy>(ls: list<T>) : is_not_empty(ls) -> list<T> {
+pure fn tail<T: copy>(ls: list<T>) -> list<T> {
     alt ls {
         cons(_, tl) { ret *tl; }
         nil { fail "list empty" }
diff --git a/src/test/compile-fail/occurs-check.rs b/src/test/compile-fail/occurs-check.rs
index aba5b5c5928..069bd0a5bbd 100644
--- a/src/test/compile-fail/occurs-check.rs
+++ b/src/test/compile-fail/occurs-check.rs
@@ -1,2 +1,2 @@
-// error-pattern: Type inference failed because I could not find
+// error-pattern: can not instantiate infinite type
 fn main() { let f; f = @f; }