proposal: reflect: add DeepCopy

[changkun]

Previous proposal updates

As a duality complement of `DeepEqual`, I propose to add a new API for deep copy:

package reflect

// DeepCopy copies src to dst recursively.
//
// Two values of identical type are deeply copied if one of the following cases applies.
//
// Array and slices values are deeply copied, including its elements.
//
// Struct values are deeply copied for all fields, including exported and unexported.
//
// Interface values are deeply copied if the underlying type can be deeply copied.
//
// Map values are deeply copied for all of its key and corresponding values.
//
// Pointer values are deeply copied for its pointed value.
//
// One exception is Func value. It is not copiable, and still points to the same function.
//
// Other values - numbers, bools, strings, and channels - are deeply copied and
// have different underlying memory address.
func DeepCopy[T any](dst, src T)
// or
//
// DeepCopy panics if src and dst have different types.
func DeepCopy(dst, src any)
// or
//
// DeepCopy returns an error if src and dst have different types.
func DeepCopy(dst, src any) error

DeepCopy may likely be very commonly used. Implement it in reflect package may receive better runtime performance.

The frist version seems more preferrable because type parameters permits compile time type checking, but the others might also be optimal.

The proposed document of the API is preliminary.

---

Update:

Based on the discussions until #51520 (comment), the documented behavior could be:

// DeepCopy copies src to dst recursively.
//
// Two values of identical type are deeply copied if one of the following
// cases apply.
//
// Array and slices values are deeply copied, including its elements.
//
// Struct values are deeply copied for all fields, including exported
// and unexported.
//
// Map values are deeply copied for all of its key and corresponding
// values.
//
// Pointer values are deeply copied for their pointed value, and the
// pointer points to the deeply copied value.
//
// Numbers, bools, strings are deeply copied and have different underlying
// memory address.
//
// Interface values are deeply copied if the underlying type can be
// deeply copied.
//
// There are a few exceptions that may result in a deeply copied value not
// deeply equal (asserted by DeepEqual(dst, src)) to the source value:
//
// 1) Func values are still refer to the same function
// 2) Chan values are replaced by newly created channels
// 3) One-way Chan values (receive or read-only) values are still refer
//    to the same channel
//
// Note that for stateful copied values, such as the lock status in
// sync.Mutex, or underlying file descriptors in os.File and net.Conn,
// are retained but may result in unexpected consequences in follow-up
// usage, the caller should clear these values depending on usage context.
//
// The function panics/returns with an error if
//
// 1) source and destination values have different types
// 2) destination value is reachable from source value

Depending on the design choice, the content included and after exceptions could decide on different behaviors, see
#51520 (comment), and #51520 (comment) as examples.

The API signature could select one of the following possible options. The main differences between them include two aspects:

1. panic (break the code flow, and enter defer recover) or return an error (user handled directly)
2. destination value in either parameter (more GC friendly) or return value (always allocates)

func DeepCopy[T any](dst, src T) error
func DeepCopy[T any](dst, src T)
func DeepCopy(dst, src any) error
func DeepCopy(dst, src any)

func DeepCopy[T any](src T) (T, error)
func DeepCopy[T any](src T) T
func DeepCopy(src any) (any, error)
func DeepCopy(src any) error

Either version is optimal, and purely depending on the final choice.

