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