toposortdemo.gno

  1// Package toposortdemo is a small gnoweb demo of the dependency ordering
  2// provided by the [p/moul/x/daily/toposort](/p/moul/x/daily/toposort/v0)
  3// library: it shows a build graph resolved into a safe install order, and a
  4// deliberately broken graph to show how a cycle is reported.
  5//
  6// It contains no ordering logic of its own — the graph, the sort and the cycle
  7// detection all come from the library. Stateless and read-only, so Render is
  8// fully deterministic.
  9package toposortdemo
 10
 11import (
 12	"strconv"
 13	"strings"
 14
 15	"gno.land/p/moul/x/daily/toposort/v0"
 16)
 17
 18// buildGraph is a small, realistic dependency graph: a realm on top of a couple
 19// of libraries, themselves on a shared core.
 20func buildGraph() *toposort.Graph {
 21	return toposort.FromPairs([][2]string{
 22		{"realm", "ui"},
 23		{"realm", "storage"},
 24		{"ui", "markdown"},
 25		{"storage", "avl"},
 26		{"markdown", "strings"},
 27		{"avl", "strings"},
 28	})
 29}
 30
 31// cyclicGraph is broken on purpose: auth and session need each other.
 32func cyclicGraph() *toposort.Graph {
 33	return toposort.FromPairs([][2]string{
 34		{"server", "auth"},
 35		{"auth", "session"},
 36		{"session", "auth"},
 37	})
 38}
 39
 40// Render renders the demo for gnoweb.
 41//
 42//	Render("")       / Render("/") -> the build graph, resolved
 43//	Render("/cycle")               -> the broken graph and its report
 44func Render(path string) string {
 45	var b strings.Builder
 46	b.WriteString("# Topological Sort\n\n")
 47	b.WriteString("Ordering a dependency graph so nothing is built before what it needs, ")
 48	b.WriteString("demoing the [`p/moul/x/daily/toposort`](/p/moul/x/daily/toposort/v0) library.\n\n")
 49
 50	if parseArg(path) == "cycle" {
 51		return b.String() + renderCycle()
 52	}
 53
 54	g := buildGraph()
 55	b.WriteString("## The graph\n\n```\n")
 56	b.WriteString(g.String())
 57	b.WriteString("```\n\n")
 58
 59	order, err := g.Sort()
 60	if err != nil {
 61		b.WriteString("_Unexpectedly cyclic._\n")
 62		return b.String()
 63	}
 64	b.WriteString("## Install order\n\n")
 65	for i, n := range order {
 66		b.WriteString(strconv.Itoa(i + 1))
 67		b.WriteString(". `")
 68		b.WriteString(n)
 69		b.WriteString("`\n")
 70	}
 71	b.WriteString("\nTies are broken lexicographically, so this ordering is the ")
 72	b.WriteString("*only* one the library will ever produce for this graph.\n\n")
 73	b.WriteString("> See [`/cycle`](/r/moul/x/daily/toposortdemo/v0:cycle) for what happens ")
 74	b.WriteString("when the graph is not a DAG.\n")
 75	return b.String()
 76}
 77
 78// renderCycle shows the failure mode.
 79func renderCycle() string {
 80	g := cyclicGraph()
 81	var b strings.Builder
 82	b.WriteString("## A graph with a cycle\n\n```\n")
 83	b.WriteString(g.String())
 84	b.WriteString("```\n\n")
 85
 86	order, err := g.Sort()
 87	if err == nil {
 88		b.WriteString("_Unexpectedly acyclic._\n")
 89		return b.String()
 90	}
 91	b.WriteString("`Sort` returns an error: **")
 92	b.WriteString(err.Error())
 93	b.WriteString("**\n\n")
 94	b.WriteString("Ordered before giving up: ")
 95	if len(order) == 0 {
 96		b.WriteString("_nothing_")
 97	} else {
 98		b.WriteString("`" + strings.Join(order, "`, `") + "`")
 99	}
100	b.WriteString("\n\nStuck on the cycle: `")
101	b.WriteString(strings.Join(g.CycleNodes(), "`, `"))
102	b.WriteString("`\n\n> The nodes still stuck are named rather than silently dropped, ")
103	b.WriteString("so a caller can report exactly which dependencies are tangled.\n")
104	return b.String()
105}
106
107// parseArg extracts the first path segment.
108func parseArg(path string) string {
109	s := strings.TrimSpace(path)
110	s = strings.TrimPrefix(s, "/")
111	if i := strings.IndexByte(s, '/'); i >= 0 {
112		s = s[:i]
113	}
114	return s
115}