Experimental: merge from bleeding_edge. Merge up to and including...

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 331 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;
+  friend class Trace;
 };
 
 
 // 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 79 matching lines @@
   int length();
   Type type;
   union {
     RegExpAtom* u_atom;
     RegExpCharacterClass* u_char_class;
   } data;
   int cp_offset;
 };
 
 
-class GenerationVariant;
+class Trace;
 
 
 struct NodeInfo {
   enum TriBool {
     UNKNOWN = -1, FALSE = 0, TRUE = 1
   };
 
   NodeInfo()
       : being_analyzed(false),
         been_analyzed(false),
@@ skipping 113 matching lines @@
   int characters_;
   Position positions_[4];
   // These values are the condensate of the above array after Rationalize().
   uint32_t mask_;
   uint32_t value_;
 };
 
 
 class RegExpNode: public ZoneObject {
  public:
-  RegExpNode() : variants_generated_(0) { }
+  RegExpNode() : trace_count_(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 Emit(RegExpCompiler* compiler, GenerationVariant* variant) = 0;
+  virtual bool Emit(RegExpCompiler* compiler, Trace* trace) = 0;
   // How many characters must this node consume at a minimum in order to
   // succeed.
   virtual int EatsAtLeast(int recursion_depth) = 0;
   // Emits some quick code that checks whether the preloaded characters match.
   // Falls through on certain failure, jumps to the label on possible success.
   // If the node cannot make a quick check it does nothing and returns false.
   bool EmitQuickCheck(RegExpCompiler* compiler,
-                      GenerationVariant* variant,
+                      Trace* trace,
                       bool preload_has_checked_bounds,
                       Label* on_possible_success,
                       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) = 0;
   static const int kNodeIsTooComplexForGreedyLoops = -1;
   virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; }
   Label* label() { return &label_; }
-  static const int kMaxVariantsGenerated = 10;
+  // If non-generic code is generated for a node (ie the node is not at the
+  // start of the trace) then it cannot be reused.  This variable sets a limit
+  // on how often we allow that to happen before we insist on starting a new
+  // trace and generating generic code for a node that can be reused by flushing
+  // the deferred actions in the current trace and generating a goto.
+  static const int kMaxCopiesCodeGenerated = 10;
 
   // 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_; }
 
   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);
+  LimitResult LimitVersions(RegExpCompiler* compiler, Trace* trace);
 
   // 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;
 
  private:
   Label label_;
   NodeInfo info_;
   SiblingList siblings_;
-  int variants_generated_;
+  // This variable keeps track of how many times code has been generated for
+  // this node (in different traces).  We don't keep track of where the
+  // generated code is located unless the code is generated at the start of
+  // a trace, in which case it is generic and can be reused by flushing the
+  // deferred operations in the current trace and generating a goto.
+  int trace_count_;
+};
+
+
+// A simple closed interval.
+class Interval {
+ public:
+  Interval() : from_(kNone), to_(kNone) { }
+  Interval(int from, int to) : from_(from), to_(to) { }
+  Interval Union(Interval that) {
+    if (that.from_ == kNone)
+      return *this;
+    else if (from_ == kNone)
+      return that;
+    else
+      return Interval(Min(from_, that.from_), Max(to_, that.to_));
+  }
+  bool Contains(int value) {
+    return (from_ <= value) && (value <= to_);
+  }
+  bool is_empty() { return from_ == kNone; }
+  int from() { return from_; }
+  int to() { return to_; }
+  static Interval Empty() { return Interval(); }
+  static const int kNone = -1;
+ private:
+  int from_;
+  int to_;
 };
 
 
 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; }
  private:
   RegExpNode* on_success_;
 };
 
 
 class ActionNode: public SeqRegExpNode {
  public:
   enum Type {
     SET_REGISTER,
     INCREMENT_REGISTER,
     STORE_POSITION,
     BEGIN_SUBMATCH,
-    POSITIVE_SUBMATCH_SUCCESS
+    POSITIVE_SUBMATCH_SUCCESS,
+    EMPTY_MATCH_CHECK,
+    CLEAR_CAPTURES
   };
   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* BeginSubmatch(
-      int stack_pointer_reg,
-      int position_reg,
-      RegExpNode* on_success);
-  static ActionNode* PositiveSubmatchSuccess(
-      int stack_pointer_reg,
-      int restore_reg,
-      RegExpNode* on_success);
+  static ActionNode* ClearCaptures(Interval range, 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);
+  static ActionNode* EmptyMatchCheck(int start_register,
+                                     int repetition_register,
+                                     int repetition_limit,
+                                     RegExpNode* on_success);
   virtual void Accept(NodeVisitor* visitor);
-  virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant);
+  virtual bool Emit(RegExpCompiler* compiler, Trace* trace);
   virtual int EatsAtLeast(int recursion_depth);
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
                                     int filled_in) {
     return on_success()->GetQuickCheckDetails(details, compiler, filled_in);
   }
   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;
     } u_increment_register;
     struct {
       int reg;
     } u_position_register;
     struct {
       int stack_pointer_register;
       int current_position_register;
     } u_submatch;
