Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(625)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: src/jsregexp.cc

Issue 10682: Inverted character classes (Closed)
Patch Set: Created 12 years, 1 month 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
Download patch
« no previous file with comments | « src/jsregexp.h ('k') | src/list.h » ('j') | src/utils.h » ('J')
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/jsregexp.cc
diff --git a/src/jsregexp.cc b/src/jsregexp.cc
index cf06051ec34c96729d955e2b7a41cc603a05b86c..0ccf0b846245ef1724126fd04fea72cabd268367 100644
--- a/src/jsregexp.cc
+++ b/src/jsregexp.cc
@@ -691,15 +691,6 @@ Handle<FixedArray> RegExpCompiler::Assemble(
}
-#define FOR_EACH_NODE_TYPE(VISIT) \
- VISIT(End) \
- VISIT(Atom) \
- VISIT(Action) \
- VISIT(Choice) \
- VISIT(Backreference) \
- VISIT(CharacterClass)
-
-
void RegExpNode::GoTo(RegExpCompiler* compiler) {
if (label.is_bound()) {
compiler->macro_assembler()->GoTo(&label);
@@ -714,130 +705,10 @@ void RegExpNode::EmitAddress(RegExpCompiler* compiler) {
}
-class SeqRegExpNode: public RegExpNode {
- public:
- explicit SeqRegExpNode(RegExpNode* on_success)
- : on_success_(on_success) { }
- RegExpNode* on_success() { return on_success_; }
- virtual void Emit(RegExpCompiler* compiler) { UNREACHABLE(); }
- private:
- RegExpNode* on_success_;
-};
-
-
-class EndNode: public RegExpNode {
- public:
- enum Action { ACCEPT, BACKTRACK };
- virtual void Accept(NodeVisitor* visitor);
- static EndNode* GetAccept() { return &kAccept; }
- static EndNode* GetBacktrack() { return &kBacktrack; }
- virtual void Emit(RegExpCompiler* compiler) { UNREACHABLE(); }
- private:
- explicit EndNode(Action action) : action_(action) { }
- Action action_;
- static EndNode kAccept;
- static EndNode kBacktrack;
-};
-
-
EndNode EndNode::kAccept(ACCEPT);
EndNode EndNode::kBacktrack(BACKTRACK);
-class AtomNode: public SeqRegExpNode {
- public:
- AtomNode(Vector<const uc16> data,
- RegExpNode* on_success,
- RegExpNode* on_failure)
- : SeqRegExpNode(on_success),
- on_failure_(on_failure),
- data_(data) { }
- virtual void Accept(NodeVisitor* visitor);
- Vector<const uc16> data() { return data_; }
- RegExpNode* on_failure() { return on_failure_; }
- virtual void Emit(RegExpCompiler* compiler) { UNREACHABLE(); }
- private:
- RegExpNode* on_failure_;
- Vector<const uc16> data_;
-};
-
-
-class BackreferenceNode: public SeqRegExpNode {
- public:
- BackreferenceNode(int start_reg,
- int end_reg,
- RegExpNode* on_success,
- RegExpNode* on_failure)
- : 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 void Emit(RegExpCompiler* compiler) { UNREACHABLE(); }
- private:
- RegExpNode* on_failure_;
- int start_reg_;
- int end_reg_;
-};
-
-
-class CharacterClassNode: public SeqRegExpNode {
- public:
- CharacterClassNode(ZoneList<CharacterRange>* ranges,
- bool is_negated,
- RegExpNode* on_success,
- RegExpNode* on_failure)
- : SeqRegExpNode(on_success),
- on_failure_(on_failure),
- ranges_(ranges),
- is_negated_(is_negated ) { }
- virtual void Accept(NodeVisitor* visitor);
- ZoneList<CharacterRange>* ranges() { return ranges_; }
- bool is_negated() { return is_negated_; }
- RegExpNode* on_failure() { return on_failure_; }
- virtual void Emit(RegExpCompiler* compiler) { UNREACHABLE(); }
- static void AddInverseToTable(List<CharacterRange> ranges,
- DispatchTable* table,
- int index);
- private:
- RegExpNode* on_failure_;
- ZoneList<CharacterRange>* ranges_;
- bool is_negated_;
-};
-
-
-class Guard: public ZoneObject {
- public:
- enum Relation { LT, GEQ };
- Guard(int reg, Relation op, int value)
- : reg_(reg),
- op_(op),
- value_(value) { }
- int reg() { return reg_; }
- Relation op() { return op_; }
- int value() { return value_; }
- private:
- int reg_;
- Relation op_;
- int value_;
-};
-
-
-class GuardedAlternative {
- public:
- explicit GuardedAlternative(RegExpNode* node) : node_(node), guards_(NULL) { }
- void AddGuard(Guard* guard);
- RegExpNode* node() { return node_; }
- ZoneList<Guard*>* guards() { return guards_; }
- private:
- RegExpNode* node_;
- ZoneList<Guard*>* guards_;
-};
-
-
void GuardedAlternative::AddGuard(Guard* guard) {
if (guards_ == NULL)
guards_ = new ZoneList<Guard*>(1);
@@ -845,69 +716,6 @@ void GuardedAlternative::AddGuard(Guard* guard) {
}
-class ChoiceNode: public RegExpNode {
- public:
- explicit ChoiceNode(int expected_size, RegExpNode* on_failure)
- : on_failure_(on_failure),
- choices_(new ZoneList<GuardedAlternative>(expected_size)),
- visited_(false) { }
- virtual void Accept(NodeVisitor* visitor);
- void AddChild(GuardedAlternative node) { choices()->Add(node); }
- ZoneList<GuardedAlternative>* choices() { return choices_; }
- DispatchTable* table() { return &table_; }
- RegExpNode* on_failure() { return on_failure_; }
- virtual void Emit(RegExpCompiler* compiler);
- bool visited() { return visited_; }
- void set_visited(bool value) { visited_ = value; }
- private:
- RegExpNode* on_failure_;
- ZoneList<GuardedAlternative>* choices_;
- DispatchTable table_;
- bool visited_;
-};
-
-
-class ActionNode: public SeqRegExpNode {
- public:
- enum Type {
- STORE_REGISTER,
- INCREMENT_REGISTER,
- STORE_POSITION,
- RESTORE_POSITION,
- BEGIN_SUBMATCH,
- ESCAPE_SUBMATCH,
- END_SUBMATCH
- };
- static ActionNode* StoreRegister(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(RegExpNode* on_success);
- static ActionNode* EscapeSubmatch(RegExpNode* on_success);
- static ActionNode* EndSubmatch(RegExpNode* on_success);
- virtual void Accept(NodeVisitor* visitor);
- virtual void Emit(RegExpCompiler* compiler);
- private:
- union {
- struct {
- int reg;
- int value;
- } u_store_register;
- struct {
- int reg;
- } u_increment_register;
- struct {
- int reg;
- } u_position_register;
- } data_;
- ActionNode(Type type, RegExpNode* on_success)
- : SeqRegExpNode(on_success),
- type_(type) { }
- Type type_;
- friend class DotPrinter;
-};
-
-
ActionNode* ActionNode::StoreRegister(int reg,
int val,
RegExpNode* on_success) {
@@ -1708,13 +1516,47 @@ void Analysis::VisitBackreference(BackreferenceNode* that) {
}
+
+static int CompareRangeByFrom(const CharacterRange* a,
+ const CharacterRange* b) {
+ return Spaceship<uc16>(a->from(), b->from());
+}
+
+
+void CharacterClassNode::AddInverseToTable(ZoneList<CharacterRange>* ranges,
+ DispatchTable* table,
+ int index) {
+ 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);
+ if (range.to() >= last) {
+ if (range.to() == 0xFFFF) {
+ last = 0xFFFF;
+ break;
+ } else {
+ last = range.to() + 1;
+ }
+ }
+ }
+ if (last < 0xFFFF)
+ table->AddRange(CharacterRange(last, 0xFFFF), index);
Erik Corry 2008/11/13 11:45:43 I think this goes wrong if range.to() for the last
Christian Plesner Hansen 2008/11/13 11:58:37 Good point. I've fixed it and added a test.
+}
+
+
void Analysis::VisitCharacterClass(CharacterClassNode* that) {
if (table() != NULL) {
int index = choice_index();
ZoneList<CharacterRange>* ranges = that->ranges();
- for (int i = 0; i < ranges->length(); i++) {
- CharacterRange range = ranges->at(i);
- table()->AddRange(range, index);
+ 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);
+ }
}
}
AnalysisBuilder outgoing(this);
« no previous file with comments | « src/jsregexp.h ('k') | src/list.h » ('j') | src/utils.h » ('J')

Powered by Google App Engine
This is Rietveld 408576698