code review 7437049: go/types: "missing return" check

go/types: "missing return" check

Implementation closely based on Russ' CL 7440047.

Future work: The error messages could be better
(e.g., instead of "missing return" it might say
"missing return (no default in switch)", etc.).

[gri, 2013-03-01 22:10:30]

Hello adonovan@google.com, rsc@golang.org (cc: golang-dev@googlegroups.com),

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

[rsc, 2013-03-01 22:25:30]

Code looks fine. It would be nice to get the spec in first.

https://codereview.appspot.com/7437049/diff/10001/src/pkg/go/types/return.go
File src/pkg/go/types/return.go (right):

https://codereview.appspot.com/7437049/diff/10001/src/pkg/go/types/return.go#...
src/pkg/go/types/return.go:112: func hasBreak(s ast.Stmt, label string, implicit
bool) bool {
Do you already have a pass that checks that, for example, break Foo implies that
there is a label Foo attached to a break-able statement, and that if there is a
label Foo then it is used somewhere? If so it might be worth recording metadata
for use by hasBreak instead of making it reinvent the wheel. If not, then carry
on. :-)

(I do think the type checker should be doing those checks, fwiw, but I
understand that you might have just not gotten to it yet.)

[gri, 2013-03-01 22:30:50]

Yes, will wait with this for the spec (next on my list).
- gri

https://codereview.appspot.com/7437049/diff/10001/src/pkg/go/types/return.go
File src/pkg/go/types/return.go (right):

https://codereview.appspot.com/7437049/diff/10001/src/pkg/go/types/return.go#...
src/pkg/go/types/return.go:112: func hasBreak(s ast.Stmt, label string, implicit
bool) bool {
On 2013/03/01 22:25:30, rsc wrote:
> Do you already have a pass that checks that, for example, break Foo implies
that
> there is a label Foo attached to a break-able statement, and that if there is
a
> label Foo then it is used somewhere? If so it might be worth recording
metadata
> for use by hasBreak instead of making it reinvent the wheel. If not, then
carry
> on. :-)
> 
> (I do think the type checker should be doing those checks, fwiw, but I
> understand that you might have just not gotten to it yet.)

Agreed, an no, the type checker doesn't do it yet.

Will adjust this once it does. Reinventing (copying, really) the wheel helped me
at least understand the topic thoroughly.

[rsc, 2013-03-01 22:34:47]

One problem with the hasBreak implementation (I didn't care for my
experiment but it matters more in real library code) is that there are
inputs that can make it go quadratic. Something like:

L1: for {
L2: for {
L3: for {
L4: for {
L5: for {
L6: for {
...
Ln: for {
...
break L6
break L5
break L4
break L3
break L2
break L1
}
...
}
}
}
}
}
}

will traverse the inner most loop n times, once looking for each label. A
single label-matching pass would give a linear time pass. So when that's
happening anyway, it will be worth reusing. :-)

Russ

[adonovan, 2013-03-04 20:19:59]

On 2013/03/01 22:34:47, rsc wrote:
> One problem with the hasBreak implementation (I didn't care for my
> experiment but it matters more in real library code) is that there are
> inputs that can make it go quadratic. Something like:
> 
> L1: for {
> L2: for {
> L3: for {
> L4: for {
> L5: for {
> L6: for {
> ...
> Ln: for {
> ...
> break L6
> break L5
> break L4
> break L3
> break L2
> break L1
> }
> ...
> }
> }
> }
> }
> }
> }
> 
> will traverse the inner most loop n times, once looking for each label. A
> single label-matching pass would give a linear time pass. So when that's
> happening anyway, it will be worth reusing. :-)
> 
> Russ

[adonovan, 2013-03-04 20:20:30]

https://codereview.appspot.com/7437049/diff/10001/src/pkg/go/types/return.go
File src/pkg/go/types/return.go (right):

