1 // To recursively copy containers and any addresses they contain, use
  2 // 'deep-copy'.
  3 //
  4 // Invariant: After a deep-copy its ingredient and result will point to no
  5 // common addresses.
  6 //
  7 // We do handle cycles in the ingredient, however. All cycles are translated
  8 // to new cycles in the product.
  9 
 10 :(scenario deep_copy_number)
 11 def main [
 12   local-scope
 13   x:num <- copy 34
 14   y:num <- deep-copy x
 15   10:bool/raw <- equal x, y
 16 ]
 17 # non-address primitives are identical
 18 +mem: storing 1 in location 10
 19 
 20 :(scenario deep_copy_null_pointer)
 21 def main [
 22   local-scope
 23   x:&:num <- copy 0
 24   y:&:num <- deep-copy x
 25   10:bool/raw <- equal x, y
 26 ]
 27 # null addresses are identical
 28 +mem: storing 1 in location 10
 29 
 30 :(scenario deep_copy_container_without_address)
 31 container foo [
 32   x:num
 33   y:num
 34 ]
 35 def main [
 36   local-scope
 37   a:foo <- merge 34, 35
 38   b:foo <- deep-copy a
 39   10:bool/raw <- equal a, b
 40 ]
 41 # containers are identical as long as they don't contain addresses
 42 +mem: storing 1 in location 10
 43 
 44 :(scenario deep_copy_address)
 45 % Memory_allocated_until = 200;
 46 def main [
 47   # avoid all memory allocations except the implicit ones inside deep-copy, so
 48   # that the result is deterministic
 49   1:&:num <- copy 100/unsafe  # pretend allocation
 50   *1:&:num <- copy 34
 51   2:&:num <- deep-copy 1:&:num
 52   10:bool <- equal 1:&:num, 2:&:num
 53   11:bool <- equal *1:&:num, *2:&:num
 54   2:&:num <- copy 0
 55 ]
 56 # the result of deep-copy is a new address
 57 +mem: storing 0 in location 10
 58 # however, the contents are identical
 59 +mem: storing 1 in location 11
 60 
 61 :(scenario deep_copy_address_to_container)
 62 % Memory_allocated_until = 200;
 63 def main [
 64   # avoid all memory allocations except the implicit ones inside deep-copy, so
 65   # that the result is deterministic
 66   1:&:point <- copy 100/unsafe  # pretend allocation
 67   *1:&:point <- merge 34, 35
 68   2:&:point <- deep-copy 1:&:point
 69   10:bool <- equal 1:&:point, 2:&:point
 70   11:bool <- equal *1:&:point, *2:&:point
 71 ]
 72 # the result of deep-copy is a new address
 73 +mem: storing 0 in location 10
 74 # however, the contents are identical
 75 +mem: storing 1 in location 11
 76 
 77 :(scenario deep_copy_address_to_address)
 78 % Memory_allocated_until = 200;
 79 def main [
 80   # avoid all memory allocations except the implicit ones inside deep-copy, so
 81   # that the result is deterministic
 82   1:&:&:num <- copy 100/unsafe  # pretend allocation
 83   *1:&:&:num <- copy 150/unsafe
 84   **1:&:&:num <- copy 34
 85   2:&:&:num <- deep-copy 1:&:&:num
 86   10:bool <- equal 1:&:&:num, 2:&:&:num
 87   11:bool <- equal *1:&:&:num, *2:&:&:num
 88   12:bool <- equal **1:&:&:num, **2:&:&:num
 89 ]
 90 # the result of deep-copy is a new address
 91 +mem: storing 0 in location 10
 92 # any addresses in it or pointed to it are also new
 93 +mem: storing 0 in location 11
 94 # however, the non-address contents are identical
 95 +mem: storing 1 in location 12
 96 
 97 :(scenario deep_copy_array)
 98 % Memory_allocated_until = 200;
 99 def main [
100   # avoid all memory allocations except the implicit ones inside deep-copy, so
101   # that the result is deterministic
102   100:num <- copy 3  # pretend array length
103   1:&:@:num <- copy 100/unsafe  # pretend allocation
104   put-index *1:&:@:num, 0, 34
105   put-index *1:&:@:num, 1, 35
106   put-index *1:&:@:num, 2, 36
107   stash [old:], *1:&:@:num
108   2:&:@:num <- deep-copy 1:&:@:num
109   stash 2:&:@:num
110   stash [new:], *2:&:@:num
111   10:bool <- equal 1:&:@:num, 2:&:@:num
112   11:bool <- equal *1:&:@:num, *2:&:@:num
113 ]
114 +app: old: 3 34 35 36
115 +app: new: 3 34 35 36
116 # the result of deep-copy is a new address
117 +mem: storing 0 in location 10
118 # however, the contents are identical
119 +mem: storing 1 in location 11
120 
121 :(scenario deep_copy_container_with_address)
122 container foo [
123   x:num
124   y:&:num
125 ]
126 def main [
127   local-scope
128   y0:&:num <- new number:type
129   *y0 <- copy 35
130   a:foo <- merge 34, y0
131   b:foo <- deep-copy a
132   10:bool/raw <- equal a, b
133   y1:&:num <- get b, y:offset
134   11:bool/raw <- equal y0, y1
135   12:num/raw <- copy *y1
136 ]
137 # containers containing addresses are not identical to their deep copies
138 +mem: storing 0 in location 10
139 # the addresses they contain are not identical either
140 +mem: storing 0 in location 11
141 +mem: storing 35 in location 12
142 
143 :(scenario deep_copy_exclusive_container_with_address)
144 exclusive-container foo [
145   x:num
146   y:&:num
147 ]
148 def main [
149   local-scope
150   y0:&:num <- new number:type
151   *y0 <- copy 34
152   a:foo <- merge 1/y, y0
153   b:foo <- deep-copy a
154   10:bool/raw <- equal a, b
155   y1:&:num, z:bool <- maybe-convert b, y:variant
156   11:bool/raw <- equal y0, y1
157   12:num/raw <- copy *y1
158 ]
159 # exclusive containers containing addresses are not identical to their deep copies
160 +mem: storing 0 in location 10
161 # the addresses they contain are not identical either
162 +mem: storing 0 in location 11
163 +mem: storing 34 in location 12
164 
165 :(scenario deep_copy_exclusive_container_with_container_with_address)
166 exclusive-container foo [
167   x:num
168   y:bar  # inline
169 ]
170 container bar [
171   x:&:num
172 ]
173 def main [
174   local-scope
175   y0:&:num <- new number:type
176   *y0 <- copy 34
177   a:bar <- merge y0
178   b:foo <- merge 1/y, a
179   c:foo <- deep-copy b
180   10:bool/raw <- equal b, c
181   d:bar, z:bool <- maybe-convert c, y:variant
182   y1:&:num <- get d, x:offset
183   11:bool/raw <- equal y0, y1
184   12:num/raw <- copy *y1
185 ]
186 # exclusive containers containing addresses are not identical to their deep copies
187 +mem: storing 0 in location 10
188 # sub-containers containing addresses are not identical either
189 +mem: storing 0 in location 11
190 +mem: storing 34 in location 12
191 
192 :(before "End Primitive Recipe Declarations")
193 DEEP_COPY,
194 :(before "End Primitive Recipe Numbers")
195 put(Recipe_ordinal, "deep-copy", DEEP_COPY);
196 :(before "End Primitive Recipe Checks")
197 case DEEP_COPY: {
198   if (SIZE(inst.ingredients) != 1) {
199     raise << maybe(get(Recipe, r).name) << "'deep-copy' takes exactly one ingredient rather than '" << to_original_string(inst) << "'\n" << end();
200     break;
201   }
202   if (SIZE(inst.products) != 1) {
203     raise << maybe(get(Recipe, r).name) << "'deep-copy' takes exactly one ingredient rather than '" << to_original_string(inst) << "'\n" << end();
204     break;
205   }
206   if (!types_strictly_match(inst.ingredients.at(0), inst.products.at(0))) {
207     raise << maybe(get(Recipe, r).name) << "'deep-copy' requires its ingredient and product to be the same type, but got '" << to_original_string(inst) << "'\n" << end();
208     break;
209   }
210   break;
211 }
212 :(before "End Primitive Recipe Implementations")
213 case DEEP_COPY: {
214   products.push_back(deep_copy(current_instruction().ingredients.at(0)));
215   break;
216 }
217 
218 :(code)
219 vector<double> deep_copy(const reagent& in) {
220   // allocate a tiny bit of temporary space for deep_copy()
221   trace(9991, "run") << "deep-copy: allocating space for temporary" << end();
222   reagent tmp("tmp:address:number");
223   tmp.set_value(allocate(1));
224   map<int, int> addresses_copied;
225   vector<double> result = deep_copy(in, addresses_copied, tmp);
226   // reclaim Mu memory allocated for tmp
227   trace(9991, "run") << "deep-copy: reclaiming temporary" << end();
228   abandon(tmp.value, payload_size(tmp));
229   // reclaim host memory allocated for tmp.type when tmp goes out of scope
230   return result;
231 }
232 
233 vector<double> deep_copy(reagent/*copy*/ in, map<int, int>& addresses_copied, const reagent& tmp) {
234   canonize(in);
235   if (is_mu_address(in)) {
236     // hack: skip primitive containers that do their own locking; they're designed to be shared between routines
237     type_tree* payload = in.type->right;
238     if (payload->left->name == "channel" || payload->left->name == "screen" || payload->left->name == "console" || payload->left->name == "resources")
239       return read_memory(in);
240   }
241   vector<double> result;
242   if (is_mu_address(in))
243     result.push_back(deep_copy_address(in, addresses_copied, tmp));
244   else
245     deep_copy(in, addresses_copied, tmp, result);
246   return result;
247 }
248 
249 // deep-copy an address and return a new address
250 int deep_copy_address(const reagent& canonized_in, map<int, int>& addresses_copied, const reagent& tmp) {
251   if (address_value(canonized_in) == 0) return 0;
252   int in_address = payload_address(canonized_in);
253   trace(9991, "run") << "deep-copy: copying address " << in_address << end();
254   if (contains_key(addresses_copied, in_address)) {
255     int out = get(addresses_copied, in_address);
256     trace(9991, "run") << "deep-copy: copy already exists: " << out << end();
257     return out;
258   }
259   int out = allocate(payload_size(canonized_in));
260   trace(9991, "run") << "deep-copy: new address is " << out << end();
261   put(addresses_copied, in_address, out);
262   reagent/*copy*/ payload = canonized_in;
263   payload.properties.push_back(pair<string, string_tree*>("lookup", NULL));
264   trace(9991, "run") << "recursing on payload " << payload.value << ' ' << to_string(payload) << end();
265   vector<double> data = deep_copy(payload, addresses_copied, tmp);
266   trace(9991, "run") << "deep-copy: writing result " << out << ": " << to_string(data) << end();
267   // HACK: write_memory interface isn't ideal for this situation; we need
268   // a temporary location to help copy the payload.
269   trace(9991, "run") << "deep-copy: writing temporary " << tmp.value << ": " << out << end();
270   put(Memory, tmp.value, out);
271   payload.set_value(tmp.value);  // now modified for output
272   vector<double> old_data = read_memory(payload);
273   trace(9991, "run") << "deep-copy: really writing to " << payload.value << ' ' << to_string(payload) << " (old value " << to_string(old_data) << " new value " << to_string(data) << ")" << end();
274   write_memory(payload, data);
275   trace(9991, "run") << "deep-copy: output is " << to_string(data) << end();
276   return out;
277 }
278 
279 // deep-copy a non-address and return a vector of locations
280 void deep_copy(const reagent& canonized_in, map<int, int>& addresses_copied, const reagent& tmp, vector<double>& out) {
281   assert(!is_mu_address(canonized_in));
282   vector<double> data = read_memory(canonized_in);
283   out.insert(out.end(), data.begin(), data.end());
284   if (!contains_key(Container_metadata, canonized_in.type)) return;
285   trace(9991, "run") << "deep-copy: scanning for addresses in " << to_string(data) << end();
286   const container_metadata& metadata = get(Container_metadata, canonized_in.type);
287   for (map<set<tag_condition_info>, set<address_element_info> >::const_iterator p = metadata.address.begin();  p != metadata.address.end();  ++p) {
288     if (!all_match(data, p->first)) continue;
289     for (set<address_element_info>::const_iterator info = p->second.begin();  info != p->second.end();  ++info) {
290       // hack: skip primitive containers that do their own locking; they're designed to be shared between routines
291       if (!info->payload_type->atom && info->payload_type->left->name == "channel")
292         continue;
293       if (info->payload_type->name == "screen" || info->payload_type->name == "console" || info->payload_type->name == "resources")
294         continue;
295       // construct a fake reagent that reads directly from the appropriate
296       // field of the container
297       reagent curr;
298       if (info->payload_type->atom)
299         curr.type = new type_tree(new type_tree("address"), new type_tree(new type_tree(info->payload_type->name), NULL));
300       else
301         curr.type = new type_tree(new type_tree("address"), new type_tree(*info->payload_type));
302       curr.set_value(canonized_in.value + info->offset);
303       curr.properties.push_back(pair<string, string_tree*>("raw", NULL));
304       trace(9991, "run") << "deep-copy: copying address " << curr.value << end();
305       out.at(info->offset) = deep_copy_address(curr, addresses_copied, tmp);
306     }
307   }
308 }
309 
310 int payload_address(reagent/*copy*/ x) {
311   x.properties.push_back(pair<string, string_tree*>("lookup", NULL));
312   canonize(x);
313   return x.value;
314 }
315 
316 int address_value(const reagent& x) {
317   assert(is_mu_address(x));
318   vector<double> result = read_memory(x);
319   assert(SIZE(result) == 1);
320   return static_cast<int>(result.at(0));
321 }
322 
323 :(scenario deep_copy_stress_test_1)
324 container foo1 [
325   p:&:num
326 ]
327 container foo2 [
328   p:&:foo1
329 ]
330 exclusive-container foo3 [
331   p:&:foo1
332   q:&:foo2
333 ]
334 def main [
335   local-scope
336   x:&:num <- new number:type
337   *x <- copy 34
338   a:&:foo1 <- new foo1:type
339   *a <- merge x
340   b:&:foo2 <- new foo2:type
341   *b <- merge a
342   c:foo3 <- merge 1/q, b
343   d:foo3 <- deep-copy c
344   e:&:foo2, z:bool <- maybe-convert d, q:variant
345   f:&:foo1 <- get *e, p:offset
346   g:&:num <- get *f, p:offset
347   1:num/raw <- copy *g
348 ]
349 +mem: storing 34 in location 1
350 
351 :(scenario deep_copy_stress_test_2)
352 container foo1 [
353   p:&:num
354 ]
355 container foo2 [
356   p:&:foo1
357 ]
358 exclusive-container foo3 [
359   p:&:foo1
360   q:&:foo2
361 ]
362 container foo4 [
363   p:num
364   q:&:foo3
365 ]
366 def main [
367   local-scope
368   x:&:num <- new number:type
369   *x <- copy 34
370   a:&:foo1 <- new foo1:type
371   *a <- merge x
372   b:&:foo2 <- new foo2:type
373   *b <- merge a
374   c:&:foo3 <- new foo3:type
375   *c <- merge 1/q, b
376   d:foo4 <- merge 35, c
377   e:foo4 <- deep-copy d
378   f:&:foo3 <- get e, q:offset
379   g:&:foo2, z:bool <- maybe-convert *f, q:variant
380   h:&:foo1 <- get *g, p:offset
381   y:&:num <- get *h, p:offset
382   1:num/raw <- copy *y
383 ]
384 +mem: storing 34 in location 1
385 
386 :(scenario deep_copy_cycles)
387 container foo [
388   p:num
389   q:&:foo
390 ]
391 def main [
392   local-scope
393   x:&:foo <- new foo:type
394   *x <- put *x, p:offset, 34
395   *x <- put *x, q:offset, x  # create a cycle
396   y:&:foo <- deep-copy x
397   1:num/raw <- get *y, p:offset
398   y2:&:foo <- get *y, q:offset
399   2:bool/raw <- equal y, y2  # is it still a cycle?
400   3:bool/raw <- equal x, y  # is it the same cycle?
401   # not bothering cleaning up; both cycles leak memory
402 ]
403 +mem: storing 34 in location 1
404 # deep copy also contains a cycle
405 +mem: storing 1 in location 2
406 # but it's a completely different (disjoint) cycle
407 +mem: storing 0 in location 3
408 
409 //: todo: version of deep_copy_cycles that breaks cycles at end and verifies no memory leaks
410 //: needs approximate matching over scenario traces
411 
412 :(scenario deep_copy_skips_channel)
413 # ugly! dummy 'channel' type if we happen to be building without that layer
414 % if (!contains_key(Type_ordinal, "channel")) get_or_insert(Type, put(Type_ordinal, "channel", Next_type_ordinal++)).name = "channel";
415 def main [
416   local-scope
417   x:&:channel:num <- new {(channel num): type}
418   y:&:channel:num <- deep-copy x
419   10:bool/raw <- equal x, y
420 ]
421 # channels are never deep-copied
422 +mem: storing 1 in location 10
423 
424 :(scenario deep_copy_skips_nested_channel)
425 # ugly! dummy 'channel' type if we happen to be building without that layer
426 % if (!contains_key(Type_ordinal, "channel")) get_or_insert(Type, put(Type_ordinal, "channel", Next_type_ordinal++)).name = "channel";
427 container foo [
428   c:&:channel:num
429 ]
430 def main [
431   local-scope
432   x:&:foo <- new foo:type
433   y:&:foo <- deep-copy x
434   xc:&:channel:num <- get *x, c:offset
435   yc:&:channel:num <- get *y, c:offset
436   10:bool/raw <- equal xc, yc
437 ]
438 # channels are never deep-copied
439 +mem: storing 1 in location 10
440 
441 :(scenario deep_copy_skips_resources)
442 # ugly! dummy 'resources' type if we happen to be building without that layer
443 % if (!contains_key(Type_ordinal, "resources")) get_or_insert(Type, put(Type_ordinal, "resources", Next_type_ordinal++)).name = "resources";
444 def main [
445   local-scope
446   x:&:resources <- new resources:type
447   y:&:resources <- deep-copy x
448   10:bool/raw <- equal x, y
449 ]
450 # resources are never deep-copied
451 +mem: storing 1 in location 10
452 
453 :(scenario deep_copy_skips_nested_resources)
454 # ugly! dummy 'resources' type if we happen to be building without that layer
455 % if (!contains_key(Type_ordinal, "resources")) get_or_insert(Type, put(Type_ordinal, "resources", Next_type_ordinal++)).name = "resources";
456 container foo [
457   c:&:resources
458 ]
459 def main [
460   local-scope
461   x:&:foo <- new foo:type
462   y:&:foo <- deep-copy x
463   xc:&:resources <- get *x, c:offset
464   yc:&:resources <- get *y, c:offset
465   10:bool/raw <- equal xc, yc
466 ]
467 # resources are never deep-copied
468 +mem: storing 1 in location 10