Merge changes from bleeding_edge into experimental toiger branch....

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 421 matching lines @@
 #undef FORWARD_DECLARE
 
 
 class TextElement {
  public:
   enum Type {UNINITIALIZED, ATOM, CHAR_CLASS};
   TextElement() : type(UNINITIALIZED) { }
   explicit TextElement(Type t) : type(t), cp_offset(-1) { }
   static TextElement Atom(RegExpAtom* atom);
   static TextElement CharClass(RegExpCharacterClass* char_class);
+  int length();
   Type type;
   union {
     RegExpAtom* u_atom;
     RegExpCharacterClass* u_char_class;
   } data;
   int cp_offset;
 };
 
 
 class GenerationVariant;
 
 
 struct NodeInfo {
   enum TriBool {
     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),
         visited(false) { }
 
   // 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);
+           (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;
   }
 
-  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;
-  }
-
   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;
     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.
-  TriBool follows_word: 2;
-  TriBool follows_newline: 2;
-  TriBool follows_start: 2;
-
   bool visited: 1;
 };
 
 
-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);
     }
   }
   void Add(RegExpNode* node) { list_->Add(node); }
   RegExpNode* Get(int index) { return list_->at(index); }
  private:
   ZoneList<RegExpNode*>* list_;
 };
 
 
+// Details of a quick mask-compare check that can look ahead in the
+// input stream.
+class QuickCheckDetails {
+ public:
+  QuickCheckDetails()
+      : characters_(0),
+        mask_(0),
+        value_(0) { }
+  explicit QuickCheckDetails(int characters)
+      : characters_(characters),
+        mask_(0),
+        value_(0) { }
+  bool Rationalize(bool ascii);
+  // Merge in the information from another branch of an alternation.
+  void Merge(QuickCheckDetails* other, int from_index);
+  // Advance the current position by some amount.
+  void Advance(int by, bool ascii);
+  void Clear();
+  struct Position {
+    Position() : mask(0), value(0), determines_perfectly(false) { }
+    uc16 mask;
+    uc16 value;
+    bool determines_perfectly;
+  };
+  int characters() { return characters_; }
+  void set_characters(int characters) { characters_ = characters; }
+  Position* positions(int index) {
+    ASSERT(index >= 0);
+    ASSERT(index < characters_);
+    return positions_ + index;
+  }
+  uint32_t mask() { return mask_; }
+  uint32_t value() { return value_; }
+
+ private:
+  // How many characters do we have quick check information from.  This is
+  // the same for all branches of a choice node.
+  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) { }
-  virtual ~RegExpNode() { }
+  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;
+  // 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,
+                      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;
 
-  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_; }
 
   void AddSibling(RegExpNode* node) { siblings_.Add(node); }
 
@@ skipping 63 matching lines @@
   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);
   virtual void Accept(NodeVisitor* visitor);
   virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant);
-  virtual RegExpNode* ExpandLocal(NodeInfo* info);
-  virtual void ExpandChildren();
+  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;
@@ skipping 25 matching lines @@
       : 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 RegExpNode* ExpandLocal(NodeInfo* info);
-  virtual void ExpandChildren();
   virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant);
+  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:
-  void ExpandAtomChildren(RegExpAtom* that);
-  void ExpandCharClassChildren(RegExpCharacterClass* that);
-
+  enum TextEmitPassType {
+    NON_ASCII_MATCH,
+    CHARACTER_MATCH,
+    CASE_CHARACTER_MATCH,
+    CHARACTER_CLASS_MATCH
+  };
+  void TextEmitPass(RegExpCompiler* compiler,
+                    TextEmitPassType pass,
+                    bool preloaded,
+                    GenerationVariant* variant,
+                    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 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 RegExpNode* ExpandLocal(NodeInfo* info);
-  virtual void ExpandChildren();
   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 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 RegExpNode* ExpandLocal(NodeInfo* info);
-  virtual void ExpandChildren();
   virtual EndNode* Clone() { return new EndNode(*this); }
 
  protected:
   void EmitInfoChecks(RegExpMacroAssembler* macro, GenerationVariant* variant);
 
  private:
   Action action_;
 };
 
 
@@ skipping 36 matching lines @@
   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)),
         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 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 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; }
 
  protected:
   int GreedyLoopTextLength(GuardedAlternative *alternative);
   ZoneList<GuardedAlternative>* alternatives_;
 
  private:
   friend class DispatchTableConstructor;
