OLD | NEW |
1 // Copyright 2008 the V8 project authors. All rights reserved. | 1 // Copyright 2008 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 28 matching lines...) Expand all Loading... |
39 | 39 |
40 class RegExpMacroAssembler { | 40 class RegExpMacroAssembler { |
41 public: | 41 public: |
42 // The implementation must be able to handle at least: | 42 // The implementation must be able to handle at least: |
43 static const int kMaxRegister = (1 << 16) - 1; | 43 static const int kMaxRegister = (1 << 16) - 1; |
44 static const int kMaxCPOffset = (1 << 15) - 1; | 44 static const int kMaxCPOffset = (1 << 15) - 1; |
45 static const int kMinCPOffset = -(1 << 15); | 45 static const int kMinCPOffset = -(1 << 15); |
46 enum IrregexpImplementation { | 46 enum IrregexpImplementation { |
47 kIA32Implementation, | 47 kIA32Implementation, |
48 kARMImplementation, | 48 kARMImplementation, |
| 49 kX64Implementation, |
49 kBytecodeImplementation | 50 kBytecodeImplementation |
50 }; | 51 }; |
51 | 52 |
52 enum StackCheckFlag { | 53 enum StackCheckFlag { |
53 kNoStackLimitCheck = false, | 54 kNoStackLimitCheck = false, |
54 kCheckStackLimit = true | 55 kCheckStackLimit = true |
55 }; | 56 }; |
56 | 57 |
57 RegExpMacroAssembler(); | 58 RegExpMacroAssembler(); |
58 virtual ~RegExpMacroAssembler(); | 59 virtual ~RegExpMacroAssembler(); |
59 // The maximal number of pushes between stack checks. Users must supply | 60 // The maximal number of pushes between stack checks. Users must supply |
60 // kCheckStackLimit flag to push operations (instead of kNoStackLimitCheck) | 61 // kCheckStackLimit flag to push operations (instead of kNoStackLimitCheck) |
61 // at least once for every stack_limit() pushes that are executed. | 62 // at least once for every stack_limit() pushes that are executed. |
62 virtual int stack_limit_slack() = 0; | 63 virtual int stack_limit_slack() = 0; |
63 virtual void AdvanceCurrentPosition(int by) = 0; // Signed cp change. | 64 virtual void AdvanceCurrentPosition(int by) = 0; // Signed cp change. |
64 virtual void AdvanceRegister(int reg, int by) = 0; // r[reg] += by. | 65 virtual void AdvanceRegister(int reg, int by) = 0; // r[reg] += by. |
65 // Continues execution from the position pushed on the top of the backtrack | 66 // Continues execution from the position pushed on the top of the backtrack |
66 // stack by an earlier PushBacktrack(Label*). | 67 // stack by an earlier PushBacktrack(Label*). |
67 virtual void Backtrack() = 0; | 68 virtual void Backtrack() = 0; |
68 virtual void Bind(Label* label) = 0; | 69 virtual void Bind(Label* label) = 0; |
69 virtual void CheckAtStart(Label* on_at_start) = 0; | 70 virtual void CheckAtStart(Label* on_at_start) = 0; |
70 // Check the current character against a bitmap. The range of the current | |
71 // character must be from start to start + length_of_bitmap_in_bits. | |
72 virtual void CheckBitmap( | |
73 uc16 start, // The bitmap is indexed from this character. | |
74 Label* bitmap, // Where the bitmap is emitted. | |
75 Label* on_zero) = 0; // Where to go if the bit is 0. Fall through on 1. | |
76 // Dispatch after looking the current character up in a 2-bits-per-entry | 71 // Dispatch after looking the current character up in a 2-bits-per-entry |
77 // map. The destinations vector has up to 4 labels. | 72 // map. The destinations vector has up to 4 labels. |
78 virtual void CheckCharacter(uint32_t c, Label* on_equal) = 0; | 73 virtual void CheckCharacter(uint32_t c, Label* on_equal) = 0; |
79 // Bitwise and the current character with the given constant and then | 74 // Bitwise and the current character with the given constant and then |
80 // check for a match with c. | 75 // check for a match with c. |
81 virtual void CheckCharacterAfterAnd(uint32_t c, | 76 virtual void CheckCharacterAfterAnd(uint32_t c, |
82 uint32_t and_with, | 77 uint32_t and_with, |
83 Label* on_equal) = 0; | 78 Label* on_equal) = 0; |
84 virtual void CheckCharacterGT(uc16 limit, Label* on_greater) = 0; | 79 virtual void CheckCharacterGT(uc16 limit, Label* on_greater) = 0; |
85 virtual void CheckCharacterLT(uc16 limit, Label* on_less) = 0; | 80 virtual void CheckCharacterLT(uc16 limit, Label* on_less) = 0; |
(...skipping 39 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
125 // Check whether a standard/default character class matches the current | 120 // Check whether a standard/default character class matches the current |
126 // character. Returns false if the type of special character class does | 121 // character. Returns false if the type of special character class does |
127 // not have custom support. | 122 // not have custom support. |
128 // May clobber the current loaded character. | 123 // May clobber the current loaded character. |
129 virtual bool CheckSpecialCharacterClass(uc16 type, | 124 virtual bool CheckSpecialCharacterClass(uc16 type, |
130 int cp_offset, | 125 int cp_offset, |
131 bool check_offset, | 126 bool check_offset, |
132 Label* on_no_match) { | 127 Label* on_no_match) { |
133 return false; | 128 return false; |
134 } | 129 } |
135 // Dispatch after looking the current character up in a byte map. The | |
136 // destinations vector has up to 256 labels. | |
137 virtual void DispatchByteMap( | |
138 uc16 start, | |
139 Label* byte_map, | |
140 const Vector<Label*>& destinations) = 0; | |
141 virtual void DispatchHalfNibbleMap( | |
142 uc16 start, | |
143 Label* half_nibble_map, | |
144 const Vector<Label*>& destinations) = 0; | |
145 // Dispatch after looking the high byte of the current character up in a byte | |
146 // map. The destinations vector has up to 256 labels. | |
147 virtual void DispatchHighByteMap( | |
148 byte start, | |
149 Label* byte_map, | |
150 const Vector<Label*>& destinations) = 0; | |
151 virtual void EmitOrLink(Label* label) = 0; | |
152 virtual void Fail() = 0; | 130 virtual void Fail() = 0; |
153 virtual Handle<Object> GetCode(Handle<String> source) = 0; | 131 virtual Handle<Object> GetCode(Handle<String> source) = 0; |
154 virtual void GoTo(Label* label) = 0; | 132 virtual void GoTo(Label* label) = 0; |
155 // Check whether a register is >= a given constant and go to a label if it | 133 // Check whether a register is >= a given constant and go to a label if it |
156 // is. Backtracks instead if the label is NULL. | 134 // is. Backtracks instead if the label is NULL. |
157 virtual void IfRegisterGE(int reg, int comparand, Label* if_ge) = 0; | 135 virtual void IfRegisterGE(int reg, int comparand, Label* if_ge) = 0; |
158 // Check whether a register is < a given constant and go to a label if it is. | 136 // Check whether a register is < a given constant and go to a label if it is. |
159 // Backtracks instead if the label is NULL. | 137 // Backtracks instead if the label is NULL. |
160 virtual void IfRegisterLT(int reg, int comparand, Label* if_lt) = 0; | 138 virtual void IfRegisterLT(int reg, int comparand, Label* if_lt) = 0; |
161 // Check whether a register is == to the current position and go to a | 139 // Check whether a register is == to the current position and go to a |
(...skipping 12 matching lines...) Expand all Loading... |
174 virtual void PushCurrentPosition() = 0; | 152 virtual void PushCurrentPosition() = 0; |
175 virtual void PushRegister(int register_index, | 153 virtual void PushRegister(int register_index, |
176 StackCheckFlag check_stack_limit) = 0; | 154 StackCheckFlag check_stack_limit) = 0; |
177 virtual void ReadCurrentPositionFromRegister(int reg) = 0; | 155 virtual void ReadCurrentPositionFromRegister(int reg) = 0; |
178 virtual void ReadStackPointerFromRegister(int reg) = 0; | 156 virtual void ReadStackPointerFromRegister(int reg) = 0; |
179 virtual void SetRegister(int register_index, int to) = 0; | 157 virtual void SetRegister(int register_index, int to) = 0; |
180 virtual void Succeed() = 0; | 158 virtual void Succeed() = 0; |
181 virtual void WriteCurrentPositionToRegister(int reg, int cp_offset) = 0; | 159 virtual void WriteCurrentPositionToRegister(int reg, int cp_offset) = 0; |
182 virtual void ClearRegisters(int reg_from, int reg_to) = 0; | 160 virtual void ClearRegisters(int reg_from, int reg_to) = 0; |
183 virtual void WriteStackPointerToRegister(int reg) = 0; | 161 virtual void WriteStackPointerToRegister(int reg) = 0; |
184 | |
185 private: | |
186 }; | 162 }; |
187 | 163 |
188 | 164 |
189 struct ArraySlice { | 165 class NativeRegExpMacroAssembler: public RegExpMacroAssembler { |
190 public: | 166 public: |
191 ArraySlice(Handle<ByteArray> array, size_t offset) | 167 // Type of input string to generate code for. |
192 : array_(array), offset_(offset) {} | 168 enum Mode { ASCII = 1, UC16 = 2 }; |
193 Handle<ByteArray> array() { return array_; } | |
194 // Offset in the byte array data. | |
195 size_t offset() { return offset_; } | |
196 // Offset from the ByteArray pointer. | |
197 size_t base_offset() { | |
198 return ByteArray::kHeaderSize - kHeapObjectTag + offset_; | |
199 } | |
200 void* location() { | |
201 return reinterpret_cast<void*>(array_->GetDataStartAddress() + offset_); | |
202 } | |
203 template <typename T> | |
204 T& at(int idx) { | |
205 return reinterpret_cast<T*>(array_->GetDataStartAddress() + offset_)[idx]; | |
206 } | |
207 private: | |
208 Handle<ByteArray> array_; | |
209 size_t offset_; | |
210 }; | |
211 | 169 |
| 170 // Result of calling generated native RegExp code. |
| 171 // RETRY: Something significant changed during execution, and the matching |
| 172 // should be retried from scratch. |
| 173 // EXCEPTION: Something failed during execution. If no exception has been |
| 174 // thrown, it's an internal out-of-memory, and the caller should |
| 175 // throw the exception. |
| 176 // FAILURE: Matching failed. |
| 177 // SUCCESS: Matching succeeded, and the output array has been filled with |
| 178 // capture positions. |
| 179 enum Result { RETRY = -2, EXCEPTION = -1, FAILURE = 0, SUCCESS = 1 }; |
212 | 180 |
213 class ByteArrayProvider { | 181 NativeRegExpMacroAssembler(); |
214 public: | 182 virtual ~NativeRegExpMacroAssembler(); |
215 explicit ByteArrayProvider(unsigned int initial_size); | 183 |
216 // Provides a place to put "size" elements of size "element_size". | 184 static Result Match(Handle<Code> regexp, |
217 // The information can be stored in the provided ByteArray at the "offset". | 185 Handle<String> subject, |
218 // The offset is aligned to the element size. | 186 int* offsets_vector, |
219 ArraySlice GetBuffer(unsigned int size, | 187 int offsets_vector_length, |
220 unsigned int element_size); | 188 int previous_index); |
221 template <typename T> | 189 |
222 ArraySlice GetBuffer(Vector<T> values); | 190 // Compares two-byte strings case insensitively. |
223 private: | 191 // Called from generated RegExp code. |
224 size_t byte_array_size_; | 192 static int CaseInsensitiveCompareUC16(Address byte_offset1, |
225 Handle<ByteArray> current_byte_array_; | 193 Address byte_offset2, |
226 int current_byte_array_free_offset_; | 194 size_t byte_length); |
| 195 |
| 196 static const byte* StringCharacterPosition(String* subject, int start_index); |
| 197 |
| 198 static Result Execute(Code* code, |
| 199 String* input, |
| 200 int start_offset, |
| 201 const byte* input_start, |
| 202 const byte* input_end, |
| 203 int* output, |
| 204 bool at_start); |
227 }; | 205 }; |
228 | 206 |
229 } } // namespace v8::internal | 207 } } // namespace v8::internal |
230 | 208 |
231 #endif // V8_REGEXP_MACRO_ASSEMBLER_H_ | 209 #endif // V8_REGEXP_MACRO_ASSEMBLER_H_ |
OLD | NEW |