Deepcopy

Deepcopy
You are encouraged to solve this task according to the task description, using any language you may know.

Task

Demonstrate how to copy data structures containing complex heterogeneous and cyclic semantics.

This is often referred to as deep copying, and is normally required where structures are mutable and to ensure that independent copies can be manipulated without side-effects.

If this facility is not built into the language, it is permissible to use functions from a common library, or a coded procedure.

The task should show:

• Relevant semantics of structures, such as their homogeneous or heterogeneous properties, or containment of (self- or mutual-reference) cycles.

• Any limitations of the method.

• That the structure and its copy are different.

• Suitable links to external documentation for common libraries.

6502 Assembly

Deep copying is very simple on the 6502 - just load a value from memory and store it somewhere else.

LDA $00  ;read the byte at memory address $00
STA $20  ;store it at memory address $20

Now, anything you do to the byte at $00 won't affect the byte at $20.

LDA $00      ;read the byte at memory address $00
STA $20      ;store it at memory address $20
INC $00      ;add 1 to the original
CMP $00      ;compare the copy to the original (we could have done LDA $20 first but they're the same value so why bother)
BNE notEqual ;this branch will be taken.

There is no built-in memcpy() function but it doesn't take much effort to create one. This version can copy up to 256 bytes of memory:

;input: 
;$00,$01 = pointer to source       
;$07,$08 = pointer to destination
;X = bytes to copy
;(the memory addresses are arbitrary, but each pair of input addresses MUST be consecutive or this won't work.)
memcpy:
LDY #0
memcpy_again:
lda ($00),y
sta ($07),y
iny
dex
bne memcpy_again
rts

Aime

list L1, L2;

# Lists are heterogeneous:
l_append(L1, 3);
l_append(L1, "deep");

# and may contain self references.
# A self references in the last position:
l_link(L1, -1, L1);

# List may also contain mutual references.
# Create a new list in the last position:
l_n_list(L1, -1);
# Add a reference to the top level list to the nested list:
l_link(l_q_list(L1, -1), -1, L1);

# There are no limitations to the deep copy method:
l_copy(L2, L1);

# Modify the string in the original list,
# via the self reference in the 3rd position
l_r_text(l_q_list(L1, 2), 1, "copy");

# Show the string in the two lists:
o_text(l_query(L2, 1));
o_text(l_query(L1, 1));
o_byte('\n');

# And again, via the included self references:
o_text(l_query(l_query(L2, 2), 1));
o_text(l_query(l_query(L1, 2), 1));
o_byte('\n');

Output:

deepcopy
deepcopy

Arturo

x: #[
    name: "John"
    surname: "Doe"
    age: 34
    hobbies: [
        "Cycling", 
        "History", 
        "Programming", 
        "Languages",
        "Psychology", 
        "Buddhism"
    ]
    sayHello: function [][
        print "Hello there!"
    ]
]

print ["Name of first person:" x\name]

y: new x
y\name: "Jane"

print ["Name of first person:" x\name]
print ["Name of second person:" y\name]

Output:

Name of first person: John 
Name of first person: John 
Name of second person: Jane

AutoHotkey

Works with: AutoHotkey L

http://www.autohotkey.com/board/topic/85201-array-deep-copy-treeview-viewer-and-more/

DeepCopy(Array, Objs=0)
{
    If !Objs
        Objs := Object()
    Obj := Array.Clone() ; produces a shallow copy in that any sub-objects are not cloned
    Objs[&Array] := Obj ; Save this new array - & returns the address of Array in memory
    For Key, Val in Obj
        If (IsObject(Val)) ; If it is a subarray
            Obj[Key] := Objs[&Val] ; If we already know of a reference to this array
            ? Objs[&Val] ; Then point it to the new array (to prevent infinite recursion on self-references
            : DeepCopy(Val,Objs) ; Otherwise, clone this sub-array
    Return Obj
}

AWK

AWK's only data structure is the associative array, and it doesn't allow nested associative arrays (POSIX). Thus:

BEGIN {
    for (elem in original)
        copied[elem] = original[elem]
}

Babel

Any pure Babel object, however complex, can be deep-copied with the cp operator. By contrast, the dup operator makes a shallow copy of any object (duplicates the reference on top-of-stack). In the examples below, the sd utility is the "stack dump" and shows the Babel stack.

Here is an example of shallow-copy - modifying one object modifies both because they are really just references to one underlying object:

babel> [1 2 3] dup dup 0 7 0 1 move sd !
---TOS---
[val 0x7 0x2 0x3 ]
[val 0x7 0x2 0x3 ]
---BOS---

Deep-copy is proved by the ability to separately modify two objects:

babel> clear [1 2 3] dup cp dup 0 7 0 1 move sd !
---TOS---
[val 0x7 0x2 0x3 ]
[val 0x1 0x2 0x3 ]
---BOS---

You can deep-copy any pure-Babel object with cp. Here is a list-of-lists, we copy it using cp:

babel> ((1 2) (3 4) (5 6)) cp
babel> {lsnum !} each
( 1 2 )
( 3 4 )
( 5 6 )

Here is a list-of-maps, we copy it using cp:

babel> ([map "foo" 3 "bar" 17] [map "foo" 4 "bar" 18] [map "foo" 5 "bar" 19] [map "foo" 0 "bar" 20]) cp 
babel> 2 ith "bar" lumap ! itod say !
19

Here is Babel code, we copy it using cp:

babel> { { 1 randlf 100 rem itod << " " << } 20 times } cp
babel> eval
86 51 50 43 82 76 13 78 33 45 11 35 84 25 80 36 33 81 43 24

C

Structures without pointers

Structures without pointers can be copied like standard C variables such as int, float, char etc. The level of nesting is irrelevant. As the following implementation shows, a simple assignment is enough :

#include<stdio.h>

typedef struct{
	int a;
}layer1;

typedef struct{
	layer1 l1;
	float b,c;
}layer2;

typedef struct{
	layer2 l2;
	layer1 l1;
	int d,e;
}layer3;

void showCake(layer3 cake){
	printf("\ncake.d = %d",cake.d);
	printf("\ncake.e = %d",cake.e);
	printf("\ncake.l1.a = %d",cake.l1.a);
	printf("\ncake.l2.b = %f",cake.l2.b);
	printf("\ncake.l2.l1.a = %d",cake.l2.l1.a);
}

int main()
{
	layer3 cake1,cake2;
	
	cake1.d = 1;
	cake1.e = 2;
	cake1.l1.a = 3;
	cake1.l2.b = 4;
	cake1.l2.l1.a = 5;
	
	printf("Cake 1 is : ");
	showCake(cake1);
	
	cake2 = cake1;
	
	cake2.l2.b += cake2.l2.l1.a;
	
	printf("\nCake 2 is : ");
	showCake(cake2);
	
	return 0;
}

Output:

Cake 1 is :
cake.d = 1
cake.e = 2
cake.l1.a = 3
cake.l2.b = 4.000000
cake.l2.l1.a = 5
Cake 2 is :
cake.d = 1
cake.e = 2
cake.l1.a = 3
cake.l2.b = 9.000000
cake.l2.l1.a = 5

Structures with pointers

Structures with pointers which are usually used to represent data structures such as Linked lists, Stacks, Trees, Graphs etc. have to be copied element by element. A simple assignment as in the above example will not be a copy at all. It will be two pointers pointing towards the same memory location.

#include<stdlib.h>
#include<stdio.h>

typedef struct elem{
	int data;
	struct elem* next;
}cell;

typedef cell* list;

void addToList(list *a,int num){
	list temp, holder;
	
	if(*a==NULL){
		*a = (list)malloc(sizeof(cell));
		(*a)->data = num;
		(*a)->next = NULL;
	}
	else{
		temp = *a;
		
		while(temp->next!=NULL)
			temp = temp->next;
		
		holder = (list)malloc(sizeof(cell));
		holder->data = num;
		holder->next = NULL;
		
		temp->next = holder;
	}
}

list copyList(list a){
	list b, tempA, tempB, temp;
	
	if(a!=NULL){
		b = (list)malloc(sizeof(cell));
		b->data = a->data;
		b->next = NULL;
		
		tempA = a->next;
		tempB = b;
		
		while(tempA!=NULL){
			temp = (list)malloc(sizeof(cell));
			temp->data = tempA->data;
			temp->next = NULL;
		
			tempB->next = temp;
			tempB = temp;
		
			tempA = tempA->next;
		}
	}
	
	return b;
}

void printList(list a){
	list temp = a;
	
	while(temp!=NULL){
		printf("%d,",temp->data);
		temp = temp->next;
	}
	printf("\b");
}

int main()
{
	list a,b;
	int i;
	
	for(i=1;i<=5;i++)
		addToList(&a,i);
	
	printf("List a is : ");
	
	printList(a);
	
	b = copyList(a);
	
	free(a);
	
	printf("\nList a destroyed, List b is : ");
	
	printList(b);
	
	return 0;
}

Output:

List a is : 1,2,3,4,5,
List a destroyed, List b is : 1,2,3,4,5,

C#

using System;

namespace prog
{
	class MainClass
	{
		class MyClass : ICloneable
		{
			public MyClass() { f = new int[3]{2,3,5}; c = '1'; }
			
			public object Clone()
			{				
				MyClass cpy = (MyClass) this.MemberwiseClone();
				cpy.f = (int[]) this.f.Clone();			
				return cpy;
			}
			
			public char c;
			public int[] f;
		}
		
		public static void Main( string[] args )
		{
			MyClass c1 = new MyClass();
			MyClass c2 = (MyClass) c1.Clone();
		}
	}
}

C++

In C++ a type defines its own copy semantics. The standard containers copy all of their elements by value including elements that are complex or are themselves containers. However if the container contains pointers, the pointers themselves are copied and will continue to point to the original elements. The example below does not use any pointers.

#include <array>
#include <iostream>
#include <list>
#include <map>
#include <vector>

int main()
{
    // make a nested structure to copy - a map of arrays containing vectors of strings
    auto myNumbers = std::vector<std::string>{"one", "two", "three", "four"};
    auto myColors = std::vector<std::string>{"red", "green", "blue"};
    auto myArray = std::array<std::vector<std::string>, 2>{myNumbers, myColors};
    auto myMap = std::map<int, decltype(myArray)> {{3, myArray}, {7, myArray}};

    // make a deep copy of the map
    auto mapCopy = myMap;

    // modify the copy
    mapCopy[3][0][1] = "2";
    mapCopy[7][1][2] = "purple";
    
    std::cout << "the original values:\n";
    std::cout << myMap[3][0][1] << "\n";
    std::cout << myMap[7][1][2] << "\n\n";

    std::cout << "the modified copy:\n";
    std::cout << mapCopy[3][0][1] << "\n";
    std::cout << mapCopy[7][1][2] << "\n";    
}

Output:

the original values:
two
blue

the modified copy:
2
purple

Common Lisp

Numerous approaches can be demonstrated here. Here is a quick and dirty way to copy circular structure.

Common Lisp has a printed notation which preserves circularity and shared substructure. This way of printing is in effect when the dynamic variable *print-circle* is set true.

We can copy a structure by printing it this way to a string and then reading the resulting string back to data.

The circular notation consists of the two elements #num= obj and #<num>#. For instance #42=(a b) denotes the list (a b) and furthermore, it associates it with the number 42. Then, later in the same form, #42# denotes an additional occurence of the same (a b) object. So for instance, a cons cell whose car is 1, and whose cdr points back to that cons cell is written #1=(1 . #1#).

$ clisp -q
[1]> (setf *print-circle* t)
T
[2]> (let ((a (cons 1 nil))) (setf (cdr a) a)) ;; create circular list
#1=(1 . #1#)
[3]> (read-from-string "#1=(1 . #1#)") ;; read it from a string
#1=(1 . #1#) ;; a similar circular list is returned

Déjà Vu

local :(copy-action) {}

(copy-action)!list obj cache:
	local :new []
	set-to cache obj new
	for i range 0 -- len obj:
		push-to new (deepcopy) @obj! i cache
	return new

(copy-action)!dict obj cache:
	local :new {}
	set-to cache obj new
	for key in keys obj:
		set-to new (deepcopy) @key cache (deepcopy) @obj! @key cache
	return new

labda obj cache:
	set-to cache @obj dup copy @obj
set-default (copy-action)

(deepcopy) obj cache:
	if has cache obj:
		return @cache! @obj
	(copy-action)! type @obj @obj cache

deepcopy obj:
	(deepcopy) obj {}

#example usage:
#a reasonably complicated object:
set :A { :foo [ "bar" ] [] [ & 1 2 & 3 4 ] }
set :B deepcopy A

!. A
!. B

push-to get-from B :foo "HODOR"

!. A
!. B

#it works with cycles:
set :C push-through dup []
set :D deepcopy C

!. C
!. D

push-to C 7

!. C
!. D

Output:

{ :foo [ "bar" ] [ ] [ & 1 2 & 3 4 ] }
{ [ ] [ & 1 2 & 3 4 ] :foo [ "bar" ] }
{ :foo [ "bar" ] [ ] [ & 1 2 & 3 4 ] }
{ [ ] [ & 1 2 & 3 4 ] :foo [ "bar" "HODOR" ] }
[ [ [ [ [...] ] ] ] ]
[ [ [ [ [...] ] ] ] ]
[ [ [ [ [...] 7 ] 7 ] 7 ] 7 ]
[ [ [ [ [...] ] ] ] ]

Delphi

Library: System.TypInfo

program DeepCopyApp;

{$APPTYPE CONSOLE}

uses
  System.TypInfo;

type
  TTypeA = record
    value1: integer;
    value2: char;
    value3: string[10];
    value4: Boolean;
    function DeepCopy: TTypeA;
  end;

{ TTypeA }

function TTypeA.DeepCopy: TTypeA;
begin
  CopyRecord(@result, @self, TypeInfo(TTypeA));
end;

var
  a, b: TTypeA;

begin
  a.value1 := 10;
  a.value2 := 'A';
  a.value3 := 'OK';
  a.value4 := True;

  b := a.DeepCopy;
  a.value1 := 20;
  a.value2 := 'B';
  a.value3 := 'NOK';
  a.value4 := False;

  Writeln('Value of "a":');
  Writeln(a.value1);
  Writeln(a.value2);
  Writeln(a.value3);
  Writeln(a.value4);

  Writeln(#10'Value of "b":');
  Writeln(b.value1);
  Writeln(b.value2);
  Writeln(b.value3);
  Writeln(b.value4);
  readln;
end.

Output:

Value of "a":
20
B
NOK
FALSE

Value of "b":
10
A
OK
TRUE

E

In E, serialization is generalized to transforming object graphs from one representation to another. Deep copying, therefore, consists of transforming a live object graph into a live object graph, by connecting deSubgraphKit's output to its input. No intermediate serialized form is needed.

def deSubgraphKit := <elib:serial.deSubgraphKit>
def deepcopy(x) {
  return deSubgraphKit.recognize(x, deSubgraphKit.makeBuilder())
}

As befits a serialization system, this deep copy may operate on any serializable structure, whether standard or user-defined, and the structure may contain cycles.

? def x := ["a" => 1, "b" => [x].diverge()]
# value: ["a" => 1, "b" => [<***CYCLE***>].diverge()]

? def y := deepcopy(x)
# value: ["a" => 1, "b" => [<***CYCLE***>].diverge()]

? y["b"].push(2)

? y
# value: ["a" => 1, "b" => [<***CYCLE***>, 2].diverge()]

? x
# value: ["a" => 1, "b" => [<***CYCLE***>].diverge()]

? y["b"][0] == y
# value: true

? y["b"][0] == x
# value: false

? x["b"][0] == x
# value: true

(.diverge() produces mutable data structures, and <***CYCLE***> is what is printed when printing some object meets itself again.)

See also: Polymorphic copy#E

Erlang

All values in Erlang are immutable and garbage collected, so copying is meaningless. Moreover, it's impossible to create cyclic data structures in Erlang, due to the absence of a let rec construct (and the fact that all values are immutable).

Data is copied when sent from one Erlang (lightweight) processes to another, because each process manages it's own memory. This is an implementation detail and is not part of the language semantics.

An exception is "large binaries", which can be shared between Erlang processes, and sub-binaries which can reference larger binaries. These can be copied using binary:copy/1 to free the memory of the referenced larger binary if it has no other references. This function is provided with a note in the reference manual indicating that this is usually not what you want. Here is an example though:

Output:

1> A = <<"abcdefghijklmnopqrstuvwxyz">>.
<<"abcdefghijklmnopqrstuvwxyz">>
2> B = <<A/binary, A/binary, A/binary, A/binary>>.
<<"abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz">>
3> <<_:10/binary, C:80/binary, _/binary>> = B.
<<"abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz">>
4> C.
<<"klmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijkl">>
5> byte_size(C).
80
6> binary:referenced_byte_size(C).
104
7> C2 = binary:copy(C).
<<"klmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijkl">>
8> C2 == C.
true
9> binary:referenced_byte_size(C2).
80

Factor

It's possible to create deep copies with [ clone ] deep-map, though this suffers from the limitation that it will hang indefinitely on circularities. We can even do this with tuples, since named tuples allow tuples to be treated like arrays. The following is a demonstration of deep copying an object in this manner.

Works with: Factor version 0.99 2019-10-06

USING: accessors arrays io kernel named-tuples prettyprint
sequences sequences.deep ;

! Define a simple class
TUPLE: foo bar baz ;

! Allow instances of foo to be modified like an array
INSTANCE: foo named-tuple

! Create a foo object composed of mutable objects
V{ 1 2 3 } V{ 4 5 6 } [ clone ] bi@ foo boa

! create a copy of the reference to the object
dup 

! create a deep copy from this copy
>array [ clone ] deep-map T{ foo } like

! print them both
"Before modification:" print [ [ . ] bi@ ] 2keep nl

! modify the deep copy
[ -1 suffix! ] change-bar

! print them both again
"After modification:" print [ . ] bi@

Output:

Before modification:
T{ foo { bar V{ 1 2 3 } } { baz V{ 4 5 6 } } }
T{ foo { bar V{ 1 2 3 } } { baz V{ 4 5 6 } } }

After modification:
T{ foo { bar V{ 1 2 3 } } { baz V{ 4 5 6 } } }
T{ foo { bar V{ 1 2 3 -1 } } { baz V{ 4 5 6 } } }

Another way to make deep copies is by serializing an object to a byte array and then deserializing it back to an object. This has the advantage of preserving circularities, but it doesn't work on non-serializable objects (such as continuations).

! Create a foo object composed of mutable objects
V{ 1 2 3 } V{ 4 5 6 } [ clone ] bi@ foo boa

! create a copy of the reference to the object
dup

! create a deep copy from this copy
object>bytes bytes>object

! print them both
"Before modification:" print [ [ . ] bi@ ] 2keep nl

! modify the deep copy
[ -99 suffix! ] change-bar

"After modification:" print [ . ] bi@

Output:

Before modification:
T{ foo { bar V{ 1 2 3 } } { baz V{ 4 5 6 } } }
T{ foo { bar V{ 1 2 3 } } { baz V{ 4 5 6 } } }

After modification:
T{ foo { bar V{ 1 2 3 } } { baz V{ 4 5 6 } } }
T{ foo { bar V{ 1 2 3 -99 } } { baz V{ 4 5 6 } } }

FreeBASIC

Translation of: PureBasic

Type DeepCopy
    value1 As Integer
    value2 As String * 1
    value3 As String
    value4 As Boolean
    value5 As Double
End Type
Dim As DeepCopy a, b

a.value1 = 10
a.value2 = "A"
a.value3 = "OK"
a.value4 = True
a.value5 = 1.985766472453666

b = a
a.value1 = 20
a.value2 = "B"
a.value3 = "NOK"
a.value4 = False
a.value5 = 3.148556644245367

Print !"Valor de \"a\":"
Print a.value1
Print a.value2
Print a.value3
Print a.value4
Print a.value5

Print !"\nValor \"b\":"
With b
    Print .value1
    Print .value2
    Print .value3
    Print .value4
    Print .value5
End With
Sleep

Output:

Valor de "a":
 20
B
NOK
false
 3.148556644245367

Valor de "b":
 10
A
OK
true
 1.985766472453666

FutureBasic

Translation of FreeBasic

include "NSLog.incl"

begin record DeepCopy
  NSInteger   value1
  CFStringRef value2
  CFStringRef value3
  Boolean     value4
  double      value5
end record

local fn DoDeepCopy
  DeepCopy a, b
  
  a.value1 = 10
  a.value2 = @"A"
  a.value3 = @"Okay"
  a.value4 = YES
  a.value5 = 1.985766472453666
  
  b = a
  b.value1 = 20
  b.value2 = @"B"
  b.value3 = @"Not Okay"
  b.value4 = NO
  b.value5 = 3.148556644245367
  
  NSLog( @"\nValue of 'a':" )
  NSLog( @"a.value1: %ld",   a.value1 )
  NSLog( @"a.value2: %@",    a.value2 )
  NSLog( @"a.value3: %@%",   a.value3 )
  NSLog( @"b.value4: %@",    fn BoolString( a.value4 ) )
  NSLog( @"a.value5: %.15f", a.value5 )
  
  NSLog( @"\nValue of 'b':" )
  NSLog( @"b.value1: %ld",   b.value1 )
  NSLog( @"b.value2: %@",    b.value2 )
  NSLog( @"b.value3: %@%",   b.value3 )
  NSLog( @"b.value4: %@",    fn BoolString( b.value4 ) )
  NSLog( @"b.value5: %.15f", b.value5 )
end fn

fn DoDeepCopy

HandleEvents

Output:

Value of 'a':
a.value1: 10
a.value2: A
a.value3: Okay
b.value4: YES
a.value5: 1.985766472453666

Value of 'b':
b.value1: 20
b.value2: B
b.value3: Not Okay
b.value4: NO
b.value5: 3.148556644245367

Go

Go does not have direct support for deep copy. To make deep copies of specific data structures, it is most efficient to write your own copy function and just copy what needs to be copied.

Heterogeneous:

package main

import "fmt"

// a complex data structure
type cds struct {
    i int            // no special handling needed for deep copy
    s string         // no special handling
    b []byte         // copied easily with append function
    m map[int]bool   // deep copy requires looping
}

// a method
func (c cds) deepcopy() *cds {
    // copy what you can in one line
    r := &cds{c.i, c.s, append([]byte{}, c.b...), make(map[int]bool)}
    // populate map with a loop
    for k, v := range c.m {
        r.m[k] = v
    }
    return r
}

// demo
func main() {
    // create and populate a structure 
    c1 := &cds{1, "one", []byte("unit"), map[int]bool{1: true}}
    fmt.Println(c1)      // show it
    c2 := c1.deepcopy()  // copy it
    fmt.Println(c2)      // show copy
    c1.i = 0             // change original
    c1.s = "nil"
    copy(c1.b, "zero")
    c1.m[1] = false
    fmt.Println(c1)      // show changes
    fmt.Println(c2)      // show copy unaffected
}

Output:

&{1 one [117 110 105 116] map[1:true]}
&{1 one [117 110 105 116] map[1:true]}
&{0 nil [122 101 114 111] map[1:false]}
&{1 one [117 110 105 116] map[1:true]}

Cyclic:

DIY here requires you to code a traversal algorithm.

package main

import "fmt"

// a type that allows cyclic structures
type node []*node

// recursively print the contents of a node
func (n *node) list() {
    if n == nil {
        fmt.Println(n)
        return
    }
    listed := map[*node]bool{nil: true}
    var r func(*node)
    r = func(n *node) {
        listed[n] = true
        fmt.Printf("%p -> %v\n", n, *n)
        for _, m := range *n {
            if !listed[m] {
                r(m)
            }
        }
    }
    r(n)
}

// construct a deep copy of a node
func (n *node) ccopy() *node {
    if n == nil {
        return n
    }
    cc := map[*node]*node{nil: nil}
    var r func(*node) *node
    r = func(n *node) *node {
        c := make(node, len(*n))
        cc[n] = &c
        for i, m := range *n {
            d, ok := cc[m]
            if !ok {
                d = r(m)
            }
            c[i] = d
        }
        return &c
    }
    return r(n)
}

func main() {
    a := node{nil}
    c := &node{&node{&a}}
    a[0] = c
    c.list()
    cc := c.ccopy()
    fmt.Println("copy:")
    cc.list()
    fmt.Println("original:")
    c.list()
}

Output:

0xc42000a4a0 -> [0xc42000a4c0]
0xc42000a4c0 -> [0xc42000a480]
0xc42000a480 -> [0xc42000a4a0]
copy:
0xc42000a580 -> [0xc42000a5a0]
0xc42000a5a0 -> [0xc42000a5c0]
0xc42000a5c0 -> [0xc42000a580]
original:
0xc42000a4a0 -> [0xc42000a4c0]
0xc42000a4c0 -> [0xc42000a480]
0xc42000a480 -> [0xc42000a4a0]

General heterogeneous:

If you still want a generalized deep copy, one can be cobbled with an os.Pipe and the gob package, which does type safe serialization. The deepcopy function shown below works on arbitrary data with a few limitations. It handles data types with recursive or cyclic definitions, but does not handle cycles in the data itself. For example, it handles a linked list, but not a ring data structure. Another limitation is that struct fields must be exported. (That is, fields must start with an upper case letter. This makes the field visible outside the package.)

package main

import (
    "encoding/gob"
    "fmt"
    "os"
)

// capability requested by task
func deepcopy(dst, src interface{}) error {
    r, w, err := os.Pipe()
    if err != nil {
        return err
    }
    enc := gob.NewEncoder(w)
    err = enc.Encode(src)
    if err != nil {
        return err
    }
    dec := gob.NewDecoder(r)
    return dec.Decode(dst)
}

// define linked list type, an example of a recursive type
type link struct {
    Value string
    Next  *link
}

// method satisfies stringer interface for fmt.Println
func (l *link) String() string {
    if l == nil {
        return "nil"
    }
    s := "(" + l.Value
    for l = l.Next; l != nil; l = l.Next {
        s += " " + l.Value
    }
    return s + ")"
}

func main() {
    // create a linked list with two elements
    l1 := &link{"a", &link{Value: "b"}}
    // print original
    fmt.Println(l1)
    // declare a variable to hold deep copy
    var l2 *link
    // copy
    if err := deepcopy(&l2, l1); err != nil {
        fmt.Println(err)
        return
    }
    // print copy
    fmt.Println(l2)
    // now change contents of original list
    l1.Value, l1.Next.Value = "c", "d"
    // show that it is changed
    fmt.Println(l1)
    // show that copy is unaffected
    fmt.Println(l2)
}

Output:

(a b)
(a b)
(c d)
(a b)

Icon and Unicon

Unicon and Icon support heterogeneous structures with loops. The Unicon book has an example of a simple algorithm for producing a deep copy of a structured value (set, list, table, or record); however, that code did not handle graph structures that are not trees. The code for deepcopy below from Unilib is a modification that addresses loops.

The code requires modification to run under Icon as Unicon extended key(X) to operate on lists and records not just tables.

procedure deepcopy(A, cache)  #: return a deepcopy of A
    local k

    /cache := table()        # used to handle multireferenced objects
    if \cache[A] then return cache[A]

    case type(A) of {
        "table"|"list": {
            cache[A] := copy(A)
            every cache[A][k := key(A)] := deepcopy(A[k], cache)
            }
        "set": {
            cache[A] := set()
            every insert(cache[A], deepcopy(!A, cache))
            }
        default: {           # records and objects (encoded as records)
            cache[A] := copy(A)
            if match("record ",image(A)) then {
                every cache[A][k := key(A)] := deepcopy(A[k], cache)
                }
            }
        }
    return .cache[A]
end

The following code demonstrates deepcopy usage and that the resulting structure is different from the original by comparing assignment, copy, and deepcopy.

link printf,ximage

procedure main()

   knot    := makeknot()     # create a structure with loops
   knota   := knot           # copy by assignment (reference)
   knotc   := copy(knot)     # built-in copy (shallow)
   knotdc  := deepcopy(knot) # deep copy

    
   showdeep("knota  (assignment) vs. knot",knota,knot) 
   showdeep("knotc  (copy)  vs. knot",knotc,knot) 
   showdeep("knotdc (deepcopy)  vs. knot",knotdc,knot) 

   xdump("knot   (original)",knot)
   xdump("knota  (assignment)",knota)
   xdump("knotc  (copy)",knotc)
   xdump("knotdc (deepcopy)",knotdc)
end

record rec1(a,b,c)      # record for example

class Class1(a1,a2)     # class - looks like a record under the covers
   method one()
      self.a1 := 1
      return
   end
initially  
   self.a1 := 0
end


procedure makeknot()    #: return a homogeneous structure with loops
   L := [9,8,7]
   T := table()
   T["a"] := 1
   R := rec1(T)
   S := set(R)
   C := Class1()
   C.one()
   T["knot"] := [L,R,S,C]
   put(L,R,S,T,C)
   return L
end

procedure showdeep(tag,XC,X)    #: demo to show (non-)equivalence of list elements
   printf("Analysis of copy depth for %s:\n",tag)
   showequiv(XC,X)
   every showequiv(XC[i := 1 to *X],X[i])
end

procedure showequiv(x,y)       #: show (non-)equivalence of two values
   return printf("   %i %s %i\n",x,if x === y then "===" else "~===",y)
end

Library: Unicon Code Library

DeepCopy.icn

Library: Icon Programming Library

printf.icn provides printf ximage.icn provides xdump

The sample of output below compares all elements of a copy of a structure against the original. Immutable types like numbers, strings, and csets will show as the same (i.e. ===) and different mutable types will show as not the same (i.e. ~===). This clearly shows the difference between assignment, copy, and deepcopy.

Analysis of copy depth for knota  (assignment) vs. knot:
   list_11(7) === list_11(7)
   9 === 9
   8 === 8
   7 === 7
   record rec1_2(3) === record rec1_2(3)
   set_2(1) === set_2(1)
   table_2(2) === table_2(2)
   record Class1__state_2(4) === record Class1__state_2(4)
Analysis of copy depth for knotc  (copy)  vs. knot:
   list_13(7) ~=== list_11(7)
   9 === 9
   8 === 8
   7 === 7
   record rec1_2(3) === record rec1_2(3)
   set_2(1) === set_2(1)
   table_2(2) === table_2(2)
   record Class1__state_2(4) === record Class1__state_2(4)
Analysis of copy depth for knotdc (deepcopy)  vs. knot:
   list_14(7) ~=== list_11(7)
   9 === 9
   8 === 8
   7 === 7
   record rec1_3(3) ~=== record rec1_2(3)
   set_3(1) ~=== set_2(1)
   table_4(2) ~=== table_2(2)
   record Class1__state_3(4) ~=== record Class1__state_2(4)
...

Another way to show the difference in the structures is to use the xdump procedure will produce the following in stderr (&errout):

knot   (original)"
L11 := list(7)
   L11[1] := 9
   L11[2] := 8
   L11[3] := 7
   L11[4] := R_rec1_2 := rec1()
      R_rec1_2.a := T2 := table(&null)
         T2["a"] := 1
         T2["knot"] := L12 := list(4)
            L12[1] := L11
            L12[2] := R_rec1_2
            L12[3] := S2 := set()
               insert(S2,R_rec1_2)
            L12[4] := R_Class1__state_2 := Class1__state()
               R_Class1__state_2.a1 := 1
   L11[5] := S2
   L11[6] := T2
   L11[7] := R_Class1__state_2
...

Insitux

It is impossible to have cyclical structures in Insitux, and values are immutable.

> (var x [1 2 [3 4]])
[1 2 [3 4]]

> (var y x)
[1 2 [3 4]]

> (var x "something else")
something else

> y
[1 2 [3 4]]

J

J uses pass by value semantics (typically implemented as copy on write) so Deepcopy is trivial -- values inside the language are immutable.

   a=:b=: 2 2 2 2 2  NB. two copies of the same array
   b=: 3 (2)} b  NB. modify one of the arrays
   b
2 2 3 2 2
   a
2 2 2 2 2

That said, J can reference values outside the language. But Deepcopy of those values is, by definition, outside the scope of the language. Usually, bringing the values into the language is sufficient.

Another possible exception would be classes and objects (which are not values but collections of references to values). But as a general rule copying of an object should be delegated to the object itself rather than imposed from the outside. Also, "deepcopy" violates the Law of Demeter as well as the concept of black-box reuse -- if you need deepcopy in J, you probably should not be representing your data structure as objects.

Java

Deep copy can be performed several ways.

1. Immutable Objects. Do not perform the deep copy, use immutable objects. If an object is immutable, and hence unchangeable, then a deep copy is not needed. However, this task is about deep copy, so we will continue with the demonstration.
2. Copy Constructor. Use a copy constructor to make a duplicate of the object. This is not a feature of Java, but a design pattern.
3. Object Serialization. Java supports serialization of an object to a byte stream using the Serializable interface. However, there are security concerns with this methodology. See the various Internet articles.
4. Object Clone. Java supports cloning of an object using the Cloneable interface. As with serialization, there are security concerns with this methodology. See the various Internet articles.

Copy constructor, object serialization, and object clone are demonstrated below.

import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;

public class DeepCopy {

    public static void main(String[] args) {
        Person p1 = new Person("Clark", "Kent", new Address("1 World Center", "Metropolis", "NY", "010101"));
        Person p2 = p1;
        
        System.out.printf("Demonstrate shallow copy.  Both are the same object.%n");
        System.out.printf("Person p1 = %s%n", p1);
        System.out.printf("Person p2 = %s%n", p2);
        System.out.printf("Set city on person 2.  City on both objects is changed.%n");
        p2.getAddress().setCity("New York");
        System.out.printf("Person p1 = %s%n", p1);
        System.out.printf("Person p2 = %s%n", p2);
        
        p1 = new Person("Clark", "Kent", new Address("1 World Center", "Metropolis", "NY", "010101"));
        p2 = new Person(p1);
        System.out.printf("%nDemonstrate copy constructor.  Object p2 is a deep copy of p1.%n");
        System.out.printf("Person p1 = %s%n", p1);
        System.out.printf("Person p2 = %s%n", p2);
        System.out.printf("Set city on person 2.  City on objects is different.%n");
        p2.getAddress().setCity("New York");
        System.out.printf("Person p1 = %s%n", p1);
        System.out.printf("Person p2 = %s%n", p2);

        p2 = (Person) deepCopy(p1);
        System.out.printf("%nDemonstrate serialization.  Object p2 is a deep copy of p1.%n");
        System.out.printf("Person p1 = %s%n", p1);
        System.out.printf("Person p2 = %s%n", p2);
        System.out.printf("Set city on person 2.  City on objects is different.%n");
        p2.getAddress().setCity("New York");
        System.out.printf("Person p1 = %s%n", p1);
        System.out.printf("Person p2 = %s%n", p2);
        
        p2 = (Person) p1.clone();
        System.out.printf("%nDemonstrate cloning.  Object p2 is a deep copy of p1.%n");
        System.out.printf("Person p1 = %s%n", p1);
        System.out.printf("Person p2 = %s%n", p2);
        System.out.printf("Set city on person 2.  City on objects is different.%n");
        p2.getAddress().setCity("New York");
        System.out.printf("Person p1 = %s%n", p1);
        System.out.printf("Person p2 = %s%n", p2);
    }

    /**
     * Makes a deep copy of any Java object that is passed.
     */
    private static Object deepCopy(Object object) {
        try {
            ByteArrayOutputStream outputStream = new ByteArrayOutputStream();
            ObjectOutputStream outputStrm = new ObjectOutputStream(outputStream);
            outputStrm.writeObject(object);
            ByteArrayInputStream inputStream = new ByteArrayInputStream(outputStream.toByteArray());
            ObjectInputStream objInputStream = new ObjectInputStream(inputStream);
            return objInputStream.readObject();
        }
        catch (Exception e) {
            e.printStackTrace();
            return null;
        }
    }
    
    public static class Address implements Serializable, Cloneable {

        private static final long serialVersionUID = -7073778041809445593L;

        private String street;
        private String city;
        private String state;
        private String postalCode;
        public String getStreet() {
            return street;
        }
        public String getCity() {
            return city;
        }
        public void setCity(String city) {
            this.city = city;
        }
        public String getState() {
            return state;
        }
        public String getPostalCode() {
            return postalCode;
        }
        
        @Override
        public String toString() {
            return "[street=" + street + ", city=" + city + ", state=" + state + ", code=" + postalCode + "]";
        }
        
        public Address(String s, String c, String st, String p) {
            street = s;
            city = c;
            state = st;
            postalCode = p;
        }
        
        //  Copy constructor
        public Address(Address add) {
            street    = add.street;
            city       = add.city;
            state      = add.state;
            postalCode = add.postalCode;
        }
        
        //  Support Cloneable
        @Override
        public Object clone() {
            return new Address(this);
        }
        
    }
    
    public static class Person implements Serializable, Cloneable {
        private static final long serialVersionUID = -521810583786595050L;
        private String firstName;
        private String lastName;
        private Address address;
        public String getFirstName() {
            return firstName;
        }
        public String getLastName() {
            return lastName;
        }
        public Address getAddress() {
            return address;
        }

        @Override
        public String toString() {
            return "[first name=" + firstName + ", last name=" + lastName + ", address=" + address + "]";
        }

        public Person(String fn, String ln, Address add) {
            firstName = fn;
            lastName = ln;
            address = add;
        }
        
        //  Copy Constructor
        public Person(Person person) {
            firstName = person.firstName;
            lastName = person.lastName;
            address = new Address(person.address);  //  Invoke copy constructor of mutable sub-objects.
        }
        
        //  Support Cloneable
        @Override
        public Object clone() {
            return new Person(this);
        }
    }
}

Output:

Demonstrate shallow copy.  Both are the same object.
Person p1 = [first name=Clark, last name=Kent, address=[street=1 World Center, city=Metropolis, state=NY, code=010101]]
Person p2 = [first name=Clark, last name=Kent, address=[street=1 World Center, city=Metropolis, state=NY, code=010101]]
Set city on person 2.  City on both objects is changed.
Person p1 = [first name=Clark, last name=Kent, address=[street=1 World Center, city=New York, state=NY, code=010101]]
Person p2 = [first name=Clark, last name=Kent, address=[street=1 World Center, city=New York, state=NY, code=010101]]

Demonstrate copy constructor.  Object p2 is a deep copy of p1.
Person p1 = [first name=Clark, last name=Kent, address=[street=1 World Center, city=Metropolis, state=NY, code=010101]]
Person p2 = [first name=Clark, last name=Kent, address=[street=1 World Center, city=Metropolis, state=NY, code=010101]]
Set city on person 2.  City on objects is different.
Person p1 = [first name=Clark, last name=Kent, address=[street=1 World Center, city=Metropolis, state=NY, code=010101]]
Person p2 = [first name=Clark, last name=Kent, address=[street=1 World Center, city=New York, state=NY, code=010101]]

Demonstrate serialization.  Object p2 is a deep copy of p1.
Person p1 = [first name=Clark, last name=Kent, address=[street=1 World Center, city=Metropolis, state=NY, code=010101]]
Person p2 = [first name=Clark, last name=Kent, address=[street=1 World Center, city=Metropolis, state=NY, code=010101]]
Set city on person 2.  City on objects is different.
Person p1 = [first name=Clark, last name=Kent, address=[street=1 World Center, city=Metropolis, state=NY, code=010101]]
Person p2 = [first name=Clark, last name=Kent, address=[street=1 World Center, city=New York, state=NY, code=010101]]

Demonstrate cloning.  Object p2 is a deep copy of p1.
Person p1 = [first name=Clark, last name=Kent, address=[street=1 World Center, city=Metropolis, state=NY, code=010101]]
Person p2 = [first name=Clark, last name=Kent, address=[street=1 World Center, city=Metropolis, state=NY, code=010101]]
Set city on person 2.  City on objects is different.
Person p1 = [first name=Clark, last name=Kent, address=[street=1 World Center, city=Metropolis, state=NY, code=010101]]
Person p2 = [first name=Clark, last name=Kent, address=[street=1 World Center, city=New York, state=NY, code=010101]]

JavaScript

You can use JSON for ordinary objects.

var deepcopy = function(o){
  return JSON.parse(JSON.stringify(src));
};

var src = {foo:0,bar:[0,1]};
print(JSON.stringify(src));
var dst = deepcopy(src);
print(JSON.stringify(src));

You can go further if you have uneval(). You can even deep copy objects with cyclic references.

var deepcopy = function(o){
  return eval(uneval(o));
};
var src = {foo:0,bar:[0,1]};
src['baz'] = src;
print(uneval(src));
var dst = deepcopy(src);
print(uneval(src));

jq

The distinction between "deep" and "shallow" copying is as irrelevant in a jq program as in elementary arithmetic. There is only one "equality" operator in jq and it is defined in terms of equality of values.

In jq, a variable is merely a reference to a value, so in the pipeline:

[1,2] | . as $x | . as $y

both $x and $y are simply references to [1,2]. The same applies to function parameters.

jq's data values are JSON values, and in particular there are no pointers, and there is no way to create self-referential data structures as is possible, for example, in JavaScript. In JavaScript, the following pair of assignments would create a self-referential array:

x=[1,2]; x[0]=x;                     // javascript

In jq, the superficially similar sequence:

[1,2] as $x | ($x|setpath([0];$x))   # jq

merely emits [[1,2], 2].

Julia

# v0.6.0

cp = deepcopy(obj)

Kotlin

The JDK has an Object.clone() method but it only produces a 'shallow' copy.

If a 'deep' copy is needed, then usually a custom method would be written.

However, an easy way to produce a deep copy for any object, including one which contains cyclic or null references, is to serialize it to memory and then deserialize it back to a new object. A drawback is that the class of the object to be serialized needs to be marked as implementing the Serializable interface (albeit it contains no members).

The serialization approach is used below.

// Version 1.2.31

import java.io.Serializable
import java.io.ByteArrayOutputStream
import java.io.ByteArrayInputStream
import java.io.ObjectOutputStream
import java.io.ObjectInputStream

fun <T : Serializable> deepCopy(obj: T?): T? {
    if (obj == null) return null
    val baos = ByteArrayOutputStream()
    val oos  = ObjectOutputStream(baos)
    oos.writeObject(obj)
    oos.close()
    val bais = ByteArrayInputStream(baos.toByteArray())
    val ois  = ObjectInputStream(bais)
    @Suppress("unchecked_cast")
    return ois.readObject() as T
} 

class Person(
    val name: String,
    var age: Int,
    val sex: Char,
    var income: Double,
    var partner: Person?
) : Serializable

fun printDetails(p1: Person, p2: Person?, p3: Person, p4: Person?) {
    with (p3) {
        println("Name    : $name")
        println("Age     : $age")
        println("Sex     : $sex")
        println("Income  : $income")
        if (p4 == null) {
            println("Partner : None")
        }
        else {
            println("Partner :-")
            with (p4) {
                println("  Name   : $name")
                println("  Age    : $age")
                println("  Sex    : $sex")
                println("  Income : $income")
            }
        }
        println("\nSame person as original '$name' == ${p1 === p3}")
        if (p4 != null) {
            println("Same person as original '${p2!!.name}' == ${p2 === p4}")
        }
    }
    println()
}

fun main(args: Array<String>) {
    var p1 = Person("John", 35, 'M', 50000.0, null)
    val p2 = Person("Jane", 32, 'F', 25000.0, p1)
    p1.partner = p2
    var p3 = deepCopy(p1)
    val p4 = p3!!.partner
    printDetails(p1, p2, p3, p4)

    println("..or, say, after 2 years have elapsed:-\n")
    with (p1) {
        age = 37
        income = 55000.0
        partner = null
    }
    p3 = deepCopy(p1)
    printDetails(p1, null, p3!!, null)
}

Output:

Name    : John
Age     : 35
Sex     : M
Income  : 50000.0
Partner :-
  Name   : Jane
  Age    : 32
  Sex    : F
  Income : 25000.0

Same person as original 'John' == false
Same person as original 'Jane' == false

..or, say, after 2 years have elapsed:-

Name    : John
Age     : 37
Sex     : M
Income  : 55000.0
Partner : None

Same person as original 'John' == false

Lasso

Every Lasso type has an ascopy and ascopydeep method.

local(copy) = #myobject->ascopydeep

Lingo

-- Supports lists, property lists, images, script instances and scalar values (integer, float, string, symbol).
on deepcopy (var, cycleCheck)   
  case ilk(var) of
  #list, #propList, #image: 
    return var.duplicate()
  #instance:
    if string(var) starts "<Xtra " then return var -- deep copy makes no sense for Xtra instances
    if voidP(cycleCheck) then cycleCheck = [:]
    if not voidP(cycleCheck[var]) then return cycleCheck[var]
    copy = var.script.rawNew()
    cycleCheck[var] = copy
    repeat with i = 1 to var.count
      copy.setProp(var.getPropAt(i), deepcopy(var[i], cycleCheck))
    end repeat
    return copy
  otherwise: 
    return var
  end case
end

val = [#foo:42, "bar":[1,2,3, "Hello world!"]]
put deepcopy(val)
-- [#foo: 42, "bar": [1, 2, 3, "Hello world!"]]

val = script("MyClass").new()
val.foo = 42
val.bar = [1, 2, 3, "Hello world!"]]
copy = deepcopy(val)

Lua

These are simple functions which illustrate the possibility to use tables as table keys in Lua. More robust implementation, such as this, would also deep-copy metatables, function upvalues, etc.

Recursive

function _deepcopy(o, tables)
 
  if type(o) ~= 'table' then
    return o
  end
 
  if tables[o] ~= nil then
    return tables[o]
  end
 
  local new_o = {}
  tables[o] = new_o
 
  for k, v in next, o, nil do
    local new_k = _deepcopy(k, tables)
    local new_v = _deepcopy(v, tables)
    new_o[new_k] = new_v
  end
 
  return new_o
end
 
function deepcopy(o)
  return _deepcopy(o, {})
end

Output:

> a = {'beans', 'sausage', 'eggs', {table='wood', fork='silver', dish='china'}}
> aa = deepcopy(a)
> 
> a   
table: 0x55ef852b8390
> aa
table: 0x55ef852b4e50
> 
> aa[2]
sausage
> aa[2] = 'bacon'
> aa[2]
bacon
> a[2]
sausage
> 
> a[4]
table: 0x55ef852b8880
> aa[4]
table: 0x55ef8528d6d0
> aa[4].dish 
china

Works with self-referencing / cyclic tables as well:

> z = {}
> z[1] = {}
> z[1][2] = {}
> z[1][2][3] = z
> zz = deepcopy(z)
> z  
table: 0x557659e84c00
> zz
table: 0x557659e59630
> z[1]
table: 0x557659e85160
> zz[1]
table: 0x557659e596c0
> z[1][2]
table: 0x557659e85790
> zz[1][2]
table: 0x557659e597a0
> z[1][2][3]
table: 0x557659e84c00
> zz[1][2][3]
table: 0x557659e59630

Table keys are also deep-cloned:

> q = {}
> q[q] = q
> qq = deepcopy(q)
> qq[q]
nil
> qq[qq]
table: 0x557659e859f0
> qq[qq] == qq
true

Non-recursive

These functions have a string argument mode (like __mode in a metatable), which determines whether keys, values, both or neither will be deep-copied (defaults to values).

Breadth-first

function deepcopy(o, mode)

  if type(o) ~= 'table' then
    return o
  end

  mode = mode and mode:lower() or 'v'
  local deep_keys   = mode:find('k')
  local deep_values = mode:find('v')

  local new_t = {}
  local stack = {o}
  local tables = {[o] = new_t}

  local function copy(v)
    if type(v) ~= 'table' then
      return v
    end
    if tables[v] == nil then
      tables[v] = {}
      stack[#stack+1] = v
    end
    return tables[v]
  end

  while #stack ~= 0 do
    local t = table.remove(stack)
    local new_t = tables[t]
    
    for k,v in next, t, nil do
      if deep_keys   then k = copy(k) end
      if deep_values then v = copy(v) end
      new_t[k] = v
    end
  end

  return new_t
end

> q = {}
> q[q] = q
> q1 = deepcopy(q)
> q2 = deepcopy(q, 'kv')
> q1[q] == q1
true
> q1[q1] == q1
false
> q2[q2] == q2
true

Depth-first

When the current source table t contains either value (v) or key (k) which is a table, then the source table t is pushed onto stack, together with the current key k. The key/value then becomes the current source table and current key is reset to nil. In other words, the current "context" is saved and replaced by a new one, consisting of the subtable (k or v) and a nil key (nil, because we must start traversing the subtable from the beginning).

If both key k and value v are tables (and mode is "kv"), then an additional value 0 is pushed onto stack to indicate that both key and value must be copied. The key table k is then copied, and after copying it and seeing 0 on top of the stack, the value table v is copied. Then, the context is restored and copying of the parent table continues.

function deepcopy(o, mode)

  if type(o) ~= 'table' then
    return o
  end

  mode = mode and mode:lower() or 'v'
  local deep_keys   = mode:find('k')
  local deep_values = mode:find('v')

  local tables = {[o] = {}} -- list of known tables (to handle circular tables)
  local stack = {o}         -- first table which will be popped from stack is the root table
                            --   and the key must be `nil` because we are at the beginning
                            --   of the root table. since it's `nil`, we don't need to put it
                            --   on the stack - `table.remove()` will by default return `nil`
                            --   when called on an empty table.

  while #stack ~= 0 do
    local t, new_t, k, v = table.remove(stack)  -- assigns only to `t`,
                                                --   other variables are set to `nil`
    if t ~= 0 then
      k = table.remove(stack) -- restore the context

    else  -- we finished copying the key, now copy the value
      t = stack[#stack]    -- get the parent table to retrieve the value from
      k = stack[#stack-1]  -- get saved key
      t = t[k]  -- retrieve the value from the parent table and set it as the current table
      k = nil   -- reset key (start traversing the value table from the beginning)
    end
    new_t = tables[t] -- get the new table from the list of known tables

    if k ~= nil then  -- this is always true except for
                      --  1. when we just popped the root table `o`
                      --  2. when we just finished copying the key table
                      --     and now we have to copy the value table
      local v = t[k]  -- get the original value
                      -- if we want to deep-copy keys, then get its copy from the list
                      --   of known tables. if it's not there, then it isn't a table,
                      --   so keep its original value. same goes for the value.
      if deep_keys   then k = tables[k] or k end
      if deep_values then v = tables[v] or v end
      new_t[k] = v    -- put value into the new table
    end

    k,v = next(t,k) -- in case we have just started traversing the root table `o`, this retrieves
                    --   the first key and value, as well as in case we have just finished copying
                    --   the key table and are now copying the value table. otherwise, it continues
                    --   where we left off when we descended into subtable.

    while k ~= nil do
      -- we need to deep-copy the key/value only if
      --  1. we want to do it (eg. `mode` specifies to deep-copy keys/values), AND
      --  2. it is a table, AND
      --  3. we haven't copied it already (and are not copying it right now)
      local copy_key   = deep_keys   and type(k) == 'table' and not tables[k]
      local copy_value = deep_values and type(v) == 'table' and not tables[v]

      if not copy_key and not copy_value then -- boring stuff
        -- if either `deep_keys` is `nil` (we don't want to deep-copy keys)
        --   or `tables[k]` is `nil` (the key is not a table), then keep the key's original value,
        --   otherwise use the value saved in `tables`. same goes for the value.
        local new_k = deep_keys   and tables[k] or k
        local new_v = deep_values and tables[v] or v
        new_t[new_k] = new_v  -- put the value into the new table

      else -- copy_key or copy_value
        stack[#stack+1] = k -- save current context
        stack[#stack+1] = t

        if copy_key then
          t = k   -- descend into the key table
          if copy_value then
            stack[#stack+1] = 0 -- remember we have to copy the value table as well
            tables[v] = {}      -- create new table for the value beforehand
          end
        else -- copy only the value
          t = v  -- descent into the value table
        end

        new_t = {}        -- create new table
        tables[t] = new_t -- add it to the list of known tables
        k = nil           -- reset the key
      end

      k,v = next(t,k) -- get next key/value (or first, in case we just descended into a subtable)
    end
  end

  return tables[o]  -- return the copy corresponding to the root table `o`
end

Mathematica / Wolfram Language

Everything in Mathematica is a value type.

a = {"foo", \[Pi], {<|
     "deep" -> {# + 
         1 &, {{"Mathematica"}, {{"is"}, {"a"}}, {{{"cool"}}}, \
{{"programming"}, {"language!"}}}}|>}};
b = a;
a[[2]] -= 3;
a[[3, 1, 1, 1]] = #^2 &;
Print[a];
Print[b];

Output:

{foo, -3 + π, {<|deep -> {#1^2 &, {{Mathematica}, {{is}, {a}}, {{{cool}}}, {{programming}, {language!}}}}|>}}
{foo, π, {<|deep -> {#1+1&, {{Mathematica}, {{is}, {a}}, {{{cool}}}, {{programming}, {language!}}}}|>}}

Nim

Works with Nim 1.4.0:

deepCopy(newObj, obj)

For example with binary trees:

type
  Node[T] = ref TNode[T]
  TNode[T] = object
    data: T
    left, right: Node[T]

proc newNode[T](data: T; left, right: Node[T] = nil): Node[T] =
  Node[T](data: data, left: left, right: right)

proc preorder[T](n: Node[T]): seq[T] =
  if n == nil: @[]
  else: @[n.data] & preorder(n.left) & preorder(n.right)

var tree = 1.newNode(
             2.newNode(
               4.newNode(
                 7.newNode),
               5.newNode),
             3.newNode(
               6.newNode(
                 8.newNode,
                 9.newNode)))

var tree2: Node[int]
tree2.deepCopy tree
tree2.data = 10
tree2.left.data = 20
tree2.right.left.data = 90

echo "Tree2:"
echo preorder tree2

echo "Tree:"
echo preorder tree

Output:

Tree2:
@[10, 20, 4, 7, 5, 3, 90, 8, 9]
Tree:
@[1, 2, 4, 7, 5, 3, 6, 8, 9]

OCaml

This code is just provided in order to achieve this task, but an OCaml programmer wouldn't use this kind of code, because this copy function is made generic due to the use of the Obj module, and it is not recommanded to use it.

let rec copy t =
  if Obj.is_int t then t else
    let tag = Obj.tag t in
    if tag = Obj.double_tag then t else
    if tag = Obj.closure_tag then t else
    if tag = Obj.string_tag then Obj.repr (String.copy (Obj.obj t)) else
    if tag = 0 || tag = Obj.double_array_tag then begin
      let size = Obj.size t in
      let r = Obj.new_block tag size in
      for i = 0 to pred size do
        Obj.set_field r i (copy (Obj.field t i))
      done;
      r
    end else failwith "copy" ;;

let copy (v : 'a) : 'a = Obj.obj (copy (Obj.repr v))

OCaml programmers will prefer to use specialised copy functions for each mutable types. For base types like strings and arrays, the standard library provides copy functions: String.copy and Array.copy. For mutable user-defined data structures, we will create a copy function based on these previous copy functions. For example in the module Hashtbl, the type is a record containing an integer and an array, so the copy function is defined as below:

let copy h =
  { size = h.size;
    data = Array.copy h.data }

OxygenBasic

'DEEP COPY FOR A RECURSIVE TREE STRUCTURE

uses console

class branches
  '
  static int count
  int level
  int a,b,c
  branches*branch1
  branches*branch2
  '
  method constructor(int n)
  =========================
    level=n
    count++
    output count tab level cr
    if level>0
      new branches n1(n-1)
      new branches n2(n-1)
      @branch1=@n1
      @branch2=@n2
    endif
    ...
  end method
  '
  method destructor
  =================
    if level>0
      del branch1
      del branch2
    endif
    ...
  end method
  '
  method RecurseCopy(int n, branches *dc, *sc)
  ============================================
    dc.level=sc.level
    dc.a=sc.a
    dc.b=sc.b
    dc.c=sc.c
    if n>0
      RecurseCopy n-1, byval @dc.branch1, byval @sc.branch1
      RecurseCopy n-1, byval @dc.branch2, byval @sc.branch2
    endif
  end method
  '
  method DeepCopy() as branches*
  ==============================
    new branches dc(level)
    RecurseCopy level,dc,this
    return @dc
  end method
  '
end class

output "count" tab "level" tab "(original)" cr
new branches br(3)
output "count" tab "level" tab "(copy)" cr
branches *bc = br.DeepCopy
pause
del bc
del br

PARI/GP

All copies in GP are deep; this is one of its major inefficiencies when working with large objects.

In PARI, this is accomplished with the command gcopy rather than shallowcopy or leafcopy. The function takes and returns a GEN. See section 10.6 of the User's Guide to the PARI Library.

Perl

use Storable; Storable::dclone() is exactly what you are looking for.

#!/usr/bin/perl
use strict;
use warnings;
use Storable;
use Data::Dumper;

my $src = { foo => 0, bar => [0, 1] };
$src->{baz} = $src;
my $dst = Storable::dclone($src);
print Dumper($src);
print Dumper($dst);

Phix

Library: Phix/basics

Handled natively. Phix uses reference counting with copy-on-write semantics; the initial copy is fast even for huge complex and deeply nested structures (copying a single machine-word-sized reference and incrementing a single machine-word-sized reference count), and when a shared object (anything with a refcount>1) is modified, an internal clone of the minimum necessary levels occurs, with all the rest of the structure remaining shared, but obviously still properly protected in the same way.

object a, b
    a = {1,{2,3},"four",{5.6,7,{8.9}}}
    b = a
    b[3] = 4
?a
?b

Output:

{1,{2,3},"four",{5.6,7,{8.9}}}
{1,{2,3},4,{5.6,7,{8.9}}}

It is worth noting that this mechanism is also used for parameter passing, and when a local variable is both passed as a parameter and assigned on return, automatic pass-by-reference handling kicks in to avoid any unnecessary internal cloning.

However, JavaScript has pass-by-sharing semantics, and since 1.0.0 when pwa/p2js (the Phix to JavaScript transpiler) was introduced, a simple "with js" (which works identically to "with javascript_semantics") effectively disables both underlying semantic mechanisms simultaneously, and causes desktop/Phix to raise fatal runtime errors ("p2js violation: relies on copy on write semantics") indicating where a deep_copy() is needed, which is now a builtin (see builtins\repeat.e for the actual) and is a bit like this:

function deep_copy(object o)
object res
    if atom(o) then
        res = o
    else
        res = repeat(' ',length(o))
        for i=1 to length(o) do
            res[i] = deep_copy(o[i])
        end for
    end if
    return res
end function

object c = deep_copy(b)
?c

It is worth pointing out that "with js" and deep_copy() have proved staggeringly effective and nowhere near as painful as first feared. In just a few months (1.0.0 was released in July 2021) I have tested, fixed where necessary, and marked as javascript compatible some 450 rosettacode entries for Phix, and only one tenth of that as incompatible.

Or you could just serialize and deserialize, though it would probably be quite a bit slower:

include builtins\serialize.e
object d = deserialize(serialize(a))
?d

Output:

{1,{2,3},4,{5.6,7,{8.9}}}
{1,{2,3},"four",{5.6,7,{8.9}}}

PHP

PHP provides the clone operator (docs) for shallow copying, and allows you to hook into a magic class method called __clone() in your classes to do some of the lifting to create deeper copies, but this method won't create a true deep copy if you don't write the code to manage it in each of the child classes.

<?php
class Foo
{
    public function __clone()
    {
        $this->child = clone $this->child;
    }
}

$object = new Foo;
$object->some_value = 1;
$object->child = new stdClass;
$object->child->some_value = 1;

$deepcopy = clone $object;
$deepcopy->some_value++;
$deepcopy->child->some_value++;

echo "Object contains {$object->some_value}, child contains {$object->child->some_value}\n",
     "Clone of object contains {$deepcopy->some_value}, child contains {$deepcopy->child->some_value}\n";
?>

Automatically generated deep copies can be created in any situation where your object graph can be serialized (i.e. does not contain any Closures or resources like DB connections or file handles):

<?php

// stdClass is a default PHP object
$object = new stdClass;
$object->some_value = 1;
$object->child = new stdClass;
$object->child->some_value = 1;

$deepcopy = unserialize(serialize($object));
$deepcopy->some_value++;
$deepcopy->child->some_value++;

echo "Object contains {$object->some_value}, child contains {$object->child->some_value}\n",
     "Clone of object contains {$deepcopy->some_value}, child contains {$deepcopy->child->some_value}\n";

PicoLisp

A shallow copy can be done with 'copy'. This function takes care of cons pairs and lists, no matter whether they are cyclic, or end in NIL or some other data structure.

For a known depth, it might be used in combination with other list functions. For example, to copy a non-cyclic structure of depth 2 with 'mapcar':

(mapcar copy List)

Copying non-cyclic structures of arbitrary depth and list-termination could be handled with a custom function (using 'cons'):

(de deepCopy (X)
   (if (atom X)
      X
      (cons (deepCopy (car X)) (deepCopy (cdr X))) ) )

Test:

: (setq A '((a . b) (c d e) f g . e))
-> ((a . b) (c d e) f g . e)

: (setq B (deepCopy A))
-> ((a . b) (c d e) f g . e)

: A
-> ((a . b) (c d e) f g . e)

: B
-> ((a . b) (c d e) f g . e)

: (= A B)
-> T              # A and its copy B are structure-equal
: (== A B)
-> NIL            # but they are not identical (pointer-equal)

: (cadr A)
-> (c d e)

: (cadr B)
-> (c d e)

: (== (cadr A) (cadr B))
-> NIL            # The same holds for sub-structures

For cyclic structures, the above 'deepCopy' function could be extended, to remember already visited structures and their copies in a mark list:

(de deepCopy (X)
   (let Mark NIL
      (recur (X)
         (cond
            ((atom X) X)
            ((asoq X Mark) (cdr @))
            (T
               (prog1 (cons)
                  (push 'Mark (cons X @))
                  (set @ (recurse (car X)))
                  (con @ (recurse (cdr X))) ) ) ) ) ) )

Test:

: (setq A '(a b .)  B (deepCopy A))
-> (a b .)
: A
-> (a b .)
: B
-> (a b .)

: (= A B)
-> T              # A and its copy B are structure-equal

: (== A B)
-> NIL            # but they are not identical (pointer-equal)

PureBasic

Macro PrintStruc(StrucVal)
  PrintN(Str(StrucVal#\value1))
  PrintN(Chr(StrucVal#\value2))
  PrintN(StrucVal#\value3)
  If StrucVal#\value4
    PrintN("TRUE")
  Else
    PrintN("FALSE")
  EndIf  
  PrintN("")  
EndMacro

Structure TTypeA
  value1.i
  value2.c
  value3.s[10]
  value4.b
EndStructure

Define.TTypeA a, b

a\value1=10
a\value2='A'
a\value3="OK"
a\value4=#True

b=a

a\value1=20
a\value2='B'
a\value3="NOK"
a\value4=#False

If OpenConsole("")
  PrintN("Value of 'a':") : PrintStruc(a)
  PrintN("Value of 'b':") : PrintStruc(b)  
  Input()
EndIf

Output:

Value of 'a':
20
B
NOK
FALSE
Value of 'b':
10
A
OK
TRUE

Python

import copy
deepcopy_of_obj = copy.deepcopy(obj)

Racket

Unlike most Lisps, Racket's pairs are immutable, but they still support sharing and cycles using shared (or at the lower level, via make-reader-graph). This would make the implementation a little more complicated, but it's much easier to just dump the structure out and re-read it to get a new copy:

#lang racket

(define (deepcopy x)
  ;; make sure that all sharings are shown
  (parameterize ([print-graph #t]) (read (open-input-string (format "~s" x)))))

(define (try x)
  ;; use the same setting to see that it worked
  (parameterize ([print-graph #t])
    (printf "original: ~s\n" x)
    (printf "deepcopy: ~s\n" (deepcopy x))
    ;; print both also, which shows that they are indeed different
    (printf "both: ~s\n" (list x (deepcopy x)))))
(try (shared ([x (cons 1 x)]) (list x x)))

Output:

original: (#0=(1 . #0#) #0#)
deepcopy: (#0=(1 . #0#) #0#)
both: ((#0=(1 . #0#) #0#) (#1=(1 . #1#) #1#))

Raku

(formerly Perl 6)

Raku doesn't currently provide a proper mechanism for deep copies, but depending on your requirements you could use one of these work-arounds:

1) Use .deepmap(*.clone):

.deepmap constructs a copy of the data structure, and .clone makes a shallow copy of each leaf node. Limitations:

• Hangs indefinitely when given a self-referential data structure.
• Descends only into Iterable collections (like Array/Hash), which means that a Pair or a typical custom object would be considered a leaf node.

my %x = foo => 0, bar => [0, 1];
my %y = %x.deepmap(*.clone);

%x<bar>[1]++;
say %x;
say %y;

Output:

{bar => [0 2], foo => 0}
{bar => [0 1], foo => 0}

2) Use .raku.EVAL:

.raku serializes the data structure to Raku code, and .EVAL deserializes it. Limitations:

• Doesn't work correctly if the data structure contains elements that can't be properly serialized, such as closures or file handles.

my %x = foo => 0, bar => [0, 1];
my %y = %x.raku.EVAL;

%x<bar>[1]++;
say %x;
say %y;

Output:

{bar => [0 2], foo => 0}
{bar => [0 1], foo => 0}

Ruby

Rubyists can hack a deep copy by using the core class Marshal. The intermediate form of Marshal.load(Marshal.dump object) saves the object and any descendant objects.

# _orig_ is a Hash that contains an Array.
orig = { :num => 1, :ary => [2, 3] }
orig[:cycle] = orig	# _orig_ also contains itself.

# _copy_ becomes a deep copy of _orig_.
copy = Marshal.load(Marshal.dump orig)

# These changes to _orig_ never affect _copy_,
# because _orig_ and _copy_ are disjoint structures.
orig[:ary] << 4
orig[:rng] = (5..6)

# Because of deep copy, orig[:ary] and copy[:ary]
# refer to different Arrays.
p orig	# => {:num=>1, :ary=>[2, 3, 4], :cycle=>{...}, :rng=>5..6}
p copy	# => {:num=>1, :ary=>[2, 3], :cycle=>{...}}

# The original contains itself, and the copy contains itself,
# but the original and the copy are not the same object.
p [(orig.equal? orig[:cycle]),
   (copy.equal? copy[:cycle]),
   (not orig.equal? copy)]	# => [true, true, true]

Marshal cannot dump an object that relates to the system (like Dir or IO), relates to the program (like MatchData or Thread), uses an anonymous class or module, or has a singleton method. (ri Marshal.dump documents this restriction.) If Marshal encounters any such object, then the deep copy fails.

Marshal can dump internal objects, but never copies them. The internal objects are nil, false, true and instances of Fixnum or Symbol. For example, Marshal.load(Marshal.dump :sym) returns the original :sym, not a copy.

The internal objects are almost immutable, so there is almost no reason to copy them. Yet, there are esoteric ways to modify them. For example, nil.instance_eval { @i = 1 } would modify nil. A program cannot have another copy of nil to escape such modification. If there was a deep copy of some object that contains nil, then such modification would also affect nil inside such copy.

Rust

This is what the Clone trait exists for although the depth of the copy is arbitrary and up to the type that implements the trait.

// The compiler can automatically implement Clone on structs (assuming all members have implemented Clone).
#[derive(Clone)]
struct Tree<T> {
    left: Leaf<T>,
    data: T,
    right: Leaf<T>,
}

type Leaf<T> = Option<Box<Tree<T>>>;

impl<T> Tree<T> {
    fn root(data: T) -> Self {
        Self { left: None, data, right: None }
    }

    fn leaf(d: T) -> Leaf<T> {
        Some(Box::new(Self::root(d)))
    }
}

fn main() {
    let mut tree = Tree::root([4, 5, 6]);
    tree.right = Tree::leaf([1, 2, 3]);
    tree.left = Tree::leaf([7, 8, 9]);

    let newtree = tree.clone();
}

Scheme

(define (deep-copy-1 exp)
  ;; basic version that copies an arbitrary tree made up of pairs
  (cond ((pair? exp)
	 (cons (deep-copy-1 (car exp))
	       (deep-copy-1 (cdr exp))))
	;; cases for extra container data types can be
	;; added here, like vectors and so on
	(else ;; atomic objects
	 (if (string? exp)
	     (string-copy exp)
	     exp))))

(define (deep-copy-2 exp)
  (let ((sharing (make-hash-table)))
    (let loop ((exp exp))
      (cond ((pair? exp)
	     (cond ((get-hash-table sharing exp #f)
		    => (lambda (copy)
			 copy))
		   (else
		    (let ((res (cons #f #f)))
		      (put-hash-table! sharing exp res)
		      (set-car! res (loop (car exp)))
		      (set-cdr! res (loop (cdr exp)))
		      res))))
	    (else
	     (if (string? exp)
		 (string-copy exp)
		 exp))))))

(define t1 '(a b c d))
(define t2 (list #f))
(set-car! t2 t2)
(define t2b (list #f))
(set-car! t2b t2b)
(define t3 (list #f #f))
(set-car! t3 t3)
(set-car! (cdr t3) t3)
(define t4 (list t2 t2b))

;> (print-graph #t)
;> (deep-copy-2 t1)
;(a b c d)
;> (deep-copy-2 t2)
;#0=(#0#)
;> (deep-copy-2 t3)
;#0=(#0# #0#)
;> (deep-copy-2 t4)
;(#0=(#0#) #1=(#1#))

Sidef

Object.dclone() returns a deep clone of any mutable object.

var src = Hash(foo => 0, bar => [0,1])

# Add a cyclic reference
src{:baz} = src

# Make a deep clone
var dst = src.dclone

# The address of src
say src.object_id
say src{:baz}.object_id

# The address of dst
say dst.object_id
say dst{:baz}.object_id

Output:

15154128
15154128
25296304
25296304

Tcl

Tcl uses an immutable value model that is implemented as copy-on-write at the low level, so deep copies are generally not required. However, they can be achieved by simply appending a letter to the value and stripping it off again:

set deepCopy [string range ${valueToCopy}x 0 end-1]

For objects (as introduced in Tcl 8.6), there is a command to create a copy:

set copiedObject [oo::copy $originalObject]

Wren

Library: Wren-seq

Library: Wren-trait

Wren does not have any built-in facilities for deep-copying an object and you therefore have to write your own method to do this.

However, using the above module, a class can inherit from the Cloneable or CloneableSeq abstract class and override its clone() method. Knowing that objects have such a method is useful when cloning other objects which contain them as fields or nested fields.

Note though that, since Wren is dynamically typed, it may be impractical or impossible to deep-copy generic objects because, if an object does not have a clone() method, all that can be done is to return the argument itself which, unless it is a built-in immutable type, will simply be a reference to the original.

In the following example, we attempt to deep-copy a custom type, MyMap, which wraps the built-in generic Map type. This succeeds here because of the types of values used but wouldn't succeed if a Map value were, say, some user-defined type which didn't have a clone() method.

import "./trait" for Cloneable, CloneableSeq
import "./seq" for Lst

class MyMap is Cloneable {
    construct new (m) {
        if (m.type != Map) Fiber.abort("Argument must be a Map.")
        _m = m
    }

    m { _m }

    toString { _m.toString }

    clone() {
        // Map keys are always immutable built-in types so we only need to worry about
        // their values which can be anything.
        var m2 = {}
        for (me in _m) {
            var v = me.value
            m2[me.key] = (v is List) ? Lst.clone(v) :
                         (v is Cloneable || v is CloneableSeq) ? v.clone() : v
        }
        return MyMap.new(m2)
    }
}

var my = MyMap.new({"a": 0, "b": 1, "c": [2, 3], "d": MyMap.new({"e": 4})})
var my2 = my.clone()
System.print("Before any changes:")
System.print("  my  = %(my)")
System.print("  my2 = %(my2)")
// now change my2
my2.m["a"] = 5
my2.m["b"] = 6
my2.m["c"][0] = 7
my2.m["c"][1] = 8
my2.m["d"].m["e"] = 9
my2.m["d"].m["f"] = 10
System.print("\nAfter changes to my2:")
System.print("  my  = %(my)")
System.print("  my2 = %(my2)")

Output:

Before any changes:
  my  = {c: [2, 3], d: {e: 4}, b: 1, a: 0}
  my2 = {c: [2, 3], d: {e: 4}, b: 1, a: 0}

After changes to my2:
  my  = {c: [2, 3], d: {e: 4}, b: 1, a: 0}
  my2 = {c: [7, 8], d: {e: 9, f: 10}, b: 6, a: 5}

Z80 Assembly

There is no built-in type checking, so there's no way to tell apart pointers from actual data without knowing it in advance. Other than that, a deep copy is very easy to perform. A single byte or word can be copied by loading it from memory and writing it to a new location.

LD HL,(&C000)
LD (&D000),HL

For copying a string or record, the LDIR command makes this very easy, provided you know the size (in bytes) of the data you wish to copy. Label arithmetic is the easiest way to do this for fixed-size data.

LD HL,MyString
LD DE,UserRam
LD BC,MyString_End-MyString  ;the difference between these two addresses is the byte count.
LDIR                         ;essentially C's memcpy()

MyString:
byte "Hello, world!",0

UserRam:
ds 32,0   ;32 bytes of memory initialized to zero.