+++ /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