Source file src/pkg/go/types/check.go

     1	// Copyright 2011 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 the Check function, which drives type-checking.
     6	
     7	package types
     8	
     9	import (
    10		"go/ast"
    11		"go/constant"
    12		"go/token"
    13	)
    14	
    15	// debugging/development support
    16	const (
    17		debug = false // leave on during development
    18		trace = false // turn on for detailed type resolution traces
    19	)
    20	
    21	// If Strict is set, the type-checker enforces additional
    22	// rules not specified by the Go 1 spec, but which will
    23	// catch guaranteed run-time errors if the respective
    24	// code is executed. In other words, programs passing in
    25	// Strict mode are Go 1 compliant, but not all Go 1 programs
    26	// will pass in Strict mode. The additional rules are:
    27	//
    28	// - A type assertion x.(T) where T is an interface type
    29	//   is invalid if any (statically known) method that exists
    30	//   for both x and T have different signatures.
    31	//
    32	const strict = false
    33	
    34	// exprInfo stores information about an untyped expression.
    35	type exprInfo struct {
    36		isLhs bool // expression is lhs operand of a shift with delayed type-check
    37		mode  operandMode
    38		typ   *Basic
    39		val   constant.Value // constant value; or nil (if not a constant)
    40	}
    41	
    42	// A context represents the context within which an object is type-checked.
    43	type context struct {
    44		decl          *declInfo              // package-level declaration whose init expression/function body is checked
    45		scope         *Scope                 // top-most scope for lookups
    46		pos           token.Pos              // if valid, identifiers are looked up as if at position pos (used by Eval)
    47		iota          constant.Value         // value of iota in a constant declaration; nil otherwise
    48		sig           *Signature             // function signature if inside a function; nil otherwise
    49		isPanic       map[*ast.CallExpr]bool // set of panic call expressions (used for termination check)
    50		hasLabel      bool                   // set if a function makes use of labels (only ~1% of functions); unused outside functions
    51		hasCallOrRecv bool                   // set if an expression contains a function call or channel receive operation
    52	}
    53	
    54	// lookup looks up name in the current context and returns the matching object, or nil.
    55	func (ctxt *context) lookup(name string) Object {
    56		_, obj := ctxt.scope.LookupParent(name, ctxt.pos)
    57		return obj
    58	}
    59	
    60	// An importKey identifies an imported package by import path and source directory
    61	// (directory containing the file containing the import). In practice, the directory
    62	// may always be the same, or may not matter. Given an (import path, directory), an
    63	// importer must always return the same package (but given two different import paths,
    64	// an importer may still return the same package by mapping them to the same package
    65	// paths).
    66	type importKey struct {
    67		path, dir string
    68	}
    69	
    70	// A Checker maintains the state of the type checker.
    71	// It must be created with NewChecker.
    72	type Checker struct {
    73		// package information
    74		// (initialized by NewChecker, valid for the life-time of checker)
    75		conf *Config
    76		fset *token.FileSet
    77		pkg  *Package
    78		*Info
    79		objMap map[Object]*declInfo   // maps package-level objects and (non-interface) methods to declaration info
    80		impMap map[importKey]*Package // maps (import path, source directory) to (complete or fake) package
    81	
    82		// information collected during type-checking of a set of package files
    83		// (initialized by Files, valid only for the duration of check.Files;
    84		// maps and lists are allocated on demand)
    85		files            []*ast.File                       // package files
    86		unusedDotImports map[*Scope]map[*Package]token.Pos // positions of unused dot-imported packages for each file scope
    87	
    88		firstErr error                 // first error encountered
    89		methods  map[*TypeName][]*Func // maps package scope type names to associated non-blank, non-interface methods
    90		// TODO(gri) move interfaces up to the group of fields persistent across check.Files invocations (see also comment in Checker.initFiles)
    91		interfaces map[*TypeName]*ifaceInfo // maps interface type names to corresponding interface infos
    92		untyped    map[ast.Expr]exprInfo    // map of expressions without final type
    93		delayed    []func()                 // stack of delayed actions
    94		objPath    []Object                 // path of object dependencies during type inference (for cycle reporting)
    95	
    96		// context within which the current object is type-checked
    97		// (valid only for the duration of type-checking a specific object)
    98		context
    99	
   100		// debugging
   101		indent int // indentation for tracing
   102	}
   103	
   104	// addUnusedImport adds the position of a dot-imported package
   105	// pkg to the map of dot imports for the given file scope.
   106	func (check *Checker) addUnusedDotImport(scope *Scope, pkg *Package, pos token.Pos) {
   107		mm := check.unusedDotImports
   108		if mm == nil {
   109			mm = make(map[*Scope]map[*Package]token.Pos)
   110			check.unusedDotImports = mm
   111		}
   112		m := mm[scope]
   113		if m == nil {
   114			m = make(map[*Package]token.Pos)
   115			mm[scope] = m
   116		}
   117		m[pkg] = pos
   118	}
   119	
   120	// addDeclDep adds the dependency edge (check.decl -> to) if check.decl exists
   121	func (check *Checker) addDeclDep(to Object) {
   122		from := check.decl
   123		if from == nil {
   124			return // not in a package-level init expression
   125		}
   126		if _, found := check.objMap[to]; !found {
   127			return // to is not a package-level object
   128		}
   129		from.addDep(to)
   130	}
   131	
   132	func (check *Checker) rememberUntyped(e ast.Expr, lhs bool, mode operandMode, typ *Basic, val constant.Value) {
   133		m := check.untyped
   134		if m == nil {
   135			m = make(map[ast.Expr]exprInfo)
   136			check.untyped = m
   137		}
   138		m[e] = exprInfo{lhs, mode, typ, val}
   139	}
   140	
   141	// later pushes f on to the stack of actions that will be processed later;
   142	// either at the end of the current statement, or in case of a local constant
   143	// or variable declaration, before the constant or variable is in scope
   144	// (so that f still sees the scope before any new declarations).
   145	func (check *Checker) later(f func()) {
   146		check.delayed = append(check.delayed, f)
   147	}
   148	
   149	// push pushes obj onto the object path and returns its index in the path.
   150	func (check *Checker) push(obj Object) int {
   151		check.objPath = append(check.objPath, obj)
   152		return len(check.objPath) - 1
   153	}
   154	
   155	// pop pops and returns the topmost object from the object path.
   156	func (check *Checker) pop() Object {
   157		i := len(check.objPath) - 1
   158		obj := check.objPath[i]
   159		check.objPath[i] = nil
   160		check.objPath = check.objPath[:i]
   161		return obj
   162	}
   163	
   164	// NewChecker returns a new Checker instance for a given package.
   165	// Package files may be added incrementally via checker.Files.
   166	func NewChecker(conf *Config, fset *token.FileSet, pkg *Package, info *Info) *Checker {
   167		// make sure we have a configuration
   168		if conf == nil {
   169			conf = new(Config)
   170		}
   171	
   172		// make sure we have an info struct
   173		if info == nil {
   174			info = new(Info)
   175		}
   176	
   177		return &Checker{
   178			conf:   conf,
   179			fset:   fset,
   180			pkg:    pkg,
   181			Info:   info,
   182			objMap: make(map[Object]*declInfo),
   183			impMap: make(map[importKey]*Package),
   184		}
   185	}
   186	
   187	// initFiles initializes the files-specific portion of checker.
   188	// The provided files must all belong to the same package.
   189	func (check *Checker) initFiles(files []*ast.File) {
   190		// start with a clean slate (check.Files may be called multiple times)
   191		check.files = nil
   192		check.unusedDotImports = nil
   193	
   194		check.firstErr = nil
   195		check.methods = nil
   196		// Don't clear the interfaces cache! It's important that we don't recompute
   197		// ifaceInfos repeatedly (due to multiple check.Files calls) because when
   198		// they are recomputed, they are not used in the context of their original
   199		// declaration (because those types are already type-checked, typically) and
   200		// then they will get the wrong receiver types, which matters for go/types
   201		// clients. It is also safe to not reset the interfaces cache because files
   202		// added to a package cannot change (add methods to) existing interface types;
   203		// they can only add new interfaces. See also the respective comment in
   204		// checker.infoFromTypeName (interfaces.go). Was bug - see issue #29029.
   205		check.untyped = nil
   206		check.delayed = nil
   207	
   208		// determine package name and collect valid files
   209		pkg := check.pkg
   210		for _, file := range files {
   211			switch name := file.Name.Name; pkg.name {
   212			case "":
   213				if name != "_" {
   214					pkg.name = name
   215				} else {
   216					check.errorf(file.Name.Pos(), "invalid package name _")
   217				}
   218				fallthrough
   219	
   220			case name:
   221				check.files = append(check.files, file)
   222	
   223			default:
   224				check.errorf(file.Package, "package %s; expected %s", name, pkg.name)
   225				// ignore this file
   226			}
   227		}
   228	}
   229	
   230	// A bailout panic is used for early termination.
   231	type bailout struct{}
   232	
   233	func (check *Checker) handleBailout(err *error) {
   234		switch p := recover().(type) {
   235		case nil, bailout:
   236			// normal return or early exit
   237			*err = check.firstErr
   238		default:
   239			// re-panic
   240			panic(p)
   241		}
   242	}
   243	
   244	// Files checks the provided files as part of the checker's package.
   245	func (check *Checker) Files(files []*ast.File) error { return check.checkFiles(files) }
   246	
   247	func (check *Checker) checkFiles(files []*ast.File) (err error) {
   248		defer check.handleBailout(&err)
   249	
   250		check.initFiles(files)
   251	
   252		check.collectObjects()
   253	
   254		check.packageObjects()
   255	
   256		check.processDelayed(0) // incl. all functions
   257	
   258		check.initOrder()
   259	
   260		if !check.conf.DisableUnusedImportCheck {
   261			check.unusedImports()
   262		}
   263	
   264		check.recordUntyped()
   265	
   266		check.pkg.complete = true
   267		return
   268	}
   269	
   270	func (check *Checker) recordUntyped() {
   271		if !debug && check.Types == nil {
   272			return // nothing to do
   273		}
   274	
   275		for x, info := range check.untyped {
   276			if debug && isTyped(info.typ) {
   277				check.dump("%v: %s (type %s) is typed", x.Pos(), x, info.typ)
   278				unreachable()
   279			}
   280			check.recordTypeAndValue(x, info.mode, info.typ, info.val)
   281		}
   282	}
   283	
   284	func (check *Checker) recordTypeAndValue(x ast.Expr, mode operandMode, typ Type, val constant.Value) {
   285		assert(x != nil)
   286		assert(typ != nil)
   287		if mode == invalid {
   288			return // omit
   289		}
   290		assert(typ != nil)
   291		if mode == constant_ {
   292			assert(val != nil)
   293			assert(typ == Typ[Invalid] || isConstType(typ))
   294		}
   295		if m := check.Types; m != nil {
   296			m[x] = TypeAndValue{mode, typ, val}
   297		}
   298	}
   299	
   300	func (check *Checker) recordBuiltinType(f ast.Expr, sig *Signature) {
   301		// f must be a (possibly parenthesized) identifier denoting a built-in
   302		// (built-ins in package unsafe always produce a constant result and
   303		// we don't record their signatures, so we don't see qualified idents
   304		// here): record the signature for f and possible children.
   305		for {
   306			check.recordTypeAndValue(f, builtin, sig, nil)
   307			switch p := f.(type) {
   308			case *ast.Ident:
   309				return // we're done
   310			case *ast.ParenExpr:
   311				f = p.X
   312			default:
   313				unreachable()
   314			}
   315		}
   316	}
   317	
   318	func (check *Checker) recordCommaOkTypes(x ast.Expr, a [2]Type) {
   319		assert(x != nil)
   320		if a[0] == nil || a[1] == nil {
   321			return
   322		}
   323		assert(isTyped(a[0]) && isTyped(a[1]) && isBoolean(a[1]))
   324		if m := check.Types; m != nil {
   325			for {
   326				tv := m[x]
   327				assert(tv.Type != nil) // should have been recorded already
   328				pos := x.Pos()
   329				tv.Type = NewTuple(
   330					NewVar(pos, check.pkg, "", a[0]),
   331					NewVar(pos, check.pkg, "", a[1]),
   332				)
   333				m[x] = tv
   334				// if x is a parenthesized expression (p.X), update p.X
   335				p, _ := x.(*ast.ParenExpr)
   336				if p == nil {
   337					break
   338				}
   339				x = p.X
   340			}
   341		}
   342	}
   343	
   344	func (check *Checker) recordDef(id *ast.Ident, obj Object) {
   345		assert(id != nil)
   346		if m := check.Defs; m != nil {
   347			m[id] = obj
   348		}
   349	}
   350	
   351	func (check *Checker) recordUse(id *ast.Ident, obj Object) {
   352		assert(id != nil)
   353		assert(obj != nil)
   354		if m := check.Uses; m != nil {
   355			m[id] = obj
   356		}
   357	}
   358	
   359	func (check *Checker) recordImplicit(node ast.Node, obj Object) {
   360		assert(node != nil)
   361		assert(obj != nil)
   362		if m := check.Implicits; m != nil {
   363			m[node] = obj
   364		}
   365	}
   366	
   367	func (check *Checker) recordSelection(x *ast.SelectorExpr, kind SelectionKind, recv Type, obj Object, index []int, indirect bool) {
   368		assert(obj != nil && (recv == nil || len(index) > 0))
   369		check.recordUse(x.Sel, obj)
   370		if m := check.Selections; m != nil {
   371			m[x] = &Selection{kind, recv, obj, index, indirect}
   372		}
   373	}
   374	
   375	func (check *Checker) recordScope(node ast.Node, scope *Scope) {
   376		assert(node != nil)
   377		assert(scope != nil)
   378		if m := check.Scopes; m != nil {
   379			m[node] = scope
   380		}
   381	}
   382	

View as plain text