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 "go/ast" 11 "go/constant" 12 "go/token" 13 "sort" 14 "strconv" 15 ) 16 17 // ident type-checks identifier e and initializes x with the value or type of e. 18 // If an error occurred, x.mode is set to invalid. 19 // For the meaning of def and path, see check.typ, below. 20 // 21 func (check *Checker) ident(x *operand, e *ast.Ident, def *Named, path []*TypeName) { 22 x.mode = invalid 23 x.expr = e 24 25 scope, obj := check.scope.LookupParent(e.Name, check.pos) 26 if obj == nil { 27 if e.Name == "_" { 28 check.errorf(e.Pos(), "cannot use _ as value or type") 29 } else { 30 check.errorf(e.Pos(), "undeclared name: %s", e.Name) 31 } 32 return 33 } 34 check.recordUse(e, obj) 35 36 check.objDecl(obj, def, path) 37 typ := obj.Type() 38 assert(typ != nil) 39 40 // The object may be dot-imported: If so, remove its package from 41 // the map of unused dot imports for the respective file scope. 42 // (This code is only needed for dot-imports. Without them, 43 // we only have to mark variables, see *Var case below). 44 if pkg := obj.Pkg(); pkg != check.pkg && pkg != nil { 45 delete(check.unusedDotImports[scope], pkg) 46 } 47 48 // Alias-related code. Keep for now. 49 // An alias stands for the original object; use that one instead. 50 // TODO(gri) We should be able to factor out the Typ[Invalid] test. 51 // if alias, _ := obj.(*Alias); alias != nil { 52 // obj = original(obj) 53 // if obj == nil || typ == Typ[Invalid] { 54 // return 55 // } 56 // assert(typ == obj.Type()) 57 // } 58 59 switch obj := obj.(type) { 60 case *PkgName: 61 check.errorf(e.Pos(), "use of package %s not in selector", obj.name) 62 return 63 64 case *Const: 65 check.addDeclDep(obj) 66 if typ == Typ[Invalid] { 67 return 68 } 69 if obj == universeIota { 70 if check.iota == nil { 71 check.errorf(e.Pos(), "cannot use iota outside constant declaration") 72 return 73 } 74 x.val = check.iota 75 } else { 76 x.val = obj.val 77 } 78 assert(x.val != nil) 79 x.mode = constant_ 80 81 case *TypeName: 82 x.mode = typexpr 83 // check for cycle 84 // (it's ok to iterate forward because each named type appears at most once in path) 85 for i, prev := range path { 86 if prev == obj { 87 check.errorf(obj.pos, "illegal cycle in declaration of %s", obj.name) 88 // print cycle 89 for _, obj := range path[i:] { 90 check.errorf(obj.Pos(), "\t%s refers to", obj.Name()) // secondary error, \t indented 91 } 92 check.errorf(obj.Pos(), "\t%s", obj.Name()) 93 // maintain x.mode == typexpr despite error 94 typ = Typ[Invalid] 95 break 96 } 97 } 98 99 case *Var: 100 if obj.pkg == check.pkg { 101 obj.used = true 102 } 103 check.addDeclDep(obj) 104 if typ == Typ[Invalid] { 105 return 106 } 107 x.mode = variable 108 109 case *Func: 110 check.addDeclDep(obj) 111 x.mode = value 112 113 case *Builtin: 114 x.id = obj.id 115 x.mode = builtin 116 117 case *Nil: 118 x.mode = value 119 120 default: 121 unreachable() 122 } 123 124 x.typ = typ 125 } 126 127 // typExpr type-checks the type expression e and returns its type, or Typ[Invalid]. 128 // If def != nil, e is the type specification for the named type def, declared 129 // in a type declaration, and def.underlying will be set to the type of e before 130 // any components of e are type-checked. Path contains the path of named types 131 // referring to this type. 132 // 133 func (check *Checker) typExpr(e ast.Expr, def *Named, path []*TypeName) (T Type) { 134 if trace { 135 check.trace(e.Pos(), "%s", e) 136 check.indent++ 137 defer func() { 138 check.indent-- 139 check.trace(e.Pos(), "=> %s", T) 140 }() 141 } 142 143 T = check.typExprInternal(e, def, path) 144 assert(isTyped(T)) 145 check.recordTypeAndValue(e, typexpr, T, nil) 146 147 return 148 } 149 150 func (check *Checker) typ(e ast.Expr) Type { 151 return check.typExpr(e, nil, nil) 152 } 153 154 // funcType type-checks a function or method type. 155 func (check *Checker) funcType(sig *Signature, recvPar *ast.FieldList, ftyp *ast.FuncType) { 156 scope := NewScope(check.scope, token.NoPos, token.NoPos, "function") 157 check.recordScope(ftyp, scope) 158 159 recvList, _ := check.collectParams(scope, recvPar, false) 160 params, variadic := check.collectParams(scope, ftyp.Params, true) 161 results, _ := check.collectParams(scope, ftyp.Results, false) 162 163 if recvPar != nil { 164 // recv parameter list present (may be empty) 165 // spec: "The receiver is specified via an extra parameter section preceding the 166 // method name. That parameter section must declare a single parameter, the receiver." 167 var recv *Var 168 switch len(recvList) { 169 case 0: 170 check.error(recvPar.Pos(), "method is missing receiver") 171 recv = NewParam(0, nil, "", Typ[Invalid]) // ignore recv below 172 default: 173 // more than one receiver 174 check.error(recvList[len(recvList)-1].Pos(), "method must have exactly one receiver") 175 fallthrough // continue with first receiver 176 case 1: 177 recv = recvList[0] 178 } 179 // spec: "The receiver type must be of the form T or *T where T is a type name." 180 // (ignore invalid types - error was reported before) 181 if t, _ := deref(recv.typ); t != Typ[Invalid] { 182 var err string 183 if T, _ := t.(*Named); T != nil { 184 // spec: "The type denoted by T is called the receiver base type; it must not 185 // be a pointer or interface type and it must be declared in the same package 186 // as the method." 187 if T.obj.pkg != check.pkg { 188 err = "type not defined in this package" 189 } else { 190 // TODO(gri) This is not correct if the underlying type is unknown yet. 191 switch u := T.underlying.(type) { 192 case *Basic: 193 // unsafe.Pointer is treated like a regular pointer 194 if u.kind == UnsafePointer { 195 err = "unsafe.Pointer" 196 } 197 case *Pointer, *Interface: 198 err = "pointer or interface type" 199 } 200 } 201 } else { 202 err = "basic or unnamed type" 203 } 204 if err != "" { 205 check.errorf(recv.pos, "invalid receiver %s (%s)", recv.typ, err) 206 // ok to continue 207 } 208 } 209 sig.recv = recv 210 } 211 212 sig.scope = scope 213 sig.params = NewTuple(params...) 214 sig.results = NewTuple(results...) 215 sig.variadic = variadic 216 } 217 218 // typExprInternal drives type checking of types. 219 // Must only be called by typExpr. 220 // 221 func (check *Checker) typExprInternal(e ast.Expr, def *Named, path []*TypeName) Type { 222 switch e := e.(type) { 223 case *ast.BadExpr: 224 // ignore - error reported before 225 226 case *ast.Ident: 227 var x operand 228 check.ident(&x, e, def, path) 229 230 switch x.mode { 231 case typexpr: 232 typ := x.typ 233 def.setUnderlying(typ) 234 return typ 235 case invalid: 236 // ignore - error reported before 237 case novalue: 238 check.errorf(x.pos(), "%s used as type", &x) 239 default: 240 check.errorf(x.pos(), "%s is not a type", &x) 241 } 242 243 case *ast.SelectorExpr: 244 var x operand 245 check.selector(&x, e) 246 247 switch x.mode { 248 case typexpr: 249 typ := x.typ 250 def.setUnderlying(typ) 251 return typ 252 case invalid: 253 // ignore - error reported before 254 case novalue: 255 check.errorf(x.pos(), "%s used as type", &x) 256 default: 257 check.errorf(x.pos(), "%s is not a type", &x) 258 } 259 260 case *ast.ParenExpr: 261 return check.typExpr(e.X, def, path) 262 263 case *ast.ArrayType: 264 if e.Len != nil { 265 typ := new(Array) 266 def.setUnderlying(typ) 267 typ.len = check.arrayLength(e.Len) 268 typ.elem = check.typExpr(e.Elt, nil, path) 269 return typ 270 271 } else { 272 typ := new(Slice) 273 def.setUnderlying(typ) 274 typ.elem = check.typ(e.Elt) 275 return typ 276 } 277 278 case *ast.StructType: 279 typ := new(Struct) 280 def.setUnderlying(typ) 281 check.structType(typ, e, path) 282 return typ 283 284 case *ast.StarExpr: 285 typ := new(Pointer) 286 def.setUnderlying(typ) 287 typ.base = check.typ(e.X) 288 return typ 289 290 case *ast.FuncType: 291 typ := new(Signature) 292 def.setUnderlying(typ) 293 check.funcType(typ, nil, e) 294 return typ 295 296 case *ast.InterfaceType: 297 typ := new(Interface) 298 def.setUnderlying(typ) 299 check.interfaceType(typ, e, def, path) 300 return typ 301 302 case *ast.MapType: 303 typ := new(Map) 304 def.setUnderlying(typ) 305 306 typ.key = check.typ(e.Key) 307 typ.elem = check.typ(e.Value) 308 309 // spec: "The comparison operators == and != must be fully defined 310 // for operands of the key type; thus the key type must not be a 311 // function, map, or slice." 312 // 313 // Delay this check because it requires fully setup types; 314 // it is safe to continue in any case (was issue 6667). 315 check.delay(func() { 316 if !Comparable(typ.key) { 317 check.errorf(e.Key.Pos(), "invalid map key type %s", typ.key) 318 } 319 }) 320 321 return typ 322 323 case *ast.ChanType: 324 typ := new(Chan) 325 def.setUnderlying(typ) 326 327 dir := SendRecv 328 switch e.Dir { 329 case ast.SEND | ast.RECV: 330 // nothing to do 331 case ast.SEND: 332 dir = SendOnly 333 case ast.RECV: 334 dir = RecvOnly 335 default: 336 check.invalidAST(e.Pos(), "unknown channel direction %d", e.Dir) 337 // ok to continue 338 } 339 340 typ.dir = dir 341 typ.elem = check.typ(e.Value) 342 return typ 343 344 default: 345 check.errorf(e.Pos(), "%s is not a type", e) 346 } 347 348 typ := Typ[Invalid] 349 def.setUnderlying(typ) 350 return typ 351 } 352 353 // typeOrNil type-checks the type expression (or nil value) e 354 // and returns the typ of e, or nil. 355 // If e is neither a type nor nil, typOrNil returns Typ[Invalid]. 356 // 357 func (check *Checker) typOrNil(e ast.Expr) Type { 358 var x operand 359 check.rawExpr(&x, e, nil) 360 switch x.mode { 361 case invalid: 362 // ignore - error reported before 363 case novalue: 364 check.errorf(x.pos(), "%s used as type", &x) 365 case typexpr: 366 return x.typ 367 case value: 368 if x.isNil() { 369 return nil 370 } 371 fallthrough 372 default: 373 check.errorf(x.pos(), "%s is not a type", &x) 374 } 375 return Typ[Invalid] 376 } 377 378 func (check *Checker) arrayLength(e ast.Expr) int64 { 379 var x operand 380 check.expr(&x, e) 381 if x.mode != constant_ { 382 if x.mode != invalid { 383 check.errorf(x.pos(), "array length %s must be constant", &x) 384 } 385 return 0 386 } 387 if isUntyped(x.typ) || isInteger(x.typ) { 388 if val := constant.ToInt(x.val); val.Kind() == constant.Int { 389 if representableConst(val, check.conf, Typ[Int], nil) { 390 if n, ok := constant.Int64Val(val); ok && n >= 0 { 391 return n 392 } 393 check.errorf(x.pos(), "invalid array length %s", &x) 394 return 0 395 } 396 } 397 } 398 check.errorf(x.pos(), "array length %s must be integer", &x) 399 return 0 400 } 401 402 func (check *Checker) collectParams(scope *Scope, list *ast.FieldList, variadicOk bool) (params []*Var, variadic bool) { 403 if list == nil { 404 return 405 } 406 407 var named, anonymous bool 408 for i, field := range list.List { 409 ftype := field.Type 410 if t, _ := ftype.(*ast.Ellipsis); t != nil { 411 ftype = t.Elt 412 if variadicOk && i == len(list.List)-1 { 413 variadic = true 414 } else { 415 check.invalidAST(field.Pos(), "... not permitted") 416 // ignore ... and continue 417 } 418 } 419 typ := check.typ(ftype) 420 // The parser ensures that f.Tag is nil and we don't 421 // care if a constructed AST contains a non-nil tag. 422 if len(field.Names) > 0 { 423 // named parameter 424 for _, name := range field.Names { 425 if name.Name == "" { 426 check.invalidAST(name.Pos(), "anonymous parameter") 427 // ok to continue 428 } 429 par := NewParam(name.Pos(), check.pkg, name.Name, typ) 430 check.declare(scope, name, par, scope.pos) 431 params = append(params, par) 432 } 433 named = true 434 } else { 435 // anonymous parameter 436 par := NewParam(ftype.Pos(), check.pkg, "", typ) 437 check.recordImplicit(field, par) 438 params = append(params, par) 439 anonymous = true 440 } 441 } 442 443 if named && anonymous { 444 check.invalidAST(list.Pos(), "list contains both named and anonymous parameters") 445 // ok to continue 446 } 447 448 // For a variadic function, change the last parameter's type from T to []T. 449 if variadic && len(params) > 0 { 450 last := params[len(params)-1] 451 last.typ = &Slice{elem: last.typ} 452 } 453 454 return 455 } 456 457 func (check *Checker) declareInSet(oset *objset, pos token.Pos, obj Object) bool { 458 if alt := oset.insert(obj); alt != nil { 459 check.errorf(pos, "%s redeclared", obj.Name()) 460 check.reportAltDecl(alt) 461 return false 462 } 463 return true 464 } 465 466 func (check *Checker) interfaceType(iface *Interface, ityp *ast.InterfaceType, def *Named, path []*TypeName) { 467 // empty interface: common case 468 if ityp.Methods == nil { 469 return 470 } 471 472 // The parser ensures that field tags are nil and we don't 473 // care if a constructed AST contains non-nil tags. 474 475 // use named receiver type if available (for better error messages) 476 var recvTyp Type = iface 477 if def != nil { 478 recvTyp = def 479 } 480 481 // Phase 1: Collect explicitly declared methods, the corresponding 482 // signature (AST) expressions, and the list of embedded 483 // type (AST) expressions. Do not resolve signatures or 484 // embedded types yet to avoid cycles referring to this 485 // interface. 486 487 var ( 488 mset objset 489 signatures []ast.Expr // list of corresponding method signatures 490 embedded []ast.Expr // list of embedded types 491 ) 492 for _, f := range ityp.Methods.List { 493 if len(f.Names) > 0 { 494 // The parser ensures that there's only one method 495 // and we don't care if a constructed AST has more. 496 name := f.Names[0] 497 pos := name.Pos() 498 // spec: "As with all method sets, in an interface type, 499 // each method must have a unique non-blank name." 500 if name.Name == "_" { 501 check.errorf(pos, "invalid method name _") 502 continue 503 } 504 // Don't type-check signature yet - use an 505 // empty signature now and update it later. 506 // Since we know the receiver, set it up now 507 // (required to avoid crash in ptrRecv; see 508 // e.g. test case for issue 6638). 509 // TODO(gri) Consider marking methods signatures 510 // as incomplete, for better error messages. See 511 // also the T4 and T5 tests in testdata/cycles2.src. 512 sig := new(Signature) 513 sig.recv = NewVar(pos, check.pkg, "", recvTyp) 514 m := NewFunc(pos, check.pkg, name.Name, sig) 515 if check.declareInSet(&mset, pos, m) { 516 iface.methods = append(iface.methods, m) 517 iface.allMethods = append(iface.allMethods, m) 518 signatures = append(signatures, f.Type) 519 check.recordDef(name, m) 520 } 521 } else { 522 // embedded type 523 embedded = append(embedded, f.Type) 524 } 525 } 526 527 // Phase 2: Resolve embedded interfaces. Because an interface must not 528 // embed itself (directly or indirectly), each embedded interface 529 // can be fully resolved without depending on any method of this 530 // interface (if there is a cycle or another error, the embedded 531 // type resolves to an invalid type and is ignored). 532 // In particular, the list of methods for each embedded interface 533 // must be complete (it cannot depend on this interface), and so 534 // those methods can be added to the list of all methods of this 535 // interface. 536 537 for _, e := range embedded { 538 pos := e.Pos() 539 typ := check.typExpr(e, nil, path) 540 // Determine underlying embedded (possibly incomplete) type 541 // by following its forward chain. 542 named, _ := typ.(*Named) 543 under := underlying(named) 544 embed, _ := under.(*Interface) 545 if embed == nil { 546 if typ != Typ[Invalid] { 547 check.errorf(pos, "%s is not an interface", typ) 548 } 549 continue 550 } 551 iface.embeddeds = append(iface.embeddeds, named) 552 // collect embedded methods 553 for _, m := range embed.allMethods { 554 if check.declareInSet(&mset, pos, m) { 555 iface.allMethods = append(iface.allMethods, m) 556 } 557 } 558 } 559 560 // Phase 3: At this point all methods have been collected for this interface. 561 // It is now safe to type-check the signatures of all explicitly 562 // declared methods, even if they refer to this interface via a cycle 563 // and embed the methods of this interface in a parameter of interface 564 // type. 565 566 for i, m := range iface.methods { 567 expr := signatures[i] 568 typ := check.typ(expr) 569 sig, _ := typ.(*Signature) 570 if sig == nil { 571 if typ != Typ[Invalid] { 572 check.invalidAST(expr.Pos(), "%s is not a method signature", typ) 573 } 574 continue // keep method with empty method signature 575 } 576 // update signature, but keep recv that was set up before 577 old := m.typ.(*Signature) 578 sig.recv = old.recv 579 *old = *sig // update signature (don't replace it!) 580 } 581 582 // TODO(gri) The list of explicit methods is only sorted for now to 583 // produce the same Interface as NewInterface. We may be able to 584 // claim source order in the future. Revisit. 585 sort.Sort(byUniqueMethodName(iface.methods)) 586 587 // TODO(gri) The list of embedded types is only sorted for now to 588 // produce the same Interface as NewInterface. We may be able to 589 // claim source order in the future. Revisit. 590 sort.Sort(byUniqueTypeName(iface.embeddeds)) 591 592 sort.Sort(byUniqueMethodName(iface.allMethods)) 593 } 594 595 // byUniqueTypeName named type lists can be sorted by their unique type names. 596 type byUniqueTypeName []*Named 597 598 func (a byUniqueTypeName) Len() int { return len(a) } 599 func (a byUniqueTypeName) Less(i, j int) bool { return a[i].obj.Id() < a[j].obj.Id() } 600 func (a byUniqueTypeName) Swap(i, j int) { a[i], a[j] = a[j], a[i] } 601 602 // byUniqueMethodName method lists can be sorted by their unique method names. 603 type byUniqueMethodName []*Func 604 605 func (a byUniqueMethodName) Len() int { return len(a) } 606 func (a byUniqueMethodName) Less(i, j int) bool { return a[i].Id() < a[j].Id() } 607 func (a byUniqueMethodName) Swap(i, j int) { a[i], a[j] = a[j], a[i] } 608 609 func (check *Checker) tag(t *ast.BasicLit) string { 610 if t != nil { 611 if t.Kind == token.STRING { 612 if val, err := strconv.Unquote(t.Value); err == nil { 613 return val 614 } 615 } 616 check.invalidAST(t.Pos(), "incorrect tag syntax: %q", t.Value) 617 } 618 return "" 619 } 620 621 func (check *Checker) structType(styp *Struct, e *ast.StructType, path []*TypeName) { 622 list := e.Fields 623 if list == nil { 624 return 625 } 626 627 // struct fields and tags 628 var fields []*Var 629 var tags []string 630 631 // for double-declaration checks 632 var fset objset 633 634 // current field typ and tag 635 var typ Type 636 var tag string 637 add := func(field *ast.Field, ident *ast.Ident, anonymous bool, pos token.Pos) { 638 if tag != "" && tags == nil { 639 tags = make([]string, len(fields)) 640 } 641 if tags != nil { 642 tags = append(tags, tag) 643 } 644 645 name := ident.Name 646 fld := NewField(pos, check.pkg, name, typ, anonymous) 647 // spec: "Within a struct, non-blank field names must be unique." 648 if name == "_" || check.declareInSet(&fset, pos, fld) { 649 fields = append(fields, fld) 650 check.recordDef(ident, fld) 651 } 652 } 653 654 for _, f := range list.List { 655 typ = check.typExpr(f.Type, nil, path) 656 tag = check.tag(f.Tag) 657 if len(f.Names) > 0 { 658 // named fields 659 for _, name := range f.Names { 660 add(f, name, false, name.Pos()) 661 } 662 } else { 663 // anonymous field 664 name := anonymousFieldIdent(f.Type) 665 pos := f.Type.Pos() 666 t, isPtr := deref(typ) 667 switch t := t.(type) { 668 case *Basic: 669 if t == Typ[Invalid] { 670 // error was reported before 671 continue 672 } 673 // unsafe.Pointer is treated like a regular pointer 674 if t.kind == UnsafePointer { 675 check.errorf(pos, "anonymous field type cannot be unsafe.Pointer") 676 continue 677 } 678 add(f, name, true, pos) 679 680 case *Named: 681 // spec: "An embedded type must be specified as a type name 682 // T or as a pointer to a non-interface type name *T, and T 683 // itself may not be a pointer type." 684 switch u := t.underlying.(type) { 685 case *Basic: 686 // unsafe.Pointer is treated like a regular pointer 687 if u.kind == UnsafePointer { 688 check.errorf(pos, "anonymous field type cannot be unsafe.Pointer") 689 continue 690 } 691 case *Pointer: 692 check.errorf(pos, "anonymous field type cannot be a pointer") 693 continue 694 case *Interface: 695 if isPtr { 696 check.errorf(pos, "anonymous field type cannot be a pointer to an interface") 697 continue 698 } 699 } 700 add(f, name, true, pos) 701 702 default: 703 check.invalidAST(pos, "anonymous field type %s must be named", typ) 704 } 705 } 706 } 707 708 styp.fields = fields 709 styp.tags = tags 710 } 711 712 func anonymousFieldIdent(e ast.Expr) *ast.Ident { 713 switch e := e.(type) { 714 case *ast.Ident: 715 return e 716 case *ast.StarExpr: 717 return anonymousFieldIdent(e.X) 718 case *ast.SelectorExpr: 719 return e.Sel 720 } 721 return nil // invalid anonymous field 722 } 723