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