1// Copyright 2022 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5// Package dag implements a language for expressing directed acyclic
6// graphs.
7//
8// The general syntax of a rule is:
9//
10//	a, b < c, d;
11//
12// which means c and d come after a and b in the partial order
13// (that is, there are edges from c and d to a and b),
14// but doesn't provide a relative order between a vs b or c vs d.
15//
16// The rules can chain together, as in:
17//
18//	e < f, g < h;
19//
20// which is equivalent to
21//
22//	e < f, g;
23//	f, g < h;
24//
25// Except for the special bottom element "NONE", each name
26// must appear exactly once on the right-hand side of any rule.
27// That rule serves as the definition of the allowed successor
28// for that name. The definition must appear before any uses
29// of the name on the left-hand side of a rule. (That is, the
30// rules themselves must be ordered according to the partial
31// order, for easier reading by people.)
32//
33// Negative assertions double-check the partial order:
34//
35//	i !< j
36//
37// means that it must NOT be the case that i < j.
38// Negative assertions may appear anywhere in the rules,
39// even before i and j have been defined.
40//
41// Comments begin with #.
42package dag
43
44import (
45	"cmp"
46	"fmt"
47	"slices"
48	"strings"
49)
50
51type Graph struct {
52	Nodes   []string
53	byLabel map[string]int
54	edges   map[string]map[string]bool
55}
56
57func newGraph() *Graph {
58	return &Graph{byLabel: map[string]int{}, edges: map[string]map[string]bool{}}
59}
60
61func (g *Graph) addNode(label string) bool {
62	if _, ok := g.byLabel[label]; ok {
63		return false
64	}
65	g.byLabel[label] = len(g.Nodes)
66	g.Nodes = append(g.Nodes, label)
67	g.edges[label] = map[string]bool{}
68	return true
69}
70
71func (g *Graph) AddEdge(from, to string) {
72	g.edges[from][to] = true
73}
74
75func (g *Graph) DelEdge(from, to string) {
76	delete(g.edges[from], to)
77}
78
79func (g *Graph) HasEdge(from, to string) bool {
80	return g.edges[from] != nil && g.edges[from][to]
81}
82
83func (g *Graph) Edges(from string) []string {
84	edges := make([]string, 0, 16)
85	for k := range g.edges[from] {
86		edges = append(edges, k)
87	}
88	slices.SortFunc(edges, func(a, b string) int {
89		return cmp.Compare(g.byLabel[a], g.byLabel[b])
90	})
91	return edges
92}
93
94// Parse parses the DAG language and returns the transitive closure of
95// the described graph. In the returned graph, there is an edge from "b"
96// to "a" if b < a (or a > b) in the partial order.
97func Parse(dag string) (*Graph, error) {
98	g := newGraph()
99	disallowed := []rule{}
100
101	rules, err := parseRules(dag)
102	if err != nil {
103		return nil, err
104	}
105
106	// TODO: Add line numbers to errors.
107	var errors []string
108	errorf := func(format string, a ...any) {
109		errors = append(errors, fmt.Sprintf(format, a...))
110	}
111	for _, r := range rules {
112		if r.op == "!<" {
113			disallowed = append(disallowed, r)
114			continue
115		}
116		for _, def := range r.def {
117			if def == "NONE" {
118				errorf("NONE cannot be a predecessor")
119				continue
120			}
121			if !g.addNode(def) {
122				errorf("multiple definitions for %s", def)
123			}
124			for _, less := range r.less {
125				if less == "NONE" {
126					continue
127				}
128				if _, ok := g.byLabel[less]; !ok {
129					errorf("use of %s before its definition", less)
130				} else {
131					g.AddEdge(def, less)
132				}
133			}
134		}
135	}
136
137	// Check for missing definition.
138	for _, tos := range g.edges {
139		for to := range tos {
140			if g.edges[to] == nil {
141				errorf("missing definition for %s", to)
142			}
143		}
144	}
145
146	// Complete transitive closure.
147	for _, k := range g.Nodes {
148		for _, i := range g.Nodes {
149			for _, j := range g.Nodes {
150				if i != k && k != j && g.HasEdge(i, k) && g.HasEdge(k, j) {
151					if i == j {
152						// Can only happen along with a "use of X before deps" error above,
153						// but this error is more specific - it makes clear that reordering the
154						// rules will not be enough to fix the problem.
155						errorf("graph cycle: %s < %s < %s", j, k, i)
156					}
157					g.AddEdge(i, j)
158				}
159			}
160		}
161	}
162
163	// Check negative assertions against completed allowed graph.
164	for _, bad := range disallowed {
165		for _, less := range bad.less {
166			for _, def := range bad.def {
167				if g.HasEdge(def, less) {
168					errorf("graph edge assertion failed: %s !< %s", less, def)
169				}
170			}
171		}
172	}
173
174	if len(errors) > 0 {
175		return nil, fmt.Errorf("%s", strings.Join(errors, "\n"))
176	}
177
178	return g, nil
179}
180
181// A rule is a line in the DAG language where "less < def" or "less !< def".
182type rule struct {
183	less []string
184	op   string // Either "<" or "!<"
185	def  []string
186}
187
188type syntaxError string
189
190func (e syntaxError) Error() string {
191	return string(e)
192}
193
194// parseRules parses the rules of a DAG.
195func parseRules(rules string) (out []rule, err error) {
196	defer func() {
197		e := recover()
198		switch e := e.(type) {
199		case nil:
200			return
201		case syntaxError:
202			err = e
203		default:
204			panic(e)
205		}
206	}()
207	p := &rulesParser{lineno: 1, text: rules}
208
209	var prev []string
210	var op string
211	for {
212		list, tok := p.nextList()
213		if tok == "" {
214			if prev == nil {
215				break
216			}
217			p.syntaxError("unexpected EOF")
218		}
219		if prev != nil {
220			out = append(out, rule{prev, op, list})
221		}
222		prev = list
223		if tok == ";" {
224			prev = nil
225			op = ""
226			continue
227		}
228		if tok != "<" && tok != "!<" {
229			p.syntaxError("missing <")
230		}
231		op = tok
232	}
233
234	return out, err
235}
236
237// A rulesParser parses the depsRules syntax described above.
238type rulesParser struct {
239	lineno   int
240	lastWord string
241	text     string
242}
243
244// syntaxError reports a parsing error.
245func (p *rulesParser) syntaxError(msg string) {
246	panic(syntaxError(fmt.Sprintf("parsing graph: line %d: syntax error: %s near %s", p.lineno, msg, p.lastWord)))
247}
248
249// nextList parses and returns a comma-separated list of names.
250func (p *rulesParser) nextList() (list []string, token string) {
251	for {
252		tok := p.nextToken()
253		switch tok {
254		case "":
255			if len(list) == 0 {
256				return nil, ""
257			}
258			fallthrough
259		case ",", "<", "!<", ";":
260			p.syntaxError("bad list syntax")
261		}
262		list = append(list, tok)
263
264		tok = p.nextToken()
265		if tok != "," {
266			return list, tok
267		}
268	}
269}
270
271// nextToken returns the next token in the deps rules,
272// one of ";" "," "<" "!<" or a name.
273func (p *rulesParser) nextToken() string {
274	for {
275		if p.text == "" {
276			return ""
277		}
278		switch p.text[0] {
279		case ';', ',', '<':
280			t := p.text[:1]
281			p.text = p.text[1:]
282			return t
283
284		case '!':
285			if len(p.text) < 2 || p.text[1] != '<' {
286				p.syntaxError("unexpected token !")
287			}
288			p.text = p.text[2:]
289			return "!<"
290
291		case '#':
292			i := strings.Index(p.text, "\n")
293			if i < 0 {
294				i = len(p.text)
295			}
296			p.text = p.text[i:]
297			continue
298
299		case '\n':
300			p.lineno++
301			fallthrough
302		case ' ', '\t':
303			p.text = p.text[1:]
304			continue
305
306		default:
307			i := strings.IndexAny(p.text, "!;,<#\n \t")
308			if i < 0 {
309				i = len(p.text)
310			}
311			t := p.text[:i]
312			p.text = p.text[i:]
313			p.lastWord = t
314			return t
315		}
316	}
317}
318