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 import static jdk.nashorn.internal.runtime.regexp.joni.Option.isDynamic;
  24 import static jdk.nashorn.internal.runtime.regexp.joni.Option.isIgnoreCase;
  25 import static jdk.nashorn.internal.runtime.regexp.joni.Option.isMultiline;
  26 import static jdk.nashorn.internal.runtime.regexp.joni.ast.QuantifierNode.isRepeatInfinite;
  27 
  28 import jdk.nashorn.internal.runtime.regexp.joni.ast.AnchorNode;
  29 import jdk.nashorn.internal.runtime.regexp.joni.ast.BackRefNode;
  30 import jdk.nashorn.internal.runtime.regexp.joni.ast.CClassNode;
  31 import jdk.nashorn.internal.runtime.regexp.joni.ast.CTypeNode;
  32 import jdk.nashorn.internal.runtime.regexp.joni.ast.CallNode;
  33 import jdk.nashorn.internal.runtime.regexp.joni.ast.ConsAltNode;
  34 import jdk.nashorn.internal.runtime.regexp.joni.ast.EncloseNode;
  35 import jdk.nashorn.internal.runtime.regexp.joni.ast.Node;
  36 import jdk.nashorn.internal.runtime.regexp.joni.ast.QuantifierNode;
  37 import jdk.nashorn.internal.runtime.regexp.joni.ast.StringNode;
  38 import jdk.nashorn.internal.runtime.regexp.joni.constants.AnchorType;
  39 import jdk.nashorn.internal.runtime.regexp.joni.constants.EncloseType;
  40 import jdk.nashorn.internal.runtime.regexp.joni.constants.NodeType;
  41 import jdk.nashorn.internal.runtime.regexp.joni.constants.OPCode;
  42 import jdk.nashorn.internal.runtime.regexp.joni.constants.OPSize;
  43 import jdk.nashorn.internal.runtime.regexp.joni.constants.TargetInfo;
  44 import jdk.nashorn.internal.runtime.regexp.joni.encoding.CharacterType;
  45 
  46 final class ArrayCompiler extends Compiler {
  47     private int[] code;
  48     private int codeLength;
  49 
  50     private char[][] templates;
  51     private int templateNum;
  52 
  53     ArrayCompiler(Analyser analyser) {
  54         super(analyser);
  55     }
  56 
  57     @Override
  58     protected final void prepare() {
  59         int codeSize = Config.USE_STRING_TEMPLATES ? 8 : ((analyser.getEnd() - analyser.getBegin()) * 2 + 2);
  60         code = new int[codeSize];
  61         codeLength = 0;
  62     }
  63 
  64     @Override
  65     protected final void finish() {
  66         addOpcode(OPCode.END);
  67         addOpcode(OPCode.FINISH); // for stack bottom
  68 
  69         regex.code = code;
  70         regex.codeLength = codeLength;
  71         regex.templates = templates;
  72         regex.templateNum = templateNum;
  73         regex.factory = MatcherFactory.DEFAULT;
  74 
  75         if (Config.USE_SUBEXP_CALL && analyser.env.unsetAddrList != null) {
  76             analyser.env.unsetAddrList.fix(regex);
  77             analyser.env.unsetAddrList = null;
  78         }
  79     }
  80 
  81     @Override
  82     protected void compileAltNode(ConsAltNode node) {
  83         ConsAltNode aln = node;
  84         int len = 0;
  85 
  86         do {
  87             len += compileLengthTree(aln.car);
  88             if (aln.cdr != null) {
  89                 len += OPSize.PUSH + OPSize.JUMP;
  90             }
  91         } while ((aln = aln.cdr) != null);
  92 
  93         int pos = codeLength + len;  /* goal position */
  94 
  95         aln = node;
  96         do {
  97             len = compileLengthTree(aln.car);
  98             if (aln.cdr != null) {
  99                 addOpcodeRelAddr(OPCode.PUSH, len + OPSize.JUMP);
 100             }
 101             compileTree(aln.car);
 102             if (aln.cdr != null) {
 103                 len = pos - (codeLength + OPSize.JUMP);
 104                 addOpcodeRelAddr(OPCode.JUMP, len);
 105             }
 106         } while ((aln = aln.cdr) != null);
 107     }
 108 
 109     private boolean isNeedStrLenOpExact(int op) {
 110         return  op == OPCode.EXACTN         ||
 111                 op == OPCode.EXACTMB2N      ||
 112                 op == OPCode.EXACTMB3N      ||
 113                 op == OPCode.EXACTMBN       ||
 114                 op == OPCode.EXACTN_IC      ||
 115                 op == OPCode.EXACTN_IC_SB;
 116     }
 117 
 118     private boolean opTemplated(int op) {
 119         return isNeedStrLenOpExact(op);
 120     }
 121 
 122     private int selectStrOpcode(int mbLength, int strLength, boolean ignoreCase) {
 123         int op;
 124 
 125         if (ignoreCase) {
 126             switch(strLength) {
 127             case 1: op = OPCode.EXACT1_IC; break;
 128             default:op = OPCode.EXACTN_IC; break;
 129             } // switch
 130         } else {
 131             switch (mbLength) {
 132             case 1:
 133                 switch (strLength) {
 134                 case 1: op = OPCode.EXACT1; break;
 135                 case 2: op = OPCode.EXACT2; break;
 136                 case 3: op = OPCode.EXACT3; break;
 137                 case 4: op = OPCode.EXACT4; break;
 138                 case 5: op = OPCode.EXACT5; break;
 139                 default:op = OPCode.EXACTN; break;
 140                 } // inner switch
 141                 break;
 142             case 2:
 143                 switch (strLength) {
 144                 case 1: op = OPCode.EXACTMB2N1; break;
 145                 case 2: op = OPCode.EXACTMB2N2; break;
 146                 case 3: op = OPCode.EXACTMB2N3; break;
 147                 default:op = OPCode.EXACTMB2N;  break;
 148                 } // inner switch
 149                 break;
 150             case 3:
 151                 op = OPCode.EXACTMB3N;
 152                 break;
 153             default:
 154                 op = OPCode.EXACTMBN;
 155             } // switch
 156         }
 157         return op;
 158     }
 159 
 160     private void compileTreeEmptyCheck(Node node, int emptyInfo) {
 161         int savedNumNullCheck = regex.numNullCheck;
 162 
 163         if (emptyInfo != 0) {
 164             addOpcode(OPCode.NULL_CHECK_START);
 165             addMemNum(regex.numNullCheck); /* NULL CHECK ID */
 166             regex.numNullCheck++;
 167         }
 168 
 169         compileTree(node);
 170 
 171         if (emptyInfo != 0) {
 172             switch(emptyInfo) {
 173             case TargetInfo.IS_EMPTY:
 174                 addOpcode(OPCode.NULL_CHECK_END);
 175                 break;
 176             case TargetInfo.IS_EMPTY_MEM:
 177                 addOpcode(OPCode.NULL_CHECK_END_MEMST);
 178                 break;
 179             case TargetInfo.IS_EMPTY_REC:
 180                 addOpcode(OPCode.NULL_CHECK_END_MEMST_PUSH);
 181                 break;
 182             } // switch
 183 
 184             addMemNum(savedNumNullCheck); /* NULL CHECK ID */
 185         }
 186     }
 187 
 188     private int addCompileStringlength(char[] chars, int p, int mbLength, int strLength, boolean ignoreCase) {
 189         int op = selectStrOpcode(mbLength, strLength, ignoreCase);
 190         int len = OPSize.OPCODE;
 191 
 192         if (Config.USE_STRING_TEMPLATES && opTemplated(op)) {
 193             // string length, template index, template string pointer
 194             len += OPSize.LENGTH + OPSize.INDEX + OPSize.INDEX;
 195         } else {
 196             if (isNeedStrLenOpExact(op)) len += OPSize.LENGTH;
 197             len += mbLength * strLength;
 198         }
 199         if (op == OPCode.EXACTMBN) len += OPSize.LENGTH;
 200         return len;
 201     }
 202 
 203     @Override
 204     protected final void addCompileString(char[] chars, int p, int mbLength, int strLength, boolean ignoreCase) {
 205         int op = selectStrOpcode(mbLength, strLength, ignoreCase);
 206         addOpcode(op);
 207 
 208         if (op == OPCode.EXACTMBN) addLength(mbLength);
 209 
 210         if (isNeedStrLenOpExact(op)) {
 211             if (op == OPCode.EXACTN_IC || op == OPCode.EXACTN_IC_SB) {
 212                 addLength(mbLength * strLength);
 213             } else {
 214                 addLength(strLength);
 215             }
 216         }
 217 
 218         if (Config.USE_STRING_TEMPLATES && opTemplated(op)) {
 219             addInt(templateNum);
 220             addInt(p);
 221             addTemplate(chars);
 222         } else {
 223             addChars(chars, p, mbLength * strLength);
 224         }
 225     }
 226 
 227     private int compileLengthStringNode(Node node) {
 228         StringNode sn = (StringNode)node;
 229         if (sn.length() <= 0) return 0;
 230         boolean ambig = sn.isAmbig();
 231 
 232         int p, prev;
 233         p = prev = sn.p;
 234         int end = sn.end;
 235         char[] chars = sn.chars;
 236         p++;
 237 
 238         int slen = 1;
 239         int rlen = 0;
 240 
 241         while (p < end) {
 242             slen++;
 243             p++;
 244         }
 245         int r = addCompileStringlength(chars, prev, 1, slen, ambig);
 246         rlen += r;
 247         return rlen;
 248     }
 249 
 250     private int compileLengthStringRawNode(StringNode sn) {
 251         if (sn.length() <= 0) return 0;
 252         return addCompileStringlength(sn.chars, sn.p, 1 /*sb*/, sn.length(), false);
 253     }
 254 
 255     private void addMultiByteCClass(CodeRangeBuffer mbuf) {
 256         addLength(mbuf.used);
 257         addInts(mbuf.p, mbuf.used);
 258     }
 259 
 260     private int compileLengthCClassNode(CClassNode cc) {
 261         if (cc.isShare()) return OPSize.OPCODE + OPSize.POINTER;
 262 
 263         int len;
 264         if (cc.mbuf == null) {
 265             len = OPSize.OPCODE + BitSet.BITSET_SIZE;
 266         } else {
 267             if (cc.bs.isEmpty()) {
 268                 len = OPSize.OPCODE;
 269             } else {
 270                 len = OPSize.OPCODE + BitSet.BITSET_SIZE;
 271             }
 272 
 273             len += OPSize.LENGTH + cc.mbuf.used;
 274         }
 275         return len;
 276     }
 277 
 278     @Override
 279     protected void compileCClassNode(CClassNode cc) {
 280         if (cc.isShare()) { // shared char class
 281             addOpcode(OPCode.CCLASS_NODE);
 282             addPointer(cc);
 283             return;
 284         }
 285 
 286         if (cc.mbuf == null) {
 287             if (cc.isNot()) {
 288                 addOpcode(OPCode.CCLASS_NOT);
 289             } else {
 290                 addOpcode(OPCode.CCLASS);
 291             }
 292             addInts(cc.bs.bits, BitSet.BITSET_SIZE); // add_bitset
 293         } else {
 294             if (cc.bs.isEmpty()) {
 295                 if (cc.isNot()) {
 296                     addOpcode(OPCode.CCLASS_MB_NOT);
 297                 } else {
 298                     addOpcode(OPCode.CCLASS_MB);
 299                 }
 300                 addMultiByteCClass(cc.mbuf);
 301             } else {
 302                 if (cc.isNot()) {
 303                     addOpcode(OPCode.CCLASS_MIX_NOT);
 304                 } else {
 305                     addOpcode(OPCode.CCLASS_MIX);
 306                 }
 307                 // store the bit set and mbuf themself!
 308                 addInts(cc.bs.bits, BitSet.BITSET_SIZE); // add_bitset
 309                 addMultiByteCClass(cc.mbuf);
 310             }
 311         }
 312     }
 313 
 314     @Override
 315     protected void compileCTypeNode(CTypeNode node) {
 316         CTypeNode cn = node;
 317         int op;
 318         switch (cn.ctype) {
 319         case CharacterType.WORD:
 320             if (cn.not) {
 321                 op = OPCode.NOT_WORD;
 322             } else {
 323                 op = OPCode.WORD;
 324             }
 325             break;
 326 
 327         default:
 328             newInternalException(ERR_PARSER_BUG);
 329             return; // not reached
 330         } // inner switch
 331         addOpcode(op);
 332     }
 333 
 334     @Override
 335     protected void compileAnyCharNode() {
 336         if (isMultiline(regex.options)) {
 337             addOpcode(OPCode.ANYCHAR_ML);
 338         } else {
 339             addOpcode(OPCode.ANYCHAR);
 340         }
 341     }
 342 
 343     @Override
 344     protected void compileCallNode(CallNode node) {
 345         addOpcode(OPCode.CALL);
 346         node.unsetAddrList.add(codeLength, node.target);
 347         addAbsAddr(0); /*dummy addr.*/
 348     }
 349 
 350     @Override
 351     protected void compileBackrefNode(BackRefNode node) {
 352         BackRefNode br = node;
 353         if (Config.USE_BACKREF_WITH_LEVEL && br.isNestLevel()) {
 354             addOpcode(OPCode.BACKREF_WITH_LEVEL);
 355             addOption(regex.options & Option.IGNORECASE);
 356             addLength(br.nestLevel);
 357             // !goto add_bacref_mems;!
 358             addLength(br.backNum);
 359             for (int i=br.backNum-1; i>=0; i--) addMemNum(br.back[i]);
 360             return;
 361         } else { // USE_BACKREF_AT_LEVEL
 362             if (br.backNum == 1) {
 363                 if (isIgnoreCase(regex.options)) {
 364                     addOpcode(OPCode.BACKREFN_IC);
 365                     addMemNum(br.back[0]);
 366                 } else {
 367                     switch (br.back[0]) {
 368                     case 1:
 369                         addOpcode(OPCode.BACKREF1);
 370                         break;
 371                     case 2:
 372                         addOpcode(OPCode.BACKREF2);
 373                         break;
 374                     default:
 375                         addOpcode(OPCode.BACKREFN);
 376                         addOpcode(br.back[0]);
 377                         break;
 378                     } // switch
 379                 }
 380             } else {
 381                 if (isIgnoreCase(regex.options)) {
 382                     addOpcode(OPCode.BACKREF_MULTI_IC);
 383                 } else {
 384                     addOpcode(OPCode.BACKREF_MULTI);
 385                 }
 386                 // !add_bacref_mems:!
 387                 addLength(br.backNum);
 388                 for (int i=br.backNum-1; i>=0; i--) addMemNum(br.back[i]);
 389             }
 390         }
 391     }
 392 
 393     private static final int REPEAT_RANGE_ALLOC = 8;
 394     private void entryRepeatRange(int id, int lower, int upper) {
 395         if (regex.repeatRangeLo == null) {
 396             regex.repeatRangeLo = new int[REPEAT_RANGE_ALLOC];
 397             regex.repeatRangeHi = new int[REPEAT_RANGE_ALLOC];
 398         } else if (id >= regex.repeatRangeLo.length){
 399             int[]tmp = new int[regex.repeatRangeLo.length + REPEAT_RANGE_ALLOC];
 400             System.arraycopy(regex.repeatRangeLo, 0, tmp, 0, regex.repeatRangeLo.length);
 401             regex.repeatRangeLo = tmp;
 402             tmp = new int[regex.repeatRangeHi.length + REPEAT_RANGE_ALLOC];
 403             System.arraycopy(regex.repeatRangeHi, 0, tmp, 0, regex.repeatRangeHi.length);
 404             regex.repeatRangeHi = tmp;
 405         }
 406 
 407         regex.repeatRangeLo[id] = lower;
 408         regex.repeatRangeHi[id] = isRepeatInfinite(upper) ? 0x7fffffff : upper;
 409     }
 410 
 411     private void compileRangeRepeatNode(QuantifierNode qn, int targetLen, int emptyInfo) {
 412         int numRepeat = regex.numRepeat;
 413         addOpcode(qn.greedy ? OPCode.REPEAT : OPCode.REPEAT_NG);
 414         addMemNum(numRepeat); /* OP_REPEAT ID */
 415         regex.numRepeat++;
 416         addRelAddr(targetLen + OPSize.REPEAT_INC);
 417 
 418         entryRepeatRange(numRepeat, qn.lower, qn.upper);
 419 
 420         compileTreeEmptyCheck(qn.target, emptyInfo);
 421 
 422         if ((Config.USE_SUBEXP_CALL && regex.numCall > 0) || qn.isInRepeat()) {
 423             addOpcode(qn.greedy ? OPCode.REPEAT_INC_SG : OPCode.REPEAT_INC_NG_SG);
 424         } else {
 425             addOpcode(qn.greedy ? OPCode.REPEAT_INC : OPCode.REPEAT_INC_NG);
 426         }
 427 
 428         addMemNum(numRepeat); /* OP_REPEAT ID */
 429     }
 430 
 431     private static final int QUANTIFIER_EXPAND_LIMIT_SIZE   = 50; // was 50
 432 
 433     private static boolean cknOn(int ckn) {
 434         return ckn > 0;
 435     }
 436 
 437     private int compileCECLengthQuantifierNode(QuantifierNode qn) {
 438         boolean infinite = isRepeatInfinite(qn.upper);
 439         int emptyInfo = qn.targetEmptyInfo;
 440 
 441         int tlen = compileLengthTree(qn.target);
 442         int ckn = regex.numCombExpCheck > 0 ? qn.combExpCheckNum : 0;
 443         int cklen = cknOn(ckn) ? OPSize.STATE_CHECK_NUM : 0;
 444 
 445         /* anychar repeat */
 446         if (qn.target.getType() == NodeType.CANY) {
 447             if (qn.greedy && infinite) {
 448                 if (qn.nextHeadExact != null && !cknOn(ckn)) {
 449                     return OPSize.ANYCHAR_STAR_PEEK_NEXT + tlen * qn.lower + cklen;
 450                 } else {
 451                     return OPSize.ANYCHAR_STAR + tlen * qn.lower + cklen;
 452                 }
 453             }
 454         }
 455 
 456         int modTLen;
 457         if (emptyInfo != 0) {
 458             modTLen = tlen + (OPSize.NULL_CHECK_START + OPSize.NULL_CHECK_END);
 459         } else {
 460             modTLen = tlen;
 461         }
 462 
 463         int len;
 464         if (infinite && qn.lower <= 1) {
 465             if (qn.greedy) {
 466                 if (qn.lower == 1) {
 467                     len = OPSize.JUMP;
 468                 } else {
 469                     len = 0;
 470                 }
 471                 len += OPSize.PUSH + cklen + modTLen + OPSize.JUMP;
 472             } else {
 473                 if (qn.lower == 0) {
 474                     len = OPSize.JUMP;
 475                 } else {
 476                     len = 0;
 477                 }
 478                 len += modTLen + OPSize.PUSH + cklen;
 479             }
 480         } else if (qn.upper == 0) {
 481             if (qn.isRefered) { /* /(?<n>..){0}/ */
 482                 len = OPSize.JUMP + tlen;
 483             } else {
 484                 len = 0;
 485             }
 486         } else if (qn.upper == 1 && qn.greedy) {
 487             if (qn.lower == 0) {
 488                 if (cknOn(ckn)) {
 489                     len = OPSize.STATE_CHECK_PUSH + tlen;
 490                 } else {
 491                     len = OPSize.PUSH + tlen;
 492                 }
 493             } else {
 494                 len = tlen;
 495             }
 496         } else if (!qn.greedy && qn.upper == 1 && qn.lower == 0) { /* '??' */
 497             len = OPSize.PUSH + cklen + OPSize.JUMP + tlen;
 498         } else {
 499             len = OPSize.REPEAT_INC + modTLen + OPSize.OPCODE + OPSize.RELADDR + OPSize.MEMNUM;
 500 
 501             if (cknOn(ckn)) {
 502                 len += OPSize.STATE_CHECK;
 503             }
 504         }
 505         return len;
 506     }
 507 
 508     @Override
 509     protected void compileCECQuantifierNode(QuantifierNode qn) {
 510         boolean infinite = isRepeatInfinite(qn.upper);
 511         int emptyInfo = qn.targetEmptyInfo;
 512 
 513         int tlen = compileLengthTree(qn.target);
 514 
 515         int ckn = regex.numCombExpCheck > 0 ? qn.combExpCheckNum : 0;
 516 
 517         if (qn.isAnyCharStar()) {
 518             compileTreeNTimes(qn.target, qn.lower);
 519             if (qn.nextHeadExact != null && !cknOn(ckn)) {
 520                 if (isMultiline(regex.options)) {
 521                     addOpcode(OPCode.ANYCHAR_ML_STAR_PEEK_NEXT);
 522                 } else {
 523                     addOpcode(OPCode.ANYCHAR_STAR_PEEK_NEXT);
 524                 }
 525                 if (cknOn(ckn)) {
 526                     addStateCheckNum(ckn);
 527                 }
 528                 StringNode sn = (StringNode)qn.nextHeadExact;
 529                 addChars(sn.chars, sn.p, 1);
 530                 return;
 531             } else {
 532                 if (isMultiline(regex.options)) {
 533                     if (cknOn(ckn)) {
 534                         addOpcode(OPCode.STATE_CHECK_ANYCHAR_ML_STAR);
 535                     } else {
 536                         addOpcode(OPCode.ANYCHAR_ML_STAR);
 537                     }
 538                 } else {
 539                     if (cknOn(ckn)) {
 540                         addOpcode(OPCode.STATE_CHECK_ANYCHAR_STAR);
 541                     } else {
 542                         addOpcode(OPCode.ANYCHAR_STAR);
 543                     }
 544                 }
 545                 if (cknOn(ckn)) {
 546                     addStateCheckNum(ckn);
 547                 }
 548                 return;
 549             }
 550         }
 551 
 552         int modTLen;
 553         if (emptyInfo != 0) {
 554             modTLen = tlen + (OPSize.NULL_CHECK_START + OPSize.NULL_CHECK_END);
 555         } else {
 556             modTLen = tlen;
 557         }
 558         if (infinite && qn.lower <= 1) {
 559             if (qn.greedy) {
 560                 if (qn.lower == 1) {
 561                     addOpcodeRelAddr(OPCode.JUMP, cknOn(ckn) ? OPSize.STATE_CHECK_PUSH :
 562                                                                      OPSize.PUSH);
 563                 }
 564                 if (cknOn(ckn)) {
 565                     addOpcode(OPCode.STATE_CHECK_PUSH);
 566                     addStateCheckNum(ckn);
 567                     addRelAddr(modTLen + OPSize.JUMP);
 568                 } else {
 569                     addOpcodeRelAddr(OPCode.PUSH, modTLen + OPSize.JUMP);
 570                 }
 571                 compileTreeEmptyCheck(qn.target, emptyInfo);
 572                 addOpcodeRelAddr(OPCode.JUMP, -(modTLen + OPSize.JUMP + (cknOn(ckn) ?
 573                                                                                OPSize.STATE_CHECK_PUSH :
 574                                                                                OPSize.PUSH)));
 575             } else {
 576                 if (qn.lower == 0) {
 577                     addOpcodeRelAddr(OPCode.JUMP, modTLen);
 578                 }
 579                 compileTreeEmptyCheck(qn.target, emptyInfo);
 580                 if (cknOn(ckn)) {
 581                     addOpcode(OPCode.STATE_CHECK_PUSH_OR_JUMP);
 582                     addStateCheckNum(ckn);
 583                     addRelAddr(-(modTLen + OPSize.STATE_CHECK_PUSH_OR_JUMP));
 584                 } else {
 585                     addOpcodeRelAddr(OPCode.PUSH, -(modTLen + OPSize.PUSH));
 586                 }
 587             }
 588         } else if (qn.upper == 0) {
 589             if (qn.isRefered) { /* /(?<n>..){0}/ */
 590                 addOpcodeRelAddr(OPCode.JUMP, tlen);
 591                 compileTree(qn.target);
 592             } // else r=0 ???
 593         } else if (qn.upper == 1 && qn.greedy) {
 594             if (qn.lower == 0) {
 595                 if (cknOn(ckn)) {
 596                     addOpcode(OPCode.STATE_CHECK_PUSH);
 597                     addStateCheckNum(ckn);
 598                     addRelAddr(tlen);
 599                 } else {
 600                     addOpcodeRelAddr(OPCode.PUSH, tlen);
 601                 }
 602             }
 603             compileTree(qn.target);
 604         } else if (!qn.greedy && qn.upper == 1 && qn.lower == 0){ /* '??' */
 605             if (cknOn(ckn)) {
 606                 addOpcode(OPCode.STATE_CHECK_PUSH);
 607                 addStateCheckNum(ckn);
 608                 addRelAddr(OPSize.JUMP);
 609             } else {
 610                 addOpcodeRelAddr(OPCode.PUSH, OPSize.JUMP);
 611             }
 612 
 613             addOpcodeRelAddr(OPCode.JUMP, tlen);
 614             compileTree(qn.target);
 615         } else {
 616             compileRangeRepeatNode(qn, modTLen, emptyInfo);
 617             if (cknOn(ckn)) {
 618                 addOpcode(OPCode.STATE_CHECK);
 619                 addStateCheckNum(ckn);
 620             }
 621         }
 622     }
 623 
 624     private int compileNonCECLengthQuantifierNode(QuantifierNode qn) {
 625         boolean infinite = isRepeatInfinite(qn.upper);
 626         int emptyInfo = qn.targetEmptyInfo;
 627 
 628         int tlen = compileLengthTree(qn.target);
 629 
 630         /* anychar repeat */
 631         if (qn.target.getType() == NodeType.CANY) {
 632             if (qn.greedy && infinite) {
 633                 if (qn.nextHeadExact != null) {
 634                     return OPSize.ANYCHAR_STAR_PEEK_NEXT + tlen * qn.lower;
 635                 } else {
 636                     return OPSize.ANYCHAR_STAR + tlen * qn.lower;
 637                 }
 638             }
 639         }
 640 
 641         int modTLen = 0;
 642         if (emptyInfo != 0) {
 643             modTLen = tlen + (OPSize.NULL_CHECK_START + OPSize.NULL_CHECK_END);
 644         } else {
 645             modTLen = tlen;
 646         }
 647 
 648         int len;
 649         if (infinite && (qn.lower <= 1 || tlen * qn.lower <= QUANTIFIER_EXPAND_LIMIT_SIZE)) {
 650             if (qn.lower == 1 && tlen > QUANTIFIER_EXPAND_LIMIT_SIZE) {
 651                 len = OPSize.JUMP;
 652             } else {
 653                 len = tlen * qn.lower;
 654             }
 655 
 656             if (qn.greedy) {
 657                 if (qn.headExact != null) {
 658                     len += OPSize.PUSH_OR_JUMP_EXACT1 + modTLen + OPSize.JUMP;
 659                 } else if (qn.nextHeadExact != null) {
 660                     len += OPSize.PUSH_IF_PEEK_NEXT + modTLen + OPSize.JUMP;
 661                 } else {
 662                     len += OPSize.PUSH + modTLen + OPSize.JUMP;
 663                 }
 664             } else {
 665                 len += OPSize.JUMP + modTLen + OPSize.PUSH;
 666             }
 667 
 668         } else if (qn.upper == 0 && qn.isRefered) { /* /(?<n>..){0}/ */
 669             len = OPSize.JUMP + tlen;
 670         } else if (!infinite && qn.greedy &&
 671                   (qn.upper == 1 || (tlen + OPSize.PUSH) * qn.upper <= QUANTIFIER_EXPAND_LIMIT_SIZE )) {
 672             len = tlen * qn.lower;
 673             len += (OPSize.PUSH + tlen) * (qn.upper - qn.lower);
 674         } else if (!qn.greedy && qn.upper == 1 && qn.lower == 0) { /* '??' */
 675             len = OPSize.PUSH + OPSize.JUMP + tlen;
 676         } else {
 677             len = OPSize.REPEAT_INC + modTLen + OPSize.OPCODE + OPSize.RELADDR + OPSize.MEMNUM;
 678         }
 679         return len;
 680     }
 681 
 682     @Override
 683     protected void compileNonCECQuantifierNode(QuantifierNode qn) {
 684         boolean infinite = isRepeatInfinite(qn.upper);
 685         int emptyInfo = qn.targetEmptyInfo;
 686 
 687         int tlen = compileLengthTree(qn.target);
 688 
 689         if (qn.isAnyCharStar()) {
 690             compileTreeNTimes(qn.target, qn.lower);
 691             if (qn.nextHeadExact != null) {
 692                 if (isMultiline(regex.options)) {
 693                     addOpcode(OPCode.ANYCHAR_ML_STAR_PEEK_NEXT);
 694                 } else {
 695                     addOpcode(OPCode.ANYCHAR_STAR_PEEK_NEXT);
 696                 }
 697                 StringNode sn = (StringNode)qn.nextHeadExact;
 698                 addChars(sn.chars, sn.p, 1);
 699                 return;
 700             } else {
 701                 if (isMultiline(regex.options)) {
 702                     addOpcode(OPCode.ANYCHAR_ML_STAR);
 703                 } else {
 704                     addOpcode(OPCode.ANYCHAR_STAR);
 705                 }
 706                 return;
 707             }
 708         }
 709 
 710         int modTLen;
 711         if (emptyInfo != 0) {
 712             modTLen = tlen + (OPSize.NULL_CHECK_START + OPSize.NULL_CHECK_END);
 713         } else {
 714             modTLen = tlen;
 715         }
 716         if (infinite && (qn.lower <= 1 || tlen * qn.lower <= QUANTIFIER_EXPAND_LIMIT_SIZE)) {
 717             if (qn.lower == 1 && tlen > QUANTIFIER_EXPAND_LIMIT_SIZE) {
 718                 if (qn.greedy) {
 719                     if (qn.headExact != null) {
 720                         addOpcodeRelAddr(OPCode.JUMP, OPSize.PUSH_OR_JUMP_EXACT1);
 721                     } else if (qn.nextHeadExact != null) {
 722                         addOpcodeRelAddr(OPCode.JUMP, OPSize.PUSH_IF_PEEK_NEXT);
 723                     } else {
 724                         addOpcodeRelAddr(OPCode.JUMP, OPSize.PUSH);
 725                     }
 726                 } else {
 727                     addOpcodeRelAddr(OPCode.JUMP, OPSize.JUMP);
 728                 }
 729             } else {
 730                 compileTreeNTimes(qn.target, qn.lower);
 731             }
 732 
 733             if (qn.greedy) {
 734                 if (qn.headExact != null) {
 735                     addOpcodeRelAddr(OPCode.PUSH_OR_JUMP_EXACT1, modTLen + OPSize.JUMP);
 736                     StringNode sn = (StringNode)qn.headExact;
 737                     addChars(sn.chars, sn.p, 1);
 738                     compileTreeEmptyCheck(qn.target, emptyInfo);
 739                     addOpcodeRelAddr(OPCode.JUMP, -(modTLen + OPSize.JUMP + OPSize.PUSH_OR_JUMP_EXACT1));
 740                 } else if (qn.nextHeadExact != null) {
 741                     addOpcodeRelAddr(OPCode.PUSH_IF_PEEK_NEXT, modTLen + OPSize.JUMP);
 742                     StringNode sn = (StringNode)qn.nextHeadExact;
 743                     addChars(sn.chars, sn.p, 1);
 744                     compileTreeEmptyCheck(qn.target, emptyInfo);
 745                     addOpcodeRelAddr(OPCode.JUMP, -(modTLen + OPSize.JUMP + OPSize.PUSH_IF_PEEK_NEXT));
 746                 } else {
 747                     addOpcodeRelAddr(OPCode.PUSH, modTLen + OPSize.JUMP);
 748                     compileTreeEmptyCheck(qn.target, emptyInfo);
 749                     addOpcodeRelAddr(OPCode.JUMP, -(modTLen + OPSize.JUMP + OPSize.PUSH));
 750                 }
 751             } else {
 752                 addOpcodeRelAddr(OPCode.JUMP, modTLen);
 753                 compileTreeEmptyCheck(qn.target, emptyInfo);
 754                 addOpcodeRelAddr(OPCode.PUSH, -(modTLen + OPSize.PUSH));
 755             }
 756         } else if (qn.upper == 0 && qn.isRefered) { /* /(?<n>..){0}/ */
 757             addOpcodeRelAddr(OPCode.JUMP, tlen);
 758             compileTree(qn.target);
 759         } else if (!infinite && qn.greedy &&
 760                   (qn.upper == 1 || (tlen + OPSize.PUSH) * qn.upper <= QUANTIFIER_EXPAND_LIMIT_SIZE)) {
 761             int n = qn.upper - qn.lower;
 762             compileTreeNTimes(qn.target, qn.lower);
 763 
 764             for (int i=0; i<n; i++) {
 765                 addOpcodeRelAddr(OPCode.PUSH, (n - i) * tlen + (n - i - 1) * OPSize.PUSH);
 766                 compileTree(qn.target);
 767             }
 768         } else if (!qn.greedy && qn.upper == 1 && qn.lower == 0) { /* '??' */
 769             addOpcodeRelAddr(OPCode.PUSH, OPSize.JUMP);
 770             addOpcodeRelAddr(OPCode.JUMP, tlen);
 771             compileTree(qn.target);
 772         } else {
 773             compileRangeRepeatNode(qn, modTLen, emptyInfo);
 774         }
 775     }
 776 
 777     private int compileLengthOptionNode(EncloseNode node) {
 778         int prev = regex.options;
 779         regex.options = node.option;
 780         int tlen = compileLengthTree(node.target);
 781         regex.options = prev;
 782 
 783         if (isDynamic(prev ^ node.option)) {
 784             return OPSize.SET_OPTION_PUSH + OPSize.SET_OPTION + OPSize.FAIL + tlen + OPSize.SET_OPTION;
 785         } else {
 786             return tlen;
 787         }
 788     }
 789 
 790     @Override
 791     protected void compileOptionNode(EncloseNode node) {
 792         int prev = regex.options;
 793 
 794         if (isDynamic(prev ^ node.option)) {
 795             addOpcodeOption(OPCode.SET_OPTION_PUSH, node.option);
 796             addOpcodeOption(OPCode.SET_OPTION, prev);
 797             addOpcode(OPCode.FAIL);
 798         }
 799 
 800         regex.options = node.option;
 801         compileTree(node.target);
 802         regex.options = prev;
 803 
 804         if (isDynamic(prev ^ node.option)) {
 805             addOpcodeOption(OPCode.SET_OPTION, prev);
 806         }
 807     }
 808 
 809     private int compileLengthEncloseNode(EncloseNode node) {
 810         if (node.isOption()) {
 811             return compileLengthOptionNode(node);
 812         }
 813 
 814         int tlen;
 815         if (node.target != null) {
 816             tlen = compileLengthTree(node.target);
 817         } else {
 818             tlen = 0;
 819         }
 820 
 821         int len;
 822         switch (node.type) {
 823         case EncloseType.MEMORY:
 824             if (Config.USE_SUBEXP_CALL && node.isCalled()) {
 825                 len = OPSize.MEMORY_START_PUSH + tlen + OPSize.CALL + OPSize.JUMP + OPSize.RETURN;
 826                 if (bsAt(regex.btMemEnd, node.regNum)) {
 827                     len += node.isRecursion() ? OPSize.MEMORY_END_PUSH_REC : OPSize.MEMORY_END_PUSH;
 828                 } else {
 829                     len += node.isRecursion() ? OPSize.MEMORY_END_REC : OPSize.MEMORY_END;
 830                 }
 831             } else { // USE_SUBEXP_CALL
 832                 if (bsAt(regex.btMemStart, node.regNum)) {
 833                     len = OPSize.MEMORY_START_PUSH;
 834                 } else {
 835                     len = OPSize.MEMORY_START;
 836                 }
 837                 len += tlen + (bsAt(regex.btMemEnd, node.regNum) ? OPSize.MEMORY_END_PUSH : OPSize.MEMORY_END);
 838             }
 839             break;
 840 
 841         case EncloseType.STOP_BACKTRACK:
 842             if (node.isStopBtSimpleRepeat()) {
 843                 QuantifierNode qn = (QuantifierNode)node.target;
 844                 tlen = compileLengthTree(qn.target);
 845                 len = tlen * qn.lower + OPSize.PUSH + tlen + OPSize.POP + OPSize.JUMP;
 846             } else {
 847                 len = OPSize.PUSH_STOP_BT + tlen + OPSize.POP_STOP_BT;
 848             }
 849             break;
 850 
 851         default:
 852             newInternalException(ERR_PARSER_BUG);
 853             return 0; // not reached
 854         } // switch
 855         return len;
 856     }
 857 
 858     @Override
 859     protected void compileEncloseNode(EncloseNode node) {
 860         int len;
 861         switch (node.type) {
 862         case EncloseType.MEMORY:
 863             if (Config.USE_SUBEXP_CALL) {
 864                 if (node.isCalled()) {
 865                     addOpcode(OPCode.CALL);
 866                     node.callAddr = codeLength + OPSize.ABSADDR + OPSize.JUMP;
 867                     node.setAddrFixed();
 868                     addAbsAddr(node.callAddr);
 869                     len = compileLengthTree(node.target);
 870                     len += OPSize.MEMORY_START_PUSH + OPSize.RETURN;
 871                     if (bsAt(regex.btMemEnd, node.regNum)) {
 872                         len += node.isRecursion() ? OPSize.MEMORY_END_PUSH_REC : OPSize.MEMORY_END_PUSH;
 873                     } else {
 874                         len += node.isRecursion() ? OPSize.MEMORY_END_REC : OPSize.MEMORY_END;
 875                     }
 876                     addOpcodeRelAddr(OPCode.JUMP, len);
 877                 }
 878             } // USE_SUBEXP_CALL
 879 
 880             if (bsAt(regex.btMemStart, node.regNum)) {
 881                 addOpcode(OPCode.MEMORY_START_PUSH);
 882             } else {
 883                 addOpcode(OPCode.MEMORY_START);
 884             }
 885 
 886             addMemNum(node.regNum);
 887             compileTree(node.target);
 888 
 889             if (Config.USE_SUBEXP_CALL && node.isCalled()) {
 890                 if (bsAt(regex.btMemEnd, node.regNum)) {
 891                     addOpcode(node.isRecursion() ? OPCode.MEMORY_END_PUSH_REC : OPCode.MEMORY_END_PUSH);
 892                 } else {
 893                     addOpcode(node.isRecursion() ? OPCode.MEMORY_END_REC : OPCode.MEMORY_END);
 894                 }
 895                 addMemNum(node.regNum);
 896                 addOpcode(OPCode.RETURN);
 897             } else { // USE_SUBEXP_CALL
 898                 if (bsAt(regex.btMemEnd, node.regNum)) {
 899                     addOpcode(OPCode.MEMORY_END_PUSH);
 900                 } else {
 901                     addOpcode(OPCode.MEMORY_END);
 902                 }
 903                 addMemNum(node.regNum);
 904             }
 905             break;
 906 
 907         case EncloseType.STOP_BACKTRACK:
 908             if (node.isStopBtSimpleRepeat()) {
 909                 QuantifierNode qn = (QuantifierNode)node.target;
 910 
 911                 compileTreeNTimes(qn.target, qn.lower);
 912 
 913                 len = compileLengthTree(qn.target);
 914                 addOpcodeRelAddr(OPCode.PUSH, len + OPSize.POP + OPSize.JUMP);
 915                 compileTree(qn.target);
 916                 addOpcode(OPCode.POP);
 917                 addOpcodeRelAddr(OPCode.JUMP, -(OPSize.PUSH + len + OPSize.POP + OPSize.JUMP));
 918             } else {
 919                 addOpcode(OPCode.PUSH_STOP_BT);
 920                 compileTree(node.target);
 921                 addOpcode(OPCode.POP_STOP_BT);
 922             }
 923             break;
 924 
 925         default:
 926             newInternalException(ERR_PARSER_BUG);
 927             break;
 928         } // switch
 929     }
 930 
 931     private int compileLengthAnchorNode(AnchorNode node) {
 932         int tlen;
 933         if (node.target != null) {
 934             tlen = compileLengthTree(node.target);
 935         } else {
 936             tlen = 0;
 937         }
 938 
 939         int len;
 940         switch (node.type) {
 941         case AnchorType.PREC_READ:
 942             len = OPSize.PUSH_POS + tlen + OPSize.POP_POS;
 943             break;
 944 
 945         case AnchorType.PREC_READ_NOT:
 946             len = OPSize.PUSH_POS_NOT + tlen + OPSize.FAIL_POS;
 947             break;
 948 
 949         case AnchorType.LOOK_BEHIND:
 950             len = OPSize.LOOK_BEHIND + tlen;
 951             break;
 952 
 953         case AnchorType.LOOK_BEHIND_NOT:
 954             len = OPSize.PUSH_LOOK_BEHIND_NOT + tlen + OPSize.FAIL_LOOK_BEHIND_NOT;
 955             break;
 956 
 957         default:
 958             len = OPSize.OPCODE;
 959             break;
 960         } // switch
 961         return len;
 962     }
 963 
 964     @Override
 965     protected void compileAnchorNode(AnchorNode node) {
 966         int len;
 967         int n;
 968 
 969         switch (node.type) {
 970         case AnchorType.BEGIN_BUF:          addOpcode(OPCode.BEGIN_BUF);            break;
 971         case AnchorType.END_BUF:            addOpcode(OPCode.END_BUF);              break;
 972         case AnchorType.BEGIN_LINE:         addOpcode(OPCode.BEGIN_LINE);           break;
 973         case AnchorType.END_LINE:           addOpcode(OPCode.END_LINE);             break;
 974         case AnchorType.SEMI_END_BUF:       addOpcode(OPCode.SEMI_END_BUF);         break;
 975         case AnchorType.BEGIN_POSITION:     addOpcode(OPCode.BEGIN_POSITION);       break;
 976 
 977         case AnchorType.WORD_BOUND:
 978             addOpcode(OPCode.WORD_BOUND);
 979             break;
 980 
 981         case AnchorType.NOT_WORD_BOUND:
 982             addOpcode(OPCode.NOT_WORD_BOUND);
 983             break;
 984 
 985         case AnchorType.WORD_BEGIN:
 986             if (Config.USE_WORD_BEGIN_END)
 987                 addOpcode(OPCode.WORD_BEGIN);
 988             break;
 989 
 990         case AnchorType.WORD_END:
 991             if (Config.USE_WORD_BEGIN_END)
 992                 addOpcode(OPCode.WORD_END);
 993             break;
 994 
 995         case AnchorType.PREC_READ:
 996             addOpcode(OPCode.PUSH_POS);
 997             compileTree(node.target);
 998             addOpcode(OPCode.POP_POS);
 999             break;
1000 
1001         case AnchorType.PREC_READ_NOT:
1002             len = compileLengthTree(node.target);
1003             addOpcodeRelAddr(OPCode.PUSH_POS_NOT, len + OPSize.FAIL_POS);
1004             compileTree(node.target);
1005             addOpcode(OPCode.FAIL_POS);
1006             break;
1007 
1008         case AnchorType.LOOK_BEHIND:
1009             addOpcode(OPCode.LOOK_BEHIND);
1010             if (node.charLength < 0) {
1011                 n = analyser.getCharLengthTree(node.target);
1012                 if (analyser.returnCode != 0) newSyntaxException(ERR_INVALID_LOOK_BEHIND_PATTERN);
1013             } else {
1014                 n = node.charLength;
1015             }
1016             addLength(n);
1017             compileTree(node.target);
1018             break;
1019 
1020         case AnchorType.LOOK_BEHIND_NOT:
1021             len = compileLengthTree(node.target);
1022             addOpcodeRelAddr(OPCode.PUSH_LOOK_BEHIND_NOT, len + OPSize.FAIL_LOOK_BEHIND_NOT);
1023             if (node.charLength < 0) {
1024                 n = analyser.getCharLengthTree(node.target);
1025                 if (analyser.returnCode != 0) newSyntaxException(ERR_INVALID_LOOK_BEHIND_PATTERN);
1026             } else {
1027                 n = node.charLength;
1028             }
1029             addLength(n);
1030             compileTree(node.target);
1031             addOpcode(OPCode.FAIL_LOOK_BEHIND_NOT);
1032             break;
1033 
1034         default:
1035             newInternalException(ERR_PARSER_BUG);
1036         } // switch
1037     }
1038 
1039     private int compileLengthTree(Node node) {
1040         int len = 0;
1041 
1042         switch (node.getType()) {
1043         case NodeType.LIST:
1044             ConsAltNode lin = (ConsAltNode)node;
1045             do {
1046                 len += compileLengthTree(lin.car);
1047             } while ((lin = lin.cdr) != null);
1048             break;
1049 
1050         case NodeType.ALT:
1051             ConsAltNode aln = (ConsAltNode)node;
1052             int n = 0;
1053             do {
1054                 len += compileLengthTree(aln.car);
1055                 n++;
1056             } while ((aln = aln.cdr) != null);
1057             len += (OPSize.PUSH + OPSize.JUMP) * (n - 1);
1058             break;
1059 
1060         case NodeType.STR:
1061             StringNode sn = (StringNode)node;
1062             if (sn.isRaw()) {
1063                 len = compileLengthStringRawNode(sn);
1064             } else {
1065                 len = compileLengthStringNode(sn);
1066             }
1067             break;
1068 
1069         case NodeType.CCLASS:
1070             len = compileLengthCClassNode((CClassNode)node);
1071             break;
1072 
1073         case NodeType.CTYPE:
1074         case NodeType.CANY:
1075             len = OPSize.OPCODE;
1076             break;
1077 
1078         case NodeType.BREF:
1079             BackRefNode br = (BackRefNode)node;
1080 
1081             if (Config.USE_BACKREF_WITH_LEVEL && br.isNestLevel()) {
1082                 len = OPSize.OPCODE + OPSize.OPTION + OPSize.LENGTH +
1083                       OPSize.LENGTH + (OPSize.MEMNUM * br.backNum);
1084             } else { // USE_BACKREF_AT_LEVEL
1085                 if (br.backNum == 1) {
1086                     len = ((!isIgnoreCase(regex.options) && br.back[0] <= 2)
1087                             ? OPSize.OPCODE : (OPSize.OPCODE + OPSize.MEMNUM));
1088                 } else {
1089                     len = OPSize.OPCODE + OPSize.LENGTH + (OPSize.MEMNUM * br.backNum);
1090                 }
1091             }
1092             break;
1093 
1094         case NodeType.CALL:
1095             if (Config.USE_SUBEXP_CALL) {
1096                 len = OPSize.CALL;
1097                 break;
1098             } // USE_SUBEXP_CALL
1099             break;
1100 
1101         case NodeType.QTFR:
1102             if (Config.USE_COMBINATION_EXPLOSION_CHECK) {
1103                 len = compileCECLengthQuantifierNode((QuantifierNode)node);
1104             } else {
1105                 len = compileNonCECLengthQuantifierNode((QuantifierNode)node);
1106             }
1107             break;
1108 
1109         case NodeType.ENCLOSE:
1110             len = compileLengthEncloseNode((EncloseNode)node);
1111             break;
1112 
1113         case NodeType.ANCHOR:
1114             len = compileLengthAnchorNode((AnchorNode)node);
1115             break;
1116 
1117         default:
1118             newInternalException(ERR_PARSER_BUG);
1119 
1120         } //switch
1121         return len;
1122     }
1123 
1124     private void ensure(int size) {
1125         if (size >= code.length) {
1126             int length = code.length << 1;
1127             while (length <= size) length <<= 1;
1128             int[]tmp = new int[length];
1129             System.arraycopy(code, 0, tmp, 0, code.length);
1130             code = tmp;
1131         }
1132     }
1133 
1134     private void addInt(int i) {
1135         if (codeLength >= code.length) {
1136             int[]tmp = new int[code.length << 1];
1137             System.arraycopy(code, 0, tmp, 0, code.length);
1138             code = tmp;
1139         }
1140         code[codeLength++] = i;
1141     }
1142 
1143     void setInt(int i, int offset) {
1144         ensure(offset);
1145         regex.code[offset] = i;
1146     }
1147 
1148     private void addObject(Object o) {
1149         if (regex.operands == null) {
1150             regex.operands = new Object[4];
1151         } else if (regex.operandLength >= regex.operands.length) {
1152             Object[]tmp = new Object[regex.operands.length << 1];
1153             System.arraycopy(regex.operands, 0, tmp, 0, regex.operands.length);
1154             regex.operands = tmp;
1155         }
1156         addInt(regex.operandLength);
1157         regex.operands[regex.operandLength++] = o;
1158     }
1159 
1160     private void addChars(char[] chars, int p ,int length) {
1161         ensure(codeLength + length);
1162         int end = p + length;
1163 
1164         while (p < end) code[codeLength++] = chars[p++];
1165     }
1166 
1167     private void addInts(int[]ints, int length) {
1168         ensure(codeLength + length);
1169         System.arraycopy(ints, 0, code, codeLength, length);
1170         codeLength += length;
1171     }
1172 
1173     private void addOpcode(int opcode) {
1174         addInt(opcode);
1175 
1176         switch(opcode) {
1177         case OPCode.ANYCHAR_STAR:
1178         case OPCode.ANYCHAR_STAR_SB:
1179         case OPCode.ANYCHAR_ML_STAR:
1180         case OPCode.ANYCHAR_ML_STAR_SB:
1181         case OPCode.ANYCHAR_STAR_PEEK_NEXT:
1182         case OPCode.ANYCHAR_STAR_PEEK_NEXT_SB:
1183         case OPCode.ANYCHAR_ML_STAR_PEEK_NEXT:
1184         case OPCode.ANYCHAR_ML_STAR_PEEK_NEXT_SB:
1185         case OPCode.STATE_CHECK_ANYCHAR_STAR:
1186         case OPCode.STATE_CHECK_ANYCHAR_STAR_SB:
1187         case OPCode.STATE_CHECK_ANYCHAR_ML_STAR:
1188         case OPCode.MEMORY_START_PUSH:
1189         case OPCode.MEMORY_END_PUSH:
1190         case OPCode.MEMORY_END_PUSH_REC:
1191         case OPCode.MEMORY_END_REC:
1192         case OPCode.NULL_CHECK_START:
1193         case OPCode.NULL_CHECK_END_MEMST_PUSH:
1194         case OPCode.PUSH:
1195         case OPCode.STATE_CHECK_PUSH:
1196         case OPCode.STATE_CHECK_PUSH_OR_JUMP:
1197         case OPCode.STATE_CHECK:
1198         case OPCode.PUSH_OR_JUMP_EXACT1:
1199         case OPCode.PUSH_IF_PEEK_NEXT:
1200         case OPCode.REPEAT:
1201         case OPCode.REPEAT_NG:
1202         case OPCode.REPEAT_INC_SG:
1203         case OPCode.REPEAT_INC_NG:
1204         case OPCode.REPEAT_INC_NG_SG:
1205         case OPCode.PUSH_POS:
1206         case OPCode.PUSH_POS_NOT:
1207         case OPCode.PUSH_STOP_BT:
1208         case OPCode.PUSH_LOOK_BEHIND_NOT:
1209         case OPCode.CALL:
1210         case OPCode.RETURN: // it will appear only with CALL though
1211             regex.stackNeeded = true;
1212         }
1213     }
1214 
1215     private void addStateCheckNum(int num) {
1216         addInt(num);
1217     }
1218 
1219     private void addRelAddr(int addr) {
1220         addInt(addr);
1221     }
1222 
1223     private void addAbsAddr(int addr) {
1224         addInt(addr);
1225     }
1226 
1227     private void addLength(int length) {
1228         addInt(length);
1229     }
1230 
1231     private void addMemNum(int num) {
1232         addInt(num);
1233     }
1234 
1235     private void addPointer(Object o) {
1236         addObject(o);
1237     }
1238 
1239     private void addOption(int option) {
1240         addInt(option);
1241     }
1242 
1243     private void addOpcodeRelAddr(int opcode, int addr) {
1244         addOpcode(opcode);
1245         addRelAddr(addr);
1246     }
1247 
1248     private void addOpcodeOption(int opcode, int option) {
1249         addOpcode(opcode);
1250         addOption(option);
1251     }
1252 
1253     private void addTemplate(char[] chars) {
1254         if (templateNum == 0) {
1255             templates = new char[2][];
1256         } else if (templateNum == templates.length) {
1257             char[][] tmp = new char[templateNum * 2][];
1258             System.arraycopy(templates, 0, tmp, 0, templateNum);
1259             templates = tmp;
1260         }
1261         templates[templateNum++] = chars;
1262     }
1263 }