From e5c11a5137d538b7713dd8708ca767c208824c06 Mon Sep 17 00:00:00 2001 From: "Kartik K. Agaram" Date: Mon, 26 Dec 2016 01:17:01 -0800 Subject: 3709 - line numbers in html Each line number also gets an anchor name, but I'm not hyperlinking them for now because I don't want to encourage bookmarking these links just yet. They aren't permalinks because every revision may change what's at any given line number. --- html/057immutable.cc.html | 1184 +++++++++++++++++++++++---------------------- 1 file changed, 604 insertions(+), 580 deletions(-) (limited to 'html/057immutable.cc.html') diff --git a/html/057immutable.cc.html b/html/057immutable.cc.html index 262bcf6d..8546a2d0 100644 --- a/html/057immutable.cc.html +++ b/html/057immutable.cc.html @@ -6,7 +6,7 @@ - + - + 
-//: Ingredients of a recipe are meant to be immutable unless they're also
-//: products. This layer will start enforcing this check.
-//:
-//: One hole for now: variables in surrounding spaces are implicitly mutable.
-//: [tag: todo]
-
-:(scenario can_modify_ingredients_that_are_also_products)
-# mutable container
-def main [
-  local-scope
-  p:point <- merge 34, 35
-  p <- foo p
-]
-def foo p:point -> p:point [
-  local-scope
-  load-ingredients
-  p <- put p, x:offset, 34
-]
-$error: 0
-
-:(scenario can_modify_ingredients_that_are_also_products_2)
-def main [
-  local-scope
-  p:&:point <- new point:type
-  p <- foo p
-]
-# mutable address to container
-def foo p:&:point -> p:&:point [
-  local-scope
-  load-ingredients
-  *p <- put *p, x:offset, 34
-]
-$error: 0
-
-:(scenario can_modify_ingredients_that_are_also_products_3)
-def main [
-  local-scope
-  p:&:@:num <- new number:type, 3
-  p <- foo p
-]
-# mutable address
-def foo p:&:@:num -> p:&:@:num [
-  local-scope
-  load-ingredients
-  *p <- put-index *p, 0, 34
-]
-$error: 0
-
-:(scenario ignore_literal_ingredients_for_immutability_checks)
-def main [
-  local-scope
-  p:&:d1 <- new d1:type
-  q:num <- foo p
-]
-def foo p:&:d1 -> q:num [
-  local-scope
-  load-ingredients
-  x:&:d1 <- new d1:type
-  *x <- put *x, p:offset, 34  # ignore this 'p'
-  return 36
-]
-container d1 [
-  p:num
-  q:num
-]
-$error: 0
-
-:(scenario cannot_modify_immutable_ingredients)
-% Hide_errors = true;
-def main [
-  local-scope
-  x:&:num <- new number:type
-  foo x
-]
-# immutable address to primitive
-def foo x:&:num [
-  local-scope
-  load-ingredients
-  *x <- copy 34
-]
-+error: foo: cannot modify 'x' in instruction '*x <- copy 34' because it's an ingredient of recipe foo but not also a product
-
-:(scenario cannot_modify_immutable_containers)
-% Hide_errors = true;
-def main [
-  local-scope
-  x:point-number <- merge 34, 35, 36
-  foo x
-]
-# immutable container
-def foo x:point-number [
-  local-scope
-  load-ingredients
-  # copy an element: ok
-  y:point <- get x, xy:offset
-  # modify the element: boom
-  # This could be ok if y contains no addresses, but we're not going to try to be that smart.
-  # It also makes the rules easier to reason about. If it's just an ingredient, just don't try to change it.
-  y <- put y, x:offset, 37
-]
-+error: foo: cannot modify 'y' in instruction 'y <- put y, x:offset, 37' because that would modify 'x' which is an ingredient of recipe foo but not also a product
-
-:(scenario can_modify_immutable_pointers)
-def main [
-  local-scope
-  x:&:num <- new number:type
-  foo x
-]
-def foo x:&:num [
-  local-scope
-  load-ingredients
-  # modify the address, not the payload
-  x <- copy 0
-]
-$error: 0
-
-:(scenario can_modify_immutable_pointers_but_not_their_payloads)
-% Hide_errors = true;
-def main [
-  local-scope
-  x:&:num <- new number:type
-  foo x
-]
-def foo x:&:num [
-  local-scope
-  load-ingredients
-  # modify address; ok
-  x <- new number:type
-  # modify payload: boom
-  # this could be ok, but we're not going to try to be that smart
-  *x <- copy 34
-]
-+error: foo: cannot modify 'x' in instruction '*x <- copy 34' because it's an ingredient of recipe foo but not also a product
-
-:(scenario cannot_call_mutating_recipes_on_immutable_ingredients)
-% Hide_errors = true;
-def main [
-  local-scope
-  p:&:point <- new point:type
-  foo p
-]
-def foo p:&:point [
-  local-scope
-  load-ingredients
-  bar p
-]
-def bar p:&:point -> p:&:point [
-  local-scope
-  load-ingredients
-  # p could be modified here, but it doesn't have to be, it's already marked
-  # mutable in the header
-]
-+error: foo: cannot modify 'p' in instruction 'bar p' because it's an ingredient of recipe foo but not also a product
-
-:(scenario cannot_modify_copies_of_immutable_ingredients)
-% Hide_errors = true;
-def main [
-  local-scope
-  p:&:point <- new point:type
-  foo p
-]
-def foo p:&:point [
-  local-scope
-  load-ingredients
-  q:&:point <- copy p
-  *q <- put *q, x:offset, 34
-]
-+error: foo: cannot modify 'q' in instruction '*q <- put *q, x:offset, 34' because that would modify p which is an ingredient of recipe foo but not also a product
-
-:(scenario can_modify_copies_of_mutable_ingredients)
-def main [
-  local-scope
-  p:&:point <- new point:type
-  foo p
-]
-def foo p:&:point -> p:&:point [
-  local-scope
-  load-ingredients
-  q:&:point <- copy p
-  *q <- put *q, x:offset, 34
-]
-$error: 0
-
-:(scenario cannot_modify_address_inside_immutable_ingredients)
-% Hide_errors = true;
-container foo [
-  x:&:@:num  # contains an address
-]
-def main [
-  # don't run anything
-]
-def foo a:&:foo [
-  local-scope
-  load-ingredients
-  x:&:@:num <- get *a, x:offset  # just a regular get of the container
-  *x <- put-index *x, 0, 34  # but then a put-index on the result
-]
-+error: foo: cannot modify 'x' in instruction '*x <- put-index *x, 0, 34' because that would modify a which is an ingredient of recipe foo but not also a product
-
-:(scenario cannot_modify_address_inside_immutable_ingredients_2)
-container foo [
-  x:&:@:num  # contains an address
-]
-def main [
-  # don't run anything
-]
-def foo a:&:foo [
-  local-scope
-  load-ingredients
-  b:foo <- merge 0
-  # modify b, completely unrelated to immutable ingredient a
-  x:&:@:num <- get b, x:offset
-  *x <- put-index *x, 0, 34
-]
-$error: 0
-
-:(scenario cannot_modify_address_inside_immutable_ingredients_3)
-% Hide_errors = true;
-def main [
-  # don't run anything
-]
-def foo a:&:@:&:num [
-  local-scope
-  load-ingredients
-  x:&:num <- index *a, 0  # just a regular index of the array
-  *x <- copy 34  # but then modify the result
-]
-+error: foo: cannot modify 'x' in instruction '*x <- copy 34' because that would modify a which is an ingredient of recipe foo but not also a product
-
-:(scenario cannot_modify_address_inside_immutable_ingredients_4)
-def main [
-  # don't run anything
-]
-def foo a:&:@:&:num [
-  local-scope
-  load-ingredients
-  b:&:@:&:num <- new {(address number): type}, 3
-  # modify b, completely unrelated to immutable ingredient a
-  x:&:num <- index *b, 0
-  *x <- copy 34
-]
-$error: 0
-
-:(scenario latter_ingredient_of_index_is_immutable)
-def main [
-  # don't run anything
-]
-def foo a:&:@:&:@:num, b:num -> a:&:@:&:@:num [
-  local-scope
-  load-ingredients
-  x:&:@:num <- index *a, b
-  *x <- put-index *x, 0, 34
-]
-$error: 0
-
-:(scenario can_traverse_immutable_ingredients)
-container test-list [
-  next:&:test-list
-]
-def main [
-  local-scope
-  p:&:test-list <- new test-list:type
-  foo p
-]
-def foo p:&:test-list [
-  local-scope
-  load-ingredients
-  p2:&:test-list <- bar p
-]
-def bar x:&:test-list -> y:&:test-list [
-  local-scope
-  load-ingredients
-  y <- get *x, next:offset
-]
-$error: 0
-
-:(scenario treat_optional_ingredients_as_mutable)
-def main [
-  k:&:num <- new number:type
-  test k
-]
-# recipe taking an immutable address ingredient
-def test k:&:num [
-  local-scope
-  load-ingredients
-  foo k
-]
-# ..calling a recipe with an optional address ingredient
-def foo -> [
-  local-scope
-  load-ingredients
-  k:&:num, found?:bool <- next-ingredient
-  # we don't further check k for immutability, but assume it's mutable
-]
-$error: 0
-
-:(scenario treat_optional_ingredients_as_mutable_2)
-% Hide_errors = true;
-def main [
-  local-scope
-  p:&:point <- new point:type
-  foo p
-]
-def foo p:&:point [
-  local-scope
-  load-ingredients
-  bar p
-]
-def bar [
-  local-scope
-  load-ingredients
-  p:&:point <- next-ingredient  # optional ingredient; assumed to be mutable
-]
-+error: foo: cannot modify 'p' in instruction 'bar p' because it's an ingredient of recipe foo but not also a product
-
-//: when checking for immutable ingredients, remember to take space into account
-:(scenario check_space_of_reagents_in_immutability_checks)
-def main [
-  a:space <- new-closure
-  b:&:num <- new number:type
-  run-closure b:&:num, a:space
-]
-def new-closure [
-  new-default-space
-  x:&:num <- new number:type
-  return default-space
-]
-def run-closure x:&:num, s:space [
-  local-scope
-  load-ingredients
-  0:space/names:new-closure <- copy s
-  # different space; always mutable
-  *x:&:num/space:1 <- copy 34
-]
-$error: 0
-
-:(before "End Transforms")
-Transform.push_back(check_immutable_ingredients);  // idempotent
-
-:(code)
-void check_immutable_ingredients(const recipe_ordinal r) {
-  // to ensure an address reagent isn't modified, it suffices to show that
-  //   a) we never write to its contents directly,
-  //   b) we never call 'put' or 'put-index' on it, and
-  //   c) any non-primitive recipe calls in the body aren't returning it as a product
-  const recipe& caller = get(Recipe, r);
-  trace(9991, "transform") << "--- check mutability of ingredients in recipe " << caller.name << end();
-  if (!caller.has_header) return;  // skip check for old-style recipes calling next-ingredient directly
-  for (int i = 0;  i < SIZE(caller.ingredients);  ++i) {
-    const reagent& current_ingredient = caller.ingredients.at(i);
-    if (is_present_in_products(caller, current_ingredient.name)) continue;  // not expected to be immutable
-    // End Immutable Ingredients Special-cases
-    set<reagent> immutable_vars;
-    immutable_vars.insert(current_ingredient);
-    for (int i = 0;  i < SIZE(caller.steps);  ++i) {
-      const instruction& inst = caller.steps.at(i);
-      check_immutable_ingredient_in_instruction(inst, immutable_vars, current_ingredient.name, caller);
-      if (inst.operation == INDEX && SIZE(inst.ingredients) > 1 && inst.ingredients.at(1).name == current_ingredient.name) continue;
-      update_aliases(inst, immutable_vars);
-    }
-  }
-}
-
-void update_aliases(const instruction& inst, set<reagent>& current_ingredient_and_aliases) {
-  set<int> current_ingredient_indices = ingredient_indices(inst, current_ingredient_and_aliases);
-  if (!contains_key(Recipe, inst.operation)) {
-    // primitive recipe
-    switch (inst.operation) {
-      case COPY:
-        for (set<int>::iterator p = current_ingredient_indices.begin();  p != current_ingredient_indices.end();  ++p)
-          current_ingredient_and_aliases.insert(inst.products.at(*p).name);
-        break;
-      case GET:
-      case INDEX:
-      case MAYBE_CONVERT:
-        // current_ingredient_indices can only have 0 or one value
-        if (!current_ingredient_indices.empty() && !inst.products.empty()) {
-          if (is_mu_address(inst.products.at(0)) || is_mu_container(inst.products.at(0)) || is_mu_exclusive_container(inst.products.at(0)))
-            current_ingredient_and_aliases.insert(inst.products.at(0));
-        }
-        break;
-      default: break;
-    }
-  }
-  else {
-    // defined recipe
-    set<int> contained_in_product_indices = scan_contained_in_product_indices(inst, current_ingredient_indices);
-    for (set<int>::iterator p = contained_in_product_indices.begin();  p != contained_in_product_indices.end();  ++p) {
-      if (*p < SIZE(inst.products))
-        current_ingredient_and_aliases.insert(inst.products.at(*p));
-    }
-  }
-}
-
-set<int> scan_contained_in_product_indices(const instruction& inst, set<int>& ingredient_indices) {
-  set<reagent> selected_ingredients;
-  const recipe& callee = get(Recipe, inst.operation);
-  for (set<int>::iterator p = ingredient_indices.begin();  p != ingredient_indices.end();  ++p) {
-    if (*p >= SIZE(callee.ingredients)) continue;  // optional immutable ingredient
-    selected_ingredients.insert(callee.ingredients.at(*p));
-  }
-  set<int> result;
-  for (int i = 0;  i < SIZE(callee.products);  ++i) {
-    const reagent& current_product = callee.products.at(i);
-    const string_tree* contained_in_name = property(current_product, "contained-in");
-    if (contained_in_name && selected_ingredients.find(contained_in_name->value) != selected_ingredients.end())
-      result.insert(i);
-  }
-  return result;
-}
-
-:(scenarios transform)
-:(scenario immutability_infects_contained_in_variables)
-% Hide_errors = true;
-container test-list [
-  value:num
-  next:&:test-list
-]
-def main [
-  local-scope
-  p:&:test-list <- new test-list:type
-  foo p
-]
-def foo p:&:test-list [  # p is immutable
-  local-scope
-  load-ingredients
-  p2:&:test-list <- test-next p  # p2 is immutable
-  *p2 <- put *p2, value:offset, 34
-]
-def test-next x:&:test-list -> y:&:test-list/contained-in:x [
-  local-scope
-  load-ingredients
-  y <- get *x, next:offset
-]
-+error: foo: cannot modify 'p2' in instruction '*p2 <- put *p2, value:offset, 34' because that would modify p which is an ingredient of recipe foo but not also a product
-
-:(code)
-void check_immutable_ingredient_in_instruction(const instruction& inst, const set<reagent>& current_ingredient_and_aliases, const string& original_ingredient_name, const recipe& caller) {
-  // first check if the instruction is directly modifying something it shouldn't
-  for (int i = 0;  i < SIZE(inst.products);  ++i) {
-    if (has_property(inst.products.at(i), "lookup")
-        && current_ingredient_and_aliases.find(inst.products.at(i)) != current_ingredient_and_aliases.end()) {
-      string current_product_name = inst.products.at(i).name;
-      if (current_product_name == original_ingredient_name)
-        raise << maybe(caller.name) << "cannot modify '" << current_product_name << "' in instruction '" << inst.original_string << "' because it's an ingredient of recipe " << caller.name << " but not also a product\n" << end();
-      else
-        raise << maybe(caller.name) << "cannot modify '" << current_product_name << "' in instruction '" << inst.original_string << "' because that would modify " << original_ingredient_name << " which is an ingredient of recipe " << caller.name << " but not also a product\n" << end();
-      return;
-    }
-  }
-  // check if there's any indirect modification going on
-  set<int> current_ingredient_indices = ingredient_indices(inst, current_ingredient_and_aliases);
-  if (current_ingredient_indices.empty()) return;  // ingredient not found in call
-  for (set<int>::iterator p = current_ingredient_indices.begin();  p != current_ingredient_indices.end();  ++p) {
-    const int current_ingredient_index = *p;
-    reagent current_ingredient = inst.ingredients.at(current_ingredient_index);
-    canonize_type(current_ingredient);
-    const string& current_ingredient_name = current_ingredient.name;
-    if (!contains_key(Recipe, inst.operation)) {
-      // primitive recipe
-      // we got here only because we got an instruction with an implicit product, and the instruction didn't explicitly spell it out
-      //    put x, y:offset, z
-      // instead of
-      //    x <- put x, y:offset, z
-      if (inst.operation == PUT || inst.operation == PUT_INDEX) {
-        if (current_ingredient_index == 0) {
-          if (current_ingredient_name == original_ingredient_name)
-            raise << maybe(caller.name) << "cannot modify '" << current_ingredient_name << "' in instruction '" << inst.original_string << "' because it's an ingredient of recipe " << caller.name << " but not also a product\n" << end();
-          else
-            raise << maybe(caller.name) << "cannot modify '" << current_ingredient_name << "' in instruction '" << inst.original_string << "' because that would modify '" << original_ingredient_name << "' which is an ingredient of recipe " << caller.name << " but not also a product\n" << end();
-        }
-      }
-    }
-    else {
-      // defined recipe
-      if (is_modified_in_recipe(inst.operation, current_ingredient_index, caller)) {
-        if (current_ingredient_name == original_ingredient_name)
-          raise << maybe(caller.name) << "cannot modify '" << current_ingredient_name << "' in instruction '" << inst.original_string << "' because it's an ingredient of recipe " << caller.name << " but not also a product\n" << end();
-        else
-          raise << maybe(caller.name) << "cannot modify '" << current_ingredient_name << "' in instruction '" << inst.original_string << "' because that would modify '" << original_ingredient_name << "' which is an ingredient of recipe " << caller.name << " but not also a product\n" << end();
-      }
-    }
-  }
-}
-
-bool is_modified_in_recipe(const recipe_ordinal r, const 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 recipe " << callee.name << " because it uses 'next-ingredient' directly, rather than a recipe header.\n" << end();
-    return true;
-  }
-  if (ingredient_index >= SIZE(callee.ingredients)) return false;  // optional immutable ingredient
-  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 (int i = 0;  i < SIZE(callee.products);  ++i) {
-    if (callee.products.at(i).name == ingredient_name)
-      return true;
-  }
-  return false;
-}
-
-set<int> ingredient_indices(const instruction& inst, const set<reagent>& ingredient_names) {
-  set<int> result;
-  for (int i = 0;  i < SIZE(inst.ingredients);  ++i) {
-    if (is_literal(inst.ingredients.at(i))) continue;
-    if (ingredient_names.find(inst.ingredients.at(i)) != ingredient_names.end())
-      result.insert(i);
-  }
-  return result;
-}
-
-//: 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)
-container test-list [
-  value:num
-  next:&:test-list
-]
-def main [
-  local-scope
-  p:&:test-list <- new test-list:type
-  foo p
-]
-def foo p:&:test-list -> p:&:test-list [
-  local-scope
-  load-ingredients
-  p2:&:test-list <- test-next p
-  p <- test-remove p2, p
-]
-def test-next x:&:test-list -> y:&:test-list [
-  local-scope
-  load-ingredients
-  y <- get *x, next:offset
-]
-def test-remove x:&:test-list/contained-in:from, from:&:test-list -> from:&:test-list [
-  local-scope
-  load-ingredients
-  *x <- put *x, value:offset, 34  # can modify x
-]
-$error: 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->atom
-      || (!is_present_in_ingredients(caller, tmp->value)
-          && !is_present_in_products(caller, tmp->value))) {
-    raise << maybe(caller.name) << "/contained-in can only point to another ingredient or product, but got '" << to_string(property(current_ingredient, "contained-in")) << "'\n" << end();
-  }
-  continue;
-}
-
-:(scenario contained_in_check)
-container test-list [
-  value:num
-  next:&:test-list
-]
-def test-remove x:&:test-list/contained-in:result, from:&:test-list -> result:&:test-list [
-  local-scope
-  load-ingredients
-  result <- copy 0
-]
-$error: 0
+  1 //: Ingredients of a recipe are meant to be immutable unless they're also
+  2 //: products. This layer will start enforcing this check.
+  3 //:
+  4 //: One hole for now: variables in surrounding spaces are implicitly mutable.
+  5 //: [tag: todo]
+  6 
+  7 :(scenario can_modify_ingredients_that_are_also_products)
+  8 # mutable container
+  9 def main [
+ 10   local-scope
+ 11   p:point <- merge 34, 35
+ 12   p <- foo p
+ 13 ]
+ 14 def foo p:point -> p:point [
+ 15   local-scope
+ 16   load-ingredients
+ 17   p <- put p, x:offset, 34
+ 18 ]
+ 19 $error: 0
+ 20 
+ 21 :(scenario can_modify_ingredients_that_are_also_products_2)
+ 22 def main [
+ 23   local-scope
+ 24   p:&:point <- new point:type
+ 25   p <- foo p
+ 26 ]
+ 27 # mutable address to container
+ 28 def foo p:&:point -> p:&:point [
+ 29   local-scope
+ 30   load-ingredients
+ 31   *p <- put *p, x:offset, 34
+ 32 ]
+ 33 $error: 0
+ 34 
+ 35 :(scenario can_modify_ingredients_that_are_also_products_3)
+ 36 def main [
+ 37   local-scope
+ 38   p:&:@:num <- new number:type, 3
+ 39   p <- foo p
+ 40 ]
+ 41 # mutable address
+ 42 def foo p:&:@:num -> p:&:@:num [
+ 43   local-scope
+ 44   load-ingredients
+ 45   *p <- put-index *p, 0, 34
+ 46 ]
+ 47 $error: 0
+ 48 
+ 49 :(scenario ignore_literal_ingredients_for_immutability_checks)
+ 50 def main [
+ 51   local-scope
+ 52   p:&:d1 <- new d1:type
+ 53   q:num <- foo p
+ 54 ]
+ 55 def foo p:&:d1 -> q:num [
+ 56   local-scope
+ 57   load-ingredients
+ 58   x:&:d1 <- new d1:type
+ 59   *x <- put *x, p:offset, 34  # ignore this 'p'
+ 60   return 36
+ 61 ]
+ 62 container d1 [
+ 63   p:num
+ 64   q:num
+ 65 ]
+ 66 $error: 0
+ 67 
+ 68 :(scenario cannot_modify_immutable_ingredients)
+ 69 % Hide_errors = true;
+ 70 def main [
+ 71   local-scope
+ 72   x:&:num <- new number:type
+ 73   foo x
+ 74 ]
+ 75 # immutable address to primitive
+ 76 def foo x:&:num [
+ 77   local-scope
+ 78   load-ingredients
+ 79   *x <- copy 34
+ 80 ]
+ 81 +error: foo: cannot modify 'x' in instruction '*x <- copy 34' because it's an ingredient of recipe foo but not also a product
+ 82 
+ 83 :(scenario cannot_modify_immutable_containers)
+ 84 % Hide_errors = true;
+ 85 def main [
+ 86   local-scope
+ 87   x:point-number <- merge 34, 35, 36
+ 88   foo x
+ 89 ]
+ 90 # immutable container
+ 91 def foo x:point-number [
+ 92   local-scope
+ 93   load-ingredients
+ 94   # copy an element: ok
+ 95   y:point <- get x, xy:offset
+ 96   # modify the element: boom
+ 97   # This could be ok if y contains no addresses, but we're not going to try to be that smart.
+ 98   # It also makes the rules easier to reason about. If it's just an ingredient, just don't try to change it.
+ 99   y <- put y, x:offset, 37
+100 ]
+101 +error: foo: cannot modify 'y' in instruction 'y <- put y, x:offset, 37' because that would modify 'x' which is an ingredient of recipe foo but not also a product
+102 
+103 :(scenario can_modify_immutable_pointers)
+104 def main [
+105   local-scope
+106   x:&:num <- new number:type
+107   foo x
+108 ]
+109 def foo x:&:num [
+110   local-scope
+111   load-ingredients
+112   # modify the address, not the payload
+113   x <- copy 0
+114 ]
+115 $error: 0
+116 
+117 :(scenario can_modify_immutable_pointers_but_not_their_payloads)
+118 % Hide_errors = true;
+119 def main [
+120   local-scope
+121   x:&:num <- new number:type
+122   foo x
+123 ]
+124 def foo x:&:num [
+125   local-scope
+126   load-ingredients
+127   # modify address; ok
+128   x <- new number:type
+129   # modify payload: boom
+130   # this could be ok, but we're not going to try to be that smart
+131   *x <- copy 34
+132 ]
+133 +error: foo: cannot modify 'x' in instruction '*x <- copy 34' because it's an ingredient of recipe foo but not also a product
+134 
+135 :(scenario cannot_call_mutating_recipes_on_immutable_ingredients)
+136 % Hide_errors = true;
+137 def main [
+138   local-scope
+139   p:&:point <- new point:type
+140   foo p
+141 ]
+142 def foo p:&:point [
+143   local-scope
+144   load-ingredients
+145   bar p
+146 ]
+147 def bar p:&:point -> p:&:point [
+148   local-scope
+149   load-ingredients
+150   # p could be modified here, but it doesn't have to be, it's already marked
+151   # mutable in the header
+152 ]
+153 +error: foo: cannot modify 'p' in instruction 'bar p' because it's an ingredient of recipe foo but not also a product
+154 
+155 :(scenario cannot_modify_copies_of_immutable_ingredients)
+156 % Hide_errors = true;
+157 def main [
+158   local-scope
+159   p:&:point <- new point:type
+160   foo p
+161 ]
+162 def foo p:&:point [
+163   local-scope
+164   load-ingredients
+165   q:&:point <- copy p
+166   *q <- put *q, x:offset, 34
+167 ]
+168 +error: foo: cannot modify 'q' in instruction '*q <- put *q, x:offset, 34' because that would modify p which is an ingredient of recipe foo but not also a product
+169 
+170 :(scenario can_modify_copies_of_mutable_ingredients)
+171 def main [
+172   local-scope
+173   p:&:point <- new point:type
+174   foo p
+175 ]
+176 def foo p:&:point -> p:&:point [
+177   local-scope
+178   load-ingredients
+179   q:&:point <- copy p
+180   *q <- put *q, x:offset, 34
+181 ]
+182 $error: 0
+183 
+184 :(scenario cannot_modify_address_inside_immutable_ingredients)
+185 % Hide_errors = true;
+186 container foo [
+187   x:&:@:num  # contains an address
+188 ]
+189 def main [
+190   # don't run anything
+191 ]
+192 def foo a:&:foo [
+193   local-scope
+194   load-ingredients
+195   x:&:@:num <- get *a, x:offset  # just a regular get of the container
+196   *x <- put-index *x, 0, 34  # but then a put-index on the result
+197 ]
+198 +error: foo: cannot modify 'x' in instruction '*x <- put-index *x, 0, 34' because that would modify a which is an ingredient of recipe foo but not also a product
+199 
+200 :(scenario cannot_modify_address_inside_immutable_ingredients_2)
+201 container foo [
+202   x:&:@:num  # contains an address
+203 ]
+204 def main [
+205   # don't run anything
+206 ]
+207 def foo a:&:foo [
+208   local-scope
+209   load-ingredients
+210   b:foo <- merge 0
+211   # modify b, completely unrelated to immutable ingredient a
+212   x:&:@:num <- get b, x:offset
+213   *x <- put-index *x, 0, 34
+214 ]
+215 $error: 0
+216 
+217 :(scenario cannot_modify_address_inside_immutable_ingredients_3)
+218 % Hide_errors = true;
+219 def main [
+220   # don't run anything
+221 ]
+222 def foo a:&:@:&:num [
+223   local-scope
+224   load-ingredients
+225   x:&:num <- index *a, 0  # just a regular index of the array
+226   *x <- copy 34  # but then modify the result
+227 ]
+228 +error: foo: cannot modify 'x' in instruction '*x <- copy 34' because that would modify a which is an ingredient of recipe foo but not also a product
+229 
+230 :(scenario cannot_modify_address_inside_immutable_ingredients_4)
+231 def main [
+232   # don't run anything
+233 ]
+234 def foo a:&:@:&:num [
+235   local-scope
+236   load-ingredients
+237   b:&:@:&:num <- new {(address number): type}, 3
+238   # modify b, completely unrelated to immutable ingredient a
+239   x:&:num <- index *b, 0
+240   *x <- copy 34
+241 ]
+242 $error: 0
+243 
+244 :(scenario latter_ingredient_of_index_is_immutable)
+245 def main [
+246   # don't run anything
+247 ]
+248 def foo a:&:@:&:@:num, b:num -> a:&:@:&:@:num [
+249   local-scope
+250   load-ingredients
+251   x:&:@:num <- index *a, b
+252   *x <- put-index *x, 0, 34
+253 ]
+254 $error: 0
+255 
+256 :(scenario can_traverse_immutable_ingredients)
+257 container test-list [
+258   next:&:test-list
+259 ]
+260 def main [
+261   local-scope
+262   p:&:test-list <- new test-list:type
+263   foo p
+264 ]
+265 def foo p:&:test-list [
+266   local-scope
+267   load-ingredients
+268   p2:&:test-list <- bar p
+269 ]
+270 def bar x:&:test-list -> y:&:test-list [
+271   local-scope
+272   load-ingredients
+273   y <- get *x, next:offset
+274 ]
+275 $error: 0
+276 
+277 :(scenario treat_optional_ingredients_as_mutable)
+278 def main [
+279   k:&:num <- new number:type
+280   test k
+281 ]
+282 # recipe taking an immutable address ingredient
+283 def test k:&:num [
+284   local-scope
+285   load-ingredients
+286   foo k
+287 ]
+288 # ..calling a recipe with an optional address ingredient
+289 def foo -> [
+290   local-scope
+291   load-ingredients
+292   k:&:num, found?:bool <- next-ingredient
+293   # we don't further check k for immutability, but assume it's mutable
+294 ]
+295 $error: 0
+296 
+297 :(scenario treat_optional_ingredients_as_mutable_2)
+298 % Hide_errors = true;
+299 def main [
+300   local-scope
+301   p:&:point <- new point:type
+302   foo p
+303 ]
+304 def foo p:&:point [
+305   local-scope
+306   load-ingredients
+307   bar p
+308 ]
+309 def bar [
+310   local-scope
+311   load-ingredients
+312   p:&:point <- next-ingredient  # optional ingredient; assumed to be mutable
+313 ]
+314 +error: foo: cannot modify 'p' in instruction 'bar p' because it's an ingredient of recipe foo but not also a product
+315 
+316 //: when checking for immutable ingredients, remember to take space into account
+317 :(scenario check_space_of_reagents_in_immutability_checks)
+318 def main [
+319   a:space <- new-closure
+320   b:&:num <- new number:type
+321   run-closure b:&:num, a:space
+322 ]
+323 def new-closure [
+324   new-default-space
+325   x:&:num <- new number:type
+326   return default-space
+327 ]
+328 def run-closure x:&:num, s:space [
+329   local-scope
+330   load-ingredients
+331   0:space/names:new-closure <- copy s
+332   # different space; always mutable
+333   *x:&:num/space:1 <- copy 34
+334 ]
+335 $error: 0
+336 
+337 :(before "End Transforms")
+338 Transform.push_back(check_immutable_ingredients);  // idempotent
+339 
+340 :(code)
+341 void check_immutable_ingredients(const recipe_ordinal r) {
+342   // to ensure an address reagent isn't modified, it suffices to show that
+343   //   a) we never write to its contents directly,
+344   //   b) we never call 'put' or 'put-index' on it, and
+345   //   c) any non-primitive recipe calls in the body aren't returning it as a product
+346   const recipe& caller = get(Recipe, r);
+347   trace(9991, "transform") << "--- check mutability of ingredients in recipe " << caller.name << end();
+348   if (!caller.has_header) return;  // skip check for old-style recipes calling next-ingredient directly
+349   for (int i = 0;  i < SIZE(caller.ingredients);  ++i) {
+350     const reagent& current_ingredient = caller.ingredients.at(i);
+351     if (is_present_in_products(caller, current_ingredient.name)) continue;  // not expected to be immutable
+352     // End Immutable Ingredients Special-cases
+353     set<reagent> immutable_vars;
+354     immutable_vars.insert(current_ingredient);
+355     for (int i = 0;  i < SIZE(caller.steps);  ++i) {
+356       const instruction& inst = caller.steps.at(i);
+357       check_immutable_ingredient_in_instruction(inst, immutable_vars, current_ingredient.name, caller);
+358       if (inst.operation == INDEX && SIZE(inst.ingredients) > 1 && inst.ingredients.at(1).name == current_ingredient.name) continue;
+359       update_aliases(inst, immutable_vars);
+360     }
+361   }
+362 }
+363 
+364 void update_aliases(const instruction& inst, set<reagent>& current_ingredient_and_aliases) {
+365   set<int> current_ingredient_indices = ingredient_indices(inst, current_ingredient_and_aliases);
+366   if (!contains_key(Recipe, inst.operation)) {
+367     // primitive recipe
+368     switch (inst.operation) {
+369       case COPY:
+370         for (set<int>::iterator p = current_ingredient_indices.begin();  p != current_ingredient_indices.end();  ++p)
+371           current_ingredient_and_aliases.insert(inst.products.at(*p).name);
+372         break;
+373       case GET:
+374       case INDEX:
+375       case MAYBE_CONVERT:
+376         // current_ingredient_indices can only have 0 or one value
+377         if (!current_ingredient_indices.empty() && !inst.products.empty()) {
+378           if (is_mu_address(inst.products.at(0)) || is_mu_container(inst.products.at(0)) || is_mu_exclusive_container(inst.products.at(0)))
+379             current_ingredient_and_aliases.insert(inst.products.at(0));
+380         }
+381         break;
+382       default: break;
+383     }
+384   }
+385   else {
+386     // defined recipe
+387     set<int> contained_in_product_indices = scan_contained_in_product_indices(inst, current_ingredient_indices);
+388     for (set<int>::iterator p = contained_in_product_indices.begin();  p != contained_in_product_indices.end();  ++p) {
+389       if (*p < SIZE(inst.products))
+390         current_ingredient_and_aliases.insert(inst.products.at(*p));
+391     }
+392   }
+393 }
+394 
+395 set<int> scan_contained_in_product_indices(const instruction& inst, set<int>& ingredient_indices) {
+396   set<reagent> selected_ingredients;
+397   const recipe& callee = get(Recipe, inst.operation);
+398   for (set<int>::iterator p = ingredient_indices.begin();  p != ingredient_indices.end();  ++p) {
+399     if (*p >= SIZE(callee.ingredients)) continue;  // optional immutable ingredient
+400     selected_ingredients.insert(callee.ingredients.at(*p));
+401   }
+402   set<int> result;
+403   for (int i = 0;  i < SIZE(callee.products);  ++i) {
+404     const reagent& current_product = callee.products.at(i);
+405     const string_tree* contained_in_name = property(current_product, "contained-in");
+406     if (contained_in_name && selected_ingredients.find(contained_in_name->value) != selected_ingredients.end())
+407       result.insert(i);
+408   }
+409   return result;
+410 }
+411 
+412 :(scenarios transform)
+413 :(scenario immutability_infects_contained_in_variables)
+414 % Hide_errors = true;
+415 container test-list [
+416   value:num
+417   next:&:test-list
+418 ]
+419 def main [
+420   local-scope
+421   p:&:test-list <- new test-list:type
+422   foo p
+423 ]
+424 def foo p:&:test-list [  # p is immutable
+425   local-scope
+426   load-ingredients
+427   p2:&:test-list <- test-next p  # p2 is immutable
+428   *p2 <- put *p2, value:offset, 34
+429 ]
+430 def test-next x:&:test-list -> y:&:test-list/contained-in:x [
+431   local-scope
+432   load-ingredients
+433   y <- get *x, next:offset
+434 ]
+435 +error: foo: cannot modify 'p2' in instruction '*p2 <- put *p2, value:offset, 34' because that would modify p which is an ingredient of recipe foo but not also a product
+436 
+437 :(code)
+438 void check_immutable_ingredient_in_instruction(const instruction& inst, const set<reagent>& current_ingredient_and_aliases, const string& original_ingredient_name, const recipe& caller) {
+439   // first check if the instruction is directly modifying something it shouldn't
+440   for (int i = 0;  i < SIZE(inst.products);  ++i) {
+441     if (has_property(inst.products.at(i), "lookup")
+442         && current_ingredient_and_aliases.find(inst.products.at(i)) != current_ingredient_and_aliases.end()) {
+443       string current_product_name = inst.products.at(i).name;
+444       if (current_product_name == original_ingredient_name)
+445         raise << maybe(caller.name) << "cannot modify '" << current_product_name << "' in instruction '" << inst.original_string << "' because it's an ingredient of recipe " << caller.name << " but not also a product\n" << end();
+446       else
+447         raise << maybe(caller.name) << "cannot modify '" << current_product_name << "' in instruction '" << inst.original_string << "' because that would modify " << original_ingredient_name << " which is an ingredient of recipe " << caller.name << " but not also a product\n" << end();
+448       return;
+449     }
+450   }
+451   // check if there's any indirect modification going on
+452   set<int> current_ingredient_indices = ingredient_indices(inst, current_ingredient_and_aliases);
+453   if (current_ingredient_indices.empty()) return;  // ingredient not found in call
+454   for (set<int>::iterator p = current_ingredient_indices.begin();  p != current_ingredient_indices.end();  ++p) {
+455     const int current_ingredient_index = *p;
+456     reagent current_ingredient = inst.ingredients.at(current_ingredient_index);
+457     canonize_type(current_ingredient);
+458     const string& current_ingredient_name = current_ingredient.name;
+459     if (!contains_key(Recipe, inst.operation)) {
+460       // primitive recipe
+461       // we got here only because we got an instruction with an implicit product, and the instruction didn't explicitly spell it out
+462       //    put x, y:offset, z
+463       // instead of
+464       //    x <- put x, y:offset, z
+465       if (inst.operation == PUT || inst.operation == PUT_INDEX) {
+466         if (current_ingredient_index == 0) {
+467           if (current_ingredient_name == original_ingredient_name)
+468             raise << maybe(caller.name) << "cannot modify '" << current_ingredient_name << "' in instruction '" << inst.original_string << "' because it's an ingredient of recipe " << caller.name << " but not also a product\n" << end();
+469           else
+470             raise << maybe(caller.name) << "cannot modify '" << current_ingredient_name << "' in instruction '" << inst.original_string << "' because that would modify '" << original_ingredient_name << "' which is an ingredient of recipe " << caller.name << " but not also a product\n" << end();
+471         }
+472       }
+473     }
+474     else {
+475       // defined recipe
+476       if (is_modified_in_recipe(inst.operation, current_ingredient_index, caller)) {
+477         if (current_ingredient_name == original_ingredient_name)
+478           raise << maybe(caller.name) << "cannot modify '" << current_ingredient_name << "' in instruction '" << inst.original_string << "' because it's an ingredient of recipe " << caller.name << " but not also a product\n" << end();
+479         else
+480           raise << maybe(caller.name) << "cannot modify '" << current_ingredient_name << "' in instruction '" << inst.original_string << "' because that would modify '" << original_ingredient_name << "' which is an ingredient of recipe " << caller.name << " but not also a product\n" << end();
+481       }
+482     }
+483   }
+484 }
+485 
+486 bool is_modified_in_recipe(const recipe_ordinal r, const int ingredient_index, const recipe& caller) {
+487   const recipe& callee = get(Recipe, r);
+488   if (!callee.has_header) {
+489     raise << maybe(caller.name) << "can't check mutability of ingredients in recipe " << callee.name << " because it uses 'next-ingredient' directly, rather than a recipe header.\n" << end();
+490     return true;
+491   }
+492   if (ingredient_index >= SIZE(callee.ingredients)) return false;  // optional immutable ingredient
+493   return is_present_in_products(callee, callee.ingredients.at(ingredient_index).name);
+494 }
+495 
+496 bool is_present_in_products(const recipe& callee, const string& ingredient_name) {
+497   for (int i = 0;  i < SIZE(callee.products);  ++i) {
+498     if (callee.products.at(i).name == ingredient_name)
+499       return true;
+500   }
+501   return false;
+502 }
+503 
+504 set<int> ingredient_indices(const instruction& inst, const set<reagent>& ingredient_names) {
+505   set<int> result;
+506   for (int i = 0;  i < SIZE(inst.ingredients);  ++i) {
+507     if (is_literal(inst.ingredients.at(i))) continue;
+508     if (ingredient_names.find(inst.ingredients.at(i)) != ingredient_names.end())
+509       result.insert(i);
+510   }
+511   return result;
+512 }
+513 
+514 //: Sometimes you want to pass in two addresses, one pointing inside the
+515 //: other. For example, you want to delete a node from a linked list. You
+516 //: can't pass both pointers back out, because if a caller tries to make both
+517 //: identical then you can't tell which value will be written on the way out.
+518 //:
+519 //: Experimental solution: just tell Mu that one points inside the other.
+520 //: This way we can return just one pointer as high up as necessary to capture
+521 //: all modifications performed by a recipe.
+522 //:
+523 //: We'll see if we end up wanting to abuse /contained-in for other reasons.
+524 
+525 :(scenarios transform)
+526 :(scenario can_modify_contained_in_addresses)
+527 container test-list [
+528   value:num
+529   next:&:test-list
+530 ]
+531 def main [
+532   local-scope
+533   p:&:test-list <- new test-list:type
+534   foo p
+535 ]
+536 def foo p:&:test-list -> p:&:test-list [
+537   local-scope
+538   load-ingredients
+539   p2:&:test-list <- test-next p
+540   p <- test-remove p2, p
+541 ]
+542 def test-next x:&:test-list -> y:&:test-list [
+543   local-scope
+544   load-ingredients
+545   y <- get *x, next:offset
+546 ]
+547 def test-remove x:&:test-list/contained-in:from, from:&:test-list -> from:&:test-list [
+548   local-scope
+549   load-ingredients
+550   *x <- put *x, value:offset, 34  # can modify x
+551 ]
+552 $error: 0
+553 
+554 :(before "End Immutable Ingredients Special-cases")
+555 if (has_property(current_ingredient, "contained-in")) {
+556   const string_tree* tmp = property(current_ingredient, "contained-in");
+557   if (!tmp->atom
+558       || (!is_present_in_ingredients(caller, tmp->value)
+559           && !is_present_in_products(caller, tmp->value))) {
+560     raise << maybe(caller.name) << "/contained-in can only point to another ingredient or product, but got '" << to_string(property(current_ingredient, "contained-in")) << "'\n" << end();
+561   }
+562   continue;
+563 }
+564 
+565 :(scenario contained_in_check)
+566 container test-list [
+567   value:num
+568   next:&:test-list
+569 ]
+570 def test-remove x:&:test-list/contained-in:result, from:&:test-list -> result:&:test-list [
+571   local-scope
+572   load-ingredients
+573   result <- copy 0
+574 ]
+575 $error: 0
-- cgit 1.4.1-2-gfad0