move purity checking into borrowck, addresses #1422

7 files changed, 203 insertions, 88 deletions

diff --git a/src/libcore/vec.rs b/src/libcore/vec.rs
index cddb1346c01..7a316507912 100644
--- a/src/libcore/vec.rs
+++ b/src/libcore/vec.rs
@@ -997,7 +997,7 @@ impl extensions<T> for [const T] {
     fn iteri(f: fn(uint, T)) { iteri(self, f) }
     #[doc = "Returns the length of a vector"]
     #[inline]
-    fn len() -> uint { len(self) }
+    pure fn len() -> uint { len(self) }
     #[doc = "
     Find the first index matching some predicate
 
diff --git a/src/rustc/middle/borrowck.rs b/src/rustc/middle/borrowck.rs
index 1d79ea41fb8..cd881f1c731 100644
--- a/src/rustc/middle/borrowck.rs
+++ b/src/rustc/middle/borrowck.rs
@@ -149,6 +149,13 @@ fn check_sup_mutbl(req_m: ast::mutability,
     }
 }
 
+fn save_and_restore<T:copy,U>(&t: T, f: fn() -> U) -> U {
+    let old_t = t;
+    let u <- f();
+    t = old_t;
+    ret u;
+}
+
 // ----------------------------------------------------------------------
 // Gathering loans
 //
