1/*
2 * Copyright (C) 2008-2017 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#pragma once
28
29#include <cstring>
30#include <memory>
31#include <type_traits>
32#include <wtf/Assertions.h>
33#include <wtf/CheckedArithmetic.h>
34#include <wtf/Compiler.h>
35
36// Use this macro to declare and define a debug-only global variable that may have a
37// non-trivial constructor and destructor. When building with clang, this will suppress
38// warnings about global constructors and exit-time destructors.
39#define DEFINE_GLOBAL_FOR_LOGGING(type, name, arguments) \
40 _Pragma("clang diagnostic push") \
41 _Pragma("clang diagnostic ignored \"-Wglobal-constructors\"") \
42 _Pragma("clang diagnostic ignored \"-Wexit-time-destructors\"") \
43 static type name arguments; \
44 _Pragma("clang diagnostic pop")
45
46#ifndef NDEBUG
47#if COMPILER(CLANG)
48#define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments) DEFINE_GLOBAL_FOR_LOGGING(type, name, arguments)
49#else
50#define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments) \
51 static type name arguments;
52#endif // COMPILER(CLANG)
53#else
54#define DEFINE_DEBUG_ONLY_GLOBAL(type, name, arguments)
55#endif // NDEBUG
56
57// OBJECT_OFFSETOF: Like the C++ offsetof macro, but you can use it with classes.
58// The magic number 0x4000 is insignificant. We use it to avoid using NULL, since
59// NULL can cause compiler problems, especially in cases of multiple inheritance.
60#define OBJECT_OFFSETOF(class, field) (reinterpret_cast<ptrdiff_t>(&(reinterpret_cast<class*>(0x4000)->field)) - 0x4000)
61
62#define CAST_OFFSET(from, to) (reinterpret_cast<uintptr_t>(static_cast<to>((reinterpret_cast<from>(0x4000)))) - 0x4000)
63
64// STRINGIZE: Can convert any value to quoted string, even expandable macros
65#define STRINGIZE(exp) #exp
66#define STRINGIZE_VALUE_OF(exp) STRINGIZE(exp)
67
68// WTF_CONCAT: concatenate two symbols into one, even expandable macros
69#define WTF_CONCAT_INTERNAL_DONT_USE(a, b) a ## b
70#define WTF_CONCAT(a, b) WTF_CONCAT_INTERNAL_DONT_USE(a, b)
71
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_COMPATIBLE)
84template<typename Type>
85inline bool isPointerTypeAlignmentOkay(Type* ptr)
86{
87 return !(reinterpret_cast<intptr_t>(ptr) % __alignof__(Type));
88}
89
90template<typename TypePtr>
91inline TypePtr reinterpret_cast_ptr(void* ptr)
92{
93 ASSERT(isPointerTypeAlignmentOkay(reinterpret_cast<TypePtr>(ptr)));
94 return reinterpret_cast<TypePtr>(ptr);
95}
96
97template<typename TypePtr>
98inline TypePtr reinterpret_cast_ptr(const void* ptr)
99{
100 ASSERT(isPointerTypeAlignmentOkay(reinterpret_cast<TypePtr>(ptr)));
101 return reinterpret_cast<TypePtr>(ptr);
102}
103#else
104template<typename Type>
105inline bool isPointerTypeAlignmentOkay(Type*)
106{
107 return true;
108}
109#define reinterpret_cast_ptr reinterpret_cast
110#endif
111
112namespace WTF {
113
114enum CheckMoveParameterTag { CheckMoveParameter };
115
116static const size_t KB = 1024;
117static const size_t MB = 1024 * 1024;
118static const size_t GB = 1024 * 1024 * 1024;
119
120inline bool isPointerAligned(void* p)
121{
122 return !((intptr_t)(p) & (sizeof(char*) - 1));
123}
124
125inline bool is8ByteAligned(void* p)
126{
127 return !((uintptr_t)(p) & (sizeof(double) - 1));
128}
129
130/*
131 * C++'s idea of a reinterpret_cast lacks sufficient cojones.
132 */
133template<typename ToType, typename FromType>
134inline ToType bitwise_cast(FromType from)
135{
136 static_assert(sizeof(FromType) == sizeof(ToType), "bitwise_cast size of FromType and ToType must be equal!");
137#if COMPILER_SUPPORTS(BUILTIN_IS_TRIVIALLY_COPYABLE)
138 // Not all recent STL implementations support the std::is_trivially_copyable type trait. Work around this by only checking on toolchains which have the equivalent compiler intrinsic.
139 static_assert(__is_trivially_copyable(ToType), "bitwise_cast of non-trivially-copyable type!");
140 static_assert(__is_trivially_copyable(FromType), "bitwise_cast of non-trivially-copyable type!");
141#endif
142 typename std::remove_const<ToType>::type to { };
143 std::memcpy(static_cast<void*>(&to), static_cast<void*>(&from), sizeof(to));
144 return to;
145}
146
147template<typename ToType, typename FromType>
148inline ToType safeCast(FromType value)
149{
150 RELEASE_ASSERT(isInBounds<ToType>(value));
151 return static_cast<ToType>(value);
152}
153
154// Returns a count of the number of bits set in 'bits'.
155inline size_t bitCount(unsigned bits)
156{
157 bits = bits - ((bits >> 1) & 0x55555555);
158 bits = (bits & 0x33333333) + ((bits >> 2) & 0x33333333);
159 return (((bits + (bits >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
160}
161
162inline size_t bitCount(uint64_t bits)
163{
164 return bitCount(static_cast<unsigned>(bits)) + bitCount(static_cast<unsigned>(bits >> 32));
165}
166
167// Macro that returns a compile time constant with the length of an array, but gives an error if passed a non-array.
168template<typename T, size_t Size> char (&ArrayLengthHelperFunction(T (&)[Size]))[Size];
169// GCC needs some help to deduce a 0 length array.
170#if COMPILER(GCC_COMPATIBLE)
171template<typename T> char (&ArrayLengthHelperFunction(T (&)[0]))[0];
172#endif
173#define WTF_ARRAY_LENGTH(array) sizeof(::WTF::ArrayLengthHelperFunction(array))
174
175ALWAYS_INLINE constexpr size_t roundUpToMultipleOfImpl(size_t divisor, size_t x)
176{
177 size_t remainderMask = divisor - 1;
178 return (x + remainderMask) & ~remainderMask;
179}
180
181// Efficient implementation that takes advantage of powers of two.
182inline size_t roundUpToMultipleOf(size_t divisor, size_t x)
183{
184 ASSERT(divisor && !(divisor & (divisor - 1)));
185 return roundUpToMultipleOfImpl(divisor, x);
186}
187
188template<size_t divisor> constexpr size_t roundUpToMultipleOf(size_t x)
189{
190 static_assert(divisor && !(divisor & (divisor - 1)), "divisor must be a power of two!");
191 return roundUpToMultipleOfImpl(divisor, x);
192}
193
194template<size_t divisor, typename T> inline T* roundUpToMultipleOf(T* x)
195{
196 static_assert(sizeof(T*) == sizeof(size_t), "");
197 return reinterpret_cast<T*>(roundUpToMultipleOf<divisor>(reinterpret_cast<size_t>(x)));
198}
199
200enum BinarySearchMode {
201 KeyMustBePresentInArray,
202 KeyMightNotBePresentInArray,
203 ReturnAdjacentElementIfKeyIsNotPresent
204};
205
206template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey, BinarySearchMode mode>
207inline ArrayElementType* binarySearchImpl(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
208{
209 size_t offset = 0;
210 while (size > 1) {
211 size_t pos = (size - 1) >> 1;
212 KeyType val = extractKey(&array[offset + pos]);
213
214 if (val == key)
215 return &array[offset + pos];
216 // The item we are looking for is smaller than the item being check; reduce the value of 'size',
217 // chopping off the right hand half of the array.
218 if (key < val)
219 size = pos;
220 // Discard all values in the left hand half of the array, up to and including the item at pos.
221 else {
222 size -= (pos + 1);
223 offset += (pos + 1);
224 }
225
226 ASSERT(mode != KeyMustBePresentInArray || size);
227 }
228
229 if (mode == KeyMightNotBePresentInArray && !size)
230 return 0;
231
232 ArrayElementType* result = &array[offset];
233
234 if (mode == KeyMightNotBePresentInArray && key != extractKey(result))
235 return 0;
236
237 if (mode == KeyMustBePresentInArray) {
238 ASSERT(size == 1);
239 ASSERT(key == extractKey(result));
240 }
241
242 return result;
243}
244
245// If the element is not found, crash if asserts are enabled, and behave like approximateBinarySearch in release builds.
246template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
247inline ArrayElementType* binarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
248{
249 return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(array, size, key, extractKey);
250}
251
252// Return zero if the element is not found.
253template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
254inline ArrayElementType* tryBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
255{
256 return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(array, size, key, extractKey);
257}
258
259// Return the element that is either to the left, or the right, of where the element would have been found.
260template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
261inline ArrayElementType* approximateBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
262{
263 return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(array, size, key, extractKey);
264}
265
266// Variants of the above that use const.
267template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
268inline ArrayElementType* binarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
269{
270 return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
271}
272template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
273inline ArrayElementType* tryBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
274{
275 return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
276}
277template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
278inline ArrayElementType* approximateBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
279{
280 return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(const_cast<ArrayType&>(array), size, key, extractKey);
281}
282
283template<typename VectorType, typename ElementType>
284inline void insertIntoBoundedVector(VectorType& vector, size_t size, const ElementType& element, size_t index)
285{
286 for (size_t i = size; i-- > index + 1;)
287 vector[i] = vector[i - 1];
288 vector[index] = element;
289}
290
291// This is here instead of CompilationThread.h to prevent that header from being included
292// everywhere. The fact that this method, and that header, exist outside of JSC is a bug.
293// https://bugs.webkit.org/show_bug.cgi?id=131815
294WTF_EXPORT_PRIVATE bool isCompilationThread();
295
296template<typename Func>
297bool isStatelessLambda()
298{
299 return std::is_empty<Func>::value;
300}
301
302template<typename ResultType, typename Func, typename... ArgumentTypes>
303ResultType callStatelessLambda(ArgumentTypes&&... arguments)
304{
305 uint64_t data[(sizeof(Func) + sizeof(uint64_t) - 1) / sizeof(uint64_t)];
306 memset(data, 0, sizeof(data));
307 return (*bitwise_cast<Func*>(data))(std::forward<ArgumentTypes>(arguments)...);
308}
309
310template<typename T, typename U>
311bool checkAndSet(T& left, U right)
312{
313 if (left == right)
314 return false;
315 left = right;
316 return true;
317}
318
319template<typename T>
320bool findBitInWord(T word, size_t& index, size_t endIndex, bool value)
321{
322 static_assert(std::is_unsigned<T>::value, "Type used in findBitInWord must be unsigned");
323
324 word >>= index;
325
326 while (index < endIndex) {
327 if ((word & 1) == static_cast<T>(value))
328 return true;
329 index++;
330 word >>= 1;
331 }
332
333 index = endIndex;
334 return false;
335}
336
337// Visitor adapted from http://stackoverflow.com/questions/25338795/is-there-a-name-for-this-tuple-creation-idiom
338
339template <class A, class... B>
340struct Visitor : Visitor<A>, Visitor<B...> {
341 Visitor(A a, B... b)
342 : Visitor<A>(a)
343 , Visitor<B...>(b...)
344 {
345 }
346
347 using Visitor<A>::operator ();
348 using Visitor<B...>::operator ();
349};
350
351template <class A>
352struct Visitor<A> : A {
353 Visitor(A a)
354 : A(a)
355 {
356 }
357
358 using A::operator();
359};
360
361template <class... F>
362Visitor<F...> makeVisitor(F... f)
363{
364 return Visitor<F...>(f...);
365}
366
367namespace Detail
368{
369 template <typename, template <typename...> class>
370 struct IsTemplate_ : std::false_type
371 {
372 };
373
374 template <typename... Ts, template <typename...> class C>
375 struct IsTemplate_<C<Ts...>, C> : std::true_type
376 {
377 };
378}
379
380template <typename T, template <typename...> class Template>
381struct IsTemplate : public std::integral_constant<bool, Detail::IsTemplate_<T, Template>::value> {};
382
383namespace Detail
384{
385 template <template <typename...> class Base, typename Derived>
386 struct IsBaseOfTemplateImpl
387 {
388 template <typename... Args>
389 static std::true_type test(Base<Args...>*);
390 static std::false_type test(void*);
391
392 static constexpr const bool value = decltype(test(std::declval<typename std::remove_cv<Derived>::type*>()))::value;
393 };
394}
395
396template <template <typename...> class Base, typename Derived>
397struct IsBaseOfTemplate : public std::integral_constant<bool, Detail::IsBaseOfTemplateImpl<Base, Derived>::value> {};
398
399template <class T>
400struct RemoveCVAndReference {
401 typedef typename std::remove_cv<typename std::remove_reference<T>::type>::type type;
402};
403
404template<typename IteratorTypeLeft, typename IteratorTypeRight, typename IteratorTypeDst>
405IteratorTypeDst mergeDeduplicatedSorted(IteratorTypeLeft leftBegin, IteratorTypeLeft leftEnd, IteratorTypeRight rightBegin, IteratorTypeRight rightEnd, IteratorTypeDst dstBegin)
406{
407 IteratorTypeLeft leftIter = leftBegin;
408 IteratorTypeRight rightIter = rightBegin;
409 IteratorTypeDst dstIter = dstBegin;
410
411 if (leftIter < leftEnd && rightIter < rightEnd) {
412 for (;;) {
413 auto left = *leftIter;
414 auto right = *rightIter;
415 if (left < right) {
416 *dstIter++ = left;
417 leftIter++;
418 if (leftIter >= leftEnd)
419 break;
420 } else if (left == right) {
421 *dstIter++ = left;
422 leftIter++;
423 rightIter++;
424 if (leftIter >= leftEnd || rightIter >= rightEnd)
425 break;
426 } else {
427 *dstIter++ = right;
428 rightIter++;
429 if (rightIter >= rightEnd)
430 break;
431 }
432 }
433 }
434
435 while (leftIter < leftEnd)
436 *dstIter++ = *leftIter++;
437 while (rightIter < rightEnd)
438 *dstIter++ = *rightIter++;
439
440 return dstIter;
441}
442
443// libstdc++5 does not have constexpr std::tie. Since we cannot redefine std::tie with constexpr, we define WTF::tie instead.
444// This workaround can be removed after 2019-04 and all users of WTF::tie can be converted to std::tie
445// For more info see: https://bugs.webkit.org/show_bug.cgi?id=180692 and https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65978
446template <class ...Args>
447constexpr std::tuple<Args&...> tie(Args&... values)
448{
449 return std::tuple<Args&...>(values...);
450}
451
452} // namespace WTF
453
454// This version of placement new omits a 0 check.
455enum NotNullTag { NotNull };
456inline void* operator new(size_t, NotNullTag, void* location)
457{
458 ASSERT(location);
459 return location;
460}
461
462// This adds various C++14 features for versions of the STL that may not yet have them.
463namespace std {
464#if COMPILER(CLANG) && __cplusplus < 201400L
465template<class T> struct _Unique_if {
466 typedef unique_ptr<T> _Single_object;
467};
468
469template<class T> struct _Unique_if<T[]> {
470 typedef unique_ptr<T[]> _Unknown_bound;
471};
472
473template<class T, size_t N> struct _Unique_if<T[N]> {
474 typedef void _Known_bound;
475};
476
477template<class T, class... Args> inline typename _Unique_if<T>::_Single_object
478make_unique(Args&&... args)
479{
480 return unique_ptr<T>(new T(std::forward<Args>(args)...));
481}
482
483template<class T> inline typename _Unique_if<T>::_Unknown_bound
484make_unique(size_t n)
485{
486 typedef typename remove_extent<T>::type U;
487 return unique_ptr<T>(new U[n]());
488}
489
490template<class T, class... Args> typename _Unique_if<T>::_Known_bound
491make_unique(Args&&...) = delete;
492
493// std::exchange
494template<class T, class U = T>
495T exchange(T& t, U&& newValue)
496{
497 T oldValue = std::move(t);
498 t = std::forward<U>(newValue);
499
500 return oldValue;
501}
502#endif
503
504template<WTF::CheckMoveParameterTag, typename T>
505ALWAYS_INLINE constexpr typename remove_reference<T>::type&& move(T&& value)
506{
507 static_assert(is_lvalue_reference<T>::value, "T is not an lvalue reference; move() is unnecessary.");
508
509 using NonRefQualifiedType = typename remove_reference<T>::type;
510 static_assert(!is_const<NonRefQualifiedType>::value, "T is const qualified.");
511
512 return move(forward<T>(value));
513}
514
515#if __cplusplus < 201703L && (!defined(_MSC_FULL_VER) || _MSC_FULL_VER < 190023918) && !defined(__cpp_lib_logical_traits)
516template<class...> struct wtf_conjunction_impl;
517template<> struct wtf_conjunction_impl<> : true_type { };
518template<class B0> struct wtf_conjunction_impl<B0> : B0 { };
519template<class B0, class B1> struct wtf_conjunction_impl<B0, B1> : conditional<B0::value, B1, B0>::type { };
520template<class B0, class B1, class B2, class... Bn> struct wtf_conjunction_impl<B0, B1, B2, Bn...> : conditional<B0::value, wtf_conjunction_impl<B1, B2, Bn...>, B0>::type { };
521template<class... _Args> struct conjunction : wtf_conjunction_impl<_Args...> { };
522#endif
523
524// Provide in_place_t when not building with -std=c++17, or when building with libstdc++ 6
525// (which doesn't define the _GLIBCXX_RELEASE macro that's been introduced in libstdc++ 7).
526#if ((defined(__GLIBCXX__) && !defined(_GLIBCXX_RELEASE))) && (!defined(_MSVC_LANG) || _MSVC_LANG < 201703L)
527
528// These are inline variable for C++17 and later.
529#define __IN_PLACE_INLINE_VARIABLE static const
530
531struct in_place_t {
532 explicit in_place_t() = default;
533};
534__IN_PLACE_INLINE_VARIABLE constexpr in_place_t in_place { };
535
536template <class T> struct in_place_type_t {
537 explicit in_place_type_t() = default;
538};
539template <class T>
540__IN_PLACE_INLINE_VARIABLE constexpr in_place_type_t<T> in_place_type { };
541
542template <size_t I> struct in_place_index_t {
543 explicit in_place_index_t() = default;
544};
545template <size_t I>
546__IN_PLACE_INLINE_VARIABLE constexpr in_place_index_t<I> in_place_index { };
547#endif // __cplusplus < 201703L
548
549enum class ZeroStatus {
550 MayBeZero,
551 NonZero
552};
553
554constexpr size_t clz(uint32_t value, ZeroStatus mightBeZero = ZeroStatus::MayBeZero)
555{
556 if (mightBeZero == ZeroStatus::MayBeZero && value) {
557#if COMPILER(MSVC)
558 return __lzcnt(value);
559#else
560 return __builtin_clz(value);
561#endif
562 }
563 return 32;
564}
565
566} // namespace std
567
568#define WTFMove(value) std::move<WTF::CheckMoveParameter>(value)
569
570using WTF::KB;
571using WTF::MB;
572using WTF::GB;
573using WTF::approximateBinarySearch;
574using WTF::binarySearch;
575using WTF::bitwise_cast;
576using WTF::callStatelessLambda;
577using WTF::checkAndSet;
578using WTF::findBitInWord;
579using WTF::insertIntoBoundedVector;
580using WTF::isCompilationThread;
581using WTF::isPointerAligned;
582using WTF::isStatelessLambda;
583using WTF::is8ByteAligned;
584using WTF::mergeDeduplicatedSorted;
585using WTF::roundUpToMultipleOf;
586using WTF::safeCast;
587using WTF::tryBinarySearch;
588