Experimental support for RegExp lookbehind.

src/ast.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_AST_H_
 #define V8_AST_H_
 
 #include "src/assembler.h"
 #include "src/ast-value-factory.h"
 #include "src/bailout-reason.h"
@@ skipping 101 matching lines @@
 
 class RegExpAlternative;
 class RegExpAssertion;
 class RegExpAtom;
 class RegExpBackReference;
 class RegExpCapture;
 class RegExpCharacterClass;
 class RegExpCompiler;
 class RegExpDisjunction;
 class RegExpEmpty;
-class RegExpLookahead;
+class RegExpLookaround;
 class RegExpQuantifier;
 class RegExpText;
 
 #define DEF_FORWARD_DECLARATION(type) class type;
 AST_NODE_LIST(DEF_FORWARD_DECLARATION)
 #undef DEF_FORWARD_DECLARATION
 
 
 // Typedef only introduced to avoid unreadable code.
 typedef ZoneList<Handle<String>> ZoneStringList;
@@ skipping 2692 matching lines @@
   virtual ~RegExpVisitor() { }
 #define MAKE_CASE(Name)                                              \
   virtual void* Visit##Name(RegExp##Name*, void* data) = 0;
   FOR_EACH_REG_EXP_TREE_TYPE(MAKE_CASE)
 #undef MAKE_CASE
 };
 
 
 class RegExpTree : public ZoneObject {
  public:
+  enum ReadDirection { READ_FORWARD, READ_BACKWARD };
+
   static const int kInfinity = kMaxInt;
+  explicit RegExpTree(ReadDirection read_direction)
+      : read_direction_(read_direction) {}
   virtual ~RegExpTree() {}
   virtual void* Accept(RegExpVisitor* visitor, void* data) = 0;
   virtual RegExpNode* ToNode(RegExpCompiler* compiler,
                              RegExpNode* on_success) = 0;
   virtual bool IsTextElement() { return false; }
   virtual bool IsAnchoredAtStart() { return false; }
   virtual bool IsAnchoredAtEnd() { return false; }
   virtual int min_match() = 0;
   virtual int max_match() = 0;
   // Returns the interval of registers used for captures within this
   // expression.
   virtual Interval CaptureRegisters() { return Interval::Empty(); }
   virtual void AppendToText(RegExpText* text, Zone* zone);
   std::ostream& Print(std::ostream& os, Zone* zone);  // NOLINT
 #define MAKE_ASTYPE(Name)                                                  \
   virtual RegExp##Name* As##Name();                                        \
   virtual bool Is##Name();
   FOR_EACH_REG_EXP_TREE_TYPE(MAKE_ASTYPE)
 #undef MAKE_ASTYPE
+
+  ReadDirection read_direction() const { return read_direction_; }
+  bool read_backward() const { return read_direction_ == READ_BACKWARD; }
+
+ protected:
+  ReadDirection read_direction_;
 };
 
 
 class RegExpDisjunction final : public RegExpTree {
  public:
-  explicit RegExpDisjunction(ZoneList<RegExpTree*>* alternatives);
+  RegExpDisjunction(ZoneList<RegExpTree*>* alternatives,
+                    ReadDirection read_direction);
   void* Accept(RegExpVisitor* visitor, void* data) override;
   RegExpNode* ToNode(RegExpCompiler* compiler, RegExpNode* on_success) override;
   RegExpDisjunction* AsDisjunction() override;
   Interval CaptureRegisters() override;
   bool IsDisjunction() override;
   bool IsAnchoredAtStart() override;
   bool IsAnchoredAtEnd() override;
   int min_match() override { return min_match_; }
   int max_match() override { return max_match_; }
   ZoneList<RegExpTree*>* alternatives() { return alternatives_; }
  private:
   bool SortConsecutiveAtoms(RegExpCompiler* compiler);
   void RationalizeConsecutiveAtoms(RegExpCompiler* compiler);
   void FixSingleCharacterDisjunctions(RegExpCompiler* compiler);
   ZoneList<RegExpTree*>* alternatives_;
   int min_match_;
   int max_match_;
 };
 
 
 class RegExpAlternative final : public RegExpTree {
  public:
-  explicit RegExpAlternative(ZoneList<RegExpTree*>* nodes);
+  RegExpAlternative(ZoneList<RegExpTree*>* nodes, ReadDirection read_direction);
   void* Accept(RegExpVisitor* visitor, void* data) override;
   RegExpNode* ToNode(RegExpCompiler* compiler, RegExpNode* on_success) override;
   RegExpAlternative* AsAlternative() override;
   Interval CaptureRegisters() override;
   bool IsAlternative() override;
   bool IsAnchoredAtStart() override;
   bool IsAnchoredAtEnd() override;
   int min_match() override { return min_match_; }
   int max_match() override { return max_match_; }
   ZoneList<RegExpTree*>* nodes() { return nodes_; }
  private:
   ZoneList<RegExpTree*>* nodes_;
   int min_match_;
   int max_match_;
 };
 
 
 class RegExpAssertion final : public RegExpTree {
  public:
   enum AssertionType {
     START_OF_LINE,
     START_OF_INPUT,
     END_OF_LINE,
     END_OF_INPUT,
     BOUNDARY,
     NON_BOUNDARY
   };
-  explicit RegExpAssertion(AssertionType type) : assertion_type_(type) { }
+  RegExpAssertion(AssertionType type, ReadDirection read_direction)
+      : RegExpTree(read_direction), assertion_type_(type) {}
   void* Accept(RegExpVisitor* visitor, void* data) override;
   RegExpNode* ToNode(RegExpCompiler* compiler, RegExpNode* on_success) override;
   RegExpAssertion* AsAssertion() override;
   bool IsAssertion() override;
   bool IsAnchoredAtStart() override;
   bool IsAnchoredAtEnd() override;
   int min_match() override { return 0; }
   int max_match() override { return 0; }
   AssertionType assertion_type() { return assertion_type_; }
  private:
@@ skipping 19 matching lines @@
  private:
   ZoneList<CharacterRange>* ranges_;
   // If non-zero, the value represents a standard set (e.g., all whitespace
   // characters) without having to expand the ranges.
   uc16 standard_set_type_;
 };
 
 
 class RegExpCharacterClass final : public RegExpTree {
  public:
-  RegExpCharacterClass(ZoneList<CharacterRange>* ranges, bool is_negated)
-      : set_(ranges),
-        is_negated_(is_negated) { }
-  explicit RegExpCharacterClass(uc16 type)
-      : set_(type),
-        is_negated_(false) { }
+  RegExpCharacterClass(ZoneList<CharacterRange>* ranges, bool is_negated,
+                       ReadDirection read_direction)
+      : RegExpTree(read_direction), set_(ranges), is_negated_(is_negated) {}
+  RegExpCharacterClass(uc16 type, ReadDirection read_direction)
+      : RegExpTree(read_direction), set_(type), is_negated_(false) {}
   void* Accept(RegExpVisitor* visitor, void* data) override;
   RegExpNode* ToNode(RegExpCompiler* compiler, RegExpNode* on_success) override;
   RegExpCharacterClass* AsCharacterClass() override;
   bool IsCharacterClass() override;
   bool IsTextElement() override { return true; }
   int min_match() override { return 1; }
   int max_match() override { return 1; }
   void AppendToText(RegExpText* text, Zone* zone) override;
   CharacterSet character_set() { return set_; }
   // TODO(lrn): Remove need for complex version if is_standard that
@@ skipping 15 matching lines @@
   bool is_negated() { return is_negated_; }
 
  private:
   CharacterSet set_;
   bool is_negated_;
 };
 
 
 class RegExpAtom final : public RegExpTree {
  public:
-  explicit RegExpAtom(Vector<const uc16> data) : data_(data) { }
+  RegExpAtom(Vector<const uc16> data, ReadDirection read_direction)
+      : RegExpTree(read_direction), data_(data) {}
   void* Accept(RegExpVisitor* visitor, void* data) override;
   RegExpNode* ToNode(RegExpCompiler* compiler, RegExpNode* on_success) override;
   RegExpAtom* AsAtom() override;
   bool IsAtom() override;
   bool IsTextElement() override { return true; }
   int min_match() override { return data_.length(); }
   int max_match() override { return data_.length(); }
   void AppendToText(RegExpText* text, Zone* zone) override;
   Vector<const uc16> data() { return data_; }
   int length() { return data_.length(); }
  private:
   Vector<const uc16> data_;
 };
 
 
 class RegExpText final : public RegExpTree {
  public:
-  explicit RegExpText(Zone* zone) : elements_(2, zone), length_(0) {}
+  RegExpText(Zone* zone, ReadDirection read_direction)
+      : RegExpTree(read_direction), elements_(2, zone), length_(0) {}
   void* Accept(RegExpVisitor* visitor, void* data) override;
   RegExpNode* ToNode(RegExpCompiler* compiler, RegExpNode* on_success) override;
   RegExpText* AsText() override;
   bool IsText() override;
   bool IsTextElement() override { return true; }
   int min_match() override { return length_; }
   int max_match() override { return length_; }
   void AppendToText(RegExpText* text, Zone* zone) override;
   void AddElement(TextElement elm, Zone* zone)  {
     elements_.Add(elm, zone);
     length_ += elm.length();
   }
   ZoneList<TextElement>* elements() { return &elements_; }
  private:
   ZoneList<TextElement> elements_;
   int length_;
 };
 
 
 class RegExpQuantifier final : public RegExpTree {
  public:
   enum QuantifierType { GREEDY, NON_GREEDY, POSSESSIVE };
-  RegExpQuantifier(int min, int max, QuantifierType type, RegExpTree* body)
-      : body_(body),
+  RegExpQuantifier(int min, int max, QuantifierType type, RegExpTree* body,
+                   ReadDirection read_direction)
+      : RegExpTree(read_direction),
+        body_(body),
         min_(min),
         max_(max),
         min_match_(min * body->min_match()),
         quantifier_type_(type) {
     if (max > 0 && body->max_match() > kInfinity / max) {
       max_match_ = kInfinity;
     } else {
       max_match_ = max * body->max_match();
     }
   }
@@ skipping 23 matching lines @@
   int min_;
   int max_;
   int min_match_;
   int max_match_;
   QuantifierType quantifier_type_;
 };
 
 
 class RegExpCapture final : public RegExpTree {
  public:
-  explicit RegExpCapture(RegExpTree* body, int index)
-      : body_(body), index_(index) { }
+  explicit RegExpCapture(int index)
+      : RegExpTree(READ_FORWARD), body_(NULL), index_(index) {}
   void* Accept(RegExpVisitor* visitor, void* data) override;
   RegExpNode* ToNode(RegExpCompiler* compiler, RegExpNode* on_success) override;
   static RegExpNode* ToNode(RegExpTree* body,
                             int index,
                             RegExpCompiler* compiler,
                             RegExpNode* on_success);
   RegExpCapture* AsCapture() override;
   bool IsAnchoredAtStart() override;
   bool IsAnchoredAtEnd() override;
   Interval CaptureRegisters() override;
   bool IsCapture() override;
-  int min_match() override { return body_->min_match(); }
-  int max_match() override { return body_->max_match(); }
+  // If body_ is not yet set, the capture is back referenced but not parsed yet.
+  // In the ordinary case, nothing has been captured yet, so the back reference
+  // must have the length 0.
+  // If the back reference is inside a lookbehind, effectively making it a
+  // forward reference, we return 0 since lookbehinds have a length of 0.
+  int min_match() override { return body_ ? body_->min_match() : 0; }
+  int max_match() override { return body_ ? body_->max_match() : 0; }
   RegExpTree* body() { return body_; }
+  void set_body(RegExpTree* body) { body_ = body; }
+  void set_read_direction(ReadDirection read_direction) {
+    read_direction_ = read_direction;
+  }
   int index() { return index_; }
   static int StartRegister(int index) { return index * 2; }
   static int EndRegister(int index) { return index * 2 + 1; }
 
  private:
   RegExpTree* body_;
   int index_;
 };
 
 
