diff options
Diffstat (limited to 'src/3rdparty')
46 files changed, 3822 insertions, 494 deletions
diff --git a/src/3rdparty/llvm/LICENSE.TXT b/src/3rdparty/llvm/LICENSE.TXT new file mode 100644 index 0000000000..ff63f2b6aa --- /dev/null +++ b/src/3rdparty/llvm/LICENSE.TXT @@ -0,0 +1,68 @@ +============================================================================== +LLVM Release License +============================================================================== +University of Illinois/NCSA +Open Source License + +Copyright (c) 2003-2017 University of Illinois at Urbana-Champaign. +All rights reserved. + +Developed by: + + LLVM Team + + University of Illinois at Urbana-Champaign + + http://llvm.org + +Permission is hereby granted, free of charge, to any person obtaining a copy of +this software and associated documentation files (the "Software"), to deal with +the Software without restriction, including without limitation the rights to +use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies +of the Software, and to permit persons to whom the Software is furnished to do +so, subject to the following conditions: + + * Redistributions of source code must retain the above copyright notice, + this list of conditions and the following disclaimers. + + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimers in the + documentation and/or other materials provided with the distribution. + + * Neither the names of the LLVM Team, University of Illinois at + Urbana-Champaign, nor the names of its contributors may be used to + endorse or promote products derived from this Software without specific + prior written permission. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS +FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS WITH THE +SOFTWARE. + +============================================================================== +Copyrights and Licenses for Third Party Software Distributed with LLVM: +============================================================================== +The LLVM software contains code written by third parties. Such software will +have its own individual LICENSE.TXT file in the directory in which it appears. +This file will describe the copyrights, license, and restrictions which apply +to that code. + +The disclaimer of warranty in the University of Illinois Open Source License +applies to all code in the LLVM Distribution, and nothing in any of the +other licenses gives permission to use the names of the LLVM Team or the +University of Illinois to endorse or promote products derived from this +Software. + +The following pieces of software have additional or alternate copyrights, +licenses, and/or restrictions: + +Program Directory +------- --------- +Google Test llvm/utils/unittest/googletest +OpenBSD regex llvm/lib/Support/{reg*, COPYRIGHT.regex} +pyyaml tests llvm/test/YAMLParser/{*.data, LICENSE.TXT} +ARM contributions llvm/lib/Target/ARM/LICENSE.TXT +md5 contributions llvm/lib/Support/MD5.cpp llvm/include/llvm/Support/MD5.h diff --git a/src/3rdparty/llvm/include/llvm-c/DataTypes.h b/src/3rdparty/llvm/include/llvm-c/DataTypes.h new file mode 100644 index 0000000000..7081c83ffc --- /dev/null +++ b/src/3rdparty/llvm/include/llvm-c/DataTypes.h @@ -0,0 +1,90 @@ +/*===-- include/llvm-c/DataTypes.h - Define fixed size types ------*- C -*-===*\ +|* *| +|* The LLVM Compiler Infrastructure *| +|* *| +|* This file is distributed under the University of Illinois Open Source *| +|* License. See LICENSE.TXT for details. *| +|* *| +|*===----------------------------------------------------------------------===*| +|* *| +|* This file contains definitions to figure out the size of _HOST_ data types.*| +|* This file is important because different host OS's define different macros,*| +|* which makes portability tough. This file exports the following *| +|* definitions: *| +|* *| +|* [u]int(32|64)_t : typedefs for signed and unsigned 32/64 bit system types*| +|* [U]INT(8|16|32|64)_(MIN|MAX) : Constants for the min and max values. *| +|* *| +|* No library is required when using these functions. *| +|* *| +|*===----------------------------------------------------------------------===*/ + +/* Please leave this file C-compatible. */ + +#ifndef LLVM_C_DATATYPES_H +#define LLVM_C_DATATYPES_H + +#ifdef __cplusplus +#include <cmath> +#else +#include <math.h> +#endif + +#include <inttypes.h> +#include <stdint.h> + +#ifndef _MSC_VER + +#if !defined(UINT32_MAX) +# error "The standard header <cstdint> is not C++11 compliant. Must #define "\ + "__STDC_LIMIT_MACROS before #including llvm-c/DataTypes.h" +#endif + +#if !defined(UINT32_C) +# error "The standard header <cstdint> is not C++11 compliant. Must #define "\ + "__STDC_CONSTANT_MACROS before #including llvm-c/DataTypes.h" +#endif + +/* Note that <inttypes.h> includes <stdint.h>, if this is a C99 system. */ +#include <sys/types.h> + +#ifdef _AIX +// GCC is strict about defining large constants: they must have LL modifier. +#undef INT64_MAX +#undef INT64_MIN +#endif + +#else /* _MSC_VER */ +#ifdef __cplusplus +#include <cstddef> +#include <cstdlib> +#else +#include <stddef.h> +#include <stdlib.h> +#endif +#include <sys/types.h> + +#if defined(_WIN64) +typedef signed __int64 ssize_t; +#else +typedef signed int ssize_t; +#endif /* _WIN64 */ + +#endif /* _MSC_VER */ + +/* Set defaults for constants which we cannot find. */ +#if !defined(INT64_MAX) +# define INT64_MAX 9223372036854775807LL +#endif +#if !defined(INT64_MIN) +# define INT64_MIN ((-INT64_MAX)-1) +#endif +#if !defined(UINT64_MAX) +# define UINT64_MAX 0xffffffffffffffffULL +#endif + +#ifndef HUGE_VALF +#define HUGE_VALF (float)HUGE_VAL +#endif + +#endif /* LLVM_C_DATATYPES_H */ diff --git a/src/3rdparty/llvm/include/llvm/ADT/PointerIntPair.h b/src/3rdparty/llvm/include/llvm/ADT/PointerIntPair.h new file mode 100644 index 0000000000..884d05155b --- /dev/null +++ b/src/3rdparty/llvm/include/llvm/ADT/PointerIntPair.h @@ -0,0 +1,233 @@ +//===- llvm/ADT/PointerIntPair.h - Pair for pointer and int -----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the PointerIntPair class. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_POINTERINTPAIR_H +#define LLVM_ADT_POINTERINTPAIR_H + +#include "llvm/Support/PointerLikeTypeTraits.h" +#include <cassert> +#include <cstdint> +#include <limits> + +namespace llvm { + +template <typename T> struct DenseMapInfo; +template <typename PointerT, unsigned IntBits, typename PtrTraits> +struct PointerIntPairInfo; + +/// PointerIntPair - This class implements a pair of a pointer and small +/// integer. It is designed to represent this in the space required by one +/// pointer by bitmangling the integer into the low part of the pointer. This +/// can only be done for small integers: typically up to 3 bits, but it depends +/// on the number of bits available according to PointerLikeTypeTraits for the +/// type. +/// +/// Note that PointerIntPair always puts the IntVal part in the highest bits +/// possible. For example, PointerIntPair<void*, 1, bool> will put the bit for +/// the bool into bit #2, not bit #0, which allows the low two bits to be used +/// for something else. For example, this allows: +/// PointerIntPair<PointerIntPair<void*, 1, bool>, 1, bool> +/// ... and the two bools will land in different bits. +template <typename PointerTy, unsigned IntBits, typename IntType = unsigned, + typename PtrTraits = PointerLikeTypeTraits<PointerTy>, + typename Info = PointerIntPairInfo<PointerTy, IntBits, PtrTraits>> +class PointerIntPair { + intptr_t Value = 0; + +public: + constexpr PointerIntPair() = default; + + PointerIntPair(PointerTy PtrVal, IntType IntVal) { + setPointerAndInt(PtrVal, IntVal); + } + + explicit PointerIntPair(PointerTy PtrVal) { initWithPointer(PtrVal); } + + PointerTy getPointer() const { return Info::getPointer(Value); } + + IntType getInt() const { return (IntType)Info::getInt(Value); } + + void setPointer(PointerTy PtrVal) { + Value = Info::updatePointer(Value, PtrVal); + } + + void setInt(IntType IntVal) { + Value = Info::updateInt(Value, static_cast<intptr_t>(IntVal)); + } + + void initWithPointer(PointerTy PtrVal) { + Value = Info::updatePointer(0, PtrVal); + } + + void setPointerAndInt(PointerTy PtrVal, IntType IntVal) { + Value = Info::updateInt(Info::updatePointer(0, PtrVal), + static_cast<intptr_t>(IntVal)); + } + + PointerTy const *getAddrOfPointer() const { + return const_cast<PointerIntPair *>(this)->getAddrOfPointer(); + } + + PointerTy *getAddrOfPointer() { + assert(Value == reinterpret_cast<intptr_t>(getPointer()) && + "Can only return the address if IntBits is cleared and " + "PtrTraits doesn't change the pointer"); + return reinterpret_cast<PointerTy *>(&Value); + } + + void *getOpaqueValue() const { return reinterpret_cast<void *>(Value); } + + void setFromOpaqueValue(void *Val) { + Value = reinterpret_cast<intptr_t>(Val); + } + + static PointerIntPair getFromOpaqueValue(void *V) { + PointerIntPair P; + P.setFromOpaqueValue(V); + return P; + } + + // Allow PointerIntPairs to be created from const void * if and only if the + // pointer type could be created from a const void *. + static PointerIntPair getFromOpaqueValue(const void *V) { + (void)PtrTraits::getFromVoidPointer(V); + return getFromOpaqueValue(const_cast<void *>(V)); + } + + bool operator==(const PointerIntPair &RHS) const { + return Value == RHS.Value; + } + + bool operator!=(const PointerIntPair &RHS) const { + return Value != RHS.Value; + } + + bool operator<(const PointerIntPair &RHS) const { return Value < RHS.Value; } + bool operator>(const PointerIntPair &RHS) const { return Value > RHS.Value; } + + bool operator<=(const PointerIntPair &RHS) const { + return Value <= RHS.Value; + } + + bool operator>=(const PointerIntPair &RHS) const { + return Value >= RHS.Value; + } +}; + +template <typename PointerT, unsigned IntBits, typename PtrTraits> +struct PointerIntPairInfo { + static_assert(PtrTraits::NumLowBitsAvailable < + std::numeric_limits<uintptr_t>::digits, + "cannot use a pointer type that has all bits free"); + static_assert(IntBits <= PtrTraits::NumLowBitsAvailable, + "PointerIntPair with integer size too large for pointer"); + enum : uintptr_t { + /// PointerBitMask - The bits that come from the pointer. + PointerBitMask = + ~(uintptr_t)(((intptr_t)1 << PtrTraits::NumLowBitsAvailable) - 1), + + /// IntShift - The number of low bits that we reserve for other uses, and + /// keep zero. + IntShift = (uintptr_t)PtrTraits::NumLowBitsAvailable - IntBits, + + /// IntMask - This is the unshifted mask for valid bits of the int type. + IntMask = (uintptr_t)(((intptr_t)1 << IntBits) - 1), + + // ShiftedIntMask - This is the bits for the integer shifted in place. + ShiftedIntMask = (uintptr_t)(IntMask << IntShift) + }; + + static PointerT getPointer(intptr_t Value) { + return PtrTraits::getFromVoidPointer( + reinterpret_cast<void *>(Value & PointerBitMask)); + } + + static intptr_t getInt(intptr_t Value) { + return (Value >> IntShift) & IntMask; + } + + static intptr_t updatePointer(intptr_t OrigValue, PointerT Ptr) { + intptr_t PtrWord = + reinterpret_cast<intptr_t>(PtrTraits::getAsVoidPointer(Ptr)); + assert((PtrWord & ~PointerBitMask) == 0 && + "Pointer is not sufficiently aligned"); + // Preserve all low bits, just update the pointer. + return PtrWord | (OrigValue & ~PointerBitMask); + } + + static intptr_t updateInt(intptr_t OrigValue, intptr_t Int) { + intptr_t IntWord = static_cast<intptr_t>(Int); + assert((IntWord & ~IntMask) == 0 && "Integer too large for field"); + + // Preserve all bits other than the ones we are updating. + return (OrigValue & ~ShiftedIntMask) | IntWord << IntShift; + } +}; + +template <typename T> struct isPodLike; +template <typename PointerTy, unsigned IntBits, typename IntType> +struct isPodLike<PointerIntPair<PointerTy, IntBits, IntType>> { + static const bool value = true; +}; + +// Provide specialization of DenseMapInfo for PointerIntPair. +template <typename PointerTy, unsigned IntBits, typename IntType> +struct DenseMapInfo<PointerIntPair<PointerTy, IntBits, IntType>> { + using Ty = PointerIntPair<PointerTy, IntBits, IntType>; + + static Ty getEmptyKey() { + uintptr_t Val = static_cast<uintptr_t>(-1); + Val <<= PointerLikeTypeTraits<Ty>::NumLowBitsAvailable; + return Ty::getFromOpaqueValue(reinterpret_cast<void *>(Val)); + } + + static Ty getTombstoneKey() { + uintptr_t Val = static_cast<uintptr_t>(-2); + Val <<= PointerLikeTypeTraits<PointerTy>::NumLowBitsAvailable; + return Ty::getFromOpaqueValue(reinterpret_cast<void *>(Val)); + } + + static unsigned getHashValue(Ty V) { + uintptr_t IV = reinterpret_cast<uintptr_t>(V.getOpaqueValue()); + return unsigned(IV) ^ unsigned(IV >> 9); + } + + static bool isEqual(const Ty &LHS, const Ty &RHS) { return LHS == RHS; } +}; + +// Teach SmallPtrSet that PointerIntPair is "basically a pointer". +template <typename PointerTy, unsigned IntBits, typename IntType, + typename PtrTraits> +struct PointerLikeTypeTraits< + PointerIntPair<PointerTy, IntBits, IntType, PtrTraits>> { + static inline void * + getAsVoidPointer(const PointerIntPair<PointerTy, IntBits, IntType> &P) { + return P.getOpaqueValue(); + } + + static inline PointerIntPair<PointerTy, IntBits, IntType> + getFromVoidPointer(void *P) { + return PointerIntPair<PointerTy, IntBits, IntType>::getFromOpaqueValue(P); + } + + static inline PointerIntPair<PointerTy, IntBits, IntType> + getFromVoidPointer(const void *P) { + return PointerIntPair<PointerTy, IntBits, IntType>::getFromOpaqueValue(P); + } + + enum { NumLowBitsAvailable = PtrTraits::NumLowBitsAvailable - IntBits }; +}; + +} // end namespace llvm + +#endif // LLVM_ADT_POINTERINTPAIR_H diff --git a/src/3rdparty/llvm/include/llvm/ADT/ilist.h b/src/3rdparty/llvm/include/llvm/ADT/ilist.h new file mode 100644 index 0000000000..7e346e1260 --- /dev/null +++ b/src/3rdparty/llvm/include/llvm/ADT/ilist.h @@ -0,0 +1,431 @@ +//==-- llvm/ADT/ilist.h - Intrusive Linked List Template ---------*- C++ -*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines classes to implement an intrusive doubly linked list class +// (i.e. each node of the list must contain a next and previous field for the +// list. +// +// The ilist class itself should be a plug in replacement for list. This list +// replacement does not provide a constant time size() method, so be careful to +// use empty() when you really want to know if it's empty. +// +// The ilist class is implemented as a circular list. The list itself contains +// a sentinel node, whose Next points at begin() and whose Prev points at +// rbegin(). The sentinel node itself serves as end() and rend(). +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_ILIST_H +#define LLVM_ADT_ILIST_H + +#include "llvm/ADT/simple_ilist.h" +#include <cassert> +#include <cstddef> +#include <iterator> + +namespace llvm { + +/// Use delete by default for iplist and ilist. +/// +/// Specialize this to get different behaviour for ownership-related API. (If +/// you really want ownership semantics, consider using std::list or building +/// something like \a BumpPtrList.) +/// +/// \see ilist_noalloc_traits +template <typename NodeTy> struct ilist_alloc_traits { + static void deleteNode(NodeTy *V) { delete V; } +}; + +/// Custom traits to do nothing on deletion. +/// +/// Specialize ilist_alloc_traits to inherit from this to disable the +/// non-intrusive deletion in iplist (which implies ownership). +/// +/// If you want purely intrusive semantics with no callbacks, consider using \a +/// simple_ilist instead. +/// +/// \code +/// template <> +/// struct ilist_alloc_traits<MyType> : ilist_noalloc_traits<MyType> {}; +/// \endcode +template <typename NodeTy> struct ilist_noalloc_traits { + static void deleteNode(NodeTy *) {} +}; + +/// Callbacks do nothing by default in iplist and ilist. +/// +/// Specialize this for to use callbacks for when nodes change their list +/// membership. +template <typename NodeTy> struct ilist_callback_traits { + void addNodeToList(NodeTy *) {} + void removeNodeFromList(NodeTy *) {} + + /// Callback before transferring nodes to this list. + /// + /// \pre \c this!=&OldList + template <class Iterator> + void transferNodesFromList(ilist_callback_traits &OldList, Iterator /*first*/, + Iterator /*last*/) { + (void)OldList; + } +}; + +/// A fragment for template traits for intrusive list that provides default +/// node related operations. +/// +/// TODO: Remove this layer of indirection. It's not necessary. +template <typename NodeTy> +struct ilist_node_traits : ilist_alloc_traits<NodeTy>, + ilist_callback_traits<NodeTy> {}; + +/// Default template traits for intrusive list. +/// +/// By inheriting from this, you can easily use default implementations for all +/// common operations. +/// +/// TODO: Remove this customization point. Specializing ilist_traits is +/// already fully general. +template <typename NodeTy> +struct ilist_default_traits : public ilist_node_traits<NodeTy> {}; + +/// Template traits for intrusive list. +/// +/// Customize callbacks and allocation semantics. +template <typename NodeTy> +struct ilist_traits : public ilist_default_traits<NodeTy> {}; + +/// Const traits should never be instantiated. +template <typename Ty> struct ilist_traits<const Ty> {}; + +namespace ilist_detail { + +template <class T> T &make(); + +/// Type trait to check for a traits class that has a getNext member (as a +/// canary for any of the ilist_nextprev_traits API). +template <class TraitsT, class NodeT> struct HasGetNext { + typedef char Yes[1]; + typedef char No[2]; + template <size_t N> struct SFINAE {}; + + template <class U> + static Yes &test(U *I, decltype(I->getNext(&make<NodeT>())) * = 0); + template <class> static No &test(...); + +public: + static const bool value = sizeof(test<TraitsT>(nullptr)) == sizeof(Yes); +}; + +/// Type trait to check for a traits class that has a createSentinel member (as +/// a canary for any of the ilist_sentinel_traits API). +template <class TraitsT> struct HasCreateSentinel { + typedef char Yes[1]; + typedef char No[2]; + + template <class U> + static Yes &test(U *I, decltype(I->createSentinel()) * = 0); + template <class> static No &test(...); + +public: + static const bool value = sizeof(test<TraitsT>(nullptr)) == sizeof(Yes); +}; + +/// Type trait to check for a traits class that has a createNode member. +/// Allocation should be managed in a wrapper class, instead of in +/// ilist_traits. +template <class TraitsT, class NodeT> struct HasCreateNode { + typedef char Yes[1]; + typedef char No[2]; + template <size_t N> struct SFINAE {}; + + template <class U> + static Yes &test(U *I, decltype(I->createNode(make<NodeT>())) * = 0); + template <class> static No &test(...); + +public: + static const bool value = sizeof(test<TraitsT>(nullptr)) == sizeof(Yes); +}; + +template <class TraitsT, class NodeT> struct HasObsoleteCustomization { + static const bool value = HasGetNext<TraitsT, NodeT>::value || + HasCreateSentinel<TraitsT>::value || + HasCreateNode<TraitsT, NodeT>::value; +}; + +} // end namespace ilist_detail + +//===----------------------------------------------------------------------===// +// +/// A wrapper around an intrusive list with callbacks and non-intrusive +/// ownership. +/// +/// This wraps a purely intrusive list (like simple_ilist) with a configurable +/// traits class. The traits can implement callbacks and customize the +/// ownership semantics. +/// +/// This is a subset of ilist functionality that can safely be used on nodes of +/// polymorphic types, i.e. a heterogeneous list with a common base class that +/// holds the next/prev pointers. The only state of the list itself is an +/// ilist_sentinel, which holds pointers to the first and last nodes in the +/// list. +template <class IntrusiveListT, class TraitsT> +class iplist_impl : public TraitsT, IntrusiveListT { + typedef IntrusiveListT base_list_type; + +public: + typedef typename base_list_type::pointer pointer; + typedef typename base_list_type::const_pointer const_pointer; + typedef typename base_list_type::reference reference; + typedef typename base_list_type::const_reference const_reference; + typedef typename base_list_type::value_type value_type; + typedef typename base_list_type::size_type size_type; + typedef typename base_list_type::difference_type difference_type; + typedef typename base_list_type::iterator iterator; + typedef typename base_list_type::const_iterator const_iterator; + typedef typename base_list_type::reverse_iterator reverse_iterator; + typedef + typename base_list_type::const_reverse_iterator const_reverse_iterator; + +private: + // TODO: Drop this assertion and the transitive type traits anytime after + // v4.0 is branched (i.e,. keep them for one release to help out-of-tree code + // update). + static_assert( + !ilist_detail::HasObsoleteCustomization<TraitsT, value_type>::value, + "ilist customization points have changed!"); + + static bool op_less(const_reference L, const_reference R) { return L < R; } + static bool op_equal(const_reference L, const_reference R) { return L == R; } + +public: + iplist_impl() = default; + + iplist_impl(const iplist_impl &) = delete; + iplist_impl &operator=(const iplist_impl &) = delete; + + iplist_impl(iplist_impl &&X) + : TraitsT(std::move(X)), IntrusiveListT(std::move(X)) {} + iplist_impl &operator=(iplist_impl &&X) { + *static_cast<TraitsT *>(this) = std::move(X); + *static_cast<IntrusiveListT *>(this) = std::move(X); + return *this; + } + + ~iplist_impl() { clear(); } + + // Miscellaneous inspection routines. + size_type max_size() const { return size_type(-1); } + + using base_list_type::begin; + using base_list_type::end; + using base_list_type::rbegin; + using base_list_type::rend; + using base_list_type::empty; + using base_list_type::front; + using base_list_type::back; + + void swap(iplist_impl &RHS) { + assert(0 && "Swap does not use list traits callback correctly yet!"); + base_list_type::swap(RHS); + } + + iterator insert(iterator where, pointer New) { + this->addNodeToList(New); // Notify traits that we added a node... + return base_list_type::insert(where, *New); + } + + iterator insert(iterator where, const_reference New) { + return this->insert(where, new value_type(New)); + } + + iterator insertAfter(iterator where, pointer New) { + if (empty()) + return insert(begin(), New); + else + return insert(++where, New); + } + + /// Clone another list. + template <class Cloner> void cloneFrom(const iplist_impl &L2, Cloner clone) { + clear(); + for (const_reference V : L2) + push_back(clone(V)); + } + + pointer remove(iterator &IT) { + pointer Node = &*IT++; + this->removeNodeFromList(Node); // Notify traits that we removed a node... + base_list_type::remove(*Node); + return Node; + } + + pointer remove(const iterator &IT) { + iterator MutIt = IT; + return remove(MutIt); + } + + pointer remove(pointer IT) { return remove(iterator(IT)); } + pointer remove(reference IT) { return remove(iterator(IT)); } + + // erase - remove a node from the controlled sequence... and delete it. + iterator erase(iterator where) { + this->deleteNode(remove(where)); + return where; + } + + iterator erase(pointer IT) { return erase(iterator(IT)); } + iterator erase(reference IT) { return erase(iterator(IT)); } + + /// Remove all nodes from the list like clear(), but do not call + /// removeNodeFromList() or deleteNode(). + /// + /// This should only be used immediately before freeing nodes in bulk to + /// avoid traversing the list and bringing all the nodes into cache. + void clearAndLeakNodesUnsafely() { base_list_type::clear(); } + +private: + // transfer - The heart of the splice function. Move linked list nodes from + // [first, last) into position. + // + void transfer(iterator position, iplist_impl &L2, iterator first, iterator last) { + if (position == last) + return; + + if (this != &L2) // Notify traits we moved the nodes... + this->transferNodesFromList(L2, first, last); + + base_list_type::splice(position, L2, first, last); + } + +public: + //===----------------------------------------------------------------------=== + // Functionality derived from other functions defined above... + // + + using base_list_type::size; + + iterator erase(iterator first, iterator last) { + while (first != last) + first = erase(first); + return last; + } + + void clear() { erase(begin(), end()); } + + // Front and back inserters... + void push_front(pointer val) { insert(begin(), val); } + void push_back(pointer val) { insert(end(), val); } + void pop_front() { + assert(!empty() && "pop_front() on empty list!"); + erase(begin()); + } + void pop_back() { + assert(!empty() && "pop_back() on empty list!"); + iterator t = end(); erase(--t); + } + + // Special forms of insert... + template<class InIt> void insert(iterator where, InIt first, InIt last) { + for (; first != last; ++first) insert(where, *first); + } + + // Splice members - defined in terms of transfer... + void splice(iterator where, iplist_impl &L2) { + if (!L2.empty()) + transfer(where, L2, L2.begin(), L2.end()); + } + void splice(iterator where, iplist_impl &L2, iterator first) { + iterator last = first; ++last; + if (where == first || where == last) return; // No change + transfer(where, L2, first, last); + } + void splice(iterator where, iplist_impl &L2, iterator first, iterator last) { + if (first != last) transfer(where, L2, first, last); + } + void splice(iterator where, iplist_impl &L2, reference N) { + splice(where, L2, iterator(N)); + } + void splice(iterator where, iplist_impl &L2, pointer N) { + splice(where, L2, iterator(N)); + } + + template <class Compare> + void merge(iplist_impl &Right, Compare comp) { + if (this == &Right) + return; + this->transferNodesFromList(Right, Right.begin(), Right.end()); + base_list_type::merge(Right, comp); + } + void merge(iplist_impl &Right) { return merge(Right, op_less); } + + using base_list_type::sort; + + /// \brief Get the previous node, or \c nullptr for the list head. + pointer getPrevNode(reference N) const { + auto I = N.getIterator(); + if (I == begin()) + return nullptr; + return &*std::prev(I); + } + /// \brief Get the previous node, or \c nullptr for the list head. + const_pointer getPrevNode(const_reference N) const { + return getPrevNode(const_cast<reference >(N)); + } + + /// \brief Get the next node, or \c nullptr for the list tail. + pointer getNextNode(reference N) const { + auto Next = std::next(N.getIterator()); + if (Next == end()) + return nullptr; + return &*Next; + } + /// \brief Get the next node, or \c nullptr for the list tail. + const_pointer getNextNode(const_reference N) const { + return getNextNode(const_cast<reference >(N)); + } +}; + +/// An intrusive list with ownership and callbacks specified/controlled by +/// ilist_traits, only with API safe for polymorphic types. +/// +/// The \p Options parameters are the same as those for \a simple_ilist. See +/// there for a description of what's available. +template <class T, class... Options> +class iplist + : public iplist_impl<simple_ilist<T, Options...>, ilist_traits<T>> { + using iplist_impl_type = typename iplist::iplist_impl; + +public: + iplist() = default; + + iplist(const iplist &X) = delete; + iplist &operator=(const iplist &X) = delete; + + iplist(iplist &&X) : iplist_impl_type(std::move(X)) {} + iplist &operator=(iplist &&X) { + *static_cast<iplist_impl_type *>(this) = std::move(X); + return *this; + } +}; + +template <class T, class... Options> using ilist = iplist<T, Options...>; + +} // end namespace llvm + +namespace std { + + // Ensure that swap uses the fast list swap... + template<class Ty> + void swap(llvm::iplist<Ty> &Left, llvm::iplist<Ty> &Right) { + Left.swap(Right); + } + +} // end namespace std + +#endif // LLVM_ADT_ILIST_H diff --git a/src/3rdparty/llvm/include/llvm/ADT/ilist_base.h b/src/3rdparty/llvm/include/llvm/ADT/ilist_base.h new file mode 100644 index 0000000000..3d818a48d4 --- /dev/null +++ b/src/3rdparty/llvm/include/llvm/ADT/ilist_base.h @@ -0,0 +1,93 @@ +//===- llvm/ADT/ilist_base.h - Intrusive List Base --------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_ILIST_BASE_H +#define LLVM_ADT_ILIST_BASE_H + +#include "llvm/ADT/ilist_node_base.h" +#include <cassert> + +namespace llvm { + +/// Implementations of list algorithms using ilist_node_base. +template <bool EnableSentinelTracking> class ilist_base { +public: + using node_base_type = ilist_node_base<EnableSentinelTracking>; + + static void insertBeforeImpl(node_base_type &Next, node_base_type &N) { + node_base_type &Prev = *Next.getPrev(); + N.setNext(&Next); + N.setPrev(&Prev); + Prev.setNext(&N); + Next.setPrev(&N); + } + + static void removeImpl(node_base_type &N) { + node_base_type *Prev = N.getPrev(); + node_base_type *Next = N.getNext(); + Next->setPrev(Prev); + Prev->setNext(Next); + + // Not strictly necessary, but helps catch a class of bugs. + N.setPrev(nullptr); + N.setNext(nullptr); + } + + static void removeRangeImpl(node_base_type &First, node_base_type &Last) { + node_base_type *Prev = First.getPrev(); + node_base_type *Final = Last.getPrev(); + Last.setPrev(Prev); + Prev->setNext(&Last); + + // Not strictly necessary, but helps catch a class of bugs. + First.setPrev(nullptr); + Final->setNext(nullptr); + } + + static void transferBeforeImpl(node_base_type &Next, node_base_type &First, + node_base_type &Last) { + if (&Next == &Last || &First == &Last) + return; + + // Position cannot be contained in the range to be transferred. + assert(&Next != &First && + // Check for the most common mistake. + "Insertion point can't be one of the transferred nodes"); + + node_base_type &Final = *Last.getPrev(); + + // Detach from old list/position. + First.getPrev()->setNext(&Last); + Last.setPrev(First.getPrev()); + + // Splice [First, Final] into its new list/position. + node_base_type &Prev = *Next.getPrev(); + Final.setNext(&Next); + First.setPrev(&Prev); + Prev.setNext(&First); + Next.setPrev(&Final); + } + + template <class T> static void insertBefore(T &Next, T &N) { + insertBeforeImpl(Next, N); + } + + template <class T> static void remove(T &N) { removeImpl(N); } + template <class T> static void removeRange(T &First, T &Last) { + removeRangeImpl(First, Last); + } + + template <class T> static void transferBefore(T &Next, T &First, T &Last) { + transferBeforeImpl(Next, First, Last); + } +}; + +} // end namespace llvm + +#endif // LLVM_ADT_ILIST_BASE_H diff --git a/src/3rdparty/llvm/include/llvm/ADT/ilist_iterator.h b/src/3rdparty/llvm/include/llvm/ADT/ilist_iterator.h new file mode 100644 index 0000000000..671e644e01 --- /dev/null +++ b/src/3rdparty/llvm/include/llvm/ADT/ilist_iterator.h @@ -0,0 +1,199 @@ +//===- llvm/ADT/ilist_iterator.h - Intrusive List Iterator ------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_ILIST_ITERATOR_H +#define LLVM_ADT_ILIST_ITERATOR_H + +#include "llvm/ADT/ilist_node.h" +#include <cassert> +#include <cstddef> +#include <iterator> +#include <type_traits> + +namespace llvm { + +namespace ilist_detail { + +/// Find const-correct node types. +template <class OptionsT, bool IsConst> struct IteratorTraits; +template <class OptionsT> struct IteratorTraits<OptionsT, false> { + using value_type = typename OptionsT::value_type; + using pointer = typename OptionsT::pointer; + using reference = typename OptionsT::reference; + using node_pointer = ilist_node_impl<OptionsT> *; + using node_reference = ilist_node_impl<OptionsT> &; +}; +template <class OptionsT> struct IteratorTraits<OptionsT, true> { + using value_type = const typename OptionsT::value_type; + using pointer = typename OptionsT::const_pointer; + using reference = typename OptionsT::const_reference; + using node_pointer = const ilist_node_impl<OptionsT> *; + using node_reference = const ilist_node_impl<OptionsT> &; +}; + +template <bool IsReverse> struct IteratorHelper; +template <> struct IteratorHelper<false> : ilist_detail::NodeAccess { + using Access = ilist_detail::NodeAccess; + + template <class T> static void increment(T *&I) { I = Access::getNext(*I); } + template <class T> static void decrement(T *&I) { I = Access::getPrev(*I); } +}; +template <> struct IteratorHelper<true> : ilist_detail::NodeAccess { + using Access = ilist_detail::NodeAccess; + + template <class T> static void increment(T *&I) { I = Access::getPrev(*I); } + template <class T> static void decrement(T *&I) { I = Access::getNext(*I); } +}; + +} // end namespace ilist_detail + +/// Iterator for intrusive lists based on ilist_node. +template <class OptionsT, bool IsReverse, bool IsConst> +class ilist_iterator : ilist_detail::SpecificNodeAccess<OptionsT> { + friend ilist_iterator<OptionsT, IsReverse, !IsConst>; + friend ilist_iterator<OptionsT, !IsReverse, IsConst>; + friend ilist_iterator<OptionsT, !IsReverse, !IsConst>; + + using Traits = ilist_detail::IteratorTraits<OptionsT, IsConst>; + using Access = ilist_detail::SpecificNodeAccess<OptionsT>; + +public: + using value_type = typename Traits::value_type; + using pointer = typename Traits::pointer; + using reference = typename Traits::reference; + using difference_type = ptrdiff_t; + using iterator_category = std::bidirectional_iterator_tag; + using const_pointer = typename OptionsT::const_pointer; + using const_reference = typename OptionsT::const_reference; + +private: + using node_pointer = typename Traits::node_pointer; + using node_reference = typename Traits::node_reference; + + node_pointer NodePtr = nullptr; + +public: + /// Create from an ilist_node. + explicit ilist_iterator(node_reference N) : NodePtr(&N) {} + + explicit ilist_iterator(pointer NP) : NodePtr(Access::getNodePtr(NP)) {} + explicit ilist_iterator(reference NR) : NodePtr(Access::getNodePtr(&NR)) {} + ilist_iterator() = default; + + // This is templated so that we can allow constructing a const iterator from + // a nonconst iterator... + template <bool RHSIsConst> + ilist_iterator( + const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS, + typename std::enable_if<IsConst || !RHSIsConst, void *>::type = nullptr) + : NodePtr(RHS.NodePtr) {} + + // This is templated so that we can allow assigning to a const iterator from + // a nonconst iterator... + template <bool RHSIsConst> + typename std::enable_if<IsConst || !RHSIsConst, ilist_iterator &>::type + operator=(const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS) { + NodePtr = RHS.NodePtr; + return *this; + } + + /// Explicit conversion between forward/reverse iterators. + /// + /// Translate between forward and reverse iterators without changing range + /// boundaries. The resulting iterator will dereference (and have a handle) + /// to the previous node, which is somewhat unexpected; but converting the + /// two endpoints in a range will give the same range in reverse. + /// + /// This matches std::reverse_iterator conversions. + explicit ilist_iterator( + const ilist_iterator<OptionsT, !IsReverse, IsConst> &RHS) + : ilist_iterator(++RHS.getReverse()) {} + + /// Get a reverse iterator to the same node. + /// + /// Gives a reverse iterator that will dereference (and have a handle) to the + /// same node. Converting the endpoint iterators in a range will give a + /// different range; for range operations, use the explicit conversions. + ilist_iterator<OptionsT, !IsReverse, IsConst> getReverse() const { + if (NodePtr) + return ilist_iterator<OptionsT, !IsReverse, IsConst>(*NodePtr); + return ilist_iterator<OptionsT, !IsReverse, IsConst>(); + } + + /// Const-cast. + ilist_iterator<OptionsT, IsReverse, false> getNonConst() const { + if (NodePtr) + return ilist_iterator<OptionsT, IsReverse, false>( + const_cast<typename ilist_iterator<OptionsT, IsReverse, + false>::node_reference>(*NodePtr)); + return ilist_iterator<OptionsT, IsReverse, false>(); + } + + // Accessors... + reference operator*() const { + assert(!NodePtr->isKnownSentinel()); + return *Access::getValuePtr(NodePtr); + } + pointer operator->() const { return &operator*(); } + + // Comparison operators + friend bool operator==(const ilist_iterator &LHS, const ilist_iterator &RHS) { + return LHS.NodePtr == RHS.NodePtr; + } + friend bool operator!=(const ilist_iterator &LHS, const ilist_iterator &RHS) { + return LHS.NodePtr != RHS.NodePtr; + } + + // Increment and decrement operators... + ilist_iterator &operator--() { + NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev(); + return *this; + } + ilist_iterator &operator++() { + NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext(); + return *this; + } + ilist_iterator operator--(int) { + ilist_iterator tmp = *this; + --*this; + return tmp; + } + ilist_iterator operator++(int) { + ilist_iterator tmp = *this; + ++*this; + return tmp; + } + + /// Get the underlying ilist_node. + node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); } + + /// Check for end. Only valid if ilist_sentinel_tracking<true>. + bool isEnd() const { return NodePtr ? NodePtr->isSentinel() : false; } +}; + +template <typename From> struct simplify_type; + +/// Allow ilist_iterators to convert into pointers to a node automatically when +/// used by the dyn_cast, cast, isa mechanisms... +/// +/// FIXME: remove this, since there is no implicit conversion to NodeTy. +template <class OptionsT, bool IsConst> +struct simplify_type<ilist_iterator<OptionsT, false, IsConst>> { + using iterator = ilist_iterator<OptionsT, false, IsConst>; + using SimpleType = typename iterator::pointer; + + static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; } +}; +template <class OptionsT, bool IsConst> +struct simplify_type<const ilist_iterator<OptionsT, false, IsConst>> + : simplify_type<ilist_iterator<OptionsT, false, IsConst>> {}; + +} // end namespace llvm + +#endif // LLVM_ADT_ILIST_ITERATOR_H diff --git a/src/3rdparty/llvm/include/llvm/ADT/ilist_node.h b/src/3rdparty/llvm/include/llvm/ADT/ilist_node.h new file mode 100644 index 0000000000..3362611697 --- /dev/null +++ b/src/3rdparty/llvm/include/llvm/ADT/ilist_node.h @@ -0,0 +1,306 @@ +//===- llvm/ADT/ilist_node.h - Intrusive Linked List Helper -----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the ilist_node class template, which is a convenient +// base class for creating classes that can be used with ilists. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_ILIST_NODE_H +#define LLVM_ADT_ILIST_NODE_H + +#include "llvm/ADT/ilist_node_base.h" +#include "llvm/ADT/ilist_node_options.h" + +namespace llvm { + +namespace ilist_detail { + +struct NodeAccess; + +} // end namespace ilist_detail + +template <class OptionsT, bool IsReverse, bool IsConst> class ilist_iterator; +template <class OptionsT> class ilist_sentinel; + +/// Implementation for an ilist node. +/// +/// Templated on an appropriate \a ilist_detail::node_options, usually computed +/// by \a ilist_detail::compute_node_options. +/// +/// This is a wrapper around \a ilist_node_base whose main purpose is to +/// provide type safety: you can't insert nodes of \a ilist_node_impl into the +/// wrong \a simple_ilist or \a iplist. +template <class OptionsT> class ilist_node_impl : OptionsT::node_base_type { + using value_type = typename OptionsT::value_type; + using node_base_type = typename OptionsT::node_base_type; + using list_base_type = typename OptionsT::list_base_type; + + friend typename OptionsT::list_base_type; + friend struct ilist_detail::NodeAccess; + friend class ilist_sentinel<OptionsT>; + friend class ilist_iterator<OptionsT, false, false>; + friend class ilist_iterator<OptionsT, false, true>; + friend class ilist_iterator<OptionsT, true, false>; + friend class ilist_iterator<OptionsT, true, true>; + +protected: + using self_iterator = ilist_iterator<OptionsT, false, false>; + using const_self_iterator = ilist_iterator<OptionsT, false, true>; + using reverse_self_iterator = ilist_iterator<OptionsT, true, false>; + using const_reverse_self_iterator = ilist_iterator<OptionsT, true, true>; + + ilist_node_impl() = default; + +private: + ilist_node_impl *getPrev() { + return static_cast<ilist_node_impl *>(node_base_type::getPrev()); + } + + ilist_node_impl *getNext() { + return static_cast<ilist_node_impl *>(node_base_type::getNext()); + } + + const ilist_node_impl *getPrev() const { + return static_cast<ilist_node_impl *>(node_base_type::getPrev()); + } + + const ilist_node_impl *getNext() const { + return static_cast<ilist_node_impl *>(node_base_type::getNext()); + } + + void setPrev(ilist_node_impl *N) { node_base_type::setPrev(N); } + void setNext(ilist_node_impl *N) { node_base_type::setNext(N); } + +public: + self_iterator getIterator() { return self_iterator(*this); } + const_self_iterator getIterator() const { return const_self_iterator(*this); } + + reverse_self_iterator getReverseIterator() { + return reverse_self_iterator(*this); + } + + const_reverse_self_iterator getReverseIterator() const { + return const_reverse_self_iterator(*this); + } + + // Under-approximation, but always available for assertions. + using node_base_type::isKnownSentinel; + + /// Check whether this is the sentinel node. + /// + /// This requires sentinel tracking to be explicitly enabled. Use the + /// ilist_sentinel_tracking<true> option to get this API. + bool isSentinel() const { + static_assert(OptionsT::is_sentinel_tracking_explicit, + "Use ilist_sentinel_tracking<true> to enable isSentinel()"); + return node_base_type::isSentinel(); + } +}; + +/// An intrusive list node. +/// +/// A base class to enable membership in intrusive lists, including \a +/// simple_ilist, \a iplist, and \a ilist. The first template parameter is the +/// \a value_type for the list. +/// +/// An ilist node can be configured with compile-time options to change +/// behaviour and/or add API. +/// +/// By default, an \a ilist_node knows whether it is the list sentinel (an +/// instance of \a ilist_sentinel) if and only if +/// LLVM_ENABLE_ABI_BREAKING_CHECKS. The function \a isKnownSentinel() always +/// returns \c false tracking is off. Sentinel tracking steals a bit from the +/// "prev" link, which adds a mask operation when decrementing an iterator, but +/// enables bug-finding assertions in \a ilist_iterator. +/// +/// To turn sentinel tracking on all the time, pass in the +/// ilist_sentinel_tracking<true> template parameter. This also enables the \a +/// isSentinel() function. The same option must be passed to the intrusive +/// list. (ilist_sentinel_tracking<false> turns sentinel tracking off all the +/// time.) +/// +/// A type can inherit from ilist_node multiple times by passing in different +/// \a ilist_tag options. This allows a single instance to be inserted into +/// multiple lists simultaneously, where each list is given the same tag. +/// +/// \example +/// struct A {}; +/// struct B {}; +/// struct N : ilist_node<N, ilist_tag<A>>, ilist_node<N, ilist_tag<B>> {}; +/// +/// void foo() { +/// simple_ilist<N, ilist_tag<A>> ListA; +/// simple_ilist<N, ilist_tag<B>> ListB; +/// N N1; +/// ListA.push_back(N1); +/// ListB.push_back(N1); +/// } +/// \endexample +/// +/// See \a is_valid_option for steps on adding a new option. +template <class T, class... Options> +class ilist_node + : public ilist_node_impl< + typename ilist_detail::compute_node_options<T, Options...>::type> { + static_assert(ilist_detail::check_options<Options...>::value, + "Unrecognized node option!"); +}; + +namespace ilist_detail { + +/// An access class for ilist_node private API. +/// +/// This gives access to the private parts of ilist nodes. Nodes for an ilist +/// should friend this class if they inherit privately from ilist_node. +/// +/// Using this class outside of the ilist implementation is unsupported. +struct NodeAccess { +protected: + template <class OptionsT> + static ilist_node_impl<OptionsT> *getNodePtr(typename OptionsT::pointer N) { + return N; + } + + template <class OptionsT> + static const ilist_node_impl<OptionsT> * + getNodePtr(typename OptionsT::const_pointer N) { + return N; + } + + template <class OptionsT> + static typename OptionsT::pointer getValuePtr(ilist_node_impl<OptionsT> *N) { + return static_cast<typename OptionsT::pointer>(N); + } + + template <class OptionsT> + static typename OptionsT::const_pointer + getValuePtr(const ilist_node_impl<OptionsT> *N) { + return static_cast<typename OptionsT::const_pointer>(N); + } + + template <class OptionsT> + static ilist_node_impl<OptionsT> *getPrev(ilist_node_impl<OptionsT> &N) { + return N.getPrev(); + } + + template <class OptionsT> + static ilist_node_impl<OptionsT> *getNext(ilist_node_impl<OptionsT> &N) { + return N.getNext(); + } + + template <class OptionsT> + static const ilist_node_impl<OptionsT> * + getPrev(const ilist_node_impl<OptionsT> &N) { + return N.getPrev(); + } + + template <class OptionsT> + static const ilist_node_impl<OptionsT> * + getNext(const ilist_node_impl<OptionsT> &N) { + return N.getNext(); + } +}; + +template <class OptionsT> struct SpecificNodeAccess : NodeAccess { +protected: + using pointer = typename OptionsT::pointer; + using const_pointer = typename OptionsT::const_pointer; + using node_type = ilist_node_impl<OptionsT>; + + static node_type *getNodePtr(pointer N) { + return NodeAccess::getNodePtr<OptionsT>(N); + } + + static const node_type *getNodePtr(const_pointer N) { + return NodeAccess::getNodePtr<OptionsT>(N); + } + + static pointer getValuePtr(node_type *N) { + return NodeAccess::getValuePtr<OptionsT>(N); + } + + static const_pointer getValuePtr(const node_type *N) { + return NodeAccess::getValuePtr<OptionsT>(N); + } +}; + +} // end namespace ilist_detail + +template <class OptionsT> +class ilist_sentinel : public ilist_node_impl<OptionsT> { +public: + ilist_sentinel() { + this->initializeSentinel(); + reset(); + } + + void reset() { + this->setPrev(this); + this->setNext(this); + } + + bool empty() const { return this == this->getPrev(); } +}; + +/// An ilist node that can access its parent list. +/// +/// Requires \c NodeTy to have \a getParent() to find the parent node, and the +/// \c ParentTy to have \a getSublistAccess() to get a reference to the list. +template <typename NodeTy, typename ParentTy, class... Options> +class ilist_node_with_parent : public ilist_node<NodeTy, Options...> { +protected: + ilist_node_with_parent() = default; + +private: + /// Forward to NodeTy::getParent(). + /// + /// Note: do not use the name "getParent()". We want a compile error + /// (instead of recursion) when the subclass fails to implement \a + /// getParent(). + const ParentTy *getNodeParent() const { + return static_cast<const NodeTy *>(this)->getParent(); + } + +public: + /// @name Adjacent Node Accessors + /// @{ + /// \brief Get the previous node, or \c nullptr for the list head. + NodeTy *getPrevNode() { + // Should be separated to a reused function, but then we couldn't use auto + // (and would need the type of the list). + const auto &List = + getNodeParent()->*(ParentTy::getSublistAccess((NodeTy *)nullptr)); + return List.getPrevNode(*static_cast<NodeTy *>(this)); + } + + /// \brief Get the previous node, or \c nullptr for the list head. + const NodeTy *getPrevNode() const { + return const_cast<ilist_node_with_parent *>(this)->getPrevNode(); + } + + /// \brief Get the next node, or \c nullptr for the list tail. + NodeTy *getNextNode() { + // Should be separated to a reused function, but then we couldn't use auto + // (and would need the type of the list). + const auto &List = + getNodeParent()->*(ParentTy::getSublistAccess((NodeTy *)nullptr)); + return List.getNextNode(*static_cast<NodeTy *>(this)); + } + + /// \brief Get the next node, or \c nullptr for the list tail. + const NodeTy *getNextNode() const { + return const_cast<ilist_node_with_parent *>(this)->getNextNode(); + } + /// @} +}; + +} // end namespace llvm + +#endif // LLVM_ADT_ILIST_NODE_H diff --git a/src/3rdparty/llvm/include/llvm/ADT/ilist_node_base.h b/src/3rdparty/llvm/include/llvm/ADT/ilist_node_base.h new file mode 100644 index 0000000000..e5062ac4ea --- /dev/null +++ b/src/3rdparty/llvm/include/llvm/ADT/ilist_node_base.h @@ -0,0 +1,53 @@ +//===- llvm/ADT/ilist_node_base.h - Intrusive List Node Base -----*- C++ -*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_ILIST_NODE_BASE_H +#define LLVM_ADT_ILIST_NODE_BASE_H + +#include "llvm/ADT/PointerIntPair.h" + +namespace llvm { + +/// Base class for ilist nodes. +/// +/// Optionally tracks whether this node is the sentinel. +template <bool EnableSentinelTracking> class ilist_node_base; + +template <> class ilist_node_base<false> { + ilist_node_base *Prev = nullptr; + ilist_node_base *Next = nullptr; + +public: + void setPrev(ilist_node_base *Prev) { this->Prev = Prev; } + void setNext(ilist_node_base *Next) { this->Next = Next; } + ilist_node_base *getPrev() const { return Prev; } + ilist_node_base *getNext() const { return Next; } + + bool isKnownSentinel() const { return false; } + void initializeSentinel() {} +}; + +template <> class ilist_node_base<true> { + PointerIntPair<ilist_node_base *, 1> PrevAndSentinel; + ilist_node_base *Next = nullptr; + +public: + void setPrev(ilist_node_base *Prev) { PrevAndSentinel.setPointer(Prev); } + void setNext(ilist_node_base *Next) { this->Next = Next; } + ilist_node_base *getPrev() const { return PrevAndSentinel.getPointer(); } + ilist_node_base *getNext() const { return Next; } + + bool isSentinel() const { return PrevAndSentinel.getInt(); } + bool isKnownSentinel() const { return isSentinel(); } + void initializeSentinel() { PrevAndSentinel.setInt(true); } +}; + +} // end namespace llvm + +#endif // LLVM_ADT_ILIST_NODE_BASE_H diff --git a/src/3rdparty/llvm/include/llvm/ADT/ilist_node_options.h b/src/3rdparty/llvm/include/llvm/ADT/ilist_node_options.h new file mode 100644 index 0000000000..a09fdda31c --- /dev/null +++ b/src/3rdparty/llvm/include/llvm/ADT/ilist_node_options.h @@ -0,0 +1,133 @@ +//===- llvm/ADT/ilist_node_options.h - ilist_node Options -------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_ILIST_NODE_OPTIONS_H +#define LLVM_ADT_ILIST_NODE_OPTIONS_H + +//#include "llvm/Config/abi-breaking.h" +//#include "llvm/Config/llvm-config.h" + +#include <type_traits> + +namespace llvm { + +template <bool EnableSentinelTracking> class ilist_node_base; +template <bool EnableSentinelTracking> class ilist_base; + +/// Option to choose whether to track sentinels. +/// +/// This option affects the ABI for the nodes. When not specified explicitly, +/// the ABI depends on LLVM_ENABLE_ABI_BREAKING_CHECKS. Specify explicitly to +/// enable \a ilist_node::isSentinel(). +template <bool EnableSentinelTracking> struct ilist_sentinel_tracking {}; + +/// Option to specify a tag for the node type. +/// +/// This option allows a single value type to be inserted in multiple lists +/// simultaneously. See \a ilist_node for usage examples. +template <class Tag> struct ilist_tag {}; + +namespace ilist_detail { + +/// Helper trait for recording whether an option is specified explicitly. +template <bool IsExplicit> struct explicitness { + static const bool is_explicit = IsExplicit; +}; +typedef explicitness<true> is_explicit; +typedef explicitness<false> is_implicit; + +/// Check whether an option is valid. +/// +/// The steps for adding and enabling a new ilist option include: +/// \li define the option, ilist_foo<Bar>, above; +/// \li add new parameters for Bar to \a ilist_detail::node_options; +/// \li add an extraction meta-function, ilist_detail::extract_foo; +/// \li call extract_foo from \a ilist_detail::compute_node_options and pass it +/// into \a ilist_detail::node_options; and +/// \li specialize \c is_valid_option<ilist_foo<Bar>> to inherit from \c +/// std::true_type to get static assertions passing in \a simple_ilist and \a +/// ilist_node. +template <class Option> struct is_valid_option : std::false_type {}; + +/// Extract sentinel tracking option. +/// +/// Look through \p Options for the \a ilist_sentinel_tracking option, with the +/// default depending on LLVM_ENABLE_ABI_BREAKING_CHECKS. +template <class... Options> struct extract_sentinel_tracking; +template <bool EnableSentinelTracking, class... Options> +struct extract_sentinel_tracking< + ilist_sentinel_tracking<EnableSentinelTracking>, Options...> + : std::integral_constant<bool, EnableSentinelTracking>, is_explicit {}; +template <class Option1, class... Options> +struct extract_sentinel_tracking<Option1, Options...> + : extract_sentinel_tracking<Options...> {}; +#if LLVM_ENABLE_ABI_BREAKING_CHECKS +template <> struct extract_sentinel_tracking<> : std::true_type, is_implicit {}; +#else +template <> +struct extract_sentinel_tracking<> : std::false_type, is_implicit {}; +#endif +template <bool EnableSentinelTracking> +struct is_valid_option<ilist_sentinel_tracking<EnableSentinelTracking>> + : std::true_type {}; + +/// Extract custom tag option. +/// +/// Look through \p Options for the \a ilist_tag option, pulling out the +/// custom tag type, using void as a default. +template <class... Options> struct extract_tag; +template <class Tag, class... Options> +struct extract_tag<ilist_tag<Tag>, Options...> { + typedef Tag type; +}; +template <class Option1, class... Options> +struct extract_tag<Option1, Options...> : extract_tag<Options...> {}; +template <> struct extract_tag<> { typedef void type; }; +template <class Tag> struct is_valid_option<ilist_tag<Tag>> : std::true_type {}; + +/// Check whether options are valid. +/// +/// The conjunction of \a is_valid_option on each individual option. +template <class... Options> struct check_options; +template <> struct check_options<> : std::true_type {}; +template <class Option1, class... Options> +struct check_options<Option1, Options...> + : std::integral_constant<bool, is_valid_option<Option1>::value && + check_options<Options...>::value> {}; + +/// Traits for options for \a ilist_node. +/// +/// This is usually computed via \a compute_node_options. +template <class T, bool EnableSentinelTracking, bool IsSentinelTrackingExplicit, + class TagT> +struct node_options { + typedef T value_type; + typedef T *pointer; + typedef T &reference; + typedef const T *const_pointer; + typedef const T &const_reference; + + static const bool enable_sentinel_tracking = EnableSentinelTracking; + static const bool is_sentinel_tracking_explicit = IsSentinelTrackingExplicit; + typedef TagT tag; + typedef ilist_node_base<enable_sentinel_tracking> node_base_type; + typedef ilist_base<enable_sentinel_tracking> list_base_type; +}; + +template <class T, class... Options> struct compute_node_options { + typedef node_options<T, extract_sentinel_tracking<Options...>::value, + extract_sentinel_tracking<Options...>::is_explicit, + typename extract_tag<Options...>::type> + type; +}; + +} // end namespace ilist_detail +} // end namespace llvm + +#endif // LLVM_ADT_ILIST_NODE_OPTIONS_H diff --git a/src/3rdparty/llvm/include/llvm/ADT/iterator.h b/src/3rdparty/llvm/include/llvm/ADT/iterator.h new file mode 100644 index 0000000000..711f8f2216 --- /dev/null +++ b/src/3rdparty/llvm/include/llvm/ADT/iterator.h @@ -0,0 +1,339 @@ +//===- iterator.h - Utilities for using and defining iterators --*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_ITERATOR_H +#define LLVM_ADT_ITERATOR_H + +#include "llvm/ADT/iterator_range.h" +#include <algorithm> +#include <cstddef> +#include <iterator> +#include <type_traits> +#include <utility> + +namespace llvm { + +/// \brief CRTP base class which implements the entire standard iterator facade +/// in terms of a minimal subset of the interface. +/// +/// Use this when it is reasonable to implement most of the iterator +/// functionality in terms of a core subset. If you need special behavior or +/// there are performance implications for this, you may want to override the +/// relevant members instead. +/// +/// Note, one abstraction that this does *not* provide is implementing +/// subtraction in terms of addition by negating the difference. Negation isn't +/// always information preserving, and I can see very reasonable iterator +/// designs where this doesn't work well. It doesn't really force much added +/// boilerplate anyways. +/// +/// Another abstraction that this doesn't provide is implementing increment in +/// terms of addition of one. These aren't equivalent for all iterator +/// categories, and respecting that adds a lot of complexity for little gain. +/// +/// Classes wishing to use `iterator_facade_base` should implement the following +/// methods: +/// +/// Forward Iterators: +/// (All of the following methods) +/// - DerivedT &operator=(const DerivedT &R); +/// - bool operator==(const DerivedT &R) const; +/// - const T &operator*() const; +/// - T &operator*(); +/// - DerivedT &operator++(); +/// +/// Bidirectional Iterators: +/// (All methods of forward iterators, plus the following) +/// - DerivedT &operator--(); +/// +/// Random-access Iterators: +/// (All methods of bidirectional iterators excluding the following) +/// - DerivedT &operator++(); +/// - DerivedT &operator--(); +/// (and plus the following) +/// - bool operator<(const DerivedT &RHS) const; +/// - DifferenceTypeT operator-(const DerivedT &R) const; +/// - DerivedT &operator+=(DifferenceTypeT N); +/// - DerivedT &operator-=(DifferenceTypeT N); +/// +template <typename DerivedT, typename IteratorCategoryT, typename T, + typename DifferenceTypeT = std::ptrdiff_t, typename PointerT = T *, + typename ReferenceT = T &> +class iterator_facade_base + : public std::iterator<IteratorCategoryT, T, DifferenceTypeT, PointerT, + ReferenceT> { +protected: + enum { + IsRandomAccess = std::is_base_of<std::random_access_iterator_tag, + IteratorCategoryT>::value, + IsBidirectional = std::is_base_of<std::bidirectional_iterator_tag, + IteratorCategoryT>::value, + }; + + /// A proxy object for computing a reference via indirecting a copy of an + /// iterator. This is used in APIs which need to produce a reference via + /// indirection but for which the iterator object might be a temporary. The + /// proxy preserves the iterator internally and exposes the indirected + /// reference via a conversion operator. + class ReferenceProxy { + friend iterator_facade_base; + + DerivedT I; + + ReferenceProxy(DerivedT I) : I(std::move(I)) {} + + public: + operator ReferenceT() const { return *I; } + }; + +public: + DerivedT operator+(DifferenceTypeT n) const { + static_assert(std::is_base_of<iterator_facade_base, DerivedT>::value, + "Must pass the derived type to this template!"); + static_assert( + IsRandomAccess, + "The '+' operator is only defined for random access iterators."); + DerivedT tmp = *static_cast<const DerivedT *>(this); + tmp += n; + return tmp; + } + friend DerivedT operator+(DifferenceTypeT n, const DerivedT &i) { + static_assert( + IsRandomAccess, + "The '+' operator is only defined for random access iterators."); + return i + n; + } + DerivedT operator-(DifferenceTypeT n) const { + static_assert( + IsRandomAccess, + "The '-' operator is only defined for random access iterators."); + DerivedT tmp = *static_cast<const DerivedT *>(this); + tmp -= n; + return tmp; + } + + DerivedT &operator++() { + static_assert(std::is_base_of<iterator_facade_base, DerivedT>::value, + "Must pass the derived type to this template!"); + return static_cast<DerivedT *>(this)->operator+=(1); + } + DerivedT operator++(int) { + DerivedT tmp = *static_cast<DerivedT *>(this); + ++*static_cast<DerivedT *>(this); + return tmp; + } + DerivedT &operator--() { + static_assert( + IsBidirectional, + "The decrement operator is only defined for bidirectional iterators."); + return static_cast<DerivedT *>(this)->operator-=(1); + } + DerivedT operator--(int) { + static_assert( + IsBidirectional, + "The decrement operator is only defined for bidirectional iterators."); + DerivedT tmp = *static_cast<DerivedT *>(this); + --*static_cast<DerivedT *>(this); + return tmp; + } + + bool operator!=(const DerivedT &RHS) const { + return !static_cast<const DerivedT *>(this)->operator==(RHS); + } + + bool operator>(const DerivedT &RHS) const { + static_assert( + IsRandomAccess, + "Relational operators are only defined for random access iterators."); + return !static_cast<const DerivedT *>(this)->operator<(RHS) && + !static_cast<const DerivedT *>(this)->operator==(RHS); + } + bool operator<=(const DerivedT &RHS) const { + static_assert( + IsRandomAccess, + "Relational operators are only defined for random access iterators."); + return !static_cast<const DerivedT *>(this)->operator>(RHS); + } + bool operator>=(const DerivedT &RHS) const { + static_assert( + IsRandomAccess, + "Relational operators are only defined for random access iterators."); + return !static_cast<const DerivedT *>(this)->operator<(RHS); + } + + PointerT operator->() { return &static_cast<DerivedT *>(this)->operator*(); } + PointerT operator->() const { + return &static_cast<const DerivedT *>(this)->operator*(); + } + ReferenceProxy operator[](DifferenceTypeT n) { + static_assert(IsRandomAccess, + "Subscripting is only defined for random access iterators."); + return ReferenceProxy(static_cast<DerivedT *>(this)->operator+(n)); + } + ReferenceProxy operator[](DifferenceTypeT n) const { + static_assert(IsRandomAccess, + "Subscripting is only defined for random access iterators."); + return ReferenceProxy(static_cast<const DerivedT *>(this)->operator+(n)); + } +}; + +/// \brief CRTP base class for adapting an iterator to a different type. +/// +/// This class can be used through CRTP to adapt one iterator into another. +/// Typically this is done through providing in the derived class a custom \c +/// operator* implementation. Other methods can be overridden as well. +template < + typename DerivedT, typename WrappedIteratorT, + typename IteratorCategoryT = + typename std::iterator_traits<WrappedIteratorT>::iterator_category, + typename T = typename std::iterator_traits<WrappedIteratorT>::value_type, + typename DifferenceTypeT = + typename std::iterator_traits<WrappedIteratorT>::difference_type, + typename PointerT = typename std::conditional< + std::is_same<T, typename std::iterator_traits< + WrappedIteratorT>::value_type>::value, + typename std::iterator_traits<WrappedIteratorT>::pointer, T *>::type, + typename ReferenceT = typename std::conditional< + std::is_same<T, typename std::iterator_traits< + WrappedIteratorT>::value_type>::value, + typename std::iterator_traits<WrappedIteratorT>::reference, T &>::type, + // Don't provide these, they are mostly to act as aliases below. + typename WrappedTraitsT = std::iterator_traits<WrappedIteratorT>> +class iterator_adaptor_base + : public iterator_facade_base<DerivedT, IteratorCategoryT, T, + DifferenceTypeT, PointerT, ReferenceT> { + using BaseT = typename iterator_adaptor_base::iterator_facade_base; + +protected: + WrappedIteratorT I; + + iterator_adaptor_base() = default; + + explicit iterator_adaptor_base(WrappedIteratorT u) : I(std::move(u)) { + static_assert(std::is_base_of<iterator_adaptor_base, DerivedT>::value, + "Must pass the derived type to this template!"); + } + + const WrappedIteratorT &wrapped() const { return I; } + +public: + using difference_type = DifferenceTypeT; + + DerivedT &operator+=(difference_type n) { + static_assert( + BaseT::IsRandomAccess, + "The '+=' operator is only defined for random access iterators."); + I += n; + return *static_cast<DerivedT *>(this); + } + DerivedT &operator-=(difference_type n) { + static_assert( + BaseT::IsRandomAccess, + "The '-=' operator is only defined for random access iterators."); + I -= n; + return *static_cast<DerivedT *>(this); + } + using BaseT::operator-; + difference_type operator-(const DerivedT &RHS) const { + static_assert( + BaseT::IsRandomAccess, + "The '-' operator is only defined for random access iterators."); + return I - RHS.I; + } + + // We have to explicitly provide ++ and -- rather than letting the facade + // forward to += because WrappedIteratorT might not support +=. + using BaseT::operator++; + DerivedT &operator++() { + ++I; + return *static_cast<DerivedT *>(this); + } + using BaseT::operator--; + DerivedT &operator--() { + static_assert( + BaseT::IsBidirectional, + "The decrement operator is only defined for bidirectional iterators."); + --I; + return *static_cast<DerivedT *>(this); + } + + bool operator==(const DerivedT &RHS) const { return I == RHS.I; } + bool operator<(const DerivedT &RHS) const { + static_assert( + BaseT::IsRandomAccess, + "Relational operators are only defined for random access iterators."); + return I < RHS.I; + } + + ReferenceT operator*() const { return *I; } +}; + +/// \brief An iterator type that allows iterating over the pointees via some +/// other iterator. +/// +/// The typical usage of this is to expose a type that iterates over Ts, but +/// which is implemented with some iterator over T*s: +/// +/// \code +/// using iterator = pointee_iterator<SmallVectorImpl<T *>::iterator>; +/// \endcode +template <typename WrappedIteratorT, + typename T = typename std::remove_reference< + decltype(**std::declval<WrappedIteratorT>())>::type> +struct pointee_iterator + : iterator_adaptor_base< + pointee_iterator<WrappedIteratorT>, WrappedIteratorT, + typename std::iterator_traits<WrappedIteratorT>::iterator_category, + T> { + pointee_iterator() = default; + template <typename U> + pointee_iterator(U &&u) + : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {} + + T &operator*() const { return **this->I; } +}; + +template <typename RangeT, typename WrappedIteratorT = + decltype(std::begin(std::declval<RangeT>()))> +iterator_range<pointee_iterator<WrappedIteratorT>> +make_pointee_range(RangeT &&Range) { + using PointeeIteratorT = pointee_iterator<WrappedIteratorT>; + return make_range(PointeeIteratorT(std::begin(std::forward<RangeT>(Range))), + PointeeIteratorT(std::end(std::forward<RangeT>(Range)))); +} + +template <typename WrappedIteratorT, + typename T = decltype(&*std::declval<WrappedIteratorT>())> +class pointer_iterator + : public iterator_adaptor_base<pointer_iterator<WrappedIteratorT>, + WrappedIteratorT, T> { + mutable T Ptr; + +public: + pointer_iterator() = default; + + explicit pointer_iterator(WrappedIteratorT u) + : pointer_iterator::iterator_adaptor_base(std::move(u)) {} + + T &operator*() { return Ptr = &*this->I; } + const T &operator*() const { return Ptr = &*this->I; } +}; + +template <typename RangeT, typename WrappedIteratorT = + decltype(std::begin(std::declval<RangeT>()))> +iterator_range<pointer_iterator<WrappedIteratorT>> +make_pointer_range(RangeT &&Range) { + using PointerIteratorT = pointer_iterator<WrappedIteratorT>; + return make_range(PointerIteratorT(std::begin(std::forward<RangeT>(Range))), + PointerIteratorT(std::end(std::forward<RangeT>(Range)))); +} + +} // end namespace llvm + +#endif // LLVM_ADT_ITERATOR_H diff --git a/src/3rdparty/llvm/include/llvm/ADT/iterator_range.h b/src/3rdparty/llvm/include/llvm/ADT/iterator_range.h new file mode 100644 index 0000000000..3cbf6198eb --- /dev/null +++ b/src/3rdparty/llvm/include/llvm/ADT/iterator_range.h @@ -0,0 +1,68 @@ +//===- iterator_range.h - A range adaptor for iterators ---------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// This provides a very simple, boring adaptor for a begin and end iterator +/// into a range type. This should be used to build range views that work well +/// with range based for loops and range based constructors. +/// +/// Note that code here follows more standards-based coding conventions as it +/// is mirroring proposed interfaces for standardization. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_ITERATOR_RANGE_H +#define LLVM_ADT_ITERATOR_RANGE_H + +#include <iterator> +#include <utility> + +namespace llvm { + +/// \brief A range adaptor for a pair of iterators. +/// +/// This just wraps two iterators into a range-compatible interface. Nothing +/// fancy at all. +template <typename IteratorT> +class iterator_range { + IteratorT begin_iterator, end_iterator; + +public: + //TODO: Add SFINAE to test that the Container's iterators match the range's + // iterators. + template <typename Container> + iterator_range(Container &&c) + //TODO: Consider ADL/non-member begin/end calls. + : begin_iterator(c.begin()), end_iterator(c.end()) {} + iterator_range(IteratorT begin_iterator, IteratorT end_iterator) + : begin_iterator(std::move(begin_iterator)), + end_iterator(std::move(end_iterator)) {} + + IteratorT begin() const { return begin_iterator; } + IteratorT end() const { return end_iterator; } +}; + +/// \brief Convenience function for iterating over sub-ranges. +/// +/// This provides a bit of syntactic sugar to make using sub-ranges +/// in for loops a bit easier. Analogous to std::make_pair(). +template <class T> iterator_range<T> make_range(T x, T y) { + return iterator_range<T>(std::move(x), std::move(y)); +} + +template <typename T> iterator_range<T> make_range(std::pair<T, T> p) { + return iterator_range<T>(std::move(p.first), std::move(p.second)); +} + +template<typename T> +iterator_range<decltype(begin(std::declval<T>()))> drop_begin(T &&t, int n) { + return make_range(std::next(begin(t), n), end(t)); +} +} + +#endif diff --git a/src/3rdparty/llvm/include/llvm/ADT/simple_ilist.h b/src/3rdparty/llvm/include/llvm/ADT/simple_ilist.h new file mode 100644 index 0000000000..4c7598a1ac --- /dev/null +++ b/src/3rdparty/llvm/include/llvm/ADT/simple_ilist.h @@ -0,0 +1,315 @@ +//===- llvm/ADT/simple_ilist.h - Simple Intrusive List ----------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_SIMPLE_ILIST_H +#define LLVM_ADT_SIMPLE_ILIST_H + +#include "llvm/ADT/ilist_base.h" +#include "llvm/ADT/ilist_iterator.h" +#include "llvm/ADT/ilist_node.h" +#include "llvm/ADT/ilist_node_options.h" +#include "llvm/Support/Compiler.h" +#include <algorithm> +#include <cassert> +#include <cstddef> +#include <functional> +#include <iterator> +#include <utility> + +namespace llvm { + +/// A simple intrusive list implementation. +/// +/// This is a simple intrusive list for a \c T that inherits from \c +/// ilist_node<T>. The list never takes ownership of anything inserted in it. +/// +/// Unlike \a iplist<T> and \a ilist<T>, \a simple_ilist<T> never allocates or +/// deletes values, and has no callback traits. +/// +/// The API for adding nodes include \a push_front(), \a push_back(), and \a +/// insert(). These all take values by reference (not by pointer), except for +/// the range version of \a insert(). +/// +/// There are three sets of API for discarding nodes from the list: \a +/// remove(), which takes a reference to the node to remove, \a erase(), which +/// takes an iterator or iterator range and returns the next one, and \a +/// clear(), which empties out the container. All three are constant time +/// operations. None of these deletes any nodes; in particular, if there is a +/// single node in the list, then these have identical semantics: +/// \li \c L.remove(L.front()); +/// \li \c L.erase(L.begin()); +/// \li \c L.clear(); +/// +/// As a convenience for callers, there are parallel APIs that take a \c +/// Disposer (such as \c std::default_delete<T>): \a removeAndDispose(), \a +/// eraseAndDispose(), and \a clearAndDispose(). These have different names +/// because the extra semantic is otherwise non-obvious. They are equivalent +/// to calling \a std::for_each() on the range to be discarded. +/// +/// The currently available \p Options customize the nodes in the list. The +/// same options must be specified in the \a ilist_node instantation for +/// compatibility (although the order is irrelevant). +/// \li Use \a ilist_tag to designate which ilist_node for a given \p T this +/// list should use. This is useful if a type \p T is part of multiple, +/// independent lists simultaneously. +/// \li Use \a ilist_sentinel_tracking to always (or never) track whether a +/// node is a sentinel. Specifying \c true enables the \a +/// ilist_node::isSentinel() API. Unlike \a ilist_node::isKnownSentinel(), +/// which is only appropriate for assertions, \a ilist_node::isSentinel() is +/// appropriate for real logic. +/// +/// Here are examples of \p Options usage: +/// \li \c simple_ilist<T> gives the defaults. \li \c +/// simple_ilist<T,ilist_sentinel_tracking<true>> enables the \a +/// ilist_node::isSentinel() API. +/// \li \c simple_ilist<T,ilist_tag<A>,ilist_sentinel_tracking<false>> +/// specifies a tag of A and that tracking should be off (even when +/// LLVM_ENABLE_ABI_BREAKING_CHECKS are enabled). +/// \li \c simple_ilist<T,ilist_sentinel_tracking<false>,ilist_tag<A>> is +/// equivalent to the last. +/// +/// See \a is_valid_option for steps on adding a new option. +template <typename T, class... Options> +class simple_ilist + : ilist_detail::compute_node_options<T, Options...>::type::list_base_type, + ilist_detail::SpecificNodeAccess< + typename ilist_detail::compute_node_options<T, Options...>::type> { + static_assert(ilist_detail::check_options<Options...>::value, + "Unrecognized node option!"); + using OptionsT = + typename ilist_detail::compute_node_options<T, Options...>::type; + using list_base_type = typename OptionsT::list_base_type; + ilist_sentinel<OptionsT> Sentinel; + +public: + using value_type = typename OptionsT::value_type; + using pointer = typename OptionsT::pointer; + using reference = typename OptionsT::reference; + using const_pointer = typename OptionsT::const_pointer; + using const_reference = typename OptionsT::const_reference; + using iterator = ilist_iterator<OptionsT, false, false>; + using const_iterator = ilist_iterator<OptionsT, false, true>; + using reverse_iterator = ilist_iterator<OptionsT, true, false>; + using const_reverse_iterator = ilist_iterator<OptionsT, true, true>; + using size_type = size_t; + using difference_type = ptrdiff_t; + + simple_ilist() = default; + ~simple_ilist() = default; + + // No copy constructors. + simple_ilist(const simple_ilist &) = delete; + simple_ilist &operator=(const simple_ilist &) = delete; + + // Move constructors. + simple_ilist(simple_ilist &&X) { splice(end(), X); } + simple_ilist &operator=(simple_ilist &&X) { + clear(); + splice(end(), X); + return *this; + } + + iterator begin() { return ++iterator(Sentinel); } + const_iterator begin() const { return ++const_iterator(Sentinel); } + iterator end() { return iterator(Sentinel); } + const_iterator end() const { return const_iterator(Sentinel); } + reverse_iterator rbegin() { return ++reverse_iterator(Sentinel); } + const_reverse_iterator rbegin() const { + return ++const_reverse_iterator(Sentinel); + } + reverse_iterator rend() { return reverse_iterator(Sentinel); } + const_reverse_iterator rend() const { + return const_reverse_iterator(Sentinel); + } + + /// Check if the list is empty in constant time. + LLVM_NODISCARD bool empty() const { return Sentinel.empty(); } + + /// Calculate the size of the list in linear time. + LLVM_NODISCARD size_type size() const { + return std::distance(begin(), end()); + } + + reference front() { return *begin(); } + const_reference front() const { return *begin(); } + reference back() { return *rbegin(); } + const_reference back() const { return *rbegin(); } + + /// Insert a node at the front; never copies. + void push_front(reference Node) { insert(begin(), Node); } + + /// Insert a node at the back; never copies. + void push_back(reference Node) { insert(end(), Node); } + + /// Remove the node at the front; never deletes. + void pop_front() { erase(begin()); } + + /// Remove the node at the back; never deletes. + void pop_back() { erase(--end()); } + + /// Swap with another list in place using std::swap. + void swap(simple_ilist &X) { std::swap(*this, X); } + + /// Insert a node by reference; never copies. + iterator insert(iterator I, reference Node) { + list_base_type::insertBefore(*I.getNodePtr(), *this->getNodePtr(&Node)); + return iterator(&Node); + } + + /// Insert a range of nodes; never copies. + template <class Iterator> + void insert(iterator I, Iterator First, Iterator Last) { + for (; First != Last; ++First) + insert(I, *First); + } + + /// Clone another list. + template <class Cloner, class Disposer> + void cloneFrom(const simple_ilist &L2, Cloner clone, Disposer dispose) { + clearAndDispose(dispose); + for (const_reference V : L2) + push_back(*clone(V)); + } + + /// Remove a node by reference; never deletes. + /// + /// \see \a erase() for removing by iterator. + /// \see \a removeAndDispose() if the node should be deleted. + void remove(reference N) { list_base_type::remove(*this->getNodePtr(&N)); } + + /// Remove a node by reference and dispose of it. + template <class Disposer> + void removeAndDispose(reference N, Disposer dispose) { + remove(N); + dispose(&N); + } + + /// Remove a node by iterator; never deletes. + /// + /// \see \a remove() for removing by reference. + /// \see \a eraseAndDispose() it the node should be deleted. + iterator erase(iterator I) { + assert(I != end() && "Cannot remove end of list!"); + remove(*I++); + return I; + } + + /// Remove a range of nodes; never deletes. + /// + /// \see \a eraseAndDispose() if the nodes should be deleted. + iterator erase(iterator First, iterator Last) { + list_base_type::removeRange(*First.getNodePtr(), *Last.getNodePtr()); + return Last; + } + + /// Remove a node by iterator and dispose of it. + template <class Disposer> + iterator eraseAndDispose(iterator I, Disposer dispose) { + auto Next = std::next(I); + erase(I); + dispose(&*I); + return Next; + } + + /// Remove a range of nodes and dispose of them. + template <class Disposer> + iterator eraseAndDispose(iterator First, iterator Last, Disposer dispose) { + while (First != Last) + First = eraseAndDispose(First, dispose); + return Last; + } + + /// Clear the list; never deletes. + /// + /// \see \a clearAndDispose() if the nodes should be deleted. + void clear() { Sentinel.reset(); } + + /// Clear the list and dispose of the nodes. + template <class Disposer> void clearAndDispose(Disposer dispose) { + eraseAndDispose(begin(), end(), dispose); + } + + /// Splice in another list. + void splice(iterator I, simple_ilist &L2) { + splice(I, L2, L2.begin(), L2.end()); + } + + /// Splice in a node from another list. + void splice(iterator I, simple_ilist &L2, iterator Node) { + splice(I, L2, Node, std::next(Node)); + } + + /// Splice in a range of nodes from another list. + void splice(iterator I, simple_ilist &, iterator First, iterator Last) { + list_base_type::transferBefore(*I.getNodePtr(), *First.getNodePtr(), + *Last.getNodePtr()); + } + + /// Merge in another list. + /// + /// \pre \c this and \p RHS are sorted. + ///@{ + void merge(simple_ilist &RHS) { merge(RHS, std::less<T>()); } + template <class Compare> void merge(simple_ilist &RHS, Compare comp); + ///@} + + /// Sort the list. + ///@{ + void sort() { sort(std::less<T>()); } + template <class Compare> void sort(Compare comp); + ///@} +}; + +template <class T, class... Options> +template <class Compare> +void simple_ilist<T, Options...>::merge(simple_ilist &RHS, Compare comp) { + if (this == &RHS || RHS.empty()) + return; + iterator LI = begin(), LE = end(); + iterator RI = RHS.begin(), RE = RHS.end(); + while (LI != LE) { + if (comp(*RI, *LI)) { + // Transfer a run of at least size 1 from RHS to LHS. + iterator RunStart = RI++; + RI = std::find_if(RI, RE, [&](reference RV) { return !comp(RV, *LI); }); + splice(LI, RHS, RunStart, RI); + if (RI == RE) + return; + } + ++LI; + } + // Transfer the remaining RHS nodes once LHS is finished. + splice(LE, RHS, RI, RE); +} + +template <class T, class... Options> +template <class Compare> +void simple_ilist<T, Options...>::sort(Compare comp) { + // Vacuously sorted. + if (empty() || std::next(begin()) == end()) + return; + + // Split the list in the middle. + iterator Center = begin(), End = begin(); + while (End != end() && ++End != end()) { + ++Center; + ++End; + } + simple_ilist RHS; + RHS.splice(RHS.end(), *this, Center, end()); + + // Sort the sublists and merge back together. + sort(comp); + RHS.sort(comp); + merge(RHS, comp); +} + +} // end namespace llvm + +#endif // LLVM_ADT_SIMPLE_ILIST_H diff --git a/src/3rdparty/llvm/include/llvm/Demangle/Compiler.h b/src/3rdparty/llvm/include/llvm/Demangle/Compiler.h new file mode 100644 index 0000000000..963482c64f --- /dev/null +++ b/src/3rdparty/llvm/include/llvm/Demangle/Compiler.h @@ -0,0 +1,524 @@ +//===-- llvm/Demangle/Compiler.h - Compiler abstraction support -*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines several macros, based on the current compiler. This allows +// use of compiler-specific features in a way that remains portable. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_SUPPORT_COMPILER_H +#define LLVM_SUPPORT_COMPILER_H + +//#include "llvm/Config/llvm-config.h" + +#if defined(_MSC_VER) +#include <sal.h> +#endif + +#ifndef __has_feature +# define __has_feature(x) 0 +#endif + +#ifndef __has_extension +# define __has_extension(x) 0 +#endif + +#ifndef __has_attribute +# define __has_attribute(x) 0 +#endif + +#ifndef __has_cpp_attribute +# define __has_cpp_attribute(x) 0 +#endif + +#ifndef __has_builtin +# define __has_builtin(x) 0 +#endif + +/// \macro LLVM_GNUC_PREREQ +/// \brief Extend the default __GNUC_PREREQ even if glibc's features.h isn't +/// available. +#ifndef LLVM_GNUC_PREREQ +# if defined(__GNUC__) && defined(__GNUC_MINOR__) && defined(__GNUC_PATCHLEVEL__) +# define LLVM_GNUC_PREREQ(maj, min, patch) \ + ((__GNUC__ << 20) + (__GNUC_MINOR__ << 10) + __GNUC_PATCHLEVEL__ >= \ + ((maj) << 20) + ((min) << 10) + (patch)) +# elif defined(__GNUC__) && defined(__GNUC_MINOR__) +# define LLVM_GNUC_PREREQ(maj, min, patch) \ + ((__GNUC__ << 20) + (__GNUC_MINOR__ << 10) >= ((maj) << 20) + ((min) << 10)) +# else +# define LLVM_GNUC_PREREQ(maj, min, patch) 0 +# endif +#endif + +/// \macro LLVM_MSC_PREREQ +/// \brief Is the compiler MSVC of at least the specified version? +/// The common \param version values to check for are: +/// * 1900: Microsoft Visual Studio 2015 / 14.0 +#ifdef _MSC_VER +#define LLVM_MSC_PREREQ(version) (_MSC_VER >= (version)) + +// We require at least MSVC 2015. +#if !LLVM_MSC_PREREQ(1900) +#error LLVM requires at least MSVC 2015. +#endif + +#else +#define LLVM_MSC_PREREQ(version) 0 +#endif + +/// \brief Does the compiler support ref-qualifiers for *this? +/// +/// Sadly, this is separate from just rvalue reference support because GCC +/// and MSVC implemented this later than everything else. +#if __has_feature(cxx_rvalue_references) || LLVM_GNUC_PREREQ(4, 8, 1) +#define LLVM_HAS_RVALUE_REFERENCE_THIS 1 +#else +#define LLVM_HAS_RVALUE_REFERENCE_THIS 0 +#endif + +/// Expands to '&' if ref-qualifiers for *this are supported. +/// +/// This can be used to provide lvalue/rvalue overrides of member functions. +/// The rvalue override should be guarded by LLVM_HAS_RVALUE_REFERENCE_THIS +#if LLVM_HAS_RVALUE_REFERENCE_THIS +#define LLVM_LVALUE_FUNCTION & +#else +#define LLVM_LVALUE_FUNCTION +#endif + +/// LLVM_LIBRARY_VISIBILITY - If a class marked with this attribute is linked +/// into a shared library, then the class should be private to the library and +/// not accessible from outside it. Can also be used to mark variables and +/// functions, making them private to any shared library they are linked into. +/// On PE/COFF targets, library visibility is the default, so this isn't needed. +#if (__has_attribute(visibility) || LLVM_GNUC_PREREQ(4, 0, 0)) && \ + !defined(__MINGW32__) && !defined(__CYGWIN__) && !defined(LLVM_ON_WIN32) +#define LLVM_LIBRARY_VISIBILITY __attribute__ ((visibility("hidden"))) +#else +#define LLVM_LIBRARY_VISIBILITY +#endif + +#if defined(__GNUC__) +#define LLVM_PREFETCH(addr, rw, locality) __builtin_prefetch(addr, rw, locality) +#else +#define LLVM_PREFETCH(addr, rw, locality) +#endif + +#if __has_attribute(used) || LLVM_GNUC_PREREQ(3, 1, 0) +#define LLVM_ATTRIBUTE_USED __attribute__((__used__)) +#else +#define LLVM_ATTRIBUTE_USED +#endif + +/// LLVM_NODISCARD - Warn if a type or return value is discarded. +#if __cplusplus > 201402L && __has_cpp_attribute(nodiscard) +#define LLVM_NODISCARD [[nodiscard]] +#elif !__cplusplus +// Workaround for llvm.org/PR23435, since clang 3.6 and below emit a spurious +// error when __has_cpp_attribute is given a scoped attribute in C mode. +#define LLVM_NODISCARD +#elif __has_cpp_attribute(clang::warn_unused_result) +#define LLVM_NODISCARD [[clang::warn_unused_result]] +#else +#define LLVM_NODISCARD +#endif + +// Some compilers warn about unused functions. When a function is sometimes +// used or not depending on build settings (e.g. a function only called from +// within "assert"), this attribute can be used to suppress such warnings. +// +// However, it shouldn't be used for unused *variables*, as those have a much +// more portable solution: +// (void)unused_var_name; +// Prefer cast-to-void wherever it is sufficient. +#if __has_attribute(unused) || LLVM_GNUC_PREREQ(3, 1, 0) +#define LLVM_ATTRIBUTE_UNUSED __attribute__((__unused__)) +#else +#define LLVM_ATTRIBUTE_UNUSED +#endif + +// FIXME: Provide this for PE/COFF targets. +#if (__has_attribute(weak) || LLVM_GNUC_PREREQ(4, 0, 0)) && \ + (!defined(__MINGW32__) && !defined(__CYGWIN__) && !defined(LLVM_ON_WIN32)) +#define LLVM_ATTRIBUTE_WEAK __attribute__((__weak__)) +#else +#define LLVM_ATTRIBUTE_WEAK +#endif + +// Prior to clang 3.2, clang did not accept any spelling of +// __has_attribute(const), so assume it is supported. +#if defined(__clang__) || defined(__GNUC__) +// aka 'CONST' but following LLVM Conventions. +#define LLVM_READNONE __attribute__((__const__)) +#else +#define LLVM_READNONE +#endif + +#if __has_attribute(pure) || defined(__GNUC__) +// aka 'PURE' but following LLVM Conventions. +#define LLVM_READONLY __attribute__((__pure__)) +#else +#define LLVM_READONLY +#endif + +#if __has_builtin(__builtin_expect) || LLVM_GNUC_PREREQ(4, 0, 0) +#define LLVM_LIKELY(EXPR) __builtin_expect((bool)(EXPR), true) +#define LLVM_UNLIKELY(EXPR) __builtin_expect((bool)(EXPR), false) +#else +#define LLVM_LIKELY(EXPR) (EXPR) +#define LLVM_UNLIKELY(EXPR) (EXPR) +#endif + +/// LLVM_ATTRIBUTE_NOINLINE - On compilers where we have a directive to do so, +/// mark a method "not for inlining". +#if __has_attribute(noinline) || LLVM_GNUC_PREREQ(3, 4, 0) +#define LLVM_ATTRIBUTE_NOINLINE __attribute__((noinline)) +#elif defined(_MSC_VER) +#define LLVM_ATTRIBUTE_NOINLINE __declspec(noinline) +#else +#define LLVM_ATTRIBUTE_NOINLINE +#endif + +/// LLVM_ATTRIBUTE_ALWAYS_INLINE - On compilers where we have a directive to do +/// so, mark a method "always inline" because it is performance sensitive. GCC +/// 3.4 supported this but is buggy in various cases and produces unimplemented +/// errors, just use it in GCC 4.0 and later. +#if __has_attribute(always_inline) || LLVM_GNUC_PREREQ(4, 0, 0) +#define LLVM_ATTRIBUTE_ALWAYS_INLINE __attribute__((always_inline)) +#elif defined(_MSC_VER) +#define LLVM_ATTRIBUTE_ALWAYS_INLINE __forceinline +#else +#define LLVM_ATTRIBUTE_ALWAYS_INLINE +#endif + +#ifdef __GNUC__ +#define LLVM_ATTRIBUTE_NORETURN __attribute__((noreturn)) +#elif defined(_MSC_VER) +#define LLVM_ATTRIBUTE_NORETURN __declspec(noreturn) +#else +#define LLVM_ATTRIBUTE_NORETURN +#endif + +#if __has_attribute(returns_nonnull) || LLVM_GNUC_PREREQ(4, 9, 0) +#define LLVM_ATTRIBUTE_RETURNS_NONNULL __attribute__((returns_nonnull)) +#elif defined(_MSC_VER) +#define LLVM_ATTRIBUTE_RETURNS_NONNULL _Ret_notnull_ +#else +#define LLVM_ATTRIBUTE_RETURNS_NONNULL +#endif + +/// \macro LLVM_ATTRIBUTE_RETURNS_NOALIAS Used to mark a function as returning a +/// pointer that does not alias any other valid pointer. +#ifdef __GNUC__ +#define LLVM_ATTRIBUTE_RETURNS_NOALIAS __attribute__((__malloc__)) +#elif defined(_MSC_VER) +#define LLVM_ATTRIBUTE_RETURNS_NOALIAS __declspec(restrict) +#else +#define LLVM_ATTRIBUTE_RETURNS_NOALIAS +#endif + +/// LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements. +#if __cplusplus > 201402L && __has_cpp_attribute(fallthrough) +#define LLVM_FALLTHROUGH [[fallthrough]] +#elif __has_cpp_attribute(gnu::fallthrough) +#define LLVM_FALLTHROUGH [[gnu::fallthrough]] +#elif !__cplusplus +// Workaround for llvm.org/PR23435, since clang 3.6 and below emit a spurious +// error when __has_cpp_attribute is given a scoped attribute in C mode. +#define LLVM_FALLTHROUGH +#elif __has_cpp_attribute(clang::fallthrough) +#define LLVM_FALLTHROUGH [[clang::fallthrough]] +#else +#define LLVM_FALLTHROUGH +#endif + +/// LLVM_EXTENSION - Support compilers where we have a keyword to suppress +/// pedantic diagnostics. +#ifdef __GNUC__ +#define LLVM_EXTENSION __extension__ +#else +#define LLVM_EXTENSION +#endif + +// LLVM_ATTRIBUTE_DEPRECATED(decl, "message") +#if __has_feature(attribute_deprecated_with_message) +# define LLVM_ATTRIBUTE_DEPRECATED(decl, message) \ + decl __attribute__((deprecated(message))) +#elif defined(__GNUC__) +# define LLVM_ATTRIBUTE_DEPRECATED(decl, message) \ + decl __attribute__((deprecated)) +#elif defined(_MSC_VER) +# define LLVM_ATTRIBUTE_DEPRECATED(decl, message) \ + __declspec(deprecated(message)) decl +#else +# define LLVM_ATTRIBUTE_DEPRECATED(decl, message) \ + decl +#endif + +/// LLVM_BUILTIN_UNREACHABLE - On compilers which support it, expands +/// to an expression which states that it is undefined behavior for the +/// compiler to reach this point. Otherwise is not defined. +#if __has_builtin(__builtin_unreachable) || LLVM_GNUC_PREREQ(4, 5, 0) +# define LLVM_BUILTIN_UNREACHABLE __builtin_unreachable() +#elif defined(_MSC_VER) +# define LLVM_BUILTIN_UNREACHABLE __assume(false) +#endif + +/// LLVM_BUILTIN_TRAP - On compilers which support it, expands to an expression +/// which causes the program to exit abnormally. +#if __has_builtin(__builtin_trap) || LLVM_GNUC_PREREQ(4, 3, 0) +# define LLVM_BUILTIN_TRAP __builtin_trap() +#elif defined(_MSC_VER) +// The __debugbreak intrinsic is supported by MSVC, does not require forward +// declarations involving platform-specific typedefs (unlike RaiseException), +// results in a call to vectored exception handlers, and encodes to a short +// instruction that still causes the trapping behavior we want. +# define LLVM_BUILTIN_TRAP __debugbreak() +#else +# define LLVM_BUILTIN_TRAP *(volatile int*)0x11 = 0 +#endif + +/// LLVM_BUILTIN_DEBUGTRAP - On compilers which support it, expands to +/// an expression which causes the program to break while running +/// under a debugger. +#if __has_builtin(__builtin_debugtrap) +# define LLVM_BUILTIN_DEBUGTRAP __builtin_debugtrap() +#elif defined(_MSC_VER) +// The __debugbreak intrinsic is supported by MSVC and breaks while +// running under the debugger, and also supports invoking a debugger +// when the OS is configured appropriately. +# define LLVM_BUILTIN_DEBUGTRAP __debugbreak() +#else +// Just continue execution when built with compilers that have no +// support. This is a debugging aid and not intended to force the +// program to abort if encountered. +# define LLVM_BUILTIN_DEBUGTRAP +#endif + +/// \macro LLVM_ASSUME_ALIGNED +/// \brief Returns a pointer with an assumed alignment. +#if __has_builtin(__builtin_assume_aligned) || LLVM_GNUC_PREREQ(4, 7, 0) +# define LLVM_ASSUME_ALIGNED(p, a) __builtin_assume_aligned(p, a) +#elif defined(LLVM_BUILTIN_UNREACHABLE) +// As of today, clang does not support __builtin_assume_aligned. +# define LLVM_ASSUME_ALIGNED(p, a) \ + (((uintptr_t(p) % (a)) == 0) ? (p) : (LLVM_BUILTIN_UNREACHABLE, (p))) +#else +# define LLVM_ASSUME_ALIGNED(p, a) (p) +#endif + +/// \macro LLVM_ALIGNAS +/// \brief Used to specify a minimum alignment for a structure or variable. +#if __GNUC__ && !__has_feature(cxx_alignas) && !LLVM_GNUC_PREREQ(4, 8, 1) +# define LLVM_ALIGNAS(x) __attribute__((aligned(x))) +#else +# define LLVM_ALIGNAS(x) alignas(x) +#endif + +/// \macro LLVM_PACKED +/// \brief Used to specify a packed structure. +/// LLVM_PACKED( +/// struct A { +/// int i; +/// int j; +/// int k; +/// long long l; +/// }); +/// +/// LLVM_PACKED_START +/// struct B { +/// int i; +/// int j; +/// int k; +/// long long l; +/// }; +/// LLVM_PACKED_END +#ifdef _MSC_VER +# define LLVM_PACKED(d) __pragma(pack(push, 1)) d __pragma(pack(pop)) +# define LLVM_PACKED_START __pragma(pack(push, 1)) +# define LLVM_PACKED_END __pragma(pack(pop)) +#else +# define LLVM_PACKED(d) d __attribute__((packed)) +# define LLVM_PACKED_START _Pragma("pack(push, 1)") +# define LLVM_PACKED_END _Pragma("pack(pop)") +#endif + +/// \macro LLVM_PTR_SIZE +/// \brief A constant integer equivalent to the value of sizeof(void*). +/// Generally used in combination with LLVM_ALIGNAS or when doing computation in +/// the preprocessor. +#ifdef __SIZEOF_POINTER__ +# define LLVM_PTR_SIZE __SIZEOF_POINTER__ +#elif defined(_WIN64) +# define LLVM_PTR_SIZE 8 +#elif defined(_WIN32) +# define LLVM_PTR_SIZE 4 +#elif defined(_MSC_VER) +# error "could not determine LLVM_PTR_SIZE as a constant int for MSVC" +#else +# define LLVM_PTR_SIZE sizeof(void *) +#endif + +/// \macro LLVM_MEMORY_SANITIZER_BUILD +/// \brief Whether LLVM itself is built with MemorySanitizer instrumentation. +#if __has_feature(memory_sanitizer) +# define LLVM_MEMORY_SANITIZER_BUILD 1 +# include <sanitizer/msan_interface.h> +#else +# define LLVM_MEMORY_SANITIZER_BUILD 0 +# define __msan_allocated_memory(p, size) +# define __msan_unpoison(p, size) +#endif + +/// \macro LLVM_ADDRESS_SANITIZER_BUILD +/// \brief Whether LLVM itself is built with AddressSanitizer instrumentation. +#if __has_feature(address_sanitizer) || defined(__SANITIZE_ADDRESS__) +# define LLVM_ADDRESS_SANITIZER_BUILD 1 +# include <sanitizer/asan_interface.h> +#else +# define LLVM_ADDRESS_SANITIZER_BUILD 0 +# define __asan_poison_memory_region(p, size) +# define __asan_unpoison_memory_region(p, size) +#endif + +/// \macro LLVM_THREAD_SANITIZER_BUILD +/// \brief Whether LLVM itself is built with ThreadSanitizer instrumentation. +#if __has_feature(thread_sanitizer) || defined(__SANITIZE_THREAD__) +# define LLVM_THREAD_SANITIZER_BUILD 1 +#else +# define LLVM_THREAD_SANITIZER_BUILD 0 +#endif + +#if LLVM_THREAD_SANITIZER_BUILD +// Thread Sanitizer is a tool that finds races in code. +// See http://code.google.com/p/data-race-test/wiki/DynamicAnnotations . +// tsan detects these exact functions by name. +#ifdef __cplusplus +extern "C" { +#endif +void AnnotateHappensAfter(const char *file, int line, const volatile void *cv); +void AnnotateHappensBefore(const char *file, int line, const volatile void *cv); +void AnnotateIgnoreWritesBegin(const char *file, int line); +void AnnotateIgnoreWritesEnd(const char *file, int line); +#ifdef __cplusplus +} +#endif + +// This marker is used to define a happens-before arc. The race detector will +// infer an arc from the begin to the end when they share the same pointer +// argument. +# define TsanHappensBefore(cv) AnnotateHappensBefore(__FILE__, __LINE__, cv) + +// This marker defines the destination of a happens-before arc. +# define TsanHappensAfter(cv) AnnotateHappensAfter(__FILE__, __LINE__, cv) + +// Ignore any races on writes between here and the next TsanIgnoreWritesEnd. +# define TsanIgnoreWritesBegin() AnnotateIgnoreWritesBegin(__FILE__, __LINE__) + +// Resume checking for racy writes. +# define TsanIgnoreWritesEnd() AnnotateIgnoreWritesEnd(__FILE__, __LINE__) +#else +# define TsanHappensBefore(cv) +# define TsanHappensAfter(cv) +# define TsanIgnoreWritesBegin() +# define TsanIgnoreWritesEnd() +#endif + +/// \macro LLVM_NO_SANITIZE +/// \brief Disable a particular sanitizer for a function. +#if __has_attribute(no_sanitize) +#define LLVM_NO_SANITIZE(KIND) __attribute__((no_sanitize(KIND))) +#else +#define LLVM_NO_SANITIZE(KIND) +#endif + +/// \brief Mark debug helper function definitions like dump() that should not be +/// stripped from debug builds. +/// Note that you should also surround dump() functions with +/// `#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)` so they do always +/// get stripped in release builds. +// FIXME: Move this to a private config.h as it's not usable in public headers. +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +#define LLVM_DUMP_METHOD LLVM_ATTRIBUTE_NOINLINE LLVM_ATTRIBUTE_USED +#else +#define LLVM_DUMP_METHOD LLVM_ATTRIBUTE_NOINLINE +#endif + +/// \macro LLVM_PRETTY_FUNCTION +/// \brief Gets a user-friendly looking function signature for the current scope +/// using the best available method on each platform. The exact format of the +/// resulting string is implementation specific and non-portable, so this should +/// only be used, for example, for logging or diagnostics. +#if defined(_MSC_VER) +#define LLVM_PRETTY_FUNCTION __FUNCSIG__ +#elif defined(__GNUC__) || defined(__clang__) +#define LLVM_PRETTY_FUNCTION __PRETTY_FUNCTION__ +#else +#define LLVM_PRETTY_FUNCTION __func__ +#endif + +/// \macro LLVM_THREAD_LOCAL +/// \brief A thread-local storage specifier which can be used with globals, +/// extern globals, and static globals. +/// +/// This is essentially an extremely restricted analog to C++11's thread_local +/// support, and uses that when available. However, it falls back on +/// platform-specific or vendor-provided extensions when necessary. These +/// extensions don't support many of the C++11 thread_local's features. You +/// should only use this for PODs that you can statically initialize to +/// some constant value. In almost all circumstances this is most appropriate +/// for use with a pointer, integer, or small aggregation of pointers and +/// integers. +#if LLVM_ENABLE_THREADS +#if __has_feature(cxx_thread_local) +#define LLVM_THREAD_LOCAL thread_local +#elif defined(_MSC_VER) +// MSVC supports this with a __declspec. +#define LLVM_THREAD_LOCAL __declspec(thread) +#else +// Clang, GCC, and other compatible compilers used __thread prior to C++11 and +// we only need the restricted functionality that provides. +#define LLVM_THREAD_LOCAL __thread +#endif +#else // !LLVM_ENABLE_THREADS +// If threading is disabled entirely, this compiles to nothing and you get +// a normal global variable. +#define LLVM_THREAD_LOCAL +#endif + +/// \macro LLVM_ENABLE_EXCEPTIONS +/// \brief Whether LLVM is built with exception support. +#if __has_feature(cxx_exceptions) +#define LLVM_ENABLE_EXCEPTIONS 1 +#elif defined(__GNUC__) && defined(__EXCEPTIONS) +#define LLVM_ENABLE_EXCEPTIONS 1 +#elif defined(_MSC_VER) && defined(_CPPUNWIND) +#define LLVM_ENABLE_EXCEPTIONS 1 +#endif + +/// \macro LLVM_PLUGIN_IMPORT +/// \brief Used to import the well-known entry point for registering loaded pass +/// plugins +#ifdef WIN32 +#define LLVM_PLUGIN_IMPORT __declspec(dllimport) +#else +#define LLVM_PLUGIN_IMPORT +#endif + +/// \macro LLVM_PLUGIN_EXPORT +/// \brief Used to export the well-known entry point for registering loaded pass +/// plugins +#ifdef WIN32 +#define LLVM_PLUGIN_EXPORT __declspec(dllexport) +#else +#define LLVM_PLUGIN_EXPORT +#endif + +#endif diff --git a/src/3rdparty/llvm/include/llvm/Support/Compiler.h b/src/3rdparty/llvm/include/llvm/Support/Compiler.h new file mode 100644 index 0000000000..43a96e49ce --- /dev/null +++ b/src/3rdparty/llvm/include/llvm/Support/Compiler.h @@ -0,0 +1,19 @@ +//===-- llvm/Support/Compiler.h - Compiler abstraction support --*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Due to layering constraints (Support depends on Demangler) this is a thin +// wrapper around the implementation that lives in llvm-c, though most clients +// can/should think of this as being provided by Support for simplicity (not +// many clients are aware of their dependency on Demangler/it's a weird place to +// own this - but didn't seem to justify splitting Support into "lower support" +// and "upper support"). +// +//===----------------------------------------------------------------------===// + +#include "llvm/Demangle/Compiler.h" diff --git a/src/3rdparty/llvm/include/llvm/Support/DataTypes.h b/src/3rdparty/llvm/include/llvm/Support/DataTypes.h new file mode 100644 index 0000000000..ad60a5b3f3 --- /dev/null +++ b/src/3rdparty/llvm/include/llvm/Support/DataTypes.h @@ -0,0 +1,17 @@ +//===-- llvm/Support/DataTypes.h - Define fixed size types ------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Due to layering constraints (Support depends on llvm-c) this is a thin +// wrapper around the implementation that lives in llvm-c, though most clients +// can/should think of this as being provided by Support for simplicity (not +// many clients are aware of their dependency on llvm-c). +// +//===----------------------------------------------------------------------===// + +#include "llvm-c/DataTypes.h" diff --git a/src/3rdparty/llvm/include/llvm/Support/PointerLikeTypeTraits.h b/src/3rdparty/llvm/include/llvm/Support/PointerLikeTypeTraits.h new file mode 100644 index 0000000000..794230d606 --- /dev/null +++ b/src/3rdparty/llvm/include/llvm/Support/PointerLikeTypeTraits.h @@ -0,0 +1,116 @@ +//===- llvm/Support/PointerLikeTypeTraits.h - Pointer Traits ----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the PointerLikeTypeTraits class. This allows data +// structures to reason about pointers and other things that are pointer sized. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_SUPPORT_POINTERLIKETYPETRAITS_H +#define LLVM_SUPPORT_POINTERLIKETYPETRAITS_H + +#include "llvm/Support/DataTypes.h" +#include <type_traits> + +namespace llvm { + +/// A traits type that is used to handle pointer types and things that are just +/// wrappers for pointers as a uniform entity. +template <typename T> struct PointerLikeTypeTraits; + +namespace detail { +/// A tiny meta function to compute the log2 of a compile time constant. +template <size_t N> +struct ConstantLog2 + : std::integral_constant<size_t, ConstantLog2<N / 2>::value + 1> {}; +template <> struct ConstantLog2<1> : std::integral_constant<size_t, 0> {}; + +// Provide a trait to check if T is pointer-like. +template <typename T, typename U = void> struct HasPointerLikeTypeTraits { + static const bool value = false; +}; + +// sizeof(T) is valid only for a complete T. +template <typename T> struct HasPointerLikeTypeTraits< + T, decltype((sizeof(PointerLikeTypeTraits<T>) + sizeof(T)), void())> { + static const bool value = true; +}; + +template <typename T> struct IsPointerLike { + static const bool value = HasPointerLikeTypeTraits<T>::value; +}; + +template <typename T> struct IsPointerLike<T *> { + static const bool value = true; +}; +} // namespace detail + +// Provide PointerLikeTypeTraits for non-cvr pointers. +template <typename T> struct PointerLikeTypeTraits<T *> { + static inline void *getAsVoidPointer(T *P) { return P; } + static inline T *getFromVoidPointer(void *P) { return static_cast<T *>(P); } + + enum { NumLowBitsAvailable = detail::ConstantLog2<alignof(T)>::value }; +}; + +template <> struct PointerLikeTypeTraits<void *> { + static inline void *getAsVoidPointer(void *P) { return P; } + static inline void *getFromVoidPointer(void *P) { return P; } + + /// Note, we assume here that void* is related to raw malloc'ed memory and + /// that malloc returns objects at least 4-byte aligned. However, this may be + /// wrong, or pointers may be from something other than malloc. In this case, + /// you should specify a real typed pointer or avoid this template. + /// + /// All clients should use assertions to do a run-time check to ensure that + /// this is actually true. + enum { NumLowBitsAvailable = 2 }; +}; + +// Provide PointerLikeTypeTraits for const things. +template <typename T> struct PointerLikeTypeTraits<const T> { + typedef PointerLikeTypeTraits<T> NonConst; + + static inline const void *getAsVoidPointer(const T P) { + return NonConst::getAsVoidPointer(P); + } + static inline const T getFromVoidPointer(const void *P) { + return NonConst::getFromVoidPointer(const_cast<void *>(P)); + } + enum { NumLowBitsAvailable = NonConst::NumLowBitsAvailable }; +}; + +// Provide PointerLikeTypeTraits for const pointers. +template <typename T> struct PointerLikeTypeTraits<const T *> { + typedef PointerLikeTypeTraits<T *> NonConst; + + static inline const void *getAsVoidPointer(const T *P) { + return NonConst::getAsVoidPointer(const_cast<T *>(P)); + } + static inline const T *getFromVoidPointer(const void *P) { + return NonConst::getFromVoidPointer(const_cast<void *>(P)); + } + enum { NumLowBitsAvailable = NonConst::NumLowBitsAvailable }; +}; + +// Provide PointerLikeTypeTraits for uintptr_t. +template <> struct PointerLikeTypeTraits<uintptr_t> { + static inline void *getAsVoidPointer(uintptr_t P) { + return reinterpret_cast<void *>(P); + } + static inline uintptr_t getFromVoidPointer(void *P) { + return reinterpret_cast<uintptr_t>(P); + } + // No bits are available! + enum { NumLowBitsAvailable = 0 }; +}; + +} // end namespace llvm + +#endif diff --git a/src/3rdparty/llvm/llvm.pri b/src/3rdparty/llvm/llvm.pri new file mode 100644 index 0000000000..6b3b0689ec --- /dev/null +++ b/src/3rdparty/llvm/llvm.pri @@ -0,0 +1,18 @@ +INCLUDEPATH += $$PWD/include + +HEADERS += \ + $$PWD/include/llvm/ADT/ilist_node.h \ + $$PWD/include/llvm/ADT/iterator_range.h \ + $$PWD/include/llvm/ADT/simple_ilist.h \ + $$PWD/include/llvm/ADT/ilist_base.h \ + $$PWD/include/llvm/ADT/ilist_node_options.h \ + $$PWD/include/llvm/ADT/ilist_iterator.h \ + $$PWD/include/llvm/ADT/ilist_node_base.h \ + $$PWD/include/llvm/ADT/PointerIntPair.h \ + $$PWD/include/llvm/ADT/iterator.h \ + $$PWD/include/llvm/ADT/ilist.h \ + $$PWD/include/llvm/Demangle/Compiler.h \ + $$PWD/include/llvm/Support/Compiler.h \ + $$PWD/include/llvm/Support/PointerLikeTypeTraits.h \ + $$PWD/include/llvm/Support/DataTypes.h \ + $$PWD/include/llvm-c/DataTypes.h diff --git a/src/3rdparty/llvm/qt_attribution.json b/src/3rdparty/llvm/qt_attribution.json new file mode 100644 index 0000000000..5924f16ac3 --- /dev/null +++ b/src/3rdparty/llvm/qt_attribution.json @@ -0,0 +1,14 @@ +[ + { + "Id": "llvm-adt", + "Name": "LLVM: ADT", + "QDocModule": "qtqml", + "QtUsage": "An intrusively linked list, used in the tracing JIT to hold lists of instructions", + + "Path": "src/3rdparty/llvm", + "License": "UIUC 3-clause \"New\" or \"Revised\" License", + "LicenseId": "BSD-3-Clause", + "LicenseFile": "LICENSE.TXT", + "Copyright": "Copyright (c) 2003-2017 University of Illinois at Urbana-Champaign." + } +] diff --git a/src/3rdparty/masm/assembler/ARM64Assembler.h b/src/3rdparty/masm/assembler/ARM64Assembler.h index a9166e83a2..ca6b33d39a 100644 --- a/src/3rdparty/masm/assembler/ARM64Assembler.h +++ b/src/3rdparty/masm/assembler/ARM64Assembler.h @@ -26,7 +26,7 @@ #ifndef ARM64Assembler_h #define ARM64Assembler_h -#if ENABLE(ASSEMBLER) && (CPU(ARM64) || defined(V4_BOOTSTRAP)) +#if ENABLE(ASSEMBLER) && CPU(ARM64) #include "AssemblerBuffer.h" #include "AbstractMacroAssembler.h" @@ -3021,10 +3021,7 @@ public: static void cacheFlush(void* code, size_t size) { -#if defined(V4_BOOTSTRAP) - UNUSED_PARAM(code) - UNUSED_PARAM(size) -#elif OS(IOS) +#if OS(IOS) sys_cache_control(kCacheFunctionPrepareForExecution, code, size); #elif OS(LINUX) size_t page = pageSize(); diff --git a/src/3rdparty/masm/assembler/ARMv7Assembler.h b/src/3rdparty/masm/assembler/ARMv7Assembler.h index d57e5a7c78..03cb9f42f8 100644 --- a/src/3rdparty/masm/assembler/ARMv7Assembler.h +++ b/src/3rdparty/masm/assembler/ARMv7Assembler.h @@ -27,7 +27,7 @@ #ifndef ARMAssembler_h #define ARMAssembler_h -#if ENABLE(ASSEMBLER) && (CPU(ARM_THUMB2) || defined(V4_BOOTSTRAP)) +#if ENABLE(ASSEMBLER) && CPU(ARM_THUMB2) #include "AssemblerBuffer.h" #include "MacroAssemblerCodeRef.h" @@ -40,6 +40,10 @@ #include <libkern/OSCacheControl.h> #endif +#if OS(RTEMS) +#include <rtems/rtems/cache.h> +#endif + namespace JSC { namespace ARMRegisters { @@ -2166,7 +2170,6 @@ public: linkJumpAbsolute(location, to); } -#if !defined(V4_BOOTSTRAP) static void linkCall(void* code, AssemblerLabel from, void* to) { ASSERT(!(reinterpret_cast<intptr_t>(code) & 1)); @@ -2175,14 +2178,12 @@ public: setPointer(reinterpret_cast<uint16_t*>(reinterpret_cast<intptr_t>(code) + from.m_offset) - 1, to, false); } -#endif static void linkPointer(void* code, AssemblerLabel where, void* value) { setPointer(reinterpret_cast<char*>(code) + where.m_offset, value, false); } -#if !defined(V4_BOOTSTRAP) static void relinkJump(void* from, void* to) { ASSERT(!(reinterpret_cast<intptr_t>(from) & 1)); @@ -2205,7 +2206,6 @@ public: { return readPointer(reinterpret_cast<uint16_t*>(from) - 1); } -#endif static void repatchInt32(void* where, int32_t value) { @@ -2234,7 +2234,6 @@ public: cacheFlush(location, sizeof(uint16_t) * 2); } -#if !defined(V4_BOOTSTRAP) static void repatchPointer(void* where, void* value) { ASSERT(!(reinterpret_cast<intptr_t>(where) & 1)); @@ -2246,7 +2245,6 @@ public: { return reinterpret_cast<void*>(readInt32(where)); } -#endif static void replaceWithJump(void* instructionStart, void* to) { @@ -2321,7 +2319,7 @@ public: unsigned debugOffset() { return m_formatter.debugOffset(); } -#if OS(LINUX) && !defined(V4_BOOTSTRAP) +#if OS(LINUX) static inline void linuxPageFlush(uintptr_t begin, uintptr_t end) { asm volatile( @@ -2341,10 +2339,7 @@ public: static void cacheFlush(void* code, size_t size) { -#if defined(V4_BOOTSTRAP) - UNUSED_PARAM(code) - UNUSED_PARAM(size) -#elif OS(IOS) +#if OS(IOS) sys_cache_control(kCacheFunctionPrepareForExecution, code, size); #elif OS(LINUX) size_t page = pageSize(); @@ -2368,6 +2363,8 @@ public: #elif OS(QNX) #if !ENABLE(ASSEMBLER_WX_EXCLUSIVE) msync(code, size, MS_INVALIDATE_ICACHE); +#elif OS(RTEMS) + rtems_cache_flush_multiple_data_lines(code, size); #else UNUSED_PARAM(code); UNUSED_PARAM(size); @@ -2662,11 +2659,6 @@ private: static void linkBX(uint16_t* instruction, void* target) { -#if defined(V4_BOOTSTRAP) - UNUSED_PARAM(instruction); - UNUSED_PARAM(target); - RELEASE_ASSERT_NOT_REACHED(); -#else // FIMXE: this should be up in the MacroAssembler layer. :-( ASSERT(!(reinterpret_cast<intptr_t>(instruction) & 1)); ASSERT(!(reinterpret_cast<intptr_t>(target) & 1)); @@ -2679,7 +2671,6 @@ private: instruction[-3] = twoWordOp5i6Imm4Reg4EncodedImmFirst(OP_MOVT, hi16); instruction[-2] = twoWordOp5i6Imm4Reg4EncodedImmSecond(JUMP_TEMPORARY_REGISTER, hi16); instruction[-1] = OP_BX | (JUMP_TEMPORARY_REGISTER << 3); -#endif } void linkConditionalBX(Condition cond, uint16_t* instruction, void* target) @@ -2712,9 +2703,6 @@ private: instruction[-3] = OP_NOP_T2b; linkJumpT4(instruction, target); } else { -#if defined(V4_BOOTSTRAP) - RELEASE_ASSERT_NOT_REACHED(); -#else const uint16_t JUMP_TEMPORARY_REGISTER = ARMRegisters::ip; ARMThumbImmediate lo16 = ARMThumbImmediate::makeUInt16(static_cast<uint16_t>(reinterpret_cast<uint32_t>(target) + 1)); ARMThumbImmediate hi16 = ARMThumbImmediate::makeUInt16(static_cast<uint16_t>(reinterpret_cast<uint32_t>(target) >> 16)); @@ -2723,7 +2711,6 @@ private: instruction[-3] = twoWordOp5i6Imm4Reg4EncodedImmFirst(OP_MOVT, hi16); instruction[-2] = twoWordOp5i6Imm4Reg4EncodedImmSecond(JUMP_TEMPORARY_REGISTER, hi16); instruction[-1] = OP_BX | (JUMP_TEMPORARY_REGISTER << 3); -#endif } } diff --git a/src/3rdparty/masm/assembler/AbstractMacroAssembler.h b/src/3rdparty/masm/assembler/AbstractMacroAssembler.h index d0c1c4613e..14644a4193 100644 --- a/src/3rdparty/masm/assembler/AbstractMacroAssembler.h +++ b/src/3rdparty/masm/assembler/AbstractMacroAssembler.h @@ -66,7 +66,7 @@ public: typedef MacroAssemblerCodePtr CodePtr; typedef MacroAssemblerCodeRef CodeRef; -#if !CPU(ARM_THUMB2) && !CPU(ARM64) && !defined(V4_BOOTSTRAP) +#if !CPU(ARM_THUMB2) && !CPU(ARM64) class Jump; #endif @@ -328,7 +328,7 @@ public: friend class AbstractMacroAssembler; friend struct DFG::OSRExit; -#if CPU(ARM_THUMB2) || CPU(ARM64) || defined(V4_BOOTSTRAP) +#if CPU(ARM_THUMB2) || CPU(ARM64) using Jump = typename AssemblerType::template Jump<Label>; friend Jump; #else @@ -461,7 +461,7 @@ public: AssemblerLabel m_label; }; -#if CPU(ARM_THUMB2) || CPU(ARM64) || defined(V4_BOOTSTRAP) +#if CPU(ARM_THUMB2) || CPU(ARM64) using Jump = typename AssemblerType::template Jump<Label>; friend Jump; #endif @@ -516,7 +516,7 @@ public: // into the code buffer - it is typically used to link the jump, setting the // relative offset such that when executed it will jump to the desired // destination. -#if !CPU(ARM_THUMB2) && !CPU(ARM64) && !defined(V4_BOOTSTRAP) +#if !CPU(ARM_THUMB2) && !CPU(ARM64) class Jump { template<class TemplateAssemblerType> friend class AbstractMacroAssembler; @@ -528,7 +528,7 @@ public: { } -#if CPU(ARM_THUMB2) || defined(V4_BOOTSTRAP) +#if CPU(ARM_THUMB2) // Fixme: this information should be stored in the instruction stream, not in the Jump object. Jump(AssemblerLabel jmp, ARMv7Assembler::JumpType type = ARMv7Assembler::JumpNoCondition, ARMv7Assembler::Condition condition = ARMv7Assembler::ConditionInvalid) : m_label(jmp) @@ -621,7 +621,7 @@ public: private: AssemblerLabel m_label; -#if CPU(ARM_THUMB2) || defined(V4_BOOTSTRAP) +#if CPU(ARM_THUMB2) ARMv7Assembler::JumpType m_type; ARMv7Assembler::Condition m_condition; #endif @@ -878,12 +878,10 @@ protected: AssemblerType::repatchPointer(dataLabelPtr.dataLocation(), value); } -#if !defined(V4_BOOTSTRAP) static void* readPointer(CodeLocationDataLabelPtr dataLabelPtr) { return AssemblerType::readPointer(dataLabelPtr.dataLocation()); } -#endif static void replaceWithLoad(CodeLocationConvertibleLoad label) { diff --git a/src/3rdparty/masm/assembler/LinkBuffer.h b/src/3rdparty/masm/assembler/LinkBuffer.h index a1bb046d43..8e9a3d9c7a 100644 --- a/src/3rdparty/masm/assembler/LinkBuffer.h +++ b/src/3rdparty/masm/assembler/LinkBuffer.h @@ -374,7 +374,7 @@ public: } }; -#if CPU(ARM_THUMB2) || CPU(ARM64) || defined(V4_BOOTSTRAP) +#if CPU(ARM_THUMB2) || CPU(ARM64) template <typename T> struct BranchCompactingExecutableOffsetCalculator { @@ -509,7 +509,7 @@ inline void BranchCompactingLinkBuffer<MacroAssembler>::linkCode(void* ownerUID, m_executableMemory->shrink(m_size); } -#if CPU(ARM_THUMB2) || defined(V4_BOOTSTRAP) +#if CPU(ARM_THUMB2) template <> class LinkBuffer<JSC::MacroAssembler<MacroAssemblerARMv7>> : public BranchCompactingLinkBuffer<JSC::MacroAssembler<MacroAssemblerARMv7>> { @@ -520,7 +520,7 @@ public: }; #endif -#if CPU(ARM64) || defined(V4_BOOTSTRAP) +#if CPU(ARM64) template <> class LinkBuffer<JSC::MacroAssembler<MacroAssemblerARM64>> : public BranchCompactingLinkBuffer<JSC::MacroAssembler<MacroAssemblerARM64>> { diff --git a/src/3rdparty/masm/assembler/MacroAssembler.h b/src/3rdparty/masm/assembler/MacroAssembler.h index b442a81bd0..aada47303f 100644 --- a/src/3rdparty/masm/assembler/MacroAssembler.h +++ b/src/3rdparty/masm/assembler/MacroAssembler.h @@ -97,10 +97,7 @@ public: using MacroAssemblerBase::load32; -#if defined(V4_BOOTSTRAP) - using MacroAssemblerBase::loadPtr; - using MacroAssemblerBase::storePtr; -#elif CPU(X86_64) || CPU(ARM64) +#if CPU(X86_64) || CPU(ARM64) using MacroAssemblerBase::add64; using MacroAssemblerBase::sub64; using MacroAssemblerBase::xor64; @@ -214,14 +211,12 @@ public: store32(value, addressForPoke(index)); } -#if !defined(V4_BOOTSTRAP) void poke(TrustedImmPtr imm, int index = 0) { storePtr(imm, addressForPoke(index)); } -#endif -#if (CPU(X86_64) || CPU(ARM64)) && !defined(V4_BOOTSTRAP) +#if CPU(X86_64) || CPU(ARM64) void peek64(RegisterID dest, int index = 0) { load64(Address(MacroAssemblerBase::stackPointerRegister, (index * sizeof(void*))), dest); @@ -352,7 +347,6 @@ public: return !(this->random() & (BlindingModulus - 1)); } -#if !defined(V4_BOOTSTRAP) // Ptr methods // On 32-bit platforms (i.e. x86), these methods directly map onto their 32-bit equivalents. // FIXME: should this use a test for 32-bitness instead of this specific exception? @@ -877,7 +871,7 @@ public: { return branchSub64(cond, src1, src2, dest); } -#endif // !defined(V4_BOOTSTRAP) +#endif // !CPU(X86_64) && !CPU(ARM64) #if ENABLE(JIT_CONSTANT_BLINDING) using MacroAssemblerBase::and64; @@ -1101,8 +1095,6 @@ public: #endif -#endif // !CPU(X86_64) - #if ENABLE(JIT_CONSTANT_BLINDING) bool shouldBlind(Imm32 imm) { diff --git a/src/3rdparty/masm/assembler/MacroAssemblerARM64.h b/src/3rdparty/masm/assembler/MacroAssemblerARM64.h index e5a704292d..c0c68f6393 100644 --- a/src/3rdparty/masm/assembler/MacroAssemblerARM64.h +++ b/src/3rdparty/masm/assembler/MacroAssemblerARM64.h @@ -26,7 +26,7 @@ #ifndef MacroAssemblerARM64_h #define MacroAssemblerARM64_h -#if ENABLE(ASSEMBLER) && (CPU(ARM64) || defined(V4_BOOTSTRAP)) +#if ENABLE(ASSEMBLER) && CPU(ARM64) #include "ARM64Assembler.h" #include "AbstractMacroAssembler.h" @@ -211,33 +211,6 @@ public: static bool shouldBlindForSpecificArch(uint32_t value) { return value >= 0x00ffffff; } static bool shouldBlindForSpecificArch(uint64_t value) { return value >= 0x00ffffff; } -#if defined(V4_BOOTSTRAP) - void loadPtr(ImplicitAddress address, RegisterID dest) - { - load64(address, dest); - } - - void subPtr(TrustedImm32 imm, RegisterID dest) - { - sub64(imm, dest); - } - - void addPtr(TrustedImm32 imm, RegisterID dest) - { - add64(imm, dest); - } - - void addPtr(TrustedImm32 imm, RegisterID src, RegisterID dest) - { - add64(imm, src, dest); - } - - void storePtr(RegisterID src, ImplicitAddress address) - { - store64(src, address); - } -#endif - // Integer operations: void add32(RegisterID a, RegisterID b, RegisterID dest) @@ -1126,6 +1099,14 @@ public: m_assembler.ldrh(dest, address.base, memoryTempRegister); } + void load16(ExtendedAddress address, RegisterID dest) + { + moveToCachedReg(TrustedImmPtr(reinterpret_cast<void*>(address.offset)), m_cachedMemoryTempRegister); + m_assembler.ldrh(dest, memoryTempRegister, address.base, ARM64Assembler::UXTX, 1); + if (dest == memoryTempRegister) + m_cachedMemoryTempRegister.invalidate(); + } + void load16Unaligned(ImplicitAddress address, RegisterID dest) { load16(address, dest); @@ -2814,7 +2795,6 @@ public: return branch32(cond, left, dataTempRegister); } -#if !defined(V4_BOOTSTRAP) PatchableJump patchableBranchPtr(RelationalCondition cond, Address left, TrustedImmPtr right) { m_makeJumpPatchable = true; @@ -2822,7 +2802,6 @@ public: m_makeJumpPatchable = false; return PatchableJump(result); } -#endif PatchableJump patchableBranchTest32(ResultCondition cond, RegisterID reg, TrustedImm32 mask = TrustedImm32(-1)) { diff --git a/src/3rdparty/masm/assembler/MacroAssemblerARMv7.h b/src/3rdparty/masm/assembler/MacroAssemblerARMv7.h index 99801a0e3b..6232834fde 100644 --- a/src/3rdparty/masm/assembler/MacroAssemblerARMv7.h +++ b/src/3rdparty/masm/assembler/MacroAssemblerARMv7.h @@ -27,7 +27,7 @@ #ifndef MacroAssemblerARMv7_h #define MacroAssemblerARMv7_h -#if ENABLE(ASSEMBLER) && (CPU(ARM_THUMB2) || defined(V4_BOOTSTRAP)) +#if ENABLE(ASSEMBLER) && CPU(ARM_THUMB2) #include "ARMv7Assembler.h" #include "AbstractMacroAssembler.h" @@ -162,41 +162,12 @@ public: { add32(imm, dest, dest); } - -#if defined(V4_BOOTSTRAP) - void loadPtr(ImplicitAddress address, RegisterID dest) - { - load32(address, dest); - } - - void subPtr(TrustedImm32 imm, RegisterID dest) - { - sub32(imm, dest); - } - - void addPtr(TrustedImm32 imm, RegisterID dest) - { - add32(imm, dest); - } - - void addPtr(TrustedImm32 imm, RegisterID src, RegisterID dest) - { - add32(imm, src, dest); - } - - void storePtr(RegisterID src, ImplicitAddress address) - { - store32(src, address); - } -#endif -#if !defined(V4_BOOTSTRAP) void add32(AbsoluteAddress src, RegisterID dest) { load32(src.m_ptr, dataTempRegister); add32(dataTempRegister, dest); } -#endif void add32(TrustedImm32 imm, RegisterID src, RegisterID dest) { @@ -237,7 +208,6 @@ public: add32(dataTempRegister, dest); } -#if !defined(V4_BOOTSTRAP) void add32(TrustedImm32 imm, AbsoluteAddress address) { load32(address.m_ptr, dataTempRegister); @@ -282,7 +252,6 @@ public: m_assembler.adc(dataTempRegister, dataTempRegister, ARMThumbImmediate::makeEncodedImm(imm.m_value >> 31)); m_assembler.str(dataTempRegister, addressTempRegister, ARMThumbImmediate::makeUInt12(4)); } -#endif void and32(RegisterID op1, RegisterID op2, RegisterID dest) { @@ -384,7 +353,6 @@ public: or32(dataTempRegister, dest); } -#if !defined(V4_BOOTSTRAP) void or32(RegisterID src, AbsoluteAddress dest) { move(TrustedImmPtr(dest.m_ptr), addressTempRegister); @@ -392,7 +360,6 @@ public: or32(src, dataTempRegister); store32(dataTempRegister, addressTempRegister); } -#endif void or32(TrustedImm32 imm, RegisterID dest) { @@ -504,7 +471,6 @@ public: sub32(dataTempRegister, dest); } -#if !defined(V4_BOOTSTRAP) void sub32(TrustedImm32 imm, AbsoluteAddress address) { load32(address.m_ptr, dataTempRegister); @@ -521,7 +487,6 @@ public: store32(dataTempRegister, address.m_ptr); } -#endif void xor32(Address src, RegisterID dest) { @@ -698,13 +663,11 @@ public: load16(setupArmAddress(address), dest); } -#if !defined(V4_BOOTSTRAP) void load32(const void* address, RegisterID dest) { move(TrustedImmPtr(address), addressTempRegister); m_assembler.ldr(dest, addressTempRegister, ARMThumbImmediate::makeUInt16(0)); } -#endif ConvertibleLoadLabel convertibleLoadPtr(Address address, RegisterID dest) { @@ -809,7 +772,6 @@ public: store32(dataTempRegister, setupArmAddress(address)); } -#if !defined(V4_BOOTSTRAP) void store32(RegisterID src, const void* address) { move(TrustedImmPtr(address), addressTempRegister); @@ -821,7 +783,6 @@ public: move(imm, dataTempRegister); store32(dataTempRegister, address); } -#endif void store8(RegisterID src, BaseIndex address) { @@ -839,7 +800,6 @@ public: store8(dataTempRegister, address); } -#if !defined(V4_BOOTSTRAP) void store8(RegisterID src, void* address) { move(TrustedImmPtr(address), addressTempRegister); @@ -851,7 +811,6 @@ public: move(imm, dataTempRegister); store8(dataTempRegister, address); } -#endif void store16(RegisterID src, BaseIndex address) { @@ -949,13 +908,11 @@ public: m_assembler.vmov(dest, src); } -#if !defined(V4_BOOTSTRAP) void loadDouble(const void* address, FPRegisterID dest) { move(TrustedImmPtr(address), addressTempRegister); m_assembler.vldr(dest, addressTempRegister, 0); } -#endif void storeDouble(FPRegisterID src, ImplicitAddress address) { @@ -987,13 +944,11 @@ public: m_assembler.fsts(ARMRegisters::asSingle(src), base, offset); } -#if !defined(V4_BOOTSTRAP) void storeDouble(FPRegisterID src, const void* address) { move(TrustedImmPtr(address), addressTempRegister); storeDouble(src, addressTempRegister); } -#endif void storeDouble(FPRegisterID src, BaseIndex address) { @@ -1027,13 +982,11 @@ public: m_assembler.vadd(dest, op1, op2); } -#if !defined(V4_BOOTSTRAP) void addDouble(AbsoluteAddress address, FPRegisterID dest) { loadDouble(address.m_ptr, fpTempRegister); m_assembler.vadd(dest, dest, fpTempRegister); } -#endif void divDouble(FPRegisterID src, FPRegisterID dest) { @@ -1112,7 +1065,6 @@ public: m_assembler.vcvt_signedToFloatingPoint(dest, fpTempRegisterAsSingle()); } -#if !defined(V4_BOOTSTRAP) void convertInt32ToDouble(AbsoluteAddress address, FPRegisterID dest) { // Fixme: load directly into the fpr! @@ -1120,7 +1072,6 @@ public: m_assembler.vmov(fpTempRegister, dataTempRegister, dataTempRegister); m_assembler.vcvt_signedToFloatingPoint(dest, fpTempRegisterAsSingle()); } -#endif void convertUInt32ToDouble(RegisterID src, FPRegisterID dest, RegisterID /*scratch*/) { @@ -1316,12 +1267,10 @@ public: m_assembler.mov(dest, src); } -#if !defined(V4_BOOTSTRAP) void move(TrustedImmPtr imm, RegisterID dest) { move(TrustedImm32(imm), dest); } -#endif void swap(RegisterID reg1, RegisterID reg2) { @@ -1462,7 +1411,6 @@ public: return branch32(cond, addressTempRegister, right); } -#if !defined(V4_BOOTSTRAP) Jump branch32(RelationalCondition cond, AbsoluteAddress left, RegisterID right) { load32(left.m_ptr, dataTempRegister); @@ -1475,7 +1423,6 @@ public: load32(left.m_ptr, addressTempRegister); return branch32(cond, addressTempRegister, right); } -#endif Jump branch8(RelationalCondition cond, RegisterID left, TrustedImm32 right) { @@ -1532,7 +1479,6 @@ public: return branchTest32(cond, addressTempRegister, mask); } -#if !defined(V4_BOOTSTRAP) Jump branchTest8(ResultCondition cond, AbsoluteAddress address, TrustedImm32 mask = TrustedImm32(-1)) { // use addressTempRegister incase the branchTest8 we call uses dataTempRegister. :-/ @@ -1540,7 +1486,6 @@ public: load8(Address(addressTempRegister), addressTempRegister); return branchTest32(cond, addressTempRegister, mask); } -#endif void jump(RegisterID target) { @@ -1554,14 +1499,12 @@ public: m_assembler.bx(dataTempRegister); } -#if !defined(V4_BOOTSTRAP) void jump(AbsoluteAddress address) { move(TrustedImmPtr(address.m_ptr), dataTempRegister); load32(Address(dataTempRegister), dataTempRegister); m_assembler.bx(dataTempRegister); } -#endif // Arithmetic control flow operations: @@ -1602,7 +1545,6 @@ public: return branchAdd32(cond, dest, imm, dest); } -#if !defined(V4_BOOTSTRAP) Jump branchAdd32(ResultCondition cond, TrustedImm32 imm, AbsoluteAddress dest) { // Move the high bits of the address into addressTempRegister, @@ -1628,7 +1570,6 @@ public: return Jump(makeBranch(cond)); } -#endif Jump branchMul32(ResultCondition cond, RegisterID src1, RegisterID src2, RegisterID dest) { @@ -1799,7 +1740,6 @@ public: return DataLabel32(this); } -#if !defined(V4_BOOTSTRAP) ALWAYS_INLINE DataLabelPtr moveWithPatch(TrustedImmPtr imm, RegisterID dst) { padBeforePatch(); @@ -1827,7 +1767,6 @@ public: m_makeJumpPatchable = false; return PatchableJump(result); } -#endif PatchableJump patchableBranchTest32(ResultCondition cond, RegisterID reg, TrustedImm32 mask = TrustedImm32(-1)) { @@ -1845,7 +1784,6 @@ public: return PatchableJump(result); } -#if !defined(V4_BOOTSTRAP) PatchableJump patchableBranchPtrWithPatch(RelationalCondition cond, Address left, DataLabelPtr& dataLabel, TrustedImmPtr initialRightValue = TrustedImmPtr(0)) { m_makeJumpPatchable = true; @@ -1853,7 +1791,6 @@ public: m_makeJumpPatchable = false; return PatchableJump(result); } -#endif PatchableJump patchableJump() { @@ -1864,7 +1801,6 @@ public: return PatchableJump(result); } -#if !defined(V4_BOOTSTRAP) ALWAYS_INLINE DataLabelPtr storePtrWithPatch(TrustedImmPtr initialValue, ImplicitAddress address) { DataLabelPtr label = moveWithPatch(initialValue, dataTempRegister); @@ -1872,7 +1808,6 @@ public: return label; } ALWAYS_INLINE DataLabelPtr storePtrWithPatch(ImplicitAddress address) { return storePtrWithPatch(TrustedImmPtr(0), address); } -#endif ALWAYS_INLINE Call tailRecursiveCall() { @@ -1893,7 +1828,6 @@ public: return m_assembler.executableOffsetFor(location); } -#if !defined(V4_BOOTSTRAP) static FunctionPtr readCallTarget(CodeLocationCall call) { return FunctionPtr(reinterpret_cast<void(*)()>(ARMv7Assembler::readCallTarget(call.dataLocation()))); @@ -1906,7 +1840,6 @@ public: const unsigned twoWordOpSize = 4; return label.labelAtOffset(-twoWordOpSize * 2); } -#endif static void revertJumpReplacementToBranchPtrWithPatch(CodeLocationLabel instructionStart, RegisterID rd, void* initialValue) { @@ -2024,7 +1957,6 @@ private: template <typename, template <typename> class> friend class LinkBufferBase; friend class RepatchBuffer; -#if !defined(V4_BOOTSTRAP) static void linkCall(void* code, Call call, FunctionPtr function) { ARMv7Assembler::linkCall(code, call.m_label, function.value()); @@ -2039,7 +1971,6 @@ private: { ARMv7Assembler::relinkCall(call.dataLocation(), destination.executableAddress()); } -#endif bool m_makeJumpPatchable; }; diff --git a/src/3rdparty/masm/assembler/MacroAssemblerX86.h b/src/3rdparty/masm/assembler/MacroAssemblerX86.h index e3e0bfe5e1..5cffa787ec 100644 --- a/src/3rdparty/masm/assembler/MacroAssemblerX86.h +++ b/src/3rdparty/masm/assembler/MacroAssemblerX86.h @@ -55,38 +55,6 @@ public: using MacroAssemblerX86Common::convertInt32ToDouble; using MacroAssemblerX86Common::branchTest8; -#if defined(V4_BOOTSTRAP) - void loadPtr(ImplicitAddress address, RegisterID dest) - { - load32(address, dest); - } - - void subPtr(TrustedImm32 imm, RegisterID dest) - { - sub32(imm, dest); - } - - void addPtr(TrustedImm32 imm, RegisterID dest) - { - add32(imm, dest); - } - - void addPtr(TrustedImm32 imm, RegisterID src, RegisterID dest) - { - add32(imm, src, dest); - } - - void storePtr(RegisterID src, ImplicitAddress address) - { - store32(src, address); - } - - Jump branchTest8(ResultCondition cond, ExtendedAddress address, TrustedImm32 mask = TrustedImm32(-1)) - { - return branchTest8(cond, Address(address.base, address.offset), mask); - } -#endif - void add32(TrustedImm32 imm, RegisterID src, RegisterID dest) { m_assembler.leal_mr(imm.m_value, src, dest); diff --git a/src/3rdparty/masm/assembler/MacroAssemblerX86_64.h b/src/3rdparty/masm/assembler/MacroAssemblerX86_64.h index f4349e1f93..0a6db0805b 100644 --- a/src/3rdparty/masm/assembler/MacroAssemblerX86_64.h +++ b/src/3rdparty/masm/assembler/MacroAssemblerX86_64.h @@ -53,33 +53,6 @@ public: using MacroAssemblerX86Common::loadDouble; using MacroAssemblerX86Common::convertInt32ToDouble; -#if defined(V4_BOOTSTRAP) - void loadPtr(ImplicitAddress address, RegisterID dest) - { - load64(address, dest); - } - - void subPtr(TrustedImm32 imm, RegisterID dest) - { - sub64(imm, dest); - } - - void addPtr(TrustedImm32 imm, RegisterID dest) - { - add64(imm, dest); - } - - void addPtr(TrustedImm32 imm, RegisterID src, RegisterID dest) - { - add64(imm, src, dest); - } - - void storePtr(RegisterID src, ImplicitAddress address) - { - store64(src, address); - } -#endif - void add32(TrustedImm32 imm, AbsoluteAddress address) { move(TrustedImmPtr(address.m_ptr), scratchRegister); @@ -116,6 +89,23 @@ public: sub32(imm, Address(scratchRegister)); } + void load16(ExtendedAddress address, RegisterID dest) + { + TrustedImmPtr addr(reinterpret_cast<void*>(address.offset)); + MacroAssemblerX86Common::move(addr, scratchRegister); + MacroAssemblerX86Common::load16(BaseIndex(scratchRegister, address.base, TimesTwo), dest); + } + + void load16(BaseIndex address, RegisterID dest) + { + MacroAssemblerX86Common::load16(address, dest); + } + + void load16(Address address, RegisterID dest) + { + MacroAssemblerX86Common::load16(address, dest); + } + void load32(const void* address, RegisterID dest) { if (dest == X86Registers::eax) diff --git a/src/3rdparty/masm/assembler/X86Assembler.h b/src/3rdparty/masm/assembler/X86Assembler.h index 2257cb2b9a..e8ae687036 100644 --- a/src/3rdparty/masm/assembler/X86Assembler.h +++ b/src/3rdparty/masm/assembler/X86Assembler.h @@ -255,47 +255,6 @@ public: { } -#if defined(V4_BOOTSTRAP) - template <typename LabelType> - class Jump { - template<class TemplateAssemblerType> - friend class AbstractMacroAssembler; - friend class Call; - template <typename, template <typename> class> friend class LinkBufferBase; - public: - Jump() - { - } - - Jump(AssemblerLabel jmp) - : m_label(jmp) - { - } - - LabelType label() const - { - LabelType result; - result.m_label = m_label; - return result; - } - - void link(AbstractMacroAssembler<X86Assembler>* masm) const - { - masm->m_assembler.linkJump(m_label, masm->m_assembler.label()); - } - - void linkTo(LabelType label, AbstractMacroAssembler<X86Assembler>* masm) const - { - masm->m_assembler.linkJump(m_label, label.label()); - } - - bool isSet() const { return m_label.isSet(); } - - private: - AssemblerLabel m_label; - }; -#endif - // Stack operations: void push_r(RegisterID reg) diff --git a/src/3rdparty/masm/masm-defs.pri b/src/3rdparty/masm/masm-defs.pri index 08c46a7ac2..90a795c6ce 100644 --- a/src/3rdparty/masm/masm-defs.pri +++ b/src/3rdparty/masm/masm-defs.pri @@ -33,10 +33,6 @@ disassembler { DEFINES += WTF_USE_UDIS86=0 } -force-compile-jit { - DEFINES += V4_FORCE_COMPILE_JIT -} - INCLUDEPATH += $$PWD/disassembler INCLUDEPATH += $$PWD/disassembler/udis86 INCLUDEPATH += $$_OUT_PWD diff --git a/src/3rdparty/masm/masm.pri b/src/3rdparty/masm/masm.pri index 0e63ac2ce5..1df4585aae 100644 --- a/src/3rdparty/masm/masm.pri +++ b/src/3rdparty/masm/masm.pri @@ -77,7 +77,6 @@ SOURCES += $$PWD/disassembler/ARM64Disassembler.cpp SOURCES += $$PWD/disassembler/ARM64/A64DOpcode.cpp HEADERS += $$PWD/disassembler/ARM64/A64DOpcode.h -!qmldevtools_build { SOURCES += $$PWD/yarr/YarrCanonicalizeUCS2.cpp \ $$PWD/yarr/YarrCanonicalizeUnicode.cpp \ $$PWD/yarr/YarrInterpreter.cpp \ @@ -94,7 +93,6 @@ HEADERS += $$PWD/yarr/Yarr.h \ $$PWD/yarr/YarrPattern.h \ $$PWD/yarr/YarrSyntaxChecker.h \ $$PWD/yarr/YarrUnicodeProperties.h -} # # Generate RegExpJitTables.h @@ -128,8 +126,3 @@ QMAKE_EXTRA_COMPILERS += retgen } } } - -linux { - requires(qtConfig(dlopen)) - QMAKE_USE_PRIVATE += libdl -} diff --git a/src/3rdparty/masm/stubs/wtf/Vector.h b/src/3rdparty/masm/stubs/wtf/Vector.h index f4f4dc5cf4..2fead9f6ba 100644 --- a/src/3rdparty/masm/stubs/wtf/Vector.h +++ b/src/3rdparty/masm/stubs/wtf/Vector.h @@ -109,6 +109,15 @@ public: inline bool isEmpty() const { return this->empty(); } inline T &last() { return *(this->begin() + this->size() - 1); } + + bool contains(const T &value) const + { + for (const T &inVector : *this) { + if (inVector == value) + return true; + } + return false; + } }; template <typename T, int capacity> diff --git a/src/3rdparty/masm/wtf/OSAllocatorPosix.cpp b/src/3rdparty/masm/wtf/OSAllocatorPosix.cpp index 3b2a73a39a..d59fdcd675 100644 --- a/src/3rdparty/masm/wtf/OSAllocatorPosix.cpp +++ b/src/3rdparty/masm/wtf/OSAllocatorPosix.cpp @@ -74,21 +74,9 @@ static int memfdForUsage(size_t bytes, OSAllocator::Usage usage) break; } - // try to get our own library name by giving dladdr a pointer pointing to - // something we know to be in it (using a pointer to string data) - static const char *libname = [=]() { - Dl_info info; - if (dladdr(type, &info) == 0) - info.dli_fname = nullptr; - return info.dli_fname; - }(); - char buf[PATH_MAX]; strcpy(buf, type); - if (libname) - strcat(buf, libname); - else - strcat(buf, "QtQml"); + strcat(buf, "QtQml"); int fd = syscall(SYS_memfd_create, buf, MFD_CLOEXEC); if (fd != -1) { diff --git a/src/3rdparty/masm/wtf/Platform.h b/src/3rdparty/masm/wtf/Platform.h index d5f69927db..ab1da2198a 100644 --- a/src/3rdparty/masm/wtf/Platform.h +++ b/src/3rdparty/masm/wtf/Platform.h @@ -438,6 +438,10 @@ #define WTF_OS_WINDOWS 1 #endif +#ifdef __rtems__ +#define WTF_OS_RTEMS 1 +#endif + #define WTF_OS_WIN ERROR "USE WINDOWS WITH OS NOT WIN" #define WTF_OS_MAC ERROR "USE MAC_OS_X WITH OS NOT MAC" @@ -451,6 +455,7 @@ || OS(NETBSD) \ || OS(OPENBSD) \ || OS(QNX) \ + || OS(RTEMS) \ || OS(SOLARIS) \ || defined(unix) \ || defined(__unix) \ @@ -1051,6 +1056,7 @@ #if CPU(ARM64) || (CPU(X86_64) && !OS(WINDOWS)) /* Enable JIT'ing Regular Expressions that have nested parenthesis. */ #define ENABLE_YARR_JIT_ALL_PARENS_EXPRESSIONS 1 +#define ENABLE_YARR_JIT_BACKREFERENCES 1 #endif #endif diff --git a/src/3rdparty/masm/yarr/YarrCanonicalize.h b/src/3rdparty/masm/yarr/YarrCanonicalize.h index fb5e0231ac..cbd279edca 100644 --- a/src/3rdparty/masm/yarr/YarrCanonicalize.h +++ b/src/3rdparty/masm/yarr/YarrCanonicalize.h @@ -53,6 +53,7 @@ struct CanonicalizationRange { extern const size_t UCS2_CANONICALIZATION_RANGES; extern const UChar32* const ucs2CharacterSetInfo[]; extern const CanonicalizationRange ucs2RangeInfo[]; +extern const uint16_t canonicalTableLChar[256]; extern const size_t UNICODE_CANONICALIZATION_RANGES; extern const UChar32* const unicodeCharacterSetInfo[]; diff --git a/src/3rdparty/masm/yarr/YarrCanonicalizeUCS2.cpp b/src/3rdparty/masm/yarr/YarrCanonicalizeUCS2.cpp index d91c771590..0eb59f38d2 100644 --- a/src/3rdparty/masm/yarr/YarrCanonicalizeUCS2.cpp +++ b/src/3rdparty/masm/yarr/YarrCanonicalizeUCS2.cpp @@ -1,5 +1,5 @@ /* - * Copyright (C) 2012-2013, 2015-2016 Apple Inc. All rights reserved. + * Copyright (C) 2012-2018 Apple Inc. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -44,9 +44,17 @@ const UChar32 ucs2CharacterSet10[] = { 0x03a0, 0x03c0, 0x03d6, 0 }; const UChar32 ucs2CharacterSet11[] = { 0x03a1, 0x03c1, 0x03f1, 0 }; const UChar32 ucs2CharacterSet12[] = { 0x03a3, 0x03c2, 0x03c3, 0 }; const UChar32 ucs2CharacterSet13[] = { 0x03a6, 0x03c6, 0x03d5, 0 }; -const UChar32 ucs2CharacterSet14[] = { 0x1e60, 0x1e61, 0x1e9b, 0 }; +const UChar32 ucs2CharacterSet14[] = { 0x0412, 0x0432, 0x1c80, 0 }; +const UChar32 ucs2CharacterSet15[] = { 0x0414, 0x0434, 0x1c81, 0 }; +const UChar32 ucs2CharacterSet16[] = { 0x041e, 0x043e, 0x1c82, 0 }; +const UChar32 ucs2CharacterSet17[] = { 0x0421, 0x0441, 0x1c83, 0 }; +const UChar32 ucs2CharacterSet18[] = { 0x0422, 0x0442, 0x1c84, 0x1c85, 0 }; +const UChar32 ucs2CharacterSet19[] = { 0x042a, 0x044a, 0x1c86, 0 }; +const UChar32 ucs2CharacterSet20[] = { 0x0462, 0x0463, 0x1c87, 0 }; +const UChar32 ucs2CharacterSet21[] = { 0x1e60, 0x1e61, 0x1e9b, 0 }; +const UChar32 ucs2CharacterSet22[] = { 0x1c88, 0xa64a, 0xa64b, 0 }; -static const size_t UCS2_CANONICALIZATION_SETS = 15; +static const size_t UCS2_CANONICALIZATION_SETS = 23; const UChar32* const ucs2CharacterSetInfo[UCS2_CANONICALIZATION_SETS] = { ucs2CharacterSet0, ucs2CharacterSet1, @@ -63,9 +71,17 @@ const UChar32* const ucs2CharacterSetInfo[UCS2_CANONICALIZATION_SETS] = { ucs2CharacterSet12, ucs2CharacterSet13, ucs2CharacterSet14, + ucs2CharacterSet15, + ucs2CharacterSet16, + ucs2CharacterSet17, + ucs2CharacterSet18, + ucs2CharacterSet19, + ucs2CharacterSet20, + ucs2CharacterSet21, + ucs2CharacterSet22, }; -const size_t UCS2_CANONICALIZATION_RANGES = 391; +const size_t UCS2_CANONICALIZATION_RANGES = 448; const CanonicalizationRange ucs2RangeInfo[UCS2_CANONICALIZATION_RANGES] = { { 0x0000, 0x0040, 0x0000, CanonicalizeUnique }, { 0x0041, 0x005a, 0x0020, CanonicalizeRangeLo }, @@ -182,7 +198,7 @@ const CanonicalizationRange ucs2RangeInfo[UCS2_CANONICALIZATION_RANGES] = { { 0x0267, 0x0267, 0x0000, CanonicalizeUnique }, { 0x0268, 0x0268, 0x00d1, CanonicalizeRangeHi }, { 0x0269, 0x0269, 0x00d3, CanonicalizeRangeHi }, - { 0x026a, 0x026a, 0x0000, CanonicalizeUnique }, + { 0x026a, 0x026a, 0xa544, CanonicalizeRangeLo }, { 0x026b, 0x026b, 0x29f7, CanonicalizeRangeLo }, { 0x026c, 0x026c, 0xa541, CanonicalizeRangeLo }, { 0x026d, 0x026e, 0x0000, CanonicalizeUnique }, @@ -206,7 +222,8 @@ const CanonicalizationRange ucs2RangeInfo[UCS2_CANONICALIZATION_RANGES] = { { 0x028c, 0x028c, 0x0047, CanonicalizeRangeHi }, { 0x028d, 0x0291, 0x0000, CanonicalizeUnique }, { 0x0292, 0x0292, 0x00db, CanonicalizeRangeHi }, - { 0x0293, 0x029d, 0x0000, CanonicalizeUnique }, + { 0x0293, 0x029c, 0x0000, CanonicalizeUnique }, + { 0x029d, 0x029d, 0xa515, CanonicalizeRangeLo }, { 0x029e, 0x029e, 0xa512, CanonicalizeRangeLo }, { 0x029f, 0x0344, 0x0000, CanonicalizeUnique }, { 0x0345, 0x0345, 0x0007, CanonicalizeSet }, @@ -288,10 +305,34 @@ const CanonicalizationRange ucs2RangeInfo[UCS2_CANONICALIZATION_RANGES] = { { 0x03fc, 0x03fc, 0x0000, CanonicalizeUnique }, { 0x03fd, 0x03ff, 0x0082, CanonicalizeRangeHi }, { 0x0400, 0x040f, 0x0050, CanonicalizeRangeLo }, - { 0x0410, 0x042f, 0x0020, CanonicalizeRangeLo }, - { 0x0430, 0x044f, 0x0020, CanonicalizeRangeHi }, + { 0x0410, 0x0411, 0x0020, CanonicalizeRangeLo }, + { 0x0412, 0x0412, 0x000e, CanonicalizeSet }, + { 0x0413, 0x0413, 0x0020, CanonicalizeRangeLo }, + { 0x0414, 0x0414, 0x000f, CanonicalizeSet }, + { 0x0415, 0x041d, 0x0020, CanonicalizeRangeLo }, + { 0x041e, 0x041e, 0x0010, CanonicalizeSet }, + { 0x041f, 0x0420, 0x0020, CanonicalizeRangeLo }, + { 0x0421, 0x0421, 0x0011, CanonicalizeSet }, + { 0x0422, 0x0422, 0x0012, CanonicalizeSet }, + { 0x0423, 0x0429, 0x0020, CanonicalizeRangeLo }, + { 0x042a, 0x042a, 0x0013, CanonicalizeSet }, + { 0x042b, 0x042f, 0x0020, CanonicalizeRangeLo }, + { 0x0430, 0x0431, 0x0020, CanonicalizeRangeHi }, + { 0x0432, 0x0432, 0x000e, CanonicalizeSet }, + { 0x0433, 0x0433, 0x0020, CanonicalizeRangeHi }, + { 0x0434, 0x0434, 0x000f, CanonicalizeSet }, + { 0x0435, 0x043d, 0x0020, CanonicalizeRangeHi }, + { 0x043e, 0x043e, 0x0010, CanonicalizeSet }, + { 0x043f, 0x0440, 0x0020, CanonicalizeRangeHi }, + { 0x0441, 0x0441, 0x0011, CanonicalizeSet }, + { 0x0442, 0x0442, 0x0012, CanonicalizeSet }, + { 0x0443, 0x0449, 0x0020, CanonicalizeRangeHi }, + { 0x044a, 0x044a, 0x0013, CanonicalizeSet }, + { 0x044b, 0x044f, 0x0020, CanonicalizeRangeHi }, { 0x0450, 0x045f, 0x0050, CanonicalizeRangeHi }, - { 0x0460, 0x0481, 0x0000, CanonicalizeAlternatingAligned }, + { 0x0460, 0x0461, 0x0000, CanonicalizeAlternatingAligned }, + { 0x0462, 0x0463, 0x0014, CanonicalizeSet }, + { 0x0464, 0x0481, 0x0000, CanonicalizeAlternatingAligned }, { 0x0482, 0x0489, 0x0000, CanonicalizeUnique }, { 0x048a, 0x04bf, 0x0000, CanonicalizeAlternatingAligned }, { 0x04c0, 0x04c0, 0x000f, CanonicalizeRangeLo }, @@ -308,16 +349,38 @@ const CanonicalizationRange ucs2RangeInfo[UCS2_CANONICALIZATION_RANGES] = { { 0x10c7, 0x10c7, 0x1c60, CanonicalizeRangeLo }, { 0x10c8, 0x10cc, 0x0000, CanonicalizeUnique }, { 0x10cd, 0x10cd, 0x1c60, CanonicalizeRangeLo }, - { 0x10ce, 0x1d78, 0x0000, CanonicalizeUnique }, + { 0x10ce, 0x10cf, 0x0000, CanonicalizeUnique }, + { 0x10d0, 0x10fa, 0x0bc0, CanonicalizeRangeLo }, + { 0x10fb, 0x10fc, 0x0000, CanonicalizeUnique }, + { 0x10fd, 0x10ff, 0x0bc0, CanonicalizeRangeLo }, + { 0x1100, 0x139f, 0x0000, CanonicalizeUnique }, + { 0x13a0, 0x13ef, 0x97d0, CanonicalizeRangeLo }, + { 0x13f0, 0x13f5, 0x0008, CanonicalizeRangeLo }, + { 0x13f6, 0x13f7, 0x0000, CanonicalizeUnique }, + { 0x13f8, 0x13fd, 0x0008, CanonicalizeRangeHi }, + { 0x13fe, 0x1c7f, 0x0000, CanonicalizeUnique }, + { 0x1c80, 0x1c80, 0x000e, CanonicalizeSet }, + { 0x1c81, 0x1c81, 0x000f, CanonicalizeSet }, + { 0x1c82, 0x1c82, 0x0010, CanonicalizeSet }, + { 0x1c83, 0x1c83, 0x0011, CanonicalizeSet }, + { 0x1c84, 0x1c85, 0x0012, CanonicalizeSet }, + { 0x1c86, 0x1c86, 0x0013, CanonicalizeSet }, + { 0x1c87, 0x1c87, 0x0014, CanonicalizeSet }, + { 0x1c88, 0x1c88, 0x0016, CanonicalizeSet }, + { 0x1c89, 0x1c8f, 0x0000, CanonicalizeUnique }, + { 0x1c90, 0x1cba, 0x0bc0, CanonicalizeRangeHi }, + { 0x1cbb, 0x1cbc, 0x0000, CanonicalizeUnique }, + { 0x1cbd, 0x1cbf, 0x0bc0, CanonicalizeRangeHi }, + { 0x1cc0, 0x1d78, 0x0000, CanonicalizeUnique }, { 0x1d79, 0x1d79, 0x8a04, CanonicalizeRangeLo }, { 0x1d7a, 0x1d7c, 0x0000, CanonicalizeUnique }, { 0x1d7d, 0x1d7d, 0x0ee6, CanonicalizeRangeLo }, { 0x1d7e, 0x1dff, 0x0000, CanonicalizeUnique }, { 0x1e00, 0x1e5f, 0x0000, CanonicalizeAlternatingAligned }, - { 0x1e60, 0x1e61, 0x000e, CanonicalizeSet }, + { 0x1e60, 0x1e61, 0x0015, CanonicalizeSet }, { 0x1e62, 0x1e95, 0x0000, CanonicalizeAlternatingAligned }, { 0x1e96, 0x1e9a, 0x0000, CanonicalizeUnique }, - { 0x1e9b, 0x1e9b, 0x000e, CanonicalizeSet }, + { 0x1e9b, 0x1e9b, 0x0015, CanonicalizeSet }, { 0x1e9c, 0x1e9f, 0x0000, CanonicalizeUnique }, { 0x1ea0, 0x1eff, 0x0000, CanonicalizeAlternatingAligned }, { 0x1f00, 0x1f07, 0x0008, CanonicalizeRangeLo }, @@ -428,7 +491,9 @@ const CanonicalizationRange ucs2RangeInfo[UCS2_CANONICALIZATION_RANGES] = { { 0x2d28, 0x2d2c, 0x0000, CanonicalizeUnique }, { 0x2d2d, 0x2d2d, 0x1c60, CanonicalizeRangeHi }, { 0x2d2e, 0xa63f, 0x0000, CanonicalizeUnique }, - { 0xa640, 0xa66d, 0x0000, CanonicalizeAlternatingAligned }, + { 0xa640, 0xa649, 0x0000, CanonicalizeAlternatingAligned }, + { 0xa64a, 0xa64b, 0x0016, CanonicalizeSet }, + { 0xa64c, 0xa66d, 0x0000, CanonicalizeAlternatingAligned }, { 0xa66e, 0xa67f, 0x0000, CanonicalizeUnique }, { 0xa680, 0xa69b, 0x0000, CanonicalizeAlternatingAligned }, { 0xa69c, 0xa721, 0x0000, CanonicalizeUnique }, @@ -450,15 +515,42 @@ const CanonicalizationRange ucs2RangeInfo[UCS2_CANONICALIZATION_RANGES] = { { 0xa7ab, 0xa7ab, 0xa54f, CanonicalizeRangeHi }, { 0xa7ac, 0xa7ac, 0xa54b, CanonicalizeRangeHi }, { 0xa7ad, 0xa7ad, 0xa541, CanonicalizeRangeHi }, - { 0xa7ae, 0xa7af, 0x0000, CanonicalizeUnique }, + { 0xa7ae, 0xa7ae, 0xa544, CanonicalizeRangeHi }, + { 0xa7af, 0xa7af, 0x0000, CanonicalizeUnique }, { 0xa7b0, 0xa7b0, 0xa512, CanonicalizeRangeHi }, { 0xa7b1, 0xa7b1, 0xa52a, CanonicalizeRangeHi }, - { 0xa7b2, 0xff20, 0x0000, CanonicalizeUnique }, + { 0xa7b2, 0xa7b2, 0xa515, CanonicalizeRangeHi }, + { 0xa7b3, 0xa7b3, 0x03a0, CanonicalizeRangeLo }, + { 0xa7b4, 0xa7b9, 0x0000, CanonicalizeAlternatingAligned }, + { 0xa7ba, 0xab52, 0x0000, CanonicalizeUnique }, + { 0xab53, 0xab53, 0x03a0, CanonicalizeRangeHi }, + { 0xab54, 0xab6f, 0x0000, CanonicalizeUnique }, + { 0xab70, 0xabbf, 0x97d0, CanonicalizeRangeHi }, + { 0xabc0, 0xff20, 0x0000, CanonicalizeUnique }, { 0xff21, 0xff3a, 0x0020, CanonicalizeRangeLo }, { 0xff3b, 0xff40, 0x0000, CanonicalizeUnique }, { 0xff41, 0xff5a, 0x0020, CanonicalizeRangeHi }, { 0xff5b, 0xffff, 0x0000, CanonicalizeUnique }, }; +const uint16_t canonicalTableLChar[256] = { + 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, + 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, + 0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f, + 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, + 0x40, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4a, 0x4b, 0x4c, 0x4d, 0x4e, 0x4f, + 0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58, 0x59, 0x5a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f, + 0x60, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4a, 0x4b, 0x4c, 0x4d, 0x4e, 0x4f, + 0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58, 0x59, 0x5a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, + 0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f, + 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, + 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf, + 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0x39c, 0xb6, 0xb7, 0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf, + 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, + 0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf, + 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, + 0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xf7, 0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0x178 +}; + } } // JSC::Yarr diff --git a/src/3rdparty/masm/yarr/YarrCanonicalizeUCS2.js b/src/3rdparty/masm/yarr/YarrCanonicalizeUCS2.js index dc578cfece..b92d8bdd4f 100644 --- a/src/3rdparty/masm/yarr/YarrCanonicalizeUCS2.js +++ b/src/3rdparty/masm/yarr/YarrCanonicalizeUCS2.js @@ -1,5 +1,5 @@ /* - * Copyright (C) 2012, 2016 Apple Inc. All rights reserved. + * Copyright (C) 2012-2018 Apple Inc. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -27,7 +27,7 @@ function printHeader() { var copyright = ( "/*" + "\n" + - " * Copyright (C) 2012-2013, 2015-2016 Apple Inc. All rights reserved." + "\n" + + " * Copyright (C) 2012-2018 Apple Inc. All rights reserved." + "\n" + " *" + "\n" + " * Redistribution and use in source and binary forms, with or without" + "\n" + " * modification, are permitted provided that the following conditions" + "\n" + @@ -183,6 +183,23 @@ function createTables(prefix, maxValue, canonicalGroups) } print("};"); print(); + // Create canonical table for LChar domain + let line = "const uint16_t canonicalTableLChar[256] = {"; + for (let i = 0; i < 256; i++) { + if (!(i % 16)) { + print(line); + line = " "; + } + let canonicalChar = canonicalize(i); + line = line + (canonicalChar < 16 ? "0x0" : "0x") + canonicalChar.toString(16); + if ((i % 16) != 15) + line += ", "; + else if (i != 255) + line += ","; + } + print(line); + print("};"); + print(); } printHeader(); diff --git a/src/3rdparty/masm/yarr/YarrErrorCode.h b/src/3rdparty/masm/yarr/YarrErrorCode.h index 48f2bb7900..3f06a6bff1 100644 --- a/src/3rdparty/masm/yarr/YarrErrorCode.h +++ b/src/3rdparty/masm/yarr/YarrErrorCode.h @@ -60,6 +60,13 @@ inline bool hasError(ErrorCode errorCode) { return errorCode != ErrorCode::NoError; } + +inline bool hasHardError(ErrorCode errorCode) +{ + // TooManyDisjunctions means that we ran out stack compiling. + // All other errors are due to problems in the expression. + return hasError(errorCode) && errorCode != ErrorCode::TooManyDisjunctions; +} JS_EXPORT_PRIVATE JSObject* errorToThrow(ExecState*, ErrorCode); } } // namespace JSC::Yarr diff --git a/src/3rdparty/masm/yarr/YarrInterpreter.cpp b/src/3rdparty/masm/yarr/YarrInterpreter.cpp index 4d3652fcbc..cdcd16af64 100644 --- a/src/3rdparty/masm/yarr/YarrInterpreter.cpp +++ b/src/3rdparty/masm/yarr/YarrInterpreter.cpp @@ -32,12 +32,12 @@ #include "Yarr.h" #include "YarrCanonicalize.h" #include <wtf/BumpPointerAllocator.h> +#include <wtf/CheckedArithmetic.h> #include <wtf/DataLog.h> +#include <wtf/StdLibExtras.h> #include <wtf/text/CString.h> #include <wtf/text/WTFString.h> -using namespace WTF; - namespace JSC { namespace Yarr { template<typename CharType> @@ -67,17 +67,23 @@ public: struct DisjunctionContext { - DisjunctionContext() - : term(0) - { - } + DisjunctionContext() = default; void* operator new(size_t, void* where) { return where; } - int term; + static size_t allocationSize(unsigned numberOfFrames) + { + static_assert(alignof(DisjunctionContext) <= sizeof(void*), ""); + size_t rawSize = (sizeof(DisjunctionContext) - sizeof(uintptr_t) + Checked<size_t>(numberOfFrames) * sizeof(uintptr_t)).unsafeGet(); + size_t roundedSize = WTF::roundUpToMultipleOf<sizeof(void*)>(rawSize); + RELEASE_ASSERT(roundedSize >= rawSize); + return roundedSize; + } + + int term { 0 }; unsigned matchBegin; unsigned matchEnd; uintptr_t frame[1]; @@ -85,7 +91,7 @@ public: DisjunctionContext* allocDisjunctionContext(ByteDisjunction* disjunction) { - size_t size = sizeof(DisjunctionContext) - sizeof(uintptr_t) + disjunction->m_frameSize * sizeof(uintptr_t); + size_t size = DisjunctionContext::allocationSize(disjunction->m_frameSize); allocatorPool = allocatorPool->ensureCapacity(size); RELEASE_ASSERT(allocatorPool); return new (allocatorPool->alloc(size)) DisjunctionContext(); @@ -99,7 +105,6 @@ public: struct ParenthesesDisjunctionContext { ParenthesesDisjunctionContext(unsigned* output, ByteTerm& term) - : next(0) { unsigned firstSubpatternId = term.atom.subpatternId; unsigned numNestedSubpatterns = term.atom.parenthesesDisjunction->m_numSubpatterns; @@ -125,16 +130,25 @@ public: DisjunctionContext* getDisjunctionContext(ByteTerm& term) { - return reinterpret_cast<DisjunctionContext*>(&(subpatternBackup[term.atom.parenthesesDisjunction->m_numSubpatterns << 1])); + return bitwise_cast<DisjunctionContext*>(bitwise_cast<uintptr_t>(this) + allocationSize(term.atom.parenthesesDisjunction->m_numSubpatterns)); } - ParenthesesDisjunctionContext* next; + static size_t allocationSize(unsigned numberOfSubpatterns) + { + static_assert(alignof(ParenthesesDisjunctionContext) <= sizeof(void*), ""); + size_t rawSize = (sizeof(ParenthesesDisjunctionContext) - sizeof(unsigned) + (Checked<size_t>(numberOfSubpatterns) * 2U) * sizeof(unsigned)).unsafeGet(); + size_t roundedSize = WTF::roundUpToMultipleOf<sizeof(void*)>(rawSize); + RELEASE_ASSERT(roundedSize >= rawSize); + return roundedSize; + } + + ParenthesesDisjunctionContext* next { nullptr }; unsigned subpatternBackup[1]; }; ParenthesesDisjunctionContext* allocParenthesesDisjunctionContext(ByteDisjunction* disjunction, unsigned* output, ByteTerm& term) { - size_t size = sizeof(ParenthesesDisjunctionContext) - sizeof(unsigned) + (term.atom.parenthesesDisjunction->m_numSubpatterns << 1) * sizeof(unsigned) + sizeof(DisjunctionContext) - sizeof(uintptr_t) + static_cast<size_t>(disjunction->m_frameSize) * sizeof(uintptr_t); + size_t size = (Checked<size_t>(ParenthesesDisjunctionContext::allocationSize(term.atom.parenthesesDisjunction->m_numSubpatterns)) + DisjunctionContext::allocationSize(disjunction->m_frameSize)).unsafeGet(); allocatorPool = allocatorPool->ensureCapacity(size); RELEASE_ASSERT(allocatorPool); return new (allocatorPool->alloc(size)) ParenthesesDisjunctionContext(output, term); @@ -1630,7 +1644,6 @@ public: , unicode(pattern->unicode()) , output(output) , input(input, start, length, pattern->unicode()) - , allocatorPool(0) , startOffset(start) , remainingMatchCount(matchLimit) { @@ -1641,7 +1654,7 @@ private: bool unicode; unsigned* output; InputStream input; - BumpPointerPool* allocatorPool; + WTF::BumpPointerPool* allocatorPool { nullptr }; unsigned startOffset; unsigned remainingMatchCount; }; @@ -1740,7 +1753,7 @@ public: void atomParenthesesOnceBegin(unsigned subpatternId, bool capture, unsigned inputPosition, unsigned frameLocation, unsigned alternativeFrameLocation) { - unsigned beginTerm = m_bodyDisjunction->terms.size(); + int beginTerm = m_bodyDisjunction->terms.size(); m_bodyDisjunction->terms.append(ByteTerm(ByteTerm::TypeParenthesesSubpatternOnceBegin, subpatternId, capture, false, inputPosition)); m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].frameLocation = frameLocation; diff --git a/src/3rdparty/masm/yarr/YarrJIT.cpp b/src/3rdparty/masm/yarr/YarrJIT.cpp index da65b772f7..1c8138c66e 100644 --- a/src/3rdparty/masm/yarr/YarrJIT.cpp +++ b/src/3rdparty/masm/yarr/YarrJIT.cpp @@ -37,15 +37,12 @@ #if ENABLE(YARR_JIT) -using namespace WTF; - namespace JSC { namespace Yarr { template<YarrJITCompileMode compileMode> class YarrGenerator : private DefaultMacroAssembler { - friend void jitCompile(VM*, YarrCodeBlock&, const String& pattern, unsigned& numSubpatterns, const char*& error, bool ignoreCase, bool multiline); -#if CPU(ARM) +#if CPU(ARM_THUMB2) static const RegisterID input = ARMRegisters::r0; static const RegisterID index = ARMRegisters::r1; static const RegisterID length = ARMRegisters::r2; @@ -477,6 +474,12 @@ class YarrGenerator : private DefaultMacroAssembler { return branch32(BelowOrEqual, index, length); } + Jump checkNotEnoughInput(RegisterID additionalAmount) + { + add32(index, additionalAmount); + return branch32(Above, additionalAmount, length); + } + Jump checkInput() { return branch32(BelowOrEqual, index, length); @@ -559,6 +562,16 @@ class YarrGenerator : private DefaultMacroAssembler { } #endif + void readCharacterDontDecodeSurrogates(Checked<unsigned> negativeCharacterOffset, RegisterID resultReg, RegisterID indexReg = index) + { + BaseIndex address = negativeOffsetIndexedAddress(negativeCharacterOffset, resultReg, indexReg); + + if (m_charSize == Char8) + load8(address, resultReg); + else + load16Unaligned(address, resultReg); + } + void readCharacter(Checked<unsigned> negativeCharacterOffset, RegisterID resultReg, RegisterID indexReg = index) { BaseIndex address = negativeOffsetIndexedAddress(negativeCharacterOffset, resultReg, indexReg); @@ -809,16 +822,16 @@ class YarrGenerator : private DefaultMacroAssembler { // The operation, as a YarrOpCode, and also a reference to the PatternTerm. YarrOpCode m_op; - PatternTerm* m_term; + PatternTerm* m_term = nullptr; // For alternatives, this holds the PatternAlternative and doubly linked // references to this alternative's siblings. In the case of the // OpBodyAlternativeEnd node at the end of a section of repeating nodes, // m_nextOp will reference the OpBodyAlternativeBegin node of the first // repeating alternative. - PatternAlternative* m_alternative; - size_t m_previousOp; - size_t m_nextOp; + PatternAlternative* m_alternative = nullptr; + size_t m_previousOp = 0; + size_t m_nextOp = 0; // Used to record a set of Jumps out of the generated code, typically // used for jumps out to backtracking code, and a single reentry back @@ -1119,6 +1132,228 @@ class YarrGenerator : private DefaultMacroAssembler { backtrackTermDefault(opIndex); } +#if ENABLE(YARR_JIT_BACKREFERENCES) + void matchBackreference(size_t opIndex, JumpList& characterMatchFails, RegisterID character, RegisterID patternIndex, RegisterID patternCharacter) + { + YarrOp& op = m_ops[opIndex]; + PatternTerm* term = op.m_term; + unsigned subpatternId = term->backReferenceSubpatternId; + + Label loop(this); + + readCharacterDontDecodeSurrogates(0, patternCharacter, patternIndex); + readCharacterDontDecodeSurrogates(m_checkedOffset - term->inputPosition, character); + + if (!m_pattern.ignoreCase()) + characterMatchFails.append(branch32(NotEqual, character, patternCharacter)); + else { + Jump charactersMatch = branch32(Equal, character, patternCharacter); + ExtendedAddress characterTableEntry(character, reinterpret_cast<intptr_t>(&canonicalTableLChar)); + load16(characterTableEntry, character); + ExtendedAddress patternTableEntry(patternCharacter, reinterpret_cast<intptr_t>(&canonicalTableLChar)); + load16(patternTableEntry, patternCharacter); + characterMatchFails.append(branch32(NotEqual, character, patternCharacter)); + charactersMatch.link(this); + } + + + add32(TrustedImm32(1), index); + add32(TrustedImm32(1), patternIndex); + + branch32(NotEqual, patternIndex, Address(output, ((subpatternId << 1) + 1) * sizeof(int))).linkTo(loop, this); + } + + void generateBackReference(size_t opIndex) + { + YarrOp& op = m_ops[opIndex]; + PatternTerm* term = op.m_term; + + if (m_pattern.ignoreCase() && m_charSize != Char8) { + m_failureReason = JITFailureReason::BackReference; + return; + } + + unsigned subpatternId = term->backReferenceSubpatternId; + unsigned parenthesesFrameLocation = term->frameLocation; + + const RegisterID characterOrTemp = regT0; + const RegisterID patternIndex = regT1; + const RegisterID patternTemp = regT2; + + storeToFrame(index, parenthesesFrameLocation + BackTrackInfoBackReference::beginIndex()); + if (term->quantityType != QuantifierFixedCount || term->quantityMaxCount != 1) + storeToFrame(TrustedImm32(0), parenthesesFrameLocation + BackTrackInfoBackReference::matchAmountIndex()); + + JumpList matches; + + if (term->quantityType != QuantifierNonGreedy) { + load32(Address(output, (subpatternId << 1) * sizeof(int)), patternIndex); + load32(Address(output, ((subpatternId << 1) + 1) * sizeof(int)), patternTemp); + + // An empty match is successful without consuming characters + if (term->quantityType != QuantifierFixedCount || term->quantityMaxCount != 1) { + matches.append(branch32(Equal, TrustedImm32(-1), patternIndex)); + matches.append(branch32(Equal, patternIndex, patternTemp)); + } else { + Jump zeroLengthMatch = branch32(Equal, TrustedImm32(-1), patternIndex); + Jump tryNonZeroMatch = branch32(NotEqual, patternIndex, patternTemp); + zeroLengthMatch.link(this); + storeToFrame(TrustedImm32(1), parenthesesFrameLocation + BackTrackInfoBackReference::matchAmountIndex()); + matches.append(jump()); + tryNonZeroMatch.link(this); + } + } + + switch (term->quantityType) { + case QuantifierFixedCount: { + Label outerLoop(this); + + // PatternTemp should contain pattern end index at this point + sub32(patternIndex, patternTemp); + if (m_checkedOffset - term->inputPosition) + sub32(Imm32((m_checkedOffset - term->inputPosition).unsafeGet()), patternTemp); + op.m_jumps.append(checkNotEnoughInput(patternTemp)); + + matchBackreference(opIndex, op.m_jumps, characterOrTemp, patternIndex, patternTemp); + + if (term->quantityMaxCount != 1) { + loadFromFrame(parenthesesFrameLocation + BackTrackInfoBackReference::matchAmountIndex(), characterOrTemp); + add32(TrustedImm32(1), characterOrTemp); + storeToFrame(characterOrTemp, parenthesesFrameLocation + BackTrackInfoBackReference::matchAmountIndex()); + matches.append(branch32(Equal, Imm32(term->quantityMaxCount.unsafeGet()), characterOrTemp)); + load32(Address(output, (subpatternId << 1) * sizeof(int)), patternIndex); + load32(Address(output, ((subpatternId << 1) + 1) * sizeof(int)), patternTemp); + jump(outerLoop); + } + matches.link(this); + break; + } + + case QuantifierGreedy: { + JumpList incompleteMatches; + + Label outerLoop(this); + + // PatternTemp should contain pattern end index at this point + sub32(patternIndex, patternTemp); + if (m_checkedOffset - term->inputPosition) + sub32(Imm32((m_checkedOffset - term->inputPosition).unsafeGet()), patternTemp); + matches.append(checkNotEnoughInput(patternTemp)); + + matchBackreference(opIndex, incompleteMatches, characterOrTemp, patternIndex, patternTemp); + + loadFromFrame(parenthesesFrameLocation + BackTrackInfoBackReference::matchAmountIndex(), characterOrTemp); + add32(TrustedImm32(1), characterOrTemp); + storeToFrame(characterOrTemp, parenthesesFrameLocation + BackTrackInfoBackReference::matchAmountIndex()); + if (term->quantityMaxCount != quantifyInfinite) + matches.append(branch32(Equal, Imm32(term->quantityMaxCount.unsafeGet()), characterOrTemp)); + load32(Address(output, (subpatternId << 1) * sizeof(int)), patternIndex); + load32(Address(output, ((subpatternId << 1) + 1) * sizeof(int)), patternTemp); + + // Store current index in frame for restoring after a partial match + storeToFrame(index, parenthesesFrameLocation + BackTrackInfoBackReference::beginIndex()); + jump(outerLoop); + + incompleteMatches.link(this); + loadFromFrame(parenthesesFrameLocation + BackTrackInfoBackReference::beginIndex(), index); + + matches.link(this); + op.m_reentry = label(); + break; + } + + case QuantifierNonGreedy: { + JumpList incompleteMatches; + + matches.append(jump()); + + op.m_reentry = label(); + + load32(Address(output, (subpatternId << 1) * sizeof(int)), patternIndex); + load32(Address(output, ((subpatternId << 1) + 1) * sizeof(int)), patternTemp); + + // An empty match is successful without consuming characters + Jump zeroLengthMatch = branch32(Equal, TrustedImm32(-1), patternIndex); + Jump tryNonZeroMatch = branch32(NotEqual, patternIndex, patternTemp); + zeroLengthMatch.link(this); + storeToFrame(TrustedImm32(1), parenthesesFrameLocation + BackTrackInfoBackReference::matchAmountIndex()); + matches.append(jump()); + tryNonZeroMatch.link(this); + + // Check if we have input remaining to match + sub32(patternIndex, patternTemp); + if (m_checkedOffset - term->inputPosition) + sub32(Imm32((m_checkedOffset - term->inputPosition).unsafeGet()), patternTemp); + matches.append(checkNotEnoughInput(patternTemp)); + + storeToFrame(index, parenthesesFrameLocation + BackTrackInfoBackReference::beginIndex()); + + matchBackreference(opIndex, incompleteMatches, characterOrTemp, patternIndex, patternTemp); + + matches.append(jump()); + + incompleteMatches.link(this); + loadFromFrame(parenthesesFrameLocation + BackTrackInfoBackReference::beginIndex(), index); + + matches.link(this); + break; + } + } + } + void backtrackBackReference(size_t opIndex) + { + YarrOp& op = m_ops[opIndex]; + PatternTerm* term = op.m_term; + + unsigned subpatternId = term->backReferenceSubpatternId; + + m_backtrackingState.link(this); + op.m_jumps.link(this); + + JumpList failures; + + unsigned parenthesesFrameLocation = term->frameLocation; + switch (term->quantityType) { + case QuantifierFixedCount: + loadFromFrame(parenthesesFrameLocation + BackTrackInfoBackReference::beginIndex(), index); + break; + + case QuantifierGreedy: { + const RegisterID matchAmount = regT0; + const RegisterID patternStartIndex = regT1; + const RegisterID patternEndIndexOrLen = regT2; + + loadFromFrame(parenthesesFrameLocation + BackTrackInfoBackReference::matchAmountIndex(), matchAmount); + failures.append(branchTest32(Zero, matchAmount)); + + load32(Address(output, (subpatternId << 1) * sizeof(int)), patternStartIndex); + load32(Address(output, ((subpatternId << 1) + 1) * sizeof(int)), patternEndIndexOrLen); + sub32(patternStartIndex, patternEndIndexOrLen); + sub32(patternEndIndexOrLen, index); + + sub32(TrustedImm32(1), matchAmount); + storeToFrame(matchAmount, parenthesesFrameLocation + BackTrackInfoBackReference::matchAmountIndex()); + jump(op.m_reentry); + break; + } + + case QuantifierNonGreedy: { + const RegisterID matchAmount = regT0; + + loadFromFrame(parenthesesFrameLocation + BackTrackInfoBackReference::matchAmountIndex(), matchAmount); + if (term->quantityMaxCount != quantifyInfinite) + failures.append(branch32(AboveOrEqual, Imm32(term->quantityMaxCount.unsafeGet()), matchAmount)); + add32(TrustedImm32(1), matchAmount); + storeToFrame(matchAmount, parenthesesFrameLocation + BackTrackInfoBackReference::matchAmountIndex()); + jump(op.m_reentry); + break; + } + } + failures.link(this); + m_backtrackingState.fallthrough(); + } +#endif + void generatePatternCharacterOnce(size_t opIndex) { YarrOp& op = m_ops[opIndex]; @@ -1141,12 +1376,16 @@ class YarrGenerator : private DefaultMacroAssembler { } const RegisterID character = regT0; +#if CPU(X86_64) || CPU(ARM64) + unsigned maxCharactersAtOnce = m_charSize == Char8 ? 8 : 4; +#else unsigned maxCharactersAtOnce = m_charSize == Char8 ? 4 : 2; - unsigned ignoreCaseMask = 0; +#endif + uint64_t ignoreCaseMask = 0; #if CPU(BIG_ENDIAN) - int allCharacters = ch << (m_charSize == Char8 ? 24 : 16); + uint64_t allCharacters = ch << (m_charSize == Char8 ? 24 : 16); #else - int allCharacters = ch; + uint64_t allCharacters = ch; #endif unsigned numberCharacters; unsigned startTermPosition = term->inputPosition; @@ -1155,16 +1394,19 @@ class YarrGenerator : private DefaultMacroAssembler { // upper & lower case representations are converted to a character class. ASSERT(!m_pattern.ignoreCase() || isASCIIAlpha(ch) || isCanonicallyUnique(ch, m_canonicalMode)); - if (m_pattern.ignoreCase() && isASCIIAlpha(ch)) + if (m_pattern.ignoreCase() && isASCIIAlpha(ch)) { #if CPU(BIG_ENDIAN) ignoreCaseMask |= 32 << (m_charSize == Char8 ? 24 : 16); #else ignoreCaseMask |= 32; #endif + } for (numberCharacters = 1; numberCharacters < maxCharactersAtOnce && nextOp->m_op == OpTerm; ++numberCharacters, nextOp = &m_ops[opIndex + numberCharacters]) { PatternTerm* nextTerm = nextOp->m_term; - + + // YarrJIT handles decoded surrogate pair as one character if unicode flag is enabled. + // Note that the numberCharacters become 1 while the width of the pattern character becomes 32bit in this case. if (nextTerm->type != PatternTerm::TypePatternCharacter || nextTerm->quantityType != QuantifierFixedCount || nextTerm->quantityMaxCount != 1 @@ -1192,49 +1434,132 @@ class YarrGenerator : private DefaultMacroAssembler { // upper & lower case representations are converted to a character class. ASSERT(!m_pattern.ignoreCase() || isASCIIAlpha(currentCharacter) || isCanonicallyUnique(currentCharacter, m_canonicalMode)); - allCharacters |= (currentCharacter << shiftAmount); + allCharacters |= (static_cast<uint64_t>(currentCharacter) << shiftAmount); if ((m_pattern.ignoreCase()) && (isASCIIAlpha(currentCharacter))) - ignoreCaseMask |= 32 << shiftAmount; + ignoreCaseMask |= 32ULL << shiftAmount; } + if (m_decodeSurrogatePairs) + op.m_jumps.append(jumpIfNoAvailableInput()); + if (m_charSize == Char8) { + auto check1 = [&] (Checked<unsigned> offset, UChar32 characters) { + op.m_jumps.append(jumpIfCharNotEquals(characters, offset, character)); + }; + + auto check2 = [&] (Checked<unsigned> offset, uint16_t characters, uint16_t mask) { + load16Unaligned(negativeOffsetIndexedAddress(offset, character), character); + if (mask) + or32(Imm32(mask), character); + op.m_jumps.append(branch32(NotEqual, character, Imm32(characters | mask))); + }; + + auto check4 = [&] (Checked<unsigned> offset, unsigned characters, unsigned mask) { + if (mask) { + load32WithUnalignedHalfWords(negativeOffsetIndexedAddress(offset, character), character); + if (mask) + or32(Imm32(mask), character); + op.m_jumps.append(branch32(NotEqual, character, Imm32(characters | mask))); + return; + } + op.m_jumps.append(branch32WithUnalignedHalfWords(NotEqual, negativeOffsetIndexedAddress(offset, character), TrustedImm32(characters))); + }; + +#if CPU(X86_64) || CPU(ARM64) + auto check8 = [&] (Checked<unsigned> offset, uint64_t characters, uint64_t mask) { + load64(negativeOffsetIndexedAddress(offset, character), character); + if (mask) + or64(TrustedImm64(mask), character); + op.m_jumps.append(branch64(NotEqual, character, TrustedImm64(characters | mask))); + }; +#endif + switch (numberCharacters) { case 1: - op.m_jumps.append(jumpIfCharNotEquals(ch, m_checkedOffset - startTermPosition, character)); + // Use 32bit width of allCharacters since Yarr counts surrogate pairs as one character with unicode flag. + check1(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff); return; case 2: { - load16Unaligned(negativeOffsetIndexedAddress(m_checkedOffset - startTermPosition, character), character); - break; + check2(m_checkedOffset - startTermPosition, allCharacters & 0xffff, ignoreCaseMask & 0xffff); + return; } case 3: { - load16Unaligned(negativeOffsetIndexedAddress(m_checkedOffset - startTermPosition, character), character); - if (ignoreCaseMask) - or32(Imm32(ignoreCaseMask), character); - op.m_jumps.append(branch32(NotEqual, character, Imm32((allCharacters & 0xffff) | ignoreCaseMask))); - op.m_jumps.append(jumpIfCharNotEquals(allCharacters >> 16, m_checkedOffset - startTermPosition - 2, character)); + check2(m_checkedOffset - startTermPosition, allCharacters & 0xffff, ignoreCaseMask & 0xffff); + check1(m_checkedOffset - startTermPosition - 2, (allCharacters >> 16) & 0xff); return; } case 4: { - load32WithUnalignedHalfWords(negativeOffsetIndexedAddress(m_checkedOffset- startTermPosition, character), character); - break; + check4(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff, ignoreCaseMask & 0xffffffff); + return; + } +#if CPU(X86_64) || CPU(ARM64) + case 5: { + check4(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff, ignoreCaseMask & 0xffffffff); + check1(m_checkedOffset - startTermPosition - 4, (allCharacters >> 32) & 0xff); + return; + } + case 6: { + check4(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff, ignoreCaseMask & 0xffffffff); + check2(m_checkedOffset - startTermPosition - 4, (allCharacters >> 32) & 0xffff, (ignoreCaseMask >> 32) & 0xffff); + return; + } + case 7: { + check4(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff, ignoreCaseMask & 0xffffffff); + check2(m_checkedOffset - startTermPosition - 4, (allCharacters >> 32) & 0xffff, (ignoreCaseMask >> 32) & 0xffff); + check1(m_checkedOffset - startTermPosition - 6, (allCharacters >> 48) & 0xff); + return; + } + case 8: { + check8(m_checkedOffset - startTermPosition, allCharacters, ignoreCaseMask); + return; } +#endif } } else { + auto check1 = [&] (Checked<unsigned> offset, UChar32 characters) { + op.m_jumps.append(jumpIfCharNotEquals(characters, offset, character)); + }; + + auto check2 = [&] (Checked<unsigned> offset, unsigned characters, unsigned mask) { + if (mask) { + load32WithUnalignedHalfWords(negativeOffsetIndexedAddress(offset, character), character); + if (mask) + or32(Imm32(mask), character); + op.m_jumps.append(branch32(NotEqual, character, Imm32(characters | mask))); + return; + } + op.m_jumps.append(branch32WithUnalignedHalfWords(NotEqual, negativeOffsetIndexedAddress(offset, character), TrustedImm32(characters))); + }; + +#if CPU(X86_64) || CPU(ARM64) + auto check4 = [&] (Checked<unsigned> offset, uint64_t characters, uint64_t mask) { + load64(negativeOffsetIndexedAddress(offset, character), character); + if (mask) + or64(TrustedImm64(mask), character); + op.m_jumps.append(branch64(NotEqual, character, TrustedImm64(characters | mask))); + }; +#endif + switch (numberCharacters) { case 1: - op.m_jumps.append(jumpIfCharNotEquals(ch, m_checkedOffset - term->inputPosition, character)); + // Use 32bit width of allCharacters since Yarr counts surrogate pairs as one character with unicode flag. + check1(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff); return; case 2: - load32WithUnalignedHalfWords(negativeOffsetIndexedAddress(m_checkedOffset- term->inputPosition, character), character); - break; + check2(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff, ignoreCaseMask & 0xffffffff); + return; +#if CPU(X86_64) || CPU(ARM64) + case 3: + check2(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff, ignoreCaseMask & 0xffffffff); + check1(m_checkedOffset - startTermPosition - 2, (allCharacters >> 32) & 0xffff); + return; + case 4: + check4(m_checkedOffset - startTermPosition, allCharacters, ignoreCaseMask); + return; +#endif } } - - if (ignoreCaseMask) - or32(Imm32(ignoreCaseMask), character); - op.m_jumps.append(branch32(NotEqual, character, Imm32(allCharacters | ignoreCaseMask))); - return; } void backtrackPatternCharacterOnce(size_t opIndex) { @@ -1250,6 +1575,9 @@ class YarrGenerator : private DefaultMacroAssembler { const RegisterID character = regT0; const RegisterID countRegister = regT1; + if (m_decodeSurrogatePairs) + op.m_jumps.append(jumpIfNoAvailableInput()); + move(index, countRegister); Checked<unsigned> scaledMaxCount = term->quantityMaxCount; scaledMaxCount *= U_IS_BMP(ch) ? 1 : 2; @@ -1403,8 +1731,10 @@ class YarrGenerator : private DefaultMacroAssembler { const RegisterID character = regT0; - if (m_decodeSurrogatePairs) + if (m_decodeSurrogatePairs) { + op.m_jumps.append(jumpIfNoAvailableInput()); storeToFrame(index, term->frameLocation + BackTrackInfoCharacterClass::beginIndex()); + } JumpList matchDest; readCharacter(m_checkedOffset - term->inputPosition, character); @@ -1451,6 +1781,9 @@ class YarrGenerator : private DefaultMacroAssembler { const RegisterID character = regT0; const RegisterID countRegister = regT1; + if (m_decodeSurrogatePairs) + op.m_jumps.append(jumpIfNoAvailableInput()); + move(index, countRegister); sub32(Imm32(term->quantityMaxCount.unsafeGet()), countRegister); @@ -1780,13 +2113,19 @@ class YarrGenerator : private DefaultMacroAssembler { break; case PatternTerm::TypeForwardReference: + m_failureReason = JITFailureReason::ForwardReference; break; case PatternTerm::TypeParenthesesSubpattern: case PatternTerm::TypeParentheticalAssertion: RELEASE_ASSERT_NOT_REACHED(); + case PatternTerm::TypeBackReference: +#if ENABLE(YARR_JIT_BACKREFERENCES) + generateBackReference(opIndex); +#else m_failureReason = JITFailureReason::BackReference; +#endif break; case PatternTerm::TypeDotStarEnclosure: generateDotStarEnclosure(opIndex); @@ -1846,18 +2185,23 @@ class YarrGenerator : private DefaultMacroAssembler { break; case PatternTerm::TypeForwardReference: + m_failureReason = JITFailureReason::ForwardReference; break; case PatternTerm::TypeParenthesesSubpattern: case PatternTerm::TypeParentheticalAssertion: RELEASE_ASSERT_NOT_REACHED(); - case PatternTerm::TypeDotStarEnclosure: - backtrackDotStarEnclosure(opIndex); - break; - case PatternTerm::TypeBackReference: +#if ENABLE(YARR_JIT_BACKREFERENCES) + backtrackBackReference(opIndex); +#else m_failureReason = JITFailureReason::BackReference; +#endif + break; + + case PatternTerm::TypeDotStarEnclosure: + backtrackDotStarEnclosure(opIndex); break; } } @@ -2157,7 +2501,7 @@ class YarrGenerator : private DefaultMacroAssembler { } // If the parentheses are quantified Greedy then add a label to jump back - // to if get a failed match from after the parentheses. For NonGreedy + // to if we get a failed match from after the parentheses. For NonGreedy // parentheses, link the jump from before the subpattern to here. if (term->quantityType == QuantifierGreedy) op.m_reentry = label(); @@ -2221,11 +2565,11 @@ class YarrGenerator : private DefaultMacroAssembler { // match within the parentheses, or the second having skipped over them. // - To check for empty matches, which must be rejected. // - // At the head of a NonGreedy set of parentheses we'll immediately set the - // value on the stack to -1 (indicating a match skipping the subpattern), + // At the head of a NonGreedy set of parentheses we'll immediately set 'begin' + // in the backtrack info to -1 (indicating a match skipping the subpattern), // and plant a jump to the end. We'll also plant a label to backtrack to - // to reenter the subpattern later, with a store to set up index on the - // second iteration. + // to reenter the subpattern later, with a store to set 'begin' to current index + // on the second iteration. // // FIXME: for capturing parens, could use the index in the capture array? if (term->quantityType == QuantifierGreedy || term->quantityType == QuantifierNonGreedy) { @@ -2312,7 +2656,7 @@ class YarrGenerator : private DefaultMacroAssembler { } // If the parentheses are quantified Greedy then add a label to jump back - // to if get a failed match from after the parentheses. For NonGreedy + // to if we get a failed match from after the parentheses. For NonGreedy // parentheses, link the jump from before the subpattern to here. if (term->quantityType == QuantifierGreedy) { if (term->quantityMaxCount != quantifyInfinite) @@ -2324,6 +2668,7 @@ class YarrGenerator : private DefaultMacroAssembler { } else if (term->quantityType == QuantifierNonGreedy) { YarrOp& beginOp = m_ops[op.m_previousOp]; beginOp.m_jumps.link(this); + op.m_reentry = label(); } #else // !YARR_JIT_ALL_PARENS_EXPRESSIONS RELEASE_ASSERT_NOT_REACHED(); @@ -2385,6 +2730,7 @@ class YarrGenerator : private DefaultMacroAssembler { do { --opIndex; + YarrOp& op = m_ops[opIndex]; switch (op.m_op) { @@ -2881,32 +3227,32 @@ class YarrGenerator : private DefaultMacroAssembler { if (term->quantityType != QuantifierFixedCount) { m_backtrackingState.link(this); - if (term->quantityType == QuantifierGreedy) { - RegisterID currParenContextReg = regT0; - RegisterID newParenContextReg = regT1; + RegisterID currParenContextReg = regT0; + RegisterID newParenContextReg = regT1; - loadFromFrame(parenthesesFrameLocation + BackTrackInfoParentheses::parenContextHeadIndex(), currParenContextReg); + loadFromFrame(parenthesesFrameLocation + BackTrackInfoParentheses::parenContextHeadIndex(), currParenContextReg); - restoreParenContext(currParenContextReg, regT2, term->parentheses.subpatternId, term->parentheses.lastSubpatternId, parenthesesFrameLocation); + restoreParenContext(currParenContextReg, regT2, term->parentheses.subpatternId, term->parentheses.lastSubpatternId, parenthesesFrameLocation); - freeParenContext(currParenContextReg, newParenContextReg); - storeToFrame(newParenContextReg, parenthesesFrameLocation + BackTrackInfoParentheses::parenContextHeadIndex()); - const RegisterID countTemporary = regT0; - loadFromFrame(parenthesesFrameLocation + BackTrackInfoParentheses::matchAmountIndex(), countTemporary); - Jump zeroLengthMatch = branchTest32(Zero, countTemporary); + freeParenContext(currParenContextReg, newParenContextReg); + storeToFrame(newParenContextReg, parenthesesFrameLocation + BackTrackInfoParentheses::parenContextHeadIndex()); - sub32(TrustedImm32(1), countTemporary); - storeToFrame(countTemporary, parenthesesFrameLocation + BackTrackInfoParentheses::matchAmountIndex()); + const RegisterID countTemporary = regT0; + loadFromFrame(parenthesesFrameLocation + BackTrackInfoParentheses::matchAmountIndex(), countTemporary); + Jump zeroLengthMatch = branchTest32(Zero, countTemporary); - jump(m_ops[op.m_nextOp].m_reentry); + sub32(TrustedImm32(1), countTemporary); + storeToFrame(countTemporary, parenthesesFrameLocation + BackTrackInfoParentheses::matchAmountIndex()); - zeroLengthMatch.link(this); + jump(m_ops[op.m_nextOp].m_reentry); - // Clear the flag in the stackframe indicating we didn't run through the subpattern. - storeToFrame(TrustedImm32(-1), parenthesesFrameLocation + BackTrackInfoParentheses::beginIndex()); + zeroLengthMatch.link(this); + // Clear the flag in the stackframe indicating we didn't run through the subpattern. + storeToFrame(TrustedImm32(-1), parenthesesFrameLocation + BackTrackInfoParentheses::beginIndex()); + + if (term->quantityType == QuantifierGreedy) jump(m_ops[op.m_nextOp].m_reentry); - } // If Greedy, jump to the end. if (term->quantityType == QuantifierGreedy) { @@ -2929,13 +3275,14 @@ class YarrGenerator : private DefaultMacroAssembler { if (term->quantityType != QuantifierFixedCount) { m_backtrackingState.link(this); - // Check whether we should backtrack back into the parentheses, or if we - // are currently in a state where we had skipped over the subpattern - // (in which case the flag value on the stack will be -1). unsigned parenthesesFrameLocation = term->frameLocation; - Jump hadSkipped = branch32(Equal, Address(stackPointerRegister, (parenthesesFrameLocation + BackTrackInfoParentheses::beginIndex()) * sizeof(void*)), TrustedImm32(-1)); if (term->quantityType == QuantifierGreedy) { + // Check whether we should backtrack back into the parentheses, or if we + // are currently in a state where we had skipped over the subpattern + // (in which case the flag value on the stack will be -1). + Jump hadSkipped = branch32(Equal, Address(stackPointerRegister, (parenthesesFrameLocation + BackTrackInfoParentheses::beginIndex()) * sizeof(void*)), TrustedImm32(-1)); + // For Greedy parentheses, we skip after having already tried going // through the subpattern, so if we get here we're done. YarrOp& beginOp = m_ops[op.m_previousOp]; @@ -2946,8 +3293,25 @@ class YarrGenerator : private DefaultMacroAssembler { // next. Jump back to the start of the parentheses in the forwards // matching path. ASSERT(term->quantityType == QuantifierNonGreedy); + + const RegisterID beginTemporary = regT0; + const RegisterID countTemporary = regT1; + YarrOp& beginOp = m_ops[op.m_previousOp]; - hadSkipped.linkTo(beginOp.m_reentry, this); + + loadFromFrame(parenthesesFrameLocation + BackTrackInfoParentheses::beginIndex(), beginTemporary); + branch32(Equal, beginTemporary, TrustedImm32(-1)).linkTo(beginOp.m_reentry, this); + + JumpList exceededMatchLimit; + + if (term->quantityMaxCount != quantifyInfinite) { + loadFromFrame(parenthesesFrameLocation + BackTrackInfoParentheses::matchAmountIndex(), countTemporary); + exceededMatchLimit.append(branch32(AboveOrEqual, countTemporary, Imm32(term->quantityMaxCount.unsafeGet()))); + } + + branch32(Above, index, beginTemporary).linkTo(beginOp.m_reentry, this); + + exceededMatchLimit.link(this); } m_backtrackingState.fallthrough(); @@ -3021,7 +3385,7 @@ class YarrGenerator : private DefaultMacroAssembler { // the parentheses. // Supported types of parentheses are 'Once' (quantityMaxCount == 1), // 'Terminal' (non-capturing parentheses quantified as greedy - // and infinite), and 0 based greedy quantified parentheses. + // and infinite), and 0 based greedy / non-greedy quantified parentheses. // Alternatives will use the 'Simple' set of ops if either the // subpattern is terminal (in which case we will never need to // backtrack), or if the subpattern only contains one alternative. @@ -3043,7 +3407,9 @@ class YarrGenerator : private DefaultMacroAssembler { if (term->quantityMinCount && term->quantityMinCount != term->quantityMaxCount) { m_failureReason = JITFailureReason::VariableCountedParenthesisWithNonZeroMinimum; return; - } if (term->quantityMaxCount == 1 && !term->parentheses.isCopy) { + } + + if (term->quantityMaxCount == 1 && !term->parentheses.isCopy) { // Select the 'Once' nodes. parenthesesBeginOpCode = OpParenthesesSubpatternOnceBegin; parenthesesEndOpCode = OpParenthesesSubpatternOnceEnd; @@ -3060,10 +3426,10 @@ class YarrGenerator : private DefaultMacroAssembler { parenthesesEndOpCode = OpParenthesesSubpatternTerminalEnd; } else { #if ENABLE(YARR_JIT_ALL_PARENS_EXPRESSIONS) - // We only handle generic parenthesis with greedy counts. - if (term->quantityType != QuantifierGreedy) { + // We only handle generic parenthesis with non-fixed counts. + if (term->quantityType == QuantifierFixedCount) { // This subpattern is not supported by the JIT. - m_failureReason = JITFailureReason::NonGreedyParenthesizedSubpattern; + m_failureReason = JITFailureReason::FixedCountParenthesizedSubpattern; return; } @@ -3369,7 +3735,7 @@ class YarrGenerator : private DefaultMacroAssembler { // The ABI doesn't guarantee the upper bits are zero on unsigned arguments, so clear them ourselves. zeroExtend32ToPtr(index, index); zeroExtend32ToPtr(length, length); -#elif CPU(ARM) +#elif CPU(ARM_THUMB2) push(ARMRegisters::r4); push(ARMRegisters::r5); push(ARMRegisters::r6); @@ -3422,7 +3788,7 @@ class YarrGenerator : private DefaultMacroAssembler { #elif CPU(ARM64) if (m_decodeSurrogatePairs) popPair(framePointerRegister, linkRegister); -#elif CPU(ARM) +#elif CPU(ARM_THUMB2) pop(ARMRegisters::r8); pop(ARMRegisters::r6); pop(ARMRegisters::r5); @@ -3460,10 +3826,14 @@ public: } #endif -#if ENABLE(YARR_JIT_ALL_PARENS_EXPRESSIONS) - if (m_containsNestedSubpatterns) - codeBlock.setUsesPaternContextBuffer(); + if (m_pattern.m_containsBackreferences +#if ENABLE(YARR_JIT_BACKREFERENCES) + && (compileMode == MatchOnly || (m_pattern.ignoreCase() && m_charSize != Char8)) #endif + ) { + codeBlock.setFallBackWithFailureReason(JITFailureReason::BackReference); + return; + } // We need to compile before generating code since we set flags based on compilation that // are used during generation. @@ -3473,7 +3843,12 @@ public: codeBlock.setFallBackWithFailureReason(*m_failureReason); return; } - + +#if ENABLE(YARR_JIT_ALL_PARENS_EXPRESSIONS) + if (m_containsNestedSubpatterns) + codeBlock.setUsesPatternContextBuffer(); +#endif + generateEnter(); Jump hasInput = checkInput(); @@ -3618,7 +3993,10 @@ static void dumpCompileFailure(JITFailureReason failure) dataLog("Can't JIT a pattern decoding surrogate pairs\n"); break; case JITFailureReason::BackReference: - dataLog("Can't JIT a pattern containing back references\n"); + dataLog("Can't JIT some patterns containing back references\n"); + break; + case JITFailureReason::ForwardReference: + dataLog("Can't JIT a pattern containing forward references\n"); break; case JITFailureReason::VariableCountedParenthesisWithNonZeroMinimum: dataLog("Can't JIT a pattern containing a variable counted parenthesis with a non-zero minimum\n"); @@ -3626,8 +4004,8 @@ static void dumpCompileFailure(JITFailureReason failure) case JITFailureReason::ParenthesizedSubpattern: dataLog("Can't JIT a pattern containing parenthesized subpatterns\n"); break; - case JITFailureReason::NonGreedyParenthesizedSubpattern: - dataLog("Can't JIT a pattern containing non-greedy parenthesized subpatterns\n"); + case JITFailureReason::FixedCountParenthesizedSubpattern: + dataLog("Can't JIT a pattern containing fixed count parenthesized subpatterns\n"); break; case JITFailureReason::ExecutableMemoryAllocationFailure: dataLog("Can't JIT because of failure of allocation of executable memory\n"); diff --git a/src/3rdparty/masm/yarr/YarrJIT.h b/src/3rdparty/masm/yarr/YarrJIT.h index 35a0690f6e..c6410d3c44 100644 --- a/src/3rdparty/masm/yarr/YarrJIT.h +++ b/src/3rdparty/masm/yarr/YarrJIT.h @@ -54,9 +54,10 @@ namespace Yarr { enum class JITFailureReason : uint8_t { DecodeSurrogatePair, BackReference, + ForwardReference, VariableCountedParenthesisWithNonZeroMinimum, ParenthesizedSubpattern, - NonGreedyParenthesizedSubpattern, + FixedCountParenthesizedSubpattern, ExecutableMemoryAllocationFailure, }; @@ -107,7 +108,7 @@ public: #if ENABLE(YARR_JIT_ALL_PARENS_EXPRESSIONS) bool usesPatternContextBuffer() { return m_usesPatternContextBuffer; } - void setUsesPaternContextBuffer() { m_usesPatternContextBuffer = true; } + void setUsesPatternContextBuffer() { m_usesPatternContextBuffer = true; } MatchResult execute(const LChar* input, unsigned start, unsigned length, int* output, void* freeParenContext, unsigned parenContextSize) { diff --git a/src/3rdparty/masm/yarr/YarrParser.h b/src/3rdparty/masm/yarr/YarrParser.h index edc6beb1f0..a18b553ef0 100644 --- a/src/3rdparty/masm/yarr/YarrParser.h +++ b/src/3rdparty/masm/yarr/YarrParser.h @@ -194,7 +194,9 @@ private: // invoked with inCharacterClass set. NO_RETURN_DUE_TO_ASSERT void assertionWordBoundary(bool) { RELEASE_ASSERT_NOT_REACHED(); } NO_RETURN_DUE_TO_ASSERT void atomBackReference(unsigned) { RELEASE_ASSERT_NOT_REACHED(); } - NO_RETURN_DUE_TO_ASSERT void atomNamedBackReference(String) { RELEASE_ASSERT_NOT_REACHED(); } + NO_RETURN_DUE_TO_ASSERT void atomNamedBackReference(const String&) { RELEASE_ASSERT_NOT_REACHED(); } + bool isValidNamedForwardReference(const String&) { RELEASE_ASSERT_NOT_REACHED(); return false; } + NO_RETURN_DUE_TO_ASSERT void atomNamedForwardReference(const String&) { RELEASE_ASSERT_NOT_REACHED(); } private: Delegate& m_delegate; @@ -421,9 +423,16 @@ private: if (!atEndOfPattern() && !inCharacterClass) { if (consume() == '<') { auto groupName = tryConsumeGroupName(); - if (groupName && m_captureGroupNames.contains(groupName.value())) { - delegate.atomNamedBackReference(groupName.value()); - break; + if (groupName) { + if (m_captureGroupNames.contains(groupName.value())) { + delegate.atomNamedBackReference(groupName.value()); + break; + } + + if (delegate.isValidNamedForwardReference(groupName.value())) { + delegate.atomNamedForwardReference(groupName.value()); + break; + } } if (m_isUnicode) { m_errorCode = ErrorCode::InvalidBackreference; @@ -1133,11 +1142,13 @@ private: * void atomCharacterClassRange(UChar32 begin, UChar32 end) * void atomCharacterClassBuiltIn(BuiltInCharacterClassID classID, bool invert) * void atomCharacterClassEnd() - * void atomParenthesesSubpatternBegin(bool capture = true, std::optional<String> groupName); + * void atomParenthesesSubpatternBegin(bool capture = true, Optional<String> groupName); * void atomParentheticalAssertionBegin(bool invert = false); * void atomParenthesesEnd(); * void atomBackReference(unsigned subpatternId); - * void atomNamedBackReference(String subpatternName); + * void atomNamedBackReference(const String& subpatternName); + * bool isValidNamedForwardReference(const String& subpatternName); + * void atomNamedForwardReference(const String& subpatternName); * * void quantifyAtom(unsigned min, unsigned max, bool greedy); * diff --git a/src/3rdparty/masm/yarr/YarrPattern.cpp b/src/3rdparty/masm/yarr/YarrPattern.cpp index ac66ea1b9a..9c1cdadf3f 100644 --- a/src/3rdparty/masm/yarr/YarrPattern.cpp +++ b/src/3rdparty/masm/yarr/YarrPattern.cpp @@ -33,12 +33,9 @@ #include "YarrParser.h" #include <wtf/DataLog.h> #include <wtf/Optional.h> -//#include <wtf/Threading.h> #include <wtf/Vector.h> #include <wtf/text/WTFString.h> -using namespace WTF; - namespace JSC { namespace Yarr { #include "RegExpJitTables.h" @@ -334,7 +331,7 @@ private: ranges.insert(i, CharacterRange(lo, hi)); return; } - // Okay, since we didn't hit the last case, the end of the new range is definitely at or after the begining + // Okay, since we didn't hit the last case, the end of the new range is definitely at or after the beginning // If the new range start at or before the end of the last range, then the overlap (if it starts one after the // end of the last range they concatenate, which is just as good. if (lo <= (ranges[i].end + 1)) { @@ -446,9 +443,9 @@ public: { } - void reset() + void resetForReparsing() { - m_pattern.reset(); + m_pattern.resetForReparsing(); m_characterClassConstructor.reset(); auto body = std::make_unique<PatternDisjunction>(); @@ -456,7 +453,17 @@ public: m_alternative = body->addNewAlternative(); m_pattern.m_disjunctions.append(WTFMove(body)); } - + + void saveUnmatchedNamedForwardReferences() + { + m_unmatchedNamedForwardReferences.shrink(0); + + for (auto& entry : m_pattern.m_namedForwardReferences) { + if (!m_pattern.m_captureGroupNames.contains(entry)) + m_unmatchedNamedForwardReferences.append(entry); + } + } + void assertionBOL() { if (!m_alternative->m_terms.size() && !m_invertParentheticalAssertion) { @@ -666,12 +673,24 @@ public: m_alternative->m_terms.append(PatternTerm(subpatternId)); } - void atomNamedBackReference(String subpatternName) + void atomNamedBackReference(const String& subpatternName) { ASSERT(m_pattern.m_namedGroupToParenIndex.find(subpatternName) != m_pattern.m_namedGroupToParenIndex.end()); atomBackReference(m_pattern.m_namedGroupToParenIndex.get(subpatternName)); } + bool isValidNamedForwardReference(const String& subpatternName) + { + return !m_unmatchedNamedForwardReferences.contains(subpatternName); + } + + void atomNamedForwardReference(const String& subpatternName) + { + if (!m_pattern.m_namedForwardReferences.contains(subpatternName)) + m_pattern.m_namedForwardReferences.append(subpatternName); + m_alternative->m_terms.append(PatternTerm::ForwardReference()); + } + // deep copy the argument disjunction. If filterStartsWithBOL is true, // skip alternatives with m_startsWithBOL set true. PatternDisjunction* copyDisjunction(PatternDisjunction* disjunction, bool filterStartsWithBOL = false) @@ -1079,6 +1098,7 @@ private: YarrPattern& m_pattern; PatternAlternative* m_alternative; CharacterClassConstructor m_characterClassConstructor; + Vector<String> m_unmatchedNamedForwardReferences; void* m_stackLimit; bool m_invertCharacterClass; bool m_invertParentheticalAssertion { false }; @@ -1101,13 +1121,14 @@ ErrorCode YarrPattern::compile(const String& patternString, void* stackLimit) // Quoting Netscape's "What's new in JavaScript 1.2", // "Note: if the number of left parentheses is less than the number specified // in \#, the \# is taken as an octal escape as described in the next row." - if (containsIllegalBackReference()) { + if (containsIllegalBackReference() || containsIllegalNamedForwardReferences()) { if (unicode()) return ErrorCode::InvalidBackreference; unsigned numSubpatterns = m_numSubpatterns; - constructor.reset(); + constructor.saveUnmatchedNamedForwardReferences(); + constructor.resetForReparsing(); ErrorCode error = parse(constructor, patternString, unicode(), numSubpatterns); ASSERT_UNUSED(error, !hasError(error)); ASSERT(numSubpatterns == m_numSubpatterns); @@ -1168,7 +1189,7 @@ void dumpCharacterClass(PrintStream& out, YarrPattern* pattern, CharacterClass* else if (characterClass == pattern->wordcharCharacterClass()) out.print("<word>"); else if (characterClass == pattern->wordUnicodeIgnoreCaseCharCharacterClass()) - out.print("<unicode ignore case>"); + out.print("<unicode word ignore case>"); else if (characterClass == pattern->nondigitsCharacterClass()) out.print("<non-digits>"); else if (characterClass == pattern->nonspacesCharacterClass()) @@ -1176,7 +1197,7 @@ void dumpCharacterClass(PrintStream& out, YarrPattern* pattern, CharacterClass* else if (characterClass == pattern->nonwordcharCharacterClass()) out.print("<non-word>"); else if (characterClass == pattern->nonwordUnicodeIgnoreCaseCharCharacterClass()) - out.print("<unicode non-ignore case>"); + out.print("<unicode non-word ignore case>"); else { bool needMatchesRangesSeperator = false; @@ -1298,75 +1319,7 @@ void PatternTerm::dump(PrintStream& out, YarrPattern* thisPattern, unsigned nest break; case TypeCharacterClass: out.print("character class "); - if (characterClass->m_anyCharacter) - out.print("<any character>"); - else if (characterClass == thisPattern->newlineCharacterClass()) - out.print("<newline>"); - else if (characterClass == thisPattern->digitsCharacterClass()) - out.print("<digits>"); - else if (characterClass == thisPattern->spacesCharacterClass()) - out.print("<whitespace>"); - else if (characterClass == thisPattern->wordcharCharacterClass()) - out.print("<word>"); - else if (characterClass == thisPattern->wordUnicodeIgnoreCaseCharCharacterClass()) - out.print("<unicode ignore case>"); - else if (characterClass == thisPattern->nondigitsCharacterClass()) - out.print("<non-digits>"); - else if (characterClass == thisPattern->nonspacesCharacterClass()) - out.print("<non-whitespace>"); - else if (characterClass == thisPattern->nonwordcharCharacterClass()) - out.print("<non-word>"); - else if (characterClass == thisPattern->nonwordUnicodeIgnoreCaseCharCharacterClass()) - out.print("<unicode non-ignore case>"); - else { - bool needMatchesRangesSeperator = false; - - auto dumpMatches = [&] (const char* prefix, Vector<UChar32> matches) { - size_t matchesSize = matches.size(); - if (matchesSize) { - if (needMatchesRangesSeperator) - out.print(","); - needMatchesRangesSeperator = true; - - out.print(prefix, ":("); - for (size_t i = 0; i < matchesSize; ++i) { - if (i) - out.print(","); - dumpUChar32(out, matches[i]); - } - out.print(")"); - } - }; - - auto dumpRanges = [&] (const char* prefix, Vector<CharacterRange> ranges) { - size_t rangeSize = ranges.size(); - if (rangeSize) { - if (needMatchesRangesSeperator) - out.print(","); - needMatchesRangesSeperator = true; - - out.print(prefix, " ranges:("); - for (size_t i = 0; i < rangeSize; ++i) { - if (i) - out.print(","); - CharacterRange range = ranges[i]; - out.print("("); - dumpUChar32(out, range.begin); - out.print(".."); - dumpUChar32(out, range.end); - out.print(")"); - } - out.print(")"); - } - }; - - out.print("["); - dumpMatches("ASCII", characterClass->m_matches); - dumpRanges("ASCII", characterClass->m_ranges); - dumpMatches("Unicode", characterClass->m_matchesUnicode); - dumpRanges("Unicode", characterClass->m_rangesUnicode); - out.print("]"); - } + dumpCharacterClass(out, thisPattern, characterClass); dumpQuantifier(out); if (quantityType != QuantifierFixedCount || thisPattern->unicode()) out.print(",frame location ", frameLocation); @@ -1439,16 +1392,10 @@ void PatternDisjunction::dump(PrintStream& out, YarrPattern* thisPattern, unsign } } -void YarrPattern::dumpPattern(const String& patternString) +void YarrPattern::dumpPatternString(PrintStream& out, const String& patternString) { - dumpPattern(WTF::dataFile(), patternString); -} + out.print("/", patternString, "/"); -void YarrPattern::dumpPattern(PrintStream& out, const String& patternString) -{ - out.print("RegExp pattern for /"); - out.print(patternString); - out.print("/"); if (global()) out.print("g"); if (ignoreCase()) @@ -1459,6 +1406,18 @@ void YarrPattern::dumpPattern(PrintStream& out, const String& patternString) out.print("u"); if (sticky()) out.print("y"); +} + +void YarrPattern::dumpPattern(const String& patternString) +{ + dumpPattern(WTF::dataFile(), patternString); +} + +void YarrPattern::dumpPattern(PrintStream& out, const String& patternString) +{ + out.print("RegExp pattern for "); + dumpPatternString(out, patternString); + if (m_flags != NoFlags) { bool printSeperator = false; out.print(" ("); diff --git a/src/3rdparty/masm/yarr/YarrPattern.h b/src/3rdparty/masm/yarr/YarrPattern.h index f7ddf861ba..10ea2c5b94 100644 --- a/src/3rdparty/masm/yarr/YarrPattern.h +++ b/src/3rdparty/masm/yarr/YarrPattern.h @@ -355,7 +355,7 @@ struct TermChain { struct YarrPattern { JS_EXPORT_PRIVATE YarrPattern(const String& pattern, RegExpFlags, ErrorCode&, void* stackLimit = nullptr); - void reset() + void resetForReparsing() { m_numSubpatterns = 0; m_maxBackReference = 0; @@ -382,6 +382,7 @@ struct YarrPattern { m_disjunctions.clear(); m_userCharacterClasses.clear(); m_captureGroupNames.shrink(0); + m_namedForwardReferences.shrink(0); } bool containsIllegalBackReference() @@ -389,6 +390,19 @@ struct YarrPattern { return m_maxBackReference > m_numSubpatterns; } + bool containsIllegalNamedForwardReferences() + { + if (m_namedForwardReferences.isEmpty()) + return false; + + for (auto& entry : m_namedForwardReferences) { + if (m_captureGroupNames.contains(entry)) + return true; + } + + return false; + } + bool containsUnsignedLengthPattern() { return m_containsUnsignedLengthPattern; @@ -490,6 +504,7 @@ struct YarrPattern { return unicodePropertiesCached.get(classID); } + void dumpPatternString(PrintStream& out, const String& patternString); void dumpPattern(const String& pattern); void dumpPattern(PrintStream& out, const String& pattern); @@ -513,6 +528,7 @@ struct YarrPattern { Vector<std::unique_ptr<PatternDisjunction>, 4> m_disjunctions; Vector<std::unique_ptr<CharacterClass>> m_userCharacterClasses; Vector<String> m_captureGroupNames; + Vector<String> m_namedForwardReferences; HashMap<String, unsigned> m_namedGroupToParenIndex; private: @@ -555,8 +571,8 @@ private: uintptr_t begin; // Not really needed for greedy quantifiers. uintptr_t matchAmount; // Not really needed for fixed quantifiers. - unsigned beginIndex() { return offsetof(BackTrackInfoBackReference, begin) / sizeof(uintptr_t); } - unsigned matchAmountIndex() { return offsetof(BackTrackInfoBackReference, matchAmount) / sizeof(uintptr_t); } + static unsigned beginIndex() { return offsetof(BackTrackInfoBackReference, begin) / sizeof(uintptr_t); } + static unsigned matchAmountIndex() { return offsetof(BackTrackInfoBackReference, matchAmount) / sizeof(uintptr_t); } }; struct BackTrackInfoAlternative { diff --git a/src/3rdparty/masm/yarr/YarrSyntaxChecker.cpp b/src/3rdparty/masm/yarr/YarrSyntaxChecker.cpp index 9f05f22852..358cc94d6b 100644 --- a/src/3rdparty/masm/yarr/YarrSyntaxChecker.cpp +++ b/src/3rdparty/masm/yarr/YarrSyntaxChecker.cpp @@ -48,7 +48,9 @@ public: void atomParentheticalAssertionBegin(bool = false) {} void atomParenthesesEnd() {} void atomBackReference(unsigned) {} - void atomNamedBackReference(String) {} + void atomNamedBackReference(const String&) {} + bool isValidNamedForwardReference(const String&) { return true; } + void atomNamedForwardReference(const String&) {} void quantifyAtom(unsigned, unsigned, bool) {} void disjunction() {} }; diff --git a/src/3rdparty/masm/yarr/create_regex_tables b/src/3rdparty/masm/yarr/create_regex_tables index 4c3dbbe3fb..992566db77 100644 --- a/src/3rdparty/masm/yarr/create_regex_tables +++ b/src/3rdparty/masm/yarr/create_regex_tables @@ -32,7 +32,7 @@ types = { "nonwordchar": { "UseTable" : True, "Inverse": "wordchar", "data": ['`', (0, ord('0') - 1), (ord('9') + 1, ord('A') - 1), (ord('Z') + 1, ord('_') - 1), (ord('z') + 1, 0x10ffff)]}, "nonwordUnicodeIgnoreCaseChar": { "UseTable" : False, "Inverse": "wordUnicodeIgnoreCaseChar", "data": ['`', (0, ord('0') - 1), (ord('9') + 1, ord('A') - 1), (ord('Z') + 1, ord('_') - 1), (ord('z') + 1, 0x017e), (0x0180, 0x2129), (0x212b, 0x10ffff)]}, "newline": { "UseTable" : False, "data": ['\n', '\r', 0x2028, 0x2029]}, - "spaces": { "UseTable" : True, "data": [' ', ('\t', '\r'), 0xa0, 0x1680, 0x180e, 0x2028, 0x2029, 0x202f, 0x205f, 0x3000, (0x2000, 0x200a), 0xfeff]}, + "spaces": { "UseTable" : True, "data": [' ', ('\t', '\r'), 0xa0, 0x1680, 0x2028, 0x2029, 0x202f, 0x205f, 0x3000, (0x2000, 0x200a), 0xfeff]}, "nonspaces": { "UseTable" : True, "Inverse": "spaces", "data": [(0, ord('\t') - 1), (ord('\r') + 1, ord(' ') - 1), (ord(' ') + 1, 0x009f), (0x00a1, 0x167f), (0x1681, 0x180d), (0x180f, 0x1fff), (0x200b, 0x2027), (0x202a, 0x202e), (0x2030, 0x205e), (0x2060, 0x2fff), (0x3001, 0xfefe), (0xff00, 0x10ffff)]}, "digits": { "UseTable" : False, "data": [('0', '9')]}, "nondigits": { "UseTable" : False, "Inverse": "digits", "data": [(0, ord('0') - 1), (ord('9') + 1, 0x10ffff)] } diff --git a/src/3rdparty/masm/yarr/generateYarrCanonicalizeUnicode b/src/3rdparty/masm/yarr/generateYarrCanonicalizeUnicode index a103bcdf16..95549c7eb5 100644 --- a/src/3rdparty/masm/yarr/generateYarrCanonicalizeUnicode +++ b/src/3rdparty/masm/yarr/generateYarrCanonicalizeUnicode @@ -31,7 +31,6 @@ import optparse import os import re import sys -from sets import Set header = """/* * Copyright (C) 2016 Apple Inc. All rights reserved. @@ -78,9 +77,12 @@ def openOrExit(path, mode): dirname = os.path.dirname(path) if not os.path.isdir(dirname): os.makedirs(dirname) - return open(path, mode) + if sys.version_info.major >= 3: + return open(path, mode, encoding="UTF-8") + else: + return open(path, mode) except IOError as e: - print "I/O error opening {0}, ({1}): {2}".format(path, e.errno, e.strerror) + print("I/O error opening {0}, ({1}): {2}".format(path, e.errno, e.strerror)) exit(1) class Canonicalize: @@ -93,7 +95,7 @@ class Canonicalize: self.canonicalGroups[mapping].append(code) def readCaseFolding(self, file): - codesSeen = Set() + codesSeen = set() for line in file: line = line.split('#', 1)[0] line = line.rstrip() @@ -154,8 +156,8 @@ class Canonicalize: for i in range(len(characterSets)): characters = "" - set = characterSets[i] - for ch in set: + cur_set = characterSets[i] + for ch in cur_set: characters = characters + "0x{character:04x}, ".format(character=ch) file.write("const UChar32 unicodeCharacterSet{index:d}[] = {{ {characters}0 }};\n".format(index=i, characters=characters)) @@ -189,7 +191,7 @@ if __name__ == "__main__": caseFoldingTxtPath = args[0] canonicalizeHPath = args[1] caseFoldingTxtFile = openOrExit(caseFoldingTxtPath, "r") - canonicalizeHFile = openOrExit(canonicalizeHPath, "wb") + canonicalizeHFile = openOrExit(canonicalizeHPath, "w") canonicalize = Canonicalize() canonicalize.readCaseFolding(caseFoldingTxtFile) |