Source/JavaScriptCore/yarr/YarrPattern.cpp

   1 /*
   2  * Copyright (C) 2009, 2013-2016 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 #include "config.h"
  28 #include "YarrPattern.h"
  29
  30 #include "Yarr.h"
  31 #include "YarrCanonicalizeUnicode.h"
  32 #include "YarrParser.h"
  33 #include <wtf/Vector.h>
  34
  35 using namespace WTF;
  36
  37 namespace JSC { namespace Yarr {
  38
  39 #include "RegExpJitTables.h"
  40
  41 class CharacterClassConstructor {
  42 public:
  43     CharacterClassConstructor(bool isCaseInsensitive, CanonicalMode canonicalMode)
  44         : m_isCaseInsensitive(isCaseInsensitive)
  45         , m_canonicalMode(canonicalMode)
  46     {
  47     }
  48
  49     void reset()
  50     {
  51         m_matches.clear();
  52         m_ranges.clear();
  53         m_matchesUnicode.clear();
  54         m_rangesUnicode.clear();
  55     }
  56
  57     void append(const CharacterClass* other)
  58     {
  59         for (size_t i = 0; i < other->m_matches.size(); ++i)
  60             addSorted(m_matches, other->m_matches[i]);
  61         for (size_t i = 0; i < other->m_ranges.size(); ++i)
  62             addSortedRange(m_ranges, other->m_ranges[i].begin, other->m_ranges[i].end);
  63         for (size_t i = 0; i < other->m_matchesUnicode.size(); ++i)
  64             addSorted(m_matchesUnicode, other->m_matchesUnicode[i]);
  65         for (size_t i = 0; i < other->m_rangesUnicode.size(); ++i)
  66             addSortedRange(m_rangesUnicode, other->m_rangesUnicode[i].begin, other->m_rangesUnicode[i].end);
  67     }
  68
  69     void putChar(UChar32 ch)
  70     {
  71         // Handle ascii cases.
  72         if (isASCII(ch)) {
  73             if (m_isCaseInsensitive && isASCIIAlpha(ch)) {
  74                 addSorted(m_matches, toASCIIUpper(ch));
  75                 addSorted(m_matches, toASCIILower(ch));
  76             } else
  77                 addSorted(m_matches, ch);
  78             return;
  79         }
  80
  81         // Simple case, not a case-insensitive match.
  82         if (!m_isCaseInsensitive) {
  83             addSorted(m_matchesUnicode, ch);
  84             return;
  85         }
  86
  87         // Add multiple matches, if necessary.
  88         const CanonicalizationRange* info = canonicalRangeInfoFor(ch, m_canonicalMode);
  89         if (info->type == CanonicalizeUnique)
  90             addSorted(m_matchesUnicode, ch);
  91         else
  92             putUnicodeIgnoreCase(ch, info);
  93     }
  94
  95     void putUnicodeIgnoreCase(UChar32 ch, const CanonicalizationRange* info)
  96     {
  97         ASSERT(m_isCaseInsensitive);
  98         ASSERT(ch >= info->begin && ch <= info->end);
  99         ASSERT(info->type != CanonicalizeUnique);
 100         if (info->type == CanonicalizeSet) {
 101             for (const UChar32* set = canonicalCharacterSetInfo(info->value, m_canonicalMode); (ch = *set); ++set)
 102                 addSorted(ch);
 103         } else {
 104             addSorted(ch);
 105             addSorted(getCanonicalPair(info, ch));
 106         }
 107     }
 108
 109     void putRange(UChar32 lo, UChar32 hi)
 110     {
 111         if (isASCII(lo)) {
 112             char asciiLo = lo;
 113             char asciiHi = std::min(hi, (UChar32)0x7f);
 114             addSortedRange(m_ranges, lo, asciiHi);
 115
 116             if (m_isCaseInsensitive) {
 117                 if ((asciiLo <= 'Z') && (asciiHi >= 'A'))
 118                     addSortedRange(m_ranges, std::max(asciiLo, 'A')+('a'-'A'), std::min(asciiHi, 'Z')+('a'-'A'));
 119                 if ((asciiLo <= 'z') && (asciiHi >= 'a'))
 120                     addSortedRange(m_ranges, std::max(asciiLo, 'a')+('A'-'a'), std::min(asciiHi, 'z')+('A'-'a'));
 121             }
 122         }
 123         if (isASCII(hi))
 124             return;
 125
 126         lo = std::max(lo, (UChar32)0x80);
 127         addSortedRange(m_rangesUnicode, lo, hi);
 128
 129         if (!m_isCaseInsensitive)
 130             return;
 131
 132         const CanonicalizationRange* info = canonicalRangeInfoFor(lo, m_canonicalMode);
 133         while (true) {
 134             // Handle the range [lo .. end]
 135             UChar32 end = std::min<UChar32>(info->end, hi);
 136
 137             switch (info->type) {
 138             case CanonicalizeUnique:
 139                 // Nothing to do - no canonical equivalents.
 140                 break;
 141             case CanonicalizeSet: {
 142                 UChar ch;
 143                 for (const UChar32* set = canonicalCharacterSetInfo(info->value, m_canonicalMode); (ch = *set); ++set)
 144                     addSorted(m_matchesUnicode, ch);
 145                 break;
 146             }
 147             case CanonicalizeRangeLo:
 148                 addSortedRange(m_rangesUnicode, lo + info->value, end + info->value);
 149                 break;
 150             case CanonicalizeRangeHi:
 151                 addSortedRange(m_rangesUnicode, lo - info->value, end - info->value);
 152                 break;
 153             case CanonicalizeAlternatingAligned:
 154                 // Use addSortedRange since there is likely an abutting range to combine with.
 155                 if (lo & 1)
 156                     addSortedRange(m_rangesUnicode, lo - 1, lo - 1);
 157                 if (!(end & 1))
 158                     addSortedRange(m_rangesUnicode, end + 1, end + 1);
 159                 break;
 160             case CanonicalizeAlternatingUnaligned:
 161                 // Use addSortedRange since there is likely an abutting range to combine with.
 162                 if (!(lo & 1))
 163                     addSortedRange(m_rangesUnicode, lo - 1, lo - 1);
 164                 if (end & 1)
 165                     addSortedRange(m_rangesUnicode, end + 1, end + 1);
 166                 break;
 167             }
 168
 169             if (hi == end)
 170                 return;
 171
 172             ++info;
 173             lo = info->begin;
 174         };
 175
 176     }
 177
 178     std::unique_ptr<CharacterClass> charClass()
 179     {
 180         auto characterClass = std::make_unique<CharacterClass>();
 181
 182         characterClass->m_matches.swap(m_matches);
 183         characterClass->m_ranges.swap(m_ranges);
 184         characterClass->m_matchesUnicode.swap(m_matchesUnicode);
 185         characterClass->m_rangesUnicode.swap(m_rangesUnicode);
 186
 187         return characterClass;
 188     }
 189
 190 private:
 191     void addSorted(UChar32 ch)
 192     {
 193         addSorted(isASCII(ch) ? m_matches : m_matchesUnicode, ch);
 194     }
 195
 196     void addSorted(Vector<UChar32>& matches, UChar32 ch)
 197     {
 198         unsigned pos = 0;
 199         unsigned range = matches.size();
 200
 201         // binary chop, find position to insert char.
 202         while (range) {
 203             unsigned index = range >> 1;
 204
 205             int val = matches[pos+index] - ch;
 206             if (!val)
 207                 return;
 208             else if (val > 0)
 209                 range = index;
 210             else {
 211                 pos += (index+1);
 212                 range -= (index+1);
 213             }
 214         }
 215
 216         if (pos == matches.size())
 217             matches.append(ch);
 218         else
 219             matches.insert(pos, ch);
 220     }
 221
 222     void addSortedRange(Vector<CharacterRange>& ranges, UChar32 lo, UChar32 hi)
 223     {
 224         unsigned end = ranges.size();
 225
 226         // Simple linear scan - I doubt there are that many ranges anyway...
 227         // feel free to fix this with something faster (eg binary chop).
 228         for (unsigned i = 0; i < end; ++i) {
 229             // does the new range fall before the current position in the array
 230             if (hi < ranges[i].begin) {
 231                 // optional optimization: concatenate appending ranges? - may not be worthwhile.
 232                 if (hi == (ranges[i].begin - 1)) {
 233                     ranges[i].begin = lo;
 234                     return;
 235                 }
 236                 ranges.insert(i, CharacterRange(lo, hi));
 237                 return;
 238             }
 239             // Okay, since we didn't hit the last case, the end of the new range is definitely at or after the begining
 240             // If the new range start at or before the end of the last range, then the overlap (if it starts one after the
 241             // end of the last range they concatenate, which is just as good.
 242             if (lo <= (ranges[i].end + 1)) {
 243                 // found an intersect! we'll replace this entry in the array.
 244                 ranges[i].begin = std::min(ranges[i].begin, lo);
 245                 ranges[i].end = std::max(ranges[i].end, hi);
 246
 247                 // now check if the new range can subsume any subsequent ranges.
 248                 unsigned next = i+1;
 249                 // each iteration of the loop we will either remove something from the list, or break the loop.
 250                 while (next < ranges.size()) {
 251                     if (ranges[next].begin <= (ranges[i].end + 1)) {
 252                         // the next entry now overlaps / concatenates this one.
 253                         ranges[i].end = std::max(ranges[i].end, ranges[next].end);
 254                         ranges.remove(next);
 255                     } else
 256                         break;
 257                 }
 258
 259                 return;
 260             }
 261         }
 262
 263         // CharacterRange comes after all existing ranges.
 264         ranges.append(CharacterRange(lo, hi));
 265     }
 266
 267     bool m_isCaseInsensitive;
 268     CanonicalMode m_canonicalMode;
 269
 270     Vector<UChar32> m_matches;
 271     Vector<CharacterRange> m_ranges;
 272     Vector<UChar32> m_matchesUnicode;
 273     Vector<CharacterRange> m_rangesUnicode;
 274 };
 275
 276 class YarrPatternConstructor {
 277 public:
 278     YarrPatternConstructor(YarrPattern& pattern)
 279         : m_pattern(pattern)
 280         , m_characterClassConstructor(pattern.m_ignoreCase, pattern.m_unicode ? CanonicalMode::Unicode : CanonicalMode::UCS2)
 281         , m_invertParentheticalAssertion(false)
 282     {
 283         auto body = std::make_unique<PatternDisjunction>();
 284         m_pattern.m_body = body.get();
 285         m_alternative = body->addNewAlternative();
 286         m_pattern.m_disjunctions.append(WTFMove(body));
 287     }
 288
 289     ~YarrPatternConstructor()
 290     {
 291     }
 292
 293     void reset()
 294     {
 295         m_pattern.reset();
 296         m_characterClassConstructor.reset();
 297
 298         auto body = std::make_unique<PatternDisjunction>();
 299         m_pattern.m_body = body.get();
 300         m_alternative = body->addNewAlternative();
 301         m_pattern.m_disjunctions.append(WTFMove(body));
 302     }
 303
 304     void assertionBOL()
 305     {
 306         if (!m_alternative->m_terms.size() && !m_invertParentheticalAssertion) {
 307             m_alternative->m_startsWithBOL = true;
 308             m_alternative->m_containsBOL = true;
 309             m_pattern.m_containsBOL = true;
 310         }
 311         m_alternative->m_terms.append(PatternTerm::BOL());
 312     }
 313     void assertionEOL()
 314     {
 315         m_alternative->m_terms.append(PatternTerm::EOL());
 316     }
 317     void assertionWordBoundary(bool invert)
 318     {
 319         m_alternative->m_terms.append(PatternTerm::WordBoundary(invert));
 320     }
 321
 322     void atomPatternCharacter(UChar32 ch)
 323     {
 324         // We handle case-insensitive checking of unicode characters which do have both
 325         // cases by handling them as if they were defined using a CharacterClass.
 326         if (!m_pattern.m_ignoreCase || (isASCII(ch) && !m_pattern.m_unicode)) {
 327             m_alternative->m_terms.append(PatternTerm(ch));
 328             return;
 329         }
 330
 331         const CanonicalizationRange* info = canonicalRangeInfoFor(ch, m_pattern.m_unicode ? CanonicalMode::Unicode : CanonicalMode::UCS2);
 332         if (info->type == CanonicalizeUnique) {
 333             m_alternative->m_terms.append(PatternTerm(ch));
 334             return;
 335         }
 336
 337         m_characterClassConstructor.putUnicodeIgnoreCase(ch, info);
 338         auto newCharacterClass = m_characterClassConstructor.charClass();
 339         m_alternative->m_terms.append(PatternTerm(newCharacterClass.get(), false));
 340         m_pattern.m_userCharacterClasses.append(WTFMove(newCharacterClass));
 341     }
 342
 343     void atomBuiltInCharacterClass(BuiltInCharacterClassID classID, bool invert)
 344     {
 345         switch (classID) {
 346         case DigitClassID:
 347             m_alternative->m_terms.append(PatternTerm(m_pattern.digitsCharacterClass(), invert));
 348             break;
 349         case SpaceClassID:
 350             m_alternative->m_terms.append(PatternTerm(m_pattern.spacesCharacterClass(), invert));
 351             break;
 352         case WordClassID:
 353             m_alternative->m_terms.append(PatternTerm(m_pattern.wordcharCharacterClass(), invert));
 354             break;
 355         case NewlineClassID:
 356             m_alternative->m_terms.append(PatternTerm(m_pattern.newlineCharacterClass(), invert));
 357             break;
 358         }
 359     }
 360
 361     void atomCharacterClassBegin(bool invert = false)
 362     {
 363         m_invertCharacterClass = invert;
 364     }
 365
 366     void atomCharacterClassAtom(UChar32 ch)
 367     {
 368         m_characterClassConstructor.putChar(ch);
 369     }
 370
 371     void atomCharacterClassRange(UChar32 begin, UChar32 end)
 372     {
 373         m_characterClassConstructor.putRange(begin, end);
 374     }
 375
 376     void atomCharacterClassBuiltIn(BuiltInCharacterClassID classID, bool invert)
 377     {
 378         ASSERT(classID != NewlineClassID);
 379
 380         switch (classID) {
 381         case DigitClassID:
 382             m_characterClassConstructor.append(invert ? m_pattern.nondigitsCharacterClass() : m_pattern.digitsCharacterClass());
 383             break;
 384
 385         case SpaceClassID:
 386             m_characterClassConstructor.append(invert ? m_pattern.nonspacesCharacterClass() : m_pattern.spacesCharacterClass());
 387             break;
 388
 389         case WordClassID:
 390             m_characterClassConstructor.append(invert ? m_pattern.nonwordcharCharacterClass() : m_pattern.wordcharCharacterClass());
 391             break;
 392
 393         default:
 394             RELEASE_ASSERT_NOT_REACHED();
 395         }
 396     }
 397
 398     void atomCharacterClassEnd()
 399     {
 400         auto newCharacterClass = m_characterClassConstructor.charClass();
 401         m_alternative->m_terms.append(PatternTerm(newCharacterClass.get(), m_invertCharacterClass));
 402         m_pattern.m_userCharacterClasses.append(WTFMove(newCharacterClass));
 403     }
 404
 405     void atomParenthesesSubpatternBegin(bool capture = true)
 406     {
 407         unsigned subpatternId = m_pattern.m_numSubpatterns + 1;
 408         if (capture)
 409             m_pattern.m_numSubpatterns++;
 410
 411         auto parenthesesDisjunction = std::make_unique<PatternDisjunction>(m_alternative);
 412         m_alternative->m_terms.append(PatternTerm(PatternTerm::TypeParenthesesSubpattern, subpatternId, parenthesesDisjunction.get(), capture, false));
 413         m_alternative = parenthesesDisjunction->addNewAlternative();
 414         m_pattern.m_disjunctions.append(WTFMove(parenthesesDisjunction));
 415     }
 416
 417     void atomParentheticalAssertionBegin(bool invert = false)
 418     {
 419         auto parenthesesDisjunction = std::make_unique<PatternDisjunction>(m_alternative);
 420         m_alternative->m_terms.append(PatternTerm(PatternTerm::TypeParentheticalAssertion, m_pattern.m_numSubpatterns + 1, parenthesesDisjunction.get(), false, invert));
 421         m_alternative = parenthesesDisjunction->addNewAlternative();
 422         m_invertParentheticalAssertion = invert;
 423         m_pattern.m_disjunctions.append(WTFMove(parenthesesDisjunction));
 424     }
 425
 426     void atomParenthesesEnd()
 427     {
 428         ASSERT(m_alternative->m_parent);
 429         ASSERT(m_alternative->m_parent->m_parent);
 430
 431         PatternDisjunction* parenthesesDisjunction = m_alternative->m_parent;
 432         m_alternative = m_alternative->m_parent->m_parent;
 433
 434         PatternTerm& lastTerm = m_alternative->lastTerm();
 435
 436         unsigned numParenAlternatives = parenthesesDisjunction->m_alternatives.size();
 437         unsigned numBOLAnchoredAlts = 0;
 438
 439         for (unsigned i = 0; i < numParenAlternatives; i++) {
 440             // Bubble up BOL flags
 441             if (parenthesesDisjunction->m_alternatives[i]->m_startsWithBOL)
 442                 numBOLAnchoredAlts++;
 443         }
 444
 445         if (numBOLAnchoredAlts) {
 446             m_alternative->m_containsBOL = true;
 447             // If all the alternatives in parens start with BOL, then so does this one
 448             if (numBOLAnchoredAlts == numParenAlternatives)
 449                 m_alternative->m_startsWithBOL = true;
 450         }
 451
 452         lastTerm.parentheses.lastSubpatternId = m_pattern.m_numSubpatterns;
 453         m_invertParentheticalAssertion = false;
 454     }
 455
 456     void atomBackReference(unsigned subpatternId)
 457     {
 458         ASSERT(subpatternId);
 459         m_pattern.m_containsBackreferences = true;
 460         m_pattern.m_maxBackReference = std::max(m_pattern.m_maxBackReference, subpatternId);
 461
 462         if (subpatternId > m_pattern.m_numSubpatterns) {
 463             m_alternative->m_terms.append(PatternTerm::ForwardReference());
 464             return;
 465         }
 466
 467         PatternAlternative* currentAlternative = m_alternative;
 468         ASSERT(currentAlternative);
 469
 470         // Note to self: if we waited until the AST was baked, we could also remove forwards refs
 471         while ((currentAlternative = currentAlternative->m_parent->m_parent)) {
 472             PatternTerm& term = currentAlternative->lastTerm();
 473             ASSERT((term.type == PatternTerm::TypeParenthesesSubpattern) || (term.type == PatternTerm::TypeParentheticalAssertion));
 474
 475             if ((term.type == PatternTerm::TypeParenthesesSubpattern) && term.capture() && (subpatternId == term.parentheses.subpatternId)) {
 476                 m_alternative->m_terms.append(PatternTerm::ForwardReference());
 477                 return;
 478             }
 479         }
 480
 481         m_alternative->m_terms.append(PatternTerm(subpatternId));
 482     }
 483
 484     // deep copy the argument disjunction.  If filterStartsWithBOL is true,
 485     // skip alternatives with m_startsWithBOL set true.
 486     PatternDisjunction* copyDisjunction(PatternDisjunction* disjunction, bool filterStartsWithBOL = false)
 487     {
 488         std::unique_ptr<PatternDisjunction> newDisjunction;
 489         for (unsigned alt = 0; alt < disjunction->m_alternatives.size(); ++alt) {
 490             PatternAlternative* alternative = disjunction->m_alternatives[alt].get();
 491             if (!filterStartsWithBOL || !alternative->m_startsWithBOL) {
 492                 if (!newDisjunction) {
 493                     newDisjunction = std::make_unique<PatternDisjunction>();
 494                     newDisjunction->m_parent = disjunction->m_parent;
 495                 }
 496                 PatternAlternative* newAlternative = newDisjunction->addNewAlternative();
 497                 newAlternative->m_terms.reserveInitialCapacity(alternative->m_terms.size());
 498                 for (unsigned i = 0; i < alternative->m_terms.size(); ++i)
 499                     newAlternative->m_terms.append(copyTerm(alternative->m_terms[i], filterStartsWithBOL));
 500             }
 501         }
 502
 503         if (!newDisjunction)
 504             return 0;
 505
 506         PatternDisjunction* copiedDisjunction = newDisjunction.get();
 507         m_pattern.m_disjunctions.append(WTFMove(newDisjunction));
 508         return copiedDisjunction;
 509     }
 510
 511     PatternTerm copyTerm(PatternTerm& term, bool filterStartsWithBOL = false)
 512     {
 513         if ((term.type != PatternTerm::TypeParenthesesSubpattern) && (term.type != PatternTerm::TypeParentheticalAssertion))
 514             return PatternTerm(term);
 515
 516         PatternTerm termCopy = term;
 517         termCopy.parentheses.disjunction = copyDisjunction(termCopy.parentheses.disjunction, filterStartsWithBOL);
 518         return termCopy;
 519     }
 520
 521     void quantifyAtom(unsigned min, unsigned max, bool greedy)
 522     {
 523         ASSERT(min <= max);
 524         ASSERT(m_alternative->m_terms.size());
 525
 526         if (!max) {
 527             m_alternative->removeLastTerm();
 528             return;
 529         }
 530
 531         PatternTerm& term = m_alternative->lastTerm();
 532         ASSERT(term.type > PatternTerm::TypeAssertionWordBoundary);
 533         ASSERT((term.quantityCount == 1) && (term.quantityType == QuantifierFixedCount));
 534
 535         if (term.type == PatternTerm::TypeParentheticalAssertion) {
 536             // If an assertion is quantified with a minimum count of zero, it can simply be removed.
 537             // This arises from the RepeatMatcher behaviour in the spec. Matching an assertion never
 538             // results in any input being consumed, however the continuation passed to the assertion
 539             // (called in steps, 8c and 9 of the RepeatMatcher definition, ES5.1 15.10.2.5) will
 540             // reject all zero length matches (see step 2.1). A match from the continuation of the
 541             // expression will still be accepted regardless (via steps 8a and 11) - the upshot of all
 542             // this is that matches from the assertion are not required, and won't be accepted anyway,
 543             // so no need to ever run it.
 544             if (!min)
 545                 m_alternative->removeLastTerm();
 546             // We never need to run an assertion more than once. Subsequent interations will be run
 547             // with the same start index (since assertions are non-capturing) and the same captures
 548             // (per step 4 of RepeatMatcher in ES5.1 15.10.2.5), and as such will always produce the
 549             // same result and captures. If the first match succeeds then the subsequent (min - 1)
 550             // matches will too. Any additional optional matches will fail (on the same basis as the
 551             // minimum zero quantified assertions, above), but this will still result in a match.
 552             return;
 553         }
 554
 555         if (min == 0)
 556             term.quantify(max, greedy   ? QuantifierGreedy : QuantifierNonGreedy);
 557         else if (min == max)
 558             term.quantify(min, QuantifierFixedCount);
 559         else {
 560             term.quantify(min, QuantifierFixedCount);
 561             m_alternative->m_terms.append(copyTerm(term));
 562             // NOTE: this term is interesting from an analysis perspective, in that it can be ignored.....
 563             m_alternative->lastTerm().quantify((max == quantifyInfinite) ? max : max - min, greedy ? QuantifierGreedy : QuantifierNonGreedy);
 564             if (m_alternative->lastTerm().type == PatternTerm::TypeParenthesesSubpattern)
 565                 m_alternative->lastTerm().parentheses.isCopy = true;
 566         }
 567     }
 568
 569     void disjunction()
 570     {
 571         m_alternative = m_alternative->m_parent->addNewAlternative();
 572     }
 573
 574     unsigned setupAlternativeOffsets(PatternAlternative* alternative, unsigned currentCallFrameSize, unsigned initialInputPosition)
 575     {
 576         alternative->m_hasFixedSize = true;
 577         Checked<unsigned> currentInputPosition = initialInputPosition;
 578
 579         for (unsigned i = 0; i < alternative->m_terms.size(); ++i) {
 580             PatternTerm& term = alternative->m_terms[i];
 581
 582             switch (term.type) {
 583             case PatternTerm::TypeAssertionBOL:
 584             case PatternTerm::TypeAssertionEOL:
 585             case PatternTerm::TypeAssertionWordBoundary:
 586                 term.inputPosition = currentInputPosition.unsafeGet();
 587                 break;
 588
 589             case PatternTerm::TypeBackReference:
 590                 term.inputPosition = currentInputPosition.unsafeGet();
 591                 term.frameLocation = currentCallFrameSize;
 592                 currentCallFrameSize += YarrStackSpaceForBackTrackInfoBackReference;
 593                 alternative->m_hasFixedSize = false;
 594                 break;
 595
 596             case PatternTerm::TypeForwardReference:
 597                 break;
 598
 599             case PatternTerm::TypePatternCharacter:
 600                 term.inputPosition = currentInputPosition.unsafeGet();
 601                 if (term.quantityType != QuantifierFixedCount) {
 602                     term.frameLocation = currentCallFrameSize;
 603                     currentCallFrameSize += YarrStackSpaceForBackTrackInfoPatternCharacter;
 604                     alternative->m_hasFixedSize = false;
 605                 } else if (m_pattern.m_unicode) {
 606                     currentInputPosition += U16_LENGTH(term.patternCharacter) * term.quantityCount;
 607                 } else
 608                     currentInputPosition += term.quantityCount;
 609                 break;
 610
 611             case PatternTerm::TypeCharacterClass:
 612                 term.inputPosition = currentInputPosition.unsafeGet();
 613                 if (term.quantityType != QuantifierFixedCount) {
 614                     term.frameLocation = currentCallFrameSize;
 615                     currentCallFrameSize += YarrStackSpaceForBackTrackInfoCharacterClass;
 616                     alternative->m_hasFixedSize = false;
 617                 } else if (m_pattern.m_unicode) {
 618                     term.frameLocation = currentCallFrameSize;
 619                     currentCallFrameSize += YarrStackSpaceForBackTrackInfoCharacterClass;
 620                     currentInputPosition += term.quantityCount;
 621                     alternative->m_hasFixedSize = false;
 622                 } else
 623                     currentInputPosition += term.quantityCount;
 624                 break;
 625
 626             case PatternTerm::TypeParenthesesSubpattern:
 627                 // Note: for fixed once parentheses we will ensure at least the minimum is available; others are on their own.
 628                 term.frameLocation = currentCallFrameSize;
 629                 if (term.quantityCount == 1 && !term.parentheses.isCopy) {
 630                     if (term.quantityType != QuantifierFixedCount)
 631                         currentCallFrameSize += YarrStackSpaceForBackTrackInfoParenthesesOnce;
 632                     currentCallFrameSize = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize, currentInputPosition.unsafeGet());
 633                     // If quantity is fixed, then pre-check its minimum size.
 634                     if (term.quantityType == QuantifierFixedCount)
 635                         currentInputPosition += term.parentheses.disjunction->m_minimumSize;
 636                     term.inputPosition = currentInputPosition.unsafeGet();
 637                 } else if (term.parentheses.isTerminal) {
 638                     currentCallFrameSize += YarrStackSpaceForBackTrackInfoParenthesesTerminal;
 639                     currentCallFrameSize = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize, currentInputPosition.unsafeGet());
 640                     term.inputPosition = currentInputPosition.unsafeGet();
 641                 } else {
 642                     term.inputPosition = currentInputPosition.unsafeGet();
 643                     setupDisjunctionOffsets(term.parentheses.disjunction, 0, currentInputPosition.unsafeGet());
 644                     currentCallFrameSize += YarrStackSpaceForBackTrackInfoParentheses;
 645                 }
 646                 // Fixed count of 1 could be accepted, if they have a fixed size *AND* if all alternatives are of the same length.
 647                 alternative->m_hasFixedSize = false;
 648                 break;
 649
 650             case PatternTerm::TypeParentheticalAssertion:
 651                 term.inputPosition = currentInputPosition.unsafeGet();
 652                 term.frameLocation = currentCallFrameSize;
 653                 currentCallFrameSize = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize + YarrStackSpaceForBackTrackInfoParentheticalAssertion, currentInputPosition.unsafeGet());
 654                 break;
 655
 656             case PatternTerm::TypeDotStarEnclosure:
 657                 alternative->m_hasFixedSize = false;
 658                 term.inputPosition = initialInputPosition;
 659                 break;
 660             }
 661         }
 662
 663         alternative->m_minimumSize = (currentInputPosition - initialInputPosition).unsafeGet();
 664         return currentCallFrameSize;
 665     }
 666
 667     unsigned setupDisjunctionOffsets(PatternDisjunction* disjunction, unsigned initialCallFrameSize, unsigned initialInputPosition)
 668     {
 669         if ((disjunction != m_pattern.m_body) && (disjunction->m_alternatives.size() > 1))
 670             initialCallFrameSize += YarrStackSpaceForBackTrackInfoAlternative;
 671
 672         unsigned minimumInputSize = UINT_MAX;
 673         unsigned maximumCallFrameSize = 0;
 674         bool hasFixedSize = true;
 675
 676         for (unsigned alt = 0; alt < disjunction->m_alternatives.size(); ++alt) {
 677             PatternAlternative* alternative = disjunction->m_alternatives[alt].get();
 678             unsigned currentAlternativeCallFrameSize = setupAlternativeOffsets(alternative, initialCallFrameSize, initialInputPosition);
 679             minimumInputSize = std::min(minimumInputSize, alternative->m_minimumSize);
 680             maximumCallFrameSize = std::max(maximumCallFrameSize, currentAlternativeCallFrameSize);
 681             hasFixedSize &= alternative->m_hasFixedSize;
 682             if (alternative->m_minimumSize > INT_MAX)
 683                 m_pattern.m_containsUnsignedLengthPattern = true;
 684         }
 685
 686         ASSERT(minimumInputSize != UINT_MAX);
 687         ASSERT(maximumCallFrameSize >= initialCallFrameSize);
 688
 689         disjunction->m_hasFixedSize = hasFixedSize;
 690         disjunction->m_minimumSize = minimumInputSize;
 691         disjunction->m_callFrameSize = maximumCallFrameSize;
 692         return maximumCallFrameSize;
 693     }
 694
 695     void setupOffsets()
 696     {
 697         setupDisjunctionOffsets(m_pattern.m_body, 0, 0);
 698     }
 699
 700     // This optimization identifies sets of parentheses that we will never need to backtrack.
 701     // In these cases we do not need to store state from prior iterations.
 702     // We can presently avoid backtracking for:
 703     //   * where the parens are at the end of the regular expression (last term in any of the
 704     //     alternatives of the main body disjunction).
 705     //   * where the parens are non-capturing, and quantified unbounded greedy (*).
 706     //   * where the parens do not contain any capturing subpatterns.
 707     void checkForTerminalParentheses()
 708     {
 709         // This check is much too crude; should be just checking whether the candidate
 710         // node contains nested capturing subpatterns, not the whole expression!
 711         if (m_pattern.m_numSubpatterns)
 712             return;
 713
 714         Vector<std::unique_ptr<PatternAlternative>>& alternatives = m_pattern.m_body->m_alternatives;
 715         for (size_t i = 0; i < alternatives.size(); ++i) {
 716             Vector<PatternTerm>& terms = alternatives[i]->m_terms;
 717             if (terms.size()) {
 718                 PatternTerm& term = terms.last();
 719                 if (term.type == PatternTerm::TypeParenthesesSubpattern
 720                     && term.quantityType == QuantifierGreedy
 721                     && term.quantityCount == quantifyInfinite
 722                     && !term.capture())
 723                     term.parentheses.isTerminal = true;
 724             }
 725         }
 726     }
 727
 728     void optimizeBOL()
 729     {
 730         // Look for expressions containing beginning of line (^) anchoring and unroll them.
 731         // e.g. /^a|^b|c/ becomes /^a|^b|c/ which is executed once followed by /c/ which loops
 732         // This code relies on the parsing code tagging alternatives with m_containsBOL and
 733         // m_startsWithBOL and rolling those up to containing alternatives.
 734         // At this point, this is only valid for non-multiline expressions.
 735         PatternDisjunction* disjunction = m_pattern.m_body;
 736
 737         if (!m_pattern.m_containsBOL || m_pattern.m_multiline)
 738             return;
 739
 740         PatternDisjunction* loopDisjunction = copyDisjunction(disjunction, true);
 741
 742         // Set alternatives in disjunction to "onceThrough"
 743         for (unsigned alt = 0; alt < disjunction->m_alternatives.size(); ++alt)
 744             disjunction->m_alternatives[alt]->setOnceThrough();
 745
 746         if (loopDisjunction) {
 747             // Move alternatives from loopDisjunction to disjunction
 748             for (unsigned alt = 0; alt < loopDisjunction->m_alternatives.size(); ++alt)
 749                 disjunction->m_alternatives.append(loopDisjunction->m_alternatives[alt].release());
 750
 751             loopDisjunction->m_alternatives.clear();
 752         }
 753     }
 754
 755     bool containsCapturingTerms(PatternAlternative* alternative, size_t firstTermIndex, size_t endIndex)
 756     {
 757         Vector<PatternTerm>& terms = alternative->m_terms;
 758
 759         ASSERT(endIndex <= terms.size());
 760         for (size_t termIndex = firstTermIndex; termIndex < endIndex; ++termIndex) {
 761             PatternTerm& term = terms[termIndex];
 762
 763             if (term.m_capture)
 764                 return true;
 765
 766             if (term.type == PatternTerm::TypeParenthesesSubpattern) {
 767                 PatternDisjunction* nestedDisjunction = term.parentheses.disjunction;
 768                 for (unsigned alt = 0; alt < nestedDisjunction->m_alternatives.size(); ++alt) {
 769                     if (containsCapturingTerms(nestedDisjunction->m_alternatives[alt].get(), 0, nestedDisjunction->m_alternatives[alt]->m_terms.size()))
 770                         return true;
 771                 }
 772             }
 773         }
 774
 775         return false;
 776     }
 777
 778     // This optimization identifies alternatives in the form of
 779     // [^].*[?]<expression>.*[$] for expressions that don't have any
 780     // capturing terms. The alternative is changed to <expression>
 781     // followed by processing of the dot stars to find and adjust the
 782     // beginning and the end of the match.
 783     void optimizeDotStarWrappedExpressions()
 784     {
 785         Vector<std::unique_ptr<PatternAlternative>>& alternatives = m_pattern.m_body->m_alternatives;
 786         if (alternatives.size() != 1)
 787             return;
 788
 789         PatternAlternative* alternative = alternatives[0].get();
 790         Vector<PatternTerm>& terms = alternative->m_terms;
 791         if (terms.size() >= 3) {
 792             bool startsWithBOL = false;
 793             bool endsWithEOL = false;
 794             size_t termIndex, firstExpressionTerm;
 795
 796             termIndex = 0;
 797             if (terms[termIndex].type == PatternTerm::TypeAssertionBOL) {
 798                 startsWithBOL = true;
 799                 ++termIndex;
 800             }
 801
 802             PatternTerm& firstNonAnchorTerm = terms[termIndex];
 803             if ((firstNonAnchorTerm.type != PatternTerm::TypeCharacterClass) || (firstNonAnchorTerm.characterClass != m_pattern.newlineCharacterClass()) || !((firstNonAnchorTerm.quantityType == QuantifierGreedy) || (firstNonAnchorTerm.quantityType == QuantifierNonGreedy)))
 804                 return;
 805
 806             firstExpressionTerm = termIndex + 1;
 807
 808             termIndex = terms.size() - 1;
 809             if (terms[termIndex].type == PatternTerm::TypeAssertionEOL) {
 810                 endsWithEOL = true;
 811                 --termIndex;
 812             }
 813
 814             PatternTerm& lastNonAnchorTerm = terms[termIndex];
 815             if ((lastNonAnchorTerm.type != PatternTerm::TypeCharacterClass) || (lastNonAnchorTerm.characterClass != m_pattern.newlineCharacterClass()) || (lastNonAnchorTerm.quantityType != QuantifierGreedy))
 816                 return;
 817
 818             size_t endIndex = termIndex;
 819             if (firstExpressionTerm >= endIndex)
 820                 return;
 821
 822             if (!containsCapturingTerms(alternative, firstExpressionTerm, endIndex)) {
 823                 for (termIndex = terms.size() - 1; termIndex >= endIndex; --termIndex)
 824                     terms.remove(termIndex);
 825
 826                 for (termIndex = firstExpressionTerm; termIndex > 0; --termIndex)
 827                     terms.remove(termIndex - 1);
 828
 829                 terms.append(PatternTerm(startsWithBOL, endsWithEOL));
 830
 831                 m_pattern.m_containsBOL = false;
 832             }
 833         }
 834     }
 835
 836 private:
 837     YarrPattern& m_pattern;
 838     PatternAlternative* m_alternative;
 839     CharacterClassConstructor m_characterClassConstructor;
 840     bool m_invertCharacterClass;
 841     bool m_invertParentheticalAssertion;
 842 };
 843
 844 const char* YarrPattern::compile(const String& patternString)
 845 {
 846     YarrPatternConstructor constructor(*this);
 847
 848     if (const char* error = parse(constructor, patternString, m_unicode))
 849         return error;
 850
 851     // If the pattern contains illegal backreferences reset & reparse.
 852     // Quoting Netscape's "What's new in JavaScript 1.2",
 853     //      "Note: if the number of left parentheses is less than the number specified
 854     //       in \#, the \# is taken as an octal escape as described in the next row."
 855     if (containsIllegalBackReference()) {
 856         unsigned numSubpatterns = m_numSubpatterns;
 857
 858         constructor.reset();
 859 #if !ASSERT_DISABLED
 860         const char* error =
 861 #endif
 862             parse(constructor, patternString, m_unicode, numSubpatterns);
 863
 864         ASSERT(!error);
 865         ASSERT(numSubpatterns == m_numSubpatterns);
 866     }
 867
 868     constructor.checkForTerminalParentheses();
 869     constructor.optimizeDotStarWrappedExpressions();
 870     constructor.optimizeBOL();
 871
 872     constructor.setupOffsets();
 873
 874     return 0;
 875 }
 876
 877 YarrPattern::YarrPattern(const String& pattern, bool ignoreCase, bool multiline, bool unicode, const char** error)
 878     : m_ignoreCase(ignoreCase)
 879     , m_multiline(multiline)
 880     , m_unicode(unicode)
 881     , m_containsBackreferences(false)
 882     , m_containsBOL(false)
 883     , m_containsUnsignedLengthPattern(false)
 884     , m_numSubpatterns(0)
 885     , m_maxBackReference(0)
 886     , newlineCached(0)
 887     , digitsCached(0)
 888     , spacesCached(0)
 889     , wordcharCached(0)
 890     , nondigitsCached(0)
 891     , nonspacesCached(0)
 892     , nonwordcharCached(0)
 893 {
 894     *error = compile(pattern);
 895 }
 896
 897 } }