title: golang: Preferred way to tag a struct with aribtrary data
body: <p>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.</p>
  
  <p>For example, consider a function to count the number of nodes:</p>
  
  <pre><code>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 := &amp;Node{make([]*Node, 0, 1)}
      n2 := &amp;Node{[]*Node{n1}}
      n1.Nexts = append(n1.Nexts, n2)
      fmt.Println(CountNodes(n1))
  }
  </code></pre>
  
  <p>I could rewrite this if I added a "seen" tag inside the struct:</p>
  
  <pre><code>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 := &amp;NodeWithTag{make([]*NodeWithTag, 0, 1), false}
      n2 := &amp;NodeWithTag{[]*NodeWithTag{n1}, false}
      n1.Nexts = append(n1.Nexts, n2)
      fmt.Println(CountNodesWithTag(n1))
  }
  </code></pre>
  
  <p>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:</p>
  
  <pre><code>type Node struct {
    ...
    // Not valid golang
    void* tag
  }
  </code></pre>
  
  <p>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.</p>
  
  <p>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.</p>