go/types: recursive functions cause broken InitOrder

[nlacasse]

If you have a recursive function called in an init function (or toplevel var block), the parsed InitOrder can be broken. It will report that some variables should be initialized before their dependencies.

For example, in program.go below, we have two variables: m and fooInst. The variable m depends on fooInst, and fooInst is the result of a recursive function call.

package program

var (
    m       = fooInst.Method()
    fooInst = newFoo()
)

type Foo struct{}

func (t *Foo) Method() bool {
    return true
}

func newFoo() *Foo {
    return newFoo()
}

The initialization order should be fooInst then m.

However, after parsing program.go with parser.ParseFile and then calling config.Check, the resulting InitOrder has m initialized before fooInst.

Here is the parsing program I used:

package main

import (
    "fmt"
    "go/ast"
    "go/parser"
    "go/token"
    "golang.org/x/tools/go/types"
)

func main() {
    fset := token.NewFileSet()

    f, err := parser.ParseFile(fset, "program.go", nil, 0)
    if err != nil {
        panic(err)
    }

    info := &types.Info{}
    config := types.Config{}

    _, err = config.Check("", fset, []*ast.File{f}, info)
    if err != nil {
        panic(err)
    }

    for k, v := range info.InitOrder {
        fmt.Printf("Initializer #%v: %v\n", k, v)
    }
}

And the output:

Initializer #0: m = fooInst.Method()
Initializer #1: fooInst = newFoo()

This order is clearly broken, since m cannot be initialized before fooInst.

(All tests done with go version go1.4 linux/amd64)

[griesemer]

Here's a more "realistic" example in the sense that the code would actually run (rather than lead to endless recursion and thus stack overflow):

package p

var (
    m = x.m()
    x = makeT(10)
)

type T struct{}

func (T) m() int {
    return 0
}

func makeT(n int) T {
    if n > 0 {
        return makeT(n-1)
    }
    return T{}
}

go/types also reports the wrong initialization order in this case.

The issue is that initialization cycles through functions only are silently ignored and then lead to a wrong initialization order (initorder.go:52). Instead, cycles involving only functions should probably be removed beforehand.

[cierniak]

This bug makes it impossible to use go/types as part of a frontend for a compiler. Here's an example of a Go package that is compiled incorrectly and fails at runtime because of incorrect variable initialization order: https://github.com/vanadium/go.v23/tree/master/vdl

[griesemer]

This is still high on the list for 1.7.

[gopherbot]

CL https://golang.org/cl/23442 mentions this issue.

[gopherbot]

CL https://golang.org/cl/24131 mentions this issue.