Make count-line-ends use StringSearch and only iterate over the source once.

src/handles.cc

 // Copyright 2009 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 19 matching lines @@
 #include "accessors.h"
 #include "api.h"
 #include "arguments.h"
 #include "bootstrapper.h"
 #include "compiler.h"
 #include "debug.h"
 #include "execution.h"
 #include "global-handles.h"
 #include "natives.h"
 #include "runtime.h"
+#include "string-search.h"
 #include "stub-cache.h"
 
 namespace v8 {
 namespace internal {
 
 
 v8::ImplementationUtilities::HandleScopeData HandleScope::current_ =
     { NULL, NULL, 0 };
 
 
@@ skipping 451 matching lines @@
 
   if (*array != Heap::empty_fixed_array()) {
     array->set_map(Heap::fixed_cow_array_map());
   }
 
   script->set_line_ends(*array);
   ASSERT(script->line_ends()->IsFixedArray());
 }
 
 
+template <typename SourceChar>
+static void CalculateLineEnds(List<int>* line_ends,
+                              Vector<const SourceChar> src,
+                              bool with_last_line) {
+  const int src_len = src.length();
+  StringSearch<char, SourceChar> search(CStrVector("\n"));
+
+  // Find and record line ends.
+  int position = 0;
+  while (position != -1 && position < src_len) {
+    position = search.Search(src, position);
+    if (position != -1) {
+      line_ends->Add(position);
+      position++;
+    } else if (with_last_line) {
+      // Even if the last line misses a line end, it is counted.
+      line_ends->Add(src_len);
+      return;
+    }
+  }
+}
+
+
 Handle<FixedArray> CalculateLineEnds(Handle<String> src,
-                                     bool with_imaginary_last_new_line) {
-  const int src_len = src->length();
-  Handle<String> new_line = Factory::NewStringFromAscii(CStrVector("\n"));
-
-  // Pass 1: Identify line count.
-  int line_count = 0;
-  int position = 0;
-  while (position != -1 && position < src_len) {
-    position = Runtime::StringMatch(src, new_line, position);
-    if (position != -1) {
-      position++;
-    }
-    if (position != -1) {
-      line_count++;
-    } else if (with_imaginary_last_new_line) {
-      // Even if the last line misses a line end, it is counted.
-      line_count++;
+                                     bool with_last_line) {
+  if (!src->IsFlat()) FlattenString(src);

[Vyacheslav Egorov (Chromium), 2010/11/18 10:36:08]

src = FlattenGetString(src)?

this will allow to remove ConsString handling below.

[Lasse Reichstein, 2010/11/18 10:40:55]

Done.

+  // Rough estimate of line count based on a roughly estimated average
+  // length of (unpacked) code.
+  int line_count_estimate = src->length() >> 4;
+  List<int> line_ends(line_count_estimate);
+  {
+    AssertNoAllocation no_heap_allocation;  // ensure vectors stay valid
+    // Extract flattened substring of cons string before determining asciiness.
+    String* seq_src = *src;
+    if (seq_src->IsConsString()) seq_src = ConsString::cast(seq_src)->first();
+    // Dispatch on type of strings.
+    if (seq_src->IsAsciiRepresentation()) {
+      CalculateLineEnds(&line_ends, seq_src->ToAsciiVector(), with_last_line);
+    } else {
+      CalculateLineEnds(&line_ends, seq_src->ToUC16Vector(), with_last_line);
     }
   }
-
-  // Pass 2: Fill in line ends positions
+  int line_count = line_ends.length();
   Handle<FixedArray> array = Factory::NewFixedArray(line_count);
-  int array_index = 0;
-  position = 0;
-  while (position != -1 && position < src_len) {
-    position = Runtime::StringMatch(src, new_line, position);
-    if (position != -1) {
-      array->set(array_index++, Smi::FromInt(position++));
-    } else if (with_imaginary_last_new_line) {
-      // If the script does not end with a line ending add the final end
-      // position as just past the last line ending.
-      array->set(array_index++, Smi::FromInt(src_len));
-    }
+  for (int i = 0; i < line_count; i++) {
+    array->set(i, Smi::FromInt(line_ends[i]));
   }
-  ASSERT(array_index == line_count);
-
   return array;
 }
 
 
 // Convert code position into line number.
 int GetScriptLineNumber(Handle<Script> script, int code_pos) {
   InitScriptLineEnds(script);
   AssertNoAllocation no_allocation;
   FixedArray* line_ends_array = FixedArray::cast(script->line_ends());
   const int line_ends_len = line_ends_array->length();
 
-  if (!line_ends_len)
-    return -1;
+  if (!line_ends_len) return -1;
 
-  if ((Smi::cast(line_ends_array->get(0)))->value() >= code_pos)
+  if ((Smi::cast(line_ends_array->get(0)))->value() >= code_pos) {
     return script->line_offset()->value();
+  }
 
   int left = 0;
   int right = line_ends_len;
   while (int half = (right - left) / 2) {
     if ((Smi::cast(line_ends_array->get(left + half)))->value() > code_pos) {
       right -= half;
     } else {
       left += half;
     }
   }
@@ skipping 294 matching lines @@
 
 OptimizedObjectForAddingMultipleProperties::
 ~OptimizedObjectForAddingMultipleProperties() {
   // Reoptimize the object to allow fast property access.
   if (has_been_transformed_) {
     TransformToFastProperties(object_, unused_property_fields_);
   }
 }
 
 } }  // namespace v8::internal