Inverted character classes

src/jsregexp.cc

 // 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 673 matching lines @@
              SKIP_WRITE_BARRIER);
   array->set(kNumberOfRegistersOffset,
              Smi::FromInt(next_register_),
              SKIP_WRITE_BARRIER);
   Handle<Object> code = macro_assembler->GetCode();
   work_list_ = NULL;
   return array;
 }
 
 
-#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);
   } else {
     Emit(compiler);
   }
 }
 
 
 void RegExpNode::EmitAddress(RegExpCompiler* compiler) {
   compiler->macro_assembler()->EmitOrLink(&label);
 }
 
 
-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);
   guards_->Add(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) {
   ActionNode* result = new ActionNode(STORE_REGISTER, on_success);
   result->data_.u_store_register.reg = reg;
   result->data_.u_store_register.value = val;
   return result;
 }
 
 
@@ skipping 780 matching lines @@
     data.table()->ForEach(AddDispatchRange(this));
   }
 }
 
 
 void Analysis::VisitBackreference(BackreferenceNode* that) {
   UNIMPLEMENTED();
 }
 
 
+
+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 range is 0xfffe.  I imagine
there will be literally trillions of regexps with ranges ending in one, but not
the other BOM symbol, so it's important to get this right!

[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);
   outgoing.set_table(NULL);
   outgoing.Analyze(that->on_success());
 }
 
 
 void Analysis::VisitAtom(AtomNode* that) {
   if (table() != NULL) {
@@ skipping 27 matching lines @@
   analysis.Analyze(node);
   return node;
 }
 
 
 RegExpMacroAssembler::~RegExpMacroAssembler() {
 }
 
 
 }}  // namespace v8::internal