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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
|
// Copyright 2018 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 analysis
import (
"fmt"
"reflect"
"strings"
"unicode"
)
// Validate reports an error if any of the analyzers are misconfigured.
// Checks include:
// that the name is a valid identifier;
// that the Requires graph is acyclic;
// that analyzer fact types are unique;
// that each fact type is a pointer.
func Validate(analyzers []*Analyzer) error {
// Map each fact type to its sole generating analyzer.
factTypes := make(map[reflect.Type]*Analyzer)
// Traverse the Requires graph, depth first.
const (
white = iota
grey
black
finished
)
color := make(map[*Analyzer]uint8)
var visit func(a *Analyzer) error
visit = func(a *Analyzer) error {
if a == nil {
return fmt.Errorf("nil *Analyzer")
}
if color[a] == white {
color[a] = grey
// names
if !validIdent(a.Name) {
return fmt.Errorf("invalid analyzer name %q", a)
}
if a.Doc == "" {
return fmt.Errorf("analyzer %q is undocumented", a)
}
// fact types
for _, f := range a.FactTypes {
if f == nil {
return fmt.Errorf("analyzer %s has nil FactType", a)
}
t := reflect.TypeOf(f)
if prev := factTypes[t]; prev != nil {
return fmt.Errorf("fact type %s registered by two analyzers: %v, %v",
t, a, prev)
}
if t.Kind() != reflect.Ptr {
return fmt.Errorf("%s: fact type %s is not a pointer", a, t)
}
factTypes[t] = a
}
// recursion
for _, req := range a.Requires {
if err := visit(req); err != nil {
return err
}
}
color[a] = black
}
if color[a] == grey {
stack := []*Analyzer{a}
inCycle := map[string]bool{}
for len(stack) > 0 {
current := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if color[current] == grey && !inCycle[current.Name] {
inCycle[current.Name] = true
stack = append(stack, current.Requires...)
}
}
return &CycleInRequiresGraphError{AnalyzerNames: inCycle}
}
return nil
}
for _, a := range analyzers {
if err := visit(a); err != nil {
return err
}
}
// Reject duplicates among analyzers.
// Precondition: color[a] == black.
// Postcondition: color[a] == finished.
for _, a := range analyzers {
if color[a] == finished {
return fmt.Errorf("duplicate analyzer: %s", a.Name)
}
color[a] = finished
}
return nil
}
func validIdent(name string) bool {
for i, r := range name {
if !(r == '_' || unicode.IsLetter(r) || i > 0 && unicode.IsDigit(r)) {
return false
}
}
return name != ""
}
type CycleInRequiresGraphError struct {
AnalyzerNames map[string]bool
}
func (e *CycleInRequiresGraphError) Error() string {
var b strings.Builder
b.WriteString("cycle detected involving the following analyzers:")
for n := range e.AnalyzerNames {
b.WriteByte(' ')
b.WriteString(n)
}
return b.String()
}
|
