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