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