[go: nahoru, domu]
Google Git
Sign in
android / platform / external / v8 / 589d6979ff2ef66fca2d8fa51404c369ca5e9250 / . / src / jsregexp.h
blob: 54297a49abc9fe17bb1cb7dcd692ad848114c44b [file] [log] [blame]
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]1// Copyright 2006-2008 the V8 project authors. All rights reserved.
2// Redistribution and use in source and binary forms, with or without
3// modification, are permitted provided that the following conditions are
4// met:
5//
6// * Redistributions of source code must retain the above copyright
7// notice, this list of conditions and the following disclaimer.
8// * Redistributions in binary form must reproduce the above
9// copyright notice, this list of conditions and the following
10// disclaimer in the documentation and/or other materials provided
11// with the distribution.
12// * Neither the name of Google Inc. nor the names of its
13// contributors may be used to endorse or promote products derived
14// from this software without specific prior written permission.
15//
16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28#ifndef V8_JSREGEXP_H_
29#define V8_JSREGEXP_H_
30
Ben Murdoch257744e2011-11-30 15:57:28 +0000[diff] [blame]31#include "allocation.h"
Steve Block6ded16b2010-05-10 14:33:55 +0100[diff] [blame]32#include "zone-inl.h"
Steve Block3ce2e202009-11-05 08:53:23 +0000[diff] [blame]33
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]34namespace v8 {
35namespace internal {
36
37
38class RegExpMacroAssembler;
39
40
41class RegExpImpl {
42 public:
43 // Whether V8 is compiled with native regexp support or not.
44 static bool UsesNativeRegExp() {
Steve Block6ded16b2010-05-10 14:33:55 +0100[diff] [blame]45#ifdef V8_INTERPRETED_REGEXP
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]46 return false;
Steve Block6ded16b2010-05-10 14:33:55 +0100[diff] [blame]47#else
48 return true;
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]49#endif
50 }
51
52 // Creates a regular expression literal in the old space.
53 // This function calls the garbage collector if necessary.
54 static Handle<Object> CreateRegExpLiteral(Handle<JSFunction> constructor,
55 Handle<String> pattern,
56 Handle<String> flags,
57 bool* has_pending_exception);
58
59 // Returns a string representation of a regular expression.
60 // Implements RegExp.prototype.toString, see ECMA-262 section 15.10.6.4.
61 // This function calls the garbage collector if necessary.
62 static Handle<String> ToString(Handle<Object> value);
63
64 // Parses the RegExp pattern and prepares the JSRegExp object with
65 // generic data and choice of implementation - as well as what
66 // the implementation wants to store in the data field.
67 // Returns false if compilation fails.
68 static Handle<Object> Compile(Handle<JSRegExp> re,
69 Handle<String> pattern,
70 Handle<String> flags);
71
72 // See ECMA-262 section 15.10.6.2.
73 // This function calls the garbage collector if necessary.
74 static Handle<Object> Exec(Handle<JSRegExp> regexp,
75 Handle<String> subject,
76 int index,
77 Handle<JSArray> lastMatchInfo);
78
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]79 // Prepares a JSRegExp object with Irregexp-specific data.
Steve Block6ded16b2010-05-10 14:33:55 +0100[diff] [blame]80 static void IrregexpInitialize(Handle<JSRegExp> re,
81 Handle<String> pattern,
82 JSRegExp::Flags flags,
83 int capture_register_count);
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]84
85
86 static void AtomCompile(Handle<JSRegExp> re,
87 Handle<String> pattern,
88 JSRegExp::Flags flags,
89 Handle<String> match_pattern);
90
91 static Handle<Object> AtomExec(Handle<JSRegExp> regexp,
92 Handle<String> subject,
93 int index,
94 Handle<JSArray> lastMatchInfo);
95
Steve Block6ded16b2010-05-10 14:33:55 +0100[diff] [blame]96 enum IrregexpResult { RE_FAILURE = 0, RE_SUCCESS = 1, RE_EXCEPTION = -1 };
97
98 // Prepare a RegExp for being executed one or more times (using
99 // IrregexpExecOnce) on the subject.
100 // This ensures that the regexp is compiled for the subject, and that
101 // the subject is flat.
102 // Returns the number of integer spaces required by IrregexpExecOnce
103 // as its "registers" argument. If the regexp cannot be compiled,
104 // an exception is set as pending, and this function returns negative.
105 static int IrregexpPrepare(Handle<JSRegExp> regexp,
106 Handle<String> subject);
107
108 // Execute a regular expression once on the subject, starting from
109 // character "index".
110 // If successful, returns RE_SUCCESS and set the capture positions
111 // in the first registers.
112 // If matching fails, returns RE_FAILURE.
113 // If execution fails, sets a pending exception and returns RE_EXCEPTION.
114 static IrregexpResult IrregexpExecOnce(Handle<JSRegExp> regexp,
115 Handle<String> subject,
116 int index,
Ben Murdochb8e0da22011-05-16 14:20:40 +0100[diff] [blame]117 Vector<int> registers);
Steve Block6ded16b2010-05-10 14:33:55 +0100[diff] [blame]118
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]119 // Execute an Irregexp bytecode pattern.
120 // On a successful match, the result is a JSArray containing
121 // captured positions. On a failure, the result is the null value.
122 // Returns an empty handle in case of an exception.
123 static Handle<Object> IrregexpExec(Handle<JSRegExp> regexp,
124 Handle<String> subject,
125 int index,
126 Handle<JSArray> lastMatchInfo);
127
Leon Clarkee46be812010-01-19 14:06:41 +0000[diff] [blame]128 // Array index in the lastMatchInfo array.
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]129 static const int kLastCaptureCount = 0;
130 static const int kLastSubject = 1;
131 static const int kLastInput = 2;
132 static const int kFirstCapture = 3;
133 static const int kLastMatchOverhead = 3;
134
Leon Clarkee46be812010-01-19 14:06:41 +0000[diff] [blame]135 // Direct offset into the lastMatchInfo array.
136 static const int kLastCaptureCountOffset =
137 FixedArray::kHeaderSize + kLastCaptureCount * kPointerSize;
138 static const int kLastSubjectOffset =
139 FixedArray::kHeaderSize + kLastSubject * kPointerSize;
140 static const int kLastInputOffset =
141 FixedArray::kHeaderSize + kLastInput * kPointerSize;
142 static const int kFirstCaptureOffset =
143 FixedArray::kHeaderSize + kFirstCapture * kPointerSize;
144
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]145 // Used to access the lastMatchInfo array.
146 static int GetCapture(FixedArray* array, int index) {
147 return Smi::cast(array->get(index + kFirstCapture))->value();
148 }
149
150 static void SetLastCaptureCount(FixedArray* array, int to) {
151 array->set(kLastCaptureCount, Smi::FromInt(to));
152 }
153
154 static void SetLastSubject(FixedArray* array, String* to) {
155 array->set(kLastSubject, to);
156 }
157
158 static void SetLastInput(FixedArray* array, String* to) {
159 array->set(kLastInput, to);
160 }
161
162 static void SetCapture(FixedArray* array, int index, int to) {
163 array->set(index + kFirstCapture, Smi::FromInt(to));
164 }
165
166 static int GetLastCaptureCount(FixedArray* array) {
167 return Smi::cast(array->get(kLastCaptureCount))->value();
168 }
169
170 // For acting on the JSRegExp data FixedArray.
171 static int IrregexpMaxRegisterCount(FixedArray* re);
172 static void SetIrregexpMaxRegisterCount(FixedArray* re, int value);
173 static int IrregexpNumberOfCaptures(FixedArray* re);
174 static int IrregexpNumberOfRegisters(FixedArray* re);
175 static ByteArray* IrregexpByteCode(FixedArray* re, bool is_ascii);
176 static Code* IrregexpNativeCode(FixedArray* re, bool is_ascii);
177
Steve Block053d10c2011-06-13 19:13:29 +0100[diff] [blame]178 // Limit the space regexps take up on the heap. In order to limit this we
179 // would like to keep track of the amount of regexp code on the heap. This
180 // is not tracked, however. As a conservative approximation we track the
181 // total regexp code compiled including code that has subsequently been freed
182 // and the total executable memory at any point.
183 static const int kRegExpExecutableMemoryLimit = 16 * MB;
184 static const int kRegWxpCompiledLimit = 1 * MB;
185
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]186 private:
187 static String* last_ascii_string_;
188 static String* two_byte_cached_string_;
189
190 static bool CompileIrregexp(Handle<JSRegExp> re, bool is_ascii);
191 static inline bool EnsureCompiledIrregexp(Handle<JSRegExp> re, bool is_ascii);
192
193
194 // Set the subject cache. The previous string buffer is not deleted, so the
195 // caller should ensure that it doesn't leak.
196 static void SetSubjectCache(String* subject,
197 char* utf8_subject,
198 int uft8_length,
199 int character_position,
200 int utf8_position);
201
202 // A one element cache of the last utf8_subject string and its length. The
203 // subject JS String object is cached in the heap. We also cache a
204 // translation between position and utf8 position.
205 static char* utf8_subject_cache_;
206 static int utf8_length_cache_;
207 static int utf8_position_;
208 static int character_position_;
209};
210
211
Leon Clarkee46be812010-01-19 14:06:41 +0000[diff] [blame]212// Represents the location of one element relative to the intersection of
213// two sets. Corresponds to the four areas of a Venn diagram.
214enum ElementInSetsRelation {
215 kInsideNone = 0,
216 kInsideFirst = 1,
217 kInsideSecond = 2,
218 kInsideBoth = 3
219};
220
221
222// Represents the relation of two sets.
223// Sets can be either disjoint, partially or fully overlapping, or equal.
224class SetRelation BASE_EMBEDDED {
225 public:
226 // Relation is represented by a bit saying whether there are elements in
227 // one set that is not in the other, and a bit saying that there are elements
228 // that are in both sets.
229
230 // Location of an element. Corresponds to the internal areas of
231 // a Venn diagram.
232 enum {
233 kInFirst = 1 << kInsideFirst,
234 kInSecond = 1 << kInsideSecond,
235 kInBoth = 1 << kInsideBoth
236 };
237 SetRelation() : bits_(0) {}
238 ~SetRelation() {}
239 // Add the existence of objects in a particular
240 void SetElementsInFirstSet() { bits_ |= kInFirst; }
241 void SetElementsInSecondSet() { bits_ |= kInSecond; }
242 void SetElementsInBothSets() { bits_ |= kInBoth; }
243 // Check the currently known relation of the sets (common functions only,
244 // for other combinations, use value() to get the bits and check them
245 // manually).
246 // Sets are completely disjoint.
247 bool Disjoint() { return (bits_ & kInBoth) == 0; }
248 // Sets are equal.
249 bool Equals() { return (bits_ & (kInFirst | kInSecond)) == 0; }
250 // First set contains second.
251 bool Contains() { return (bits_ & kInSecond) == 0; }
252 // Second set contains first.
253 bool ContainedIn() { return (bits_ & kInFirst) == 0; }
254 bool NonTrivialIntersection() {
255 return (bits_ == (kInFirst | kInSecond | kInBoth));
256 }
257 int value() { return bits_; }
Ben Murdoch589d6972011-11-30 16:04:58 +0000[diff] [blame^]258
Leon Clarkee46be812010-01-19 14:06:41 +0000[diff] [blame]259 private:
260 int bits_;
261};
262
263
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]264class CharacterRange {
265 public:
266 CharacterRange() : from_(0), to_(0) { }
267 // For compatibility with the CHECK_OK macro
268 CharacterRange(void* null) { ASSERT_EQ(NULL, null); } //NOLINT
269 CharacterRange(uc16 from, uc16 to) : from_(from), to_(to) { }
270 static void AddClassEscape(uc16 type, ZoneList<CharacterRange>* ranges);
271 static Vector<const uc16> GetWordBounds();
272 static inline CharacterRange Singleton(uc16 value) {
273 return CharacterRange(value, value);
274 }
275 static inline CharacterRange Range(uc16 from, uc16 to) {
276 ASSERT(from <= to);
277 return CharacterRange(from, to);
278 }
279 static inline CharacterRange Everything() {
280 return CharacterRange(0, 0xFFFF);
281 }
282 bool Contains(uc16 i) { return from_ <= i && i <= to_; }
283 uc16 from() const { return from_; }
284 void set_from(uc16 value) { from_ = value; }
285 uc16 to() const { return to_; }
286 void set_to(uc16 value) { to_ = value; }
287 bool is_valid() { return from_ <= to_; }
288 bool IsEverything(uc16 max) { return from_ == 0 && to_ >= max; }
289 bool IsSingleton() { return (from_ == to_); }
Steve Blockd0582a62009-12-15 09:54:21 +0000[diff] [blame]290 void AddCaseEquivalents(ZoneList<CharacterRange>* ranges, bool is_ascii);
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]291 static void Split(ZoneList<CharacterRange>* base,
292 Vector<const uc16> overlay,
293 ZoneList<CharacterRange>** included,
294 ZoneList<CharacterRange>** excluded);
Leon Clarkee46be812010-01-19 14:06:41 +0000[diff] [blame]295 // Whether a range list is in canonical form: Ranges ordered by from value,
296 // and ranges non-overlapping and non-adjacent.
297 static bool IsCanonical(ZoneList<CharacterRange>* ranges);
298 // Convert range list to canonical form. The characters covered by the ranges
299 // will still be the same, but no character is in more than one range, and
300 // adjacent ranges are merged. The resulting list may be shorter than the
301 // original, but cannot be longer.
302 static void Canonicalize(ZoneList<CharacterRange>* ranges);
303 // Check how the set of characters defined by a CharacterRange list relates
304 // to the set of word characters. List must be in canonical form.
305 static SetRelation WordCharacterRelation(ZoneList<CharacterRange>* ranges);
306 // Takes two character range lists (representing character sets) in canonical
307 // form and merges them.
308 // The characters that are only covered by the first set are added to
309 // first_set_only_out. the characters that are only in the second set are
310 // added to second_set_only_out, and the characters that are in both are
311 // added to both_sets_out.
312 // The pointers to first_set_only_out, second_set_only_out and both_sets_out
313 // should be to empty lists, but they need not be distinct, and may be NULL.
314 // If NULL, the characters are dropped, and if two arguments are the same
315 // pointer, the result is the union of the two sets that would be created
316 // if the pointers had been distinct.
317 // This way, the Merge function can compute all the usual set operations:
318 // union (all three out-sets are equal), intersection (only both_sets_out is
319 // non-NULL), and set difference (only first_set is non-NULL).
320 static void Merge(ZoneList<CharacterRange>* first_set,
321 ZoneList<CharacterRange>* second_set,
322 ZoneList<CharacterRange>* first_set_only_out,
323 ZoneList<CharacterRange>* second_set_only_out,
324 ZoneList<CharacterRange>* both_sets_out);
325 // Negate the contents of a character range in canonical form.
326 static void Negate(ZoneList<CharacterRange>* src,
327 ZoneList<CharacterRange>* dst);
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]328 static const int kStartMarker = (1 << 24);
329 static const int kPayloadMask = (1 << 24) - 1;
330
331 private:
332 uc16 from_;
333 uc16 to_;
334};
335
336
337// A set of unsigned integers that behaves especially well on small
338// integers (< 32). May do zone-allocation.
339class OutSet: public ZoneObject {
340 public:
341 OutSet() : first_(0), remaining_(NULL), successors_(NULL) { }
342 OutSet* Extend(unsigned value);
343 bool Get(unsigned value);
344 static const unsigned kFirstLimit = 32;
345
346 private:
347 // Destructively set a value in this set. In most cases you want
348 // to use Extend instead to ensure that only one instance exists
349 // that contains the same values.
350 void Set(unsigned value);
351
352 // The successors are a list of sets that contain the same values
353 // as this set and the one more value that is not present in this
354 // set.
355 ZoneList<OutSet*>* successors() { return successors_; }
356
357 OutSet(uint32_t first, ZoneList<unsigned>* remaining)
358 : first_(first), remaining_(remaining), successors_(NULL) { }
359 uint32_t first_;
360 ZoneList<unsigned>* remaining_;
361 ZoneList<OutSet*>* successors_;
362 friend class Trace;
363};
364
365
366// A mapping from integers, specified as ranges, to a set of integers.
367// Used for mapping character ranges to choices.
368class DispatchTable : public ZoneObject {
369 public:
370 class Entry {
371 public:
372 Entry() : from_(0), to_(0), out_set_(NULL) { }
373 Entry(uc16 from, uc16 to, OutSet* out_set)
374 : from_(from), to_(to), out_set_(out_set) { }
375 uc16 from() { return from_; }
376 uc16 to() { return to_; }
377 void set_to(uc16 value) { to_ = value; }
378 void AddValue(int value) { out_set_ = out_set_->Extend(value); }
379 OutSet* out_set() { return out_set_; }
380 private:
381 uc16 from_;
382 uc16 to_;
383 OutSet* out_set_;
384 };
385
386 class Config {
387 public:
388 typedef uc16 Key;
389 typedef Entry Value;
390 static const uc16 kNoKey;
391 static const Entry kNoValue;
392 static inline int Compare(uc16 a, uc16 b) {
393 if (a == b)
394 return 0;
395 else if (a < b)
396 return -1;
397 else
398 return 1;
399 }
400 };
401
402 void AddRange(CharacterRange range, int value);
403 OutSet* Get(uc16 value);
404 void Dump();
405
406 template <typename Callback>
407 void ForEach(Callback* callback) { return tree()->ForEach(callback); }
Ben Murdoch589d6972011-11-30 16:04:58 +0000[diff] [blame^]408
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]409 private:
410 // There can't be a static empty set since it allocates its
411 // successors in a zone and caches them.
412 OutSet* empty() { return &empty_; }
413 OutSet empty_;
414 ZoneSplayTree<Config>* tree() { return &tree_; }
415 ZoneSplayTree<Config> tree_;
416};
417
418
419#define FOR_EACH_NODE_TYPE(VISIT) \
420 VISIT(End) \
421 VISIT(Action) \
422 VISIT(Choice) \
423 VISIT(BackReference) \
424 VISIT(Assertion) \
425 VISIT(Text)
426
427
428#define FOR_EACH_REG_EXP_TREE_TYPE(VISIT) \
429 VISIT(Disjunction) \
430 VISIT(Alternative) \
431 VISIT(Assertion) \
432 VISIT(CharacterClass) \
433 VISIT(Atom) \
434 VISIT(Quantifier) \
435 VISIT(Capture) \
436 VISIT(Lookahead) \
437 VISIT(BackReference) \
438 VISIT(Empty) \
439 VISIT(Text)
440
441
442#define FORWARD_DECLARE(Name) class RegExp##Name;
443FOR_EACH_REG_EXP_TREE_TYPE(FORWARD_DECLARE)
444#undef FORWARD_DECLARE
445
446
447class TextElement {
448 public:
449 enum Type {UNINITIALIZED, ATOM, CHAR_CLASS};
450 TextElement() : type(UNINITIALIZED) { }
451 explicit TextElement(Type t) : type(t), cp_offset(-1) { }
452 static TextElement Atom(RegExpAtom* atom);
453 static TextElement CharClass(RegExpCharacterClass* char_class);
454 int length();
455 Type type;
456 union {
457 RegExpAtom* u_atom;
458 RegExpCharacterClass* u_char_class;
459 } data;
460 int cp_offset;
461};
462
463
464class Trace;
465
466
467struct NodeInfo {
468 NodeInfo()
469 : being_analyzed(false),
470 been_analyzed(false),
471 follows_word_interest(false),
472 follows_newline_interest(false),
473 follows_start_interest(false),
474 at_end(false),
475 visited(false) { }
476
477 // Returns true if the interests and assumptions of this node
478 // matches the given one.
479 bool Matches(NodeInfo* that) {
480 return (at_end == that->at_end) &&
481 (follows_word_interest == that->follows_word_interest) &&
482 (follows_newline_interest == that->follows_newline_interest) &&
483 (follows_start_interest == that->follows_start_interest);
484 }
485
486 // Updates the interests of this node given the interests of the
487 // node preceding it.
488 void AddFromPreceding(NodeInfo* that) {
489 at_end |= that->at_end;
490 follows_word_interest |= that->follows_word_interest;
491 follows_newline_interest |= that->follows_newline_interest;
492 follows_start_interest |= that->follows_start_interest;
493 }
494
495 bool HasLookbehind() {
496 return follows_word_interest ||
497 follows_newline_interest ||
498 follows_start_interest;
499 }
500
501 // Sets the interests of this node to include the interests of the
502 // following node.
503 void AddFromFollowing(NodeInfo* that) {
504 follows_word_interest |= that->follows_word_interest;
505 follows_newline_interest |= that->follows_newline_interest;
506 follows_start_interest |= that->follows_start_interest;
507 }
508
509 void ResetCompilationState() {
510 being_analyzed = false;
511 been_analyzed = false;
512 }
513
514 bool being_analyzed: 1;
515 bool been_analyzed: 1;
516
517 // These bits are set of this node has to know what the preceding
518 // character was.
519 bool follows_word_interest: 1;
520 bool follows_newline_interest: 1;
521 bool follows_start_interest: 1;
522
523 bool at_end: 1;
524 bool visited: 1;
525};
526
527
528class SiblingList {
529 public:
530 SiblingList() : list_(NULL) { }
531 int length() {
532 return list_ == NULL ? 0 : list_->length();
533 }
534 void Ensure(RegExpNode* parent) {
535 if (list_ == NULL) {
536 list_ = new ZoneList<RegExpNode*>(2);
537 list_->Add(parent);
538 }
539 }
540 void Add(RegExpNode* node) { list_->Add(node); }
541 RegExpNode* Get(int index) { return list_->at(index); }
542 private:
543 ZoneList<RegExpNode*>* list_;
544};
545
546
547// Details of a quick mask-compare check that can look ahead in the
548// input stream.
549class QuickCheckDetails {
550 public:
551 QuickCheckDetails()
552 : characters_(0),
553 mask_(0),
554 value_(0),
555 cannot_match_(false) { }
556 explicit QuickCheckDetails(int characters)
557 : characters_(characters),
558 mask_(0),
559 value_(0),
560 cannot_match_(false) { }
561 bool Rationalize(bool ascii);
562 // Merge in the information from another branch of an alternation.
563 void Merge(QuickCheckDetails* other, int from_index);
564 // Advance the current position by some amount.
565 void Advance(int by, bool ascii);
566 void Clear();
567 bool cannot_match() { return cannot_match_; }
568 void set_cannot_match() { cannot_match_ = true; }
569 struct Position {
570 Position() : mask(0), value(0), determines_perfectly(false) { }
571 uc16 mask;
572 uc16 value;
573 bool determines_perfectly;
574 };
575 int characters() { return characters_; }
576 void set_characters(int characters) { characters_ = characters; }
577 Position* positions(int index) {
578 ASSERT(index >= 0);
579 ASSERT(index < characters_);
580 return positions_ + index;
581 }
582 uint32_t mask() { return mask_; }
583 uint32_t value() { return value_; }
584
585 private:
586 // How many characters do we have quick check information from. This is
587 // the same for all branches of a choice node.
588 int characters_;
589 Position positions_[4];
590 // These values are the condensate of the above array after Rationalize().
591 uint32_t mask_;
592 uint32_t value_;
593 // If set to true, there is no way this quick check can match at all.
594 // E.g., if it requires to be at the start of the input, and isn't.
595 bool cannot_match_;
596};
597
598
599class RegExpNode: public ZoneObject {
600 public:
Leon Clarkee46be812010-01-19 14:06:41 +0000[diff] [blame]601 RegExpNode() : first_character_set_(NULL), trace_count_(0) { }
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]602 virtual ~RegExpNode();
603 virtual void Accept(NodeVisitor* visitor) = 0;
604 // Generates a goto to this node or actually generates the code at this point.
605 virtual void Emit(RegExpCompiler* compiler, Trace* trace) = 0;
606 // How many characters must this node consume at a minimum in order to
607 // succeed. If we have found at least 'still_to_find' characters that
608 // must be consumed there is no need to ask any following nodes whether
Ben Murdochb0fe1622011-05-05 13:52:32 +0100[diff] [blame]609 // they are sure to eat any more characters. The not_at_start argument is
610 // used to indicate that we know we are not at the start of the input. In
611 // this case anchored branches will always fail and can be ignored when
612 // determining how many characters are consumed on success.
613 virtual int EatsAtLeast(int still_to_find,
614 int recursion_depth,
615 bool not_at_start) = 0;
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]616 // Emits some quick code that checks whether the preloaded characters match.
617 // Falls through on certain failure, jumps to the label on possible success.
618 // If the node cannot make a quick check it does nothing and returns false.
619 bool EmitQuickCheck(RegExpCompiler* compiler,
620 Trace* trace,
621 bool preload_has_checked_bounds,
622 Label* on_possible_success,
623 QuickCheckDetails* details_return,
624 bool fall_through_on_failure);
625 // For a given number of characters this returns a mask and a value. The
626 // next n characters are anded with the mask and compared with the value.
627 // A comparison failure indicates the node cannot match the next n characters.
628 // A comparison success indicates the node may match.
629 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
630 RegExpCompiler* compiler,
631 int characters_filled_in,
632 bool not_at_start) = 0;
633 static const int kNodeIsTooComplexForGreedyLoops = -1;
634 virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; }
635 Label* label() { return &label_; }
636 // If non-generic code is generated for a node (ie the node is not at the
637 // start of the trace) then it cannot be reused. This variable sets a limit
638 // on how often we allow that to happen before we insist on starting a new
639 // trace and generating generic code for a node that can be reused by flushing
640 // the deferred actions in the current trace and generating a goto.
641 static const int kMaxCopiesCodeGenerated = 10;
642
643 NodeInfo* info() { return &info_; }
644
645 void AddSibling(RegExpNode* node) { siblings_.Add(node); }
646
647 // Static version of EnsureSibling that expresses the fact that the
648 // result has the same type as the input.
649 template <class C>
650 static C* EnsureSibling(C* node, NodeInfo* info, bool* cloned) {
651 return static_cast<C*>(node->EnsureSibling(info, cloned));
652 }
653
654 SiblingList* siblings() { return &siblings_; }
655 void set_siblings(SiblingList* other) { siblings_ = *other; }
656
Leon Clarkee46be812010-01-19 14:06:41 +0000[diff] [blame]657 // Return the set of possible next characters recognized by the regexp
658 // (or a safe subset, potentially the set of all characters).
659 ZoneList<CharacterRange>* FirstCharacterSet();
660
661 // Compute (if possible within the budget of traversed nodes) the
662 // possible first characters of the input matched by this node and
663 // its continuation. Returns the remaining budget after the computation.
664 // If the budget is spent, the result is negative, and the cached
665 // first_character_set_ value isn't set.
666 virtual int ComputeFirstCharacterSet(int budget);
667
668 // Get and set the cached first character set value.
669 ZoneList<CharacterRange>* first_character_set() {
670 return first_character_set_;
671 }
672 void set_first_character_set(ZoneList<CharacterRange>* character_set) {
673 first_character_set_ = character_set;
674 }
675
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]676 protected:
677 enum LimitResult { DONE, CONTINUE };
Leon Clarkee46be812010-01-19 14:06:41 +0000[diff] [blame]678 static const int kComputeFirstCharacterSetFail = -1;
679
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]680 LimitResult LimitVersions(RegExpCompiler* compiler, Trace* trace);
681
682 // Returns a sibling of this node whose interests and assumptions
683 // match the ones in the given node info. If no sibling exists NULL
684 // is returned.
685 RegExpNode* TryGetSibling(NodeInfo* info);
686
687 // Returns a sibling of this node whose interests match the ones in
688 // the given node info. The info must not contain any assertions.
689 // If no node exists a new one will be created by cloning the current
690 // node. The result will always be an instance of the same concrete
691 // class as this node.
692 RegExpNode* EnsureSibling(NodeInfo* info, bool* cloned);
693
694 // Returns a clone of this node initialized using the copy constructor
695 // of its concrete class. Note that the node may have to be pre-
696 // processed before it is on a usable state.
697 virtual RegExpNode* Clone() = 0;
698
699 private:
Leon Clarkee46be812010-01-19 14:06:41 +0000[diff] [blame]700 static const int kFirstCharBudget = 10;
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]701 Label label_;
702 NodeInfo info_;
703 SiblingList siblings_;
Leon Clarkee46be812010-01-19 14:06:41 +0000[diff] [blame]704 ZoneList<CharacterRange>* first_character_set_;
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]705 // This variable keeps track of how many times code has been generated for
706 // this node (in different traces). We don't keep track of where the
707 // generated code is located unless the code is generated at the start of
708 // a trace, in which case it is generic and can be reused by flushing the
709 // deferred operations in the current trace and generating a goto.
710 int trace_count_;
711};
712
713
714// A simple closed interval.
715class Interval {
716 public:
717 Interval() : from_(kNone), to_(kNone) { }
718 Interval(int from, int to) : from_(from), to_(to) { }
719 Interval Union(Interval that) {
720 if (that.from_ == kNone)
721 return *this;
722 else if (from_ == kNone)
723 return that;
724 else
725 return Interval(Min(from_, that.from_), Max(to_, that.to_));
726 }
727 bool Contains(int value) {
728 return (from_ <= value) && (value <= to_);
729 }
730 bool is_empty() { return from_ == kNone; }
731 int from() { return from_; }
732 int to() { return to_; }
733 static Interval Empty() { return Interval(); }
734 static const int kNone = -1;
735 private:
736 int from_;
737 int to_;
738};
739
740
741class SeqRegExpNode: public RegExpNode {
742 public:
743 explicit SeqRegExpNode(RegExpNode* on_success)
744 : on_success_(on_success) { }
745 RegExpNode* on_success() { return on_success_; }
746 void set_on_success(RegExpNode* node) { on_success_ = node; }
747 private:
748 RegExpNode* on_success_;
749};
750
751
752class ActionNode: public SeqRegExpNode {
753 public:
754 enum Type {
755 SET_REGISTER,
756 INCREMENT_REGISTER,
757 STORE_POSITION,
758 BEGIN_SUBMATCH,
759 POSITIVE_SUBMATCH_SUCCESS,
760 EMPTY_MATCH_CHECK,
761 CLEAR_CAPTURES
762 };
763 static ActionNode* SetRegister(int reg, int val, RegExpNode* on_success);
764 static ActionNode* IncrementRegister(int reg, RegExpNode* on_success);
765 static ActionNode* StorePosition(int reg,
766 bool is_capture,
767 RegExpNode* on_success);
768 static ActionNode* ClearCaptures(Interval range, RegExpNode* on_success);
769 static ActionNode* BeginSubmatch(int stack_pointer_reg,
770 int position_reg,
771 RegExpNode* on_success);
772 static ActionNode* PositiveSubmatchSuccess(int stack_pointer_reg,
773 int restore_reg,
774 int clear_capture_count,
775 int clear_capture_from,
776 RegExpNode* on_success);
777 static ActionNode* EmptyMatchCheck(int start_register,
778 int repetition_register,
779 int repetition_limit,
780 RegExpNode* on_success);
781 virtual void Accept(NodeVisitor* visitor);
782 virtual void Emit(RegExpCompiler* compiler, Trace* trace);
Ben Murdochb0fe1622011-05-05 13:52:32 +0100[diff] [blame]783 virtual int EatsAtLeast(int still_to_find,
784 int recursion_depth,
785 bool not_at_start);
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]786 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
787 RegExpCompiler* compiler,
788 int filled_in,
789 bool not_at_start) {
790 return on_success()->GetQuickCheckDetails(
791 details, compiler, filled_in, not_at_start);
792 }
793 Type type() { return type_; }
794 // TODO(erikcorry): We should allow some action nodes in greedy loops.
795 virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; }
796 virtual ActionNode* Clone() { return new ActionNode(*this); }
Leon Clarkee46be812010-01-19 14:06:41 +0000[diff] [blame]797 virtual int ComputeFirstCharacterSet(int budget);
Ben Murdoch589d6972011-11-30 16:04:58 +0000[diff] [blame^]798
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]799 private:
800 union {
801 struct {
802 int reg;
803 int value;
804 } u_store_register;
805 struct {
806 int reg;
807 } u_increment_register;
808 struct {
809 int reg;
810 bool is_capture;
811 } u_position_register;
812 struct {
813 int stack_pointer_register;
814 int current_position_register;
815 int clear_register_count;
816 int clear_register_from;
817 } u_submatch;
818 struct {
819 int start_register;
820 int repetition_register;
821 int repetition_limit;
822 } u_empty_match_check;
823 struct {
824 int range_from;
825 int range_to;
826 } u_clear_captures;
827 } data_;
828 ActionNode(Type type, RegExpNode* on_success)
829 : SeqRegExpNode(on_success),
830 type_(type) { }
831 Type type_;
832 friend class DotPrinter;
833};
834
835
836class TextNode: public SeqRegExpNode {
837 public:
838 TextNode(ZoneList<TextElement>* elms,
839 RegExpNode* on_success)
840 : SeqRegExpNode(on_success),
841 elms_(elms) { }
842 TextNode(RegExpCharacterClass* that,
843 RegExpNode* on_success)
844 : SeqRegExpNode(on_success),
845 elms_(new ZoneList<TextElement>(1)) {
846 elms_->Add(TextElement::CharClass(that));
847 }
848 virtual void Accept(NodeVisitor* visitor);
849 virtual void Emit(RegExpCompiler* compiler, Trace* trace);
Ben Murdochb0fe1622011-05-05 13:52:32 +0100[diff] [blame]850 virtual int EatsAtLeast(int still_to_find,
851 int recursion_depth,
852 bool not_at_start);
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]853 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
854 RegExpCompiler* compiler,
855 int characters_filled_in,
856 bool not_at_start);
857 ZoneList<TextElement>* elements() { return elms_; }
Steve Blockd0582a62009-12-15 09:54:21 +0000[diff] [blame]858 void MakeCaseIndependent(bool is_ascii);
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]859 virtual int GreedyLoopTextLength();
860 virtual TextNode* Clone() {
861 TextNode* result = new TextNode(*this);
862 result->CalculateOffsets();
863 return result;
864 }
865 void CalculateOffsets();
Leon Clarkee46be812010-01-19 14:06:41 +0000[diff] [blame]866 virtual int ComputeFirstCharacterSet(int budget);
Ben Murdoch589d6972011-11-30 16:04:58 +0000[diff] [blame^]867
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]868 private:
869 enum TextEmitPassType {
870 NON_ASCII_MATCH, // Check for characters that can't match.
871 SIMPLE_CHARACTER_MATCH, // Case-dependent single character check.
872 NON_LETTER_CHARACTER_MATCH, // Check characters that have no case equivs.
873 CASE_CHARACTER_MATCH, // Case-independent single character check.
874 CHARACTER_CLASS_MATCH // Character class.
875 };
876 static bool SkipPass(int pass, bool ignore_case);
877 static const int kFirstRealPass = SIMPLE_CHARACTER_MATCH;
878 static const int kLastPass = CHARACTER_CLASS_MATCH;
879 void TextEmitPass(RegExpCompiler* compiler,
880 TextEmitPassType pass,
881 bool preloaded,
882 Trace* trace,
883 bool first_element_checked,
884 int* checked_up_to);
885 int Length();
886 ZoneList<TextElement>* elms_;
887};
888
889
890class AssertionNode: public SeqRegExpNode {
891 public:
892 enum AssertionNodeType {
893 AT_END,
894 AT_START,
895 AT_BOUNDARY,
896 AT_NON_BOUNDARY,
Leon Clarkee46be812010-01-19 14:06:41 +0000[diff] [blame]897 AFTER_NEWLINE,
898 // Types not directly expressible in regexp syntax.
899 // Used for modifying a boundary node if its following character is
900 // known to be word and/or non-word.
901 AFTER_NONWORD_CHARACTER,
902 AFTER_WORD_CHARACTER
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]903 };
904 static AssertionNode* AtEnd(RegExpNode* on_success) {
905 return new AssertionNode(AT_END, on_success);
906 }
907 static AssertionNode* AtStart(RegExpNode* on_success) {
908 return new AssertionNode(AT_START, on_success);
909 }
910 static AssertionNode* AtBoundary(RegExpNode* on_success) {
911 return new AssertionNode(AT_BOUNDARY, on_success);
912 }
913 static AssertionNode* AtNonBoundary(RegExpNode* on_success) {
914 return new AssertionNode(AT_NON_BOUNDARY, on_success);
915 }
916 static AssertionNode* AfterNewline(RegExpNode* on_success) {
917 return new AssertionNode(AFTER_NEWLINE, on_success);
918 }
919 virtual void Accept(NodeVisitor* visitor);
920 virtual void Emit(RegExpCompiler* compiler, Trace* trace);
Ben Murdochb0fe1622011-05-05 13:52:32 +0100[diff] [blame]921 virtual int EatsAtLeast(int still_to_find,
922 int recursion_depth,
923 bool not_at_start);
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]924 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
925 RegExpCompiler* compiler,
926 int filled_in,
927 bool not_at_start);
Leon Clarkee46be812010-01-19 14:06:41 +0000[diff] [blame]928 virtual int ComputeFirstCharacterSet(int budget);
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]929 virtual AssertionNode* Clone() { return new AssertionNode(*this); }
930 AssertionNodeType type() { return type_; }
Leon Clarkee46be812010-01-19 14:06:41 +0000[diff] [blame]931 void set_type(AssertionNodeType type) { type_ = type; }
Ben Murdoch589d6972011-11-30 16:04:58 +0000[diff] [blame^]932
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]933 private:
934 AssertionNode(AssertionNodeType t, RegExpNode* on_success)
935 : SeqRegExpNode(on_success), type_(t) { }
936 AssertionNodeType type_;
937};
938
939
940class BackReferenceNode: public SeqRegExpNode {
941 public:
942 BackReferenceNode(int start_reg,
943 int end_reg,
944 RegExpNode* on_success)
945 : SeqRegExpNode(on_success),
946 start_reg_(start_reg),
947 end_reg_(end_reg) { }
948 virtual void Accept(NodeVisitor* visitor);
949 int start_register() { return start_reg_; }
950 int end_register() { return end_reg_; }
951 virtual void Emit(RegExpCompiler* compiler, Trace* trace);
Ben Murdochb0fe1622011-05-05 13:52:32 +0100[diff] [blame]952 virtual int EatsAtLeast(int still_to_find,
953 int recursion_depth,
954 bool not_at_start);
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]955 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
956 RegExpCompiler* compiler,
957 int characters_filled_in,
958 bool not_at_start) {
959 return;
960 }
961 virtual BackReferenceNode* Clone() { return new BackReferenceNode(*this); }
Leon Clarkee46be812010-01-19 14:06:41 +0000[diff] [blame]962 virtual int ComputeFirstCharacterSet(int budget);
Ben Murdoch589d6972011-11-30 16:04:58 +0000[diff] [blame^]963
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]964 private:
965 int start_reg_;
966 int end_reg_;
967};
968
969
970class EndNode: public RegExpNode {
971 public:
972 enum Action { ACCEPT, BACKTRACK, NEGATIVE_SUBMATCH_SUCCESS };
973 explicit EndNode(Action action) : action_(action) { }
974 virtual void Accept(NodeVisitor* visitor);
975 virtual void Emit(RegExpCompiler* compiler, Trace* trace);
Ben Murdochb0fe1622011-05-05 13:52:32 +0100[diff] [blame]976 virtual int EatsAtLeast(int still_to_find,
977 int recursion_depth,
978 bool not_at_start) { return 0; }
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]979 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
980 RegExpCompiler* compiler,
981 int characters_filled_in,
982 bool not_at_start) {
983 // Returning 0 from EatsAtLeast should ensure we never get here.
984 UNREACHABLE();
985 }
986 virtual EndNode* Clone() { return new EndNode(*this); }
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]987 private:
988 Action action_;
989};
990
991
992class NegativeSubmatchSuccess: public EndNode {
993 public:
994 NegativeSubmatchSuccess(int stack_pointer_reg,
995 int position_reg,
996 int clear_capture_count,
997 int clear_capture_start)
998 : EndNode(NEGATIVE_SUBMATCH_SUCCESS),
999 stack_pointer_register_(stack_pointer_reg),
1000 current_position_register_(position_reg),
1001 clear_capture_count_(clear_capture_count),
1002 clear_capture_start_(clear_capture_start) { }
1003 virtual void Emit(RegExpCompiler* compiler, Trace* trace);
1004
1005 private:
1006 int stack_pointer_register_;
1007 int current_position_register_;
1008 int clear_capture_count_;
1009 int clear_capture_start_;
1010};
1011
1012
1013class Guard: public ZoneObject {
1014 public:
1015 enum Relation { LT, GEQ };
1016 Guard(int reg, Relation op, int value)
1017 : reg_(reg),
1018 op_(op),
1019 value_(value) { }
1020 int reg() { return reg_; }
1021 Relation op() { return op_; }
1022 int value() { return value_; }
1023
1024 private:
1025 int reg_;
1026 Relation op_;
1027 int value_;
1028};
1029
1030
1031class GuardedAlternative {
1032 public:
1033 explicit GuardedAlternative(RegExpNode* node) : node_(node), guards_(NULL) { }
1034 void AddGuard(Guard* guard);
1035 RegExpNode* node() { return node_; }
1036 void set_node(RegExpNode* node) { node_ = node; }
1037 ZoneList<Guard*>* guards() { return guards_; }
1038
1039 private:
1040 RegExpNode* node_;
1041 ZoneList<Guard*>* guards_;
1042};
1043
1044
1045class AlternativeGeneration;
1046
1047
1048class ChoiceNode: public RegExpNode {
1049 public:
1050 explicit ChoiceNode(int expected_size)
1051 : alternatives_(new ZoneList<GuardedAlternative>(expected_size)),
1052 table_(NULL),
1053 not_at_start_(false),
1054 being_calculated_(false) { }
1055 virtual void Accept(NodeVisitor* visitor);
1056 void AddAlternative(GuardedAlternative node) { alternatives()->Add(node); }
1057 ZoneList<GuardedAlternative>* alternatives() { return alternatives_; }
1058 DispatchTable* GetTable(bool ignore_case);
1059 virtual void Emit(RegExpCompiler* compiler, Trace* trace);
Ben Murdochb0fe1622011-05-05 13:52:32 +0100[diff] [blame]1060 virtual int EatsAtLeast(int still_to_find,
1061 int recursion_depth,
1062 bool not_at_start);
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]1063 int EatsAtLeastHelper(int still_to_find,
1064 int recursion_depth,
Ben Murdochb0fe1622011-05-05 13:52:32 +0100[diff] [blame]1065 RegExpNode* ignore_this_node,
1066 bool not_at_start);
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]1067 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
1068 RegExpCompiler* compiler,
1069 int characters_filled_in,
1070 bool not_at_start);
1071 virtual ChoiceNode* Clone() { return new ChoiceNode(*this); }
1072
1073 bool being_calculated() { return being_calculated_; }
1074 bool not_at_start() { return not_at_start_; }
1075 void set_not_at_start() { not_at_start_ = true; }
1076 void set_being_calculated(bool b) { being_calculated_ = b; }
1077 virtual bool try_to_emit_quick_check_for_alternative(int i) { return true; }
1078
1079 protected:
Ben Murdoch589d6972011-11-30 16:04:58 +0000[diff] [blame^]1080 int GreedyLoopTextLengthForAlternative(GuardedAlternative* alternative);
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]1081 ZoneList<GuardedAlternative>* alternatives_;
1082
1083 private:
1084 friend class DispatchTableConstructor;
1085 friend class Analysis;
1086 void GenerateGuard(RegExpMacroAssembler* macro_assembler,
1087 Guard* guard,
1088 Trace* trace);
Ben Murdochb0fe1622011-05-05 13:52:32 +0100[diff] [blame]1089 int CalculatePreloadCharacters(RegExpCompiler* compiler, bool not_at_start);
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]1090 void EmitOutOfLineContinuation(RegExpCompiler* compiler,
1091 Trace* trace,
1092 GuardedAlternative alternative,
1093 AlternativeGeneration* alt_gen,
1094 int preload_characters,
1095 bool next_expects_preload);
1096 DispatchTable* table_;
1097 // If true, this node is never checked at the start of the input.
1098 // Allows a new trace to start with at_start() set to false.
1099 bool not_at_start_;
1100 bool being_calculated_;
1101};
1102
1103
1104class NegativeLookaheadChoiceNode: public ChoiceNode {
1105 public:
1106 explicit NegativeLookaheadChoiceNode(GuardedAlternative this_must_fail,
1107 GuardedAlternative then_do_this)
1108 : ChoiceNode(2) {
1109 AddAlternative(this_must_fail);
1110 AddAlternative(then_do_this);
1111 }
Ben Murdochb0fe1622011-05-05 13:52:32 +0100[diff] [blame]1112 virtual int EatsAtLeast(int still_to_find,
1113 int recursion_depth,
1114 bool not_at_start);
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]1115 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
1116 RegExpCompiler* compiler,
1117 int characters_filled_in,
1118 bool not_at_start);
1119 // For a negative lookahead we don't emit the quick check for the
1120 // alternative that is expected to fail. This is because quick check code
1121 // starts by loading enough characters for the alternative that takes fewest
1122 // characters, but on a negative lookahead the negative branch did not take
1123 // part in that calculation (EatsAtLeast) so the assumptions don't hold.
1124 virtual bool try_to_emit_quick_check_for_alternative(int i) { return i != 0; }
Leon Clarkee46be812010-01-19 14:06:41 +0000[diff] [blame]1125 virtual int ComputeFirstCharacterSet(int budget);
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]1126};
1127
1128
1129class LoopChoiceNode: public ChoiceNode {
1130 public:
1131 explicit LoopChoiceNode(bool body_can_be_zero_length)
1132 : ChoiceNode(2),
1133 loop_node_(NULL),
1134 continue_node_(NULL),
1135 body_can_be_zero_length_(body_can_be_zero_length) { }
1136 void AddLoopAlternative(GuardedAlternative alt);
1137 void AddContinueAlternative(GuardedAlternative alt);
1138 virtual void Emit(RegExpCompiler* compiler, Trace* trace);
Ben Murdochb0fe1622011-05-05 13:52:32 +0100[diff] [blame]1139 virtual int EatsAtLeast(int still_to_find,
1140 int recursion_depth,
1141 bool not_at_start);
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]1142 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
1143 RegExpCompiler* compiler,
1144 int characters_filled_in,
1145 bool not_at_start);
Leon Clarkee46be812010-01-19 14:06:41 +0000[diff] [blame]1146 virtual int ComputeFirstCharacterSet(int budget);
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]1147 virtual LoopChoiceNode* Clone() { return new LoopChoiceNode(*this); }
1148 RegExpNode* loop_node() { return loop_node_; }
1149 RegExpNode* continue_node() { return continue_node_; }
1150 bool body_can_be_zero_length() { return body_can_be_zero_length_; }
1151 virtual void Accept(NodeVisitor* visitor);
1152
1153 private:
1154 // AddAlternative is made private for loop nodes because alternatives
1155 // should not be added freely, we need to keep track of which node
1156 // goes back to the node itself.
1157 void AddAlternative(GuardedAlternative node) {
1158 ChoiceNode::AddAlternative(node);
1159 }
1160
1161 RegExpNode* loop_node_;
1162 RegExpNode* continue_node_;
1163 bool body_can_be_zero_length_;
1164};
1165
1166
1167// There are many ways to generate code for a node. This class encapsulates
1168// the current way we should be generating. In other words it encapsulates
1169// the current state of the code generator. The effect of this is that we
1170// generate code for paths that the matcher can take through the regular
1171// expression. A given node in the regexp can be code-generated several times
1172// as it can be part of several traces. For example for the regexp:
1173// /foo(bar|ip)baz/ the code to match baz will be generated twice, once as part
1174// of the foo-bar-baz trace and once as part of the foo-ip-baz trace. The code
1175// to match foo is generated only once (the traces have a common prefix). The
1176// code to store the capture is deferred and generated (twice) after the places
1177// where baz has been matched.
1178class Trace {
1179 public:
1180 // A value for a property that is either known to be true, know to be false,
1181 // or not known.
1182 enum TriBool {
1183 UNKNOWN = -1, FALSE = 0, TRUE = 1
1184 };
1185
1186 class DeferredAction {
1187 public:
1188 DeferredAction(ActionNode::Type type, int reg)
1189 : type_(type), reg_(reg), next_(NULL) { }
1190 DeferredAction* next() { return next_; }
1191 bool Mentions(int reg);
1192 int reg() { return reg_; }
1193 ActionNode::Type type() { return type_; }
1194 private:
1195 ActionNode::Type type_;
1196 int reg_;
1197 DeferredAction* next_;
1198 friend class Trace;
1199 };
1200
1201 class DeferredCapture : public DeferredAction {
1202 public:
1203 DeferredCapture(int reg, bool is_capture, Trace* trace)
1204 : DeferredAction(ActionNode::STORE_POSITION, reg),
1205 cp_offset_(trace->cp_offset()),
1206 is_capture_(is_capture) { }
1207 int cp_offset() { return cp_offset_; }
1208 bool is_capture() { return is_capture_; }
1209 private:
1210 int cp_offset_;
1211 bool is_capture_;
1212 void set_cp_offset(int cp_offset) { cp_offset_ = cp_offset; }
1213 };
1214
1215 class DeferredSetRegister : public DeferredAction {
1216 public:
1217 DeferredSetRegister(int reg, int value)
1218 : DeferredAction(ActionNode::SET_REGISTER, reg),
1219 value_(value) { }
1220 int value() { return value_; }
1221 private:
1222 int value_;
1223 };
1224
1225 class DeferredClearCaptures : public DeferredAction {
1226 public:
1227 explicit DeferredClearCaptures(Interval range)
1228 : DeferredAction(ActionNode::CLEAR_CAPTURES, -1),
1229 range_(range) { }
1230 Interval range() { return range_; }
1231 private:
1232 Interval range_;
1233 };
1234
1235 class DeferredIncrementRegister : public DeferredAction {
1236 public:
1237 explicit DeferredIncrementRegister(int reg)
1238 : DeferredAction(ActionNode::INCREMENT_REGISTER, reg) { }
1239 };
1240
1241 Trace()
1242 : cp_offset_(0),
1243 actions_(NULL),
1244 backtrack_(NULL),
1245 stop_node_(NULL),
1246 loop_label_(NULL),
1247 characters_preloaded_(0),
1248 bound_checked_up_to_(0),
1249 flush_budget_(100),
1250 at_start_(UNKNOWN) { }
1251
1252 // End the trace. This involves flushing the deferred actions in the trace
1253 // and pushing a backtrack location onto the backtrack stack. Once this is
1254 // done we can start a new trace or go to one that has already been
1255 // generated.
1256 void Flush(RegExpCompiler* compiler, RegExpNode* successor);
1257 int cp_offset() { return cp_offset_; }
1258 DeferredAction* actions() { return actions_; }
1259 // A trivial trace is one that has no deferred actions or other state that
1260 // affects the assumptions used when generating code. There is no recorded
1261 // backtrack location in a trivial trace, so with a trivial trace we will
1262 // generate code that, on a failure to match, gets the backtrack location
1263 // from the backtrack stack rather than using a direct jump instruction. We
1264 // always start code generation with a trivial trace and non-trivial traces
1265 // are created as we emit code for nodes or add to the list of deferred
1266 // actions in the trace. The location of the code generated for a node using
1267 // a trivial trace is recorded in a label in the node so that gotos can be
1268 // generated to that code.
1269 bool is_trivial() {
1270 return backtrack_ == NULL &&
1271 actions_ == NULL &&
1272 cp_offset_ == 0 &&
1273 characters_preloaded_ == 0 &&
1274 bound_checked_up_to_ == 0 &&
1275 quick_check_performed_.characters() == 0 &&
1276 at_start_ == UNKNOWN;
1277 }
1278 TriBool at_start() { return at_start_; }
1279 void set_at_start(bool at_start) { at_start_ = at_start ? TRUE : FALSE; }
1280 Label* backtrack() { return backtrack_; }
1281 Label* loop_label() { return loop_label_; }
1282 RegExpNode* stop_node() { return stop_node_; }
1283 int characters_preloaded() { return characters_preloaded_; }
1284 int bound_checked_up_to() { return bound_checked_up_to_; }
1285 int flush_budget() { return flush_budget_; }
1286 QuickCheckDetails* quick_check_performed() { return &quick_check_performed_; }
1287 bool mentions_reg(int reg);
1288 // Returns true if a deferred position store exists to the specified
1289 // register and stores the offset in the out-parameter. Otherwise
1290 // returns false.
1291 bool GetStoredPosition(int reg, int* cp_offset);
1292 // These set methods and AdvanceCurrentPositionInTrace should be used only on
1293 // new traces - the intention is that traces are immutable after creation.
1294 void add_action(DeferredAction* new_action) {
1295 ASSERT(new_action->next_ == NULL);
1296 new_action->next_ = actions_;
1297 actions_ = new_action;
1298 }
1299 void set_backtrack(Label* backtrack) { backtrack_ = backtrack; }
1300 void set_stop_node(RegExpNode* node) { stop_node_ = node; }
1301 void set_loop_label(Label* label) { loop_label_ = label; }
Leon Clarkee46be812010-01-19 14:06:41 +0000[diff] [blame]1302 void set_characters_preloaded(int count) { characters_preloaded_ = count; }
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]1303 void set_bound_checked_up_to(int to) { bound_checked_up_to_ = to; }
1304 void set_flush_budget(int to) { flush_budget_ = to; }
1305 void set_quick_check_performed(QuickCheckDetails* d) {
1306 quick_check_performed_ = *d;
1307 }
1308 void InvalidateCurrentCharacter();
1309 void AdvanceCurrentPositionInTrace(int by, RegExpCompiler* compiler);
Ben Murdoch589d6972011-11-30 16:04:58 +0000[diff] [blame^]1310
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]1311 private:
1312 int FindAffectedRegisters(OutSet* affected_registers);
1313 void PerformDeferredActions(RegExpMacroAssembler* macro,
1314 int max_register,
1315 OutSet& affected_registers,
1316 OutSet* registers_to_pop,
1317 OutSet* registers_to_clear);
1318 void RestoreAffectedRegisters(RegExpMacroAssembler* macro,
1319 int max_register,
1320 OutSet& registers_to_pop,
1321 OutSet& registers_to_clear);
1322 int cp_offset_;
1323 DeferredAction* actions_;
1324 Label* backtrack_;
1325 RegExpNode* stop_node_;
1326 Label* loop_label_;
1327 int characters_preloaded_;
1328 int bound_checked_up_to_;
1329 QuickCheckDetails quick_check_performed_;
1330 int flush_budget_;
1331 TriBool at_start_;
1332};
1333
1334
1335class NodeVisitor {
1336 public:
1337 virtual ~NodeVisitor() { }
1338#define DECLARE_VISIT(Type) \
1339 virtual void Visit##Type(Type##Node* that) = 0;
1340FOR_EACH_NODE_TYPE(DECLARE_VISIT)
1341#undef DECLARE_VISIT
1342 virtual void VisitLoopChoice(LoopChoiceNode* that) { VisitChoice(that); }
1343};
1344
1345
1346// Node visitor used to add the start set of the alternatives to the
1347// dispatch table of a choice node.
1348class DispatchTableConstructor: public NodeVisitor {
1349 public:
1350 DispatchTableConstructor(DispatchTable* table, bool ignore_case)
1351 : table_(table),
1352 choice_index_(-1),
1353 ignore_case_(ignore_case) { }
1354
1355 void BuildTable(ChoiceNode* node);
1356
1357 void AddRange(CharacterRange range) {
1358 table()->AddRange(range, choice_index_);
1359 }
1360
1361 void AddInverse(ZoneList<CharacterRange>* ranges);
1362
1363#define DECLARE_VISIT(Type) \
1364 virtual void Visit##Type(Type##Node* that);
1365FOR_EACH_NODE_TYPE(DECLARE_VISIT)
1366#undef DECLARE_VISIT
1367
1368 DispatchTable* table() { return table_; }
1369 void set_choice_index(int value) { choice_index_ = value; }
1370
1371 protected:
1372 DispatchTable* table_;
1373 int choice_index_;
1374 bool ignore_case_;
1375};
1376
1377
1378// Assertion propagation moves information about assertions such as
1379// \b to the affected nodes. For instance, in /.\b./ information must
1380// be propagated to the first '.' that whatever follows needs to know
1381// if it matched a word or a non-word, and to the second '.' that it
1382// has to check if it succeeds a word or non-word. In this case the
1383// result will be something like:
1384//
1385// +-------+ +------------+
1386// | . | | . |
1387// +-------+ ---> +------------+
1388// | word? | | check word |
1389// +-------+ +------------+
1390class Analysis: public NodeVisitor {
1391 public:
Steve Blockd0582a62009-12-15 09:54:21 +0000[diff] [blame]1392 Analysis(bool ignore_case, bool is_ascii)
1393 : ignore_case_(ignore_case),
1394 is_ascii_(is_ascii),
1395 error_message_(NULL) { }
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]1396 void EnsureAnalyzed(RegExpNode* node);
1397
1398#define DECLARE_VISIT(Type) \
1399 virtual void Visit##Type(Type##Node* that);
1400FOR_EACH_NODE_TYPE(DECLARE_VISIT)
1401#undef DECLARE_VISIT
1402 virtual void VisitLoopChoice(LoopChoiceNode* that);
1403
1404 bool has_failed() { return error_message_ != NULL; }
1405 const char* error_message() {
1406 ASSERT(error_message_ != NULL);
1407 return error_message_;
1408 }
1409 void fail(const char* error_message) {
1410 error_message_ = error_message;
1411 }
Ben Murdoch589d6972011-11-30 16:04:58 +0000[diff] [blame^]1412
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]1413 private:
1414 bool ignore_case_;
Steve Blockd0582a62009-12-15 09:54:21 +0000[diff] [blame]1415 bool is_ascii_;
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]1416 const char* error_message_;
1417
1418 DISALLOW_IMPLICIT_CONSTRUCTORS(Analysis);
1419};
1420
1421
1422struct RegExpCompileData {
1423 RegExpCompileData()
1424 : tree(NULL),
1425 node(NULL),
1426 simple(true),
1427 contains_anchor(false),
1428 capture_count(0) { }
1429 RegExpTree* tree;
1430 RegExpNode* node;
1431 bool simple;
1432 bool contains_anchor;
1433 Handle<String> error;
1434 int capture_count;
1435};
1436
1437
1438class RegExpEngine: public AllStatic {
1439 public:
1440 struct CompilationResult {
1441 explicit CompilationResult(const char* error_message)
1442 : error_message(error_message),
Steve Block44f0eee2011-05-26 01:26:41 +0100[diff] [blame]1443 code(HEAP->the_hole_value()),
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]1444 num_registers(0) {}
1445 CompilationResult(Object* code, int registers)
1446 : error_message(NULL),
1447 code(code),
1448 num_registers(registers) {}
1449 const char* error_message;
1450 Object* code;
1451 int num_registers;
1452 };
1453
1454 static CompilationResult Compile(RegExpCompileData* input,
1455 bool ignore_case,
1456 bool multiline,
1457 Handle<String> pattern,
1458 bool is_ascii);
1459
1460 static void DotPrint(const char* label, RegExpNode* node, bool ignore_case);
1461};
1462
1463
Leon Clarkee46be812010-01-19 14:06:41 +0000[diff] [blame]1464class OffsetsVector {
1465 public:
Ben Murdoch8b112d22011-06-08 16:22:53 +0100[diff] [blame]1466 explicit inline OffsetsVector(int num_registers)
Leon Clarkee46be812010-01-19 14:06:41 +0000[diff] [blame]1467 : offsets_vector_length_(num_registers) {
Steve Block44f0eee2011-05-26 01:26:41 +0100[diff] [blame]1468 if (offsets_vector_length_ > Isolate::kJSRegexpStaticOffsetsVectorSize) {
Leon Clarkee46be812010-01-19 14:06:41 +0000[diff] [blame]1469 vector_ = NewArray<int>(offsets_vector_length_);
1470 } else {
Steve Block44f0eee2011-05-26 01:26:41 +0100[diff] [blame]1471 vector_ = Isolate::Current()->jsregexp_static_offsets_vector();
Leon Clarkee46be812010-01-19 14:06:41 +0000[diff] [blame]1472 }
1473 }
1474 inline ~OffsetsVector() {
Steve Block44f0eee2011-05-26 01:26:41 +0100[diff] [blame]1475 if (offsets_vector_length_ > Isolate::kJSRegexpStaticOffsetsVectorSize) {
Leon Clarkee46be812010-01-19 14:06:41 +0000[diff] [blame]1476 DeleteArray(vector_);
1477 vector_ = NULL;
1478 }
1479 }
1480 inline int* vector() { return vector_; }
1481 inline int length() { return offsets_vector_length_; }
1482
1483 static const int kStaticOffsetsVectorSize = 50;
1484
1485 private:
Steve Block44f0eee2011-05-26 01:26:41 +0100[diff] [blame]1486 static Address static_offsets_vector_address(Isolate* isolate) {
1487 return reinterpret_cast<Address>(isolate->jsregexp_static_offsets_vector());
Leon Clarkee46be812010-01-19 14:06:41 +0000[diff] [blame]1488 }
1489
1490 int* vector_;
1491 int offsets_vector_length_;
Leon Clarkee46be812010-01-19 14:06:41 +0000[diff] [blame]1492
1493 friend class ExternalReference;
1494};
1495
1496
Steve Blocka7e24c12009-10-30 11:49:00 +0000[diff] [blame]1497} } // namespace v8::internal
1498
1499#endif // V8_JSREGEXP_H_