4 files changed, 484 insertions, 0 deletions
diff --git a/src/internal/dag/alg.go b/src/internal/dag/alg.go
new file mode 100644
index 0000000000..88002797c0
--- /dev/null
+++ b/src/internal/dag/alg.go
@@ -0,0 +1,63 @@
+// Copyright 2022 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.
+
+package dag
+
+// Transpose reverses all edges in g.
+func (g *Graph) Transpose() {
+	old := g.edges
+
+	g.edges = make(map[string]map[string]bool)
+	for _, n := range g.Nodes {
+		g.edges[n] = make(map[string]bool)
+	}
+
+	for from, tos := range old {
+		for to := range tos {
+			g.edges[to][from] = true
+		}
+	}
+}
+
+// Topo returns a topological sort of g. This function is deterministic.
+func (g *Graph) Topo() []string {
+	topo := make([]string, 0, len(g.Nodes))
+	marks := make(map[string]bool)
+
+	var visit func(n string)
+	visit = func(n string) {
+		if marks[n] {
+			return
+		}
+		for _, to := range g.Edges(n) {
+			visit(to)
+		}
+		marks[n] = true
+		topo = append(topo, n)
+	}
+	for _, root := range g.Nodes {
+		visit(root)
+	}
+	for i, j := 0, len(topo)-1; i < j; i, j = i+1, j-1 {
+		topo[i], topo[j] = topo[j], topo[i]
+	}
+	return topo
+}
+
+// TransitiveReduction removes edges from g that are transitively
+// reachable. g must be transitively closed.
+func (g *Graph) TransitiveReduction() {
+	// For i -> j -> k, if i -> k exists, delete it.
+	for _, i := range g.Nodes {
+		for _, j := range g.Nodes {
+			if g.HasEdge(i, j) {
+				for _, k := range g.Nodes {
+					if g.HasEdge(j, k) {
+						g.DelEdge(i, k)
+					}
+				}
+			}
+		}
+	}
+}
diff --git a/src/internal/dag/alg_test.go b/src/internal/dag/alg_test.go
new file mode 100644
index 0000000000..e5ea8b6ab6
--- /dev/null
+++ b/src/internal/dag/alg_test.go
@@ -0,0 +1,46 @@
+// Copyright 2022 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.
+
+package dag
+
+import (
+	"reflect"
+	"strings"
+	"testing"
+)
+
+func TestTranspose(t *testing.T) {
+	g := mustParse(t, diamond)
+	g.Transpose()
+	wantEdges(t, g, "a->b a->c a->d b->d c->d")
+}
+
+func TestTopo(t *testing.T) {
+	g := mustParse(t, diamond)
+	got := g.Topo()
+	// "d" is the root, so it's first.
+	//
+	// "c" and "b" could be in either order, but Topo is
+	// deterministic in reverse node definition order.
+	//
+	// "a" is a leaf.
+	wantNodes := strings.Fields("d c b a")
+	if !reflect.DeepEqual(wantNodes, got) {
+		t.Fatalf("want topo sort %v, got %v", wantNodes, got)
+	}
+}
+
+func TestTransitiveReduction(t *testing.T) {
+	t.Run("diamond", func(t *testing.T) {
+		g := mustParse(t, diamond)
+		g.TransitiveReduction()
+		wantEdges(t, g, "b->a c->a d->b d->c")
+	})
+	t.Run("chain", func(t *testing.T) {
+		const chain = `NONE < a < b < c < d; a, d < e;`
+		g := mustParse(t, chain)
+		g.TransitiveReduction()
+		wantEdges(t, g, "e->d d->c c->b b->a")
+	})
+}
diff --git a/src/internal/dag/parse.go b/src/internal/dag/parse.go
new file mode 100644
index 0000000000..9d5b918b11
--- /dev/null
+++ b/src/internal/dag/parse.go
@@ -0,0 +1,314 @@
+// Copyright 2022 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.
+
+// Package dag implements a language for expressing directed acyclic
+// graphs.
+//
+// The general syntax of a rule is:
+//
+//	a, b < c, d;
+//
+// which means c and d come after a and b in the partial order
+// (that is, there are edges from c and d to a and b),
+// but doesn't provide a relative order between a vs b or c vs d.
+//
+// The rules can chain together, as in:
+//
+//	e < f, g < h;
+//
+// which is equivalent to
+//
+//	e < f, g;
+//	f, g < h;
+//
+// Except for the special bottom element "NONE", each name
+// must appear exactly once on the right-hand side of any rule.
+// That rule serves as the definition of the allowed successor
+// for that name. The definition must appear before any uses
+// of the name on the left-hand side of a rule. (That is, the
+// rules themselves must be ordered according to the partial
+// order, for easier reading by people.)
+//
+// Negative assertions double-check the partial order:
+//
+//	i !< j
+//
+// means that it must NOT be the case that i < j.
+// Negative assertions may appear anywhere in the rules,
+// even before i and j have been defined.
+//
+// Comments begin with #.
+package dag
+
+import (
+	"fmt"
+	"sort"
+	"strings"
+)
+
+type Graph struct {
+	Nodes   []string
+	byLabel map[string]int
+	edges   map[string]map[string]bool
+}
+
+func newGraph() *Graph {
+	return &Graph{byLabel: map[string]int{}, edges: map[string]map[string]bool{}}
+}
+
+func (g *Graph) addNode(label string) bool {
+	if _, ok := g.byLabel[label]; ok {
+		return false
+	}
+	g.byLabel[label] = len(g.Nodes)
+	g.Nodes = append(g.Nodes, label)
+	g.edges[label] = map[string]bool{}
+	return true
+}
+
+func (g *Graph) AddEdge(from, to string) {
+	g.edges[from][to] = true
+}
+
+func (g *Graph) DelEdge(from, to string) {
+	delete(g.edges[from], to)
+}
+
+func (g *Graph) HasEdge(from, to string) bool {
+	return g.edges[from] != nil && g.edges[from][to]
+}
+
+func (g *Graph) Edges(from string) []string {
+	edges := make([]string, 0, 16)
+	for k := range g.edges[from] {
+		edges = append(edges, k)
+	}
+	sort.Slice(edges, func(i, j int) bool { return g.byLabel[edges[i]] < g.byLabel[edges[j]] })
+	return edges
+}
+
+// Parse parses the DAG language and returns the transitive closure of
+// the described graph. In the returned graph, there is an edge from "b"
+// to "a" if b < a (or a > b) in the partial order.
+func Parse(dag string) (*Graph, error) {
+	g := newGraph()
+	disallowed := []rule{}
+
+	rules, err := parseRules(dag)
+	if err != nil {
+		return nil, err
+	}
+
+	// TODO: Add line numbers to errors.
+	var errors []string
+	errorf := func(format string, a ...any) {
+		errors = append(errors, fmt.Sprintf(format, a...))
+	}
+	for _, r := range rules {
+		if r.op == "!<" {
+			disallowed = append(disallowed, r)
+			continue
+		}
+		for _, def := range r.def {
+			if def == "NONE" {
+				errorf("NONE cannot be a predecessor")
+				continue
+			}
+			if !g.addNode(def) {
+				errorf("multiple definitions for %s", def)
+			}
+			for _, less := range r.less {
+				if less == "NONE" {
+					continue
+				}
+				if _, ok := g.byLabel[less]; !ok {
+					errorf("use of %s before its definition", less)
+				} else {
+					g.AddEdge(def, less)
+				}
+			}
+		}
+	}
+
+	// Check for missing definition.
+	for _, tos := range g.edges {
+		for to := range tos {
+			if g.edges[to] == nil {
+				errorf("missing definition for %s", to)
+			}
+		}
+	}
+
+	// Complete transitive closure.
+	for _, k := range g.Nodes {
+		for _, i := range g.Nodes {
+			for _, j := range g.Nodes {
+				if i != k && k != j && g.HasEdge(i, k) && g.HasEdge(k, j) {
+					if i == j {
+						// Can only happen along with a "use of X before deps" error above,
+						// but this error is more specific - it makes clear that reordering the
+						// rules will not be enough to fix the problem.
+						errorf("graph cycle: %s < %s < %s", j, k, i)
+					}
+					g.AddEdge(i, j)
+				}
+			}
+		}
+	}
+
+	// Check negative assertions against completed allowed graph.
+	for _, bad := range disallowed {
+		for _, less := range bad.less {
+			for _, def := range bad.def {
+				if g.HasEdge(def, less) {
+					errorf("graph edge assertion failed: %s !< %s", less, def)
+				}
+			}
+		}
+	}
+
+	if len(errors) > 0 {
+		return nil, fmt.Errorf("%s", strings.Join(errors, "\n"))
+	}
+
+	return g, nil
+}
+
+// A rule is a line in the DAG language where "less < def" or "less !< def".
+type rule struct {
+	less []string
+	op   string // Either "<" or "!<"
+	def  []string
+}
+
+type syntaxError string
+
+func (e syntaxError) Error() string {
+	return string(e)
+}
+
+// parseRules parses the rules of a DAG.
+func parseRules(rules string) (out []rule, err error) {
+	defer func() {
+		e := recover()
+		switch e := e.(type) {
+		case nil:
+			return
+		case syntaxError:
+			err = e
+		default:
+			panic(e)
+		}
+	}()
+	p := &rulesParser{lineno: 1, text: rules}
+
+	var prev []string
+	var op string
+	for {
+		list, tok := p.nextList()
+		if tok == "" {
+			if prev == nil {
+				break
+			}
+			p.syntaxError("unexpected EOF")
+		}
+		if prev != nil {
+			out = append(out, rule{prev, op, list})
+		}
+		prev = list
+		if tok == ";" {
+			prev = nil
+			op = ""
+			continue
+		}
+		if tok != "<" && tok != "!<" {
+			p.syntaxError("missing <")
+		}
+		op = tok
+	}
+
+	return out, err
+}
+
+// A rulesParser parses the depsRules syntax described above.
+type rulesParser struct {
+	lineno   int
+	lastWord string
+	text     string
+}
+
+// syntaxError reports a parsing error.
+func (p *rulesParser) syntaxError(msg string) {
+	panic(syntaxError(fmt.Sprintf("parsing graph: line %d: syntax error: %s near %s", p.lineno, msg, p.lastWord)))
+}
+
+// nextList parses and returns a comma-separated list of names.
+func (p *rulesParser) nextList() (list []string, token string) {
+	for {
+		tok := p.nextToken()
+		switch tok {
+		case "":
+			if len(list) == 0 {
+				return nil, ""
+			}
+			fallthrough
+		case ",", "<", "!<", ";":
+			p.syntaxError("bad list syntax")
+		}
+		list = append(list, tok)
+
+		tok = p.nextToken()
+		if tok != "," {
+			return list, tok
+		}
+	}
+}
+
+// nextToken returns the next token in the deps rules,
+// one of ";" "," "<" "!<" or a name.
+func (p *rulesParser) nextToken() string {
+	for {
+		if p.text == "" {
+			return ""
+		}
+		switch p.text[0] {
+		case ';', ',', '<':
+			t := p.text[:1]
+			p.text = p.text[1:]
+			return t
+
+		case '!':
+			if len(p.text) < 2 || p.text[1] != '<' {
+				p.syntaxError("unexpected token !")
+			}
+			p.text = p.text[2:]
+			return "!<"
+
+		case '#':
+			i := strings.Index(p.text, "\n")
+			if i < 0 {
+				i = len(p.text)
+			}
+			p.text = p.text[i:]
+			continue
+
+		case '\n':
+			p.lineno++
+			fallthrough
+		case ' ', '\t':
+			p.text = p.text[1:]
+			continue
+
+		default:
+			i := strings.IndexAny(p.text, "!;,<#\n \t")
+			if i < 0 {
+				i = len(p.text)
+			}
+			t := p.text[:i]
+			p.text = p.text[i:]
+			p.lastWord = t
+			return t
+		}
+	}
+}
diff --git a/src/internal/dag/parse_test.go b/src/internal/dag/parse_test.go
new file mode 100644
index 0000000000..b2520c3659
--- /dev/null
+++ b/src/internal/dag/parse_test.go
@@ -0,0 +1,61 @@
+// Copyright 2022 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.
+
+package dag
+
+import (
+	"reflect"
+	"strings"
+	"testing"
+)
+
+const diamond = `
+NONE < a < b, c < d;
+`
+
+func mustParse(t *testing.T, dag string) *Graph {
+	t.Helper()
+	g, err := Parse(dag)
+	if err != nil {
+		t.Fatal(err)
+	}
+	return g
+}
+
+func wantEdges(t *testing.T, g *Graph, edges string) {
+	t.Helper()
+
+	wantEdges := strings.Fields(edges)
+	wantEdgeMap := make(map[string]bool)
+	for _, e := range wantEdges {
+		wantEdgeMap[e] = true
+	}
+
+	for _, n1 := range g.Nodes {
+		for _, n2 := range g.Nodes {
+			got := g.HasEdge(n1, n2)
+			want := wantEdgeMap[n1+"->"+n2]
+			if got && want {
+				t.Logf("%s->%s", n1, n2)
+			} else if got && !want {
+				t.Errorf("%s->%s present but not expected", n1, n2)
+			} else if want && !got {
+				t.Errorf("%s->%s missing but expected", n1, n2)
+			}
+		}
+	}
+}
+
+func TestParse(t *testing.T) {
+	// Basic smoke test for graph parsing.
+	g := mustParse(t, diamond)
+
+	wantNodes := strings.Fields("a b c d")
+	if !reflect.DeepEqual(wantNodes, g.Nodes) {
+		t.Fatalf("want nodes %v, got %v", wantNodes, g.Nodes)
+	}
+
+	// Parse returns the transitive closure, so it adds d->a.
+	wantEdges(t, g, "b->a c->a d->a d->b d->c")
+}