Refactor allocation policies.

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 269 matching lines @@
   }
   bool Contains(uc16 i) { return from_ <= i && i <= to_; }
   uc16 from() const { return from_; }
   void set_from(uc16 value) { from_ = value; }
   uc16 to() const { return to_; }
   void set_to(uc16 value) { to_ = value; }
   bool is_valid() { return from_ <= to_; }
   bool IsEverything(uc16 max) { return from_ == 0 && to_ >= max; }
   bool IsSingleton() { return (from_ == to_); }
   void AddCaseEquivalents(ZoneList<CharacterRange>* ranges, bool is_ascii);
-  static void Split(ZoneList<CharacterRange>* base,
+  static void Split(Zone* zone,
+                    ZoneList<CharacterRange>* base,
                     Vector<const uc16> overlay,
                     ZoneList<CharacterRange>** included,
                     ZoneList<CharacterRange>** excluded);
   // Whether a range list is in canonical form: Ranges ordered by from value,
   // and ranges non-overlapping and non-adjacent.
   static bool IsCanonical(ZoneList<CharacterRange>* ranges);
   // Convert range list to canonical form. The characters covered by the ranges
   // will still be the same, but no character is in more than one range, and
   // adjacent ranges are merged. The resulting list may be shorter than the
   // original, but cannot be longer.
@@ skipping 30 matching lines @@
   uc16 from_;
   uc16 to_;
 };
 
 
 // A set of unsigned integers that behaves especially well on small
 // integers (< 32).  May do zone-allocation.
 class OutSet: public ZoneObject {
  public:
   OutSet() : first_(0), remaining_(NULL), successors_(NULL) { }
-  OutSet* Extend(unsigned value);
+  OutSet* Extend(Zone* zone, unsigned value);
   bool Get(unsigned value);
   static const unsigned kFirstLimit = 32;
 
  private:
   // Destructively set a value in this set.  In most cases you want
   // to use Extend instead to ensure that only one instance exists
   // that contains the same values.
-  void Set(unsigned value);
+  void Set(Zone* zone, unsigned value);
 
   // 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 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) { }
     Entry(uc16 from, uc16 to, OutSet* out_set)
         : from_(from), to_(to), out_set_(out_set) { }
     uc16 from() { return from_; }
     uc16 to() { return to_; }
     void set_to(uc16 value) { to_ = value; }
-    void AddValue(int value) { out_set_ = out_set_->Extend(value); }
+    void AddValue(Zone* zone, int value) {
+      out_set_ = out_set_->Extend(zone, value);
+    }
     OutSet* out_set() { return out_set_; }
    private:
     uc16 from_;
     uc16 to_;
     OutSet* out_set_;
   };
 
   class Config {
    public:
     typedef uc16 Key;
     typedef Entry Value;
     static const uc16 kNoKey;
     static const Entry kNoValue;
     static inline int Compare(uc16 a, uc16 b) {
       if (a == b)
         return 0;
       else if (a < b)
         return -1;
       else
         return 1;
     }
   };
 
+  explicit DispatchTable(Zone* zone) : zone_(zone), tree_(zone) {}
+
   void AddRange(CharacterRange range, int value);
   OutSet* Get(uc16 value);
   void Dump();
 
   template <typename Callback>
   void ForEach(Callback* callback) { return tree()->ForEach(callback); }
  private:
   // There can't be a static empty set since it allocates its
   // successors in a zone and caches them.
   OutSet* empty() { return &empty_; }
+  Zone* zone_;
   OutSet empty_;
   ZoneSplayTree<Config>* tree() { return &tree_; }
   ZoneSplayTree<Config> tree_;
 };
 
 
 #define FOR_EACH_NODE_TYPE(VISIT)                                    \
   VISIT(End)                                                         \
   VISIT(Action)                                                      \
   VISIT(Choice)                                                      \
@@ skipping 101 matching lines @@
   bool visited: 1;
 };
 
 
 class SiblingList {
  public:
   SiblingList() : list_(NULL) { }
   int length() {
     return list_ == NULL ? 0 : list_->length();
   }
-  void Ensure(RegExpNode* parent) {
+  void Ensure(Zone* zone, RegExpNode* parent) {
     if (list_ == NULL) {
-      list_ = new ZoneList<RegExpNode*>(2);
+      list_ = ZoneList<RegExpNode*>::New(zone, 2);
       list_->Add(parent);
     }
   }
   void Add(RegExpNode* node) { list_->Add(node); }
   RegExpNode* Get(int index) { return list_->at(index); }
  private:
   ZoneList<RegExpNode*>* list_;
 };
 
 
@@ skipping 93 matching lines @@
   // the deferred actions in the current trace and generating a goto.
   static const int kMaxCopiesCodeGenerated = 10;
 
   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));
+  static C* EnsureSibling(Zone* zone, C* node, NodeInfo* info, bool* cloned) {
+    return static_cast<C*>(node->EnsureSibling(zone, info, cloned));
   }
 
   SiblingList* siblings() { return &siblings_; }
   void set_siblings(SiblingList* other) { siblings_ = *other; }
 
   // Return the set of possible next characters recognized by the regexp
   // (or a safe subset, potentially the set of all characters).
-  ZoneList<CharacterRange>* FirstCharacterSet();
+  ZoneList<CharacterRange>* FirstCharacterSet(Zone* zone);
 
   // Compute (if possible within the budget of traversed nodes) the
   // possible first characters of the input matched by this node and
   // its continuation. Returns the remaining budget after the computation.
   // If the budget is spent, the result is negative, and the cached
   // first_character_set_ value isn't set.
-  virtual int ComputeFirstCharacterSet(int budget);
+  virtual int ComputeFirstCharacterSet(Zone* zone, int budget);
 
   // Get and set the cached first character set value.
   ZoneList<CharacterRange>* first_character_set() {
     return first_character_set_;
   }
   void set_first_character_set(ZoneList<CharacterRange>* character_set) {
     first_character_set_ = character_set;
   }
 
  protected:
   enum LimitResult { DONE, CONTINUE };
   static const int kComputeFirstCharacterSetFail = -1;
 
   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);
+  RegExpNode* EnsureSibling(Zone* zone, 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 usable state.
   virtual RegExpNode* Clone() = 0;
 
  private:
   static const int kFirstCharBudget = 10;
   Label label_;
   NodeInfo info_;
@@ skipping 84 matching lines @@
                                     RegExpCompiler* compiler,
                                     int filled_in,
                                     bool not_at_start) {
     return on_success()->GetQuickCheckDetails(
         details, compiler, filled_in, not_at_start);
   }
   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); }
-  virtual int ComputeFirstCharacterSet(int budget);
+  virtual int ComputeFirstCharacterSet(Zone* zone, int budget);
  private:
   union {
     struct {
       int reg;
       int value;
     } u_store_register;
     struct {
       int reg;
     } u_increment_register;
     struct {
@@ skipping 23 matching lines @@
   friend class DotPrinter;
 };
 
 
 class TextNode: public SeqRegExpNode {
  public:
   TextNode(ZoneList<TextElement>* elms,
            RegExpNode* on_success)
       : SeqRegExpNode(on_success),
         elms_(elms) { }
-  TextNode(RegExpCharacterClass* that,
+  TextNode(Zone* zone,
+           RegExpCharacterClass* that,
            RegExpNode* on_success)
       : SeqRegExpNode(on_success),
-        elms_(new ZoneList<TextElement>(1)) {
+        elms_(ZoneList<TextElement>::New(zone, 1)) {
     elms_->Add(TextElement::CharClass(that));
   }
   virtual void Accept(NodeVisitor* visitor);
   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);
   ZoneList<TextElement>* elements() { return elms_; }
-  void MakeCaseIndependent(bool is_ascii);
+  void MakeCaseIndependent(Zone* zone, bool is_ascii);
   virtual int GreedyLoopTextLength();
   virtual TextNode* Clone() {
     TextNode* result = new TextNode(*this);
     result->CalculateOffsets();
     return result;
   }
   void CalculateOffsets();
-  virtual int ComputeFirstCharacterSet(int budget);
+  virtual int ComputeFirstCharacterSet(Zone* zone, int budget);
  private:
   enum TextEmitPassType {
     NON_ASCII_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;
@@ skipping 40 matching lines @@
   }
   virtual void Accept(NodeVisitor* visitor);
   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 filled_in,
                                     bool not_at_start);
-  virtual int ComputeFirstCharacterSet(int budget);
+  virtual int ComputeFirstCharacterSet(Zone* zone, int budget);
   virtual AssertionNode* Clone() { return new AssertionNode(*this); }
   AssertionNodeType type() { return type_; }
   void set_type(AssertionNodeType type) { type_ = type; }
  private:
   AssertionNode(AssertionNodeType t, RegExpNode* on_success)
       : SeqRegExpNode(on_success), type_(t) { }
   AssertionNodeType type_;
 };
 
 
@@ skipping 12 matching lines @@
   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 BackReferenceNode* Clone() { return new BackReferenceNode(*this); }
-  virtual int ComputeFirstCharacterSet(int budget);
+  virtual int ComputeFirstCharacterSet(Zone* zone, int budget);
  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) { }
@@ skipping 50 matching lines @@
  private:
   int reg_;
   Relation op_;
   int value_;
 };
 
 
 class GuardedAlternative {
  public:
   explicit GuardedAlternative(RegExpNode* node) : node_(node), guards_(NULL) { }
-  void AddGuard(Guard* guard);
+  void AddGuard(Zone* zone, Guard* guard);
   RegExpNode* node() { return node_; }
   void set_node(RegExpNode* node) { node_ = node; }
   ZoneList<Guard*>* guards() { return guards_; }
 
  private:
   RegExpNode* node_;
   ZoneList<Guard*>* guards_;
 };
 
 
 class AlternativeGeneration;
 
 
 class ChoiceNode: public RegExpNode {
  public:
-  explicit ChoiceNode(int expected_size)
-      : alternatives_(new ZoneList<GuardedAlternative>(expected_size)),
+  ChoiceNode(Zone* zone, int expected_size)
+      : alternatives_(ZoneList<GuardedAlternative>::New(zone, expected_size)),
         table_(NULL),
         not_at_start_(false),
         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);
+  DispatchTable* GetTable(Zone* zone, bool ignore_case);
   virtual void Emit(RegExpCompiler* compiler, Trace* trace);
   virtual int EatsAtLeast(int still_to_find,
                           int recursion_depth,
                           bool not_at_start);
   int EatsAtLeastHelper(int still_to_find,
                         int recursion_depth,
                         RegExpNode* ignore_this_node,
                         bool not_at_start);
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
@@ skipping 27 matching lines @@
   DispatchTable* table_;
   // If true, this node is never checked at the start of the input.
   // Allows a new trace to start with at_start() set to false.
   bool not_at_start_;
   bool being_calculated_;
 };
 
 
 class NegativeLookaheadChoiceNode: public ChoiceNode {
  public:
-  explicit NegativeLookaheadChoiceNode(GuardedAlternative this_must_fail,
+  explicit NegativeLookaheadChoiceNode(Zone* zone,
+                                       GuardedAlternative this_must_fail,
                                        GuardedAlternative then_do_this)
-      : ChoiceNode(2) {
+      : ChoiceNode(zone, 2) {
     AddAlternative(this_must_fail);
     AddAlternative(then_do_this);
   }
   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);
   // For a negative lookahead we don't emit the quick check for the
   // alternative that is expected to fail.  This is because quick check code
   // starts by loading enough characters for the alternative that takes fewest
   // characters, but on a negative lookahead the negative branch did not take
   // part in that calculation (EatsAtLeast) so the assumptions don't hold.
   virtual bool try_to_emit_quick_check_for_alternative(int i) { return i != 0; }
-  virtual int ComputeFirstCharacterSet(int budget);
+  virtual int ComputeFirstCharacterSet(Zone* zone, int budget);
 };
 
 
 class LoopChoiceNode: public ChoiceNode {
  public:
-  explicit LoopChoiceNode(bool body_can_be_zero_length)
-      : ChoiceNode(2),
+  LoopChoiceNode(Zone* zone, bool body_can_be_zero_length)
+      : ChoiceNode(zone, 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 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);
-  virtual int ComputeFirstCharacterSet(int budget);
+  virtual int ComputeFirstCharacterSet(Zone* zone, int budget);
   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.
@@ skipping 144 matching lines @@
   void set_loop_label(Label* label) { loop_label_ = label; }
   void set_characters_preloaded(int count) { characters_preloaded_ = count; }
   void set_bound_checked_up_to(int to) { bound_checked_up_to_ = to; }
   void set_flush_budget(int to) { flush_budget_ = to; }
   void set_quick_check_performed(QuickCheckDetails* d) {
     quick_check_performed_ = *d;
   }
   void InvalidateCurrentCharacter();
   void AdvanceCurrentPositionInTrace(int by, RegExpCompiler* compiler);
  private:
-  int FindAffectedRegisters(OutSet* affected_registers);
-  void PerformDeferredActions(RegExpMacroAssembler* macro,
-                               int max_register,
-                               OutSet& affected_registers,
-                               OutSet* registers_to_pop,
-                               OutSet* registers_to_clear);
+  int FindAffectedRegisters(Zone* zone, OutSet* affected_registers);
+  void PerformDeferredActions(Zone* zone,
+                              RegExpMacroAssembler* macro,
+                              int max_register,
+                              OutSet& affected_registers,
+                              OutSet* registers_to_pop,
+                              OutSet* registers_to_clear);
   void RestoreAffectedRegisters(RegExpMacroAssembler* macro,
                                 int max_register,
                                 OutSet& registers_to_pop,
                                 OutSet& registers_to_clear);
   int cp_offset_;
   DeferredAction* actions_;
   Label* backtrack_;
   RegExpNode* stop_node_;
   Label* loop_label_;
   int characters_preloaded_;
@@ skipping 12 matching lines @@
 FOR_EACH_NODE_TYPE(DECLARE_VISIT)
 #undef DECLARE_VISIT
   virtual void VisitLoopChoice(LoopChoiceNode* that) { VisitChoice(that); }
 };
 
 
 // Node visitor used to add the start set of the alternatives to the
 // dispatch table of a choice node.
 class DispatchTableConstructor: public NodeVisitor {
  public:
-  DispatchTableConstructor(DispatchTable* table, bool ignore_case)
-      : table_(table),
+  DispatchTableConstructor(Zone* zone, DispatchTable* table, bool ignore_case)
+      : zone_(zone),
+        table_(table),
         choice_index_(-1),
         ignore_case_(ignore_case) { }
 
   void BuildTable(ChoiceNode* node);
 
   void AddRange(CharacterRange range) {
     table()->AddRange(range, choice_index_);
   }
 
   void AddInverse(ZoneList<CharacterRange>* ranges);
 
 #define DECLARE_VISIT(Type)                                          \
   virtual void Visit##Type(Type##Node* that);
 FOR_EACH_NODE_TYPE(DECLARE_VISIT)
 #undef DECLARE_VISIT
 
   DispatchTable* table() { return table_; }
   void set_choice_index(int value) { choice_index_ = value; }
 
  protected:
+  Zone* zone_;
   DispatchTable* table_;
   int choice_index_;
   bool ignore_case_;
 };
 
 
 // Assertion propagation moves information about assertions such as
 // \b to the affected nodes.  For instance, in /.\b./ information must
 // be propagated to the first '.' that whatever follows needs to know
 // if it matched a word or a non-word, and to the second '.' that it
 // has to check if it succeeds a word or non-word.  In this case the
 // result will be something like:
 //
 //   +-------+        +------------+
 //   |   .   |        |      .     |
 //   +-------+  --->  +------------+
 //   | word? |        | check word |
 //   +-------+        +------------+
 class Analysis: public NodeVisitor {
  public:
-  Analysis(bool ignore_case, bool is_ascii)
-      : ignore_case_(ignore_case),
+  Analysis(Zone* zone, bool ignore_case, bool is_ascii)
+      : zone_(zone),
+        ignore_case_(ignore_case),
         is_ascii_(is_ascii),
         error_message_(NULL) { }
   void EnsureAnalyzed(RegExpNode* node);
 
 #define DECLARE_VISIT(Type)                                          \
   virtual void Visit##Type(Type##Node* that);
 FOR_EACH_NODE_TYPE(DECLARE_VISIT)
 #undef DECLARE_VISIT
   virtual void VisitLoopChoice(LoopChoiceNode* that);
 
   bool has_failed() { return error_message_ != NULL; }
   const char* error_message() {
     ASSERT(error_message_ != NULL);
     return error_message_;
   }
   void fail(const char* error_message) {
     error_message_ = error_message;
   }
  private:
+  Zone* zone_;
   bool ignore_case_;
   bool is_ascii_;
   const char* error_message_;
 
   DISALLOW_IMPLICIT_CONSTRUCTORS(Analysis);
 };
 
 
 struct RegExpCompileData {
   RegExpCompileData()
@@ skipping 66 matching lines @@
   int* vector_;
   int offsets_vector_length_;
 
   friend class ExternalReference;
 };
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_JSREGEXP_H_