Changeset 210837 in webkit


Ignore:
Timestamp:
Jan 17, 2017 5:27:04 PM (7 years ago)
Author:
msaboff@apple.com
Message:

Nested parenthesized regular expressions with non-zero minimum counts appear to hang and use lots of memory
​https://bugs.webkit.org/show_bug.cgi?id=167125

Reviewed by Filip Pizlo.

JSTests:

  • microbenchmarks/regexp-nested-nonzero-min-counted-parens.js: Added.

New test with limits that run slow and take a reasonable amount of memory
before the change and run fast, using little memory with the change.

Source/JavaScriptCore:

Changed Yarr to handle nested parenthesized subexpressions where the minimum count is
not 0 directly in the Yarr interpreter. Previously we'd factor an expression like
(a|b)+ into (a|b)(a|b)* with special handling for captures. This factoring was done
using a deep copy that doubled the size of the resulting expresion for each nested
parenthesized subexpression. Now the Yarr interpreter can directly process a regexp
like (a|b){2,42}.

The parser will allow one level of nested, non-zero minimum, counted parenthesis using
the old copy method. After one level, it will generate parenthesis terms with a non-zero
minimum. Such an expression wasn't handled by the Yarr JIT before the change, so this
change isn't a performance regression.

Added a minimum count to the YarrPattern and ByteTerm classes, and then factored that
minimum into the interpreter. A non-zero minimum is only handled by the Yarr interpreter.
If the Yarr JIT see such a term, it punts back to the interpreter.

  • yarr/YarrInterpreter.cpp:

(JSC::Yarr::Interpreter::backtrackPatternCharacter):
(JSC::Yarr::Interpreter::backtrackPatternCasedCharacter):
(JSC::Yarr::Interpreter::matchCharacterClass):
(JSC::Yarr::Interpreter::backtrackCharacterClass):
(JSC::Yarr::Interpreter::matchBackReference):
(JSC::Yarr::Interpreter::backtrackBackReference):
(JSC::Yarr::Interpreter::matchParenthesesOnceBegin):
(JSC::Yarr::Interpreter::matchParenthesesOnceEnd):
(JSC::Yarr::Interpreter::backtrackParenthesesOnceBegin):
(JSC::Yarr::Interpreter::backtrackParenthesesOnceEnd):
(JSC::Yarr::Interpreter::matchParenthesesTerminalBegin):
(JSC::Yarr::Interpreter::backtrackParenthesesTerminalBegin):
(JSC::Yarr::Interpreter::matchParentheticalAssertionBegin):
(JSC::Yarr::Interpreter::matchParentheticalAssertionEnd):
(JSC::Yarr::Interpreter::backtrackParentheticalAssertionBegin):
(JSC::Yarr::Interpreter::backtrackParentheticalAssertionEnd):
(JSC::Yarr::Interpreter::matchParentheses):
(JSC::Yarr::Interpreter::backtrackParentheses):
(JSC::Yarr::Interpreter::matchDisjunction):
(JSC::Yarr::ByteCompiler::atomPatternCharacter):
(JSC::Yarr::ByteCompiler::atomCharacterClass):
(JSC::Yarr::ByteCompiler::atomBackReference):
(JSC::Yarr::ByteCompiler::atomParentheticalAssertionEnd):
(JSC::Yarr::ByteCompiler::atomParenthesesSubpatternEnd):
(JSC::Yarr::ByteCompiler::atomParenthesesOnceEnd):
(JSC::Yarr::ByteCompiler::atomParenthesesTerminalEnd):
(JSC::Yarr::ByteCompiler::emitDisjunction):

  • yarr/YarrInterpreter.h:

(JSC::Yarr::ByteTerm::ByteTerm):

  • yarr/YarrJIT.cpp:

(JSC::Yarr::YarrGenerator::generatePatternCharacterOnce):
(JSC::Yarr::YarrGenerator::generatePatternCharacterFixed):
(JSC::Yarr::YarrGenerator::generatePatternCharacterGreedy):
(JSC::Yarr::YarrGenerator::backtrackPatternCharacterNonGreedy):
(JSC::Yarr::YarrGenerator::generateCharacterClassFixed):
(JSC::Yarr::YarrGenerator::generateCharacterClassGreedy):
(JSC::Yarr::YarrGenerator::backtrackCharacterClassNonGreedy):
(JSC::Yarr::YarrGenerator::generateTerm):
(JSC::Yarr::YarrGenerator::backtrackTerm):
(JSC::Yarr::YarrGenerator::generate):
(JSC::Yarr::YarrGenerator::backtrack):
(JSC::Yarr::YarrGenerator::opCompileParenthesesSubpattern):

  • yarr/YarrPattern.cpp:

(JSC::Yarr::YarrPatternConstructor::copyTerm):
(JSC::Yarr::YarrPatternConstructor::quantifyAtom):
(JSC::Yarr::YarrPatternConstructor::checkForTerminalParentheses):
(JSC::Yarr::YarrPattern::YarrPattern):

  • yarr/YarrPattern.h:

(JSC::Yarr::PatternTerm::PatternTerm):
(JSC::Yarr::PatternTerm::quantify):
(JSC::Yarr::YarrPattern::reset):

Location:
trunk
Files:
1 added
7 edited

Legend:

