toposort.gno
5.89 Kb · 217 lines
1// Package toposort orders a dependency graph so that every node comes after
2// 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 always
6// taken in lexicographic order, so a given graph always yields the exact same
7// ordering. That matters on-chain, where a Render that reshuffled between
8// identical calls would be a bug. Adjacency is kept in sorted slices rather
9// 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 than
12// panicking or silently dropping them.
13//
14// A live demo of this package is at
15// [r/moul/x/daily/toposortdemo](/r/moul/x/daily/toposortdemo/v0).
16package toposort
17
18import (
19 "errors"
20 "sort"
21 "strings"
22)
23
24// ErrCycle is returned by Sort when the graph is not a DAG. Use CycleNodes to
25// recover which nodes are involved.
26var ErrCycle = errors.New("toposort: graph has a cycle")
27
28// Graph is a directed dependency graph. The zero value is not usable — build
29// one with New.
30type Graph struct {
31 nodes []string // every known node, kept sorted and unique
32 deps map[string][]string // node -> the nodes it depends on (sorted, unique)
33}
34
35// New returns an empty Graph.
36func New() *Graph {
37 return &Graph{deps: map[string][]string{}}
38}
39
40// Add registers a node with no dependencies. Adding twice is a no-op; it is
41// how you declare a leaf that nothing depends on.
42func (g *Graph) Add(node string) {
43 if node == "" {
44 return
45 }
46 g.addNode(node)
47}
48
49// DependOn records that node depends on dep, so dep must come first. Both
50// endpoints are registered. A self-dependency is ignored (it would be a
51// trivial cycle and is never what the caller means). Duplicate edges collapse.
52func (g *Graph) DependOn(node, dep string) {
53 if node == "" || dep == "" {
54 return
55 }
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, but
60 // the node was still named, so it stays in the graph as a leaf.
61 return
62 }
63 cur := g.deps[node]
64 i := sort.SearchStrings(cur, dep)
65 if i < len(cur) && cur[i] == dep {
66 return // already recorded
67 }
68 cur = append(cur, "")
69 copy(cur[i+1:], cur[i:])
70 cur[i] = dep
71 g.deps[node] = cur
72}
73
74// 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 return
79 }
80 g.nodes = append(g.nodes, "")
81 copy(g.nodes[i+1:], g.nodes[i:])
82 g.nodes[i] = node
83}
84
85// Len returns how many nodes the graph holds.
86func (g *Graph) Len() int { return len(g.nodes) }
87
88// 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 out
93}
94
95// 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 out
101}
102
103// Sort returns the nodes ordered so every node follows its dependencies.
104//
105// Among nodes that are simultaneously ready, the lexicographically smallest is
106// emitted first, which makes the result unique for a given graph. On a cycle it
107// 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 }
119
120 // ready holds nodes with no unresolved dependency, kept sorted so the
121 // smallest is always taken first.
122 ready := []string{}
123 for _, n := range g.nodes { // g.nodes is already sorted
124 if indegree[n] == 0 {
125 ready = append(ready, n)
126 }
127 }
128
129 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)
134
135 // Releasing dependents can make several ready at once; collect them and
136 // 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 }
149
150 if len(out) != len(g.nodes) {
151 return out, ErrCycle
152 }
153 return out, nil
154}
155
156// CycleNodes returns the nodes that could not be ordered — i.e. those on or
157// 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] = true
166 }
167 stuck := []string{}
168 for _, n := range g.nodes {
169 if !placed[n] {
170 stuck = append(stuck, n)
171 }
172 }
173 return stuck
174}
175
176// 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, 0
180 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 out
192}
193
194// FromPairs builds a Graph from "node depends on dep" pairs. Each pair is
195// {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 g
202}
203
204// String renders the graph as "node <- dep1, dep2" lines, sorted. Useful for
205// debugging and for demos.
206func (g *Graph) String() string {
207 var b strings.Builder
208 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}
