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< class="p">>
<span id="L20" class="LineNr"> 20 </span><span class="Delimiter">:(before &quot;End Primitive Recipe Checks&quot;)</span>
<span id="L21" class="LineNr"> 21 </span><span class="Normal">case</span> CREATE_ARRAY: <span class="Delimiter">{</span>
<span id="L22" class="LineNr"> 22 </span>  <span class="Normal">if</span> <span class="Delimiter">(</span>inst<span class="Delimiter">.</span>products<span class="Delimiter">.</span>empty<span class="Delimiter">())</span> <span class="Delimiter">{</span>
<span id="L23" class="LineNr"> 23 </span>  <span class="Conceal">¦</span> <a href='003trace.cc.html#L174'>raise</a> &lt;&lt; <a href='013update_operation.cc.html#L25'>maybe</a><span class="Delimiter">(</span>get<span class="Delimiter">(</span>Recipe<span class="Delimiter">,</span> r<span class="Delimiter">).</span>name<span class="Delimiter">)</span> &lt;&lt; <span class="Constant">&quot;'create-array' needs one product and no ingredients but got '&quot;</span> &lt;&lt; to_original_string<span class="Delimiter">(</span>inst<span class="Delimiter">)</span> &lt;&lt; <span class="cSpecial">'\n'</span> &lt;&lt; end<span class="Delimiter">();</span>
<span id="L24" class="LineNr"> 24 </span>  <span class="Conceal">¦</span> <span class="Identifier">break</span><span class="Delimiter">;</span>
<span id="L25" class="LineNr"> 25 </span>  <span class="Delimiter">}</span>
<span id="L26" class="LineNr"> 26 </span>  reagent<span class="Comment">/*</span><span class="Comment">copy</span><span class="Comment">*/</span> product = inst<span class="Delimiter">.</span>products<span class="Delimiter">.</span>at<span class="Delimiter">(</span><span class="Constant">0</span><span class="Delimiter">);</span>
<span id="L27" class="LineNr"> 27 </span>  <span class="Comment">// Update CREATE_ARRAY product in Check</span>
<span id="L28" class="LineNr"> 28 </span>  <span class="Normal">if</span> <span class="Delimiter">(</span>!is_mu_array<span class="Delimiter">(</span>product<span class="Delimiter">))</span> <span class="Delimiter">{</span>
<span id="L29" class="LineNr"> 29 </span>  <span class="Conceal">¦</span> <a href='003trace.cc.html#L174'>raise</a> &lt;&lt; <a href='013update_operation.cc.html#L25'>maybe</a><span class="Delimiter">(</span>get<span class="Delimiter">(</span>Recipe<span class="Delimiter">,</span> r<span class="Delimiter">).</span>name<span class="Delimiter">)</span> &lt;&lt; <span class="Constant">&quot;'create-array' cannot create non-array '&quot;</span> &lt;&lt; product<span class="Delimiter">.</span>original_string &lt;&lt; <span class="Constant">&quot;'</span><span class="cSpecial">\n</span><span class="Constant">&quot;</span> &lt;&lt; <a href='003trace.cc.html#L203'>end</a><span class="Delimiter">();</span>
<span id="L30" class="LineNr"> 30 </span>  <span class="Conceal">¦</span> <span class="Identifier">break</span><span class="Delimiter">;</span>
<span id="L31" class="LineNr"> 31 </span>  <span class="Delimiter">}</span>
<span id="L32" class="LineNr"> 32 </span>  <span class="Normal">if</span> <span class="Delimiter">(</span>!product<span class="Delimiter">.</span>type<span class="Delimiter">-&gt;</span>right<span class="Delimiter">)</span> <span class="Delimiter">{</span>
<span id="L33" class="LineNr"> 33 </span>  <span class="Conceal">¦</span> <a href='003trace.cc.html#L174'>raise</a> &lt;&lt; <a href='013update_operation.cc.html#L25'>maybe</a><span class="Delimiter">(</span>get<span class="Delimiter">(</span>Recipe<span class="Delimiter">,</span> r<span class="Delimiter">).</span>name<span class="Delimiter">)</span> &lt;&lt; <span class="Constant">&quot;create array of what? '&quot;</span> &lt;&lt; to_original_string<span class="Delimiter">(</span>inst<span class="Delimiter">)</span> &lt;&lt; <span class="Constant">&quot;'</span><span class="cSpecial">\n</span><span class="Constant">&quot;</span> &lt;&lt; <a href='003trace.cc.html#L203'>end</a><span class="Delimiter">();</span>
<span id="L34" class="LineNr"> 34 </span>  <span class="Conceal">¦</span> <span class="Identifier">break</span><span class="Delimiter">;</span>
<span id="L35" class="LineNr"> 35 </span>  <span class="Delimiter">}</span>
<span id="L36" class="LineNr"> 36 </span>  <span class="Comment">// 'create-array' will need to check properties rather than types</span>
<span id="L37" class="LineNr"> 37