Take advantage of batched results when matching global regexp.

src/jsregexp.h

 // 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
@@ skipping 75 matching lines @@
                                  Handle<String> pattern,
                                  JSRegExp::Flags flags,
                                  int capture_register_count);
 
 
   static void AtomCompile(Handle<JSRegExp> re,
                           Handle<String> pattern,
                           JSRegExp::Flags flags,
                           Handle<String> match_pattern);
 
+
+  static int AtomExecRaw(Handle<JSRegExp> regexp,
+                         Handle<String> subject,
+                         int index,
+                         int32_t* output,
+                         int output_size);
+
+
   static Handle<Object> AtomExec(Handle<JSRegExp> regexp,
                                  Handle<String> subject,
                                  int index,
                                  Handle<JSArray> lastMatchInfo);
 
   enum IrregexpResult { RE_FAILURE = 0, RE_SUCCESS = 1, RE_EXCEPTION = -1 };
 
   // Prepare a RegExp for being executed one or more times (using
   // IrregexpExecOnce) on the subject.
   // This ensures that the regexp is compiled for the subject, and that
   // the subject is flat.
   // Returns the number of integer spaces required by IrregexpExecOnce
   // as its "registers" argument. If the regexp cannot be compiled,
   // an exception is set as pending, and this function returns negative.
   static int IrregexpPrepare(Handle<JSRegExp> regexp,
                              Handle<String> subject);
 
   // Calculate the size of offsets vector for the case of global regexp
   // and the number of matches this vector is able to store.
   static int GlobalOffsetsVectorSize(Handle<JSRegExp> regexp,

[ulan, 2012/08/03 07:44:27]

Looks like this function is not used anymore.

[Yang, 2012/08/03 11:37:42]

Done.

                                      int registers_per_match,
                                      int* max_matches);
 
   // Execute a regular expression on the subject, starting from index.
   // If matching succeeds, return the number of matches.  This can be larger
   // than one in the case of global regular expressions.
   // The captures and subcaptures are stored into the registers vector.
   // If matching fails, returns RE_FAILURE.
   // If execution fails, sets a pending exception and returns RE_EXCEPTION.
   static int IrregexpExecRaw(Handle<JSRegExp> regexp,
                              Handle<String> subject,
                              int index,
-                             Vector<int> registers);
+                             int32_t* output,
+                             int output_size);
 
   // Execute an Irregexp bytecode pattern.
   // On a successful match, the result is a JSArray containing
   // captured positions. On a failure, the result is the null value.
   // Returns an empty handle in case of an exception.
   static Handle<Object> IrregexpExec(Handle<JSRegExp> regexp,
                                      Handle<String> subject,
                                      int index,
                                      Handle<JSArray> lastMatchInfo);
 
+  // Set last match info.   If match is NULL, then setting captures is omitted.

[ulan, 2012/08/03 07:44:27]

Double spaces in the comments for the functions below.

[Yang, 2012/08/03 11:37:42]

Done.

+  static Handle<JSArray> SetLastMatchInfo(Handle<JSArray> last_match_info,
+                                          Handle<String> subject,
+                                          int capture_count,
+                                          int32_t* match);
+
+  // Initialize a run of global regexp matching.  Return either
+  // RE_SUCCESS or RE_EXCEPTION.
+  static int GlobalCacheInitialize(Handle<JSRegExp> regexp,
+                                   Handle<String> subject,
+                                   bool is_global,
+                                   Isolate* isolate);
+
+  // Fetch the next entry in the cache for global regexp match results.
+  // This does not set the last match info.  Upon failure, NULL is returned.
+  // The cause can be checked with GlobalCacheResult().  The previous
+  // result is still in available in memory when a failure happens.
+  INLINE(static int32_t* GlobalCacheFetchNext(Handle<JSRegExp> regexp,

[ulan, 2012/08/03 07:44:27]

Can we put this function in .cc file, it seems to be too large to be inlineable.

[Yang, 2012/08/03 11:37:42]

Done.

+                                              Handle<String> subject)) {
+    global_cache_current_match_index_++;
+    // The cache must not be clobbered.

[ulan, 2012/08/03 07:44:27]

Stale comment?

[Yang, 2012/08/03 11:37:42]

Done.

+    ASSERT(global_cache_register_array_ != NULL);
+    if (global_cache_current_match_index_ >= global_cache_num_matches_) {
+      // Current batch of results exhausted.
+      // Fail if last batch was not even fully filled.
+      if (global_cache_num_matches_ < global_cache_max_matches_) {
+        global_cache_num_matches_ = 0;
+        return NULL;
+      }
+
+      int32_t* last_match =
+          &global_cache_register_array_[global_cache_register_array_size_ -
+                                        global_cache_registers_per_match_];
+      int last_end_index = last_match[1];
+
+      if (global_cache_current_type_ == JSRegExp::ATOM) {
+        global_cache_num_matches_ =
+            RegExpImpl::AtomExecRaw(regexp,
+                                    subject,
+                                    last_end_index,
+                                    global_cache_register_array_,
+                                    global_cache_register_array_size_);
+      } else {
+        int last_start_index = last_match[0];
+        if (last_start_index == last_end_index) last_end_index++;
+        if (last_end_index > subject->length()) {
+          global_cache_num_matches_ = 0;
+          return NULL;
+        }
+        global_cache_num_matches_ =
+            RegExpImpl::IrregexpExecRaw(regexp,
+                                        subject,
+                                        last_end_index,
+                                        global_cache_register_array_,
+                                        global_cache_register_array_size_);
+      }
+
+      if (global_cache_num_matches_ <= 0) return NULL;
+      global_cache_current_match_index_ = 0;
+      return global_cache_register_array_;
+    } else {
+      return &global_cache_register_array_[
+                 global_cache_current_match_index_ *
+                 global_cache_registers_per_match_];
+    }
+  }
+
+  INLINE(static IrregexpResult GlobalCacheResult()) {
+    if (global_cache_num_matches_ > 0) return RE_SUCCESS;
+    if (global_cache_num_matches_ == 0) return RE_FAILURE;
+    return RE_EXCEPTION;
+  }
+
+
   // Array index in the lastMatchInfo array.
   static const int kLastCaptureCount = 0;
   static const int kLastSubject = 1;
   static const int kLastInput = 2;
   static const int kFirstCapture = 3;
   static const int kLastMatchOverhead = 3;
 
   // Direct offset into the lastMatchInfo array.
   static const int kLastCaptureCountOffset =
       FixedArray::kHeaderSize + kLastCaptureCount * kPointerSize;
