Recursive tree building in Goroutines

Question

I want to build and display a tree of linked issues using the github.com/xlab/treeprint package. I have a working version, but it doesn't use go-routines, and seems like a good candidate.

The tree part may be irrelevant, though maybe if I return different values from my function, I could build it in a different way.

func main {
    tree := treeprint.New()
    recurseTreeFetching(fetcher, tree, *issueID)
    fmt.Println(tree.String())
}

func recurseTreeFetching(fetcher Fetcher, tree treeprint.Tree, issueID string) {
    issues := fetcher.fetchIssues(issueID)
    if len(issues) == 0 {
        return
    }
    for i := 0; i < len(issues); i++ {
        currIssueID := issues[i].Key
        currBranch := tree.AddBranch(currIssueID)
        recurseTreeFetching(fetcher, currBranch, currIssueID)
    }
}

This works, but it's pretty slow. I've looked at answers like this: /recursive-goroutines-what-is-the-neatest-way-to-tell-go-to-stop-reading-from-ch, but I'm struggling to get it to work.

I'm not limiting depth, nor checking for already added nodes.

I've tried "sprinkling on some concurrency." But the function deadlocks. Any guidance or fixes?

func main {
    tree := treeprint.New()
    var ch chan int
    go recurseTreeFetching(fetcher, tree, *issueID, ch)
    tocollect := 1
    for n := 0; n < tocollect; n++ {
        tocollect += <-ch
    }
    fmt.Println(tree.String())

}

func recurseTreeFetching(fetcher Fetcher, tree treeprint.Tree, issueID string, ch chan int) {
    issues := fetcher.fetchIssues(issueID)
    if len(issues) == 0 {
        return
    }
    ch <- len(issues)
    for i := 0; i < len(issues); i++ {
        currIssueID := issues[i].Key
        currBranch := tree.AddBranch(currIssueID)
        go recurseTreeFetching(fetcher, currBranch, currIssueID, ch)
    }
}

Answer 1

Adding another answer because it uses a different method.

The problem with my first solution is if we never reach the depth variable, we never get a done <- true, so the function never "wraps up". If this is not called deadlock, what is it called?

The idea of the following code is as follows:

• maintain a number of function calls being executed, these are equivalent to the number of children (including the initial "tree-top").
• once a function execution finishes, subtract that from the number.
• once we get to zero, we've exhausted our function calls and can print the tree

Potential problems: If one branch takes significantly longer than another, I believe the code could subtract the children value to 0 before the slow branch is complete.

func recurseTreeFetching(fetcher Fetcher, tree treeprint.Tree, issueID string, ch chan int, depth int) {
    issues := fetcher.fetchIssues(issueID)
    if len(issues) == 0 {
        // delete this child
        ch <- -1
        return
    }
    depth--
    if depth == 0 {
        // delete this child
        ch <- -1
        return
    }
    // add the number of child issues, minus the current one
    ch <- len(issues) - 1

    for i := 0; i < len(issues); i++ {
        currIssueID := issues[i].Key
        currBranch := tree.AddBranch(currIssueID)
        go recurseTreeFetching(fetcher, currBranch, currIssueID, ch, depth)
    }
}

And the client code:

    go recurseTreeFetching(fetcher, tree, *issueID, ch, *depth)
    childs := 1
    for childs > 0 {
        childs += <-ch
    }

    fmt.Println(tree.String())

Here's a test that I thought would demonstrate the bug, however it displays correctly, so maybe this works.

type fakeUnEvenFetcher struct {
}

func (f fakeUnEvenFetcher) fetchIssues(issueID string) []Issue {
    var array []Issue
    // initial return
    if issueID == "a" {
        b := Issue{Key: "b"}
        array = append(array, b)
        c := Issue{Key: "c"}
        array = append(array, c)
    }
    // branch b quickly returns three results
    if issueID == "b" {
        d := Issue{Key: "d"}
        array = append(array, d)
        e := Issue{Key: "e"}
        array = append(array, e)

    }
    // branch c returns two returns after 3 seconds
    if issueID == "c" {
        time.Sleep(3 * time.Second)
        f := Issue{Key: "f"}
        array = append(array, f)
        g := Issue{Key: "g"}
        array = append(array, g)
        h := Issue{Key: "h"}
        array = append(array, h)
    }

    return array
}

func TestUnEvenFetch(t *testing.T) {
    fetcher := fakeUnEvenFetcher{}
    tree := treeprint.New()
    var ch = make(chan int)

    go RecurseTreeFetching(fetcher, tree, "a", ch, 3)
    childs := 1
    for childs > 0 {
        childs += <-ch
    }

    fmt.Println(tree.String())
}

This prints:

.
├── b
│   ├── d
│   └── e
└── c
    ├── f
    ├── g
    └── h

Which is my expected result, but not the failure I was expecting.