92 lines
1.9 KiB
Go
92 lines
1.9 KiB
Go
package engine
|
|
|
|
import (
|
|
"fmt"
|
|
"sort"
|
|
|
|
"gitlab.hive-brain.de/MDietermann/Archduino/internal/module"
|
|
)
|
|
|
|
// TopoSort returns module IDs in a valid dependency order.
|
|
// Ties are broken alphabetically for deterministic output.
|
|
// Returns an error on unknown deps or cycles.
|
|
func TopoSort(metas []module.Meta) ([]string, error) {
|
|
known := make(map[string]bool, len(metas))
|
|
for _, m := range metas {
|
|
known[m.ID] = true
|
|
}
|
|
for _, m := range metas {
|
|
for _, d := range m.Deps {
|
|
if !known[d] {
|
|
return nil, fmt.Errorf("module %q depends on unknown %q", m.ID, d)
|
|
}
|
|
}
|
|
}
|
|
|
|
// Kahn's algorithm with alphabetical tie-breaking.
|
|
indeg := make(map[string]int, len(metas))
|
|
children := make(map[string][]string, len(metas))
|
|
for _, m := range metas {
|
|
if _, ok := indeg[m.ID]; !ok {
|
|
indeg[m.ID] = 0
|
|
}
|
|
for _, d := range m.Deps {
|
|
indeg[m.ID]++
|
|
children[d] = append(children[d], m.ID)
|
|
}
|
|
}
|
|
|
|
var ready []string
|
|
for id, d := range indeg {
|
|
if d == 0 {
|
|
ready = append(ready, id)
|
|
}
|
|
}
|
|
sort.Strings(ready)
|
|
|
|
var order []string
|
|
for len(ready) > 0 {
|
|
next := ready[0]
|
|
ready = ready[1:]
|
|
order = append(order, next)
|
|
kids := append([]string(nil), children[next]...)
|
|
sort.Strings(kids)
|
|
for _, c := range kids {
|
|
indeg[c]--
|
|
if indeg[c] == 0 {
|
|
ready = append(ready, c)
|
|
sort.Strings(ready)
|
|
}
|
|
}
|
|
}
|
|
|
|
if len(order) != len(metas) {
|
|
return nil, fmt.Errorf("dependency cycle detected among modules")
|
|
}
|
|
return order, nil
|
|
}
|
|
|
|
// Descendants returns the set of module IDs transitively downstream of root.
|
|
// Root itself is NOT included.
|
|
func Descendants(metas []module.Meta, root string) map[string]bool {
|
|
children := make(map[string][]string)
|
|
for _, m := range metas {
|
|
for _, d := range m.Deps {
|
|
children[d] = append(children[d], m.ID)
|
|
}
|
|
}
|
|
out := make(map[string]bool)
|
|
var walk func(string)
|
|
walk = func(id string) {
|
|
for _, c := range children[id] {
|
|
if out[c] {
|
|
continue
|
|
}
|
|
out[c] = true
|
|
walk(c)
|
|
}
|
|
}
|
|
walk(root)
|
|
return out
|
|
}
|