Use pragma once in WTF
[WebKit-https.git] / Source / WTF / wtf / Vector.h
1 /*
2  *  Copyright (C) 2005-2017 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 #pragma once
22
23 #include <initializer_list>
24 #include <limits>
25 #include <string.h>
26 #include <type_traits>
27 #include <utility>
28 #include <wtf/CheckedArithmetic.h>
29 #include <wtf/FastMalloc.h>
30 #include <wtf/Forward.h>
31 #include <wtf/MallocPtr.h>
32 #include <wtf/MathExtras.h>
33 #include <wtf/Noncopyable.h>
34 #include <wtf/NotFound.h>
35 #include <wtf/StdLibExtras.h>
36 #include <wtf/ValueCheck.h>
37 #include <wtf/VectorTraits.h>
38
39 #if ASAN_ENABLED
40 extern "C" void __sanitizer_annotate_contiguous_container(const void* begin, const void* end, const void* old_mid, const void* new_mid);
41 #endif
42
43 namespace WTF {
44
45 template <bool needsDestruction, typename T>
46 struct VectorDestructor;
47
48 template<typename T>
49 struct VectorDestructor<false, T>
50 {
51     static void destruct(T*, T*) {}
52 };
53
54 template<typename T>
55 struct VectorDestructor<true, T>
56 {
57     static void destruct(T* begin, T* end) 
58     {
59         for (T* cur = begin; cur != end; ++cur)
60             cur->~T();
61     }
62 };
63
64 template <bool needsInitialization, bool canInitializeWithMemset, typename T>
65 struct VectorInitializer;
66
67 template<bool canInitializeWithMemset, typename T>
68 struct VectorInitializer<false, canInitializeWithMemset, T>
69 {
70     static void initializeIfNonPOD(T*, T*) { }
71
72     static void initialize(T* begin, T* end)
73     {
74         VectorInitializer<true, canInitializeWithMemset, T>::initialize(begin, end);
75     }
76 };
77
78 template<typename T>
79 struct VectorInitializer<true, false, T>
80 {
81     static void initializeIfNonPOD(T* begin, T* end)
82     {
83         for (T* cur = begin; cur != end; ++cur)
84             new (NotNull, cur) T();
85     }
86
87     static void initialize(T* begin, T* end)
88     {
89         initializeIfNonPOD(begin, end);
90     }
91 };
92
93 template<typename T>
94 struct VectorInitializer<true, true, T>
95 {
96     static void initializeIfNonPOD(T* begin, T* end)
97     {
98         memset(static_cast<void*>(begin), 0, reinterpret_cast<char*>(end) - reinterpret_cast<char*>(begin));
99     }
100
101     static void initialize(T* begin, T* end)
102     {
103         initializeIfNonPOD(begin, end);
104     }
105 };
106
107 template <bool canMoveWithMemcpy, typename T>
108 struct VectorMover;
109
110 template<typename T>
111 struct VectorMover<false, T>
112 {
113     static void move(T* src, T* srcEnd, T* dst)
114     {
115         while (src != srcEnd) {
116             new (NotNull, dst) T(WTFMove(*src));
117             src->~T();
118             ++dst;
119             ++src;
120         }
121     }
122     static void moveOverlapping(T* src, T* srcEnd, T* dst)
123     {
124         if (src > dst)
125             move(src, srcEnd, dst);
126         else {
127             T* dstEnd = dst + (srcEnd - src);
128             while (src != srcEnd) {
129                 --srcEnd;
130                 --dstEnd;
131                 new (NotNull, dstEnd) T(WTFMove(*srcEnd));
132                 srcEnd->~T();
133             }
134         }
135     }
136 };
137
138 template<typename T>
139 struct VectorMover<true, T>
140 {
141     static void move(const T* src, const T* srcEnd, T* dst) 
142     {
143         memcpy(static_cast<void*>(dst), static_cast<void*>(const_cast<T*>(src)), reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
144     }
145     static void moveOverlapping(const T* src, const T* srcEnd, T* dst) 
146     {
147         memmove(static_cast<void*>(dst), static_cast<void*>(const_cast<T*>(src)), reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
148     }
149 };
150
151 template <bool canCopyWithMemcpy, typename T>
152 struct VectorCopier;
153
154 template<typename T>
155 struct VectorCopier<false, T>
156 {
157     template<typename U>
158     static void uninitializedCopy(const T* src, const T* srcEnd, U* dst)
159     {
160         while (src != srcEnd) {
161             new (NotNull, dst) U(*src);
162             ++dst;
163             ++src;
164         }
165     }
166 };
167
168 template<typename T>
169 struct VectorCopier<true, T>
170 {
171     static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
172     {
173         memcpy(static_cast<void*>(dst), static_cast<void*>(const_cast<T*>(src)), reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
174     }
175     template<typename U>
176     static void uninitializedCopy(const T* src, const T* srcEnd, U* dst)
177     {
178         VectorCopier<false, T>::uninitializedCopy(src, srcEnd, dst);
179     }
180 };
181
182 template <bool canFillWithMemset, typename T>
183 struct VectorFiller;
184
185 template<typename T>
186 struct VectorFiller<false, T>
187 {
188     static void uninitializedFill(T* dst, T* dstEnd, const T& val) 
189     {
190         while (dst != dstEnd) {
191             new (NotNull, dst) T(val);
192             ++dst;
193         }
194     }
195 };
196
197 template<typename T>
198 struct VectorFiller<true, T>
199 {
200     static void uninitializedFill(T* dst, T* dstEnd, const T& val) 
201     {
202         static_assert(sizeof(T) == 1, "Size of type T should be equal to one!");
203 #if COMPILER(GCC_COMPATIBLE) && defined(_FORTIFY_SOURCE)
204         if (!__builtin_constant_p(dstEnd - dst) || (!(dstEnd - dst)))
205 #endif
206             memset(dst, val, dstEnd - dst);
207     }
208 };
209
210 template<bool canCompareWithMemcmp, typename T>
211 struct VectorComparer;
212
213 template<typename T>
214 struct VectorComparer<false, T>
215 {
216     static bool compare(const T* a, const T* b, size_t size)
217     {
218         for (size_t i = 0; i < size; ++i)
219             if (!(a[i] == b[i]))
220                 return false;
221         return true;
222     }
223 };
224
225 template<typename T>
226 struct VectorComparer<true, T>
227 {
228     static bool compare(const T* a, const T* b, size_t size)
229     {
230         return memcmp(a, b, sizeof(T) * size) == 0;
231     }
232 };
233
234 template<typename T>
235 struct VectorTypeOperations
236 {
237     static void destruct(T* begin, T* end)
238     {
239         VectorDestructor<!std::is_trivially_destructible<T>::value, T>::destruct(begin, end);
240     }
241
242     static void initializeIfNonPOD(T* begin, T* end)
243     {
244         VectorInitializer<VectorTraits<T>::needsInitialization, VectorTraits<T>::canInitializeWithMemset, T>::initializeIfNonPOD(begin, end);
245     }
246
247     static void initialize(T* begin, T* end)
248     {
249         VectorInitializer<VectorTraits<T>::needsInitialization, VectorTraits<T>::canInitializeWithMemset, T>::initialize(begin, end);
250     }
251
252     static void move(T* src, T* srcEnd, T* dst)
253     {
254         VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::move(src, srcEnd, dst);
255     }
256
257     static void moveOverlapping(T* src, T* srcEnd, T* dst)
258     {
259         VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::moveOverlapping(src, srcEnd, dst);
260     }
261
262     static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
263     {
264         VectorCopier<VectorTraits<T>::canCopyWithMemcpy, T>::uninitializedCopy(src, srcEnd, dst);
265     }
266
267     static void uninitializedFill(T* dst, T* dstEnd, const T& val)
268     {
269         VectorFiller<VectorTraits<T>::canFillWithMemset, T>::uninitializedFill(dst, dstEnd, val);
270     }
271     
272     static bool compare(const T* a, const T* b, size_t size)
273     {
274         return VectorComparer<VectorTraits<T>::canCompareWithMemcmp, T>::compare(a, b, size);
275     }
276 };
277
278 template<typename T>
279 class VectorBufferBase {
280     WTF_MAKE_NONCOPYABLE(VectorBufferBase);
281 public:
282     void allocateBuffer(size_t newCapacity)
283     {
284         ASSERT(newCapacity);
285         if (newCapacity > std::numeric_limits<unsigned>::max() / sizeof(T))
286             CRASH();
287         size_t sizeToAllocate = newCapacity * sizeof(T);
288         m_capacity = sizeToAllocate / sizeof(T);
289         m_buffer = static_cast<T*>(fastMalloc(sizeToAllocate));
290     }
291
292     bool tryAllocateBuffer(size_t newCapacity)
293     {
294         ASSERT(newCapacity);
295         if (newCapacity > std::numeric_limits<unsigned>::max() / sizeof(T))
296             return false;
297
298         size_t sizeToAllocate = newCapacity * sizeof(T);
299         T* newBuffer;
300         if (tryFastMalloc(sizeToAllocate).getValue(newBuffer)) {
301             m_capacity = sizeToAllocate / sizeof(T);
302             m_buffer = newBuffer;
303             return true;
304         }
305         return false;
306     }
307
308     bool shouldReallocateBuffer(size_t newCapacity) const
309     {
310         return VectorTraits<T>::canMoveWithMemcpy && m_capacity && newCapacity;
311     }
312
313     void reallocateBuffer(size_t newCapacity)
314     {
315         ASSERT(shouldReallocateBuffer(newCapacity));
316         if (newCapacity > std::numeric_limits<size_t>::max() / sizeof(T))
317             CRASH();
318         size_t sizeToAllocate = newCapacity * sizeof(T);
319         m_capacity = sizeToAllocate / sizeof(T);
320         m_buffer = static_cast<T*>(fastRealloc(m_buffer, sizeToAllocate));
321     }
322
323     void deallocateBuffer(T* bufferToDeallocate)
324     {
325         if (!bufferToDeallocate)
326             return;
327         
328         if (m_buffer == bufferToDeallocate) {
329             m_buffer = 0;
330             m_capacity = 0;
331         }
332
333         fastFree(bufferToDeallocate);
334     }
335
336     T* buffer() { return m_buffer; }
337     const T* buffer() const { return m_buffer; }
338     static ptrdiff_t bufferMemoryOffset() { return OBJECT_OFFSETOF(VectorBufferBase, m_buffer); }
339     size_t capacity() const { return m_capacity; }
340
341     MallocPtr<T> releaseBuffer()
342     {
343         T* buffer = m_buffer;
344         m_buffer = 0;
345         m_capacity = 0;
346         return adoptMallocPtr(buffer);
347     }
348
349 protected:
350     VectorBufferBase()
351         : m_buffer(0)
352         , m_capacity(0)
353         , m_size(0)
354     {
355     }
356
357     VectorBufferBase(T* buffer, size_t capacity, size_t size)
358         : m_buffer(buffer)
359         , m_capacity(capacity)
360         , m_size(size)
361     {
362     }
363
364     ~VectorBufferBase()
365     {
366         // FIXME: It would be nice to find a way to ASSERT that m_buffer hasn't leaked here.
367     }
368
369     T* m_buffer;
370     unsigned m_capacity;
371     unsigned m_size; // Only used by the Vector subclass, but placed here to avoid padding the struct.
372 };
373
374 template<typename T, size_t inlineCapacity>
375 class VectorBuffer;
376
377 template<typename T>
378 class VectorBuffer<T, 0> : private VectorBufferBase<T> {
379 private:
380     typedef VectorBufferBase<T> Base;
381 public:
382     VectorBuffer()
383     {
384     }
385
386     VectorBuffer(size_t capacity, size_t size = 0)
387     {
388         m_size = size;
389         // Calling malloc(0) might take a lock and may actually do an
390         // allocation on some systems.
391         if (capacity)
392             allocateBuffer(capacity);
393     }
394
395     ~VectorBuffer()
396     {
397         deallocateBuffer(buffer());
398     }
399     
400     void swap(VectorBuffer<T, 0>& other, size_t, size_t)
401     {
402         std::swap(m_buffer, other.m_buffer);
403         std::swap(m_capacity, other.m_capacity);
404     }
405     
406     void restoreInlineBufferIfNeeded() { }
407
408 #if ASAN_ENABLED
409     void* endOfBuffer()
410     {
411         return buffer() + capacity();
412     }
413 #endif
414
415     using Base::allocateBuffer;
416     using Base::tryAllocateBuffer;
417     using Base::shouldReallocateBuffer;
418     using Base::reallocateBuffer;
419     using Base::deallocateBuffer;
420
421     using Base::buffer;
422     using Base::capacity;
423     using Base::bufferMemoryOffset;
424
425     using Base::releaseBuffer;
426
427 protected:
428     using Base::m_size;
429
430 private:
431     using Base::m_buffer;
432     using Base::m_capacity;
433 };
434
435 template<typename T, size_t inlineCapacity>
436 class VectorBuffer : private VectorBufferBase<T> {
437     WTF_MAKE_NONCOPYABLE(VectorBuffer);
438 private:
439     typedef VectorBufferBase<T> Base;
440 public:
441     VectorBuffer()
442         : Base(inlineBuffer(), inlineCapacity, 0)
443     {
444     }
445
446     VectorBuffer(size_t capacity, size_t size = 0)
447         : Base(inlineBuffer(), inlineCapacity, size)
448     {
449         if (capacity > inlineCapacity)
450             Base::allocateBuffer(capacity);
451     }
452
453     ~VectorBuffer()
454     {
455         deallocateBuffer(buffer());
456     }
457
458     void allocateBuffer(size_t newCapacity)
459     {
460         // FIXME: This should ASSERT(!m_buffer) to catch misuse/leaks.
461         if (newCapacity > inlineCapacity)
462             Base::allocateBuffer(newCapacity);
463         else {
464             m_buffer = inlineBuffer();
465             m_capacity = inlineCapacity;
466         }
467     }
468
469     bool tryAllocateBuffer(size_t newCapacity)
470     {
471         if (newCapacity > inlineCapacity)
472             return Base::tryAllocateBuffer(newCapacity);
473         m_buffer = inlineBuffer();
474         m_capacity = inlineCapacity;
475         return true;
476     }
477
478     void deallocateBuffer(T* bufferToDeallocate)
479     {
480         if (bufferToDeallocate == inlineBuffer())
481             return;
482         Base::deallocateBuffer(bufferToDeallocate);
483     }
484
485     bool shouldReallocateBuffer(size_t newCapacity) const
486     {
487         // We cannot reallocate the inline buffer.
488         return Base::shouldReallocateBuffer(newCapacity) && std::min(static_cast<size_t>(m_capacity), newCapacity) > inlineCapacity;
489     }
490
491     void reallocateBuffer(size_t newCapacity)
492     {
493         ASSERT(shouldReallocateBuffer(newCapacity));
494         Base::reallocateBuffer(newCapacity);
495     }
496
497     void swap(VectorBuffer& other, size_t mySize, size_t otherSize)
498     {
499         if (buffer() == inlineBuffer() && other.buffer() == other.inlineBuffer()) {
500             swapInlineBuffer(other, mySize, otherSize);
501             std::swap(m_capacity, other.m_capacity);
502         } else if (buffer() == inlineBuffer()) {
503             m_buffer = other.m_buffer;
504             other.m_buffer = other.inlineBuffer();
505             swapInlineBuffer(other, mySize, 0);
506             std::swap(m_capacity, other.m_capacity);
507         } else if (other.buffer() == other.inlineBuffer()) {
508             other.m_buffer = m_buffer;
509             m_buffer = inlineBuffer();
510             swapInlineBuffer(other, 0, otherSize);
511             std::swap(m_capacity, other.m_capacity);
512         } else {
513             std::swap(m_buffer, other.m_buffer);
514             std::swap(m_capacity, other.m_capacity);
515         }
516     }
517
518     void restoreInlineBufferIfNeeded()
519     {
520         if (m_buffer)
521             return;
522         m_buffer = inlineBuffer();
523         m_capacity = inlineCapacity;
524     }
525
526 #if ASAN_ENABLED
527     void* endOfBuffer()
528     {
529         ASSERT(buffer());
530
531         IGNORE_GCC_WARNINGS_BEGIN("invalid-offsetof")
532         static_assert((offsetof(VectorBuffer, m_inlineBuffer) + sizeof(m_inlineBuffer)) % 8 == 0, "Inline buffer end needs to be on 8 byte boundary for ASan annotations to work.");
533         IGNORE_GCC_WARNINGS_END
534
535         if (buffer() == inlineBuffer())
536             return reinterpret_cast<char*>(m_inlineBuffer) + sizeof(m_inlineBuffer);
537
538         return buffer() + capacity();
539     }
540 #endif
541
542     using Base::buffer;
543     using Base::capacity;
544     using Base::bufferMemoryOffset;
545
546     MallocPtr<T> releaseBuffer()
547     {
548         if (buffer() == inlineBuffer())
549             return nullptr;
550         return Base::releaseBuffer();
551     }
552
553 protected:
554     using Base::m_size;
555
556 private:
557     using Base::m_buffer;
558     using Base::m_capacity;
559     
560     void swapInlineBuffer(VectorBuffer& other, size_t mySize, size_t otherSize)
561     {
562         // FIXME: We could make swap part of VectorTypeOperations
563         // https://bugs.webkit.org/show_bug.cgi?id=128863
564         swapInlineBuffers(inlineBuffer(), other.inlineBuffer(), mySize, otherSize);
565     }
566     
567     static void swapInlineBuffers(T* left, T* right, size_t leftSize, size_t rightSize)
568     {
569         if (left == right)
570             return;
571         
572         ASSERT(leftSize <= inlineCapacity);
573         ASSERT(rightSize <= inlineCapacity);
574         
575         size_t swapBound = std::min(leftSize, rightSize);
576         for (unsigned i = 0; i < swapBound; ++i)
577             std::swap(left[i], right[i]);
578         VectorTypeOperations<T>::move(left + swapBound, left + leftSize, right + swapBound);
579         VectorTypeOperations<T>::move(right + swapBound, right + rightSize, left + swapBound);
580     }
581
582     T* inlineBuffer() { return reinterpret_cast_ptr<T*>(m_inlineBuffer); }
583     const T* inlineBuffer() const { return reinterpret_cast_ptr<const T*>(m_inlineBuffer); }
584
585 #if ASAN_ENABLED
586     // ASan needs the buffer to begin and end on 8-byte boundaries for annotations to work.
587     // FIXME: Add a redzone before the buffer to catch off by one accesses. We don't need a guard after, because the buffer is the last member variable.
588     static const size_t asanInlineBufferAlignment = std::alignment_of<T>::value >= 8 ? std::alignment_of<T>::value : 8;
589     static const size_t asanAdjustedInlineCapacity = ((sizeof(T) * inlineCapacity + 7) & ~7) / sizeof(T);
590     typename std::aligned_storage<sizeof(T), asanInlineBufferAlignment>::type m_inlineBuffer[asanAdjustedInlineCapacity];
591 #else
592     typename std::aligned_storage<sizeof(T), std::alignment_of<T>::value>::type m_inlineBuffer[inlineCapacity];
593 #endif
594 };
595
596 struct UnsafeVectorOverflow {
597     static NO_RETURN_DUE_TO_ASSERT void overflowed()
598     {
599         ASSERT_NOT_REACHED();
600     }
601 };
602
603 // Template default values are in Forward.h.
604 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
605 class Vector : private VectorBuffer<T, inlineCapacity> {
606     WTF_MAKE_FAST_ALLOCATED;
607 private:
608     typedef VectorBuffer<T, inlineCapacity> Base;
609     typedef VectorTypeOperations<T> TypeOperations;
610
611 public:
612     typedef T ValueType;
613
614     typedef T* iterator;
615     typedef const T* const_iterator;
616     typedef std::reverse_iterator<iterator> reverse_iterator;
617     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
618
619     Vector()
620     {
621     }
622
623     // Unlike in std::vector, this constructor does not initialize POD types.
624     explicit Vector(size_t size)
625         : Base(size, size)
626     {
627         asanSetInitialBufferSizeTo(size);
628
629         if (begin())
630             TypeOperations::initializeIfNonPOD(begin(), end());
631     }
632
633     Vector(size_t size, const T& val)
634         : Base(size, size)
635     {
636         asanSetInitialBufferSizeTo(size);
637
638         if (begin())
639             TypeOperations::uninitializedFill(begin(), end(), val);
640     }
641
642     Vector(std::initializer_list<T> initializerList)
643     {
644         reserveInitialCapacity(initializerList.size());
645
646         asanSetInitialBufferSizeTo(initializerList.size());
647
648         for (const auto& element : initializerList)
649             uncheckedAppend(element);
650     }
651
652     template<typename... Items>
653     static Vector from(Items&&... items)
654     {
655         Vector result;
656         auto size = sizeof...(items);
657
658         result.reserveInitialCapacity(size);
659         result.asanSetInitialBufferSizeTo(size);
660         result.m_size = size;
661
662         result.uncheckedInitialize<0>(std::forward<Items>(items)...);
663         return result;
664     }
665
666     ~Vector()
667     {
668         if (m_size)
669             TypeOperations::destruct(begin(), end());
670
671         asanSetBufferSizeToFullCapacity(0);
672     }
673
674     Vector(const Vector&);
675     template<size_t otherCapacity, typename otherOverflowBehaviour, size_t otherMinimumCapacity>
676     explicit Vector(const Vector<T, otherCapacity, otherOverflowBehaviour, otherMinimumCapacity>&);
677
678     Vector& operator=(const Vector&);
679     template<size_t otherCapacity, typename otherOverflowBehaviour, size_t otherMinimumCapacity>
680     Vector& operator=(const Vector<T, otherCapacity, otherOverflowBehaviour, otherMinimumCapacity>&);
681
682     Vector(Vector&&);
683     Vector& operator=(Vector&&);
684
685     size_t size() const { return m_size; }
686     static ptrdiff_t sizeMemoryOffset() { return OBJECT_OFFSETOF(Vector, m_size); }
687     size_t capacity() const { return Base::capacity(); }
688     bool isEmpty() const { return !size(); }
689
690     T& at(size_t i)
691     {
692         if (UNLIKELY(i >= size()))
693             OverflowHandler::overflowed();
694         return Base::buffer()[i];
695     }
696     const T& at(size_t i) const 
697     {
698         if (UNLIKELY(i >= size()))
699             OverflowHandler::overflowed();
700         return Base::buffer()[i];
701     }
702     T& at(Checked<size_t> i)
703     {
704         RELEASE_ASSERT(i < size());
705         return Base::buffer()[i];
706     }
707     const T& at(Checked<size_t> i) const
708     {
709         RELEASE_ASSERT(i < size());
710         return Base::buffer()[i];
711     }
712
713     T& operator[](size_t i) { return at(i); }
714     const T& operator[](size_t i) const { return at(i); }
715     T& operator[](Checked<size_t> i) { return at(i); }
716     const T& operator[](Checked<size_t> i) const { return at(i); }
717
718     T* data() { return Base::buffer(); }
719     const T* data() const { return Base::buffer(); }
720     static ptrdiff_t dataMemoryOffset() { return Base::bufferMemoryOffset(); }
721
722     iterator begin() { return data(); }
723     iterator end() { return begin() + m_size; }
724     const_iterator begin() const { return data(); }
725     const_iterator end() const { return begin() + m_size; }
726
727     reverse_iterator rbegin() { return reverse_iterator(end()); }
728     reverse_iterator rend() { return reverse_iterator(begin()); }
729     const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
730     const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
731
732     T& first() { return at(0); }
733     const T& first() const { return at(0); }
734     T& last() { return at(size() - 1); }
735     const T& last() const { return at(size() - 1); }
736     
737     T takeLast()
738     {
739         T result = WTFMove(last());
740         removeLast();
741         return result;
742     }
743     
744     template<typename U> bool contains(const U&) const;
745     template<typename U> size_t find(const U&) const;
746     template<typename MatchFunction> size_t findMatching(const MatchFunction&) const;
747     template<typename U> size_t reverseFind(const U&) const;
748     
749     template<typename U> bool appendIfNotContains(const U&);
750
751     void shrink(size_t size);
752     void grow(size_t size);
753     void resize(size_t size);
754     void resizeToFit(size_t size);
755     void reserveCapacity(size_t newCapacity);
756     bool tryReserveCapacity(size_t newCapacity);
757     void reserveInitialCapacity(size_t initialCapacity);
758     void shrinkCapacity(size_t newCapacity);
759     void shrinkToFit() { shrinkCapacity(size()); }
760
761     void clear() { shrinkCapacity(0); }
762
763     template<typename U = T> Vector<U> isolatedCopy() const;
764
765     ALWAYS_INLINE void append(ValueType&& value) { append<ValueType>(std::forward<ValueType>(value)); }
766     template<typename U> void append(U&&);
767     template<typename... Args> void constructAndAppend(Args&&...);
768     template<typename... Args> bool tryConstructAndAppend(Args&&...);
769
770     void uncheckedAppend(ValueType&& value) { uncheckedAppend<ValueType>(std::forward<ValueType>(value)); }
771     template<typename U> void uncheckedAppend(U&&);
772
773     template<typename U> void append(const U*, size_t);
774     template<typename U, size_t otherCapacity> void appendVector(const Vector<U, otherCapacity>&);
775     template<typename U> bool tryAppend(const U*, size_t);
776
777     template<typename U> void insert(size_t position, const U*, size_t);
778     template<typename U> void insert(size_t position, U&&);
779     template<typename U, size_t c> void insertVector(size_t position, const Vector<U, c>&);
780
781     void remove(size_t position);
782     void remove(size_t position, size_t length);
783     template<typename U> bool removeFirst(const U&);
784     template<typename MatchFunction> bool removeFirstMatching(const MatchFunction&, size_t startIndex = 0);
785     template<typename U> unsigned removeAll(const U&);
786     template<typename MatchFunction> unsigned removeAllMatching(const MatchFunction&, size_t startIndex = 0);
787
788     void removeLast() 
789     {
790         if (UNLIKELY(isEmpty()))
791             OverflowHandler::overflowed();
792         shrink(size() - 1); 
793     }
794
795     void fill(const T&, size_t);
796     void fill(const T& val) { fill(val, size()); }
797
798     template<typename Iterator> void appendRange(Iterator start, Iterator end);
799
800     MallocPtr<T> releaseBuffer();
801
802     void swap(Vector<T, inlineCapacity, OverflowHandler, minCapacity>& other)
803     {
804 #if ASAN_ENABLED
805         if (this == std::addressof(other)) // ASan will crash if we try to restrict access to the same buffer twice.
806             return;
807 #endif
808
809         // Make it possible to copy inline buffers.
810         asanSetBufferSizeToFullCapacity();
811         other.asanSetBufferSizeToFullCapacity();
812
813         Base::swap(other, m_size, other.m_size);
814         std::swap(m_size, other.m_size);
815
816         asanSetInitialBufferSizeTo(m_size);
817         other.asanSetInitialBufferSizeTo(other.m_size);
818     }
819
820     void reverse();
821
822     void checkConsistency();
823
824     template<typename MapFunction, typename R = typename std::result_of<MapFunction(const T&)>::type> Vector<R> map(MapFunction) const;
825
826 private:
827     void expandCapacity(size_t newMinCapacity);
828     T* expandCapacity(size_t newMinCapacity, T*);
829     bool tryExpandCapacity(size_t newMinCapacity);
830     const T* tryExpandCapacity(size_t newMinCapacity, const T*);
831     template<typename U> U* expandCapacity(size_t newMinCapacity, U*); 
832     template<typename U> void appendSlowCase(U&&);
833     template<typename... Args> void constructAndAppendSlowCase(Args&&...);
834     template<typename... Args> bool tryConstructAndAppendSlowCase(Args&&...);
835
836     template<size_t position, typename U, typename... Items>
837     void uncheckedInitialize(U&& item, Items&&... items)
838     {
839         uncheckedInitialize<position>(std::forward<U>(item));
840         uncheckedInitialize<position + 1>(std::forward<Items>(items)...);
841     }
842     template<size_t position, typename U>
843     void uncheckedInitialize(U&& value)
844     {
845         ASSERT(position < size());
846         ASSERT(position < capacity());
847         new (NotNull, begin() + position) T(std::forward<U>(value));
848     }
849
850     void asanSetInitialBufferSizeTo(size_t);
851     void asanSetBufferSizeToFullCapacity(size_t);
852     void asanSetBufferSizeToFullCapacity() { asanSetBufferSizeToFullCapacity(size()); }
853
854     void asanBufferSizeWillChangeTo(size_t);
855
856     using Base::m_size;
857     using Base::buffer;
858     using Base::capacity;
859     using Base::swap;
860     using Base::allocateBuffer;
861     using Base::deallocateBuffer;
862     using Base::tryAllocateBuffer;
863     using Base::shouldReallocateBuffer;
864     using Base::reallocateBuffer;
865     using Base::restoreInlineBufferIfNeeded;
866     using Base::releaseBuffer;
867 #if ASAN_ENABLED
868     using Base::endOfBuffer;
869 #endif
870 };
871
872 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
873 Vector<T, inlineCapacity, OverflowHandler, minCapacity>::Vector(const Vector& other)
874     : Base(other.capacity(), other.size())
875 {
876     asanSetInitialBufferSizeTo(other.size());
877
878     if (begin())
879         TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
880 }
881
882 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
883 template<size_t otherCapacity, typename otherOverflowBehaviour, size_t otherMinimumCapacity>
884 Vector<T, inlineCapacity, OverflowHandler, minCapacity>::Vector(const Vector<T, otherCapacity, otherOverflowBehaviour, otherMinimumCapacity>& other)
885     : Base(other.capacity(), other.size())
886 {
887     asanSetInitialBufferSizeTo(other.size());
888
889     if (begin())
890         TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
891 }
892
893 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
894 Vector<T, inlineCapacity, OverflowHandler, minCapacity>& Vector<T, inlineCapacity, OverflowHandler, minCapacity>::operator=(const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& other)
895 {
896     if (&other == this)
897         return *this;
898     
899     if (size() > other.size())
900         shrink(other.size());
901     else if (other.size() > capacity()) {
902         clear();
903         reserveCapacity(other.size());
904         ASSERT(begin());
905     }
906
907     asanBufferSizeWillChangeTo(other.size());
908
909     std::copy(other.begin(), other.begin() + size(), begin());
910     TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
911     m_size = other.size();
912
913     return *this;
914 }
915
916 inline bool typelessPointersAreEqual(const void* a, const void* b) { return a == b; }
917
918 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
919 template<size_t otherCapacity, typename otherOverflowBehaviour, size_t otherMinimumCapacity>
920 Vector<T, inlineCapacity, OverflowHandler, minCapacity>& Vector<T, inlineCapacity, OverflowHandler, minCapacity>::operator=(const Vector<T, otherCapacity, otherOverflowBehaviour, otherMinimumCapacity>& other)
921 {
922     // If the inline capacities match, we should call the more specific
923     // template.  If the inline capacities don't match, the two objects
924     // shouldn't be allocated the same address.
925     ASSERT(!typelessPointersAreEqual(&other, this));
926
927     if (size() > other.size())
928         shrink(other.size());
929     else if (other.size() > capacity()) {
930         clear();
931         reserveCapacity(other.size());
932         ASSERT(begin());
933     }
934     
935     asanBufferSizeWillChangeTo(other.size());
936
937     std::copy(other.begin(), other.begin() + size(), begin());
938     TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
939     m_size = other.size();
940
941     return *this;
942 }
943
944 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
945 inline Vector<T, inlineCapacity, OverflowHandler, minCapacity>::Vector(Vector<T, inlineCapacity, OverflowHandler, minCapacity>&& other)
946 {
947     swap(other);
948 }
949
950 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
951 inline Vector<T, inlineCapacity, OverflowHandler, minCapacity>& Vector<T, inlineCapacity, OverflowHandler, minCapacity>::operator=(Vector<T, inlineCapacity, OverflowHandler, minCapacity>&& other)
952 {
953     swap(other);
954     return *this;
955 }
956
957 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
958 template<typename U>
959 bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::contains(const U& value) const
960 {
961     return find(value) != notFound;
962 }
963
964 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
965 template<typename MatchFunction>
966 size_t Vector<T, inlineCapacity, OverflowHandler, minCapacity>::findMatching(const MatchFunction& matches) const
967 {
968     for (size_t i = 0; i < size(); ++i) {
969         if (matches(at(i)))
970             return i;
971     }
972     return notFound;
973 }
974
975 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
976 template<typename U>
977 size_t Vector<T, inlineCapacity, OverflowHandler, minCapacity>::find(const U& value) const
978 {
979     return findMatching([&](auto& item) {
980         return item == value;
981     });
982 }
983
984 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
985 template<typename U>
986 size_t Vector<T, inlineCapacity, OverflowHandler, minCapacity>::reverseFind(const U& value) const
987 {
988     for (size_t i = 1; i <= size(); ++i) {
989         const size_t index = size() - i;
990         if (at(index) == value)
991             return index;
992     }
993     return notFound;
994 }
995
996 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
997 template<typename U>
998 bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::appendIfNotContains(const U& value)
999 {
1000     if (contains(value))
1001         return false;
1002     append(value);
1003     return true;
1004 }
1005
1006 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1007 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::fill(const T& val, size_t newSize)
1008 {
1009     if (size() > newSize)
1010         shrink(newSize);
1011     else if (newSize > capacity()) {
1012         clear();
1013         reserveCapacity(newSize);
1014         ASSERT(begin());
1015     }
1016
1017     asanBufferSizeWillChangeTo(newSize);
1018
1019     std::fill(begin(), end(), val);
1020     TypeOperations::uninitializedFill(end(), begin() + newSize, val);
1021     m_size = newSize;
1022 }
1023
1024 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1025 template<typename Iterator>
1026 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::appendRange(Iterator start, Iterator end)
1027 {
1028     for (Iterator it = start; it != end; ++it)
1029         append(*it);
1030 }
1031
1032 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1033 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::expandCapacity(size_t newMinCapacity)
1034 {
1035     reserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(minCapacity), capacity() + capacity() / 4 + 1)));
1036 }
1037
1038 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1039 NEVER_INLINE T* Vector<T, inlineCapacity, OverflowHandler, minCapacity>::expandCapacity(size_t newMinCapacity, T* ptr)
1040 {
1041     if (ptr < begin() || ptr >= end()) {
1042         expandCapacity(newMinCapacity);
1043         return ptr;
1044     }
1045     size_t index = ptr - begin();
1046     expandCapacity(newMinCapacity);
1047     return begin() + index;
1048 }
1049
1050 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1051 bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryExpandCapacity(size_t newMinCapacity)
1052 {
1053     return tryReserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(minCapacity), capacity() + capacity() / 4 + 1)));
1054 }
1055
1056 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1057 const T* Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryExpandCapacity(size_t newMinCapacity, const T* ptr)
1058 {
1059     if (ptr < begin() || ptr >= end()) {
1060         if (!tryExpandCapacity(newMinCapacity))
1061             return 0;
1062         return ptr;
1063     }
1064     size_t index = ptr - begin();
1065     if (!tryExpandCapacity(newMinCapacity))
1066         return 0;
1067     return begin() + index;
1068 }
1069
1070 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1071 template<typename U>
1072 inline U* Vector<T, inlineCapacity, OverflowHandler, minCapacity>::expandCapacity(size_t newMinCapacity, U* ptr)
1073 {
1074     expandCapacity(newMinCapacity);
1075     return ptr;
1076 }
1077
1078 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1079 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::resize(size_t size)
1080 {
1081     if (size <= m_size) {
1082         TypeOperations::destruct(begin() + size, end());
1083         asanBufferSizeWillChangeTo(size);
1084     } else {
1085         if (size > capacity())
1086             expandCapacity(size);
1087         asanBufferSizeWillChangeTo(size);
1088         if (begin())
1089             TypeOperations::initializeIfNonPOD(end(), begin() + size);
1090     }
1091     
1092     m_size = size;
1093 }
1094
1095 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1096 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::resizeToFit(size_t size)
1097 {
1098     reserveCapacity(size);
1099     resize(size);
1100 }
1101
1102 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1103 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::shrink(size_t size)
1104 {
1105     ASSERT(size <= m_size);
1106     TypeOperations::destruct(begin() + size, end());
1107     asanBufferSizeWillChangeTo(size);
1108     m_size = size;
1109 }
1110
1111 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1112 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::grow(size_t size)
1113 {
1114     ASSERT(size >= m_size);
1115     if (size > capacity())
1116         expandCapacity(size);
1117     asanBufferSizeWillChangeTo(size);
1118     if (begin())
1119         TypeOperations::initializeIfNonPOD(end(), begin() + size);
1120     m_size = size;
1121 }
1122
1123 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1124 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::asanSetInitialBufferSizeTo(size_t size)
1125 {
1126 #if ASAN_ENABLED
1127     if (!buffer())
1128         return;
1129
1130     // This function resticts buffer access to only elements in [begin(), end()) range, making ASan detect an error
1131     // when accessing elements in [end(), endOfBuffer()) range.
1132     // A newly allocated buffer can be accessed without restrictions, so "old_mid" argument equals "end" argument.
1133     __sanitizer_annotate_contiguous_container(buffer(), endOfBuffer(), endOfBuffer(), buffer() + size);
1134 #else
1135     UNUSED_PARAM(size);
1136 #endif
1137 }
1138
1139 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1140 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::asanSetBufferSizeToFullCapacity(size_t size)
1141 {
1142 #if ASAN_ENABLED
1143     if (!buffer())
1144         return;
1145
1146     // ASan requires that the annotation is returned to its initial state before deallocation.
1147     __sanitizer_annotate_contiguous_container(buffer(), endOfBuffer(), buffer() + size, endOfBuffer());
1148 #else
1149     UNUSED_PARAM(size);
1150 #endif
1151 }
1152
1153 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1154 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::asanBufferSizeWillChangeTo(size_t newSize)
1155 {
1156 #if ASAN_ENABLED
1157     if (!buffer())
1158         return;
1159
1160     // Change allowed range.
1161     __sanitizer_annotate_contiguous_container(buffer(), endOfBuffer(), buffer() + size(), buffer() + newSize);
1162 #else
1163     UNUSED_PARAM(newSize);
1164 #endif
1165 }
1166
1167 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1168 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::reserveCapacity(size_t newCapacity)
1169 {
1170     if (newCapacity <= capacity())
1171         return;
1172     T* oldBuffer = begin();
1173     T* oldEnd = end();
1174
1175     asanSetBufferSizeToFullCapacity();
1176
1177     Base::allocateBuffer(newCapacity);
1178     ASSERT(begin());
1179
1180     asanSetInitialBufferSizeTo(size());
1181
1182     TypeOperations::move(oldBuffer, oldEnd, begin());
1183     Base::deallocateBuffer(oldBuffer);
1184 }
1185
1186 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1187 bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryReserveCapacity(size_t newCapacity)
1188 {
1189     if (newCapacity <= capacity())
1190         return true;
1191     T* oldBuffer = begin();
1192     T* oldEnd = end();
1193
1194     asanSetBufferSizeToFullCapacity();
1195
1196     if (!Base::tryAllocateBuffer(newCapacity)) {
1197         asanSetInitialBufferSizeTo(size());
1198         return false;
1199     }
1200     ASSERT(begin());
1201
1202     asanSetInitialBufferSizeTo(size());
1203
1204     TypeOperations::move(oldBuffer, oldEnd, begin());
1205     Base::deallocateBuffer(oldBuffer);
1206     return true;
1207 }
1208
1209 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1210 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::reserveInitialCapacity(size_t initialCapacity)
1211 {
1212     ASSERT(!m_size);
1213     ASSERT(capacity() == inlineCapacity);
1214     if (initialCapacity > inlineCapacity)
1215         Base::allocateBuffer(initialCapacity);
1216 }
1217
1218 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1219 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::shrinkCapacity(size_t newCapacity)
1220 {
1221     if (newCapacity >= capacity())
1222         return;
1223
1224     if (newCapacity < size()) 
1225         shrink(newCapacity);
1226
1227     asanSetBufferSizeToFullCapacity();
1228
1229     T* oldBuffer = begin();
1230     if (newCapacity > 0) {
1231         if (Base::shouldReallocateBuffer(newCapacity)) {
1232             Base::reallocateBuffer(newCapacity);
1233             asanSetInitialBufferSizeTo(size());
1234             return;
1235         }
1236
1237         T* oldEnd = end();
1238         Base::allocateBuffer(newCapacity);
1239         if (begin() != oldBuffer)
1240             TypeOperations::move(oldBuffer, oldEnd, begin());
1241     }
1242
1243     Base::deallocateBuffer(oldBuffer);
1244     Base::restoreInlineBufferIfNeeded();
1245
1246     asanSetInitialBufferSizeTo(size());
1247 }
1248
1249 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1250 template<typename U>
1251 ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::append(const U* data, size_t dataSize)
1252 {
1253     size_t newSize = m_size + dataSize;
1254     if (newSize > capacity()) {
1255         data = expandCapacity(newSize, data);
1256         ASSERT(begin());
1257     }
1258     if (newSize < m_size)
1259         CRASH();
1260     asanBufferSizeWillChangeTo(newSize);
1261     T* dest = end();
1262     VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, std::addressof(data[dataSize]), dest);
1263     m_size = newSize;
1264 }
1265
1266 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1267 template<typename U>
1268 ALWAYS_INLINE bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryAppend(const U* data, size_t dataSize)
1269 {
1270     size_t newSize = m_size + dataSize;
1271     if (newSize > capacity()) {
1272         data = tryExpandCapacity(newSize, data);
1273         if (!data)
1274             return false;
1275         ASSERT(begin());
1276     }
1277     if (newSize < m_size)
1278         return false;
1279     asanBufferSizeWillChangeTo(newSize);
1280     T* dest = end();
1281     VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, std::addressof(data[dataSize]), dest);
1282     m_size = newSize;
1283     return true;
1284 }
1285
1286 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1287 template<typename U>
1288 ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::append(U&& value)
1289 {
1290     if (size() != capacity()) {
1291         asanBufferSizeWillChangeTo(m_size + 1);
1292         new (NotNull, end()) T(std::forward<U>(value));
1293         ++m_size;
1294         return;
1295     }
1296
1297     appendSlowCase(std::forward<U>(value));
1298 }
1299
1300 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1301 template<typename... Args>
1302 ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::constructAndAppend(Args&&... args)
1303 {
1304     if (size() != capacity()) {
1305         asanBufferSizeWillChangeTo(m_size + 1);
1306         new (NotNull, end()) T(std::forward<Args>(args)...);
1307         ++m_size;
1308         return;
1309     }
1310
1311     constructAndAppendSlowCase(std::forward<Args>(args)...);
1312 }
1313
1314 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1315 template<typename... Args>
1316 ALWAYS_INLINE bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryConstructAndAppend(Args&&... args)
1317 {
1318     if (size() != capacity()) {
1319         asanBufferSizeWillChangeTo(m_size + 1);
1320         new (NotNull, end()) T(std::forward<Args>(args)...);
1321         ++m_size;
1322         return true;
1323     }
1324     
1325     return tryConstructAndAppendSlowCase(std::forward<Args>(args)...);
1326 }
1327
1328 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1329 template<typename U>
1330 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::appendSlowCase(U&& value)
1331 {
1332     ASSERT(size() == capacity());
1333
1334     auto ptr = const_cast<typename std::remove_const<typename std::remove_reference<U>::type>::type*>(std::addressof(value));
1335     ptr = expandCapacity(size() + 1, ptr);
1336     ASSERT(begin());
1337
1338     asanBufferSizeWillChangeTo(m_size + 1);
1339     new (NotNull, end()) T(std::forward<U>(*ptr));
1340     ++m_size;
1341 }
1342
1343 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1344 template<typename... Args>
1345 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::constructAndAppendSlowCase(Args&&... args)
1346 {
1347     ASSERT(size() == capacity());
1348
1349     expandCapacity(size() + 1);
1350     ASSERT(begin());
1351
1352     asanBufferSizeWillChangeTo(m_size + 1);
1353     new (NotNull, end()) T(std::forward<Args>(args)...);
1354     ++m_size;
1355 }
1356
1357 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1358 template<typename... Args>
1359 bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::tryConstructAndAppendSlowCase(Args&&... args)
1360 {
1361     ASSERT(size() == capacity());
1362     
1363     if (UNLIKELY(!tryExpandCapacity(size() + 1)))
1364         return false;
1365     ASSERT(begin());
1366     
1367     asanBufferSizeWillChangeTo(m_size + 1);
1368     new (NotNull, end()) T(std::forward<Args>(args)...);
1369     ++m_size;
1370     return true;
1371 }
1372
1373 // This version of append saves a branch in the case where you know that the
1374 // vector's capacity is large enough for the append to succeed.
1375
1376 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1377 template<typename U>
1378 ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::uncheckedAppend(U&& value)
1379 {
1380     ASSERT(size() < capacity());
1381
1382     asanBufferSizeWillChangeTo(m_size + 1);
1383
1384     new (NotNull, end()) T(std::forward<U>(value));
1385     ++m_size;
1386 }
1387
1388 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1389 template<typename U, size_t otherCapacity>
1390 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::appendVector(const Vector<U, otherCapacity>& val)
1391 {
1392     append(val.begin(), val.size());
1393 }
1394
1395 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1396 template<typename U>
1397 void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::insert(size_t position, const U* data, size_t dataSize)
1398 {
1399     ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
1400     size_t newSize = m_size + dataSize;
1401     if (newSize > capacity()) {
1402         data = expandCapacity(newSize, data);
1403         ASSERT(begin());
1404     }
1405     if (newSize < m_size)
1406         CRASH();
1407     asanBufferSizeWillChangeTo(newSize);
1408     T* spot = begin() + position;
1409     TypeOperations::moveOverlapping(spot, end(), spot + dataSize);
1410     VectorCopier<std::is_trivial<T>::value, U>::uninitializedCopy(data, std::addressof(data[dataSize]), spot);
1411     m_size = newSize;
1412 }
1413  
1414 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1415 template<typename U>
1416 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::insert(size_t position, U&& value)
1417 {
1418     ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
1419
1420     auto ptr = const_cast<typename std::remove_const<typename std::remove_reference<U>::type>::type*>(std::addressof(value));
1421     if (size() == capacity()) {
1422         ptr = expandCapacity(size() + 1, ptr);
1423         ASSERT(begin());
1424     }
1425
1426     asanBufferSizeWillChangeTo(m_size + 1);
1427
1428     T* spot = begin() + position;
1429     TypeOperations::moveOverlapping(spot, end(), spot + 1);
1430     new (NotNull, spot) T(std::forward<U>(*ptr));
1431     ++m_size;
1432 }
1433
1434 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1435 template<typename U, size_t c>
1436 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::insertVector(size_t position, const Vector<U, c>& val)
1437 {
1438     insert(position, val.begin(), val.size());
1439 }
1440
1441 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1442 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::remove(size_t position)
1443 {
1444     ASSERT_WITH_SECURITY_IMPLICATION(position < size());
1445     T* spot = begin() + position;
1446     spot->~T();
1447     TypeOperations::moveOverlapping(spot + 1, end(), spot);
1448     asanBufferSizeWillChangeTo(m_size - 1);
1449     --m_size;
1450 }
1451
1452 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1453 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::remove(size_t position, size_t length)
1454 {
1455     ASSERT_WITH_SECURITY_IMPLICATION(position <= size());
1456     ASSERT_WITH_SECURITY_IMPLICATION(position + length <= size());
1457     T* beginSpot = begin() + position;
1458     T* endSpot = beginSpot + length;
1459     TypeOperations::destruct(beginSpot, endSpot); 
1460     TypeOperations::moveOverlapping(endSpot, end(), beginSpot);
1461     asanBufferSizeWillChangeTo(m_size - length);
1462     m_size -= length;
1463 }
1464
1465 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1466 template<typename U>
1467 inline bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::removeFirst(const U& value)
1468 {
1469     return removeFirstMatching([&value] (const T& current) {
1470         return current == value;
1471     });
1472 }
1473
1474 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1475 template<typename MatchFunction>
1476 inline bool Vector<T, inlineCapacity, OverflowHandler, minCapacity>::removeFirstMatching(const MatchFunction& matches, size_t startIndex)
1477 {
1478     for (size_t i = startIndex; i < size(); ++i) {
1479         if (matches(at(i))) {
1480             remove(i);
1481             return true;
1482         }
1483     }
1484     return false;
1485 }
1486
1487 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1488 template<typename U>
1489 inline unsigned Vector<T, inlineCapacity, OverflowHandler, minCapacity>::removeAll(const U& value)
1490 {
1491     return removeAllMatching([&value] (const T& current) {
1492         return current == value;
1493     });
1494 }
1495
1496 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1497 template<typename MatchFunction>
1498 inline unsigned Vector<T, inlineCapacity, OverflowHandler, minCapacity>::removeAllMatching(const MatchFunction& matches, size_t startIndex)
1499 {
1500     iterator holeBegin = end();
1501     iterator holeEnd = end();
1502     unsigned matchCount = 0;
1503     for (auto it = begin() + startIndex, itEnd = end(); it < itEnd; ++it) {
1504         if (matches(*it)) {
1505             if (holeBegin == end())
1506                 holeBegin = it;
1507             else if (holeEnd != it) {
1508                 TypeOperations::moveOverlapping(holeEnd, it, holeBegin);
1509                 holeBegin += it - holeEnd;
1510             }
1511             holeEnd = it + 1;
1512             it->~T();
1513             ++matchCount;
1514         }
1515     }
1516     if (holeEnd != end())
1517         TypeOperations::moveOverlapping(holeEnd, end(), holeBegin);
1518     asanBufferSizeWillChangeTo(m_size - matchCount);
1519     m_size -= matchCount;
1520     return matchCount;
1521 }
1522
1523 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1524 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::reverse()
1525 {
1526     for (size_t i = 0; i < m_size / 2; ++i)
1527         std::swap(at(i), at(m_size - 1 - i));
1528 }
1529
1530 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1531 template<typename MapFunction, typename R>
1532 inline Vector<R> Vector<T, inlineCapacity, OverflowHandler, minCapacity>::map(MapFunction mapFunction) const
1533 {
1534     Vector<R> result;
1535     result.reserveInitialCapacity(size());
1536     for (size_t i = 0; i < size(); ++i)
1537         result.uncheckedAppend(mapFunction(at(i)));
1538     return result;
1539 }
1540
1541 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1542 inline MallocPtr<T> Vector<T, inlineCapacity, OverflowHandler, minCapacity>::releaseBuffer()
1543 {
1544     // FIXME: Find a way to preserve annotations on the returned buffer.
1545     // ASan requires that all annotations are removed before deallocation,
1546     // and MallocPtr doesn't implement that.
1547     asanSetBufferSizeToFullCapacity();
1548
1549     auto buffer = Base::releaseBuffer();
1550     if (inlineCapacity && !buffer && m_size) {
1551         // If the vector had some data, but no buffer to release,
1552         // that means it was using the inline buffer. In that case,
1553         // we create a brand new buffer so the caller always gets one.
1554         size_t bytes = m_size * sizeof(T);
1555         buffer = adoptMallocPtr(static_cast<T*>(fastMalloc(bytes)));
1556         memcpy(buffer.get(), data(), bytes);
1557     }
1558     m_size = 0;
1559     // FIXME: Should we call Base::restoreInlineBufferIfNeeded() here?
1560     return buffer;
1561 }
1562
1563 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1564 inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::checkConsistency()
1565 {
1566 #if !ASSERT_DISABLED
1567     for (size_t i = 0; i < size(); ++i)
1568         ValueCheck<T>::checkConsistency(at(i));
1569 #endif
1570 }
1571
1572 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1573 inline void swap(Vector<T, inlineCapacity, OverflowHandler, minCapacity>& a, Vector<T, inlineCapacity, OverflowHandler, minCapacity>& b)
1574 {
1575     a.swap(b);
1576 }
1577
1578 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1579 bool operator==(const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& a, const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& b)
1580 {
1581     if (a.size() != b.size())
1582         return false;
1583
1584     return VectorTypeOperations<T>::compare(a.data(), b.data(), a.size());
1585 }
1586
1587 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1588 inline bool operator!=(const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& a, const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& b)
1589 {
1590     return !(a == b);
1591 }
1592
1593 #if !ASSERT_DISABLED
1594 template<typename T> struct ValueCheck<Vector<T>> {
1595     typedef Vector<T> TraitType;
1596     static void checkConsistency(const Vector<T>& v)
1597     {
1598         v.checkConsistency();
1599     }
1600 };
1601 #endif
1602
1603 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1604 template<typename U>
1605 inline Vector<U> Vector<T, inlineCapacity, OverflowHandler, minCapacity>::isolatedCopy() const
1606 {
1607     Vector<U> copy;
1608     copy.reserveInitialCapacity(size());
1609     for (const auto& element : *this)
1610         copy.uncheckedAppend(element.isolatedCopy());
1611     return copy;
1612 }
1613     
1614 template<typename VectorType, typename Func>
1615 size_t removeRepeatedElements(VectorType& vector, const Func& func)
1616 {
1617     auto end = std::unique(vector.begin(), vector.end(), func);
1618     size_t newSize = end - vector.begin();
1619     vector.shrink(newSize);
1620     return newSize;
1621 }
1622
1623 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
1624 size_t removeRepeatedElements(Vector<T, inlineCapacity, OverflowHandler, minCapacity>& vector)
1625 {
1626     return removeRepeatedElements(vector, [] (T& a, T& b) { return a == b; });
1627 }
1628
1629 template<typename SourceType>
1630 struct CollectionInspector {
1631     using RealSourceType = typename std::remove_reference<SourceType>::type;
1632     using IteratorType = decltype(std::begin(std::declval<RealSourceType>()));
1633     using SourceItemType = typename std::iterator_traits<IteratorType>::value_type;
1634 };
1635
1636 template<typename MapFunction, typename SourceType, typename Enable = void>
1637 struct Mapper {
1638     using SourceItemType = typename CollectionInspector<SourceType>::SourceItemType;
1639     using DestinationItemType = typename std::result_of<MapFunction(SourceItemType&)>::type;
1640
1641     static Vector<DestinationItemType> map(SourceType source, const MapFunction& mapFunction)
1642     {
1643         Vector<DestinationItemType> result;
1644         // FIXME: Use std::size when available on all compilers.
1645         result.reserveInitialCapacity(source.size());
1646         for (auto& item : source)
1647             result.uncheckedAppend(mapFunction(item));
1648         return result;
1649     }
1650 };
1651
1652 template<typename MapFunction, typename SourceType>
1653 struct Mapper<MapFunction, SourceType, typename std::enable_if<std::is_rvalue_reference<SourceType&&>::value>::type> {
1654     using SourceItemType = typename CollectionInspector<SourceType>::SourceItemType;
1655     using DestinationItemType = typename std::result_of<MapFunction(SourceItemType&&)>::type;
1656
1657     static Vector<DestinationItemType> map(SourceType&& source, const MapFunction& mapFunction)
1658     {
1659         Vector<DestinationItemType> result;
1660         // FIXME: Use std::size when available on all compilers.
1661         result.reserveInitialCapacity(source.size());
1662         for (auto& item : source)
1663             result.uncheckedAppend(mapFunction(WTFMove(item)));
1664         return result;
1665     }
1666 };
1667
1668 template<typename MapFunction, typename SourceType>
1669 Vector<typename Mapper<MapFunction, SourceType>::DestinationItemType> map(SourceType&& source, MapFunction&& mapFunction)
1670 {
1671     return Mapper<MapFunction, SourceType>::map(std::forward<SourceType>(source), std::forward<MapFunction>(mapFunction));
1672 }
1673
1674 template<typename DestinationVector, typename Collection>
1675 inline auto copyToVectorSpecialization(const Collection& collection) -> DestinationVector
1676 {
1677     DestinationVector result;
1678     // FIXME: Use std::size when available on all compilers.
1679     result.reserveInitialCapacity(collection.size());
1680     for (auto& item : collection)
1681         result.uncheckedAppend(item);
1682     return result;
1683 }
1684
1685 template<typename DestinationItemType, typename Collection>
1686 inline auto copyToVectorOf(const Collection& collection) -> Vector<DestinationItemType>
1687 {
1688     return WTF::map(collection, [] (const auto& v) -> DestinationItemType { return v; });
1689 }
1690
1691 template<typename Collection>
1692 struct CopyToVectorResult {
1693     using Type = typename std::remove_cv<typename CollectionInspector<Collection>::SourceItemType>::type;
1694 };
1695
1696 template<typename Collection>
1697 inline auto copyToVector(const Collection& collection) -> Vector<typename CopyToVectorResult<Collection>::Type>
1698 {
1699     return copyToVectorOf<typename CopyToVectorResult<Collection>::Type>(collection);
1700 }
1701
1702 } // namespace WTF
1703
1704 using WTF::UnsafeVectorOverflow;
1705 using WTF::Vector;
1706 using WTF::copyToVector;
1707 using WTF::copyToVectorOf;
1708 using WTF::copyToVectorSpecialization;
1709 using WTF::removeRepeatedElements;