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 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 210type TypeErrorPass string 211 212const ( 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. 233func 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. 280func 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). 294func 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. 315func 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 387func 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. 402func 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