src/go/types/typexpr.go

   1 // Copyright 2013 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 // This file implements type-checking of identifiers and type expressions.
   6
   7 package types
   8
   9 import (
  10         "fmt"
  11         "go/ast"
  12         "go/constant"
  13         "go/token"
  14         "sort"
  15         "strconv"
  16         "strings"
  17 )
  18
  19 // ident type-checks identifier e and initializes x with the value or type of e.
  20 // If an error occurred, x.mode is set to invalid.
  21 // For the meaning of def, see Checker.definedType, below.
  22 // If wantType is set, the identifier e is expected to denote a type.
  23 //
  24 func (check *Checker) ident(x *operand, e *ast.Ident, def *Named, wantType bool) {
  25         x.mode = invalid
  26         x.expr = e
  27
  28         // Note that we cannot use check.lookup here because the returned scope
  29         // may be different from obj.Parent(). See also Scope.LookupParent doc.
  30         scope, obj := check.scope.LookupParent(e.Name, check.pos)
  31         if obj == nil {
  32                 if e.Name == "_" {
  33                         check.errorf(e, _InvalidBlank, "cannot use _ as value or type")
  34                 } else {
  35                         check.errorf(e, _UndeclaredName, "undeclared name: %s", e.Name)
  36                 }
  37                 return
  38         }
  39         check.recordUse(e, obj)
  40
  41         // Type-check the object.
  42         // Only call Checker.objDecl if the object doesn't have a type yet
  43         // (in which case we must actually determine it) or the object is a
  44         // TypeName and we also want a type (in which case we might detect
  45         // a cycle which needs to be reported). Otherwise we can skip the
  46         // call and avoid a possible cycle error in favor of the more
  47         // informative "not a type/value" error that this function's caller
  48         // will issue (see issue #25790).
  49         typ := obj.Type()
  50         if _, gotType := obj.(*TypeName); typ == nil || gotType && wantType {
  51                 check.objDecl(obj, def)
  52                 typ = obj.Type() // type must have been assigned by Checker.objDecl
  53         }
  54         assert(typ != nil)
  55
  56         // The object may be dot-imported: If so, remove its package from
  57         // the map of unused dot imports for the respective file scope.
  58         // (This code is only needed for dot-imports. Without them,
  59         // we only have to mark variables, see *Var case below).
  60         if pkg := obj.Pkg(); pkg != check.pkg && pkg != nil {
  61                 delete(check.unusedDotImports[scope], pkg)
  62         }
  63
  64         switch obj := obj.(type) {
  65         case *PkgName:
  66                 check.errorf(e, _InvalidPkgUse, "use of package %s not in selector", obj.name)
  67                 return
  68
  69         case *Const:
  70                 check.addDeclDep(obj)
  71                 if typ == Typ[Invalid] {
  72                         return
  73                 }
  74                 if obj == universeIota {
  75                         if check.iota == nil {
  76                                 check.errorf(e, _InvalidIota, "cannot use iota outside constant declaration")
  77                                 return
  78                         }
  79                         x.val = check.iota
  80                 } else {
  81                         x.val = obj.val
  82                 }
  83                 assert(x.val != nil)
  84                 x.mode = constant_
  85
  86         case *TypeName:
  87                 x.mode = typexpr
  88
  89         case *Var:
  90                 // It's ok to mark non-local variables, but ignore variables
  91                 // from other packages to avoid potential race conditions with
  92                 // dot-imported variables.
  93                 if obj.pkg == check.pkg {
  94                         obj.used = true
  95                 }
  96                 check.addDeclDep(obj)
  97                 if typ == Typ[Invalid] {
  98                         return
  99                 }
 100                 x.mode = variable
 101
 102         case *Func:
 103                 check.addDeclDep(obj)
 104                 x.mode = value
 105
 106         case *Builtin:
 107                 x.id = obj.id
 108                 x.mode = builtin
 109
 110         case *Nil:
 111                 x.mode = value
 112
 113         default:
 114                 unreachable()
 115         }
 116
 117         x.typ = typ
 118 }
 119
 120 // typ type-checks the type expression e and returns its type, or Typ[Invalid].
 121 // The type must not be an (uninstantiated) generic type.
 122 func (check *Checker) typ(e ast.Expr) Type {
 123         return check.definedType(e, nil)
 124 }
 125
 126 // varType type-checks the type expression e and returns its type, or Typ[Invalid].
 127 // The type must not be an (uninstantiated) generic type and it must be ordinary
 128 // (see ordinaryType).
 129 func (check *Checker) varType(e ast.Expr) Type {
 130         typ := check.definedType(e, nil)
 131         check.ordinaryType(e, typ)
 132         return typ
 133 }
 134
 135 // ordinaryType reports an error if typ is an interface type containing
 136 // type lists or is (or embeds) the predeclared type comparable.
 137 func (check *Checker) ordinaryType(pos positioner, typ Type) {
 138         // We don't want to call under() (via asInterface) or complete interfaces
 139         // while we are in the middle of type-checking parameter declarations that
 140         // might belong to interface methods. Delay this check to the end of
 141         // type-checking.
 142         check.atEnd(func() {
 143                 if t := asInterface(typ); t != nil {
 144                         check.completeInterface(pos.Pos(), t) // TODO(gri) is this the correct position?
 145                         if t.allTypes != nil {
 146                                 check.softErrorf(pos, _Todo, "interface contains type constraints (%s)", t.allTypes)
 147                                 return
 148                         }
 149                         if t.IsComparable() {
 150                                 check.softErrorf(pos, _Todo, "interface is (or embeds) comparable")
 151                         }
 152                 }
 153         })
 154 }
 155
 156 // anyType type-checks the type expression e and returns its type, or Typ[Invalid].
 157 // The type may be generic or instantiated.
 158 func (check *Checker) anyType(e ast.Expr) Type {
 159         typ := check.typInternal(e, nil)
 160         assert(isTyped(typ))
 161         check.recordTypeAndValue(e, typexpr, typ, nil)
 162         return typ
 163 }
 164
 165 // definedType is like typ but also accepts a type name def.
 166 // If def != nil, e is the type specification for the defined type def, declared
 167 // in a type declaration, and def.underlying will be set to the type of e before
 168 // any components of e are type-checked.
 169 //
 170 func (check *Checker) definedType(e ast.Expr, def *Named) Type {
 171         typ := check.typInternal(e, def)
 172         assert(isTyped(typ))
 173         if isGeneric(typ) {
 174                 check.errorf(e, _Todo, "cannot use generic type %s without instantiation", typ)
 175                 typ = Typ[Invalid]
 176         }
 177         check.recordTypeAndValue(e, typexpr, typ, nil)
 178         return typ
 179 }
 180
 181 // genericType is like typ but the type must be an (uninstantiated) generic type.
 182 func (check *Checker) genericType(e ast.Expr, reportErr bool) Type {
 183         typ := check.typInternal(e, nil)
 184         assert(isTyped(typ))
 185         if typ != Typ[Invalid] && !isGeneric(typ) {
 186                 if reportErr {
 187                         check.errorf(e, _Todo, "%s is not a generic type", typ)
 188                 }
 189                 typ = Typ[Invalid]
 190         }
 191         // TODO(gri) what is the correct call below?
 192         check.recordTypeAndValue(e, typexpr, typ, nil)
 193         return typ
 194 }
 195
 196 // isubst returns an x with identifiers substituted per the substitution map smap.
 197 // isubst only handles the case of (valid) method receiver type expressions correctly.
 198 func isubst(x ast.Expr, smap map[*ast.Ident]*ast.Ident) ast.Expr {
 199         switch n := x.(type) {
 200         case *ast.Ident:
 201                 if alt := smap[n]; alt != nil {
 202                         return alt
 203                 }
 204         case *ast.StarExpr:
 205                 X := isubst(n.X, smap)
 206                 if X != n.X {
 207                         new := *n
 208                         new.X = X
 209                         return &new
 210                 }
 211         case *ast.CallExpr:
 212                 var args []ast.Expr
 213                 for i, arg := range n.Args {
 214                         new := isubst(arg, smap)
 215                         if new != arg {
 216                                 if args == nil {
 217                                         args = make([]ast.Expr, len(n.Args))
 218                                         copy(args, n.Args)
 219                                 }
 220                                 args[i] = new
 221                         }
 222                 }
 223                 if args != nil {
 224                         new := *n
 225                         new.Args = args
 226                         return &new
 227                 }
 228         case *ast.ParenExpr:
 229                 return isubst(n.X, smap) // no need to keep parentheses
 230         default:
 231                 // Other receiver type expressions are invalid.
 232                 // It's fine to ignore those here as they will
 233                 // be checked elsewhere.
 234         }
 235         return x
 236 }
 237
 238 // funcType type-checks a function or method type.
 239 func (check *Checker) funcType(sig *Signature, recvPar *ast.FieldList, ftyp *ast.FuncType) {
 240         check.openScope(ftyp, "function")
 241         check.scope.isFunc = true
 242         check.recordScope(ftyp, check.scope)
 243         sig.scope = check.scope
 244         defer check.closeScope()
 245
 246         var recvTyp ast.Expr // rewritten receiver type; valid if != nil
 247         if recvPar != nil && len(recvPar.List) > 0 {
 248                 // collect generic receiver type parameters, if any
 249                 // - a receiver type parameter is like any other type parameter, except that it is declared implicitly
 250                 // - the receiver specification acts as local declaration for its type parameters, which may be blank
 251                 _, rname, rparams := check.unpackRecv(recvPar.List[0].Type, true)
 252                 if len(rparams) > 0 {
 253                         // Blank identifiers don't get declared and regular type-checking of the instantiated
 254                         // parameterized receiver type expression fails in Checker.collectParams of receiver.
 255                         // Identify blank type parameters and substitute each with a unique new identifier named
 256                         // "n_" (where n is the parameter index) and which cannot conflict with any user-defined
 257                         // name.
 258                         var smap map[*ast.Ident]*ast.Ident // substitution map from "_" to "n_" identifiers
 259                         for i, p := range rparams {
 260                                 if p.Name == "_" {
 261                                         new := *p
 262                                         new.Name = fmt.Sprintf("%d_", i)
 263                                         rparams[i] = &new // use n_ identifier instead of _ so it can be looked up
 264                                         if smap == nil {
 265                                                 smap = make(map[*ast.Ident]*ast.Ident)
 266                                         }
 267                                         smap[p] = &new
 268                                 }
 269                         }
 270                         if smap != nil {
 271                                 // blank identifiers were found => use rewritten receiver type
 272                                 recvTyp = isubst(recvPar.List[0].Type, smap)
 273                         }
 274                         sig.rparams = check.declareTypeParams(nil, rparams)
 275                         // determine receiver type to get its type parameters
 276                         // and the respective type parameter bounds
 277                         var recvTParams []*TypeName
 278                         if rname != nil {
 279                                 // recv should be a Named type (otherwise an error is reported elsewhere)
 280                                 // Also: Don't report an error via genericType since it will be reported
 281                                 //       again when we type-check the signature.
 282                                 // TODO(gri) maybe the receiver should be marked as invalid instead?
 283                                 if recv := asNamed(check.genericType(rname, false)); recv != nil {
 284                                         recvTParams = recv.tparams
 285                                 }
 286                         }
 287                         // provide type parameter bounds
 288                         // - only do this if we have the right number (otherwise an error is reported elsewhere)
 289                         if len(sig.rparams) == len(recvTParams) {
 290                                 // We have a list of *TypeNames but we need a list of Types.
 291                                 list := make([]Type, len(sig.rparams))
 292                                 for i, t := range sig.rparams {
 293                                         list[i] = t.typ
 294                                 }
 295                                 smap := makeSubstMap(recvTParams, list)
 296                                 for i, tname := range sig.rparams {
 297                                         bound := recvTParams[i].typ.(*TypeParam).bound
 298                                         // bound is (possibly) parameterized in the context of the
 299                                         // receiver type declaration. Substitute parameters for the
 300                                         // current context.
 301                                         // TODO(gri) should we assume now that bounds always exist?
 302                                         //           (no bound == empty interface)
 303                                         if bound != nil {
 304                                                 bound = check.subst(tname.pos, bound, smap)
 305                                                 tname.typ.(*TypeParam).bound = bound
 306                                         }
 307                                 }
 308                         }
 309                 }
 310         }
 311
 312         if ftyp.TParams != nil {
 313                 sig.tparams = check.collectTypeParams(ftyp.TParams)
 314                 // Always type-check method type parameters but complain that they are not allowed.
 315                 // (A separate check is needed when type-checking interface method signatures because
 316                 // they don't have a receiver specification.)
 317                 if recvPar != nil {
 318                         check.errorf(ftyp.TParams, _Todo, "methods cannot have type parameters")
 319                 }
 320         }
 321
 322         // Value (non-type) parameters' scope starts in the function body. Use a temporary scope for their
 323         // declarations and then squash that scope into the parent scope (and report any redeclarations at
 324         // that time).
 325         scope := NewScope(check.scope, token.NoPos, token.NoPos, "function body (temp. scope)")
 326         recvList, _ := check.collectParams(scope, recvPar, recvTyp, false) // use rewritten receiver type, if any
 327         params, variadic := check.collectParams(scope, ftyp.Params, nil, true)
 328         results, _ := check.collectParams(scope, ftyp.Results, nil, false)
 329         scope.Squash(func(obj, alt Object) {
 330                 check.errorf(obj, _DuplicateDecl, "%s redeclared in this block", obj.Name())
 331                 check.reportAltDecl(alt)
 332         })
 333
 334         if recvPar != nil {
 335                 // recv parameter list present (may be empty)
 336                 // spec: "The receiver is specified via an extra parameter section preceding the
 337                 // method name. That parameter section must declare a single parameter, the receiver."
 338                 var recv *Var
 339                 switch len(recvList) {
 340                 case 0:
 341                         // error reported by resolver
 342                         recv = NewParam(0, nil, "", Typ[Invalid]) // ignore recv below
 343                 default:
 344                         // more than one receiver
 345                         check.error(recvList[len(recvList)-1], _BadRecv, "method must have exactly one receiver")
 346                         fallthrough // continue with first receiver
 347                 case 1:
 348                         recv = recvList[0]
 349                 }
 350
 351                 // TODO(gri) We should delay rtyp expansion to when we actually need the
 352                 //           receiver; thus all checks here should be delayed to later.
 353                 rtyp, _ := deref(recv.typ)
 354                 rtyp = expand(rtyp)
 355
 356                 // spec: "The receiver type must be of the form T or *T where T is a type name."
 357                 // (ignore invalid types - error was reported before)
 358                 if t := rtyp; t != Typ[Invalid] {
 359                         var err string
 360                         if T := asNamed(t); T != nil {
 361                                 // spec: "The type denoted by T is called the receiver base type; it must not
 362                                 // be a pointer or interface type and it must be declared in the same package
 363                                 // as the method."
 364                                 if T.obj.pkg != check.pkg {
 365                                         err = "type not defined in this package"
 366                                 } else {
 367                                         switch u := optype(T).(type) {
 368                                         case *Basic:
 369                                                 // unsafe.Pointer is treated like a regular pointer
 370                                                 if u.kind == UnsafePointer {
 371                                                         err = "unsafe.Pointer"
 372                                                 }
 373                                         case *Pointer, *Interface:
 374                                                 err = "pointer or interface type"
 375                                         }
 376                                 }
 377                         } else {
 378                                 err = "basic or unnamed type"
 379                         }
 380                         if err != "" {
 381                                 check.errorf(recv, _InvalidRecv, "invalid receiver %s (%s)", recv.typ, err)
 382                                 // ok to continue
 383                         }
 384                 }
 385                 sig.recv = recv
 386         }
 387
 388         sig.params = NewTuple(params...)
 389         sig.results = NewTuple(results...)
 390         sig.variadic = variadic
 391 }
 392
 393 // goTypeName returns the Go type name for typ and
 394 // removes any occurences of "types." from that name.
 395 func goTypeName(typ Type) string {
 396         return strings.ReplaceAll(fmt.Sprintf("%T", typ), "types.", "")
 397 }
 398
 399 // typInternal drives type checking of types.
 400 // Must only be called by definedType or genericType.
 401 //
 402 func (check *Checker) typInternal(e0 ast.Expr, def *Named) (T Type) {
 403         if trace {
 404                 check.trace(e0.Pos(), "type %s", e0)
 405                 check.indent++
 406                 defer func() {
 407                         check.indent--
 408                         var under Type
 409                         if T != nil {
 410                                 // Calling under() here may lead to endless instantiations.
 411                                 // Test case: type T[P any] *T[P]
 412                                 // TODO(gri) investigate if that's a bug or to be expected
 413                                 // (see also analogous comment in Checker.instantiate).
 414                                 under = T.Underlying()
 415                         }
 416                         if T == under {
 417                                 check.trace(e0.Pos(), "=> %s // %s", T, goTypeName(T))
 418                         } else {
 419                                 check.trace(e0.Pos(), "=> %s (under = %s) // %s", T, under, goTypeName(T))
 420                         }
 421                 }()
 422         }
 423
 424         switch e := e0.(type) {
 425         case *ast.BadExpr:
 426                 // ignore - error reported before
 427
 428         case *ast.Ident:
 429                 var x operand
 430                 check.ident(&x, e, def, true)
 431
 432                 switch x.mode {
 433                 case typexpr:
 434                         typ := x.typ
 435                         def.setUnderlying(typ)
 436                         return typ
 437                 case invalid:
 438                         // ignore - error reported before
 439                 case novalue:
 440                         check.errorf(&x, _NotAType, "%s used as type", &x)
 441                 default:
 442                         check.errorf(&x, _NotAType, "%s is not a type", &x)
 443                 }
 444
 445         case *ast.SelectorExpr:
 446                 var x operand
 447                 check.selector(&x, e)
 448
 449                 switch x.mode {
 450                 case typexpr:
 451                         typ := x.typ
 452                         def.setUnderlying(typ)
 453                         return typ
 454                 case invalid:
 455                         // ignore - error reported before
 456                 case novalue:
 457                         check.errorf(&x, _NotAType, "%s used as type", &x)
 458                 default:
 459                         check.errorf(&x, _NotAType, "%s is not a type", &x)
 460                 }
 461
 462         case *ast.IndexExpr:
 463                 return check.instantiatedType(e.X, []ast.Expr{e.Index}, def)
 464
 465         case *ast.CallExpr:
 466                 if e.Brackets {
 467                         return check.instantiatedType(e.Fun, e.Args, def)
 468                 } else {
 469                         check.errorf(e0, _NotAType, "%s is not a type", e0)
 470                 }
 471
 472         case *ast.ParenExpr:
 473                 // Generic types must be instantiated before they can be used in any form.
 474                 // Consequently, generic types cannot be parenthesized.
 475                 return check.definedType(e.X, def)
 476
 477         case *ast.ArrayType:
 478                 if e.Len != nil {
 479                         typ := new(Array)
 480                         def.setUnderlying(typ)
 481                         typ.len = check.arrayLength(e.Len)
 482                         typ.elem = check.varType(e.Elt)
 483                         return typ
 484                 }
 485
 486                 typ := new(Slice)
 487                 def.setUnderlying(typ)
 488                 typ.elem = check.varType(e.Elt)
 489                 return typ
 490
 491         case *ast.Ellipsis:
 492                 // dots are handled explicitly where they are legal
 493                 // (array composite literals and parameter lists)
 494                 check.error(e, _InvalidDotDotDot, "invalid use of '...'")
 495                 check.use(e.Elt)
 496
 497         case *ast.StructType:
 498                 typ := new(Struct)
 499                 def.setUnderlying(typ)
 500                 check.structType(typ, e)
 501                 return typ
 502
 503         case *ast.StarExpr:
 504                 typ := new(Pointer)
 505                 def.setUnderlying(typ)
 506                 typ.base = check.varType(e.X)
 507                 return typ
 508
 509         case *ast.FuncType:
 510                 typ := new(Signature)
 511                 def.setUnderlying(typ)
 512                 check.funcType(typ, nil, e)
 513                 return typ
 514
 515         case *ast.InterfaceType:
 516                 typ := new(Interface)
 517                 def.setUnderlying(typ)
 518                 if def != nil {
 519                         typ.obj = def.obj
 520                 }
 521                 check.interfaceType(typ, e, def)
 522                 return typ
 523
 524         case *ast.MapType:
 525                 typ := new(Map)
 526                 def.setUnderlying(typ)
 527
 528                 typ.key = check.varType(e.Key)
 529                 typ.elem = check.varType(e.Value)
 530
 531                 // spec: "The comparison operators == and != must be fully defined
 532                 // for operands of the key type; thus the key type must not be a
 533                 // function, map, or slice."
 534                 //
 535                 // Delay this check because it requires fully setup types;
 536                 // it is safe to continue in any case (was issue 6667).
 537                 check.atEnd(func() {
 538                         if !Comparable(typ.key) {
 539                                 var why string
 540                                 if asTypeParam(typ.key) != nil {
 541                                         why = " (missing comparable constraint)"
 542                                 }
 543                                 check.errorf(e.Key, _IncomparableMapKey, "incomparable map key type %s%s", typ.key, why)
 544                         }
 545                 })
 546
 547                 return typ
 548
 549         case *ast.ChanType:
 550                 typ := new(Chan)
 551                 def.setUnderlying(typ)
 552
 553                 dir := SendRecv
 554                 switch e.Dir {
 555                 case ast.SEND | ast.RECV:
 556                         // nothing to do
 557                 case ast.SEND:
 558                         dir = SendOnly
 559                 case ast.RECV:
 560                         dir = RecvOnly
 561                 default:
 562                         check.invalidAST(e, "unknown channel direction %d", e.Dir)
 563                         // ok to continue
 564                 }
 565
 566                 typ.dir = dir
 567                 typ.elem = check.varType(e.Value)
 568                 return typ
 569
 570         default:
 571                 check.errorf(e0, _NotAType, "%s is not a type", e0)
 572         }
 573
 574         typ := Typ[Invalid]
 575         def.setUnderlying(typ)
 576         return typ
 577 }
 578
 579 // typeOrNil type-checks the type expression (or nil value) e
 580 // and returns the type of e, or nil. If e is a type, it must
 581 // not be an (uninstantiated) generic type.
 582 // If e is neither a type nor nil, typeOrNil returns Typ[Invalid].
 583 // TODO(gri) should we also disallow non-var types?
 584 func (check *Checker) typeOrNil(e ast.Expr) Type {
 585         var x operand
 586         check.rawExpr(&x, e, nil)
 587         switch x.mode {
 588         case invalid:
 589                 // ignore - error reported before
 590         case novalue:
 591                 check.errorf(&x, _NotAType, "%s used as type", &x)
 592         case typexpr:
 593                 check.instantiatedOperand(&x)
 594                 return x.typ
 595         case value:
 596                 if x.isNil() {
 597                         return nil
 598                 }
 599                 fallthrough
 600         default:
 601                 check.errorf(&x, _NotAType, "%s is not a type", &x)
 602         }
 603         return Typ[Invalid]
 604 }
 605
 606 func (check *Checker) instantiatedType(x ast.Expr, targs []ast.Expr, def *Named) Type {
 607         b := check.genericType(x, true) // TODO(gri) what about cycles?
 608         if b == Typ[Invalid] {
 609                 return b // error already reported
 610         }
 611         base := asNamed(b)
 612         if base == nil {
 613                 unreachable() // should have been caught by genericType
 614         }
 615
 616         // create a new type instance rather than instantiate the type
 617         // TODO(gri) should do argument number check here rather than
 618         //           when instantiating the type?
 619         typ := new(instance)
 620         def.setUnderlying(typ)
 621
 622         typ.check = check
 623         typ.pos = x.Pos()
 624         typ.base = base
 625
 626         // evaluate arguments (always)
 627         typ.targs = check.typeList(targs)
 628         if typ.targs == nil {
 629                 def.setUnderlying(Typ[Invalid]) // avoid later errors due to lazy instantiation
 630                 return Typ[Invalid]
 631         }
 632
 633         // determine argument positions (for error reporting)
 634         typ.poslist = make([]token.Pos, len(targs))
 635         for i, arg := range targs {
 636                 typ.poslist[i] = arg.Pos()
 637         }
 638
 639         // make sure we check instantiation works at least once
 640         // and that the resulting type is valid
 641         check.atEnd(func() {
 642                 t := typ.expand()
 643                 check.validType(t, nil)
 644         })
 645
 646         return typ
 647 }
 648
 649 // arrayLength type-checks the array length expression e
 650 // and returns the constant length >= 0, or a value < 0
 651 // to indicate an error (and thus an unknown length).
 652 func (check *Checker) arrayLength(e ast.Expr) int64 {
 653         var x operand
 654         check.expr(&x, e)
 655         if x.mode != constant_ {
 656                 if x.mode != invalid {
 657                         check.errorf(&x, _InvalidArrayLen, "array length %s must be constant", &x)
 658                 }
 659                 return -1
 660         }
 661         if isUntyped(x.typ) || isInteger(x.typ) {
 662                 if val := constant.ToInt(x.val); val.Kind() == constant.Int {
 663                         if representableConst(val, check, Typ[Int], nil) {
 664                                 if n, ok := constant.Int64Val(val); ok && n >= 0 {
 665                                         return n
 666                                 }
 667                                 check.errorf(&x, _InvalidArrayLen, "invalid array length %s", &x)
 668                                 return -1
 669                         }
 670                 }
 671         }
 672         check.errorf(&x, _InvalidArrayLen, "array length %s must be integer", &x)
 673         return -1
 674 }
 675
 676 // typeList provides the list of types corresponding to the incoming expression list.
 677 // If an error occured, the result is nil, but all list elements were type-checked.
 678 func (check *Checker) typeList(list []ast.Expr) []Type {
 679         res := make([]Type, len(list)) // res != nil even if len(list) == 0
 680         for i, x := range list {
 681                 t := check.varType(x)
 682                 if t == Typ[Invalid] {
 683                         res = nil
 684                 }
 685                 if res != nil {
 686                         res[i] = t
 687                 }
 688         }
 689         return res
 690 }
 691
 692 // collectParams declares the parameters of list in scope and returns the corresponding
 693 // variable list. If type0 != nil, it is used instead of the the first type in list.
 694 func (check *Checker) collectParams(scope *Scope, list *ast.FieldList, type0 ast.Expr, variadicOk bool) (params []*Var, variadic bool) {
 695         if list == nil {
 696                 return
 697         }
 698
 699         var named, anonymous bool
 700         for i, field := range list.List {
 701                 ftype := field.Type
 702                 if i == 0 && type0 != nil {
 703                         ftype = type0
 704                 }
 705                 if t, _ := ftype.(*ast.Ellipsis); t != nil {
 706                         ftype = t.Elt
 707                         if variadicOk && i == len(list.List)-1 && len(field.Names) <= 1 {
 708                                 variadic = true
 709                         } else {
 710                                 check.softErrorf(t, _MisplacedDotDotDot, "can only use ... with final parameter in list")
 711                                 // ignore ... and continue
 712                         }
 713                 }
 714                 typ := check.varType(ftype)
 715                 // The parser ensures that f.Tag is nil and we don't
 716                 // care if a constructed AST contains a non-nil tag.
 717                 if len(field.Names) > 0 {
 718                         // named parameter
 719                         for _, name := range field.Names {
 720                                 if name.Name == "" {
 721                                         check.invalidAST(name, "anonymous parameter")
 722                                         // ok to continue
 723                                 }
 724                                 par := NewParam(name.Pos(), check.pkg, name.Name, typ)
 725                                 check.declare(scope, name, par, scope.pos)
 726                                 params = append(params, par)
 727                         }
 728                         named = true
 729                 } else {
 730                         // anonymous parameter
 731                         par := NewParam(ftype.Pos(), check.pkg, "", typ)
 732                         check.recordImplicit(field, par)
 733                         params = append(params, par)
 734                         anonymous = true
 735                 }
 736         }
 737
 738         if named && anonymous {
 739                 check.invalidAST(list, "list contains both named and anonymous parameters")
 740                 // ok to continue
 741         }
 742
 743         // For a variadic function, change the last parameter's type from T to []T.
 744         // Since we type-checked T rather than ...T, we also need to retro-actively
 745         // record the type for ...T.
 746         if variadic {
 747                 last := params[len(params)-1]
 748                 last.typ = &Slice{elem: last.typ}
 749                 check.recordTypeAndValue(list.List[len(list.List)-1].Type, typexpr, last.typ, nil)
 750         }
 751
 752         return
 753 }
 754
 755 func (check *Checker) declareInSet(oset *objset, pos token.Pos, obj Object) bool {
 756         if alt := oset.insert(obj); alt != nil {
 757                 check.errorf(atPos(pos), _DuplicateDecl, "%s redeclared", obj.Name())
 758                 check.reportAltDecl(alt)
 759                 return false
 760         }
 761         return true
 762 }
 763
 764 func (check *Checker) interfaceType(ityp *Interface, iface *ast.InterfaceType, def *Named) {
 765         var tlist *ast.Ident // "type" name of first entry in a type list declaration
 766         var types []ast.Expr
 767         for _, f := range iface.Methods.List {
 768                 if len(f.Names) > 0 {
 769                         // We have a method with name f.Names[0], or a type
 770                         // of a type list (name.Name == "type").
 771                         // (The parser ensures that there's only one method
 772                         // and we don't care if a constructed AST has more.)
 773                         name := f.Names[0]
 774                         if name.Name == "_" {
 775                                 check.errorf(name, _BlankIfaceMethod, "invalid method name _")
 776                                 continue // ignore
 777                         }
 778
 779                         if name.Name == "type" {
 780                                 // Always collect all type list entries, even from
 781                                 // different type lists, under the assumption that
 782                                 // the author intended to include all types.
 783                                 types = append(types, f.Type)
 784                                 if tlist != nil && tlist != name {
 785                                         check.errorf(name, _Todo, "cannot have multiple type lists in an interface")
 786                                 }
 787                                 tlist = name
 788                                 continue
 789                         }
 790
 791                         typ := check.typ(f.Type)
 792                         sig, _ := typ.(*Signature)
 793                         if sig == nil {
 794                                 if typ != Typ[Invalid] {
 795                                         check.invalidAST(f.Type, "%s is not a method signature", typ)
 796                                 }
 797                                 continue // ignore
 798                         }
 799
 800                         // Always type-check method type parameters but complain if they are not enabled.
 801                         // (This extra check is needed here because interface method signatures don't have
 802                         // a receiver specification.)
 803                         if sig.tparams != nil {
 804                                 check.errorf(f.Type.(*ast.FuncType).TParams, _Todo, "methods cannot have type parameters")
 805                         }
 806
 807                         // use named receiver type if available (for better error messages)
 808                         var recvTyp Type = ityp
 809                         if def != nil {
 810                                 recvTyp = def
 811                         }
 812                         sig.recv = NewVar(name.Pos(), check.pkg, "", recvTyp)
 813
 814                         m := NewFunc(name.Pos(), check.pkg, name.Name, sig)
 815                         check.recordDef(name, m)
 816                         ityp.methods = append(ityp.methods, m)
 817                 } else {
 818                         // We have an embedded type. completeInterface will
 819                         // eventually verify that we have an interface.
 820                         ityp.embeddeds = append(ityp.embeddeds, check.typ(f.Type))
 821                         check.posMap[ityp] = append(check.posMap[ityp], f.Type.Pos())
 822                 }
 823         }
 824
 825         // type constraints
 826         ityp.types = NewSum(check.collectTypeConstraints(iface.Pos(), types))
 827
 828         if len(ityp.methods) == 0 && ityp.types == nil && len(ityp.embeddeds) == 0 {
 829                 // empty interface
 830                 ityp.allMethods = markComplete
 831                 return
 832         }
 833
 834         // sort for API stability
 835         sort.Sort(byUniqueMethodName(ityp.methods))
 836         sort.Stable(byUniqueTypeName(ityp.embeddeds))
 837
 838         check.later(func() { check.completeInterface(iface.Pos(), ityp) })
 839 }
 840
 841 func (check *Checker) completeInterface(pos token.Pos, ityp *Interface) {
 842         if ityp.allMethods != nil {
 843                 return
 844         }
 845
 846         // completeInterface may be called via the LookupFieldOrMethod,
 847         // MissingMethod, Identical, or IdenticalIgnoreTags external API
 848         // in which case check will be nil. In this case, type-checking
 849         // must be finished and all interfaces should have been completed.
 850         if check == nil {
 851                 panic("internal error: incomplete interface")
 852         }
 853
 854         if trace {
 855                 // Types don't generally have position information.
 856                 // If we don't have a valid pos provided, try to use
 857                 // one close enough.
 858                 if !pos.IsValid() && len(ityp.methods) > 0 {
 859                         pos = ityp.methods[0].pos
 860                 }
 861
 862                 check.trace(pos, "complete %s", ityp)
 863                 check.indent++
 864                 defer func() {
 865                         check.indent--
 866                         check.trace(pos, "=> %s (methods = %v, types = %v)", ityp, ityp.allMethods, ityp.allTypes)
 867                 }()
 868         }
 869
 870         // An infinitely expanding interface (due to a cycle) is detected
 871         // elsewhere (Checker.validType), so here we simply assume we only
 872         // have valid interfaces. Mark the interface as complete to avoid
 873         // infinite recursion if the validType check occurs later for some
 874         // reason.
 875         ityp.allMethods = markComplete
 876
 877         // Methods of embedded interfaces are collected unchanged; i.e., the identity
 878         // of a method I.m's Func Object of an interface I is the same as that of
 879         // the method m in an interface that embeds interface I. On the other hand,
 880         // if a method is embedded via multiple overlapping embedded interfaces, we
 881         // don't provide a guarantee which "original m" got chosen for the embedding
 882         // interface. See also issue #34421.
 883         //
 884         // If we don't care to provide this identity guarantee anymore, instead of
 885         // reusing the original method in embeddings, we can clone the method's Func
 886         // Object and give it the position of a corresponding embedded interface. Then
 887         // we can get rid of the mpos map below and simply use the cloned method's
 888         // position.
 889
 890         var seen objset
 891         var methods []*Func
 892         mpos := make(map[*Func]token.Pos) // method specification or method embedding position, for good error messages
 893         addMethod := func(pos token.Pos, m *Func, explicit bool) {
 894                 switch other := seen.insert(m); {
 895                 case other == nil:
 896                         methods = append(methods, m)
 897                         mpos[m] = pos
 898                 case explicit:
 899                         check.errorf(atPos(pos), _DuplicateDecl, "duplicate method %s", m.name)
 900                         check.errorf(atPos(mpos[other.(*Func)]), _DuplicateDecl, "\tother declaration of %s", m.name) // secondary error, \t indented
 901                 default:
 902                         // check method signatures after all types are computed (issue #33656)
 903                         check.atEnd(func() {
 904                                 if !check.identical(m.typ, other.Type()) {
 905                                         check.errorf(atPos(pos), _DuplicateDecl, "duplicate method %s", m.name)
 906                                         check.errorf(atPos(mpos[other.(*Func)]), _DuplicateDecl, "\tother declaration of %s", m.name) // secondary error, \t indented
 907                                 }
 908                         })
 909                 }
 910         }
 911
 912         for _, m := range ityp.methods {
 913                 addMethod(m.pos, m, true)
 914         }
 915
 916         // collect types
 917         allTypes := ityp.types
 918
 919         posList := check.posMap[ityp]
 920         for i, typ := range ityp.embeddeds {
 921                 pos := posList[i] // embedding position
 922                 utyp := under(typ)
 923                 etyp := asInterface(utyp)
 924                 if etyp == nil {
 925                         if utyp != Typ[Invalid] {
 926                                 var format string
 927                                 if _, ok := utyp.(*TypeParam); ok {
 928                                         format = "%s is a type parameter, not an interface"
 929                                 } else {
 930                                         format = "%s is not an interface"
 931                                 }
 932                                 // TODO: correct error code.
 933                                 check.errorf(atPos(pos), _InvalidIfaceEmbed, format, typ)
 934                         }
 935                         continue
 936                 }
 937                 check.completeInterface(pos, etyp)
 938                 for _, m := range etyp.allMethods {
 939                         addMethod(pos, m, false) // use embedding position pos rather than m.pos
 940                 }
 941                 allTypes = intersect(allTypes, etyp.allTypes)
 942         }
 943
 944         if methods != nil {
 945                 sort.Sort(byUniqueMethodName(methods))
 946                 ityp.allMethods = methods
 947         }
 948         ityp.allTypes = allTypes
 949 }
 950
 951 // intersect computes the intersection of the types x and y.
 952 // Note: A incomming nil type stands for the top type. A top
 953 // type result is returned as nil.
 954 func intersect(x, y Type) (r Type) {
 955         defer func() {
 956                 if r == theTop {
 957                         r = nil
 958                 }
 959         }()
 960
 961         switch {
 962         case x == theBottom || y == theBottom:
 963                 return theBottom
 964         case x == nil || x == theTop:
 965                 return y
 966         case y == nil || x == theTop:
 967                 return x
 968         }
 969
 970         xtypes := unpackType(x)
 971         ytypes := unpackType(y)
 972         // Compute the list rtypes which includes only
 973         // types that are in both xtypes and ytypes.
 974         // Quadratic algorithm, but good enough for now.
 975         // TODO(gri) fix this
 976         var rtypes []Type
 977         for _, x := range xtypes {
 978                 if includes(ytypes, x) {
 979                         rtypes = append(rtypes, x)
 980                 }
 981         }
 982
 983         if rtypes == nil {
 984                 return theBottom
 985         }
 986         return NewSum(rtypes)
 987 }
 988
 989 // byUniqueTypeName named type lists can be sorted by their unique type names.
 990 type byUniqueTypeName []Type
 991
 992 func (a byUniqueTypeName) Len() int           { return len(a) }
 993 func (a byUniqueTypeName) Less(i, j int) bool { return sortName(a[i]) < sortName(a[j]) }
 994 func (a byUniqueTypeName) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
 995
 996 func sortName(t Type) string {
 997         if named := asNamed(t); named != nil {
 998                 return named.obj.Id()
 999         }
1000         return ""
1001 }
1002
1003 // byUniqueMethodName method lists can be sorted by their unique method names.
1004 type byUniqueMethodName []*Func
1005
1006 func (a byUniqueMethodName) Len() int           { return len(a) }
1007 func (a byUniqueMethodName) Less(i, j int) bool { return a[i].Id() < a[j].Id() }
1008 func (a byUniqueMethodName) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
1009
1010 func (check *Checker) tag(t *ast.BasicLit) string {
1011         if t != nil {
1012                 if t.Kind == token.STRING {
1013                         if val, err := strconv.Unquote(t.Value); err == nil {
1014                                 return val
1015                         }
1016                 }
1017                 check.invalidAST(t, "incorrect tag syntax: %q", t.Value)
1018         }
1019         return ""
1020 }
1021
1022 func (check *Checker) structType(styp *Struct, e *ast.StructType) {
1023         list := e.Fields
1024         if list == nil {
1025                 return
1026         }
1027
1028         // struct fields and tags
1029         var fields []*Var
1030         var tags []string
1031
1032         // for double-declaration checks
1033         var fset objset
1034
1035         // current field typ and tag
1036         var typ Type
1037         var tag string
1038         add := func(ident *ast.Ident, embedded bool, pos token.Pos) {
1039                 if tag != "" && tags == nil {
1040                         tags = make([]string, len(fields))
1041                 }
1042                 if tags != nil {
1043                         tags = append(tags, tag)
1044                 }
1045
1046                 name := ident.Name
1047                 fld := NewField(pos, check.pkg, name, typ, embedded)
1048                 // spec: "Within a struct, non-blank field names must be unique."
1049                 if name == "_" || check.declareInSet(&fset, pos, fld) {
1050                         fields = append(fields, fld)
1051                         check.recordDef(ident, fld)
1052                 }
1053         }
1054
1055         // addInvalid adds an embedded field of invalid type to the struct for
1056         // fields with errors; this keeps the number of struct fields in sync
1057         // with the source as long as the fields are _ or have different names
1058         // (issue #25627).
1059         addInvalid := func(ident *ast.Ident, pos token.Pos) {
1060                 typ = Typ[Invalid]
1061                 tag = ""
1062                 add(ident, true, pos)
1063         }
1064
1065         for _, f := range list.List {
1066                 typ = check.varType(f.Type)
1067                 tag = check.tag(f.Tag)
1068                 if len(f.Names) > 0 {
1069                         // named fields
1070                         for _, name := range f.Names {
1071                                 add(name, false, name.Pos())
1072                         }
1073                 } else {
1074                         // embedded field
1075                         // spec: "An embedded type must be specified as a type name T or as a
1076                         // pointer to a non-interface type name *T, and T itself may not be a
1077                         // pointer type."
1078                         pos := f.Type.Pos()
1079                         name := embeddedFieldIdent(f.Type)
1080                         if name == nil {
1081                                 // TODO(rFindley): using invalidAST here causes test failures (all
1082                                 //                 errors should have codes). Clean this up.
1083                                 check.errorf(f.Type, _Todo, "invalid AST: embedded field type %s has no name", f.Type)
1084                                 name = ast.NewIdent("_")
1085                                 name.NamePos = pos
1086                                 addInvalid(name, pos)
1087                                 continue
1088                         }
1089                         add(name, true, pos)
1090
1091                         // Because we have a name, typ must be of the form T or *T, where T is the name
1092                         // of a (named or alias) type, and t (= deref(typ)) must be the type of T.
1093                         // We must delay this check to the end because we don't want to instantiate
1094                         // (via under(t)) a possibly incomplete type.
1095
1096                         // for use in the closure below
1097                         embeddedTyp := typ
1098                         embeddedPos := f.Type
1099
1100                         check.atEnd(func() {
1101                                 t, isPtr := deref(embeddedTyp)
1102                                 switch t := optype(t).(type) {
1103                                 case *Basic:
1104                                         if t == Typ[Invalid] {
1105                                                 // error was reported before
1106                                                 return
1107                                         }
1108                                         // unsafe.Pointer is treated like a regular pointer
1109                                         if t.kind == UnsafePointer {
1110                                                 check.errorf(embeddedPos, _InvalidPtrEmbed, "embedded field type cannot be unsafe.Pointer")
1111                                         }
1112                                 case *Pointer:
1113                                         check.errorf(embeddedPos, _InvalidPtrEmbed, "embedded field type cannot be a pointer")
1114                                 case *Interface:
1115                                         if isPtr {
1116                                                 check.errorf(embeddedPos, _InvalidPtrEmbed, "embedded field type cannot be a pointer to an interface")
1117                                         }
1118                                 }
1119                         })
1120                 }
1121         }
1122
1123         styp.fields = fields
1124         styp.tags = tags
1125 }
1126
1127 func embeddedFieldIdent(e ast.Expr) *ast.Ident {
1128         switch e := e.(type) {
1129         case *ast.Ident:
1130                 return e
1131         case *ast.StarExpr:
1132                 // *T is valid, but **T is not
1133                 if _, ok := e.X.(*ast.StarExpr); !ok {
1134                         return embeddedFieldIdent(e.X)
1135                 }
1136         case *ast.SelectorExpr:
1137                 return e.Sel
1138         case *ast.IndexExpr:
1139                 return embeddedFieldIdent(e.X)
1140         case *ast.CallExpr:
1141                 if e.Brackets {
1142                         return embeddedFieldIdent(e.Fun)
1143                 }
1144         }
1145         return nil // invalid embedded field
1146 }
1147
1148 func (check *Checker) collectTypeConstraints(pos token.Pos, types []ast.Expr) []Type {
1149         list := make([]Type, 0, len(types)) // assume all types are correct
1150         for _, texpr := range types {
1151                 if texpr == nil {
1152                         check.invalidAST(atPos(pos), "missing type constraint")
1153                         continue
1154                 }
1155                 list = append(list, check.varType(texpr))
1156         }
1157
1158         // Ensure that each type is only present once in the type list.  Types may be
1159         // interfaces, which may not be complete yet. It's ok to do this check at the
1160         // end because it's not a requirement for correctness of the code.
1161         // Note: This is a quadratic algorithm, but type lists tend to be short.
1162         check.atEnd(func() {
1163                 for i, t := range list {
1164                         if t := asInterface(t); t != nil {
1165                                 check.completeInterface(types[i].Pos(), t)
1166                         }
1167                         if includes(list[:i], t) {
1168                                 check.softErrorf(types[i], _Todo, "duplicate type %s in type list", t)
1169                         }
1170                 }
1171         })
1172
1173         return list
1174 }
1175
1176 // includes reports whether typ is in list.
1177 func includes(list []Type, typ Type) bool {
1178         for _, e := range list {
1179                 if Identical(typ, e) {
1180                         return true
1181                 }
1182         }
1183         return false
1184 }