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