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 7package types 8 9import ( 10 "go/ast" 11 "go/constant" 12 "go/token" 13) 14 15// debugging/development support 16const ( 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// 32const strict = false 33 34// exprInfo stores information about an untyped expression. 35type 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. 43type 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. 55func (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). 66type 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. 72type 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. 106func (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 121func (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 132func (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). 145func (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. 150func (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. 156func (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. 166func 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. 189func (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. 231type bailout struct{} 232 233func (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. 245func (check *Checker) Files(files []*ast.File) error { return check.checkFiles(files) } 246 247func (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 270func (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 284func (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 300func (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 318func (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 344func (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 351func (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 359func (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 367func (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 375func (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