112 lines
4.5 KiB
Go
112 lines
4.5 KiB
Go
package executor
|
||
|
||
import (
|
||
"fmt"
|
||
"strings"
|
||
|
||
"github.com/vladimir/goherence/internal/parser"
|
||
)
|
||
|
||
// orderTasks сортирует tasks по явным зависимостям (after/before), как
|
||
// require/before в Puppet, вместо жёсткого порядка "как написано в файле".
|
||
// Это СТАБИЛЬНАЯ топологическая сортировка: если ни один таск не объявляет
|
||
// after/before, результат побайтово совпадает с исходным порядком — граф
|
||
// зависимостей влияет только на то, что реально зависимостями объявлено,
|
||
// и не может незаметно переставить местами таски без причины.
|
||
//
|
||
// Алгоритм Кана с выбором наименьшего доступного индекса на каждом шаге
|
||
// (а не FIFO/DFS) — это и даёт стабильность: без явных рёбер все узлы
|
||
// доступны сразу, и они просто разбираются по порядку.
|
||
//
|
||
// Важная деталь тай-брейка: если из двух тасков без прямой связи друг
|
||
// с другом один вынужден сдвинуться из-за чужой зависимости, второй
|
||
// остаётся на исходном относительном месте — а не "уступает дорогу"
|
||
// первому. Иными словами, при конфликте сохраняется как можно больше
|
||
// исходных пар "было раньше" — но если это математически невозможно
|
||
// для ВСЕХ пар сразу (что бывает при before/after), какая именно пара
|
||
// "жертвуется" — вопрос тай-брейка, а не более раннего решения "правильно/неправильно".
|
||
func orderTasks(tasks []parser.Task) ([]parser.Task, error) {
|
||
n := len(tasks)
|
||
|
||
index := map[string]int{}
|
||
for i, t := range tasks {
|
||
if t.Name != "" {
|
||
if _, dup := index[t.Name]; dup {
|
||
return nil, fmt.Errorf("два таска с одинаковым именем %q — "+
|
||
"after/before не может однозначно на них сослаться", t.Name)
|
||
}
|
||
index[t.Name] = i
|
||
}
|
||
}
|
||
|
||
adj := make([][]int, n) // adj[i] — какие таски должны идти после i
|
||
indeg := make([]int, n)
|
||
|
||
addEdge := func(from, to int) {
|
||
if from == to {
|
||
return
|
||
}
|
||
adj[from] = append(adj[from], to)
|
||
indeg[to]++
|
||
}
|
||
|
||
for i, t := range tasks {
|
||
for _, depName := range t.After {
|
||
j, ok := index[depName]
|
||
if !ok {
|
||
return nil, fmt.Errorf("таск %q: after ссылается на неизвестный таск %q", t.Name, depName)
|
||
}
|
||
addEdge(j, i) // depName должен выполниться до t
|
||
}
|
||
for _, targetName := range t.Before {
|
||
j, ok := index[targetName]
|
||
if !ok {
|
||
return nil, fmt.Errorf("таск %q: before ссылается на неизвестный таск %q", t.Name, targetName)
|
||
}
|
||
addEdge(i, j) // t должен выполниться до targetName
|
||
}
|
||
}
|
||
|
||
visited := make([]bool, n)
|
||
var order []int
|
||
for len(order) < n {
|
||
picked := -1
|
||
for i := 0; i < n; i++ {
|
||
if !visited[i] && indeg[i] == 0 {
|
||
picked = i
|
||
break // наименьший индекс среди доступных — гарантирует стабильность
|
||
}
|
||
}
|
||
if picked == -1 {
|
||
return nil, fmt.Errorf("цикл в зависимостях тасков (after/before): %s", cycleHint(tasks, visited))
|
||
}
|
||
visited[picked] = true
|
||
order = append(order, picked)
|
||
for _, next := range adj[picked] {
|
||
indeg[next]--
|
||
}
|
||
}
|
||
|
||
out := make([]parser.Task, n)
|
||
for pos, idx := range order {
|
||
out[pos] = tasks[idx]
|
||
}
|
||
return out, nil
|
||
}
|
||
|
||
// cycleHint перечисляет имена тасков, которые не удалось разместить —
|
||
// то есть участников цикла (или зависящих от него), чтобы сообщение об
|
||
// ошибке указывало, где искать проблему, а не просто "где-то цикл".
|
||
func cycleHint(tasks []parser.Task, visited []bool) string {
|
||
var names []string
|
||
for i, v := range visited {
|
||
if !v {
|
||
name := tasks[i].Name
|
||
if name == "" {
|
||
name = fmt.Sprintf("#%d", i)
|
||
}
|
||
names = append(names, name)
|
||
}
|
||
}
|
||
return strings.Join(names, ", ")
|
||
}
|