Design
cquery is architecturally split into three components: an indexer, a completion backend, and a querydb frontend. The querydb frontend implements the language server protocol which allows cquery to be used with any editor, such as VS Code, Vim, Emacs, Atom, Eclipse, and Sublime.
The querydb frontend is language agnostic; it is relatively easy to extend cquery to support other programming languages by writing an indexer for said languages. The indexer just needs to generate a file in the IndexFile format. The querydb front-end is oblivious to how this file was generated. It will simply send it through the import pipeline and begin serving requests based on the imported data.
cquery is split into a number of different threads. Primarily, there are xxx (ie, 40) indexer threads which perform a small set of highly parallelizable tasks, the two code completion threads, and one querydb thread.
The indexer threads are responsible for running an instance of the indexer, computing querydb updates, and writing indexes to files. querydb is responsible for applying index updates and responding to query requests.
The import pipeline has been designed to minimize the amount of work that the querydb thread needs to do, since any work that happens on querydb is part of the critical path and dramatically reduces scalability. The pipeline is as follows:
1. indexer:
- check modification time on existing imported index, if it has not
changed exit
- goto step 2
2. querydb:
- check if path is loaded into querydb, if so goto 2a
- generate local to global id mappings for current/previous indexes
- goto step 3
2a. indexer:
- load previous index from disk
- goto step 2 to load local to global ids for previous index
3. indexer:
- prepare IndexUpdate, either a full or delta depending on if there is a
previous index update instance
- write new index to disk
4. querydb: import IndexUpdate
idle: when indexer is idle take IndexUpdate instances and merge them togetherThis architecture enables near linear scaling to 50+ processors and extremely fast restoring from cache.
Each indexer generates a serialized IndexFile representation of a given translation unit. The IndexFile for foo.cc contains information only discovered in foo.cc. If foo.cc depends on foo.h, then there is a separate IndexFile for foo.h. This approach nicely resolves issues with common header files, like common.h included by both foo.cc and bar.cc. common.h will be imported into querydb only once.
The IndexFile contains quite a bit of information. It is split into three sections: types, functions, and variables. If one of these objects (ie, functions) is referenced, a reference is added. For example, given this very simple code we generate the following index:
1: void called() {}
2: void caller() {
3: called();
4: }
IndexFile:
{
"funcs": [{
"id": 0,
"usr": "c:@F@called#",
"short_name": "called",
"detailed_name": "void called()",
"definition_spelling": "1:6-1:12",
"definition_extent": "1:1-1:17",
"callers": ["1@3:3-3:9"]
}, {
"id": 1,
"usr": "c:@F@caller#",
"short_name": "caller",
"detailed_name": "void caller()",
"definition_spelling": "2:6-2:12",
"definition_extent": "2:1-4:2",
"callees": ["0@3:3-3:9"]
}]
}If called was not defined in the file, certain information would be elided from the index, like the definition location. All available data for the function is imported into querydb and the assumption is made that another file can add additional metadata about the function. This approach seamlessly enables cross-references across files.
The index size is much larger than the code size.
Testing the indexer is relatively straight-forward and worthwhile. For example, changing clang versions often has small changes in what gets indexed, and new workarounds or approaches are needed.
Each test is a cc file which has some desired behavior, for example, calling a function prototype. The serialized IndexFile is written below and the test runner verifies that the actual serialized state matches the expected serialized state.
As a user edits the code base, the index actively changes, especially after large operations like a git checkout. The existing index that cquery has imported is stored in disk in the cache directory. A new in-memory index is generated for the given target file. The existing index is sent through the import pipeline; if the index has already been imported, the previous index is loaded off disk and a delta index update is computed off the querydb thread. This delta index update is then applied and the new index is written to disk, replacing the previous one.
Unfortunately, generating an index for an arbitrary file can take anywhere from 3-20 seconds. It is simply not possible to interactively index a file, so cquery understands that an index can be out of date.
When saving an indexed file to disk, the contents of the file that generated that index are also copied to the cache directory. When looking up semantic information from the index to the current working file, the working file is compared to the indexed file contents using a diff algorithm.
Monitoring file changes does not work because there is no guarantee that you have access to every file change - a simple example is starting the indexer after syncing code.
All semantic analysis operations are performed in either the indexing stage or on the querydb thread. All operations which require a deep level of code inspection happen in the indexer, otherwise query latency would get too high.
cquery fetches semantic analysis results on the querydb thread, as that is where they are stored. This includes things like references, calls, base methods, etc.
cquery is fast enough to show references above all referenceable types in real-time, but this leads to an editor that is too visually-busy.
The only way to achieve such fast semantic query performance is to reduce the amount of work to the absolute minimum. When looking up a simple semantic operation, such as derived types, cquery finds the symbol at the given cursor location, looks up the metadata structure which is stored in a flat array, and immediately finds the list of derived types.
More advanced operations, like a type hierarchy, involve a number of different queries across the querydb data structures instead of a single lookup. However, since most everything is stored as a flat array doing so is fast - the only performance issues are from cache misses.
Clang provides a number of APIs for code completion which provide good results. However, latency is often very high with these APIs (often well over 1s). A naive integration leads to a very poor user experience.
Clang will provide relatively fast code completions (ie, under 100ms) assuming that the document has not had major changes since it was parsed. cquery takes advantage of this by having two indexer threads. One thread services completion requests, while the other thread is creating a new clang completion index in the background. The new clang completion index is recreated whenever the user saves the file.
There is a significant amount of implementation complexity because the user can send many completion requests over a very short period of time. When performing the completion requests cquery still needs to service code lens requests, as vscode will start updating code lens. If cquery takes too long to respond, vscode will hide the code lens which will cause a very annoying flickering.
cquery fetches information about files using the clang compilation database, which is just a (very) large JSON file which encodes every translation unit (cc file) in the project along with the arguments that are passed to clang.
Unfortunately, compile_commands.json is not always able to be passed directly to clang, ie, arguments is not entirely reliable; for example, in Chrome, gomacc is the first argument in the list, which will cause libclang to fail if passed. This is addressed by a custom filtering layer.
If using cquery in a third party project and it is challenging to generate a compile_commands.json file from ninja, cmake, or a similar tool, the user can specify a list of arguments to send to clang in a .cquery file.