From 43a123c1ae6613b3efeed291fa552ecd909d3acf Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Tue, 16 Apr 2024 21:23:18 +0200 Subject: Adding upstream version 1.20.14. Signed-off-by: Daniel Baumann --- src/internal/dag/alg.go | 63 +++++++++ src/internal/dag/alg_test.go | 46 ++++++ src/internal/dag/parse.go | 314 +++++++++++++++++++++++++++++++++++++++++ src/internal/dag/parse_test.go | 61 ++++++++ 4 files changed, 484 insertions(+) create mode 100644 src/internal/dag/alg.go create mode 100644 src/internal/dag/alg_test.go create mode 100644 src/internal/dag/parse.go create mode 100644 src/internal/dag/parse_test.go (limited to 'src/internal/dag') diff --git a/src/internal/dag/alg.go b/src/internal/dag/alg.go new file mode 100644 index 0000000..8800279 --- /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 0000000..e5ea8b6 --- /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 0000000..9d5b918 --- /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 0000000..b2520c3 --- /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") +} -- cgit v1.2.3