src/simd/archsimd/_gen/cmd/spectasks/main.go - go - Git at Google

 // Copyright 2026 The Go Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.

 // Spectasks renders SPEC-TRANSITION.md's task dependencies as a Graphviz
 // graph, and checks the document's copies of those dependencies against each
 // other.
 //
 //	go run ./cmd/spectasks -w        # write SPEC-TASKS.dot
 //	go run ./cmd/spectasks           # check only; write the graph to stdout
 //
 // SPEC-TRANSITION.md states its dependencies three times: once in Part 2's
 // table, which this tool treats as the source of truth; once per task in
 // Part 3's "Needs:"/"Prefers:" header lines; and a third time, reversed, in
 // Part 3's "Blocks:" lines. go test ./cmd/spectasks fails if they disagree, and
 // also fails if SPEC-TASKS.dot has not been regenerated since. Adding the graph
 // as a fourth hand-maintained copy would have made that worse, so the graph is
 // generated.
 //
 // Two things the graph shows that the table cannot. The critical path is
 // computed, not asserted: a task is on it when delaying it delays the whole
 // project, which is the set of tasks whose longest-chain-in plus
 // longest-chain-out spans the graph. And milestones -- the points worth
 // announcing -- are drawn as nodes, so it is visible which tasks feed them.
 // Milestone state is derived from the task checkboxes and is never written
 // down separately.
 package main

 import (
 	"bytes"
 	"cmp"
 	"flag"
 	"fmt"
 	"log"
 	"os"
 	"path/filepath"
 	"regexp"
 	"slices"
 	"strings"

 	"simd/archsimd/_gen/gentools"
 	"simd/archsimd/_gen/specgen"
 )

 // paths returns the plan document and the graph generated from it.
 func paths(goroot string) (md, dot string) {
 	specDir := specgen.MustFindSpecDir(goroot)
 	genDir := filepath.Join(filepath.Clean(filepath.Join(specDir, "..", "..")), "archsimd", "_gen")
 	return filepath.Join(genDir, "SPEC-TRANSITION.md"), filepath.Join(genDir, "SPEC-TASKS.dot")
 }

 // load parses the plan document.
 func load(md string) *doc {
 	data, err := os.ReadFile(md)
 	if err != nil {
 		log.Fatal(err)
 	}
 	return parse(string(data))
 }

 func main() {
 	log.SetFlags(0)
 	log.SetPrefix("spectasks: ")
 	genOpts := gentools.RegisterFlags(nil)
 	flag.Parse()

 	md, _ := paths(genOpts.GOROOT)
 	d := load(md)

 	// The test is where inconsistency is reported properly; this is only a
 	// guard, so that a graph is never written from a document that disagrees
 	// with itself.
 	if probs := d.problems(); len(probs) > 0 {
 		for _, s := range probs {
 			fmt.Fprintf(os.Stderr, "spectasks: %s\n", s)
 		}
 		log.Fatalf("%s disagrees with itself; go test ./cmd/spectasks reports this properly", filepath.Base(md))
 	}

 	var files gentools.Files
 	defer files.FlushOrExit()

 	buf := files.NewRawFile("simd/archsimd/_gen/SPEC-TASKS.dot")
 	d.dot(buf)
 }

 // A dep is one edge: the id of the task depended on.
 type dep struct {
 	id string
 }

 type task struct {
 	id             string
 	done           bool
 	track          string
 	title          string
 	needs, prefers []dep

 	critical bool // on some longest chain through the graph
 }

 type track struct {
 	letter, name string
 	tasks        []string
 }

 type milestone struct {
 	name  string
 	needs []dep
 }

 type doc struct {
 	tasks      map[string]*task
 	order      []string // task ids, in table order, which must be topological
 	tracks     []track
 	milestones []milestone

 	// part4 is what Part 4's header lines claim, for cross-checking.
 	part4 map[string]struct{ needs, prefers, blocks []dep }
 }

 // --- parsing ---------------------------------------------------------------

 // A markdown table, as a header row and body rows of trimmed cells.
 type mdTable struct {
 	head []string
 	rows [][]string
 }

 // cells splits one "| a | b |" line. Leading and trailing empties from the
 // bounding pipes are dropped.
 func cells(line string) []string {
 	s := strings.TrimSpace(line)
 	if !strings.HasPrefix(s, "|") || !strings.HasSuffix(s, "|") {
 		return nil
 	}
 	parts := strings.Split(s[1:len(s)-1], "|")
 	for i, p := range parts {
 		parts[i] = strings.TrimSpace(p)
 	}
 	return parts
 }

 // findTable returns the first table in lines whose header row equals head.
 // The header must match exactly: this is a format we control, and a silent
 // mismatch would silently drop rows.
 func findTable(lines []string, head ...string) *mdTable {
 	for i, line := range lines {
 		got := cells(line)
 		if !slices.Equal(got, head) {
 			continue
 		}
 		if i+1 >= len(lines) || !strings.HasPrefix(strings.TrimSpace(lines[i+1]), "|-") {
 			log.Fatalf("table %q at line %d has no separator row", head, i+1)
 		}
 		t := &mdTable{head: got}
 		for _, row := range lines[i+2:] {
 			c := cells(row)
 			if c == nil {
 				break
 			}
 			if len(c) != len(head) {
 				log.Fatalf("line %d: got %d cells, want %d", i+1, len(c), len(head))
 			}
 			t.rows = append(t.rows, c)
 		}
 		return t
 	}
 	log.Fatalf("no table with header %q", head)
 	return nil
 }

 var (
 	// A dependency list entry: a task id.
 	depRE = regexp.MustCompile(`^[a-z0-9]+(?:-[a-z0-9]+)*$`)
 	// A Part 4 task heading: "### `spec-common` — Spec the common operations".
 	headingRE = regexp.MustCompile("^### `([a-z0-9]+(?:-[a-z0-9]+)*)` — ")
 	// A Part 4 header field: "**Needs:** 3, 5".
 	fieldRE = regexp.MustCompile(`\*\*(Needs|Prefers|Blocks):\*\* ([^·]*)`)
 	// Markdown emphasis and code spans, for extracting plain text.
 	markupRE = regexp.MustCompile("[`*]")
 )

 // parseDeps parses a dependency cell: "—" for none, else a comma-separated
 // list of dep entries.
 func parseDeps(s string) []dep {
 	s = strings.TrimSpace(markupRE.ReplaceAllString(s, ""))
 	if s == "" || s == "—" || s == "-" {
 		return nil
 	}
 	var out []dep
 	for _, f := range strings.Split(s, ",") {
 		f = strings.TrimSpace(f)
 		if !depRE.MatchString(f) {
 			log.Fatalf("cannot parse dependency %q in %q; want a task id", f, s)
 		}
 		out = append(out, dep{f})
 	}
 	// Sorted so that the three copies of the edge set compare equal
 	// regardless of the order each happens to list them in.
 	slices.SortFunc(out, func(a, b dep) int { return cmp.Compare(a.id, b.id) })
 	return out
 }

 func parse(text string) *doc {
 	lines := strings.Split(text, "\n")
 	d := &doc{
 		tasks: make(map[string]*task),
 		part4: make(map[string]struct{ needs, prefers, blocks []dep }),
 	}

 	for _, r := range findTable(lines, "", "Track", "What it is", "Tasks").rows {
 		var tasks []string
 		for _, dep := range parseDeps(r[3]) {
 			tasks = append(tasks, dep.id)
 		}
 		d.tracks = append(d.tracks, track{
 			letter: markupRE.ReplaceAllString(r[0], ""),
 			name:   r[1],
 			tasks:  tasks,
 		})
 	}

 	for _, r := range findTable(lines, "✓", "T", "Task", "What it is", "Needs", "Prefers").rows {
 		id := markupRE.ReplaceAllString(r[2], "")
 		if !depRE.MatchString(id) {
 			log.Fatalf("bad task id %q; want lowercase words joined by hyphens", r[2])
 		}
 		if d.tasks[id] != nil {
 			log.Fatalf("task %q listed twice", id)
 		}
 		d.tasks[id] = &task{
 			id:      id,
 			done:    strings.Contains(r[0], "x"),
 			track:   r[1],
 			title:   markupRE.ReplaceAllString(r[3], ""),
 			needs:   parseDeps(r[4]),
 			prefers: parseDeps(r[5]),
 		}
 		d.order = append(d.order, id)
 	}

 	for _, r := range findTable(lines, "Milestone", "Reached after", "What it means").rows {
 		d.milestones = append(d.milestones, milestone{
 			name:  markupRE.ReplaceAllString(r[0], ""),
 			needs: parseDeps(r[1]),
 		})
 	}

 	// Part 4 header lines, for cross-checking.
 	cur := ""
 	for _, line := range lines {
 		if m := headingRE.FindStringSubmatch(line); m != nil {
 			cur = m[1]
 			continue
 		}
 		if cur == "" || !strings.HasPrefix(line, "**Done:** [") {
 			continue
 		}
 		var e struct{ needs, prefers, blocks []dep }
 		for _, m := range fieldRE.FindAllStringSubmatch(line, -1) {
 			switch m[1] {
 			case "Needs":
 				e.needs = parseDeps(m[2])
 			case "Prefers":
 				e.prefers = parseDeps(m[2])
 			case "Blocks":
 				e.blocks = parseDeps(m[2])
 			}
 		}
 		d.part4[cur] = e
 		cur = ""
 	}
 	return d
 }

 // --- checking --------------------------------------------------------------

 func ids(ds []dep) []string {
 	out := make([]string, len(ds))
 	for i, d := range ds {
 		out[i] = d.id
 	}
 	return out
 }

 func fmtIDs(xs []string) string {
 	if len(xs) == 0 {
 		return "—"
 	}
 	return strings.Join(xs, ", ")
 }

 // problems returns everything inconsistent about the document, as one message
 // per problem, in a stable order. It reports rather than fails, so that the
 // test can attribute each one and the tool can use it as a guard.
 func (d *doc) problems() []string {
 	var probs []string
 	fail := func(format string, args ...any) {
 		probs = append(probs, fmt.Sprintf(format, args...))
 	}

 	// Every task belongs to exactly one track, and the two lists agree.
 	seen := make(map[string]string)
 	for _, tr := range d.tracks {
 		for _, id := range tr.tasks {
 			if prev, ok := seen[id]; ok {
 				fail("task %s is in tracks %s and %s", id, prev, tr.letter)
 			}
 			seen[id] = tr.letter
 			if t := d.tasks[id]; t == nil {
 				fail("track %s lists task %s, which the dependency table does not have", tr.letter, id)
 			} else if t.track != tr.letter {
 				fail("task %s is in track %s per the track table, %s per the dependency table", id, tr.letter, t.track)
 			}
 		}
 	}

 	// The table is in topological order, so that reading it top to bottom is
 	// a legal order to do the work in. This is what task ids buy: identity no
 	// longer encodes position, so rows can be moved and inserted freely.
 	pos := make(map[string]int, len(d.order))
 	for i, id := range d.order {
 		pos[id] = i
 	}

 	// Edges point at real tasks; Part 4 agrees with the table; Blocks is the
 	// exact reverse of Needs.
 	blocks := make(map[string][]string)
 	for _, id := range d.order {
 		t := d.tasks[id]
 		if seen[id] == "" {
 			fail("task %s is in no track", id)
 		}
 		for _, e := range slices.Concat(t.needs, t.prefers) {
 			if d.tasks[e.id] == nil {
 				fail("task %s depends on task %s, which does not exist", id, e.id)
 			}
 		}
 		for _, e := range t.needs {
 			if d.tasks[e.id] != nil && pos[e.id] > pos[id] {
 				fail("task %s needs %s but comes before it; the table must be in topological order", id, e.id)
 			}
 			blocks[e.id] = append(blocks[e.id], id)
 		}
 		for _, e := range t.prefers {
 			if d.tasks[e.id] != nil && pos[e.id] > pos[id] {
 				fail("task %s prefers %s but comes before it; the table must be in topological order", id, e.id)
 			}
 		}
 		p4, ok := d.part4[id]
 		if !ok {
 			fail("task %s has no Part 4 entry", id)
 			continue
 		}
 		if !slices.Equal(ids(t.needs), ids(p4.needs)) {
 			fail("task %s Needs: table says %s, Part 4 says %s", id, fmtIDs(ids(t.needs)), fmtIDs(ids(p4.needs)))
 		}
 		if !slices.Equal(ids(t.prefers), ids(p4.prefers)) {
 			fail("task %s Prefers: table says %s, Part 4 says %s", id, fmtIDs(ids(t.prefers)), fmtIDs(ids(p4.prefers)))
 		}
 	}
 	for _, id := range d.order {
 		want := blocks[id]
 		slices.Sort(want)
 		if got := ids(d.part4[id].blocks); !slices.Equal(got, want) {
 			fail("task %s Blocks: header says %s, reversing Needs gives %s", id, fmtIDs(got), fmtIDs(want))
 		}
 	}

 	// Unrelated tasks sort by track: if task A (track X) precedes task B
 	// (track Y) and X > Y, then B must transitively depend on A through
 	// Needs or Prefers edges.
 	tdeps := make(map[string]map[string]bool, len(d.order))
 	var computeDeps func(string) map[string]bool
 	computeDeps = func(id string) map[string]bool {
 		if r, ok := tdeps[id]; ok {
 			return r
 		}
 		r := make(map[string]bool)
 		tdeps[id] = r
 		for _, e := range slices.Concat(d.tasks[id].needs, d.tasks[id].prefers) {
 			if d.tasks[e.id] != nil {
 				r[e.id] = true
 				for dep := range computeDeps(e.id) {
 					r[dep] = true
 				}
 			}
 		}
 		return r
 	}
 	for _, id := range d.order {
 		computeDeps(id)
 	}
 	for i, id := range d.order {
 		for _, id2 := range d.order[i+1:] {
 			if d.tasks[id].track > d.tasks[id2].track && !tdeps[id2][id] {
 				fail("task %s (track %s) precedes %s (track %s) but %s does not depend on %s; unrelated tasks sort by track",
 					id, d.tasks[id].track, id2, d.tasks[id2].track, id2, id)
 			}
 		}
 	}

 	for _, m := range d.milestones {
 		for _, e := range m.needs {
 			if d.tasks[e.id] == nil {
 				fail("milestone %q depends on task %s, which does not exist", m.name, e.id)
 			}
 		}
 	}

 	return probs
 }

 // mark sets task.critical on every task that lies on some longest chain of
 // hard dependencies: delaying it delays the whole project. Ties are kept --
 // there is usually more than one longest chain, and picking one of them
 // arbitrarily is how a hand-written "critical path" understates the work.
 func (d *doc) mark() {
 	var into, outOf func(string) int
 	memo := func(f func(string) int) func(string) int {
 		m := make(map[string]int)
 		return func(id string) int {
 			if v, ok := m[id]; ok {
 				return v
 			}
 			m[id] = 1 // cycles fall back to 1 rather than recursing forever
 			v := f(id)
 			m[id] = v
 			return v
 		}
 	}
 	// Longest chain ending at id, counted in tasks.
 	into = memo(func(id string) int {
 		best := 0
 		for _, e := range d.tasks[id].needs {
 			if d.tasks[e.id] != nil {
 				best = max(best, into(e.id))
 			}
 		}
 		return best + 1
 	})
 	// Longest chain starting at id.
 	outOf = memo(func(id string) int {
 		best := 0
 		for _, other := range d.order {
 			for _, e := range d.tasks[other].needs {
 				if e.id == id {
 					best = max(best, outOf(other))
 				}
 			}
 		}
 		return best + 1
 	})

 	span := 0
 	for _, id := range d.order {
 		span = max(span, into(id))
 	}
 	for _, id := range d.order {
 		d.tasks[id].critical = into(id)+outOf(id)-1 == span
 	}
 }

 // reached reports whether every task feeding m is ticked.
 func (d *doc) reached(m milestone) bool {
 	for _, e := range m.needs {
 		if !d.tasks[e.id].done {
 			return false
 		}
 	}
 	return len(m.needs) > 0
 }

 // --- rendering -------------------------------------------------------------

 // Node fills, in track order. Light enough to read black text on.
 var trackFill = []string{
 	"#dce9f7", "#d9f2e2", "#fbe6cd", "#ebdcf7", "#f7dce3", "#d8f0f0", "#e8e8e8",
 }

 // wrap breaks a title into Graphviz label lines of at most width runes,
 // without breaking words.
 func wrap(s string, width int) string {
 	var lines []string
 	line := ""
 	for _, w := range strings.Fields(s) {
 		switch {
 		case line == "":
 			line = w
 		case len([]rune(line))+1+len([]rune(w)) <= width:
 			line += " " + w
 		default:
 			lines = append(lines, line)
 			line = w
 		}
 	}
 	return strings.Join(append(lines, line), `\n`)
 }

 // node is a task id as a Graphviz node name. Ids contain hyphens, which are
 // not legal in a bare Graphviz ID, so they are always quoted.
 func node(id string) string { return quote(id) }

 func quote(s string) string {
 	return `"` + strings.NewReplacer(`"`, `\"`, "\n", `\n`).Replace(s) + `"`
 }

 func (d *doc) dot(w *bytes.Buffer) {
 	d.mark()
 	p := func(format string, args ...any) { fmt.Fprintf(w, format+"\n", args...) }

 	p(`// Task graph for SPEC-TRANSITION.md. Do not edit.`)
 	p(`// Generated by archsimd/_gen/cmd/spectasks; regenerate with:`)
 	p(`//     go run ./cmd/spectasks -w`)
 	p(`// Render with, e.g.:`)
 	p(`//     dot -Tsvg SPEC-TASKS.dot -o SPEC-TASKS.svg`)
 	p(`//`)
 	p(`// The key in the rendered graph explains the notation.`)
 	p(``)
 	p(`digraph spectransition {`)
 	p(`  rankdir=LR;`)
 	p(`  newrank=true;`)
 	p(`  ranksep=0.55; nodesep=0.22;`)
 	p(`  fontname="Helvetica"; fontsize=11;`)
 	p(`  node [shape=box, style="rounded,filled", fillcolor=white,`)
 	p(`        fontname="Helvetica", fontsize=10, margin="0.10,0.06"];`)
 	p(`  edge [color="#666666", arrowsize=0.7];`)
 	p(``)

 	// Tracks are shown as node colour, not as clusters: a cluster has to be
 	// laid out contiguously, which fights the topological ranking and drags
 	// long edges across the whole graph. Colour costs a legend and keeps the
 	// left-to-right reading of dependency order.
 	emit := func(t *task, fill string) {
 		attrs := []string{
 			"label=" + quote(t.id+`\n`+wrap(t.title, 22)),
 			"fillcolor=" + quote(fill),
 			`color="#999999"`,
 		}
 		if t.done {
 			attrs = append(attrs, `fillcolor="#d0d0d0"`, `fontcolor="#777777"`)
 		}
 		p(`  %s [%s];`, node(t.id), strings.Join(attrs, ", "))
 	}
 	// Emitted track by track: declaration order is one of the things dot breaks
 	// ties on, and grouping by track lays out better than topological order
 	// does. Any task no track claims is emitted afterwards rather than dropped,
 	// so a document that problems() would reject still renders.
 	seen := make(map[string]bool, len(d.order))
 	for i, tr := range d.tracks {
 		for _, id := range tr.tasks {
 			if t := d.tasks[id]; t != nil && !seen[id] {
 				seen[id] = true
 				emit(t, trackFill[i%len(trackFill)])
 			}
 		}
 	}
 	for _, id := range d.order {
 		if !seen[id] {
 			emit(d.tasks[id], "white")
 		}
 	}

 	p(``)

 	for _, id := range d.order {
 		t := d.tasks[id]
 		for _, e := range t.needs {
 			var attrs []string
 			if t.critical && d.tasks[e.id].critical {
 				attrs = append(attrs, `color="#c0392b"`, `penwidth=1.8`)
 			}
 			p(`  %s -> %s%s;`, node(e.id), node(id), attrList(attrs))
 		}
 		for _, e := range t.prefers {
 			p(`  %s -> %s [style=dotted, color="#aaaaaa", arrowsize=0.5];`, node(e.id), node(id))
 		}
 	}
 	p(``)

 	for i, m := range d.milestones {
 		fill := "#fff8dc"
 		if d.reached(m) {
 			fill = "#d7d7d7"
 		}
 		p(`  m%d [label=%s, shape=box, style="filled,bold", fillcolor=%s, color="#8a6d3b"];`,
 			i, quote(wrap(m.name, 22)), quote(fill))
 		for _, e := range m.needs {
 			p(`  %s -> m%d [color="#8a6d3b", style=bold, arrowsize=0.7];`, node(e.id), i)
 		}
 	}

 	// The key is a single node with an HTML label rather than a cluster of
 	// nodes: a cluster chained together spans as many ranks as it has entries,
 	// and dot then aligns those ranks with the graph proper, which distorts the
 	// layout it is supposed to annotate.
 	p(``)
 	p(`  key [shape=plaintext, style="", label=<`)
 	p(`    <TABLE BORDER="0" CELLBORDER="0" CELLSPACING="1" CELLPADDING="3" BGCOLOR="#fafafa">`)
 	p(`    <TR><TD ALIGN="LEFT" COLSPAN="2"><B>Tracks</B></TD></TR>`)
 	for i, tr := range d.tracks {
 		p(`    <TR><TD BGCOLOR="%s" WIDTH="18"> </TD><TD ALIGN="LEFT">%s</TD></TR>`,
 			trackFill[i%len(trackFill)], html(tr.letter+" — "+tr.name))
 	}
 	p(`    <TR><TD COLSPAN="2"><FONT POINT-SIZE="5"> </FONT></TD></TR>`)
 	p(`    <TR><TD ALIGN="LEFT" COLSPAN="2"><B>Reading the graph</B></TD></TR>`)
 	// Each row shows the thing it names, rather than describing it: an arrow in
 	// the edge's own colour, a swatch in the node's own fill.
 	arrow := func(color, glyph string) string {
 		return fmt.Sprintf(`<FONT COLOR="%s" POINT-SIZE="14">%s</FONT>`, color, glyph)
 	}
 	swatch := func(fill, border string) string {
 		return fmt.Sprintf(`<TABLE BORDER="1" CELLBORDER="0" CELLSPACING="0" CELLPADDING="0" `+
 			`COLOR="%s" BGCOLOR="%s"><TR><TD WIDTH="16" HEIGHT="9"> </TD></TR></TABLE>`, border, fill)
 	}
 	for _, row := range [][2]string{
 		{arrow("#666666", "&#8594;"), "must be done first"},
 		{arrow("#aaaaaa", "&#8674;"), "better done first, but not required"},
 		{arrow("#c0392b", "&#8594;"), "on a longest chain: slipping it slips the project"},
 		{swatch("#fff8dc", "#8a6d3b"), "milestone: reached, not worked on"},
 		{swatch("#d0d0d0", "#999999"), "done"},
 	} {
 		p(`    <TR><TD ALIGN="RIGHT">%s</TD><TD ALIGN="LEFT">%s</TD></TR>`, row[0], html(row[1]))
 	}
 	p(`    </TABLE>`)
 	p(`  >];`)
 	p(`}`)
 }

 // html escapes text for a Graphviz HTML-like label.
 func html(s string) string {
 	return strings.NewReplacer("&", "&amp;", "<", "&lt;", ">", "&gt;").Replace(s)
 }

 func attrList(attrs []string) string {
 	if len(attrs) == 0 {
 		return ""
 	}
 	return " [" + strings.Join(attrs, ", ") + "]"
 }
	// Copyright 2026 The Go Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style
	// license that can be found in the LICENSE file.

	// Spectasks renders SPEC-TRANSITION.md's task dependencies as a Graphviz
	// graph, and checks the document's copies of those dependencies against each
	// other.
	//
	// go run ./cmd/spectasks -w # write SPEC-TASKS.dot
	// go run ./cmd/spectasks # check only; write the graph to stdout
	//
	// SPEC-TRANSITION.md states its dependencies three times: once in Part 2's
	// table, which this tool treats as the source of truth; once per task in
	// Part 3's "Needs:"/"Prefers:" header lines; and a third time, reversed, in
	// Part 3's "Blocks:" lines. go test ./cmd/spectasks fails if they disagree, and
	// also fails if SPEC-TASKS.dot has not been regenerated since. Adding the graph
	// as a fourth hand-maintained copy would have made that worse, so the graph is
	// generated.
	//
	// Two things the graph shows that the table cannot. The critical path is
	// computed, not asserted: a task is on it when delaying it delays the whole
	// project, which is the set of tasks whose longest-chain-in plus
	// longest-chain-out spans the graph. And milestones -- the points worth
	// announcing -- are drawn as nodes, so it is visible which tasks feed them.
	// Milestone state is derived from the task checkboxes and is never written
	// down separately.
	package main

	import (
	"bytes"
	"cmp"
	"flag"
	"fmt"
	"log"
	"os"
	"path/filepath"
	"regexp"
	"slices"
	"strings"

	"simd/archsimd/_gen/gentools"
	"simd/archsimd/_gen/specgen"
	)

	// paths returns the plan document and the graph generated from it.
	func paths(goroot string) (md, dot string) {
	specDir := specgen.MustFindSpecDir(goroot)
	genDir := filepath.Join(filepath.Clean(filepath.Join(specDir, "..", "..")), "archsimd", "_gen")
	return filepath.Join(genDir, "SPEC-TRANSITION.md"), filepath.Join(genDir, "SPEC-TASKS.dot")
	}

	// load parses the plan document.
	func load(md string) *doc {
	data, err := os.ReadFile(md)
	if err != nil {
	log.Fatal(err)
	}
	return parse(string(data))
	}

	func main() {
	log.SetFlags(0)
	log.SetPrefix("spectasks: ")
	genOpts := gentools.RegisterFlags(nil)
	flag.Parse()

	md, _ := paths(genOpts.GOROOT)
	d := load(md)

	// The test is where inconsistency is reported properly; this is only a
	// guard, so that a graph is never written from a document that disagrees
	// with itself.
	if probs := d.problems(); len(probs) > 0 {
	for _, s := range probs {
	fmt.Fprintf(os.Stderr, "spectasks: %s\n", s)
	}
	log.Fatalf("%s disagrees with itself; go test ./cmd/spectasks reports this properly", filepath.Base(md))
	}

	var files gentools.Files
	defer files.FlushOrExit()

	buf := files.NewRawFile("simd/archsimd/_gen/SPEC-TASKS.dot")
	d.dot(buf)
	}

	// A dep is one edge: the id of the task depended on.
	type dep struct {
	id string
	}

	type task struct {
	id string
	done bool
	track string
	title string
	needs, prefers []dep

	critical bool // on some longest chain through the graph
	}

	type track struct {
	letter, name string
	tasks []string
	}

	type milestone struct {
	name string
	needs []dep
	}

	type doc struct {
	tasks map[string]*task
	order []string // task ids, in table order, which must be topological
	tracks []track
	milestones []milestone

	// part4 is what Part 4's header lines claim, for cross-checking.
	part4 map[string]struct{ needs, prefers, blocks []dep }
	}

	// --- parsing ---------------------------------------------------------------

	// A markdown table, as a header row and body rows of trimmed cells.
	type mdTable struct {
	head []string
	rows [][]string
	}

	// cells splits one "\| a \| b \|" line. Leading and trailing empties from the
	// bounding pipes are dropped.
	func cells(line string) []string {
	s := strings.TrimSpace(line)
	if !strings.HasPrefix(s, "\|") \|\| !strings.HasSuffix(s, "\|") {
	return nil
	}
	parts := strings.Split(s[1:len(s)-1], "\|")
	for i, p := range parts {
	parts[i] = strings.TrimSpace(p)
	}
	return parts
	}

	// findTable returns the first table in lines whose header row equals head.
	// The header must match exactly: this is a format we control, and a silent
	// mismatch would silently drop rows.
	func findTable(lines []string, head ...string) *mdTable {
	for i, line := range lines {
	got := cells(line)
	if !slices.Equal(got, head) {
	continue
	}
	if i+1 >= len(lines) \|\| !strings.HasPrefix(strings.TrimSpace(lines[i+1]), "\|-") {
	log.Fatalf("table %q at line %d has no separator row", head, i+1)
	}
	t := &mdTable{head: got}
	for _, row := range lines[i+2:] {
	c := cells(row)
	if c == nil {
	break
	}
	if len(c) != len(head) {
	log.Fatalf("line %d: got %d cells, want %d", i+1, len(c), len(head))
	}
	t.rows = append(t.rows, c)
	}
	return t
	}
	log.Fatalf("no table with header %q", head)
	return nil
	}

	var (
	// A dependency list entry: a task id.
	depRE = regexp.MustCompile(`^[a-z0-9]+(?:-[a-z0-9]+)*$`)
	// A Part 4 task heading: "### `spec-common` — Spec the common operations".
	headingRE = regexp.MustCompile("^### `([a-z0-9]+(?:-[a-z0-9]+)*)` — ")
	// A Part 4 header field: "Needs: 3, 5".
	fieldRE = regexp.MustCompile(`\\(Needs\|Prefers\|Blocks):\\ ([^·]*)`)
	// Markdown emphasis and code spans, for extracting plain text.
	markupRE = regexp.MustCompile("[`*]")
	)

	// parseDeps parses a dependency cell: "—" for none, else a comma-separated
	// list of dep entries.
	func parseDeps(s string) []dep {
	s = strings.TrimSpace(markupRE.ReplaceAllString(s, ""))
	if s == "" \|\| s == "—" \|\| s == "-" {
	return nil
	}
	var out []dep
	for _, f := range strings.Split(s, ",") {
	f = strings.TrimSpace(f)
	if !depRE.MatchString(f) {
	log.Fatalf("cannot parse dependency %q in %q; want a task id", f, s)
	}
	out = append(out, dep{f})
	}
	// Sorted so that the three copies of the edge set compare equal
	// regardless of the order each happens to list them in.
	slices.SortFunc(out, func(a, b dep) int { return cmp.Compare(a.id, b.id) })
	return out
	}

	func parse(text string) *doc {
	lines := strings.Split(text, "\n")
	d := &doc{
	tasks: make(map[string]*task),
	part4: make(map[string]struct{ needs, prefers, blocks []dep }),
	}

	for _, r := range findTable(lines, "", "Track", "What it is", "Tasks").rows {
	var tasks []string
	for _, dep := range parseDeps(r[3]) {
	tasks = append(tasks, dep.id)
	}
	d.tracks = append(d.tracks, track{
	letter: markupRE.ReplaceAllString(r[0], ""),
	name: r[1],
	tasks: tasks,
	})
	}

	for _, r := range findTable(lines, "✓", "T", "Task", "What it is", "Needs", "Prefers").rows {
	id := markupRE.ReplaceAllString(r[2], "")
	if !depRE.MatchString(id) {
	log.Fatalf("bad task id %q; want lowercase words joined by hyphens", r[2])
	}
	if d.tasks[id] != nil {
	log.Fatalf("task %q listed twice", id)
	}
	d.tasks[id] = &task{
	id: id,
	done: strings.Contains(r[0], "x"),
	track: r[1],
	title: markupRE.ReplaceAllString(r[3], ""),
	needs: parseDeps(r[4]),
	prefers: parseDeps(r[5]),
	}
	d.order = append(d.order, id)
	}

	for _, r := range findTable(lines, "Milestone", "Reached after", "What it means").rows {
	d.milestones = append(d.milestones, milestone{
	name: markupRE.ReplaceAllString(r[0], ""),
	needs: parseDeps(r[1]),
	})
	}

	// Part 4 header lines, for cross-checking.
	cur := ""
	for _, line := range lines {
	if m := headingRE.FindStringSubmatch(line); m != nil {
	cur = m[1]
	continue
	}
	if cur == "" \|\| !strings.HasPrefix(line, "Done: [") {
	continue
	}
	var e struct{ needs, prefers, blocks []dep }
	for _, m := range fieldRE.FindAllStringSubmatch(line, -1) {
	switch m[1] {
	case "Needs":
	e.needs = parseDeps(m[2])
	case "Prefers":
	e.prefers = parseDeps(m[2])
	case "Blocks":
	e.blocks = parseDeps(m[2])
	}
	}
	d.part4[cur] = e
	cur = ""
	}
	return d
	}

	// --- checking --------------------------------------------------------------

	func ids(ds []dep) []string {
	out := make([]string, len(ds))
	for i, d := range ds {
	out[i] = d.id
	}
	return out
	}

	func fmtIDs(xs []string) string {
	if len(xs) == 0 {
	return "—"
	}
	return strings.Join(xs, ", ")
	}

	// problems returns everything inconsistent about the document, as one message
	// per problem, in a stable order. It reports rather than fails, so that the
	// test can attribute each one and the tool can use it as a guard.
	func (d *doc) problems() []string {
	var probs []string
	fail := func(format string, args ...any) {
	probs = append(probs, fmt.Sprintf(format, args...))
	}

	// Every task belongs to exactly one track, and the two lists agree.
	seen := make(map[string]string)
	for _, tr := range d.tracks {
	for _, id := range tr.tasks {
	if prev, ok := seen[id]; ok {
	fail("task %s is in tracks %s and %s", id, prev, tr.letter)
	}
	seen[id] = tr.letter
	if t := d.tasks[id]; t == nil {
	fail("track %s lists task %s, which the dependency table does not have", tr.letter, id)
	} else if t.track != tr.letter {
	fail("task %s is in track %s per the track table, %s per the dependency table", id, tr.letter, t.track)
	}
	}
	}

	// The table is in topological order, so that reading it top to bottom is
	// a legal order to do the work in. This is what task ids buy: identity no
	// longer encodes position, so rows can be moved and inserted freely.
	pos := make(map[string]int, len(d.order))
	for i, id := range d.order {
	pos[id] = i
	}

	// Edges point at real tasks; Part 4 agrees with the table; Blocks is the
	// exact reverse of Needs.
	blocks := make(map[string][]string)
	for _, id := range d.order {
	t := d.tasks[id]
	if seen[id] == "" {
	fail("task %s is in no track", id)
	}
	for _, e := range slices.Concat(t.needs, t.prefers) {
	if d.tasks[e.id] == nil {
	fail("task %s depends on task %s, which does not exist", id, e.id)
	}
	}
	for _, e := range t.needs {
	if d.tasks[e.id] != nil && pos[e.id] > pos[id] {
	fail("task %s needs %s but comes before it; the table must be in topological order", id, e.id)
	}
	blocks[e.id] = append(blocks[e.id], id)
	}
	for _, e := range t.prefers {
	if d.tasks[e.id] != nil && pos[e.id] > pos[id] {
	fail("task %s prefers %s but comes before it; the table must be in topological order", id, e.id)
	}
	}
	p4, ok := d.part4[id]
	if !ok {
	fail("task %s has no Part 4 entry", id)
	continue
	}
	if !slices.Equal(ids(t.needs), ids(p4.needs)) {
	fail("task %s Needs: table says %s, Part 4 says %s", id, fmtIDs(ids(t.needs)), fmtIDs(ids(p4.needs)))
	}
	if !slices.Equal(ids(t.prefers), ids(p4.prefers)) {
	fail("task %s Prefers: table says %s, Part 4 says %s", id, fmtIDs(ids(t.prefers)), fmtIDs(ids(p4.prefers)))
	}
	}
	for _, id := range d.order {
	want := blocks[id]
	slices.Sort(want)
	if got := ids(d.part4[id].blocks); !slices.Equal(got, want) {
	fail("task %s Blocks: header says %s, reversing Needs gives %s", id, fmtIDs(got), fmtIDs(want))
	}
	}

	// Unrelated tasks sort by track: if task A (track X) precedes task B
	// (track Y) and X > Y, then B must transitively depend on A through
	// Needs or Prefers edges.
	tdeps := make(map[string]map[string]bool, len(d.order))
	var computeDeps func(string) map[string]bool
	computeDeps = func(id string) map[string]bool {
	if r, ok := tdeps[id]; ok {
	return r
	}
	r := make(map[string]bool)
	tdeps[id] = r
	for _, e := range slices.Concat(d.tasks[id].needs, d.tasks[id].prefers) {
	if d.tasks[e.id] != nil {
	r[e.id] = true
	for dep := range computeDeps(e.id) {
	r[dep] = true
	}
	}
	}
	return r
	}
	for _, id := range d.order {
	computeDeps(id)
	}
	for i, id := range d.order {
	for _, id2 := range d.order[i+1:] {
	if d.tasks[id].track > d.tasks[id2].track && !tdeps[id2][id] {
	fail("task %s (track %s) precedes %s (track %s) but %s does not depend on %s; unrelated tasks sort by track",
	id, d.tasks[id].track, id2, d.tasks[id2].track, id2, id)
	}
	}
	}

	for _, m := range d.milestones {
	for _, e := range m.needs {
	if d.tasks[e.id] == nil {
	fail("milestone %q depends on task %s, which does not exist", m.name, e.id)
	}
	}
	}

	return probs
	}

	// mark sets task.critical on every task that lies on some longest chain of
	// hard dependencies: delaying it delays the whole project. Ties are kept --
	// there is usually more than one longest chain, and picking one of them
	// arbitrarily is how a hand-written "critical path" understates the work.
	func (d *doc) mark() {
	var into, outOf func(string) int
	memo := func(f func(string) int) func(string) int {
	m := make(map[string]int)
	return func(id string) int {
	if v, ok := m[id]; ok {
	return v
	}
	m[id] = 1 // cycles fall back to 1 rather than recursing forever
	v := f(id)
	m[id] = v
	return v
	}
	}
	// Longest chain ending at id, counted in tasks.
	into = memo(func(id string) int {
	best := 0
	for _, e := range d.tasks[id].needs {
	if d.tasks[e.id] != nil {
	best = max(best, into(e.id))
	}
	}
	return best + 1
	})
	// Longest chain starting at id.
	outOf = memo(func(id string) int {
	best := 0
	for _, other := range d.order {
	for _, e := range d.tasks[other].needs {
	if e.id == id {
	best = max(best, outOf(other))
	}
	}
	}
	return best + 1
	})

	span := 0
	for _, id := range d.order {
	span = max(span, into(id))
	}
	for _, id := range d.order {
	d.tasks[id].critical = into(id)+outOf(id)-1 == span
	}
	}

	// reached reports whether every task feeding m is ticked.
	func (d *doc) reached(m milestone) bool {
	for _, e := range m.needs {
	if !d.tasks[e.id].done {
	return false
	}
	}
	return len(m.needs) > 0
	}

	// --- rendering -------------------------------------------------------------

	// Node fills, in track order. Light enough to read black text on.
	var trackFill = []string{
	"#dce9f7", "#d9f2e2", "#fbe6cd", "#ebdcf7", "#f7dce3", "#d8f0f0", "#e8e8e8",
	}

	// wrap breaks a title into Graphviz label lines of at most width runes,
	// without breaking words.
	func wrap(s string, width int) string {
	var lines []string
	line := ""
	for _, w := range strings.Fields(s) {
	switch {
	case line == "":
	line = w
	case len([]rune(line))+1+len([]rune(w)) <= width:
	line += " " + w
	default:
	lines = append(lines, line)
	line = w
	}
	}
	return strings.Join(append(lines, line), `\n`)
	}

	// node is a task id as a Graphviz node name. Ids contain hyphens, which are
	// not legal in a bare Graphviz ID, so they are always quoted.
	func node(id string) string { return quote(id) }

	func quote(s string) string {
	return `"` + strings.NewReplacer(`"`, `\"`, "\n", `\n`).Replace(s) + `"`
	}

	func (d doc) dot(w bytes.Buffer) {
	d.mark()
	p := func(format string, args ...any) { fmt.Fprintf(w, format+"\n", args...) }

	p(`// Task graph for SPEC-TRANSITION.md. Do not edit.`)
	p(`// Generated by archsimd/_gen/cmd/spectasks; regenerate with:`)
	p(`// go run ./cmd/spectasks -w`)
	p(`// Render with, e.g.:`)
	p(`// dot -Tsvg SPEC-TASKS.dot -o SPEC-TASKS.svg`)
	p(`//`)
	p(`// The key in the rendered graph explains the notation.`)
	p(``)
	p(`digraph spectransition {`)
	p(` rankdir=LR;`)
	p(` newrank=true;`)
	p(` ranksep=0.55; nodesep=0.22;`)
	p(` fontname="Helvetica"; fontsize=11;`)
	p(` node [shape=box, style="rounded,filled", fillcolor=white,`)
	p(` fontname="Helvetica", fontsize=10, margin="0.10,0.06"];`)
	p(` edge [color="#666666", arrowsize=0.7];`)
	p(``)

	// Tracks are shown as node colour, not as clusters: a cluster has to be
	// laid out contiguously, which fights the topological ranking and drags
	// long edges across the whole graph. Colour costs a legend and keeps the
	// left-to-right reading of dependency order.
	emit := func(t *task, fill string) {
	attrs := []string{
	"label=" + quote(t.id+`\n`+wrap(t.title, 22)),
	"fillcolor=" + quote(fill),
	`color="#999999"`,
	}
	if t.done {
	attrs = append(attrs, `fillcolor="#d0d0d0"`, `fontcolor="#777777"`)
	}
	p(` %s [%s];`, node(t.id), strings.Join(attrs, ", "))
	}
	// Emitted track by track: declaration order is one of the things dot breaks
	// ties on, and grouping by track lays out better than topological order
	// does. Any task no track claims is emitted afterwards rather than dropped,
	// so a document that problems() would reject still renders.
	seen := make(map[string]bool, len(d.order))
	for i, tr := range d.tracks {
	for _, id := range tr.tasks {
	if t := d.tasks[id]; t != nil && !seen[id] {
	seen[id] = true
	emit(t, trackFill[i%len(trackFill)])
	}
	}
	}
	for _, id := range d.order {
	if !seen[id] {
	emit(d.tasks[id], "white")
	}
	}

	p(``)

	for _, id := range d.order {
	t := d.tasks[id]
	for _, e := range t.needs {
	var attrs []string
	if t.critical && d.tasks[e.id].critical {
	attrs = append(attrs, `color="#c0392b"`, `penwidth=1.8`)
	}
	p(` %s -> %s%s;`, node(e.id), node(id), attrList(attrs))
	}
	for _, e := range t.prefers {
	p(` %s -> %s [style=dotted, color="#aaaaaa", arrowsize=0.5];`, node(e.id), node(id))
	}
	}
	p(``)

	for i, m := range d.milestones {
	fill := "#fff8dc"
	if d.reached(m) {
	fill = "#d7d7d7"
	}
	p(` m%d [label=%s, shape=box, style="filled,bold", fillcolor=%s, color="#8a6d3b"];`,
	i, quote(wrap(m.name, 22)), quote(fill))
	for _, e := range m.needs {
	p(` %s -> m%d [color="#8a6d3b", style=bold, arrowsize=0.7];`, node(e.id), i)
	}
	}

	// The key is a single node with an HTML label rather than a cluster of
	// nodes: a cluster chained together spans as many ranks as it has entries,
	// and dot then aligns those ranks with the graph proper, which distorts the
	// layout it is supposed to annotate.
	p(``)
	p(` key [shape=plaintext, style="", label=<`)
	p(` <TABLE BORDER="0" CELLBORDER="0" CELLSPACING="1" CELLPADDING="3" BGCOLOR="#fafafa">`)
	p(` <TR><TD ALIGN="LEFT" COLSPAN="2"><B>Tracks</B></TD></TR>`)
	for i, tr := range d.tracks {
	p(` <TR><TD BGCOLOR="%s" WIDTH="18"> </TD><TD ALIGN="LEFT">%s</TD></TR>`,
	trackFill[i%len(trackFill)], html(tr.letter+" — "+tr.name))
	}
	p(` <TR><TD COLSPAN="2"><FONT POINT-SIZE="5"> </FONT></TD></TR>`)
	p(` <TR><TD ALIGN="LEFT" COLSPAN="2"><B>Reading the graph</B></TD></TR>`)
	// Each row shows the thing it names, rather than describing it: an arrow in
	// the edge's own colour, a swatch in the node's own fill.
	arrow := func(color, glyph string) string {
	return fmt.Sprintf(`<FONT COLOR="%s" POINT-SIZE="14">%s</FONT>`, color, glyph)
	}
	swatch := func(fill, border string) string {
	return fmt.Sprintf(`<TABLE BORDER="1" CELLBORDER="0" CELLSPACING="0" CELLPADDING="0" `+
	`COLOR="%s" BGCOLOR="%s"><TR><TD WIDTH="16" HEIGHT="9"> </TD></TR></TABLE>`, border, fill)
	}
	for _, row := range [][2]string{
	{arrow("#666666", "→"), "must be done first"},
	{arrow("#aaaaaa", "⇢"), "better done first, but not required"},
	{arrow("#c0392b", "→"), "on a longest chain: slipping it slips the project"},
	{swatch("#fff8dc", "#8a6d3b"), "milestone: reached, not worked on"},
	{swatch("#d0d0d0", "#999999"), "done"},
	} {
	p(` <TR><TD ALIGN="RIGHT">%s</TD><TD ALIGN="LEFT">%s</TD></TR>`, row[0], html(row[1]))
	}
	p(` </TABLE>`)
	p(` >];`)
	p(`}`)
	}

	// html escapes text for a Graphviz HTML-like label.
	func html(s string) string {
	return strings.NewReplacer("&", "&", "<", "<", ">", ">").Replace(s)
	}

	func attrList(attrs []string) string {
	if len(attrs) == 0 {
	return ""
	}
	return " [" + strings.Join(attrs, ", ") + "]"
	}