CharacterClassConstructor(bool isCaseInsensitive, CompileMode compileMode)

: m_isCaseInsensitive(isCaseInsensitive)

, m_anyCharacter(false)

, m_mayContainStrings(false)

, m_invertedStrings(false)

, m_compileMode(compileMode)

, m_canonicalMode(compileMode == CompileMode::Legacy ? CanonicalMode::UCS2 : CanonicalMode::Unicode)

{

}

void reset()

{

m_strings.clear();

m_matches8.clear();

m_ranges8.clear();

m_matches32.clear();

m_ranges32.clear();

m_setOp = CharacterClassSetOp::Default;

m_anyCharacter = false;

m_mayContainStrings = false;

m_invertedStrings = false;

}

void LEGACY_NODELETE combiningSetOp(CharacterClassSetOp setOp)

{

ASSERT(m_setOp == CharacterClassSetOp::Default || m_setOp == setOp);

m_setOp = setOp;

}

void append(const CharacterClass* other)

{

if (m_setOp != CharacterClassSetOp::Default) {

performSetOpWith(other);

return;

}

for (size_t i = 0; i < other->m_strings.size(); ++i)

m_strings.append(other->m_strings[i]);

for (size_t i = 0; i < other->m_matches8.size(); ++i)

addSorted(m_matches8, other->m_matches8[i]);

for (size_t i = 0; i < other->m_ranges8.size(); ++i)

addSortedRange(m_ranges8, other->m_ranges8[i].begin, other->m_ranges8[i].end);

for (size_t i = 0; i < other->m_matches32.size(); ++i)

addSorted(m_matches32, other->m_matches32[i]);

for (size_t i = 0; i < other->m_ranges32.size(); ++i)

addSortedRange(m_ranges32, other->m_ranges32[i].begin, other->m_ranges32[i].end);

m_mayContainStrings |= other->hasStrings();

}

void appendInverted(const CharacterClass* other)

{

auto addSortedInverted = [&](char32_t min, char32_t max,

const Vector<char32_t>& srcMatches, const Vector<CharacterRange>& srcRanges,

Vector<char32_t>& destMatches, Vector<CharacterRange>& destRanges) {

auto addSortedMatchOrRange = [&](char32_t lo, char32_t hiPlusOne) {

if (lo < hiPlusOne) {

if (lo + 1 == hiPlusOne)

addSorted(destMatches, lo);

else

addSortedRange(destRanges, lo, hiPlusOne - 1);

}

};

char32_t lo = min;

size_t matchesIndex = 0;

size_t rangesIndex = 0;

bool matchesRemaining = matchesIndex < srcMatches.size();

bool rangesRemaining = rangesIndex < srcRanges.size();

if (!matchesRemaining && !rangesRemaining) {

addSortedMatchOrRange(min, max + 1);

return;

}

while (matchesRemaining || rangesRemaining) {

char32_t hiPlusOne;

char32_t nextLo;

if (matchesRemaining

&& (!rangesRemaining || srcMatches[matchesIndex] < srcRanges[rangesIndex].begin)) {

hiPlusOne = srcMatches[matchesIndex];

nextLo = hiPlusOne + 1;

++matchesIndex;

matchesRemaining = matchesIndex < srcMatches.size();

} else {

hiPlusOne = srcRanges[rangesIndex].begin;

nextLo = srcRanges[rangesIndex].end + 1;

++rangesIndex;

rangesRemaining = rangesIndex < srcRanges.size();

}

addSortedMatchOrRange(lo, hiPlusOne);

lo = nextLo;

}

addSortedMatchOrRange(lo, max + 1);

};

if (other->hasStrings()) {

m_mayContainStrings = true;

m_invertedStrings = true;

}

if (!isUnionSetOp()) {

// FIXME: Flipping the pending op (intersect with complement == subtract, and vice versa)

// would avoid materializing the complement, but m_strings still needs the original op.

CharacterClass inverted;

addSortedInverted(0, 0xff, other->m_matches8, other->m_ranges8, inverted.m_matches8, inverted.m_ranges8);

addSortedInverted(0x100, UCHAR_MAX_VALUE, other->m_matches32, other->m_ranges32, inverted.m_matches32, inverted.m_ranges32);

append(&inverted);

return;

}

addSortedInverted(0, 0xff, other->m_matches8, other->m_ranges8, m_matches8, m_ranges8);

addSortedInverted(0x100, UCHAR_MAX_VALUE, other->m_matches32, other->m_ranges32, m_matches32, m_ranges32);

}

