[clangd] Implementation of workspace/symbol request

[malaperle]

Summary

This is a basic implementation of the "workspace/symbol" request which is
used to find symbols by a string query. Since this is similar to code completion
in terms of result, this implementation reuses the "fuzzyFind" in order to get
matches. For now, the scoring algorithm is the same as code completion and
improvements could be done in the future.

The index model doesn't contain quite enough symbols for this to cover
common symbols like methods, enum class enumerators, functions in unamed
namespaces, etc. The index model will be augmented separately to achieve this.

[ilya-biryukov]

Adding @sammccall, he will definitely want to take a look at index-related changes.
On a high level, the approach seems just right.
A few questions immedieately that came to mind:

• Unconditionally storing much more symbols in the index might have subtle performance implications, especially for our internal use (the codebase is huge). I bet that internally we wouldn't want to store the symbols not needed for completion, so we'll probably need a switch to disable storing them in the indexing implementation. But let's wait for Sam to take a look, he certainly has a better perspective on the issues there.
• Current fuzzyFind implementation can only match qualifiers strictly (i.e. st::vector won't match std::vector). Should we look into allowing fuzzy matches for this feature? (not in this patch, rather in the long term).
• Have you considered also allowing '.' and ' ' (space) as separators in the request? Having additional separators doesn't really hurt complexity of the implementation, but allows to switch between tools for different languages easier.

E.g., std.vector.push_back and std vector push_back could produce the same matches as std::vector::push_back.

clangd/ClangdServer.h

162

NIT: use Callback typedef.

clangd/WorkspaceSymbols.cpp

165 ↗

(On Diff #139749)

We have FuzzyMatcher, it can produce decent match scores and is already used in completion.
Any reason not to use it here?

clangd/index/Index.h

141 ↗

(On Diff #139749)

NIT: remove empty lines to be consistent with the rest of the struct.

[malaperle]

In D44882#1048043, @ilya-biryukov wrote:

• Unconditionally storing much more symbols in the index might have subtle performance implications, especially for our internal use (the codebase is huge). I bet that internally we wouldn't want to store the symbols not needed for completion, so we'll probably need a switch to disable storing them in the indexing implementation. But let's wait for Sam to take a look, he certainly has a better perspective on the issues there.

I'm a bit surprised that internally you do not want symbols beyond the ones for completion. We have a lot more features in mind that will make the index much bigger, like adding all occurrences (maybe not in the current YAML though). But having options to control the amount of information indexed sounds good to me as there can be a lot of different project sizes and there can be different tradeoffs. I had in mind to an option for including/excluding the occurrences because without them, you lose workspace/references, call hierarchy, etc, but you still have code completion and workspace/symbol, document/symbol, etc while making the index much smaller. But more options sounds good.

• Current fuzzyFind implementation can only match qualifiers strictly (i.e. st::vector won't match std::vector). Should we look into allowing fuzzy matches for this feature? (not in this patch, rather in the long term).

I'm not sure, I'm thinking there should be a balance between how fuzzy it it and how much noise it generates. Right now I find it a bit too fuzzy since when I type "Draft" (to find DraftMgr), it picks up things like DocumentRangeFormattingParams. Adding fuzziness to the namespace would make this worse. Maybe with improved scoring it won't matter too much? I'll try FuzzyMatcher and see.

• Have you considered also allowing '.' and ' ' (space) as separators in the request? Having additional separators doesn't really hurt complexity of the implementation, but allows to switch between tools for different languages easier.

E.g., std.vector.push_back and std vector push_back could produce the same matches as std::vector::push_back.

I haven't thought of that and I think it's a good idea. Sounds like a good, isolated thing to do in a separate patch.

[malaperle]

clangd/WorkspaceSymbols.cpp

165 ↗

(On Diff #139749)

I think it was giving odd ordering but let me try this again and at least document the reason.

[sammccall]

Very nice! I'd like to reduce the scope of the initial patch, which seems to be possible, so we can review the details but not get bogged down too much.

In D44882#1048179, @malaperle wrote:

In D44882#1048043, @ilya-biryukov wrote:

• Unconditionally storing much more symbols in the index might have subtle performance implications, especially for our internal use (the codebase is huge). I bet that internally we wouldn't want to store the symbols not needed for completion, so we'll probably need a switch to disable storing them in the indexing implementation. But let's wait for Sam to take a look, he certainly has a better perspective on the issues there.

I'm a bit surprised that internally you do not want symbols beyond the ones for completion.

FWIW, I think we do, it just needs to be done carefully (with the right semantic filters at query time, and metadata at indexing time).
Can we split this patch up (it's pretty large anyway) and land the workspaceSymbols implementation first, without changing the indexer behavior?

I think the indexer changes are in the right direction, but I think "ForCompletion" isn't quite enough metadata, and don't want to block everything on that.

We have a lot more features in mind that will make the index much bigger, like adding all occurrences (maybe not in the current YAML though).

(tangential)
FWIW, I think *that* might be a case where we want quite a different API - I think this is a file-major index operation (handful of results per file) rather than a symbol-major one (results per symbol is essentially unbounded, e.g. std::string). At the scale of google's internal codebase, this means we need a different backend, and this may be the case for large open-source codebases too (I know chromium hits scaling issues with indexers they try).
There are also other operations where results are files rather than symbols: which files include file x, etc.

But having options to control the amount of information indexed sounds good to me as there can be a lot of different project sizes and there can be different tradeoffs. I had in mind to an option for including/excluding the occurrences because without them, you lose workspace/references, call hierarchy, etc, but you still have code completion and workspace/symbol, document/symbol, etc while making the index much smaller. But more options sounds good.

If we add options, someone has to actually set them.
Anything that's too big for google's internal index or similar can be filtered out in the wrapping code (mapreduce) if the indexer exposes enough information to do so.
We shouldn't have problems with the in-memory dynamic index.
Features that are off in the default static indexer configuration won't end up getting used much.

So I can see a use for filters where the command-line indexer (YAML) would run too slow otherwise, but a) let's cross that bridge when we come to it and b) there's lots of low-hanging fruit there - the YAML format itself should be considered a placeholder.

• Current fuzzyFind implementation can only match qualifiers strictly (i.e. st::vector won't match std::vector). Should we look into allowing fuzzy matches for this feature? (not in this patch, rather in the long term).

I'm not sure, I'm thinking there should be a balance between how fuzzy it it and how much noise it generates. Right now I find it a bit too fuzzy since when I type "Draft" (to find DraftMgr), it picks up things like DocumentRangeFormattingParams. Adding fuzziness to the namespace would make this worse. Maybe with improved scoring it won't matter too much? I'll try FuzzyMatcher and see.

+1, I think experience with workspaceSymbols will help us answer this question.

clangd/ClangdLSPServer.cpp

107

This is the analogue to the one on completion that we currently ignore, and one on symbol corresponding to the documentSymbol call which isn't implemented yet.

I think the value of the extended types is low and it might be worth leaving out of the first version to keep complexity down.
(If we really want it, the supporting code (mapping tables) should probably be in a place where it can be reused by documentSymbol and can live next to the equivalent for completion...)

clangd/ClangdLSPServer.h

94

This comment is just the var name, delete?

95

actually, I'm not sure this is worth tracking at all.
Dynamic index is on by default, and the worst that can happen is some dynamically-configured clients will show a menu option in a non-default configuration, but it won't actually work.
I don't think fixing this is worth the layering violation

clangd/ClangdServer.h

160

onWorkspaceSymbol -> workspaceSymbols

clangd/WorkspaceSymbols.cpp

1 ↗

(On Diff #139749)

as noted elsewhere, adjustKindToCapability etc need to be sharable, so I'm not sure this file structure quite works - it's named too narrowly to have any shared functionality, but if you pull those functions out there's only one left.

Maybe we could rename this FindSymbols.cpp, and then documentSymbols will also live here?

165 ↗

(On Diff #139749)

I think it's going to be worth pulling out a scoring concept/function here, we can't reuse the priority from the sema codecompletion, but the server's going to provide useful scoring signals.
I'm not sure how much we want to keep this in sync with code completion overall, though.

clangd/WorkspaceSymbols.h

37 ↗

(On Diff #139749)

so reading all the files we return from the index is obviously going to be bad, we screwed up the interfaces :-)

From discussing with people who've dealt with similar things, we're probably going to need to store both row/col and offset in the index. I'll try to fix this soon...
What you're doing for now is fine, but should probably have loud fixmes on it.

clangd/index/Index.h

143 ↗

(On Diff #139749)

This strikes me as conflating a bunch of ideas that are independently important (e.g. is the symbol top-level, is it visible outside the declaring file). We should design this carefully after considering LSP features that might use the index.

clangd/tool/ClangdMain.cpp

105

the -completion-limit was mostly to control rollout, I'm not sure this needs to be a flag. If it does, can we make it the same flag as completions (and call it -limit or so?)

122

if we're renaming this, just -index?

[ilya-biryukov]

• Current fuzzyFind implementation can only match qualifiers strictly (i.e. st::vector won't match std::vector). Should we look into allowing fuzzy matches for this feature? (not in this patch, rather in the long term).

I'm not sure, I'm thinking there should be a balance between how fuzzy it it and how much noise it generates. Right now I find it a bit too fuzzy since when I type "Draft" (to find DraftMgr), it picks up things like DocumentRangeFormattingParams. Adding fuzziness to the namespace would make this worse. Maybe with improved scoring it won't matter too much? I'll try FuzzyMatcher and see.

+1, I think experience with workspaceSymbols will help us answer this question.

I was using an IDE that had fuzzy find for an equivalent of workspaceSymbols and found it to be an amazing experience. And having consistent behavior between different features is really nice.
Good ranking is a key to it being useful, though. If when typing Draft you get DocumentRangeFormattingParams ranked higher than DraftMgr that's a bug in FuzzyMatcher. If you have some not-very-nice results at the end of the list, this shouldn't be a problem in most cases.

I'm highly in favor of enabling fuzzy matching for workspaceSymbols.

[ilya-biryukov]

I'm highly in favor of enabling fuzzy matching for workspaceSymbols.

At lest for the name themselves. Non-fuzzy matching of qualifiers does not look that important.

[malaperle]

In D44882#1048355, @sammccall wrote:

Can we split this patch up (it's pretty large anyway) and land the workspaceSymbols implementation first, without changing the indexer behavior?

I think the indexer changes are in the right direction, but I think "ForCompletion" isn't quite enough metadata, and don't want to block everything on that.

Sounds good. ForCompletion was more of a short term hack in my mind, we can try to split it and make proper metadata.

We have a lot more features in mind that will make the index much bigger, like adding all occurrences (maybe not in the current YAML though).

(tangential)
FWIW, I think *that* might be a case where we want quite a different API - I think this is a file-major index operation (handful of results per file) rather than a symbol-major one (results per symbol is essentially unbounded, e.g. std::string). At the scale of google's internal codebase, this means we need a different backend, and this may be the case for large open-source codebases too (I know chromium hits scaling issues with indexers they try).
There are also other operations where results are files rather than symbols: which files include file x, etc.

Yeah, there needs to be an API to fetch things per file, such as the dependencies and the occurrences it contains (for updating when the file is deleted, etc). I'm not sure there needs to be an API that queries a file for a given USR though, I think that could be transparent to the caller and an implementation detail. The results could be grouped by file though. Good discussion for future patches :)

But having options to control the amount of information indexed sounds good to me as there can be a lot of different project sizes and there can be different tradeoffs. I had in mind to an option for including/excluding the occurrences because without them, you lose workspace/references, call hierarchy, etc, but you still have code completion and workspace/symbol, document/symbol, etc while making the index much smaller. But more options sounds good.

If we add options, someone has to actually set them.
Anything that's too big for google's internal index or similar can be filtered out in the wrapping code (mapreduce) if the indexer exposes enough information to do so.
We shouldn't have problems with the in-memory dynamic index.
Features that are off in the default static indexer configuration won't end up getting used much.

I think everything should be ON by default but we can run into issues that the user wants to reduce index size and help indexing speed. We had such options in CDT since there are quite a few things that can make it big (macro expansion steps, all references, etc). But this can be added as needed later.

So I can see a use for filters where the command-line indexer (YAML) would run too slow otherwise, but a) let's cross that bridge when we come to it

Sounds good.

In D44882#1049007, @ilya-biryukov wrote:

• Current fuzzyFind implementation can only match qualifiers strictly (i.e. st::vector won't match std::vector). Should we look into allowing fuzzy matches for this feature? (not in this patch, rather in the long term).

I'm not sure, I'm thinking there should be a balance between how fuzzy it it and how much noise it generates. Right now I find it a bit too fuzzy since when I type "Draft" (to find DraftMgr), it picks up things like DocumentRangeFormattingParams. Adding fuzziness to the namespace would make this worse. Maybe with improved scoring it won't matter too much? I'll try FuzzyMatcher and see.

+1, I think experience with workspaceSymbols will help us answer this question.

I was using an IDE that had fuzzy find for an equivalent of workspaceSymbols and found it to be an amazing experience. And having consistent behavior between different features is really nice.
Good ranking is a key to it being useful, though. If when typing Draft you get DocumentRangeFormattingParams ranked higher than DraftMgr that's a bug in FuzzyMatcher. If you have some not-very-nice results at the end of the list, this shouldn't be a problem in most cases.

I'm highly in favor of enabling fuzzy matching for workspaceSymbols.

I think it will be fine once we address the bug(s). As long as the exact matches are always first then there's no problem.

clangd/ClangdLSPServer.cpp

107

I think having Struct and EnumMember is nice and for sure once Macros is there we will want to use it. So would it be OK to move to FindSymbols.cpp (the new common file for document/symbol and workspace/symbol)?

clangd/ClangdLSPServer.h

95

I wonder if the "enable-index-based" is even necessary...

clangd/WorkspaceSymbols.cpp

1 ↗

(On Diff #139749)

FindSymbols.cpp sounds good, I was thinking of moving things around once I introduce document/symbols but we might as well name this appropriately in the first place.

165 ↗

(On Diff #139749)

I think I'm going to remove the sort here and try to investigate the FuzzyMatcher separately. It seems to work correctly for code completion but for workspace symbols there are many more results and it looks like the scoring needs to be tweaked.

clangd/WorkspaceSymbols.h

37 ↗

(On Diff #139749)

I added a FIXME in the implementation. You should probably chime in https://reviews.llvm.org/D39050, about storing more things in the index to not read all files :-)

clangd/index/Index.h

143 ↗

(On Diff #139749)

Agreed. I was hesitant between adding a bunch of additional information/fields or adding just one for simplicity and revisit when we need more features. But it would be best if this could be well defined from the get go and was hoping for some suggestions on how to go about this. Doing this in a separate patch makes a lot of sense to me.

clangd/tool/ClangdMain.cpp

105

I think it's quite similar to "completions", when you type just one letter for example, you can get a lot of results and a lot of JSON output. So it feels like the flag could apply to both completions and workspace symbols. How about -limit-resuts? I think just -limit might be a bit too general as we might want to limit other things.

[malaperle]

Split the patch so that this part only has the workspace/symbol part
and the index model will be updated separately.

[MaskRay]

Have you considered also allowing '.' and ' ' (space) as separators in the request? Having additional separators doesn't really hurt complexity of the implementation, but allows to switch between tools for different languages easier.

I would suggest allowing patterns containing space to match text without space, e.g. pattern a b can match text aB. The initial character of each word in the pattern should be seen as a Head position. This behavior matches many fuzzy matching plugins used in Emacs and Vim.

clangd/SourceCode.cpp

108

May I ask a question about the conversion between SourceLocation and LSP location? When the document is slightly out of sync with the indexed version, what will be returned?

[MaskRay]

clangd/tool/ClangdMain.cpp

105

Can these options be set by LSP initialization options?

[malaperle]

The index changes are moved here: https://reviews.llvm.org/D44954 I haven't changed the patch yet though, I just removed it from this one.

[malaperle]

clangd/SourceCode.cpp

108

I forgot to cover the case of the unsaved files, which are indexed in memory. It that what you mean? I'll update the patch to address by using the DraftStore when available. There is also the case where the file is not opened but outdated on disk. I don't think we can do much about it but make sure it doesn't crash :) At worst, the location might be off, and navigation will be momentarily affected, until the index can be updated with the file change. This is what I've noticed in other IDEs as well.

clangd/tool/ClangdMain.cpp

105

They could. Are you say they *should*? We could add it in DidChangeConfigurationParams/ClangdConfigurationParamsChange (workspace/didChangeConfiguration) if we need to. I haven't tried or needed to add it on the client side though. It's not 100% clear what should go in workspace/didChangeConfiguration but I think it should probably things that the user would change more often at run-time. I'm not sure how frequent this "limit" will be changed by the user.

[malaperle]

Use the DraftStore for offset -> line/col when there is a draft available.

[malaperle]

I realized that using the draft store has limited improvement for now because not many symbol locations come from main files (.cpp, etc) and when headers are modified, the main files are not reindexed right now. So the draft store will give better location for example when navigating to a function definition which moved in the unsaved main file. But it will be more general once header updates are handled better.

[MaskRay]

clangd/FindSymbols.cpp

32

This std::find loop adds some overhead to each candidate... In my experience the client usually doesn't care about the returned symbol kinds, they are used to give a category name. You can always patch the upstream to add missing categories.

This is one instance where LSP is over specified. nvm I don't have strong opinion here

clangd/Protocol.cpp

206

This copy-pasting exposes another problem that the current fromJSON toJSON approach is too verbose and you may find other space-efficient serialization format convenient .... Anyway, they can always be improved in the future.

clangd/tool/ClangdMain.cpp

235

I know command line options are easy for testing purpose but they are clumsy for users. You need a "initialization option" <-> "command line option" bridge.

[sammccall]

This is fantastic, really looking forward to using it.
I'm going to need to give up on vim at this rate, or do some serious work on ycm.

Most significant comments are around the new functions in SourceLocation, and whether we can keep the type-mapping restricted to the LSP layer.

clangd/ClangdLSPServer.cpp

107

I think having Struct and EnumMember is nice and for sure once Macros is there we will want to use it.

OK, fair enough.

I think what bothers me about this option is how deep it goes - this isn't really a request option in any useful sense.
I'd suggest the "C++ layer" i.e. ClangdServer should always return full-fidelity results, and the "LSP layer" should deal with folding them.

In which case adjustKindToCapability should live somewhere like protocol.h and get called from this file - WDYT?

clangd/ClangdServer.h

160

nit: add a comment for this API, e.g. /// Retrieve the top symbols from the workspace matching a query

clangd/FindSymbols.cpp

29

Can we rather have this condition checked when the client sets the supported symbols, and remove this special knowledge here?

33

this seems gratuituously inefficient - I guess it doesn't matter that much, but can't we store the supported kinds as a std::bitset or so?

37

nit: if we think this will be extended, a switch might be clearer

43

This code shouldn't need to handle this case. The LSP specifies the default set of supported types if it's not provided, so ClangdLSPServer should enure we always have a valid set

115

why Query.empty()?
In practice maybe showing results before you type is bad UX, but that seems up to the editor to decide.

118

nit: move this below the next "paragraph" where it's used?

131

nit: this is Names.first.consume_front("::")
Might be clearer as "FuzzyFind doesn't want leading :: qualifier" to avoid implication, that global namespace is special, particularly because...

131

actually the global namespace *is* special :-)

IMO If you type Foo, you should get results from any namespace, but if you type ::Foo you should only get results from the global namespace.

So something like:

if (Names.first.consume_front("::") || !Names.first.empty())
  Req.Scopes = {Names.first};

though more explicit handling of the cases may be clearer

142

Ugh, I never know what the right thing is here, decl/def split is a mess, and there's lots of different workflows.

I don't have any problem with the choice made here (personally I'd probably prefer canonical decl if we had working gotodefn), but it's subtle, so I think it should be a bit louder :-)
Maybe just a comment // Prefer the definition over e.g. a function declaration in a header - that's the most important case that differs.

If we see this decision popping up again maybe we should put it as a function on Symbol to call out/codify this decision?
e.g. SymbolLocation Symbol::NavigationLocation() { return Definition ? Definition : CanonicalDeclaration; }
but up to you' that's probably premature

157

nit: move into if?

160

maybe add an assertion that the adjusted SK is supported? (This should be easier if the supportedSymbolKinds is always provided)

163

The most obvious reading of the spec to me, and the one that matches the language servers I found, is that the containerName should be "foo::bar", not "foo::bar::"

clangd/Protocol.cpp

194

there's two right ways to do this which are conflated a bit here:

• make the field of type T, give it a meaningful default value, and map it optionally (ignore return value of map())
• make the field of type Optional<T>, let the default be none, and require map() to succeed (which it will if the field is missing)

So I think you want O && O.map("valueSet", R.valueSet), and below. This has the advantage that if valueSet is present in the message but has an invalid value, parsing will fail.

(Yes, this is confusing and not at all ideal, sorry...)

clangd/SourceCode.cpp

79

This function seems to be biting off more than it can chew - it's really hard to abstract this away and its callsites don't seem to fit the same pattern.

I'd probably suggest moving it back and having FindSymbols do just the part it needs locally.

First, SourceRange doesn't have a consistent set of semantics stronger than "a pair of sourcelocations". The first element always indicates the first point in the range, but the second element can be any of:

• the first character outside the range (you're assuming this, which I think is actually the rarest in clang)
• the last character inside the range
• the first character of the last token inside the range (this is the least useful and I think most common!)

Secondly, there's several ways to interpret a location and the choice is somewhat arbitrary here. (in fact the choice isn't consistent even within the function - you may take the spelling location sometimes and the expansion location other times).

Third, the failure mechanism is opaque - this might fail and we don't describe how, so callsites are going to depend on the implementation details, and possibly end up doing redundant fallbacks.

Maybe most importantly, in the long run this is doing complicated and redundant work to push workspaceSymbols through this function:

• constructing a path from SourceLocation is useful to xrefs, but documentHighlights had the path in the first place!
• converting offset->row/column for workspaceSymbols is more simply done without SourceManager (VFS + offsetToPosition) and will go away entirely when we fix the index.

clangd/index/SymbolCollector.cpp

320

the message just repeats the assert expression, remove?
(I think this would be slightly clearer if it was just below OS.flush)

clangd/tool/ClangdMain.cpp

105

Static configuration that's available at construction time is much easier to work with, it follows the lifetime of the C++ objects. The LSP-initialization is an annoying fact of life, but not too bad since no "real work" needs to happen first.

If a parameter actually needs to be dynamic, we should strive to specify it at request-time, that's also a simple logical model. If we're going to have to extend LSP for this stuff anyway, we might as well extend the requests.

The didChangeConfiguration is very difficult to work with in my view, and we should avoid adding more options there at all possible.

Aside: several times I've attempted to clean up the GlobalCompilationDatabase and run up against this requirement that breaks most attempts at abstraction. (I'm curious why just restarting clangd when the compilation database is overridden doesn't work). At some point as we add the abstractions needed to track changes on disk and dependent rebuilds, we'll get a chance to revisit how this works.

unittests/clangd/FindSymbolsTests.cpp

21

nit: please move to operator<< declared in protocol.h

23

(if stripping :: from containername, don't forget to update here)

48

(nit: why are all these on the heap?)

54

nit: it's rare to need SetUp, the constructor is fine (and consistent with other tests)

96

these negative tests spell the exact name of the symbol and assert the results are empty.
They'll pass if the name is spelled/formatted wrong - maybe prefer getSymbols("l") or getSymbols("")?

100

combine with NoLocals?

121

Can we hold off on these tests until the functionality is in? (though do include *something* in a namespace)

180

maybe add more namespace cases to this:

namespace ans1 { int ai1; namespace ans2 { int ai2 } }

"a" -> ans1, ans1::i1, ans1::ans2, ans1::ans2::i2
"::a" -> ans1
"ans1::" -> ans1::ans2, ans1::ai1
"::ans1::ans2::" -> ans1::ans2::ai2

210

can you include a symbol inside a namespace, and verify it doesn't get returned? (or combine with other namespaces queries as suggested above)

246

the enums/union/inlinenamespace cases seem to be basically testing symbolcollector again - the only differences here are on the indexing side. So I think they're ok to drop.

[malaperle]

clangd/FindSymbols.cpp

32

I have a client that throws an exception when the symbolkind is not known and the whole request fails, so I think it's worth checking. But if it's too slow I can look at making it faster. Unfortunately, I cannot patch any upstream project :)

[MaskRay]

clangd/FindSymbols.cpp

32

https://github.com/gluon-lang/languageserver-types/blob/master/src/lib.rs#L2016

LanguageClient-neovim returns empty candidate list if one of the candidates has unknown SymbolKind. Apparently they should be more tolerant and there is an issue tracking it.

[MaskRay]

clangd/FindSymbols.cpp

32

If it was not an internal confidential client, I would like to know its name, unless the confidentiality includes the existence of the client.

[malaperle]

clangd/FindSymbols.cpp

32

Sorry, I should have explained a bit more my thought. I see that an older-ish version of Monaco is not handling unknown symbols kinds well. I don't really know if it's our integration with Monaco or Monaco itself (the IDE is Theia). But my thought is that there are clients out there that follow the protocol "correctly" by choosing not to handle those unknown symbol kinds gracefully. I am not that concerned about a single client in particular, just general support of clients out there. As a server, I think it makes sense to support clients that follow the protocol, especially since 1.x and 2.x are not that old. I don't think it's the crux of the complexity of this patch.

[hokein]

clangd/ClangdLSPServer.cpp

270

InvalidParams doesn't match all cases where internal errors occur. Maybe use ErrorCode::InternalError?

clangd/FindSymbols.cpp

146

I think we may want to report the error to client instead of just logging them.

clangd/SourceCode.cpp

140

nit: this comment is duplicated with the one in header.

clangd/SourceCode.h

58

We should use llvm::Expected?

The function needs a comment documenting its behavior, especially on the unsaved file content.

60

nit: name FilePath or FileName, File seems to be a bit confusing, does it mean FileContent or FileName?

[malaperle]

Address comments.

clangd/ClangdLSPServer.cpp

107

Sounds good, I moved it.

270

Sounds good.

clangd/FindSymbols.cpp

29

"supportedSymbolKinds" is now populated with those base symbol kinds at initialization.

43

My thought is that if we start dealing with one of those:

Object = 19,
Key = 20,
Null = 21,
Event = 24,
Operator = 25,
TypeParameter = 26

and it's an older client that only supports up to "Array = 18", then we can provide a fallback, otherwise the client my not handle the unknown kind gracefully. But we can add this later if necessary I guess.

115

vscode sends an empty query and it also doesn't show all symbols in Typescript for example, so that's why I thought that would be best.

131

Sounds good. I think this works well.

142

I think perhaps this could be a user option and making that decision (reading the option and returning the decl) would make sense in a function. Perhaps this can be added a bit later.

146

I'm not sure, wouldn't that mean aborting the whole request? I think by logging only, if one symbol has a problem and not the others, the request could still provide a lot of good results.

160

I added an assertion in ClangdLSPServer, where adjustKindToCapability is now called.

163

Sounds good. I had to create a temp std::string *and* StringRef, yuck.

clangd/SourceCode.cpp

79

This function seems to be biting off more than it can chew - it's really hard to abstract this away and its callsites don't seem to fit the same pattern.
I'd probably suggest moving it back and having FindSymbols do just the part it needs locally.

Sure, I'll move it back/ make a local one. In the end the one in xrefs will be quite similar, especially once we add the proper "go to definition" (soon!) but maybe it's less confusing to duplicate some code here.

you may take the spelling location sometimes and the expansion location other times

What do you mean here? I see spelling but not expansion, maybe I missed it.

converting offset->row/column for workspaceSymbols is more simply done without SourceManager (VFS + offsetToPosition) and will go away entirely when we fix the index.

More simply but I'm not 100% sure it's better. I would be good to somehow reuse the logic in SourceManager's ComputeLineNumbers as it seems to be faster (SSE?) and handles more cases (\r?).
If I were to change the code to use VFS, how would I go about it? I would use FileSystem::getBufferForFile but to prevent reloading the same buffer over and over, then I would need to keep a map of filenames -> buffers, which pretty much FileManager/SourceManager provides already.

clangd/SourceCode.h

58

I removed this one.

60

removed

clangd/index/SymbolCollector.cpp

320

The assert was just moved from splitQualifiedName but I can remove the message and move it.

clangd/tool/ClangdMain.cpp

105

(I'm curious why just restarting clangd when the compilation database is overridden doesn't work).

Restarting Clangd would mean that the client has the burden to know that it has to restart Clangd and "reopen" all the files, which I don't think is specified in the LSP. I think the client would be free to just not restart a "crashed" server. VSCode does restart a crashing server (up to 5 times?) but that's arbitrary I think.
We also want to soon look at handling the CDB changing through the "workspace/didChangeWatchedFiles" and track which flags for which files actually changes, which means some files would be reparsed and others not.

unittests/clangd/FindSymbolsTests.cpp

48

I needed to set ServerOpts.BuildDynamicSymbolIndex = true; before creating the ClangServer. But I extracted this to a test-file-specific optsForTest() and used that instead. Much nicer.

246

My reasoning was that this was also making sure that getWorkspaceSymbols worked for those cases, regardless of how it was implemented, i.e., being dependent on SymbolCollector. It would be possible that getWorkspaceSymbols breaks one of these cases, although unlikely given its *current* implementation. I think a good blend of tests is both some tests that take into consideration the implementation and also tests that do not consider the implementation but rather expected functionality. I guess in that sense, I was trying to add a bit more black box testing of functionality.

[malaperle]

clangd/ClangdLSPServer.cpp

109

I'd like to add some test to exercise the changes in ClangdLSPServer.cpp and Protocol.cpp but it's not straightforward to do nicely. Using a "lit" test, I cannot have a header and since symbols in the main file are not collected then it's not useful. If I make a gtest, I have to feed it the lsp server with stdin and check the stdout which is a bit messy, but doable.

[sammccall]

Sorry about the delay Marc-André - I got stuck on "how to test ClangdLSPServer" and then distracted!
But this looks great.

clangd/ClangdLSPServer.cpp

109

Yeah, we don't have a good way to test ClangdLSPServer :-( I would like to fix that, but I don't know of any easy fixes.

This is kind of gross, but do standard library includes work from our lit tests? You could #include <map> and then test using some symbols you know are there...

111

I'd like to be slightly less hostile than this to (broken) clients that fail to call initialize.
As the patch stands they'll get an empty SupportedSymbolKinds, and we'll crash if they call documentSymbols.

Instead I'd suggest pulling out defaultSymbolKinds() and initializing to that in the constructor, and then overriding with either SpecifiedSymbolKinds or SpecifiedSymbolKinds | defaultSymbolKinds() here.

clangd/ClangdServer.h

162

I think it would probably be more consistent with other functions to just take int limit here. I'm not sure CodeCompletion is an example we want to emulate.

ClangdLSPServer might even just grab it from the code completion options, since that's the behavior we actually want.

Up to you, though.

163

maybe a short FIXME here too e.g. "remove param when the index has line/col"

clangd/FindSymbols.cpp

43

Ah yes I agree, fallbacks are good. I just meant that ClangdLSPServer should ensure that we actually have the bitset populated with the right values. I think it looks good now.

clangd/Protocol.cpp

209

This doesn't actually seem unreachable (or won't stay that way), maybe log and return Null or something like that? (Wow, there's really no catch-all option for this mandatory enum...)

[sammccall]

(BTW @hokein has D45513 to add row/col to the index, which will allow all the file-reading stuff to be cleaned up, but no need to wait on that since it's all working now).

[malaperle]

Address comments.

[malaperle]

In D44882#1064196, @sammccall wrote:

(BTW @hokein has D45513 to add row/col to the index, which will allow all the file-reading stuff to be cleaned up, but no need to wait on that since it's all working now).

Looking forward to it!

clangd/ClangdLSPServer.cpp

109

It doesn't seem to work unfortunately. I'm not sure why yet. Either way, I think I would add this test as a separate patch if we are to add a standard library include because I'm a bit nervous it will break and we will have to revert it :)

111

Good catch. I initialized SupportedSymbolKinds with defaultSymbolKinds() and let this loop add additional symbol kinds.

clangd/ClangdServer.h

162

I think it makes sense. We can reintroduce an option struct when there is more than one thing in it.

clangd/Protocol.cpp

209

Null Is not in LSP 1.0 and 2.0 that's why I had put Variable at the beginning. Maybe String is better. Not sure what you think is best.

[sammccall]

Still LG, thanks!
I'll look into the testing issue.

clangd/ClangdLSPServer.cpp

113

nit: the bounds checks at usage types, with explicit underlying type for the enum are inconsistent with what we do in other protocol enums, and seem to clutter the code.

All else equal, I'd prefer to have an enum/enum class with implicit type, and not have values that are out of the enum's range. It's a simpler model that matches the code we have, and doesn't need tricky casts to SymKindUnderlyingType. If we want to support clients that send higher numbers than we know about, we could either:

• overload fromJSON(vector<SymbolKind>)&
• just express the capabilities as vector<int> and convert them to the enum (and check bounds) at this point.

WDYT?

clangd/FindSymbols.h

27

Would be nice to have a comment describing: query syntax, limit=0 special behavior.

[malaperle]

In D44882#1065622, @sammccall wrote:

Still LG, thanks!
I'll look into the testing issue.

I thought about it after... I think it was because I was trying to test with std::unordered_map (to prevent multiple results) which needs std=c++11, I'll try with something else.

[sammccall]

In D44882#1065631, @malaperle wrote:

In D44882#1065622, @sammccall wrote:

Still LG, thanks!
I'll look into the testing issue.

I thought about it after... I think it was because I was trying to test with std::unordered_map (to prevent multiple results) which needs std=c++11, I'll try with something else.

Worth a shot, but don't count on it - for c++ clang switched to using std=c++11 by default a while ago.

[hokein]

@malaperle, what's your plan of this patch? Are you going to land it before D45513? With the Line&Column info in the index, this patch could be simplified.

[malaperle]

In D44882#1065787, @hokein wrote:

@malaperle, what's your plan of this patch? Are you going to land it before D45513? With the Line&Column info in the index, this patch could be simplified.

I'll address the last comment and wait for review. Probably at least another day of delay. So if that ends up after D45513 then I'll update it to simplify. Sounds good?

[malaperle]

In D44882#1065632, @sammccall wrote:

In D44882#1065631, @malaperle wrote:

In D44882#1065622, @sammccall wrote:

Still LG, thanks!
I'll look into the testing issue.

I thought about it after... I think it was because I was trying to test with std::unordered_map (to prevent multiple results) which needs std=c++11, I'll try with something else.

Worth a shot, but don't count on it - for c++ clang switched to using std=c++11 by default a while ago.

I just tried "std::basic_ostringstream" and that works. Seems safer.

[malaperle]

Address comments.

[malaperle]

clangd/ClangdLSPServer.cpp

113

I think it's better to keep vector<SymbolKind> in Protocol.h, it is clearer and more in line with the protocol. I overloaded fromJSON, which simplifies the code here, but it still needs a static_cast to size_t for the bitset.set(). Other places there still needs a static_cast, like in defaultSymbolKinds for the loop, I can static_cast to size_t everywhere (or int?) but having SymKindUnderlyingType seems more correct. I changed it to size_t, let me know if it was something like that you had in mind.

[hokein]

In D44882#1065932, @malaperle wrote:

In D44882#1065787, @hokein wrote:

@malaperle, what's your plan of this patch? Are you going to land it before D45513? With the Line&Column info in the index, this patch could be simplified.

I'll address the last comment and wait for review. Probably at least another day of delay. So if that ends up after D45513 then I'll update it to simplify. Sounds good?

Thanks, I have landed the patch today, you need to update your patch (I think it is mostly about removing the code of reading-file stuff).

[sammccall]

Still LG

clangd/ClangdLSPServer.cpp

113

LG, though I've commented in one place where the cast seems necessary.

Personally I usually use int here, but size_t is good too. The exact type doesn't matter as long as it covers all values of the enum.

274

you no longer need the min/max asserts and their casts, because we don't allow any values of type SymbolKind that don't have one of the enum values (i.e. we're just echoing the type system here)

[malaperle]

Address comments. Simplify with using line/col from index.

[malaperle]

In D44882#1066883, @hokein wrote:

Thanks, I have landed the patch today, you need to update your patch (I think it is mostly about removing the code of reading-file stuff).

I updated the patch using the new line/col from the index. This is great!

[malaperle]

Any objections to the latest version?

[sammccall]

Sorry, missed this.
Just a few leftovers from removing the line/col conversion code.
Then ship it!

clangd/ClangdServer.h

164

DraftStore is now unused and can be dropped :-)
(also the forward decl of it)

clangd/FindSymbols.cpp

12

dead include

clangd/FindSymbols.h

14

nit: header guards no longer match filename

25

dead forward decl (and the VirtualFileSystem and IntrusiveRefCntPtr includes)

[hokein]

clangd/FindSymbols.cpp

118

The current URI scheme (file, test) works fine without HintPath because they don't use it, but for some custom URI schemes, they might rely on the HintPath(e.g. the path of current main file) to resolve the absolute path correctly. Maybe add a FIXME here?

[malaperle]

Address comments.

[malaperle]

Sorry for the embarrassing clean-ups I forgot!

[malaperle]

Remove more includes.

[sammccall]

In D44882#1066743, @malaperle wrote:

In D44882#1065632, @sammccall wrote:

In D44882#1065631, @malaperle wrote:

In D44882#1065622, @sammccall wrote:

Still LG, thanks!
I'll look into the testing issue.

I thought about it after... I think it was because I was trying to test with std::unordered_map (to prevent multiple results) which needs std=c++11, I'll try with something else.

Worth a shot, but don't count on it - for c++ clang switched to using std=c++11 by default a while ago.

I just tried "std::basic_ostringstream" and that works. Seems safer.

So this fails if there's no standard library available without flags, which is the case in google's test environment to ensure hermeticity :-(

In the short-term, we've disabled the test internally - did it trigger any buildbot failures?
In the medium term we should probably find a better way to test this :(

[malaperle]

In D44882#1076864, @sammccall wrote:

So this fails if there's no standard library available without flags, which is the case in google's test environment to ensure hermeticity :-(

In the short-term, we've disabled the test internally - did it trigger any buildbot failures?
In the medium term we should probably find a better way to test this :(

No buildbot failures yet. But I suggest we just remove the test and add it back when we collect more symbols, i.e. in main files. WDYT?

[sammccall]

In D44882#1076927, @malaperle wrote:

In D44882#1076864, @sammccall wrote:

So this fails if there's no standard library available without flags, which is the case in google's test environment to ensure hermeticity :-(

In the short-term, we've disabled the test internally - did it trigger any buildbot failures?
In the medium term we should probably find a better way to test this :(

No buildbot failures yet. But I suggest we just remove the test and add it back when we collect more symbols, i.e. in main files. WDYT?

It makes sense, but @bkramer came up with some deep magic in rL330754 so I think we're actually good now.

[malaperle]

In D44882#1077516, @sammccall wrote:

It makes sense, but @bkramer came up with some deep magic in rL330754 so I think we're actually good now.

Nice! Thanks @bkramer !

clangd/CMakeLists.txt

add_clang_library(clangDaemon
   ClangdUnit.cpp
   CodeComplete.cpp
   CodeCompletionStrings.cpp
   CompileArgsCache.cpp
   Compiler.cpp
   Context.cpp
   Diagnostics.cpp
   DraftStore.cpp
+  FindSymbols.cpp
   FuzzyMatch.cpp
   GlobalCompilationDatabase.cpp
   Headers.cpp
   JSONExpr.cpp
   JSONRPCDispatcher.cpp
   Logger.cpp
   Protocol.cpp
   ProtocolHandlers.cpp

clangd/ClangdLSPServer.h

 //===--- ClangdLSPServer.h - LSP server --------------------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===---------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_CLANGDLSPSERVER_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_CLANGDLSPSERVER_H
 
 #include "ClangdServer.h"
 #include "DraftStore.h"
+#include "FindSymbols.h"
 #include "GlobalCompilationDatabase.h"
 #include "Path.h"
 #include "Protocol.h"
 #include "ProtocolHandlers.h"
 #include "clang/Tooling/Core/Replacement.h"
 #include "llvm/ADT/Optional.h"
 
 namespace clang {
private:
   void onCodeAction(CodeActionParams &Params) override;
   void onCompletion(TextDocumentPositionParams &Params) override;
   void onSignatureHelp(TextDocumentPositionParams &Params) override;
   void onGoToDefinition(TextDocumentPositionParams &Params) override;
   void onSwitchSourceHeader(TextDocumentIdentifier &Params) override;
   void onDocumentHighlight(TextDocumentPositionParams &Params) override;
   void onFileEvent(DidChangeWatchedFilesParams &Params) override;
   void onCommand(ExecuteCommandParams &Params) override;
+  void onWorkspaceSymbol(WorkspaceSymbolParams &Params) override;
   void onRename(RenameParams &Parames) override;
   void onHover(TextDocumentPositionParams &Params) override;
   void onChangeConfiguration(DidChangeConfigurationParams &Params) override;
 
   std::vector<Fix> getFixes(StringRef File, const clangd::Diagnostic &D);
 
   /// Forces a reparse of all currently opened files.  As a result, this method
   /// may be very expensive.  This method is normally called when the
   /// compilation database is changed.
   void reparseOpenedFiles();
 
   JSONOutput &Out;
   /// Used to indicate that the 'shutdown' request was received from the
   /// Language Server client.
   bool ShutdownRequestReceived = false;
 
   /// Used to indicate that the 'exit' notification was received from the
   /// Language Server client.
   /// It's used to break out of the LSP parsing loop.
   bool IsDone = false;
 
   std::mutex FixItsMutex;
   typedef std::map<clangd::Diagnostic, std::vector<Fix>, LSPDiagnosticCompare>
       DiagnosticToReplacementMap;
   /// Caches FixIts per file and diagnostics
   llvm::StringMap<DiagnosticToReplacementMap> FixItsMap;
 
   // Various ClangdServer parameters go here. It's important they're created
   // before ClangdServer.
   DirectoryBasedGlobalCompilationDatabase CDB;
   RealFileSystemProvider FSProvider;
   /// Options used for code completion
   clangd::CodeCompleteOptions CCOpts;
+  /// The supported kinds of the client.
+  SymbolKindBitset SupportedSymbolKinds;
 
   // Store of the current versions of the open documents.
   DraftStore DraftMgr;
 
   // Server must be the last member of the class to allow its destructor to exit
   // the worker thread that may otherwise run an async callback on partially
   // destructed instance of ClangdLSPServer.
   ClangdServer Server;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif

clangd/ClangdLSPServer.cpp

 std::vector<TextEdit> replacementsToEdits(StringRef Code,
                                           const tooling::Replacements &Repls) {
   std::vector<TextEdit> Edits;
   for (const auto &R : Repls)
     Edits.push_back(replacementToEdit(Code, R));
   return Edits;
 }
 
+SymbolKindBitset defaultSymbolKinds() {
+  SymbolKindBitset Defaults;
+  for (size_t I = SymbolKindMin; I <= static_cast<size_t>(SymbolKind::Array);
+       ++I)
+    Defaults.set(I);
+  return Defaults;
+}
+
 } // namespace
 
 void ClangdLSPServer::onInitialize(InitializeParams &Params) {
   if (Params.rootUri && *Params.rootUri)
     Server.setRootPath(Params.rootUri->file());
   else if (Params.rootPath && !Params.rootPath->empty())
     Server.setRootPath(*Params.rootPath);
 
   CCOpts.EnableSnippets =
       Params.capabilities.textDocument.completion.completionItem.snippetSupport;
 
+  if (Params.capabilities.workspace && Params.capabilities.workspace->symbol &&
+      Params.capabilities.workspace->symbol->symbolKind) {
+    for (SymbolKind Kind :
+         *Params.capabilities.workspace->symbol->symbolKind->valueSet) {
+      SupportedSymbolKinds.set(static_cast<size_t>(Kind));
+    }
+  }
+
   reply(json::obj{
       {{"capabilities",
         json::obj{
             {"textDocumentSync", (int)TextDocumentSyncKind::Incremental},
             {"documentFormattingProvider", true},
             {"documentRangeFormattingProvider", true},
             {"documentOnTypeFormattingProvider",
              json::obj{
reply(json::obj{
             {"signatureHelpProvider",
              json::obj{
                  {"triggerCharacters", {"(", ","}},
              }},
             {"definitionProvider", true},
             {"documentHighlightProvider", true},
             {"hoverProvider", true},
             {"renameProvider", true},
+            {"workspaceSymbolProvider", true},
             {"executeCommandProvider",
              json::obj{
                  {"commands",
                   {ExecuteCommandParams::CLANGD_APPLY_FIX_COMMAND,
                    ExecuteCommandParams::CLANGD_INSERT_HEADER_INCLUDE}},
              }},
         }}}});
 }
if (Params.command == ExecuteCommandParams::CLANGD_APPLY_FIX_COMMAND &&
     // parsed in the first place and this handler should not be called. But if
     // more commands are added, this will be here has a safe guard.
     replyError(
         ErrorCode::InvalidParams,
         llvm::formatv("Unsupported command \"{0}\".", Params.command).str());
   }
 }
 
+void ClangdLSPServer::onWorkspaceSymbol(WorkspaceSymbolParams &Params) {
+  Server.workspaceSymbols(
+      Params.query, CCOpts.Limit,
+      [this](llvm::Expected<std::vector<SymbolInformation>> Items) {
+        if (!Items)
+          return replyError(ErrorCode::InternalError,
+                            llvm::toString(Items.takeError()));
+        for (auto &Sym : *Items)
+          Sym.kind = adjustKindToCapability(Sym.kind, SupportedSymbolKinds);
+
+        reply(json::ary(*Items));
+      });
+}
+
 void ClangdLSPServer::onRename(RenameParams &Params) {
   Path File = Params.textDocument.uri.file();
   llvm::Optional<std::string> Code = DraftMgr.getDraft(File);
   if (!Code)
     return replyError(ErrorCode::InvalidParams,
                       "onRename called for non-added file");
 
   Server.rename(
void ClangdLSPServer::onChangeConfiguration(
   }
 }
 
 ClangdLSPServer::ClangdLSPServer(JSONOutput &Out,
                                  const clangd::CodeCompleteOptions &CCOpts,
                                  llvm::Optional<Path> CompileCommandsDir,
                                  const ClangdServer::Options &Opts)
     : Out(Out), CDB(std::move(CompileCommandsDir)), CCOpts(CCOpts),
+      SupportedSymbolKinds(defaultSymbolKinds()),
       Server(CDB, FSProvider, /*DiagConsumer=*/*this, Opts) {}
 
 bool ClangdLSPServer::run(std::istream &In, JSONStreamStyle InputStyle) {
   assert(!IsDone && "Run was called before");
 
   // Set up JSONRPCDispatcher.
   JSONRPCDispatcher Dispatcher([](const json::Expr &Params) {
     replyError(ErrorCode::MethodNotFound, "method not found");

clangd/ClangdServer.h

public:
 
   /// Get document highlights for a given position.
   void findDocumentHighlights(PathRef File, Position Pos,
                               Callback<std::vector<DocumentHighlight>> CB);
 
   /// Get code hover for a given position.
   void findHover(PathRef File, Position Pos, Callback<Hover> CB);
 
+  /// Retrieve the top symbols from the workspace matching a query.
+  void workspaceSymbols(StringRef Query, int Limit,
+                        Callback<std::vector<SymbolInformation>> CB);
+
   /// Run formatting for \p Rng inside \p File with content \p Code.
   llvm::Expected<tooling::Replacements> formatRange(StringRef Code,
                                                     PathRef File, Range Rng);
 
   /// Run formatting for the whole \p File with content \p Code.
   llvm::Expected<tooling::Replacements> formatFile(StringRef Code,
                                                    PathRef File);
 
   /// Run formatting after a character was typed at \p Pos in \p File with

clangd/ClangdServer.cpp

 //===--- ClangdServer.cpp - Main clangd server code --------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===-------------------------------------------------------------------===//
 
 #include "ClangdServer.h"
 #include "CodeComplete.h"
+#include "FindSymbols.h"
 #include "Headers.h"
 #include "SourceCode.h"
 #include "XRefs.h"
 #include "index/Merge.h"
 #include "clang/Format/Format.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Tooling/CompilationDatabase.h"
void ClangdServer::consumeDiagnostics(PathRef File, DocVersion Version,
   DiagConsumer.onDiagnosticsReady(File, std::move(Diags));
 }
 
 void ClangdServer::onFileEvent(const DidChangeWatchedFilesParams &Params) {
   // FIXME: Do nothing for now. This will be used for indexing and potentially
   // invalidating other caches.
 }
 
+void ClangdServer::workspaceSymbols(
+    StringRef Query, int Limit, Callback<std::vector<SymbolInformation>> CB) {
+  CB(clangd::getWorkspaceSymbols(Query, Limit, Index));
+}
+
 std::vector<std::pair<Path, std::size_t>>
 ClangdServer::getUsedBytesPerFile() const {
   return WorkScheduler.getUsedBytesPerFile();
 }
 
 LLVM_NODISCARD bool
 ClangdServer::blockUntilIdleForTest(llvm::Optional<double> TimeoutSeconds) {
   return WorkScheduler.blockUntilIdle(timeoutSeconds(TimeoutSeconds));
 }

clangd/FindSymbols.h

+//===--- FindSymbols.h --------------------------------------*- C++-*------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Queries that provide a list of symbols matching a string.
+//
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_FINDSYMBOLS_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_FINDSYMBOLS_H
+
+#include "Protocol.h"
+#include "llvm/ADT/StringRef.h"
+
+namespace clang {
+namespace clangd {
+class SymbolIndex;
+
+/// Searches for the symbols matching \p Query. The syntax of \p Query can be
+/// the non-qualified name or fully qualified of a symbol. For example, "vector"
+/// will match the symbol std::vector and "std::vector" would also match it.
+/// Direct children of scopes (namepaces, etc) can be listed with a trailing
+/// "::". For example, "std::" will list all children of the std namespace and
+/// "::" alone will list all children of the global namespace.
+/// \p Limit limits the number of results returned (0 means no limit).
+llvm::Expected<std::vector<SymbolInformation>>
+getWorkspaceSymbols(llvm::StringRef Query, int Limit,
+                    const SymbolIndex *const Index);
+
+} // namespace clangd
+} // namespace clang
+
+#endif

clangd/FindSymbols.cpp

+//===--- FindSymbols.cpp ------------------------------------*- C++-*------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+#include "FindSymbols.h"
+
+#include "Logger.h"
+#include "SourceCode.h"
+#include "index/Index.h"
+#include "clang/Index/IndexSymbol.h"
+#include "llvm/Support/FormatVariadic.h"
+#include "llvm/Support/Path.h"
+
+namespace clang {
+namespace clangd {
+
+namespace {
+
+// Convert a index::SymbolKind to clangd::SymbolKind (LSP)
+// Note, some are not perfect matches and should be improved when this LSP
+// issue is addressed:
+// https://github.com/Microsoft/language-server-protocol/issues/344
+SymbolKind indexSymbolKindToSymbolKind(index::SymbolKind Kind) {
+  switch (Kind) {
+  case index::SymbolKind::Unknown:
+    return SymbolKind::Variable;
+  case index::SymbolKind::Module:
+    return SymbolKind::Module;
+  case index::SymbolKind::Namespace:
+    return SymbolKind::Namespace;
+  case index::SymbolKind::NamespaceAlias:
+    return SymbolKind::Namespace;
+  case index::SymbolKind::Macro:
+    return SymbolKind::String;
+  case index::SymbolKind::Enum:
+    return SymbolKind::Enum;
+  case index::SymbolKind::Struct:
+    return SymbolKind::Struct;
+  case index::SymbolKind::Class:
+    return SymbolKind::Class;
+  case index::SymbolKind::Protocol:
+    return SymbolKind::Interface;
+  case index::SymbolKind::Extension:
+    return SymbolKind::Interface;
+  case index::SymbolKind::Union:
+    return SymbolKind::Class;
+  case index::SymbolKind::TypeAlias:
+    return SymbolKind::Class;
+  case index::SymbolKind::Function:
+    return SymbolKind::Function;
+  case index::SymbolKind::Variable:
+    return SymbolKind::Variable;
+  case index::SymbolKind::Field:
+    return SymbolKind::Field;
+  case index::SymbolKind::EnumConstant:
+    return SymbolKind::EnumMember;
+  case index::SymbolKind::InstanceMethod:
+  case index::SymbolKind::ClassMethod:
+  case index::SymbolKind::StaticMethod:
+    return SymbolKind::Method;
+  case index::SymbolKind::InstanceProperty:
+  case index::SymbolKind::ClassProperty:
+  case index::SymbolKind::StaticProperty:
+    return SymbolKind::Property;
+  case index::SymbolKind::Constructor:
+  case index::SymbolKind::Destructor:
+    return SymbolKind::Method;
+  case index::SymbolKind::ConversionFunction:
+    return SymbolKind::Function;
+  case index::SymbolKind::Parameter:
+    return SymbolKind::Variable;
+  case index::SymbolKind::Using:
+    return SymbolKind::Namespace;
+  }
+  llvm_unreachable("invalid symbol kind");
+}
+
+} // namespace
+
+llvm::Expected<std::vector<SymbolInformation>>
+getWorkspaceSymbols(StringRef Query, int Limit,
+                    const SymbolIndex *const Index) {
+  std::vector<SymbolInformation> Result;
+  if (Query.empty() || !Index)
+    return Result;
+
+  auto Names = splitQualifiedName(Query);
+
+  FuzzyFindRequest Req;
+  Req.Query = Names.second;
+
+  // FuzzyFind doesn't want leading :: qualifier
+  bool IsGlobalQuery = Names.first.consume_front("::");
+  // Restrict results to the scope in the query string if present (global or
+  // not).
+  if (IsGlobalQuery || !Names.first.empty())
+    Req.Scopes = {Names.first};
+  if (Limit)
+    Req.MaxCandidateCount = Limit;
+  Index->fuzzyFind(Req, [&Result](const Symbol &Sym) {
+    // Prefer the definition over e.g. a function declaration in a header
+    auto &CD = Sym.Definition ? Sym.Definition : Sym.CanonicalDeclaration;
+    auto Uri = URI::parse(CD.FileURI);
+    if (!Uri) {
+      log(llvm::formatv(
+          "Workspace symbol: Could not parse URI '{0}' for symbol '{1}'.",
+          CD.FileURI, Sym.Name));
+      return;
+    }
+    // FIXME: Passing no HintPath here will work for "file" and "test" schemes
+    // because they don't use it but this might not work for other custom ones.
+    auto Path = URI::resolve(*Uri);
+    if (!Path) {
+      log(llvm::formatv("Workspace symbol: Could not resolve path for URI "
+                        "'{0}' for symbol '{1}'.",
+                        (*Uri).toString(), Sym.Name.str()));
+      return;
+    }
+    Location L;
+    L.uri = URIForFile((*Path));
+    Position Start, End;
+    Start.line = CD.Start.Line;
+    Start.character = CD.Start.Column;
+    End.line = CD.End.Line;
+    End.character = CD.End.Column;
+    L.range = {Start, End};
+    SymbolKind SK = indexSymbolKindToSymbolKind(Sym.SymInfo.Kind);
+    std::string Scope = Sym.Scope;
+    StringRef ScopeRef = Scope;
+    ScopeRef.consume_back("::");
+    Result.push_back({Sym.Name, SK, L, ScopeRef});
+  });
+  return Result;
+}
+
+} // namespace clangd
+} // namespace clang

clangd/Protocol.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_PROTOCOL_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_PROTOCOL_H
 
 #include "JSONExpr.h"
 #include "URI.h"
 #include "llvm/ADT/Optional.h"
+#include <bitset>
 #include <string>
 #include <vector>
 
 namespace clang {
 namespace clangd {
 
 enum class ErrorCode {
   // Defined by JSON RPC.
struct CompletionClientCapabilities {
   // llvm::Optional<CompletionItemKindCapabilities> completionItemKind;
 
   /// The client supports to send additional context information for a
   /// `textDocument/completion` request.
   bool contextSupport = false;
 };
 bool fromJSON(const json::Expr &, CompletionClientCapabilities &);
 
+/// A symbol kind.
+enum class SymbolKind {
+  File = 1,
+  Module = 2,
+  Namespace = 3,
+  Package = 4,
+  Class = 5,
+  Method = 6,
+  Property = 7,
+  Field = 8,
+  Constructor = 9,
+  Enum = 10,
+  Interface = 11,
+  Function = 12,
+  Variable = 13,
+  Constant = 14,
+  String = 15,
+  Number = 16,
+  Boolean = 17,
+  Array = 18,
+  Object = 19,
+  Key = 20,
+  Null = 21,
+  EnumMember = 22,
+  Struct = 23,
+  Event = 24,
+  Operator = 25,
+  TypeParameter = 26
+};
+
+constexpr auto SymbolKindMin = static_cast<size_t>(SymbolKind::File);
+constexpr auto SymbolKindMax = static_cast<size_t>(SymbolKind::TypeParameter);
+using SymbolKindBitset = std::bitset<SymbolKindMax + 1>;
+
+bool fromJSON(const json::Expr &, SymbolKind &);
+
+struct SymbolKindCapabilities {
+  /// The SymbolKinds that the client supports. If not set, the client only
+  /// supports <= SymbolKind::Array and will not fall back to a valid default
+  /// value.
+  llvm::Optional<std::vector<SymbolKind>> valueSet;
+};
+bool fromJSON(const json::Expr &, std::vector<SymbolKind> &);
+bool fromJSON(const json::Expr &, SymbolKindCapabilities &);
+SymbolKind adjustKindToCapability(SymbolKind Kind,
+                                  SymbolKindBitset &supportedSymbolKinds);
+
+struct WorkspaceSymbolCapabilities {
+  /// Capabilities SymbolKind.
+  llvm::Optional<SymbolKindCapabilities> symbolKind;
+};
+bool fromJSON(const json::Expr &, WorkspaceSymbolCapabilities &);
+
+// FIXME: most of the capabilities are missing from this struct. Only the ones
+// used by clangd are currently there.
+struct WorkspaceClientCapabilities {
+  /// Capabilities specific to `workspace/symbol`.
+  llvm::Optional<WorkspaceSymbolCapabilities> symbol;
+};
+bool fromJSON(const json::Expr &, WorkspaceClientCapabilities &);
+
 // FIXME: most of the capabilities are missing from this struct. Only the ones
 // used by clangd are currently there.
 struct TextDocumentClientCapabilities {
   /// Capabilities specific to the `textDocument/completion`
   CompletionClientCapabilities completion;
 };
 bool fromJSON(const json::Expr &, TextDocumentClientCapabilities &);
 
 struct ClientCapabilities {
   // Workspace specific client capabilities.
-  // NOTE: not used by clangd at the moment.
-  // WorkspaceClientCapabilities workspace;
+  llvm::Optional<WorkspaceClientCapabilities> workspace;
 
   // Text document specific client capabilities.
   TextDocumentClientCapabilities textDocument;
 };
 
 bool fromJSON(const json::Expr &, ClientCapabilities &);
 
 struct InitializeParams {

 bool fromJSON(const json::Expr &, ExecuteCommandParams &);
 
 struct Command : public ExecuteCommandParams {
   std::string title;
 };
 
 json::Expr toJSON(const Command &C);
 
+/// Represents information about programming constructs like variables, classes,
+/// interfaces etc.
+struct SymbolInformation {
+  /// The name of this symbol.
+  std::string name;
+
+  /// The kind of this symbol.
+  SymbolKind kind;
+
+  /// The location of this symbol.
+  Location location;
+
+  /// The name of the symbol containing this symbol.
+  std::string containerName;
+};
+json::Expr toJSON(const SymbolInformation &);
+llvm::raw_ostream &operator<<(llvm::raw_ostream &, const SymbolInformation &);
+
+/// The parameters of a Workspace Symbol Request.
+struct WorkspaceSymbolParams {
+  /// A non-empty query string
+  std::string query;
+};
+bool fromJSON(const json::Expr &, WorkspaceSymbolParams &);
+
 struct ApplyWorkspaceEditParams {
   WorkspaceEdit edit;
 };
 json::Expr toJSON(const ApplyWorkspaceEditParams &);
 
 struct TextDocumentPositionParams {
   /// The text document.
   TextDocumentIdentifier textDocument;

clangd/Protocol.cpp

bool fromJSON(const json::Expr &Params, CompletionClientCapabilities &R) {
   if (!O)
     return false;
   O.map("dynamicRegistration", R.dynamicRegistration);
   O.map("completionItem", R.completionItem);
   O.map("contextSupport", R.contextSupport);
   return true;
 }
 
+bool fromJSON(const json::Expr &E, SymbolKind &Out) {
+  if (auto T = E.asInteger()) {
+    if (*T < static_cast<int>(SymbolKind::File) ||
+        *T > static_cast<int>(SymbolKind::TypeParameter))
+      return false;
+    Out = static_cast<SymbolKind>(*T);
+    return true;
+  }
+  return false;
+}
+
+bool fromJSON(const json::Expr &E, std::vector<SymbolKind> &Out) {
+  if (auto *A = E.asArray()) {
+    Out.clear();
+    for (size_t I = 0; I < A->size(); ++I) {
+      SymbolKind KindOut;
+      if (fromJSON((*A)[I], KindOut))
+        Out.push_back(KindOut);
+    }
+    return true;
+  }
+  return false;
+}
+
+bool fromJSON(const json::Expr &Params, SymbolKindCapabilities &R) {
+  json::ObjectMapper O(Params);
+  return O && O.map("valueSet", R.valueSet);
+}
+
+SymbolKind adjustKindToCapability(SymbolKind Kind,
+                                  SymbolKindBitset &supportedSymbolKinds) {
+  auto KindVal = static_cast<size_t>(Kind);
+  if (KindVal >= SymbolKindMin && KindVal <= supportedSymbolKinds.size() &&
+      supportedSymbolKinds[KindVal])
+    return Kind;
+
+  switch (Kind) {
+  // Provide some fall backs for common kinds that are close enough.
+  case SymbolKind::Struct:
+    return SymbolKind::Class;
+  case SymbolKind::EnumMember:
+    return SymbolKind::Enum;
+  default:
+    return SymbolKind::String;
+  }
+}
+
+bool fromJSON(const json::Expr &Params, WorkspaceSymbolCapabilities &R) {
+  json::ObjectMapper O(Params);
+  return O && O.map("symbolKind", R.symbolKind);
+}
+
+bool fromJSON(const json::Expr &Params, WorkspaceClientCapabilities &R) {
+  json::ObjectMapper O(Params);
+  return O && O.map("symbol", R.symbol);
+}
+
 bool fromJSON(const json::Expr &Params, TextDocumentClientCapabilities &R) {
   json::ObjectMapper O(Params);
   if (!O)
     return false;
   O.map("completion", R.completion);
   return true;
 }
 
 bool fromJSON(const json::Expr &Params, ClientCapabilities &R) {
   json::ObjectMapper O(Params);
   if (!O)
     return false;
   O.map("textDocument", R.textDocument);
+  O.map("workspace", R.workspace);
   return true;
 }
 
 bool fromJSON(const json::Expr &Params, InitializeParams &R) {
   json::ObjectMapper O(Params);
   if (!O)
     return false;
   // We deliberately don't fail if we can't parse individual fields.
return Args && Args->size() == 1 &&
            fromJSON(Args->front(), R.workspaceEdit);
   } else if (R.command == ExecuteCommandParams::CLANGD_INSERT_HEADER_INCLUDE) {
     return Args && Args->size() == 1 &&
            fromJSON(Args->front(), R.includeInsertion);
   }
   return false; // Unrecognized command.
 }
 
+json::Expr toJSON(const SymbolInformation &P) {
+  return json::obj{
+      {"name", P.name},
+      {"kind", static_cast<int>(P.kind)},
+      {"location", P.location},
+      {"containerName", P.containerName},
+  };
+}
+
+llvm::raw_ostream &operator<<(llvm::raw_ostream &O,
+                              const SymbolInformation &SI) {
+  O << SI.containerName << "::" << SI.name << " - " << toJSON(SI);
+  return O;
+}
+
+bool fromJSON(const json::Expr &Params, WorkspaceSymbolParams &R) {
+  json::ObjectMapper O(Params);
+  return O && O.map("query", R.query);
+}
+
 json::Expr toJSON(const Command &C) {
   auto Cmd = json::obj{{"title", C.title}, {"command", C.command}};
   if (C.workspaceEdit)
     Cmd["arguments"] = {*C.workspaceEdit};
   else if (C.includeInsertion)
     Cmd["arguments"] = {*C.includeInsertion};
   return std::move(Cmd);
 }

clangd/ProtocolHandlers.h

public:
   onDocumentRangeFormatting(DocumentRangeFormattingParams &Params) = 0;
   virtual void onCodeAction(CodeActionParams &Params) = 0;
   virtual void onCompletion(TextDocumentPositionParams &Params) = 0;
   virtual void onSignatureHelp(TextDocumentPositionParams &Params) = 0;
   virtual void onGoToDefinition(TextDocumentPositionParams &Params) = 0;
   virtual void onSwitchSourceHeader(TextDocumentIdentifier &Params) = 0;
   virtual void onFileEvent(DidChangeWatchedFilesParams &Params) = 0;
   virtual void onCommand(ExecuteCommandParams &Params) = 0;
+  virtual void onWorkspaceSymbol(WorkspaceSymbolParams &Params) = 0;
   virtual void onRename(RenameParams &Parames) = 0;
   virtual void onDocumentHighlight(TextDocumentPositionParams &Params) = 0;
   virtual void onHover(TextDocumentPositionParams &Params) = 0;
   virtual void onChangeConfiguration(DidChangeConfigurationParams &Params) = 0;
 };
 
 void registerCallbackHandlers(JSONRPCDispatcher &Dispatcher,
                               ProtocolCallbacks &Callbacks);
 
 } // namespace clangd
 } // namespace clang
 
 #endif

clangd/ProtocolHandlers.cpp

void clangd::registerCallbackHandlers(JSONRPCDispatcher &Dispatcher,
   Register("textDocument/rename", &ProtocolCallbacks::onRename);
   Register("textDocument/hover", &ProtocolCallbacks::onHover);
   Register("workspace/didChangeWatchedFiles", &ProtocolCallbacks::onFileEvent);
   Register("workspace/executeCommand", &ProtocolCallbacks::onCommand);
   Register("textDocument/documentHighlight",
            &ProtocolCallbacks::onDocumentHighlight);
   Register("workspace/didChangeConfiguration",
            &ProtocolCallbacks::onChangeConfiguration);
+  Register("workspace/symbol", &ProtocolCallbacks::onWorkspaceSymbol);
 }

clangd/SourceCode.h

 /// Turn a SourceLocation into a [line, column] pair.
 /// FIXME: This should return an error if the location is invalid.
 Position sourceLocToPosition(const SourceManager &SM, SourceLocation Loc);
 
 // Converts a half-open clang source range to an LSP range.
 // Note that clang also uses closed source ranges, which this can't handle!
 Range halfOpenToRange(const SourceManager &SM, CharSourceRange R);
 
+/// From "a::b::c", return {"a::b::", "c"}. Scope is empty if there's no
+/// qualifier.
+std::pair<llvm::StringRef, llvm::StringRef>
+splitQualifiedName(llvm::StringRef QName);
+
 } // namespace clangd
 } // namespace clang
 #endif

clangd/SourceCode.cpp

 Range halfOpenToRange(const SourceManager &SM, CharSourceRange R) {
   // Clang is 1-based, LSP uses 0-based indexes.
   Position Begin = sourceLocToPosition(SM, R.getBegin());
   Position End = sourceLocToPosition(SM, R.getEnd());
 
   return {Begin, End};
 }
 
+std::pair<llvm::StringRef, llvm::StringRef>
+splitQualifiedName(llvm::StringRef QName) {
+  size_t Pos = QName.rfind("::");
+  if (Pos == llvm::StringRef::npos)
+    return {StringRef(), QName};
+  return {QName.substr(0, Pos + 2), QName.substr(Pos + 2)};
+}
+
 } // namespace clangd
 } // namespace clang

clangd/index/SymbolCollector.cpp

 //===--- SymbolCollector.cpp -------------------------------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "SymbolCollector.h"
 #include "../AST.h"
 #include "../CodeCompletionStrings.h"
 #include "../Logger.h"
+#include "../SourceCode.h"
 #include "../URI.h"
 #include "CanonicalIncludes.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/DeclTemplate.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Index/IndexSymbol.h"
 #include "clang/Index/USRGeneration.h"
if (U)
       return U->toString();
     ErrMsg += llvm::toString(U.takeError()) + "\n";
   }
   log(llvm::Twine("Failed to create an URI for file ") + AbsolutePath + ": " +
       ErrMsg);
   return llvm::None;
 }
 
-// "a::b::c", return {"a::b::", "c"}. Scope is empty if there's no qualifier.
-std::pair<llvm::StringRef, llvm::StringRef>
-splitQualifiedName(llvm::StringRef QName) {
-  assert(!QName.startswith("::") && "Qualified names should not start with ::");
-  size_t Pos = QName.rfind("::");
-  if (Pos == llvm::StringRef::npos)
-    return {StringRef(), QName};
-  return {QName.substr(0, Pos + 2), QName.substr(Pos + 2)};
-}
-
 bool shouldFilterDecl(const NamedDecl *ND, ASTContext *ASTCtx,
                       const SymbolCollector::Options &Opts) {
   using namespace clang::ast_matchers;
   if (ND->isImplicit())
     return true;
   // Skip anonymous declarations, e.g (anonymous enum/class/struct).
   if (ND->getDeclName().isEmpty())
     return true;
const Symbol *SymbolCollector::addDeclaration(const NamedDecl &ND,
   PrintingPolicy Policy(ASTCtx->getLangOpts());
   // Note that inline namespaces are treated as transparent scopes. This
   // reflects the way they're most commonly used for lookup. Ideally we'd
   // include them, but at query time it's hard to find all the inline
   // namespaces to query: the preamble doesn't have a dedicated list.
   Policy.SuppressUnwrittenScope = true;
   ND.printQualifiedName(OS, Policy);
   OS.flush();
+  assert(!StringRef(QName).startswith("::"));
 
   Symbol S;
   S.ID = std::move(ID);
   std::tie(S.Scope, S.Name) = splitQualifiedName(QName);
   S.SymInfo = index::getSymbolInfo(&ND);
   std::string FileURI;
   if (auto DeclLoc =
           getSymbolLocation(ND, SM, Opts, ASTCtx->getLangOpts(), FileURI))
     S.CanonicalDeclaration = *DeclLoc;
 
   // Add completion info.
   // FIXME: we may want to choose a different redecl, or combine from several.
   assert(ASTCtx && PP.get() && "ASTContext and Preprocessor must be set.");

clangd/tool/ClangdMain.cpp

static llvm::cl::opt<PCHStorageFlag> PCHStorage(
     "pch-storage",
     llvm::cl::desc("Storing PCHs in memory increases memory usages, but may "
                    "improve performance"),
     llvm::cl::values(
         clEnumValN(PCHStorageFlag::Disk, "disk", "store PCHs on disk"),
         clEnumValN(PCHStorageFlag::Memory, "memory", "store PCHs in memory")),
     llvm::cl::init(PCHStorageFlag::Disk));
 
-static llvm::cl::opt<int> LimitCompletionResult(
-    "completion-limit",
-    llvm::cl::desc("Limit the number of completion results returned by clangd. "
+static llvm::cl::opt<int> LimitResults(
+    "limit-results",
+    llvm::cl::desc("Limit the number of results returned by clangd. "
                    "0 means no limit."),
     llvm::cl::init(100));
 
 static llvm::cl::opt<bool> RunSynchronously(
     "run-synchronously",
     llvm::cl::desc("Parse on main thread. If set, -j is ignored"),
     llvm::cl::init(false), llvm::cl::Hidden);
 
 static llvm::cl::opt<Path>
     ResourceDir("resource-dir",
                 llvm::cl::desc("Directory for system clang headers"),
                 llvm::cl::init(""), llvm::cl::Hidden);
 
 static llvm::cl::opt<Path> InputMirrorFile(
     "input-mirror-file",
     llvm::cl::desc(
         "Mirror all LSP input to the specified file. Useful for debugging."),
     llvm::cl::init(""), llvm::cl::Hidden);
 
-static llvm::cl::opt<bool> EnableIndexBasedCompletion(
-    "enable-index-based-completion",
-    llvm::cl::desc(
-        "Enable index-based global code completion. "
+static llvm::cl::opt<bool> EnableIndex(
+    "index",
+    llvm::cl::desc("Enable index-based features such as global code completion "
+                   "and searching for symbols."
                    "Clang uses an index built from symbols in opened files"),
     llvm::cl::init(true));
 
 static llvm::cl::opt<Path> YamlSymbolFile(
     "yaml-symbol-file",
     llvm::cl::desc(
         "YAML-format global symbol file to build the static index. Clangd will "
         "use the static index for global code completion.\n"
         "WARNING: This option is experimental only, and will be removed "
case PCHStorageFlag::Memory:
     Opts.StorePreamblesInMemory = true;
     break;
   case PCHStorageFlag::Disk:
     Opts.StorePreamblesInMemory = false;
     break;
   }
   if (!ResourceDir.empty())
     Opts.ResourceDir = ResourceDir;
-  Opts.BuildDynamicSymbolIndex = EnableIndexBasedCompletion;
+  Opts.BuildDynamicSymbolIndex = EnableIndex;
   std::unique_ptr<SymbolIndex> StaticIdx;
-  if (EnableIndexBasedCompletion && !YamlSymbolFile.empty()) {
+  if (EnableIndex && !YamlSymbolFile.empty()) {
     StaticIdx = BuildStaticIndex(YamlSymbolFile);
     Opts.StaticIndex = StaticIdx.get();
   }
   Opts.AsyncThreadsCount = WorkerThreadsCount;
 
   clangd::CodeCompleteOptions CCOpts;
   CCOpts.IncludeIneligibleResults = IncludeIneligibleResults;
-  CCOpts.Limit = LimitCompletionResult;
+  CCOpts.Limit = LimitResults;
 
   // Initialize and run ClangdLSPServer.
   ClangdLSPServer LSPServer(Out, CCOpts, CompileCommandsDirPath, Opts);
   constexpr int NoShutdownRequestErrorCode = 1;
   llvm::set_thread_name("clangd.main");
   // Change stdin to binary to not lose \r\n on windows.
   llvm::sys::ChangeStdinToBinary();
   return LSPServer.run(std::cin, InputStyle) ? 0 : NoShutdownRequestErrorCode;
 }

test/clangd/initialize-params-invalid.test

 # CHECK-NEXT:      "hoverProvider": true,
 # CHECK-NEXT:      "renameProvider": true,
 # CHECK-NEXT:      "signatureHelpProvider": {
 # CHECK-NEXT:        "triggerCharacters": [
 # CHECK-NEXT:          "(",
 # CHECK-NEXT:          ","
 # CHECK-NEXT:        ]
 # CHECK-NEXT:      },
-# CHECK-NEXT:      "textDocumentSync": 2
+# CHECK-NEXT:      "textDocumentSync": 2,
+# CHECK-NEXT:      "workspaceSymbolProvider": true
 # CHECK-NEXT:    }
 # CHECK-NEXT:  }
 ---
 {"jsonrpc":"2.0","id":3,"method":"shutdown"}
 ---
 {"jsonrpc":"2.0","method":"exit"}

test/clangd/initialize-params.test

 # CHECK-NEXT:      "hoverProvider": true,
 # CHECK-NEXT:      "renameProvider": true,
 # CHECK-NEXT:      "signatureHelpProvider": {
 # CHECK-NEXT:        "triggerCharacters": [
 # CHECK-NEXT:          "(",
 # CHECK-NEXT:          ","
 # CHECK-NEXT:        ]
 # CHECK-NEXT:      },
-# CHECK-NEXT:      "textDocumentSync": 2
+# CHECK-NEXT:      "textDocumentSync": 2,
+# CHECK-NEXT:      "workspaceSymbolProvider": true
 # CHECK-NEXT:    }
 # CHECK-NEXT:  }
 ---
 {"jsonrpc":"2.0","id":3,"method":"shutdown"}
 #      CHECK:  "id": 3,
 # CHECK-NEXT:  "jsonrpc": "2.0",
 # CHECK-NEXT:  "result": null
 ---
 {"jsonrpc":"2.0":"method":"exit"}

test/clangd/symbols.test

+# RUN: clangd -lit-test < %s | FileCheck %s
+{"jsonrpc":"2.0","id":0,"method":"initialize","params":{"processId":123,"rootPath":"clangd","capabilities":{"workspace":{"symbol":{"symbolKind":{"valueSet": [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26]}}}},"trace":"off"}}
+---
+{"jsonrpc":"2.0","method":"textDocument/didOpen","params":{"textDocument":{"uri":"test:///main.cpp","languageId":"cpp","version":1,"text":"#include <sstream>\nvoid foo(); int main() { foo(); }\n"}}}
+---
+{"jsonrpc":"2.0","id":1,"method":"workspace/symbol","params":{"query":"std::basic_ostringstream"}}
+#      CHECK:  "id": 1,
+# CHECK-NEXT:  "jsonrpc": "2.0",
+# CHECK-NEXT:    "result": [
+# CHECK-NEXT:      {
+# CHECK-NEXT:        "containerName": "std",
+# CHECK-NEXT:        "kind": 5,
+# CHECK-NEXT:        "location": {
+# CHECK-NEXT:          "range": {
+# CHECK-NEXT:            "end": {
+# CHECK-NEXT:              "character": {{.*}},
+# CHECK-NEXT:              "line": {{.*}}
+# CHECK-NEXT:            },
+# CHECK-NEXT:            "start": {
+# CHECK-NEXT:              "character": {{.*}},
+# CHECK-NEXT:              "line": {{.*}}
+# CHECK-NEXT:            }
+# CHECK-NEXT:          },
+# CHECK-NEXT:          "uri": "file://{{.*}}/sstream"
+# CHECK-NEXT:        },
+# CHECK-NEXT:        "name": "basic_ostringstream"
+# CHECK-NEXT:      }
+# CHECK-NEXT:    ]
+# CHECK-NEXT:}
+---
+{"jsonrpc":"2.0","id":3,"method":"shutdown"}
+---
+{"jsonrpc":"2.0","method":"exit"}

unittests/clangd/CMakeLists.txt

add_extra_unittest(ClangdTests
   Annotations.cpp
   ClangdTests.cpp
   ClangdUnitTests.cpp
   CodeCompleteTests.cpp
   CodeCompletionStringsTests.cpp
   ContextTests.cpp
   DraftStoreTests.cpp
   FileIndexTests.cpp
+  FindSymbolsTests.cpp
   FuzzyMatchTests.cpp
   GlobalCompilationDatabaseTests.cpp
   HeadersTests.cpp
   IndexTests.cpp
   JSONExprTests.cpp
   SourceCodeTests.cpp
   SymbolCollectorTests.cpp
   SyncAPI.cpp

unittests/clangd/FindSymbolsTests.cpp

+//===-- FindSymbolsTests.cpp -------------------------*- C++ -*------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+#include "Annotations.h"
+#include "ClangdServer.h"
+#include "FindSymbols.h"
+#include "SyncAPI.h"
+#include "TestFS.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace clangd {
+
+namespace {
+
+using ::testing::AllOf;
+using ::testing::AnyOf;
+using ::testing::ElementsAre;
+using ::testing::IsEmpty;
+using ::testing::UnorderedElementsAre;
+
+class IgnoreDiagnostics : public DiagnosticsConsumer {
+  void onDiagnosticsReady(PathRef File,
+                          std::vector<Diag> Diagnostics) override {}
+};
+
+// GMock helpers for matching SymbolInfos items.
+MATCHER_P(Named, Name, "") { return arg.name == Name; }
+MATCHER_P(InContainer, ContainerName, "") {
+  return arg.containerName == ContainerName;
+}
+MATCHER_P(WithKind, Kind, "") { return arg.kind == Kind; }
+
+ClangdServer::Options optsForTests() {
+  auto ServerOpts = ClangdServer::optsForTest();
+  ServerOpts.BuildDynamicSymbolIndex = true;
+  return ServerOpts;
+}
+
+class WorkspaceSymbolsTest : public ::testing::Test {
+public:
+  WorkspaceSymbolsTest()
+      : Server(CDB, FSProvider, DiagConsumer, optsForTests()) {}
+
+protected:
+  MockFSProvider FSProvider;
+  MockCompilationDatabase CDB;
+  IgnoreDiagnostics DiagConsumer;
+  ClangdServer Server;
+  int Limit;
+
+  std::vector<SymbolInformation> getSymbols(StringRef Query) {
+    EXPECT_TRUE(Server.blockUntilIdleForTest()) << "Waiting for preamble";
+    auto SymbolInfos = runWorkspaceSymbols(Server, Query, Limit);
+    EXPECT_TRUE(bool(SymbolInfos)) << "workspaceSymbols returned an error";
+    return *SymbolInfos;
+  }
+
+  void addFile(StringRef FileName, StringRef Contents) {
+    auto Path = testPath(FileName);
+    FSProvider.Files[Path] = Contents;
+    Server.addDocument(Path, Contents);
+  }
+};
+
+} // namespace
+
+TEST_F(WorkspaceSymbolsTest, NoMacro) {
+  addFile("foo.cpp", R"cpp(
+      #define MACRO X
+      )cpp");
+
+  // Macros are not in the index.
+  EXPECT_THAT(getSymbols("macro"), IsEmpty());
+}
+
+TEST_F(WorkspaceSymbolsTest, NoLocals) {
+  addFile("foo.cpp", R"cpp(
+      void test(int FirstParam, int SecondParam) {
+        struct LocalClass {};
+        int local_var;
+      })cpp");
+  EXPECT_THAT(getSymbols("l"), IsEmpty());
+  EXPECT_THAT(getSymbols("p"), IsEmpty());
+}
+
+TEST_F(WorkspaceSymbolsTest, Globals) {
+  addFile("foo.h", R"cpp(
+      int global_var;
+
+      int global_func();
+
+      struct GlobalStruct {};)cpp");
+  addFile("foo.cpp", R"cpp(
+      #include "foo.h"
+      )cpp");
+  EXPECT_THAT(getSymbols("global"),
+              UnorderedElementsAre(AllOf(Named("GlobalStruct"), InContainer(""),
+                                         WithKind(SymbolKind::Struct)),
+                                   AllOf(Named("global_func"), InContainer(""),
+                                         WithKind(SymbolKind::Function)),
+                                   AllOf(Named("global_var"), InContainer(""),
+                                         WithKind(SymbolKind::Variable))));
+}
+
+TEST_F(WorkspaceSymbolsTest, Unnamed) {
+  addFile("foo.h", R"cpp(
+      struct {
+        int InUnnamed;
+      } UnnamedStruct;)cpp");
+  addFile("foo.cpp", R"cpp(
+      #include "foo.h"
+      )cpp");
+  EXPECT_THAT(getSymbols("UnnamedStruct"),
+              ElementsAre(AllOf(Named("UnnamedStruct"),
+                                WithKind(SymbolKind::Variable))));
+  EXPECT_THAT(getSymbols("InUnnamed"), IsEmpty());
+}
+
+TEST_F(WorkspaceSymbolsTest, InMainFile) {
+  addFile("foo.cpp", R"cpp(
+      int test() {
+      }
+      )cpp");
+  EXPECT_THAT(getSymbols("test"), IsEmpty());
+}
+
+TEST_F(WorkspaceSymbolsTest, Namespaces) {
+  addFile("foo.h", R"cpp(
+      namespace ans1 {
+        int ai1;
+      namespace ans2 {
+        int ai2;
+      }
+      }
+      )cpp");
+  addFile("foo.cpp", R"cpp(
+      #include "foo.h"
+      )cpp");
+  EXPECT_THAT(
+      getSymbols("a"),
+      UnorderedElementsAre(AllOf(Named("ans1"), InContainer("")),
+                           AllOf(Named("ai1"), InContainer("ans1")),
+                           AllOf(Named("ans2"), InContainer("ans1")),
+                           AllOf(Named("ai2"), InContainer("ans1::ans2"))));
+  EXPECT_THAT(getSymbols("::"),
+              ElementsAre(AllOf(Named("ans1"), InContainer(""))));
+  EXPECT_THAT(getSymbols("::a"),
+              ElementsAre(AllOf(Named("ans1"), InContainer(""))));
+  EXPECT_THAT(getSymbols("ans1::"),
+              UnorderedElementsAre(AllOf(Named("ai1"), InContainer("ans1")),
+                                   AllOf(Named("ans2"), InContainer("ans1"))));
+  EXPECT_THAT(getSymbols("::ans1"),
+              ElementsAre(AllOf(Named("ans1"), InContainer(""))));
+  EXPECT_THAT(getSymbols("::ans1::"),
+              UnorderedElementsAre(AllOf(Named("ai1"), InContainer("ans1")),
+                                   AllOf(Named("ans2"), InContainer("ans1"))));
+  EXPECT_THAT(getSymbols("::ans1::ans2"),
+              ElementsAre(AllOf(Named("ans2"), InContainer("ans1"))));
+  EXPECT_THAT(getSymbols("::ans1::ans2::"),
+              ElementsAre(AllOf(Named("ai2"), InContainer("ans1::ans2"))));
+}
+
+TEST_F(WorkspaceSymbolsTest, AnonymousNamespace) {
+  addFile("foo.h", R"cpp(
+      namespace {
+      void test() {}
+      }
+      )cpp");
+  addFile("foo.cpp", R"cpp(
+      #include "foo.h"
+      )cpp");
+  EXPECT_THAT(getSymbols("test"), IsEmpty());
+}
+
+TEST_F(WorkspaceSymbolsTest, MultiFile) {
+  addFile("foo.h", R"cpp(
+      int foo() {
+      }
+      )cpp");
+  addFile("foo2.h", R"cpp(
+      int foo2() {
+      }
+      )cpp");
+  addFile("foo.cpp", R"cpp(
+      #include "foo.h"
+      #include "foo2.h"
+      )cpp");
+  EXPECT_THAT(getSymbols("foo"),
+              UnorderedElementsAre(AllOf(Named("foo"), InContainer("")),
+                                   AllOf(Named("foo2"), InContainer(""))));
+}
+
+TEST_F(WorkspaceSymbolsTest, GlobalNamespaceQueries) {
+  addFile("foo.h", R"cpp(
+      int foo() {
+      }
+      class Foo {
+        int a;
+      };
+      namespace ns {
+      int foo2() {
+      }
+      }
+      )cpp");
+  addFile("foo.cpp", R"cpp(
+      #include "foo.h"
+      )cpp");
+  EXPECT_THAT(
+      getSymbols("::"),
+      UnorderedElementsAre(
+          AllOf(Named("Foo"), InContainer(""), WithKind(SymbolKind::Class)),
+          AllOf(Named("foo"), InContainer(""), WithKind(SymbolKind::Function)),
+          AllOf(Named("ns"), InContainer(""),
+                WithKind(SymbolKind::Namespace))));
+  EXPECT_THAT(getSymbols(":"), IsEmpty());
+  EXPECT_THAT(getSymbols(""), IsEmpty());
+}
+
+TEST_F(WorkspaceSymbolsTest, WithLimit) {
+  addFile("foo.h", R"cpp(
+      int foo;
+      int foo2;
+      )cpp");
+  addFile("foo.cpp", R"cpp(
+      #include "foo.h"
+      )cpp");
+  EXPECT_THAT(getSymbols("foo"),
+              ElementsAre(AllOf(Named("foo"), InContainer(""),
+                                WithKind(SymbolKind::Variable)),
+                          AllOf(Named("foo2"), InContainer(""),
+                                WithKind(SymbolKind::Variable))));
+
+  Limit = 1;
+  EXPECT_THAT(getSymbols("foo"),
+              ElementsAre(AnyOf((Named("foo"), InContainer("")),
+                                AllOf(Named("foo2"), InContainer("")))));
+}
+
+} // namespace clangd
+} // namespace clang

unittests/clangd/SyncAPI.h

 llvm::Expected<std::vector<DocumentHighlight>>
 runFindDocumentHighlights(ClangdServer &Server, PathRef File, Position Pos);
 
 llvm::Expected<std::vector<tooling::Replacement>>
 runRename(ClangdServer &Server, PathRef File, Position Pos, StringRef NewName);
 
 std::string runDumpAST(ClangdServer &Server, PathRef File);
 
+llvm::Expected<std::vector<SymbolInformation>>
+runWorkspaceSymbols(ClangdServer &Server, StringRef Query, int Limit);
+
 } // namespace clangd
 } // namespace clang
 
 #endif

unittests/clangd/SyncAPI.cpp

 }
 
 std::string runDumpAST(ClangdServer &Server, PathRef File) {
   llvm::Optional<std::string> Result;
   Server.dumpAST(File, capture(Result));
   return std::move(*Result);
 }
 
+llvm::Expected<std::vector<SymbolInformation>>
+runWorkspaceSymbols(ClangdServer &Server, StringRef Query, int Limit) {
+  llvm::Optional<llvm::Expected<std::vector<SymbolInformation>>> Result;
+  Server.workspaceSymbols(Query, Limit, capture(Result));
+  return std::move(*Result);
+}
+
 } // namespace clangd
 } // namespace clang