Irregexp: Added derived knowledge of whether we are at the start of input.

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 436 matching lines @@
     RegExpCharacterClass* u_char_class;
   } data;
   int cp_offset;
 };
 
 
 class Trace;
 
 
 struct NodeInfo {
-  enum TriBool {
-    UNKNOWN = -1, FALSE = 0, TRUE = 1
-  };
-
   NodeInfo()
       : being_analyzed(false),
         been_analyzed(false),
         follows_word_interest(false),
         follows_newline_interest(false),
         follows_start_interest(false),
         at_end(false),
         visited(false) { }
 
   // Returns true if the interests and assumptions of this node
@@ skipping 66 matching lines @@
 };
 
 
 // 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) { }
+        value_(0),
+        cannot_match_(false) { }
   explicit QuickCheckDetails(int characters)
       : characters_(characters),
         mask_(0),
-        value_(0) { }
+        value_(0),
+        cannot_match_(false) { }
   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();
+  bool cannot_match() { return cannot_match_; }
+  void set_cannot_match() { cannot_match_ = true; }
   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_;
+  // If set to true, there is no way this quick check can match at all.
+  // E.g., if it requires to be at the start of the input, and isn't.
+  bool cannot_match_;
 };
 
 
 class RegExpNode: public ZoneObject {
  public:
   RegExpNode() : trace_count_(0) { }
   virtual ~RegExpNode();
   virtual void Accept(NodeVisitor* visitor) = 0;
   // Generates a goto to this node or actually generates the code at this point.
   virtual void Emit(RegExpCompiler* compiler, Trace* trace) = 0;
@@ skipping 10 matching lines @@
                       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;
+                                    int characters_filled_in,
+                                    bool not_at_start) = 0;
   static const int kNodeIsTooComplexForGreedyLoops = -1;
   virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; }
   Label* label() { return &label_; }
   // If non-generic code is generated for a node (ie the node is not at the
   // start of the trace) then it cannot be reused.  This variable sets a limit
   // on how often we allow that to happen before we insist on starting a new
   // trace and generating generic code for a node that can be reused by flushing
   // the deferred actions in the current trace and generating a goto.
   static const int kMaxCopiesCodeGenerated = 10;
 
@@ skipping 110 matching lines @@
                                              RegExpNode* on_success);
   static ActionNode* EmptyMatchCheck(int start_register,
                                      int repetition_register,
                                      int repetition_limit,
                                      RegExpNode* on_success);
   virtual void Accept(NodeVisitor* visitor);
   virtual void Emit(RegExpCompiler* compiler, Trace* trace);
   virtual int EatsAtLeast(int still_to_find, int recursion_depth);
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
-                                    int filled_in) {
-    return on_success()->GetQuickCheckDetails(details, compiler, filled_in);
+                                    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); }
 
  private:
   union {
     struct {
       int reg;
@@ skipping 40 matching lines @@
            RegExpNode* on_success)
       : SeqRegExpNode(on_success),
         elms_(new ZoneList<TextElement>(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);
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
-                                    int characters_filled_in);
+                                    int characters_filled_in,
+                                    bool not_at_start);
   ZoneList<TextElement>* elements() { return elms_; }
   void MakeCaseIndependent();
   virtual int GreedyLoopTextLength();
   virtual TextNode* Clone() {
     TextNode* result = new TextNode(*this);
     result->CalculateOffsets();
     return result;
   }
   void CalculateOffsets();
 
