QuantifierNode.java revision 953:221a84ef44c0
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; 29 30import jdk.nashorn.internal.runtime.regexp.joni.Config; 31import jdk.nashorn.internal.runtime.regexp.joni.ScanEnvironment; 32import jdk.nashorn.internal.runtime.regexp.joni.constants.TargetInfo; 33 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) setByNumber(); 82 } 83 84 @Override 85 public int getType() { 86 return QTFR; 87 } 88 89 @Override 90 protected void setChild(final Node newChild) { 91 target = newChild; 92 } 93 94 @Override 95 protected Node getChild() { 96 return target; 97 } 98 99 public void setTarget(final Node tgt) { 100 target = tgt; 101 tgt.parent = this; 102 } 103 104 public StringNode convertToString(final int flag) { 105 final StringNode sn = new StringNode(); 106 sn.flag = flag; 107 sn.swap(this); 108 return sn; 109 } 110 111 @Override 112 public String getName() { 113 return "Quantifier"; 114 } 115 116 @Override 117 public String toString(final int level) { 118 final StringBuilder value = new StringBuilder(super.toString(level)); 119 value.append("\n target: " + pad(target, level + 1)); 120 value.append("\n lower: " + lower); 121 value.append("\n upper: " + upper); 122 value.append("\n greedy: " + greedy); 123 value.append("\n targetEmptyInfo: " + targetEmptyInfo); 124 value.append("\n headExact: " + pad(headExact, level + 1)); 125 value.append("\n nextHeadExact: " + pad(nextHeadExact, level + 1)); 126 value.append("\n isRefered: " + isRefered); 127 128 return value.toString(); 129 } 130 131 public boolean isAnyCharStar() { 132 return greedy && isRepeatInfinite(upper) && target.getType() == CANY; 133 } 134 135 /* ?:0, *:1, +:2, ??:3, *?:4, +?:5 */ 136 protected int popularNum() { 137 if (greedy) { 138 if (lower == 0) { 139 if (upper == 1) return 0; 140 else if (isRepeatInfinite(upper)) return 1; 141 } else if (lower == 1) { 142 if (isRepeatInfinite(upper)) return 2; 143 } 144 } else { 145 if (lower == 0) { 146 if (upper == 1) return 3; 147 else if (isRepeatInfinite(upper)) return 4; 148 } else if (lower == 1) { 149 if (isRepeatInfinite(upper)) return 5; 150 } 151 } 152 return -1; 153 } 154 155 protected void set(final QuantifierNode other) { 156 setTarget(other.target); 157 other.target = null; 158 lower = other.lower; 159 upper = other.upper; 160 greedy = other.greedy; 161 targetEmptyInfo = other.targetEmptyInfo; 162 163 //setHeadExact(other.headExact); 164 //setNextHeadExact(other.nextHeadExact); 165 headExact = other.headExact; 166 nextHeadExact = other.nextHeadExact; 167 isRefered = other.isRefered; 168 } 169 170 public void reduceNestedQuantifier(final QuantifierNode other) { 171 final int pnum = popularNum(); 172 final int cnum = other.popularNum(); 173 174 if (pnum < 0 || cnum < 0) return; 175 176 switch(REDUCE_TABLE[cnum][pnum]) { 177 case DEL: 178 // no need to set the parent here... 179 // swap ? 180 set(other); // *pnode = *cnode; ??? 181 break; 182 183 case A: 184 setTarget(other.target); 185 lower = 0; 186 upper = REPEAT_INFINITE; 187 greedy = true; 188 break; 189 190 case AQ: 191 setTarget(other.target); 192 lower = 0; 193 upper = REPEAT_INFINITE; 194 greedy = false; 195 break; 196 197 case QQ: 198 setTarget(other.target); 199 lower = 0; 200 upper = 1; 201 greedy = false; 202 break; 203 204 case P_QQ: 205 setTarget(other); 206 lower = 0; 207 upper = 1; 208 greedy = false; 209 other.lower = 1; 210 other.upper = REPEAT_INFINITE; 211 other.greedy = true; 212 return; 213 214 case PQ_Q: 215 setTarget(other); 216 lower = 0; 217 upper = 1; 218 greedy = true; 219 other.lower = 1; 220 other.upper = REPEAT_INFINITE; 221 other.greedy = false; 222 return; 223 224 case ASIS: 225 setTarget(other); 226 return; 227 } 228 // ??? remove the parent from target ??? 229 other.target = null; // remove target from reduced quantifier 230 } 231 232 @SuppressWarnings("fallthrough") 233 public int setQuantifier(final Node tgt, final boolean group, final ScanEnvironment env, final char[] chars, final int p, final int end) { 234 if (lower == 1 && upper == 1) return 1; 235 236 switch(tgt.getType()) { 237 238 case STR: 239 if (!group) { 240 final StringNode sn = (StringNode)tgt; 241 if (sn.canBeSplit()) { 242 final StringNode n = sn.splitLastChar(); 243 if (n != null) { 244 setTarget(n); 245 return 2; 246 } 247 } 248 } 249 break; 250 251 case QTFR: 252 /* check redundant double repeat. */ 253 /* verbose warn (?:.?)? etc... but not warn (.?)? etc... */ 254 final QuantifierNode qnt = (QuantifierNode)tgt; 255 final int nestQNum = popularNum(); 256 final int targetQNum = qnt.popularNum(); 257 258 if (Config.USE_WARNING_REDUNDANT_NESTED_REPEAT_OPERATOR) { 259 if (!isByNumber() && !qnt.isByNumber() && env.syntax.warnReduntantNestedRepeat()) { 260 switch(REDUCE_TABLE[targetQNum][nestQNum]) { 261 case ASIS: 262 break; 263 264 case DEL: 265 env.reg.getWarnings().warn(new String(chars, p, end) + 266 " redundant nested repeat operator"); 267 break; 268 269 default: 270 env.reg.getWarnings().warn(new String(chars, p, end) + 271 " nested repeat operator " + PopularQStr[targetQNum] + 272 " and " + PopularQStr[nestQNum] + " was replaced with '" + 273 ReduceQStr[REDUCE_TABLE[targetQNum][nestQNum].ordinal()] + "'"); 274 } 275 } 276 } // USE_WARNING_REDUNDANT_NESTED_REPEAT_OPERATOR 277 278 if (targetQNum >= 0) { 279 if (nestQNum >= 0) { 280 reduceNestedQuantifier(qnt); 281 return 0; 282 } else if (targetQNum == 1 || targetQNum == 2) { /* * or + */ 283 /* (?:a*){n,m}, (?:a+){n,m} => (?:a*){n,n}, (?:a+){n,n} */ 284 if (!isRepeatInfinite(upper) && upper > 1 && greedy) { 285 upper = lower == 0 ? 1 : lower; 286 } 287 } 288 } 289 290 default: 291 break; 292 } 293 294 setTarget(tgt); 295 return 0; 296 } 297 298 public static final int REPEAT_INFINITE = -1; 299 public static boolean isRepeatInfinite(final int n) { 300 return n == REPEAT_INFINITE; 301 } 302 303} 304