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.runtime.regexp.joni.ast;
  21 
  22 import static jdk.nashorn.internal.runtime.regexp.joni.ast.QuantifierNode.ReduceType.A;
  23 import static jdk.nashorn.internal.runtime.regexp.joni.ast.QuantifierNode.ReduceType.AQ;
  24 import static jdk.nashorn.internal.runtime.regexp.joni.ast.QuantifierNode.ReduceType.ASIS;
  25 import static jdk.nashorn.internal.runtime.regexp.joni.ast.QuantifierNode.ReduceType.DEL;
  26 import static jdk.nashorn.internal.runtime.regexp.joni.ast.QuantifierNode.ReduceType.PQ_Q;
  27 import static jdk.nashorn.internal.runtime.regexp.joni.ast.QuantifierNode.ReduceType.P_QQ;
  28 import static jdk.nashorn.internal.runtime.regexp.joni.ast.QuantifierNode.ReduceType.QQ;
  29 import jdk.nashorn.internal.runtime.regexp.joni.Config;
  30 import jdk.nashorn.internal.runtime.regexp.joni.ScanEnvironment;
  31 import jdk.nashorn.internal.runtime.regexp.joni.constants.TargetInfo;
  32 
  33 @SuppressWarnings("javadoc")
  34 public 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 }