typeof.go

Documentation: golang.org/x/tools/go/ast/inspector

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