Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

spec: no rule about loops in constant definition #13890

Open
momchil-velikov opened this issue Jan 9, 2016 · 13 comments

Comments

@momchil-velikov
Copy link
Contributor

commented Jan 9, 2016

The compiler issues error constant definition loop for the following program:

package main
import "fmt"
const C = len(u)
func f() ([1]int, [C]float64) {
    return [...]int{1}, [...]float64{1.1}
}
var u, v = f()
func main() {
    fmt.Println(C, v)
}

In fact the value if C (resp. the type of u) does not depend on the type of the second return of f.

The same program is compiled successfully by gccgo.

PS. Another test case

package main
import "fmt"
const C = len(u)
type S struct {
    X [1]int
    Y [C]int
}
var s S
var u, v = s.X, s.Y
func main() {
    fmt.Println(C, v)
}
@cznic

This comment has been minimized.

Copy link
Contributor

commented Jan 9, 2016

I believe this is working as intended.

From the specs: Package initialization:

Dependency analysis does not rely on the actual values of the variables, only on lexical references to them in the source, analyzed transitively. For instance, if a variable x's initialization expression refers to a function whose body refers to variable y then x depends on y. Specifically:

  • A reference to a variable or function is an identifier denoting that variable or function.
  • A reference to a method m is a method value or method expression of the form t.m, where the (static) type of t is not an interface type, and the method m is in the method set of t. It is immaterial whether the resulting function value t.m is invoked.
  • A variable, function, or method x depends on a variable y if x's initialization expression or body (for functions and methods) contains a reference to y or to a function or method that depends on y.

According to the above, C depends on u, u depends on f and f depends on C, which completes the circular dependency.

@bradfitz

This comment has been minimized.

Copy link
Member

commented Jan 9, 2016

There is some bug somewhere if gc and gccgo disagree.

/cc @alandonovan @griesemer @ianlancetaylor

@alandonovan

This comment has been minimized.

Copy link
Contributor

commented Jan 11, 2016

I agree with cznic that this is a dependency cycle, so all three frontends should report it as such. Thus this is a bug report against gccgo.

FWIW, go/types also yields an error, but the wrong one:

a.go:6:25: cannot return ([...]float64 literal) (value of type [1]float64) as value of type [0]float64

@mdempsky

This comment has been minimized.

Copy link
Member

commented Jan 11, 2016

Note that C is a constant, not a variable, so strictly speaking there cannot be a variable initialization/dependency cycle between C and u. Is there some other part of the spec that disallows @momchil-velikov's program(s)?

@alandonovan

This comment has been minimized.

Copy link
Contributor

commented Jan 11, 2016

Good point; the broader problem is that the spec does not currently forbid this program:

const (
    x = y
    y = x
)

@ianlancetaylor ianlancetaylor changed the title cmd/compiler: Incorrect constant definition loop error spec: no rule about loops in constant definition Jan 11, 2016

@ianlancetaylor ianlancetaylor added this to the Go1.7 milestone Jan 11, 2016

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented Jan 11, 2016

I've changed this to be a bug report against the spec.

@momchil-velikov

This comment has been minimized.

Copy link
Contributor Author

commented Jan 11, 2016

@alandonovan, I don't think there is a dependency cycle, unless a somewhat conservative notion of dependency is introduced in the spec, according to which the type of u would depend on the type of f as a whole, as opposed to depending only on the type of the first return of f.

@alandonovan

This comment has been minimized.

Copy link
Contributor

commented Jan 11, 2016

@momchil-velikov: I was mistakenly reading the specification of variable initialization cycles, which treats a reference to a function as a reference to all the entities mentioned in the function body. You are right that the corresponding text for constants need not be so conservative, but currently there is no such text at all.

@mdempsky

This comment has been minimized.

Copy link
Member

commented Apr 18, 2016

I think @alandonovan's sample

const (
    x = y
    y = x
)

is obviously invalid and should be disallowed, because it's a cycle in constant declarations.

However, I think @momchil-velikov's original sample is still interesting, because it reveals that current Go type checkers are unnecessarily integrating type propagation/inference with constant evaluations. If those two steps are split into separate phases, the cycle goes away.

