[-v] cmd/compile: incorrect package initialization order for spec example

chadwhitacre commented 5 years ago

Picking up from #1 ...

Todo

[x] determine state needed in walk in order to generate lout properly
[x] populate the state!
[x] generate lout properly
[x] clean up any code elsewhere in Go that depends on this buggy behavior

Then

[ ] find a nicer way to initialize Deps
[ ] consider bool instead of struct{} for deps
[ ] unit test Deps
[ ] I guess static variables are added directly so shouldn't be included?
[ ] ensure all sorts of assignments are covered, expand test suite
[ ] make sure pointer usage is correct
[x] protect against infinite looping
[ ] check performance
[ ] sort dcls by number of deps?
[ ] test traversing across multiple functions
[ ] test different GOARCH/GOOS?
[ ] run whole test suite

Meanwhile

Finally

[ ] https://github.com/golang/go/wiki/CodeReviewComments
[ ] https://golang.org/doc/contribute.html
[ ] copyright notice at top of files?

Further

[ ] investigate OAS2 and OASOP—what happens if I x,y = 1,2 or x = 1; x += 1 in xtop?
[ ] investigate Ninit—does initreorder ever actually recurse? Can we get some test coverage reporting?
[ ] investigate nf—what if we have init functions but no statements? really return early?

chadwhitacre commented 5 years ago

Okay! Failing test. Now what? 😬

chadwhitacre commented 5 years ago

Are there some side-effects to initreorder (beyond sinit.go)? If not then I am thinking about maybe starting a rewrite there. Can we store state in some intermediate data structure (a la initplans), which we update while walking and then use to generate the final lout?

chadwhitacre commented 5 years ago

Here are the functions in sinit.go:

addMapEntries
addvalue
anylit
fixedlit
foundinitloop
genAsStatic
getdyn
getlit
init1
init2
init2list
initfix
initplan
initreorder
isLiteral
isStaticCompositeLiteral
isZero
isvaluelit
litas
maplit
oaslit
slicelit
stataddr
staticassign
staticcopy
staticinit
staticname

chadwhitacre commented 5 years ago

Just looking at the requirements, my first thought is to keep a) a deque of variable names in declaration order, and b) a map of variable names to stacks of requirements for each variable. When we see a LHS we push the variable name onto (a) and file an empty stack under the variable name in (b). During RHS processing we push dependencies onto the stack in (b). After processing a complete declaration we flatten (a) and (b) by recursing through them and appending to the out list when we find an empty stack in (b).

https://github.com/chadwhitacre/go/issues/1#issuecomment-341645348

chadwhitacre commented 5 years ago

Here is global state:

initlist
initplans
inittemps

And here is the call graph (↺ indicates a nested recursion):

initfix
  initreorder
    initreorder
    init1
      init1
      init2
        init1 ↺
          init2list
            init2 ↺
      init2list
        init2
      foundinitloop
      staticinit
        staticassign
          staticassign
          initplan
            addvalue
              initplan ↺
              isZero
                isZero
              isvaluelit
          isZero
            isZero
          stataddr
            getlit
          staticcopy
            staticcopy
            isZero
              isZero
            staticassign ↺
          staticname

Aaaand here is a call graph coming in from walk.go(!) (↺ indicates a nested recursion):

oaslit
  anylit
    anylit
    slicelit
      fixedlit
        fixedlit
        genAsStatic
          stataddr
        isLiteral
        slicelit ↺
      getdyn
        getdyn
        isLiteral
      isLiteral
      stataddr
        stataddr
        getlit
      staticname
    fixedlit
    staticname
  maplit
    addMapEntries
    isStaticCompositeLiteral
      isStaticCompositeLiteral
    litas
    fixedlit
    staticname

chadwhitacre commented 5 years ago

Yeah, okay, getting back into it: right now declarations are sorted by a) reverse dependency and b) RHS appearance (i.e., usage or reference), but they need to be sorted by a) reverse dependency and b) LHS appearance (i.e., declaration).

