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 exposes internal-only fields from go/analysis.
     6  package analysisinternal
     7  
     8  import (
     9  	"bytes"
    10  	"fmt"
    11  	"go/ast"
    12  	"go/token"
    13  	"go/types"
    14  	"strings"
    15  
    16  	"golang.org/x/tools/go/ast/astutil"
    17  	"golang.org/x/tools/internal/lsp/fuzzy"
    18  )
    19  
    20  var (
    21  	GetTypeErrors func(p interface{}) []types.Error
    22  	SetTypeErrors func(p interface{}, errors []types.Error)
    23  )
    24  
    25  func TypeErrorEndPos(fset *token.FileSet, src []byte, start token.Pos) token.Pos {
    26  	// Get the end position for the type error.
    27  	offset, end := fset.PositionFor(start, false).Offset, start
    28  	if offset >= len(src) {
    29  		return end
    30  	}
    31  	if width := bytes.IndexAny(src[offset:], " \n,():;[]+-*"); width > 0 {
    32  		end = start + token.Pos(width)
    33  	}
    34  	return end
    35  }
    36  
    37  func ZeroValue(fset *token.FileSet, f *ast.File, pkg *types.Package, typ types.Type) ast.Expr {
    38  	under := typ
    39  	if n, ok := typ.(*types.Named); ok {
    40  		under = n.Underlying()
    41  	}
    42  	switch u := under.(type) {
    43  	case *types.Basic:
    44  		switch {
    45  		case u.Info()&types.IsNumeric != 0:
    46  			return &ast.BasicLit{Kind: token.INT, Value: "0"}
    47  		case u.Info()&types.IsBoolean != 0:
    48  			return &ast.Ident{Name: "false"}
    49  		case u.Info()&types.IsString != 0:
    50  			return &ast.BasicLit{Kind: token.STRING, Value: `""`}
    51  		default:
    52  			panic("unknown basic type")
    53  		}
    54  	case *types.Chan, *types.Interface, *types.Map, *types.Pointer, *types.Signature, *types.Slice, *types.Array:
    55  		return ast.NewIdent("nil")
    56  	case *types.Struct:
    57  		texpr := TypeExpr(fset, f, pkg, typ) // typ because we want the name here.
    58  		if texpr == nil {
    59  			return nil
    60  		}
    61  		return &ast.CompositeLit{
    62  			Type: texpr,
    63  		}
    64  	}
    65  	return nil
    66  }
    67  
    68  // IsZeroValue checks whether the given expression is a 'zero value' (as determined by output of
    69  // analysisinternal.ZeroValue)
    70  func IsZeroValue(expr ast.Expr) bool {
    71  	switch e := expr.(type) {
    72  	case *ast.BasicLit:
    73  		return e.Value == "0" || e.Value == `""`
    74  	case *ast.Ident:
    75  		return e.Name == "nil" || e.Name == "false"
    76  	default:
    77  		return false
    78  	}
    79  }
    80  
    81  func TypeExpr(fset *token.FileSet, f *ast.File, pkg *types.Package, typ types.Type) ast.Expr {
    82  	switch t := typ.(type) {
    83  	case *types.Basic:
    84  		switch t.Kind() {
    85  		case types.UnsafePointer:
    86  			return &ast.SelectorExpr{X: ast.NewIdent("unsafe"), Sel: ast.NewIdent("Pointer")}
    87  		default:
    88  			return ast.NewIdent(t.Name())
    89  		}
    90  	case *types.Pointer:
    91  		x := TypeExpr(fset, f, pkg, t.Elem())
    92  		if x == nil {
    93  			return nil
    94  		}
    95  		return &ast.UnaryExpr{
    96  			Op: token.MUL,
    97  			X:  x,
    98  		}
    99  	case *types.Array:
   100  		elt := TypeExpr(fset, f, pkg, t.Elem())
   101  		if elt == nil {
   102  			return nil
   103  		}
   104  		return &ast.ArrayType{
   105  			Len: &ast.BasicLit{
   106  				Kind:  token.INT,
   107  				Value: fmt.Sprintf("%d", t.Len()),
   108  			},
   109  			Elt: elt,
   110  		}
   111  	case *types.Slice:
   112  		elt := TypeExpr(fset, f, pkg, t.Elem())
   113  		if elt == nil {
   114  			return nil
   115  		}
   116  		return &ast.ArrayType{
   117  			Elt: elt,
   118  		}
   119  	case *types.Map:
   120  		key := TypeExpr(fset, f, pkg, t.Key())
   121  		value := TypeExpr(fset, f, pkg, t.Elem())
   122  		if key == nil || value == nil {
   123  			return nil
   124  		}
   125  		return &ast.MapType{
   126  			Key:   key,
   127  			Value: value,
   128  		}
   129  	case *types.Chan:
   130  		dir := ast.ChanDir(t.Dir())
   131  		if t.Dir() == types.SendRecv {
   132  			dir = ast.SEND | ast.RECV
   133  		}
   134  		value := TypeExpr(fset, f, pkg, t.Elem())
   135  		if value == nil {
   136  			return nil
   137  		}
   138  		return &ast.ChanType{
   139  			Dir:   dir,
   140  			Value: value,
   141  		}
   142  	case *types.Signature:
   143  		var params []*ast.Field
   144  		for i := 0; i < t.Params().Len(); i++ {
   145  			p := TypeExpr(fset, f, pkg, t.Params().At(i).Type())
   146  			if p == nil {
   147  				return nil
   148  			}
   149  			params = append(params, &ast.Field{
   150  				Type: p,
   151  				Names: []*ast.Ident{
   152  					{
   153  						Name: t.Params().At(i).Name(),
   154  					},
   155  				},
   156  			})
   157  		}
   158  		var returns []*ast.Field
   159  		for i := 0; i < t.Results().Len(); i++ {
   160  			r := TypeExpr(fset, f, pkg, t.Results().At(i).Type())
   161  			if r == nil {
   162  				return nil
   163  			}
   164  			returns = append(returns, &ast.Field{
   165  				Type: r,
   166  			})
   167  		}
   168  		return &ast.FuncType{
   169  			Params: &ast.FieldList{
   170  				List: params,
   171  			},
   172  			Results: &ast.FieldList{
   173  				List: returns,
   174  			},
   175  		}
   176  	case *types.Named:
   177  		if t.Obj().Pkg() == nil {
   178  			return ast.NewIdent(t.Obj().Name())
   179  		}
   180  		if t.Obj().Pkg() == pkg {
   181  			return ast.NewIdent(t.Obj().Name())
   182  		}
   183  		pkgName := t.Obj().Pkg().Name()
   184  		// If the file already imports the package under another name, use that.
   185  		for _, group := range astutil.Imports(fset, f) {
   186  			for _, cand := range group {
   187  				if strings.Trim(cand.Path.Value, `"`) == t.Obj().Pkg().Path() {
   188  					if cand.Name != nil && cand.Name.Name != "" {
   189  						pkgName = cand.Name.Name
   190  					}
   191  				}
   192  			}
   193  		}
   194  		if pkgName == "." {
   195  			return ast.NewIdent(t.Obj().Name())
   196  		}
   197  		return &ast.SelectorExpr{
   198  			X:   ast.NewIdent(pkgName),
   199  			Sel: ast.NewIdent(t.Obj().Name()),
   200  		}
   201  	case *types.Struct:
   202  		return ast.NewIdent(t.String())
   203  	case *types.Interface:
   204  		return ast.NewIdent(t.String())
   205  	default:
   206  		return nil
   207  	}
   208  }
   209  
   210  type TypeErrorPass string
   211  
   212  const (
   213  	NoNewVars      TypeErrorPass = "nonewvars"
   214  	NoResultValues TypeErrorPass = "noresultvalues"
   215  	UndeclaredName TypeErrorPass = "undeclaredname"
   216  )
   217  
   218  // StmtToInsertVarBefore returns the ast.Stmt before which we can safely insert a new variable.
   219  // Some examples:
   220  //
   221  // Basic Example:
   222  // z := 1
   223  // y := z + x
   224  // If x is undeclared, then this function would return `y := z + x`, so that we
   225  // can insert `x := ` on the line before `y := z + x`.
   226  //
   227  // If stmt example:
   228  // if z == 1 {
   229  // } else if z == y {}
   230  // If y is undeclared, then this function would return `if z == 1 {`, because we cannot
   231  // insert a statement between an if and an else if statement. As a result, we need to find
   232  // the top of the if chain to insert `y := ` before.
   233  func StmtToInsertVarBefore(path []ast.Node) ast.Stmt {
   234  	enclosingIndex := -1
   235  	for i, p := range path {
   236  		if _, ok := p.(ast.Stmt); ok {
   237  			enclosingIndex = i
   238  			break
   239  		}
   240  	}
   241  	if enclosingIndex == -1 {
   242  		return nil
   243  	}
   244  	enclosingStmt := path[enclosingIndex]
   245  	switch enclosingStmt.(type) {
   246  	case *ast.IfStmt:
   247  		// The enclosingStmt is inside of the if declaration,
   248  		// We need to check if we are in an else-if stmt and
   249  		// get the base if statement.
   250  		return baseIfStmt(path, enclosingIndex)
   251  	case *ast.CaseClause:
   252  		// Get the enclosing switch stmt if the enclosingStmt is
   253  		// inside of the case statement.
   254  		for i := enclosingIndex + 1; i < len(path); i++ {
   255  			if node, ok := path[i].(*ast.SwitchStmt); ok {
   256  				return node
   257  			} else if node, ok := path[i].(*ast.TypeSwitchStmt); ok {
   258  				return node
   259  			}
   260  		}
   261  	}
   262  	if len(path) <= enclosingIndex+1 {
   263  		return enclosingStmt.(ast.Stmt)
   264  	}
   265  	// Check if the enclosing statement is inside another node.
   266  	switch expr := path[enclosingIndex+1].(type) {
   267  	case *ast.IfStmt:
   268  		// Get the base if statement.
   269  		return baseIfStmt(path, enclosingIndex+1)
   270  	case *ast.ForStmt:
   271  		if expr.Init == enclosingStmt || expr.Post == enclosingStmt {
   272  			return expr
   273  		}
   274  	}
   275  	return enclosingStmt.(ast.Stmt)
   276  }
   277  
   278  // baseIfStmt walks up the if/else-if chain until we get to
   279  // the top of the current if chain.
   280  func baseIfStmt(path []ast.Node, index int) ast.Stmt {
   281  	stmt := path[index]
   282  	for i := index + 1; i < len(path); i++ {
   283  		if node, ok := path[i].(*ast.IfStmt); ok && node.Else == stmt {
   284  			stmt = node
   285  			continue
   286  		}
   287  		break
   288  	}
   289  	return stmt.(ast.Stmt)
   290  }
   291  
   292  // WalkASTWithParent walks the AST rooted at n. The semantics are
   293  // similar to ast.Inspect except it does not call f(nil).
   294  func WalkASTWithParent(n ast.Node, f func(n ast.Node, parent ast.Node) bool) {
   295  	var ancestors []ast.Node
   296  	ast.Inspect(n, func(n ast.Node) (recurse bool) {
   297  		if n == nil {
   298  			ancestors = ancestors[:len(ancestors)-1]
   299  			return false
   300  		}
   301  
   302  		var parent ast.Node
   303  		if len(ancestors) > 0 {
   304  			parent = ancestors[len(ancestors)-1]
   305  		}
   306  		ancestors = append(ancestors, n)
   307  		return f(n, parent)
   308  	})
   309  }
   310  
   311  // FindMatchingIdents finds all identifiers in 'node' that match any of the given types.
   312  // 'pos' represents the position at which the identifiers may be inserted. 'pos' must be within
   313  // the scope of each of identifier we select. Otherwise, we will insert a variable at 'pos' that
   314  // is unrecognized.
   315  func FindMatchingIdents(typs []types.Type, node ast.Node, pos token.Pos, info *types.Info, pkg *types.Package) map[types.Type][]*ast.Ident {
   316  	matches := map[types.Type][]*ast.Ident{}
   317  	// Initialize matches to contain the variable types we are searching for.
   318  	for _, typ := range typs {
   319  		if typ == nil {
   320  			continue
   321  		}
   322  		matches[typ] = []*ast.Ident{}
   323  	}
   324  	seen := map[types.Object]struct{}{}
   325  	ast.Inspect(node, func(n ast.Node) bool {
   326  		if n == nil {
   327  			return false
   328  		}
   329  		// Prevent circular definitions. If 'pos' is within an assignment statement, do not
   330  		// allow any identifiers in that assignment statement to be selected. Otherwise,
   331  		// we could do the following, where 'x' satisfies the type of 'f0':
   332  		//
   333  		// x := fakeStruct{f0: x}
   334  		//
   335  		assignment, ok := n.(*ast.AssignStmt)
   336  		if ok && pos > assignment.Pos() && pos <= assignment.End() {
   337  			return false
   338  		}
   339  		if n.End() > pos {
   340  			return n.Pos() <= pos
   341  		}
   342  		ident, ok := n.(*ast.Ident)
   343  		if !ok || ident.Name == "_" {
   344  			return true
   345  		}
   346  		obj := info.Defs[ident]
   347  		if obj == nil || obj.Type() == nil {
   348  			return true
   349  		}
   350  		if _, ok := obj.(*types.TypeName); ok {
   351  			return true
   352  		}
   353  		// Prevent duplicates in matches' values.
   354  		if _, ok = seen[obj]; ok {
   355  			return true
   356  		}
   357  		seen[obj] = struct{}{}
   358  		// Find the scope for the given position. Then, check whether the object
   359  		// exists within the scope.
   360  		innerScope := pkg.Scope().Innermost(pos)
   361  		if innerScope == nil {
   362  			return true
   363  		}
   364  		_, foundObj := innerScope.LookupParent(ident.Name, pos)
   365  		if foundObj != obj {
   366  			return true
   367  		}
   368  		// The object must match one of the types that we are searching for.
   369  		if idents, ok := matches[obj.Type()]; ok {
   370  			matches[obj.Type()] = append(idents, ast.NewIdent(ident.Name))
   371  		}
   372  		// If the object type does not exactly match any of the target types, greedily
   373  		// find the first target type that the object type can satisfy.
   374  		for typ := range matches {
   375  			if obj.Type() == typ {
   376  				continue
   377  			}
   378  			if equivalentTypes(obj.Type(), typ) {
   379  				matches[typ] = append(matches[typ], ast.NewIdent(ident.Name))
   380  			}
   381  		}
   382  		return true
   383  	})
   384  	return matches
   385  }
   386  
   387  func equivalentTypes(want, got types.Type) bool {
   388  	if want == got || types.Identical(want, got) {
   389  		return true
   390  	}
   391  	// Code segment to help check for untyped equality from (golang/go#32146).
   392  	if rhs, ok := want.(*types.Basic); ok && rhs.Info()&types.IsUntyped > 0 {
   393  		if lhs, ok := got.Underlying().(*types.Basic); ok {
   394  			return rhs.Info()&types.IsConstType == lhs.Info()&types.IsConstType
   395  		}
   396  	}
   397  	return types.AssignableTo(want, got)
   398  }
   399  
   400  // FindBestMatch employs fuzzy matching to evaluate the similarity of each given identifier to the
   401  // given pattern. We return the identifier whose name is most similar to the pattern.
   402  func FindBestMatch(pattern string, idents []*ast.Ident) ast.Expr {
   403  	fuzz := fuzzy.NewMatcher(pattern)
   404  	var bestFuzz ast.Expr
   405  	highScore := float32(0) // minimum score is 0 (no match)
   406  	for _, ident := range idents {
   407  		// TODO: Improve scoring algorithm.
   408  		score := fuzz.Score(ident.Name)
   409  		if score > highScore {
   410  			highScore = score
   411  			bestFuzz = ident
   412  		} else if score == 0 {
   413  			// Order matters in the fuzzy matching algorithm. If we find no match
   414  			// when matching the target to the identifier, try matching the identifier
   415  			// to the target.
   416  			revFuzz := fuzzy.NewMatcher(ident.Name)
   417  			revScore := revFuzz.Score(pattern)
   418  			if revScore > highScore {
   419  				highScore = revScore
   420  				bestFuzz = ident
   421  			}
   422  		}
   423  	}
   424  	return bestFuzz
   425  }
   426
View as plain text