1// Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#ifndef RUNTIME_VM_REGEXP_H_
6#define RUNTIME_VM_REGEXP_H_
7
8#include "platform/unicode.h"
9
10#include "vm/object.h"
11#include "vm/regexp_assembler.h"
12#include "vm/splay-tree.h"
13
14namespace dart {
15
16class NodeVisitor;
17class RegExpCompiler;
18class RegExpMacroAssembler;
19class RegExpNode;
20class RegExpTree;
21class BoyerMooreLookahead;
22
23// Represents code units in the range from from_ to to_, both ends are
24// inclusive.
25class CharacterRange {
26 public:
27 CharacterRange() : from_(0), to_(0) {}
28 CharacterRange(int32_t from, int32_t to) : from_(from), to_(to) {}
29
30 static void AddClassEscape(uint16_t type,
31 ZoneGrowableArray<CharacterRange>* ranges);
32 // Add class escapes with case equivalent closure for \w and \W if necessary.
33 static void AddClassEscape(uint16_t type,
34 ZoneGrowableArray<CharacterRange>* ranges,
35 bool add_unicode_case_equivalents);
36 static GrowableArray<const intptr_t> GetWordBounds();
37 static inline CharacterRange Singleton(int32_t value) {
38 return CharacterRange(value, value);
39 }
40 static inline CharacterRange Range(int32_t from, int32_t to) {
41 ASSERT(from <= to);
42 return CharacterRange(from, to);
43 }
44 static inline CharacterRange Everything() {
45 return CharacterRange(0, Utf::kMaxCodePoint);
46 }
47 static inline ZoneGrowableArray<CharacterRange>* List(Zone* zone,
48 CharacterRange range) {
49 auto list = new (zone) ZoneGrowableArray<CharacterRange>(1);
50 list->Add(range);
51 return list;
52 }
53 bool Contains(int32_t i) const { return from_ <= i && i <= to_; }
54 int32_t from() const { return from_; }
55 void set_from(int32_t value) { from_ = value; }
56 int32_t to() const { return to_; }
57 void set_to(int32_t value) { to_ = value; }
58 bool is_valid() const { return from_ <= to_; }
59 bool IsEverything(int32_t max) const { return from_ == 0 && to_ >= max; }
60 bool IsSingleton() const { return (from_ == to_); }
61 static void AddCaseEquivalents(ZoneGrowableArray<CharacterRange>* ranges,
62 bool is_one_byte,
63 Zone* zone);
64 static void Split(ZoneGrowableArray<CharacterRange>* base,
65 GrowableArray<const intptr_t> overlay,
66 ZoneGrowableArray<CharacterRange>** included,
67 ZoneGrowableArray<CharacterRange>** excluded,
68 Zone* zone);
69 // Whether a range list is in canonical form: Ranges ordered by from value,
70 // and ranges non-overlapping and non-adjacent.
71 static bool IsCanonical(ZoneGrowableArray<CharacterRange>* ranges);
72 // Convert range list to canonical form. The characters covered by the ranges
73 // will still be the same, but no character is in more than one range, and
74 // adjacent ranges are merged. The resulting list may be shorter than the
75 // original, but cannot be longer.
76 static void Canonicalize(ZoneGrowableArray<CharacterRange>* ranges);
77 // Negate the contents of a character range in canonical form.
78 static void Negate(ZoneGrowableArray<CharacterRange>* src,
79 ZoneGrowableArray<CharacterRange>* dst);
80 static const intptr_t kStartMarker = (1 << 24);
81 static const intptr_t kPayloadMask = (1 << 24) - 1;
82
83 private:
84 int32_t from_;
85 int32_t to_;
86
87 DISALLOW_ALLOCATION();
88};
89
90// A set of unsigned integers that behaves especially well on small
91// integers (< 32). May do zone-allocation.
92class OutSet : public ZoneAllocated {
93 public:
94 OutSet() : first_(0), remaining_(NULL), successors_(NULL) {}
95 OutSet* Extend(unsigned value, Zone* zone);
96 bool Get(unsigned value) const;
97 static const unsigned kFirstLimit = 32;
98
99 private:
100 // Destructively set a value in this set. In most cases you want
101 // to use Extend instead to ensure that only one instance exists
102 // that contains the same values.
103 void Set(unsigned value, Zone* zone);
104
105 // The successors are a list of sets that contain the same values
106 // as this set and the one more value that is not present in this
107 // set.
108 ZoneGrowableArray<OutSet*>* successors() { return successors_; }
109
110 OutSet(uint32_t first, ZoneGrowableArray<unsigned>* remaining)
111 : first_(first), remaining_(remaining), successors_(NULL) {}
112 uint32_t first_;
113 ZoneGrowableArray<unsigned>* remaining_;
114 ZoneGrowableArray<OutSet*>* successors_;
115 friend class Trace;
116};
117
118// A mapping from integers, specified as ranges, to a set of integers.
119// Used for mapping character ranges to choices.
120class ChoiceTable : public ValueObject {
121 public:
122 explicit ChoiceTable(Zone* zone) : tree_(zone) {}
123
124 class Entry {
125 public:
126 Entry() : from_(0), to_(0), out_set_(nullptr) {}
127 Entry(int32_t from, int32_t to, OutSet* out_set)
128 : from_(from), to_(to), out_set_(out_set) {
129 ASSERT(from <= to);
130 }
131 int32_t from() { return from_; }
132 int32_t to() { return to_; }
133 void set_to(int32_t value) { to_ = value; }
134 void AddValue(int value, Zone* zone) {
135 out_set_ = out_set_->Extend(value, zone);
136 }
137 OutSet* out_set() { return out_set_; }
138
139 private:
140 int32_t from_;
141 int32_t to_;
142 OutSet* out_set_;
143 };
144
145 class Config {
146 public:
147 typedef int32_t Key;
148 typedef Entry Value;
149 static const int32_t kNoKey;
150 static const Entry NoValue() { return Value(); }
151 static inline int Compare(int32_t a, int32_t b) {
152 if (a == b)
153 return 0;
154 else if (a < b)
155 return -1;
156 else
157 return 1;
158 }
159 };
160
161 void AddRange(CharacterRange range, int32_t value, Zone* zone);
162 OutSet* Get(int32_t value);
163 void Dump();
164
165 template <typename Callback>
166 void ForEach(Callback* callback) {
167 return tree()->ForEach(callback);
168 }
169
170 private:
171 // There can't be a static empty set since it allocates its
172 // successors in a zone and caches them.
173 OutSet* empty() { return &empty_; }
174 OutSet empty_;
175 ZoneSplayTree<Config>* tree() { return &tree_; }
176 ZoneSplayTree<Config> tree_;
177};
178
179// Categorizes character ranges into BMP, non-BMP, lead, and trail surrogates.
180class UnicodeRangeSplitter : public ValueObject {
181 public:
182 UnicodeRangeSplitter(Zone* zone, ZoneGrowableArray<CharacterRange>* base);
183 void Call(uint32_t from, ChoiceTable::Entry entry);
184
185 ZoneGrowableArray<CharacterRange>* bmp() { return bmp_; }
186 ZoneGrowableArray<CharacterRange>* lead_surrogates() {
187 return lead_surrogates_;
188 }
189 ZoneGrowableArray<CharacterRange>* trail_surrogates() {
190 return trail_surrogates_;
191 }
192 ZoneGrowableArray<CharacterRange>* non_bmp() const { return non_bmp_; }
193
194 private:
195 static const int kBase = 0;
196 // Separate ranges into
197 static const int kBmpCodePoints = 1;
198 static const int kLeadSurrogates = 2;
199 static const int kTrailSurrogates = 3;
200 static const int kNonBmpCodePoints = 4;
201
202 Zone* zone_;
203 ChoiceTable table_;
204 ZoneGrowableArray<CharacterRange>* bmp_;
205 ZoneGrowableArray<CharacterRange>* lead_surrogates_;
206 ZoneGrowableArray<CharacterRange>* trail_surrogates_;
207 ZoneGrowableArray<CharacterRange>* non_bmp_;
208};
209
210#define FOR_EACH_NODE_TYPE(VISIT) \
211 VISIT(End) \
212 VISIT(Action) \
213 VISIT(Choice) \
214 VISIT(BackReference) \
215 VISIT(Assertion) \
216 VISIT(Text)
217
218#define FOR_EACH_REG_EXP_TREE_TYPE(VISIT) \
219 VISIT(Disjunction) \
220 VISIT(Alternative) \
221 VISIT(Assertion) \
222 VISIT(CharacterClass) \
223 VISIT(Atom) \
224 VISIT(Quantifier) \
225 VISIT(Capture) \
226 VISIT(Lookaround) \
227 VISIT(BackReference) \
228 VISIT(Empty) \
229 VISIT(Text)
230
231#define FORWARD_DECLARE(Name) class RegExp##Name;
232FOR_EACH_REG_EXP_TREE_TYPE(FORWARD_DECLARE)
233#undef FORWARD_DECLARE
234
235class TextElement {
236 public:
237 enum TextType { ATOM, CHAR_CLASS };
238
239 static TextElement Atom(RegExpAtom* atom);
240 static TextElement CharClass(RegExpCharacterClass* char_class);
241
242 intptr_t cp_offset() const { return cp_offset_; }
243 void set_cp_offset(intptr_t cp_offset) { cp_offset_ = cp_offset; }
244 intptr_t length() const;
245
246 TextType text_type() const { return text_type_; }
247
248 RegExpTree* tree() const { return tree_; }
249
250 RegExpAtom* atom() const {
251 ASSERT(text_type() == ATOM);
252 return reinterpret_cast<RegExpAtom*>(tree());
253 }
254
255 RegExpCharacterClass* char_class() const {
256 ASSERT(text_type() == CHAR_CLASS);
257 return reinterpret_cast<RegExpCharacterClass*>(tree());
258 }
259
260 private:
261 TextElement(TextType text_type, RegExpTree* tree)
262 : cp_offset_(-1), text_type_(text_type), tree_(tree) {}
263
264 intptr_t cp_offset_;
265 TextType text_type_;
266 RegExpTree* tree_;
267
268 DISALLOW_ALLOCATION();
269};
270
271class Trace;
272struct PreloadState;
273class GreedyLoopState;
274class AlternativeGenerationList;
275
276struct NodeInfo {
277 NodeInfo()
278 : being_analyzed(false),
279 been_analyzed(false),
280 follows_word_interest(false),
281 follows_newline_interest(false),
282 follows_start_interest(false),
283 at_end(false),
284 visited(false),
285 replacement_calculated(false) {}
286
287 // Returns true if the interests and assumptions of this node
288 // matches the given one.
289 bool Matches(NodeInfo* that) {
290 return (at_end == that->at_end) &&
291 (follows_word_interest == that->follows_word_interest) &&
292 (follows_newline_interest == that->follows_newline_interest) &&
293 (follows_start_interest == that->follows_start_interest);
294 }
295
296 // Updates the interests of this node given the interests of the
297 // node preceding it.
298 void AddFromPreceding(NodeInfo* that) {
299 at_end |= that->at_end;
300 follows_word_interest |= that->follows_word_interest;
301 follows_newline_interest |= that->follows_newline_interest;
302 follows_start_interest |= that->follows_start_interest;
303 }
304
305 bool HasLookbehind() {
306 return follows_word_interest || follows_newline_interest ||
307 follows_start_interest;
308 }
309
310 // Sets the interests of this node to include the interests of the
311 // following node.
312 void AddFromFollowing(NodeInfo* that) {
313 follows_word_interest |= that->follows_word_interest;
314 follows_newline_interest |= that->follows_newline_interest;
315 follows_start_interest |= that->follows_start_interest;
316 }
317
318 void ResetCompilationState() {
319 being_analyzed = false;
320 been_analyzed = false;
321 }
322
323 bool being_analyzed : 1;
324 bool been_analyzed : 1;
325
326 // These bits are set of this node has to know what the preceding
327 // character was.
328 bool follows_word_interest : 1;
329 bool follows_newline_interest : 1;
330 bool follows_start_interest : 1;
331
332 bool at_end : 1;
333 bool visited : 1;
334 bool replacement_calculated : 1;
335};
336
337// Details of a quick mask-compare check that can look ahead in the
338// input stream.
339class QuickCheckDetails {
340 public:
341 QuickCheckDetails()
342 : characters_(0), mask_(0), value_(0), cannot_match_(false) {}
343 explicit QuickCheckDetails(intptr_t characters)
344 : characters_(characters), mask_(0), value_(0), cannot_match_(false) {}
345 bool Rationalize(bool one_byte);
346 // Merge in the information from another branch of an alternation.
347 void Merge(QuickCheckDetails* other, intptr_t from_index);
348 // Advance the current position by some amount.
349 void Advance(intptr_t by, bool one_byte);
350 void Clear();
351 bool cannot_match() { return cannot_match_; }
352 void set_cannot_match() { cannot_match_ = true; }
353 struct Position {
354 Position() : mask(0), value(0), determines_perfectly(false) {}
355 uint16_t mask;
356 uint16_t value;
357 bool determines_perfectly;
358 };
359 intptr_t characters() { return characters_; }
360 void set_characters(intptr_t characters) { characters_ = characters; }
361 Position* positions(intptr_t index) {
362 ASSERT(index >= 0);
363 ASSERT(index < characters_);
364 return positions_ + index;
365 }
366 uint32_t mask() { return mask_; }
367 uint32_t value() { return value_; }
368
369 private:
370 // How many characters do we have quick check information from. This is
371 // the same for all branches of a choice node.
372 intptr_t characters_;
373 Position positions_[4];
374 // These values are the condensate of the above array after Rationalize().
375 uint32_t mask_;
376 uint32_t value_;
377 // If set to true, there is no way this quick check can match at all.
378 // E.g., if it requires to be at the start of the input, and isn't.
379 bool cannot_match_;
380
381 DISALLOW_ALLOCATION();
382};
383
384class RegExpNode : public ZoneAllocated {
385 public:
386 explicit RegExpNode(Zone* zone)
387 : replacement_(NULL), trace_count_(0), zone_(zone) {
388 bm_info_[0] = bm_info_[1] = NULL;
389 }
390 virtual ~RegExpNode();
391 virtual void Accept(NodeVisitor* visitor) = 0;
392 // Generates a goto to this node or actually generates the code at this point.
393 virtual void Emit(RegExpCompiler* compiler, Trace* trace) = 0;
394 // How many characters must this node consume at a minimum in order to
395 // succeed. If we have found at least 'still_to_find' characters that
396 // must be consumed there is no need to ask any following nodes whether
397 // they are sure to eat any more characters. The not_at_start argument is
398 // used to indicate that we know we are not at the start of the input. In
399 // this case anchored branches will always fail and can be ignored when
400 // determining how many characters are consumed on success.
401 virtual intptr_t EatsAtLeast(intptr_t still_to_find,
402 intptr_t budget,
403 bool not_at_start) = 0;
404 // Emits some quick code that checks whether the preloaded characters match.
405 // Falls through on certain failure, jumps to the label on possible success.
406 // If the node cannot make a quick check it does nothing and returns false.
407 bool EmitQuickCheck(RegExpCompiler* compiler,
408 Trace* bounds_check_trace,
409 Trace* trace,
410 bool preload_has_checked_bounds,
411 BlockLabel* on_possible_success,
412 QuickCheckDetails* details_return,
413 bool fall_through_on_failure);
414 // For a given number of characters this returns a mask and a value. The
415 // next n characters are anded with the mask and compared with the value.
416 // A comparison failure indicates the node cannot match the next n characters.
417 // A comparison success indicates the node may match.
418 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
419 RegExpCompiler* compiler,
420 intptr_t characters_filled_in,
421 bool not_at_start) = 0;
422 static const intptr_t kNodeIsTooComplexForGreedyLoops = -1;
423 virtual intptr_t GreedyLoopTextLength() {
424 return kNodeIsTooComplexForGreedyLoops;
425 }
426 // Only returns the successor for a text node of length 1 that matches any
427 // character and that has no guards on it.
428 virtual RegExpNode* GetSuccessorOfOmnivorousTextNode(
429 RegExpCompiler* compiler) {
430 return NULL;
431 }
432
433 // Collects information on the possible code units (mod 128) that can match if
434 // we look forward. This is used for a Boyer-Moore-like string searching
435 // implementation. TODO(erikcorry): This should share more code with
436 // EatsAtLeast, GetQuickCheckDetails. The budget argument is used to limit
437 // the number of nodes we are willing to look at in order to create this data.
438 static const intptr_t kRecursionBudget = 200;
439 virtual void FillInBMInfo(intptr_t offset,
440 intptr_t budget,
441 BoyerMooreLookahead* bm,
442 bool not_at_start) {
443 UNREACHABLE();
444 }
445
446 // If we know that the input is one-byte then there are some nodes that can
447 // never match. This method returns a node that can be substituted for
448 // itself, or NULL if the node can never match.
449 virtual RegExpNode* FilterOneByte(intptr_t depth) { return this; }
450 // Helper for FilterOneByte.
451 RegExpNode* replacement() {
452 ASSERT(info()->replacement_calculated);
453 return replacement_;
454 }
455 RegExpNode* set_replacement(RegExpNode* replacement) {
456 info()->replacement_calculated = true;
457 replacement_ = replacement;
458 return replacement; // For convenience.
459 }
460
461 // We want to avoid recalculating the lookahead info, so we store it on the
462 // node. Only info that is for this node is stored. We can tell that the
463 // info is for this node when offset == 0, so the information is calculated
464 // relative to this node.
465 void SaveBMInfo(BoyerMooreLookahead* bm, bool not_at_start, intptr_t offset) {
466 if (offset == 0) set_bm_info(not_at_start, bm);
467 }
468
469 BlockLabel* label() { return &label_; }
470 // If non-generic code is generated for a node (i.e. the node is not at the
471 // start of the trace) then it cannot be reused. This variable sets a limit
472 // on how often we allow that to happen before we insist on starting a new
473 // trace and generating generic code for a node that can be reused by flushing
474 // the deferred actions in the current trace and generating a goto.
475 static const intptr_t kMaxCopiesCodeGenerated = 10;
476
477 NodeInfo* info() { return &info_; }
478
479 BoyerMooreLookahead* bm_info(bool not_at_start) {
480 return bm_info_[not_at_start ? 1 : 0];
481 }
482
483 Zone* zone() const { return zone_; }
484
485 protected:
486 enum LimitResult { DONE, CONTINUE };
487 RegExpNode* replacement_;
488
489 LimitResult LimitVersions(RegExpCompiler* compiler, Trace* trace);
490
491 void set_bm_info(bool not_at_start, BoyerMooreLookahead* bm) {
492 bm_info_[not_at_start ? 1 : 0] = bm;
493 }
494
495 private:
496 static const intptr_t kFirstCharBudget = 10;
497 BlockLabel label_;
498 NodeInfo info_;
499 // This variable keeps track of how many times code has been generated for
500 // this node (in different traces). We don't keep track of where the
501 // generated code is located unless the code is generated at the start of
502 // a trace, in which case it is generic and can be reused by flushing the
503 // deferred operations in the current trace and generating a goto.
504 intptr_t trace_count_;
505 BoyerMooreLookahead* bm_info_[2];
506 Zone* zone_;
507};
508
509// A simple closed interval.
510class Interval {
511 public:
512 Interval() : from_(kNone), to_(kNone) {}
513 Interval(intptr_t from, intptr_t to) : from_(from), to_(to) {}
514
515 Interval Union(Interval that) {
516 if (that.from_ == kNone)
517 return *this;
518 else if (from_ == kNone)
519 return that;
520 else
521 return Interval(Utils::Minimum(from_, that.from_),
522 Utils::Maximum(to_, that.to_));
523 }
524 bool Contains(intptr_t value) const {
525 return (from_ <= value) && (value <= to_);
526 }
527 bool is_empty() const { return from_ == kNone; }
528 intptr_t from() const { return from_; }
529 intptr_t to() const { return to_; }
530 static Interval Empty() { return Interval(); }
531 static const intptr_t kNone = -1;
532
533 private:
534 intptr_t from_;
535 intptr_t to_;
536
537 DISALLOW_ALLOCATION();
538};
539
540class SeqRegExpNode : public RegExpNode {
541 public:
542 explicit SeqRegExpNode(RegExpNode* on_success)
543 : RegExpNode(on_success->zone()), on_success_(on_success) {}
544 RegExpNode* on_success() { return on_success_; }
545 void set_on_success(RegExpNode* node) { on_success_ = node; }
546 virtual RegExpNode* FilterOneByte(intptr_t depth);
547 virtual void FillInBMInfo(intptr_t offset,
548 intptr_t budget,
549 BoyerMooreLookahead* bm,
550 bool not_at_start) {
551 on_success_->FillInBMInfo(offset, budget - 1, bm, not_at_start);
552 if (offset == 0) set_bm_info(not_at_start, bm);
553 }
554
555 protected:
556 RegExpNode* FilterSuccessor(intptr_t depth);
557
558 private:
559 RegExpNode* on_success_;
560};
561
562class ActionNode : public SeqRegExpNode {
563 public:
564 enum ActionType {
565 SET_REGISTER,
566 INCREMENT_REGISTER,
567 STORE_POSITION,
568 BEGIN_SUBMATCH,
569 POSITIVE_SUBMATCH_SUCCESS,
570 EMPTY_MATCH_CHECK,
571 CLEAR_CAPTURES
572 };
573 static ActionNode* SetRegister(intptr_t reg,
574 intptr_t val,
575 RegExpNode* on_success);
576 static ActionNode* IncrementRegister(intptr_t reg, RegExpNode* on_success);
577 static ActionNode* StorePosition(intptr_t reg,
578 bool is_capture,
579 RegExpNode* on_success);
580 static ActionNode* ClearCaptures(Interval range, RegExpNode* on_success);
581 static ActionNode* BeginSubmatch(intptr_t stack_pointer_reg,
582 intptr_t position_reg,
583 RegExpNode* on_success);
584 static ActionNode* PositiveSubmatchSuccess(intptr_t stack_pointer_reg,
585 intptr_t restore_reg,
586 intptr_t clear_capture_count,
587 intptr_t clear_capture_from,
588 RegExpNode* on_success);
589 static ActionNode* EmptyMatchCheck(intptr_t start_register,
590 intptr_t repetition_register,
591 intptr_t repetition_limit,
592 RegExpNode* on_success);
593 virtual void Accept(NodeVisitor* visitor);
594 virtual void Emit(RegExpCompiler* compiler, Trace* trace);
595 virtual intptr_t EatsAtLeast(intptr_t still_to_find,
596 intptr_t budget,
597 bool not_at_start);
598 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
599 RegExpCompiler* compiler,
600 intptr_t filled_in,
601 bool not_at_start) {
602 return on_success()->GetQuickCheckDetails(details, compiler, filled_in,
603 not_at_start);
604 }
605 virtual void FillInBMInfo(intptr_t offset,
606 intptr_t budget,
607 BoyerMooreLookahead* bm,
608 bool not_at_start);
609 ActionType action_type() { return action_type_; }
610 // TODO(erikcorry): We should allow some action nodes in greedy loops.
611 virtual intptr_t GreedyLoopTextLength() {
612 return kNodeIsTooComplexForGreedyLoops;
613 }
614
615 private:
616 union {
617 struct {
618 intptr_t reg;
619 intptr_t value;
620 } u_store_register;
621 struct {
622 intptr_t reg;
623 } u_increment_register;
624 struct {
625 intptr_t reg;
626 bool is_capture;
627 } u_position_register;
628 struct {
629 intptr_t stack_pointer_register;
630 intptr_t current_position_register;
631 intptr_t clear_register_count;
632 intptr_t clear_register_from;
633 } u_submatch;
634 struct {
635 intptr_t start_register;
636 intptr_t repetition_register;
637 intptr_t repetition_limit;
638 } u_empty_match_check;
639 struct {
640 intptr_t range_from;
641 intptr_t range_to;
642 } u_clear_captures;
643 } data_;
644 ActionNode(ActionType action_type, RegExpNode* on_success)
645 : SeqRegExpNode(on_success), action_type_(action_type) {}
646 ActionType action_type_;
647 friend class DotPrinter;
648};
649
650class TextNode : public SeqRegExpNode {
651 public:
652 TextNode(ZoneGrowableArray<TextElement>* elms,
653 bool read_backward,
654 RegExpNode* on_success)
655 : SeqRegExpNode(on_success), elms_(elms), read_backward_(read_backward) {}
656 TextNode(RegExpCharacterClass* that,
657 bool read_backward,
658 RegExpNode* on_success)
659 : SeqRegExpNode(on_success),
660 elms_(new (zone()) ZoneGrowableArray<TextElement>(1)),
661 read_backward_(read_backward) {
662 elms_->Add(TextElement::CharClass(that));
663 }
664 // Create TextNode for a single character class for the given ranges.
665 static TextNode* CreateForCharacterRanges(
666 ZoneGrowableArray<CharacterRange>* ranges,
667 bool read_backward,
668 RegExpNode* on_success,
669 RegExpFlags flags);
670 // Create TextNode for a surrogate pair with a range given for the
671 // lead and the trail surrogate each.
672 static TextNode* CreateForSurrogatePair(CharacterRange lead,
673 CharacterRange trail,
674 bool read_backward,
675 RegExpNode* on_success,
676 RegExpFlags flags);
677 virtual void Accept(NodeVisitor* visitor);
678 virtual void Emit(RegExpCompiler* compiler, Trace* trace);
679 virtual intptr_t EatsAtLeast(intptr_t still_to_find,
680 intptr_t budget,
681 bool not_at_start);
682 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
683 RegExpCompiler* compiler,
684 intptr_t characters_filled_in,
685 bool not_at_start);
686 ZoneGrowableArray<TextElement>* elements() { return elms_; }
687 bool read_backward() { return read_backward_; }
688 void MakeCaseIndependent(bool is_one_byte);
689 virtual intptr_t GreedyLoopTextLength();
690 virtual RegExpNode* GetSuccessorOfOmnivorousTextNode(
691 RegExpCompiler* compiler);
692 virtual void FillInBMInfo(intptr_t offset,
693 intptr_t budget,
694 BoyerMooreLookahead* bm,
695 bool not_at_start);
696 void CalculateOffsets();
697 virtual RegExpNode* FilterOneByte(intptr_t depth);
698
699 private:
700 enum TextEmitPassType {
701 NON_LATIN1_MATCH, // Check for characters that can't match.
702 SIMPLE_CHARACTER_MATCH, // Case-dependent single character check.
703 NON_LETTER_CHARACTER_MATCH, // Check characters that have no case equivs.
704 CASE_CHARACTER_MATCH, // Case-independent single character check.
705 CHARACTER_CLASS_MATCH // Character class.
706 };
707 static bool SkipPass(intptr_t pass, bool ignore_case);
708 static const intptr_t kFirstRealPass = SIMPLE_CHARACTER_MATCH;
709 static const intptr_t kLastPass = CHARACTER_CLASS_MATCH;
710 void TextEmitPass(RegExpCompiler* compiler,
711 TextEmitPassType pass,
712 bool preloaded,
713 Trace* trace,
714 bool first_element_checked,
715 intptr_t* checked_up_to);
716 intptr_t Length();
717 ZoneGrowableArray<TextElement>* elms_;
718 bool read_backward_;
719};
720
721class AssertionNode : public SeqRegExpNode {
722 public:
723 enum AssertionType {
724 AT_END,
725 AT_START,
726 AT_BOUNDARY,
727 AT_NON_BOUNDARY,
728 AFTER_NEWLINE
729 };
730 static AssertionNode* AtEnd(RegExpNode* on_success) {
731 return new (on_success->zone()) AssertionNode(AT_END, on_success);
732 }
733 static AssertionNode* AtStart(RegExpNode* on_success) {
734 return new (on_success->zone()) AssertionNode(AT_START, on_success);
735 }
736 static AssertionNode* AtBoundary(RegExpNode* on_success) {
737 return new (on_success->zone()) AssertionNode(AT_BOUNDARY, on_success);
738 }
739 static AssertionNode* AtNonBoundary(RegExpNode* on_success) {
740 return new (on_success->zone()) AssertionNode(AT_NON_BOUNDARY, on_success);
741 }
742 static AssertionNode* AfterNewline(RegExpNode* on_success) {
743 return new (on_success->zone()) AssertionNode(AFTER_NEWLINE, on_success);
744 }
745 virtual void Accept(NodeVisitor* visitor);
746 virtual void Emit(RegExpCompiler* compiler, Trace* trace);
747 virtual intptr_t EatsAtLeast(intptr_t still_to_find,
748 intptr_t budget,
749 bool not_at_start);
750 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
751 RegExpCompiler* compiler,
752 intptr_t filled_in,
753 bool not_at_start);
754 virtual void FillInBMInfo(intptr_t offset,
755 intptr_t budget,
756 BoyerMooreLookahead* bm,
757 bool not_at_start);
758 AssertionType assertion_type() { return assertion_type_; }
759
760 private:
761 void EmitBoundaryCheck(RegExpCompiler* compiler, Trace* trace);
762 enum IfPrevious { kIsNonWord, kIsWord };
763 void BacktrackIfPrevious(RegExpCompiler* compiler,
764 Trace* trace,
765 IfPrevious backtrack_if_previous);
766 AssertionNode(AssertionType t, RegExpNode* on_success)
767 : SeqRegExpNode(on_success), assertion_type_(t) {}
768 AssertionType assertion_type_;
769};
770
771class BackReferenceNode : public SeqRegExpNode {
772 public:
773 BackReferenceNode(intptr_t start_reg,
774 intptr_t end_reg,
775 RegExpFlags flags,
776 bool read_backward,
777 RegExpNode* on_success)
778 : SeqRegExpNode(on_success),
779 start_reg_(start_reg),
780 end_reg_(end_reg),
781 flags_(flags),
782 read_backward_(read_backward) {}
783 virtual void Accept(NodeVisitor* visitor);
784 intptr_t start_register() { return start_reg_; }
785 intptr_t end_register() { return end_reg_; }
786 bool read_backward() { return read_backward_; }
787 virtual void Emit(RegExpCompiler* compiler, Trace* trace);
788 virtual intptr_t EatsAtLeast(intptr_t still_to_find,
789 intptr_t recursion_depth,
790 bool not_at_start);
791 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
792 RegExpCompiler* compiler,
793 intptr_t characters_filled_in,
794 bool not_at_start) {
795 return;
796 }
797 virtual void FillInBMInfo(intptr_t offset,
798 intptr_t budget,
799 BoyerMooreLookahead* bm,
800 bool not_at_start);
801
802 private:
803 intptr_t start_reg_;
804 intptr_t end_reg_;
805 RegExpFlags flags_;
806 bool read_backward_;
807};
808
809class EndNode : public RegExpNode {
810 public:
811 enum Action { ACCEPT, BACKTRACK, NEGATIVE_SUBMATCH_SUCCESS };
812 explicit EndNode(Action action, Zone* zone)
813 : RegExpNode(zone), action_(action) {}
814 virtual void Accept(NodeVisitor* visitor);
815 virtual void Emit(RegExpCompiler* compiler, Trace* trace);
816 virtual intptr_t EatsAtLeast(intptr_t still_to_find,
817 intptr_t recursion_depth,
818 bool not_at_start) {
819 return 0;
820 }
821 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
822 RegExpCompiler* compiler,
823 intptr_t characters_filled_in,
824 bool not_at_start) {
825 // Returning 0 from EatsAtLeast should ensure we never get here.
826 UNREACHABLE();
827 }
828 virtual void FillInBMInfo(intptr_t offset,
829 intptr_t budget,
830 BoyerMooreLookahead* bm,
831 bool not_at_start) {
832 // Returning 0 from EatsAtLeast should ensure we never get here.
833 UNREACHABLE();
834 }
835
836 private:
837 Action action_;
838};
839
840class NegativeSubmatchSuccess : public EndNode {
841 public:
842 NegativeSubmatchSuccess(intptr_t stack_pointer_reg,
843 intptr_t position_reg,
844 intptr_t clear_capture_count,
845 intptr_t clear_capture_start,
846 Zone* zone)
847 : EndNode(NEGATIVE_SUBMATCH_SUCCESS, zone),
848 stack_pointer_register_(stack_pointer_reg),
849 current_position_register_(position_reg),
850 clear_capture_count_(clear_capture_count),
851 clear_capture_start_(clear_capture_start) {}
852 virtual void Emit(RegExpCompiler* compiler, Trace* trace);
853
854 private:
855 intptr_t stack_pointer_register_;
856 intptr_t current_position_register_;
857 intptr_t clear_capture_count_;
858 intptr_t clear_capture_start_;
859};
860
861class Guard : public ZoneAllocated {
862 public:
863 enum Relation { LT, GEQ };
864 Guard(intptr_t reg, Relation op, intptr_t value)
865 : reg_(reg), op_(op), value_(value) {}
866 intptr_t reg() { return reg_; }
867 Relation op() { return op_; }
868 intptr_t value() { return value_; }
869
870 private:
871 intptr_t reg_;
872 Relation op_;
873 intptr_t value_;
874};
875
876class GuardedAlternative {
877 public:
878 explicit GuardedAlternative(RegExpNode* node) : node_(node), guards_(NULL) {}
879 void AddGuard(Guard* guard, Zone* zone);
880 RegExpNode* node() const { return node_; }
881 void set_node(RegExpNode* node) { node_ = node; }
882 ZoneGrowableArray<Guard*>* guards() const { return guards_; }
883
884 private:
885 RegExpNode* node_;
886 ZoneGrowableArray<Guard*>* guards_;
887
888 DISALLOW_ALLOCATION();
889};
890
891struct AlternativeGeneration;
892
893class ChoiceNode : public RegExpNode {
894 public:
895 explicit ChoiceNode(intptr_t expected_size, Zone* zone)
896 : RegExpNode(zone),
897 alternatives_(new (zone)
898 ZoneGrowableArray<GuardedAlternative>(expected_size)),
899 not_at_start_(false),
900 being_calculated_(false) {}
901 virtual void Accept(NodeVisitor* visitor);
902 void AddAlternative(GuardedAlternative node) { alternatives()->Add(node); }
903 ZoneGrowableArray<GuardedAlternative>* alternatives() {
904 return alternatives_;
905 }
906 virtual void Emit(RegExpCompiler* compiler, Trace* trace);
907 virtual intptr_t EatsAtLeast(intptr_t still_to_find,
908 intptr_t budget,
909 bool not_at_start);
910 intptr_t EatsAtLeastHelper(intptr_t still_to_find,
911 intptr_t budget,
912 RegExpNode* ignore_this_node,
913 bool not_at_start);
914 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
915 RegExpCompiler* compiler,
916 intptr_t characters_filled_in,
917 bool not_at_start);
918 virtual void FillInBMInfo(intptr_t offset,
919 intptr_t budget,
920 BoyerMooreLookahead* bm,
921 bool not_at_start);
922
923 bool being_calculated() { return being_calculated_; }
924 bool not_at_start() { return not_at_start_; }
925 void set_not_at_start() { not_at_start_ = true; }
926 void set_being_calculated(bool b) { being_calculated_ = b; }
927 virtual bool try_to_emit_quick_check_for_alternative(bool is_first) {
928 return true;
929 }
930 virtual RegExpNode* FilterOneByte(intptr_t depth);
931 virtual bool read_backward() { return false; }
932
933 protected:
934 intptr_t GreedyLoopTextLengthForAlternative(
935 const GuardedAlternative* alternative);
936 ZoneGrowableArray<GuardedAlternative>* alternatives_;
937
938 private:
939 friend class Analysis;
940 void GenerateGuard(RegExpMacroAssembler* macro_assembler,
941 Guard* guard,
942 Trace* trace);
943 intptr_t CalculatePreloadCharacters(RegExpCompiler* compiler,
944 intptr_t eats_at_least);
945 void EmitOutOfLineContinuation(RegExpCompiler* compiler,
946 Trace* trace,
947 GuardedAlternative alternative,
948 AlternativeGeneration* alt_gen,
949 intptr_t preload_characters,
950 bool next_expects_preload);
951 void SetUpPreLoad(RegExpCompiler* compiler,
952 Trace* current_trace,
953 PreloadState* preloads);
954 void AssertGuardsMentionRegisters(Trace* trace);
955 intptr_t EmitOptimizedUnanchoredSearch(RegExpCompiler* compiler,
956 Trace* trace);
957 Trace* EmitGreedyLoop(RegExpCompiler* compiler,
958 Trace* trace,
959 AlternativeGenerationList* alt_gens,
960 PreloadState* preloads,
961 GreedyLoopState* greedy_loop_state,
962 intptr_t text_length);
963 void EmitChoices(RegExpCompiler* compiler,
964 AlternativeGenerationList* alt_gens,
965 intptr_t first_choice,
966 Trace* trace,
967 PreloadState* preloads);
968 // If true, this node is never checked at the start of the input.
969 // Allows a new trace to start with at_start() set to false.
970 bool not_at_start_;
971 bool being_calculated_;
972};
973
974class NegativeLookaroundChoiceNode : public ChoiceNode {
975 public:
976 explicit NegativeLookaroundChoiceNode(GuardedAlternative this_must_fail,
977 GuardedAlternative then_do_this,
978 Zone* zone)
979 : ChoiceNode(2, zone) {
980 AddAlternative(this_must_fail);
981 AddAlternative(then_do_this);
982 }
983 virtual intptr_t EatsAtLeast(intptr_t still_to_find,
984 intptr_t budget,
985 bool not_at_start);
986 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
987 RegExpCompiler* compiler,
988 intptr_t characters_filled_in,
989 bool not_at_start);
990 virtual void FillInBMInfo(intptr_t offset,
991 intptr_t budget,
992 BoyerMooreLookahead* bm,
993 bool not_at_start) {
994 (*alternatives_)[1].node()->FillInBMInfo(offset, budget - 1, bm,
995 not_at_start);
996 if (offset == 0) set_bm_info(not_at_start, bm);
997 }
998 // For a negative lookahead we don't emit the quick check for the
999 // alternative that is expected to fail. This is because quick check code
1000 // starts by loading enough characters for the alternative that takes fewest
1001 // characters, but on a negative lookahead the negative branch did not take
1002 // part in that calculation (EatsAtLeast) so the assumptions don't hold.
1003 virtual bool try_to_emit_quick_check_for_alternative(bool is_first) {
1004 return !is_first;
1005 }
1006 virtual RegExpNode* FilterOneByte(intptr_t depth);
1007};
1008
1009class LoopChoiceNode : public ChoiceNode {
1010 public:
1011 explicit LoopChoiceNode(bool body_can_be_zero_length,
1012 bool read_backward,
1013 Zone* zone)
1014 : ChoiceNode(2, zone),
1015 loop_node_(NULL),
1016 continue_node_(NULL),
1017 body_can_be_zero_length_(body_can_be_zero_length),
1018 read_backward_(read_backward) {}
1019 void AddLoopAlternative(GuardedAlternative alt);
1020 void AddContinueAlternative(GuardedAlternative alt);
1021 virtual void Emit(RegExpCompiler* compiler, Trace* trace);
1022 virtual intptr_t EatsAtLeast(intptr_t still_to_find,
1023 intptr_t budget,
1024 bool not_at_start);
1025 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
1026 RegExpCompiler* compiler,
1027 intptr_t characters_filled_in,
1028 bool not_at_start);
1029 virtual void FillInBMInfo(intptr_t offset,
1030 intptr_t budget,
1031 BoyerMooreLookahead* bm,
1032 bool not_at_start);
1033 RegExpNode* loop_node() { return loop_node_; }
1034 RegExpNode* continue_node() { return continue_node_; }
1035 bool body_can_be_zero_length() { return body_can_be_zero_length_; }
1036 virtual bool read_backward() { return read_backward_; }
1037 virtual void Accept(NodeVisitor* visitor);
1038 virtual RegExpNode* FilterOneByte(intptr_t depth);
1039
1040 private:
1041 // AddAlternative is made private for loop nodes because alternatives
1042 // should not be added freely, we need to keep track of which node
1043 // goes back to the node itself.
1044 void AddAlternative(GuardedAlternative node) {
1045 ChoiceNode::AddAlternative(node);
1046 }
1047
1048 RegExpNode* loop_node_;
1049 RegExpNode* continue_node_;
1050 bool body_can_be_zero_length_;
1051 bool read_backward_;
1052};
1053
1054// Improve the speed that we scan for an initial point where a non-anchored
1055// regexp can match by using a Boyer-Moore-like table. This is done by
1056// identifying non-greedy non-capturing loops in the nodes that eat any
1057// character one at a time. For example in the middle of the regexp
1058// /foo[\s\S]*?bar/ we find such a loop. There is also such a loop implicitly
1059// inserted at the start of any non-anchored regexp.
1060//
1061// When we have found such a loop we look ahead in the nodes to find the set of
1062// characters that can come at given distances. For example for the regexp
1063// /.?foo/ we know that there are at least 3 characters ahead of us, and the
1064// sets of characters that can occur are [any, [f, o], [o]]. We find a range in
1065// the lookahead info where the set of characters is reasonably constrained. In
1066// our example this is from index 1 to 2 (0 is not constrained). We can now
1067// look 3 characters ahead and if we don't find one of [f, o] (the union of
1068// [f, o] and [o]) then we can skip forwards by the range size (in this case 2).
1069//
1070// For Unicode input strings we do the same, but modulo 128.
1071//
1072// We also look at the first string fed to the regexp and use that to get a hint
1073// of the character frequencies in the inputs. This affects the assessment of
1074// whether the set of characters is 'reasonably constrained'.
1075//
1076// We also have another lookahead mechanism (called quick check in the code),
1077// which uses a wide load of multiple characters followed by a mask and compare
1078// to determine whether a match is possible at this point.
1079enum ContainedInLattice {
1080 kNotYet = 0,
1081 kLatticeIn = 1,
1082 kLatticeOut = 2,
1083 kLatticeUnknown = 3 // Can also mean both in and out.
1084};
1085
1086inline ContainedInLattice Combine(ContainedInLattice a, ContainedInLattice b) {
1087 return static_cast<ContainedInLattice>(a | b);
1088}
1089
1090ContainedInLattice AddRange(ContainedInLattice a,
1091 const intptr_t* ranges,
1092 intptr_t ranges_size,
1093 Interval new_range);
1094
1095class BoyerMoorePositionInfo : public ZoneAllocated {
1096 public:
1097 explicit BoyerMoorePositionInfo(Zone* zone)
1098 : map_(new (zone) ZoneGrowableArray<bool>(kMapSize)),
1099 map_count_(0),
1100 w_(kNotYet),
1101 s_(kNotYet),
1102 d_(kNotYet),
1103 surrogate_(kNotYet) {
1104 for (intptr_t i = 0; i < kMapSize; i++) {
1105 map_->Add(false);
1106 }
1107 }
1108
1109 bool& at(intptr_t i) { return (*map_)[i]; }
1110
1111 static const intptr_t kMapSize = 128;
1112 static const intptr_t kMask = kMapSize - 1;
1113
1114 intptr_t map_count() const { return map_count_; }
1115
1116 void Set(intptr_t character);
1117 void SetInterval(const Interval& interval);
1118 void SetAll();
1119 bool is_non_word() { return w_ == kLatticeOut; }
1120 bool is_word() { return w_ == kLatticeIn; }
1121
1122 private:
1123 ZoneGrowableArray<bool>* map_;
1124 intptr_t map_count_; // Number of set bits in the map.
1125 ContainedInLattice w_; // The \w character class.
1126 ContainedInLattice s_; // The \s character class.
1127 ContainedInLattice d_; // The \d character class.
1128 ContainedInLattice surrogate_; // Surrogate UTF-16 code units.
1129};
1130
1131class BoyerMooreLookahead : public ZoneAllocated {
1132 public:
1133 BoyerMooreLookahead(intptr_t length, RegExpCompiler* compiler, Zone* Zone);
1134
1135 intptr_t length() { return length_; }
1136 intptr_t max_char() { return max_char_; }
1137 RegExpCompiler* compiler() { return compiler_; }
1138
1139 intptr_t Count(intptr_t map_number) {
1140 return bitmaps_->At(map_number)->map_count();
1141 }
1142
1143 BoyerMoorePositionInfo* at(intptr_t i) { return bitmaps_->At(i); }
1144
1145 void Set(intptr_t map_number, intptr_t character) {
1146 if (character > max_char_) return;
1147 BoyerMoorePositionInfo* info = bitmaps_->At(map_number);
1148 info->Set(character);
1149 }
1150
1151 void SetInterval(intptr_t map_number, const Interval& interval) {
1152 if (interval.from() > max_char_) return;
1153 BoyerMoorePositionInfo* info = bitmaps_->At(map_number);
1154 if (interval.to() > max_char_) {
1155 info->SetInterval(Interval(interval.from(), max_char_));
1156 } else {
1157 info->SetInterval(interval);
1158 }
1159 }
1160
1161 void SetAll(intptr_t map_number) { bitmaps_->At(map_number)->SetAll(); }
1162
1163 void SetRest(intptr_t from_map) {
1164 for (intptr_t i = from_map; i < length_; i++)
1165 SetAll(i);
1166 }
1167 void EmitSkipInstructions(RegExpMacroAssembler* masm);
1168
1169 private:
1170 // This is the value obtained by EatsAtLeast. If we do not have at least this
1171 // many characters left in the sample string then the match is bound to fail.
1172 // Therefore it is OK to read a character this far ahead of the current match
1173 // point.
1174 intptr_t length_;
1175 RegExpCompiler* compiler_;
1176 // 0xff for Latin1, 0xffff for UTF-16.
1177 intptr_t max_char_;
1178 ZoneGrowableArray<BoyerMoorePositionInfo*>* bitmaps_;
1179
1180 intptr_t GetSkipTable(intptr_t min_lookahead,
1181 intptr_t max_lookahead,
1182 const TypedData& boolean_skip_table);
1183 bool FindWorthwhileInterval(intptr_t* from, intptr_t* to);
1184 intptr_t FindBestInterval(intptr_t max_number_of_chars,
1185 intptr_t old_biggest_points,
1186 intptr_t* from,
1187 intptr_t* to);
1188};
1189
1190// There are many ways to generate code for a node. This class encapsulates
1191// the current way we should be generating. In other words it encapsulates
1192// the current state of the code generator. The effect of this is that we
1193// generate code for paths that the matcher can take through the regular
1194// expression. A given node in the regexp can be code-generated several times
1195// as it can be part of several traces. For example for the regexp:
1196// /foo(bar|ip)baz/ the code to match baz will be generated twice, once as part
1197// of the foo-bar-baz trace and once as part of the foo-ip-baz trace. The code
1198// to match foo is generated only once (the traces have a common prefix). The
1199// code to store the capture is deferred and generated (twice) after the places
1200// where baz has been matched.
1201class Trace {
1202 public:
1203 // A value for a property that is either known to be true, know to be false,
1204 // or not known.
1205 enum TriBool { UNKNOWN = -1, FALSE_VALUE = 0, TRUE_VALUE = 1 };
1206
1207 class DeferredAction {
1208 public:
1209 DeferredAction(ActionNode::ActionType action_type, intptr_t reg)
1210 : action_type_(action_type), reg_(reg), next_(NULL) {}
1211 DeferredAction* next() { return next_; }
1212 bool Mentions(intptr_t reg);
1213 intptr_t reg() { return reg_; }
1214 ActionNode::ActionType action_type() { return action_type_; }
1215
1216 private:
1217 ActionNode::ActionType action_type_;
1218 intptr_t reg_;
1219 DeferredAction* next_;
1220 friend class Trace;
1221
1222 DISALLOW_ALLOCATION();
1223 };
1224
1225 class DeferredCapture : public DeferredAction {
1226 public:
1227 DeferredCapture(intptr_t reg, bool is_capture, Trace* trace)
1228 : DeferredAction(ActionNode::STORE_POSITION, reg),
1229 cp_offset_(trace->cp_offset()),
1230 is_capture_(is_capture) {}
1231 intptr_t cp_offset() { return cp_offset_; }
1232 bool is_capture() { return is_capture_; }
1233
1234 private:
1235 intptr_t cp_offset_;
1236 bool is_capture_;
1237 void set_cp_offset(intptr_t cp_offset) { cp_offset_ = cp_offset; }
1238 };
1239
1240 class DeferredSetRegister : public DeferredAction {
1241 public:
1242 DeferredSetRegister(intptr_t reg, intptr_t value)
1243 : DeferredAction(ActionNode::SET_REGISTER, reg), value_(value) {}
1244 intptr_t value() { return value_; }
1245
1246 private:
1247 intptr_t value_;
1248 };
1249
1250 class DeferredClearCaptures : public DeferredAction {
1251 public:
1252 explicit DeferredClearCaptures(Interval range)
1253 : DeferredAction(ActionNode::CLEAR_CAPTURES, -1), range_(range) {}
1254 Interval range() { return range_; }
1255
1256 private:
1257 Interval range_;
1258 };
1259
1260 class DeferredIncrementRegister : public DeferredAction {
1261 public:
1262 explicit DeferredIncrementRegister(intptr_t reg)
1263 : DeferredAction(ActionNode::INCREMENT_REGISTER, reg) {}
1264 };
1265
1266 Trace()
1267 : cp_offset_(0),
1268 actions_(NULL),
1269 backtrack_(NULL),
1270 stop_node_(NULL),
1271 loop_label_(NULL),
1272 characters_preloaded_(0),
1273 bound_checked_up_to_(0),
1274 flush_budget_(100),
1275 at_start_(UNKNOWN) {}
1276
1277 // End the trace. This involves flushing the deferred actions in the trace
1278 // and pushing a backtrack location onto the backtrack stack. Once this is
1279 // done we can start a new trace or go to one that has already been
1280 // generated.
1281 void Flush(RegExpCompiler* compiler, RegExpNode* successor);
1282 intptr_t cp_offset() { return cp_offset_; }
1283 DeferredAction* actions() { return actions_; }
1284 // A trivial trace is one that has no deferred actions or other state that
1285 // affects the assumptions used when generating code. There is no recorded
1286 // backtrack location in a trivial trace, so with a trivial trace we will
1287 // generate code that, on a failure to match, gets the backtrack location
1288 // from the backtrack stack rather than using a direct jump instruction. We
1289 // always start code generation with a trivial trace and non-trivial traces
1290 // are created as we emit code for nodes or add to the list of deferred
1291 // actions in the trace. The location of the code generated for a node using
1292 // a trivial trace is recorded in a label in the node so that gotos can be
1293 // generated to that code.
1294 bool is_trivial() {
1295 return backtrack_ == NULL && actions_ == NULL && cp_offset_ == 0 &&
1296 characters_preloaded_ == 0 && bound_checked_up_to_ == 0 &&
1297 quick_check_performed_.characters() == 0 && at_start_ == UNKNOWN;
1298 }
1299 TriBool at_start() { return at_start_; }
1300 void set_at_start(TriBool at_start) { at_start_ = at_start; }
1301 BlockLabel* backtrack() { return backtrack_; }
1302 BlockLabel* loop_label() { return loop_label_; }
1303 RegExpNode* stop_node() { return stop_node_; }
1304 intptr_t characters_preloaded() { return characters_preloaded_; }
1305 intptr_t bound_checked_up_to() { return bound_checked_up_to_; }
1306 intptr_t flush_budget() { return flush_budget_; }
1307 QuickCheckDetails* quick_check_performed() { return &quick_check_performed_; }
1308 bool mentions_reg(intptr_t reg);
1309 // Returns true if a deferred position store exists to the specified
1310 // register and stores the offset in the out-parameter. Otherwise
1311 // returns false.
1312 bool GetStoredPosition(intptr_t reg, intptr_t* cp_offset);
1313 // These set methods and AdvanceCurrentPositionInTrace should be used only on
1314 // new traces - the intention is that traces are immutable after creation.
1315 void add_action(DeferredAction* new_action) {
1316 ASSERT(new_action->next_ == NULL);
1317 new_action->next_ = actions_;
1318 actions_ = new_action;
1319 }
1320 void set_backtrack(BlockLabel* backtrack) { backtrack_ = backtrack; }
1321 void set_stop_node(RegExpNode* node) { stop_node_ = node; }
1322 void set_loop_label(BlockLabel* label) { loop_label_ = label; }
1323 void set_characters_preloaded(intptr_t count) {
1324 characters_preloaded_ = count;
1325 }
1326 void set_bound_checked_up_to(intptr_t to) { bound_checked_up_to_ = to; }
1327 void set_flush_budget(intptr_t to) { flush_budget_ = to; }
1328 void set_quick_check_performed(QuickCheckDetails* d) {
1329 quick_check_performed_ = *d;
1330 }
1331 void InvalidateCurrentCharacter();
1332 void AdvanceCurrentPositionInTrace(intptr_t by, RegExpCompiler* compiler);
1333
1334 private:
1335 intptr_t FindAffectedRegisters(OutSet* affected_registers, Zone* zone);
1336 void PerformDeferredActions(RegExpMacroAssembler* macro,
1337 intptr_t max_register,
1338 const OutSet& affected_registers,
1339 OutSet* registers_to_pop,
1340 OutSet* registers_to_clear,
1341 Zone* zone);
1342 void RestoreAffectedRegisters(RegExpMacroAssembler* macro,
1343 intptr_t max_register,
1344 const OutSet& registers_to_pop,
1345 const OutSet& registers_to_clear);
1346 intptr_t cp_offset_;
1347 DeferredAction* actions_;
1348 BlockLabel* backtrack_;
1349 RegExpNode* stop_node_;
1350 BlockLabel* loop_label_;
1351 intptr_t characters_preloaded_;
1352 intptr_t bound_checked_up_to_;
1353 QuickCheckDetails quick_check_performed_;
1354 intptr_t flush_budget_;
1355 TriBool at_start_;
1356
1357 DISALLOW_ALLOCATION();
1358};
1359
1360class GreedyLoopState {
1361 public:
1362 explicit GreedyLoopState(bool not_at_start);
1363
1364 BlockLabel* label() { return &label_; }
1365 Trace* counter_backtrack_trace() { return &counter_backtrack_trace_; }
1366
1367 private:
1368 BlockLabel label_;
1369 Trace counter_backtrack_trace_;
1370};
1371
1372struct PreloadState {
1373 static const intptr_t kEatsAtLeastNotYetInitialized = -1;
1374 bool preload_is_current_;
1375 bool preload_has_checked_bounds_;
1376 intptr_t preload_characters_;
1377 intptr_t eats_at_least_;
1378 void init() { eats_at_least_ = kEatsAtLeastNotYetInitialized; }
1379
1380 DISALLOW_ALLOCATION();
1381};
1382
1383class NodeVisitor : public ValueObject {
1384 public:
1385 virtual ~NodeVisitor() {}
1386#define DECLARE_VISIT(Type) virtual void Visit##Type(Type##Node* that) = 0;
1387 FOR_EACH_NODE_TYPE(DECLARE_VISIT)
1388#undef DECLARE_VISIT
1389 virtual void VisitLoopChoice(LoopChoiceNode* that) { VisitChoice(that); }
1390};
1391
1392// Assertion propagation moves information about assertions such as
1393// \b to the affected nodes. For instance, in /.\b./ information must
1394// be propagated to the first '.' that whatever follows needs to know
1395// if it matched a word or a non-word, and to the second '.' that it
1396// has to check if it succeeds a word or non-word. In this case the
1397// result will be something like:
1398//
1399// +-------+ +------------+
1400// | . | | . |
1401// +-------+ ---> +------------+
1402// | word? | | check word |
1403// +-------+ +------------+
1404class Analysis : public NodeVisitor {
1405 public:
1406 explicit Analysis(bool is_one_byte)
1407 : is_one_byte_(is_one_byte), error_message_(NULL) {}
1408 void EnsureAnalyzed(RegExpNode* node);
1409
1410#define DECLARE_VISIT(Type) virtual void Visit##Type(Type##Node* that);
1411 FOR_EACH_NODE_TYPE(DECLARE_VISIT)
1412#undef DECLARE_VISIT
1413 virtual void VisitLoopChoice(LoopChoiceNode* that);
1414
1415 bool has_failed() { return error_message_ != NULL; }
1416 const char* error_message() {
1417 ASSERT(error_message_ != NULL);
1418 return error_message_;
1419 }
1420 void fail(const char* error_message) { error_message_ = error_message; }
1421
1422 private:
1423 bool is_one_byte_;
1424 const char* error_message_;
1425
1426 DISALLOW_IMPLICIT_CONSTRUCTORS(Analysis);
1427};
1428
1429struct RegExpCompileData : public ZoneAllocated {
1430 RegExpCompileData()
1431 : tree(NULL),
1432 node(NULL),
1433 simple(true),
1434 contains_anchor(false),
1435 capture_name_map(Array::Handle(Array::null())),
1436 error(String::Handle(String::null())),
1437 capture_count(0) {}
1438 RegExpTree* tree;
1439 RegExpNode* node;
1440 bool simple;
1441 bool contains_anchor;
1442 Array& capture_name_map;
1443 String& error;
1444 intptr_t capture_count;
1445};
1446
1447class RegExpEngine : public AllStatic {
1448 public:
1449 struct CompilationResult {
1450 explicit CompilationResult(const char* error_message)
1451 : error_message(error_message),
1452#if !defined(DART_PRECOMPILED_RUNTIME)
1453 backtrack_goto(NULL),
1454 graph_entry(NULL),
1455 num_blocks(-1),
1456 num_stack_locals(-1),
1457#endif
1458 bytecode(NULL),
1459 num_registers(-1) {
1460 }
1461
1462 CompilationResult(TypedData* bytecode, intptr_t num_registers)
1463 : error_message(NULL),
1464#if !defined(DART_PRECOMPILED_RUNTIME)
1465 backtrack_goto(NULL),
1466 graph_entry(NULL),
1467 num_blocks(-1),
1468 num_stack_locals(-1),
1469#endif
1470 bytecode(bytecode),
1471 num_registers(num_registers) {
1472 }
1473
1474#if !defined(DART_PRECOMPILED_RUNTIME)
1475 CompilationResult(IndirectGotoInstr* backtrack_goto,
1476 GraphEntryInstr* graph_entry,
1477 intptr_t num_blocks,
1478 intptr_t num_stack_locals,
1479 intptr_t num_registers)
1480 : error_message(NULL),
1481 backtrack_goto(backtrack_goto),
1482 graph_entry(graph_entry),
1483 num_blocks(num_blocks),
1484 num_stack_locals(num_stack_locals),
1485 bytecode(NULL) {}
1486#endif
1487
1488 const char* error_message;
1489
1490 NOT_IN_PRECOMPILED(IndirectGotoInstr* backtrack_goto);
1491 NOT_IN_PRECOMPILED(GraphEntryInstr* graph_entry);
1492 NOT_IN_PRECOMPILED(const intptr_t num_blocks);
1493 NOT_IN_PRECOMPILED(const intptr_t num_stack_locals);
1494
1495 TypedData* bytecode;
1496 intptr_t num_registers;
1497 };
1498
1499#if !defined(DART_PRECOMPILED_RUNTIME)
1500 static CompilationResult CompileIR(
1501 RegExpCompileData* input,
1502 const ParsedFunction* parsed_function,
1503 const ZoneGrowableArray<const ICData*>& ic_data_array,
1504 intptr_t osr_id);
1505#endif
1506
1507 static CompilationResult CompileBytecode(RegExpCompileData* data,
1508 const RegExp& regexp,
1509 bool is_one_byte,
1510 bool sticky,
1511 Zone* zone);
1512
1513 static RegExpPtr CreateRegExp(Thread* thread,
1514 const String& pattern,
1515 RegExpFlags flags);
1516
1517 static void DotPrint(const char* label, RegExpNode* node, bool ignore_case);
1518};
1519
1520} // namespace dart
1521
1522#endif // RUNTIME_VM_REGEXP_H_
1523