src/cmd/compile/internal/gc/initorder.go

   1 // Copyright 2019 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 package gc
   6
   7 import (
   8         "bytes"
   9         "container/heap"
  10         "fmt"
  11 )
  12
  13 // Package initialization
  14 //
  15 // Here we implement the algorithm for ordering package-level variable
  16 // initialization. The spec is written in terms of variable
  17 // initialization, but multiple variables initialized by a single
  18 // assignment are handled together, so here we instead focus on
  19 // ordering initialization assignments. Conveniently, this maps well
  20 // to how we represent package-level initializations using the Node
  21 // AST.
  22 //
  23 // Assignments are in one of three phases: NotStarted, Pending, or
  24 // Done. For assignments in the Pending phase, we use Xoffset to
  25 // record the number of unique variable dependencies whose
  26 // initialization assignment is not yet Done. We also maintain a
  27 // "blocking" map that maps assignments back to all of the assignments
  28 // that depend on it.
  29 //
  30 // For example, for an initialization like:
  31 //
  32 //     var x = f(a, b, b)
  33 //     var a, b = g()
  34 //
  35 // the "x = f(a, b, b)" assignment depends on two variables (a and b),
  36 // so its Xoffset will be 2. Correspondingly, the "a, b = g()"
  37 // assignment's "blocking" entry will have two entries back to x's
  38 // assignment.
  39 //
  40 // Logically, initialization works by (1) taking all NotStarted
  41 // assignments, calculating their dependencies, and marking them
  42 // Pending; (2) adding all Pending assignments with Xoffset==0 to a
  43 // "ready" priority queue (ordered by variable declaration position);
  44 // and (3) iteratively processing the next Pending assignment from the
  45 // queue, decreasing the Xoffset of assignments it's blocking, and
  46 // adding them to the queue if decremented to 0.
  47 //
  48 // As an optimization, we actually apply each of these three steps for
  49 // each assignment. This yields the same order, but keeps queue size
  50 // down and thus also heap operation costs.
  51
  52 // Static initialization phase.
  53 // These values are stored in two bits in Node.flags.
  54 const (
  55         InitNotStarted = iota
  56         InitDone
  57         InitPending
  58 )
  59
  60 type InitOrder struct {
  61         // blocking maps initialization assignments to the assignments
  62         // that depend on it.
  63         blocking map[*Node][]*Node
  64
  65         // ready is the queue of Pending initialization assignments
  66         // that are ready for initialization.
  67         ready declOrder
  68 }
  69
  70 // initOrder computes initialization order for a list l of
  71 // package-level declarations (in declaration order) and outputs the
  72 // corresponding list of statements to include in the init() function
  73 // body.
  74 func initOrder(l []*Node) []*Node {
  75         s := InitSchedule{
  76                 initplans: make(map[*Node]*InitPlan),
  77                 inittemps: make(map[*Node]*Node),
  78         }
  79         o := InitOrder{
  80                 blocking: make(map[*Node][]*Node),
  81         }
  82
  83         // Process all package-level assignment in declaration order.
  84         for _, n := range l {
  85                 switch n.Op {
  86                 case OAS, OAS2DOTTYPE, OAS2FUNC, OAS2MAPR, OAS2RECV:
  87                         o.processAssign(n)
  88                         o.flushReady(s.staticInit)
  89                 case ODCLCONST, ODCLFUNC, ODCLTYPE:
  90                         // nop
  91                 default:
  92                         Fatalf("unexpected package-level statement: %v", n)
  93                 }
  94         }
  95
  96         // Check that all assignments are now Done; if not, there must
  97         // have been a dependency cycle.
  98         for _, n := range l {
  99                 switch n.Op {
 100                 case OAS, OAS2DOTTYPE, OAS2FUNC, OAS2MAPR, OAS2RECV:
 101                         if n.Initorder() != InitDone {
 102                                 // If there have already been errors
 103                                 // printed, those errors may have
 104                                 // confused us and there might not be
 105                                 // a loop. Let the user fix those
 106                                 // first.
 107                                 if nerrors > 0 {
 108                                         errorexit()
 109                                 }
 110
 111                                 findInitLoopAndExit(firstLHS(n), new([]*Node), make(map[*Node]bool))
 112                                 Fatalf("initialization unfinished, but failed to identify loop")
 113                         }
 114                 }
 115         }
 116
 117         // Invariant consistency check. If this is non-zero, then we
 118         // should have found a cycle above.
 119         if len(o.blocking) != 0 {
 120                 Fatalf("expected empty map: %v", o.blocking)
 121         }
 122
 123         return s.out
 124 }
 125
 126 func (o *InitOrder) processAssign(n *Node) {
 127         if n.Initorder() != InitNotStarted || n.Xoffset != BADWIDTH {
 128                 Fatalf("unexpected state: %v, %v, %v", n, n.Initorder(), n.Xoffset)
 129         }
 130
 131         n.SetInitorder(InitPending)
 132         n.Xoffset = 0
 133
 134         // Compute number of variable dependencies and build the
 135         // inverse dependency ("blocking") graph.
 136         for dep := range collectDeps(n, true) {
 137                 defn := dep.Name.Defn
 138                 // Skip dependencies on functions (PFUNC) and
 139                 // variables already initialized (InitDone).
 140                 if dep.Class() != PEXTERN || defn.Initorder() == InitDone {
 141                         continue
 142                 }
 143                 n.Xoffset++
 144                 o.blocking[defn] = append(o.blocking[defn], n)
 145         }
 146
 147         if n.Xoffset == 0 {
 148                 heap.Push(&o.ready, n)
 149         }
 150 }
 151
 152 // flushReady repeatedly applies initialize to the earliest (in
 153 // declaration order) assignment ready for initialization and updates
 154 // the inverse dependency ("blocking") graph.
 155 func (o *InitOrder) flushReady(initialize func(*Node)) {
 156         for o.ready.Len() != 0 {
 157                 n := heap.Pop(&o.ready).(*Node)
 158                 if n.Initorder() != InitPending || n.Xoffset != 0 {
 159                         Fatalf("unexpected state: %v, %v, %v", n, n.Initorder(), n.Xoffset)
 160                 }
 161
 162                 initialize(n)
 163                 n.SetInitorder(InitDone)
 164                 n.Xoffset = BADWIDTH
 165
 166                 blocked := o.blocking[n]
 167                 delete(o.blocking, n)
 168
 169                 for _, m := range blocked {
 170                         m.Xoffset--
 171                         if m.Xoffset == 0 {
 172                                 heap.Push(&o.ready, m)
 173                         }
 174                 }
 175         }
 176 }
 177
 178 // findInitLoopAndExit searches for an initialization loop involving variable
 179 // or function n. If one is found, it reports the loop as an error and exits.
 180 //
 181 // path points to a slice used for tracking the sequence of
 182 // variables/functions visited. Using a pointer to a slice allows the
 183 // slice capacity to grow and limit reallocations.
 184 func findInitLoopAndExit(n *Node, path *[]*Node, ok map[*Node]bool) {
 185         for i, x := range *path {
 186                 if x == n {
 187                         reportInitLoopAndExit((*path)[i:])
 188                         return
 189                 }
 190         }
 191
 192         // There might be multiple loops involving n; by sorting
 193         // references, we deterministically pick the one reported.
 194         refers := collectDeps(n.Name.Defn, false).Sorted(func(ni, nj *Node) bool {
 195                 return ni.Pos.Before(nj.Pos)
 196         })
 197
 198         *path = append(*path, n)
 199         for _, ref := range refers {
 200                 // Short-circuit variables that were initialized.
 201                 if ref.Class() == PEXTERN && ref.Name.Defn.Initorder() == InitDone || ok[ref] {
 202                         continue
 203                 }
 204                 findInitLoopAndExit(ref, path, ok)
 205         }
 206
 207         // n is not involved in a cycle.
 208         // Record that fact to avoid checking it again when reached another way,
 209         // or else this traversal will take exponential time traversing all paths
 210         // through the part of the package's call graph implicated in the cycle.
 211         ok[n] = true
 212
 213         *path = (*path)[:len(*path)-1]
 214 }
 215
 216 // reportInitLoopAndExit reports and initialization loop as an error
 217 // and exits. However, if l is not actually an initialization loop, it
 218 // simply returns instead.
 219 func reportInitLoopAndExit(l []*Node) {
 220         // Rotate loop so that the earliest variable declaration is at
 221         // the start.
 222         i := -1
 223         for j, n := range l {
 224                 if n.Class() == PEXTERN && (i == -1 || n.Pos.Before(l[i].Pos)) {
 225                         i = j
 226                 }
 227         }
 228         if i == -1 {
 229                 // False positive: loop only involves recursive
 230                 // functions. Return so that findInitLoop can continue
 231                 // searching.
 232                 return
 233         }
 234         l = append(l[i:], l[:i]...)
 235
 236         // TODO(mdempsky): Method values are printed as "T.m-fm"
 237         // rather than "T.m". Figure out how to avoid that.
 238
 239         var msg bytes.Buffer
 240         fmt.Fprintf(&msg, "initialization loop:\n")
 241         for _, n := range l {
 242                 fmt.Fprintf(&msg, "\t%v: %v refers to\n", n.Line(), n)
 243         }
 244         fmt.Fprintf(&msg, "\t%v: %v", l[0].Line(), l[0])
 245
 246         yyerrorl(l[0].Pos, msg.String())
 247         errorexit()
 248 }
 249
 250 // collectDeps returns all of the package-level functions and
 251 // variables that declaration n depends on. If transitive is true,
 252 // then it also includes the transitive dependencies of any depended
 253 // upon functions (but not variables).
 254 func collectDeps(n *Node, transitive bool) NodeSet {
 255         d := initDeps{transitive: transitive}
 256         switch n.Op {
 257         case OAS:
 258                 d.inspect(n.Right)
 259         case OAS2DOTTYPE, OAS2FUNC, OAS2MAPR, OAS2RECV:
 260                 d.inspect(n.Right)
 261         case ODCLFUNC:
 262                 d.inspectList(n.Nbody)
 263         default:
 264                 Fatalf("unexpected Op: %v", n.Op)
 265         }
 266         return d.seen
 267 }
 268
 269 type initDeps struct {
 270         transitive bool
 271         seen       NodeSet
 272 }
 273
 274 func (d *initDeps) inspect(n *Node)     { inspect(n, d.visit) }
 275 func (d *initDeps) inspectList(l Nodes) { inspectList(l, d.visit) }
 276
 277 // visit calls foundDep on any package-level functions or variables
 278 // referenced by n, if any.
 279 func (d *initDeps) visit(n *Node) bool {
 280         switch n.Op {
 281         case ONAME:
 282                 if n.isMethodExpression() {
 283                         d.foundDep(asNode(n.Type.FuncType().Nname))
 284                         return false
 285                 }
 286
 287                 switch n.Class() {
 288                 case PEXTERN, PFUNC:
 289                         d.foundDep(n)
 290                 }
 291
 292         case OCLOSURE:
 293                 d.inspectList(n.Func.Closure.Nbody)
 294
 295         case ODOTMETH, OCALLPART:
 296                 d.foundDep(asNode(n.Type.FuncType().Nname))
 297         }
 298
 299         return true
 300 }
 301
 302 // foundDep records that we've found a dependency on n by adding it to
 303 // seen.
 304 func (d *initDeps) foundDep(n *Node) {
 305         // Can happen with method expressions involving interface
 306         // types; e.g., fixedbugs/issue4495.go.
 307         if n == nil {
 308                 return
 309         }
 310
 311         // Names without definitions aren't interesting as far as
 312         // initialization ordering goes.
 313         if n.Name.Defn == nil {
 314                 return
 315         }
 316
 317         if d.seen.Has(n) {
 318                 return
 319         }
 320         d.seen.Add(n)
 321         if d.transitive && n.Class() == PFUNC {
 322                 d.inspectList(n.Name.Defn.Nbody)
 323         }
 324 }
 325
 326 // declOrder implements heap.Interface, ordering assignment statements
 327 // by the position of their first LHS expression.
 328 //
 329 // N.B., the Pos of the first LHS expression is used because because
 330 // an OAS node's Pos may not be unique. For example, given the
 331 // declaration "var a, b = f(), g()", "a" must be ordered before "b",
 332 // but both OAS nodes use the "=" token's position as their Pos.
 333 type declOrder []*Node
 334
 335 func (s declOrder) Len() int           { return len(s) }
 336 func (s declOrder) Less(i, j int) bool { return firstLHS(s[i]).Pos.Before(firstLHS(s[j]).Pos) }
 337 func (s declOrder) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
 338
 339 func (s *declOrder) Push(x interface{}) { *s = append(*s, x.(*Node)) }
 340 func (s *declOrder) Pop() interface{} {
 341         n := (*s)[len(*s)-1]
 342         *s = (*s)[:len(*s)-1]
 343         return n
 344 }
 345
 346 // firstLHS returns the first expression on the left-hand side of
 347 // assignment n.
 348 func firstLHS(n *Node) *Node {
 349         switch n.Op {
 350         case OAS:
 351                 return n.Left
 352         case OAS2DOTTYPE, OAS2FUNC, OAS2RECV, OAS2MAPR:
 353                 return n.List.First()
 354         }
 355
 356         Fatalf("unexpected Op: %v", n.Op)
 357         return nil
 358 }