kadircet updated this revision to Diff 296111. kadircet marked 7 inline comments as done. kadircet added a comment.
- Address comments Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D88411/new/ https://reviews.llvm.org/D88411 Files: clang-tools-extra/clangd/support/CMakeLists.txt clang-tools-extra/clangd/support/MemoryTree.cpp clang-tools-extra/clangd/support/MemoryTree.h clang-tools-extra/clangd/unittests/CMakeLists.txt clang-tools-extra/clangd/unittests/support/MemoryTreeTests.cpp
Index: clang-tools-extra/clangd/unittests/support/MemoryTreeTests.cpp =================================================================== --- /dev/null +++ clang-tools-extra/clangd/unittests/support/MemoryTreeTests.cpp @@ -0,0 +1,131 @@ +//===-- MemoryTreeTests.cpp -------------------------------------*- 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 +// +//===----------------------------------------------------------------------===// + +#include "support/MemoryTree.h" +#include "llvm/Support/Allocator.h" +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include <ostream> + +namespace clang { +namespace clangd { +namespace { +using testing::Contains; +using testing::UnorderedElementsAre; + +struct Component { + std::string Name; + size_t Size; +}; +std::ostream &operator<<(std::ostream &OS, const Component &Comp) { + return OS << Comp.Name << ',' << Comp.Size; +} + +MATCHER_P2(WithNameAndSize, Name, Size, "") { + return std::tie(arg.Name, arg.Size) == std::tie(Name, Size); +} + +std::vector<Component> collectComponents(const MemoryTree &MT) { + std::vector<Component> SeenComponents; + MT.traverseTree( + [&SeenComponents](size_t Size, llvm::StringRef CompName) { + Component C; + C.Name = CompName.str(); + C.Size = Size; + SeenComponents.emplace_back(std::move(C)); + }, + "root"); + return SeenComponents; +} + +TEST(MemoryTree, Basics) { + MemoryTree MT; + EXPECT_THAT(collectComponents(MT), + UnorderedElementsAre(WithNameAndSize("root", 0))); + + MT.addUsage(42); + EXPECT_THAT(collectComponents(MT), + UnorderedElementsAre(WithNameAndSize("root", 42))); + + MT.addChild("leaf")->addUsage(1); + EXPECT_THAT(collectComponents(MT), + UnorderedElementsAre(WithNameAndSize("root", 42), + WithNameAndSize("root.leaf", 1))); + + // addChild should be idempotent. + MT.addChild("leaf")->addUsage(1); + EXPECT_THAT(collectComponents(MT), + UnorderedElementsAre(WithNameAndSize("root", 42), + WithNameAndSize("root.leaf", 2))); +} + +TEST(MemoryTree, DetailedNodesWithoutDetails) { + MemoryTree MT; + MT.addDetail("should_be_ignored")->addUsage(2); + EXPECT_THAT(collectComponents(MT), + UnorderedElementsAre(WithNameAndSize("root", 2))); + + // Make sure children from details are merged. + MT.addDetail("first_detail")->addChild("leaf")->addUsage(1); + MT.addDetail("second_detail")->addChild("leaf")->addUsage(1); + EXPECT_THAT(collectComponents(MT), Contains(WithNameAndSize("root.leaf", 2))); +} + +TEST(MemoryTree, DetailedNodesWithDetails) { + llvm::BumpPtrAllocator Alloc; + MemoryTree MT(&Alloc); + + MT.addDetail("first_detail")->addChild("leaf")->addUsage(1); + EXPECT_THAT(collectComponents(MT), + Contains(WithNameAndSize("root.first_detail.leaf", 1))); + MT.addDetail("second_detail")->addChild("leaf")->addUsage(1); + EXPECT_THAT(collectComponents(MT), + Contains(WithNameAndSize("root.second_detail.leaf", 1))); +} + +TEST(MemoryTree, Traversal) { + auto AddNodes = [](MemoryTree Root) { + Root.addChild("leaf")->addUsage(1); + + { + auto *Detail = Root.addDetail("detail"); + Detail->addUsage(1); + Detail->addChild("leaf")->addUsage(1); + auto *Child = Detail->addChild("child"); + Child->addUsage(1); + Child->addChild("leaf")->addUsage(1); + } + + { + auto *Child = Root.addChild("child"); + Child->addUsage(1); + Child->addChild("leaf")->addUsage(1); + } + return Root; + }; + + EXPECT_THAT(collectComponents(AddNodes(MemoryTree())), + UnorderedElementsAre(WithNameAndSize("root", 1), + WithNameAndSize("root.leaf", 2), + WithNameAndSize("root.child", 2), + WithNameAndSize("root.child.leaf", 2))); + + llvm::BumpPtrAllocator Alloc; + EXPECT_THAT(collectComponents(AddNodes(MemoryTree(&Alloc))), + UnorderedElementsAre(WithNameAndSize("root", 0), + WithNameAndSize("root.leaf", 1), + WithNameAndSize("root.detail", 1), + WithNameAndSize("root.detail.leaf", 1), + WithNameAndSize("root.detail.child", 1), + WithNameAndSize("root.detail.child.leaf", 1), + WithNameAndSize("root.child", 1), + WithNameAndSize("root.child.leaf", 1))); +} +} // namespace +} // namespace clangd +} // namespace clang Index: clang-tools-extra/clangd/unittests/CMakeLists.txt =================================================================== --- clang-tools-extra/clangd/unittests/CMakeLists.txt +++ clang-tools-extra/clangd/unittests/CMakeLists.txt @@ -99,6 +99,7 @@ support/ContextTests.cpp support/FunctionTests.cpp support/MarkupTests.cpp + support/MemoryTreeTests.cpp support/ThreadingTests.cpp support/TestTracer.cpp support/TraceTests.cpp Index: clang-tools-extra/clangd/support/MemoryTree.h =================================================================== --- /dev/null +++ clang-tools-extra/clangd/support/MemoryTree.h @@ -0,0 +1,72 @@ +//===--- MemoryTree.h - A special tree for components and sizes -*- 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_MEMORYTREE_H_ +#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_SUPPORT_MEMORYTREE_H_ + +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/Support/Allocator.h" +#include "llvm/Support/StringSaver.h" +#include <cstddef> +#include <string> +#include <vector> + +namespace clang { +namespace clangd { + +/// A tree that can be used to represent memory usage of nested components while +/// preserving the hierarchy. +/// Edges have associated names. An edge that might not be interesting to all +/// traversers or costly to copy (e.g. file names) can be marked as "detail". +/// Tree construction allows chosing between a detailed and brief mode, in brief +/// mode all "detail" edges are ignored and tree is constructed without any +/// string copies. +struct MemoryTree { +public: + /// If Alloc is nullptr, tree is in brief mode and will ignore detail edges. + MemoryTree(llvm::BumpPtrAllocator *Alloc = nullptr) : Alloc(Alloc) {} + + /// No copy of the \p Name. + MemoryTree *addChild(llvm::StringLiteral Name) { return &createChild(Name); } + + /// Makes a copy of the \p Name in detailed mode, returns current node + /// otherwise. + MemoryTree *addDetail(llvm::StringRef Name) { + return Alloc ? &createChild(llvm::StringSaver(*Alloc).save(Name)) : this; + } + + /// Increases size of current node by \p Increment. + void addUsage(size_t Increment) { Size += Increment; } + + /// Performs a pre-order traversal of the tree, while concatenating edge names + /// with dots("."). + void traverseTree(llvm::function_ref<void(size_t /*Size*/, + llvm::StringRef /*ComponentName*/)> + CB, + std::string ComponentName = "") const; + +private: + /// Adds a child with an edge labeled as \p Name. Multiple calls to this + /// function returns the same node. + MemoryTree &createChild(llvm::StringRef Name); + + /// Allocator to use for detailed edge names. + llvm::BumpPtrAllocator *Alloc = nullptr; + + /// Bytes owned by this component specifically. + size_t Size = 0; + + /// Edges from current node to its children. Keys are the labels for edges. + llvm::DenseMap<llvm::StringRef, MemoryTree> Children; +}; + +} // namespace clangd +} // namespace clang + +#endif Index: clang-tools-extra/clangd/support/MemoryTree.cpp =================================================================== --- /dev/null +++ clang-tools-extra/clangd/support/MemoryTree.cpp @@ -0,0 +1,22 @@ +#include "support/MemoryTree.h" + +namespace clang { +namespace clangd { + +void MemoryTree::traverseTree( + llvm::function_ref<void(size_t /*Size*/, llvm::StringRef /*ComponentName*/)> + CB, + std::string ComponentName) const { + CB(Size, ComponentName); + if (!ComponentName.empty()) + ComponentName += '.'; + for (const auto &Entry : Children) + Entry.getSecond().traverseTree(CB, (ComponentName + Entry.first).str()); +} + +MemoryTree &MemoryTree::createChild(llvm::StringRef Name) { + auto &Child = Children.try_emplace(Name, Alloc).first->getSecond(); + return Child; +} +} // namespace clangd +} // namespace clang Index: clang-tools-extra/clangd/support/CMakeLists.txt =================================================================== --- clang-tools-extra/clangd/support/CMakeLists.txt +++ clang-tools-extra/clangd/support/CMakeLists.txt @@ -21,6 +21,7 @@ Context.cpp Logger.cpp Markup.cpp + MemoryTree.cpp Shutdown.cpp Threading.cpp ThreadsafeFS.cpp
_______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
