auto merge of #17157 : nikomatsakis/rust/occurs-check, r=pcwalton

Avoid ever constructing cyclic types in the first place, rather than detecting them in resolve. This simplifies logic elsewhere in the compiler, in particular on the trait reform branch.

r? @pnkfelix or @pcwalton 

cc #5527

6 files changed, 127 insertions, 51 deletions

diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index ee59de11fc3..e196304b82a 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -1002,7 +1002,8 @@ pub enum type_err {
     terr_float_mismatch(expected_found<ast::FloatTy>),
     terr_traits(expected_found<ast::DefId>),
     terr_builtin_bounds(expected_found<BuiltinBounds>),
-    terr_variadic_mismatch(expected_found<bool>)
+    terr_variadic_mismatch(expected_found<bool>),
+    terr_cyclic_ty,
 }
 
 /// Bounds suitable for a named type parameter like `A` in `fn foo<A>`
@@ -3791,6 +3792,7 @@ pub fn type_err_to_str(cx: &ctxt, err: &type_err) -> String {
     }
 
     match *err {
+        terr_cyclic_ty => "cyclic type of infinite size".to_string(),
         terr_mismatch => "types differ".to_string(),
         terr_fn_style_mismatch(values) => {
             format!("expected {} fn, found {} fn",
diff --git a/src/librustc/middle/typeck/infer/combine.rs b/src/librustc/middle/typeck/infer/combine.rs
index 66caf10cb40..17e7aa8ddc3 100644
--- a/src/librustc/middle/typeck/infer/combine.rs
+++ b/src/librustc/middle/typeck/infer/combine.rs
@@ -39,6 +39,7 @@ use middle::ty::{FloatVar, FnSig, IntVar, TyVar};
 use middle::ty::{IntType, UintType};
 use middle::ty::{BuiltinBounds};
 use middle::ty;
+use middle::ty_fold;
 use middle::typeck::infer::equate::Equate;
 use middle::typeck::infer::glb::Glb;
 use middle::typeck::infer::lub::Lub;
@@ -48,7 +49,7 @@ use middle::typeck::infer::{InferCtxt, cres};
 use middle::typeck::infer::{MiscVariable, TypeTrace};
 use middle::typeck::infer::type_variable::{RelationDir, EqTo,
                                            SubtypeOf, SupertypeOf};
-use middle::ty_fold::{RegionFolder, TypeFoldable};
+use middle::ty_fold::{TypeFoldable};
 use util::ppaux::Repr;
 
 use std::result;
@@ -56,6 +57,7 @@ use std::result;
 use syntax::ast::{Onceness, FnStyle};
 use syntax::ast;
 use syntax::abi;
+use syntax::codemap::Span;
 
 pub trait Combine<'tcx> {
     fn infcx<'a>(&'a self) -> &'a InferCtxt<'a, 'tcx>;
@@ -637,10 +639,14 @@ impl<'f, 'tcx> CombineFields<'f, 'tcx> {
                 Some(t) => t, // ...already instantiated.
                 None => {     // ...not yet instantiated:
                     // Generalize type if necessary.
-                    let generalized_ty = match dir {
-                        EqTo => a_ty,
-                        SupertypeOf | SubtypeOf => self.generalize(a_ty)
-                    };
+                    let generalized_ty = try!(match dir {
+                        EqTo => {
+                            self.generalize(a_ty, b_vid, false)
+                        }
+                        SupertypeOf | SubtypeOf => {
+                            self.generalize(a_ty, b_vid, true)
+                        }
+                    });
                     debug!("instantiate(a_ty={}, dir={}, \
                                         b_vid={}, generalized_ty={})",
                            a_ty.repr(tcx), dir, b_vid.repr(tcx),
@@ -678,15 +684,85 @@ impl<'f, 'tcx> CombineFields<'f, 'tcx> {
         Ok(())
     }
 
-    fn generalize(&self, t: ty::t) -> ty::t {
-        // FIXME(#16847): This is non-ideal because we don't give a
-        // very descriptive origin for this region variable.
+    fn generalize(&self,
+                  ty: ty::t,
+                  for_vid: ty::TyVid,
+                  make_region_vars: bool)
+                  -> cres<ty::t>
+    {
+        /*!
+         * Attempts to generalize `ty` for the type variable
+         * `for_vid`.  This checks for cycle -- that is, whether the
+         * type `ty` references `for_vid`. If `make_region_vars` is
+         * true, it will also replace all regions with fresh
+         * variables. Returns `ty_err` in the case of a cycle, `Ok`
+         * otherwise.
+         */
+
+        let mut generalize = Generalizer { infcx: self.infcx,
+                                           span: self.trace.origin.span(),
+                                           for_vid: for_vid,
+                                           make_region_vars: make_region_vars,
+                                           cycle_detected: false };
+        let u = ty.fold_with(&mut generalize);
+        if generalize.cycle_detected {
+            Err(ty::terr_cyclic_ty)
+        } else {
+            Ok(u)
+        }
+    }
+}
 
-        let infcx = self.infcx;
-        let span = self.trace.origin.span();
-        t.fold_with(
-            &mut RegionFolder::regions(
-                self.infcx.tcx,
-                |_| infcx.next_region_var(MiscVariable(span))))
+struct Generalizer<'cx, 'tcx:'cx> {
+    infcx: &'cx InferCtxt<'cx, 'tcx>,
+    span: Span,
+    for_vid: ty::TyVid,
+    make_region_vars: bool,
+    cycle_detected: bool,
+}
+
+impl<'cx, 'tcx> ty_fold::TypeFolder<'tcx> for Generalizer<'cx, 'tcx> {
+    fn tcx(&self) -> &ty::ctxt<'tcx> {
+        self.infcx.tcx
+    }
+
+    fn fold_ty(&mut self, t: ty::t) -> ty::t {
+        // Check to see whether the type we are genealizing references
+        // `vid`. At the same time, also update any type variables to
+        // the values that they are bound to. This is needed to truly
+        // check for cycles, but also just makes things readable.
+        //
+        // (In particular, you could have something like `$0 = Box<$1>`
+        //  where `$1` has already been instantiated with `Box<$0>`)
+        match ty::get(t).sty {
+            ty::ty_infer(ty::TyVar(vid)) => {
+                if vid == self.for_vid {
+                    self.cycle_detected = true;
+                    ty::mk_err()
+                } else {
+                    match self.infcx.type_variables.borrow().probe(vid) {
+                        Some(u) => self.fold_ty(u),
+                        None => t,
+                    }
+                }
+            }
+            _ => {
+                ty_fold::super_fold_ty(self, t)
+            }
+        }
+    }
+
+    fn fold_region(&mut self, r: ty::Region) -> ty::Region {
+        match r {
+            ty::ReLateBound(..) | ty::ReEarlyBound(..) => r,
+            _ if self.make_region_vars => {
+                // FIXME: This is non-ideal because we don't give a
+                // very descriptive origin for this region variable.
+                self.infcx.next_region_var(MiscVariable(self.span))
+            }
+            _ => r,
+        }
     }
 }
+
+
diff --git a/src/librustc/middle/typeck/infer/mod.rs b/src/librustc/middle/typeck/infer/mod.rs
index 44ee7ba2de6..f917ced08ce 100644
--- a/src/librustc/middle/typeck/infer/mod.rs
+++ b/src/librustc/middle/typeck/infer/mod.rs
@@ -266,7 +266,6 @@ pub enum fixup_err {
     unresolved_int_ty(IntVid),
     unresolved_float_ty(FloatVid),
     unresolved_ty(TyVid),
-    cyclic_ty(TyVid),
     unresolved_region(RegionVid),
     region_var_bound_by_region_var(RegionVid, RegionVid)
 }
@@ -282,7 +281,6 @@ pub fn fixup_err_to_string(f: fixup_err) -> String {
            the type explicitly".to_string()
       }
       unresolved_ty(_) => "unconstrained type".to_string(),
-      cyclic_ty(_) => "cyclic type of infinite size".to_string(),
       unresolved_region(_) => "unconstrained region".to_string(),
       region_var_bound_by_region_var(r1, r2) => {
         format!("region var {:?} bound by another region var {:?}; \
diff --git a/src/librustc/middle/typeck/infer/resolve.rs b/src/librustc/middle/typeck/infer/resolve.rs
index dcdae7ed29c..569206f6754 100644
--- a/src/librustc/middle/typeck/infer/resolve.rs
+++ b/src/librustc/middle/typeck/infer/resolve.rs
@@ -51,7 +51,7 @@ use middle::ty::{FloatVar, FloatVid, IntVar, IntVid, RegionVid, TyVar, TyVid};
 use middle::ty::{IntType, UintType};
 use middle::ty;
 use middle::ty_fold;
-use middle::typeck::infer::{cyclic_ty, fixup_err, fres, InferCtxt};
+use middle::typeck::infer::{fixup_err, fres, InferCtxt};
 use middle::typeck::infer::{unresolved_int_ty,unresolved_float_ty,unresolved_ty};
 use syntax::codemap::Span;
 use util::common::indent;
@@ -78,7 +78,6 @@ pub struct ResolveState<'a, 'tcx: 'a> {
     infcx: &'a InferCtxt<'a, 'tcx>,
     modes: uint,
     err: Option<fixup_err>,
-    v_seen: Vec<TyVid> ,
     type_depth: uint,
 }
 
@@ -90,7 +89,6 @@ pub fn resolver<'a, 'tcx>(infcx: &'a InferCtxt<'a, 'tcx>,
         infcx: infcx,
         modes: modes,
         err: None,
-        v_seen: Vec::new(),
         type_depth: 0,
     }
 }
@@ -126,9 +124,7 @@ impl<'a, 'tcx> ResolveState<'a, 'tcx> {
         // n.b. This is a hokey mess because the current fold doesn't
         // allow us to pass back errors in any useful way.
 
-        assert!(self.v_seen.is_empty());
-        let rty = indent(|| self.resolve_type(typ) );
-        assert!(self.v_seen.is_empty());
+        let rty = self.resolve_type(typ);
         match self.err {
           None => {
             debug!("Resolved {} to {} (modes={:x})",
@@ -205,33 +201,19 @@ impl<'a, 'tcx> ResolveState<'a, 'tcx> {
     }
 
     pub fn resolve_ty_var(&mut self, vid: TyVid) -> ty::t {
-        if self.v_seen.contains(&vid) {
-            self.err = Some(cyclic_ty(vid));
-            return ty::mk_var(self.infcx.tcx, vid);
-        } else {
-            self.v_seen.push(vid);
-            let tcx = self.infcx.tcx;
-
-            // Nonobvious: prefer the most specific type
-            // (i.e., the lower bound) to the more general
-            // one.  More general types in Rust (e.g., fn())
-            // tend to carry more restrictions or higher
-            // perf. penalties, so it pays to know more.
-
-            let t1 = match self.infcx.type_variables.borrow().probe(vid) {
-                Some(t) => {
-                    self.resolve_type(t)
-                }
-                None => {
-                    if self.should(force_tvar) {
-                        self.err = Some(unresolved_ty(vid));
-                    }
-                    ty::mk_var(tcx, vid)
+        let tcx = self.infcx.tcx;
+        let t1 = match self.infcx.type_variables.borrow().probe(vid) {
+            Some(t) => {
+                self.resolve_type(t)
+            }
+            None => {
+                if self.should(force_tvar) {
+                    self.err = Some(unresolved_ty(vid));
                 }
-            };
-            self.v_seen.pop().unwrap();
-            return t1;
-        }
+                ty::mk_var(tcx, vid)
+            }
+        };
+        return t1;
     }
 
     pub fn resolve_int_var(&mut self, vid: IntVid) -> ty::t {
diff --git a/src/test/compile-fail/occurs-check-2.rs b/src/test/compile-fail/occurs-check-2.rs
new file mode 100644
index 00000000000..69c012e0d8e
--- /dev/null
+++ b/src/test/compile-fail/occurs-check-2.rs
@@ -0,0 +1,18 @@
+// Copyright 2012 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.
+
+use std::gc::GC;
+
+fn main() {
+    let f;
+    let g;
+    g = f;
+    f = box(GC) g; //~ ERROR cyclic type of infinite size
+}
diff --git a/src/test/compile-fail/occurs-check.rs b/src/test/compile-fail/occurs-check.rs
index a2148c07187..a00528616c3 100644
--- a/src/test/compile-fail/occurs-check.rs
+++ b/src/test/compile-fail/occurs-check.rs
@@ -12,6 +12,6 @@
 use std::gc::GC;
 
 fn main() {
-    let f; //~ ERROR cyclic type of infinite size
-    f = box(GC) f;
+    let f;
+    f = box(GC) f; //~ ERROR cyclic type of infinite size
 }