<div dir="ltr">Hi,<div><br></div><div>Thanks for making a summary of existing solutions!<br><div class="gmail_extra"><br><div class="gmail_quote">On 17 May 2017 at 23:38, Marc-André Laperle via cfe-dev <span dir="ltr"><<a href="mailto:cfe-dev@lists.llvm.org" target="_blank">cfe-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">Hi,<br>
<br>
I’ve been thinking about how to add features to Clangd requiring an index, i.e. features that need a database containing information of all source files (Go to definition, find references, etc). I’d like to share with you my thoughts on how things are and what approaches could be taken before getting too deep into implementing something.<br>
<br>
My understanding of the current Clang indexing facilities is as follow:<br>
  - It is part of the libclang so it is meant to have a stable API which can be limiting because it does not expose the full Clang C/C++ API<br>
  - It does not have persistence. I.e. the index cannot be reloaded from disk at a later time after it is built.<br>
  - There is no header caching mechanism in order to allow faster reparsing when a source file changes but its included headers haven’t (a common occurrence during code editing).<br></blockquote><div><br></div><div>Have you looked into the precompiled preamble? I believe it can (and is) used when indexing.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<br>
-- Other indexing solutions --<br>
<br>
I have done a very high level exploration of some other projects using Clang for indexing, you can find some notes here:<br>
<a href="https://docs.google.com/document/d/1Z0pDZpUlhyRkw1yB9frVVeb_xgSb5PuXD0-aeUtKkpo/edit?usp=sharing" rel="noreferrer" target="_blank">https://docs.google.com/<wbr>document/d/<wbr>1Z0pDZpUlhyRkw1yB9frVVeb_<wbr>xgSb5PuXD0-aeUtKkpo/edit?usp=<wbr>sharing</a><br>
(Feel free to add your own notes if you’d like!)<br>
<br>
>From what I gathered:<br>
  - Some projects are using libclang, others use the Clang C++ APIs (AST) directly because of libclang limitations<br>
  - Some projects have a custom index formats on disk, others use RDMS (PostgreSql, Sqlite) or other already available solutions (Elastic Search, etc).<br>
  - I didn’t notice any projects based on Clang doing header caching, although perhaps I missed it. Ilya Biryukov wrote that JetBrains CLion does header caching but it’s not clear how they are stored or if it is using Clang. </blockquote><div><br></div><div>IIRC CLion uses a custom C++ parser instead of Clang.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">On the Eclipse CDT side, Clang is not used but there is header caching by storing the semantic model in the index (not plain AST). Then the source files can be parsed reusing that cached information.<br>
<br>
Possible approach for Clangd:<br>
  - I suggest using Clang libraries directly and not using libclang in order to not have any limitations. I think that using a stable API is not as important since Clangd resides in the same tree and is built and tested in coordination with Clang itself. The downside is that it will not reuse some of the work already done in libclang such as finding references, etc.<br></blockquote><div><br></div><div>I agree, Clangd should not use libclang. Note that in general libclang's indexer API is intended to be a wrapper around the core implementation in lib/Index. I also don't think libclang doesn't expose any means to find references.</div><div><br></div><div>I would encourage Clangd to reuse existing code in lib/Index. Even though it has bugs, we are (and will be) currently fixing a lot of issues in the library to ensure that our consumer records all of the possible declarations and references for both C++ and Obj-C.</div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
  - I think introducing a big dependency such as PostgreSql is not acceptable for Clangd (correct me if I’m wrong!). So a custom tailored file format for the index make more sense to me.<br>
  - For header caching, I wonder if it is possible to reuse the precompiled header support in Clang. There would be some logic that would decide whether or not a precompiled header could be used depending on the preprocessing context (same macro definitions, etc).</blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<br>
-- The Index model --<br>
<br>
Here’s what the data model could look like. For sure it’s partial and I expect it will evolve quite a bit. But it should be enough to communicate the general idea.<br>
<br>
Index: Represents the model of the code base as a whole<br>
  - IndexFile []<br>
<br>
IndexFile: Represents an indexed file<br>
  - URI path<br>
  - IndexFile includedBy [ ]<br>
  - IndexName [ ]<br>
  - Last modified timestamp, checksum, etc<br>
<br>
IndexName: Represents a declaration, definition, macro, etc<br>
  - Source Location<br>
  - IndexReference [ ]<br>
<br>
IndexNameReference: Reference to a name<br>
  - Source Location<br>
  - Access (read, write, read/write)<br>
<br>
IndexTypeName extends IndexName: represents classes, structs, etc<br>
  - IndexTypeName bases [ ]<br>
<br>
IndexFunctionName extends IndexName: represents functions, methods, etc<br>
  - IndexFunctionName callers [ ]<br>
<br>
Note that a lot of information probably doesn’t need to be modeled because a lot of information only needs to be available with an opened file for which we can have access to the full AST.<br>
<br>
-- The persisted file format --<br>
<br>
All elements in the model mentioned above could have a querying interface which could be implemented for an “in memory” database (simpler to debug and fast for small projects) and also for an on-disk database. From my experience in Eclipse CDT, the index on disk was stored in the form of a BTree which worked quite well. The BTree is made out of chunks. Chunks can be cached in memory and fetched from disk as required. Every information in the model is fetched from the database (from cache otherwise from disk). A similar approach could be used for Clangd if it’s deemed suitable.<br></blockquote><div><br></div><div>Have you looked into LLVM's bitcode as a possible format for the persistent index? Clang currently uses it for serialized diagnostics and modules.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<br>
<br>
<br>
In summary, I’m proposing for Clangd an index on disk stored in the form of a BTree that is populated using Clang’s C++ API (not libclang). Any concerns or input would be greatly appreciated. Just as a side note, I’m aware that this is just one line of thinking and others could be considered.<br>
<br>
Best regards,<br>
Marc-André Laperle<br>
______________________________<wbr>_________________<br>
cfe-dev mailing list<br>
<a href="mailto:cfe-dev@lists.llvm.org">cfe-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/cfe-dev</a><br>
</blockquote></div><br></div></div></div>