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