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;
29import jdk.nashorn.internal.runtime.regexp.joni.Config;
30import jdk.nashorn.internal.runtime.regexp.joni.ScanEnvironment;
31import jdk.nashorn.internal.runtime.regexp.joni.constants.TargetInfo;
32
33@SuppressWarnings("javadoc")
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) {
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}
323