Fix Deque.swap for deques with inline capacity

Source/wtf/DequeTest.cpp

Index: Source/wtf/DequeTest.cpp
diff --git a/Source/wtf/DequeTest.cpp b/Source/wtf/DequeTest.cpp
index e343158dfc6fec0f7cd0f874f5011a5a6a50ebec..3027c928b6284a5029b6facca0cffa5d06086030 100644
--- a/Source/wtf/DequeTest.cpp
+++ b/Source/wtf/DequeTest.cpp
@@ -41,9 +41,10 @@ TEST(DequeTest, Basic)
     EXPECT_EQ(0ul, intDeque.size());
 }
 
-void checkNumberSequence(Deque<int>& deque, int from, int to, bool increment)
+template<size_t inlineCapacity>
+void checkNumberSequence(Deque<int, inlineCapacity>& deque, int from, int to, bool increment)
 {
-    Deque<int>::iterator it = increment ? deque.begin() : deque.end();
+    typename Deque<int, inlineCapacity>::iterator it = increment ? deque.begin() : deque.end();
     int step = from < to ? 1 : -1;
     for (int i = from; i != to + step; i += step) {
         if (!increment)
@@ -57,9 +58,10 @@ void checkNumberSequence(Deque<int>& deque, int from, int to, bool increment)
     EXPECT_EQ(increment ? deque.end() : deque.begin(), it);
 }
 
-void checkNumberSequenceReverse(Deque<int>& deque, int from, int to, bool increment)
+template<size_t inlineCapacity>
+void checkNumberSequenceReverse(Deque<int, inlineCapacity>& deque, int from, int to, bool increment)
 {
-    Deque<int>::reverse_iterator it = increment ? deque.rbegin() : deque.rend();
+    typename Deque<int, inlineCapacity>::reverse_iterator it = increment ? deque.rbegin() : deque.rend();
     int step = from < to ? 1 : -1;
     for (int i = from; i != to + step; i += step) {
         if (!increment)
@@ -73,9 +75,10 @@ void checkNumberSequenceReverse(Deque<int>& deque, int from, int to, bool increm
     EXPECT_EQ(increment ? deque.rend() : deque.rbegin(), it);
 }
 
-TEST(DequeTest, Reverse)
+template<size_t inlineCapacity>
+void reverseTest()
 {
-    Deque<int> intDeque;
+    Deque<int, inlineCapacity> intDeque;
     intDeque.append(10);
     intDeque.append(11);
     intDeque.append(12);
@@ -109,7 +112,7 @@ TEST(DequeTest, Reverse)
     checkNumberSequenceReverse(intDeque, 199, 191, true);
     checkNumberSequenceReverse(intDeque, 191, 199, false);
 
-    Deque<int> intDeque2;
+    Deque<int, inlineCapacity> intDeque2;

[Ken Russell (switch to Gerrit), 2014/07/17 18:39:58]

Throughout this file and VectorTest.cpp, it seems to me that the following
boundary conditions need to be tested:

 - deque or vector 1's inline capacity = 0, deque 2's inline capacity = 0
 - deque or vector 1's inline capacity = 0, deque 2's inline capacity > 0
 - deque or vector 1's inline capacity > 0, deque 2's inline capacity = 0
 - deque or vector 1's inline capacity > 0 and == deque 2's inline capacity
 - deque or vector 1's inline capacity > 0 and > than deque 2's inline capacity,
also > 0
 - deque or vector 1's inline capacity > 0 and < than deque 2's inline capacity,
also > 0

Could you please either argue why these conditions don't all need to be tested,
or modify the tests to add these? Thanks.

[Erik Corry, 2014/07/18 07:16:09]

The template system doesn't allow you to swap if the inlineCapacity does not
match, and you can't swap a vector with a deque or vice versa.  So the tests
that hit inline capacities of 0, 2 and 10 with up to 11 elements in the
collections should be sufficient.

I'll modify the tests to use more different fullnesses.

     swap(intDeque, intDeque2);
 
     checkNumberSequence(intDeque2, 191, 199, true);
@@ -132,6 +135,12 @@ TEST(DequeTest, Reverse)
     checkNumberSequenceReverse(intDeque2, 191, 199, false);
 }
 
+TEST(DequeTest, Reverse)
+{
+    reverseTest<0>();
+    reverseTest<2>();
+}
+
 class DestructCounter {
 public:
     explicit DestructCounter(int i, int* destructNumber)
@@ -147,9 +156,8 @@ private:
     int* m_destructNumber;
 };
 
-typedef WTF::Deque<OwnPtr<DestructCounter> > OwnPtrDeque;
-
-TEST(DequeTest, OwnPtr)
+template<typename OwnPtrDeque>
+void ownPtrTest()
 {
     int destructNumber = 0;
     OwnPtrDeque deque;
@@ -164,7 +172,7 @@ TEST(DequeTest, OwnPtr)
     EXPECT_EQ(0, destructNumber);
 
     size_t index = 0;
-    for (OwnPtrDeque::iterator iter = deque.begin(); iter != deque.end(); ++iter) {
+    for (typename OwnPtrDeque::iterator iter = deque.begin(); iter != deque.end(); ++iter) {
         OwnPtr<DestructCounter>& refCounter = *iter;
         EXPECT_EQ(index, static_cast<size_t>(refCounter->get()));
         EXPECT_EQ(index, static_cast<size_t>((*refCounter).get()));
@@ -172,7 +180,7 @@ TEST(DequeTest, OwnPtr)
     }
     EXPECT_EQ(0, destructNumber);
 
-    OwnPtrDeque::iterator it = deque.begin();
+    typename OwnPtrDeque::iterator it = deque.begin();
     for (index = 0; index < deque.size(); ++index) {
         OwnPtr<DestructCounter>& refCounter = *it;
         EXPECT_EQ(index, static_cast<size_t>(refCounter->get()));
@@ -215,6 +223,13 @@ TEST(DequeTest, OwnPtr)
     EXPECT_EQ(count, static_cast<size_t>(destructNumber));
 }
 
+TEST(DequeTest, OwnPtr)
+{
+    ownPtrTest<WTF::Deque<OwnPtr<DestructCounter> > >();
+    ownPtrTest<WTF::Deque<OwnPtr<DestructCounter>, 2> >();
+}
+
+
 // WrappedInt class will fail if it was memmoved or memcpyed.
 static HashSet<void*> constructedWrappedInts;
 class WrappedInt {
@@ -253,11 +268,12 @@ private:
     int m_i;
 };
 
-TEST(DequeTest, SwapWithoutInlineCapacity)
+template<size_t inlineCapacity>
+void swapWithOrWithoutInlineCapacity()
 {
-    Deque<WrappedInt> dequeA;
+    Deque<WrappedInt, inlineCapacity> dequeA;
     dequeA.append(WrappedInt(1));
-    Deque<WrappedInt> dequeB;
+    Deque<WrappedInt, inlineCapacity> dequeB;
     dequeB.append(WrappedInt(2));
 
     ASSERT_EQ(dequeA.size(), dequeB.size());
@@ -297,4 +313,147 @@ TEST(DequeTest, SwapWithoutInlineCapacity)
     dequeB.swap(dequeA);
 }
 
+TEST(DequeTest, SwapWithOrWithoutInlineCapacity)
+{
+    swapWithOrWithoutInlineCapacity<0>();
+    swapWithOrWithoutInlineCapacity<2>();
+}
+
+class LivenessCounter {
+public:
+    void ref() { s_live++; }
+    void deref() { s_live--; }
+
+    static unsigned s_live;
+};
+
+unsigned LivenessCounter::s_live = 0;
+
+bool fairlyPrime(int i)
+{
+    return (i % 2) && (i % 3) && (i % 5) && (i % 7);
+}
+
+template<size_t inlineCapacity>
+void theBigSwapTest()
+{
+    LivenessCounter::s_live = 0;
+    LivenessCounter counter;
+    EXPECT_EQ(0u, LivenessCounter::s_live);
+
+    Deque<RefPtr<LivenessCounter>, inlineCapacity> deque;
+    Deque<RefPtr<LivenessCounter>, inlineCapacity> deque2;
+    deque.append(&counter);
+    deque2.append(&counter);
+    EXPECT_EQ(2u, LivenessCounter::s_live);
+
+    for (unsigned i = 0; i < 13; i++) {
+        if (!fairlyPrime(i))
+            continue;
+        for (unsigned j = i; j < 13; j++) {
+            if (!fairlyPrime(j))
+                continue;
+            deque.clear();
+            deque2.clear();
+            EXPECT_EQ(0u, LivenessCounter::s_live);
+            for (unsigned k = 0; k < j; k++)
+                deque.append(&counter);
+            EXPECT_EQ(j, LivenessCounter::s_live);
+            EXPECT_EQ(j, deque.size());
+            for (unsigned k = 0; k < i; k++)
+                deque.removeFirst();
+
+            EXPECT_EQ(j - i, LivenessCounter::s_live);
+            EXPECT_EQ(j - i, deque.size());
+            deque.swap(deque2);
+            EXPECT_EQ(j - i, LivenessCounter::s_live);
+            EXPECT_EQ(0u, deque.size());
+            EXPECT_EQ(j - i, deque2.size());
+            deque.swap(deque2);
+            EXPECT_EQ(j - i, LivenessCounter::s_live);
+
+            deque2.append(&counter);
+            deque2.append(&counter);
+            deque2.append(&counter);
+
+            for (unsigned k = 0; k < 13; k++) {
+                EXPECT_EQ(3 + j - i, LivenessCounter::s_live);
+                EXPECT_EQ(j - i, deque.size());
+                EXPECT_EQ(3u, deque2.size());
+                deque.swap(deque2);
+                EXPECT_EQ(3 + j - i, LivenessCounter::s_live);
+                EXPECT_EQ(j - i, deque2.size());
+                EXPECT_EQ(3u, deque.size());
+                deque.swap(deque2);
+                EXPECT_EQ(3 + j - i, LivenessCounter::s_live);
+                EXPECT_EQ(j - i, deque.size());
+                EXPECT_EQ(3u, deque2.size());
+
+                deque2.removeFirst();
+                deque2.append(&counter);
+            }
+        }
+    }
+
+}
+
+TEST(DequeTest, BigSwapTest)
+{
+    theBigSwapTest<0>();
+    theBigSwapTest<2>();
+    theBigSwapTest<10>();
+}
+
+template<size_t inlineCapacity>
+void swapValuesTest()
+{
+    Deque<unsigned, inlineCapacity> deque;
+    Deque<unsigned, inlineCapacity> deque2;
+
+    for (unsigned pad = 0; pad < 13; pad++) {
+        if (!fairlyPrime(pad))
+            continue;
+        for (unsigned pad2 = 0; pad2 < 13; pad2++) {
+            if (!fairlyPrime(pad2))
+                continue;
+            for (unsigned size = 0; size < 13; size++) {
+                if (!fairlyPrime(size))
+                    continue;
+                for (unsigned size2 = 0; size2 < 13; size2++) {
+                    if (!fairlyPrime(size2))
+                        continue;
+                    deque.clear();
+                    deque2.clear();
+                    for (unsigned i = 0; i < pad; i++)
+                        deque.append(103);
+                    for (unsigned i = 0; i < pad2; i++)
+                        deque2.append(888);
+                    for (unsigned i = 0; i < size; i++)
+                        deque.append(i);
+                    for (unsigned i = 0; i < size2; i++)
+                        deque2.append(i + 42);
+                    for (unsigned i = 0; i < pad; i++)
+                        EXPECT_EQ(103u, deque.takeFirst());
+                    for (unsigned i = 0; i < pad2; i++)
+                        EXPECT_EQ(888u, deque2.takeFirst());
+                    EXPECT_EQ(size, deque.size());
+                    EXPECT_EQ(size2, deque2.size());
+                    deque.swap(deque2);
+                    for (unsigned i = 0; i < size; i++)
+                        EXPECT_EQ(i, deque2.takeFirst());
+                    for (unsigned i = 0; i < size2; i++)
+                        EXPECT_EQ(i + 42, deque.takeFirst());
+                }
+            }
+        }
+    }
+}
+
+TEST(DequeTest, SwapValuesTest)
+{
+    swapValuesTest<0>();
+    swapValuesTest<2>();
+    swapValuesTest<10>();
+}
+
 } // namespace