Home | History | Annotate | Download | only in types
      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 // funcInfo stores the information required for type-checking a function.
     43 type funcInfo struct {
     44 	name string    // for debugging/tracing only
     45 	decl *declInfo // for cycle detection
     46 	sig  *Signature
     47 	body *ast.BlockStmt
     48 }
     49 
     50 // A context represents the context within which an object is type-checked.
     51 type context struct {
     52 	decl          *declInfo      // package-level declaration whose init expression/function body is checked
     53 	scope         *Scope         // top-most scope for lookups
     54 	iota          constant.Value // value of iota in a constant declaration; nil otherwise
     55 	sig           *Signature     // function signature if inside a function; nil otherwise
     56 	hasLabel      bool           // set if a function makes use of labels (only ~1% of functions); unused outside functions
     57 	hasCallOrRecv bool           // set if an expression contains a function call or channel receive operation
     58 }
     59 
     60 // A Checker maintains the state of the type checker.
     61 // It must be created with NewChecker.
     62 type Checker struct {
     63 	// package information
     64 	// (initialized by NewChecker, valid for the life-time of checker)
     65 	conf *Config
     66 	fset *token.FileSet
     67 	pkg  *Package
     68 	*Info
     69 	objMap map[Object]*declInfo // maps package-level object to declaration info
     70 
     71 	// information collected during type-checking of a set of package files
     72 	// (initialized by Files, valid only for the duration of check.Files;
     73 	// maps and lists are allocated on demand)
     74 	files            []*ast.File                       // package files
     75 	unusedDotImports map[*Scope]map[*Package]token.Pos // positions of unused dot-imported packages for each file scope
     76 
     77 	firstErr error                 // first error encountered
     78 	methods  map[string][]*Func    // maps type names to associated methods
     79 	untyped  map[ast.Expr]exprInfo // map of expressions without final type
     80 	funcs    []funcInfo            // list of functions to type-check
     81 	delayed  []func()              // delayed checks requiring fully setup types
     82 
     83 	// context within which the current object is type-checked
     84 	// (valid only for the duration of type-checking a specific object)
     85 	context
     86 	pos token.Pos // if valid, identifiers are looked up as if at position pos (used by Eval)
     87 
     88 	// debugging
     89 	indent int // indentation for tracing
     90 }
     91 
     92 // addUnusedImport adds the position of a dot-imported package
     93 // pkg to the map of dot imports for the given file scope.
     94 func (check *Checker) addUnusedDotImport(scope *Scope, pkg *Package, pos token.Pos) {
     95 	mm := check.unusedDotImports
     96 	if mm == nil {
     97 		mm = make(map[*Scope]map[*Package]token.Pos)
     98 		check.unusedDotImports = mm
     99 	}
    100 	m := mm[scope]
    101 	if m == nil {
    102 		m = make(map[*Package]token.Pos)
    103 		mm[scope] = m
    104 	}
    105 	m[pkg] = pos
    106 }
    107 
    108 // addDeclDep adds the dependency edge (check.decl -> to) if check.decl exists
    109 func (check *Checker) addDeclDep(to Object) {
    110 	from := check.decl
    111 	if from == nil {
    112 		return // not in a package-level init expression
    113 	}
    114 	if _, found := check.objMap[to]; !found {
    115 		return // to is not a package-level object
    116 	}
    117 	from.addDep(to)
    118 }
    119 
    120 func (check *Checker) assocMethod(tname string, meth *Func) {
    121 	m := check.methods
    122 	if m == nil {
    123 		m = make(map[string][]*Func)
    124 		check.methods = m
    125 	}
    126 	m[tname] = append(m[tname], meth)
    127 }
    128 
    129 func (check *Checker) rememberUntyped(e ast.Expr, lhs bool, mode operandMode, typ *Basic, val constant.Value) {
    130 	m := check.untyped
    131 	if m == nil {
    132 		m = make(map[ast.Expr]exprInfo)
    133 		check.untyped = m
    134 	}
    135 	m[e] = exprInfo{lhs, mode, typ, val}
    136 }
    137 
    138 func (check *Checker) later(name string, decl *declInfo, sig *Signature, body *ast.BlockStmt) {
    139 	check.funcs = append(check.funcs, funcInfo{name, decl, sig, body})
    140 }
    141 
    142 func (check *Checker) delay(f func()) {
    143 	check.delayed = append(check.delayed, f)
    144 }
    145 
    146 // NewChecker returns a new Checker instance for a given package.
    147 // Package files may be added incrementally via checker.Files.
    148 func NewChecker(conf *Config, fset *token.FileSet, pkg *Package, info *Info) *Checker {
    149 	// make sure we have a configuration
    150 	if conf == nil {
    151 		conf = new(Config)
    152 	}
    153 
    154 	// make sure we have an info struct
    155 	if info == nil {
    156 		info = new(Info)
    157 	}
    158 
    159 	return &Checker{
    160 		conf:   conf,
    161 		fset:   fset,
    162 		pkg:    pkg,
    163 		Info:   info,
    164 		objMap: make(map[Object]*declInfo),
    165 	}
    166 }
    167 
    168 // initFiles initializes the files-specific portion of checker.
    169 // The provided files must all belong to the same package.
    170 func (check *Checker) initFiles(files []*ast.File) {
    171 	// start with a clean slate (check.Files may be called multiple times)
    172 	check.files = nil
    173 	check.unusedDotImports = nil
    174 
    175 	check.firstErr = nil
    176 	check.methods = nil
    177 	check.untyped = nil
    178 	check.funcs = nil
    179 	check.delayed = nil
    180 
    181 	// determine package name and collect valid files
    182 	pkg := check.pkg
    183 	for _, file := range files {
    184 		switch name := file.Name.Name; pkg.name {
    185 		case "":
    186 			if name != "_" {
    187 				pkg.name = name
    188 			} else {
    189 				check.errorf(file.Name.Pos(), "invalid package name _")
    190 			}
    191 			fallthrough
    192 
    193 		case name:
    194 			check.files = append(check.files, file)
    195 
    196 		default:
    197 			check.errorf(file.Package, "package %s; expected %s", name, pkg.name)
    198 			// ignore this file
    199 		}
    200 	}
    201 }
    202 
    203 // A bailout panic is used for early termination.
    204 type bailout struct{}
    205 
    206 func (check *Checker) handleBailout(err *error) {
    207 	switch p := recover().(type) {
    208 	case nil, bailout:
    209 		// normal return or early exit
    210 		*err = check.firstErr
    211 	default:
    212 		// re-panic
    213 		panic(p)
    214 	}
    215 }
    216 
    217 // Files checks the provided files as part of the checker's package.
    218 func (check *Checker) Files(files []*ast.File) error { return check.checkFiles(files) }
    219 
    220 func (check *Checker) checkFiles(files []*ast.File) (err error) {
    221 	defer check.handleBailout(&err)
    222 
    223 	check.initFiles(files)
    224 
    225 	check.collectObjects()
    226 
    227 	check.packageObjects(check.resolveOrder())
    228 
    229 	check.functionBodies()
    230 
    231 	check.initOrder()
    232 
    233 	if !check.conf.DisableUnusedImportCheck {
    234 		check.unusedImports()
    235 	}
    236 
    237 	// perform delayed checks
    238 	for _, f := range check.delayed {
    239 		f()
    240 	}
    241 
    242 	check.recordUntyped()
    243 
    244 	check.pkg.complete = true
    245 	return
    246 }
    247 
    248 func (check *Checker) recordUntyped() {
    249 	if !debug && check.Types == nil {
    250 		return // nothing to do
    251 	}
    252 
    253 	for x, info := range check.untyped {
    254 		if debug && isTyped(info.typ) {
    255 			check.dump("%s: %s (type %s) is typed", x.Pos(), x, info.typ)
    256 			unreachable()
    257 		}
    258 		check.recordTypeAndValue(x, info.mode, info.typ, info.val)
    259 	}
    260 }
    261 
    262 func (check *Checker) recordTypeAndValue(x ast.Expr, mode operandMode, typ Type, val constant.Value) {
    263 	assert(x != nil)
    264 	assert(typ != nil)
    265 	if mode == invalid {
    266 		return // omit
    267 	}
    268 	assert(typ != nil)
    269 	if mode == constant_ {
    270 		assert(val != nil)
    271 		assert(typ == Typ[Invalid] || isConstType(typ))
    272 	}
    273 	if m := check.Types; m != nil {
    274 		m[x] = TypeAndValue{mode, typ, val}
    275 	}
    276 }
    277 
    278 func (check *Checker) recordBuiltinType(f ast.Expr, sig *Signature) {
    279 	// f must be a (possibly parenthesized) identifier denoting a built-in
    280 	// (built-ins in package unsafe always produce a constant result and
    281 	// we don't record their signatures, so we don't see qualified idents
    282 	// here): record the signature for f and possible children.
    283 	for {
    284 		check.recordTypeAndValue(f, builtin, sig, nil)
    285 		switch p := f.(type) {
    286 		case *ast.Ident:
    287 			return // we're done
    288 		case *ast.ParenExpr:
    289 			f = p.X
    290 		default:
    291 			unreachable()
    292 		}
    293 	}
    294 }
    295 
    296 func (check *Checker) recordCommaOkTypes(x ast.Expr, a [2]Type) {
    297 	assert(x != nil)
    298 	if a[0] == nil || a[1] == nil {
    299 		return
    300 	}
    301 	assert(isTyped(a[0]) && isTyped(a[1]) && isBoolean(a[1]))
    302 	if m := check.Types; m != nil {
    303 		for {
    304 			tv := m[x]
    305 			assert(tv.Type != nil) // should have been recorded already
    306 			pos := x.Pos()
    307 			tv.Type = NewTuple(
    308 				NewVar(pos, check.pkg, "", a[0]),
    309 				NewVar(pos, check.pkg, "", a[1]),
    310 			)
    311 			m[x] = tv
    312 			// if x is a parenthesized expression (p.X), update p.X
    313 			p, _ := x.(*ast.ParenExpr)
    314 			if p == nil {
    315 				break
    316 			}
    317 			x = p.X
    318 		}
    319 	}
    320 }
    321 
    322 func (check *Checker) recordDef(id *ast.Ident, obj Object) {
    323 	assert(id != nil)
    324 	if m := check.Defs; m != nil {
    325 		m[id] = obj
    326 	}
    327 }
    328 
    329 func (check *Checker) recordUse(id *ast.Ident, obj Object) {
    330 	assert(id != nil)
    331 	assert(obj != nil)
    332 	if m := check.Uses; m != nil {
    333 		m[id] = obj
    334 	}
    335 }
    336 
    337 func (check *Checker) recordImplicit(node ast.Node, obj Object) {
    338 	assert(node != nil)
    339 	assert(obj != nil)
    340 	if m := check.Implicits; m != nil {
    341 		m[node] = obj
    342 	}
    343 }
    344 
    345 func (check *Checker) recordSelection(x *ast.SelectorExpr, kind SelectionKind, recv Type, obj Object, index []int, indirect bool) {
    346 	assert(obj != nil && (recv == nil || len(index) > 0))
    347 	check.recordUse(x.Sel, obj)
    348 	if m := check.Selections; m != nil {
    349 		m[x] = &Selection{kind, recv, obj, index, indirect}
    350 	}
    351 }
    352 
    353 func (check *Checker) recordScope(node ast.Node, scope *Scope) {
    354 	assert(node != nil)
    355 	assert(scope != nil)
    356 	if m := check.Scopes; m != nil {
    357 		m[node] = scope
    358 	}
    359 }
    360