Go: cmd/compile: incorrect package initialization order for spec example

[chadwhitacre]

From https://golang.org/ref/spec#Package_initialization:

Initialization proceeds by repeatedly initializing the next package-level variable that is earliest in declaration order and ready for initialization, until there are no variables ready for initialization.

[…]

For example, given the declarations

var (
  a = c + b
  b = f()
  c = f()
  d = 3
)

func f() int {
  d++
  return d
}

the initialization order is d, b, c, a.

If Go initializes b before c, then after initialization I'd expect the value of b to be 4 and c to be 5. However, this test outputs b as 5 and c as 4. Swapping the b and c declarations doesn't change the output, but swapping the order in the addition in the declaration of a _does_ change the output. Does this mean that the initialization order in the example is actually d, c, b, a? And that both LHS and RHS are in scope in the phrase "earliest in declaration order"? Or (more likely) am I missing something about what it means to declare and initialize a variable?

P.S. Location in current master:

https://github.com/golang/go/blob/a9afa4e933f3eff131f12e24bb0f5b9f3168ca14/doc/go_spec.html#L6341

[griesemer]

Thanks for the issue. The spec example is correct but cmd/compile is wrong; and I'm pretty sure we have an issue for it, but I can't find it at the moment. go/types also agrees with the spec, and there is a test case for this exact example here).

The spec says:

...by repeatedly initializing the next package-level variable that is earliest in declaration order and ready for initialization...

At first, a is dependent on c and b, so it must wait. Both b and c depend on d so they also must wait. Once d is initialized, both c and b have no (uninitialized) dependency and thus can be initialized. They must be initialized in declaration order; since b is declared before c, b must be initialized first. Hence you get the order d, b, c, a.

By introducing a little helper function, we can have the code print out the initialization order explicitly: https://play.golang.org/p/yiajBYfoSG . As you can see, the order is clearly wrong.

The reason it is wrong for cmd/compile is that the compiler doesn't sort the "ready to initialize" variables in declaration order for some reason.

[chadwhitacre]

for some reason

Hmm ... something related to initfix? 🤔

https://github.com/golang/go/blob/2c1d2e06afee98d0770427d8b6c29bd9971a0999/src/cmd/compile/internal/gc/sinit.go#L243-L254

[griesemer]

Yes, somewhere in that file. Haven't investigated.

[chadwhitacre]

@griesemer Cool, no worries. Verbose dive log on https://github.com/whit537/go/issues/1, will report back here if I find anything. :)

[chadwhitacre]

@griesemer I've got the test running. It passes, which seems odd. My work plan:

• Modify TestInitOrderInfo so that it fails for the case in question (and perhaps others as well?).
• Fix it! :) Seems like initorder.go might be implicated.

[ianlancetaylor]

For the record, gccgo gets this right.

[griesemer]

@whit537 I'm not sure what you mean with the test passes. If you're referring to go/types's test then of course it passes. go/types does this correctly as I mentioned above. The bug is in the compiler (which doesn't use go/types).

[chadwhitacre]

@griesemer @ianlancetaylor I've been working on writing a test and thought I'd provide an update. I don't find any existing tests for package initialization ordering in the compiler. If I'm missing them by all means please point them out. I'm writing a new sinit_test.go file that so far looks like this (yes, it's broken):

// Copyright 2017 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package gc

import (
    "cmd/compile/internal/syntax"
    "testing"
)

func TestInitOrder(t *testing.T) {
    tests := []struct {
        src string
    }{
        {`package foo; var (bar = 537)`},
    }
    for i, test := range tests {

        parsed, err := syntax.ParseBytes(nil, []byte(test.src), nil, nil, nil, 0)
        initfix(parsed)

        if test.src != `Greetings, program!` {
            t.Errorf("%d: y u no greet? :(", i)
        }
    }
}

I was hoping to use writing a test or three to comprehend the code so I can find the bug, and I'm trying to find a good place in the call chain at which to test even simple package initialization behavior. The call chain I see is: Main → fninit → initfix → initreorder. What I'm up against is that afaict Main does a lot of processing and mutating of xtop before handing it off to fninit and initfix. I'm looking for a way to short-circuit all of that in a test since initfix seems like the important function here. I have a hunch that noder.go might be the ticket.

That's my current status. I would be happy for feedback if you have it, otherwise I will keep plugging away as I can find the time. :)

[mdempsky]

@whit537 For historical reasons (the compiler used to be written in C, so it couldn't use Go's testing package), the compiler is mostly tested through tests in $GOROOT/test. You can run those tests by cd'ing into $GOROOT/test and running go run run.go to run them all or something like go run run.go -- fixedbugs/bug345.go to run a single one.

