Irregexp:...

src/jsregexp.h

 // Copyright 2006-2008 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 328 matching lines @@
   // The successors are a list of sets that contain the same values
   // as this set and the one more value that is not present in this
   // set.
   ZoneList<OutSet*>* successors() { return successors_; }
 
   OutSet(uint32_t first, ZoneList<unsigned>* remaining)
       : first_(first), remaining_(remaining), successors_(NULL) { }
   uint32_t first_;
   ZoneList<unsigned>* remaining_;
   ZoneList<OutSet*>* successors_;
+  friend class GenerationVariant;
 };
 
 
 // A mapping from integers, specified as ranges, to a set of integers.
 // Used for mapping character ranges to choices.
 class DispatchTable : public ZoneObject {
  public:
   class Entry {
    public:
     Entry() : from_(0), to_(0), out_set_(NULL) { }
@@ skipping 66 matching lines @@
 
 #define FORWARD_DECLARE(Name) class RegExp##Name;
 FOR_EACH_REG_EXP_TREE_TYPE(FORWARD_DECLARE)
 #undef FORWARD_DECLARE
 
 
 class TextElement {
  public:
   enum Type {UNINITIALIZED, ATOM, CHAR_CLASS};
   TextElement() : type(UNINITIALIZED) { }
-  explicit TextElement(Type t) : type(t) { }
+  explicit TextElement(Type t) : type(t), cp_offset(-1) { }
   static TextElement Atom(RegExpAtom* atom);
   static TextElement CharClass(RegExpCharacterClass* char_class);
   Type type;
   union {
     RegExpAtom* u_atom;
     RegExpCharacterClass* u_char_class;
   } data;
+  int cp_offset;
 };
 
 
+class GenerationVariant;
+
+
 struct NodeInfo {
   enum TriBool {
     UNKNOWN = -1, FALSE = 0, TRUE = 1
   };
 
   NodeInfo()
       : being_analyzed(false),
         been_analyzed(false),
         being_expanded(false),
         been_expanded(false),
@@ skipping 144 matching lines @@
   }
   void Add(RegExpNode* node) { list_->Add(node); }
   RegExpNode* Get(int index) { return list_->at(index); }
  private:
   ZoneList<RegExpNode*>* list_;
 };
 
 
 class RegExpNode: public ZoneObject {
  public:
+  RegExpNode() : variants_generated_(0) { }
   virtual ~RegExpNode() { }
   virtual void Accept(NodeVisitor* visitor) = 0;
   // Generates a goto to this node or actually generates the code at this point.
   // Until the implementation is complete we will return true for success and
   // false for failure.
-  virtual bool GoTo(RegExpCompiler* compiler);
-  Label* label();
-
-  // Until the implementation is complete we will return true for success and
-  // false for failure.
-  virtual bool Emit(RegExpCompiler* compiler) = 0;
+  virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant) = 0;
+  static const int kNodeIsTooComplexForGreedyLoops = -1;
+  virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; }
+  Label* label() { return &label_; }
+  static const int kMaxVariantsGenerated = 10;
 
   RegExpNode* EnsureExpanded(NodeInfo* info);
   virtual RegExpNode* ExpandLocal(NodeInfo* info) = 0;
   virtual void ExpandChildren() = 0;
 
   // Propagates the given interest information forward.  When seeing
   // \bfoo for instance, the \b is implemented by propagating forward
   // to the 'foo' string that it should only succeed if its first
   // character is a letter xor the previous character was a letter.
   virtual RegExpNode* PropagateForward(NodeInfo* info) = 0;
 
   NodeInfo* info() { return &info_; }
-  virtual bool IsBacktrack() { return false; }
 
   void AddSibling(RegExpNode* node) { siblings_.Add(node); }
 
   // Static version of EnsureSibling that expresses the fact that the
   // result has the same type as the input.
   template <class C>
   static C* EnsureSibling(C* node, NodeInfo* info, bool* cloned) {
     return static_cast<C*>(node->EnsureSibling(info, cloned));
   }
 
   SiblingList* siblings() { return &siblings_; }
   void set_siblings(SiblingList* other) { siblings_ = *other; }
 
  protected:
