Compiler treatment of infinite loops

[Scott Pakin]

The Go compiler (I'm using go1.16 linux/amd64) correctly infers that function with an infinite for { … } loop that conditionally returns a value from within the loop does not also need to return a value at the end of the function:

• https://play.golang.org/p/07ZjFx2uJlx

However, changing that infinite loop to a three-clause for loop with true as the continuation condition (e.g., for i := 0; true; i++ { … }) complains about a missing return at end of function:

• https://play.golang.org/p/yf4ihkdBUXZ

Shouldn't the compiler treat those two cases the same?

[peterGo]

Another way to look at it.

The Go Programming Language Specification
https://golang.org/ref/spec

For statements

For statements with for clause

ForClause = [ InitStmt ] ";" [ Condition ] ";" [ PostStmt ] .

Any element of the ForClause may be empty but the semicolons are required unless there is only a condition.

If the condition is absent, it is equivalent to the boolean value true.

However, the compiler does not appear to apply the equivalency:

// no error
func ForLoop1() int {
    for i := 0; ; i++ {
        if i%123 == 0 {
            return 456
        }
    }
}

// error: missing return at end of function
func ForLoop2() int {

    for i := 0; true; i++ {

        if i%123 == 0 {
            return 456
        }
    }
}

https://play.golang.org/p/Q-hF7ZhL4Vf

Peter

[Brian Candler]

There is a flip side to that: if you add the return statements, then ForLoop1() gives an error due to unreachable code!

https://play.golang.org/p/0bajnJWTz7U

So you can't win either way.  I think this implies that if the behaviour were changed now, it would break the go compatibility promise.

[Scott Pakin]

On Friday, March 5, 2021 at 8:20:36 AM UTC-7 Brian Candler wrote:

There is a flip side to that: if you add the return statements, then ForLoop1() gives an error due to unreachable code!

https://play.golang.org/p/0bajnJWTz7U

So you can't win either way.  I think this implies that if the behaviour were changed now, it would break the go compatibility promise.

The Go developers might want to comment on this, but my interpretation of the Go compatibility promise is that working programs won't break, not that programs that fail to compile will suddenly compile.  So I think we're safe there.

I don't know if it makes any difference, but the "unreachable code" complaint is coming from go vet, not the compiler proper.

Still, you make an interesting observation.

[Marvin Renich]

* Brian Candler <b.ca...@pobox.com> [210305 10:21]:

> There is a flip side to that: if you add the return statements, then
> ForLoop1() gives an error due to unreachable code!
> https://play.golang.org/p/0bajnJWTz7U
>
> So you can't win either way. I think this implies that if the behaviour
> were changed now, it would break the go compatibility promise.

The Go compatibility promise does not apply to fixing bugs where the
compiler does not behave according to the language spec.

From https://golang.org/doc/go1compat#expectations:

Bugs. If a compiler or library has a bug that violates the
specification, a program that depends on the buggy behavior may break
if the bug is fixed. We reserve the right to fix such bugs.

I would consider this a good candidate for invoking this clause. Bugs
where the compiler incorrectly flags code as being reachable or
unreachable and fails to compile the code because of such a bug are
important to fix, IMO.

Would someone who has a github account please file an issue for this?

Thanks...Marvin

[Brian Candler]

On Friday, 5 March 2021 at 15:35:48 UTC Scott Pakin wrote:

The Go developers might want to comment on this, but my interpretation of the Go compatibility promise is that working programs won't break, not that programs that fail to compile will suddenly compile.

I was thinking the opposite, that code which previously compiled then fails to compile.  Say someone has written this:

func ForLoop2() int {

    for i := 0; true; i++ {

        if i%123 == 0 {
            return 456
        }
    }

    return 0
}

They were forced to include the "return 0" because although it's not needed, the compiler refuses to compile without it.  All works.

Now let's say the behaviour is changed so that the "true" condition is understood by the compiler to mean an infinite loop, and the subsequent code is known to unreachable.  I was thinking that the code will now refuse to compile, because go will reject the program (it will says the "return 0" is unreachable code).

But then as you pointed out:

 

  

I don't know if it makes any difference, but the "unreachable code" complaint is coming from go vet, not the compiler proper.

Ah yes - it does make a difference.

Tested with command-line go (instead of playground):

$ go run f1.go

# command-line-arguments

./f1.go:19:1: missing return at end of function

$ go run f2.go

$ go vet f2.go

# command-line-arguments

./f2.go:10:2: unreachable code

So including the "return 0" doesn't prevent it from compiling, it only causes "go vet" to whinge.

[Axel Wagner]

On Fri, Mar 5, 2021 at 4:36 PM Scott Pakin <scot...@pakin.org> wrote:

I don't know if it makes any difference, but the "unreachable code" complaint is coming from go vet, not the compiler proper.

It does. In particular, making `vet` more or less restrictive is not breaking the compatibility promise.

However, OPs complaint was different. The spec currently requires a function that returns a value to end in a terminating statement:

If the function's signature declares result parameters, the function body's statement list must end in a terminating statement.

 

The list of terminating statements has to say about loops:

A "for" statement in which:
• there are no "break" statements referring to the "for" statement, and
• the loop condition is absent.

The simplest case to illustrate the issue is thus probably https://play.golang.org/p/CjKR8lV36op. It is important to clearly state, that the compiler is thus behaving according to the spec and the compatibility promise applies. No ifs and buts.

Now. OP is right that it would be more consistent to treat both cases the same. However, I don't think we can reasonably do that.

• We can't start to reject the program containing the `for {}` loop, as that would break the compatibility promise.

• We can't say "if the loop is an endless loop, it is a terminating statement" because that would require solving the halting problem

• We could extend the list of terminating statements to include the `for true {}` case. But this opens the question of where to stop. Shouldn't the compiler also accept `x := true; for x {}`? What about `x := 42 % 2 == 0; for x {}`? Et cetera. It's, in my opinion, unreasonable to expand the list further - in my opinion, it's already too long.

• We can't drop the requirement for a function to end in a terminating statement altogether - that would open the question of what `func() int {}` does.

So, I just don't see any better options than what we are doing. Keep the spec as-is, implement reasonable heuristics as warnings in vet and require the programmer to be explicit and maybe add a superfluous `return` or `panic` or whatever here and there, to make the overzealous compiler shut up.

[Axel Wagner]

FWIW, one option I didn't mention, but which deserves a mention:

We could replace "all other statements are not terminating" with "an implementation is allowed to treat other statements as terminating, if it can prove it" (or similar). This wouldn't break the compatibility promise, as it would only start accepting programs that are currently rejected. However, the job of the spec is to clearly say which programs are valid and which are not. There are some cases where the spec allows an implementation to chose behaviors - but I don't think any of them would make the validity of go programs so blatantly dependent on what heuristics a compiler author might consider reasonable or not. They are mostly about performance and future-proofing. So we'd likely pay a pretty hefty price in terms of portability of code between compilers. We could still do it, but we still need to ask ourselves if it's really worth it. After all, again, the worst case is having to add an extra `return` here and there.

There's also, FWIW, another argument that could be made. Which is that it also should be obvious to a human reading the code that the loop is an endless loop. Requiring the condition to actually be empty is easily scannable. And it might not be such a bad thing, to force people to write more obvious code.

[Ian Lance Taylor]

On Fri, Mar 5, 2021 at 4:11 PM 'Axel Wagner' via golang-nuts
<golan...@googlegroups.com> wrote:
>
> FWIW, one option I didn't mention, but which deserves a mention:
>
> We could replace "all other statements are not terminating" with "an implementation is allowed to treat other statements as terminating, if it can prove it" (or similar). This wouldn't break the compatibility promise, as it would only start accepting programs that are currently rejected. However, the job of the spec is to clearly say which programs are valid and which are not. There are some cases where the spec allows an implementation to chose behaviors - but I don't think any of them would make the validity of go programs so blatantly dependent on what heuristics a compiler author might consider reasonable or not. They are mostly about performance and future-proofing. So we'd likely pay a pretty hefty price in terms of portability of code between compilers. We could still do it, but we still need to ask ourselves if it's really worth it. After all, again, the worst case is having to add an extra `return` here and there.

Yes, in general we don't want compilers to accept or reject programs
based on heuristics. That would mean that different compilers would
accept or reject different programs. We want to avoid that as much as
is feasible. We want all the compilers to implement the same
language.

Ian

[Keith Randall]

The fact that "for{}" is a terminating statement and "for true {}" is not, parallels the fact that "return" is a terminating statement and "if true { return }" is not.