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 null
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 null
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 <
lt;- 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/names:new-closure <- new-closure 320 b:&:num <- new number:type 321 run-closure b:&:num, a:space 322 ] 323 def new-closure [ 324 local-scope 325 x:&:num <- new number:type 326 return default-space/names:new-closure 327 ] 328 def run-closure x:&:num, s:space/names:new-closure [ 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, name_and_space_lt> 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, name_and_space_lt>& 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, name_and_space_lt> 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 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 :(before "End Types") 439 // reagent comparison -- only in the context of a single recipe 440 struct name_and_space_lt { 441 bool operator()(const reagent& a, const reagent& b) const; 442 }; 443 :(code) 444 bool name_and_space_lt::operator()(const reagent& a, const reagent& b) const { 445 int aspace = 0, bspace = 0; 446 if (has_property(a, "space")) aspace = to_integer(property(a, "space")->value); 447 if (has_property(b, "space")) bspace = to_integer(property(b, "space")->value); 448 if (aspace != bspace) return aspace < bspace; 449 return a.name < b.name; 450 } 451 452 :(scenarios transform) 453 :(scenario immutability_infects_contained_in_variables) 454 % Hide_errors = true; 455 container test-list [ 456 value:num 457 next:&:test-list 458 ] 459 def main [ 460 local-scope 461 p:&:test-list <- new test-list:type 462 foo p 463 ] 464 def foo p:&:test-list [ # p is immutable 465 local-scope 466 load-ingredients 467 p2:&:test-list <- test-next p # p2 is immutable 468 *p2 <- put *p2, value:offset, 34 469 ] 470 def test-next x:&:test-list -> y:&:test-list/contained-in:x [ 471 local-scope 472 load-ingredients 473 y <- get *x, next:offset 474 ] 475 +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 476 477 :(code) 478 void check_immutable_ingredient_in_instruction(const instruction& inst, const set<reagent, name_and_space_lt>& current_ingredient_and_aliases, const string& original_ingredient_name, const recipe& caller) { 479 // first check if the instruction is directly modifying something it shouldn't 480 for (int i = 0; i < SIZE(inst.products); ++i) { 481 if (has_property(inst.products.at(i), "lookup") 482 && current_ingredient_and_aliases.find(inst.products.at(i)) != current_ingredient_and_aliases.end()) { 483 string current_product_name = inst.products.at(i).name; 484 if (current_product_name == original_ingredient_name) 485 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(); 486 else 487 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(); 488 return; 489 } 490 } 491 // check if there's any indirect modification going on 492 set<int> current_ingredient_indices = ingredient_indices(inst, current_ingredient_and_aliases); 493 if (current_ingredient_indices.empty()) return; // ingredient not found in call 494 for (set<int>::iterator p = current_ingredient_indices.begin(); p != current_ingredient_indices.end(); ++p) { 495 const int current_ingredient_index = *p; 496 reagent current_ingredient = inst.ingredients.at(current_ingredient_index); 497 canonize_type(current_ingredient); 498 const string& current_ingredient_name = current_ingredient.name; 499 if (!contains_key(Recipe, inst.operation)) { 500 // primitive recipe 501 // we got here only because we got an instruction with an implicit product, and the instruction didn't explicitly spell it out 502 // put x, y:offset, z 503 // instead of 504 // x <- put x, y:offset, z 505 if (inst.operation == PUT || inst.operation == PUT_INDEX) { 506 if (current_ingredient_index == 0) { 507 if (current_ingredient_name == original_ingredient_name) 508 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(); 509 else 510 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(); 511 } 512 } 513 } 514 else { 515 // defined recipe 516 if (is_modified_in_recipe(inst.operation, current_ingredient_index, caller)) { 517 if (current_ingredient_name == original_ingredient_name) 518 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(); 519 else 520 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(); 521 } 522 } 523 } 524 } 525 526 bool is_modified_in_recipe(const recipe_ordinal r, const int ingredient_index, const recipe& caller) { 527 const recipe& callee = get(Recipe, r); 528 if (!callee.has_header) { 529 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(); 530 return true; 531 } 532 if (ingredient_index >= SIZE(callee.ingredients)) return false; // optional immutable ingredient 533 return is_present_in_products(callee, callee.ingredients.at(ingredient_index).name); 534 } 535 536 bool is_present_in_products(const recipe& callee, const string& ingredient_name) { 537 for (int i = 0; i < SIZE(callee.products); ++i) { 538 if (callee.products.at(i).name == ingredient_name) 539 return true; 540 } 541 return false; 542 } 543 544 set<int> ingredient_indices(const instruction& inst, const set<reagent, name_and_space_lt>& ingredient_names) { 545 set<int> result; 546 for (int i = 0; i < SIZE(inst.ingredients); ++i) { 547 if (is_literal(inst.ingredients.at(i))) continue; 548 if (ingredient_names.find(inst.ingredients.at(i)) != ingredient_names.end()) 549 result.insert(i); 550 } 551 return result; 552 } 553 554 //: Sometimes you want to pass in two addresses, one pointing inside the 555 //: other. For example, you want to delete a node from a linked list. You 556 //: can't pass both pointers back out, because if a caller tries to make both 557 //: identical then you can't tell which value will be written on the way out. 558 //: 559 //: Experimental solution: just tell Mu that one points inside the other. 560 //: This way we can return just one pointer as high up as necessary to capture 561 //: all modifications performed by a recipe. 562 //: 563 //: We'll see if we end up wanting to abuse /contained-in for other reasons. 564 565 :(scenarios transform) 566 :(scenario can_modify_contained_in_addresses) 567 container test-list [ 568 value:num 569 next:&:test-list 570 ] 571 def main [ 572 local-scope 573 p:&:test-list <- new test-list:type 574 foo p 575 ] 576 def foo p:&:test-list -> p:&:test-list [ 577 local-scope 578 load-ingredients 579 p2:&:test-list <- test-next p 580 p <- test-remove p2, p 581 ] 582 def test-next x:&:test-list -> y:&:test-list [ 583 local-scope 584 load-ingredients 585 y <- get *x, next:offset 586 ] 587 def test-remove x:&:test-list/contained-in:from, from:&:test-list -> from:&:test-list [ 588 local-scope 589 load-ingredients 590 *x <- put *x, value:offset, 34 # can modify x 591 ] 592 $error: 0 593 594 :(before "End Immutable Ingredients Special-cases") 595 if (has_property(current_ingredient, "contained-in")) { 596 const string_tree* tmp = property(current_ingredient, "contained-in"); 597 if (!tmp->atom 598 || (!is_present_in_ingredients(caller, tmp->value) 599 && !is_present_in_products(caller, tmp->value))) { 600 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(); 601 } 602 continue; 603 } 604 605 :(scenario contained_in_product) 606 container test-list [ 607 value:num 608 next:&:test-list 609 ] 610 def foo x:&:test-list/contained-in:result -> result:&:test-list [ 611 local-scope 612 load-ingredients 613 result <- copy null 614 ] 615 $error: 0 616 617 :(scenario contained_in_is_mutable) 618 container test-list [ 619 value:num 620 next:&:test-list 621 ] 622 def foo x:&:test-list/contained-in:result -> result:&:test-list [ 623 local-scope 624 load-ingredients 625 result <- copy x 626 put *x, value:offset, 34 627 ] 628 $error: 0