experiment: treat pure ingredients as immutable

This isn't complete yet:

a) If you copy a variable the copy is not checked for mutations.

b) /contained-in might be a hack. It's needed because sometimes I want
to pass in two pointers to a data structure, say for deleting something
from a list. Both are conceptually the same structure, so it's
unnecessary for both to be products as well. There's also technical
reasons you *can't* return both, because if you pass in the same
variable to both ingredients (say you want to remove the first element
of a list), the products now must write to the same variable as well
(thanks to our earlier /same-as-ingredient constraint), and what value
gets written last is not something we want to be thinking about.

c) Even if we stick with /contained-in, it's ambiguous. I'm using it
sometimes to say "a belongs to b", sometimes to say "a _will_ belong to
b after the recipe returns. Perhaps that distinction doesn't matter.
We'll see.

d) Should we be encouraged to say ingredients are contained in products?
At the moment 'push' works only because of mu's incomplete analysis.
Once we fix a) above, it's unclear what the right header should be.

e) edit/ isn't close to working yet.

(No more commit numbers since I'm now starting a branch, and can't rely
on a stable ordering as I rebase. For the same reason I'm not including
the changes to .traces/, to minimize merge conflicts.)

3 files changed, 257 insertions, 48 deletions

diff --git a/060immutable.cc b/060immutable.cc
new file mode 100644
index 00000000..9acd74e3
--- /dev/null
+++ b/060immutable.cc
@@ -0,0 +1,211 @@
+//: Addresses passed into of a recipe are meant to be immutable unless they're
+//: also products. This layer will start enforcing this check.
+
+:(scenario can_modify_value_ingredients)
+% Hide_warnings = true;
+recipe main [
+  local-scope
+  p:address:point <- new point:type
+  foo *p
+]
+recipe foo p:point [
+  local-scope
+  load-ingredients
+  x:address:number <- get-address p, x:offset
+  *x <- copy 34
+]
+$warn: 0
+
+:(scenario can_modify_ingredients_that_are_also_products)
+% Hide_warnings = true;
+recipe main [
+  local-scope
+  p:address:point <- new point:type
+  p <- foo p
+]
+recipe foo p:address:point -> p:address:point [
+  local-scope
+  load-ingredients
+  x:address:number <- get-address *p, x:offset
+  *x <- copy 34
+]
+$warn: 0
+
+:(scenario cannot_take_address_inside_immutable_ingredients)
+% Hide_warnings = true;
+recipe main [
+  local-scope
+  p:address:point <- new point:type
+  foo p
+]
+recipe foo p:address:point [
+  local-scope
+  load-ingredients
+  x:address:number <- get-address *p, x:offset
+  *x <- copy 34
+]
++warn: foo: cannot modify ingredient p after instruction 'x:address:number <- get-address *p, x:offset' because it's not also a product of foo
+
+:(scenario cannot_call_mutating_recipes_on_immutable_ingredients)
+% Hide_warnings = true;
+recipe main [
+  local-scope
+  p:address:point <- new point:type
+  foo p
+]
+recipe foo p:address:point [
+  local-scope
+  load-ingredients
+  bar p
+]
+recipe bar p:address:point -> p:address:point [
+  local-scope
+  load-ingredients
+  x:address:number <- get-address *p, x:offset
+  *x <- copy 34
+]
++warn: foo: cannot modify ingredient p at instruction 'bar p' because it's not also a product of foo
+
+:(scenario can_traverse_immutable_ingredients)
+% Hide_warnings = true;
+container test-list [
+  next:address:test-list
+]
+recipe main [
+  local-scope
+  p:address:test-list <- new test-list:type
+  foo p
+]
+recipe foo p:address:test-list [
+  local-scope
+  load-ingredients
+  p2:address:test-list <- bar p
+]
+recipe bar x:address:test-list -> y:address:test-list [
+  local-scope
+  load-ingredients
+  y <- get *x, next:offset
+]
+$warn: 0
+
+:(before "End Transforms")
+Transform.push_back(check_immutable_ingredients);  // idempotent
+
+:(code)
+void check_immutable_ingredients(recipe_ordinal r) {
+  // to ensure a reagent isn't modified, it suffices to show that we never
+  // call get-address or index-address with it, and that any non-primitive
+  // recipe calls in the body aren't returning it as a product.
+  const recipe& caller = get(Recipe, r);
+  if (!caller.has_header) return;  // skip check for old-style recipes calling next-ingredient directly
+  for (long long int i = 0; i < SIZE(caller.ingredients); ++i) {
+    const reagent& current_ingredient = caller.ingredients.at(i);
+    if (!is_mu_address(current_ingredient)) continue;  // will be copied
+    if (is_present_in_products(caller, current_ingredient.name)) continue;  // not expected to be immutable
+    // End Immutable Ingredients Special-cases
+    for (long long int i = 0; i < SIZE(caller.steps); ++i) {
+      check_immutable_ingredient_in_instruction(caller.steps.at(i), current_ingredient.name, caller);
+    }
+  }
+}
+
+void check_immutable_ingredient_in_instruction(const instruction& inst, const string& current_ingredient_name, const recipe& caller) {
+  long long int current_ingredient_index = find_ingredient_index(inst, current_ingredient_name);
+  if (current_ingredient_index == -1) return;  // ingredient not found in call
+  reagent current_ingredient = inst.ingredients.at(current_ingredient_index);
+  canonize_type(current_ingredient);
+  if (!contains_key(Recipe, inst.operation)) {
+    // primitive recipe
+    if (inst.operation == GET_ADDRESS || inst.operation == INDEX_ADDRESS)
+      raise << maybe(caller.name) << "cannot modify ingredient " << current_ingredient_name << " after instruction '" << inst.to_string() << "' because it's not also a product of " << caller.name << '\n' << end();
+  }
+  else {
+    // defined recipe
+    if (!is_mu_address(current_ingredient)) return;  // making a copy is ok
+    if (is_modified_in_recipe(inst.operation, current_ingredient_index, caller))
+      raise << maybe(caller.name) << "cannot modify ingredient " << current_ingredient_name << " at instruction '" << inst.to_string() << "' because it's not also a product of " << caller.name << '\n' << end();
+  }
+}
+
+bool is_modified_in_recipe(recipe_ordinal r, long long int ingredient_index, const recipe& caller) {
+  const recipe& callee = get(Recipe, r);
+  if (!callee.has_header) {
+    raise << maybe(caller.name) << "can't check mutability of ingredients in " << callee.name << " because it uses 'next-ingredient' directly, rather than a recipe header.\n" << end();
+    return true;
+  }
+  return is_present_in_products(callee, callee.ingredients.at(ingredient_index).name);
+}
+
+bool is_present_in_products(const recipe& callee, const string& ingredient_name) {
+  for (long long int i = 0; i < SIZE(callee.products); ++i) {
+    if (callee.products.at(i).name == ingredient_name)
+      return true;
+  }
+  return false;
+}
+
+bool is_present_in_ingredients(const recipe& callee, const string& ingredient_name) {
+  for (long long int i = 0; i < SIZE(callee.ingredients); ++i) {
+    if (callee.ingredients.at(i).name == ingredient_name)
+      return true;
+  }
+  return false;
+}
+
+long long int find_ingredient_index(const instruction& inst, const string& ingredient_name) {
+  for (long long int i = 0; i < SIZE(inst.ingredients); ++i) {
+    if (inst.ingredients.at(i).name == ingredient_name)
+      return i;
+  }
+  return -1;
+}
+
+//: Sometimes you want to pass in two addresses, one pointing inside the
+//: other. For example, you want to delete a node from a linked list. You
+//: can't pass both pointers back out, because if a caller tries to make both
+//: identical then you can't tell which value will be written on the way out.
+//:
+//: Experimental solution: just tell mu that one points inside the other.
+//: This way we can return just one pointer as high up as necessary to capture
+//: all modifications performed by a recipe.
+//:
+//: We'll see if we end up wanting to abuse /contained-in for other reasons.
+
+:(scenarios transform)
+:(scenario can_modify_contained_in_addresses)
+#% Hide_warnings = true;
+container test-list [
+  next:address:test-list
+]
+recipe main [
+  local-scope
+  p:address:test-list <- new test-list:type
+  foo p
+]
+recipe foo p:address:test-list -> p:address:test-list [
+  local-scope
+  load-ingredients
+  p2:address:test-list <- test-next p
+  p <- test-remove p2, p
+]
+recipe test-next x:address:test-list -> y:address:test-list [
+  local-scope
+  load-ingredients
+  y <- get *x, next:offset
+]
+recipe test-remove x:address:test-list/contained-in:from, from:address:test-list -> from:address:test-list [
+  local-scope
+  load-ingredients
+  x2:address:address:test-list <- get-address *x, next:offset  # pretend modification
+]
+$warn: 0
+
+:(before "End Immutable Ingredients Special-cases")
+if (has_property(current_ingredient, "contained-in")) {
+  const string_tree* tmp = property(current_ingredient, "contained-in");
+  if (tmp->left || tmp->right
+      || !is_present_in_ingredients(caller, tmp->value)
+      || !is_present_in_products(caller, tmp->value))
+    raise_error << maybe(caller.name) << "contained-in can only point to another ingredient+product, but got " << debug_string(property(current_ingredient, "contained-in")) << '\n' << end();
+  continue;
+}
diff --git a/073list.mu b/073list.mu
index 1e0e6a17..6f27a7a8 100644
--- a/073list.mu
+++ b/073list.mu
@@ -8,6 +8,7 @@ container list:_elem [
   next:address:list:_elem
 ]
 