Original:

const C = len(u)
func f() ([1]int, [C]float64) { ... }
var u, v = f()

Apply type propagation/inference:

const C int = len(u)
func f() ([1]int, [C]float64) { ... }
var (u [1]int, v [C]float64) = f()

Apply constant evaluation (including evaluating array bounds, which I expect in practice would even include evaluating the constant literal 1 in [1]int):

const C int = 1
func () ([1]int, [1]float64) { ... }
var (u [1]int, v [1]float64) = f()

Am I overlooking any counter examples where separating these steps would fail? I.e., programs where assigning types to names/expressions requires constant evaluation?

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented Apr 18, 2016

Our goal should be to write the simplest possible rule, not the rule that permits the largest number of programs. That is the rule we've tried to follow for initialization loops in general. The simpler the rule, the more likely that all Go compilers will agree on the definition of a valid program.

@griesemer

This comment has been minimized.

Copy link
Contributor

commented Apr 19, 2016

@mdempsky I believe it is difficult to separate type inference from constant evaluations - they are necessarily coupled: the length of an array type can be any constant expression, that value of which becomes part of that type. And a constant expression may depend on the result of a compile-time evaluated call of len(x), where the result of len(x) depends on the type of x.

I agree that some type checkers (gc, go/types, even) use a somewhat ad-hoc approach at the moment to resolve cycles - in the sense that we don't necessarily have proof that we caught all cases correctly. Determining explicit dependencies first, and evaluating types (and constants) afterwards, in a controlled manner, might be the way to go.

The spec doesn't say much if anything about cycles in constant expressions.

For what it's worth, I don't think this is for 1.7. These are esoteric corner cases, and hardly showstoppers.

@griesemer griesemer modified the milestones: Go1.8, Go1.7, Unreleased Apr 19, 2016

@mdempsky

This comment has been minimized.

Copy link
Member

commented Apr 19, 2016

@ianlancetaylor Agreed. I'm not saying @momchil-velikov's program has to be valid, but I think there should be a simple way to describe making it valid. I also wouldn't be surprised if allowing it is simpler than rejecting it.

@griesemer I don't think either of those reasons actually force type inference and constant evaluations to happen together. In fact, I think they both already show up in @momchil-velikov's sample, that I walked through above:

  1. The length of an array type like [C]float64 does involve a constant expression, but you don't need to evaluate the constant C to be able to do type inference. For example, given var a [C]float64, even without evaluating C you know that b := a means that b also has type [C]float64 or that a[i] has type float64. (Of course, if i happens to also be a constant, you need to ensure 0 <= i < C, but that can wait until we've evaluated i and C. It doesn't need to be done at the same time as type inference.)
  2. The expression len(a) always has type int, so const x = len(a) always declares a constant of type int. Again, we can defer evaluating the constant value len(a) until a separate constant evaluation pass.

Formalizing slightly, suppose for Go expression X we have Type(X) to denote X's type and Value(X) to denote X's constant value (if any). E.g., given b := a, we have Type(b)=Type(a); and given Type(a) = [C]T (for some type T), then Value(len(a)) = C.

My hypothesis is Type's definition does not depend on Value. If so, then it's sound to separate type inference from constant evaluation into separate passes.

Further, if expanding Type(X) or Value(X) in turn recursively references Type(X) or Value(X) (respectively), then there's a cycle and the program is invalid.

Under this formulation, disallowing @momchil-velikov's program requires an additional rule that if Type(X)'s expansion includes Type(Y) anywhere, then the program is also invalid if Value(Y)'s expansion mentions Type(X) or Value(X).

(Of course this sort of pseudo-language-theory is not suitable as is for the Go spec; it's just my thought process on the topic.)

@griesemer

This comment has been minimized.

Copy link
Contributor

commented Apr 19, 2016

@mdempsky I think you're right. I had a similar - albeit not quite formulated out - thought on my way home last night, that the actual length of the array is not required right away. I also agree that we should be able to make the program valid.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
7 participants
You can’t perform that action at this time.