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 
QuantifierNode(final int lower, final int upper, final boolean byNumber)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
getType()87     public int getType() {
88         return QTFR;
89     }
90 
91     @Override
setChild(final Node newChild)92     protected void setChild(final Node newChild) {
93         target = newChild;
94     }
95 
96     @Override
getChild()97     protected Node getChild() {
98         return target;
99     }
100 
setTarget(final Node tgt)101     public void setTarget(final Node tgt) {
102         target = tgt;
103         tgt.parent = this;
104     }
105 
convertToString(final int flag)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
getName()114     public String getName() {
115         return "Quantifier";
116     }
117 
118     @Override
toString(final int level)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 
isAnyCharStar()133     public boolean isAnyCharStar() {
134         return greedy && isRepeatInfinite(upper) && target.getType() == CANY;
135     }
136 
137     /* ?:0, *:1, +:2, ??:3, *?:4, +?:5 */
popularNum()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 
set(final QuantifierNode other)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 
reduceNestedQuantifier(final QuantifierNode other)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")
setQuantifier(final Node tgt, final boolean group, final ScanEnvironment env, final char[] chars, final int p, final int end)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;
isRepeatInfinite(final int n)318     public static boolean isRepeatInfinite(final int n) {
319         return n == REPEAT_INFINITE;
320     }
321 
322 }
323