src/go/types/initorder.go - go - Git at Google

 // Copyright 2014 The Go Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.

 package types

 import (
 	"container/heap"
 	"fmt"
 )

 // initOrder computes the Info.InitOrder for package variables.
 func (check *Checker) initOrder() {
 	// An InitOrder may already have been computed if a package is
 	// built from several calls to (*Checker).Files. Clear it.
 	check.Info.InitOrder = check.Info.InitOrder[:0]

 	// Compute the object dependency graph and initialize
 	// a priority queue with the list of graph nodes.
 	pq := nodeQueue(dependencyGraph(check.objMap))
 	heap.Init(&pq)

 	const debug = false
 	if debug {
 		fmt.Printf("Computing initialization order for %s\n\n", check.pkg)
 		fmt.Println("Object dependency graph:")
 		for obj, d := range check.objMap {
 			// only print objects that may appear in the dependency graph
 			if obj, _ := obj.(dependency); obj != nil {
 				if len(d.deps) > 0 {
 					fmt.Printf("\t%s depends on\n", obj.Name())
 					for dep := range d.deps {
 						fmt.Printf("\t\t%s\n", dep.Name())
 					}
 				} else {
 					fmt.Printf("\t%s has no dependencies\n", obj.Name())
 				}
 			}
 		}
 		fmt.Println()

 		fmt.Println("Transposed object dependency graph (functions eliminated):")
 		for _, n := range pq {
 			fmt.Printf("\t%s depends on %d nodes\n", n.obj.Name(), n.ndeps)
 			for p := range n.pred {
 				fmt.Printf("\t\t%s is dependent\n", p.obj.Name())
 			}
 		}
 		fmt.Println()

 		fmt.Println("Processing nodes:")
 	}

 	// Determine initialization order by removing the highest priority node
 	// (the one with the fewest dependencies) and its edges from the graph,
 	// repeatedly, until there are no nodes left.
 	// In a valid Go program, those nodes always have zero dependencies (after
 	// removing all incoming dependencies), otherwise there are initialization
 	// cycles.
 	emitted := make(map[*declInfo]bool)
 	for len(pq) > 0 {
 		// get the next node
 		n := heap.Pop(&pq).(*graphNode)

 		if debug {
 			fmt.Printf("\t%s (src pos %d) depends on %d nodes now\n",
 				n.obj.Name(), n.obj.order(), n.ndeps)
 		}

 		// if n still depends on other nodes, we have a cycle
 		if n.ndeps > 0 {
 			cycle := findPath(check.objMap, n.obj, n.obj, make(map[Object]bool))
 			// If n.obj is not part of the cycle (e.g., n.obj->b->c->d->c),
 			// cycle will be nil. Don't report anything in that case since
 			// the cycle is reported when the algorithm gets to an object
 			// in the cycle.
 			// Furthermore, once an object in the cycle is encountered,
 			// the cycle will be broken (dependency count will be reduced
 			// below), and so the remaining nodes in the cycle don't trigger
 			// another error (unless they are part of multiple cycles).
 			if cycle != nil {
 				check.reportCycle(cycle)
 			}
 			// Ok to continue, but the variable initialization order
 			// will be incorrect at this point since it assumes no
 			// cycle errors.
 		}

 		// reduce dependency count of all dependent nodes
 		// and update priority queue
 		for p := range n.pred {
 			p.ndeps--
 			heap.Fix(&pq, p.index)
 		}

 		// record the init order for variables with initializers only
 		v, _ := n.obj.(*Var)
 		info := check.objMap[v]
 		if v == nil || !info.hasInitializer() {
 			continue
 		}

 		// n:1 variable declarations such as: a, b = f()
 		// introduce a node for each lhs variable (here: a, b);
 		// but they all have the same initializer - emit only
 		// one, for the first variable seen
 		if emitted[info] {
 			continue // initializer already emitted, if any
 		}
 		emitted[info] = true

 		infoLhs := info.lhs // possibly nil (see declInfo.lhs field comment)
 		if infoLhs == nil {
 			infoLhs = []*Var{v}
 		}
 		init := &Initializer{infoLhs, info.init}
 		check.Info.InitOrder = append(check.Info.InitOrder, init)
 	}

 	if debug {
 		fmt.Println()
 		fmt.Println("Initialization order:")
 		for _, init := range check.Info.InitOrder {
 			fmt.Printf("\t%s\n", init)
 		}
 		fmt.Println()
 	}
 }

 // findPath returns the (reversed) list of objects []Object{to, ... from}
 // such that there is a path of object dependencies from 'from' to 'to'.
 // If there is no such path, the result is nil.
 func findPath(objMap map[Object]*declInfo, from, to Object, seen map[Object]bool) []Object {
 	if seen[from] {
 		return nil
 	}
 	seen[from] = true

 	for d := range objMap[from].deps {
 		if d == to {
 			return []Object{d}
 		}
 		if P := findPath(objMap, d, to, seen); P != nil {
 			return append(P, d)
 		}
 	}

 	return nil
 }

 // reportCycle reports an error for the given cycle.
 func (check *Checker) reportCycle(cycle []Object) {
 	obj := cycle[0]
 	check.errorf(obj, _InvalidInitCycle, "initialization cycle for %s", obj.Name())
 	// subtle loop: print cycle[i] for i = 0, n-1, n-2, ... 1 for len(cycle) = n
 	for i := len(cycle) - 1; i >= 0; i-- {
 		check.errorf(obj, _InvalidInitCycle, "\t%s refers to", obj.Name()) // secondary error, \t indented
 		obj = cycle[i]
 	}
 	// print cycle[0] again to close the cycle
 	check.errorf(obj, _InvalidInitCycle, "\t%s", obj.Name())
 }

 // ----------------------------------------------------------------------------
 // Object dependency graph

 // A dependency is an object that may be a dependency in an initialization
 // expression. Only constants, variables, and functions can be dependencies.
 // Constants are here because constant expression cycles are reported during
 // initialization order computation.
 type dependency interface {
 	Object
 	isDependency()
 }

 // A graphNode represents a node in the object dependency graph.
 // Each node p in n.pred represents an edge p->n, and each node
 // s in n.succ represents an edge n->s; with a->b indicating that
 // a depends on b.
 type graphNode struct {
 	obj        dependency // object represented by this node
 	pred, succ nodeSet    // consumers and dependencies of this node (lazily initialized)
 	index      int        // node index in graph slice/priority queue
 	ndeps      int        // number of outstanding dependencies before this object can be initialized
 }

 type nodeSet map[*graphNode]bool

 func (s *nodeSet) add(p *graphNode) {
 	if *s == nil {
 		*s = make(nodeSet)
 	}
 	(*s)[p] = true
 }

 // dependencyGraph computes the object dependency graph from the given objMap,
 // with any function nodes removed. The resulting graph contains only constants
 // and variables.
 func dependencyGraph(objMap map[Object]*declInfo) []*graphNode {
 	// M is the dependency (Object) -> graphNode mapping
 	M := make(map[dependency]*graphNode)
 	for obj := range objMap {
 		// only consider nodes that may be an initialization dependency
 		if obj, _ := obj.(dependency); obj != nil {
 			M[obj] = &graphNode{obj: obj}
 		}
 	}

 	// compute edges for graph M
 	// (We need to include all nodes, even isolated ones, because they still need
 	// to be scheduled for initialization in correct order relative to other nodes.)
 	for obj, n := range M {
 		// for each dependency obj -> d (= deps[i]), create graph edges n->s and s->n
 		for d := range objMap[obj].deps {
 			// only consider nodes that may be an initialization dependency
 			if d, _ := d.(dependency); d != nil {
 				d := M[d]
 				n.succ.add(d)
 				d.pred.add(n)
 			}
 		}
 	}

 	// remove function nodes and collect remaining graph nodes in G
 	// (Mutually recursive functions may introduce cycles among themselves
 	// which are permitted. Yet such cycles may incorrectly inflate the dependency
 	// count for variables which in turn may not get scheduled for initialization
 	// in correct order.)
 	var G []*graphNode
 	for obj, n := range M {
 		if _, ok := obj.(*Func); ok {
 			// connect each predecessor p of n with each successor s
 			// and drop the function node (don't collect it in G)
 			for p := range n.pred {
 				// ignore self-cycles
 				if p != n {
 					// Each successor s of n becomes a successor of p, and
 					// each predecessor p of n becomes a predecessor of s.
 					for s := range n.succ {
 						// ignore self-cycles
 						if s != n {
 							p.succ.add(s)
 							s.pred.add(p)
 							delete(s.pred, n) // remove edge to n
 						}
 					}
 					delete(p.succ, n) // remove edge to n
 				}
 			}
 		} else {
 			// collect non-function nodes
 			G = append(G, n)
 		}
 	}

 	// fill in index and ndeps fields
 	for i, n := range G {
 		n.index = i
 		n.ndeps = len(n.succ)
 	}

 	return G
 }

 // ----------------------------------------------------------------------------
 // Priority queue

 // nodeQueue implements the container/heap interface;
 // a nodeQueue may be used as a priority queue.
 type nodeQueue []*graphNode

 func (a nodeQueue) Len() int { return len(a) }

 func (a nodeQueue) Swap(i, j int) {
 	x, y := a[i], a[j]
 	a[i], a[j] = y, x
 	x.index, y.index = j, i
 }

 func (a nodeQueue) Less(i, j int) bool {
 	x, y := a[i], a[j]
 	// nodes are prioritized by number of incoming dependencies (1st key)
 	// and source order (2nd key)
 	return x.ndeps < y.ndeps || x.ndeps == y.ndeps && x.obj.order() < y.obj.order()
 }

 func (a *nodeQueue) Push(x interface{}) {
 	panic("unreachable")
 }

 func (a *nodeQueue) Pop() interface{} {
 	n := len(*a)
 	x := (*a)[n-1]
 	x.index = -1 // for safety
 	*a = (*a)[:n-1]
 	return x
 }
	// Copyright 2014 The Go Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style
	// license that can be found in the LICENSE file.

	package types

	import (
	"container/heap"
	"fmt"
	)

	// initOrder computes the Info.InitOrder for package variables.
	func (check *Checker) initOrder() {
	// An InitOrder may already have been computed if a package is
	// built from several calls to (*Checker).Files. Clear it.
	check.Info.InitOrder = check.Info.InitOrder[:0]

	// Compute the object dependency graph and initialize
	// a priority queue with the list of graph nodes.
	pq := nodeQueue(dependencyGraph(check.objMap))
	heap.Init(&pq)

	const debug = false
	if debug {
	fmt.Printf("Computing initialization order for %s\n\n", check.pkg)
	fmt.Println("Object dependency graph:")
	for obj, d := range check.objMap {
	// only print objects that may appear in the dependency graph
	if obj, _ := obj.(dependency); obj != nil {
	if len(d.deps) > 0 {
	fmt.Printf("\t%s depends on\n", obj.Name())
	for dep := range d.deps {
	fmt.Printf("\t\t%s\n", dep.Name())
	}
	} else {
	fmt.Printf("\t%s has no dependencies\n", obj.Name())
	}
	}
	}
	fmt.Println()

	fmt.Println("Transposed object dependency graph (functions eliminated):")
	for _, n := range pq {
	fmt.Printf("\t%s depends on %d nodes\n", n.obj.Name(), n.ndeps)
	for p := range n.pred {
	fmt.Printf("\t\t%s is dependent\n", p.obj.Name())
	}
	}
	fmt.Println()

	fmt.Println("Processing nodes:")
	}

	// Determine initialization order by removing the highest priority node
	// (the one with the fewest dependencies) and its edges from the graph,
	// repeatedly, until there are no nodes left.
	// In a valid Go program, those nodes always have zero dependencies (after
	// removing all incoming dependencies), otherwise there are initialization
	// cycles.
	emitted := make(map[*declInfo]bool)
	for len(pq) > 0 {
	// get the next node
	n := heap.Pop(&pq).(*graphNode)

	if debug {
	fmt.Printf("\t%s (src pos %d) depends on %d nodes now\n",
	n.obj.Name(), n.obj.order(), n.ndeps)
	}

	// if n still depends on other nodes, we have a cycle
	if n.ndeps > 0 {
	cycle := findPath(check.objMap, n.obj, n.obj, make(map[Object]bool))
	// If n.obj is not part of the cycle (e.g., n.obj->b->c->d->c),
	// cycle will be nil. Don't report anything in that case since
	// the cycle is reported when the algorithm gets to an object
	// in the cycle.
	// Furthermore, once an object in the cycle is encountered,
	// the cycle will be broken (dependency count will be reduced
	// below), and so the remaining nodes in the cycle don't trigger
	// another error (unless they are part of multiple cycles).
	if cycle != nil {
	check.reportCycle(cycle)
	}
	// Ok to continue, but the variable initialization order
	// will be incorrect at this point since it assumes no
	// cycle errors.
	}

	// reduce dependency count of all dependent nodes
	// and update priority queue
	for p := range n.pred {
	p.ndeps--
	heap.Fix(&pq, p.index)
	}

	// record the init order for variables with initializers only
	v, _ := n.obj.(*Var)
	info := check.objMap[v]
	if v == nil \|\| !info.hasInitializer() {
	continue
	}

	// n:1 variable declarations such as: a, b = f()
	// introduce a node for each lhs variable (here: a, b);
	// but they all have the same initializer - emit only
	// one, for the first variable seen
	if emitted[info] {
	continue // initializer already emitted, if any
	}
	emitted[info] = true

	infoLhs := info.lhs // possibly nil (see declInfo.lhs field comment)
	if infoLhs == nil {
	infoLhs = []*Var{v}
	}
	init := &Initializer{infoLhs, info.init}
	check.Info.InitOrder = append(check.Info.InitOrder, init)
	}

	if debug {
	fmt.Println()
	fmt.Println("Initialization order:")
	for _, init := range check.Info.InitOrder {
	fmt.Printf("\t%s\n", init)
	}
	fmt.Println()
	}
	}

	// findPath returns the (reversed) list of objects []Object{to, ... from}
	// such that there is a path of object dependencies from 'from' to 'to'.
	// If there is no such path, the result is nil.
	func findPath(objMap map[Object]*declInfo, from, to Object, seen map[Object]bool) []Object {
	if seen[from] {
	return nil
	}
	seen[from] = true

	for d := range objMap[from].deps {
	if d == to {
	return []Object{d}
	}
	if P := findPath(objMap, d, to, seen); P != nil {
	return append(P, d)
	}
	}

	return nil
	}

	// reportCycle reports an error for the given cycle.
	func (check *Checker) reportCycle(cycle []Object) {
	obj := cycle[0]
	check.errorf(obj, _InvalidInitCycle, "initialization cycle for %s", obj.Name())
	// subtle loop: print cycle[i] for i = 0, n-1, n-2, ... 1 for len(cycle) = n
	for i := len(cycle) - 1; i >= 0; i-- {
	check.errorf(obj, _InvalidInitCycle, "\t%s refers to", obj.Name()) // secondary error, \t indented
	obj = cycle[i]
	}
	// print cycle[0] again to close the cycle
	check.errorf(obj, _InvalidInitCycle, "\t%s", obj.Name())
	}

	// ----------------------------------------------------------------------------
	// Object dependency graph

	// A dependency is an object that may be a dependency in an initialization
	// expression. Only constants, variables, and functions can be dependencies.
	// Constants are here because constant expression cycles are reported during
	// initialization order computation.
	type dependency interface {
	Object
	isDependency()
	}

	// A graphNode represents a node in the object dependency graph.
	// Each node p in n.pred represents an edge p->n, and each node
	// s in n.succ represents an edge n->s; with a->b indicating that
	// a depends on b.
	type graphNode struct {
	obj dependency // object represented by this node
	pred, succ nodeSet // consumers and dependencies of this node (lazily initialized)
	index int // node index in graph slice/priority queue
	ndeps int // number of outstanding dependencies before this object can be initialized
	}

	type nodeSet map[*graphNode]bool

	func (s nodeSet) add(p graphNode) {
	if *s == nil {
	*s = make(nodeSet)
	}
	(*s)[p] = true
	}

	// dependencyGraph computes the object dependency graph from the given objMap,
	// with any function nodes removed. The resulting graph contains only constants
	// and variables.
	func dependencyGraph(objMap map[Object]declInfo) []graphNode {
	// M is the dependency (Object) -> graphNode mapping
	M := make(map[dependency]*graphNode)
	for obj := range objMap {
	// only consider nodes that may be an initialization dependency
	if obj, _ := obj.(dependency); obj != nil {
	M[obj] = &graphNode{obj: obj}
	}
	}

	// compute edges for graph M
	// (We need to include all nodes, even isolated ones, because they still need
	// to be scheduled for initialization in correct order relative to other nodes.)
	for obj, n := range M {
	// for each dependency obj -> d (= deps[i]), create graph edges n->s and s->n
	for d := range objMap[obj].deps {
	// only consider nodes that may be an initialization dependency
	if d, _ := d.(dependency); d != nil {
	d := M[d]
	n.succ.add(d)
	d.pred.add(n)
	}
	}
	}

	// remove function nodes and collect remaining graph nodes in G
	// (Mutually recursive functions may introduce cycles among themselves
	// which are permitted. Yet such cycles may incorrectly inflate the dependency
	// count for variables which in turn may not get scheduled for initialization
	// in correct order.)
	var G []*graphNode
	for obj, n := range M {
	if _, ok := obj.(*Func); ok {
	// connect each predecessor p of n with each successor s
	// and drop the function node (don't collect it in G)
	for p := range n.pred {
	// ignore self-cycles
	if p != n {
	// Each successor s of n becomes a successor of p, and
	// each predecessor p of n becomes a predecessor of s.
	for s := range n.succ {
	// ignore self-cycles
	if s != n {
	p.succ.add(s)
	s.pred.add(p)
	delete(s.pred, n) // remove edge to n
	}
	}
	delete(p.succ, n) // remove edge to n
	}
	}
	} else {
	// collect non-function nodes
	G = append(G, n)
	}
	}

	// fill in index and ndeps fields
	for i, n := range G {
	n.index = i
	n.ndeps = len(n.succ)
	}

	return G
	}

	// ----------------------------------------------------------------------------
	// Priority queue

	// nodeQueue implements the container/heap interface;
	// a nodeQueue may be used as a priority queue.
	type nodeQueue []*graphNode

	func (a nodeQueue) Len() int { return len(a) }

	func (a nodeQueue) Swap(i, j int) {
	x, y := a[i], a[j]
	a[i], a[j] = y, x
	x.index, y.index = j, i
	}

	func (a nodeQueue) Less(i, j int) bool {
	x, y := a[i], a[j]
	// nodes are prioritized by number of incoming dependencies (1st key)
	// and source order (2nd key)
	return x.ndeps < y.ndeps \|\| x.ndeps == y.ndeps && x.obj.order() < y.obj.order()
	}

	func (a *nodeQueue) Push(x interface{}) {
	panic("unreachable")
	}

	func (a *nodeQueue) Pop() interface{} {
	n := len(*a)
	x := (*a)[n-1]
	x.index = -1 // for safety
	a = (a)[:n-1]
	return x
	}