package definition

import (
	"fmt"
	"sort"
	"strings"
)

// FindSubagentCycle reports the first delegation cycle in a set of agents, or
// "" if the graph is acyclic.
//
// §3: "subagents must form a DAG. Cycle detection runs at publish." This is the
// publish-time half. The runtime half is runtime.MaxDelegationDepth, which
// bounds a cycle that reaches run time anyway — because a graph can only be
// checked against the agents the checker was GIVEN, and an agent published
// while another is being edited can complete a loop neither publish saw.
//
// The returned string names the cycle in the order it was walked, so an
// operator can see which edge to cut:
//
//	a -> b -> c -> a
//
// Edges pointing at agents not in the set are ignored rather than treated as
// missing. Resolving those is a different check with a different message
// (runtime.unknown_subagent), and conflating the two produces "cycle detected"
// for what is actually a typo.
func FindSubagentCycle(subagents map[string][]string) string {
	// Depth-first search tracking the path, so the cycle can be REPORTED
	// rather than merely detected — "there is a cycle" leaves an operator to
	// find it by hand across a set of specs.
	//
	// Recursive, and deliberately: a goroutine stack grows on demand, so depth
	// here costs memory rather than a crash, and a 5000-long chain is covered
	// by a test. An explicit stack would buy nothing and lose the path
	// bookkeeping that makes the message useful.
	const (
		unvisited = 0
		onPath    = 1
		done      = 2
	)
	state := make(map[string]int, len(subagents))

	// Sorted, so the same set of agents always reports the same cycle. An
	// error message that changes between runs on identical input is one
	// nobody trusts.
	roots := make([]string, 0, len(subagents))
	for id := range subagents {
		roots = append(roots, id)
	}
	sort.Strings(roots)

	var path []string
	var walk func(id string) string
	walk = func(id string) string {
		switch state[id] {
		case done:
			return ""
		case onPath:
			// Found it. Report from the first occurrence of this id, so the
			// message is the cycle itself and not the walk that reached it.
			for i, seen := range path {
				if seen == id {
					return strings.Join(append(append([]string{}, path[i:]...), id), " -> ")
				}
			}
			return id + " -> " + id
		}

		state[id] = onPath
		path = append(path, id)
		for _, next := range subagents[id] {
			if _, known := subagents[next]; !known {
				continue // not ours to judge; see the doc comment
			}
			if cycle := walk(next); cycle != "" {
				return cycle
			}
		}
		path = path[:len(path)-1]
		state[id] = done
		return ""
	}

	for _, id := range roots {
		if cycle := walk(id); cycle != "" {
			return cycle
		}
	}
	return ""
}

// ErrVersionWentBackwards describes a publish that lowers a version.
//
// §3 calls the version monotonic. Nothing enforced it: the upsert wrote
// whatever the frontmatter said, so a spec edited from an older copy silently
// rolled a deployed agent backwards — no conflict, because the older version's
// content still matched what was published under that number.
func ErrVersionWentBackwards(id string, from, to int) error {
	return fmt.Errorf(
		"%q is published at version %d and this publishes version %d; "+
			"a version is monotonic, so raise it above %d rather than lowering it",
		id, from, to, from)
}