summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/go/build/deps_test.go5
-rw-r--r--src/internal/dag/parse.go80
-rw-r--r--src/internal/dag/parse_test.go61
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")
+}
View Lorry Controller Status