clang-tools-extra/clangd/GlobalCompilationDatabase.cpp

   1 //===--- GlobalCompilationDatabase.cpp ---------------------------*- C++-*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "GlobalCompilationDatabase.h"
  10 #include "Config.h"
  11 #include "FS.h"
  12 #include "SourceCode.h"
  13 #include "support/Logger.h"
  14 #include "support/Path.h"
  15 #include "support/Threading.h"
  16 #include "support/ThreadsafeFS.h"
  17 #include "clang/Tooling/ArgumentsAdjusters.h"
  18 #include "clang/Tooling/CompilationDatabase.h"
  19 #include "clang/Tooling/CompilationDatabasePluginRegistry.h"
  20 #include "clang/Tooling/JSONCompilationDatabase.h"
  21 #include "llvm/ADT/PointerIntPair.h"
  22 #include "llvm/ADT/STLExtras.h"
  23 #include "llvm/ADT/ScopeExit.h"
  24 #include "llvm/ADT/SmallString.h"
  25 #include "llvm/ADT/StringMap.h"
  26 #include "llvm/Support/Path.h"
  27 #include "llvm/Support/VirtualFileSystem.h"
  28 #include <atomic>
  29 #include <chrono>
  30 #include <condition_variable>
  31 #include <mutex>
  32 #include <optional>
  33 #include <string>
  34 #include <tuple>
  35 #include <vector>
  36
  37 namespace clang {
  38 namespace clangd {
  39 namespace {
  40
  41 // Runs the given action on all parent directories of filename, starting from
  42 // deepest directory and going up to root. Stops whenever action succeeds.
  43 void actOnAllParentDirectories(PathRef FileName,
  44                                llvm::function_ref<bool(PathRef)> Action) {
  45   for (auto Path = absoluteParent(FileName); !Path.empty() && !Action(Path);
  46        Path = absoluteParent(Path))
  47     ;
  48 }
  49
  50 } // namespace
  51
  52 tooling::CompileCommand
  53 GlobalCompilationDatabase::getFallbackCommand(PathRef File) const {
  54   std::vector<std::string> Argv = {"clang"};
  55   // Clang treats .h files as C by default and files without extension as linker
  56   // input, resulting in unhelpful diagnostics.
  57   // Parsing as Objective C++ is friendly to more cases.
  58   auto FileExtension = llvm::sys::path::extension(File);
  59   if (FileExtension.empty() || FileExtension == ".h")
  60     Argv.push_back("-xobjective-c++-header");
  61   Argv.push_back(std::string(File));
  62   tooling::CompileCommand Cmd(llvm::sys::path::parent_path(File),
  63                               llvm::sys::path::filename(File), std::move(Argv),
  64                               /*Output=*/"");
  65   Cmd.Heuristic = "clangd fallback";
  66   return Cmd;
  67 }
  68
  69 // Loads and caches the CDB from a single directory.
  70 //
  71 // This class is threadsafe, which is to say we have independent locks for each
  72 // directory we're searching for a CDB.
  73 // Loading is deferred until first access.
  74 //
  75 // The DirectoryBasedCDB keeps a map from path => DirectoryCache.
  76 // Typical usage is to:
  77 //  - 1) determine all the paths that might be searched
  78 //  - 2) acquire the map lock and get-or-create all the DirectoryCache entries
  79 //  - 3) release the map lock and query the caches as desired
  80 class DirectoryBasedGlobalCompilationDatabase::DirectoryCache {
  81   using stopwatch = std::chrono::steady_clock;
  82
  83   // CachedFile is used to read a CDB file on disk (e.g. compile_commands.json).
  84   // It specializes in being able to quickly bail out if the file is unchanged,
  85   // which is the common case.
  86   // Internally, it stores file metadata so a stat() can verify it's unchanged.
  87   // We don't actually cache the content as it's not needed - if the file is
  88   // unchanged then the previous CDB is valid.
  89   struct CachedFile {
  90     CachedFile(llvm::StringRef Parent, llvm::StringRef Rel) {
  91       llvm::SmallString<256> Path = Parent;
  92       llvm::sys::path::append(Path, Rel);
  93       this->Path = Path.str().str();
  94     }
  95     std::string Path;
  96     size_t Size = NoFileCached;
  97     llvm::sys::TimePoint<> ModifiedTime;
  98     FileDigest ContentHash;
  99
 100     static constexpr size_t NoFileCached = -1;
 101
 102     struct LoadResult {
 103       enum {
 104         FileNotFound,
 105         TransientError,
 106         FoundSameData,
 107         FoundNewData,
 108       } Result;
 109       std::unique_ptr<llvm::MemoryBuffer> Buffer; // Set only if FoundNewData
 110     };
 111
 112     LoadResult load(llvm::vfs::FileSystem &FS, bool HasOldData);
 113   };
 114
 115   // If we've looked for a CDB here and found none, the time when that happened.
 116   // (Atomics make it possible for get() to return without taking a lock)
 117   std::atomic<stopwatch::rep> NoCDBAt = {
 118       stopwatch::time_point::min().time_since_epoch().count()};
 119
 120   // Guards the following cache state.
 121   std::mutex Mu;
 122   // When was the cache last known to be in sync with disk state?
 123   stopwatch::time_point CachePopulatedAt = stopwatch::time_point::min();
 124   // Whether a new CDB has been loaded but not broadcast yet.
 125   bool NeedsBroadcast = false;
 126   // Last loaded CDB, meaningful if CachePopulatedAt was ever set.
 127   // shared_ptr so we can overwrite this when callers are still using the CDB.
 128   std::shared_ptr<tooling::CompilationDatabase> CDB;
 129   // File metadata for the CDB files we support tracking directly.
 130   CachedFile CompileCommandsJson;
 131   CachedFile BuildCompileCommandsJson;
 132   CachedFile CompileFlagsTxt;
 133   // CachedFile member corresponding to CDB.
 134   //   CDB  | ACF  | Scenario
 135   //   null | null | no CDB found, or initial empty cache
 136   //   set  | null | CDB was loaded via generic plugin interface
 137   //   null | set  | found known CDB file, but parsing it failed
 138   //   set  | set  | CDB was parsed from a known file
 139   CachedFile *ActiveCachedFile = nullptr;
 140
 141 public:
 142   DirectoryCache(llvm::StringRef Path)
 143       : CompileCommandsJson(Path, "compile_commands.json"),
 144         BuildCompileCommandsJson(Path, "build/compile_commands.json"),
 145         CompileFlagsTxt(Path, "compile_flags.txt"), Path(Path) {
 146     assert(llvm::sys::path::is_absolute(Path));
 147   }
 148
 149   // Absolute canonical path that we're the cache for. (Not case-folded).
 150   const std::string Path;
 151
 152   // Get the CDB associated with this directory.
 153   // ShouldBroadcast:
 154   //  - as input, signals whether the caller is willing to broadcast a
 155   //    newly-discovered CDB. (e.g. to trigger background indexing)
 156   //  - as output, signals whether the caller should do so.
 157   // (If a new CDB is discovered and ShouldBroadcast is false, we mark the
 158   // CDB as needing broadcast, and broadcast it next time we can).
 159   std::shared_ptr<const tooling::CompilationDatabase>
 160   get(const ThreadsafeFS &TFS, bool &ShouldBroadcast,
 161       stopwatch::time_point FreshTime, stopwatch::time_point FreshTimeMissing) {
 162     // Fast path for common case without taking lock.
 163     if (stopwatch::time_point(stopwatch::duration(NoCDBAt.load())) >
 164         FreshTimeMissing) {
 165       ShouldBroadcast = false;
 166       return nullptr;
 167     }
 168
 169     std::lock_guard<std::mutex> Lock(Mu);
 170     auto RequestBroadcast = llvm::make_scope_exit([&, OldCDB(CDB.get())] {
 171       // If we loaded a new CDB, it should be broadcast at some point.
 172       if (CDB != nullptr && CDB.get() != OldCDB)
 173         NeedsBroadcast = true;
 174       else if (CDB == nullptr) // nothing to broadcast anymore!
 175         NeedsBroadcast = false;
 176       // If we have something to broadcast, then do so iff allowed.
 177       if (!ShouldBroadcast)
 178         return;
 179       ShouldBroadcast = NeedsBroadcast;
 180       NeedsBroadcast = false;
 181     });
 182
 183     // If our cache is valid, serve from it.
 184     if (CachePopulatedAt > FreshTime)
 185       return CDB;
 186
 187     if (/*MayCache=*/load(*TFS.view(/*CWD=*/std::nullopt))) {
 188       // Use new timestamp, as loading may be slow.
 189       CachePopulatedAt = stopwatch::now();
 190       NoCDBAt.store((CDB ? stopwatch::time_point::min() : CachePopulatedAt)
 191                         .time_since_epoch()
 192                         .count());
 193     }
 194
 195     return CDB;
 196   }
 197
 198 private:
 199   // Updates `CDB` from disk state. Returns false on failure.
 200   bool load(llvm::vfs::FileSystem &FS);
 201 };
 202
 203 DirectoryBasedGlobalCompilationDatabase::DirectoryCache::CachedFile::LoadResult
 204 DirectoryBasedGlobalCompilationDatabase::DirectoryCache::CachedFile::load(
 205     llvm::vfs::FileSystem &FS, bool HasOldData) {
 206   auto Stat = FS.status(Path);
 207   if (!Stat || !Stat->isRegularFile()) {
 208     Size = NoFileCached;
 209     ContentHash = {};
 210     return {LoadResult::FileNotFound, nullptr};
 211   }
 212   // If both the size and mtime match, presume unchanged without reading.
 213   if (HasOldData && Stat->getLastModificationTime() == ModifiedTime &&
 214       Stat->getSize() == Size)
 215     return {LoadResult::FoundSameData, nullptr};
 216   auto Buf = FS.getBufferForFile(Path);
 217   if (!Buf || (*Buf)->getBufferSize() != Stat->getSize()) {
 218     // Don't clear the cache - possible we're seeing inconsistent size as the
 219     // file is being recreated. If it ends up identical later, great!
 220     //
 221     // This isn't a complete solution: if we see a partial file but stat/read
 222     // agree on its size, we're ultimately going to have spurious CDB reloads.
 223     // May be worth fixing if generators don't write atomically (CMake does).
 224     elog("Failed to read {0}: {1}", Path,
 225          Buf ? "size changed" : Buf.getError().message());
 226     return {LoadResult::TransientError, nullptr};
 227   }
 228
 229   FileDigest NewContentHash = digest((*Buf)->getBuffer());
 230   if (HasOldData && NewContentHash == ContentHash) {
 231     // mtime changed but data is the same: avoid rebuilding the CDB.
 232     ModifiedTime = Stat->getLastModificationTime();
 233     return {LoadResult::FoundSameData, nullptr};
 234   }
 235
 236   Size = (*Buf)->getBufferSize();
 237   ModifiedTime = Stat->getLastModificationTime();
 238   ContentHash = NewContentHash;
 239   return {LoadResult::FoundNewData, std::move(*Buf)};
 240 }
 241
 242 // Adapt CDB-loading functions to a common interface for DirectoryCache::load().
 243 static std::unique_ptr<tooling::CompilationDatabase>
 244 parseJSON(PathRef Path, llvm::StringRef Data, std::string &Error) {
 245   if (auto CDB = tooling::JSONCompilationDatabase::loadFromBuffer(
 246           Data, Error, tooling::JSONCommandLineSyntax::AutoDetect)) {
 247     return tooling::inferMissingCompileCommands(std::move(CDB));
 248   }
 249   return nullptr;
 250 }
 251 static std::unique_ptr<tooling::CompilationDatabase>
 252 parseFixed(PathRef Path, llvm::StringRef Data, std::string &Error) {
 253   return tooling::FixedCompilationDatabase::loadFromBuffer(
 254       llvm::sys::path::parent_path(Path), Data, Error);
 255 }
 256
 257 bool DirectoryBasedGlobalCompilationDatabase::DirectoryCache::load(
 258     llvm::vfs::FileSystem &FS) {
 259   dlog("Probing directory {0}", Path);
 260   std::string Error;
 261
 262   // Load from the specially-supported compilation databases (JSON + Fixed).
 263   // For these, we know the files they read and cache their metadata so we can
 264   // cheaply validate whether they've changed, and hot-reload if they have.
 265   // (As a bonus, these are also VFS-clean)!
 266   struct CDBFile {
 267     CachedFile *File;
 268     // Wrapper for {Fixed,JSON}CompilationDatabase::loadFromBuffer.
 269     std::unique_ptr<tooling::CompilationDatabase> (*Parser)(
 270         PathRef,
 271         /*Data*/ llvm::StringRef,
 272         /*ErrorMsg*/ std::string &);
 273   };
 274   for (const auto &Entry : {CDBFile{&CompileCommandsJson, parseJSON},
 275                             CDBFile{&BuildCompileCommandsJson, parseJSON},
 276                             CDBFile{&CompileFlagsTxt, parseFixed}}) {
 277     bool Active = ActiveCachedFile == Entry.File;
 278     auto Loaded = Entry.File->load(FS, Active);
 279     switch (Loaded.Result) {
 280     case CachedFile::LoadResult::FileNotFound:
 281       if (Active) {
 282         log("Unloaded compilation database from {0}", Entry.File->Path);
 283         ActiveCachedFile = nullptr;
 284         CDB = nullptr;
 285       }
 286       // Continue looking at other candidates.
 287       break;
 288     case CachedFile::LoadResult::TransientError:
 289       // File existed but we couldn't read it. Reuse the cache, retry later.
 290       return false; // Load again next time.
 291     case CachedFile::LoadResult::FoundSameData:
 292       assert(Active && "CachedFile may not return 'same data' if !HasOldData");
 293       // This is the critical file, and it hasn't changed.
 294       return true;
 295     case CachedFile::LoadResult::FoundNewData:
 296       // We have a new CDB!
 297       CDB = Entry.Parser(Entry.File->Path, Loaded.Buffer->getBuffer(), Error);
 298       if (CDB)
 299         log("{0} compilation database from {1}", Active ? "Reloaded" : "Loaded",
 300             Entry.File->Path);
 301       else
 302         elog("Failed to load compilation database from {0}: {1}",
 303              Entry.File->Path, Error);
 304       ActiveCachedFile = Entry.File;
 305       return true;
 306     }
 307   }
 308
 309   // Fall back to generic handling of compilation databases.
 310   // We don't know what files they read, so can't efficiently check whether
 311   // they need to be reloaded. So we never do that.
 312   // FIXME: the interface doesn't provide a way to virtualize FS access.
 313
 314   // Don't try these more than once. If we've scanned before, we're done.
 315   if (CachePopulatedAt > stopwatch::time_point::min())
 316     return true;
 317   for (const auto &Entry :
 318        tooling::CompilationDatabasePluginRegistry::entries()) {
 319     // Avoid duplicating the special cases handled above.
 320     if (Entry.getName() == "fixed-compilation-database" ||
 321         Entry.getName() == "json-compilation-database")
 322       continue;
 323     auto Plugin = Entry.instantiate();
 324     if (auto CDB = Plugin->loadFromDirectory(Path, Error)) {
 325       log("Loaded compilation database from {0} with plugin {1}", Path,
 326           Entry.getName());
 327       this->CDB = std::move(CDB);
 328       return true;
 329     }
 330     // Don't log Error here, it's usually just "couldn't find <file>".
 331   }
 332   dlog("No compilation database at {0}", Path);
 333   return true;
 334 }
 335
 336 DirectoryBasedGlobalCompilationDatabase::
 337     DirectoryBasedGlobalCompilationDatabase(const Options &Opts)
 338     : Opts(Opts), Broadcaster(std::make_unique<BroadcastThread>(*this)) {
 339   if (!this->Opts.ContextProvider)
 340     this->Opts.ContextProvider = [](llvm::StringRef) {
 341       return Context::current().clone();
 342     };
 343 }
 344
 345 DirectoryBasedGlobalCompilationDatabase::
 346     ~DirectoryBasedGlobalCompilationDatabase() = default;
 347
 348 std::optional<tooling::CompileCommand>
 349 DirectoryBasedGlobalCompilationDatabase::getCompileCommand(PathRef File) const {
 350   CDBLookupRequest Req;
 351   Req.FileName = File;
 352   Req.ShouldBroadcast = true;
 353   auto Now = std::chrono::steady_clock::now();
 354   Req.FreshTime = Now - Opts.RevalidateAfter;
 355   Req.FreshTimeMissing = Now - Opts.RevalidateMissingAfter;
 356
 357   auto Res = lookupCDB(Req);
 358   if (!Res) {
 359     log("Failed to find compilation database for {0}", File);
 360     return std::nullopt;
 361   }
 362
 363   auto Candidates = Res->CDB->getCompileCommands(File);
 364   if (!Candidates.empty())
 365     return std::move(Candidates.front());
 366
 367   return std::nullopt;
 368 }
 369
 370 std::vector<DirectoryBasedGlobalCompilationDatabase::DirectoryCache *>
 371 DirectoryBasedGlobalCompilationDatabase::getDirectoryCaches(
 372     llvm::ArrayRef<llvm::StringRef> Dirs) const {
 373   std::vector<std::string> FoldedDirs;
 374   FoldedDirs.reserve(Dirs.size());
 375   for (const auto &Dir : Dirs) {
 376 #ifndef NDEBUG
 377     if (!llvm::sys::path::is_absolute(Dir))
 378       elog("Trying to cache CDB for relative {0}");
 379 #endif
 380     FoldedDirs.push_back(maybeCaseFoldPath(Dir));
 381   }
 382
 383   std::vector<DirectoryCache *> Ret;
 384   Ret.reserve(Dirs.size());
 385
 386   std::lock_guard<std::mutex> Lock(DirCachesMutex);
 387   for (unsigned I = 0; I < Dirs.size(); ++I)
 388     Ret.push_back(&DirCaches.try_emplace(FoldedDirs[I], Dirs[I]).first->second);
 389   return Ret;
 390 }
 391
 392 std::optional<DirectoryBasedGlobalCompilationDatabase::CDBLookupResult>
 393 DirectoryBasedGlobalCompilationDatabase::lookupCDB(
 394     CDBLookupRequest Request) const {
 395   assert(llvm::sys::path::is_absolute(Request.FileName) &&
 396          "path must be absolute");
 397
 398   std::string Storage;
 399   std::vector<llvm::StringRef> SearchDirs;
 400   if (Opts.CompileCommandsDir) // FIXME: unify this case with config.
 401     SearchDirs = {*Opts.CompileCommandsDir};
 402   else {
 403     WithContext WithProvidedContext(Opts.ContextProvider(Request.FileName));
 404     const auto &Spec = Config::current().CompileFlags.CDBSearch;
 405     switch (Spec.Policy) {
 406     case Config::CDBSearchSpec::NoCDBSearch:
 407       return std::nullopt;
 408     case Config::CDBSearchSpec::FixedDir:
 409       Storage = *Spec.FixedCDBPath;
 410       SearchDirs = {Storage};
 411       break;
 412     case Config::CDBSearchSpec::Ancestors:
 413       // Traverse the canonical version to prevent false positives. i.e.:
 414       // src/build/../a.cc can detect a CDB in /src/build if not
 415       // canonicalized.
 416       Storage = removeDots(Request.FileName);
 417       actOnAllParentDirectories(Storage, [&](llvm::StringRef Dir) {
 418         SearchDirs.push_back(Dir);
 419         return false;
 420       });
 421     }
 422   }
 423
 424   std::shared_ptr<const tooling::CompilationDatabase> CDB = nullptr;
 425   bool ShouldBroadcast = false;
 426   DirectoryCache *DirCache = nullptr;
 427   for (DirectoryCache *Candidate : getDirectoryCaches(SearchDirs)) {
 428     bool CandidateShouldBroadcast = Request.ShouldBroadcast;
 429     if ((CDB = Candidate->get(Opts.TFS, CandidateShouldBroadcast,
 430                               Request.FreshTime, Request.FreshTimeMissing))) {
 431       DirCache = Candidate;
 432       ShouldBroadcast = CandidateShouldBroadcast;
 433       break;
 434     }
 435   }
 436
 437   if (!CDB)
 438     return std::nullopt;
 439
 440   CDBLookupResult Result;
 441   Result.CDB = std::move(CDB);
 442   Result.PI.SourceRoot = DirCache->Path;
 443
 444   if (ShouldBroadcast)
 445     broadcastCDB(Result);
 446   return Result;
 447 }
 448
 449 // The broadcast thread announces files with new compile commands to the world.
 450 // Primarily this is used to enqueue them for background indexing.
 451 //
 452 // It's on a separate thread because:
 453 //  - otherwise it would block the first parse of the initial file
 454 //  - we need to enumerate all files in the CDB, of which there are many
 455 //  - we (will) have to evaluate config for every file in the CDB, which is slow
 456 class DirectoryBasedGlobalCompilationDatabase::BroadcastThread {
 457   class Filter;
 458   DirectoryBasedGlobalCompilationDatabase &Parent;
 459
 460   std::mutex Mu;
 461   std::condition_variable CV;
 462   // Shutdown flag (CV is notified after writing).
 463   // This is atomic so that broadcasts can also observe it and abort early.
 464   std::atomic<bool> ShouldStop = {false};
 465   struct Task {
 466     CDBLookupResult Lookup;
 467     Context Ctx;
 468   };
 469   std::deque<Task> Queue;
 470   std::optional<Task> ActiveTask;
 471   std::thread Thread; // Must be last member.
 472
 473   // Thread body: this is just the basic queue procesing boilerplate.
 474   void run() {
 475     std::unique_lock<std::mutex> Lock(Mu);
 476     while (true) {
 477       bool Stopping = false;
 478       CV.wait(Lock, [&] {
 479         return (Stopping = ShouldStop.load(std::memory_order_acquire)) ||
 480                !Queue.empty();
 481       });
 482       if (Stopping) {
 483         Queue.clear();
 484         CV.notify_all();
 485         return;
 486       }
 487       ActiveTask = std::move(Queue.front());
 488       Queue.pop_front();
 489
 490       Lock.unlock();
 491       {
 492         WithContext WithCtx(std::move(ActiveTask->Ctx));
 493         process(ActiveTask->Lookup);
 494       }
 495       Lock.lock();
 496       ActiveTask.reset();
 497       CV.notify_all();
 498     }
 499   }
 500
 501   // Inspects a new CDB and broadcasts the files it owns.
 502   void process(const CDBLookupResult &T);
 503
 504 public:
 505   BroadcastThread(DirectoryBasedGlobalCompilationDatabase &Parent)
 506       : Parent(Parent), Thread([this] { run(); }) {}
 507
 508   void enqueue(CDBLookupResult Lookup) {
 509     {
 510       assert(!Lookup.PI.SourceRoot.empty());
 511       std::lock_guard<std::mutex> Lock(Mu);
 512       // New CDB takes precedence over any queued one for the same directory.
 513       llvm::erase_if(Queue, [&](const Task &T) {
 514         return T.Lookup.PI.SourceRoot == Lookup.PI.SourceRoot;
 515       });
 516       Queue.push_back({std::move(Lookup), Context::current().clone()});
 517     }
 518     CV.notify_all();
 519   }
 520
 521   bool blockUntilIdle(Deadline Timeout) {
 522     std::unique_lock<std::mutex> Lock(Mu);
 523     return wait(Lock, CV, Timeout,
 524                 [&] { return Queue.empty() && !ActiveTask; });
 525   }
 526
 527   ~BroadcastThread() {
 528     {
 529       std::lock_guard<std::mutex> Lock(Mu);
 530       ShouldStop.store(true, std::memory_order_release);
 531     }
 532     CV.notify_all();
 533     Thread.join();
 534   }
 535 };
 536
 537 // The DirBasedCDB associates each file with a specific CDB.
 538 // When a CDB is discovered, it may claim to describe files that we associate
 539 // with a different CDB. We do not want to broadcast discovery of these, and
 540 // trigger background indexing of them.
 541 //
 542 // We must filter the list, and check whether they are associated with this CDB.
 543 // This class attempts to do so efficiently.
 544 //
 545 // Roughly, it:
 546 //  - loads the config for each file, and determines the relevant search path
 547 //  - gathers all directories that are part of any search path
 548 //  - (lazily) checks for a CDB in each such directory at most once
 549 //  - walks the search path for each file and determines whether to include it.
 550 class DirectoryBasedGlobalCompilationDatabase::BroadcastThread::Filter {
 551   llvm::StringRef ThisDir;
 552   DirectoryBasedGlobalCompilationDatabase &Parent;
 553
 554   // Keep track of all directories we might check for CDBs.
 555   struct DirInfo {
 556     DirectoryCache *Cache = nullptr;
 557     enum { Unknown, Missing, TargetCDB, OtherCDB } State = Unknown;
 558     DirInfo *Parent = nullptr;
 559   };
 560   llvm::StringMap<DirInfo> Dirs;
 561
 562   // A search path starts at a directory, and either includes ancestors or not.
 563   using SearchPath = llvm::PointerIntPair<DirInfo *, 1>;
 564
 565   // Add all ancestor directories of FilePath to the tracked set.
 566   // Returns the immediate parent of the file.
 567   DirInfo *addParents(llvm::StringRef FilePath) {
 568     DirInfo *Leaf = nullptr;
 569     DirInfo *Child = nullptr;
 570     actOnAllParentDirectories(FilePath, [&](llvm::StringRef Dir) {
 571       auto &Info = Dirs[Dir];
 572       // If this is the first iteration, then this node is the overall result.
 573       if (!Leaf)
 574         Leaf = &Info;
 575       // Fill in the parent link from the previous iteration to this parent.
 576       if (Child)
 577         Child->Parent = &Info;
 578       // Keep walking, whether we inserted or not, if parent link is missing.
 579       // (If it's present, parent links must be present up to the root, so stop)
 580       Child = &Info;
 581       return Info.Parent != nullptr;
 582     });
 583     return Leaf;
 584   }
 585
 586   // Populates DirInfo::Cache (and State, if it is TargetCDB).
 587   void grabCaches() {
 588     // Fast path out if there were no files, or CDB loading is off.
 589     if (Dirs.empty())
 590       return;
 591
 592     std::vector<llvm::StringRef> DirKeys;
 593     std::vector<DirInfo *> DirValues;
 594     DirKeys.reserve(Dirs.size() + 1);
 595     DirValues.reserve(Dirs.size());
 596     for (auto &E : Dirs) {
 597       DirKeys.push_back(E.first());
 598       DirValues.push_back(&E.second);
 599     }
 600
 601     // Also look up the cache entry for the CDB we're broadcasting.
 602     // Comparing DirectoryCache pointers is more robust than checking string
 603     // equality, e.g. reuses the case-sensitivity handling.
 604     DirKeys.push_back(ThisDir);
 605     auto DirCaches = Parent.getDirectoryCaches(DirKeys);
 606     const DirectoryCache *ThisCache = DirCaches.back();
 607     DirCaches.pop_back();
 608     DirKeys.pop_back();
 609
 610     for (unsigned I = 0; I < DirKeys.size(); ++I) {
 611       DirValues[I]->Cache = DirCaches[I];
 612       if (DirCaches[I] == ThisCache)
 613         DirValues[I]->State = DirInfo::TargetCDB;
 614     }
 615   }
 616
 617   // Should we include a file from this search path?
 618   bool shouldInclude(SearchPath P) {
 619     DirInfo *Info = P.getPointer();
 620     if (!Info)
 621       return false;
 622     if (Info->State == DirInfo::Unknown) {
 623       assert(Info->Cache && "grabCaches() should have filled this");
 624       // Given that we know that CDBs have been moved/generated, don't trust
 625       // caches. (This should be rare, so it's OK to add a little latency).
 626       constexpr auto IgnoreCache = std::chrono::steady_clock::time_point::max();
 627       // Don't broadcast CDBs discovered while broadcasting!
 628       bool ShouldBroadcast = false;
 629       bool Exists =
 630           nullptr != Info->Cache->get(Parent.Opts.TFS, ShouldBroadcast,
 631                                       /*FreshTime=*/IgnoreCache,
 632                                       /*FreshTimeMissing=*/IgnoreCache);
 633       Info->State = Exists ? DirInfo::OtherCDB : DirInfo::Missing;
 634     }
 635     // If we have a CDB, include the file if it's the target CDB only.
 636     if (Info->State != DirInfo::Missing)
 637       return Info->State == DirInfo::TargetCDB;
 638     // If we have no CDB and no relevant parent, don't include the file.
 639     if (!P.getInt() || !Info->Parent)
 640       return false;
 641     // Walk up to the next parent.
 642     return shouldInclude(SearchPath(Info->Parent, 1));
 643   }
 644
 645 public:
 646   Filter(llvm::StringRef ThisDir,
 647          DirectoryBasedGlobalCompilationDatabase &Parent)
 648       : ThisDir(ThisDir), Parent(Parent) {}
 649
 650   std::vector<std::string> filter(std::vector<std::string> AllFiles,
 651                                   std::atomic<bool> &ShouldStop) {
 652     std::vector<std::string> Filtered;
 653     // Allow for clean early-exit of the slow parts.
 654     auto ExitEarly = [&] {
 655       if (ShouldStop.load(std::memory_order_acquire)) {
 656         log("Giving up on broadcasting CDB, as we're shutting down");
 657         Filtered.clear();
 658         return true;
 659       }
 660       return false;
 661     };
 662     // Compute search path for each file.
 663     std::vector<SearchPath> SearchPaths(AllFiles.size());
 664     for (unsigned I = 0; I < AllFiles.size(); ++I) {
 665       if (Parent.Opts.CompileCommandsDir) { // FIXME: unify with config
 666         SearchPaths[I].setPointer(&Dirs[*Parent.Opts.CompileCommandsDir]);
 667         continue;
 668       }
 669       if (ExitEarly()) // loading config may be slow
 670         return Filtered;
 671       WithContext WithProvidedContent(Parent.Opts.ContextProvider(AllFiles[I]));
 672       const Config::CDBSearchSpec &Spec =
 673           Config::current().CompileFlags.CDBSearch;
 674       switch (Spec.Policy) {
 675       case Config::CDBSearchSpec::NoCDBSearch:
 676         break;
 677       case Config::CDBSearchSpec::Ancestors:
 678         SearchPaths[I].setInt(/*Recursive=*/1);
 679         SearchPaths[I].setPointer(addParents(AllFiles[I]));
 680         break;
 681       case Config::CDBSearchSpec::FixedDir:
 682         SearchPaths[I].setPointer(&Dirs[*Spec.FixedCDBPath]);
 683         break;
 684       }
 685     }
 686     // Get the CDB cache for each dir on the search path, but don't load yet.
 687     grabCaches();
 688     // Now work out which files we want to keep, loading CDBs where needed.
 689     for (unsigned I = 0; I < AllFiles.size(); ++I) {
 690       if (ExitEarly()) // loading CDBs may be slow
 691         return Filtered;
 692       if (shouldInclude(SearchPaths[I]))
 693         Filtered.push_back(std::move(AllFiles[I]));
 694     }
 695     return Filtered;
 696   }
 697 };
 698
 699 void DirectoryBasedGlobalCompilationDatabase::BroadcastThread::process(
 700     const CDBLookupResult &T) {
 701   vlog("Broadcasting compilation database from {0}", T.PI.SourceRoot);
 702   std::vector<std::string> GovernedFiles =
 703       Filter(T.PI.SourceRoot, Parent).filter(T.CDB->getAllFiles(), ShouldStop);
 704   if (!GovernedFiles.empty())
 705     Parent.OnCommandChanged.broadcast(std::move(GovernedFiles));
 706 }
 707
 708 void DirectoryBasedGlobalCompilationDatabase::broadcastCDB(
 709     CDBLookupResult Result) const {
 710   assert(Result.CDB && "Trying to broadcast an invalid CDB!");
 711   Broadcaster->enqueue(Result);
 712 }
 713
 714 bool DirectoryBasedGlobalCompilationDatabase::blockUntilIdle(
 715     Deadline Timeout) const {
 716   return Broadcaster->blockUntilIdle(Timeout);
 717 }
 718
 719 std::optional<ProjectInfo>
 720 DirectoryBasedGlobalCompilationDatabase::getProjectInfo(PathRef File) const {
 721   CDBLookupRequest Req;
 722   Req.FileName = File;
 723   Req.ShouldBroadcast = false;
 724   Req.FreshTime = Req.FreshTimeMissing =
 725       std::chrono::steady_clock::time_point::min();
 726   auto Res = lookupCDB(Req);
 727   if (!Res)
 728     return std::nullopt;
 729   return Res->PI;
 730 }
 731
 732 OverlayCDB::OverlayCDB(const GlobalCompilationDatabase *Base,
 733                        std::vector<std::string> FallbackFlags,
 734                        CommandMangler Mangler)
 735     : DelegatingCDB(Base), Mangler(std::move(Mangler)),
 736       FallbackFlags(std::move(FallbackFlags)) {}
 737
 738 std::optional<tooling::CompileCommand>
 739 OverlayCDB::getCompileCommand(PathRef File) const {
 740   std::optional<tooling::CompileCommand> Cmd;
 741   {
 742     std::lock_guard<std::mutex> Lock(Mutex);
 743     auto It = Commands.find(removeDots(File));
 744     if (It != Commands.end())
 745       Cmd = It->second;
 746   }
 747   if (!Cmd)
 748     Cmd = DelegatingCDB::getCompileCommand(File);
 749   if (!Cmd)
 750     return std::nullopt;
 751   if (Mangler)
 752     Mangler(*Cmd, File);
 753   return Cmd;
 754 }
 755
 756 tooling::CompileCommand OverlayCDB::getFallbackCommand(PathRef File) const {
 757   auto Cmd = DelegatingCDB::getFallbackCommand(File);
 758   std::lock_guard<std::mutex> Lock(Mutex);
 759   Cmd.CommandLine.insert(Cmd.CommandLine.end(), FallbackFlags.begin(),
 760                          FallbackFlags.end());
 761   if (Mangler)
 762     Mangler(Cmd, File);
 763   return Cmd;
 764 }
 765
 766 void OverlayCDB::setCompileCommand(PathRef File,
 767                                    std::optional<tooling::CompileCommand> Cmd) {
 768   // We store a canonical version internally to prevent mismatches between set
 769   // and get compile commands. Also it assures clients listening to broadcasts
 770   // doesn't receive different names for the same file.
 771   std::string CanonPath = removeDots(File);
 772   {
 773     std::unique_lock<std::mutex> Lock(Mutex);
 774     if (Cmd)
 775       Commands[CanonPath] = std::move(*Cmd);
 776     else
 777       Commands.erase(CanonPath);
 778   }
 779   OnCommandChanged.broadcast({CanonPath});
 780 }
 781
 782 DelegatingCDB::DelegatingCDB(const GlobalCompilationDatabase *Base)
 783     : Base(Base) {
 784   if (Base)
 785     BaseChanged = Base->watch([this](const std::vector<std::string> Changes) {
 786       OnCommandChanged.broadcast(Changes);
 787     });
 788 }
 789
 790 DelegatingCDB::DelegatingCDB(std::unique_ptr<GlobalCompilationDatabase> Base)
 791     : DelegatingCDB(Base.get()) {
 792   BaseOwner = std::move(Base);
 793 }
 794
 795 std::optional<tooling::CompileCommand>
 796 DelegatingCDB::getCompileCommand(PathRef File) const {
 797   if (!Base)
 798     return std::nullopt;
 799   return Base->getCompileCommand(File);
 800 }
 801
 802 std::optional<ProjectInfo> DelegatingCDB::getProjectInfo(PathRef File) const {
 803   if (!Base)
 804     return std::nullopt;
 805   return Base->getProjectInfo(File);
 806 }
 807
 808 tooling::CompileCommand DelegatingCDB::getFallbackCommand(PathRef File) const {
 809   if (!Base)
 810     return GlobalCompilationDatabase::getFallbackCommand(File);
 811   return Base->getFallbackCommand(File);
 812 }
 813
 814 bool DelegatingCDB::blockUntilIdle(Deadline D) const {
 815   if (!Base)
 816     return true;
 817   return Base->blockUntilIdle(D);
 818 }
 819
 820 } // namespace clangd
 821 } // namespace clang