--- /dev/null
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package source
+
+import (
+ "context"
+ "fmt"
+ "go/ast"
+ "go/token"
+ "go/types"
+ "sort"
+ "strings"
+ "unicode"
+ "unicode/utf8"
+
+ "golang.org/x/tools/internal/event"
+ "golang.org/x/tools/internal/lsp/fuzzy"
+ "golang.org/x/tools/internal/lsp/protocol"
+ "golang.org/x/tools/internal/span"
+)
+
+// maxSymbols defines the maximum number of symbol results that should ever be
+// sent in response to a client.
+const maxSymbols = 100
+
+// WorkspaceSymbols matches symbols across all views using the given query,
+// according to the match semantics parameterized by matcherType and style.
+//
+// The workspace symbol method is defined in the spec as follows:
+//
+// The workspace symbol request is sent from the client to the server to
+// list project-wide symbols matching the query string.
+//
+// It is unclear what "project-wide" means here, but given the parameters of
+// workspace/symbol do not include any workspace identifier, then it has to be
+// assumed that "project-wide" means "across all workspaces". Hence why
+// WorkspaceSymbols receives the views []View.
+//
+// However, it then becomes unclear what it would mean to call WorkspaceSymbols
+// with a different configured SymbolMatcher per View. Therefore we assume that
+// Session level configuration will define the SymbolMatcher to be used for the
+// WorkspaceSymbols method.
+func WorkspaceSymbols(ctx context.Context, matcherType SymbolMatcher, style SymbolStyle, views []View, query string) ([]protocol.SymbolInformation, error) {
+ ctx, done := event.Start(ctx, "source.WorkspaceSymbols")
+ defer done()
+ if query == "" {
+ return nil, nil
+ }
+ sc := newSymbolCollector(matcherType, style, query)
+ return sc.walk(ctx, views)
+}
+
+// A matcherFunc determines the matching score of a symbol.
+//
+// See the comment for symbolCollector for more information.
+type matcherFunc func(name string) float64
+
+// A symbolizer returns the best symbol match for name with pkg, according to
+// some heuristic.
+//
+// See the comment for symbolCollector for more information.
+type symbolizer func(name string, pkg Package, m matcherFunc) (string, float64)
+
+func fullyQualifiedSymbolMatch(name string, pkg Package, matcher matcherFunc) (string, float64) {
+ _, score := dynamicSymbolMatch(name, pkg, matcher)
+ if score > 0 {
+ return pkg.PkgPath() + "." + name, score
+ }
+ return "", 0
+}
+
+func dynamicSymbolMatch(name string, pkg Package, matcher matcherFunc) (string, float64) {
+ // Prefer any package-qualified match.
+ pkgQualified := pkg.Name() + "." + name
+ if match, score := bestMatch(pkgQualified, matcher); match != "" {
+ return match, score
+ }
+ fullyQualified := pkg.PkgPath() + "." + name
+ if match, score := bestMatch(fullyQualified, matcher); match != "" {
+ return match, score
+ }
+ return "", 0
+}
+
+func packageSymbolMatch(name string, pkg Package, matcher matcherFunc) (string, float64) {
+ qualified := pkg.Name() + "." + name
+ if matcher(qualified) > 0 {
+ return qualified, 1
+ }
+ return "", 0
+}
+
+// bestMatch returns the highest scoring symbol suffix of fullPath, starting
+// from the right and splitting on selectors and path components.
+//
+// e.g. given a symbol path of the form 'host.com/dir/pkg.type.field', we
+// check the match quality of the following:
+// - field
+// - type.field
+// - pkg.type.field
+// - dir/pkg.type.field
+// - host.com/dir/pkg.type.field
+//
+// and return the best match, along with its score.
+//
+// This is used to implement the 'dynamic' symbol style.
+func bestMatch(fullPath string, matcher matcherFunc) (string, float64) {
+ pathParts := strings.Split(fullPath, "/")
+ dottedParts := strings.Split(pathParts[len(pathParts)-1], ".")
+
+ var best string
+ var score float64
+
+ for i := 0; i < len(dottedParts); i++ {
+ path := strings.Join(dottedParts[len(dottedParts)-1-i:], ".")
+ if match := matcher(path); match > score {
+ best = path
+ score = match
+ }
+ }
+ for i := 0; i < len(pathParts); i++ {
+ path := strings.Join(pathParts[len(pathParts)-1-i:], "/")
+ if match := matcher(path); match > score {
+ best = path
+ score = match
+ }
+ }
+ return best, score
+}
+
+// symbolCollector holds context as we walk Packages, gathering symbols that
+// match a given query.
+//
+// How we match symbols is parameterized by two interfaces:
+// * A matcherFunc determines how well a string symbol matches a query. It
+// returns a non-negative score indicating the quality of the match. A score
+// of zero indicates no match.
+// * A symbolizer determines how we extract the symbol for an object. This
+// enables the 'symbolStyle' configuration option.
+type symbolCollector struct {
+ // These types parameterize the symbol-matching pass.
+ matcher matcherFunc
+ symbolizer symbolizer
+
+ // current holds metadata for the package we are currently walking.
+ current *pkgView
+ curFile *ParsedGoFile
+
+ res [maxSymbols]symbolInformation
+}
+
+func newSymbolCollector(matcher SymbolMatcher, style SymbolStyle, query string) *symbolCollector {
+ var m matcherFunc
+ switch matcher {
+ case SymbolFuzzy:
+ m = parseQuery(query)
+ case SymbolCaseSensitive:
+ m = func(s string) float64 {
+ if strings.Contains(s, query) {
+ return 1
+ }
+ return 0
+ }
+ case SymbolCaseInsensitive:
+ q := strings.ToLower(query)
+ m = func(s string) float64 {
+ if strings.Contains(strings.ToLower(s), q) {
+ return 1
+ }
+ return 0
+ }
+ default:
+ panic(fmt.Errorf("unknown symbol matcher: %v", matcher))
+ }
+ var s symbolizer
+ switch style {
+ case DynamicSymbols:
+ s = dynamicSymbolMatch
+ case FullyQualifiedSymbols:
+ s = fullyQualifiedSymbolMatch
+ case PackageQualifiedSymbols:
+ s = packageSymbolMatch
+ default:
+ panic(fmt.Errorf("unknown symbol style: %v", style))
+ }
+ return &symbolCollector{
+ matcher: m,
+ symbolizer: s,
+ }
+}
+
+// parseQuery parses a field-separated symbol query, extracting the special
+// characters listed below, and returns a matcherFunc corresponding to the AND
+// of all field queries.
+//
+// Special characters:
+// ^ match exact prefix
+// $ match exact suffix
+// ' match exact
+//
+// In all three of these special queries, matches are 'smart-cased', meaning
+// they are case sensitive if the symbol query contains any upper-case
+// characters, and case insensitive otherwise.
+func parseQuery(q string) matcherFunc {
+ fields := strings.Fields(q)
+ if len(fields) == 0 {
+ return func(string) float64 { return 0 }
+ }
+ var funcs []matcherFunc
+ for _, field := range fields {
+ var f matcherFunc
+ switch {
+ case strings.HasPrefix(field, "^"):
+ prefix := field[1:]
+ f = smartCase(prefix, func(s string) float64 {
+ if strings.HasPrefix(s, prefix) {
+ return 1
+ }
+ return 0
+ })
+ case strings.HasPrefix(field, "'"):
+ exact := field[1:]
+ f = smartCase(exact, func(s string) float64 {
+ if strings.Contains(s, exact) {
+ return 1
+ }
+ return 0
+ })
+ case strings.HasSuffix(field, "$"):
+ suffix := field[0 : len(field)-1]
+ f = smartCase(suffix, func(s string) float64 {
+ if strings.HasSuffix(s, suffix) {
+ return 1
+ }
+ return 0
+ })
+ default:
+ fm := fuzzy.NewMatcher(field)
+ f = func(s string) float64 {
+ return float64(fm.Score(s))
+ }
+ }
+ funcs = append(funcs, f)
+ }
+ return comboMatcher(funcs).match
+}
+
+// smartCase returns a matcherFunc that is case-sensitive if q contains any
+// upper-case characters, and case-insensitive otherwise.
+func smartCase(q string, m matcherFunc) matcherFunc {
+ insensitive := strings.ToLower(q) == q
+ return func(s string) float64 {
+ if insensitive {
+ s = strings.ToLower(s)
+ }
+ return m(s)
+ }
+}
+
+type comboMatcher []matcherFunc
+
+func (c comboMatcher) match(s string) float64 {
+ score := 1.0
+ for _, f := range c {
+ score *= f(s)
+ }
+ return score
+}
+
+// walk walks views, gathers symbols, and returns the results.
+func (sc *symbolCollector) walk(ctx context.Context, views []View) (_ []protocol.SymbolInformation, err error) {
+ toWalk, release, err := sc.collectPackages(ctx, views)
+ defer release()
+ if err != nil {
+ return nil, err
+ }
+ // Make sure we only walk files once (we might see them more than once due to
+ // build constraints).
+ seen := make(map[span.URI]bool)
+ for _, pv := range toWalk {
+ sc.current = pv
+ for _, pgf := range pv.pkg.CompiledGoFiles() {
+ if seen[pgf.URI] {
+ continue
+ }
+ seen[pgf.URI] = true
+ sc.curFile = pgf
+ sc.walkFilesDecls(pgf.File.Decls)
+ }
+ }
+ return sc.results(), nil
+}
+
+func (sc *symbolCollector) results() []protocol.SymbolInformation {
+ var res []protocol.SymbolInformation
+ for _, si := range sc.res {
+ if si.score <= 0 {
+ return res
+ }
+ res = append(res, si.asProtocolSymbolInformation())
+ }
+ return res
+}
+
+// collectPackages gathers the packages we are going to inspect for symbols.
+// This pre-step is required in order to filter out any "duplicate"
+// *types.Package. The duplicates arise for packages that have test variants.
+// For example, if package mod.com/p has test files, then we will visit two
+// packages that have the PkgPath() mod.com/p: the first is the actual package
+// mod.com/p, the second is a special version that includes the non-XTest
+// _test.go files. If we were to walk both of of these packages, then we would
+// get duplicate matching symbols and we would waste effort. Therefore where
+// test variants exist we walk those (because they include any symbols defined
+// in non-XTest _test.go files).
+//
+// One further complication is that even after this filtering, packages between
+// views might not be "identical" because they can be built using different
+// build constraints (via the "env" config option).
+//
+// Therefore on a per view basis we first build up a map of package path ->
+// *types.Package preferring the test variants if they exist. Then we merge the
+// results between views, de-duping by *types.Package.
+func (sc *symbolCollector) collectPackages(ctx context.Context, views []View) ([]*pkgView, func(), error) {
+ gathered := make(map[string]map[*types.Package]*pkgView)
+ var releaseFuncs []func()
+ release := func() {
+ for _, releaseFunc := range releaseFuncs {
+ releaseFunc()
+ }
+ }
+ var toWalk []*pkgView
+ for _, v := range views {
+ seen := make(map[string]*pkgView)
+ snapshot, release := v.Snapshot(ctx)
+ releaseFuncs = append(releaseFuncs, release)
+ knownPkgs, err := snapshot.KnownPackages(ctx)
+ if err != nil {
+ return nil, release, err
+ }
+ workspacePackages, err := snapshot.WorkspacePackages(ctx)
+ if err != nil {
+ return nil, release, err
+ }
+ isWorkspacePkg := make(map[Package]bool)
+ for _, wp := range workspacePackages {
+ isWorkspacePkg[wp] = true
+ }
+ var forTests []*pkgView
+ for _, pkg := range knownPkgs {
+ toAdd := &pkgView{
+ pkg: pkg,
+ snapshot: snapshot,
+ isWorkspace: isWorkspacePkg[pkg],
+ }
+ // Defer test packages, so that they overwrite seen for this package
+ // path.
+ if pkg.ForTest() != "" {
+ forTests = append(forTests, toAdd)
+ } else {
+ seen[pkg.PkgPath()] = toAdd
+ }
+ }
+ for _, pkg := range forTests {
+ seen[pkg.pkg.PkgPath()] = pkg
+ }
+ for _, pkg := range seen {
+ pm, ok := gathered[pkg.pkg.PkgPath()]
+ if !ok {
+ pm = make(map[*types.Package]*pkgView)
+ gathered[pkg.pkg.PkgPath()] = pm
+ }
+ pm[pkg.pkg.GetTypes()] = pkg
+ }
+ }
+ for _, pm := range gathered {
+ for _, pkg := range pm {
+ toWalk = append(toWalk, pkg)
+ }
+ }
+ // Now sort for stability of results. We order by
+ // (pkgView.isWorkspace, pkgView.p.ID())
+ sort.Slice(toWalk, func(i, j int) bool {
+ lhs := toWalk[i]
+ rhs := toWalk[j]
+ switch {
+ case lhs.isWorkspace == rhs.isWorkspace:
+ return lhs.pkg.ID() < rhs.pkg.ID()
+ case lhs.isWorkspace:
+ return true
+ default:
+ return false
+ }
+ })
+ return toWalk, release, nil
+}
+
+func (sc *symbolCollector) walkFilesDecls(decls []ast.Decl) {
+ for _, decl := range decls {
+ switch decl := decl.(type) {
+ case *ast.FuncDecl:
+ kind := protocol.Function
+ var recv *ast.Ident
+ if decl.Recv != nil {
+ kind = protocol.Method
+ switch typ := decl.Recv.List[0].Type.(type) {
+ case *ast.StarExpr:
+ recv = typ.X.(*ast.Ident)
+ case *ast.Ident:
+ recv = typ
+ }
+ }
+ if recv != nil {
+ sc.match(decl.Name.Name, kind, decl.Name, recv)
+ } else {
+ sc.match(decl.Name.Name, kind, decl.Name)
+ }
+ case *ast.GenDecl:
+ for _, spec := range decl.Specs {
+ switch spec := spec.(type) {
+ case *ast.TypeSpec:
+ sc.match(spec.Name.Name, typeToKind(sc.current.pkg.GetTypesInfo().TypeOf(spec.Type)), spec.Name)
+ sc.walkType(spec.Type, spec.Name)
+ case *ast.ValueSpec:
+ for _, name := range spec.Names {
+ kind := protocol.Variable
+ if decl.Tok == token.CONST {
+ kind = protocol.Constant
+ }
+ sc.match(name.Name, kind, name)
+ }
+ }
+ }
+ }
+ }
+}
+
+// walkType processes symbols related to a type expression. path is path of
+// nested type identifiers to the type expression.
+func (sc *symbolCollector) walkType(typ ast.Expr, path ...*ast.Ident) {
+ switch st := typ.(type) {
+ case *ast.StructType:
+ for _, field := range st.Fields.List {
+ sc.walkField(field, protocol.Field, protocol.Field, path...)
+ }
+ case *ast.InterfaceType:
+ for _, field := range st.Methods.List {
+ sc.walkField(field, protocol.Interface, protocol.Method, path...)
+ }
+ }
+}
+
+// walkField processes symbols related to the struct field or interface method.
+//
+// unnamedKind and namedKind are the symbol kinds if the field is resp. unnamed
+// or named. path is the path of nested identifiers containing the field.
+func (sc *symbolCollector) walkField(field *ast.Field, unnamedKind, namedKind protocol.SymbolKind, path ...*ast.Ident) {
+ if len(field.Names) == 0 {
+ sc.match(types.ExprString(field.Type), unnamedKind, field, path...)
+ }
+ for _, name := range field.Names {
+ sc.match(name.Name, namedKind, name, path...)
+ sc.walkType(field.Type, append(path, name)...)
+ }
+}
+
+func typeToKind(typ types.Type) protocol.SymbolKind {
+ switch typ := typ.Underlying().(type) {
+ case *types.Interface:
+ return protocol.Interface
+ case *types.Struct:
+ return protocol.Struct
+ case *types.Signature:
+ if typ.Recv() != nil {
+ return protocol.Method
+ }
+ return protocol.Function
+ case *types.Named:
+ return typeToKind(typ.Underlying())
+ case *types.Basic:
+ i := typ.Info()
+ switch {
+ case i&types.IsNumeric != 0:
+ return protocol.Number
+ case i&types.IsBoolean != 0:
+ return protocol.Boolean
+ case i&types.IsString != 0:
+ return protocol.String
+ }
+ }
+ return protocol.Variable
+}
+
+// match finds matches and gathers the symbol identified by name, kind and node
+// via the symbolCollector's matcher after first de-duping against previously
+// seen symbols.
+//
+// path specifies the identifier path to a nested field or interface method.
+func (sc *symbolCollector) match(name string, kind protocol.SymbolKind, node ast.Node, path ...*ast.Ident) {
+ if !node.Pos().IsValid() || !node.End().IsValid() {
+ return
+ }
+
+ isExported := isExported(name)
+ if len(path) > 0 {
+ var nameBuilder strings.Builder
+ for _, ident := range path {
+ nameBuilder.WriteString(ident.Name)
+ nameBuilder.WriteString(".")
+ if !ident.IsExported() {
+ isExported = false
+ }
+ }
+ nameBuilder.WriteString(name)
+ name = nameBuilder.String()
+ }
+
+ // Factors to apply to the match score for the purpose of downranking
+ // results.
+ //
+ // These numbers were crudely calibrated based on trial-and-error using a
+ // small number of sample queries. Adjust as necessary.
+ //
+ // All factors are multiplicative, meaning if more than one applies they are
+ // multiplied together.
+ const (
+ // nonWorkspaceFactor is applied to symbols outside of any active
+ // workspace. Developers are less likely to want to jump to code that they
+ // are not actively working on.
+ nonWorkspaceFactor = 0.5
+ // nonWorkspaceUnexportedFactor is applied to unexported symbols outside of
+ // any active workspace. Since one wouldn't usually jump to unexported
+ // symbols to understand a package API, they are particularly irrelevant.
+ nonWorkspaceUnexportedFactor = 0.5
+ // fieldFactor is applied to fields and interface methods. One would
+ // typically jump to the type definition first, so ranking fields highly
+ // can be noisy.
+ fieldFactor = 0.5
+ )
+ symbol, score := sc.symbolizer(name, sc.current.pkg, sc.matcher)
+
+ // Downrank symbols outside of the workspace.
+ if !sc.current.isWorkspace {
+ score *= nonWorkspaceFactor
+ if !isExported {
+ score *= nonWorkspaceUnexportedFactor
+ }
+ }
+
+ // Downrank fields.
+ if len(path) > 0 {
+ score *= fieldFactor
+ }
+
+ // Avoid the work below if we know this score will not be sorted into the
+ // results.
+ if score <= sc.res[len(sc.res)-1].score {
+ return
+ }
+
+ mrng := NewMappedRange(sc.current.snapshot.FileSet(), sc.curFile.Mapper, node.Pos(), node.End())
+ rng, err := mrng.Range()
+ if err != nil {
+ return
+ }
+ si := symbolInformation{
+ score: score,
+ name: name,
+ symbol: symbol,
+ container: sc.current.pkg.PkgPath(),
+ kind: kind,
+ location: protocol.Location{
+ URI: protocol.URIFromSpanURI(mrng.URI()),
+ Range: rng,
+ },
+ }
+ insertAt := sort.Search(len(sc.res), func(i int) bool {
+ return sc.res[i].score < score
+ })
+ if insertAt < len(sc.res)-1 {
+ copy(sc.res[insertAt+1:], sc.res[insertAt:len(sc.res)-1])
+ }
+ sc.res[insertAt] = si
+}
+
+// isExported reports if a token is exported. Copied from
+// token.IsExported (go1.13+).
+//
+// TODO: replace usage with token.IsExported once go1.12 is no longer
+// supported.
+func isExported(name string) bool {
+ ch, _ := utf8.DecodeRuneInString(name)
+ return unicode.IsUpper(ch)
+}
+
+// pkgView holds information related to a package that we are going to walk.
+type pkgView struct {
+ pkg Package
+ snapshot Snapshot
+ isWorkspace bool
+}
+
+// symbolInformation is a cut-down version of protocol.SymbolInformation that
+// allows struct values of this type to be used as map keys.
+type symbolInformation struct {
+ score float64
+ name string
+ symbol string
+ container string
+ kind protocol.SymbolKind
+ location protocol.Location
+}
+
+// asProtocolSymbolInformation converts s to a protocol.SymbolInformation value.
+//
+// TODO: work out how to handle tags if/when they are needed.
+func (s symbolInformation) asProtocolSymbolInformation() protocol.SymbolInformation {
+ return protocol.SymbolInformation{
+ Name: s.symbol,
+ Kind: s.kind,
+ Location: s.location,
+ ContainerName: s.container,
+ }
+}
projects / dotfiles / .git / blobdiff