It looks like there are some initialization related tests in there (e.g., $GOROOT/test/*init*.go).

[chadwhitacre]

I've created fixedbugs/issue22326.go with the spec example. It fails as expected with

go run run.go -- fixedbugs/issue22326.go

Now I'm trying to see a panic in src/cmd/compile/internal/gc/main.go show up under this test. I've discovered the comment-based execution recipes for run.go (e.g., // run), but haven't yet identified one of those (buildrun?) to help here ...

[chadwhitacre]

Figured out to rebuild Go with make.bash before testing with go run run.go, and to use printlns instead of panics so that rebuilding succeeds. Now to debug! :)

Lessee here ... 🤔

[chadwhitacre]

Here are:

• example.go, the spec example without the d (not needed to reproduce the bug),
• a patch (against 3e887ff7ea4f1e0d17a7a67e906bef9eec00ed1d) to trace the package initialization AST walk,
• the stderr of go run example.go using the patch, and
• a mapping of int (as line number) to Op.

My hunch is that the first traversal of c should only make it as far as InitPending, not the whole way to InitDone, so that on the second traversal it runs to completion. In the second traversals c comes after b as desired, since it's in order of the declarations, as opposed to the order in the addition.

A naive attempt to move the init2 over defn.Right to below the subsequent append resulted in a failure to build. My next step is to understand that init2 call better, and consider what condition might follow InitPending to catch this case.

[mdempsky]

This issue was present in Go 1.9, so not a regression nor release critical. Bumping to 1.11.

[chadwhitacre]

Going over this in person with @DeadHeadRussell ... looks like options are:

1. Introduce some sort of state/context object to send down through the AST walk to make the information about variable declaration order available when calling init over Rlists.
2. Traverse back up the tree as needed to discover this information.

[chadwhitacre]

Not obvious that parent is available on Node so (2) might not be a ready option.

[chadwhitacre]

(1) is pretty clearly the longer-term solution, but also pretty clearly a significant refactor.

[josharian]

sinit.go could use a substantial rewrite. However, that's pretty non-trivial.

Last time I looked at adding state to some sinit.go methods, I found it pretty hard to work with, because walk and sinit call each other recursively, and it gets gnarly quickly. Maybe your needs will be more easily met.

Also, long term, we'd like to get rid of the current Node AST entirely, so any major refactoring to sinit.go would hopefully move in the direction of simplification and elimination of code, e.g. by shifting it into the SSA backend.

That's not really a precise answer to your implicit question, but I hope it helps a little.

[chadwhitacre]

The call graphs in sinit.go are indeed gnarly, though I think this bug can be fixed short of a rewrite.

something related to initfix?

Here's a sketch of data structures and an algorithm to add to initfix:

dcls: [a,b,c,d]

deps:
    a: [c,b]
    b: [d]
    c: [d]
    d: []

depsback:
    d: [c,b]
    c: [a]
    b: [a]
    a: []

initreorder(...)

while dcls
    for n in dcls
        if deps[n]
            continue

        lout.append(n)
        dcls.remove(n)

        for o in depsback[n]
            deps[o].remove(n)

dcls seems easy to get under initreorder (modulo a wrinkle around static vs. dynamic declarations; d = 3 doesn't actually end up in lout). deps / depsback are more complicated (but still doable?) because they require descending into init1, I think to the point(s) where out gets appended.

[chadwhitacre]

I have deps. Smooth sailing from here? 🤞

[chadwhitacre]

I have code (HEAD, diff) to compute an out parallel to lout in initfix, which either exactly matches or is a reordering of lout:

 427 final: match!
 192 final: reordered!

The spec example case is reordered as expected:

  out: b = f(), c = f(), a = c + b
 lout: c = f(), b = f(), a = c + b

So far so good!

However, flipping the switch to actually _return_ out instead of lout results in a broken build, suggesting that perhaps (and it does seem likely) there is code that depends on the buggy behavior. I intend to keep debugging, but this does raise the question: might fixing this bug be a backwards-incompatible change?

[chadwhitacre]

I have a source tree (diff) that builds cleanly and passes the test in question. 💃

$ go run test/run.go -- test/fixedbugs/issue22326.go 
$

I have a week left to work on this. I am hoping 🤞 to submit a change request in that time, but I expect it'll need some iteration, which I despair of being able to provide (until next year? ;^).

[josharian]

Awesome. Lucky for you (?) we are in the freeze part of the release cycle (https://github.com/golang/go/wiki/Go-Release-Cycle), so thorough code review and iteration has to wait for a while anyway. Do go ahead and mail your change soon, just anticipate delays. (Sorry.)

[chadwhitacre]

I've prepared a commit according to the guidelines. Unfortunately, though perhaps predictably, all.bash fails miserably. This doesn't bode well for the wider ecosystem. I suspect that this fix may need to be hidden behind a compilation flag for the foreseeable future to avoid breaking lots of code.

I'm out of time to work on this. Would you like me to start a CL with what I've got so far?

[josharian]

Yes please.

[gopherbot]

Change https://golang.org/cl/156328 mentions this issue: cmd/compile: initialize variables in the right order

[chadwhitacre]

Ftr, my first patch was buggy. I submitted a second patch, which passes the test suite.

[chadwhitacre]

Bump. Does anybody want https://go-review.googlesource.com/c/go/+/156328/?

[gopherbot]

Change https://golang.org/cl/169898 mentions this issue: cmd/compile: change sinit.go functions into methods

[gopherbot]

Change https://golang.org/cl/169899 mentions this issue: cmd/compile: move sinit.go globals into InitSchedule

[mdempsky]

What's the correct initialization order for this program?

package main

var (
    _ = f("_", b)
    a = f("a")
    b = f("b")
)

func f(s string, rest ...int) int { print(s); return 0 }

func main() { println() }

cmd/compile outputs b_a, but gccgo and go/types (according to Info.InitOrder) output ab_. I think cmd/compile is correct here.

Though notably, changing _ = f("_", b) to just _ = b causes cmd/compile to output ab; I think the correct output is still ba.

@griesemer @ianlancetaylor What do you think?

[ianlancetaylor]

I agree that b_a seems to be correct. I'm not sure why gccgo gets it wrong. The code is there to do the right thing.

[gopherbot]

Change https://golang.org/cl/170062 mentions this issue: cmd/compile: fix package initialization ordering

[griesemer]

Regarding the example here, I believe go/types follows the spec, specifically the following paragraph:

More precisely, a package-level variable is considered ready for initialization if it is not yet initialized and either has no initialization expression or its initialization expression has no dependencies on uninitialized variables. Initialization proceeds by repeatedly initializing the next package-level variable that is earliest in declaration order and ready for initialization, until there are no variables ready for initialization.

According to this (specifically the 2nd sentence), for

var (
    _ = f("_", b)
    a = f("a")
    b = f("b")
)

the next earliest (in decl. order) variable that has no dependencies is a, followed by b. After b is initialized, the next earliest variable with no uninitialized dependencies is _ . To me that suggests that the initialization order should be a, b, _, (with corresponding output ab_).

Analogously, for the 2nd example (changing _ = f("_", b) to just _ = b), the init order should be unchanged and the output should be ab.

Thus I believe both go/types and gccgo produce the correct output in this case. @ianlancetaylor Thoughts?

The first sentence in this section is perhaps misleading and should be clarified. I filed https://github.com/golang/go/issues/31292 for now.

As an aside, whether a variable is named _ or not doesn't matter. The spec should probably be more precise here as well because it talks about "declaration order" in this section while elsewhere it says that _ identifiers are not declared.

[mdempsky]

After chatting with @griesemer about this, I've changed my mind and agree that ab_ does seem to be the right behavior prescribed by the "ready for initialization" paragraph (and that gccgo and go/types are correct).

[ianlancetaylor]

I'm willing to believe that ab_ is correct.

[gopherbot]

Change https://golang.org/cl/175980 mentions this issue: spec: clarify language on package-level variable initialization

[bradfitz]

@griesemer, what remains here?

[mdempsky]

@bradfitz I need to update my cmd/compile CL. I was waiting until we'd clarified the ambiguity in #31292, which is done now.

[mdempsky]

CL 170062 is ready for review, if it's not too late in the cycle.

[griesemer]

Yes, aware of it. Thanks.

• gri

On Mon, May 20, 2019, 5:33 PM Matthew Dempsky [e-mail]
wrote:

CL 170062 is ready for review, if it's not too late in the cycle.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/golang/go/issues/22326?email_source=notifications&email_token=ACBCIT2IELKMAVQMTCWBWWLPWMKKPA5CNFSM4D7X4AKKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODV2ECVQ#issuecomment-494158166,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACBCIT3VMZEZYB6SWOUXDWTPWMKKPANCNFSM4D7X4AKA
.

[gopherbot]

Change https://golang.org/cl/179238 mentions this issue: cmd/compile: sort OAS2* declarations

[gopherbot]

Change https://golang.org/cl/179398 mentions this issue: cmd/compile: fix fmt_test.go after CL 170062