jsregexp.c

来自「一个基于alice开发的机器人」· C语言 代码 · 共 1,779 行 · 第 1/5 页

        if ((((RENode *)(result->kid))->op == REOP_FLAT)
                && (((RENode *)(result->u.kid2))->op == REOP_FLAT)
                && ((state->flags & JSREG_FOLD) == 0) ) {
            result->op = REOP_ALTPREREQ;
            result->u.altprereq.ch1 
                = ((RENode *)(result->kid))->u.flat.chr;
            result->u.altprereq.ch2 
                = ((RENode *)(result->u.kid2))->u.flat.chr;
            /* ALTPREREQ, <end>, uch1, uch2, <next>, ..., 
                                            JUMP, <end> ... ENDALT */
            state->progLength += 13;
        }
        else
        if ((((RENode *)(result->kid))->op == REOP_CLASS)
                && (((RENode *)(result->kid))->u.ucclass.index < 256)
                && (((RENode *)(result->u.kid2))->op == REOP_FLAT)
                && ((state->flags & JSREG_FOLD) == 0) ) {
            result->op = REOP_ALTPREREQ2;
            result->u.altprereq.ch1 
                = ((RENode *)(result->u.kid2))->u.flat.chr;
            result->u.altprereq.ch2 
                = ((RENode *)(result->kid))->u.ucclass.index;
            /* ALTPREREQ2, <end>, uch1, uch2, <next>, ..., 
                                            JUMP, <end> ... ENDALT */
            state->progLength += 13;
        }
        else
        if ((((RENode *)(result->kid))->op == REOP_FLAT)
                && (((RENode *)(result->u.kid2))->op == REOP_CLASS)
                && (((RENode *)(result->u.kid2))->u.ucclass.index < 256)
                && ((state->flags & JSREG_FOLD) == 0) ) {
            result->op = REOP_ALTPREREQ2;
            result->u.altprereq.ch1 
                = ((RENode *)(result->kid))->u.flat.chr;
            result->u.altprereq.ch2 
                = ((RENode *)(result->u.kid2))->u.ucclass.index;
            /* ALTPREREQ2, <end>, uch1, uch2, <next>, ..., 
                                          JUMP, <end> ... ENDALT */
            state->progLength += 13;
        }
        else
            /* ALT, <next>, ..., JUMP, <end> ... ENDALT */
            state->progLength += 7;
        break;
    case REOP_CONCAT:
        result = operandStack[operandSP - 2];
        while (result->next)
            result = result->next;
        result->next = operandStack[operandSP - 1];
        break;
    case REOP_ASSERT:
    case REOP_ASSERT_NOT:
    case REOP_LPARENNON:
    case REOP_LPAREN:
        /* These should have been processed by a close paren. */
        js_ReportCompileErrorNumber(state->context, state->tokenStream,
                                    NULL, JSREPORT_ERROR,
                                    JSMSG_MISSING_PAREN, opData->errPos);
        return JS_FALSE;
    default:;
    }
    return JS_TRUE;
}

/*
 * Parser forward declarations.
 */
static JSBool parseTerm(CompilerState *state);
static JSBool parseQuantifier(CompilerState *state);

/*
 * Top-down regular expression grammar, based closely on Perl4.
 *
 *  regexp:     altern                  A regular expression is one or more
 *              altern '|' regexp       alternatives separated by vertical bar.
 */

