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/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> 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 '" << 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