void putChar(char32_t ch)

{

if (!isUnionSetOp())

return putCharNonUnion(ch);

if (!m_isCaseInsensitive) {

addSorted(ch);

return;

}

if (m_canonicalMode == CanonicalMode::UCS2 && isASCII(ch)) {

// Handle ASCII cases.

if (isASCIIAlpha(ch)) {

addSorted(m_matches8, toASCIIUpper(ch));

addSorted(m_matches8, toASCIILower(ch));

} else

addSorted(m_matches8, ch);

return;

}

// Add multiple matches, if necessary.

const CanonicalizationRange* info = canonicalRangeInfoFor(ch, m_canonicalMode);

if (info->type == CanonicalizeUnique)

addSorted(ch);

else

putUnicodeIgnoreCase(ch, info);

}

void putCharNonUnion(char32_t ch)

{

Vector<char32_t> matches8;

Vector<char32_t> matches32;

Vector<CharacterRange> emptyRanges;

if (m_setOp == CharacterClassSetOp::Intersection)

m_strings.clear();

auto addChar = [&] (char32_t ch) {

if (isLatin1(ch))

matches8.append(ch);

else

matches32.append(ch);

};

auto performOp = [&] () {

performSetOpWithMatches(matches8, emptyRanges, matches32, emptyRanges);

};

if (!m_isCaseInsensitive) {

addChar(ch);

performOp();

return;

}

if (m_canonicalMode == CanonicalMode::UCS2 && isASCII(ch)) {

// Handle ASCII cases.

if (isASCIIAlpha(ch)) {

addChar(toASCIIUpper(ch));

addChar(toASCIILower(ch));

} else

addChar(ch);

performOp();

return;

}

// Add multiple matches, if necessary.

const CanonicalizationRange* info = canonicalRangeInfoFor(ch, m_canonicalMode);

if (info->type == CanonicalizeUnique)

addChar(ch);

else {

if (info->type == CanonicalizeSet) {

for (auto* set = canonicalCharacterSetInfo(info->value, m_canonicalMode); (ch = *set); ++set)

addChar(ch);

} else {

char32_t canonicalChar = getCanonicalPair(info, ch);

addChar(std::min(ch, canonicalChar));

addChar(std::max(ch, canonicalChar));

}

}

performOp();

}

void putUnicodeIgnoreCase(char32_t ch, const CanonicalizationRange* info)

{

ASSERT(ch >= info->begin && ch <= info->end);

ASSERT(info->type != CanonicalizeUnique);

if (info->type == CanonicalizeSet) {

for (auto* set = canonicalCharacterSetInfo(info->value, m_canonicalMode); (ch = *set); ++set)

addSorted(ch);

} else {

addSorted(ch);

addSorted(getCanonicalPair(info, ch));

}

}

void putRange(char32_t lo, char32_t hi)

