https://github.com/akkartik/mu/blob/master/043space.cc
  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 //: Tests in this layer can write to a location as part of one type, and read
 12 //: it as part of another. This is unsafe and insecure, and we'll stop doing
 13 //: this once we switch to variable names.
 14 
 15 //: Under the hood, a space is an array of locations in memory.
 16 :(before "End Mu Types Initialization")
 17 put(Type_abbreviations, "space", new_type_tree("address:array:location"));
 18 
 19 :(scenario set_default_space)
 20 def main [
 21   # prepare default-space address
 22   10:num/alloc-id, 11:num <- copy 0, 1000
 23   # prepare default-space payload
 24   1000:num <- copy 0  # alloc id of payload
 25   1001:num <- copy 5  # length
 26   # actual start of this recipe
 27   default-space:space <- copy 10:&:@:location
 28   # if default-space is 1000, then:
 29   #   1000: alloc id
 30   #   1001: array size
 31   #   1002: location 0 (space for the chaining slot; described later; often unused)
 32   #   1003: location 1 (space for the chaining slot; described later; often unused)
 33   #   1004: local 2 (assuming it is a scalar)
 34   2:num <- copy 93
 35 ]
 36 +mem: storing 93 in location 1004
 37 
 38 :(scenario lookup_sidesteps_default_space)
 39 def main [
 40   # prepare default-space address
 41   10:num/alloc-id, 11:num <- copy 0, 1000
 42   # prepare default-space payload
 43   1000:num <- copy 0  # alloc id of payload
 44   1001:num <- copy 5  # length
 45   # prepare payload outside the local scope
 46   2000:num/alloc-id, 2001:num <- copy 0, 34
 47   # actual start of this recipe
 48   default-space:space <- copy 10:&:@:location
 49   # a local address
 50   2:num, 3:num <- copy 0, 2000
 51   20:num/raw <- copy *2:&:num
 52 ]
 53 +mem: storing 2000 in location 1005
 54 +mem: storing 34 in location 20
 55 
 56 //: precondition: disable name conversion for 'default-space'
 57 
 58 :(scenarios transform)
 59 :(scenario convert_names_passes_default_space)
 60 % Hide_errors = true;
 61 def main [
 62   default-space:num <- copy 0
 63   x:num <- copy 1
 64 ]
 65 +name: assign x 2
 66 -name: assign default-space 1
 67 -name: assign default-space 2
 68 :(scenarios run)
 69 
 70 :(before "End is_disqualified Special-cases")
 71 if (x.name == "default-space")
 72   x.initialized = true;
 73 :(before "End is_special_name Special-cases")
 74 if (s == "default-space") return true;
 75 
 76 //: core implementation
 77 
 78 :(before "End call Fields")
 79 int default_space;
 80 :(before "End call Constructor")
 81 default_space = 0;
 82 
 83 :(before "Begin canonize(x) Lookups")
 84 absolutize(x);
 85 :(code)
 86 void absolutize(reagent& x) {
 87   if (is_raw(x) || is_dummy(x)) return;
 88   if (x.name == "default-space") return;
 89   if (!x.initialized)
 90     raise << to_original_string(current_instruction()) << ": reagent not initialized: '" << x.original_string << "'\n" << end();
 91   x.set_value(address(x.value, space_base(x)));
 92   x.properties.push_back(pair<string, string_tree*>("raw", NULL));
 93   assert(is_raw(x));
 94 }
 95 
 96 //: hook replaced in a later layer
 97 int space_base(const reagent& x) {
 98   return current_call().default_space ? (current_call().default_space + /*skip alloc id*/1) : 0;
 99 }
