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