1 /* 2 * Permission is hereby granted, free of charge, to any person obtaining a copy of 3 * this software and associated documentation files (the "Software"), to deal in 4 * the Software without restriction, including without limitation the rights to 5 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies 6 * of the Software, and to permit persons to whom the Software is furnished to do 7 * so, subject to the following conditions: 8 * 9 * The above copyright notice and this permission notice shall be included in all 10 * copies or substantial portions of the Software. 11 * 12 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 13 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 14 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 15 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 16 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 17 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 18 * SOFTWARE. 19 */ 20 package jdk.nashorn.internal.runtime.regexp.joni; 21 22 import static jdk.nashorn.internal.runtime.regexp.joni.BitStatus.bsAt; 23 24 import java.lang.ref.WeakReference; 25 import java.util.Arrays; 26 27 import jdk.nashorn.internal.runtime.regexp.joni.constants.StackPopLevel; 28 import jdk.nashorn.internal.runtime.regexp.joni.constants.StackType; 29 30 abstract class StackMachine extends Matcher implements StackType { 31 protected static final int INVALID_INDEX = -1; 32 33 protected StackEntry[]stack; 34 protected int stk; // stkEnd 35 36 protected final int[]repeatStk; 37 protected final int memStartStk, memEndStk; 38 39 // CEC 40 protected byte[] stateCheckBuff; // move to int[] ? 41 int stateCheckBuffSize; 42 43 protected StackMachine(Regex regex, char[] chars, int p , int end) { 44 super(regex, chars, p, end); 45 46 this.stack = regex.stackNeeded ? fetchStack() : null; 47 int n = regex.numRepeat + (regex.numMem << 1); 48 this.repeatStk = n > 0 ? new int[n] : null; 49 50 memStartStk = regex.numRepeat - 1; 51 memEndStk = memStartStk + regex.numMem; 52 /* for index start from 1, mem_start_stk[1]..mem_start_stk[num_mem] */ 53 /* for index start from 1, mem_end_stk[1]..mem_end_stk[num_mem] */ 54 } 55 56 private static StackEntry[] allocateStack() { 57 StackEntry[]stack = new StackEntry[Config.INIT_MATCH_STACK_SIZE]; 58 stack[0] = new StackEntry(); 59 return stack; 60 } 61 62 private void doubleStack() { 63 StackEntry[] newStack = new StackEntry[stack.length << 1]; 64 System.arraycopy(stack, 0, newStack, 0, stack.length); 65 stack = newStack; 66 } 67 68 static final ThreadLocal<WeakReference<StackEntry[]>> stacks 69 = new ThreadLocal<WeakReference<StackEntry[]>>() { 70 @Override 71 protected WeakReference<StackEntry[]> initialValue() { 72 return new WeakReference<StackEntry[]>(allocateStack()); 73 } 74 }; 75 76 private static StackEntry[] fetchStack() { 77 WeakReference<StackEntry[]> ref = stacks.get(); 78 StackEntry[] stack = ref.get(); 79 if (stack == null) { 80 ref = new WeakReference<StackEntry[]>(stack = allocateStack()); 81 stacks.set(ref); 82 } 83 return stack; 84 } 85 86 protected final void init() { 87 if (stack != null) pushEnsured(ALT, regex.codeLength - 1); /* bottom stack */ 88 if (repeatStk != null) { 89 for (int i=1; i<=regex.numMem; i++) { 90 repeatStk[i + memStartStk] = repeatStk[i + memEndStk] = INVALID_INDEX; 91 } 92 } 93 } 94 95 protected final StackEntry ensure1() { 96 if (stk >= stack.length) doubleStack(); 97 StackEntry e = stack[stk]; 98 if (e == null) stack[stk] = e = new StackEntry(); 99 return e; 100 } 101 102 protected final void pushType(int type) { 103 ensure1().type = type; 104 stk++; 105 } 106 107 // CEC 108 109 // STATE_CHECK_POS 110 private int stateCheckPos(int s, int snum) { 111 return (s - str) * regex.numCombExpCheck + (snum - 1); 112 } 113 114 // STATE_CHECK_VAL 115 protected final boolean stateCheckVal(int s, int snum) { 116 if (stateCheckBuff != null) { 117 int x = stateCheckPos(s, snum); 118 return (stateCheckBuff[x / 8] & (1 << (x % 8))) != 0; 119 } 120 return false; 121 } 122 123 // ELSE_IF_STATE_CHECK_MARK 124 private void stateCheckMark() { 125 StackEntry e = stack[stk]; 126 int x = stateCheckPos(e.getStatePStr(), e.getStateCheck()); 127 stateCheckBuff[x / 8] |= (1 << (x % 8)); 128 } 129 130 // STATE_CHECK_BUFF_INIT 131 private static final int STATE_CHECK_BUFF_MALLOC_THRESHOLD_SIZE = 16; 132 protected final void stateCheckBuffInit(int strLength, int offset, int stateNum) { 133 if (stateNum > 0 && strLength >= Config.CHECK_STRING_THRESHOLD_LEN) { 134 int size = ((strLength + 1) * stateNum + 7) >>> 3; 135 offset = (offset * stateNum) >>> 3; 136 137 if (size > 0 && offset < size && size < Config.CHECK_BUFF_MAX_SIZE) { 138 if (size >= STATE_CHECK_BUFF_MALLOC_THRESHOLD_SIZE) { 139 stateCheckBuff = new byte[size]; 140 } else { 141 // same impl, reduce... 142 stateCheckBuff = new byte[size]; 143 } 144 Arrays.fill(stateCheckBuff, offset, (size - offset), (byte)0); 145 stateCheckBuffSize = size; 146 } else { 147 stateCheckBuff = null; // reduce 148 stateCheckBuffSize = 0; 149 } 150 } else { 151 stateCheckBuff = null; // reduce 152 stateCheckBuffSize = 0; 153 } 154 } 155 156 protected final void stateCheckBuffClear() { 157 stateCheckBuff = null; 158 stateCheckBuffSize = 0; 159 } 160 161 private void push(int type, int pat, int s, int prev) { 162 StackEntry e = ensure1(); 163 e.type = type; 164 e.setStatePCode(pat); 165 e.setStatePStr(s); 166 e.setStatePStrPrev(prev); 167 if (Config.USE_COMBINATION_EXPLOSION_CHECK) e.setStateCheck(0); 168 stk++; 169 } 170 171 protected final void pushEnsured(int type, int pat) { 172 StackEntry e = stack[stk]; 173 e.type = type; 174 e.setStatePCode(pat); 175 if (Config.USE_COMBINATION_EXPLOSION_CHECK) e.setStateCheck(0); 176 stk++; 177 } 178 179 protected final void pushAltWithStateCheck(int pat, int s, int sprev, int snum) { 180 StackEntry e = ensure1(); 181 e.type = ALT; 182 e.setStatePCode(pat); 183 e.setStatePStr(s); 184 e.setStatePStrPrev(sprev); 185 if (Config.USE_COMBINATION_EXPLOSION_CHECK) e.setStateCheck(stateCheckBuff != null ? snum : 0); 186 stk++; 187 } 188 189 protected final void pushStateCheck(int s, int snum) { 190 if (stateCheckBuff != null) { 191 StackEntry e = ensure1(); 192 e.type = STATE_CHECK_MARK; 193 e.setStatePStr(s); 194 e.setStateCheck(snum); 195 stk++; 196 } 197 } 198 199 protected final void pushAlt(int pat, int s, int prev) { 200 push(ALT, pat, s, prev); 201 } 202 203 protected final void pushPos(int s, int prev) { 204 push(POS, -1 /*NULL_UCHARP*/, s, prev); 205 } 206 207 protected final void pushPosNot(int pat, int s, int prev) { 208 push(POS_NOT, pat, s, prev); 209 } 210 211 protected final void pushStopBT() { 212 pushType(STOP_BT); 213 } 214 215 protected final void pushLookBehindNot(int pat, int s, int sprev) { 216 push(LOOK_BEHIND_NOT, pat, s, sprev); 217 } 218 219 protected final void pushRepeat(int id, int pat) { 220 StackEntry e = ensure1(); 221 e.type = REPEAT; 222 e.setRepeatNum(id); 223 e.setRepeatPCode(pat); 224 e.setRepeatCount(0); 225 stk++; 226 } 227 228 protected final void pushRepeatInc(int sindex) { 229 StackEntry e = ensure1(); 230 e.type = REPEAT_INC; 231 e.setSi(sindex); 232 stk++; 233 } 234 235 protected final void pushMemStart(int mnum, int s) { 236 StackEntry e = ensure1(); 237 e.type = MEM_START; 238 e.setMemNum(mnum); 239 e.setMemPstr(s); 240 e.setMemStart(repeatStk[memStartStk + mnum]); 241 e.setMemEnd(repeatStk[memEndStk + mnum]); 242 repeatStk[memStartStk + mnum] = stk; 243 repeatStk[memEndStk + mnum] = INVALID_INDEX; 244 stk++; 245 } 246 247 protected final void pushMemEnd(int mnum, int s) { 248 StackEntry e = ensure1(); 249 e.type = MEM_END; 250 e.setMemNum(mnum); 251 e.setMemPstr(s); 252 e.setMemStart(repeatStk[memStartStk + mnum]); 253 e.setMemEnd(repeatStk[memEndStk + mnum]); 254 repeatStk[memEndStk + mnum] = stk; 255 stk++; 256 } 257 258 protected final void pushMemEndMark(int mnum) { 259 StackEntry e = ensure1(); 260 e.type = MEM_END_MARK; 261 e.setMemNum(mnum); 262 stk++; 263 } 264 265 protected final int getMemStart(int mnum) { 266 int level = 0; 267 int stkp = stk; 268 269 while (stkp > 0) { 270 stkp--; 271 StackEntry e = stack[stkp]; 272 if ((e.type & MASK_MEM_END_OR_MARK) != 0 && e.getMemNum() == mnum) { 273 level++; 274 } else if (e.type == MEM_START && e.getMemNum() == mnum) { 275 if (level == 0) break; 276 level--; 277 } 278 } 279 return stkp; 280 } 281 282 protected final void pushNullCheckStart(int cnum, int s) { 283 StackEntry e = ensure1(); 284 e.type = NULL_CHECK_START; 285 e.setNullCheckNum(cnum); 286 e.setNullCheckPStr(s); 287 stk++; 288 } 289 290 protected final void pushNullCheckEnd(int cnum) { 291 StackEntry e = ensure1(); 292 e.type = NULL_CHECK_END; 293 e.setNullCheckNum(cnum); 294 stk++; 295 } 296 297 protected final void pushCallFrame(int pat) { 298 StackEntry e = ensure1(); 299 e.type = CALL_FRAME; 300 e.setCallFrameRetAddr(pat); 301 stk++; 302 } 303 304 protected final void pushReturn() { 305 StackEntry e = ensure1(); 306 e.type = RETURN; 307 stk++; 308 } 309 310 // stack debug routines here 311 // ... 312 313 protected final void popOne() { 314 stk--; 315 } 316 317 protected final StackEntry pop() { 318 switch (regex.stackPopLevel) { 319 case StackPopLevel.FREE: 320 return popFree(); 321 case StackPopLevel.MEM_START: 322 return popMemStart(); 323 default: 324 return popDefault(); 325 } 326 } 327 328 private StackEntry popFree() { 329 while (true) { 330 StackEntry e = stack[--stk]; 331 332 if ((e.type & MASK_POP_USED) != 0) { 333 return e; 334 } else if (Config.USE_COMBINATION_EXPLOSION_CHECK) { 335 if (e.type == STATE_CHECK_MARK) stateCheckMark(); 336 } 337 } 338 } 339 340 private StackEntry popMemStart() { 341 while (true) { 342 StackEntry e = stack[--stk]; 343 344 if ((e.type & MASK_POP_USED) != 0) { 345 return e; 346 } else if (e.type == MEM_START) { 347 repeatStk[memStartStk + e.getMemNum()] = e.getMemStart(); 348 repeatStk[memEndStk + e.getMemNum()] = e.getMemEnd(); 349 } else if (Config.USE_COMBINATION_EXPLOSION_CHECK) { 350 if (e.type == STATE_CHECK_MARK) stateCheckMark(); 351 } 352 } 353 } 354 355 private StackEntry popDefault() { 356 while (true) { 357 StackEntry e = stack[--stk]; 358 359 if ((e.type & MASK_POP_USED) != 0) { 360 return e; 361 } else if (e.type == MEM_START) { 362 repeatStk[memStartStk + e.getMemNum()] = e.getMemStart(); 363 repeatStk[memEndStk + e.getMemNum()] = e.getMemEnd(); 364 } else if (e.type == REPEAT_INC) { 365 //int si = stack[stk + IREPEAT_INC_SI]; 366 //stack[si + IREPEAT_COUNT]--; 367 stack[e.getSi()].decreaseRepeatCount(); 368 } else if (e.type == MEM_END) { 369 repeatStk[memStartStk + e.getMemNum()] = e.getMemStart(); 370 repeatStk[memEndStk + e.getMemNum()] = e.getMemEnd(); 371 } else if (Config.USE_COMBINATION_EXPLOSION_CHECK) { 372 if (e.type == STATE_CHECK_MARK) stateCheckMark(); 373 } 374 } 375 } 376 377 protected final void popTilPosNot() { 378 while (true) { 379 stk--; 380 StackEntry e = stack[stk]; 381 382 if (e.type == POS_NOT) { 383 break; 384 } else if (e.type == MEM_START) { 385 repeatStk[memStartStk + e.getMemNum()] = e.getMemStart(); 386 repeatStk[memEndStk + e.getMemNum()] = e.getMemStart(); 387 } else if (e.type == REPEAT_INC) { 388 //int si = stack[stk + IREPEAT_INC_SI]; 389 //stack[si + IREPEAT_COUNT]--; 390 stack[e.getSi()].decreaseRepeatCount(); 391 } else if (e.type == MEM_END){ 392 repeatStk[memStartStk + e.getMemNum()] = e.getMemStart(); 393 repeatStk[memEndStk + e.getMemNum()] = e.getMemStart(); 394 } else if (Config.USE_COMBINATION_EXPLOSION_CHECK) { 395 if (e.type == STATE_CHECK_MARK) stateCheckMark(); 396 } 397 } 398 } 399 400 protected final void popTilLookBehindNot() { 401 while (true) { 402 stk--; 403 StackEntry e = stack[stk]; 404 405 if (e.type == LOOK_BEHIND_NOT) { 406 break; 407 } else if (e.type == MEM_START) { 408 repeatStk[memStartStk + e.getMemNum()] = e.getMemStart(); 409 repeatStk[memEndStk + e.getMemNum()] = e.getMemEnd(); 410 } else if (e.type == REPEAT_INC) { 411 //int si = stack[stk + IREPEAT_INC_SI]; 412 //stack[si + IREPEAT_COUNT]--; 413 stack[e.getSi()].decreaseRepeatCount(); 414 } else if (e.type == MEM_END) { 415 repeatStk[memStartStk + e.getMemNum()] = e.getMemStart(); 416 repeatStk[memEndStk + e.getMemNum()] = e.getMemEnd(); 417 } else if (Config.USE_COMBINATION_EXPLOSION_CHECK) { 418 if (e.type == STATE_CHECK_MARK) stateCheckMark(); 419 } 420 } 421 } 422 423 protected final int posEnd() { 424 int k = stk; 425 while (true) { 426 k--; 427 StackEntry e = stack[k]; 428 if ((e.type & MASK_TO_VOID_TARGET) != 0) { 429 e.type = VOID; 430 } else if (e.type == POS) { 431 e.type = VOID; 432 break; 433 } 434 } 435 return k; 436 } 437 438 protected final void stopBtEnd() { 439 int k = stk; 440 while (true) { 441 k--; 442 StackEntry e = stack[k]; 443 444 if ((e.type & MASK_TO_VOID_TARGET) != 0) { 445 e.type = VOID; 446 } else if (e.type == STOP_BT) { 447 e.type = VOID; 448 break; 449 } 450 } 451 } 452 453 // int for consistency with other null check routines 454 protected final int nullCheck(int id, int s) { 455 int k = stk; 456 while (true) { 457 k--; 458 StackEntry e = stack[k]; 459 460 if (e.type == NULL_CHECK_START) { 461 if (e.getNullCheckNum() == id) { 462 return e.getNullCheckPStr() == s ? 1 : 0; 463 } 464 } 465 } 466 } 467 468 protected final int nullCheckRec(int id, int s) { 469 int level = 0; 470 int k = stk; 471 while (true) { 472 k--; 473 StackEntry e = stack[k]; 474 475 if (e.type == NULL_CHECK_START) { 476 if (e.getNullCheckNum() == id) { 477 if (level == 0) { 478 return e.getNullCheckPStr() == s ? 1 : 0; 479 } else { 480 level--; 481 } 482 } 483 } else if (e.type == NULL_CHECK_END) { 484 level++; 485 } 486 } 487 } 488 489 protected final int nullCheckMemSt(int id, int s) { 490 int k = stk; 491 int isNull; 492 while (true) { 493 k--; 494 StackEntry e = stack[k]; 495 496 if (e.type == NULL_CHECK_START) { 497 if (e.getNullCheckNum() == id) { 498 if (e.getNullCheckPStr() != s) { 499 isNull = 0; 500 break; 501 } else { 502 int endp; 503 isNull = 1; 504 while (k < stk) { 505 if (e.type == MEM_START) { 506 if (e.getMemEnd() == INVALID_INDEX) { 507 isNull = 0; 508 break; 509 } 510 if (bsAt(regex.btMemEnd, e.getMemNum())) { 511 endp = stack[e.getMemEnd()].getMemPStr(); 512 } else { 513 endp = e.getMemEnd(); 514 } 515 if (stack[e.getMemStart()].getMemPStr() != endp) { 516 isNull = 0; 517 break; 518 } else if (endp != s) { 519 isNull = -1; /* empty, but position changed */ 520 } 521 } 522 k++; 523 e = stack[k]; // !! 524 } 525 break; 526 } 527 } 528 } 529 } 530 return isNull; 531 } 532 533 protected final int nullCheckMemStRec(int id, int s) { 534 int level = 0; 535 int k = stk; 536 int isNull; 537 while (true) { 538 k--; 539 StackEntry e = stack[k]; 540 541 if (e.type == NULL_CHECK_START) { 542 if (e.getNullCheckNum() == id) { 543 if (level == 0) { 544 if (e.getNullCheckPStr() != s) { 545 isNull = 0; 546 break; 547 } else { 548 int endp; 549 isNull = 1; 550 while (k < stk) { 551 if (e.type == MEM_START) { 552 if (e.getMemEnd() == INVALID_INDEX) { 553 isNull = 0; 554 break; 555 } 556 if (bsAt(regex.btMemEnd, e.getMemNum())) { 557 endp = stack[e.getMemEnd()].getMemPStr(); 558 } else { 559 endp = e.getMemEnd(); 560 } 561 if (stack[e.getMemStart()].getMemPStr() != endp) { 562 isNull = 0; 563 break; 564 } else if (endp != s) { 565 isNull = -1;; /* empty, but position changed */ 566 } 567 } 568 k++; 569 e = stack[k]; 570 } 571 break; 572 } 573 } else { 574 level--; 575 } 576 } 577 } else if (e.type == NULL_CHECK_END) { 578 if (e.getNullCheckNum() == id) level++; 579 } 580 } 581 return isNull; 582 } 583 584 protected final int getRepeat(int id) { 585 int level = 0; 586 int k = stk; 587 while (true) { 588 k--; 589 StackEntry e = stack[k]; 590 591 if (e.type == REPEAT) { 592 if (level == 0) { 593 if (e.getRepeatNum() == id) return k; 594 } 595 } else if (e.type == CALL_FRAME) { 596 level--; 597 } else if (e.type == RETURN) { 598 level++; 599 } 600 } 601 } 602 603 protected final int sreturn() { 604 int level = 0; 605 int k = stk; 606 while (true) { 607 k--; 608 StackEntry e = stack[k]; 609 610 if (e.type == CALL_FRAME) { 611 if (level == 0) { 612 return e.getCallFrameRetAddr(); 613 } else { 614 level--; 615 } 616 } else if (e.type == RETURN) { 617 level++; 618 } 619 } 620 } 621 }