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