+# should I say in/contained-in:result, allow ingredients to refer to products?
 recipe push x:_elem, in:address:list:_elem -> result:address:list:_elem [
   local-scope
   load-ingredients
diff --git a/075duplex_list.mu b/075duplex_list.mu
index 02bb3152..1f00a0cf 100644
--- a/075duplex_list.mu
+++ b/075duplex_list.mu
@@ -6,17 +6,21 @@ container duplex-list:_elem [
   prev:address:duplex-list:_elem
 ]
 
-recipe push x:_elem, in:address:duplex-list:_elem -> result:address:duplex-list:_elem [
+# should I say in/contained-in:result, allow ingredients to refer to products?
+recipe push x:_elem, in:address:duplex-list:_elem -> in:address:duplex-list:_elem [
   local-scope
   load-ingredients
-  result <- new {(duplex-list _elem): type}
+  result:address:duplex-list:_elem <- new {(duplex-list _elem): type}
   val:address:_elem <- get-address *result, value:offset
   *val <- copy x
   next:address:address:duplex-list:_elem <- get-address *result, next:offset
   *next <- copy in
-  reply-unless in
-  prev:address:address:duplex-list:_elem <- get-address *in, prev:offset
-  *prev <- copy result
+  {
+    break-unless in
+    prev:address:address:duplex-list:_elem <- get-address *in, prev:offset
+    *prev <- copy result
+  }
+  reply result  # needed explicitly because we need to replace 'in' with 'result'
 ]
 
 recipe first in:address:duplex-list:_elem -> result:_elem [
@@ -82,11 +86,11 @@ scenario duplex-list-handling [
   ]
 ]
 
-# Inserts 'x' after 'in'. Returns some pointer into the list.
-recipe insert x:_elem, in:address:duplex-list:_elem -> new-node:address:duplex-list:_elem [
+# insert 'x' after 'in'
+recipe insert x:_elem, in:address:duplex-list:_elem -> in:address:duplex-list:_elem [
   local-scope
   load-ingredients
-  new-node <- new {(duplex-list _elem): type}
+  new-node:address:duplex-list:_elem <- new {(duplex-list _elem): type}
   val:address:_elem <- get-address *new-node, value:offset
   *val <- copy x
   next-node:address:duplex-list:_elem <- get *in, next:offset
@@ -100,11 +104,10 @@ recipe insert x:_elem, in:address:duplex-list:_elem -> new-node:address:duplex-l
   y <- get-address *new-node, next:offset
   *y <- copy next-node
   # if next-node is not null
-  reply-unless next-node, new-node
+  reply-unless next-node
   # next-node.prev = new-node
   y <- get-address *next-node, prev:offset
   *y <- copy new-node
-  reply new-node  # just signalling something changed; don't rely on the result
 ]
 
 scenario inserting-into-duplex-list [
@@ -185,7 +188,7 @@ scenario inserting-after-start-of-duplex-list [
     1:address:duplex-list:character <- push 3, 0
     1:address:duplex-list:character <- push 4, 1:address:duplex-list:character
     1:address:duplex-list:character <- push 5, 1:address:duplex-list:character
-    2:address:duplex-list:character <- insert 6, 1:address:duplex-list:character
+    1:address:duplex-list:character <- insert 6, 1:address:duplex-list:character
     # check structure like before
     2:address:duplex-list:character <- copy 1:address:duplex-list:character
     3:character <- first 2:address:duplex-list:character
@@ -215,38 +218,37 @@ scenario inserting-after-start-of-duplex-list [
   ]
 ]
 
-# Removes 'in' from its surrounding list. Returns some valid pointer into the
-# rest of the list.
+# remove 'x' from its surrounding list 'in'
 #
-# Returns null if and only if list is empty. Beware: in that case any pointers
-# to the head are now invalid.
-recipe remove in:address:duplex-list:_elem -> next-node:address:duplex-list:_elem [
+# Returns null if and only if list is empty. Beware: in that case any other
+# pointers to the head are now invalid.
+recipe remove x:address:duplex-list:_elem/contained-in:in, in:address:duplex-list:_elem -> in:address:duplex-list:_elem [
   local-scope
   load-ingredients
-  # if 'in' is null, return
-  reply-unless in, in
-  next-node:address:duplex-list:_elem <- get *in, next:offset
-  prev-node:address:duplex-list:_elem <- get *in, prev:offset
-  # null in's pointers
-  x:address:address:duplex-list:_elem <- get-address *in, next:offset
-  *x <- copy 0
-  x <- get-address *in, prev:offset
-  *x <- copy 0
+  # if 'x' is null, return
+  reply-unless x
+  next-node:address:duplex-list:_elem <- get *x, next:offset
+  prev-node:address:duplex-list:_elem <- get *x, prev:offset
+  # null x's pointers
+  tmp:address:address:duplex-list:_elem <- get-address *x, next:offset
+  *tmp <- copy 0
+  tmp <- get-address *x, prev:offset
+  *tmp <- copy 0
+  # if next-node is not null, set its prev pointer
   {
-    # if next-node is not null
     break-unless next-node
-    # next-node.prev = prev-node
-    x <- get-address *next-node, prev:offset
-    *x <- copy prev-node
+    tmp <- get-address *next-node, prev:offset
+    *tmp <- copy prev-node
   }
+  # if prev-node is not null, set its next pointer and return
   {
-    # if prev-node is not null
     break-unless prev-node
-    # prev-node.next = next-node
-    x <- get-address *prev-node, next:offset
-    *x <- copy next-node
-    reply prev-node
+    tmp <- get-address *prev-node, next:offset
+    *tmp <- copy next-node
+    reply
   }
+  # if prev-node is null, then we removed the node at 'in'
+  # return the new head rather than the old 'in'
   reply next-node
 ]
 
@@ -256,7 +258,7 @@ scenario removing-from-duplex-list [
     1:address:duplex-list:character <- push 4, 1:address:duplex-list:character
     1:address:duplex-list:character <- push 5, 1:address:duplex-list:character
     2:address:duplex-list:character <- next 1:address:duplex-list:character  # 2 points at second element
-    2:address:duplex-list:character <- remove 2:address:duplex-list:character
+    1:address:duplex-list:character <- remove 2:address:duplex-list:character, 1:address:duplex-list:character
     3:boolean <- equal 2:address:duplex-list:character, 0
     # check structure like before
     2:address:duplex-list:character <- copy 1:address:duplex-list:character
@@ -283,8 +285,7 @@ scenario removing-from-start-of-duplex-list [
     1:address:duplex-list:character <- push 3, 0
     1:address:duplex-list:character <- push 4, 1:address:duplex-list:character
     1:address:duplex-list:character <- push 5, 1:address:duplex-list:character
-    # removing from head? return value matters.
-    1:address:duplex-list:character <- remove 1:address:duplex-list:character
+    1:address:duplex-list:character <- remove 1:address:duplex-list:character, 1:address:duplex-list:character
     # check structure like before
     2:address:duplex-list:character <- copy 1:address:duplex-list:character
     3:character <- first 2:address:duplex-list:character
@@ -312,7 +313,7 @@ scenario removing-from-end-of-duplex-list [
     # delete last element
     2:address:duplex-list:character <- next 1:address:duplex-list:character
     2:address:duplex-list:character <- next 2:address:duplex-list:character
-    2:address:duplex-list:character <- remove 2:address:duplex-list:character
+    1:address:duplex-list:character <- remove 2:address:duplex-list:character, 1:address:duplex-list:character
     3:boolean <- equal 2:address:duplex-list:character, 0
     # check structure like before
     2:address:duplex-list:character <- copy 1:address:duplex-list:character
@@ -337,20 +338,16 @@ scenario removing-from-end-of-duplex-list [
 scenario removing-from-singleton-list [
   run [
     1:address:duplex-list:character <- push 3, 0
-    2:address:duplex-list:character <- remove 1:address:duplex-list:character
-    3:address:duplex-list:character <- get *1:address:duplex-list:character, next:offset
-    4:address:duplex-list:character <- get *1:address:duplex-list:character, prev:offset
+    1:address:duplex-list:character <- remove 1:address:duplex-list:character, 1:address:duplex-list:character
   ]
   memory-should-contain [
-    2 <- 0  # remove returned null
-    3 <- 0  # removed node is also detached
-    4 <- 0
+    1 <- 0  # back to an empty list
   ]
 ]
 
 # remove values between 'start' and 'end' (both exclusive)
 # also clear pointers back out from start/end for hygiene
-recipe remove-between start:address:duplex-list:_elem, end:address:duplex-list:_elem -> start:address:duplex-list:_elem [
+recipe remove-between start:address:duplex-list:_elem, end:address:duplex-list:_elem/contained-in:start -> start:address:duplex-list:_elem [
   local-scope
   load-ingredients
   reply-unless start
@@ -457,8 +454,8 @@ scenario remove-range-empty [
   ]
 ]
 
-# Inserts list beginning at 'new' after 'in'. Returns some pointer into the list.
-recipe insert-range in:address:duplex-list:_elem, start:address:duplex-list:_elem -> in:address:duplex-list:_elem [
+# insert list beginning at 'new' after 'in'
+recipe insert-range in:address:duplex-list:_elem, start:address:duplex-list:_elem/contained-in:in -> in:address:duplex-list:_elem [
   local-scope
   load-ingredients
   reply-unless in
@@ -484,7 +481,7 @@ recipe insert-range in:address:duplex-list:_elem, start:address:duplex-list:_ele
   *dest <- copy in
 ]
 
-recipe append in:address:duplex-list:_elem, new:address:duplex-list:_elem -> in:address:duplex-list:_elem [
+recipe append in:address:duplex-list:_elem, new:address:duplex-list:_elem/contained-in:in -> in:address:duplex-list:_elem [
   local-scope
   load-ingredients
   last:address:duplex-list:_elem <- last in