| // 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(objSet)) |
| // 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, visited objSet) []Object { |
| if visited[from] { |
| return nil // node already seen |
| } |
| visited[from] = true |
| |
| for d := range objMap[from].deps { |
| if d == to { |
| return []Object{d} |
| } |
| if P := findPath(objMap, d, to, visited); 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.Pos(), "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.Pos(), "\t%s refers to", obj.Name()) // secondary error, \t indented |
| obj = cycle[i] |
| } |
| // print cycle[0] again to close the cycle |
| check.errorf(obj.Pos(), "\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 |
| } |