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 import java.lang.ref.WeakReference;
23 import jdk.nashorn.internal.runtime.regexp.joni.constants.StackPopLevel;
24 import jdk.nashorn.internal.runtime.regexp.joni.constants.StackType;
25
26 abstract class StackMachine extends Matcher implements StackType {
27 protected static final int INVALID_INDEX = -1;
28
29 protected StackEntry[]stack;
30 protected int stk; // stkEnd
31
32 protected final int[]repeatStk;
33 protected final int memStartStk, memEndStk;
34
35 protected StackMachine(final Regex regex, final char[] chars, final int p , final int end) {
36 super(regex, chars, p, end);
37
38 this.stack = regex.stackNeeded ? fetchStack() : null;
39 final int n = regex.numRepeat + (regex.numMem << 1);
40 this.repeatStk = n > 0 ? new int[n] : null;
41
42 memStartStk = regex.numRepeat - 1;
43 memEndStk = memStartStk + regex.numMem;
44 /* for index start from 1, mem_start_stk[1]..mem_start_stk[num_mem] */
45 /* for index start from 1, mem_end_stk[1]..mem_end_stk[num_mem] */
46 }
47
48 private static StackEntry[] allocateStack() {
49 final StackEntry[]stack = new StackEntry[Config.INIT_MATCH_STACK_SIZE];
50 stack[0] = new StackEntry();
51 return stack;
52 }
53
54 private void doubleStack() {
55 final StackEntry[] newStack = new StackEntry[stack.length << 1];
56 System.arraycopy(stack, 0, newStack, 0, stack.length);
57 stack = newStack;
58 }
59
60 static final ThreadLocal<WeakReference<StackEntry[]>> stacks
61 = new ThreadLocal<WeakReference<StackEntry[]>>() {
62 @SuppressWarnings("unused")
63 @Override
64 protected WeakReference<StackEntry[]> initialValue() {
65 return new WeakReference<StackEntry[]>(allocateStack());
66 }
67 };
68
69 @SuppressWarnings("unused")
70 private static StackEntry[] fetchStack() {
71 WeakReference<StackEntry[]> ref = stacks.get();
72 StackEntry[] stack = ref.get();
73 if (stack == null) {
74 ref = new WeakReference<StackEntry[]>(stack = allocateStack());
75 stacks.set(ref);
76 }
77 return stack;
78 }
79
80 protected final void init() {
81 if (stack != null) {
82 pushEnsured(ALT, regex.codeLength - 1); /* bottom stack */
83 }
84 if (repeatStk != null) {
85 for (int i=1; i<=regex.numMem; i++) {
86 repeatStk[i + memStartStk] = repeatStk[i + memEndStk] = INVALID_INDEX;
87 }
88 }
89 }
90
91 protected final StackEntry ensure1() {
92 if (stk >= stack.length) {
93 doubleStack();
94 }
95 StackEntry e = stack[stk];
96 if (e == null) {
97 stack[stk] = e = new StackEntry();
98 }
99 return e;
100 }
101
102 protected final void pushType(final int type) {
103 ensure1().type = type;
104 stk++;
105 }
106
107 private void push(final int type, final int pat, final int s, final int prev) {
108 final StackEntry e = ensure1();
109 e.type = type;
110 e.setStatePCode(pat);
111 e.setStatePStr(s);
112 e.setStatePStrPrev(prev);
113 stk++;
114 }
115
116 protected final void pushEnsured(final int type, final int pat) {
117 final StackEntry e = stack[stk];
118 e.type = type;
119 e.setStatePCode(pat);
120 stk++;
121 }
122
123 protected final void pushAlt(final int pat, final int s, final int prev) {
124 push(ALT, pat, s, prev);
125 }
126
127 protected final void pushPos(final int s, final int prev) {
128 push(POS, -1 /*NULL_UCHARP*/, s, prev);
129 }
130
131 protected final void pushPosNot(final int pat, final int s, final int prev) {
132 push(POS_NOT, pat, s, prev);
133 }
134
135 protected final void pushStopBT() {
136 pushType(STOP_BT);
137 }
138
139 protected final void pushLookBehindNot(final int pat, final int s, final int sprev) {
140 push(LOOK_BEHIND_NOT, pat, s, sprev);
141 }
142
143 protected final void pushRepeat(final int id, final int pat) {
144 final StackEntry e = ensure1();
145 e.type = REPEAT;
146 e.setRepeatNum(id);
147 e.setRepeatPCode(pat);
148 e.setRepeatCount(0);
149 stk++;
150 }
151
152 protected final void pushRepeatInc(final int sindex) {
153 final StackEntry e = ensure1();
154 e.type = REPEAT_INC;
155 e.setSi(sindex);
156 stk++;
157 }
158
159 protected final void pushMemStart(final int mnum, final int s) {
160 final StackEntry e = ensure1();
161 e.type = MEM_START;
162 e.setMemNum(mnum);
163 e.setMemPstr(s);
164 e.setMemStart(repeatStk[memStartStk + mnum]);
165 e.setMemEnd(repeatStk[memEndStk + mnum]);
166 repeatStk[memStartStk + mnum] = stk;
167 repeatStk[memEndStk + mnum] = INVALID_INDEX;
168 stk++;
169 }
170
171 protected final void pushMemEnd(final int mnum, final int s) {
172 final StackEntry e = ensure1();
173 e.type = MEM_END;
174 e.setMemNum(mnum);
175 e.setMemPstr(s);
176 e.setMemStart(repeatStk[memStartStk + mnum]);
177 e.setMemEnd(repeatStk[memEndStk + mnum]);
178 repeatStk[memEndStk + mnum] = stk;
179 stk++;
180 }
181
182 protected final void pushMemEndMark(final int mnum) {
183 final StackEntry e = ensure1();
184 e.type = MEM_END_MARK;
185 e.setMemNum(mnum);
186 stk++;
187 }
188
189 protected final int getMemStart(final int mnum) {
190 int level = 0;
191 int stkp = stk;
192
193 while (stkp > 0) {
194 stkp--;
195 final StackEntry e = stack[stkp];
196 if ((e.type & MASK_MEM_END_OR_MARK) != 0 && e.getMemNum() == mnum) {
197 level++;
198 } else if (e.type == MEM_START && e.getMemNum() == mnum) {
199 if (level == 0) {
200 break;
201 }
202 level--;
203 }
204 }
205 return stkp;
206 }
207
208 protected final void pushNullCheckStart(final int cnum, final int s) {
209 final StackEntry e = ensure1();
210 e.type = NULL_CHECK_START;
211 e.setNullCheckNum(cnum);
212 e.setNullCheckPStr(s);
213 stk++;
214 }
215
216 protected final void pushNullCheckEnd(final int cnum) {
217 final StackEntry e = ensure1();
218 e.type = NULL_CHECK_END;
219 e.setNullCheckNum(cnum);
220 stk++;
221 }
222
223 // stack debug routines here
224 // ...
225
226 protected final void popOne() {
227 stk--;
228 }
229
230 protected final StackEntry pop() {
231 switch (regex.stackPopLevel) {
232 case StackPopLevel.FREE:
233 return popFree();
234 case StackPopLevel.MEM_START:
235 return popMemStart();
236 default:
237 return popDefault();
238 }
239 }
240
241 private StackEntry popFree() {
242 while (true) {
243 final StackEntry e = stack[--stk];
244
245 if ((e.type & MASK_POP_USED) != 0) {
246 return e;
247 }
248 }
249 }
250
251 private StackEntry popMemStart() {
252 while (true) {
253 final StackEntry e = stack[--stk];
254
255 if ((e.type & MASK_POP_USED) != 0) {
256 return e;
257 } else if (e.type == MEM_START) {
258 repeatStk[memStartStk + e.getMemNum()] = e.getMemStart();
259 repeatStk[memEndStk + e.getMemNum()] = e.getMemEnd();
260 }
261 }
262 }
263
264 private StackEntry popDefault() {
265 while (true) {
266 final StackEntry e = stack[--stk];
267
268 if ((e.type & MASK_POP_USED) != 0) {
269 return e;
270 } else if (e.type == MEM_START) {
271 repeatStk[memStartStk + e.getMemNum()] = e.getMemStart();
272 repeatStk[memEndStk + e.getMemNum()] = e.getMemEnd();
273 } else if (e.type == REPEAT_INC) {
274 //int si = stack[stk + IREPEAT_INC_SI];
275 //stack[si + IREPEAT_COUNT]--;
276 stack[e.getSi()].decreaseRepeatCount();
277 } else if (e.type == MEM_END) {
278 repeatStk[memStartStk + e.getMemNum()] = e.getMemStart();
279 repeatStk[memEndStk + e.getMemNum()] = e.getMemEnd();
280 }
281 }
282 }
283
284 protected final void popTilPosNot() {
285 while (true) {
286 stk--;
287 final StackEntry e = stack[stk];
288
289 if (e.type == POS_NOT) {
290 break;
291 } else if (e.type == MEM_START) {
292 repeatStk[memStartStk + e.getMemNum()] = e.getMemStart();
293 repeatStk[memEndStk + e.getMemNum()] = e.getMemStart();
294 } else if (e.type == REPEAT_INC) {
295 //int si = stack[stk + IREPEAT_INC_SI];
296 //stack[si + IREPEAT_COUNT]--;
297 stack[e.getSi()].decreaseRepeatCount();
298 } else if (e.type == MEM_END){
299 repeatStk[memStartStk + e.getMemNum()] = e.getMemStart();
300 repeatStk[memEndStk + e.getMemNum()] = e.getMemStart();
301 }
302 }
303 }
304
305 protected final void popTilLookBehindNot() {
306 while (true) {
307 stk--;
308 final StackEntry e = stack[stk];
309
310 if (e.type == LOOK_BEHIND_NOT) {
311 break;
312 } else if (e.type == MEM_START) {
313 repeatStk[memStartStk + e.getMemNum()] = e.getMemStart();
314 repeatStk[memEndStk + e.getMemNum()] = e.getMemEnd();
315 } else if (e.type == REPEAT_INC) {
316 //int si = stack[stk + IREPEAT_INC_SI];
317 //stack[si + IREPEAT_COUNT]--;
318 stack[e.getSi()].decreaseRepeatCount();
319 } else if (e.type == MEM_END) {
320 repeatStk[memStartStk + e.getMemNum()] = e.getMemStart();
321 repeatStk[memEndStk + e.getMemNum()] = e.getMemEnd();
322 }
323 }
324 }
325
326 protected final int posEnd() {
327 int k = stk;
328 while (true) {
329 k--;
330 final StackEntry e = stack[k];
331 if ((e.type & MASK_TO_VOID_TARGET) != 0) {
332 e.type = VOID;
333 } else if (e.type == POS) {
334 e.type = VOID;
335 break;
336 }
337 }
338 return k;
339 }
340
341 protected final void stopBtEnd() {
342 int k = stk;
343 while (true) {
344 k--;
345 final StackEntry e = stack[k];
346
347 if ((e.type & MASK_TO_VOID_TARGET) != 0) {
348 e.type = VOID;
349 } else if (e.type == STOP_BT) {
350 e.type = VOID;
351 break;
352 }
353 }
354 }
355
356 // int for consistency with other null check routines
357 protected final int nullCheck(final int id, final int s) {
358 int k = stk;
359 while (true) {
360 k--;
361 final StackEntry e = stack[k];
362
363 if (e.type == NULL_CHECK_START) {
364 if (e.getNullCheckNum() == id) {
365 return e.getNullCheckPStr() == s ? 1 : 0;
366 }
367 }
368 }
369 }
370
371 protected final int nullCheckMemSt(final int id, final int s) {
372 // Return -1 here to cause operation to fail
373 return -nullCheck(id, s);
374 }
375
376 protected final int getRepeat(final int id) {
377 int level = 0;
378 int k = stk;
379 while (true) {
380 k--;
381 final StackEntry e = stack[k];
382
383 if (e.type == REPEAT) {
384 if (level == 0) {
385 if (e.getRepeatNum() == id) {
386 return k;
387 }
388 }
389 } else if (e.type == CALL_FRAME) {
390 level--;
391 } else if (e.type == RETURN) {
392 level++;
393 }
394 }
395 }
396
397 protected final int sreturn() {
398 int level = 0;
399 int k = stk;
400 while (true) {
401 k--;
402 final StackEntry e = stack[k];
403
404 if (e.type == CALL_FRAME) {
405 if (level == 0) {
406 return e.getCallFrameRetAddr();
407 }
408 level--;
409 } else if (e.type == RETURN) {
410 level++;
411 }
412 }
413 }
414 }