-  friend class AssertionPropagation;
+  friend class Analysis;
   void GenerateGuard(RegExpMacroAssembler* macro_assembler,
                      Guard *guard,
                      GenerationVariant* variant);
+  int CalculatePreloadCharacters(RegExpCompiler* compiler);
+  bool EmitOutOfLineContinuation(RegExpCompiler* compiler,
+                                 GenerationVariant* variant,
+                                 GuardedAlternative alternative,
+                                 AlternativeGeneration* alt_gen,
+                                 int preload_characters,
+                                 bool next_expects_preload);
   DispatchTable* table_;
   bool being_calculated_;
 };
 
 
 class LoopChoiceNode: public ChoiceNode {
  public:
-  explicit LoopChoiceNode(int expected_size) : ChoiceNode(expected_size) { }
+  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 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 {
  public:
   class DeferredAction {
    public:
@@ skipping 29 matching lines @@
    private:
     int value_;
   };
 
   class DeferredIncrementRegister: public DeferredAction {
    public:
     explicit DeferredIncrementRegister(int reg)
         : DeferredAction(ActionNode::INCREMENT_REGISTER, reg) { }
   };
 
-  explicit GenerationVariant(Label* backtrack)
-      : cp_offset_(0),
-        actions_(NULL),
-        backtrack_(backtrack),
-        stop_node_(NULL),
-        loop_label_(NULL) { }
   GenerationVariant()
       : cp_offset_(0),
         actions_(NULL),
         backtrack_(NULL),
         stop_node_(NULL),
-        loop_label_(NULL) { }
+        loop_label_(NULL),
+        characters_preloaded_(0) { }
   bool Flush(RegExpCompiler* compiler, RegExpNode* successor);
   int cp_offset() { return cp_offset_; }
   DeferredAction* actions() { return actions_; }
   bool is_trivial() {
-    return backtrack_ == NULL && actions_ == NULL && cp_offset_ == 0;
+    return backtrack_ == NULL &&
+           actions_ == NULL &&
+           cp_offset_ == 0 &&
+           characters_preloaded_ == 0 &&
+           quick_check_performed_.characters() == 0;
   }
   Label* backtrack() { return backtrack_; }
   Label* loop_label() { return loop_label_; }
   RegExpNode* stop_node() { return stop_node_; }
-  // These set methods should be used only on new GenerationVariants - the
-  // intention is that GenerationVariants are immutable after creation.
+  int characters_preloaded() { return characters_preloaded_; }
+  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.
   void add_action(DeferredAction* new_action) {
     ASSERT(new_action->next_ == NULL);
     new_action->next_ = actions_;
     actions_ = new_action;
   }
-  void set_cp_offset(int new_cp_offset) {
-    ASSERT(new_cp_offset >= cp_offset_);
-    cp_offset_ = new_cp_offset;
-  }
   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; }
-  bool mentions_reg(int reg);
+  void set_characters_preloaded(int cpre) { characters_preloaded_ = cpre; }
+  void set_quick_check_performed(QuickCheckDetails* d) {
+    quick_check_performed_ = *d;
+  }
+  void clear_quick_check_performed() {
+  }
+  void AdvanceVariant(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,
                              OutSet& affected_registers);
   int cp_offset_;
   DeferredAction* actions_;
   Label* backtrack_;
   RegExpNode* stop_node_;
   Label* loop_label_;
+  int characters_preloaded_;
+  QuickCheckDetails quick_check_performed_;
 };
+
+
 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
+  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),
         choice_index_(-1),
@@ skipping 27 matching lines @@
 // 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 {
+class Analysis: public NodeVisitor {
  public:
-  explicit AssertionPropagation(bool ignore_case)
+  explicit Analysis(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
+  virtual void VisitLoopChoice(LoopChoiceNode* that);
 
  private:
   bool ignore_case_;
 
-  DISALLOW_IMPLICIT_CONSTRUCTORS(AssertionPropagation);
+  DISALLOW_IMPLICIT_CONSTRUCTORS(Analysis);
 };
 
 
 struct RegExpCompileData {
   RegExpCompileData()
     : tree(NULL),
       node(NULL),
-      has_lookbehind(false),
       simple(true),
       capture_count(0) { }
   RegExpTree* tree;
   RegExpNode* node;
-  bool has_lookbehind;
   bool simple;
   Handle<String> error;
   int capture_count;
 };
 
 
 class RegExpEngine: public AllStatic {
  public:
   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_