Update (until #51520 (comment)):

I propose to add a new API for deep copy:

// DeepCopy copies src to dst recursively.
//
// Two values of identical type are deeply copied if one of the following
// cases apply.
//
// Numbers, bools, strings are deeply copied and have different underlying
// memory address.
//
// Slice and Array values are deeply copied, including its elements.
//
// Map values are deeply copied for all of its key and corresponding
// values.
//
// Pointer values are deeply copied for their pointed value, and the
// pointer points to the deeply copied value.
//
// Struct values are deeply copied for all fields, including exported
// and unexported.
//
// Interface values are deeply copied if the underlying type can be
// deeply copied.
//
// There are a few exceptions that may result in a deeply copied value not
// deeply equal (asserted by DeepEqual(dst, src)) to the source value:
//
// 1) Func values are still refer to the same function
// 2) Chan values are replaced by newly created channels
// 3) One-way Chan values (receive or read-only) values are still refer
//    to the same channel
//
// Note that while correct uses of DeepCopy do exist, they are not rare.
// The use of DeepCopy often indicates the copying object does not contain
// a singleton or is never meant to be copied, such as sync.Mutex, os.File,
// net.Conn, js.Value, etc. In these cases, the copied value retains the
// memory representations of the source value but may result in unexpected
// consequences in follow-up usage, the caller should clear these values
// depending on their usage context.
func DeepCopy[T any](src T) (dst T)

Here is an implementation for trying out: https://pkg.go.dev/golang.design/x/reflect

[mvdan]

Have you seen previous proposals like #18371?

[changkun]

Unlike #18371, this proposal suggests deep copy as a package API (as a complement of DeepEqual) other than a built-in function.

[mvdan]

The reflect API was already mentioned there, but in any case, it was rejected due to the functionality being proposed and not what package API it's under.

[changkun]

The previous decision was made based on the interpretation of it should not be built-in. The discussion of as a reflect API seems not to converge to a consensus yet (as how I understand the conversation).

Sure, the deep copy behavior can be implemented as an external package as there are many already. But as an API in reflect package, it can also receive runtime performance improvements (e.g. direct memory copy).

Moreover, it is also a standard implementation to avoid potentially incorrect implementation.

[ianlancetaylor]

How should DeepCopy handle circular data structures?

[changkun]

How should DeepCopy handle circular data structures?

I can imagine two options for as the behavior (if I understood the question correctly):

1. Panics if the data structure is circular
2. Handle them. For example:

package main

import (
	"unsafe"
	"reflect"
)

type A struct{ b *B }
type B struct{ a *A }

func main() {
	x := &A{}
	y := &B{}
	x.b = y
	y.a = x
	println(memAddr(x), memAddr(y), memAddr(x.b), memAddr(x.b.a), memAddr(x.b.a.b)) // 1 2 2 1 2
	
	var z *A
	reflect.DeepCopy(z, x)
	
	println(memAddr(z), memAddr(z.b), memAddr(z.b.a), memAddr(z.b.a.b)) // 3 4 3 4
}

func memAddr[T any](x *T) uintptr { return uintptr(unsafe.Pointer(x)) }

I would more prefer the second case, hence propose the second option.

[DeedleFake]

I feel like there is little benefit to the output value being an argument to the function. Any, for example, fields in a struct that are interfaces, pointers, maps, etc. are going to require the function to instantiate new values from scratch anyways if it's really going to create a full copy, so how about just func DeepCopy[T any](v T) T? That'll lead to less confusion and fewer potential errors with mismatched/incorrect types. Otherwise you also get questions like

What happens if I copy into a map that has existing data in it? Is the map cleared first? If I copy into a slice, does the slice's old capacity get preserved?

[DeedleFake]

@changkun

How does it handle overlapping cyclic structures? For example:

type S struct {
  Next *S
}

func main() {
  one := &S{}
  two := &S{Next: &S{Next: &S{Next: one}}}
  one.Next = two

  reflect.DeepCopy(one, two)
}

Obviously this would be a really weird case, but something similar could happen accidentally. If the address stored in one is used to store the output, then that means that two's data is getting changed by the copy, potentially resulting in some really strange, implementation-dependent results if not explicitly defined, likely an infinite loop as it continuously generates new structures to try to continue copying further and further downwards.

[changkun]

...so how about just func DeepCopy[T any](v T) T? That'll lead to less confusion and fewer potential errors with mismatched/incorrect types.

I think this is one of the possible optimal versions of deep copy. The pros are as you explained and don't require further document about the status of destination. The cons might be that it always have to allocate on heap.

The proposed versions have pros such as the destination might be stack allocated, hence GC friendly. The potential con could be addressed by documenting more:

The destination value must be a nil or points to a zero
value of source type, and itself not reachable from the
source value. Otherwise, the function panics/return
an error.

Either way is acceptable, and have their unique advantages. Depends on the final decision.

[changkun]

type S struct {
  Next *S
}

func main() {
  one := &S{}
  two := &S{Next: &S{Next: &S{Next: one}}}
  one.Next = two
  reflect.DeepCopy(one, two)
}

This is an interesting case and I would more prefer to panic as a misuse and not handling it.

It is solved by adding this constraint as my last comment elaborated:

The destination value must be a nil or points to a zero
value of source type, and itself not reachable from the
source value. Otherwise, the function panics/return
an error.

[rittneje]

One thing that is problematic is that currently the reflect package disallows setting private (unexported) struct fields. But your proposed version of DeepCopy would have to violate this rule.

Also, there are several interesting cases beyond just func. Like what does it mean to deep copy a mutex? Or a buffered channel? Or a one-way channel? Or a net.Conn? What if a type needs to override whatever the default deep copy logic is?

To me it seems like the de facto standard Clone method is a cleaner solution, because then there is a stable API contract around what it means to copy something.

[changkun]

One thing that is problematic is that currently the reflect package disallows setting private (unexported) struct fields. But your proposed version of DeepCopy would have to violate this rule.

I would argue that deep copy is not about violating setting private struct fields because one cannot use it to set a particular private field. Instead, the API duplicates one to the other completely.

Also, there are several interesting cases beyond just func. Like what does it mean to deep copy a mutex? Or a buffered channel? Or a one-way channel? Or a net.Conn? What if a type needs to override whatever the default deep copy logic is?

These are valid cases, but also make the argument of "why a standard implementation is necessary" stronger. To my senses, I think:

1. deep copy of a mutex results in a new mutex;
2. a buffered channel results in a buffered channel that has the same buffer size, but elements inside the buffer are not copied (intuitively, the elements should be received by the actual receiver, not a copied value) hence empty buffer;
3. one-way channels: a) a copy of a receive-only channel results in the same receive-only channel (intuitively as a new reader), or could result in nil (intuitively slightly matches the behavior in 2)). b) send-only channel results in the same send-only channel (intuitively as a new sender), or could result in nil.
4. a copy of net.Conn results in an invalid connection, can be either zero-valued or nil.

To me it seems like the de facto standard Clone method is a cleaner solution, because then there is a stable API contract around what it means to copy something.

I am not sure which Clone are you referring to and why it is considered as a cleaner de facto standard. Assuming net/http, there are different Clones but it seems that they are all customized object copy behavior, for instance:

func (h Header) Clone() Header
func (r *Request) Clone(ctx context.Context) *Request
func (t *Transport) Clone() *Transport

defining a common interface (as a Copiable constraint) is not possible, there is also no way to define NonCopiable that excludes certain types with the current type set design.

Let's still assume a type set type Copier[T] interface { Clone() T }, a non-pointer value (say type V) may not be subject to this constraint if the Clone signature is (*V).Clone() *V. In this case, only a pointer of V can be used as a type parameter of Copier (Copier[*V]).

[davecheney]

deep copy of a mutex results in a new mutex;

If the original mutex was locked, what is the state of the new mutex?

If the struct being copied contained a *os.File, what is the state of the cloned *os.File? Does it point a new a file descriptor, or the original file descriptor? What happens when code was using the mutex to serialise access to that file descriptor?