CODEWITHSUNDEEP
gotree
James Hiew
James Hiew

Reputation: 7157

Why does this tree walking function deadlock?

I am going through the Tour of Go to refresh my memory, and am stumbling on the Equivalent Binary Trees exercise. I have written some code to traverse a binary tree that looks like it should work.

package main

import (
    "golang.org/x/tour/tree"
    "fmt"
)

// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
    if t == nil {
        return
    }
    ch <- t.Value
    Walk(t.Left, ch)
    Walk(t.Right, ch)
}

func main() {
    ch := make(chan int, 10)
    go Walk(tree.New(3), ch)
    for v := range ch {
        fmt.Printf("%q", v)
    }
}

When I run the above code I'm getting the following error:

'\x1e''\x0f''\t''\x03''\x06''\f''\x15''\x12''\x1b''\x18'fatal error: all goroutines are asleep - deadlock!

goroutine 1 [chan receive]:
main.main()
    /Users/james/src/local/go-sandbox/main.go:22 +0x115

Process finished with exit code 2

I am wondering why it is deadlocking? It looks like it does print out some garbage before this happens.

Upvotes: 5

Views: 697

Answers (2)

Darshan Rivka Whittle
Darshan Rivka Whittle

Reputation: 34041

The range loop will read until ch is closed, but you never close it, so you end up in state where the main goroutine is asleep waiting to receive on ch, but no other goroutines exist to send to it — "all" one of your goroutines are asleep.

I'd simply wrap the Walk call in main like this:

go func() {
    Walk(tree.New(3), ch)
    close(ch)
}()

See the Tour of Go entry a few earlier than the one you linked to for a refresher on Range and Close.

Upvotes: 4

ain
ain

Reputation: 22759

You must close the channel so range loop over it will terminate:

func main() {
    ch := make(chan int, 10)
    go func() {
        Walk(tree.New(3), ch)
        close(ch)
    }()
    for v := range ch {
        fmt.Printf("%q", v)
    }
}

Upvotes: 8

Related Questions