Use of WTF::move prevents clang's move diagnostics from warning about several classes...
[WebKit-https.git] / Source / WTF / wtf / StdLibExtras.h
1 /*
2  * Copyright (C) 2008 Apple Inc. All Rights Reserved.
3  * Copyright (C) 2013 Patrick Gansterer <paroga@paroga.com>
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
15  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
18  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
25  */
26
27 #ifndef WTF_StdLibExtras_h
28 #define WTF_StdLibExtras_h
29
30 #include <chrono>
31 #include <memory>
32 #include <wtf/Assertions.h>
33 #include <wtf/CheckedArithmetic.h>
34
35 // This was used to declare and define a static local variable (static T;) so that
36 //  it was leaked so that its destructors were not called at exit.
37 // Newly written code should use static NeverDestroyed<T> instead.
38 #ifndef DEPRECATED_DEFINE_STATIC_LOCAL
39 #define DEPRECATED_DEFINE_STATIC_LOCAL(type, name, arguments) \
40     static type& name = *new type arguments
41 #endif
42
43 // Use this macro to declare and define a debug-only global variable that may have a
44 // non-trivial constructor and destructor. When building with clang, this will suppress
45 // warnings about global constructors and exit-time destructors.
46 #define DEFINE_GLOBAL_FOR_LOGGING(type, name, arguments) \
47     _Pragma("clang diagnostic push") \
48     _Pragma("clang diagnostic ignored \"-Wglobal-constructors\"") \
49     _Pragma("clang diagnostic ignored \"-Wexit-time-destructors\"") \
50     static type name arguments; \
51     _Pragma("clang diagnostic pop")
52
53 #ifndef NDEBUG
54 #if COMPILER(CLANG)
55 #define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments) DEFINE_GLOBAL_FOR_LOGGING(type, name, arguments)
56 #else
57 #define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments) \
58     static type name arguments;
59 #endif // COMPILER(CLANG)
60 #else
61 #define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments)
62 #endif // NDEBUG
63
64 // OBJECT_OFFSETOF: Like the C++ offsetof macro, but you can use it with classes.
65 // The magic number 0x4000 is insignificant. We use it to avoid using NULL, since
66 // NULL can cause compiler problems, especially in cases of multiple inheritance.
67 #define OBJECT_OFFSETOF(class, field) (reinterpret_cast<ptrdiff_t>(&(reinterpret_cast<class*>(0x4000)->field)) - 0x4000)
68
69 // STRINGIZE: Can convert any value to quoted string, even expandable macros
70 #define STRINGIZE(exp) #exp
71 #define STRINGIZE_VALUE_OF(exp) STRINGIZE(exp)
72
73 /*
74  * The reinterpret_cast<Type1*>([pointer to Type2]) expressions - where
75  * sizeof(Type1) > sizeof(Type2) - cause the following warning on ARM with GCC:
76  * increases required alignment of target type.
77  *
78  * An implicit or an extra static_cast<void*> bypasses the warning.
79  * For more info see the following bugzilla entries:
80  * - https://bugs.webkit.org/show_bug.cgi?id=38045
81  * - http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43976
82  */
83 #if (CPU(ARM) || CPU(MIPS)) && COMPILER(GCC_OR_CLANG)
84 template<typename Type>
85 inline bool isPointerTypeAlignmentOkay(Type* ptr)
86 {
87     return !(reinterpret_cast<intptr_t>(ptr) % __alignof__(Type));
88 }
89
90 template<typename TypePtr>
91 inline TypePtr reinterpret_cast_ptr(void* ptr)
92 {
93     ASSERT(isPointerTypeAlignmentOkay(reinterpret_cast<TypePtr>(ptr)));
94     return reinterpret_cast<TypePtr>(ptr);
95 }
96
97 template<typename TypePtr>
98 inline TypePtr reinterpret_cast_ptr(const void* ptr)
99 {
100     ASSERT(isPointerTypeAlignmentOkay(reinterpret_cast<TypePtr>(ptr)));
101     return reinterpret_cast<TypePtr>(ptr);
102 }
103 #else
104 template<typename Type>
105 inline bool isPointerTypeAlignmentOkay(Type*)
106 {
107     return true;
108 }
109 #define reinterpret_cast_ptr reinterpret_cast
110 #endif
111
112 namespace WTF {
113
114 enum CheckMoveParameterTag { CheckMoveParameter };
115
116 // FIXME: Using this function prevents Clang's move diagnostics (-Wpessimizing-move, -Wredundant-move, -Wself-move) from
117 // finding mistakes, since these diagnostics only evaluate calls to std::move().
118 template<typename T>
119 ALWAYS_INLINE typename std::remove_reference<T>::type&& move(T&& value)
120 {
121     static_assert(std::is_lvalue_reference<T>::value, "T is not an lvalue reference; move() is unnecessary.");
122
123     using NonRefQualifiedType = typename std::remove_reference<T>::type;
124     static_assert(!std::is_const<NonRefQualifiedType>::value, "T is const qualified.");
125     return std::move(value);
126 }
127
128 static const size_t KB = 1024;
129 static const size_t MB = 1024 * 1024;
130
131 inline bool isPointerAligned(void* p)
132 {
133     return !((intptr_t)(p) & (sizeof(char*) - 1));
134 }
135
136 inline bool is8ByteAligned(void* p)
137 {
138     return !((uintptr_t)(p) & (sizeof(double) - 1));
139 }
140
141 /*
142  * C++'s idea of a reinterpret_cast lacks sufficient cojones.
143  */
144 template<typename ToType, typename FromType>
145 inline ToType bitwise_cast(FromType from)
146 {
147     static_assert(sizeof(FromType) == sizeof(ToType), "bitwise_cast size of FromType and ToType must be equal!");
148     union {
149         FromType from;
150         ToType to;
151     } u;
152     u.from = from;
153     return u.to;
154 }
155
156 template<typename ToType, typename FromType>
157 inline ToType safeCast(FromType value)
158 {
159     ASSERT(isInBounds<ToType>(value));
160     return static_cast<ToType>(value);
161 }
162
163 // Returns a count of the number of bits set in 'bits'.
164 inline size_t bitCount(unsigned bits)
165 {
166     bits = bits - ((bits >> 1) & 0x55555555);
167     bits = (bits & 0x33333333) + ((bits >> 2) & 0x33333333);
168     return (((bits + (bits >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
169 }
170
171 inline size_t bitCount(uint64_t bits)
172 {
173     return bitCount(static_cast<unsigned>(bits)) + bitCount(static_cast<unsigned>(bits >> 32));
174 }
175
176 // Macro that returns a compile time constant with the length of an array, but gives an error if passed a non-array.
177 template<typename T, size_t Size> char (&ArrayLengthHelperFunction(T (&)[Size]))[Size];
178 // GCC needs some help to deduce a 0 length array.
179 #if COMPILER(GCC_OR_CLANG)
180 template<typename T> char (&ArrayLengthHelperFunction(T (&)[0]))[0];
181 #endif
182 #define WTF_ARRAY_LENGTH(array) sizeof(::WTF::ArrayLengthHelperFunction(array))
183
184 // Efficient implementation that takes advantage of powers of two.
185 inline size_t roundUpToMultipleOf(size_t divisor, size_t x)
186 {
187     ASSERT(divisor && !(divisor & (divisor - 1)));
188     size_t remainderMask = divisor - 1;
189     return (x + remainderMask) & ~remainderMask;
190 }
191
192 template<size_t divisor> inline size_t roundUpToMultipleOf(size_t x)
193 {
194     static_assert(divisor && !(divisor & (divisor - 1)), "divisor must be a power of two!");
195     return roundUpToMultipleOf(divisor, x);
196 }
197
198 enum BinarySearchMode {
199     KeyMustBePresentInArray,
200     KeyMightNotBePresentInArray,
201     ReturnAdjacentElementIfKeyIsNotPresent
202 };
203
204 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey, BinarySearchMode mode>
205 inline ArrayElementType* binarySearchImpl(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
206 {
207     size_t offset = 0;
208     while (size > 1) {
209         size_t pos = (size - 1) >> 1;
210         KeyType val = extractKey(&array[offset + pos]);
211         
212         if (val == key)
213             return &array[offset + pos];
214         // The item we are looking for is smaller than the item being check; reduce the value of 'size',
215         // chopping off the right hand half of the array.
216         if (key < val)
217             size = pos;
218         // Discard all values in the left hand half of the array, up to and including the item at pos.
219         else {
220             size -= (pos + 1);
221             offset += (pos + 1);
222         }
223
224         ASSERT(mode != KeyMustBePresentInArray || size);
225     }
226     
227     if (mode == KeyMightNotBePresentInArray && !size)
228         return 0;
229     
230     ArrayElementType* result = &array[offset];
231
232     if (mode == KeyMightNotBePresentInArray && key != extractKey(result))
233         return 0;
234
235     if (mode == KeyMustBePresentInArray) {
236         ASSERT(size == 1);
237         ASSERT(key == extractKey(result));
238     }
239
240     return result;
241 }
242
243 // If the element is not found, crash if asserts are enabled, and behave like approximateBinarySearch in release builds.
244 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
245 inline ArrayElementType* binarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
246 {
247     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(array, size, key, extractKey);
248 }
249
250 // Return zero if the element is not found.
251 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
252 inline ArrayElementType* tryBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
253 {
254     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(array, size, key, extractKey);
255 }
256
257 // Return the element that is either to the left, or the right, of where the element would have been found.
258 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
259 inline ArrayElementType* approximateBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
260 {
261     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(array, size, key, extractKey);
262 }
263
264 // Variants of the above that use const.
265 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
266 inline ArrayElementType* binarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
267 {
268     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
269 }
270 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
271 inline ArrayElementType* tryBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
272 {
273     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
274 }
275 template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
276 inline ArrayElementType* approximateBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
277 {
278     return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(const_cast<ArrayType&>(array), size, key, extractKey);
279 }
280
281 template<typename VectorType, typename ElementType>
282 inline void insertIntoBoundedVector(VectorType& vector, size_t size, const ElementType& element, size_t index)
283 {
284     for (size_t i = size; i-- > index + 1;)
285         vector[i] = vector[i - 1];
286     vector[index] = element;
287 }
288
289 // This is here instead of CompilationThread.h to prevent that header from being included
290 // everywhere. The fact that this method, and that header, exist outside of JSC is a bug.
291 // https://bugs.webkit.org/show_bug.cgi?id=131815
292 WTF_EXPORT_PRIVATE bool isCompilationThread();
293
294 } // namespace WTF
295
296 // This version of placement new omits a 0 check.
297 enum NotNullTag { NotNull };
298 inline void* operator new(size_t, NotNullTag, void* location)
299 {
300     ASSERT(location);
301     return location;
302 }
303
304 // This adds various C++14 features for versions of the STL that may not yet have them.
305 namespace std {
306 // MSVC 2013 supports std::make_unique already.
307 #if !defined(_MSC_VER) || _MSC_VER < 1800
308 template<class T> struct _Unique_if {
309     typedef unique_ptr<T> _Single_object;
310 };
311
312 template<class T> struct _Unique_if<T[]> {
313     typedef unique_ptr<T[]> _Unknown_bound;
314 };
315
316 template<class T, size_t N> struct _Unique_if<T[N]> {
317     typedef void _Known_bound;
318 };
319
320 template<class T, class... Args> inline typename _Unique_if<T>::_Single_object
321 make_unique(Args&&... args)
322 {
323     return unique_ptr<T>(new T(std::forward<Args>(args)...));
324 }
325
326 template<class T> inline typename _Unique_if<T>::_Unknown_bound
327 make_unique(size_t n)
328 {
329     typedef typename remove_extent<T>::type U;
330     return unique_ptr<T>(new U[n]());
331 }
332
333 template<class T, class... Args> typename _Unique_if<T>::_Known_bound
334 make_unique(Args&&...) = delete;
335 #endif
336
337 // MSVC 2015 supports these functions.
338 #if !COMPILER(MSVC) || _MSC_VER < 1900
339 // Compile-time integer sequences
340 // http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3658.html
341 // (Note that we only implement index_sequence, and not the more generic integer_sequence).
342 template<size_t... indexes> struct index_sequence {
343     static size_t size() { return sizeof...(indexes); }
344 };
345
346 template<size_t currentIndex, size_t...indexes> struct make_index_sequence_helper;
347
348 template<size_t...indexes> struct make_index_sequence_helper<0, indexes...> {
349     typedef std::index_sequence<indexes...> type;
350 };
351
352 template<size_t currentIndex, size_t...indexes> struct make_index_sequence_helper {
353     typedef typename make_index_sequence_helper<currentIndex - 1, currentIndex - 1, indexes...>::type type;
354 };
355
356 template<size_t length> struct make_index_sequence : public make_index_sequence_helper<length>::type { };
357
358 // std::exchange
359 template<class T, class U = T>
360 T exchange(T& t, U&& newValue)
361 {
362     T oldValue = std::move(t);
363     t = std::forward<U>(newValue);
364
365     return oldValue;
366 }
367 #endif
368
369 #if COMPILER_SUPPORTS(CXX_USER_LITERALS)
370 // These literals are available in C++14, so once we require C++14 compilers we can get rid of them here.
371 // (User-literals need to have a leading underscore so we add it here - the "real" literals don't have underscores).
372 namespace literals {
373 namespace chrono_literals {
374     CONSTEXPR inline chrono::seconds operator"" _s(unsigned long long s)
375     {
376         return chrono::seconds(static_cast<chrono::seconds::rep>(s));
377     }
378
379     CONSTEXPR chrono::milliseconds operator"" _ms(unsigned long long ms)
380     {
381         return chrono::milliseconds(static_cast<chrono::milliseconds::rep>(ms));
382     }
383 }
384 }
385 #endif
386
387 template<WTF::CheckMoveParameterTag, typename T>
388 ALWAYS_INLINE CONSTEXPR typename remove_reference<T>::type&& move(T&& value)
389 {
390     static_assert(is_lvalue_reference<T>::value, "T is not an lvalue reference; move() is unnecessary.");
391
392     using NonRefQualifiedType = typename remove_reference<T>::type;
393     static_assert(!is_const<NonRefQualifiedType>::value, "T is const qualified.");
394
395     return move(forward<T>(value));
396 }
397
398 } // namespace std
399
400 #define WTF_MOVE(value) std::move<WTF::CheckMoveParameter>(value)
401
402 using WTF::KB;
403 using WTF::MB;
404 using WTF::isCompilationThread;
405 using WTF::insertIntoBoundedVector;
406 using WTF::isPointerAligned;
407 using WTF::is8ByteAligned;
408 using WTF::binarySearch;
409 using WTF::tryBinarySearch;
410 using WTF::approximateBinarySearch;
411 using WTF::bitwise_cast;
412 using WTF::safeCast;
413
414 #if COMPILER_SUPPORTS(CXX_USER_LITERALS)
415 // We normally don't want to bring in entire std namespaces, but literals are an exception.
416 using namespace std::literals::chrono_literals;
417 #endif
418
419 #endif // WTF_StdLibExtras_h