code review 134780043: go.tools/cmd/vet: detect suspicious shifts

go.tools/cmd/vet: detect suspicious shifts

[mjibson, 2014-08-24 20:52:10]

Hello golang-codereviews@googlegroups.com,

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

[josharian, 2014-08-25 02:40:17]

Thanks for doing this. Here's a first pass of comments, looking just at the
implementation.

https://codereview.appspot.com/134780043/diff/40001/cmd/vet/shift.go
File cmd/vet/shift.go (right):

https://codereview.appspot.com/134780043/diff/40001/cmd/vet/shift.go#newcode34
cmd/vet/shift.go:34: for i, lhs := range node.Lhs {
From the spec: "In assignment operations, both the left- and right-hand
expression lists must contain exactly one single-valued expression..". You can
return early if the lhs or rhs has more than one expression. That should
simplify this a bit.

https://codereview.appspot.com/134780043/diff/40001/cmd/vet/shift.go#newcode48
cmd/vet/shift.go:48: func checkSuspiciousShift(f *File, node ast.Node, x, y
ast.Expr, op token.Token) {
op is unused.

https://codereview.appspot.com/134780043/diff/40001/cmd/vet/shift.go#newcode49
cmd/vet/shift.go:49: basic, ok := y.(*ast.BasicLit)
Use f.pkg.types[y].Value to get a constant value instead. It does full constant
evaluation, so e.g. it knows that 27+5 is 32, not just a binary expression.

https://codereview.appspot.com/134780043/diff/40001/cmd/vet/shift.go#newcode68
cmd/vet/shift.go:68: size = 8
The max meaningful shift for signed ints is one smaller than for unsigned ints.

https://codereview.appspot.com/134780043/diff/40001/cmd/vet/testdata/shift.go
File cmd/vet/testdata/shift.go (right):

https://codereview.appspot.com/134780043/diff/40001/cmd/vet/testdata/shift.go...
cmd/vet/testdata/shift.go:11: i8 << 7
It'd be nice for this code to be compilable. Assign to blank throughout, e.g.:

_ = i8 << 7

[minux, 2014-08-25 04:42:19]

https://codereview.appspot.com/134780043/diff/40001/cmd/vet/shift.go
File cmd/vet/shift.go (right):

https://codereview.appspot.com/134780043/diff/40001/cmd/vet/shift.go#newcode68
cmd/vet/shift.go:68: size = 8
On 2014/08/25 02:40:17, josharian wrote:
> The max meaningful shift for signed ints is one smaller than for unsigned
ints.
this is not right.

int8 >> 8 is still meaningful, you get either 0 or -1 depending on the sign of
the int8. And this is useful for example to calculate absolute value without
branch.

abs(x int8) = x ^ (x >> 8) - x >> 8

http://play.golang.org/p/1KMPSq7ULV

[dsymonds, 2014-08-25 06:41:28]

https://codereview.appspot.com/134780043/diff/40001/cmd/vet/shift.go
File cmd/vet/shift.go (right):

https://codereview.appspot.com/134780043/diff/40001/cmd/vet/shift.go#newcode23
cmd/vet/shift.go:23: binaryExpr,
join the next line onto this one. (keep the list of AST types checked on the
same line)

https://codereview.appspot.com/134780043/diff/40001/cmd/vet/shift.go#newcode80
cmd/vet/shift.go:80: f.Badf(node.Pos(), "suspicious shift of %s", ident)
I'm not sure what one would do with such a message. Can you make it clearer
what's wrong with the code?

[mjibson, 2014-08-26 14:58:29]

Hello golang-codereviews@googlegroups.com, josharian@gmail.com,
minux@golang.org, dsymonds@golang.org (cc: golang-codereviews@googlegroups.com),

Please take another look.

[josharian, 2014-08-26 19:53:16]

Another round. Once you fix the panic from non-constant shifts, I'll run this
over a big corpus to see what it catches.

https://codereview.appspot.com/134780043/diff/80001/cmd/vet/doc.go
File cmd/vet/doc.go (right):

https://codereview.appspot.com/134780043/diff/80001/cmd/vet/doc.go#newcode157
cmd/vet/doc.go:157: Shift and shift-assigns longer than the underlying
variable's length.
s/and shift-assigns//
s/longer than/equal to or longer than/
Maybe s/underlying//

I feel like there's probably a clearer overall formulation, but I don't know
what it is.

https://codereview.appspot.com/134780043/diff/80001/cmd/vet/shift.go
File cmd/vet/shift.go (right):

https://codereview.appspot.com/134780043/diff/80001/cmd/vet/shift.go#newcode45
cmd/vet/shift.go:45: amt, ok := exact.Int64Val(f.pkg.types[y].Value)
Int64Val panics when passed a nil.

And please add a test case for non-constant shifts.

https://codereview.appspot.com/134780043/diff/80001/cmd/vet/shift.go#newcode50
cmd/vet/shift.go:50: if t != nil {
This might be a bit clearer as:

if t == nil {
  return
}
b, ok := t.Underlying().(*types.Basic)

Your call.

https://codereview.appspot.com/134780043/diff/80001/cmd/vet/shift.go#newcode72
cmd/vet/shift.go:72: f.Badf(node.Pos(), "shift of %s by %d will always be 0",
ident, amt)
If the value is negative, the shifted value will be -1, not 0.

Perhaps instead something along the lines of:

"%s has size %d but is shifted by %d", ident, size, amt

My word-fu is weak today.

https://codereview.appspot.com/134780043/diff/80001/cmd/vet/testdata/shift.go
File cmd/vet/testdata/shift.go (right):

https://codereview.appspot.com/134780043/diff/80001/cmd/vet/testdata/shift.go...
cmd/vet/testdata/shift.go:11: i8 << 7
Again, please make this file compilable. E.g.

_ = i8 << 7
_ = i8 << (7 + 1) // ERROR ...

[josharian, 2014-08-26 19:54:05]

> > The max meaningful shift for signed ints is one smaller than for unsigned
> ints.
> this is not right.

Thanks, minux. As soon as I saw an email from you on this CL, I knew I'd screwed
this up. :)

[mjibson, 2014-08-26 20:53:40]

Hello golang-codereviews@googlegroups.com, josharian@gmail.com,
minux@golang.org, dsymonds@golang.org (cc: golang-codereviews@googlegroups.com),

Please take another look.

[josharian, 2014-08-26 21:28:30]

Wow. This found 308 instances in the corpus, and based on a sampling, almost all
of them are bugs. The full list is at
https://gist.github.com/josharian/7a434741abe827a36a59.

I noticed one false positive, in the stdlib:

math/big/nat.go:96
math/big/nat.go:104

The shifts are used here to break a uint64 into word-sized chunks; _W is a
constant, but it varies by platform. (As an aside, math/big's Word type should
probably be uint instead of uintptr, but I guess we can't change that now.)

dsymonds or minux, do you have an opinion about the false positive? I'm inclined
to call it unfortunate and live with it.

[dave_cheney.net, 2014-08-26 22:27:10]

+axw,

Thanks Josh, very informative.

Andrew, looks like there are a couple that need fixing in llgo.
On 27 Aug 2014 07:28, <josharian@gmail.com> wrote:

> Wow. This found 308 instances in the corpus, and based on a sampling,
> almost all of them are bugs. The full list is at
> https://gist.github.com/josharian/7a434741abe827a36a59.
>
> I noticed one false positive, in the stdlib:
>
> math/big/nat.go:96
> math/big/nat.go:104
>
> The shifts are used here to break a uint64 into word-sized chunks; _W is
> a constant, but it varies by platform. (As an aside, math/big's Word
> type should probably be uint instead of uintptr, but I guess we can't
> change that now.)
>
> dsymonds or minux, do you have an opinion about the false positive? I'm
> inclined to call it unfortunate and live with it.
>
> https://codereview.appspot.com/134780043/
>
> --
> You received this message because you are subscribed to the Google Groups
> "golang-codereviews" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to golang-codereviews+unsubscribe@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>

[axw, 2014-08-27 00:52:03]

On 2014/08/26 22:27:10, dfc wrote:
> +axw,
> 
> Thanks Josh, very informative.
> 
> Andrew, looks like there are a couple that need fixing in llgo.

Thanks Dave. They're just test cases, and intentional ones.

(Curiously, the corpus contains three out-of-date forks of llgo, but neither the
original nor the current.)

> On 27 Aug 2014 07:28, <mailto:josharian@gmail.com> wrote:
> 
> > Wow. This found 308 instances in the corpus, and based on a sampling,
> > almost all of them are bugs. The full list is at
> > https://gist.github.com/josharian/7a434741abe827a36a59.
> >
> > I noticed one false positive, in the stdlib:
> >
> > math/big/nat.go:96
> > math/big/nat.go:104
> >
> > The shifts are used here to break a uint64 into word-sized chunks; _W is
> > a constant, but it varies by platform. (As an aside, math/big's Word
> > type should probably be uint instead of uintptr, but I guess we can't
> > change that now.)
> >
> > dsymonds or minux, do you have an opinion about the false positive? I'm
> > inclined to call it unfortunate and live with it.
> >
> > https://codereview.appspot.com/134780043/
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> > "golang-codereviews" group.
> > To unsubscribe from this group and stop receiving emails from it, send an
> > email to mailto:golang-codereviews+unsubscribe@googlegroups.com.
> > For more options, visit https://groups.google.com/d/optout.
> >

[josharian, 2014-08-27 00:58:26]

> (Curiously, the corpus contains three out-of-date forks of llgo, but neither
the
> original nor the current.)

Being out of date is expected. Updating is slow, so I don't do it often. Does
the original (non-fork) llgo show up on godoc.org? The corpus is drawn directly
from godoc.org/-/index. I worried originally about forks but decided that forks
approximate importance, so overweighting forked projects is ok.

[axw, 2014-08-27 01:50:30]

On 2014/08/27 00:58:26, josharian wrote:
> > (Curiously, the corpus contains three out-of-date forks of llgo, but neither
> the
> > original nor the current.)
> 
> Being out of date is expected. Updating is slow, so I don't do it often. Does
> the original (non-fork) llgo show up on godoc.org? The corpus is drawn
directly
> from godoc.org/-/index. I worried originally about forks but decided that
forks
> approximate importance, so overweighting forked projects is ok.

No problems. The main repo is there at http://godoc.org/github.com/go-llvm/llgo.
Master has diverged significantly. The test code hasn't changed, it's just
moved; not sure why it doesn't show up. I'm not too fussed - free vetting is
always appreciated though.

[minux, 2014-08-27 06:05:57]

On Aug 26, 2014 5:28 PM, <josharian@gmail.com> wrote:
>
> Wow. This found 308 instances in the corpus, and based on a sampling,
> almost all of them are bugs. The full list is at
> https://gist.github.com/josharian/7a434741abe827a36a59.
>
> I noticed one false positive, in the stdlib:
>
> math/big/nat.go:96
> math/big/nat.go:104
>
> The shifts are used here to break a uint64 into word-sized chunks; _W is
> a constant, but it varies by platform. (As an aside, math/big's Word
> type should probably be uint instead of uintptr, but I guess we can't
> change that now.)
i don't understand why this code triggers the warning.

_W is at most 64 and t is uint64, so why govet gives the warning?
(i'm on mobile right now, so it's difficult to look at the code and
experiment, sorry if i missed something trivial)

[adg, 2014-08-27 12:36:09]

s/suspicious/shifty/g

[josharian, 2014-08-27 22:00:28]

> _W is at most 64 and t is uint64, so why govet gives the warning?

This check warns if you shift an X bit (u)int by >= X bits. We want >= instead
of > because the most common bug caught by this is of the flavor (stolen
straight from dfc):

var lo, hi uint32
result := uint64(hi<<32) | uint64(lo)

> s/suspicious/shifty/g

Brilliant.

[josharian, 2014-08-27 22:01:24]

LGTM

I'll wait another day or two before submitting.

Thanks again for doing this.

[minux, 2014-08-27 22:12:31]

On Aug 27, 2014 6:00 PM, <josharian@gmail.com> wrote:
>>
>> _W is at most 64 and t is uint64, so why govet gives the warning?
>
> This check warns if you shift an X bit (u)int by >= X bits. We want >=
> instead of > because the most common bug caught by this is of the flavor
> (stolen straight from dfc):
>
> var lo, hi uint32
> result := uint64(hi<<32) | uint64(lo)
could we check for >= size for left shifts and > size for right shifts?

[mjibson, 2014-08-27 22:18:56]

On Wed, Aug 27, 2014 at 6:12 PM, minux <minux@golang.org> wrote:
>
> could we check for >= size for left shifts and > size for right shifts?
>
> Can you explain the rationale for this?

[minux, 2014-08-27 23:44:41]

On Aug 27, 2014 6:18 PM, "Matt Jibson" <matt.jibson@gmail.com> wrote:
> On Wed, Aug 27, 2014 at 6:12 PM, minux <minux@golang.org> wrote:
>>
>> could we check for >= size for left shifts and > size for right shifts?
>
> Can you explain the rationale for this?
there are useful use of right shift of size,
and there are two examples in math/big/nat.go.

[dsymonds, 2014-08-27 23:56:39]

Rob should give this a review before anyone submits it.

https://codereview.appspot.com/134780043/diff/120001/cmd/vet/shift.go
File cmd/vet/shift.go (right):

https://codereview.appspot.com/134780043/diff/120001/cmd/vet/shift.go#newcode44
cmd/vet/shift.go:44: func checkSuspiciousShift(f *File, node ast.Node, x, y
ast.Expr) {
checkLongShift?

https://codereview.appspot.com/134780043/diff/120001/cmd/vet/testdata/shift.go
File cmd/vet/testdata/shift.go (right):

https://codereview.appspot.com/134780043/diff/120001/cmd/vet/testdata/shift.g...
cmd/vet/testdata/shift.go:9: func ShiftTest() {
can you add a test case for the shift being an expression? e.g.

_ = (i8 + 1) >> 8

Does the code work? The type should be deduceable; it'd be good to check that
the full expression appears in the error message.

[josharian, 2014-08-28 00:27:46]

> could we check for >= size for left shifts and > size for right shifts?

This is going to be a false positive / false negative tradeoff. Restricting to >
size for right shifts yields this list:
https://gist.github.com/josharian/3b08b915dc9a2e7c06c1. (The original was
https://gist.github.com/josharian/7a434741abe827a36a59.)

It no longer has a stdlib false positive, but it loses some true positives. I
haven't gone through enough manually to have a feel for the numbers.


> Rob should give this a review before anyone submits it.

Ack. Sorry for my over-enthusiasm. Thanks for the reminder.

[mjibson, 2014-08-28 18:02:40]

Hello golang-codereviews@googlegroups.com, josharian@gmail.com,
minux@golang.org, dsymonds@golang.org, dave@cheney.net, axwalk@gmail.com,
adg@golang.org, r@golang.org (cc: golang-codereviews@googlegroups.com),

Please take another look.

[dsymonds, 2014-08-29 00:57:42]

LGTM

The ball's in Rob's court.

[r, 2014-08-29 02:09:21]

https://codereview.appspot.com/134780043/diff/180001/cmd/vet/doc.go
File cmd/vet/doc.go (right):

https://codereview.appspot.com/134780043/diff/180001/cmd/vet/doc.go#newcode154
cmd/vet/doc.go:154: Suspicious shifts
s/uspicious s//

https://codereview.appspot.com/134780043/diff/180001/cmd/vet/shift.go
File cmd/vet/shift.go (right):

https://codereview.appspot.com/134780043/diff/180001/cmd/vet/shift.go#newcode21
cmd/vet/shift.go:21: "check for suspicious shifts",
this "suspicious" thing doesn't feel right. suspicion is an opinion held by a
person.
i'd prefer "useless" or "invalid". state the facts, not an opinion.

https://codereview.appspot.com/134780043/diff/180001/cmd/vet/shift.go#newcode71
cmd/vet/shift.go:71: default:
what about int and uint and uinptr?

[mjibson, 2014-08-29 17:06:58]

https://codereview.appspot.com/134780043/diff/180001/cmd/vet/shift.go
File cmd/vet/shift.go (right):

https://codereview.appspot.com/134780043/diff/180001/cmd/vet/shift.go#newcode71
cmd/vet/shift.go:71: default:
On 2014/08/29 02:09:21, r wrote:
> what about int and uint and uinptr?

I'm unsure about the correct way to determine the size of these.
unsafe.Sizeof(x) * 8 is my first thought. math/big/arith.go determines this with
const expressions. Another? Which is the best way?

[josharian, 2014-08-29 17:16:31]

On 2014/08/29 17:06:58, mjibson wrote:
> https://codereview.appspot.com/134780043/diff/180001/cmd/vet/shift.go
> File cmd/vet/shift.go (right):
> 
>
https://codereview.appspot.com/134780043/diff/180001/cmd/vet/shift.go#newcode71
> cmd/vet/shift.go:71: default:
> On 2014/08/29 02:09:21, r wrote:
> > what about int and uint and uinptr?
> 
> I'm unsure about the correct way to determine the size of these.
> unsafe.Sizeof(x) * 8 is my first thought. math/big/arith.go determines this
with
> const expressions. Another? Which is the best way?

This is a bit of a can of worms. The size of int, uint, and uintptr varies. We'd
want to use the minimum size they could be, which means looking at build tags
and file names. I'm not sure that it is worth it. r?

[r, 2014-08-29 17:17:15]

https://codereview.appspot.com/134780043/diff/180001/cmd/vet/shift.go
File cmd/vet/shift.go (right):

https://codereview.appspot.com/134780043/diff/180001/cmd/vet/shift.go#newcode71
cmd/vet/shift.go:71: default:
int and uint can be as small as 32 bits, so for code to be portable 32 is the
cutoff, period.

do not use vet's execution environment to decide what the target program's
environment is.

[mjibson, 2014-08-29 17:29:59]

Hello golang-codereviews@googlegroups.com, josharian@gmail.com,
minux@golang.org, dsymonds@golang.org, dave@cheney.net, axwalk@gmail.com,
adg@golang.org, r@golang.org (cc: golang-codereviews@googlegroups.com),

Please take another look.

[r, 2014-08-29 17:42:57]

https://codereview.appspot.com/134780043/diff/220001/cmd/vet/shift.go
File cmd/vet/shift.go (right):

https://codereview.appspot.com/134780043/diff/220001/cmd/vet/shift.go#newcode72
cmd/vet/shift.go:72: size = 32
// These types may be as small as 32 bits, but no smaller.

[mjibson, 2014-08-29 17:51:42]

Hello golang-codereviews@googlegroups.com, josharian@gmail.com,
minux@golang.org, dsymonds@golang.org, dave@cheney.net, axwalk@gmail.com,
adg@golang.org, r@golang.org (cc: golang-codereviews@googlegroups.com),

Please take another look.

[r, 2014-08-29 18:00:13]

https://codereview.appspot.com/134780043/diff/250001/cmd/vet/shift.go
File cmd/vet/shift.go (right):

https://codereview.appspot.com/134780043/diff/250001/cmd/vet/shift.go#newcode79
cmd/vet/shift.go:79: f.Badf(node.Pos(), "%s has size %d but is shifted by %d",
ident, size, amt)
int might not be 32 now, but you complain about a shift of 32. you need to
duplicate the error message or do a little trickery to avoid a nonsense message.

maybe

%s %stoo small for shift of %d

where the second %s is an empty string or "might be" for int, uint.

[mjibson, 2014-08-29 18:12:28]

Hello golang-codereviews@googlegroups.com, josharian@gmail.com,
minux@golang.org, dsymonds@golang.org, dave@cheney.net, axwalk@gmail.com,
adg@golang.org, r@golang.org (cc: golang-codereviews@googlegroups.com),

Please take another look.

[r, 2014-08-29 18:15:51]

LGTM

[r, 2014-08-29 18:17:04]

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

go.tools/cmd/vet: detect suspicious shifts

LGTM=josharian, dsymonds, r
R=golang-codereviews, josharian, minux, dsymonds, dave, axwalk, adg, r
CC=golang-codereviews
https://codereview.appspot.com/134780043

Committer: Rob Pike <r@golang.org>

[Éz, 2022-11-18 18:54:27]

On 2014/08/29 18:17:04, r wrote:
> *** Submitted as
> https://code.google.com/p/go/source/detail?r=37b8aca2b320&repo=tools ***
> 
> go.tools/cmd/vet: detect suspicious shifts
> 
> LGTM=josharian, dsymonds, r
> R=golang-codereviews, josharian, minux, dsymonds, dave, axwalk, adg, r
> CC=golang-codereviews
> https://codereview.appspot.com/134780043
> 
> Committer: Rob Pike <mailto:r@golang.org>

Apply repo