+    struct {
+      int start_register;
+      int repetition_register;
+      int repetition_limit;
+    } u_empty_match_check;
+    struct {
+      int range_from;
+      int range_to;
+    } u_clear_captures;
   } data_;
   ActionNode(Type type, RegExpNode* on_success)
       : SeqRegExpNode(on_success),
         type_(type) { }
   Type type_;
   friend class DotPrinter;
 };
 
 
 class TextNode: public SeqRegExpNode {
  public:
   TextNode(ZoneList<TextElement>* elms,
            RegExpNode* on_success)
       : SeqRegExpNode(on_success),
         elms_(elms) { }
   TextNode(RegExpCharacterClass* that,
            RegExpNode* on_success)
       : SeqRegExpNode(on_success),
         elms_(new ZoneList<TextElement>(1)) {
     elms_->Add(TextElement::CharClass(that));
   }
   virtual void Accept(NodeVisitor* visitor);
   virtual RegExpNode* PropagateForward(NodeInfo* info);
-  virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant);
+  virtual bool Emit(RegExpCompiler* compiler, Trace* trace);
   virtual int EatsAtLeast(int recursion_depth);
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
                                     int characters_filled_in);
   ZoneList<TextElement>* elements() { return elms_; }
   void MakeCaseIndependent();
   virtual int GreedyLoopTextLength();
   virtual TextNode* Clone() {
     TextNode* result = new TextNode(*this);
     result->CalculateOffsets();
     return result;
   }
   void CalculateOffsets();
 
  private:
   enum TextEmitPassType {
     NON_ASCII_MATCH,
     CHARACTER_MATCH,
     CASE_CHARACTER_MATCH,
     CHARACTER_CLASS_MATCH
   };
   void TextEmitPass(RegExpCompiler* compiler,
                     TextEmitPassType pass,
                     bool preloaded,
-                    GenerationVariant* variant,
+                    Trace* trace,
                     bool first_element_checked,
                     int* checked_up_to);
   int Length();
   ZoneList<TextElement>* elms_;
 };
 
 
 class BackReferenceNode: public SeqRegExpNode {
  public:
   BackReferenceNode(int start_reg,
                     int end_reg,
                     RegExpNode* on_success)
       : SeqRegExpNode(on_success),
         start_reg_(start_reg),
         end_reg_(end_reg) { }
   virtual void Accept(NodeVisitor* visitor);
   int start_register() { return start_reg_; }
   int end_register() { return end_reg_; }
-  virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant);
+  virtual bool Emit(RegExpCompiler* compiler, Trace* trace);
   virtual int EatsAtLeast(int recursion_depth) { return 0; }
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
                                     int characters_filled_in) {
     return;
   }
   virtual RegExpNode* PropagateForward(NodeInfo* info);
   virtual BackReferenceNode* Clone() { return new BackReferenceNode(*this); }
 
  private:
   int start_reg_;
   int end_reg_;
 };
 
 
 class EndNode: public RegExpNode {
  public:
   enum Action { ACCEPT, BACKTRACK, NEGATIVE_SUBMATCH_SUCCESS };
   explicit EndNode(Action action) : action_(action) { }
   virtual void Accept(NodeVisitor* visitor);
-  virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant);
+  virtual bool Emit(RegExpCompiler* compiler, Trace* trace);
   virtual int EatsAtLeast(int recursion_depth) { return 0; }
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
                                     int characters_filled_in) {
     // Returning 0 from EatsAtLeast should ensure we never get here.
     UNREACHABLE();
   }
   virtual RegExpNode* PropagateForward(NodeInfo* info);
   virtual EndNode* Clone() { return new EndNode(*this); }
 
  protected:
