summaryrefslogtreecommitdiffstats
path: root/src/cmd/compile/internal/gc/initorder.go
blob: e2084fd03862ca8ea9f7e79557f2df1038ba9056 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
// Copyright 2019 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 (
	"bytes"
	"container/heap"
	"fmt"
)

// Package initialization
//
// Here we implement the algorithm for ordering package-level variable
// initialization. The spec is written in terms of variable
// initialization, but multiple variables initialized by a single
// assignment are handled together, so here we instead focus on
// ordering initialization assignments. Conveniently, this maps well
// to how we represent package-level initializations using the Node
// AST.
//
// Assignments are in one of three phases: NotStarted, Pending, or
// Done. For assignments in the Pending phase, we use Xoffset to
// record the number of unique variable dependencies whose
// initialization assignment is not yet Done. We also maintain a
// "blocking" map that maps assignments back to all of the assignments
// that depend on it.
//
// For example, for an initialization like:
//
//     var x = f(a, b, b)
//     var a, b = g()
//
// the "x = f(a, b, b)" assignment depends on two variables (a and b),
// so its Xoffset will be 2. Correspondingly, the "a, b = g()"
// assignment's "blocking" entry will have two entries back to x's
// assignment.
//
// Logically, initialization works by (1) taking all NotStarted
// assignments, calculating their dependencies, and marking them
// Pending; (2) adding all Pending assignments with Xoffset==0 to a
// "ready" priority queue (ordered by variable declaration position);
// and (3) iteratively processing the next Pending assignment from the
// queue, decreasing the Xoffset of assignments it's blocking, and
// adding them to the queue if decremented to 0.
//
// As an optimization, we actually apply each of these three steps for
// each assignment. This yields the same order, but keeps queue size
// down and thus also heap operation costs.

// Static initialization phase.
// These values are stored in two bits in Node.flags.
const (
	InitNotStarted = iota
	InitDone
	InitPending
)

type InitOrder struct {
	// blocking maps initialization assignments to the assignments
	// that depend on it.
	blocking map[*Node][]*Node

	// ready is the queue of Pending initialization assignments
	// that are ready for initialization.
	ready declOrder
}

// initOrder computes initialization order for a list l of
// package-level declarations (in declaration order) and outputs the
// corresponding list of statements to include in the init() function
// body.
func initOrder(l []*Node) []*Node {
	s := InitSchedule{
		initplans: make(map[*Node]*InitPlan),
		inittemps: make(map[*Node]*Node),
	}
	o := InitOrder{
		blocking: make(map[*Node][]*Node),
	}

	// Process all package-level assignment in declaration order.
	for _, n := range l {
		switch n.Op {
		case OAS, OAS2DOTTYPE, OAS2FUNC, OAS2MAPR, OAS2RECV:
			o.processAssign(n)
			o.flushReady(s.staticInit)
		case ODCLCONST, ODCLFUNC, ODCLTYPE:
			// nop
		default:
			Fatalf("unexpected package-level statement: %v", n)
		}
	}

	// Check that all assignments are now Done; if not, there must
	// have been a dependency cycle.
	for _, n := range l {
		switch n.Op {
		case OAS, OAS2DOTTYPE, OAS2FUNC, OAS2MAPR, OAS2RECV:
			if n.Initorder() != InitDone {
				// If there have already been errors
				// printed, those errors may have
				// confused us and there might not be
				// a loop. Let the user fix those
				// first.
				if nerrors > 0 {
					errorexit()
				}

				findInitLoopAndExit(firstLHS(n), new([]*Node), make(map[*Node]bool))
				Fatalf("initialization unfinished, but failed to identify loop")
			}
		}
	}

	// Invariant consistency check. If this is non-zero, then we
	// should have found a cycle above.
	if len(o.blocking) != 0 {
		Fatalf("expected empty map: %v", o.blocking)
	}

	return s.out
}

func (o *InitOrder) processAssign(n *Node) {
	if n.Initorder() != InitNotStarted || n.Xoffset != BADWIDTH {
		Fatalf("unexpected state: %v, %v, %v", n, n.Initorder(), n.Xoffset)
	}

	n.SetInitorder(InitPending)
	n.Xoffset = 0

	// Compute number of variable dependencies and build the
	// inverse dependency ("blocking") graph.
	for dep := range collectDeps(n, true) {
		defn := dep.Name.Defn
		// Skip dependencies on functions (PFUNC) and
		// variables already initialized (InitDone).
		if dep.Class() != PEXTERN || defn.Initorder() == InitDone {
			continue
		}
		n.Xoffset++
		o.blocking[defn] = append(o.blocking[defn], n)
	}

	if n.Xoffset == 0 {
		heap.Push(&o.ready, n)
	}
}

// flushReady repeatedly applies initialize to the earliest (in
// declaration order) assignment ready for initialization and updates
// the inverse dependency ("blocking") graph.
func (o *InitOrder) flushReady(initialize func(*Node)) {
	for o.ready.Len() != 0 {
		n := heap.Pop(&o.ready).(*Node)
		if n.Initorder() != InitPending || n.Xoffset != 0 {
			Fatalf("unexpected state: %v, %v, %v", n, n.Initorder(), n.Xoffset)
		}

		initialize(n)
		n.SetInitorder(InitDone)
		n.Xoffset = BADWIDTH

		blocked := o.blocking[n]
		delete(o.blocking, n)

		for _, m := range blocked {
			m.Xoffset--
			if m.Xoffset == 0 {
				heap.Push(&o.ready, m)
			}
		}
	}
}

