New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

cmd/compile: incorrect package initialization order for spec example #22326

Open
chadwhitacre opened this Issue Oct 18, 2017 · 20 comments

Comments

Projects
None yet
5 participants
@chadwhitacre

chadwhitacre commented Oct 18, 2017

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:

the initialization order is <code>d</code>, <code>b</code>, <code>c</code>, <code>a</code>.

@griesemer

This comment has been minimized.

Contributor

griesemer commented Oct 18, 2017

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.

@griesemer griesemer changed the title from spec: Package initialization example is confusing (maybe even wrong?) to cmd/compile: incorrect package initialization order for spec example Oct 18, 2017

@chadwhitacre

This comment has been minimized.

chadwhitacre commented Oct 18, 2017

for some reason

Hmm ... something related to initfix? 🤔

// initfix computes initialization order for a list l of top-level
// declarations and outputs the corresponding list of statements
// to include in the init() function body.
func initfix(l []*Node) []*Node {
var lout []*Node
initplans = make(map[*Node]*InitPlan)
lno := lineno
initreorder(l, &lout)
lineno = lno
initplans = nil
return lout
}

@griesemer

This comment has been minimized.

Contributor

griesemer commented Oct 18, 2017

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

@chadwhitacre

This comment has been minimized.

chadwhitacre commented Oct 18, 2017

@griesemer Cool, no worries. Verbose dive log on chadwhitacre#1, will report back here if I find anything. :)

@chadwhitacre

This comment has been minimized.

chadwhitacre commented Oct 18, 2017

@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

This comment has been minimized.

Contributor

ianlancetaylor commented Oct 18, 2017

For the record, gccgo gets this right.

@griesemer

This comment has been minimized.

Contributor

griesemer commented Oct 18, 2017

@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

This comment has been minimized.

chadwhitacre commented Oct 25, 2017

@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: Mainfninitinitfixinitreorder. 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

This comment has been minimized.

Member

mdempsky commented Oct 25, 2017

@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

This comment has been minimized.

chadwhitacre commented Oct 26, 2017

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

This comment has been minimized.

chadwhitacre commented Oct 26, 2017

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

This comment has been minimized.

chadwhitacre commented Oct 31, 2017

Here are:

  • example.go, the spec example without the d (not needed to reproduce the bug),
  • a patch (against 3e887ff) 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 mdempsky modified the milestones: Go1.10, Go1.11 Nov 29, 2017

@mdempsky

This comment has been minimized.

Member

mdempsky commented Nov 29, 2017

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

@chadwhitacre

This comment has been minimized.

chadwhitacre commented May 31, 2018

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

This comment has been minimized.

chadwhitacre commented May 31, 2018

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

@chadwhitacre

This comment has been minimized.

chadwhitacre commented May 31, 2018

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

@josharian

This comment has been minimized.

Contributor

josharian commented Jun 1, 2018

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.

@ianlancetaylor ianlancetaylor modified the milestones: Go1.11, Go1.12 Jun 30, 2018

@chadwhitacre

This comment has been minimized.

chadwhitacre commented Nov 30, 2018

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

This comment has been minimized.

chadwhitacre commented Dec 3, 2018

I have deps. Smooth sailing from here? 🤞

@chadwhitacre

This comment has been minimized.

chadwhitacre commented Dec 7, 2018

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?

@griesemer griesemer modified the milestones: Go1.12, Go1.13 Dec 11, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment