title: Synchronize workers for recursive crawl
body: <p>I would like to implement a "crawler" with <code>n</code> workers where each worker is able to add additional jobs. The program should stop when there are no jobs left and all workers have finished their work.</p>
  
  <p>I have the following code (you can play with it at <a href="https://play.golang.org/p/_j22p_OfYv" rel="nofollow noreferrer">https://play.golang.org/p/_j22p_OfYv</a>):</p>
  
  <pre><code>package main
  
  import (
      "fmt"
      "sync"
  )
  
  func main() {
      pathChan := make(chan string)
      fileChan := make(chan string)
      workers := 3
      var wg sync.WaitGroup
  
      paths := map[string][]string{
          "/":     {"/test", "/foo", "a", "b"},
          "/test": {"aa", "bb", "cc"},
          "/foo":  {"/bar", "bbb", "ccc"},
          "/bar":  {"aaaa", "bbbb", "cccc"},
      }
  
      for i := 0; i &lt; workers; i++ {
          wg.Add(1)
          go func() {
              for {
                  path, ok := &lt;-pathChan
                  if !ok {
                      break
                  }
  
                  for _, f := range paths[path] {
                      if f[0] == '/' {
                          pathChan &lt;- f
                      } else {
                          fileChan &lt;- f
                      }
                  }
              }
  
              wg.Done()
          }()
      }
  
      pathChan &lt;- "/"
  
      for {
          filePath, ok := &lt;-fileChan
          if !ok {
              break
          }
  
          fmt.Println(filePath)
      }
  
      wg.Wait()
      close(pathChan)
  }
  </code></pre>
  
  <p>Unfortunately, this ends in a dead-lock. Where exactly is the problem? Also, what is the best practice to write such functionality? Are channels the correct feature to use?</p>
  
  <p><strong>EDIT:</strong></p>
  
  <p>I have updated my code to use two wait groups, one for the jobs and one for the workers (see <a href="https://play.golang.org/p/bueUJzMhqj" rel="nofollow noreferrer">https://play.golang.org/p/bueUJzMhqj</a>):</p>
  
  <pre><code>package main
  
  import (
      "fmt"
      "sync"
  )
  
  func main() {
      pathChan := make(chan string)
      fileChan := make(chan string)
      jobs := new(sync.WaitGroup)
      workers := new(sync.WaitGroup)
      nworkers := 2
  
      paths := map[string][]string{
          "/":     {"/test", "/foo", "a", "b"},
          "/test": {"aa", "bb", "cc"},
          "/foo":  {"/bar", "bbb", "ccc"},
          "/bar":  {"aaaa", "bbbb", "cccc"},
      }
  
      for i := 0; i &lt; nworkers; i++ {
          workers.Add(1)
          go func() {
              defer workers.Done()
              for {
                  path, ok := &lt;-pathChan
                  if !ok {
                      break
                  }
  
                  for _, f := range paths[path] {
                      if f[0] == '/' {
                          jobs.Add(1)
                          pathChan &lt;- f
                      } else {
                          fileChan &lt;- f
                      }
                  }
  
                  jobs.Done()
              }
  
          }()
      }
  
      jobs.Add(1)
      pathChan &lt;- "/"
  
      go func() {
          jobs.Wait()
          close(pathChan)
          workers.Wait()
          close(fileChan)
      }()
  
      for {
          filePath, ok := &lt;-fileChan
          if !ok {
              break
          }
  
          fmt.Println(filePath)
      }
  
  }
  </code></pre>
  
  <p>This indeed seems to work, but obviously a deadlock will still happen if <code>nworkers</code> is set to <code>1</code>, because the single worker will wait forever when adding something to the channel <code>pathChan</code>. To solve this issue, the channel buffer can be increased (e.g. <code>pathChan := make(chan string, 2)</code>), but this will only work as long as two buffer isn't completely full. Of course, the buffer size could be set to a large number, say 10000, but the code could still hit a deadlock. Additionally, this doesn't seem to be a clean solution to me.</p>
  
  <p>This is where I realized that it would be easier to use some sort of queue instead of a channel, where elements can be added and removed without blocking and where the size of the queue isn't fixed. Do such queues exist in the Go standard library?</p>