gopls/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 (
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

MembersX

maskOf.nodes

maskOf.mask

maskOf.RangeStmt_4917.n

math

nArrayType

maskOf

Members

GoPLS Viewer