1 //: Spaces help isolate recipes from each other. You can create them at will,
  2 //: and all addresses in arguments are implicitly based on the 'default-space'
  3 //: (unless they have the /raw property)
  4 //:
  5 //: Spaces are often called 'scopes' in other languages. Stack frames are a
  6 //: limited form of space that can't outlive callers.
  7 //:
  8 //: Warning: messing with 'default-space' can corrupt memory. Don't do things
  9 //: like initialize default-space with some other function's default-space.
 10 //: Later we'll see how to chain spaces safely.
 11 
 12 //: Under the hood, a space is an array of locations in memory.
 13 :(before "End Mu Types Initialization")
 14 put(Type_abbreviations, "space", new_type_tree("address:array:location"));
 15 
 16 :(scenario set_default_space)
 17 # if default-space is 10, and if an array of 5 locals lies from location 12 to 16 (inclusive),
 18 # then local 0 is really location 12, local 1 is really location 13, and so on.
 19 def main [
 20   # pretend address:array:location; in practice we'll use 'new'
 21   10:num <- copy 0  # refcount
 22   11:num <- copy 5  # length
 23   default-space:space <- copy 10/unsafe
 24   1:num <- copy 23
 25 ]
 26 +mem: storing 23 in location 13
 27 
 28 :(scenario lookup_sidesteps_default_space)
 29 def main [
 30   # pretend pointer from outside (2000 reserved for refcount)
 31   2001:num <- copy 34
 32   # pretend address:array:location; in practice we'll use 'new'
 33   1000:num <- copy 0  # refcount
 34   1001:num <- copy 5  # length
 35   # actual start of this recipe
 36   default-space:space <- copy 1000/unsafe
 37   1:&:num <- copy 2000/unsafe  # even local variables always contain raw addresses
 38   8:num/raw <- copy *1:&:num
 39 ]
 40 +mem: storing 34 in location 8
 41 
 42 //: precondition: disable name conversion for 'default-space'
 43 
 44 :(scenario convert_names_passes_default_space)
 45 % Hide_errors = true;
 46 def main [
 47   default-space:num, x:num <- copy 0, 1
 48 ]
 49 +name: assign x 1
 50 -name: assign default-space 1
 51 
 52 :(before "End is_disqualified Special-cases")
 53 if (x.name == "default-space")
 54   x.initialized = true;
 55 :(before "End is_special_name Special-cases")
 56 if (s == "default-space") return true;
 57 
 58 //: core implementation
 59 
 60 :(before "End call Fields")
 61 int default_space;
 62 :(before "End call Constructor")
 63 default_space = 0;
 64 
 65 :(before "Begin canonize(x) Lookups")
 66 absolutize(x);
 67 :(code)
 68 void absolutize(reagent& x) {
 69   if (is_raw(x) || is_dummy(x)) return;
 70   if (x.name == "default-space") return;
 71   if (!x.initialized)
 72   ¦ raise << to_original_string(current_instruction()) << ": reagent not initialized: '" << x.original_string << "'\n" << end();
 73   x.set_value(address(x.value, space_base(x)));
 74   x.properties.push_back(pair<string, string_tree*>("raw", NULL));
 75   assert(is_raw(x));
 76 }
 77 
 78 //: hook replaced in a later layer
 79 int space_base(const reagent& x) {
 80   return current_call().default_space ? (current_call().default_space+/*skip refcount*/1) : 0;
 81 }
 82 
 83 int address(int offset, int base) {
 84   assert(offset >= 0);
 85   if (base == 0) return offset;  // raw
 86   int size = get_or_insert(Memory, base);
 87   if (offset >= size) {
 88   ¦ // todo: test
 89   ¦ raise << current_recipe_name() << ": location " << offset << " is out of bounds " << size << " at " << base << '\n' << end();
 90   ¦ DUMP("");
 91   ¦ exit(1);
 92   ¦ return 0;
 93   }
 94   return base + /*skip length*/1 + offset;
 95 }
 96 
 97 //: reads and writes to the 'default-space' variable have special behavior
 98 
 99 :(after "Begin Preprocess write_memory(x, data)")
