njames93 created this revision.
njames93 added a reviewer: sammccall.
Herald added subscribers: usaxena95, kadircet, arphaman.
njames93 requested review of this revision.
Herald added subscribers: cfe-commits, MaskRay, ilya-biryukov.
Herald added a project: clang.
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.
This change should be NFC.
Depends on D96204 <https://reviews.llvm.org/D96204> - Mainly for the test cases
added, to ensure this isn't breakign behaviour.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D96286
Files:
clang-tools-extra/clangd/TidyProvider.cpp
Index: clang-tools-extra/clangd/TidyProvider.cpp
===================================================================
--- clang-tools-extra/clangd/TidyProvider.cpp
+++ clang-tools-extra/clangd/TidyProvider.cpp
@@ -76,12 +76,24 @@
}
};
+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;
@@ -90,56 +102,92 @@
// 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.
+
+ // AbsPath should be pointing to a file, get the directory.
llvm::StringRef Parent = path::parent_path(AbsPath);
- llvm::SmallVector<DotClangTidyCache *> Caches;
- {
- std::lock_guard<std::mutex> Lock(Mu);
- for (auto I = path::rbegin(Parent), E = path::rend(Parent); I != E; ++I) {
- assert(I->end() >= Parent.begin() && I->end() <= Parent.end() &&
- "Canonical path components should be substrings");
- llvm::StringRef Ancestor(Parent.begin(), I->end() - Parent.begin());
+ auto I = path::rbegin(Parent), E = path::rend(Parent);
+ assert(I != E && "There should be at least 1 path component to traverse");
+ llvm::StringRef Ancestor(Parent.begin(), I->end() - Parent.begin());
+
+ std::lock_guard<std::mutex> Lock(Mu);
+
+ auto It = Cache.find(Ancestor);
+ // 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.
+ ++I;
+ for (; I != E; ++I) {
+ assert(I->end() >= Parent.begin() && I->end() <= Parent.end() &&
+ "Canonical path components should be substrings");
+ llvm::StringRef Ancestor(Parent.begin(), I->end() - Parent.begin());
#ifdef _WIN32
- // C:\ is an ancestor, but skip its (relative!) parent C:.
- if (Ancestor.size() == 2 && Ancestor.back() == ':')
- continue;
+ // C:\ is an ancestor, but skip its (relative!) parent C:.
+ if (Ancestor.size() == 2 && Ancestor.back() == ':')
+ break;
#endif
- assert(path::is_absolute(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);
+ assert(path::is_absolute(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;
}
- // Finally query each individual file.
- // This will take a (per-file) lock for each file that actually exists.
+ 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++);
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
