Comment 1:

Labels changed: added priority-soon, removed priority-triage.

Owner changed to @adonovan.

Status changed to Accepted.

Comment 2:

Thanks for finding and reporting an interesting and subtle constellation of bugs!  I
think this behaviour arises from a lack of clarity in the language specification, but
it's not yet clear to me what the appropriate fix is.
Consider this source program and generated SSA code:
    bitSize := 64
    cutoff := uint64(1 << uint(bitSize-1))
    t0 = 64:int - 1:int                                                     int
        t1 = convert uint <- int (t0)                                          uint
        t2 = convert uint64 <- uint (t1)                                     uint64
        t3 = 1:untyped integer << t2                                untyped integer
The expression 1 is an untyped integer constant, and the shift is non-constant since the
right operand is a variable.  The spec tells us:
  "If the left operand of a non-constant shift expression is an untyped constant, the type of the constant is what it would be if the shift expression were replaced by its left operand alone."
There are a number of problems with this statement (and it has proven very subtle to
implement).
Firstly, the term "untyped" is misleading, as it really means something like "exact", or
more precisely "of a very large but implementation-specific width".  From a
type-theoretic perspective, the types of "untyped constants" are real types.  I move for
a future version of the spec to describe them with a different term such as "exact".
I think this sentence assumes the reader knows that type-checking requires both
bottom-up and top-down attributes of the abstract syntax tree---or "synthesized" and
"inherited" attributes, to use Knuth's attribute grammar terminology---and what it is
trying to say is that the attributes inherited by the x<<y expression are also
inherited by the x subtree.  It is confusing because the "if ..." clause seems to know
already the type of x ("an untyped constant") yet the type is determined by the
"then..." clause ("the type of the constant would be..."), which seems circular.  Only
by explaining type inference as a function of both synthetic and inherited attributes
does it make sense.
Now consider y := 1 << x.  We've determined that the type of 1 here is the same as
the type of 1 in this code: y := 1.  But is that int (inherited from the assignment to
y) or is it 'untyped int', which is the synthesized type of 1?  If the former, then we
have a bug in the type-checker since it should not report 'untyped int' for this
literal, nor indeed for any expression except those internal to a constant expression. 
In the concrete example at the top, the inherited type might by uint64 from the
conversion, but it's not clear.
Then there's a separate question of the following possible (but not current) invariant:
should any SSA instruction yield a value of an "untyped" type?  I think the answer
should be "no", and I would love to make it so, since representing such values is
challenging and the intent of the spec is that they're only needed by the compiler
front-end.  Currently, values of 'untyped' types do appear in the SSA form, and the
interpreter represents them by whatever type they would be converted to if assigned to
an empty interface: int, float64, etc.  So if you're running on a 32-bit system, they'll
be converted to int, which means you'll see 32-bit arithmetic in the shift operation,
which yields the value of zero.  The spec nowhere describes the width of the arithmetic
used in an "untyped" shift, perhaps because it assumes that all variables have "typed"
types ultimately derived from their inherited type.
A more prosaic bug you have found is that the SSA builder seems to be generating a
rather unnecessary pair of conversions int->uint->uint64; I will file a separate
bug report for that.
Also, just FYI:
 
- I find the (underspecified) 'println' built-in function very helpful for debugging
since it allows one to inspect a value without importing functions from other packages
such as fmt.Print or os.Exit.  For example:
func main() {
        bitSize := 64
        println(uint64(1 << uint(bitSize-1)))
}
- Changing 'bitSize := 64' to 'const bitSize = 64' causes the whole thing to become
constant folded.
- There are three commented-out lines at the end of ssa/interp.visitInstr.  Uncommenting
them causes the interpreter to print the result of every instruction.  This can be
useful for debugging very tiny programs such as the one above.  I will give your
interpreter a try today though.

Owner changed to @griesemer.

Comment 3 by rocky.bernstein:

It's not really my interpreter. It's *your* interpreter with a couple of
changes ;-)

Comment 4:

(Sorry, I meant "debugger".)

Comment 5:

