internal/dag: add a Graph type and make node order deterministic

The go/types package doesn't care about node ordering because it's
just querying paths in the graph, but we're about to use this for the
runtime lock graph, and there we want determinism.

For #53789.

Change-Id: Ic41329bf2eb9a3a202f97c21c761ea588ca551c8
Reviewed-on: https://go-review.googlesource.com/c/go/+/418593
Reviewed-by: Michael Pratt <mpratt@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Run-TryBot: Austin Clements <austin@google.com>

3 files changed, 126 insertions, 20 deletions

diff --git a/src/go/build/deps_test.go b/src/go/build/deps_test.go
index c7e22463f9..e5f343a185 100644
--- a/src/go/build/deps_test.go
+++ b/src/go/build/deps_test.go
@@ -597,11 +597,10 @@ func TestDependencies(t *testing.T) {
 		if sawImport[pkg] == nil {
 			sawImport[pkg] = map[string]bool{}
 		}
-		ok := policy[pkg]
 		var bad []string
 		for _, imp := range imports {
 			sawImport[pkg][imp] = true
-			if !ok[imp] {
+			if !policy.HasEdge(pkg, imp) {
 				bad = append(bad, imp)
 			}
 		}
@@ -670,7 +669,7 @@ func findImports(pkg string) ([]string, error) {
 }
 
 // depsPolicy returns a map m such that m[p][d] == true when p can import d.
-func depsPolicy(t *testing.T) map[string]map[string]bool {
+func depsPolicy(t *testing.T) *dag.Graph {
 	g, err := dag.Parse(depsRules)
 	if err != nil {
 		t.Fatal(err)
diff --git a/src/internal/dag/parse.go b/src/internal/dag/parse.go
index 640b535454..1991772e39 100644
--- a/src/internal/dag/parse.go
+++ b/src/internal/dag/parse.go
@@ -43,13 +43,52 @@ package dag
 
 import (
 	"fmt"
+	"sort"
 	"strings"
 )
 
-// Parse returns a map m such that m[p][d] == true when there is a
-// path from p to d.
-func Parse(dag string) (map[string]map[string]bool, error) {
-	allowed := map[string]map[string]bool{"NONE": {}}
+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) 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)
@@ -68,40 +107,47 @@ func Parse(dag string) (map[string]map[string]bool, error) {
 			continue
 		}
 		for _, def := range r.def {
-			if allowed[def] != nil {
+			if def == "NONE" {
+				errorf("NONE cannot be a predecessor")
+				continue
+			}
+			if !g.addNode(def) {
 				errorf("multiple definitions for %s", def)
 			}
-			allowed[def] = make(map[string]bool)
 			for _, less := range r.less {
-				if allowed[less] == nil {
+				if less == "NONE" {
+					continue
+				}
+				if _, ok := g.byLabel[less]; !ok {
 					errorf("use of %s before its definition", less)
+				} else {
+					g.AddEdge(def, less)
 				}
-				allowed[def][less] = true
 			}
 		}
 	}
 
 	// Check for missing definition.
-	for _, tos := range allowed {
+	for _, tos := range g.edges {
 		for to := range tos {
-			if allowed[to] == nil {
+			if g.edges[to] == nil {
 				errorf("missing definition for %s", to)
 			}
 		}
 	}
 
 	// Complete transitive closure.
-	for k := range allowed {
-		for i := range allowed {
-			for j := range allowed {
-				if i != k && k != j && allowed[i][k] && allowed[k][j] {
+	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)
 					}
-					allowed[i][j] = true
+					g.AddEdge(i, j)
 				}
 			}
 		}
@@ -111,7 +157,7 @@ func Parse(dag string) (map[string]map[string]bool, error) {
 	for _, bad := range disallowed {
 		for _, less := range bad.less {
 			for _, def := range bad.def {
-				if allowed[def][less] {
+				if g.HasEdge(def, less) {
 					errorf("graph edge assertion failed: %s !< %s", less, def)
 				}
 			}
@@ -122,7 +168,7 @@ func Parse(dag string) (map[string]map[string]bool, error) {
 		return nil, fmt.Errorf("%s", strings.Join(errors, "\n"))
 	}
 
-	return allowed, nil
+	return g, nil
 }
 
 // A rule is a line in the DAG language where "less < def" or "less !< def".
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")
+}