blob: 4ca83a47691cf25d4b56a71493ff59c9dd35a98b [file] [log] [blame]
rossberg@chromium.org717967f2011-07-20 13:44:42 +00001// Copyright 2011 the V8 project authors. All rights reserved.
christian.plesner.hansen43d26ec2008-07-03 15:10:15 +00002// 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
ager@chromium.orga74f0da2008-12-03 16:05:52 +000030#include "ast.h"
kasperl@chromium.orgb3284ad2009-05-18 06:12:45 +000031#include "compiler.h"
christian.plesner.hansen43d26ec2008-07-03 15:10:15 +000032#include "execution.h"
33#include "factory.h"
sgjesse@chromium.org0b6db592009-07-30 14:48:31 +000034#include "jsregexp.h"
christian.plesner.hansen43d26ec2008-07-03 15:10:15 +000035#include "platform.h"
kasperl@chromium.orga5551262010-12-07 12:49:48 +000036#include "string-search.h"
kasperl@chromium.org41044eb2008-10-06 08:24:46 +000037#include "runtime.h"
kasperl@chromium.org9fe21c62008-10-28 08:53:51 +000038#include "compilation-cache.h"
ager@chromium.orga74f0da2008-12-03 16:05:52 +000039#include "string-stream.h"
40#include "parser.h"
41#include "regexp-macro-assembler.h"
42#include "regexp-macro-assembler-tracer.h"
43#include "regexp-macro-assembler-irregexp.h"
ager@chromium.org32912102009-01-16 10:38:43 +000044#include "regexp-stack.h"
ager@chromium.orga74f0da2008-12-03 16:05:52 +000045
ricow@chromium.orgc9c80822010-04-21 08:22:37 +000046#ifndef V8_INTERPRETED_REGEXP
kasperl@chromium.org71affb52009-05-26 05:44:31 +000047#if V8_TARGET_ARCH_IA32
ager@chromium.org3a37e9b2009-04-27 09:26:21 +000048#include "ia32/regexp-macro-assembler-ia32.h"
ager@chromium.org9085a012009-05-11 19:22:57 +000049#elif V8_TARGET_ARCH_X64
ager@chromium.org9085a012009-05-11 19:22:57 +000050#include "x64/regexp-macro-assembler-x64.h"
51#elif V8_TARGET_ARCH_ARM
52#include "arm/regexp-macro-assembler-arm.h"
lrn@chromium.org7516f052011-03-30 08:52:27 +000053#elif V8_TARGET_ARCH_MIPS
54#include "mips/regexp-macro-assembler-mips.h"
kasperl@chromium.org2abc4502009-07-02 07:00:29 +000055#else
56#error Unsupported target architecture.
ager@chromium.orga74f0da2008-12-03 16:05:52 +000057#endif
sgjesse@chromium.org911335c2009-08-19 12:59:44 +000058#endif
ager@chromium.orga74f0da2008-12-03 16:05:52 +000059
60#include "interpreter-irregexp.h"
kasperl@chromium.org9fe21c62008-10-28 08:53:51 +000061
ager@chromium.orga74f0da2008-12-03 16:05:52 +000062
kasperl@chromium.org71affb52009-05-26 05:44:31 +000063namespace v8 {
64namespace internal {
christian.plesner.hansen43d26ec2008-07-03 15:10:15 +000065
mads.s.ager@gmail.com9a4089a2008-09-01 08:55:01 +000066Handle<Object> RegExpImpl::CreateRegExpLiteral(Handle<JSFunction> constructor,
67 Handle<String> pattern,
christian.plesner.hansen43d26ec2008-07-03 15:10:15 +000068 Handle<String> flags,
69 bool* has_pending_exception) {
christian.plesner.hansen43d26ec2008-07-03 15:10:15 +000070 // Call the construct code with 2 arguments.
71 Object** argv[2] = { Handle<Object>::cast(pattern).location(),
72 Handle<Object>::cast(flags).location() };
mads.s.ager@gmail.com9a4089a2008-09-01 08:55:01 +000073 return Execution::New(constructor, 2, argv, has_pending_exception);
christian.plesner.hansen43d26ec2008-07-03 15:10:15 +000074}
75
76
kasperl@chromium.org9fe21c62008-10-28 08:53:51 +000077static JSRegExp::Flags RegExpFlagsFromString(Handle<String> str) {
78 int flags = JSRegExp::NONE;
ager@chromium.orgbb29dc92009-03-24 13:25:23 +000079 for (int i = 0; i < str->length(); i++) {
80 switch (str->Get(i)) {
kasperl@chromium.org9fe21c62008-10-28 08:53:51 +000081 case 'i':
82 flags |= JSRegExp::IGNORE_CASE;
83 break;
84 case 'g':
85 flags |= JSRegExp::GLOBAL;
86 break;
87 case 'm':
88 flags |= JSRegExp::MULTILINE;
89 break;
90 }
91 }
92 return JSRegExp::Flags(flags);
93}
94
95
ager@chromium.orga74f0da2008-12-03 16:05:52 +000096static inline void ThrowRegExpException(Handle<JSRegExp> re,
97 Handle<String> pattern,
98 Handle<String> error_text,
99 const char* message) {
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +0000100 Isolate* isolate = re->GetIsolate();
101 Factory* factory = isolate->factory();
102 Handle<FixedArray> elements = factory->NewFixedArray(2);
karlklose@chromium.org8f806e82011-03-07 14:06:08 +0000103 elements->set(0, *pattern);
104 elements->set(1, *error_text);
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +0000105 Handle<JSArray> array = factory->NewJSArrayWithElements(elements);
106 Handle<Object> regexp_err = factory->NewSyntaxError(message, array);
107 isolate->Throw(*regexp_err);
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000108}
kasperl@chromium.org41044eb2008-10-06 08:24:46 +0000109
110
ager@chromium.org8bb60582008-12-11 12:02:20 +0000111// Generic RegExp methods. Dispatches to implementation specific methods.
112
113
kasperl@chromium.org41044eb2008-10-06 08:24:46 +0000114Handle<Object> RegExpImpl::Compile(Handle<JSRegExp> re,
115 Handle<String> pattern,
kasperl@chromium.org9fe21c62008-10-28 08:53:51 +0000116 Handle<String> flag_str) {
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +0000117 Isolate* isolate = re->GetIsolate();
kasperl@chromium.org9fe21c62008-10-28 08:53:51 +0000118 JSRegExp::Flags flags = RegExpFlagsFromString(flag_str);
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +0000119 CompilationCache* compilation_cache = isolate->compilation_cache();
120 Handle<FixedArray> cached = compilation_cache->LookupRegExp(pattern, flags);
kasperl@chromium.org9fe21c62008-10-28 08:53:51 +0000121 bool in_cache = !cached.is_null();
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +0000122 LOG(isolate, RegExpCompileEvent(re, in_cache));
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000123
kasperl@chromium.org41044eb2008-10-06 08:24:46 +0000124 Handle<Object> result;
kasperl@chromium.org9fe21c62008-10-28 08:53:51 +0000125 if (in_cache) {
126 re->set_data(*cached);
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000127 return re;
128 }
kasperl@chromium.orga5551262010-12-07 12:49:48 +0000129 pattern = FlattenGetString(pattern);
jkummerow@chromium.orge297f592011-06-08 10:05:15 +0000130 ZoneScope zone_scope(isolate, DELETE_ON_EXIT);
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +0000131 PostponeInterruptsScope postpone(isolate);
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000132 RegExpCompileData parse_result;
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +0000133 FlatStringReader reader(isolate, pattern);
fschneider@chromium.orge03fb642010-11-01 12:34:09 +0000134 if (!RegExpParser::ParseRegExp(&reader, flags.is_multiline(),
135 &parse_result)) {
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000136 // Throw an exception if we fail to parse the pattern.
137 ThrowRegExpException(re,
138 pattern,
139 parse_result.error,
140 "malformed_regexp");
141 return Handle<Object>::null();
kasperl@chromium.org41044eb2008-10-06 08:24:46 +0000142 }
143
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000144 if (parse_result.simple && !flags.is_ignore_case()) {
145 // Parse-tree is a single atom that is equal to the pattern.
146 AtomCompile(re, pattern, flags, pattern);
147 } else if (parse_result.tree->IsAtom() &&
148 !flags.is_ignore_case() &&
149 parse_result.capture_count == 0) {
150 RegExpAtom* atom = parse_result.tree->AsAtom();
151 Vector<const uc16> atom_pattern = atom->data();
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +0000152 Handle<String> atom_string =
153 isolate->factory()->NewStringFromTwoByte(atom_pattern);
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000154 AtomCompile(re, pattern, flags, atom_string);
155 } else {
whesse@chromium.orgcec079d2010-03-22 14:44:04 +0000156 IrregexpInitialize(re, pattern, flags, parse_result.capture_count);
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000157 }
158 ASSERT(re->data()->IsFixedArray());
159 // Compilation succeeded so the data is set on the regexp
160 // and we can store it in the cache.
161 Handle<FixedArray> data(FixedArray::cast(re->data()));
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +0000162 compilation_cache->PutRegExp(pattern, flags, data);
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000163
164 return re;
kasperl@chromium.org41044eb2008-10-06 08:24:46 +0000165}
166
167
168Handle<Object> RegExpImpl::Exec(Handle<JSRegExp> regexp,
169 Handle<String> subject,
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000170 int index,
171 Handle<JSArray> last_match_info) {
kasperl@chromium.org9fe21c62008-10-28 08:53:51 +0000172 switch (regexp->TypeTag()) {
ager@chromium.org8bb60582008-12-11 12:02:20 +0000173 case JSRegExp::ATOM:
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000174 return AtomExec(regexp, subject, index, last_match_info);
ager@chromium.org8bb60582008-12-11 12:02:20 +0000175 case JSRegExp::IRREGEXP: {
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000176 Handle<Object> result =
177 IrregexpExec(regexp, subject, index, last_match_info);
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +0000178 ASSERT(!result.is_null() || Isolate::Current()->has_pending_exception());
ager@chromium.orgddb913d2009-01-27 10:01:48 +0000179 return result;
ager@chromium.org8bb60582008-12-11 12:02:20 +0000180 }
kasperl@chromium.org41044eb2008-10-06 08:24:46 +0000181 default:
182 UNREACHABLE();
ager@chromium.org8bb60582008-12-11 12:02:20 +0000183 return Handle<Object>::null();
kasperl@chromium.org41044eb2008-10-06 08:24:46 +0000184 }
185}
186
187
ager@chromium.org8bb60582008-12-11 12:02:20 +0000188// RegExp Atom implementation: Simple string search using indexOf.
189
190
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000191void RegExpImpl::AtomCompile(Handle<JSRegExp> re,
192 Handle<String> pattern,
193 JSRegExp::Flags flags,
194 Handle<String> match_pattern) {
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +0000195 re->GetIsolate()->factory()->SetRegExpAtomData(re,
196 JSRegExp::ATOM,
197 pattern,
198 flags,
199 match_pattern);
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000200}
201
202
203static void SetAtomLastCapture(FixedArray* array,
204 String* subject,
205 int from,
206 int to) {
207 NoHandleAllocation no_handles;
208 RegExpImpl::SetLastCaptureCount(array, 2);
209 RegExpImpl::SetLastSubject(array, subject);
210 RegExpImpl::SetLastInput(array, subject);
211 RegExpImpl::SetCapture(array, 0, from);
212 RegExpImpl::SetCapture(array, 1, to);
kasperl@chromium.org41044eb2008-10-06 08:24:46 +0000213}
214
215
216Handle<Object> RegExpImpl::AtomExec(Handle<JSRegExp> re,
217 Handle<String> subject,
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000218 int index,
219 Handle<JSArray> last_match_info) {
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +0000220 Isolate* isolate = re->GetIsolate();
221
kasperl@chromium.orga5551262010-12-07 12:49:48 +0000222 ASSERT(0 <= index);
223 ASSERT(index <= subject->length());
kasperl@chromium.org41044eb2008-10-06 08:24:46 +0000224
kasperl@chromium.orga5551262010-12-07 12:49:48 +0000225 if (!subject->IsFlat()) FlattenString(subject);
226 AssertNoAllocation no_heap_allocation; // ensure vectors stay valid
kasperl@chromium.org41044eb2008-10-06 08:24:46 +0000227
kasperl@chromium.orga5551262010-12-07 12:49:48 +0000228 String* needle = String::cast(re->DataAt(JSRegExp::kAtomPatternIndex));
229 int needle_len = needle->length();
ricow@chromium.orgddd545c2011-08-24 12:02:41 +0000230 ASSERT(needle->IsFlat());
kasperl@chromium.orga5551262010-12-07 12:49:48 +0000231
232 if (needle_len != 0) {
ricow@chromium.orgddd545c2011-08-24 12:02:41 +0000233 if (index + needle_len > subject->length()) {
234 return isolate->factory()->null_value();
235 }
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +0000236
ricow@chromium.orgddd545c2011-08-24 12:02:41 +0000237 String::FlatContent needle_content = needle->GetFlatContent();
238 String::FlatContent subject_content = subject->GetFlatContent();
239 ASSERT(needle_content.IsFlat());
240 ASSERT(subject_content.IsFlat());
kasperl@chromium.orga5551262010-12-07 12:49:48 +0000241 // dispatch on type of strings
ricow@chromium.orgddd545c2011-08-24 12:02:41 +0000242 index = (needle_content.IsAscii()
243 ? (subject_content.IsAscii()
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +0000244 ? SearchString(isolate,
ricow@chromium.orgddd545c2011-08-24 12:02:41 +0000245 subject_content.ToAsciiVector(),
246 needle_content.ToAsciiVector(),
kasperl@chromium.orga5551262010-12-07 12:49:48 +0000247 index)
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +0000248 : SearchString(isolate,
ricow@chromium.orgddd545c2011-08-24 12:02:41 +0000249 subject_content.ToUC16Vector(),
250 needle_content.ToAsciiVector(),
kasperl@chromium.orga5551262010-12-07 12:49:48 +0000251 index))
ricow@chromium.orgddd545c2011-08-24 12:02:41 +0000252 : (subject_content.IsAscii()
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +0000253 ? SearchString(isolate,
ricow@chromium.orgddd545c2011-08-24 12:02:41 +0000254 subject_content.ToAsciiVector(),
255 needle_content.ToUC16Vector(),
kasperl@chromium.orga5551262010-12-07 12:49:48 +0000256 index)
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +0000257 : SearchString(isolate,
ricow@chromium.orgddd545c2011-08-24 12:02:41 +0000258 subject_content.ToUC16Vector(),
259 needle_content.ToUC16Vector(),
kasperl@chromium.orga5551262010-12-07 12:49:48 +0000260 index)));
kmillikin@chromium.org7c2628c2011-08-10 11:27:35 +0000261 if (index == -1) return isolate->factory()->null_value();
kasperl@chromium.orga5551262010-12-07 12:49:48 +0000262 }
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000263 ASSERT(last_match_info->HasFastElements());
ager@chromium.org7c537e22008-10-16 08:43:32 +0000264
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000265 {
266 NoHandleAllocation no_handles;
sgjesse@chromium.org0b6db592009-07-30 14:48:31 +0000267 FixedArray* array = FixedArray::cast(last_match_info->elements());
kasperl@chromium.orga5551262010-12-07 12:49:48 +0000268 SetAtomLastCapture(array, *subject, index, index + needle_len);
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000269 }
270 return last_match_info;
kasperl@chromium.org41044eb2008-10-06 08:24:46 +0000271}
272
273
ager@chromium.org8bb60582008-12-11 12:02:20 +0000274// Irregexp implementation.
275
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000276// Ensures that the regexp object contains a compiled version of the
277// source for either ASCII or non-ASCII strings.
278// If the compiled version doesn't already exist, it is compiled
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +0000279// from the source pattern.
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000280// If compilation fails, an exception is thrown and this function
281// returns false.
ager@chromium.org41826e72009-03-30 13:30:57 +0000282bool RegExpImpl::EnsureCompiledIrregexp(Handle<JSRegExp> re, bool is_ascii) {
sgjesse@chromium.org911335c2009-08-19 12:59:44 +0000283 Object* compiled_code = re->DataAt(JSRegExp::code_index(is_ascii));
ricow@chromium.orgc9c80822010-04-21 08:22:37 +0000284#ifdef V8_INTERPRETED_REGEXP
sgjesse@chromium.org911335c2009-08-19 12:59:44 +0000285 if (compiled_code->IsByteArray()) return true;
ricow@chromium.orgc9c80822010-04-21 08:22:37 +0000286#else // V8_INTERPRETED_REGEXP (RegExp native code)
287 if (compiled_code->IsCode()) return true;
kasperl@chromium.org68ac0092009-07-09 06:00:35 +0000288#endif
jkummerow@chromium.orgddda9e82011-07-06 11:27:02 +0000289 // We could potentially have marked this as flushable, but have kept
290 // a saved version if we did not flush it yet.
291 Object* saved_code = re->DataAt(JSRegExp::saved_code_index(is_ascii));
292 if (saved_code->IsCode()) {
293 // Reinstate the code in the original place.
294 re->SetDataAt(JSRegExp::code_index(is_ascii), saved_code);
295 ASSERT(compiled_code->IsSmi());
296 return true;
297 }
kasperl@chromium.org68ac0092009-07-09 06:00:35 +0000298 return CompileIrregexp(re, is_ascii);
299}
ager@chromium.org8bb60582008-12-11 12:02:20 +0000300
kasperl@chromium.org68ac0092009-07-09 06:00:35 +0000301
jkummerow@chromium.orgddda9e82011-07-06 11:27:02 +0000302static bool CreateRegExpErrorObjectAndThrow(Handle<JSRegExp> re,
303 bool is_ascii,
304 Handle<String> error_message,
305 Isolate* isolate) {
306 Factory* factory = isolate->factory();
307 Handle<FixedArray> elements = factory->NewFixedArray(2);
308 elements->set(0, re->Pattern());
309 elements->set(1, *error_message);
310 Handle<JSArray> array = factory->NewJSArrayWithElements(elements);
311 Handle<Object> regexp_err =
312 factory->NewSyntaxError("malformed_regexp", array);
313 isolate->Throw(*regexp_err);
314 return false;
315}
316
317
kasperl@chromium.org68ac0092009-07-09 06:00:35 +0000318bool RegExpImpl::CompileIrregexp(Handle<JSRegExp> re, bool is_ascii) {
ager@chromium.org8bb60582008-12-11 12:02:20 +0000319 // Compile the RegExp.
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +0000320 Isolate* isolate = re->GetIsolate();
jkummerow@chromium.orge297f592011-06-08 10:05:15 +0000321 ZoneScope zone_scope(isolate, DELETE_ON_EXIT);
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +0000322 PostponeInterruptsScope postpone(isolate);
jkummerow@chromium.orgddda9e82011-07-06 11:27:02 +0000323 // If we had a compilation error the last time this is saved at the
324 // saved code index.
kasperl@chromium.org68ac0092009-07-09 06:00:35 +0000325 Object* entry = re->DataAt(JSRegExp::code_index(is_ascii));
jkummerow@chromium.orgddda9e82011-07-06 11:27:02 +0000326 // When arriving here entry can only be a smi, either representing an
327 // uncompiled regexp, a previous compilation error, or code that has
328 // been flushed.
329 ASSERT(entry->IsSmi());
330 int entry_value = Smi::cast(entry)->value();
331 ASSERT(entry_value == JSRegExp::kUninitializedValue ||
332 entry_value == JSRegExp::kCompilationErrorValue ||
333 (entry_value < JSRegExp::kCodeAgeMask && entry_value >= 0));
334
335 if (entry_value == JSRegExp::kCompilationErrorValue) {
336 // A previous compilation failed and threw an error which we store in
337 // the saved code index (we store the error message, not the actual
338 // error). Recreate the error object and throw it.
339 Object* error_string = re->DataAt(JSRegExp::saved_code_index(is_ascii));
340 ASSERT(error_string->IsString());
341 Handle<String> error_message(String::cast(error_string));
342 CreateRegExpErrorObjectAndThrow(re, is_ascii, error_message, isolate);
kasperl@chromium.org68ac0092009-07-09 06:00:35 +0000343 return false;
344 }
ager@chromium.org8bb60582008-12-11 12:02:20 +0000345
346 JSRegExp::Flags flags = re->GetFlags();
347
348 Handle<String> pattern(re->Pattern());
ricow@chromium.org4668a2c2011-08-29 10:41:00 +0000349 if (!pattern->IsFlat()) FlattenString(pattern);
ager@chromium.org8bb60582008-12-11 12:02:20 +0000350 RegExpCompileData compile_data;
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +0000351 FlatStringReader reader(isolate, pattern);
fschneider@chromium.orge03fb642010-11-01 12:34:09 +0000352 if (!RegExpParser::ParseRegExp(&reader, flags.is_multiline(),
353 &compile_data)) {
ager@chromium.org8bb60582008-12-11 12:02:20 +0000354 // Throw an exception if we fail to parse the pattern.
kasperl@chromium.org68ac0092009-07-09 06:00:35 +0000355 // THIS SHOULD NOT HAPPEN. We already pre-parsed it successfully once.
ager@chromium.org8bb60582008-12-11 12:02:20 +0000356 ThrowRegExpException(re,
357 pattern,
358 compile_data.error,
359 "malformed_regexp");
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000360 return false;
ager@chromium.org8bb60582008-12-11 12:02:20 +0000361 }
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000362 RegExpEngine::CompilationResult result =
ager@chromium.org8bb60582008-12-11 12:02:20 +0000363 RegExpEngine::Compile(&compile_data,
364 flags.is_ignore_case(),
365 flags.is_multiline(),
366 pattern,
367 is_ascii);
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000368 if (result.error_message != NULL) {
369 // Unable to compile regexp.
karlklose@chromium.org8f806e82011-03-07 14:06:08 +0000370 Handle<String> error_message =
jkummerow@chromium.orgddda9e82011-07-06 11:27:02 +0000371 isolate->factory()->NewStringFromUtf8(CStrVector(result.error_message));
372 CreateRegExpErrorObjectAndThrow(re, is_ascii, error_message, isolate);
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000373 return false;
ager@chromium.org8bb60582008-12-11 12:02:20 +0000374 }
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000375
kasperl@chromium.org68ac0092009-07-09 06:00:35 +0000376 Handle<FixedArray> data = Handle<FixedArray>(FixedArray::cast(re->data()));
377 data->set(JSRegExp::code_index(is_ascii), result.code);
378 int register_max = IrregexpMaxRegisterCount(*data);
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000379 if (result.num_registers > register_max) {
kasperl@chromium.org68ac0092009-07-09 06:00:35 +0000380 SetIrregexpMaxRegisterCount(*data, result.num_registers);
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000381 }
382
383 return true;
christian.plesner.hansen43d26ec2008-07-03 15:10:15 +0000384}
385
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000386
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000387int RegExpImpl::IrregexpMaxRegisterCount(FixedArray* re) {
388 return Smi::cast(
389 re->get(JSRegExp::kIrregexpMaxRegisterCountIndex))->value();
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000390}
391
392
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000393void RegExpImpl::SetIrregexpMaxRegisterCount(FixedArray* re, int value) {
394 re->set(JSRegExp::kIrregexpMaxRegisterCountIndex, Smi::FromInt(value));
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000395}
396
397
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000398int RegExpImpl::IrregexpNumberOfCaptures(FixedArray* re) {
399 return Smi::cast(re->get(JSRegExp::kIrregexpCaptureCountIndex))->value();
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000400}
401
402
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000403int RegExpImpl::IrregexpNumberOfRegisters(FixedArray* re) {
404 return Smi::cast(re->get(JSRegExp::kIrregexpMaxRegisterCountIndex))->value();
ager@chromium.org8bb60582008-12-11 12:02:20 +0000405}
406
407
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000408ByteArray* RegExpImpl::IrregexpByteCode(FixedArray* re, bool is_ascii) {
kasperl@chromium.org68ac0092009-07-09 06:00:35 +0000409 return ByteArray::cast(re->get(JSRegExp::code_index(is_ascii)));
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000410}
411
412
413Code* RegExpImpl::IrregexpNativeCode(FixedArray* re, bool is_ascii) {
kasperl@chromium.org68ac0092009-07-09 06:00:35 +0000414 return Code::cast(re->get(JSRegExp::code_index(is_ascii)));
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000415}
416
417
whesse@chromium.orgcec079d2010-03-22 14:44:04 +0000418void RegExpImpl::IrregexpInitialize(Handle<JSRegExp> re,
419 Handle<String> pattern,
420 JSRegExp::Flags flags,
421 int capture_count) {
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000422 // Initialize compiled code entries to null.
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +0000423 re->GetIsolate()->factory()->SetRegExpIrregexpData(re,
424 JSRegExp::IRREGEXP,
425 pattern,
426 flags,
427 capture_count);
ager@chromium.org8bb60582008-12-11 12:02:20 +0000428}
429
430
whesse@chromium.orgcec079d2010-03-22 14:44:04 +0000431int RegExpImpl::IrregexpPrepare(Handle<JSRegExp> regexp,
432 Handle<String> subject) {
ricow@chromium.org4668a2c2011-08-29 10:41:00 +0000433 if (!subject->IsFlat()) FlattenString(subject);
434
lrn@chromium.org32d961d2010-06-30 09:09:34 +0000435 // Check the asciiness of the underlying storage.
ricow@chromium.org4668a2c2011-08-29 10:41:00 +0000436 bool is_ascii = subject->IsAsciiRepresentationUnderneath();
437 if (!EnsureCompiledIrregexp(regexp, is_ascii)) return -1;
438
ricow@chromium.orgc9c80822010-04-21 08:22:37 +0000439#ifdef V8_INTERPRETED_REGEXP
440 // Byte-code regexp needs space allocated for all its registers.
441 return IrregexpNumberOfRegisters(FixedArray::cast(regexp->data()));
442#else // V8_INTERPRETED_REGEXP
whesse@chromium.orgcec079d2010-03-22 14:44:04 +0000443 // Native regexp only needs room to output captures. Registers are handled
444 // internally.
445 return (IrregexpNumberOfCaptures(FixedArray::cast(regexp->data())) + 1) * 2;
ricow@chromium.orgc9c80822010-04-21 08:22:37 +0000446#endif // V8_INTERPRETED_REGEXP
whesse@chromium.orgcec079d2010-03-22 14:44:04 +0000447}
448
449
erik.corry@gmail.com145eff52010-08-23 11:36:18 +0000450RegExpImpl::IrregexpResult RegExpImpl::IrregexpExecOnce(
451 Handle<JSRegExp> regexp,
452 Handle<String> subject,
453 int index,
sgjesse@chromium.orgc6c57182011-01-17 12:24:25 +0000454 Vector<int> output) {
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +0000455 Isolate* isolate = regexp->GetIsolate();
456
457 Handle<FixedArray> irregexp(FixedArray::cast(regexp->data()), isolate);
whesse@chromium.orgcec079d2010-03-22 14:44:04 +0000458
459 ASSERT(index >= 0);
460 ASSERT(index <= subject->length());
461 ASSERT(subject->IsFlat());
462
ricow@chromium.org4668a2c2011-08-29 10:41:00 +0000463 bool is_ascii = subject->IsAsciiRepresentationUnderneath();
lrn@chromium.org32d961d2010-06-30 09:09:34 +0000464
ricow@chromium.orgc9c80822010-04-21 08:22:37 +0000465#ifndef V8_INTERPRETED_REGEXP
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +0000466 ASSERT(output.length() >= (IrregexpNumberOfCaptures(*irregexp) + 1) * 2);
whesse@chromium.orgcec079d2010-03-22 14:44:04 +0000467 do {
sgjesse@chromium.org6db88712011-07-11 11:41:22 +0000468 EnsureCompiledIrregexp(regexp, is_ascii);
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +0000469 Handle<Code> code(IrregexpNativeCode(*irregexp, is_ascii), isolate);
whesse@chromium.orgcec079d2010-03-22 14:44:04 +0000470 NativeRegExpMacroAssembler::Result res =
471 NativeRegExpMacroAssembler::Match(code,
472 subject,
473 output.start(),
474 output.length(),
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +0000475 index,
476 isolate);
whesse@chromium.orgcec079d2010-03-22 14:44:04 +0000477 if (res != NativeRegExpMacroAssembler::RETRY) {
478 ASSERT(res != NativeRegExpMacroAssembler::EXCEPTION ||
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +0000479 isolate->has_pending_exception());
whesse@chromium.orgcec079d2010-03-22 14:44:04 +0000480 STATIC_ASSERT(
481 static_cast<int>(NativeRegExpMacroAssembler::SUCCESS) == RE_SUCCESS);
482 STATIC_ASSERT(
483 static_cast<int>(NativeRegExpMacroAssembler::FAILURE) == RE_FAILURE);
484 STATIC_ASSERT(static_cast<int>(NativeRegExpMacroAssembler::EXCEPTION)
485 == RE_EXCEPTION);
486 return static_cast<IrregexpResult>(res);
487 }
488 // If result is RETRY, the string has changed representation, and we
489 // must restart from scratch.
490 // In this case, it means we must make sure we are prepared to handle
lrn@chromium.org32d961d2010-06-30 09:09:34 +0000491 // the, potentially, different subject (the string can switch between
whesse@chromium.orgcec079d2010-03-22 14:44:04 +0000492 // being internal and external, and even between being ASCII and UC16,
493 // but the characters are always the same).
494 IrregexpPrepare(regexp, subject);
ricow@chromium.org4668a2c2011-08-29 10:41:00 +0000495 is_ascii = subject->IsAsciiRepresentationUnderneath();
whesse@chromium.orgcec079d2010-03-22 14:44:04 +0000496 } while (true);
497 UNREACHABLE();
498 return RE_EXCEPTION;
ricow@chromium.orgc9c80822010-04-21 08:22:37 +0000499#else // V8_INTERPRETED_REGEXP
whesse@chromium.orgcec079d2010-03-22 14:44:04 +0000500
501 ASSERT(output.length() >= IrregexpNumberOfRegisters(*irregexp));
whesse@chromium.orgcec079d2010-03-22 14:44:04 +0000502 // We must have done EnsureCompiledIrregexp, so we can get the number of
503 // registers.
504 int* register_vector = output.start();
505 int number_of_capture_registers =
506 (IrregexpNumberOfCaptures(*irregexp) + 1) * 2;
507 for (int i = number_of_capture_registers - 1; i >= 0; i--) {
508 register_vector[i] = -1;
509 }
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +0000510 Handle<ByteArray> byte_codes(IrregexpByteCode(*irregexp, is_ascii), isolate);
whesse@chromium.orgcec079d2010-03-22 14:44:04 +0000511
fschneider@chromium.org7979bbb2011-03-28 10:47:03 +0000512 if (IrregexpInterpreter::Match(isolate,
513 byte_codes,
whesse@chromium.orgcec079d2010-03-22 14:44:04 +0000514 subject,
515 register_vector,
516 index)) {
517 return RE_SUCCESS;
518 }
519 return RE_FAILURE;
ricow@chromium.orgc9c80822010-04-21 08:22:37 +0000520#endif // V8_INTERPRETED_REGEXP
whesse@chromium.orgcec079d2010-03-22 14:44:04 +0000521}
522
523
ager@chromium.org41826e72009-03-30 13:30:57 +0000524Handle<Object> RegExpImpl::IrregexpExec(Handle<JSRegExp> jsregexp,
ager@chromium.org8bb60582008-12-11 12:02:20 +0000525 Handle<String> subject,
ager@chromium.org41826e72009-03-30 13:30:57 +0000526 int previous_index,
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000527 Handle<JSArray> last_match_info) {
ager@chromium.org41826e72009-03-30 13:30:57 +0000528 ASSERT_EQ(jsregexp->TypeTag(), JSRegExp::IRREGEXP);
ager@chromium.org8bb60582008-12-11 12:02:20 +0000529
ager@chromium.org8bb60582008-12-11 12:02:20 +0000530 // Prepare space for the return values.
ricow@chromium.orgc9c80822010-04-21 08:22:37 +0000531#ifdef V8_INTERPRETED_REGEXP
ager@chromium.org8bb60582008-12-11 12:02:20 +0000532#ifdef DEBUG
533 if (FLAG_trace_regexp_bytecodes) {
ager@chromium.org41826e72009-03-30 13:30:57 +0000534 String* pattern = jsregexp->Pattern();
ager@chromium.org8bb60582008-12-11 12:02:20 +0000535 PrintF("\n\nRegexp match: /%s/\n\n", *(pattern->ToCString()));
536 PrintF("\n\nSubject string: '%s'\n\n", *(subject->ToCString()));
537 }
538#endif
kasperl@chromium.org68ac0092009-07-09 06:00:35 +0000539#endif
whesse@chromium.orgcec079d2010-03-22 14:44:04 +0000540 int required_registers = RegExpImpl::IrregexpPrepare(jsregexp, subject);
541 if (required_registers < 0) {
542 // Compiling failed with an exception.
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +0000543 ASSERT(Isolate::Current()->has_pending_exception());
kasperl@chromium.org68ac0092009-07-09 06:00:35 +0000544 return Handle<Object>::null();
545 }
ager@chromium.org8bb60582008-12-11 12:02:20 +0000546
whesse@chromium.orgcec079d2010-03-22 14:44:04 +0000547 OffsetsVector registers(required_registers);
ager@chromium.org5aa501c2009-06-23 07:57:28 +0000548
ricow@chromium.org0b9f8502010-08-18 07:45:01 +0000549 IrregexpResult res = RegExpImpl::IrregexpExecOnce(
sgjesse@chromium.orgc6c57182011-01-17 12:24:25 +0000550 jsregexp, subject, previous_index, Vector<int>(registers.vector(),
551 registers.length()));
whesse@chromium.orgcec079d2010-03-22 14:44:04 +0000552 if (res == RE_SUCCESS) {
553 int capture_register_count =
554 (IrregexpNumberOfCaptures(FixedArray::cast(jsregexp->data())) + 1) * 2;
555 last_match_info->EnsureSize(capture_register_count + kLastMatchOverhead);
556 AssertNoAllocation no_gc;
557 int* register_vector = registers.vector();
558 FixedArray* array = FixedArray::cast(last_match_info->elements());
559 for (int i = 0; i < capture_register_count; i += 2) {
560 SetCapture(array, i, register_vector[i]);
561 SetCapture(array, i + 1, register_vector[i + 1]);
fschneider@chromium.org0c20e672010-01-14 15:28:53 +0000562 }
whesse@chromium.orgcec079d2010-03-22 14:44:04 +0000563 SetLastCaptureCount(array, capture_register_count);
564 SetLastSubject(array, *subject);
565 SetLastInput(array, *subject);
566 return last_match_info;
kasperl@chromium.org68ac0092009-07-09 06:00:35 +0000567 }
whesse@chromium.orgcec079d2010-03-22 14:44:04 +0000568 if (res == RE_EXCEPTION) {
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +0000569 ASSERT(Isolate::Current()->has_pending_exception());
kasperl@chromium.org68ac0092009-07-09 06:00:35 +0000570 return Handle<Object>::null();
571 }
whesse@chromium.orgcec079d2010-03-22 14:44:04 +0000572 ASSERT(res == RE_FAILURE);
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +0000573 return Isolate::Current()->factory()->null_value();
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000574}
575
576
577// -------------------------------------------------------------------
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000578// Implementation of the Irregexp regular expression engine.
ager@chromium.org8bb60582008-12-11 12:02:20 +0000579//
580// The Irregexp regular expression engine is intended to be a complete
581// implementation of ECMAScript regular expressions. It generates either
582// bytecodes or native code.
583
584// The Irregexp regexp engine is structured in three steps.
585// 1) The parser generates an abstract syntax tree. See ast.cc.
586// 2) From the AST a node network is created. The nodes are all
587// subclasses of RegExpNode. The nodes represent states when
588// executing a regular expression. Several optimizations are
589// performed on the node network.
590// 3) From the nodes we generate either byte codes or native code
591// that can actually execute the regular expression (perform
592// the search). The code generation step is described in more
593// detail below.
594
595// Code generation.
596//
597// The nodes are divided into four main categories.
598// * Choice nodes
599// These represent places where the regular expression can
600// match in more than one way. For example on entry to an
601// alternation (foo|bar) or a repetition (*, +, ? or {}).
602// * Action nodes
603// These represent places where some action should be
604// performed. Examples include recording the current position
605// in the input string to a register (in order to implement
606// captures) or other actions on register for example in order
607// to implement the counters needed for {} repetitions.
608// * Matching nodes
609// These attempt to match some element part of the input string.
610// Examples of elements include character classes, plain strings
611// or back references.
612// * End nodes
613// These are used to implement the actions required on finding
614// a successful match or failing to find a match.
615//
616// The code generated (whether as byte codes or native code) maintains
617// some state as it runs. This consists of the following elements:
618//
619// * The capture registers. Used for string captures.
620// * Other registers. Used for counters etc.
621// * The current position.
622// * The stack of backtracking information. Used when a matching node
623// fails to find a match and needs to try an alternative.
624//
625// Conceptual regular expression execution model:
626//
627// There is a simple conceptual model of regular expression execution
628// which will be presented first. The actual code generated is a more
629// efficient simulation of the simple conceptual model:
630//
631// * Choice nodes are implemented as follows:
632// For each choice except the last {
633// push current position
634// push backtrack code location
635// <generate code to test for choice>
636// backtrack code location:
637// pop current position
638// }
639// <generate code to test for last choice>
640//
641// * Actions nodes are generated as follows
642// <push affected registers on backtrack stack>
643// <generate code to perform action>
644// push backtrack code location
645// <generate code to test for following nodes>
646// backtrack code location:
647// <pop affected registers to restore their state>
648// <pop backtrack location from stack and go to it>
649//
650// * Matching nodes are generated as follows:
651// if input string matches at current position
652// update current position
653// <generate code to test for following nodes>
654// else
655// <pop backtrack location from stack and go to it>
656//
657// Thus it can be seen that the current position is saved and restored
658// by the choice nodes, whereas the registers are saved and restored by
659// by the action nodes that manipulate them.
660//
661// The other interesting aspect of this model is that nodes are generated
662// at the point where they are needed by a recursive call to Emit(). If
663// the node has already been code generated then the Emit() call will
664// generate a jump to the previously generated code instead. In order to
665// limit recursion it is possible for the Emit() function to put the node
666// on a work list for later generation and instead generate a jump. The
667// destination of the jump is resolved later when the code is generated.
668//
669// Actual regular expression code generation.
670//
671// Code generation is actually more complicated than the above. In order
672// to improve the efficiency of the generated code some optimizations are
673// performed
674//
675// * Choice nodes have 1-character lookahead.
676// A choice node looks at the following character and eliminates some of
677// the choices immediately based on that character. This is not yet
678// implemented.
679// * Simple greedy loops store reduced backtracking information.
680// A quantifier like /.*foo/m will greedily match the whole input. It will
681// then need to backtrack to a point where it can match "foo". The naive
682// implementation of this would push each character position onto the
683// backtracking stack, then pop them off one by one. This would use space
684// proportional to the length of the input string. However since the "."
685// can only match in one way and always has a constant length (in this case
686// of 1) it suffices to store the current position on the top of the stack
687// once. Matching now becomes merely incrementing the current position and
688// backtracking becomes decrementing the current position and checking the
689// result against the stored current position. This is faster and saves
690// space.
691// * The current state is virtualized.
692// This is used to defer expensive operations until it is clear that they
693// are needed and to generate code for a node more than once, allowing
694// specialized an efficient versions of the code to be created. This is
695// explained in the section below.
696//
697// Execution state virtualization.
698//
699// Instead of emitting code, nodes that manipulate the state can record their
ager@chromium.org32912102009-01-16 10:38:43 +0000700// manipulation in an object called the Trace. The Trace object can record a
701// current position offset, an optional backtrack code location on the top of
702// the virtualized backtrack stack and some register changes. When a node is
703// to be emitted it can flush the Trace or update it. Flushing the Trace
ager@chromium.org8bb60582008-12-11 12:02:20 +0000704// will emit code to bring the actual state into line with the virtual state.
705// Avoiding flushing the state can postpone some work (eg updates of capture
706// registers). Postponing work can save time when executing the regular
707// expression since it may be found that the work never has to be done as a
708// failure to match can occur. In addition it is much faster to jump to a
709// known backtrack code location than it is to pop an unknown backtrack
710// location from the stack and jump there.
711//
ager@chromium.org32912102009-01-16 10:38:43 +0000712// The virtual state found in the Trace affects code generation. For example
713// the virtual state contains the difference between the actual current
714// position and the virtual current position, and matching code needs to use
715// this offset to attempt a match in the correct location of the input
716// string. Therefore code generated for a non-trivial trace is specialized
717// to that trace. The code generator therefore has the ability to generate
718// code for each node several times. In order to limit the size of the
719// generated code there is an arbitrary limit on how many specialized sets of
720// code may be generated for a given node. If the limit is reached, the
721// trace is flushed and a generic version of the code for a node is emitted.
722// This is subsequently used for that node. The code emitted for non-generic
723// trace is not recorded in the node and so it cannot currently be reused in
724// the event that code generation is requested for an identical trace.
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000725
726
727void RegExpTree::AppendToText(RegExpText* text) {
728 UNREACHABLE();
729}
730
731
732void RegExpAtom::AppendToText(RegExpText* text) {
733 text->AddElement(TextElement::Atom(this));
734}
735
736
737void RegExpCharacterClass::AppendToText(RegExpText* text) {
738 text->AddElement(TextElement::CharClass(this));
739}
740
741
742void RegExpText::AppendToText(RegExpText* text) {
743 for (int i = 0; i < elements()->length(); i++)
744 text->AddElement(elements()->at(i));
745}
746
747
748TextElement TextElement::Atom(RegExpAtom* atom) {
749 TextElement result = TextElement(ATOM);
750 result.data.u_atom = atom;
751 return result;
752}
753
754
755TextElement TextElement::CharClass(
756 RegExpCharacterClass* char_class) {
757 TextElement result = TextElement(CHAR_CLASS);
758 result.data.u_char_class = char_class;
759 return result;
760}
761
762
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +0000763int TextElement::length() {
764 if (type == ATOM) {
765 return data.u_atom->length();
766 } else {
767 ASSERT(type == CHAR_CLASS);
768 return 1;
769 }
770}
771
772
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000773DispatchTable* ChoiceNode::GetTable(bool ignore_case) {
774 if (table_ == NULL) {
775 table_ = new DispatchTable();
776 DispatchTableConstructor cons(table_, ignore_case);
777 cons.BuildTable(this);
778 }
779 return table_;
780}
781
782
783class RegExpCompiler {
784 public:
ager@chromium.org8bb60582008-12-11 12:02:20 +0000785 RegExpCompiler(int capture_count, bool ignore_case, bool is_ascii);
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000786
ager@chromium.orgddb913d2009-01-27 10:01:48 +0000787 int AllocateRegister() {
788 if (next_register_ >= RegExpMacroAssembler::kMaxRegister) {
789 reg_exp_too_big_ = true;
790 return next_register_;
791 }
792 return next_register_++;
793 }
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000794
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000795 RegExpEngine::CompilationResult Assemble(RegExpMacroAssembler* assembler,
796 RegExpNode* start,
797 int capture_count,
798 Handle<String> pattern);
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000799
800 inline void AddWork(RegExpNode* node) { work_list_->Add(node); }
801
802 static const int kImplementationOffset = 0;
803 static const int kNumberOfRegistersOffset = 0;
804 static const int kCodeOffset = 1;
805
806 RegExpMacroAssembler* macro_assembler() { return macro_assembler_; }
807 EndNode* accept() { return accept_; }
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000808
809 static const int kMaxRecursion = 100;
810 inline int recursion_depth() { return recursion_depth_; }
811 inline void IncrementRecursionDepth() { recursion_depth_++; }
812 inline void DecrementRecursionDepth() { recursion_depth_--; }
813
ager@chromium.orgddb913d2009-01-27 10:01:48 +0000814 void SetRegExpTooBig() { reg_exp_too_big_ = true; }
815
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000816 inline bool ignore_case() { return ignore_case_; }
ager@chromium.org8bb60582008-12-11 12:02:20 +0000817 inline bool ascii() { return ascii_; }
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000818
whesse@chromium.org7b260152011-06-20 15:33:18 +0000819 int current_expansion_factor() { return current_expansion_factor_; }
820 void set_current_expansion_factor(int value) {
821 current_expansion_factor_ = value;
822 }
823
ager@chromium.org32912102009-01-16 10:38:43 +0000824 static const int kNoRegister = -1;
jkummerow@chromium.orge297f592011-06-08 10:05:15 +0000825
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000826 private:
827 EndNode* accept_;
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000828 int next_register_;
829 List<RegExpNode*>* work_list_;
830 int recursion_depth_;
831 RegExpMacroAssembler* macro_assembler_;
832 bool ignore_case_;
ager@chromium.org8bb60582008-12-11 12:02:20 +0000833 bool ascii_;
ager@chromium.orgddb913d2009-01-27 10:01:48 +0000834 bool reg_exp_too_big_;
whesse@chromium.org7b260152011-06-20 15:33:18 +0000835 int current_expansion_factor_;
ager@chromium.org8bb60582008-12-11 12:02:20 +0000836};
837
838
839class RecursionCheck {
840 public:
841 explicit RecursionCheck(RegExpCompiler* compiler) : compiler_(compiler) {
842 compiler->IncrementRecursionDepth();
843 }
844 ~RecursionCheck() { compiler_->DecrementRecursionDepth(); }
845 private:
846 RegExpCompiler* compiler_;
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000847};
848
849
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000850static RegExpEngine::CompilationResult IrregexpRegExpTooBig() {
851 return RegExpEngine::CompilationResult("RegExp too big");
ager@chromium.orgddb913d2009-01-27 10:01:48 +0000852}
853
854
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000855// Attempts to compile the regexp using an Irregexp code generator. Returns
856// a fixed array or a null handle depending on whether it succeeded.
ager@chromium.org8bb60582008-12-11 12:02:20 +0000857RegExpCompiler::RegExpCompiler(int capture_count, bool ignore_case, bool ascii)
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000858 : next_register_(2 * (capture_count + 1)),
859 work_list_(NULL),
860 recursion_depth_(0),
ager@chromium.org8bb60582008-12-11 12:02:20 +0000861 ignore_case_(ignore_case),
ager@chromium.orgddb913d2009-01-27 10:01:48 +0000862 ascii_(ascii),
whesse@chromium.org7b260152011-06-20 15:33:18 +0000863 reg_exp_too_big_(false),
864 current_expansion_factor_(1) {
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000865 accept_ = new EndNode(EndNode::ACCEPT);
ager@chromium.orgddb913d2009-01-27 10:01:48 +0000866 ASSERT(next_register_ - 1 <= RegExpMacroAssembler::kMaxRegister);
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000867}
868
869
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000870RegExpEngine::CompilationResult RegExpCompiler::Assemble(
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000871 RegExpMacroAssembler* macro_assembler,
872 RegExpNode* start,
ager@chromium.org8bb60582008-12-11 12:02:20 +0000873 int capture_count,
874 Handle<String> pattern) {
karlklose@chromium.org83a47282011-05-11 11:54:09 +0000875 Heap* heap = pattern->GetHeap();
876
877 bool use_slow_safe_regexp_compiler = false;
878 if (heap->total_regexp_code_generated() >
879 RegExpImpl::kRegWxpCompiledLimit &&
880 heap->isolate()->memory_allocator()->SizeExecutable() >
881 RegExpImpl::kRegExpExecutableMemoryLimit) {
882 use_slow_safe_regexp_compiler = true;
883 }
884
885 macro_assembler->set_slow_safe(use_slow_safe_regexp_compiler);
886
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000887#ifdef DEBUG
888 if (FLAG_trace_regexp_assembler)
889 macro_assembler_ = new RegExpMacroAssemblerTracer(macro_assembler);
890 else
891#endif
892 macro_assembler_ = macro_assembler;
karlklose@chromium.org83a47282011-05-11 11:54:09 +0000893
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000894 List <RegExpNode*> work_list(0);
895 work_list_ = &work_list;
896 Label fail;
iposva@chromium.org245aa852009-02-10 00:49:54 +0000897 macro_assembler_->PushBacktrack(&fail);
ager@chromium.org32912102009-01-16 10:38:43 +0000898 Trace new_trace;
ager@chromium.orgddb913d2009-01-27 10:01:48 +0000899 start->Emit(this, &new_trace);
ager@chromium.org8bb60582008-12-11 12:02:20 +0000900 macro_assembler_->Bind(&fail);
901 macro_assembler_->Fail();
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000902 while (!work_list.is_empty()) {
ager@chromium.orgddb913d2009-01-27 10:01:48 +0000903 work_list.RemoveLast()->Emit(this, &new_trace);
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000904 }
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000905 if (reg_exp_too_big_) return IrregexpRegExpTooBig();
906
karlklose@chromium.org83a47282011-05-11 11:54:09 +0000907 Handle<HeapObject> code = macro_assembler_->GetCode(pattern);
908 heap->IncreaseTotalRegexpCodeGenerated(code->Size());
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000909 work_list_ = NULL;
910#ifdef DEBUG
danno@chromium.org4d3fe4e2011-03-10 10:14:28 +0000911 if (FLAG_print_code) {
912 Handle<Code>::cast(code)->Disassemble(*pattern->ToCString());
913 }
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000914 if (FLAG_trace_regexp_assembler) {
915 delete macro_assembler_;
916 }
917#endif
kasperl@chromium.org7be3c992009-03-12 07:19:55 +0000918 return RegExpEngine::CompilationResult(*code, next_register_);
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000919}
920
ager@chromium.orgddb913d2009-01-27 10:01:48 +0000921
ager@chromium.org32912102009-01-16 10:38:43 +0000922bool Trace::DeferredAction::Mentions(int that) {
923 if (type() == ActionNode::CLEAR_CAPTURES) {
924 Interval range = static_cast<DeferredClearCaptures*>(this)->range();
925 return range.Contains(that);
926 } else {
927 return reg() == that;
928 }
929}
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000930
ager@chromium.org32912102009-01-16 10:38:43 +0000931
932bool Trace::mentions_reg(int reg) {
ager@chromium.org8bb60582008-12-11 12:02:20 +0000933 for (DeferredAction* action = actions_;
934 action != NULL;
935 action = action->next()) {
ager@chromium.org32912102009-01-16 10:38:43 +0000936 if (action->Mentions(reg))
937 return true;
ager@chromium.orga74f0da2008-12-03 16:05:52 +0000938 }
ager@chromium.org8bb60582008-12-11 12:02:20 +0000939 return false;
940}
941
942
ager@chromium.org32912102009-01-16 10:38:43 +0000943bool Trace::GetStoredPosition(int reg, int* cp_offset) {
944 ASSERT_EQ(0, *cp_offset);
ager@chromium.org8bb60582008-12-11 12:02:20 +0000945 for (DeferredAction* action = actions_;
946 action != NULL;
947 action = action->next()) {
ager@chromium.org32912102009-01-16 10:38:43 +0000948 if (action->Mentions(reg)) {
949 if (action->type() == ActionNode::STORE_POSITION) {
950 *cp_offset = static_cast<DeferredCapture*>(action)->cp_offset();
951 return true;
952 } else {
953 return false;
954 }
955 }
956 }
957 return false;
958}
959
960
961int Trace::FindAffectedRegisters(OutSet* affected_registers) {
962 int max_register = RegExpCompiler::kNoRegister;
963 for (DeferredAction* action = actions_;
964 action != NULL;
965 action = action->next()) {
966 if (action->type() == ActionNode::CLEAR_CAPTURES) {
967 Interval range = static_cast<DeferredClearCaptures*>(action)->range();
968 for (int i = range.from(); i <= range.to(); i++)
969 affected_registers->Set(i);
970 if (range.to() > max_register) max_register = range.to();
971 } else {
972 affected_registers->Set(action->reg());
973 if (action->reg() > max_register) max_register = action->reg();
974 }
ager@chromium.org8bb60582008-12-11 12:02:20 +0000975 }
976 return max_register;
977}
978
979
ager@chromium.org32912102009-01-16 10:38:43 +0000980void Trace::RestoreAffectedRegisters(RegExpMacroAssembler* assembler,
981 int max_register,
ager@chromium.orgddb913d2009-01-27 10:01:48 +0000982 OutSet& registers_to_pop,
983 OutSet& registers_to_clear) {
ager@chromium.org8bb60582008-12-11 12:02:20 +0000984 for (int reg = max_register; reg >= 0; reg--) {
ager@chromium.orgddb913d2009-01-27 10:01:48 +0000985 if (registers_to_pop.Get(reg)) assembler->PopRegister(reg);
986 else if (registers_to_clear.Get(reg)) {
987 int clear_to = reg;
988 while (reg > 0 && registers_to_clear.Get(reg - 1)) {
989 reg--;
990 }
991 assembler->ClearRegisters(reg, clear_to);
992 }
ager@chromium.org8bb60582008-12-11 12:02:20 +0000993 }
994}
995
996
ager@chromium.org32912102009-01-16 10:38:43 +0000997void Trace::PerformDeferredActions(RegExpMacroAssembler* assembler,
998 int max_register,
ager@chromium.orgddb913d2009-01-27 10:01:48 +0000999 OutSet& affected_registers,
1000 OutSet* registers_to_pop,
1001 OutSet* registers_to_clear) {
1002 // The "+1" is to avoid a push_limit of zero if stack_limit_slack() is 1.
1003 const int push_limit = (assembler->stack_limit_slack() + 1) / 2;
1004
ager@chromium.org5aa501c2009-06-23 07:57:28 +00001005 // Count pushes performed to force a stack limit check occasionally.
1006 int pushes = 0;
1007
ager@chromium.org8bb60582008-12-11 12:02:20 +00001008 for (int reg = 0; reg <= max_register; reg++) {
1009 if (!affected_registers.Get(reg)) {
1010 continue;
1011 }
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001012
1013 // The chronologically first deferred action in the trace
1014 // is used to infer the action needed to restore a register
1015 // to its previous state (or not, if it's safe to ignore it).
1016 enum DeferredActionUndoType { IGNORE, RESTORE, CLEAR };
1017 DeferredActionUndoType undo_action = IGNORE;
1018
ager@chromium.org8bb60582008-12-11 12:02:20 +00001019 int value = 0;
1020 bool absolute = false;
ager@chromium.org32912102009-01-16 10:38:43 +00001021 bool clear = false;
ager@chromium.org8bb60582008-12-11 12:02:20 +00001022 int store_position = -1;
1023 // This is a little tricky because we are scanning the actions in reverse
1024 // historical order (newest first).
1025 for (DeferredAction* action = actions_;
1026 action != NULL;
1027 action = action->next()) {
ager@chromium.org32912102009-01-16 10:38:43 +00001028 if (action->Mentions(reg)) {
ager@chromium.org8bb60582008-12-11 12:02:20 +00001029 switch (action->type()) {
1030 case ActionNode::SET_REGISTER: {
ager@chromium.org32912102009-01-16 10:38:43 +00001031 Trace::DeferredSetRegister* psr =
1032 static_cast<Trace::DeferredSetRegister*>(action);
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001033 if (!absolute) {
1034 value += psr->value();
1035 absolute = true;
1036 }
1037 // SET_REGISTER is currently only used for newly introduced loop
1038 // counters. They can have a significant previous value if they
1039 // occour in a loop. TODO(lrn): Propagate this information, so
1040 // we can set undo_action to IGNORE if we know there is no value to
1041 // restore.
1042 undo_action = RESTORE;
ager@chromium.org8bb60582008-12-11 12:02:20 +00001043 ASSERT_EQ(store_position, -1);
ager@chromium.org32912102009-01-16 10:38:43 +00001044 ASSERT(!clear);
ager@chromium.org8bb60582008-12-11 12:02:20 +00001045 break;
1046 }
1047 case ActionNode::INCREMENT_REGISTER:
1048 if (!absolute) {
1049 value++;
1050 }
1051 ASSERT_EQ(store_position, -1);
ager@chromium.org32912102009-01-16 10:38:43 +00001052 ASSERT(!clear);
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001053 undo_action = RESTORE;
ager@chromium.org8bb60582008-12-11 12:02:20 +00001054 break;
1055 case ActionNode::STORE_POSITION: {
ager@chromium.org32912102009-01-16 10:38:43 +00001056 Trace::DeferredCapture* pc =
1057 static_cast<Trace::DeferredCapture*>(action);
1058 if (!clear && store_position == -1) {
ager@chromium.org8bb60582008-12-11 12:02:20 +00001059 store_position = pc->cp_offset();
1060 }
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001061
1062 // For captures we know that stores and clears alternate.
1063 // Other register, are never cleared, and if the occur
1064 // inside a loop, they might be assigned more than once.
1065 if (reg <= 1) {
1066 // Registers zero and one, aka "capture zero", is
1067 // always set correctly if we succeed. There is no
1068 // need to undo a setting on backtrack, because we
1069 // will set it again or fail.
1070 undo_action = IGNORE;
1071 } else {
1072 undo_action = pc->is_capture() ? CLEAR : RESTORE;
1073 }
ager@chromium.org8bb60582008-12-11 12:02:20 +00001074 ASSERT(!absolute);
1075 ASSERT_EQ(value, 0);
1076 break;
1077 }
ager@chromium.org32912102009-01-16 10:38:43 +00001078 case ActionNode::CLEAR_CAPTURES: {
1079 // Since we're scanning in reverse order, if we've already
1080 // set the position we have to ignore historically earlier
1081 // clearing operations.
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001082 if (store_position == -1) {
ager@chromium.org32912102009-01-16 10:38:43 +00001083 clear = true;
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001084 }
1085 undo_action = RESTORE;
ager@chromium.org32912102009-01-16 10:38:43 +00001086 ASSERT(!absolute);
1087 ASSERT_EQ(value, 0);
1088 break;
1089 }
ager@chromium.org8bb60582008-12-11 12:02:20 +00001090 default:
1091 UNREACHABLE();
1092 break;
1093 }
1094 }
1095 }
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001096 // Prepare for the undo-action (e.g., push if it's going to be popped).
1097 if (undo_action == RESTORE) {
1098 pushes++;
1099 RegExpMacroAssembler::StackCheckFlag stack_check =
1100 RegExpMacroAssembler::kNoStackLimitCheck;
1101 if (pushes == push_limit) {
1102 stack_check = RegExpMacroAssembler::kCheckStackLimit;
1103 pushes = 0;
1104 }
1105
1106 assembler->PushRegister(reg, stack_check);
1107 registers_to_pop->Set(reg);
1108 } else if (undo_action == CLEAR) {
1109 registers_to_clear->Set(reg);
1110 }
1111 // Perform the chronologically last action (or accumulated increment)
1112 // for the register.
ager@chromium.org8bb60582008-12-11 12:02:20 +00001113 if (store_position != -1) {
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001114 assembler->WriteCurrentPositionToRegister(reg, store_position);
ager@chromium.org32912102009-01-16 10:38:43 +00001115 } else if (clear) {
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001116 assembler->ClearRegisters(reg, reg);
ager@chromium.org32912102009-01-16 10:38:43 +00001117 } else if (absolute) {
1118 assembler->SetRegister(reg, value);
1119 } else if (value != 0) {
1120 assembler->AdvanceRegister(reg, value);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001121 }
1122 }
1123}
1124
1125
ager@chromium.org8bb60582008-12-11 12:02:20 +00001126// This is called as we come into a loop choice node and some other tricky
ager@chromium.org32912102009-01-16 10:38:43 +00001127// nodes. It normalizes the state of the code generator to ensure we can
ager@chromium.org8bb60582008-12-11 12:02:20 +00001128// generate generic code.
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001129void Trace::Flush(RegExpCompiler* compiler, RegExpNode* successor) {
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001130 RegExpMacroAssembler* assembler = compiler->macro_assembler();
ager@chromium.org8bb60582008-12-11 12:02:20 +00001131
iposva@chromium.org245aa852009-02-10 00:49:54 +00001132 ASSERT(!is_trivial());
ager@chromium.org8bb60582008-12-11 12:02:20 +00001133
1134 if (actions_ == NULL && backtrack() == NULL) {
1135 // Here we just have some deferred cp advances to fix and we are back to
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001136 // a normal situation. We may also have to forget some information gained
1137 // through a quick check that was already performed.
1138 if (cp_offset_ != 0) assembler->AdvanceCurrentPosition(cp_offset_);
ager@chromium.org8bb60582008-12-11 12:02:20 +00001139 // Create a new trivial state and generate the node with that.
ager@chromium.org32912102009-01-16 10:38:43 +00001140 Trace new_state;
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001141 successor->Emit(compiler, &new_state);
1142 return;
ager@chromium.org8bb60582008-12-11 12:02:20 +00001143 }
1144
1145 // Generate deferred actions here along with code to undo them again.
1146 OutSet affected_registers;
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001147
ager@chromium.org381abbb2009-02-25 13:23:22 +00001148 if (backtrack() != NULL) {
1149 // Here we have a concrete backtrack location. These are set up by choice
1150 // nodes and so they indicate that we have a deferred save of the current
1151 // position which we may need to emit here.
1152 assembler->PushCurrentPosition();
1153 }
1154
ager@chromium.org8bb60582008-12-11 12:02:20 +00001155 int max_register = FindAffectedRegisters(&affected_registers);
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001156 OutSet registers_to_pop;
1157 OutSet registers_to_clear;
1158 PerformDeferredActions(assembler,
1159 max_register,
1160 affected_registers,
1161 &registers_to_pop,
1162 &registers_to_clear);
ager@chromium.org8bb60582008-12-11 12:02:20 +00001163 if (cp_offset_ != 0) {
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001164 assembler->AdvanceCurrentPosition(cp_offset_);
ager@chromium.org8bb60582008-12-11 12:02:20 +00001165 }
1166
1167 // Create a new trivial state and generate the node with that.
1168 Label undo;
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001169 assembler->PushBacktrack(&undo);
ager@chromium.org32912102009-01-16 10:38:43 +00001170 Trace new_state;
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001171 successor->Emit(compiler, &new_state);
ager@chromium.org8bb60582008-12-11 12:02:20 +00001172
1173 // On backtrack we need to restore state.
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001174 assembler->Bind(&undo);
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001175 RestoreAffectedRegisters(assembler,
1176 max_register,
1177 registers_to_pop,
1178 registers_to_clear);
ager@chromium.org8bb60582008-12-11 12:02:20 +00001179 if (backtrack() == NULL) {
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001180 assembler->Backtrack();
ager@chromium.org8bb60582008-12-11 12:02:20 +00001181 } else {
ager@chromium.org381abbb2009-02-25 13:23:22 +00001182 assembler->PopCurrentPosition();
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001183 assembler->GoTo(backtrack());
ager@chromium.org8bb60582008-12-11 12:02:20 +00001184 }
ager@chromium.org8bb60582008-12-11 12:02:20 +00001185}
1186
1187
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001188void NegativeSubmatchSuccess::Emit(RegExpCompiler* compiler, Trace* trace) {
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001189 RegExpMacroAssembler* assembler = compiler->macro_assembler();
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001190
1191 // Omit flushing the trace. We discard the entire stack frame anyway.
1192
ager@chromium.org8bb60582008-12-11 12:02:20 +00001193 if (!label()->is_bound()) {
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001194 // We are completely independent of the trace, since we ignore it,
1195 // so this code can be used as the generic version.
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001196 assembler->Bind(label());
ager@chromium.org8bb60582008-12-11 12:02:20 +00001197 }
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001198
1199 // Throw away everything on the backtrack stack since the start
1200 // of the negative submatch and restore the character position.
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001201 assembler->ReadCurrentPositionFromRegister(current_position_register_);
1202 assembler->ReadStackPointerFromRegister(stack_pointer_register_);
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001203 if (clear_capture_count_ > 0) {
1204 // Clear any captures that might have been performed during the success
1205 // of the body of the negative look-ahead.
1206 int clear_capture_end = clear_capture_start_ + clear_capture_count_ - 1;
1207 assembler->ClearRegisters(clear_capture_start_, clear_capture_end);
1208 }
ager@chromium.org8bb60582008-12-11 12:02:20 +00001209 // Now that we have unwound the stack we find at the top of the stack the
1210 // backtrack that the BeginSubmatch node got.
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001211 assembler->Backtrack();
ager@chromium.org8bb60582008-12-11 12:02:20 +00001212}
1213
1214
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001215void EndNode::Emit(RegExpCompiler* compiler, Trace* trace) {
ager@chromium.org32912102009-01-16 10:38:43 +00001216 if (!trace->is_trivial()) {
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001217 trace->Flush(compiler, this);
1218 return;
ager@chromium.org8bb60582008-12-11 12:02:20 +00001219 }
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001220 RegExpMacroAssembler* assembler = compiler->macro_assembler();
ager@chromium.org8bb60582008-12-11 12:02:20 +00001221 if (!label()->is_bound()) {
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001222 assembler->Bind(label());
ager@chromium.org8bb60582008-12-11 12:02:20 +00001223 }
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001224 switch (action_) {
1225 case ACCEPT:
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001226 assembler->Succeed();
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001227 return;
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001228 case BACKTRACK:
ager@chromium.org32912102009-01-16 10:38:43 +00001229 assembler->GoTo(trace->backtrack());
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001230 return;
ager@chromium.org8bb60582008-12-11 12:02:20 +00001231 case NEGATIVE_SUBMATCH_SUCCESS:
1232 // This case is handled in a different virtual method.
1233 UNREACHABLE();
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001234 }
ager@chromium.org8bb60582008-12-11 12:02:20 +00001235 UNIMPLEMENTED();
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001236}
1237
1238
1239void GuardedAlternative::AddGuard(Guard* guard) {
1240 if (guards_ == NULL)
1241 guards_ = new ZoneList<Guard*>(1);
1242 guards_->Add(guard);
1243}
1244
1245
ager@chromium.org8bb60582008-12-11 12:02:20 +00001246ActionNode* ActionNode::SetRegister(int reg,
1247 int val,
1248 RegExpNode* on_success) {
1249 ActionNode* result = new ActionNode(SET_REGISTER, on_success);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001250 result->data_.u_store_register.reg = reg;
1251 result->data_.u_store_register.value = val;
1252 return result;
1253}
1254
1255
1256ActionNode* ActionNode::IncrementRegister(int reg, RegExpNode* on_success) {
1257 ActionNode* result = new ActionNode(INCREMENT_REGISTER, on_success);
1258 result->data_.u_increment_register.reg = reg;
1259 return result;
1260}
1261
1262
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001263ActionNode* ActionNode::StorePosition(int reg,
1264 bool is_capture,
1265 RegExpNode* on_success) {
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001266 ActionNode* result = new ActionNode(STORE_POSITION, on_success);
1267 result->data_.u_position_register.reg = reg;
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001268 result->data_.u_position_register.is_capture = is_capture;
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001269 return result;
1270}
1271
1272
ager@chromium.org32912102009-01-16 10:38:43 +00001273ActionNode* ActionNode::ClearCaptures(Interval range,
1274 RegExpNode* on_success) {
1275 ActionNode* result = new ActionNode(CLEAR_CAPTURES, on_success);
1276 result->data_.u_clear_captures.range_from = range.from();
1277 result->data_.u_clear_captures.range_to = range.to();
1278 return result;
1279}
1280
1281
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001282ActionNode* ActionNode::BeginSubmatch(int stack_reg,
1283 int position_reg,
1284 RegExpNode* on_success) {
1285 ActionNode* result = new ActionNode(BEGIN_SUBMATCH, on_success);
1286 result->data_.u_submatch.stack_pointer_register = stack_reg;
1287 result->data_.u_submatch.current_position_register = position_reg;
1288 return result;
1289}
1290
1291
ager@chromium.org8bb60582008-12-11 12:02:20 +00001292ActionNode* ActionNode::PositiveSubmatchSuccess(int stack_reg,
1293 int position_reg,
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001294 int clear_register_count,
1295 int clear_register_from,
ager@chromium.org8bb60582008-12-11 12:02:20 +00001296 RegExpNode* on_success) {
1297 ActionNode* result = new ActionNode(POSITIVE_SUBMATCH_SUCCESS, on_success);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001298 result->data_.u_submatch.stack_pointer_register = stack_reg;
ager@chromium.org8bb60582008-12-11 12:02:20 +00001299 result->data_.u_submatch.current_position_register = position_reg;
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001300 result->data_.u_submatch.clear_register_count = clear_register_count;
1301 result->data_.u_submatch.clear_register_from = clear_register_from;
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001302 return result;
1303}
1304
1305
ager@chromium.org32912102009-01-16 10:38:43 +00001306ActionNode* ActionNode::EmptyMatchCheck(int start_register,
1307 int repetition_register,
1308 int repetition_limit,
1309 RegExpNode* on_success) {
1310 ActionNode* result = new ActionNode(EMPTY_MATCH_CHECK, on_success);
1311 result->data_.u_empty_match_check.start_register = start_register;
1312 result->data_.u_empty_match_check.repetition_register = repetition_register;
1313 result->data_.u_empty_match_check.repetition_limit = repetition_limit;
1314 return result;
1315}
1316
1317
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001318#define DEFINE_ACCEPT(Type) \
1319 void Type##Node::Accept(NodeVisitor* visitor) { \
1320 visitor->Visit##Type(this); \
1321 }
1322FOR_EACH_NODE_TYPE(DEFINE_ACCEPT)
1323#undef DEFINE_ACCEPT
1324
1325
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001326void LoopChoiceNode::Accept(NodeVisitor* visitor) {
1327 visitor->VisitLoopChoice(this);
1328}
1329
1330
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001331// -------------------------------------------------------------------
1332// Emit code.
1333
1334
1335void ChoiceNode::GenerateGuard(RegExpMacroAssembler* macro_assembler,
1336 Guard* guard,
ager@chromium.org32912102009-01-16 10:38:43 +00001337 Trace* trace) {
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001338 switch (guard->op()) {
1339 case Guard::LT:
ager@chromium.org32912102009-01-16 10:38:43 +00001340 ASSERT(!trace->mentions_reg(guard->reg()));
ager@chromium.org8bb60582008-12-11 12:02:20 +00001341 macro_assembler->IfRegisterGE(guard->reg(),
1342 guard->value(),
ager@chromium.org32912102009-01-16 10:38:43 +00001343 trace->backtrack());
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001344 break;
1345 case Guard::GEQ:
ager@chromium.org32912102009-01-16 10:38:43 +00001346 ASSERT(!trace->mentions_reg(guard->reg()));
ager@chromium.org8bb60582008-12-11 12:02:20 +00001347 macro_assembler->IfRegisterLT(guard->reg(),
1348 guard->value(),
ager@chromium.org32912102009-01-16 10:38:43 +00001349 trace->backtrack());
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001350 break;
1351 }
1352}
1353
1354
ager@chromium.org381abbb2009-02-25 13:23:22 +00001355// Returns the number of characters in the equivalence class, omitting those
1356// that cannot occur in the source string because it is ASCII.
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +00001357static int GetCaseIndependentLetters(Isolate* isolate,
1358 uc16 character,
ager@chromium.org381abbb2009-02-25 13:23:22 +00001359 bool ascii_subject,
1360 unibrow::uchar* letters) {
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +00001361 int length =
1362 isolate->jsregexp_uncanonicalize()->get(character, '\0', letters);
whesse@chromium.orge90029b2010-08-02 11:52:17 +00001363 // Unibrow returns 0 or 1 for characters where case independence is
ager@chromium.org381abbb2009-02-25 13:23:22 +00001364 // trivial.
1365 if (length == 0) {
1366 letters[0] = character;
1367 length = 1;
1368 }
1369 if (!ascii_subject || character <= String::kMaxAsciiCharCode) {
1370 return length;
1371 }
1372 // The standard requires that non-ASCII characters cannot have ASCII
1373 // character codes in their equivalence class.
1374 return 0;
1375}
1376
1377
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +00001378static inline bool EmitSimpleCharacter(Isolate* isolate,
1379 RegExpCompiler* compiler,
ager@chromium.org381abbb2009-02-25 13:23:22 +00001380 uc16 c,
1381 Label* on_failure,
1382 int cp_offset,
1383 bool check,
1384 bool preloaded) {
1385 RegExpMacroAssembler* assembler = compiler->macro_assembler();
1386 bool bound_checked = false;
1387 if (!preloaded) {
1388 assembler->LoadCurrentCharacter(
1389 cp_offset,
1390 on_failure,
1391 check);
1392 bound_checked = true;
1393 }
1394 assembler->CheckNotCharacter(c, on_failure);
1395 return bound_checked;
1396}
1397
1398
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001399// Only emits non-letters (things that don't have case). Only used for case
1400// independent matches.
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +00001401static inline bool EmitAtomNonLetter(Isolate* isolate,
1402 RegExpCompiler* compiler,
ager@chromium.org381abbb2009-02-25 13:23:22 +00001403 uc16 c,
1404 Label* on_failure,
1405 int cp_offset,
1406 bool check,
1407 bool preloaded) {
1408 RegExpMacroAssembler* macro_assembler = compiler->macro_assembler();
1409 bool ascii = compiler->ascii();
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001410 unibrow::uchar chars[unibrow::Ecma262UnCanonicalize::kMaxWidth];
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +00001411 int length = GetCaseIndependentLetters(isolate, c, ascii, chars);
ager@chromium.org381abbb2009-02-25 13:23:22 +00001412 if (length < 1) {
1413 // This can't match. Must be an ASCII subject and a non-ASCII character.
1414 // We do not need to do anything since the ASCII pass already handled this.
1415 return false; // Bounds not checked.
1416 }
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001417 bool checked = false;
ager@chromium.org381abbb2009-02-25 13:23:22 +00001418 // We handle the length > 1 case in a later pass.
1419 if (length == 1) {
1420 if (ascii && c > String::kMaxAsciiCharCodeU) {
1421 // Can't match - see above.
1422 return false; // Bounds not checked.
1423 }
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001424 if (!preloaded) {
1425 macro_assembler->LoadCurrentCharacter(cp_offset, on_failure, check);
1426 checked = check;
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001427 }
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001428 macro_assembler->CheckNotCharacter(c, on_failure);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001429 }
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001430 return checked;
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001431}
1432
1433
1434static bool ShortCutEmitCharacterPair(RegExpMacroAssembler* macro_assembler,
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001435 bool ascii,
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001436 uc16 c1,
1437 uc16 c2,
1438 Label* on_failure) {
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001439 uc16 char_mask;
1440 if (ascii) {
1441 char_mask = String::kMaxAsciiCharCode;
1442 } else {
1443 char_mask = String::kMaxUC16CharCode;
1444 }
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001445 uc16 exor = c1 ^ c2;
1446 // Check whether exor has only one bit set.
1447 if (((exor - 1) & exor) == 0) {
1448 // If c1 and c2 differ only by one bit.
1449 // Ecma262UnCanonicalize always gives the highest number last.
1450 ASSERT(c2 > c1);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001451 uc16 mask = char_mask ^ exor;
1452 macro_assembler->CheckNotCharacterAfterAnd(c1, mask, on_failure);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001453 return true;
1454 }
1455 ASSERT(c2 > c1);
1456 uc16 diff = c2 - c1;
1457 if (((diff - 1) & diff) == 0 && c1 >= diff) {
1458 // If the characters differ by 2^n but don't differ by one bit then
1459 // subtract the difference from the found character, then do the or
1460 // trick. We avoid the theoretical case where negative numbers are
1461 // involved in order to simplify code generation.
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001462 uc16 mask = char_mask ^ diff;
1463 macro_assembler->CheckNotCharacterAfterMinusAnd(c1 - diff,
1464 diff,
1465 mask,
1466 on_failure);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001467 return true;
1468 }
1469 return false;
1470}
1471
1472
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +00001473typedef bool EmitCharacterFunction(Isolate* isolate,
1474 RegExpCompiler* compiler,
ager@chromium.org381abbb2009-02-25 13:23:22 +00001475 uc16 c,
1476 Label* on_failure,
1477 int cp_offset,
1478 bool check,
1479 bool preloaded);
1480
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001481// Only emits letters (things that have case). Only used for case independent
1482// matches.
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +00001483static inline bool EmitAtomLetter(Isolate* isolate,
1484 RegExpCompiler* compiler,
ager@chromium.org381abbb2009-02-25 13:23:22 +00001485 uc16 c,
1486 Label* on_failure,
1487 int cp_offset,
1488 bool check,
1489 bool preloaded) {
1490 RegExpMacroAssembler* macro_assembler = compiler->macro_assembler();
1491 bool ascii = compiler->ascii();
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001492 unibrow::uchar chars[unibrow::Ecma262UnCanonicalize::kMaxWidth];
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +00001493 int length = GetCaseIndependentLetters(isolate, c, ascii, chars);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001494 if (length <= 1) return false;
1495 // We may not need to check against the end of the input string
1496 // if this character lies before a character that matched.
1497 if (!preloaded) {
1498 macro_assembler->LoadCurrentCharacter(cp_offset, on_failure, check);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001499 }
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001500 Label ok;
1501 ASSERT(unibrow::Ecma262UnCanonicalize::kMaxWidth == 4);
1502 switch (length) {
1503 case 2: {
1504 if (ShortCutEmitCharacterPair(macro_assembler,
1505 ascii,
1506 chars[0],
1507 chars[1],
1508 on_failure)) {
1509 } else {
1510 macro_assembler->CheckCharacter(chars[0], &ok);
1511 macro_assembler->CheckNotCharacter(chars[1], on_failure);
1512 macro_assembler->Bind(&ok);
1513 }
1514 break;
1515 }
1516 case 4:
1517 macro_assembler->CheckCharacter(chars[3], &ok);
1518 // Fall through!
1519 case 3:
1520 macro_assembler->CheckCharacter(chars[0], &ok);
1521 macro_assembler->CheckCharacter(chars[1], &ok);
1522 macro_assembler->CheckNotCharacter(chars[2], on_failure);
1523 macro_assembler->Bind(&ok);
1524 break;
1525 default:
1526 UNREACHABLE();
1527 break;
1528 }
1529 return true;
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001530}
1531
1532
1533static void EmitCharClass(RegExpMacroAssembler* macro_assembler,
1534 RegExpCharacterClass* cc,
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001535 bool ascii,
ager@chromium.org381abbb2009-02-25 13:23:22 +00001536 Label* on_failure,
1537 int cp_offset,
1538 bool check_offset,
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001539 bool preloaded) {
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001540 ZoneList<CharacterRange>* ranges = cc->ranges();
ager@chromium.org8bb60582008-12-11 12:02:20 +00001541 int max_char;
1542 if (ascii) {
1543 max_char = String::kMaxAsciiCharCode;
1544 } else {
1545 max_char = String::kMaxUC16CharCode;
1546 }
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001547
1548 Label success;
1549
1550 Label* char_is_in_class =
1551 cc->is_negated() ? on_failure : &success;
1552
1553 int range_count = ranges->length();
1554
ager@chromium.org8bb60582008-12-11 12:02:20 +00001555 int last_valid_range = range_count - 1;
1556 while (last_valid_range >= 0) {
1557 CharacterRange& range = ranges->at(last_valid_range);
1558 if (range.from() <= max_char) {
1559 break;
1560 }
1561 last_valid_range--;
1562 }
1563
1564 if (last_valid_range < 0) {
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001565 if (!cc->is_negated()) {
ager@chromium.org8bb60582008-12-11 12:02:20 +00001566 // TODO(plesner): We can remove this when the node level does our
1567 // ASCII optimizations for us.
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001568 macro_assembler->GoTo(on_failure);
1569 }
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001570 if (check_offset) {
1571 macro_assembler->CheckPosition(cp_offset, on_failure);
1572 }
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001573 return;
1574 }
1575
ager@chromium.org8bb60582008-12-11 12:02:20 +00001576 if (last_valid_range == 0 &&
1577 !cc->is_negated() &&
1578 ranges->at(0).IsEverything(max_char)) {
1579 // This is a common case hit by non-anchored expressions.
ager@chromium.org8bb60582008-12-11 12:02:20 +00001580 if (check_offset) {
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001581 macro_assembler->CheckPosition(cp_offset, on_failure);
ager@chromium.org8bb60582008-12-11 12:02:20 +00001582 }
1583 return;
1584 }
1585
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001586 if (!preloaded) {
1587 macro_assembler->LoadCurrentCharacter(cp_offset, on_failure, check_offset);
ager@chromium.org8bb60582008-12-11 12:02:20 +00001588 }
1589
fschneider@chromium.org0c20e672010-01-14 15:28:53 +00001590 if (cc->is_standard() &&
1591 macro_assembler->CheckSpecialCharacterClass(cc->standard_type(),
1592 on_failure)) {
1593 return;
1594 }
1595
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001596 for (int i = 0; i < last_valid_range; i++) {
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001597 CharacterRange& range = ranges->at(i);
1598 Label next_range;
1599 uc16 from = range.from();
1600 uc16 to = range.to();
ager@chromium.org8bb60582008-12-11 12:02:20 +00001601 if (from > max_char) {
1602 continue;
1603 }
1604 if (to > max_char) to = max_char;
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001605 if (to == from) {
1606 macro_assembler->CheckCharacter(to, char_is_in_class);
1607 } else {
1608 if (from != 0) {
1609 macro_assembler->CheckCharacterLT(from, &next_range);
1610 }
ager@chromium.org8bb60582008-12-11 12:02:20 +00001611 if (to != max_char) {
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001612 macro_assembler->CheckCharacterLT(to + 1, char_is_in_class);
1613 } else {
1614 macro_assembler->GoTo(char_is_in_class);
1615 }
1616 }
1617 macro_assembler->Bind(&next_range);
1618 }
1619
ager@chromium.org8bb60582008-12-11 12:02:20 +00001620 CharacterRange& range = ranges->at(last_valid_range);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001621 uc16 from = range.from();
1622 uc16 to = range.to();
1623
ager@chromium.org8bb60582008-12-11 12:02:20 +00001624 if (to > max_char) to = max_char;
1625 ASSERT(to >= from);
1626
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001627 if (to == from) {
1628 if (cc->is_negated()) {
1629 macro_assembler->CheckCharacter(to, on_failure);
1630 } else {
1631 macro_assembler->CheckNotCharacter(to, on_failure);
1632 }
1633 } else {
1634 if (from != 0) {
1635 if (cc->is_negated()) {
1636 macro_assembler->CheckCharacterLT(from, &success);
1637 } else {
1638 macro_assembler->CheckCharacterLT(from, on_failure);
1639 }
1640 }
ager@chromium.org8bb60582008-12-11 12:02:20 +00001641 if (to != String::kMaxUC16CharCode) {
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001642 if (cc->is_negated()) {
1643 macro_assembler->CheckCharacterLT(to + 1, on_failure);
1644 } else {
1645 macro_assembler->CheckCharacterGT(to, on_failure);
1646 }
1647 } else {
1648 if (cc->is_negated()) {
1649 macro_assembler->GoTo(on_failure);
1650 }
1651 }
1652 }
1653 macro_assembler->Bind(&success);
1654}
1655
1656
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001657RegExpNode::~RegExpNode() {
1658}
1659
1660
ager@chromium.org8bb60582008-12-11 12:02:20 +00001661RegExpNode::LimitResult RegExpNode::LimitVersions(RegExpCompiler* compiler,
ager@chromium.org32912102009-01-16 10:38:43 +00001662 Trace* trace) {
ager@chromium.org8bb60582008-12-11 12:02:20 +00001663 // If we are generating a greedy loop then don't stop and don't reuse code.
ager@chromium.org32912102009-01-16 10:38:43 +00001664 if (trace->stop_node() != NULL) {
ager@chromium.org8bb60582008-12-11 12:02:20 +00001665 return CONTINUE;
1666 }
1667
ager@chromium.orga74f0da2008-12-03 16:05:52 +00001668 RegExpMacroAssembler* macro_assembler = compiler->macro_assembler();
ager@chromium.org32912102009-01-16 10:38:43 +00001669 if (trace->is_trivial()) {
ager@chromium.org8bb60582008-12-11 12:02:20 +00001670 if (label_.is_bound()) {
1671 // We are being asked to generate a generic version, but that's already
1672 // been done so just go to it.
1673 macro_assembler->GoTo(&label_);
1674 return DONE;
1675 }
1676 if (compiler->recursion_depth() >= RegExpCompiler::kMaxRecursion) {
1677 // To avoid too deep recursion we push the node to the work queue and just
1678 // generate a goto here.
1679 compiler->AddWork(this);
1680 macro_assembler->GoTo(&label_);
1681 return DONE;
1682 }
1683 // Generate generic version of the node and bind the label for later use.
1684 macro_assembler->Bind(&label_);
1685 return CONTINUE;
1686 }
1687
1688 // We are being asked to make a non-generic version. Keep track of how many
1689 // non-generic versions we generate so as not to overdo it.
ager@chromium.org32912102009-01-16 10:38:43 +00001690 trace_count_++;
ager@chromium.org381abbb2009-02-25 13:23:22 +00001691 if (FLAG_regexp_optimization &&
iposva@chromium.org245aa852009-02-10 00:49:54 +00001692 trace_count_ < kMaxCopiesCodeGenerated &&
ager@chromium.org8bb60582008-12-11 12:02:20 +00001693 compiler->recursion_depth() <= RegExpCompiler::kMaxRecursion) {
1694 return CONTINUE;
1695 }
1696
ager@chromium.org32912102009-01-16 10:38:43 +00001697 // If we get here code has been generated for this node too many times or
1698 // recursion is too deep. Time to switch to a generic version. The code for
ager@chromium.org8bb60582008-12-11 12:02:20 +00001699 // generic versions above can handle deep recursion properly.
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001700 trace->Flush(compiler, this);
1701 return DONE;
ager@chromium.org8bb60582008-12-11 12:02:20 +00001702}
1703
1704
kasperl@chromium.orga5551262010-12-07 12:49:48 +00001705int ActionNode::EatsAtLeast(int still_to_find,
1706 int recursion_depth,
1707 bool not_at_start) {
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001708 if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0;
1709 if (type_ == POSITIVE_SUBMATCH_SUCCESS) return 0; // Rewinds input!
kasperl@chromium.orga5551262010-12-07 12:49:48 +00001710 return on_success()->EatsAtLeast(still_to_find,
1711 recursion_depth + 1,
1712 not_at_start);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001713}
1714
1715
kasperl@chromium.orga5551262010-12-07 12:49:48 +00001716int AssertionNode::EatsAtLeast(int still_to_find,
1717 int recursion_depth,
1718 bool not_at_start) {
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001719 if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0;
kasperl@chromium.orga5551262010-12-07 12:49:48 +00001720 // If we know we are not at the start and we are asked "how many characters
1721 // will you match if you succeed?" then we can answer anything since false
1722 // implies false. So lets just return the max answer (still_to_find) since
1723 // that won't prevent us from preloading a lot of characters for the other
1724 // branches in the node graph.
1725 if (type() == AT_START && not_at_start) return still_to_find;
1726 return on_success()->EatsAtLeast(still_to_find,
1727 recursion_depth + 1,
1728 not_at_start);
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001729}
1730
1731
kasperl@chromium.orga5551262010-12-07 12:49:48 +00001732int BackReferenceNode::EatsAtLeast(int still_to_find,
1733 int recursion_depth,
1734 bool not_at_start) {
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001735 if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0;
kasperl@chromium.orga5551262010-12-07 12:49:48 +00001736 return on_success()->EatsAtLeast(still_to_find,
1737 recursion_depth + 1,
1738 not_at_start);
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001739}
1740
1741
kasperl@chromium.orga5551262010-12-07 12:49:48 +00001742int TextNode::EatsAtLeast(int still_to_find,
1743 int recursion_depth,
1744 bool not_at_start) {
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001745 int answer = Length();
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001746 if (answer >= still_to_find) return answer;
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001747 if (recursion_depth > RegExpCompiler::kMaxRecursion) return answer;
kasperl@chromium.orga5551262010-12-07 12:49:48 +00001748 // We are not at start after this node so we set the last argument to 'true'.
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001749 return answer + on_success()->EatsAtLeast(still_to_find - answer,
kasperl@chromium.orga5551262010-12-07 12:49:48 +00001750 recursion_depth + 1,
1751 true);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001752}
1753
1754
fschneider@chromium.org0c20e672010-01-14 15:28:53 +00001755int NegativeLookaheadChoiceNode::EatsAtLeast(int still_to_find,
kasperl@chromium.orga5551262010-12-07 12:49:48 +00001756 int recursion_depth,
1757 bool not_at_start) {
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001758 if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0;
1759 // Alternative 0 is the negative lookahead, alternative 1 is what comes
1760 // afterwards.
1761 RegExpNode* node = alternatives_->at(1).node();
kasperl@chromium.orga5551262010-12-07 12:49:48 +00001762 return node->EatsAtLeast(still_to_find, recursion_depth + 1, not_at_start);
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001763}
1764
1765
1766void NegativeLookaheadChoiceNode::GetQuickCheckDetails(
1767 QuickCheckDetails* details,
1768 RegExpCompiler* compiler,
iposva@chromium.org245aa852009-02-10 00:49:54 +00001769 int filled_in,
1770 bool not_at_start) {
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001771 // Alternative 0 is the negative lookahead, alternative 1 is what comes
1772 // afterwards.
1773 RegExpNode* node = alternatives_->at(1).node();
iposva@chromium.org245aa852009-02-10 00:49:54 +00001774 return node->GetQuickCheckDetails(details, compiler, filled_in, not_at_start);
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001775}
1776
1777
1778int ChoiceNode::EatsAtLeastHelper(int still_to_find,
1779 int recursion_depth,
kasperl@chromium.orga5551262010-12-07 12:49:48 +00001780 RegExpNode* ignore_this_node,
1781 bool not_at_start) {
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001782 if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0;
1783 int min = 100;
1784 int choice_count = alternatives_->length();
1785 for (int i = 0; i < choice_count; i++) {
1786 RegExpNode* node = alternatives_->at(i).node();
1787 if (node == ignore_this_node) continue;
ager@chromium.orgddb913d2009-01-27 10:01:48 +00001788 int node_eats_at_least = node->EatsAtLeast(still_to_find,
kasperl@chromium.orga5551262010-12-07 12:49:48 +00001789 recursion_depth + 1,
1790 not_at_start);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001791 if (node_eats_at_least < min) min = node_eats_at_least;
1792 }
1793 return min;
1794}
1795
1796
kasperl@chromium.orga5551262010-12-07 12:49:48 +00001797int LoopChoiceNode::EatsAtLeast(int still_to_find,
1798 int recursion_depth,
1799 bool not_at_start) {
1800 return EatsAtLeastHelper(still_to_find,
1801 recursion_depth,
1802 loop_node_,
1803 not_at_start);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001804}
1805
1806
kasperl@chromium.orga5551262010-12-07 12:49:48 +00001807int ChoiceNode::EatsAtLeast(int still_to_find,
1808 int recursion_depth,
1809 bool not_at_start) {
1810 return EatsAtLeastHelper(still_to_find,
1811 recursion_depth,
1812 NULL,
1813 not_at_start);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001814}
1815
1816
1817// Takes the left-most 1-bit and smears it out, setting all bits to its right.
1818static inline uint32_t SmearBitsRight(uint32_t v) {
1819 v |= v >> 1;
1820 v |= v >> 2;
1821 v |= v >> 4;
1822 v |= v >> 8;
1823 v |= v >> 16;
1824 return v;
1825}
1826
1827
1828bool QuickCheckDetails::Rationalize(bool asc) {
1829 bool found_useful_op = false;
1830 uint32_t char_mask;
1831 if (asc) {
1832 char_mask = String::kMaxAsciiCharCode;
1833 } else {
1834 char_mask = String::kMaxUC16CharCode;
1835 }
1836 mask_ = 0;
1837 value_ = 0;
1838 int char_shift = 0;
1839 for (int i = 0; i < characters_; i++) {
1840 Position* pos = &positions_[i];
1841 if ((pos->mask & String::kMaxAsciiCharCode) != 0) {
1842 found_useful_op = true;
1843 }
1844 mask_ |= (pos->mask & char_mask) << char_shift;
1845 value_ |= (pos->value & char_mask) << char_shift;
1846 char_shift += asc ? 8 : 16;
1847 }
1848 return found_useful_op;
1849}
1850
1851
1852bool RegExpNode::EmitQuickCheck(RegExpCompiler* compiler,
ager@chromium.org32912102009-01-16 10:38:43 +00001853 Trace* trace,
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001854 bool preload_has_checked_bounds,
1855 Label* on_possible_success,
1856 QuickCheckDetails* details,
1857 bool fall_through_on_failure) {
1858 if (details->characters() == 0) return false;
iposva@chromium.org245aa852009-02-10 00:49:54 +00001859 GetQuickCheckDetails(details, compiler, 0, trace->at_start() == Trace::FALSE);
1860 if (details->cannot_match()) return false;
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001861 if (!details->Rationalize(compiler->ascii())) return false;
ager@chromium.org18ad94b2009-09-02 08:22:29 +00001862 ASSERT(details->characters() == 1 ||
1863 compiler->macro_assembler()->CanReadUnaligned());
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001864 uint32_t mask = details->mask();
1865 uint32_t value = details->value();
1866
1867 RegExpMacroAssembler* assembler = compiler->macro_assembler();
1868
ager@chromium.org32912102009-01-16 10:38:43 +00001869 if (trace->characters_preloaded() != details->characters()) {
1870 assembler->LoadCurrentCharacter(trace->cp_offset(),
1871 trace->backtrack(),
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001872 !preload_has_checked_bounds,
1873 details->characters());
1874 }
1875
1876
1877 bool need_mask = true;
1878
1879 if (details->characters() == 1) {
1880 // If number of characters preloaded is 1 then we used a byte or 16 bit
1881 // load so the value is already masked down.
1882 uint32_t char_mask;
1883 if (compiler->ascii()) {
1884 char_mask = String::kMaxAsciiCharCode;
1885 } else {
1886 char_mask = String::kMaxUC16CharCode;
1887 }
1888 if ((mask & char_mask) == char_mask) need_mask = false;
1889 mask &= char_mask;
1890 } else {
ricow@chromium.org5ad5ace2010-06-23 09:06:43 +00001891 // For 2-character preloads in ASCII mode or 1-character preloads in
1892 // TWO_BYTE mode we also use a 16 bit load with zero extend.
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001893 if (details->characters() == 2 && compiler->ascii()) {
ricow@chromium.org5ad5ace2010-06-23 09:06:43 +00001894 if ((mask & 0x7f7f) == 0x7f7f) need_mask = false;
1895 } else if (details->characters() == 1 && !compiler->ascii()) {
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001896 if ((mask & 0xffff) == 0xffff) need_mask = false;
1897 } else {
1898 if (mask == 0xffffffff) need_mask = false;
1899 }
1900 }
1901
1902 if (fall_through_on_failure) {
1903 if (need_mask) {
1904 assembler->CheckCharacterAfterAnd(value, mask, on_possible_success);
1905 } else {
1906 assembler->CheckCharacter(value, on_possible_success);
1907 }
1908 } else {
1909 if (need_mask) {
ager@chromium.org32912102009-01-16 10:38:43 +00001910 assembler->CheckNotCharacterAfterAnd(value, mask, trace->backtrack());
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001911 } else {
ager@chromium.org32912102009-01-16 10:38:43 +00001912 assembler->CheckNotCharacter(value, trace->backtrack());
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001913 }
1914 }
1915 return true;
1916}
1917
1918
1919// Here is the meat of GetQuickCheckDetails (see also the comment on the
1920// super-class in the .h file).
1921//
1922// We iterate along the text object, building up for each character a
1923// mask and value that can be used to test for a quick failure to match.
1924// The masks and values for the positions will be combined into a single
1925// machine word for the current character width in order to be used in
1926// generating a quick check.
1927void TextNode::GetQuickCheckDetails(QuickCheckDetails* details,
1928 RegExpCompiler* compiler,
iposva@chromium.org245aa852009-02-10 00:49:54 +00001929 int characters_filled_in,
1930 bool not_at_start) {
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +00001931 Isolate* isolate = Isolate::Current();
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001932 ASSERT(characters_filled_in < details->characters());
1933 int characters = details->characters();
1934 int char_mask;
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001935 if (compiler->ascii()) {
1936 char_mask = String::kMaxAsciiCharCode;
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001937 } else {
1938 char_mask = String::kMaxUC16CharCode;
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001939 }
1940 for (int k = 0; k < elms_->length(); k++) {
1941 TextElement elm = elms_->at(k);
1942 if (elm.type == TextElement::ATOM) {
1943 Vector<const uc16> quarks = elm.data.u_atom->data();
1944 for (int i = 0; i < characters && i < quarks.length(); i++) {
1945 QuickCheckDetails::Position* pos =
1946 details->positions(characters_filled_in);
ager@chromium.org6f10e412009-02-13 10:11:16 +00001947 uc16 c = quarks[i];
1948 if (c > char_mask) {
1949 // If we expect a non-ASCII character from an ASCII string,
1950 // there is no way we can match. Not even case independent
1951 // matching can turn an ASCII character into non-ASCII or
1952 // vice versa.
1953 details->set_cannot_match();
ager@chromium.org381abbb2009-02-25 13:23:22 +00001954 pos->determines_perfectly = false;
ager@chromium.org6f10e412009-02-13 10:11:16 +00001955 return;
1956 }
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001957 if (compiler->ignore_case()) {
1958 unibrow::uchar chars[unibrow::Ecma262UnCanonicalize::kMaxWidth];
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +00001959 int length = GetCaseIndependentLetters(isolate, c, compiler->ascii(),
1960 chars);
ager@chromium.org381abbb2009-02-25 13:23:22 +00001961 ASSERT(length != 0); // Can only happen if c > char_mask (see above).
1962 if (length == 1) {
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001963 // This letter has no case equivalents, so it's nice and simple
1964 // and the mask-compare will determine definitely whether we have
1965 // a match at this character position.
1966 pos->mask = char_mask;
1967 pos->value = c;
1968 pos->determines_perfectly = true;
1969 } else {
1970 uint32_t common_bits = char_mask;
1971 uint32_t bits = chars[0];
1972 for (int j = 1; j < length; j++) {
1973 uint32_t differing_bits = ((chars[j] & common_bits) ^ bits);
1974 common_bits ^= differing_bits;
1975 bits &= common_bits;
1976 }
1977 // If length is 2 and common bits has only one zero in it then
1978 // our mask and compare instruction will determine definitely
1979 // whether we have a match at this character position. Otherwise
1980 // it can only be an approximate check.
1981 uint32_t one_zero = (common_bits | ~char_mask);
1982 if (length == 2 && ((~one_zero) & ((~one_zero) - 1)) == 0) {
1983 pos->determines_perfectly = true;
1984 }
1985 pos->mask = common_bits;
1986 pos->value = bits;
1987 }
1988 } else {
1989 // Don't ignore case. Nice simple case where the mask-compare will
1990 // determine definitely whether we have a match at this character
1991 // position.
1992 pos->mask = char_mask;
ager@chromium.org6f10e412009-02-13 10:11:16 +00001993 pos->value = c;
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00001994 pos->determines_perfectly = true;
1995 }
1996 characters_filled_in++;
1997 ASSERT(characters_filled_in <= details->characters());
1998 if (characters_filled_in == details->characters()) {
1999 return;
2000 }
2001 }
2002 } else {
2003 QuickCheckDetails::Position* pos =
2004 details->positions(characters_filled_in);
2005 RegExpCharacterClass* tree = elm.data.u_char_class;
2006 ZoneList<CharacterRange>* ranges = tree->ranges();
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002007 if (tree->is_negated()) {
2008 // A quick check uses multi-character mask and compare. There is no
2009 // useful way to incorporate a negative char class into this scheme
2010 // so we just conservatively create a mask and value that will always
2011 // succeed.
2012 pos->mask = 0;
2013 pos->value = 0;
2014 } else {
ager@chromium.org381abbb2009-02-25 13:23:22 +00002015 int first_range = 0;
2016 while (ranges->at(first_range).from() > char_mask) {
2017 first_range++;
2018 if (first_range == ranges->length()) {
2019 details->set_cannot_match();
2020 pos->determines_perfectly = false;
2021 return;
2022 }
2023 }
2024 CharacterRange range = ranges->at(first_range);
2025 uc16 from = range.from();
2026 uc16 to = range.to();
2027 if (to > char_mask) {
2028 to = char_mask;
2029 }
2030 uint32_t differing_bits = (from ^ to);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002031 // A mask and compare is only perfect if the differing bits form a
2032 // number like 00011111 with one single block of trailing 1s.
ager@chromium.org5aa501c2009-06-23 07:57:28 +00002033 if ((differing_bits & (differing_bits + 1)) == 0 &&
2034 from + differing_bits == to) {
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002035 pos->determines_perfectly = true;
2036 }
2037 uint32_t common_bits = ~SmearBitsRight(differing_bits);
ager@chromium.org381abbb2009-02-25 13:23:22 +00002038 uint32_t bits = (from & common_bits);
2039 for (int i = first_range + 1; i < ranges->length(); i++) {
2040 CharacterRange range = ranges->at(i);
2041 uc16 from = range.from();
2042 uc16 to = range.to();
2043 if (from > char_mask) continue;
2044 if (to > char_mask) to = char_mask;
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002045 // Here we are combining more ranges into the mask and compare
2046 // value. With each new range the mask becomes more sparse and
2047 // so the chances of a false positive rise. A character class
2048 // with multiple ranges is assumed never to be equivalent to a
2049 // mask and compare operation.
2050 pos->determines_perfectly = false;
ager@chromium.org381abbb2009-02-25 13:23:22 +00002051 uint32_t new_common_bits = (from ^ to);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002052 new_common_bits = ~SmearBitsRight(new_common_bits);
2053 common_bits &= new_common_bits;
2054 bits &= new_common_bits;
ager@chromium.org381abbb2009-02-25 13:23:22 +00002055 uint32_t differing_bits = (from & common_bits) ^ bits;
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002056 common_bits ^= differing_bits;
2057 bits &= common_bits;
2058 }
2059 pos->mask = common_bits;
2060 pos->value = bits;
2061 }
2062 characters_filled_in++;
2063 ASSERT(characters_filled_in <= details->characters());
2064 if (characters_filled_in == details->characters()) {
2065 return;
2066 }
2067 }
2068 }
2069 ASSERT(characters_filled_in != details->characters());
iposva@chromium.org245aa852009-02-10 00:49:54 +00002070 on_success()-> GetQuickCheckDetails(details,
2071 compiler,
2072 characters_filled_in,
2073 true);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002074}
2075
2076
2077void QuickCheckDetails::Clear() {
2078 for (int i = 0; i < characters_; i++) {
2079 positions_[i].mask = 0;
2080 positions_[i].value = 0;
2081 positions_[i].determines_perfectly = false;
2082 }
2083 characters_ = 0;
2084}
2085
2086
2087void QuickCheckDetails::Advance(int by, bool ascii) {
ager@chromium.orgddb913d2009-01-27 10:01:48 +00002088 ASSERT(by >= 0);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002089 if (by >= characters_) {
2090 Clear();
2091 return;
2092 }
2093 for (int i = 0; i < characters_ - by; i++) {
2094 positions_[i] = positions_[by + i];
2095 }
2096 for (int i = characters_ - by; i < characters_; i++) {
2097 positions_[i].mask = 0;
2098 positions_[i].value = 0;
2099 positions_[i].determines_perfectly = false;
2100 }
2101 characters_ -= by;
2102 // We could change mask_ and value_ here but we would never advance unless
2103 // they had already been used in a check and they won't be used again because
2104 // it would gain us nothing. So there's no point.
2105}
2106
2107
2108void QuickCheckDetails::Merge(QuickCheckDetails* other, int from_index) {
2109 ASSERT(characters_ == other->characters_);
iposva@chromium.org245aa852009-02-10 00:49:54 +00002110 if (other->cannot_match_) {
2111 return;
2112 }
2113 if (cannot_match_) {
2114 *this = *other;
2115 return;
2116 }
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002117 for (int i = from_index; i < characters_; i++) {
2118 QuickCheckDetails::Position* pos = positions(i);
2119 QuickCheckDetails::Position* other_pos = other->positions(i);
2120 if (pos->mask != other_pos->mask ||
2121 pos->value != other_pos->value ||
2122 !other_pos->determines_perfectly) {
2123 // Our mask-compare operation will be approximate unless we have the
2124 // exact same operation on both sides of the alternation.
2125 pos->determines_perfectly = false;
2126 }
2127 pos->mask &= other_pos->mask;
2128 pos->value &= pos->mask;
2129 other_pos->value &= pos->mask;
2130 uc16 differing_bits = (pos->value ^ other_pos->value);
2131 pos->mask &= ~differing_bits;
2132 pos->value &= pos->mask;
2133 }
2134}
2135
2136
ager@chromium.org32912102009-01-16 10:38:43 +00002137class VisitMarker {
2138 public:
2139 explicit VisitMarker(NodeInfo* info) : info_(info) {
2140 ASSERT(!info->visited);
2141 info->visited = true;
2142 }
2143 ~VisitMarker() {
2144 info_->visited = false;
2145 }
2146 private:
2147 NodeInfo* info_;
2148};
2149
2150
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002151void LoopChoiceNode::GetQuickCheckDetails(QuickCheckDetails* details,
2152 RegExpCompiler* compiler,
iposva@chromium.org245aa852009-02-10 00:49:54 +00002153 int characters_filled_in,
2154 bool not_at_start) {
ager@chromium.org32912102009-01-16 10:38:43 +00002155 if (body_can_be_zero_length_ || info()->visited) return;
2156 VisitMarker marker(info());
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002157 return ChoiceNode::GetQuickCheckDetails(details,
2158 compiler,
iposva@chromium.org245aa852009-02-10 00:49:54 +00002159 characters_filled_in,
2160 not_at_start);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002161}
2162
2163
2164void ChoiceNode::GetQuickCheckDetails(QuickCheckDetails* details,
2165 RegExpCompiler* compiler,
iposva@chromium.org245aa852009-02-10 00:49:54 +00002166 int characters_filled_in,
2167 bool not_at_start) {
2168 not_at_start = (not_at_start || not_at_start_);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002169 int choice_count = alternatives_->length();
2170 ASSERT(choice_count > 0);
2171 alternatives_->at(0).node()->GetQuickCheckDetails(details,
2172 compiler,
iposva@chromium.org245aa852009-02-10 00:49:54 +00002173 characters_filled_in,
2174 not_at_start);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002175 for (int i = 1; i < choice_count; i++) {
2176 QuickCheckDetails new_details(details->characters());
2177 RegExpNode* node = alternatives_->at(i).node();
iposva@chromium.org245aa852009-02-10 00:49:54 +00002178 node->GetQuickCheckDetails(&new_details, compiler,
2179 characters_filled_in,
2180 not_at_start);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002181 // Here we merge the quick match details of the two branches.
2182 details->Merge(&new_details, characters_filled_in);
2183 }
2184}
2185
2186
ager@chromium.orgddb913d2009-01-27 10:01:48 +00002187// Check for [0-9A-Z_a-z].
2188static void EmitWordCheck(RegExpMacroAssembler* assembler,
2189 Label* word,
2190 Label* non_word,
2191 bool fall_through_on_word) {
fschneider@chromium.org0c20e672010-01-14 15:28:53 +00002192 if (assembler->CheckSpecialCharacterClass(
2193 fall_through_on_word ? 'w' : 'W',
2194 fall_through_on_word ? non_word : word)) {
2195 // Optimized implementation available.
2196 return;
2197 }
ager@chromium.orgddb913d2009-01-27 10:01:48 +00002198 assembler->CheckCharacterGT('z', non_word);
2199 assembler->CheckCharacterLT('0', non_word);
2200 assembler->CheckCharacterGT('a' - 1, word);
2201 assembler->CheckCharacterLT('9' + 1, word);
2202 assembler->CheckCharacterLT('A', non_word);
2203 assembler->CheckCharacterLT('Z' + 1, word);
2204 if (fall_through_on_word) {
2205 assembler->CheckNotCharacter('_', non_word);
2206 } else {
2207 assembler->CheckCharacter('_', word);
2208 }
2209}
2210
2211
2212// Emit the code to check for a ^ in multiline mode (1-character lookbehind
2213// that matches newline or the start of input).
2214static void EmitHat(RegExpCompiler* compiler,
2215 RegExpNode* on_success,
2216 Trace* trace) {
2217 RegExpMacroAssembler* assembler = compiler->macro_assembler();
2218 // We will be loading the previous character into the current character
2219 // register.
2220 Trace new_trace(*trace);
2221 new_trace.InvalidateCurrentCharacter();
2222
2223 Label ok;
2224 if (new_trace.cp_offset() == 0) {
2225 // The start of input counts as a newline in this context, so skip to
2226 // ok if we are at the start.
2227 assembler->CheckAtStart(&ok);
2228 }
2229 // We already checked that we are not at the start of input so it must be
2230 // OK to load the previous character.
2231 assembler->LoadCurrentCharacter(new_trace.cp_offset() -1,
2232 new_trace.backtrack(),
2233 false);
fschneider@chromium.org0c20e672010-01-14 15:28:53 +00002234 if (!assembler->CheckSpecialCharacterClass('n',
2235 new_trace.backtrack())) {
2236 // Newline means \n, \r, 0x2028 or 0x2029.
2237 if (!compiler->ascii()) {
2238 assembler->CheckCharacterAfterAnd(0x2028, 0xfffe, &ok);
2239 }
2240 assembler->CheckCharacter('\n', &ok);
2241 assembler->CheckNotCharacter('\r', new_trace.backtrack());
ager@chromium.orgddb913d2009-01-27 10:01:48 +00002242 }
ager@chromium.orgddb913d2009-01-27 10:01:48 +00002243 assembler->Bind(&ok);
2244 on_success->Emit(compiler, &new_trace);
2245}
2246
2247
fschneider@chromium.org0c20e672010-01-14 15:28:53 +00002248// Emit the code to handle \b and \B (word-boundary or non-word-boundary)
2249// when we know whether the next character must be a word character or not.
2250static void EmitHalfBoundaryCheck(AssertionNode::AssertionNodeType type,
2251 RegExpCompiler* compiler,
2252 RegExpNode* on_success,
2253 Trace* trace) {
2254 RegExpMacroAssembler* assembler = compiler->macro_assembler();
2255 Label done;
2256
2257 Trace new_trace(*trace);
2258
2259 bool expect_word_character = (type == AssertionNode::AFTER_WORD_CHARACTER);
2260 Label* on_word = expect_word_character ? &done : new_trace.backtrack();
2261 Label* on_non_word = expect_word_character ? new_trace.backtrack() : &done;
2262
2263 // Check whether previous character was a word character.
2264 switch (trace->at_start()) {
2265 case Trace::TRUE:
2266 if (expect_word_character) {
2267 assembler->GoTo(on_non_word);
2268 }
2269 break;
2270 case Trace::UNKNOWN:
2271 ASSERT_EQ(0, trace->cp_offset());
2272 assembler->CheckAtStart(on_non_word);
2273 // Fall through.
2274 case Trace::FALSE:
2275 int prev_char_offset = trace->cp_offset() - 1;
2276 assembler->LoadCurrentCharacter(prev_char_offset, NULL, false, 1);
2277 EmitWordCheck(assembler, on_word, on_non_word, expect_word_character);
2278 // We may or may not have loaded the previous character.
2279 new_trace.InvalidateCurrentCharacter();
2280 }
2281
2282 assembler->Bind(&done);
2283
2284 on_success->Emit(compiler, &new_trace);
2285}
2286
2287
ager@chromium.orgddb913d2009-01-27 10:01:48 +00002288// Emit the code to handle \b and \B (word-boundary or non-word-boundary).
2289static void EmitBoundaryCheck(AssertionNode::AssertionNodeType type,
2290 RegExpCompiler* compiler,
2291 RegExpNode* on_success,
2292 Trace* trace) {
2293 RegExpMacroAssembler* assembler = compiler->macro_assembler();
2294 Label before_non_word;
2295 Label before_word;
2296 if (trace->characters_preloaded() != 1) {
2297 assembler->LoadCurrentCharacter(trace->cp_offset(), &before_non_word);
2298 }
2299 // Fall through on non-word.
2300 EmitWordCheck(assembler, &before_word, &before_non_word, false);
2301
2302 // We will be loading the previous character into the current character
2303 // register.
2304 Trace new_trace(*trace);
2305 new_trace.InvalidateCurrentCharacter();
2306
2307 Label ok;
2308 Label* boundary;
2309 Label* not_boundary;
2310 if (type == AssertionNode::AT_BOUNDARY) {
2311 boundary = &ok;
2312 not_boundary = new_trace.backtrack();
2313 } else {
2314 not_boundary = &ok;
2315 boundary = new_trace.backtrack();
2316 }
2317
2318 // Next character is not a word character.
2319 assembler->Bind(&before_non_word);
2320 if (new_trace.cp_offset() == 0) {
2321 // The start of input counts as a non-word character, so the question is
2322 // decided if we are at the start.
2323 assembler->CheckAtStart(not_boundary);
2324 }
2325 // We already checked that we are not at the start of input so it must be
2326 // OK to load the previous character.
2327 assembler->LoadCurrentCharacter(new_trace.cp_offset() - 1,
2328 &ok, // Unused dummy label in this call.
2329 false);
2330 // Fall through on non-word.
2331 EmitWordCheck(assembler, boundary, not_boundary, false);
2332 assembler->GoTo(not_boundary);
2333
2334 // Next character is a word character.
2335 assembler->Bind(&before_word);
2336 if (new_trace.cp_offset() == 0) {
2337 // The start of input counts as a non-word character, so the question is
2338 // decided if we are at the start.
2339 assembler->CheckAtStart(boundary);
2340 }
2341 // We already checked that we are not at the start of input so it must be
2342 // OK to load the previous character.
2343 assembler->LoadCurrentCharacter(new_trace.cp_offset() - 1,
2344 &ok, // Unused dummy label in this call.
2345 false);
2346 bool fall_through_on_word = (type == AssertionNode::AT_NON_BOUNDARY);
2347 EmitWordCheck(assembler, not_boundary, boundary, fall_through_on_word);
2348
2349 assembler->Bind(&ok);
2350
2351 on_success->Emit(compiler, &new_trace);
2352}
2353
2354
iposva@chromium.org245aa852009-02-10 00:49:54 +00002355void AssertionNode::GetQuickCheckDetails(QuickCheckDetails* details,
2356 RegExpCompiler* compiler,
2357 int filled_in,
2358 bool not_at_start) {
2359 if (type_ == AT_START && not_at_start) {
2360 details->set_cannot_match();
2361 return;
2362 }
2363 return on_success()->GetQuickCheckDetails(details,
2364 compiler,
2365 filled_in,
2366 not_at_start);
2367}
2368
2369
ager@chromium.orgddb913d2009-01-27 10:01:48 +00002370void AssertionNode::Emit(RegExpCompiler* compiler, Trace* trace) {
2371 RegExpMacroAssembler* assembler = compiler->macro_assembler();
2372 switch (type_) {
2373 case AT_END: {
2374 Label ok;
2375 assembler->CheckPosition(trace->cp_offset(), &ok);
2376 assembler->GoTo(trace->backtrack());
2377 assembler->Bind(&ok);
2378 break;
2379 }
iposva@chromium.org245aa852009-02-10 00:49:54 +00002380 case AT_START: {
2381 if (trace->at_start() == Trace::FALSE) {
2382 assembler->GoTo(trace->backtrack());
2383 return;
2384 }
2385 if (trace->at_start() == Trace::UNKNOWN) {
2386 assembler->CheckNotAtStart(trace->backtrack());
2387 Trace at_start_trace = *trace;
2388 at_start_trace.set_at_start(true);
2389 on_success()->Emit(compiler, &at_start_trace);
2390 return;
2391 }
2392 }
2393 break;
ager@chromium.orgddb913d2009-01-27 10:01:48 +00002394 case AFTER_NEWLINE:
2395 EmitHat(compiler, on_success(), trace);
2396 return;
ager@chromium.orgddb913d2009-01-27 10:01:48 +00002397 case AT_BOUNDARY:
fschneider@chromium.org0c20e672010-01-14 15:28:53 +00002398 case AT_NON_BOUNDARY: {
ager@chromium.orgddb913d2009-01-27 10:01:48 +00002399 EmitBoundaryCheck(type_, compiler, on_success(), trace);
2400 return;
fschneider@chromium.org0c20e672010-01-14 15:28:53 +00002401 }
2402 case AFTER_WORD_CHARACTER:
2403 case AFTER_NONWORD_CHARACTER: {
2404 EmitHalfBoundaryCheck(type_, compiler, on_success(), trace);
2405 }
ager@chromium.orgddb913d2009-01-27 10:01:48 +00002406 }
2407 on_success()->Emit(compiler, trace);
2408}
2409
2410
ager@chromium.org381abbb2009-02-25 13:23:22 +00002411static bool DeterminedAlready(QuickCheckDetails* quick_check, int offset) {
2412 if (quick_check == NULL) return false;
2413 if (offset >= quick_check->characters()) return false;
2414 return quick_check->positions(offset)->determines_perfectly;
2415}
2416
2417
2418static void UpdateBoundsCheck(int index, int* checked_up_to) {
2419 if (index > *checked_up_to) {
2420 *checked_up_to = index;
2421 }
2422}
2423
2424
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002425// We call this repeatedly to generate code for each pass over the text node.
2426// The passes are in increasing order of difficulty because we hope one
2427// of the first passes will fail in which case we are saved the work of the
2428// later passes. for example for the case independent regexp /%[asdfghjkl]a/
2429// we will check the '%' in the first pass, the case independent 'a' in the
2430// second pass and the character class in the last pass.
2431//
2432// The passes are done from right to left, so for example to test for /bar/
2433// we will first test for an 'r' with offset 2, then an 'a' with offset 1
2434// and then a 'b' with offset 0. This means we can avoid the end-of-input
2435// bounds check most of the time. In the example we only need to check for
2436// end-of-input when loading the putative 'r'.
2437//
2438// A slight complication involves the fact that the first character may already
2439// be fetched into a register by the previous node. In this case we want to
2440// do the test for that character first. We do this in separate passes. The
2441// 'preloaded' argument indicates that we are doing such a 'pass'. If such a
2442// pass has been performed then subsequent passes will have true in
2443// first_element_checked to indicate that that character does not need to be
2444// checked again.
2445//
ager@chromium.org32912102009-01-16 10:38:43 +00002446// In addition to all this we are passed a Trace, which can
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002447// contain an AlternativeGeneration object. In this AlternativeGeneration
2448// object we can see details of any quick check that was already passed in
2449// order to get to the code we are now generating. The quick check can involve
2450// loading characters, which means we do not need to recheck the bounds
2451// up to the limit the quick check already checked. In addition the quick
2452// check can have involved a mask and compare operation which may simplify
2453// or obviate the need for further checks at some character positions.
2454void TextNode::TextEmitPass(RegExpCompiler* compiler,
2455 TextEmitPassType pass,
2456 bool preloaded,
ager@chromium.org32912102009-01-16 10:38:43 +00002457 Trace* trace,
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002458 bool first_element_checked,
2459 int* checked_up_to) {
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +00002460 Isolate* isolate = Isolate::Current();
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002461 RegExpMacroAssembler* assembler = compiler->macro_assembler();
2462 bool ascii = compiler->ascii();
ager@chromium.org32912102009-01-16 10:38:43 +00002463 Label* backtrack = trace->backtrack();
2464 QuickCheckDetails* quick_check = trace->quick_check_performed();
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002465 int element_count = elms_->length();
2466 for (int i = preloaded ? 0 : element_count - 1; i >= 0; i--) {
2467 TextElement elm = elms_->at(i);
ager@chromium.org32912102009-01-16 10:38:43 +00002468 int cp_offset = trace->cp_offset() + elm.cp_offset;
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002469 if (elm.type == TextElement::ATOM) {
ager@chromium.org381abbb2009-02-25 13:23:22 +00002470 Vector<const uc16> quarks = elm.data.u_atom->data();
2471 for (int j = preloaded ? 0 : quarks.length() - 1; j >= 0; j--) {
2472 if (first_element_checked && i == 0 && j == 0) continue;
2473 if (DeterminedAlready(quick_check, elm.cp_offset + j)) continue;
2474 EmitCharacterFunction* emit_function = NULL;
2475 switch (pass) {
2476 case NON_ASCII_MATCH:
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002477 ASSERT(ascii);
2478 if (quarks[j] > String::kMaxAsciiCharCode) {
2479 assembler->GoTo(backtrack);
2480 return;
2481 }
ager@chromium.org381abbb2009-02-25 13:23:22 +00002482 break;
2483 case NON_LETTER_CHARACTER_MATCH:
2484 emit_function = &EmitAtomNonLetter;
2485 break;
2486 case SIMPLE_CHARACTER_MATCH:
2487 emit_function = &EmitSimpleCharacter;
2488 break;
2489 case CASE_CHARACTER_MATCH:
2490 emit_function = &EmitAtomLetter;
2491 break;
2492 default:
2493 break;
2494 }
2495 if (emit_function != NULL) {
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +00002496 bool bound_checked = emit_function(isolate,
2497 compiler,
ager@chromium.org6f10e412009-02-13 10:11:16 +00002498 quarks[j],
2499 backtrack,
2500 cp_offset + j,
2501 *checked_up_to < cp_offset + j,
2502 preloaded);
ager@chromium.org381abbb2009-02-25 13:23:22 +00002503 if (bound_checked) UpdateBoundsCheck(cp_offset + j, checked_up_to);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002504 }
2505 }
2506 } else {
2507 ASSERT_EQ(elm.type, TextElement::CHAR_CLASS);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002508 if (pass == CHARACTER_CLASS_MATCH) {
ager@chromium.org381abbb2009-02-25 13:23:22 +00002509 if (first_element_checked && i == 0) continue;
2510 if (DeterminedAlready(quick_check, elm.cp_offset)) continue;
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002511 RegExpCharacterClass* cc = elm.data.u_char_class;
2512 EmitCharClass(assembler,
2513 cc,
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002514 ascii,
ager@chromium.org381abbb2009-02-25 13:23:22 +00002515 backtrack,
2516 cp_offset,
2517 *checked_up_to < cp_offset,
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002518 preloaded);
ager@chromium.org381abbb2009-02-25 13:23:22 +00002519 UpdateBoundsCheck(cp_offset, checked_up_to);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002520 }
2521 }
2522 }
2523}
2524
2525
2526int TextNode::Length() {
2527 TextElement elm = elms_->last();
2528 ASSERT(elm.cp_offset >= 0);
2529 if (elm.type == TextElement::ATOM) {
2530 return elm.cp_offset + elm.data.u_atom->data().length();
2531 } else {
2532 return elm.cp_offset + 1;
2533 }
2534}
2535
2536
ager@chromium.org381abbb2009-02-25 13:23:22 +00002537bool TextNode::SkipPass(int int_pass, bool ignore_case) {
2538 TextEmitPassType pass = static_cast<TextEmitPassType>(int_pass);
2539 if (ignore_case) {
2540 return pass == SIMPLE_CHARACTER_MATCH;
2541 } else {
2542 return pass == NON_LETTER_CHARACTER_MATCH || pass == CASE_CHARACTER_MATCH;
2543 }
2544}
2545
2546
ager@chromium.org8bb60582008-12-11 12:02:20 +00002547// This generates the code to match a text node. A text node can contain
2548// straight character sequences (possibly to be matched in a case-independent
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002549// way) and character classes. For efficiency we do not do this in a single
2550// pass from left to right. Instead we pass over the text node several times,
2551// emitting code for some character positions every time. See the comment on
2552// TextEmitPass for details.
ager@chromium.orgddb913d2009-01-27 10:01:48 +00002553void TextNode::Emit(RegExpCompiler* compiler, Trace* trace) {
ager@chromium.org32912102009-01-16 10:38:43 +00002554 LimitResult limit_result = LimitVersions(compiler, trace);
ager@chromium.orgddb913d2009-01-27 10:01:48 +00002555 if (limit_result == DONE) return;
ager@chromium.org8bb60582008-12-11 12:02:20 +00002556 ASSERT(limit_result == CONTINUE);
2557
ager@chromium.orgddb913d2009-01-27 10:01:48 +00002558 if (trace->cp_offset() + Length() > RegExpMacroAssembler::kMaxCPOffset) {
2559 compiler->SetRegExpTooBig();
2560 return;
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002561 }
2562
2563 if (compiler->ascii()) {
2564 int dummy = 0;
ager@chromium.org32912102009-01-16 10:38:43 +00002565 TextEmitPass(compiler, NON_ASCII_MATCH, false, trace, false, &dummy);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002566 }
2567
2568 bool first_elt_done = false;
ager@chromium.org32912102009-01-16 10:38:43 +00002569 int bound_checked_to = trace->cp_offset() - 1;
2570 bound_checked_to += trace->bound_checked_up_to();
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002571
2572 // If a character is preloaded into the current character register then
2573 // check that now.
ager@chromium.org32912102009-01-16 10:38:43 +00002574 if (trace->characters_preloaded() == 1) {
ager@chromium.org381abbb2009-02-25 13:23:22 +00002575 for (int pass = kFirstRealPass; pass <= kLastPass; pass++) {
2576 if (!SkipPass(pass, compiler->ignore_case())) {
2577 TextEmitPass(compiler,
2578 static_cast<TextEmitPassType>(pass),
2579 true,
2580 trace,
2581 false,
2582 &bound_checked_to);
2583 }
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002584 }
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002585 first_elt_done = true;
2586 }
2587
ager@chromium.org381abbb2009-02-25 13:23:22 +00002588 for (int pass = kFirstRealPass; pass <= kLastPass; pass++) {
2589 if (!SkipPass(pass, compiler->ignore_case())) {
2590 TextEmitPass(compiler,
2591 static_cast<TextEmitPassType>(pass),
2592 false,
2593 trace,
2594 first_elt_done,
2595 &bound_checked_to);
2596 }
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002597 }
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002598
ager@chromium.org32912102009-01-16 10:38:43 +00002599 Trace successor_trace(*trace);
iposva@chromium.org245aa852009-02-10 00:49:54 +00002600 successor_trace.set_at_start(false);
ager@chromium.orgddb913d2009-01-27 10:01:48 +00002601 successor_trace.AdvanceCurrentPositionInTrace(Length(), compiler);
ager@chromium.org8bb60582008-12-11 12:02:20 +00002602 RecursionCheck rc(compiler);
ager@chromium.orgddb913d2009-01-27 10:01:48 +00002603 on_success()->Emit(compiler, &successor_trace);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002604}
2605
2606
ager@chromium.orgddb913d2009-01-27 10:01:48 +00002607void Trace::InvalidateCurrentCharacter() {
2608 characters_preloaded_ = 0;
2609}
2610
2611
2612void Trace::AdvanceCurrentPositionInTrace(int by, RegExpCompiler* compiler) {
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002613 ASSERT(by > 0);
2614 // We don't have an instruction for shifting the current character register
2615 // down or for using a shifted value for anything so lets just forget that
2616 // we preloaded any characters into it.
2617 characters_preloaded_ = 0;
2618 // Adjust the offsets of the quick check performed information. This
2619 // information is used to find out what we already determined about the
2620 // characters by means of mask and compare.
ager@chromium.orgddb913d2009-01-27 10:01:48 +00002621 quick_check_performed_.Advance(by, compiler->ascii());
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002622 cp_offset_ += by;
ager@chromium.orgddb913d2009-01-27 10:01:48 +00002623 if (cp_offset_ > RegExpMacroAssembler::kMaxCPOffset) {
2624 compiler->SetRegExpTooBig();
2625 cp_offset_ = 0;
2626 }
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002627 bound_checked_up_to_ = Max(0, bound_checked_up_to_ - by);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00002628}
2629
2630
ager@chromium.org38e4c712009-11-11 09:11:58 +00002631void TextNode::MakeCaseIndependent(bool is_ascii) {
ager@chromium.orga74f0da2008-12-03 16:05:52 +00002632 int element_count = elms_->length();
2633 for (int i = 0; i < element_count; i++) {
2634 TextElement elm = elms_->at(i);
2635 if (elm.type == TextElement::CHAR_CLASS) {
2636 RegExpCharacterClass* cc = elm.data.u_char_class;
ager@chromium.org38e4c712009-11-11 09:11:58 +00002637 // None of the standard character classses is different in the case
2638 // independent case and it slows us down if we don't know that.
2639 if (cc->is_standard()) continue;
ager@chromium.orga74f0da2008-12-03 16:05:52 +00002640 ZoneList<CharacterRange>* ranges = cc->ranges();
2641 int range_count = ranges->length();
ager@chromium.org38e4c712009-11-11 09:11:58 +00002642 for (int j = 0; j < range_count; j++) {
2643 ranges->at(j).AddCaseEquivalents(ranges, is_ascii);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00002644 }
2645 }
2646 }
2647}
2648
2649
ager@chromium.org8bb60582008-12-11 12:02:20 +00002650int TextNode::GreedyLoopTextLength() {
2651 TextElement elm = elms_->at(elms_->length() - 1);
2652 if (elm.type == TextElement::CHAR_CLASS) {
2653 return elm.cp_offset + 1;
2654 } else {
2655 return elm.cp_offset + elm.data.u_atom->data().length();
2656 }
2657}
2658
2659
2660// Finds the fixed match length of a sequence of nodes that goes from
2661// this alternative and back to this choice node. If there are variable
2662// length nodes or other complications in the way then return a sentinel
2663// value indicating that a greedy loop cannot be constructed.
2664int ChoiceNode::GreedyLoopTextLength(GuardedAlternative* alternative) {
2665 int length = 0;
2666 RegExpNode* node = alternative->node();
2667 // Later we will generate code for all these text nodes using recursion
2668 // so we have to limit the max number.
2669 int recursion_depth = 0;
2670 while (node != this) {
2671 if (recursion_depth++ > RegExpCompiler::kMaxRecursion) {
2672 return kNodeIsTooComplexForGreedyLoops;
2673 }
ager@chromium.org8bb60582008-12-11 12:02:20 +00002674 int node_length = node->GreedyLoopTextLength();
2675 if (node_length == kNodeIsTooComplexForGreedyLoops) {
2676 return kNodeIsTooComplexForGreedyLoops;
2677 }
2678 length += node_length;
2679 SeqRegExpNode* seq_node = static_cast<SeqRegExpNode*>(node);
2680 node = seq_node->on_success();
2681 }
2682 return length;
2683}
2684
2685
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002686void LoopChoiceNode::AddLoopAlternative(GuardedAlternative alt) {
2687 ASSERT_EQ(loop_node_, NULL);
2688 AddAlternative(alt);
2689 loop_node_ = alt.node();
2690}
2691
2692
2693void LoopChoiceNode::AddContinueAlternative(GuardedAlternative alt) {
2694 ASSERT_EQ(continue_node_, NULL);
2695 AddAlternative(alt);
2696 continue_node_ = alt.node();
2697}
2698
2699
ager@chromium.orgddb913d2009-01-27 10:01:48 +00002700void LoopChoiceNode::Emit(RegExpCompiler* compiler, Trace* trace) {
ager@chromium.orga74f0da2008-12-03 16:05:52 +00002701 RegExpMacroAssembler* macro_assembler = compiler->macro_assembler();
ager@chromium.org32912102009-01-16 10:38:43 +00002702 if (trace->stop_node() == this) {
ager@chromium.org8bb60582008-12-11 12:02:20 +00002703 int text_length = GreedyLoopTextLength(&(alternatives_->at(0)));
2704 ASSERT(text_length != kNodeIsTooComplexForGreedyLoops);
2705 // Update the counter-based backtracking info on the stack. This is an
2706 // optimization for greedy loops (see below).
ager@chromium.org32912102009-01-16 10:38:43 +00002707 ASSERT(trace->cp_offset() == text_length);
ager@chromium.org8bb60582008-12-11 12:02:20 +00002708 macro_assembler->AdvanceCurrentPosition(text_length);
ager@chromium.org32912102009-01-16 10:38:43 +00002709 macro_assembler->GoTo(trace->loop_label());
ager@chromium.orgddb913d2009-01-27 10:01:48 +00002710 return;
ager@chromium.org8bb60582008-12-11 12:02:20 +00002711 }
ager@chromium.org32912102009-01-16 10:38:43 +00002712 ASSERT(trace->stop_node() == NULL);
2713 if (!trace->is_trivial()) {
ager@chromium.orgddb913d2009-01-27 10:01:48 +00002714 trace->Flush(compiler, this);
2715 return;
ager@chromium.org8bb60582008-12-11 12:02:20 +00002716 }
ager@chromium.orgddb913d2009-01-27 10:01:48 +00002717 ChoiceNode::Emit(compiler, trace);
ager@chromium.org8bb60582008-12-11 12:02:20 +00002718}
2719
2720
kasperl@chromium.orga5551262010-12-07 12:49:48 +00002721int ChoiceNode::CalculatePreloadCharacters(RegExpCompiler* compiler,
2722 bool not_at_start) {
2723 int preload_characters = EatsAtLeast(4, 0, not_at_start);
ager@chromium.org18ad94b2009-09-02 08:22:29 +00002724 if (compiler->macro_assembler()->CanReadUnaligned()) {
2725 bool ascii = compiler->ascii();
2726 if (ascii) {
2727 if (preload_characters > 4) preload_characters = 4;
2728 // We can't preload 3 characters because there is no machine instruction
2729 // to do that. We can't just load 4 because we could be reading
2730 // beyond the end of the string, which could cause a memory fault.
2731 if (preload_characters == 3) preload_characters = 2;
2732 } else {
2733 if (preload_characters > 2) preload_characters = 2;
2734 }
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002735 } else {
ager@chromium.org18ad94b2009-09-02 08:22:29 +00002736 if (preload_characters > 1) preload_characters = 1;
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002737 }
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002738 return preload_characters;
2739}
2740
2741
2742// This class is used when generating the alternatives in a choice node. It
2743// records the way the alternative is being code generated.
2744class AlternativeGeneration: public Malloced {
2745 public:
2746 AlternativeGeneration()
2747 : possible_success(),
2748 expects_preload(false),
2749 after(),
2750 quick_check_details() { }
2751 Label possible_success;
2752 bool expects_preload;
2753 Label after;
2754 QuickCheckDetails quick_check_details;
2755};
2756
2757
2758// Creates a list of AlternativeGenerations. If the list has a reasonable
2759// size then it is on the stack, otherwise the excess is on the heap.
2760class AlternativeGenerationList {
2761 public:
2762 explicit AlternativeGenerationList(int count)
2763 : alt_gens_(count) {
2764 for (int i = 0; i < count && i < kAFew; i++) {
2765 alt_gens_.Add(a_few_alt_gens_ + i);
2766 }
2767 for (int i = kAFew; i < count; i++) {
2768 alt_gens_.Add(new AlternativeGeneration());
2769 }
2770 }
2771 ~AlternativeGenerationList() {
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002772 for (int i = kAFew; i < alt_gens_.length(); i++) {
2773 delete alt_gens_[i];
2774 alt_gens_[i] = NULL;
2775 }
2776 }
2777
2778 AlternativeGeneration* at(int i) {
2779 return alt_gens_[i];
2780 }
jkummerow@chromium.orge297f592011-06-08 10:05:15 +00002781
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002782 private:
2783 static const int kAFew = 10;
2784 ZoneList<AlternativeGeneration*> alt_gens_;
2785 AlternativeGeneration a_few_alt_gens_[kAFew];
2786};
2787
2788
2789/* Code generation for choice nodes.
2790 *
2791 * We generate quick checks that do a mask and compare to eliminate a
2792 * choice. If the quick check succeeds then it jumps to the continuation to
2793 * do slow checks and check subsequent nodes. If it fails (the common case)
2794 * it falls through to the next choice.
2795 *
2796 * Here is the desired flow graph. Nodes directly below each other imply
2797 * fallthrough. Alternatives 1 and 2 have quick checks. Alternative
2798 * 3 doesn't have a quick check so we have to call the slow check.
2799 * Nodes are marked Qn for quick checks and Sn for slow checks. The entire
2800 * regexp continuation is generated directly after the Sn node, up to the
2801 * next GoTo if we decide to reuse some already generated code. Some
2802 * nodes expect preload_characters to be preloaded into the current
2803 * character register. R nodes do this preloading. Vertices are marked
2804 * F for failures and S for success (possible success in the case of quick
2805 * nodes). L, V, < and > are used as arrow heads.
2806 *
2807 * ----------> R
2808 * |
2809 * V
2810 * Q1 -----> S1
2811 * | S /
2812 * F| /
2813 * | F/
2814 * | /
2815 * | R
2816 * | /
2817 * V L
2818 * Q2 -----> S2
2819 * | S /
2820 * F| /
2821 * | F/
2822 * | /
2823 * | R
2824 * | /
2825 * V L
2826 * S3
2827 * |
2828 * F|
2829 * |
2830 * R
2831 * |
2832 * backtrack V
2833 * <----------Q4
2834 * \ F |
2835 * \ |S
2836 * \ F V
2837 * \-----S4
2838 *
2839 * For greedy loops we reverse our expectation and expect to match rather
2840 * than fail. Therefore we want the loop code to look like this (U is the
2841 * unwind code that steps back in the greedy loop). The following alternatives
2842 * look the same as above.
2843 * _____
2844 * / \
2845 * V |
2846 * ----------> S1 |
2847 * /| |
2848 * / |S |
2849 * F/ \_____/
2850 * /
2851 * |<-----------
2852 * | \
2853 * V \
2854 * Q2 ---> S2 \
2855 * | S / |
2856 * F| / |
2857 * | F/ |
2858 * | / |
2859 * | R |
2860 * | / |
2861 * F VL |
2862 * <------U |
2863 * back |S |
2864 * \______________/
2865 */
2866
2867
ager@chromium.orgddb913d2009-01-27 10:01:48 +00002868void ChoiceNode::Emit(RegExpCompiler* compiler, Trace* trace) {
ager@chromium.org8bb60582008-12-11 12:02:20 +00002869 RegExpMacroAssembler* macro_assembler = compiler->macro_assembler();
2870 int choice_count = alternatives_->length();
2871#ifdef DEBUG
ager@chromium.orga74f0da2008-12-03 16:05:52 +00002872 for (int i = 0; i < choice_count - 1; i++) {
2873 GuardedAlternative alternative = alternatives_->at(i);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00002874 ZoneList<Guard*>* guards = alternative.guards();
ager@chromium.org8bb60582008-12-11 12:02:20 +00002875 int guard_count = (guards == NULL) ? 0 : guards->length();
2876 for (int j = 0; j < guard_count; j++) {
ager@chromium.org32912102009-01-16 10:38:43 +00002877 ASSERT(!trace->mentions_reg(guards->at(j)->reg()));
ager@chromium.orga74f0da2008-12-03 16:05:52 +00002878 }
ager@chromium.org8bb60582008-12-11 12:02:20 +00002879 }
2880#endif
2881
ager@chromium.org32912102009-01-16 10:38:43 +00002882 LimitResult limit_result = LimitVersions(compiler, trace);
ager@chromium.orgddb913d2009-01-27 10:01:48 +00002883 if (limit_result == DONE) return;
ager@chromium.org8bb60582008-12-11 12:02:20 +00002884 ASSERT(limit_result == CONTINUE);
2885
ager@chromium.org381abbb2009-02-25 13:23:22 +00002886 int new_flush_budget = trace->flush_budget() / choice_count;
2887 if (trace->flush_budget() == 0 && trace->actions() != NULL) {
2888 trace->Flush(compiler, this);
2889 return;
2890 }
2891
ager@chromium.org8bb60582008-12-11 12:02:20 +00002892 RecursionCheck rc(compiler);
2893
ager@chromium.org32912102009-01-16 10:38:43 +00002894 Trace* current_trace = trace;
ager@chromium.org8bb60582008-12-11 12:02:20 +00002895
2896 int text_length = GreedyLoopTextLength(&(alternatives_->at(0)));
2897 bool greedy_loop = false;
2898 Label greedy_loop_label;
ager@chromium.org32912102009-01-16 10:38:43 +00002899 Trace counter_backtrack_trace;
2900 counter_backtrack_trace.set_backtrack(&greedy_loop_label);
iposva@chromium.org245aa852009-02-10 00:49:54 +00002901 if (not_at_start()) counter_backtrack_trace.set_at_start(false);
2902
ager@chromium.org8bb60582008-12-11 12:02:20 +00002903 if (choice_count > 1 && text_length != kNodeIsTooComplexForGreedyLoops) {
2904 // Here we have special handling for greedy loops containing only text nodes
2905 // and other simple nodes. These are handled by pushing the current
2906 // position on the stack and then incrementing the current position each
2907 // time around the switch. On backtrack we decrement the current position
2908 // and check it against the pushed value. This avoids pushing backtrack
2909 // information for each iteration of the loop, which could take up a lot of
2910 // space.
2911 greedy_loop = true;
ager@chromium.org32912102009-01-16 10:38:43 +00002912 ASSERT(trace->stop_node() == NULL);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00002913 macro_assembler->PushCurrentPosition();
ager@chromium.org32912102009-01-16 10:38:43 +00002914 current_trace = &counter_backtrack_trace;
ager@chromium.org8bb60582008-12-11 12:02:20 +00002915 Label greedy_match_failed;
ager@chromium.org32912102009-01-16 10:38:43 +00002916 Trace greedy_match_trace;
iposva@chromium.org245aa852009-02-10 00:49:54 +00002917 if (not_at_start()) greedy_match_trace.set_at_start(false);
ager@chromium.org32912102009-01-16 10:38:43 +00002918 greedy_match_trace.set_backtrack(&greedy_match_failed);
ager@chromium.org8bb60582008-12-11 12:02:20 +00002919 Label loop_label;
2920 macro_assembler->Bind(&loop_label);
ager@chromium.org32912102009-01-16 10:38:43 +00002921 greedy_match_trace.set_stop_node(this);
2922 greedy_match_trace.set_loop_label(&loop_label);
ager@chromium.orgddb913d2009-01-27 10:01:48 +00002923 alternatives_->at(0).node()->Emit(compiler, &greedy_match_trace);
ager@chromium.org8bb60582008-12-11 12:02:20 +00002924 macro_assembler->Bind(&greedy_match_failed);
ager@chromium.org8bb60582008-12-11 12:02:20 +00002925 }
2926
2927 Label second_choice; // For use in greedy matches.
2928 macro_assembler->Bind(&second_choice);
2929
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002930 int first_normal_choice = greedy_loop ? 1 : 0;
2931
kasperl@chromium.orga5551262010-12-07 12:49:48 +00002932 int preload_characters =
2933 CalculatePreloadCharacters(compiler,
2934 current_trace->at_start() == Trace::FALSE);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002935 bool preload_is_current =
ager@chromium.org32912102009-01-16 10:38:43 +00002936 (current_trace->characters_preloaded() == preload_characters);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002937 bool preload_has_checked_bounds = preload_is_current;
2938
2939 AlternativeGenerationList alt_gens(choice_count);
2940
ager@chromium.org8bb60582008-12-11 12:02:20 +00002941 // For now we just call all choices one after the other. The idea ultimately
2942 // is to use the Dispatch table to try only the relevant ones.
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002943 for (int i = first_normal_choice; i < choice_count; i++) {
ager@chromium.org8bb60582008-12-11 12:02:20 +00002944 GuardedAlternative alternative = alternatives_->at(i);
ager@chromium.org32912102009-01-16 10:38:43 +00002945 AlternativeGeneration* alt_gen = alt_gens.at(i);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002946 alt_gen->quick_check_details.set_characters(preload_characters);
ager@chromium.org8bb60582008-12-11 12:02:20 +00002947 ZoneList<Guard*>* guards = alternative.guards();
2948 int guard_count = (guards == NULL) ? 0 : guards->length();
ager@chromium.org32912102009-01-16 10:38:43 +00002949 Trace new_trace(*current_trace);
2950 new_trace.set_characters_preloaded(preload_is_current ?
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002951 preload_characters :
2952 0);
2953 if (preload_has_checked_bounds) {
ager@chromium.org32912102009-01-16 10:38:43 +00002954 new_trace.set_bound_checked_up_to(preload_characters);
ager@chromium.org8bb60582008-12-11 12:02:20 +00002955 }
ager@chromium.org32912102009-01-16 10:38:43 +00002956 new_trace.quick_check_performed()->Clear();
iposva@chromium.org245aa852009-02-10 00:49:54 +00002957 if (not_at_start_) new_trace.set_at_start(Trace::FALSE);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002958 alt_gen->expects_preload = preload_is_current;
2959 bool generate_full_check_inline = false;
ager@chromium.org381abbb2009-02-25 13:23:22 +00002960 if (FLAG_regexp_optimization &&
iposva@chromium.org245aa852009-02-10 00:49:54 +00002961 try_to_emit_quick_check_for_alternative(i) &&
ager@chromium.orgddb913d2009-01-27 10:01:48 +00002962 alternative.node()->EmitQuickCheck(compiler,
ager@chromium.org32912102009-01-16 10:38:43 +00002963 &new_trace,
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002964 preload_has_checked_bounds,
2965 &alt_gen->possible_success,
2966 &alt_gen->quick_check_details,
2967 i < choice_count - 1)) {
2968 // Quick check was generated for this choice.
2969 preload_is_current = true;
2970 preload_has_checked_bounds = true;
2971 // On the last choice in the ChoiceNode we generated the quick
2972 // check to fall through on possible success. So now we need to
2973 // generate the full check inline.
2974 if (i == choice_count - 1) {
2975 macro_assembler->Bind(&alt_gen->possible_success);
ager@chromium.org32912102009-01-16 10:38:43 +00002976 new_trace.set_quick_check_performed(&alt_gen->quick_check_details);
2977 new_trace.set_characters_preloaded(preload_characters);
2978 new_trace.set_bound_checked_up_to(preload_characters);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002979 generate_full_check_inline = true;
2980 }
iposva@chromium.org245aa852009-02-10 00:49:54 +00002981 } else if (alt_gen->quick_check_details.cannot_match()) {
2982 if (i == choice_count - 1 && !greedy_loop) {
2983 macro_assembler->GoTo(trace->backtrack());
2984 }
2985 continue;
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002986 } else {
2987 // No quick check was generated. Put the full code here.
2988 // If this is not the first choice then there could be slow checks from
2989 // previous cases that go here when they fail. There's no reason to
2990 // insist that they preload characters since the slow check we are about
2991 // to generate probably can't use it.
2992 if (i != first_normal_choice) {
2993 alt_gen->expects_preload = false;
fschneider@chromium.org0c20e672010-01-14 15:28:53 +00002994 new_trace.InvalidateCurrentCharacter();
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002995 }
2996 if (i < choice_count - 1) {
ager@chromium.org32912102009-01-16 10:38:43 +00002997 new_trace.set_backtrack(&alt_gen->after);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00002998 }
2999 generate_full_check_inline = true;
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003000 }
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003001 if (generate_full_check_inline) {
ager@chromium.org381abbb2009-02-25 13:23:22 +00003002 if (new_trace.actions() != NULL) {
3003 new_trace.set_flush_budget(new_flush_budget);
3004 }
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003005 for (int j = 0; j < guard_count; j++) {
ager@chromium.org32912102009-01-16 10:38:43 +00003006 GenerateGuard(macro_assembler, guards->at(j), &new_trace);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003007 }
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003008 alternative.node()->Emit(compiler, &new_trace);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003009 preload_is_current = false;
3010 }
3011 macro_assembler->Bind(&alt_gen->after);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003012 }
ager@chromium.org8bb60582008-12-11 12:02:20 +00003013 if (greedy_loop) {
3014 macro_assembler->Bind(&greedy_loop_label);
3015 // If we have unwound to the bottom then backtrack.
ager@chromium.org32912102009-01-16 10:38:43 +00003016 macro_assembler->CheckGreedyLoop(trace->backtrack());
ager@chromium.org8bb60582008-12-11 12:02:20 +00003017 // Otherwise try the second priority at an earlier position.
3018 macro_assembler->AdvanceCurrentPosition(-text_length);
3019 macro_assembler->GoTo(&second_choice);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003020 }
ager@chromium.org381abbb2009-02-25 13:23:22 +00003021
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003022 // At this point we need to generate slow checks for the alternatives where
3023 // the quick check was inlined. We can recognize these because the associated
3024 // label was bound.
3025 for (int i = first_normal_choice; i < choice_count - 1; i++) {
3026 AlternativeGeneration* alt_gen = alt_gens.at(i);
ager@chromium.org381abbb2009-02-25 13:23:22 +00003027 Trace new_trace(*current_trace);
3028 // If there are actions to be flushed we have to limit how many times
3029 // they are flushed. Take the budget of the parent trace and distribute
3030 // it fairly amongst the children.
3031 if (new_trace.actions() != NULL) {
3032 new_trace.set_flush_budget(new_flush_budget);
3033 }
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003034 EmitOutOfLineContinuation(compiler,
ager@chromium.org381abbb2009-02-25 13:23:22 +00003035 &new_trace,
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003036 alternatives_->at(i),
3037 alt_gen,
3038 preload_characters,
3039 alt_gens.at(i + 1)->expects_preload);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003040 }
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003041}
3042
3043
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003044void ChoiceNode::EmitOutOfLineContinuation(RegExpCompiler* compiler,
ager@chromium.org32912102009-01-16 10:38:43 +00003045 Trace* trace,
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003046 GuardedAlternative alternative,
3047 AlternativeGeneration* alt_gen,
3048 int preload_characters,
3049 bool next_expects_preload) {
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003050 if (!alt_gen->possible_success.is_linked()) return;
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003051
3052 RegExpMacroAssembler* macro_assembler = compiler->macro_assembler();
3053 macro_assembler->Bind(&alt_gen->possible_success);
ager@chromium.org32912102009-01-16 10:38:43 +00003054 Trace out_of_line_trace(*trace);
3055 out_of_line_trace.set_characters_preloaded(preload_characters);
3056 out_of_line_trace.set_quick_check_performed(&alt_gen->quick_check_details);
iposva@chromium.org245aa852009-02-10 00:49:54 +00003057 if (not_at_start_) out_of_line_trace.set_at_start(Trace::FALSE);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003058 ZoneList<Guard*>* guards = alternative.guards();
3059 int guard_count = (guards == NULL) ? 0 : guards->length();
3060 if (next_expects_preload) {
3061 Label reload_current_char;
ager@chromium.org32912102009-01-16 10:38:43 +00003062 out_of_line_trace.set_backtrack(&reload_current_char);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003063 for (int j = 0; j < guard_count; j++) {
ager@chromium.org32912102009-01-16 10:38:43 +00003064 GenerateGuard(macro_assembler, guards->at(j), &out_of_line_trace);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003065 }
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003066 alternative.node()->Emit(compiler, &out_of_line_trace);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003067 macro_assembler->Bind(&reload_current_char);
3068 // Reload the current character, since the next quick check expects that.
3069 // We don't need to check bounds here because we only get into this
3070 // code through a quick check which already did the checked load.
ager@chromium.org32912102009-01-16 10:38:43 +00003071 macro_assembler->LoadCurrentCharacter(trace->cp_offset(),
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003072 NULL,
3073 false,
3074 preload_characters);
3075 macro_assembler->GoTo(&(alt_gen->after));
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003076 } else {
ager@chromium.org32912102009-01-16 10:38:43 +00003077 out_of_line_trace.set_backtrack(&(alt_gen->after));
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003078 for (int j = 0; j < guard_count; j++) {
ager@chromium.org32912102009-01-16 10:38:43 +00003079 GenerateGuard(macro_assembler, guards->at(j), &out_of_line_trace);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003080 }
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003081 alternative.node()->Emit(compiler, &out_of_line_trace);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003082 }
3083}
3084
3085
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003086void ActionNode::Emit(RegExpCompiler* compiler, Trace* trace) {
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003087 RegExpMacroAssembler* assembler = compiler->macro_assembler();
ager@chromium.org32912102009-01-16 10:38:43 +00003088 LimitResult limit_result = LimitVersions(compiler, trace);
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003089 if (limit_result == DONE) return;
ager@chromium.org8bb60582008-12-11 12:02:20 +00003090 ASSERT(limit_result == CONTINUE);
3091
3092 RecursionCheck rc(compiler);
3093
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003094 switch (type_) {
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003095 case STORE_POSITION: {
ager@chromium.org32912102009-01-16 10:38:43 +00003096 Trace::DeferredCapture
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003097 new_capture(data_.u_position_register.reg,
3098 data_.u_position_register.is_capture,
3099 trace);
ager@chromium.org32912102009-01-16 10:38:43 +00003100 Trace new_trace = *trace;
3101 new_trace.add_action(&new_capture);
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003102 on_success()->Emit(compiler, &new_trace);
3103 break;
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003104 }
ager@chromium.org8bb60582008-12-11 12:02:20 +00003105 case INCREMENT_REGISTER: {
ager@chromium.org32912102009-01-16 10:38:43 +00003106 Trace::DeferredIncrementRegister
ager@chromium.org8bb60582008-12-11 12:02:20 +00003107 new_increment(data_.u_increment_register.reg);
ager@chromium.org32912102009-01-16 10:38:43 +00003108 Trace new_trace = *trace;
3109 new_trace.add_action(&new_increment);
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003110 on_success()->Emit(compiler, &new_trace);
3111 break;
ager@chromium.org8bb60582008-12-11 12:02:20 +00003112 }
3113 case SET_REGISTER: {
ager@chromium.org32912102009-01-16 10:38:43 +00003114 Trace::DeferredSetRegister
ager@chromium.org8bb60582008-12-11 12:02:20 +00003115 new_set(data_.u_store_register.reg, data_.u_store_register.value);
ager@chromium.org32912102009-01-16 10:38:43 +00003116 Trace new_trace = *trace;
3117 new_trace.add_action(&new_set);
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003118 on_success()->Emit(compiler, &new_trace);
3119 break;
ager@chromium.org32912102009-01-16 10:38:43 +00003120 }
3121 case CLEAR_CAPTURES: {
3122 Trace::DeferredClearCaptures
3123 new_capture(Interval(data_.u_clear_captures.range_from,
3124 data_.u_clear_captures.range_to));
3125 Trace new_trace = *trace;
3126 new_trace.add_action(&new_capture);
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003127 on_success()->Emit(compiler, &new_trace);
3128 break;
ager@chromium.org8bb60582008-12-11 12:02:20 +00003129 }
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003130 case BEGIN_SUBMATCH:
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003131 if (!trace->is_trivial()) {
3132 trace->Flush(compiler, this);
3133 } else {
3134 assembler->WriteCurrentPositionToRegister(
3135 data_.u_submatch.current_position_register, 0);
3136 assembler->WriteStackPointerToRegister(
3137 data_.u_submatch.stack_pointer_register);
3138 on_success()->Emit(compiler, trace);
3139 }
3140 break;
ager@chromium.org32912102009-01-16 10:38:43 +00003141 case EMPTY_MATCH_CHECK: {
3142 int start_pos_reg = data_.u_empty_match_check.start_register;
3143 int stored_pos = 0;
3144 int rep_reg = data_.u_empty_match_check.repetition_register;
3145 bool has_minimum = (rep_reg != RegExpCompiler::kNoRegister);
3146 bool know_dist = trace->GetStoredPosition(start_pos_reg, &stored_pos);
3147 if (know_dist && !has_minimum && stored_pos == trace->cp_offset()) {
3148 // If we know we haven't advanced and there is no minimum we
3149 // can just backtrack immediately.
3150 assembler->GoTo(trace->backtrack());
ager@chromium.org32912102009-01-16 10:38:43 +00003151 } else if (know_dist && stored_pos < trace->cp_offset()) {
3152 // If we know we've advanced we can generate the continuation
3153 // immediately.
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003154 on_success()->Emit(compiler, trace);
3155 } else if (!trace->is_trivial()) {
3156 trace->Flush(compiler, this);
3157 } else {
3158 Label skip_empty_check;
3159 // If we have a minimum number of repetitions we check the current
3160 // number first and skip the empty check if it's not enough.
3161 if (has_minimum) {
3162 int limit = data_.u_empty_match_check.repetition_limit;
3163 assembler->IfRegisterLT(rep_reg, limit, &skip_empty_check);
3164 }
3165 // If the match is empty we bail out, otherwise we fall through
3166 // to the on-success continuation.
3167 assembler->IfRegisterEqPos(data_.u_empty_match_check.start_register,
3168 trace->backtrack());
3169 assembler->Bind(&skip_empty_check);
3170 on_success()->Emit(compiler, trace);
ager@chromium.org32912102009-01-16 10:38:43 +00003171 }
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003172 break;
ager@chromium.org32912102009-01-16 10:38:43 +00003173 }
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003174 case POSITIVE_SUBMATCH_SUCCESS: {
3175 if (!trace->is_trivial()) {
3176 trace->Flush(compiler, this);
3177 return;
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003178 }
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003179 assembler->ReadCurrentPositionFromRegister(
ager@chromium.org8bb60582008-12-11 12:02:20 +00003180 data_.u_submatch.current_position_register);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003181 assembler->ReadStackPointerFromRegister(
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003182 data_.u_submatch.stack_pointer_register);
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003183 int clear_register_count = data_.u_submatch.clear_register_count;
3184 if (clear_register_count == 0) {
3185 on_success()->Emit(compiler, trace);
3186 return;
3187 }
3188 int clear_registers_from = data_.u_submatch.clear_register_from;
3189 Label clear_registers_backtrack;
3190 Trace new_trace = *trace;
3191 new_trace.set_backtrack(&clear_registers_backtrack);
3192 on_success()->Emit(compiler, &new_trace);
3193
3194 assembler->Bind(&clear_registers_backtrack);
3195 int clear_registers_to = clear_registers_from + clear_register_count - 1;
3196 assembler->ClearRegisters(clear_registers_from, clear_registers_to);
3197
3198 ASSERT(trace->backtrack() == NULL);
3199 assembler->Backtrack();
3200 return;
3201 }
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003202 default:
3203 UNREACHABLE();
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003204 }
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003205}
3206
3207
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003208void BackReferenceNode::Emit(RegExpCompiler* compiler, Trace* trace) {
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003209 RegExpMacroAssembler* assembler = compiler->macro_assembler();
ager@chromium.org32912102009-01-16 10:38:43 +00003210 if (!trace->is_trivial()) {
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003211 trace->Flush(compiler, this);
3212 return;
ager@chromium.org8bb60582008-12-11 12:02:20 +00003213 }
3214
ager@chromium.org32912102009-01-16 10:38:43 +00003215 LimitResult limit_result = LimitVersions(compiler, trace);
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003216 if (limit_result == DONE) return;
ager@chromium.org8bb60582008-12-11 12:02:20 +00003217 ASSERT(limit_result == CONTINUE);
3218
3219 RecursionCheck rc(compiler);
3220
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003221 ASSERT_EQ(start_reg_ + 1, end_reg_);
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003222 if (compiler->ignore_case()) {
3223 assembler->CheckNotBackReferenceIgnoreCase(start_reg_,
3224 trace->backtrack());
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003225 } else {
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003226 assembler->CheckNotBackReference(start_reg_, trace->backtrack());
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003227 }
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003228 on_success()->Emit(compiler, trace);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003229}
3230
3231
3232// -------------------------------------------------------------------
3233// Dot/dotty output
3234
3235
3236#ifdef DEBUG
3237
3238
3239class DotPrinter: public NodeVisitor {
3240 public:
3241 explicit DotPrinter(bool ignore_case)
3242 : ignore_case_(ignore_case),
3243 stream_(&alloc_) { }
3244 void PrintNode(const char* label, RegExpNode* node);
3245 void Visit(RegExpNode* node);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003246 void PrintAttributes(RegExpNode* from);
3247 StringStream* stream() { return &stream_; }
ager@chromium.org8bb60582008-12-11 12:02:20 +00003248 void PrintOnFailure(RegExpNode* from, RegExpNode* to);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003249#define DECLARE_VISIT(Type) \
3250 virtual void Visit##Type(Type##Node* that);
3251FOR_EACH_NODE_TYPE(DECLARE_VISIT)
3252#undef DECLARE_VISIT
3253 private:
3254 bool ignore_case_;
3255 HeapStringAllocator alloc_;
3256 StringStream stream_;
3257};
3258
3259
3260void DotPrinter::PrintNode(const char* label, RegExpNode* node) {
3261 stream()->Add("digraph G {\n graph [label=\"");
3262 for (int i = 0; label[i]; i++) {
3263 switch (label[i]) {
3264 case '\\':
3265 stream()->Add("\\\\");
3266 break;
3267 case '"':
3268 stream()->Add("\"");
3269 break;
3270 default:
3271 stream()->Put(label[i]);
3272 break;
3273 }
3274 }
3275 stream()->Add("\"];\n");
3276 Visit(node);
3277 stream()->Add("}\n");
3278 printf("%s", *(stream()->ToCString()));
3279}
3280
3281
3282void DotPrinter::Visit(RegExpNode* node) {
3283 if (node->info()->visited) return;
3284 node->info()->visited = true;
3285 node->Accept(this);
3286}
3287
3288
3289void DotPrinter::PrintOnFailure(RegExpNode* from, RegExpNode* on_failure) {
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003290 stream()->Add(" n%p -> n%p [style=dotted];\n", from, on_failure);
3291 Visit(on_failure);
3292}
3293
3294
3295class TableEntryBodyPrinter {
3296 public:
3297 TableEntryBodyPrinter(StringStream* stream, ChoiceNode* choice)
3298 : stream_(stream), choice_(choice) { }
3299 void Call(uc16 from, DispatchTable::Entry entry) {
3300 OutSet* out_set = entry.out_set();
3301 for (unsigned i = 0; i < OutSet::kFirstLimit; i++) {
3302 if (out_set->Get(i)) {
3303 stream()->Add(" n%p:s%io%i -> n%p;\n",
3304 choice(),
3305 from,
3306 i,
3307 choice()->alternatives()->at(i).node());
3308 }
3309 }
3310 }
3311 private:
3312 StringStream* stream() { return stream_; }
3313 ChoiceNode* choice() { return choice_; }
3314 StringStream* stream_;
3315 ChoiceNode* choice_;
3316};
3317
3318
3319class TableEntryHeaderPrinter {
3320 public:
3321 explicit TableEntryHeaderPrinter(StringStream* stream)
3322 : first_(true), stream_(stream) { }
3323 void Call(uc16 from, DispatchTable::Entry entry) {
3324 if (first_) {
3325 first_ = false;
3326 } else {
3327 stream()->Add("|");
3328 }
3329 stream()->Add("{\\%k-\\%k|{", from, entry.to());
3330 OutSet* out_set = entry.out_set();
3331 int priority = 0;
3332 for (unsigned i = 0; i < OutSet::kFirstLimit; i++) {
3333 if (out_set->Get(i)) {
3334 if (priority > 0) stream()->Add("|");
3335 stream()->Add("<s%io%i> %i", from, i, priority);
3336 priority++;
3337 }
3338 }
3339 stream()->Add("}}");
3340 }
jkummerow@chromium.orge297f592011-06-08 10:05:15 +00003341
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003342 private:
3343 bool first_;
3344 StringStream* stream() { return stream_; }
3345 StringStream* stream_;
3346};
3347
3348
3349class AttributePrinter {
3350 public:
3351 explicit AttributePrinter(DotPrinter* out)
3352 : out_(out), first_(true) { }
3353 void PrintSeparator() {
3354 if (first_) {
3355 first_ = false;
3356 } else {
3357 out_->stream()->Add("|");
3358 }
3359 }
3360 void PrintBit(const char* name, bool value) {
3361 if (!value) return;
3362 PrintSeparator();
3363 out_->stream()->Add("{%s}", name);
3364 }
3365 void PrintPositive(const char* name, int value) {
3366 if (value < 0) return;
3367 PrintSeparator();
3368 out_->stream()->Add("{%s|%x}", name, value);
3369 }
3370 private:
3371 DotPrinter* out_;
3372 bool first_;
3373};
3374
3375
3376void DotPrinter::PrintAttributes(RegExpNode* that) {
3377 stream()->Add(" a%p [shape=Mrecord, color=grey, fontcolor=grey, "
3378 "margin=0.1, fontsize=10, label=\"{",
3379 that);
3380 AttributePrinter printer(this);
3381 NodeInfo* info = that->info();
3382 printer.PrintBit("NI", info->follows_newline_interest);
3383 printer.PrintBit("WI", info->follows_word_interest);
3384 printer.PrintBit("SI", info->follows_start_interest);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003385 Label* label = that->label();
3386 if (label->is_bound())
3387 printer.PrintPositive("@", label->pos());
3388 stream()->Add("}\"];\n");
3389 stream()->Add(" a%p -> n%p [style=dashed, color=grey, "
3390 "arrowhead=none];\n", that, that);
3391}
3392
3393
3394static const bool kPrintDispatchTable = false;
3395void DotPrinter::VisitChoice(ChoiceNode* that) {
3396 if (kPrintDispatchTable) {
3397 stream()->Add(" n%p [shape=Mrecord, label=\"", that);
3398 TableEntryHeaderPrinter header_printer(stream());
3399 that->GetTable(ignore_case_)->ForEach(&header_printer);
3400 stream()->Add("\"]\n", that);
3401 PrintAttributes(that);
3402 TableEntryBodyPrinter body_printer(stream(), that);
3403 that->GetTable(ignore_case_)->ForEach(&body_printer);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003404 } else {
3405 stream()->Add(" n%p [shape=Mrecord, label=\"?\"];\n", that);
3406 for (int i = 0; i < that->alternatives()->length(); i++) {
3407 GuardedAlternative alt = that->alternatives()->at(i);
3408 stream()->Add(" n%p -> n%p;\n", that, alt.node());
3409 }
3410 }
3411 for (int i = 0; i < that->alternatives()->length(); i++) {
3412 GuardedAlternative alt = that->alternatives()->at(i);
3413 alt.node()->Accept(this);
3414 }
3415}
3416
3417
3418void DotPrinter::VisitText(TextNode* that) {
3419 stream()->Add(" n%p [label=\"", that);
3420 for (int i = 0; i < that->elements()->length(); i++) {
3421 if (i > 0) stream()->Add(" ");
3422 TextElement elm = that->elements()->at(i);
3423 switch (elm.type) {
3424 case TextElement::ATOM: {
3425 stream()->Add("'%w'", elm.data.u_atom->data());
3426 break;
3427 }
3428 case TextElement::CHAR_CLASS: {
3429 RegExpCharacterClass* node = elm.data.u_char_class;
3430 stream()->Add("[");
3431 if (node->is_negated())
3432 stream()->Add("^");
3433 for (int j = 0; j < node->ranges()->length(); j++) {
3434 CharacterRange range = node->ranges()->at(j);
3435 stream()->Add("%k-%k", range.from(), range.to());
3436 }
3437 stream()->Add("]");
3438 break;
3439 }
3440 default:
3441 UNREACHABLE();
3442 }
3443 }
3444 stream()->Add("\", shape=box, peripheries=2];\n");
3445 PrintAttributes(that);
3446 stream()->Add(" n%p -> n%p;\n", that, that->on_success());
3447 Visit(that->on_success());
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003448}
3449
3450
3451void DotPrinter::VisitBackReference(BackReferenceNode* that) {
3452 stream()->Add(" n%p [label=\"$%i..$%i\", shape=doubleoctagon];\n",
3453 that,
3454 that->start_register(),
3455 that->end_register());
3456 PrintAttributes(that);
3457 stream()->Add(" n%p -> n%p;\n", that, that->on_success());
3458 Visit(that->on_success());
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003459}
3460
3461
3462void DotPrinter::VisitEnd(EndNode* that) {
3463 stream()->Add(" n%p [style=bold, shape=point];\n", that);
3464 PrintAttributes(that);
3465}
3466
3467
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003468void DotPrinter::VisitAssertion(AssertionNode* that) {
3469 stream()->Add(" n%p [", that);
3470 switch (that->type()) {
3471 case AssertionNode::AT_END:
3472 stream()->Add("label=\"$\", shape=septagon");
3473 break;
3474 case AssertionNode::AT_START:
3475 stream()->Add("label=\"^\", shape=septagon");
3476 break;
3477 case AssertionNode::AT_BOUNDARY:
3478 stream()->Add("label=\"\\b\", shape=septagon");
3479 break;
3480 case AssertionNode::AT_NON_BOUNDARY:
3481 stream()->Add("label=\"\\B\", shape=septagon");
3482 break;
3483 case AssertionNode::AFTER_NEWLINE:
3484 stream()->Add("label=\"(?<=\\n)\", shape=septagon");
3485 break;
fschneider@chromium.org0c20e672010-01-14 15:28:53 +00003486 case AssertionNode::AFTER_WORD_CHARACTER:
3487 stream()->Add("label=\"(?<=\\w)\", shape=septagon");
3488 break;
3489 case AssertionNode::AFTER_NONWORD_CHARACTER:
3490 stream()->Add("label=\"(?<=\\W)\", shape=septagon");
3491 break;
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003492 }
3493 stream()->Add("];\n");
3494 PrintAttributes(that);
3495 RegExpNode* successor = that->on_success();
3496 stream()->Add(" n%p -> n%p;\n", that, successor);
3497 Visit(successor);
3498}
3499
3500
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003501void DotPrinter::VisitAction(ActionNode* that) {
3502 stream()->Add(" n%p [", that);
3503 switch (that->type_) {
ager@chromium.org8bb60582008-12-11 12:02:20 +00003504 case ActionNode::SET_REGISTER:
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003505 stream()->Add("label=\"$%i:=%i\", shape=octagon",
3506 that->data_.u_store_register.reg,
3507 that->data_.u_store_register.value);
3508 break;
3509 case ActionNode::INCREMENT_REGISTER:
3510 stream()->Add("label=\"$%i++\", shape=octagon",
3511 that->data_.u_increment_register.reg);
3512 break;
3513 case ActionNode::STORE_POSITION:
3514 stream()->Add("label=\"$%i:=$pos\", shape=octagon",
3515 that->data_.u_position_register.reg);
3516 break;
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003517 case ActionNode::BEGIN_SUBMATCH:
3518 stream()->Add("label=\"$%i:=$pos,begin\", shape=septagon",
3519 that->data_.u_submatch.current_position_register);
3520 break;
ager@chromium.org8bb60582008-12-11 12:02:20 +00003521 case ActionNode::POSITIVE_SUBMATCH_SUCCESS:
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003522 stream()->Add("label=\"escape\", shape=septagon");
3523 break;
ager@chromium.org32912102009-01-16 10:38:43 +00003524 case ActionNode::EMPTY_MATCH_CHECK:
3525 stream()->Add("label=\"$%i=$pos?,$%i<%i?\", shape=septagon",
3526 that->data_.u_empty_match_check.start_register,
3527 that->data_.u_empty_match_check.repetition_register,
3528 that->data_.u_empty_match_check.repetition_limit);
3529 break;
3530 case ActionNode::CLEAR_CAPTURES: {
3531 stream()->Add("label=\"clear $%i to $%i\", shape=septagon",
3532 that->data_.u_clear_captures.range_from,
3533 that->data_.u_clear_captures.range_to);
3534 break;
3535 }
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003536 }
3537 stream()->Add("];\n");
3538 PrintAttributes(that);
ager@chromium.org8bb60582008-12-11 12:02:20 +00003539 RegExpNode* successor = that->on_success();
3540 stream()->Add(" n%p -> n%p;\n", that, successor);
3541 Visit(successor);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003542}
3543
3544
3545class DispatchTableDumper {
3546 public:
3547 explicit DispatchTableDumper(StringStream* stream) : stream_(stream) { }
3548 void Call(uc16 key, DispatchTable::Entry entry);
3549 StringStream* stream() { return stream_; }
3550 private:
3551 StringStream* stream_;
3552};
3553
3554
3555void DispatchTableDumper::Call(uc16 key, DispatchTable::Entry entry) {
3556 stream()->Add("[%k-%k]: {", key, entry.to());
3557 OutSet* set = entry.out_set();
3558 bool first = true;
3559 for (unsigned i = 0; i < OutSet::kFirstLimit; i++) {
3560 if (set->Get(i)) {
3561 if (first) {
3562 first = false;
3563 } else {
3564 stream()->Add(", ");
3565 }
3566 stream()->Add("%i", i);
3567 }
3568 }
3569 stream()->Add("}\n");
3570}
3571
3572
3573void DispatchTable::Dump() {
3574 HeapStringAllocator alloc;
3575 StringStream stream(&alloc);
3576 DispatchTableDumper dumper(&stream);
3577 tree()->ForEach(&dumper);
3578 OS::PrintError("%s", *stream.ToCString());
3579}
3580
3581
3582void RegExpEngine::DotPrint(const char* label,
3583 RegExpNode* node,
3584 bool ignore_case) {
3585 DotPrinter printer(ignore_case);
3586 printer.PrintNode(label, node);
3587}
3588
3589
3590#endif // DEBUG
3591
3592
3593// -------------------------------------------------------------------
3594// Tree to graph conversion
3595
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003596static const int kSpaceRangeCount = 20;
3597static const int kSpaceRangeAsciiCount = 4;
3598static const uc16 kSpaceRanges[kSpaceRangeCount] = { 0x0009, 0x000D, 0x0020,
3599 0x0020, 0x00A0, 0x00A0, 0x1680, 0x1680, 0x180E, 0x180E, 0x2000, 0x200A,
3600 0x2028, 0x2029, 0x202F, 0x202F, 0x205F, 0x205F, 0x3000, 0x3000 };
3601
3602static const int kWordRangeCount = 8;
3603static const uc16 kWordRanges[kWordRangeCount] = { '0', '9', 'A', 'Z', '_',
3604 '_', 'a', 'z' };
3605
3606static const int kDigitRangeCount = 2;
3607static const uc16 kDigitRanges[kDigitRangeCount] = { '0', '9' };
3608
3609static const int kLineTerminatorRangeCount = 6;
3610static const uc16 kLineTerminatorRanges[kLineTerminatorRangeCount] = { 0x000A,
3611 0x000A, 0x000D, 0x000D, 0x2028, 0x2029 };
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003612
3613RegExpNode* RegExpAtom::ToNode(RegExpCompiler* compiler,
ager@chromium.org8bb60582008-12-11 12:02:20 +00003614 RegExpNode* on_success) {
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003615 ZoneList<TextElement>* elms = new ZoneList<TextElement>(1);
3616 elms->Add(TextElement::Atom(this));
ager@chromium.org8bb60582008-12-11 12:02:20 +00003617 return new TextNode(elms, on_success);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003618}
3619
3620
3621RegExpNode* RegExpText::ToNode(RegExpCompiler* compiler,
ager@chromium.org8bb60582008-12-11 12:02:20 +00003622 RegExpNode* on_success) {
3623 return new TextNode(elements(), on_success);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003624}
3625
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003626static bool CompareInverseRanges(ZoneList<CharacterRange>* ranges,
3627 const uc16* special_class,
3628 int length) {
3629 ASSERT(ranges->length() != 0);
3630 ASSERT(length != 0);
3631 ASSERT(special_class[0] != 0);
3632 if (ranges->length() != (length >> 1) + 1) {
3633 return false;
3634 }
3635 CharacterRange range = ranges->at(0);
3636 if (range.from() != 0) {
3637 return false;
3638 }
3639 for (int i = 0; i < length; i += 2) {
3640 if (special_class[i] != (range.to() + 1)) {
3641 return false;
3642 }
3643 range = ranges->at((i >> 1) + 1);
3644 if (special_class[i+1] != range.from() - 1) {
3645 return false;
3646 }
3647 }
3648 if (range.to() != 0xffff) {
3649 return false;
3650 }
3651 return true;
3652}
3653
3654
3655static bool CompareRanges(ZoneList<CharacterRange>* ranges,
3656 const uc16* special_class,
3657 int length) {
3658 if (ranges->length() * 2 != length) {
3659 return false;
3660 }
3661 for (int i = 0; i < length; i += 2) {
3662 CharacterRange range = ranges->at(i >> 1);
3663 if (range.from() != special_class[i] || range.to() != special_class[i+1]) {
3664 return false;
3665 }
3666 }
3667 return true;
3668}
3669
3670
3671bool RegExpCharacterClass::is_standard() {
3672 // TODO(lrn): Remove need for this function, by not throwing away information
3673 // along the way.
3674 if (is_negated_) {
3675 return false;
3676 }
3677 if (set_.is_standard()) {
3678 return true;
3679 }
3680 if (CompareRanges(set_.ranges(), kSpaceRanges, kSpaceRangeCount)) {
3681 set_.set_standard_set_type('s');
3682 return true;
3683 }
3684 if (CompareInverseRanges(set_.ranges(), kSpaceRanges, kSpaceRangeCount)) {
3685 set_.set_standard_set_type('S');
3686 return true;
3687 }
3688 if (CompareInverseRanges(set_.ranges(),
3689 kLineTerminatorRanges,
3690 kLineTerminatorRangeCount)) {
3691 set_.set_standard_set_type('.');
3692 return true;
3693 }
fschneider@chromium.org0c20e672010-01-14 15:28:53 +00003694 if (CompareRanges(set_.ranges(),
3695 kLineTerminatorRanges,
3696 kLineTerminatorRangeCount)) {
3697 set_.set_standard_set_type('n');
3698 return true;
3699 }
3700 if (CompareRanges(set_.ranges(), kWordRanges, kWordRangeCount)) {
3701 set_.set_standard_set_type('w');
3702 return true;
3703 }
3704 if (CompareInverseRanges(set_.ranges(), kWordRanges, kWordRangeCount)) {
3705 set_.set_standard_set_type('W');
3706 return true;
3707 }
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003708 return false;
3709}
3710
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003711
3712RegExpNode* RegExpCharacterClass::ToNode(RegExpCompiler* compiler,
ager@chromium.org8bb60582008-12-11 12:02:20 +00003713 RegExpNode* on_success) {
3714 return new TextNode(this, on_success);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003715}
3716
3717
3718RegExpNode* RegExpDisjunction::ToNode(RegExpCompiler* compiler,
ager@chromium.org8bb60582008-12-11 12:02:20 +00003719 RegExpNode* on_success) {
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003720 ZoneList<RegExpTree*>* alternatives = this->alternatives();
3721 int length = alternatives->length();
ager@chromium.org8bb60582008-12-11 12:02:20 +00003722 ChoiceNode* result = new ChoiceNode(length);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003723 for (int i = 0; i < length; i++) {
3724 GuardedAlternative alternative(alternatives->at(i)->ToNode(compiler,
ager@chromium.org8bb60582008-12-11 12:02:20 +00003725 on_success));
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003726 result->AddAlternative(alternative);
3727 }
3728 return result;
3729}
3730
3731
3732RegExpNode* RegExpQuantifier::ToNode(RegExpCompiler* compiler,
ager@chromium.org8bb60582008-12-11 12:02:20 +00003733 RegExpNode* on_success) {
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003734 return ToNode(min(),
3735 max(),
3736 is_greedy(),
3737 body(),
3738 compiler,
ager@chromium.org8bb60582008-12-11 12:02:20 +00003739 on_success);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003740}
3741
3742
whesse@chromium.org7b260152011-06-20 15:33:18 +00003743// Scoped object to keep track of how much we unroll quantifier loops in the
3744// regexp graph generator.
3745class RegExpExpansionLimiter {
3746 public:
3747 static const int kMaxExpansionFactor = 6;
3748 RegExpExpansionLimiter(RegExpCompiler* compiler, int factor)
3749 : compiler_(compiler),
3750 saved_expansion_factor_(compiler->current_expansion_factor()),
3751 ok_to_expand_(saved_expansion_factor_ <= kMaxExpansionFactor) {
3752 ASSERT(factor > 0);
3753 if (ok_to_expand_) {
3754 if (factor > kMaxExpansionFactor) {
3755 // Avoid integer overflow of the current expansion factor.
3756 ok_to_expand_ = false;
3757 compiler->set_current_expansion_factor(kMaxExpansionFactor + 1);
3758 } else {
3759 int new_factor = saved_expansion_factor_ * factor;
3760 ok_to_expand_ = (new_factor <= kMaxExpansionFactor);
3761 compiler->set_current_expansion_factor(new_factor);
3762 }
3763 }
3764 }
3765
3766 ~RegExpExpansionLimiter() {
3767 compiler_->set_current_expansion_factor(saved_expansion_factor_);
3768 }
3769
3770 bool ok_to_expand() { return ok_to_expand_; }
3771
3772 private:
3773 RegExpCompiler* compiler_;
3774 int saved_expansion_factor_;
3775 bool ok_to_expand_;
3776
3777 DISALLOW_IMPLICIT_CONSTRUCTORS(RegExpExpansionLimiter);
3778};
3779
3780
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003781RegExpNode* RegExpQuantifier::ToNode(int min,
3782 int max,
3783 bool is_greedy,
3784 RegExpTree* body,
3785 RegExpCompiler* compiler,
iposva@chromium.org245aa852009-02-10 00:49:54 +00003786 RegExpNode* on_success,
3787 bool not_at_start) {
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003788 // x{f, t} becomes this:
3789 //
3790 // (r++)<-.
3791 // | `
3792 // | (x)
3793 // v ^
3794 // (r=0)-->(?)---/ [if r < t]
3795 // |
3796 // [if r >= f] \----> ...
3797 //
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003798
3799 // 15.10.2.5 RepeatMatcher algorithm.
3800 // The parser has already eliminated the case where max is 0. In the case
3801 // where max_match is zero the parser has removed the quantifier if min was
3802 // > 0 and removed the atom if min was 0. See AddQuantifierToAtom.
3803
3804 // If we know that we cannot match zero length then things are a little
3805 // simpler since we don't need to make the special zero length match check
3806 // from step 2.1. If the min and max are small we can unroll a little in
3807 // this case.
3808 static const int kMaxUnrolledMinMatches = 3; // Unroll (foo)+ and (foo){3,}
3809 static const int kMaxUnrolledMaxMatches = 3; // Unroll (foo)? and (foo){x,3}
3810 if (max == 0) return on_success; // This can happen due to recursion.
ager@chromium.org32912102009-01-16 10:38:43 +00003811 bool body_can_be_empty = (body->min_match() == 0);
3812 int body_start_reg = RegExpCompiler::kNoRegister;
3813 Interval capture_registers = body->CaptureRegisters();
3814 bool needs_capture_clearing = !capture_registers.is_empty();
3815 if (body_can_be_empty) {
3816 body_start_reg = compiler->AllocateRegister();
ager@chromium.org381abbb2009-02-25 13:23:22 +00003817 } else if (FLAG_regexp_optimization && !needs_capture_clearing) {
ager@chromium.org32912102009-01-16 10:38:43 +00003818 // Only unroll if there are no captures and the body can't be
3819 // empty.
whesse@chromium.org7b260152011-06-20 15:33:18 +00003820 {
3821 RegExpExpansionLimiter limiter(
3822 compiler, min + ((max != min) ? 1 : 0));
3823 if (min > 0 && min <= kMaxUnrolledMinMatches && limiter.ok_to_expand()) {
3824 int new_max = (max == kInfinity) ? max : max - min;
3825 // Recurse once to get the loop or optional matches after the fixed
3826 // ones.
3827 RegExpNode* answer = ToNode(
3828 0, new_max, is_greedy, body, compiler, on_success, true);
3829 // Unroll the forced matches from 0 to min. This can cause chains of
3830 // TextNodes (which the parser does not generate). These should be
3831 // combined if it turns out they hinder good code generation.
3832 for (int i = 0; i < min; i++) {
3833 answer = body->ToNode(compiler, answer);
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003834 }
whesse@chromium.org7b260152011-06-20 15:33:18 +00003835 return answer;
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003836 }
whesse@chromium.org7b260152011-06-20 15:33:18 +00003837 }
3838 if (max <= kMaxUnrolledMaxMatches && min == 0) {
3839 ASSERT(max > 0); // Due to the 'if' above.
3840 RegExpExpansionLimiter limiter(compiler, max);
3841 if (limiter.ok_to_expand()) {
3842 // Unroll the optional matches up to max.
3843 RegExpNode* answer = on_success;
3844 for (int i = 0; i < max; i++) {
3845 ChoiceNode* alternation = new ChoiceNode(2);
3846 if (is_greedy) {
3847 alternation->AddAlternative(
3848 GuardedAlternative(body->ToNode(compiler, answer)));
3849 alternation->AddAlternative(GuardedAlternative(on_success));
3850 } else {
3851 alternation->AddAlternative(GuardedAlternative(on_success));
3852 alternation->AddAlternative(
3853 GuardedAlternative(body->ToNode(compiler, answer)));
3854 }
3855 answer = alternation;
3856 if (not_at_start) alternation->set_not_at_start();
3857 }
3858 return answer;
3859 }
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003860 }
3861 }
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003862 bool has_min = min > 0;
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003863 bool has_max = max < RegExpTree::kInfinity;
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003864 bool needs_counter = has_min || has_max;
ager@chromium.org32912102009-01-16 10:38:43 +00003865 int reg_ctr = needs_counter
3866 ? compiler->AllocateRegister()
3867 : RegExpCompiler::kNoRegister;
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003868 LoopChoiceNode* center = new LoopChoiceNode(body->min_match() == 0);
iposva@chromium.org245aa852009-02-10 00:49:54 +00003869 if (not_at_start) center->set_not_at_start();
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003870 RegExpNode* loop_return = needs_counter
3871 ? static_cast<RegExpNode*>(ActionNode::IncrementRegister(reg_ctr, center))
3872 : static_cast<RegExpNode*>(center);
ager@chromium.org32912102009-01-16 10:38:43 +00003873 if (body_can_be_empty) {
3874 // If the body can be empty we need to check if it was and then
3875 // backtrack.
3876 loop_return = ActionNode::EmptyMatchCheck(body_start_reg,
3877 reg_ctr,
3878 min,
3879 loop_return);
3880 }
ager@chromium.org8bb60582008-12-11 12:02:20 +00003881 RegExpNode* body_node = body->ToNode(compiler, loop_return);
ager@chromium.org32912102009-01-16 10:38:43 +00003882 if (body_can_be_empty) {
3883 // If the body can be empty we need to store the start position
3884 // so we can bail out if it was empty.
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003885 body_node = ActionNode::StorePosition(body_start_reg, false, body_node);
ager@chromium.org32912102009-01-16 10:38:43 +00003886 }
3887 if (needs_capture_clearing) {
3888 // Before entering the body of this loop we need to clear captures.
3889 body_node = ActionNode::ClearCaptures(capture_registers, body_node);
3890 }
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003891 GuardedAlternative body_alt(body_node);
3892 if (has_max) {
3893 Guard* body_guard = new Guard(reg_ctr, Guard::LT, max);
3894 body_alt.AddGuard(body_guard);
3895 }
3896 GuardedAlternative rest_alt(on_success);
3897 if (has_min) {
3898 Guard* rest_guard = new Guard(reg_ctr, Guard::GEQ, min);
3899 rest_alt.AddGuard(rest_guard);
3900 }
3901 if (is_greedy) {
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003902 center->AddLoopAlternative(body_alt);
3903 center->AddContinueAlternative(rest_alt);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003904 } else {
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00003905 center->AddContinueAlternative(rest_alt);
3906 center->AddLoopAlternative(body_alt);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003907 }
3908 if (needs_counter) {
ager@chromium.org8bb60582008-12-11 12:02:20 +00003909 return ActionNode::SetRegister(reg_ctr, 0, center);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003910 } else {
3911 return center;
3912 }
3913}
3914
3915
3916RegExpNode* RegExpAssertion::ToNode(RegExpCompiler* compiler,
ager@chromium.org8bb60582008-12-11 12:02:20 +00003917 RegExpNode* on_success) {
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003918 NodeInfo info;
3919 switch (type()) {
3920 case START_OF_LINE:
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003921 return AssertionNode::AfterNewline(on_success);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003922 case START_OF_INPUT:
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003923 return AssertionNode::AtStart(on_success);
3924 case BOUNDARY:
3925 return AssertionNode::AtBoundary(on_success);
3926 case NON_BOUNDARY:
3927 return AssertionNode::AtNonBoundary(on_success);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003928 case END_OF_INPUT:
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003929 return AssertionNode::AtEnd(on_success);
3930 case END_OF_LINE: {
3931 // Compile $ in multiline regexps as an alternation with a positive
3932 // lookahead in one side and an end-of-input on the other side.
3933 // We need two registers for the lookahead.
3934 int stack_pointer_register = compiler->AllocateRegister();
3935 int position_register = compiler->AllocateRegister();
3936 // The ChoiceNode to distinguish between a newline and end-of-input.
3937 ChoiceNode* result = new ChoiceNode(2);
3938 // Create a newline atom.
3939 ZoneList<CharacterRange>* newline_ranges =
3940 new ZoneList<CharacterRange>(3);
3941 CharacterRange::AddClassEscape('n', newline_ranges);
3942 RegExpCharacterClass* newline_atom = new RegExpCharacterClass('n');
3943 TextNode* newline_matcher = new TextNode(
3944 newline_atom,
3945 ActionNode::PositiveSubmatchSuccess(stack_pointer_register,
3946 position_register,
3947 0, // No captures inside.
3948 -1, // Ignored if no captures.
3949 on_success));
3950 // Create an end-of-input matcher.
3951 RegExpNode* end_of_line = ActionNode::BeginSubmatch(
3952 stack_pointer_register,
3953 position_register,
3954 newline_matcher);
3955 // Add the two alternatives to the ChoiceNode.
3956 GuardedAlternative eol_alternative(end_of_line);
3957 result->AddAlternative(eol_alternative);
3958 GuardedAlternative end_alternative(AssertionNode::AtEnd(on_success));
3959 result->AddAlternative(end_alternative);
3960 return result;
3961 }
3962 default:
3963 UNREACHABLE();
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003964 }
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003965 return on_success;
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003966}
3967
3968
3969RegExpNode* RegExpBackReference::ToNode(RegExpCompiler* compiler,
ager@chromium.org8bb60582008-12-11 12:02:20 +00003970 RegExpNode* on_success) {
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003971 return new BackReferenceNode(RegExpCapture::StartRegister(index()),
3972 RegExpCapture::EndRegister(index()),
ager@chromium.org8bb60582008-12-11 12:02:20 +00003973 on_success);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003974}
3975
3976
3977RegExpNode* RegExpEmpty::ToNode(RegExpCompiler* compiler,
ager@chromium.org8bb60582008-12-11 12:02:20 +00003978 RegExpNode* on_success) {
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003979 return on_success;
3980}
3981
3982
3983RegExpNode* RegExpLookahead::ToNode(RegExpCompiler* compiler,
ager@chromium.org8bb60582008-12-11 12:02:20 +00003984 RegExpNode* on_success) {
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003985 int stack_pointer_register = compiler->AllocateRegister();
3986 int position_register = compiler->AllocateRegister();
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003987
3988 const int registers_per_capture = 2;
3989 const int register_of_first_capture = 2;
3990 int register_count = capture_count_ * registers_per_capture;
3991 int register_start =
3992 register_of_first_capture + capture_from_ * registers_per_capture;
3993
ager@chromium.org8bb60582008-12-11 12:02:20 +00003994 RegExpNode* success;
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003995 if (is_positive()) {
ager@chromium.orgddb913d2009-01-27 10:01:48 +00003996 RegExpNode* node = ActionNode::BeginSubmatch(
ager@chromium.orga74f0da2008-12-03 16:05:52 +00003997 stack_pointer_register,
3998 position_register,
3999 body()->ToNode(
4000 compiler,
ager@chromium.org8bb60582008-12-11 12:02:20 +00004001 ActionNode::PositiveSubmatchSuccess(stack_pointer_register,
4002 position_register,
ager@chromium.orgddb913d2009-01-27 10:01:48 +00004003 register_count,
4004 register_start,
ager@chromium.org8bb60582008-12-11 12:02:20 +00004005 on_success)));
ager@chromium.orgddb913d2009-01-27 10:01:48 +00004006 return node;
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004007 } else {
ager@chromium.org8bb60582008-12-11 12:02:20 +00004008 // We use a ChoiceNode for a negative lookahead because it has most of
4009 // the characteristics we need. It has the body of the lookahead as its
4010 // first alternative and the expression after the lookahead of the second
4011 // alternative. If the first alternative succeeds then the
4012 // NegativeSubmatchSuccess will unwind the stack including everything the
4013 // choice node set up and backtrack. If the first alternative fails then
4014 // the second alternative is tried, which is exactly the desired result
ager@chromium.orgddb913d2009-01-27 10:01:48 +00004015 // for a negative lookahead. The NegativeLookaheadChoiceNode is a special
4016 // ChoiceNode that knows to ignore the first exit when calculating quick
4017 // checks.
ager@chromium.org8bb60582008-12-11 12:02:20 +00004018 GuardedAlternative body_alt(
4019 body()->ToNode(
4020 compiler,
4021 success = new NegativeSubmatchSuccess(stack_pointer_register,
ager@chromium.orgddb913d2009-01-27 10:01:48 +00004022 position_register,
4023 register_count,
4024 register_start)));
4025 ChoiceNode* choice_node =
4026 new NegativeLookaheadChoiceNode(body_alt,
4027 GuardedAlternative(on_success));
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004028 return ActionNode::BeginSubmatch(stack_pointer_register,
4029 position_register,
ager@chromium.org8bb60582008-12-11 12:02:20 +00004030 choice_node);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004031 }
4032}
4033
4034
4035RegExpNode* RegExpCapture::ToNode(RegExpCompiler* compiler,
ager@chromium.org8bb60582008-12-11 12:02:20 +00004036 RegExpNode* on_success) {
4037 return ToNode(body(), index(), compiler, on_success);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004038}
4039
4040
4041RegExpNode* RegExpCapture::ToNode(RegExpTree* body,
4042 int index,
4043 RegExpCompiler* compiler,
ager@chromium.org8bb60582008-12-11 12:02:20 +00004044 RegExpNode* on_success) {
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004045 int start_reg = RegExpCapture::StartRegister(index);
4046 int end_reg = RegExpCapture::EndRegister(index);
ager@chromium.orgddb913d2009-01-27 10:01:48 +00004047 RegExpNode* store_end = ActionNode::StorePosition(end_reg, true, on_success);
ager@chromium.org8bb60582008-12-11 12:02:20 +00004048 RegExpNode* body_node = body->ToNode(compiler, store_end);
ager@chromium.orgddb913d2009-01-27 10:01:48 +00004049 return ActionNode::StorePosition(start_reg, true, body_node);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004050}
4051
4052
4053RegExpNode* RegExpAlternative::ToNode(RegExpCompiler* compiler,
ager@chromium.org8bb60582008-12-11 12:02:20 +00004054 RegExpNode* on_success) {
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004055 ZoneList<RegExpTree*>* children = nodes();
4056 RegExpNode* current = on_success;
4057 for (int i = children->length() - 1; i >= 0; i--) {
ager@chromium.org8bb60582008-12-11 12:02:20 +00004058 current = children->at(i)->ToNode(compiler, current);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004059 }
4060 return current;
4061}
4062
4063
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004064static void AddClass(const uc16* elmv,
4065 int elmc,
4066 ZoneList<CharacterRange>* ranges) {
4067 for (int i = 0; i < elmc; i += 2) {
4068 ASSERT(elmv[i] <= elmv[i + 1]);
4069 ranges->Add(CharacterRange(elmv[i], elmv[i + 1]));
4070 }
4071}
4072
4073
4074static void AddClassNegated(const uc16 *elmv,
4075 int elmc,
4076 ZoneList<CharacterRange>* ranges) {
4077 ASSERT(elmv[0] != 0x0000);
ager@chromium.org8bb60582008-12-11 12:02:20 +00004078 ASSERT(elmv[elmc-1] != String::kMaxUC16CharCode);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004079 uc16 last = 0x0000;
4080 for (int i = 0; i < elmc; i += 2) {
4081 ASSERT(last <= elmv[i] - 1);
4082 ASSERT(elmv[i] <= elmv[i + 1]);
4083 ranges->Add(CharacterRange(last, elmv[i] - 1));
4084 last = elmv[i + 1] + 1;
4085 }
ager@chromium.org8bb60582008-12-11 12:02:20 +00004086 ranges->Add(CharacterRange(last, String::kMaxUC16CharCode));
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004087}
4088
4089
4090void CharacterRange::AddClassEscape(uc16 type,
4091 ZoneList<CharacterRange>* ranges) {
4092 switch (type) {
4093 case 's':
4094 AddClass(kSpaceRanges, kSpaceRangeCount, ranges);
4095 break;
4096 case 'S':
4097 AddClassNegated(kSpaceRanges, kSpaceRangeCount, ranges);
4098 break;
4099 case 'w':
4100 AddClass(kWordRanges, kWordRangeCount, ranges);
4101 break;
4102 case 'W':
4103 AddClassNegated(kWordRanges, kWordRangeCount, ranges);
4104 break;
4105 case 'd':
4106 AddClass(kDigitRanges, kDigitRangeCount, ranges);
4107 break;
4108 case 'D':
4109 AddClassNegated(kDigitRanges, kDigitRangeCount, ranges);
4110 break;
4111 case '.':
4112 AddClassNegated(kLineTerminatorRanges,
4113 kLineTerminatorRangeCount,
4114 ranges);
4115 break;
4116 // This is not a character range as defined by the spec but a
4117 // convenient shorthand for a character class that matches any
4118 // character.
4119 case '*':
4120 ranges->Add(CharacterRange::Everything());
4121 break;
ager@chromium.orgddb913d2009-01-27 10:01:48 +00004122 // This is the set of characters matched by the $ and ^ symbols
4123 // in multiline mode.
4124 case 'n':
4125 AddClass(kLineTerminatorRanges,
4126 kLineTerminatorRangeCount,
4127 ranges);
4128 break;
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004129 default:
4130 UNREACHABLE();
4131 }
4132}
4133
4134
4135Vector<const uc16> CharacterRange::GetWordBounds() {
4136 return Vector<const uc16>(kWordRanges, kWordRangeCount);
4137}
4138
4139
4140class CharacterRangeSplitter {
4141 public:
4142 CharacterRangeSplitter(ZoneList<CharacterRange>** included,
4143 ZoneList<CharacterRange>** excluded)
4144 : included_(included),
4145 excluded_(excluded) { }
4146 void Call(uc16 from, DispatchTable::Entry entry);
4147
4148 static const int kInBase = 0;
4149 static const int kInOverlay = 1;
4150
4151 private:
4152 ZoneList<CharacterRange>** included_;
4153 ZoneList<CharacterRange>** excluded_;
4154};
4155
4156
4157void CharacterRangeSplitter::Call(uc16 from, DispatchTable::Entry entry) {
4158 if (!entry.out_set()->Get(kInBase)) return;
4159 ZoneList<CharacterRange>** target = entry.out_set()->Get(kInOverlay)
4160 ? included_
4161 : excluded_;
4162 if (*target == NULL) *target = new ZoneList<CharacterRange>(2);
4163 (*target)->Add(CharacterRange(entry.from(), entry.to()));
4164}
4165
4166
4167void CharacterRange::Split(ZoneList<CharacterRange>* base,
4168 Vector<const uc16> overlay,
4169 ZoneList<CharacterRange>** included,
4170 ZoneList<CharacterRange>** excluded) {
4171 ASSERT_EQ(NULL, *included);
4172 ASSERT_EQ(NULL, *excluded);
4173 DispatchTable table;
4174 for (int i = 0; i < base->length(); i++)
4175 table.AddRange(base->at(i), CharacterRangeSplitter::kInBase);
4176 for (int i = 0; i < overlay.length(); i += 2) {
4177 table.AddRange(CharacterRange(overlay[i], overlay[i+1]),
4178 CharacterRangeSplitter::kInOverlay);
4179 }
4180 CharacterRangeSplitter callback(included, excluded);
4181 table.ForEach(&callback);
4182}
4183
4184
ager@chromium.org38e4c712009-11-11 09:11:58 +00004185void CharacterRange::AddCaseEquivalents(ZoneList<CharacterRange>* ranges,
4186 bool is_ascii) {
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +00004187 Isolate* isolate = Isolate::Current();
ager@chromium.org38e4c712009-11-11 09:11:58 +00004188 uc16 bottom = from();
4189 uc16 top = to();
4190 if (is_ascii) {
4191 if (bottom > String::kMaxAsciiCharCode) return;
4192 if (top > String::kMaxAsciiCharCode) top = String::kMaxAsciiCharCode;
4193 }
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004194 unibrow::uchar chars[unibrow::Ecma262UnCanonicalize::kMaxWidth];
ager@chromium.org38e4c712009-11-11 09:11:58 +00004195 if (top == bottom) {
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004196 // If this is a singleton we just expand the one character.
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +00004197 int length = isolate->jsregexp_uncanonicalize()->get(bottom, '\0', chars);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004198 for (int i = 0; i < length; i++) {
4199 uc32 chr = chars[i];
ager@chromium.org38e4c712009-11-11 09:11:58 +00004200 if (chr != bottom) {
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004201 ranges->Add(CharacterRange::Singleton(chars[i]));
4202 }
4203 }
whesse@chromium.orge90029b2010-08-02 11:52:17 +00004204 } else {
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004205 // If this is a range we expand the characters block by block,
4206 // expanding contiguous subranges (blocks) one at a time.
4207 // The approach is as follows. For a given start character we
whesse@chromium.orge90029b2010-08-02 11:52:17 +00004208 // look up the remainder of the block that contains it (represented
4209 // by the end point), for instance we find 'z' if the character
4210 // is 'c'. A block is characterized by the property
4211 // that all characters uncanonicalize in the same way, except that
4212 // each entry in the result is incremented by the distance from the first
4213 // element. So a-z is a block because 'a' uncanonicalizes to ['a', 'A'] and
4214 // the k'th letter uncanonicalizes to ['a' + k, 'A' + k].
4215 // Once we've found the end point we look up its uncanonicalization
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004216 // and produce a range for each element. For instance for [c-f]
whesse@chromium.orge90029b2010-08-02 11:52:17 +00004217 // we look up ['z', 'Z'] and produce [c-f] and [C-F]. We then only
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004218 // add a range if it is not already contained in the input, so [c-f]
4219 // will be skipped but [C-F] will be added. If this range is not
4220 // completely contained in a block we do this for all the blocks
whesse@chromium.orge90029b2010-08-02 11:52:17 +00004221 // covered by the range (handling characters that is not in a block
4222 // as a "singleton block").
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004223 unibrow::uchar range[unibrow::Ecma262UnCanonicalize::kMaxWidth];
ager@chromium.org38e4c712009-11-11 09:11:58 +00004224 int pos = bottom;
ager@chromium.org38e4c712009-11-11 09:11:58 +00004225 while (pos < top) {
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +00004226 int length = isolate->jsregexp_canonrange()->get(pos, '\0', range);
whesse@chromium.orge90029b2010-08-02 11:52:17 +00004227 uc16 block_end;
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004228 if (length == 0) {
whesse@chromium.orge90029b2010-08-02 11:52:17 +00004229 block_end = pos;
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004230 } else {
4231 ASSERT_EQ(1, length);
whesse@chromium.orge90029b2010-08-02 11:52:17 +00004232 block_end = range[0];
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004233 }
ager@chromium.org38e4c712009-11-11 09:11:58 +00004234 int end = (block_end > top) ? top : block_end;
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +00004235 length = isolate->jsregexp_uncanonicalize()->get(block_end, '\0', range);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004236 for (int i = 0; i < length; i++) {
4237 uc32 c = range[i];
whesse@chromium.orge90029b2010-08-02 11:52:17 +00004238 uc16 range_from = c - (block_end - pos);
4239 uc16 range_to = c - (block_end - end);
ager@chromium.org38e4c712009-11-11 09:11:58 +00004240 if (!(bottom <= range_from && range_to <= top)) {
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004241 ranges->Add(CharacterRange(range_from, range_to));
4242 }
4243 }
whesse@chromium.orge90029b2010-08-02 11:52:17 +00004244 pos = end + 1;
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004245 }
ager@chromium.org38e4c712009-11-11 09:11:58 +00004246 }
4247}
4248
4249
fschneider@chromium.org0c20e672010-01-14 15:28:53 +00004250bool CharacterRange::IsCanonical(ZoneList<CharacterRange>* ranges) {
4251 ASSERT_NOT_NULL(ranges);
4252 int n = ranges->length();
4253 if (n <= 1) return true;
4254 int max = ranges->at(0).to();
4255 for (int i = 1; i < n; i++) {
4256 CharacterRange next_range = ranges->at(i);
4257 if (next_range.from() <= max + 1) return false;
4258 max = next_range.to();
4259 }
4260 return true;
4261}
4262
4263SetRelation CharacterRange::WordCharacterRelation(
4264 ZoneList<CharacterRange>* range) {
4265 ASSERT(IsCanonical(range));
4266 int i = 0; // Word character range index.
4267 int j = 0; // Argument range index.
4268 ASSERT_NE(0, kWordRangeCount);
4269 SetRelation result;
4270 if (range->length() == 0) {
4271 result.SetElementsInSecondSet();
4272 return result;
4273 }
4274 CharacterRange argument_range = range->at(0);
4275 CharacterRange word_range = CharacterRange(kWordRanges[0], kWordRanges[1]);
4276 while (i < kWordRangeCount && j < range->length()) {
4277 // Check the two ranges for the five cases:
4278 // - no overlap.
4279 // - partial overlap (there are elements in both ranges that isn't
4280 // in the other, and there are also elements that are in both).
4281 // - argument range entirely inside word range.
4282 // - word range entirely inside argument range.
4283 // - ranges are completely equal.
4284
4285 // First check for no overlap. The earlier range is not in the other set.
4286 if (argument_range.from() > word_range.to()) {
4287 // Ranges are disjoint. The earlier word range contains elements that
4288 // cannot be in the argument set.
4289 result.SetElementsInSecondSet();
4290 } else if (word_range.from() > argument_range.to()) {
4291 // Ranges are disjoint. The earlier argument range contains elements that
4292 // cannot be in the word set.
4293 result.SetElementsInFirstSet();
4294 } else if (word_range.from() <= argument_range.from() &&
4295 word_range.to() >= argument_range.from()) {
4296 result.SetElementsInBothSets();
4297 // argument range completely inside word range.
4298 if (word_range.from() < argument_range.from() ||
4299 word_range.to() > argument_range.from()) {
4300 result.SetElementsInSecondSet();
4301 }
4302 } else if (word_range.from() >= argument_range.from() &&
4303 word_range.to() <= argument_range.from()) {
4304 result.SetElementsInBothSets();
4305 result.SetElementsInFirstSet();
4306 } else {
4307 // There is overlap, and neither is a subrange of the other
4308 result.SetElementsInFirstSet();
4309 result.SetElementsInSecondSet();
4310 result.SetElementsInBothSets();
4311 }
4312 if (result.NonTrivialIntersection()) {
4313 // The result is as (im)precise as we can possibly make it.
4314 return result;
4315 }
4316 // Progress the range(s) with minimal to-character.
4317 uc16 word_to = word_range.to();
4318 uc16 argument_to = argument_range.to();
4319 if (argument_to <= word_to) {
4320 j++;
4321 if (j < range->length()) {
4322 argument_range = range->at(j);
4323 }
4324 }
4325 if (word_to <= argument_to) {
4326 i += 2;
4327 if (i < kWordRangeCount) {
4328 word_range = CharacterRange(kWordRanges[i], kWordRanges[i + 1]);
4329 }
4330 }
4331 }
4332 // Check if anything wasn't compared in the loop.
4333 if (i < kWordRangeCount) {
4334 // word range contains something not in argument range.
4335 result.SetElementsInSecondSet();
4336 } else if (j < range->length()) {
4337 // Argument range contains something not in word range.
4338 result.SetElementsInFirstSet();
4339 }
4340
4341 return result;
4342}
4343
4344
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00004345ZoneList<CharacterRange>* CharacterSet::ranges() {
4346 if (ranges_ == NULL) {
4347 ranges_ = new ZoneList<CharacterRange>(2);
4348 CharacterRange::AddClassEscape(standard_set_type_, ranges_);
4349 }
4350 return ranges_;
4351}
4352
4353
fschneider@chromium.org0c20e672010-01-14 15:28:53 +00004354// Move a number of elements in a zonelist to another position
4355// in the same list. Handles overlapping source and target areas.
4356static void MoveRanges(ZoneList<CharacterRange>* list,
4357 int from,
4358 int to,
4359 int count) {
4360 // Ranges are potentially overlapping.
4361 if (from < to) {
4362 for (int i = count - 1; i >= 0; i--) {
4363 list->at(to + i) = list->at(from + i);
4364 }
4365 } else {
4366 for (int i = 0; i < count; i++) {
4367 list->at(to + i) = list->at(from + i);
4368 }
4369 }
4370}
4371
4372
4373static int InsertRangeInCanonicalList(ZoneList<CharacterRange>* list,
4374 int count,
4375 CharacterRange insert) {
4376 // Inserts a range into list[0..count[, which must be sorted
4377 // by from value and non-overlapping and non-adjacent, using at most
4378 // list[0..count] for the result. Returns the number of resulting
4379 // canonicalized ranges. Inserting a range may collapse existing ranges into
4380 // fewer ranges, so the return value can be anything in the range 1..count+1.
4381 uc16 from = insert.from();
4382 uc16 to = insert.to();
4383 int start_pos = 0;
4384 int end_pos = count;
4385 for (int i = count - 1; i >= 0; i--) {
4386 CharacterRange current = list->at(i);
4387 if (current.from() > to + 1) {
4388 end_pos = i;
4389 } else if (current.to() + 1 < from) {
4390 start_pos = i + 1;
4391 break;
4392 }
4393 }
4394
4395 // Inserted range overlaps, or is adjacent to, ranges at positions
4396 // [start_pos..end_pos[. Ranges before start_pos or at or after end_pos are
4397 // not affected by the insertion.
4398 // If start_pos == end_pos, the range must be inserted before start_pos.
4399 // if start_pos < end_pos, the entire range from start_pos to end_pos
4400 // must be merged with the insert range.
4401
4402 if (start_pos == end_pos) {
4403 // Insert between existing ranges at position start_pos.
4404 if (start_pos < count) {
4405 MoveRanges(list, start_pos, start_pos + 1, count - start_pos);
4406 }
4407 list->at(start_pos) = insert;
4408 return count + 1;
4409 }
4410 if (start_pos + 1 == end_pos) {
4411 // Replace single existing range at position start_pos.
4412 CharacterRange to_replace = list->at(start_pos);
4413 int new_from = Min(to_replace.from(), from);
4414 int new_to = Max(to_replace.to(), to);
4415 list->at(start_pos) = CharacterRange(new_from, new_to);
4416 return count;
4417 }
4418 // Replace a number of existing ranges from start_pos to end_pos - 1.
4419 // Move the remaining ranges down.
4420
4421 int new_from = Min(list->at(start_pos).from(), from);
4422 int new_to = Max(list->at(end_pos - 1).to(), to);
4423 if (end_pos < count) {
4424 MoveRanges(list, end_pos, start_pos + 1, count - end_pos);
4425 }
4426 list->at(start_pos) = CharacterRange(new_from, new_to);
4427 return count - (end_pos - start_pos) + 1;
4428}
4429
4430
4431void CharacterSet::Canonicalize() {
4432 // Special/default classes are always considered canonical. The result
4433 // of calling ranges() will be sorted.
4434 if (ranges_ == NULL) return;
4435 CharacterRange::Canonicalize(ranges_);
4436}
4437
4438
4439void CharacterRange::Canonicalize(ZoneList<CharacterRange>* character_ranges) {
4440 if (character_ranges->length() <= 1) return;
4441 // Check whether ranges are already canonical (increasing, non-overlapping,
4442 // non-adjacent).
4443 int n = character_ranges->length();
4444 int max = character_ranges->at(0).to();
4445 int i = 1;
4446 while (i < n) {
4447 CharacterRange current = character_ranges->at(i);
4448 if (current.from() <= max + 1) {
4449 break;
4450 }
4451 max = current.to();
4452 i++;
4453 }
4454 // Canonical until the i'th range. If that's all of them, we are done.
4455 if (i == n) return;
4456
4457 // The ranges at index i and forward are not canonicalized. Make them so by
4458 // doing the equivalent of insertion sort (inserting each into the previous
4459 // list, in order).
4460 // Notice that inserting a range can reduce the number of ranges in the
4461 // result due to combining of adjacent and overlapping ranges.
4462 int read = i; // Range to insert.
4463 int num_canonical = i; // Length of canonicalized part of list.
4464 do {
4465 num_canonical = InsertRangeInCanonicalList(character_ranges,
4466 num_canonical,
4467 character_ranges->at(read));
4468 read++;
4469 } while (read < n);
4470 character_ranges->Rewind(num_canonical);
4471
4472 ASSERT(CharacterRange::IsCanonical(character_ranges));
4473}
4474
4475
4476// Utility function for CharacterRange::Merge. Adds a range at the end of
4477// a canonicalized range list, if necessary merging the range with the last
4478// range of the list.
4479static void AddRangeToSet(ZoneList<CharacterRange>* set, CharacterRange range) {
4480 if (set == NULL) return;
4481 ASSERT(set->length() == 0 || set->at(set->length() - 1).to() < range.from());
4482 int n = set->length();
4483 if (n > 0) {
4484 CharacterRange lastRange = set->at(n - 1);
4485 if (lastRange.to() == range.from() - 1) {
4486 set->at(n - 1) = CharacterRange(lastRange.from(), range.to());
4487 return;
4488 }
4489 }
4490 set->Add(range);
4491}
4492
4493
4494static void AddRangeToSelectedSet(int selector,
4495 ZoneList<CharacterRange>* first_set,
4496 ZoneList<CharacterRange>* second_set,
4497 ZoneList<CharacterRange>* intersection_set,
4498 CharacterRange range) {
4499 switch (selector) {
4500 case kInsideFirst:
4501 AddRangeToSet(first_set, range);
4502 break;
4503 case kInsideSecond:
4504 AddRangeToSet(second_set, range);
4505 break;
4506 case kInsideBoth:
4507 AddRangeToSet(intersection_set, range);
4508 break;
4509 }
4510}
4511
4512
4513
4514void CharacterRange::Merge(ZoneList<CharacterRange>* first_set,
4515 ZoneList<CharacterRange>* second_set,
4516 ZoneList<CharacterRange>* first_set_only_out,
4517 ZoneList<CharacterRange>* second_set_only_out,
4518 ZoneList<CharacterRange>* both_sets_out) {
4519 // Inputs are canonicalized.
4520 ASSERT(CharacterRange::IsCanonical(first_set));
4521 ASSERT(CharacterRange::IsCanonical(second_set));
4522 // Outputs are empty, if applicable.
4523 ASSERT(first_set_only_out == NULL || first_set_only_out->length() == 0);
4524 ASSERT(second_set_only_out == NULL || second_set_only_out->length() == 0);
4525 ASSERT(both_sets_out == NULL || both_sets_out->length() == 0);
4526
4527 // Merge sets by iterating through the lists in order of lowest "from" value,
4528 // and putting intervals into one of three sets.
4529
4530 if (first_set->length() == 0) {
4531 second_set_only_out->AddAll(*second_set);
4532 return;
4533 }
4534 if (second_set->length() == 0) {
4535 first_set_only_out->AddAll(*first_set);
4536 return;
4537 }
4538 // Indices into input lists.
4539 int i1 = 0;
4540 int i2 = 0;
4541 // Cache length of input lists.
4542 int n1 = first_set->length();
4543 int n2 = second_set->length();
4544 // Current range. May be invalid if state is kInsideNone.
4545 int from = 0;
4546 int to = -1;
4547 // Where current range comes from.
4548 int state = kInsideNone;
4549
4550 while (i1 < n1 || i2 < n2) {
4551 CharacterRange next_range;
4552 int range_source;
ager@chromium.org64488672010-01-25 13:24:36 +00004553 if (i2 == n2 ||
4554 (i1 < n1 && first_set->at(i1).from() < second_set->at(i2).from())) {
4555 // Next smallest element is in first set.
fschneider@chromium.org0c20e672010-01-14 15:28:53 +00004556 next_range = first_set->at(i1++);
4557 range_source = kInsideFirst;
4558 } else {
ager@chromium.org64488672010-01-25 13:24:36 +00004559 // Next smallest element is in second set.
fschneider@chromium.org0c20e672010-01-14 15:28:53 +00004560 next_range = second_set->at(i2++);
4561 range_source = kInsideSecond;
4562 }
4563 if (to < next_range.from()) {
4564 // Ranges disjoint: |current| |next|
4565 AddRangeToSelectedSet(state,
4566 first_set_only_out,
4567 second_set_only_out,
4568 both_sets_out,
4569 CharacterRange(from, to));
4570 from = next_range.from();
4571 to = next_range.to();
4572 state = range_source;
4573 } else {
4574 if (from < next_range.from()) {
4575 AddRangeToSelectedSet(state,
4576 first_set_only_out,
4577 second_set_only_out,
4578 both_sets_out,
4579 CharacterRange(from, next_range.from()-1));
4580 }
4581 if (to < next_range.to()) {
4582 // Ranges overlap: |current|
4583 // |next|
4584 AddRangeToSelectedSet(state | range_source,
4585 first_set_only_out,
4586 second_set_only_out,
4587 both_sets_out,
4588 CharacterRange(next_range.from(), to));
4589 from = to + 1;
4590 to = next_range.to();
4591 state = range_source;
4592 } else {
4593 // Range included: |current| , possibly ending at same character.
4594 // |next|
4595 AddRangeToSelectedSet(
4596 state | range_source,
4597 first_set_only_out,
4598 second_set_only_out,
4599 both_sets_out,
4600 CharacterRange(next_range.from(), next_range.to()));
4601 from = next_range.to() + 1;
4602 // If ranges end at same character, both ranges are consumed completely.
4603 if (next_range.to() == to) state = kInsideNone;
4604 }
4605 }
4606 }
4607 AddRangeToSelectedSet(state,
4608 first_set_only_out,
4609 second_set_only_out,
4610 both_sets_out,
4611 CharacterRange(from, to));
4612}
4613
4614
4615void CharacterRange::Negate(ZoneList<CharacterRange>* ranges,
4616 ZoneList<CharacterRange>* negated_ranges) {
4617 ASSERT(CharacterRange::IsCanonical(ranges));
4618 ASSERT_EQ(0, negated_ranges->length());
4619 int range_count = ranges->length();
4620 uc16 from = 0;
4621 int i = 0;
4622 if (range_count > 0 && ranges->at(0).from() == 0) {
4623 from = ranges->at(0).to();
4624 i = 1;
4625 }
4626 while (i < range_count) {
4627 CharacterRange range = ranges->at(i);
4628 negated_ranges->Add(CharacterRange(from + 1, range.from() - 1));
4629 from = range.to();
4630 i++;
4631 }
4632 if (from < String::kMaxUC16CharCode) {
4633 negated_ranges->Add(CharacterRange(from + 1, String::kMaxUC16CharCode));
4634 }
4635}
4636
4637
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00004638
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004639// -------------------------------------------------------------------
4640// Interest propagation
4641
4642
4643RegExpNode* RegExpNode::TryGetSibling(NodeInfo* info) {
4644 for (int i = 0; i < siblings_.length(); i++) {
4645 RegExpNode* sibling = siblings_.Get(i);
4646 if (sibling->info()->Matches(info))
4647 return sibling;
4648 }
4649 return NULL;
4650}
4651
4652
4653RegExpNode* RegExpNode::EnsureSibling(NodeInfo* info, bool* cloned) {
4654 ASSERT_EQ(false, *cloned);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004655 siblings_.Ensure(this);
4656 RegExpNode* result = TryGetSibling(info);
4657 if (result != NULL) return result;
4658 result = this->Clone();
4659 NodeInfo* new_info = result->info();
4660 new_info->ResetCompilationState();
4661 new_info->AddFromPreceding(info);
4662 AddSibling(result);
4663 *cloned = true;
4664 return result;
4665}
4666
4667
4668template <class C>
4669static RegExpNode* PropagateToEndpoint(C* node, NodeInfo* info) {
4670 NodeInfo full_info(*node->info());
4671 full_info.AddFromPreceding(info);
4672 bool cloned = false;
4673 return RegExpNode::EnsureSibling(node, &full_info, &cloned);
4674}
4675
4676
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004677// -------------------------------------------------------------------
4678// Splay tree
4679
4680
4681OutSet* OutSet::Extend(unsigned value) {
4682 if (Get(value))
4683 return this;
4684 if (successors() != NULL) {
4685 for (int i = 0; i < successors()->length(); i++) {
4686 OutSet* successor = successors()->at(i);
4687 if (successor->Get(value))
4688 return successor;
4689 }
4690 } else {
4691 successors_ = new ZoneList<OutSet*>(2);
4692 }
4693 OutSet* result = new OutSet(first_, remaining_);
4694 result->Set(value);
4695 successors()->Add(result);
4696 return result;
4697}
4698
4699
4700void OutSet::Set(unsigned value) {
4701 if (value < kFirstLimit) {
4702 first_ |= (1 << value);
4703 } else {
4704 if (remaining_ == NULL)
4705 remaining_ = new ZoneList<unsigned>(1);
4706 if (remaining_->is_empty() || !remaining_->Contains(value))
4707 remaining_->Add(value);
4708 }
4709}
4710
4711
4712bool OutSet::Get(unsigned value) {
4713 if (value < kFirstLimit) {
4714 return (first_ & (1 << value)) != 0;
4715 } else if (remaining_ == NULL) {
4716 return false;
4717 } else {
4718 return remaining_->Contains(value);
4719 }
4720}
4721
4722
4723const uc16 DispatchTable::Config::kNoKey = unibrow::Utf8::kBadChar;
4724const DispatchTable::Entry DispatchTable::Config::kNoValue;
4725
4726
4727void DispatchTable::AddRange(CharacterRange full_range, int value) {
4728 CharacterRange current = full_range;
4729 if (tree()->is_empty()) {
4730 // If this is the first range we just insert into the table.
4731 ZoneSplayTree<Config>::Locator loc;
4732 ASSERT_RESULT(tree()->Insert(current.from(), &loc));
4733 loc.set_value(Entry(current.from(), current.to(), empty()->Extend(value)));
4734 return;
4735 }
4736 // First see if there is a range to the left of this one that
4737 // overlaps.
4738 ZoneSplayTree<Config>::Locator loc;
4739 if (tree()->FindGreatestLessThan(current.from(), &loc)) {
4740 Entry* entry = &loc.value();
4741 // If we've found a range that overlaps with this one, and it
4742 // starts strictly to the left of this one, we have to fix it
4743 // because the following code only handles ranges that start on
4744 // or after the start point of the range we're adding.
4745 if (entry->from() < current.from() && entry->to() >= current.from()) {
4746 // Snap the overlapping range in half around the start point of
4747 // the range we're adding.
4748 CharacterRange left(entry->from(), current.from() - 1);
4749 CharacterRange right(current.from(), entry->to());
4750 // The left part of the overlapping range doesn't overlap.
4751 // Truncate the whole entry to be just the left part.
4752 entry->set_to(left.to());
4753 // The right part is the one that overlaps. We add this part
4754 // to the map and let the next step deal with merging it with
4755 // the range we're adding.
4756 ZoneSplayTree<Config>::Locator loc;
4757 ASSERT_RESULT(tree()->Insert(right.from(), &loc));
4758 loc.set_value(Entry(right.from(),
4759 right.to(),
4760 entry->out_set()));
4761 }
4762 }
4763 while (current.is_valid()) {
4764 if (tree()->FindLeastGreaterThan(current.from(), &loc) &&
4765 (loc.value().from() <= current.to()) &&
4766 (loc.value().to() >= current.from())) {
4767 Entry* entry = &loc.value();
4768 // We have overlap. If there is space between the start point of
4769 // the range we're adding and where the overlapping range starts
4770 // then we have to add a range covering just that space.
4771 if (current.from() < entry->from()) {
4772 ZoneSplayTree<Config>::Locator ins;
4773 ASSERT_RESULT(tree()->Insert(current.from(), &ins));
4774 ins.set_value(Entry(current.from(),
4775 entry->from() - 1,
4776 empty()->Extend(value)));
4777 current.set_from(entry->from());
4778 }
4779 ASSERT_EQ(current.from(), entry->from());
4780 // If the overlapping range extends beyond the one we want to add
4781 // we have to snap the right part off and add it separately.
4782 if (entry->to() > current.to()) {
4783 ZoneSplayTree<Config>::Locator ins;
4784 ASSERT_RESULT(tree()->Insert(current.to() + 1, &ins));
4785 ins.set_value(Entry(current.to() + 1,
4786 entry->to(),
4787 entry->out_set()));
4788 entry->set_to(current.to());
4789 }
4790 ASSERT(entry->to() <= current.to());
4791 // The overlapping range is now completely contained by the range
4792 // we're adding so we can just update it and move the start point
4793 // of the range we're adding just past it.
4794 entry->AddValue(value);
4795 // Bail out if the last interval ended at 0xFFFF since otherwise
4796 // adding 1 will wrap around to 0.
ager@chromium.org8bb60582008-12-11 12:02:20 +00004797 if (entry->to() == String::kMaxUC16CharCode)
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004798 break;
4799 ASSERT(entry->to() + 1 > current.from());
4800 current.set_from(entry->to() + 1);
4801 } else {
4802 // There is no overlap so we can just add the range
4803 ZoneSplayTree<Config>::Locator ins;
4804 ASSERT_RESULT(tree()->Insert(current.from(), &ins));
4805 ins.set_value(Entry(current.from(),
4806 current.to(),
4807 empty()->Extend(value)));
4808 break;
4809 }
4810 }
4811}
4812
4813
4814OutSet* DispatchTable::Get(uc16 value) {
4815 ZoneSplayTree<Config>::Locator loc;
4816 if (!tree()->FindGreatestLessThan(value, &loc))
4817 return empty();
4818 Entry* entry = &loc.value();
4819 if (value <= entry->to())
4820 return entry->out_set();
4821 else
4822 return empty();
4823}
4824
4825
4826// -------------------------------------------------------------------
4827// Analysis
4828
4829
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00004830void Analysis::EnsureAnalyzed(RegExpNode* that) {
sgjesse@chromium.orgea88ce92011-03-23 11:19:56 +00004831 StackLimitCheck check(Isolate::Current());
sgjesse@chromium.org755c5b12009-05-29 11:04:38 +00004832 if (check.HasOverflowed()) {
4833 fail("Stack overflow");
4834 return;
4835 }
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004836 if (that->info()->been_analyzed || that->info()->being_analyzed)
4837 return;
4838 that->info()->being_analyzed = true;
4839 that->Accept(this);
4840 that->info()->being_analyzed = false;
4841 that->info()->been_analyzed = true;
4842}
4843
4844
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00004845void Analysis::VisitEnd(EndNode* that) {
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004846 // nothing to do
4847}
4848
4849
ager@chromium.org8bb60582008-12-11 12:02:20 +00004850void TextNode::CalculateOffsets() {
4851 int element_count = elements()->length();
4852 // Set up the offsets of the elements relative to the start. This is a fixed
4853 // quantity since a TextNode can only contain fixed-width things.
4854 int cp_offset = 0;
4855 for (int i = 0; i < element_count; i++) {
4856 TextElement& elm = elements()->at(i);
4857 elm.cp_offset = cp_offset;
4858 if (elm.type == TextElement::ATOM) {
4859 cp_offset += elm.data.u_atom->data().length();
4860 } else {
4861 cp_offset++;
ager@chromium.org8bb60582008-12-11 12:02:20 +00004862 }
4863 }
4864}
4865
4866
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00004867void Analysis::VisitText(TextNode* that) {
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004868 if (ignore_case_) {
ager@chromium.org38e4c712009-11-11 09:11:58 +00004869 that->MakeCaseIndependent(is_ascii_);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004870 }
4871 EnsureAnalyzed(that->on_success());
sgjesse@chromium.org755c5b12009-05-29 11:04:38 +00004872 if (!has_failed()) {
4873 that->CalculateOffsets();
4874 }
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004875}
4876
4877
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00004878void Analysis::VisitAction(ActionNode* that) {
ager@chromium.org8bb60582008-12-11 12:02:20 +00004879 RegExpNode* target = that->on_success();
4880 EnsureAnalyzed(target);
sgjesse@chromium.org755c5b12009-05-29 11:04:38 +00004881 if (!has_failed()) {
4882 // If the next node is interested in what it follows then this node
4883 // has to be interested too so it can pass the information on.
4884 that->info()->AddFromFollowing(target->info());
4885 }
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004886}
4887
4888
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00004889void Analysis::VisitChoice(ChoiceNode* that) {
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004890 NodeInfo* info = that->info();
4891 for (int i = 0; i < that->alternatives()->length(); i++) {
4892 RegExpNode* node = that->alternatives()->at(i).node();
4893 EnsureAnalyzed(node);
sgjesse@chromium.org755c5b12009-05-29 11:04:38 +00004894 if (has_failed()) return;
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004895 // Anything the following nodes need to know has to be known by
4896 // this node also, so it can pass it on.
4897 info->AddFromFollowing(node->info());
4898 }
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004899}
4900
4901
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00004902void Analysis::VisitLoopChoice(LoopChoiceNode* that) {
4903 NodeInfo* info = that->info();
4904 for (int i = 0; i < that->alternatives()->length(); i++) {
4905 RegExpNode* node = that->alternatives()->at(i).node();
4906 if (node != that->loop_node()) {
4907 EnsureAnalyzed(node);
sgjesse@chromium.org755c5b12009-05-29 11:04:38 +00004908 if (has_failed()) return;
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00004909 info->AddFromFollowing(node->info());
4910 }
4911 }
4912 // Check the loop last since it may need the value of this node
4913 // to get a correct result.
4914 EnsureAnalyzed(that->loop_node());
sgjesse@chromium.org755c5b12009-05-29 11:04:38 +00004915 if (!has_failed()) {
4916 info->AddFromFollowing(that->loop_node()->info());
4917 }
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00004918}
4919
4920
4921void Analysis::VisitBackReference(BackReferenceNode* that) {
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004922 EnsureAnalyzed(that->on_success());
ager@chromium.orga74f0da2008-12-03 16:05:52 +00004923}
4924
4925
ager@chromium.orgddb913d2009-01-27 10:01:48 +00004926void Analysis::VisitAssertion(AssertionNode* that) {
4927 EnsureAnalyzed(that->on_success());
fschneider@chromium.org0c20e672010-01-14 15:28:53 +00004928 AssertionNode::AssertionNodeType type = that->type();
4929 if (type == AssertionNode::AT_BOUNDARY ||
4930 type == AssertionNode::AT_NON_BOUNDARY) {
4931 // Check if the following character is known to be a word character
4932 // or known to not be a word character.
4933 ZoneList<CharacterRange>* following_chars = that->FirstCharacterSet();
4934
4935 CharacterRange::Canonicalize(following_chars);
4936
4937 SetRelation word_relation =
4938 CharacterRange::WordCharacterRelation(following_chars);
lrn@chromium.orgc34f5802010-04-28 12:53:43 +00004939 if (word_relation.Disjoint()) {
4940 // Includes the case where following_chars is empty (e.g., end-of-input).
fschneider@chromium.org0c20e672010-01-14 15:28:53 +00004941 // Following character is definitely *not* a word character.
4942 type = (type == AssertionNode::AT_BOUNDARY) ?
lrn@chromium.orgc34f5802010-04-28 12:53:43 +00004943 AssertionNode::AFTER_WORD_CHARACTER :
4944 AssertionNode::AFTER_NONWORD_CHARACTER;
4945 that->set_type(type);
4946 } else if (word_relation.ContainedIn()) {
4947 // Following character is definitely a word character.
4948 type = (type == AssertionNode::AT_BOUNDARY) ?
4949 AssertionNode::AFTER_NONWORD_CHARACTER :
4950 AssertionNode::AFTER_WORD_CHARACTER;
fschneider@chromium.org0c20e672010-01-14 15:28:53 +00004951 that->set_type(type);
4952 }
4953 }
ager@chromium.orgddb913d2009-01-27 10:01:48 +00004954}
4955
4956
fschneider@chromium.org0c20e672010-01-14 15:28:53 +00004957ZoneList<CharacterRange>* RegExpNode::FirstCharacterSet() {
4958 if (first_character_set_ == NULL) {
4959 if (ComputeFirstCharacterSet(kFirstCharBudget) < 0) {
4960 // If we can't find an exact solution within the budget, we
4961 // set the value to the set of every character, i.e., all characters
4962 // are possible.
4963 ZoneList<CharacterRange>* all_set = new ZoneList<CharacterRange>(1);
4964 all_set->Add(CharacterRange::Everything());
4965 first_character_set_ = all_set;
4966 }
4967 }
4968 return first_character_set_;
4969}
4970
4971
4972int RegExpNode::ComputeFirstCharacterSet(int budget) {
4973 // Default behavior is to not be able to determine the first character.
4974 return kComputeFirstCharacterSetFail;
4975}
4976
4977
4978int LoopChoiceNode::ComputeFirstCharacterSet(int budget) {
4979 budget--;
4980 if (budget >= 0) {
4981 // Find loop min-iteration. It's the value of the guarded choice node
4982 // with a GEQ guard, if any.
4983 int min_repetition = 0;
4984
4985 for (int i = 0; i <= 1; i++) {
4986 GuardedAlternative alternative = alternatives()->at(i);
4987 ZoneList<Guard*>* guards = alternative.guards();
4988 if (guards != NULL && guards->length() > 0) {
4989 Guard* guard = guards->at(0);
4990 if (guard->op() == Guard::GEQ) {
4991 min_repetition = guard->value();
4992 break;
4993 }
4994 }
4995 }
4996
4997 budget = loop_node()->ComputeFirstCharacterSet(budget);
4998 if (budget >= 0) {
4999 ZoneList<CharacterRange>* character_set =
5000 loop_node()->first_character_set();
5001 if (body_can_be_zero_length() || min_repetition == 0) {
5002 budget = continue_node()->ComputeFirstCharacterSet(budget);
5003 if (budget < 0) return budget;
5004 ZoneList<CharacterRange>* body_set =
5005 continue_node()->first_character_set();
5006 ZoneList<CharacterRange>* union_set =
5007 new ZoneList<CharacterRange>(Max(character_set->length(),
5008 body_set->length()));
5009 CharacterRange::Merge(character_set,
5010 body_set,
5011 union_set,
5012 union_set,
5013 union_set);
5014 character_set = union_set;
5015 }
5016 set_first_character_set(character_set);
5017 }
5018 }
5019 return budget;
5020}
5021
5022
5023int NegativeLookaheadChoiceNode::ComputeFirstCharacterSet(int budget) {
5024 budget--;
5025 if (budget >= 0) {
5026 GuardedAlternative successor = this->alternatives()->at(1);
5027 RegExpNode* successor_node = successor.node();
5028 budget = successor_node->ComputeFirstCharacterSet(budget);
5029 if (budget >= 0) {
5030 set_first_character_set(successor_node->first_character_set());
5031 }
5032 }
5033 return budget;
5034}
5035
5036
5037// The first character set of an EndNode is unknowable. Just use the
5038// default implementation that fails and returns all characters as possible.
5039
5040
5041int AssertionNode::ComputeFirstCharacterSet(int budget) {
5042 budget -= 1;
5043 if (budget >= 0) {
5044 switch (type_) {
5045 case AT_END: {
5046 set_first_character_set(new ZoneList<CharacterRange>(0));
5047 break;
5048 }
5049 case AT_START:
5050 case AT_BOUNDARY:
5051 case AT_NON_BOUNDARY:
5052 case AFTER_NEWLINE:
5053 case AFTER_NONWORD_CHARACTER:
5054 case AFTER_WORD_CHARACTER: {
5055 ASSERT_NOT_NULL(on_success());
5056 budget = on_success()->ComputeFirstCharacterSet(budget);
sgjesse@chromium.orgdf7a2842010-03-25 14:34:15 +00005057 if (budget >= 0) {
5058 set_first_character_set(on_success()->first_character_set());
5059 }
fschneider@chromium.org0c20e672010-01-14 15:28:53 +00005060 break;
5061 }
5062 }
5063 }
5064 return budget;
5065}
5066
5067
5068int ActionNode::ComputeFirstCharacterSet(int budget) {
5069 if (type_ == POSITIVE_SUBMATCH_SUCCESS) return kComputeFirstCharacterSetFail;
5070 budget--;
5071 if (budget >= 0) {
5072 ASSERT_NOT_NULL(on_success());
5073 budget = on_success()->ComputeFirstCharacterSet(budget);
5074 if (budget >= 0) {
5075 set_first_character_set(on_success()->first_character_set());
5076 }
5077 }
5078 return budget;
5079}
5080
5081
5082int BackReferenceNode::ComputeFirstCharacterSet(int budget) {
5083 // We don't know anything about the first character of a backreference
5084 // at this point.
sgjesse@chromium.orgdf7a2842010-03-25 14:34:15 +00005085 // The potential first characters are the first characters of the capture,
5086 // and the first characters of the on_success node, depending on whether the
5087 // capture can be empty and whether it is known to be participating or known
5088 // not to be.
fschneider@chromium.org0c20e672010-01-14 15:28:53 +00005089 return kComputeFirstCharacterSetFail;
5090}
5091
5092
5093int TextNode::ComputeFirstCharacterSet(int budget) {
5094 budget--;
5095 if (budget >= 0) {
5096 ASSERT_NE(0, elements()->length());
5097 TextElement text = elements()->at(0);
5098 if (text.type == TextElement::ATOM) {
5099 RegExpAtom* atom = text.data.u_atom;
5100 ASSERT_NE(0, atom->length());
5101 uc16 first_char = atom->data()[0];
5102 ZoneList<CharacterRange>* range = new ZoneList<CharacterRange>(1);
5103 range->Add(CharacterRange(first_char, first_char));
5104 set_first_character_set(range);
5105 } else {
5106 ASSERT(text.type == TextElement::CHAR_CLASS);
5107 RegExpCharacterClass* char_class = text.data.u_char_class;
sgjesse@chromium.orgdf7a2842010-03-25 14:34:15 +00005108 ZoneList<CharacterRange>* ranges = char_class->ranges();
5109 // TODO(lrn): Canonicalize ranges when they are created
5110 // instead of waiting until now.
5111 CharacterRange::Canonicalize(ranges);
fschneider@chromium.org0c20e672010-01-14 15:28:53 +00005112 if (char_class->is_negated()) {
fschneider@chromium.org0c20e672010-01-14 15:28:53 +00005113 int length = ranges->length();
5114 int new_length = length + 1;
5115 if (length > 0) {
5116 if (ranges->at(0).from() == 0) new_length--;
5117 if (ranges->at(length - 1).to() == String::kMaxUC16CharCode) {
5118 new_length--;
5119 }
5120 }
5121 ZoneList<CharacterRange>* negated_ranges =
5122 new ZoneList<CharacterRange>(new_length);
5123 CharacterRange::Negate(ranges, negated_ranges);
5124 set_first_character_set(negated_ranges);
5125 } else {
sgjesse@chromium.orgdf7a2842010-03-25 14:34:15 +00005126 set_first_character_set(ranges);
fschneider@chromium.org0c20e672010-01-14 15:28:53 +00005127 }
5128 }
5129 }
5130 return budget;
5131}
5132
5133
5134
ager@chromium.orga74f0da2008-12-03 16:05:52 +00005135// -------------------------------------------------------------------
ager@chromium.orga74f0da2008-12-03 16:05:52 +00005136// Dispatch table construction
5137
5138
5139void DispatchTableConstructor::VisitEnd(EndNode* that) {
5140 AddRange(CharacterRange::Everything());
5141}
5142
5143
5144void DispatchTableConstructor::BuildTable(ChoiceNode* node) {
5145 node->set_being_calculated(true);
5146 ZoneList<GuardedAlternative>* alternatives = node->alternatives();
5147 for (int i = 0; i < alternatives->length(); i++) {
5148 set_choice_index(i);
5149 alternatives->at(i).node()->Accept(this);
5150 }
5151 node->set_being_calculated(false);
5152}
5153
5154
5155class AddDispatchRange {
5156 public:
5157 explicit AddDispatchRange(DispatchTableConstructor* constructor)
5158 : constructor_(constructor) { }
5159 void Call(uc32 from, DispatchTable::Entry entry);
5160 private:
5161 DispatchTableConstructor* constructor_;
5162};
5163
5164
5165void AddDispatchRange::Call(uc32 from, DispatchTable::Entry entry) {
5166 CharacterRange range(from, entry.to());
5167 constructor_->AddRange(range);
5168}
5169
5170
5171void DispatchTableConstructor::VisitChoice(ChoiceNode* node) {
5172 if (node->being_calculated())
5173 return;
5174 DispatchTable* table = node->GetTable(ignore_case_);
5175 AddDispatchRange adder(this);
5176 table->ForEach(&adder);
5177}
5178
5179
5180void DispatchTableConstructor::VisitBackReference(BackReferenceNode* that) {
5181 // TODO(160): Find the node that we refer back to and propagate its start
5182 // set back to here. For now we just accept anything.
5183 AddRange(CharacterRange::Everything());
5184}
5185
5186
ager@chromium.orgddb913d2009-01-27 10:01:48 +00005187void DispatchTableConstructor::VisitAssertion(AssertionNode* that) {
5188 RegExpNode* target = that->on_success();
5189 target->Accept(this);
5190}
5191
5192
ager@chromium.orga74f0da2008-12-03 16:05:52 +00005193static int CompareRangeByFrom(const CharacterRange* a,
5194 const CharacterRange* b) {
5195 return Compare<uc16>(a->from(), b->from());
5196}
5197
5198
5199void DispatchTableConstructor::AddInverse(ZoneList<CharacterRange>* ranges) {
5200 ranges->Sort(CompareRangeByFrom);
5201 uc16 last = 0;
5202 for (int i = 0; i < ranges->length(); i++) {
5203 CharacterRange range = ranges->at(i);
5204 if (last < range.from())
5205 AddRange(CharacterRange(last, range.from() - 1));
5206 if (range.to() >= last) {
ager@chromium.org8bb60582008-12-11 12:02:20 +00005207 if (range.to() == String::kMaxUC16CharCode) {
ager@chromium.orga74f0da2008-12-03 16:05:52 +00005208 return;
5209 } else {
5210 last = range.to() + 1;
5211 }
5212 }
5213 }
ager@chromium.org8bb60582008-12-11 12:02:20 +00005214 AddRange(CharacterRange(last, String::kMaxUC16CharCode));
ager@chromium.orga74f0da2008-12-03 16:05:52 +00005215}
5216
5217
5218void DispatchTableConstructor::VisitText(TextNode* that) {
5219 TextElement elm = that->elements()->at(0);
5220 switch (elm.type) {
5221 case TextElement::ATOM: {
5222 uc16 c = elm.data.u_atom->data()[0];
5223 AddRange(CharacterRange(c, c));
5224 break;
5225 }
5226 case TextElement::CHAR_CLASS: {
5227 RegExpCharacterClass* tree = elm.data.u_char_class;
5228 ZoneList<CharacterRange>* ranges = tree->ranges();
5229 if (tree->is_negated()) {
5230 AddInverse(ranges);
5231 } else {
5232 for (int i = 0; i < ranges->length(); i++)
5233 AddRange(ranges->at(i));
5234 }
5235 break;
5236 }
5237 default: {
5238 UNIMPLEMENTED();
5239 }
5240 }
5241}
5242
5243
5244void DispatchTableConstructor::VisitAction(ActionNode* that) {
ager@chromium.org8bb60582008-12-11 12:02:20 +00005245 RegExpNode* target = that->on_success();
5246 target->Accept(this);
5247}
5248
5249
kasperl@chromium.org7be3c992009-03-12 07:19:55 +00005250RegExpEngine::CompilationResult RegExpEngine::Compile(RegExpCompileData* data,
5251 bool ignore_case,
5252 bool is_multiline,
5253 Handle<String> pattern,
5254 bool is_ascii) {
ager@chromium.orgddb913d2009-01-27 10:01:48 +00005255 if ((data->capture_count + 1) * 2 - 1 > RegExpMacroAssembler::kMaxRegister) {
kasperl@chromium.org7be3c992009-03-12 07:19:55 +00005256 return IrregexpRegExpTooBig();
ager@chromium.orgddb913d2009-01-27 10:01:48 +00005257 }
ager@chromium.org8bb60582008-12-11 12:02:20 +00005258 RegExpCompiler compiler(data->capture_count, ignore_case, is_ascii);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00005259 // Wrap the body of the regexp in capture #0.
ager@chromium.org8bb60582008-12-11 12:02:20 +00005260 RegExpNode* captured_body = RegExpCapture::ToNode(data->tree,
ager@chromium.orga74f0da2008-12-03 16:05:52 +00005261 0,
5262 &compiler,
ager@chromium.org8bb60582008-12-11 12:02:20 +00005263 compiler.accept());
ager@chromium.orgddb913d2009-01-27 10:01:48 +00005264 RegExpNode* node = captured_body;
whesse@chromium.org4a5224e2010-10-20 12:37:07 +00005265 bool is_end_anchored = data->tree->IsAnchoredAtEnd();
5266 bool is_start_anchored = data->tree->IsAnchoredAtStart();
5267 int max_length = data->tree->max_match();
5268 if (!is_start_anchored) {
ager@chromium.orgddb913d2009-01-27 10:01:48 +00005269 // Add a .*? at the beginning, outside the body capture, unless
5270 // this expression is anchored at the beginning.
iposva@chromium.org245aa852009-02-10 00:49:54 +00005271 RegExpNode* loop_node =
5272 RegExpQuantifier::ToNode(0,
5273 RegExpTree::kInfinity,
5274 false,
5275 new RegExpCharacterClass('*'),
5276 &compiler,
5277 captured_body,
5278 data->contains_anchor);
5279
5280 if (data->contains_anchor) {
5281 // Unroll loop once, to take care of the case that might start
5282 // at the start of input.
5283 ChoiceNode* first_step_node = new ChoiceNode(2);
5284 first_step_node->AddAlternative(GuardedAlternative(captured_body));
5285 first_step_node->AddAlternative(GuardedAlternative(
5286 new TextNode(new RegExpCharacterClass('*'), loop_node)));
5287 node = first_step_node;
5288 } else {
5289 node = loop_node;
5290 }
ager@chromium.orgddb913d2009-01-27 10:01:48 +00005291 }
christian.plesner.hansen@gmail.com37abdec2009-01-06 14:43:28 +00005292 data->node = node;
ager@chromium.org38e4c712009-11-11 09:11:58 +00005293 Analysis analysis(ignore_case, is_ascii);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00005294 analysis.EnsureAnalyzed(node);
sgjesse@chromium.org755c5b12009-05-29 11:04:38 +00005295 if (analysis.has_failed()) {
5296 const char* error_message = analysis.error_message();
5297 return CompilationResult(error_message);
5298 }
ager@chromium.orga74f0da2008-12-03 16:05:52 +00005299
sgjesse@chromium.org911335c2009-08-19 12:59:44 +00005300 // Create the correct assembler for the architecture.
ricow@chromium.orgc9c80822010-04-21 08:22:37 +00005301#ifndef V8_INTERPRETED_REGEXP
sgjesse@chromium.org911335c2009-08-19 12:59:44 +00005302 // Native regexp implementation.
5303
5304 NativeRegExpMacroAssembler::Mode mode =
5305 is_ascii ? NativeRegExpMacroAssembler::ASCII
5306 : NativeRegExpMacroAssembler::UC16;
5307
ager@chromium.org18ad94b2009-09-02 08:22:29 +00005308#if V8_TARGET_ARCH_IA32
5309 RegExpMacroAssemblerIA32 macro_assembler(mode, (data->capture_count + 1) * 2);
5310#elif V8_TARGET_ARCH_X64
5311 RegExpMacroAssemblerX64 macro_assembler(mode, (data->capture_count + 1) * 2);
5312#elif V8_TARGET_ARCH_ARM
5313 RegExpMacroAssemblerARM macro_assembler(mode, (data->capture_count + 1) * 2);
lrn@chromium.org7516f052011-03-30 08:52:27 +00005314#elif V8_TARGET_ARCH_MIPS
5315 RegExpMacroAssemblerMIPS macro_assembler(mode, (data->capture_count + 1) * 2);
sgjesse@chromium.org911335c2009-08-19 12:59:44 +00005316#endif
5317
ricow@chromium.orgc9c80822010-04-21 08:22:37 +00005318#else // V8_INTERPRETED_REGEXP
sgjesse@chromium.org911335c2009-08-19 12:59:44 +00005319 // Interpreted regexp implementation.
ager@chromium.orga74f0da2008-12-03 16:05:52 +00005320 EmbeddedVector<byte, 1024> codes;
5321 RegExpMacroAssemblerIrregexp macro_assembler(codes);
ricow@chromium.orgc9c80822010-04-21 08:22:37 +00005322#endif // V8_INTERPRETED_REGEXP
sgjesse@chromium.org911335c2009-08-19 12:59:44 +00005323
whesse@chromium.org4a5224e2010-10-20 12:37:07 +00005324 // Inserted here, instead of in Assembler, because it depends on information
5325 // in the AST that isn't replicated in the Node structure.
5326 static const int kMaxBacksearchLimit = 1024;
5327 if (is_end_anchored &&
5328 !is_start_anchored &&
5329 max_length < kMaxBacksearchLimit) {
5330 macro_assembler.SetCurrentPositionFromEnd(max_length);
5331 }
5332
ager@chromium.orga74f0da2008-12-03 16:05:52 +00005333 return compiler.Assemble(&macro_assembler,
5334 node,
ager@chromium.org8bb60582008-12-11 12:02:20 +00005335 data->capture_count,
5336 pattern);
ager@chromium.orga74f0da2008-12-03 16:05:52 +00005337}
5338
fschneider@chromium.org0c20e672010-01-14 15:28:53 +00005339
christian.plesner.hansen43d26ec2008-07-03 15:10:15 +00005340}} // namespace v8::internal