克隆节点[golang.org/x/net/html]：堆栈溢出

Question

I'm trying to clone/copy a html Node so that I can modify/duplicate it and then inject it back in the main document. The issue is that I'm getting a stack overflow[2]. I assume there is a race condition. It looks like it's due Parent and PrevSibling fields(based on my blind tests). Any idea why is that and how can I clone it completely(so that it can test positive on reflect.DeepEqual) ?

func clone(src *html.Node) *html.Node {
    if src == nil {
        return nil
    }
    n := html.Node{
        Parent:      clone(src.Parent),
        FirstChild:  clone(src.FirstChild),
        LastChild:   clone(src.LastChild),
        PrevSibling: clone(src.PrevSibling),
        NextSibling: clone(src.NextSibling),

        Type:      src.Type,
        DataAtom:  src.DataAtom,
        Data:      src.Data,
        Namespace: src.Namespace,
    }
    for _, v := range n.Attr {
        n.Attr = append(n.Attr, v)
    }
    return &n
}

[2]

runtime: goroutine stack exceeds 1000000000-byte limit
fatal error: stack overflow

runtime stack:
runtime.throw(0x3495b9, 0xe)
    /Users/x/gosrc/src/runtime/panic.go:566 +0x95
runtime.newstack()
    /Users/x/gosrc/src/runtime/stack.go:1061 +0x416
runtime.morestack()
    /Users/x/gosrc/src/runtime/asm_amd64.s:366 +0x7f

goroutine 7 [running]:
runtime.heapBitsSetType(0xc42a0ae5b0, 0x70, 0x68, 0x32e420)
    /Users/x/gosrc/src/runtime/mbitmap.go:867 fp=0xc4402002a8 sp=0xc4402002a0
runtime.mallocgc(0x70, 0x32e420, 0x1, 0x0)
    /Users/x/gosrc/src/runtime/malloc.go:690 +0x5ba fp=0xc440200348 sp=0xc4402002a8
runtime.newobject(0x32e420, 0x0)
    /Users/x/gosrc/src/runtime/malloc.go:785 +0x38 fp=0xc440200378 sp=0xc440200348
bitbucket.org/x/y/client.clone(0xc420138d20, 0x0)

Answer 1

When deep-cloning a data structure containing pointers that is not a tree you need a more sophisticated approach; if you call

 n := Node{...
           next:clone(src.next),
           prev:clone(src.prev),
           ...}

and your structure has even just two siblings nodes n1 and n2 where n1.next is &n2 and n2.prev is &n1 the code will stack overflow (cloning n1 will call clone(n2) for the next pointer that in turn will call clone(n1) for the prev pointer, looping back and forth forever until the call stack explodes).

A solution is to keep a "cache" where when cloning a node you will store the src→cloned association, so the clone procedure will be able to return the node in case of recursive structures.

What follows is a full minimal example:

package main

import "fmt"

type Node struct {
    value      int
    prev, next *Node
}

func clone(n *Node, cache map[*Node]*Node) *Node {
    if n == nil {
        return nil
    }

    if val, ok := cache[n]; ok {
        return val
    }

    val := &Node{}
    cache[n] = val
    val.value = n.value
    val.prev = clone(n.prev, cache)
    val.next = clone(n.next, cache)

    return val
}

func printlist(n *Node) {
    for n != nil {
        println(fmt.Sprintf("address=%p, value=%v, prev=%p, next=%p",
            n, n.value, n.prev, n.next))
        n = n.next
    }
}

func main() {
    n1 := &Node{}
    n2 := &Node{}
    n3 := &Node{}
    n1.value = 100
    n2.value = 200
    n3.value = 300
    n1.next = n2
    n2.prev = n1
    n2.next = n3
    n3.prev = n2

    printlist(n1)

    println("Cloning list")
    c1 := clone(n1, make(map[*Node]*Node))
    printlist(c1)
}

Running this program on my machine i get

~/x$ go run recstruct.go
address=0xc42000e540, value=100, prev=0x0, next=0xc42000e560
address=0xc42000e560, value=200, prev=0xc42000e540, next=0xc42000e580
address=0xc42000e580, value=300, prev=0xc42000e560, next=0x0
Cloning list
address=0xc42000e5c0, value=100, prev=0x0, next=0xc42000e5e0
address=0xc42000e5e0, value=200, prev=0xc42000e5c0, next=0xc42000e600
address=0xc42000e600, value=300, prev=0xc42000e5e0, next=0x0
~/x$ 

where you can see that the three nodes have been cloned correctly and prev/next are pointing each other in the cloned structure list.