-  void EmitInfoChecks(RegExpMacroAssembler* macro, GenerationVariant* variant);
+  void EmitInfoChecks(RegExpMacroAssembler* macro, Trace* trace);
 
  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);
+  virtual bool Emit(RegExpCompiler* compiler, Trace* trace);
 
  private:
   int stack_pointer_register_;
   int current_position_register_;
 };
 
 
 class Guard: public ZoneObject {
  public:
   enum Relation { LT, GEQ };
@@ skipping 32 matching lines @@
 class ChoiceNode: public RegExpNode {
  public:
   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);
-  virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant);
+  virtual bool Emit(RegExpCompiler* compiler, Trace* trace);
   virtual int EatsAtLeast(int recursion_depth);
   int EatsAtLeastHelper(int recursion_depth, RegExpNode* ignore_this_node);
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
                                     int characters_filled_in);
   virtual RegExpNode* PropagateForward(NodeInfo* info);
   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,
-                     GenerationVariant* variant);
+                     Trace* trace);
   int CalculatePreloadCharacters(RegExpCompiler* compiler);
   bool EmitOutOfLineContinuation(RegExpCompiler* compiler,
-                                 GenerationVariant* variant,
+                                 Trace* trace,
                                  GuardedAlternative alternative,
                                  AlternativeGeneration* alt_gen,
                                  int preload_characters,
                                  bool next_expects_preload);
   DispatchTable* table_;
   bool being_calculated_;
 };
 
 
 class LoopChoiceNode: public ChoiceNode {
  public:
   explicit LoopChoiceNode(bool body_can_be_zero_length)
       : ChoiceNode(2),
         loop_node_(NULL),
         continue_node_(NULL),
         body_can_be_zero_length_(body_can_be_zero_length) { }
   void AddLoopAlternative(GuardedAlternative alt);
   void AddContinueAlternative(GuardedAlternative alt);
-  virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant);
+  virtual bool Emit(RegExpCompiler* compiler, Trace* trace);
   virtual int EatsAtLeast(int recursion_depth);  // Returns 0.
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
                                     int characters_filled_in);
   virtual LoopChoiceNode* Clone() { return new LoopChoiceNode(*this); }
   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 void Accept(NodeVisitor* visitor);
 
  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_;
 };
 
 
 // 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 {
+// the current state of the code generator.  The effect of this is that we
+// generate code for paths that the matcher can take through the regular
+// expression.  A given node in the regexp can be code-generated several times
+// as it can be part of several traces.  For example for the regexp:
+// /foo(bar|ip)baz/ the code to match baz will be generated twice, once as part
+// of the foo-bar-baz trace and once as part of the foo-ip-baz trace.  The code
+// to match foo is generated only once (the traces have a common prefix).  The
+// code to store the capture is deferred and generated (twice) after the places
+// where baz has been matched.
+class Trace {
  public:
   class DeferredAction {
    public:
     DeferredAction(ActionNode::Type type, int reg)
         : type_(type), reg_(reg), next_(NULL) { }
     DeferredAction* next() { return next_; }
+    bool Mentions(int reg);
     int reg() { return reg_; }
     ActionNode::Type type() { return type_; }
    private:
     ActionNode::Type type_;
     int reg_;
     DeferredAction* next_;
-    friend class GenerationVariant;
+    friend class Trace;
   };
 
   class DeferredCapture: public DeferredAction {
    public:
-    DeferredCapture(int reg, GenerationVariant* variant)
+    DeferredCapture(int reg, Trace* trace)
         : DeferredAction(ActionNode::STORE_POSITION, reg),
-          cp_offset_(variant->cp_offset()) { }
+          cp_offset_(trace->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 DeferredClearCaptures : public DeferredAction {
+   public:
+    explicit DeferredClearCaptures(Interval range)
+        : DeferredAction(ActionNode::CLEAR_CAPTURES, -1),
+          range_(range) { }
+    Interval range() { return range_; }
+   private:
+    Interval range_;
+  };
+
   class DeferredIncrementRegister: public DeferredAction {
    public:
     explicit DeferredIncrementRegister(int reg)
         : DeferredAction(ActionNode::INCREMENT_REGISTER, reg) { }
   };
 
-  GenerationVariant()
+  Trace()
       : cp_offset_(0),
         actions_(NULL),
         backtrack_(NULL),
         stop_node_(NULL),
         loop_label_(NULL),
         characters_preloaded_(0),
         bound_checked_up_to_(0) { }
+  // End the trace.  This involves flushing the deferred actions in the trace
+  // and pushing a backtrack location onto the backtrack stack.  Once this is
+  // done we can start a new trace or go to one that has already been
+  // generated.
   bool Flush(RegExpCompiler* compiler, RegExpNode* successor);
   int cp_offset() { return cp_offset_; }
   DeferredAction* actions() { return actions_; }
+  // A trivial trace is one that has no deferred actions or other state that
+  // affects the assumptions used when generating code.  There is no recorded
+  // backtrack location in a trivial trace, so with a trivial trace we will
+  // generate code that, on a failure to match, gets the backtrack location
+  // from the backtrack stack rather than using a direct jump instruction.  We
+  // always start code generation with a trivial trace and non-trivial traces
+  // are created as we emit code for nodes or add to the list of deferred
+  // actions in the trace.  The location of the code generated for a node using
+  // a trivial trace is recorded in a label in the node so that gotos can be
+  // generated to that code.
   bool is_trivial() {
     return backtrack_ == NULL &&
            actions_ == NULL &&
            cp_offset_ == 0 &&
            characters_preloaded_ == 0 &&
            bound_checked_up_to_ == 0 &&
            quick_check_performed_.characters() == 0;
   }
   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_; }
   QuickCheckDetails* quick_check_performed() { return &quick_check_performed_; }
   bool mentions_reg(int reg);
-  // These set methods and AdvanceVariant should be used only on new
-  // GenerationVariants - the intention is that GenerationVariants are
-  // immutable after creation.
+  // Returns true if a deferred position store exists to the specified
+  // register and stores the offset in the out-parameter.  Otherwise
+  // returns false.
+  bool GetStoredPosition(int reg, int* cp_offset);
+  // These set methods and AdvanceCurrentPositionInTrace should be used only on
+  // new traces - the intention is that traces are immutable after creation.
   void add_action(DeferredAction* new_action) {
     ASSERT(new_action->next_ == NULL);
     new_action->next_ = actions_;
     actions_ = new_action;
   }
   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; }
   void set_characters_preloaded(int cpre) { characters_preloaded_ = cpre; }
   void set_bound_checked_up_to(int to) { bound_checked_up_to_ = to; }
   void set_quick_check_performed(QuickCheckDetails* d) {
     quick_check_performed_ = *d;
   }
   void clear_quick_check_performed() {
   }
-  void AdvanceVariant(int by, bool ascii);
+  void AdvanceCurrentPositionInTrace(int by, bool ascii);
  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,
@@ skipping 105 matching lines @@
                                     Handle<String> pattern,
                                     bool is_ascii);
 
   static void DotPrint(const char* label, RegExpNode* node, bool ignore_case);
 };
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_JSREGEXP_H_