blob: 3ed5a7e43da743b3c4101d72a2e6192fff0755e6 [file] [log] [blame]
Steve Blocka7e24c12009-10-30 11:49:00 +00001// 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
Steve Block3ce2e202009-11-05 08:53:23 +000031#include "macro-assembler.h"
Steve Block6ded16b2010-05-10 14:33:55 +010032#include "zone-inl.h"
Steve Block3ce2e202009-11-05 08:53:23 +000033
Steve Blocka7e24c12009-10-30 11:49:00 +000034namespace 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 +010045#ifdef V8_INTERPRETED_REGEXP
Steve Blocka7e24c12009-10-30 11:49:00 +000046 return false;
Steve Block6ded16b2010-05-10 14:33:55 +010047#else
48 return true;
Steve Blocka7e24c12009-10-30 11:49:00 +000049#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 +000079 // Prepares a JSRegExp object with Irregexp-specific data.
Steve Block6ded16b2010-05-10 14:33:55 +010080 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 +000084
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 +010096 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 +0100117 Vector<int> registers);
Steve Block6ded16b2010-05-10 14:33:55 +0100118
Steve Blocka7e24c12009-10-30 11:49:00 +0000119 // 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 +0000128 // Array index in the lastMatchInfo array.
Steve Blocka7e24c12009-10-30 11:49:00 +0000129 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 +0000135 // 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 +0000145 // 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
178 private:
179 static String* last_ascii_string_;
180 static String* two_byte_cached_string_;
181
182 static bool CompileIrregexp(Handle<JSRegExp> re, bool is_ascii);
183 static inline bool EnsureCompiledIrregexp(Handle<JSRegExp> re, bool is_ascii);
184
185
186 // Set the subject cache. The previous string buffer is not deleted, so the
187 // caller should ensure that it doesn't leak.
188 static void SetSubjectCache(String* subject,
189 char* utf8_subject,
190 int uft8_length,
191 int character_position,
192 int utf8_position);
193
194 // A one element cache of the last utf8_subject string and its length. The
195 // subject JS String object is cached in the heap. We also cache a
196 // translation between position and utf8 position.
197 static char* utf8_subject_cache_;
198 static int utf8_length_cache_;
199 static int utf8_position_;
200 static int character_position_;
201};
202
203
Leon Clarkee46be812010-01-19 14:06:41 +0000204// Represents the location of one element relative to the intersection of
205// two sets. Corresponds to the four areas of a Venn diagram.
206enum ElementInSetsRelation {
207 kInsideNone = 0,
208 kInsideFirst = 1,
209 kInsideSecond = 2,
210 kInsideBoth = 3
211};
212
213
214// Represents the relation of two sets.
215// Sets can be either disjoint, partially or fully overlapping, or equal.
216class SetRelation BASE_EMBEDDED {
217 public:
218 // Relation is represented by a bit saying whether there are elements in
219 // one set that is not in the other, and a bit saying that there are elements
220 // that are in both sets.
221
222 // Location of an element. Corresponds to the internal areas of
223 // a Venn diagram.
224 enum {
225 kInFirst = 1 << kInsideFirst,
226 kInSecond = 1 << kInsideSecond,
227 kInBoth = 1 << kInsideBoth
228 };
229 SetRelation() : bits_(0) {}
230 ~SetRelation() {}
231 // Add the existence of objects in a particular
232 void SetElementsInFirstSet() { bits_ |= kInFirst; }
233 void SetElementsInSecondSet() { bits_ |= kInSecond; }
234 void SetElementsInBothSets() { bits_ |= kInBoth; }
235 // Check the currently known relation of the sets (common functions only,
236 // for other combinations, use value() to get the bits and check them
237 // manually).
238 // Sets are completely disjoint.
239 bool Disjoint() { return (bits_ & kInBoth) == 0; }
240 // Sets are equal.
241 bool Equals() { return (bits_ & (kInFirst | kInSecond)) == 0; }
242 // First set contains second.
243 bool Contains() { return (bits_ & kInSecond) == 0; }
244 // Second set contains first.
245 bool ContainedIn() { return (bits_ & kInFirst) == 0; }
246 bool NonTrivialIntersection() {
247 return (bits_ == (kInFirst | kInSecond | kInBoth));
248 }
249 int value() { return bits_; }
250 private:
251 int bits_;
252};
253
254
Steve Blocka7e24c12009-10-30 11:49:00 +0000255class CharacterRange {
256 public:
257 CharacterRange() : from_(0), to_(0) { }
258 // For compatibility with the CHECK_OK macro
259 CharacterRange(void* null) { ASSERT_EQ(NULL, null); } //NOLINT
260 CharacterRange(uc16 from, uc16 to) : from_(from), to_(to) { }
261 static void AddClassEscape(uc16 type, ZoneList<CharacterRange>* ranges);
262 static Vector<const uc16> GetWordBounds();
263 static inline CharacterRange Singleton(uc16 value) {
264 return CharacterRange(value, value);
265 }
266 static inline CharacterRange Range(uc16 from, uc16 to) {
267 ASSERT(from <= to);
268 return CharacterRange(from, to);
269 }
270 static inline CharacterRange Everything() {
271 return CharacterRange(0, 0xFFFF);
272 }
273 bool Contains(uc16 i) { return from_ <= i && i <= to_; }
274 uc16 from() const { return from_; }
275 void set_from(uc16 value) { from_ = value; }
276 uc16 to() const { return to_; }
277 void set_to(uc16 value) { to_ = value; }
278 bool is_valid() { return from_ <= to_; }
279 bool IsEverything(uc16 max) { return from_ == 0 && to_ >= max; }
280 bool IsSingleton() { return (from_ == to_); }
Steve Blockd0582a62009-12-15 09:54:21 +0000281 void AddCaseEquivalents(ZoneList<CharacterRange>* ranges, bool is_ascii);
Steve Blocka7e24c12009-10-30 11:49:00 +0000282 static void Split(ZoneList<CharacterRange>* base,
283 Vector<const uc16> overlay,
284 ZoneList<CharacterRange>** included,
285 ZoneList<CharacterRange>** excluded);
Leon Clarkee46be812010-01-19 14:06:41 +0000286 // Whether a range list is in canonical form: Ranges ordered by from value,
287 // and ranges non-overlapping and non-adjacent.
288 static bool IsCanonical(ZoneList<CharacterRange>* ranges);
289 // Convert range list to canonical form. The characters covered by the ranges
290 // will still be the same, but no character is in more than one range, and
291 // adjacent ranges are merged. The resulting list may be shorter than the
292 // original, but cannot be longer.
293 static void Canonicalize(ZoneList<CharacterRange>* ranges);
294 // Check how the set of characters defined by a CharacterRange list relates
295 // to the set of word characters. List must be in canonical form.
296 static SetRelation WordCharacterRelation(ZoneList<CharacterRange>* ranges);
297 // Takes two character range lists (representing character sets) in canonical
298 // form and merges them.
299 // The characters that are only covered by the first set are added to
300 // first_set_only_out. the characters that are only in the second set are
301 // added to second_set_only_out, and the characters that are in both are
302 // added to both_sets_out.
303 // The pointers to first_set_only_out, second_set_only_out and both_sets_out
304 // should be to empty lists, but they need not be distinct, and may be NULL.
305 // If NULL, the characters are dropped, and if two arguments are the same
306 // pointer, the result is the union of the two sets that would be created
307 // if the pointers had been distinct.
308 // This way, the Merge function can compute all the usual set operations:
309 // union (all three out-sets are equal), intersection (only both_sets_out is
310 // non-NULL), and set difference (only first_set is non-NULL).
311 static void Merge(ZoneList<CharacterRange>* first_set,
312 ZoneList<CharacterRange>* second_set,
313 ZoneList<CharacterRange>* first_set_only_out,
314 ZoneList<CharacterRange>* second_set_only_out,
315 ZoneList<CharacterRange>* both_sets_out);
316 // Negate the contents of a character range in canonical form.
317 static void Negate(ZoneList<CharacterRange>* src,
318 ZoneList<CharacterRange>* dst);
Steve Blocka7e24c12009-10-30 11:49:00 +0000319 static const int kStartMarker = (1 << 24);
320 static const int kPayloadMask = (1 << 24) - 1;
321
322 private:
323 uc16 from_;
324 uc16 to_;
325};
326
327
328// A set of unsigned integers that behaves especially well on small
329// integers (< 32). May do zone-allocation.
330class OutSet: public ZoneObject {
331 public:
332 OutSet() : first_(0), remaining_(NULL), successors_(NULL) { }
333 OutSet* Extend(unsigned value);
334 bool Get(unsigned value);
335 static const unsigned kFirstLimit = 32;
336
337 private:
338 // Destructively set a value in this set. In most cases you want
339 // to use Extend instead to ensure that only one instance exists
340 // that contains the same values.
341 void Set(unsigned value);
342
343 // The successors are a list of sets that contain the same values
344 // as this set and the one more value that is not present in this
345 // set.
346 ZoneList<OutSet*>* successors() { return successors_; }
347
348 OutSet(uint32_t first, ZoneList<unsigned>* remaining)
349 : first_(first), remaining_(remaining), successors_(NULL) { }
350 uint32_t first_;
351 ZoneList<unsigned>* remaining_;
352 ZoneList<OutSet*>* successors_;
353 friend class Trace;
354};
355
356
357// A mapping from integers, specified as ranges, to a set of integers.
358// Used for mapping character ranges to choices.
359class DispatchTable : public ZoneObject {
360 public:
361 class Entry {
362 public:
363 Entry() : from_(0), to_(0), out_set_(NULL) { }
364 Entry(uc16 from, uc16 to, OutSet* out_set)
365 : from_(from), to_(to), out_set_(out_set) { }
366 uc16 from() { return from_; }
367 uc16 to() { return to_; }
368 void set_to(uc16 value) { to_ = value; }
369 void AddValue(int value) { out_set_ = out_set_->Extend(value); }
370 OutSet* out_set() { return out_set_; }
371 private:
372 uc16 from_;
373 uc16 to_;
374 OutSet* out_set_;
375 };
376
377 class Config {
378 public:
379 typedef uc16 Key;
380 typedef Entry Value;
381 static const uc16 kNoKey;
382 static const Entry kNoValue;
383 static inline int Compare(uc16 a, uc16 b) {
384 if (a == b)
385 return 0;
386 else if (a < b)
387 return -1;
388 else
389 return 1;
390 }
391 };
392
393 void AddRange(CharacterRange range, int value);
394 OutSet* Get(uc16 value);
395 void Dump();
396
397 template <typename Callback>
398 void ForEach(Callback* callback) { return tree()->ForEach(callback); }
399 private:
400 // There can't be a static empty set since it allocates its
401 // successors in a zone and caches them.
402 OutSet* empty() { return &empty_; }
403 OutSet empty_;
404 ZoneSplayTree<Config>* tree() { return &tree_; }
405 ZoneSplayTree<Config> tree_;
406};
407
408
409#define FOR_EACH_NODE_TYPE(VISIT) \
410 VISIT(End) \
411 VISIT(Action) \
412 VISIT(Choice) \
413 VISIT(BackReference) \
414 VISIT(Assertion) \
415 VISIT(Text)
416
417
418#define FOR_EACH_REG_EXP_TREE_TYPE(VISIT) \
419 VISIT(Disjunction) \
420 VISIT(Alternative) \
421 VISIT(Assertion) \
422 VISIT(CharacterClass) \
423 VISIT(Atom) \
424 VISIT(Quantifier) \
425 VISIT(Capture) \
426 VISIT(Lookahead) \
427 VISIT(BackReference) \
428 VISIT(Empty) \
429 VISIT(Text)
430
431
432#define FORWARD_DECLARE(Name) class RegExp##Name;
433FOR_EACH_REG_EXP_TREE_TYPE(FORWARD_DECLARE)
434#undef FORWARD_DECLARE
435
436
437class TextElement {
438 public:
439 enum Type {UNINITIALIZED, ATOM, CHAR_CLASS};
440 TextElement() : type(UNINITIALIZED) { }
441 explicit TextElement(Type t) : type(t), cp_offset(-1) { }
442 static TextElement Atom(RegExpAtom* atom);
443 static TextElement CharClass(RegExpCharacterClass* char_class);
444 int length();
445 Type type;
446 union {
447 RegExpAtom* u_atom;
448 RegExpCharacterClass* u_char_class;
449 } data;
450 int cp_offset;
451};
452
453
454class Trace;
455
456
457struct NodeInfo {
458 NodeInfo()
459 : being_analyzed(false),
460 been_analyzed(false),
461 follows_word_interest(false),
462 follows_newline_interest(false),
463 follows_start_interest(false),
464 at_end(false),
465 visited(false) { }
466
467 // Returns true if the interests and assumptions of this node
468 // matches the given one.
469 bool Matches(NodeInfo* that) {
470 return (at_end == that->at_end) &&
471 (follows_word_interest == that->follows_word_interest) &&
472 (follows_newline_interest == that->follows_newline_interest) &&
473 (follows_start_interest == that->follows_start_interest);
474 }
475
476 // Updates the interests of this node given the interests of the
477 // node preceding it.
478 void AddFromPreceding(NodeInfo* that) {
479 at_end |= that->at_end;
480 follows_word_interest |= that->follows_word_interest;
481 follows_newline_interest |= that->follows_newline_interest;
482 follows_start_interest |= that->follows_start_interest;
483 }
484
485 bool HasLookbehind() {
486 return follows_word_interest ||
487 follows_newline_interest ||
488 follows_start_interest;
489 }
490
491 // Sets the interests of this node to include the interests of the
492 // following node.
493 void AddFromFollowing(NodeInfo* that) {
494 follows_word_interest |= that->follows_word_interest;
495 follows_newline_interest |= that->follows_newline_interest;
496 follows_start_interest |= that->follows_start_interest;
497 }
498
499 void ResetCompilationState() {
500 being_analyzed = false;
501 been_analyzed = false;
502 }
503
504 bool being_analyzed: 1;
505 bool been_analyzed: 1;
506
507 // These bits are set of this node has to know what the preceding
508 // character was.
509 bool follows_word_interest: 1;
510 bool follows_newline_interest: 1;
511 bool follows_start_interest: 1;
512
513 bool at_end: 1;
514 bool visited: 1;
515};
516
517
518class SiblingList {
519 public:
520 SiblingList() : list_(NULL) { }
521 int length() {
522 return list_ == NULL ? 0 : list_->length();
523 }
524 void Ensure(RegExpNode* parent) {
525 if (list_ == NULL) {
526 list_ = new ZoneList<RegExpNode*>(2);
527 list_->Add(parent);
528 }
529 }
530 void Add(RegExpNode* node) { list_->Add(node); }
531 RegExpNode* Get(int index) { return list_->at(index); }
532 private:
533 ZoneList<RegExpNode*>* list_;
534};
535
536
537// Details of a quick mask-compare check that can look ahead in the
538// input stream.
539class QuickCheckDetails {
540 public:
541 QuickCheckDetails()
542 : characters_(0),
543 mask_(0),
544 value_(0),
545 cannot_match_(false) { }
546 explicit QuickCheckDetails(int characters)
547 : characters_(characters),
548 mask_(0),
549 value_(0),
550 cannot_match_(false) { }
551 bool Rationalize(bool ascii);
552 // Merge in the information from another branch of an alternation.
553 void Merge(QuickCheckDetails* other, int from_index);
554 // Advance the current position by some amount.
555 void Advance(int by, bool ascii);
556 void Clear();
557 bool cannot_match() { return cannot_match_; }
558 void set_cannot_match() { cannot_match_ = true; }
559 struct Position {
560 Position() : mask(0), value(0), determines_perfectly(false) { }
561 uc16 mask;
562 uc16 value;
563 bool determines_perfectly;
564 };
565 int characters() { return characters_; }
566 void set_characters(int characters) { characters_ = characters; }
567 Position* positions(int index) {
568 ASSERT(index >= 0);
569 ASSERT(index < characters_);
570 return positions_ + index;
571 }
572 uint32_t mask() { return mask_; }
573 uint32_t value() { return value_; }
574
575 private:
576 // How many characters do we have quick check information from. This is
577 // the same for all branches of a choice node.
578 int characters_;
579 Position positions_[4];
580 // These values are the condensate of the above array after Rationalize().
581 uint32_t mask_;
582 uint32_t value_;
583 // If set to true, there is no way this quick check can match at all.
584 // E.g., if it requires to be at the start of the input, and isn't.
585 bool cannot_match_;
586};
587
588
589class RegExpNode: public ZoneObject {
590 public:
Leon Clarkee46be812010-01-19 14:06:41 +0000591 RegExpNode() : first_character_set_(NULL), trace_count_(0) { }
Steve Blocka7e24c12009-10-30 11:49:00 +0000592 virtual ~RegExpNode();
593 virtual void Accept(NodeVisitor* visitor) = 0;
594 // Generates a goto to this node or actually generates the code at this point.
595 virtual void Emit(RegExpCompiler* compiler, Trace* trace) = 0;
596 // How many characters must this node consume at a minimum in order to
597 // succeed. If we have found at least 'still_to_find' characters that
598 // must be consumed there is no need to ask any following nodes whether
Ben Murdochb0fe1622011-05-05 13:52:32 +0100599 // they are sure to eat any more characters. The not_at_start argument is
600 // used to indicate that we know we are not at the start of the input. In
601 // this case anchored branches will always fail and can be ignored when
602 // determining how many characters are consumed on success.
603 virtual int EatsAtLeast(int still_to_find,
604 int recursion_depth,
605 bool not_at_start) = 0;
Steve Blocka7e24c12009-10-30 11:49:00 +0000606 // Emits some quick code that checks whether the preloaded characters match.
607 // Falls through on certain failure, jumps to the label on possible success.
608 // If the node cannot make a quick check it does nothing and returns false.
609 bool EmitQuickCheck(RegExpCompiler* compiler,
610 Trace* trace,
611 bool preload_has_checked_bounds,
612 Label* on_possible_success,
613 QuickCheckDetails* details_return,
614 bool fall_through_on_failure);
615 // For a given number of characters this returns a mask and a value. The
616 // next n characters are anded with the mask and compared with the value.
617 // A comparison failure indicates the node cannot match the next n characters.
618 // A comparison success indicates the node may match.
619 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
620 RegExpCompiler* compiler,
621 int characters_filled_in,
622 bool not_at_start) = 0;
623 static const int kNodeIsTooComplexForGreedyLoops = -1;
624 virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; }
625 Label* label() { return &label_; }
626 // If non-generic code is generated for a node (ie the node is not at the
627 // start of the trace) then it cannot be reused. This variable sets a limit
628 // on how often we allow that to happen before we insist on starting a new
629 // trace and generating generic code for a node that can be reused by flushing
630 // the deferred actions in the current trace and generating a goto.
631 static const int kMaxCopiesCodeGenerated = 10;
632
633 NodeInfo* info() { return &info_; }
634
635 void AddSibling(RegExpNode* node) { siblings_.Add(node); }
636
637 // Static version of EnsureSibling that expresses the fact that the
638 // result has the same type as the input.
639 template <class C>
640 static C* EnsureSibling(C* node, NodeInfo* info, bool* cloned) {
641 return static_cast<C*>(node->EnsureSibling(info, cloned));
642 }
643
644 SiblingList* siblings() { return &siblings_; }
645 void set_siblings(SiblingList* other) { siblings_ = *other; }
646
Leon Clarkee46be812010-01-19 14:06:41 +0000647 // Return the set of possible next characters recognized by the regexp
648 // (or a safe subset, potentially the set of all characters).
649 ZoneList<CharacterRange>* FirstCharacterSet();
650
651 // Compute (if possible within the budget of traversed nodes) the
652 // possible first characters of the input matched by this node and
653 // its continuation. Returns the remaining budget after the computation.
654 // If the budget is spent, the result is negative, and the cached
655 // first_character_set_ value isn't set.
656 virtual int ComputeFirstCharacterSet(int budget);
657
658 // Get and set the cached first character set value.
659 ZoneList<CharacterRange>* first_character_set() {
660 return first_character_set_;
661 }
662 void set_first_character_set(ZoneList<CharacterRange>* character_set) {
663 first_character_set_ = character_set;
664 }
665
Steve Blocka7e24c12009-10-30 11:49:00 +0000666 protected:
667 enum LimitResult { DONE, CONTINUE };
Leon Clarkee46be812010-01-19 14:06:41 +0000668 static const int kComputeFirstCharacterSetFail = -1;
669
Steve Blocka7e24c12009-10-30 11:49:00 +0000670 LimitResult LimitVersions(RegExpCompiler* compiler, Trace* trace);
671
672 // Returns a sibling of this node whose interests and assumptions
673 // match the ones in the given node info. If no sibling exists NULL
674 // is returned.
675 RegExpNode* TryGetSibling(NodeInfo* info);
676
677 // Returns a sibling of this node whose interests match the ones in
678 // the given node info. The info must not contain any assertions.
679 // If no node exists a new one will be created by cloning the current
680 // node. The result will always be an instance of the same concrete
681 // class as this node.
682 RegExpNode* EnsureSibling(NodeInfo* info, bool* cloned);
683
684 // Returns a clone of this node initialized using the copy constructor
685 // of its concrete class. Note that the node may have to be pre-
686 // processed before it is on a usable state.
687 virtual RegExpNode* Clone() = 0;
688
689 private:
Leon Clarkee46be812010-01-19 14:06:41 +0000690 static const int kFirstCharBudget = 10;
Steve Blocka7e24c12009-10-30 11:49:00 +0000691 Label label_;
692 NodeInfo info_;
693 SiblingList siblings_;
Leon Clarkee46be812010-01-19 14:06:41 +0000694 ZoneList<CharacterRange>* first_character_set_;
Steve Blocka7e24c12009-10-30 11:49:00 +0000695 // This variable keeps track of how many times code has been generated for
696 // this node (in different traces). We don't keep track of where the
697 // generated code is located unless the code is generated at the start of
698 // a trace, in which case it is generic and can be reused by flushing the
699 // deferred operations in the current trace and generating a goto.
700 int trace_count_;
701};
702
703
704// A simple closed interval.
705class Interval {
706 public:
707 Interval() : from_(kNone), to_(kNone) { }
708 Interval(int from, int to) : from_(from), to_(to) { }
709 Interval Union(Interval that) {
710 if (that.from_ == kNone)
711 return *this;
712 else if (from_ == kNone)
713 return that;
714 else
715 return Interval(Min(from_, that.from_), Max(to_, that.to_));
716 }
717 bool Contains(int value) {
718 return (from_ <= value) && (value <= to_);
719 }
720 bool is_empty() { return from_ == kNone; }
721 int from() { return from_; }
722 int to() { return to_; }
723 static Interval Empty() { return Interval(); }
724 static const int kNone = -1;
725 private:
726 int from_;
727 int to_;
728};
729
730
731class SeqRegExpNode: public RegExpNode {
732 public:
733 explicit SeqRegExpNode(RegExpNode* on_success)
734 : on_success_(on_success) { }
735 RegExpNode* on_success() { return on_success_; }
736 void set_on_success(RegExpNode* node) { on_success_ = node; }
737 private:
738 RegExpNode* on_success_;
739};
740
741
742class ActionNode: public SeqRegExpNode {
743 public:
744 enum Type {
745 SET_REGISTER,
746 INCREMENT_REGISTER,
747 STORE_POSITION,
748 BEGIN_SUBMATCH,
749 POSITIVE_SUBMATCH_SUCCESS,
750 EMPTY_MATCH_CHECK,
751 CLEAR_CAPTURES
752 };
753 static ActionNode* SetRegister(int reg, int val, RegExpNode* on_success);
754 static ActionNode* IncrementRegister(int reg, RegExpNode* on_success);
755 static ActionNode* StorePosition(int reg,
756 bool is_capture,
757 RegExpNode* on_success);
758 static ActionNode* ClearCaptures(Interval range, RegExpNode* on_success);
759 static ActionNode* BeginSubmatch(int stack_pointer_reg,
760 int position_reg,
761 RegExpNode* on_success);
762 static ActionNode* PositiveSubmatchSuccess(int stack_pointer_reg,
763 int restore_reg,
764 int clear_capture_count,
765 int clear_capture_from,
766 RegExpNode* on_success);
767 static ActionNode* EmptyMatchCheck(int start_register,
768 int repetition_register,
769 int repetition_limit,
770 RegExpNode* on_success);
771 virtual void Accept(NodeVisitor* visitor);
772 virtual void Emit(RegExpCompiler* compiler, Trace* trace);
Ben Murdochb0fe1622011-05-05 13:52:32 +0100773 virtual int EatsAtLeast(int still_to_find,
774 int recursion_depth,
775 bool not_at_start);
Steve Blocka7e24c12009-10-30 11:49:00 +0000776 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
777 RegExpCompiler* compiler,
778 int filled_in,
779 bool not_at_start) {
780 return on_success()->GetQuickCheckDetails(
781 details, compiler, filled_in, not_at_start);
782 }
783 Type type() { return type_; }
784 // TODO(erikcorry): We should allow some action nodes in greedy loops.
785 virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; }
786 virtual ActionNode* Clone() { return new ActionNode(*this); }
Leon Clarkee46be812010-01-19 14:06:41 +0000787 virtual int ComputeFirstCharacterSet(int budget);
Steve Blocka7e24c12009-10-30 11:49:00 +0000788 private:
789 union {
790 struct {
791 int reg;
792 int value;
793 } u_store_register;
794 struct {
795 int reg;
796 } u_increment_register;
797 struct {
798 int reg;
799 bool is_capture;
800 } u_position_register;
801 struct {
802 int stack_pointer_register;
803 int current_position_register;
804 int clear_register_count;
805 int clear_register_from;
806 } u_submatch;
807 struct {
808 int start_register;
809 int repetition_register;
810 int repetition_limit;
811 } u_empty_match_check;
812 struct {
813 int range_from;
814 int range_to;
815 } u_clear_captures;
816 } data_;
817 ActionNode(Type type, RegExpNode* on_success)
818 : SeqRegExpNode(on_success),
819 type_(type) { }
820 Type type_;
821 friend class DotPrinter;
822};
823
824
825class TextNode: public SeqRegExpNode {
826 public:
827 TextNode(ZoneList<TextElement>* elms,
828 RegExpNode* on_success)
829 : SeqRegExpNode(on_success),
830 elms_(elms) { }
831 TextNode(RegExpCharacterClass* that,
832 RegExpNode* on_success)
833 : SeqRegExpNode(on_success),
834 elms_(new ZoneList<TextElement>(1)) {
835 elms_->Add(TextElement::CharClass(that));
836 }
837 virtual void Accept(NodeVisitor* visitor);
838 virtual void Emit(RegExpCompiler* compiler, Trace* trace);
Ben Murdochb0fe1622011-05-05 13:52:32 +0100839 virtual int EatsAtLeast(int still_to_find,
840 int recursion_depth,
841 bool not_at_start);
Steve Blocka7e24c12009-10-30 11:49:00 +0000842 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
843 RegExpCompiler* compiler,
844 int characters_filled_in,
845 bool not_at_start);
846 ZoneList<TextElement>* elements() { return elms_; }
Steve Blockd0582a62009-12-15 09:54:21 +0000847 void MakeCaseIndependent(bool is_ascii);
Steve Blocka7e24c12009-10-30 11:49:00 +0000848 virtual int GreedyLoopTextLength();
849 virtual TextNode* Clone() {
850 TextNode* result = new TextNode(*this);
851 result->CalculateOffsets();
852 return result;
853 }
854 void CalculateOffsets();
Leon Clarkee46be812010-01-19 14:06:41 +0000855 virtual int ComputeFirstCharacterSet(int budget);
Steve Blocka7e24c12009-10-30 11:49:00 +0000856 private:
857 enum TextEmitPassType {
858 NON_ASCII_MATCH, // Check for characters that can't match.
859 SIMPLE_CHARACTER_MATCH, // Case-dependent single character check.
860 NON_LETTER_CHARACTER_MATCH, // Check characters that have no case equivs.
861 CASE_CHARACTER_MATCH, // Case-independent single character check.
862 CHARACTER_CLASS_MATCH // Character class.
863 };
864 static bool SkipPass(int pass, bool ignore_case);
865 static const int kFirstRealPass = SIMPLE_CHARACTER_MATCH;
866 static const int kLastPass = CHARACTER_CLASS_MATCH;
867 void TextEmitPass(RegExpCompiler* compiler,
868 TextEmitPassType pass,
869 bool preloaded,
870 Trace* trace,
871 bool first_element_checked,
872 int* checked_up_to);
873 int Length();
874 ZoneList<TextElement>* elms_;
875};
876
877
878class AssertionNode: public SeqRegExpNode {
879 public:
880 enum AssertionNodeType {
881 AT_END,
882 AT_START,
883 AT_BOUNDARY,
884 AT_NON_BOUNDARY,
Leon Clarkee46be812010-01-19 14:06:41 +0000885 AFTER_NEWLINE,
886 // Types not directly expressible in regexp syntax.
887 // Used for modifying a boundary node if its following character is
888 // known to be word and/or non-word.
889 AFTER_NONWORD_CHARACTER,
890 AFTER_WORD_CHARACTER
Steve Blocka7e24c12009-10-30 11:49:00 +0000891 };
892 static AssertionNode* AtEnd(RegExpNode* on_success) {
893 return new AssertionNode(AT_END, on_success);
894 }
895 static AssertionNode* AtStart(RegExpNode* on_success) {
896 return new AssertionNode(AT_START, on_success);
897 }
898 static AssertionNode* AtBoundary(RegExpNode* on_success) {
899 return new AssertionNode(AT_BOUNDARY, on_success);
900 }
901 static AssertionNode* AtNonBoundary(RegExpNode* on_success) {
902 return new AssertionNode(AT_NON_BOUNDARY, on_success);
903 }
904 static AssertionNode* AfterNewline(RegExpNode* on_success) {
905 return new AssertionNode(AFTER_NEWLINE, on_success);
906 }
907 virtual void Accept(NodeVisitor* visitor);
908 virtual void Emit(RegExpCompiler* compiler, Trace* trace);
Ben Murdochb0fe1622011-05-05 13:52:32 +0100909 virtual int EatsAtLeast(int still_to_find,
910 int recursion_depth,
911 bool not_at_start);
Steve Blocka7e24c12009-10-30 11:49:00 +0000912 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
913 RegExpCompiler* compiler,
914 int filled_in,
915 bool not_at_start);
Leon Clarkee46be812010-01-19 14:06:41 +0000916 virtual int ComputeFirstCharacterSet(int budget);
Steve Blocka7e24c12009-10-30 11:49:00 +0000917 virtual AssertionNode* Clone() { return new AssertionNode(*this); }
918 AssertionNodeType type() { return type_; }
Leon Clarkee46be812010-01-19 14:06:41 +0000919 void set_type(AssertionNodeType type) { type_ = type; }
Steve Blocka7e24c12009-10-30 11:49:00 +0000920 private:
921 AssertionNode(AssertionNodeType t, RegExpNode* on_success)
922 : SeqRegExpNode(on_success), type_(t) { }
923 AssertionNodeType type_;
924};
925
926
927class BackReferenceNode: public SeqRegExpNode {
928 public:
929 BackReferenceNode(int start_reg,
930 int end_reg,
931 RegExpNode* on_success)
932 : SeqRegExpNode(on_success),
933 start_reg_(start_reg),
934 end_reg_(end_reg) { }
935 virtual void Accept(NodeVisitor* visitor);
936 int start_register() { return start_reg_; }
937 int end_register() { return end_reg_; }
938 virtual void Emit(RegExpCompiler* compiler, Trace* trace);
Ben Murdochb0fe1622011-05-05 13:52:32 +0100939 virtual int EatsAtLeast(int still_to_find,
940 int recursion_depth,
941 bool not_at_start);
Steve Blocka7e24c12009-10-30 11:49:00 +0000942 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
943 RegExpCompiler* compiler,
944 int characters_filled_in,
945 bool not_at_start) {
946 return;
947 }
948 virtual BackReferenceNode* Clone() { return new BackReferenceNode(*this); }
Leon Clarkee46be812010-01-19 14:06:41 +0000949 virtual int ComputeFirstCharacterSet(int budget);
Steve Blocka7e24c12009-10-30 11:49:00 +0000950 private:
951 int start_reg_;
952 int end_reg_;
953};
954
955
956class EndNode: public RegExpNode {
957 public:
958 enum Action { ACCEPT, BACKTRACK, NEGATIVE_SUBMATCH_SUCCESS };
959 explicit EndNode(Action action) : action_(action) { }
960 virtual void Accept(NodeVisitor* visitor);
961 virtual void Emit(RegExpCompiler* compiler, Trace* trace);
Ben Murdochb0fe1622011-05-05 13:52:32 +0100962 virtual int EatsAtLeast(int still_to_find,
963 int recursion_depth,
964 bool not_at_start) { return 0; }
Steve Blocka7e24c12009-10-30 11:49:00 +0000965 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
966 RegExpCompiler* compiler,
967 int characters_filled_in,
968 bool not_at_start) {
969 // Returning 0 from EatsAtLeast should ensure we never get here.
970 UNREACHABLE();
971 }
972 virtual EndNode* Clone() { return new EndNode(*this); }
Steve Blocka7e24c12009-10-30 11:49:00 +0000973 private:
974 Action action_;
975};
976
977
978class NegativeSubmatchSuccess: public EndNode {
979 public:
980 NegativeSubmatchSuccess(int stack_pointer_reg,
981 int position_reg,
982 int clear_capture_count,
983 int clear_capture_start)
984 : EndNode(NEGATIVE_SUBMATCH_SUCCESS),
985 stack_pointer_register_(stack_pointer_reg),
986 current_position_register_(position_reg),
987 clear_capture_count_(clear_capture_count),
988 clear_capture_start_(clear_capture_start) { }
989 virtual void Emit(RegExpCompiler* compiler, Trace* trace);
990
991 private:
992 int stack_pointer_register_;
993 int current_position_register_;
994 int clear_capture_count_;
995 int clear_capture_start_;
996};
997
998
999class Guard: public ZoneObject {
1000 public:
1001 enum Relation { LT, GEQ };
1002 Guard(int reg, Relation op, int value)
1003 : reg_(reg),
1004 op_(op),
1005 value_(value) { }
1006 int reg() { return reg_; }
1007 Relation op() { return op_; }
1008 int value() { return value_; }
1009
1010 private:
1011 int reg_;
1012 Relation op_;
1013 int value_;
1014};
1015
1016
1017class GuardedAlternative {
1018 public:
1019 explicit GuardedAlternative(RegExpNode* node) : node_(node), guards_(NULL) { }
1020 void AddGuard(Guard* guard);
1021 RegExpNode* node() { return node_; }
1022 void set_node(RegExpNode* node) { node_ = node; }
1023 ZoneList<Guard*>* guards() { return guards_; }
1024
1025 private:
1026 RegExpNode* node_;
1027 ZoneList<Guard*>* guards_;
1028};
1029
1030
1031class AlternativeGeneration;
1032
1033
1034class ChoiceNode: public RegExpNode {
1035 public:
1036 explicit ChoiceNode(int expected_size)
1037 : alternatives_(new ZoneList<GuardedAlternative>(expected_size)),
1038 table_(NULL),
1039 not_at_start_(false),
1040 being_calculated_(false) { }
1041 virtual void Accept(NodeVisitor* visitor);
1042 void AddAlternative(GuardedAlternative node) { alternatives()->Add(node); }
1043 ZoneList<GuardedAlternative>* alternatives() { return alternatives_; }
1044 DispatchTable* GetTable(bool ignore_case);
1045 virtual void Emit(RegExpCompiler* compiler, Trace* trace);
Ben Murdochb0fe1622011-05-05 13:52:32 +01001046 virtual int EatsAtLeast(int still_to_find,
1047 int recursion_depth,
1048 bool not_at_start);
Steve Blocka7e24c12009-10-30 11:49:00 +00001049 int EatsAtLeastHelper(int still_to_find,
1050 int recursion_depth,
Ben Murdochb0fe1622011-05-05 13:52:32 +01001051 RegExpNode* ignore_this_node,
1052 bool not_at_start);
Steve Blocka7e24c12009-10-30 11:49:00 +00001053 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
1054 RegExpCompiler* compiler,
1055 int characters_filled_in,
1056 bool not_at_start);
1057 virtual ChoiceNode* Clone() { return new ChoiceNode(*this); }
1058
1059 bool being_calculated() { return being_calculated_; }
1060 bool not_at_start() { return not_at_start_; }
1061 void set_not_at_start() { not_at_start_ = true; }
1062 void set_being_calculated(bool b) { being_calculated_ = b; }
1063 virtual bool try_to_emit_quick_check_for_alternative(int i) { return true; }
1064
1065 protected:
1066 int GreedyLoopTextLength(GuardedAlternative* alternative);
1067 ZoneList<GuardedAlternative>* alternatives_;
1068
1069 private:
1070 friend class DispatchTableConstructor;
1071 friend class Analysis;
1072 void GenerateGuard(RegExpMacroAssembler* macro_assembler,
1073 Guard* guard,
1074 Trace* trace);
Ben Murdochb0fe1622011-05-05 13:52:32 +01001075 int CalculatePreloadCharacters(RegExpCompiler* compiler, bool not_at_start);
Steve Blocka7e24c12009-10-30 11:49:00 +00001076 void EmitOutOfLineContinuation(RegExpCompiler* compiler,
1077 Trace* trace,
1078 GuardedAlternative alternative,
1079 AlternativeGeneration* alt_gen,
1080 int preload_characters,
1081 bool next_expects_preload);
1082 DispatchTable* table_;
1083 // If true, this node is never checked at the start of the input.
1084 // Allows a new trace to start with at_start() set to false.
1085 bool not_at_start_;
1086 bool being_calculated_;
1087};
1088
1089
1090class NegativeLookaheadChoiceNode: public ChoiceNode {
1091 public:
1092 explicit NegativeLookaheadChoiceNode(GuardedAlternative this_must_fail,
1093 GuardedAlternative then_do_this)
1094 : ChoiceNode(2) {
1095 AddAlternative(this_must_fail);
1096 AddAlternative(then_do_this);
1097 }
Ben Murdochb0fe1622011-05-05 13:52:32 +01001098 virtual int EatsAtLeast(int still_to_find,
1099 int recursion_depth,
1100 bool not_at_start);
Steve Blocka7e24c12009-10-30 11:49:00 +00001101 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
1102 RegExpCompiler* compiler,
1103 int characters_filled_in,
1104 bool not_at_start);
1105 // For a negative lookahead we don't emit the quick check for the
1106 // alternative that is expected to fail. This is because quick check code
1107 // starts by loading enough characters for the alternative that takes fewest
1108 // characters, but on a negative lookahead the negative branch did not take
1109 // part in that calculation (EatsAtLeast) so the assumptions don't hold.
1110 virtual bool try_to_emit_quick_check_for_alternative(int i) { return i != 0; }
Leon Clarkee46be812010-01-19 14:06:41 +00001111 virtual int ComputeFirstCharacterSet(int budget);
Steve Blocka7e24c12009-10-30 11:49:00 +00001112};
1113
1114
1115class LoopChoiceNode: public ChoiceNode {
1116 public:
1117 explicit LoopChoiceNode(bool body_can_be_zero_length)
1118 : ChoiceNode(2),
1119 loop_node_(NULL),
1120 continue_node_(NULL),
1121 body_can_be_zero_length_(body_can_be_zero_length) { }
1122 void AddLoopAlternative(GuardedAlternative alt);
1123 void AddContinueAlternative(GuardedAlternative alt);
1124 virtual void Emit(RegExpCompiler* compiler, Trace* trace);
Ben Murdochb0fe1622011-05-05 13:52:32 +01001125 virtual int EatsAtLeast(int still_to_find,
1126 int recursion_depth,
1127 bool not_at_start);
Steve Blocka7e24c12009-10-30 11:49:00 +00001128 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
1129 RegExpCompiler* compiler,
1130 int characters_filled_in,
1131 bool not_at_start);
Leon Clarkee46be812010-01-19 14:06:41 +00001132 virtual int ComputeFirstCharacterSet(int budget);
Steve Blocka7e24c12009-10-30 11:49:00 +00001133 virtual LoopChoiceNode* Clone() { return new LoopChoiceNode(*this); }
1134 RegExpNode* loop_node() { return loop_node_; }
1135 RegExpNode* continue_node() { return continue_node_; }
1136 bool body_can_be_zero_length() { return body_can_be_zero_length_; }
1137 virtual void Accept(NodeVisitor* visitor);
1138
1139 private:
1140 // AddAlternative is made private for loop nodes because alternatives
1141 // should not be added freely, we need to keep track of which node
1142 // goes back to the node itself.
1143 void AddAlternative(GuardedAlternative node) {
1144 ChoiceNode::AddAlternative(node);
1145 }
1146
1147 RegExpNode* loop_node_;
1148 RegExpNode* continue_node_;
1149 bool body_can_be_zero_length_;
1150};
1151
1152
1153// There are many ways to generate code for a node. This class encapsulates
1154// the current way we should be generating. In other words it encapsulates
1155// the current state of the code generator. The effect of this is that we
1156// generate code for paths that the matcher can take through the regular
1157// expression. A given node in the regexp can be code-generated several times
1158// as it can be part of several traces. For example for the regexp:
1159// /foo(bar|ip)baz/ the code to match baz will be generated twice, once as part
1160// of the foo-bar-baz trace and once as part of the foo-ip-baz trace. The code
1161// to match foo is generated only once (the traces have a common prefix). The
1162// code to store the capture is deferred and generated (twice) after the places
1163// where baz has been matched.
1164class Trace {
1165 public:
1166 // A value for a property that is either known to be true, know to be false,
1167 // or not known.
1168 enum TriBool {
1169 UNKNOWN = -1, FALSE = 0, TRUE = 1
1170 };
1171
1172 class DeferredAction {
1173 public:
1174 DeferredAction(ActionNode::Type type, int reg)
1175 : type_(type), reg_(reg), next_(NULL) { }
1176 DeferredAction* next() { return next_; }
1177 bool Mentions(int reg);
1178 int reg() { return reg_; }
1179 ActionNode::Type type() { return type_; }
1180 private:
1181 ActionNode::Type type_;
1182 int reg_;
1183 DeferredAction* next_;
1184 friend class Trace;
1185 };
1186
1187 class DeferredCapture : public DeferredAction {
1188 public:
1189 DeferredCapture(int reg, bool is_capture, Trace* trace)
1190 : DeferredAction(ActionNode::STORE_POSITION, reg),
1191 cp_offset_(trace->cp_offset()),
1192 is_capture_(is_capture) { }
1193 int cp_offset() { return cp_offset_; }
1194 bool is_capture() { return is_capture_; }
1195 private:
1196 int cp_offset_;
1197 bool is_capture_;
1198 void set_cp_offset(int cp_offset) { cp_offset_ = cp_offset; }
1199 };
1200
1201 class DeferredSetRegister : public DeferredAction {
1202 public:
1203 DeferredSetRegister(int reg, int value)
1204 : DeferredAction(ActionNode::SET_REGISTER, reg),
1205 value_(value) { }
1206 int value() { return value_; }
1207 private:
1208 int value_;
1209 };
1210
1211 class DeferredClearCaptures : public DeferredAction {
1212 public:
1213 explicit DeferredClearCaptures(Interval range)
1214 : DeferredAction(ActionNode::CLEAR_CAPTURES, -1),
1215 range_(range) { }
1216 Interval range() { return range_; }
1217 private:
1218 Interval range_;
1219 };
1220
1221 class DeferredIncrementRegister : public DeferredAction {
1222 public:
1223 explicit DeferredIncrementRegister(int reg)
1224 : DeferredAction(ActionNode::INCREMENT_REGISTER, reg) { }
1225 };
1226
1227 Trace()
1228 : cp_offset_(0),
1229 actions_(NULL),
1230 backtrack_(NULL),
1231 stop_node_(NULL),
1232 loop_label_(NULL),
1233 characters_preloaded_(0),
1234 bound_checked_up_to_(0),
1235 flush_budget_(100),
1236 at_start_(UNKNOWN) { }
1237
1238 // End the trace. This involves flushing the deferred actions in the trace
1239 // and pushing a backtrack location onto the backtrack stack. Once this is
1240 // done we can start a new trace or go to one that has already been
1241 // generated.
1242 void Flush(RegExpCompiler* compiler, RegExpNode* successor);
1243 int cp_offset() { return cp_offset_; }
1244 DeferredAction* actions() { return actions_; }
1245 // A trivial trace is one that has no deferred actions or other state that
1246 // affects the assumptions used when generating code. There is no recorded
1247 // backtrack location in a trivial trace, so with a trivial trace we will
1248 // generate code that, on a failure to match, gets the backtrack location
1249 // from the backtrack stack rather than using a direct jump instruction. We
1250 // always start code generation with a trivial trace and non-trivial traces
1251 // are created as we emit code for nodes or add to the list of deferred
1252 // actions in the trace. The location of the code generated for a node using
1253 // a trivial trace is recorded in a label in the node so that gotos can be
1254 // generated to that code.
1255 bool is_trivial() {
1256 return backtrack_ == NULL &&
1257 actions_ == NULL &&
1258 cp_offset_ == 0 &&
1259 characters_preloaded_ == 0 &&
1260 bound_checked_up_to_ == 0 &&
1261 quick_check_performed_.characters() == 0 &&
1262 at_start_ == UNKNOWN;
1263 }
1264 TriBool at_start() { return at_start_; }
1265 void set_at_start(bool at_start) { at_start_ = at_start ? TRUE : FALSE; }
1266 Label* backtrack() { return backtrack_; }
1267 Label* loop_label() { return loop_label_; }
1268 RegExpNode* stop_node() { return stop_node_; }
1269 int characters_preloaded() { return characters_preloaded_; }
1270 int bound_checked_up_to() { return bound_checked_up_to_; }
1271 int flush_budget() { return flush_budget_; }
1272 QuickCheckDetails* quick_check_performed() { return &quick_check_performed_; }
1273 bool mentions_reg(int reg);
1274 // Returns true if a deferred position store exists to the specified
1275 // register and stores the offset in the out-parameter. Otherwise
1276 // returns false.
1277 bool GetStoredPosition(int reg, int* cp_offset);
1278 // These set methods and AdvanceCurrentPositionInTrace should be used only on
1279 // new traces - the intention is that traces are immutable after creation.
1280 void add_action(DeferredAction* new_action) {
1281 ASSERT(new_action->next_ == NULL);
1282 new_action->next_ = actions_;
1283 actions_ = new_action;
1284 }
1285 void set_backtrack(Label* backtrack) { backtrack_ = backtrack; }
1286 void set_stop_node(RegExpNode* node) { stop_node_ = node; }
1287 void set_loop_label(Label* label) { loop_label_ = label; }
Leon Clarkee46be812010-01-19 14:06:41 +00001288 void set_characters_preloaded(int count) { characters_preloaded_ = count; }
Steve Blocka7e24c12009-10-30 11:49:00 +00001289 void set_bound_checked_up_to(int to) { bound_checked_up_to_ = to; }
1290 void set_flush_budget(int to) { flush_budget_ = to; }
1291 void set_quick_check_performed(QuickCheckDetails* d) {
1292 quick_check_performed_ = *d;
1293 }
1294 void InvalidateCurrentCharacter();
1295 void AdvanceCurrentPositionInTrace(int by, RegExpCompiler* compiler);
1296 private:
1297 int FindAffectedRegisters(OutSet* affected_registers);
1298 void PerformDeferredActions(RegExpMacroAssembler* macro,
1299 int max_register,
1300 OutSet& affected_registers,
1301 OutSet* registers_to_pop,
1302 OutSet* registers_to_clear);
1303 void RestoreAffectedRegisters(RegExpMacroAssembler* macro,
1304 int max_register,
1305 OutSet& registers_to_pop,
1306 OutSet& registers_to_clear);
1307 int cp_offset_;
1308 DeferredAction* actions_;
1309 Label* backtrack_;
1310 RegExpNode* stop_node_;
1311 Label* loop_label_;
1312 int characters_preloaded_;
1313 int bound_checked_up_to_;
1314 QuickCheckDetails quick_check_performed_;
1315 int flush_budget_;
1316 TriBool at_start_;
1317};
1318
1319
1320class NodeVisitor {
1321 public:
1322 virtual ~NodeVisitor() { }
1323#define DECLARE_VISIT(Type) \
1324 virtual void Visit##Type(Type##Node* that) = 0;
1325FOR_EACH_NODE_TYPE(DECLARE_VISIT)
1326#undef DECLARE_VISIT
1327 virtual void VisitLoopChoice(LoopChoiceNode* that) { VisitChoice(that); }
1328};
1329
1330
1331// Node visitor used to add the start set of the alternatives to the
1332// dispatch table of a choice node.
1333class DispatchTableConstructor: public NodeVisitor {
1334 public:
1335 DispatchTableConstructor(DispatchTable* table, bool ignore_case)
1336 : table_(table),
1337 choice_index_(-1),
1338 ignore_case_(ignore_case) { }
1339
1340 void BuildTable(ChoiceNode* node);
1341
1342 void AddRange(CharacterRange range) {
1343 table()->AddRange(range, choice_index_);
1344 }
1345
1346 void AddInverse(ZoneList<CharacterRange>* ranges);
1347
1348#define DECLARE_VISIT(Type) \
1349 virtual void Visit##Type(Type##Node* that);
1350FOR_EACH_NODE_TYPE(DECLARE_VISIT)
1351#undef DECLARE_VISIT
1352
1353 DispatchTable* table() { return table_; }
1354 void set_choice_index(int value) { choice_index_ = value; }
1355
1356 protected:
1357 DispatchTable* table_;
1358 int choice_index_;
1359 bool ignore_case_;
1360};
1361
1362
1363// Assertion propagation moves information about assertions such as
1364// \b to the affected nodes. For instance, in /.\b./ information must
1365// be propagated to the first '.' that whatever follows needs to know
1366// if it matched a word or a non-word, and to the second '.' that it
1367// has to check if it succeeds a word or non-word. In this case the
1368// result will be something like:
1369//
1370// +-------+ +------------+
1371// | . | | . |
1372// +-------+ ---> +------------+
1373// | word? | | check word |
1374// +-------+ +------------+
1375class Analysis: public NodeVisitor {
1376 public:
Steve Blockd0582a62009-12-15 09:54:21 +00001377 Analysis(bool ignore_case, bool is_ascii)
1378 : ignore_case_(ignore_case),
1379 is_ascii_(is_ascii),
1380 error_message_(NULL) { }
Steve Blocka7e24c12009-10-30 11:49:00 +00001381 void EnsureAnalyzed(RegExpNode* node);
1382
1383#define DECLARE_VISIT(Type) \
1384 virtual void Visit##Type(Type##Node* that);
1385FOR_EACH_NODE_TYPE(DECLARE_VISIT)
1386#undef DECLARE_VISIT
1387 virtual void VisitLoopChoice(LoopChoiceNode* that);
1388
1389 bool has_failed() { return error_message_ != NULL; }
1390 const char* error_message() {
1391 ASSERT(error_message_ != NULL);
1392 return error_message_;
1393 }
1394 void fail(const char* error_message) {
1395 error_message_ = error_message;
1396 }
1397 private:
1398 bool ignore_case_;
Steve Blockd0582a62009-12-15 09:54:21 +00001399 bool is_ascii_;
Steve Blocka7e24c12009-10-30 11:49:00 +00001400 const char* error_message_;
1401
1402 DISALLOW_IMPLICIT_CONSTRUCTORS(Analysis);
1403};
1404
1405
1406struct RegExpCompileData {
1407 RegExpCompileData()
1408 : tree(NULL),
1409 node(NULL),
1410 simple(true),
1411 contains_anchor(false),
1412 capture_count(0) { }
1413 RegExpTree* tree;
1414 RegExpNode* node;
1415 bool simple;
1416 bool contains_anchor;
1417 Handle<String> error;
1418 int capture_count;
1419};
1420
1421
1422class RegExpEngine: public AllStatic {
1423 public:
1424 struct CompilationResult {
1425 explicit CompilationResult(const char* error_message)
1426 : error_message(error_message),
Steve Block44f0eee2011-05-26 01:26:41 +01001427 code(HEAP->the_hole_value()),
Steve Blocka7e24c12009-10-30 11:49:00 +00001428 num_registers(0) {}
1429 CompilationResult(Object* code, int registers)
1430 : error_message(NULL),
1431 code(code),
1432 num_registers(registers) {}
1433 const char* error_message;
1434 Object* code;
1435 int num_registers;
1436 };
1437
1438 static CompilationResult Compile(RegExpCompileData* input,
1439 bool ignore_case,
1440 bool multiline,
1441 Handle<String> pattern,
1442 bool is_ascii);
1443
1444 static void DotPrint(const char* label, RegExpNode* node, bool ignore_case);
1445};
1446
1447
Leon Clarkee46be812010-01-19 14:06:41 +00001448class OffsetsVector {
1449 public:
1450 inline OffsetsVector(int num_registers)
1451 : offsets_vector_length_(num_registers) {
Steve Block44f0eee2011-05-26 01:26:41 +01001452 if (offsets_vector_length_ > Isolate::kJSRegexpStaticOffsetsVectorSize) {
Leon Clarkee46be812010-01-19 14:06:41 +00001453 vector_ = NewArray<int>(offsets_vector_length_);
1454 } else {
Steve Block44f0eee2011-05-26 01:26:41 +01001455 vector_ = Isolate::Current()->jsregexp_static_offsets_vector();
Leon Clarkee46be812010-01-19 14:06:41 +00001456 }
1457 }
1458 inline ~OffsetsVector() {
Steve Block44f0eee2011-05-26 01:26:41 +01001459 if (offsets_vector_length_ > Isolate::kJSRegexpStaticOffsetsVectorSize) {
Leon Clarkee46be812010-01-19 14:06:41 +00001460 DeleteArray(vector_);
1461 vector_ = NULL;
1462 }
1463 }
1464 inline int* vector() { return vector_; }
1465 inline int length() { return offsets_vector_length_; }
1466
1467 static const int kStaticOffsetsVectorSize = 50;
1468
1469 private:
Steve Block44f0eee2011-05-26 01:26:41 +01001470 static Address static_offsets_vector_address(Isolate* isolate) {
1471 return reinterpret_cast<Address>(isolate->jsregexp_static_offsets_vector());
Leon Clarkee46be812010-01-19 14:06:41 +00001472 }
1473
1474 int* vector_;
1475 int offsets_vector_length_;
Leon Clarkee46be812010-01-19 14:06:41 +00001476
1477 friend class ExternalReference;
1478};
1479
1480
Steve Blocka7e24c12009-10-30 11:49:00 +00001481} } // namespace v8::internal
1482
1483#endif // V8_JSREGEXP_H_