From 059def11cb8c53d85f7eed2af98a0bca0120a9cc Mon Sep 17 00:00:00 2001 From: Kartik Agaram Date: Sat, 12 May 2018 23:08:39 -0700 Subject: 4244 --- html/057immutable.cc.html | 390 ++++++++++++++++++++++++---------------------- 1 file changed, 208 insertions(+), 182 deletions(-) (limited to 'html/057immutable.cc.html') diff --git a/html/057immutable.cc.html b/html/057immutable.cc.html index 9fe98f1e..f0ea4e20 100644 --- a/html/057immutable.cc.html +++ b/html/057immutable.cc.html @@ -411,13 +411,13 @@ if ('onhashchange' in window) { 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 +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); +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 } @@ -425,7 +425,7 @@ if ('onhashchange' in window) { 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); +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) { @@ -455,10 +455,10 @@ if ('onhashchange' in window) { 392 } 393 } 394 -395 set<int> scan_contained_in_product_indices(const instruction& inst, set<int>& ingredient_indices) { +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) { +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 } @@ -472,183 +472,209 @@ if ('onhashchange' in window) { 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 '" << to_original_string(inst) << "' 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 '" << 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(); -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 '" << to_original_string(inst) << "' 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 '" << 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(); -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 '" << to_original_string(inst) << "' 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 '" << 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(); -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_product) -566 container test-list [ -567 value:num -568 next:&:test-list -569 ] -570 def foo x:&:test-list/contained-in:result -> result:&:test-list [ -571 local-scope -572 load-ingredients -573 result <- copy 0 -574 ] -575 $error: 0 -576 -577 :(scenario contained_in_is_mutable) -578 container test-list [ -579 value:num -580 next:&:test-list -581 ] -582 def foo x:&:test-list/contained-in:result -> result:&:test-list [ -583 local-scope -584 load-ingredients -585 result <- copy x -586 put *x, value:offset, 34 -587 ] -588 $error: 0 +412 bool is_mu_container(const reagent& r) { +413 return is_mu_container(r.type); +414 } +415 bool is_mu_container(const type_tree* type) { +416 if (!type) return false; +417 if (!type->atom) +418 return is_mu_container(get_base_type(type)); +419 if (type->value == 0) return false; +420 if (!contains_key(Type, type->value)) return false; // error raised elsewhere +421 type_info& info = get(Type, type->value); +422 return info.kind == CONTAINER; +423 } +424 +425 bool is_mu_exclusive_container(const reagent& r) { +426 return is_mu_exclusive_container(r.type); +427 } +428 bool is_mu_exclusive_container(const type_tree* type) { +429 if (!type) return false; +430 if (!type->atom) +431 return is_mu_exclusive_container(get_base_type(type)); +432 if (type->value == 0) return false; +433 if (!contains_key(Type, type->value)) return false; // error raised elsewhere +434 type_info& info = get(Type, type->value); +435 return info.kind == EXCLUSIVE_CONTAINER; +436 } +437 +438 :(scenarios transform) +439 :(scenario immutability_infects_contained_in_variables) +440 % Hide_errors = true; +441 container test-list [ +442 value:num +443 next:&:test-list +444 ] +445 def main [ +446 local-scope +447 p:&:test-list <- new test-list:type +448 foo p +449 ] +450 def foo p:&:test-list [ # p is immutable +451 local-scope +452 load-ingredients +453 p2:&:test-list <- test-next p # p2 is immutable +454 *p2 <- put *p2, value:offset, 34 +455 ] +456 def test-next x:&:test-list -> y:&:test-list/contained-in:x [ +457 local-scope +458 load-ingredients +459 y <- get *x, next:offset +460 ] +461 +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 +462 +463 :(code) +464 void check_immutable_ingredient_in_instruction(const instruction& inst, const set<reagent>& current_ingredient_and_aliases, const string& original_ingredient_name, const recipe& caller) { +465 // first check if the instruction is directly modifying something it shouldn't +466 for (int i = 0; i < SIZE(inst.products); ++i) { +467 if (has_property(inst.products.at(i), "lookup") +468 && current_ingredient_and_aliases.find(inst.products.at(i)) != current_ingredient_and_aliases.end()) { +469 string current_product_name = inst.products.at(i).name; +470 if (current_product_name == original_ingredient_name) +471 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(); +472 else +473 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(); +474 return; +475 } +476 } +477 // check if there's any indirect modification going on +478 set<int> current_ingredient_indices = ingredient_indices(inst, current_ingredient_and_aliases); +479 if (current_ingredient_indices.empty()) return; // ingredient not found in call +480 for (set<int>::iterator p = current_ingredient_indices.begin(); p != current_ingredient_indices.end(); ++p) { +481 const int current_ingredient_index = *p; +482 reagent current_ingredient = inst.ingredients.at(current_ingredient_index); +483 canonize_type(current_ingredient); +484 const string& current_ingredient_name = current_ingredient.name; +485 if (!contains_key(Recipe, inst.operation)) { +486 // primitive recipe +487 // we got here only because we got an instruction with an implicit product, and the instruction didn't explicitly spell it out +488 // put x, y:offset, z +489 // instead of +490 // x <- put x, y:offset, z +491 if (inst.operation == PUT || inst.operation == PUT_INDEX) { +492 if (current_ingredient_index == 0) { +493 if (current_ingredient_name == original_ingredient_name) +494 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(); +495 else +496 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(); +497 } +498 } +499 } +500 else { +501 // defined recipe +502 if (is_modified_in_recipe(inst.operation, current_ingredient_index, caller)) { +503 if (current_ingredient_name == original_ingredient_name) +504 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(); +505 else +506 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(); +507 } +508 } +509 } +510 } +511 +512 bool is_modified_in_recipe(const recipe_ordinal r, const int ingredient_index, const recipe& caller) { +513 const recipe& callee = get(Recipe, r); +514 if (!callee.has_header) { +515 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(); +516 return true; +517 } +518 if (ingredient_index >= SIZE(callee.ingredients)) return false; // optional immutable ingredient +519 return is_present_in_products(callee, callee.ingredients.at(ingredient_index).name); +520 } +521 +522 bool is_present_in_products(const recipe& callee, const string& ingredient_name) { +523 for (int i = 0; i < SIZE(callee.products); ++i) { +524 if (callee.products.at(i).name == ingredient_name) +525 return true; +526 } +527 return false; +528 } +529 +530 set<int> ingredient_indices(const instruction& inst, const set<reagent>& ingredient_names) { +531 set<int> result; +532 for (int i = 0; i < SIZE(inst.ingredients); ++i) { +533 if (is_literal(inst.ingredients.at(i))) continue; +534 if (ingredient_names.find(inst.ingredients.at(i)) != ingredient_names.end()) +535 result.insert(i); +536 } +537 return result; +538 } +539 +540 //: Sometimes you want to pass in two addresses, one pointing inside the +541 //: other. For example, you want to delete a node from a linked list. You +542 //: can't pass both pointers back out, because if a caller tries to make both +543 //: identical then you can't tell which value will be written on the way out. +544 //: +545 //: Experimental solution: just tell Mu that one points inside the other. +546 //: This way we can return just one pointer as high up as necessary to capture +547 //: all modifications performed by a recipe. +548 //: +549 //: We'll see if we end up wanting to abuse /contained-in for other reasons. +550 +551 :(scenarios transform) +552 :(scenario can_modify_contained_in_addresses) +553 container test-list [ +554 value:num +555 next:&:test-list +556 ] +557 def main [ +558 local-scope +559 p:&:test-list <- new test-list:type +560 foo p +561 ] +562 def foo p:&:test-list -> p:&:test-list [ +563 local-scope +564 load-ingredients +565 p2:&:test-list <- test-next p +566 p <- test-remove p2, p +567 ] +568 def test-next x:&:test-list -> y:&:test-list [ +569 local-scope +570 load-ingredients +571 y <- get *x, next:offset +572 ] +573 def test-remove x:&:test-list/contained-in:from, from:&:test-list -> from:&:test-list [ +574 local-scope +575 load-ingredients +576 *x <- put *x, value:offset, 34 # can modify x +577 ] +578 $error: 0 +579 +580 :(before "End Immutable Ingredients Special-cases") +581 if (has_property(current_ingredient, "contained-in")) { +582 const string_tree* tmp = property(current_ingredient, "contained-in"); +583 if (!tmp->atom +584 || (!is_present_in_ingredients(caller, tmp->value) +585 && !is_present_in_products(caller, tmp->value))) { +586 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(); +587 } +588 continue; +589 } +590 +591 :(scenario contained_in_product) +592 container test-list [ +593 value:num +594 next:&:test-list +595 ] +596 def foo x:&:test-list/contained-in:result -> result:&:test-list [ +597 local-scope +598 load-ingredients +599 result <- copy 0 +600 ] +601 $error: 0 +602 +603 :(scenario contained_in_is_mutable) +604 container test-list [ +605 value:num +606 next:&:test-list +607 ] +608 def foo x:&:test-list/contained-in:result -> result:&:test-list [ +609 local-scope +610 load-ingredients +611 result <- copy x +612 put *x, value:offset, 34 +613 ] +614 $error: 0 -- cgit 1.4.1-2-gfad0