3d1e1adef5035c840d461221d15fb1305fefbe12
[WebKit-https.git] / Source / JavaScriptCore / yarr / YarrPattern.h
1 /*
2  * Copyright (C) 2009, 2013-2017 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 #pragma once
28
29 #include "RegExpKey.h"
30 #include "YarrUnicodeProperties.h"
31 #include <wtf/CheckedArithmetic.h>
32 #include <wtf/HashMap.h>
33 #include <wtf/PrintStream.h>
34 #include <wtf/Vector.h>
35 #include <wtf/text/WTFString.h>
36
37 namespace JSC { namespace Yarr {
38
39 struct YarrPattern;
40 struct PatternDisjunction;
41
42 struct CharacterRange {
43     UChar32 begin { 0 };
44     UChar32 end { 0x10ffff };
45
46     CharacterRange(UChar32 begin, UChar32 end)
47         : begin(begin)
48         , end(end)
49     {
50     }
51 };
52
53 struct CharacterClass {
54     WTF_MAKE_FAST_ALLOCATED;
55 public:
56     // All CharacterClass instances have to have the full set of matches and ranges,
57     // they may have an optional m_table for faster lookups (which must match the
58     // specified matches and ranges)
59     CharacterClass()
60         : m_table(0)
61         , m_hasNonBMPCharacters(false)
62         , m_anyCharacter(false)
63     {
64     }
65     CharacterClass(const char* table, bool inverted)
66         : m_table(table)
67         , m_tableInverted(inverted)
68         , m_hasNonBMPCharacters(false)
69         , m_anyCharacter(false)
70     {
71     }
72     CharacterClass(std::initializer_list<UChar32> matches, std::initializer_list<CharacterRange> ranges, std::initializer_list<UChar32> matchesUnicode, std::initializer_list<CharacterRange> rangesUnicode)
73         : m_matches(matches)
74         , m_ranges(ranges)
75         , m_matchesUnicode(matchesUnicode)
76         , m_rangesUnicode(rangesUnicode)
77         , m_table(0)
78         , m_tableInverted(false)
79         , m_hasNonBMPCharacters(false)
80         , m_anyCharacter(false)
81     {
82     }
83
84     Vector<UChar32> m_matches;
85     Vector<CharacterRange> m_ranges;
86     Vector<UChar32> m_matchesUnicode;
87     Vector<CharacterRange> m_rangesUnicode;
88
89     const char* m_table;
90     bool m_tableInverted : 1;
91     bool m_hasNonBMPCharacters : 1;
92     bool m_anyCharacter : 1;
93 };
94
95 enum QuantifierType {
96     QuantifierFixedCount,
97     QuantifierGreedy,
98     QuantifierNonGreedy,
99 };
100
101 struct PatternTerm {
102     enum Type {
103         TypeAssertionBOL,
104         TypeAssertionEOL,
105         TypeAssertionWordBoundary,
106         TypePatternCharacter,
107         TypeCharacterClass,
108         TypeBackReference,
109         TypeForwardReference,
110         TypeParenthesesSubpattern,
111         TypeParentheticalAssertion,
112         TypeDotStarEnclosure,
113     } type;
114     bool m_capture :1;
115     bool m_invert :1;
116     union {
117         UChar32 patternCharacter;
118         CharacterClass* characterClass;
119         unsigned backReferenceSubpatternId;
120         struct {
121             PatternDisjunction* disjunction;
122             unsigned subpatternId;
123             unsigned lastSubpatternId;
124             bool isCopy;
125             bool isTerminal;
126         } parentheses;
127         struct {
128             bool bolAnchor : 1;
129             bool eolAnchor : 1;
130         } anchors;
131     };
132     QuantifierType quantityType;
133     Checked<unsigned> quantityMinCount;
134     Checked<unsigned> quantityMaxCount;
135     unsigned inputPosition;
136     unsigned frameLocation;
137
138     PatternTerm(UChar32 ch)
139         : type(PatternTerm::TypePatternCharacter)
140         , m_capture(false)
141         , m_invert(false)
142     {
143         patternCharacter = ch;
144         quantityType = QuantifierFixedCount;
145         quantityMinCount = quantityMaxCount = 1;
146     }
147
148     PatternTerm(CharacterClass* charClass, bool invert)
149         : type(PatternTerm::TypeCharacterClass)
150         , m_capture(false)
151         , m_invert(invert)
152     {
153         characterClass = charClass;
154         quantityType = QuantifierFixedCount;
155         quantityMinCount = quantityMaxCount = 1;
156     }
157
158     PatternTerm(Type type, unsigned subpatternId, PatternDisjunction* disjunction, bool capture = false, bool invert = false)
159         : type(type)
160         , m_capture(capture)
161         , m_invert(invert)
162     {
163         parentheses.disjunction = disjunction;
164         parentheses.subpatternId = subpatternId;
165         parentheses.isCopy = false;
166         parentheses.isTerminal = false;
167         quantityType = QuantifierFixedCount;
168         quantityMinCount = quantityMaxCount = 1;
169     }
170     
171     PatternTerm(Type type, bool invert = false)
172         : type(type)
173         , m_capture(false)
174         , m_invert(invert)
175     {
176         quantityType = QuantifierFixedCount;
177         quantityMinCount = quantityMaxCount = 1;
178     }
179
180     PatternTerm(unsigned spatternId)
181         : type(TypeBackReference)
182         , m_capture(false)
183         , m_invert(false)
184     {
185         backReferenceSubpatternId = spatternId;
186         quantityType = QuantifierFixedCount;
187         quantityMinCount = quantityMaxCount = 1;
188     }
189
190     PatternTerm(bool bolAnchor, bool eolAnchor)
191         : type(TypeDotStarEnclosure)
192         , m_capture(false)
193         , m_invert(false)
194     {
195         anchors.bolAnchor = bolAnchor;
196         anchors.eolAnchor = eolAnchor;
197         quantityType = QuantifierFixedCount;
198         quantityMinCount = quantityMaxCount = 1;
199     }
200     
201     static PatternTerm ForwardReference()
202     {
203         return PatternTerm(TypeForwardReference);
204     }
205
206     static PatternTerm BOL()
207     {
208         return PatternTerm(TypeAssertionBOL);
209     }
210
211     static PatternTerm EOL()
212     {
213         return PatternTerm(TypeAssertionEOL);
214     }
215
216     static PatternTerm WordBoundary(bool invert)
217     {
218         return PatternTerm(TypeAssertionWordBoundary, invert);
219     }
220     
221     bool invert()
222     {
223         return m_invert;
224     }
225
226     bool capture()
227     {
228         return m_capture;
229     }
230     
231     void quantify(unsigned count, QuantifierType type)
232     {
233         quantityMinCount = 0;
234         quantityMaxCount = count;
235         quantityType = type;
236     }
237
238     void quantify(unsigned minCount, unsigned maxCount, QuantifierType type)
239     {
240         // Currently only Parentheses can specify a non-zero min with a different max.
241         ASSERT(this->type == TypeParenthesesSubpattern || !minCount || minCount == maxCount);
242         ASSERT(minCount <= maxCount);
243         quantityMinCount = minCount;
244         quantityMaxCount = maxCount;
245         quantityType = type;
246     }
247
248     void dumpQuantifier(PrintStream&);
249     void dump(PrintStream&, YarrPattern*, unsigned);
250 };
251
252 struct PatternAlternative {
253     WTF_MAKE_FAST_ALLOCATED;
254 public:
255     PatternAlternative(PatternDisjunction* disjunction)
256         : m_parent(disjunction)
257         , m_onceThrough(false)
258         , m_hasFixedSize(false)
259         , m_startsWithBOL(false)
260         , m_containsBOL(false)
261     {
262     }
263
264     PatternTerm& lastTerm()
265     {
266         ASSERT(m_terms.size());
267         return m_terms[m_terms.size() - 1];
268     }
269     
270     void removeLastTerm()
271     {
272         ASSERT(m_terms.size());
273         m_terms.shrink(m_terms.size() - 1);
274     }
275     
276     void setOnceThrough()
277     {
278         m_onceThrough = true;
279     }
280     
281     bool onceThrough()
282     {
283         return m_onceThrough;
284     }
285
286     void dump(PrintStream&, YarrPattern*, unsigned);
287
288     Vector<PatternTerm> m_terms;
289     PatternDisjunction* m_parent;
290     unsigned m_minimumSize;
291     bool m_onceThrough : 1;
292     bool m_hasFixedSize : 1;
293     bool m_startsWithBOL : 1;
294     bool m_containsBOL : 1;
295 };
296
297 struct PatternDisjunction {
298     WTF_MAKE_FAST_ALLOCATED;
299 public:
300     PatternDisjunction(PatternAlternative* parent = 0)
301         : m_parent(parent)
302         , m_hasFixedSize(false)
303     {
304     }
305     
306     PatternAlternative* addNewAlternative()
307     {
308         m_alternatives.append(std::make_unique<PatternAlternative>(this));
309         return static_cast<PatternAlternative*>(m_alternatives.last().get());
310     }
311
312     void dump(PrintStream&, YarrPattern*, unsigned);
313
314     Vector<std::unique_ptr<PatternAlternative>> m_alternatives;
315     PatternAlternative* m_parent;
316     unsigned m_minimumSize;
317     unsigned m_callFrameSize;
318     bool m_hasFixedSize;
319 };
320
321 // You probably don't want to be calling these functions directly
322 // (please to be calling newlineCharacterClass() et al on your
323 // friendly neighborhood YarrPattern instance to get nicely
324 // cached copies).
325
326 std::unique_ptr<CharacterClass> anycharCreate();
327 std::unique_ptr<CharacterClass> newlineCreate();
328 std::unique_ptr<CharacterClass> digitsCreate();
329 std::unique_ptr<CharacterClass> spacesCreate();
330 std::unique_ptr<CharacterClass> wordcharCreate();
331 std::unique_ptr<CharacterClass> wordUnicodeIgnoreCaseCharCreate();
332 std::unique_ptr<CharacterClass> nondigitsCreate();
333 std::unique_ptr<CharacterClass> nonspacesCreate();
334 std::unique_ptr<CharacterClass> nonwordcharCreate();
335 std::unique_ptr<CharacterClass> nonwordUnicodeIgnoreCaseCharCreate();
336
337 struct TermChain {
338     TermChain(PatternTerm term)
339         : term(term)
340     {}
341
342     PatternTerm term;
343     Vector<TermChain> hotTerms;
344 };
345
346
347 struct YarrPattern {
348     JS_EXPORT_PRIVATE YarrPattern(const String& pattern, RegExpFlags, const char** error, void* stackLimit = nullptr);
349
350     enum ErrorCode {
351         NoError,
352         PatternTooLarge,
353         QuantifierOutOfOrder,
354         QuantifierWithoutAtom,
355         QuantifierTooLarge,
356         MissingParentheses,
357         ParenthesesUnmatched,
358         ParenthesesTypeInvalid,
359         InvalidGroupName,
360         DuplicateGroupName,
361         CharacterClassUnmatched,
362         CharacterClassOutOfOrder,
363         EscapeUnterminated,
364         InvalidUnicodeEscape,
365         InvalidBackreference,
366         InvalidIdentityEscape,
367         InvalidUnicodePropertyExpression,
368         TooManyDisjunctions,
369         OffsetTooLarge,
370         InvalidRegularExpressionFlags,
371         NumberOfErrorCodes
372     };
373     
374     JS_EXPORT_PRIVATE static const char* errorMessage(ErrorCode);
375
376     void reset()
377     {
378         m_numSubpatterns = 0;
379         m_maxBackReference = 0;
380         m_initialStartValueFrameLocation = 0;
381
382         m_containsBackreferences = false;
383         m_containsBOL = false;
384         m_containsUnsignedLengthPattern = false;
385         m_hasCopiedParenSubexpressions = false;
386         m_saveInitialStartValue = false;
387
388         anycharCached = 0;
389         newlineCached = 0;
390         digitsCached = 0;
391         spacesCached = 0;
392         wordcharCached = 0;
393         wordUnicodeIgnoreCaseCharCached = 0;
394         nondigitsCached = 0;
395         nonspacesCached = 0;
396         nonwordcharCached = 0;
397         nonwordUnicodeIgnoreCasecharCached = 0;
398         unicodePropertiesCached.clear();
399
400         m_disjunctions.clear();
401         m_userCharacterClasses.clear();
402         m_captureGroupNames.shrink(0);
403     }
404
405     bool containsIllegalBackReference()
406     {
407         return m_maxBackReference > m_numSubpatterns;
408     }
409
410     bool containsUnsignedLengthPattern()
411     {
412         return m_containsUnsignedLengthPattern;
413     }
414
415     CharacterClass* anyCharacterClass()
416     {
417         if (!anycharCached) {
418             m_userCharacterClasses.append(anycharCreate());
419             anycharCached = m_userCharacterClasses.last().get();
420         }
421         return anycharCached;
422     }
423     CharacterClass* newlineCharacterClass()
424     {
425         if (!newlineCached) {
426             m_userCharacterClasses.append(newlineCreate());
427             newlineCached = m_userCharacterClasses.last().get();
428         }
429         return newlineCached;
430     }
431     CharacterClass* digitsCharacterClass()
432     {
433         if (!digitsCached) {
434             m_userCharacterClasses.append(digitsCreate());
435             digitsCached = m_userCharacterClasses.last().get();
436         }
437         return digitsCached;
438     }
439     CharacterClass* spacesCharacterClass()
440     {
441         if (!spacesCached) {
442             m_userCharacterClasses.append(spacesCreate());
443             spacesCached = m_userCharacterClasses.last().get();
444         }
445         return spacesCached;
446     }
447     CharacterClass* wordcharCharacterClass()
448     {
449         if (!wordcharCached) {
450             m_userCharacterClasses.append(wordcharCreate());
451             wordcharCached = m_userCharacterClasses.last().get();
452         }
453         return wordcharCached;
454     }
455     CharacterClass* wordUnicodeIgnoreCaseCharCharacterClass()
456     {
457         if (!wordUnicodeIgnoreCaseCharCached) {
458             m_userCharacterClasses.append(wordUnicodeIgnoreCaseCharCreate());
459             wordUnicodeIgnoreCaseCharCached = m_userCharacterClasses.last().get();
460         }
461         return wordUnicodeIgnoreCaseCharCached;
462     }
463     CharacterClass* nondigitsCharacterClass()
464     {
465         if (!nondigitsCached) {
466             m_userCharacterClasses.append(nondigitsCreate());
467             nondigitsCached = m_userCharacterClasses.last().get();
468         }
469         return nondigitsCached;
470     }
471     CharacterClass* nonspacesCharacterClass()
472     {
473         if (!nonspacesCached) {
474             m_userCharacterClasses.append(nonspacesCreate());
475             nonspacesCached = m_userCharacterClasses.last().get();
476         }
477         return nonspacesCached;
478     }
479     CharacterClass* nonwordcharCharacterClass()
480     {
481         if (!nonwordcharCached) {
482             m_userCharacterClasses.append(nonwordcharCreate());
483             nonwordcharCached = m_userCharacterClasses.last().get();
484         }
485         return nonwordcharCached;
486     }
487     CharacterClass* nonwordUnicodeIgnoreCaseCharCharacterClass()
488     {
489         if (!nonwordUnicodeIgnoreCasecharCached) {
490             m_userCharacterClasses.append(nonwordUnicodeIgnoreCaseCharCreate());
491             nonwordUnicodeIgnoreCasecharCached = m_userCharacterClasses.last().get();
492         }
493         return nonwordUnicodeIgnoreCasecharCached;
494     }
495     CharacterClass* unicodeCharacterClassFor(BuiltInCharacterClassID unicodeClassID)
496     {
497         ASSERT(unicodeClassID >= BuiltInCharacterClassID::BaseUnicodePropertyID);
498
499         unsigned classID = static_cast<unsigned>(unicodeClassID);
500
501         if (unicodePropertiesCached.find(classID) == unicodePropertiesCached.end()) {
502             m_userCharacterClasses.append(createUnicodeCharacterClassFor(unicodeClassID));
503             CharacterClass* result = m_userCharacterClasses.last().get();
504             unicodePropertiesCached.add(classID, result);
505             return result;
506         }
507
508         return unicodePropertiesCached.get(classID);
509     }
510
511     void dumpPattern(const String& pattern);
512     void dumpPattern(PrintStream& out, const String& pattern);
513
514     bool global() const { return m_flags & FlagGlobal; }
515     bool ignoreCase() const { return m_flags & FlagIgnoreCase; }
516     bool multiline() const { return m_flags & FlagMultiline; }
517     bool sticky() const { return m_flags & FlagSticky; }
518     bool unicode() const { return m_flags & FlagUnicode; }
519     bool dotAll() const { return m_flags & FlagDotAll; }
520
521     bool m_containsBackreferences : 1;
522     bool m_containsBOL : 1;
523     bool m_containsUnsignedLengthPattern : 1;
524     bool m_hasCopiedParenSubexpressions : 1;
525     bool m_saveInitialStartValue : 1;
526     RegExpFlags m_flags;
527     unsigned m_numSubpatterns;
528     unsigned m_maxBackReference;
529     unsigned m_initialStartValueFrameLocation;
530     PatternDisjunction* m_body;
531     Vector<std::unique_ptr<PatternDisjunction>, 4> m_disjunctions;
532     Vector<std::unique_ptr<CharacterClass>> m_userCharacterClasses;
533     Vector<String> m_captureGroupNames;
534     HashMap<String, unsigned> m_namedGroupToParenIndex;
535
536 private:
537     const char* compile(const String& patternString, void* stackLimit);
538
539     CharacterClass* anycharCached;
540     CharacterClass* newlineCached;
541     CharacterClass* digitsCached;
542     CharacterClass* spacesCached;
543     CharacterClass* wordcharCached;
544     CharacterClass* wordUnicodeIgnoreCaseCharCached;
545     CharacterClass* nondigitsCached;
546     CharacterClass* nonspacesCached;
547     CharacterClass* nonwordcharCached;
548     CharacterClass* nonwordUnicodeIgnoreCasecharCached;
549     HashMap<unsigned, CharacterClass*> unicodePropertiesCached;
550 };
551
552     struct BackTrackInfoPatternCharacter {
553         uintptr_t begin; // Only needed for unicode patterns
554         uintptr_t matchAmount;
555
556         static unsigned beginIndex() { return offsetof(BackTrackInfoPatternCharacter, begin) / sizeof(uintptr_t); }
557         static unsigned matchAmountIndex() { return offsetof(BackTrackInfoPatternCharacter, matchAmount) / sizeof(uintptr_t); }
558     };
559
560     struct BackTrackInfoCharacterClass {
561         uintptr_t begin; // Only needed for unicode patterns
562         uintptr_t matchAmount;
563
564         static unsigned beginIndex() { return offsetof(BackTrackInfoCharacterClass, begin) / sizeof(uintptr_t); }
565         static unsigned matchAmountIndex() { return offsetof(BackTrackInfoCharacterClass, matchAmount) / sizeof(uintptr_t); }
566     };
567
568     struct BackTrackInfoBackReference {
569         uintptr_t begin; // Not really needed for greedy quantifiers.
570         uintptr_t matchAmount; // Not really needed for fixed quantifiers.
571
572         unsigned beginIndex() { return offsetof(BackTrackInfoBackReference, begin) / sizeof(uintptr_t); }
573         unsigned matchAmountIndex() { return offsetof(BackTrackInfoBackReference, matchAmount) / sizeof(uintptr_t); }
574     };
575
576     struct BackTrackInfoAlternative {
577         uintptr_t offset;
578
579         static unsigned offsetIndex() { return offsetof(BackTrackInfoAlternative, offset) / sizeof(uintptr_t); }
580     };
581
582     struct BackTrackInfoParentheticalAssertion {
583         uintptr_t begin;
584
585         static unsigned beginIndex() { return offsetof(BackTrackInfoParentheticalAssertion, begin) / sizeof(uintptr_t); }
586     };
587
588     struct BackTrackInfoParenthesesOnce {
589         uintptr_t begin;
590
591         static unsigned beginIndex() { return offsetof(BackTrackInfoParenthesesOnce, begin) / sizeof(uintptr_t); }
592     };
593
594     struct BackTrackInfoParenthesesTerminal {
595         uintptr_t begin;
596
597         static unsigned beginIndex() { return offsetof(BackTrackInfoParenthesesTerminal, begin) / sizeof(uintptr_t); }
598     };
599
600 } } // namespace JSC::Yarr