Source file src/pkg/go/types/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 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(objSet))
    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, visited objSet) []Object {
   134		if visited[from] {
   135			return nil // node already seen
   136		}
   137		visited[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, visited); 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.Pos(), "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.Pos(), "\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.Pos(), "\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