Deque: Add HeapDeque and prevent buggy use of swap and operator=

Source/platform/heap/HeapTest.cpp

 /*
  * Copyright (C) 2013 Google Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are
  * met:
  *
  *     * Redistributions of source code must retain the above copyright
  * notice, this list of conditions and the following disclaimer.
  *     * Redistributions in binary form must reproduce the above
@@ skipping 1844 matching lines @@
 
 class Container : public GarbageCollected<Container> {
 public:
     static Container* create() { return new Container(); }
     HeapHashMap<Member<IntWrapper>, Member<IntWrapper> > map;
     HeapHashSet<Member<IntWrapper> > set;
     HeapHashSet<Member<IntWrapper> > set2;
     HeapVector<Member<IntWrapper>, 2> vector;
     HeapVector<PairWrappedUnwrapped, 2> vectorWU;
     HeapVector<PairUnwrappedWrapped, 2> vectorUW;
+    HeapDeque<Member<IntWrapper>, 0> deque;
+    HeapDeque<PairWrappedUnwrapped, 0> dequeWU;
+    HeapDeque<PairUnwrappedWrapped, 0> dequeUW;
     void trace(Visitor* visitor)
     {
         visitor->trace(map);
         visitor->trace(set);
         visitor->trace(set2);
         visitor->trace(vector);
+        visitor->trace(vectorWU);
+        visitor->trace(vectorUW);
+        visitor->trace(deque);
+        visitor->trace(dequeWU);
+        visitor->trace(dequeUW);
     }
 };
 
 struct ShouldBeTraced {
     explicit ShouldBeTraced(IntWrapper* wrapper) : m_wrapper(wrapper) { }
     void trace(Visitor* visitor) { visitor->trace(m_wrapper); }
     Member<IntWrapper> m_wrapper;
 };
 
 class OffHeapContainer : public GarbageCollectedFinalized<OffHeapContainer> {
@@ skipping 109 matching lines @@
         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
         EXPECT_TRUE(vector1.contains(three));
         EXPECT_TRUE(vector1.contains(four));
         EXPECT_TRUE(vector1.contains(five));
         EXPECT_TRUE(vector1.contains(six));
         EXPECT_TRUE(vector2.contains(one));
         EXPECT_TRUE(vector2.contains(two));
     }
 }
 
+template<typename T, size_t inlineCapacity, typename U>
+bool dequeContains(HeapDeque<T, inlineCapacity>& deque, U u)
+{
+    typedef typename HeapDeque<T, inlineCapacity>::iterator iterator;
+    for (iterator it = deque.begin(); it != deque.end(); ++it) {
+        if (*it == u)
+            return true;
+    }
+    return false;
+}
+
 TEST(HeapTest, HeapCollectionTypes)
 {
     HeapStats initialHeapSize;
     IntWrapper::s_destructorCalls = 0;
 
     typedef HeapHashMap<Member<IntWrapper>, Member<IntWrapper> > MemberMember;
     typedef HeapHashMap<Member<IntWrapper>, int> MemberPrimitive;
     typedef HeapHashMap<int, Member<IntWrapper> > PrimitiveMember;
 
     typedef HeapHashSet<Member<IntWrapper> > MemberSet;
 
     typedef HeapVector<Member<IntWrapper>, 2> MemberVector;
+    typedef HeapDeque<Member<IntWrapper>, 0> MemberDeque;
 
     typedef HeapVector<PairWrappedUnwrapped, 2> VectorWU;
     typedef HeapVector<PairUnwrappedWrapped, 2> VectorUW;
+    typedef HeapDeque<PairWrappedUnwrapped, 0> DequeWU;
+    typedef HeapDeque<PairUnwrappedWrapped, 0> DequeUW;
 
     Persistent<MemberMember> memberMember = new MemberMember();
     Persistent<MemberMember> memberMember2 = new MemberMember();
     Persistent<MemberMember> memberMember3 = new MemberMember();
     Persistent<MemberPrimitive> memberPrimitive = new MemberPrimitive();
     Persistent<PrimitiveMember> primitiveMember = new PrimitiveMember();
     Persistent<MemberSet> set = new MemberSet();
     Persistent<MemberSet> set2 = new MemberSet();
     Persistent<MemberVector> vector = new MemberVector();
     Persistent<MemberVector> vector2 = new MemberVector();
     Persistent<VectorWU> vectorWU = new VectorWU();
     Persistent<VectorWU> vectorWU2 = new VectorWU();
     Persistent<VectorUW> vectorUW = new VectorUW();
     Persistent<VectorUW> vectorUW2 = new VectorUW();
+    Persistent<MemberDeque> deque = new MemberDeque();
+    Persistent<MemberDeque> deque2 = new MemberDeque();
+    Persistent<DequeWU> dequeWU = new DequeWU();
+    Persistent<DequeWU> dequeWU2 = new DequeWU();
+    Persistent<DequeUW> dequeUW = new DequeUW();
+    Persistent<DequeUW> dequeUW2 = new DequeUW();
     Persistent<Container> container = Container::create();
 
     clearOutOldGarbage(&initialHeapSize);
     {
         Persistent<IntWrapper> one(IntWrapper::create(1));
         Persistent<IntWrapper> two(IntWrapper::create(2));
         Persistent<IntWrapper> oneB(IntWrapper::create(1));
         Persistent<IntWrapper> twoB(IntWrapper::create(2));
         Persistent<IntWrapper> oneC(IntWrapper::create(1));
         Persistent<IntWrapper> oneD(IntWrapper::create(1));
+        Persistent<IntWrapper> oneE(IntWrapper::create(1));
+        Persistent<IntWrapper> oneF(IntWrapper::create(1));
         {
+            IntWrapper* threeB(IntWrapper::create(3));
+            IntWrapper* threeC(IntWrapper::create(3));
+            IntWrapper* threeD(IntWrapper::create(3));
+            IntWrapper* threeE(IntWrapper::create(3));
+            IntWrapper* threeF(IntWrapper::create(3));
             IntWrapper* three(IntWrapper::create(3));
+            IntWrapper* fourB(IntWrapper::create(4));
+            IntWrapper* fourC(IntWrapper::create(4));
+            IntWrapper* fourD(IntWrapper::create(4));
+            IntWrapper* fourE(IntWrapper::create(4));
+            IntWrapper* fourF(IntWrapper::create(4));
             IntWrapper* four(IntWrapper::create(4));
-            IntWrapper* threeB(IntWrapper::create(3));
-            IntWrapper* fourB(IntWrapper::create(4));
-            IntWrapper* threeC(IntWrapper::create(3));
-            IntWrapper* fourC(IntWrapper::create(4));
             IntWrapper* fiveC(IntWrapper::create(5));
-            IntWrapper* threeD(IntWrapper::create(3));
-            IntWrapper* fourD(IntWrapper::create(4));
             IntWrapper* fiveD(IntWrapper::create(5));
+            IntWrapper* fiveE(IntWrapper::create(5));
+            IntWrapper* fiveF(IntWrapper::create(5));
 
             // Member Collections.
             memberMember2->add(one, two);
             memberMember2->add(two, three);
             memberMember2->add(three, four);
             memberMember2->add(four, one);
             primitiveMember->add(1, two);
             primitiveMember->add(2, three);
             primitiveMember->add(3, four);
             primitiveMember->add(4, one);
             memberPrimitive->add(one, 2);
             memberPrimitive->add(two, 3);
             memberPrimitive->add(three, 4);
             memberPrimitive->add(four, 1);
             set2->add(one);
             set2->add(two);
             set2->add(three);
             set2->add(four);
             set->add(oneB);
             vector->append(oneB);
+            deque->append(oneB);
             vector2->append(threeB);
             vector2->append(fourB);
+            deque2->append(threeE);
+            deque2->append(fourE);
             vectorWU->append(PairWrappedUnwrapped(&*oneC, 42));
+            dequeWU->append(PairWrappedUnwrapped(&*oneE, 42));
             vectorWU2->append(PairWrappedUnwrapped(&*threeC, 43));
             vectorWU2->append(PairWrappedUnwrapped(&*fourC, 44));
             vectorWU2->append(PairWrappedUnwrapped(&*fiveC, 45));
+            dequeWU2->append(PairWrappedUnwrapped(&*threeE, 43));
+            dequeWU2->append(PairWrappedUnwrapped(&*fourE, 44));
+            dequeWU2->append(PairWrappedUnwrapped(&*fiveE, 45));
             vectorUW->append(PairUnwrappedWrapped(1, &*oneD));
             vectorUW2->append(PairUnwrappedWrapped(103, &*threeD));
             vectorUW2->append(PairUnwrappedWrapped(104, &*fourD));
             vectorUW2->append(PairUnwrappedWrapped(105, &*fiveD));
+            dequeUW->append(PairUnwrappedWrapped(1, &*oneF));
+            dequeUW2->append(PairUnwrappedWrapped(103, &*threeF));
+            dequeUW2->append(PairUnwrappedWrapped(104, &*fourF));
+            dequeUW2->append(PairUnwrappedWrapped(105, &*fiveF));
+
+            EXPECT_TRUE(dequeContains(*deque, oneB));
 
             // Collect garbage. This should change nothing since we are keeping
             // alive the IntWrapper objects with on-stack pointers.
             Heap::collectGarbage(ThreadState::HeapPointersOnStack);
+
+            EXPECT_TRUE(dequeContains(*deque, oneB));
+
             EXPECT_EQ(0u, memberMember->size());
             EXPECT_EQ(4u, memberMember2->size());
             EXPECT_EQ(4u, primitiveMember->size());
             EXPECT_EQ(4u, memberPrimitive->size());
             EXPECT_EQ(1u, set->size());
             EXPECT_EQ(4u, set2->size());
             EXPECT_EQ(1u, vector->size());
             EXPECT_EQ(2u, vector2->size());
             EXPECT_EQ(1u, vectorWU->size());
             EXPECT_EQ(3u, vectorWU2->size());
             EXPECT_EQ(1u, vectorUW->size());
             EXPECT_EQ(3u, vectorUW2->size());
+            EXPECT_EQ(1u, deque->size());
+            EXPECT_EQ(2u, deque2->size());
+            EXPECT_EQ(1u, dequeWU->size());
+            EXPECT_EQ(3u, dequeWU2->size());
+            EXPECT_EQ(1u, dequeUW->size());
+            EXPECT_EQ(3u, dequeUW2->size());
 
             MemberVector& cvec = container->vector;
             cvec.swap(*vector.get());
             vector2->swap(cvec);
             vector->swap(cvec);
 
             VectorWU& cvecWU = container->vectorWU;
             cvecWU.swap(*vectorWU.get());
             vectorWU2->swap(cvecWU);
             vectorWU->swap(cvecWU);
 
             VectorUW& cvecUW = container->vectorUW;
             cvecUW.swap(*vectorUW.get());
             vectorUW2->swap(cvecUW);
             vectorUW->swap(cvecUW);
 
+            MemberDeque& cDeque = container->deque;
+            cDeque.swap(*deque.get());
+            deque2->swap(cDeque);
+            deque->swap(cDeque);
+
+            DequeWU& cDequeWU = container->dequeWU;
+            cDequeWU.swap(*dequeWU.get());
+            dequeWU2->swap(cDequeWU);
+            dequeWU->swap(cDequeWU);
+
+            DequeUW& cDequeUW = container->dequeUW;
+            cDequeUW.swap(*dequeUW.get());
+            dequeUW2->swap(cDequeUW);
+            dequeUW->swap(cDequeUW);
+
             // Swap set and set2 in a roundabout way.
             MemberSet& cset1 = container->set;
             MemberSet& cset2 = container->set2;
             set->swap(cset1);
             set2->swap(cset2);
             set->swap(cset2);
             cset1.swap(cset2);
             cset2.swap(set2);
 
             // Triple swap.
@@ skipping 14 matching lines @@
             EXPECT_EQ(2, memberPrimitive->get(one));
             EXPECT_EQ(3, memberPrimitive->get(two));
             EXPECT_EQ(4, memberPrimitive->get(three));
             EXPECT_TRUE(set->contains(one));
             EXPECT_TRUE(set->contains(two));
             EXPECT_TRUE(set->contains(three));
             EXPECT_TRUE(set->contains(four));
             EXPECT_TRUE(set2->contains(oneB));
             EXPECT_TRUE(vector->contains(threeB));
             EXPECT_TRUE(vector->contains(fourB));
+            EXPECT_TRUE(dequeContains(*deque, threeE));
+            EXPECT_TRUE(dequeContains(*deque, fourE));
             EXPECT_TRUE(vector2->contains(oneB));
             EXPECT_FALSE(vector2->contains(threeB));
+            EXPECT_TRUE(dequeContains(*deque2, oneB));
+            EXPECT_FALSE(dequeContains(*deque2, threeE));
             EXPECT_TRUE(vectorWU->contains(PairWrappedUnwrapped(&*threeC, 43)));
             EXPECT_TRUE(vectorWU->contains(PairWrappedUnwrapped(&*fourC, 44)));
             EXPECT_TRUE(vectorWU->contains(PairWrappedUnwrapped(&*fiveC, 45)));
             EXPECT_TRUE(vectorWU2->contains(PairWrappedUnwrapped(&*oneC, 42)));
             EXPECT_FALSE(vectorWU2->contains(PairWrappedUnwrapped(&*threeC, 43)));
             EXPECT_TRUE(vectorUW->contains(PairUnwrappedWrapped(103, &*threeD)));
             EXPECT_TRUE(vectorUW->contains(PairUnwrappedWrapped(104, &*fourD)));
             EXPECT_TRUE(vectorUW->contains(PairUnwrappedWrapped(105, &*fiveD)));
             EXPECT_TRUE(vectorUW2->contains(PairUnwrappedWrapped(1, &*oneD)));
             EXPECT_FALSE(vectorUW2->contains(PairUnwrappedWrapped(103, &*threeD)));
+            EXPECT_TRUE(dequeContains(*dequeWU, PairWrappedUnwrapped(&*threeE, 43)));
+            EXPECT_TRUE(dequeContains(*dequeWU, PairWrappedUnwrapped(&*fourE, 44)));
+            EXPECT_TRUE(dequeContains(*dequeWU, PairWrappedUnwrapped(&*fiveE, 45)));
+            EXPECT_TRUE(dequeContains(*dequeWU2, PairWrappedUnwrapped(&*oneE, 42)));
+            EXPECT_FALSE(dequeContains(*dequeWU2, PairWrappedUnwrapped(&*threeE, 43)));
+            EXPECT_TRUE(dequeContains(*dequeUW, PairUnwrappedWrapped(103, &*threeF)));
+            EXPECT_TRUE(dequeContains(*dequeUW, PairUnwrappedWrapped(104, &*fourF)));
+            EXPECT_TRUE(dequeContains(*dequeUW, PairUnwrappedWrapped(105, &*fiveF)));
+            EXPECT_TRUE(dequeContains(*dequeUW2, PairUnwrappedWrapped(1, &*oneF)));
+            EXPECT_FALSE(dequeContains(*dequeUW2, PairUnwrappedWrapped(103, &*threeF)));
         }
 
         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
 
         EXPECT_EQ(4u, memberMember->size());
         EXPECT_EQ(0u, memberMember2->size());
         EXPECT_EQ(4u, primitiveMember->size());
         EXPECT_EQ(4u, memberPrimitive->size());
         EXPECT_EQ(4u, set->size());
         EXPECT_EQ(1u, set2->size());
         EXPECT_EQ(2u, vector->size());
         EXPECT_EQ(1u, vector2->size());
         EXPECT_EQ(3u, vectorUW->size());
         EXPECT_EQ(1u, vector2->size());
+        EXPECT_EQ(2u, deque->size());
+        EXPECT_EQ(1u, deque2->size());
+        EXPECT_EQ(3u, dequeUW->size());
+        EXPECT_EQ(1u, deque2->size());
 
         EXPECT_TRUE(memberMember->get(one) == two);
         EXPECT_TRUE(primitiveMember->get(1) == two);
         EXPECT_TRUE(primitiveMember->get(4) == one);
         EXPECT_EQ(2, memberPrimitive->get(one));
         EXPECT_EQ(3, memberPrimitive->get(two));
         EXPECT_TRUE(set->contains(one));
         EXPECT_TRUE(set->contains(two));
         EXPECT_FALSE(set->contains(oneB));
         EXPECT_TRUE(set2->contains(oneB));
         EXPECT_EQ(3, vector->at(0)->value());
         EXPECT_EQ(4, vector->at(1)->value());
+        EXPECT_EQ(3, deque->begin()->get()->value());
     }
 
     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
 
     EXPECT_EQ(4u, memberMember->size());
     EXPECT_EQ(4u, primitiveMember->size());
     EXPECT_EQ(4u, memberPrimitive->size());
     EXPECT_EQ(4u, set->size());
     EXPECT_EQ(1u, set2->size());
     EXPECT_EQ(2u, vector->size());
     EXPECT_EQ(1u, vector2->size());
     EXPECT_EQ(3u, vectorWU->size());
     EXPECT_EQ(1u, vectorWU2->size());
     EXPECT_EQ(3u, vectorUW->size());
     EXPECT_EQ(1u, vectorUW2->size());
+    EXPECT_EQ(2u, deque->size());
+    EXPECT_EQ(1u, deque2->size());
+    EXPECT_EQ(3u, dequeWU->size());
+    EXPECT_EQ(1u, dequeWU2->size());
+    EXPECT_EQ(3u, dequeUW->size());
+    EXPECT_EQ(1u, dequeUW2->size());
 }
 
 template<typename T>
 void MapIteratorCheck(T& it, const T& end, int expected)
 {
     int found = 0;
     while (it != end) {
         found++;
         int key = it->key->value();
         int value = it->value->value();
@@ skipping 696 matching lines @@
 
 TEST(HeapTest, PersistentHeapCollectionTypes)
 {
     HeapStats initialHeapSize;
     IntWrapper::s_destructorCalls = 0;
 
     typedef HeapVector<Member<IntWrapper> > Vec;
     typedef PersistentHeapVector<Member<IntWrapper> > PVec;
     typedef PersistentHeapHashSet<Member<IntWrapper> > PSet;
     typedef PersistentHeapHashMap<Member<IntWrapper>, Member<IntWrapper> > PMap;
+    typedef PersistentHeapDeque<Member<IntWrapper> > PDeque;
 
     clearOutOldGarbage(&initialHeapSize);
     {
         PVec pVec;
+        PDeque pDeque;
         PSet pSet;
         PMap pMap;
 
         IntWrapper* one(IntWrapper::create(1));
         IntWrapper* two(IntWrapper::create(2));
         IntWrapper* three(IntWrapper::create(3));
         IntWrapper* four(IntWrapper::create(4));
         IntWrapper* five(IntWrapper::create(5));
         IntWrapper* six(IntWrapper::create(6));
+        IntWrapper* seven(IntWrapper::create(7));
 
         pVec.append(one);
         pVec.append(two);
 
+        pDeque.append(seven);
+        pDeque.append(two);
+
         Vec* vec = new Vec();
         vec->swap(pVec);
 
         pVec.append(two);
         pVec.append(three);
 
         pSet.add(four);
         pMap.add(five, six);
 
         // Collect |vec| and |one|.
         vec = 0;
         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
         EXPECT_EQ(1, IntWrapper::s_destructorCalls);
 
         EXPECT_EQ(2u, pVec.size());
-        EXPECT_TRUE(pVec.at(0) == two);
-        EXPECT_TRUE(pVec.at(1) == three);
+        EXPECT_EQ(two, pVec.at(0));
+        EXPECT_EQ(three, pVec.at(1));
+
+        EXPECT_EQ(2u, pDeque.size());
+        EXPECT_EQ(seven, pDeque.first());
+        EXPECT_EQ(seven, pDeque.takeFirst());
+        EXPECT_EQ(two, pDeque.first());
+
+        EXPECT_EQ(1u, pDeque.size());
 
         EXPECT_EQ(1u, pSet.size());
         EXPECT_TRUE(pSet.contains(four));
 
         EXPECT_EQ(1u, pMap.size());
-        EXPECT_TRUE(pMap.get(five) == six);
+        EXPECT_EQ(six, pMap.get(five));
     }
 
     // Collect previous roots.
     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
-    EXPECT_EQ(6, IntWrapper::s_destructorCalls);
+    EXPECT_EQ(7, IntWrapper::s_destructorCalls);
 }
 
 TEST(HeapTest, CollectionNesting)
 {
     HeapStats initialStats;
     clearOutOldGarbage(&initialStats);
-    void* key = &IntWrapper::s_destructorCalls;
+    int* key = &IntWrapper::s_destructorCalls;
     IntWrapper::s_destructorCalls = 0;
     typedef HeapVector<Member<IntWrapper> > IntVector;
+    typedef HeapDeque<Member<IntWrapper> > IntDeque;
     HeapHashMap<void*, IntVector>* map = new HeapHashMap<void*, IntVector>();
+    HeapHashMap<void*, IntDeque>* map2 = new HeapHashMap<void*, IntDeque>();
 
     map->add(key, IntVector());
+    map2->add(key, IntDeque());
 
     HeapHashMap<void*, IntVector>::iterator it = map->find(key);
     EXPECT_EQ(0u, map->get(key).size());
 
+    HeapHashMap<void*, IntDeque>::iterator it2 = map2->find(key);
+    EXPECT_EQ(0u, map2->get(key).size());
+
     it->value.append(IntWrapper::create(42));
     EXPECT_EQ(1u, map->get(key).size());
 
+    it2->value.append(IntWrapper::create(42));
+    EXPECT_EQ(1u, map2->get(key).size());
+
     Persistent<HeapHashMap<void*, IntVector> > keepAlive(map);
+    Persistent<HeapHashMap<void*, IntDeque> > keepAlive2(map2);
+
+    for (int i = 0; i < 100; i++) {
+        map->add(key + 1 + i, IntVector());
+        map2->add(key + 1 + i, IntDeque());
+    }
+
     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
+
     EXPECT_EQ(1u, map->get(key).size());
+    EXPECT_EQ(1u, map2->get(key).size());
     EXPECT_EQ(0, IntWrapper::s_destructorCalls);
 
     keepAlive = nullptr;
     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
     EXPECT_EQ(1, IntWrapper::s_destructorCalls);
 }
 
 TEST(HeapTest, GarbageCollectedMixin)
 {
     HeapStats initialHeapStats;
@@ skipping 37 matching lines @@
     EXPECT_EQ(1u, map->get(key).size());
     EXPECT_EQ(0, IntWrapper::s_destructorCalls);
 }
 
 TEST(HeapTest, CollectionNesting3)
 {
     HeapStats initialStats;
     clearOutOldGarbage(&initialStats);
     IntWrapper::s_destructorCalls = 0;
     typedef HeapVector<Member<IntWrapper> > IntVector;
+    typedef HeapDeque<Member<IntWrapper> > IntDeque;
     HeapVector<IntVector>* vector = new HeapVector<IntVector>();
+    HeapDeque<IntDeque>* deque = new HeapDeque<IntDeque>();
 
     vector->append(IntVector());
+    deque->append(IntDeque());
 
     HeapVector<IntVector>::iterator it = vector->begin();
+    HeapDeque<IntDeque>::iterator it2 = deque->begin();
     EXPECT_EQ(0u, it->size());
+    EXPECT_EQ(0u, it2->size());
 
     it->append(IntWrapper::create(42));
+    it2->append(IntWrapper::create(42));
     EXPECT_EQ(1u, it->size());
+    EXPECT_EQ(1u, it2->size());
 
     Persistent<HeapVector<IntVector> > keepAlive(vector);
+    Persistent<HeapDeque<IntDeque> > keepAlive2(deque);
     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
     EXPECT_EQ(1u, it->size());
+    EXPECT_EQ(1u, it2->size());
     EXPECT_EQ(0, IntWrapper::s_destructorCalls);
 }
 
 TEST(HeapTest, EmbeddedInVector)
 {
     HeapStats initialStats;
     clearOutOldGarbage(&initialStats);
     SimpleFinalizedObject::s_destructorCalls = 0;
     {
         PersistentHeapVector<VectorObject, 2> inlineVector;
@@ skipping 23 matching lines @@
         VectorObjectNoTrace n1, n2;
         vectorNoTrace.append(n1);
         vectorNoTrace.append(n2);
         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
         EXPECT_EQ(2, SimpleFinalizedObject::s_destructorCalls);
     }
     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
     EXPECT_EQ(8, SimpleFinalizedObject::s_destructorCalls);
 }
 
+TEST(HeapTest, EmbeddedInDeque)
+{
+    HeapStats initialStats;
+    clearOutOldGarbage(&initialStats);
+    SimpleFinalizedObject::s_destructorCalls = 0;
+    {
+        PersistentHeapDeque<VectorObject, 2> inlineDeque;
+        PersistentHeapDeque<VectorObject> outlineDeque;
+        VectorObject i1, i2;
+        inlineDeque.append(i1);
+        inlineDeque.append(i2);
+
+        VectorObject o1, o2;
+        outlineDeque.append(o1);
+        outlineDeque.append(o2);
+
+        PersistentHeapDeque<VectorObjectInheritedTrace> dequeInheritedTrace;
+        VectorObjectInheritedTrace it1, it2;
+        dequeInheritedTrace.append(it1);
+        dequeInheritedTrace.append(it2);
+
+        Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
+        EXPECT_EQ(0, SimpleFinalizedObject::s_destructorCalls);
+
+        // Since VectorObjectNoTrace has no trace method it will
+        // not be traced and hence be collected when doing GC.
+        // We trace items in a collection braced on the item's
+        // having a trace method. This is determined via the
+        // NeedsTracing trait in wtf/TypeTraits.h.
+        PersistentHeapDeque<VectorObjectNoTrace> dequeNoTrace;
+        VectorObjectNoTrace n1, n2;
+        dequeNoTrace.append(n1);
+        dequeNoTrace.append(n2);
+        Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
+        EXPECT_EQ(2, SimpleFinalizedObject::s_destructorCalls);
+    }
+    Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
+    EXPECT_EQ(8, SimpleFinalizedObject::s_destructorCalls);
+}
+
 TEST(HeapTest, RawPtrInHash)
 {
     HashSet<RawPtr<int> > set;
     set.add(new int(42));
     set.add(new int(42));
     EXPECT_EQ(2u, set.size());
     for (HashSet<RawPtr<int> >::iterator it = set.begin(); it != set.end(); ++it)
         EXPECT_EQ(42, **it);
 }
 
@@ skipping 119 matching lines @@
 {
     HeapHashMap<SimpleClassWithDestructor*, OwnPtr<SimpleClassWithDestructor> > map;
     SimpleClassWithDestructor* hasDestructor = new SimpleClassWithDestructor();
     map.add(hasDestructor, adoptPtr(hasDestructor));
     SimpleClassWithDestructor::s_wasDestructed = false;
     map.clear();
     ASSERT(SimpleClassWithDestructor::s_wasDestructed);
 }
 
 } // WebCore namespace