runtime: generate the lock ranking from a DAG description

Currently, the runtime lock rank graph is maintained manually in a
large set of arrays that give the partial order and a manual
topological sort of this partial order. Any changes to the rank graph
are difficult to reason about and hard to review, as well as likely to
cause merge conflicts. Furthermore, because the partial order is
manually maintained, it's not actually transitively closed (though
it's close), meaning there are many cases where rank a can be acquired
before b and b before c, but a cannot be acquired before c. While this
isn't technically wrong, it's very strange in the context of lock
ordering.

Replace all of this with a much more compact, readable, and
maintainable description of the rank graph written in the internal/dag
graph language. We statically generate the runtime structures from
this description, which has the advantage that the parser doesn't have
to run during runtime initialization and the structures can live in
static data where they can be accessed from any point during runtime
init.

The current description was automatically generated from the existing
partial order, combined with a transitive reduction. This ensures it's
correct, but it could use some manual messaging to call out the
logical layers and add some structure.

We do lose the ad hoc string names of the lock ranks in this
translation, which could mostly be derived from the rank constant
names, but not always. I may bring those back but in a more uniform
way.

We no longer need the tests in lockrank_test.go because they were
checking that we manually maintained the structures correctly.

Fixes #53789.

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

3 files changed, 113 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
index 1991772e39..9d5b918b11 100644
--- a/src/internal/dag/parse.go
+++ b/src/internal/dag/parse.go
@@ -71,6 +71,10 @@ 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]
 }