Unmodified
Added
Removed

  • trunk/JSTests/ChangeLog

    r210775 r210837  
     12017-01-17  Michael Saboff  <msaboff@apple.com>
     2
     3        Nested parenthesized regular expressions with non-zero minimum counts appear to hang and use lots of memory
     4        https://bugs.webkit.org/show_bug.cgi?id=167125
     5
     6        Reviewed by Filip Pizlo.
     7
     8        * microbenchmarks/regexp-nested-nonzero-min-counted-parens.js: Added.
     9        New test with limits that run slow and take a reasonable amount of memory
     10        before the change and run fast, using little memory with the change.
     11
    1122017-01-14  Yusuke Suzuki  <utatane.tea@gmail.com>
    213

  • trunk/Source/JavaScriptCore/ChangeLog

    r210832 r210837  
     12017-01-17  Michael Saboff  <msaboff@apple.com>
     2
     3        Nested parenthesized regular expressions with non-zero minimum counts appear to hang and use lots of memory
     4        https://bugs.webkit.org/show_bug.cgi?id=167125
     5
     6        Reviewed by Filip Pizlo.
     7
     8        Changed Yarr to handle nested parenthesized subexpressions where the minimum count is
     9        not 0 directly in the Yarr interpreter.  Previously we'd factor an expression like
     10        (a|b)+ into (a|b)(a|b)* with special handling for captures.  This factoring was done
     11        using a deep copy that doubled the size of the resulting expresion for each nested
     12        parenthesized subexpression.  Now the Yarr interpreter can directly process a regexp
     13        like (a|b){2,42}. 
     14
     15        The parser will allow one level of nested, non-zero minimum, counted parenthesis using
     16        the old copy method.  After one level, it will generate parenthesis terms with a non-zero
     17        minimum.   Such an expression wasn't handled by the Yarr JIT before the change, so this
     18        change isn't a performance regression.
     19
     20        Added a minimum count to the YarrPattern and ByteTerm classes, and then factored that
     21        minimum into the interpreter.  A non-zero minimum is only handled by the Yarr interpreter.
     22        If the Yarr JIT see such a term, it punts back to the interpreter.
     23
     24        * yarr/YarrInterpreter.cpp:
     25        (JSC::Yarr::Interpreter::backtrackPatternCharacter):
     26        (JSC::Yarr::Interpreter::backtrackPatternCasedCharacter):
     27        (JSC::Yarr::Interpreter::matchCharacterClass):
     28        (JSC::Yarr::Interpreter::backtrackCharacterClass):
     29        (JSC::Yarr::Interpreter::matchBackReference):
     30        (JSC::Yarr::Interpreter::backtrackBackReference):
     31        (JSC::Yarr::Interpreter::matchParenthesesOnceBegin):
     32        (JSC::Yarr::Interpreter::matchParenthesesOnceEnd):
     33        (JSC::Yarr::Interpreter::backtrackParenthesesOnceBegin):
     34        (JSC::Yarr::Interpreter::backtrackParenthesesOnceEnd):
     35        (JSC::Yarr::Interpreter::matchParenthesesTerminalBegin):
     36        (JSC::Yarr::Interpreter::backtrackParenthesesTerminalBegin):
     37        (JSC::Yarr::Interpreter::matchParentheticalAssertionBegin):
     38        (JSC::Yarr::Interpreter::matchParentheticalAssertionEnd):
     39        (JSC::Yarr::Interpreter::backtrackParentheticalAssertionBegin):
     40        (JSC::Yarr::Interpreter::backtrackParentheticalAssertionEnd):
     41        (JSC::Yarr::Interpreter::matchParentheses):
     42        (JSC::Yarr::Interpreter::backtrackParentheses):
     43        (JSC::Yarr::Interpreter::matchDisjunction):
     44        (JSC::Yarr::ByteCompiler::atomPatternCharacter):
     45        (JSC::Yarr::ByteCompiler::atomCharacterClass):
     46        (JSC::Yarr::ByteCompiler::atomBackReference):
     47        (JSC::Yarr::ByteCompiler::atomParentheticalAssertionEnd):
     48        (JSC::Yarr::ByteCompiler::atomParenthesesSubpatternEnd):
     49        (JSC::Yarr::ByteCompiler::atomParenthesesOnceEnd):
     50        (JSC::Yarr::ByteCompiler::atomParenthesesTerminalEnd):
     51        (JSC::Yarr::ByteCompiler::emitDisjunction):
     52        * yarr/YarrInterpreter.h:
     53        (JSC::Yarr::ByteTerm::ByteTerm):
     54        * yarr/YarrJIT.cpp:
     55        (JSC::Yarr::YarrGenerator::generatePatternCharacterOnce):
     56        (JSC::Yarr::YarrGenerator::generatePatternCharacterFixed):
     57        (JSC::Yarr::YarrGenerator::generatePatternCharacterGreedy):
     58        (JSC::Yarr::YarrGenerator::backtrackPatternCharacterNonGreedy):
     59        (JSC::Yarr::YarrGenerator::generateCharacterClassFixed):
     60        (JSC::Yarr::YarrGenerator::generateCharacterClassGreedy):
     61        (JSC::Yarr::YarrGenerator::backtrackCharacterClassNonGreedy):
     62        (JSC::Yarr::YarrGenerator::generateTerm):
     63        (JSC::Yarr::YarrGenerator::backtrackTerm):
     64        (JSC::Yarr::YarrGenerator::generate):
     65        (JSC::Yarr::YarrGenerator::backtrack):
     66        (JSC::Yarr::YarrGenerator::opCompileParenthesesSubpattern):
     67        * yarr/YarrPattern.cpp:
     68        (JSC::Yarr::YarrPatternConstructor::copyTerm):
     69        (JSC::Yarr::YarrPatternConstructor::quantifyAtom):
     70        (JSC::Yarr::YarrPatternConstructor::checkForTerminalParentheses):
     71        (JSC::Yarr::YarrPattern::YarrPattern):
     72        * yarr/YarrPattern.h:
     73        (JSC::Yarr::PatternTerm::PatternTerm):
     74        (JSC::Yarr::PatternTerm::quantify):
     75        (JSC::Yarr::YarrPattern::reset):
     76
    1772017-01-17  Joseph Pecoraro  <pecoraro@apple.com>
    278

  • trunk/Source/JavaScriptCore/yarr/YarrInterpreter.cpp

    r210023 r210837  
    439439
    440440        case QuantifierNonGreedy:
    441             if ((backTrack->matchAmount < term.atom.quantityCount) && input.checkInput(1)) {
     441            if ((backTrack->matchAmount < term.atom.quantityMaxCount) && input.checkInput(1)) {
    442442                ++backTrack->matchAmount;
    443443                if (checkCharacter(term.atom.patternCharacter, term.inputPosition + 1))
    … …  
    468468
    469469        case QuantifierNonGreedy:
    470             if ((backTrack->matchAmount < term.atom.quantityCount) && input.checkInput(1)) {
     470            if ((backTrack->matchAmount < term.atom.quantityMaxCount) && input.checkInput(1)) {
    471471                ++backTrack->matchAmount;
    472472                if (checkCasedCharacter(term.atom.casedCharacter.lo, term.atom.casedCharacter.hi, term.inputPosition + 1))
    … …  
    490490                backTrack->begin = input.getPos();
    491491                unsigned matchAmount = 0;
    492                 for (matchAmount = 0; matchAmount < term.atom.quantityCount; ++matchAmount) {
     492                for (matchAmount = 0; matchAmount < term.atom.quantityMaxCount; ++matchAmount) {
    493493                    if (!checkCharacterClass(term.atom.characterClass, term.invert(), term.inputPosition - matchAmount)) {
    494494                        input.setPos(backTrack->begin);
    … …  
    500500            }
    501501
    502             for (unsigned matchAmount = 0; matchAmount < term.atom.quantityCount; ++matchAmount) {
     502            for (unsigned matchAmount = 0; matchAmount < term.atom.quantityMaxCount; ++matchAmount) {
    503503                if (!checkCharacterClass(term.atom.characterClass, term.invert(), term.inputPosition - matchAmount))
    504504                    return false;
    … …  
    511511            backTrack->begin = position;
    512512            unsigned matchAmount = 0;
    513             while ((matchAmount < term.atom.quantityCount) && input.checkInput(1)) {
     513            while ((matchAmount < term.atom.quantityMaxCount) && input.checkInput(1)) {
    514514                if (!checkCharacterClass(term.atom.characterClass, term.invert(), term.inputPosition + 1)) {
    515515                    input.setPos(position);
    … …  
    566566
    567567        case QuantifierNonGreedy:
    568             if ((backTrack->matchAmount < term.atom.quantityCount) && input.checkInput(1)) {
     568            if ((backTrack->matchAmount < term.atom.quantityMaxCount) && input.checkInput(1)) {
    569569                ++backTrack->matchAmount;
    570570                if (checkCharacterClass(term.atom.characterClass, term.invert(), term.inputPosition + 1))
    … …  
    603603        case QuantifierFixedCount: {
    604604            backTrack->begin = input.getPos();
    605             for (unsigned matchAmount = 0; matchAmount < term.atom.quantityCount; ++matchAmount) {
     605            for (unsigned matchAmount = 0; matchAmount < term.atom.quantityMaxCount; ++matchAmount) {
    606606                if (!tryConsumeBackReference(matchBegin, matchEnd, term.inputPosition)) {
    607607                    input.setPos(backTrack->begin);
    … …  
    614614        case QuantifierGreedy: {
    615615            unsigned matchAmount = 0;
    616             while ((matchAmount < term.atom.quantityCount) && tryConsumeBackReference(matchBegin, matchEnd, term.inputPosition))
     616            while ((matchAmount < term.atom.quantityMaxCount) && tryConsumeBackReference(matchBegin, matchEnd, term.inputPosition))
    617617                ++matchAmount;
    618618            backTrack->matchAmount = matchAmount;
    … …  
    648648        switch (term.atom.quantityType) {
    649649        case QuantifierFixedCount:
    650             // for quantityCount == 1, could rewind.
     650            // for quantityMaxCount == 1, could rewind.
    651651            input.setPos(backTrack->begin);
    652652            break;
    … …  
    661661
    662662        case QuantifierNonGreedy:
    663             if ((backTrack->matchAmount < term.atom.quantityCount) && tryConsumeBackReference(matchBegin, matchEnd, term.inputPosition)) {
     663            if ((backTrack->matchAmount < term.atom.quantityMaxCount) && tryConsumeBackReference(matchBegin, matchEnd, term.inputPosition)) {
    664664                ++backTrack->matchAmount;
    665665                return true;
    … …  
    709709    {
    710710        ASSERT(term.type == ByteTerm::TypeParenthesesSubpatternOnceBegin);
    711         ASSERT(term.atom.quantityCount == 1);
     711        ASSERT(term.atom.quantityMaxCount == 1);
    712712
    713713        BackTrackInfoParenthesesOnce* backTrack = reinterpret_cast<BackTrackInfoParenthesesOnce*>(context->frame + term.frameLocation);
    … …  
    739739    {
    740740        ASSERT(term.type == ByteTerm::TypeParenthesesSubpatternOnceEnd);
    741         ASSERT(term.atom.quantityCount == 1);
     741        ASSERT(term.atom.quantityMaxCount == 1);
    742742
    743743        if (term.capture()) {
    … …  
    756756    {
    757757        ASSERT(term.type == ByteTerm::TypeParenthesesSubpatternOnceBegin);
    758         ASSERT(term.atom.quantityCount == 1);
     758        ASSERT(term.atom.quantityMaxCount == 1);
    759759
    760760        BackTrackInfoParenthesesOnce* backTrack = reinterpret_cast<BackTrackInfoParenthesesOnce*>(context->frame + term.frameLocation);
    … …  
    786786    {
    787787        ASSERT(term.type == ByteTerm::TypeParenthesesSubpatternOnceEnd);
    788         ASSERT(term.atom.quantityCount == 1);
     788        ASSERT(term.atom.quantityMaxCount == 1);
    789789
    790790        BackTrackInfoParenthesesOnce* backTrack = reinterpret_cast<BackTrackInfoParenthesesOnce*>(context->frame + term.frameLocation);
    … …  
    824824        ASSERT(term.type == ByteTerm::TypeParenthesesSubpatternTerminalBegin);
    825825        ASSERT(term.atom.quantityType == QuantifierGreedy);
    826         ASSERT(term.atom.quantityCount == quantifyInfinite);
     826        ASSERT(term.atom.quantityMaxCount == quantifyInfinite);
    827827        ASSERT(!term.capture());
    828828
    … …  
    850850        ASSERT(term.type == ByteTerm::TypeParenthesesSubpatternTerminalBegin);
    851851        ASSERT(term.atom.quantityType == QuantifierGreedy);
    852         ASSERT(term.atom.quantityCount == quantifyInfinite);
     852        ASSERT(term.atom.quantityMaxCount == quantifyInfinite);
    853853        ASSERT(!term.capture());
    854854
    … …  
    870870    {
    871871        ASSERT(term.type == ByteTerm::TypeParentheticalAssertionBegin);
    872         ASSERT(term.atom.quantityCount == 1);
     872        ASSERT(term.atom.quantityMaxCount == 1);
    873873
    874874        BackTrackInfoParentheticalAssertion* backTrack = reinterpret_cast<BackTrackInfoParentheticalAssertion*>(context->frame + term.frameLocation);
    … …  
    881881    {
    882882        ASSERT(term.type == ByteTerm::TypeParentheticalAssertionEnd);
    883         ASSERT(term.atom.quantityCount == 1);
     883        ASSERT(term.atom.quantityMaxCount == 1);
    884884
    885885        BackTrackInfoParentheticalAssertion* backTrack = reinterpret_cast<BackTrackInfoParentheticalAssertion*>(context->frame + term.frameLocation);
    … …  
    899899    {
    900900        ASSERT(term.type == ByteTerm::TypeParentheticalAssertionBegin);
    901         ASSERT(term.atom.quantityCount == 1);
     901        ASSERT(term.atom.quantityMaxCount == 1);
    902902
    903903        // We've failed to match parens; if they are inverted, this is win!
    … …  
    913913    {
    914914        ASSERT(term.type == ByteTerm::TypeParentheticalAssertionEnd);
    915         ASSERT(term.atom.quantityCount == 1);
     915        ASSERT(term.atom.quantityMaxCount == 1);
    916916
    917917        BackTrackInfoParentheticalAssertion* backTrack = reinterpret_cast<BackTrackInfoParentheticalAssertion*>(context->frame + term.frameLocation);
    … …  
    933933        backTrack->lastContext = 0;
    934934
    935         switch (term.atom.quantityType) {
    936         case QuantifierFixedCount: {
     935        ASSERT(term.atom.quantityType != QuantifierFixedCount || term.atom.quantityMinCount == term.atom.quantityMaxCount);
     936
     937        unsigned minimumMatchCount = term.atom.quantityMinCount;
     938        JSRegExpResult fixedMatchResult;
     939
     940        // Handle fixed matches and the minimum part of a variable length match.
     941        if (minimumMatchCount) {
    937942            // While we haven't yet reached our fixed limit,
    938             while (backTrack->matchAmount < term.atom.quantityCount) {
     943            while (backTrack->matchAmount < minimumMatchCount) {
    939944                // Try to do a match, and it it succeeds, add it to the list.
    940945                ParenthesesDisjunctionContext* context = allocParenthesesDisjunctionContext(disjunctionBody, output, term);
    941                 JSRegExpResult result = matchDisjunction(disjunctionBody, context->getDisjunctionContext(term));
    942                 if (result == JSRegExpMatch)
     946                fixedMatchResult = matchDisjunction(disjunctionBody, context->getDisjunctionContext(term));
     947                if (fixedMatchResult == JSRegExpMatch)
    943948                    appendParenthesesDisjunctionContext(backTrack, context);
    944949                else {
    … …  
    946951                    resetMatches(term, context);
    947952                    freeParenthesesDisjunctionContext(context);
    948 
    949                     if (result != JSRegExpNoMatch)
    950                         return result;
     953                   
     954                    if (fixedMatchResult != JSRegExpNoMatch)
     955                        return fixedMatchResult;
    951956                    JSRegExpResult backtrackResult = parenthesesDoBacktrack(term, backTrack);
    952957                    if (backtrackResult != JSRegExpMatch)
    … …  
    955960            }
    956961
    957             ASSERT(backTrack->matchAmount == term.atom.quantityCount);
    958962            ParenthesesDisjunctionContext* context = backTrack->lastContext;
    959963            recordParenthesesMatch(term, context);
     964        }
     965
     966        switch (term.atom.quantityType) {
     967        case QuantifierFixedCount: {
     968            ASSERT(backTrack->matchAmount == term.atom.quantityMaxCount);
    960969            return JSRegExpMatch;
    961970        }
    962971
    963972        case QuantifierGreedy: {
    964             while (backTrack->matchAmount < term.atom.quantityCount) {
     973            while (backTrack->matchAmount < term.atom.quantityMaxCount) {
    965974                ParenthesesDisjunctionContext* context = allocParenthesesDisjunctionContext(disjunctionBody, output, term);
    966975                JSRegExpResult result = matchNonZeroDisjunction(disjunctionBody, context->getDisjunctionContext(term));
    … …  
    10121021        switch (term.atom.quantityType) {
    10131022        case QuantifierFixedCount: {
    1014             ASSERT(backTrack->matchAmount == term.atom.quantityCount);
     1023            ASSERT(backTrack->matchAmount == term.atom.quantityMaxCount);
    10151024
    10161025            ParenthesesDisjunctionContext* context = 0;
    … …  
    10211030
    10221031            // While we haven't yet reached our fixed limit,
    1023             while (backTrack->matchAmount < term.atom.quantityCount) {
     1032            while (backTrack->matchAmount < term.atom.quantityMaxCount) {
    10241033                // Try to do a match, and it it succeeds, add it to the list.
    10251034                context = allocParenthesesDisjunctionContext(disjunctionBody, output, term);
    … …  
    10411050            }
    10421051
    1043             ASSERT(backTrack->matchAmount == term.atom.quantityCount);
     1052            ASSERT(backTrack->matchAmount == term.atom.quantityMaxCount);
    10441053            context = backTrack->lastContext;
    10451054            recordParenthesesMatch(term, context);
    … …  
    10541063            JSRegExpResult result = matchNonZeroDisjunction(disjunctionBody, context->getDisjunctionContext(term), true);
    10551064            if (result == JSRegExpMatch) {
    1056                 while (backTrack->matchAmount < term.atom.quantityCount) {
     1065                while (backTrack->matchAmount < term.atom.quantityMaxCount) {
    10571066                    ParenthesesDisjunctionContext* context = allocParenthesesDisjunctionContext(disjunctionBody, output, term);
    10581067                    JSRegExpResult parenthesesResult = matchNonZeroDisjunction(disjunctionBody, context->getDisjunctionContext(term));
    … …  
    10871096        case QuantifierNonGreedy: {
    10881097            // If we've not reached the limit, try to add one more match.
    1089             if (backTrack->matchAmount < term.atom.quantityCount) {
     1098            if (backTrack->matchAmount < term.atom.quantityMaxCount) {
    10901099                ParenthesesDisjunctionContext* context = allocParenthesesDisjunctionContext(disjunctionBody, output, term);
    10911100                JSRegExpResult result = matchNonZeroDisjunction(disjunctionBody, context->getDisjunctionContext(term));
    … …  
    12241233            if (unicode) {
    12251234                if (!U_IS_BMP(currentTerm().atom.patternCharacter)) {
    1226                     for (unsigned matchAmount = 0; matchAmount < currentTerm().atom.quantityCount; ++matchAmount) {
     1235                    for (unsigned matchAmount = 0; matchAmount < currentTerm().atom.quantityMaxCount; ++matchAmount) {
    12271236                        if (!checkSurrogatePair(currentTerm().atom.patternCharacter, currentTerm().inputPosition - 2 * matchAmount)) {
    12281237                            BACKTRACK();
    … …  
    12341243            unsigned position = input.getPos(); // May need to back out reading a surrogate pair.
    12351244
    1236             for (unsigned matchAmount = 0; matchAmount < currentTerm().atom.quantityCount; ++matchAmount) {
     1245            for (unsigned matchAmount = 0; matchAmount < currentTerm().atom.quantityMaxCount; ++matchAmount) {
    12371246                if (!checkCharacter(currentTerm().atom.patternCharacter, currentTerm().inputPosition - matchAmount)) {
    12381247                    input.setPos(position);
    … …  
    12461255            unsigned matchAmount = 0;
    12471256            unsigned position = input.getPos(); // May need to back out reading a surrogate pair.
    1248             while ((matchAmount < currentTerm().atom.quantityCount) && input.checkInput(1)) {
     1257            while ((matchAmount < currentTerm().atom.quantityMaxCount) && input.checkInput(1)) {
    12491258                if (!checkCharacter(currentTerm().atom.patternCharacter, currentTerm().inputPosition + 1)) {
    12501259                    input.setPos(position);
    … …  
    12731282                unsigned position = input.getPos(); // May need to back out reading a surrogate pair.
    12741283               
    1275                 for (unsigned matchAmount = 0; matchAmount < currentTerm().atom.quantityCount; ++matchAmount) {
     1284                for (unsigned matchAmount = 0; matchAmount < currentTerm().atom.quantityMaxCount; ++matchAmount) {
    12761285                    if (!checkCasedCharacter(currentTerm().atom.casedCharacter.lo, currentTerm().atom.casedCharacter.hi, currentTerm().inputPosition - matchAmount)) {
    12771286                        input.setPos(position);
    … …  
    12821291            }
    12831292
    1284             for (unsigned matchAmount = 0; matchAmount < currentTerm().atom.quantityCount; ++matchAmount) {
     1293            for (unsigned matchAmount = 0; matchAmount < currentTerm().atom.quantityMaxCount; ++matchAmount) {
    12851294                if (!checkCasedCharacter(currentTerm().atom.casedCharacter.lo, currentTerm().atom.casedCharacter.hi, currentTerm().inputPosition - matchAmount))
    12861295                    BACKTRACK();
    … …  
    12951304
    12961305            unsigned matchAmount = 0;
    1297             while ((matchAmount < currentTerm().atom.quantityCount) && input.checkInput(1)) {
     1306            while ((matchAmount < currentTerm().atom.quantityMaxCount) && input.checkInput(1)) {
    12981307                if (!checkCasedCharacter(currentTerm().atom.casedCharacter.lo, currentTerm().atom.casedCharacter.hi, currentTerm().inputPosition + 1)) {
    12991308                    input.uncheckInput(1);
    … …  
    16231632    }
    16241633
    1625     void atomPatternCharacter(UChar32 ch, unsigned inputPosition, unsigned frameLocation, Checked<unsigned> quantityCount, QuantifierType quantityType)
     1634    void atomPatternCharacter(UChar32 ch, unsigned inputPosition, unsigned frameLocation, Checked<unsigned> quantityMaxCount, QuantifierType quantityType)
    16261635    {
    16271636        if (m_pattern.ignoreCase()) {
    … …  
    16301639
    16311640            if (lo != hi) {
    1632                 m_bodyDisjunction->terms.append(ByteTerm(lo, hi, inputPosition, frameLocation, quantityCount, quantityType));
     1641                m_bodyDisjunction->terms.append(ByteTerm(lo, hi, inputPosition, frameLocation, quantityMaxCount, quantityType));
    16331642                return;
    16341643            }
    16351644        }
    16361645
    1637         m_bodyDisjunction->terms.append(ByteTerm(ch, inputPosition, frameLocation, quantityCount, quantityType));
    1638     }
    1639 
    1640     void atomCharacterClass(CharacterClass* characterClass, bool invert, unsigned inputPosition, unsigned frameLocation, Checked<unsigned> quantityCount, QuantifierType quantityType)
     1646        m_bodyDisjunction->terms.append(ByteTerm(ch, inputPosition, frameLocation, quantityMaxCount, quantityType));
     1647    }
     1648
     1649    void atomCharacterClass(CharacterClass* characterClass, bool invert, unsigned inputPosition, unsigned frameLocation, Checked<unsigned> quantityMaxCount, QuantifierType quantityType)
    16411650    {
    16421651        m_bodyDisjunction->terms.append(ByteTerm(characterClass, invert, inputPosition));
    16431652
    1644         m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].atom.quantityCount = quantityCount.unsafeGet();
     1653        m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].atom.quantityMaxCount = quantityMaxCount.unsafeGet();
    16451654        m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].atom.quantityType = quantityType;
    16461655        m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].frameLocation = frameLocation;
    16471656    }
    16481657
    1649     void atomBackReference(unsigned subpatternId, unsigned inputPosition, unsigned frameLocation, Checked<unsigned> quantityCount, QuantifierType quantityType)
     1658    void atomBackReference(unsigned subpatternId, unsigned inputPosition, unsigned frameLocation, Checked<unsigned> quantityMaxCount, QuantifierType quantityType)
    16501659    {
    16511660        ASSERT(subpatternId);
    … …  
    16531662        m_bodyDisjunction->terms.append(ByteTerm::BackReference(subpatternId, inputPosition));
    16541663
    1655         m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].atom.quantityCount = quantityCount.unsafeGet();
     1664        m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].atom.quantityMaxCount = quantityMaxCount.unsafeGet();
    16561665        m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].atom.quantityType = quantityType;
    16571666        m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].frameLocation = frameLocation;
    … …  
    17141723    }
    17151724
    1716     void atomParentheticalAssertionEnd(unsigned inputPosition, unsigned frameLocation, Checked<unsigned> quantityCount, QuantifierType quantityType)
     1725    void atomParentheticalAssertionEnd(unsigned inputPosition, unsigned frameLocation, Checked<unsigned> quantityMaxCount, QuantifierType quantityType)
    17171726    {
    17181727        unsigned beginTerm = popParenthesesStack();
    … …  
    17301739        m_bodyDisjunction->terms[endTerm].frameLocation = frameLocation;
    17311740
    1732         m_bodyDisjunction->terms[beginTerm].atom.quantityCount = quantityCount.unsafeGet();
     1741        m_bodyDisjunction->terms[beginTerm].atom.quantityMaxCount = quantityMaxCount.unsafeGet();
    17331742        m_bodyDisjunction->terms[beginTerm].atom.quantityType = quantityType;
    1734         m_bodyDisjunction->terms[endTerm].atom.quantityCount = quantityCount.unsafeGet();
     1743        m_bodyDisjunction->terms[endTerm].atom.quantityMaxCount = quantityMaxCount.unsafeGet();
    17351744        m_bodyDisjunction->terms[endTerm].atom.quantityType = quantityType;
    17361745    }
    … …  
    18121821    }
    18131822
    1814     void atomParenthesesSubpatternEnd(unsigned lastSubpatternId, unsigned inputPosition, unsigned frameLocation, Checked<unsigned> quantityCount, QuantifierType quantityType, unsigned callFrameSize = 0)
     1823    void atomParenthesesSubpatternEnd(unsigned lastSubpatternId, unsigned inputPosition, unsigned frameLocation, Checked<unsigned> quantityMinCount, Checked<unsigned> quantityMaxCount, QuantifierType quantityType, unsigned callFrameSize = 0)
    18151824    {
    18161825        unsigned beginTerm = popParenthesesStack();
    … …  
    18411850        m_allParenthesesInfo.append(WTFMove(parenthesesDisjunction));
    18421851
    1843         m_bodyDisjunction->terms[beginTerm].atom.quantityCount = quantityCount.unsafeGet();
     1852        m_bodyDisjunction->terms[beginTerm].atom.quantityMinCount = quantityMinCount.unsafeGet();
     1853        m_bodyDisjunction->terms[beginTerm].atom.quantityMaxCount = quantityMaxCount.unsafeGet();
    18441854        m_bodyDisjunction->terms[beginTerm].atom.quantityType = quantityType;
    18451855        m_bodyDisjunction->terms[beginTerm].frameLocation = frameLocation;
    18461856    }
    18471857
    1848     void atomParenthesesOnceEnd(unsigned inputPosition, unsigned frameLocation, Checked<unsigned> quantityCount, QuantifierType quantityType)
     1858    void atomParenthesesOnceEnd(unsigned inputPosition, unsigned frameLocation, Checked<unsigned> quantityMinCount, Checked<unsigned> quantityMaxCount, QuantifierType quantityType)
    18491859    {
    18501860        unsigned beginTerm = popParenthesesStack();
    … …  
    18621872        m_bodyDisjunction->terms[endTerm].frameLocation = frameLocation;
    18631873
    1864         m_bodyDisjunction->terms[beginTerm].atom.quantityCount = quantityCount.unsafeGet();
     1874        m_bodyDisjunction->terms[beginTerm].atom.quantityMinCount = quantityMinCount.unsafeGet();
     1875        m_bodyDisjunction->terms[beginTerm].atom.quantityMaxCount = quantityMaxCount.unsafeGet();
    18651876        m_bodyDisjunction->terms[beginTerm].atom.quantityType = quantityType;
    1866         m_bodyDisjunction->terms[endTerm].atom.quantityCount = quantityCount.unsafeGet();
     1877        m_bodyDisjunction->terms[endTerm].atom.quantityMinCount = quantityMinCount.unsafeGet();
     1878        m_bodyDisjunction->terms[endTerm].atom.quantityMaxCount = quantityMaxCount.unsafeGet();
    18671879        m_bodyDisjunction->terms[endTerm].atom.quantityType = quantityType;
    18681880    }
    18691881
    1870     void atomParenthesesTerminalEnd(unsigned inputPosition, unsigned frameLocation, Checked<unsigned> quantityCount, QuantifierType quantityType)
     1882    void atomParenthesesTerminalEnd(unsigned inputPosition, unsigned frameLocation, Checked<unsigned> quantityMinCount, Checked<unsigned> quantityMaxCount, QuantifierType quantityType)
    18711883    {
    18721884        unsigned beginTerm = popParenthesesStack();
    … …  
    18841896        m_bodyDisjunction->terms[endTerm].frameLocation = frameLocation;
    18851897
    1886         m_bodyDisjunction->terms[beginTerm].atom.quantityCount = quantityCount.unsafeGet();
     1898        m_bodyDisjunction->terms[beginTerm].atom.quantityMinCount = quantityMinCount.unsafeGet();
     1899        m_bodyDisjunction->terms[beginTerm].atom.quantityMaxCount = quantityMaxCount.unsafeGet();
    18871900        m_bodyDisjunction->terms[beginTerm].atom.quantityType = quantityType;
    1888         m_bodyDisjunction->terms[endTerm].atom.quantityCount = quantityCount.unsafeGet();
     1901        m_bodyDisjunction->terms[endTerm].atom.quantityMinCount = quantityMinCount.unsafeGet();
     1902        m_bodyDisjunction->terms[endTerm].atom.quantityMaxCount = quantityMaxCount.unsafeGet();
    18891903        m_bodyDisjunction->terms[endTerm].atom.quantityType = quantityType;
    18901904    }
    … …  
    19591973
    19601974                case PatternTerm::TypePatternCharacter:
    1961                     atomPatternCharacter(term.patternCharacter, currentCountAlreadyChecked - term.inputPosition, term.frameLocation, term.quantityCount, term.quantityType);
     1975                    atomPatternCharacter(term.patternCharacter, currentCountAlreadyChecked - term.inputPosition, term.frameLocation, term.quantityMaxCount, term.quantityType);
    19621976                    break;
    19631977
    19641978                case PatternTerm::TypeCharacterClass:
    1965                     atomCharacterClass(term.characterClass, term.invert(), currentCountAlreadyChecked- term.inputPosition, term.frameLocation, term.quantityCount, term.quantityType);
     1979                    atomCharacterClass(term.characterClass, term.invert(), currentCountAlreadyChecked- term.inputPosition, term.frameLocation, term.quantityMaxCount, term.quantityType);
    19661980                    break;
    19671981
    19681982                case PatternTerm::TypeBackReference:
    1969                     atomBackReference(term.backReferenceSubpatternId, currentCountAlreadyChecked - term.inputPosition, term.frameLocation, term.quantityCount, term.quantityType);
     1983                    atomBackReference(term.backReferenceSubpatternId, currentCountAlreadyChecked - term.inputPosition, term.frameLocation, term.quantityMaxCount, term.quantityType);
    19701984                        break;
    19711985
    … …  
    19751989                case PatternTerm::TypeParenthesesSubpattern: {
    19761990                    unsigned disjunctionAlreadyCheckedCount = 0;
    1977                     if (term.quantityCount == 1 && !term.parentheses.isCopy) {
     1991                    if (term.quantityMaxCount == 1 && !term.parentheses.isCopy) {
    19781992                        unsigned alternativeFrameLocation = term.frameLocation;
    19791993                        // For QuantifierFixedCount we pre-check the minimum size; for greedy/non-greedy we reserve a slot in the frame.
    … …  
    19862000                        atomParenthesesOnceBegin(term.parentheses.subpatternId, term.capture(), disjunctionAlreadyCheckedCount + delegateEndInputOffset, term.frameLocation, alternativeFrameLocation);
    19872001                        emitDisjunction(term.parentheses.disjunction, currentCountAlreadyChecked, disjunctionAlreadyCheckedCount);
    1988                         atomParenthesesOnceEnd(delegateEndInputOffset, term.frameLocation, term.quantityCount, term.quantityType);
     2002                        atomParenthesesOnceEnd(delegateEndInputOffset, term.frameLocation, term.quantityMinCount, term.quantityMaxCount, term.quantityType);
    19892003                    } else if (term.parentheses.isTerminal) {
    19902004                        ASSERT(currentCountAlreadyChecked >= term.inputPosition);
    … …  
    19922006                        atomParenthesesTerminalBegin(term.parentheses.subpatternId, term.capture(), disjunctionAlreadyCheckedCount + delegateEndInputOffset, term.frameLocation, term.frameLocation + YarrStackSpaceForBackTrackInfoParenthesesOnce);
    19932007                        emitDisjunction(term.parentheses.disjunction, currentCountAlreadyChecked, disjunctionAlreadyCheckedCount);
    1994                         atomParenthesesTerminalEnd(delegateEndInputOffset, term.frameLocation, term.quantityCount, term.quantityType);
     2008                        atomParenthesesTerminalEnd(delegateEndInputOffset, term.frameLocation, term.quantityMinCount, term.quantityMaxCount, term.quantityType);
    19952009                    } else {
    19962010                        ASSERT(currentCountAlreadyChecked >= term.inputPosition);
    … …  
    19982012                        atomParenthesesSubpatternBegin(term.parentheses.subpatternId, term.capture(), disjunctionAlreadyCheckedCount + delegateEndInputOffset, term.frameLocation, 0);
    19992013                        emitDisjunction(term.parentheses.disjunction, currentCountAlreadyChecked, 0);
    2000                         atomParenthesesSubpatternEnd(term.parentheses.lastSubpatternId, delegateEndInputOffset, term.frameLocation, term.quantityCount, term.quantityType, term.parentheses.disjunction->m_callFrameSize);
     2014                        atomParenthesesSubpatternEnd(term.parentheses.lastSubpatternId, delegateEndInputOffset, term.frameLocation, term.quantityMinCount, term.quantityMaxCount, term.quantityType, term.parentheses.disjunction->m_callFrameSize);
    20012015                    }
    20022016                    break;
    … …  
    20172031                    atomParentheticalAssertionBegin(term.parentheses.subpatternId, term.invert(), term.frameLocation, alternativeFrameLocation);
    20182032                    emitDisjunction(term.parentheses.disjunction, currentCountAlreadyChecked, positiveInputOffset - uncheckAmount);
    2019                     atomParentheticalAssertionEnd(0, term.frameLocation, term.quantityCount, term.quantityType);
     2033                    atomParentheticalAssertionEnd(0, term.frameLocation, term.quantityMaxCount, term.quantityType);
    20202034                    if (uncheckAmount) {
    20212035                        checkInput(uncheckAmount);

  • trunk/Source/JavaScriptCore/yarr/YarrInterpreter.h

    r208761 r210837  
    8888            };
    8989            QuantifierType quantityType;
    90             unsigned quantityCount;
     90            unsigned quantityMinCount;
     91            unsigned quantityMaxCount;
    9192        } atom;
    9293        struct {
    … …  
    111112        , m_invert(false)
    112113    {
     114        atom.patternCharacter = ch;
     115        atom.quantityType = quantityType;
     116        atom.quantityMinCount = quantityCount.unsafeGet();
     117        atom.quantityMaxCount = quantityCount.unsafeGet();
     118        inputPosition = inputPos;
     119
    113120        switch (quantityType) {
    114121        case QuantifierFixedCount:
    … …  
    122129            break;
    123130        }
    124 
    125         atom.patternCharacter = ch;
    126         atom.quantityType = quantityType;
    127         atom.quantityCount = quantityCount.unsafeGet();
    128         inputPosition = inputPos;
    129131    }
    130132
    … …  
    149151        atom.casedCharacter.hi = hi;
    150152        atom.quantityType = quantityType;
    151         atom.quantityCount = quantityCount.unsafeGet();
     153        atom.quantityMinCount = quantityCount.unsafeGet();
     154        atom.quantityMaxCount = quantityCount.unsafeGet();
    152155        inputPosition = inputPos;
    153156    }
    … …  
    160163        atom.characterClass = characterClass;
    161164        atom.quantityType = QuantifierFixedCount;
    162         atom.quantityCount = 1;
     165        atom.quantityMinCount = 1;
     166        atom.quantityMaxCount = 1;
    163167        inputPosition = inputPos;
    164168    }
    … …  
    172176        atom.parenthesesDisjunction = parenthesesInfo;
    173177        atom.quantityType = QuantifierFixedCount;
    174         atom.quantityCount = 1;
     178        atom.quantityMinCount = 1;
     179        atom.quantityMaxCount = 1;
    175180        inputPosition = inputPos;
    176181    }
    … …  
    182187    {
    183188        atom.quantityType = QuantifierFixedCount;
    184         atom.quantityCount = 1;
     189        atom.quantityMinCount = 1;
     190        atom.quantityMaxCount = 1;
    185191    }
    186192
    … …  
    192198        atom.subpatternId = subpatternId;
    193199        atom.quantityType = QuantifierFixedCount;
    194         atom.quantityCount = 1;
     200        atom.quantityMinCount = 1;
     201        atom.quantityMaxCount = 1;
    195202        inputPosition = inputPos;
    196203    }

  • trunk/Source/JavaScriptCore/yarr/YarrJIT.cpp

    r210232 r210837  
    454454        OpSimpleNestedAlternativeNext,
    455455        OpSimpleNestedAlternativeEnd,
    456         // Used to wrap 'Once' subpattern matches (quantityCount == 1).
     456        // Used to wrap 'Once' subpattern matches (quantityMaxCount == 1).
    457457        OpParenthesesSubpatternOnceBegin,
    458458        OpParenthesesSubpatternOnceEnd,
    … …  
    831831            if (nextTerm->type != PatternTerm::TypePatternCharacter
    832832                || nextTerm->quantityType != QuantifierFixedCount
    833                 || nextTerm->quantityCount != 1
     833                || nextTerm->quantityMaxCount != 1
    834834                || nextTerm->inputPosition != (startTermPosition + numberCharacters))
    835835                break;
    … …  
    914914
    915915        move(index, countRegister);
    916         sub32(Imm32(term->quantityCount.unsafeGet()), countRegister);
     916        sub32(Imm32(term->quantityMaxCount.unsafeGet()), countRegister);
    917917
    918918        Label loop(this);
    919         readCharacter(m_checkedOffset - term->inputPosition - term->quantityCount, character, countRegister);
     919        readCharacter(m_checkedOffset - term->inputPosition - term->quantityMaxCount, character, countRegister);
    920920        // For case-insesitive compares, non-ascii characters that have different
    921921        // upper & lower case representations are converted to a character class.
    … …  
    955955            add32(TrustedImm32(1), countRegister);
    956956            add32(TrustedImm32(1), index);
    957             if (term->quantityCount == quantifyInfinite)
     957            if (term->quantityMaxCount == quantifyInfinite)
    958958                jump(loop);
    959959            else
    960                 branch32(NotEqual, countRegister, Imm32(term->quantityCount.unsafeGet())).linkTo(loop, this);
     960                branch32(NotEqual, countRegister, Imm32(term->quantityMaxCount.unsafeGet())).linkTo(loop, this);
    961961
    962962            failures.link(this);
    … …  
    10101010            JumpList nonGreedyFailures;
    10111011            nonGreedyFailures.append(atEndOfInput());
    1012             if (term->quantityCount != quantifyInfinite)
    1013                 nonGreedyFailures.append(branch32(Equal, countRegister, Imm32(term->quantityCount.unsafeGet())));
     1012            if (term->quantityMaxCount != quantifyInfinite)
     1013                nonGreedyFailures.append(branch32(Equal, countRegister, Imm32(term->quantityMaxCount.unsafeGet())));
    10141014            nonGreedyFailures.append(jumpIfCharNotEquals(ch, m_checkedOffset - term->inputPosition, character));
    10151015
    … …  
    10571057
    10581058        move(index, countRegister);
    1059         sub32(Imm32(term->quantityCount.unsafeGet()), countRegister);
     1059        sub32(Imm32(term->quantityMaxCount.unsafeGet()), countRegister);
    10601060
    10611061        Label loop(this);
    10621062        JumpList matchDest;
    1063         readCharacter(m_checkedOffset - term->inputPosition - term->quantityCount, character, countRegister);
     1063        readCharacter(m_checkedOffset - term->inputPosition - term->quantityMaxCount, character, countRegister);
    10641064        matchCharacterClass(character, matchDest, term->characterClass);
    10651065
    … …  
    11061106        add32(TrustedImm32(1), countRegister);
    11071107        add32(TrustedImm32(1), index);
    1108         if (term->quantityCount != quantifyInfinite) {
    1109             branch32(NotEqual, countRegister, Imm32(term->quantityCount.unsafeGet())).linkTo(loop, this);
     1108        if (term->quantityMaxCount != quantifyInfinite) {
     1109            branch32(NotEqual, countRegister, Imm32(term->quantityMaxCount.unsafeGet())).linkTo(loop, this);
    11101110            failures.append(jump());
    11111111        } else
    … …  
    11591159
    11601160        nonGreedyFailures.append(atEndOfInput());
    1161         nonGreedyFailures.append(branch32(Equal, countRegister, Imm32(term->quantityCount.unsafeGet())));
     1161        nonGreedyFailures.append(branch32(Equal, countRegister, Imm32(term->quantityMaxCount.unsafeGet())));
    11621162
    11631163        JumpList matchDest;
    … …  
    12551255            switch (term->quantityType) {
    12561256            case QuantifierFixedCount:
    1257                 if (term->quantityCount == 1)
     1257                if (term->quantityMaxCount == 1)
    12581258                    generatePatternCharacterOnce(opIndex);
    12591259                else
    … …  
    12721272            switch (term->quantityType) {
    12731273            case QuantifierFixedCount:
    1274                 if (term->quantityCount == 1)
     1274                if (term->quantityMaxCount == 1)
    12751275                    generateCharacterClassOnce(opIndex);
    12761276                else
    … …  
    13211321            switch (term->quantityType) {
    13221322            case QuantifierFixedCount:
    1323                 if (term->quantityCount == 1)
     1323                if (term->quantityMaxCount == 1)
    13241324                    backtrackPatternCharacterOnce(opIndex);
    13251325                else
    … …  
    13381338            switch (term->quantityType) {
    13391339            case QuantifierFixedCount:
    1340                 if (term->quantityCount == 1)
     1340                if (term->quantityMaxCount == 1)
    13411341                    backtrackCharacterClassOnce(opIndex);
    13421342                else
    … …  
    16071607                unsigned parenthesesFrameLocation = term->frameLocation;
    16081608                const RegisterID indexTemporary = regT0;
    1609                 ASSERT(term->quantityCount == 1);
     1609                ASSERT(term->quantityMaxCount == 1);
    16101610
    16111611                // Upon entry to a Greedy quantified set of parenthese store the index.
    … …  
    16541654                PatternTerm* term = op.m_term;
    16551655                const RegisterID indexTemporary = regT0;
    1656                 ASSERT(term->quantityCount == 1);
     1656                ASSERT(term->quantityMaxCount == 1);
    16571657
    16581658                // Runtime ASSERT to make sure that the nested alternative handled the
    … …  
    16971697                PatternTerm* term = op.m_term;
    16981698                ASSERT(term->quantityType == QuantifierGreedy);
    1699                 ASSERT(term->quantityCount == quantifyInfinite);
     1699                ASSERT(term->quantityMaxCount == quantifyInfinite);
    17001700                ASSERT(!term->capture());
    17011701
    … …  
    21812181            case OpParenthesesSubpatternOnceBegin: {
    21822182                PatternTerm* term = op.m_term;
    2183                 ASSERT(term->quantityCount == 1);
     2183                ASSERT(term->quantityMaxCount == 1);
    21842184
    21852185                // We only need to backtrack to thispoint if capturing or greedy.
    … …  
    23202320    // of a set of alternatives wrapped in an outer set of nodes for
    23212321    // the parentheses.
    2322     // Supported types of parentheses are 'Once' (quantityCount == 1)
     2322    // Supported types of parentheses are 'Once' (quantityMaxCount == 1)
    23232323    // and 'Terminal' (non-capturing parentheses quantified as greedy
    23242324    // and infinite).
    … …  
    23412341        // need to restore the capture from the first subpattern upon a
    23422342        // failure in the second.
    2343         if (term->quantityCount == 1 && !term->parentheses.isCopy) {
     2343        if (term->quantityMinCount && term->quantityMinCount != term->quantityMaxCount) {
     2344            m_shouldFallBack = true;
     2345            return;
     2346        } if (term->quantityMaxCount == 1 && !term->parentheses.isCopy) {
    23442347            // Select the 'Once' nodes.
    23452348            parenthesesBeginOpCode = OpParenthesesSubpatternOnceBegin;

  • trunk/Source/JavaScriptCore/yarr/YarrPattern.cpp

    r205937 r210837  
    523523        PatternTerm termCopy = term;
    524524        termCopy.parentheses.disjunction = copyDisjunction(termCopy.parentheses.disjunction, filterStartsWithBOL);
     525        m_pattern.m_hasCopiedParenSubexpressions = true;
    525526        return termCopy;
    526527    }
    … …  
    538539        PatternTerm& term = m_alternative->lastTerm();
    539540        ASSERT(term.type > PatternTerm::TypeAssertionWordBoundary);
    540         ASSERT((term.quantityCount == 1) && (term.quantityType == QuantifierFixedCount));
     541        ASSERT(term.quantityMinCount == 1 && term.quantityMaxCount == 1 && term.quantityType == QuantifierFixedCount);
    541542
    542543        if (term.type == PatternTerm::TypeParentheticalAssertion) {
    … …  
    560561        }
    561562
    562         if (min == 0)
    563             term.quantify(max, greedy   ? QuantifierGreedy : QuantifierNonGreedy);
    564         else if (min == max)
    565             term.quantify(min, QuantifierFixedCount);
     563        if (min == max)
     564            term.quantify(min, max, QuantifierFixedCount);
     565        else if (!min || (term.type == PatternTerm::TypeParenthesesSubpattern && m_pattern.m_hasCopiedParenSubexpressions))
     566            term.quantify(min, max, greedy ? QuantifierGreedy : QuantifierNonGreedy);
    566567        else {
    567             term.quantify(min, QuantifierFixedCount);
     568            term.quantify(min, min, QuantifierFixedCount);
    568569            m_alternative->m_terms.append(copyTerm(term));
    569570            // NOTE: this term is interesting from an analysis perspective, in that it can be ignored.....
    … …  
    615616                    alternative->m_hasFixedSize = false;
    616617                } else if (m_pattern.unicode()) {
    617                     currentInputPosition += U16_LENGTH(term.patternCharacter) * term.quantityCount;
     618                    currentInputPosition += U16_LENGTH(term.patternCharacter) * term.quantityMaxCount;
    618619                } else
    619                     currentInputPosition += term.quantityCount;
     620                    currentInputPosition += term.quantityMaxCount;
    620621                break;
    621622
    … …  
    629630                    term.frameLocation = currentCallFrameSize;
    630631                    currentCallFrameSize += YarrStackSpaceForBackTrackInfoCharacterClass;
    631                     currentInputPosition += term.quantityCount;
     632                    currentInputPosition += term.quantityMaxCount;
    632633                    alternative->m_hasFixedSize = false;
    633634                } else
    634                     currentInputPosition += term.quantityCount;
     635                    currentInputPosition += term.quantityMaxCount;
    635636                break;
    636637
    … …  
    638639                // Note: for fixed once parentheses we will ensure at least the minimum is available; others are on their own.
    639640                term.frameLocation = currentCallFrameSize;
    640                 if (term.quantityCount == 1 && !term.parentheses.isCopy) {
     641                if (term.quantityMaxCount == 1 && !term.parentheses.isCopy) {
    641642                    if (term.quantityType != QuantifierFixedCount)
    642643                        currentCallFrameSize += YarrStackSpaceForBackTrackInfoParenthesesOnce;
    … …  
    755756                if (term.type == PatternTerm::TypeParenthesesSubpattern
    756757                    && term.quantityType == QuantifierGreedy
    757                     && term.quantityCount == quantifyInfinite
     758                    && term.quantityMinCount == 0
     759                    && term.quantityMaxCount == quantifyInfinite
    758760                    && !term.capture())
    759761                    term.parentheses.isTerminal = true;
    … …  
    956958    , m_containsBOL(false)
    957959    , m_containsUnsignedLengthPattern(false)
     960    , m_hasCopiedParenSubexpressions(false)
    958961    , m_flags(flags)
    959962    , m_numSubpatterns(0)

  • trunk/Source/JavaScriptCore/yarr/YarrPattern.h

    r206525 r210837  
    109109    };
    110110    QuantifierType quantityType;
    111     Checked<unsigned> quantityCount;
     111    Checked<unsigned> quantityMinCount;
     112    Checked<unsigned> quantityMaxCount;
    112113    unsigned inputPosition;
    113114    unsigned frameLocation;
    … …  
    120121        patternCharacter = ch;
    121122        quantityType = QuantifierFixedCount;
    122         quantityCount = 1;
     123        quantityMinCount = quantityMaxCount = 1;
    123124    }
    124125
    … …  
    130131        characterClass = charClass;
    131132        quantityType = QuantifierFixedCount;
    132         quantityCount = 1;
     133        quantityMinCount = quantityMaxCount = 1;
    133134    }
    134135
    … …  
    143144        parentheses.isTerminal = false;
    144145        quantityType = QuantifierFixedCount;
    145         quantityCount = 1;
     146        quantityMinCount = quantityMaxCount = 1;
    146147    }
    147148   
    … …  
    152153    {
    153154        quantityType = QuantifierFixedCount;
    154         quantityCount = 1;
     155        quantityMinCount = quantityMaxCount = 1;
    155156    }
    156157
    … …  
    162163        backReferenceSubpatternId = spatternId;
    163164        quantityType = QuantifierFixedCount;
    164         quantityCount = 1;
     165        quantityMinCount = quantityMaxCount = 1;
    165166    }
    166167
    … …  
    173174        anchors.eolAnchor = eolAnchor;
    174175        quantityType = QuantifierFixedCount;
    175         quantityCount = 1;
     176        quantityMinCount = quantityMaxCount = 1;
    176177    }
    177178   
    … …  
    208209    void quantify(unsigned count, QuantifierType type)
    209210    {
    210         quantityCount = count;
     211        quantityMinCount = 0;
     212        quantityMaxCount = count;
     213        quantityType = type;
     214    }
     215
     216    void quantify(unsigned minCount, unsigned maxCount, QuantifierType type)
     217    {
     218        // Currently only Parentheses can specify a non-zero min with a different max.
     219        ASSERT(this->type == TypeParenthesesSubpattern || !minCount || minCount == maxCount);
     220        ASSERT(minCount <= maxCount);
     221        quantityMinCount = minCount;
     222        quantityMaxCount = maxCount;
    211223        quantityType = type;
    212224    }
    … …  
    335347        m_containsBOL = false;
    336348        m_containsUnsignedLengthPattern = false;
     349        m_hasCopiedParenSubexpressions = false;
    337350
    338351        newlineCached = 0;
    … …  
    440453    bool m_containsBackreferences : 1;
    441454    bool m_containsBOL : 1;
    442     bool m_containsUnsignedLengthPattern : 1;
     455    bool m_containsUnsignedLengthPattern : 1;
     456    bool m_hasCopiedParenSubexpressions : 1;
    443457    RegExpFlags m_flags;
    444458    unsigned m_numSubpatterns;
Note: See TracChangeset for help on using the changeset viewer.