internal/symbols/extract.go

  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}