src/v8/src/jsregexp.h

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