golang：使用框架数据标记结构的首选方法

Question

tl;dr I have an arbitrary directed graph defined by a Node struct. I now want to be able to provide a way to write functions that walk this graph and "tag" each Node with metadata specific to that function.

For example, consider a function to count the number of nodes:

type Node struct {
    Nexts []*Node
}

func CountNodes(root *Node) int {
    m := make(map[*Node]bool)
    return countNodesHelper(root, m)
}

func countNodesHelper(root *Node, m map[*Node]bool) int {
    _, seen := m[root]
    if seen {
        return 0
    }
    m[root] = true
    c := 1
    for _, child := range root.Nexts {
        c += countNodesHelper(child, m)
    }
    return c
}

func main() {
    n1 := &Node{make([]*Node, 0, 1)}
    n2 := &Node{[]*Node{n1}}
    n1.Nexts = append(n1.Nexts, n2)
    fmt.Println(CountNodes(n1))
}

I could rewrite this if I added a "seen" tag inside the struct:

type NodeWithTag struct {
    Nexts []*NodeWithTag
    Seen  bool
}

func CountNodesWithTag(root *NodeWithTag) int {
    if root.Seen {
        return 0
    }
    root.Seen = true
    c := 1
    for _, child := range root.Nexts {
        c += CountNodesWithTag(child)
    }
    return c
}

func main() {
    n1 := &NodeWithTag{make([]*NodeWithTag, 0, 1), false}
    n2 := &NodeWithTag{[]*NodeWithTag{n1}, false}
    n1.Nexts = append(n1.Nexts, n2)
    fmt.Println(CountNodesWithTag(n1))
}

But the Seen tag isn't enough for, say, a DFS on a tree where I also want to find backwards edges (you need to count up to 2 -- never seen, seen, seen a second time along a a single path). So, I want some way to allow the function's implementation to use it's own type to tag the struct with. A rough equivalent of:

type Node struct {
  ...
  // Not valid golang
  void* tag
}

but safer that a void* -- The function should be able to statically verify that the tag is the current type that it expects. Is there a way to do this / an alternative approach.

The reason I want to associate the tag with the Node (rather than a separate map / store of the tags) is to allow easy parallelization of the functions that use such tags, farming out the nodes to different goroutines. In the first approach, the map would have to be shared between the goroutines, and this would quickly become a bottleneck because it will require synchronized access.

Answer 1

If you need to support arbitrary data types, you'll need to use an empty interface:

type NodeWithTag struct {
    Nexts []*NodeWithTag
    Tag   interface{}
}

You can assign any value to the Tag field. If you want to verify that the value is a certain type, say MyType, you can use a type assertion:

myVal, ok := node.Tag.(MyType)

If the value is of that type, ok will be true and myVal will contain the typed value.