Experimental support for RegExp lookbehind.

src/regexp/jsregexp.h

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef V8_REGEXP_JSREGEXP_H_
 #define V8_REGEXP_JSREGEXP_H_
 
 #include "src/allocation.h"
 #include "src/assembler.h"
 
@@ skipping 369 matching lines @@
 
 #define FOR_EACH_NODE_TYPE(VISIT)                                    \
   VISIT(End)                                                         \
   VISIT(Action)                                                      \
   VISIT(Choice)                                                      \
   VISIT(BackReference)                                               \
   VISIT(Assertion)                                                   \
   VISIT(Text)
 
 
-#define FOR_EACH_REG_EXP_TREE_TYPE(VISIT)                            \
-  VISIT(Disjunction)                                                 \
-  VISIT(Alternative)                                                 \
-  VISIT(Assertion)                                                   \
-  VISIT(CharacterClass)                                              \
-  VISIT(Atom)                                                        \
-  VISIT(Quantifier)                                                  \
-  VISIT(Capture)                                                     \
-  VISIT(Lookahead)                                                   \
-  VISIT(BackReference)                                               \
-  VISIT(Empty)                                                       \
+#define FOR_EACH_REG_EXP_TREE_TYPE(VISIT) \
+  VISIT(Disjunction)                      \
+  VISIT(Alternative)                      \
+  VISIT(Assertion)                        \
+  VISIT(CharacterClass)                   \
+  VISIT(Atom)                             \
+  VISIT(Quantifier)                       \
+  VISIT(Capture)                          \
+  VISIT(Lookaround)                       \
+  VISIT(BackReference)                    \
+  VISIT(Empty)                            \
   VISIT(Text)
 
 
 #define FORWARD_DECLARE(Name) class RegExp##Name;
 FOR_EACH_REG_EXP_TREE_TYPE(FORWARD_DECLARE)
 #undef FORWARD_DECLARE
 
 
 class TextElement final BASE_EMBEDDED {
  public:
@@ skipping 185 matching lines @@
                       QuickCheckDetails* details_return,
                       bool fall_through_on_failure);
   // For a given number of characters this returns a mask and a value.  The
   // next n characters are anded with the mask and compared with the value.
   // A comparison failure indicates the node cannot match the next n characters.
   // A comparison success indicates the node may match.
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
                                     int characters_filled_in,
                                     bool not_at_start) = 0;
-  static const int kNodeIsTooComplexForGreedyLoops = -1;
+  static const int kNodeIsTooComplexForGreedyLoops = kMinInt;
   virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; }
   // Only returns the successor for a text node of length 1 that matches any
   // character and that has no guards on it.
   virtual RegExpNode* GetSuccessorOfOmnivorousTextNode(
       RegExpCompiler* compiler) {
     return NULL;
   }
 
   // Collects information on the possible code units (mod 128) that can match if
   // we look forward.  This is used for a Boyer-Moore-like string searching
