in rhino/src/main/java/org/mozilla/javascript/regexp/NativeRegExp.java [2366:2935]
private static boolean executeREBytecode(
Context cx, REGlobalData gData, String input, int end) {
int pc = 0;
byte[] program = gData.regexp.program;
int continuationOp = REOP_END;
int continuationPc = 0;
boolean result = false;
boolean matchBackward = false; /* match forward by default */
int op = program[pc++];
/*
* If the first node is a simple match, step the index into the string
* until that match is made, or fail if it can't be found at all.
*/
if (gData.regexp.anchorCh < 0 && reopIsSimple(op)) {
boolean anchor = false;
while (gData.cp <= end) {
int match = simpleMatch(gData, input, op, program, pc, end, true, false);
if (match < 0) {
if ((gData.regexp.flags & JSREG_STICKY) != 0) {
return false;
}
} else {
anchor = true;
pc = match; /* accept skip to next opcode */
op = program[pc++];
break;
}
gData.skipped++;
gData.cp++;
}
if (!anchor) return false;
}
final boolean instructionCounting = cx.getInstructionObserverThreshold() != 0;
for (; ; ) {
if (instructionCounting) {
ScriptRuntime.addInstructionCount(cx, 5);
}
if (reopIsSimple(op)) {
int match = simpleMatch(gData, input, op, program, pc, end, true, matchBackward);
result = match >= 0;
if (result) pc = match; /* accept skip to next opcode */
} else {
switchStatement:
switch (op) {
case REOP_ALTPREREQ:
case REOP_ALTPREREQi:
case REOP_ALTPREREQ2:
{
char matchCh1 = (char) getIndex(program, pc);
pc += INDEX_LEN;
char matchCh2 = (char) getIndex(program, pc);
pc += INDEX_LEN;
final int cpToMatch = gData.cp + (matchBackward ? -1 : 0);
final boolean cpInBounds = cpToMatch >= 0 && cpToMatch < end;
if (!cpInBounds) {
result = false;
break;
}
char c = input.charAt(cpToMatch);
if (op == REOP_ALTPREREQ2) {
if (c != matchCh1
&& !classMatcher(
gData, gData.regexp.classList[matchCh2], c)) {
result = false;
break;
}
} else {
if (op == REOP_ALTPREREQi) c = upcase(c);
if (c != matchCh1 && c != matchCh2) {
result = false;
break;
}
}
}
/* else false thru... */
// fall through
case REOP_ALT:
{
int nextpc = pc + getOffset(program, pc);
pc += INDEX_LEN;
op = program[pc++];
int startcp = gData.cp;
if (reopIsSimple(op)) {
int match =
simpleMatch(
gData,
input,
op,
program,
pc,
end,
true,
matchBackward);
if (match < 0) {
op = program[nextpc++];
pc = nextpc;
continue;
}
result = true;
pc = match;
op = program[pc++];
}
byte nextop = program[nextpc++];
pushBackTrackState(
gData, nextop, nextpc, startcp, continuationOp, continuationPc);
}
continue;
case REOP_JUMP:
{
int offset = getOffset(program, pc);
pc += offset;
op = program[pc++];
}
continue;
case REOP_LPAREN:
{
int parenIndex = getIndex(program, pc);
pc += INDEX_LEN;
gData.setParens(parenIndex, gData.cp, 0);
op = program[pc++];
}
continue;
case REOP_RPAREN:
{
int parenIndex = getIndex(program, pc);
pc += INDEX_LEN;
int cap_index = gData.parensIndex(parenIndex);
if (matchBackward)
// paren content is captured backwards. Therefore we
// reverse the capture here
gData.setParens(parenIndex, gData.cp, cap_index - gData.cp);
else gData.setParens(parenIndex, cap_index, gData.cp - cap_index);
op = program[pc++];
}
continue;
case REOP_ASSERTBACK:
{
int nextpc =
pc + getIndex(program, pc); /* start of term after ASSERT */
pc += INDEX_LEN; /* start of ASSERT child */
op = program[pc++];
if (reopIsSimple(op)
&& simpleMatch(gData, input, op, program, pc, end, false, true)
< 0) {
result = false;
break;
}
pushProgState(
gData,
0,
0,
gData.cp,
matchBackward,
gData.backTrackStackTop,
continuationOp,
continuationPc);
pushBackTrackState(
gData,
REOP_ASSERTBACKTEST,
nextpc,
gData.cp,
continuationOp,
continuationPc);
matchBackward = true;
}
continue;
case REOP_ASSERTBACK_NOT:
{
int nextpc =
pc + getIndex(program, pc); /* start of term after ASSERT */
pc += INDEX_LEN; /* start of ASSERT child */
op = program[pc++];
if (reopIsSimple(op)) {
int match =
simpleMatch(
gData, input, op, program, pc, end, false, true);
if (match >= 0 && program[match] == REOP_ASSERTBACKNOTTEST) {
result = false;
break;
}
}
pushProgState(
gData,
0,
0,
gData.cp,
matchBackward,
gData.backTrackStackTop,
continuationOp,
continuationPc);
pushBackTrackState(
gData,
REOP_ASSERTBACKNOTTEST,
nextpc,
gData.cp,
continuationOp,
continuationPc);
matchBackward = true;
}
continue;
case REOP_ASSERT:
{
int nextpc =
pc + getIndex(program, pc); /* start of term after ASSERT */
pc += INDEX_LEN; /* start of ASSERT child */
op = program[pc++];
if (reopIsSimple(op)
&& simpleMatch(gData, input, op, program, pc, end, false, false)
< 0) {
result = false;
break;
}
pushProgState(
gData,
0,
0,
gData.cp,
matchBackward,
gData.backTrackStackTop,
continuationOp,
continuationPc);
pushBackTrackState(gData, REOP_ASSERTTEST, nextpc);
matchBackward = false;
}
continue;
case REOP_ASSERT_NOT:
{
int nextpc =
pc + getIndex(program, pc); /* start of term after ASSERT */
pc += INDEX_LEN; /* start of ASSERT child */
op = program[pc++];
if (reopIsSimple(op)) {
int match =
simpleMatch(
gData, input, op, program, pc, end, false, false);
if (match >= 0 && program[match] == REOP_ASSERTNOTTEST) {
result = false;
break;
}
}
pushProgState(
gData,
0,
0,
gData.cp,
matchBackward,
gData.backTrackStackTop,
continuationOp,
continuationPc);
pushBackTrackState(gData, REOP_ASSERTNOTTEST, nextpc);
matchBackward = false;
}
continue;
case REOP_ASSERTTEST:
case REOP_ASSERTBACKTEST:
case REOP_ASSERTNOTTEST:
case REOP_ASSERTBACKNOTTEST:
{
REProgState state = popProgState(gData);
gData.cp = state.index;
gData.backTrackStackTop = state.backTrack;
matchBackward = state.matchBackward;
continuationPc = state.continuationPc;
continuationOp = state.continuationOp;
if (op == REOP_ASSERTNOTTEST || op == REOP_ASSERTBACKNOTTEST) {
result = !result;
}
}
break;
case REOP_STAR:
case REOP_PLUS:
case REOP_OPT:
case REOP_QUANT:
case REOP_MINIMALSTAR:
case REOP_MINIMALPLUS:
case REOP_MINIMALOPT:
case REOP_MINIMALQUANT:
{
int min, max;
boolean greedy = false;
switch (op) {
case REOP_STAR:
greedy = true;
// fallthrough
case REOP_MINIMALSTAR:
min = 0;
max = -1;
break;
case REOP_PLUS:
greedy = true;
// fallthrough
case REOP_MINIMALPLUS:
min = 1;
max = -1;
break;
case REOP_OPT:
greedy = true;
// fallthrough
case REOP_MINIMALOPT:
min = 0;
max = 1;
break;
case REOP_QUANT:
greedy = true;
// fallthrough
case REOP_MINIMALQUANT:
min = getOffset(program, pc);
pc += INDEX_LEN;
// See comments in emitREBytecode for " - 1" reason
max = getOffset(program, pc) - 1;
pc += INDEX_LEN;
break;
default:
throw Kit.codeBug();
}
pushProgState(
gData,
min,
max,
gData.cp,
matchBackward,
null,
continuationOp,
continuationPc);
if (greedy) {
pushBackTrackState(gData, REOP_REPEAT, pc);
continuationOp = REOP_REPEAT;
continuationPc = pc;
/* Step over <parencount>, <parenindex> & <next> */
pc += 3 * INDEX_LEN;
} else {
if (min != 0) {
continuationOp = REOP_MINIMALREPEAT;
continuationPc = pc;
/* <parencount> <parenindex> & <next> */
pc += 3 * INDEX_LEN;
} else {
pushBackTrackState(gData, REOP_MINIMALREPEAT, pc);
popProgState(gData);
pc += 2 * INDEX_LEN; // <parencount> & <parenindex>
pc = pc + getOffset(program, pc);
}
}
op = program[pc++];
}
continue;
case REOP_ENDCHILD: /* marks the end of a quantifier child */
// If we have not gotten a result here, it is because of an
// empty match. Do the same thing REOP_EMPTY would do.
result = true;
// Use the current continuation.
pc = continuationPc;
op = continuationOp;
continue;
case REOP_REPEAT:
{
int nextpc, nextop;
do {
REProgState state = popProgState(gData);
if (!result) {
// Failed, see if we have enough children.
if (state.min == 0) result = true;
continuationPc = state.continuationPc;
continuationOp = state.continuationOp;
pc += 2 * INDEX_LEN; /* <parencount> & <parenindex> */
pc += getOffset(program, pc);
break switchStatement;
}
if (state.min == 0 && (gData.cp == state.index || state.max == 0)) {
// matched an empty string or an {0} quantifier, that'll get us
// nowhere
result = false;
continuationPc = state.continuationPc;
continuationOp = state.continuationOp;
pc += 2 * INDEX_LEN;
pc += getOffset(program, pc);
break switchStatement;
}
int new_min = state.min, new_max = state.max;
if (new_min != 0) new_min--;
if (new_max != -1) new_max--;
if (new_max == 0) {
result = true;
continuationPc = state.continuationPc;
continuationOp = state.continuationOp;
pc += 2 * INDEX_LEN;
pc += getOffset(program, pc);
break switchStatement;
}
nextpc = pc + 3 * INDEX_LEN;
nextop = program[nextpc];
int startcp = gData.cp;
if (reopIsSimple(nextop)) {
nextpc++;
int match =
simpleMatch(
gData,
input,
nextop,
program,
nextpc,
end,
true,
matchBackward);
if (match < 0) {
result = (new_min == 0);
continuationPc = state.continuationPc;
continuationOp = state.continuationOp;
pc += 2 * INDEX_LEN; /* <parencount> & <parenindex> */
pc += getOffset(program, pc);
break switchStatement;
}
result = true;
nextpc = match;
}
continuationOp = REOP_REPEAT;
continuationPc = pc;
pushProgState(
gData,
new_min,
new_max,
startcp,
matchBackward,
null,
state.continuationOp,
state.continuationPc);
if (new_min == 0) {
pushBackTrackState(
gData,
REOP_REPEAT,
pc,
startcp,
state.continuationOp,
state.continuationPc);
}
int parenCount = getIndex(program, pc);
int parenIndex = getIndex(program, pc + INDEX_LEN);
for (int k = 0; k < parenCount; k++) {
gData.setParens(parenIndex + k, -1, 0);
}
} while (program[nextpc] == REOP_ENDCHILD);
pc = nextpc;
op = program[pc++];
}
continue;
case REOP_MINIMALREPEAT:
{
REProgState state = popProgState(gData);
if (!result) {
//
// Non-greedy failure - try to consume another child.
//
if (state.max == -1 || state.max > 0) {
pushProgState(
gData,
state.min,
state.max,
gData.cp,
matchBackward,
null,
state.continuationOp,
state.continuationPc);
continuationOp = REOP_MINIMALREPEAT;
continuationPc = pc;
int parenCount = getIndex(program, pc);
pc += INDEX_LEN;
int parenIndex = getIndex(program, pc);
pc += 2 * INDEX_LEN;
for (int k = 0; k < parenCount; k++) {
gData.setParens(parenIndex + k, -1, 0);
}
op = program[pc++];
continue;
}
// Don't need to adjust pc since we're going to pop.
continuationPc = state.continuationPc;
continuationOp = state.continuationOp;
break;
}
if (state.min == 0 && gData.cp == state.index) {
// Matched an empty string, that'll get us nowhere.
result = false;
continuationPc = state.continuationPc;
continuationOp = state.continuationOp;
break;
}
int new_min = state.min, new_max = state.max;
if (new_min != 0) new_min--;
if (new_max != -1) new_max--;
pushProgState(
gData,
new_min,
new_max,
gData.cp,
matchBackward,
null,
state.continuationOp,
state.continuationPc);
if (new_min != 0) {
continuationOp = REOP_MINIMALREPEAT;
continuationPc = pc;
int parenCount = getIndex(program, pc);
pc += INDEX_LEN;
int parenIndex = getIndex(program, pc);
pc += 2 * INDEX_LEN;
for (int k = 0; k < parenCount; k++) {
gData.setParens(parenIndex + k, -1, 0);
}
} else {
continuationPc = state.continuationPc;
continuationOp = state.continuationOp;
pushBackTrackState(gData, REOP_MINIMALREPEAT, pc);
popProgState(gData);
pc += 2 * INDEX_LEN;
pc = pc + getOffset(program, pc);
}
op = program[pc++];
continue;
}
case REOP_END:
return true;
default:
throw Kit.codeBug("invalid bytecode");
}
}
/*
* If the match failed and there's a backtrack option, take it.
* Otherwise this is a complete and utter failure.
*/
if (!result) {
REBackTrackData backTrackData = gData.backTrackStackTop;
if (backTrackData != null) {
gData.backTrackStackTop = backTrackData.previous;
gData.parens = backTrackData.parens;
gData.cp = backTrackData.cp;
gData.stateStackTop = backTrackData.stateStackTop;
continuationOp = backTrackData.continuationOp;
continuationPc = backTrackData.continuationPc;
pc = backTrackData.pc;
op = backTrackData.op;
continue;
}
return false;
}
op = program[pc++];
}
}