[clangd] Cache .clang-tidy files again.

[sammccall]

Summary

This cache went away in 73fdd998701cce3aa6c4d8d2a73ab97351a0313b

This time, the cache is periodically validated against disk, so config
is still mostly "live".

The per-file cache reuses FileCache, but the tree-of-file-caches is
duplicated from ConfigProvider. .clangd, .clang-tidy, .clang-format, and
compile_commands.json all have this pattern, we should extract it at some point.
TODO for now though.

[njames93]

clang-tools-extra/clangd/TidyProvider.cpp

34

To save a copy, could this not return a const pointer to whats stored in Value, nullptr if Value is empty.
In DotClangTidyTree, OptionStack could then store pointers instead of values.
Considering the size of ClangTidyOptions (312 bytes in x64 with libstdc++) this is definitely a worthwhile saving.

One slight issue is I'm not sure how nicely this approach would play with the mutex.

61–62

Should these both be const?

76

Given path has been brought into scope in the line above can probably remove excess qualifiers.

84–87

How does this work with .. components. Or does clangd ensure all absolute paths have those removed?

113

This will result in incorrect behaviour if a config specifies InheritParentConfig as false

[sammccall]

Return shared_ptr instead of value from cache, to avoid copies.

Remove unneeded qualifiers.

clang-tools-extra/clangd/TidyProvider.cpp

34

You're right, and 312 bytes understates it - it contains strings and stuff that likely allocate on the heap when copied.

The issue with a pointer is that the underlying value may not live long enough (or to put it another way, the pointer will point to the cache slot which may be concurrently modified).

I think the fix for that is to store and return a shared_ptr<const ClangTidyOptions>. I'll give that a try.

61–62

We've generally avoided making members const in clangd when they can be, probably mostly to avoid problems with move semantics, but in the end because you've got to pick a style and stick with it.

(The move-semantics argument seems weak because we do use reference members sometimes, including in this class, and convert them to pointers when it becomes a problem. Oh well...)

84–87

Right, paths are always canonical.

113

Whoops, thanks!
(Why is this optional<bool> rather than bool?)

[njames93]

clang-tools-extra/clangd/TidyProvider.cpp

34

That sounds like a good resolve. I'm guessing in the common case where the config file doesn't change, this would never mutate.

84–87

If that's the case, aren't these checks redundant. Maybe put some asserts in so we don't pay for them in release builds

113

I'm honestly not sure. Personally I don't think it should belong in ClangTidyOptions. Its only used when reading configuration from files(or command line). Maybe I'll rustle something up for that.

[njames93]

clang-tools-extra/clangd/TidyProvider.cpp

113

What do you think about this approach? D92199

[sammccall]

Replace dynamic check with assert.

[njames93]

LGTM, with a couple of nits that could easily be disregarded.

clang-tools-extra/clangd/TidyProvider.cpp

61–62

nit: Unless we actually do extract this as a base class, these don't really need to be fields.

81–102

nit: Is it not better to simply merge these 2 loops into one traversal and get rid of the Ancestors vector. The path traversal is relatively cheap so we wouldn't be holding the mutex for that much longer.

[njames93]

Unfortunately this broke the search order for clang-tidy files in root directories in favour or subdirectories. This wasn't caught as we didn't have tests for this. I've put a fix for this in D96204 with appropriate tests.

clang-tools-extra/clangd/TidyProvider.cpp

 //===--- TidyProvider.cpp - create options for running clang-tidy----------===//
 //
 // 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 "TidyProvider.h"
 #include "Config.h"
+#include "support/FileCache.h"
 #include "support/Logger.h"
