diff options
| -rw-r--r-- | 060immutable.cc | 211 | ||||
| -rw-r--r-- | 073list.mu | 1 | ||||
| -rw-r--r-- | 075duplex_list.mu | 93 |
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 |