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 }