diff options
Diffstat (limited to 'llvm/unittests')
9 files changed, 389 insertions, 8 deletions
diff --git a/llvm/unittests/ADT/CMakeLists.txt b/llvm/unittests/ADT/CMakeLists.txt index 848ccba..af503d9 100644 --- a/llvm/unittests/ADT/CMakeLists.txt +++ b/llvm/unittests/ADT/CMakeLists.txt @@ -63,6 +63,7 @@ add_llvm_unittest(ADTTests PointerUnionTest.cpp PostOrderIteratorTest.cpp PriorityWorklistTest.cpp + RadixTreeTest.cpp RangeAdapterTest.cpp RewriteBufferTest.cpp SCCIteratorTest.cpp diff --git a/llvm/unittests/ADT/RadixTreeTest.cpp b/llvm/unittests/ADT/RadixTreeTest.cpp new file mode 100644 index 0000000..b2dd67c --- /dev/null +++ b/llvm/unittests/ADT/RadixTreeTest.cpp @@ -0,0 +1,379 @@ +//===- llvm/unittest/ADT/RadixTreeTest.cpp --------------------------------===// +// +// 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 "llvm/ADT/RadixTree.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/StringRef.h" +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include <iterator> +#include <list> +#include <vector> + +using namespace llvm; +namespace { + +using ::testing::ElementsAre; +using ::testing::ElementsAreArray; +using ::testing::Pair; +using ::testing::UnorderedElementsAre; + +// Test with StringRef. + +TEST(RadixTreeTest, Empty) { + RadixTree<StringRef, int> T; + EXPECT_TRUE(T.empty()); + EXPECT_EQ(T.size(), 0u); + + EXPECT_TRUE(T.find_prefixes("").empty()); + EXPECT_TRUE(T.find_prefixes("A").empty()); + + EXPECT_EQ(T.countNodes(), 1u); +} + +TEST(RadixTreeTest, InsertEmpty) { + RadixTree<StringRef, int> T; + auto [It, IsNew] = T.emplace("", 4); + EXPECT_TRUE(!T.empty()); + EXPECT_EQ(T.size(), 1u); + EXPECT_TRUE(IsNew); + const auto &[K, V] = *It; + EXPECT_TRUE(K.empty()); + EXPECT_EQ(4, V); + + EXPECT_THAT(T, ElementsAre(Pair("", 4))); + + EXPECT_THAT(T.find_prefixes(""), ElementsAre(Pair("", 4))); + + EXPECT_THAT(T.find_prefixes("a"), ElementsAre(Pair("", 4))); + + EXPECT_EQ(T.countNodes(), 1u); +} + +TEST(RadixTreeTest, Complex) { + RadixTree<StringRef, int> T; + T.emplace("abcd", 1); + EXPECT_EQ(T.countNodes(), 2u); + T.emplace("abklm", 2); + EXPECT_EQ(T.countNodes(), 4u); + T.emplace("123abklm", 3); + EXPECT_EQ(T.countNodes(), 5u); + T.emplace("123abklm", 4); + EXPECT_EQ(T.countNodes(), 5u); + T.emplace("ab", 5); + EXPECT_EQ(T.countNodes(), 5u); + T.emplace("1234567", 6); + EXPECT_EQ(T.countNodes(), 7u); + T.emplace("123456", 7); + EXPECT_EQ(T.countNodes(), 8u); + T.emplace("123456789", 8); + EXPECT_EQ(T.countNodes(), 9u); + + EXPECT_THAT(T, UnorderedElementsAre(Pair("abcd", 1), Pair("abklm", 2), + Pair("123abklm", 3), Pair("ab", 5), + Pair("1234567", 6), Pair("123456", 7), + Pair("123456789", 8))); + + EXPECT_THAT(T.find_prefixes("1234567890"), + UnorderedElementsAre(Pair("1234567", 6), Pair("123456", 7), + Pair("123456789", 8))); + + EXPECT_THAT(T.find_prefixes("123abklm"), + UnorderedElementsAre(Pair("123abklm", 3))); + + EXPECT_THAT(T.find_prefixes("abcdefg"), + UnorderedElementsAre(Pair("abcd", 1), Pair("ab", 5))); + + EXPECT_EQ(T.countNodes(), 9u); +} + +TEST(RadixTreeTest, ValueWith2Parameters) { + RadixTree<StringRef, std::pair<std::string, int>> T; + T.emplace("abcd", "a", 3); + + EXPECT_THAT(T, UnorderedElementsAre(Pair("abcd", Pair("a", 3)))); +} + +// Test different types, less readable. + +template <typename T> struct TestData { + static const T Data1[]; + static const T Data2[]; +}; + +template <> const char TestData<char>::Data1[] = "abcdedcba"; +template <> const char TestData<char>::Data2[] = "abCDEDCba"; + +template <> const int TestData<int>::Data1[] = {1, 2, 3, 4, 5, 4, 3, 2, 1}; +template <> const int TestData<int>::Data2[] = {1, 2, 4, 8, 16, 8, 4, 2, 1}; + +template <typename T> class RadixTreeTypeTest : public ::testing::Test { +public: + using IteratorType = decltype(adl_begin(std::declval<const T &>())); + using CharType = remove_cvref_t<decltype(*adl_begin(std::declval<T &>()))>; + + T make(const CharType *Data, size_t N) { return T(StringRef(Data, N)); } + + T make1(size_t N) { return make(TestData<CharType>::Data1, N); } + T make2(size_t N) { return make(TestData<CharType>::Data2, N); } +}; + +template <> +iterator_range<StringRef::const_iterator> +RadixTreeTypeTest<iterator_range<StringRef::const_iterator>>::make( + const char *Data, size_t N) { + return StringRef(Data).take_front(N); +} + +template <> +iterator_range<StringRef::const_reverse_iterator> +RadixTreeTypeTest<iterator_range<StringRef::const_reverse_iterator>>::make( + const char *Data, size_t N) { + return reverse(StringRef(Data).take_back(N)); +} + +template <> +ArrayRef<int> RadixTreeTypeTest<ArrayRef<int>>::make(const int *Data, + size_t N) { + return ArrayRef<int>(Data, Data + N); +} + +template <> +std::vector<int> RadixTreeTypeTest<std::vector<int>>::make(const int *Data, + size_t N) { + return std::vector<int>(Data, Data + N); +} + +template <> +std::list<int> RadixTreeTypeTest<std::list<int>>::make(const int *Data, + size_t N) { + return std::list<int>(Data, Data + N); +} + +class TypeNameGenerator { +public: + template <typename T> static std::string GetName(int) { + if (std::is_same_v<T, StringRef>) + return "StringRef"; + if (std::is_same_v<T, std::string>) + return "string"; + if (std::is_same_v<T, iterator_range<StringRef::const_iterator>>) + return "iterator_range"; + if (std::is_same_v<T, iterator_range<StringRef::const_reverse_iterator>>) + return "reverse_iterator_range"; + if (std::is_same_v<T, ArrayRef<int>>) + return "ArrayRef"; + if (std::is_same_v<T, std::vector<int>>) + return "vector"; + if (std::is_same_v<T, std::list<int>>) + return "list"; + return "Unknown"; + } +}; + +using TestTypes = + ::testing::Types<StringRef, std::string, + iterator_range<StringRef::const_iterator>, + iterator_range<StringRef::const_reverse_iterator>, + ArrayRef<int>, std::vector<int>, std::list<int>>; + +TYPED_TEST_SUITE(RadixTreeTypeTest, TestTypes, TypeNameGenerator); + +TYPED_TEST(RadixTreeTypeTest, Helpers) { + for (size_t i = 0; i < 9; ++i) { + auto R1 = this->make1(i); + auto R2 = this->make2(i); + EXPECT_EQ(llvm::range_size(R1), i); + EXPECT_EQ(llvm::range_size(R2), i); + auto [I1, I2] = llvm::mismatch(R1, R2); + // Exactly 2 first elements of Data1 and Data2 must match. + EXPECT_EQ(std::distance(R1.begin(), I1), std::min<int>(2, i)); + } +} + +TYPED_TEST(RadixTreeTypeTest, Empty) { + RadixTree<TypeParam, int> T; + EXPECT_TRUE(T.empty()); + EXPECT_EQ(T.size(), 0u); + + EXPECT_TRUE(T.find_prefixes(this->make1(0)).empty()); + EXPECT_TRUE(T.find_prefixes(this->make2(1)).empty()); + + EXPECT_EQ(T.countNodes(), 1u); +} + +TYPED_TEST(RadixTreeTypeTest, InsertEmpty) { + using TreeType = RadixTree<TypeParam, int>; + TreeType T; + auto [It, IsNew] = T.emplace(this->make1(0), 5); + EXPECT_TRUE(!T.empty()); + EXPECT_EQ(T.size(), 1u); + EXPECT_TRUE(IsNew); + const auto &[K, V] = *It; + EXPECT_TRUE(K.empty()); + EXPECT_EQ(5, V); + + EXPECT_THAT(T.find_prefixes(this->make1(0)), + ElementsAre(Pair(ElementsAre(), 5))); + + EXPECT_THAT(T.find_prefixes(this->make2(1)), + ElementsAre(Pair(ElementsAre(), 5))); + + EXPECT_THAT(T, ElementsAre(Pair(ElementsAre(), 5))); + + EXPECT_EQ(T.countNodes(), 1u); +} + +TYPED_TEST(RadixTreeTypeTest, InsertEmptyTwice) { + using TreeType = RadixTree<TypeParam, int>; + TreeType T; + T.emplace(this->make1(0), 5); + auto [It, IsNew] = T.emplace(this->make1(0), 6); + EXPECT_TRUE(!T.empty()); + EXPECT_EQ(T.size(), 1u); + EXPECT_TRUE(!IsNew); + const auto &[K, V] = *It; + EXPECT_TRUE(K.empty()); + EXPECT_EQ(5, V); + + EXPECT_THAT(T.find_prefixes(this->make1(0)), + ElementsAre(Pair(ElementsAre(), 5))); + + EXPECT_THAT(T.find_prefixes(this->make2(1)), + ElementsAre(Pair(ElementsAre(), 5))); + + EXPECT_THAT(T, ElementsAre(Pair(ElementsAre(), 5))); + + EXPECT_EQ(T.countNodes(), 1u); +} + +TYPED_TEST(RadixTreeTypeTest, InsertOne) { + using TreeType = RadixTree<TypeParam, int>; + TreeType T; + auto [It, IsNew] = T.emplace(this->make1(1), 4); + EXPECT_TRUE(!T.empty()); + EXPECT_EQ(T.size(), 1u); + EXPECT_TRUE(IsNew); + const auto &[K, V] = *It; + EXPECT_THAT(K, ElementsAreArray(this->make1(1))); + EXPECT_EQ(4, V); + + EXPECT_THAT(T, ElementsAre(Pair(ElementsAreArray(this->make1(1)), 4))); + + EXPECT_THAT(T.find_prefixes(this->make1(1)), + ElementsAre(Pair(ElementsAreArray(this->make1(1)), 4))); + + EXPECT_THAT(T.find_prefixes(this->make1(2)), + ElementsAre(Pair(ElementsAreArray(this->make1(1)), 4))); + + EXPECT_EQ(T.countNodes(), 2u); +} + +TYPED_TEST(RadixTreeTypeTest, InsertOneTwice) { + using TreeType = RadixTree<TypeParam, int>; + TreeType T; + T.emplace(this->make1(1), 4); + auto [It, IsNew] = T.emplace(this->make1(1), 4); + EXPECT_TRUE(!T.empty()); + EXPECT_EQ(T.size(), 1u); + EXPECT_TRUE(!IsNew); + + EXPECT_THAT(T, ElementsAre(Pair(ElementsAreArray(this->make1(1)), 4))); + EXPECT_EQ(T.countNodes(), 2u); +} + +TYPED_TEST(RadixTreeTypeTest, InsertSuperStrings) { + using TreeType = RadixTree<TypeParam, int>; + TreeType T; + + for (size_t Len = 0; Len < 7; Len += 2) { + auto [It, IsNew] = T.emplace(this->make1(Len), Len); + EXPECT_TRUE(IsNew); + } + + EXPECT_THAT(T, + UnorderedElementsAre(Pair(ElementsAreArray(this->make1(0)), 0), + Pair(ElementsAreArray(this->make1(2)), 2), + Pair(ElementsAreArray(this->make1(4)), 4), + Pair(ElementsAreArray(this->make1(6)), 6))); + + EXPECT_THAT(T.find_prefixes(this->make1(0)), + UnorderedElementsAre(Pair(ElementsAreArray(this->make1(0)), 0))); + + EXPECT_THAT(T.find_prefixes(this->make1(3)), + UnorderedElementsAre(Pair(ElementsAreArray(this->make1(0)), 0), + Pair(ElementsAreArray(this->make1(2)), 2))); + + EXPECT_THAT(T.find_prefixes(this->make1(7)), + UnorderedElementsAre(Pair(ElementsAreArray(this->make1(0)), 0), + Pair(ElementsAreArray(this->make1(2)), 2), + Pair(ElementsAreArray(this->make1(4)), 4), + Pair(ElementsAreArray(this->make1(6)), 6))); + + EXPECT_EQ(T.countNodes(), 4u); +} + +TYPED_TEST(RadixTreeTypeTest, InsertSubStrings) { + using TreeType = RadixTree<TypeParam, int>; + TreeType T; + + for (size_t Len = 0; Len < 7; Len += 2) { + auto [It, IsNew] = T.emplace(this->make1(7 - Len), 7 - Len); + EXPECT_TRUE(IsNew); + } + + EXPECT_THAT(T, + UnorderedElementsAre(Pair(ElementsAreArray(this->make1(1)), 1), + Pair(ElementsAreArray(this->make1(3)), 3), + Pair(ElementsAreArray(this->make1(5)), 5), + Pair(ElementsAreArray(this->make1(7)), 7))); + + EXPECT_THAT(T.find_prefixes(this->make1(0)), UnorderedElementsAre()); + + EXPECT_THAT(T.find_prefixes(this->make1(3)), + UnorderedElementsAre(Pair(ElementsAreArray(this->make1(1)), 1), + Pair(ElementsAreArray(this->make1(3)), 3))); + + EXPECT_THAT(T.find_prefixes(this->make1(6)), + UnorderedElementsAre(Pair(ElementsAreArray(this->make1(1)), 1), + Pair(ElementsAreArray(this->make1(3)), 3), + Pair(ElementsAreArray(this->make1(5)), 5))); + + EXPECT_EQ(T.countNodes(), 5u); +} + +TYPED_TEST(RadixTreeTypeTest, InsertVShape) { + using TreeType = RadixTree<TypeParam, int>; + TreeType T; + + EXPECT_EQ(T.countNodes(), 1u); + T.emplace(this->make1(5), 15); + EXPECT_EQ(T.countNodes(), 2u); + T.emplace(this->make2(6), 26); + EXPECT_EQ(T.countNodes(), 4u); + T.emplace(this->make2(1), 21); + EXPECT_EQ(T.countNodes(), 5u); + + EXPECT_THAT(T, + UnorderedElementsAre(Pair(ElementsAreArray(this->make1(5)), 15), + Pair(ElementsAreArray(this->make2(6)), 26), + Pair(ElementsAreArray(this->make2(1)), 21))); + + EXPECT_THAT(T.find_prefixes(this->make1(7)), + UnorderedElementsAre(Pair(ElementsAreArray(this->make2(1)), 21), + Pair(ElementsAreArray(this->make1(5)), 15))); + + EXPECT_THAT(T.find_prefixes(this->make2(7)), + UnorderedElementsAre(Pair(ElementsAreArray(this->make2(1)), 21), + Pair(ElementsAreArray(this->make2(6)), 26))); + + EXPECT_EQ(T.countNodes(), 5u); +} + +} // namespace diff --git a/llvm/unittests/ADT/STLForwardCompatTest.cpp b/llvm/unittests/ADT/STLForwardCompatTest.cpp index 2a97e8d..c6ae6e3 100644 --- a/llvm/unittests/ADT/STLForwardCompatTest.cpp +++ b/llvm/unittests/ADT/STLForwardCompatTest.cpp @@ -185,7 +185,7 @@ TEST(TransformTest, ToUnderlying) { } TEST(STLForwardCompatTest, IdentityCxx20) { - llvm::identity_cxx20 identity; + llvm::identity identity; // Test with an lvalue. int X = 42; diff --git a/llvm/unittests/DebugInfo/LogicalView/CompareElementsTest.cpp b/llvm/unittests/DebugInfo/LogicalView/CompareElementsTest.cpp index e9c1fba..d3bf26b 100644 --- a/llvm/unittests/DebugInfo/LogicalView/CompareElementsTest.cpp +++ b/llvm/unittests/DebugInfo/LogicalView/CompareElementsTest.cpp @@ -75,8 +75,8 @@ public: setInstance(this); } - Error createScopes() { return LVReader::createScopes(); } - Error printScopes() { return LVReader::printScopes(); } + Error createScopes() override { return LVReader::createScopes(); } + Error printScopes() override { return LVReader::printScopes(); } void createElements(); void addElements(bool IsReference, bool IsTarget); diff --git a/llvm/unittests/DebugInfo/LogicalView/LocationRangesTest.cpp b/llvm/unittests/DebugInfo/LogicalView/LocationRangesTest.cpp index 8694971..7cd6813 100644 --- a/llvm/unittests/DebugInfo/LogicalView/LocationRangesTest.cpp +++ b/llvm/unittests/DebugInfo/LogicalView/LocationRangesTest.cpp @@ -34,7 +34,7 @@ protected: public: ReaderTest(ScopedPrinter &W) : LVReader("", "", W) { setInstance(this); } - Error createScopes() { return LVReader::createScopes(); } + Error createScopes() override { return LVReader::createScopes(); } }; // Helper function to add a logical element to a given scope. diff --git a/llvm/unittests/DebugInfo/LogicalView/LogicalElementsTest.cpp b/llvm/unittests/DebugInfo/LogicalView/LogicalElementsTest.cpp index 8aa856a..866739f 100644 --- a/llvm/unittests/DebugInfo/LogicalView/LogicalElementsTest.cpp +++ b/llvm/unittests/DebugInfo/LogicalView/LogicalElementsTest.cpp @@ -72,8 +72,8 @@ public: setInstance(this); } - Error createScopes() { return LVReader::createScopes(); } - Error printScopes() { return LVReader::printScopes(); } + Error createScopes() override { return LVReader::createScopes(); } + Error printScopes() override { return LVReader::printScopes(); } void createElements(); void addElements(); diff --git a/llvm/unittests/DebugInfo/LogicalView/SelectElementsTest.cpp b/llvm/unittests/DebugInfo/LogicalView/SelectElementsTest.cpp index 70835ce..2653347 100644 --- a/llvm/unittests/DebugInfo/LogicalView/SelectElementsTest.cpp +++ b/llvm/unittests/DebugInfo/LogicalView/SelectElementsTest.cpp @@ -60,7 +60,7 @@ public: setInstance(this); } - Error createScopes() { return LVReader::createScopes(); } + Error createScopes() override { return LVReader::createScopes(); } void createElements(); void addElements(); diff --git a/llvm/unittests/DebugInfo/LogicalView/WarningInternalTest.cpp b/llvm/unittests/DebugInfo/LogicalView/WarningInternalTest.cpp index 36c6e16..011321b 100644 --- a/llvm/unittests/DebugInfo/LogicalView/WarningInternalTest.cpp +++ b/llvm/unittests/DebugInfo/LogicalView/WarningInternalTest.cpp @@ -117,7 +117,7 @@ public: setInstance(this); } - Error createScopes() { return LVReader::createScopes(); } + Error createScopes() override { return LVReader::createScopes(); } void setMapping(); void createElements(); diff --git a/llvm/unittests/ExecutionEngine/Orc/CMakeLists.txt b/llvm/unittests/ExecutionEngine/Orc/CMakeLists.txt index 7e3ebc8..b06aa25 100644 --- a/llvm/unittests/ExecutionEngine/Orc/CMakeLists.txt +++ b/llvm/unittests/ExecutionEngine/Orc/CMakeLists.txt @@ -5,6 +5,7 @@ set(LLVM_LINK_COMPONENTS IRReader JITLink Object + ObjectYAML OrcDebugging OrcJIT OrcShared |