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