{

// The ASCII case-folding fast path is only valid in UCS2 canonical mode. In Unicode

// canonical mode, U+212A and U+017F canonicalize into ASCII 'k' and 's', so ASCII

// ranges must go through the canonicalization table below.

if (!m_isCaseInsensitive || m_canonicalMode == CanonicalMode::UCS2) {

// This is ASCII-case-folding fast path. So intentionally using isASCII (not isLatin1).

if (isASCII(lo)) {

char asciiLo = lo;

char asciiHi = std::min<char32_t>(hi, 0x7f);

addSortedRange(lo, asciiHi);

if (m_isCaseInsensitive) {

if ((asciiLo <= 'Z') && (asciiHi >= 'A'))

addSortedRange(std::max(asciiLo, 'A')+('a'-'A'), std::min(asciiHi, 'Z')+('a'-'A'));

if ((asciiLo <= 'z') && (asciiHi >= 'a'))

addSortedRange(std::max(asciiLo, 'a')+('A'-'a'), std::min(asciiHi, 'z')+('A'-'a'));

}

}

if (isASCII(hi))

return;

lo = std::max<char32_t>(lo, 0x80);

}

addSortedRange(lo, hi);

if (!m_isCaseInsensitive)

return;

const CanonicalizationRange* info = canonicalRangeInfoFor(lo, m_canonicalMode);

while (true) {

// Handle the range [lo .. end]

char32_t end = std::min<char32_t>(info->end, hi);

switch (info->type) {

case CanonicalizeUnique:

// Nothing to do - no canonical equivalents.

break;

case CanonicalizeSet: {

char16_t ch;

for (auto* set = canonicalCharacterSetInfo(info->value, m_canonicalMode); (ch = *set); ++set)

addSorted(ch);

break;

}

case CanonicalizeRangeLo:

addSortedRange(lo + info->value, end + info->value);

break;

case CanonicalizeRangeHi:

addSortedRange(lo - info->value, end - info->value);

break;

case CanonicalizeAlternatingAligned:

// Use addSortedRange since there is likely an abutting range to combine with.

if (lo & 1)

addSortedRange(lo - 1, lo - 1);

if (!(end & 1))

addSortedRange(end + 1, end + 1);

break;

case CanonicalizeAlternatingUnaligned:

// Use addSortedRange since there is likely an abutting range to combine with.

if (!(lo & 1))

addSortedRange(lo - 1, lo - 1);

if (end & 1)

addSortedRange(end + 1, end + 1);

break;

}

if (hi == end)

return;

++info;

lo = info->begin;

}

}

void putUnicodeIgnoreCase(const CharacterClass* other)

{

ASSERT(m_isCaseInsensitive && m_canonicalMode == CanonicalMode::Unicode && isUnionSetOp());

for (auto& string : other->m_strings)

m_strings.append(string);

for (char32_t ch : other->m_matches8)

putChar(ch);

for (auto& range : other->m_ranges8)

putRange(range.begin, range.end);

for (char32_t ch : other->m_matches32)

putChar(ch);

for (auto& range : other->m_ranges32)

putRange(range.begin, range.end);

m_mayContainStrings |= other->hasStrings();

}

void atomClassStringDisjunction(Vector<Vector<char32_t>>& disjunctionStrings)

{

Vector<Vector<char32_t>> utf32Strings;

Vector<char32_t> matches8;

Vector<char32_t> matches32;

Vector<CharacterRange> emptyRanges;

sort(disjunctionStrings);

auto addCh = [&](char32_t ch) {

if (isLatin1(ch))

matches8.append(ch);

else

matches32.append(ch);

};

for (auto string : disjunctionStrings) {

if (string.size() == 1) {

char32_t ch = string[0];

if (!m_isCaseInsensitive) {

addCh(ch);

continue;

}

// Add multiple matches, if necessary.

const CanonicalizationRange* info = canonicalRangeInfoFor(ch, m_canonicalMode);

if (info->type == CanonicalizeUnique)

addCh(ch);

else {

if (info->type == CanonicalizeSet) {

for (auto* set = canonicalCharacterSetInfo(info->value, m_canonicalMode); (ch = *set); ++set)

addCh(ch);

} else {

addCh(ch);

addCh(getCanonicalPair(info, ch));

}

}

continue;

}

utf32Strings.append(string);

}

performSetOpWithStrings(utf32Strings);

performSetOpWithMatches(matches8, emptyRanges, matches32, emptyRanges);

}

void invertMatches()

{

if (!m_strings.isEmpty())

m_invertedStrings = true;

latin1Invert();

nonLatin1Invert();

}

void performSetOpWith(CharacterClassConstructor* rhs)

{

performSetOpWithStrings(rhs->m_strings);

performSetOpWithMatches(rhs->m_matches8, rhs->m_ranges8, rhs->m_matches32, rhs->m_ranges32);

}

void performSetOpWith(const CharacterClass* rhs)

{

performSetOpWithStrings(rhs->m_strings);

performSetOpWithMatches(rhs->m_matches8, rhs->m_ranges8, rhs->m_matches32, rhs->m_ranges32);

}

void performSetOpWithStrings(const Vector<Vector<char32_t>>& utf32Strings)