+  enum LimitResult { DONE, FAIL, CONTINUE };
+  LimitResult LimitVersions(RegExpCompiler* compiler,
+                            GenerationVariant* variant);
 
   // Returns a sibling of this node whose interests and assumptions
   // match the ones in the given node info.  If no sibling exists NULL
   // is returned.
   RegExpNode* TryGetSibling(NodeInfo* info);
 
   // Returns a sibling of this node whose interests match the ones in
   // the given node info.  The info must not contain any assertions.
   // If no node exists a new one will be created by cloning the current
   // node.  The result will always be an instance of the same concrete
   // class as this node.
   RegExpNode* EnsureSibling(NodeInfo* info, bool* cloned);
 
   // Returns a clone of this node initialized using the copy constructor
   // of its concrete class.  Note that the node may have to be pre-
   // processed before it is on a useable state.
   virtual RegExpNode* Clone() = 0;
 
-  inline void Bind(RegExpMacroAssembler* macro);
-
  private:
   Label label_;
   NodeInfo info_;
   SiblingList siblings_;
+  int variants_generated_;
 };
 
 
 class SeqRegExpNode: public RegExpNode {
  public:
   explicit SeqRegExpNode(RegExpNode* on_success)
       : on_success_(on_success) { }
   RegExpNode* on_success() { return on_success_; }
   void set_on_success(RegExpNode* node) { on_success_ = node; }
-  virtual bool Emit(RegExpCompiler* compiler) { return false; }
  private:
   RegExpNode* on_success_;
 };
 
 
 class ActionNode: public SeqRegExpNode {
  public:
   enum Type {
-    STORE_REGISTER,
+    SET_REGISTER,
     INCREMENT_REGISTER,
     STORE_POSITION,
-    RESTORE_POSITION,
     BEGIN_SUBMATCH,
-    ESCAPE_SUBMATCH
+    POSITIVE_SUBMATCH_SUCCESS
   };
-  static ActionNode* StoreRegister(int reg, int val, RegExpNode* on_success);
+  static ActionNode* SetRegister(int reg, int val, RegExpNode* on_success);
   static ActionNode* IncrementRegister(int reg, RegExpNode* on_success);
   static ActionNode* StorePosition(int reg, RegExpNode* on_success);
-  static ActionNode* RestorePosition(int reg, RegExpNode* on_success);
-  static ActionNode* BeginSubmatch(int stack_pointer_reg,
-                                   int position_reg,
-                                   RegExpNode* on_success);
-  static ActionNode* EscapeSubmatch(int stack_pointer_reg,
-                                    bool and_restore_position,
-                                    int restore_reg,
-                                    RegExpNode* on_success);
+  static ActionNode* BeginSubmatch(
+      int stack_pointer_reg,
+      int position_reg,
+      RegExpNode* on_success);
+  static ActionNode* PositiveSubmatchSuccess(
+      int stack_pointer_reg,
+      int restore_reg,
+      RegExpNode* on_success);
   virtual void Accept(NodeVisitor* visitor);
-  virtual bool Emit(RegExpCompiler* compiler);
+  virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant);
   virtual RegExpNode* ExpandLocal(NodeInfo* info);
   virtual void ExpandChildren();
   virtual RegExpNode* PropagateForward(NodeInfo* info);
