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;
21
22@SuppressWarnings("javadoc")
23public abstract class SearchAlgorithm {
24
25    public abstract String getName();
26    public abstract int search(Regex regex, char[] text, int textP, int textEnd, int textRange);
27    public abstract int searchBackward(Regex regex, char[] text, int textP, int adjustText, int textEnd, int textStart, int s_, int range_);
28
29
30    public static final SearchAlgorithm NONE = new SearchAlgorithm() {
31
32        @Override
33        public final String getName() {
34            return "NONE";
35        }
36
37        @Override
38        public final int search(final Regex regex, final char[] text, final int textP, final int textEnd, final int textRange) {
39            return textP;
40        }
41
42        @Override
43        public final int searchBackward(final Regex regex, final char[] text, final int textP, final int adjustText, final int textEnd, final int textStart, final int s_, final int range_) {
44            return textP;
45        }
46
47    };
48
49    public static final SearchAlgorithm SLOW = new SearchAlgorithm() {
50
51        @Override
52        public final String getName() {
53            return "EXACT";
54        }
55
56        @Override
57        public final int search(final Regex regex, final char[] text, final int textP, final int textEnd, final int textRange) {
58            final char[] target = regex.exact;
59            final int targetP = regex.exactP;
60            final int targetEnd = regex.exactEnd;
61
62
63            int end = textEnd;
64            end -= targetEnd - targetP - 1;
65
66            if (end > textRange) {
67                end = textRange;
68            }
69
70            int s = textP;
71
72            while (s < end) {
73                if (text[s] == target[targetP]) {
74                    int p = s + 1;
75                    int t = targetP + 1;
76                    while (t < targetEnd) {
77                        if (target[t] != text[p++]) {
78                            break;
79                        }
80                        t++;
81                    }
82
83                    if (t == targetEnd) {
84                        return s;
85                    }
86                }
87                s++;
88            }
89
90            return -1;
91        }
92
93        @Override
94        public final int searchBackward(final Regex regex, final char[] text, final int textP, final int adjustText, final int textEnd, final int textStart, final int s_, final int range_) {
95            final char[] target = regex.exact;
96            final int targetP = regex.exactP;
97            final int targetEnd = regex.exactEnd;
98
99            int s = textEnd;
100            s -= targetEnd - targetP;
101
102            if (s > textStart) {
103                s = textStart;
104            }
105
106            while (s >= textP) {
107                if (text[s] == target[targetP]) {
108                    int p = s + 1;
109                    int t = targetP + 1;
110                    while (t < targetEnd) {
111                        if (target[t] != text[p++]) {
112                            break;
113                        }
114                        t++;
115                    }
116                    if (t == targetEnd) {
117                        return s;
118                    }
119                }
120                // s = enc.prevCharHead or s = s <= adjustText ? -1 : s - 1;
121                s--;
122            }
123            return -1;
124        }
125    };
126
127    public static final class SLOW_IC extends SearchAlgorithm {
128        public SLOW_IC(final Regex regex) {
129            //empty
130        }
131
132        @Override
133        public final String getName() {
134            return "EXACT_IC";
135        }
136
137        @Override
138        public final int search(final Regex regex, final char[] text, final int textP, final int textEnd, final int textRange) {
139            final char[] target = regex.exact;
140            final int targetP = regex.exactP;
141            final int targetEnd = regex.exactEnd;
142
143            int end = textEnd;
144            end -= targetEnd - targetP - 1;
145
146            if (end > textRange) {
147                end = textRange;
148            }
149            int s = textP;
150
151            while (s < end) {
152                if (lowerCaseMatch(target, targetP, targetEnd, text, s, textEnd)) {
153                    return s;
154                }
155                s++;
156            }
157            return -1;
158        }
159
160        @Override
161        public final int searchBackward(final Regex regex, final char[] text, final int textP, final int adjustText, final int textEnd, final int textStart, final int s_, final int range_) {
162            final char[] target = regex.exact;
163            final int targetP = regex.exactP;
164            final int targetEnd = regex.exactEnd;
165
166            int s = textEnd;
167            s -= targetEnd - targetP;
168
169            if (s > textStart) {
170                s = textStart;
171            }
172
173            while (s >= textP) {
174                if (lowerCaseMatch(target, targetP, targetEnd, text, s, textEnd)) {
175                    return s;
176                }
177                s = EncodingHelper.prevCharHead(adjustText, s);
178            }
179            return -1;
180        }
181
182        private static boolean lowerCaseMatch(final char[] t, final int tPp, final int tEnd,
183                                       final char[] chars, final int pp, final int end) {
184
185            for (int tP = tPp, p = pp; tP < tEnd; ) {
186                if (t[tP++] != EncodingHelper.toLowerCase(chars[p++])) {
187                    return false;
188                }
189            }
190            return true;
191        }
192    }
193
194    public static final SearchAlgorithm BM = new SearchAlgorithm() {
195
196        @Override
197        public final String getName() {
198            return "EXACT_BM";
199        }
200
201        @Override
202        public final int search(final Regex regex, final char[] text, final int textP, final int textEnd, final int textRange) {
203            final char[] target = regex.exact;
204            final int targetP = regex.exactP;
205            final int targetEnd = regex.exactEnd;
206
207            int end = textRange + (targetEnd - targetP) - 1;
208            if (end > textEnd) {
209                end = textEnd;
210            }
211
212            final int tail = targetEnd - 1;
213            int s = textP + (targetEnd - targetP) - 1;
214
215            if (regex.intMap == null) {
216                while (s < end) {
217                    int p = s;
218                    int t = tail;
219
220                    while (text[p] == target[t]) {
221                        if (t == targetP) {
222                            return p;
223                        }
224                        p--; t--;
225                    }
226
227                    s += regex.map[text[s] & 0xff];
228                }
229            } else { /* see int_map[] */
230                while (s < end) {
231                    int p = s;
232                    int t = tail;
233
234                    while (text[p] == target[t]) {
235                        if (t == targetP) {
236                            return p;
237                        }
238                        p--; t--;
239                    }
240
241                    s += regex.intMap[text[s] & 0xff];
242                }
243            }
244            return -1;
245        }
246
247        private static final int BM_BACKWARD_SEARCH_LENGTH_THRESHOLD = 100;
248
249        @Override
250        public final int searchBackward(final Regex regex, final char[] text, final int textP, final int adjustText, final int textEnd, final int textStart, final int s_, final int range_) {
251            final char[] target = regex.exact;
252            final int targetP = regex.exactP;
253            final int targetEnd = regex.exactEnd;
254
255            if (regex.intMapBackward == null) {
256                if (s_ - range_ < BM_BACKWARD_SEARCH_LENGTH_THRESHOLD) {
257                    // goto exact_method;
258                    return SLOW.searchBackward(regex, text, textP, adjustText, textEnd, textStart, s_, range_);
259                }
260                setBmBackwardSkip(regex, target, targetP, targetEnd);
261            }
262
263            int s = textEnd - (targetEnd - targetP);
264
265            if (textStart < s) {
266                s = textStart;
267            }
268
269            while (s >= textP) {
270                int p = s;
271                int t = targetP;
272                while (t < targetEnd && text[p] == target[t]) {
273                    p++; t++;
274                }
275                if (t == targetEnd) {
276                    return s;
277                }
278
279                s -= regex.intMapBackward[text[s] & 0xff];
280            }
281            return -1;
282        }
283
284
285        private void setBmBackwardSkip(final Regex regex, final char[] chars, final int p, final int end) {
286            int[] skip;
287            if (regex.intMapBackward == null) {
288                skip = new int[Config.CHAR_TABLE_SIZE];
289                regex.intMapBackward = skip;
290            } else {
291                skip = regex.intMapBackward;
292            }
293
294            final int len = end - p;
295
296            for (int i=0; i<Config.CHAR_TABLE_SIZE; i++) {
297                skip[i] = len;
298            }
299            for (int i=len-1; i>0; i--) {
300                skip[chars[i] & 0xff] = i;
301            }
302        }
303    };
304
305    public static final SearchAlgorithm MAP = new SearchAlgorithm() {
306
307        @Override
308        public final String getName() {
309            return "MAP";
310        }
311
312        @Override
313        public final int search(final Regex regex, final char[] text, final int textP, final int textEnd, final int textRange) {
314            final byte[] map = regex.map;
315            int s = textP;
316
317            while (s < textRange) {
318                if (text[s] > 0xff || map[text[s]] != 0) {
319                    return s;
320                }
321                s++;
322            }
323            return -1;
324        }
325
326        @Override
327        public final int searchBackward(final Regex regex, final char[] text, final int textP, final int adjustText, final int textEnd, final int textStart, final int s_, final int range_) {
328            final byte[] map = regex.map;
329            int s = textStart;
330
331            if (s >= textEnd) {
332                s = textEnd - 1;
333            }
334            while (s >= textP) {
335                if (text[s] > 0xff || map[text[s]] != 0) {
336                    return s;
337                }
338                s--;
339            }
340            return -1;
341        }
342    };
343
344}
345