| //------------------------------------------------------------------------------------------------------- |
| // Copyright (C) Microsoft. All rights reserved. |
| // Licensed under the MIT license. See LICENSE.txt file in the project root for full license information. |
| //------------------------------------------------------------------------------------------------------- |
| namespace UnifiedRegex |
| { |
| template <typename C> |
| class CharSet; |
| |
| template <typename C> |
| class RuntimeCharSet; |
| |
| class CharBitvec : private Chars<char> |
| { |
| public: |
| static const int Width = Chars<char>::CharWidth; |
| static const int Size = NumChars; |
| |
| private: |
| static const int wordSize = sizeof(uint32) * 8; |
| static const int vecSize = Size / wordSize; |
| static const uint32 ones = (uint32)-1; |
| |
| static const uint8 oneBits[Size]; |
| |
| uint32 vec[vecSize]; |
| |
| inline static void setrng(uint32 &v, uint l, uint h) |
| { |
| uint w = h - l + 1; |
| if (w == wordSize) |
| { |
| v = ones; |
| } |
| else |
| { |
| v |= ((1U << w) - 1) << l; |
| } |
| } |
| |
| inline static void clearrng(uint32 &v, uint l, uint h) |
| { |
| uint w = h - l + 1; |
| if (w == wordSize) |
| { |
| v = 0; |
| } |
| else |
| { |
| v &= ~(((1U << w) - 1) << l); |
| } |
| } |
| |
| public: |
| inline void CloneFrom(const CharBitvec& other) |
| { |
| for (int w = 0; w < vecSize; w++) |
| { |
| vec[w] = other.vec[w]; |
| } |
| } |
| |
| inline void Clear() |
| { |
| for (int w = 0; w < vecSize; w++) |
| { |
| vec[w] = 0; |
| } |
| } |
| |
| inline void SetAll() |
| { |
| for (int w = 0; w < vecSize; w++) |
| { |
| vec[w] = ones; |
| } |
| } |
| |
| inline void Set(uint k) |
| { |
| Assert(k < Size); |
| __assume(k < Size); |
| if (k < Size) |
| { |
| vec[k / wordSize] |= 1U << (k % wordSize); |
| } |
| } |
| |
| inline void SetRange(uint l, uint h) |
| { |
| Assert(l < Size); |
| Assert(h < Size); |
| __assume(l < Size); |
| __assume(h < Size); |
| if (l < Size && h < Size) |
| { |
| if (l == h) |
| { |
| vec[l / wordSize] |= 1U << (l % wordSize); |
| } |
| else if (l < h) |
| { |
| int lw = l / wordSize; |
| int hw = h / wordSize; |
| int lo = l % wordSize; |
| int hio = h % wordSize; |
| if (lw == hw) |
| { |
| setrng(vec[lw], lo, hio); |
| } |
| else |
| { |
| setrng(vec[lw], lo, wordSize - 1); |
| for (int w = lw + 1; w < hw; w++) |
| { |
| vec[w] = ones; |
| } |
| setrng(vec[hw], 0, hio); |
| } |
| } |
| } |
| } |
| |
| inline void ClearRange(uint l, uint h) |
| { |
| Assert(l < Size); |
| Assert(h < Size); |
| __assume(l < Size); |
| __assume(h < Size); |
| if (l < Size && h < Size) |
| { |
| if (l == h) |
| { |
| vec[l / wordSize] &= ~(1U << (l % wordSize)); |
| } |
| else if (l < h) |
| { |
| int lw = l / wordSize; |
| int hw = h / wordSize; |
| int lo = l % wordSize; |
| int hio = h % wordSize; |
| if (lw == hw) |
| { |
| clearrng(vec[lw], lo, hio); |
| } |
| else |
| { |
| clearrng(vec[lw], lo, wordSize - 1); |
| for (int w = lw + 1; w < hw; w++) |
| { |
| vec[w] = 0; |
| } |
| clearrng(vec[hw], 0, hio); |
| } |
| } |
| } |
| } |
| |
| inline bool IsEmpty() |
| { |
| for (int i = 0; i < vecSize; i++) |
| { |
| if (vec[i] != 0) |
| { |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| inline void UnionInPlace(const CharBitvec& other) |
| { |
| for (int w = 0; w < vecSize; w++) |
| { |
| vec[w] |= other.vec[w]; |
| } |
| } |
| |
| inline bool UnionInPlaceFullCheck(const CharBitvec& other) |
| { |
| bool isFull = true; |
| for (int w = 0; w < vecSize; w++) |
| { |
| vec[w] |= other.vec[w]; |
| if (vec[w] != ones) |
| { |
| isFull = false; |
| } |
| } |
| return isFull; |
| } |
| |
| inline bool Get(uint k) const |
| { |
| Assert(k < Size); |
| __assume(k < Size); |
| return ((vec[k / wordSize] >> (k % wordSize)) & 1) != 0; |
| } |
| |
| inline bool IsFull() const |
| { |
| for (int w = 0; w < vecSize; w++) |
| { |
| if (vec[w] != ones) |
| { |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| inline bool IsSubsetOf(const CharBitvec& other) const |
| { |
| for (int w = 0; w < vecSize; w++) |
| { |
| uint32 v = other.vec[w]; |
| if (v != (vec[w] | v)) |
| { |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| inline bool IsEqualTo(const CharBitvec& other) const |
| { |
| for (int w = 0; w < vecSize; w++) |
| { |
| if (vec[w] != other.vec[w]) |
| { |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| uint Count() const; |
| |
| int NextSet(int k) const; |
| int NextClear(int k) const; |
| |
| template <typename C> |
| void ToComplement(ArenaAllocator* allocator, uint base, CharSet<C>& result) const; |
| |
| template <typename C> |
| void ToEquivClass(ArenaAllocator* allocator, uint base, uint& tblidx, CharSet<C>& result, codepoint_t baseOffset = 0x0) const; |
| }; |
| |
| template <typename C> |
| class CharSet {}; |
| |
| struct CharSetNode : protected Chars<char16> |
| { |
| static const int directBits = Chars<char>::CharWidth; |
| static const uint directSize = Chars<char>::NumChars; |
| |
| static const uint bitsPerInnerLevel = 4; |
| static const uint branchingPerInnerLevel = 1 << bitsPerInnerLevel; |
| static const uint innerMask = branchingPerInnerLevel - 1; |
| |
| static const int bitsPerLeafLevel = CharBitvec::Width; |
| static const int branchingPerLeafLevel = CharBitvec::Size; |
| static const uint leafMask = branchingPerLeafLevel - 1; |
| |
| static const uint levels = 1 + (CharWidth - bitsPerLeafLevel) / bitsPerInnerLevel; |
| |
| inline static uint innerIdx(uint level, uint v) |
| { |
| return (v >> ((level + 1) * bitsPerInnerLevel)) & innerMask; |
| } |
| |
| inline static uint indexToValue(uint level, uint index, uint offset) |
| { |
| Assert((index & innerMask) == index); |
| Assert((uint)(1 << ((level + 1) * bitsPerInnerLevel)) > offset); |
| |
| return (index << ((level + 1) * bitsPerInnerLevel)) + offset; |
| } |
| |
| inline static uint leafIdx(uint v) |
| { |
| return v & leafMask; |
| } |
| |
| inline static uint lim(uint level) |
| { |
| return (1U << (bitsPerLeafLevel + level * bitsPerInnerLevel)) - 1; |
| } |
| |
| inline static uint remain(uint level, uint v) |
| { |
| return v & lim(level); |
| } |
| |
| virtual void FreeSelf(ArenaAllocator* allocator) = 0; |
| virtual CharSetNode* Clone(ArenaAllocator* allocator) const = 0; |
| virtual CharSetNode* Set(ArenaAllocator* allocator, uint level, uint l, uint h) = 0; |
| virtual CharSetNode* ClearRange(ArenaAllocator* allocator, uint level, uint l, uint h) = 0; |
| virtual CharSetNode* UnionInPlace(ArenaAllocator* allocator, uint level, const CharSetNode* other) = 0; |
| virtual bool Get(uint level, uint k) const = 0; |
| virtual void ToComplement(ArenaAllocator* allocator, uint level, uint base, CharSet<Char>& result) const = 0; |
| virtual void ToEquivClassW(ArenaAllocator* allocator, uint level, uint base, uint& tblidx, CharSet<char16>& result) const = 0; |
| virtual void ToEquivClassCP(ArenaAllocator* allocator, uint level, uint base, uint& tblidx, CharSet<codepoint_t>& result, codepoint_t baseOffset) const = 0; |
| virtual bool IsSubsetOf(uint level, const CharSetNode* other) const = 0; |
| virtual bool IsEqualTo(uint level, const CharSetNode* other) const = 0; |
| virtual uint Count(uint level) const = 0; |
| _Success_(return) virtual bool GetNextRange(uint level, Char searchCharStart, _Out_ Char *outLowerChar, _Out_ Char *outHigherChar) const = 0; |
| #if DBG |
| virtual bool IsLeaf() const = 0; |
| #endif |
| |
| static CharSetNode* For(ArenaAllocator* allocator, int level); |
| }; |
| |
| struct CharSetFull : CharSetNode |
| { |
| private: |
| template <typename C> |
| void ToEquivClass(ArenaAllocator* allocator, uint level, uint base, uint& tblidx, CharSet<C>& result, codepoint_t baseOffset = 0x0) const; |
| public: |
| static CharSetFull Instance; |
| static CharSetFull * const TheFullNode; |
| |
| CharSetFull(); |
| |
| void FreeSelf(ArenaAllocator* allocator) override; |
| CharSetNode* Clone(ArenaAllocator* allocator) const override; |
| CharSetNode* Set(ArenaAllocator* allocator, uint level, uint l, uint h) override; |
| CharSetNode* ClearRange(ArenaAllocator* allocator, uint level, uint l, uint h) override; |
| CharSetNode* UnionInPlace(ArenaAllocator* allocator, uint level, const CharSetNode* other) override; |
| bool Get(uint level, uint k) const override; |
| void ToComplement(ArenaAllocator* allocator, uint level, uint base, CharSet<Char>& result) const override; |
| void ToEquivClassW(ArenaAllocator* allocator, uint level, uint base, uint& tblidx, CharSet<char16>& result) const override; |
| void ToEquivClassCP(ArenaAllocator* allocator, uint level, uint base, uint& tblidx, CharSet<codepoint_t>& result, codepoint_t baseOffset) const override; |
| bool IsSubsetOf(uint level, const CharSetNode* other) const override; |
| bool IsEqualTo(uint level, const CharSetNode* other) const override; |
| uint Count(uint level) const override; |
| _Success_(return) bool GetNextRange(uint level, Char searchCharStart, _Out_ Char *outLowerChar, _Out_ Char *outHigherChar) const override; |
| #if DBG |
| bool IsLeaf() const override; |
| #endif |
| }; |
| |
| struct CharSetInner sealed : CharSetNode |
| { |
| private: |
| template <typename C> |
| void ToEquivClass(ArenaAllocator* allocator, uint level, uint base, uint& tblidx, CharSet<C>& result) const; |
| public: |
| CharSetNode * children[branchingPerInnerLevel]; |
| |
| CharSetInner(); |
| void FreeSelf(ArenaAllocator* allocator) override; |
| CharSetNode* Clone(ArenaAllocator* allocator) const override; |
| CharSetNode* Set(ArenaAllocator* allocator, uint level, uint l, uint h) override; |
| CharSetNode* ClearRange(ArenaAllocator* allocator, uint level, uint l, uint h) override; |
| CharSetNode* UnionInPlace(ArenaAllocator* allocator, uint level, const CharSetNode* other) override; |
| bool Get(uint level, uint k) const override; |
| void ToComplement(ArenaAllocator* allocator, uint level, uint base, CharSet<Char>& result) const override; |
| void ToEquivClassW(ArenaAllocator* allocator, uint level, uint base, uint& tblidx, CharSet<char16>& result) const override; |
| void ToEquivClassCP(ArenaAllocator* allocator, uint level, uint base, uint& tblidx, CharSet<codepoint_t>& result, codepoint_t baseOffset) const override; |
| bool IsSubsetOf(uint level, const CharSetNode* other) const override; |
| bool IsEqualTo(uint level, const CharSetNode* other) const override; |
| uint Count(uint level) const override; |
| _Success_(return) bool GetNextRange(uint level, Char searchCharStart, _Out_ Char *outLowerChar, _Out_ Char *outHigherChar) const override; |
| #if DBG |
| bool IsLeaf() const override; |
| #endif |
| }; |
| |
| struct CharSetLeaf sealed : CharSetNode |
| { |
| private: |
| template <typename C> |
| void ToEquivClass(ArenaAllocator* allocator, uint level, uint base, uint& tblidx, CharSet<C>& result, codepoint_t baseOffset = 0x0) const; |
| public: |
| CharBitvec vec; |
| |
| CharSetLeaf(); |
| void FreeSelf(ArenaAllocator* allocator) override; |
| CharSetNode* Clone(ArenaAllocator* allocator) const override; |
| CharSetNode* Set(ArenaAllocator* allocator, uint level, uint l, uint h) override; |
| CharSetNode* ClearRange(ArenaAllocator* allocator, uint level, uint l, uint h) override; |
| CharSetNode* UnionInPlace(ArenaAllocator* allocator, uint level, const CharSetNode* other) override; |
| bool Get(uint level, uint k) const override; |
| void ToComplement(ArenaAllocator* allocator, uint level, uint base, CharSet<Char>& result) const override; |
| void ToEquivClassW(ArenaAllocator* allocator, uint level, uint base, uint& tblidx, CharSet<char16>& result) const override; |
| void ToEquivClassCP(ArenaAllocator* allocator, uint level, uint base, uint& tblidx, CharSet<codepoint_t>& result, codepoint_t baseOffset) const override; |
| bool IsSubsetOf(uint level, const CharSetNode* other) const override; |
| bool IsEqualTo(uint level, const CharSetNode* other) const override; |
| uint Count(uint level) const override; |
| _Success_(return) bool GetNextRange(uint level, Char searchCharStart, _Out_ Char *outLowerChar, _Out_ Char *outHigherChar) const override; |
| #if DBG |
| bool IsLeaf() const override; |
| #endif |
| }; |
| |
| template <> |
| class CharSet<char16> : private Chars<char16> |
| { |
| public: |
| static const uint MaxCompact = 4; |
| |
| static const uint emptySlot = (uint)-1; |
| |
| struct CompactRep |
| { |
| // 1 + number of distinct characters, 1..MaxCompact+1 |
| size_t countPlusOne; |
| // Characters, in no particular order, or (uint)-1 for tail empty slots |
| uint cs[MaxCompact]; |
| uint8 padding[sizeof(CharBitvec) - sizeof(uint) * MaxCompact]; |
| }; |
| |
| struct FullRep |
| { |
| // Trie for remaining characters. Pointer value will be 0 or >> MaxCompact. |
| CharSetNode* root; |
| // Entries for first 256 characters |
| CharBitvec direct; |
| }; |
| |
| union Rep |
| { |
| struct CompactRep compact; |
| struct FullRep full; |
| } rep; |
| |
| static const int compactSize = sizeof(CompactRep); |
| static const int fullSize = sizeof(FullRep); |
| |
| inline bool IsCompact() const { return rep.compact.countPlusOne - 1 <= MaxCompact; } |
| void SwitchRepresentations(ArenaAllocator* allocator); |
| void Sort(); |
| |
| public: |
| CharSet(); |
| void FreeBody(ArenaAllocator* allocator); |
| void Clear(ArenaAllocator* allocator); |
| void CloneFrom(ArenaAllocator* allocator, const CharSet<Char>& other); |
| void CloneNonSurrogateCodeUnitsTo(ArenaAllocator* allocator, CharSet<Char>& other); |
| void CloneSurrogateCodeUnitsTo(ArenaAllocator* allocator, CharSet<Char>& other); |
| |
| inline void Set(ArenaAllocator* allocator, Char kc) { SetRange(allocator, kc, kc); } |
| |
| void SetRange(ArenaAllocator* allocator, Char lc, Char hc); |
| void SubtractRange(ArenaAllocator* allocator, Char lc, Char hc); |
| void SetRanges(ArenaAllocator* allocator, int numSortedPairs, const Char* sortedPairs); |
| void SetNotRanges(ArenaAllocator* allocator, int numSortedPairs, const Char* sortedPairs); |
| void UnionInPlace(ArenaAllocator* allocator, const CharSet<Char>& other); |
| _Success_(return) bool GetNextRange(Char searchCharStart, _Out_ Char *outLowerChar, _Out_ Char *outHigherChar); |
| bool Get_helper(uint k) const; |
| |
| inline bool Get(Char kc) const |
| { |
| if (IsCompact()) |
| { |
| Assert(MaxCompact == 4); |
| return rep.compact.cs[0] == CTU(kc) || |
| rep.compact.cs[1] == CTU(kc) || |
| rep.compact.cs[2] == CTU(kc) || |
| rep.compact.cs[3] == CTU(kc); |
| } |
| else |
| { |
| if (CTU(kc) < CharSetNode::directSize) |
| { |
| return rep.full.direct.Get(CTU(kc)); |
| } |
| else if (rep.full.root == 0) |
| { |
| return false; |
| } |
| else |
| { |
| return Get_helper(CTU(kc)); |
| } |
| } |
| } |
| |
| inline bool IsEmpty() const |
| { |
| return rep.compact.countPlusOne == 1; |
| } |
| |
| inline bool IsSingleton() const |
| { |
| return rep.compact.countPlusOne == 2; |
| } |
| |
| // Helpers to clean up the code |
| |
| inline uint GetCompactLength() const |
| { |
| Assert(IsCompact()); |
| return (uint)(rep.compact.countPlusOne - 1u); |
| } |
| |
| inline void SetCompactLength(size_t length) |
| { |
| rep.compact.countPlusOne = length + 1; |
| } |
| |
| inline uint GetCompactCharU(uint index) const |
| { |
| Assert(index < this->GetCompactLength()); |
| Assert(IsCompact()); |
| Assert(rep.compact.cs[index] <= MaxUChar); |
| return rep.compact.cs[index]; |
| } |
| |
| inline Char GetCompactChar(uint index) const |
| { |
| return (Char)(GetCompactCharU(index)); |
| } |
| |
| //Replaces an existing character with a new value |
| inline void ReplaceCompactCharU(uint index, uint value) |
| { |
| Assert(index < this->GetCompactLength()); |
| Assert(IsCompact()); |
| Assert(value <= MaxUChar); |
| rep.compact.cs[index] = value; |
| } |
| |
| inline void ClearCompactChar(uint index) |
| { |
| Assert(index < this->GetCompactLength()); |
| Assert(IsCompact()); |
| rep.compact.cs[index] = emptySlot; |
| } |
| |
| // Adds the character to the end, assuming there is enough space. (Assert in place) |
| // Increments count. |
| inline void AddCompactCharU(uint value) |
| { |
| Assert(this->GetCompactLength() < MaxCompact); |
| Assert(IsCompact()); |
| rep.compact.cs[this->GetCompactLength()] = value; |
| rep.compact.countPlusOne += 1; |
| } |
| |
| // Adds the character to the end, assuming there is enough space. (Assert in place) |
| // Increments count. |
| inline void AddCompactChar(Char value) |
| { |
| AddCompactCharU((Char)(value)); |
| } |
| |
| // This performs a check to see if the index is the last char, if so sets it to emptySlot |
| // If not, replaces it with last index. |
| inline void RemoveCompactChar(uint index) |
| { |
| Assert(index < this->GetCompactLength()); |
| Assert(IsCompact()); |
| |
| if (index == this->GetCompactLength() - 1) |
| { |
| this->ClearCompactChar(index); |
| } |
| else |
| { |
| this->ReplaceCompactCharU(index, this->GetCompactCharU((uint)this->GetCompactLength() - 1)); |
| } |
| |
| rep.compact.countPlusOne -= 1; |
| } |
| |
| inline char16 Singleton() const |
| { |
| Assert(IsSingleton()); |
| Assert(rep.compact.cs[0] <= MaxUChar); |
| return UTC(rep.compact.cs[0]); |
| } |
| |
| int GetCompactEntries(uint max, __out_ecount(max) Char* entries) const; |
| |
| bool IsSubsetOf(const CharSet<Char>& other) const; |
| bool IsEqualTo(const CharSet<Char>& other) const; |
| |
| inline uint Count() const |
| { |
| if (IsCompact()) |
| { |
| return (uint)rep.compact.countPlusOne - 1; |
| } |
| else if (rep.full.root == 0) |
| { |
| return rep.full.direct.Count(); |
| } |
| else |
| { |
| //The bit vector |
| Assert(rep.full.root == CharSetFull::TheFullNode || rep.full.root->Count(CharSetNode::levels - 1) <= 0xFF00); |
| return rep.full.direct.Count() + (rep.full.root == CharSetFull::TheFullNode ? 0xFF00 : rep.full.root->Count(CharSetNode::levels - 1)); |
| } |
| } |
| |
| // NOTE: These are not 'const' methods since they may sort the compact representation internally |
| void ToComplement(ArenaAllocator* allocator, CharSet<Char>& result); |
| void ToEquivClass(ArenaAllocator* allocator, CharSet<Char>& result); |
| void ToEquivClassCP(ArenaAllocator* allocator, CharSet<codepoint_t>& result, codepoint_t baseOffset); |
| #if ENABLE_REGEX_CONFIG_OPTIONS |
| void Print(DebugWriter* w) const; |
| #endif |
| }; |
| |
| template <> |
| class CharSet<codepoint_t> : private Chars<codepoint_t> |
| { |
| static const int NumberOfPlanes = 17; |
| private: |
| // Character planes are composed of 65536 characters each. |
| // First plane is the Basic Multilingual Plane (characters 0 - 65535) |
| // Every subsequent plane also stores characters in the form [0 - 65535]; to get the actual value, add 'index * 0x10000' to it |
| CharSet<char16> characterPlanes[NumberOfPlanes]; |
| |
| // Takes a character, and returns the index of the CharSet<char16> that holds it. |
| inline int CharToIndex(Char c) const |
| { |
| Assert(c <= Chars<codepoint_t>::MaxUChar); |
| return (int)(CTU(c) / (Chars<char16>::MaxUChar + 1)); |
| } |
| |
| // Takes a character, and removes the offset to make it < 0x10000 |
| inline char16 RemoveOffset(Char c) const |
| { |
| Assert(c <= Chars<codepoint_t>::MaxUChar); |
| return (char16)(CTU(c) % 0x10000); |
| } |
| |
| // Takes a character, and removes the offset to make it < 0x10000 |
| inline Char AddOffset(char16 c, int index) const |
| { |
| Assert(c <= Chars<char16>::MaxUChar); |
| Assert(index >= 0); |
| Assert(index < NumberOfPlanes); |
| return ((Char)c) + 0x10000 * index; |
| } |
| |
| public: |
| CharSet(); |
| void FreeBody(ArenaAllocator* allocator); |
| void Clear(ArenaAllocator* allocator); |
| void CloneFrom(ArenaAllocator* allocator, const CharSet<Char>& other); |
| void CloneSimpleCharsTo(ArenaAllocator* allocator, CharSet<char16>& other) const; |
| |
| inline void CloneNonSurrogateCodeUnitsTo(ArenaAllocator* allocator, CharSet<char16>& other) |
| { |
| Assert(this->SimpleCharCount() > 0); |
| AssertMsg(this->ContainSurrogateCodeUnits(), "This doesn't contain surrogate code units, a simple clone is faster."); |
| this->characterPlanes[0].CloneNonSurrogateCodeUnitsTo(allocator, other); |
| } |
| |
| inline void CloneSurrogateCodeUnitsTo(ArenaAllocator* allocator, CharSet<char16>& other) |
| { |
| Assert(this->SimpleCharCount() > 0); |
| AssertMsg(this->ContainSurrogateCodeUnits(), "This doesn't contain surrogate code units, will not produce any result."); |
| this->characterPlanes[0].CloneSurrogateCodeUnitsTo(allocator, other); |
| } |
| |
| inline void Set(ArenaAllocator* allocator, Char kc) { SetRange(allocator, kc, kc); } |
| |
| inline bool ContainSurrogateCodeUnits() |
| { |
| char16 outLower = 0xFFFF, ignore = 0x0; |
| return this->characterPlanes[0].GetNextRange(0xD800, &outLower, &ignore) ? outLower <= 0xDFFF : false; |
| } |
| |
| void SetRange(ArenaAllocator* allocator, Char lc, Char hc); |
| void SetRanges(ArenaAllocator* allocator, int numSortedPairs, const Char* sortedPairs); |
| void SetNotRanges(ArenaAllocator* allocator, int numSortedPairs, const Char* sortedPairs); |
| void UnionInPlace(ArenaAllocator* allocator, const CharSet<Char>& other); |
| void UnionInPlace(ArenaAllocator* allocator, const CharSet<char16>& other); |
| _Success_(return) bool GetNextRange(Char searchCharStart, _Out_ Char *outLowerChar, _Out_ Char *outHigherChar); |
| |
| inline bool Get(Char kc) const |
| { |
| return this->characterPlanes[CharToIndex(kc)].Get(RemoveOffset(kc)); |
| } |
| |
| inline bool IsEmpty() const |
| { |
| for (int i = 0; i < NumberOfPlanes; i++) |
| { |
| if (!this->characterPlanes[i].IsEmpty()) |
| { |
| return false; |
| } |
| } |
| |
| return true; |
| } |
| |
| inline bool IsSimpleCharASingleton() const |
| { |
| return this->characterPlanes[0].IsSingleton(); |
| } |
| |
| inline char16 SimpleCharSingleton() const |
| { |
| return this->characterPlanes[0].Singleton(); |
| } |
| |
| inline bool IsSingleton() const |
| { |
| return this->Count() == 1; |
| } |
| |
| inline codepoint_t Singleton() const |
| { |
| Assert(IsSingleton()); |
| |
| for (int i = 0; i < NumberOfPlanes; i++) |
| { |
| if (this->characterPlanes[i].IsSingleton()) |
| { |
| return AddOffset(this->characterPlanes[i].Singleton(), i); |
| } |
| } |
| |
| AssertMsg(false, "Should not reach here, first Assert verifies we are a singleton."); |
| return INVALID_CODEPOINT; |
| } |
| |
| bool IsSubsetOf(const CharSet<Char>& other) const; |
| bool IsEqualTo(const CharSet<Char>& other) const; |
| |
| inline uint Count() const |
| { |
| uint totalCount = 0; |
| |
| for (int i = 0; i < NumberOfPlanes; i++) |
| { |
| totalCount += this->characterPlanes[i].Count(); |
| } |
| |
| return totalCount; |
| } |
| |
| inline uint SimpleCharCount() const |
| { |
| return this->characterPlanes[0].Count(); |
| } |
| |
| // NOTE: These are not 'const' methods since they may sort the compact representation internally |
| void ToComplement(ArenaAllocator* allocator, CharSet<Char>& result); |
| void ToSimpleComplement(ArenaAllocator* allocator, CharSet<codepoint_t>& result); |
| void ToSimpleComplement(ArenaAllocator* allocator, CharSet<char16>& result); |
| void ToEquivClass(ArenaAllocator* allocator, CharSet<Char>& result); |
| void ToSurrogateEquivClass(ArenaAllocator* allocator, CharSet<Char>& result); |
| #if ENABLE_REGEX_CONFIG_OPTIONS |
| void Print(DebugWriter* w) const; |
| #endif |
| }; |
| |
| |
| template <> |
| class RuntimeCharSet<char16> : private Chars<char16> |
| { |
| private: |
| // Trie for remaining characters. Pointer value will be 0 or >> MaxCompact. |
| CharSetNode * root; |
| // Entries for first 256 characters |
| CharBitvec direct; |
| |
| public: |
| RuntimeCharSet(); |
| void FreeBody(ArenaAllocator* allocator); |
| void CloneFrom(ArenaAllocator* allocator, const CharSet<Char>& other); |
| bool Get_helper(uint k) const; |
| |
| inline bool Get(Char kc) const |
| { |
| if (CTU(kc) < CharSetNode::directSize) |
| { |
| return direct.Get(CTU(kc)); |
| } |
| else if (root == 0) |
| { |
| return false; |
| } |
| else |
| { |
| return Get_helper(CTU(kc)); |
| } |
| } |
| |
| #if ENABLE_REGEX_CONFIG_OPTIONS |
| void Print(DebugWriter* w) const; |
| #endif |
| }; |
| |
| typedef CharSet<char16> UnicodeCharSet; |
| typedef RuntimeCharSet<char16> UnicodeRuntimeCharSet; |
| } |
