[clangd] automatically index STL

[kuhnel]

Summary

This addresses issue 403.

Goal
Provide code completion for entire STL, even if it was not yet used in the project and thus is not contained in any index.

Design:
Generate a header file that includes all of STL. Then inject this file into the background indexer.

Pros:

• relatively easy to implement, reusing background index for the hard work

Cons:

• need to write to a file
• file needs to be close to project to find compilation database
• not sure when file can be deleted after background indexer finishes
• need to check with every opened file if we still need to perform the STL indexing

Notes:
to enable the feature run clangd with the new flag --index-stl.

[kuhnel]

@sammccall here the first implementation we talked about yesterday. This works well on my testing poject that has a compile_commands.json. It does not work without one.

Also I'm not really happy with the design as I haven't really found a good place to store the generated header file.

Should we look into implementing a separate Index to only handle the STL?

[kadircet]

(not sure if you were looking for comments yet, but i was just passing by and it was a small-ish patch, so couldn't resist :D)

clang-tools-extra/clangd/index/Background.cpp

449

In theory BackgroundIndex only reads headers from the FS, so we can provide an in-memory buffer as the main file itself. prepareCompilerInstance in Compiler.h (and used by BackgroundIndex::index does that exactly).

It might be better to just have a separate endpoint in BackgroundIndex (as indexSTLHeaders) that is invoked once at construction time that enqueues indexing of this phantom file.

WDYT?

clang-tools-extra/clangd/tool/ClangdMain.cpp

527

do we really need to hide this behind a flag ? it sounds like a quite useful feature to me with minimal risk of regressions and unlikely to make anyone upset. in the end we are not doing anything heuristically and just throwing clang on some STL headers, that'll probably be included within the TUs eventually.

there's always the risk of crashing while parsing some STL headers, but i don't think it is any different than user just including the header manually.

the biggest problem i can see is people using custom STL headers, but hopefully compile flags interpolation logic should be able to infer the relevant location for those. and in the cases it fails we either index the default STL and suggest people some symbols their implementation might lack, or fail to find STL at all and print some logs for the missing includes.

[kuhnel]

Yes, I was looking for feedback on this one as I wasn't happy with my design.

clang-tools-extra/clangd/index/Background.cpp

449

Agree to both. I'll take a look.

clang-tools-extra/clangd/tool/ClangdMain.cpp

527

Back when I was developing embedded software, we couldn't use the STL for various reasons (object size, no exceptions, no dynamic memory, ...) and had our own, proprietary base library. In such a scenario it would be annoying if clangd would be proposing things I could not use in the project.

So we should have a way for users to disable this. I'm fine if we switch it on by default and offer a --disable-stl-index flag instead.

[njames93]

How does this approach work with differing language standards. For example with an old implementation designed for c++14, string_view header won't exist. If the implementation is designed to work with c++17, including that header in c++14 mode will probably be ifdef... Error.

[kadircet]

In D94293#2486468, @njames93 wrote:

How does this approach work with differing language standards. For example with an old implementation designed for c++14, string_view header won't exist. If the implementation is designed to work with c++17, including that header in c++14 mode will probably be ifdef... Error.

As I mentioned in my comments for putting this behind a flag, in such scenarios we should just hit some "missing includes" while indexing the phantom file, so all should be fine.

clang-tools-extra/clangd/tool/ClangdMain.cpp

527

I see. It still feels like those developers would be less inclined to accept autocompletion of std::vector compared to xyz::vector and also our ranking should be doing a good job of promoting xyz::vector due to its high number of usage, compared to std::vector.

I am mostly unhappy about the flag as it needs propagation to many components. It might be better to have it as a config option, which requires a lot less plumbing (at least for bg-index), if you think even the down-ranking of std symbols wouldn't be a good experience.

[sammccall]

In D94293#2486468, @njames93 wrote:

How does this approach work with differing language standards. For example with an old implementation designed for c++14, string_view header won't exist. If the implementation is designed to work with c++17, including that header in c++14 mode will probably be ifdef... Error.

Yeah, this seems at least annoying. There's some spectrum of:

• build indexes per language version and dynamically switch between them based on the file
• make this variable in some global way (e.g. a flag, or first file opened chooses the language version)
• language version is always (e.g.) c++14, hopefully it's better than nothing

Similar to the no-stdlib question and the multiple-languages question, this points to a separate index layer being a stronger design to allow dynamically swapping it (though worse can be better, too).

clang-tools-extra/clangd/ClangdServer.h

161

nit: "the standard library"

for two reasons:

• "STL" is no longer the correct name, even for C++
• languages other than C++ have standard libraries (C in particular) that we could also control with this flag

clang-tools-extra/clangd/index/Background.cpp

451

separate from the issue of virtual vs real file, it's not clear to me why we *want* this file to be close to the project rather than in some completely anonymous location.

(I have a few guesses, but...)

clang-tools-extra/clangd/index/Background.h

160

this can happen 0+ times (roughly it happens once every time an enumerable CDB is discovered).

Instead, we'd want it to happen exactly once, or possibly 0-1 times if we're going to be language-sensitive.

clang-tools-extra/clangd/tool/ClangdMain.cpp

527

Yeah, this is a good point.

Having this configurable would be valuable, but the useful granularity for such an option is per-file (Config) rather than a global clangd flag, as it's codebase-specific.

Unfortunately that doesn't really square with having it in the background index.

[kuhnel]

thx for the review and feedback!

I guess I'll re-design the feature and add a new indexing layer instead.
However that might take a while, so I'll abandon this revision and start a new one later on.

clang-tools-extra/clangd/ClangdServer.h

struct Options {
     std::vector<std::string> QueryDriverGlobs;
 
     /// Enable notification-based semantic highlighting.
     bool TheiaSemanticHighlighting = false;
 
     /// Enable preview of FoldingRanges feature.
     bool FoldingRanges = false;
 
+    // Automatically parse the STL to enable code completion and include
+    // insertion
+    bool IndexSTL = false;
+
     explicit operator TUScheduler::Options() const;
   };
   // Sensible default options for use in tests.
   // Features like indexing must be enabled if desired.
   static Options optsForTest();
 
   /// Creates a new ClangdServer instance.
   ///

clang-tools-extra/clangd/ClangdServer.cpp

 #include "index/CanonicalIncludes.h"
 #include "index/FileIndex.h"
 #include "index/Merge.h"
 #include "refactor/Rename.h"
 #include "refactor/Tweak.h"
 #include "support/Logger.h"
 #include "support/Markup.h"
 #include "support/MemoryTree.h"
+#include "support/Path.h"
 #include "support/ThreadsafeFS.h"
 #include "support/Trace.h"
 #include "clang/Format/Format.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Tooling/CompilationDatabase.h"
 #include "clang/Tooling/Core/Replacement.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/ScopedPrinter.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <chrono>
 #include <future>
-#include <memory>
 #include <mutex>
-#include <string>
 #include <type_traits>
 
 namespace clang {
 namespace clangd {
 namespace {
 
 // Update the FileIndex with new ASTs and plumb the diagnostics responses.
 struct UpdateIndexCallbacks : public ParsingCallbacks {
if (this->Index != nullptr) {
       this->Index = Idx;
     }
   };
   if (Opts.StaticIndex)
     AddIndex(Opts.StaticIndex);
   if (Opts.BackgroundIndex) {
     BackgroundIndex::Options BGOpts;
     BGOpts.ThreadPoolSize = std::max(Opts.AsyncThreadsCount, 1u);
+    BGOpts.IndexSTL = Opts.IndexSTL;
     BGOpts.OnProgress = [Callbacks](BackgroundQueue::Stats S) {
       if (Callbacks)
         Callbacks->onBackgroundIndexProgress(S);
     };
     BGOpts.ContextProvider = [this](PathRef P) {
       return createProcessingContext(P);
     };
     BGOpts.CollectMainFileRefs = Opts.CollectMainFileRefs;
void ClangdServer::addDocument(PathRef File, llvm::StringRef Contents,
   Inputs.Index = Index;
   Inputs.ClangTidyProvider = ClangTidyProvider;
   Inputs.Opts.BuildRecoveryAST = BuildRecoveryAST;
   Inputs.Opts.PreserveRecoveryASTType = PreserveRecoveryASTType;
   bool NewFile = WorkScheduler.update(File, Inputs, WantDiags);
   // If we loaded Foo.h, we want to make sure Foo.cpp is indexed.
   if (NewFile && BackgroundIdx)
     BackgroundIdx->boostRelated(File);
+  if (BackgroundIdx)
+    BackgroundIdx->indexSTLHeaders({File.str()});
 }
 
 void ClangdServer::removeDocument(PathRef File) { WorkScheduler.remove(File); }
 
 void ClangdServer::codeComplete(PathRef File, Position Pos,
                                 const clangd::CodeCompleteOptions &Opts,
                                 Callback<CodeCompleteResult> CB) {
   // Copy completion options for passing them to async task handler.

clang-tools-extra/clangd/index/Background.h

struct Options {
     // Callback that provides notifications as indexing makes progress.
     std::function<void(BackgroundQueue::Stats)> OnProgress = nullptr;
     // Function called to obtain the Context to use while indexing the specified
     // file. Called with the empty string for other tasks.
     // (When called, the context from BackgroundIndex construction is active).
     std::function<Context(PathRef)> ContextProvider = nullptr;
     // Whether to collect references to main-file-only symbols.
     bool CollectMainFileRefs = false;
+    bool IndexSTL = false;
   };
 
   /// Creates a new background index and starts its threads.
   /// The current Context will be propagated to each worker thread.
   BackgroundIndex(const ThreadsafeFS &, const GlobalCompilationDatabase &CDB,
                   BackgroundIndexStorage::Factory IndexStorageFactory,
                   Options Opts);
   ~BackgroundIndex(); // Blocks while the current task finishes.
 
   // Enqueue translation units for indexing.
   // The indexing happens in a background thread, so the symbols will be
   // available sometime later.
   void enqueue(const std::vector<std::string> &ChangedFiles) {
     Queue.push(changedFilesTask(ChangedFiles));
+    // TODO(kuhnel): Only index if enqueueing C++ file.
+    indexSTLHeaders(ChangedFiles);
   }
 
   /// Boosts priority of indexing related to Path.
   /// Typically used to index TUs when headers are opened.
   void boostRelated(llvm::StringRef Path);
 
   // Cause background threads to stop after ther current task, any remaining
   // tasks will be discarded.
   void stop() {
     Rebuilder.shutdown();
     Queue.stop();
   }
 
   // Wait until the queue is empty, to allow deterministic testing.
   LLVM_NODISCARD bool
   blockUntilIdleForTest(llvm::Optional<double> TimeoutSeconds = 10) {
     return Queue.blockUntilIdleForTest(TimeoutSeconds);
   }
 
   void profile(MemoryTree &MT) const;
 
+  void indexSTLHeaders(const std::vector<std::string> &ChangedFiles);
+
 private:
   /// Represents the state of a single file when indexing was performed.
   struct ShardVersion {
     FileDigest Digest{{0}};
     bool HadErrors = false;
   };
 
   /// Given index results from a TU, only update symbols coming from files with
private:
   enum QueuePriority {
     IndexFile,
     IndexBoostedFile,
     LoadShards,
   };
   BackgroundQueue Queue;
   AsyncTaskRunner ThreadPool;
   GlobalCompilationDatabase::CommandChanged::Subscription CommandsChanged;
+  // Whether the STL header files need to be indexed
+  bool NeedToIndexSTLHeaders = true;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif

clang-tools-extra/clangd/index/Background.cpp

 #include "llvm/Support/Path.h"
 #include "llvm/Support/Threading.h"
 
 #include <algorithm>
 #include <atomic>
 #include <chrono>
 #include <condition_variable>
 #include <cstddef>
+#include <fstream>
 #include <memory>
 #include <mutex>
 #include <numeric>
 #include <queue>
 #include <random>
 #include <string>
 #include <thread>
 #include <utility>
: SwapIndex(std::make_unique<MemIndex>()), TFS(TFS), CDB(CDB),
       ContextProvider(std::move(Opts.ContextProvider)),
       CollectMainFileRefs(Opts.CollectMainFileRefs),
       Rebuilder(this, &IndexedSymbols, Opts.ThreadPoolSize),
       IndexStorageFactory(std::move(IndexStorageFactory)),
       Queue(std::move(Opts.OnProgress)),
       CommandsChanged(
           CDB.watch([&](const std::vector<std::string> &ChangedFiles) {
             enqueue(ChangedFiles);
-          })) {
+          })),
+      NeedToIndexSTLHeaders(Opts.IndexSTL) {
   assert(Opts.ThreadPoolSize > 0 && "Thread pool size can't be zero.");
   assert(this->IndexStorageFactory && "Storage factory can not be null!");
   for (unsigned I = 0; I < Opts.ThreadPoolSize; ++I) {
     ThreadPool.runAsync("background-worker-" + llvm::Twine(I + 1),
                         [this, Ctx(Context::current().clone())]() mutable {
                           WithContext BGContext(std::move(Ctx));
                           Queue.work([&] { Rebuilder.idle(); });
                         });
BackgroundIndex::loadProject(std::vector<std::string> MainFiles) {
   return {TUsToIndex.begin(), TUsToIndex.end()};
 }
 
 void BackgroundIndex::profile(MemoryTree &MT) const {
   IndexedSymbols.profile(MT.child("slabs"));
   // We don't want to mix memory used by index and symbols, so call base class.
   MT.child("index").addUsage(SwapIndex::estimateMemoryUsage());
 }
+
+void BackgroundIndex::indexSTLHeaders(
+    const std::vector<std::string> &ChangedFiles) {
+  // Only index if we need to.
+  if (!NeedToIndexSTLHeaders)
+    return;
+
+  vlog("Trying to find place for STL header include.");
+  std::string SourceRoot;
+  for (auto ChangedFile : ChangedFiles) {
+    if (CDB.getProjectInfo(ChangedFile)) {
+      SourceRoot = CDB.getProjectInfo(ChangedFile)->SourceRoot;
+      break;
+    }
+  }
+  // fallback if we can't find a Compilations Database
+  if (SourceRoot.empty()) {
+    if (ChangedFiles.empty()) {
+      vlog("Could not find place for STL header include.");
+      return;
+    }
+    SourceRoot = llvm::sys::path::parent_path(ChangedFiles[0]).str();
+  }
+  // TODO(kuhnel): is the a better place to store this file?
+  // TODO(kuhnel): do we need a file at all, can we just pass a string to the
+  //               indexer?
+  const Path STLHeaderPath = SourceRoot + "/.stl_header.h";
+  vlog("Indexing STL headers from {0}", STLHeaderPath);
+  std::ofstream STLIndexFile;
+  std::set<std::string> Headers;
+
+// gather all the known STL headers, without duplicates
+#define SYMBOL(Name, NameSpace, Header) Headers.insert(#Header);
+#include "StdSymbolMap.inc"
+#undef SYMBOL
+
+  // TODO(kuhnel): figure out if there are other ways to write to files in llvm.
+  STLIndexFile.open(STLHeaderPath);
+  STLIndexFile << "/* This is a temporary file created by clangd. It is "
+                  "used by the background index to automatically index the "
+                  "standard template library. */"
+               << std::endl
+               << std::endl;
+  for (auto Header : Headers) {
+    STLIndexFile << "#include " << Header << std::endl;
+  }
+  STLIndexFile.close();
+  Queue.push(changedFilesTask({STLHeaderPath}));
+  NeedToIndexSTLHeaders = false;
+};
+
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/tool/ClangdMain.cpp

return []() {
     if (malloc_trim(MallocTrimPad))
       vlog("Released memory via malloc_trim");
   };
 }
 #else
 std::function<void()> getMemoryCleanupFunction() { return nullptr; }
 #endif
 
+opt<bool> IndexSTL{
+    "index-stl",
+    cat(Features),
+    desc("Background index should always include the STL headers even if \n"
+         "not used at the moment. This will enable code completion and \n"
+         "include fixer."),
+    init(true),
+};
+
 #if CLANGD_ENABLE_REMOTE
 opt<std::string> RemoteIndexAddress{
     "remote-index-address",
     cat(Features),
     desc("Address of the remote index server"),
 };
 
 // FIXME(kirillbobyrev): Should this be the location of compile_commands.json?
if (TweakList.getNumOccurrences())
       return llvm::is_contained(TweakList, T.id());
     return true;
   };
   if (ForceOffsetEncoding != OffsetEncoding::UnsupportedEncoding)
     Opts.Encoding = ForceOffsetEncoding;
 
   // Shall we allow to customize the file limit?
   Opts.Rename.AllowCrossFile = CrossFileRename;
+  Opts.IndexSTL = IndexSTL;
 
   if (CheckFile.getNumOccurrences()) {
     llvm::SmallString<256> Path;
     llvm::sys::fs::real_path(CheckFile, Path, /*expand_tilde=*/true);
     log("Entering check mode (no LSP server)");
     return check(Path, TFS, Opts)
                ? 0
                : static_cast<int>(ErrorResultCode::CheckFailed);