initorder.go

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