100 
101 int address(int offset, int base) {
102   assert(offset >= 0);
103   if (base == 0) return offset;  // raw
104   int size = get_or_insert(Memory, base);
105   if (offset >= size) {
106     // todo: test
107     raise << current_recipe_name() << ": location " << offset << " is out of bounds " << size << " at " << base << '\n' << end();
108     DUMP("");
109     exit(1);
110     return 0;
111   }
112   return base + /*skip length*/1 + offset;
113 }
114 
115 //: reads and writes to the 'default-space' variable have special behavior
116 
117 :(after "Begin Preprocess write_memory(x, data)")
118 if (x.name == "default-space") {
119   if (!is_mu_space(x))
120     raise << maybe(current_recipe_name()) << "'default-space' should be of type address:array:location, but is " << to_string(x.type) << '\n' << end();
121   if (SIZE(data) != 2)
122     raise << maybe(current_recipe_name()) << "'default-space' getting data from non-address\n" << end();
123   current_call().default_space = data.at(/*skip alloc id*/1);
124   return;
125 }
126 :(code)
127 bool is_mu_space(reagent/*copy*/ x) {
128   canonize_type(x);
129   if (!is_compound_type_starting_with(x.type, "address")) return false;
130   drop_from_type(x, "address");
131   if (!is_compound_type_starting_with(x.type, "array")) return false;
132   drop_from_type(x, "array");
133   return x.type && x.type->atom && x.type->name == "location";
134 }
135 
136 :(scenario get_default_space)
137 def main [
138   # prepare default-space address
139   10:num/alloc-id, 11:num <- copy 0, 1000
140   # prepare default-space payload
141   1000:num <- copy 0  # alloc id of payload
142   1001:num <- copy 5  # length
143   # actual start of this recipe
144   default-space:space <- copy 10:space
145   2:space/raw <- copy default-space:space
146 ]
147 +mem: storing 1000 in location 3
148 
149 :(after "Begin Preprocess read_memory(x)")
150 if (x.name == "default-space") {
151   vector<double> result;
152   result.push_back(/*alloc id*/0);
153   result.push_back(current_call().default_space);
154   return result;
155 }
156 
157 //:: fix 'get'
158 
159 :(scenario lookup_sidesteps_default_space_in_get)
160 def main [
161   # prepare default-space address
162   10:num/alloc-id, 11:num <- copy 0, 1000
163   # prepare default-space payload
164   1000:num <- copy 0  # alloc id of payload
165   1001:num <- copy 5  # length
166   # prepare payload outside the local scope
167   2000:num/alloc-id, 2001:num/x, 2002:num/y <- copy 0, 34, 35
168   # actual start of this recipe
169   default-space:space <- copy 10:space
170   # a local address
171   2:num, 3:num <- copy 0, 2000
172   3000:num/raw <- get *2:&:point, 1:offset
173 ]
174 +mem: storing 35 in location 3000
175 
176 :(before "Read element" following "case GET:")
177 element.properties.push_back(pair<string, string_tree*>("raw", NULL));
178 
179 //:: fix 'index'
180 
181 :(scenario lookup_sidesteps_default_space_in_index)
182 def main [
183   # prepare default-space address
184   10:num/alloc-id, 11:num <- copy 0, 1000
185   # prepare default-space payload
186   1000:num <- copy 0  # alloc id of payload
187   1001:num <- copy 5  # length
188   # prepare an array address
189   20:num/alloc-id, 21:num <- copy 0, 2000
190   # prepare an array payload
191   2000:num/alloc-id, 2001:num/length, 2002:num/index:0, 2003:num/index:1 <- copy 0, 2, 34, 35
192   # actual start of this recipe
193   default-space:space <- copy 10:&:@:location
194   1:&:@:num <- copy 20:&:@:num/raw
195   3000:num/raw <- index *1:&:@:num, 1
196 ]
197 +mem: storing 35 in location 3000
198 
199 :(before "Read element" following "case INDEX:")
200 element.properties.push_back(pair<string, string_tree*>("raw", NULL));
201 
202 //:: 'local-scope' is a convenience operation to automatically deduce
203 //:: the amount of space to allocate in a default space with names
204 
205 :(scenario local_scope)
206 def main [
207   local-scope
208   x:num <- copy 0
209   y:num <- copy 3
210 ]
211 # allocate space for x and y, as well as the chaining slot at indices 0 and 1
212 +mem: array length is 4
213 
214 :(before "End is_disqualified Special-cases")
215 if (x.name == "number-of-locals")
216   x.initialized = true;
217 :(before "End is_special_name Special-cases")
218 if (s == "number-of-locals") return true;
219 
220 :(before "End Rewrite Instruction(curr, recipe result)")
221 // rewrite 'local-scope' to
222 //   ```
223 //   default-space:space <- new location:type, number-of-locals:literal
224 //   ```
225 // where number-of-locals is Name[recipe][""]
226 if (curr.name == "local-scope") {
227   rewrite_default_space_instruction(curr);
228 }
229 :(code)
230 void rewrite_default_space_instruction(instruction& curr) {
231   if (!curr.ingredients.empty())
232     raise << "'" << to_original_string(curr) << "' can't take any ingredients\n" << end();
233   curr.name = "new";
234   curr.ingredients.push_back(reagent("location:type"));
235   curr.ingredients.push_back(reagent("number-of-locals:literal"));
236   if (!curr.products.empty())
237     raise << "local-scope can't take any results\n" << end();
238   curr.products.push_back(reagent("default-space:space"));
239 }
240 :(after "Begin Preprocess read_memory(x)")
241 if (x.name == "number-of-locals") {
242   vector<double> result;
243   result.push_back(Name[get(Recipe_ordinal, current_recipe_name())][""]);
244   if (result.back() == 0)
245     raise << "no space allocated for default-space in recipe " << current_recipe_name() << "; are you using names?\n" << end();
246   return result;
247 }
248 :(after "Begin Preprocess write_memory(x, data)")
249 if (x.name == "number-of-locals") {
250   raise << maybe(current_recipe_name()) << "can't write to special name 'number-of-locals'\n" << end();
251   return;
252 }
253 
254 //:: all recipes must set default-space one way or another
255 
256 :(before "End Globals")
257 bool Hide_missing_default_space_errors = true;
258 :(before "End Checks")
259 Transform.push_back(check_default_space);  // idempotent
260 :(code)
261 void check_default_space(const recipe_ordinal r) {
262   if (Hide_missing_default_space_errors) return;  // skip previous core tests; this is only for Mu code
263   const recipe& caller = get(Recipe, r);
264   // End check_default_space Special-cases
265   // assume recipes with only numeric addresses know what they're doing (usually tests)
266   if (!contains_non_special_name(r)) return;
267   trace(9991, "transform") << "--- check that recipe " << caller.name << " sets default-space" << end();
268   if (caller.steps.empty()) return;
269   if (!starts_by_setting_default_space(caller))
270     raise << caller.name << " does not seem to start with 'local-scope' or 'default-space'\n" << end();
271 }
272 bool starts_by_setting_default_space(const recipe& r) {
273   return !r.steps.empty()
274       && !r.steps.at(0).products.empty()
275       && r.steps.at(0).products.at(0).name == "default-space";
276 }
277 
278 :(after "Load Mu Prelude")
279 Hide_missing_default_space_errors = false;
280 :(after "Test Runs")
281 Hide_missing_default_space_errors = true;
282 :(after "Running Main")
283 Hide_missing_default_space_errors = false;
284 
285 :(code)
286 bool contains_non_special_name(const recipe_ordinal r) {
287   for (map<string, int>::iterator p = Name[r].begin();  p != Name[r].end();  ++p) {
288     if (p->first.empty()) continue;
289     if (p->first.find("stash_") == 0) continue;  // generated by rewrite_stashes_to_text (cross-layer)
290     if (!is_special_name(p->first))
291       return true;
292   }
293   return false;
294 }