...
Run Format

Source file src/go/types/resolver.go

Documentation: go/types

     1  // Copyright 2013 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  package types
     6  
     7  import (
     8  	"fmt"
     9  	"go/ast"
    10  	"go/constant"
    11  	"go/token"
    12  	"strconv"
    13  	"strings"
    14  	"unicode"
    15  )
    16  
    17  // A declInfo describes a package-level const, type, var, or func declaration.
    18  type declInfo struct {
    19  	file  *Scope        // scope of file containing this declaration
    20  	lhs   []*Var        // lhs of n:1 variable declarations, or nil
    21  	typ   ast.Expr      // type, or nil
    22  	init  ast.Expr      // init/orig expression, or nil
    23  	fdecl *ast.FuncDecl // func declaration, or nil
    24  	alias bool          // type alias declaration
    25  
    26  	// The deps field tracks initialization expression dependencies.
    27  	// As a special (overloaded) case, it also tracks dependencies of
    28  	// interface types on embedded interfaces (see ordering.go).
    29  	deps objSet // lazily initialized
    30  }
    31  
    32  // An objSet is simply a set of objects.
    33  type objSet map[Object]bool
    34  
    35  // hasInitializer reports whether the declared object has an initialization
    36  // expression or function body.
    37  func (d *declInfo) hasInitializer() bool {
    38  	return d.init != nil || d.fdecl != nil && d.fdecl.Body != nil
    39  }
    40  
    41  // addDep adds obj to the set of objects d's init expression depends on.
    42  func (d *declInfo) addDep(obj Object) {
    43  	m := d.deps
    44  	if m == nil {
    45  		m = make(objSet)
    46  		d.deps = m
    47  	}
    48  	m[obj] = true
    49  }
    50  
    51  // arityMatch checks that the lhs and rhs of a const or var decl
    52  // have the appropriate number of names and init exprs. For const
    53  // decls, init is the value spec providing the init exprs; for
    54  // var decls, init is nil (the init exprs are in s in this case).
    55  func (check *Checker) arityMatch(s, init *ast.ValueSpec) {
    56  	l := len(s.Names)
    57  	r := len(s.Values)
    58  	if init != nil {
    59  		r = len(init.Values)
    60  	}
    61  
    62  	switch {
    63  	case init == nil && r == 0:
    64  		// var decl w/o init expr
    65  		if s.Type == nil {
    66  			check.errorf(s.Pos(), "missing type or init expr")
    67  		}
    68  	case l < r:
    69  		if l < len(s.Values) {
    70  			// init exprs from s
    71  			n := s.Values[l]
    72  			check.errorf(n.Pos(), "extra init expr %s", n)
    73  			// TODO(gri) avoid declared but not used error here
    74  		} else {
    75  			// init exprs "inherited"
    76  			check.errorf(s.Pos(), "extra init expr at %s", check.fset.Position(init.Pos()))
    77  			// TODO(gri) avoid declared but not used error here
    78  		}
    79  	case l > r && (init != nil || r != 1):
    80  		n := s.Names[r]
    81  		check.errorf(n.Pos(), "missing init expr for %s", n)
    82  	}
    83  }
    84  
    85  func validatedImportPath(path string) (string, error) {
    86  	s, err := strconv.Unquote(path)
    87  	if err != nil {
    88  		return "", err
    89  	}
    90  	if s == "" {
    91  		return "", fmt.Errorf("empty string")
    92  	}
    93  	const illegalChars = `!"#$%&'()*,:;<=>?[\]^{|}` + "`\uFFFD"
    94  	for _, r := range s {
    95  		if !unicode.IsGraphic(r) || unicode.IsSpace(r) || strings.ContainsRune(illegalChars, r) {
    96  			return s, fmt.Errorf("invalid character %#U", r)
    97  		}
    98  	}
    99  	return s, nil
   100  }
   101  
   102  // declarePkgObj declares obj in the package scope, records its ident -> obj mapping,
   103  // and updates check.objMap. The object must not be a function or method.
   104  func (check *Checker) declarePkgObj(ident *ast.Ident, obj Object, d *declInfo) {
   105  	assert(ident.Name == obj.Name())
   106  
   107  	// spec: "A package-scope or file-scope identifier with name init
   108  	// may only be declared to be a function with this (func()) signature."
   109  	if ident.Name == "init" {
   110  		check.errorf(ident.Pos(), "cannot declare init - must be func")
   111  		return
   112  	}
   113  
   114  	// spec: "The main package must have package name main and declare
   115  	// a function main that takes no arguments and returns no value."
   116  	if ident.Name == "main" && check.pkg.name == "main" {
   117  		check.errorf(ident.Pos(), "cannot declare main - must be func")
   118  		return
   119  	}
   120  
   121  	check.declare(check.pkg.scope, ident, obj, token.NoPos)
   122  	check.objMap[obj] = d
   123  	obj.setOrder(uint32(len(check.objMap)))
   124  }
   125  
   126  // filename returns a filename suitable for debugging output.
   127  func (check *Checker) filename(fileNo int) string {
   128  	file := check.files[fileNo]
   129  	if pos := file.Pos(); pos.IsValid() {
   130  		return check.fset.File(pos).Name()
   131  	}
   132  	return fmt.Sprintf("file[%d]", fileNo)
   133  }
   134  
   135  func (check *Checker) importPackage(pos token.Pos, path, dir string) *Package {
   136  	// If we already have a package for the given (path, dir)
   137  	// pair, use it instead of doing a full import.
   138  	// Checker.impMap only caches packages that are marked Complete
   139  	// or fake (dummy packages for failed imports). Incomplete but
   140  	// non-fake packages do require an import to complete them.
   141  	key := importKey{path, dir}
   142  	imp := check.impMap[key]
   143  	if imp != nil {
   144  		return imp
   145  	}
   146  
   147  	// no package yet => import it
   148  	if path == "C" && check.conf.FakeImportC {
   149  		imp = NewPackage("C", "C")
   150  		imp.fake = true
   151  	} else {
   152  		// ordinary import
   153  		var err error
   154  		if importer := check.conf.Importer; importer == nil {
   155  			err = fmt.Errorf("Config.Importer not installed")
   156  		} else if importerFrom, ok := importer.(ImporterFrom); ok {
   157  			imp, err = importerFrom.ImportFrom(path, dir, 0)
   158  			if imp == nil && err == nil {
   159  				err = fmt.Errorf("Config.Importer.ImportFrom(%s, %s, 0) returned nil but no error", path, dir)
   160  			}
   161  		} else {
   162  			imp, err = importer.Import(path)
   163  			if imp == nil && err == nil {
   164  				err = fmt.Errorf("Config.Importer.Import(%s) returned nil but no error", path)
   165  			}
   166  		}
   167  		// make sure we have a valid package name
   168  		// (errors here can only happen through manipulation of packages after creation)
   169  		if err == nil && imp != nil && (imp.name == "_" || imp.name == "") {
   170  			err = fmt.Errorf("invalid package name: %q", imp.name)
   171  			imp = nil // create fake package below
   172  		}
   173  		if err != nil {
   174  			check.errorf(pos, "could not import %s (%s)", path, err)
   175  			if imp == nil {
   176  				// create a new fake package
   177  				// come up with a sensible package name (heuristic)
   178  				name := path
   179  				if i := len(name); i > 0 && name[i-1] == '/' {
   180  					name = name[:i-1]
   181  				}
   182  				if i := strings.LastIndex(name, "/"); i >= 0 {
   183  					name = name[i+1:]
   184  				}
   185  				imp = NewPackage(path, name)
   186  			}
   187  			// continue to use the package as best as we can
   188  			imp.fake = true // avoid follow-up lookup failures
   189  		}
   190  	}
   191  
   192  	// package should be complete or marked fake, but be cautious
   193  	if imp.complete || imp.fake {
   194  		check.impMap[key] = imp
   195  		return imp
   196  	}
   197  
   198  	// something went wrong (importer may have returned incomplete package without error)
   199  	return nil
   200  }
   201  
   202  // collectObjects collects all file and package objects and inserts them
   203  // into their respective scopes. It also performs imports and associates
   204  // methods with receiver base type names.
   205  func (check *Checker) collectObjects() {
   206  	pkg := check.pkg
   207  
   208  	// pkgImports is the set of packages already imported by any package file seen
   209  	// so far. Used to avoid duplicate entries in pkg.imports. Allocate and populate
   210  	// it (pkg.imports may not be empty if we are checking test files incrementally).
   211  	// Note that pkgImports is keyed by package (and thus package path), not by an
   212  	// importKey value. Two different importKey values may map to the same package
   213  	// which is why we cannot use the check.impMap here.
   214  	var pkgImports = make(map[*Package]bool)
   215  	for _, imp := range pkg.imports {
   216  		pkgImports[imp] = true
   217  	}
   218  
   219  	for fileNo, file := range check.files {
   220  		// The package identifier denotes the current package,
   221  		// but there is no corresponding package object.
   222  		check.recordDef(file.Name, nil)
   223  
   224  		// Use the actual source file extent rather than *ast.File extent since the
   225  		// latter doesn't include comments which appear at the start or end of the file.
   226  		// Be conservative and use the *ast.File extent if we don't have a *token.File.
   227  		pos, end := file.Pos(), file.End()
   228  		if f := check.fset.File(file.Pos()); f != nil {
   229  			pos, end = token.Pos(f.Base()), token.Pos(f.Base()+f.Size())
   230  		}
   231  		fileScope := NewScope(check.pkg.scope, pos, end, check.filename(fileNo))
   232  		check.recordScope(file, fileScope)
   233  
   234  		// determine file directory, necessary to resolve imports
   235  		// FileName may be "" (typically for tests) in which case
   236  		// we get "." as the directory which is what we would want.
   237  		fileDir := dir(check.fset.Position(file.Name.Pos()).Filename)
   238  
   239  		for _, decl := range file.Decls {
   240  			switch d := decl.(type) {
   241  			case *ast.BadDecl:
   242  				// ignore
   243  
   244  			case *ast.GenDecl:
   245  				var last *ast.ValueSpec // last ValueSpec with type or init exprs seen
   246  				for iota, spec := range d.Specs {
   247  					switch s := spec.(type) {
   248  					case *ast.ImportSpec:
   249  						// import package
   250  						path, err := validatedImportPath(s.Path.Value)
   251  						if err != nil {
   252  							check.errorf(s.Path.Pos(), "invalid import path (%s)", err)
   253  							continue
   254  						}
   255  
   256  						imp := check.importPackage(s.Path.Pos(), path, fileDir)
   257  						if imp == nil {
   258  							continue
   259  						}
   260  
   261  						// add package to list of explicit imports
   262  						// (this functionality is provided as a convenience
   263  						// for clients; it is not needed for type-checking)
   264  						if !pkgImports[imp] {
   265  							pkgImports[imp] = true
   266  							pkg.imports = append(pkg.imports, imp)
   267  						}
   268  
   269  						// local name overrides imported package name
   270  						name := imp.name
   271  						if s.Name != nil {
   272  							name = s.Name.Name
   273  							if path == "C" {
   274  								// match cmd/compile (not prescribed by spec)
   275  								check.errorf(s.Name.Pos(), `cannot rename import "C"`)
   276  								continue
   277  							}
   278  							if name == "init" {
   279  								check.errorf(s.Name.Pos(), "cannot declare init - must be func")
   280  								continue
   281  							}
   282  						}
   283  
   284  						obj := NewPkgName(s.Pos(), pkg, name, imp)
   285  						if s.Name != nil {
   286  							// in a dot-import, the dot represents the package
   287  							check.recordDef(s.Name, obj)
   288  						} else {
   289  							check.recordImplicit(s, obj)
   290  						}
   291  
   292  						if path == "C" {
   293  							// match cmd/compile (not prescribed by spec)
   294  							obj.used = true
   295  						}
   296  
   297  						// add import to file scope
   298  						if name == "." {
   299  							// merge imported scope with file scope
   300  							for _, obj := range imp.scope.elems {
   301  								// A package scope may contain non-exported objects,
   302  								// do not import them!
   303  								if obj.Exported() {
   304  									// TODO(gri) When we import a package, we create
   305  									// a new local package object. We should do the
   306  									// same for each dot-imported object. That way
   307  									// they can have correct position information.
   308  									// (We must not modify their existing position
   309  									// information because the same package - found
   310  									// via Config.Packages - may be dot-imported in
   311  									// another package!)
   312  									check.declare(fileScope, nil, obj, token.NoPos)
   313  								}
   314  							}
   315  							// add position to set of dot-import positions for this file
   316  							// (this is only needed for "imported but not used" errors)
   317  							check.addUnusedDotImport(fileScope, imp, s.Pos())
   318  						} else {
   319  							// declare imported package object in file scope
   320  							check.declare(fileScope, nil, obj, token.NoPos)
   321  						}
   322  
   323  					case *ast.ValueSpec:
   324  						switch d.Tok {
   325  						case token.CONST:
   326  							// determine which initialization expressions to use
   327  							switch {
   328  							case s.Type != nil || len(s.Values) > 0:
   329  								last = s
   330  							case last == nil:
   331  								last = new(ast.ValueSpec) // make sure last exists
   332  							}
   333  
   334  							// declare all constants
   335  							for i, name := range s.Names {
   336  								obj := NewConst(name.Pos(), pkg, name.Name, nil, constant.MakeInt64(int64(iota)))
   337  
   338  								var init ast.Expr
   339  								if i < len(last.Values) {
   340  									init = last.Values[i]
   341  								}
   342  
   343  								d := &declInfo{file: fileScope, typ: last.Type, init: init}
   344  								check.declarePkgObj(name, obj, d)
   345  							}
   346  
   347  							check.arityMatch(s, last)
   348  
   349  						case token.VAR:
   350  							lhs := make([]*Var, len(s.Names))
   351  							// If there's exactly one rhs initializer, use
   352  							// the same declInfo d1 for all lhs variables
   353  							// so that each lhs variable depends on the same
   354  							// rhs initializer (n:1 var declaration).
   355  							var d1 *declInfo
   356  							if len(s.Values) == 1 {
   357  								// The lhs elements are only set up after the for loop below,
   358  								// but that's ok because declareVar only collects the declInfo
   359  								// for a later phase.
   360  								d1 = &declInfo{file: fileScope, lhs: lhs, typ: s.Type, init: s.Values[0]}
   361  							}
   362  
   363  							// declare all variables
   364  							for i, name := range s.Names {
   365  								obj := NewVar(name.Pos(), pkg, name.Name, nil)
   366  								lhs[i] = obj
   367  
   368  								d := d1
   369  								if d == nil {
   370  									// individual assignments
   371  									var init ast.Expr
   372  									if i < len(s.Values) {
   373  										init = s.Values[i]
   374  									}
   375  									d = &declInfo{file: fileScope, typ: s.Type, init: init}
   376  								}
   377  
   378  								check.declarePkgObj(name, obj, d)
   379  							}
   380  
   381  							check.arityMatch(s, nil)
   382  
   383  						default:
   384  							check.invalidAST(s.Pos(), "invalid token %s", d.Tok)
   385  						}
   386  
   387  					case *ast.TypeSpec:
   388  						obj := NewTypeName(s.Name.Pos(), pkg, s.Name.Name, nil)
   389  						check.declarePkgObj(s.Name, obj, &declInfo{file: fileScope, typ: s.Type, alias: s.Assign.IsValid()})
   390  
   391  					default:
   392  						check.invalidAST(s.Pos(), "unknown ast.Spec node %T", s)
   393  					}
   394  				}
   395  
   396  			case *ast.FuncDecl:
   397  				name := d.Name.Name
   398  				obj := NewFunc(d.Name.Pos(), pkg, name, nil)
   399  				if d.Recv == nil {
   400  					// regular function
   401  					if name == "init" {
   402  						// don't declare init functions in the package scope - they are invisible
   403  						obj.parent = pkg.scope
   404  						check.recordDef(d.Name, obj)
   405  						// init functions must have a body
   406  						if d.Body == nil {
   407  							check.softErrorf(obj.pos, "missing function body")
   408  						}
   409  					} else {
   410  						check.declare(pkg.scope, d.Name, obj, token.NoPos)
   411  					}
   412  				} else {
   413  					// method
   414  					check.recordDef(d.Name, obj)
   415  					// Associate method with receiver base type name, if possible.
   416  					// Ignore methods that have an invalid receiver, or a blank _
   417  					// receiver name. They will be type-checked later, with regular
   418  					// functions.
   419  					if list := d.Recv.List; len(list) > 0 {
   420  						typ := unparen(list[0].Type)
   421  						if ptr, _ := typ.(*ast.StarExpr); ptr != nil {
   422  							typ = unparen(ptr.X)
   423  						}
   424  						if base, _ := typ.(*ast.Ident); base != nil && base.Name != "_" {
   425  							check.assocMethod(base.Name, obj)
   426  						}
   427  					}
   428  				}
   429  				info := &declInfo{file: fileScope, fdecl: d}
   430  				check.objMap[obj] = info
   431  				obj.setOrder(uint32(len(check.objMap)))
   432  
   433  			default:
   434  				check.invalidAST(d.Pos(), "unknown ast.Decl node %T", d)
   435  			}
   436  		}
   437  	}
   438  
   439  	// verify that objects in package and file scopes have different names
   440  	for _, scope := range check.pkg.scope.children /* file scopes */ {
   441  		for _, obj := range scope.elems {
   442  			if alt := pkg.scope.Lookup(obj.Name()); alt != nil {
   443  				if pkg, ok := obj.(*PkgName); ok {
   444  					check.errorf(alt.Pos(), "%s already declared through import of %s", alt.Name(), pkg.Imported())
   445  					check.reportAltDecl(pkg)
   446  				} else {
   447  					check.errorf(alt.Pos(), "%s already declared through dot-import of %s", alt.Name(), obj.Pkg())
   448  					// TODO(gri) dot-imported objects don't have a position; reportAltDecl won't print anything
   449  					check.reportAltDecl(obj)
   450  				}
   451  			}
   452  		}
   453  	}
   454  }
   455  
   456  // packageObjects typechecks all package objects in objList, but not function bodies.
   457  func (check *Checker) packageObjects(objList []Object) {
   458  	// add new methods to already type-checked types (from a prior Checker.Files call)
   459  	for _, obj := range objList {
   460  		if obj, _ := obj.(*TypeName); obj != nil && obj.typ != nil {
   461  			check.addMethodDecls(obj)
   462  		}
   463  	}
   464  
   465  	// pre-allocate space for type declaration paths so that the underlying array is reused
   466  	typePath := make([]*TypeName, 0, 8)
   467  
   468  	for _, obj := range objList {
   469  		check.objDecl(obj, nil, typePath)
   470  	}
   471  
   472  	// At this point we may have a non-empty check.methods map; this means that not all
   473  	// entries were deleted at the end of typeDecl because the respective receiver base
   474  	// types were not found. In that case, an error was reported when declaring those
   475  	// methods. We can now safely discard this map.
   476  	check.methods = nil
   477  }
   478  
   479  // functionBodies typechecks all function bodies.
   480  func (check *Checker) functionBodies() {
   481  	for _, f := range check.funcs {
   482  		check.funcBody(f.decl, f.name, f.sig, f.body)
   483  	}
   484  }
   485  
   486  // unusedImports checks for unused imports.
   487  func (check *Checker) unusedImports() {
   488  	// if function bodies are not checked, packages' uses are likely missing - don't check
   489  	if check.conf.IgnoreFuncBodies {
   490  		return
   491  	}
   492  
   493  	// spec: "It is illegal (...) to directly import a package without referring to
   494  	// any of its exported identifiers. To import a package solely for its side-effects
   495  	// (initialization), use the blank identifier as explicit package name."
   496  
   497  	// check use of regular imported packages
   498  	for _, scope := range check.pkg.scope.children /* file scopes */ {
   499  		for _, obj := range scope.elems {
   500  			if obj, ok := obj.(*PkgName); ok {
   501  				// Unused "blank imports" are automatically ignored
   502  				// since _ identifiers are not entered into scopes.
   503  				if !obj.used {
   504  					path := obj.imported.path
   505  					base := pkgName(path)
   506  					if obj.name == base {
   507  						check.softErrorf(obj.pos, "%q imported but not used", path)
   508  					} else {
   509  						check.softErrorf(obj.pos, "%q imported but not used as %s", path, obj.name)
   510  					}
   511  				}
   512  			}
   513  		}
   514  	}
   515  
   516  	// check use of dot-imported packages
   517  	for _, unusedDotImports := range check.unusedDotImports {
   518  		for pkg, pos := range unusedDotImports {
   519  			check.softErrorf(pos, "%q imported but not used", pkg.path)
   520  		}
   521  	}
   522  }
   523  
   524  // pkgName returns the package name (last element) of an import path.
   525  func pkgName(path string) string {
   526  	if i := strings.LastIndex(path, "/"); i >= 0 {
   527  		path = path[i+1:]
   528  	}
   529  	return path
   530  }
   531  
   532  // dir makes a good-faith attempt to return the directory
   533  // portion of path. If path is empty, the result is ".".
   534  // (Per the go/build package dependency tests, we cannot import
   535  // path/filepath and simply use filepath.Dir.)
   536  func dir(path string) string {
   537  	if i := strings.LastIndexAny(path, `/\`); i > 0 {
   538  		return path[:i]
   539  	}
   540  	// i <= 0
   541  	return "."
   542  }
   543  

View as plain text