douhe3313
2017-03-05 17:45
浏览 39
已采纳

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

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)
  • 写回答
  • 好问题 提建议
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

  • dsplos5731 2017-03-05 18:06
    已采纳

    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.

    已采纳该答案
    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题