diff options
author | Dimitry Andric <dim@FreeBSD.org> | 2011-02-20 12:57:14 +0000 |
---|---|---|
committer | Dimitry Andric <dim@FreeBSD.org> | 2011-02-20 12:57:14 +0000 |
commit | cf099d11218cb6f6c5cce947d6738e347f07fb12 (patch) | |
tree | d2b61ce94e654cb01a254d2195259db5f9cc3f3c /unittests/ADT | |
parent | 49011b52fcba02a6051957b84705159f52fae4e4 (diff) |
Notes
Diffstat (limited to 'unittests/ADT')
-rw-r--r-- | unittests/ADT/APIntTest.cpp | 7 | ||||
-rw-r--r-- | unittests/ADT/BitVectorTest.cpp | 7 | ||||
-rw-r--r-- | unittests/ADT/FoldingSet.cpp | 39 | ||||
-rw-r--r-- | unittests/ADT/ImmutableSetTest.cpp | 48 | ||||
-rw-r--r-- | unittests/ADT/IntEqClassesTest.cpp | 107 | ||||
-rw-r--r-- | unittests/ADT/IntervalMapTest.cpp | 716 | ||||
-rw-r--r-- | unittests/ADT/Makefile | 2 | ||||
-rw-r--r-- | unittests/ADT/SmallBitVectorTest.cpp | 7 | ||||
-rw-r--r-- | unittests/ADT/SmallVectorTest.cpp | 2 | ||||
-rw-r--r-- | unittests/ADT/StringMapTest.cpp | 2 | ||||
-rw-r--r-- | unittests/ADT/StringRefTest.cpp | 2 | ||||
-rw-r--r-- | unittests/ADT/TripleTest.cpp | 80 | ||||
-rw-r--r-- | unittests/ADT/TwineTest.cpp | 8 | ||||
-rw-r--r-- | unittests/ADT/ValueMapTest.cpp | 294 |
14 files changed, 969 insertions, 352 deletions
diff --git a/unittests/ADT/APIntTest.cpp b/unittests/ADT/APIntTest.cpp index 0cb79963f5054..557d835bacda0 100644 --- a/unittests/ADT/APIntTest.cpp +++ b/unittests/ADT/APIntTest.cpp @@ -39,6 +39,9 @@ TEST(APIntTest, i128_NegativeCount) { EXPECT_EQ(-1, Minus1.getSExtValue()); } +// XFAIL this test on FreeBSD where the system gcc-4.2.1 seems to miscompile it. +#if defined(__llvm__) || !defined(__FreeBSD__) + TEST(APIntTest, i33_Count) { APInt i33minus2(33, static_cast<uint64_t>(-2), true); EXPECT_EQ(0u, i33minus2.countLeadingZeros()); @@ -50,9 +53,11 @@ TEST(APIntTest, i33_Count) { EXPECT_EQ(((uint64_t)-2)&((1ull<<33) -1), i33minus2.getZExtValue()); } +#endif + TEST(APIntTest, i65_Count) { APInt i65minus(65, 0, true); - i65minus.set(64); + i65minus.setBit(64); EXPECT_EQ(0u, i65minus.countLeadingZeros()); EXPECT_EQ(1u, i65minus.countLeadingOnes()); EXPECT_EQ(65u, i65minus.getActiveBits()); diff --git a/unittests/ADT/BitVectorTest.cpp b/unittests/ADT/BitVectorTest.cpp index a9fc133c72e26..fa663121a8a69 100644 --- a/unittests/ADT/BitVectorTest.cpp +++ b/unittests/ADT/BitVectorTest.cpp @@ -22,6 +22,7 @@ TEST(BitVectorTest, TrivialOperation) { EXPECT_EQ(0U, Vec.count()); EXPECT_EQ(0U, Vec.size()); EXPECT_FALSE(Vec.any()); + EXPECT_TRUE(Vec.all()); EXPECT_TRUE(Vec.none()); EXPECT_TRUE(Vec.empty()); @@ -29,6 +30,7 @@ TEST(BitVectorTest, TrivialOperation) { EXPECT_EQ(5U, Vec.count()); EXPECT_EQ(5U, Vec.size()); EXPECT_TRUE(Vec.any()); + EXPECT_TRUE(Vec.all()); EXPECT_FALSE(Vec.none()); EXPECT_FALSE(Vec.empty()); @@ -36,6 +38,7 @@ TEST(BitVectorTest, TrivialOperation) { EXPECT_EQ(5U, Vec.count()); EXPECT_EQ(11U, Vec.size()); EXPECT_TRUE(Vec.any()); + EXPECT_FALSE(Vec.all()); EXPECT_FALSE(Vec.none()); EXPECT_FALSE(Vec.empty()); @@ -43,6 +46,7 @@ TEST(BitVectorTest, TrivialOperation) { EXPECT_EQ(6U, Inv.count()); EXPECT_EQ(11U, Inv.size()); EXPECT_TRUE(Inv.any()); + EXPECT_FALSE(Inv.all()); EXPECT_FALSE(Inv.none()); EXPECT_FALSE(Inv.empty()); @@ -123,6 +127,7 @@ TEST(BitVectorTest, TrivialOperation) { EXPECT_EQ(0U, Vec.count()); EXPECT_EQ(130U, Vec.size()); EXPECT_FALSE(Vec.any()); + EXPECT_FALSE(Vec.all()); EXPECT_TRUE(Vec.none()); EXPECT_FALSE(Vec.empty()); @@ -130,6 +135,7 @@ TEST(BitVectorTest, TrivialOperation) { EXPECT_EQ(0U, Inv.count()); EXPECT_EQ(0U, Inv.size()); EXPECT_FALSE(Inv.any()); + EXPECT_TRUE(Inv.all()); EXPECT_TRUE(Inv.none()); EXPECT_TRUE(Inv.empty()); @@ -137,6 +143,7 @@ TEST(BitVectorTest, TrivialOperation) { EXPECT_EQ(0U, Vec.count()); EXPECT_EQ(0U, Vec.size()); EXPECT_FALSE(Vec.any()); + EXPECT_TRUE(Vec.all()); EXPECT_TRUE(Vec.none()); EXPECT_TRUE(Vec.empty()); } diff --git a/unittests/ADT/FoldingSet.cpp b/unittests/ADT/FoldingSet.cpp new file mode 100644 index 0000000000000..a18a0df957166 --- /dev/null +++ b/unittests/ADT/FoldingSet.cpp @@ -0,0 +1,39 @@ +//===- llvm/unittest/ADT/FoldingSetTest.cpp -------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// FoldingSet unit tests. +// +//===----------------------------------------------------------------------===// + +#include "gtest/gtest.h" +#include "llvm/ADT/FoldingSet.h" +#include <string> + +using namespace llvm; + +namespace { + +// Unaligned string test. +TEST(FoldingSetTest, UnalignedStringTest) { + SCOPED_TRACE("UnalignedStringTest"); + + FoldingSetNodeID a, b; + // An aligned string + std::string str1= "a test string"; + a.AddString(str1); + + // An unaligned string + std::string str2 = ">" + str1; + b.AddString(str2.c_str() + 1); + + EXPECT_EQ(a.ComputeHash(), b.ComputeHash()); +} + +} + diff --git a/unittests/ADT/ImmutableSetTest.cpp b/unittests/ADT/ImmutableSetTest.cpp index 1be510d599e39..febd441db1663 100644 --- a/unittests/ADT/ImmutableSetTest.cpp +++ b/unittests/ADT/ImmutableSetTest.cpp @@ -37,11 +37,11 @@ char ImmutableSetTest::buffer[10]; TEST_F(ImmutableSetTest, EmptyIntSetTest) { ImmutableSet<int>::Factory f; - EXPECT_TRUE(f.GetEmptySet() == f.GetEmptySet()); - EXPECT_FALSE(f.GetEmptySet() != f.GetEmptySet()); - EXPECT_TRUE(f.GetEmptySet().isEmpty()); + EXPECT_TRUE(f.getEmptySet() == f.getEmptySet()); + EXPECT_FALSE(f.getEmptySet() != f.getEmptySet()); + EXPECT_TRUE(f.getEmptySet().isEmpty()); - ImmutableSet<int> S = f.GetEmptySet(); + ImmutableSet<int> S = f.getEmptySet(); EXPECT_EQ(0u, S.getHeight()); EXPECT_TRUE(S.begin() == S.end()); EXPECT_FALSE(S.begin() != S.end()); @@ -50,9 +50,9 @@ TEST_F(ImmutableSetTest, EmptyIntSetTest) { TEST_F(ImmutableSetTest, OneElemIntSetTest) { ImmutableSet<int>::Factory f; - ImmutableSet<int> S = f.GetEmptySet(); + ImmutableSet<int> S = f.getEmptySet(); - ImmutableSet<int> S2 = f.Add(S, 3); + ImmutableSet<int> S2 = f.add(S, 3); EXPECT_TRUE(S.isEmpty()); EXPECT_FALSE(S2.isEmpty()); EXPECT_FALSE(S == S2); @@ -62,7 +62,7 @@ TEST_F(ImmutableSetTest, OneElemIntSetTest) { EXPECT_FALSE(S2.begin() == S2.end()); EXPECT_TRUE(S2.begin() != S2.end()); - ImmutableSet<int> S3 = f.Add(S, 2); + ImmutableSet<int> S3 = f.add(S, 2); EXPECT_TRUE(S.isEmpty()); EXPECT_FALSE(S3.isEmpty()); EXPECT_FALSE(S == S3); @@ -78,11 +78,11 @@ TEST_F(ImmutableSetTest, OneElemIntSetTest) { TEST_F(ImmutableSetTest, MultiElemIntSetTest) { ImmutableSet<int>::Factory f; - ImmutableSet<int> S = f.GetEmptySet(); + ImmutableSet<int> S = f.getEmptySet(); - ImmutableSet<int> S2 = f.Add(f.Add(f.Add(S, 3), 4), 5); - ImmutableSet<int> S3 = f.Add(f.Add(f.Add(S2, 9), 20), 43); - ImmutableSet<int> S4 = f.Add(S2, 9); + ImmutableSet<int> S2 = f.add(f.add(f.add(S, 3), 4), 5); + ImmutableSet<int> S3 = f.add(f.add(f.add(S2, 9), 20), 43); + ImmutableSet<int> S4 = f.add(S2, 9); EXPECT_TRUE(S.isEmpty()); EXPECT_FALSE(S2.isEmpty()); @@ -116,11 +116,11 @@ TEST_F(ImmutableSetTest, MultiElemIntSetTest) { TEST_F(ImmutableSetTest, RemoveIntSetTest) { ImmutableSet<int>::Factory f; - ImmutableSet<int> S = f.GetEmptySet(); + ImmutableSet<int> S = f.getEmptySet(); - ImmutableSet<int> S2 = f.Add(f.Add(S, 4), 5); - ImmutableSet<int> S3 = f.Add(S2, 3); - ImmutableSet<int> S4 = f.Remove(S3, 3); + ImmutableSet<int> S2 = f.add(f.add(S, 4), 5); + ImmutableSet<int> S3 = f.add(S2, 3); + ImmutableSet<int> S4 = f.remove(S3, 3); EXPECT_TRUE(S3.contains(3)); EXPECT_FALSE(S2.contains(3)); @@ -139,10 +139,10 @@ TEST_F(ImmutableSetTest, RemoveIntSetTest) { TEST_F(ImmutableSetTest, CallbackCharSetTest) { ImmutableSet<char>::Factory f; - ImmutableSet<char> S = f.GetEmptySet(); + ImmutableSet<char> S = f.getEmptySet(); - ImmutableSet<char> S2 = f.Add(f.Add(f.Add(S, 'a'), 'e'), 'i'); - ImmutableSet<char> S3 = f.Add(f.Add(S2, 'o'), 'u'); + ImmutableSet<char> S2 = f.add(f.add(f.add(S, 'a'), 'e'), 'i'); + ImmutableSet<char> S3 = f.add(f.add(S2, 'o'), 'u'); S3.foreach<MyIter>(); @@ -151,10 +151,10 @@ TEST_F(ImmutableSetTest, CallbackCharSetTest) { TEST_F(ImmutableSetTest, Callback2CharSetTest) { ImmutableSet<char>::Factory f; - ImmutableSet<char> S = f.GetEmptySet(); + ImmutableSet<char> S = f.getEmptySet(); - ImmutableSet<char> S2 = f.Add(f.Add(f.Add(S, 'b'), 'c'), 'd'); - ImmutableSet<char> S3 = f.Add(f.Add(f.Add(S2, 'f'), 'g'), 'h'); + ImmutableSet<char> S2 = f.add(f.add(f.add(S, 'b'), 'c'), 'd'); + ImmutableSet<char> S3 = f.add(f.add(f.add(S2, 'f'), 'g'), 'h'); MyIter obj; S3.foreach<MyIter>(obj); @@ -174,10 +174,10 @@ TEST_F(ImmutableSetTest, Callback2CharSetTest) { TEST_F(ImmutableSetTest, IterLongSetTest) { ImmutableSet<long>::Factory f; - ImmutableSet<long> S = f.GetEmptySet(); + ImmutableSet<long> S = f.getEmptySet(); - ImmutableSet<long> S2 = f.Add(f.Add(f.Add(S, 0), 1), 2); - ImmutableSet<long> S3 = f.Add(f.Add(f.Add(S2, 3), 4), 5); + ImmutableSet<long> S2 = f.add(f.add(f.add(S, 0), 1), 2); + ImmutableSet<long> S3 = f.add(f.add(f.add(S2, 3), 4), 5); int i = 0; for (ImmutableSet<long>::iterator I = S.begin(), E = S.end(); I != E; ++I) { diff --git a/unittests/ADT/IntEqClassesTest.cpp b/unittests/ADT/IntEqClassesTest.cpp new file mode 100644 index 0000000000000..fc908c1e8bff3 --- /dev/null +++ b/unittests/ADT/IntEqClassesTest.cpp @@ -0,0 +1,107 @@ +//===---- ADT/IntEqClassesTest.cpp - IntEqClasses unit tests ----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/IntEqClasses.h" +#include "gtest/gtest.h" + +using namespace llvm; + +namespace { + +TEST(IntEqClasses, Simple) { + IntEqClasses ec(10); + + ec.join(0, 1); + ec.join(3, 2); + ec.join(4, 5); + ec.join(7, 6); + + EXPECT_EQ(0u, ec.findLeader(0)); + EXPECT_EQ(0u, ec.findLeader(1)); + EXPECT_EQ(2u, ec.findLeader(2)); + EXPECT_EQ(2u, ec.findLeader(3)); + EXPECT_EQ(4u, ec.findLeader(4)); + EXPECT_EQ(4u, ec.findLeader(5)); + EXPECT_EQ(6u, ec.findLeader(6)); + EXPECT_EQ(6u, ec.findLeader(7)); + EXPECT_EQ(8u, ec.findLeader(8)); + EXPECT_EQ(9u, ec.findLeader(9)); + + // join two non-leaders. + ec.join(1, 3); + + EXPECT_EQ(0u, ec.findLeader(0)); + EXPECT_EQ(0u, ec.findLeader(1)); + EXPECT_EQ(0u, ec.findLeader(2)); + EXPECT_EQ(0u, ec.findLeader(3)); + EXPECT_EQ(4u, ec.findLeader(4)); + EXPECT_EQ(4u, ec.findLeader(5)); + EXPECT_EQ(6u, ec.findLeader(6)); + EXPECT_EQ(6u, ec.findLeader(7)); + EXPECT_EQ(8u, ec.findLeader(8)); + EXPECT_EQ(9u, ec.findLeader(9)); + + // join two leaders. + ec.join(4, 8); + + EXPECT_EQ(0u, ec.findLeader(0)); + EXPECT_EQ(0u, ec.findLeader(1)); + EXPECT_EQ(0u, ec.findLeader(2)); + EXPECT_EQ(0u, ec.findLeader(3)); + EXPECT_EQ(4u, ec.findLeader(4)); + EXPECT_EQ(4u, ec.findLeader(5)); + EXPECT_EQ(6u, ec.findLeader(6)); + EXPECT_EQ(6u, ec.findLeader(7)); + EXPECT_EQ(4u, ec.findLeader(8)); + EXPECT_EQ(9u, ec.findLeader(9)); + + // join mixed. + ec.join(9, 1); + + EXPECT_EQ(0u, ec.findLeader(0)); + EXPECT_EQ(0u, ec.findLeader(1)); + EXPECT_EQ(0u, ec.findLeader(2)); + EXPECT_EQ(0u, ec.findLeader(3)); + EXPECT_EQ(4u, ec.findLeader(4)); + EXPECT_EQ(4u, ec.findLeader(5)); + EXPECT_EQ(6u, ec.findLeader(6)); + EXPECT_EQ(6u, ec.findLeader(7)); + EXPECT_EQ(4u, ec.findLeader(8)); + EXPECT_EQ(0u, ec.findLeader(9)); + + // compressed map. + ec.compress(); + EXPECT_EQ(3u, ec.getNumClasses()); + + EXPECT_EQ(0u, ec[0]); + EXPECT_EQ(0u, ec[1]); + EXPECT_EQ(0u, ec[2]); + EXPECT_EQ(0u, ec[3]); + EXPECT_EQ(1u, ec[4]); + EXPECT_EQ(1u, ec[5]); + EXPECT_EQ(2u, ec[6]); + EXPECT_EQ(2u, ec[7]); + EXPECT_EQ(1u, ec[8]); + EXPECT_EQ(0u, ec[9]); + + // uncompressed map. + ec.uncompress(); + EXPECT_EQ(0u, ec.findLeader(0)); + EXPECT_EQ(0u, ec.findLeader(1)); + EXPECT_EQ(0u, ec.findLeader(2)); + EXPECT_EQ(0u, ec.findLeader(3)); + EXPECT_EQ(4u, ec.findLeader(4)); + EXPECT_EQ(4u, ec.findLeader(5)); + EXPECT_EQ(6u, ec.findLeader(6)); + EXPECT_EQ(6u, ec.findLeader(7)); + EXPECT_EQ(4u, ec.findLeader(8)); + EXPECT_EQ(0u, ec.findLeader(9)); +} + +} // end anonymous namespace diff --git a/unittests/ADT/IntervalMapTest.cpp b/unittests/ADT/IntervalMapTest.cpp new file mode 100644 index 0000000000000..b5556d265ae49 --- /dev/null +++ b/unittests/ADT/IntervalMapTest.cpp @@ -0,0 +1,716 @@ +//===---- ADT/IntervalMapTest.cpp - IntervalMap unit tests ------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/IntervalMap.h" +#include "gtest/gtest.h" + +using namespace llvm; + +namespace { + +typedef IntervalMap<unsigned, unsigned, 4> UUMap; + +// Empty map tests +TEST(IntervalMapTest, EmptyMap) { + UUMap::Allocator allocator; + UUMap map(allocator); + EXPECT_TRUE(map.empty()); + + // Lookup on empty map. + EXPECT_EQ(0u, map.lookup(0)); + EXPECT_EQ(7u, map.lookup(0, 7)); + EXPECT_EQ(0u, map.lookup(~0u-1)); + EXPECT_EQ(7u, map.lookup(~0u-1, 7)); + + // Iterators. + EXPECT_TRUE(map.begin() == map.begin()); + EXPECT_TRUE(map.begin() == map.end()); + EXPECT_TRUE(map.end() == map.end()); + EXPECT_FALSE(map.begin() != map.begin()); + EXPECT_FALSE(map.begin() != map.end()); + EXPECT_FALSE(map.end() != map.end()); + EXPECT_FALSE(map.begin().valid()); + EXPECT_FALSE(map.end().valid()); + UUMap::iterator I = map.begin(); + EXPECT_FALSE(I.valid()); + EXPECT_TRUE(I == map.end()); + + // Default constructor and cross-constness compares. + UUMap::const_iterator CI; + CI = map.begin(); + EXPECT_TRUE(CI == I); + UUMap::iterator I2; + I2 = map.end(); + EXPECT_TRUE(I2 == CI); +} + +// Single entry map tests +TEST(IntervalMapTest, SingleEntryMap) { + UUMap::Allocator allocator; + UUMap map(allocator); + map.insert(100, 150, 1); + EXPECT_FALSE(map.empty()); + + // Lookup around interval. + EXPECT_EQ(0u, map.lookup(0)); + EXPECT_EQ(0u, map.lookup(99)); + EXPECT_EQ(1u, map.lookup(100)); + EXPECT_EQ(1u, map.lookup(101)); + EXPECT_EQ(1u, map.lookup(125)); + EXPECT_EQ(1u, map.lookup(149)); + EXPECT_EQ(1u, map.lookup(150)); + EXPECT_EQ(0u, map.lookup(151)); + EXPECT_EQ(0u, map.lookup(200)); + EXPECT_EQ(0u, map.lookup(~0u-1)); + + // Iterators. + EXPECT_TRUE(map.begin() == map.begin()); + EXPECT_FALSE(map.begin() == map.end()); + EXPECT_TRUE(map.end() == map.end()); + EXPECT_TRUE(map.begin().valid()); + EXPECT_FALSE(map.end().valid()); + + // Iter deref. + UUMap::iterator I = map.begin(); + ASSERT_TRUE(I.valid()); + EXPECT_EQ(100u, I.start()); + EXPECT_EQ(150u, I.stop()); + EXPECT_EQ(1u, I.value()); + + // Preincrement. + ++I; + EXPECT_FALSE(I.valid()); + EXPECT_FALSE(I == map.begin()); + EXPECT_TRUE(I == map.end()); + + // PreDecrement. + --I; + ASSERT_TRUE(I.valid()); + EXPECT_EQ(100u, I.start()); + EXPECT_EQ(150u, I.stop()); + EXPECT_EQ(1u, I.value()); + EXPECT_TRUE(I == map.begin()); + EXPECT_FALSE(I == map.end()); + + // Change the value. + I.setValue(2); + ASSERT_TRUE(I.valid()); + EXPECT_EQ(100u, I.start()); + EXPECT_EQ(150u, I.stop()); + EXPECT_EQ(2u, I.value()); + + // Grow the bounds. + I.setStart(0); + ASSERT_TRUE(I.valid()); + EXPECT_EQ(0u, I.start()); + EXPECT_EQ(150u, I.stop()); + EXPECT_EQ(2u, I.value()); + + I.setStop(200); + ASSERT_TRUE(I.valid()); + EXPECT_EQ(0u, I.start()); + EXPECT_EQ(200u, I.stop()); + EXPECT_EQ(2u, I.value()); + + // Shrink the bounds. + I.setStart(150); + ASSERT_TRUE(I.valid()); + EXPECT_EQ(150u, I.start()); + EXPECT_EQ(200u, I.stop()); + EXPECT_EQ(2u, I.value()); + + I.setStop(160); + ASSERT_TRUE(I.valid()); + EXPECT_EQ(150u, I.start()); + EXPECT_EQ(160u, I.stop()); + EXPECT_EQ(2u, I.value()); + + // Erase last elem. + I.erase(); + EXPECT_TRUE(map.empty()); + EXPECT_EQ(0, std::distance(map.begin(), map.end())); +} + +// Flat coalescing tests. +TEST(IntervalMapTest, RootCoalescing) { + UUMap::Allocator allocator; + UUMap map(allocator); + map.insert(100, 150, 1); + + // Coalesce from the left. + map.insert(90, 99, 1); + EXPECT_EQ(1, std::distance(map.begin(), map.end())); + EXPECT_EQ(90u, map.start()); + EXPECT_EQ(150u, map.stop()); + + // Coalesce from the right. + map.insert(151, 200, 1); + EXPECT_EQ(1, std::distance(map.begin(), map.end())); + EXPECT_EQ(90u, map.start()); + EXPECT_EQ(200u, map.stop()); + + // Non-coalesce from the left. + map.insert(60, 89, 2); + EXPECT_EQ(2, std::distance(map.begin(), map.end())); + EXPECT_EQ(60u, map.start()); + EXPECT_EQ(200u, map.stop()); + EXPECT_EQ(2u, map.lookup(89)); + EXPECT_EQ(1u, map.lookup(90)); + + UUMap::iterator I = map.begin(); + EXPECT_EQ(60u, I.start()); + EXPECT_EQ(89u, I.stop()); + EXPECT_EQ(2u, I.value()); + ++I; + EXPECT_EQ(90u, I.start()); + EXPECT_EQ(200u, I.stop()); + EXPECT_EQ(1u, I.value()); + ++I; + EXPECT_FALSE(I.valid()); + + // Non-coalesce from the right. + map.insert(201, 210, 2); + EXPECT_EQ(3, std::distance(map.begin(), map.end())); + EXPECT_EQ(60u, map.start()); + EXPECT_EQ(210u, map.stop()); + EXPECT_EQ(2u, map.lookup(201)); + EXPECT_EQ(1u, map.lookup(200)); + + // Erase from the left. + map.begin().erase(); + EXPECT_EQ(2, std::distance(map.begin(), map.end())); + EXPECT_EQ(90u, map.start()); + EXPECT_EQ(210u, map.stop()); + + // Erase from the right. + (--map.end()).erase(); + EXPECT_EQ(1, std::distance(map.begin(), map.end())); + EXPECT_EQ(90u, map.start()); + EXPECT_EQ(200u, map.stop()); + + // Add non-coalescing, then trigger coalescing with setValue. + map.insert(80, 89, 2); + map.insert(201, 210, 2); + EXPECT_EQ(3, std::distance(map.begin(), map.end())); + (++map.begin()).setValue(2); + EXPECT_EQ(1, std::distance(map.begin(), map.end())); + I = map.begin(); + ASSERT_TRUE(I.valid()); + EXPECT_EQ(80u, I.start()); + EXPECT_EQ(210u, I.stop()); + EXPECT_EQ(2u, I.value()); +} + +// Flat multi-coalescing tests. +TEST(IntervalMapTest, RootMultiCoalescing) { + UUMap::Allocator allocator; + UUMap map(allocator); + map.insert(140, 150, 1); + map.insert(160, 170, 1); + map.insert(100, 110, 1); + map.insert(120, 130, 1); + EXPECT_EQ(4, std::distance(map.begin(), map.end())); + EXPECT_EQ(100u, map.start()); + EXPECT_EQ(170u, map.stop()); + + // Verify inserts. + UUMap::iterator I = map.begin(); + EXPECT_EQ(100u, I.start()); + EXPECT_EQ(110u, I.stop()); + ++I; + EXPECT_EQ(120u, I.start()); + EXPECT_EQ(130u, I.stop()); + ++I; + EXPECT_EQ(140u, I.start()); + EXPECT_EQ(150u, I.stop()); + ++I; + EXPECT_EQ(160u, I.start()); + EXPECT_EQ(170u, I.stop()); + ++I; + EXPECT_FALSE(I.valid()); + + // Test advanceTo on flat tree. + I = map.begin(); + I.advanceTo(135); + ASSERT_TRUE(I.valid()); + EXPECT_EQ(140u, I.start()); + EXPECT_EQ(150u, I.stop()); + + I.advanceTo(145); + ASSERT_TRUE(I.valid()); + EXPECT_EQ(140u, I.start()); + EXPECT_EQ(150u, I.stop()); + + I.advanceTo(200); + EXPECT_FALSE(I.valid()); + + I.advanceTo(300); + EXPECT_FALSE(I.valid()); + + // Coalesce left with followers. + // [100;110] [120;130] [140;150] [160;170] + map.insert(111, 115, 1); + I = map.begin(); + ASSERT_TRUE(I.valid()); + EXPECT_EQ(100u, I.start()); + EXPECT_EQ(115u, I.stop()); + ++I; + ASSERT_TRUE(I.valid()); + EXPECT_EQ(120u, I.start()); + EXPECT_EQ(130u, I.stop()); + ++I; + ASSERT_TRUE(I.valid()); + EXPECT_EQ(140u, I.start()); + EXPECT_EQ(150u, I.stop()); + ++I; + ASSERT_TRUE(I.valid()); + EXPECT_EQ(160u, I.start()); + EXPECT_EQ(170u, I.stop()); + ++I; + EXPECT_FALSE(I.valid()); + + // Coalesce right with followers. + // [100;115] [120;130] [140;150] [160;170] + map.insert(135, 139, 1); + I = map.begin(); + ASSERT_TRUE(I.valid()); + EXPECT_EQ(100u, I.start()); + EXPECT_EQ(115u, I.stop()); + ++I; + ASSERT_TRUE(I.valid()); + EXPECT_EQ(120u, I.start()); + EXPECT_EQ(130u, I.stop()); + ++I; + ASSERT_TRUE(I.valid()); + EXPECT_EQ(135u, I.start()); + EXPECT_EQ(150u, I.stop()); + ++I; + ASSERT_TRUE(I.valid()); + EXPECT_EQ(160u, I.start()); + EXPECT_EQ(170u, I.stop()); + ++I; + EXPECT_FALSE(I.valid()); + + // Coalesce left and right with followers. + // [100;115] [120;130] [135;150] [160;170] + map.insert(131, 134, 1); + I = map.begin(); + ASSERT_TRUE(I.valid()); + EXPECT_EQ(100u, I.start()); + EXPECT_EQ(115u, I.stop()); + ++I; + ASSERT_TRUE(I.valid()); + EXPECT_EQ(120u, I.start()); + EXPECT_EQ(150u, I.stop()); + ++I; + ASSERT_TRUE(I.valid()); + EXPECT_EQ(160u, I.start()); + EXPECT_EQ(170u, I.stop()); + ++I; + EXPECT_FALSE(I.valid()); + + // Test clear() on non-branched map. + map.clear(); + EXPECT_TRUE(map.empty()); + EXPECT_TRUE(map.begin() == map.end()); +} + +// Branched, non-coalescing tests. +TEST(IntervalMapTest, Branched) { + UUMap::Allocator allocator; + UUMap map(allocator); + + // Insert enough intervals to force a branched tree. + // This creates 9 leaf nodes with 11 elements each, tree height = 1. + for (unsigned i = 1; i < 100; ++i) { + map.insert(10*i, 10*i+5, i); + EXPECT_EQ(10u, map.start()); + EXPECT_EQ(10*i+5, map.stop()); + } + + // Tree limits. + EXPECT_FALSE(map.empty()); + EXPECT_EQ(10u, map.start()); + EXPECT_EQ(995u, map.stop()); + + // Tree lookup. + for (unsigned i = 1; i < 100; ++i) { + EXPECT_EQ(0u, map.lookup(10*i-1)); + EXPECT_EQ(i, map.lookup(10*i)); + EXPECT_EQ(i, map.lookup(10*i+5)); + EXPECT_EQ(0u, map.lookup(10*i+6)); + } + + // Forward iteration. + UUMap::iterator I = map.begin(); + for (unsigned i = 1; i < 100; ++i) { + ASSERT_TRUE(I.valid()); + EXPECT_EQ(10*i, I.start()); + EXPECT_EQ(10*i+5, I.stop()); + EXPECT_EQ(i, *I); + ++I; + } + EXPECT_FALSE(I.valid()); + EXPECT_TRUE(I == map.end()); + + // Backwards iteration. + for (unsigned i = 99; i; --i) { + --I; + ASSERT_TRUE(I.valid()); + EXPECT_EQ(10*i, I.start()); + EXPECT_EQ(10*i+5, I.stop()); + EXPECT_EQ(i, *I); + } + EXPECT_TRUE(I == map.begin()); + + // Test advanceTo in same node. + I.advanceTo(20); + ASSERT_TRUE(I.valid()); + EXPECT_EQ(20u, I.start()); + EXPECT_EQ(25u, I.stop()); + + // Change value, no coalescing. + I.setValue(0); + ASSERT_TRUE(I.valid()); + EXPECT_EQ(20u, I.start()); + EXPECT_EQ(25u, I.stop()); + EXPECT_EQ(0u, I.value()); + + // Close the gap right, no coalescing. + I.setStop(29); + ASSERT_TRUE(I.valid()); + EXPECT_EQ(20u, I.start()); + EXPECT_EQ(29u, I.stop()); + EXPECT_EQ(0u, I.value()); + + // Change value, no coalescing. + I.setValue(2); + ASSERT_TRUE(I.valid()); + EXPECT_EQ(20u, I.start()); + EXPECT_EQ(29u, I.stop()); + EXPECT_EQ(2u, I.value()); + + // Change value, now coalescing. + I.setValue(3); + ASSERT_TRUE(I.valid()); + EXPECT_EQ(20u, I.start()); + EXPECT_EQ(35u, I.stop()); + EXPECT_EQ(3u, I.value()); + + // Close the gap, now coalescing. + I.setValue(4); + ASSERT_TRUE(I.valid()); + I.setStop(39); + ASSERT_TRUE(I.valid()); + EXPECT_EQ(20u, I.start()); + EXPECT_EQ(45u, I.stop()); + EXPECT_EQ(4u, I.value()); + + // advanceTo another node. + I.advanceTo(200); + ASSERT_TRUE(I.valid()); + EXPECT_EQ(200u, I.start()); + EXPECT_EQ(205u, I.stop()); + + // Close the gap left, no coalescing. + I.setStart(196); + ASSERT_TRUE(I.valid()); + EXPECT_EQ(196u, I.start()); + EXPECT_EQ(205u, I.stop()); + EXPECT_EQ(20u, I.value()); + + // Change value, no coalescing. + I.setValue(0); + ASSERT_TRUE(I.valid()); + EXPECT_EQ(196u, I.start()); + EXPECT_EQ(205u, I.stop()); + EXPECT_EQ(0u, I.value()); + + // Change value, now coalescing. + I.setValue(19); + ASSERT_TRUE(I.valid()); + EXPECT_EQ(190u, I.start()); + EXPECT_EQ(205u, I.stop()); + EXPECT_EQ(19u, I.value()); + + // Close the gap, now coalescing. + I.setValue(18); + ASSERT_TRUE(I.valid()); + I.setStart(186); + ASSERT_TRUE(I.valid()); + EXPECT_EQ(180u, I.start()); + EXPECT_EQ(205u, I.stop()); + EXPECT_EQ(18u, I.value()); + + // Erase from the front. + I = map.begin(); + for (unsigned i = 0; i != 20; ++i) { + I.erase(); + EXPECT_TRUE(I == map.begin()); + EXPECT_FALSE(map.empty()); + EXPECT_EQ(I.start(), map.start()); + EXPECT_EQ(995u, map.stop()); + } + + // Test clear() on branched map. + map.clear(); + EXPECT_TRUE(map.empty()); + EXPECT_TRUE(map.begin() == map.end()); +} + +// Branched, high, non-coalescing tests. +TEST(IntervalMapTest, Branched2) { + UUMap::Allocator allocator; + UUMap map(allocator); + + // Insert enough intervals to force a height >= 2 tree. + for (unsigned i = 1; i < 1000; ++i) + map.insert(10*i, 10*i+5, i); + + // Tree limits. + EXPECT_FALSE(map.empty()); + EXPECT_EQ(10u, map.start()); + EXPECT_EQ(9995u, map.stop()); + + // Tree lookup. + for (unsigned i = 1; i < 1000; ++i) { + EXPECT_EQ(0u, map.lookup(10*i-1)); + EXPECT_EQ(i, map.lookup(10*i)); + EXPECT_EQ(i, map.lookup(10*i+5)); + EXPECT_EQ(0u, map.lookup(10*i+6)); + } + + // Forward iteration. + UUMap::iterator I = map.begin(); + for (unsigned i = 1; i < 1000; ++i) { + ASSERT_TRUE(I.valid()); + EXPECT_EQ(10*i, I.start()); + EXPECT_EQ(10*i+5, I.stop()); + EXPECT_EQ(i, *I); + ++I; + } + EXPECT_FALSE(I.valid()); + EXPECT_TRUE(I == map.end()); + + // Backwards iteration. + for (unsigned i = 999; i; --i) { + --I; + ASSERT_TRUE(I.valid()); + EXPECT_EQ(10*i, I.start()); + EXPECT_EQ(10*i+5, I.stop()); + EXPECT_EQ(i, *I); + } + EXPECT_TRUE(I == map.begin()); + + // Test advanceTo in same node. + I.advanceTo(20); + ASSERT_TRUE(I.valid()); + EXPECT_EQ(20u, I.start()); + EXPECT_EQ(25u, I.stop()); + + // advanceTo sibling leaf node. + I.advanceTo(200); + ASSERT_TRUE(I.valid()); + EXPECT_EQ(200u, I.start()); + EXPECT_EQ(205u, I.stop()); + + // advanceTo further. + I.advanceTo(2000); + ASSERT_TRUE(I.valid()); + EXPECT_EQ(2000u, I.start()); + EXPECT_EQ(2005u, I.stop()); + + // advanceTo beyond end() + I.advanceTo(20000); + EXPECT_FALSE(I.valid()); + + // end().advanceTo() is valid as long as x > map.stop() + I.advanceTo(30000); + EXPECT_FALSE(I.valid()); + + // Test clear() on branched map. + map.clear(); + EXPECT_TRUE(map.empty()); + EXPECT_TRUE(map.begin() == map.end()); +} + +// Random insertions, coalescing to a single interval. +TEST(IntervalMapTest, RandomCoalescing) { + UUMap::Allocator allocator; + UUMap map(allocator); + + // This is a poor PRNG with maximal period: + // x_n = 5 x_{n-1} + 1 mod 2^N + + unsigned x = 100; + for (unsigned i = 0; i != 4096; ++i) { + map.insert(10*x, 10*x+9, 1); + EXPECT_GE(10*x, map.start()); + EXPECT_LE(10*x+9, map.stop()); + x = (5*x+1)%4096; + } + + // Map should be fully coalesced after that exercise. + EXPECT_FALSE(map.empty()); + EXPECT_EQ(0u, map.start()); + EXPECT_EQ(40959u, map.stop()); + EXPECT_EQ(1, std::distance(map.begin(), map.end())); + +} + +TEST(IntervalMapOverlapsTest, SmallMaps) { + typedef IntervalMapOverlaps<UUMap,UUMap> UUOverlaps; + UUMap::Allocator allocator; + UUMap mapA(allocator); + UUMap mapB(allocator); + + // empty, empty. + EXPECT_FALSE(UUOverlaps(mapA, mapB).valid()); + + mapA.insert(1, 2, 3); + + // full, empty + EXPECT_FALSE(UUOverlaps(mapA, mapB).valid()); + // empty, full + EXPECT_FALSE(UUOverlaps(mapB, mapA).valid()); + + mapB.insert(3, 4, 5); + + // full, full, non-overlapping + EXPECT_FALSE(UUOverlaps(mapA, mapB).valid()); + EXPECT_FALSE(UUOverlaps(mapB, mapA).valid()); + + // Add an overlapping segment. + mapA.insert(4, 5, 6); + + UUOverlaps AB(mapA, mapB); + ASSERT_TRUE(AB.valid()); + EXPECT_EQ(4u, AB.a().start()); + EXPECT_EQ(3u, AB.b().start()); + ++AB; + EXPECT_FALSE(AB.valid()); + + UUOverlaps BA(mapB, mapA); + ASSERT_TRUE(BA.valid()); + EXPECT_EQ(3u, BA.a().start()); + EXPECT_EQ(4u, BA.b().start()); + // advance past end. + BA.advanceTo(6); + EXPECT_FALSE(BA.valid()); + // advance an invalid iterator. + BA.advanceTo(7); + EXPECT_FALSE(BA.valid()); +} + +TEST(IntervalMapOverlapsTest, BigMaps) { + typedef IntervalMapOverlaps<UUMap,UUMap> UUOverlaps; + UUMap::Allocator allocator; + UUMap mapA(allocator); + UUMap mapB(allocator); + + // [0;4] [10;14] [20;24] ... + for (unsigned n = 0; n != 100; ++n) + mapA.insert(10*n, 10*n+4, n); + + // [5;6] [15;16] [25;26] ... + for (unsigned n = 10; n != 20; ++n) + mapB.insert(10*n+5, 10*n+6, n); + + // [208;209] [218;219] ... + for (unsigned n = 20; n != 30; ++n) + mapB.insert(10*n+8, 10*n+9, n); + + // insert some overlapping segments. + mapB.insert(400, 400, 400); + mapB.insert(401, 401, 401); + mapB.insert(402, 500, 402); + mapB.insert(600, 601, 402); + + UUOverlaps AB(mapA, mapB); + ASSERT_TRUE(AB.valid()); + EXPECT_EQ(400u, AB.a().start()); + EXPECT_EQ(400u, AB.b().start()); + ++AB; + ASSERT_TRUE(AB.valid()); + EXPECT_EQ(400u, AB.a().start()); + EXPECT_EQ(401u, AB.b().start()); + ++AB; + ASSERT_TRUE(AB.valid()); + EXPECT_EQ(400u, AB.a().start()); + EXPECT_EQ(402u, AB.b().start()); + ++AB; + ASSERT_TRUE(AB.valid()); + EXPECT_EQ(410u, AB.a().start()); + EXPECT_EQ(402u, AB.b().start()); + ++AB; + ASSERT_TRUE(AB.valid()); + EXPECT_EQ(420u, AB.a().start()); + EXPECT_EQ(402u, AB.b().start()); + AB.skipB(); + ASSERT_TRUE(AB.valid()); + EXPECT_EQ(600u, AB.a().start()); + EXPECT_EQ(600u, AB.b().start()); + ++AB; + EXPECT_FALSE(AB.valid()); + + // Test advanceTo. + UUOverlaps AB2(mapA, mapB); + AB2.advanceTo(410); + ASSERT_TRUE(AB2.valid()); + EXPECT_EQ(410u, AB2.a().start()); + EXPECT_EQ(402u, AB2.b().start()); + + // It is valid to advanceTo with any monotonic sequence. + AB2.advanceTo(411); + ASSERT_TRUE(AB2.valid()); + EXPECT_EQ(410u, AB2.a().start()); + EXPECT_EQ(402u, AB2.b().start()); + + // Check reversed maps. + UUOverlaps BA(mapB, mapA); + ASSERT_TRUE(BA.valid()); + EXPECT_EQ(400u, BA.b().start()); + EXPECT_EQ(400u, BA.a().start()); + ++BA; + ASSERT_TRUE(BA.valid()); + EXPECT_EQ(400u, BA.b().start()); + EXPECT_EQ(401u, BA.a().start()); + ++BA; + ASSERT_TRUE(BA.valid()); + EXPECT_EQ(400u, BA.b().start()); + EXPECT_EQ(402u, BA.a().start()); + ++BA; + ASSERT_TRUE(BA.valid()); + EXPECT_EQ(410u, BA.b().start()); + EXPECT_EQ(402u, BA.a().start()); + ++BA; + ASSERT_TRUE(BA.valid()); + EXPECT_EQ(420u, BA.b().start()); + EXPECT_EQ(402u, BA.a().start()); + BA.skipA(); + ASSERT_TRUE(BA.valid()); + EXPECT_EQ(600u, BA.b().start()); + EXPECT_EQ(600u, BA.a().start()); + ++BA; + EXPECT_FALSE(BA.valid()); + + // Test advanceTo. + UUOverlaps BA2(mapB, mapA); + BA2.advanceTo(410); + ASSERT_TRUE(BA2.valid()); + EXPECT_EQ(410u, BA2.b().start()); + EXPECT_EQ(402u, BA2.a().start()); + + BA2.advanceTo(411); + ASSERT_TRUE(BA2.valid()); + EXPECT_EQ(410u, BA2.b().start()); + EXPECT_EQ(402u, BA2.a().start()); +} + +} // namespace diff --git a/unittests/ADT/Makefile b/unittests/ADT/Makefile index fe0832894d32b..c255a0b44d091 100644 --- a/unittests/ADT/Makefile +++ b/unittests/ADT/Makefile @@ -9,7 +9,7 @@ LEVEL = ../.. TESTNAME = ADT -LINK_COMPONENTS := core support +LINK_COMPONENTS := support include $(LEVEL)/Makefile.config diff --git a/unittests/ADT/SmallBitVectorTest.cpp b/unittests/ADT/SmallBitVectorTest.cpp index 9c69aad5a9730..c4dda9e88d445 100644 --- a/unittests/ADT/SmallBitVectorTest.cpp +++ b/unittests/ADT/SmallBitVectorTest.cpp @@ -19,6 +19,7 @@ TEST(SmallBitVectorTest, TrivialOperation) { EXPECT_EQ(0U, Vec.count()); EXPECT_EQ(0U, Vec.size()); EXPECT_FALSE(Vec.any()); + EXPECT_TRUE(Vec.all()); EXPECT_TRUE(Vec.none()); EXPECT_TRUE(Vec.empty()); @@ -26,6 +27,7 @@ TEST(SmallBitVectorTest, TrivialOperation) { EXPECT_EQ(5U, Vec.count()); EXPECT_EQ(5U, Vec.size()); EXPECT_TRUE(Vec.any()); + EXPECT_TRUE(Vec.all()); EXPECT_FALSE(Vec.none()); EXPECT_FALSE(Vec.empty()); @@ -33,6 +35,7 @@ TEST(SmallBitVectorTest, TrivialOperation) { EXPECT_EQ(5U, Vec.count()); EXPECT_EQ(11U, Vec.size()); EXPECT_TRUE(Vec.any()); + EXPECT_FALSE(Vec.all()); EXPECT_FALSE(Vec.none()); EXPECT_FALSE(Vec.empty()); @@ -40,6 +43,7 @@ TEST(SmallBitVectorTest, TrivialOperation) { EXPECT_EQ(6U, Inv.count()); EXPECT_EQ(11U, Inv.size()); EXPECT_TRUE(Inv.any()); + EXPECT_FALSE(Inv.all()); EXPECT_FALSE(Inv.none()); EXPECT_FALSE(Inv.empty()); @@ -120,6 +124,7 @@ TEST(SmallBitVectorTest, TrivialOperation) { EXPECT_EQ(0U, Vec.count()); EXPECT_EQ(130U, Vec.size()); EXPECT_FALSE(Vec.any()); + EXPECT_FALSE(Vec.all()); EXPECT_TRUE(Vec.none()); EXPECT_FALSE(Vec.empty()); @@ -127,6 +132,7 @@ TEST(SmallBitVectorTest, TrivialOperation) { EXPECT_EQ(0U, Inv.count()); EXPECT_EQ(0U, Inv.size()); EXPECT_FALSE(Inv.any()); + EXPECT_TRUE(Inv.all()); EXPECT_TRUE(Inv.none()); EXPECT_TRUE(Inv.empty()); @@ -134,6 +140,7 @@ TEST(SmallBitVectorTest, TrivialOperation) { EXPECT_EQ(0U, Vec.count()); EXPECT_EQ(0U, Vec.size()); EXPECT_FALSE(Vec.any()); + EXPECT_TRUE(Vec.all()); EXPECT_TRUE(Vec.none()); EXPECT_TRUE(Vec.empty()); } diff --git a/unittests/ADT/SmallVectorTest.cpp b/unittests/ADT/SmallVectorTest.cpp index 78dc393e5c18d..f4da54dbca1a6 100644 --- a/unittests/ADT/SmallVectorTest.cpp +++ b/unittests/ADT/SmallVectorTest.cpp @@ -77,7 +77,7 @@ public: return c0.getValue() == c1.getValue(); } - friend bool ATTRIBUTE_UNUSED + friend bool LLVM_ATTRIBUTE_UNUSED operator!=(const Constructable & c0, const Constructable & c1) { return c0.getValue() != c1.getValue(); } diff --git a/unittests/ADT/StringMapTest.cpp b/unittests/ADT/StringMapTest.cpp index 413f068d49069..ea91348a5bdf7 100644 --- a/unittests/ADT/StringMapTest.cpp +++ b/unittests/ADT/StringMapTest.cpp @@ -9,7 +9,7 @@ #include "gtest/gtest.h" #include "llvm/ADT/StringMap.h" -#include "llvm/System/DataTypes.h" +#include "llvm/Support/DataTypes.h" using namespace llvm; namespace { diff --git a/unittests/ADT/StringRefTest.cpp b/unittests/ADT/StringRefTest.cpp index 7e4d0dcd413fc..5731e4abaf152 100644 --- a/unittests/ADT/StringRefTest.cpp +++ b/unittests/ADT/StringRefTest.cpp @@ -16,7 +16,7 @@ using namespace llvm; namespace llvm { std::ostream &operator<<(std::ostream &OS, const StringRef &S) { - OS << S; + OS << S.str(); return OS; } diff --git a/unittests/ADT/TripleTest.cpp b/unittests/ADT/TripleTest.cpp index 067f5e5116cdd..160b69253b6fa 100644 --- a/unittests/ADT/TripleTest.cpp +++ b/unittests/ADT/TripleTest.cpp @@ -79,16 +79,25 @@ TEST(TripleTest, ParsedIDs) { EXPECT_EQ(Triple::x86, T.getArch()); EXPECT_EQ(Triple::Apple, T.getVendor()); EXPECT_EQ(Triple::Darwin, T.getOS()); + EXPECT_EQ(Triple::UnknownEnvironment, T.getEnvironment()); T = Triple("x86_64-pc-linux-gnu"); EXPECT_EQ(Triple::x86_64, T.getArch()); EXPECT_EQ(Triple::PC, T.getVendor()); EXPECT_EQ(Triple::Linux, T.getOS()); + EXPECT_EQ(Triple::GNU, T.getEnvironment()); T = Triple("powerpc-dunno-notsure"); EXPECT_EQ(Triple::ppc, T.getArch()); EXPECT_EQ(Triple::UnknownVendor, T.getVendor()); EXPECT_EQ(Triple::UnknownOS, T.getOS()); + EXPECT_EQ(Triple::UnknownEnvironment, T.getEnvironment()); + + T = Triple("arm-none-none-eabi"); + EXPECT_EQ(Triple::arm, T.getArch()); + EXPECT_EQ(Triple::UnknownVendor, T.getVendor()); + EXPECT_EQ(Triple::UnknownOS, T.getOS()); + EXPECT_EQ(Triple::EABI, T.getEnvironment()); T = Triple("huh"); EXPECT_EQ(Triple::UnknownArch, T.getArch()); @@ -105,6 +114,7 @@ static std::string Join(StringRef A, StringRef B, StringRef C, StringRef D) { } TEST(TripleTest, Normalization) { + EXPECT_EQ("", Triple::normalize("")); EXPECT_EQ("-", Triple::normalize("-")); EXPECT_EQ("--", Triple::normalize("--")); @@ -119,10 +129,12 @@ TEST(TripleTest, Normalization) { EXPECT_EQ("i386-b-c", Triple::normalize("i386-b-c")); EXPECT_EQ("i386-a-c", Triple::normalize("a-i386-c")); EXPECT_EQ("i386-a-b", Triple::normalize("a-b-i386")); + EXPECT_EQ("i386-a-b-c", Triple::normalize("a-b-c-i386")); EXPECT_EQ("a-pc-c", Triple::normalize("a-pc-c")); EXPECT_EQ("-pc-b-c", Triple::normalize("pc-b-c")); EXPECT_EQ("a-pc-b", Triple::normalize("a-b-pc")); + EXPECT_EQ("a-pc-b-c", Triple::normalize("a-b-c-pc")); EXPECT_EQ("a-b-linux", Triple::normalize("a-b-linux")); EXPECT_EQ("--linux-b-c", Triple::normalize("linux-b-c")); @@ -137,10 +149,11 @@ TEST(TripleTest, Normalization) { EXPECT_EQ("-pc", Triple::normalize("pc")); EXPECT_EQ("--linux", Triple::normalize("linux")); + EXPECT_EQ("x86_64--linux-gnu", Triple::normalize("x86_64-gnu-linux")); + // Check that normalizing a permutated set of valid components returns a // triple with the unpermuted components. StringRef C[4]; - C[3] = "environment"; for (int Arch = 1+Triple::UnknownArch; Arch < Triple::InvalidArch; ++Arch) { C[0] = Triple::getArchTypeName(Triple::ArchType(Arch)); for (int Vendor = 1+Triple::UnknownVendor; Vendor <= Triple::PC; @@ -149,46 +162,52 @@ TEST(TripleTest, Normalization) { for (int OS = 1+Triple::UnknownOS; OS <= Triple::Minix; ++OS) { C[2] = Triple::getOSTypeName(Triple::OSType(OS)); - std::string E = Join(C[0], C[1], C[2]); - std::string F = Join(C[0], C[1], C[2], C[3]); - EXPECT_EQ(E, Triple::normalize(Join(C[0], C[1], C[2]))); - EXPECT_EQ(F, Triple::normalize(Join(C[0], C[1], C[2], C[3]))); - // If a value has multiple interpretations, then the permutation // test will inevitably fail. Currently this is only the case for // "psp" which parses as both an architecture and an O/S. if (OS == Triple::Psp) continue; + std::string E = Join(C[0], C[1], C[2]); + EXPECT_EQ(E, Triple::normalize(Join(C[0], C[1], C[2]))); + EXPECT_EQ(E, Triple::normalize(Join(C[0], C[2], C[1]))); EXPECT_EQ(E, Triple::normalize(Join(C[1], C[2], C[0]))); EXPECT_EQ(E, Triple::normalize(Join(C[1], C[0], C[2]))); EXPECT_EQ(E, Triple::normalize(Join(C[2], C[0], C[1]))); EXPECT_EQ(E, Triple::normalize(Join(C[2], C[1], C[0]))); - EXPECT_EQ(F, Triple::normalize(Join(C[0], C[1], C[3], C[2]))); - EXPECT_EQ(F, Triple::normalize(Join(C[0], C[2], C[3], C[1]))); - EXPECT_EQ(F, Triple::normalize(Join(C[0], C[2], C[1], C[3]))); - EXPECT_EQ(F, Triple::normalize(Join(C[0], C[3], C[1], C[2]))); - EXPECT_EQ(F, Triple::normalize(Join(C[0], C[3], C[2], C[1]))); - EXPECT_EQ(F, Triple::normalize(Join(C[1], C[2], C[3], C[0]))); - EXPECT_EQ(F, Triple::normalize(Join(C[1], C[2], C[0], C[3]))); - EXPECT_EQ(F, Triple::normalize(Join(C[1], C[3], C[0], C[2]))); - EXPECT_EQ(F, Triple::normalize(Join(C[1], C[3], C[2], C[0]))); - EXPECT_EQ(F, Triple::normalize(Join(C[1], C[0], C[2], C[3]))); - EXPECT_EQ(F, Triple::normalize(Join(C[1], C[0], C[3], C[2]))); - EXPECT_EQ(F, Triple::normalize(Join(C[2], C[3], C[0], C[1]))); - EXPECT_EQ(F, Triple::normalize(Join(C[2], C[3], C[1], C[0]))); - EXPECT_EQ(F, Triple::normalize(Join(C[2], C[0], C[1], C[3]))); - EXPECT_EQ(F, Triple::normalize(Join(C[2], C[0], C[3], C[1]))); - EXPECT_EQ(F, Triple::normalize(Join(C[2], C[1], C[3], C[0]))); - EXPECT_EQ(F, Triple::normalize(Join(C[2], C[1], C[0], C[3]))); - EXPECT_EQ(F, Triple::normalize(Join(C[3], C[0], C[1], C[2]))); - EXPECT_EQ(F, Triple::normalize(Join(C[3], C[0], C[2], C[1]))); - EXPECT_EQ(F, Triple::normalize(Join(C[3], C[1], C[2], C[0]))); - EXPECT_EQ(F, Triple::normalize(Join(C[3], C[1], C[0], C[2]))); - EXPECT_EQ(F, Triple::normalize(Join(C[3], C[2], C[0], C[1]))); - EXPECT_EQ(F, Triple::normalize(Join(C[3], C[2], C[1], C[0]))); + for (int Env = 1+Triple::UnknownEnvironment; Env <= Triple::MachO; + ++Env) { + C[3] = Triple::getEnvironmentTypeName(Triple::EnvironmentType(Env)); + + std::string F = Join(C[0], C[1], C[2], C[3]); + EXPECT_EQ(F, Triple::normalize(Join(C[0], C[1], C[2], C[3]))); + + EXPECT_EQ(F, Triple::normalize(Join(C[0], C[1], C[3], C[2]))); + EXPECT_EQ(F, Triple::normalize(Join(C[0], C[2], C[3], C[1]))); + EXPECT_EQ(F, Triple::normalize(Join(C[0], C[2], C[1], C[3]))); + EXPECT_EQ(F, Triple::normalize(Join(C[0], C[3], C[1], C[2]))); + EXPECT_EQ(F, Triple::normalize(Join(C[0], C[3], C[2], C[1]))); + EXPECT_EQ(F, Triple::normalize(Join(C[1], C[2], C[3], C[0]))); + EXPECT_EQ(F, Triple::normalize(Join(C[1], C[2], C[0], C[3]))); + EXPECT_EQ(F, Triple::normalize(Join(C[1], C[3], C[0], C[2]))); + EXPECT_EQ(F, Triple::normalize(Join(C[1], C[3], C[2], C[0]))); + EXPECT_EQ(F, Triple::normalize(Join(C[1], C[0], C[2], C[3]))); + EXPECT_EQ(F, Triple::normalize(Join(C[1], C[0], C[3], C[2]))); + EXPECT_EQ(F, Triple::normalize(Join(C[2], C[3], C[0], C[1]))); + EXPECT_EQ(F, Triple::normalize(Join(C[2], C[3], C[1], C[0]))); + EXPECT_EQ(F, Triple::normalize(Join(C[2], C[0], C[1], C[3]))); + EXPECT_EQ(F, Triple::normalize(Join(C[2], C[0], C[3], C[1]))); + EXPECT_EQ(F, Triple::normalize(Join(C[2], C[1], C[3], C[0]))); + EXPECT_EQ(F, Triple::normalize(Join(C[2], C[1], C[0], C[3]))); + EXPECT_EQ(F, Triple::normalize(Join(C[3], C[0], C[1], C[2]))); + EXPECT_EQ(F, Triple::normalize(Join(C[3], C[0], C[2], C[1]))); + EXPECT_EQ(F, Triple::normalize(Join(C[3], C[1], C[2], C[0]))); + EXPECT_EQ(F, Triple::normalize(Join(C[3], C[1], C[0], C[2]))); + EXPECT_EQ(F, Triple::normalize(Join(C[3], C[2], C[0], C[1]))); + EXPECT_EQ(F, Triple::normalize(Join(C[3], C[2], C[1], C[0]))); + } } } } @@ -203,6 +222,7 @@ TEST(TripleTest, Normalization) { EXPECT_EQ("i486--linux-gnu", Triple::normalize("i486-linux-gnu")); // i486-pc-linux-gnu EXPECT_EQ("i386-redhat-linux", Triple::normalize("i386-redhat-linux")); // i386-redhat-linux-gnu EXPECT_EQ("i686--linux", Triple::normalize("i686-linux")); // i686-pc-linux-gnu + EXPECT_EQ("arm-none--eabi", Triple::normalize("arm-none-eabi")); // arm-none-eabi } TEST(TripleTest, MutateName) { @@ -210,6 +230,7 @@ TEST(TripleTest, MutateName) { EXPECT_EQ(Triple::UnknownArch, T.getArch()); EXPECT_EQ(Triple::UnknownVendor, T.getVendor()); EXPECT_EQ(Triple::UnknownOS, T.getOS()); + EXPECT_EQ(Triple::UnknownEnvironment, T.getEnvironment()); T.setArchName("i386"); EXPECT_EQ(Triple::x86, T.getArch()); @@ -243,6 +264,7 @@ TEST(TripleTest, MutateName) { EXPECT_EQ(Triple::PC, T.getVendor()); EXPECT_EQ(Triple::Darwin, T.getOS()); EXPECT_EQ("i386-pc-darwin", T.getTriple()); + } } diff --git a/unittests/ADT/TwineTest.cpp b/unittests/ADT/TwineTest.cpp index 61e8a0ac37cbb..57f54cb0060f5 100644 --- a/unittests/ADT/TwineTest.cpp +++ b/unittests/ADT/TwineTest.cpp @@ -9,6 +9,7 @@ #include "gtest/gtest.h" #include "llvm/ADT/Twine.h" +#include "llvm/ADT/SmallString.h" #include "llvm/Support/raw_ostream.h" using namespace llvm; @@ -69,6 +70,13 @@ TEST(TwineTest, Concat) { repr(Twine("a").concat(Twine("b").concat(Twine("c"))))); } +TEST(TwineTest, toNullTerminatedStringRef) { + SmallString<8> storage; + EXPECT_EQ(0, *Twine("hello").toNullTerminatedStringRef(storage).end()); + EXPECT_EQ(0, + *Twine(StringRef("hello")).toNullTerminatedStringRef(storage).end()); +} + // I suppose linking in the entire code generator to add a unit test to check // the code size of the concat operation is overkill... :) diff --git a/unittests/ADT/ValueMapTest.cpp b/unittests/ADT/ValueMapTest.cpp deleted file mode 100644 index 152e8eaaf1f18..0000000000000 --- a/unittests/ADT/ValueMapTest.cpp +++ /dev/null @@ -1,294 +0,0 @@ -//===- llvm/unittest/ADT/ValueMapTest.cpp - ValueMap unit tests -*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#include "llvm/ADT/ValueMap.h" -#include "llvm/Instructions.h" -#include "llvm/LLVMContext.h" -#include "llvm/ADT/OwningPtr.h" -#include "llvm/Config/config.h" - -#include "gtest/gtest.h" - -using namespace llvm; - -namespace { - -// Test fixture -template<typename T> -class ValueMapTest : public testing::Test { -protected: - Constant *ConstantV; - OwningPtr<BitCastInst> BitcastV; - OwningPtr<BinaryOperator> AddV; - - ValueMapTest() : - ConstantV(ConstantInt::get(Type::getInt32Ty(getGlobalContext()), 0)), - BitcastV(new BitCastInst(ConstantV, Type::getInt32Ty(getGlobalContext()))), - AddV(BinaryOperator::CreateAdd(ConstantV, ConstantV)) { - } -}; - -// Run everything on Value*, a subtype to make sure that casting works as -// expected, and a const subtype to make sure we cast const correctly. -typedef ::testing::Types<Value, Instruction, const Instruction> KeyTypes; -TYPED_TEST_CASE(ValueMapTest, KeyTypes); - -TYPED_TEST(ValueMapTest, Null) { - ValueMap<TypeParam*, int> VM1; - VM1[NULL] = 7; - EXPECT_EQ(7, VM1.lookup(NULL)); -} - -TYPED_TEST(ValueMapTest, FollowsValue) { - ValueMap<TypeParam*, int> VM; - VM[this->BitcastV.get()] = 7; - EXPECT_EQ(7, VM.lookup(this->BitcastV.get())); - EXPECT_EQ(0, VM.count(this->AddV.get())); - this->BitcastV->replaceAllUsesWith(this->AddV.get()); - EXPECT_EQ(7, VM.lookup(this->AddV.get())); - EXPECT_EQ(0, VM.count(this->BitcastV.get())); - this->AddV.reset(); - EXPECT_EQ(0, VM.count(this->AddV.get())); - EXPECT_EQ(0, VM.count(this->BitcastV.get())); - EXPECT_EQ(0U, VM.size()); -} - -TYPED_TEST(ValueMapTest, OperationsWork) { - ValueMap<TypeParam*, int> VM; - ValueMap<TypeParam*, int> VM2(16); (void)VM2; - typename ValueMapConfig<TypeParam*>::ExtraData Data; - ValueMap<TypeParam*, int> VM3(Data, 16); (void)VM3; - EXPECT_TRUE(VM.empty()); - - VM[this->BitcastV.get()] = 7; - - // Find: - typename ValueMap<TypeParam*, int>::iterator I = - VM.find(this->BitcastV.get()); - ASSERT_TRUE(I != VM.end()); - EXPECT_EQ(this->BitcastV.get(), I->first); - EXPECT_EQ(7, I->second); - EXPECT_TRUE(VM.find(this->AddV.get()) == VM.end()); - - // Const find: - const ValueMap<TypeParam*, int> &CVM = VM; - typename ValueMap<TypeParam*, int>::const_iterator CI = - CVM.find(this->BitcastV.get()); - ASSERT_TRUE(CI != CVM.end()); - EXPECT_EQ(this->BitcastV.get(), CI->first); - EXPECT_EQ(7, CI->second); - EXPECT_TRUE(CVM.find(this->AddV.get()) == CVM.end()); - - // Insert: - std::pair<typename ValueMap<TypeParam*, int>::iterator, bool> InsertResult1 = - VM.insert(std::make_pair(this->AddV.get(), 3)); - EXPECT_EQ(this->AddV.get(), InsertResult1.first->first); - EXPECT_EQ(3, InsertResult1.first->second); - EXPECT_TRUE(InsertResult1.second); - EXPECT_EQ(true, VM.count(this->AddV.get())); - std::pair<typename ValueMap<TypeParam*, int>::iterator, bool> InsertResult2 = - VM.insert(std::make_pair(this->AddV.get(), 5)); - EXPECT_EQ(this->AddV.get(), InsertResult2.first->first); - EXPECT_EQ(3, InsertResult2.first->second); - EXPECT_FALSE(InsertResult2.second); - - // Erase: - VM.erase(InsertResult2.first); - EXPECT_EQ(0U, VM.count(this->AddV.get())); - EXPECT_EQ(1U, VM.count(this->BitcastV.get())); - VM.erase(this->BitcastV.get()); - EXPECT_EQ(0U, VM.count(this->BitcastV.get())); - EXPECT_EQ(0U, VM.size()); - - // Range insert: - SmallVector<std::pair<Instruction*, int>, 2> Elems; - Elems.push_back(std::make_pair(this->AddV.get(), 1)); - Elems.push_back(std::make_pair(this->BitcastV.get(), 2)); - VM.insert(Elems.begin(), Elems.end()); - EXPECT_EQ(1, VM.lookup(this->AddV.get())); - EXPECT_EQ(2, VM.lookup(this->BitcastV.get())); -} - -template<typename ExpectedType, typename VarType> -void CompileAssertHasType(VarType) { - typedef char assert[is_same<ExpectedType, VarType>::value ? 1 : -1]; -} - -TYPED_TEST(ValueMapTest, Iteration) { - ValueMap<TypeParam*, int> VM; - VM[this->BitcastV.get()] = 2; - VM[this->AddV.get()] = 3; - size_t size = 0; - for (typename ValueMap<TypeParam*, int>::iterator I = VM.begin(), E = VM.end(); - I != E; ++I) { - ++size; - std::pair<TypeParam*, int> value = *I; (void)value; - CompileAssertHasType<TypeParam*>(I->first); - if (I->second == 2) { - EXPECT_EQ(this->BitcastV.get(), I->first); - I->second = 5; - } else if (I->second == 3) { - EXPECT_EQ(this->AddV.get(), I->first); - I->second = 6; - } else { - ADD_FAILURE() << "Iterated through an extra value."; - } - } - EXPECT_EQ(2U, size); - EXPECT_EQ(5, VM[this->BitcastV.get()]); - EXPECT_EQ(6, VM[this->AddV.get()]); - - size = 0; - // Cast to const ValueMap to avoid a bug in DenseMap's iterators. - const ValueMap<TypeParam*, int>& CVM = VM; - for (typename ValueMap<TypeParam*, int>::const_iterator I = CVM.begin(), - E = CVM.end(); I != E; ++I) { - ++size; - std::pair<TypeParam*, int> value = *I; (void)value; - CompileAssertHasType<TypeParam*>(I->first); - if (I->second == 5) { - EXPECT_EQ(this->BitcastV.get(), I->first); - } else if (I->second == 6) { - EXPECT_EQ(this->AddV.get(), I->first); - } else { - ADD_FAILURE() << "Iterated through an extra value."; - } - } - EXPECT_EQ(2U, size); -} - -TYPED_TEST(ValueMapTest, DefaultCollisionBehavior) { - // By default, we overwrite the old value with the replaced value. - ValueMap<TypeParam*, int> VM; - VM[this->BitcastV.get()] = 7; - VM[this->AddV.get()] = 9; - this->BitcastV->replaceAllUsesWith(this->AddV.get()); - EXPECT_EQ(0, VM.count(this->BitcastV.get())); - EXPECT_EQ(9, VM.lookup(this->AddV.get())); -} - -TYPED_TEST(ValueMapTest, ConfiguredCollisionBehavior) { - // TODO: Implement this when someone needs it. -} - -template<typename KeyT> -struct LockMutex : ValueMapConfig<KeyT> { - struct ExtraData { - sys::Mutex *M; - bool *CalledRAUW; - bool *CalledDeleted; - }; - static void onRAUW(const ExtraData &Data, KeyT Old, KeyT New) { - *Data.CalledRAUW = true; - EXPECT_FALSE(Data.M->tryacquire()) << "Mutex should already be locked."; - } - static void onDelete(const ExtraData &Data, KeyT Old) { - *Data.CalledDeleted = true; - EXPECT_FALSE(Data.M->tryacquire()) << "Mutex should already be locked."; - } - static sys::Mutex *getMutex(const ExtraData &Data) { return Data.M; } -}; -#if ENABLE_THREADS -TYPED_TEST(ValueMapTest, LocksMutex) { - sys::Mutex M(false); // Not recursive. - bool CalledRAUW = false, CalledDeleted = false; - typename LockMutex<TypeParam*>::ExtraData Data = - {&M, &CalledRAUW, &CalledDeleted}; - ValueMap<TypeParam*, int, LockMutex<TypeParam*> > VM(Data); - VM[this->BitcastV.get()] = 7; - this->BitcastV->replaceAllUsesWith(this->AddV.get()); - this->AddV.reset(); - EXPECT_TRUE(CalledRAUW); - EXPECT_TRUE(CalledDeleted); -} -#endif - -template<typename KeyT> -struct NoFollow : ValueMapConfig<KeyT> { - enum { FollowRAUW = false }; -}; - -TYPED_TEST(ValueMapTest, NoFollowRAUW) { - ValueMap<TypeParam*, int, NoFollow<TypeParam*> > VM; - VM[this->BitcastV.get()] = 7; - EXPECT_EQ(7, VM.lookup(this->BitcastV.get())); - EXPECT_EQ(0, VM.count(this->AddV.get())); - this->BitcastV->replaceAllUsesWith(this->AddV.get()); - EXPECT_EQ(7, VM.lookup(this->BitcastV.get())); - EXPECT_EQ(0, VM.lookup(this->AddV.get())); - this->AddV.reset(); - EXPECT_EQ(7, VM.lookup(this->BitcastV.get())); - EXPECT_EQ(0, VM.lookup(this->AddV.get())); - this->BitcastV.reset(); - EXPECT_EQ(0, VM.lookup(this->BitcastV.get())); - EXPECT_EQ(0, VM.lookup(this->AddV.get())); - EXPECT_EQ(0U, VM.size()); -} - -template<typename KeyT> -struct CountOps : ValueMapConfig<KeyT> { - struct ExtraData { - int *Deletions; - int *RAUWs; - }; - - static void onRAUW(const ExtraData &Data, KeyT Old, KeyT New) { - ++*Data.RAUWs; - } - static void onDelete(const ExtraData &Data, KeyT Old) { - ++*Data.Deletions; - } -}; - -TYPED_TEST(ValueMapTest, CallsConfig) { - int Deletions = 0, RAUWs = 0; - typename CountOps<TypeParam*>::ExtraData Data = {&Deletions, &RAUWs}; - ValueMap<TypeParam*, int, CountOps<TypeParam*> > VM(Data); - VM[this->BitcastV.get()] = 7; - this->BitcastV->replaceAllUsesWith(this->AddV.get()); - EXPECT_EQ(0, Deletions); - EXPECT_EQ(1, RAUWs); - this->AddV.reset(); - EXPECT_EQ(1, Deletions); - EXPECT_EQ(1, RAUWs); - this->BitcastV.reset(); - EXPECT_EQ(1, Deletions); - EXPECT_EQ(1, RAUWs); -} - -template<typename KeyT> -struct ModifyingConfig : ValueMapConfig<KeyT> { - // We'll put a pointer here back to the ValueMap this key is in, so - // that we can modify it (and clobber *this) before the ValueMap - // tries to do the same modification. In previous versions of - // ValueMap, that exploded. - typedef ValueMap<KeyT, int, ModifyingConfig<KeyT> > **ExtraData; - - static void onRAUW(ExtraData Map, KeyT Old, KeyT New) { - (*Map)->erase(Old); - } - static void onDelete(ExtraData Map, KeyT Old) { - (*Map)->erase(Old); - } -}; -TYPED_TEST(ValueMapTest, SurvivesModificationByConfig) { - ValueMap<TypeParam*, int, ModifyingConfig<TypeParam*> > *MapAddress; - ValueMap<TypeParam*, int, ModifyingConfig<TypeParam*> > VM(&MapAddress); - MapAddress = &VM; - // Now the ModifyingConfig can modify the Map inside a callback. - VM[this->BitcastV.get()] = 7; - this->BitcastV->replaceAllUsesWith(this->AddV.get()); - EXPECT_FALSE(VM.count(this->BitcastV.get())); - EXPECT_FALSE(VM.count(this->AddV.get())); - VM[this->AddV.get()] = 7; - this->AddV.reset(); - EXPECT_FALSE(VM.count(this->AddV.get())); -} - -} |