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