report cycle when visiting a grey analyzer
Fixes golang/go#40408
Change-Id: I04cd852f816f072e0e89c8ed5af636b09d0b54b4
GitHub-Last-Rev: 627dd414eb90d239cab9fce38454d43be133276e
GitHub-Pull-Request: golang/tools#244
Reviewed-on: https://go-review.googlesource.com/c/tools/+/244799
Run-TryBot: Rebecca Stambler <rstambler@golang.org>
gopls-CI: kokoro <noreply+kokoro@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Michael Matloob <matloob@golang.org>
diff --git a/go/analysis/validate.go b/go/analysis/validate.go
index be98143..ad0e727 100644
--- a/go/analysis/validate.go
+++ b/go/analysis/validate.go
@@ -3,6 +3,7 @@
import (
"fmt"
"reflect"
+ "strings"
"unicode"
)
@@ -58,14 +59,28 @@
}
// recursion
- for i, req := range a.Requires {
+ for _, req := range a.Requires {
if err := visit(req); err != nil {
- return fmt.Errorf("%s.Requires[%d]: %v", a.Name, i, err)
+ 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 {
@@ -95,3 +110,17 @@
}
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()
+}
diff --git a/go/analysis/validate_test.go b/go/analysis/validate_test.go
new file mode 100644
index 0000000..1116034
--- /dev/null
+++ b/go/analysis/validate_test.go
@@ -0,0 +1,118 @@
+// Copyright 2020 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 (
+ "strings"
+ "testing"
+)
+
+func TestValidate(t *testing.T) {
+ var (
+ dependsOnSelf = &Analyzer{
+ Name: "dependsOnSelf",
+ Doc: "this analyzer depends on itself",
+ }
+ inCycleA = &Analyzer{
+ Name: "inCycleA",
+ Doc: "this analyzer depends on inCycleB",
+ }
+ inCycleB = &Analyzer{
+ Name: "inCycleB",
+ Doc: "this analyzer depends on inCycleA and notInCycleA",
+ }
+ pointsToCycle = &Analyzer{
+ Name: "pointsToCycle",
+ Doc: "this analyzer depends on inCycleA",
+ }
+ notInCycleA = &Analyzer{
+ Name: "notInCycleA",
+ Doc: "this analyzer depends on notInCycleB and notInCycleC",
+ }
+ notInCycleB = &Analyzer{
+ Name: "notInCycleB",
+ Doc: "this analyzer depends on notInCycleC",
+ }
+ notInCycleC = &Analyzer{
+ Name: "notInCycleC",
+ Doc: "this analyzer has no dependencies",
+ }
+ )
+
+ dependsOnSelf.Requires = append(dependsOnSelf.Requires, dependsOnSelf)
+ inCycleA.Requires = append(inCycleA.Requires, inCycleB)
+ inCycleB.Requires = append(inCycleB.Requires, inCycleA, notInCycleA)
+ pointsToCycle.Requires = append(pointsToCycle.Requires, inCycleA)
+ notInCycleA.Requires = append(notInCycleA.Requires, notInCycleB, notInCycleC)
+ notInCycleB.Requires = append(notInCycleB.Requires, notInCycleC)
+ notInCycleC.Requires = []*Analyzer{}
+
+ cases := []struct {
+ analyzers []*Analyzer
+ wantErr bool
+ analyzersInCycle map[string]bool
+ }{
+ {
+ []*Analyzer{dependsOnSelf},
+ true,
+ map[string]bool{"dependsOnSelf": true},
+ },
+ {
+ []*Analyzer{inCycleA, inCycleB},
+ true,
+ map[string]bool{"inCycleA": true, "inCycleB": true},
+ },
+ {
+ []*Analyzer{pointsToCycle},
+ true,
+ map[string]bool{"inCycleA": true, "inCycleB": true},
+ },
+ {
+ []*Analyzer{notInCycleA},
+ false,
+ map[string]bool{},
+ },
+ }
+
+ for _, c := range cases {
+ got := Validate(c.analyzers)
+
+ if !c.wantErr {
+ if got == nil {
+ continue
+ }
+ t.Errorf("got unexpected error while validating analyzers %v: %v", c.analyzers, got)
+ }
+
+ if got == nil {
+ t.Errorf("expected error while validating analyzers %v, but got nil", c.analyzers)
+ }
+
+ err, ok := got.(*CycleInRequiresGraphError)
+ if !ok {
+ t.Errorf("want CycleInRequiresGraphError, got %T", err)
+ }
+
+ for a := range c.analyzersInCycle {
+ if !err.AnalyzerNames[a] {
+ t.Errorf("analyzer %s should be in cycle", a)
+ }
+ }
+ for a := range err.AnalyzerNames {
+ if !c.analyzersInCycle[a] {
+ t.Errorf("analyzer %s should not be in cycle", a)
+ }
+ }
+ }
+}
+
+func TestCycleInRequiresGraphErrorMessage(t *testing.T) {
+ err := CycleInRequiresGraphError{}
+ errMsg := err.Error()
+ wantSubstring := "cycle detected"
+ if !strings.Contains(errMsg, wantSubstring) {
+ t.Errorf("error string %s does not contain expected substring %q", errMsg, wantSubstring)
+ }
+}
