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 510 matching lines @@
     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;
   }
 
+  bool HasLookbehind() {
+    return follows_word_interest ||
+           follows_newline_interest ||
+           follows_start_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;
   }
 
   void ResetCompilationState() {
     being_analyzed = false;
@@ skipping 346 matching lines @@
 
   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;
+  friend class AssertionPropagation;
   void GenerateGuard(RegExpMacroAssembler* macro_assembler,
                      Guard *guard,
                      GenerationVariant* variant);
   DispatchTable* table_;
   bool being_calculated_;
 };
 
 
 class LoopChoiceNode: public ChoiceNode {
  public:
@@ skipping 137 matching lines @@
   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 {
+// 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 |
+//   +-------+        +------------+
+//
+// At a later phase all nodes that determine information for their
+// following nodes are split into several 'sibling' nodes.  In this
+// case the first '.' is split into one node that only matches words
+// and one that only matches non-words.  The second '.' is also split,
+// into one node that assumes that the previous character was a word
+// character and one that assumes that is was non-word.  In this case
+// the result is
+//
+//         +------------------+        +------------------+
+//   /-->  | intersect(., \w) |  --->  | intersect(., \W) |
+//   |     +------------------+        +------------------+
+//   |                                 |    follows \w    |
+//   |                                 +------------------+
+// --?
+//   |     +------------------+        +------------------+
+//   \-->  | intersect(., \W) |  --->  | intersect(., \w) |
+//         +------------------+        +------------------+
+//                                     |    follows \W    |
+//                                     +------------------+
+//
+// This way we don't need to explicitly check the previous character
+// but can always assume that whoever consumed the previous character
+// has propagated the relevant information forward.
+class AssertionPropagation: public NodeVisitor {
  public:
-  explicit Analysis(bool ignore_case)
+  explicit AssertionPropagation(bool ignore_case)
       : ignore_case_(ignore_case) { }
   void EnsureAnalyzed(RegExpNode* node);
 
 #define DECLARE_VISIT(Type)                                          \
   virtual void Visit##Type(Type##Node* that);
 FOR_EACH_NODE_TYPE(DECLARE_VISIT)
 #undef DECLARE_VISIT
 
  private:
   bool ignore_case_;
 
-  DISALLOW_IMPLICIT_CONSTRUCTORS(Analysis);
+  DISALLOW_IMPLICIT_CONSTRUCTORS(AssertionPropagation);
 };
 
 
-struct RegExpParseResult {
+struct RegExpCompileData {
+  RegExpCompileData()
+    : tree(NULL),
+      node(NULL),
+      has_lookbehind(false),
+      has_character_escapes(false),
+      capture_count(0) { }
   RegExpTree* tree;
+  RegExpNode* node;
+  bool has_lookbehind;
   bool has_character_escapes;
   Handle<String> error;
   int capture_count;
 };
 
 
 class RegExpEngine: public AllStatic {
  public:
-  static Handle<FixedArray> Compile(RegExpParseResult* input,
-                                    RegExpNode** node_return,
+  static Handle<FixedArray> Compile(RegExpCompileData* input,
                                     bool ignore_case,
                                     bool multiline,
                                     Handle<String> pattern,
                                     bool is_ascii);
 
   static void DotPrint(const char* label, RegExpNode* node, bool ignore_case);
 };
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_JSREGEXP_H_