+  Type type() { return type_; }
+  // TODO(erikcorry): We should allow some action nodes in greedy loops.
+  virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; }
   virtual ActionNode* Clone() { return new ActionNode(*this); }
 
  private:
   union {
     struct {
       int reg;
       int value;
     } u_store_register;
     struct {
       int reg;
@@ skipping 10 matching lines @@
       : SeqRegExpNode(on_success),
         type_(type) { }
   Type type_;
   friend class DotPrinter;
 };
 
 
 class TextNode: public SeqRegExpNode {
  public:
   TextNode(ZoneList<TextElement>* elms,
-           RegExpNode* on_success,
-           RegExpNode* on_failure)
+           RegExpNode* on_success)
       : SeqRegExpNode(on_success),
-        on_failure_(on_failure),
         elms_(elms) { }
   TextNode(RegExpCharacterClass* that,
-           RegExpNode* on_success,
-           RegExpNode* on_failure)
+           RegExpNode* on_success)
       : SeqRegExpNode(on_success),
-        on_failure_(on_failure),
         elms_(new ZoneList<TextElement>(1)) {
     elms_->Add(TextElement::CharClass(that));
   }
   virtual void Accept(NodeVisitor* visitor);
   virtual RegExpNode* PropagateForward(NodeInfo* info);
   virtual RegExpNode* ExpandLocal(NodeInfo* info);
   virtual void ExpandChildren();
-  RegExpNode* on_failure() { return on_failure_; }
-  virtual bool Emit(RegExpCompiler* compiler);
+  virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant);
   ZoneList<TextElement>* elements() { return elms_; }
   void MakeCaseIndependent();
-  virtual TextNode* Clone() { return new TextNode(*this); }
-
+  virtual int GreedyLoopTextLength();
+  virtual TextNode* Clone() {
+    TextNode* result = new TextNode(*this);
+    result->CalculateOffsets();
+    return result;
+  }
+  void CalculateOffsets();
  private:
   void ExpandAtomChildren(RegExpAtom* that);
   void ExpandCharClassChildren(RegExpCharacterClass* that);
 
-  RegExpNode* on_failure_;
   ZoneList<TextElement>* elms_;
 };
 
 
 class BackReferenceNode: public SeqRegExpNode {
  public:
   BackReferenceNode(int start_reg,
                     int end_reg,
-                    RegExpNode* on_success,
-                    RegExpNode* on_failure)
+                    RegExpNode* on_success)
       : SeqRegExpNode(on_success),
-        on_failure_(on_failure),
         start_reg_(start_reg),
         end_reg_(end_reg) { }
   virtual void Accept(NodeVisitor* visitor);
-  RegExpNode* on_failure() { return on_failure_; }
   int start_register() { return start_reg_; }
   int end_register() { return end_reg_; }
-  virtual bool Emit(RegExpCompiler* compiler);
+  virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant);
   virtual RegExpNode* PropagateForward(NodeInfo* info);
   virtual RegExpNode* ExpandLocal(NodeInfo* info);
   virtual void ExpandChildren();
   virtual BackReferenceNode* Clone() { return new BackReferenceNode(*this); }
 
  private:
-  RegExpNode* on_failure_;
   int start_reg_;
   int end_reg_;
 };
 
 
 class EndNode: public RegExpNode {
  public:
-  enum Action { ACCEPT, BACKTRACK };
+  enum Action { ACCEPT, BACKTRACK, NEGATIVE_SUBMATCH_SUCCESS };
   explicit EndNode(Action action) : action_(action) { }
   virtual void Accept(NodeVisitor* visitor);
-  virtual bool Emit(RegExpCompiler* compiler);
+  virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant);
   virtual RegExpNode* PropagateForward(NodeInfo* info);
   virtual RegExpNode* ExpandLocal(NodeInfo* info);
   virtual void ExpandChildren();
-  virtual bool IsBacktrack() { return action_ == BACKTRACK; }
-  virtual bool GoTo(RegExpCompiler* compiler);
   virtual EndNode* Clone() { return new EndNode(*this); }
 
+ protected:
+  void EmitInfoChecks(RegExpMacroAssembler* macro, GenerationVariant* variant);
+
  private:
   Action action_;
 };
 
 