@@ skipping 203 matching lines @@
   ActionNode(ActionType action_type, RegExpNode* on_success)
       : SeqRegExpNode(on_success),
         action_type_(action_type) { }
   ActionType action_type_;
   friend class DotPrinter;
 };
 
 
 class TextNode: public SeqRegExpNode {
  public:
-  TextNode(ZoneList<TextElement>* elms,
+  TextNode(ZoneList<TextElement>* elms, bool read_backward,
+           RegExpNode* on_success)
+      : SeqRegExpNode(on_success), elms_(elms), read_backward_(read_backward) {}
+  TextNode(RegExpCharacterClass* that, bool read_backward,
            RegExpNode* on_success)
       : SeqRegExpNode(on_success),
-        elms_(elms) { }
-  TextNode(RegExpCharacterClass* that,
-           RegExpNode* on_success)
-      : SeqRegExpNode(on_success),
-        elms_(new(zone()) ZoneList<TextElement>(1, zone())) {
+        elms_(new (zone()) ZoneList<TextElement>(1, zone())),
+        read_backward_(read_backward) {
     elms_->Add(TextElement::CharClass(that), zone());
   }
   virtual void Accept(NodeVisitor* visitor);
   virtual void Emit(RegExpCompiler* compiler, Trace* trace);
   virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start);
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
                                     int characters_filled_in,
                                     bool not_at_start);
   ZoneList<TextElement>* elements() { return elms_; }
+  bool read_backward() { return read_backward_; }
   void MakeCaseIndependent(Isolate* isolate, bool is_one_byte);
   virtual int GreedyLoopTextLength();
   virtual RegExpNode* GetSuccessorOfOmnivorousTextNode(
       RegExpCompiler* compiler);
   virtual void FillInBMInfo(Isolate* isolate, int offset, int budget,
                             BoyerMooreLookahead* bm, bool not_at_start);
   void CalculateOffsets();
   virtual RegExpNode* FilterOneByte(int depth, bool ignore_case);
 
  private:
   enum TextEmitPassType {
     NON_LATIN1_MATCH,            // Check for characters that can't match.
     SIMPLE_CHARACTER_MATCH,      // Case-dependent single character check.
     NON_LETTER_CHARACTER_MATCH,  // Check characters that have no case equivs.
     CASE_CHARACTER_MATCH,        // Case-independent single character check.
     CHARACTER_CLASS_MATCH        // Character class.
   };
   static bool SkipPass(int pass, bool ignore_case);
   static const int kFirstRealPass = SIMPLE_CHARACTER_MATCH;
   static const int kLastPass = CHARACTER_CLASS_MATCH;
   void TextEmitPass(RegExpCompiler* compiler,
                     TextEmitPassType pass,
                     bool preloaded,
                     Trace* trace,
                     bool first_element_checked,
                     int* checked_up_to);
   int Length();
   ZoneList<TextElement>* elms_;
+  bool read_backward_;
 };
 
 
 class AssertionNode: public SeqRegExpNode {
  public:
   enum AssertionType {
     AT_END,
     AT_START,
     AT_BOUNDARY,
     AT_NON_BOUNDARY,
@@ skipping 32 matching lines @@
                            Trace* trace,
                            IfPrevious backtrack_if_previous);
   AssertionNode(AssertionType t, RegExpNode* on_success)
       : SeqRegExpNode(on_success), assertion_type_(t) { }
   AssertionType assertion_type_;
 };
 
 
 class BackReferenceNode: public SeqRegExpNode {
  public:
-  BackReferenceNode(int start_reg,
-                    int end_reg,
+  BackReferenceNode(int start_reg, int end_reg, bool read_backward,
                     RegExpNode* on_success)
       : SeqRegExpNode(on_success),
         start_reg_(start_reg),
-        end_reg_(end_reg) { }
+        end_reg_(end_reg),
+        read_backward_(read_backward) {}
   virtual void Accept(NodeVisitor* visitor);
   int start_register() { return start_reg_; }
   int end_register() { return end_reg_; }
+  bool read_backward() { return read_backward_; }
   virtual void Emit(RegExpCompiler* compiler, Trace* trace);
   virtual int EatsAtLeast(int still_to_find,
                           int recursion_depth,
                           bool not_at_start);
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
                                     int characters_filled_in,
                                     bool not_at_start) {
     return;
   }
   virtual void FillInBMInfo(Isolate* isolate, int offset, int budget,
                             BoyerMooreLookahead* bm, bool not_at_start);
 
  private:
   int start_reg_;
   int end_reg_;
+  bool read_backward_;
 };
 
 
 class EndNode: public RegExpNode {
  public:
   enum Action { ACCEPT, BACKTRACK, NEGATIVE_SUBMATCH_SUCCESS };
   explicit EndNode(Action action, Zone* zone)
       : RegExpNode(zone), action_(action) { }
   virtual void Accept(NodeVisitor* visitor);
   virtual void Emit(RegExpCompiler* compiler, Trace* trace);
@@ skipping 104 matching lines @@
                             BoyerMooreLookahead* bm, bool not_at_start);
 
   bool being_calculated() { return being_calculated_; }
   bool not_at_start() { return not_at_start_; }
   void set_not_at_start() { not_at_start_ = true; }
   void set_being_calculated(bool b) { being_calculated_ = b; }
   virtual bool try_to_emit_quick_check_for_alternative(bool is_first) {
     return true;
   }
   virtual RegExpNode* FilterOneByte(int depth, bool ignore_case);
