gno.land/p/moul/x/daily/toposort/v0⧉

1// Package toposort orders a dependency graph so that every node comes after2// everything it depends on — the "install these packages in a safe order"3// problem — as a pure, reusable package.4//5// It uses Kahn's algorithm, and it is *deterministic*: ready nodes are always6// taken in lexicographic order, so a given graph always yields the exact same7// ordering. That matters on-chain, where a Render that reshuffled between8// identical calls would be a bug. Adjacency is kept in sorted slices rather9// than maps for the same reason — Go/gno map iteration order is unspecified.10//11// A cycle is reported as an error naming the nodes still stuck, rather than12// panicking or silently dropping them.13//14// A live demo of this package is at15// [r/moul/x/daily/toposortdemo](/r/moul/x/daily/toposortdemo/v0).16package toposort1718import (19	"errors"20	"sort"21	"strings"22)2324// ErrCycle is returned by Sort when the graph is not a DAG. Use CycleNodes to25// recover which nodes are involved.26var ErrCycle = errors.New("toposort: graph has a cycle")2728// Graph is a directed dependency graph. The zero value is not usable — build29// one with New.30type Graph struct {31	nodes []string            // every known node, kept sorted and unique32	deps  map[string][]string // node -> the nodes it depends on (sorted, unique)33}3435// New returns an empty Graph.36func New() *Graph {37	return &Graph{deps: map[string][]string{}}38}3940// Add registers a node with no dependencies. Adding twice is a no-op; it is41// how you declare a leaf that nothing depends on.42func (g *Graph) Add(node string) {43	if node == "" {44		return45	}46	g.addNode(node)47}4849// DependOn records that node depends on dep, so dep must come first. Both50// endpoints are registered. A self-dependency is ignored (it would be a51// trivial cycle and is never what the caller means). Duplicate edges collapse.52func (g *Graph) DependOn(node, dep string) {53	if node == "" || dep == "" {54		return55	}56	g.addNode(node)57	g.addNode(dep)58	if node == dep {59		// A self-edge is a trivial cycle and never what the caller means, but60		// the node was still named, so it stays in the graph as a leaf.61		return62	}63	cur := g.deps[node]64	i := sort.SearchStrings(cur, dep)65	if i < len(cur) && cur[i] == dep {66		return // already recorded67	}68	cur = append(cur, "")69	copy(cur[i+1:], cur[i:])70	cur[i] = dep71	g.deps[node] = cur72}7374// addNode inserts node into the sorted node list if absent.75func (g *Graph) addNode(node string) {76	i := sort.SearchStrings(g.nodes, node)77	if i < len(g.nodes) && g.nodes[i] == node {78		return79	}80	g.nodes = append(g.nodes, "")81	copy(g.nodes[i+1:], g.nodes[i:])82	g.nodes[i] = node83}8485// Len returns how many nodes the graph holds.86func (g *Graph) Len() int { return len(g.nodes) }8788// Nodes returns every node in lexicographic order.89func (g *Graph) Nodes() []string {90	out := make([]string, len(g.nodes))91	copy(out, g.nodes)92	return out93}9495// DependenciesOf returns node's direct dependencies, sorted.96func (g *Graph) DependenciesOf(node string) []string {97	d := g.deps[node]98	out := make([]string, len(d))99	copy(out, d)100	return out101}102103// Sort returns the nodes ordered so every node follows its dependencies.104//105// Among nodes that are simultaneously ready, the lexicographically smallest is106// emitted first, which makes the result unique for a given graph. On a cycle it107// returns ErrCycle along with the partial order computed so far.108func (g *Graph) Sort() ([]string, error) {109	// indegree[n] = how many of n's dependencies are still unresolved.110	indegree := map[string]int{}111	// dependents[d] = nodes waiting on d.112	dependents := map[string][]string{}113	for _, n := range g.nodes {114		indegree[n] = len(g.deps[n])115		for _, d := range g.deps[n] {116			dependents[d] = append(dependents[d], n)117		}118	}119120	// ready holds nodes with no unresolved dependency, kept sorted so the121	// smallest is always taken first.122	ready := []string{}123	for _, n := range g.nodes { // g.nodes is already sorted124		if indegree[n] == 0 {125			ready = append(ready, n)126		}127	}128129	out := make([]string, 0, len(g.nodes))130	for len(ready) > 0 {131		n := ready[0]132		ready = ready[1:]133		out = append(out, n)134135		// Releasing dependents can make several ready at once; collect them and136		// merge into the sorted queue so ordering stays deterministic.137		freed := []string{}138		for _, m := range dependents[n] {139			indegree[m]--140			if indegree[m] == 0 {141				freed = append(freed, m)142			}143		}144		if len(freed) > 0 {145			sort.Strings(freed)146			ready = mergeSorted(ready, freed)147		}148	}149150	if len(out) != len(g.nodes) {151		return out, ErrCycle152	}153	return out, nil154}155156// CycleNodes returns the nodes that could not be ordered — i.e. those on or157// downstream of a cycle — in lexicographic order. Empty when the graph is a DAG.158func (g *Graph) CycleNodes() []string {159	done, err := g.Sort()160	if err == nil {161		return []string{}162	}163	placed := map[string]bool{}164	for _, n := range done {165		placed[n] = true166	}167	stuck := []string{}168	for _, n := range g.nodes {169		if !placed[n] {170			stuck = append(stuck, n)171		}172	}173	return stuck174}175176// mergeSorted merges two sorted string slices into one sorted slice.177func mergeSorted(a, b []string) []string {178	out := make([]string, 0, len(a)+len(b))179	i, j := 0, 0180	for i < len(a) && j < len(b) {181		if a[i] <= b[j] {182			out = append(out, a[i])183			i++184		} else {185			out = append(out, b[j])186			j++187		}188	}189	out = append(out, a[i:]...)190	out = append(out, b[j:]...)191	return out192}193194// FromPairs builds a Graph from "node depends on dep" pairs. Each pair is195// {node, dep}. Handy for tests and literal declarations.196func FromPairs(pairs [][2]string) *Graph {197	g := New()198	for _, p := range pairs {199		g.DependOn(p[0], p[1])200	}201	return g202}203204// String renders the graph as "node <- dep1, dep2" lines, sorted. Useful for205// debugging and for demos.206func (g *Graph) String() string {207	var b strings.Builder208	for _, n := range g.nodes {209		b.WriteString(n)210		if d := g.deps[n]; len(d) > 0 {211			b.WriteString(" <- ")212			b.WriteString(strings.Join(d, ", "))213		}214		b.WriteString("\n")215	}216	return b.String()217}218