Agent-Squad/squad/graph_test.go

package squad

import (
	"strings"
	"testing"
)

func stepsOf(specs ...StepSpec) []StepSpec {
	out := make([]StepSpec, len(specs))
	copy(out, specs)
	return out
}

func TestCompileGraphLinearAndAdjacentParallel(t *testing.T) {
	steps := stepsOf(
		StepSpec{ID: "a", Status: "pending"},
		StepSpec{ID: "b", Status: "pending", Parallel: true},
		StepSpec{ID: "c", Status: "pending", Parallel: true},
		StepSpec{ID: "d", Status: "pending"},
	)
	g, err := compileGraph(steps)
	if err != nil {
		t.Fatal(err)
	}
	// 线性链：b/c 同层依赖 a，d 依赖 c。
	if len(g.needs["a"]) != 0 {
		t.Fatalf("a needs = %v", g.needs["a"])
	}
	if len(g.needs["b"]) != 1 || g.needs["b"][0] != "a" || g.needs["c"][0] != "a" {
		t.Fatalf("parallel needs = %v %v", g.needs["b"], g.needs["c"])
	}
	if len(g.needs["d"]) != 1 || g.needs["d"][0] != "c" {
		t.Fatalf("d needs = %v", g.needs["d"])
	}
	// 首轮可执行：只有 a。
	layer, ok := g.nextLayer(steps)
	if !ok || len(layer.par) != 1 || layer.par[0] != 0 || len(layer.seq) != 0 {
		t.Fatalf("first layer = %+v", layer)
	}
	// a 完成后：b、c 同层并行。
	steps[0].Status = "completed"
	layer, ok = g.nextLayer(steps)
	if !ok || len(layer.par) != 2 || layer.par[0] != 1 || layer.par[1] != 2 {
		t.Fatalf("second layer = %+v", layer)
	}
}

func TestCompileGraphNeedsPruneAndMixed(t *testing.T) {
	steps := stepsOf(
		StepSpec{ID: "a", Status: "pending"},
		StepSpec{ID: "b", Status: "pending"},
		StepSpec{ID: "c", Status: "pending", Needs: []string{"a"}},
	)
	g, err := compileGraph(steps)
	if err != nil {
		t.Fatal(err)
	}
	// a 完成后：b（线性依赖 a）与 c（needs a）同层。
	steps[0].Status = "completed"
	layer, ok := g.nextLayer(steps)
	if !ok || len(layer.par) != 2 {
		t.Fatalf("layer = %+v", layer)
	}
	// b 失败（非关键降级）后 c 仍按 needs 调度（与线性扫描的降级继续一致）。
	steps[1].Status = "failed"
	layer, ok = g.nextLayer(steps)
	if !ok || len(layer.par)+len(layer.seq) == 0 {
		t.Fatalf("after b failed: layer = %+v", layer)
	}
}

func TestCompileGraphRejectsUnknownAndCycleAndDup(t *testing.T) {
	if _, err := compileGraph(stepsOf(
		StepSpec{ID: "a", Status: "pending", Needs: []string{"ghost"}},
	)); err == nil || !strings.Contains(err.Error(), "未知步骤") {
		t.Fatalf("unknown ref: %v", err)
	}
	if _, err := compileGraph(stepsOf(
		StepSpec{ID: "a", Status: "pending", Needs: []string{"b"}},
		StepSpec{ID: "b", Status: "pending", Needs: []string{"a"}},
	)); err == nil || !strings.Contains(err.Error(), "成环") {
		t.Fatalf("cycle: %v", err)
	}
	if _, err := compileGraph(stepsOf(
		StepSpec{ID: "a", Status: "pending"},
		StepSpec{ID: "a", Status: "pending"},
	)); err == nil || !strings.Contains(err.Error(), "重复") {
		t.Fatalf("dup: %v", err)
	}
	if _, err := compileGraph(stepsOf(
		StepSpec{ID: "a", Status: "pending", Needs: []string{"a"}},
	)); err == nil || !strings.Contains(err.Error(), "自身") {
		t.Fatalf("self ref: %v", err)
	}
}

func TestWriteSetConflictSerializes(t *testing.T) {
	steps := stepsOf(
		StepSpec{ID: "z", Status: "completed"},
		StepSpec{ID: "a", Status: "pending", Parallel: true, Writes: []string{"report.md"}},
		StepSpec{ID: "b", Status: "pending", Parallel: true, Writes: []string{"report.md"}},
		StepSpec{ID: "c", Status: "pending", Parallel: true, Writes: []string{"notes.md"}},
		StepSpec{ID: "d", Status: "pending", Parallel: true},
	)
	// 全部首轮可执行（无依赖）：b 与 a 冲突 → b 串行；c、d 无冲突 → 并行。
	g, err := compileGraph(steps)
	if err != nil {
		t.Fatal(err)
	}
	layer, ok := g.nextLayer(steps)
	if !ok {
		t.Fatal("no layer")
	}
	if len(layer.seq) != 1 || layer.seq[0] != 2 {
		t.Fatalf("seq = %v", layer.seq)
	}
	if len(layer.par) != 3 || layer.par[0] != 1 || layer.par[1] != 3 || layer.par[2] != 4 {
		t.Fatalf("par = %v", layer.par)
	}
}

func TestFailedDependencyStillSchedules(t *testing.T) {
	// 与线性扫描的「非关键失败降级继续」一致：依赖 failed 仍视为满足。
	steps := stepsOf(
		StepSpec{ID: "b", Status: "failed"},
		StepSpec{ID: "a", Status: "pending", Needs: []string{"b"}},
	)
	g, err := compileGraph(steps)
	if err != nil {
		t.Fatal(err)
	}
	layer, ok := g.nextLayer(steps)
	if !ok || len(layer.par) != 1 || layer.par[0] != 1 {
		t.Fatalf("failed dependency should still schedule: %+v", layer)
	}
	if pendingCount(steps) != 1 {
		t.Fatalf("pending = %d", pendingCount(steps))
	}
}