057immutable.cc.html « html - mu - Soul of a tiny new machine. More thorough tests → More comprehensible and rewrite-friendly software → More resilient society.

blob: 4d3b51fcda3d19ae39ecdba7e8f15aede1a5138b (plain) (tree)

2f02189d ^

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
pre { line-height: 125%; }
td.linenos .normal { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
span.linenos { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
td.linenos .special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
span.linenos.special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
.highlight .hll { background-color: #ffffcc }
.highlight .c { color: #888888 } /* Comment */
.highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */
.highlight .k { color: #008800; font-weight: bold } /* Keyword */
.highlight .ch { color: #888888 } /* Comment.Hashbang */
.highlight .cm { color: #888888 } /* Comment.Multiline */
.highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */
.highlight .cpf { color: #888888 } /* Comment.PreprocFile */
.highlight .c1 { color: #888888 } /* Comment.Single */
.highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */
.highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .ges { font-weight: bold; font-style: italic } /* Generic.EmphStrong */
.highlight .gr { color: #aa0000 } /* Generic.Error */
.highlight .gh { color: #333333 } /* Generic.Heading */
.highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */
.highlight .go { color: #888888 } /* Generic.Output */
.highlight .gp { color: #555555 } /* Generic.Prompt */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #666666 } /* Generic.Subheading */
.highlight .gt { color: #aa0000 } /* Generic.Traceback */
.highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */
.highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */
.highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */
.highlight .kp { color: #008800 } /* Keyword.Pseudo */
.highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */
.highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */
.highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */
.highlight .s { color: #dd2200; background-color: #fff0f0 } /* Literal.String */
.highlight .na { color: #336699 } /* Name.Attribute */
.highlight .nb { color: #003388 } /* Name.Builtin */
.highlight .nc { color: #bb0066; font-weight: bold } /* Name.Class */
.highlight .no { color: #003366; font-weight: bold } /* Name.Constant */
.highlight .nd { color: #555555 } /* Name.Decorator */
.highlight .ne { color: #bb0066; font-weight: bold } /* Name.Exception */
.highlight .nf { color: #0066bb; font-weight: bold } /* Name.Function */
.highlight .nl { color: #336699; font-style: italic } /* Name.Label */
.highlight .nn { color: #bb0066; font-weight: bold } /* Name.Namespace */
.highlight .py { color: #336699; font-weight: bold } /* Name.Property */
.highlight .nt { color: #bb0066; font-weight: bold } /* Name.Tag */
.highlight .nv { color: #336699 } /* Name.Variable */
.highlight .ow { color: #008800 } /* Operator.Word */
.highlight .w { color: #bbbbbb } /* Text.Whitespace */
.highlight .mb { color: #0000DD; font-weight: bold } /* Literal.Number.Bin */
.highlight .mf { color: #0000DD; font-weight: bold } /* Literal.Number.Float */
.highlight .mh { color: #0000DD; font-weight: bold } /* Literal.Number.Hex */
.highlight .mi { color: #0000DD; font-weight: bold } /* Literal.Number.Integer */
.highlight .mo { color: #0000DD; font-weight: bold } /* Literal.Number.Oct */
.highlight .sa { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Affix */
.highlight .sb { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Backtick */
.highlight .sc { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Char */
.highlight .dl { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Delimiter */
.highlight .sd { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Doc */
.highlight .s2 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Double */
.highlight .se { color: #0044dd; background-color: #fff0f0 } /* Literal.String.Escape */
.highlight .sh { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Heredoc */
.highlight .si { color: #3333bb; background-color: #fff0f0 } /* Literal.String.Interpol */
.highlight .sx { color: #22bb22; background-color: #f0fff0 } /* Literal.String.Other */
.highlight .sr { color: #008800; background-color: #fff0ff } /* Literal.String.Regex */
.highlight .s1 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Single */
.highlight .ss { color: #aa6600; background-color: #fff0f0 } /* Literal.String.Symbol */
.highlight .bp { color: #003388 } /* Name.Builtin.Pseudo */
.highlight .fm { color: #0066bb; font-weight: bold } /* Name.Function.Magic */
.highlight .vc { color: #336699 } /* Name.Variable.Class */
.highlight .vg { color: #dd7700 } /* Name.Variable.Global */
.highlight .vi { color: #3333bb } /* Name.Variable.Instance */
.highlight .vm { color: #336699 } /* Name.Variable.Magic */
.highlight .il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */#!/bin/sh
# Run this before running './mu edit' or './mu sandbox' to make sure you don't
# lose any work.
#
# You'll be editing code in lesson/recipes.mu, and any sandboxes you create
# will be in lesson/0, lesson/1, etc., from top to bottom.

set -e

mkdir lesson
cd lesson
git init
echo '**/.*.swp' > .gitignore
git add .
git commit -m 0

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"> <html> <head> <meta http-equiv="content-type" content="text/html; charset=UTF-8"> <title>Mu - 057immutable.cc</title> <meta name="Generator" content="Vim/7.4"> <meta name="plugin-version" content="vim7.4_v2"> <meta name="syntax" content="cpp"> <meta name="settings" content="use_css,pre_wrap,no_foldcolumn,expand_tabs,prevent_copy="> <meta name="colorscheme" content="minimal"> <style type="text/css">  </style> <script type='text/javascript'>  </script> </head> <body> <pre id='vimCodeElement'> //: 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. :(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:address:point <- new point:type p <- foo p ] # mutable address to container def foo p:address:point -> p:address: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:address:array:number <- new number:type, 3 p <- foo p ] # mutable address def foo p:address:array:number -> p:address:array:number [ local-scope load-ingredients *p <- put-index *p, 0, 34 ] $error: 0 :(scenario ignore_literal_ingredients_for_immutability_checks) def main [ local-scope p:address:d1 <- new d1:type q:number <- foo p ] def foo p:address:d1 -> q:number [ local-scope load-ingredients x:address:d1 <- new d1:type *x <- put *x, p:offset, 34 # ignore this 'p' reply 36 ] container d1 [ p:number q:number ] $error: 0 :(scenario cannot_modify_immutable_ingredients) % Hide_errors = true; def main [ local-scope x:address:number <- new number:type foo x ] # immutable address to primitive def foo x:address:number [ 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:address:number <- new number:type foo x ] def foo x:address:number [ 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:address:number <- new number:type foo x ] def foo x:address:number [ 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:address:point <- new point:type foo p ] def foo p:address:point [ local-scope load-ingredients bar p ] def bar p:address:point -> p:address: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:address:point <- new point:type foo p ] def foo p:address:point [ local-scope load-ingredients q:address: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:address:point <- new point:type foo p ] def foo p:address:point -> p:address:point [ local-scope load-ingredients q:address:point <- copy p *q <- put *q, x:offset, 34 ] $error: 0 :(scenario cannot_modify_address_inside_immutable_ingredients) % Hide_errors = true; container foo [ x:address:array:number # contains an address ] def main [ # don't run anything ] def foo a:address:foo [ local-scope load-ingredients x:address:array:number <- 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:address:array:number # contains an address ] def main [ # don't run anything ] def foo a:address:foo [ local-scope load-ingredients b:foo <- merge 0 # modify b, completely unrelated to immutable ingredient a x:address:array:number <- get b, x:offset *x <- put-index *x, 0, 34 ] $error: 0 :(scenario cannot_modify_address_inside_immutable_ingredients_3) % Hide_errors = true; container foo [ x:number ] def main [ # don't run anything ] def foo a:address:array:address:number [ local-scope load-ingredients x:address:number <- 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) container foo [ x:address:array:number # contains an address ] def main [ # don't run anything ] def foo a:address:array:address:number [ local-scope load-ingredients b:address:array:address:number <- new {(address number): type}, 3 # modify b, completely unrelated to immutable ingredient a x:address:number <- index *b, 0 *x <- copy 34 ] $error: 0 :(scenario can_traverse_immutable_ingredients) container test-list [ next:address:test-list ] def main [ local-scope p:address:test-list <- new test-list:type foo p ] def foo p:address:test-list [ local-scope load-ingredients p2:address:test-list <- bar p ] def bar x:address:test-list -> y:address:test-list [ local-scope load-ingredients y <- get *x, next:offset ] $error: 0 :(scenario treat_optional_ingredients_as_mutable) def main [ k:address:number <- new number:type test k ] # recipe taking an immutable address ingredient def test k:address:number [ local-scope load-ingredients foo k ] # ..calling a recipe with an optional address ingredient def foo -> [ local-scope load-ingredients k:address:number, found?:boolean <- 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:address:point <- new point:type foo p ] def foo p:address:point [ local-scope load-ingredients bar p ] def bar [ local-scope load-ingredients p:address: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:address:array:location <- new-closure b:address:number <- new number:type run-closure b:address:number, a:address:array:location ] def new-closure [ new-default-space x:address:number <- new number:type return default-space ] def run-closure x:address:number, s:address:array:location [ local-scope load-ingredients 0:address:array:location/names:new-closure <- copy s # different space; always mutable *x:address:number/space:1 <- copy 34 ] $error: 0 :(before "End Transforms") Transform.push_back(check_immutable_ingredients); // idempotent :(code) void check_immutable_ingredients(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); 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()) { 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); // TODO 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:number next:address:test-list ] def main [ local-scope p:address:test-list <- new test-list:type foo p ] def foo p:address:test-list [ # p is immutable local-scope load-ingredients p2:address:test-list <- test-next p # p2 is immutable *p2 <- put *p2, value:offset, 34 ] def test-next x:address:test-list -> y:address: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 '" << to_original_string(inst) << "' 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 '" << to_original_string(inst) << "' 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 '" << to_original_string(inst) << "' 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 '" << to_original_string(inst) << "' 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 '" << to_original_string(inst) << "' 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 '" << to_original_string(inst) << "' 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(recipe_ordinal r, 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; } bool is_present_in_ingredients(const recipe& callee, const string& ingredient_name) { for (int i = 0; i < SIZE(callee.ingredients); ++i) { if (callee.ingredients.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:number next:address:test-list ] def main [ local-scope p:address:test-list <- new test-list:type foo p ] def 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 ] def test-next x:address:test-list -> y:address:test-list [ local-scope load-ingredients y <- get *x, next:offset ] def test-remove x:address:test-list/contained-in:from, from:address:test-list -> from:address: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->left || tmp->right || !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+product, but got '" << to_string(property(current_ingredient, "contained-in")) << "'\n" << end(); continue; } </pre> </body> </html>