Changeset 73866 in webkit


Ignore:
Timestamp:
Dec 11, 2010 7:24:56 PM (13 years ago)
Author:
msaboff@apple.com
Message:

2010-12-10 Michael Saboff <​msaboff@apple.com>

Reviewed by Gavin Barraclough.

REGRESSION Hang inside Yarr::RegexCodeBlock::execute when visiting
bugs.webkit.org
​https://bugs.webkit.org/show_bug.cgi?id=50816

First nested parentheses of the second or greater alternative
where backtracking to the prior parentheses. Changed the default
handling of initial parentheses for all alternatives to go back
to the immediate outer paren.

  • yarr/RegexJIT.cpp: (JSC::Yarr::RegexGenerator::GenerationState::addParenthesesTail): (JSC::Yarr::RegexGenerator::TermGenerationState::TermGenerationState): (JSC::Yarr::RegexGenerator::TermGenerationState::isLastTerm): (JSC::Yarr::RegexGenerator::TermGenerationState::getTermIndex): (JSC::Yarr::RegexGenerator::TermGenerationState::setParenthesesTail): (JSC::Yarr::RegexGenerator::TermGenerationState::getParenthesesTail): (JSC::Yarr::RegexGenerator::ParenthesesTail::ParenthesesTail): (JSC::Yarr::RegexGenerator::ParenthesesTail::processBacktracks): (JSC::Yarr::RegexGenerator::ParenthesesTail::generateCode): (JSC::Yarr::RegexGenerator::generateParenthesesSingle):

2010-12-10 Michael Saboff <​msaboff@apple.com>

Reviewed by Gavin Barraclough.

REGRESSION Hang inside Yarr::RegexCodeBlock::execute when visiting
bugs.webkit.org
​https://bugs.webkit.org/show_bug.cgi?id=50816

New test to verify proper backtracking of alternative nested parens.

  • fast/regex/parentheses-expected.txt:
  • fast/regex/script-tests/parentheses.js:
