code review 98120043: go.tools/cmd/vet: detect stupid boolean conditions

go.tools/cmd/vet: detect stupid boolean conditions

This CL introduces two vet checks. Statistics and code below are from a recent 50mb corpus of public code.

1. Check for redundant conjunctions and disjunctions. This check caught 26 instances, of which 20 were clearly copy/paste bugs and 6 appeared to be mere duplication. A typical example:

if xResolution < 0 || xResolution < 0 {
        panic("SetSize(): width < 0 || height < 0")
}

2. Check for expressions of the form 'x != c1 || x != c2' or 'x == c1 && x == c2', with c1 and c2 constant expressions. This check caught 16 instances, of which all were bugs. A typical example:

if rf.uri.Scheme != "http" || rf.uri.Scheme != "ftp" {
        rf.uri.Scheme = "file"
}

Fixes issue 7622.

[josharian, 2014-06-26 17:57:14]

Hello golang-codereviews@googlegroups.com (cc: r@golang.org, rsc@golang.org),

I'd like you to review this change to
https://code.google.com/p/go.tools

[jscrockett01, 2014-06-26 18:03:02]

In #2 you meant to say "with y and z constant expressions" instead of "x 
and z".

On Thursday, June 26, 2014 1:57:15 PM UTC-4, Josh Bleecher Snyder wrote:
>
> Reviewers: golang-codereviews, 
>
> Message: 
> Hello golang-co...@googlegroups.com <javascript:> (cc: r...@golang.org 
> <javascript:>, 
> r...@golang.org <javascript:>), 
>
> I'd like you to review this change to 
> https://code.google.com/p/go.tools 
>
>
> Description: 
> go.tools/cmd/vet: detect stupid boolean conditions 
>
> This CL introduces two vet checks. Statistics and code below are from a 
> recent 50mb corpus of public code. 
>
> 1. Check for redundant disjuncts. This check caught 19 instances, of 
> which 17 were clearly copy/paste bugs; 2 appeared to be mere 
> duplication. A typical example: 
>
> if xResolution < 0 || xResolution < 0 { 
>          panic("SetSize(): width < 0 || height < 0") 
> } 
>
> 2. Check for disjunctions of the form x != y || x != z, with x and z 
> constant expressions. This check caught 11 instances, of which all were 
> bugs. A typical example: 
>
> if rf.uri.Scheme != "http" || rf.uri.Scheme != "ftp" { 
>          rf.uri.Scheme = "file" 
> } 
>
> Fixes issue 7622. 
>
> Please review this at https://codereview.appspot.com/98120043/ 
>
> Affected files (+240, -0 lines): 
>    A cmd/vet/bool.go 
>    M cmd/vet/doc.go 
>    A cmd/vet/testdata/bool.go 
>
>
>

[josharian, 2014-06-26 18:04:41]

> In #2 you meant to say "with y and z constant expressions" instead of "x 
> and z".

Thanks, fixed.

[r, 2014-06-26 18:11:03]

this looks interesting. i'd like gri to look at how the ast is used.

https://codereview.appspot.com/98120043/diff/240001/cmd/vet/bool.go
File cmd/vet/bool.go (right):

https://codereview.appspot.com/98120043/diff/240001/cmd/vet/bool.go#newcode35
cmd/vet/bool.go:35: // unparenthized disjunction that may be safely reordered
and that
unparenthesized

https://codereview.appspot.com/98120043/diff/240001/cmd/vet/bool.go#newcode145
cmd/vet/bool.go:145: // idempotent reports whether evaluation of e is free from
side effects.
a more expansive comment would be welcome here

[gri, 2014-06-26 19:04:23]

Some initial feedback.

I still need to look at commutativeDisjuncts.

https://codereview.appspot.com/98120043/diff/240001/cmd/vet/bool.go
File cmd/vet/bool.go (right):

https://codereview.appspot.com/98120043/diff/240001/cmd/vet/bool.go#newcode32
cmd/vet/bool.go:32: var checkedDisjuncts = make(map[*ast.BinaryExpr]struct{})
make this

map[*ast.BinaryExpr]bool

and then you can simply write

