Home | History | Annotate | Download | only in wrec 
      1 /*
      2  * Copyright (C) 2008 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 #include "config.h"
     27 #include "WRECParser.h"
     28 
     29 #if ENABLE(WREC)
     30 
     31 #include "CharacterClassConstructor.h"
     32 #include "WRECFunctors.h"
     33 
     34 using namespace WTF;
     35 
     36 namespace JSC { namespace WREC {
     37 
     38 // These error messages match the error messages used by PCRE.
     39 const char* Parser::QuantifierOutOfOrder = "numbers out of order in {} quantifier";
     40 const char* Parser::QuantifierWithoutAtom = "nothing to repeat";
     41 const char* Parser::ParenthesesUnmatched = "unmatched parentheses";
     42 const char* Parser::ParenthesesTypeInvalid = "unrecognized character after (?";
     43 const char* Parser::ParenthesesNotSupported = ""; // Not a user-visible syntax error -- just signals a syntax that WREC doesn't support yet.
     44 const char* Parser::CharacterClassUnmatched = "missing terminating ] for character class";
     45 const char* Parser::CharacterClassOutOfOrder = "range out of order in character class";
     46 const char* Parser::EscapeUnterminated = "\\ at end of pattern";
     47 
     48 class PatternCharacterSequence {
     49 typedef Generator::JumpList JumpList;
     50 
     51 public:
     52     PatternCharacterSequence(Generator& generator, JumpList& failures)
     53         : m_generator(generator)
     54         , m_failures(failures)
     55     {
     56     }
     57 
     58     size_t size() { return m_sequence.size(); }
     59 
     60     void append(int ch)
     61     {
     62         m_sequence.append(ch);
     63     }
     64 
     65     void flush()
     66     {
     67         if (!m_sequence.size())
     68             return;
     69 
     70         m_generator.generatePatternCharacterSequence(m_failures, m_sequence.begin(), m_sequence.size());
     71         m_sequence.clear();
     72     }
     73 
     74     void flush(const Quantifier& quantifier)
     75     {
     76         if (!m_sequence.size())
     77             return;
     78 
     79         m_generator.generatePatternCharacterSequence(m_failures, m_sequence.begin(), m_sequence.size() - 1);
     80 
     81         switch (quantifier.type) {
     82         case Quantifier::None:
     83         case Quantifier::Error:
     84             ASSERT_NOT_REACHED();
     85             break;
     86 
     87         case Quantifier::Greedy: {
     88             GeneratePatternCharacterFunctor functor(m_sequence.last());
     89             m_generator.generateGreedyQuantifier(m_failures, functor, quantifier.min, quantifier.max);
     90             break;
     91         }
     92 
     93         case Quantifier::NonGreedy: {
     94             GeneratePatternCharacterFunctor functor(m_sequence.last());
     95             m_generator.generateNonGreedyQuantifier(m_failures, functor, quantifier.min, quantifier.max);
     96             break;
     97         }
     98         }
     99 
    100         m_sequence.clear();
    101     }
    102 
    103 private:
    104     Generator& m_generator;
    105     JumpList& m_failures;
    106     Vector<int, 8> m_sequence;
    107 };
    108 
    109 ALWAYS_INLINE Quantifier Parser::consumeGreedyQuantifier()
    110 {
    111     switch (peek()) {
    112         case '?':
    113             consume();
    114             return Quantifier(Quantifier::Greedy, 0, 1);
    115 
    116         case '*':
    117             consume();
    118             return Quantifier(Quantifier::Greedy, 0);
    119 
    120         case '+':
    121             consume();
    122             return Quantifier(Quantifier::Greedy, 1);
    123 
    124         case '{': {
    125             SavedState state(*this);
    126             consume();
    127 
    128             // Accept: {n}, {n,}, {n,m}.
    129             // Reject: {n,m} where n > m.
    130             // Ignore: Anything else, such as {n, m}.
    131 
    132             if (!peekIsDigit()) {
    133                 state.restore();
    134                 return Quantifier();
    135             }
    136 
    137             unsigned min = consumeNumber();
    138             unsigned max = min;
    139 
    140             if (peek() == ',') {
    141                 consume();
    142                 max = peekIsDigit() ? consumeNumber() : Quantifier::Infinity;
    143             }
    144 
    145             if (peek() != '}') {
    146                 state.restore();
    147                 return Quantifier();
    148             }
    149             consume();
    150 
    151             if (min > max) {
    152                 setError(QuantifierOutOfOrder);
    153                 return Quantifier(Quantifier::Error);
    154             }
    155 
    156             return Quantifier(Quantifier::Greedy, min, max);
    157          }
    158 
    159          default:
    160             return Quantifier(); // No quantifier.
    161     }
    162 }
    163 
    164 Quantifier Parser::consumeQuantifier()
    165 {
    166     Quantifier q = consumeGreedyQuantifier();
    167 
    168     if ((q.type == Quantifier::Greedy) && (peek() == '?')) {
    169         consume();
    170         q.type = Quantifier::NonGreedy;
    171     }
    172 
    173     return q;
    174 }
    175 
    176 bool Parser::parseCharacterClassQuantifier(JumpList& failures, const CharacterClass& charClass, bool invert)
    177 {
    178     Quantifier q = consumeQuantifier();
    179 
    180     switch (q.type) {
    181     case Quantifier::None: {
    182         m_generator.generateCharacterClass(failures, charClass, invert);
    183         break;
    184     }
    185 
    186     case Quantifier::Greedy: {
    187         GenerateCharacterClassFunctor functor(&charClass, invert);
    188         m_generator.generateGreedyQuantifier(failures, functor, q.min, q.max);
    189         break;
    190     }
    191 
    192     case Quantifier::NonGreedy: {
    193         GenerateCharacterClassFunctor functor(&charClass, invert);
    194         m_generator.generateNonGreedyQuantifier(failures, functor, q.min, q.max);
    195         break;
    196     }
    197 
    198     case Quantifier::Error:
    199         return false;
    200     }
    201 
    202     return true;
    203 }
    204 
    205 bool Parser::parseBackreferenceQuantifier(JumpList& failures, unsigned subpatternId)
    206 {
    207     Quantifier q = consumeQuantifier();
    208 
    209     switch (q.type) {
    210     case Quantifier::None: {
    211         m_generator.generateBackreference(failures, subpatternId);
    212         break;
    213     }
    214 
    215     case Quantifier::Greedy:
    216     case Quantifier::NonGreedy:
    217         m_generator.generateBackreferenceQuantifier(failures, q.type, subpatternId, q.min, q.max);
    218         return true;
    219 
    220     case Quantifier::Error:
    221         return false;
    222     }
    223 
    224     return true;
    225 }
    226 
    227 bool Parser::parseParentheses(JumpList& failures)
    228 {
    229     ParenthesesType type = consumeParenthesesType();
    230 
    231     // FIXME: WREC originally failed to backtrack correctly in cases such as
    232     // "c".match(/(.*)c/). Now, most parentheses handling is disabled. For
    233     // unsupported parentheses, we fall back on PCRE.
    234 
    235     switch (type) {
    236         case Generator::Assertion: {
    237             m_generator.generateParenthesesAssertion(failures);
    238 
    239             if (consume() != ')') {
    240                 setError(ParenthesesUnmatched);
    241                 return false;
    242             }
    243 
    244             Quantifier quantifier = consumeQuantifier();
    245             if (quantifier.type != Quantifier::None && quantifier.min == 0) {
    246                 setError(ParenthesesNotSupported);
    247                 return false;
    248             }
    249 
    250             return true;
    251         }
    252         case Generator::InvertedAssertion: {
    253             m_generator.generateParenthesesInvertedAssertion(failures);
    254 
    255             if (consume() != ')') {
    256                 setError(ParenthesesUnmatched);
    257                 return false;
    258             }
    259 
    260             Quantifier quantifier = consumeQuantifier();
    261             if (quantifier.type != Quantifier::None && quantifier.min == 0) {
    262                 setError(ParenthesesNotSupported);
    263                 return false;
    264             }
    265 
    266             return true;
    267         }
    268         default:
    269             setError(ParenthesesNotSupported);
    270             return false;
    271     }
    272 }
    273 
    274 bool Parser::parseCharacterClass(JumpList& failures)
    275 {
    276     bool invert = false;
    277     if (peek() == '^') {
    278         consume();
    279         invert = true;
    280     }
    281 
    282     CharacterClassConstructor constructor(m_ignoreCase);
    283 
    284     int ch;
    285     while ((ch = peek()) != ']') {
    286         switch (ch) {
    287         case EndOfPattern:
    288             setError(CharacterClassUnmatched);
    289             return false;
    290 
    291         case '\\': {
    292             consume();
    293             Escape escape = consumeEscape(true);
    294 
    295             switch (escape.type()) {
    296                 case Escape::PatternCharacter: {
    297                     int character = PatternCharacterEscape::cast(escape).character();
    298                     if (character == '-')
    299                         constructor.flushBeforeEscapedHyphen();
    300                     constructor.put(character);
    301                     break;
    302                 }
    303                 case Escape::CharacterClass: {
    304                     const CharacterClassEscape& characterClassEscape = CharacterClassEscape::cast(escape);
    305                     ASSERT(!characterClassEscape.invert());
    306                     constructor.append(characterClassEscape.characterClass());
    307                     break;
    308                 }
    309                 case Escape::Error:
    310                     return false;
    311                 case Escape::Backreference:
    312                 case Escape::WordBoundaryAssertion: {
    313                     ASSERT_NOT_REACHED();
    314                     break;
    315                 }
    316             }
    317             break;
    318         }
    319 
    320         default:
    321             consume();
    322             constructor.put(ch);
    323         }
    324     }
    325     consume();
    326 
    327     // lazily catch reversed ranges ([z-a])in character classes
    328     if (constructor.isUpsideDown()) {
    329         setError(CharacterClassOutOfOrder);
    330         return false;
    331     }
    332 
    333     constructor.flush();
    334     CharacterClass charClass = constructor.charClass();
    335     return parseCharacterClassQuantifier(failures, charClass, invert);
    336 }
    337 
    338 bool Parser::parseNonCharacterEscape(JumpList& failures, const Escape& escape)
    339 {
    340     switch (escape.type()) {
    341         case Escape::PatternCharacter:
    342             ASSERT_NOT_REACHED();
    343             return false;
    344 
    345         case Escape::CharacterClass:
    346             return parseCharacterClassQuantifier(failures, CharacterClassEscape::cast(escape).characterClass(), CharacterClassEscape::cast(escape).invert());
    347 
    348         case Escape::Backreference:
    349             return parseBackreferenceQuantifier(failures, BackreferenceEscape::cast(escape).subpatternId());
    350 
    351         case Escape::WordBoundaryAssertion:
    352             m_generator.generateAssertionWordBoundary(failures, WordBoundaryAssertionEscape::cast(escape).invert());
    353             return true;
    354 
    355         case Escape::Error:
    356             return false;
    357     }
    358 
    359     ASSERT_NOT_REACHED();
    360     return false;
    361 }
    362 
    363 Escape Parser::consumeEscape(bool inCharacterClass)
    364 {
    365     switch (peek()) {
    366     case EndOfPattern:
    367         setError(EscapeUnterminated);
    368         return Escape(Escape::Error);
    369 
    370     // Assertions
    371     case 'b':
    372         consume();
    373         if (inCharacterClass)
    374             return PatternCharacterEscape('\b');
    375         return WordBoundaryAssertionEscape(false); // do not invert
    376     case 'B':
    377         consume();
    378         if (inCharacterClass)
    379             return PatternCharacterEscape('B');
    380         return WordBoundaryAssertionEscape(true); // invert
    381 
    382     // CharacterClassEscape
    383     case 'd':
    384         consume();
    385         return CharacterClassEscape(CharacterClass::digits(), false);
    386     case 's':
    387         consume();
    388         return CharacterClassEscape(CharacterClass::spaces(), false);
    389     case 'w':
    390         consume();
    391         return CharacterClassEscape(CharacterClass::wordchar(), false);
    392     case 'D':
    393         consume();
    394         return inCharacterClass
    395             ? CharacterClassEscape(CharacterClass::nondigits(), false)
    396             : CharacterClassEscape(CharacterClass::digits(), true);
    397     case 'S':
    398         consume();
    399         return inCharacterClass
    400             ? CharacterClassEscape(CharacterClass::nonspaces(), false)
    401             : CharacterClassEscape(CharacterClass::spaces(), true);
    402     case 'W':
    403         consume();
    404         return inCharacterClass
    405             ? CharacterClassEscape(CharacterClass::nonwordchar(), false)
    406             : CharacterClassEscape(CharacterClass::wordchar(), true);
    407 
    408     // DecimalEscape
    409     case '1':
    410     case '2':
    411     case '3':
    412     case '4':
    413     case '5':
    414     case '6':
    415     case '7':
    416     case '8':
    417     case '9': {
    418         if (peekDigit() > m_numSubpatterns || inCharacterClass) {
    419             // To match Firefox, we parse an invalid backreference in the range [1-7]
    420             // as an octal escape.
    421             return peekDigit() > 7 ? PatternCharacterEscape('\\') : PatternCharacterEscape(consumeOctal());
    422         }
    423 
    424         int value = 0;
    425         do {
    426             unsigned newValue = value * 10 + peekDigit();
    427             if (newValue > m_numSubpatterns)
    428                 break;
    429             value = newValue;
    430             consume();
    431         } while (peekIsDigit());
    432 
    433         return BackreferenceEscape(value);
    434     }
    435 
    436     // Octal escape
    437     case '0':
    438         consume();
    439         return PatternCharacterEscape(consumeOctal());
    440 
    441     // ControlEscape
    442     case 'f':
    443         consume();
    444         return PatternCharacterEscape('\f');
    445     case 'n':
    446         consume();
    447         return PatternCharacterEscape('\n');
    448     case 'r':
    449         consume();
    450         return PatternCharacterEscape('\r');
    451     case 't':
    452         consume();
    453         return PatternCharacterEscape('\t');
    454     case 'v':
    455         consume();
    456         return PatternCharacterEscape('\v');
    457 
    458     // ControlLetter
    459     case 'c': {
    460         SavedState state(*this);
    461         consume();
    462 
    463         int control = consume();
    464         // To match Firefox, inside a character class, we also accept numbers
    465         // and '_' as control characters.
    466         if ((!inCharacterClass && !isASCIIAlpha(control)) || (!isASCIIAlphanumeric(control) && control != '_')) {
    467             state.restore();
    468             return PatternCharacterEscape('\\');
    469         }
    470         return PatternCharacterEscape(control & 31);
    471     }
    472 
    473     // HexEscape
    474     case 'x': {
    475         consume();
    476 
    477         SavedState state(*this);
    478         int x = consumeHex(2);
    479         if (x == -1) {
    480             state.restore();
    481             return PatternCharacterEscape('x');
    482         }
    483         return PatternCharacterEscape(x);
    484     }
    485 
    486     // UnicodeEscape
    487     case 'u': {
    488         consume();
    489 
    490         SavedState state(*this);
    491         int x = consumeHex(4);
    492         if (x == -1) {
    493             state.restore();
    494             return PatternCharacterEscape('u');
    495         }
    496         return PatternCharacterEscape(x);
    497     }
    498 
    499     // IdentityEscape
    500     default:
    501         return PatternCharacterEscape(consume());
    502     }
    503 }
    504 
    505 void Parser::parseAlternative(JumpList& failures)
    506 {
    507     PatternCharacterSequence sequence(m_generator, failures);
    508 
    509     while (1) {
    510         switch (peek()) {
    511         case EndOfPattern:
    512         case '|':
    513         case ')':
    514             sequence.flush();
    515             return;
    516 
    517         case '*':
    518         case '+':
    519         case '?':
    520         case '{': {
    521             Quantifier q = consumeQuantifier();
    522 
    523             if (q.type == Quantifier::None) {
    524                 sequence.append(consume());
    525                 continue;
    526             }
    527 
    528             if (q.type == Quantifier::Error)
    529                 return;
    530 
    531             if (!sequence.size()) {
    532                 setError(QuantifierWithoutAtom);
    533                 return;
    534             }
    535 
    536             sequence.flush(q);
    537             continue;
    538         }
    539 
    540         case '^':
    541             consume();
    542 
    543             sequence.flush();
    544             m_generator.generateAssertionBOL(failures);
    545             continue;
    546 
    547         case '$':
    548             consume();
    549 
    550             sequence.flush();
    551             m_generator.generateAssertionEOL(failures);
    552             continue;
    553 
    554         case '.':
    555             consume();
    556 
    557             sequence.flush();
    558             if (!parseCharacterClassQuantifier(failures, CharacterClass::newline(), true))
    559                 return;
    560             continue;
    561 
    562         case '[':
    563             consume();
    564 
    565             sequence.flush();
    566             if (!parseCharacterClass(failures))
    567                 return;
    568             continue;
    569 
    570         case '(':
    571             consume();
    572 
    573             sequence.flush();
    574             if (!parseParentheses(failures))
    575                 return;
    576             continue;
    577 
    578         case '\\': {
    579             consume();
    580 
    581             Escape escape = consumeEscape(false);
    582             if (escape.type() == Escape::PatternCharacter) {
    583                 sequence.append(PatternCharacterEscape::cast(escape).character());
    584                 continue;
    585             }
    586 
    587             sequence.flush();
    588             if (!parseNonCharacterEscape(failures, escape))
    589                 return;
    590             continue;
    591         }
    592 
    593         default:
    594             sequence.append(consume());
    595             continue;
    596         }
    597     }
    598 }
    599 
    600 /*
    601   TOS holds index.
    602 */
    603 void Parser::parseDisjunction(JumpList& failures)
    604 {
    605     parseAlternative(failures);
    606     if (peek() != '|')
    607         return;
    608 
    609     JumpList successes;
    610     do {
    611         consume();
    612         m_generator.terminateAlternative(successes, failures);
    613         parseAlternative(failures);
    614     } while (peek() == '|');
    615 
    616     m_generator.terminateDisjunction(successes);
    617 }
    618 
    619 Generator::ParenthesesType Parser::consumeParenthesesType()
    620 {
    621     if (peek() != '?')
    622         return Generator::Capturing;
    623     consume();
    624 
    625     switch (consume()) {
    626     case ':':
    627         return Generator::NonCapturing;
    628 
    629     case '=':
    630         return Generator::Assertion;
    631 
    632     case '!':
    633         return Generator::InvertedAssertion;
    634 
    635     default:
    636         setError(ParenthesesTypeInvalid);
    637         return Generator::Error;
    638     }
    639 }
    640 
    641 } } // namespace JSC::WREC
    642 
    643 #endif // ENABLE(WREC)
    644