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/scanner"
    14  	"go/token"
    15  	"go/types"
    16  	"os"
    17  	pathpkg "path"
    18  
    19  	"golang.org/x/tools/go/analysis"
    20  )
    21  
    22  func TypeErrorEndPos(fset *token.FileSet, src []byte, start token.Pos) token.Pos {
    23  	// Get the end position for the type error.
    24  	file := fset.File(start)
    25  	if file == nil {
    26  		return start
    27  	}
    28  	if offset := file.PositionFor(start, false).Offset; offset > len(src) {
    29  		return start
    30  	} else {
    31  		src = src[offset:]
    32  	}
    33  
    34  	// Attempt to find a reasonable end position for the type error.
    35  	//
    36  	// TODO(rfindley): the heuristic implemented here is unclear. It looks like
    37  	// it seeks the end of the primary operand starting at start, but that is not
    38  	// quite implemented (for example, given a func literal this heuristic will
    39  	// return the range of the func keyword).
    40  	//
    41  	// We should formalize this heuristic, or deprecate it by finally proposing
    42  	// to add end position to all type checker errors.
    43  	//
    44  	// Nevertheless, ensure that the end position at least spans the current
    45  	// token at the cursor (this was golang/go#69505).
    46  	end := start
    47  	{
    48  		var s scanner.Scanner
    49  		fset := token.NewFileSet()
    50  		f := fset.AddFile("", fset.Base(), len(src))
    51  		s.Init(f, src, nil /* no error handler */, scanner.ScanComments)
    52  		pos, tok, lit := s.Scan()
    53  		if tok != token.SEMICOLON && token.Pos(f.Base()) <= pos && pos <= token.Pos(f.Base()+f.Size()) {
    54  			off := file.Offset(pos) + len(lit)
    55  			src = src[off:]
    56  			end += token.Pos(off)
    57  		}
    58  	}
    59  
    60  	// Look for bytes that might terminate the current operand. See note above:
    61  	// this is imprecise.
    62  	if width := bytes.IndexAny(src, " \n,():;[]+-*/"); width > 0 {
    63  		end += token.Pos(width)
    64  	}
    65  	return end
    66  }
    67  
    68  // StmtToInsertVarBefore returns the ast.Stmt before which we can
    69  // safely insert a new var declaration, or nil if the path denotes a
    70  // node outside any statement.
    71  //
    72  // Basic Example:
    73  //
    74  //	z := 1
    75  //	y := z + x
    76  //
    77  // If x is undeclared, then this function would return `y := z + x`, so that we
    78  // can insert `x := ` on the line before `y := z + x`.
    79  //
    80  // If stmt example:
    81  //
    82  //	if z == 1 {
    83  //	} else if z == y {}
    84  //
    85  // If y is undeclared, then this function would return `if z == 1 {`, because we cannot
    86  // insert a statement between an if and an else if statement. As a result, we need to find
    87  // the top of the if chain to insert `y := ` before.
    88  func StmtToInsertVarBefore(path []ast.Node) ast.Stmt {
    89  	enclosingIndex := -1
    90  	for i, p := range path {
    91  		if _, ok := p.(ast.Stmt); ok {
    92  			enclosingIndex = i
    93  			break
    94  		}
    95  	}
    96  	if enclosingIndex == -1 {
    97  		return nil // no enclosing statement: outside function
    98  	}
    99  	enclosingStmt := path[enclosingIndex]
   100  	switch enclosingStmt.(type) {
   101  	case *ast.IfStmt:
   102  		// The enclosingStmt is inside of the if declaration,
   103  		// We need to check if we are in an else-if stmt and
   104  		// get the base if statement.
   105  		// TODO(adonovan): for non-constants, it may be preferable
   106  		// to add the decl as the Init field of the innermost
   107  		// enclosing ast.IfStmt.
   108  		return baseIfStmt(path, enclosingIndex)
   109  	case *ast.CaseClause:
   110  		// Get the enclosing switch stmt if the enclosingStmt is
   111  		// inside of the case statement.
   112  		for i := enclosingIndex + 1; i < len(path); i++ {
   113  			if node, ok := path[i].(*ast.SwitchStmt); ok {
   114  				return node
   115  			} else if node, ok := path[i].(*ast.TypeSwitchStmt); ok {
   116  				return node
   117  			}
   118  		}
   119  	}
   120  	if len(path) <= enclosingIndex+1 {
   121  		return enclosingStmt.(ast.Stmt)
   122  	}
   123  	// Check if the enclosing statement is inside another node.
   124  	switch expr := path[enclosingIndex+1].(type) {
   125  	case *ast.IfStmt:
   126  		// Get the base if statement.
   127  		return baseIfStmt(path, enclosingIndex+1)
   128  	case *ast.ForStmt:
   129  		if expr.Init == enclosingStmt || expr.Post == enclosingStmt {
   130  			return expr
   131  		}
   132  	case *ast.SwitchStmt, *ast.TypeSwitchStmt:
   133  		return expr.(ast.Stmt)
   134  	}
   135  	return enclosingStmt.(ast.Stmt)
   136  }
   137  
   138  // baseIfStmt walks up the if/else-if chain until we get to
   139  // the top of the current if chain.
   140  func baseIfStmt(path []ast.Node, index int) ast.Stmt {
   141  	stmt := path[index]
   142  	for i := index + 1; i < len(path); i++ {
   143  		if node, ok := path[i].(*ast.IfStmt); ok && node.Else == stmt {
   144  			stmt = node
   145  			continue
   146  		}
   147  		break
   148  	}
   149  	return stmt.(ast.Stmt)
   150  }
   151  
   152  // WalkASTWithParent walks the AST rooted at n. The semantics are
   153  // similar to ast.Inspect except it does not call f(nil).
   154  func WalkASTWithParent(n ast.Node, f func(n ast.Node, parent ast.Node) bool) {
   155  	var ancestors []ast.Node
   156  	ast.Inspect(n, func(n ast.Node) (recurse bool) {
   157  		if n == nil {
   158  			ancestors = ancestors[:len(ancestors)-1]
   159  			return false
   160  		}
   161  
   162  		var parent ast.Node
   163  		if len(ancestors) > 0 {
   164  			parent = ancestors[len(ancestors)-1]
   165  		}
   166  		ancestors = append(ancestors, n)
   167  		return f(n, parent)
   168  	})
   169  }
   170  
   171  // MatchingIdents finds the names of all identifiers in 'node' that match any of the given types.
   172  // 'pos' represents the position at which the identifiers may be inserted. 'pos' must be within
   173  // the scope of each of identifier we select. Otherwise, we will insert a variable at 'pos' that
   174  // is unrecognized.
   175  func MatchingIdents(typs []types.Type, node ast.Node, pos token.Pos, info *types.Info, pkg *types.Package) map[types.Type][]string {
   176  
   177  	// Initialize matches to contain the variable types we are searching for.
   178  	matches := make(map[types.Type][]string)
   179  	for _, typ := range typs {
   180  		if typ == nil {
   181  			continue // TODO(adonovan): is this reachable?
   182  		}
   183  		matches[typ] = nil // create entry
   184  	}
   185  
   186  	seen := map[types.Object]struct{}{}
   187  	ast.Inspect(node, func(n ast.Node) bool {
   188  		if n == nil {
   189  			return false
   190  		}
   191  		// Prevent circular definitions. If 'pos' is within an assignment statement, do not
   192  		// allow any identifiers in that assignment statement to be selected. Otherwise,
   193  		// we could do the following, where 'x' satisfies the type of 'f0':
   194  		//
   195  		// x := fakeStruct{f0: x}
   196  		//
   197  		if assign, ok := n.(*ast.AssignStmt); ok && pos > assign.Pos() && pos <= assign.End() {
   198  			return false
   199  		}
   200  		if n.End() > pos {
   201  			return n.Pos() <= pos
   202  		}
   203  		ident, ok := n.(*ast.Ident)
   204  		if !ok || ident.Name == "_" {
   205  			return true
   206  		}
   207  		obj := info.Defs[ident]
   208  		if obj == nil || obj.Type() == nil {
   209  			return true
   210  		}
   211  		if _, ok := obj.(*types.TypeName); ok {
   212  			return true
   213  		}
   214  		// Prevent duplicates in matches' values.
   215  		if _, ok = seen[obj]; ok {
   216  			return true
   217  		}
   218  		seen[obj] = struct{}{}
   219  		// Find the scope for the given position. Then, check whether the object
   220  		// exists within the scope.
   221  		innerScope := pkg.Scope().Innermost(pos)
   222  		if innerScope == nil {
   223  			return true
   224  		}
   225  		_, foundObj := innerScope.LookupParent(ident.Name, pos)
   226  		if foundObj != obj {
   227  			return true
   228  		}
   229  		// The object must match one of the types that we are searching for.
   230  		// TODO(adonovan): opt: use typeutil.Map?
   231  		if names, ok := matches[obj.Type()]; ok {
   232  			matches[obj.Type()] = append(names, ident.Name)
   233  		} else {
   234  			// If the object type does not exactly match
   235  			// any of the target types, greedily find the first
   236  			// target type that the object type can satisfy.
   237  			for typ := range matches {
   238  				if equivalentTypes(obj.Type(), typ) {
   239  					matches[typ] = append(matches[typ], ident.Name)
   240  				}
   241  			}
   242  		}
   243  		return true
   244  	})
   245  	return matches
   246  }
   247  
   248  func equivalentTypes(want, got types.Type) bool {
   249  	if types.Identical(want, got) {
   250  		return true
   251  	}
   252  	// Code segment to help check for untyped equality from (golang/go#32146).
   253  	if rhs, ok := want.(*types.Basic); ok && rhs.Info()&types.IsUntyped > 0 {
   254  		if lhs, ok := got.Underlying().(*types.Basic); ok {
   255  			return rhs.Info()&types.IsConstType == lhs.Info()&types.IsConstType
   256  		}
   257  	}
   258  	return types.AssignableTo(want, got)
   259  }
   260  
   261  // MakeReadFile returns a simple implementation of the Pass.ReadFile function.
   262  func MakeReadFile(pass *analysis.Pass) func(filename string) ([]byte, error) {
   263  	return func(filename string) ([]byte, error) {
   264  		if err := CheckReadable(pass, filename); err != nil {
   265  			return nil, err
   266  		}
   267  		return os.ReadFile(filename)
   268  	}
   269  }
   270  
   271  // CheckReadable enforces the access policy defined by the ReadFile field of [analysis.Pass].
   272  func CheckReadable(pass *analysis.Pass, filename string) error {
   273  	if slicesContains(pass.OtherFiles, filename) ||
   274  		slicesContains(pass.IgnoredFiles, filename) {
   275  		return nil
   276  	}
   277  	for _, f := range pass.Files {
   278  		if pass.Fset.File(f.FileStart).Name() == filename {
   279  			return nil
   280  		}
   281  	}
   282  	return fmt.Errorf("Pass.ReadFile: %s is not among OtherFiles, IgnoredFiles, or names of Files", filename)
   283  }
   284  
   285  // TODO(adonovan): use go1.21 slices.Contains.
   286  func slicesContains[S ~[]E, E comparable](slice S, x E) bool {
   287  	for _, elem := range slice {
   288  		if elem == x {
   289  			return true
   290  		}
   291  	}
   292  	return false
   293  }
   294  
   295  // AddImport checks whether this file already imports pkgpath and
   296  // that import is in scope at pos. If so, it returns the name under
   297  // which it was imported and a zero edit. Otherwise, it adds a new
   298  // import of pkgpath, using a name derived from the preferred name,
   299  // and returns the chosen name along with the edit for the new import.
   300  //
   301  // It does not mutate its arguments.
   302  func AddImport(info *types.Info, file *ast.File, pos token.Pos, pkgpath, preferredName string) (name string, newImport []analysis.TextEdit) {
   303  	// Find innermost enclosing lexical block.
   304  	scope := info.Scopes[file].Innermost(pos)
   305  	if scope == nil {
   306  		panic("no enclosing lexical block")
   307  	}
   308  
   309  	// Is there an existing import of this package?
   310  	// If so, are we in its scope? (not shadowed)
   311  	for _, spec := range file.Imports {
   312  		pkgname, ok := importedPkgName(info, spec)
   313  		if ok && pkgname.Imported().Path() == pkgpath {
   314  			if _, obj := scope.LookupParent(pkgname.Name(), pos); obj == pkgname {
   315  				return pkgname.Name(), nil
   316  			}
   317  		}
   318  	}
   319  
   320  	// We must add a new import.
   321  	// Ensure we have a fresh name.
   322  	newName := preferredName
   323  	for i := 0; ; i++ {
   324  		if _, obj := scope.LookupParent(newName, pos); obj == nil {
   325  			break // fresh
   326  		}
   327  		newName = fmt.Sprintf("%s%d", preferredName, i)
   328  	}
   329  
   330  	// For now, keep it real simple: create a new import
   331  	// declaration before the first existing declaration (which
   332  	// must exist), including its comments, and let goimports tidy it up.
   333  	//
   334  	// Use a renaming import whenever the preferred name is not
   335  	// available, or the chosen name does not match the last
   336  	// segment of its path.
   337  	newText := fmt.Sprintf("import %q\n\n", pkgpath)
   338  	if newName != preferredName || newName != pathpkg.Base(pkgpath) {
   339  		newText = fmt.Sprintf("import %s %q\n\n", newName, pkgpath)
   340  	}
   341  	decl0 := file.Decls[0]
   342  	var before ast.Node = decl0
   343  	switch decl0 := decl0.(type) {
   344  	case *ast.GenDecl:
   345  		if decl0.Doc != nil {
   346  			before = decl0.Doc
   347  		}
   348  	case *ast.FuncDecl:
   349  		if decl0.Doc != nil {
   350  			before = decl0.Doc
   351  		}
   352  	}
   353  	return newName, []analysis.TextEdit{{
   354  		Pos:     before.Pos(),
   355  		End:     before.Pos(),
   356  		NewText: []byte(newText),
   357  	}}
   358  }
   359  
   360  // importedPkgName returns the PkgName object declared by an ImportSpec.
   361  // TODO(adonovan): use go1.22's Info.PkgNameOf.
   362  func importedPkgName(info *types.Info, imp *ast.ImportSpec) (*types.PkgName, bool) {
   363  	var obj types.Object
   364  	if imp.Name != nil {
   365  		obj = info.Defs[imp.Name]
   366  	} else {
   367  		obj = info.Implicits[imp]
   368  	}
   369  	pkgname, ok := obj.(*types.PkgName)
   370  	return pkgname, ok
   371  }
   372
View as plain text