Fix Deque.swap for deques with inline capacity

Source/wtf/Deque.h

 /*
  * Copyright (C) 2007, 2008 Apple Inc. All rights reserved.
  * Copyright (C) 2009 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:
  *
  * 1.  Redistributions of source code must retain the above copyright
  *     notice, this list of conditions and the following disclaimer.
@@ skipping 25 matching lines @@
 #include "wtf/PassTraits.h"
 #include "wtf/Vector.h"
 #include <iterator>
 
 namespace WTF {
     template<typename T, size_t inlineCapacity, typename Allocator> class DequeIteratorBase;
     template<typename T, size_t inlineCapacity, typename Allocator> class DequeIterator;
     template<typename T, size_t inlineCapacity, typename Allocator> class DequeConstIterator;
 
     template<typename T, size_t inlineCapacity = 0, typename Allocator = DefaultAllocator>
-    class Deque : public VectorDestructorBase<Deque<T, inlineCapacity, Allocator>, T, (inlineCapacity > 0), Allocator::isGarbageCollected> {
+    class Deque : private VectorBuffer<T, inlineCapacity, Allocator>, public VectorDestructorBase<Deque<T, inlineCapacity, Allocator>, T, (inlineCapacity > 0), Allocator::isGarbageCollected> {
         WTF_USE_ALLOCATOR(Deque, Allocator);
+    private:
+private:

[Mads Ager (chromium), 2014/07/18 11:03:14]

Remove this line.

+        typedef VectorBuffer<T, inlineCapacity, Allocator> Base;
+        typedef typename Base::Range Range;
+
     public:
         typedef DequeIterator<T, inlineCapacity, Allocator> iterator;
         typedef DequeConstIterator<T, inlineCapacity, Allocator> const_iterator;
         typedef std::reverse_iterator<iterator> reverse_iterator;
         typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
         typedef PassTraits<T> Pass;
         typedef typename PassTraits<T>::PassType PassType;
 
         Deque();
         Deque(const Deque<T, inlineCapacity, Allocator>&);
-        // FIXME: Doesn't work if there is an inline buffer, due to crbug.com/360572
-        Deque<T, 0, Allocator>& operator=(const Deque&);
+        Deque<T, inlineCapacity, Allocator>& operator=(const Deque&);
 
         void finalize();
         void finalizeGarbageCollectedObject() { finalize(); }
 
-        // We hard wire the inlineCapacity to zero here, due to crbug.com/360572
-        void swap(Deque<T, 0, Allocator>&);
+        void swap(Deque&);
 
-        size_t size() const { return m_start <= m_end ? m_end - m_start : m_end + m_buffer.capacity() - m_start; }
+        size_t size() const { return m_start <= m_end ? m_end - m_start : m_end + capacity() - m_start; }
         bool isEmpty() const { return m_start == m_end; }
 
         iterator begin() { return iterator(this, m_start); }
         iterator end() { return iterator(this, m_end); }
         const_iterator begin() const { return const_iterator(this, m_start); }
         const_iterator end() const { return const_iterator(this, m_end); }
         reverse_iterator rbegin() { return reverse_iterator(end()); }
         reverse_iterator rend() { return reverse_iterator(begin()); }
         const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
         const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
 
-        T& first() { ASSERT(m_start != m_end); return m_buffer.buffer()[m_start]; }
-        const T& first() const { ASSERT(m_start != m_end); return m_buffer.buffer()[m_start]; }
+        T& first() { ASSERT(m_start != m_end); return buffer()[m_start]; }
+        const T& first() const { ASSERT(m_start != m_end); return buffer()[m_start]; }
         PassType takeFirst();
 
         T& last() { ASSERT(m_start != m_end); return *(--end()); }
         const T& last() const { ASSERT(m_start != m_end); return *(--end()); }
         PassType takeLast();
 
         template<typename U> void append(const U&);
         template<typename U> void prepend(const U&);
         void removeFirst();
         void removeLast();
         void remove(iterator&);
         void remove(const_iterator&);
 
         void clear();
 
         template<typename Predicate>
         iterator findIf(Predicate&);
 
         void trace(typename Allocator::Visitor*);
 
     private:
+        using Base::buffer;
+        using Base::capacity;
+        using Base::allocateBuffer;
+        using Base::clearUnusedSlots;
+        using Base::hasOutOfLineBuffer;
+
         friend class DequeIteratorBase<T, inlineCapacity, Allocator>;
+        friend class VectorBuffer<T, inlineCapacity, Allocator>;

[Mads Ager (chromium), 2014/07/18 11:03:14]

Is this needed? When is the VectorBuffer super class accessing private parts of
the subclass?

[Erik Corry, 2014/07/22 15:49:26]

Not needed yet, removed.

 
-        typedef VectorBuffer<T, inlineCapacity, Allocator> Buffer;
         typedef VectorTypeOperations<T> TypeOperations;
         typedef DequeIteratorBase<T, inlineCapacity, Allocator> IteratorBase;
 
         void remove(size_t position);
         void destroyAll();
         void expandCapacityIfNeeded();
         void expandCapacity();
 
-        Buffer m_buffer;
         unsigned m_start;
         unsigned m_end;
     };
 
     template<typename T, size_t inlineCapacity, typename Allocator>
     class DequeIteratorBase {
     protected:
         DequeIteratorBase();
         DequeIteratorBase(const Deque<T, inlineCapacity, Allocator>*, size_t);
         DequeIteratorBase(const DequeIteratorBase&);
@@ skipping 82 matching lines @@
 
     template<typename T, size_t inlineCapacity, typename Allocator>
     inline Deque<T, inlineCapacity, Allocator>::Deque()
         : m_start(0)
         , m_end(0)
     {
     }
 
     template<typename T, size_t inlineCapacity, typename Allocator>
     inline Deque<T, inlineCapacity, Allocator>::Deque(const Deque<T, inlineCapacity, Allocator>& other)
-        : m_buffer(other.m_buffer.capacity())
+        : VectorBuffer<T, inlineCapacity, Allocator>(other.capacity())
         , m_start(other.m_start)
         , m_end(other.m_end)
     {
-        const T* otherBuffer = other.m_buffer.buffer();
+        const T* otherBuffer = other.buffer();
         if (m_start <= m_end)
-            TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_end, m_buffer.buffer() + m_start);
+            TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_end, buffer() + m_start);
         else {
-            TypeOperations::uninitializedCopy(otherBuffer, otherBuffer + m_end, m_buffer.buffer());
-            TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_buffer.capacity(), m_buffer.buffer() + m_start);
+            TypeOperations::uninitializedCopy(otherBuffer, otherBuffer + m_end, buffer());
+            TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + capacity(), buffer() + m_start);
         }
     }
 
     template<typename T, size_t inlineCapacity, typename Allocator>
     void deleteAllValues(const Deque<T, inlineCapacity, Allocator>& collection)
     {
         typedef typename Deque<T, inlineCapacity, Allocator>::const_iterator iterator;
         iterator end = collection.end();
         for (iterator it = collection.begin(); it != end; ++it)
             delete *it;
     }
 
     template<typename T, size_t inlineCapacity, typename Allocator>
-    inline Deque<T, 0, Allocator>& Deque<T, inlineCapacity, Allocator>::operator=(const Deque& other)
+    inline Deque<T, inlineCapacity, Allocator>& Deque<T, inlineCapacity, Allocator>::operator=(const Deque& other)
     {
-        Deque<T> copy(other);
+        Deque copy(other);
         swap(copy);
         return *this;
     }
 
     template<typename T, size_t inlineCapacity, typename Allocator>
     inline void Deque<T, inlineCapacity, Allocator>::destroyAll()
     {
         if (m_start <= m_end) {
-            TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_end);
-            m_buffer.clearUnusedSlots(m_buffer.buffer() + m_start, m_buffer.buffer() + m_end);
+            TypeOperations::destruct(buffer() + m_start, buffer() + m_end);
+            clearUnusedSlots(buffer() + m_start, buffer() + m_end);
         } else {
-            TypeOperations::destruct(m_buffer.buffer(), m_buffer.buffer() + m_end);
-            m_buffer.clearUnusedSlots(m_buffer.buffer(), m_buffer.buffer() + m_end);
-            TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_buffer.capacity());
-            m_buffer.clearUnusedSlots(m_buffer.buffer() + m_start, m_buffer.buffer() + m_buffer.capacity());
+            TypeOperations::destruct(buffer(), buffer() + m_end);
+            clearUnusedSlots(buffer(), buffer() + m_end);
+            TypeOperations::destruct(buffer() + m_start, buffer() + capacity());
+            clearUnusedSlots(buffer() + m_start, buffer() + capacity());
         }
     }
 
     // Off-GC-heap deques: Destructor should be called.
     // On-GC-heap deques: Destructor should be called for inline buffers
     // (if any) but destructor shouldn't be called for vector backing since
     // it is managed by the traced GC heap.
     template<typename T, size_t inlineCapacity, typename Allocator>
     inline void Deque<T, inlineCapacity, Allocator>::finalize()
     {
-        if (!inlineCapacity && !m_buffer.buffer())
+        if (!inlineCapacity && !buffer())
             return;
-        if (!isEmpty() && !(Allocator::isGarbageCollected && m_buffer.hasOutOfLineBuffer()))
+        if (!isEmpty() && !(Allocator::isGarbageCollected && hasOutOfLineBuffer()))
             destroyAll();
 
-        m_buffer.destruct();
-    }
-
-    // FIXME: Doesn't work if there is an inline buffer, due to crbug.com/360572
-    template<typename T, size_t inlineCapacity, typename Allocator>
-    inline void Deque<T, inlineCapacity, Allocator>::swap(Deque<T, 0, Allocator>& other)
-    {
-        std::swap(m_start, other.m_start);
-        std::swap(m_end, other.m_end);
-        m_buffer.swapVectorBuffer(other.m_buffer);
+        Base::destruct();
     }
 
     template<typename T, size_t inlineCapacity, typename Allocator>

[Ken Russell (switch to Gerrit), 2014/07/21 20:44:09]

Throughout this class, member function templates are used. I believe this is an
error. The template parameters T, inlineCapacity, and Allocator should be
re-used from the template parameters of the class. Otherwise it isn't apparent
that they must match the values used at construction time, and I think it may be
possible to subvert the type checking you intend. Basically, I think you should
remove the template<typename T, size_t inlineCapacity, typename Allocator> lines
throughout this class. The Deque<T, inlineCapacity, Allocator> scoping is
redundant as well.

If I'm correct about this issue, please send out a revised CL. Thanks.

[Erik Corry, 2014/07/22 15:49:26]

This is just because they are defined out of line. I am using the class template
parameters.  For a reduced example that hopefully makes it more clear, the
template situation with bar and bar2 is identical, it's just that in the second
case I am defining bar2 out of line, and so I have to write template<typename T>

template <typename T>
class Foo {
  bool bar(T* t) { return !!t; }
  bool bar2(T* t);
}

template <typename T>
Foo<T>::bar2(T* t)
{
  return !!t;
}

+    inline void Deque<T, inlineCapacity, Allocator>::swap(Deque<T, inlineCapacity, Allocator>& other)
+    {
+        Range thisRange = (m_start != m_end && m_end == 0) ? Range(m_start, capacity()) : Range(m_start, m_end);
+        Range otherRange = (other.m_start != other.m_end && other.m_end == 0) ? Range(other.m_start, other.capacity()) : Range(other.m_start, other.m_end);
+        Base::swapVectorBuffer(other, thisRange, otherRange);
+        std::swap(m_start, other.m_start);
+        std::swap(m_end, other.m_end);
+    }
+
+    template<typename T, size_t inlineCapacity, typename Allocator>
     inline void Deque<T, inlineCapacity, Allocator>::clear()
     {
         destroyAll();
         m_start = 0;
         m_end = 0;
-        m_buffer.deallocateBuffer(m_buffer.buffer());
-        m_buffer.resetBufferPointer();
+        Base::deallocateBuffer(buffer());
+        Base::resetBufferPointer();
     }
 
     template<typename T, size_t inlineCapacity, typename Allocator>
     template<typename Predicate>
     inline DequeIterator<T, inlineCapacity, Allocator> Deque<T, inlineCapacity, Allocator>::findIf(Predicate& predicate)
     {
         iterator end_iterator = end();
         for (iterator it = begin(); it != end_iterator; ++it) {
             if (predicate(*it))
                 return it;
         }
         return end_iterator;
     }
 
+    // Because start == end indicates an empty deque, we can never use the last
+    // element in the backing.
     template<typename T, size_t inlineCapacity, typename Allocator>
     inline void Deque<T, inlineCapacity, Allocator>::expandCapacityIfNeeded()
     {
         if (m_start) {
             if (m_end + 1 != m_start)
                 return;
         } else if (m_end) {
-            if (m_end != m_buffer.capacity() - 1)
+            if (m_end != capacity() - 1)
                 return;
-        } else if (m_buffer.capacity())
+        } else if (capacity())
             return;
 
         expandCapacity();
     }
 
     template<typename T, size_t inlineCapacity, typename Allocator>
     void Deque<T, inlineCapacity, Allocator>::expandCapacity()
     {
-        size_t oldCapacity = m_buffer.capacity();
-        T* oldBuffer = m_buffer.buffer();
-        m_buffer.allocateBuffer(std::max(static_cast<size_t>(16), oldCapacity + oldCapacity / 4 + 1));
+        size_t oldCapacity = capacity();
+        T* oldBuffer = buffer();
+        Base::allocateBuffer(std::max(static_cast<size_t>(16), oldCapacity + oldCapacity / 4 + 1));
         if (m_start <= m_end)
-            TypeOperations::move(oldBuffer + m_start, oldBuffer + m_end, m_buffer.buffer() + m_start);
+            TypeOperations::move(oldBuffer + m_start, oldBuffer + m_end, buffer() + m_start);
         else {
-            TypeOperations::move(oldBuffer, oldBuffer + m_end, m_buffer.buffer());
-            size_t newStart = m_buffer.capacity() - (oldCapacity - m_start);
-            TypeOperations::move(oldBuffer + m_start, oldBuffer + oldCapacity, m_buffer.buffer() + newStart);
+            TypeOperations::move(oldBuffer, oldBuffer + m_end, buffer());
+            size_t newStart = capacity() - (oldCapacity - m_start);
+            TypeOperations::move(oldBuffer + m_start, oldBuffer + oldCapacity, buffer() + newStart);
             m_start = newStart;
         }
-        m_buffer.deallocateBuffer(oldBuffer);
+        Base::deallocateBuffer(oldBuffer);
     }
 
     template<typename T, size_t inlineCapacity, typename Allocator>
     inline typename Deque<T, inlineCapacity, Allocator>::PassType Deque<T, inlineCapacity, Allocator>::takeFirst()
     {
         T oldFirst = Pass::transfer(first());
         removeFirst();
         return Pass::transfer(oldFirst);
     }
 
     template<typename T, size_t inlineCapacity, typename Allocator>
     inline typename Deque<T, inlineCapacity, Allocator>::PassType Deque<T, inlineCapacity, Allocator>::takeLast()
     {
         T oldLast = Pass::transfer(last());
         removeLast();
         return Pass::transfer(oldLast);
     }
 
     template<typename T, size_t inlineCapacity, typename Allocator> template<typename U>
     inline void Deque<T, inlineCapacity, Allocator>::append(const U& value)
     {
         expandCapacityIfNeeded();
-        new (NotNull, &m_buffer.buffer()[m_end]) T(value);
-        if (m_end == m_buffer.capacity() - 1)
+        new (NotNull, &buffer()[m_end]) T(value);
+        if (m_end == capacity() - 1)
             m_end = 0;
         else
             ++m_end;
     }
 
     template<typename T, size_t inlineCapacity, typename Allocator> template<typename U>
     inline void Deque<T, inlineCapacity, Allocator>::prepend(const U& value)
     {
         expandCapacityIfNeeded();
         if (!m_start)
-            m_start = m_buffer.capacity() - 1;
+            m_start = capacity() - 1;
         else
             --m_start;
-        new (NotNull, &m_buffer.buffer()[m_start]) T(value);
+        new (NotNull, &buffer()[m_start]) T(value);
     }
 
     template<typename T, size_t inlineCapacity, typename Allocator>
     inline void Deque<T, inlineCapacity, Allocator>::removeFirst()
     {
         ASSERT(!isEmpty());
-        TypeOperations::destruct(&m_buffer.buffer()[m_start], &m_buffer.buffer()[m_start + 1]);
-        m_buffer.clearUnusedSlots(&m_buffer.buffer()[m_start], &m_buffer.buffer()[m_start + 1]);
-        if (m_start == m_buffer.capacity() - 1)
+        TypeOperations::destruct(&buffer()[m_start], &buffer()[m_start + 1]);
+        clearUnusedSlots(&buffer()[m_start], &buffer()[m_start + 1]);
+        if (m_start == capacity() - 1)
             m_start = 0;
         else
             ++m_start;
     }
 
     template<typename T, size_t inlineCapacity, typename Allocator>
     inline void Deque<T, inlineCapacity, Allocator>::removeLast()
     {
         ASSERT(!isEmpty());
         if (!m_end)
-            m_end = m_buffer.capacity() - 1;
+            m_end = capacity() - 1;
         else
             --m_end;
-        TypeOperations::destruct(&m_buffer.buffer()[m_end], &m_buffer.buffer()[m_end + 1]);
-        m_buffer.clearUnusedSlots(&m_buffer.buffer()[m_end], &m_buffer.buffer()[m_end + 1]);
+        TypeOperations::destruct(&buffer()[m_end], &buffer()[m_end + 1]);
+        clearUnusedSlots(&buffer()[m_end], &buffer()[m_end + 1]);
     }
 
     template<typename T, size_t inlineCapacity, typename Allocator>
     inline void Deque<T, inlineCapacity, Allocator>::remove(iterator& it)
     {
         remove(it.m_index);
     }
 
     template<typename T, size_t inlineCapacity, typename Allocator>
     inline void Deque<T, inlineCapacity, Allocator>::remove(const_iterator& it)
     {
         remove(it.m_index);
     }
 
     template<typename T, size_t inlineCapacity, typename Allocator>
     inline void Deque<T, inlineCapacity, Allocator>::remove(size_t position)
     {
         if (position == m_end)
             return;
 
-        T* buffer = m_buffer.buffer();
-        TypeOperations::destruct(&buffer[position], &buffer[position + 1]);
+        T* buf = buffer();
+        TypeOperations::destruct(&buf[position], &buf[position + 1]);
 
         // Find which segment of the circular buffer contained the remove element, and only move elements in that part.
         if (position >= m_start) {
-            TypeOperations::moveOverlapping(buffer + m_start, buffer + position, buffer + m_start + 1);
-            m_buffer.clearUnusedSlots(buffer + m_start, buffer + m_start + 1);
-            m_start = (m_start + 1) % m_buffer.capacity();
+            TypeOperations::moveOverlapping(buf + m_start, buf + position, buf + m_start + 1);
+            clearUnusedSlots(buf + m_start, buf + m_start + 1);
+            m_start = (m_start + 1) % capacity();
         } else {
-            TypeOperations::moveOverlapping(buffer + position + 1, buffer + m_end, buffer + position);
-            m_buffer.clearUnusedSlots(buffer + m_end - 1, buffer + m_end);
-            m_end = (m_end - 1 + m_buffer.capacity()) % m_buffer.capacity();
+            TypeOperations::moveOverlapping(buf + position + 1, buf + m_end, buf + position);
+            clearUnusedSlots(buf + m_end - 1, buf + m_end);
+            m_end = (m_end - 1 + capacity()) % capacity();
         }
     }
 
     template<typename T, size_t inlineCapacity, typename Allocator>
     inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase()
         : m_deque(0)
     {
     }
 
     template<typename T, size_t inlineCapacity, typename Allocator>
@@ skipping 26 matching lines @@
     template<typename T, size_t inlineCapacity, typename Allocator>
     inline bool DequeIteratorBase<T, inlineCapacity, Allocator>::isEqual(const DequeIteratorBase& other) const
     {
         return m_index == other.m_index;
     }
 
     template<typename T, size_t inlineCapacity, typename Allocator>
     inline void DequeIteratorBase<T, inlineCapacity, Allocator>::increment()
     {
         ASSERT(m_index != m_deque->m_end);
-        ASSERT(m_deque->m_buffer.capacity());
-        if (m_index == m_deque->m_buffer.capacity() - 1)
+        ASSERT(m_deque->capacity());
+        if (m_index == m_deque->capacity() - 1)
             m_index = 0;
         else
             ++m_index;
     }
 
     template<typename T, size_t inlineCapacity, typename Allocator>
     inline void DequeIteratorBase<T, inlineCapacity, Allocator>::decrement()
     {
         ASSERT(m_index != m_deque->m_start);
-        ASSERT(m_deque->m_buffer.capacity());
+        ASSERT(m_deque->capacity());
         if (!m_index)
-            m_index = m_deque->m_buffer.capacity() - 1;
+            m_index = m_deque->capacity() - 1;
         else
             --m_index;
     }
 
     template<typename T, size_t inlineCapacity, typename Allocator>
     inline T* DequeIteratorBase<T, inlineCapacity, Allocator>::after() const
     {
         ASSERT(m_index != m_deque->m_end);
-        return &m_deque->m_buffer.buffer()[m_index];
+        return &m_deque->buffer()[m_index];
     }
 
     template<typename T, size_t inlineCapacity, typename Allocator>
     inline T* DequeIteratorBase<T, inlineCapacity, Allocator>::before() const
     {
         ASSERT(m_index != m_deque->m_start);
         if (!m_index)
-            return &m_deque->m_buffer.buffer()[m_deque->m_buffer.capacity() - 1];
-        return &m_deque->m_buffer.buffer()[m_index - 1];
+            return &m_deque->buffer()[m_deque->capacity() - 1];
+        return &m_deque->buffer()[m_index - 1];
     }
 
     // This is only called if the allocator is a HeapAllocator. It is used when
     // visiting during a tracing GC.
     template<typename T, size_t inlineCapacity, typename Allocator>
     void Deque<T, inlineCapacity, Allocator>::trace(typename Allocator::Visitor* visitor)
     {
         ASSERT(Allocator::isGarbageCollected); // Garbage collector must be enabled.
-        const T* bufferBegin = m_buffer.buffer();
+        const T* bufferBegin = buffer();
         const T* end = bufferBegin + m_end;
         if (ShouldBeTraced<VectorTraits<T> >::value) {
             if (m_start <= m_end) {
                 for (const T* bufferEntry = bufferBegin + m_start; bufferEntry != end; bufferEntry++)
                     Allocator::template trace<T, VectorTraits<T> >(visitor, *const_cast<T*>(bufferEntry));
             } else {
                 for (const T* bufferEntry = bufferBegin; bufferEntry != end; bufferEntry++)
                     Allocator::template trace<T, VectorTraits<T> >(visitor, *const_cast<T*>(bufferEntry));
-                const T* bufferEnd = m_buffer.buffer() + m_buffer.capacity();
+                const T* bufferEnd = buffer() + capacity();
                 for (const T* bufferEntry = bufferBegin + m_start; bufferEntry != bufferEnd; bufferEntry++)
                     Allocator::template trace<T, VectorTraits<T> >(visitor, *const_cast<T*>(bufferEntry));
             }
         }
-        if (m_buffer.hasOutOfLineBuffer())
-            Allocator::markNoTracing(visitor, m_buffer.buffer());
+        if (hasOutOfLineBuffer())
+            Allocator::markNoTracing(visitor, buffer());
     }
 
 #if !ENABLE(OILPAN)
     template<typename T, size_t N>
     struct NeedsTracing<Deque<T, N> > {
         static const bool value = false;
     };
 #endif
 
 } // namespace WTF
 
 using WTF::Deque;
 
 #endif // WTF_Deque_h