Add the basic infrastructure to compile attributes matching in selectors
[WebKit-https.git] / Source / WTF / wtf / Vector.h
1 /*
2  *  Copyright (C) 2005, 2006, 2007, 2008, 2014 Apple Inc. All rights reserved.
3  *
4  *  This library is free software; you can redistribute it and/or
5  *  modify it under the terms of the GNU Library General Public
6  *  License as published by the Free Software Foundation; either
7  *  version 2 of the License, or (at your option) any later version.
8  *
9  *  This library is distributed in the hope that it will be useful,
10  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
11  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12  *  Library General Public License for more details.
13  *
14  *  You should have received a copy of the GNU Library General Public License
15  *  along with this library; see the file COPYING.LIB.  If not, write to
16  *  the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17  *  Boston, MA 02110-1301, USA.
18  *
19  */
20
21 #ifndef WTF_Vector_h
22 #define WTF_Vector_h
23
24 #include <initializer_list>
25 #include <limits>
26 #include <string.h>
27 #include <type_traits>
28 #include <utility>
29 #include <wtf/CheckedArithmetic.h>
30 #include <wtf/FastMalloc.h>
31 #include <wtf/MallocPtr.h>
32 #include <wtf/Noncopyable.h>
33 #include <wtf/OwnPtr.h>
34 #include <wtf/StdLibExtras.h>
35 #include <wtf/ValueCheck.h>
36 #include <wtf/VectorTraits.h>
37
38 namespace WTF {
39
40 const size_t notFound = static_cast<size_t>(-1);
41
42 template <bool needsDestruction, typename T>
43 struct VectorDestructor;
44
45 template<typename T>
46 struct VectorDestructor<false, T>
47 {
48     static void destruct(T*, T*) {}
49 };
50
51 template<typename T>
52 struct VectorDestructor<true, T>
53 {
54     static void destruct(T* begin, T* end) 
55     {
56         for (T* cur = begin; cur != end; ++cur)
57             cur->~T();
58     }
59 };
60
61 template <bool needsInitialization, bool canInitializeWithMemset, typename T>
62 struct VectorInitializer;
63
64 template<bool ignore, typename T>
65 struct VectorInitializer<false, ignore, T>
66 {
67     static void initialize(T*, T*) {}
68 };
69
70 template<typename T>
71 struct VectorInitializer<true, false, T>
72 {
73     static void initialize(T* begin, T* end) 
74     {
75         for (T* cur = begin; cur != end; ++cur)
76             new (NotNull, cur) T;
77     }
78 };
79
80 template<typename T>
81 struct VectorInitializer<true, true, T>
82 {
83     static void initialize(T* begin, T* end) 
84     {
85         memset(begin, 0, reinterpret_cast<char*>(end) - reinterpret_cast<char*>(begin));
86     }
87 };
88
89 template <bool canMoveWithMemcpy, typename T>
90 struct VectorMover;
91
92 template<typename T>
93 struct VectorMover<false, T>
94 {
95     static void move(T* src, T* srcEnd, T* dst)
96     {
97         while (src != srcEnd) {
98             new (NotNull, dst) T(std::move(*src));
99             src->~T();
100             ++dst;
101             ++src;
102         }
103     }
104     static void moveOverlapping(T* src, T* srcEnd, T* dst)
105     {
106         if (src > dst)
107             move(src, srcEnd, dst);
108         else {
109             T* dstEnd = dst + (srcEnd - src);
110             while (src != srcEnd) {
111                 --srcEnd;
112                 --dstEnd;
113                 new (NotNull, dstEnd) T(std::move(*srcEnd));
114                 srcEnd->~T();
115             }
116         }
117     }
118 };
119
120 template<typename T>
121 struct VectorMover<true, T>
122 {
123     static void move(const T* src, const T* srcEnd, T* dst) 
124     {
125         memcpy(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
126     }
127     static void moveOverlapping(const T* src, const T* srcEnd, T* dst) 
128     {
129         memmove(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
130     }
131 };
132
133 template <bool canCopyWithMemcpy, typename T>
134 struct VectorCopier;
135
136 template<typename T>
137 struct VectorCopier<false, T>
138 {
139     static void uninitializedCopy(const T* src, const T* srcEnd, T* dst) 
140     {
141         while (src != srcEnd) {
142             new (NotNull, dst) T(*src);
143             ++dst;
144             ++src;
145         }
146     }
147 };
148
149 template<typename T>
150 struct VectorCopier<true, T>
151 {
152     static void uninitializedCopy(const T* src, const T* srcEnd, T* dst) 
153     {
154         memcpy(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
155     }
156 };
157
158 template <bool canFillWithMemset, typename T>
159 struct VectorFiller;
160
161 template<typename T>
162 struct VectorFiller<false, T>
163 {
164     static void uninitializedFill(T* dst, T* dstEnd, const T& val) 
165     {
166         while (dst != dstEnd) {
167             new (NotNull, dst) T(val);
168             ++dst;
169         }
170     }
171 };
172
173 template<typename T>
174 struct VectorFiller<true, T>
175 {
176     static void uninitializedFill(T* dst, T* dstEnd, const T& val) 
177     {
178         static_assert(sizeof(T) == 1, "Size of type T should be equal to one!");
179 #if COMPILER(GCC) && defined(_FORTIFY_SOURCE)
180         if (!__builtin_constant_p(dstEnd - dst) || (!(dstEnd - dst)))
181 #endif
182             memset(dst, val, dstEnd - dst);
183     }
184 };
185
186 template<bool canCompareWithMemcmp, typename T>
187 struct VectorComparer;
188
189 template<typename T>
190 struct VectorComparer<false, T>
191 {
192     static bool compare(const T* a, const T* b, size_t size)
193     {
194         for (size_t i = 0; i < size; ++i)
195             if (!(a[i] == b[i]))
196                 return false;
197         return true;
198     }
199 };
200
201 template<typename T>
202 struct VectorComparer<true, T>
203 {
204     static bool compare(const T* a, const T* b, size_t size)
205     {
206         return memcmp(a, b, sizeof(T) * size) == 0;
207     }
208 };
209
210 template<typename T>
211 struct VectorTypeOperations
212 {
213     static void destruct(T* begin, T* end)
214     {
215         VectorDestructor<!std::is_trivially_destructible<T>::value, T>::destruct(begin, end);
216     }
217
218     static void initialize(T* begin, T* end)
219     {
220         VectorInitializer<VectorTraits<T>::needsInitialization, VectorTraits<T>::canInitializeWithMemset, T>::initialize(begin, end);
221     }
222
223     static void move(T* src, T* srcEnd, T* dst)
224     {
225         VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::move(src, srcEnd, dst);
226     }
227
228     static void moveOverlapping(T* src, T* srcEnd, T* dst)
229     {
230         VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::moveOverlapping(src, srcEnd, dst);
231     }
232
233     static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
234     {
235         VectorCopier<VectorTraits<T>::canCopyWithMemcpy, T>::uninitializedCopy(src, srcEnd, dst);
236     }
237
238     static void uninitializedFill(T* dst, T* dstEnd, const T& val)
239     {
240         VectorFiller<VectorTraits<T>::canFillWithMemset, T>::uninitializedFill(dst, dstEnd, val);
241     }
242     
243     static bool compare(const T* a, const T* b, size_t size)
244     {
245         return VectorComparer<VectorTraits<T>::canCompareWithMemcmp, T>::compare(a, b, size);
246     }
247 };
248
249 template<typename T>
250 class VectorBufferBase {
251     WTF_MAKE_NONCOPYABLE(VectorBufferBase);
252 public:
253     void allocateBuffer(size_t newCapacity)
254     {
255         ASSERT(newCapacity);
256         if (newCapacity > std::numeric_limits<unsigned>::max() / sizeof(T))
257             CRASH();
258         size_t sizeToAllocate = fastMallocGoodSize(newCapacity * sizeof(T));
259         m_capacity = sizeToAllocate / sizeof(T);
260         m_buffer = static_cast<T*>(fastMalloc(sizeToAllocate));
261     }
262
263     bool tryAllocateBuffer(size_t newCapacity)
264     {
265         ASSERT(newCapacity);
266         if (newCapacity > std::numeric_limits<unsigned>::max() / sizeof(T))
267             return false;
268
269         size_t sizeToAllocate = fastMallocGoodSize(newCapacity * sizeof(T));
270         T* newBuffer;
271         if (tryFastMalloc(sizeToAllocate).getValue(newBuffer)) {
272             m_capacity = sizeToAllocate / sizeof(T);
273             m_buffer = newBuffer;
274             return true;
275         }
276         return false;
277     }
278
279     bool shouldReallocateBuffer(size_t newCapacity) const
280     {
281         return VectorTraits<T>::canMoveWithMemcpy && m_capacity && newCapacity;
282     }
283
284     void reallocateBuffer(size_t newCapacity)
285     {
286         ASSERT(shouldReallocateBuffer(newCapacity));
287         if (newCapacity > std::numeric_limits<size_t>::max() / sizeof(T))
288             CRASH();
289         size_t sizeToAllocate = fastMallocGoodSize(newCapacity * sizeof(T));
290         m_capacity = sizeToAllocate / sizeof(T);
291         m_buffer = static_cast<T*>(fastRealloc(m_buffer, sizeToAllocate));
292     }
293
294     void deallocateBuffer(T* bufferToDeallocate)
295     {
296         if (!bufferToDeallocate)
297             return;
298         
299         if (m_buffer == bufferToDeallocate) {
300             m_buffer = 0;
301             m_capacity = 0;
302         }
303
304         fastFree(bufferToDeallocate);
305     }
306
307     T* buffer() { return m_buffer; }
308     const T* buffer() const { return m_buffer; }
309     static ptrdiff_t bufferMemoryOffset() { return OBJECT_OFFSETOF(VectorBufferBase, m_buffer); }
310     size_t capacity() const { return m_capacity; }
311
312     MallocPtr<T> releaseBuffer()
313     {
314         T* buffer = m_buffer;
315         m_buffer = 0;
316         m_capacity = 0;
317         return adoptMallocPtr(buffer);
318     }
319
320 protected:
321     VectorBufferBase()
322         : m_buffer(0)
323         , m_capacity(0)
324         , m_size(0)
325     {
326     }
327
328     VectorBufferBase(T* buffer, size_t capacity, size_t size)
329         : m_buffer(buffer)
330         , m_capacity(capacity)
331         , m_size(size)
332     {
333     }
334
335     ~VectorBufferBase()
336     {
337         // FIXME: It would be nice to find a way to ASSERT that m_buffer hasn't leaked here.
338     }
339
340     T* m_buffer;
341     unsigned m_capacity;
342     unsigned m_size; // Only used by the Vector subclass, but placed here to avoid padding the struct.
343 };
344
345 template<typename T, size_t inlineCapacity>
346 class VectorBuffer;
347
348 template<typename T>
349 class VectorBuffer<T, 0> : private VectorBufferBase<T> {
350 private:
351     typedef VectorBufferBase<T> Base;
352 public:
353     VectorBuffer()
354     {
355     }
356
357     VectorBuffer(size_t capacity, size_t size = 0)
358     {
359         m_size = size;
360         // Calling malloc(0) might take a lock and may actually do an
361         // allocation on some systems.
362         if (capacity)
363             allocateBuffer(capacity);
364     }
365
366     ~VectorBuffer()
367     {
368         deallocateBuffer(buffer());
369     }
370     
371     void swap(VectorBuffer<T, 0>& other)
372     {
373         std::swap(m_buffer, other.m_buffer);
374         std::swap(m_capacity, other.m_capacity);
375     }
376     
377     void restoreInlineBufferIfNeeded() { }
378
379     using Base::allocateBuffer;
380     using Base::tryAllocateBuffer;
381     using Base::shouldReallocateBuffer;
382     using Base::reallocateBuffer;
383     using Base::deallocateBuffer;
384
385     using Base::buffer;
386     using Base::capacity;
387     using Base::bufferMemoryOffset;
388
389     using Base::releaseBuffer;
390
391 protected:
392     using Base::m_size;
393
394 private:
395     using Base::m_buffer;
396     using Base::m_capacity;
397 };
398
399 template<typename T, size_t inlineCapacity>
400 class VectorBuffer : private VectorBufferBase<T> {
401     WTF_MAKE_NONCOPYABLE(VectorBuffer);
402 private:
403     typedef VectorBufferBase<T> Base;
404 public:
405     VectorBuffer()
406         : Base(inlineBuffer(), inlineCapacity, 0)
407     {
408     }
409
410     VectorBuffer(size_t capacity, size_t size = 0)
411         : Base(inlineBuffer(), inlineCapacity, size)
412     {
413         if (capacity > inlineCapacity)
414             Base::allocateBuffer(capacity);
415     }
416
417     ~VectorBuffer()
418     {
419         deallocateBuffer(buffer());
420     }
421
422     void allocateBuffer(size_t newCapacity)
423     {
424         // FIXME: This should ASSERT(!m_buffer) to catch misuse/leaks.
425         if (newCapacity > inlineCapacity)
426             Base::allocateBuffer(newCapacity);
427         else {
428             m_buffer = inlineBuffer();
429             m_capacity = inlineCapacity;
430         }
431     }
432
433     bool tryAllocateBuffer(size_t newCapacity)
434     {
435         if (newCapacity > inlineCapacity)
436             return Base::tryAllocateBuffer(newCapacity);
437         m_buffer = inlineBuffer();
438         m_capacity = inlineCapacity;
439         return true;
440     }
441
442     void deallocateBuffer(T* bufferToDeallocate)
443     {
444         if (bufferToDeallocate == inlineBuffer())
445             return;
446         Base::deallocateBuffer(bufferToDeallocate);
447     }
448
449     bool shouldReallocateBuffer(size_t newCapacity) const
450     {
451         // We cannot reallocate the inline buffer.
452         return Base::shouldReallocateBuffer(newCapacity) && std::min(static_cast<size_t>(m_capacity), newCapacity) > inlineCapacity;
453     }
454
455     void reallocateBuffer(size_t newCapacity)
456     {
457         ASSERT(shouldReallocateBuffer(newCapacity));
458         Base::reallocateBuffer(newCapacity);
459     }
460
461     void swap(VectorBuffer& other)
462     {
463         if (buffer() == inlineBuffer() && other.buffer() == other.inlineBuffer()) {
464             std::swap(m_inlineBuffer, other.m_inlineBuffer);
465             std::swap(m_capacity, other.m_capacity);
466         } else if (buffer() == inlineBuffer()) {
467             m_buffer = other.m_buffer;
468             other.m_buffer = other.inlineBuffer();
469             std::swap(m_inlineBuffer, other.m_inlineBuffer);
470             std::swap(m_capacity, other.m_capacity);
471         } else if (other.buffer() == other.inlineBuffer()) {
472             other.m_buffer = m_buffer;
473             m_buffer = inlineBuffer();
474             std::swap(m_inlineBuffer, other.m_inlineBuffer);
475             std::swap(m_capacity, other.m_capacity);
476         } else {
477             std::swap(m_buffer, other.m_buffer);
478             std::swap(m_capacity, other.m_capacity);
479         }
480     }
481
482     void restoreInlineBufferIfNeeded()
483     {
484         if (m_buffer)
485             return;
486         m_buffer = inlineBuffer();
487         m_capacity = inlineCapacity;
488     }
489
490     using Base::buffer;
491     using Base::capacity;
492     using Base::bufferMemoryOffset;
493
494     MallocPtr<T> releaseBuffer()
495     {
496         if (buffer() == inlineBuffer())
497             return nullptr;
498         return Base::releaseBuffer();
499     }
500
501 protected:
502     using Base::m_size;
503
504 private:
505     using Base::m_buffer;
506     using Base::m_capacity;
507
508     T* inlineBuffer() { return reinterpret_cast_ptr<T*>(m_inlineBuffer); }
509     const T* inlineBuffer() const { return reinterpret_cast_ptr<const T*>(m_inlineBuffer); }
510
511     typename std::aligned_storage<sizeof(T), std::alignment_of<T>::value>::type m_inlineBuffer[inlineCapacity];
512 };
513
514 struct UnsafeVectorOverflow {
515     static NO_RETURN_DUE_TO_ASSERT void overflowed()
516     {
517         ASSERT_NOT_REACHED();
518     }
519 };
520
521 template<typename T, size_t inlineCapacity = 0, typename OverflowHandler = CrashOnOverflow>
522 class Vector : private VectorBuffer<T, inlineCapacity> {
523     WTF_MAKE_FAST_ALLOCATED;
524 private:
525     typedef VectorBuffer<T, inlineCapacity> Base;
526     typedef VectorTypeOperations<T> TypeOperations;
527
528 public:
529     typedef T ValueType;
530
531     typedef T* iterator;
532     typedef const T* const_iterator;
533     typedef std::reverse_iterator<iterator> reverse_iterator;
534     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
535
536     Vector()
537     {
538     }
539
540     // Unlike in std::vector, this constructor does not initialize POD types.
541     explicit Vector(size_t size)
542         : Base(size, size)
543     {
544         if (begin())
545             TypeOperations::initialize(begin(), end());
546     }
547
548     Vector(size_t size, const T& val)
549         : Base(size, size)
550     {
551         if (begin())
552             TypeOperations::uninitializedFill(begin(), end(), val);
553     }
554
555     Vector(std::initializer_list<T> initializerList)
556     {
557         reserveInitialCapacity(initializerList.size());
558         for (const auto& element : initializerList)
559             uncheckedAppend(element);
560     }
561
562     ~Vector()
563     {
564         if (m_size)
565             shrink(0);
566     }
567
568     Vector(const Vector&);
569     template<size_t otherCapacity, typename otherOverflowBehaviour>
570     Vector(const Vector<T, otherCapacity, otherOverflowBehaviour>&);
571
572     Vector& operator=(const Vector&);
573     template<size_t otherCapacity, typename otherOverflowBehaviour>
574     Vector& operator=(const Vector<T, otherCapacity, otherOverflowBehaviour>&);
575
576     Vector(Vector&&);
577     Vector& operator=(Vector&&);
578
579     size_t size() const { return m_size; }
580     static ptrdiff_t sizeMemoryOffset() { return OBJECT_OFFSETOF(Vector, m_size); }
581     size_t capacity() const { return Base::capacity(); }
582     bool isEmpty() const { return !size(); }
583
584     T& at(size_t i)
585     {
586         if (UNLIKELY(i >= size()))
587             OverflowHandler::overflowed();
588         return Base::buffer()[i];
589     }
590     const T& at(size_t i) const 
591     {
592         if (UNLIKELY(i >= size()))
593             OverflowHandler::overflowed();
594         return Base::buffer()[i];
595     }
596     T& at(Checked<size_t> i)
597     {
598         RELEASE_ASSERT(i < size());
599         return Base::buffer()[i];
600     }
601     const T& at(Checked<size_t> i) const
602     {
603         RELEASE_ASSERT(i < size());
604         return Base::buffer()[i];
605     }
606
607     T& operator[](size_t i) { return at(i); }
608     const T& operator[](size_t i) const { return at(i); }
609     T& operator[](Checked<size_t> i) { return at(i); }
610     const T& operator[](Checked<size_t> i) const { return at(i); }
611
612     T* data() { return Base::buffer(); }
613     const T* data() const { return Base::buffer(); }
614     static ptrdiff_t dataMemoryOffset() { return Base::bufferMemoryOffset(); }
615
616     iterator begin() { return data(); }
617     iterator end() { return begin() + m_size; }
618     const_iterator begin() const { return data(); }
619     const_iterator end() const { return begin() + m_size; }
620
621     reverse_iterator rbegin() { return reverse_iterator(end()); }
622     reverse_iterator rend() { return reverse_iterator(begin()); }
623     const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
624     const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
625
626     T& first() { return at(0); }
627     const T& first() const { return at(0); }
628     T& last() { return at(size() - 1); }
629     const T& last() const { return at(size() - 1); }
630     
631     T takeLast()
632     {
633         T result = last();
634         removeLast();
635         return result;
636     }
637     
638     template<typename U> bool contains(const U&) const;
639     template<typename U> size_t find(const U&) const;
640     template<typename U> size_t reverseFind(const U&) const;
641
642     void shrink(size_t size);
643     void grow(size_t size);
644     void resize(size_t size);
645     void resizeToFit(size_t size);
646     void reserveCapacity(size_t newCapacity);
647     bool tryReserveCapacity(size_t newCapacity);
648     void reserveInitialCapacity(size_t initialCapacity);
649     void shrinkCapacity(size_t newCapacity);
650     void shrinkToFit() { shrinkCapacity(size()); }
651
652     void clear() { shrinkCapacity(0); }
653
654     template<typename U> void append(const U*, size_t);
655     template<typename U> void append(U&&);
656     template<typename U> void uncheckedAppend(U&& val);
657     template<typename U, size_t otherCapacity> void appendVector(const Vector<U, otherCapacity>&);
658     template<typename U> bool tryAppend(const U*, size_t);
659
660     template<typename U> void insert(size_t position, const U*, size_t);
661     template<typename U> void insert(size_t position, U&&);
662     template<typename U, size_t c> void insertVector(size_t position, const Vector<U, c>&);
663
664     void remove(size_t position);
665     void remove(size_t position, size_t length);
666
667     void removeLast() 
668     {
669         if (UNLIKELY(isEmpty()))
670             OverflowHandler::overflowed();
671         shrink(size() - 1); 
672     }
673
674     void fill(const T&, size_t);
675     void fill(const T& val) { fill(val, size()); }
676
677     template<typename Iterator> void appendRange(Iterator start, Iterator end);
678
679     MallocPtr<T> releaseBuffer();
680
681     void swap(Vector<T, inlineCapacity, OverflowHandler>& other)
682     {
683         std::swap(m_size, other.m_size);
684         Base::swap(other);
685     }
686
687     void reverse();
688
689     void checkConsistency();
690
691 private:
692     void expandCapacity(size_t newMinCapacity);
693     T* expandCapacity(size_t newMinCapacity, T*);
694     bool tryExpandCapacity(size_t newMinCapacity);
695     const T* tryExpandCapacity(size_t newMinCapacity, const T*);
696     template<typename U> U* expandCapacity(size_t newMinCapacity, U*); 
697     template<typename U> void appendSlowCase(U&&);
698
699     using Base::m_size;
700     using Base::buffer;
701     using Base::capacity;
702     using Base::swap;
703     using Base::allocateBuffer;
704     using Base::deallocateBuffer;
705     using Base::tryAllocateBuffer;
706     using Base::shouldReallocateBuffer;
707     using Base::reallocateBuffer;
708     using Base::restoreInlineBufferIfNeeded;
709     using Base::releaseBuffer;
710 };
711
712 template<typename T, size_t inlineCapacity, typename OverflowHandler>
713 Vector<T, inlineCapacity, OverflowHandler>::Vector(const Vector& other)
714     : Base(other.capacity(), other.size())
715 {
716     if (begin())
717         TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
718 }
719
720 template<typename T, size_t inlineCapacity, typename OverflowHandler>
721 template<size_t otherCapacity, typename otherOverflowBehaviour>
722 Vector<T, inlineCapacity, OverflowHandler>::Vector(const Vector<T, otherCapacity, otherOverflowBehaviour>& other)
723     : Base(other.capacity(), other.size())
724 {
725     if (begin())
726         TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
727 }
728
729 template<typename T, size_t inlineCapacity, typename OverflowHandler>
730 Vector<T, inlineCapacity, OverflowHandler>& Vector<T, inlineCapacity, OverflowHandler>::operator=(const Vector<T, inlineCapacity, OverflowHandler>& other)
731 {
732     if (&other == this)
733         return *this;
734     
735     if (size() > other.size())
736         shrink(other.size());
737     else if (other.size() > capacity()) {
738         clear();
739         reserveCapacity(other.size());
740         ASSERT(begin());
741     }
742     
743 // Works around an assert in VS2010. See https://connect.microsoft.com/VisualStudio/feedback/details/558044/std-copy-should-not-check-dest-when-first-last
744 #if COMPILER(MSVC) && defined(_ITERATOR_DEBUG_LEVEL) && _ITERATOR_DEBUG_LEVEL
745     if (!begin())
746         return *this;
747 #endif
748
749     std::copy(other.begin(), other.begin() + size(), begin());
750     TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
751     m_size = other.size();
752
753     return *this;
754 }
755
756 inline bool typelessPointersAreEqual(const void* a, const void* b) { return a == b; }
757
758 template<typename T, size_t inlineCapacity, typename OverflowHandler>
759 template<size_t otherCapacity, typename otherOverflowBehaviour>
760 Vector<T, inlineCapacity, OverflowHandler>& Vector<T, inlineCapacity, OverflowHandler>::operator=(const Vector<T, otherCapacity, otherOverflowBehaviour>& other)
761 {
762     // If the inline capacities match, we should call the more specific
763     // template.  If the inline capacities don't match, the two objects
764     // shouldn't be allocated the same address.
765     ASSERT(!typelessPointersAreEqual(&other, this));
766
767     if (size() > other.size())
768         shrink(other.size());
769     else if (other.size() > capacity()) {
770         clear();
771         reserveCapacity(other.size());
772         ASSERT(begin());
773     }
774     
775 // Works around an assert in VS2010. See https://connect.microsoft.com/VisualStudio/feedback/details/558044/std-copy-should-not-check-dest-when-first-last
776 #if COMPILER(MSVC) && defined(_ITERATOR_DEBUG_LEVEL) && _ITERATOR_DEBUG_LEVEL
777     if (!begin())
778         return *this;
779 #endif
780
781     std::copy(other.begin(), other.begin() + size(), begin());
782     TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
783     m_size = other.size();
784
785     return *this;
786 }
787
788 template<typename T, size_t inlineCapacity, typename OverflowHandler>
789 inline Vector<T, inlineCapacity, OverflowHandler>::Vector(Vector<T, inlineCapacity, OverflowHandler>&& other)
790 {
791     swap(other);
792 }
793
794 template<typename T, size_t inlineCapacity, typename OverflowHandler>
795 inline Vector<T, inlineCapacity, OverflowHandler>& Vector<T, inlineCapacity, OverflowHandler>::operator=(Vector<T, inlineCapacity, OverflowHandler>&& other)
796 {
797     swap(other);
798     return *this;
799 }
800
801 template<typename T, size_t inlineCapacity, typename OverflowHandler>
802 template<typename U>
803 bool Vector<T, inlineCapacity, OverflowHandler>::contains(const U& value) const
804 {
805     return find(value) != notFound;
806 }
807
808 template<typename T, size_t inlineCapacity, typename OverflowHandler>
809 template<typename U>
810 size_t Vector<T, inlineCapacity, OverflowHandler>::find(const U& value) const
811 {
812     for (size_t i = 0; i < size(); ++i) {
813         if (at(i) == value)
814             return i;
815     }
816     return notFound;
817 }
818
819 template<typename T, size_t inlineCapacity, typename OverflowHandler>
820 template<typename U>
821 size_t Vector<T, inlineCapacity, OverflowHandler>::reverseFind(const U& value) const
822 {
823     for (size_t i = 1; i <= size(); ++i) {
824         const size_t index = size() - i;
825         if (at(index) == value)
826             return index;
827     }
828     return notFound;
829 }
830
831 template<typename T, size_t inlineCapacity, typename OverflowHandler>
832 void Vector<T, inlineCapacity, OverflowHandler>::fill(const T& val, size_t newSize)
833 {
834     if (size() > newSize)
835         shrink(newSize);
836     else if (newSize > capacity()) {
837         clear();
838         reserveCapacity(newSize);
839         ASSERT(begin());
840     }
841     
842     std::fill(begin(), end(), val);
843     TypeOperations::uninitializedFill(end(), begin() + newSize, val);
844     m_size = newSize;
845 }
846
847 template<typename T, size_t inlineCapacity, typename OverflowHandler>
848 template<typename Iterator>
849 void Vector<T, inlineCapacity, OverflowHandler>::appendRange(Iterator start, Iterator end)
850 {
851     for (Iterator it = start; it != end; ++it)
852         append(*it);
853 }
854
855 template<typename T, size_t inlineCapacity, typename OverflowHandler>
856 void Vector<T, inlineCapacity, OverflowHandler>::expandCapacity(size_t newMinCapacity)
857 {
858     reserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1)));
859 }
860
861 template<typename T, size_t inlineCapacity, typename OverflowHandler>
862 T* Vector<T, inlineCapacity, OverflowHandler>::expandCapacity(size_t newMinCapacity, T* ptr)
863 {
864     if (ptr < begin() || ptr >= end()) {
865         expandCapacity(newMinCapacity);
866         return ptr;
867     }
868     size_t index = ptr - begin();
869     expandCapacity(newMinCapacity);
870     return begin() + index;
871 }
872
873 template<typename T, size_t inlineCapacity, typename OverflowHandler>
874 bool Vector<T, inlineCapacity, OverflowHandler>::tryExpandCapacity(size_t newMinCapacity)
875 {
876     return tryReserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1)));
877 }
878
879 template<typename T, size_t inlineCapacity, typename OverflowHandler>
880 const T* Vector<T, inlineCapacity, OverflowHandler>::tryExpandCapacity(size_t newMinCapacity, const T* ptr)
881 {
882     if (ptr < begin() || ptr >= end()) {
883         if (!tryExpandCapacity(newMinCapacity))
884             return 0;
885         return ptr;
886     }
887     size_t index = ptr - begin();
888     if (!tryExpandCapacity(newMinCapacity))
889         return 0;
890     return begin() + index;
891 }
892
893 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
894 inline U* Vector<T, inlineCapacity, OverflowHandler>::expandCapacity(size_t newMinCapacity, U* ptr)
895 {
896     expandCapacity(newMinCapacity);
897     return ptr;
898 }
899
900 template<typename T, size_t inlineCapacity, typename OverflowHandler>
901 inline void Vector<T, inlineCapacity, OverflowHandler>::resize(size_t size)
902 {
903     if (size <= m_size)
904         TypeOperations::destruct(begin() + size, end());
905     else {
906         if (size > capacity())
907             expandCapacity(size);
908         if (begin())
909             TypeOperations::initialize(end(), begin() + size);
910     }
911     
912     m_size = size;
913 }
914
915 template<typename T, size_t inlineCapacity, typename OverflowHandler>
916 void Vector<T, inlineCapacity, OverflowHandler>::resizeToFit(size_t size)
917 {
918     reserveCapacity(size);
919     resize(size);
920 }
921
922 template<typename T, size_t inlineCapacity, typename OverflowHandler>
923 void Vector<T, inlineCapacity, OverflowHandler>::shrink(size_t size)
924 {
925     ASSERT(size <= m_size);
926     TypeOperations::destruct(begin() + size, end());
927     m_size = size;
928 }
929
930 template<typename T, size_t inlineCapacity, typename OverflowHandler>
931 void Vector<T, inlineCapacity, OverflowHandler>::grow(size_t size)
932 {
933     ASSERT(size >= m_size);
934     if (size > capacity())
935         expandCapacity(size);
936     if (begin())
937         TypeOperations::initialize(end(), begin() + size);
938     m_size = size;
939 }
940
941 template<typename T, size_t inlineCapacity, typename OverflowHandler>
942 void Vector<T, inlineCapacity, OverflowHandler>::reserveCapacity(size_t newCapacity)
943 {
944     if (newCapacity <= capacity())
945         return;
946     T* oldBuffer = begin();
947     T* oldEnd = end();
948     Base::allocateBuffer(newCapacity);
949     ASSERT(begin());
950     TypeOperations::move(oldBuffer, oldEnd, begin());
951     Base::deallocateBuffer(oldBuffer);
952 }
953
954 template<typename T, size_t inlineCapacity, typename OverflowHandler>
955 bool Vector<T, inlineCapacity, OverflowHandler>::tryReserveCapacity(size_t newCapacity)
956 {
957     if (newCapacity <= capacity())
958         return true;
959     T* oldBuffer = begin();
960     T* oldEnd = end();
961     if (!Base::tryAllocateBuffer(newCapacity))
962         return false;
963     ASSERT(begin());
964     TypeOperations::move(oldBuffer, oldEnd, begin());
965     Base::deallocateBuffer(oldBuffer);
966     return true;
967 }
968
969 template<typename T, size_t inlineCapacity, typename OverflowHandler>
970 inline void Vector<T, inlineCapacity, OverflowHandler>::reserveInitialCapacity(size_t initialCapacity)
971 {
972     ASSERT(!m_size);
973     ASSERT(capacity() == inlineCapacity);
974     if (initialCapacity > inlineCapacity)
975         Base::allocateBuffer(initialCapacity);
976 }
977
978 template<typename T, size_t inlineCapacity, typename OverflowHandler>
979 void Vector<T, inlineCapacity, OverflowHandler>::shrinkCapacity(size_t newCapacity)
980 {
981     if (newCapacity >= capacity())
982         return;
983
984     if (newCapacity < size()) 
985         shrink(newCapacity);
986
987     T* oldBuffer = begin();
988     if (newCapacity > 0) {
989         if (Base::shouldReallocateBuffer(newCapacity)) {
990             Base::reallocateBuffer(newCapacity);
991             return;
992         }
993
994         T* oldEnd = end();
995         Base::allocateBuffer(newCapacity);
996         if (begin() != oldBuffer)
997             TypeOperations::move(oldBuffer, oldEnd, begin());
998     }
999
1000     Base::deallocateBuffer(oldBuffer);
1001     Base::restoreInlineBufferIfNeeded();
1002 }
1003
1004 // Templatizing these is better than just letting the conversion happen implicitly,
1005 // because for instance it allows a PassRefPtr to be appended to a RefPtr vector
1006 // without refcount thrash.
1007
1008 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
1009 void Vector<T, inlineCapacity, OverflowHandler>::append(const U* data, size_t dataSize)
1010 {
1011     size_t newSize = m_size + dataSize;
1012     if (newSize > capacity()) {
1013         data = expandCapacity(newSize, data);
1014         ASSERT(begin());
1015     }
1016     if (newSize < m_size)
1017         CRASH();
1018     T* dest = end();
1019     for (size_t i = 0; i < dataSize; ++i)
1020         new (NotNull, &dest[i]) T(data[i]);
1021     m_size = newSize;
1022 }
1023
1024 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
1025 bool Vector<T, inlineCapacity, OverflowHandler>::tryAppend(const U* data, size_t dataSize)
1026 {
1027     size_t newSize = m_size + dataSize;
1028     if (newSize > capacity()) {
1029         data = tryExpandCapacity(newSize, data);
1030         if (!data)
1031             return false;
1032         ASSERT(begin());
1033     }
1034     if (newSize < m_size)
1035         return false;
1036     T* dest = end();
1037     for (size_t i = 0; i < dataSize; ++i)
1038         new (NotNull, &dest[i]) T(data[i]);
1039     m_size = newSize;
1040     return true;
1041 }
1042
1043 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
1044 ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler>::append(U&& value)
1045 {
1046     if (size() != capacity()) {
1047         new (NotNull, end()) T(std::forward<U>(value));
1048         ++m_size;
1049         return;
1050     }
1051
1052     appendSlowCase(std::forward<U>(value));
1053 }
1054
1055 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
1056 void Vector<T, inlineCapacity, OverflowHandler>::appendSlowCase(U&& value)
1057 {
1058     ASSERT(size() == capacity());
1059
1060     auto ptr = const_cast<typename std::remove_const<typename std::remove_reference<U>::type>::type*>(std::addressof(value));
1061     ptr = expandCapacity(size() + 1, ptr);
1062     ASSERT(begin());
1063
1064     new (NotNull, end()) T(std::forward<U>(*ptr));
1065     ++m_size;
1066 }
1067
1068 // This version of append saves a branch in the case where you know that the
1069 // vector's capacity is large enough for the append to succeed.
1070
1071 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
1072 inline void Vector<T, inlineCapacity, OverflowHandler>::uncheckedAppend(U&& value)
1073 {
1074     ASSERT(size() < capacity());
1075
1076     auto ptr = std::addressof(value);
1077     new (NotNull, end()) T(std::forward<U>(*ptr));
1078     ++m_size;
1079 }
1080
1081 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U, size_t otherCapacity>
1082 inline void Vector<T, inlineCapacity, OverflowHandler>::appendVector(const Vector<U, otherCapacity>& val)
1083 {
1084     append(val.begin(), val.size());
1085 }
1086
1087 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
1088 void Vector<T, inlineCapacity, OverflowHandler>::insert(size_t position, const U* data, size_t dataSize)
1089 {
1090     ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
1091     size_t newSize = m_size + dataSize;
1092     if (newSize > capacity()) {
1093         data = expandCapacity(newSize, data);
1094         ASSERT(begin());
1095     }
1096     if (newSize < m_size)
1097         CRASH();
1098     T* spot = begin() + position;
1099     TypeOperations::moveOverlapping(spot, end(), spot + dataSize);
1100     for (size_t i = 0; i < dataSize; ++i)
1101         new (NotNull, &spot[i]) T(data[i]);
1102     m_size = newSize;
1103 }
1104  
1105 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U>
1106 inline void Vector<T, inlineCapacity, OverflowHandler>::insert(size_t position, U&& value)
1107 {
1108     ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
1109
1110     auto ptr = const_cast<typename std::remove_const<typename std::remove_reference<U>::type>::type*>(std::addressof(value));
1111     if (size() == capacity()) {
1112         ptr = expandCapacity(size() + 1, ptr);
1113         ASSERT(begin());
1114     }
1115
1116     T* spot = begin() + position;
1117     TypeOperations::moveOverlapping(spot, end(), spot + 1);
1118     new (NotNull, spot) T(std::forward<U>(*ptr));
1119     ++m_size;
1120 }
1121
1122 template<typename T, size_t inlineCapacity, typename OverflowHandler> template<typename U, size_t c>
1123 inline void Vector<T, inlineCapacity, OverflowHandler>::insertVector(size_t position, const Vector<U, c>& val)
1124 {
1125     insert(position, val.begin(), val.size());
1126 }
1127
1128 template<typename T, size_t inlineCapacity, typename OverflowHandler>
1129 inline void Vector<T, inlineCapacity, OverflowHandler>::remove(size_t position)
1130 {
1131     ASSERT_WITH_SECURITY_IMPLICATION(position < size());
1132     T* spot = begin() + position;
1133     spot->~T();
1134     TypeOperations::moveOverlapping(spot + 1, end(), spot);
1135     --m_size;
1136 }
1137
1138 template<typename T, size_t inlineCapacity, typename OverflowHandler>
1139 inline void Vector<T, inlineCapacity, OverflowHandler>::remove(size_t position, size_t length)
1140 {
1141     ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
1142     ASSERT_WITH_SECURITY_IMPLICATION(position + length <= size());
1143     T* beginSpot = begin() + position;
1144     T* endSpot = beginSpot + length;
1145     TypeOperations::destruct(beginSpot, endSpot); 
1146     TypeOperations::moveOverlapping(endSpot, end(), beginSpot);
1147     m_size -= length;
1148 }
1149
1150 template<typename T, size_t inlineCapacity, typename OverflowHandler>
1151 inline void Vector<T, inlineCapacity, OverflowHandler>::reverse()
1152 {
1153     for (size_t i = 0; i < m_size / 2; ++i)
1154         std::swap(at(i), at(m_size - 1 - i));
1155 }
1156
1157 template<typename T, size_t inlineCapacity, typename OverflowHandler>
1158 inline MallocPtr<T> Vector<T, inlineCapacity, OverflowHandler>::releaseBuffer()
1159 {
1160     auto buffer = Base::releaseBuffer();
1161     if (inlineCapacity && !buffer && m_size) {
1162         // If the vector had some data, but no buffer to release,
1163         // that means it was using the inline buffer. In that case,
1164         // we create a brand new buffer so the caller always gets one.
1165         size_t bytes = m_size * sizeof(T);
1166         buffer = adoptMallocPtr(static_cast<T*>(fastMalloc(bytes)));
1167         memcpy(buffer.get(), data(), bytes);
1168     }
1169     m_size = 0;
1170     return buffer;
1171 }
1172
1173 template<typename T, size_t inlineCapacity, typename OverflowHandler>
1174 inline void Vector<T, inlineCapacity, OverflowHandler>::checkConsistency()
1175 {
1176 #if !ASSERT_DISABLED
1177     for (size_t i = 0; i < size(); ++i)
1178         ValueCheck<T>::checkConsistency(at(i));
1179 #endif
1180 }
1181
1182 template<typename T, size_t inlineCapacity, typename OverflowHandler>
1183 void deprecatedDeleteAllValues(const Vector<T, inlineCapacity, OverflowHandler>& collection)
1184 {
1185     typedef typename Vector<T, inlineCapacity, OverflowHandler>::const_iterator iterator;
1186     iterator end = collection.end();
1187     for (iterator it = collection.begin(); it != end; ++it)
1188         delete *it;
1189 }
1190
1191 template<typename T, size_t inlineCapacity, typename OverflowHandler>
1192 inline void swap(Vector<T, inlineCapacity, OverflowHandler>& a, Vector<T, inlineCapacity, OverflowHandler>& b)
1193 {
1194     a.swap(b);
1195 }
1196
1197 template<typename T, size_t inlineCapacity, typename OverflowHandler>
1198 bool operator==(const Vector<T, inlineCapacity, OverflowHandler>& a, const Vector<T, inlineCapacity, OverflowHandler>& b)
1199 {
1200     if (a.size() != b.size())
1201         return false;
1202
1203     return VectorTypeOperations<T>::compare(a.data(), b.data(), a.size());
1204 }
1205
1206 template<typename T, size_t inlineCapacity, typename OverflowHandler>
1207 inline bool operator!=(const Vector<T, inlineCapacity, OverflowHandler>& a, const Vector<T, inlineCapacity, OverflowHandler>& b)
1208 {
1209     return !(a == b);
1210 }
1211
1212 #if !ASSERT_DISABLED
1213 template<typename T> struct ValueCheck<Vector<T>> {
1214     typedef Vector<T> TraitType;
1215     static void checkConsistency(const Vector<T>& v)
1216     {
1217         v.checkConsistency();
1218     }
1219 };
1220 #endif
1221
1222 } // namespace WTF
1223
1224 using WTF::Vector;
1225 using WTF::UnsafeVectorOverflow;
1226 using WTF::notFound;
1227
1228 #endif // WTF_Vector_h