1 // Copyright 2012 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 38 RegExpMacroAssembler::RegExpMacroAssembler(Zone* zone) 39 : slow_safe_compiler_(false), 40 global_mode_(NOT_GLOBAL), 41 zone_(zone) { 42 } 43 44 45 RegExpMacroAssembler::~RegExpMacroAssembler() { 46 } 47 48 49 bool RegExpMacroAssembler::CanReadUnaligned() { 50 #ifdef V8_HOST_CAN_READ_UNALIGNED 51 return true; 52 #else 53 return false; 54 #endif 55 } 56 57 58 #ifndef V8_INTERPRETED_REGEXP // Avoid unused code, e.g., on ARM. 59 60 NativeRegExpMacroAssembler::NativeRegExpMacroAssembler(Zone* zone) 61 : RegExpMacroAssembler(zone) { 62 } 63 64 65 NativeRegExpMacroAssembler::~NativeRegExpMacroAssembler() { 66 } 67 68 69 bool NativeRegExpMacroAssembler::CanReadUnaligned() { 70 return FLAG_enable_unaligned_accesses && !slow_safe(); 71 } 72 73 const byte* NativeRegExpMacroAssembler::StringCharacterPosition( 74 String* subject, 75 int start_index) { 76 // Not just flat, but ultra flat. 77 ASSERT(subject->IsExternalString() || subject->IsSeqString()); 78 ASSERT(start_index >= 0); 79 ASSERT(start_index <= subject->length()); 80 if (subject->IsOneByteRepresentation()) { 81 const byte* address; 82 if (StringShape(subject).IsExternal()) { 83 const uint8_t* data = ExternalAsciiString::cast(subject)->GetChars(); 84 address = reinterpret_cast<const byte*>(data); 85 } else { 86 ASSERT(subject->IsSeqOneByteString()); 87 const uint8_t* data = SeqOneByteString::cast(subject)->GetChars(); 88 address = reinterpret_cast<const byte*>(data); 89 } 90 return address + start_index; 91 } 92 const uc16* data; 93 if (StringShape(subject).IsExternal()) { 94 data = ExternalTwoByteString::cast(subject)->GetChars(); 95 } else { 96 ASSERT(subject->IsSeqTwoByteString()); 97 data = SeqTwoByteString::cast(subject)->GetChars(); 98 } 99 return reinterpret_cast<const byte*>(data + start_index); 100 } 101 102 103 NativeRegExpMacroAssembler::Result NativeRegExpMacroAssembler::Match( 104 Handle<Code> regexp_code, 105 Handle<String> subject, 106 int* offsets_vector, 107 int offsets_vector_length, 108 int previous_index, 109 Isolate* isolate) { 110 111 ASSERT(subject->IsFlat()); 112 ASSERT(previous_index >= 0); 113 ASSERT(previous_index <= subject->length()); 114 115 // No allocations before calling the regexp, but we can't use 116 // DisallowHeapAllocation, since regexps might be preempted, and another 117 // thread might do allocation anyway. 118 119 String* subject_ptr = *subject; 120 // Character offsets into string. 121 int start_offset = previous_index; 122 int char_length = subject_ptr->length() - start_offset; 123 int slice_offset = 0; 124 125 // The string has been flattened, so if 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 } else if (StringShape(subject_ptr).IsSliced()) { 131 SlicedString* slice = SlicedString::cast(subject_ptr); 132 subject_ptr = slice->parent(); 133 slice_offset = slice->offset(); 134 } 135 // Ensure that an underlying string has the same ASCII-ness. 136 bool is_ascii = subject_ptr->IsOneByteRepresentation(); 137 ASSERT(subject_ptr->IsExternalString() || subject_ptr->IsSeqString()); 138 // String is now either Sequential or External 139 int char_size_shift = is_ascii ? 0 : 1; 140 141 const byte* input_start = 142 StringCharacterPosition(subject_ptr, start_offset + slice_offset); 143 int byte_length = char_length << char_size_shift; 144 const byte* input_end = input_start + byte_length; 145 Result res = Execute(*regexp_code, 146 *subject, 147 start_offset, 148 input_start, 149 input_end, 150 offsets_vector, 151 offsets_vector_length, 152 isolate); 153 return res; 154 } 155 156 157 NativeRegExpMacroAssembler::Result NativeRegExpMacroAssembler::Execute( 158 Code* code, 159 String* input, // This needs to be the unpacked (sliced, cons) string. 160 int start_offset, 161 const byte* input_start, 162 const byte* input_end, 163 int* output, 164 int output_size, 165 Isolate* isolate) { 166 ASSERT(isolate == Isolate::Current()); 167 // Ensure that the minimum stack has been allocated. 168 RegExpStackScope stack_scope(isolate); 169 Address stack_base = stack_scope.stack()->stack_base(); 170 171 int direct_call = 0; 172 int result = CALL_GENERATED_REGEXP_CODE(code->entry(), 173 input, 174 start_offset, 175 input_start, 176 input_end, 177 output, 178 output_size, 179 stack_base, 180 direct_call, 181 isolate); 182 ASSERT(result >= RETRY); 183 184 if (result == EXCEPTION && !isolate->has_pending_exception()) { 185 // We detected a stack overflow (on the backtrack stack) in RegExp code, 186 // but haven't created the exception yet. 187 isolate->StackOverflow(); 188 } 189 return static_cast<Result>(result); 190 } 191 192 193 const byte NativeRegExpMacroAssembler::word_character_map[] = { 194 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 195 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 196 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 197 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 198 199 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 200 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 201 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, // '0' - '7' 202 0xffu, 0xffu, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, // '8' - '9' 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, 0xffu, // 'X' - 'Z', '_' 208 209 0x00u, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, // 'a' - 'g' 210 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, // 'h' - 'o' 211 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, 0xffu, // 'p' - 'w' 212 0xffu, 0xffu, 0xffu, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, // 'x' - 'z' 213 // Latin-1 range 214 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 215 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 216 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 217 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 218 219 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 220 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 221 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 222 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 223 224 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 225 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 226 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 227 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 228 229 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 230 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 231 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 232 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 233 }; 234 235 236 int NativeRegExpMacroAssembler::CaseInsensitiveCompareUC16( 237 Address byte_offset1, 238 Address byte_offset2, 239 size_t byte_length, 240 Isolate* isolate) { 241 ASSERT(isolate == Isolate::Current()); 242 unibrow::Mapping<unibrow::Ecma262Canonicalize>* canonicalize = 243 isolate->regexp_macro_assembler_canonicalize(); 244 // This function is not allowed to cause a garbage collection. 245 // A GC might move the calling generated code and invalidate the 246 // return address on the stack. 247 ASSERT(byte_length % 2 == 0); 248 uc16* substring1 = reinterpret_cast<uc16*>(byte_offset1); 249 uc16* substring2 = reinterpret_cast<uc16*>(byte_offset2); 250 size_t length = byte_length >> 1; 251 252 for (size_t i = 0; i < length; i++) { 253 unibrow::uchar c1 = substring1[i]; 254 unibrow::uchar c2 = substring2[i]; 255 if (c1 != c2) { 256 unibrow::uchar s1[1] = { c1 }; 257 canonicalize->get(c1, '\0', s1); 258 if (s1[0] != c2) { 259 unibrow::uchar s2[1] = { c2 }; 260 canonicalize->get(c2, '\0', s2); 261 if (s1[0] != s2[0]) { 262 return 0; 263 } 264 } 265 } 266 } 267 return 1; 268 } 269 270 271 Address NativeRegExpMacroAssembler::GrowStack(Address stack_pointer, 272 Address* stack_base, 273 Isolate* isolate) { 274 ASSERT(isolate == Isolate::Current()); 275 RegExpStack* regexp_stack = isolate->regexp_stack(); 276 size_t size = regexp_stack->stack_capacity(); 277 Address old_stack_base = regexp_stack->stack_base(); 278 ASSERT(old_stack_base == *stack_base); 279 ASSERT(stack_pointer <= old_stack_base); 280 ASSERT(static_cast<size_t>(old_stack_base - stack_pointer) <= size); 281 Address new_stack_base = regexp_stack->EnsureCapacity(size * 2); 282 if (new_stack_base == NULL) { 283 return NULL; 284 } 285 *stack_base = new_stack_base; 286 intptr_t stack_content_size = old_stack_base - stack_pointer; 287 return new_stack_base - stack_content_size; 288 } 289 290 #endif // V8_INTERPRETED_REGEXP 291 292 } } // namespace v8::internal 293