+#include "support/ThreadsafeFS.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/Process.h"
 #include "llvm/Support/VirtualFileSystem.h"
 #include <memory>
 
 namespace clang {
 namespace clangd {
+namespace {
+
+// Access to config from a .clang-tidy file, caching IO and parsing.
+class DotClangTidyCache : private FileCache {
+  mutable llvm::Optional<tidy::ClangTidyOptions> Value;
+
+public:
+  DotClangTidyCache(PathRef Path) : FileCache(Path) {}
+
+  llvm::Optional<tidy::ClangTidyOptions>
+  get(const ThreadsafeFS &TFS,
+      std::chrono::steady_clock::time_point FreshTime) const {
+    llvm::Optional<tidy::ClangTidyOptions> Result;
+    read(
+        TFS, FreshTime,
+        [this](llvm::Optional<llvm::StringRef> Data) {
+          Value.reset();
+          if (Data && !Data->empty()) {
+            if (auto Parsed = tidy::parseConfiguration(*Data))
+              Value = std::move(*Parsed);
+            else
+              elog("Error parsing clang-tidy configuration in {0}: {1}", path(),
+                   Parsed.getError().message());
+          }
+        },
+        [&]() { Result = Value; });
+    return Result;
+  }
+};
+
+// Access to combined config from .clang-tidy files governing a source file.
+// Each config file is cached and the caches are shared for affected sources.
+//
+// FIXME: largely duplicates config::Provider::fromAncestorRelativeYAMLFiles.
+// Potentially useful for compile_commands.json too. Extract?
+class DotClangTidyTree {
+  const ThreadsafeFS &FS;
+  std::string RelPath;
+  std::chrono::steady_clock::duration MaxStaleness;
+
+  mutable std::mutex Mu;
+  // Keys are the ancestor directory, not the actual config path within it.
+  // We only insert into this map, so pointers to values are stable forever.
+  // Mutex guards the map itself, not the values (which are threadsafe).
+  mutable llvm::StringMap<DotClangTidyCache> Cache;
+
+public:
+  DotClangTidyTree(const ThreadsafeFS &FS)
+      : FS(FS), RelPath(".clang-tidy"), MaxStaleness(std::chrono::seconds(5)) {}
+
+  void apply(tidy::ClangTidyOptions &Result, PathRef AbsPath) {
+    namespace path = llvm::sys::path;
+    assert(llvm::sys::path::is_absolute(AbsPath));
+
+    // Compute absolute paths to all ancestors (substrings of P.Path).
+    llvm::StringRef Parent = path::parent_path(AbsPath);
+    llvm::SmallVector<llvm::StringRef, 8> Ancestors;
+    for (auto I = path::begin(Parent, path::Style::posix),
+              E = path::end(Parent);
+         I != E; ++I) {
+      // Avoid weird non-substring cases like phantom "." components.
+      // In practice, Component is a substring for all "normal" ancestors.
+      if (I->end() < Parent.begin() && I->end() > Parent.end())
+        continue;
+      Ancestors.emplace_back(Parent.begin(), I->end() - Parent.begin());
+    }
+    // Ensure corresponding cache entries exist in the map.
+    llvm::SmallVector<DotClangTidyCache *, 8> Caches;
+    {
+      std::lock_guard<std::mutex> Lock(Mu);
+      for (llvm::StringRef Ancestor : Ancestors) {
+        auto It = Cache.find(Ancestor);
+        // Assemble the actual config file path only once.
+        if (It == Cache.end()) {
+          llvm::SmallString<256> ConfigPath = Ancestor;
+          path::append(ConfigPath, RelPath);
+          It = Cache.try_emplace(Ancestor, ConfigPath.str()).first;
+        }
+        Caches.push_back(&It->second);
+      }
+    }
+    // Finally query each individual file.
+    // This will take a (per-file) lock for each file that actually exists.
+    std::chrono::steady_clock::time_point FreshTime =
+        std::chrono::steady_clock::now() - MaxStaleness;
+    llvm::SmallVector<tidy::ClangTidyOptions, 1> OptionStack;
+    for (const DotClangTidyCache *Cache : Caches)
+      if (auto Config = Cache->get(FS, FreshTime)) {
+        OptionStack.push_back(std::move(*Config));
+        if (!OptionStack.back().InheritParentConfig)
+          break;
+      }
+    unsigned Order = 1u;
+    for (auto &Option : llvm::reverse(OptionStack))
+      Result.mergeWith(Option, Order++);
+  }
+};
+
+} // namespace
 
 static void mergeCheckList(llvm::Optional<std::string> &Checks,
                            llvm::StringRef List) {
   if (List.empty())
     return;
   if (!Checks || Checks->empty()) {
     Checks.emplace(List);
     return;
   }
   *Checks = llvm::join_items(",", *Checks, List);
 }
 
-static llvm::Optional<tidy::ClangTidyOptions>
-tryReadConfigFile(llvm::vfs::FileSystem *FS, llvm::StringRef Directory) {
-  assert(!Directory.empty());
-  // We guaranteed that child directories of Directory exist, so this assert
-  // should hopefully never fail.
-  assert(FS->exists(Directory));
-
-  llvm::SmallString<128> ConfigFile(Directory);
-  llvm::sys::path::append(ConfigFile, ".clang-tidy");
-
-  llvm::ErrorOr<llvm::vfs::Status> FileStatus = FS->status(ConfigFile);
-
-  if (!FileStatus || !FileStatus->isRegularFile())
-    return llvm::None;
-
-  llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> Text =
-      FS->getBufferForFile(ConfigFile);
-  if (std::error_code EC = Text.getError()) {
-    elog("Can't read '{0}': {1}", ConfigFile, EC.message());
-    return llvm::None;
-  }
-
-  // Skip empty files, e.g. files opened for writing via shell output
-  // redirection.
-  if ((*Text)->getBuffer().empty())
-    return llvm::None;
-  llvm::ErrorOr<tidy::ClangTidyOptions> ParsedOptions =
-      tidy::parseConfiguration((*Text)->getBuffer());
-  if (!ParsedOptions) {
-    if (ParsedOptions.getError())
-      elog("Error parsing clang-tidy configuration in '{0}': {1}", ConfigFile,
-           ParsedOptions.getError().message());
-    return llvm::None;
-  }
-  return std::move(*ParsedOptions);
-}
-
 TidyProviderRef provideEnvironment() {
   static const llvm::Optional<std::string> User = [] {
     llvm::Optional<std::string> Ret = llvm::sys::Process::GetEnv("USER");
 #ifdef _WIN32
     if (!Ret)
       return llvm::sys::Process::GetEnv("USERNAME");
 #endif
     return Ret;
return [](tidy::ClangTidyOptions &Opts, llvm::StringRef) {
     for (const auto &CheckOption : CurTidyConfig.CheckOptions)
       Opts.CheckOptions.insert_or_assign(CheckOption.getKey(),
                                          tidy::ClangTidyOptions::ClangTidyValue(
                                              CheckOption.getValue(), 10000U));
   };
 }
 
 TidyProvider provideClangTidyFiles(ThreadsafeFS &TFS) {
-  return [&TFS](tidy::ClangTidyOptions &Opts, llvm::StringRef Filename) {
-    llvm::SmallVector<tidy::ClangTidyOptions, 4> OptionStack;
-    auto FS(TFS.view(llvm::None));
-    llvm::SmallString<256> AbsolutePath(Filename);
-
-    assert(llvm::sys::path::is_absolute(AbsolutePath));
-
-    llvm::sys::path::remove_dots(AbsolutePath, true);
-    llvm::StringRef Directory = llvm::sys::path::parent_path(AbsolutePath);
-    {
-      auto Status = FS->status(Directory);
-
-      if (!Status || !Status->isDirectory()) {
-        elog("Error reading configuration from {0}: directory doesn't exist",
-             Directory);
-        return;
-      }
-    }
-
-    // FIXME: Store options in a cache that validates itself against changes
-    // during the clangd session.
-    for (llvm::StringRef CurrentDirectory = Directory;
-         !CurrentDirectory.empty();
-         CurrentDirectory = llvm::sys::path::parent_path(CurrentDirectory)) {
-      auto ConfigFile = tryReadConfigFile(FS.get(), CurrentDirectory);
-      if (!ConfigFile)
-        continue;
-      OptionStack.push_back(std::move(*ConfigFile));
-      // Should we search for a parent config to merge
-      if (!OptionStack.back().InheritParentConfig.getValueOr(false))
-        break;
-    }
-    unsigned Order = 1U;
-    for (auto &Option : llvm::reverse(OptionStack))
-      Opts.mergeWith(Option, Order++);
+  return [Tree = std::make_unique<DotClangTidyTree>(TFS)](
+             tidy::ClangTidyOptions &Opts, llvm::StringRef Filename) {
+    Tree->apply(Opts, Filename);
   };
 }
 
 TidyProvider combine(std::vector<TidyProvider> Providers) {
   // FIXME: Once function_ref and unique_function operator= operators handle
   // null values, we should filter out any Providers that are null. Right now we
   // have to ensure we dont pass any providers that are null.
   return [Providers(std::move(Providers))](tidy::ClangTidyOptions &Opts,