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   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, 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