1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
package participle
import (
"fmt"
"strings"
)
// Perform some post-construction validation. This currently does:
//
// Checks for left recursion.
func validate(n node) error {
checked := map[*strct]bool{}
seen := map[node]bool{}
return visit(n, func(n node, next func() error) error {
if n, ok := n.(*strct); ok {
if !checked[n] && isLeftRecursive(n) {
return fmt.Errorf("left recursion detected on\n\n%s", indent(n.String()))
}
checked[n] = true
if seen[n] {
return nil
}
}
seen[n] = true
return next()
})
}
func isLeftRecursive(root *strct) (found bool) {
defer func() { _ = recover() }()
seen := map[node]bool{}
_ = visit(root.expr, func(n node, next func() error) error {
if found {
return nil
}
switch n := n.(type) {
case *strct:
if root.typ == n.typ {
found = true
}
case *sequence:
if !n.head {
panic("done")
}
}
if seen[n] {
return nil
}
seen[n] = true
return next()
})
return
}
func indent(s string) string {
return " " + strings.Join(strings.Split(s, "\n"), "\n ")
}
|
