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