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     {
 211     }
 212
 213     PatternTerm& lastTerm()
 214     {
 215         ASSERT(m_terms.size());
 216         return m_terms[m_terms.size() - 1];
 217     }
 218
 219     void removeLastTerm()
 220     {
 221         ASSERT(m_terms.size());
 222         m_terms.shrink(m_terms.size() - 1);
 223     }
 224
 225     Vector<PatternTerm> m_terms;
 226     PatternDisjunction* m_parent;
 227     unsigned m_minimumSize;
 228     bool m_hasFixedSize;
 229 };
 230
 231 struct PatternDisjunction : FastAllocBase {
 232     PatternDisjunction(PatternAlternative* parent = 0)
 233         : m_parent(parent)
 234     {
 235     }
 236
 237     ~PatternDisjunction()
 238     {
 239         deleteAllValues(m_alternatives);
 240     }
 241
 242     PatternAlternative* addNewAlternative()
 243     {
 244         PatternAlternative* alternative = new PatternAlternative(this);
 245         m_alternatives.append(alternative);
 246         return alternative;
 247     }
 248
 249     Vector<PatternAlternative*> m_alternatives;
 250     PatternAlternative* m_parent;
 251     unsigned m_minimumSize;
 252     unsigned m_callFrameSize;
 253     bool m_hasFixedSize;
 254 };
 255
 256 // You probably don't want to be calling these functions directly
 257 // (please to be calling newlineCharacterClass() et al on your
 258 // friendly neighborhood RegexPattern instance to get nicely
 259 // cached copies).
 260 CharacterClass* newlineCreate();
 261 CharacterClass* digitsCreate();
 262 CharacterClass* spacesCreate();
 263 CharacterClass* wordcharCreate();
 264 CharacterClass* nondigitsCreate();
 265 CharacterClass* nonspacesCreate();
 266 CharacterClass* nonwordcharCreate();
 267
 268 struct RegexPattern {
 269     RegexPattern(bool ignoreCase, bool multiline)
 270         : m_ignoreCase(ignoreCase)
 271         , m_multiline(multiline)
 272         , m_numSubpatterns(0)
 273         , m_maxBackReference(0)
 274         , m_shouldFallBack(false)
 275         , newlineCached(0)
 276         , digitsCached(0)
 277         , spacesCached(0)
 278         , wordcharCached(0)
 279         , nondigitsCached(0)
 280         , nonspacesCached(0)
 281         , nonwordcharCached(0)
 282     {
 283     }
 284
 285     ~RegexPattern()
 286     {
 287         deleteAllValues(m_disjunctions);
 288         deleteAllValues(m_userCharacterClasses);
 289     }
 290
 291     void reset()
 292     {
 293         m_numSubpatterns = 0;
 294         m_maxBackReference = 0;
 295
 296         m_shouldFallBack = false;
 297
 298         newlineCached = 0;
 299         digitsCached = 0;
 300         spacesCached = 0;
 301         wordcharCached = 0;
 302         nondigitsCached = 0;
 303         nonspacesCached = 0;
 304         nonwordcharCached = 0;
 305
 306         deleteAllValues(m_disjunctions);
 307         m_disjunctions.clear();
 308         deleteAllValues(m_userCharacterClasses);
 309         m_userCharacterClasses.clear();
 310     }
 311
 312     bool containsIllegalBackReference()
 313     {
 314         return m_maxBackReference > m_numSubpatterns;
 315     }
 316
 317     CharacterClass* newlineCharacterClass()
 318     {
 319         if (!newlineCached)
 320             m_userCharacterClasses.append(newlineCached = newlineCreate());
 321         return newlineCached;
 322     }
 323     CharacterClass* digitsCharacterClass()
 324     {
 325         if (!digitsCached)
 326             m_userCharacterClasses.append(digitsCached = digitsCreate());
 327         return digitsCached;
 328     }
 329     CharacterClass* spacesCharacterClass()
 330     {
 331         if (!spacesCached)
 332             m_userCharacterClasses.append(spacesCached = spacesCreate());
 333         return spacesCached;
 334     }
 335     CharacterClass* wordcharCharacterClass()
 336     {
 337         if (!wordcharCached)
 338             m_userCharacterClasses.append(wordcharCached = wordcharCreate());
 339         return wordcharCached;
 340     }
 341     CharacterClass* nondigitsCharacterClass()
 342     {
 343         if (!nondigitsCached)
 344             m_userCharacterClasses.append(nondigitsCached = nondigitsCreate());
 345         return nondigitsCached;
 346     }
 347     CharacterClass* nonspacesCharacterClass()
 348     {
 349         if (!nonspacesCached)
 350             m_userCharacterClasses.append(nonspacesCached = nonspacesCreate());
 351         return nonspacesCached;
 352     }
 353     CharacterClass* nonwordcharCharacterClass()
 354     {
 355         if (!nonwordcharCached)
 356             m_userCharacterClasses.append(nonwordcharCached = nonwordcharCreate());
 357         return nonwordcharCached;
 358     }
 359
 360     bool m_ignoreCase;
 361     bool m_multiline;
 362     unsigned m_numSubpatterns;
 363     unsigned m_maxBackReference;
 364     bool m_shouldFallBack;
 365     PatternDisjunction* m_body;
 366     Vector<PatternDisjunction*, 4> m_disjunctions;
 367     Vector<CharacterClass*> m_userCharacterClasses;
 368
 369 private:
 370     CharacterClass* newlineCached;
 371     CharacterClass* digitsCached;
 372     CharacterClass* spacesCached;
 373     CharacterClass* wordcharCached;
 374     CharacterClass* nondigitsCached;
 375     CharacterClass* nonspacesCached;
 376     CharacterClass* nonwordcharCached;
 377 };
 378
 379 } } // namespace JSC::Yarr
 380
 381 #endif
 382
 383 #endif // RegexPattern_h