src/jsregexp.h - Issue 12900: Irregexp:...

Unified Diff: src/jsregexp.h

Issue 12900: Irregexp:... (Closed) Base URL: http://v8.googlecode.com/svn/branches/bleeding_edge/

Patch Set: '' Created 12 years ago

Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.

Jump to:

View side-by-side diff with in-line comments

Index: src/jsregexp.h

===================================================================

--- src/jsregexp.h (revision 927)

+++ src/jsregexp.h (working copy)

@@ -346,6 +346,7 @@

uint32_t first_;

ZoneList<unsigned>* remaining_;

ZoneList<OutSet*>* successors_;

+ friend class GenerationVariant;

};

@@ -432,7 +433,7 @@

public:

enum Type {UNINITIALIZED, ATOM, CHAR_CLASS};

TextElement() : type(UNINITIALIZED) { }

- explicit TextElement(Type t) : type(t) { }

+ explicit TextElement(Type t) : type(t), cp_offset(-1) { }

static TextElement Atom(RegExpAtom* atom);

static TextElement CharClass(RegExpCharacterClass* char_class);

Type type;

@@ -440,9 +441,13 @@

RegExpAtom* u_atom;

RegExpCharacterClass* u_char_class;

} data;

+ int cp_offset;

};

+class GenerationVariant;

struct NodeInfo {

enum TriBool {

UNKNOWN = -1, FALSE = 0, TRUE = 1

@@ -607,18 +612,18 @@

class RegExpNode: public ZoneObject {

public:

+ RegExpNode() : variants_generated_(0) { }

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 GoTo(RegExpCompiler* compiler);

- Label* label();

+ virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant) = 0;

+ static const int kNodeIsTooComplexForGreedyLoops = -1;

+ virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; }

+ Label* label() { return &label_; }

+ static const int kMaxVariantsGenerated = 10;

- // Until the implementation is complete we will return true for success and

- // false for failure.

- virtual bool Emit(RegExpCompiler* compiler) = 0;

RegExpNode* EnsureExpanded(NodeInfo* info);

virtual RegExpNode* ExpandLocal(NodeInfo* info) = 0;

virtual void ExpandChildren() = 0;

@@ -630,7 +635,6 @@

virtual RegExpNode* PropagateForward(NodeInfo* info) = 0;

NodeInfo* info() { return &info_; }

- virtual bool IsBacktrack() { return false; }

void AddSibling(RegExpNode* node) { siblings_.Add(node); }

@@ -645,6 +649,9 @@

void set_siblings(SiblingList* other) { siblings_ = *other; }

protected:

+ enum LimitResult { DONE, FAIL, CONTINUE };

+ LimitResult LimitVersions(RegExpCompiler* compiler,

+ GenerationVariant* variant);

// Returns a sibling of this node whose interests and assumptions

// match the ones in the given node info. If no sibling exists NULL

@@ -663,12 +670,11 @@

// processed before it is on a useable state.

virtual RegExpNode* Clone() = 0;

- inline void Bind(RegExpMacroAssembler* macro);

private:

Label label_;

NodeInfo info_;

SiblingList siblings_;

+ int variants_generated_;

};

@@ -678,7 +684,6 @@

: on_success_(on_success) { }

RegExpNode* on_success() { return on_success_; }

void set_on_success(RegExpNode* node) { on_success_ = node; }

- virtual bool Emit(RegExpCompiler* compiler) { return false; }

private:

RegExpNode* on_success_;

};

@@ -687,29 +692,31 @@

class ActionNode: public SeqRegExpNode {

public:

enum Type {

- STORE_REGISTER,

+ SET_REGISTER,

INCREMENT_REGISTER,

STORE_POSITION,

- RESTORE_POSITION,

BEGIN_SUBMATCH,

- ESCAPE_SUBMATCH

+ POSITIVE_SUBMATCH_SUCCESS

};

- static ActionNode* StoreRegister(int reg, int val, RegExpNode* on_success);

+ 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* RestorePosition(int reg, RegExpNode* on_success);

- static ActionNode* BeginSubmatch(int stack_pointer_reg,

- int position_reg,

- RegExpNode* on_success);

- static ActionNode* EscapeSubmatch(int stack_pointer_reg,

- bool and_restore_position,

- int restore_reg,

- 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,

+ RegExpNode* on_success);

virtual void Accept(NodeVisitor* visitor);

- virtual bool Emit(RegExpCompiler* compiler);

+ virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant);

virtual RegExpNode* ExpandLocal(NodeInfo* info);

virtual void ExpandChildren();

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:

@@ -740,16 +747,12 @@

class TextNode: public SeqRegExpNode {

public:

TextNode(ZoneList<TextElement>* elms,

- RegExpNode* on_success,

- RegExpNode* on_failure)

+ RegExpNode* on_success)

: SeqRegExpNode(on_success),

- on_failure_(on_failure),

elms_(elms) { }

TextNode(RegExpCharacterClass* that,

- RegExpNode* on_success,

- RegExpNode* on_failure)

+ RegExpNode* on_success)

: SeqRegExpNode(on_success),

- on_failure_(on_failure),

elms_(new ZoneList<TextElement>(1)) {

elms_->Add(TextElement::CharClass(that));

}

@@ -757,17 +760,20 @@

virtual RegExpNode* PropagateForward(NodeInfo* info);

virtual RegExpNode* ExpandLocal(NodeInfo* info);

virtual void ExpandChildren();

- RegExpNode* on_failure() { return on_failure_; }

- virtual bool Emit(RegExpCompiler* compiler);

+ virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant);

ZoneList<TextElement>* elements() { return elms_; }

void MakeCaseIndependent();

- virtual TextNode* Clone() { return new TextNode(*this); }

+ 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);

- RegExpNode* on_failure_;

ZoneList<TextElement>* elms_;

};

@@ -776,24 +782,20 @@

public:

BackReferenceNode(int start_reg,

int end_reg,

- RegExpNode* on_success,

- RegExpNode* on_failure)

+ RegExpNode* on_success)

: 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 bool Emit(RegExpCompiler* compiler, GenerationVariant* variant);

virtual RegExpNode* PropagateForward(NodeInfo* info);

virtual RegExpNode* ExpandLocal(NodeInfo* info);

virtual void ExpandChildren();

virtual BackReferenceNode* Clone() { return new BackReferenceNode(*this); }

private:

- RegExpNode* on_failure_;

int start_reg_;

int end_reg_;

};

@@ -801,22 +803,37 @@

class EndNode: public RegExpNode {

public:

- enum Action { ACCEPT, BACKTRACK };

+ enum Action { ACCEPT, BACKTRACK, NEGATIVE_SUBMATCH_SUCCESS };

explicit EndNode(Action action) : action_(action) { }

virtual void Accept(NodeVisitor* visitor);

- virtual bool Emit(RegExpCompiler* compiler);

+ virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant);

virtual RegExpNode* PropagateForward(NodeInfo* info);

virtual RegExpNode* ExpandLocal(NodeInfo* info);

virtual void ExpandChildren();

- virtual bool IsBacktrack() { return action_ == BACKTRACK; }

- virtual bool GoTo(RegExpCompiler* compiler);

virtual EndNode* Clone() { return new EndNode(*this); }

+ protected:

+ void EmitInfoChecks(RegExpMacroAssembler* macro, GenerationVariant* variant);

private:

Action action_;

};

+class NegativeSubmatchSuccess: public EndNode {

+ public:

+ NegativeSubmatchSuccess(int stack_pointer_reg, int position_reg)

+ : EndNode(NEGATIVE_SUBMATCH_SUCCESS),

+ stack_pointer_register_(stack_pointer_reg),

+ current_position_register_(position_reg) { }

+ virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant);

+ private:

+ int stack_pointer_register_;

+ int current_position_register_;

+};

class Guard: public ZoneObject {

public:

enum Relation { LT, GEQ };

@@ -851,17 +868,15 @@

class ChoiceNode: public RegExpNode {

public:

- explicit ChoiceNode(int expected_size, RegExpNode* on_failure)

- : on_failure_(on_failure),

- alternatives_(new ZoneList<GuardedAlternative>(expected_size)),

+ 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);

- RegExpNode* on_failure() { return on_failure_; }

- virtual bool Emit(RegExpCompiler* compiler);

+ virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant);

virtual RegExpNode* PropagateForward(NodeInfo* info);

virtual RegExpNode* ExpandLocal(NodeInfo* info);

virtual void ExpandChildren();

@@ -870,19 +885,128 @@

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;

void GenerateGuard(RegExpMacroAssembler* macro_assembler,

Guard *guard,

- Label* on_failure);

- RegExpNode* on_failure_;

- ZoneList<GuardedAlternative>* alternatives_;

+ GenerationVariant* variant);

DispatchTable* table_;

bool being_calculated_;

};

+class LoopChoiceNode: public ChoiceNode {

+ public:

+ explicit LoopChoiceNode(int expected_size) : ChoiceNode(expected_size) { }

+ virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant);

+ virtual LoopChoiceNode* Clone() { return new LoopChoiceNode(*this); }

+};

+// 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 {

Christian Plesner Hansen 2008/12/08 08:54:19 Not a fan of this name though I can't think of any

+ public:

+ class DeferredAction {

+ public:

+ DeferredAction(ActionNode::Type type, int reg)

+ : type_(type), reg_(reg), next_(NULL) { }

+ DeferredAction* next() { return next_; }

+ int reg() { return reg_; }

+ ActionNode::Type type() { return type_; }

+ private:

+ ActionNode::Type type_;

+ int reg_;

+ DeferredAction* next_;

+ friend class GenerationVariant;

+ };

+ class DeferredCapture: public DeferredAction {

+ public:

+ DeferredCapture(int reg, GenerationVariant* variant)

+ : DeferredAction(ActionNode::STORE_POSITION, reg),

+ cp_offset_(variant->cp_offset()) { }

+ int cp_offset() { return cp_offset_; }

+ private:

+ int cp_offset_;

+ void set_cp_offset(int cp_offset) { cp_offset_ = cp_offset; }

+ };

+ class DeferredSetRegister :public DeferredAction {

+ public:

+ DeferredSetRegister(int reg, int value)

+ : DeferredAction(ActionNode::SET_REGISTER, reg),

+ value_(value) { }

+ int value() { return value_; }

+ 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) { }

+ 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;

+ }

+ 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.

+ 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);

+ 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_;

+};

class NodeVisitor {

public:

virtual ~NodeVisitor() { }

@@ -956,7 +1080,8 @@

static Handle<FixedArray> Compile(RegExpParseResult* input,

RegExpNode** node_return,

bool ignore_case,

- bool multiline);

+ bool multiline,

+ Handle<String> pattern);

static void DotPrint(const char* label, RegExpNode* node, bool ignore_case);

};

« no previous file with comments | « src/interpreter-irregexp.cc ('k') | src/jsregexp.cc » ('j') | src/jsregexp.cc » ('J')