Author: [EMAIL PROTECTED]
Date: Fri Nov 14 04:45:27 2008
New Revision: 755
Modified:
branches/experimental/regexp2000/src/ast.cc
branches/experimental/regexp2000/src/ast.h
branches/experimental/regexp2000/src/jsregexp-inl.h
branches/experimental/regexp2000/src/jsregexp.cc
branches/experimental/regexp2000/src/jsregexp.h
branches/experimental/regexp2000/src/string-stream.cc
branches/experimental/regexp2000/src/string-stream.h
branches/experimental/regexp2000/test/cctest/test-regexp.cc
Log:
- Split analysis into two separate visitors, one for filling out
dispatch tables and one for propagating information about nodes.
- Integrated dispatch table layout in dot graphs.
- Renamed choice/child nodes of disjunctions to alternatives, for
uniformity.
Modified: branches/experimental/regexp2000/src/ast.cc
==============================================================================
--- branches/experimental/regexp2000/src/ast.cc (original)
+++ branches/experimental/regexp2000/src/ast.cc Fri Nov 14 04:45:27 2008
@@ -233,9 +233,9 @@
void* RegExpUnparser::VisitDisjunction(RegExpDisjunction* that, void*
data) {
stream()->Add("(|");
- for (int i = 0; i < that->nodes()->length(); i++) {
+ for (int i = 0; i < that->alternatives()->length(); i++) {
stream()->Add(" ");
- that->nodes()->at(i)->Accept(this, data);
+ that->alternatives()->at(i)->Accept(this, data);
}
stream()->Add(")");
return NULL;
Modified: branches/experimental/regexp2000/src/ast.h
==============================================================================
--- branches/experimental/regexp2000/src/ast.h (original)
+++ branches/experimental/regexp2000/src/ast.h Fri Nov 14 04:45:27 2008
@@ -1225,15 +1225,16 @@
class RegExpDisjunction: public RegExpTree {
public:
- explicit RegExpDisjunction(ZoneList<RegExpTree*>* nodes) : nodes_(nodes)
{ }
+ explicit RegExpDisjunction(ZoneList<RegExpTree*>* alternatives)
+ : alternatives_(alternatives) { }
virtual void* Accept(RegExpVisitor* visitor, void* data);
virtual RegExpNode* ToNode(RegExpCompiler* compiler,
RegExpNode* on_success,
RegExpNode* on_failure);
virtual RegExpDisjunction* AsDisjunction();
- ZoneList<RegExpTree*>* nodes() { return nodes_; }
+ ZoneList<RegExpTree*>* alternatives() { return alternatives_; }
private:
- ZoneList<RegExpTree*>* nodes_;
+ ZoneList<RegExpTree*>* alternatives_;
};
@@ -1274,7 +1275,7 @@
RegExpCharacterClass(ZoneList<CharacterRange>* ranges, bool is_negated)
: ranges_(ranges),
is_negated_(is_negated) { }
- RegExpCharacterClass(uc16 type)
+ explicit RegExpCharacterClass(uc16 type)
: ranges_(new ZoneList<CharacterRange>(2)),
is_negated_(false) {
CharacterRange::AddClassEscape(type, ranges_);
Modified: branches/experimental/regexp2000/src/jsregexp-inl.h
==============================================================================
--- branches/experimental/regexp2000/src/jsregexp-inl.h (original)
+++ branches/experimental/regexp2000/src/jsregexp-inl.h Fri Nov 14 04:45:27
2008
@@ -245,10 +245,10 @@
template <typename Node, class Callback>
-static void DoForEach(Node* node, Callback callback) {
+static void DoForEach(Node* node, Callback* callback) {
if (node == NULL) return;
DoForEach<Node, Callback>(node->left(), callback);
- callback.Call(node->key(), node->value());
+ callback->Call(node->key(), node->value());
DoForEach<Node, Callback>(node->right(), callback);
}
Modified: branches/experimental/regexp2000/src/jsregexp.cc
==============================================================================
--- branches/experimental/regexp2000/src/jsregexp.cc (original)
+++ branches/experimental/regexp2000/src/jsregexp.cc Fri Nov 14 04:45:27
2008
@@ -788,14 +788,9 @@
// New regular expression engine
-class DotPrinter;
-
-
class RegExpCompiler {
public:
- explicit RegExpCompiler(int capture_count)
- : next_register_(2 * capture_count),
- work_list_(NULL) { }
+ explicit RegExpCompiler(int capture_count);
int AllocateRegister() { return next_register_++; }
@@ -806,10 +801,17 @@
inline void AddWork(RegExpNode* node) { work_list_->Add(node); }
- RegExpMacroAssembler* macro_assembler() {
- return macro_assembler_;
- }
+ static const int kImplementationOffset = 0;
+ static const int kNumberOfRegistersOffset = 0;
+ static const int kCodeOffset = 1;
+
+ RegExpMacroAssembler* macro_assembler() { return macro_assembler_; }
+ EndNode* accept() { return accept_; }
+ EndNode* backtrack() { return backtrack_; }
+
private:
+ EndNode* accept_;
+ EndNode* backtrack_;
int next_register_;
List<RegExpNode*>* work_list_;
RegExpMacroAssembler* macro_assembler_;
@@ -818,6 +820,14 @@
// Attempts to compile the regexp using a Regexp2000 code generator.
Returns
// a fixed array or a null handle depending on whether it succeeded.
+RegExpCompiler::RegExpCompiler(int capture_count)
+ : next_register_(2 * capture_count),
+ work_list_(NULL) {
+ accept_ = new EndNode(EndNode::ACCEPT);
+ backtrack_ = new EndNode(EndNode::BACKTRACK);
+}
+
+
Handle<FixedArray> RegExpCompiler::Assemble(
RegExpMacroAssembler* macro_assembler,
RegExpNode* start,
@@ -871,10 +881,6 @@
}
-EndNode EndNode::kAccept(ACCEPT);
-EndNode EndNode::kBacktrack(BACKTRACK);
-
-
bool EndNode::Emit(RegExpCompiler* compiler) {
switch (action_) {
case ACCEPT:
@@ -941,16 +947,6 @@
}
-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
-};
-
-
#define DEFINE_ACCEPT(Type) \
void Type##Node::Accept(NodeVisitor* visitor) { \
visitor->Visit##Type(this); \
@@ -1043,7 +1039,7 @@
break;
}
}
- stream()->Add("\"]; \n");
+ stream()->Add("\"];\n");
Visit(node);
stream()->Add("}\n");
printf("%s", *(stream()->ToCString()));
@@ -1059,42 +1055,77 @@
void DotPrinter::PrintOnFailure(RegExpNode* from, RegExpNode* on_failure) {
- if (on_failure == EndNode::GetBacktrack()) return;
+ if (on_failure->IsBacktrack()) return;
stream()->Add(" n%p -> n%p [style=dotted];\n", from, on_failure);
Visit(on_failure);
}
-void DotPrinter::VisitChoice(ChoiceNode* that) {
- stream()->Add(" n%p [label=\"? (%p)\"];\n", that, that);
- PrintOnFailure(that, that->on_failure());
- for (int i = 0; i < that->choices()->length(); i++) {
- GuardedAlternative alt = that->choices()->at(i);
- stream()->Add(" n%p -> n%p [label=\"%i",
- that,
- alt.node(),
- i);
- if (alt.guards() != NULL) {
- stream()->Add(" [");
- for (int j = 0; j < alt.guards()->length(); j++) {
- if (j > 0) stream()->Add(" ");
- Guard* guard = alt.guards()->at(j);
- switch (guard->op()) {
- case Guard::GEQ:
- stream()->Add("$%i ≥ %i", guard->reg(), guard->value());
- break;
- case Guard::LT:
- stream()->Add("$%i < %i", guard->reg(), guard->value());
- break;
- }
+class TableEntryBodyPrinter {
+ public:
+ TableEntryBodyPrinter(StringStream* stream, ChoiceNode* choice)
+ : stream_(stream), choice_(choice) { }
+ void Call(uc16 from, DispatchTable::Entry entry) {
+ OutSet* out_set = entry.out_set();
+ for (unsigned i = 0; i < OutSet::kFirstLimit; i++) {
+ if (out_set->Get(i)) {
+ stream()->Add(" n%p:s%io%i -> n%p;\n",
+ choice(),
+ from,
+ i,
+ choice()->alternatives()->at(i).node());
}
- stream()->Add("]");
}
- stream()->Add("\"];\n");
- that->choices()->at(i).node()->Accept(this);
}
- OS::PrintError("--- %p ---\n", static_cast<void*>(that));
- that->table()->Dump();
+ private:
+ StringStream* stream() { return stream_; }
+ ChoiceNode* choice() { return choice_; }
+ StringStream* stream_;
+ ChoiceNode* choice_;
+};
+
+
+class TableEntryHeaderPrinter {
+ public:
+ explicit TableEntryHeaderPrinter(StringStream* stream)
+ : first_(true), stream_(stream) { }
+ void Call(uc16 from, DispatchTable::Entry entry) {
+ if (first_) {
+ first_ = false;
+ } else {
+ stream()->Add("|");
+ }
+ stream()->Add("{%k-%k|{", from, from, entry.to());
+ OutSet* out_set = entry.out_set();
+ int priority = 0;
+ for (unsigned i = 0; i < OutSet::kFirstLimit; i++) {
+ if (out_set->Get(i)) {
+ if (priority > 0) stream()->Add("|");
+ stream()->Add("<s%io%i> %i", from, i, priority);
+ priority++;
+ }
+ }
+ stream()->Add("}}");
+ }
+ private:
+ bool first_;
+ StringStream* stream() { return stream_; }
+ StringStream* stream_;
+};
+
+
+void DotPrinter::VisitChoice(ChoiceNode* that) {
+ stream()->Add(" n%p [shape=Mrecord, label=\"", that);
+ TableEntryHeaderPrinter header_printer(stream());
+ that->table()->ForEach(&header_printer);
+ stream()->Add("\"]\n", that);
+ TableEntryBodyPrinter body_printer(stream(), that);
+ that->table()->ForEach(&body_printer);
+ PrintOnFailure(that, that->on_failure());
+ for (int i = 0; i < that->alternatives()->length(); i++) {
+ GuardedAlternative alt = that->alternatives()->at(i);
+ alt.node()->Accept(this);
+ }
}
@@ -1206,7 +1237,8 @@
void DispatchTable::Dump() {
HeapStringAllocator alloc;
StringStream stream(&alloc);
- tree()->ForEach(DispatchTableDumper(&stream));
+ DispatchTableDumper dumper(&stream);
+ tree()->ForEach(&dumper);
OS::PrintError("%s", *stream.ToCString());
}
@@ -1244,14 +1276,14 @@
RegExpNode* RegExpDisjunction::ToNode(RegExpCompiler* compiler,
RegExpNode* on_success,
RegExpNode* on_failure) {
- ZoneList<RegExpTree*>* children = nodes();
- int length = children->length();
+ ZoneList<RegExpTree*>* alternatives = this->alternatives();
+ int length = alternatives->length();
ChoiceNode* result = new ChoiceNode(length, on_failure);
for (int i = 0; i < length; i++) {
- GuardedAlternative child(children->at(i)->ToNode(compiler,
- on_success,
- on_failure));
- result->AddChild(child);
+ GuardedAlternative alternative(alternatives->at(i)->ToNode(compiler,
+ on_success,
+
on_failure));
+ result->AddAlternative(alternative);
}
return result;
}
@@ -1310,11 +1342,11 @@
rest_alt.AddGuard(rest_guard);
}
if (is_greedy) {
- center->AddChild(body_alt);
- center->AddChild(rest_alt);
+ center->AddAlternative(body_alt);
+ center->AddAlternative(rest_alt);
} else {
- center->AddChild(rest_alt);
- center->AddChild(body_alt);
+ center->AddAlternative(rest_alt);
+ center->AddAlternative(body_alt);
}
if (needs_counter) {
return ActionNode::StoreRegister(reg_ctr, 0, center);
@@ -1385,9 +1417,9 @@
new ChoiceNode(1, ActionNode::EndSubmatch(on_success));
RegExpNode* body_node = body()->ToNode(compiler,
ActionNode::EscapeSubmatch(on_failure),
- EndNode::GetBacktrack());
+ compiler->backtrack());
GuardedAlternative body_alt(body_node);
- try_node->AddChild(body_alt);
+ try_node->AddAlternative(body_alt);
return ActionNode::BeginSubmatch(try_node);
}
}
@@ -1654,78 +1686,115 @@
// Analysis
-class Analysis: public NodeVisitor {
- public:
- explicit Analysis(RegExpCompiler* compiler)
- : compiler_(compiler),
- table_(NULL),
- choice_index_(-1) { }
- DispatchTable* table() { return table_; }
- RegExpCompiler* compiler() { return compiler_; }
- int choice_index() { return choice_index_; }
- void Analyze(RegExpNode* node) { node->Accept(this); }
-#define DECLARE_VISIT(Type) \
- virtual void Visit##Type(Type##Node* that);
-FOR_EACH_NODE_TYPE(DECLARE_VISIT)
-#undef DECLARE_VISIT
- protected:
- explicit Analysis(Analysis* prev) { *this = *prev; }
- RegExpCompiler* compiler_;
- DispatchTable *table_;
- int choice_index_;
-};
+void Analysis::EnsureAnalyzed(RegExpNode* that) {
+ if (that->info()->been_analyzed || that->info()->being_analyzed)
+ return;
+ that->info()->being_analyzed = true;
+ that->Accept(this);
+ that->info()->being_analyzed = false;
+ that->info()->been_analyzed = true;
+}
-// A subclass of analysis data that allows fields to be set. Anyone
-// who needs to create new analysis data creates an instance of this
-// class, configures it, and then passes it on as an AnalysisData
-// which doesn't allow its fields to be changed.
-class AnalysisBuilder: public Analysis {
- public:
- explicit AnalysisBuilder(Analysis* prev) : Analysis(prev) { }
- void set_table(DispatchTable* value) { table_ = value; }
- void set_choice_index(int value) { choice_index_ = value; }
-};
+void Analysis::VisitEnd(EndNode* that) {
+ // nothing to do
+}
-void Analysis::VisitEnd(EndNode* that) {
+void Analysis::VisitAtom(AtomNode* that) {
+ EnsureAnalyzed(that->on_success());
+ EnsureAnalyzed(that->on_failure());
+}
+
+
+void Analysis::VisitAction(ActionNode* that) {
+ RegExpNode* next = that->on_success();
+ EnsureAnalyzed(next);
+ that->info()->propagate_line = next->info()->propagate_line;
+ that->info()->propagate_word = next->info()->propagate_word;
+}
+
+
+void Analysis::VisitChoice(ChoiceNode* that) {
+ NodeInfo* info = that->info();
+ for (int i = 0; i < that->alternatives()->length(); i++) {
+ RegExpNode* node = that->alternatives()->at(i).node();
+ EnsureAnalyzed(node);
+ info->propagate_line |= node->info()->propagate_line;
+ info->propagate_word |= node->info()->propagate_word;
+ }
+ if (!that->table_calculated()) {
+ DispatchTableConstructor cons(that->table());
+ cons.BuildTable(that);
+ }
+ EnsureAnalyzed(that->on_failure());
+}
+
+
+void Analysis::VisitBackreference(BackreferenceNode* that) {
+ EnsureAnalyzed(that->on_success());
+ EnsureAnalyzed(that->on_failure());
+}
+
+
+void Analysis::VisitCharacterClass(CharacterClassNode* that) {
+ EnsureAnalyzed(that->on_success());
+ EnsureAnalyzed(that->on_failure());
+}
+
+
+// -------------------------------------------------------------------
+// Dispatch table construction
+
+
+void DispatchTableConstructor::VisitEnd(EndNode* that) {
// nothing to do
}
+void DispatchTableConstructor::BuildTable(ChoiceNode* node) {
+ ASSERT(!node->table_calculated());
+ node->set_being_calculated(true);
+ ZoneList<GuardedAlternative>* alternatives = node->alternatives();
+ for (int i = 0; i < alternatives->length(); i++) {
+ set_choice_index(i);
+ alternatives->at(i).node()->Accept(this);
+ }
+ node->set_being_calculated(false);
+ node->set_table_calculated(true);
+}
+
+
class AddDispatchRange {
public:
- explicit AddDispatchRange(Analysis* analysis) : analysis_(analysis) { }
+ explicit AddDispatchRange(DispatchTableConstructor* constructor)
+ : constructor_(constructor) { }
void Call(uc32 from, DispatchTable::Entry entry);
private:
- Analysis* analysis_;
+ DispatchTableConstructor* constructor_;
};
void AddDispatchRange::Call(uc32 from, DispatchTable::Entry entry) {
CharacterRange range(from, entry.to());
- analysis_->table()->AddRange(range, analysis_->choice_index());
+ constructor_->AddRange(range);
}
-void Analysis::VisitChoice(ChoiceNode* node) {
- if (node->visited()) return;
- node->set_visited(true);
- ZoneList<GuardedAlternative>* choices = node->choices();
- AnalysisBuilder data(this);
- data.set_table(node->table());
- for (int i = 0; i < choices->length(); i++) {
- data.set_choice_index(i);
- data.Analyze(choices->at(i).node());
- }
- node->set_visited(false);
- if (table() != NULL) {
- data.table()->ForEach(AddDispatchRange(this));
+void DispatchTableConstructor::VisitChoice(ChoiceNode* node) {
+ if (node->being_calculated())
+ return;
+ if (!node->table_calculated()) {
+ DispatchTableConstructor constructor(node->table());
+ constructor.BuildTable(node);
}
+ ASSERT(node->table_calculated());
+ AddDispatchRange adder(this);
+ node->table()->ForEach(&adder);
}
-void Analysis::VisitBackreference(BackreferenceNode* that) {
+void DispatchTableConstructor::VisitBackreference(BackreferenceNode* that)
{
UNIMPLEMENTED();
}
@@ -1737,15 +1806,13 @@
}
-void CharacterClassNode::AddInverseToTable(ZoneList<CharacterRange>*
ranges,
- DispatchTable* table,
- int index) {
+void DispatchTableConstructor::AddInverse(ZoneList<CharacterRange>*
ranges) {
ranges->Sort(CompareRangeByFrom);
uc16 last = 0;
for (int i = 0; i < ranges->length(); i++) {
CharacterRange range = ranges->at(i);
if (last < range.from())
- table->AddRange(CharacterRange(last, range.from() - 1), index);
+ AddRange(CharacterRange(last, range.from() - 1));
if (range.to() >= last) {
if (range.to() == 0xFFFF) {
return;
@@ -1754,42 +1821,30 @@
}
}
}
- table->AddRange(CharacterRange(last, 0xFFFF), index);
+ AddRange(CharacterRange(last, 0xFFFF));
}
-void Analysis::VisitCharacterClass(CharacterClassNode* that) {
- if (table() != NULL) {
- int index = choice_index();
- ZoneList<CharacterRange>* ranges = that->ranges();
- if (that->is_negated()) {
- CharacterClassNode::AddInverseToTable(ranges, table(), index);
- } else {
- for (int i = 0; i < ranges->length(); i++) {
- CharacterRange range = ranges->at(i);
- table()->AddRange(range, index);
- }
+void DispatchTableConstructor::VisitCharacterClass(CharacterClassNode*
that) {
+ ZoneList<CharacterRange>* ranges = that->ranges();
+ if (that->is_negated()) {
+ AddInverse(ranges);
+ } else {
+ for (int i = 0; i < ranges->length(); i++) {
+ AddRange(ranges->at(i));
}
}
- AnalysisBuilder outgoing(this);
- outgoing.set_table(NULL);
- outgoing.Analyze(that->on_success());
}
-void Analysis::VisitAtom(AtomNode* that) {
- if (table() != NULL) {
- uc16 c = that->data()[0];
- table()->AddRange(CharacterRange(c, c), choice_index());
- }
- AnalysisBuilder outgoing(this);
- outgoing.set_table(NULL);
- outgoing.Analyze(that->on_success());
+void DispatchTableConstructor::VisitAtom(AtomNode* that) {
+ uc16 c = that->data()[0];
+ AddRange(CharacterRange(c, c));
}
-void Analysis::VisitAction(ActionNode* that) {
- Analyze(that->on_success());
+void DispatchTableConstructor::VisitAction(ActionNode* that) {
+ that->on_success()->Accept(this);
}
@@ -1801,8 +1856,8 @@
RegExpNode* captured_body = RegExpCapture::ToNode(input->tree,
0,
&compiler,
- EndNode::GetAccept(),
-
EndNode::GetBacktrack());
+ compiler.accept(),
+ compiler.backtrack());
// Add a .*? at the beginning, outside the body capture.
// Note: We could choose to not add this if the regexp is anchored at
// the start of the input but I'm not sure how best to do that and
@@ -1814,10 +1869,10 @@
new
RegExpCharacterClass('.'),
&compiler,
captured_body,
- EndNode::GetBacktrack());
+ compiler.backtrack());
if (node_return != NULL) *node_return = node;
- Analysis analysis(&compiler);
- analysis.Analyze(node);
+ Analysis analysis;
+ analysis.EnsureAnalyzed(node);
byte codes[10240];
Re2kAssembler assembler(Vector<byte>(codes, 1024));
RegExpMacroAssemblerRe2k macro_assembler(&assembler);
Modified: branches/experimental/regexp2000/src/jsregexp.h
==============================================================================
--- branches/experimental/regexp2000/src/jsregexp.h (original)
+++ branches/experimental/regexp2000/src/jsregexp.h Fri Nov 14 04:45:27 2008
@@ -205,7 +205,7 @@
template <typename Node, class Callback>
-static void DoForEach(Node* node, Callback callback);
+static void DoForEach(Node* node, Callback* callback);
// A zone splay tree. The config type parameter encapsulates the
@@ -297,7 +297,7 @@
};
template <class Callback>
- void ForEach(Callback c) {
+ void ForEach(Callback* c) {
DoForEach<typename ZoneSplayTree<Config>::Node, Callback>(root_, c);
}
@@ -376,7 +376,7 @@
void Dump();
template <typename Callback>
- void ForEach(Callback callback) { return tree()->ForEach(callback); }
+ void ForEach(Callback* callback) { return tree()->ForEach(callback); }
private:
// There can't be a static empty set since it allocates its
// successors in a zone and caches them.
@@ -396,6 +396,23 @@
VISIT(CharacterClass)
+class NodeInfo {
+ public:
+ NodeInfo()
+ : being_analyzed(false),
+ been_analyzed(false),
+ propagate_word(false),
+ propagate_line(false) { }
+ bool being_analyzed: 1;
+ bool been_analyzed: 1;
+ bool propagate_word: 1;
+ bool propagate_line: 1;
+};
+
+
+STATIC_CHECK(sizeof(NodeInfo) <= sizeof(int)); // NOLINT
+
+
class RegExpNode: public ZoneObject {
public:
virtual ~RegExpNode() { }
@@ -405,11 +422,15 @@
// false for failure.
bool GoTo(RegExpCompiler* compiler);
void EmitAddress(RegExpCompiler* compiler);
+
// Until the implementation is complete we will return true for success
and
// false for failure.
virtual bool Emit(RegExpCompiler* compiler) = 0;
+ NodeInfo* info() { return &info_; }
+ virtual bool IsBacktrack() { return false; }
private:
Label label;
+ NodeInfo info_;
};
@@ -533,15 +554,12 @@
class EndNode: public RegExpNode {
public:
enum Action { ACCEPT, BACKTRACK };
+ explicit EndNode(Action action) : action_(action) { }
virtual void Accept(NodeVisitor* visitor);
- static EndNode* GetAccept() { return &kAccept; }
- static EndNode* GetBacktrack() { return &kBacktrack; }
virtual bool Emit(RegExpCompiler* compiler);
+ virtual bool IsBacktrack() { return action_ == BACKTRACK; }
private:
- explicit EndNode(Action action) : action_(action) { }
Action action_;
- static EndNode kAccept;
- static EndNode kBacktrack;
};
@@ -578,21 +596,76 @@
public:
explicit ChoiceNode(int expected_size, RegExpNode* on_failure)
: on_failure_(on_failure),
- choices_(new ZoneList<GuardedAlternative>(expected_size)),
- visited_(false) { }
+ alternatives_(new ZoneList<GuardedAlternative>(expected_size)),
+ table_calculated_(false),
+ being_calculated_(false) { }
virtual void Accept(NodeVisitor* visitor);
- void AddChild(GuardedAlternative node) { choices()->Add(node); }
- ZoneList<GuardedAlternative>* choices() { return choices_; }
+ void AddAlternative(GuardedAlternative node) {
alternatives()->Add(node); }
+ ZoneList<GuardedAlternative>* alternatives() { return alternatives_; }
DispatchTable* table() { return &table_; }
RegExpNode* on_failure() { return on_failure_; }
virtual bool Emit(RegExpCompiler* compiler);
- bool visited() { return visited_; }
- void set_visited(bool value) { visited_ = value; }
+ bool table_calculated() { return table_calculated_; }
+ void set_table_calculated(bool b) { table_calculated_ = b; }
+ bool being_calculated() { return being_calculated_; }
+ void set_being_calculated(bool b) { being_calculated_ = b; }
private:
RegExpNode* on_failure_;
- ZoneList<GuardedAlternative>* choices_;
+ ZoneList<GuardedAlternative>* alternatives_;
DispatchTable table_;
- bool visited_;
+ bool table_calculated_;
+ bool being_calculated_;
+};
+
+
+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
+};
+
+
+// Node visitor used to add the start set of the alternatives to the
+// dispatch table of a choice node.
+class DispatchTableConstructor: public NodeVisitor {
+ public:
+ explicit DispatchTableConstructor(DispatchTable* table)
+ : table_(table),
+ choice_index_(-1) { }
+
+ void BuildTable(ChoiceNode* node);
+
+ void AddRange(CharacterRange range) {
+ table()->AddRange(range, choice_index_);
+ }
+
+ void AddInverse(ZoneList<CharacterRange>* ranges);
+
+#define DECLARE_VISIT(Type) \
+ virtual void Visit##Type(Type##Node* that);
+FOR_EACH_NODE_TYPE(DECLARE_VISIT)
+#undef DECLARE_VISIT
+
+ DispatchTable* table() { return table_; }
+ void set_choice_index(int value) { choice_index_ = value; }
+
+ protected:
+ DispatchTable *table_;
+ int choice_index_;
+};
+
+
+class Analysis: public NodeVisitor {
+ public:
+ void EnsureAnalyzed(RegExpNode* node);
+
+#define DECLARE_VISIT(Type) \
+ virtual void Visit##Type(Type##Node* that);
+FOR_EACH_NODE_TYPE(DECLARE_VISIT)
+#undef DECLARE_VISIT
};
@@ -611,9 +684,6 @@
bool ignore_case);
static void DotPrint(const char* label, RegExpNode* node);
};
-
-
-class RegExpCompiler;
} } // namespace v8::internal
Modified: branches/experimental/regexp2000/src/string-stream.cc
==============================================================================
--- branches/experimental/regexp2000/src/string-stream.cc (original)
+++ branches/experimental/regexp2000/src/string-stream.cc Fri Nov 14
04:45:27 2008
@@ -233,6 +233,14 @@
}
+void StringStream::Add(const char* format, FmtElm arg0, FmtElm arg1,
+ FmtElm arg2, FmtElm arg3) {
+ const char argc = 4;
+ FmtElm argv[argc] = { arg0, arg1, arg2, arg3 };
+ Add(CStrVector(format), Vector<FmtElm>(argv, argc));
+}
+
+
SmartPointer<const char> StringStream::ToCString() {
char* str = NewArray<char>(length_ + 1);
memcpy(str, buffer_, length_);
Modified: branches/experimental/regexp2000/src/string-stream.h
==============================================================================
--- branches/experimental/regexp2000/src/string-stream.h (original)
+++ branches/experimental/regexp2000/src/string-stream.h Fri Nov 14
04:45:27 2008
@@ -116,6 +116,11 @@
void Add(const char* format, FmtElm arg0);
void Add(const char* format, FmtElm arg0, FmtElm arg1);
void Add(const char* format, FmtElm arg0, FmtElm arg1, FmtElm arg2);
+ void Add(const char* format,
+ FmtElm arg0,
+ FmtElm arg1,
+ FmtElm arg2,
+ FmtElm arg3);
// Getting the message out.
void OutputToStdOut();
Modified: branches/experimental/regexp2000/test/cctest/test-regexp.cc
==============================================================================
--- branches/experimental/regexp2000/test/cctest/test-regexp.cc (original)
+++ branches/experimental/regexp2000/test/cctest/test-regexp.cc Fri Nov 14
04:45:27 2008
@@ -679,7 +679,9 @@
ranges->Add(CharacterRange(from, to));
}
DispatchTable table;
- CharacterClassNode::AddInverseToTable(ranges, &table, 0);
+ DispatchTableConstructor cons(&table);
+ cons.set_choice_index(0);
+ cons.AddInverse(ranges);
for (int i = 0; i < kLimit; i++) {
bool is_on = false;
for (int j = 0; !is_on && j < kRangeCount; j++)
@@ -693,7 +695,9 @@
new ZoneList<CharacterRange>(1);
ranges->Add(CharacterRange(0xFFF0, 0xFFFE));
DispatchTable table;
- CharacterClassNode::AddInverseToTable(ranges, &table, 0);
+ DispatchTableConstructor cons(&table);
+ cons.set_choice_index(0);
+ cons.AddInverse(ranges);
CHECK(!table.Get(0xFFFE)->Get(0));
CHECK(table.Get(0xFFFF)->Get(0));
}
--~--~---------~--~----~------------~-------~--~----~
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
-~----------~----~----~----~------~----~------~--~---
