initorder.go

     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
View as plain text