4089

Clean up how we reclaim local scopes.

It used to work like this (commit 3216):

  1. Update refcounts of products after every instruction, EXCEPT:

      a) when instruction is a non-primitive and the callee starts with
      'local-scope' (because it's already not decremented in 'return')

    OR:

      b) when instruction is primitive 'next-ingredient' or
      'next-ingredient-without-typechecking', and its result is saved to a
      variable in the default space (because it's already incremented at
      the time of the call)

  2. If a function starts with 'local-scope', force it to be reclaimed
  before each return. However, since locals may be returned, *very
  carefully* don't reclaim those. (See the logic in the old `escaping`
  and `should_update_refcount` functions.)

However, this approach had issues. We needed two separate commands for
'local-scope' (reclaim locals on exit) and 'new-default-space'
(programmer takes charge of reclaiming locals). The hard-coded
reclamation duplicated refcounting logic. In addition to adding
complexity, this implementation failed to work if a function overwrites
default-space after setting up a local-scope (the old default-space is
leaked). It also fails in the presence of continuations. Calling a
continuation more than once was guaranteed to corrupt memory (commit
3986).

After this commit, reclaiming local scopes now works like this:

  Update refcounts of products for every PRIMITIVE instruction.
  For non-primitive instructions, all the work happens in the `return`
  instruction:
    increment refcount of ingredients to `return`
      (unless -- one last bit of ugliness -- they aren't saved in the
      caller)
    decrement the refcount of the default-space
      use existing infrastructure for reclaiming as necessary
      if reclaiming default-space, first decrement refcount of each
      local
        again, use existing infrastructure for reclaiming as necessary

This commit (finally!) completes the bulk[1] of step 2 of the plan in
commit 3991. It was very hard until I gave up trying to tweak the
existing implementation and just test-drove layer 43 from scratch.

[1] There's still potential for memory corruption if we abuse
`default-space`. I should probably try to add warnings about that at
some point (todo in layer 45).

12 files changed, 124 insertions, 118 deletions

diff --git a/001help.cc b/001help.cc
index 45ab7bf1..814bdde7 100644
--- a/001help.cc
+++ b/001help.cc
@@ -256,3 +256,7 @@ using std::cerr;
 using std::string;
 
 #define unused  __attribute__((unused))
+
+#include <algorithm>
+using std::min;
+using std::max;
diff --git a/003trace.cc b/003trace.cc
index ea0c2882..e388b0f7 100644
--- a/003trace.cc
+++ b/003trace.cc
@@ -386,7 +386,6 @@ using std::list;
 using std::map;
 #include <set>
 using std::set;
-#include <algorithm>
 
 #include <sstream>
 using std::istringstream;
diff --git a/020run.cc b/020run.cc
index c4df88bd..d1bc77f4 100644
--- a/020run.cc
+++ b/020run.cc
@@ -95,15 +95,15 @@ void run_current_routine() {
     }
     //: used by a later layer
     if (write_products) {
-      Writing_products_of_instruction = true;
       if (SIZE(products) < SIZE(current_instruction().products)) {
         raise << SIZE(products) << " vs " << SIZE(current_instruction().products) << ": failed to write to all products in '" << to_original_string(current_instruction()) << "'\n" << end();
       }
       else {
-        for (int i = 0;  i < SIZE(current_instruction().products);  ++i)
+        for (int i = 0;  i < SIZE(current_instruction().products);  ++i) {
+          // Writing Instruction Product(i)
           write_memory(current_instruction().products.at(i), products.at(i));
+        }
       }
-      Writing_products_of_instruction = false;
     }
     // End Running One Instruction
     if (fall_through_to_next_instruction)
@@ -111,8 +111,6 @@ void run_current_routine() {
   }
   stop_running_current_routine:;
 }
-:(before "End Globals")
-bool Writing_products_of_instruction = false;
 
 :(code)
 //: hook replaced in a later layer
