1 // Code generated by "go test -run=Generate -write=all"; DO NOT EDIT.
2 // Source: ../../cmd/compile/internal/types2/initorder.go
3 4 // Copyright 2014 The Go Authors. All rights reserved.
5 // Use of this source code is governed by a BSD-style
6 // license that can be found in the LICENSE file.
7 8 package types
9 10 import (
11 "cmp"
12 "container/heap"
13 "fmt"
14 . "internal/types/errors"
15 "slices"
16 "sort"
17 )
18 19 // initOrder computes the Info.InitOrder for package variables.
20 func (check *Checker) initOrder() {
21 // An InitOrder may already have been computed if a package is
22 // built from several calls to (*Checker).Files. Clear it.
23 check.Info.InitOrder = check.Info.InitOrder[:0]
24 25 // Compute the object dependency graph and initialize
26 // a priority queue with the list of graph nodes.
27 pq := nodeQueue(dependencyGraph(check.objMap))
28 heap.Init(&pq)
29 30 const debug = false
31 if debug {
32 fmt.Printf("Computing initialization order for %s\n\n", check.pkg)
33 fmt.Println("Object dependency graph:")
34 for obj, d := range check.objMap {
35 // only print objects that may appear in the dependency graph
36 if obj, _ := obj.(dependency); obj != nil {
37 if len(d.deps) > 0 {
38 fmt.Printf("\t%s depends on\n", obj.Name())
39 for dep := range d.deps {
40 fmt.Printf("\t\t%s\n", dep.Name())
41 }
42 } else {
43 fmt.Printf("\t%s has no dependencies\n", obj.Name())
44 }
45 }
46 }
47 fmt.Println()
48 49 fmt.Println("Transposed object dependency graph (functions eliminated):")
50 for _, n := range pq {
51 fmt.Printf("\t%s depends on %d nodes\n", n.obj.Name(), n.ndeps)
52 for p := range n.pred {
53 fmt.Printf("\t\t%s is dependent\n", p.obj.Name())
54 }
55 }
56 fmt.Println()
57 58 fmt.Println("Processing nodes:")
59 }
60 61 // Determine initialization order by removing the highest priority node
62 // (the one with the fewest dependencies) and its edges from the graph,
63 // repeatedly, until there are no nodes left.
64 // In a valid Go program, those nodes always have zero dependencies (after
65 // removing all incoming dependencies), otherwise there are initialization
66 // cycles.
67 emitted := make(map[*declInfo]bool)
68 for len(pq) > 0 {
69 // get the next node
70 n := heap.Pop(&pq).(*graphNode)
71 72 if debug {
73 fmt.Printf("\t%s (src pos %d) depends on %d nodes now\n",
74 n.obj.Name(), n.obj.order(), n.ndeps)
75 }
76 77 // if n still depends on other nodes, we have a cycle
78 if n.ndeps > 0 {
79 cycle := findPath(check.objMap, n.obj, n.obj, make(map[Object]bool))
80 // If n.obj is not part of the cycle (e.g., n.obj->b->c->d->c),
81 // cycle will be nil. Don't report anything in that case since
82 // the cycle is reported when the algorithm gets to an object
83 // in the cycle.
84 // Furthermore, once an object in the cycle is encountered,
85 // the cycle will be broken (dependency count will be reduced
86 // below), and so the remaining nodes in the cycle don't trigger
87 // another error (unless they are part of multiple cycles).
88 if cycle != nil {
89 check.reportCycle(cycle)
90 }
91 // Ok to continue, but the variable initialization order
92 // will be incorrect at this point since it assumes no
93 // cycle errors.
94 }
95 96 // reduce dependency count of all dependent nodes
97 // and update priority queue
98 for p := range n.pred {
99 p.ndeps--
100 heap.Fix(&pq, p.index)
101 }
102 103 // record the init order for variables with initializers only
104 v, _ := n.obj.(*Var)
105 info := check.objMap[v]
106 if v == nil || !info.hasInitializer() {
107 continue
108 }
109 110 // n:1 variable declarations such as: a, b = f()
111 // introduce a node for each lhs variable (here: a, b);
112 // but they all have the same initializer - emit only
113 // one, for the first variable seen
114 if emitted[info] {
115 continue // initializer already emitted, if any
116 }
117 emitted[info] = true
118 119 infoLhs := info.lhs // possibly nil (see declInfo.lhs field comment)
120 if infoLhs == nil {
121 infoLhs = []*Var{v}
122 }
123 init := &Initializer{infoLhs, info.init}
124 check.Info.InitOrder = append(check.Info.InitOrder, init)
125 }
126 127 if debug {
128 fmt.Println()
129 fmt.Println("Initialization order:")
130 for _, init := range check.Info.InitOrder {
131 fmt.Printf("\t%s\n", init)
132 }
133 fmt.Println()
134 }
135 }
136 137 // findPath returns the (reversed) list of objects []Object{to, ... from}
138 // such that there is a path of object dependencies from 'from' to 'to'.
139 // If there is no such path, the result is nil.
140 func findPath(objMap map[Object]*declInfo, from, to Object, seen map[Object]bool) []Object {
141 if seen[from] {
142 return nil
143 }
144 seen[from] = true
145 146 // sort deps for deterministic result
147 var deps []Object
148 for d := range objMap[from].deps {
149 deps = append(deps, d)
150 }
151 sort.Slice(deps, func(i, j int) bool {
152 return deps[i].order() < deps[j].order()
153 })
154 155 for _, d := range deps {
156 if d == to {
157 return []Object{d}
158 }
159 if P := findPath(objMap, d, to, seen); P != nil {
160 return append(P, d)
161 }
162 }
163 164 return nil
165 }
166 167 // reportCycle reports an error for the given cycle.
168 func (check *Checker) reportCycle(cycle []Object) {
169 obj := cycle[0]
170 171 // report a more concise error for self references
172 if len(cycle) == 1 {
173 check.errorf(obj, InvalidInitCycle, "initialization cycle: %s refers to itself", obj.Name())
174 return
175 }
176 177 err := check.newError(InvalidInitCycle)
178 err.addf(obj, "initialization cycle for %s", obj.Name())
179 // "cycle[i] refers to cycle[j]" for (i,j) = (0,n-1), (n-1,n-2), ..., (1,0) for len(cycle) = n.
180 for j := len(cycle) - 1; j >= 0; j-- {
181 next := cycle[j]
182 err.addf(obj, "%s refers to %s", obj.Name(), next.Name())
183 obj = next
184 }
185 err.report()
186 }
187 188 // ----------------------------------------------------------------------------
189 // Object dependency graph
190 191 // A dependency is an object that may be a dependency in an initialization
192 // expression. Only constants, variables, and functions can be dependencies.
193 // Constants are here because constant expression cycles are reported during
194 // initialization order computation.
195 type dependency interface {
196 Object
197 isDependency()
198 }
199 200 // A graphNode represents a node in the object dependency graph.
201 // Each node p in n.pred represents an edge p->n, and each node
202 // s in n.succ represents an edge n->s; with a->b indicating that
203 // a depends on b.
204 type graphNode struct {
205 obj dependency // object represented by this node
206 pred, succ nodeSet // consumers and dependencies of this node (lazily initialized)
207 index int // node index in graph slice/priority queue
208 ndeps int // number of outstanding dependencies before this object can be initialized
209 }
210 211 // cost returns the cost of removing this node, which involves copying each
212 // predecessor to each successor (and vice-versa).
213 func (n *graphNode) cost() int {
214 return len(n.pred) * len(n.succ)
215 }
216 217 type nodeSet map[*graphNode]bool
218 219 func (s *nodeSet) add(p *graphNode) {
220 if *s == nil {
221 *s = make(nodeSet)
222 }
223 (*s)[p] = true
224 }
225 226 // dependencyGraph computes the object dependency graph from the given objMap,
227 // with any function nodes removed. The resulting graph contains only constants
228 // and variables.
229 func dependencyGraph(objMap map[Object]*declInfo) []*graphNode {
230 // M is the dependency (Object) -> graphNode mapping
231 M := make(map[dependency]*graphNode)
232 for obj := range objMap {
233 // only consider nodes that may be an initialization dependency
234 if obj, _ := obj.(dependency); obj != nil {
235 M[obj] = &graphNode{obj: obj}
236 }
237 }
238 239 // compute edges for graph M
240 // (We need to include all nodes, even isolated ones, because they still need
241 // to be scheduled for initialization in correct order relative to other nodes.)
242 for obj, n := range M {
243 // for each dependency obj -> d (= deps[i]), create graph edges n->s and s->n
244 for d := range objMap[obj].deps {
245 // only consider nodes that may be an initialization dependency
246 if d, _ := d.(dependency); d != nil {
247 d := M[d]
248 n.succ.add(d)
249 d.pred.add(n)
250 }
251 }
252 }
253 254 var G, funcG []*graphNode // separate non-functions and functions
255 for _, n := range M {
256 if _, ok := n.obj.(*Func); ok {
257 funcG = append(funcG, n)
258 } else {
259 G = append(G, n)
260 }
261 }
262 263 // remove function nodes and collect remaining graph nodes in G
264 // (Mutually recursive functions may introduce cycles among themselves
265 // which are permitted. Yet such cycles may incorrectly inflate the dependency
266 // count for variables which in turn may not get scheduled for initialization
267 // in correct order.)
268 //
269 // Note that because we recursively copy predecessors and successors
270 // throughout the function graph, the cost of removing a function at
271 // position X is proportional to cost * (len(funcG)-X). Therefore, we should
272 // remove high-cost functions last.
273 slices.SortFunc(funcG, func(a, b *graphNode) int {
274 return cmp.Compare(a.cost(), b.cost())
275 })
276 for _, n := range funcG {
277 // connect each predecessor p of n with each successor s
278 // and drop the function node (don't collect it in G)
279 for p := range n.pred {
280 // ignore self-cycles
281 if p != n {
282 // Each successor s of n becomes a successor of p, and
283 // each predecessor p of n becomes a predecessor of s.
284 for s := range n.succ {
285 // ignore self-cycles
286 if s != n {
287 p.succ.add(s)
288 s.pred.add(p)
289 }
290 }
291 delete(p.succ, n) // remove edge to n
292 }
293 }
294 for s := range n.succ {
295 delete(s.pred, n) // remove edge to n
296 }
297 }
298 299 // fill in index and ndeps fields
300 for i, n := range G {
301 n.index = i
302 n.ndeps = len(n.succ)
303 }
304 305 return G
306 }
307 308 // ----------------------------------------------------------------------------
309 // Priority queue
310 311 // nodeQueue implements the container/heap interface;
312 // a nodeQueue may be used as a priority queue.
313 type nodeQueue []*graphNode
314 315 func (a nodeQueue) Len() int { return len(a) }
316 317 func (a nodeQueue) Swap(i, j int) {
318 x, y := a[i], a[j]
319 a[i], a[j] = y, x
320 x.index, y.index = j, i
321 }
322 323 func (a nodeQueue) Less(i, j int) bool {
324 x, y := a[i], a[j]
325 326 // Prioritize all constants before non-constants. See go.dev/issue/66575/.
327 _, xConst := x.obj.(*Const)
328 _, yConst := y.obj.(*Const)
329 if xConst != yConst {
330 return xConst
331 }
332 333 // nodes are prioritized by number of incoming dependencies (1st key)
334 // and source order (2nd key)
335 return x.ndeps < y.ndeps || x.ndeps == y.ndeps && x.obj.order() < y.obj.order()
336 }
337 338 func (a *nodeQueue) Push(x any) {
339 panic("unreachable")
340 }
341 342 func (a *nodeQueue) Pop() any {
343 n := len(*a)
344 x := (*a)[n-1]
345 x.index = -1 // for safety
346 *a = (*a)[:n-1]
347 return x
348 }
349