if checkedDisjuncts[e] { ...

rather than

if _, ok := checkedDisjuncts[e]; ok { ...

below ( I don't think this will use more memory - maps always have space for a
1-word value, used or not, I believe)

As an aside: maps like theses are often called "visited" as in "we have visited
this node before". Perhaps

s/checkedDisjuncts/visitedDisjuncts/

(or seenDisjuncts, since you are using seen below)

(leaving up to you)

https://codereview.appspot.com/98120043/diff/240001/cmd/vet/bool.go#newcode92
cmd/vet/bool.go:92: fmt := make([]string, len(djs))
just use a map - no need to optimize by hand here (f.gofmt is so expensive)

var seen map[string]bool
for _, x := range djs {
   s := f.gofmt(x)
   if seen[s] {
      f.Badf(x.Pos(), ....)
   } else {
      seen[s] = true
   }
}

https://codereview.appspot.com/98120043/diff/240001/cmd/vet/bool.go#newcode106
cmd/vet/bool.go:106: // x != y || x != z where y and z are constant expressions.
write this as 

x != c1 || x != c2

to make it clearer that those are constants

(presumably x must be side-effect free at this point - should add in comment)

https://codereview.appspot.com/98120043/diff/240001/cmd/vet/bool.go#newcode108
cmd/vet/bool.go:108: // if y and z are different then it's always true.
Does the dual form x == c1 && x == c2 appear? Is it worthwhile checking it?

(I suspect it could be done with the same routine, using an extra parameter)

https://codereview.appspot.com/98120043/diff/240001/cmd/vet/bool.go#newcode110
cmd/vet/bool.go:110: seen := make(map[string]string)
seen could use a comment

maps ... to ....

https://codereview.appspot.com/98120043/diff/240001/cmd/vet/bool.go#newcode134
cmd/vet/bool.go:134: k := f.gofmt(e)
The choice of variable names here doesn't make this easy to read. How about
(with s/e/x/):

// dj is of the form x != c
sdj := f.gofmt(dj)
sx := f.gofmt(x)
if prev, found := seen[sx]; found {
   f.Badf(...
} else {
   seen[sx] = sdj
}

(using the convention that sx is the gofmt-ed version of x)

https://codereview.appspot.com/98120043/diff/240001/cmd/vet/bool.go#newcode150
cmd/vet/bool.go:150: case *ast.CallExpr:
note this also includes conversions since they look like calls - but conversions
are side-effect free (I wouldn't worry about it, but you could add a comment)

[gri, 2014-06-27 00:44:34]

https://codereview.appspot.com/98120043/diff/240001/cmd/vet/bool.go
File cmd/vet/bool.go (right):

https://codereview.appspot.com/98120043/diff/240001/cmd/vet/bool.go#newcode46
cmd/vet/bool.go:46: func commutativeDisjuncts(f *File, e *ast.BinaryExpr)
[][]ast.Expr {
I think this function is more complicated than needed. I don't understand why
you need to remember what you have already traversed - these are trees w/o any
sharing of nodes.

I've played a bit with some experimental code, see:

http://play.golang.org/p/zFL1cTG7TE

look at the split function (the rest is just for testing). It's not quite right
in general, but close, I think. I need to think some more about this; about to
leave now.

[josharian, 2014-07-01 02:05:19]

PTAL

Thanks for the detailed, helpful feedback. I'm not sure I've done it justice.


> this looks interesting.

It was rsc's idea.

https://codereview.appspot.com/98120043/diff/240001/cmd/vet/bool.go
File cmd/vet/bool.go (right):

https://codereview.appspot.com/98120043/diff/240001/cmd/vet/bool.go#newcode32
cmd/vet/bool.go:32: var checkedDisjuncts = make(map[*ast.BinaryExpr]struct{})
> make this
> 
> map[*ast.BinaryExpr]bool
> 
> and then you can simply write
> 
> if checkedDisjuncts[e] { ...
> 
> rather than
> 
> if _, ok := checkedDisjuncts[e]; ok { ...
> 
> below ( I don't think this will use more memory - maps always have space for a
> 1-word value, used or not, I believe)

I had in mind run time rather than memory. That depends on CL 93060043, which I
will mail when that part of the tree is open.

That said, the readability gains from your suggestion trump the tiny performance
difference. Done, and thanks.


> As an aside: maps like theses are often called "visited" as in "we have
visited
> this node before". Perhaps
> 
> s/checkedDisjuncts/visitedDisjuncts/
> 
> (or seenDisjuncts, since you are using seen below)

I opted for seenExprs, since they have not been visited yet, at least in the
ast.Walk sense.

https://codereview.appspot.com/98120043/diff/240001/cmd/vet/bool.go#newcode35
cmd/vet/bool.go:35: // unparenthized disjunction that may be safely reordered
and that
On 2014/06/26 18:11:03, r wrote:
> unparenthesized

Done.

https://codereview.appspot.com/98120043/diff/240001/cmd/vet/bool.go#newcode46
cmd/vet/bool.go:46: func commutativeDisjuncts(f *File, e *ast.BinaryExpr)
[][]ast.Expr {
> I think this function is more complicated than needed. I don't understand why
> you need to remember what you have already traversed - these are trees w/o any
> sharing of nodes.
> 
> I've played a bit with some experimental code, see:
> 
> http://play.golang.org/p/zFL1cTG7TE
> 
> look at the split function (the rest is just for testing). It's not quite
right
> in general, but close, I think. I need to think some more about this; about to
> leave now.

I spent quite some time trying out variants of this. I borrowed your split and
unparen functions and moved the seenExpr tracking to checkBool. I'm not sure it
is a net readability improvement, although it is nice to handle parenthesized
expressions correctly. I expect to do another rev of this.

https://codereview.appspot.com/98120043/diff/240001/cmd/vet/bool.go#newcode92
cmd/vet/bool.go:92: fmt := make([]string, len(djs))
> just use a map - no need to optimize by hand here (f.gofmt is so expensive)
> 
> var seen map[string]bool
> for _, x := range djs {
>    s := f.gofmt(x)
>    if seen[s] {
>       f.Badf(x.Pos(), ....)
>    } else {
>       seen[s] = true
>    }
> }

Done, thanks.

FWIW, I tried out faster AST-walking alternatives to gofmt, but they were
verbose. Anyway, we shouldn't get here often, and most boolean expressions are
short.

https://codereview.appspot.com/98120043/diff/240001/cmd/vet/bool.go#newcode106
cmd/vet/bool.go:106: // x != y || x != z where y and z are constant expressions.
On 2014/06/26 19:04:23, gri wrote:
> write this as 
> 
> x != c1 || x != c2
> 
> to make it clearer that those are constants
> 
> (presumably x must be side-effect free at this point - should add in comment)

Done.

https://codereview.appspot.com/98120043/diff/240001/cmd/vet/bool.go#newcode108
cmd/vet/bool.go:108: // if y and z are different then it's always true.
> Does the dual form x == c1 && x == c2 appear? Is it worthwhile checking it?
> 
> (I suspect it could be done with the same routine, using an extra parameter)

It does appear, although less often -- about 50% as much as the disjunctive
forms.

Added, with some refactoring. Thanks; I really should have thought of that.

https://codereview.appspot.com/98120043/diff/240001/cmd/vet/bool.go#newcode110
cmd/vet/bool.go:110: seen := make(map[string]string)
On 2014/06/26 19:04:22, gri wrote:
> seen could use a comment
> 
> maps ... to ....

Done.

https://codereview.appspot.com/98120043/diff/240001/cmd/vet/bool.go#newcode134
cmd/vet/bool.go:134: k := f.gofmt(e)
> The choice of variable names here doesn't make this easy to read. How about
> (with s/e/x/):
> 
> // dj is of the form x != c
> sdj := f.gofmt(dj)
> sx := f.gofmt(x)
> if prev, found := seen[sx]; found {
>    f.Badf(...
> } else {
>    seen[sx] = sdj
> }
> 
> (using the convention that sx is the gofmt-ed version of x)

Done, slightly differently. Please check whether they meet your standards. :)

https://codereview.appspot.com/98120043/diff/240001/cmd/vet/bool.go#newcode145
cmd/vet/bool.go:145: // idempotent reports whether evaluation of e is free from
side effects.
> a more expansive comment would be welcome here

Took a stab, not sure it is an improvement. More feedback welcome.

https://codereview.appspot.com/98120043/diff/240001/cmd/vet/bool.go#newcode150
cmd/vet/bool.go:150: case *ast.CallExpr:
On 2014/06/26 19:04:22, gri wrote:
> note this also includes conversions since they look like calls - but
conversions
> are side-effect free (I wouldn't worry about it, but you could add a comment)

Done.

[rsc, 2014-07-01 12:50:00]

lgtm; leaving for r
thanks very much for implementing this. it's my most common obvious mistake.

https://codereview.appspot.com/98120043/diff/260001/cmd/vet/bool.go
File cmd/vet/bool.go (right):

https://codereview.appspot.com/98120043/diff/260001/cmd/vet/bool.go#newcode28
cmd/vet/bool.go:28: e := n.(*ast.BinaryExpr)
If it's always a *ast.BinaryExpr why not make that the argument type?

https://codereview.appspot.com/98120043/diff/260001/cmd/vet/bool.go#newcode71
cmd/vet/bool.go:71: disjunction = boolOp{"disjunction", token.LOR, token.NEQ}
s/disjunction/or/g
s/conjunction/and/g

https://codereview.appspot.com/98120043/diff/260001/cmd/vet/bool.go#newcode85
cmd/vet/bool.go:85: n := 0
n is an unusual name for an index. 
the cap on the next line seems overly picky. until you have proof that it is
important, leave it out and let the runtime do its job.
the final append can be rolled into the loop.

var sets [][]ast.Expr
i := 0
for j := 0; j <= len(exprs); j++ {
    if j == len(exprs) || !reorderable(exprs[j]) {
        if i < j {
            sets = append(sets, exprs[i:j])
        }
        i = j+1
    }
}

https://codereview.appspot.com/98120043/diff/260001/cmd/vet/bool.go#newcode194
cmd/vet/bool.go:194: // split returns []{a, b, c, d}.
Looks like it actually returns {d, c, b, a}.

[josharian, 2014-07-01 15:33:00]

PTAL

Thanks, rsc.

I also removed seenExpr; it was complicated, not quite correct, and didn't pull
its weight. This will result in occasional duplicate complaints from vet, but
does not impact correctness or the tests.

https://codereview.appspot.com/98120043/diff/260001/cmd/vet/bool.go
File cmd/vet/bool.go (right):

https://codereview.appspot.com/98120043/diff/260001/cmd/vet/bool.go#newcode28
cmd/vet/bool.go:28: e := n.(*ast.BinaryExpr)
On 2014/07/01 12:50:00, rsc wrote:
> If it's always a *ast.BinaryExpr why not make that the argument type?

vet has switched to a registration model for checks; the method signature is
fixed. See CL 83400043.

https://codereview.appspot.com/98120043/diff/260001/cmd/vet/bool.go#newcode71
cmd/vet/bool.go:71: disjunction = boolOp{"disjunction", token.LOR, token.NEQ}
On 2014/07/01 12:50:00, rsc wrote:
> s/disjunction/or/g
> s/conjunction/and/g

Done.

https://codereview.appspot.com/98120043/diff/260001/cmd/vet/bool.go#newcode85
cmd/vet/bool.go:85: n := 0
On 2014/07/01 12:50:00, rsc wrote:
> n is an unusual name for an index. 
> the cap on the next line seems overly picky. until you have proof that it is
> important, leave it out and let the runtime do its job.
> the final append can be rolled into the loop.
> 
> var sets [][]ast.Expr
> i := 0
> for j := 0; j <= len(exprs); j++ {
>     if j == len(exprs) || !reorderable(exprs[j]) {
>         if i < j {
>             sets = append(sets, exprs[i:j])
>         }
>         i = j+1
>     }
> }

Done, thanks.

https://codereview.appspot.com/98120043/diff/260001/cmd/vet/bool.go#newcode194
cmd/vet/bool.go:194: // split returns []{a, b, c, d}.
On 2014/07/01 12:50:00, rsc wrote:
> Looks like it actually returns {d, c, b, a}.

Done.

[r, 2014-07-01 16:08:57]

LGTM

https://codereview.appspot.com/98120043/diff/300001/cmd/vet/bool.go
File cmd/vet/bool.go (right):

https://codereview.appspot.com/98120043/diff/300001/cmd/vet/bool.go#newcode52
cmd/vet/bool.go:52: // commutativeSets all reorderable sets of expressions in e
that are connected by op.
missing verb?

https://codereview.appspot.com/98120043/diff/300001/cmd/vet/bool.go#newcode181
cmd/vet/bool.go:181: }
easy to avoid the recursion, probably worthwhile because usually there is at
most one paren and the final invocation is unnecessary.

for {
  p, ok := e.(*ast.ParenExpr)
  if !ok {
    return e (and delete the return below)
  }
  e = p
}

https://codereview.appspot.com/98120043/diff/300001/cmd/vet/testdata/bool.go
File cmd/vet/testdata/bool.go (right):

https://codereview.appspot.com/98120043/diff/300001/cmd/vet/testdata/bool.go#...
cmd/vet/testdata/bool.go:51: // Check that all redundant disjuncts are flagged
s/disjunct(ion)?/or/ s/conjunct(ion)?/and/g

[gri, 2014-07-01 16:12:40]

FYI

https://codereview.appspot.com/98120043/diff/300001/cmd/vet/bool.go
File cmd/vet/bool.go (right):

https://codereview.appspot.com/98120043/diff/300001/cmd/vet/bool.go#newcode52
cmd/vet/bool.go:52: // commutativeSets all reorderable sets of expressions in e
that are connected by op.
s/all/collects all/

or returns all ?

https://codereview.appspot.com/98120043/diff/300001/cmd/vet/bool.go#newcode137
cmd/vet/bool.go:137: // reorderable reports whether evaluation of e may be
safely reordered
I'd call this

hasSideEffects

that's directly saying what it is checking instead. I have to think twice each
time I read 'reorderable' which is also why you need the comment (in
practice...)

[josharian, 2014-07-01 16:34:52]

All done. I'll leave this ~8hrs in case anyone wants to look again before I
submit.

https://codereview.appspot.com/98120043/diff/300001/cmd/vet/bool.go
File cmd/vet/bool.go (right):

https://codereview.appspot.com/98120043/diff/300001/cmd/vet/bool.go#newcode52
cmd/vet/bool.go:52: // commutativeSets all reorderable sets of expressions in e
that are connected by op.
On 2014/07/01 16:08:56, r wrote:
> missing verb?

Done.

https://codereview.appspot.com/98120043/diff/300001/cmd/vet/bool.go#newcode137
cmd/vet/bool.go:137: // reorderable reports whether evaluation of e may be
safely reordered
On 2014/07/01 16:12:39, gri wrote:
> I'd call this
> 
> hasSideEffects
> 
> that's directly saying what it is checking instead. I have to think twice each
> time I read 'reorderable' which is also why you need the comment (in
> practice...)

Done.

https://codereview.appspot.com/98120043/diff/300001/cmd/vet/bool.go#newcode181
cmd/vet/bool.go:181: }
On 2014/07/01 16:08:56, r wrote:
> easy to avoid the recursion, probably worthwhile because usually there is at
> most one paren and the final invocation is unnecessary.
> 
> for {
>   p, ok := e.(*ast.ParenExpr)
>   if !ok {
>     return e (and delete the return below)
>   }
>   e = p
> }
> 
>   

Done.

https://codereview.appspot.com/98120043/diff/300001/cmd/vet/testdata/bool.go
File cmd/vet/testdata/bool.go (right):

https://codereview.appspot.com/98120043/diff/300001/cmd/vet/testdata/bool.go#...
cmd/vet/testdata/bool.go:51: // Check that all redundant disjuncts are flagged
On 2014/07/01 16:08:56, r wrote:
> s/disjunct(ion)?/or/ s/conjunct(ion)?/and/g

Done.

[josharian, 2014-07-02 17:40:02]

*** Submitted as
https://code.google.com/p/go/source/detail?r=a2a0f87c4b38&repo=tools ***

go.tools/cmd/vet: detect stupid boolean conditions

This CL introduces two vet checks. Statistics and code below are from a recent
50mb corpus of public code.

1. Check for redundant conjunctions and disjunctions. This check caught 26
instances, of which 20 were clearly copy/paste bugs and 6 appeared to be mere
duplication. A typical example:

if xResolution < 0 || xResolution < 0 {
        panic("SetSize(): width < 0 || height < 0")
}

2. Check for expressions of the form 'x != c1 || x != c2' or 'x == c1 && x ==
c2', with c1 and c2 constant expressions. This check caught 16 instances, of
which all were bugs. A typical example:

if rf.uri.Scheme != "http" || rf.uri.Scheme != "ftp" {
        rf.uri.Scheme = "file"
}

Fixes issue 7622.

LGTM=rsc, r
R=golang-codereviews, jscrockett01, r, gri, rsc
CC=golang-codereviews
https://codereview.appspot.com/98120043