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