Location:
trunk
Files:
5 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/ChangeLog

    r73853 r73866  
     12010-12-10  Michael Saboff  <msaboff@apple.com>
     2
     3        Reviewed by Gavin Barraclough.
     4
     5        REGRESSION Hang inside Yarr::RegexCodeBlock::execute when visiting
     6        bugs.webkit.org
     7        https://bugs.webkit.org/show_bug.cgi?id=50816
     8
     9        First nested parentheses of the second or greater alternative
     10        where backtracking to the prior parentheses.  Changed the default
     11        handling of initial parentheses for all alternatives to go back
     12        to the immediate outer paren.
     13
     14        * yarr/RegexJIT.cpp:
     15        (JSC::Yarr::RegexGenerator::GenerationState::addParenthesesTail):
     16        (JSC::Yarr::RegexGenerator::TermGenerationState::TermGenerationState):
     17        (JSC::Yarr::RegexGenerator::TermGenerationState::isLastTerm):
     18        (JSC::Yarr::RegexGenerator::TermGenerationState::getTermIndex):
     19        (JSC::Yarr::RegexGenerator::TermGenerationState::setParenthesesTail):
     20        (JSC::Yarr::RegexGenerator::TermGenerationState::getParenthesesTail):
     21        (JSC::Yarr::RegexGenerator::ParenthesesTail::ParenthesesTail):
     22        (JSC::Yarr::RegexGenerator::ParenthesesTail::processBacktracks):
     23        (JSC::Yarr::RegexGenerator::ParenthesesTail::generateCode):
     24        (JSC::Yarr::RegexGenerator::generateParenthesesSingle):
     25
    1262010-12-11  Patrick Gansterer  <paroga@webkit.org>
    227

  • trunk/JavaScriptCore/yarr/RegexJIT.cpp

    r73640 r73866  
    375375        }
    376376
    377         ParenthesesTail* addParenthesesTail(PatternTerm& term)
    378         {
    379             ParenthesesTail* parenthesesTail = new ParenthesesTail(term, m_parenNestingLevel);
     377        ParenthesesTail* addParenthesesTail(PatternTerm& term, ParenthesesTail* nextOuterParenTail)
     378        {
     379            ParenthesesTail* parenthesesTail = new ParenthesesTail(term, m_parenNestingLevel, nextOuterParenTail);
    380380            m_parenTails.append(parenthesesTail);
    381381            m_parenTailsForIteration.append(parenthesesTail);
    … …  
    767767            : disjunction(disjunction)
    768768            , checkedTotal(checkedTotal)
     769            , m_subParenNum(0)
    769770            , m_linkedBacktrack(0)
     771            , m_parenthesesTail(0)
    770772        {
    771773        }
    … …  
    797799            ASSERT(alternativeValid());
    798800            t = 0;
     801            m_subParenNum = 0;
    799802        }
    800803        bool termValid()
    … …  
    817820            ASSERT(alternativeValid());
    818821            return (t + 1) == alternative()->m_terms.size();
     822        }       
     823        unsigned getSubParenNum()
     824        {
     825            return m_subParenNum++;
    819826        }
    820827        bool isMainDisjunction()
    … …  
    822829            return !disjunction->m_parent;
    823830        }
    824 
     831       
     832        void setParenthesesTail(ParenthesesTail* parenthesesTail)
     833        {
     834            m_parenthesesTail = parenthesesTail;
     835        }
     836
     837        ParenthesesTail* getParenthesesTail()
     838        {
     839            return m_parenthesesTail;
     840        }
     841       
    825842        PatternTerm& lookaheadTerm()
    826843        {
    … …  
    950967        unsigned alt;
    951968        unsigned t;
     969        unsigned m_subParenNum;
    952970        BacktrackDestination m_backtrack;
    953971        BacktrackDestination* m_linkedBacktrack;
     972        ParenthesesTail* m_parenthesesTail;
    954973
    955974    };
    956975
    957976    struct ParenthesesTail {
    958         ParenthesesTail(PatternTerm& term, int nestingLevel)
     977        ParenthesesTail(PatternTerm& term, int nestingLevel, ParenthesesTail* nextOuterParenTail)
    959978            : m_term(term)
    960979            , m_nestingLevel(nestingLevel)
     980            , m_subParenIndex(0)
     981            , m_nextOuterParenTail(nextOuterParenTail)
    961982        {
    962983        }
    … …  
    967988            m_fallThrough = fallThrough;
    968989
     990            m_subParenIndex = state.getSubParenNum();
    969991            parenthesesState.getBacktrackDestination().copyTo(m_parenBacktrack);
    970992            state.chainBacktracks(&m_backtrack);
    … …  
    10241046                    m_backtrack.setLabel(m_backtrackToLabel);
    10251047                    nextBacktrackFallThrough = false;
     1048                } else if (!m_subParenIndex && m_nextOuterParenTail) {
     1049                    // If we don't have a destination and we are the first term of a nested paren, go
     1050                    // back to the outer paren.
     1051                    // There is an optimization if the next outer paren is the next paren to be emitted.
     1052                    // In that case we really want the else clause.
     1053                    m_backtrack.setBacktrackJumpList(&m_nextOuterParenTail->m_withinBacktrackJumps);
     1054                    nextBacktrackFallThrough = false;
    10261055                } else
    10271056                    m_backtrack.setBacktrackJumpList(&jumpsToNext);
    … …  
    10541083                fromPriorBacktrack.link(generator);
    10551084            m_parenBacktrack.linkAlternativeBacktracks(generator);
     1085            m_withinBacktrackJumps.link(generator);           
    10561086
    10571087            if (m_term.capture())
    … …  
    10731103        PatternTerm& m_term;
    10741104        int m_nestingLevel;
     1105        unsigned m_subParenIndex;
     1106        ParenthesesTail* m_nextOuterParenTail;
    10751107        Label m_nonGreedyTryParentheses;
    10761108        Label m_fallThrough;
    … …  
    10791111        DataLabelPtr m_dataAfterLabelPtr;
    10801112        JumpList m_pattBacktrackJumps;
     1113        JumpList m_withinBacktrackJumps;
    10811114        BacktrackDestination m_parenBacktrack;
    10821115        BacktrackDestination m_backtrack;
    … …  
    15991632            }
    16001633
    1601             ParenthesesTail* parenthesesTail = m_expressionState.addParenthesesTail(term);
     1634            ParenthesesTail* parenthesesTail = m_expressionState.addParenthesesTail(term, state.getParenthesesTail());
    16021635
    16031636            m_expressionState.incrementParenNestingLevel();
    16041637
     1638            TermGenerationState parenthesesState(disjunction, state.checkedTotal);
     1639           
     1640            // Save the parenthesesTail for backtracking from nested parens to this one.
     1641            parenthesesState.setParenthesesTail(parenthesesTail);
     1642
    16051643            // generate the body of the parentheses
    1606             TermGenerationState parenthesesState(disjunction, state.checkedTotal);
    16071644            generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation);
    16081645

  • trunk/LayoutTests/ChangeLog

    r73863 r73866  
     12010-12-10  Michael Saboff  <msaboff@apple.com>
     2
     3        Reviewed by Gavin Barraclough.
     4
     5        REGRESSION Hang inside Yarr::RegexCodeBlock::execute when visiting
     6        bugs.webkit.org
     7        https://bugs.webkit.org/show_bug.cgi?id=50816
     8
     9        New test to verify proper backtracking of alternative nested parens.
     10
     11        * fast/regex/parentheses-expected.txt:
     12        * fast/regex/script-tests/parentheses.js:
     13
    1142010-12-11  Pavel Feldman  <pfeldman@chromium.org>
    215

  • trunk/LayoutTests/fast/regex/parentheses-expected.txt

    r73640 r73866  
    3434PASS regexp27.exec('file:///Users/Someone/Desktop/HelloWorld/index.html') is ['file:///Users/Someone/Desktop/HelloWorld/index.html','file','//','',undefined,undefined,undefined,'',undefined,'/Users/Someone/Desktop/HelloWorld/index.html',undefined,undefined]
    3535PASS regexp28.exec('file:///Users/Someone/Desktop/HelloWorld/index.html') is ['file:','file',undefined,undefined,undefined,undefined,undefined]
     36PASS regexp29.exec('Committer:') is null
     37PASS regexp30.exec('Committer:') is null
     38PASS regexp31.exec('Committer:') is null
     39PASS regexp32.exec('Committer:') is null
    3640PASS 'Hi Bob'.match(/(Rob)|(Bob)|(Robert)|(Bobby)/) is ['Bob',undefined,'Bob',undefined,undefined]
    3741PASS successfullyParsed is true

  • trunk/LayoutTests/fast/regex/script-tests/parentheses.js

    r73640 r73866  
    126126shouldBe("regexp28.exec('file:///Users/Someone/Desktop/HelloWorld/index.html')", "['file:','file',undefined,undefined,undefined,undefined,undefined]");
    127127
     128var regexp29 = /^\s*((\[[^\]]+\])|(u?)("[^"]+"))\s*/;
     129shouldBeNull("regexp29.exec('Committer:')");
     130
     131var regexp30 = /^\s*((\[[^\]]+\])|m(u?)("[^"]+"))\s*/;
     132shouldBeNull("regexp30.exec('Committer:')");
     133
     134var regexp31 = /^\s*(m(\[[^\]]+\])|m(u?)("[^"]+"))\s*/;
     135shouldBeNull("regexp31.exec('Committer:')");
     136
     137var regexp32 = /\s*(m(\[[^\]]+\])|m(u?)("[^"]+"))\s*/;
     138shouldBeNull("regexp32.exec('Committer:')");
     139
    128140shouldBe("'Hi Bob'.match(/(Rob)|(Bob)|(Robert)|(Bobby)/)", "['Bob',undefined,'Bob',undefined,undefined]");
    129141
Note: See TracChangeset for help on using the changeset viewer.