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_container_without_address)
 24 container foo [
 25   x:num
 26   y:num
 27 ]
 28 def main [
 29   local-scope
 30   a:foo <- merge 34, 35
 31   b:foo <- deep-copy a
 32   10:bool/raw <- equal a, b
 33 ]
 34 # containers are identical as long as they don't contain addresses
 35 +mem: storing 1 in location 10
 36 
 37 :(scenario deep_copy_address)
 38 % Memory_allocated_until = 200;
 39 def main [
 40   # avoid all memory allocations except the implicit ones inside deep-copy, so
 41   # that the result is deterministic
 42   1:&:num <- copy 100/unsafe  # pretend allocation
 43   *1:&:num <- copy 34
 44   2:&:num <- deep-copy 1:&:num
 45   10:bool <- equal 1:&:num, 2:&:num
 46   11:bool <- equal *1:&:num, *2:&:num
 47   2:&:num <- copy 0
 48 ]
 49 # the result of deep-copy is a new address
 50 +mem: storing 0 in location 10
 51 # however, the contents are identical
 52 +mem: storing 1 in location 11
 53 # the result of deep-copy gets a refcount of 1
 54 # (its address 202 = 200 base + 2 for temporary space inside deep-copy)
 55 +run: {2: ("address" "number")} <- copy {0: "literal"}
 56 +mem: decrementing refcount of 202: 1 -> 0
 57 +abandon: saving 202 in free-list of size 2
 58 
 59 :(scenario deep_copy_address_to_container)
 60 % Memory_allocated_until = 200;
 61 def main [
 62   # avoid all memory allocations except the implicit ones inside deep-copy, so
 63   # that the result is deterministic
 64   1:&:point <- copy 100/unsafe  # pretend allocation
 65   *1:&:point <- merge 34, 35
 66   2:&:point <- deep-copy 1:&:point
 67   10:bool <- equal 1:&:point, 2:&:point
 68   11:bool <- equal *1:&:point, *2:&:point
 69 ]
 70 # the result of deep-copy is a new address
 71 +mem: storing 0 in location 10
 72 # however, the contents are identical
 73 +mem: storing 1 in location 11
 74 
 75 :(scenario deep_copy_address_to_address)
 76 % Memory_allocated_until = 200;
 77 def main [
 78   # avoid all memory allocations except the implicit ones inside deep-copy, so
 79   # that the result is deterministic
 80   1:&:&:num <- copy 100/unsafe  # pretend allocation
 81   *1:&:&:num <- copy 150/unsafe
 82   **1:&:&:num <- copy 34
 83   2:&:&:num <- deep-copy 1:&:&:num
 84   10:bool <- equal 1:&:&:num, 2:&:&:num
 85   11:bool <- equal *1:&:&:num, *2:&:&:num
 86   12:bool <- equal **1:&:&:num, **2:&:&:num
 87 ]
 88 # the result of deep-copy is a new address
 89 +mem: storing 0 in location 10
 90 # any addresses in it or pointed to it are also new
 91 +mem: storing 0 in location 11
 92 # however, the non-address contents are identical
 93 +mem: storing 1 in location 12
 94 
 95 :(scenario deep_copy_array)
 96 % Memory_allocated_until = 200;
 97 def main [
 98   # avoid all memory allocations except the implicit ones inside deep-copy, so
 99   # that the result is deterministic
100   100:num <- copy 1  # pretend refcount
101   101:num <- copy 3  # pretend array length
102   1:&:@:num <- copy 100/unsafe  # pretend allocation
103   put-index *1:&:@:num, 0, 34
104   put-index *1:&:@:num, 1, 35
105   put-index *1:&:@:num, 2, 36
106   stash [old:], *1:&:@:num
107   2:&:@:num <- deep-copy 1:&:@:num
108   stash 2:&:@:num
109   stash [new:], *2:&:@:num
110   10:bool <- equal 1:&:@:num, 2:&:@:num
111   11:bool <- equal *1:&:@:num, *2:&:@:num
112 ]
113 +app: old: 3 34 35 36
114 +app: new: 3 34 35 36
115 # the result of deep-copy is a new address
116 +mem: storing 0 in location 10
117 # however, the contents are identical
118 +mem: storing 1 in location 11
119 
120 :(scenario deep_copy_container_with_address)
121 container foo [
122   x:num
123   y:&:num
124 ]
125 def main [
126   local-scope
127   y0:&:num <- new number:type
128   *y0 <- copy 35
129   a:foo <- merge 34, y0
130   b:foo <- deep-copy a
131   10:bool/raw <- equal a, b
132   y1:&:num <- get b, y:offset
133   11:bool/raw <- equal y0, y1
134   12:num/raw <- copy *y1
135 ]
136 # containers containing addresses are not identical to their deep copies
137 +mem: storing 0 in location 10
138 # the addresses they contain are not identical either
139 +mem: storing 0 in location 11
140 +mem: storing 35 in location 12
141 
142 :(scenario deep_copy_exclusive_container_with_address)
143 exclusive-container foo [
144   x:num
145   y:&:num
146 ]
147 def main [
148   local-scope
149   y0:&:num <- new number:type
150   *y0 <- copy 34
151   a:foo <- merge 1/y, y0
152   b:foo <- deep-copy a
153   10:bool/raw <- equal a, b
154   y1:&:num, z:bool <- maybe-convert b, y:variant
155   11:bool/raw <- equal y0, y1
156   12:num/raw <- copy *y1
157 ]
158 # exclusive containers containing addresses are not identical to their deep copies
159 +mem: storing 0 in location 10
160 # the addresses they contain are not identical either
161 +mem: storing 0 in location 11
162 +mem: storing 34 in location 12
163 
164 :(scenario deep_copy_exclusive_container_with_container_with_address)
165 exclusive-container foo [
166   x:num
167   y:bar  # inline
168 ]
169 container bar [
170   x:&:num
171 ]
172 def main [
173   local-scope
174   y0:&:num <- new number:type
175   *y0 <- copy 34
176   a:bar <- merge y0
177   b:foo <- merge 1/y, a
178   c:foo <- deep-copy b
179   10:bool/raw <- equal b, c
180   d:bar, z:bool <- maybe-convert c, y:variant
181   y1:&:num <- get d, x:offset
182   11:bool/raw <- equal y0, y1
183   12:num/raw <- copy *y1
184 ]
185 # exclusive containers containing addresses are not identical to their deep copies
186 +mem: storing 0 in location 10
187 # sub-containers containing addresses are not identical either
188 +mem: storing 0 in location 11
189 +mem: storing 34 in location 12
190 
191 :(before "End Primitive Recipe Declarations")
192 DEEP_COPY,
193 :(before "End Primitive Recipe Numbers")
194 put(Recipe_ordinal, "deep-copy", DEEP_COPY);
195 :(before "End Primitive Recipe Checks")
196 case DEEP_COPY: {
197   if (SIZE(inst.ingredients) != 1) {
198     raise << maybe(get(Recipe, r).name) << "'deep-copy' takes exactly one ingredient rather than '" << inst.original_string << "'\n" << end();
199     break;
200   }
201   if (SIZE(inst.products) != 1) {
202     raise << maybe(get(Recipe, r).name) << "'deep-copy' takes exactly one ingredient rather than '" << inst.original_string << "'\n" << end();
203     break;
204   }
205   if (!types_strictly_match(inst.ingredients.at(0), inst.products.at(0))) {
206     raise << maybe(get(Recipe, r).name) << "'deep-copy' requires its ingredient and product to be the same type, but got '" << inst.original_string << "'\n" << end();
207     break;
208   }
209   break;
210 }
211 :(before "End Primitive Recipe Implementations")
212 case DEEP_COPY: {
213   const reagent& input = current_instruction().ingredients.at(0);
214   // allocate a tiny bit of temporary space for deep_copy()
215   trace(9991, "run") << "deep-copy: allocating space for temporary" << end();
216   reagent tmp("tmp:address:number");
217   tmp.set_value(allocate(1));
218   products.push_back(deep_copy(input, tmp));
219   // reclaim Mu memory allocated for tmp
220   trace(9991, "run") << "deep-copy: reclaiming temporary" << end();
221   abandon(tmp.value, payload_type(tmp.type), payload_size(tmp));
222   // reclaim host memory allocated for tmp.type when tmp goes out of scope
223   break;
224 }
225 
226 :(code)
227 vector<double> deep_copy(const reagent& in, const reagent& tmp) {
228   map<int, int> addresses_copied;
229   return deep_copy(in, addresses_copied, tmp);
230 }
231 
232 vector<double> deep_copy(reagent/*copy*/ in, map<int, int>& addresses_copied, const reagent& tmp) {
233   canonize(in);
234   vector<double> result;
235   if (is_mu_address(in))
236     result.push_back(deep_copy_address(in, addresses_copied, tmp));
237   else
238     deep_copy(in, addresses_copied, tmp, result);
239   return result;
240 }
241 
242 // deep-copy an address and return a new address
243 int deep_copy_address(const reagent& canonized_in, map<int, int>& addresses_copied, const reagent& tmp) {
244   if (canonized_in.value == 0) return 0;
245   int in_address = payload_address(canonized_in);
246   trace(9991, "run") << "deep-copy: copying address " << in_address << end();
247   if (contains_key(addresses_copied, in_address)) {
248     int out = get(addresses_copied, in_address);
249     trace(9991, "run") << "deep-copy: copy already exists: " << out << end();
250     return out;
251   }
252   int out = allocate(payload_size(canonized_in));
253   trace(9991, "run") << "deep-copy: new address is " << out << end();
254   put(addresses_copied, in_address, out);
255   reagent/*copy*/ payload = canonized_in;
256   payload.properties.push_back(pair<string, string_tree*>("lookup", NULL));
257   trace(9991, "run") << "recursing on payload " << payload.value << ' ' << to_string(payload) << end();
258   vector<double> data = deep_copy(payload, addresses_copied, tmp);
259   trace(9991, "run") << "deep-copy: writing result " << out << ": " << to_string(data) << end();
260   // HACK: write_memory interface isn't ideal for this situation; we need
261   // a temporary location to help copy the payload.
262   trace(9991, "run") << "deep-copy: writing temporary " << tmp.value << ": " << out << end();
263   put(Memory, tmp.value, out);
264   payload.set_value(tmp.value);  // now modified for output
265   vector<double> old_data = read_memory(payload);
266   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();
267   write_memory(payload, data);
268   trace(9991, "run") << "deep-copy: output is " << to_string(data) << end();
269   return out;
270 }
271 
272 // deep-copy a non-address and return a vector of locations
273 void deep_copy(const reagent& canonized_in, map<int, int>& addresses_copied, const reagent& tmp, vector<double>& out) {
274   assert(!is_mu_address(canonized_in));
275   vector<double> data = read_memory(canonized_in);
276   out.insert(out.end(), data.begin(), data.end());
277   if (!contains_key(Container_metadata, canonized_in.type)) return;
278   trace(9991, "run") << "deep-copy: scanning for addresses in " << to_string(data) << end();
279   const container_metadata& metadata = get(Container_metadata, canonized_in.type);
280   for (map<set<tag_condition_info>, set<address_element_info> >::const_iterator p = metadata.address.begin();  p != metadata.address.end();  ++p) {
281     if (!all_match(data, p->first)) continue;
282     for (set<address_element_info>::const_iterator info = p->second.begin();  info != p->second.end();  ++info) {
283       // construct a fake reagent that reads directly from the appropriate
284       // field of the container
285       reagent curr;
286       if (info->payload_type->atom)
287         curr.type = new type_tree(new type_tree("address"), new type_tree(new type_tree(info->payload_type->name), NULL));
288       else
289         curr.type = new type_tree(new type_tree("address"), new type_tree(*info->payload_type));
290       curr.set_value(canonized_in.value + info->offset);
291       curr.properties.push_back(pair<string, string_tree*>("raw", NULL));
292       trace(9991, "run") << "deep-copy: copying address " << curr.value << end();
293       out.at(info->offset) = deep_copy_address(curr, addresses_copied, tmp);
294     }
295   }
296 }
297 
298 int payload_address(reagent/*copy*/ x) {
299   x.properties.push_back(pair<string, string_tree*>("lookup", NULL));
300   canonize(x);
301   return x.value;
302 }
303 
304 //: moar tests, just because I can't believe it all works
305 
306 :(scenario deep_copy_stress_test_1)
307 container foo1 [
308   p:&:num
309 ]
310 container foo2 [
311   p:&:foo1
312 ]
313 exclusive-container foo3 [
314   p:&:foo1
315   q:&:foo2
316 ]
317 def main [
318   local-scope
319   x:&:num <- new number:type
320   *x <- copy 34
321   a:&:foo1 <- new foo1:type
322   *a <- merge x
323   b:&:foo2 <- new foo2:type
324   *b <- merge a
325   c:foo3 <- merge 1/q, b
326   d:foo3 <- deep-copy c
327   e:&:foo2, z:bool <- maybe-convert d, q:variant
328   f:&:foo1 <- get *e, p:offset
329   g:&:num <- get *f, p:offset
330   1:num/raw <- copy *g
331 ]
332 +mem: storing 34 in location 1
333 
334 :(scenario deep_copy_stress_test_2)
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 container foo4 [
346   p:num
347   q:&:foo3
348 ]
349 def main [
350   local-scope
351   x:&:num <- new number:type
352   *x <- copy 34
353   a:&:foo1 <- new foo1:type
354   *a <- merge x
355   b:&:foo2 <- new foo2:type
356   *b <- merge a
357   c:&:foo3 <- new foo3:type
358   *c <- merge 1/q, b
359   d:foo4 <- merge 35, c
360   e:foo4 <- deep-copy d
361   f:&:foo3 <- get e, q:offset
362   g:&:foo2, z:bool <- maybe-convert *f, q:variant
363   h:&:foo1 <- get *g, p:offset
364   y:&:num <- get *h, p:offset
365   1:num/raw <- copy *y
366 ]
367 +mem: storing 34 in location 1
368 
369 :(scenario deep_copy_cycles)
370 container foo [
371   p:num
372   q:&:foo
373 ]
374 def main [
375   local-scope
376   x:&:foo <- new foo:type
377   *x <- put *x, p:offset, 34
378   *x <- put *x, q:offset, x  # create a cycle
379   y:&:foo <- deep-copy x
380   1:num/raw <- get *y, p:offset
381   y2:&:foo <- get *y, q:offset
382   stash y [vs] y2
383   2:bool/raw <- equal y, y2  # is it still a cycle?
384   3:bool/raw <- equal x, y  # is it the same cycle?
385 ]
386 +mem: storing 34 in location 1
387 # deep copy also contains a cycle
388 +mem: storing 1 in location 2
389 # but it's a completely different (disjoint) cycle
390 +mem: storing 0 in location 3