Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 : * vim: set ts=8 sts=4 et sw=4 tw=99: */
3 :
4 : // Copyright 2012 the V8 project authors. All rights reserved.
5 : // Redistribution and use in source and binary forms, with or without
6 : // modification, are permitted provided that the following conditions are
7 : // met:
8 : //
9 : // * Redistributions of source code must retain the above copyright
10 : // notice, this list of conditions and the following disclaimer.
11 : // * Redistributions in binary form must reproduce the above
12 : // copyright notice, this list of conditions and the following
13 : // disclaimer in the documentation and/or other materials provided
14 : // with the distribution.
15 : // * Neither the name of Google Inc. nor the names of its
16 : // contributors may be used to endorse or promote products derived
17 : // from this software without specific prior written permission.
18 : //
19 : // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 : // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 : // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22 : // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23 : // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 : // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25 : // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26 : // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27 : // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 : // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29 : // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 :
31 : #include "irregexp/RegExpMacroAssembler.h"
32 :
33 : #include "irregexp/RegExpBytecode.h"
34 :
35 : using namespace js;
36 : using namespace js::irregexp;
37 :
38 : template <typename CharT>
39 : int
40 0 : irregexp::CaseInsensitiveCompareStrings(const CharT* substring1, const CharT* substring2,
41 : size_t byteLength)
42 : {
43 0 : MOZ_ASSERT(byteLength % sizeof(CharT) == 0);
44 0 : size_t length = byteLength / sizeof(CharT);
45 :
46 0 : for (size_t i = 0; i < length; i++) {
47 0 : char16_t c1 = substring1[i];
48 0 : char16_t c2 = substring2[i];
49 0 : if (c1 != c2) {
50 0 : c1 = unicode::ToLowerCase(c1);
51 0 : c2 = unicode::ToLowerCase(c2);
52 0 : if (c1 != c2)
53 0 : return 0;
54 : }
55 : }
56 :
57 0 : return 1;
58 : }
59 :
60 : template int
61 : irregexp::CaseInsensitiveCompareStrings(const Latin1Char* substring1, const Latin1Char* substring2,
62 : size_t byteLength);
63 :
64 : template int
65 : irregexp::CaseInsensitiveCompareStrings(const char16_t* substring1, const char16_t* substring2,
66 : size_t byteLength);
67 :
68 : template <typename CharT>
69 : int
70 0 : irregexp::CaseInsensitiveCompareUCStrings(const CharT* substring1, const CharT* substring2,
71 : size_t byteLength)
72 : {
73 0 : MOZ_ASSERT(byteLength % sizeof(CharT) == 0);
74 0 : size_t length = byteLength / sizeof(CharT);
75 :
76 0 : for (size_t i = 0; i < length; i++) {
77 0 : char16_t c1 = substring1[i];
78 0 : char16_t c2 = substring2[i];
79 0 : if (c1 != c2) {
80 0 : c1 = unicode::FoldCase(c1);
81 0 : c2 = unicode::FoldCase(c2);
82 0 : if (c1 != c2)
83 0 : return 0;
84 : }
85 : }
86 :
87 0 : return 1;
88 : }
89 :
90 : template int
91 : irregexp::CaseInsensitiveCompareUCStrings(const Latin1Char* substring1,
92 : const Latin1Char* substring2,
93 : size_t byteLength);
94 :
95 : template int
96 : irregexp::CaseInsensitiveCompareUCStrings(const char16_t* substring1,
97 : const char16_t* substring2,
98 : size_t byteLength);
99 :
100 0 : InterpretedRegExpMacroAssembler::InterpretedRegExpMacroAssembler(JSContext* cx, LifoAlloc* alloc,
101 0 : size_t numSavedRegisters)
102 : : RegExpMacroAssembler(cx, *alloc, numSavedRegisters),
103 : pc_(0),
104 : advance_current_start_(0),
105 : advance_current_offset_(0),
106 : advance_current_end_(kInvalidPC),
107 : buffer_(nullptr),
108 0 : length_(0)
109 : {
110 : // The first int32 word is the number of registers.
111 0 : Emit32(0);
112 0 : }
113 :
114 0 : InterpretedRegExpMacroAssembler::~InterpretedRegExpMacroAssembler()
115 : {
116 0 : js_free(buffer_);
117 0 : }
118 :
119 : RegExpCode
120 0 : InterpretedRegExpMacroAssembler::GenerateCode(JSContext* cx, bool match_only)
121 : {
122 0 : Bind(&backtrack_);
123 0 : Emit(BC_POP_BT, 0);
124 :
125 : // Update the number of registers.
126 0 : *(int32_t*)buffer_ = num_registers_;
127 :
128 0 : RegExpCode res;
129 0 : res.byteCode = buffer_;
130 0 : buffer_ = nullptr;
131 0 : return res;
132 : }
133 :
134 : void
135 0 : InterpretedRegExpMacroAssembler::AdvanceCurrentPosition(int by)
136 : {
137 0 : MOZ_ASSERT(by >= kMinCPOffset);
138 0 : MOZ_ASSERT(by <= kMaxCPOffset);
139 0 : advance_current_start_ = pc_;
140 0 : advance_current_offset_ = by;
141 0 : Emit(BC_ADVANCE_CP, by);
142 0 : advance_current_end_ = pc_;
143 0 : }
144 :
145 : void
146 0 : InterpretedRegExpMacroAssembler::AdvanceRegister(int reg, int by)
147 : {
148 0 : checkRegister(reg);
149 0 : Emit(BC_ADVANCE_REGISTER, reg);
150 0 : Emit32(by);
151 0 : }
152 :
153 : void
154 0 : InterpretedRegExpMacroAssembler::Backtrack()
155 : {
156 0 : Emit(BC_POP_BT, 0);
157 0 : }
158 :
159 : void
160 0 : InterpretedRegExpMacroAssembler::Bind(jit::Label* label)
161 : {
162 0 : advance_current_end_ = kInvalidPC;
163 0 : MOZ_ASSERT(!label->bound());
164 0 : if (label->used()) {
165 0 : int pos = label->offset();
166 0 : while (pos != jit::Label::INVALID_OFFSET) {
167 0 : int fixup = pos;
168 0 : pos = *reinterpret_cast<int32_t*>(buffer_ + fixup);
169 0 : *reinterpret_cast<uint32_t*>(buffer_ + fixup) = pc_;
170 : }
171 : }
172 0 : label->bind(pc_);
173 0 : }
174 :
175 : void
176 0 : InterpretedRegExpMacroAssembler::CheckAtStart(jit::Label* on_at_start)
177 : {
178 0 : Emit(BC_CHECK_AT_START, 0);
179 0 : EmitOrLink(on_at_start);
180 0 : }
181 :
182 : void
183 0 : InterpretedRegExpMacroAssembler::CheckCharacter(unsigned c, jit::Label* on_equal)
184 : {
185 0 : if (c > MAX_FIRST_ARG) {
186 0 : Emit(BC_CHECK_4_CHARS, 0);
187 0 : Emit32(c);
188 : } else {
189 0 : Emit(BC_CHECK_CHAR, c);
190 : }
191 0 : EmitOrLink(on_equal);
192 0 : }
193 :
194 : void
195 0 : InterpretedRegExpMacroAssembler::CheckCharacterAfterAnd(unsigned c, unsigned and_with, jit::Label* on_equal)
196 : {
197 0 : if (c > MAX_FIRST_ARG) {
198 0 : Emit(BC_AND_CHECK_4_CHARS, 0);
199 0 : Emit32(c);
200 : } else {
201 0 : Emit(BC_AND_CHECK_CHAR, c);
202 : }
203 0 : Emit32(and_with);
204 0 : EmitOrLink(on_equal);
205 0 : }
206 :
207 : void
208 0 : InterpretedRegExpMacroAssembler::CheckCharacterGT(char16_t limit, jit::Label* on_greater)
209 : {
210 0 : Emit(BC_CHECK_GT, limit);
211 0 : EmitOrLink(on_greater);
212 0 : }
213 :
214 : void
215 0 : InterpretedRegExpMacroAssembler::CheckCharacterLT(char16_t limit, jit::Label* on_less)
216 : {
217 0 : Emit(BC_CHECK_LT, limit);
218 0 : EmitOrLink(on_less);
219 0 : }
220 :
221 : void
222 0 : InterpretedRegExpMacroAssembler::CheckGreedyLoop(jit::Label* on_tos_equals_current_position)
223 : {
224 0 : Emit(BC_CHECK_GREEDY, 0);
225 0 : EmitOrLink(on_tos_equals_current_position);
226 0 : }
227 :
228 : void
229 0 : InterpretedRegExpMacroAssembler::CheckNotAtStart(jit::Label* on_not_at_start)
230 : {
231 0 : Emit(BC_CHECK_NOT_AT_START, 0);
232 0 : EmitOrLink(on_not_at_start);
233 0 : }
234 :
235 : void
236 0 : InterpretedRegExpMacroAssembler::CheckNotBackReference(int start_reg, jit::Label* on_no_match)
237 : {
238 0 : MOZ_ASSERT(start_reg >= 0);
239 0 : MOZ_ASSERT(start_reg <= kMaxRegister);
240 0 : Emit(BC_CHECK_NOT_BACK_REF, start_reg);
241 0 : EmitOrLink(on_no_match);
242 0 : }
243 :
244 : void
245 0 : InterpretedRegExpMacroAssembler::CheckNotBackReferenceIgnoreCase(int start_reg,
246 : jit::Label* on_no_match,
247 : bool unicode)
248 : {
249 0 : MOZ_ASSERT(start_reg >= 0);
250 0 : MOZ_ASSERT(start_reg <= kMaxRegister);
251 0 : if (unicode)
252 0 : Emit(BC_CHECK_NOT_BACK_REF_NO_CASE_UNICODE, start_reg);
253 : else
254 0 : Emit(BC_CHECK_NOT_BACK_REF_NO_CASE, start_reg);
255 0 : EmitOrLink(on_no_match);
256 0 : }
257 :
258 : void
259 0 : InterpretedRegExpMacroAssembler::CheckNotCharacter(unsigned c, jit::Label* on_not_equal)
260 : {
261 0 : if (c > MAX_FIRST_ARG) {
262 0 : Emit(BC_CHECK_NOT_4_CHARS, 0);
263 0 : Emit32(c);
264 : } else {
265 0 : Emit(BC_CHECK_NOT_CHAR, c);
266 : }
267 0 : EmitOrLink(on_not_equal);
268 0 : }
269 :
270 : void
271 0 : InterpretedRegExpMacroAssembler::CheckNotCharacterAfterAnd(unsigned c, unsigned and_with,
272 : jit::Label* on_not_equal)
273 : {
274 0 : if (c > MAX_FIRST_ARG) {
275 0 : Emit(BC_AND_CHECK_NOT_4_CHARS, 0);
276 0 : Emit32(c);
277 : } else {
278 0 : Emit(BC_AND_CHECK_NOT_CHAR, c);
279 : }
280 0 : Emit32(and_with);
281 0 : EmitOrLink(on_not_equal);
282 0 : }
283 :
284 : void
285 0 : InterpretedRegExpMacroAssembler::CheckNotCharacterAfterMinusAnd(char16_t c, char16_t minus, char16_t and_with,
286 : jit::Label* on_not_equal)
287 : {
288 0 : Emit(BC_MINUS_AND_CHECK_NOT_CHAR, c);
289 0 : Emit16(minus);
290 0 : Emit16(and_with);
291 0 : EmitOrLink(on_not_equal);
292 0 : }
293 :
294 : void
295 0 : InterpretedRegExpMacroAssembler::CheckCharacterInRange(char16_t from, char16_t to,
296 : jit::Label* on_in_range)
297 : {
298 0 : Emit(BC_CHECK_CHAR_IN_RANGE, 0);
299 0 : Emit16(from);
300 0 : Emit16(to);
301 0 : EmitOrLink(on_in_range);
302 0 : }
303 :
304 : void
305 0 : InterpretedRegExpMacroAssembler::CheckCharacterNotInRange(char16_t from, char16_t to,
306 : jit::Label* on_not_in_range)
307 : {
308 0 : Emit(BC_CHECK_CHAR_NOT_IN_RANGE, 0);
309 0 : Emit16(from);
310 0 : Emit16(to);
311 0 : EmitOrLink(on_not_in_range);
312 0 : }
313 :
314 : void
315 0 : InterpretedRegExpMacroAssembler::CheckBitInTable(RegExpShared::JitCodeTable table,
316 : jit::Label* on_bit_set)
317 : {
318 : static const int kBitsPerByte = 8;
319 :
320 0 : Emit(BC_CHECK_BIT_IN_TABLE, 0);
321 0 : EmitOrLink(on_bit_set);
322 0 : for (int i = 0; i < kTableSize; i += kBitsPerByte) {
323 0 : int byte = 0;
324 0 : for (int j = 0; j < kBitsPerByte; j++) {
325 0 : if (table[i + j] != 0)
326 0 : byte |= 1 << j;
327 : }
328 0 : Emit8(byte);
329 : }
330 0 : }
331 :
332 : void
333 0 : InterpretedRegExpMacroAssembler::JumpOrBacktrack(jit::Label* to)
334 : {
335 0 : if (advance_current_end_ == pc_) {
336 : // Combine advance current and goto.
337 0 : pc_ = advance_current_start_;
338 0 : Emit(BC_ADVANCE_CP_AND_GOTO, advance_current_offset_);
339 0 : EmitOrLink(to);
340 0 : advance_current_end_ = kInvalidPC;
341 : } else {
342 : // Regular goto.
343 0 : Emit(BC_GOTO, 0);
344 0 : EmitOrLink(to);
345 : }
346 0 : }
347 :
348 : void
349 0 : InterpretedRegExpMacroAssembler::Fail()
350 : {
351 0 : Emit(BC_FAIL, 0);
352 0 : }
353 :
354 : void
355 0 : InterpretedRegExpMacroAssembler::IfRegisterGE(int reg, int comparand, jit::Label* if_ge)
356 : {
357 0 : checkRegister(reg);
358 0 : Emit(BC_CHECK_REGISTER_GE, reg);
359 0 : Emit32(comparand);
360 0 : EmitOrLink(if_ge);
361 0 : }
362 :
363 : void
364 0 : InterpretedRegExpMacroAssembler::IfRegisterLT(int reg, int comparand, jit::Label* if_lt)
365 : {
366 0 : checkRegister(reg);
367 0 : Emit(BC_CHECK_REGISTER_LT, reg);
368 0 : Emit32(comparand);
369 0 : EmitOrLink(if_lt);
370 0 : }
371 :
372 : void
373 0 : InterpretedRegExpMacroAssembler::IfRegisterEqPos(int reg, jit::Label* if_eq)
374 : {
375 0 : checkRegister(reg);
376 0 : Emit(BC_CHECK_REGISTER_EQ_POS, reg);
377 0 : EmitOrLink(if_eq);
378 0 : }
379 :
380 : void
381 0 : InterpretedRegExpMacroAssembler::LoadCurrentCharacter(int cp_offset, jit::Label* on_end_of_input,
382 : bool check_bounds, int characters)
383 : {
384 0 : MOZ_ASSERT(cp_offset >= kMinCPOffset);
385 0 : MOZ_ASSERT(cp_offset <= kMaxCPOffset);
386 : int bytecode;
387 0 : if (check_bounds) {
388 0 : if (characters == 4) {
389 0 : bytecode = BC_LOAD_4_CURRENT_CHARS;
390 0 : } else if (characters == 2) {
391 0 : bytecode = BC_LOAD_2_CURRENT_CHARS;
392 : } else {
393 0 : MOZ_ASSERT(characters == 1);
394 0 : bytecode = BC_LOAD_CURRENT_CHAR;
395 : }
396 : } else {
397 0 : if (characters == 4) {
398 0 : bytecode = BC_LOAD_4_CURRENT_CHARS_UNCHECKED;
399 0 : } else if (characters == 2) {
400 0 : bytecode = BC_LOAD_2_CURRENT_CHARS_UNCHECKED;
401 : } else {
402 0 : MOZ_ASSERT(characters == 1);
403 0 : bytecode = BC_LOAD_CURRENT_CHAR_UNCHECKED;
404 : }
405 : }
406 0 : Emit(bytecode, cp_offset);
407 0 : if (check_bounds)
408 0 : EmitOrLink(on_end_of_input);
409 0 : }
410 :
411 : void
412 0 : InterpretedRegExpMacroAssembler::PopCurrentPosition()
413 : {
414 0 : Emit(BC_POP_CP, 0);
415 0 : }
416 :
417 : void
418 0 : InterpretedRegExpMacroAssembler::PopRegister(int reg)
419 : {
420 0 : checkRegister(reg);
421 0 : Emit(BC_POP_REGISTER, reg);
422 0 : }
423 :
424 : void
425 0 : InterpretedRegExpMacroAssembler::PushCurrentPosition()
426 : {
427 0 : Emit(BC_PUSH_CP, 0);
428 0 : }
429 :
430 : void
431 0 : InterpretedRegExpMacroAssembler::PushRegister(int reg, StackCheckFlag check_stack_limit)
432 : {
433 0 : checkRegister(reg);
434 0 : Emit(BC_PUSH_REGISTER, reg);
435 0 : }
436 :
437 : void
438 0 : InterpretedRegExpMacroAssembler::ReadCurrentPositionFromRegister(int reg)
439 : {
440 0 : checkRegister(reg);
441 0 : Emit(BC_SET_CP_TO_REGISTER, reg);
442 0 : }
443 :
444 : void
445 0 : InterpretedRegExpMacroAssembler::ReadBacktrackStackPointerFromRegister(int reg)
446 : {
447 0 : checkRegister(reg);
448 0 : Emit(BC_SET_SP_TO_REGISTER, reg);
449 0 : }
450 :
451 : void
452 0 : InterpretedRegExpMacroAssembler::SetCurrentPositionFromEnd(int by)
453 : {
454 0 : MOZ_ASSERT(by >= 0 && by < (1 << 24));
455 0 : Emit(BC_SET_CURRENT_POSITION_FROM_END, by);
456 0 : }
457 :
458 : void
459 0 : InterpretedRegExpMacroAssembler::SetRegister(int reg, int to)
460 : {
461 0 : checkRegister(reg);
462 0 : Emit(BC_SET_REGISTER, reg);
463 0 : Emit32(to);
464 0 : }
465 :
466 : bool
467 0 : InterpretedRegExpMacroAssembler::Succeed()
468 : {
469 0 : Emit(BC_SUCCEED, 0);
470 :
471 : // Restart matching for global regexp not supported.
472 0 : return false;
473 : }
474 :
475 : void
476 0 : InterpretedRegExpMacroAssembler::WriteCurrentPositionToRegister(int reg, int cp_offset)
477 : {
478 0 : checkRegister(reg);
479 0 : Emit(BC_SET_REGISTER_TO_CP, reg);
480 0 : Emit32(cp_offset); // Current position offset.
481 0 : }
482 :
483 : void
484 0 : InterpretedRegExpMacroAssembler::ClearRegisters(int reg_from, int reg_to)
485 : {
486 0 : MOZ_ASSERT(reg_from <= reg_to);
487 0 : for (int reg = reg_from; reg <= reg_to; reg++)
488 0 : SetRegister(reg, -1);
489 0 : }
490 :
491 : void
492 0 : InterpretedRegExpMacroAssembler::WriteBacktrackStackPointerToRegister(int reg)
493 : {
494 0 : checkRegister(reg);
495 0 : Emit(BC_SET_REGISTER_TO_SP, reg);
496 0 : }
497 :
498 : void
499 0 : InterpretedRegExpMacroAssembler::PushBacktrack(jit::Label* label)
500 : {
501 0 : Emit(BC_PUSH_BT, 0);
502 0 : EmitOrLink(label);
503 0 : }
504 :
505 : void
506 0 : InterpretedRegExpMacroAssembler::BindBacktrack(jit::Label* label)
507 : {
508 0 : Bind(label);
509 0 : }
510 :
511 : void
512 0 : InterpretedRegExpMacroAssembler::EmitOrLink(jit::Label* label)
513 : {
514 0 : if (label == nullptr)
515 0 : label = &backtrack_;
516 0 : if (label->bound()) {
517 0 : Emit32(label->offset());
518 : } else {
519 0 : int pos = label->use(pc_);
520 0 : Emit32(pos);
521 : }
522 0 : }
523 :
524 : void
525 0 : InterpretedRegExpMacroAssembler::Emit(uint32_t byte, uint32_t twenty_four_bits)
526 : {
527 0 : uint32_t word = ((twenty_four_bits << BYTECODE_SHIFT) | byte);
528 0 : Emit32(word);
529 0 : }
530 :
531 : void
532 0 : InterpretedRegExpMacroAssembler::Emit32(uint32_t word)
533 : {
534 0 : MOZ_ASSERT(pc_ <= length_);
535 0 : if (pc_ + 3 >= length_)
536 0 : Expand();
537 0 : *reinterpret_cast<uint32_t*>(buffer_ + pc_) = word;
538 0 : pc_ += 4;
539 0 : }
540 :
541 : void
542 0 : InterpretedRegExpMacroAssembler::Emit16(uint32_t word)
543 : {
544 0 : MOZ_ASSERT(pc_ <= length_);
545 0 : if (pc_ + 1 >= length_)
546 0 : Expand();
547 0 : *reinterpret_cast<uint16_t*>(buffer_ + pc_) = word;
548 0 : pc_ += 2;
549 0 : }
550 :
551 : void
552 0 : InterpretedRegExpMacroAssembler::Emit8(uint32_t word)
553 : {
554 0 : MOZ_ASSERT(pc_ <= length_);
555 0 : if (pc_ == length_)
556 0 : Expand();
557 0 : *reinterpret_cast<unsigned char*>(buffer_ + pc_) = word;
558 0 : pc_ += 1;
559 0 : }
560 :
561 : void
562 0 : InterpretedRegExpMacroAssembler::Expand()
563 : {
564 0 : AutoEnterOOMUnsafeRegion oomUnsafe;
565 :
566 0 : int newLength = Max(100, length_ * 2);
567 0 : if (newLength < length_ + 4)
568 0 : oomUnsafe.crash("InterpretedRegExpMacroAssembler::Expand");
569 :
570 0 : buffer_ = (uint8_t*) js_realloc(buffer_, newLength);
571 0 : if (!buffer_)
572 0 : oomUnsafe.crash("InterpretedRegExpMacroAssembler::Expand");
573 0 : length_ = newLength;
574 0 : }
|
