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 */ 20package jdk.nashorn.internal.runtime.regexp.joni.ast; 21 22import static jdk.nashorn.internal.runtime.regexp.joni.ast.QuantifierNode.ReduceType.A; 23import static jdk.nashorn.internal.runtime.regexp.joni.ast.QuantifierNode.ReduceType.AQ; 24import static jdk.nashorn.internal.runtime.regexp.joni.ast.QuantifierNode.ReduceType.ASIS; 25import static jdk.nashorn.internal.runtime.regexp.joni.ast.QuantifierNode.ReduceType.DEL; 26import static jdk.nashorn.internal.runtime.regexp.joni.ast.QuantifierNode.ReduceType.PQ_Q; 27import static jdk.nashorn.internal.runtime.regexp.joni.ast.QuantifierNode.ReduceType.P_QQ; 28import static jdk.nashorn.internal.runtime.regexp.joni.ast.QuantifierNode.ReduceType.QQ; 29import jdk.nashorn.internal.runtime.regexp.joni.Config; 30import jdk.nashorn.internal.runtime.regexp.joni.ScanEnvironment; 31import jdk.nashorn.internal.runtime.regexp.joni.constants.TargetInfo; 32 33@SuppressWarnings("javadoc") 34public final class QuantifierNode extends StateNode { 35 36 public Node target; 37 public int lower; 38 public int upper; 39 public boolean greedy; 40 41 public int targetEmptyInfo; 42 43 public Node headExact; 44 public Node nextHeadExact; 45 public boolean isRefered; /* include called node. don't eliminate even if {0} */ 46 47 enum ReduceType { 48 ASIS, /* as is */ 49 DEL, /* delete parent */ 50 A, /* to '*' */ 51 AQ, /* to '*?' */ 52 QQ, /* to '??' */ 53 P_QQ, /* to '+)??' */ 54 PQ_Q, /* to '+?)?' */ 55 } 56 57 private final static ReduceType[][] REDUCE_TABLE = { 58 {DEL, A, A, QQ, AQ, ASIS}, /* '?' */ 59 {DEL, DEL, DEL, P_QQ, P_QQ, DEL}, /* '*' */ 60 {A, A, DEL, ASIS, P_QQ, DEL}, /* '+' */ 61 {DEL, AQ, AQ, DEL, AQ, AQ}, /* '??' */ 62 {DEL, DEL, DEL, DEL, DEL, DEL}, /* '*?' */ 63 {ASIS, PQ_Q, DEL, AQ, AQ, DEL} /* '+?' */ 64 }; 65 66 private final static String PopularQStr[] = new String[] { 67 "?", "*", "+", "??", "*?", "+?" 68 }; 69 70 private final static String ReduceQStr[]= new String[] { 71 "", "", "*", "*?", "??", "+ and ??", "+? and ?" 72 }; 73 74 75 public QuantifierNode(final int lower, final int upper, final boolean byNumber) { 76 this.lower = lower; 77 this.upper = upper; 78 greedy = true; 79 targetEmptyInfo = TargetInfo.ISNOT_EMPTY; 80 81 if (byNumber) { 82 setByNumber(); 83 } 84 } 85 86 @Override 87 public int getType() { 88 return QTFR; 89 } 90 91 @Override 92 protected void setChild(final Node newChild) { 93 target = newChild; 94 } 95 96 @Override 97 protected Node getChild() { 98 return target; 99 } 100 101 public void setTarget(final Node tgt) { 102 target = tgt; 103 tgt.parent = this; 104 } 105 106 public StringNode convertToString(final int flag) { 107 final StringNode sn = new StringNode(); 108 sn.flag = flag; 109 sn.swap(this); 110 return sn; 111 } 112 113 @Override 114 public String getName() { 115 return "Quantifier"; 116 } 117 118 @Override 119 public String toString(final int level) { 120 final StringBuilder value = new StringBuilder(super.toString(level)); 121 value.append("\n target: ").append(pad(target, level + 1)); 122 value.append("\n lower: ").append(lower); 123 value.append("\n upper: ").append(upper); 124 value.append("\n greedy: ").append(greedy); 125 value.append("\n targetEmptyInfo: ").append(targetEmptyInfo); 126 value.append("\n headExact: ").append(pad(headExact, level + 1)); 127 value.append("\n nextHeadExact: ").append(pad(nextHeadExact, level + 1)); 128 value.append("\n isRefered: ").append(isRefered); 129 130 return value.toString(); 131 } 132 133 public boolean isAnyCharStar() { 134 return greedy && isRepeatInfinite(upper) && target.getType() == CANY; 135 } 136 137 /* ?:0, *:1, +:2, ??:3, *?:4, +?:5 */ 138 protected int popularNum() { 139 if (greedy) { 140 if (lower == 0) { 141 if (upper == 1) { 142 return 0; 143 } else if (isRepeatInfinite(upper)) { 144 return 1; 145 } 146 } else if (lower == 1) { 147 if (isRepeatInfinite(upper)) { 148 return 2; 149 } 150 } 151 } else { 152 if (lower == 0) { 153 if (upper == 1) { 154 return 3; 155 } else if (isRepeatInfinite(upper)) { 156 return 4; 157 } 158 } else if (lower == 1) { 159 if (isRepeatInfinite(upper)) { 160 return 5; 161 } 162 } 163 } 164 return -1; 165 } 166 167 protected void set(final QuantifierNode other) { 168 setTarget(other.target); 169 other.target = null; 170 lower = other.lower; 171 upper = other.upper; 172 greedy = other.greedy; 173 targetEmptyInfo = other.targetEmptyInfo; 174 175 //setHeadExact(other.headExact); 176 //setNextHeadExact(other.nextHeadExact); 177 headExact = other.headExact; 178 nextHeadExact = other.nextHeadExact; 179 isRefered = other.isRefered; 180 } 181 182 public void reduceNestedQuantifier(final QuantifierNode other) { 183 final int pnum = popularNum(); 184 final int cnum = other.popularNum(); 185 186 if (pnum < 0 || cnum < 0) { 187 return; 188 } 189 190 switch(REDUCE_TABLE[cnum][pnum]) { 191 case DEL: 192 // no need to set the parent here... 193 // swap ? 194 set(other); // *pnode = *cnode; ??? 195 break; 196 197 case A: 198 setTarget(other.target); 199 lower = 0; 200 upper = REPEAT_INFINITE; 201 greedy = true; 202 break; 203 204 case AQ: 205 setTarget(other.target); 206 lower = 0; 207 upper = REPEAT_INFINITE; 208 greedy = false; 209 break; 210 211 case QQ: 212 setTarget(other.target); 213 lower = 0; 214 upper = 1; 215 greedy = false; 216 break; 217 218 case P_QQ: 219 setTarget(other); 220 lower = 0; 221 upper = 1; 222 greedy = false; 223 other.lower = 1; 224 other.upper = REPEAT_INFINITE; 225 other.greedy = true; 226 return; 227 228 case PQ_Q: 229 setTarget(other); 230 lower = 0; 231 upper = 1; 232 greedy = true; 233 other.lower = 1; 234 other.upper = REPEAT_INFINITE; 235 other.greedy = false; 236 return; 237 238 case ASIS: 239 setTarget(other); 240 return; 241 242 default: 243 break; 244 } 245 // ??? remove the parent from target ??? 246 other.target = null; // remove target from reduced quantifier 247 } 248 249 @SuppressWarnings("fallthrough") 250 public int setQuantifier(final Node tgt, final boolean group, final ScanEnvironment env, final char[] chars, final int p, final int end) { 251 if (lower == 1 && upper == 1) { 252 return 1; 253 } 254 255 switch(tgt.getType()) { 256 257 case STR: 258 if (!group) { 259 final StringNode sn = (StringNode)tgt; 260 if (sn.canBeSplit()) { 261 final StringNode n = sn.splitLastChar(); 262 if (n != null) { 263 setTarget(n); 264 return 2; 265 } 266 } 267 } 268 break; 269 270 case QTFR: 271 /* check redundant double repeat. */ 272 /* verbose warn (?:.?)? etc... but not warn (.?)? etc... */ 273 final QuantifierNode qnt = (QuantifierNode)tgt; 274 final int nestQNum = popularNum(); 275 final int targetQNum = qnt.popularNum(); 276 277 if (Config.USE_WARNING_REDUNDANT_NESTED_REPEAT_OPERATOR) { 278 if (!isByNumber() && !qnt.isByNumber() && env.syntax.warnReduntantNestedRepeat()) { 279 switch(REDUCE_TABLE[targetQNum][nestQNum]) { 280 case ASIS: 281 break; 282 283 case DEL: 284 env.reg.getWarnings().warn(new String(chars, p, end) + 285 " redundant nested repeat operator"); 286 break; 287 288 default: 289 env.reg.getWarnings().warn(new String(chars, p, end) + 290 " nested repeat operator " + PopularQStr[targetQNum] + 291 " and " + PopularQStr[nestQNum] + " was replaced with '" + 292 ReduceQStr[REDUCE_TABLE[targetQNum][nestQNum].ordinal()] + "'"); 293 } 294 } 295 } // USE_WARNING_REDUNDANT_NESTED_REPEAT_OPERATOR 296 297 if (targetQNum >= 0) { 298 if (nestQNum >= 0) { 299 reduceNestedQuantifier(qnt); 300 return 0; 301 } else if (targetQNum == 1 || targetQNum == 2) { /* * or + */ 302 /* (?:a*){n,m}, (?:a+){n,m} => (?:a*){n,n}, (?:a+){n,n} */ 303 if (!isRepeatInfinite(upper) && upper > 1 && greedy) { 304 upper = lower == 0 ? 1 : lower; 305 } 306 } 307 } 308 309 default: 310 break; 311 } 312 313 setTarget(tgt); 314 return 0; 315 } 316 317 public static final int REPEAT_INFINITE = -1; 318 public static boolean isRepeatInfinite(final int n) { 319 return n == REPEAT_INFINITE; 320 } 321 322} 323