1	/*
2	* Copyright (C) 2009, 2013-2016 Apple Inc. All rights reserved.
3	* Copyright (C) 2010 Peter Varga (pvarga@inf.u-szeged.hu), University of Szeged
4	*
5	* Redistribution and use in source and binary forms, with or without
6	* modification, are permitted provided that the following conditions
7	* are met:
8	* 1. Redistributions of source code must retain the above copyright
9	* notice, this list of conditions and the following disclaimer.
10	* 2. Redistributions in binary form must reproduce the above copyright
11	* notice, this list of conditions and the following disclaimer in the
12	* documentation and/or other materials provided with the distribution.
13	*
14	* THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
15	* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17	* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
18	* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19	* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20	* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21	* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22	* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24	* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25	*/
26
27	#include "config.h"
28	#include "YarrPattern.h"
29
30	#include "Options.h"
31	#include "Yarr.h"
32	#include "YarrCanonicalize.h"
33	#include "YarrParser.h"
34	#include <wtf/DataLog.h>
35	#include <wtf/Optional.h>
36	#include <wtf/Vector.h>
37	#include <wtf/text/WTFString.h>
38
39	namespace JSC { namespace Yarr {
40
41	#include "RegExpJitTables.h"
42
43	class CharacterClassConstructor {
44	public:
45	CharacterClassConstructor(bool isCaseInsensitive, CanonicalMode canonicalMode)
46	: m_isCaseInsensitive(isCaseInsensitive)
47	, m_hasNonBMPCharacters(false)
48	, m_anyCharacter(false)
49	, m_canonicalMode(canonicalMode)
50	{
51	}
52
53	void reset()
54	{
55	m_matches.clear();
56	m_ranges.clear();
57	m_matchesUnicode.clear();
58	m_rangesUnicode.clear();
59	m_hasNonBMPCharacters = false;
60	m_anyCharacter = false;
61	}
62
63	void append(const CharacterClass* other)
64	{
65	for (size_t i = 0; i < other->m_matches.size(); ++i)
66	addSorted(matches&: m_matches, ch: other->m_matches[i]);
67	for (size_t i = 0; i < other->m_ranges.size(); ++i)
68	addSortedRange(ranges&: m_ranges, lo: other->m_ranges[i].begin, hi: other->m_ranges[i].end);
69	for (size_t i = 0; i < other->m_matchesUnicode.size(); ++i)
70	addSorted(matches&: m_matchesUnicode, ch: other->m_matchesUnicode[i]);
71	for (size_t i = 0; i < other->m_rangesUnicode.size(); ++i)
72	addSortedRange(ranges&: m_rangesUnicode, lo: other->m_rangesUnicode[i].begin, hi: other->m_rangesUnicode[i].end);
73	}
74
75	void appendInverted(const CharacterClass* other)
76	{
77	auto addSortedInverted = [&](UChar32 min, UChar32 max,
78	const Vector<UChar32>& srcMatches, const Vector<CharacterRange>& srcRanges,
79	Vector<UChar32>& destMatches, Vector<CharacterRange>& destRanges) {
80
81	auto addSortedMatchOrRange = [&](UChar32 lo, UChar32 hiPlusOne) {
82	if (lo < hiPlusOne) {
83	if (lo + 1 == hiPlusOne)
84	addSorted(destMatches, lo);
85	else
86	addSortedRange(ranges&: destRanges, lo, hi: hiPlusOne - 1);
87	}
88	};
89
90	UChar32 lo = min;
91	size_t matchesIndex = 0;
92	size_t rangesIndex = 0;
93	bool matchesRemaining = matchesIndex < srcMatches.size();
94	bool rangesRemaining = rangesIndex < srcRanges.size();
95
96	if (!matchesRemaining && !rangesRemaining) {
97	addSortedMatchOrRange(min, max + 1);
98	return;
99	}
100
101	while (matchesRemaining || rangesRemaining) {
102	UChar32 hiPlusOne;
103	UChar32 nextLo;
104
105	if (matchesRemaining
106	&& (!rangesRemaining || srcMatches[matchesIndex] < srcRanges[rangesIndex].begin)) {
107	hiPlusOne = srcMatches[matchesIndex];
108	nextLo = hiPlusOne + 1;
109	++matchesIndex;
110	matchesRemaining = matchesIndex < srcMatches.size();
111	} else {
112	hiPlusOne = srcRanges[rangesIndex].begin;
113	nextLo = srcRanges[rangesIndex].end + 1;
114	++rangesIndex;
115	rangesRemaining = rangesIndex < srcRanges.size();
116	}
117
118	addSortedMatchOrRange(lo, hiPlusOne);
119
120	lo = nextLo;
121	}
122
123	addSortedMatchOrRange(lo, max + 1);
124	};
125
126	addSortedInverted(0, 0x7f, other->m_matches, other->m_ranges, m_matches, m_ranges);
127	addSortedInverted(0x80, 0x10ffff, other->m_matchesUnicode, other->m_rangesUnicode, m_matchesUnicode, m_rangesUnicode);
128	}
129
130	void putChar(UChar32 ch)
131	{
132	if (!m_isCaseInsensitive) {
133	addSorted(ch);
134	return;
135	}
136
137	if (m_canonicalMode == CanonicalMode::UCS2 && isASCII(ch)) {
138	// Handle ASCII cases.
139	if (isASCIIAlpha(ch)) {
140	addSorted(m_matches, toASCIIUpper(ch));
141	addSorted(m_matches, toASCIILower(ch));
142	} else
143	addSorted(matches&: m_matches, ch);
144	return;
145	}
146
147	// Add multiple matches, if necessary.
148	const CanonicalizationRange* info = canonicalRangeInfoFor(ch, canonicalMode: m_canonicalMode);
149	if (info->type == CanonicalizeUnique)
150	addSorted(ch);
151	else
152	putUnicodeIgnoreCase(ch, info);
153	}
154
155	void putUnicodeIgnoreCase(UChar32 ch, const CanonicalizationRange* info)
156	{
157	ASSERT(m_isCaseInsensitive);
158	ASSERT(ch >= info->begin && ch <= info->end);
159	ASSERT(info->type != CanonicalizeUnique);
160	if (info->type == CanonicalizeSet) {
161	for (const UChar32* set = canonicalCharacterSetInfo(index: info->value, canonicalMode: m_canonicalMode); (ch = *set); ++set)
162	addSorted(ch);
163	} else {
164	addSorted(ch);
165	addSorted(ch: getCanonicalPair(info, ch));
166	}
167	}
168
169	void putRange(UChar32 lo, UChar32 hi)
170	{
171	if (isASCII(lo)) {
172	char asciiLo = lo;
173	char asciiHi = std::min(hi, (UChar32)0x7f);
174	addSortedRange(ranges&: m_ranges, lo, hi: asciiHi);
175
176	if (m_isCaseInsensitive) {
177	if ((asciiLo <= 'Z') && (asciiHi >= 'A'))
178	addSortedRange(ranges&: m_ranges, lo: std::max(asciiLo, 'A')+('a'-'A'), hi: std::min(asciiHi, 'Z')+('a'-'A'));
179	if ((asciiLo <= 'z') && (asciiHi >= 'a'))
180	addSortedRange(ranges&: m_ranges, lo: std::max(asciiLo, 'a')+('A'-'a'), hi: std::min(asciiHi, 'z')+('A'-'a'));
181	}
182	}
183	if (isASCII(hi))
184	return;
185
186	lo = std::max(lo, (UChar32)0x80);
187	addSortedRange(ranges&: m_rangesUnicode, lo, hi);
188
189	if (!m_isCaseInsensitive)
190	return;
191
192	const CanonicalizationRange* info = canonicalRangeInfoFor(ch: lo, canonicalMode: m_canonicalMode);
193	while (true) {
194	// Handle the range [lo .. end]
195	UChar32 end = std::min<UChar32>(info->end, hi);
196
197	switch (info->type) {
198	case CanonicalizeUnique:
199	// Nothing to do - no canonical equivalents.
200	break;
201	case CanonicalizeSet: {
202	UChar ch;
203	for (const UChar32* set = canonicalCharacterSetInfo(index: info->value, canonicalMode: m_canonicalMode); (ch = *set); ++set)
204	addSorted(matches&: m_matchesUnicode, ch);
205	break;
206	}
207	case CanonicalizeRangeLo:
208	addSortedRange(ranges&: m_rangesUnicode, lo: lo + info->value, hi: end + info->value);
209	break;
210	case CanonicalizeRangeHi:
211	addSortedRange(ranges&: m_rangesUnicode, lo: lo - info->value, hi: end - info->value);
212	break;
213	case CanonicalizeAlternatingAligned:
214	// Use addSortedRange since there is likely an abutting range to combine with.
215	if (lo & 1)
216	addSortedRange(ranges&: m_rangesUnicode, lo: lo - 1, hi: lo - 1);
217	if (!(end & 1))
218	addSortedRange(ranges&: m_rangesUnicode, lo: end + 1, hi: end + 1);
219	break;
220	case CanonicalizeAlternatingUnaligned:
221	// Use addSortedRange since there is likely an abutting range to combine with.
222	if (!(lo & 1))
223	addSortedRange(ranges&: m_rangesUnicode, lo: lo - 1, hi: lo - 1);
224	if (end & 1)
225	addSortedRange(ranges&: m_rangesUnicode, lo: end + 1, hi: end + 1);
226	break;
227	}
228
229	if (hi == end)
230	return;
231
232	++info;
233	lo = info->begin;
234	};
235
236	}
237
238	std::unique_ptr<CharacterClass> charClass()
239	{
240	coalesceTables();
241
242	auto characterClass = std::make_unique<CharacterClass>();
243
244	characterClass->m_matches.swap(m_matches);
245	characterClass->m_ranges.swap(m_ranges);
246	characterClass->m_matchesUnicode.swap(m_matchesUnicode);
247	characterClass->m_rangesUnicode.swap(m_rangesUnicode);
248	characterClass->m_hasNonBMPCharacters = hasNonBMPCharacters();
249	characterClass->m_anyCharacter = anyCharacter();
250
251	m_hasNonBMPCharacters = false;
252	m_anyCharacter = false;
253
254	return characterClass;
255	}
256
257	private:
258	void addSorted(UChar32 ch)
259	{
260	addSorted(matches&: isASCII(ch) ? m_matches : m_matchesUnicode, ch);
261	}
262
263	void addSorted(Vector<UChar32>& matches, UChar32 ch)
264	{
265	unsigned pos = 0;
266	unsigned range = matches.size();
267
268	if (!U_IS_BMP(ch))
269	m_hasNonBMPCharacters = true;
270
271	// binary chop, find position to insert char.
272	while (range) {
273	unsigned index = range >> 1;
274
275	int val = matches[pos+index] - ch;
276	if (!val)
277	return;
278	else if (val > 0) {
279	if (val == 1) {
280	UChar32 lo = ch;
281	UChar32 hi = ch + 1;
282	matches.remove(position: pos + index);
283	if (pos + index > 0 && matches[pos + index - 1] == ch - 1) {
284	lo = ch - 1;
285	matches.remove(position: pos + index - 1);
286	}
287	addSortedRange(ranges&: isASCII(ch) ? m_ranges : m_rangesUnicode, lo, hi);
288	return;
289	}
290	range = index;
291	} else {
292	if (val == -1) {
293	UChar32 lo = ch - 1;
294	UChar32 hi = ch;
295	matches.remove(position: pos + index);
296	if (pos + index + 1 < matches.size() && matches[pos + index + 1] == ch + 1) {
297	hi = ch + 1;
298	matches.remove(position: pos + index + 1);
299	}
300	addSortedRange(ranges&: isASCII(ch) ? m_ranges : m_rangesUnicode, lo, hi);
301	return;
302	}
303	pos += (index+1);
304	range -= (index+1);
305	}
306	}
307
308	if (pos == matches.size())
309	matches.append(value: ch);
310	else
311	matches.insert(position: pos, value: ch);
312	}
313
314	void addSortedRange(Vector<CharacterRange>& ranges, UChar32 lo, UChar32 hi)
315	{
316	size_t end = ranges.size();
317
318	if (!U_IS_BMP(hi))
319	m_hasNonBMPCharacters = true;
320
321	// Simple linear scan - I doubt there are that many ranges anyway...
322	// feel free to fix this with something faster (eg binary chop).
323	for (size_t i = 0; i < end; ++i) {
324	// does the new range fall before the current position in the array
325	if (hi < ranges[i].begin) {
326	// Concatenate appending ranges.
327	if (hi == (ranges[i].begin - 1)) {
328	ranges[i].begin = lo;
329	return;
330	}
331	ranges.insert(position: i, value: CharacterRange(lo, hi));
332	return;
333	}
334	// Okay, since we didn't hit the last case, the end of the new range is definitely at or after the beginning
335	// If the new range start at or before the end of the last range, then the overlap (if it starts one after the
336	// end of the last range they concatenate, which is just as good.
337	if (lo <= (ranges[i].end + 1)) {
338	// found an intersect! we'll replace this entry in the array.
339	ranges[i].begin = std::min(ranges[i].begin, lo);
340	ranges[i].end = std::max(ranges[i].end, hi);
341
342	mergeRangesFrom(ranges, index: i);
343	return;
344	}
345	}
346
347	// CharacterRange comes after all existing ranges.
348	ranges.append(other: CharacterRange(lo, hi));
349	}
350
351	void mergeRangesFrom(Vector<CharacterRange>& ranges, size_t index)
352	{
353	size_t next = index + 1;
354
355	// each iteration of the loop we will either remove something from the list, or break out of the loop.
356	while (next < ranges.size()) {
357	if (ranges[next].begin <= (ranges[index].end + 1)) {
358	// the next entry now overlaps / concatenates with this one.
359	ranges[index].end = std::max(ranges[index].end, ranges[next].end);
360	ranges.remove(position: next);
361	} else
362	break;
363	}
364
365	}
366
367	void coalesceTables()
368	{
369	auto coalesceMatchesAndRanges = [&](Vector<UChar32>& matches, Vector<CharacterRange>& ranges) {
370
371	size_t matchesIndex = 0;
372	size_t rangesIndex = 0;
373
374	while (matchesIndex < matches.size() && rangesIndex < ranges.size()) {
375	while (matchesIndex < matches.size() && matches[matchesIndex] < ranges[rangesIndex].begin - 1)
376	matchesIndex++;
377
378	if (matchesIndex < matches.size() && matches[matchesIndex] == ranges[rangesIndex].begin - 1) {
379	ranges[rangesIndex].begin = matches[matchesIndex];
380	matches.remove(matchesIndex);
381	}
382
383	while (matchesIndex < matches.size() && matches[matchesIndex] < ranges[rangesIndex].end + 1)
384	matchesIndex++;
385
386	if (matchesIndex < matches.size()) {
387	if (matches[matchesIndex] == ranges[rangesIndex].end + 1) {
388	ranges[rangesIndex].end = matches[matchesIndex];
389	matches.remove(matchesIndex);
390
391	mergeRangesFrom(ranges&: ranges, index: rangesIndex);
392	} else
393	matchesIndex++;
394	}
395	}
396	};
397
398	coalesceMatchesAndRanges(m_matches, m_ranges);
399	coalesceMatchesAndRanges(m_matchesUnicode, m_rangesUnicode);
400
401	if (!m_matches.size() && !m_matchesUnicode.size()
402	&& m_ranges.size() == 1 && m_rangesUnicode.size() == 1
403	&& m_ranges[0].begin == 0 && m_ranges[0].end == 0x7f
404	&& m_rangesUnicode[0].begin == 0x80 && m_rangesUnicode[0].end == 0x10ffff)
405	m_anyCharacter = true;
406	}
407
408	bool hasNonBMPCharacters()
409	{
410	return m_hasNonBMPCharacters;
411	}
412
413	bool anyCharacter()
414	{
415	return m_anyCharacter;
416	}
417
418	bool m_isCaseInsensitive : 1;
419	bool m_hasNonBMPCharacters : 1;
420	bool m_anyCharacter : 1;
421	CanonicalMode m_canonicalMode;
422
423	Vector<UChar32> m_matches;
424	Vector<CharacterRange> m_ranges;
425	Vector<UChar32> m_matchesUnicode;
426	Vector<CharacterRange> m_rangesUnicode;
427	};
428
429	class YarrPatternConstructor {
430	public:
431	YarrPatternConstructor(YarrPattern& pattern, void* stackLimit)
432	: m_pattern(pattern)
433	, m_characterClassConstructor(pattern.ignoreCase(), pattern.unicode() ? CanonicalMode::Unicode : CanonicalMode::UCS2)
434	, m_stackLimit(stackLimit)
435	{
436	auto body = std::make_unique<PatternDisjunction>();
437	m_pattern.m_body = body.get();
438	m_alternative = body->addNewAlternative();
439	m_pattern.m_disjunctions.append(WTFMove(body));
440	}
441
442	~YarrPatternConstructor()
443	{
444	}
445
446	void resetForReparsing()
447	{
448	m_pattern.resetForReparsing();
449	m_characterClassConstructor.reset();
450
451	auto body = std::make_unique<PatternDisjunction>();
452	m_pattern.m_body = body.get();
453	m_alternative = body->addNewAlternative();
454	m_pattern.m_disjunctions.append(WTFMove(body));
455	}
456
457	void saveUnmatchedNamedForwardReferences()
458	{
459	m_unmatchedNamedForwardReferences.shrink(0);
460
461	for (auto& entry : m_pattern.m_namedForwardReferences) {
462	if (!m_pattern.m_captureGroupNames.contains(entry))
463	m_unmatchedNamedForwardReferences.append(entry);
464	}
465	}
466
467	void assertionBOL()
468	{
469	if (!m_alternative->m_terms.size() && !m_invertParentheticalAssertion) {
470	m_alternative->m_startsWithBOL = true;
471	m_alternative->m_containsBOL = true;
472	m_pattern.m_containsBOL = true;
473	}
474	m_alternative->m_terms.append(other: PatternTerm::BOL());
475	}
476	void assertionEOL()
477	{
478	m_alternative->m_terms.append(other: PatternTerm::EOL());
479	}
480	void assertionWordBoundary(bool invert)
481	{
482	m_alternative->m_terms.append(other: PatternTerm::WordBoundary(invert));
483	}
484
485	void atomPatternCharacter(UChar32 ch)
486	{
487	// We handle case-insensitive checking of unicode characters which do have both
488	// cases by handling them as if they were defined using a CharacterClass.
489	if (!m_pattern.ignoreCase() || (isASCII(ch) && !m_pattern.unicode())) {
490	m_alternative->m_terms.append(other: PatternTerm(ch));
491	return;
492	}
493
494	const CanonicalizationRange* info = canonicalRangeInfoFor(ch, canonicalMode: m_pattern.unicode() ? CanonicalMode::Unicode : CanonicalMode::UCS2);
495	if (info->type == CanonicalizeUnique) {
496	m_alternative->m_terms.append(other: PatternTerm(ch));
497	return;
498	}
499
500	m_characterClassConstructor.putUnicodeIgnoreCase(ch, info);
501	auto newCharacterClass = m_characterClassConstructor.charClass();
502	m_alternative->m_terms.append(other: PatternTerm(newCharacterClass.get(), false));
503	m_pattern.m_userCharacterClasses.append(WTFMove(newCharacterClass));
504	}
505
506	void atomBuiltInCharacterClass(BuiltInCharacterClassID classID, bool invert)
507	{
508	switch (classID) {
509	case BuiltInCharacterClassID::DigitClassID:
510	m_alternative->m_terms.append(other: PatternTerm(m_pattern.digitsCharacterClass(), invert));
511	break;
512	case BuiltInCharacterClassID::SpaceClassID:
513	m_alternative->m_terms.append(other: PatternTerm(m_pattern.spacesCharacterClass(), invert));
514	break;
515	case BuiltInCharacterClassID::WordClassID:
516	if (m_pattern.unicode() && m_pattern.ignoreCase())
517	m_alternative->m_terms.append(other: PatternTerm(m_pattern.wordUnicodeIgnoreCaseCharCharacterClass(), invert));
518	else
519	m_alternative->m_terms.append(other: PatternTerm(m_pattern.wordcharCharacterClass(), invert));
520	break;
521	case BuiltInCharacterClassID::DotClassID:
522	ASSERT(!invert);
523	if (m_pattern.dotAll())
524	m_alternative->m_terms.append(other: PatternTerm(m_pattern.anyCharacterClass(), false));
525	else
526	m_alternative->m_terms.append(other: PatternTerm(m_pattern.newlineCharacterClass(), true));
527	break;
528	default:
529	m_alternative->m_terms.append(other: PatternTerm(m_pattern.unicodeCharacterClassFor(unicodeClassID: classID), invert));
530	break;
531	}
532	}
533
534	void atomCharacterClassBegin(bool invert = false)
535	{
536	m_invertCharacterClass = invert;
537	}
538
539	void atomCharacterClassAtom(UChar32 ch)
540	{
541	m_characterClassConstructor.putChar(ch);
542	}
543
544	void atomCharacterClassRange(UChar32 begin, UChar32 end)
545	{
546	m_characterClassConstructor.putRange(lo: begin, hi: end);
547	}
548
549	void atomCharacterClassBuiltIn(BuiltInCharacterClassID classID, bool invert)
550	{
551	ASSERT(classID != BuiltInCharacterClassID::DotClassID);
552
553	switch (classID) {
554	case BuiltInCharacterClassID::DigitClassID:
555	m_characterClassConstructor.append(other: invert ? m_pattern.nondigitsCharacterClass() : m_pattern.digitsCharacterClass());
556	break;
557
558	case BuiltInCharacterClassID::SpaceClassID:
559	m_characterClassConstructor.append(other: invert ? m_pattern.nonspacesCharacterClass() : m_pattern.spacesCharacterClass());
560	break;
561
562	case BuiltInCharacterClassID::WordClassID:
563	if (m_pattern.unicode() && m_pattern.ignoreCase())
564	m_characterClassConstructor.append(other: invert ? m_pattern.nonwordUnicodeIgnoreCaseCharCharacterClass() : m_pattern.wordUnicodeIgnoreCaseCharCharacterClass());
565	else
566	m_characterClassConstructor.append(other: invert ? m_pattern.nonwordcharCharacterClass() : m_pattern.wordcharCharacterClass());
567	break;
568
569	default:
570	if (!invert)
571	m_characterClassConstructor.append(other: m_pattern.unicodeCharacterClassFor(unicodeClassID: classID));
572	else
573	m_characterClassConstructor.appendInverted(other: m_pattern.unicodeCharacterClassFor(unicodeClassID: classID));
574	}
575	}
576
577	void atomCharacterClassEnd()
578	{
579	auto newCharacterClass = m_characterClassConstructor.charClass();
580
581	if (!m_invertCharacterClass && newCharacterClass.get()->m_anyCharacter) {
582	m_alternative->m_terms.append(other: PatternTerm(m_pattern.anyCharacterClass(), false));
583	return;
584	}
585	m_alternative->m_terms.append(other: PatternTerm(newCharacterClass.get(), m_invertCharacterClass));
586	m_pattern.m_userCharacterClasses.append(WTFMove(newCharacterClass));
587	}
588
589	void atomParenthesesSubpatternBegin(bool capture = true, std::optional<String> optGroupName = std::nullopt)
590	{
591	unsigned subpatternId = m_pattern.m_numSubpatterns + 1;
592	if (capture) {
593	m_pattern.m_numSubpatterns++;
594	if (optGroupName) {
595	while (m_pattern.m_captureGroupNames.size() < subpatternId)
596	m_pattern.m_captureGroupNames.append(other: String());
597	m_pattern.m_captureGroupNames.append(value: optGroupName.value());
598	m_pattern.m_namedGroupToParenIndex.add(k: optGroupName.value(), v: subpatternId);
599	}
600	} else
601	ASSERT(!optGroupName);
602
603	auto parenthesesDisjunction = std::make_unique<PatternDisjunction>(m_alternative);
604	m_alternative->m_terms.append(other: PatternTerm(PatternTerm::TypeParenthesesSubpattern, subpatternId, parenthesesDisjunction.get(), capture, false));
605	m_alternative = parenthesesDisjunction->addNewAlternative();
606	m_pattern.m_disjunctions.append(WTFMove(parenthesesDisjunction));
607	}
608
609	void atomParentheticalAssertionBegin(bool invert = false)
610	{
611	auto parenthesesDisjunction = std::make_unique<PatternDisjunction>(m_alternative);
612	m_alternative->m_terms.append(other: PatternTerm(PatternTerm::TypeParentheticalAssertion, m_pattern.m_numSubpatterns + 1, parenthesesDisjunction.get(), false, invert));
613	m_alternative = parenthesesDisjunction->addNewAlternative();
614	m_invertParentheticalAssertion = invert;
615	m_pattern.m_disjunctions.append(WTFMove(parenthesesDisjunction));
616	}
617
618	void atomParenthesesEnd()
619	{
620	ASSERT(m_alternative->m_parent);
621	ASSERT(m_alternative->m_parent->m_parent);
622
623	PatternDisjunction* parenthesesDisjunction = m_alternative->m_parent;
624	m_alternative = m_alternative->m_parent->m_parent;
625
626	PatternTerm& lastTerm = m_alternative->lastTerm();
627
628	unsigned numParenAlternatives = parenthesesDisjunction->m_alternatives.size();
629	unsigned numBOLAnchoredAlts = 0;
630
631	for (unsigned i = 0; i < numParenAlternatives; i++) {
632	// Bubble up BOL flags
633	if (parenthesesDisjunction->m_alternatives[i]->m_startsWithBOL)
634	numBOLAnchoredAlts++;
635	}
636
637	if (numBOLAnchoredAlts) {
638	m_alternative->m_containsBOL = true;
639	// If all the alternatives in parens start with BOL, then so does this one
640	if (numBOLAnchoredAlts == numParenAlternatives)
641	m_alternative->m_startsWithBOL = true;
642	}
643
644	lastTerm.parentheses.lastSubpatternId = m_pattern.m_numSubpatterns;
645	m_invertParentheticalAssertion = false;
646	}
647
648	void atomBackReference(unsigned subpatternId)
649	{
650	ASSERT(subpatternId);
651	m_pattern.m_containsBackreferences = true;
652	m_pattern.m_maxBackReference = std::max(m_pattern.m_maxBackReference, subpatternId);
653
654	if (subpatternId > m_pattern.m_numSubpatterns) {
655	m_alternative->m_terms.append(other: PatternTerm::ForwardReference());
656	return;
657	}
658
659	PatternAlternative* currentAlternative = m_alternative;
660	ASSERT(currentAlternative);
661
662	// Note to self: if we waited until the AST was baked, we could also remove forwards refs
663	while ((currentAlternative = currentAlternative->m_parent->m_parent)) {
664	PatternTerm& term = currentAlternative->lastTerm();
665	ASSERT((term.type == PatternTerm::TypeParenthesesSubpattern) || (term.type == PatternTerm::TypeParentheticalAssertion));
666
667	if ((term.type == PatternTerm::TypeParenthesesSubpattern) && term.capture() && (subpatternId == term.parentheses.subpatternId)) {
668	m_alternative->m_terms.append(other: PatternTerm::ForwardReference());
669	return;
670	}
671	}
672
673	m_alternative->m_terms.append(other: PatternTerm(subpatternId));
674	}
675
676	void atomNamedBackReference(const String& subpatternName)
677	{
678	ASSERT(m_pattern.m_namedGroupToParenIndex.find(subpatternName) != m_pattern.m_namedGroupToParenIndex.end());
679	atomBackReference(subpatternId: m_pattern.m_namedGroupToParenIndex.get(k: subpatternName));
680	}
681
682	bool isValidNamedForwardReference(const String& subpatternName)
683	{
684	return !m_unmatchedNamedForwardReferences.contains(subpatternName);
685	}
686
687	void atomNamedForwardReference(const String& subpatternName)
688	{
689	if (!m_pattern.m_namedForwardReferences.contains(value: subpatternName))
690	m_pattern.m_namedForwardReferences.append(value: subpatternName);
691	m_alternative->m_terms.append(other: PatternTerm::ForwardReference());
692	}
693
694	// deep copy the argument disjunction. If filterStartsWithBOL is true,
695	// skip alternatives with m_startsWithBOL set true.
696	PatternDisjunction* copyDisjunction(PatternDisjunction* disjunction, bool filterStartsWithBOL = false)
697	{
698	std::unique_ptr<PatternDisjunction> newDisjunction;
699	for (unsigned alt = 0; alt < disjunction->m_alternatives.size(); ++alt) {
700	PatternAlternative* alternative = disjunction->m_alternatives[alt].get();
701	if (!filterStartsWithBOL || !alternative->m_startsWithBOL) {
702	if (!newDisjunction) {
703	newDisjunction = std::make_unique<PatternDisjunction>();
704	newDisjunction->m_parent = disjunction->m_parent;
705	}
706	PatternAlternative* newAlternative = newDisjunction->addNewAlternative();
707	newAlternative->m_terms.reserveInitialCapacity(size: alternative->m_terms.size());
708	for (unsigned i = 0; i < alternative->m_terms.size(); ++i)
709	newAlternative->m_terms.append(other: copyTerm(term&: alternative->m_terms[i], filterStartsWithBOL));
710	}
711	}
712
713	if (!newDisjunction)
714	return 0;
715
716	PatternDisjunction* copiedDisjunction = newDisjunction.get();
717	m_pattern.m_disjunctions.append(WTFMove(newDisjunction));
718	return copiedDisjunction;
719	}
720
721	PatternTerm copyTerm(PatternTerm& term, bool filterStartsWithBOL = false)
722	{
723	if ((term.type != PatternTerm::TypeParenthesesSubpattern) && (term.type != PatternTerm::TypeParentheticalAssertion))
724	return PatternTerm(term);
725
726	PatternTerm termCopy = term;
727	termCopy.parentheses.disjunction = copyDisjunction(disjunction: termCopy.parentheses.disjunction, filterStartsWithBOL);
728	m_pattern.m_hasCopiedParenSubexpressions = true;
729	return termCopy;
730	}
731
732	void quantifyAtom(unsigned min, unsigned max, bool greedy)
733	{
734	ASSERT(min <= max);
735	ASSERT(m_alternative->m_terms.size());
736
737	if (!max) {
738	m_alternative->removeLastTerm();
739	return;
740	}
741
742	PatternTerm& term = m_alternative->lastTerm();
743	ASSERT(term.type > PatternTerm::TypeAssertionWordBoundary);
744	ASSERT(term.quantityMinCount == 1 && term.quantityMaxCount == 1 && term.quantityType == QuantifierFixedCount);
745
746	if (term.type == PatternTerm::TypeParentheticalAssertion) {
747	// If an assertion is quantified with a minimum count of zero, it can simply be removed.
748	// This arises from the RepeatMatcher behaviour in the spec. Matching an assertion never
749	// results in any input being consumed, however the continuation passed to the assertion
750	// (called in steps, 8c and 9 of the RepeatMatcher definition, ES5.1 15.10.2.5) will
751	// reject all zero length matches (see step 2.1). A match from the continuation of the
752	// expression will still be accepted regardless (via steps 8a and 11) - the upshot of all
753	// this is that matches from the assertion are not required, and won't be accepted anyway,
754	// so no need to ever run it.
755	if (!min)
756	m_alternative->removeLastTerm();
757	// We never need to run an assertion more than once. Subsequent interations will be run
758	// with the same start index (since assertions are non-capturing) and the same captures
759	// (per step 4 of RepeatMatcher in ES5.1 15.10.2.5), and as such will always produce the
760	// same result and captures. If the first match succeeds then the subsequent (min - 1)
761	// matches will too. Any additional optional matches will fail (on the same basis as the
762	// minimum zero quantified assertions, above), but this will still result in a match.
763	return;
764	}
765
766	if (min == max)
767	term.quantify(minCount: min, maxCount: max, type: QuantifierFixedCount);
768	else if (!min || (term.type == PatternTerm::TypeParenthesesSubpattern && m_pattern.m_hasCopiedParenSubexpressions))
769	term.quantify(minCount: min, maxCount: max, type: greedy ? QuantifierGreedy : QuantifierNonGreedy);
770	else {
771	term.quantify(minCount: min, maxCount: min, type: QuantifierFixedCount);
772	m_alternative->m_terms.append(other: copyTerm(term));
773	// NOTE: this term is interesting from an analysis perspective, in that it can be ignored.....
774	m_alternative->lastTerm().quantify(count: (max == quantifyInfinite) ? max : max - min, type: greedy ? QuantifierGreedy : QuantifierNonGreedy);
775	if (m_alternative->lastTerm().type == PatternTerm::TypeParenthesesSubpattern)
776	m_alternative->lastTerm().parentheses.isCopy = true;
777	}
778	}
779
780	void disjunction()
781	{
782	m_alternative = m_alternative->m_parent->addNewAlternative();
783	}
784
785	ErrorCode setupAlternativeOffsets(PatternAlternative* alternative, unsigned currentCallFrameSize, unsigned initialInputPosition, unsigned& newCallFrameSize) WARN_UNUSED_RETURN
786	{
787	if (UNLIKELY(!isSafeToRecurse()))
788	return ErrorCode::TooManyDisjunctions;
789
790	ErrorCode error = ErrorCode::NoError;
791	alternative->m_hasFixedSize = true;
792	Checked<unsigned, RecordOverflow> currentInputPosition = initialInputPosition;
793
794	for (unsigned i = 0; i < alternative->m_terms.size(); ++i) {
795	PatternTerm& term = alternative->m_terms[i];
796
797	switch (term.type) {
798	case PatternTerm::TypeAssertionBOL:
799	case PatternTerm::TypeAssertionEOL:
800	case PatternTerm::TypeAssertionWordBoundary:
801	term.inputPosition = currentInputPosition.unsafeGet();
802	break;
803
804	case PatternTerm::TypeBackReference:
805	term.inputPosition = currentInputPosition.unsafeGet();
806	term.frameLocation = currentCallFrameSize;
807	currentCallFrameSize += YarrStackSpaceForBackTrackInfoBackReference;
808	alternative->m_hasFixedSize = false;
809	break;
810
811	case PatternTerm::TypeForwardReference:
812	break;
813
814	case PatternTerm::TypePatternCharacter:
815	term.inputPosition = currentInputPosition.unsafeGet();
816	if (term.quantityType != QuantifierFixedCount) {
817	term.frameLocation = currentCallFrameSize;
818	currentCallFrameSize += YarrStackSpaceForBackTrackInfoPatternCharacter;
819	alternative->m_hasFixedSize = false;
820	} else if (m_pattern.unicode()) {
821	Checked<unsigned, RecordOverflow> tempCount = term.quantityMaxCount;
822	tempCount *= U16_LENGTH(term.patternCharacter);
823	if (tempCount.hasOverflowed())
824	return ErrorCode::OffsetTooLarge;
825	currentInputPosition += tempCount;
826	} else
827	currentInputPosition += term.quantityMaxCount;
828	break;
829
830	case PatternTerm::TypeCharacterClass:
831	term.inputPosition = currentInputPosition.unsafeGet();
832	if (term.quantityType != QuantifierFixedCount) {
833	term.frameLocation = currentCallFrameSize;
834	currentCallFrameSize += YarrStackSpaceForBackTrackInfoCharacterClass;
835	alternative->m_hasFixedSize = false;
836	} else if (m_pattern.unicode()) {
837	term.frameLocation = currentCallFrameSize;
838	currentCallFrameSize += YarrStackSpaceForBackTrackInfoCharacterClass;
839	currentInputPosition += term.quantityMaxCount;
840	alternative->m_hasFixedSize = false;
841	} else
842	currentInputPosition += term.quantityMaxCount;
843	break;
844
845	case PatternTerm::TypeParenthesesSubpattern:
846	// Note: for fixed once parentheses we will ensure at least the minimum is available; others are on their own.
847	term.frameLocation = currentCallFrameSize;
848	if (term.quantityMaxCount == 1 && !term.parentheses.isCopy) {
849	currentCallFrameSize += YarrStackSpaceForBackTrackInfoParenthesesOnce;
850	error = setupDisjunctionOffsets(disjunction: term.parentheses.disjunction, initialCallFrameSize: currentCallFrameSize, initialInputPosition: currentInputPosition.unsafeGet(), callFrameSize&: currentCallFrameSize);
851	if (hasError(errorCode: error))
852	return error;
853	// If quantity is fixed, then pre-check its minimum size.
854	if (term.quantityType == QuantifierFixedCount)
855	currentInputPosition += term.parentheses.disjunction->m_minimumSize;
856	term.inputPosition = currentInputPosition.unsafeGet();
857	} else if (term.parentheses.isTerminal) {
858	currentCallFrameSize += YarrStackSpaceForBackTrackInfoParenthesesTerminal;
859	error = setupDisjunctionOffsets(disjunction: term.parentheses.disjunction, initialCallFrameSize: currentCallFrameSize, initialInputPosition: currentInputPosition.unsafeGet(), callFrameSize&: currentCallFrameSize);
860	if (hasError(errorCode: error))
861	return error;
862	term.inputPosition = currentInputPosition.unsafeGet();
863	} else {
864	term.inputPosition = currentInputPosition.unsafeGet();
865	currentCallFrameSize += YarrStackSpaceForBackTrackInfoParentheses;
866	error = setupDisjunctionOffsets(disjunction: term.parentheses.disjunction, initialCallFrameSize: currentCallFrameSize, initialInputPosition: currentInputPosition.unsafeGet(), callFrameSize&: currentCallFrameSize);
867	if (hasError(errorCode: error))
868	return error;
869	}
870	// Fixed count of 1 could be accepted, if they have a fixed size *AND* if all alternatives are of the same length.
871	alternative->m_hasFixedSize = false;
872	break;
873
874	case PatternTerm::TypeParentheticalAssertion:
875	term.inputPosition = currentInputPosition.unsafeGet();
876	term.frameLocation = currentCallFrameSize;
877	error = setupDisjunctionOffsets(disjunction: term.parentheses.disjunction, initialCallFrameSize: currentCallFrameSize + YarrStackSpaceForBackTrackInfoParentheticalAssertion, initialInputPosition: currentInputPosition.unsafeGet(), callFrameSize&: currentCallFrameSize);
878	if (hasError(errorCode: error))
879	return error;
880	break;
881
882	case PatternTerm::TypeDotStarEnclosure:
883	ASSERT(!m_pattern.m_saveInitialStartValue);
884	alternative->m_hasFixedSize = false;
885	term.inputPosition = initialInputPosition;
886	m_pattern.m_initialStartValueFrameLocation = currentCallFrameSize;
887	currentCallFrameSize += YarrStackSpaceForDotStarEnclosure;
888	m_pattern.m_saveInitialStartValue = true;
889	break;
890	}
891	if (currentInputPosition.hasOverflowed())
892	return ErrorCode::OffsetTooLarge;
893	}
894
895	alternative->m_minimumSize = (currentInputPosition - initialInputPosition).unsafeGet();
896	newCallFrameSize = currentCallFrameSize;
897	return error;
898	}
899
900	ErrorCode setupDisjunctionOffsets(PatternDisjunction* disjunction, unsigned initialCallFrameSize, unsigned initialInputPosition, unsigned& callFrameSize)
901	{
902	if (UNLIKELY(!isSafeToRecurse()))
903	return ErrorCode::TooManyDisjunctions;
904
905	if ((disjunction != m_pattern.m_body) && (disjunction->m_alternatives.size() > 1))
906	initialCallFrameSize += YarrStackSpaceForBackTrackInfoAlternative;
907
908	unsigned minimumInputSize = UINT_MAX;
909	unsigned maximumCallFrameSize = 0;
910	bool hasFixedSize = true;
911	ErrorCode error = ErrorCode::NoError;
912
913	for (unsigned alt = 0; alt < disjunction->m_alternatives.size(); ++alt) {
914	PatternAlternative* alternative = disjunction->m_alternatives[alt].get();
915	unsigned currentAlternativeCallFrameSize;
916	error = setupAlternativeOffsets(alternative, currentCallFrameSize: initialCallFrameSize, initialInputPosition, newCallFrameSize&: currentAlternativeCallFrameSize);
917	if (hasError(errorCode: error))
918	return error;
919	minimumInputSize = std::min(minimumInputSize, alternative->m_minimumSize);
920	maximumCallFrameSize = std::max(maximumCallFrameSize, currentAlternativeCallFrameSize);
921	hasFixedSize &= alternative->m_hasFixedSize;
922	if (alternative->m_minimumSize > INT_MAX)
923	m_pattern.m_containsUnsignedLengthPattern = true;
924	}
925
926	ASSERT(minimumInputSize != UINT_MAX);
927	ASSERT(maximumCallFrameSize >= initialCallFrameSize);
928
929	disjunction->m_hasFixedSize = hasFixedSize;
930	disjunction->m_minimumSize = minimumInputSize;
931	disjunction->m_callFrameSize = maximumCallFrameSize;
932	callFrameSize = maximumCallFrameSize;
933	return error;
934	}
935
936	ErrorCode setupOffsets()
937	{
938	// FIXME: Yarr should not use the stack to handle subpatterns (rdar://problem/26436314).
939	unsigned ignoredCallFrameSize;
940	return setupDisjunctionOffsets(disjunction: m_pattern.m_body, initialCallFrameSize: 0, initialInputPosition: 0, callFrameSize&: ignoredCallFrameSize);
941	}
942
943	// This optimization identifies sets of parentheses that we will never need to backtrack.
944	// In these cases we do not need to store state from prior iterations.
945	// We can presently avoid backtracking for:
946	// * where the parens are at the end of the regular expression (last term in any of the
947	// alternatives of the main body disjunction).
948	// * where the parens are non-capturing, and quantified unbounded greedy (*).
949	// * where the parens do not contain any capturing subpatterns.
950	void checkForTerminalParentheses()
951	{
952	// This check is much too crude; should be just checking whether the candidate
953	// node contains nested capturing subpatterns, not the whole expression!
954	if (m_pattern.m_numSubpatterns)
955	return;
956
957	Vector<std::unique_ptr<PatternAlternative>>& alternatives = m_pattern.m_body->m_alternatives;
958	for (size_t i = 0; i < alternatives.size(); ++i) {
959	Vector<PatternTerm>& terms = alternatives[i]->m_terms;
960	if (terms.size()) {
961	PatternTerm& term = terms.last();
962	if (term.type == PatternTerm::TypeParenthesesSubpattern
963	&& term.quantityType == QuantifierGreedy
964	&& term.quantityMinCount == 0
965	&& term.quantityMaxCount == quantifyInfinite
966	&& !term.capture())
967	term.parentheses.isTerminal = true;
968	}
969	}
970	}
971
972	void optimizeBOL()
973	{
974	// Look for expressions containing beginning of line (^) anchoring and unroll them.
975	// e.g. /^a|^b|c/ becomes /^a|^b|c/ which is executed once followed by /c/ which loops
976	// This code relies on the parsing code tagging alternatives with m_containsBOL and
977	// m_startsWithBOL and rolling those up to containing alternatives.
978	// At this point, this is only valid for non-multiline expressions.
979	PatternDisjunction* disjunction = m_pattern.m_body;
980
981	if (!m_pattern.m_containsBOL || m_pattern.multiline())
982	return;
983
984	PatternDisjunction* loopDisjunction = copyDisjunction(disjunction, filterStartsWithBOL: true);
985
986	// Set alternatives in disjunction to "onceThrough"
987	for (unsigned alt = 0; alt < disjunction->m_alternatives.size(); ++alt)
988	disjunction->m_alternatives[alt]->setOnceThrough();
989
990	if (loopDisjunction) {
991	// Move alternatives from loopDisjunction to disjunction
992	for (unsigned alt = 0; alt < loopDisjunction->m_alternatives.size(); ++alt)
993	disjunction->m_alternatives.append(loopDisjunction->m_alternatives[alt].release());
994
995	loopDisjunction->m_alternatives.clear();
996	}
997	}
998
999	bool containsCapturingTerms(PatternAlternative* alternative, size_t firstTermIndex, size_t endIndex)
1000	{
1001	Vector<PatternTerm>& terms = alternative->m_terms;
1002
1003	ASSERT(endIndex <= terms.size());
1004	for (size_t termIndex = firstTermIndex; termIndex < endIndex; ++termIndex) {
1005	PatternTerm& term = terms[termIndex];
1006
1007	if (term.m_capture)
1008	return true;
1009
1010	if (term.type == PatternTerm::TypeParenthesesSubpattern) {
1011	PatternDisjunction* nestedDisjunction = term.parentheses.disjunction;
1012	for (unsigned alt = 0; alt < nestedDisjunction->m_alternatives.size(); ++alt) {
1013	if (containsCapturingTerms(nestedDisjunction->m_alternatives[alt].get(), 0, nestedDisjunction->m_alternatives[alt]->m_terms.size()))
1014	return true;
1015	}
1016	}
1017	}
1018
1019	return false;
1020	}
1021
1022	// This optimization identifies alternatives in the form of
1023	// [^].*[?]<expression>.*[$] for expressions that don't have any
1024	// capturing terms. The alternative is changed to <expression>
1025	// followed by processing of the dot stars to find and adjust the
1026	// beginning and the end of the match.
1027	void optimizeDotStarWrappedExpressions()
1028	{
1029	Vector<std::unique_ptr<PatternAlternative>>& alternatives = m_pattern.m_body->m_alternatives;
1030	if (alternatives.size() != 1)
1031	return;
1032
1033	CharacterClass* dotCharacterClass = m_pattern.dotAll() ? m_pattern.anyCharacterClass() : m_pattern.newlineCharacterClass();
1034	PatternAlternative* alternative = alternatives[0].get();
1035	Vector<PatternTerm>& terms = alternative->m_terms;
1036	if (terms.size() >= 3) {
1037	bool startsWithBOL = false;
1038	bool endsWithEOL = false;
1039	size_t termIndex, firstExpressionTerm;
1040
1041	termIndex = 0;
1042	if (terms[termIndex].type == PatternTerm::TypeAssertionBOL) {
1043	startsWithBOL = true;
1044	++termIndex;
1045	}
1046
1047	PatternTerm& firstNonAnchorTerm = terms[termIndex];
1048	if (firstNonAnchorTerm.type != PatternTerm::TypeCharacterClass
1049	|| firstNonAnchorTerm.characterClass != dotCharacterClass
1050	|| firstNonAnchorTerm.quantityMinCount
1051	|| firstNonAnchorTerm.quantityMaxCount != quantifyInfinite)
1052	return;
1053
1054	firstExpressionTerm = termIndex + 1;
1055
1056	termIndex = terms.size() - 1;
1057	if (terms[termIndex].type == PatternTerm::TypeAssertionEOL) {
1058	endsWithEOL = true;
1059	--termIndex;
1060	}
1061
1062	PatternTerm& lastNonAnchorTerm = terms[termIndex];
1063	if (lastNonAnchorTerm.type != PatternTerm::TypeCharacterClass
1064	|| lastNonAnchorTerm.characterClass != dotCharacterClass
1065	|| lastNonAnchorTerm.quantityType != QuantifierGreedy
1066	|| lastNonAnchorTerm.quantityMinCount
1067	|| lastNonAnchorTerm.quantityMaxCount != quantifyInfinite)
1068	return;
1069
1070	size_t endIndex = termIndex;
1071	if (firstExpressionTerm >= endIndex)
1072	return;
1073
1074	if (!containsCapturingTerms(alternative, firstTermIndex: firstExpressionTerm, endIndex)) {
1075	for (termIndex = terms.size() - 1; termIndex >= endIndex; --termIndex)
1076	terms.remove(termIndex);
1077
1078	for (termIndex = firstExpressionTerm; termIndex > 0; --termIndex)
1079	terms.remove(termIndex - 1);
1080
1081	terms.append(PatternTerm(startsWithBOL, endsWithEOL));
1082
1083	m_pattern.m_containsBOL = false;
1084	}
1085	}
1086	}
1087
1088	private:
1089	bool isSafeToRecurse() const
1090	{
1091	if (!m_stackLimit)
1092	return true;
1093	int8_t* curr = reinterpret_cast<int8_t*>(&curr);
1094	int8_t* limit = reinterpret_cast<int8_t*>(m_stackLimit);
1095	return curr >= limit;
1096	}
1097
1098	YarrPattern& m_pattern;
1099	PatternAlternative* m_alternative;
1100	CharacterClassConstructor m_characterClassConstructor;
1101	Vector<String> m_unmatchedNamedForwardReferences;
1102	void* m_stackLimit;
1103	bool m_invertCharacterClass;
1104	bool m_invertParentheticalAssertion { false };
1105	};
1106
1107	ErrorCode YarrPattern::compile(const String& patternString, void* stackLimit)
1108	{
1109	YarrPatternConstructor constructor(*this, stackLimit);
1110
1111	if (m_flags == InvalidFlags)
1112	return ErrorCode::InvalidRegularExpressionFlags;
1113
1114	{
1115	ErrorCode error = parse(constructor, patternString, unicode());
1116	if (hasError(errorCode: error))
1117	return error;
1118	}
1119
1120	// If the pattern contains illegal backreferences reset & reparse.
1121	// Quoting Netscape's "What's new in JavaScript 1.2",
1122	// "Note: if the number of left parentheses is less than the number specified
1123	// in \#, the \# is taken as an octal escape as described in the next row."
1124	if (containsIllegalBackReference() || containsIllegalNamedForwardReferences()) {
1125	if (unicode())
1126	return ErrorCode::InvalidBackreference;
1127
1128	unsigned numSubpatterns = m_numSubpatterns;
1129
1130	constructor.saveUnmatchedNamedForwardReferences();
1131	constructor.resetForReparsing();
1132	ErrorCode error = parse(constructor, patternString, unicode(), numSubpatterns);
1133	ASSERT_UNUSED(error, !hasError(error));
1134	ASSERT(numSubpatterns == m_numSubpatterns);
1135	}
1136
1137	constructor.checkForTerminalParentheses();
1138	constructor.optimizeDotStarWrappedExpressions();
1139	constructor.optimizeBOL();
1140
1141	{
1142	ErrorCode error = constructor.setupOffsets();
1143	if (hasError(errorCode: error))
1144	return error;
1145	}
1146
1147	if (Options::dumpCompiledRegExpPatterns())
1148	dumpPattern(pattern: patternString);
1149
1150	return ErrorCode::NoError;
1151	}
1152
1153	YarrPattern::YarrPattern(const String& pattern, RegExpFlags flags, ErrorCode& error, void* stackLimit)
1154	: m_containsBackreferences(false)
1155	, m_containsBOL(false)
1156	, m_containsUnsignedLengthPattern(false)
1157	, m_hasCopiedParenSubexpressions(false)
1158	, m_saveInitialStartValue(false)
1159	, m_flags(flags)
1160	{
1161	error = compile(patternString: pattern, stackLimit);
1162	}
1163
1164	void indentForNestingLevel(PrintStream& out, unsigned nestingDepth)
1165	{
1166	out.print(" ");
1167	for (; nestingDepth; --nestingDepth)
1168	out.print(" ");
1169	}
1170
1171	void dumpUChar32(PrintStream& out, UChar32 c)
1172	{
1173	if (c >= ' '&& c <= 0xff)
1174	out.printf(format: "'%c'", static_cast<char>(c));
1175	else
1176	out.printf(format: "0x%04x", c);
1177	}
1178
1179	void dumpCharacterClass(PrintStream& out, YarrPattern* pattern, CharacterClass* characterClass)
1180	{
1181	if (characterClass == pattern->anyCharacterClass())
1182	out.print("<any character>");
1183	else if (characterClass == pattern->newlineCharacterClass())
1184	out.print("<newline>");
1185	else if (characterClass == pattern->digitsCharacterClass())
1186	out.print("<digits>");
1187	else if (characterClass == pattern->spacesCharacterClass())
1188	out.print("<whitespace>");
1189	else if (characterClass == pattern->wordcharCharacterClass())
1190	out.print("<word>");
1191	else if (characterClass == pattern->wordUnicodeIgnoreCaseCharCharacterClass())
1192	out.print("<unicode word ignore case>");
1193	else if (characterClass == pattern->nondigitsCharacterClass())
1194	out.print("<non-digits>");
1195	else if (characterClass == pattern->nonspacesCharacterClass())
1196	out.print("<non-whitespace>");
1197	else if (characterClass == pattern->nonwordcharCharacterClass())
1198	out.print("<non-word>");
1199	else if (characterClass == pattern->nonwordUnicodeIgnoreCaseCharCharacterClass())
1200	out.print("<unicode non-word ignore case>");
1201	else {
1202	bool needMatchesRangesSeperator = false;
1203
1204	auto dumpMatches = [&] (const char* prefix, Vector<UChar32> matches) {
1205	size_t matchesSize = matches.size();
1206	if (matchesSize) {
1207	if (needMatchesRangesSeperator)
1208	out.print(",");
1209	needMatchesRangesSeperator = true;
1210
1211	out.print(prefix, ":(");
1212	for (size_t i = 0; i < matchesSize; ++i) {
1213	if (i)
1214	out.print(",");
1215	dumpUChar32(out, matches[i]);
1216	}
1217	out.print(")");
1218	}
1219	};
1220
1221	auto dumpRanges = [&] (const char* prefix, Vector<CharacterRange> ranges) {
1222	size_t rangeSize = ranges.size();
1223	if (rangeSize) {
1224	if (needMatchesRangesSeperator)
1225	out.print(",");
1226	needMatchesRangesSeperator = true;
1227
1228	out.print(prefix, " ranges:(");
1229	for (size_t i = 0; i < rangeSize; ++i) {
1230	if (i)
1231	out.print(",");
1232	CharacterRange range = ranges[i];
1233	out.print("(");
1234	dumpUChar32(out, c: range.begin);
1235	out.print("..");
1236	dumpUChar32(out, c: range.end);
1237	out.print(")");
1238	}
1239	out.print(")");
1240	}
1241	};
1242
1243	out.print("[");
1244	dumpMatches("ASCII", characterClass->m_matches);
1245	dumpRanges("ASCII", characterClass->m_ranges);
1246	dumpMatches("Unicode", characterClass->m_matchesUnicode);
1247	dumpRanges("Unicode", characterClass->m_rangesUnicode);
1248	out.print("]");
1249	}
1250	}
1251
1252	void PatternAlternative::dump(PrintStream& out, YarrPattern* thisPattern, unsigned nestingDepth)
1253	{
1254	out.print("minimum size: ", m_minimumSize);
1255	if (m_hasFixedSize)
1256	out.print(",fixed size");
1257	if (m_onceThrough)
1258	out.print(",once through");
1259	if (m_startsWithBOL)
1260	out.print(",starts with ^");
1261	if (m_containsBOL)
1262	out.print(",contains ^");
1263	out.print("\n");
1264
1265	for (size_t i = 0; i < m_terms.size(); ++i)
1266	m_terms[i].dump(out, thisPattern, nestingDepth);
1267	}
1268
1269	void PatternTerm::dumpQuantifier(PrintStream& out)
1270	{
1271	if (quantityType == QuantifierFixedCount && quantityMinCount == 1 && quantityMaxCount == 1)
1272	return;
1273	out.print(" {", quantityMinCount.unsafeGet());
1274	if (quantityMinCount != quantityMaxCount) {
1275	if (quantityMaxCount == UINT_MAX)
1276	out.print(",...");
1277	else
1278	out.print(",", quantityMaxCount.unsafeGet());
1279	}
1280	out.print("}");
1281	if (quantityType == QuantifierGreedy)
1282	out.print(" greedy");
1283	else if (quantityType == QuantifierNonGreedy)
1284	out.print(" non-greedy");
1285	}
1286
1287	void PatternTerm::dump(PrintStream& out, YarrPattern* thisPattern, unsigned nestingDepth)
1288	{
1289	indentForNestingLevel(out, nestingDepth);
1290
1291	if (type != TypeParenthesesSubpattern && type != TypeParentheticalAssertion) {
1292	if (invert())
1293	out.print("not ");
1294	}
1295
1296	switch (type) {
1297	case TypeAssertionBOL:
1298	out.println("BOL");
1299	break;
1300	case TypeAssertionEOL:
1301	out.println("EOL");
1302	break;
1303	case TypeAssertionWordBoundary:
1304	out.println("word boundary");
1305	break;
1306	case TypePatternCharacter:
1307	out.printf(format: "character ");
1308	out.printf(format: "inputPosition %u ", inputPosition);
1309	if (thisPattern->ignoreCase() && isASCIIAlpha(patternCharacter)) {
1310	dumpUChar32(out, toASCIIUpper(patternCharacter));
1311	out.print("/");
1312	dumpUChar32(out, toASCIILower(patternCharacter));
1313	} else
1314	dumpUChar32(out, c: patternCharacter);
1315	dumpQuantifier(out);
1316	if (quantityType != QuantifierFixedCount)
1317	out.print(",frame location ", frameLocation);
1318	out.println();
1319	break;
1320	case TypeCharacterClass:
1321	out.print("character class ");
1322	dumpCharacterClass(out, pattern: thisPattern, characterClass: characterClass);
1323	dumpQuantifier(out);
1324	if (quantityType != QuantifierFixedCount || thisPattern->unicode())
1325	out.print(",frame location ", frameLocation);
1326	out.println();
1327	break;
1328	case TypeBackReference:
1329	out.print("back reference to subpattern #", backReferenceSubpatternId);
1330	out.println(",frame location ", frameLocation);
1331	break;
1332	case TypeForwardReference:
1333	out.println("forward reference");
1334	break;
1335	case TypeParenthesesSubpattern:
1336	if (m_capture)
1337	out.print("captured ");
1338	else
1339	out.print("non-captured ");
1340
1341	FALLTHROUGH;
1342	case TypeParentheticalAssertion:
1343	if (m_invert)
1344	out.print("inverted ");
1345
1346	if (type == TypeParenthesesSubpattern)
1347	out.print("subpattern");
1348	else if (type == TypeParentheticalAssertion)
1349	out.print("assertion");
1350
1351	if (m_capture)
1352	out.print(" #", parentheses.subpatternId);
1353
1354	dumpQuantifier(out);
1355
1356	if (parentheses.isCopy)
1357	out.print(",copy");
1358
1359	if (parentheses.isTerminal)
1360	out.print(",terminal");
1361
1362	out.println(",frame location ", frameLocation);
1363
1364	if (parentheses.disjunction->m_alternatives.size() > 1) {
1365	indentForNestingLevel(out, nestingDepth: nestingDepth + 1);
1366	unsigned alternativeFrameLocation = frameLocation;
1367	if (quantityMaxCount == 1 && !parentheses.isCopy)
1368	alternativeFrameLocation += YarrStackSpaceForBackTrackInfoParenthesesOnce;
1369	else if (parentheses.isTerminal)
1370	alternativeFrameLocation += YarrStackSpaceForBackTrackInfoParenthesesTerminal;
1371	else
1372	alternativeFrameLocation += YarrStackSpaceForBackTrackInfoParentheses;
1373	out.println("alternative list,frame location ", alternativeFrameLocation);
1374	}
1375
1376	parentheses.disjunction->dump(out, thisPattern, nestingDepth + 1);
1377	break;
1378	case TypeDotStarEnclosure:
1379	out.println(".* enclosure,frame location ", thisPattern->m_initialStartValueFrameLocation);
1380	break;
1381	}
1382	}
1383
1384	void PatternDisjunction::dump(PrintStream& out, YarrPattern* thisPattern, unsigned nestingDepth = 0)
1385	{
1386	unsigned alternativeCount = m_alternatives.size();
1387	for (unsigned i = 0; i < alternativeCount; ++i) {
1388	indentForNestingLevel(out, nestingDepth);
1389	if (alternativeCount > 1)
1390	out.print("alternative #", i, ": ");
1391	m_alternatives[i].get()->dump(out, thisPattern, nestingDepth + (alternativeCount > 1));
1392	}
1393	}
1394
1395	void YarrPattern::dumpPatternString(PrintStream& out, const String& patternString)
1396	{
1397	out.print("/", patternString, "/");
1398
1399	if (global())
1400	out.print("g");
1401	if (ignoreCase())
1402	out.print("i");
1403	if (multiline())
1404	out.print("m");
1405	if (unicode())
1406	out.print("u");
1407	if (sticky())
1408	out.print("y");
1409	}
1410
1411	void YarrPattern::dumpPattern(const String& patternString)
1412	{
1413	dumpPattern(out&: WTF::dataFile(), pattern: patternString);
1414	}
1415
1416	void YarrPattern::dumpPattern(PrintStream& out, const String& patternString)
1417	{
1418	out.print("RegExp pattern for ");
1419	dumpPatternString(out, patternString);
1420
1421	if (m_flags != NoFlags) {
1422	bool printSeperator = false;
1423	out.print(" (");
1424	if (global()) {
1425	out.print("global");
1426	printSeperator = true;
1427	}
1428	if (ignoreCase()) {
1429	if (printSeperator)
1430	out.print("|");
1431	out.print("ignore case");
1432	printSeperator = true;
1433	}
1434	if (multiline()) {
1435	if (printSeperator)
1436	out.print("|");
1437	out.print("multiline");
1438	printSeperator = true;
1439	}
1440	if (unicode()) {
1441	if (printSeperator)
1442	out.print("|");
1443	out.print("unicode");
1444	printSeperator = true;
1445	}
1446	if (sticky()) {
1447	if (printSeperator)
1448	out.print("|");
1449	out.print("sticky");
1450	printSeperator = true;
1451	}
1452	out.print(")");
1453	}
1454	out.print(":\n");
1455	if (m_body->m_callFrameSize)
1456	out.print(" callframe size: ", m_body->m_callFrameSize, "\n");
1457	m_body->dump(out, thisPattern: this);
1458	}
1459
1460	std::unique_ptr<CharacterClass> anycharCreate()
1461	{
1462	auto characterClass = std::make_unique<CharacterClass>();
1463	characterClass->m_ranges.append(CharacterRange(0x00, 0x7f));
1464	characterClass->m_rangesUnicode.append(CharacterRange(0x0080, 0x10ffff));
1465	characterClass->m_hasNonBMPCharacters = true;
1466	characterClass->m_anyCharacter = true;
1467	return characterClass;
1468	}
1469
1470	} } // namespace JSC::Yarr
1471