Enabled new regular expression engine.
Made a number of changes to the debugger protocol.
Fixed a number of bugs in the preemption support.
Added -p option to the developer shell to run files in parallel using preemption.
Fixed a number of minor bugs (including issues 176, 187, 189, 192, 193, 198 and 201).
Fixed a number of bugs in the serialization/deserialization support for the ARM platform.
git-svn-id: http://v8.googlecode.com/svn/trunk@1172 ce2b1a6d-e550-0410-aec6-3dcde31c8c00
diff --git a/src/jsregexp.h b/src/jsregexp.h
index bf3bdb7..0783727 100644
--- a/src/jsregexp.h
+++ b/src/jsregexp.h
@@ -410,6 +410,7 @@
VISIT(Action) \
VISIT(Choice) \
VISIT(BackReference) \
+ VISIT(Assertion) \
VISIT(Text)
@@ -587,12 +588,12 @@
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, Trace* trace) = 0;
+ virtual void Emit(RegExpCompiler* compiler, Trace* trace) = 0;
// How many characters must this node consume at a minimum in order to
- // succeed.
- virtual int EatsAtLeast(int recursion_depth) = 0;
+ // succeed. If we have found at least 'still_to_find' characters that
+ // must be consumed there is no need to ask any following nodes whether
+ // they are sure to eat any more characters.
+ virtual int EatsAtLeast(int still_to_find, 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.
@@ -619,12 +620,6 @@
// the deferred actions in the current trace and generating a goto.
static const int kMaxCopiesCodeGenerated = 10;
- // 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); }
@@ -640,7 +635,7 @@
void set_siblings(SiblingList* other) { siblings_ = *other; }
protected:
- enum LimitResult { DONE, FAIL, CONTINUE };
+ enum LimitResult { DONE, CONTINUE };
LimitResult LimitVersions(RegExpCompiler* compiler, Trace* trace);
// Returns a sibling of this node whose interests and assumptions
@@ -724,27 +719,30 @@
};
static ActionNode* SetRegister(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* StorePosition(int reg,
+ bool is_capture,
+ RegExpNode* on_success);
static ActionNode* ClearCaptures(Interval range, RegExpNode* on_success);
static ActionNode* BeginSubmatch(int stack_pointer_reg,
int position_reg,
RegExpNode* on_success);
static ActionNode* PositiveSubmatchSuccess(int stack_pointer_reg,
int restore_reg,
+ int clear_capture_count,
+ int clear_capture_from,
RegExpNode* on_success);
static ActionNode* EmptyMatchCheck(int start_register,
int repetition_register,
int repetition_limit,
RegExpNode* on_success);
virtual void Accept(NodeVisitor* visitor);
- virtual bool Emit(RegExpCompiler* compiler, Trace* trace);
- virtual int EatsAtLeast(int recursion_depth);
+ 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);
}
- 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; }
@@ -761,10 +759,13 @@
} u_increment_register;
struct {
int reg;
+ bool is_capture;
} u_position_register;
struct {
int stack_pointer_register;
int current_position_register;
+ int clear_register_count;
+ int clear_register_from;
} u_submatch;
struct {
int start_register;
@@ -797,9 +798,8 @@
elms_->Add(TextElement::CharClass(that));
}
virtual void Accept(NodeVisitor* visitor);
- virtual RegExpNode* PropagateForward(NodeInfo* info);
- virtual bool Emit(RegExpCompiler* compiler, Trace* trace);
- virtual int EatsAtLeast(int recursion_depth);
+ 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);
@@ -831,6 +831,47 @@
};
+class AssertionNode: public SeqRegExpNode {
+ public:
+ enum AssertionNodeType {
+ AT_END,
+ AT_START,
+ AT_BOUNDARY,
+ AT_NON_BOUNDARY,
+ AFTER_NEWLINE
+ };
+ static AssertionNode* AtEnd(RegExpNode* on_success) {
+ return new AssertionNode(AT_END, on_success);
+ }
+ static AssertionNode* AtStart(RegExpNode* on_success) {
+ return new AssertionNode(AT_START, on_success);
+ }
+ static AssertionNode* AtBoundary(RegExpNode* on_success) {
+ return new AssertionNode(AT_BOUNDARY, on_success);
+ }
+ static AssertionNode* AtNonBoundary(RegExpNode* on_success) {
+ 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);
+ }
+ 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,
@@ -842,14 +883,13 @@
virtual void Accept(NodeVisitor* visitor);
int start_register() { return start_reg_; }
int end_register() { return end_reg_; }
- virtual bool Emit(RegExpCompiler* compiler, Trace* trace);
- virtual int EatsAtLeast(int recursion_depth) { return 0; }
+ 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) {
return;
}
- virtual RegExpNode* PropagateForward(NodeInfo* info);
virtual BackReferenceNode* Clone() { return new BackReferenceNode(*this); }
private:
@@ -863,20 +903,16 @@
enum Action { ACCEPT, BACKTRACK, NEGATIVE_SUBMATCH_SUCCESS };
explicit EndNode(Action action) : action_(action) { }
virtual void Accept(NodeVisitor* visitor);
- virtual bool Emit(RegExpCompiler* compiler, Trace* trace);
- virtual int EatsAtLeast(int recursion_depth) { return 0; }
+ 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) {
// Returning 0 from EatsAtLeast should ensure we never get here.
UNREACHABLE();
}
- virtual RegExpNode* PropagateForward(NodeInfo* info);
virtual EndNode* Clone() { return new EndNode(*this); }
- protected:
- void EmitInfoChecks(RegExpMacroAssembler* macro, Trace* trace);
-
private:
Action action_;
};
@@ -884,15 +920,22 @@
class NegativeSubmatchSuccess: public EndNode {
public:
- NegativeSubmatchSuccess(int stack_pointer_reg, int position_reg)
+ NegativeSubmatchSuccess(int stack_pointer_reg,
+ int position_reg,
+ int clear_capture_count,
+ int clear_capture_start)
: EndNode(NEGATIVE_SUBMATCH_SUCCESS),
stack_pointer_register_(stack_pointer_reg),
- current_position_register_(position_reg) { }
- virtual bool Emit(RegExpCompiler* compiler, Trace* trace);
+ current_position_register_(position_reg),
+ clear_capture_count_(clear_capture_count),
+ clear_capture_start_(clear_capture_start) { }
+ virtual void Emit(RegExpCompiler* compiler, Trace* trace);
private:
int stack_pointer_register_;
int current_position_register_;
+ int clear_capture_count_;
+ int clear_capture_start_;
};
@@ -941,17 +984,19 @@
void AddAlternative(GuardedAlternative node) { alternatives()->Add(node); }
ZoneList<GuardedAlternative>* alternatives() { return alternatives_; }
DispatchTable* GetTable(bool ignore_case);
- virtual bool Emit(RegExpCompiler* compiler, Trace* trace);
- virtual int EatsAtLeast(int recursion_depth);
- int EatsAtLeastHelper(int recursion_depth, RegExpNode* ignore_this_node);
+ 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);
- virtual RegExpNode* PropagateForward(NodeInfo* info);
virtual ChoiceNode* Clone() { return new ChoiceNode(*this); }
bool being_calculated() { return being_calculated_; }
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);
@@ -964,7 +1009,7 @@
Guard *guard,
Trace* trace);
int CalculatePreloadCharacters(RegExpCompiler* compiler);
- bool EmitOutOfLineContinuation(RegExpCompiler* compiler,
+ void EmitOutOfLineContinuation(RegExpCompiler* compiler,
Trace* trace,
GuardedAlternative alternative,
AlternativeGeneration* alt_gen,
@@ -975,6 +1020,27 @@
};
+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);
+ // 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)
@@ -984,8 +1050,8 @@
body_can_be_zero_length_(body_can_be_zero_length) { }
void AddLoopAlternative(GuardedAlternative alt);
void AddContinueAlternative(GuardedAlternative alt);
- virtual bool Emit(RegExpCompiler* compiler, Trace* trace);
- virtual int EatsAtLeast(int recursion_depth); // Returns 0.
+ 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);
@@ -1037,18 +1103,21 @@
friend class Trace;
};
- class DeferredCapture: public DeferredAction {
+ class DeferredCapture : public DeferredAction {
public:
- DeferredCapture(int reg, Trace* trace)
+ DeferredCapture(int reg, bool is_capture, Trace* trace)
: DeferredAction(ActionNode::STORE_POSITION, reg),
- cp_offset_(trace->cp_offset()) { }
+ cp_offset_(trace->cp_offset()),
+ is_capture_(is_capture) { }
int cp_offset() { return cp_offset_; }
+ bool is_capture() { return is_capture_; }
private:
int cp_offset_;
+ bool is_capture_;
void set_cp_offset(int cp_offset) { cp_offset_ = cp_offset; }
};
- class DeferredSetRegister :public DeferredAction {
+ class DeferredSetRegister : public DeferredAction {
public:
DeferredSetRegister(int reg, int value)
: DeferredAction(ActionNode::SET_REGISTER, reg),
@@ -1068,7 +1137,7 @@
Interval range_;
};
- class DeferredIncrementRegister: public DeferredAction {
+ class DeferredIncrementRegister : public DeferredAction {
public:
explicit DeferredIncrementRegister(int reg)
: DeferredAction(ActionNode::INCREMENT_REGISTER, reg) { }
@@ -1086,7 +1155,7 @@
// 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.
- bool Flush(RegExpCompiler* compiler, RegExpNode* successor);
+ 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
@@ -1133,20 +1202,19 @@
void set_quick_check_performed(QuickCheckDetails* d) {
quick_check_performed_ = *d;
}
- void clear_quick_check_performed() {
- }
- void AdvanceCurrentPositionInTrace(int by, bool ascii);
+ void InvalidateCurrentCharacter();
+ void AdvanceCurrentPositionInTrace(int by, RegExpCompiler* compiler);
private:
int FindAffectedRegisters(OutSet* affected_registers);
void PerformDeferredActions(RegExpMacroAssembler* macro,
int max_register,
- OutSet& affected_registers);
+ OutSet& affected_registers,
+ OutSet* registers_to_pop,
+ OutSet* registers_to_clear);
void RestoreAffectedRegisters(RegExpMacroAssembler* macro,
int max_register,
- OutSet& affected_registers);
- void PushAffectedRegisters(RegExpMacroAssembler* macro,
- int max_register,
- OutSet& affected_registers);
+ OutSet& registers_to_pop,
+ OutSet& registers_to_clear);
int cp_offset_;
DeferredAction* actions_;
Label* backtrack_;