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 #include <wtf/Platform.h>
  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 CharacterClass : FastAllocBase {
  61     Vector<UChar> m_matches;
  62     Vector<CharacterRange> m_ranges;
  63     Vector<UChar> m_matchesUnicode;
  64     Vector<CharacterRange> m_rangesUnicode;
  65 };
  66
  67 enum QuantifierType {
  68     QuantifierFixedCount,
  69     QuantifierGreedy,
  70     QuantifierNonGreedy,
  71 };
  72
  73 struct PatternTerm {
  74     enum Type {
  75         TypeAssertionBOL,
  76         TypeAssertionEOL,
  77         TypeAssertionWordBoundary,
  78         TypePatternCharacter,
  79         TypeCharacterClass,
  80         TypeBackReference,
  81         TypeForwardReference,
  82         TypeParenthesesSubpattern,
  83         TypeParentheticalAssertion,
  84     } type;
  85     bool invertOrCapture;
  86     union {
  87         UChar patternCharacter;
  88         CharacterClass* characterClass;
  89         unsigned subpatternId;
  90         struct {
  91             PatternDisjunction* disjunction;
  92             unsigned subpatternId;
  93             unsigned lastSubpatternId;
  94             bool isCopy;
  95         } parentheses;
  96     };
  97     QuantifierType quantityType;
  98     unsigned quantityCount;
  99     int inputPosition;
 100     unsigned frameLocation;
 101
 102     PatternTerm(UChar ch)
 103         : type(PatternTerm::TypePatternCharacter)
 104     {
 105         patternCharacter = ch;
 106         quantityType = QuantifierFixedCount;
 107         quantityCount = 1;
 108     }
 109
 110     PatternTerm(CharacterClass* charClass, bool invert)
 111         : type(PatternTerm::TypeCharacterClass)
 112         , invertOrCapture(invert)
 113     {
 114         characterClass = charClass;
 115         quantityType = QuantifierFixedCount;
 116         quantityCount = 1;
 117     }
 118
 119     PatternTerm(Type type, unsigned subpatternId, PatternDisjunction* disjunction, bool invertOrCapture)
 120         : type(type)
 121         , invertOrCapture(invertOrCapture)
 122     {
 123         parentheses.disjunction = disjunction;
 124         parentheses.subpatternId = subpatternId;
 125         parentheses.isCopy = false;
 126         quantityType = QuantifierFixedCount;
 127         quantityCount = 1;
 128     }
 129
 130     PatternTerm(Type type, bool invert = false)
 131         : type(type)
 132         , invertOrCapture(invert)
 133     {
 134         quantityType = QuantifierFixedCount;
 135         quantityCount = 1;
 136     }
 137
 138     PatternTerm(unsigned spatternId)
 139         : type(TypeBackReference)
 140         , invertOrCapture(false)
 141     {
 142         subpatternId = spatternId;
 143         quantityType = QuantifierFixedCount;
 144         quantityCount = 1;
 145     }
 146
 147     static PatternTerm ForwardReference()
 148     {
 149         return PatternTerm(TypeForwardReference);
 150     }
 151
 152     static PatternTerm BOL()
 153     {
 154         return PatternTerm(TypeAssertionBOL);
 155     }
 156
 157     static PatternTerm EOL()
 158     {
 159         return PatternTerm(TypeAssertionEOL);
 160     }
 161
 162     static PatternTerm WordBoundary(bool invert)
 163     {
 164         return PatternTerm(TypeAssertionWordBoundary, invert);
 165     }
 166
 167     bool invert()
 168     {
 169         return invertOrCapture;
 170     }
 171
 172     bool capture()
 173     {
 174         return invertOrCapture;
 175     }
 176
 177     void quantify(unsigned count, QuantifierType type)
 178     {
 179         quantityCount = count;
 180         quantityType = type;
 181     }
 182 };
 183
 184 struct PatternAlternative : FastAllocBase {
 185     PatternAlternative(PatternDisjunction* disjunction)
 186         : m_parent(disjunction)
 187     {
 188     }
 189
 190     PatternTerm& lastTerm()
 191     {
 192         ASSERT(m_terms.size());
 193         return m_terms[m_terms.size() - 1];
 194     }
 195
 196     void removeLastTerm()
 197     {
 198         ASSERT(m_terms.size());
 199         m_terms.shrink(m_terms.size() - 1);
 200     }
 201
 202     Vector<PatternTerm> m_terms;
 203     PatternDisjunction* m_parent;
 204     unsigned m_minimumSize;
 205     bool m_hasFixedSize;
 206 };
 207
 208 struct PatternDisjunction : FastAllocBase {
 209     PatternDisjunction(PatternAlternative* parent = 0)
 210         : m_parent(parent)
 211     {
 212     }
 213
 214     ~PatternDisjunction()
 215     {
 216         deleteAllValues(m_alternatives);
 217     }
 218
 219     PatternAlternative* addNewAlternative()
 220     {
 221         PatternAlternative* alternative = new PatternAlternative(this);
 222         m_alternatives.append(alternative);
 223         return alternative;
 224     }
 225
 226     Vector<PatternAlternative*> m_alternatives;
 227     PatternAlternative* m_parent;
 228     unsigned m_minimumSize;
 229     unsigned m_callFrameSize;
 230     bool m_hasFixedSize;
 231 };
 232
 233 // You probably don't want to be calling these functions directly
 234 // (please to be calling newlineCharacterClass() et al on your
 235 // friendly neighborhood RegexPattern instance to get nicely
 236 // cached copies).
 237 CharacterClass* newlineCreate();
 238 CharacterClass* digitsCreate();
 239 CharacterClass* spacesCreate();
 240 CharacterClass* wordcharCreate();
 241 CharacterClass* nondigitsCreate();
 242 CharacterClass* nonspacesCreate();
 243 CharacterClass* nonwordcharCreate();
 244
 245 struct RegexPattern {
 246     RegexPattern(bool ignoreCase, bool multiline)
 247         : m_ignoreCase(ignoreCase)
 248         , m_multiline(multiline)
 249         , m_numSubpatterns(0)
 250         , m_maxBackReference(0)
 251         , newlineCached(0)
 252         , digitsCached(0)
 253         , spacesCached(0)
 254         , wordcharCached(0)
 255         , nondigitsCached(0)
 256         , nonspacesCached(0)
 257         , nonwordcharCached(0)
 258     {
 259     }
 260
 261     ~RegexPattern()
 262     {
 263         deleteAllValues(m_disjunctions);
 264         deleteAllValues(m_userCharacterClasses);
 265     }
 266
 267     void reset()
 268     {
 269         m_numSubpatterns = 0;
 270         m_maxBackReference = 0;
 271
 272         newlineCached = 0;
 273         digitsCached = 0;
 274         spacesCached = 0;
 275         wordcharCached = 0;
 276         nondigitsCached = 0;
 277         nonspacesCached = 0;
 278         nonwordcharCached = 0;
 279
 280         deleteAllValues(m_disjunctions);
 281         m_disjunctions.clear();
 282         deleteAllValues(m_userCharacterClasses);
 283         m_userCharacterClasses.clear();
 284     }
 285
 286     bool containsIllegalBackReference()
 287     {
 288         return m_maxBackReference > m_numSubpatterns;
 289     }
 290
 291     CharacterClass* newlineCharacterClass()
 292     {
 293         if (!newlineCached)
 294             m_userCharacterClasses.append(newlineCached = newlineCreate());
 295         return newlineCached;
 296     }
 297     CharacterClass* digitsCharacterClass()
 298     {
 299         if (!digitsCached)
 300             m_userCharacterClasses.append(digitsCached = digitsCreate());
 301         return digitsCached;
 302     }
 303     CharacterClass* spacesCharacterClass()
 304     {
 305         if (!spacesCached)
 306             m_userCharacterClasses.append(spacesCached = spacesCreate());
 307         return spacesCached;
 308     }
 309     CharacterClass* wordcharCharacterClass()
 310     {
 311         if (!wordcharCached)
 312             m_userCharacterClasses.append(wordcharCached = wordcharCreate());
 313         return wordcharCached;
 314     }
 315     CharacterClass* nondigitsCharacterClass()
 316     {
 317         if (!nondigitsCached)
 318             m_userCharacterClasses.append(nondigitsCached = nondigitsCreate());
 319         return nondigitsCached;
 320     }
 321     CharacterClass* nonspacesCharacterClass()
 322     {
 323         if (!nonspacesCached)
 324             m_userCharacterClasses.append(nonspacesCached = nonspacesCreate());
 325         return nonspacesCached;
 326     }
 327     CharacterClass* nonwordcharCharacterClass()
 328     {
 329         if (!nonwordcharCached)
 330             m_userCharacterClasses.append(nonwordcharCached = nonwordcharCreate());
 331         return nonwordcharCached;
 332     }
 333
 334     bool m_ignoreCase;
 335     bool m_multiline;
 336     unsigned m_numSubpatterns;
 337     unsigned m_maxBackReference;
 338     PatternDisjunction* m_body;
 339     Vector<PatternDisjunction*, 4> m_disjunctions;
 340     Vector<CharacterClass*> m_userCharacterClasses;
 341
 342 private:
 343     CharacterClass* newlineCached;
 344     CharacterClass* digitsCached;
 345     CharacterClass* spacesCached;
 346     CharacterClass* wordcharCached;
 347     CharacterClass* nondigitsCached;
 348     CharacterClass* nonspacesCached;
 349     CharacterClass* nonwordcharCached;
 350 };
 351
 352 } } // namespace JSC::Yarr
 353
 354 #endif
 355
 356 #endif // RegexPattern_h