toposort_test.gno

  1package toposort
  2
  3import (
  4	"strings"
  5	"testing"
  6
  7	"gno.land/p/nt/uassert/v0"
  8)
  9
 10// order asserts a successful sort and returns the joined result.
 11func order(t *testing.T, g *Graph) string {
 12	t.Helper()
 13	out, err := g.Sort()
 14	uassert.NoError(t, err)
 15	return strings.Join(out, ",")
 16}
 17
 18func TestLinearChain(t *testing.T) {
 19	// c depends on b depends on a
 20	g := FromPairs([][2]string{{"c", "b"}, {"b", "a"}})
 21	uassert.Equal(t, "a,b,c", order(t, g))
 22}
 23
 24func TestDependenciesComeFirst(t *testing.T) {
 25	g := FromPairs([][2]string{
 26		{"app", "lib"},
 27		{"lib", "core"},
 28		{"app", "core"},
 29	})
 30	uassert.Equal(t, "core,lib,app", order(t, g))
 31}
 32
 33// Ties are broken lexicographically, so a given graph has exactly one answer —
 34// the property that keeps an on-chain Render stable.
 35func TestTiesAreLexicographic(t *testing.T) {
 36	g := New()
 37	for _, n := range []string{"delta", "alpha", "charlie", "bravo"} {
 38		g.Add(n)
 39	}
 40	uassert.Equal(t, "alpha,bravo,charlie,delta", order(t, g))
 41}
 42
 43func TestResultIsIndependentOfInsertionOrder(t *testing.T) {
 44	a := FromPairs([][2]string{{"c", "b"}, {"b", "a"}, {"d", "a"}})
 45	b := FromPairs([][2]string{{"d", "a"}, {"b", "a"}, {"c", "b"}})
 46	uassert.Equal(t, order(t, a), order(t, b))
 47}
 48
 49func TestIsolatedNodes(t *testing.T) {
 50	g := New()
 51	g.Add("solo")
 52	g.DependOn("b", "a")
 53	uassert.Equal(t, "a,b,solo", order(t, g))
 54}
 55
 56func TestEmptyGraph(t *testing.T) {
 57	g := New()
 58	out, err := g.Sort()
 59	uassert.NoError(t, err)
 60	uassert.Equal(t, 0, len(out))
 61	uassert.Equal(t, 0, g.Len())
 62}
 63
 64func TestCycleIsReported(t *testing.T) {
 65	g := FromPairs([][2]string{{"a", "b"}, {"b", "c"}, {"c", "a"}})
 66	out, err := g.Sort()
 67	uassert.Error(t, err)
 68	uassert.Equal(t, 0, len(out)) // nothing could start
 69	uassert.Equal(t, "a,b,c", strings.Join(g.CycleNodes(), ","))
 70}
 71
 72// A cycle downstream of a healthy prefix still orders the prefix, and reports
 73// only the stuck part.
 74func TestPartialOrderBeforeCycle(t *testing.T) {
 75	g := FromPairs([][2]string{
 76		{"b", "a"}, // fine
 77		{"x", "y"}, // cycle…
 78		{"y", "x"}, // …here
 79	})
 80	out, err := g.Sort()
 81	uassert.Error(t, err)
 82	uassert.Equal(t, "a,b", strings.Join(out, ","))
 83	uassert.Equal(t, "x,y", strings.Join(g.CycleNodes(), ","))
 84}
 85
 86func TestCycleNodesEmptyOnDAG(t *testing.T) {
 87	g := FromPairs([][2]string{{"b", "a"}})
 88	uassert.Equal(t, 0, len(g.CycleNodes()))
 89}
 90
 91// A self-dependency is meaningless and must not deadlock the graph.
 92func TestSelfDependencyIgnored(t *testing.T) {
 93	g := New()
 94	g.DependOn("a", "a")
 95	uassert.Equal(t, "a", order(t, g))
 96	uassert.Equal(t, 0, len(g.DependenciesOf("a")))
 97}
 98
 99func TestDuplicateEdgesCollapse(t *testing.T) {
100	g := New()
101	g.DependOn("b", "a")
102	g.DependOn("b", "a")
103	uassert.Equal(t, 1, len(g.DependenciesOf("b")))
104	uassert.Equal(t, "a,b", order(t, g))
105}
106
107func TestEmptyNamesIgnored(t *testing.T) {
108	g := New()
109	g.Add("")
110	g.DependOn("", "a")
111	g.DependOn("a", "")
112	uassert.Equal(t, 0, g.Len())
113}
114
115func TestNodesAndDependenciesAreCopies(t *testing.T) {
116	g := FromPairs([][2]string{{"b", "a"}})
117	ns := g.Nodes()
118	ns[0] = "mutated"
119	uassert.Equal(t, "a,b", strings.Join(g.Nodes(), ","))
120
121	ds := g.DependenciesOf("b")
122	ds[0] = "mutated"
123	uassert.Equal(t, "a", strings.Join(g.DependenciesOf("b"), ","))
124}
125
126func TestString(t *testing.T) {
127	g := FromPairs([][2]string{{"app", "lib"}, {"app", "core"}})
128	uassert.Equal(t, "app <- core, lib\ncore\nlib\n", g.String())
129}
130
131// A wide diamond: both middles are ready at once and must come out sorted.
132func TestDiamond(t *testing.T) {
133	g := FromPairs([][2]string{
134		{"top", "left"},
135		{"top", "right"},
136		{"left", "base"},
137		{"right", "base"},
138	})
139	uassert.Equal(t, "base,left,right,top", order(t, g))
140}