Recognize standard character classes and implement more efficient matchers.

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 249 matching lines @@
                            "malformed_regexp");
       return Handle<Object>::null();
     }
 
     if (parse_result.simple && !flags.is_ignore_case()) {
       // Parse-tree is a single atom that is equal to the pattern.
       result = AtomCompile(re, pattern, flags, pattern);
     } else if (parse_result.tree->IsAtom() &&
         !flags.is_ignore_case() &&
         parse_result.capture_count == 0) {
-      // TODO(lrn) Accept capture_count > 0 on atoms.
       RegExpAtom* atom = parse_result.tree->AsAtom();
       Vector<const uc16> atom_pattern = atom->data();
-      Handle<String> atom_string =
-          Factory::NewStringFromTwoByte(atom_pattern);
+      Handle<String> atom_string = Factory::NewStringFromTwoByte(atom_pattern);
       result = AtomCompile(re, pattern, flags, atom_string);
     } else if (FLAG_irregexp) {
       result = IrregexpPrepare(re, pattern, flags);
     } else {
       result = JscrePrepare(re, pattern, flags);
     }
     Object* data = re->data();
     if (data->IsFixedArray()) {
       // If compilation succeeded then the data is set on the regexp
       // and we can store it in the cache.
@@ skipping 220 matching lines @@
   JscreCompileWithRetryAfterGC(two_byte_pattern,
                                flags,
                                &number_of_captures,
                                &error_message,
                                &code);
 
   if (code == NULL) {
     // Throw an exception.
     Handle<JSArray> array = Factory::NewJSArray(2);
     SetElement(array, 0, pattern);
-    SetElement(array, 1, Factory::NewStringFromUtf8(CStrVector(
-        (error_message == NULL) ? "Unknown regexp error" : error_message)));
+    const char* message =
+        (error_message == NULL) ? "Unknown regexp error" : error_message;
+    SetElement(array, 1, Factory::NewStringFromUtf8(CStrVector(message)));
     Handle<Object> regexp_err =
         Factory::NewSyntaxError("malformed_regexp", array);
     Top::Throw(*regexp_err);
     return Handle<Object>();
   }
 
   // Convert the return address to a ByteArray pointer.
   Handle<ByteArray> internal(
       ByteArray::FromDataStartAddress(reinterpret_cast<Address>(code)));
 
@@ skipping 1210 matching lines @@
 }
 
 
 static void EmitCharClass(RegExpMacroAssembler* macro_assembler,
                           RegExpCharacterClass* cc,
                           int cp_offset,
                           Label* on_failure,
                           bool check_offset,
                           bool ascii,
                           bool preloaded) {
+  if (cc->is_standard() &&
+      macro_assembler->CheckSpecialCharacterClass(cc->standard_type(),
+                                                  cp_offset, check_offset,

[Mads Ager (chromium), 2009/01/02 10:45:16]

I would put one argument per line here.

+                                                  on_failure)) {
+    return;
+  }
+
   ZoneList<CharacterRange>* ranges = cc->ranges();
   int max_char;
   if (ascii) {
     max_char = String::kMaxAsciiCharCode;
   } else {
     max_char = String::kMaxUC16CharCode;
   }
 
   Label success;
 
@@ skipping 1581 matching lines @@
   printer.PrintNode(label, node);
 }
 
 
 #endif  // DEBUG
 
 
 // -------------------------------------------------------------------
 // Tree to graph conversion
 
+static const int kSpaceRangeCount = 20;
+static const int kSpaceRangeAsciiCount = 4;
+static const uc16 kSpaceRanges[kSpaceRangeCount] = { 0x0009, 0x000D, 0x0020,
+    0x0020, 0x00A0, 0x00A0, 0x1680, 0x1680, 0x180E, 0x180E, 0x2000, 0x200A,
+    0x2028, 0x2029, 0x202F, 0x202F, 0x205F, 0x205F, 0x3000, 0x3000 };
+
+static const int kWordRangeCount = 8;
+static const uc16 kWordRanges[kWordRangeCount] = { '0', '9', 'A', 'Z', '_',
+    '_', 'a', 'z' };
+
+static const int kDigitRangeCount = 2;
+static const uc16 kDigitRanges[kDigitRangeCount] = { '0', '9' };
+
+static const int kLineTerminatorRangeCount = 6;
+static const uc16 kLineTerminatorRanges[kLineTerminatorRangeCount] = { 0x000A,
+    0x000A, 0x000D, 0x000D, 0x2028, 0x2029 };
 
 RegExpNode* RegExpAtom::ToNode(RegExpCompiler* compiler,
                                RegExpNode* on_success) {
   ZoneList<TextElement>* elms = new ZoneList<TextElement>(1);
   elms->Add(TextElement::Atom(this));
   return new TextNode(elms, on_success);
 }
 
 
 RegExpNode* RegExpText::ToNode(RegExpCompiler* compiler,
                                RegExpNode* on_success) {
   return new TextNode(elements(), on_success);
 }
 
