More assertion propagation.

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 419 matching lines @@
   static TextElement CharClass(RegExpCharacterClass* char_class);
   Type type;
   union {
     RegExpAtom* u_atom;
     RegExpCharacterClass* u_char_class;
   } data;
 };
 
 
 struct NodeInfo {
+  enum PrecedingInfo {
+    UNKNOWN = -1, FALSE = 0, TRUE = 1
+  };
+
   NodeInfo()
       : being_analyzed(false),
         been_analyzed(false),
         determine_word(false),
         determine_newline(false),
         determine_start(false),
         follows_word_interest(false),
         follows_newline_interest(false),
-        follows_start_interest(false) { }
-  bool SameInterests(NodeInfo* that) {
-    return (follows_word_interest == that->follows_word_interest)
+        follows_start_interest(false),
+        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);
   }
-  void AdoptInterests(NodeInfo* that) {
-    follows_word_interest = that->follows_word_interest;
-    follows_newline_interest = that->follows_newline_interest;
-    follows_start_interest = that->follows_start_interest;
+
+  // 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;
   }
-  bool prev_determine_word() {
-    return determine_word || follows_word_interest;
+
+  // 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;
   }
-  bool prev_determine_newline() {
-    return determine_newline || follows_newline_interest;
-  }
-  bool prev_determine_start() {
-    return determine_start || follows_start_interest;
-  }
+
   bool being_analyzed: 1;
   bool been_analyzed: 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;
+
+  // 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;
+
+  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;
 };
 
 
 STATIC_CHECK(sizeof(NodeInfo) <= sizeof(int));  // NOLINT
 
 
 class SiblingList {
  public:
   SiblingList() : list_(NULL) { }
   int length() {
@@ skipping 18 matching lines @@
   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 RegExpNode* PropagateInterest(NodeInfo* info) = 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); }
  protected:
   inline void Bind(RegExpMacroAssembler* macro);
  private:
   Label label_;
   NodeInfo info_;
@@ skipping 26 matching lines @@
   };
   static ActionNode* StoreRegister(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* SavePosition(int reg, RegExpNode* on_success);
   static ActionNode* RestorePosition(int reg, RegExpNode* on_success);
   static ActionNode* BeginSubmatch(int reg, RegExpNode* on_success);
   static ActionNode* EscapeSubmatch(int reg, RegExpNode* on_success);
   virtual void Accept(NodeVisitor* visitor);
   virtual bool Emit(RegExpCompiler* compiler);
-  virtual RegExpNode* PropagateInterest(NodeInfo* info);
+  virtual RegExpNode* PropagateForward(NodeInfo* info);
  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) { }
   virtual void Accept(NodeVisitor* visitor);
-  virtual RegExpNode* PropagateInterest(NodeInfo* info);
+  virtual RegExpNode* PropagateForward(NodeInfo* info);
   RegExpNode* on_failure() { return on_failure_; }
   virtual bool Emit(RegExpCompiler* compiler);
   ZoneList<TextElement>* elements() { return elms_; }
   void MakeCaseIndependent();
  private:
   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* PropagateInterest(NodeInfo* info);
+  virtual RegExpNode* PropagateForward(NodeInfo* info);
  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* PropagateInterest(NodeInfo* info);
+  virtual RegExpNode* PropagateForward(NodeInfo* info);
   virtual bool IsBacktrack() { return action_ == BACKTRACK; }
   virtual bool GoTo(RegExpCompiler* compiler);
  private:
   Action action_;
 };
 
 
 class Guard: public ZoneObject {
  public:
   enum Relation { LT, GEQ };
@@ skipping 30 matching lines @@
       : on_failure_(on_failure),
         alternatives_(new ZoneList<GuardedAlternative>(expected_size)),
         table_calculated_(false),
         being_calculated_(false) { }
   virtual void Accept(NodeVisitor* visitor);
   void AddAlternative(GuardedAlternative node) { alternatives()->Add(node); }
   ZoneList<GuardedAlternative>* alternatives() { return alternatives_; }
   DispatchTable* table() { return &table_; }
   RegExpNode* on_failure() { return on_failure_; }
   virtual bool Emit(RegExpCompiler* compiler);
-  virtual RegExpNode* PropagateInterest(NodeInfo* info);
+  virtual RegExpNode* PropagateForward(NodeInfo* info);
   bool table_calculated() { return table_calculated_; }
   void set_table_calculated(bool b) { table_calculated_ = b; }
   bool being_calculated() { return being_calculated_; }
   void set_being_calculated(bool b) { being_calculated_ = b; }
  private:
   void GenerateGuard(RegExpMacroAssembler* macro_assembler,
                      Guard *guard,
                      Label* on_failure);
   RegExpNode* on_failure_;
   ZoneList<GuardedAlternative>* alternatives_;
@@ skipping 66 matching lines @@
   bool has_character_escapes;
   Handle<String> error;
   int capture_count;
 };
 
 
 class RegExpEngine: public AllStatic {
  public:
   static Handle<FixedArray> Compile(RegExpParseResult* input,
                                     RegExpNode** node_return,
-                                    bool ignore_case);
+                                    bool ignore_case,
+                                    bool multiline);
   static void DotPrint(const char* label, RegExpNode* node);
 };
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_JSREGEXP_H_