analysis.go

     1  // Copyright 2020 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 analysisinternal provides gopls' internal analyses with a
     6  // number of helper functions that operate on typed syntax trees.
     7  package analysisinternal
     8  
     9  import (
    10  	"bytes"
    11  	"fmt"
    12  	"go/ast"
    13  	"go/token"
    14  	"go/types"
    15  	"os"
    16  	pathpkg "path"
    17  	"strconv"
    18  
    19  	"golang.org/x/tools/go/analysis"
    20  	"golang.org/x/tools/internal/aliases"
    21  )
    22  
    23  func TypeErrorEndPos(fset *token.FileSet, src []byte, start token.Pos) token.Pos {
    24  	// Get the end position for the type error.
    25  	offset, end := fset.PositionFor(start, false).Offset, start
    26  	if offset >= len(src) {
    27  		return end
    28  	}
    29  	if width := bytes.IndexAny(src[offset:], " \n,():;[]+-*"); width > 0 {
    30  		end = start + token.Pos(width)
    31  	}
    32  	return end
    33  }
    34  
    35  func ZeroValue(f *ast.File, pkg *types.Package, typ types.Type) ast.Expr {
    36  	// TODO(adonovan): think about generics, and also generic aliases.
    37  	under := aliases.Unalias(typ)
    38  	// Don't call Underlying unconditionally: although it removes
    39  	// Named and Alias, it also removes TypeParam.
    40  	if n, ok := under.(*types.Named); ok {
    41  		under = n.Underlying()
    42  	}
    43  	switch under := under.(type) {
    44  	case *types.Basic:
    45  		switch {
    46  		case under.Info()&types.IsNumeric != 0:
    47  			return &ast.BasicLit{Kind: token.INT, Value: "0"}
    48  		case under.Info()&types.IsBoolean != 0:
    49  			return &ast.Ident{Name: "false"}
    50  		case under.Info()&types.IsString != 0:
    51  			return &ast.BasicLit{Kind: token.STRING, Value: `""`}
    52  		default:
    53  			panic(fmt.Sprintf("unknown basic type %v", under))
    54  		}
    55  	case *types.Chan, *types.Interface, *types.Map, *types.Pointer, *types.Signature, *types.Slice, *types.Array:
    56  		return ast.NewIdent("nil")
    57  	case *types.Struct:
    58  		texpr := TypeExpr(f, pkg, typ) // typ because we want the name here.
    59  		if texpr == nil {
    60  			return nil
    61  		}
    62  		return &ast.CompositeLit{
    63  			Type: texpr,
    64  		}
    65  	}
    66  	return nil
    67  }
    68  
    69  // IsZeroValue checks whether the given expression is a 'zero value' (as determined by output of
    70  // analysisinternal.ZeroValue)
    71  func IsZeroValue(expr ast.Expr) bool {
    72  	switch e := expr.(type) {
    73  	case *ast.BasicLit:
    74  		return e.Value == "0" || e.Value == `""`
    75  	case *ast.Ident:
    76  		return e.Name == "nil" || e.Name == "false"
    77  	default:
    78  		return false
    79  	}
    80  }
    81  
    82  // TypeExpr returns syntax for the specified type. References to
    83  // named types from packages other than pkg are qualified by an appropriate
    84  // package name, as defined by the import environment of file.
    85  func TypeExpr(f *ast.File, pkg *types.Package, typ types.Type) ast.Expr {
    86  	switch t := typ.(type) {
    87  	case *types.Basic:
    88  		switch t.Kind() {
    89  		case types.UnsafePointer:
    90  			return &ast.SelectorExpr{X: ast.NewIdent("unsafe"), Sel: ast.NewIdent("Pointer")}
    91  		default:
    92  			return ast.NewIdent(t.Name())
    93  		}
    94  	case *types.Pointer:
    95  		x := TypeExpr(f, pkg, t.Elem())
    96  		if x == nil {
    97  			return nil
    98  		}
    99  		return &ast.UnaryExpr{
   100  			Op: token.MUL,
   101  			X:  x,
   102  		}
   103  	case *types.Array:
   104  		elt := TypeExpr(f, pkg, t.Elem())
   105  		if elt == nil {
   106  			return nil
   107  		}
   108  		return &ast.ArrayType{
   109  			Len: &ast.BasicLit{
   110  				Kind:  token.INT,
   111  				Value: fmt.Sprintf("%d", t.Len()),
   112  			},
   113  			Elt: elt,
   114  		}
   115  	case *types.Slice:
   116  		elt := TypeExpr(f, pkg, t.Elem())
   117  		if elt == nil {
   118  			return nil
   119  		}
   120  		return &ast.ArrayType{
   121  			Elt: elt,
   122  		}
   123  	case *types.Map:
   124  		key := TypeExpr(f, pkg, t.Key())
   125  		value := TypeExpr(f, pkg, t.Elem())
   126  		if key == nil || value == nil {
   127  			return nil
   128  		}
   129  		return &ast.MapType{
   130  			Key:   key,
   131  			Value: value,
   132  		}
   133  	case *types.Chan:
   134  		dir := ast.ChanDir(t.Dir())
   135  		if t.Dir() == types.SendRecv {
   136  			dir = ast.SEND | ast.RECV
   137  		}
   138  		value := TypeExpr(f, pkg, t.Elem())
   139  		if value == nil {
   140  			return nil
   141  		}
   142  		return &ast.ChanType{
   143  			Dir:   dir,
   144  			Value: value,
   145  		}
   146  	case *types.Signature:
   147  		var params []*ast.Field
   148  		for i := 0; i < t.Params().Len(); i++ {
   149  			p := TypeExpr(f, pkg, t.Params().At(i).Type())
   150  			if p == nil {
   151  				return nil
   152  			}
   153  			params = append(params, &ast.Field{
   154  				Type: p,
   155  				Names: []*ast.Ident{
   156  					{
   157  						Name: t.Params().At(i).Name(),
   158  					},
   159  				},
   160  			})
   161  		}
   162  		if t.Variadic() {
   163  			last := params[len(params)-1]
   164  			last.Type = &ast.Ellipsis{Elt: last.Type.(*ast.ArrayType).Elt}
   165  		}
   166  		var returns []*ast.Field
   167  		for i := 0; i < t.Results().Len(); i++ {
   168  			r := TypeExpr(f, pkg, t.Results().At(i).Type())
   169  			if r == nil {
   170  				return nil
   171  			}
   172  			returns = append(returns, &ast.Field{
   173  				Type: r,
   174  			})
   175  		}
   176  		return &ast.FuncType{
   177  			Params: &ast.FieldList{
   178  				List: params,
   179  			},
   180  			Results: &ast.FieldList{
   181  				List: returns,
   182  			},
   183  		}
   184  	case interface{ Obj() *types.TypeName }: // *types.{Alias,Named,TypeParam}
   185  		if t.Obj().Pkg() == nil {
   186  			return ast.NewIdent(t.Obj().Name())
   187  		}
   188  		if t.Obj().Pkg() == pkg {
   189  			return ast.NewIdent(t.Obj().Name())
   190  		}
   191  		pkgName := t.Obj().Pkg().Name()
   192  
   193  		// If the file already imports the package under another name, use that.
   194  		for _, cand := range f.Imports {
   195  			if path, _ := strconv.Unquote(cand.Path.Value); path == t.Obj().Pkg().Path() {
   196  				if cand.Name != nil && cand.Name.Name != "" {
   197  					pkgName = cand.Name.Name
   198  				}
   199  			}
   200  		}
   201  		if pkgName == "." {
   202  			return ast.NewIdent(t.Obj().Name())
   203  		}
   204  		return &ast.SelectorExpr{
   205  			X:   ast.NewIdent(pkgName),
   206  			Sel: ast.NewIdent(t.Obj().Name()),
   207  		}
   208  	case *types.Struct:
   209  		return ast.NewIdent(t.String())
   210  	case *types.Interface:
   211  		return ast.NewIdent(t.String())
   212  	default:
   213  		return nil
   214  	}
   215  }
   216  
   217  // StmtToInsertVarBefore returns the ast.Stmt before which we can safely insert a new variable.
   218  // Some examples:
   219  //
   220  // Basic Example:
   221  // z := 1
   222  // y := z + x
   223  // If x is undeclared, then this function would return `y := z + x`, so that we
   224  // can insert `x := ` on the line before `y := z + x`.
   225  //
   226  // If stmt example:
   227  // if z == 1 {
   228  // } else if z == y {}
   229  // If y is undeclared, then this function would return `if z == 1 {`, because we cannot
   230  // insert a statement between an if and an else if statement. As a result, we need to find
   231  // the top of the if chain to insert `y := ` before.
   232  func StmtToInsertVarBefore(path []ast.Node) ast.Stmt {
   233  	enclosingIndex := -1
   234  	for i, p := range path {
   235  		if _, ok := p.(ast.Stmt); ok {
   236  			enclosingIndex = i
   237  			break
   238  		}
   239  	}
   240  	if enclosingIndex == -1 {
   241  		return nil
   242  	}
   243  	enclosingStmt := path[enclosingIndex]
   244  	switch enclosingStmt.(type) {
   245  	case *ast.IfStmt:
   246  		// The enclosingStmt is inside of the if declaration,
   247  		// We need to check if we are in an else-if stmt and
   248  		// get the base if statement.
   249  		return baseIfStmt(path, enclosingIndex)
   250  	case *ast.CaseClause:
   251  		// Get the enclosing switch stmt if the enclosingStmt is
   252  		// inside of the case statement.
   253  		for i := enclosingIndex + 1; i < len(path); i++ {
   254  			if node, ok := path[i].(*ast.SwitchStmt); ok {
   255  				return node
   256  			} else if node, ok := path[i].(*ast.TypeSwitchStmt); ok {
   257  				return node
   258  			}
   259  		}
   260  	}
   261  	if len(path) <= enclosingIndex+1 {
   262  		return enclosingStmt.(ast.Stmt)
   263  	}
   264  	// Check if the enclosing statement is inside another node.
   265  	switch expr := path[enclosingIndex+1].(type) {
   266  	case *ast.IfStmt:
   267  		// Get the base if statement.
   268  		return baseIfStmt(path, enclosingIndex+1)
   269  	case *ast.ForStmt:
   270  		if expr.Init == enclosingStmt || expr.Post == enclosingStmt {
   271  			return expr
   272  		}
   273  	case *ast.SwitchStmt, *ast.TypeSwitchStmt:
   274  		return expr.(ast.Stmt)
   275  	}
   276  	return enclosingStmt.(ast.Stmt)
   277  }
   278  
   279  // baseIfStmt walks up the if/else-if chain until we get to
   280  // the top of the current if chain.
   281  func baseIfStmt(path []ast.Node, index int) ast.Stmt {
   282  	stmt := path[index]
   283  	for i := index + 1; i < len(path); i++ {
   284  		if node, ok := path[i].(*ast.IfStmt); ok && node.Else == stmt {
   285  			stmt = node
   286  			continue
   287  		}
   288  		break
   289  	}
   290  	return stmt.(ast.Stmt)
   291  }
   292  
   293  // WalkASTWithParent walks the AST rooted at n. The semantics are
   294  // similar to ast.Inspect except it does not call f(nil).
   295  func WalkASTWithParent(n ast.Node, f func(n ast.Node, parent ast.Node) bool) {
   296  	var ancestors []ast.Node
   297  	ast.Inspect(n, func(n ast.Node) (recurse bool) {
   298  		if n == nil {
   299  			ancestors = ancestors[:len(ancestors)-1]
   300  			return false
   301  		}
   302  
   303  		var parent ast.Node
   304  		if len(ancestors) > 0 {
   305  			parent = ancestors[len(ancestors)-1]
   306  		}
   307  		ancestors = append(ancestors, n)
   308  		return f(n, parent)
   309  	})
   310  }
   311  
   312  // MatchingIdents finds the names of all identifiers in 'node' that match any of the given types.
   313  // 'pos' represents the position at which the identifiers may be inserted. 'pos' must be within
   314  // the scope of each of identifier we select. Otherwise, we will insert a variable at 'pos' that
   315  // is unrecognized.
   316  func MatchingIdents(typs []types.Type, node ast.Node, pos token.Pos, info *types.Info, pkg *types.Package) map[types.Type][]string {
   317  
   318  	// Initialize matches to contain the variable types we are searching for.
   319  	matches := make(map[types.Type][]string)
   320  	for _, typ := range typs {
   321  		if typ == nil {
   322  			continue // TODO(adonovan): is this reachable?
   323  		}
   324  		matches[typ] = nil // create entry
   325  	}
   326  
   327  	seen := map[types.Object]struct{}{}
   328  	ast.Inspect(node, func(n ast.Node) bool {
   329  		if n == nil {
   330  			return false
   331  		}
   332  		// Prevent circular definitions. If 'pos' is within an assignment statement, do not
   333  		// allow any identifiers in that assignment statement to be selected. Otherwise,
   334  		// we could do the following, where 'x' satisfies the type of 'f0':
   335  		//
   336  		// x := fakeStruct{f0: x}
   337  		//
   338  		if assign, ok := n.(*ast.AssignStmt); ok && pos > assign.Pos() && pos <= assign.End() {
   339  			return false
   340  		}
   341  		if n.End() > pos {
   342  			return n.Pos() <= pos
   343  		}
   344  		ident, ok := n.(*ast.Ident)
   345  		if !ok || ident.Name == "_" {
   346  			return true
   347  		}
   348  		obj := info.Defs[ident]
   349  		if obj == nil || obj.Type() == nil {
   350  			return true
   351  		}
   352  		if _, ok := obj.(*types.TypeName); ok {
   353  			return true
   354  		}
   355  		// Prevent duplicates in matches' values.
   356  		if _, ok = seen[obj]; ok {
   357  			return true
   358  		}
   359  		seen[obj] = struct{}{}
   360  		// Find the scope for the given position. Then, check whether the object
   361  		// exists within the scope.
   362  		innerScope := pkg.Scope().Innermost(pos)
   363  		if innerScope == nil {
   364  			return true
   365  		}
   366  		_, foundObj := innerScope.LookupParent(ident.Name, pos)
   367  		if foundObj != obj {
   368  			return true
   369  		}
   370  		// The object must match one of the types that we are searching for.
   371  		// TODO(adonovan): opt: use typeutil.Map?
   372  		if names, ok := matches[obj.Type()]; ok {
   373  			matches[obj.Type()] = append(names, ident.Name)
   374  		} else {
   375  			// If the object type does not exactly match
   376  			// any of the target types, greedily find the first
   377  			// target type that the object type can satisfy.
   378  			for typ := range matches {
   379  				if equivalentTypes(obj.Type(), typ) {
   380  					matches[typ] = append(matches[typ], ident.Name)
   381  				}
   382  			}
   383  		}
   384  		return true
   385  	})
   386  	return matches
   387  }
   388  
   389  func equivalentTypes(want, got types.Type) bool {
   390  	if types.Identical(want, got) {
   391  		return true
   392  	}
   393  	// Code segment to help check for untyped equality from (golang/go#32146).
   394  	if rhs, ok := want.(*types.Basic); ok && rhs.Info()&types.IsUntyped > 0 {
   395  		if lhs, ok := got.Underlying().(*types.Basic); ok {
   396  			return rhs.Info()&types.IsConstType == lhs.Info()&types.IsConstType
   397  		}
   398  	}
   399  	return types.AssignableTo(want, got)
   400  }
   401  
   402  // MakeReadFile returns a simple implementation of the Pass.ReadFile function.
   403  func MakeReadFile(pass *analysis.Pass) func(filename string) ([]byte, error) {
   404  	return func(filename string) ([]byte, error) {
   405  		if err := CheckReadable(pass, filename); err != nil {
   406  			return nil, err
   407  		}
   408  		return os.ReadFile(filename)
   409  	}
   410  }
   411  
   412  // CheckReadable enforces the access policy defined by the ReadFile field of [analysis.Pass].
   413  func CheckReadable(pass *analysis.Pass, filename string) error {
   414  	if slicesContains(pass.OtherFiles, filename) ||
   415  		slicesContains(pass.IgnoredFiles, filename) {
   416  		return nil
   417  	}
   418  	for _, f := range pass.Files {
   419  		// TODO(adonovan): use go1.20 f.FileStart
   420  		if pass.Fset.File(f.Pos()).Name() == filename {
   421  			return nil
   422  		}
   423  	}
   424  	return fmt.Errorf("Pass.ReadFile: %s is not among OtherFiles, IgnoredFiles, or names of Files", filename)
   425  }
   426  
   427  // TODO(adonovan): use go1.21 slices.Contains.
   428  func slicesContains[S ~[]E, E comparable](slice S, x E) bool {
   429  	for _, elem := range slice {
   430  		if elem == x {
   431  			return true
   432  		}
   433  	}
   434  	return false
   435  }
   436  
   437  // AddImport checks whether this file already imports pkgpath and
   438  // that import is in scope at pos. If so, it returns the name under
   439  // which it was imported and a zero edit. Otherwise, it adds a new
   440  // import of pkgpath, using a name derived from the preferred name,
   441  // and returns the chosen name along with the edit for the new import.
   442  //
   443  // It does not mutate its arguments.
   444  func AddImport(info *types.Info, file *ast.File, pos token.Pos, pkgpath, preferredName string) (name string, newImport analysis.TextEdit) {
   445  	// Find innermost enclosing lexical block.
   446  	scope := info.Scopes[file].Innermost(pos)
   447  	if scope == nil {
   448  		panic("no enclosing lexical block")
   449  	}
   450  
   451  	// Is there an existing import of this package?
   452  	// If so, are we in its scope? (not shadowed)
   453  	for _, spec := range file.Imports {
   454  		pkgname, ok := importedPkgName(info, spec)
   455  		if ok && pkgname.Imported().Path() == pkgpath {
   456  			if _, obj := scope.LookupParent(pkgname.Name(), pos); obj == pkgname {
   457  				return pkgname.Name(), analysis.TextEdit{}
   458  			}
   459  		}
   460  	}
   461  
   462  	// We must add a new import.
   463  	// Ensure we have a fresh name.
   464  	newName := preferredName
   465  	for i := 0; ; i++ {
   466  		if _, obj := scope.LookupParent(newName, pos); obj == nil {
   467  			break // fresh
   468  		}
   469  		newName = fmt.Sprintf("%s%d", preferredName, i)
   470  	}
   471  
   472  	// For now, keep it real simple: create a new import
   473  	// declaration before the first existing declaration (which
   474  	// must exist), including its comments, and let goimports tidy it up.
   475  	//
   476  	// Use a renaming import whenever the preferred name is not
   477  	// available, or the chosen name does not match the last
   478  	// segment of its path.
   479  	newText := fmt.Sprintf("import %q\n\n", pkgpath)
   480  	if newName != preferredName || newName != pathpkg.Base(pkgpath) {
   481  		newText = fmt.Sprintf("import %s %q\n\n", newName, pkgpath)
   482  	}
   483  	decl0 := file.Decls[0]
   484  	var before ast.Node = decl0
   485  	switch decl0 := decl0.(type) {
   486  	case *ast.GenDecl:
   487  		if decl0.Doc != nil {
   488  			before = decl0.Doc
   489  		}
   490  	case *ast.FuncDecl:
   491  		if decl0.Doc != nil {
   492  			before = decl0.Doc
   493  		}
   494  	}
   495  	return newName, analysis.TextEdit{
   496  		Pos:     before.Pos(),
   497  		End:     before.Pos(),
   498  		NewText: []byte(newText),
   499  	}
   500  }
   501  
   502  // importedPkgName returns the PkgName object declared by an ImportSpec.
   503  // TODO(adonovan): use go1.22's Info.PkgNameOf.
   504  func importedPkgName(info *types.Info, imp *ast.ImportSpec) (*types.PkgName, bool) {
   505  	var obj types.Object
   506  	if imp.Name != nil {
   507  		obj = info.Defs[imp.Name]
   508  	} else {
   509  		obj = info.Implicits[imp]
   510  	}
   511  	pkgname, ok := obj.(*types.PkgName)
   512  	return pkgname, ok
   513  }
   514
View as plain text