1 // Copyright 2018 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 analysis
6 7 import (
8 "fmt"
9 "reflect"
10 "strings"
11 "unicode"
12 )
13 14 // Validate reports an error if any of the analyzers are misconfigured.
15 // Checks include:
16 // that the name is a valid identifier;
17 // that the Doc is not empty;
18 // that the Run is non-nil;
19 // that the Requires graph is acyclic;
20 // that analyzer fact types are unique;
21 // that each fact type is a pointer.
22 //
23 // Analyzer names need not be unique, though this may be confusing.
24 func Validate(analyzers []*Analyzer) error {
25 // Map each fact type to its sole generating analyzer.
26 factTypes := make(map[reflect.Type]*Analyzer)
27 28 // Traverse the Requires graph, depth first.
29 const (
30 white = iota
31 grey
32 black
33 finished
34 )
35 color := make(map[*Analyzer]uint8)
36 var visit func(a *Analyzer) error
37 visit = func(a *Analyzer) error {
38 if a == nil {
39 return fmt.Errorf("nil *Analyzer")
40 }
41 if color[a] == white {
42 color[a] = grey
43 44 // names
45 if !validIdent(a.Name) {
46 return fmt.Errorf("invalid analyzer name %q", a)
47 }
48 49 if a.Doc == "" {
50 return fmt.Errorf("analyzer %q is undocumented", a)
51 }
52 53 if a.Run == nil {
54 return fmt.Errorf("analyzer %q has nil Run", a)
55 }
56 // fact types
57 for _, f := range a.FactTypes {
58 if f == nil {
59 return fmt.Errorf("analyzer %s has nil FactType", a)
60 }
61 t := reflect.TypeOf(f)
62 if prev := factTypes[t]; prev != nil {
63 return fmt.Errorf("fact type %s registered by two analyzers: %v, %v",
64 t, a, prev)
65 }
66 if t.Kind() != reflect.Pointer {
67 return fmt.Errorf("%s: fact type %s is not a pointer", a, t)
68 }
69 factTypes[t] = a
70 }
71 72 // recursion
73 for _, req := range a.Requires {
74 if err := visit(req); err != nil {
75 return err
76 }
77 }
78 color[a] = black
79 }
80 81 if color[a] == grey {
82 stack := []*Analyzer{a}
83 inCycle := map[string]bool{}
84 for len(stack) > 0 {
85 current := stack[len(stack)-1]
86 stack = stack[:len(stack)-1]
87 if color[current] == grey && !inCycle[current.Name] {
88 inCycle[current.Name] = true
89 stack = append(stack, current.Requires...)
90 }
91 }
92 return &CycleInRequiresGraphError{AnalyzerNames: inCycle}
93 }
94 95 return nil
96 }
97 for _, a := range analyzers {
98 if err := visit(a); err != nil {
99 return err
100 }
101 }
102 103 // Reject duplicates among analyzers.
104 // Precondition: color[a] == black.
105 // Postcondition: color[a] == finished.
106 for _, a := range analyzers {
107 if color[a] == finished {
108 return fmt.Errorf("duplicate analyzer: %s", a.Name)
109 }
110 color[a] = finished
111 }
112 113 return nil
114 }
115 116 func validIdent(name string) bool {
117 for i, r := range name {
118 if !(r == '_' || unicode.IsLetter(r) || i > 0 && unicode.IsDigit(r)) {
119 return false
120 }
121 }
122 return name != ""
123 }
124 125 type CycleInRequiresGraphError struct {
126 AnalyzerNames map[string]bool
127 }
128 129 func (e *CycleInRequiresGraphError) Error() string {
130 var b strings.Builder
131 b.WriteString("cycle detected involving the following analyzers:")
132 for n := range e.AnalyzerNames {
133 b.WriteByte(' ')
134 b.WriteString(n)
135 }
136 return b.String()
137 }
138