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. 6package analysisinternal 7 8import ( 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 20var ( 21 GetTypeErrors func(p interface{}) []types.Error 22 SetTypeErrors func(p interface{}, errors []types.Error) 23) 24 25func 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 37func 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) 70func 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 81func 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 default: 202 return nil // TODO: anonymous structs, but who does that 203 } 204} 205 206type TypeErrorPass string 207 208const ( 209 NoNewVars TypeErrorPass = "nonewvars" 210 NoResultValues TypeErrorPass = "noresultvalues" 211 UndeclaredName TypeErrorPass = "undeclaredname" 212) 213 214// StmtToInsertVarBefore returns the ast.Stmt before which we can safely insert a new variable. 215// Some examples: 216// 217// Basic Example: 218// z := 1 219// y := z + x 220// If x is undeclared, then this function would return `y := z + x`, so that we 221// can insert `x := ` on the line before `y := z + x`. 222// 223// If stmt example: 224// if z == 1 { 225// } else if z == y {} 226// If y is undeclared, then this function would return `if z == 1 {`, because we cannot 227// insert a statement between an if and an else if statement. As a result, we need to find 228// the top of the if chain to insert `y := ` before. 229func StmtToInsertVarBefore(path []ast.Node) ast.Stmt { 230 enclosingIndex := -1 231 for i, p := range path { 232 if _, ok := p.(ast.Stmt); ok { 233 enclosingIndex = i 234 break 235 } 236 } 237 if enclosingIndex == -1 { 238 return nil 239 } 240 enclosingStmt := path[enclosingIndex] 241 switch enclosingStmt.(type) { 242 case *ast.IfStmt: 243 // The enclosingStmt is inside of the if declaration, 244 // We need to check if we are in an else-if stmt and 245 // get the base if statement. 246 return baseIfStmt(path, enclosingIndex) 247 case *ast.CaseClause: 248 // Get the enclosing switch stmt if the enclosingStmt is 249 // inside of the case statement. 250 for i := enclosingIndex + 1; i < len(path); i++ { 251 if node, ok := path[i].(*ast.SwitchStmt); ok { 252 return node 253 } else if node, ok := path[i].(*ast.TypeSwitchStmt); ok { 254 return node 255 } 256 } 257 } 258 if len(path) <= enclosingIndex+1 { 259 return enclosingStmt.(ast.Stmt) 260 } 261 // Check if the enclosing statement is inside another node. 262 switch expr := path[enclosingIndex+1].(type) { 263 case *ast.IfStmt: 264 // Get the base if statement. 265 return baseIfStmt(path, enclosingIndex+1) 266 case *ast.ForStmt: 267 if expr.Init == enclosingStmt || expr.Post == enclosingStmt { 268 return expr 269 } 270 } 271 return enclosingStmt.(ast.Stmt) 272} 273 274// baseIfStmt walks up the if/else-if chain until we get to 275// the top of the current if chain. 276func baseIfStmt(path []ast.Node, index int) ast.Stmt { 277 stmt := path[index] 278 for i := index + 1; i < len(path); i++ { 279 if node, ok := path[i].(*ast.IfStmt); ok && node.Else == stmt { 280 stmt = node 281 continue 282 } 283 break 284 } 285 return stmt.(ast.Stmt) 286} 287 288// WalkASTWithParent walks the AST rooted at n. The semantics are 289// similar to ast.Inspect except it does not call f(nil). 290func WalkASTWithParent(n ast.Node, f func(n ast.Node, parent ast.Node) bool) { 291 var ancestors []ast.Node 292 ast.Inspect(n, func(n ast.Node) (recurse bool) { 293 if n == nil { 294 ancestors = ancestors[:len(ancestors)-1] 295 return false 296 } 297 298 var parent ast.Node 299 if len(ancestors) > 0 { 300 parent = ancestors[len(ancestors)-1] 301 } 302 ancestors = append(ancestors, n) 303 return f(n, parent) 304 }) 305} 306 307// FindMatchingIdents finds all identifiers in 'node' that match any of the given types. 308// 'pos' represents the position at which the identifiers may be inserted. 'pos' must be within 309// the scope of each of identifier we select. Otherwise, we will insert a variable at 'pos' that 310// is unrecognized. 311func FindMatchingIdents(typs []types.Type, node ast.Node, pos token.Pos, info *types.Info, pkg *types.Package) map[types.Type][]*ast.Ident { 312 matches := map[types.Type][]*ast.Ident{} 313 // Initialize matches to contain the variable types we are searching for. 314 for _, typ := range typs { 315 if typ == nil { 316 continue 317 } 318 matches[typ] = []*ast.Ident{} 319 } 320 seen := map[types.Object]struct{}{} 321 ast.Inspect(node, func(n ast.Node) bool { 322 if n == nil { 323 return false 324 } 325 // Prevent circular definitions. If 'pos' is within an assignment statement, do not 326 // allow any identifiers in that assignment statement to be selected. Otherwise, 327 // we could do the following, where 'x' satisfies the type of 'f0': 328 // 329 // x := fakeStruct{f0: x} 330 // 331 assignment, ok := n.(*ast.AssignStmt) 332 if ok && pos > assignment.Pos() && pos <= assignment.End() { 333 return false 334 } 335 if n.End() > pos { 336 return n.Pos() <= pos 337 } 338 ident, ok := n.(*ast.Ident) 339 if !ok || ident.Name == "_" { 340 return true 341 } 342 obj := info.Defs[ident] 343 if obj == nil || obj.Type() == nil { 344 return true 345 } 346 if _, ok := obj.(*types.TypeName); ok { 347 return true 348 } 349 // Prevent duplicates in matches' values. 350 if _, ok = seen[obj]; ok { 351 return true 352 } 353 seen[obj] = struct{}{} 354 // Find the scope for the given position. Then, check whether the object 355 // exists within the scope. 356 innerScope := pkg.Scope().Innermost(pos) 357 if innerScope == nil { 358 return true 359 } 360 _, foundObj := innerScope.LookupParent(ident.Name, pos) 361 if foundObj != obj { 362 return true 363 } 364 // The object must match one of the types that we are searching for. 365 if idents, ok := matches[obj.Type()]; ok { 366 matches[obj.Type()] = append(idents, ast.NewIdent(ident.Name)) 367 } 368 // If the object type does not exactly match any of the target types, greedily 369 // find the first target type that the object type can satisfy. 370 for typ := range matches { 371 if obj.Type() == typ { 372 continue 373 } 374 if equivalentTypes(obj.Type(), typ) { 375 matches[typ] = append(matches[typ], ast.NewIdent(ident.Name)) 376 } 377 } 378 return true 379 }) 380 return matches 381} 382 383func equivalentTypes(want, got types.Type) bool { 384 if want == got || types.Identical(want, got) { 385 return true 386 } 387 // Code segment to help check for untyped equality from (golang/go#32146). 388 if rhs, ok := want.(*types.Basic); ok && rhs.Info()&types.IsUntyped > 0 { 389 if lhs, ok := got.Underlying().(*types.Basic); ok { 390 return rhs.Info()&types.IsConstType == lhs.Info()&types.IsConstType 391 } 392 } 393 return types.AssignableTo(want, got) 394} 395 396// FindBestMatch employs fuzzy matching to evaluate the similarity of each given identifier to the 397// given pattern. We return the identifier whose name is most similar to the pattern. 398func FindBestMatch(pattern string, idents []*ast.Ident) ast.Expr { 399 fuzz := fuzzy.NewMatcher(pattern) 400 var bestFuzz ast.Expr 401 highScore := float32(-1) // minimum score is -1 (no match) 402 for _, ident := range idents { 403 // TODO: Improve scoring algorithm. 404 score := fuzz.Score(ident.Name) 405 if score > highScore { 406 highScore = score 407 bestFuzz = ident 408 } else if score == -1 { 409 // Order matters in the fuzzy matching algorithm. If we find no match 410 // when matching the target to the identifier, try matching the identifier 411 // to the target. 412 revFuzz := fuzzy.NewMatcher(ident.Name) 413 revScore := revFuzz.Score(pattern) 414 if revScore > highScore { 415 highScore = revScore 416 bestFuzz = ident 417 } 418 } 419 } 420 return bestFuzz 421} 422