initorder.go

// 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("package %s: object dependency graph\n", check.pkg.Name())
		for _, n := range pq {
			for _, o := range n.out {
				fmt.Printf("\t%s -> %s\n", n.obj.Name(), o.obj.Name())
			}
		}
		fmt.Println()
		fmt.Printf("package %s: initialization order\n", check.pkg.Name())
	}

	// 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.
	mark := 0
	emitted := make(map[*declInfo]bool)
	for len(pq) > 0 {
		// get the next node
		n := heap.Pop(&pq).(*objNode)

		// if n still depends on other nodes, we have a cycle
		if n.in > 0 {
			mark++ // mark nodes using a different value each time
			cycle := findPath(n, n, mark)
			if i := valIndex(cycle); i >= 0 {
				check.reportCycle(cycle, i)
			}
			// 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 _, out := range n.out {
			out.in--
			heap.Fix(&pq, out.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.Printf("\t%s\n", init)
		}
	}

	if debug {
		fmt.Println()
	}
}

// findPath returns the (reversed) list of nodes z, ... c, b, a,
// such that there is a path (list of edges) from a to z.
// If there is no such path, the result is nil.
// Nodes marked with the value mark are considered "visited";
// unvisited nodes are marked during the graph search.
func findPath(a, z *objNode, mark int) []*objNode {
	if a.mark == mark {
		return nil // node already seen
	}
	a.mark = mark

	for _, n := range a.out {
		if n == z {
			return []*objNode{z}
		}
		if P := findPath(n, z, mark); P != nil {
			return append(P, n)
		}
	}

	return nil
}

// valIndex returns the index of the first constant or variable in a,
// if any; or a value < 0.
func valIndex(a []*objNode) int {
	for i, n := range a {
		switch n.obj.(type) {
		case *Const, *Var:
			return i
		}
	}
	return -1
}

// reportCycle reports an error for the cycle starting at i.
func (check *Checker) reportCycle(cycle []*objNode, i int) {
	obj := cycle[i].obj
	check.errorf(obj.Pos(), "initialization cycle for %s", obj.Name())
	// print cycle
	for _ = range cycle {
		check.errorf(obj.Pos(), "\t%s refers to", obj.Name()) // secondary error, \t indented
		i++
		if i >= len(cycle) {
			i = 0
		}
		obj = cycle[i].obj
	}
	check.errorf(obj.Pos(), "\t%s", obj.Name())
}

// An objNode represents a node in the object dependency graph.
// Each node b in a.out represents an edge a->b indicating that
// b depends on a.
// Nodes may be marked for cycle detection. A node n is marked
// if n.mark corresponds to the current mark value.
type objNode struct {
	obj   Object     // object represented by this node
	in    int        // number of nodes this node depends on
	out   []*objNode // list of nodes that depend on this node
	index int        // node index in list of nodes
	mark  int        // for cycle detection
}

// dependencyGraph computes the transposed object dependency graph
// from the given objMap. The transposed graph is returned as a list
// of nodes; an edge d->n indicates that node n depends on node d.
func dependencyGraph(objMap map[Object]*declInfo) []*objNode {
	// M maps each object to its corresponding node
	M := make(map[Object]*objNode, len(objMap))
	for obj := range objMap {
		M[obj] = &objNode{obj: obj}
	}

	// G is the graph of nodes n
	G := make([]*objNode, len(M))
	i := 0
	for obj, n := range M {
		deps := objMap[obj].deps
		n.in = len(deps)
		for d := range deps {
			d := M[d]                // node n depends on node d
			d.out = append(d.out, n) // add edge d->n
		}

		G[i] = n
		n.index = i
		i++
	}

	return G
}

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

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.in < y.in || x.in == y.in && 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
}