@@ skipping 37 matching lines @@
     return new AssertionNode(AT_NON_BOUNDARY, on_success);
   }
   static AssertionNode* AfterNewline(RegExpNode* on_success) {
     return new AssertionNode(AFTER_NEWLINE, on_success);
   }
   virtual void Accept(NodeVisitor* visitor);
   virtual void Emit(RegExpCompiler* compiler, Trace* trace);
   virtual int EatsAtLeast(int still_to_find, int recursion_depth);
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
-                                    int filled_in) {
-    return on_success()->GetQuickCheckDetails(details, compiler, filled_in);
-  }
+                                    int filled_in,
+                                    bool not_at_start);
   virtual AssertionNode* Clone() { return new AssertionNode(*this); }
   AssertionNodeType type() { return type_; }
  private:
   AssertionNode(AssertionNodeType t, RegExpNode* on_success)
       : SeqRegExpNode(on_success), type_(t) { }
   AssertionNodeType type_;
 };
 
 
 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 void Emit(RegExpCompiler* compiler, Trace* trace);
   virtual int EatsAtLeast(int still_to_find, int recursion_depth);
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
-                                    int characters_filled_in) {
+                                    int characters_filled_in,
+                                    bool not_at_start) {
     return;
   }
   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 void Emit(RegExpCompiler* compiler, Trace* trace);
   virtual int EatsAtLeast(int still_to_find, int recursion_depth) { return 0; }
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
-                                    int characters_filled_in) {
+                                    int characters_filled_in,
+                                    bool not_at_start) {
     // Returning 0 from EatsAtLeast should ensure we never get here.
     UNREACHABLE();
   }
   virtual EndNode* Clone() { return new EndNode(*this); }
 
  private:
   Action action_;
 };
 
 
@@ skipping 51 matching lines @@
 
 
 class AlternativeGeneration;
 
 
 class ChoiceNode: public RegExpNode {
  public:
   explicit ChoiceNode(int expected_size)
       : alternatives_(new ZoneList<GuardedAlternative>(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);
   virtual void Emit(RegExpCompiler* compiler, Trace* trace);
   virtual int EatsAtLeast(int still_to_find, int recursion_depth);
   int EatsAtLeastHelper(int still_to_find,
                         int recursion_depth,
                         RegExpNode* ignore_this_node);
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
-                                    int characters_filled_in);
+                                    int characters_filled_in,
+                                    bool not_at_start);
   virtual ChoiceNode* Clone() { return new ChoiceNode(*this); }
 
   bool being_calculated() { return being_calculated_; }
