tarjanSCC runs Tarjan's strongly-connected-components algorithm on the dependency graph and returns SCCs. Each SCC's members are returned in the order the algorithm discovered them; callers sort for determinism.
(objects []*objectEntry, edges map[string][]string)
| 419 | // dependency graph and returns SCCs. Each SCC's members are returned in the |
| 420 | // order the algorithm discovered them; callers sort for determinism. |
| 421 | func tarjanSCC(objects []*objectEntry, edges map[string][]string) [][]*objectEntry { |
| 422 | type state struct { |
| 423 | index, low int |
| 424 | onStack bool |
| 425 | } |
| 426 | st := make(map[string]*state, len(objects)) |
| 427 | byKey := make(map[string]*objectEntry, len(objects)) |
| 428 | for _, obj := range objects { |
| 429 | byKey[obj.key()] = obj |
| 430 | } |
| 431 | |
| 432 | // Walk nodes in deterministic order so tests and shadow diffs reproduce. |
| 433 | keys := make([]string, 0, len(objects)) |
| 434 | for _, obj := range objects { |
| 435 | keys = append(keys, obj.key()) |
| 436 | } |
| 437 | slices.Sort(keys) |
| 438 | |
| 439 | var ( |
| 440 | index int |
| 441 | stack []string |
| 442 | result [][]*objectEntry |
| 443 | ) |
| 444 | |
| 445 | var strongconnect func(v string) |
| 446 | strongconnect = func(v string) { |
| 447 | st[v] = &state{index: index, low: index, onStack: true} |
| 448 | index++ |
| 449 | stack = append(stack, v) |
| 450 | |
| 451 | for _, w := range edges[v] { |
| 452 | if _, ok := byKey[w]; !ok { |
| 453 | continue |
| 454 | } |
| 455 | if _, seen := st[w]; !seen { |
| 456 | strongconnect(w) |
| 457 | st[v].low = min(st[v].low, st[w].low) |
| 458 | } else if st[w].onStack { |
| 459 | st[v].low = min(st[v].low, st[w].index) |
| 460 | } |
| 461 | } |
| 462 | |
| 463 | if st[v].low == st[v].index { |
| 464 | var scc []*objectEntry |
| 465 | for { |
| 466 | w := stack[len(stack)-1] |
| 467 | stack = stack[:len(stack)-1] |
| 468 | st[w].onStack = false |
| 469 | scc = append(scc, byKey[w]) |
| 470 | if w == v { |
| 471 | break |
| 472 | } |
| 473 | } |
| 474 | result = append(result, scc) |
| 475 | } |
| 476 | } |
| 477 | |
| 478 | for _, k := range keys { |