108 lines
2.7 KiB
Go
108 lines
2.7 KiB
Go
package domain
|
|
|
|
import (
|
|
"errors"
|
|
"sort"
|
|
|
|
"git.cin.su/m/Assistant/contracts/work"
|
|
)
|
|
|
|
var (
|
|
ErrInvalidGraph = errors.New("invalid work graph")
|
|
ErrGraphCycle = errors.New("work graph contains a cycle")
|
|
)
|
|
|
|
func ValidateWorkGraph(graph work.WorkGraph) error {
|
|
if graph.ID == "" || graph.Revision < 1 || graph.Budget.MaxParallel < 1 || graph.Budget.MaxAttempts < 1 || len(graph.Nodes) == 0 {
|
|
return ErrInvalidGraph
|
|
}
|
|
nodes := make(map[work.GraphNodeID]struct{}, len(graph.Nodes))
|
|
keys := make(map[string]struct{}, len(graph.Nodes))
|
|
for _, node := range graph.Nodes {
|
|
if node.ID == "" || node.IdempotencyKey == "" || node.Attempts < 0 {
|
|
return ErrInvalidGraph
|
|
}
|
|
if _, exists := nodes[node.ID]; exists {
|
|
return ErrInvalidGraph
|
|
}
|
|
if _, exists := keys[node.IdempotencyKey]; exists {
|
|
return ErrInvalidGraph
|
|
}
|
|
nodes[node.ID] = struct{}{}
|
|
keys[node.IdempotencyKey] = struct{}{}
|
|
}
|
|
adjacency := make(map[work.GraphNodeID][]work.GraphNodeID, len(nodes))
|
|
for _, edge := range graph.Edges {
|
|
if edge.From == "" || edge.To == "" || edge.From == edge.To {
|
|
return ErrInvalidGraph
|
|
}
|
|
if _, ok := nodes[edge.From]; !ok {
|
|
return ErrInvalidGraph
|
|
}
|
|
if _, ok := nodes[edge.To]; !ok {
|
|
return ErrInvalidGraph
|
|
}
|
|
adjacency[edge.From] = append(adjacency[edge.From], edge.To)
|
|
}
|
|
visiting := map[work.GraphNodeID]bool{}
|
|
visited := map[work.GraphNodeID]bool{}
|
|
var visit func(work.GraphNodeID) error
|
|
visit = func(node work.GraphNodeID) error {
|
|
if visiting[node] {
|
|
return ErrGraphCycle
|
|
}
|
|
if visited[node] {
|
|
return nil
|
|
}
|
|
visiting[node] = true
|
|
for _, next := range adjacency[node] {
|
|
if err := visit(next); err != nil {
|
|
return err
|
|
}
|
|
}
|
|
delete(visiting, node)
|
|
visited[node] = true
|
|
return nil
|
|
}
|
|
for node := range nodes {
|
|
if err := visit(node); err != nil {
|
|
return err
|
|
}
|
|
}
|
|
return nil
|
|
}
|
|
|
|
func ReadyGraphNodes(graph work.WorkGraph) ([]work.GraphNodeID, error) {
|
|
if err := ValidateWorkGraph(graph); err != nil {
|
|
return nil, err
|
|
}
|
|
completed := map[work.GraphNodeID]bool{}
|
|
for _, node := range graph.Nodes {
|
|
if node.State == work.GraphNodeSuccess {
|
|
completed[node.ID] = true
|
|
}
|
|
}
|
|
blockedBy := map[work.GraphNodeID][]work.GraphNodeID{}
|
|
for _, edge := range graph.Edges {
|
|
blockedBy[edge.To] = append(blockedBy[edge.To], edge.From)
|
|
}
|
|
ready := make([]work.GraphNodeID, 0)
|
|
for _, node := range graph.Nodes {
|
|
if node.State != work.GraphNodeReady && node.State != work.GraphNodeBlocked {
|
|
continue
|
|
}
|
|
dependenciesReady := true
|
|
for _, dependency := range blockedBy[node.ID] {
|
|
if !completed[dependency] {
|
|
dependenciesReady = false
|
|
break
|
|
}
|
|
}
|
|
if dependenciesReady {
|
|
ready = append(ready, node.ID)
|
|
}
|
|
}
|
|
sort.Slice(ready, func(i, j int) bool { return ready[i] < ready[j] })
|
|
return ready, nil
|
|
}
|