24 import static jdk.nashorn.internal.runtime.regexp.joni.BitStatus.bsClear;

    26 import static jdk.nashorn.internal.runtime.regexp.joni.BitStatus.bsOnAtSimple;

    27 import static jdk.nashorn.internal.runtime.regexp.joni.Option.isCaptureGroup;

    39 import jdk.nashorn.internal.runtime.regexp.joni.ast.CTypeNode;

    40 import jdk.nashorn.internal.runtime.regexp.joni.ast.CallNode;

    52 import jdk.nashorn.internal.runtime.regexp.joni.encoding.CharacterType;

    54 import jdk.nashorn.internal.runtime.regexp.joni.encoding.Ptr;

    77         regex.numCombExpCheck = 0;

    78 

    79         if (Config.USE_COMBINATION_EXPLOSION_CHECK) regex.numCombExpCheck = 0;

    82 

    83         if (Config.USE_NAMED_GROUP) {

    84             /* mixed use named group and no-named group */

    85             if (env.numNamed > 0 && syntax.captureOnlyNamedGroup() && !isCaptureGroup(regex.options)) {

    86                 if (env.numNamed != env.numMem) {

    87                     root = disableNoNameGroupCapture(root);

    88                 } else {

    89                     numberedRefCheck(root);

    90                 }

    91             }

    92         } // USE_NAMED_GROUP

    93 

    94         if (Config.USE_NAMED_GROUP) {

    95             if (env.numCall > 0) {

    96                 env.unsetAddrList = new UnsetAddrList(env.numCall);

    97                 setupSubExpCall(root);

    98                 // r != 0 ???

    99                 subexpRecursiveCheckTrav(root);

   100                 // r < 0 -< err, FOUND_CALLED_NODE = 1

   101                 subexpInfRecursiveCheckTrav(root);

   102                 // r != 0  recursion infinite ???

   103                 regex.numCall = env.numCall;

   104             } else {

   105                 regex.numCall = 0;

   106             }

   107         } // USE_NAMED_GROUP

   131 

   132         if (Config.USE_COMBINATION_EXPLOSION_CHECK) {

   133             if (env.backrefedMem == 0 || (Config.USE_SUBEXP_CALL && env.numCall == 0)) {

   134                 setupCombExpCheck(root, 0);

   135 

   136                 if (Config.USE_SUBEXP_CALL && env.hasRecursion) {

   137                     env.numCombExpCheck = 0;

   138                 } else { // USE_SUBEXP_CALL

   139                     if (env.combExpMaxRegNum > 0) {

   140                         for (int i=1; i<env.combExpMaxRegNum; i++) {

   141                             if (bsAt(env.backrefedMem, i)) {

   142                                 env.numCombExpCheck = 0;

   143                                 break;

   144                             }

   145                         }

   146                     }

   147                 }

   148 

   149             } // USE_SUBEXP_CALL

   150             regex.numCombExpCheck = env.numCombExpCheck;

   151         } // USE_COMBINATION_EXPLOSION_CHECK

   170             if (Config.USE_NAMED_GROUP) Config.log.print(regex.nameTableToString());

   178     }

   179 

   180     private void noNameDisableMapFor_cosAlt(Node node, int[]map, Ptr counter) {

   181         ConsAltNode can = (ConsAltNode)node;

   182         do {

   183             can.setCar(noNameDisableMap(can.car, map, counter));

   184         } while ((can = can.cdr) != null);

   185     }

   186 

   187     private void noNameDisableMapFor_quantifier(Node node, int[]map, Ptr counter) {

   188         QuantifierNode qn = (QuantifierNode)node;

   189         Node target = qn.target;

   190         Node old = target;

   191         target = noNameDisableMap(target, map, counter);

   192 

   193         if (target != old) {

   194             qn.setTarget(target);

   195             if (target.getType() == NodeType.QTFR) qn.reduceNestedQuantifier((QuantifierNode)target);

   196         }

   197     }

   198 

   199     private Node noNameDisableMapFor_enclose(Node node, int[]map, Ptr counter) {

   200         EncloseNode en = (EncloseNode)node;

   201         if (en.type == EncloseType.MEMORY) {

   202             if (en.isNamedGroup()) {

   203                 counter.p++;

   204                 map[en.regNum] = counter.p;

   205                 en.regNum = counter.p;

   206                 //en.target = noNameDisableMap(en.target, map, counter);

   207                 en.setTarget(noNameDisableMap(en.target, map, counter)); // ???

   208             } else {

   209                 node = en.target;

   210                 en.target = null; // remove first enclose: /(a)(?<b>c)/

   211                 node = noNameDisableMap(node, map, counter);

   212             }

   213         } else {

   214             //en.target = noNameDisableMap(en.target, map, counter);

   215             en.setTarget(noNameDisableMap(en.target, map, counter)); // ???

   216         }

   217         return node;

   218     }

   219 

   220     private void noNameDisableMapFor_anchor(Node node, int[]map, Ptr counter) {

   221         AnchorNode an = (AnchorNode)node;

   222         switch (an.type) {

   223             case AnchorNode.PREC_READ:

   224             case AnchorNode.PREC_READ_NOT:

   225             case AnchorNode.LOOK_BEHIND:

   226             case AnchorNode.LOOK_BEHIND_NOT:

   227                 an.setTarget(noNameDisableMap(an.target, map, counter));

   228         }

   229     }

   230 

   231     private Node noNameDisableMap(Node node, int[]map, Ptr counter) {

   232         switch (node.getType()) {

   233         case NodeType.LIST:

   234         case NodeType.ALT:

   235             noNameDisableMapFor_cosAlt(node, map, counter);

   236             break;

   237         case NodeType.QTFR:

   238             noNameDisableMapFor_quantifier(node, map, counter);

   239             break;

   240         case NodeType.ENCLOSE:

   241             node = noNameDisableMapFor_enclose(node, map, counter);

   242             break;

   243         case NodeType.ANCHOR:

   244             noNameDisableMapFor_anchor(node, map, counter);

   245             break;

   246         } // switch

   247         return node;

   248     }

   249 

   250     private void renumberByMap(Node node, int[]map) {

   251         switch (node.getType()) {

   252         case NodeType.LIST:

   253         case NodeType.ALT:

   254             ConsAltNode can = (ConsAltNode)node;

   255             do {

   256                 renumberByMap(can.car, map);

   257             } while ((can = can.cdr) != null);

   258             break;

   259 

   260         case NodeType.QTFR:

   261             renumberByMap(((QuantifierNode)node).target, map);

   262             break;

   263 

   264         case NodeType.ENCLOSE:

   265             renumberByMap(((EncloseNode)node).target, map);

   266             break;

   267 

   268         case NodeType.BREF:

   269             ((BackRefNode)node).renumber(map);

   270             break;

   271         } // switch

   272     }

   273 

   274     protected final void numberedRefCheck(Node node) {

   275         switch (node.getType()) {

   276         case NodeType.LIST:

   277         case NodeType.ALT:

   278             ConsAltNode can = (ConsAltNode)node;

   279             do {

   280                 numberedRefCheck(can.car);

   281             } while ((can = can.cdr) != null);

   282             break;

   283 

   284         case NodeType.QTFR:

   285             numberedRefCheck(((QuantifierNode)node).target);

   286             break;

   287 

   288         case NodeType.ENCLOSE:

   289             numberedRefCheck(((EncloseNode)node).target);

   290             break;

   291 

   292         case NodeType.BREF:

   293             BackRefNode br = (BackRefNode)node;

   294             if (!br.isNameRef()) newValueException(ERR_NUMBERED_BACKREF_OR_CALL_NOT_ALLOWED);

   295             break;

   296         } // switch

   297     }

   298 

   299     protected final Node disableNoNameGroupCapture(Node root) {

   300         int[]map = new int[env.numMem + 1];

   301 

   302         for (int i=1; i<=env.numMem; i++) map[i] = 0;

   303 

   304         root = noNameDisableMap(root, map, new Ptr(0));

   305         renumberByMap(root, map);

   306 

   307         for (int i=1, pos=1; i<=env.numMem; i++) {

   308             if (map[i] > 0) {

   309                 env.memNodes[pos] = env.memNodes[i];

   310                 pos++;

   311             }

   312         }

   313 

   314         int loc = env.captureHistory;

   315         env.captureHistory = bsClear();

   316 

   317         for (int i=1; i<=Config.MAX_CAPTURE_HISTORY_GROUP; i++) {

   318             if (bsAt(loc, i)) {

   319                 env.captureHistory = bsOnAtSimple(env.captureHistory, map[i]);

   320             }

   321         }

   322 

   323         env.numMem = env.numNamed;

   324         regex.numMem = env.numNamed;

   325 

   326         regex.renumberNameTable(map);

   327 

   328         return root;

   355         case NodeType.CALL:

   356             if (Config.USE_SUBEXP_CALL) {

   357                 CallNode cn = (CallNode)node;

   358                 if (cn.isRecursion()) {

   359                     return TargetInfo.IS_EMPTY_REC; /* tiny version */

   360                 } else {

   361                     info = quantifiersMemoryInfo(cn.target);

   362                 }

   363             } // USE_SUBEXP_CALL

   364             break;

   365 

   418             break;

   419 

   420         case NodeType.CALL:

   421             if (Config.USE_SUBEXP_CALL) {

   422                 CallNode cn = (CallNode)node;

   423                 if (cn.isRecursion()) {

   424                     EncloseNode en = (EncloseNode)cn.target;

   425                     if (en.isMinFixed()) min = en.minLength;

   426                 } else {

   427                     min = getMinMatchLength(cn.target);

   428                 }

   429             } // USE_SUBEXP_CALL

   548             break;

   549 

   550         case NodeType.CALL:

   551             if (Config.USE_SUBEXP_CALL) {

   552                 CallNode cn = (CallNode)node;

   553                 if (!cn.isRecursion()) {

   554                     max = getMaxMatchLength(cn.target);

   555                 } else {

   556                     max = MinMaxLen.INFINITE_DISTANCE;

   557                 }

   558             } // USE_SUBEXP_CALL

   666         case NodeType.CALL:

   667             if (Config.USE_SUBEXP_CALL) {

   668                 CallNode cn = (CallNode)node;

   669                 if (!cn.isRecursion()) {

   670                     len = getCharLengthTree(cn.target, level);

   671                 } else {

   672                     returnCode = GET_CHAR_LEN_VARLEN;

   673                 }

   674             } // USE_SUBEXP_CALL

   675             break;

   676 

   730             case NodeType.CTYPE:

   731                 CTypeNode cny = (CTypeNode)y;

   732                 CTypeNode cnx = (CTypeNode)x;

   733                 return cny.ctype == cnx.ctype && cny.not != cnx.not;

   759             case NodeType.CTYPE:

   760                 switch(((CTypeNode)y).ctype) {

   761                 case CharacterType.WORD:

   762                     if (!((CTypeNode)y).not) {

   763                         if (xc.mbuf == null && !xc.isNot()) {

   764                             for (int i=0; i<BitSet.SINGLE_BYTE_SIZE; i++) {

   765                                 if (xc.bs.at(i)) {

   766                                     if (EncodingHelper.isWord(i)) return false;

   767                                 }

   768                             }

   769                             return true;

   770                         }

   771                         return false;

   772                     } else {

   773                         for (int i=0; i<BitSet.SINGLE_BYTE_SIZE; i++) {

   774                             if (!EncodingHelper.isWord(i)) {

   775                                 if (!xc.isNot()) {

   776                                     if (xc.bs.at(i)) return false;

   777                                 } else {

   778                                     if (!xc.bs.at(i)) return false;

   779                                 }

   780                             }

   781                         }

   782                         return true;

   783                     }

   784                     // break; not reached

   785 

   786                 default:

   787                     break;

   788                 } // inner switch

   789                 break;

   823             case NodeType.CTYPE:

   824                 CTypeNode cy = ((CTypeNode)y);

   825                 switch (cy.ctype) {

   826                 case CharacterType.WORD:

   827                     return !cy.not;

   828 

   829                 default:

   830                     break;

   831 

   832                 } // inner switch

   833                 break;

   876         case NodeType.CALL:

   877             break; // if (Config.USE_SUBEXP_CALL)

   878 

   978     }

   979 

   980     private static final int RECURSION_EXIST       = 1;

   981     private static final int RECURSION_INFINITE    = 2;

   982     private int subexpInfRecursiveCheck(Node node, boolean head) {

   983         int r = 0;

   984 

   985         switch (node.getType()) {

   986         case NodeType.LIST:

   987             int min;

   988             ConsAltNode x = (ConsAltNode)node;

   989             do {

   990                 int ret = subexpInfRecursiveCheck(x.car, head);

   991                 if (ret == RECURSION_INFINITE) return ret;

   992                 r |= ret;

   993                 if (head) {

   994                     min = getMinMatchLength(x.car);

   995                     if (min != 0) head = false;

   996                 }

   997             } while ((x = x.cdr) != null);

   998             break;

   999 

  1000         case NodeType.ALT:

  1001             ConsAltNode can = (ConsAltNode)node;

  1002             r = RECURSION_EXIST;

  1003             do {

  1004                 int ret = subexpInfRecursiveCheck(can.car, head);

  1005                 if (ret == RECURSION_INFINITE) return ret;

  1006                 r &= ret;

  1007             } while ((can = can.cdr) != null);

  1008             break;

  1009 

  1010         case NodeType.QTFR:

  1011             QuantifierNode qn = (QuantifierNode)node;

  1012             r = subexpInfRecursiveCheck(qn.target, head);

  1013             if (r == RECURSION_EXIST) {

  1014                 if (qn.lower == 0) r = 0;

  1015             }

  1016             break;

  1017 

  1018         case NodeType.ANCHOR:

  1019             AnchorNode an = (AnchorNode)node;

  1020             switch (an.type) {

  1021             case AnchorType.PREC_READ:

  1022             case AnchorType.PREC_READ_NOT:

  1023             case AnchorType.LOOK_BEHIND:

  1024             case AnchorType.LOOK_BEHIND_NOT:

  1025                 r = subexpInfRecursiveCheck(an.target, head);

  1026                 break;

  1027             } // inner switch

  1028             break;

  1029 

  1030         case NodeType.CALL:

  1031             r = subexpInfRecursiveCheck(((CallNode)node).target, head);

  1032             break;

  1033 

  1034         case NodeType.ENCLOSE:

  1035             EncloseNode en = (EncloseNode)node;

  1036             if (en.isMark2()) {

  1037                 return 0;

  1038             } else if (en.isMark1()) {

  1039                 return !head ? RECURSION_EXIST : RECURSION_INFINITE;

  1040                 // throw exception here ???

  1041             } else {

  1042                 en.setMark2();

  1043                 r = subexpInfRecursiveCheck(en.target, head);

  1044                 en.clearMark2();

  1045             }

  1046             break;

  1047 

  1048         default:

  1049             break;

  1050         } // switch

  1051         return r;

  1052     }

  1053 

  1054     protected final int subexpInfRecursiveCheckTrav(Node node) {

  1055         int r = 0;

  1056 

  1057         switch (node.getType()) {

  1058         case NodeType.LIST:

  1059         case NodeType.ALT:

  1060             ConsAltNode can = (ConsAltNode)node;

  1061             do {

  1062                 r = subexpInfRecursiveCheckTrav(can.car);

  1063             } while (r == 0 && (can = can.cdr) != null);

  1064             break;

  1065 

  1066         case NodeType.QTFR:

  1067             r = subexpInfRecursiveCheckTrav(((QuantifierNode)node).target);

  1068             break;

  1069 

  1070         case NodeType.ANCHOR:

  1071             AnchorNode an = (AnchorNode)node;

  1072             switch (an.type) {

  1073             case AnchorType.PREC_READ:

  1074             case AnchorType.PREC_READ_NOT:

  1075             case AnchorType.LOOK_BEHIND:

  1076             case AnchorType.LOOK_BEHIND_NOT:

  1077                 r = subexpInfRecursiveCheckTrav(an.target);

  1078                 break;

  1079             } // inner switch

  1080             break;

  1081 

  1082         case NodeType.ENCLOSE:

  1083             EncloseNode en = (EncloseNode)node;

  1084             if (en.isRecursion()) {

  1085                 en.setMark1();

  1086                 r = subexpInfRecursiveCheck(en.target, true);

  1087                 if (r > 0) newValueException(ERR_NEVER_ENDING_RECURSION);

  1088                 en.clearMark1();

  1089             }

  1090             r = subexpInfRecursiveCheckTrav(en.target);

  1091             break;

  1092 

  1093         default:

  1094             break;

  1095         } // switch

  1096 

  1097         return r;

  1098     }

  1099 

  1100     private int subexpRecursiveCheck(Node node) {

  1101         int r = 0;

  1102 

  1103         switch (node.getType()) {

  1104         case NodeType.LIST:

  1105         case NodeType.ALT:

  1106             ConsAltNode can = (ConsAltNode)node;

  1107             do {

  1108                 r |= subexpRecursiveCheck(can.car);

  1109             } while ((can = can.cdr) != null);

  1110             break;

  1111 

  1112         case NodeType.QTFR:

  1113             r = subexpRecursiveCheck(((QuantifierNode)node).target);

  1114             break;

  1115 

  1116         case NodeType.ANCHOR:

  1117             AnchorNode an = (AnchorNode)node;

  1118             switch (an.type) {

  1119             case AnchorType.PREC_READ:

  1120             case AnchorType.PREC_READ_NOT:

  1121             case AnchorType.LOOK_BEHIND:

  1122             case AnchorType.LOOK_BEHIND_NOT:

  1123                 r = subexpRecursiveCheck(an.target);

  1124                 break;

  1125             } // inner switch

  1126             break;

  1127 

  1128         case NodeType.CALL:

  1129             CallNode cn = (CallNode)node;

  1130             r = subexpRecursiveCheck(cn.target);

  1131             if (r != 0) cn.setRecursion();

  1132             break;

  1133 

  1134         case NodeType.ENCLOSE:

  1135             EncloseNode en = (EncloseNode)node;

  1136             if (en.isMark2()) {

  1137                 return 0;

  1138             } else if (en.isMark1()) {

  1139                 return 1; /* recursion */

  1140             } else {

  1141                 en.setMark2();

  1142                 r = subexpRecursiveCheck(en.target);

  1143                 en.clearMark2();

  1144             }

  1145             break;

  1146 

  1147         default:

  1148             break;

  1149         } // switch

  1150 

  1151         return r;

  1152     }

  1153 

  1154     private static final int FOUND_CALLED_NODE  = 1;

  1155     protected final int subexpRecursiveCheckTrav(Node node) {

  1156         int r = 0;

  1157 

  1158         switch (node.getType()) {

  1159         case NodeType.LIST:

  1160         case NodeType.ALT:

  1161             ConsAltNode can = (ConsAltNode)node;

  1162             do {

  1163                 int ret = subexpRecursiveCheckTrav(can.car);

  1164                 if (ret == FOUND_CALLED_NODE) {

  1165                     r = FOUND_CALLED_NODE;

  1166                 }

  1167                 // else if (ret < 0) return ret; ???

  1168             } while ((can = can.cdr) != null);

  1169             break;

  1170 

  1171         case NodeType.QTFR:

  1172             QuantifierNode qn = (QuantifierNode)node;

  1173             r = subexpRecursiveCheckTrav(qn.target);

  1174             if (qn.upper == 0) {

  1175                 if (r == FOUND_CALLED_NODE) qn.isRefered = true;

  1176             }

  1177             break;

  1178 

  1179         case NodeType.ANCHOR:

  1180             AnchorNode an = (AnchorNode)node;

  1181             switch (an.type) {

  1182             case AnchorType.PREC_READ:

  1183             case AnchorType.PREC_READ_NOT:

  1184             case AnchorType.LOOK_BEHIND:

  1185             case AnchorType.LOOK_BEHIND_NOT:

  1186                 r = subexpRecursiveCheckTrav(an.target);

  1187                 break;

  1188             } // inner switch

  1189             break;

  1190 

  1191         case NodeType.ENCLOSE:

  1192             EncloseNode en = (EncloseNode)node;

  1193             if (!en.isRecursion()) {

  1194                 if (en.isCalled()) {

  1195                     en.setMark1();

  1196                     r = subexpRecursiveCheck(en.target);

  1197                     if (r != 0) en.setRecursion();

  1198                     en.clearMark1();

  1199                 }

  1200             }

  1201             r = subexpRecursiveCheckTrav(en.target);

  1202             if (en.isCalled()) r |= FOUND_CALLED_NODE;

  1203             break;

  1204 

  1205         default:

  1206             break;

  1207         } // switch

  1208 

  1209         return r;

  1210     }

  1211 

  1212     private void setCallAttr(CallNode cn) {

  1213         cn.target = env.memNodes[cn.groupNum]; // no setTarget in call nodes!

  1214         if (cn.target == null) newValueException(ERR_UNDEFINED_NAME_REFERENCE, cn.nameP, cn.nameEnd);

  1215 

  1216         ((EncloseNode)cn.target).setCalled();

  1217         env.btMemStart = BitStatus.bsOnAt(env.btMemStart, cn.groupNum);

  1218         cn.unsetAddrList = env.unsetAddrList;

  1219     }

  1220 

  1221     protected final void setupSubExpCall(Node node) {

  1222 

  1223         switch(node.getType()) {

  1224         case NodeType.LIST:

  1225             ConsAltNode ln = (ConsAltNode)node;

  1226             do {

  1227                 setupSubExpCall(ln.car);

  1228             } while ((ln = ln.cdr) != null);

  1229             break;

  1230 

  1231         case NodeType.ALT:

  1232             ConsAltNode can = (ConsAltNode)node;

  1233             do {

  1234                 setupSubExpCall(can.car);

  1235             } while ((can = can.cdr) != null);

  1236             break;

  1237 

  1238         case NodeType.QTFR:

  1239             setupSubExpCall(((QuantifierNode)node).target);

  1240             break;

  1241 

  1242         case NodeType.ENCLOSE:

  1243             setupSubExpCall(((EncloseNode)node).target);

  1244             break;

  1245 

  1246         case NodeType.CALL:

  1247             CallNode cn = (CallNode)node;

  1248 

  1249             if (cn.groupNum != 0) {

  1250                 int gNum = cn.groupNum;

  1251 

  1252                 if (Config.USE_NAMED_GROUP) {

  1253                     if (env.numNamed > 0 && syntax.captureOnlyNamedGroup() && !isCaptureGroup(env.option)) {

  1254                         newValueException(ERR_NUMBERED_BACKREF_OR_CALL_NOT_ALLOWED);

  1255                     }

  1256                 } // USE_NAMED_GROUP

  1257                 if (gNum > env.numMem) newValueException(ERR_UNDEFINED_GROUP_REFERENCE, cn.nameP, cn.nameEnd);

  1258                 setCallAttr(cn);

  1259             } else {

  1260                 if (Config.USE_NAMED_GROUP) {

  1261                     NameEntry ne = regex.nameToGroupNumbers(cn.name, cn.nameP, cn.nameEnd);

  1262 

  1263                     if (ne == null) {

  1264                         newValueException(ERR_UNDEFINED_NAME_REFERENCE, cn.nameP, cn.nameEnd);

  1265                     } else if (ne.backNum > 1) {

  1266                         newValueException(ERR_MULTIPLEX_DEFINITION_NAME_CALL, cn.nameP, cn.nameEnd);

  1267                     } else {

  1268                         cn.groupNum = ne.backRef1; // ne.backNum == 1 ? ne.backRef1 : ne.backRefs[0]; // ??? need to check ?

  1269                         setCallAttr(cn);

  1270                     }

  1271                 }

  1272             }

  1273             break;

  1274 

  1275         case NodeType.ANCHOR:

  1276             AnchorNode an = (AnchorNode)node;

  1277             switch (an.type) {

  1278             case AnchorType.PREC_READ:

  1279             case AnchorType.PREC_READ_NOT:

  1280             case AnchorType.LOOK_BEHIND:

  1281             case AnchorType.LOOK_BEHIND_NOT:

  1282                 setupSubExpCall(an.target);

  1283                 break;

  1284             }

  1285             break;

  1286 

  1287         } // switch

  1524     }

  1525 

  1526     private static final int CEC_THRES_NUM_BIG_REPEAT       = 512;

  1527     private static final int CEC_INFINITE_NUM               = 0x7fffffff;

  1528 

  1529     private static final int CEC_IN_INFINITE_REPEAT         = (1<<0);

  1530     private static final int CEC_IN_FINITE_REPEAT           = (1<<1);

  1531     private static final int CEC_CONT_BIG_REPEAT            = (1<<2);

  1532 

  1533     protected final int setupCombExpCheck(Node node, int state) {

  1534         int r = state;

  1535         int ret;

  1536 

  1537         switch (node.getType()) {

  1538         case NodeType.LIST:

  1539             ConsAltNode ln = (ConsAltNode)node;

  1540 

  1541             do {

  1542                 r = setupCombExpCheck(ln.car, r);

  1543                 //prev = ((ConsAltNode)node).car;

  1544             } while (r >= 0 && (ln = ln.cdr) != null);

  1545             break;

  1546 

  1547         case NodeType.ALT:

  1548             ConsAltNode an = (ConsAltNode)node;

  1549             do {

  1550                 ret = setupCombExpCheck(an.car, state);

  1551                 r |= ret;

  1552             } while (ret >= 0 && (an = an.cdr) != null);

  1553             break;

  1554 

  1555         case NodeType.QTFR:

  1556             QuantifierNode qn = (QuantifierNode)node;

  1557             int childState = state;

  1558             int addState = 0;

  1559             int varNum;

  1560 

  1561             if (!isRepeatInfinite(qn.upper)) {

  1562                 if (qn.upper > 1) {

  1563                     /* {0,1}, {1,1} are allowed */

  1564                     childState |= CEC_IN_FINITE_REPEAT;

  1565 

  1566                     /* check (a*){n,m}, (a+){n,m} => (a*){n,n}, (a+){n,n} */

  1567                     if (env.backrefedMem == 0) {

  1568                         if (qn.target.getType() == NodeType.ENCLOSE) {

  1569                             EncloseNode en = (EncloseNode)qn.target;

  1570                             if (en.type == EncloseType.MEMORY) {

  1571                                 if (en.target.getType() == NodeType.QTFR) {

  1572                                     QuantifierNode q = (QuantifierNode)en.target;

  1573                                     if (isRepeatInfinite(q.upper) && q.greedy == qn.greedy) {

  1574                                         qn.upper = qn.lower == 0 ? 1 : qn.lower;

  1575                                         if (qn.upper == 1) childState = state;

  1576                                     }

  1577                                 }

  1578                             }

  1579                         }

  1580                     }

  1581                 }

  1582             }

  1583 

  1584             if ((state & CEC_IN_FINITE_REPEAT) != 0) {

  1585                 qn.combExpCheckNum = -1;

  1586             } else {

  1587                 if (isRepeatInfinite(qn.upper)) {

  1588                     varNum = CEC_INFINITE_NUM;

  1589                     childState |= CEC_IN_INFINITE_REPEAT;

  1590                 } else {

  1591                     varNum = qn.upper - qn.lower;

  1592                 }

  1593 

  1594                 if (varNum >= CEC_THRES_NUM_BIG_REPEAT) addState |= CEC_CONT_BIG_REPEAT;

  1595 

  1596                 if (((state & CEC_IN_INFINITE_REPEAT) != 0 && varNum != 0) ||

  1597                    ((state & CEC_CONT_BIG_REPEAT) != 0 && varNum >= CEC_THRES_NUM_BIG_REPEAT)) {

  1598                     if (qn.combExpCheckNum == 0) {

  1599                         env.numCombExpCheck++;

  1600                         qn.combExpCheckNum = env.numCombExpCheck;

  1601                         if (env.currMaxRegNum > env.combExpMaxRegNum) {

  1602                             env.combExpMaxRegNum = env.currMaxRegNum;

  1603                         }

  1604                     }

  1605                 }

  1606             }

  1607             r = setupCombExpCheck(qn.target, childState);

  1608             r |= addState;

  1609             break;

  1610 

  1611         case NodeType.ENCLOSE:

  1612             EncloseNode en = (EncloseNode)node;

  1613             switch( en.type) {

  1614             case EncloseNode.MEMORY:

  1615                 if (env.currMaxRegNum < en.regNum) {

  1616                     env.currMaxRegNum = en.regNum;

  1617                 }

  1618                 r = setupCombExpCheck(en.target, state);

  1619                 break;

  1620 

  1621             default:

  1622                 r = setupCombExpCheck(en.target, state);

  1623             } // inner switch

  1624             break;

  1625 

  1626         case NodeType.CALL:

  1627             if (Config.USE_SUBEXP_CALL) {

  1628                 CallNode cn = (CallNode)node;

  1629                 if (cn.isRecursion()) {

  1630                     env.hasRecursion = true;

  1631                 } else {

  1632                     r = setupCombExpCheck(cn.target, state);

  1633                 }

  1634             } // USE_SUBEXP_CALL

  1635             break;

  1636 

  1637         default:

  1638             break;

  1639 

  1640         } // switch

  1641 

  1642         return r;

  1694         case NodeType.CALL: // if (Config.USE_SUBEXP_CALL) ?

  1695             break;

  1696 

  1703                 if (Config.USE_BACKREF_WITH_LEVEL) {

  1704                     if (br.isNestLevel()) {

  1705                         env.btMemEnd = bsOnAt(env.btMemEnd, br.back[i]);

  1706                     }

  1707                 } // USE_BACKREF_AT_LEVEL

  1919         case NodeType.CTYPE: {

  1920             int min;

  1921             int max = 1;

  1922             if (max == 1) {

  1923                 min = 1;

  1924                 CTypeNode cn = (CTypeNode)node;

  1925 

  1926                 switch (cn.ctype) {

  1927                 case CharacterType.WORD:

  1928                     if (cn.not) {

  1929                         for (int i=0; i<BitSet.SINGLE_BYTE_SIZE; i++) {

  1930                             if (!EncodingHelper.isWord(i)) {

  1931                                 opt.map.addChar(i);

  1932                             }

  1933                         }

  1934                     } else {

  1935                         for (int i=0; i<BitSet.SINGLE_BYTE_SIZE; i++) {

  1936                             if (EncodingHelper.isWord(i)) {

  1937                                 opt.map.addChar(i);

  1938                             }

  1939                         }

  1940                     }

  1941                     break;

  1942                 } // inner switch

  1943             } else {

  1944                 min = 1;

  1945             }

  1946             opt.length.set(min, max);

  1947             break;

  1948         }

  1949 

  2011         case NodeType.CALL: {

  2012             if (Config.USE_SUBEXP_CALL) {

  2013                 CallNode cn = (CallNode)node;

  2014                 if (cn.isRecursion()) {

  2015                     opt.length.set(0, MinMaxLen.INFINITE_DISTANCE);

  2016                 } else {

  2017                     int safe = oenv.options;

  2018                     oenv.options = ((EncloseNode)cn.target).option;

  2019                     optimizeNodeLeft(cn.target, opt, oenv);

  2020                     oenv.options = safe;

  2021                 }

  2022             } // USE_SUBEXP_CALL

  2023             break;

  2024         }