internal/symbols/extract.go
355 lines · 10679 bytes
1// Package symbols finds definitions in source files and keeps one index of
2// them per repository, for `repo symbols` and the blob view's links from a
3// name to where it is defined.
4//
5// The indexer is pure Go, with no external tagger. Go is parsed with
6// go/parser; the other languages are matched a line at a time against a
7// small table of anchored patterns, which finds the common definition
8// shapes and misses the unusual ones.
9//
10// Go function, method (named Type.Method), type, const, var
11// Swift function, class, struct, enum, interface (protocol), type (typealias)
12// Rust function, struct, enum, interface (trait), type, module, const, macro
13// Python function, method (an indented def), class
14// JavaScript, TS function, class, interface, type, enum, const
15// C and C++ headers function (prototype), struct, enum, class, type (typedef), macro (#define)
16// Shell function
17// Org, Markdown section (a heading)
18//
19// The index covers the tree of the default branch's head and is keyed by
20// that tree's id, so a push that leaves the tree as it was is not indexed
21// again. Worker builds it in the background after a push to the default
22// branch.
23package symbols
24
25import (
26 "bytes"
27 "go/ast"
28 "go/parser"
29 "go/token"
30 "path"
31 "regexp"
32 "strings"
33)
34
35// Kinds are the symbol kinds the indexer records, in the order they are
36// listed.
37var Kinds = []string{
38 "function", "method", "class", "struct", "enum", "interface",
39 "type", "const", "var", "module", "macro", "section",
40}
41
42// ValidKind reports whether k is one of Kinds.
43func ValidKind(k string) bool {
44 for _, v := range Kinds {
45 if v == k {
46 return true
47 }
48 }
49 return false
50}
51
52// Symbol is one definition in one file. Name is what is listed; Key is the
53// name as it is written where the symbol is used, which differs from Name
54// only for Go methods (Name "Server.Handle", Key "Handle").
55type Symbol struct {
56 Name string
57 Key string
58 Kind string
59 Line int
60}
61
62// MaxFileBytes is the largest file the indexer reads.
63const MaxFileBytes = 1 << 20
64
65// Skip reports whether a file is left out of the index before it is read:
66// too large, vendored, generated by its name, or in a language the indexer
67// does not know.
68func Skip(p string, size int64) bool {
69 if size > MaxFileBytes || Language(p) == "" {
70 return true
71 }
72 for _, seg := range strings.Split(path.Dir(p), "/") {
73 if seg == "vendor" || seg == "node_modules" {
74 return true
75 }
76 }
77 base := path.Base(p)
78 return strings.HasSuffix(base, "_gen.go") || strings.HasSuffix(base, ".pb.go") ||
79 strings.HasSuffix(base, ".min.js")
80}
81
82var languages = map[string]string{
83 ".go": "go",
84 ".swift": "swift",
85 ".rs": "rust",
86 ".py": "python",
87 ".js": "js",
88 ".mjs": "js",
89 ".cjs": "js",
90 ".jsx": "js",
91 ".ts": "js",
92 ".tsx": "js",
93 ".mts": "js",
94 ".h": "c",
95 ".hh": "c",
96 ".hpp": "c",
97 ".hxx": "c",
98 ".sh": "shell",
99 ".bash": "shell",
100 ".zsh": "shell",
101 ".org": "org",
102 ".md": "markdown",
103 ".markdown": "markdown",
104}
105
106// Language names the indexer's language for a path, or "" when it has
107// none.
108func Language(p string) string {
109 return languages[strings.ToLower(path.Ext(p))]
110}
111
112// generatedGo is the marker `go generate` tools write, per the Go
113// convention for generated files.
114var generatedGo = regexp.MustCompile(`(?m)^// Code generated .* DO NOT EDIT\.$`)
115
116// MaxNameBytes is the longest name the index keeps. A longer one is
117// dropped: no real definition is named that way, and a file of them is a
118// way to fill the index.
119const MaxNameBytes = 256
120
121// Extract returns the definitions in one file, in line order.
122func Extract(p string, data []byte) []Symbol {
123 var syms []Symbol
124 switch lang := Language(p); lang {
125 case "":
126 return nil
127 case "go":
128 syms = extractGo(data)
129 case "org", "markdown":
130 syms = extractHeadings(lang, data)
131 default:
132 syms = extractLines(rules[lang], data)
133 }
134 kept := syms[:0]
135 for _, s := range syms {
136 if len(s.Name) <= MaxNameBytes && len(s.Key) <= MaxNameBytes {
137 kept = append(kept, s)
138 }
139 }
140 return kept
141}
142
143func extractGo(data []byte) []Symbol {
144 head := data
145 if len(head) > 4096 {
146 head = head[:4096]
147 }
148 if generatedGo.Match(head) {
149 return nil
150 }
151 fset := token.NewFileSet()
152 // A file that does not parse still yields the declarations before the
153 // error.
154 f, _ := parser.ParseFile(fset, "", data, parser.SkipObjectResolution)
155 if f == nil {
156 return nil
157 }
158 var out []Symbol
159 add := func(id *ast.Ident, name, kind string) {
160 if id == nil || id.Name == "_" {
161 return
162 }
163 out = append(out, Symbol{Name: name, Key: id.Name, Kind: kind, Line: fset.Position(id.Pos()).Line})
164 }
165 for _, d := range f.Decls {
166 switch d := d.(type) {
167 case *ast.FuncDecl:
168 if d.Recv == nil || len(d.Recv.List) == 0 {
169 add(d.Name, d.Name.Name, "function")
170 continue
171 }
172 recv := receiverName(d.Recv.List[0].Type)
173 if recv == "" {
174 add(d.Name, d.Name.Name, "method")
175 continue
176 }
177 add(d.Name, recv+"."+d.Name.Name, "method")
178 case *ast.GenDecl:
179 for _, spec := range d.Specs {
180 switch s := spec.(type) {
181 case *ast.TypeSpec:
182 add(s.Name, s.Name.Name, "type")
183 case *ast.ValueSpec:
184 kind := "var"
185 if d.Tok == token.CONST {
186 kind = "const"
187 }
188 for _, n := range s.Names {
189 add(n, n.Name, kind)
190 }
191 }
192 }
193 }
194 }
195 return out
196}
197
198// receiverName is the type a method is declared on, without a pointer or
199// type parameters.
200func receiverName(e ast.Expr) string {
201 for {
202 switch t := e.(type) {
203 case *ast.StarExpr:
204 e = t.X
205 case *ast.ParenExpr:
206 e = t.X
207 case *ast.IndexExpr:
208 e = t.X
209 case *ast.IndexListExpr:
210 e = t.X
211 case *ast.Ident:
212 return t.Name
213 default:
214 return ""
215 }
216 }
217}
218
219// rule is one line pattern: the first submatch is the name.
220type rule struct {
221 re *regexp.Regexp
222 kind string
223}
224
225func r(kind, pattern string) rule { return rule{regexp.MustCompile(pattern), kind} }
226
227// ident is a name in the languages the line rules cover.
228const ident = `([A-Za-z_$][A-Za-z0-9_$]*)`
229
230var rules = map[string][]rule{
231 "swift": {
232 r("function", `^\s*(?:@\w+\s+)*(?:(?:public|private|fileprivate|internal|open|static|class|final|override|mutating|nonisolated|async|convenience|required)\s+)*func\s+`+ident),
233 r("class", `^\s*(?:@\w+\s+)*(?:(?:public|private|fileprivate|internal|open|final)\s+)*(?:class|actor)\s+`+ident),
234 r("struct", `^\s*(?:@\w+\s+)*(?:(?:public|private|fileprivate|internal)\s+)*struct\s+`+ident),
235 r("enum", `^\s*(?:@\w+\s+)*(?:(?:public|private|fileprivate|internal|indirect)\s+)*enum\s+`+ident),
236 r("interface", `^\s*(?:@\w+\s+)*(?:(?:public|private|fileprivate|internal)\s+)*protocol\s+`+ident),
237 r("type", `^\s*(?:(?:public|private|fileprivate|internal)\s+)*typealias\s+`+ident),
238 },
239 "rust": {
240 r("function", `^\s*(?:pub(?:\([^)]*\))?\s+)?(?:(?:const|async|unsafe|extern(?:\s+"[^"]*")?)\s+)*fn\s+`+ident),
241 r("struct", `^\s*(?:pub(?:\([^)]*\))?\s+)?struct\s+`+ident),
242 r("enum", `^\s*(?:pub(?:\([^)]*\))?\s+)?enum\s+`+ident),
243 r("interface", `^\s*(?:pub(?:\([^)]*\))?\s+)?(?:unsafe\s+)?trait\s+`+ident),
244 r("type", `^\s*(?:pub(?:\([^)]*\))?\s+)?type\s+`+ident),
245 r("module", `^\s*(?:pub(?:\([^)]*\))?\s+)?mod\s+`+ident),
246 r("const", `^\s*(?:pub(?:\([^)]*\))?\s+)?(?:const|static(?:\s+mut)?)\s+`+ident+`\s*:`),
247 r("macro", `^\s*macro_rules!\s+`+ident),
248 },
249 "python": {
250 r("function", `^(?:async\s+)?def\s+`+ident),
251 r("method", `^\s+(?:async\s+)?def\s+`+ident),
252 r("class", `^\s*class\s+`+ident),
253 },
254 "js": {
255 r("function", `^\s*(?:export\s+)?(?:default\s+)?(?:async\s+)?function\s*\*?\s*`+ident),
256 r("class", `^\s*(?:export\s+)?(?:default\s+)?(?:abstract\s+)?class\s+`+ident),
257 r("interface", `^\s*(?:export\s+)?(?:declare\s+)?interface\s+`+ident),
258 r("type", `^\s*(?:export\s+)?(?:declare\s+)?type\s+`+ident+`\s*(?:<[^=]*>)?\s*=`),
259 r("enum", `^\s*(?:export\s+)?(?:declare\s+)?(?:const\s+)?enum\s+`+ident),
260 r("const", `^(?:export\s+)?const\s+`+ident+`\s*(?::[^=]*)?=`),
261 },
262 "c": {
263 r("macro", `^\s*#\s*define\s+`+ident),
264 r("struct", `^\s*(?:typedef\s+)?struct\s+`+ident+`\s*\{`),
265 r("enum", `^\s*(?:typedef\s+)?enum\s+(?:class\s+)?`+ident+`\s*(?::[^{]*)?\{`),
266 r("class", `^\s*class\s+`+ident+`\s*(?::[^{;]*)?\{`),
267 r("type", `^\s*typedef\s+[^;(]*?\b`+ident+`\s*;`),
268 r("type", `^\s*}\s*`+ident+`\s*;`),
269 r("function", `^[A-Za-z_][\w\s\*&:<>,]*?[\s\*&]`+ident+`\s*\([^;{]*\)\s*(?:const\s*)?;`),
270 },
271 "shell": {
272 r("function", `^\s*function\s+([A-Za-z_][A-Za-z0-9_:.-]*)`),
273 r("function", `^\s*([A-Za-z_][A-Za-z0-9_:.-]*)\s*\(\)\s*(?:\{|$)`),
274 },
275}
276
277// keywords are never names, though a rule can capture one: Swift's
278// `class var x` reads as a class named var, C's `if (x);` as a prototype.
279var keywords = map[string]bool{
280 "return": true, "if": true, "while": true, "for": true, "switch": true,
281 "sizeof": true, "else": true, "case": true, "do": true, "goto": true,
282 "var": true, "let": true, "func": true, "static": true,
283}
284
285func extractLines(rs []rule, data []byte) []Symbol {
286 var out []Symbol
287 line := 0
288 for len(data) > 0 {
289 line++
290 var text []byte
291 if i := bytes.IndexByte(data, '\n'); i >= 0 {
292 text, data = data[:i], data[i+1:]
293 } else {
294 text, data = data, nil
295 }
296 if len(text) > 1000 {
297 continue
298 }
299 for _, ru := range rs {
300 m := ru.re.FindSubmatch(text)
301 if m == nil {
302 continue
303 }
304 name := string(m[1])
305 if keywords[name] {
306 continue
307 }
308 out = append(out, Symbol{Name: name, Key: name, Kind: ru.kind, Line: line})
309 break
310 }
311 }
312 return out
313}
314
315var (
316 mdHeading = regexp.MustCompile(`^#{1,6}\s+(.+?)\s*#*\s*$`)
317 orgHeading = regexp.MustCompile(`^\*+\s+(.+?)\s*$`)
318)
319
320// extractHeadings lists headings as sections, skipping what sits inside a
321// code block, where a line starting with # or * is code.
322func extractHeadings(lang string, data []byte) []Symbol {
323 var out []Symbol
324 inBlock := false
325 for i, text := range strings.Split(string(data), "\n") {
326 trimmed := strings.TrimSpace(text)
327 if lang == "markdown" {
328 if strings.HasPrefix(trimmed, "```") || strings.HasPrefix(trimmed, "~~~") {
329 inBlock = !inBlock
330 continue
331 }
332 } else {
333 lower := strings.ToLower(trimmed)
334 if strings.HasPrefix(lower, "#+begin_") {
335 inBlock = true
336 continue
337 }
338 if strings.HasPrefix(lower, "#+end_") {
339 inBlock = false
340 continue
341 }
342 }
343 if inBlock || len(text) > 1000 {
344 continue
345 }
346 re := mdHeading
347 if lang == "org" {
348 re = orgHeading
349 }
350 if m := re.FindStringSubmatch(text); m != nil {
351 out = append(out, Symbol{Name: m[1], Key: m[1], Kind: "section", Line: i + 1})
352 }
353 }
354 return out
355}