diff --git a/clang-tools-extra/clangd/TidyProvider.cpp b/clang-tools-extra/clangd/TidyProvider.cpp --- a/clang-tools-extra/clangd/TidyProvider.cpp +++ b/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 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 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 Caches; - { - std::lock_guard 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 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> 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++);