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 roundUpToMultipleOfImpl0(size_t remainderMask, size_t x)
176{
177 return (x + remainderMask) & ~remainderMask;
178}
179
180ALWAYS_INLINE constexpr size_t roundUpToMultipleOfImpl(size_t divisor, size_t x)
181{
182 return roundUpToMultipleOfImpl0(divisor - 1, x);
183}
184
185// Efficient implementation that takes advantage of powers of two.
186inline size_t roundUpToMultipleOf(size_t divisor, size_t x)
187{
188 ASSERT(divisor && !(divisor & (divisor - 1)));
189 return roundUpToMultipleOfImpl(divisor, x);
190}
191
192template<size_t divisor> constexpr size_t roundUpToMultipleOf(size_t x)
193{
194 static_assert(divisor && !(divisor & (divisor - 1)), "divisor must be a power of two!");
195 return roundUpToMultipleOfImpl(divisor, x);
196}
197
198template<size_t divisor, typename T> inline T* roundUpToMultipleOf(T* x)
199{
200 static_assert(sizeof(T*) == sizeof(size_t), "");
201 return reinterpret_cast<T*>(roundUpToMultipleOf<divisor>(reinterpret_cast<size_t>(x)));
202}
203
204enum BinarySearchMode {
205 KeyMustBePresentInArray,
206 KeyMightNotBePresentInArray,
207 ReturnAdjacentElementIfKeyIsNotPresent
208};
209
210template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey, BinarySearchMode mode>
211inline ArrayElementType* binarySearchImpl(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
212{
213 size_t offset = 0;
214 while (size > 1) {
215 size_t pos = (size - 1) >> 1;
216 KeyType val = extractKey(&array[offset + pos]);
217
218 if (val == key)
219 return &array[offset + pos];
220 // The item we are looking for is smaller than the item being check; reduce the value of 'size',
221 // chopping off the right hand half of the array.
222 if (key < val)
223 size = pos;
224 // Discard all values in the left hand half of the array, up to and including the item at pos.
225 else {
226 size -= (pos + 1);
227 offset += (pos + 1);
228 }
229
230 ASSERT(mode != KeyMustBePresentInArray || size);
231 }
232
233 if (mode == KeyMightNotBePresentInArray && !size)
234 return 0;
235
236 ArrayElementType* result = &array[offset];
237
238 if (mode == KeyMightNotBePresentInArray && key != extractKey(result))
239 return 0;
240
241 if (mode == KeyMustBePresentInArray) {
242 ASSERT(size == 1);
243 ASSERT(key == extractKey(result));
244 }
245
246 return result;
247}
248
249// If the element is not found, crash if asserts are enabled, and behave like approximateBinarySearch in release builds.
250template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
251inline ArrayElementType* binarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
252{
253 return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(array, size, key, extractKey);
254}
255
256// Return zero if the element is not found.
257template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
258inline ArrayElementType* tryBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
259{
260 return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(array, size, key, extractKey);
261}
262
263// Return the element that is either to the left, or the right, of where the element would have been found.
264template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
265inline ArrayElementType* approximateBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
266{
267 return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(array, size, key, extractKey);
268}
269
270// Variants of the above that use const.
271template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
272inline ArrayElementType* binarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
273{
274 return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
275}
276template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
277inline ArrayElementType* tryBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
278{
279 return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
280}
281template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
282inline ArrayElementType* approximateBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
283{
284 return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(const_cast<ArrayType&>(array), size, key, extractKey);
285}
286
287template<typename VectorType, typename ElementType>
288inline void insertIntoBoundedVector(VectorType& vector, size_t size, const ElementType& element, size_t index)
289{
290 for (size_t i = size; i-- > index + 1;)
291 vector[i] = vector[i - 1];
292 vector[index] = element;
293}
294
295// This is here instead of CompilationThread.h to prevent that header from being included
296// everywhere. The fact that this method, and that header, exist outside of JSC is a bug.
297// https://bugs.webkit.org/show_bug.cgi?id=131815
298WTF_EXPORT_PRIVATE bool isCompilationThread();
299
300template<typename Func>
301bool isStatelessLambda()
302{
303 return std::is_empty<Func>::value;
304}
305
306template<typename ResultType, typename Func, typename... ArgumentTypes>
307ResultType callStatelessLambda(ArgumentTypes&&... arguments)
308{
309 uint64_t data[(sizeof(Func) + sizeof(uint64_t) - 1) / sizeof(uint64_t)];
310 memset(data, 0, sizeof(data));
311 return (*bitwise_cast<Func*>(data))(std::forward<ArgumentTypes>(arguments)...);
312}
313
314template<typename T, typename U>
315bool checkAndSet(T& left, U right)
316{
317 if (left == right)
318 return false;
319 left = right;
320 return true;
321}
322
323template<typename T>
324bool findBitInWord(T word, size_t& index, size_t endIndex, bool value)
325{
326 static_assert(std::is_unsigned<T>::value, "Type used in findBitInWord must be unsigned");
327
328 word >>= index;
329
330 while (index < endIndex) {
331 if ((word & 1) == static_cast<T>(value))
332 return true;
333 index++;
334 word >>= 1;
335 }
336
337 index = endIndex;
338 return false;
339}
340
341// Visitor adapted from http://stackoverflow.com/questions/25338795/is-there-a-name-for-this-tuple-creation-idiom
342
343template <class A, class... B>
344struct Visitor : Visitor<A>, Visitor<B...> {
345 Visitor(A a, B... b)
346 : Visitor<A>(a)
347 , Visitor<B...>(b...)
348 {
349 }
350
351 using Visitor<A>::operator ();
352 using Visitor<B...>::operator ();
353};
354
355template <class A>
356struct Visitor<A> : A {
357 Visitor(A a)
358 : A(a)
359 {
360 }
361
362 using A::operator();
363};
364
365template <class... F>
366Visitor<F...> makeVisitor(F... f)
367{
368 return Visitor<F...>(f...);
369}
370
371namespace Detail
372{
373 template <typename, template <typename...> class>
374 struct IsTemplate_ : std::false_type
375 {
376 };
377
378 template <typename... Ts, template <typename...> class C>
379 struct IsTemplate_<C<Ts...>, C> : std::true_type
380 {
381 };
382}
383
384template <typename T, template <typename...> class Template>
385struct IsTemplate : public std::integral_constant<bool, Detail::IsTemplate_<T, Template>::value> {};
386
387namespace Detail
388{
389 template <template <typename...> class Base, typename Derived>
390 struct IsBaseOfTemplateImpl
391 {
392 template <typename... Args>
393 static std::true_type test(Base<Args...>*);
394 static std::false_type test(void*);
395
396 static constexpr const bool value = decltype(test(std::declval<typename std::remove_cv<Derived>::type*>()))::value;
397 };
398}
399
400template <template <typename...> class Base, typename Derived>
401struct IsBaseOfTemplate : public std::integral_constant<bool, Detail::IsBaseOfTemplateImpl<Base, Derived>::value> {};
402
403template <class T>
404struct RemoveCVAndReference {
405 typedef typename std::remove_cv<typename std::remove_reference<T>::type>::type type;
406};
407
408template<typename IteratorTypeLeft, typename IteratorTypeRight, typename IteratorTypeDst>
409IteratorTypeDst mergeDeduplicatedSorted(IteratorTypeLeft leftBegin, IteratorTypeLeft leftEnd, IteratorTypeRight rightBegin, IteratorTypeRight rightEnd, IteratorTypeDst dstBegin)
410{
411 IteratorTypeLeft leftIter = leftBegin;
412 IteratorTypeRight rightIter = rightBegin;
413 IteratorTypeDst dstIter = dstBegin;
414
415 if (leftIter < leftEnd && rightIter < rightEnd) {
416 for (;;) {
417 auto left = *leftIter;
418 auto right = *rightIter;
419 if (left < right) {
420 *dstIter++ = left;
421 leftIter++;
422 if (leftIter >= leftEnd)
423 break;
424 } else if (left == right) {
425 *dstIter++ = left;
426 leftIter++;
427 rightIter++;
428 if (leftIter >= leftEnd || rightIter >= rightEnd)
429 break;
430 } else {
431 *dstIter++ = right;
432 rightIter++;
433 if (rightIter >= rightEnd)
434 break;
435 }
436 }
437 }
438
439 while (leftIter < leftEnd)
440 *dstIter++ = *leftIter++;
441 while (rightIter < rightEnd)
442 *dstIter++ = *rightIter++;
443
444 return dstIter;
445}
446
447// libstdc++5 does not have constexpr std::tie. Since we cannot redefine std::tie with constexpr, we define WTF::tie instead.
448// This workaround can be removed after 2019-04 and all users of WTF::tie can be converted to std::tie
449// For more info see: https://bugs.webkit.org/show_bug.cgi?id=180692 and https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65978
450template <class ...Args>
451constexpr std::tuple<Args&...> tie(Args&... values)
452{
453 return std::tuple<Args&...>(values...);
454}
455
456} // namespace WTF
457
458// This version of placement new omits a 0 check.
459enum NotNullTag { NotNull };
460inline void* operator new(size_t, NotNullTag, void* location)
461{
462 ASSERT(location);
463 return location;
464}
465
466// This adds various C++14 features for versions of the STL that may not yet have them.
467namespace std {
468#if COMPILER(CLANG) && __cplusplus < 201400L
469template<class T> struct _Unique_if {
470 typedef unique_ptr<T> _Single_object;
471};
472
473template<class T> struct _Unique_if<T[]> {
474 typedef unique_ptr<T[]> _Unknown_bound;
475};
476
477template<class T, size_t N> struct _Unique_if<T[N]> {
478 typedef void _Known_bound;
479};
480
481template<class T, class... Args> inline typename _Unique_if<T>::_Single_object
482make_unique(Args&&... args)
483{
484 return unique_ptr<T>(new T(std::forward<Args>(args)...));
485}
486
487template<class T> inline typename _Unique_if<T>::_Unknown_bound
488make_unique(size_t n)
489{
490 typedef typename remove_extent<T>::type U;
491 return unique_ptr<T>(new U[n]());
492}
493
494template<class T, class... Args> typename _Unique_if<T>::_Known_bound
495make_unique(Args&&...) = delete;
496
497// std::exchange
498template<class T, class U = T>
499T exchange(T& t, U&& newValue)
500{
501 T oldValue = std::move(t);
502 t = std::forward<U>(newValue);
503
504 return oldValue;
505}
506#endif
507
508template<WTF::CheckMoveParameterTag, typename T>
509ALWAYS_INLINE constexpr typename remove_reference<T>::type&& move(T&& value)
510{
511 static_assert(is_lvalue_reference<T>::value, "T is not an lvalue reference; move() is unnecessary.");
512
513 using NonRefQualifiedType = typename remove_reference<T>::type;
514 static_assert(!is_const<NonRefQualifiedType>::value, "T is const qualified.");
515
516 return move(forward<T>(value));
517}
518
519#if __cplusplus < 201703L && (!defined(_MSC_FULL_VER) || _MSC_FULL_VER < 190023918) && !defined(__cpp_lib_logical_traits)
520template<class...> struct wtf_conjunction_impl;
521template<> struct wtf_conjunction_impl<> : true_type { };
522template<class B0> struct wtf_conjunction_impl<B0> : B0 { };
523template<class B0, class B1> struct wtf_conjunction_impl<B0, B1> : conditional<B0::value, B1, B0>::type { };
524template<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 { };
525template<class... _Args> struct conjunction : wtf_conjunction_impl<_Args...> { };
526#endif
527
528// Provide in_place_t when not building with -std=c++17, or when building with libstdc++ 6
529// (which doesn't define the _GLIBCXX_RELEASE macro that's been introduced in libstdc++ 7).
530#if (__cplusplus < 201703L || (defined(__GLIBCXX__) && !defined(_GLIBCXX_RELEASE))) && (!defined(_MSVC_LANG) || _MSVC_LANG < 201703L)
531
532// These are inline variable for C++17 and later.
533#define __IN_PLACE_INLINE_VARIABLE static const
534
535struct in_place_t {
536 explicit in_place_t() = default;
537};
538__IN_PLACE_INLINE_VARIABLE constexpr in_place_t in_place { };
539
540template <class T> struct in_place_type_t {
541 explicit in_place_type_t() = default;
542};
543template <class T>
544__IN_PLACE_INLINE_VARIABLE constexpr in_place_type_t<T> in_place_type { };
545
546template <size_t I> struct in_place_index_t {
547 explicit in_place_index_t() = default;
548};
549template <size_t I>
550__IN_PLACE_INLINE_VARIABLE constexpr in_place_index_t<I> in_place_index { };
551#endif // __cplusplus < 201703L
552
553enum class ZeroStatus {
554 MayBeZero,
555 NonZero
556};
557
558constexpr size_t clz(uint32_t value, ZeroStatus mightBeZero = ZeroStatus::MayBeZero)
559{
560 if (mightBeZero == ZeroStatus::MayBeZero && value) {
561#if COMPILER(MSVC)
562 return __lzcnt(value);
563#else
564 return __builtin_clz(value);
565#endif
566 }
567 return 32;
568}
569
570} // namespace std
571
572#define WTFMove(value) std::move<WTF::CheckMoveParameter>(value)
573
574using WTF::KB;
575using WTF::MB;
576using WTF::GB;
577using WTF::approximateBinarySearch;
578using WTF::binarySearch;
579using WTF::bitwise_cast;
580using WTF::callStatelessLambda;
581using WTF::checkAndSet;
582using WTF::findBitInWord;
583using WTF::insertIntoBoundedVector;
584using WTF::isCompilationThread;
585using WTF::isPointerAligned;
586using WTF::isStatelessLambda;
587using WTF::is8ByteAligned;
588using WTF::mergeDeduplicatedSorted;
589using WTF::roundUpToMultipleOf;
590using WTF::safeCast;
591using WTF::tryBinarySearch;
592