-class RegExpLookahead final : public RegExpTree {
+class RegExpLookaround final : public RegExpTree {
  public:
-  RegExpLookahead(RegExpTree* body,
-                  bool is_positive,
-                  int capture_count,
-                  int capture_from)
-      : body_(body),
+  RegExpLookaround(RegExpTree* body, bool is_positive, int capture_count,
+                   int capture_from, ReadDirection read_direction)
+      : RegExpTree(read_direction),
+        body_(body),
         is_positive_(is_positive),
         capture_count_(capture_count),
-        capture_from_(capture_from) { }
+        capture_from_(capture_from) {}
 
   void* Accept(RegExpVisitor* visitor, void* data) override;
   RegExpNode* ToNode(RegExpCompiler* compiler, RegExpNode* on_success) override;
-  RegExpLookahead* AsLookahead() override;
+  RegExpLookaround* AsLookaround() override;
   Interval CaptureRegisters() override;
-  bool IsLookahead() override;
+  bool IsLookaround() override;
   bool IsAnchoredAtStart() override;
   int min_match() override { return 0; }
   int max_match() override { return 0; }
   RegExpTree* body() { return body_; }
   bool is_positive() { return is_positive_; }
   int capture_count() { return capture_count_; }
   int capture_from() { return capture_from_; }
 
  private:
   RegExpTree* body_;
   bool is_positive_;
   int capture_count_;
   int capture_from_;
 };
 
 
 class RegExpBackReference final : public RegExpTree {
  public:
-  explicit RegExpBackReference(RegExpCapture* capture)
-      : capture_(capture) { }
+  RegExpBackReference(RegExpCapture* capture, ReadDirection read_direction)
+      : RegExpTree(read_direction), capture_(capture) {}
   void* Accept(RegExpVisitor* visitor, void* data) override;
   RegExpNode* ToNode(RegExpCompiler* compiler, RegExpNode* on_success) override;
   RegExpBackReference* AsBackReference() override;
   bool IsBackReference() override;
   int min_match() override { return 0; }
   int max_match() override { return capture_->max_match(); }
   int index() { return capture_->index(); }
   RegExpCapture* capture() { return capture_; }
  private:
   RegExpCapture* capture_;
 };
 
 
 class RegExpEmpty final : public RegExpTree {
  public:
-  RegExpEmpty() { }
+  RegExpEmpty() : RegExpTree(READ_FORWARD) {}
   void* Accept(RegExpVisitor* visitor, void* data) override;
   RegExpNode* ToNode(RegExpCompiler* compiler, RegExpNode* on_success) override;
   RegExpEmpty* AsEmpty() override;
   bool IsEmpty() override;
   int min_match() override { return 0; }
   int max_match() override { return 0; }
 };
 
 
 // ----------------------------------------------------------------------------
@@ skipping 494 matching lines @@
   // the parser-level zone.
   Zone* parser_zone_;
   AstValueFactory* ast_value_factory_;
 };
 
 
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_AST_H_