That is, b and c still need to come before a, but b needs to come before c.

chadwhitacre commented 5 years ago

With 5cb3111:

$ pwd
/Users/whit537/workbench/go/src/github.com/golang/go/src
$ ./make.bash && ../bin/go run ../test/run.go -- ../test/fixedbugs/issue22326.go
[...]
# go run run.go -- ../test/fixedbugs/issue22326.go
exit status 1
# command-line-arguments
declaring a
declaring c
declaring d
declaring b
panic: b is 5 not 4

goroutine 1 [running]:
main.expect(...)
        /Users/whit537/workbench/go/src/github.com/golang/go/test/fixedbugs/issue22326.go:21
main.main()
        /Users/whit537/workbench/go/src/github.com/golang/go/test/fixedbugs/issue22326.go:26 +0x267
exit status 2

FAIL    ../test/fixedbugs/issue22326.go 2.070s
exit status 1
$

a c d b is not the order I expected here! I expected a b c d. 🤔

chadwhitacre commented 5 years ago

With 9e14150:

# go run run.go -- ../test/fixedbugs/issue22326.go
exit status 1
# command-line-arguments
seeing a
declaring a
declaring c
declaring d
declaring b
seeing b
seeing c
seeing d
panic: b is 5 not 4

goroutine 1 [running]:
main.expect(...)
        /Users/whit537/workbench/go/src/github.com/golang/go/test/fixedbugs/issue22326.go:21
main.main()
        /Users/whit537/workbench/go/src/github.com/golang/go/test/fixedbugs/issue22326.go:26 +0x267
exit status 2

FAIL    ../test/fixedbugs/issue22326.go 1.083s
exit status 1
$

chadwhitacre commented 5 years ago

36d9e34

0 declaring a
first time using a
first time using c
first time using d
first time using b
0 declaring b
0 declaring c
0 declaring d

chadwhitacre commented 5 years ago

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: []

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)

chadwhitacre commented 5 years ago

c2cebfe:

declaring a at depth 0
first time using a
first time using c
first time using d
first time using b
declaring b at depth 0
declaring c at depth 0
declaring d at depth 0
 out: a, b, c, d
lout: c, b, a

chadwhitacre commented 5 years ago

Bringing back append logging in 91b85e4 .

declaring a at depth 0
first time using a
first time using c
first time using d
appending (1) c
first time using b
appending (1) b
appending (1) a
declaring b at depth 0
declaring c at depth 0
declaring d at depth 0
dcls: a, b, c, d
 out: a, b, c, d
lout: c, b, a

chadwhitacre commented 5 years ago

Here's logging that includes the d = 3 assignment: 02a1c00.

declaring a at depth 0
expecting a
expecting c
expecting d
s'initing d
appending c at point (1)
expecting b
appending b at point (1)
appending a at point (1)
declaring b at depth 0
declaring c at depth 0
declaring d at depth 0
dcls: a, b, c, d
 out: a, b, c, d
lout: c, b, a

chadwhitacre commented 5 years ago

Alright, sooo ... I'm pretty sure expecting always comes before appending/s'initing. I think that's the time to populate keys in dep/depsback. But ... values?

chadwhitacre commented 5 years ago

Has to be append/s'init time. What does that look like?

When I am appending c what can I say about the dependencies that c is a part of? I want to say one or both of:

deps:
    a: [c]
    c: [d]

depsback:
    c: [a]
    d: [c]