{

if (m_compileMode != CompileMode::UnicodeSets)

return;

switch (m_setOp) {

case CharacterClassSetOp::Default:

case CharacterClassSetOp::Union:

unionStrings(utf32Strings);

break;

case CharacterClassSetOp::Intersection:

intersectionStrings(utf32Strings);

break;

case CharacterClassSetOp::Subtraction:

subtractionStrings(utf32Strings);

break;

}

}

void performSetOpWithMatches(const Vector<char32_t>& rhsMatches8, const Vector<CharacterRange>& rhsRanges8, const Vector<char32_t>& rhsMatches32, const Vector<CharacterRange>& rhsRanges32)

{

if (m_compileMode != CompileMode::UnicodeSets)

return;

latin1Op(rhsMatches8, rhsRanges8);

// Sort the incoming non-Latin-1 matches, since Unicode case folding canonicalization may cause

// characters to be added to rhsMatches32 out of code point order.

Vector<char32_t> rhsSortedMatches32(rhsMatches32);

std::ranges::sort(rhsSortedMatches32);

nonLatin1OpSorted(rhsSortedMatches32, rhsRanges32);

}

bool LEGACY_NODELETE hasInvertedStrings()

{

return m_invertedStrings;

}

static ALWAYS_INLINE int LEGACY_NODELETE compareUTF32Strings(const Vector<char32_t>& a, const Vector<char32_t>& b)

{

// Longer strings before shorter.

if (a.size() > b.size())

return -1;

if (a.size() < b.size())

return 1;

// Lexically sort for same length strings.

for (unsigned i = 0; i < a.size(); ++i) {

if (a[i] != b[i])

return (a[i] < b[i]) ? -1 : 1;

}

return 0;

}

static void sort(Vector<Vector<char32_t>>& utf32Strings)

{

std::ranges::sort(utf32Strings, [](const auto& a, const auto& b) {

return compareUTF32Strings(a, b) < 0;

});

}

std::unique_ptr<CharacterClass> charClass()

{

coalesceTables();

if (!m_strings.isEmpty())

sort(m_strings);

auto characterClass = makeUnique<CharacterClass>();

characterClass->m_strings.swap(m_strings);

characterClass->m_matches8.swap(m_matches8);

characterClass->m_ranges8.swap(m_ranges8);

characterClass->m_matches32.swap(m_matches32);

characterClass->m_ranges32.swap(m_ranges32);

characterClass->m_anyCharacter = anyCharacter();

characterClass->m_characterWidths = characterWidths(*characterClass);

buildLatin1TableIfBeneficial(*characterClass);

m_anyCharacter = false;

return characterClass;

}

void LEGACY_NODELETE setIsCaseInsensitive(bool ignoreCase)

{

m_isCaseInsensitive = ignoreCase;

}

static void buildLatin1TableIfBeneficial(CharacterClass& characterClass)

{

if (!characterClass.m_strings.isEmpty() || characterClass.m_anyCharacter || characterClass.m_table)

return;

const auto& matches = characterClass.m_matches8;

const auto& ranges = characterClass.m_ranges8;

// A single range is already one subtract + one compare in the JIT, so a table would not help.

unsigned entryCount = matches.size() + ranges.size();

if (entryCount < 2)

return;

constexpr char32_t maxLatin1 = CharacterClass::latin1TableSize - 1;

char32_t low = !ranges.isEmpty() ? ranges.first().begin : matches.first();

char32_t high = !ranges.isEmpty() ? ranges.last().end : matches.last();

if (!matches.isEmpty()) {

low = std::min<char32_t>(low, matches.first());

high = std::max<char32_t>(high, matches.last());

}

ASSERT_UNUSED(maxLatin1, low <= maxLatin1 && high <= maxLatin1);

constexpr char32_t bitTestFootprint = 64;

if (high - low < bitTestFootprint)

return;

auto table = makeUnique<CharacterClass::ByteTable>();

for (auto match : matches) {

ASSERT(match <= maxLatin1);

table->data[match] = 1;

}

for (auto range : ranges) {

ASSERT(range.end <= maxLatin1);

for (char32_t ch = range.begin; ch <= range.end; ++ch)

table->data[ch] = 1;

}

characterClass.m_latin1Table = WTF::move(table);

}

void addSorted(char32_t ch)

{

addSorted(isLatin1(ch) ? m_matches8 : m_matches32, ch);

}

