Implement loop for global regexps in regexp assembler.

src/jsregexp.cc

-// Copyright 2011 the V8 project authors. All rights reserved.
+// Copyright 2012 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
 //       with the distribution.
@@ skipping 410 matching lines @@
     // THIS SHOULD NOT HAPPEN. We already pre-parsed it successfully once.
     ThrowRegExpException(re,
                          pattern,
                          compile_data.error,
                          "malformed_regexp");
     return false;
   }
   RegExpEngine::CompilationResult result =
       RegExpEngine::Compile(&compile_data,
                             flags.is_ignore_case(),
+                            flags.is_global(),
                             flags.is_multiline(),
                             pattern,
                             sample_subject,
                             is_ascii);
   if (result.error_message != NULL) {
     // Unable to compile regexp.
     Handle<String> error_message =
         isolate->factory()->NewStringFromUtf8(CStrVector(result.error_message));
     CreateRegExpErrorObjectAndThrow(re, is_ascii, error_message, isolate);
     return false;
@@ skipping 66 matching lines @@
   // Byte-code regexp needs space allocated for all its registers.
   return IrregexpNumberOfRegisters(FixedArray::cast(regexp->data()));
 #else  // V8_INTERPRETED_REGEXP
   // Native regexp only needs room to output captures. Registers are handled
   // internally.
   return (IrregexpNumberOfCaptures(FixedArray::cast(regexp->data())) + 1) * 2;
 #endif  // V8_INTERPRETED_REGEXP
 }
 
 
-RegExpImpl::IrregexpResult RegExpImpl::IrregexpExecOnce(
+int RegExpImpl::GlobalOffsetsVectorSize(Handle<JSRegExp> regexp,
+                                        int registers_per_match,
+                                        int* max_matches) {
+#ifdef V8_INTERPRETED_REGEXP
+  // Global loop in interpreted regexp is not implemented.  Therefore we choose
+  // the size of the offsets vector so that it can only store one match.
+  *max_matches = 1;
+  return registers_per_match;
+#else  // V8_INTERPRETED_REGEXP
+  int size = Max(registers_per_match, OffsetsVector::kStaticOffsetsVectorSize);
+  *max_matches = size / registers_per_match;
+  return size;
+#endif  // V8_INTERPRETED_REGEXP
+}
+
+
+int RegExpImpl::IrregexpExecRaw(
     Handle<JSRegExp> regexp,
     Handle<String> subject,
     int index,
     Vector<int> output) {
   Isolate* isolate = regexp->GetIsolate();
 
   Handle<FixedArray> irregexp(FixedArray::cast(regexp->data()), isolate);
 
   ASSERT(index >= 0);
   ASSERT(index <= subject->length());
@@ skipping 81 matching lines @@
 #endif
   int required_registers = RegExpImpl::IrregexpPrepare(jsregexp, subject);
   if (required_registers < 0) {
     // Compiling failed with an exception.
     ASSERT(isolate->has_pending_exception());
     return Handle<Object>::null();
   }
 
   OffsetsVector registers(required_registers, isolate);
 
-  IrregexpResult res = RegExpImpl::IrregexpExecOnce(
+  int res = RegExpImpl::IrregexpExecRaw(
       jsregexp, subject, previous_index, Vector<int>(registers.vector(),
                                                      registers.length()));
   if (res == RE_SUCCESS) {
     int capture_register_count =
         (IrregexpNumberOfCaptures(FixedArray::cast(jsregexp->data())) + 1) * 2;
     last_match_info->EnsureSize(capture_register_count + kLastMatchOverhead);
     AssertNoAllocation no_gc;
     int* register_vector = registers.vector();
     FixedArray* array = FixedArray::cast(last_match_info->elements());
     for (int i = 0; i < capture_register_count; i += 2) {
@@ skipping 5142 matching lines @@
 
 void DispatchTableConstructor::VisitAction(ActionNode* that) {
   RegExpNode* target = that->on_success();
   target->Accept(this);
 }
 
 
 RegExpEngine::CompilationResult RegExpEngine::Compile(
     RegExpCompileData* data,
     bool ignore_case,
+    bool is_global,
     bool is_multiline,
     Handle<String> pattern,
     Handle<String> sample_subject,
     bool is_ascii) {
   if ((data->capture_count + 1) * 2 - 1 > RegExpMacroAssembler::kMaxRegister) {
     return IrregexpRegExpTooBig();
   }
   RegExpCompiler compiler(data->capture_count, ignore_case, is_ascii);

[Erik Corry, 2012/05/22 08:32:46]

Optimization idea (probably for the next patch): At this point you can use
data->tree->min_match() to see whether the regexp can do a zero length match. 
You can pass that as a flag to the compiler and it can tell the macro assembler
to avoid testing for zero length matches in the repeat code on global regexps.

[Yang, 2012/05/22 14:48:03]

This is exactly what I've been looking for! I tried my luck with EatsAtLeast,
but that wouldn't work for non-capturing matches (e.g. lookahead). Thanks!

 
   // Sample some characters from the middle of the string.
   static const int kSampleSize = 128;
 
   FlattenString(sample_subject);
   int chars_sampled = 0;
   int half_way = (sample_subject->length() - kSampleSize) / 2;
   for (int i = Max(0, half_way);
        i < sample_subject->length() && chars_sampled < kSampleSize;
        i++, chars_sampled++) {
@@ skipping 75 matching lines @@
 
   // Inserted here, instead of in Assembler, because it depends on information
   // in the AST that isn't replicated in the Node structure.
   static const int kMaxBacksearchLimit = 1024;
   if (is_end_anchored &&
       !is_start_anchored &&
       max_length < kMaxBacksearchLimit) {
     macro_assembler.SetCurrentPositionFromEnd(max_length);
   }
 
+  macro_assembler.set_global(is_global);
+
   return compiler.Assemble(&macro_assembler,
                            node,
                            data->capture_count,
                            pattern);
 }
 
 
 }}  // namespace v8::internal