go/analysis/passes/bools: eliminate quadratic runtime, output
If you have x == 1 || x == 2 || x == 3 || x == 4, the pass considered the set
{x==1, x==2, x==3, x==4}
and then also
{x==2, x==3, x==4}
{x==3, x==4}
Since the comparison is itself linear in the size of the set, this was overall
taking time quadratic in the length of the || or && sequence.
Worse, if it found duplicates, they'd be reported a quadratic number of times.
This CL cuts the time and output to linear by avoiding already-checked
subexpressions. This cuts the time spent analyzing cmd/compile/internal/ssa
(with all passes enabled, not just this one) by 20%.
Fixes golang/go#28086.
Change-Id: I812f64bd5a44fea995c9ab0c4fa2fbefb44037ce
Reviewed-on: https://go-review.googlesource.com/c/tools/+/176457
Run-TryBot: Russ Cox <rsc@golang.org>
Reviewed-by: Rob Pike <r@golang.org>
Reviewed-by: Alan Donovan <adonovan@google.com>
diff --git a/go/analysis/passes/bools/bools.go b/go/analysis/passes/bools/bools.go
index 833c9d7..c82d367 100644
--- a/go/analysis/passes/bools/bools.go
+++ b/go/analysis/passes/bools/bools.go
@@ -30,8 +30,13 @@
nodeFilter := []ast.Node{
(*ast.BinaryExpr)(nil),
}
+ seen := make(map[*ast.BinaryExpr]bool)
inspect.Preorder(nodeFilter, func(n ast.Node) {
e := n.(*ast.BinaryExpr)
+ if seen[e] {
+ // Already processed as a subexpression of an earlier node.
+ return
+ }
var op boolOp
switch e.Op {
@@ -43,10 +48,7 @@
return
}
- // TODO(adonovan): this reports n(n-1)/2 errors for an
- // expression e||...||e of depth n. Fix.
- // See https://golang.org/issue/28086.
- comm := op.commutativeSets(pass.TypesInfo, e)
+ comm := op.commutativeSets(pass.TypesInfo, e, seen)
for _, exprs := range comm {
op.checkRedundant(pass, exprs)
op.checkSuspect(pass, exprs)
@@ -70,8 +72,9 @@
// expressions in e that are connected by op.
// For example, given 'a || b || f() || c || d' with the or op,
// commutativeSets returns {{b, a}, {d, c}}.
-func (op boolOp) commutativeSets(info *types.Info, e *ast.BinaryExpr) [][]ast.Expr {
- exprs := op.split(e)
+// commutativeSets adds any expanded BinaryExprs to seen.
+func (op boolOp) commutativeSets(info *types.Info, e *ast.BinaryExpr, seen map[*ast.BinaryExpr]bool) [][]ast.Expr {
+ exprs := op.split(e, seen)
// Partition the slice of expressions into commutative sets.
i := 0
@@ -188,11 +191,13 @@
// split returns a slice of all subexpressions in e that are connected by op.
// For example, given 'a || (b || c) || d' with the or op,
// split returns []{d, c, b, a}.
-func (op boolOp) split(e ast.Expr) (exprs []ast.Expr) {
+// seen[e] is already true; any newly processed exprs are added to seen.
+func (op boolOp) split(e ast.Expr, seen map[*ast.BinaryExpr]bool) (exprs []ast.Expr) {
for {
e = unparen(e)
if b, ok := e.(*ast.BinaryExpr); ok && b.Op == op.tok {
- exprs = append(exprs, op.split(b.Y)...)
+ seen[b] = true
+ exprs = append(exprs, op.split(b.Y, seen)...)
e = b.X
} else {
exprs = append(exprs, e)
diff --git a/go/analysis/passes/bools/testdata/src/a/a.go b/go/analysis/passes/bools/testdata/src/a/a.go
index c4b7dfd..5358fbc 100644
--- a/go/analysis/passes/bools/testdata/src/a/a.go
+++ b/go/analysis/passes/bools/testdata/src/a/a.go
@@ -46,22 +46,17 @@
_ = i+1 == 1 || i+1 == 1 // want `redundant or: i\+1 == 1 \|\| i\+1 == 1`
_ = i == 1 || j+1 == i || i == 1 // want `redundant or: i == 1 \|\| i == 1`
- // The various r.* patterns are intended to match duplicate
- // diagnostics reported for the same underlying problem.
- // See https://golang.org/issue/28086.
- // TODO(adonovan): fix the checker.
-
- _ = i == 1 || i == 1 || f() == 1 // want `redundant or: i == 1 \|\| i == 1` `r.*`
+ _ = i == 1 || i == 1 || f() == 1 // want `redundant or: i == 1 \|\| i == 1`
_ = i == 1 || f() == 1 || i == 1 // OK f may alter i as a side effect
_ = f() == 1 || i == 1 || i == 1 // want `redundant or: i == 1 \|\| i == 1`
// Test partition edge cases
- _ = f() == 1 || i == 1 || i == 1 || j == 1 // want `redundant or: i == 1 \|\| i == 1` `r.*`
+ _ = f() == 1 || i == 1 || i == 1 || j == 1 // want `redundant or: i == 1 \|\| i == 1`
_ = f() == 1 || j == 1 || i == 1 || i == 1 // want `redundant or: i == 1 \|\| i == 1`
_ = i == 1 || f() == 1 || i == 1 || i == 1 // want `redundant or: i == 1 \|\| i == 1`
- _ = i == 1 || i == 1 || f() == 1 || i == 1 // want `redundant or: i == 1 \|\| i == 1` `r.*` `r.*`
- _ = i == 1 || i == 1 || j == 1 || f() == 1 // want `redundant or: i == 1 \|\| i == 1` `r.*` `r.*`
- _ = j == 1 || i == 1 || i == 1 || f() == 1 // want `redundant or: i == 1 \|\| i == 1` `r.*`
+ _ = i == 1 || i == 1 || f() == 1 || i == 1 // want `redundant or: i == 1 \|\| i == 1`
+ _ = i == 1 || i == 1 || j == 1 || f() == 1 // want `redundant or: i == 1 \|\| i == 1`
+ _ = j == 1 || i == 1 || i == 1 || f() == 1 // want `redundant or: i == 1 \|\| i == 1`
_ = i == 1 || f() == 1 || f() == 1 || i == 1
_ = i == 1 || (i == 1 || i == 2) // want `redundant or: i == 1 \|\| i == 1`
@@ -76,9 +71,9 @@
_ = j == 0 ||
i == 1 ||
f() == 1 ||
- j == 0 || // want `redundant or: j == 0 \|\| j == 0` `r.*`
- i == 1 || // want `redundant or: i == 1 \|\| i == 1` `r.*` `r.*` `r.*`
- i == 1 || // want `redundant or: i == 1 \|\| i == 1` `r.*` `r.*`
+ j == 0 || // want `redundant or: j == 0 \|\| j == 0`
+ i == 1 || // want `redundant or: i == 1 \|\| i == 1`
+ i == 1 || // want `redundant or: i == 1 \|\| i == 1`
i == 1 ||
j == 0 ||
k == 0
@@ -94,7 +89,7 @@
_ = 0 != <-c && 0 != <-c // OK subsequent receives may yield different values
_ = f() != 0 && f() != 0 // OK f might have side effects
_ = f != nil && f != nil // want `redundant and: f != nil && f != nil`
- _ = i != 1 && i != 1 && f() != 1 // want `redundant and: i != 1 && i != 1` `r.*`
+ _ = i != 1 && i != 1 && f() != 1 // want `redundant and: i != 1 && i != 1`
_ = i != 1 && f() != 1 && i != 1 // OK f may alter i as a side effect
_ = f() != 1 && i != 1 && i != 1 // want `redundant and: i != 1 && i != 1`
}