@@ skipping 39 matching lines @@
 
   // Limit the space regexps take up on the heap.  In order to limit this we
   // would like to keep track of the amount of regexp code on the heap.  This
   // is not tracked, however.  As a conservative approximation we track the
   // total regexp code compiled including code that has subsequently been freed
   // and the total executable memory at any point.
   static const int kRegExpExecutableMemoryLimit = 16 * MB;
   static const int kRegWxpCompiledLimit = 1 * MB;
 
  private:
-  static String* last_ascii_string_;
-  static String* two_byte_cached_string_;
-
   static bool CompileIrregexp(
       Handle<JSRegExp> re, Handle<String> sample_subject, bool is_ascii);
   static inline bool EnsureCompiledIrregexp(
       Handle<JSRegExp> re, Handle<String> sample_subject, bool is_ascii);
 
-
-  // Set the subject cache.  The previous string buffer is not deleted, so the
-  // caller should ensure that it doesn't leak.
-  static void SetSubjectCache(String* subject,
-                              char* utf8_subject,
-                              int uft8_length,
-                              int character_position,
-                              int utf8_position);
-
-  // A one element cache of the last utf8_subject string and its length.  The
-  // subject JS String object is cached in the heap.  We also cache a
-  // translation between position and utf8 position.
-  static char* utf8_subject_cache_;
-  static int utf8_length_cache_;
-  static int utf8_position_;
-  static int character_position_;
+  // State of the global cache.
+  static int global_cache_num_matches_;
+  static int global_cache_max_matches_;
+  static int global_cache_current_match_index_;
+  static int global_cache_registers_per_match_;
+  // Pointer to the last set of captures.
+  static JSRegExp::Type global_cache_current_type_;
+  static int32_t* global_cache_register_array_;
+  static int global_cache_register_array_size_;
 };
 
 
 // Represents the location of one element relative to the intersection of
 // two sets. Corresponds to the four areas of a Venn diagram.
 enum ElementInSetsRelation {
   kInsideNone = 0,
   kInsideFirst = 1,
   kInsideSecond = 2,
   kInsideBoth = 3
@@ skipping 1383 matching lines @@
                                    bool global,
                                    bool multiline,
                                    Handle<String> pattern,
                                    Handle<String> sample_subject,
                                    bool is_ascii, Zone* zone);
 
   static void DotPrint(const char* label, RegExpNode* node, bool ignore_case);
 };
 
 
-class OffsetsVector {
- public:
-  inline OffsetsVector(int num_registers, Isolate* isolate)
-      : offsets_vector_length_(num_registers) {
-    if (offsets_vector_length_ > Isolate::kJSRegexpStaticOffsetsVectorSize) {
-      vector_ = NewArray<int>(offsets_vector_length_);
-    } else {
-      vector_ = isolate->jsregexp_static_offsets_vector();
-    }
-  }
-  inline ~OffsetsVector() {
-    if (offsets_vector_length_ > Isolate::kJSRegexpStaticOffsetsVectorSize) {
-      DeleteArray(vector_);
-      vector_ = NULL;
-    }
-  }
-  inline int* vector() { return vector_; }
-  inline int length() { return offsets_vector_length_; }
-
-  static const int kStaticOffsetsVectorSize =
-      Isolate::kJSRegexpStaticOffsetsVectorSize;
-
- private:
-  static Address static_offsets_vector_address(Isolate* isolate) {
-    return reinterpret_cast<Address>(isolate->jsregexp_static_offsets_vector());
-  }
-
-  int* vector_;
-  int offsets_vector_length_;
-
-  friend class ExternalReference;
-};
-
-
 } }  // namespace v8::internal
 
 #endif  // V8_JSREGEXP_H_