(It's trivial to populate both deps and depsback at the same time.)

chadwhitacre commented 5 years ago

Progress! Now how about b expecting d? That's the one we need!

4e75238

declaring a at depth 0
root is expecting a
a is expecting c
c is expecting d
s'initing d
appending c at point (1)
a is expecting b
appending b at point (1)
appending a at point (1)
declaring b at depth 0
declaring c at depth 0
declaring d at depth 0
dcls: a, b, c, d
 out: a, b, c, d
lout: c, b, a

chadwhitacre commented 5 years ago

I'm referring to https://github.com/golang/go/issues/22326#issuecomment-443085177 in another tab through all of this, btw.

chadwhitacre commented 5 years ago

ea56f22 🤔

declaring a at depth 0
root is expecting a
a is expecting c
c is expecting d
s'initing d
already done: d
already done: d
already done: d
already done: f
appending c at point (1)
a is expecting b
already done: f
appending b at point (1)
already done: c
already done: b
appending a at point (1)
declaring b at depth 0
declaring c at depth 0
declaring d at depth 0
dcls: a, b, c, d
 out: a, b, c, d
lout: c, b, a

chadwhitacre commented 5 years ago

7c1eca0 💃

declaring a at depth 0
root is expecting a
a is expecting c
c is expecting function f
f is expecting d
s'initing d
already done: d
already done: d
already done: d
already done: f
appending c at point (1)
a is expecting b
already done: f
appending b at point (1)
already done: c
already done: b
appending a at point (1)
declaring b at depth 0
declaring c at depth 0
declaring d at depth 0
dcls: a, b, c, d
 out: a, b, c, d
lout: c, b, a

chadwhitacre commented 5 years ago

Alright, so we can get from c to d through f, but still where is b is expecting function f?

chadwhitacre commented 5 years ago

Got it! 😍 💃

6504037

declaring a at depth 0
root is expecting a
a is expecting c
c is expecting f
f is expecting d
s'initing d
f is expecting d
f is expecting d
f is expecting d
f is expecting d
appending c at point (1)
a is expecting b
b is expecting f
appending b at point (1)
appending a at point (1)
root is expecting c
root is expecting b
declaring b at depth 0
root is expecting b
root is expecting f
declaring c at depth 0
root is expecting c
root is expecting f
declaring d at depth 0
root is expecting d
dcls: a, b, c, d
 out: a, b, c, d
lout: c, b, a

chadwhitacre commented 5 years ago

💃💃💃💃💃💃

81f01ab

fwd:
        a: [c, b]
        c: [f]
        f: [d]
        b: [f]
bck:
        f: [c, b]
        d: [f]
        b: [a]
        a: []
        c: [a]

chadwhitacre commented 5 years ago

cb6308f

dcls: a, b, c, d
fwd:
        a: [c, b]
        c: [f]
        f: [d]
        b: [f]
bck:
        a: []
        c: [a]
        f: [b, c]
        d: [f]
        b: [a]
out: 
processing a (=) ... skipped!
processing b (=) ... skipped!
processing c (=) ... skipped!
processing d (=) ... go!
dcls: a, b, c, d
fwd:
        a: [b, c]
        c: [f]
        f: [d]
        b: [f]
bck:
        a: []
        c: [a]
        f: [c, b]
        d: [f]
        b: [a]
 out: d
lout: c, b, a
panic: b is 5 not 4

chadwhitacre commented 5 years ago

f5cdd46

dcls: a, b, c, d
fwd:
        a: [c, b]
        c: [f]
        f: [d]
        b: [f]
bck:
        a: []
        c: [a]
        f: [c, b]
        d: [f]
        b: [a]
out:
f is a NAME and Func is &{<S>    [] [] [] 0 map[] <nil> <N> 0 <N> <N> <nil> 0xc000086bc0 0 {0 0} {0 0} 0 128 <nil>}
dcls: a, b, c
fwd:
        a: [c, b]
        c: [f]
        f: [d]
        b: [f]
bck:
        a: []
        c: [a]
        f: [b, c]
        d: [f]
        b: [a]
 out: d
lout: c, b, a
panic: b is 5 not 4

chadwhitacre commented 5 years ago

!!!!!!

removing c
removing c from fwd[a]
removing a from bck[c]
 dcls: a
  fwd:
        a: []
        c: []
        f: []
        b: []
  bck:
        a: []
        c: []
        f: []
        d: []
        b: []
  out: d, b, c
a ready? true
removing a
 dcls: 
  fwd:
        a: []
        c: []
        f: []
        b: []
  bck:
        d: []
        b: []
        a: []
        c: []
        f: []
  out: d, b, c, a
 lout: c, b, a
panic: b is 5 not 4

chadwhitacre commented 5 years ago

😍 😍 😍 😍 😍 😍 😍 😍 😍 😍 😍

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

chadwhitacre commented 5 years ago

That's acbf979. Still a ways to go, apparently a) lout != out for other cases, and b) there are some infinite loops.

chadwhitacre commented 5 years ago

Okay, trying to button together out and lout. Level-set with master 048c916:

$ make.bash
Building Go cmd/dist using /usr/local/Cellar/go/1.10.1/libexec.
Building Go toolchain1 using /usr/local/Cellar/go/1.10.1/libexec.
Building Go bootstrap cmd/go (go_bootstrap) using Go toolchain1.
Building Go toolchain2 using go_bootstrap and Go toolchain1.
Building Go toolchain3 using go_bootstrap and Go toolchain2.
Building packages and commands for darwin/amd64.
---
Installed Go for darwin/amd64 in /Users/whit537/workbench/go/src/github.com/golang/go
Installed commands in /Users/whit537/workbench/go/src/github.com/golang/go/bin

chadwhitacre commented 5 years ago

Building out some logging on master bbc8369849e890edae3a1eb7dfbee5e04894744d:

https://github.com/chadwhitacre/go/blob/bbc8369849e890edae3a1eb7dfbee5e04894744d/src/make.log

chadwhitacre commented 5 years ago

Okay, I have lined up logging between the 22326 (this one) and 22326-alt branches. That shows that this 22326 branch is able to generate lout just like on master.

chadwhitacre commented 5 years ago

Getting there! Looks like something is up with deps removal? 🤔

686c59a

$ grep '^final' make.log | sort | uniq -c
 106 final result: infloop and mismatch!
 406 final result: match!
 105 final result: reordered!
$

chadwhitacre commented 5 years ago

The issue is with function transitivity. If a variable depends only on functions that do not themselves depend on non-functions, it is "ready".

----------------------------------------------------
file: src/hash/crc32/crc32.go
 dcls: IEEETable (= CALLFUNC)
  fwd:  
        IEEETable: [simpleMakeTable]
        simpleMakeTable: [simplePopulateTable]
  bck:  
        IEEETable: []
        simpleMakeTable: [IEEETable]
        simplePopulateTable: [simpleMakeTable]
  out:
IEEETable ready? false

chadwhitacre commented 5 years ago

Could we get simplePopulateTable: [] in fwd?

chadwhitacre commented 5 years ago

We could preprocess deps to remove anything in bck that isn't in fwd. Seems cleaner if we can deps.add(simplePopulateTable) somehow tho ... 🤔

chadwhitacre commented 5 years ago

Closer with ceb4a7a ...

   5 final: infloop and mismatch!
 437 final: match!
 175 final: reordered!

... but the spec example is reordered incorrectly. 🤔

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

chadwhitacre commented 5 years ago

a33bed0

  51 final: infloop and mismatch!
 428 final: match!
 138 final: reordered!

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

chadwhitacre commented 5 years ago

^^^ That handles the IEE case correctly, new one to fix is globalRand/rngCooked ...

chadwhitacre commented 5 years ago

76214da

  16 final: infloop and mismatch!
 437 final: match!
 164 final: reordered!

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

I guess I'm trying to squeeze out the infloops and then think about proper ordering? Or maybe I should shake out the ordering bug next?

chadwhitacre commented 5 years ago

The two seem linked! ☺️

 file: test/fixedbugs/issue22326.go
 dcls: c (= CALLFUNC), b (= CALLFUNC), a (= +)
  fwd:
    d: []
    b: [f]
    a: [c, b]
    c: [f]
    f: [d]
  bck:
    a: []
    c: [a]
    f: [c, b]
    d: [f]
    b: [a]
pruning to map[a = c + b:{} b = f():{} c = f():{}]
removing d
removing d from fwd[f]
removing f from bck[d]
removing f
removing f from fwd[c]
removing c from bck[f]
removing f from fwd[b]
removing b from bck[f]
removing b
removing b from fwd[a]
removing a from bck[b]
done pruning
 dcls: c (= CALLFUNC), b (= CALLFUNC), a (= +)
  fwd:
    c: []
    f: []
    d: []
    b: []
    a: [c]
  bck:
    a: []
    c: [a]
    f: []
    d: []
    b: []
  out: 
c ready? true
removing c
removing c from fwd[a]
removing a from bck[c]
a ready? true
removing a
b ready? true
removing b
 dcls: 
  fwd:
    a: []
    c: []
    f: []
    d: []
    b: []
  bck:
    a: []
    c: []
    f: []
    d: []
    b: []
final: reordered!
  out: c (= CALLFUNC), a (= +), b (= CALLFUNC)
 lout: c (= CALLFUNC), b (= CALLFUNC), a (= +)
panic: b is 5 not 4

goroutine 1 [running]:
main.expect(...)
    /Users/whit537/workbench/go/src/github.com/golang/go/test/fixedbugs/issue22326.go:21
main.main()
    /Users/whit537/workbench/go/src/github.com/golang/go/test/fixedbugs/issue22326.go:26 +0x267
exit status 2

FAIL    ../test/fixedbugs/issue22326.go 0.514s
exit status 1

chadwhitacre commented 5 years ago

need an ordering in declaration order: is reverse(lout) that?
if b is removed why isn't c?

chadwhitacre commented 5 years ago

We need two things: declaration order and dependency order. We have declaration order in l. We the dependency graph in deps.

chadwhitacre commented 5 years ago

Huh. 5ebf2e1c705b0183c4eb49b74cf2fe1897b85498 is close to 76214da but not exactly the same. ¯\_(ツ)_/¯

  15 final: infloop and mismatch!
 437 final: match!
 167 final: reordered!

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

chadwhitacre commented 5 years ago

162dd86

Subtle differences!

  17 final: infloop and mismatch!
 437 final: match!
 165 final: reordered!

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

chadwhitacre commented 5 years ago

😍 😍 😍 😍 😍 😍

 251 final: match!
 308 final: mismatch!

c5f62b9

chadwhitacre commented 5 years ago

Oh! Hrm. mismatch, not reordered. 😕

chadwhitacre commented 5 years ago

87e453409aad6fceec7a10f4c7b2546757a7d212

Looks like sorted as implemented is not adequate, because it doesn't include nodes that are created under staticinit. 😖

  70 final: infloop and mismatch!
 308 final: match!
 149 final: mismatch!
  32 final: reordered!

go tool dist: FAILED: /Users/whit537/workbench/go/src/github.com/golang/go/pkg/tool/darwin_amd64/go_bootstrap install -gcflags=all= -ldflags=all= std cmd: exit status 2

chadwhitacre commented 5 years ago

If they're all static then they don't depend on anything, right? So we can just front-load them?

chadwhitacre commented 5 years ago

260df4c

  13 final: infloop and mismatch!
 388 final: match!
 158 final: reordered!

go tool dist: FAILED: /Users/whit537/workbench/go/src/github.com/golang/go/pkg/tool/darwin_amd64/go_bootstrap install -gcflags=all= -ldflags=all= std cmd: exit status 2

chadwhitacre commented 5 years ago

OAS2!

chadwhitacre commented 5 years ago

1e94a32

 387 final: match!
 172 final: reordered!

Phew! But still ...

go tool dist: FAILED: /Users/whit537/workbench/go/src/github.com/golang/go/pkg/tool/darwin_amd64/go_bootstrap install -gcflags=all= -ldflags=all= std cmd: exit status 2

chadwhitacre / go