add static region and also fix regions to be contravariant

12 files changed, 146 insertions, 72 deletions

diff --git a/src/librustsyntax/ast.rs b/src/librustsyntax/ast.rs
index c6fe959e290..67988e807c1 100644
--- a/src/librustsyntax/ast.rs
+++ b/src/librustsyntax/ast.rs
@@ -442,7 +442,8 @@ type region = {id: node_id, node: region_};
 enum region_ {
     re_inferred,
     re_named(ident),
-    re_self
+    re_self,
+    re_static
 }
 
 #[auto_serialize]
diff --git a/src/librustsyntax/parse/parser.rs b/src/librustsyntax/parse/parser.rs
index dfd682b9ae9..759ac1a3a95 100644
--- a/src/librustsyntax/parse/parser.rs
+++ b/src/librustsyntax/parse/parser.rs
@@ -434,6 +434,8 @@ fn parse_region(p: parser) -> ast::region {
             p.bump(); p.bump();
             if string == "self" {
                 ast::re_self
+            } else if string == "static" {
+                ast::re_static
             } else {
                 ast::re_named(string)
             }
diff --git a/src/librustsyntax/print/pprust.rs b/src/librustsyntax/print/pprust.rs
index 6f53344926b..58fd96bbb2e 100644
--- a/src/librustsyntax/print/pprust.rs
+++ b/src/librustsyntax/print/pprust.rs
@@ -322,6 +322,7 @@ fn print_region(s: ps, region: ast::region) {
       ast::re_inferred { /* no-op */ }
       ast::re_named(name) { word(s.s, name); word(s.s, "."); }
       ast::re_self { word(s.s, "self"); word(s.s, "."); }
+      ast::re_static { word(s.s, "static"); word(s.s, "."); }
     }
 }
 
diff --git a/src/rustc/metadata/tyencode.rs b/src/rustc/metadata/tyencode.rs
index c5f23f37b86..33f420ba245 100644
--- a/src/rustc/metadata/tyencode.rs
+++ b/src/rustc/metadata/tyencode.rs
@@ -140,6 +140,9 @@ fn enc_region(w: io::writer, r: ty::region) {
         w.write_uint(id.to_uint());
         w.write_char('|');
       }
+      ty::re_static {
+        w.write_char('t');
+      }
     }
 }
 fn enc_sty(w: io::writer, cx: @ctxt, st: ty::sty) {
diff --git a/src/rustc/middle/infer.rs b/src/rustc/middle/infer.rs
index 74843f95fa8..fd8700042c6 100644
--- a/src/rustc/middle/infer.rs
+++ b/src/rustc/middle/infer.rs
@@ -9,6 +9,7 @@ import util::ppaux::{ty_to_str, mt_to_str};
 import result::{result, extensions, ok, err, map, map2, iter2};
 import ty::type_is_bot;
 import driver::session::session;
+import util::common::{indent, indenter};
 
 export infer_ctxt;
 export new_infer_ctxt;
@@ -66,25 +67,31 @@ fn new_infer_ctxt(tcx: ty::ctxt) -> infer_ctxt {
 }
 
 fn mk_subty(cx: infer_ctxt, a: ty::t, b: ty::t) -> ures {
-    #debug[">> mk_subty(%s <: %s)", a.to_str(cx), b.to_str(cx)];
-    cx.commit {||
-        cx.tys(a, b)
+    #debug["mk_subty(%s <: %s)", a.to_str(cx), b.to_str(cx)];
+    indent {||
+        cx.commit {||
+            cx.tys(a, b)
+        }
     }
 }
 
 fn mk_eqty(cx: infer_ctxt, a: ty::t, b: ty::t) -> ures {
-    #debug[">> mk_eqty(%s <: %s)", a.to_str(cx), b.to_str(cx)];
-    cx.commit {||
-        cx.eq_tys(a, b)
+    #debug["mk_eqty(%s <: %s)", a.to_str(cx), b.to_str(cx)];
+    indent {||
+        cx.commit {||
+            cx.eq_tys(a, b)
+        }
     }
 }
 
 fn compare_tys(tcx: ty::ctxt, a: ty::t, b: ty::t) -> ures {
     let infcx = new_infer_ctxt(tcx);
-    #debug[">> compare_tys(%s == %s)", a.to_str(infcx), b.to_str(infcx)];
-    infcx.commit {||
-        mk_subty(infcx, a, b).then {||
-            mk_subty(infcx, b, a)
+    #debug["compare_tys(%s == %s)", a.to_str(infcx), b.to_str(infcx)];
+    indent {||
+        infcx.commit {||
+            mk_subty(infcx, a, b).then {||
+                mk_subty(infcx, b, a)
+            }
         }
     }
 }
@@ -226,24 +233,22 @@ impl unify_methods for infer_ctxt {
         self.set(self.vb, vid, new_v);
     }
 
-    fn commit<T:copy,E:copy>(f: fn() -> result<T,E>) -> result<T,E> {
+    fn commit<T,E>(f: fn() -> result<T,E>) -> result<T,E> {
 
         assert self.vb.bindings.len() == 0u;
         assert self.rb.bindings.len() == 0u;
 
-        let r = self.try(f);
+        let r <- self.try(f);
 
         // TODO---could use a vec::clear() that ran destructors but kept
         // the vec at its currently allocated length
         self.vb.bindings = [];
         self.rb.bindings = [];
 
-        #debug[">> Commit result: %?", r];
-
         ret r;
     }
 
-    fn try<T:copy,E:copy>(f: fn() -> result<T,E>) -> result<T,E> {
+    fn try<T,E>(f: fn() -> result<T,E>) -> result<T,E> {
 
         fn rollback_to<V:copy vid, T:copy>(
             vb: vals_and_bindings<V, T>, len: uint) {
@@ -257,7 +262,7 @@ impl unify_methods for infer_ctxt {
         let vbl = self.vb.bindings.len();
         let rbl = self.rb.bindings.len();
         #debug["try(vbl=%u, rbl=%u)", vbl, rbl];
-        let r = f();
+        let r <- f();
         alt r {
           result::ok(_) { #debug["try--ok"]; }
           result::err(_) {
@@ -309,6 +314,9 @@ impl unify_methods for infer_ctxt {
         a: bound<V>, b: bound<V>,
         merge_op: fn(V,V) -> cres<V>) -> cres<bound<V>> {
 
+        #debug["merge_bnd(%s,%s)", a.to_str(self), b.to_str(self)];
+        let _r = indenter();
+
         alt (a, b) {
           (none, none) {
             ok(none)
@@ -332,6 +340,7 @@ impl unify_methods for infer_ctxt {
         lub: fn(V,V) -> cres<V>,
         glb: fn(V,V) -> cres<V>) -> cres<bounds<V>> {
 
+        let _r = indenter();
         self.merge_bnd(a.ub, b.ub, glb).chain {|ub|
             #debug["glb of ubs %s and %s is %s",
                    a.ub.to_str(self), b.ub.to_str(self),
@@ -383,6 +392,7 @@ impl unify_methods for infer_ctxt {
         // them explicitly gives the type inferencer more
         // information and helps to produce tighter bounds
         // when necessary.
+        indent {||
         self.bnds(a.lb, b.ub).then {||
         self.bnds(b.lb, a.ub).then {||
         self.merge_bnd(a.ub, b.ub, {|x, y| x.glb(self, y)}).chain {|ub|
@@ -395,10 +405,10 @@ impl unify_methods for infer_ctxt {
             // the new bounds must themselves
             // be relatable:
             self.bnds(bnds.lb, bnds.ub).then {||
-            self.set(vb, v_id, bounded(bnds));
-            self.uok()
+                self.set(vb, v_id, bounded(bnds));
+                self.uok()
             }
-        }}}}
+        }}}}}
     }
 
     fn vars<V:copy vid, T:copy to_str st>(
@@ -465,46 +475,29 @@ impl unify_methods for infer_ctxt {
     }
 
     fn regions(a: ty::region, b: ty::region) -> ures {
-        alt (a, b) { // XXX
-          (ty::re_var(a_id), ty::re_var(b_id)) {
-            self.vars(self.rb, a_id, b_id)
-          }
-          (ty::re_var(a_id), _) {
-            self.vart(self.rb, a_id, b)
-          }
-          (_, ty::re_var(b_id)) {
-            self.tvar(self.rb, a, b_id)
-          }
-
-          (ty::re_free(a_id, _), ty::re_scope(b_id)) |
-          (ty::re_scope(a_id), ty::re_free(b_id, _)) |
-          (ty::re_scope(a_id), ty::re_scope(b_id)) {
-            let rm = self.tcx.region_map;
-            alt region::nearest_common_ancestor(rm, a_id, b_id) {
-              some(r_id) if r_id == a_id { self.uok() }
-              _ { err(ty::terr_regions_differ(false, b, a)) }
-            }
-          }
+        #debug["regions(%s <= %s)", a.to_str(self), b.to_str(self)];
+        indent {||
+            alt (a, b) {
+              (ty::re_var(a_id), ty::re_var(b_id)) {
+                self.vars(self.rb, a_id, b_id)
+              }
+              (ty::re_var(a_id), _) {
+                self.vart(self.rb, a_id, b)
+              }
+              (_, ty::re_var(b_id)) {
+                self.tvar(self.rb, a, b_id)
+              }
 
-          // For these types, we cannot define any additional relationship:
-          (ty::re_free(_, _), ty::re_free(_, _)) |
-          (ty::re_bound(_), ty::re_bound(_)) |
-          (ty::re_bound(_), ty::re_free(_, _)) |
-          (ty::re_bound(_), ty::re_scope(_)) |
-          (ty::re_free(_, _), ty::re_bound(_)) |
-          (ty::re_scope(_), ty::re_bound(_)) {
-            if a == b {
-                self.uok()
-            } else {
-                err(ty::terr_regions_differ(false, b, a))
+              _ {
+                lub(self).c_regions(a, b).chain {|r|
+                    if b == r {
+                        self.uok()
+                    } else {
+                        err(ty::terr_regions_differ(false, b, a))
+                    }
+                }
+              }
             }
-          }
-
-          (ty::re_default, _) |
-          (_, ty::re_default) {
-            // actually a compiler bug, I think.
-            err(ty::terr_regions_differ(false, b, a))
-          }
         }
     }
 
@@ -657,16 +650,17 @@ impl unify_methods for infer_ctxt {
         a: bound<T>, b: bound<T>) -> ures {
 
         #debug("bnds(%s <: %s)", a.to_str(self), b.to_str(self));
-
-        alt (a, b) {
-          (none, none) |
-          (some(_), none) |
-          (none, some(_)) {
-            self.uok()
-          }
-          (some(t_a), some(t_b)) {
-            t_a.st(self, t_b)
-          }
+        indent {||
+            alt (a, b) {
+              (none, none) |
+              (some(_), none) |
+              (none, some(_)) {
+                self.uok()
+              }
+              (some(t_a), some(t_b)) {
+                t_a.st(self, t_b)
+              }
+            }
         }
     }
 
@@ -744,7 +738,9 @@ impl unify_methods for infer_ctxt {
 
           (ty::ty_rptr(a_r, a_mt), ty::ty_rptr(b_r, b_mt)) {
             self.mts(a_mt, b_mt).then {||
-                self.regions(a_r, b_r)
+                // Non-obvious: for &a.T to be a subtype of &b.T, &a
+                // must exist for LONGER than &b.  That is, &b <= &a.
+                self.regions(b_r, a_r)
             }
           }
 
@@ -972,8 +968,11 @@ iface combine {
 
     // Combining regions (along with some specific cases that are
     // different for LUB/GLB):
+    fn c_contraregions(
+        a: ty::region, b: ty::region) -> cres<ty::region>;
     fn c_regions(
         a: ty::region, b: ty::region) -> cres<ty::region>;
+    fn c_regions_static(r: ty::region) -> cres<ty::region>;
     fn c_regions_scope_scope(
         a: ty::region, a_id: ast::node_id,
         b: ty::region, b_id: ast::node_id) -> cres<ty::region>;
@@ -1045,11 +1044,13 @@ fn c_var_t<V:copy vid, C:combine, T:copy to_str st>(
     alt self.bnd(a_bounds) {
       some(a_bnd) {
         // If a has an upper bound, return it.
+        #debug["bnd=some(%s)", a_bnd.to_str(self.infcx())];
         ret c_ts(a_bnd, b);
       }
       none {
         // If a does not have an upper bound, make b the upper bound of a
         // and then return b.
+        #debug["bnd=none"];
         let a_bounds = self.with_bnd(a_bounds, b);
         self.infcx().bnds(a_bounds.lb, a_bounds.ub).then {||
             self.infcx().set(vb, a_id, bounded(a_bounds));
@@ -1162,6 +1163,7 @@ fn c_tys<C:combine>(
     // Fast path.
     if a == b { ret ok(a); }
 
+    indent {||
     alt (ty::get(a).struct, ty::get(b).struct) {
       (ty::ty_bot, _) { self.c_bot(b) }
       (_, ty::ty_bot) { self.c_bot(b) }
@@ -1249,7 +1251,7 @@ fn c_tys<C:combine>(
       }
 
       (ty::ty_rptr(a_r, a_mt), ty::ty_rptr(b_r, b_mt)) {
-        self.c_regions(a_r, b_r).chain {|r|
+        self.c_contraregions(a_r, b_r).chain {|r|
             self.c_mts(a_mt, b_mt).chain {|mt|
                 ok(ty::mk_rptr(tcx, r, mt))
             }
@@ -1293,6 +1295,7 @@ fn c_tys<C:combine>(
 
       _ { err(ty::terr_mismatch) }
     }
+    }
 }
 
 fn c_regions<C:combine>(
@@ -1303,7 +1306,12 @@ fn c_regions<C:combine>(
            a.to_str(self.infcx()),
            b.to_str(self.infcx())];
 
+    indent {||
     alt (a, b) {
+      (ty::re_static, r) | (r, ty::re_static) {
+        self.c_regions_static(r)
+      }
+
       (ty::re_var(a_id), ty::re_var(b_id)) {
         c_vars(self, self.infcx().rb,
                a, a_id, b_id,
@@ -1352,6 +1360,7 @@ fn c_regions<C:combine>(
         err(ty::terr_regions_differ(false, b, a))
       }
     }
+    }
 }
 
 impl of combine for lub {
@@ -1443,6 +1452,16 @@ impl of combine for lub {
         ret c_regions(self, a, b);
     }
 
+    fn c_contraregions(a: ty::region, b: ty::region) -> cres<ty::region> {
+        ret glb(self.infcx()).c_regions(a, b);
+    }
+
+    fn c_regions_static(_r: ty::region) -> cres<ty::region> {
+        // LUB of `r` and static is always static---what's bigger than
+        // that?
+        ret ok(ty::re_static);
+    }
+
     fn c_regions_free_scope(
         a: ty::region, _a_id: ast::node_id, _a_br: ty::bound_region,
         _b: ty::region, _b_id: ast::node_id) -> cres<ty::region> {
@@ -1573,6 +1592,16 @@ impl of combine for glb {
         ret c_regions(self, a, b);
     }
 
+    fn c_contraregions(a: ty::region, b: ty::region) -> cres<ty::region> {
+        ret lub(self.infcx()).c_regions(a, b);
+    }
+
+    fn c_regions_static(r: ty::region) -> cres<ty::region> {
+        // GLB of `r` and static is always `r`; static is bigger than
+        // everything
+        ret ok(r);
+    }
+
     fn c_regions_free_scope(
         _a: ty::region, _a_id: ast::node_id, _a_br: ty::bound_region,
         b: ty::region, _b_id: ast::node_id) -> cres<ty::region> {
diff --git a/src/rustc/middle/region.rs b/src/rustc/middle/region.rs
index 1e002e9c1d0..d17f28efd68 100644
--- a/src/rustc/middle/region.rs
+++ b/src/rustc/middle/region.rs
@@ -377,6 +377,8 @@ fn resolve_region_binding(cx: ctxt, span: span, region: ast::region) {
         // }
       }
 
+      ast::re_static { /* fallthrough */ }
+
       ast::re_named(ident) {
         alt cx.scope.resolve_ident(ident) {
           some(r) {
diff --git a/src/rustc/middle/regionck.rs b/src/rustc/middle/regionck.rs
index 611f010ae10..c16b164d153 100644
--- a/src/rustc/middle/regionck.rs
+++ b/src/rustc/middle/regionck.rs
@@ -28,7 +28,7 @@ fn check_expr(expr: @ast::expr, cx: ctxt, visitor: visit::vt<ctxt>) {
             alt ty::get(t).struct {
               ty::ty_rptr(region, _) {
                 alt region {
-                  ty::re_bound(_) | ty::re_free(_, _) {
+                  ty::re_bound(_) | ty::re_free(_, _) | ty::re_static {
                     /* ok */
                   }
                   ty::re_scope(rbi) {
diff --git a/src/rustc/middle/ty.rs b/src/rustc/middle/ty.rs
index 89c34064f6d..70173de4f05 100644
--- a/src/rustc/middle/ty.rs
+++ b/src/rustc/middle/ty.rs
@@ -267,6 +267,7 @@ enum region {
     re_free(node_id, bound_region),
     re_scope(node_id),
     re_var(region_vid),
+    re_static, // effectively `top` in the region lattice
     re_default
 }
 
@@ -1473,6 +1474,7 @@ fn hash_type_structure(st: sty) -> uint {
           re_scope(id)  { ((id as uint) << 2u) | 2u }
           re_var(id)    { (id.to_uint() << 2u) | 3u }
           re_default    { 4u }
+          re_bot        { 5u }
         }
     }
     alt st {
diff --git a/src/rustc/middle/typeck.rs b/src/rustc/middle/typeck.rs
index 8fcdcbbc86d..1109cc53ab6 100644
--- a/src/rustc/middle/typeck.rs
+++ b/src/rustc/middle/typeck.rs
@@ -20,6 +20,7 @@ import std::map::{hashmap, int_hash};
 import std::serialization::{serialize_uint, deserialize_uint};
 import std::ufind;
 import syntax::print::pprust::*;
+import util::common::indent;
 
 export check_crate;
 export method_map;
@@ -366,6 +367,9 @@ fn ast_ty_to_ty(tcx: ty::ctxt, mode: mode, &&ast_ty: @ast::ty) -> ty::t {
               ast::re_self | ast::re_named(_) {
                 tcx.region_map.ast_type_to_region.get(region.id)
               }
+              ast::re_static {
+                ty::re_static
+              }
             };
             ty::mk_rptr(tcx, r, ast_mt_to_mt(tcx, mode, mt))
           }
@@ -2472,7 +2476,7 @@ fn check_expr_fn_with_unifier(fcx: @fn_ctxt,
 fn check_expr_with_unifier(fcx: @fn_ctxt, expr: @ast::expr, unify: unifier,
                            expected: ty::t) -> bool {
 
-    #debug("typechecking expr %d (%s)",
+    #debug(">> typechecking expr %d (%s)",
            expr.id, syntax::print::pprust::expr_to_str(expr));
 
     // A generic function to factor out common logic from call and bind
@@ -3382,6 +3386,8 @@ fn check_expr_with_unifier(fcx: @fn_ctxt, expr: @ast::expr, unify: unifier,
            ty_to_str(tcx, expected));
 
     unify(fcx, expr.span, expected, fcx.expr_ty(expr));
+
+    #debug("<< bot=%b", bot);
     ret bot;
 }
 
diff --git a/src/rustc/util/ppaux.rs b/src/rustc/util/ppaux.rs
index 2cb0fef1a90..d8b27dc5686 100644
--- a/src/rustc/util/ppaux.rs
+++ b/src/rustc/util/ppaux.rs
@@ -36,6 +36,7 @@ fn region_to_str(cx: ctxt, region: region) -> str {
       // These two should not be seen by end-users (very often, anyhow):
       re_var(id)    { #fmt("&%s.", id.to_str()) }
       re_default    { "&(default)." }
+      re_static     { "&static." }
     }
 }
 
diff --git a/src/test/compile-fail/regions-leaking-ptr.rs b/src/test/compile-fail/regions-leaking-ptr.rs
new file mode 100644
index 00000000000..ffc9f6ca1e0
--- /dev/null
+++ b/src/test/compile-fail/regions-leaking-ptr.rs
@@ -0,0 +1,19 @@
+// The type of `y` ends up getting inferred to the type of the block.
+// This generates a ton of error msgs at the moment.
+fn broken() -> int {
+    let mut x = 3;
+    let mut y = [&x]; //! ERROR reference escapes its block
+    while x < 10 {
+        let z = x;
+        y += [&z];
+        x += 1;
+    }
+    vec::foldl(0, y) {|v, p| v + *p }
+    //!^ ERROR reference escapes its block
+    //!^^ ERROR reference escapes its block
+    //!^^^ ERROR reference escapes its block
+    //!^^^^ ERROR reference escapes its block
+    //!^^^^^ ERROR reference escapes its block
+}
+
+fn main() { }
\ No newline at end of file
diff --git a/src/test/run-pass/regions-bot.rs b/src/test/run-pass/regions-bot.rs
new file mode 100644
index 00000000000..b25d7ceccba
--- /dev/null
+++ b/src/test/run-pass/regions-bot.rs
@@ -0,0 +1,8 @@
+// A very limited test of the "bottom" region
+
+fn produce_static<T>() -> &static.T { fail; }
+
+fn foo<T>(x: &T) -> &uint { produce_static() }
+
+fn main() {
+}
\ No newline at end of file