be31fcd35523e3f7448b111b5dcb33252a4d18d3
[WebKit-https.git] / JavaScriptCore / yarr / RegexPattern.h
1 /*
2  * Copyright (C) 2009 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 #ifndef RegexPattern_h
28 #define RegexPattern_h
29
30
31 #if ENABLE(YARR)
32
33 #include <wtf/Vector.h>
34 #include <wtf/unicode/Unicode.h>
35
36
37 namespace JSC { namespace Yarr {
38
39 #define RegexStackSpaceForBackTrackInfoPatternCharacter 1 // Only for !fixed quantifiers.
40 #define RegexStackSpaceForBackTrackInfoCharacterClass 1 // Only for !fixed quantifiers.
41 #define RegexStackSpaceForBackTrackInfoBackReference 2
42 #define RegexStackSpaceForBackTrackInfoAlternative 1 // One per alternative.
43 #define RegexStackSpaceForBackTrackInfoParentheticalAssertion 1
44 #define RegexStackSpaceForBackTrackInfoParenthesesOnce 1 // Only for !fixed quantifiers.
45 #define RegexStackSpaceForBackTrackInfoParentheses 4
46
47 struct PatternDisjunction;
48
49 struct CharacterRange {
50     UChar begin;
51     UChar end;
52
53     CharacterRange(UChar begin, UChar end)
54         : begin(begin)
55         , end(end)
56     {
57     }
58 };
59
60 struct CharacterClassTable : RefCounted<CharacterClassTable> {
61     const char* m_table;
62     bool m_inverted;
63     static PassRefPtr<CharacterClassTable> create(const char* table, bool inverted)
64     {
65         return adoptRef(new CharacterClassTable(table, inverted));
66     }
67
68 private:
69     CharacterClassTable(const char* table, bool inverted)
70         : m_table(table)
71         , m_inverted(inverted)
72     {
73     }
74 };
75
76 struct CharacterClass : FastAllocBase {
77     // All CharacterClass instances have to have the full set of matches and ranges,
78     // they may have an optional table for faster lookups (which must match the
79     // specified matches and ranges)
80     CharacterClass(PassRefPtr<CharacterClassTable> table)
81         : m_table(table)
82     {
83     }
84     Vector<UChar> m_matches;
85     Vector<CharacterRange> m_ranges;
86     Vector<UChar> m_matchesUnicode;
87     Vector<CharacterRange> m_rangesUnicode;
88     RefPtr<CharacterClassTable> m_table;
89 };
90
91 enum QuantifierType {
92     QuantifierFixedCount,
93     QuantifierGreedy,
94     QuantifierNonGreedy,
95 };
96
97 struct PatternTerm {
98     enum Type {
99         TypeAssertionBOL,
100         TypeAssertionEOL,
101         TypeAssertionWordBoundary,
102         TypePatternCharacter,
103         TypeCharacterClass,
104         TypeBackReference,
105         TypeForwardReference,
106         TypeParenthesesSubpattern,
107         TypeParentheticalAssertion,
108     } type;
109     bool invertOrCapture;
110     union {
111         UChar patternCharacter;
112         CharacterClass* characterClass;
113         unsigned subpatternId;
114         struct {
115             PatternDisjunction* disjunction;
116             unsigned subpatternId;
117             unsigned lastSubpatternId;
118             bool isCopy;
119         } parentheses;
120     };
121     QuantifierType quantityType;
122     unsigned quantityCount;
123     int inputPosition;
124     unsigned frameLocation;
125
126     PatternTerm(UChar ch)
127         : type(PatternTerm::TypePatternCharacter)
128     {
129         patternCharacter = ch;
130         quantityType = QuantifierFixedCount;
131         quantityCount = 1;
132     }
133
134     PatternTerm(CharacterClass* charClass, bool invert)
135         : type(PatternTerm::TypeCharacterClass)
136         , invertOrCapture(invert)
137     {
138         characterClass = charClass;
139         quantityType = QuantifierFixedCount;
140         quantityCount = 1;
141     }
142
143     PatternTerm(Type type, unsigned subpatternId, PatternDisjunction* disjunction, bool invertOrCapture)
144         : type(type)
145         , invertOrCapture(invertOrCapture)
146     {
147         parentheses.disjunction = disjunction;
148         parentheses.subpatternId = subpatternId;
149         parentheses.isCopy = false;
150         quantityType = QuantifierFixedCount;
151         quantityCount = 1;
152     }
153     
154     PatternTerm(Type type, bool invert = false)
155         : type(type)
156         , invertOrCapture(invert)
157     {
158         quantityType = QuantifierFixedCount;
159         quantityCount = 1;
160     }
161
162     PatternTerm(unsigned spatternId)
163         : type(TypeBackReference)
164         , invertOrCapture(false)
165     {
166         subpatternId = spatternId;
167         quantityType = QuantifierFixedCount;
168         quantityCount = 1;
169     }
170
171     static PatternTerm ForwardReference()
172     {
173         return PatternTerm(TypeForwardReference);
174     }
175
176     static PatternTerm BOL()
177     {
178         return PatternTerm(TypeAssertionBOL);
179     }
180
181     static PatternTerm EOL()
182     {
183         return PatternTerm(TypeAssertionEOL);
184     }
185
186     static PatternTerm WordBoundary(bool invert)
187     {
188         return PatternTerm(TypeAssertionWordBoundary, invert);
189     }
190     
191     bool invert()
192     {
193         return invertOrCapture;
194     }
195
196     bool capture()
197     {
198         return invertOrCapture;
199     }
200     
201     void quantify(unsigned count, QuantifierType type)
202     {
203         quantityCount = count;
204         quantityType = type;
205     }
206 };
207
208 struct PatternAlternative : FastAllocBase {
209     PatternAlternative(PatternDisjunction* disjunction)
210         : m_parent(disjunction)
211         , m_onceThrough(false)
212         , m_hasFixedSize(false)
213         , m_startsWithBOL(false)
214         , m_containsBOL(false)
215     {
216     }
217
218     PatternTerm& lastTerm()
219     {
220         ASSERT(m_terms.size());
221         return m_terms[m_terms.size() - 1];
222     }
223     
224     void removeLastTerm()
225     {
226         ASSERT(m_terms.size());
227         m_terms.shrink(m_terms.size() - 1);
228     }
229     
230     void setOnceThrough()
231     {
232         m_onceThrough = true;
233     }
234     
235     bool onceThrough()
236     {
237         return m_onceThrough;
238     }
239
240     Vector<PatternTerm> m_terms;
241     PatternDisjunction* m_parent;
242     unsigned m_minimumSize;
243     bool m_onceThrough : 1;
244     bool m_hasFixedSize : 1;
245     bool m_startsWithBOL : 1;
246     bool m_containsBOL : 1;
247 };
248
249 struct PatternDisjunction : FastAllocBase {
250     PatternDisjunction(PatternAlternative* parent = 0)
251         : m_parent(parent)
252         , m_hasFixedSize(false)
253     {
254     }
255     
256     ~PatternDisjunction()
257     {
258         deleteAllValues(m_alternatives);
259     }
260
261     PatternAlternative* addNewAlternative()
262     {
263         PatternAlternative* alternative = new PatternAlternative(this);
264         m_alternatives.append(alternative);
265         return alternative;
266     }
267
268     Vector<PatternAlternative*> m_alternatives;
269     PatternAlternative* m_parent;
270     unsigned m_minimumSize;
271     unsigned m_callFrameSize;
272     bool m_hasFixedSize;
273 };
274
275 // You probably don't want to be calling these functions directly
276 // (please to be calling newlineCharacterClass() et al on your
277 // friendly neighborhood RegexPattern instance to get nicely
278 // cached copies).
279 CharacterClass* newlineCreate();
280 CharacterClass* digitsCreate();
281 CharacterClass* spacesCreate();
282 CharacterClass* wordcharCreate();
283 CharacterClass* nondigitsCreate();
284 CharacterClass* nonspacesCreate();
285 CharacterClass* nonwordcharCreate();
286
287 struct TermChain {
288     TermChain(PatternTerm term)
289         : term(term)
290     {}
291
292     PatternTerm term;
293     Vector<TermChain> hotTerms;
294 };
295
296 struct BeginChar {
297     BeginChar()
298         : value(0)
299         , mask(0)
300     {}
301
302     BeginChar(unsigned value, unsigned mask)
303         : value(value)
304         , mask(mask)
305     {}
306
307     unsigned value;
308     unsigned mask;
309 };
310
311 struct RegexPattern {
312     RegexPattern(bool ignoreCase, bool multiline)
313         : m_ignoreCase(ignoreCase)
314         , m_multiline(multiline)
315         , m_containsBackreferences(false)
316         , m_containsBeginChars(false)
317         , m_containsBOL(false)
318         , m_numSubpatterns(0)
319         , m_maxBackReference(0)
320         , newlineCached(0)
321         , digitsCached(0)
322         , spacesCached(0)
323         , wordcharCached(0)
324         , nondigitsCached(0)
325         , nonspacesCached(0)
326         , nonwordcharCached(0)
327     {
328     }
329
330     ~RegexPattern()
331     {
332         deleteAllValues(m_disjunctions);
333         deleteAllValues(m_userCharacterClasses);
334     }
335
336     void reset()
337     {
338         m_numSubpatterns = 0;
339         m_maxBackReference = 0;
340
341         m_containsBackreferences = false;
342         m_containsBeginChars = false;
343         m_containsBOL = false;
344
345         newlineCached = 0;
346         digitsCached = 0;
347         spacesCached = 0;
348         wordcharCached = 0;
349         nondigitsCached = 0;
350         nonspacesCached = 0;
351         nonwordcharCached = 0;
352
353         deleteAllValues(m_disjunctions);
354         m_disjunctions.clear();
355         deleteAllValues(m_userCharacterClasses);
356         m_userCharacterClasses.clear();
357         m_beginChars.clear();
358     }
359
360     bool containsIllegalBackReference()
361     {
362         return m_maxBackReference > m_numSubpatterns;
363     }
364
365     CharacterClass* newlineCharacterClass()
366     {
367         if (!newlineCached)
368             m_userCharacterClasses.append(newlineCached = newlineCreate());
369         return newlineCached;
370     }
371     CharacterClass* digitsCharacterClass()
372     {
373         if (!digitsCached)
374             m_userCharacterClasses.append(digitsCached = digitsCreate());
375         return digitsCached;
376     }
377     CharacterClass* spacesCharacterClass()
378     {
379         if (!spacesCached)
380             m_userCharacterClasses.append(spacesCached = spacesCreate());
381         return spacesCached;
382     }
383     CharacterClass* wordcharCharacterClass()
384     {
385         if (!wordcharCached)
386             m_userCharacterClasses.append(wordcharCached = wordcharCreate());
387         return wordcharCached;
388     }
389     CharacterClass* nondigitsCharacterClass()
390     {
391         if (!nondigitsCached)
392             m_userCharacterClasses.append(nondigitsCached = nondigitsCreate());
393         return nondigitsCached;
394     }
395     CharacterClass* nonspacesCharacterClass()
396     {
397         if (!nonspacesCached)
398             m_userCharacterClasses.append(nonspacesCached = nonspacesCreate());
399         return nonspacesCached;
400     }
401     CharacterClass* nonwordcharCharacterClass()
402     {
403         if (!nonwordcharCached)
404             m_userCharacterClasses.append(nonwordcharCached = nonwordcharCreate());
405         return nonwordcharCached;
406     }
407
408     bool m_ignoreCase : 1;
409     bool m_multiline : 1;
410     bool m_containsBackreferences : 1;
411     bool m_containsBeginChars : 1;
412     bool m_containsBOL : 1;
413     unsigned m_numSubpatterns;
414     unsigned m_maxBackReference;
415     PatternDisjunction* m_body;
416     Vector<PatternDisjunction*, 4> m_disjunctions;
417     Vector<CharacterClass*> m_userCharacterClasses;
418     Vector<BeginChar> m_beginChars;
419
420 private:
421     CharacterClass* newlineCached;
422     CharacterClass* digitsCached;
423     CharacterClass* spacesCached;
424     CharacterClass* wordcharCached;
425     CharacterClass* nondigitsCached;
426     CharacterClass* nonspacesCached;
427     CharacterClass* nonwordcharCached;
428 };
429
430 } } // namespace JSC::Yarr
431
432 #endif
433
434 #endif // RegexPattern_h