// findInitLoopAndExit searches for an initialization loop involving variable
// or function n. If one is found, it reports the loop as an error and exits.
//
// path points to a slice used for tracking the sequence of
// variables/functions visited. Using a pointer to a slice allows the
// slice capacity to grow and limit reallocations.
func findInitLoopAndExit(n *Node, path *[]*Node, ok map[*Node]bool) {
	for i, x := range *path {
		if x == n {
			reportInitLoopAndExit((*path)[i:])
			return
		}
	}

	// There might be multiple loops involving n; by sorting
	// references, we deterministically pick the one reported.
	refers := collectDeps(n.Name.Defn, false).Sorted(func(ni, nj *Node) bool {
		return ni.Pos.Before(nj.Pos)
	})

	*path = append(*path, n)
	for _, ref := range refers {
		// Short-circuit variables that were initialized.
		if ref.Class() == PEXTERN && ref.Name.Defn.Initorder() == InitDone || ok[ref] {
			continue
		}
		findInitLoopAndExit(ref, path, ok)
	}

	// n is not involved in a cycle.
	// Record that fact to avoid checking it again when reached another way,
	// or else this traversal will take exponential time traversing all paths
	// through the part of the package's call graph implicated in the cycle.
	ok[n] = true

	*path = (*path)[:len(*path)-1]
}

// reportInitLoopAndExit reports and initialization loop as an error
// and exits. However, if l is not actually an initialization loop, it
// simply returns instead.
func reportInitLoopAndExit(l []*Node) {
	// Rotate loop so that the earliest variable declaration is at
	// the start.
	i := -1
	for j, n := range l {
		if n.Class() == PEXTERN && (i == -1 || n.Pos.Before(l[i].Pos)) {
			i = j
		}
	}
	if i == -1 {
		// False positive: loop only involves recursive
		// functions. Return so that findInitLoop can continue
		// searching.
		return
	}
	l = append(l[i:], l[:i]...)

	// TODO(mdempsky): Method values are printed as "T.m-fm"
	// rather than "T.m". Figure out how to avoid that.

	var msg bytes.Buffer
	fmt.Fprintf(&msg, "initialization loop:\n")
	for _, n := range l {
		fmt.Fprintf(&msg, "\t%v: %v refers to\n", n.Line(), n)
	}
	fmt.Fprintf(&msg, "\t%v: %v", l[0].Line(), l[0])

	yyerrorl(l[0].Pos, msg.String())
	errorexit()
}

// collectDeps returns all of the package-level functions and
// variables that declaration n depends on. If transitive is true,
// then it also includes the transitive dependencies of any depended
// upon functions (but not variables).
func collectDeps(n *Node, transitive bool) NodeSet {
	d := initDeps{transitive: transitive}
	switch n.Op {
	case OAS:
		d.inspect(n.Right)
	case OAS2DOTTYPE, OAS2FUNC, OAS2MAPR, OAS2RECV:
		d.inspect(n.Right)
	case ODCLFUNC:
		d.inspectList(n.Nbody)
	default:
		Fatalf("unexpected Op: %v", n.Op)
	}
	return d.seen
}

type initDeps struct {
	transitive bool
	seen       NodeSet
}

func (d *initDeps) inspect(n *Node)     { inspect(n, d.visit) }
func (d *initDeps) inspectList(l Nodes) { inspectList(l, d.visit) }

// visit calls foundDep on any package-level functions or variables
// referenced by n, if any.
func (d *initDeps) visit(n *Node) bool {
	switch n.Op {
	case ONAME:
		if n.isMethodExpression() {
			d.foundDep(asNode(n.Type.FuncType().Nname))
			return false
		}

		switch n.Class() {
		case PEXTERN, PFUNC:
			d.foundDep(n)
		}

	case OCLOSURE:
		d.inspectList(n.Func.Closure.Nbody)

	case ODOTMETH, OCALLPART:
		d.foundDep(asNode(n.Type.FuncType().Nname))
	}

	return true
}

// foundDep records that we've found a dependency on n by adding it to
// seen.
func (d *initDeps) foundDep(n *Node) {
	// Can happen with method expressions involving interface
	// types; e.g., fixedbugs/issue4495.go.
	if n == nil {
		return
	}

	// Names without definitions aren't interesting as far as
	// initialization ordering goes.
	if n.Name.Defn == nil {
		return
	}

	if d.seen.Has(n) {
		return
	}
	d.seen.Add(n)
	if d.transitive && n.Class() == PFUNC {
		d.inspectList(n.Name.Defn.Nbody)
	}
}

// declOrder implements heap.Interface, ordering assignment statements
// by the position of their first LHS expression.
//
// N.B., the Pos of the first LHS expression is used because because
// an OAS node's Pos may not be unique. For example, given the
// declaration "var a, b = f(), g()", "a" must be ordered before "b",
// but both OAS nodes use the "=" token's position as their Pos.
type declOrder []*Node

func (s declOrder) Len() int           { return len(s) }
func (s declOrder) Less(i, j int) bool { return firstLHS(s[i]).Pos.Before(firstLHS(s[j]).Pos) }
func (s declOrder) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }

func (s *declOrder) Push(x interface{}) { *s = append(*s, x.(*Node)) }
func (s *declOrder) Pop() interface{} {
	n := (*s)[len(*s)-1]
	*s = (*s)[:len(*s)-1]
	return n
}

// firstLHS returns the first expression on the left-hand side of
// assignment n.
func firstLHS(n *Node) *Node {
	switch n.Op {
	case OAS:
		return n.Left
	case OAS2DOTTYPE, OAS2FUNC, OAS2RECV, OAS2MAPR:
		return n.List.First()
	}

	Fatalf("unexpected Op: %v", n.Op)
	return nil
}