100 if (x.name == "default-space") {
101   if (!scalar(data) || !is_mu_space(x))
102   ¦ raise << maybe(current_recipe_name()) << "'default-space' should be of type address:array:location, but is " << to_string(x.type) << '\n' << end();
103   current_call().default_space = data.at(0);
104   return;
105 }
106 :(code)
107 bool is_mu_space(reagent/*copy*/ x) {
108   canonize_type(x);
109   if (!is_compound_type_starting_with(x.type, "address")) return false;
110   drop_from_type(x, "address");
111   if (!is_compound_type_starting_with(x.type, "array")) return false;
112   drop_from_type(x, "array");
113   return x.type && x.type->atom && x.type->name == "location";
114 }
115 
116 :(scenario get_default_space)
117 def main [
118   default-space:space <- copy 10/unsafe
119   1:space/raw <- copy default-space:space
120 ]
121 +mem: storing 10 in location 1
122 
123 :(after "Begin Preprocess read_memory(x)")
124 if (x.name == "default-space") {
125   vector<double> result;
126   result.push_back(current_call().default_space);
127   return result;
128 }
129 
130 //:: fix 'get'
131 
132 :(scenario lookup_sidesteps_default_space_in_get)
133 def main [
134   # pretend pointer to container from outside (2000 reserved for refcount)
135   2001:num <- copy 34
136   2002:num <- copy 35
137   # pretend address:array:location; in practice we'll use 'new'
138   1000:num <- copy 0  # refcount
139   1001:num <- copy 5  # length
140   # actual start of this recipe
141   default-space:space <- copy 1000/unsafe
142   1:&:point <- copy 2000/unsafe
143   9:num/raw <- get *1:&:point, 1:offset
144 ]
145 +mem: storing 35 in location 9
146 
147 :(before "Read element" following "case GET:")
148 element.properties.push_back(pair<string, string_tree*>("raw", NULL));
149 
150 //:: fix 'index'
151 
152 :(scenario lookup_sidesteps_default_space_in_index)
153 def main [
154   # pretend pointer to array from outside (2000 reserved for refcount)
155   2001:num <- copy 2  # length
156   2002:num <- copy 34
157   2003:num <- copy 35
158   # pretend address:array:location; in practice we'll use 'new'
159   1000:num <- copy 0  # refcount
160   1001:num <- copy 5  # length
161   # actual start of this recipe
162   default-space:space <- copy 1000/unsafe
163   1:&:@:num <- copy 2000/unsafe
164   9:num/raw <- index *1:&:@:num, 1
165 ]
166 +mem: storing 35 in location 9
167 
168 :(before "Read element" following "case INDEX:")
169 element.properties.push_back(pair<string, string_tree*>("raw", NULL));
170 
171 //:: 'local-scope' is a convenience operation to automatically deduce
172 //:: the amount of space to allocate in a default space with names
173 
174 :(scenario local_scope)
175 def main [
176   local-scope
177   x:num <- copy 0
178   y:num <- copy 3
179 ]
180 # allocate space for x and y, as well as the chaining slot at 0
181 +mem: array length is 3
182 
183 :(before "End is_disqualified Special-cases")
184 if (x.name == "number-of-locals")
185   x.initialized = true;
186 :(before "End is_special_name Special-cases")
187 if (s == "number-of-locals") return true;
188 
189 :(before "End Rewrite Instruction(curr, recipe result)")
190 // rewrite 'local-scope' to
191 //   ```
192 //   default-space:space <- new location:type, number-of-locals:literal
193 //   ```
194 // where number-of-locals is Name[recipe][""]
195 if (curr.name == "local-scope") {
196   rewrite_default_space_instruction(curr);
197 }
198 :(code)
199 void rewrite_default_space_instruction(instruction& curr) {
200   if (!curr.ingredients.empty())
201   ¦ raise << "'" << to_original_string(curr) << "' can't take any ingredients\n" << end();
202   curr.name = "new";
203   curr.ingredients.push_back(reagent("location:type"));
204   curr.ingredients.push_back(reagent("number-of-locals:literal"));
205   if (!curr.products.empty())
206   ¦ raise << "new-default-space can't take any results\n" << end();
207   curr.products.push_back(reagent("default-space:space"));
208 }
209 :(after "Begin Preprocess read_memory(x)")
210 if (x.name == "number-of-locals") {
211   vector<double> result;
212   result.push_back(Name[get(Recipe_ordinal, current_recipe_name())][""]);
213   if (result.back() == 0)
214   ¦ raise << "no space allocated for default-space in recipe " << current_recipe_name() << "; are you using names?\n" << end();
215   return result;
216 }
217 :(after "Begin Preprocess write_memory(x, data)")
218 if (x.name == "number-of-locals") {
219   raise << maybe(current_recipe_name()) << "can't write to special name 'number-of-locals'\n" << end();
220   return;
221 }
222 
223 //:: try to reclaim the default-space when a recipe returns
224 
225 :(scenario local_scope_reclaimed_on_return)
226 def main [
227   1:num <- foo
228   2:num <- foo
229   3:bool <- equal 1:num, 2:num
230 ]
231 def foo [
232   local-scope
233   result:num <- copy default-space:space
234   return result:num
235 ]
236 # both calls to foo should have received the same default-space
237 +mem: storing 1 in location 3
238 
239 //: todo: do this in a transform, rather than magically in the 'return' instruction
240 :(after "Falling Through End Of Recipe")
241 reclaim_default_space();
242 :(after "Begin Return")
243 reclaim_default_space();
244 :(code)
245 void reclaim_default_space() {
246   if (!Reclaim_memory) return;
247   reagent default_space("default-space:address:array:location");
248   decrement_any_refcounts(default_space);
249 }
250 :(after "Begin Decrement Refcounts(canonized_x)")
251 if (is_mu_space(canonized_x)) {
252   int space_address = (canonized_x.name == "default-space") ? current_call().default_space : get_or_insert(Memory, canonized_x.value);
253   if (space_address == 0) return;
254   // this branch relies on global state
255   string recipe_name;
256   if (has_property(canonized_x, "names")) {
257   ¦ assert(property(canonized_x, "names")->atom);
258   ¦ recipe_name = property(canonized_x, "names")->value;
259   }
260   else {
261   ¦ if (canonized_x.name != "default-space")
262   ¦ ¦ cerr << current_recipe_name() << ": " << to_string(canonized_x) << '\n';
263   ¦ assert(canonized_x.name == "default-space");
264   ¦ recipe_name = current_recipe_name();
265   }
266   const recipe_ordinal space_recipe_ordinal = get(Recipe_ordinal, recipe_name);
267   const recipe& space_recipe = get(Recipe, space_recipe_ordinal);
268   if (canonized_x.name == "default-space" && !has_property(canonized_x, "names") && !starts_by_setting_default_space(space_recipe)) return;
269   // Reclaim Space(space_address, space_recipe_ordinal, space_recipe)
270   decrement_refcount(space_address, canonized_x.type->right,
271   ¦ ¦ /*refcount*/1 + /*array length*/1 + /*number-of-locals*/Name[space_recipe_ordinal][""]);
272   return;
273 }
274 :(code)
275 bool starts_by_setting_default_space(const recipe& r) {
276   return !r.steps.empty()
277   ¦ ¦ && !r.steps.at(0).products.empty()
278   ¦ ¦ && r.steps.at(0).products.at(0).name == "default-space";
279 }
280 
281 //:
282 
283 :(scenario local_scope_reclaims_locals)
284 def main [
285   local-scope
286   x:text <- new [abc]
287 ]
288 # x
289 +mem: automatically abandoning 1004
290 # local-scope
291 +mem: automatically abandoning 1000
292 
293 :(before "Reclaim Space(space_address, space_recipe_ordinal, space_recipe)")
294 if (get_or_insert(Memory, space_address) <= 1) {
295   set<string> reclaimed_locals;
296   trace(9999, "mem") << "trying to reclaim locals" << end();
297   // update any refcounts for variables in the space -- in the context of the space
298   call_stack calls_stash = save_call_stack(space_address, space_recipe_ordinal);
299   Current_routine->calls.swap(calls_stash);
300   // no early returns until we restore 'calls' below
301   for (int i = /*leave default space for last*/1;  i < SIZE(space_recipe.steps);  ++i) {
302   ¦ const instruction& inst = space_recipe.steps.at(i);
303   ¦ for (int i = 0;  i < SIZE(inst.products);  ++i) {
304   ¦ ¦ reagent/*copy*/ product = inst.products.at(i);
305   ¦ ¦ if (reclaimed_locals.find(product.name) != reclaimed_locals.end()) continue;
306   ¦ ¦ reclaimed_locals.insert(product.name);
307   ¦ ¦ // local variables only
308   ¦ ¦ if (has_property(product, "lookup")) continue;
309   ¦ ¦ if (has_property(product, "raw")) continue;  // tests often want to check such locations after they run
310   ¦ ¦ // End Checks For Reclaiming Locals
311   ¦ ¦ trace(9999, "mem") << "trying to reclaim local " << product.original_string << end();
312   ¦ ¦ canonize(product);
313   ¦ ¦ decrement_any_refcounts(product);
314   ¦ }
315   }
316   Current_routine->calls.swap(calls_stash);  // restore
317 }
318 :(code)
319 call_stack save_call_stack(int space_address, recipe_ordinal space_recipe_ordinal) {
320   call dummy_call(space_recipe_ordinal);
321   dummy_call.default_space = space_address;
322   call_stack result;
323   result.push_front(dummy_call);
324   return result;
325 }
326 
327 :(scenario local_variables_can_outlive_call)
328 def main [
329   local-scope
330   x:&:num <- new num:type
331   y:space <- copy default-space:space
332 ]
333 -mem: automatically abandoning 1005
334 
335 //:
336 
337 :(scenario local_scope_does_not_reclaim_escaping_locals)
338 def main [
339   1:text <- foo
340 ]
341 def foo [
342   local-scope
343   x:text <- new [abc]
344   return x:text
345 ]
346 # local-scope
347 +mem: automatically abandoning 1000
348 # x
349 -mem: automatically abandoning 1004
350 
351 :(after "Begin Return")  // before reclaiming default-space
352 increment_refcounts_of_return_ingredients(ingredients);
353 :(code)
354 void increment_refcounts_of_return_ingredients(const vector<vector<double> >& ingredients) {
355   assert(current_instruction().operation == RETURN);
356   if (SIZE(Current_routine->calls) == 1)  // no caller to receive result
357   ¦ return;
358   const instruction& caller_instruction = to_instruction(*++Current_routine->calls.begin());
359   for (int i = 0;  i < min(SIZE(current_instruction().ingredients), SIZE(caller_instruction.products));  ++i) {
360   ¦ if (!is_dummy(caller_instruction.products.at(i))) {
361   ¦ ¦ // no need to canonize ingredient because we ignore its value
362   ¦ ¦ increment_any_refcounts(current_instruction().ingredients.at(i), ingredients.at(i));
363   ¦ }
364   }
365 }
366 
367 //:
368 
369 :(scenario local_scope_frees_up_addresses_inside_containers)
370 container foo [
371   x:num
372   y:&:num
373 ]
374 def main [
375   local-scope
376   x:&:num <- new number:type
377   y:foo <- merge 34, x:&:num
378   # x and y are both cleared when main returns
379 ]
380 +mem: automatically abandoning 1006
381 
382 :(scenario local_scope_returns_addresses_inside_containers)
383 container foo [
384   x:num
385   y:&:num
386 ]
387 def f [
388   local-scope
389   x:&:num <- new number:type
390   *x:&:num <- copy 12
391   y:foo <- merge 34, x:&:num
392   # since y is 'escaping' f, it should not be cleared
393   return y:foo
394 ]
395 def main [
396   1:foo <- f
397   3:num <- get 1:foo, x:offset
398   4:&:num <- get 1:foo, y:offset
399   5:num <- copy *4:&:num
400   1:foo <- put 1:foo, y:offset, 0
401   4:&:num <- copy 0
402 ]
403 +mem: storing 34 in location 1
404 +mem: storing 1006 in location 2
405 +mem: storing 34 in location 3
406 # refcount of 1:foo shouldn't include any stray ones from f
407 +run: {4: ("address" "number")} <- get {1: "foo"}, {y: "offset"}
408 +mem: incrementing refcount of 1006: 1 -> 2
409 # 1:foo wasn't abandoned/cleared
410 +run: {5: "number"} <- copy {4: ("address" "number"), "lookup": ()}
411 +mem: storing 12 in location 5
412 +run: {1: "foo"} <- put {1: "foo"}, {y: "offset"}, {0: "literal"}
413 +mem: decrementing refcount of 1006: 2 -> 1
414 +run: {4: ("address" "number")} <- copy {0: "literal"}
415 +mem: decrementing refcount of 1006: 1 -> 0
416 +mem: automatically abandoning 1006
417 
418 :(scenario local_scope_claims_return_values_when_not_saved)
419 def f [
420   local-scope
421   x:&:num <- new number:type
422   return x:&:num
423 ]
424 def main [
425   f  # doesn't save result
426 ]
427 # x reclaimed
428 +mem: automatically abandoning 1004
429 # f's local scope reclaimed
430 +mem: automatically abandoning 1000
431 
432 //:: all recipes must set default-space one way or another
433 
434 :(before "End Globals")
435 bool Hide_missing_default_space_errors = true;
436 :(before "End Checks")
437 Transform.push_back(check_default_space);  // idempotent
438 :(code)
439 void check_default_space(const recipe_ordinal r) {
440   if (Hide_missing_default_space_errors) return;  // skip previous core tests; this is only for Mu code
441   const recipe& caller = get(Recipe, r);
442   // End check_default_space Special-cases
443   // assume recipes with only numeric addresses know what they're doing (usually tests)
444   if (!contains_non_special_name(r)) return;
445   trace(9991, "transform") << "--- check that recipe " << caller.name << " sets default-space" << end();
446   if (caller.steps.empty()) return;
447   if (!starts_by_setting_default_space(caller))
448   ¦ raise << caller.name << " does not seem to start with 'local-scope' or 'default-space'\n" << end();
449 }
450 :(after "Load Mu Prelude")
451 Hide_missing_default_space_errors = false;
452 :(after "Test Runs")
453 Hide_missing_default_space_errors = true;
454 :(after "Running Main")
455 Hide_missing_default_space_errors = false;
456 
457 :(code)
458 bool contains_non_special_name(const recipe_ordinal r) {
459   for (map<string, int>::iterator p = Name[r].begin();  p != Name[r].end();  ++p) {
460   ¦ if (p->first.empty()) continue;
461   ¦ if (p->first.find("stash_") == 0) continue;  // generated by rewrite_stashes_to_text (cross-layer)
462   ¦ if (!is_special_name(p->first))
463   ¦ ¦ return true;
464   }
465   return false;
466 }
467 
468 // reagent comparison -- only between reagents in a single recipe
469 bool operator==(const reagent& a, const reagent& b) {
470   if (a.name != b.name) return false;
471   if (property(a, "space") != property(b, "space")) return false;
472   return true;
473 }
474 
475 bool operator<(const reagent& a, const reagent& b) {
476   int aspace = 0, bspace = 0;
477   if (has_property(a, "space")) aspace = to_integer(property(a, "space")->value);
478   if (has_property(b, "space")) bspace = to_integer(property(b, "space")->value);
479   if (aspace != bspace) return aspace < bspace;
480   return a.name < b.name;
481 }