1 // Copyright 2008 the V8 project authors. All rights reserved.
2 // Redistribution and use in source and binary forms, with or without
3 // modification, are permitted provided that the following conditions are
4 // met:
5 //
6 // * Redistributions of source code must retain the above copyright
7 // notice, this list of conditions and the following disclaimer.
8 // * Redistributions in binary form must reproduce the above
9 // copyright notice, this list of conditions and the following
10 // disclaimer in the documentation and/or other materials provided
11 // with the distribution.
12 // * Neither the name of Google Inc. nor the names of its
13 // contributors may be used to endorse or promote products derived
14 // from this software without specific prior written permission.
15 //
16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28 #include "v8.h"
29 #include "ast.h"
30 #include "assembler.h"
31 #include "regexp-stack.h"
32 #include "regexp-macro-assembler.h"
33 #include "simulator.h"
34
35 namespace v8 {
36 namespace internal {
37
RegExpMacroAssembler()38 RegExpMacroAssembler::RegExpMacroAssembler() : slow_safe_compiler_(false) {
39 }
40
41
~RegExpMacroAssembler()42 RegExpMacroAssembler::~RegExpMacroAssembler() {
43 }
44
45
CanReadUnaligned()46 bool RegExpMacroAssembler::CanReadUnaligned() {
47 #ifdef V8_HOST_CAN_READ_UNALIGNED
48 return true;
49 #else
50 return false;
51 #endif
52 }
53
54
55 #ifndef V8_INTERPRETED_REGEXP // Avoid unused code, e.g., on ARM.
56
NativeRegExpMacroAssembler()57 NativeRegExpMacroAssembler::NativeRegExpMacroAssembler()
58 : RegExpMacroAssembler() {
59 }
60
61
~NativeRegExpMacroAssembler()62 NativeRegExpMacroAssembler::~NativeRegExpMacroAssembler() {
63 }
64
65
CanReadUnaligned()66 bool NativeRegExpMacroAssembler::CanReadUnaligned() {
67 #ifdef V8_TARGET_CAN_READ_UNALIGNED
68 return !slow_safe();
69 #else
70 return false;
71 #endif
72 }
73
StringCharacterPosition(String * subject,int start_index)74 const byte* NativeRegExpMacroAssembler::StringCharacterPosition(
75 String* subject,
76 int start_index) {
77 // Not just flat, but ultra flat.
78 ASSERT(subject->IsExternalString() || subject->IsSeqString());
79 ASSERT(start_index >= 0);
80 ASSERT(start_index <= subject->length());
81 if (subject->IsAsciiRepresentation()) {
82 const byte* address;
83 if (StringShape(subject).IsExternal()) {
84 const char* data = ExternalAsciiString::cast(subject)->resource()->data();
85 address = reinterpret_cast<const byte*>(data);
86 } else {
87 ASSERT(subject->IsSeqAsciiString());
88 char* data = SeqAsciiString::cast(subject)->GetChars();
89 address = reinterpret_cast<const byte*>(data);
90 }
91 return address + start_index;
92 }
93 const uc16* data;
94 if (StringShape(subject).IsExternal()) {
95 data = ExternalTwoByteString::cast(subject)->resource()->data();
96 } else {
97 ASSERT(subject->IsSeqTwoByteString());
98 data = SeqTwoByteString::cast(subject)->GetChars();
99 }
100 return reinterpret_cast<const byte*>(data + start_index);
101 }
102
103
Match(Handle<Code> regexp_code,Handle<String> subject,int * offsets_vector,int offsets_vector_length,int previous_index,Isolate * isolate)104 NativeRegExpMacroAssembler::Result NativeRegExpMacroAssembler::Match(
105 Handle<Code> regexp_code,
106 Handle<String> subject,
107 int* offsets_vector,
108 int offsets_vector_length,
109 int previous_index,
110 Isolate* isolate) {
111
112 ASSERT(subject->IsFlat());
113 ASSERT(previous_index >= 0);
114 ASSERT(previous_index <= subject->length());
115
116 // No allocations before calling the regexp, but we can't use
117 // AssertNoAllocation, since regexps might be preempted, and another thread
118 // might do allocation anyway.
119
120 String* subject_ptr = *subject;
121 // Character offsets into string.
122 int start_offset = previous_index;
123 int end_offset = subject_ptr->length();
124
125 // The string has been flattened, so it it is a cons string it contains the
126 // full string in the first part.
127 if (StringShape(subject_ptr).IsCons()) {
128 ASSERT_EQ(0, ConsString::cast(subject_ptr)->second()->length());
129 subject_ptr = ConsString::cast(subject_ptr)->first();
130 }
131 // Ensure that an underlying string has the same ascii-ness.
132 bool is_ascii = subject_ptr->IsAsciiRepresentation();
133 ASSERT(subject_ptr->IsExternalString() || subject_ptr->IsSeqString());
134 // String is now either Sequential or External
135 int char_size_shift = is_ascii ? 0 : 1;
136 int char_length = end_offset - start_offset;
137
138 const byte* input_start =
139 StringCharacterPosition(subject_ptr, start_offset);
140 int byte_length = char_length << char_size_shift;
141 const byte* input_end = input_start + byte_length;
142 Result res = Execute(*regexp_code,
143 subject_ptr,
144 start_offset,
145 input_start,
146 input_end,
147 offsets_vector,
148 isolate);
149 return res;
150 }
151
152
Execute(Code * code,String * input,int start_offset,const byte * input_start,const byte * input_end,int * output,Isolate * isolate)153 NativeRegExpMacroAssembler::Result NativeRegExpMacroAssembler::Execute(
154 Code* code,
155 String* input,
156 int start_offset,
157 const byte* input_start,
158 const byte* input_end,
159 int* output,
160 Isolate* isolate) {
161 ASSERT(isolate == Isolate::Current());
162 // Ensure that the minimum stack has been allocated.
163 RegExpStackScope stack_scope(isolate);
164 Address stack_base = stack_scope.stack()->stack_base();
165
166 int direct_call = 0;
167 int result = CALL_GENERATED_REGEXP_CODE(code->entry(),
168 input,
169 start_offset,
170 input_start,
171 input_end,
172 output,
173 stack_base,
174 direct_call,
175 isolate);
176 ASSERT(result <= SUCCESS);
177 ASSERT(result >= RETRY);
178
179 if (result == EXCEPTION && !isolate->has_pending_exception()) {
180 // We detected a stack overflow (on the backtrack stack) in RegExp code,
181 // but haven't created the exception yet.
182 isolate->StackOverflow();
183 }
184 return static_cast<Result>(result);
185 }
186
187
188 const byte NativeRegExpMacroAssembler::word_character_map[] = {
189 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u,
190 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u,
191 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u,
192 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u,
193
194 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u,
195 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u,
196 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, // '0' - '7'
197 0xffu, 0xffu, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, // '8' - '9'
198
199 0x00u, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, // 'A' - 'G'
200 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, // 'H' - 'O'
201 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, // 'P' - 'W'
202 0xffu, 0xffu, 0xffu, 0x00u, 0x00u, 0x00u, 0x00u, 0xffu, // 'X' - 'Z', '_'
203
204 0x00u, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, // 'a' - 'g'
205 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, // 'h' - 'o'
206 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, // 'p' - 'w'
207 0xffu, 0xffu, 0xffu, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, // 'x' - 'z'
208 };
209
210
CaseInsensitiveCompareUC16(Address byte_offset1,Address byte_offset2,size_t byte_length,Isolate * isolate)211 int NativeRegExpMacroAssembler::CaseInsensitiveCompareUC16(
212 Address byte_offset1,
213 Address byte_offset2,
214 size_t byte_length,
215 Isolate* isolate) {
216 ASSERT(isolate == Isolate::Current());
217 unibrow::Mapping<unibrow::Ecma262Canonicalize>* canonicalize =
218 isolate->regexp_macro_assembler_canonicalize();
219 // This function is not allowed to cause a garbage collection.
220 // A GC might move the calling generated code and invalidate the
221 // return address on the stack.
222 ASSERT(byte_length % 2 == 0);
223 uc16* substring1 = reinterpret_cast<uc16*>(byte_offset1);
224 uc16* substring2 = reinterpret_cast<uc16*>(byte_offset2);
225 size_t length = byte_length >> 1;
226
227 for (size_t i = 0; i < length; i++) {
228 unibrow::uchar c1 = substring1[i];
229 unibrow::uchar c2 = substring2[i];
230 if (c1 != c2) {
231 unibrow::uchar s1[1] = { c1 };
232 canonicalize->get(c1, '\0', s1);
233 if (s1[0] != c2) {
234 unibrow::uchar s2[1] = { c2 };
235 canonicalize->get(c2, '\0', s2);
236 if (s1[0] != s2[0]) {
237 return 0;
238 }
239 }
240 }
241 }
242 return 1;
243 }
244
245
GrowStack(Address stack_pointer,Address * stack_base,Isolate * isolate)246 Address NativeRegExpMacroAssembler::GrowStack(Address stack_pointer,
247 Address* stack_base,
248 Isolate* isolate) {
249 ASSERT(isolate == Isolate::Current());
250 RegExpStack* regexp_stack = isolate->regexp_stack();
251 size_t size = regexp_stack->stack_capacity();
252 Address old_stack_base = regexp_stack->stack_base();
253 ASSERT(old_stack_base == *stack_base);
254 ASSERT(stack_pointer <= old_stack_base);
255 ASSERT(static_cast<size_t>(old_stack_base - stack_pointer) <= size);
256 Address new_stack_base = regexp_stack->EnsureCapacity(size * 2);
257 if (new_stack_base == NULL) {
258 return NULL;
259 }
260 *stack_base = new_stack_base;
261 intptr_t stack_content_size = old_stack_base - stack_pointer;
262 return new_stack_base - stack_content_size;
263 }
264
265 #endif // V8_INTERPRETED_REGEXP
266
267 } } // namespace v8::internal
268