void addSorted(Vector<char32_t>& matches, char32_t ch)

{

unsigned pos = 0;

unsigned range = matches.size();

// binary chop, find position to insert char.

while (range) {

unsigned index = range >> 1;

int val = matches[pos+index] - ch;

if (!val)

return;

else if (val > 0) {

if (val == 1) {

char32_t lo = ch;

char32_t hi = ch + 1;

matches.removeAt(pos + index);

if (pos + index > 0 && matches[pos + index - 1] == ch - 1) {

lo = ch - 1;

matches.removeAt(pos + index - 1);

}

addSortedRange(isLatin1(ch) ? m_ranges8 : m_ranges32, lo, hi);

return;

}

range = index;

} else {

if (val == -1) {

char32_t lo = ch - 1;

char32_t hi = ch;

matches.removeAt(pos + index);

if (pos + index + 1 < matches.size() && matches[pos + index + 1] == ch + 1) {

hi = ch + 1;

matches.removeAt(pos + index + 1);

}

addSortedRange(isLatin1(ch) ? m_ranges8 : m_ranges32, lo, hi);

return;

}

pos += (index+1);

range -= (index+1);

}

}

if (pos == matches.size())

matches.append(ch);

else

matches.insert(pos, ch);

}

void addSortedRange(Vector<CharacterRange>& ranges, char32_t lo, char32_t hi)

{

auto iter = std::lower_bound(ranges.begin(), ranges.end(), lo,

[](const CharacterRange& range, char32_t value) {

return static_cast<uint64_t>(range.end) + 1 < value;

});

if (iter == ranges.end()) {

// CharacterRange comes after all existing ranges.

ranges.append(CharacterRange(lo, hi));

return;

}

ASSERT(lo <= (iter->end + 1));

// does the new range fall before the current position in the array

if (hi < iter->begin) {

// Concatenate appending ranges.

if (hi == (iter->begin - 1)) {

iter->begin = lo;

return;

}

ranges.insert(iter - ranges.begin(), CharacterRange(lo, hi));

return;

}

// 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.

// found an intersect! we'll replace this entry in the array.

iter->begin = std::min(iter->begin, lo);

iter->end = std::max(iter->end, hi);

mergeRangesFrom(ranges, iter - ranges.begin());

}

void addSortedRange(char32_t lo, char32_t hi)

{

if (lo == hi) {

addSorted(lo);

return;

}

if (isLatin1(lo)) {

auto latin1Hi = std::min<char32_t>(hi, 0xff);

if (lo == latin1Hi)

addSorted(m_matches8, lo);

else

addSortedRange(m_ranges8, lo, latin1Hi);

if (isLatin1(hi))

return;

lo = 0x100;

if (lo == hi) {

addSorted(m_matches32, hi);

return;

}

}

addSortedRange(m_ranges32, lo, hi);

}

void mergeRangesFrom(Vector<CharacterRange>& ranges, size_t index)

{

unsigned next = index + 1;

// each iteration of the loop we will either remove something from the list, or break out of the loop.

while (next < ranges.size()) {

if (ranges[next].begin <= (ranges[index].end + 1)) {

// the next entry now overlaps / concatenates with this one.

ranges[index].end = std::max(ranges[index].end, ranges[next].end);

ranges.removeAt(next);

} else

break;

}

}

void unionStrings(const Vector<Vector<char32_t>>& rhsStrings)

{

// result should include strings in either the LHS or RHS

Vector<Vector<char32_t>> result;

size_t lhsIndex = 0;

size_t rhsIndex = 0;

while (lhsIndex < m_strings.size() && rhsIndex < rhsStrings.size()) {

auto lhsString = m_strings[lhsIndex];

auto rhsString = rhsStrings[rhsIndex];

auto strCompare = compareUTF32Strings(lhsString, rhsString);

if (strCompare <= 0) {

result.append(lhsString);

lhsIndex++;

if (!strCompare)

rhsIndex++;

} else {

result.append(rhsString);

rhsIndex++;

}

}

// One of LHS or RHS has been exhausted, add the remaining strings.

while (lhsIndex < m_strings.size())

result.append(m_strings[lhsIndex++]);

while (rhsIndex < rhsStrings.size())

result.append(rhsStrings[rhsIndex++]);

m_strings.swap(result);

m_mayContainStrings = !m_strings.isEmpty();

}