#define INITIAL_STACK_SIZE (128)
static JSBool 
parseRegExp(CompilerState *state)
{
    uint16 parenIndex;
    RENode *operand;
    REOpData *operatorStack;
    RENode **operandStack;
    REOp op;
    intN i;
    JSBool result = JS_FALSE;

    intN operatorSP = 0, operatorStackSize = INITIAL_STACK_SIZE;
    intN operandSP = 0, operandStackSize = INITIAL_STACK_SIZE;

    /* Watch out for empty regexp */
    if (state->cp == state->cpend) {
        state->result = NewRENode(state, REOP_EMPTY);
        return (state->result != NULL);
    }

    operatorStack = (REOpData *)JS_malloc(state->context, 
                                          sizeof(REOpData) * operatorStackSize);
    if (!operatorStack)
        return JS_FALSE;

    operandStack = (RENode **)JS_malloc(state->context,
                                        sizeof(RENode *) * operandStackSize);
    if (!operandStack)
        goto out;


    while (JS_TRUE) {
        if (state->cp == state->cpend) {
            /*
             * If we are at the end of the regexp and we're short an operand,
             * the regexp must have the form /x|/ or some such.
             */
            if (operatorSP == operandSP) {
                operand = NewRENode(state, REOP_EMPTY);
                if (!operand)
                    goto out;
                goto pushOperand;
            }
        } else {
            switch (*state->cp) {
                /* balance '(' */
            case '(':           /* balance ')' */
                ++state->cp;
                if ((state->cp < state->cpend) && (*state->cp == '?')
                        && ( (state->cp[1] == '=')
                                || (state->cp[1] == '!')
                                || (state->cp[1] == ':') )) {
                    ++state->cp;
                    if (state->cp == state->cpend) {
                        js_ReportCompileErrorNumber(state->context, 
                                                    state->tokenStream,
                                                    NULL, JSREPORT_ERROR,
                                                    JSMSG_MISSING_PAREN);
                        goto out;
                    }
                    switch (*state->cp++) {
                    case '=':
                        op = REOP_ASSERT;
                        /* ASSERT, <next>, ... ASSERTTEST */
                        state->progLength += 4;    
                        break;
                    case '!':
                        op = REOP_ASSERT_NOT;
                        /* ASSERTNOT, <next>, ... ASSERTNOTTEST */
                        state->progLength += 4;
                        break;
                    case ':':
                        op = REOP_LPARENNON;
                        break;
                    }
                    parenIndex = state->parenCount;
                }
                else {
                    op = REOP_LPAREN;
                    /* LPAREN, <index>, ... RPAREN, <index> */
                    state->progLength += 6;
                    parenIndex = state->parenCount++;
                    if (state->parenCount == 65535) {
                        js_ReportCompileErrorNumber(state->context, 
                                                    state->tokenStream,
                                                    NULL, JSREPORT_ERROR,
                                                    JSMSG_TOO_MANY_PARENS);
                        goto out;
                    }
                }
                goto pushOperator;
            case ')':
                /* If there's not a stacked open parenthesis, throw
                 * a syntax error.
                 */
                for (i = operatorSP - 1; i >= 0; i--)
                    if ((operatorStack[i].op == REOP_ASSERT)
                            || (operatorStack[i].op == REOP_ASSERT_NOT)
                            || (operatorStack[i].op == REOP_LPARENNON)
                            || (operatorStack[i].op == REOP_LPAREN))
                        break;
                if (i == -1) {
                    js_ReportCompileErrorNumber(state->context, 
                                                state->tokenStream,
                                                NULL, JSREPORT_ERROR,
                                                JSMSG_UNMATCHED_RIGHT_PAREN);
                    goto out;
                }
                /* fall thru... */
            case '|':
                /* Expected an operand before these, so make an empty one */
                operand = NewRENode(state, REOP_EMPTY);
                if (!operand)
                    goto out;
                goto pushOperand;
            default:
                if (!parseTerm(state))
                    goto out;
                operand = state->result;
pushOperand:
                if (operandSP == operandStackSize) {
                    operandStackSize += operandStackSize;
                    operandStack = 
                      (RENode **)JS_realloc(state->context, operandStack,
                                            sizeof(RENode *) * operandStackSize);
                    if (!operandStack)
                        goto out;
                }
                operandStack[operandSP++] = operand;
                break;
            }
        }
            /* At the end; process remaining operators */
restartOperator:
        if (state->cp == state->cpend) {
            while (operatorSP) {
                --operatorSP;
                if (!processOp(state, &operatorStack[operatorSP], 
                               operandStack, operandSP))
                    goto out;
                --operandSP;
            }
            JS_ASSERT(operandSP == 1);
            state->result = operandStack[0];
            result = JS_TRUE;
            goto out;
        }
        switch (*state->cp) {
        case '|': 
            /* Process any stacked 'concat' operators */
            ++state->cp;
            while (operatorSP 
                    && (operatorStack[operatorSP - 1].op == REOP_CONCAT)) {
                --operatorSP;
                if (!processOp(state, &operatorStack[operatorSP], 
                               operandStack, operandSP))
                    goto out;
                --operandSP;
            }
            op = REOP_ALT;
            goto pushOperator;

        case ')':
            /* If there's not a stacked open parenthesis,we
             * accept the close as a flat.
             */
            for (i = operatorSP - 1; i >= 0; i--)
                if ((operatorStack[i].op == REOP_ASSERT)
                        || (operatorStack[i].op == REOP_ASSERT_NOT)
                        || (operatorStack[i].op == REOP_LPARENNON)
                        || (operatorStack[i].op == REOP_LPAREN))
                    break;
            if (i == -1) {
                js_ReportCompileErrorNumber(state->context, 
                                            state->tokenStream,
                                            NULL, JSREPORT_ERROR,
                                            JSMSG_UNMATCHED_RIGHT_PAREN);
                goto out;
            }
            ++state->cp;
            /* process everything on the stack until the open */
            while (JS_TRUE) {
                JS_ASSERT(operatorSP);                    
                --operatorSP;
                switch (operatorStack[operatorSP].op) {
                case REOP_ASSERT:
                case REOP_ASSERT_NOT:
                case REOP_LPAREN:
                    operand = NewRENode(state, operatorStack[operatorSP].op);
                    if (!operand)
                        goto out;
                    operand->u.parenIndex 
                                    = operatorStack[operatorSP].parenIndex;
                    JS_ASSERT(operandSP);
                    operand->kid = operandStack[operandSP - 1];
                    operandStack[operandSP - 1] = operand;
                    ++state->treeDepth;
                    /* fall thru... */
                case REOP_LPARENNON:
                    state->result = operandStack[operandSP - 1];
                    if (!parseQuantifier(state))
                        goto out;
                    operandStack[operandSP - 1] = state->result;
                    goto restartOperator;
                default:
                    if (!processOp(state, &operatorStack[operatorSP], 
                                   operandStack, operandSP))
                        goto out;
                    --operandSP;
                    break;
                }
            }
            break;
        default:
            /* Anything else is the start of the next term */
            op = REOP_CONCAT;
pushOperator:
            if (operatorSP == operatorStackSize) {
                operatorStackSize += operatorStackSize;
                operatorStack = 
                    (REOpData *)JS_realloc(state->context, operatorStack,
                                           sizeof(REOpData) * operatorStackSize);
                if (!operatorStack)
                    goto out;
            }
            operatorStack[operatorSP].op = op;
            operatorStack[operatorSP].errPos = state->cp;
            operatorStack[operatorSP++].parenIndex = parenIndex;
            break;
        }
    }
out:
    if (operatorStack)
        JS_free(state->context, operatorStack);
    if (operandStack)
        JS_free(state->context, operandStack);
    return result;
}

/*
 * Extract and return a decimal value at state->cp, the
 * initial character 'c' has already been read.
 */
static intN 
getDecimalValue(jschar c, CompilerState *state)
{
    intN value = JS7_UNDEC(c);
    while (state->cp < state->cpend) {
        c = *state->cp; 
        if (!JS7_ISDEC(c))
            break;
        value = (10 * value) + JS7_UNDEC(c);
        ++state->cp;
    }
    return value;
}

/*
 * Calculate the total size of the bitmap required for a class expression.
 */
static JSBool 
calculateBitmapSize(CompilerState *state, RENode *target, const jschar *src,
                    const jschar *end)
{
    jschar rangeStart, c;
    uintN n, digit, nDigits, i;
    uintN max = 0;
    JSBool inRange = JS_FALSE;

    target->u.ucclass.bmsize = 0;
    target->u.ucclass.sense = JS_TRUE;

    if (src == end)
        return JS_TRUE;

    if (*src == '^') {
        ++src;
        target->u.ucclass.sense = JS_FALSE;