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;
21
22 @SuppressWarnings("javadoc")
23 public 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 }