initorder.go

Documentation: go/types

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