Ignore:
Timestamp:
Jan 1, 2008, 11:16:06 AM (17 years ago)
Author:
Darin Adler
Message:

JavaScriptCore:

Reviewed by Geoff.

Fixes 34 failing test cases in the fast/regex/test1.html test.

Restored the stack which prevents infinite loops for brackets that match the empty
string; it had been removed as an optimization.

Unfortunately, restoring this stack causes the regular expression test in SunSpider
to be 1.095x as slow and the overall test to be 1.004x as slow. Maybe we can find
a correct optimization to restore the speed!

It's possible the original change was on the right track but just off by one.

  • pcre/pcre_exec.cpp: Add back eptrblock, but name it BracketChainNode. (MatchStack::pushNewFrame): Add back the logic needed here. (startNewGroup): Ditto. (match): Ditto.

LayoutTests:

Reviewed by Geoff.

  • fast/regex/test1-expected.txt: Update results changed by restoring the logic to avoid failing on infinite repeats of brackets that match the empty string.
File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/pcre/pcre_exec.cpp

    r28841 r29066  
    6767#endif
    6868
     69/* Structure for building a chain of data for holding the values of
     70the subject pointer at the start of each bracket, used to detect when
     71an empty string has been matched by a bracket to break infinite loops. */
     72struct BracketChainNode {
     73    BracketChainNode* previousBracket;
     74    const UChar* bracketStart;
     75};
     76
    6977struct MatchFrame {
    7078    ReturnLocation returnLocation;
    … …  
    7684        const unsigned char* instructionPtr;
    7785        int offsetTop;
    78         const UChar* subpatternStart;
     86        BracketChainNode* bracketChain;
    7987    } args;
    8088   
    … …  
    102110        int saveOffset3;
    103111       
    104         const UChar* subpatternStart;
     112        BracketChainNode bracketChainNode;
    105113    } locals;
    106114};
    … …  
    314322    }
    315323   
    316     inline void pushNewFrame(const unsigned char* instructionPtr, const UChar* subpatternStart, ReturnLocation returnLocation)
     324    inline void pushNewFrame(const unsigned char* instructionPtr, BracketChainNode* bracketChain, ReturnLocation returnLocation)
    317325    {
    318326        MatchFrame* newframe = allocateNextFrame();
    … …  
    322330        newframe->args.offsetTop = currentFrame->args.offsetTop;
    323331        newframe->args.instructionPtr = instructionPtr;
    324         newframe->args.subpatternStart = subpatternStart;
     332        newframe->args.bracketChain = bracketChain;
    325333        newframe->returnLocation = returnLocation;
    326334        size++;
    … …  
    376384     this stack. */
    377385   
    378     currentFrame->locals.subpatternStart = currentFrame->args.subpatternStart;
     386    currentFrame->locals.bracketChainNode.previousBracket = currentFrame->args.bracketChain;
     387    currentFrame->locals.bracketChainNode.bracketStart = currentFrame->args.subjectPtr;
     388    currentFrame->args.bracketChain = &currentFrame->locals.bracketChainNode;
    379389}
    380390
    … …  
    426436    stack.currentFrame->args.instructionPtr = instructionPtr;
    427437    stack.currentFrame->args.offsetTop = offsetTop;
    428     stack.currentFrame->args.subpatternStart = 0;
     438    stack.currentFrame->args.bracketChain = 0;
    429439    startNewGroup(stack.currentFrame);
    430440   
    … …  
    462472                DPRINTF(("start bracket 0\n"));
    463473                do {
    464                     RECURSIVE_MATCH_STARTNG_NEW_GROUP(2, stack.currentFrame->args.instructionPtr + 1 + LINK_SIZE, stack.currentFrame->args.subpatternStart);
     474                    RECURSIVE_MATCH_STARTNG_NEW_GROUP(2, stack.currentFrame->args.instructionPtr + 1 + LINK_SIZE, stack.currentFrame->args.bracketChain);
    465475                    if (isMatch)
    466476                        RRETURN;
    … …  
    536546            BEGIN_OPCODE(BRAZERO): {
    537547                stack.currentFrame->locals.startOfRepeatingBracket = stack.currentFrame->args.instructionPtr + 1;
    538                 RECURSIVE_MATCH_STARTNG_NEW_GROUP(14, stack.currentFrame->locals.startOfRepeatingBracket, stack.currentFrame->args.subpatternStart);
     548                RECURSIVE_MATCH_STARTNG_NEW_GROUP(14, stack.currentFrame->locals.startOfRepeatingBracket, stack.currentFrame->args.bracketChain);
    539549                if (isMatch)
    540550                    RRETURN;
    … …  
    547557                stack.currentFrame->locals.startOfRepeatingBracket = stack.currentFrame->args.instructionPtr + 1;
    548558                advanceToEndOfBracket(stack.currentFrame->locals.startOfRepeatingBracket);
    549                 RECURSIVE_MATCH_STARTNG_NEW_GROUP(15, stack.currentFrame->locals.startOfRepeatingBracket + 1 + LINK_SIZE, stack.currentFrame->args.subpatternStart);
     559                RECURSIVE_MATCH_STARTNG_NEW_GROUP(15, stack.currentFrame->locals.startOfRepeatingBracket + 1 + LINK_SIZE, stack.currentFrame->args.bracketChain);
    550560                if (isMatch)
    551561                    RRETURN;
    … …  
    563573            BEGIN_OPCODE(KETRMAX):
    564574                stack.currentFrame->locals.instructionPtrAtStartOfOnce = stack.currentFrame->args.instructionPtr - getLinkValue(stack.currentFrame->args.instructionPtr + 1);
    565                 stack.currentFrame->args.subpatternStart = stack.currentFrame->locals.subpatternStart;
    566                 stack.currentFrame->locals.subpatternStart = stack.currentFrame->previousFrame->args.subpatternStart;
     575                stack.currentFrame->locals.subjectPtrAtStartOfInstruction = stack.currentFrame->args.bracketChain->bracketStart;
     576
     577                /* Back up the stack of bracket start pointers. */
     578
     579                stack.currentFrame->args.bracketChain = stack.currentFrame->args.bracketChain->previousBracket;
    567580
    568581                if (*stack.currentFrame->locals.instructionPtrAtStartOfOnce == OP_ASSERT || *stack.currentFrame->locals.instructionPtrAtStartOfOnce == OP_ASSERT_NOT) {
    … …  
    622635               
    623636                if (*stack.currentFrame->args.instructionPtr == OP_KETRMIN) {
    624                     RECURSIVE_MATCH(16, stack.currentFrame->args.instructionPtr + 1 + LINK_SIZE, stack.currentFrame->args.subpatternStart);
     637                    RECURSIVE_MATCH(16, stack.currentFrame->args.instructionPtr + 1 + LINK_SIZE, stack.currentFrame->args.bracketChain);
    625638                    if (isMatch)
    626639                        RRETURN;
    627                     RECURSIVE_MATCH_STARTNG_NEW_GROUP(17, stack.currentFrame->locals.instructionPtrAtStartOfOnce, stack.currentFrame->args.subpatternStart);
     640                    RECURSIVE_MATCH_STARTNG_NEW_GROUP(17, stack.currentFrame->locals.instructionPtrAtStartOfOnce, stack.currentFrame->args.bracketChain);
    628641                    if (isMatch)
    629642                        RRETURN;
    630643                } else { /* OP_KETRMAX */
    631                     RECURSIVE_MATCH_STARTNG_NEW_GROUP(18, stack.currentFrame->locals.instructionPtrAtStartOfOnce, stack.currentFrame->args.subpatternStart);
     644                    RECURSIVE_MATCH_STARTNG_NEW_GROUP(18, stack.currentFrame->locals.instructionPtrAtStartOfOnce, stack.currentFrame->args.bracketChain);
    632645                    if (isMatch)
    633646                        RRETURN;
    634                     RECURSIVE_MATCH(19, stack.currentFrame->args.instructionPtr + 1 + LINK_SIZE, stack.currentFrame->args.subpatternStart);
     647                    RECURSIVE_MATCH(19, stack.currentFrame->args.instructionPtr + 1 + LINK_SIZE, stack.currentFrame->args.bracketChain);
    635648                    if (isMatch)
    636649                        RRETURN;
    … …  
    806819                if (minimize) {
    807820                    for (stack.currentFrame->locals.fi = min;; stack.currentFrame->locals.fi++) {
    808                         RECURSIVE_MATCH(20, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.subpatternStart);
     821                        RECURSIVE_MATCH(20, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
    809822                        if (isMatch)
    810823                            RRETURN;
    … …  
    826839                    }
    827840                    while (stack.currentFrame->args.subjectPtr >= stack.currentFrame->locals.subjectPtrAtStartOfInstruction) {
    828                         RECURSIVE_MATCH(21, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.subpatternStart);
     841                        RECURSIVE_MATCH(21, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
    829842                        if (isMatch)
    830843                            RRETURN;
    … …  
    901914                if (minimize) {
    902915                    for (stack.currentFrame->locals.fi = min;; stack.currentFrame->locals.fi++) {
    903                         RECURSIVE_MATCH(22, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.subpatternStart);
     916                        RECURSIVE_MATCH(22, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
    904917                        if (isMatch)
    905918                            RRETURN;
    … …  
    935948                    }
    936949                    for (;;) {
    937                         RECURSIVE_MATCH(24, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.subpatternStart);
     950                        RECURSIVE_MATCH(24, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
    938951                        if (isMatch)
    939952                            RRETURN;
    … …  
    9971010                if (minimize) {
    9981011                    for (stack.currentFrame->locals.fi = min;; stack.currentFrame->locals.fi++) {
    999                         RECURSIVE_MATCH(26, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.subpatternStart);
     1012                        RECURSIVE_MATCH(26, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
    10001013                        if (isMatch)
    10011014                            RRETURN;
    … …  
    10221035                    }
    10231036                    for(;;) {
    1024                         RECURSIVE_MATCH(27, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.subpatternStart);
     1037                        RECURSIVE_MATCH(27, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
    10251038                        if (isMatch)
    10261039                            RRETURN;
    … …  
    11341147                        stack.currentFrame->locals.repeatOthercase = othercase;
    11351148                        for (stack.currentFrame->locals.fi = min;; stack.currentFrame->locals.fi++) {
    1136                             RECURSIVE_MATCH(28, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.subpatternStart);
     1149                            RECURSIVE_MATCH(28, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
    11371150                            if (isMatch)
    11381151                                RRETURN;
    … …  
    11541167                        }
    11551168                        while (stack.currentFrame->args.subjectPtr >= stack.currentFrame->locals.subjectPtrAtStartOfInstruction) {
    1156                             RECURSIVE_MATCH(29, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.subpatternStart);
     1169                            RECURSIVE_MATCH(29, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
    11571170                            if (isMatch)
    11581171                                RRETURN;
    … …  
    11761189                    if (minimize) {
    11771190                        for (stack.currentFrame->locals.fi = min;; stack.currentFrame->locals.fi++) {
    1178                             RECURSIVE_MATCH(30, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.subpatternStart);
     1191                            RECURSIVE_MATCH(30, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
    11791192                            if (isMatch)
    11801193                                RRETURN;
    … …  
    11961209                        }
    11971210                        while (stack.currentFrame->args.subjectPtr >= stack.currentFrame->locals.subjectPtrAtStartOfInstruction) {
    1198                             RECURSIVE_MATCH(31, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.subpatternStart);
     1211                            RECURSIVE_MATCH(31, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
    11991212                            if (isMatch)
    12001213                                RRETURN;
    … …  
    12911304                    if (minimize) {
    12921305                        for (stack.currentFrame->locals.fi = min;; stack.currentFrame->locals.fi++) {
    1293                             RECURSIVE_MATCH(38, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.subpatternStart);
     1306                            RECURSIVE_MATCH(38, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
    12941307                            if (isMatch)
    12951308                                RRETURN;
    … …  
    13191332                        }
    13201333                        for (;;) {
    1321                             RECURSIVE_MATCH(40, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.subpatternStart);
     1334                            RECURSIVE_MATCH(40, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
    13221335                            if (isMatch)
    13231336                                RRETURN;
    … …  
    13451358                    if (minimize) {
    13461359                        for (stack.currentFrame->locals.fi = min;; stack.currentFrame->locals.fi++) {
    1347                             RECURSIVE_MATCH(42, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.subpatternStart);
     1360                            RECURSIVE_MATCH(42, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
    13481361                            if (isMatch)
    13491362                                RRETURN;
    … …  
    13691382                        }
    13701383                        for (;;) {
    1371                             RECURSIVE_MATCH(44, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.subpatternStart);
     1384                            RECURSIVE_MATCH(44, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
    13721385                            if (isMatch)
    13731386                                RRETURN;
    … …  
    14951508                if (minimize) {
    14961509                    for (stack.currentFrame->locals.fi = min;; stack.currentFrame->locals.fi++) {
    1497                         RECURSIVE_MATCH(48, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.subpatternStart);
     1510                        RECURSIVE_MATCH(48, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
    14981511                        if (isMatch)
    14991512                            RRETURN;
    … …  
    16351648                   
    16361649                    for (;;) {
    1637                         RECURSIVE_MATCH(52, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.subpatternStart);
     1650                        RECURSIVE_MATCH(52, stack.currentFrame->args.instructionPtr, stack.currentFrame->args.bracketChain);
    16381651                        if (isMatch)
    16391652                            RRETURN;
    … …  
    17041717                   
    17051718                    do {
    1706                         RECURSIVE_MATCH_STARTNG_NEW_GROUP(1, stack.currentFrame->args.instructionPtr + 1 + LINK_SIZE, stack.currentFrame->args.subpatternStart);
     1719                        RECURSIVE_MATCH_STARTNG_NEW_GROUP(1, stack.currentFrame->args.instructionPtr + 1 + LINK_SIZE, stack.currentFrame->args.bracketChain);
    17071720                        if (isMatch)
    17081721                            RRETURN;
Note: See TracChangeset for help on using the changeset viewer.