blob: 77a739c7c14e34c5c951e77195cfcb970a748954 [file] [log] [blame]
// 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
}