+static bool CompareInverseRanges(ZoneList<CharacterRange>* ranges,
+                                 const uc16* special_class,
+                                 int length) {
+  ASSERT(ranges->length() != 0);
+  ASSERT(length != 0);
+  ASSERT(special_class[0] != 0);
+  if (ranges->length() != (length>>1)+1) {

[Mads Ager (chromium), 2009/01/02 10:45:16]

Space around the binary operators?

+    return false;
+  }
+  CharacterRange range = ranges->at(0);
+  if (range.from() != 0) {
+    return false;
+  }
+  for (int i = 0; i < length; i += 2) {
+    if (special_class[i] != (range.to() + 1)) {
+      return false;
+    }
+    range = ranges->at((i>>1)+1);

[Mads Ager (chromium), 2009/01/02 10:45:16]

Space around the binary operators?

+    if (special_class[i+1] != range.from() - 1) {

[Mads Ager (chromium), 2009/01/02 10:45:16]

Space around the binary operator?

+      return false;
+    }
+  }
+  if (range.to() != 0xffff) {
+    return false;
+  }
+  return true;
+}
+
+
+static bool CompareRanges(ZoneList<CharacterRange>* ranges,
+                          const uc16* special_class,
+                          int length) {
+  if (ranges->length() * 2 != length) {
+    return false;
+  }
+  for (int i = 0; i < length; i+=2) {

[Mads Ager (chromium), 2009/01/02 10:45:16]

Space around the '+=' for consistency?

+    CharacterRange range = ranges->at(i >> 1);
+    if (range.from() != special_class[i] || range.to() != special_class[i+1]) {
+      return false;
+    }
+  }
+  return true;
+}
+
+
+bool RegExpCharacterClass::is_standard() {
+  // TODO(lrn): Remove need for this function, by not throwing away information
+  // along the way.
+  if (is_negated_) {
+    return false;
+  }
+  if (set_.is_standard()) {
+    return true;
+  }
+  if (CompareRanges(set_.ranges(), kSpaceRanges, kSpaceRangeCount)) {
+    set_.set_standard_set_type('s');
+    return true;
+  }
+  if (CompareInverseRanges(set_.ranges(), kSpaceRanges, kSpaceRangeCount)) {
+    set_.set_standard_set_type('S');
+    return true;
+  }
+  if (CompareInverseRanges(set_.ranges(),
+                           kLineTerminatorRanges,
+                           kLineTerminatorRangeCount)) {
+    set_.set_standard_set_type('.');
+    return true;
+  }
+  return false;
+}
+
 
 RegExpNode* RegExpCharacterClass::ToNode(RegExpCompiler* compiler,
                                          RegExpNode* on_success) {
   return new TextNode(this, on_success);
 }
 
 
 RegExpNode* RegExpDisjunction::ToNode(RegExpCompiler* compiler,
                                       RegExpNode* on_success) {
   ZoneList<RegExpTree*>* alternatives = this->alternatives();
@@ skipping 221 matching lines @@
                                       RegExpNode* on_success) {
   ZoneList<RegExpTree*>* children = nodes();
   RegExpNode* current = on_success;
   for (int i = children->length() - 1; i >= 0; i--) {
     current = children->at(i)->ToNode(compiler, current);
   }
   return current;
 }
 
 
-static const int kSpaceRangeCount = 20;
-static const uc16 kSpaceRanges[kSpaceRangeCount] = {
-  0x0009, 0x000D, 0x0020, 0x0020, 0x00A0, 0x00A0, 0x1680,
-  0x1680, 0x180E, 0x180E, 0x2000, 0x200A, 0x2028, 0x2029,
-  0x202F, 0x202F, 0x205F, 0x205F, 0x3000, 0x3000
-};
-
-
-static const int kWordRangeCount = 8;
-static const uc16 kWordRanges[kWordRangeCount] = {
-  '0', '9', 'A', 'Z', '_', '_', 'a', 'z'
-};
-
-
-static const int kDigitRangeCount = 2;
-static const uc16 kDigitRanges[kDigitRangeCount] = {
-  '0', '9'
-};
-
-
-static const int kLineTerminatorRangeCount = 6;
-static const uc16 kLineTerminatorRanges[kLineTerminatorRangeCount] = {
-  0x000A, 0x000A, 0x000D, 0x000D, 0x2028, 0x2029
-};
-
-
 static void AddClass(const uc16* elmv,
                      int elmc,
                      ZoneList<CharacterRange>* ranges) {
   for (int i = 0; i < elmc; i += 2) {
     ASSERT(elmv[i] <= elmv[i + 1]);
     ranges->Add(CharacterRange(elmv[i], elmv[i + 1]));
   }
 }
 
 
@@ skipping 175 matching lines @@
         }
       }
       start = pos = block_end + 1;
     }
   } else {
     // TODO(plesner) when we've fixed the 2^11 bug in unibrow.
   }
 }
 
 
+ZoneList<CharacterRange>* CharacterSet::ranges() {
+  if (ranges_ == NULL) {
+    ranges_ = new ZoneList<CharacterRange>(2);
+    CharacterRange::AddClassEscape(standard_set_type_, ranges_);
+  }
+  return ranges_;
+}
+
+
+
 // -------------------------------------------------------------------
 // Interest propagation
 
 
 RegExpNode* RegExpNode::TryGetSibling(NodeInfo* info) {
   for (int i = 0; i < siblings_.length(); i++) {
     RegExpNode* sibling = siblings_.Get(i);
     if (sibling->info()->Matches(info))
       return sibling;
   }
@@ skipping 481 matching lines @@
   EmbeddedVector<byte, 1024> codes;
   RegExpMacroAssemblerIrregexp macro_assembler(codes);
   return compiler.Assemble(&macro_assembler,
                            node,
                            data->capture_count,
                            pattern);
 }
 
 
 }}  // namespace v8::internal