The spec says ( http://tip.golang.org/ref/spec#Operators ):
"If the left operand of a non-constant shift expression is an untyped constant, the type
of the constant is what it would be if the shift expression were replaced by its left
operand alone."
For:
uint64(1 << s)
we get:
uint64(1)
Furthermore, the spec says ( http://tip.golang.org/ref/spec#Constants ):
"A constant may be given a type explicitly by a constant declaration or conversion, or
implicitly when used in a variable declaration or an assignment or as an operand in an
expression."
Therefore, in this case, the type of 1 is uint64 since it's given an explicit type via a
conversion.
There may be a bug in go/types or elsewhere, but the spec is reasonably clear about the
type of 1 here.

Comment 6:

> There may be a bug in go/types or elsewhere, ...
go/types infers an 'untyped' type for the constant 1, and for many other constant
expressions for which I think a 'typed' type is appropriate.  
        const c = 2
        var x uint
        println(uint64(c << x))
        t0 = convert uint64 <- uint (0:uint)                             uint64
        t1 = 2:untyped integer << t0                            untyped integer   !!!
        t2 = convert uint64 <- untyped integer (t1)                      uint64
        t3 = println(t2, nil:[]interface{})                                  ()
> ... the spec is reasonably clear about the type of 1 here.
It's clear once the reader understands that type information flows both top-down and
bottom-up, but this is an implicit assumption of the spec.  It would be good to state
this explicitly and to rephrase the sentence ("If the left operand...") with reference
to it.  Otherwise it sounds like the type of the constant changes from untyped to typed,
which is a confusingly imperative description of type-checking.

Comment 7:

The sentence:
"If the left operand of a non-constant shift expression is an untyped constant, the type
of the constant is what it would be if the shift expression were replaced by its left
operand alone."
implies that type information is also "flowing down".
The spec could be more precise, but this is not the issue at hand (we have other issues
open in that respect).

Comment 8:

I am confused. The issue summary says that the issue is about the spec, but
it sounds like the spec is okay.
If this is a spec issue, please be clearer (and more concise) about what
needs changing.
If this is not a spec issue, please correct the summary.

Comment 9:

IMHO the spec should:
(a) explicitly state that type-checking requires both bottom-up and top-down attributes
of the AST.
(b) rephrase the type inference rule for c<<v (where c is a constant and v a
variable) to make the use of top-down/bottom-up information clear.  Currently it could
be construed either as a circular definition, or as a two-step imperative algorithm that
infers types and then mutates them, neither of which is the intended reading.

Comment 10:

This is NOT a spec issue. The spec could be clearer, but the specific bug at hand is a
go/types bug (fix: https://golang.org/cl/11007043); and the respective spec
question has been answered many times before quite clearly.
Updated the description.

Comment 11 by rocky.bernstein:

How about splitting this into several issues which can be closed or tracked
independently? Namely: 
1. There are two concerns with the way the spec is written. In subsequent discussion,
the intent of the spec has been clarified, even if the spec could be phrased better.
(And I agree, the intent could be made clearer, even if only by giving that how that
specific example done in the discussion above.)
2. But given that, as best as I can now tell, there is a bug the way the types have been
assigned in this particular case. 
3. Perhaps there is a weirdness or inelegance in the way constants are handled with
"untyped integer". 
4. And finally you mention the weirdness with the multiple sets of conversions on
int->unit->uint64 in this specific case.  
I'm probably the wrong person to split this issue up as I really don't understand things
as well as the others.

Comment 12:

I don't believe the spec should refer to specific implementation
techniques, such as bottom-up and top-down attribute grammars.
It should be made clear, but it should not require a PhD in compilers or
type theory to read.

Comment 13:

This issue was closed by revision golang/tools@1aa0484.

Status changed to Fixed.

Comment 14:

Agreed, but...
[dons pedant hat]
...an attribute grammar is an analytical tool, not an implementation
technique.  Same goes for type inference rules.
Efficient implementations may resemble neither.
Of course, as I don't have one. :)
A simpler way to say it is that the type of an expression depends upon
(a) its syntax;
(b) the name->type mapping in its environment; and
(c) perhaps, the type that is "wanted" by its enclosing context.
(c) is a somewhat non-obvious yet critical fact of Go's type system, and no
matter what implementation you choose (or mental model you have), it will
be wrong if it doesn't capture it.
Rocky wrote:
tracked independently? Namely:
discussion, the intent of the spec has been clarified, even if the spec
could be phrased better. (And I agree, the intent could be made clearer,
even if only by giving that how that specific example done in the
discussion above.)
I think I've said enough about this. :)
types have been assigned in this particular case.
This was fixed in CL 088133ed831d.
conversions on int->unit->uint64 in this specific case.
I've just mailed out https://golang.org/cl/11011043 to fix this.

Comment 15 by rocky.bernstein:

Boy, that was fast to fix! Thanks everyone!
When go inside go.tools/ssa/interp and run "go test -test.short" coverage.go now fails.
Attached is a log of what I get as it's possible I'm doing something wrong.

Attachments:

1. interp-fail.log (510 bytes)

Comment 16:

Are you running an x86 32bit version (as opposed to 64bit?). We are seeing the same
failure on the dashboard.
http://build.golang.org/log/1dd1e084fea8765913ac9ce93d2c158d583e64f3

Comment 17 by rocky.bernstein:

Curiouser and curiouser. Narowing the code in coverage.go it appears what is failing is
code that was just added. In particular see: http://play.golang.org/p/V5dV02wrix
Assembly I get from the ssa interpreter for that is:  
    i = local int64                                                  *int64
    *i = 1:int64
    u = local uint64                                                *uint64
    *u = 4294967296:uint64
    x = local int64                                                  *int64
    t0 = *i                                                           int64
    t1 = *u                                                          uint64
    t2 = t0 << t1                                                     int64
    *x = t2
    t3 = *x                                                           int64
    t4 = t3 != 0:int64                                                 bool
Which fails while go run succeeds. Is this what you get?

Comment 18 by rocky.bernstein:

Yes 32 bit: 
go version go1.1.1 linux/386
thanks.

Comment 19:

Sorry, careless error: it's not safe to assume the high 32 bits of the shift are zero,
which I did on 386.
I just mailed out https://golang.org/cl/11023043 for a fix.