Line data Source code
1 : // Copyright 2008-2009 the V8 project authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file.
4 :
5 : #include "src/regexp/regexp-macro-assembler-irregexp.h"
6 :
7 : #include "src/ast/ast.h"
8 : #include "src/objects-inl.h"
9 : #include "src/regexp/bytecodes-irregexp.h"
10 : #include "src/regexp/regexp-macro-assembler-irregexp-inl.h"
11 : #include "src/regexp/regexp-macro-assembler.h"
12 :
13 : namespace v8 {
14 : namespace internal {
15 :
16 3275 : RegExpMacroAssemblerIrregexp::RegExpMacroAssemblerIrregexp(Isolate* isolate,
17 : Zone* zone)
18 : : RegExpMacroAssembler(isolate, zone),
19 : buffer_(Vector<byte>::New(1024)),
20 : pc_(0),
21 : own_buffer_(true),
22 : advance_current_end_(kInvalidPC),
23 9825 : isolate_(isolate) {}
24 :
25 9820 : RegExpMacroAssemblerIrregexp::~RegExpMacroAssemblerIrregexp() {
26 3275 : if (backtrack_.is_linked()) backtrack_.Unuse();
27 3275 : if (own_buffer_) buffer_.Dispose();
28 6545 : }
29 :
30 :
31 : RegExpMacroAssemblerIrregexp::IrregexpImplementation
32 0 : RegExpMacroAssemblerIrregexp::Implementation() {
33 0 : return kBytecodeImplementation;
34 : }
35 :
36 :
37 322931 : void RegExpMacroAssemblerIrregexp::Bind(Label* l) {
38 322931 : advance_current_end_ = kInvalidPC;
39 : DCHECK(!l->is_bound());
40 322931 : if (l->is_linked()) {
41 : int pos = l->pos();
42 1160719 : while (pos != 0) {
43 : int fixup = pos;
44 482825 : pos = *reinterpret_cast<int32_t*>(buffer_.start() + fixup);
45 482825 : *reinterpret_cast<uint32_t*>(buffer_.start() + fixup) = pc_;
46 : }
47 : }
48 322931 : l->bind_to(pc_);
49 322931 : }
50 :
51 :
52 541523 : void RegExpMacroAssemblerIrregexp::EmitOrLink(Label* l) {
53 541523 : if (l == nullptr) l = &backtrack_;
54 541523 : if (l->is_bound()) {
55 58698 : Emit32(l->pos());
56 : } else {
57 : int pos = 0;
58 482825 : if (l->is_linked()) {
59 : pos = l->pos();
60 : }
61 482825 : l->link_to(pc_);
62 482825 : Emit32(pos);
63 : }
64 541523 : }
65 :
66 :
67 10363 : void RegExpMacroAssemblerIrregexp::PopRegister(int register_index) {
68 : DCHECK_LE(0, register_index);
69 : DCHECK_GE(kMaxRegister, register_index);
70 10363 : Emit(BC_POP_REGISTER, register_index);
71 10363 : }
72 :
73 :
74 10363 : void RegExpMacroAssemblerIrregexp::PushRegister(
75 : int register_index,
76 : StackCheckFlag check_stack_limit) {
77 : DCHECK_LE(0, register_index);
78 : DCHECK_GE(kMaxRegister, register_index);
79 10363 : Emit(BC_PUSH_REGISTER, register_index);
80 10363 : }
81 :
82 :
83 53607 : void RegExpMacroAssemblerIrregexp::WriteCurrentPositionToRegister(
84 : int register_index, int cp_offset) {
85 : DCHECK_LE(0, register_index);
86 : DCHECK_GE(kMaxRegister, register_index);
87 53607 : Emit(BC_SET_REGISTER_TO_CP, register_index);
88 53607 : Emit32(cp_offset); // Current position offset.
89 53607 : }
90 :
91 :
92 22557 : void RegExpMacroAssemblerIrregexp::ClearRegisters(int reg_from, int reg_to) {
93 : DCHECK(reg_from <= reg_to);
94 108743 : for (int reg = reg_from; reg <= reg_to; reg++) {
95 43093 : SetRegister(reg, -1);
96 : }
97 22557 : }
98 :
99 :
100 881 : void RegExpMacroAssemblerIrregexp::ReadCurrentPositionFromRegister(
101 : int register_index) {
102 : DCHECK_LE(0, register_index);
103 : DCHECK_GE(kMaxRegister, register_index);
104 881 : Emit(BC_SET_CP_TO_REGISTER, register_index);
105 881 : }
106 :
107 :
108 874 : void RegExpMacroAssemblerIrregexp::WriteStackPointerToRegister(
109 : int register_index) {
110 : DCHECK_LE(0, register_index);
111 : DCHECK_GE(kMaxRegister, register_index);
112 874 : Emit(BC_SET_REGISTER_TO_SP, register_index);
113 874 : }
114 :
115 :
116 881 : void RegExpMacroAssemblerIrregexp::ReadStackPointerFromRegister(
117 : int register_index) {
118 : DCHECK_LE(0, register_index);
119 : DCHECK_GE(kMaxRegister, register_index);
120 881 : Emit(BC_SET_SP_TO_REGISTER, register_index);
121 881 : }
122 :
123 :
124 37 : void RegExpMacroAssemblerIrregexp::SetCurrentPositionFromEnd(int by) {
125 : DCHECK(is_uint24(by));
126 37 : Emit(BC_SET_CURRENT_POSITION_FROM_END, by);
127 37 : }
128 :
129 :
130 43747 : void RegExpMacroAssemblerIrregexp::SetRegister(int register_index, int to) {
131 : DCHECK_LE(0, register_index);
132 : DCHECK_GE(kMaxRegister, register_index);
133 43747 : Emit(BC_SET_REGISTER, register_index);
134 43747 : Emit32(to);
135 43747 : }
136 :
137 :
138 704 : void RegExpMacroAssemblerIrregexp::AdvanceRegister(int register_index, int by) {
139 : DCHECK_LE(0, register_index);
140 : DCHECK_GE(kMaxRegister, register_index);
141 704 : Emit(BC_ADVANCE_REGISTER, register_index);
142 704 : Emit32(by);
143 704 : }
144 :
145 :
146 65923 : void RegExpMacroAssemblerIrregexp::PopCurrentPosition() {
147 : Emit(BC_POP_CP, 0);
148 65923 : }
149 :
150 :
151 67974 : void RegExpMacroAssemblerIrregexp::PushCurrentPosition() {
152 : Emit(BC_PUSH_CP, 0);
153 67974 : }
154 :
155 :
156 3434 : void RegExpMacroAssemblerIrregexp::Backtrack() {
157 : Emit(BC_POP_BT, 0);
158 3434 : }
159 :
160 :
161 182850 : void RegExpMacroAssemblerIrregexp::GoTo(Label* l) {
162 182850 : if (advance_current_end_ == pc_) {
163 : // Combine advance current and goto.
164 18738 : pc_ = advance_current_start_;
165 18738 : Emit(BC_ADVANCE_CP_AND_GOTO, advance_current_offset_);
166 18738 : EmitOrLink(l);
167 18738 : advance_current_end_ = kInvalidPC;
168 : } else {
169 : // Regular goto.
170 : Emit(BC_GOTO, 0);
171 164112 : EmitOrLink(l);
172 : }
173 182850 : }
174 :
175 :
176 71976 : void RegExpMacroAssemblerIrregexp::PushBacktrack(Label* l) {
177 : Emit(BC_PUSH_BT, 0);
178 71976 : EmitOrLink(l);
179 71976 : }
180 :
181 :
182 4393 : bool RegExpMacroAssemblerIrregexp::Succeed() {
183 : Emit(BC_SUCCEED, 0);
184 4393 : return false; // Restart matching for global regexp not supported.
185 : }
186 :
187 :
188 3280 : void RegExpMacroAssemblerIrregexp::Fail() {
189 : Emit(BC_FAIL, 0);
190 3280 : }
191 :
192 :
193 73391 : void RegExpMacroAssemblerIrregexp::AdvanceCurrentPosition(int by) {
194 : DCHECK_LE(kMinCPOffset, by);
195 : DCHECK_GE(kMaxCPOffset, by);
196 73391 : advance_current_start_ = pc_;
197 73391 : advance_current_offset_ = by;
198 73391 : Emit(BC_ADVANCE_CP, by);
199 73391 : advance_current_end_ = pc_;
200 73391 : }
201 :
202 :
203 2051 : void RegExpMacroAssemblerIrregexp::CheckGreedyLoop(
204 : Label* on_tos_equals_current_position) {
205 : Emit(BC_CHECK_GREEDY, 0);
206 2051 : EmitOrLink(on_tos_equals_current_position);
207 2051 : }
208 :
209 :
210 192847 : void RegExpMacroAssemblerIrregexp::LoadCurrentCharacter(int cp_offset,
211 : Label* on_failure,
212 : bool check_bounds,
213 : int characters) {
214 : DCHECK_LE(kMinCPOffset, cp_offset);
215 : DCHECK_GE(kMaxCPOffset, cp_offset);
216 : int bytecode;
217 192847 : if (check_bounds) {
218 77305 : if (characters == 4) {
219 : bytecode = BC_LOAD_4_CURRENT_CHARS;
220 77305 : } else if (characters == 2) {
221 : bytecode = BC_LOAD_2_CURRENT_CHARS;
222 : } else {
223 : DCHECK_EQ(1, characters);
224 : bytecode = BC_LOAD_CURRENT_CHAR;
225 : }
226 : } else {
227 115542 : if (characters == 4) {
228 : bytecode = BC_LOAD_4_CURRENT_CHARS_UNCHECKED;
229 115542 : } else if (characters == 2) {
230 : bytecode = BC_LOAD_2_CURRENT_CHARS_UNCHECKED;
231 : } else {
232 : DCHECK_EQ(1, characters);
233 : bytecode = BC_LOAD_CURRENT_CHAR_UNCHECKED;
234 : }
235 : }
236 192847 : Emit(bytecode, cp_offset);
237 192847 : if (check_bounds) EmitOrLink(on_failure);
238 192847 : }
239 :
240 :
241 2353 : void RegExpMacroAssemblerIrregexp::CheckCharacterLT(uc16 limit,
242 : Label* on_less) {
243 2353 : Emit(BC_CHECK_LT, limit);
244 2353 : EmitOrLink(on_less);
245 2353 : }
246 :
247 :
248 2900 : void RegExpMacroAssemblerIrregexp::CheckCharacterGT(uc16 limit,
249 : Label* on_greater) {
250 2900 : Emit(BC_CHECK_GT, limit);
251 2900 : EmitOrLink(on_greater);
252 2900 : }
253 :
254 :
255 39766 : void RegExpMacroAssemblerIrregexp::CheckCharacter(uint32_t c, Label* on_equal) {
256 39766 : if (c > MAX_FIRST_ARG) {
257 : Emit(BC_CHECK_4_CHARS, 0);
258 0 : Emit32(c);
259 : } else {
260 39766 : Emit(BC_CHECK_CHAR, c);
261 : }
262 39766 : EmitOrLink(on_equal);
263 39766 : }
264 :
265 :
266 51 : void RegExpMacroAssemblerIrregexp::CheckAtStart(Label* on_at_start) {
267 : Emit(BC_CHECK_AT_START, 0);
268 51 : EmitOrLink(on_at_start);
269 51 : }
270 :
271 :
272 496 : void RegExpMacroAssemblerIrregexp::CheckNotAtStart(int cp_offset,
273 : Label* on_not_at_start) {
274 496 : Emit(BC_CHECK_NOT_AT_START, cp_offset);
275 496 : EmitOrLink(on_not_at_start);
276 496 : }
277 :
278 :
279 145653 : void RegExpMacroAssemblerIrregexp::CheckNotCharacter(uint32_t c,
280 : Label* on_not_equal) {
281 145653 : if (c > MAX_FIRST_ARG) {
282 : Emit(BC_CHECK_NOT_4_CHARS, 0);
283 0 : Emit32(c);
284 : } else {
285 145653 : Emit(BC_CHECK_NOT_CHAR, c);
286 : }
287 145653 : EmitOrLink(on_not_equal);
288 145653 : }
289 :
290 :
291 1011 : void RegExpMacroAssemblerIrregexp::CheckCharacterAfterAnd(
292 : uint32_t c,
293 : uint32_t mask,
294 : Label* on_equal) {
295 1011 : if (c > MAX_FIRST_ARG) {
296 : Emit(BC_AND_CHECK_4_CHARS, 0);
297 0 : Emit32(c);
298 : } else {
299 1011 : Emit(BC_AND_CHECK_CHAR, c);
300 : }
301 1011 : Emit32(mask);
302 1011 : EmitOrLink(on_equal);
303 1011 : }
304 :
305 :
306 1284 : void RegExpMacroAssemblerIrregexp::CheckNotCharacterAfterAnd(
307 : uint32_t c,
308 : uint32_t mask,
309 : Label* on_not_equal) {
310 1284 : if (c > MAX_FIRST_ARG) {
311 : Emit(BC_AND_CHECK_NOT_4_CHARS, 0);
312 0 : Emit32(c);
313 : } else {
314 1284 : Emit(BC_AND_CHECK_NOT_CHAR, c);
315 : }
316 1284 : Emit32(mask);
317 1284 : EmitOrLink(on_not_equal);
318 1284 : }
319 :
320 :
321 12 : void RegExpMacroAssemblerIrregexp::CheckNotCharacterAfterMinusAnd(
322 : uc16 c,
323 : uc16 minus,
324 : uc16 mask,
325 : Label* on_not_equal) {
326 12 : Emit(BC_MINUS_AND_CHECK_NOT_CHAR, c);
327 12 : Emit16(minus);
328 12 : Emit16(mask);
329 12 : EmitOrLink(on_not_equal);
330 12 : }
331 :
332 :
333 3798 : void RegExpMacroAssemblerIrregexp::CheckCharacterInRange(
334 : uc16 from,
335 : uc16 to,
336 : Label* on_in_range) {
337 : Emit(BC_CHECK_CHAR_IN_RANGE, 0);
338 3798 : Emit16(from);
339 3798 : Emit16(to);
340 3798 : EmitOrLink(on_in_range);
341 3798 : }
342 :
343 :
344 7161 : void RegExpMacroAssemblerIrregexp::CheckCharacterNotInRange(
345 : uc16 from,
346 : uc16 to,
347 : Label* on_not_in_range) {
348 : Emit(BC_CHECK_CHAR_NOT_IN_RANGE, 0);
349 7161 : Emit16(from);
350 7161 : Emit16(to);
351 7161 : EmitOrLink(on_not_in_range);
352 7161 : }
353 :
354 :
355 1570 : void RegExpMacroAssemblerIrregexp::CheckBitInTable(
356 : Handle<ByteArray> table, Label* on_bit_set) {
357 : Emit(BC_CHECK_BIT_IN_TABLE, 0);
358 1570 : EmitOrLink(on_bit_set);
359 51810 : for (int i = 0; i < kTableSize; i += kBitsPerByte) {
360 : int byte = 0;
361 427040 : for (int j = 0; j < kBitsPerByte; j++) {
362 401920 : if (table->get(i + j) != 0) byte |= 1 << j;
363 : }
364 : Emit8(byte);
365 : }
366 1570 : }
367 :
368 :
369 121 : void RegExpMacroAssemblerIrregexp::CheckNotBackReference(int start_reg,
370 : bool read_backward,
371 : Label* on_not_equal) {
372 : DCHECK_LE(0, start_reg);
373 : DCHECK_GE(kMaxRegister, start_reg);
374 121 : Emit(read_backward ? BC_CHECK_NOT_BACK_REF_BACKWARD : BC_CHECK_NOT_BACK_REF,
375 121 : start_reg);
376 121 : EmitOrLink(on_not_equal);
377 121 : }
378 :
379 :
380 333 : void RegExpMacroAssemblerIrregexp::CheckNotBackReferenceIgnoreCase(
381 : int start_reg, bool read_backward, bool unicode, Label* on_not_equal) {
382 : DCHECK_LE(0, start_reg);
383 : DCHECK_GE(kMaxRegister, start_reg);
384 333 : Emit(read_backward ? (unicode ? BC_CHECK_NOT_BACK_REF_NO_CASE_UNICODE_BACKWARD
385 : : BC_CHECK_NOT_BACK_REF_NO_CASE_BACKWARD)
386 : : (unicode ? BC_CHECK_NOT_BACK_REF_NO_CASE_UNICODE
387 : : BC_CHECK_NOT_BACK_REF_NO_CASE),
388 333 : start_reg);
389 333 : EmitOrLink(on_not_equal);
390 333 : }
391 :
392 :
393 287 : void RegExpMacroAssemblerIrregexp::IfRegisterLT(int register_index,
394 : int comparand,
395 : Label* on_less_than) {
396 : DCHECK_LE(0, register_index);
397 : DCHECK_GE(kMaxRegister, register_index);
398 287 : Emit(BC_CHECK_REGISTER_LT, register_index);
399 287 : Emit32(comparand);
400 287 : EmitOrLink(on_less_than);
401 287 : }
402 :
403 :
404 486 : void RegExpMacroAssemblerIrregexp::IfRegisterGE(int register_index,
405 : int comparand,
406 : Label* on_greater_or_equal) {
407 : DCHECK_LE(0, register_index);
408 : DCHECK_GE(kMaxRegister, register_index);
409 486 : Emit(BC_CHECK_REGISTER_GE, register_index);
410 486 : Emit32(comparand);
411 486 : EmitOrLink(on_greater_or_equal);
412 486 : }
413 :
414 :
415 59 : void RegExpMacroAssemblerIrregexp::IfRegisterEqPos(int register_index,
416 : Label* on_eq) {
417 : DCHECK_LE(0, register_index);
418 : DCHECK_GE(kMaxRegister, register_index);
419 59 : Emit(BC_CHECK_REGISTER_EQ_POS, register_index);
420 59 : EmitOrLink(on_eq);
421 59 : }
422 :
423 :
424 3275 : Handle<HeapObject> RegExpMacroAssemblerIrregexp::GetCode(
425 : Handle<String> source) {
426 3275 : Bind(&backtrack_);
427 : Emit(BC_POP_BT, 0);
428 3275 : Handle<ByteArray> array = isolate_->factory()->NewByteArray(length());
429 : Copy(array->GetDataStartAddress());
430 3275 : return array;
431 : }
432 :
433 :
434 0 : int RegExpMacroAssemblerIrregexp::length() {
435 3275 : return pc_;
436 : }
437 :
438 0 : void RegExpMacroAssemblerIrregexp::Copy(byte* a) {
439 3275 : MemCopy(a, buffer_.start(), length());
440 0 : }
441 :
442 :
443 409 : void RegExpMacroAssemblerIrregexp::Expand() {
444 409 : bool old_buffer_was_our_own = own_buffer_;
445 409 : Vector<byte> old_buffer = buffer_;
446 818 : buffer_ = Vector<byte>::New(old_buffer.length() * 2);
447 409 : own_buffer_ = true;
448 409 : MemCopy(buffer_.start(), old_buffer.start(), old_buffer.length());
449 409 : if (old_buffer_was_our_own) {
450 : old_buffer.Dispose();
451 : }
452 409 : }
453 :
454 : } // namespace internal
455 122004 : } // namespace v8
|