void intersectionStrings(const Vector<Vector<char32_t>>& rhsStrings)

{

// result should include strings that are in both the LHS and RHS.

Vector<Vector<char32_t>> result;

size_t lhsIndex = 0;

size_t rhsIndex = 0;

while (lhsIndex < m_strings.size() && rhsIndex < rhsStrings.size()) {

auto lhsString = m_strings[lhsIndex];

auto rhsString = rhsStrings[rhsIndex];

auto strCompare = compareUTF32Strings(lhsString, rhsString);

if (!strCompare) {

result.append(lhsString);

lhsIndex++;

rhsIndex++;

} else if (strCompare < 0)

lhsIndex++;

else

rhsIndex++;

}

m_strings.swap(result);

m_mayContainStrings = !m_strings.isEmpty();

}

void subtractionStrings(const Vector<Vector<char32_t>>& rhsStrings)

{

// result should include strings in LHS that are not in RHS.

Vector<Vector<char32_t>> result;

size_t lhsIndex = 0;

size_t rhsIndex = 0;

while (lhsIndex < m_strings.size() && rhsIndex < rhsStrings.size()) {

auto lhsString = m_strings[lhsIndex];

auto rhsString = rhsStrings[rhsIndex];

auto strCompare = compareUTF32Strings(lhsString, rhsString);

if (!strCompare) {

lhsIndex++;

rhsIndex++;

} else if (strCompare < 0) {

result.append(lhsString);

lhsIndex++;

} else

rhsIndex++;

}

// Add any remaining LHS strings.

while (lhsIndex < m_strings.size())

result.append(m_strings[lhsIndex++]);

m_strings.swap(result);

m_mayContainStrings = !m_strings.isEmpty();

}

void latin1Op(const Vector<char32_t>& rhsMatches, const Vector<CharacterRange>& rhsRanges)

{

Vector<char32_t> resultMatches;

Vector<CharacterRange> resultRanges;

WTF::BitSet<0x100> lhsLatin1BitSet;

WTF::BitSet<0x100> rhsLatin1BitSet;

for (auto match : m_matches8)

lhsLatin1BitSet.set(match);

for (auto range : m_ranges8) {

for (char32_t ch = range.begin; ch <= range.end; ch++)

lhsLatin1BitSet.set(ch);

}

for (auto match : rhsMatches)

rhsLatin1BitSet.set(match);

for (auto range : rhsRanges) {

for (char32_t ch = range.begin; ch <= range.end; ch++)

rhsLatin1BitSet.set(ch);

}

switch (m_setOp) {

case CharacterClassSetOp::Default:

case CharacterClassSetOp::Union:

lhsLatin1BitSet.merge(rhsLatin1BitSet);

break;

case CharacterClassSetOp::Intersection:

lhsLatin1BitSet.filter(rhsLatin1BitSet);

break;

case CharacterClassSetOp::Subtraction:

lhsLatin1BitSet.exclude(rhsLatin1BitSet);

break;

}

bool firstCharUnset = true;

char32_t lo = 0;

char32_t hi = 0;

auto addCharToResults = [&]() {

if (lo == hi)

resultMatches.append(lo);

else

resultRanges.append(CharacterRange(lo, hi));

};

for (auto setVal : lhsLatin1BitSet) {

char32_t ch = setVal;

if (firstCharUnset) {

lo = hi = ch;

firstCharUnset = false;

} else {

if (ch == hi + 1)

hi = ch;

else {

addCharToResults();

lo = hi = ch;

}

}

}

if (!firstCharUnset)

addCharToResults();

m_matches8.swap(resultMatches);

m_ranges8.swap(resultRanges);

}

void latin1Invert()

