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 }