diff --git a/028call_return.cc b/028call_return.cc
index 0227acee..d77e1fa7 100644
--- a/028call_return.cc
+++ b/028call_return.cc
@@ -35,7 +35,7 @@ case RETURN: {
 }
 :(before "End Primitive Recipe Implementations")
 case RETURN: {
-  // Starting Reply
+  // Begin Return
   if (Trace_stream) {
     trace(9999, "trace") << current_instruction().name << ": decrementing callstack depth from " << Trace_stream->callstack_depth << end();
     --Trace_stream->callstack_depth;
@@ -51,7 +51,7 @@ case RETURN: {
     trace(9998, "run") << "result " << i << " is " << to_string(ingredients.at(i)) << end();
   // make return products available to caller
   copy(ingredients.begin(), ingredients.end(), inserter(products, products.begin()));
-  // End Reply
+  // End Return
   break;  // continue to process rest of *caller* instruction
 }
 
diff --git a/036refcount.cc b/036refcount.cc
index 477dc011..1f31bcbb 100644
--- a/036refcount.cc
+++ b/036refcount.cc
@@ -17,8 +17,12 @@ def main [
 +run: {2: ("address" "number")} <- copy {0: "literal"}
 +mem: decrementing refcount of 1000: 1 -> 0
 
-:(before "End write_memory(x) Special-cases")
-update_any_refcounts(x, data);
+:(after "Writing Instruction Product(i)")
+if (is_primitive(current_instruction().operation)) {
+  reagent/*copy*/ tmp = current_instruction().products.at(i);
+  canonize(tmp);
+  update_any_refcounts(tmp, products.at(i));
+}
 
 :(before "End Globals")
 bool Reclaim_memory = true;
@@ -30,17 +34,10 @@ else if (is_equal(*arg, "--no-reclaim")) {
 :(code)
 void update_any_refcounts(const reagent& canonized_x, const vector<double>& data) {
   if (!Reclaim_memory) return;
-  if (!should_update_refcounts()) return;
   increment_any_refcounts(canonized_x, data);  // increment first so we don't reclaim on x <- copy x
   decrement_any_refcounts(canonized_x);
 }
 
-//: escape hatch for a later layer
-bool should_update_refcounts() {
-  // End should_update_refcounts() Special-cases
-  return true;
-}
-
 void increment_any_refcounts(const reagent& canonized_x, const vector<double>& data) {
   if (is_mu_address(canonized_x)) {
     assert(scalar(data));
@@ -60,8 +57,8 @@ void increment_refcount(int new_address) {
 }
 
 void decrement_any_refcounts(const reagent& canonized_x) {
-  if (is_mu_address(canonized_x)) {
-    assert(canonized_x.value);
+  // Begin Decrement Refcounts(canonized_x)
+  if (is_mu_address(canonized_x) && canonized_x.value != 0) {
     assert(!canonized_x.metadata.size);
     decrement_refcount(get_or_insert(Memory, canonized_x.value), payload_type(canonized_x.type), payload_size(canonized_x));
   }
@@ -1057,7 +1054,7 @@ if (Run_profiler) {
 Num_refcount_updates[caller_frame.running_recipe][caller_frame.running_step_index]
     += (Total_refcount_updates - initial_num_refcount_updates);
 initial_num_refcount_updates = Total_refcount_updates;
-:(after "Starting Reply")
+:(after "Begin Return")
 if (Run_profiler) {
   Num_refcount_updates[current_call().running_recipe][current_call().running_step_index]
       += (Total_refcount_updates - initial_num_refcount_updates);
diff --git a/043space.cc b/043space.cc
index 378b20a9..2f11c6c2 100644
--- a/043space.cc
+++ b/043space.cc
@@ -4,6 +4,10 @@
 //:
 //: Spaces are often called 'scopes' in other languages. Stack frames are a
 //: limited form of space that can't outlive callers.
+//:
+//: Warning: messing with 'default-space' can corrupt memory. Don't do things
+//: like initialize default-space with some other function's default-space.
+//: Later we'll see how to chain spaces safely.
 
 //: Under the hood, a space is an array of locations in memory.
 :(before "End Mu Types Initialization")
@@ -157,12 +161,12 @@ def main [
 :(before "Read element" following "case INDEX:")
 element.properties.push_back(pair<string, string_tree*>("raw", NULL));
 
-//:: 'new-default-space' is a convenience operation to automatically deduce
+//:: 'local-scope' is a convenience operation to automatically deduce
 //:: the amount of space to allocate in a default space with names
 
-:(scenario new_default_space)
+:(scenario local_scope)
 def main [
-  new-default-space
+  local-scope
   x:num <- copy 0
   y:num <- copy 3
 ]
@@ -176,12 +180,12 @@ if (x.name == "number-of-locals")
 if (s == "number-of-locals") return true;
 
 :(before "End Rewrite Instruction(curr, recipe result)")
-// rewrite 'new-default-space' to
+// rewrite 'local-scope' to
 //   ```
 //   default-space:space <- new location:type, number-of-locals:literal
 //   ```
 // where number-of-locals is Name[recipe][""]
-if (curr.name == "new-default-space") {
+if (curr.name == "local-scope") {
   rewrite_default_space_instruction(curr);
 }
 :(code)
@@ -209,10 +213,9 @@ if (x.name == "number-of-locals") {
   return;
 }
 
-//:: 'local-scope' is like 'new-default-space' except that we'll reclaim the
-//:: default-space when the routine exits
+//:: try to reclaim the default-space when a recipe returns
 
-:(scenario local_scope)
+:(scenario local_scope_reclaimed_on_return)
 def main [
   1:num <- foo
   2:num <- foo
@@ -226,104 +229,102 @@ def foo [
 # both calls to foo should have received the same default-space
 +mem: storing 1 in location 3
 
-:(scenario local_scope_frees_up_addresses)
-def main [
-  local-scope
-  x:text <- new [abc]
-]
-+mem: clearing x:text
-
-:(before "End Rewrite Instruction(curr, recipe result)")
-if (curr.name == "local-scope") {
-  rewrite_default_space_instruction(curr);
-}
-
 //: todo: do this in a transform, rather than magically in the 'return' instruction
 :(after "Falling Through End Of Recipe")
-try_reclaim_locals();
-:(after "Starting Reply")
-try_reclaim_locals();
-
+reclaim_default_space();
+:(after "Begin Return")
+reclaim_default_space();
 :(code)
-void try_reclaim_locals() {
+void reclaim_default_space() {
   if (!Reclaim_memory) return;
-  // only reclaim routines starting with 'local-scope'
   const recipe_ordinal r = get(Recipe_ordinal, current_recipe_name());
   const recipe& exiting_recipe = get(Recipe, r);
-  if (exiting_recipe.steps.empty()) return;
-  const instruction& inst = exiting_recipe.steps.at(0);
-  if (inst.name_before_rewrite != "local-scope") return;
-  // reclaim any local variables unless they're being returned
-  vector<double> zeros;
+  if (!starts_by_setting_default_space(exiting_recipe)) return;
+  // Reclaim default-space
+  decrement_refcount(current_call().default_space,
+      exiting_recipe.steps.at(0).products.at(0).type->right,
+      /*refcount*/1 + /*array length*/1 + /*number-of-locals*/Name[r][""]);
+}
+bool starts_by_setting_default_space(const recipe& r) {
+  return !r.steps.empty()
+      && !r.steps.at(0).products.empty()
+      && r.steps.at(0).products.at(0).name == "default-space";
+}
+
+//:
+
+:(scenario local_scope_reclaims_locals)
+def main [
+  local-scope
+  x:text <- new [abc]
+]
+# x
++mem: automatically abandoning 1004
+# local-scope
++mem: automatically abandoning 1000
+
+:(before "Reclaim default-space")
+if (get_or_insert(Memory, current_call().default_space) <= 1) {
+  set<string> reclaimed_locals;
+  trace(9999, "mem") << "trying to reclaim locals" << end();
   for (int i = /*leave default space for last*/1;  i < SIZE(exiting_recipe.steps);  ++i) {
     const instruction& inst = exiting_recipe.steps.at(i);
     for (int i = 0;  i < SIZE(inst.products);  ++i) {
-      const reagent& product = inst.products.at(i);
+      reagent/*copy*/ product = inst.products.at(i);
+      if (reclaimed_locals.find(product.name) != reclaimed_locals.end()) continue;
+      reclaimed_locals.insert(product.name);
       // local variables only
       if (has_property(product, "lookup")) continue;
       if (has_property(product, "raw")) continue;  // tests often want to check such locations after they run
-      if (escaping(product)) continue;
       // End Checks For Reclaiming Locals
-      trace(9999, "mem") << "clearing " << product.original_string << end();
-      zeros.resize(size_of(product));
-      write_memory(product, zeros);
+      trace(9999, "mem") << "trying to reclaim local " << product.original_string << end();
+      canonize(product);
+      decrement_any_refcounts(product);
     }
   }
-  trace(9999, "mem") << "automatically abandoning " << current_call().default_space << end();
-  abandon(current_call().default_space,
-          inst.products.at(0).type->right,
-          /*refcount*/1 + /*array length*/1 + /*number-of-locals*/Name[r][""]);
 }
 
-//: Reclaiming local variables above requires remembering what name an
-//: instruction had before any rewrites or transforms.
-:(before "End instruction Fields")
-string name_before_rewrite;
-:(before "End instruction Clear")
-name_before_rewrite.clear();
-:(before "End next_instruction(curr)")
-curr->name_before_rewrite = curr->name;
+:(scenario local_variables_can_outlive_call)
+def main [
+  local-scope
+  x:&:num <- new num:type
+  y:space <- copy default-space:space
+]
+-mem: automatically abandoning 1005
 
+//:
+
+:(scenario local_scope_does_not_reclaim_escaping_locals)
+def main [
+  1:text <- foo
+]
+def foo [
+  local-scope
+  x:text <- new [abc]
+  return x:text
+]
+# local-scope
++mem: automatically abandoning 1000
+# x
+-mem: automatically abandoning 1004
+
+:(after "Begin Return")  // before reclaiming default-space
+increment_refcounts_of_return_ingredients(ingredients);
 :(code)
-// is this reagent one of the values returned by the current (return) instruction?
-// is the corresponding ingredient saved in the caller?
-bool escaping(const reagent& r) {
-  assert(Current_routine);  // run-time only
-  // nothing escapes when you fall through past end of recipe
-  if (current_step_index() >= SIZE(Current_routine->steps())) return false;
-  for (long long i = 0;  i < SIZE(current_instruction().ingredients);  ++i) {
-    if (r == current_instruction().ingredients.at(i)) {
-      if (caller_uses_product(i))
-        return true;
+void increment_refcounts_of_return_ingredients(const vector<vector<double> >& ingredients) {
+  assert(current_instruction().operation == RETURN);
+  if (SIZE(Current_routine->calls) == 1)  // no caller to receive result
+    return;
+  const instruction& caller_instruction = to_instruction(*++Current_routine->calls.begin());
+  for (int i = 0;  i < min(SIZE(current_instruction().ingredients), SIZE(caller_instruction.products));  ++i) {
+    if (!is_dummy(caller_instruction.products.at(i))) {
+      // no need to canonize ingredient because we ignore its value
+      increment_any_refcounts(current_instruction().ingredients.at(i), ingredients.at(i));
     }
   }
-  return false;
-}
-
-//: since we don't decrement refcounts for escaping values above, make sure we
-//: don't increment them when the caller saves them either
-
-:(before "End should_update_refcounts() Special-cases")
-if (Writing_products_of_instruction) {
-  const instruction& inst = current_instruction();
-  // should_update_refcounts() Special-cases When Writing Products Of Primitive Instructions
-  if (is_primitive(inst.operation)) return true;
-  if (!contains_key(Recipe, inst.operation)) return true;
-  const recipe& callee = get(Recipe, inst.operation);
-  if (callee.steps.empty()) return true;
-  return callee.steps.at(0).name_before_rewrite != "local-scope";  // callees that call local-scope are already dealt with before return
 }
 
-:(code)
-bool caller_uses_product(int product_index) {
-  assert(Current_routine);  // run-time only
-  assert(!Current_routine->calls.empty());
-  if (Current_routine->calls.size() == 1) return false;
-  const call& caller = *++Current_routine->calls.begin();
-  const instruction& caller_inst = to_instruction(caller);
-  if (product_index >= SIZE(caller_inst.products)) return false;
-  return !is_dummy(caller_inst.products.at(product_index));
-}
+//:
 
 :(scenario local_scope_frees_up_addresses_inside_containers)
 container foo [
@@ -336,10 +337,6 @@ def main [
   y:foo <- merge 34, x:&:num
   # x and y are both cleared when main returns
 ]
-+mem: clearing x:&:num
-+mem: decrementing refcount of 1006: 2 -> 1
-+mem: clearing y:foo
-+mem: decrementing refcount of 1006: 1 -> 0
 +mem: automatically abandoning 1006
 
 :(scenario local_scope_returns_addresses_inside_containers)
@@ -407,10 +404,8 @@ void check_default_space(const recipe_ordinal r) {
   if (!contains_non_special_name(r)) return;
   trace(9991, "transform") << "--- check that recipe " << caller.name << " sets default-space" << end();
   if (caller.steps.empty()) return;
-  if (caller.steps.at(0).products.empty()
-      || caller.steps.at(0).products.at(0).name != "default-space") {
+  if (!starts_by_setting_default_space(caller))
     raise << caller.name << " does not seem to start with 'local-scope' or 'default-space'\n" << end();
-  }
 }
 :(after "Load Mu Prelude")
 Hide_missing_default_space_errors = false;
diff --git a/045closure_name.cc b/045closure_name.cc
index 7852b92e..f7c0082f 100644
--- a/045closure_name.cc
+++ b/045closure_name.cc
@@ -2,6 +2,9 @@
 //: spaces together. When a variable has a property of /space:1, it looks up
 //: the variable in the chained/surrounding space. /space:2 looks up the
 //: surrounding space of the surrounding space, etc.
+//:
+//: todo: warn on default-space abuse. default-space for one function should
+//: never come from another, otherwise memory will be corrupted.
 
 :(scenario closure)
 def main [
@@ -149,7 +152,7 @@ def f [
 //: extra test for try_reclaim_locals() from previous layers
 :(scenario local_scope_ignores_nonlocal_spaces)
 def new-scope [
-  new-default-space
+  local-scope
   x:&:num <- new number:type
   *x:&:num <- copy 34
   return default-space:space
diff --git a/053recipe_header.cc b/053recipe_header.cc
index 9e01db42..513cfc4e 100644
--- a/053recipe_header.cc
+++ b/053recipe_header.cc
@@ -640,7 +640,3 @@ void check_recipe_header_constraints(const recipe_ordinal r) {
     raise << "recipe 'main' must return at most a single product, a number\n" << end();
   }
 }
-
-:(before "End Includes")
-using std::min;
-using std::max;
diff --git a/057immutable.cc b/057immutable.cc
index e1a17a84..4657ade0 100644
--- a/057immutable.cc
+++ b/057immutable.cc
@@ -321,7 +321,7 @@ def main [
   run-closure b:&:num, a:space
 ]
 def new-closure [
-  new-default-space
+  local-scope
   x:&:num <- new number:type
   return default-space
 ]
diff --git a/062convert_ingredients_to_text.cc b/062convert_ingredients_to_text.cc
index cf639b9e..abbacb1e 100644
--- a/062convert_ingredients_to_text.cc
+++ b/062convert_ingredients_to_text.cc
@@ -143,6 +143,15 @@ bool is_static_array(const reagent& x) {
   return !x.type->atom && x.type->left->atom && x.type->left->name == "array";
 }
 
+//: Supporting 'append' above requires remembering what name an instruction
+//: had before any rewrites or transforms.
+:(before "End instruction Fields")
+string name_before_rewrite;
+:(before "End instruction Clear")
+name_before_rewrite.clear();
+:(before "End next_instruction(curr)")
+curr->name_before_rewrite = curr->name;
+
 :(scenarios run)
 :(scenario append_other_types_to_text)
 def main [
diff --git a/071deep_copy.cc b/071deep_copy.cc
index 96f2671c..ffeb00bd 100644
--- a/071deep_copy.cc
+++ b/071deep_copy.cc
@@ -263,6 +263,8 @@ int deep_copy_address(const reagent& canonized_in, map<int, int>& addresses_copi
   if (contains_key(addresses_copied, in_address)) {
     int out = get(addresses_copied, in_address);
     trace(9991, "run") << "deep-copy: copy already exists: " << out << end();
+    assert(contains_key(Memory, out));  // refcount must already be incremented
+    ++get(Memory, out);
     return out;
   }
   int out = allocate(payload_size(canonized_in));
@@ -405,9 +407,9 @@ def main [
   y:&:foo <- deep-copy x
   1:num/raw <- get *y, p:offset
   y2:&:foo <- get *y, q:offset
-  stash y [vs] y2
   2:bool/raw <- equal y, y2  # is it still a cycle?
   3:bool/raw <- equal x, y  # is it the same cycle?
+  # not bothering cleaning up; both cycles leak memory
 ]
 +mem: storing 34 in location 1
 # deep copy also contains a cycle
@@ -415,6 +417,9 @@ def main [
 # but it's a completely different (disjoint) cycle
 +mem: storing 0 in location 3
 
+//: todo: version of deep_copy_cycles that breaks cycles at end and verifies no memory leaks
+//: needs approximate matching over scenario traces
+
 :(scenario deep_copy_skips_channel)
 # ugly! dummy 'channel' type if we happen to be building without that layer
 % if (!contains_key(Type_ordinal, "channel")) get_or_insert(Type, put(Type_ordinal, "channel", Next_type_ordinal++)).name = "channel";
diff --git a/counters.mu b/counters.mu
index 417f7f79..f0e514d7 100644
--- a/counters.mu
+++ b/counters.mu
@@ -3,7 +3,7 @@
 
 def new-counter n:num -> default-space:space [
   default-space <- new location:type, 30
-  load-ingredients
+  load-ingredients  # initialize n
 ]
 
 def increment-counter outer:space/names:new-counter, x:num -> n:num/space:1 [