+class NegativeSubmatchSuccess: public EndNode {
+ public:
+  NegativeSubmatchSuccess(int stack_pointer_reg, int position_reg)
+      : EndNode(NEGATIVE_SUBMATCH_SUCCESS),
+        stack_pointer_register_(stack_pointer_reg),
+        current_position_register_(position_reg) { }
+  virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant);
+
+ private:
+  int stack_pointer_register_;
+  int current_position_register_;
+};
+
+
 class Guard: public ZoneObject {
  public:
   enum Relation { LT, GEQ };
   Guard(int reg, Relation op, int value)
       : reg_(reg),
         op_(op),
         value_(value) { }
   int reg() { return reg_; }
   Relation op() { return op_; }
   int value() { return value_; }
@@ skipping 14 matching lines @@
   ZoneList<Guard*>* guards() { return guards_; }
 
  private:
   RegExpNode* node_;
   ZoneList<Guard*>* guards_;
 };
 
 
 class ChoiceNode: public RegExpNode {
  public:
-  explicit ChoiceNode(int expected_size, RegExpNode* on_failure)
-      : on_failure_(on_failure),
-        alternatives_(new ZoneList<GuardedAlternative>(expected_size)),
+  explicit ChoiceNode(int expected_size)
+      : alternatives_(new ZoneList<GuardedAlternative>(expected_size)),
         table_(NULL),
         being_calculated_(false) { }
   virtual void Accept(NodeVisitor* visitor);
   void AddAlternative(GuardedAlternative node) { alternatives()->Add(node); }
   ZoneList<GuardedAlternative>* alternatives() { return alternatives_; }
   DispatchTable* GetTable(bool ignore_case);
-  RegExpNode* on_failure() { return on_failure_; }
-  virtual bool Emit(RegExpCompiler* compiler);
+  virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant);
   virtual RegExpNode* PropagateForward(NodeInfo* info);
   virtual RegExpNode* ExpandLocal(NodeInfo* info);
   virtual void ExpandChildren();
   virtual ChoiceNode* Clone() { return new ChoiceNode(*this); }
 
   bool being_calculated() { return being_calculated_; }
   void set_being_calculated(bool b) { being_calculated_ = b; }
 
+ protected:
+  int GreedyLoopTextLength(GuardedAlternative *alternative);
+  ZoneList<GuardedAlternative>* alternatives_;
+
  private:
   friend class DispatchTableConstructor;
   friend class Analysis;
   void GenerateGuard(RegExpMacroAssembler* macro_assembler,
                      Guard *guard,
-                     Label* on_failure);
-  RegExpNode* on_failure_;
-  ZoneList<GuardedAlternative>* alternatives_;
+                     GenerationVariant* variant);
   DispatchTable* table_;
   bool being_calculated_;
 };
 
 
