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
CaseInsensitiveCompareStrings(const CharT * substring1,const CharT * substring2,size_t byteLength)40 irregexp::CaseInsensitiveCompareStrings(const CharT* substring1, const CharT* substring2,
41 size_t byteLength)
42 {
43 AutoUnsafeCallWithABI unsafe;
44
45 MOZ_ASSERT(byteLength % sizeof(CharT) == 0);
46 size_t length = byteLength / sizeof(CharT);
47
48 for (size_t i = 0; i < length; i++) {
49 char16_t c1 = substring1[i];
50 char16_t c2 = substring2[i];
51 if (c1 != c2) {
52 c1 = unicode::ToLowerCase(c1);
53 c2 = unicode::ToLowerCase(c2);
54 if (c1 != c2)
55 return 0;
56 }
57 }
58
59 return 1;
60 }
61
62 template int
63 irregexp::CaseInsensitiveCompareStrings(const Latin1Char* substring1, const Latin1Char* substring2,
64 size_t byteLength);
65
66 template int
67 irregexp::CaseInsensitiveCompareStrings(const char16_t* substring1, const char16_t* substring2,
68 size_t byteLength);
69
70 template <typename CharT>
71 int
CaseInsensitiveCompareUCStrings(const CharT * substring1,const CharT * substring2,size_t byteLength)72 irregexp::CaseInsensitiveCompareUCStrings(const CharT* substring1, const CharT* substring2,
73 size_t byteLength)
74 {
75 AutoUnsafeCallWithABI unsafe;
76
77 MOZ_ASSERT(byteLength % sizeof(CharT) == 0);
78 size_t length = byteLength / sizeof(CharT);
79
80 for (size_t i = 0; i < length; i++) {
81 char16_t c1 = substring1[i];
82 char16_t c2 = substring2[i];
83 if (c1 != c2) {
84 c1 = unicode::FoldCase(c1);
85 c2 = unicode::FoldCase(c2);
86 if (c1 != c2)
87 return 0;
88 }
89 }
90
91 return 1;
92 }
93
94 template int
95 irregexp::CaseInsensitiveCompareUCStrings(const Latin1Char* substring1,
96 const Latin1Char* substring2,
97 size_t byteLength);
98
99 template int
100 irregexp::CaseInsensitiveCompareUCStrings(const char16_t* substring1,
101 const char16_t* substring2,
102 size_t byteLength);
103
InterpretedRegExpMacroAssembler(JSContext * cx,LifoAlloc * alloc,size_t numSavedRegisters)104 InterpretedRegExpMacroAssembler::InterpretedRegExpMacroAssembler(JSContext* cx, LifoAlloc* alloc,
105 size_t numSavedRegisters)
106 : RegExpMacroAssembler(cx, *alloc, numSavedRegisters),
107 pc_(0),
108 advance_current_start_(0),
109 advance_current_offset_(0),
110 advance_current_end_(kInvalidPC),
111 buffer_(nullptr),
112 length_(0)
113 {
114 // The first int32 word is the number of registers.
115 Emit32(0);
116 }
117
~InterpretedRegExpMacroAssembler()118 InterpretedRegExpMacroAssembler::~InterpretedRegExpMacroAssembler()
119 {
120 js_free(buffer_);
121 }
122
123 RegExpCode
GenerateCode(JSContext * cx,bool match_only)124 InterpretedRegExpMacroAssembler::GenerateCode(JSContext* cx, bool match_only)
125 {
126 Bind(&backtrack_);
127 Emit(BC_POP_BT, 0);
128
129 // Update the number of registers.
130 *(int32_t*)buffer_ = num_registers_;
131
132 RegExpCode res;
133 res.byteCode = buffer_;
134 buffer_ = nullptr;
135 return res;
136 }
137
138 void
AdvanceCurrentPosition(int by)139 InterpretedRegExpMacroAssembler::AdvanceCurrentPosition(int by)
140 {
141 MOZ_ASSERT(by >= kMinCPOffset);
142 MOZ_ASSERT(by <= kMaxCPOffset);
143 advance_current_start_ = pc_;
144 advance_current_offset_ = by;
145 Emit(BC_ADVANCE_CP, by);
146 advance_current_end_ = pc_;
147 }
148
149 void
AdvanceRegister(int reg,int by)150 InterpretedRegExpMacroAssembler::AdvanceRegister(int reg, int by)
151 {
152 checkRegister(reg);
153 Emit(BC_ADVANCE_REGISTER, reg);
154 Emit32(by);
155 }
156
157 void
Backtrack()158 InterpretedRegExpMacroAssembler::Backtrack()
159 {
160 Emit(BC_POP_BT, 0);
161 }
162
163 static const int32_t INVALID_OFFSET = -1;
164
165 void
Bind(jit::Label * label)166 InterpretedRegExpMacroAssembler::Bind(jit::Label* label)
167 {
168 advance_current_end_ = kInvalidPC;
169 MOZ_ASSERT(!label->bound());
170 if (label->used()) {
171 int pos = label->offset();
172 MOZ_ASSERT(pos >= 0);
173 do {
174 int fixup = pos;
175 pos = *reinterpret_cast<int32_t*>(buffer_ + fixup);
176 *reinterpret_cast<uint32_t*>(buffer_ + fixup) = pc_;
177 } while (pos != INVALID_OFFSET);
178 }
179 label->bind(pc_);
180 }
181
182 void
CheckAtStart(jit::Label * on_at_start)183 InterpretedRegExpMacroAssembler::CheckAtStart(jit::Label* on_at_start)
184 {
185 Emit(BC_CHECK_AT_START, 0);
186 EmitOrLink(on_at_start);
187 }
188
189 void
CheckCharacter(unsigned c,jit::Label * on_equal)190 InterpretedRegExpMacroAssembler::CheckCharacter(unsigned c, jit::Label* on_equal)
191 {
192 if (c > MAX_FIRST_ARG) {
193 Emit(BC_CHECK_4_CHARS, 0);
194 Emit32(c);
195 } else {
196 Emit(BC_CHECK_CHAR, c);
197 }
198 EmitOrLink(on_equal);
199 }
200
201 void
CheckCharacterAfterAnd(unsigned c,unsigned and_with,jit::Label * on_equal)202 InterpretedRegExpMacroAssembler::CheckCharacterAfterAnd(unsigned c, unsigned and_with, jit::Label* on_equal)
203 {
204 if (c > MAX_FIRST_ARG) {
205 Emit(BC_AND_CHECK_4_CHARS, 0);
206 Emit32(c);
207 } else {
208 Emit(BC_AND_CHECK_CHAR, c);
209 }
210 Emit32(and_with);
211 EmitOrLink(on_equal);
212 }
213
214 void
CheckCharacterGT(char16_t limit,jit::Label * on_greater)215 InterpretedRegExpMacroAssembler::CheckCharacterGT(char16_t limit, jit::Label* on_greater)
216 {
217 Emit(BC_CHECK_GT, limit);
218 EmitOrLink(on_greater);
219 }
220
221 void
CheckCharacterLT(char16_t limit,jit::Label * on_less)222 InterpretedRegExpMacroAssembler::CheckCharacterLT(char16_t limit, jit::Label* on_less)
223 {
224 Emit(BC_CHECK_LT, limit);
225 EmitOrLink(on_less);
226 }
227
228 void
CheckGreedyLoop(jit::Label * on_tos_equals_current_position)229 InterpretedRegExpMacroAssembler::CheckGreedyLoop(jit::Label* on_tos_equals_current_position)
230 {
231 Emit(BC_CHECK_GREEDY, 0);
232 EmitOrLink(on_tos_equals_current_position);
233 }
234
235 void
CheckNotAtStart(jit::Label * on_not_at_start)236 InterpretedRegExpMacroAssembler::CheckNotAtStart(jit::Label* on_not_at_start)
237 {
238 Emit(BC_CHECK_NOT_AT_START, 0);
239 EmitOrLink(on_not_at_start);
240 }
241
242 void
CheckNotBackReference(int start_reg,jit::Label * on_no_match)243 InterpretedRegExpMacroAssembler::CheckNotBackReference(int start_reg, jit::Label* on_no_match)
244 {
245 MOZ_ASSERT(start_reg >= 0);
246 MOZ_ASSERT(start_reg <= kMaxRegister);
247 Emit(BC_CHECK_NOT_BACK_REF, start_reg);
248 EmitOrLink(on_no_match);
249 }
250
251 void
CheckNotBackReferenceIgnoreCase(int start_reg,jit::Label * on_no_match,bool unicode)252 InterpretedRegExpMacroAssembler::CheckNotBackReferenceIgnoreCase(int start_reg,
253 jit::Label* on_no_match,
254 bool unicode)
255 {
256 MOZ_ASSERT(start_reg >= 0);
257 MOZ_ASSERT(start_reg <= kMaxRegister);
258 if (unicode)
259 Emit(BC_CHECK_NOT_BACK_REF_NO_CASE_UNICODE, start_reg);
260 else
261 Emit(BC_CHECK_NOT_BACK_REF_NO_CASE, start_reg);
262 EmitOrLink(on_no_match);
263 }
264
265 void
CheckNotCharacter(unsigned c,jit::Label * on_not_equal)266 InterpretedRegExpMacroAssembler::CheckNotCharacter(unsigned c, jit::Label* on_not_equal)
267 {
268 if (c > MAX_FIRST_ARG) {
269 Emit(BC_CHECK_NOT_4_CHARS, 0);
270 Emit32(c);
271 } else {
272 Emit(BC_CHECK_NOT_CHAR, c);
273 }
274 EmitOrLink(on_not_equal);
275 }
276
277 void
CheckNotCharacterAfterAnd(unsigned c,unsigned and_with,jit::Label * on_not_equal)278 InterpretedRegExpMacroAssembler::CheckNotCharacterAfterAnd(unsigned c, unsigned and_with,
279 jit::Label* on_not_equal)
280 {
281 if (c > MAX_FIRST_ARG) {
282 Emit(BC_AND_CHECK_NOT_4_CHARS, 0);
283 Emit32(c);
284 } else {
285 Emit(BC_AND_CHECK_NOT_CHAR, c);
286 }
287 Emit32(and_with);
288 EmitOrLink(on_not_equal);
289 }
290
291 void
CheckNotCharacterAfterMinusAnd(char16_t c,char16_t minus,char16_t and_with,jit::Label * on_not_equal)292 InterpretedRegExpMacroAssembler::CheckNotCharacterAfterMinusAnd(char16_t c, char16_t minus, char16_t and_with,
293 jit::Label* on_not_equal)
294 {
295 Emit(BC_MINUS_AND_CHECK_NOT_CHAR, c);
296 Emit16(minus);
297 Emit16(and_with);
298 EmitOrLink(on_not_equal);
299 }
300
301 void
CheckCharacterInRange(char16_t from,char16_t to,jit::Label * on_in_range)302 InterpretedRegExpMacroAssembler::CheckCharacterInRange(char16_t from, char16_t to,
303 jit::Label* on_in_range)
304 {
305 Emit(BC_CHECK_CHAR_IN_RANGE, 0);
306 Emit16(from);
307 Emit16(to);
308 EmitOrLink(on_in_range);
309 }
310
311 void
CheckCharacterNotInRange(char16_t from,char16_t to,jit::Label * on_not_in_range)312 InterpretedRegExpMacroAssembler::CheckCharacterNotInRange(char16_t from, char16_t to,
313 jit::Label* on_not_in_range)
314 {
315 Emit(BC_CHECK_CHAR_NOT_IN_RANGE, 0);
316 Emit16(from);
317 Emit16(to);
318 EmitOrLink(on_not_in_range);
319 }
320
321 void
CheckBitInTable(RegExpShared::JitCodeTable table,jit::Label * on_bit_set)322 InterpretedRegExpMacroAssembler::CheckBitInTable(RegExpShared::JitCodeTable table,
323 jit::Label* on_bit_set)
324 {
325 static const int kBitsPerByte = 8;
326
327 Emit(BC_CHECK_BIT_IN_TABLE, 0);
328 EmitOrLink(on_bit_set);
329 for (int i = 0; i < kTableSize; i += kBitsPerByte) {
330 int byte = 0;
331 for (int j = 0; j < kBitsPerByte; j++) {
332 if (table[i + j] != 0)
333 byte |= 1 << j;
334 }
335 Emit8(byte);
336 }
337 }
338
339 void
JumpOrBacktrack(jit::Label * to)340 InterpretedRegExpMacroAssembler::JumpOrBacktrack(jit::Label* to)
341 {
342 if (advance_current_end_ == pc_) {
343 // Combine advance current and goto.
344 pc_ = advance_current_start_;
345 Emit(BC_ADVANCE_CP_AND_GOTO, advance_current_offset_);
346 EmitOrLink(to);
347 advance_current_end_ = kInvalidPC;
348 } else {
349 // Regular goto.
350 Emit(BC_GOTO, 0);
351 EmitOrLink(to);
352 }
353 }
354
355 void
Fail()356 InterpretedRegExpMacroAssembler::Fail()
357 {
358 Emit(BC_FAIL, 0);
359 }
360
361 void
IfRegisterGE(int reg,int comparand,jit::Label * if_ge)362 InterpretedRegExpMacroAssembler::IfRegisterGE(int reg, int comparand, jit::Label* if_ge)
363 {
364 checkRegister(reg);
365 Emit(BC_CHECK_REGISTER_GE, reg);
366 Emit32(comparand);
367 EmitOrLink(if_ge);
368 }
369
370 void
IfRegisterLT(int reg,int comparand,jit::Label * if_lt)371 InterpretedRegExpMacroAssembler::IfRegisterLT(int reg, int comparand, jit::Label* if_lt)
372 {
373 checkRegister(reg);
374 Emit(BC_CHECK_REGISTER_LT, reg);
375 Emit32(comparand);
376 EmitOrLink(if_lt);
377 }
378
379 void
IfRegisterEqPos(int reg,jit::Label * if_eq)380 InterpretedRegExpMacroAssembler::IfRegisterEqPos(int reg, jit::Label* if_eq)
381 {
382 checkRegister(reg);
383 Emit(BC_CHECK_REGISTER_EQ_POS, reg);
384 EmitOrLink(if_eq);
385 }
386
387 void
LoadCurrentCharacter(int cp_offset,jit::Label * on_end_of_input,bool check_bounds,int characters)388 InterpretedRegExpMacroAssembler::LoadCurrentCharacter(int cp_offset, jit::Label* on_end_of_input,
389 bool check_bounds, int characters)
390 {
391 MOZ_ASSERT(cp_offset >= kMinCPOffset);
392 MOZ_ASSERT(cp_offset <= kMaxCPOffset);
393 int bytecode;
394 if (check_bounds) {
395 if (characters == 4) {
396 bytecode = BC_LOAD_4_CURRENT_CHARS;
397 } else if (characters == 2) {
398 bytecode = BC_LOAD_2_CURRENT_CHARS;
399 } else {
400 MOZ_ASSERT(characters == 1);
401 bytecode = BC_LOAD_CURRENT_CHAR;
402 }
403 } else {
404 if (characters == 4) {
405 bytecode = BC_LOAD_4_CURRENT_CHARS_UNCHECKED;
406 } else if (characters == 2) {
407 bytecode = BC_LOAD_2_CURRENT_CHARS_UNCHECKED;
408 } else {
409 MOZ_ASSERT(characters == 1);
410 bytecode = BC_LOAD_CURRENT_CHAR_UNCHECKED;
411 }
412 }
413 Emit(bytecode, cp_offset);
414 if (check_bounds)
415 EmitOrLink(on_end_of_input);
416 }
417
418 void
PopCurrentPosition()419 InterpretedRegExpMacroAssembler::PopCurrentPosition()
420 {
421 Emit(BC_POP_CP, 0);
422 }
423
424 void
PopRegister(int reg)425 InterpretedRegExpMacroAssembler::PopRegister(int reg)
426 {
427 checkRegister(reg);
428 Emit(BC_POP_REGISTER, reg);
429 }
430
431 void
PushCurrentPosition()432 InterpretedRegExpMacroAssembler::PushCurrentPosition()
433 {
434 Emit(BC_PUSH_CP, 0);
435 }
436
437 void
PushRegister(int reg,StackCheckFlag check_stack_limit)438 InterpretedRegExpMacroAssembler::PushRegister(int reg, StackCheckFlag check_stack_limit)
439 {
440 checkRegister(reg);
441 Emit(BC_PUSH_REGISTER, reg);
442 }
443
444 void
ReadCurrentPositionFromRegister(int reg)445 InterpretedRegExpMacroAssembler::ReadCurrentPositionFromRegister(int reg)
446 {
447 checkRegister(reg);
448 Emit(BC_SET_CP_TO_REGISTER, reg);
449 }
450
451 void
ReadBacktrackStackPointerFromRegister(int reg)452 InterpretedRegExpMacroAssembler::ReadBacktrackStackPointerFromRegister(int reg)
453 {
454 checkRegister(reg);
455 Emit(BC_SET_SP_TO_REGISTER, reg);
456 }
457
458 void
SetCurrentPositionFromEnd(int by)459 InterpretedRegExpMacroAssembler::SetCurrentPositionFromEnd(int by)
460 {
461 MOZ_ASSERT(by >= 0 && by < (1 << 24));
462 Emit(BC_SET_CURRENT_POSITION_FROM_END, by);
463 }
464
465 void
SetRegister(int reg,int to)466 InterpretedRegExpMacroAssembler::SetRegister(int reg, int to)
467 {
468 checkRegister(reg);
469 Emit(BC_SET_REGISTER, reg);
470 Emit32(to);
471 }
472
473 bool
Succeed()474 InterpretedRegExpMacroAssembler::Succeed()
475 {
476 Emit(BC_SUCCEED, 0);
477
478 // Restart matching for global regexp not supported.
479 return false;
480 }
481
482 void
WriteCurrentPositionToRegister(int reg,int cp_offset)483 InterpretedRegExpMacroAssembler::WriteCurrentPositionToRegister(int reg, int cp_offset)
484 {
485 checkRegister(reg);
486 Emit(BC_SET_REGISTER_TO_CP, reg);
487 Emit32(cp_offset); // Current position offset.
488 }
489
490 void
ClearRegisters(int reg_from,int reg_to)491 InterpretedRegExpMacroAssembler::ClearRegisters(int reg_from, int reg_to)
492 {
493 MOZ_ASSERT(reg_from <= reg_to);
494 for (int reg = reg_from; reg <= reg_to; reg++)
495 SetRegister(reg, -1);
496 }
497
498 void
WriteBacktrackStackPointerToRegister(int reg)499 InterpretedRegExpMacroAssembler::WriteBacktrackStackPointerToRegister(int reg)
500 {
501 checkRegister(reg);
502 Emit(BC_SET_REGISTER_TO_SP, reg);
503 }
504
505 void
PushBacktrack(jit::Label * label)506 InterpretedRegExpMacroAssembler::PushBacktrack(jit::Label* label)
507 {
508 Emit(BC_PUSH_BT, 0);
509 EmitOrLink(label);
510 }
511
512 void
BindBacktrack(jit::Label * label)513 InterpretedRegExpMacroAssembler::BindBacktrack(jit::Label* label)
514 {
515 Bind(label);
516 }
517
518 void
EmitOrLink(jit::Label * label)519 InterpretedRegExpMacroAssembler::EmitOrLink(jit::Label* label)
520 {
521 if (label == nullptr)
522 label = &backtrack_;
523 if (label->bound()) {
524 Emit32(label->offset());
525 } else {
526 int pos = label->used() ? label->offset() : INVALID_OFFSET;
527 label->use(pc_);
528 Emit32(pos);
529 }
530 }
531
532 void
Emit(uint32_t byte,uint32_t twenty_four_bits)533 InterpretedRegExpMacroAssembler::Emit(uint32_t byte, uint32_t twenty_four_bits)
534 {
535 uint32_t word = ((twenty_four_bits << BYTECODE_SHIFT) | byte);
536 Emit32(word);
537 }
538
539 void
Emit32(uint32_t word)540 InterpretedRegExpMacroAssembler::Emit32(uint32_t word)
541 {
542 MOZ_ASSERT(pc_ <= length_);
543 if (pc_ + 3 >= length_)
544 Expand();
545 *reinterpret_cast<uint32_t*>(buffer_ + pc_) = word;
546 pc_ += 4;
547 }
548
549 void
Emit16(uint32_t word)550 InterpretedRegExpMacroAssembler::Emit16(uint32_t word)
551 {
552 MOZ_ASSERT(pc_ <= length_);
553 if (pc_ + 1 >= length_)
554 Expand();
555 *reinterpret_cast<uint16_t*>(buffer_ + pc_) = word;
556 pc_ += 2;
557 }
558
559 void
Emit8(uint32_t word)560 InterpretedRegExpMacroAssembler::Emit8(uint32_t word)
561 {
562 MOZ_ASSERT(pc_ <= length_);
563 if (pc_ == length_)
564 Expand();
565 *reinterpret_cast<unsigned char*>(buffer_ + pc_) = word;
566 pc_ += 1;
567 }
568
569 void
Expand()570 InterpretedRegExpMacroAssembler::Expand()
571 {
572 AutoEnterOOMUnsafeRegion oomUnsafe;
573
574 int newLength = Max(100, length_ * 2);
575 if (newLength < length_ + 4)
576 oomUnsafe.crash("InterpretedRegExpMacroAssembler::Expand");
577
578 buffer_ = (uint8_t*) js_realloc(buffer_, newLength);
579 if (!buffer_)
580 oomUnsafe.crash("InterpretedRegExpMacroAssembler::Expand");
581 length_ = newLength;
582 }
583