[clangd][NFC] Unify ancestor logic for config and tidy provider.

[njames93]

Summary

Removed duplicated code for building list of ancestors when finding .config and .clang-tidy files in ancestor directories.

Supercedes D96286

clang-tools-extra/clangd/ConfigProvider.cpp

 //===--- ConfigProvider.cpp - Loading of user configuration ---------------===//
 //
 // 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 "ConfigProvider.h"
 #include "Config.h"
 #include "ConfigFragment.h"
+#include "support/AncestorFileCache.h"
 #include "support/FileCache.h"
 #include "support/Path.h"
 #include "support/ThreadsafeFS.h"
 #include "support/Trace.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Path.h"
std::unique_ptr<Provider> Provider::fromYAMLFile(llvm::StringRef AbsPath,
 
   return std::make_unique<AbsFileProvider>(AbsPath, Directory, FS, Trusted);
 }
 
 std::unique_ptr<Provider>
 Provider::fromAncestorRelativeYAMLFiles(llvm::StringRef RelPath,
                                         const ThreadsafeFS &FS, bool Trusted) {
   class RelFileProvider : public Provider {
-    std::string RelPath;
+    AncestorFileCache<FileConfigCache> Cache;
     const ThreadsafeFS &FS;
     bool Trusted;
 
-    mutable std::mutex Mu;
-    // Keys are the (posix-style) ancestor directory, not the config 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<FileConfigCache> Cache;
-
     std::vector<CompiledFragment>
     getFragments(const Params &P, DiagnosticCallback DC) const override {
-      namespace path = llvm::sys::path;
-
-      if (P.Path.empty())
-        return {};
-
-      // Compute absolute paths to all ancestors (substrings of P.Path).
-      llvm::SmallVector<llvm::StringRef, 8> Ancestors;
-      for (auto Ancestor = absoluteParent(P.Path); !Ancestor.empty();
-           Ancestor = absoluteParent(Ancestor)) {
-        Ancestors.emplace_back(Ancestor);
-      }
-      // Ensure corresponding cache entries exist in the map.
       llvm::SmallVector<FileConfigCache *, 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);
-            // Use native slashes for reading the file, affects diagnostics.
-            llvm::sys::path::native(ConfigPath);
-            It = Cache.try_emplace(Ancestor, ConfigPath.str(), Ancestor).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::vector<CompiledFragment> Result;
-      for (FileConfigCache *Cache : llvm::reverse(Caches))
-        Cache->get(FS, DC, P.FreshTime, Trusted, Result);
+      for (FileConfigCache *Item : Cache.reverseAncestors(P.Path, Caches))
+        Item->get(FS, DC, P.FreshTime, Trusted, Result);
       return Result;
-    };
+    }
 
   public:
     RelFileProvider(llvm::StringRef RelPath, const ThreadsafeFS &FS,
                     bool Trusted)
-        : RelPath(RelPath), FS(FS), Trusted(Trusted) {
+        : Cache(RelPath), FS(FS), Trusted(Trusted) {
       assert(llvm::sys::path::is_relative(RelPath));
     }
   };
 
   return std::make_unique<RelFileProvider>(RelPath, FS, Trusted);
 }
 
 std::unique_ptr<Provider>

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 "../clang-tidy/ClangTidyModuleRegistry.h"
 #include "Config.h"
