src/go/types/expr.go

   1 // REVIEW INCOMPLETE
   2 // Copyright 2012 The Go Authors. All rights reserved.
   3 // Use of this source code is governed by a BSD-style
   4 // license that can be found in the LICENSE file.
   5
   6 // This file implements typechecking of expressions.
   7
   8 package types
   9
  10 import (
  11         "fmt"
  12         "go/ast"
  13         "go/constant"
  14         "go/token"
  15         "math"
  16 )
  17
  18 /*
  19 Basic algorithm:
  20
  21 Expressions are checked recursively, top down. Expression checker functions
  22 are generally of the form:
  23
  24   func f(x *operand, e *ast.Expr, ...)
  25
  26 where e is the expression to be checked, and x is the result of the check.
  27 The check performed by f may fail in which case x.mode == invalid, and
  28 related error messages will have been issued by f.
  29
  30 If a hint argument is present, it is the composite literal element type
  31 of an outer composite literal; it is used to type-check composite literal
  32 elements that have no explicit type specification in the source
  33 (e.g.: []T{{...}, {...}}, the hint is the type T in this case).
  34
  35 All expressions are checked via rawExpr, which dispatches according
  36 to expression kind. Upon returning, rawExpr is recording the types and
  37 constant values for all expressions that have an untyped type (those types
  38 may change on the way up in the expression tree). Usually these are constants,
  39 but the results of comparisons or non-constant shifts of untyped constants
  40 may also be untyped, but not constant.
  41
  42 Untyped expressions may eventually become fully typed (i.e., not untyped),
  43 typically when the value is assigned to a variable, or is used otherwise.
  44 The updateExprType method is used to record this final type and update
  45 the recorded types: the type-checked expression tree is again traversed down,
  46 and the new type is propagated as needed. Untyped constant expression values
  47 that become fully typed must now be representable by the full type (constant
  48 sub-expression trees are left alone except for their roots). This mechanism
  49 ensures that a client sees the actual (run-time) type an untyped value would
  50 have. It also permits type-checking of lhs shift operands "as if the shift
  51 were not present": when updateExprType visits an untyped lhs shift operand
  52 and assigns it it's final type, that type must be an integer type, and a
  53 constant lhs must be representable as an integer.
  54
  55 When an expression gets its final type, either on the way out from rawExpr,
  56 on the way down in updateExprType, or at the end of the type checker run,
  57 the type (and constant value, if any) is recorded via Info.Types, if present.
  58 */
  59
  60 type opPredicates map[token.Token]func(Type) bool
  61
  62 var unaryOpPredicates opPredicates
  63
  64 func init() {
  65         // Setting unaryOpPredicates in init avoids declaration cycles.
  66         unaryOpPredicates = opPredicates{
  67                 token.ADD: isNumeric,
  68                 token.SUB: isNumeric,
  69                 token.XOR: isInteger,
  70                 token.NOT: isBoolean,
  71         }
  72 }
  73
  74 func (check *Checker) op(m opPredicates, x *operand, op token.Token) bool {
  75         if pred := m[op]; pred != nil {
  76                 if !pred(x.typ) {
  77                         check.invalidOp(x, _UndefinedOp, "operator %s not defined for %s", op, x)
  78                         return false
  79                 }
  80         } else {
  81                 check.invalidAST(x, "unknown operator %s", op)
  82                 return false
  83         }
  84         return true
  85 }
  86
  87 // The unary expression e may be nil. It's passed in for better error messages only.
  88 func (check *Checker) unary(x *operand, e *ast.UnaryExpr, op token.Token) {
  89         switch op {
  90         case token.AND:
  91                 // spec: "As an exception to the addressability
  92                 // requirement x may also be a composite literal."
  93                 if _, ok := unparen(x.expr).(*ast.CompositeLit); !ok && x.mode != variable {
  94                         check.invalidOp(x, _UnaddressableOperand, "cannot take address of %s", x)
  95                         x.mode = invalid
  96                         return
  97                 }
  98                 x.mode = value
  99                 x.typ = &Pointer{base: x.typ}
 100                 return
 101
 102         case token.ARROW:
 103                 typ := asChan(x.typ)
 104                 if typ == nil {
 105                         check.invalidOp(x, _InvalidReceive, "cannot receive from non-channel %s", x)
 106                         x.mode = invalid
 107                         return
 108                 }
 109                 if typ.dir == SendOnly {
 110                         check.invalidOp(x, _InvalidReceive, "cannot receive from send-only channel %s", x)
 111                         x.mode = invalid
 112                         return
 113                 }
 114                 x.mode = commaok
 115                 x.typ = typ.elem
 116                 check.hasCallOrRecv = true
 117                 return
 118         }
 119
 120         if !check.op(unaryOpPredicates, x, op) {
 121                 x.mode = invalid
 122                 return
 123         }
 124
 125         if x.mode == constant_ {
 126                 typ := asBasic(x.typ)
 127                 var prec uint
 128                 if isUnsigned(typ) {
 129                         prec = uint(check.conf.sizeof(typ) * 8)
 130                 }
 131                 x.val = constant.UnaryOp(op, x.val, prec)
 132                 // Typed constants must be representable in
 133                 // their type after each constant operation.
 134                 if isTyped(typ) {
 135                         if e != nil {
 136                                 x.expr = e // for better error message
 137                         }
 138                         check.representable(x, typ)
 139                 }
 140                 return
 141         }
 142
 143         x.mode = value
 144         // x.typ remains unchanged
 145 }
 146
 147 func isShift(op token.Token) bool {
 148         return op == token.SHL || op == token.SHR
 149 }
 150
 151 func isComparison(op token.Token) bool {
 152         // Note: tokens are not ordered well to make this much easier
 153         switch op {
 154         case token.EQL, token.NEQ, token.LSS, token.LEQ, token.GTR, token.GEQ:
 155                 return true
 156         }
 157         return false
 158 }
 159
 160 func fitsFloat32(x constant.Value) bool {
 161         f32, _ := constant.Float32Val(x)
 162         f := float64(f32)
 163         return !math.IsInf(f, 0)
 164 }
 165
 166 func roundFloat32(x constant.Value) constant.Value {
 167         f32, _ := constant.Float32Val(x)
 168         f := float64(f32)
 169         if !math.IsInf(f, 0) {
 170                 return constant.MakeFloat64(f)
 171         }
 172         return nil
 173 }
 174
 175 func fitsFloat64(x constant.Value) bool {
 176         f, _ := constant.Float64Val(x)
 177         return !math.IsInf(f, 0)
 178 }
 179
 180 func roundFloat64(x constant.Value) constant.Value {
 181         f, _ := constant.Float64Val(x)
 182         if !math.IsInf(f, 0) {
 183                 return constant.MakeFloat64(f)
 184         }
 185         return nil
 186 }
 187
 188 // representableConst reports whether x can be represented as
 189 // value of the given basic type and for the configuration
 190 // provided (only needed for int/uint sizes).
 191 //
 192 // If rounded != nil, *rounded is set to the rounded value of x for
 193 // representable floating-point and complex values, and to an Int
 194 // value for integer values; it is left alone otherwise.
 195 // It is ok to provide the addressof the first argument for rounded.
 196 //
 197 // The check parameter may be nil if representableConst is invoked
 198 // (indirectly) through an exported API call (AssignableTo, ConvertibleTo)
 199 // because we don't need the Checker's config for those calls.
 200 func representableConst(x constant.Value, check *Checker, typ *Basic, rounded *constant.Value) bool {
 201         if x.Kind() == constant.Unknown {
 202                 return true // avoid follow-up errors
 203         }
 204
 205         var conf *Config
 206         if check != nil {
 207                 conf = check.conf
 208         }
 209
 210         switch {
 211         case isInteger(typ):
 212                 x := constant.ToInt(x)
 213                 if x.Kind() != constant.Int {
 214                         return false
 215                 }
 216                 if rounded != nil {
 217                         *rounded = x
 218                 }
 219                 if x, ok := constant.Int64Val(x); ok {
 220                         switch typ.kind {
 221                         case Int:
 222                                 var s = uint(conf.sizeof(typ)) * 8
 223                                 return int64(-1)<<(s-1) <= x && x <= int64(1)<<(s-1)-1
 224                         case Int8:
 225                                 const s = 8
 226                                 return -1<<(s-1) <= x && x <= 1<<(s-1)-1
 227                         case Int16:
 228                                 const s = 16
 229                                 return -1<<(s-1) <= x && x <= 1<<(s-1)-1
 230                         case Int32:
 231                                 const s = 32
 232                                 return -1<<(s-1) <= x && x <= 1<<(s-1)-1
 233                         case Int64, UntypedInt:
 234                                 return true
 235                         case Uint, Uintptr:
 236                                 if s := uint(conf.sizeof(typ)) * 8; s < 64 {
 237                                         return 0 <= x && x <= int64(1)<<s-1
 238                                 }
 239                                 return 0 <= x
 240                         case Uint8:
 241                                 const s = 8
 242                                 return 0 <= x && x <= 1<<s-1
 243                         case Uint16:
 244                                 const s = 16
 245                                 return 0 <= x && x <= 1<<s-1
 246                         case Uint32:
 247                                 const s = 32
 248                                 return 0 <= x && x <= 1<<s-1
 249                         case Uint64:
 250                                 return 0 <= x
 251                         default:
 252                                 unreachable()
 253                         }
 254                 }
 255                 // x does not fit into int64
 256                 switch n := constant.BitLen(x); typ.kind {
 257                 case Uint, Uintptr:
 258                         var s = uint(conf.sizeof(typ)) * 8
 259                         return constant.Sign(x) >= 0 && n <= int(s)
 260                 case Uint64:
 261                         return constant.Sign(x) >= 0 && n <= 64
 262                 case UntypedInt:
 263                         return true
 264                 }
 265
 266         case isFloat(typ):
 267                 x := constant.ToFloat(x)
 268                 if x.Kind() != constant.Float {
 269                         return false
 270                 }
 271                 switch typ.kind {
 272                 case Float32:
 273                         if rounded == nil {
 274                                 return fitsFloat32(x)
 275                         }
 276                         r := roundFloat32(x)
 277                         if r != nil {
 278                                 *rounded = r
 279                                 return true
 280                         }
 281                 case Float64:
 282                         if rounded == nil {
 283                                 return fitsFloat64(x)
 284                         }
 285                         r := roundFloat64(x)
 286                         if r != nil {
 287                                 *rounded = r
 288                                 return true
 289                         }
 290                 case UntypedFloat:
 291                         return true
 292                 default:
 293                         unreachable()
 294                 }
 295
 296         case isComplex(typ):
 297                 x := constant.ToComplex(x)
 298                 if x.Kind() != constant.Complex {
 299                         return false
 300                 }
 301                 switch typ.kind {
 302                 case Complex64:
 303                         if rounded == nil {
 304                                 return fitsFloat32(constant.Real(x)) && fitsFloat32(constant.Imag(x))
 305                         }
 306                         re := roundFloat32(constant.Real(x))
 307                         im := roundFloat32(constant.Imag(x))
 308                         if re != nil && im != nil {
 309                                 *rounded = constant.BinaryOp(re, token.ADD, constant.MakeImag(im))
 310                                 return true
 311                         }
 312                 case Complex128:
 313                         if rounded == nil {
 314                                 return fitsFloat64(constant.Real(x)) && fitsFloat64(constant.Imag(x))
 315                         }
 316                         re := roundFloat64(constant.Real(x))
 317                         im := roundFloat64(constant.Imag(x))
 318                         if re != nil && im != nil {
 319                                 *rounded = constant.BinaryOp(re, token.ADD, constant.MakeImag(im))
 320                                 return true
 321                         }
 322                 case UntypedComplex:
 323                         return true
 324                 default:
 325                         unreachable()
 326                 }
 327
 328         case isString(typ):
 329                 return x.Kind() == constant.String
 330
 331         case isBoolean(typ):
 332                 return x.Kind() == constant.Bool
 333         }
 334
 335         return false
 336 }
 337
 338 // representable checks that a constant operand is representable in the given
 339 // basic type.
 340 func (check *Checker) representable(x *operand, typ *Basic) {
 341         if v, code := check.representation(x, typ); code != 0 {
 342                 check.invalidConversion(code, x, typ)
 343                 x.mode = invalid
 344         } else if v != nil {
 345                 x.val = v
 346         }
 347 }
 348
 349 func (check *Checker) representation(x *operand, typ *Basic) (constant.Value, errorCode) {
 350         assert(x.mode == constant_)
 351         v := x.val
 352         if !representableConst(x.val, check, typ, &v) {
 353                 if isNumeric(x.typ) && isNumeric(typ) {
 354                         // numeric conversion : error msg
 355                         //
 356                         // integer -> integer : overflows
 357                         // integer -> float   : overflows (actually not possible)
 358                         // float   -> integer : truncated
 359                         // float   -> float   : overflows
 360                         //
 361                         if !isInteger(x.typ) && isInteger(typ) {
 362                                 return nil, _TruncatedFloat
 363                         } else {
 364                                 return nil, _NumericOverflow
 365                         }
 366                 }
 367                 return nil, _InvalidConstVal
 368         }
 369         return v, 0
 370 }
 371
 372 func (check *Checker) invalidConversion(code errorCode, x *operand, target Type) {
 373         msg := "cannot convert %s to %s"
 374         switch code {
 375         case _TruncatedFloat:
 376                 msg = "%s truncated to %s"
 377         case _NumericOverflow:
 378                 msg = "%s overflows %s"
 379         }
 380         check.errorf(x, code, msg, x, target)
 381 }
 382
 383 // updateExprType updates the type of x to typ and invokes itself
 384 // recursively for the operands of x, depending on expression kind.
 385 // If typ is still an untyped and not the final type, updateExprType
 386 // only updates the recorded untyped type for x and possibly its
 387 // operands. Otherwise (i.e., typ is not an untyped type anymore,
 388 // or it is the final type for x), the type and value are recorded.
 389 // Also, if x is a constant, it must be representable as a value of typ,
 390 // and if x is the (formerly untyped) lhs operand of a non-constant
 391 // shift, it must be an integer value.
 392 //
 393 func (check *Checker) updateExprType(x ast.Expr, typ Type, final bool) {
 394         old, found := check.untyped[x]
 395         if !found {
 396                 return // nothing to do
 397         }
 398
 399         // update operands of x if necessary
 400         switch x := x.(type) {
 401         case *ast.BadExpr,
 402                 *ast.FuncLit,
 403                 *ast.CompositeLit,
 404                 *ast.IndexExpr,
 405                 *ast.SliceExpr,
 406                 *ast.TypeAssertExpr,
 407                 *ast.StarExpr,
 408                 *ast.KeyValueExpr,
 409                 *ast.ArrayType,
 410                 *ast.StructType,
 411                 *ast.FuncType,
 412                 *ast.InterfaceType,
 413                 *ast.MapType,
 414                 *ast.ChanType:
 415                 // These expression are never untyped - nothing to do.
 416                 // The respective sub-expressions got their final types
 417                 // upon assignment or use.
 418                 if debug {
 419                         check.dump("%v: found old type(%s): %s (new: %s)", x.Pos(), x, old.typ, typ)
 420                         unreachable()
 421                 }
 422                 return
 423
 424         case *ast.CallExpr:
 425                 // Resulting in an untyped constant (e.g., built-in complex).
 426                 // The respective calls take care of calling updateExprType
 427                 // for the arguments if necessary.
 428
 429         case *ast.Ident, *ast.BasicLit, *ast.SelectorExpr:
 430                 // An identifier denoting a constant, a constant literal,
 431                 // or a qualified identifier (imported untyped constant).
 432                 // No operands to take care of.
 433
 434         case *ast.ParenExpr:
 435                 check.updateExprType(x.X, typ, final)
 436
 437         case *ast.UnaryExpr:
 438                 // If x is a constant, the operands were constants.
 439                 // The operands don't need to be updated since they
 440                 // never get "materialized" into a typed value. If
 441                 // left in the untyped map, they will be processed
 442                 // at the end of the type check.
 443                 if old.val != nil {
 444                         break
 445                 }
 446                 check.updateExprType(x.X, typ, final)
 447
 448         case *ast.BinaryExpr:
 449                 if old.val != nil {
 450                         break // see comment for unary expressions
 451                 }
 452                 if isComparison(x.Op) {
 453                         // The result type is independent of operand types
 454                         // and the operand types must have final types.
 455                 } else if isShift(x.Op) {
 456                         // The result type depends only on lhs operand.
 457                         // The rhs type was updated when checking the shift.
 458                         check.updateExprType(x.X, typ, final)
 459                 } else {
 460                         // The operand types match the result type.
 461                         check.updateExprType(x.X, typ, final)
 462                         check.updateExprType(x.Y, typ, final)
 463                 }
 464
 465         default:
 466                 unreachable()
 467         }
 468
 469         // If the new type is not final and still untyped, just
 470         // update the recorded type.
 471         if !final && isUntyped(typ) {
 472                 old.typ = asBasic(typ)
 473                 check.untyped[x] = old
 474                 return
 475         }
 476
 477         // Otherwise we have the final (typed or untyped type).
 478         // Remove it from the map of yet untyped expressions.
 479         delete(check.untyped, x)
 480
 481         if old.isLhs {
 482                 // If x is the lhs of a shift, its final type must be integer.
 483                 // We already know from the shift check that it is representable
 484                 // as an integer if it is a constant.
 485                 if !isInteger(typ) {
 486                         check.invalidOp(x, _InvalidShiftOperand, "shifted operand %s (type %s) must be integer", x, typ)
 487                         return
 488                 }
 489                 // Even if we have an integer, if the value is a constant we
 490                 // still must check that it is representable as the specific
 491                 // int type requested (was issue #22969). Fall through here.
 492         }
 493         if old.val != nil {
 494                 // If x is a constant, it must be representable as a value of typ.
 495                 c := operand{old.mode, x, old.typ, old.val, 0}
 496                 check.convertUntyped(&c, typ)
 497                 if c.mode == invalid {
 498                         return
 499                 }
 500         }
 501
 502         // Everything's fine, record final type and value for x.
 503         check.recordTypeAndValue(x, old.mode, typ, old.val)
 504 }
 505
 506 // updateExprVal updates the value of x to val.
 507 func (check *Checker) updateExprVal(x ast.Expr, val constant.Value) {
 508         if info, ok := check.untyped[x]; ok {
 509                 info.val = val
 510                 check.untyped[x] = info
 511         }
 512 }
 513
 514 // convertUntyped attempts to set the type of an untyped value to the target type.
 515 func (check *Checker) convertUntyped(x *operand, target Type) {
 516         newType, val, code := check.implicitTypeAndValue(x, target)
 517         if code != 0 {
 518                 check.invalidConversion(code, x, target.Underlying())
 519                 x.mode = invalid
 520                 return
 521         }
 522         if val != nil {
 523                 x.val = val
 524                 check.updateExprVal(x.expr, val)
 525         }
 526         if newType != x.typ {
 527                 x.typ = newType
 528                 check.updateExprType(x.expr, newType, false)
 529         }
 530 }
 531
 532 // implicitTypeAndValue returns the implicit type of x when used in a context
 533 // where the target type is expected. If no such implicit conversion is
 534 // possible, it returns a nil Type.
 535 func (check *Checker) implicitTypeAndValue(x *operand, target Type) (Type, constant.Value, errorCode) {
 536         target = expand(target)
 537         if x.mode == invalid || isTyped(x.typ) || target == Typ[Invalid] {
 538                 return x.typ, nil, 0
 539         }
 540
 541         if isUntyped(target) {
 542                 // both x and target are untyped
 543                 xkind := x.typ.(*Basic).kind
 544                 tkind := target.(*Basic).kind
 545                 if isNumeric(x.typ) && isNumeric(target) {
 546                         if xkind < tkind {
 547                                 return target, nil, 0
 548                         }
 549                 } else if xkind != tkind {
 550                         return nil, nil, _InvalidUntypedConversion
 551                 }
 552                 return x.typ, nil, 0
 553         }
 554
 555         switch t := optype(target).(type) {
 556         case *Basic:
 557                 if x.mode == constant_ {
 558                         v, code := check.representation(x, t)
 559                         if code != 0 {
 560                                 return nil, nil, code
 561                         }
 562                         return target, v, code
 563                 }
 564                 // Non-constant untyped values may appear as the
 565                 // result of comparisons (untyped bool), intermediate
 566                 // (delayed-checked) rhs operands of shifts, and as
 567                 // the value nil.
 568                 switch x.typ.(*Basic).kind {
 569                 case UntypedBool:
 570                         if !isBoolean(target) {
 571                                 return nil, nil, _InvalidUntypedConversion
 572                         }
 573                 case UntypedInt, UntypedRune, UntypedFloat, UntypedComplex:
 574                         if !isNumeric(target) {
 575                                 return nil, nil, _InvalidUntypedConversion
 576                         }
 577                 case UntypedString:
 578                         // Non-constant untyped string values are not permitted by the spec and
 579                         // should not occur during normal typechecking passes, but this path is
 580                         // reachable via the AssignableTo API.
 581                         if !isString(target) {
 582                                 return nil, nil, _InvalidUntypedConversion
 583                         }
 584                 case UntypedNil:
 585                         // Unsafe.Pointer is a basic type that includes nil.
 586                         if !hasNil(target) {
 587                                 return nil, nil, _InvalidUntypedConversion
 588                         }
 589                         // TODO(rFindley) return UntypedNil here (golang.org/issues/13061).
 590                 default:
 591                         return nil, nil, _InvalidUntypedConversion
 592                 }
 593         case *Sum:
 594                 ok := t.is(func(t Type) bool {
 595                         target, _, _ := check.implicitTypeAndValue(x, t)
 596                         return target != nil
 597                 })
 598                 if !ok {
 599                         return nil, nil, _InvalidUntypedConversion
 600                 }
 601                 // keep nil untyped (was bug #39755)
 602                 if x.isNil() {
 603                         return Typ[UntypedNil], nil, 0
 604                 }
 605         case *Interface:
 606                 // Values must have concrete dynamic types. If the value is nil,
 607                 // keep it untyped (this is important for tools such as go vet which
 608                 // need the dynamic type for argument checking of say, print
 609                 // functions)
 610                 if x.isNil() {
 611                         return Typ[UntypedNil], nil, 0
 612                 }
 613                 // cannot assign untyped values to non-empty interfaces
 614                 check.completeInterface(token.NoPos, t)
 615                 if !t.Empty() {
 616                         return nil, nil, _InvalidUntypedConversion
 617                 }
 618                 return Default(x.typ), nil, 0
 619         case *Pointer, *Signature, *Slice, *Map, *Chan:
 620                 if !x.isNil() {
 621                         return nil, nil, _InvalidUntypedConversion
 622                 }
 623                 // Keep nil untyped - see comment for interfaces, above.
 624                 return Typ[UntypedNil], nil, 0
 625         default:
 626                 return nil, nil, _InvalidUntypedConversion
 627         }
 628         return target, nil, 0
 629 }
 630
 631 func (check *Checker) comparison(x, y *operand, op token.Token) {
 632         // spec: "In any comparison, the first operand must be assignable
 633         // to the type of the second operand, or vice versa."
 634         err := ""
 635         var code errorCode
 636         xok, _ := x.assignableTo(check, y.typ, nil)
 637         yok, _ := y.assignableTo(check, x.typ, nil)
 638         if xok || yok {
 639                 defined := false
 640                 switch op {
 641                 case token.EQL, token.NEQ:
 642                         // spec: "The equality operators == and != apply to operands that are comparable."
 643                         defined = Comparable(x.typ) && Comparable(y.typ) || x.isNil() && hasNil(y.typ) || y.isNil() && hasNil(x.typ)
 644                 case token.LSS, token.LEQ, token.GTR, token.GEQ:
 645                         // spec: The ordering operators <, <=, >, and >= apply to operands that are ordered."
 646                         defined = isOrdered(x.typ) && isOrdered(y.typ)
 647                 default:
 648                         unreachable()
 649                 }
 650                 if !defined {
 651                         typ := x.typ
 652                         if x.isNil() {
 653                                 typ = y.typ
 654                         }
 655                         err = check.sprintf("operator %s not defined for %s", op, typ)
 656                         code = _UndefinedOp
 657                 }
 658         } else {
 659                 err = check.sprintf("mismatched types %s and %s", x.typ, y.typ)
 660                 code = _MismatchedTypes
 661         }
 662
 663         if err != "" {
 664                 check.errorf(x, code, "cannot compare %s %s %s (%s)", x.expr, op, y.expr, err)
 665                 x.mode = invalid
 666                 return
 667         }
 668
 669         if x.mode == constant_ && y.mode == constant_ {
 670                 x.val = constant.MakeBool(constant.Compare(x.val, op, y.val))
 671                 // The operands are never materialized; no need to update
 672                 // their types.
 673         } else {
 674                 x.mode = value
 675                 // The operands have now their final types, which at run-
 676                 // time will be materialized. Update the expression trees.
 677                 // If the current types are untyped, the materialized type
 678                 // is the respective default type.
 679                 check.updateExprType(x.expr, Default(x.typ), true)
 680                 check.updateExprType(y.expr, Default(y.typ), true)
 681         }
 682
 683         // spec: "Comparison operators compare two operands and yield
 684         //        an untyped boolean value."
 685         x.typ = Typ[UntypedBool]
 686 }
 687
 688 func (check *Checker) shift(x, y *operand, e *ast.BinaryExpr, op token.Token) {
 689         untypedx := isUntyped(x.typ)
 690
 691         var xval constant.Value
 692         if x.mode == constant_ {
 693                 xval = constant.ToInt(x.val)
 694         }
 695
 696         if isInteger(x.typ) || untypedx && xval != nil && xval.Kind() == constant.Int {
 697                 // The lhs is of integer type or an untyped constant representable
 698                 // as an integer. Nothing to do.
 699         } else {
 700                 // shift has no chance
 701                 check.invalidOp(x, _InvalidShiftOperand, "shifted operand %s must be integer", x)
 702                 x.mode = invalid
 703                 return
 704         }
 705
 706         // spec: "The right operand in a shift expression must have integer type
 707         // or be an untyped constant representable by a value of type uint."
 708         switch {
 709         case isInteger(y.typ):
 710                 // nothing to do
 711         case isUntyped(y.typ):
 712                 check.convertUntyped(y, Typ[Uint])
 713                 if y.mode == invalid {
 714                         x.mode = invalid
 715                         return
 716                 }
 717         default:
 718                 check.invalidOp(y, _InvalidShiftCount, "shift count %s must be integer", y)
 719                 x.mode = invalid
 720                 return
 721         }
 722
 723         var yval constant.Value
 724         if y.mode == constant_ {
 725                 // rhs must be an integer value
 726                 // (Either it was of an integer type already, or it was
 727                 // untyped and successfully converted to a uint above.)
 728                 yval = constant.ToInt(y.val)
 729                 assert(yval.Kind() == constant.Int)
 730                 if constant.Sign(yval) < 0 {
 731                         check.invalidOp(y, _InvalidShiftCount, "negative shift count %s", y)
 732                         x.mode = invalid
 733                         return
 734                 }
 735         }
 736
 737         if x.mode == constant_ {
 738                 if y.mode == constant_ {
 739                         // rhs must be within reasonable bounds in constant shifts
 740                         const shiftBound = 1023 - 1 + 52 // so we can express smallestFloat64
 741                         s, ok := constant.Uint64Val(yval)
 742                         if !ok || s > shiftBound {
 743                                 check.invalidOp(y, _InvalidShiftCount, "invalid shift count %s", y)
 744                                 x.mode = invalid
 745                                 return
 746                         }
 747                         // The lhs is representable as an integer but may not be an integer
 748                         // (e.g., 2.0, an untyped float) - this can only happen for untyped
 749                         // non-integer numeric constants. Correct the type so that the shift
 750                         // result is of integer type.
 751                         if !isInteger(x.typ) {
 752                                 x.typ = Typ[UntypedInt]
 753                         }
 754                         // x is a constant so xval != nil and it must be of Int kind.
 755                         x.val = constant.Shift(xval, op, uint(s))
 756                         // Typed constants must be representable in
 757                         // their type after each constant operation.
 758                         if isTyped(x.typ) {
 759                                 if e != nil {
 760                                         x.expr = e // for better error message
 761                                 }
 762                                 check.representable(x, asBasic(x.typ))
 763                         }
 764                         return
 765                 }
 766
 767                 // non-constant shift with constant lhs
 768                 if untypedx {
 769                         // spec: "If the left operand of a non-constant shift
 770                         // expression is an untyped constant, the type of the
 771                         // constant is what it would be if the shift expression
 772                         // were replaced by its left operand alone.".
 773                         //
 774                         // Delay operand checking until we know the final type
 775                         // by marking the lhs expression as lhs shift operand.
 776                         //
 777                         // Usually (in correct programs), the lhs expression
 778                         // is in the untyped map. However, it is possible to
 779                         // create incorrect programs where the same expression
 780                         // is evaluated twice (via a declaration cycle) such
 781                         // that the lhs expression type is determined in the
 782                         // first round and thus deleted from the map, and then
 783                         // not found in the second round (double insertion of
 784                         // the same expr node still just leads to one entry for
 785                         // that node, and it can only be deleted once).
 786                         // Be cautious and check for presence of entry.
 787                         // Example: var e, f = int(1<<""[f]) // issue 11347
 788                         if info, found := check.untyped[x.expr]; found {
 789                                 info.isLhs = true
 790                                 check.untyped[x.expr] = info
 791                         }
 792                         // keep x's type
 793                         x.mode = value
 794                         return
 795                 }
 796         }
 797
 798         // non-constant shift - lhs must be an integer
 799         if !isInteger(x.typ) {
 800                 check.invalidOp(x, _InvalidShiftOperand, "shifted operand %s must be integer", x)
 801                 x.mode = invalid
 802                 return
 803         }
 804
 805         x.mode = value
 806 }
 807
 808 var binaryOpPredicates opPredicates
 809
 810 func init() {
 811         // Setting binaryOpPredicates in init avoids declaration cycles.
 812         binaryOpPredicates = opPredicates{
 813                 token.ADD: isNumericOrString,
 814                 token.SUB: isNumeric,
 815                 token.MUL: isNumeric,
 816                 token.QUO: isNumeric,
 817                 token.REM: isInteger,
 818
 819                 token.AND:     isInteger,
 820                 token.OR:      isInteger,
 821                 token.XOR:     isInteger,
 822                 token.AND_NOT: isInteger,
 823
 824                 token.LAND: isBoolean,
 825                 token.LOR:  isBoolean,
 826         }
 827 }
 828
 829 // The binary expression e may be nil. It's passed in for better error messages only.
 830 func (check *Checker) binary(x *operand, e *ast.BinaryExpr, lhs, rhs ast.Expr, op token.Token, opPos token.Pos) {
 831         var y operand
 832
 833         check.expr(x, lhs)
 834         check.expr(&y, rhs)
 835
 836         if x.mode == invalid {
 837                 return
 838         }
 839         if y.mode == invalid {
 840                 x.mode = invalid
 841                 x.expr = y.expr
 842                 return
 843         }
 844
 845         if isShift(op) {
 846                 check.shift(x, &y, e, op)
 847                 return
 848         }
 849
 850         check.convertUntyped(x, y.typ)
 851         if x.mode == invalid {
 852                 return
 853         }
 854         check.convertUntyped(&y, x.typ)
 855         if y.mode == invalid {
 856                 x.mode = invalid
 857                 return
 858         }
 859
 860         if isComparison(op) {
 861                 check.comparison(x, &y, op)
 862                 return
 863         }
 864
 865         if !check.identical(x.typ, y.typ) {
 866                 // only report an error if we have valid types
 867                 // (otherwise we had an error reported elsewhere already)
 868                 if x.typ != Typ[Invalid] && y.typ != Typ[Invalid] {
 869                         var posn positioner = x
 870                         if e != nil {
 871                                 posn = e
 872                         }
 873                         check.invalidOp(posn, _MismatchedTypes, "mismatched types %s and %s", x.typ, y.typ)
 874                 }
 875                 x.mode = invalid
 876                 return
 877         }
 878
 879         if !check.op(binaryOpPredicates, x, op) {
 880                 x.mode = invalid
 881                 return
 882         }
 883
 884         if op == token.QUO || op == token.REM {
 885                 // check for zero divisor
 886                 if (x.mode == constant_ || isInteger(x.typ)) && y.mode == constant_ && constant.Sign(y.val) == 0 {
 887                         check.invalidOp(&y, _DivByZero, "division by zero")
 888                         x.mode = invalid
 889                         return
 890                 }
 891
 892                 // check for divisor underflow in complex division (see issue 20227)
 893                 if x.mode == constant_ && y.mode == constant_ && isComplex(x.typ) {
 894                         re, im := constant.Real(y.val), constant.Imag(y.val)
 895                         re2, im2 := constant.BinaryOp(re, token.MUL, re), constant.BinaryOp(im, token.MUL, im)
 896                         if constant.Sign(re2) == 0 && constant.Sign(im2) == 0 {
 897                                 check.invalidOp(&y, _DivByZero, "division by zero")
 898                                 x.mode = invalid
 899                                 return
 900                         }
 901                 }
 902         }
 903
 904         if x.mode == constant_ && y.mode == constant_ {
 905                 xval := x.val
 906                 yval := y.val
 907                 typ := asBasic(x.typ)
 908                 // force integer division of integer operands
 909                 if op == token.QUO && isInteger(typ) {
 910                         op = token.QUO_ASSIGN
 911                 }
 912                 x.val = constant.BinaryOp(xval, op, yval)
 913                 // report error if valid operands lead to an invalid result
 914                 if xval.Kind() != constant.Unknown && yval.Kind() != constant.Unknown && x.val.Kind() == constant.Unknown {
 915                         // TODO(gri) We should report exactly what went wrong. At the
 916                         //           moment we don't have the (go/constant) API for that.
 917                         //           See also TODO in go/constant/value.go.
 918                         check.errorf(atPos(opPos), _InvalidConstVal, "constant result is not representable")
 919                         // TODO(gri) Should we mark operands with unknown values as invalid?
 920                 }
 921                 // Typed constants must be representable in
 922                 // their type after each constant operation.
 923                 if isTyped(typ) {
 924                         if e != nil {
 925                                 x.expr = e // for better error message
 926                         }
 927                         check.representable(x, typ)
 928                 }
 929                 return
 930         }
 931
 932         x.mode = value
 933         // x.typ is unchanged
 934 }
 935
 936 // index checks an index expression for validity.
 937 // If max >= 0, it is the upper bound for index.
 938 // If the result typ is != Typ[Invalid], index is valid and typ is its (possibly named) integer type.
 939 // If the result val >= 0, index is valid and val is its constant int value.
 940 func (check *Checker) index(index ast.Expr, max int64) (typ Type, val int64) {
 941         typ = Typ[Invalid]
 942         val = -1
 943
 944         var x operand
 945         check.expr(&x, index)
 946         if x.mode == invalid {
 947                 return
 948         }
 949
 950         // an untyped constant must be representable as Int
 951         check.convertUntyped(&x, Typ[Int])
 952         if x.mode == invalid {
 953                 return
 954         }
 955
 956         // the index must be of integer type
 957         if !isInteger(x.typ) {
 958                 check.invalidArg(&x, _InvalidIndex, "index %s must be integer", &x)
 959                 return
 960         }
 961
 962         if x.mode != constant_ {
 963                 return x.typ, -1
 964         }
 965
 966         // a constant index i must be in bounds
 967         if constant.Sign(x.val) < 0 {
 968                 check.invalidArg(&x, _InvalidIndex, "index %s must not be negative", &x)
 969                 return
 970         }
 971
 972         v, valid := constant.Int64Val(constant.ToInt(x.val))
 973         if !valid || max >= 0 && v >= max {
 974                 check.errorf(&x, _InvalidIndex, "index %s is out of bounds", &x)
 975                 return
 976         }
 977
 978         // 0 <= v [ && v < max ]
 979         return Typ[Int], v
 980 }
 981
 982 // indexElts checks the elements (elts) of an array or slice composite literal
 983 // against the literal's element type (typ), and the element indices against
 984 // the literal length if known (length >= 0). It returns the length of the
 985 // literal (maximum index value + 1).
 986 //
 987 func (check *Checker) indexedElts(elts []ast.Expr, typ Type, length int64) int64 {
 988         visited := make(map[int64]bool, len(elts))
 989         var index, max int64
 990         for _, e := range elts {
 991                 // determine and check index
 992                 validIndex := false
 993                 eval := e
 994                 if kv, _ := e.(*ast.KeyValueExpr); kv != nil {
 995                         if typ, i := check.index(kv.Key, length); typ != Typ[Invalid] {
 996                                 if i >= 0 {
 997                                         index = i
 998                                         validIndex = true
 999                                 } else {
1000                                         check.errorf(e, _InvalidLitIndex, "index %s must be integer constant", kv.Key)
1001                                 }
1002                         }
1003                         eval = kv.Value
1004                 } else if length >= 0 && index >= length {
1005                         check.errorf(e, _OversizeArrayLit, "index %d is out of bounds (>= %d)", index, length)
1006                 } else {
1007                         validIndex = true
1008                 }
1009
1010                 // if we have a valid index, check for duplicate entries
1011                 if validIndex {
1012                         if visited[index] {
1013                                 check.errorf(e, _DuplicateLitKey, "duplicate index %d in array or slice literal", index)
1014                         }
1015                         visited[index] = true
1016                 }
1017                 index++
1018                 if index > max {
1019                         max = index
1020                 }
1021
1022                 // check element against composite literal element type
1023                 var x operand
1024                 check.exprWithHint(&x, eval, typ)
1025                 check.assignment(&x, typ, "array or slice literal")
1026         }
1027         return max
1028 }
1029
1030 // exprKind describes the kind of an expression; the kind
1031 // determines if an expression is valid in 'statement context'.
1032 type exprKind int
1033
1034 const (
1035         conversion exprKind = iota
1036         expression
1037         statement
1038 )
1039
1040 // rawExpr typechecks expression e and initializes x with the expression
1041 // value or type. If an error occurred, x.mode is set to invalid.
1042 // If hint != nil, it is the type of a composite literal element.
1043 //
1044 func (check *Checker) rawExpr(x *operand, e ast.Expr, hint Type) exprKind {
1045         if trace {
1046                 check.trace(e.Pos(), "expr %s", e)
1047                 check.indent++
1048                 defer func() {
1049                         check.indent--
1050                         check.trace(e.Pos(), "=> %s", x)
1051                 }()
1052         }
1053
1054         kind := check.exprInternal(x, e, hint)
1055
1056         // convert x into a user-friendly set of values
1057         // TODO(gri) this code can be simplified
1058         var typ Type
1059         var val constant.Value
1060         switch x.mode {
1061         case invalid:
1062                 typ = Typ[Invalid]
1063         case novalue:
1064                 typ = (*Tuple)(nil)
1065         case constant_:
1066                 typ = x.typ
1067                 val = x.val
1068         default:
1069                 typ = x.typ
1070         }
1071         assert(x.expr != nil && typ != nil)
1072
1073         if isUntyped(typ) {
1074                 // delay type and value recording until we know the type
1075                 // or until the end of type checking
1076                 check.rememberUntyped(x.expr, false, x.mode, typ.(*Basic), val)
1077         } else {
1078                 check.recordTypeAndValue(e, x.mode, typ, val)
1079         }
1080
1081         return kind
1082 }
1083
1084 // exprInternal contains the core of type checking of expressions.
1085 // Must only be called by rawExpr.
1086 //
1087 func (check *Checker) exprInternal(x *operand, e ast.Expr, hint Type) exprKind {
1088         // make sure x has a valid state in case of bailout
1089         // (was issue 5770)
1090         x.mode = invalid
1091         x.typ = Typ[Invalid]
1092
1093         switch e := e.(type) {
1094         case *ast.BadExpr:
1095                 goto Error // error was reported before
1096
1097         case *ast.Ident:
1098                 check.ident(x, e, nil, false)
1099
1100         case *ast.Ellipsis:
1101                 // ellipses are handled explicitly where they are legal
1102                 // (array composite literals and parameter lists)
1103                 check.error(e, _BadDotDotDotSyntax, "invalid use of '...'")
1104                 goto Error
1105
1106         case *ast.BasicLit:
1107                 x.setConst(e.Kind, e.Value)
1108                 if x.mode == invalid {
1109                         // The parser already establishes syntactic correctness.
1110                         // If we reach here it's because of number under-/overflow.
1111                         // TODO(gri) setConst (and in turn the go/constant package)
1112                         // should return an error describing the issue.
1113                         check.errorf(e, _InvalidConstVal, "malformed constant: %s", e.Value)
1114                         goto Error
1115                 }
1116
1117         case *ast.FuncLit:
1118                 if sig, ok := check.typ(e.Type).(*Signature); ok {
1119                         // Anonymous functions are considered part of the
1120                         // init expression/func declaration which contains
1121                         // them: use existing package-level declaration info.
1122                         decl := check.decl // capture for use in closure below
1123                         iota := check.iota // capture for use in closure below (#22345)
1124                         // Don't type-check right away because the function may
1125                         // be part of a type definition to which the function
1126                         // body refers. Instead, type-check as soon as possible,
1127                         // but before the enclosing scope contents changes (#22992).
1128                         check.later(func() {
1129                                 check.funcBody(decl, "<function literal>", sig, e.Body, iota)
1130                         })
1131                         x.mode = value
1132                         x.typ = sig
1133                 } else {
1134                         check.invalidAST(e, "invalid function literal %s", e)
1135                         goto Error
1136                 }
1137
1138         case *ast.CompositeLit:
1139                 var typ, base Type
1140
1141                 switch {
1142                 case e.Type != nil:
1143                         // composite literal type present - use it
1144                         // [...]T array types may only appear with composite literals.
1145                         // Check for them here so we don't have to handle ... in general.
1146                         if atyp, _ := e.Type.(*ast.ArrayType); atyp != nil && atyp.Len != nil {
1147                                 if ellip, _ := atyp.Len.(*ast.Ellipsis); ellip != nil && ellip.Elt == nil {
1148                                         // We have an "open" [...]T array type.
1149                                         // Create a new ArrayType with unknown length (-1)
1150                                         // and finish setting it up after analyzing the literal.
1151                                         typ = &Array{len: -1, elem: check.varType(atyp.Elt)}
1152                                         base = typ
1153                                         break
1154                                 }
1155                         }
1156                         typ = check.typ(e.Type)
1157                         base = typ
1158
1159                 case hint != nil:
1160                         // no composite literal type present - use hint (element type of enclosing type)
1161                         typ = hint
1162                         base, _ = deref(under(typ)) // *T implies &T{}
1163
1164                 default:
1165                         // TODO(gri) provide better error messages depending on context
1166                         check.error(e, _UntypedLit, "missing type in composite literal")
1167                         goto Error
1168                 }
1169
1170                 switch utyp := optype(base).(type) {
1171                 case *Struct:
1172                         if len(e.Elts) == 0 {
1173                                 break
1174                         }
1175                         fields := utyp.fields
1176                         if _, ok := e.Elts[0].(*ast.KeyValueExpr); ok {
1177                                 // all elements must have keys
1178                                 visited := make([]bool, len(fields))
1179                                 for _, e := range e.Elts {
1180                                         kv, _ := e.(*ast.KeyValueExpr)
1181                                         if kv == nil {
1182                                                 check.error(e, _MixedStructLit, "mixture of field:value and value elements in struct literal")
1183                                                 continue
1184                                         }
1185                                         key, _ := kv.Key.(*ast.Ident)
1186                                         // do all possible checks early (before exiting due to errors)
1187                                         // so we don't drop information on the floor
1188                                         check.expr(x, kv.Value)
1189                                         if key == nil {
1190                                                 check.errorf(kv, _InvalidLitField, "invalid field name %s in struct literal", kv.Key)
1191                                                 continue
1192                                         }
1193                                         i := fieldIndex(utyp.fields, check.pkg, key.Name)
1194                                         if i < 0 {
1195                                                 check.errorf(kv, _MissingLitField, "unknown field %s in struct literal", key.Name)
1196                                                 continue
1197                                         }
1198                                         fld := fields[i]
1199                                         check.recordUse(key, fld)
1200                                         etyp := fld.typ
1201                                         check.assignment(x, etyp, "struct literal")
1202                                         // 0 <= i < len(fields)
1203                                         if visited[i] {
1204                                                 check.errorf(kv, _DuplicateLitField, "duplicate field name %s in struct literal", key.Name)
1205                                                 continue
1206                                         }
1207                                         visited[i] = true
1208                                 }
1209                         } else {
1210                                 // no element must have a key
1211                                 for i, e := range e.Elts {
1212                                         if kv, _ := e.(*ast.KeyValueExpr); kv != nil {
1213                                                 check.error(kv, _MixedStructLit, "mixture of field:value and value elements in struct literal")
1214                                                 continue
1215                                         }
1216                                         check.expr(x, e)
1217                                         if i >= len(fields) {
1218                                                 check.error(x, _InvalidStructLit, "too many values in struct literal")
1219                                                 break // cannot continue
1220                                         }
1221                                         // i < len(fields)
1222                                         fld := fields[i]
1223                                         if !fld.Exported() && fld.pkg != check.pkg {
1224                                                 check.errorf(x,
1225                                                         _UnexportedLitField,
1226                                                         "implicit assignment to unexported field %s in %s literal", fld.name, typ)
1227                                                 continue
1228                                         }
1229                                         etyp := fld.typ
1230                                         check.assignment(x, etyp, "struct literal")
1231                                 }
1232                                 if len(e.Elts) < len(fields) {
1233                                         check.error(inNode(e, e.Rbrace), _InvalidStructLit, "too few values in struct literal")
1234                                         // ok to continue
1235                                 }
1236                         }
1237
1238                 case *Array:
1239                         // Prevent crash if the array referred to is not yet set up. Was issue #18643.
1240                         // This is a stop-gap solution. Should use Checker.objPath to report entire
1241                         // path starting with earliest declaration in the source. TODO(gri) fix this.
1242                         if utyp.elem == nil {
1243                                 check.error(e, _InvalidTypeCycle, "illegal cycle in type declaration")
1244                                 goto Error
1245                         }
1246                         n := check.indexedElts(e.Elts, utyp.elem, utyp.len)
1247                         // If we have an array of unknown length (usually [...]T arrays, but also
1248                         // arrays [n]T where n is invalid) set the length now that we know it and
1249                         // record the type for the array (usually done by check.typ which is not
1250                         // called for [...]T). We handle [...]T arrays and arrays with invalid
1251                         // length the same here because it makes sense to "guess" the length for
1252                         // the latter if we have a composite literal; e.g. for [n]int{1, 2, 3}
1253                         // where n is invalid for some reason, it seems fair to assume it should
1254                         // be 3 (see also Checked.arrayLength and issue #27346).
1255                         if utyp.len < 0 {
1256                                 utyp.len = n
1257                                 // e.Type is missing if we have a composite literal element
1258                                 // that is itself a composite literal with omitted type. In
1259                                 // that case there is nothing to record (there is no type in
1260                                 // the source at that point).
1261                                 if e.Type != nil {
1262                                         check.recordTypeAndValue(e.Type, typexpr, utyp, nil)
1263                                 }
1264                         }
1265
1266                 case *Slice:
1267                         // Prevent crash if the slice referred to is not yet set up.
1268                         // See analogous comment for *Array.
1269                         if utyp.elem == nil {
1270                                 check.error(e, _InvalidTypeCycle, "illegal cycle in type declaration")
1271                                 goto Error
1272                         }
1273                         check.indexedElts(e.Elts, utyp.elem, -1)
1274
1275                 case *Map:
1276                         // Prevent crash if the map referred to is not yet set up.
1277                         // See analogous comment for *Array.
1278                         if utyp.key == nil || utyp.elem == nil {
1279                                 check.error(e, _InvalidTypeCycle, "illegal cycle in type declaration")
1280                                 goto Error
1281                         }
1282                         visited := make(map[interface{}][]Type, len(e.Elts))
1283                         for _, e := range e.Elts {
1284                                 kv, _ := e.(*ast.KeyValueExpr)
1285                                 if kv == nil {
1286                                         check.error(e, _MissingLitKey, "missing key in map literal")
1287                                         continue
1288                                 }
1289                                 check.exprWithHint(x, kv.Key, utyp.key)
1290                                 check.assignment(x, utyp.key, "map literal")
1291                                 if x.mode == invalid {
1292                                         continue
1293                                 }
1294                                 if x.mode == constant_ {
1295                                         duplicate := false
1296                                         // if the key is of interface type, the type is also significant when checking for duplicates
1297                                         xkey := keyVal(x.val)
1298                                         if asInterface(utyp.key) != nil {
1299                                                 for _, vtyp := range visited[xkey] {
1300                                                         if check.identical(vtyp, x.typ) {
1301                                                                 duplicate = true
1302                                                                 break
1303                                                         }
1304                                                 }
1305                                                 visited[xkey] = append(visited[xkey], x.typ)
1306                                         } else {
1307                                                 _, duplicate = visited[xkey]
1308                                                 visited[xkey] = nil
1309                                         }
1310                                         if duplicate {
1311                                                 check.errorf(x, _DuplicateLitKey, "duplicate key %s in map literal", x.val)
1312                                                 continue
1313                                         }
1314                                 }
1315                                 check.exprWithHint(x, kv.Value, utyp.elem)
1316                                 check.assignment(x, utyp.elem, "map literal")
1317                         }
1318
1319                 default:
1320                         // when "using" all elements unpack KeyValueExpr
1321                         // explicitly because check.use doesn't accept them
1322                         for _, e := range e.Elts {
1323                                 if kv, _ := e.(*ast.KeyValueExpr); kv != nil {
1324                                         // Ideally, we should also "use" kv.Key but we can't know
1325                                         // if it's an externally defined struct key or not. Going
1326                                         // forward anyway can lead to other errors. Give up instead.
1327                                         e = kv.Value
1328                                 }
1329                                 check.use(e)
1330                         }
1331                         // if utyp is invalid, an error was reported before
1332                         if utyp != Typ[Invalid] {
1333                                 check.errorf(e, _InvalidLit, "invalid composite literal type %s", typ)
1334                                 goto Error
1335                         }
1336                 }
1337
1338                 x.mode = value
1339                 x.typ = typ
1340
1341         case *ast.ParenExpr:
1342                 kind := check.rawExpr(x, e.X, nil)
1343                 x.expr = e
1344                 return kind
1345
1346         case *ast.SelectorExpr:
1347                 check.selector(x, e)
1348
1349         case *ast.IndexExpr:
1350                 check.exprOrType(x, e.X)
1351                 if x.mode == invalid {
1352                         check.use(e.Index)
1353                         goto Error
1354                 }
1355
1356                 if x.mode == typexpr {
1357                         // type instantiation
1358                         x.mode = invalid
1359                         x.typ = check.varType(e)
1360                         if x.typ != Typ[Invalid] {
1361                                 x.mode = typexpr
1362                         }
1363                         return expression
1364                 }
1365
1366                 if x.mode == value {
1367                         if sig := asSignature(x.typ); sig != nil && len(sig.tparams) > 0 {
1368                                 return check.call(x, nil, e)
1369                         }
1370                 }
1371
1372                 valid := false
1373                 length := int64(-1) // valid if >= 0
1374                 switch typ := optype(x.typ).(type) {
1375                 case *Basic:
1376                         if isString(typ) {
1377                                 valid = true
1378                                 if x.mode == constant_ {
1379                                         length = int64(len(constant.StringVal(x.val)))
1380                                 }
1381                                 // an indexed string always yields a byte value
1382                                 // (not a constant) even if the string and the
1383                                 // index are constant
1384                                 x.mode = value
1385                                 x.typ = universeByte // use 'byte' name
1386                         }
1387
1388                 case *Array:
1389                         valid = true
1390                         length = typ.len
1391                         if x.mode != variable {
1392                                 x.mode = value
1393                         }
1394                         x.typ = typ.elem
1395
1396                 case *Pointer:
1397                         if typ := asArray(typ.base); typ != nil {
1398                                 valid = true
1399                                 length = typ.len
1400                                 x.mode = variable
1401                                 x.typ = typ.elem
1402                         }
1403
1404                 case *Slice:
1405                         valid = true
1406                         x.mode = variable
1407                         x.typ = typ.elem
1408
1409                 case *Map:
1410                         var key operand
1411                         check.expr(&key, e.Index)
1412                         check.assignment(&key, typ.key, "map index")
1413                         // ok to continue even if indexing failed - map element type is known
1414                         x.mode = mapindex
1415                         x.typ = typ.elem
1416                         x.expr = e
1417                         return expression
1418
1419                 case *Sum:
1420                         // A sum type can be indexed if all of the sum's types
1421                         // support indexing and have the same index and element
1422                         // type. Special rules apply for maps in the sum type.
1423                         var tkey, telem Type // key is for map types only
1424                         nmaps := 0           // number of map types in sum type
1425                         if typ.is(func(t Type) bool {
1426                                 var e Type
1427                                 switch t := under(t).(type) {
1428                                 case *Basic:
1429                                         if isString(t) {
1430                                                 e = universeByte
1431                                         }
1432                                 case *Array:
1433                                         e = t.elem
1434                                 case *Pointer:
1435                                         if t := asArray(t.base); t != nil {
1436                                                 e = t.elem
1437                                         }
1438                                 case *Slice:
1439                                         e = t.elem
1440                                 case *Map:
1441                                         // If there are multiple maps in the sum type,
1442                                         // they must have identical key types.
1443                                         // TODO(gri) We may be able to relax this rule
1444                                         // but it becomes complicated very quickly.
1445                                         if tkey != nil && !Identical(t.key, tkey) {
1446                                                 return false
1447                                         }
1448                                         tkey = t.key
1449                                         e = t.elem
1450                                         nmaps++
1451                                 case *TypeParam:
1452                                         check.errorf(x, 0, "type of %s contains a type parameter - cannot index (implementation restriction)", x)
1453                                 case *instance:
1454                                         panic("unimplemented")
1455                                 }
1456                                 if e == nil || telem != nil && !Identical(e, telem) {
1457                                         return false
1458                                 }
1459                                 telem = e
1460                                 return true
1461                         }) {
1462                                 // If there are maps, the index expression must be assignable
1463                                 // to the map key type (as for simple map index expressions).
1464                                 if nmaps > 0 {
1465                                         var key operand
1466                                         check.expr(&key, e.Index)
1467                                         check.assignment(&key, tkey, "map index")
1468                                         // ok to continue even if indexing failed - map element type is known
1469
1470                                         // If there are only maps, we are done.
1471                                         if nmaps == len(typ.types) {
1472                                                 x.mode = mapindex
1473                                                 x.typ = telem
1474                                                 x.expr = e
1475                                                 return expression
1476                                         }
1477
1478                                         // Otherwise we have mix of maps and other types. For
1479                                         // now we require that the map key be an integer type.
1480                                         // TODO(gri) This is probably not good enough.
1481                                         valid = isInteger(tkey)
1482                                         // avoid 2nd indexing error if indexing failed above
1483                                         if !valid && key.mode == invalid {
1484                                                 goto Error
1485                                         }
1486                                         x.mode = value // map index expressions are not addressable
1487                                 } else {
1488                                         // no maps
1489                                         valid = true
1490                                         x.mode = variable
1491                                 }
1492                                 x.typ = telem
1493                         }
1494                 }
1495
1496                 if !valid {
1497                         check.invalidOp(x, _NonIndexableOperand, "cannot index %s", x)
1498                         goto Error
1499                 }
1500
1501                 if e.Index == nil {
1502                         check.invalidAST(e, "missing index for %s", x)
1503                         goto Error
1504                 }
1505
1506                 // In pathological (invalid) cases (e.g.: type T1 [][[]T1{}[0][0]]T0)
1507                 // the element type may be accessed before it's set. Make sure we have
1508                 // a valid type.
1509                 if x.typ == nil {
1510                         x.typ = Typ[Invalid]
1511                 }
1512
1513                 check.index(e.Index, length)
1514                 // ok to continue
1515
1516         case *ast.SliceExpr:
1517                 check.expr(x, e.X)
1518                 if x.mode == invalid {
1519                         check.use(e.Low, e.High, e.Max)
1520                         goto Error
1521                 }
1522
1523                 valid := false
1524                 length := int64(-1) // valid if >= 0
1525                 switch typ := optype(x.typ).(type) {
1526                 case *Basic:
1527                         if isString(typ) {
1528                                 if e.Slice3 {
1529                                         check.invalidOp(x, _InvalidSliceExpr, "3-index slice of string")
1530                                         goto Error
1531                                 }
1532                                 valid = true
1533                                 if x.mode == constant_ {
1534                                         length = int64(len(constant.StringVal(x.val)))
1535                                 }
1536                                 // spec: "For untyped string operands the result
1537                                 // is a non-constant value of type string."
1538                                 if typ.kind == UntypedString {
1539                                         x.typ = Typ[String]
1540                                 }
1541                         }
1542
1543                 case *Array:
1544                         valid = true
1545                         length = typ.len
1546                         if x.mode != variable {
1547                                 check.invalidOp(x, _NonSliceableOperand, "cannot slice %s (value not addressable)", x)
1548                                 goto Error
1549                         }
1550                         x.typ = &Slice{elem: typ.elem}
1551
1552                 case *Pointer:
1553                         if typ := asArray(typ.base); typ != nil {
1554                                 valid = true
1555                                 length = typ.len
1556                                 x.typ = &Slice{elem: typ.elem}
1557                         }
1558
1559                 case *Slice:
1560                         valid = true
1561                         // x.typ doesn't change
1562
1563                 case *Sum, *TypeParam:
1564                         check.errorf(x, 0, "generic slice expressions not yet implemented")
1565                         goto Error
1566                 }
1567
1568                 if !valid {
1569                         check.invalidOp(x, _NonSliceableOperand, "cannot slice %s", x)
1570                         goto Error
1571                 }
1572
1573                 x.mode = value
1574
1575                 // spec: "Only the first index may be omitted; it defaults to 0."
1576                 if e.Slice3 && (e.High == nil || e.Max == nil) {
1577                         check.invalidAST(inNode(e, e.Rbrack), "2nd and 3rd index required in 3-index slice")
1578                         goto Error
1579                 }
1580
1581                 // check indices
1582                 var ind [3]int64
1583                 for i, expr := range []ast.Expr{e.Low, e.High, e.Max} {
1584                         x := int64(-1)
1585                         switch {
1586                         case expr != nil:
1587                                 // The "capacity" is only known statically for strings, arrays,
1588                                 // and pointers to arrays, and it is the same as the length for
1589                                 // those types.
1590                                 max := int64(-1)
1591                                 if length >= 0 {
1592                                         max = length + 1
1593                                 }
1594                                 if _, v := check.index(expr, max); v >= 0 {
1595                                         x = v
1596                                 }
1597                         case i == 0:
1598                                 // default is 0 for the first index
1599                                 x = 0
1600                         case length >= 0:
1601                                 // default is length (== capacity) otherwise
1602                                 x = length
1603                         }
1604                         ind[i] = x
1605                 }
1606
1607                 // constant indices must be in range
1608                 // (check.index already checks that existing indices >= 0)
1609         L:
1610                 for i, x := range ind[:len(ind)-1] {
1611                         if x > 0 {
1612                                 for _, y := range ind[i+1:] {
1613                                         if y >= 0 && x > y {
1614                                                 check.errorf(inNode(e, e.Rbrack), _SwappedSliceIndices, "swapped slice indices: %d > %d", x, y)
1615                                                 break L // only report one error, ok to continue
1616                                         }
1617                                 }
1618                         }
1619                 }
1620
1621         case *ast.TypeAssertExpr:
1622                 check.expr(x, e.X)
1623                 if x.mode == invalid {
1624                         goto Error
1625                 }
1626                 xtyp, _ := under(x.typ).(*Interface)
1627                 if xtyp == nil {
1628                         check.invalidOp(x, _InvalidAssert, "%s is not an interface", x)
1629                         goto Error
1630                 }
1631                 check.ordinaryType(x, xtyp)
1632                 // x.(type) expressions are handled explicitly in type switches
1633                 if e.Type == nil {
1634                         // Don't use invalidAST because this can occur in the AST produced by
1635                         // go/parser.
1636                         check.error(e, _BadTypeKeyword, "use of .(type) outside type switch")
1637                         goto Error
1638                 }
1639                 T := check.varType(e.Type)
1640                 if T == Typ[Invalid] {
1641                         goto Error
1642                 }
1643                 check.typeAssertion(x, x, xtyp, T)
1644                 x.mode = commaok
1645                 x.typ = T
1646
1647         case *ast.CallExpr:
1648                 return check.call(x, e, e)
1649
1650         case *ast.StarExpr:
1651                 check.exprOrType(x, e.X)
1652                 switch x.mode {
1653                 case invalid:
1654                         goto Error
1655                 case typexpr:
1656                         x.typ = &Pointer{base: x.typ}
1657                 default:
1658                         if typ := asPointer(x.typ); typ != nil {
1659                                 x.mode = variable
1660                                 x.typ = typ.base
1661                         } else {
1662                                 check.invalidOp(x, _InvalidIndirection, "cannot indirect %s", x)
1663                                 goto Error
1664                         }
1665                 }
1666
1667         case *ast.UnaryExpr:
1668                 check.expr(x, e.X)
1669                 if x.mode == invalid {
1670                         goto Error
1671                 }
1672                 check.unary(x, e, e.Op)
1673                 if x.mode == invalid {
1674                         goto Error
1675                 }
1676                 if e.Op == token.ARROW {
1677                         x.expr = e
1678                         return statement // receive operations may appear in statement context
1679                 }
1680
1681         case *ast.BinaryExpr:
1682                 check.binary(x, e, e.X, e.Y, e.Op, e.OpPos)
1683                 if x.mode == invalid {
1684                         goto Error
1685                 }
1686
1687         case *ast.KeyValueExpr:
1688                 // key:value expressions are handled in composite literals
1689                 check.invalidAST(e, "no key:value expected")
1690                 goto Error
1691
1692         case *ast.ArrayType, *ast.StructType, *ast.FuncType,
1693                 *ast.InterfaceType, *ast.MapType, *ast.ChanType:
1694                 x.mode = typexpr
1695                 x.typ = check.typ(e)
1696                 // Note: rawExpr (caller of exprInternal) will call check.recordTypeAndValue
1697                 // even though check.typ has already called it. This is fine as both
1698                 // times the same expression and type are recorded. It is also not a
1699                 // performance issue because we only reach here for composite literal
1700                 // types, which are comparatively rare.
1701
1702         default:
1703                 panic(fmt.Sprintf("%s: unknown expression type %T", check.fset.Position(e.Pos()), e))
1704         }
1705
1706         // everything went well
1707         x.expr = e
1708         return expression
1709
1710 Error:
1711         x.mode = invalid
1712         x.expr = e
1713         return statement // avoid follow-up errors
1714 }
1715
1716 func keyVal(x constant.Value) interface{} {
1717         switch x.Kind() {
1718         case constant.Bool:
1719                 return constant.BoolVal(x)
1720         case constant.String:
1721                 return constant.StringVal(x)
1722         case constant.Int:
1723                 if v, ok := constant.Int64Val(x); ok {
1724                         return v
1725                 }
1726                 if v, ok := constant.Uint64Val(x); ok {
1727                         return v
1728                 }
1729         case constant.Float:
1730                 v, _ := constant.Float64Val(x)
1731                 return v
1732         case constant.Complex:
1733                 r, _ := constant.Float64Val(constant.Real(x))
1734                 i, _ := constant.Float64Val(constant.Imag(x))
1735                 return complex(r, i)
1736         }
1737         return x
1738 }
1739
1740 // typeAssertion checks that x.(T) is legal; xtyp must be the type of x.
1741 func (check *Checker) typeAssertion(at positioner, x *operand, xtyp *Interface, T Type) {
1742         method, wrongType := check.assertableTo(xtyp, T)
1743         if method == nil {
1744                 return
1745         }
1746         var msg string
1747         if wrongType != nil {
1748                 if check.identical(method.typ, wrongType.typ) {
1749                         msg = fmt.Sprintf("missing method %s (%s has pointer receiver)", method.name, method.name)
1750                 } else {
1751                         msg = fmt.Sprintf("wrong type for method %s (have %s, want %s)", method.name, wrongType.typ, method.typ)
1752                 }
1753         } else {
1754                 msg = "missing method " + method.name
1755         }
1756         check.errorf(at, _ImpossibleAssert, "%s cannot have dynamic type %s (%s)", x, T, msg)
1757 }
1758
1759 // expr typechecks expression e and initializes x with the expression value.
1760 // The result must be a single value.
1761 // If an error occurred, x.mode is set to invalid.
1762 //
1763 func (check *Checker) expr(x *operand, e ast.Expr) {
1764         check.rawExpr(x, e, nil)
1765         check.exclude(x, 1<<novalue|1<<builtin|1<<typexpr)
1766         check.singleValue(x)
1767 }
1768
1769 // multiExpr is like expr but the result may also be a multi-value.
1770 func (check *Checker) multiExpr(x *operand, e ast.Expr) {
1771         check.rawExpr(x, e, nil)
1772         check.exclude(x, 1<<novalue|1<<builtin|1<<typexpr)
1773 }
1774
1775 // multiExprOrType is like multiExpr but the result may also be a type.
1776 func (check *Checker) multiExprOrType(x *operand, e ast.Expr) {
1777         check.rawExpr(x, e, nil)
1778         check.exclude(x, 1<<novalue|1<<builtin)
1779 }
1780
1781 // exprWithHint typechecks expression e and initializes x with the expression value;
1782 // hint is the type of a composite literal element.
1783 // If an error occurred, x.mode is set to invalid.
1784 //
1785 func (check *Checker) exprWithHint(x *operand, e ast.Expr, hint Type) {
1786         assert(hint != nil)
1787         check.rawExpr(x, e, hint)
1788         check.exclude(x, 1<<novalue|1<<builtin|1<<typexpr)
1789         check.singleValue(x)
1790 }
1791
1792 // exprOrType typechecks expression or type e and initializes x with the expression value or type.
1793 // If an error occurred, x.mode is set to invalid.
1794 //
1795 func (check *Checker) exprOrType(x *operand, e ast.Expr) {
1796         check.rawExpr(x, e, nil)
1797         check.exclude(x, 1<<novalue)
1798         check.singleValue(x)
1799 }
1800
1801 // exclude reports an error if x.mode is in modeset and sets x.mode to invalid.
1802 // The modeset may contain any of 1<<novalue, 1<<builtin, 1<<typexpr.
1803 func (check *Checker) exclude(x *operand, modeset uint) {
1804         if modeset&(1<<x.mode) != 0 {
1805                 var msg string
1806                 var code errorCode
1807                 switch x.mode {
1808                 case novalue:
1809                         if modeset&(1<<typexpr) != 0 {
1810                                 msg = "%s used as value"
1811                         } else {
1812                                 msg = "%s used as value or type"
1813                         }
1814                         code = _TooManyValues
1815                 case builtin:
1816                         msg = "%s must be called"
1817                         code = _UncalledBuiltin
1818                 case typexpr:
1819                         msg = "%s is not an expression"
1820                         code = _NotAnExpr
1821                 default:
1822                         unreachable()
1823                 }
1824                 check.errorf(x, code, msg, x)
1825                 x.mode = invalid
1826         }
1827 }
1828
1829 // singleValue reports an error if x describes a tuple and sets x.mode to invalid.
1830 func (check *Checker) singleValue(x *operand) {
1831         if x.mode == value {
1832                 // tuple types are never named - no need for underlying type below
1833                 if t, ok := x.typ.(*Tuple); ok {
1834                         assert(t.Len() != 1)
1835                         check.errorf(x, _TooManyValues, "%d-valued %s where single value is expected", t.Len(), x)
1836                         x.mode = invalid
1837                 }
1838         }
1839 }