+  bool not_at_start() { return not_at_start_; }
+  void set_not_at_start() { not_at_start_ = true; }
   void set_being_calculated(bool b) { being_calculated_ = b; }
   virtual bool try_to_emit_quick_check_for_alternative(int i) { return true; }
 
  protected:
   int GreedyLoopTextLength(GuardedAlternative *alternative);
   ZoneList<GuardedAlternative>* alternatives_;
 
  private:
   friend class DispatchTableConstructor;
   friend class Analysis;
   void GenerateGuard(RegExpMacroAssembler* macro_assembler,
                      Guard *guard,
                      Trace* trace);
   int CalculatePreloadCharacters(RegExpCompiler* compiler);
   void EmitOutOfLineContinuation(RegExpCompiler* compiler,
                                  Trace* trace,
                                  GuardedAlternative alternative,
                                  AlternativeGeneration* alt_gen,
                                  int preload_characters,
                                  bool next_expects_preload);
   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,
                                        GuardedAlternative then_do_this)
       : ChoiceNode(2) {
     AddAlternative(this_must_fail);
     AddAlternative(then_do_this);
   }
   virtual int EatsAtLeast(int still_to_find, int recursion_depth);
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
-                                    int characters_filled_in);
+                                    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; }
 };
 
 
 class LoopChoiceNode: public ChoiceNode {
  public:
   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 void Emit(RegExpCompiler* compiler, Trace* trace);
   virtual int EatsAtLeast(int still_to_find, int recursion_depth);
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
-                                    int characters_filled_in);
+                                    int characters_filled_in,
+                                    bool not_at_start);
   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 13 matching lines @@
 // generate code for paths that the matcher can take through the regular
 // expression.  A given node in the regexp can be code-generated several times
 // as it can be part of several traces.  For example for the regexp:
 // /foo(bar|ip)baz/ the code to match baz will be generated twice, once as part
 // of the foo-bar-baz trace and once as part of the foo-ip-baz trace.  The code
 // to match foo is generated only once (the traces have a common prefix).  The
 // code to store the capture is deferred and generated (twice) after the places
 // where baz has been matched.
 class Trace {
  public:
+  // A value for a property that is either known to be true, know to be false,
+  // or not known.
+  enum TriBool {
+    UNKNOWN = -1, FALSE = 0, TRUE = 1
+  };
+
   class DeferredAction {
    public:
     DeferredAction(ActionNode::Type type, int reg)
         : type_(type), reg_(reg), next_(NULL) { }
     DeferredAction* next() { return next_; }
     bool Mentions(int reg);
     int reg() { return reg_; }
     ActionNode::Type type() { return type_; }
    private:
     ActionNode::Type type_;
@@ skipping 42 matching lines @@
         : DeferredAction(ActionNode::INCREMENT_REGISTER, reg) { }
   };
 
   Trace()
       : cp_offset_(0),
         actions_(NULL),
         backtrack_(NULL),
         stop_node_(NULL),
         loop_label_(NULL),
         characters_preloaded_(0),
-        bound_checked_up_to_(0) { }
+        bound_checked_up_to_(0),
+        at_start_(UNKNOWN) { }
+
   // End the trace.  This involves flushing the deferred actions in the trace
   // and pushing a backtrack location onto the backtrack stack.  Once this is
   // done we can start a new trace or go to one that has already been
   // generated.
   void Flush(RegExpCompiler* compiler, RegExpNode* successor);
   int cp_offset() { return cp_offset_; }
   DeferredAction* actions() { return actions_; }
   // A trivial trace is one that has no deferred actions or other state that
   // affects the assumptions used when generating code.  There is no recorded
   // backtrack location in a trivial trace, so with a trivial trace we will
   // generate code that, on a failure to match, gets the backtrack location
   // from the backtrack stack rather than using a direct jump instruction.  We
   // always start code generation with a trivial trace and non-trivial traces
   // are created as we emit code for nodes or add to the list of deferred
   // actions in the trace.  The location of the code generated for a node using
   // a trivial trace is recorded in a label in the node so that gotos can be
   // generated to that code.
   bool is_trivial() {
     return backtrack_ == NULL &&
            actions_ == NULL &&
            cp_offset_ == 0 &&
            characters_preloaded_ == 0 &&
            bound_checked_up_to_ == 0 &&
-           quick_check_performed_.characters() == 0;
+           quick_check_performed_.characters() == 0 &&
+           at_start_ == UNKNOWN;
   }
+  TriBool at_start() { return at_start_; }
+  void set_at_start(bool at_start) { at_start_ = at_start ? TRUE : FALSE; }
   Label* backtrack() { return backtrack_; }
   Label* loop_label() { return loop_label_; }
   RegExpNode* stop_node() { return stop_node_; }
   int characters_preloaded() { return characters_preloaded_; }
   int bound_checked_up_to() { return bound_checked_up_to_; }
   QuickCheckDetails* quick_check_performed() { return &quick_check_performed_; }
   bool mentions_reg(int reg);
   // Returns true if a deferred position store exists to the specified
   // register and stores the offset in the out-parameter.  Otherwise
   // returns false.
@@ skipping 27 matching lines @@
                                 OutSet& registers_to_pop,
                                 OutSet& registers_to_clear);
   int cp_offset_;
   DeferredAction* actions_;
   Label* backtrack_;
   RegExpNode* stop_node_;
   Label* loop_label_;
   int characters_preloaded_;
   int bound_checked_up_to_;
   QuickCheckDetails quick_check_performed_;
+  TriBool at_start_;
 };
 
 
 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
@@ skipping 62 matching lines @@
 
   DISALLOW_IMPLICIT_CONSTRUCTORS(Analysis);
 };
 
 
 struct RegExpCompileData {
   RegExpCompileData()
     : tree(NULL),
       node(NULL),
       simple(true),
+      contains_anchor(false),
       capture_count(0) { }
   RegExpTree* tree;
   RegExpNode* node;
   bool simple;
+  bool contains_anchor;
   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_