topoSortObjects orders objects by their dependency edges so each object is processed only after its dependencies. Cycles are broken via Tarjan SCC with intra-SCC lexicographic ordering (C10): one member of an SCC installs first (and typically fails → pseudo), the rest install against the pseudo.
(objects []*objectEntry)
| 246 | // with intra-SCC lexicographic ordering (C10): one member of an SCC installs |
| 247 | // first (and typically fails → pseudo), the rest install against the pseudo. |
| 248 | func topoSortObjects(objects []*objectEntry) []*objectEntry { |
| 249 | if len(objects) == 0 { |
| 250 | return nil |
| 251 | } |
| 252 | |
| 253 | index := make(map[string]*objectEntry, len(objects)) |
| 254 | for _, obj := range objects { |
| 255 | index[obj.key()] = obj |
| 256 | } |
| 257 | |
| 258 | edges := buildDependencyEdges(objects, index) |
| 259 | sccs := tarjanSCC(objects, edges) |
| 260 | |
| 261 | // Build a condensed DAG of SCCs, then topo sort and flatten. |
| 262 | sccOf := make(map[string]int, len(objects)) |
| 263 | for i, scc := range sccs { |
| 264 | for _, obj := range scc { |
| 265 | sccOf[obj.key()] = i |
| 266 | } |
| 267 | } |
| 268 | condensedEdges := make([][]int, len(sccs)) |
| 269 | inDegree := make([]int, len(sccs)) |
| 270 | seenEdge := make(map[[2]int]bool) |
| 271 | for src, dsts := range edges { |
| 272 | srcSCC, ok := sccOf[src] |
| 273 | if !ok { |
| 274 | continue |
| 275 | } |
| 276 | for _, dst := range dsts { |
| 277 | dstSCC, ok := sccOf[dst] |
| 278 | if !ok || dstSCC == srcSCC { |
| 279 | continue |
| 280 | } |
| 281 | edge := [2]int{dstSCC, srcSCC} // dst must come before src |
| 282 | if seenEdge[edge] { |
| 283 | continue |
| 284 | } |
| 285 | seenEdge[edge] = true |
| 286 | condensedEdges[dstSCC] = append(condensedEdges[dstSCC], srcSCC) |
| 287 | inDegree[srcSCC]++ |
| 288 | } |
| 289 | } |
| 290 | |
| 291 | // Kahn's algorithm on the condensed graph with a deterministic tiebreak: |
| 292 | // ready SCCs are sorted by the lex-smallest sort key of their members. |
| 293 | readyHeap := make([]int, 0) |
| 294 | for i := range sccs { |
| 295 | if inDegree[i] == 0 { |
| 296 | readyHeap = append(readyHeap, i) |
| 297 | } |
| 298 | } |
| 299 | sortSCCsByMin(readyHeap, sccs) |
| 300 | |
| 301 | var flat []*objectEntry |
| 302 | for len(readyHeap) > 0 { |
| 303 | next := readyHeap[0] |
| 304 | readyHeap = readyHeap[1:] |
| 305 | flat = append(flat, sortedSCCMembers(sccs[next])...) |