[clangd][NFC] Change TidyProvider cache to use a linked list approach

[njames93]

Summary

I know linked lists are the work of the devil, but it makes sense here.

Change the map in the DotClangTidyTree to store the FileCache as well as a link to its parent FileCache.
By storing a pointer to each items parent in the map, we no longer need to traverse the entire directory tree and populating a vector for each item.
Instead we just grab the tail from the map and (in all but the first run) it will contain links to the whole directory structure we need for querying.
This can save a lot of redundant work if the config file was in the tail directory but there was 15 parent directories above it.

[njames93]

A similar approach could be used for the config provider, however It may not make as much sense there. The directories are traversed in the opposite order and we will always attempt to read from each directory.

[njames93]

Update using absoluteParent helper

[njames93]

Ping @sammccall Any issues with this?

[kadircet]

just wanted to point out that, this is almost the same thing as https://github.com/llvm/llvm-project/blob/main/clang-tools-extra/clangd/GlobalCompilationDatabase.cpp#L569.

[njames93]

Ping

[njames93]

Ping?

[njames93]

Ping

clang-tools-extra/clangd/TidyProvider.cpp

read(
                    Parsed.getError().message());
           }
         },
         [&]() { Result = Value; });
     return Result;
   }
 };
 
+llvm::SmallString<256> pathAppend(PathRef Path, llvm::StringRef Tail) {
+  llvm::SmallString<256> ConfigPath(Path);
+  llvm::sys::path::append(ConfigPath, Tail);
+  return ConfigPath;
+}
+
 // 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 {
+  struct DirectoryNode {
+    DirectoryNode(PathRef File) : Cache(File), Parent(nullptr) {}
+    DotClangTidyCache Cache;
+    DirectoryNode *Parent;
+  };
+
   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) {
+  // We store values as linked lists pointing to their parent directories nodes,
+  // this saves quering the map for each component of a path.
+  mutable llvm::StringMap<DirectoryNode> Cache;
+
+  /// Ensures there is a FileCache for each .clang-tidy file in the directory
+  /// tree up to \p AbsPath and returns a linked list structure pointing to the
+  /// first item.
+  /// \pre \p AbsPath is an absolute path to a file.
+  DirectoryNode *getNode(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.
+    // AbsPath should be pointing to a file, get the directory.
+    auto Ancestor = absoluteParent(AbsPath);
+    assert(!Ancestor.empty() &&
+           "There should be at least 1 path component to traverse");
+
+
+    // This is the hot path. After invoking this method on a given path once,
+    // The path will stay in the map for the life of this object, saving any
+    // further lookup.
+    if (LLVM_LIKELY(It != Cache.end()))
+      return &It->getValue();
+
+    // Build the FileCache for this item and store a pointer to its parent node,
+    // this will be filled in when we process the next component in the path.
+    DirectoryNode *Result =
+        &Cache.try_emplace(Ancestor, pathAppend(Ancestor, RelPath).str())
+             .first->getValue();
+    DirectoryNode **ParentPtr = &Result->Parent;
+
+    // Skip the first item as we have already processed it.
+    for (Ancestor = absoluteParent(Ancestor); !Ancestor.empty();
+         Ancestor = absoluteParent(Ancestor)) {
+
+      It = Cache.find(Ancestor);
+      if (It != Cache.end()) {
+        // We have found a relative parent already in the map. Update the childs
+        // parent pointer to this, then stop. This items Parent should contain
+        // the tree below it already.
+        *ParentPtr = &It->getValue();
+        break;
+
+      // The item isn't in the cache, so assemble it.
+      auto *Node =
+          &Cache.try_emplace(Ancestor, pathAppend(Ancestor, RelPath).str())
+               .first->getValue();
+      *ParentPtr = Node;
+      // Keep track of this nodes parent pointer for the next iteration.
+      ParentPtr = &Node->Parent;
+    return Result;
+
+public:
+  DotClangTidyTree(const ThreadsafeFS &FS)
+      : FS(FS), RelPath(".clang-tidy"), MaxStaleness(std::chrono::seconds(5)) {}
+
+  void apply(tidy::ClangTidyOptions &Result, PathRef AbsPath) {
     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 (auto *DirNode = getNode(AbsPath); DirNode; DirNode = DirNode->Parent) {
+      if (auto Config = DirNode->Cache.get(FS, FreshTime)) {
         OptionStack.push_back(std::move(Config));
         if (!OptionStack.back()->InheritParentConfig.getValueOr(false))
           break;
       }
+    }
     unsigned Order = 1u;
     for (auto &Option : llvm::reverse(OptionStack))
       Result.mergeWith(*Option, Order++);
   }
 };
 
 } // namespace