{

Vector<char32_t> resultMatches;

Vector<CharacterRange> resultRanges;

WTF::BitSet<0x100> latin1BitSet;

for (auto match : m_matches8)

latin1BitSet.set(match);

for (auto range : m_ranges8) {

for (char32_t ch = range.begin; ch <= range.end; ch++)

latin1BitSet.set(ch);

}

latin1BitSet.invert();

bool firstCharUnset = true;

char32_t lo = 0;

char32_t hi = 0;

auto addCharToResults = [&]() {

if (lo == hi)

resultMatches.append(lo);

else

resultRanges.append(CharacterRange(lo, hi));

};

for (auto setVal : latin1BitSet) {

char32_t ch = setVal;

if (firstCharUnset) {

lo = hi = ch;

firstCharUnset = false;

} else {

if (ch == hi + 1)

hi = ch;

else {

addCharToResults();

lo = hi = ch;

}

}

}

if (!firstCharUnset)

addCharToResults();

m_matches8.swap(resultMatches);

m_ranges8.swap(resultRanges);

}

void nonLatin1OpSorted(const Vector<char32_t>& rhsMatches32, const Vector<CharacterRange>& rhsRanges32)

{

Vector<char32_t> resultMatches;

Vector<CharacterRange> resultRanges;

constexpr size_t chunkSize = 2048;

WTF::BitSet<chunkSize> lhsChunkBitSet;

WTF::BitSet<chunkSize> rhsChunkBitSet;

char32_t chunkLo = INT_MAX, chunkHi;

size_t lhsMatchIndex = 0;

size_t lhsRangeIndex = 0;

size_t rhsMatchIndex = 0;

size_t rhsRangeIndex = 0;

auto lhsHasMore = [&] {

return lhsMatchIndex < m_matches32.size() || lhsRangeIndex < m_ranges32.size();

};

auto rhsHasMore = [&] {

return rhsMatchIndex < rhsMatches32.size() || rhsRangeIndex < rhsRanges32.size();

};

auto canProduceMore = [&] {

switch (m_setOp) {

case CharacterClassSetOp::Default:

case CharacterClassSetOp::Union:

return lhsHasMore() || rhsHasMore();

case CharacterClassSetOp::Intersection:

return lhsHasMore() && rhsHasMore();

case CharacterClassSetOp::Subtraction:

return lhsHasMore();

}

RELEASE_ASSERT_NOT_REACHED();

return false;

};

if (!m_matches32.isEmpty())

chunkLo = std::min(chunkLo, m_matches32[0]);

if (!m_ranges32.isEmpty())

chunkLo = std::min(chunkLo, m_ranges32[0].begin);

if (!rhsMatches32.isEmpty())

chunkLo = std::min(chunkLo, rhsMatches32[0]);

if (!rhsRanges32.isEmpty())

chunkLo = std::min(chunkLo, rhsRanges32[0].begin);

while (canProduceMore()) {

chunkHi = chunkLo + chunkSize - 1;

for (; lhsMatchIndex < m_matches32.size(); ++lhsMatchIndex) {

char32_t ch = m_matches32[lhsMatchIndex];

if (ch > chunkHi)

break;

ASSERT(ch >= chunkLo);

lhsChunkBitSet.set(ch - chunkLo);

}

for (; lhsRangeIndex < m_ranges32.size(); ++lhsRangeIndex) {

auto range = m_ranges32[lhsRangeIndex];

if (range.begin > chunkHi)

break;

auto begin = std::max(chunkLo, range.begin);

auto end = std::min(range.end, chunkHi);

for (char32_t ch = begin; ch <= end; ch++) {

ASSERT(ch >= chunkLo);

lhsChunkBitSet.set(ch - chunkLo);

}

if (range.end > chunkHi)

break;

}

for (; rhsMatchIndex < rhsMatches32.size(); ++rhsMatchIndex) {

char32_t ch = rhsMatches32[rhsMatchIndex];

if (ch > chunkHi)

break;

ASSERT(ch >= chunkLo);

rhsChunkBitSet.set(ch - chunkLo);

}

for (; rhsRangeIndex < rhsRanges32.size(); ++rhsRangeIndex) {

auto range = rhsRanges32[rhsRangeIndex];

if (range.begin > chunkHi)

break;

auto begin = std::max(chunkLo, range.begin);

auto end = std::min(range.end, chunkHi);

for (char32_t ch = begin; ch <= end; ch++) {

ASSERT(ch >= chunkLo);

rhsChunkBitSet.set(ch - chunkLo);

}

if (range.end > chunkHi)

break;

}

switch (m_setOp) {

case CharacterClassSetOp::Default:

case CharacterClassSetOp::Union: