Rudimentary assertion expansion

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 167 matching lines @@
 };
 
 
 class CharacterRange {
  public:
   CharacterRange() : from_(0), to_(0) { }
   // For compatibility with the CHECK_OK macro
   CharacterRange(void* null) { ASSERT_EQ(NULL, null); }  //NOLINT
   CharacterRange(uc16 from, uc16 to) : from_(from), to_(to) { }
   static void AddClassEscape(uc16 type, ZoneList<CharacterRange>* ranges);
+  static Vector<const uc16> GetWordBounds();
   static inline CharacterRange Singleton(uc16 value) {
     return CharacterRange(value, value);
   }
   static inline CharacterRange Range(uc16 from, uc16 to) {
     ASSERT(from <= to);
     return CharacterRange(from, to);
   }
   static inline CharacterRange Everything() {
     return CharacterRange(0, 0xFFFF);
   }
   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 IsSingleton() { return (from_ == to_); }
   void AddCaseEquivalents(ZoneList<CharacterRange>* ranges);
+  static void Split(ZoneList<CharacterRange>* base,
+                    Vector<const uc16> overlay,
+                    ZoneList<CharacterRange>** included,
+                    ZoneList<CharacterRange>** excluded);
+
   static const int kRangeCanonicalizeMax = 0x346;
   static const int kStartMarker = (1 << 24);
   static const int kPayloadMask = (1 << 24) - 1;
+
  private:
   uc16 from_;
   uc16 to_;
 };
 
 
 template <typename Node, class Callback>
 static void DoForEach(Node* node, Callback* callback);
 
 
@@ skipping 118 matching lines @@
   OutSet(uint32_t first, ZoneList<unsigned>* remaining)
       : first_(first), remaining_(remaining), successors_(NULL) { }
   uint32_t first_;
   ZoneList<unsigned>* remaining_;
   ZoneList<OutSet*>* successors_;
 };
 
 
 // A mapping from integers, specified as ranges, to a set of integers.
 // Used for mapping character ranges to choices.
-class DispatchTable {
+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); }
@@ skipping 72 matching lines @@
   static TextElement CharClass(RegExpCharacterClass* char_class);
   Type type;
   union {
     RegExpAtom* u_atom;
     RegExpCharacterClass* u_char_class;
   } data;
 };
 
 
 struct NodeInfo {
-  enum PrecedingInfo {
+  enum TriBool {

[Lasse Reichstein, 2008/12/01 11:55:47]

Not really a better name. Not that I can think of one that is, but TriBool is
simply wrong (either it's three or it's a bool). 

     UNKNOWN = -1, FALSE = 0, TRUE = 1
   };
 
   NodeInfo()
       : being_analyzed(false),
         been_analyzed(false),
+        being_expanded(false),
+        been_expanded(false),
         determine_word(false),
         determine_newline(false),
         determine_start(false),
+        does_determine_word(false),
+        does_determine_newline(false),
+        does_determine_start(false),
         follows_word_interest(false),
         follows_newline_interest(false),
         follows_start_interest(false),
+        is_word(UNKNOWN),
+        is_newline(UNKNOWN),
         at_end(false),
         follows_word(UNKNOWN),
         follows_newline(UNKNOWN),
         follows_start(UNKNOWN) { }
 
-  bool HasSameForwardInterests(NodeInfo* that) {
-    return (at_end == that->at_end)
-        && (follows_word_interest == that->follows_word_interest)
-        && (follows_newline_interest == that->follows_newline_interest)
-        && (follows_start_interest == that->follows_start_interest);
+  // Returns true if the interests and assumptions of this node
+  // matches the given one.
+  bool Matches(NodeInfo* that) {
+    return (at_end == that->at_end) &&
+           (follows_word_interest == that->follows_word_interest) &&
+           (follows_newline_interest == that->follows_newline_interest) &&
+           (follows_start_interest == that->follows_start_interest) &&
+           (follows_word == that->follows_word) &&
+           (follows_newline == that->follows_newline) &&
+           (follows_start == that->follows_start) &&
+           (does_determine_word == that->does_determine_word) &&
+           (does_determine_newline == that->does_determine_newline) &&
+           (does_determine_start == that->does_determine_start);
+  }
+
+  bool HasAssertions() {
+    return (follows_word != UNKNOWN) ||
+           (follows_newline != UNKNOWN) ||
+           (follows_start != UNKNOWN);
   }
 
   // Updates the interests of this node given the interests of the
   // node preceding it.
   void AddFromPreceding(NodeInfo* that) {
     at_end |= that->at_end;
     follows_word_interest |= that->follows_word_interest;
     follows_newline_interest |= that->follows_newline_interest;
     follows_start_interest |= that->follows_start_interest;
   }
 
+  void AddAssumptions(NodeInfo* that) {
+    if (that->follows_word != UNKNOWN) {
+      ASSERT(follows_word == UNKNOWN || follows_word == that->follows_word);
+      follows_word = that->follows_word;
+    }
+    if (that->follows_newline != UNKNOWN) {
+      ASSERT(follows_newline == UNKNOWN ||
+             follows_newline == that->follows_newline);
+      follows_newline = that->follows_newline;
+    }
+    if (that->follows_start != UNKNOWN) {
+      ASSERT(follows_start == UNKNOWN ||
+             follows_start == that->follows_start);
+      follows_start = that->follows_start;
+    }
+    does_determine_word = that->does_determine_word;
+    does_determine_newline = that->does_determine_newline;
+    does_determine_start = that->does_determine_start;
+  }
+
   // Sets the interests of this node to include the interests of the
   // following node.
   void AddFromFollowing(NodeInfo* that) {
     follows_word_interest |= that->follows_word_interest;
     follows_newline_interest |= that->follows_newline_interest;
     follows_start_interest |= that->follows_start_interest;
   }
 
+  void ResetCompilationState() {
+    being_analyzed = false;
+    been_analyzed = false;
+    being_expanded = false;
+    been_expanded = false;
+  }
+
   bool being_analyzed: 1;
   bool been_analyzed: 1;
+  bool being_expanded: 1;
+  bool been_expanded: 1;
 
   // These bits are set if this node must propagate forward information
   // about the last character it consumed (or, in the case of 'start',
   // if it is at the start of the input).
   bool determine_word: 1;
   bool determine_newline: 1;
   bool determine_start: 1;
 
+  bool does_determine_word: 1;
+  bool does_determine_newline: 1;
+  bool does_determine_start: 1;
+
   // These bits are set of this node has to know what the preceding
   // character was.
   bool follows_word_interest: 1;
   bool follows_newline_interest: 1;
   bool follows_start_interest: 1;
 
+  TriBool is_word: 2;
+  TriBool is_newline: 2;
+
   bool at_end: 1;
 
   // These bits are set if the node can make assumptions about what
   // the previous character was.
-  PrecedingInfo follows_word: 2;
-  PrecedingInfo follows_newline: 2;
-  PrecedingInfo follows_start: 2;
+  TriBool follows_word: 2;
+  TriBool follows_newline: 2;
+  TriBool follows_start: 2;
 };
 
 
+class ExpansionGuard {
+ public:
+  explicit inline ExpansionGuard(NodeInfo* info) : info_(info) {
+    ASSERT(!info->being_expanded);
+    info->being_expanded = true;
+  }
+  inline ~ExpansionGuard() {
+    info_->being_expanded = false;
+  }
+ private:
+  NodeInfo* info_;
+};
+
+
 class SiblingList {
  public:
   SiblingList() : list_(NULL) { }
   int length() {
     return list_ == NULL ? 0 : list_->length();
   }
   void Ensure(RegExpNode* parent) {
     if (list_ == NULL) {
       list_ = new ZoneList<RegExpNode*>(2);
       list_->Add(parent);
@@ skipping 13 matching lines @@
   // 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;
 
+  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; }
-  RegExpNode* GetSibling(NodeInfo* info);
-  void EnsureSiblings() { siblings_.Ensure(this); }
+
   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:
+
+  // 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_;
 };
 
 
 class SeqRegExpNode: public RegExpNode {
  public:
   explicit SeqRegExpNode(RegExpNode* on_success)
@@ skipping 22 matching lines @@
   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);
   virtual void Accept(NodeVisitor* visitor);
   virtual bool Emit(RegExpCompiler* compiler);
+  virtual RegExpNode* ExpandLocal(NodeInfo* info);
+  virtual void ExpandChildren();
   virtual RegExpNode* PropagateForward(NodeInfo* info);
+  virtual ActionNode* Clone() { return new ActionNode(*this); }
+
  private:
   union {
     struct {
       int reg;
       int value;
     } u_store_register;
     struct {
       int reg;
     } u_increment_register;
     struct {
@@ skipping 13 matching lines @@
 
 
 class TextNode: public SeqRegExpNode {
  public:
   TextNode(ZoneList<TextElement>* elms,
            RegExpNode* on_success,
            RegExpNode* on_failure)
       : SeqRegExpNode(on_success),
         on_failure_(on_failure),
         elms_(elms) { }
+  TextNode(RegExpCharacterClass* that,
+           RegExpNode* on_success,
+           RegExpNode* on_failure)
+      : 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);
   ZoneList<TextElement>* elements() { return elms_; }
   void MakeCaseIndependent();
+  virtual TextNode* Clone() { return new TextNode(*this); }
+
  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)
       : 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 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 };
   explicit EndNode(Action action) : action_(action) { }
   virtual void Accept(NodeVisitor* visitor);
   virtual bool Emit(RegExpCompiler* compiler);
   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); }
+
  private:
   Action action_;
 };
 
 
 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_; }
+
  private:
   int reg_;
   Relation op_;
   int value_;
 };
 
 
 class GuardedAlternative {
  public:
   explicit GuardedAlternative(RegExpNode* node) : node_(node), guards_(NULL) { }
   void AddGuard(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 ChoiceNode: public RegExpNode {
  public:
   explicit ChoiceNode(int expected_size, RegExpNode* on_failure)
       : on_failure_(on_failure),
         alternatives_(new ZoneList<GuardedAlternative>(expected_size)),
-        table_calculated_(false),
+        table_(NULL),
         being_calculated_(false) { }
   virtual void Accept(NodeVisitor* visitor);
   void AddAlternative(GuardedAlternative node) { alternatives()->Add(node); }
   ZoneList<GuardedAlternative>* alternatives() { return alternatives_; }
-  DispatchTable* table() { return &table_; }
+  DispatchTable* GetTable(bool ignore_case);
   RegExpNode* on_failure() { return on_failure_; }
   virtual bool Emit(RegExpCompiler* compiler);
   virtual RegExpNode* PropagateForward(NodeInfo* info);
-  bool table_calculated() { return table_calculated_; }
-  void set_table_calculated(bool b) { table_calculated_ = b; }
+  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; }
+
  private:
+  friend class DispatchTableConstructor;
+  friend class Analysis;
   void GenerateGuard(RegExpMacroAssembler* macro_assembler,
                      Guard *guard,
                      Label* on_failure);
   RegExpNode* on_failure_;
   ZoneList<GuardedAlternative>* alternatives_;
-  DispatchTable table_;
-  bool table_calculated_;
+  DispatchTable* table_;
   bool being_calculated_;
 };
 
 
 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
 };
 
 
 // Node visitor used to add the start set of the alternatives to the
 // dispatch table of a choice node.
 class DispatchTableConstructor: public NodeVisitor {
  public:
-  explicit DispatchTableConstructor(DispatchTable* table)
+  DispatchTableConstructor(DispatchTable* table, bool ignore_case)
       : table_(table),
-        choice_index_(-1) { }
+        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:
   DispatchTable *table_;
   int choice_index_;
+  bool ignore_case_;
 };
 
 
 class Analysis: public NodeVisitor {
  public:
   explicit Analysis(bool ignore_case)
       : ignore_case_(ignore_case) { }
   void EnsureAnalyzed(RegExpNode* node);
 
 #define DECLARE_VISIT(Type)                                          \
@@ skipping 15 matching lines @@
   int capture_count;
 };
 
 
 class RegExpEngine: public AllStatic {
  public:
   static Handle<FixedArray> Compile(RegExpParseResult* input,
                                     RegExpNode** node_return,
                                     bool ignore_case,
                                     bool multiline);
-  static void DotPrint(const char* label, RegExpNode* node);
+  static void DotPrint(const char* label, RegExpNode* node, bool ignore_case);
 };
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_JSREGEXP_H_