https://codereview.appspot.com/7437049/diff/10001/src/pkg/go/types/return.go#...
src/pkg/go/types/return.go:17: func (check *checker) isTerminating(s ast.Stmt,
label string) bool {
labels are named objects (i.e. canonical) so you can just pass their addresses
down the recursion, or nil in lieu of "".

https://codereview.appspot.com/7437049/diff/10001/src/pkg/go/types/return.go#...
src/pkg/go/types/return.go:17: func (check *checker) isTerminating(s ast.Stmt,
label string) bool {
labels are canonical objects so just pass the object's address and avoid string
comparisons.

s/s.Label.Name/s.Label/
s/""/nil/

https://codereview.appspot.com/7437049/diff/10001/src/pkg/go/types/return.go#...
src/pkg/go/types/return.go:50: if s.Tok == token.GOTO || s.Tok ==
token.FALLTHROUGH {
Is it actually necessary to check this condition?
If the branch is a break or continue, you wouldn't have reached this far in the
recursion because the enclosing hasBranch for the loop would have pruned the
search already.

https://codereview.appspot.com/7437049/diff/10001/src/pkg/go/types/return.go#...
src/pkg/go/types/return.go:130: if s.Label.Name == label {
s.Label == label

[gri, 2013-03-04 22:04:04]

https://codereview.appspot.com/7437049/diff/10001/src/pkg/go/types/return.go
File src/pkg/go/types/return.go (right):

https://codereview.appspot.com/7437049/diff/10001/src/pkg/go/types/return.go#...
src/pkg/go/types/return.go:17: func (check *checker) isTerminating(s ast.Stmt,
label string) bool {
On 2013/03/04 20:20:30, adonovan wrote:
> labels are named objects (i.e. canonical) so you can just pass their addresses
> down the recursion, or nil in lieu of "".

Yes, but we can do even better once branches/breaks are pointing to the
respective statement. Leaving alone for now.

https://codereview.appspot.com/7437049/diff/10001/src/pkg/go/types/return.go#...
src/pkg/go/types/return.go:50: if s.Tok == token.GOTO || s.Tok ==
token.FALLTHROUGH {
On 2013/03/04 20:20:30, adonovan wrote:
> Is it actually necessary to check this condition?
> If the branch is a break or continue, you wouldn't have reached this far in
the
> recursion because the enclosing hasBranch for the loop would have pruned the
> search already.

It's certainly necessary to check for the GOTO since we may be in the very first
call of isTerminating. I think it's also required for the FALLTHROUGH.

https://codereview.appspot.com/7437049/diff/10001/src/pkg/go/types/return.go#...
src/pkg/go/types/return.go:130: if s.Label.Name == label {
On 2013/03/04 20:20:30, adonovan wrote:
> s.Label == label

see comment above - will do in another CL

[rsc, 2013-03-04 22:07:32]

LGTM

Please add a TODO to replace hasBreak with something that walks the tree just
once.

https://codereview.appspot.com/7437049/diff/10001/src/pkg/go/types/testdata/s...
File src/pkg/go/types/testdata/stmt1.src (right):

https://codereview.appspot.com/7437049/diff/10001/src/pkg/go/types/testdata/s...
src/pkg/go/types/testdata/stmt1.src:1: // Copyright 2013 The Go Authors. All
rights reserved.
$GOROOT/test/return.go has an expanded set of test cases

[gri, 2013-03-04 22:40:37]

*** Submitted as https://code.google.com/p/go/source/detail?r=4ec840873df1 ***

go/types: "missing return" check

Implementation closely based on Russ' CL 7440047.

Future work: The error messages could be better
(e.g., instead of "missing return" it might say
"missing return (no default in switch)", etc.).

R=adonovan, rsc
CC=golang-dev
https://codereview.appspot.com/7437049

[gri, 2013-03-04 22:51:34]

On Mon, Mar 4, 2013 at 2:07 PM, <rsc@golang.org> wrote:

> LGTM
>
> Please add a TODO to replace hasBreak with something that walks the tree
> just once.
>

Just noticed that I made this change on the wrong workspace. The TODO will
show up in the next CL.
- gri