@@ -398,7 +405,9 @@ enum check_loan_ctxt = @{
     // Keep track of whether we're inside a ctor, so as to
     // allow mutating immutable fields in the same class if
     // we are in a ctor, we track the self id
-    mut in_ctor: bool
+    mut in_ctor: bool,
+
+    mut is_pure: bool
 };
 
 fn check_loans(bccx: borrowck_ctxt,
@@ -406,7 +415,8 @@ fn check_loans(bccx: borrowck_ctxt,
                crate: @ast::crate) {
     let clcx = check_loan_ctxt(@{bccx: bccx,
                                  req_loan_map: req_loan_map,
-                                 mut in_ctor: false});
+                                 mut in_ctor: false,
+                                 mut is_pure: false});
     let vt = visit::mk_vt(@{visit_expr: check_loans_in_expr,
                             visit_block: check_loans_in_block,
                             visit_fn: check_loans_in_fn
@@ -465,6 +475,76 @@ impl methods for check_loan_ctxt {
         }
     }
 
+    // when we are in a pure context, we check each call to ensure
+    // that the function which is invoked is itself pure.
+    fn check_pure(expr: @ast::expr) {
+        let tcx = self.tcx();
+        alt ty::get(tcx.ty(expr)).struct {
+          ty::ty_fn(_) {
+            // Extract purity or unsafety based on what kind of callee
+            // we've got.  This would be cleaner if we just admitted
+            // that we have an effect system and carried the purity
+            // etc around in the type.
+
+            // First, check the def_map---if expr.id is present then
+            // expr must be a path (at least I think that's the idea---NDM)
+            let callee_purity = alt tcx.def_map.find(expr.id) {
+              some(ast::def_fn(_, p)) { p }
+              some(ast::def_variant(_, _)) { ast::pure_fn }
+              _ {
+                // otherwise it may be a method call that we can trace
+                // to the def'n site:
+                alt self.bccx.method_map.find(expr.id) {
+                  some(typeck::method_static(did)) {
+                    if did.crate == ast::local_crate {
+                        alt tcx.items.get(did.node) {
+                          ast_map::node_method(m, _, _) { m.decl.purity }
+                          _ { tcx.sess.span_bug(expr.span,
+                                                "Node not bound \
+                                                 to a method") }
+                        }
+                    } else {
+                        metadata::csearch::lookup_method_purity(
+                            tcx.sess.cstore,
+                            did)
+                    }
+                  }
+                  some(typeck::method_param(iid, n_m, _, _)) |
+                  some(typeck::method_iface(iid, n_m)) {
+                    ty::iface_methods(tcx, iid)[n_m].purity
+                  }
+                  none {
+                    // otherwise it's just some dang thing.  We know
+                    // it cannot be unsafe because we do not allow
+                    // unsafe functions to be used as values (or,
+                    // rather, we only allow that inside an unsafe
+                    // block, and then it's up to the user to keep
+                    // things confined).
+                    ast::impure_fn
+                  }
+                }
+              }
+            };
+
+            alt callee_purity {
+              ast::crust_fn | ast::pure_fn { /*ok*/ }
+              ast::impure_fn {
+                self.bccx.span_err(
+                    expr.span,
+                    "pure function calls function \
+                     not known to be pure");
+              }
+              ast::unsafe_fn {
+                self.bccx.span_err(
+                    expr.span,
+                    "pure function calls unsafe function");
+              }
+            }
+          }
+          _ { /* not a fn, ok */ }
+        }
+    }
+
     fn check_for_conflicting_loans(scope_id: ast::node_id) {
         let new_loanss = alt self.req_loan_map.find(scope_id) {
             none { ret; }
@@ -532,6 +612,16 @@ impl methods for check_loan_ctxt {
             }
         }
 
+        // if this is a pure function, only loan-able state can be
+        // assigned, because it is uniquely tied to this function and
+        // is not visible from the outside
+        if self.is_pure && cmt.lp.is_none() {
+            self.bccx.span_err(
+                ex.span,
+                #fmt["%s prohibited in pure functions",
+                     at.ing_form(self.bccx.cmt_to_str(cmt))]);
+        }
+
         // check for a conflicting loan as well, except in the case of
         // taking a mutable ref.  that will create a loan of its own
         // which will be checked for compat separately in
@@ -617,21 +707,27 @@ fn check_loans_in_fn(fk: visit::fn_kind, decl: ast::fn_decl, body: ast::blk,
                      sp: span, id: ast::node_id, &&self: check_loan_ctxt,
                      visitor: visit::vt<check_loan_ctxt>) {
 
-    let old_in_ctor = self.in_ctor;
-
-    // In principle, we could consider fk_anon(*) or fk_fn_block(*) to
-    // be in a ctor, I suppose, but the purpose of the in_ctor flag is
-    // to allow modifications of otherwise immutable fields and
-    // typestate wouldn't be able to "see" into those functions
-    // anyway, so it wouldn't be very helpful.
-    alt fk {
-      visit::fk_ctor(*) { self.in_ctor = true; }
-      _ { self.in_ctor = false; }
-    };
+    save_and_restore(self.in_ctor) {||
+        save_and_restore(self.is_pure) {||
+            // In principle, we could consider fk_anon(*) or
+            // fk_fn_block(*) to be in a ctor, I suppose, but the
+            // purpose of the in_ctor flag is to allow modifications
+            // of otherwise immutable fields and typestate wouldn't be
+            // able to "see" into those functions anyway, so it
+            // wouldn't be very helpful.
+            alt fk {
+              visit::fk_ctor(*) { self.in_ctor = true; }
+              _ { self.in_ctor = false; }
+            };
 
-    visit::visit_fn(fk, decl, body, sp, id, self, visitor);
+            alt decl.purity {
+              ast::pure_fn { self.is_pure = true; }
+              _ { }
+            }
 
-    self.in_ctor = old_in_ctor;
+            visit::visit_fn(fk, decl, body, sp, id, self, visitor);
+        }
+    }
 }
 
 fn check_loans_in_expr(expr: @ast::expr,
@@ -680,6 +776,10 @@ fn check_loans_in_expr(expr: @ast::expr,
         }
       }
       ast::expr_call(f, args, _) {
+        if self.is_pure {
+            self.check_pure(f);
+            for args.each { |arg| self.check_pure(arg) }
+        }
         let arg_tys = ty::ty_fn_args(ty::expr_ty(self.tcx(), f));
         vec::iter2(args, arg_tys) { |arg, arg_ty|
             alt ty::resolved_mode(self.tcx(), arg_ty.mode) {
@@ -696,14 +796,25 @@ fn check_loans_in_expr(expr: @ast::expr,
       }
       _ { }
     }
+
     visit::visit_expr(expr, self, vt);
 }
 
 fn check_loans_in_block(blk: ast::blk,
                         &&self: check_loan_ctxt,
                         vt: visit::vt<check_loan_ctxt>) {
-    self.check_for_conflicting_loans(blk.node.id);
-    visit::visit_block(blk, self, vt);
+    save_and_restore(self.is_pure) {||
+        self.check_for_conflicting_loans(blk.node.id);
+
+        alt blk.node.rules {
+          ast::default_blk {
+          }
+          ast::unchecked_blk |
+          ast::unsafe_blk { self.is_pure = false; }
+        }
+
+        visit::visit_block(blk, self, vt);
+    }
 }
 
 // ----------------------------------------------------------------------
@@ -1022,20 +1133,25 @@ impl categorize_methods for borrowck_ctxt {
             // lp: loan path, must be none for aliasable things
             let {m,lp} = alt ty::resolved_mode(self.tcx, mode) {
               ast::by_mutbl_ref {
-                {m:m_mutbl, lp:none}
+                {m: m_mutbl,
+                 lp: none}
               }
               ast::by_move | ast::by_copy {
-                {m:m_mutbl, lp:some(@lp_arg(vid))}
+                {m: m_mutbl,
+                 lp: some(@lp_arg(vid))}
               }
               ast::by_ref {
-                if TREAT_CONST_AS_IMM {
-                    {m:m_imm, lp:some(@lp_arg(vid))}
-                } else {
-                    {m:m_const, lp:none}
-                }
+                {m: if TREAT_CONST_AS_IMM {m_imm} else {m_const},
+                 lp: none}
               }
               ast::by_val {
-                {m:m_imm, lp:some(@lp_arg(vid))}
+                // by-value is this hybrid mode where we have a
+                // pointer but we do not own it.  This is not
+                // considered loanable because, for example, a by-ref
+                // and and by-val argument might both actually contain
+                // the same unique ptr.
+                {m: m_imm,
+                 lp: none}
               }
             };
             @{id:id, span:span,
diff --git a/src/rustc/middle/typeck.rs b/src/rustc/middle/typeck.rs
index 7e132ffbee6..6f77fc957b2 100644
--- a/src/rustc/middle/typeck.rs
+++ b/src/rustc/middle/typeck.rs
@@ -1349,18 +1349,6 @@ impl methods for @fn_ctxt {
         infer::mk_eqty(self.infcx, sub, sup)
     }
 
-    fn require_impure(sp: span) {
-        alt self.purity {
-          ast::unsafe_fn { ret; }
-          ast::impure_fn | ast::crust_fn { ret; }
-          ast::pure_fn {
-            self.ccx.tcx.sess.span_err(
-                sp,
-                "found impure expression in pure function decl");
-          }
-        }
-    }
-
     fn require_unsafe(sp: span, op: str) {
         alt self.purity {
           ast::unsafe_fn {/*ok*/}
@@ -2425,45 +2413,6 @@ fn check_pat(pcx: pat_ctxt, pat: @ast::pat, expected: ty::t) {
     }
 }
 
-fn require_pure_call(ccx: @crate_ctxt, caller_purity: ast::purity,
-                     callee: @ast::expr, sp: span) {
-    if caller_purity == ast::unsafe_fn { ret; }
-    let callee_purity = alt ccx.tcx.def_map.find(callee.id) {
-      some(ast::def_fn(_, p)) { p }
-      some(ast::def_variant(_, _)) { ast::pure_fn }
-      _ {
-        alt ccx.method_map.find(callee.id) {
-          some(method_static(did)) {
-            if did.crate == ast::local_crate {
-                alt ccx.tcx.items.get(did.node) {
-                  ast_map::node_method(m, _, _) { m.decl.purity }
-                  _ { ccx.tcx.sess.span_bug(sp,
-                             "Node not bound to a method") }
-                }
-            } else {
-                csearch::lookup_method_purity(ccx.tcx.sess.cstore, did)
-            }
-          }
-          some(method_param(iid, n_m, _, _)) | some(method_iface(iid, n_m)) {
-            ty::iface_methods(ccx.tcx, iid)[n_m].purity
-          }
-          none { ast::impure_fn }
-        }
-      }
-    };
-    alt (caller_purity, callee_purity) {
-      (ast::impure_fn, ast::unsafe_fn) | (ast::crust_fn, ast::unsafe_fn) {
-        ccx.tcx.sess.span_err(sp, "safe function calls function marked \
-                                   unsafe");
-      }
-      (ast::pure_fn, ast::unsafe_fn) | (ast::pure_fn, ast::impure_fn) {
-        ccx.tcx.sess.span_err(sp, "pure function calls function not \
-                                   known to be pure");
-      }
-      _ {}
-    }
-}
-
 fn check_expr_with(fcx: @fn_ctxt, expr: @ast::expr, expected: ty::t) -> bool {
     check_expr(fcx, expr, some(expected))
 }
@@ -2989,10 +2938,6 @@ fn check_expr_with_unifier(fcx: @fn_ctxt,
             r.fty
         };
 
-        // Need to restrict oper to being an explicit expr_path if we're
-        // inside a pure function
-        require_pure_call(fcx.ccx, fcx.purity, f, sp);
-
         // Pull the return type out of the type of the function.
         alt structure_of(fcx, sp, fty) {
           ty::ty_fn(f) {
@@ -3277,7 +3222,6 @@ fn check_expr_with_unifier(fcx: @fn_ctxt,
         bot |= check_binop(fcx, expr, op, lhs, rhs);
       }
       ast::expr_assign_op(op, lhs, rhs) {
-        fcx.require_impure(expr.span);
         bot |= check_binop(fcx, expr, op, lhs, rhs);
         let lhs_t = fcx.expr_ty(lhs);
         let result_t = fcx.expr_ty(expr);
@@ -3437,15 +3381,12 @@ fn check_expr_with_unifier(fcx: @fn_ctxt,
         fcx.write_ty(id, fcx.expr_ty(a));
       }
       ast::expr_move(lhs, rhs) {
-        fcx.require_impure(expr.span);
         bot = check_assignment(fcx, expr.span, lhs, rhs, id);
       }
       ast::expr_assign(lhs, rhs) {
-        fcx.require_impure(expr.span);
         bot = check_assignment(fcx, expr.span, lhs, rhs, id);
       }
       ast::expr_swap(lhs, rhs) {
-        fcx.require_impure(expr.span);
         bot = check_assignment(fcx, expr.span, lhs, rhs, id);
       }
       ast::expr_if(cond, thn, elsopt) {
diff --git a/src/test/compile-fail/native-unsafe-fn-called.rs b/src/test/compile-fail/native-unsafe-fn-called.rs
index 6459a423611..ee44500fee3 100644
--- a/src/test/compile-fail/native-unsafe-fn-called.rs
+++ b/src/test/compile-fail/native-unsafe-fn-called.rs
@@ -1,5 +1,5 @@
 // -*- rust -*-
-// error-pattern: safe function calls function marked unsafe
+
 #[abi = "cdecl"]
 native mod test {
     unsafe fn free();
@@ -7,5 +7,6 @@ native mod test {
 
 fn main() {
     test::free();
+    //!^ ERROR access to unsafe function requires unsafe function or block
 }
 
diff --git a/src/test/compile-fail/pure-modifies-aliased.rs b/src/test/compile-fail/pure-modifies-aliased.rs
new file mode 100644
index 00000000000..9e825b9daca
--- /dev/null
+++ b/src/test/compile-fail/pure-modifies-aliased.rs
@@ -0,0 +1,18 @@
+// Check that pure functions cannot modify aliased state.
+
+pure fn modify_in_ref(&&sum: {mut f: int}) {
+    sum.f = 3; //! ERROR assigning to mutable field prohibited in pure functions
+}
+
+pure fn modify_in_box(sum: @mut {f: int}) {
+    sum.f = 3; //! ERROR assigning to mutable field prohibited in pure functions
+}
+
+impl foo for int {
+    pure fn modify_in_box_rec(sum: @{mut f: int}) {
+        sum.f = self; //! ERROR assigning to mutable field prohibited in pure functions
+    }
+}
+
+fn main() {
+}
\ No newline at end of file
diff --git a/src/test/compile-fail/unsafe-fn-called-from-safe.rs b/src/test/compile-fail/unsafe-fn-called-from-safe.rs
index 62fcfa689d9..2353be31c2b 100644
--- a/src/test/compile-fail/unsafe-fn-called-from-safe.rs
+++ b/src/test/compile-fail/unsafe-fn-called-from-safe.rs
@@ -1,8 +1,7 @@
 // -*- rust -*-
-// error-pattern: safe function calls function marked unsafe
 
 unsafe fn f() { ret; }
 
 fn main() {
-    f();
+    f(); //! ERROR access to unsafe function requires unsafe function or block
 }
diff --git a/src/test/run-pass/pure-sum.rs b/src/test/run-pass/pure-sum.rs
new file mode 100644
index 00000000000..f5bc71d94b0
--- /dev/null
+++ b/src/test/run-pass/pure-sum.rs
@@ -0,0 +1,40 @@
+// Check that pure functions can modify local state.
+
+pure fn sums_to(v: [int], sum: int) -> bool {
+    let mut i = 0u, sum0 = 0;
+    while i < v.len() {
+        sum0 += v[i];
+        i += 1u;
+    }
+    ret sum0 == sum;
+}
+
+pure fn sums_to_using_uniq(v: [int], sum: int) -> bool {
+    let mut i = 0u, sum0 = ~mut 0;
+    while i < v.len() {
+        *sum0 += v[i];
+        i += 1u;
+    }
+    ret *sum0 == sum;
+}
+
+pure fn sums_to_using_rec(v: [int], sum: int) -> bool {
+    let mut i = 0u, sum0 = {f: 0};
+    while i < v.len() {
+        sum0.f += v[i];
+        i += 1u;
+    }
+    ret sum0.f == sum;
+}
+
+pure fn sums_to_using_uniq_rec(v: [int], sum: int) -> bool {
+    let mut i = 0u, sum0 = {f: ~mut 0};
+    while i < v.len() {
+        *sum0.f += v[i];
+        i += 1u;
+    }
+    ret *sum0.f == sum;
+}
+
+fn main() {
+}
\ No newline at end of file