79 lines
1.8 KiB
Go
79 lines
1.8 KiB
Go
package ci
|
|
|
|
import "fmt"
|
|
|
|
// dagNode holds a job name and its resolved dependencies.
|
|
type dagNode struct {
|
|
name string
|
|
needs []string
|
|
}
|
|
|
|
// TopoSort returns the job names in a valid topological execution order.
|
|
// Returns an error if the dependency graph has cycles or references unknown jobs.
|
|
func TopoSort(jobs map[string]WorkflowJob) ([]string, error) {
|
|
nodes := make(map[string]*dagNode, len(jobs))
|
|
for name, job := range jobs {
|
|
nodes[name] = &dagNode{name: name, needs: []string(job.Needs)}
|
|
}
|
|
// Validate all dependencies exist.
|
|
for _, node := range nodes {
|
|
for _, dep := range node.needs {
|
|
if _, ok := nodes[dep]; !ok {
|
|
return nil, fmt.Errorf("job %q depends on unknown job %q", node.name, dep)
|
|
}
|
|
}
|
|
}
|
|
|
|
var order []string
|
|
visited := make(map[string]bool, len(nodes))
|
|
inStack := make(map[string]bool, len(nodes))
|
|
|
|
var visit func(name string) error
|
|
visit = func(name string) error {
|
|
if inStack[name] {
|
|
return fmt.Errorf("cycle detected at job %q", name)
|
|
}
|
|
if visited[name] {
|
|
return nil
|
|
}
|
|
inStack[name] = true
|
|
for _, dep := range nodes[name].needs {
|
|
if err := visit(dep); err != nil {
|
|
return err
|
|
}
|
|
}
|
|
inStack[name] = false
|
|
visited[name] = true
|
|
order = append(order, name)
|
|
return nil
|
|
}
|
|
|
|
for name := range nodes {
|
|
if err := visit(name); err != nil {
|
|
return nil, err
|
|
}
|
|
}
|
|
return order, nil
|
|
}
|
|
|
|
// ReadyJobs returns the names of jobs whose dependencies are all in completedJobs.
|
|
func ReadyJobs(jobs map[string]WorkflowJob, completedJobs map[string]bool, enqueuedJobs map[string]bool) []string {
|
|
var ready []string
|
|
for name, job := range jobs {
|
|
if enqueuedJobs[name] {
|
|
continue
|
|
}
|
|
allDone := true
|
|
for _, dep := range job.Needs {
|
|
if !completedJobs[dep] {
|
|
allDone = false
|
|
break
|
|
}
|
|
}
|
|
if allDone {
|
|
ready = append(ready, name)
|
|
}
|
|
}
|
|
return ready
|
|
}
|