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
# To check our support for screens in scenarios, rewrite tests from print.mu

scenario print-character-at-top-left-2 [
  local-scope
  assume-screen 3/width, 2/height
  run [
    a:char <- copy 97/a
    screen <- print screen, a
  ]
  screen-should-contain [
    .a  .
    .   .
  ]
]

scenario clear-line-erases-printed-characters-2 [
  local-scope
  assume-screen 5/width, 3/height
  # print a character
  a:char <- copy 97/a
  screen <- print screen, a
  # move cursor to start of line
  screen <- move-cursor screen, 0/row, 0/column
  run [
    screen <- clear-line screen
  ]
  screen-should-contain [
    .     .
    .     .
    .     .
  ]
]

scenario scroll-screen [
  local-scope
  assume-screen 3/width, 2/height
  run [
    a:char <- copy 97/a
    move-cursor screen, 1/row, 2/column
    screen <- print screen, a
    screen <- print screen, a
  ]
  screen-should-contain [
    .  a.
    .a  .
  ]
]
0" class="LineNr">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