+class LoopChoiceNode: public ChoiceNode {
+ public:
+  explicit LoopChoiceNode(int expected_size) : ChoiceNode(expected_size) { }
+  virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant);
+  virtual LoopChoiceNode* Clone() { return new LoopChoiceNode(*this); }
+};
+
+
+// There are many ways to generate code for a node.  This class encapsulates
+// the current way we should be generating.  In other words it encapsulates
+// the current state of the code generator.
+class GenerationVariant {

[Christian Plesner Hansen, 2008/12/08 08:54:19]

Not a fan of this name though I can't think of anything better.

+ public:
+  class DeferredAction {
+   public:
+    DeferredAction(ActionNode::Type type, int reg)
+        : type_(type), reg_(reg), next_(NULL) { }
+    DeferredAction* next() { return next_; }
+    int reg() { return reg_; }
+    ActionNode::Type type() { return type_; }
+   private:
+    ActionNode::Type type_;
+    int reg_;
+    DeferredAction* next_;
+    friend class GenerationVariant;
+  };
+
+  class DeferredCapture: public DeferredAction {
+   public:
+    DeferredCapture(int reg, GenerationVariant* variant)
+        : DeferredAction(ActionNode::STORE_POSITION, reg),
+          cp_offset_(variant->cp_offset()) { }
+    int cp_offset() { return cp_offset_; }
+   private:
+    int cp_offset_;
+    void set_cp_offset(int cp_offset) { cp_offset_ = cp_offset; }
+  };
+
+  class DeferredSetRegister :public DeferredAction {
+   public:
+    DeferredSetRegister(int reg, int value)
+        : DeferredAction(ActionNode::SET_REGISTER, reg),
+          value_(value) { }
+    int value() { return value_; }
+   private:
+    int value_;
+  };
+
+  class DeferredIncrementRegister: public DeferredAction {
+   public:
+    explicit DeferredIncrementRegister(int reg)
+        : DeferredAction(ActionNode::INCREMENT_REGISTER, reg) { }
+  };
+
+  explicit GenerationVariant(Label* backtrack)
+      : cp_offset_(0),
+        actions_(NULL),
+        backtrack_(backtrack),
+        stop_node_(NULL),
+        loop_label_(NULL) { }
+  GenerationVariant()
+      : cp_offset_(0),
+        actions_(NULL),
+        backtrack_(NULL),
+        stop_node_(NULL),
+        loop_label_(NULL) { }
+  bool Flush(RegExpCompiler* compiler, RegExpNode* successor);
+  int cp_offset() { return cp_offset_; }
+  DeferredAction* actions() { return actions_; }
+  bool is_trivial() {
+    return backtrack_ == NULL && actions_ == NULL && cp_offset_ == 0;
+  }
+  Label* backtrack() { return backtrack_; }
+  Label* loop_label() { return loop_label_; }
+  RegExpNode* stop_node() { return stop_node_; }
+  // These set methods should be used only on new GenerationVariants - the
+  // intention is that GenerationVariants are immutable after creation.
+  void add_action(DeferredAction* new_action) {
+    ASSERT(new_action->next_ == NULL);
+    new_action->next_ = actions_;
+    actions_ = new_action;
+  }
+  void set_cp_offset(int new_cp_offset) {
+    ASSERT(new_cp_offset >= cp_offset_);
+    cp_offset_ = new_cp_offset;
+  }
+  void set_backtrack(Label* backtrack) { backtrack_ = backtrack; }
+  void set_stop_node(RegExpNode* node) { stop_node_ = node; }
+  void set_loop_label(Label* label) { loop_label_ = label; }
+  bool mentions_reg(int reg);
+ private:
+  int FindAffectedRegisters(OutSet* affected_registers);
+  void PerformDeferredActions(RegExpMacroAssembler* macro,
+                               int max_register,
+                               OutSet& affected_registers);
+  void RestoreAffectedRegisters(RegExpMacroAssembler* macro,
+                                int max_register,
+                                OutSet& affected_registers);
+  void PushAffectedRegisters(RegExpMacroAssembler* macro,
+                             int max_register,
+                             OutSet& affected_registers);
+  int cp_offset_;
+  DeferredAction* actions_;
+  Label* backtrack_;
+  RegExpNode* stop_node_;
+  Label* loop_label_;
+};
 class NodeVisitor {
  public:
   virtual ~NodeVisitor() { }
 #define DECLARE_VISIT(Type)                                          \
   virtual void Visit##Type(Type##Node* that) = 0;
 FOR_EACH_NODE_TYPE(DECLARE_VISIT)
 #undef DECLARE_VISIT
 };
 
 
@@ skipping 53 matching lines @@
   Handle<String> error;
   int capture_count;
 };
 
 
 class RegExpEngine: public AllStatic {
  public:
   static Handle<FixedArray> Compile(RegExpParseResult* input,
                                     RegExpNode** node_return,
                                     bool ignore_case,
-                                    bool multiline);
+                                    bool multiline,
+                                    Handle<String> pattern);
   static void DotPrint(const char* label, RegExpNode* node, bool ignore_case);
 };
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_JSREGEXP_H_