+  virtual bool read_backward() { return false; }
 
  protected:
   int GreedyLoopTextLengthForAlternative(GuardedAlternative* alternative);
   ZoneList<GuardedAlternative>* alternatives_;
 
  private:
   friend class DispatchTableConstructor;
   friend class Analysis;
   void GenerateGuard(RegExpMacroAssembler* macro_assembler,
                      Guard* guard,
@@ skipping 56 matching lines @@
   // part in that calculation (EatsAtLeast) so the assumptions don't hold.
   virtual bool try_to_emit_quick_check_for_alternative(bool is_first) {
     return !is_first;
   }
   virtual RegExpNode* FilterOneByte(int depth, bool ignore_case);
 };
 
 
 class LoopChoiceNode: public ChoiceNode {
  public:
-  explicit LoopChoiceNode(bool body_can_be_zero_length, Zone* zone)
+  LoopChoiceNode(bool body_can_be_zero_length, bool read_backward, Zone* zone)
       : ChoiceNode(2, zone),
         loop_node_(NULL),
         continue_node_(NULL),
-        body_can_be_zero_length_(body_can_be_zero_length)
-        { }
+        body_can_be_zero_length_(body_can_be_zero_length),
+        read_backward_(read_backward) {}
   void AddLoopAlternative(GuardedAlternative alt);
   void AddContinueAlternative(GuardedAlternative alt);
   virtual void Emit(RegExpCompiler* compiler, Trace* trace);
   virtual int EatsAtLeast(int still_to_find,  int budget, bool not_at_start);
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
                                     int characters_filled_in,
                                     bool not_at_start);
   virtual void FillInBMInfo(Isolate* isolate, int offset, int budget,
                             BoyerMooreLookahead* bm, bool not_at_start);
   RegExpNode* loop_node() { return loop_node_; }
   RegExpNode* continue_node() { return continue_node_; }
   bool body_can_be_zero_length() { return body_can_be_zero_length_; }
+  virtual bool read_backward() { return read_backward_; }
   virtual void Accept(NodeVisitor* visitor);
   virtual RegExpNode* FilterOneByte(int depth, bool ignore_case);
 
  private:
   // AddAlternative is made private for loop nodes because alternatives
   // should not be added freely, we need to keep track of which node
   // goes back to the node itself.
   void AddAlternative(GuardedAlternative node) {
     ChoiceNode::AddAlternative(node);
   }
 
   RegExpNode* loop_node_;
   RegExpNode* continue_node_;
   bool body_can_be_zero_length_;
+  bool read_backward_;
 };
 
 
 // Improve the speed that we scan for an initial point where a non-anchored
 // regexp can match by using a Boyer-Moore-like table. This is done by
 // identifying non-greedy non-capturing loops in the nodes that eat any
 // character one at a time.  For example in the middle of the regexp
 // /foo[\s\S]*?bar/ we find such a loop.  There is also such a loop implicitly
 // inserted at the start of any non-anchored regexp.
 //
@@ skipping 235 matching lines @@
   bool is_trivial() {
     return backtrack_ == NULL &&
            actions_ == NULL &&
            cp_offset_ == 0 &&
            characters_preloaded_ == 0 &&
            bound_checked_up_to_ == 0 &&
            quick_check_performed_.characters() == 0 &&
            at_start_ == UNKNOWN;
   }
   TriBool at_start() { return at_start_; }
-  void set_at_start(bool at_start) {
-    at_start_ = at_start ? TRUE_VALUE : FALSE_VALUE;
-  }
+  void set_at_start(TriBool at_start) { at_start_ = at_start; }
   Label* backtrack() { return backtrack_; }
   Label* loop_label() { return loop_label_; }
   RegExpNode* stop_node() { return stop_node_; }
   int characters_preloaded() { return characters_preloaded_; }
   int bound_checked_up_to() { return bound_checked_up_to_; }
   int flush_budget() { return flush_budget_; }
   QuickCheckDetails* quick_check_performed() { return &quick_check_performed_; }
   bool mentions_reg(int reg);
   // Returns true if a deferred position store exists to the specified
   // register and stores the offset in the out-parameter.  Otherwise
@@ skipping 226 matching lines @@
   static const int kStringOffset = 0;
   static const int kPatternOffset = 1;
   static const int kArrayOffset = 2;
   static const int kLastMatchOffset = 3;
 };
 
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_REGEXP_JSREGEXP_H_