[clangd] Make signatureHelp work with stale preambles

[kadircet]

Summary

This is achieved by calculating newly added includes and implicitly
parsing them as if they were part of the main file.

This also gets rid of the need for consistent preamble reads.

[sammccall]

This is the perfect feature to start with (doesn't actually need any location transforms, lets us drop TUScheduler features), so well done for finding that.

That said, high-level comments mostly about preamble patching in general rather than this particular case.

clang-tools-extra/clangd/CodeComplete.cpp

1072

This is going to be used in other places where we parse too, we'll want some abstraction to encapsulate the analysis, the tweaks to CompilerInvocation, and (for other uses) mapping of locations from the preamble file and injected regions.

As discussed offline, I think injecting by synthesizing a header snippet which is mapped into the VFS and then added to PreprocessorOpts.Includes is preferable to tweaking the CompilerInvocation directly:

• it extends to arbitrary directives, e.g. there's no way today to inject an #import directive via CompilerInvocation, no control over <> vs "", ...
• it's easier to debug as the injected region can easily be dumped as text
• it's easier to for code to recognize locations in our injected region if we're not sharing it with e.g. -Ds coming from the commandline
• (I think) it lets us use the PresumedLocation mechanism to record the association of each injected line with the corresponding line in the mainfile (not sure if this is valuable if we also need to translate the other way)

So I'd probably suggest something like

class PreamblePatch { // ends up stored in ParsedAST
public:
  PreamblePatch(); // empty, used when no patching is done
  static PreamblePatch compute(const ParseInputs&);

  void apply(CompilerInvocation&); // adjusts PPOptions.{RemappedFileBuffers, Includes} to include injected header

  friend operator<<(raw_ostream&, const PreamblePatch &); // probably just dumps InjectedHeaderContent

  // later... not sure about signature/names here
  SourceLocation parsedToUserLoc(SourceLocation);
  SourceLocation userToParsedLoc(SourceLocation); // is this also needed?

private:
  std::string InjectedHeaderContent; // with #line directives, or at least comments 
  // some data structure to map between locations in the stale preamble and their user locations
  // some data structure to map between locations in the injected header and their user locations
};

clang-tools-extra/clangd/Headers.cpp

237 ↗

(On Diff #254779)

The tradeoff between raw-lexing and running the actual preprocessor in SingleFileParseMode seems pretty interesting.
(I'm not suggesting any particular change here, but I think it's worth exploring at some point. If the raw lexing is "for now" let's call that out, if it's a decision let's justify it. Also just curious what you think at this point - I know we've discussed this in the past and I pushed for raw-lexing)

---

The SingleFileParseMode is more accurate:

• it's probably much easier to handle more directives correctly
• it will handle ifdefs correctly where possible without reading files
• it will tell us what includes actually resolve to (I'm not sure if this is useful though, when you can inject an #include with the right spelling and check that later)
• ??? maybe we can recognize bad directives that we want to avoid injecting for better results ???
• we don't have to do weird stuff like track the raw-lexed includes in preambledata

But potentially expensive with IO:

• it will stat all the files along the search path.
• it will ::realpath all the files that were found

Possible workaround for stat along the search path: most of the time, the #include directives are going to refer to files that were already included in the previous preamble (i.e. the preamble we're trying to patch) so we (heuristically) know what they resolve to.
If we used the HeaderSearchInfo's alias map to redirect <foo.h> to </absolute/path/to/foo.h> then #include <foo.h> will just cost a single stat. And when our heuristic is wrong and <foo.h> resolves to something else, we'll just get an include-not-found, we can still add the #include.

More radical workaround: give it a completely null VFS so it can't do any IO. All includes will fail to resolve, but if we don't need their resolved path at this point we don't care, right?

clang-tools-extra/clangd/Headers.h

198 ↗

(On Diff #254779)

I'm guessing the APIs we end up with probably belong more in Preamble.h rather than here, both thematically and in terms of layering

[kadircet]

• Encapsulate logic into PreamblePatch

[kadircet]

clang-tools-extra/clangd/CodeComplete.cpp

1072

implemented an initial version of this, no sourcelocation handling yet.

compute also takes the preamble we are patching though.

clang-tools-extra/clangd/Headers.cpp

237 ↗

(On Diff #254779)

the choice of raw lexer was more of a shortcut. i was just trying to get an initial version, tried to put some ideas in comments.

Will experiment with couple of options, but using alias mapping to map written includes to resolved absolute paths and also using the statcached vfs sounds like the best thing we can do for now.

We should also put this behind a "raw string equality" check to not perform any IO in the most common case(preamble is same).

Moreover, we can also put this logic into TUScheduler to not even perform string equality checks in case the contents haven't been modified. Not sure how useful that'll be though, as we usually receive a signaturehelp request after a modification to the source code.

[kadircet]

• Use preprocessor instead of raw lexer

[kadircet]

This is ready for another round. To summarize the current state:

• PreamblePatch can be create from a ParseInput and a PreambleData,
  • It will preprocessor preamble section of current file contents using a dummy FS to reduce cost of stat/realpaths
  • It won't populate Resolved path for inclusions, as we don't need them at this stage, and even later on. As we'll run the real preprocessor when building the ParsedAST, and we can collect resolved paths at that stage instead.
  • Afterwards it will diff the includes found in current contents with includes found in the PreambleData, and create a patch containing all the new includes
• PreamblePatch can be applied to a CompilerInvocation:
  • It is a no-op if contents are empty, i.e it was default constructed or there were no new includes.
  • Otherwise it will create an implicit include which contains patch created with new includes.

Things that I don't like about current state:

• We'll run processor to collect includes even when the preamble section of current file hasn't changed.
  • PrecompiledPreamble contains the contents of the preamble but it is not exposed, I suppose we can either expose that to get rid of extra preprocessor creation overhead.
• We create an extra CompilerInvocation and CompilerInstance just to run preprocessor and throw them away later on. I am not sure what to do about this :/

[sammccall]

This looks pretty good! Haven't reviewed the tests or removal of consistent preamble support yet. (Mostly note-to-self)

clang-tools-extra/clangd/Preamble.cpp

116

Given your getDecomposedTok before, you might want to assert Tok is in the main file inside the loop

127

I'd call this scanPreambleIncludes or something just slightly less generic - again here we don't want it to be accidentally reused for something that needs to be accurate.

149

Something needs to check that there's one input etc.
(This could maybe be moved into buildCompilerInvocation I guess, but currently the caller does it)

247

I'd stick to LexedIncludes or ApproxmimateIncludes or BaselineIncludes - it excludes stuff under ifdefs that *can* be resolved, and we don't want it to be used for other purposes...

277

I'm slightly nervous about incorporating the filename itself, not sure why but it feels unneccesary.
WDYT about "dir/__preamble_patch__.h"?

280

Why not a DenseSet<pair<PPKeywordKind, StringRef>>?
(The copies probably don't matter, but I think it'd be a bit clearer and more typesafe)

312

worth a comment indicating exactly where this is going to be inserted into the parsing stream.

clang-tools-extra/clangd/Preamble.h

71

Maybe "Used as a baseline for creating a PreamblePatch"?
Since this is a bit unusual.

73

Since computing these inclusions seems to be cheap (you've disabled all the IO), would it be clearer and more flexible to store the preamble text as a string and compute both the baseline & new includes at the same time?
I'm thinking if other preamble constructs (macros?) are added, needing to put more data structures in PreambleData, where if you store the text only those can be private details.

(In fact the preamble text is already stored in PrecompiledPreamble, you could just expose it there)

94

This is probably a good place for a high-level overview of the concept, and maybe an example.

In particular, *something* should mention that this is approximate, and what we use it for/don't use it for.

97

// With an empty patch, the preamble is used verbatim.

103

nit: it'd be good to give these "version"s names. e.g. PI -> Modified, Preamble -> Baseline. And maybe mention these in the class description?

104

This explanation is a little low-level, I'd add a first sentence explaining the goal.

e.g. "Adjusts CI (which compiles the modified inputs) to be used with the baseline preamble".

[kadircet]

clang-tools-extra/clangd/Preamble.cpp

277

it was done to get rid of path manipulations, but not that important.

280

PPKeywordKind didn't have a DenseMapInfo, adding one. It already has two invalid enum values.

clang-tools-extra/clangd/Preamble.h

73

since a preamble can be used with multiple preamble patches i wanted to reduce lexing overhead. I suppose we can address that later if it shows up in the traces. exposing the contents in PrecompiledPreamble.

[kadircet]

• Address comments
• Don't store LexedInclude in PreambleData, expose the contents in PrecompiledPreamble instead.
• Introduce DenseMapInfo for PPKeywordKind

[sammccall]

Great stuff!

clang-tools-extra/clangd/Preamble.cpp

128

The error-handling paths here just return {}, same as an empty preamble.

Results:
if both baseline & current fail, then we'll generate no patch --> fine
if baseline is ok and current fails, we'll consider all headers, we'll consider all headers removed and generate no new includes --> fine for now (added-includes-only model)
if baseline fails and current is OK, we'll create a patch that adds all the headers --> really slow, we'd be better off creating an empty patch

clarity and debuggability:
behaviors are implicit and silent. I think we should write out these three cases explicitly in the code, and log them at least at -log/verbose. These should be rare conditions I think. (If they're not, we should be able to track down & handle the common causes I think)

I think this function should probably return Expected.

280

Ugh, I thought enums had those implicitly. The need for two invalid values is really annoying, it's probably why we don't have more implicit ones.

I wonder whether it's feasible (technically and legally) to replace DenseHashMap with a fork of absl::flat_hash_map. I'm pretty sure it's faster, and it doesn't have these weird API requirements.

[sammccall]

Keep missing the "ship it" button...

[kadircet]

• Make scanPreambleIncludes return an Expected<std::vector<Inclusion>>
• Bail out in case of errors, document the rational.

[kadircet]

clang-tools-extra/clangd/Preamble.cpp

280

IANAL, but they both seemed to have apache v2 :D

as for technicalities, how hard can it be to replace one of the most basic data structures in a code base :P

clang-tools-extra/clangd/ClangdServer.cpp

auto Action = [Pos, FS = FSProvider.getFileSystem(), File = File.str(),
     if (!PreambleData)
       return CB(llvm::createStringError(llvm::inconvertibleErrorCode(),
                                         "Failed to parse includes"));
 
     CB(clangd::signatureHelp(File, IP->Command, *PreambleData, IP->Contents,
                              Pos, FS, Index));
   };
 
-  // Unlike code completion, we wait for an up-to-date preamble here.
-  // Signature help is often triggered after code completion. If the code
-  // completion inserted a header to make the symbol available, then using
-  // the old preamble would yield useless results.
-  WorkScheduler.runWithPreamble("SignatureHelp", File, TUScheduler::Consistent,
+  // Unlike code completion, we wait for a preamble here.
+  WorkScheduler.runWithPreamble("SignatureHelp", File, TUScheduler::Stale,
                                 std::move(Action));
 }
 
 llvm::Expected<tooling::Replacements>
 ClangdServer::formatRange(llvm::StringRef Code, PathRef File, Range Rng) {
   llvm::Expected<size_t> Begin = positionToOffset(Code, Rng.start);
   if (!Begin)
     return Begin.takeError();

clang-tools-extra/clangd/CodeComplete.cpp

private:
   CodeCompletionTUInfo CCTUInfo;
   const SymbolIndex *Index;
 }; // SignatureHelpCollector
 
 struct SemaCompleteInput {
   PathRef FileName;
   const tooling::CompileCommand &Command;
   const PreambleData &Preamble;
+  const PreamblePatch &PreamblePatch;
   llvm::StringRef Contents;
   size_t Offset;
   llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem> VFS;
 };
 
 void loadMainFilePreambleMacros(const Preprocessor &PP,
                                 const PreambleData &Preamble) {
   // The ExternalPreprocessorSource has our macros, if we know where to look.
bool semaCodeComplete(std::unique_ptr<CodeCompleteConsumer> Consumer,
   trace::Span Tracer("Sema completion");
   llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem> VFS = Input.VFS;
   if (Input.Preamble.StatCache)
     VFS = Input.Preamble.StatCache->getConsumingFS(std::move(VFS));
   ParseInputs ParseInput;
   ParseInput.CompileCommand = Input.Command;
   ParseInput.FS = VFS;
   ParseInput.Contents = std::string(Input.Contents);
-  ParseInput.Opts = ParseOptions();
 
   IgnoreDiagnostics IgnoreDiags;
   auto CI = buildCompilerInvocation(ParseInput, IgnoreDiags);
   if (!CI) {
     elog("Couldn't create CompilerInvocation");
     return false;
   }
   auto &FrontendOpts = CI->getFrontendOpts();
   FrontendOpts.SkipFunctionBodies = true;
   // Disable typo correction in Sema.
   CI->getLangOpts()->SpellChecking = false;
   // Code completion won't trigger in delayed template bodies.
   // This is on-by-default in windows to allow parsing SDK headers; we're only
   // disabling it for the main-file (not preamble).
   CI->getLangOpts()->DelayedTemplateParsing = false;
   // Setup code completion.
   FrontendOpts.CodeCompleteOpts = Options;
bool semaCodeComplete(std::unique_ptr<CodeCompleteConsumer> Consumer,
   // correctness/performance tradeoff: building without a preamble is slow, and
   // completion is latency-sensitive.
   // However, if we're completing *inside* the preamble section of the draft,
   // overriding the preamble will break sema completion. Fortunately we can just
   // skip all includes in this case; these completions are really simple.
   PreambleBounds PreambleRegion =
       ComputePreambleBounds(*CI->getLangOpts(), ContentsBuffer.get(), 0);
   bool CompletingInPreamble = PreambleRegion.Size > Input.Offset;
+  Input.PreamblePatch.apply(*CI);
   // NOTE: we must call BeginSourceFile after prepareCompilerInstance. Otherwise
   // the remapped buffers do not get freed.
   auto Clang = prepareCompilerInstance(
       std::move(CI), !CompletingInPreamble ? &Input.Preamble.Preamble : nullptr,
       std::move(ContentsBuffer), std::move(VFS), IgnoreDiags);
   Clang->getPreprocessorOpts().SingleFileParseMode = CompletingInPreamble;
   Clang->setCodeCompletionConsumer(Consumer.release());
 
if (!Offset) {
     elog("Code completion position was invalid {0}", Offset.takeError());
     return CodeCompleteResult();
   }
   auto Flow = CodeCompleteFlow(
       FileName, Preamble ? Preamble->Includes : IncludeStructure(),
       SpecFuzzyFind, Opts);
   return (!Preamble || Opts.RunParser == CodeCompleteOptions::NeverParse)
              ? std::move(Flow).runWithoutSema(Contents, *Offset, VFS)
-             : std::move(Flow).run(
-                   {FileName, Command, *Preamble, Contents, *Offset, VFS});
+             : std::move(Flow).run({FileName, Command, *Preamble,
+                                    // We want to serve code completions with
+                                    // low latency, so don't bother patching.
+                                    PreamblePatch(), Contents, *Offset, VFS});
 }
 
 SignatureHelp signatureHelp(PathRef FileName,
                             const tooling::CompileCommand &Command,
                             const PreambleData &Preamble,
                             llvm::StringRef Contents, Position Pos,
                             llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem> VFS,
                             const SymbolIndex *Index) {
   auto Offset = positionToOffset(Contents, Pos);
   if (!Offset) {
     elog("Code completion position was invalid {0}", Offset.takeError());
     return SignatureHelp();
   }
   SignatureHelp Result;
   clang::CodeCompleteOptions Options;
   Options.IncludeGlobals = false;
   Options.IncludeMacros = false;
   Options.IncludeCodePatterns = false;
   Options.IncludeBriefComments = false;
-  IncludeStructure PreambleInclusions; // Unused for signatureHelp
+
+  ParseInputs PI;
+  PI.CompileCommand = Command;
+  PI.Contents = Contents.str();
+  PI.FS = std::move(VFS);
+  auto PP = PreamblePatch::create(FileName, PI, Preamble);
   semaCodeComplete(
       std::make_unique<SignatureHelpCollector>(Options, Index, Result), Options,
-      {FileName, Command, Preamble, Contents, *Offset, std::move(VFS)});
+      {FileName, Command, Preamble, PP, Contents, *Offset, std::move(PI.FS)});
   return Result;
 }
 
 bool isIndexedForCodeCompletion(const NamedDecl &ND, ASTContext &ASTCtx) {
   auto InTopLevelScope = [](const NamedDecl &ND) {
     switch (ND.getDeclContext()->getDeclKind()) {
     case Decl::TranslationUnit:
     case Decl::Namespace:

clang-tools-extra/clangd/Preamble.h

 #include "Diagnostics.h"
 #include "FS.h"
 #include "Headers.h"
 #include "Path.h"
 #include "index/CanonicalIncludes.h"
 #include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Frontend/PrecompiledPreamble.h"
 #include "clang/Tooling/CompilationDatabase.h"
+#include "llvm/ADT/StringRef.h"
 
 #include <memory>
 #include <string>
 #include <vector>
 
 namespace clang {
 namespace clangd {
 
struct PreambleData {
   // Macros defined in the preamble section of the main file.
   // Users care about headers vs main-file, not preamble vs non-preamble.
   // These should be treated as main-file entities e.g. for code completion.
   MainFileMacros Macros;
   // Cache of FS operations performed when building the preamble.
   // When reusing a preamble, this cache can be consumed to save IO.
   std::unique_ptr<PreambleFileStatusCache> StatCache;
   CanonicalIncludes CanonIncludes;
 };
 
 using PreambleParsedCallback =
     std::function<void(ASTContext &, std::shared_ptr<clang::Preprocessor>,
                        const CanonicalIncludes &)>;
 
 /// Build a preamble for the new inputs unless an old one can be reused.
 /// If \p PreambleCallback is set, it will be run on top of the AST while
 /// building the preamble.
 std::shared_ptr<const PreambleData>
 buildPreamble(PathRef FileName, CompilerInvocation CI,
               const ParseInputs &Inputs, bool StoreInMemory,
               PreambleParsedCallback PreambleCallback);
 
 /// Returns true if \p Preamble is reusable for \p Inputs. Note that it will
 /// return true when some missing headers are now available.
 /// FIXME: Should return more information about the delta between \p Preamble
 /// and \p Inputs, e.g. new headers.
 bool isPreambleCompatible(const PreambleData &Preamble,
                           const ParseInputs &Inputs, PathRef FileName,
                           const CompilerInvocation &CI);
+
+/// Stores information required to parse a TU using a (possibly stale) Baseline
+/// preamble. Updates compiler invocation to approximately reflect additions to
+/// the preamble section of Modified contents, e.g. new include directives.
+class PreamblePatch {
+public:
+  // With an empty patch, the preamble is used verbatim.
+  PreamblePatch() = default;
+  /// Builds a patch that contains new PP directives introduced to the preamble
+  /// section of \p Modified compared to \p Baseline.
+  /// FIXME: This only handles include directives, we should at least handle
+  /// define/undef.
+  static PreamblePatch create(llvm::StringRef FileName,
+                              const ParseInputs &Modified,
+                              const PreambleData &Baseline);
+  /// Adjusts CI (which compiles the modified inputs) to be used with the
+  /// baseline preamble. This is done by inserting an artifical include to the
+  /// \p CI that contains new directives calculated in create.
+  void apply(CompilerInvocation &CI) const;
+
+private:
+  std::string PatchContents;
+  std::string PatchFileName;
+};
+
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_PREAMBLE_H

clang-tools-extra/clangd/Preamble.cpp

 //===--- Preamble.cpp - Reusing expensive parts of the AST ----------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "Preamble.h"
 #include "Compiler.h"
+#include "Headers.h"
 #include "Logger.h"
 #include "Trace.h"
+#include "clang/Basic/Diagnostic.h"
+#include "clang/Basic/LangOptions.h"
 #include "clang/Basic/SourceLocation.h"
+#include "clang/Basic/TokenKinds.h"
+#include "clang/Frontend/CompilerInvocation.h"
+#include "clang/Frontend/FrontendActions.h"
+#include "clang/Lex/Lexer.h"
 #include "clang/Lex/PPCallbacks.h"
+#include "clang/Lex/Preprocessor.h"
 #include "clang/Lex/PreprocessorOptions.h"
+#include "clang/Tooling/CompilationDatabase.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/IntrusiveRefCntPtr.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/StringSet.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/FormatVariadic.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/Path.h"
+#include "llvm/Support/VirtualFileSystem.h"
+#include "llvm/Support/raw_ostream.h"
+#include <iterator>
+#include <memory>
+#include <string>
+#include <system_error>
+#include <utility>
+#include <vector>
 
 namespace clang {
 namespace clangd {
 namespace {
 
 bool compileCommandsAreEqual(const tooling::CompileCommand &LHS,
                              const tooling::CompileCommand &RHS) {
   // We don't check for Output, it should not matter to clangd.
private:
   IncludeStructure Includes;
   CanonicalIncludes CanonIncludes;
   MainFileMacros Macros;
   std::unique_ptr<CommentHandler> IWYUHandler = nullptr;
   const clang::LangOptions *LangOpts = nullptr;
   const SourceManager *SourceMgr = nullptr;
 };
 
+// Runs preprocessor over preamble section.
+class PreambleOnlyAction : public PreprocessorFrontendAction {
+protected:
+  void ExecuteAction() override {
+    Preprocessor &PP = getCompilerInstance().getPreprocessor();
+    auto &SM = PP.getSourceManager();
+    PP.EnterMainSourceFile();
+    auto Bounds = ComputePreambleBounds(getCompilerInstance().getLangOpts(),
+                                        SM.getBuffer(SM.getMainFileID()), 0);
+    Token Tok;
+    do {
+      PP.Lex(Tok);
+      assert(SM.isInMainFile(Tok.getLocation()));
+    } while (Tok.isNot(tok::eof) &&
+             SM.getDecomposedLoc(Tok.getLocation()).second < Bounds.Size);
+  }
+};
+
+/// Gets the includes in the preamble section of the file by running
+/// preprocessor over \p Contents. Returned includes do not contain resolved
+/// paths. \p VFS and \p Cmd is used to build the compiler invocation, which
+/// might stat/read files.
+std::vector<Inclusion>
+scanPreambleIncludes(llvm::StringRef Contents,
+                     llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem> VFS,
+                     const tooling::CompileCommand &Cmd) {
+  // Build and run Preprocessor over the preamble.
+  ParseInputs PI;
+  PI.Contents = Contents.str();
+  PI.FS = std::move(VFS);
+  PI.CompileCommand = Cmd;
+  IgnoringDiagConsumer IgnoreDiags;
+  auto CI = buildCompilerInvocation(PI, IgnoreDiags);
+  if (!CI)
+    return {};
+  CI->getDiagnosticOpts().IgnoreWarnings = true;
+  auto ContentsBuffer = llvm::MemoryBuffer::getMemBuffer(Contents);
+  auto Clang = prepareCompilerInstance(
+      std::move(CI), nullptr, std::move(ContentsBuffer),
+      // Provide an empty FS to prevent preprocessor from performing IO. This
+      // also implies missing resolved paths for includes.
+      new llvm::vfs::InMemoryFileSystem, IgnoreDiags);
+  // We are only interested in main file includes.
+  Clang->getPreprocessorOpts().SingleFileParseMode = true;
+  PreambleOnlyAction Action;
+  if (Clang->getFrontendOpts().Inputs.empty())
+    return {};
+  if (!Action.BeginSourceFile(*Clang, Clang->getFrontendOpts().Inputs[0]))
+    return {};
+  Preprocessor &PP = Clang->getPreprocessor();
+  IncludeStructure Includes;
+  PP.addPPCallbacks(
+      collectIncludeStructureCallback(Clang->getSourceManager(), &Includes));
+  if (llvm::Error Err = Action.Execute()) {
+    elog("Failed to run include collection: {0}", toString(std::move(Err)));
+    return {};
+  }
+  Action.EndSourceFile();
+  return Includes.MainFileIncludes;
+}
+
+const char *spellingForIncDirective(tok::PPKeywordKind IncludeDirective) {
+  switch (IncludeDirective) {
+  case tok::pp_include:
+    return "include";
+  case tok::pp_import:
+    return "import";
+  case tok::pp_include_next:
+    return "include_next";
+  default:
+    break;
+  }
+  llvm_unreachable("not an include directive");
+}
 } // namespace
 
 PreambleData::PreambleData(const ParseInputs &Inputs,
                            PrecompiledPreamble Preamble,
                            std::vector<Diag> Diags, IncludeStructure Includes,
                            MainFileMacros Macros,
                            std::unique_ptr<PreambleFileStatusCache> StatCache,
                            CanonicalIncludes CanonIncludes)
buildPreamble(PathRef FileName, CompilerInvocation CI,
   // When building the AST for the main file, we do want the function
   // bodies.
   CI.getFrontendOpts().SkipFunctionBodies = false;
 
   if (BuiltPreamble) {
     vlog("Built preamble of size {0} for file {1} version {2}",
          BuiltPreamble->getSize(), FileName, Inputs.Version);
     std::vector<Diag> Diags = PreambleDiagnostics.take();
     return std::make_shared<PreambleData>(
         Inputs, std::move(*BuiltPreamble), std::move(Diags),
         SerializedDeclsCollector.takeIncludes(),
         SerializedDeclsCollector.takeMacros(), std::move(StatCache),
         SerializedDeclsCollector.takeCanonicalIncludes());
   } else {
     elog("Could not build a preamble for file {0} version {1}", FileName,
          Inputs.Version);
     return nullptr;
   }
 }
 
 bool isPreambleCompatible(const PreambleData &Preamble,
                           const ParseInputs &Inputs, PathRef FileName,
                           const CompilerInvocation &CI) {
   auto ContentsBuffer =
       llvm::MemoryBuffer::getMemBuffer(Inputs.Contents, FileName);
   auto Bounds =
       ComputePreambleBounds(*CI.getLangOpts(), ContentsBuffer.get(), 0);
   return compileCommandsAreEqual(Inputs.CompileCommand,
                                  Preamble.CompileCommand) &&
          Preamble.Preamble.CanReuse(CI, ContentsBuffer.get(), Bounds,
                                     Inputs.FS.get());
 }
+
+PreamblePatch PreamblePatch::create(llvm::StringRef FileName,
+                                    const ParseInputs &Modified,
+                                    const PreambleData &Baseline) {
+  PreamblePatch PP;
+  // This shouldn't coincide with any real file name.
+  llvm::SmallString<128> PatchName;
+  llvm::sys::path::append(PatchName, llvm::sys::path::parent_path(FileName),
+                          "__preamble_patch__.h");
+  PP.PatchFileName = PatchName.str().str();
+
+  // We are only interested in newly added includes.
+  llvm::DenseSet<std::pair<tok::PPKeywordKind, llvm::StringRef>>
+      ExistingIncludes;
+  auto PreambleIncludes = scanPreambleIncludes(
+      // Contents needs to be null-terminated.
+      Baseline.Preamble.getContents().str(),
+      Baseline.StatCache->getConsumingFS(Modified.FS), Modified.CompileCommand);
+  for (const auto &Inc : PreambleIncludes)
+    ExistingIncludes.insert({Inc.Directive, Inc.Written});
+
+  // Calculate extra includes that needs to be inserted.
+  llvm::raw_string_ostream Patch(PP.PatchContents);
+  for (const auto &Inc : scanPreambleIncludes(
+           Modified.Contents, Baseline.StatCache->getConsumingFS(Modified.FS),
+           Modified.CompileCommand)) {
+    if (ExistingIncludes.count({Inc.Directive, Inc.Written}))
+      continue;
+    Patch << llvm::formatv("#{0} {1}\n", spellingForIncDirective(Inc.Directive),
+                           Inc.Written);
+  }
+  Patch.flush();
+  // FIXME: Handle more directives, e.g. define/undef.
+  return PP;
+}
+
+void PreamblePatch::apply(CompilerInvocation &CI) const {
+  // No need to map an empty file.
+  if (PatchContents.empty())
+    return;
+  auto &PPOpts = CI.getPreprocessorOpts();
+  auto PatchBuffer =
+      // we copy here to ensure contents are still valid if CI outlives the
+      // PreamblePatch.
+      llvm::MemoryBuffer::getMemBufferCopy(PatchContents, PatchFileName);
+  // CI will take care of the lifetime of the buffer.
+  PPOpts.addRemappedFile(PatchFileName, PatchBuffer.release());
+  // The patch will be parsed after loading the preamble ast and before parsing
+  // the main file.
+  PPOpts.Includes.push_back(PatchFileName);
+}
+
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/TUScheduler.h

public:
   /// If the context is cancelled before the AST is ready, or the invalidation
   /// policy is triggered, the callback will receive a CancelledError.
   void runWithAST(llvm::StringRef Name, PathRef File,
                   Callback<InputsAndAST> Action,
                   ASTActionInvalidation = NoInvalidation);
 
   /// Controls whether preamble reads wait for the preamble to be up-to-date.
   enum PreambleConsistency {
-    /// The preamble is generated from the current version of the file.
-    /// If the content was recently updated, we will wait until we have a
-    /// preamble that reflects that update.
-    /// This is the slowest option, and may be delayed by other tasks.
-    Consistent,
     /// The preamble may be generated from an older version of the file.
     /// Reading from locations in the preamble may cause files to be re-read.
     /// This gives callers two options:
     /// - validate that the preamble is still valid, and only use it if so
     /// - accept that the preamble contents may be outdated, and try to avoid
     ///   reading source code from headers.
     /// This is the fastest option, usually a preamble is available immediately.
     Stale,

clang-tools-extra/clangd/TUScheduler.cpp

 }
 
 std::shared_ptr<const PreambleData>
 ASTWorker::getPossiblyStalePreamble() const {
   std::lock_guard<std::mutex> Lock(Mutex);
   return LatestPreamble;
 }
 
-void ASTWorker::getCurrentPreamble(
-    llvm::unique_function<void(std::shared_ptr<const PreambleData>)> Callback) {
-  // We could just call startTask() to throw the read on the queue, knowing
-  // it will run after any updates. But we know this task is cheap, so to
-  // improve latency we cheat: insert it on the queue after the last update.
-  std::unique_lock<std::mutex> Lock(Mutex);
-  auto LastUpdate =
-      std::find_if(Requests.rbegin(), Requests.rend(),
-                   [](const Request &R) { return R.UpdateType.hasValue(); });
-  // If there were no writes in the queue, and CurrentRequest is not a write,
-  // the preamble is ready now.
-  if (LastUpdate == Requests.rend() &&
-      (!CurrentRequest || CurrentRequest->UpdateType.hasValue())) {
-    Lock.unlock();
-    return Callback(getPossiblyStalePreamble());
-  }
-  assert(!RunSync && "Running synchronously, but queue is non-empty!");
-  Requests.insert(LastUpdate.base(),
-                  Request{[Callback = std::move(Callback), this]() mutable {
-                            Callback(getPossiblyStalePreamble());
-                          },
-                          "GetPreamble", steady_clock::now(),
-                          Context::current().clone(),
-                          /*UpdateType=*/None,
-                          /*InvalidationPolicy=*/TUScheduler::NoInvalidation,
-                          /*Invalidate=*/nullptr});
-  Lock.unlock();
-  RequestsCV.notify_all();
-}
-
 void ASTWorker::waitForFirstPreamble() const { BuiltFirstPreamble.wait(); }
 
 tooling::CompileCommand ASTWorker::getCurrentCompileCommand() const {
   std::unique_lock<std::mutex> Lock(Mutex);
   return FileInputs.CompileCommand;
 }
 
 TUScheduler::FileStats ASTWorker::stats() const {
if (!PreambleTasks) {
     std::shared_ptr<const PreambleData> Preamble =
         It->second->Worker->getPossiblyStalePreamble();
     Action(InputsAndPreamble{It->second->Contents,
                              It->second->Worker->getCurrentCompileCommand(),
                              Preamble.get()});
     return;
   }
 
-  // Future is populated if the task needs a specific preamble.
-  std::future<std::shared_ptr<const PreambleData>> ConsistentPreamble;
-  // FIXME: Currently this only holds because ASTWorker blocks after issuing a
-  // preamble build. Get rid of consistent reads or make them build on the
-  // calling thread instead.
-  if (Consistency == Consistent) {
-    std::promise<std::shared_ptr<const PreambleData>> Promise;
-    ConsistentPreamble = Promise.get_future();
-    It->second->Worker->getCurrentPreamble(
-        [Promise = std::move(Promise)](
-            std::shared_ptr<const PreambleData> Preamble) mutable {
-          Promise.set_value(std::move(Preamble));
-        });
-  }
-
   std::shared_ptr<const ASTWorker> Worker = It->second->Worker.lock();
   auto Task =
       [Worker, Consistency, Name = Name.str(), File = File.str(),
        Contents = It->second->Contents,
        Command = Worker->getCurrentCompileCommand(),
        Ctx = Context::current().derive(kFileBeingProcessed, std::string(File)),
-       ConsistentPreamble = std::move(ConsistentPreamble),
        Action = std::move(Action), this]() mutable {
         std::shared_ptr<const PreambleData> Preamble;
-        if (ConsistentPreamble.valid()) {
-          Preamble = ConsistentPreamble.get();
-        } else {
-          if (Consistency != PreambleConsistency::StaleOrAbsent) {
-            // Wait until the preamble is built for the first time, if preamble
-            // is required. This avoids extra work of processing the preamble
-            // headers in parallel multiple times.
-            Worker->waitForFirstPreamble();
-          }
-          Preamble = Worker->getPossiblyStalePreamble();
-        }
+        if (Consistency == PreambleConsistency::Stale) {
 
         std::lock_guard<Semaphore> BarrierLock(Barrier);
         WithContext Guard(std::move(Ctx));
         trace::Span Tracer(Name);
         SPAN_ATTACH(Tracer, "file", File);
         Action(InputsAndPreamble{Contents, Command, Preamble.get()});
       };
 

clang-tools-extra/clangd/unittests/CMakeLists.txt

add_unittest(ClangdUnitTests ClangdTests
   HeaderSourceSwitchTests.cpp
   HoverTests.cpp
   IndexActionTests.cpp
   IndexTests.cpp
   JSONTransportTests.cpp
   LSPClient.cpp
   ParsedASTTests.cpp
   PathMappingTests.cpp
+  PreambleTests.cpp
   PrintASTTests.cpp
   QualityTests.cpp
   RenameTests.cpp
   RIFFTests.cpp
   SelectionTests.cpp
   SemanticHighlightingTests.cpp
   SemanticSelectionTests.cpp
   SerializationTests.cpp

clang-tools-extra/clangd/unittests/CodeCompleteTests.cpp

TEST(SignatureHelpTest, OpeningParen) {
   for (auto Test : Tests) {
     Annotations Code(Test);
     EXPECT_EQ(signatures(Code.code(), Code.point()).argListStart,
               Code.point("p"))
         << "Test source:" << Test;
   }
 }
 
+TEST(SignatureHelpTest, StalePreamble) {
+  TestTU TU;
+  TU.Code = "";
+  IgnoreDiagnostics Diags;
+  auto Inputs = TU.inputs();
+  auto CI = buildCompilerInvocation(Inputs, Diags);
+  ASSERT_TRUE(CI);
+  auto EmptyPreamble = buildPreamble(testPath(TU.Filename), *CI, Inputs,
+                                     /*InMemory=*/true, /*Callback=*/nullptr);
+  ASSERT_TRUE(EmptyPreamble);
+
+  TU.AdditionalFiles["a.h"] = "int foo(int x);";
+  const Annotations Test(R"cpp(
+    #include "a.h"
+    void bar() { foo(^2); })cpp");
+  TU.Code = Test.code().str();
+  Inputs = TU.inputs();
+  auto Results =
+      signatureHelp(testPath(TU.Filename), Inputs.CompileCommand,
+                    *EmptyPreamble, TU.Code, Test.point(), Inputs.FS, nullptr);
+  EXPECT_THAT(Results.signatures, ElementsAre(Sig("foo([[int x]]) -> int")));
+  EXPECT_EQ(0, Results.activeSignature);
+  EXPECT_EQ(0, Results.activeParameter);
+}
+
 class IndexRequestCollector : public SymbolIndex {
 public:
   bool
   fuzzyFind(const FuzzyFindRequest &Req,
             llvm::function_ref<void(const Symbol &)> Callback) const override {
     std::unique_lock<std::mutex> Lock(Mut);
     Requests.push_back(Req);
     ReceivedRequestCV.notify_one();

clang-tools-extra/clangd/unittests/PreambleTests.cpp

+//===--- PreambleTests.cpp --------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "Annotations.h"
+#include "Compiler.h"
+#include "Preamble.h"
+#include "TestFS.h"
+#include "clang/Lex/PreprocessorOptions.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/StringRef.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include <string>
+#include <vector>
+
+namespace clang {
+namespace clangd {
+namespace {
+
+using testing::_;
+using testing::Contains;
+using testing::Pair;
+
+MATCHER_P(HasContents, Contents, "") { return arg->getBuffer() == Contents; }
+
+TEST(PreamblePatchTest, IncludeParsing) {
+  MockFSProvider FS;
+  MockCompilationDatabase CDB;
+  IgnoreDiagnostics Diags;
+  ParseInputs PI;
+  PI.FS = FS.getFileSystem();
+
+  // We expect any line with a point to show up in the patch.
+  llvm::StringRef Cases[] = {
+      // Only preamble
+      R"cpp(^#include "a.h")cpp",
+      // Both preamble and mainfile
+      R"cpp(
+        ^#include "a.h"
+        garbage, finishes preamble
+        #include "a.h")cpp",
+      // Mixed directives
+      R"cpp(
+        ^#include "a.h"
+        #pragma directive
+        // some comments
+        ^#include_next <a.h>
+        #ifdef skipped
+        ^#import "a.h"
+        #endif)cpp",
+      // Broken directives
+      R"cpp(
+        #include "a
+        ^#include "a.h"
+        #include <b
+        ^#include <b.h>)cpp",
+  };
+
+  const auto FileName = testPath("foo.cc");
+  for (const auto Case : Cases) {
+    Annotations Test(Case);
+    const auto Code = Test.code();
+    PI.CompileCommand = *CDB.getCompileCommand(FileName);
+
+    SCOPED_TRACE(Code);
+    // Check preamble lexing logic by building an empty preamble and patching it
+    // with all the contents.
+    PI.Contents = "";
+    const auto CI = buildCompilerInvocation(PI, Diags);
+    const auto EmptyPreamble = buildPreamble(FileName, *CI, PI, true, nullptr);
+    PI.Contents = Code.str();
+
+    std::string ExpectedBuffer;
+    const auto Points = Test.points();
+    for (const auto &P : Points) {
+      // Copy the whole line.
+      auto StartOffset = llvm::cantFail(positionToOffset(Code, P));
+      ExpectedBuffer.append(Code.substr(StartOffset)
+                                .take_until([](char C) { return C == '\n'; })
+                                .str());
+      ExpectedBuffer += '\n';
+    }
+
+    PreamblePatch::create(FileName, PI, *EmptyPreamble).apply(*CI);
+    EXPECT_THAT(CI->getPreprocessorOpts().RemappedFileBuffers,
+                Contains(Pair(_, HasContents(ExpectedBuffer))));
+  }
+}
+
+TEST(PreamblePatchTest, ContainsNewIncludes) {
+  MockFSProvider FS;
+  MockCompilationDatabase CDB;
+  IgnoreDiagnostics Diags;
+
+  const auto FileName = testPath("foo.cc");
+  ParseInputs PI;
+  PI.FS = FS.getFileSystem();
+  PI.CompileCommand = *CDB.getCompileCommand(FileName);
+  PI.Contents = "#include <existing.h>\n";
+
+  // Check diffing logic by adding a new header to the preamble and ensuring
+  // only it is patched.
+  const auto CI = buildCompilerInvocation(PI, Diags);
+  const auto FullPreamble = buildPreamble(FileName, *CI, PI, true, nullptr);
+
+  constexpr llvm::StringLiteral Patch =
+      "#include <test>\n#import <existing.h>\n";
+  // We provide the same includes twice, they shouldn't be included in the
+  // patch.
+  PI.Contents = (Patch + PI.Contents + PI.Contents).str();
+  PreamblePatch::create(FileName, PI, *FullPreamble).apply(*CI);
+  EXPECT_THAT(CI->getPreprocessorOpts().RemappedFileBuffers,
+              Contains(Pair(_, HasContents(Patch))));
+}
+
+} // namespace
+} // namespace clangd
+} // namespace clang

clang-tools-extra/clangd/unittests/TUSchedulerTests.cpp

std::atomic<int> CallbackCount(0);
     updateWithDiags(S, Path, "auto (shut down)", WantDiagnostics::Auto,
                     [&](std::vector<Diag>) { ++CallbackCount; });
 
     ASSERT_TRUE(S.blockUntilIdle(timeoutSeconds(10)));
   }
   EXPECT_EQ(2, CallbackCount);
 }
 
-static std::vector<std::string> includes(const PreambleData *Preamble) {
-  std::vector<std::string> Result;
-  if (Preamble)
-    for (const auto &Inclusion : Preamble->Includes.MainFileIncludes)
-      Result.push_back(Inclusion.Written);
-  return Result;
-}
-
-TEST_F(TUSchedulerTests, PreambleConsistency) {
-  std::atomic<int> CallbackCount(0);
-  {
-    Notification InconsistentReadDone; // Must live longest.
-    TUScheduler S(CDB, optsForTest());
-    auto Path = testPath("foo.cpp");
-    // Schedule two updates (A, B) and two preamble reads (stale, consistent).
-    // The stale read should see A, and the consistent read should see B.
-    // (We recognize the preambles by their included files).
-    auto Inputs = getInputs(Path, "#include <A>");
-    Inputs.Version = "A";
-    updateWithCallback(S, Path, Inputs, WantDiagnostics::Yes, [&]() {
-      // This callback runs in between the two preamble updates.
-
-      // This blocks update B, preventing it from winning the race
-      // against the stale read.
-      // If the first read was instead consistent, this would deadlock.
-      InconsistentReadDone.wait();
-      // This delays update B, preventing it from winning a race
-      // against the consistent read. The consistent read sees B
-      // only because it waits for it.
-      // If the second read was stale, it would usually see A.
-      std::this_thread::sleep_for(std::chrono::milliseconds(100));
-    });
-    Inputs.Contents = "#include <B>";
-    Inputs.Version = "B";
-    S.update(Path, Inputs, WantDiagnostics::Yes);
-
-    S.runWithPreamble("StaleRead", Path, TUScheduler::Stale,
-                      [&](Expected<InputsAndPreamble> Pre) {
-                        ASSERT_TRUE(bool(Pre));
-                        ASSERT_TRUE(Pre->Preamble);
-                        EXPECT_EQ(Pre->Preamble->Version, "A");
-                        EXPECT_THAT(includes(Pre->Preamble),
-                                    ElementsAre("<A>"));
-                        InconsistentReadDone.notify();
-                        ++CallbackCount;
-                      });
-    S.runWithPreamble("ConsistentRead", Path, TUScheduler::Consistent,
-                      [&](Expected<InputsAndPreamble> Pre) {
-                        ASSERT_TRUE(bool(Pre));
-                        ASSERT_TRUE(Pre->Preamble);
-                        EXPECT_EQ(Pre->Preamble->Version, "B");
-                        EXPECT_THAT(includes(Pre->Preamble),
-                                    ElementsAre("<B>"));
-                        ++CallbackCount;
-                      });
-    S.blockUntilIdle(timeoutSeconds(10));
-  }
-  EXPECT_EQ(2, CallbackCount);
-}
-
 TEST_F(TUSchedulerTests, Cancellation) {
   // We have the following update/read sequence
   //   U0
   //   U1(WantDiags=Yes) <-- cancelled
   //    R1               <-- cancelled
   //   U2(WantDiags=Yes) <-- cancelled
   //    R2A              <-- cancelled
   //    R2B

clang/include/clang/Basic/TokenKinds.h

 //===--- TokenKinds.h - Enum values for C Token Kinds -----------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 /// Defines the clang::TokenKind enum and support functions.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_BASIC_TOKENKINDS_H
 #define LLVM_CLANG_BASIC_TOKENKINDS_H
 
+#include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/Support/Compiler.h"
 
 namespace clang {
 
 namespace tok {
 
 /// Provides a simple uniform namespace for tokens from all C languages.
 enum TokenKind : unsigned short {

 }
 
 /// Return true if this is any of tok::annot_* kinds.
 bool isAnnotation(TokenKind K);
 
 /// Return true if this is an annotation token representing a pragma.
 bool isPragmaAnnotation(TokenKind K);
 
-}  // end namespace tok
-}  // end namespace clang
+} // end namespace tok
+} // end namespace clang
 
+namespace llvm {
+template <> struct DenseMapInfo<clang::tok::PPKeywordKind> {
+  static inline clang::tok::PPKeywordKind getEmptyKey() {
+    return clang::tok::PPKeywordKind::pp_not_keyword;
+  }
+  static inline clang::tok::PPKeywordKind getTombstoneKey() {
+    return clang::tok::PPKeywordKind::NUM_PP_KEYWORDS;
+  }
+  static unsigned getHashValue(const clang::tok::PPKeywordKind &Val) {
+    return static_cast<unsigned>(Val);
+  }
+  static bool isEqual(const clang::tok::PPKeywordKind &LHS,
+                      const clang::tok::PPKeywordKind &RHS) {
+    return LHS == RHS;
+  }
+};
+} // namespace llvm
+
 #endif

clang/include/clang/Frontend/PrecompiledPreamble.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_FRONTEND_PRECOMPILED_PREAMBLE_H
 #define LLVM_CLANG_FRONTEND_PRECOMPILED_PREAMBLE_H
 
 #include "clang/Lex/Lexer.h"
 #include "clang/Lex/Preprocessor.h"
 #include "llvm/ADT/IntrusiveRefCntPtr.h"
+#include "llvm/ADT/StringRef.h"
 #include "llvm/Support/AlignOf.h"
 #include "llvm/Support/MD5.h"
 #include <cstddef>
 #include <memory>
 #include <system_error>
 #include <type_traits>
 
 namespace llvm {
public:
   /// PreambleBounds used to build the preamble.
   PreambleBounds getBounds() const;
 
   /// Returns the size, in bytes, that preamble takes on disk or in memory.
   /// For on-disk preambles returns 0 if filesystem operations fail. Intended to
   /// be used for logging and debugging purposes only.
   std::size_t getSize() const;
 
+  /// Returned string is not null-terminated.
+  llvm::StringRef getContents() const {
+    return {PreambleBytes.data(), PreambleBytes.size()};
+  }
+
   /// Check whether PrecompiledPreamble can be reused for the new contents(\p
   /// MainFileBuffer) of the main file.
   bool CanReuse(const CompilerInvocation &Invocation,
                 const llvm::MemoryBuffer *MainFileBuffer, PreambleBounds Bounds,
                 llvm::vfs::FileSystem *VFS) const;
 
   /// Changes options inside \p CI to use PCH from this preamble. Also remaps
   /// main file to \p MainFileBuffer and updates \p VFS to ensure the preamble