dependencyGraph computes the object dependency graph from the given objMap, with any function nodes removed. The resulting graph contains only constants and variables.
(objMap map[Object]*declInfo)
| 210 | // with any function nodes removed. The resulting graph contains only constants |
| 211 | // and variables. |
| 212 | func dependencyGraph(objMap map[Object]*declInfo) []*graphNode { |
| 213 | // M is the dependency (Object) -> graphNode mapping |
| 214 | M := make(map[dependency]*graphNode) |
| 215 | for obj := range objMap { |
| 216 | // only consider nodes that may be an initialization dependency |
| 217 | if obj, _ := obj.(dependency); obj != nil { |
| 218 | M[obj] = &graphNode{obj: obj} |
| 219 | } |
| 220 | } |
| 221 | |
| 222 | // compute edges for graph M |
| 223 | // (We need to include all nodes, even isolated ones, because they still need |
| 224 | // to be scheduled for initialization in correct order relative to other nodes.) |
| 225 | for obj, n := range M { |
| 226 | // for each dependency obj -> d (= deps[i]), create graph edges n->s and s->n |
| 227 | for d := range objMap[obj].deps { |
| 228 | // only consider nodes that may be an initialization dependency |
| 229 | if d, _ := d.(dependency); d != nil { |
| 230 | d := M[d] |
| 231 | n.succ.add(d) |
| 232 | d.pred.add(n) |
| 233 | } |
| 234 | } |
| 235 | } |
| 236 | |
| 237 | var G, funcG []*graphNode // separate non-functions and functions |
| 238 | for _, n := range M { |
| 239 | if _, ok := n.obj.(*Func); ok { |
| 240 | funcG = append(funcG, n) |
| 241 | } else { |
| 242 | G = append(G, n) |
| 243 | } |
| 244 | } |
| 245 | |
| 246 | // remove function nodes and collect remaining graph nodes in G |
| 247 | // (Mutually recursive functions may introduce cycles among themselves |
| 248 | // which are permitted. Yet such cycles may incorrectly inflate the dependency |
| 249 | // count for variables which in turn may not get scheduled for initialization |
| 250 | // in correct order.) |
| 251 | // |
| 252 | // Note that because we recursively copy predecessors and successors |
| 253 | // throughout the function graph, the cost of removing a function at |
| 254 | // position X is proportional to cost * (len(funcG)-X). Therefore, we should |
| 255 | // remove high-cost functions last. |
| 256 | sort.Slice(funcG, func(i, j int) bool { |
| 257 | return funcG[i].cost() < funcG[j].cost() |
| 258 | }) |
| 259 | for _, n := range funcG { |
| 260 | // connect each predecessor p of n with each successor s |
| 261 | // and drop the function node (don't collect it in G) |
| 262 | for p := range n.pred { |
| 263 | // ignore self-cycles |
| 264 | if p != n { |
| 265 | // Each successor s of n becomes a successor of p, and |
| 266 | // each predecessor p of n becomes a predecessor of s. |
| 267 | for s := range n.succ { |
| 268 | // ignore self-cycles |
| 269 | if s != n { |