.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.1.1-0.20210319172145-bda8f5cee399/go/ast/inspector/typeof.go

   1 // Copyright 2018 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 inspector
   6
   7 // This file defines func typeOf(ast.Node) uint64.
   8 //
   9 // The initial map-based implementation was too slow;
  10 // see https://go-review.googlesource.com/c/tools/+/135655/1/go/ast/inspector/inspector.go#196
  11
  12 import "go/ast"
  13
  14 const (
  15         nArrayType = iota
  16         nAssignStmt
  17         nBadDecl
  18         nBadExpr
  19         nBadStmt
  20         nBasicLit
  21         nBinaryExpr
  22         nBlockStmt
  23         nBranchStmt
  24         nCallExpr
  25         nCaseClause
  26         nChanType
  27         nCommClause
  28         nComment
  29         nCommentGroup
  30         nCompositeLit
  31         nDeclStmt
  32         nDeferStmt
  33         nEllipsis
  34         nEmptyStmt
  35         nExprStmt
  36         nField
  37         nFieldList
  38         nFile
  39         nForStmt
  40         nFuncDecl
  41         nFuncLit
  42         nFuncType
  43         nGenDecl
  44         nGoStmt
  45         nIdent
  46         nIfStmt
  47         nImportSpec
  48         nIncDecStmt
  49         nIndexExpr
  50         nInterfaceType
  51         nKeyValueExpr
  52         nLabeledStmt
  53         nMapType
  54         nPackage
  55         nParenExpr
  56         nRangeStmt
  57         nReturnStmt
  58         nSelectStmt
  59         nSelectorExpr
  60         nSendStmt
  61         nSliceExpr
  62         nStarExpr
  63         nStructType
  64         nSwitchStmt
  65         nTypeAssertExpr
  66         nTypeSpec
  67         nTypeSwitchStmt
  68         nUnaryExpr
  69         nValueSpec
  70 )
  71
  72 // typeOf returns a distinct single-bit value that represents the type of n.
  73 //
  74 // Various implementations were benchmarked with BenchmarkNewInspector:
  75 //                                                              GOGC=off
  76 // - type switch                                4.9-5.5ms       2.1ms
  77 // - binary search over a sorted list of types  5.5-5.9ms       2.5ms
  78 // - linear scan, frequency-ordered list        5.9-6.1ms       2.7ms
  79 // - linear scan, unordered list                6.4ms           2.7ms
  80 // - hash table                                 6.5ms           3.1ms
  81 // A perfect hash seemed like overkill.
  82 //
  83 // The compiler's switch statement is the clear winner
  84 // as it produces a binary tree in code,
  85 // with constant conditions and good branch prediction.
  86 // (Sadly it is the most verbose in source code.)
  87 // Binary search suffered from poor branch prediction.
  88 //
  89 func typeOf(n ast.Node) uint64 {
  90         // Fast path: nearly half of all nodes are identifiers.
  91         if _, ok := n.(*ast.Ident); ok {
  92                 return 1 << nIdent
  93         }
  94
  95         // These cases include all nodes encountered by ast.Inspect.
  96         switch n.(type) {
  97         case *ast.ArrayType:
  98                 return 1 << nArrayType
  99         case *ast.AssignStmt:
 100                 return 1 << nAssignStmt
 101         case *ast.BadDecl:
 102                 return 1 << nBadDecl
 103         case *ast.BadExpr:
 104                 return 1 << nBadExpr
 105         case *ast.BadStmt:
 106                 return 1 << nBadStmt
 107         case *ast.BasicLit:
 108                 return 1 << nBasicLit
 109         case *ast.BinaryExpr:
 110                 return 1 << nBinaryExpr
 111         case *ast.BlockStmt:
 112                 return 1 << nBlockStmt
 113         case *ast.BranchStmt:
 114                 return 1 << nBranchStmt
 115         case *ast.CallExpr:
 116                 return 1 << nCallExpr
 117         case *ast.CaseClause:
 118                 return 1 << nCaseClause
 119         case *ast.ChanType:
 120                 return 1 << nChanType
 121         case *ast.CommClause:
 122                 return 1 << nCommClause
 123         case *ast.Comment:
 124                 return 1 << nComment
 125         case *ast.CommentGroup:
 126                 return 1 << nCommentGroup
 127         case *ast.CompositeLit:
 128                 return 1 << nCompositeLit
 129         case *ast.DeclStmt:
 130                 return 1 << nDeclStmt
 131         case *ast.DeferStmt:
 132                 return 1 << nDeferStmt
 133         case *ast.Ellipsis:
 134                 return 1 << nEllipsis
 135         case *ast.EmptyStmt:
 136                 return 1 << nEmptyStmt
 137         case *ast.ExprStmt:
 138                 return 1 << nExprStmt
 139         case *ast.Field:
 140                 return 1 << nField
 141         case *ast.FieldList:
 142                 return 1 << nFieldList
 143         case *ast.File:
 144                 return 1 << nFile
 145         case *ast.ForStmt:
 146                 return 1 << nForStmt
 147         case *ast.FuncDecl:
 148                 return 1 << nFuncDecl
 149         case *ast.FuncLit:
 150                 return 1 << nFuncLit
 151         case *ast.FuncType:
 152                 return 1 << nFuncType
 153         case *ast.GenDecl:
 154                 return 1 << nGenDecl
 155         case *ast.GoStmt:
 156                 return 1 << nGoStmt
 157         case *ast.Ident:
 158                 return 1 << nIdent
 159         case *ast.IfStmt:
 160                 return 1 << nIfStmt
 161         case *ast.ImportSpec:
 162                 return 1 << nImportSpec
 163         case *ast.IncDecStmt:
 164                 return 1 << nIncDecStmt
 165         case *ast.IndexExpr:
 166                 return 1 << nIndexExpr
 167         case *ast.InterfaceType:
 168                 return 1 << nInterfaceType
 169         case *ast.KeyValueExpr:
 170                 return 1 << nKeyValueExpr
 171         case *ast.LabeledStmt:
 172                 return 1 << nLabeledStmt
 173         case *ast.MapType:
 174                 return 1 << nMapType
 175         case *ast.Package:
 176                 return 1 << nPackage
 177         case *ast.ParenExpr:
 178                 return 1 << nParenExpr
 179         case *ast.RangeStmt:
 180                 return 1 << nRangeStmt
 181         case *ast.ReturnStmt:
 182                 return 1 << nReturnStmt
 183         case *ast.SelectStmt:
 184                 return 1 << nSelectStmt
 185         case *ast.SelectorExpr:
 186                 return 1 << nSelectorExpr
 187         case *ast.SendStmt:
 188                 return 1 << nSendStmt
 189         case *ast.SliceExpr:
 190                 return 1 << nSliceExpr
 191         case *ast.StarExpr:
 192                 return 1 << nStarExpr
 193         case *ast.StructType:
 194                 return 1 << nStructType
 195         case *ast.SwitchStmt:
 196                 return 1 << nSwitchStmt
 197         case *ast.TypeAssertExpr:
 198                 return 1 << nTypeAssertExpr
 199         case *ast.TypeSpec:
 200                 return 1 << nTypeSpec
 201         case *ast.TypeSwitchStmt:
 202                 return 1 << nTypeSwitchStmt
 203         case *ast.UnaryExpr:
 204                 return 1 << nUnaryExpr
 205         case *ast.ValueSpec:
 206                 return 1 << nValueSpec
 207         }
 208         return 0
 209 }
 210
 211 func maskOf(nodes []ast.Node) uint64 {
 212         if nodes == nil {
 213                 return 1<<64 - 1 // match all node types
 214         }
 215         var mask uint64
 216         for _, n := range nodes {
 217                 mask |= typeOf(n)
 218         }
 219         return mask
 220 }