eecbd4378a487f54e104bf4b699e49d08e783da9
[WebKit-https.git] / JavaScriptCore / yarr / RegexPattern.h
1 /*
2  * Copyright (C) 2009 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #ifndef RegexPattern_h
27 #define RegexPattern_h
28
29
30 #if ENABLE(YARR)
31
32 #include <wtf/Vector.h>
33 #include <wtf/unicode/Unicode.h>
34
35
36 namespace JSC { namespace Yarr {
37
38 #define RegexStackSpaceForBackTrackInfoPatternCharacter 1 // Only for !fixed quantifiers.
39 #define RegexStackSpaceForBackTrackInfoCharacterClass 1 // Only for !fixed quantifiers.
40 #define RegexStackSpaceForBackTrackInfoBackReference 2
41 #define RegexStackSpaceForBackTrackInfoAlternative 1 // One per alternative.
42 #define RegexStackSpaceForBackTrackInfoParentheticalAssertion 1
43 #define RegexStackSpaceForBackTrackInfoParenthesesOnce 1 // Only for !fixed quantifiers.
44 #define RegexStackSpaceForBackTrackInfoParentheses 4
45
46 struct PatternDisjunction;
47
48 struct CharacterRange {
49     UChar begin;
50     UChar end;
51
52     CharacterRange(UChar begin, UChar end)
53         : begin(begin)
54         , end(end)
55     {
56     }
57 };
58
59 struct CharacterClassTable : RefCounted<CharacterClassTable> {
60     const char* m_table;
61     bool m_inverted;
62     static PassRefPtr<CharacterClassTable> create(const char* table, bool inverted)
63     {
64         return adoptRef(new CharacterClassTable(table, inverted));
65     }
66
67 private:
68     CharacterClassTable(const char* table, bool inverted)
69         : m_table(table)
70         , m_inverted(inverted)
71     {
72     }
73 };
74
75 struct CharacterClass : FastAllocBase {
76     // All CharacterClass instances have to have the full set of matches and ranges,
77     // they may have an optional table for faster lookups (which must match the
78     // specified matches and ranges)
79     CharacterClass(PassRefPtr<CharacterClassTable> table)
80         : m_table(table)
81     {
82     }
83     Vector<UChar> m_matches;
84     Vector<CharacterRange> m_ranges;
85     Vector<UChar> m_matchesUnicode;
86     Vector<CharacterRange> m_rangesUnicode;
87     RefPtr<CharacterClassTable> m_table;
88 };
89
90 enum QuantifierType {
91     QuantifierFixedCount,
92     QuantifierGreedy,
93     QuantifierNonGreedy,
94 };
95
96 struct PatternTerm {
97     enum Type {
98         TypeAssertionBOL,
99         TypeAssertionEOL,
100         TypeAssertionWordBoundary,
101         TypePatternCharacter,
102         TypeCharacterClass,
103         TypeBackReference,
104         TypeForwardReference,
105         TypeParenthesesSubpattern,
106         TypeParentheticalAssertion,
107     } type;
108     bool invertOrCapture;
109     union {
110         UChar patternCharacter;
111         CharacterClass* characterClass;
112         unsigned subpatternId;
113         struct {
114             PatternDisjunction* disjunction;
115             unsigned subpatternId;
116             unsigned lastSubpatternId;
117             bool isCopy;
118         } parentheses;
119     };
120     QuantifierType quantityType;
121     unsigned quantityCount;
122     int inputPosition;
123     unsigned frameLocation;
124
125     PatternTerm(UChar ch)
126         : type(PatternTerm::TypePatternCharacter)
127     {
128         patternCharacter = ch;
129         quantityType = QuantifierFixedCount;
130         quantityCount = 1;
131     }
132
133     PatternTerm(CharacterClass* charClass, bool invert)
134         : type(PatternTerm::TypeCharacterClass)
135         , invertOrCapture(invert)
136     {
137         characterClass = charClass;
138         quantityType = QuantifierFixedCount;
139         quantityCount = 1;
140     }
141
142     PatternTerm(Type type, unsigned subpatternId, PatternDisjunction* disjunction, bool invertOrCapture)
143         : type(type)
144         , invertOrCapture(invertOrCapture)
145     {
146         parentheses.disjunction = disjunction;
147         parentheses.subpatternId = subpatternId;
148         parentheses.isCopy = false;
149         quantityType = QuantifierFixedCount;
150         quantityCount = 1;
151     }
152     
153     PatternTerm(Type type, bool invert = false)
154         : type(type)
155         , invertOrCapture(invert)
156     {
157         quantityType = QuantifierFixedCount;
158         quantityCount = 1;
159     }
160
161     PatternTerm(unsigned spatternId)
162         : type(TypeBackReference)
163         , invertOrCapture(false)
164     {
165         subpatternId = spatternId;
166         quantityType = QuantifierFixedCount;
167         quantityCount = 1;
168     }
169
170     static PatternTerm ForwardReference()
171     {
172         return PatternTerm(TypeForwardReference);
173     }
174
175     static PatternTerm BOL()
176     {
177         return PatternTerm(TypeAssertionBOL);
178     }
179
180     static PatternTerm EOL()
181     {
182         return PatternTerm(TypeAssertionEOL);
183     }
184
185     static PatternTerm WordBoundary(bool invert)
186     {
187         return PatternTerm(TypeAssertionWordBoundary, invert);
188     }
189     
190     bool invert()
191     {
192         return invertOrCapture;
193     }
194
195     bool capture()
196     {
197         return invertOrCapture;
198     }
199     
200     void quantify(unsigned count, QuantifierType type)
201     {
202         quantityCount = count;
203         quantityType = type;
204     }
205 };
206
207 struct PatternAlternative : FastAllocBase {
208     PatternAlternative(PatternDisjunction* disjunction)
209         : m_parent(disjunction)
210         , m_onceThrough(false)
211         , m_hasFixedSize(false)
212         , m_startsWithBOL(false)
213         , m_containsBOL(false)
214     {
215     }
216
217     PatternTerm& lastTerm()
218     {
219         ASSERT(m_terms.size());
220         return m_terms[m_terms.size() - 1];
221     }
222     
223     void removeLastTerm()
224     {
225         ASSERT(m_terms.size());
226         m_terms.shrink(m_terms.size() - 1);
227     }
228     
229     void setOnceThrough()
230     {
231         m_onceThrough = true;
232     }
233     
234     bool onceThrough()
235     {
236         return m_onceThrough;
237     }
238
239     Vector<PatternTerm> m_terms;
240     PatternDisjunction* m_parent;
241     unsigned m_minimumSize;
242     bool m_onceThrough : 1;
243     bool m_hasFixedSize : 1;
244     bool m_startsWithBOL : 1;
245     bool m_containsBOL : 1;
246 };
247
248 struct PatternDisjunction : FastAllocBase {
249     PatternDisjunction(PatternAlternative* parent = 0)
250         : m_parent(parent)
251         , m_hasFixedSize(false)
252     {
253     }
254     
255     ~PatternDisjunction()
256     {
257         deleteAllValues(m_alternatives);
258     }
259
260     PatternAlternative* addNewAlternative()
261     {
262         PatternAlternative* alternative = new PatternAlternative(this);
263         m_alternatives.append(alternative);
264         return alternative;
265     }
266
267     Vector<PatternAlternative*> m_alternatives;
268     PatternAlternative* m_parent;
269     unsigned m_minimumSize;
270     unsigned m_callFrameSize;
271     bool m_hasFixedSize;
272 };
273
274 // You probably don't want to be calling these functions directly
275 // (please to be calling newlineCharacterClass() et al on your
276 // friendly neighborhood RegexPattern instance to get nicely
277 // cached copies).
278 CharacterClass* newlineCreate();
279 CharacterClass* digitsCreate();
280 CharacterClass* spacesCreate();
281 CharacterClass* wordcharCreate();
282 CharacterClass* nondigitsCreate();
283 CharacterClass* nonspacesCreate();
284 CharacterClass* nonwordcharCreate();
285
286 struct RegexPattern {
287     RegexPattern(bool ignoreCase, bool multiline)
288         : m_ignoreCase(ignoreCase)
289         , m_multiline(multiline)
290         , m_containsBackreferences(false)
291         , m_containsBOL(false)
292         , m_numSubpatterns(0)
293         , m_maxBackReference(0)
294         , newlineCached(0)
295         , digitsCached(0)
296         , spacesCached(0)
297         , wordcharCached(0)
298         , nondigitsCached(0)
299         , nonspacesCached(0)
300         , nonwordcharCached(0)
301     {
302     }
303
304     ~RegexPattern()
305     {
306         deleteAllValues(m_disjunctions);
307         deleteAllValues(m_userCharacterClasses);
308     }
309
310     void reset()
311     {
312         m_numSubpatterns = 0;
313         m_maxBackReference = 0;
314
315         m_containsBackreferences = false;
316         m_containsBOL = false;
317
318         newlineCached = 0;
319         digitsCached = 0;
320         spacesCached = 0;
321         wordcharCached = 0;
322         nondigitsCached = 0;
323         nonspacesCached = 0;
324         nonwordcharCached = 0;
325
326         deleteAllValues(m_disjunctions);
327         m_disjunctions.clear();
328         deleteAllValues(m_userCharacterClasses);
329         m_userCharacterClasses.clear();
330     }
331
332     bool containsIllegalBackReference()
333     {
334         return m_maxBackReference > m_numSubpatterns;
335     }
336
337     CharacterClass* newlineCharacterClass()
338     {
339         if (!newlineCached)
340             m_userCharacterClasses.append(newlineCached = newlineCreate());
341         return newlineCached;
342     }
343     CharacterClass* digitsCharacterClass()
344     {
345         if (!digitsCached)
346             m_userCharacterClasses.append(digitsCached = digitsCreate());
347         return digitsCached;
348     }
349     CharacterClass* spacesCharacterClass()
350     {
351         if (!spacesCached)
352             m_userCharacterClasses.append(spacesCached = spacesCreate());
353         return spacesCached;
354     }
355     CharacterClass* wordcharCharacterClass()
356     {
357         if (!wordcharCached)
358             m_userCharacterClasses.append(wordcharCached = wordcharCreate());
359         return wordcharCached;
360     }
361     CharacterClass* nondigitsCharacterClass()
362     {
363         if (!nondigitsCached)
364             m_userCharacterClasses.append(nondigitsCached = nondigitsCreate());
365         return nondigitsCached;
366     }
367     CharacterClass* nonspacesCharacterClass()
368     {
369         if (!nonspacesCached)
370             m_userCharacterClasses.append(nonspacesCached = nonspacesCreate());
371         return nonspacesCached;
372     }
373     CharacterClass* nonwordcharCharacterClass()
374     {
375         if (!nonwordcharCached)
376             m_userCharacterClasses.append(nonwordcharCached = nonwordcharCreate());
377         return nonwordcharCached;
378     }
379
380     bool m_ignoreCase : 1;
381     bool m_multiline : 1;
382     bool m_containsBackreferences : 1;
383     bool m_containsBOL : 1;
384     unsigned m_numSubpatterns;
385     unsigned m_maxBackReference;
386     PatternDisjunction* m_body;
387     Vector<PatternDisjunction*, 4> m_disjunctions;
388     Vector<CharacterClass*> m_userCharacterClasses;
389
390 private:
391     CharacterClass* newlineCached;
392     CharacterClass* digitsCached;
393     CharacterClass* spacesCached;
394     CharacterClass* wordcharCached;
395     CharacterClass* nondigitsCached;
396     CharacterClass* nonspacesCached;
397     CharacterClass* nonwordcharCached;
398 };
399
400 } } // namespace JSC::Yarr
401
402 #endif
403
404 #endif // RegexPattern_h