1 // Copyright 2014 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.
14 func (check *Checker) reportAltDecl(obj Object) {
15 if pos := obj.Pos(); pos.IsValid() {
16 // We use "other" rather than "previous" here because
17 // the first declaration seen may not be textually
18 // earlier in the source.
19 check.errorf(obj, _DuplicateDecl, "\tother declaration of %s", obj.Name()) // secondary error, \t indented
23 func (check *Checker) declare(scope *Scope, id *ast.Ident, obj Object, pos token.Pos) {
24 // spec: "The blank identifier, represented by the underscore
25 // character _, may be used in a declaration like any other
26 // identifier but the declaration does not introduce a new
28 if obj.Name() != "_" {
29 if alt := scope.Insert(obj); alt != nil {
30 check.errorf(obj, _DuplicateDecl, "%s redeclared in this block", obj.Name())
31 check.reportAltDecl(alt)
37 check.recordDef(id, obj)
41 // pathString returns a string of the form a->b-> ... ->g for a path [a, b, ... g].
42 func pathString(path []Object) string {
44 for i, p := range path {
53 // objDecl type-checks the declaration of obj in its respective (file) context.
54 // For the meaning of def, see Checker.definedType, in typexpr.go.
55 func (check *Checker) objDecl(obj Object, def *Named) {
56 if trace && obj.Type() == nil {
57 if check.indent == 0 {
58 fmt.Println() // empty line between top-level objects for readability
60 check.trace(obj.Pos(), "-- checking %s (%s, objPath = %s)", obj, obj.color(), pathString(check.objPath))
64 check.trace(obj.Pos(), "=> %s (%s)", obj, obj.color())
68 // Checking the declaration of obj means inferring its type
69 // (and possibly its value, for constants).
70 // An object's type (and thus the object) may be in one of
71 // three states which are expressed by colors:
73 // - an object whose type is not yet known is painted white (initial color)
74 // - an object whose type is in the process of being inferred is painted grey
75 // - an object whose type is fully inferred is painted black
77 // During type inference, an object's color changes from white to grey
78 // to black (pre-declared objects are painted black from the start).
79 // A black object (i.e., its type) can only depend on (refer to) other black
80 // ones. White and grey objects may depend on white and black objects.
81 // A dependency on a grey object indicates a cycle which may or may not be
84 // When objects turn grey, they are pushed on the object path (a stack);
85 // they are popped again when they turn black. Thus, if a grey object (a
86 // cycle) is encountered, it is on the object path, and all the objects
87 // it depends on are the remaining objects on that path. Color encoding
88 // is such that the color value of a grey object indicates the index of
89 // that object in the object path.
91 // During type-checking, white objects may be assigned a type without
92 // traversing through objDecl; e.g., when initializing constants and
93 // variables. Update the colors of those objects here (rather than
94 // everywhere where we set the type) to satisfy the color invariants.
95 if obj.color() == white && obj.Type() != nil {
102 assert(obj.Type() == nil)
103 // All color values other than white and black are considered grey.
104 // Because black and white are < grey, all values >= grey are grey.
105 // Use those values to encode the object's index into the object path.
106 obj.setColor(grey + color(check.push(obj)))
108 check.pop().setColor(black)
112 assert(obj.Type() != nil)
116 // Color values other than white or black are considered grey.
121 // In the existing code, this is marked by a non-nil type
122 // for the object except for constants and variables whose
123 // type may be non-nil (known), or nil if it depends on the
124 // not-yet known initialization value.
125 // In the former case, set the type to Typ[Invalid] because
126 // we have an initialization cycle. The cycle error will be
127 // reported later, when determining initialization order.
128 // TODO(gri) Report cycle here and simplify initialization
130 switch obj := obj.(type) {
132 if check.cycle(obj) || obj.typ == nil {
133 obj.typ = Typ[Invalid]
137 if check.cycle(obj) || obj.typ == nil {
138 obj.typ = Typ[Invalid]
142 if check.cycle(obj) {
144 // (without this, calling underlying()
145 // below may lead to an endless loop
146 // if we have a cycle for a defined
148 obj.typ = Typ[Invalid]
152 if check.cycle(obj) {
153 // Don't set obj.typ to Typ[Invalid] here
154 // because plenty of code type-asserts that
155 // functions have a *Signature type. Grey
156 // functions have their type set to an empty
157 // signature which makes it impossible to
158 // initialize a variable with the function.
164 assert(obj.Type() != nil)
168 d := check.objMap[obj]
170 check.dump("%v: %s should have been declared", obj.Pos(), obj)
174 // save/restore current context and setup object context
175 defer func(ctxt context) {
178 check.context = context{
182 // Const and var declarations must not have initialization
183 // cycles. We track them by remembering the current declaration
184 // in check.decl. Initialization expressions depending on other
185 // consts, vars, or functions, add dependencies to the current
187 switch obj := obj.(type) {
189 check.decl = d // new package-level const decl
190 check.constDecl(obj, d.vtyp, d.init, d.inherited)
192 check.decl = d // new package-level var decl
193 check.varDecl(obj, d.lhs, d.vtyp, d.init)
195 // invalid recursive types are detected via path
196 check.typeDecl(obj, d.tdecl, def)
197 check.collectMethods(obj) // methods can only be added to top-level types
199 // functions may be recursive - no need to track dependencies
200 check.funcDecl(obj, d)
206 // cycle checks if the cycle starting with obj is valid and
207 // reports an error if it is not.
208 func (check *Checker) cycle(obj Object) (isCycle bool) {
209 // The object map contains the package scope objects and the non-interface methods.
211 info := check.objMap[obj]
212 inObjMap := info != nil && (info.fdecl == nil || info.fdecl.Recv == nil) // exclude methods
213 isPkgObj := obj.Parent() == check.pkg.scope
214 if isPkgObj != inObjMap {
215 check.dump("%v: inconsistent object map for %s (isPkgObj = %v, inObjMap = %v)", obj.Pos(), obj, isPkgObj, inObjMap)
220 // Count cycle objects.
221 assert(obj.color() >= grey)
222 start := obj.color() - grey // index of obj in objPath
223 cycle := check.objPath[start:]
224 nval := 0 // number of (constant or variable) values in the cycle
225 ndef := 0 // number of type definitions in the cycle
226 for _, obj := range cycle {
227 switch obj := obj.(type) {
231 // Determine if the type name is an alias or not. For
232 // package-level objects, use the object map which
233 // provides syntactic information (which doesn't rely
234 // on the order in which the objects are set up). For
235 // local objects, we can rely on the order, so use
236 // the object's predicate.
237 // TODO(gri) It would be less fragile to always access
238 // the syntactic information. We should consider storing
239 // this information explicitly in the object.
241 if d := check.objMap[obj]; d != nil {
242 alias = d.tdecl.Assign.IsValid() // package-level object
244 alias = obj.IsAlias() // function local object
257 check.trace(obj.Pos(), "## cycle detected: objPath = %s->%s (len = %d)", pathString(cycle), obj.Name(), len(cycle))
258 check.trace(obj.Pos(), "## cycle contains: %d values, %d type definitions", nval, ndef)
261 check.trace(obj.Pos(), "=> error: cycle is invalid")
266 // A cycle involving only constants and variables is invalid but we
267 // ignore them here because they are reported via the initialization
269 if nval == len(cycle) {
273 // A cycle involving only types (and possibly functions) must have at least
274 // one type definition to be permitted: If there is no type definition, we
275 // have a sequence of alias type names which will expand ad infinitum.
276 if nval == 0 && ndef > 0 {
277 return false // cycle is permitted
280 check.cycleError(cycle)
287 // validType verifies that the given type does not "expand" infinitely
288 // producing a cycle in the type graph. Cycles are detected by marking
290 // (Cycles involving alias types, as in "type A = [10]A" are detected
291 // earlier, via the objDecl cycle detection mechanism.)
292 func (check *Checker) validType(typ Type, path []Object) typeInfo {
294 unknown typeInfo = iota
300 switch t := typ.(type) {
302 return check.validType(t.elem, path)
305 for _, f := range t.fields {
306 if check.validType(f.typ, path) == invalid {
312 for _, etyp := range t.embeddeds {
313 if check.validType(etyp, path) == invalid {
319 // don't touch the type if it is from a different package or the Universe scope
320 // (doing so would lead to a race condition - was issue #35049)
321 if t.obj.pkg != check.pkg {
325 // don't report a 2nd error if we already know the type is invalid
326 // (e.g., if a cycle was detected earlier, via under).
327 if t.underlying == Typ[Invalid] {
335 t.info = check.validType(t.orig, append(path, t.obj)) // only types of current package added to path
338 for i, tn := range path {
339 if t.obj.pkg != check.pkg {
340 panic("internal error: type cycle via package-external type")
343 check.cycleError(path[i:])
348 panic("internal error: cycle start not found")
353 return check.validType(t.expand(), path)
359 // cycleError reports a declaration cycle starting with
360 // the object in cycle that is "first" in the source.
361 func (check *Checker) cycleError(cycle []Object) {
362 // TODO(gri) Should we start with the last (rather than the first) object in the cycle
363 // since that is the earliest point in the source where we start seeing the
364 // cycle? That would be more consistent with other error messages.
365 i := firstInSrc(cycle)
367 check.errorf(obj, _InvalidDeclCycle, "illegal cycle in declaration of %s", obj.Name())
369 check.errorf(obj, _InvalidDeclCycle, "\t%s refers to", obj.Name()) // secondary error, \t indented
376 check.errorf(obj, _InvalidDeclCycle, "\t%s", obj.Name())
379 // firstInSrc reports the index of the object with the "smallest"
380 // source position in path. path must not be empty.
381 func firstInSrc(path []Object) int {
382 fst, pos := 0, path[0].Pos()
383 for i, t := range path[1:] {
385 fst, pos = i+1, t.Pos()
396 importDecl struct{ spec *ast.ImportSpec }
404 varDecl struct{ spec *ast.ValueSpec }
405 typeDecl struct{ spec *ast.TypeSpec }
406 funcDecl struct{ decl *ast.FuncDecl }
409 func (d importDecl) node() ast.Node { return d.spec }
410 func (d constDecl) node() ast.Node { return d.spec }
411 func (d varDecl) node() ast.Node { return d.spec }
412 func (d typeDecl) node() ast.Node { return d.spec }
413 func (d funcDecl) node() ast.Node { return d.decl }
415 func (check *Checker) walkDecls(decls []ast.Decl, f func(decl)) {
416 for _, d := range decls {
421 func (check *Checker) walkDecl(d ast.Decl, f func(decl)) {
422 switch d := d.(type) {
426 var last *ast.ValueSpec // last ValueSpec with type or init exprs seen
427 for iota, s := range d.Specs {
428 switch s := s.(type) {
429 case *ast.ImportSpec:
434 // determine which initialization expressions to use
437 case s.Type != nil || len(s.Values) > 0:
441 last = new(ast.ValueSpec) // make sure last exists
444 check.arityMatch(s, last)
445 f(constDecl{spec: s, iota: iota, typ: last.Type, init: last.Values, inherited: inherited})
447 check.arityMatch(s, nil)
450 check.invalidAST(s, "invalid token %s", d.Tok)
455 check.invalidAST(s, "unknown ast.Spec node %T", s)
461 check.invalidAST(d, "unknown ast.Decl node %T", d)
465 func (check *Checker) constDecl(obj *Const, typ, init ast.Expr, inherited bool) {
466 assert(obj.typ == nil)
468 // use the correct value of iota
469 defer func(iota constant.Value, errpos positioner) {
471 check.errpos = errpos
472 }(check.iota, check.errpos)
476 // provide valid constant value under all circumstances
477 obj.val = constant.MakeUnknown()
479 // determine type, if any
483 // don't report an error if the type is an invalid C (defined) type
485 if under(t) != Typ[Invalid] {
486 check.errorf(typ, _InvalidConstType, "invalid constant type %s", t)
488 obj.typ = Typ[Invalid]
494 // check initialization
498 // The initialization expression is inherited from a previous
499 // constant declaration, and (error) positions refer to that
500 // expression and not the current constant declaration. Use
501 // the constant identifier position for any errors during
502 // init expression evaluation since that is all we have
503 // (see issues #42991, #42992).
504 check.errpos = atPos(obj.pos)
508 check.initConst(obj, &x)
511 func (check *Checker) varDecl(obj *Var, lhs []*Var, typ, init ast.Expr) {
512 assert(obj.typ == nil)
514 // If we have undefined variable types due to errors,
515 // mark variables as used to avoid follow-on errors.
516 // Matches compiler behavior.
518 if obj.typ == Typ[Invalid] {
521 for _, lhs := range lhs {
522 if lhs.typ == Typ[Invalid] {
528 // determine type, if any
530 obj.typ = check.varType(typ)
531 // We cannot spread the type to all lhs variables if there
532 // are more than one since that would mark them as checked
533 // (see Checker.objDecl) and the assignment of init exprs,
534 // if any, would not be checked.
536 // TODO(gri) If we have no init expr, we should distribute
537 // a given type otherwise we need to re-evalate the type
538 // expr for each lhs variable, leading to duplicate work.
541 // check initialization
544 // error reported before by arityMatch
545 obj.typ = Typ[Invalid]
550 if lhs == nil || len(lhs) == 1 {
551 assert(lhs == nil || lhs[0] == obj)
554 check.initVar(obj, &x, "variable declaration")
559 // obj must be one of lhs
561 for _, lhs := range lhs {
568 panic("inconsistent lhs")
572 // We have multiple variables on the lhs and one init expr.
573 // Make sure all variables have been given the same type if
574 // one was specified, otherwise they assume the type of the
575 // init expression values (was issue #15755).
577 for _, lhs := range lhs {
582 check.initVars(lhs, []ast.Expr{init}, token.NoPos)
585 // under returns the expanded underlying type of n0; possibly by following
586 // forward chains of named types. If an underlying type is found, resolve
587 // the chain by setting the underlying type for each defined type in the
588 // chain before returning it. If no underlying type is found or a cycle
589 // is detected, the result is Typ[Invalid]. If a cycle is detected and
590 // n0.check != nil, the cycle is reported.
591 func (n0 *Named) under() Type {
597 // If the underlying type of a defined type is not a defined
598 // type, then that is the desired underlying type.
601 return u // common case
604 // Otherwise, follow the forward chain.
605 seen := map[*Named]int{n0: 0}
606 path := []Object{n0.obj}
615 break // end of chain
619 path = append(path, n.obj)
622 if i, ok := seen[n]; ok {
624 // TODO(rFindley) revert this to a method on Checker. Having a possibly
625 // nil Checker on Named and TypeParam is too subtle.
627 n0.check.cycleError(path[i:])
634 for n := range seen {
635 // We should never have to update the underlying type of an imported type;
636 // those underlying types should have been resolved during the import.
637 // Also, doing so would lead to a race condition (was issue #31749).
638 // Do this check always, not just in debug more (it's cheap).
639 if n0.check != nil && n.obj.pkg != n0.check.pkg {
640 panic("internal error: imported type with unresolved underlying type")
648 func (n *Named) setUnderlying(typ Type) {
654 func (check *Checker) typeDecl(obj *TypeName, tdecl *ast.TypeSpec, def *Named) {
655 assert(obj.typ == nil)
658 check.validType(obj.typ, nil)
661 alias := tdecl.Assign.IsValid()
662 if alias && tdecl.TParams != nil {
663 // The parser will ensure this but we may still get an invalid AST.
664 // Complain and continue as regular type definition.
665 check.error(atPos(tdecl.Assign), 0, "generic type cannot be alias")
670 // type alias declaration
672 obj.typ = Typ[Invalid]
673 obj.typ = check.anyType(tdecl.Type)
676 // defined type declaration
678 named := &Named{check: check, obj: obj}
679 def.setUnderlying(named)
680 obj.typ = named // make sure recursive type declarations terminate
682 if tdecl.TParams != nil {
683 check.openScope(tdecl, "type parameters")
684 defer check.closeScope()
685 named.tparams = check.collectTypeParams(tdecl.TParams)
688 // determine underlying type of named
689 named.orig = check.definedType(tdecl.Type, named)
691 // The underlying type of named may be itself a named type that is
700 // The type of C is the (named) type of A which is incomplete,
701 // and which has as its underlying type the named type B.
702 // Determine the (final, unnamed) underlying type by resolving
703 // any forward chain.
704 // TODO(gri) Investigate if we can just use named.origin here
705 // and rely on lazy computation of the underlying type.
706 named.underlying = under(named)
711 func (check *Checker) collectTypeParams(list *ast.FieldList) (tparams []*TypeName) {
712 // Type parameter lists should not be empty. The parser will
713 // complain but we still may get an incorrect AST: ignore it.
714 if list.NumFields() == 0 {
718 // Declare type parameters up-front, with empty interface as type bound.
719 // The scope of type parameters starts at the beginning of the type parameter
720 // list (so we can have mutually recursive parameterized interfaces).
721 for _, f := range list.List {
722 tparams = check.declareTypeParams(tparams, f.Names)
725 setBoundAt := func(at int, bound Type) {
726 assert(IsInterface(bound))
727 tparams[at].typ.(*TypeParam).bound = bound
732 for _, f := range list.List {
737 // The predeclared identifier "any" is visible only as a constraint
738 // in a type parameter list. Look for it before general constraint
740 if tident, _ := f.Type.(*ast.Ident); tident != nil && tident.Name == "any" && check.lookup("any") == nil {
743 bound = check.typ(f.Type)
746 // type bound must be an interface
747 // TODO(gri) We should delay the interface check because
748 // we may not have a complete interface yet:
749 // type C(type T C) interface {}
751 if _, ok := under(bound).(*Interface); ok {
752 // Otherwise, set the bound for each type parameter.
753 for i := range f.Names {
754 setBoundAt(index+i, bound)
756 } else if bound != Typ[Invalid] {
757 check.errorf(f.Type, _Todo, "%s is not an interface", bound)
761 index += len(f.Names)
767 func (check *Checker) declareTypeParams(tparams []*TypeName, names []*ast.Ident) []*TypeName {
768 for _, name := range names {
769 tpar := NewTypeName(name.Pos(), check.pkg, name.Name, nil)
770 check.NewTypeParam(tpar, len(tparams), &emptyInterface) // assigns type to tpar as a side-effect
771 check.declare(check.scope, name, tpar, check.scope.pos) // TODO(gri) check scope position
772 tparams = append(tparams, tpar)
775 if trace && len(names) > 0 {
776 check.trace(names[0].Pos(), "type params = %v", tparams[len(tparams)-len(names):])
782 func (check *Checker) collectMethods(obj *TypeName) {
783 // get associated methods
784 // (Checker.collectObjects only collects methods with non-blank names;
785 // Checker.resolveBaseTypeName ensures that obj is not an alias name
786 // if it has attached methods.)
787 methods := check.methods[obj]
791 delete(check.methods, obj)
792 assert(!check.objMap[obj].tdecl.Assign.IsValid()) // don't use TypeName.IsAlias (requires fully set up object)
794 // use an objset to check for name conflicts
797 // spec: "If the base type is a struct type, the non-blank method
798 // and field names must be distinct."
799 base := asNamed(obj.typ) // shouldn't fail but be conservative
801 if t, _ := base.underlying.(*Struct); t != nil {
802 for _, fld := range t.fields {
804 assert(mset.insert(fld) == nil)
809 // Checker.Files may be called multiple times; additional package files
810 // may add methods to already type-checked types. Add pre-existing methods
811 // so that we can detect redeclarations.
812 for _, m := range base.methods {
813 assert(m.name != "_")
814 assert(mset.insert(m) == nil)
819 for _, m := range methods {
820 // spec: "For a base type, the non-blank names of methods bound
821 // to it must be unique."
822 assert(m.name != "_")
823 if alt := mset.insert(m); alt != nil {
826 check.errorf(m, _DuplicateFieldAndMethod, "field and method with the same name %s", m.name)
828 check.errorf(m, _DuplicateMethod, "method %s already declared for %s", m.name, obj)
832 check.reportAltDecl(alt)
837 base.methods = append(base.methods, m)
842 func (check *Checker) funcDecl(obj *Func, decl *declInfo) {
843 assert(obj.typ == nil)
845 // func declarations cannot use iota
846 assert(check.iota == nil)
848 sig := new(Signature)
849 obj.typ = sig // guard against cycles
851 // Avoid cycle error when referring to method while type-checking the signature.
852 // This avoids a nuisance in the best case (non-parameterized receiver type) and
853 // since the method is not a type, we get an error. If we have a parameterized
854 // receiver type, instantiating the receiver type leads to the instantiation of
855 // its methods, and we don't want a cycle error in that case.
856 // TODO(gri) review if this is correct and/or whether we still need this?
860 check.funcType(sig, fdecl.Recv, fdecl.Type)
863 // function body must be type-checked after global declarations
864 // (functions implemented elsewhere have no body)
865 if !check.conf.IgnoreFuncBodies && fdecl.Body != nil {
867 check.funcBody(decl, obj.name, sig, fdecl.Body, nil)
872 func (check *Checker) declStmt(d ast.Decl) {
875 check.walkDecl(d, func(d decl) {
876 switch d := d.(type) {
878 top := len(check.delayed)
880 // declare all constants
881 lhs := make([]*Const, len(d.spec.Names))
882 for i, name := range d.spec.Names {
883 obj := NewConst(name.Pos(), pkg, name.Name, nil, constant.MakeInt64(int64(d.iota)))
891 check.constDecl(obj, d.typ, init, d.inherited)
894 // process function literals in init expressions before scope changes
895 check.processDelayed(top)
897 // spec: "The scope of a constant or variable identifier declared
898 // inside a function begins at the end of the ConstSpec or VarSpec
899 // (ShortVarDecl for short variable declarations) and ends at the
900 // end of the innermost containing block."
901 scopePos := d.spec.End()
902 for i, name := range d.spec.Names {
903 check.declare(check.scope, name, lhs[i], scopePos)
907 top := len(check.delayed)
909 lhs0 := make([]*Var, len(d.spec.Names))
910 for i, name := range d.spec.Names {
911 lhs0[i] = NewVar(name.Pos(), pkg, name.Name, nil)
914 // initialize all variables
915 for i, obj := range lhs0 {
918 switch len(d.spec.Values) {
919 case len(d.spec.Names):
921 init = d.spec.Values[i]
923 // rhs is expected to be a multi-valued expression
925 init = d.spec.Values[0]
927 if i < len(d.spec.Values) {
928 init = d.spec.Values[i]
931 check.varDecl(obj, lhs, d.spec.Type, init)
932 if len(d.spec.Values) == 1 {
933 // If we have a single lhs variable we are done either way.
934 // If we have a single rhs expression, it must be a multi-
935 // valued expression, in which case handling the first lhs
936 // variable will cause all lhs variables to have a type
937 // assigned, and we are done as well.
939 for _, obj := range lhs0 {
940 assert(obj.typ != nil)
947 // process function literals in init expressions before scope changes
948 check.processDelayed(top)
950 // declare all variables
951 // (only at this point are the variable scopes (parents) set)
952 scopePos := d.spec.End() // see constant declarations
953 for i, name := range d.spec.Names {
954 // see constant declarations
955 check.declare(check.scope, name, lhs0[i], scopePos)
959 obj := NewTypeName(d.spec.Name.Pos(), pkg, d.spec.Name.Name, nil)
960 // spec: "The scope of a type identifier declared inside a function
961 // begins at the identifier in the TypeSpec and ends at the end of
962 // the innermost containing block."
963 scopePos := d.spec.Name.Pos()
964 check.declare(check.scope, d.spec.Name, obj, scopePos)
965 // mark and unmark type before calling typeDecl; its type is still nil (see Checker.objDecl)
966 obj.setColor(grey + color(check.push(obj)))
967 check.typeDecl(obj, d.spec, nil)
968 check.pop().setColor(black)
970 check.invalidAST(d.node(), "unknown ast.Decl node %T", d.node())