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 public 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(Regex regex, char[] text, int textP, int textEnd, int textRange) {
38 return textP;
39 }
40
41 @Override
42 public final int searchBackward(Regex regex, char[] text, int textP, int adjustText, int textEnd, int textStart, int s_, 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(Regex regex, char[] text, int textP, int textEnd, int textRange) {
57 char[] target = regex.exact;
58 int targetP = regex.exactP;
59 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(Regex regex, char[] text, int textP, int adjustText, int textEnd, int textStart, int s_, int range_) {
88 char[] target = regex.exact;
89 int targetP = regex.exactP;
90 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(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(Regex regex, char[] text, int textP, int textEnd, int textRange) {
130 char[] target = regex.exact;
131 int targetP = regex.exactP;
132 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(Regex regex, char[] text, int textP, int adjustText, int textEnd, int textStart, int s_, int range_) {
149 char[] target = regex.exact;
150 int targetP = regex.exactP;
151 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(char[] t, int tP, int tEnd,
168 char[] chars, int p, int end) {
169
170 while (tP < tEnd) {
171 if (t[tP++] != Character.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(Regex regex, char[] text, int textP, int textEnd, int textRange) {
186 char[] target = regex.exact;
187 int targetP = regex.exactP;
188 int targetEnd = regex.exactEnd;
189
190 int end = textRange + (targetEnd - targetP) - 1;
191 if (end > textEnd) end = textEnd;
192
193 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(Regex regex, char[] text, int textP, int adjustText, int textEnd, int textStart, int s_, int range_) {
228 char[] target = regex.exact;
229 int targetP = regex.exactP;
230 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(Regex regex, char[] chars, int p, 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 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(Regex regex, char[] text, int textP, int textEnd, int textRange) {
285 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(Regex regex, char[] text, int textP, int adjustText, int textEnd, int textStart, int s_, int range_) {
297 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 }
--- EOF ---