+#include "support/AncestorFileCache.h"
 #include "support/FileCache.h"
 #include "support/Logger.h"
 #include "support/Path.h"
 #include "support/ThreadsafeFS.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Process.h"
 #include "llvm/Support/SourceMgr.h"
 #include <memory>
 
 namespace clang {
 namespace clangd {
 namespace {
 
 // Access to config from a .clang-tidy file, caching IO and parsing.
 class DotClangTidyCache : private FileCache {
   // We cache and expose shared_ptr to avoid copying the value on every lookup
   // when we're ultimately just going to pass it to mergeWith.
   mutable std::shared_ptr<const tidy::ClangTidyOptions> Value;
 
 public:
-  DotClangTidyCache(PathRef Path) : FileCache(Path) {}
+  DotClangTidyCache(PathRef Path, PathRef) : FileCache(Path) {}
 
   std::shared_ptr<const tidy::ClangTidyOptions>
   get(const ThreadsafeFS &TFS,
       std::chrono::steady_clock::time_point FreshTime) const {
     std::shared_ptr<const tidy::ClangTidyOptions> Result;
     read(
         TFS, FreshTime,
         [this](llvm::Optional<llvm::StringRef> Data) {

 
 // 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;
+  AncestorFileCache<DotClangTidyCache> Cache;
   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)) {}
+      : FS(FS), Cache(".clang-tidy"), MaxStaleness(std::chrono::seconds(5)) {}
 
   void apply(tidy::ClangTidyOptions &Result, PathRef AbsPath) {
-    namespace path = llvm::sys::path;
-    assert(path::is_absolute(AbsPath));
 
-    // Compute absolute paths to all ancestors (substrings of P.Path).
-    // Ensure cache entries for each ancestor exist in the map.
-    llvm::SmallVector<DotClangTidyCache *> Caches;
-    {
-      std::lock_guard<std::mutex> Lock(Mu);
-      for (auto Ancestor = absoluteParent(AbsPath); !Ancestor.empty();
-           Ancestor = absoluteParent(Ancestor)) {
-        auto It = Cache.find(Ancestor);
-        // Assemble the actual config file path only if needed.
-        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<std::shared_ptr<const tidy::ClangTidyOptions>>
         OptionStack;
-    for (const DotClangTidyCache *Cache : Caches)
-      if (auto Config = Cache->get(FS, FreshTime)) {
+    for (const DotClangTidyCache &SingleCache : Cache.ancestors(AbsPath))
+      if (auto Config = SingleCache.get(FS, FreshTime)) {
         OptionStack.push_back(std::move(Config));
         if (!OptionStack.back()->InheritParentConfig.value_or(false))
           break;
       }
     unsigned Order = 1u;
     for (auto &Option : llvm::reverse(OptionStack))
       Result.mergeWith(*Option, Order++);
   }

clang-tools-extra/clangd/support/AncestorFileCache.h

+//===--- AncestorFileCache.h -------------------------------------*- 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_SUPPORT_ANCESTORFILECACHE_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_SUPPORT_ANCESTORFILECACHE_H
+
+#include "FileCache.h"
+#include "llvm/ADT/StringMap.h"
+#include <type_traits>
+
+namespace clang {
+namespace clangd {
+
+template <typename FCache> class AncestorFileCache {
+  static_assert(std::is_base_of<FileCache, FCache>::value, "");
+  struct Node {
+    Node(llvm::StringRef Path, llvm::StringRef Directory)
+        : Item(Path, Directory) {}
+    FCache Item;
+    Node *Parent = nullptr;
+  };
+
+  std::string RelPath;
+  mutable std::mutex Mu;
+
+  // Keys are the (posix-style) ancestor directory, not the config 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<Node> Cache; // GUARDED_BY(Mu)
+
+  Node *getNode(PathRef P) const {
+    if (P.empty())
+      return nullptr;
+    auto Ancestor = absoluteParent(P);
+    if (Ancestor.empty())
+      return nullptr;
+    std::lock_guard<std::mutex> Lock(Mu);
+    auto It = Cache.find(Ancestor);
+    if (LLVM_LIKELY(It != Cache.end()))
+      return &It->getValue();
+
+    llvm::SmallString<256> ConfigPath = Ancestor;
+    llvm::sys::path::append(ConfigPath, RelPath);
+    llvm::sys::path::native(ConfigPath);
+    Node *Res = &Cache.try_emplace(Ancestor, ConfigPath.str(), Ancestor)
+                     .first->getValue();
+    Node **Parent = &Res->Parent;
+
+    for (Ancestor = absoluteParent(Ancestor); !Ancestor.empty();
+         Ancestor = absoluteParent(Ancestor)) {
+      It = Cache.find(Ancestor);
+      if (It != Cache.end()) {
+        *Parent = &It->getValue();
+        return Res;
+      }
+      ConfigPath = Ancestor;
+      llvm::sys::path::append(ConfigPath, RelPath);
+      llvm::sys::path::native(ConfigPath);
+      Node *Child = &Cache.try_emplace(Ancestor, ConfigPath.str(), Ancestor)
+                         .first->getValue();
+      *Parent = Child;
+      Parent = &Child->Parent;
+    }
+    return Res;
+  }
+
+public:
+  AncestorFileCache(llvm::StringRef RelPath) : RelPath(RelPath) {}
+  class Iterator
+      : public llvm::iterator_facade_base<Iterator, std::forward_iterator_tag,
+                                          Node *> {
+    friend class AncestorFileCache<FCache>;
+    Node *Item = nullptr;
+    Iterator() = default;
+    Iterator(Node *Item) : Item(Item) {}
+
+  public:
+    Iterator(const Iterator &) = default;
+    Iterator &operator=(const Iterator &R) = default;
+
+    bool operator==(const Iterator &R) const { return Item == R.Item; }
+    FCache &operator*() const { return Item->Item; }
+    Iterator &operator++() {
+      Item = Item->Parent;
+      return *this;
+    }
+  };
+
+  Iterator begin(PathRef P) const { return Iterator(getNode(P)); }
+
+  Iterator end() const { return Iterator(); }
+
+  llvm::iterator_range<Iterator> ancestors(PathRef P) const {
+    return {begin(P), end()};
+  }
+
+  llvm::iterator_range<std::reverse_iterator<FCache **>>
+  reverseAncestors(PathRef P, llvm::SmallVectorImpl<FCache *> &Storage) const {
+    Storage.clear();
+    for (auto &Item : ancestors(P)) {
+      Storage.push_back(&Item);
+    }
+    return llvm::reverse(Storage);
+  }
+};
+
+} // namespace clangd
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_SUPPORT_ANCESTORFILECACHE_H