package main

import "sort"

// SCC is a strongly connected component over first-party modules.
type SCC struct {
	Members []string // sorted module paths
}

// Key is a stable, order-independent identity for an SCC: its sorted members
// joined by "|". Used to match against the accepted-SCC allowlist.
func (s SCC) Key() string {
	members := append([]string(nil), s.Members...)
	sort.Strings(members)
	out := ""
	for i, m := range members {
		if i > 0 {
			out += "|"
		}
		out += m
	}
	return out
}

// tarjanSCC computes strongly connected components over the first-party module
// graph using require-direction edges (module -> its required first-party deps).
// Only modules present as keys in `nodes` participate; edges to absent modules
// are ignored. Missing placeholder modules are skipped entirely.
func tarjanSCC(modules map[string]*Module) []SCC {
	// Build the node set and adjacency over present, non-missing modules.
	nodes := make([]string, 0, len(modules))
	present := map[string]bool{}
	for p, m := range modules {
		if m.Missing {
			continue
		}
		nodes = append(nodes, p)
		present[p] = true
	}
	sort.Strings(nodes) // deterministic ordering -> deterministic SCC output

	adj := map[string][]string{}
	for _, p := range nodes {
		m := modules[p]
		var out []string
		seen := map[string]bool{}
		for _, dep := range m.firstPartyEdges() {
			if present[dep] && !seen[dep] {
				out = append(out, dep)
				seen[dep] = true
			}
		}
		sort.Strings(out)
		adj[p] = out
	}

	var (
		index   = 0
		indices = map[string]int{}
		lowlink = map[string]int{}
		onStack = map[string]bool{}
		stack   []string
		sccs    []SCC
	)

	// Iterative Tarjan to avoid recursion-depth surprises on larger graphs.
	type frame struct {
		node string
		i    int // next neighbor index to process
	}

	for _, root := range nodes {
		if _, ok := indices[root]; ok {
			continue
		}
		var callStack []*frame
		callStack = append(callStack, &frame{node: root, i: 0})
		indices[root] = index
		lowlink[root] = index
		index++
		stack = append(stack, root)
		onStack[root] = true

		for len(callStack) > 0 {
			fr := callStack[len(callStack)-1]
			v := fr.node
			neighbors := adj[v]

			if fr.i < len(neighbors) {
				w := neighbors[fr.i]
				fr.i++
				if _, visited := indices[w]; !visited {
					indices[w] = index
					lowlink[w] = index
					index++
					stack = append(stack, w)
					onStack[w] = true
					callStack = append(callStack, &frame{node: w, i: 0})
				} else if onStack[w] {
					if indices[w] < lowlink[v] {
						lowlink[v] = indices[w]
					}
				}
				continue
			}

			// Done with v's neighbors. If v is an SCC root, pop the component.
			if lowlink[v] == indices[v] {
				var comp []string
				for {
					n := len(stack) - 1
					w := stack[n]
					stack = stack[:n]
					onStack[w] = false
					comp = append(comp, w)
					if w == v {
						break
					}
				}
				sort.Strings(comp)
				sccs = append(sccs, SCC{Members: comp})
			}

			// Pop v and propagate lowlink to its parent.
			callStack = callStack[:len(callStack)-1]
			if len(callStack) > 0 {
				parent := callStack[len(callStack)-1].node
				if lowlink[v] < lowlink[parent] {
					lowlink[parent] = lowlink[v]
				}
			}
		}
	}

	// Deterministic output: sort SCCs by their first member.
	sort.Slice(sccs, func(i, j int) bool {
		return sccs[i].Members[0] < sccs[j].Members[0]
	})
	return sccs
}

// nontrivialSCCs returns only SCCs with more than one member (true cycles).
func nontrivialSCCs(sccs []SCC) []SCC {
	var out []SCC
	for _, s := range sccs {
		if len(s.Members) > 1 {
			out = append(out, s)
		}
	}
	return out
}