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