// Package servicegraph models a service-dependency graph and the
// structural analyses an architect runs on it: cycle detection (the
// distributed-monolith smell), blast-radius (who breaks if X breaks),
// fan-in/fan-out coupling, and layering-rule enforcement. Stdlib-only.
package servicegraph

import "sort"

// Graph is a directed dependency graph: an edge from A to B means
// "A depends on B" (A calls / needs B).
type Graph struct {
	deps  map[string]map[string]bool // service -> set of services it depends on
	layer map[string]string          // service -> layer/tag (for layering rules)
	nodes map[string]bool
}

func New() *Graph {
	return &Graph{
		deps:  map[string]map[string]bool{},
		layer: map[string]string{},
		nodes: map[string]bool{},
	}
}

func (g *Graph) AddService(name string) { g.nodes[name] = true }

// SetLayer tags a service with a layer/domain for layering rules
// (e.g. "domain", "infra", "api").
func (g *Graph) SetLayer(name, layer string) {
	g.nodes[name] = true
	g.layer[name] = layer
}

// AddDependency records that `from` depends on `to`.
func (g *Graph) AddDependency(from, to string) {
	g.nodes[from] = true
	g.nodes[to] = true
	if g.deps[from] == nil {
		g.deps[from] = map[string]bool{}
	}
	g.deps[from][to] = true
}

// FanOut is the number of services a service directly depends on (its
// efferent coupling — how much it can be broken by others).
func (g *Graph) FanOut(svc string) int { return len(g.deps[svc]) }

// FanIn is the number of services that directly depend on a service (its
// afferent coupling — how much breaks if it breaks).
func (g *Graph) FanIn(svc string) int {
	n := 0
	for _, ds := range g.deps {
		if ds[svc] {
			n++
		}
	}
	return n
}

// Cycles returns dependency cycles (strongly-connected components of size
// > 1, plus self-loops) via Tarjan's algorithm. Any cycle is a
// distributed-monolith smell: those services cannot evolve or deploy
// independently. Deterministic output (sorted).
func (g *Graph) Cycles() [][]string {
	index := 0
	idx := map[string]int{}
	low := map[string]int{}
	onStack := map[string]bool{}
	var stack []string
	var out [][]string

	var dfs func(v string)
	dfs = func(v string) {
		idx[v] = index
		low[v] = index
		index++
		stack = append(stack, v)
		onStack[v] = true
		for _, w := range sortedKeys(g.deps[v]) {
			if _, seen := idx[w]; !seen {
				dfs(w)
				low[v] = min(low[v], low[w])
			} else if onStack[w] {
				low[v] = min(low[v], idx[w])
			}
		}
		if low[v] == idx[v] {
			var comp []string
			for {
				w := stack[len(stack)-1]
				stack = stack[:len(stack)-1]
				onStack[w] = false
				comp = append(comp, w)
				if w == v {
					break
				}
			}
			if len(comp) > 1 || g.deps[v][v] { // SCC>1 or a self-loop
				sort.Strings(comp)
				out = append(out, comp)
			}
		}
	}
	for _, v := range g.sortedNodes() {
		if _, seen := idx[v]; !seen {
			dfs(v)
		}
	}
	return out
}

// HasCycle reports whether any dependency cycle exists.
func (g *Graph) HasCycle() bool { return len(g.Cycles()) > 0 }

// BlastRadius returns every service that transitively depends on svc —
// i.e. everything that is affected if svc fails. Sorted, excludes svc.
func (g *Graph) BlastRadius(svc string) []string {
	// reverse reachability over the dependency edges
	affected := map[string]bool{}
	var visit func(s string)
	visit = func(s string) {
		for _, dependent := range g.dependentsOf(s) {
			if !affected[dependent] {
				affected[dependent] = true
				visit(dependent)
			}
		}
	}
	visit(svc)
	delete(affected, svc)
	out := make([]string, 0, len(affected))
	for s := range affected {
		out = append(out, s)
	}
	sort.Strings(out)
	return out
}

func (g *Graph) dependentsOf(svc string) []string {
	var out []string
	for from, ds := range g.deps {
		if ds[svc] {
			out = append(out, from)
		}
	}
	sort.Strings(out)
	return out
}

// LayerRule forbids services in layer From from depending on services in
// layer To (e.g. {From:"domain", To:"infra"} keeps domain logic
// independent of infrastructure).
type LayerRule struct{ From, To string }

// Violation is a dependency edge that breaks a layer rule.
type Violation struct {
	From, To   string
	FromLayer  string
	ToLayer    string
}

// LayeringViolations returns edges that break any layer rule — the kind
// of architecture constraint an architect encodes as a fitness function
// (pa-10).
func (g *Graph) LayeringViolations(rules []LayerRule) []Violation {
	var out []Violation
	for _, from := range g.sortedNodes() {
		for _, to := range sortedKeys(g.deps[from]) {
			fl, tl := g.layer[from], g.layer[to]
			for _, r := range rules {
				if fl == r.From && tl == r.To {
					out = append(out, Violation{From: from, To: to, FromLayer: fl, ToLayer: tl})
				}
			}
		}
	}
	return out
}

func (g *Graph) sortedNodes() []string {
	out := make([]string, 0, len(g.nodes))
	for n := range g.nodes {
		out = append(out, n)
	}
	sort.Strings(out)
	return out
}

func sortedKeys(m map[string]bool) []string {
	out := make([]string, 0, len(m))
	for k := range m {
		out = append(out, k)
	}
	sort.Strings(out)
	return out
}