//-------------------------------------------------------------------------------------------------------

// Copyright (C) Microsoft. All rights reserved.

// Licensed under the MIT license. See LICENSE.txt file in the project root for full license information.

//-------------------------------------------------------------------------------------------------------

#include "ParserPch.h"

namespace UnifiedRegex

{

// ----------------------------------------------------------------------

// CharBitVec

// ----------------------------------------------------------------------

inline uint32 popcnt(uint32 x)

{

// sum set bits in every bit pair

x -= (x >> 1) & 0x55555555u;

// sum pairs into quads

x = (x & 0x33333333u) + ((x >> 2) & 0x33333333u);

// sum quads into octets

x = (x + (x >> 4)) & 0x0f0f0f0fu;

// sum octets into topmost octet

x *= 0x01010101u;

return x >> 24;

}

uint CharBitvec::Count() const

{

uint n = 0;

for (int w = 0; w < vecSize; w++)

{

n += popcnt(vec[w]);

}

return n;

}

int CharBitvec::NextSet(int k) const

{

if (k < 0 || k >= Size)

return -1;

uint w = k / wordSize;

uint o = k % wordSize;

uint32 v = vec[w] >> o;

do

{

if (v == 0)

{

k += wordSize - o;

break;

}

else if ((v & 0x1) != 0)

return k;

else

{

v >>= 1;

o++;

k++;

}

}

while (o < wordSize);

w++;

while (w < vecSize)

{

o = 0;

v = vec[w];

do

{

if (v == 0)

{

k += wordSize - o;

break;

}

else if ((v & 0x1) != 0)

return k;

else

{

v >>= 1;

o++;

k++;

}

}

while (o < wordSize);

w++;

}

return -1;

}

int CharBitvec::NextClear(int k) const

{

if (k < 0 || k >= Size)

return -1;

uint w = k / wordSize;

uint o = k % wordSize;

uint32 v = vec[w] >> o;

do

{

if (v == ones)

{

k += wordSize - o;

break;

}

else if ((v & 0x1) == 0)

return k;

else

{

v >>= 1;

o++;

k++;

}

}

while (o < wordSize);

w++;

while (w < vecSize)

{

o = 0;

v = vec[w];

do

{

if (v == ones)

{

k += wordSize - o;

break;

}

else if ((v & 0x1) == 0)

return k;

else

{

v >>= 1;

o++;

k++;

}

}

while (o < wordSize);

w++;

}

return -1;

}

template <typename C>

void CharBitvec::ToComplement(ArenaAllocator* allocator, uint base, CharSet<C>& result) const

{

int hi = -1;

while (true)

{

// Find the next range of clear bits in vector

int li = NextClear(hi + 1);

if (li < 0)

return;

hi = NextSet(li + 1);

if (hi < 0)

hi = Size - 1;

else

{

Assert(hi > 0);

hi--;

}

// Add range as characters

result.SetRange(allocator, Chars<C>::ITC(base + li), Chars<C>::ITC(base + hi));

}

}

template <typename C>

void CharBitvec::ToEquivClass(ArenaAllocator* allocator, uint base, uint& tblidx, CharSet<C>& result, codepoint_t baseOffset) const

{

int hi = -1;

while (true)

{

// Find the next range of set bits in vector

int li = NextSet(hi + 1);

if (li < 0)

return;

hi = NextClear(li + 1);

if (hi < 0)

hi = Size - 1;

else

{

Assert(hi > 0);

hi--;

}

// Convert to character codes

uint l = base + li + baseOffset;

uint h = base + hi + baseOffset;

do

{

uint acth;

C equivl[CaseInsensitive::EquivClassSize];

CaseInsensitive::RangeToEquivClass(tblidx, l, h, acth, equivl);

uint n = acth - l;

for (int i = 0; i < CaseInsensitive::EquivClassSize; i++)

{

result.SetRange(allocator, equivl[i], Chars<C>::Shift(equivl[i], n));

}

// Go around again for rest of this range

l = acth + 1;

}

while (l <= h);

}

}

// ----------------------------------------------------------------------

// CharSetNode

// ----------------------------------------------------------------------

inline CharSetNode* CharSetNode::For(ArenaAllocator* allocator, int level)

{

if (level == 0)

return Anew(allocator, CharSetLeaf);

else

return Anew(allocator, CharSetInner);

}

// ----------------------------------------------------------------------

// CharSetFull

// ----------------------------------------------------------------------

CharSetFull CharSetFull::Instance;

CharSetFull* const CharSetFull::TheFullNode = &CharSetFull::Instance;

CharSetFull::CharSetFull() {}

void CharSetFull::FreeSelf(ArenaAllocator* allocator)

{

Assert(this == TheFullNode);

// Never allocated

}

CharSetNode* CharSetFull::Clone(ArenaAllocator* allocator) const

{

// Always shared

return (CharSetNode*)this;

}

CharSetNode* CharSetFull::Set(ArenaAllocator* allocator, uint level, uint l, uint h)

{

return this;

}

CharSetNode* CharSetFull::ClearRange(ArenaAllocator* allocator, uint level, uint l, uint h)

{

AssertMsg(h <= lim(level), "The range for clearing provided is invalid for this level.");

AssertMsg(l <= h, "Can't clear where lover is bigger than the higher.");

if (l == 0 && h == lim(level))

{

return nullptr;

}

CharSetNode* toReturn = For(allocator, level);

if (l > 0)

{

AssertVerify(toReturn->Set(allocator, level, 0, l - 1) == toReturn);

}

if (h < lim(level))

{

AssertVerify(toReturn->Set(allocator, level, h + 1, lim(level)) == toReturn);

}

return toReturn;

}

CharSetNode* CharSetFull::UnionInPlace(ArenaAllocator* allocator, uint level, const CharSetNode* other)

{

return this;

}

bool CharSetFull::Get(uint level, uint k) const

{

return true;

}

void CharSetFull::ToComplement(ArenaAllocator* allocator, uint level, uint base, CharSet<Char>& result) const

{

// Empty, so add nothing

}

void CharSetFull::ToEquivClassW(ArenaAllocator* allocator, uint level, uint base, uint& tblidx, CharSet<wchar_t>& result) const

{

this->ToEquivClass<wchar_t>(allocator, level, base, tblidx, result);

}

void CharSetFull::ToEquivClassCP(ArenaAllocator* allocator, uint level, uint base, uint& tblidx, CharSet<codepoint_t>& result, codepoint_t baseOffset) const

{

this->ToEquivClass<codepoint_t>(allocator, level, base, tblidx, result, baseOffset);

}

template <typename C>

void CharSetFull::ToEquivClass(ArenaAllocator* allocator, uint level, uint base, uint& tblidx, CharSet<C>& result, codepoint_t baseOffset) const

{

uint l = base + (CharSetNode::levels - 1 == level ? 0xff : 0) + baseOffset;

uint h = base + lim(level) + baseOffset;

do

{

uint acth;

C equivl[CaseInsensitive::EquivClassSize];

CaseInsensitive::RangeToEquivClass(tblidx, l, h, acth, equivl);

uint n = acth - l;

for (int i = 0; i < CaseInsensitive::EquivClassSize; i++)

{

result.SetRange(allocator, equivl[i], Chars<C>::Shift(equivl[i], n));

}

// Go around again for rest of this range

l = acth + 1;

}

while (l <= h);

}

bool CharSetFull::IsSubsetOf(uint level, const CharSetNode* other) const

{

Assert(other != nullptr);

return other == TheFullNode;

}

bool CharSetFull::IsEqualTo(uint level, const CharSetNode* other) const

{

Assert(other != nullptr);

return other == TheFullNode;

}

uint CharSetFull::Count(uint level) const

{

return lim(level) + 1;

}

_Success_(return)

bool CharSetFull::GetNextRange(uint level, Char searchCharStart, _Out_ Char *outLowerChar, _Out_ Char *outHigherChar) const

{

Assert(searchCharStart < this->Count(level));

*outLowerChar = searchCharStart;

*outHigherChar = (Char)this->Count(level) - 1;

return true;

}

#if DBG

bool CharSetFull::IsLeaf() const

{

return false;

}

#endif

// ----------------------------------------------------------------------

// CharSetInner

// ----------------------------------------------------------------------

CharSetInner::CharSetInner()

{

for (uint i = 0; i < branchingPerInnerLevel; i++)

children[i] = 0;

}

void CharSetInner::FreeSelf(ArenaAllocator* allocator)

{

for (uint i = 0; i < branchingPerInnerLevel; i++)

{

if (children[i] != 0)

{

children[i]->FreeSelf(allocator);

#if DBG

children[i] = 0;

#endif

}

}

Adelete(allocator, this);

}

CharSetNode* CharSetInner::Clone(ArenaAllocator* allocator) const

{

CharSetInner* res = Anew(allocator, CharSetInner);

for (uint i = 0; i < branchingPerInnerLevel; i++)

{

if (children[i] != 0)

res->children[i] = children[i]->Clone(allocator);

}

return res;

}

CharSetNode* CharSetInner::ClearRange(ArenaAllocator* allocator, uint level, uint l, uint h)

{

Assert(level > 0);

AssertMsg(h <= lim(level), "The range for clearing provided is invalid for this level.");

AssertMsg(l <= h, "Can't clear where lover is bigger than the higher.");

if (l == 0 && h == lim(level))

{

return nullptr;

}

uint lowerIndex = innerIdx(level, l);

uint higherIndex = innerIdx(level--, h);

l = l & lim(level);

h = h & lim(level);

if (lowerIndex == higherIndex)

{

if (children[lowerIndex] != nullptr)

{

children[lowerIndex] = children[lowerIndex]->ClearRange(allocator, level, l, h);

}

}

else

{

if (children[lowerIndex] != nullptr)

{

children[lowerIndex] = children[lowerIndex]->ClearRange(allocator, level, l, lim(level));

}

for (uint i = lowerIndex + 1; i < higherIndex; i++)

{

if (children[i] != nullptr)

{

children[i]->FreeSelf(allocator);

}

children[i] = nullptr;

}

if (children[higherIndex] != nullptr)

{

children[higherIndex] = children[higherIndex]->ClearRange(allocator, level, 0, h);

}

}

for (int i = 0; i < branchingPerInnerLevel; i++)

{

if (children[i] != nullptr)

{

return this;

}

}

return nullptr;

}

CharSetNode* CharSetInner::Set(ArenaAllocator* allocator, uint level, uint l, uint h)

{

Assert(level > 0);

uint li = innerIdx(level, l);

uint hi = innerIdx(level--, h);

bool couldBeFull = true;

if (li == hi)

{

if (children[li] == nullptr)

{

if (remain(level, l) == 0 && remain(level, h + 1) == 0)

children[li] = CharSetFull::TheFullNode;

else

{

children[li] = For(allocator, level);

children[li] = children[li]->Set(allocator, level, l, h);

couldBeFull = false;

}

}

else

children[li] = children[li]->Set(allocator, level, l, h);

}

else

{

if (children[li] == nullptr)

{

if (remain(level, l) == 0)

children[li] = CharSetFull::TheFullNode;

else

{

children[li] = For(allocator, level);

children[li] = children[li]->Set(allocator, level, l, lim(level));

couldBeFull = false;

}

}

else

children[li] = children[li]->Set(allocator, level, l, lim(level));

for (uint i = li + 1; i < hi; i++)

{

if (children[i] != nullptr)

children[i]->FreeSelf(allocator);

children[i] = CharSetFull::TheFullNode;

}

if (children[hi] == nullptr)

{

if (remain(level, h + 1) == 0)

children[hi] = CharSetFull::TheFullNode;

else

{

children[hi] = For(allocator, level);

children[hi] = children[hi]->Set(allocator, level, 0, h);

couldBeFull = false;

}

}

else

children[hi] = children[hi]->Set(allocator, level, 0, h);

}

if (couldBeFull)

{

for (uint i = 0; i < branchingPerInnerLevel; i++)

{

if (children[i] != CharSetFull::TheFullNode)

return this;

}

FreeSelf(allocator);

return CharSetFull::TheFullNode;

}

else

return this;

}

CharSetNode* CharSetInner::UnionInPlace(ArenaAllocator* allocator, uint level, const CharSetNode* other)

{

Assert(level > 0);

Assert(other != nullptr && other != CharSetFull::TheFullNode && !other->IsLeaf());

CharSetInner* otherInner = (CharSetInner*)other;

level--;

bool isFull = true;

for (uint i = 0; i < branchingPerInnerLevel; i++)

{

if (otherInner->children[i] != nullptr)

{

if (otherInner->children[i] == CharSetFull::TheFullNode)

{

if (children[i] != nullptr)

children[i]->FreeSelf(allocator);

children[i] = CharSetFull::TheFullNode;

}

else

{

if (children[i] == nullptr)

children[i] = For(allocator, level);

children[i] = children[i]->UnionInPlace(allocator, level, otherInner->children[i]);

if (children[i] != CharSetFull::TheFullNode)

isFull = false;

}

}

else if (children[i] != CharSetFull::TheFullNode)

isFull = false;

}

if (isFull)

{

FreeSelf(allocator);

return CharSetFull::TheFullNode;

}

else

return this;

}

bool CharSetInner::Get(uint level, uint k) const

{

Assert(level > 0);

uint i = innerIdx(level--, k);

if (children[i] == nullptr)

return false;

else

return children[i]->Get(level, k);

}

void CharSetInner::ToComplement(ArenaAllocator* allocator, uint level, uint base, CharSet<Char>& result) const

{

Assert(level > 0);

level--;

uint delta = lim(level) + 1;

for (uint i = 0; i < branchingPerInnerLevel; i++)

{

if (children[i] == nullptr)

// Caution: Part of the range for this child may overlap with direct vector

result.SetRange(allocator, UTC(max(base, directSize)), UTC(base + delta - 1));

else

children[i]->ToComplement(allocator, level, base, result);

base += delta;

}

}

void CharSetInner::ToEquivClassW(ArenaAllocator* allocator, uint level, uint base, uint& tblidx, CharSet<wchar_t>& result) const

{

Assert(level > 0);

level--;

uint delta = lim(level) + 1;

for (uint i = 0; i < branchingPerInnerLevel; i++)

{

if (children[i] != nullptr)

{

children[i]->ToEquivClassW(allocator, level, base, tblidx, result);

}

base += delta;

}

}

void CharSetInner::ToEquivClassCP(ArenaAllocator* allocator, uint level, uint base, uint& tblidx, CharSet<codepoint_t>& result, codepoint_t baseOffset) const

{

Assert(level > 0);

level--;

uint delta = lim(level) + 1;

for (uint i = 0; i < branchingPerInnerLevel; i++)

{

if (children[i] != nullptr)

{

children[i]->ToEquivClassCP(allocator, level, base, tblidx, result, baseOffset);

}

base += delta;

}

}

bool CharSetInner::IsSubsetOf(uint level, const CharSetNode* other) const

{

Assert(level > 0);

Assert(other != nullptr && !other->IsLeaf());

if (other == CharSetFull::TheFullNode)

return true;

level--;

const CharSetInner* otherInner = (CharSetInner*)other;

for (uint i = 0; i < branchingPerInnerLevel; i++)

{

if (children[i] != nullptr)

{

if (otherInner->children[i] == nullptr)

return false;

if (children[i]->IsSubsetOf(level, otherInner->children[i]))

return false;

}

}

return true;

}

bool CharSetInner::IsEqualTo(uint level, const CharSetNode* other) const

{

Assert(level > 0);

Assert(other != nullptr && !other->IsLeaf());

if (other == CharSetFull::TheFullNode)

return false;

level--;

const CharSetInner* otherInner = (CharSetInner*)other;

for (uint i = 0; i < branchingPerInnerLevel; i++)

{

if (children[i] != 0)

{

if (otherInner->children[i] == nullptr)

return false;

if (children[i]->IsSubsetOf(level, otherInner->children[i]))

return false;

}

}

return true;

}

uint CharSetInner::Count(uint level) const

{

uint n = 0;

Assert(level > 0);

level--;

for (uint i = 0; i < branchingPerInnerLevel; i++)

{

if (children[i] != nullptr)

n += children[i]->Count(level);

}

return n;

}

_Success_(return)

bool CharSetInner::GetNextRange(uint level, Char searchCharStart, _Out_ Char *outLowerChar, _Out_ Char *outHigherChar) const

{

Assert(searchCharStart < this->lim(level) + 1);

uint innerIndex = innerIdx(level--, searchCharStart);

Char currentLowChar = 0, currentHighChar = 0;

for (; innerIndex < branchingPerInnerLevel; innerIndex++)

{

if (children[innerIndex] != nullptr && children[innerIndex]->GetNextRange(level, (Char)remain(level, searchCharStart), &currentLowChar, &currentHighChar))

{

break;

}

if (innerIndex < branchingPerInnerLevel - 1)

{

searchCharStart = (Char)indexToValue(level + 1, innerIndex + 1, 0);

}

}

if (innerIndex == branchingPerInnerLevel)

{

return false;

}

currentLowChar = (Char)indexToValue(level + 1, innerIndex, currentLowChar);

currentHighChar = (Char)indexToValue(level + 1, innerIndex, currentHighChar);

innerIndex += 1;

for (; remain(level, currentHighChar) == lim(level) && innerIndex < branchingPerInnerLevel; innerIndex++)

{

Char tempLower, tempHigher;

if (children[innerIndex] == nullptr || !children[innerIndex]->GetNextRange(level, 0x0, &tempLower, &tempHigher) || remain(level, tempLower) != 0)

{

break;

}

currentHighChar = (Char)indexToValue(level + 1, innerIndex, tempHigher);

}

*outLowerChar = currentLowChar;

*outHigherChar = currentHighChar;

return true;

}

#if DBG

bool CharSetInner::IsLeaf() const

{

return false;

}

#endif

// ----------------------------------------------------------------------

// CharSetLeaf

// ----------------------------------------------------------------------

CharSetLeaf::CharSetLeaf()

{

vec.Clear();

}

void CharSetLeaf::FreeSelf(ArenaAllocator* allocator)

{

Adelete(allocator, this);

}

CharSetNode* CharSetLeaf::Clone(ArenaAllocator* allocator) const

{

return Anew(allocator, CharSetLeaf, *this);

}

CharSetNode* CharSetLeaf::Set(ArenaAllocator* allocator, uint level, uint l, uint h)

{

Assert(level == 0);

vec.SetRange(leafIdx(l), leafIdx(h));

if (vec.IsFull())

{

FreeSelf(allocator);

return CharSetFull::TheFullNode;

}

else

return this;

}

CharSetNode* CharSetLeaf::ClearRange(ArenaAllocator* allocator, uint level, uint l, uint h)

{

Assert(level == 0);

AssertMsg(h <= lim(level), "The range for clearing provided is invalid for this level.");

AssertMsg(l <= h, "Can't clear where lover is bigger than the higher.");

if (l == 0 && h == lim(level))

{

return nullptr;

}

vec.ClearRange(leafIdx(l), leafIdx(h));

if (vec.IsEmpty())

{

FreeSelf(allocator);

return nullptr;

}

return this;

}

CharSetNode* CharSetLeaf::UnionInPlace(ArenaAllocator* allocator, uint level, const CharSetNode* other)

{

Assert(level == 0);

Assert(other != nullptr && other->IsLeaf());

CharSetLeaf* otherLeaf = (CharSetLeaf*)other;

if (vec.UnionInPlaceFullCheck(otherLeaf->vec))

{

FreeSelf(allocator);

return CharSetFull::TheFullNode;

}

else

return this;

}

bool CharSetLeaf::Get(uint level, uint k) const

{

Assert(level == 0);

return vec.Get(leafIdx(k));

}

void CharSetLeaf::ToComplement(ArenaAllocator* allocator, uint level, uint base, CharSet<Char>& result) const

{

Assert(level == 0);

vec.ToComplement<wchar_t>(allocator, base, result);

}

void CharSetLeaf::ToEquivClassW(ArenaAllocator* allocator, uint level, uint base, uint& tblidx, CharSet<wchar_t>& result) const

{

this->ToEquivClass<wchar_t>(allocator, level, base, tblidx, result);

}

void CharSetLeaf::ToEquivClassCP(ArenaAllocator* allocator, uint level, uint base, uint& tblidx, CharSet<codepoint_t>& result, codepoint_t baseOffset) const

{

this->ToEquivClass<codepoint_t>(allocator, level, base, tblidx, result, baseOffset);

}

template <typename C>

void CharSetLeaf::ToEquivClass(ArenaAllocator* allocator, uint level, uint base, uint& tblidx, CharSet<C>& result, codepoint_t baseOffset) const

{

Assert(level == 0);

vec.ToEquivClass<C>(allocator, base, tblidx, result, baseOffset);

}

bool CharSetLeaf::IsSubsetOf(uint level, const CharSetNode* other) const

{

Assert(level == 0);

Assert(other != nullptr);

if (other == CharSetFull::TheFullNode)

return true;

Assert(other->IsLeaf());

CharSetLeaf* otherLeaf = (CharSetLeaf*)other;

return vec.IsSubsetOf(otherLeaf->vec);

}

bool CharSetLeaf::IsEqualTo(uint level, const CharSetNode* other) const

{

Assert(level == 0);

Assert(other != nullptr);

if (other == CharSetFull::TheFullNode)

return false;

Assert(other->IsLeaf());

CharSetLeaf* otherLeaf = (CharSetLeaf*)other;

return vec.IsSubsetOf(otherLeaf->vec);

}

uint CharSetLeaf::Count(uint level) const

{

Assert(level == 0);

return vec.Count();

}

_Success_(return)

bool CharSetLeaf::GetNextRange(uint level, Char searchCharStart, _Out_ Char *outLowerChar, _Out_ Char *outHigherChar) const

{

Assert(searchCharStart < lim(level) + 1);

int nextSet = vec.NextSet(searchCharStart);

if (nextSet == -1)

{

return false;

}

*outLowerChar = (wchar_t)nextSet;

int nextClear = vec.NextClear(nextSet);

*outHigherChar = UTC(nextClear == -1 ? lim(level) : nextClear - 1);

return true;

}

#if DBG

bool CharSetLeaf::IsLeaf() const

{

return true;

}

#endif

// ----------------------------------------------------------------------

// CharSet<wchar_t>

// ----------------------------------------------------------------------

void CharSet<wchar_t>::SwitchRepresentations(ArenaAllocator* allocator)

{

Assert(IsCompact());

uint existCount = this->GetCompactLength();

__assume(existCount <= MaxCompact);

if (existCount <= MaxCompact)

{

Char existCs[MaxCompact];

for (uint i = 0; i < existCount; i++)

{

existCs[i] = GetCompactChar(i);

}

rep.full.root = nullptr;

rep.full.direct.Clear();

for (uint i = 0; i < existCount; i++)

Set(allocator, existCs[i]);

}

}

void CharSet<wchar_t>::Sort()

{

Assert(IsCompact());

__assume(this->GetCompactLength() <= MaxCompact);

for (uint i = 1; i < this->GetCompactLength(); i++)

{

uint curr = GetCompactCharU(i);

for (uint j = 0; j < i; j++)

{

if (GetCompactCharU(j) > curr)

{

for (int k = i; k > (int)j; k--)

{

this->ReplaceCompactCharU(k, this->GetCompactCharU(k - 1));

}

this->ReplaceCompactCharU(j, curr);

break;

}

}

}

}

CharSet<wchar_t>::CharSet()

{

Assert(sizeof(Node*) == sizeof(size_t));

Assert(sizeof(CompactRep) == sizeof(FullRep));

rep.compact.countPlusOne = 1;

for (int i = 0; i < MaxCompact; i++)

rep.compact.cs[i] = emptySlot;

}

void CharSet<wchar_t>::FreeBody(ArenaAllocator* allocator)

{

if (!IsCompact() && rep.full.root != nullptr)

{

rep.full.root->FreeSelf(allocator);

#if DBG

rep.full.root = nullptr;

#endif

}

}

void CharSet<wchar_t>::Clear(ArenaAllocator* allocator)

{

if (!IsCompact() && rep.full.root != nullptr)

rep.full.root->FreeSelf(allocator);

rep.compact.countPlusOne = 1;

for (int i = 0; i < MaxCompact; i++)

rep.compact.cs[i] = emptySlot;

}

void CharSet<wchar_t>::CloneFrom(ArenaAllocator* allocator, const CharSet<Char>& other)

{

Clear(allocator);

Assert(IsCompact());

if (other.IsCompact())

{

this->SetCompactLength(other.GetCompactLength());

for (uint i = 0; i < other.GetCompactLength(); i++)

{

this->ReplaceCompactCharU(i, other.GetCompactCharU(i));

}

}

else

{

rep.full.root = other.rep.full.root == nullptr ? nullptr : other.rep.full.root->Clone(allocator);

rep.full.direct.CloneFrom(other.rep.full.direct);

}

}

void CharSet<wchar_t>::CloneNonSurrogateCodeUnitsTo(ArenaAllocator* allocator, CharSet<Char>& other)

{

if (this->IsCompact())

{

for (uint i = 0; i < this->GetCompactLength(); i++)

{

Char c = this->GetCompactChar(i);

uint uChar = CTU(c);

if (uChar < 0xD800 || uChar > 0xDFFF)

{

other.Set(allocator, c);

}

}

}

else

{

other.rep.full.direct.CloneFrom(rep.full.direct);

if (rep.full.root == nullptr)

{

other.rep.full.root = nullptr;

}

else

{

other.rep.full.root = rep.full.root->Clone(allocator);

other.rep.full.root->ClearRange(allocator, CharSetNode::levels - 1, 0xD800, 0XDFFF);

}

}

}

void CharSet<wchar_t>::CloneSurrogateCodeUnitsTo(ArenaAllocator* allocator, CharSet<Char>& other)

{

if (this->IsCompact())

{

for (uint i = 0; i < this->GetCompactLength(); i++)

{

Char c = this->GetCompactChar(i);

uint uChar = CTU(c);

if (0xD800 <= uChar && uChar <= 0xDFFF)

{