From 80ace73cb866404f57a74b49c6575fb58d15c1d6 Mon Sep 17 00:00:00 2001
From: "lrn@chromium.org"
 <lrn@chromium.org@ce2b1a6d-e550-0410-aec6-3dcde31c8c00>
Date: Thu, 18 Nov 2010 10:42:22 +0000
Subject: [PATCH] Make count-line-ends use StringSearch and only iterate over
 the source once.

Review URL: http://codereview.chromium.org/5121007

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@5850 ce2b1a6d-e550-0410-aec6-3dcde31c8c00
---
 src/handles.cc | 66 ++++++++++++++++++++++++++++++++--------------------------
 1 file changed, 37 insertions(+), 29 deletions(-)

diff --git a/src/handles.cc b/src/handles.cc
index 1364951..3dfb886 100644
--- a/src/handles.cc
+++ b/src/handles.cc
@@ -37,6 +37,7 @@
 #include "global-handles.h"
 #include "natives.h"
 #include "runtime.h"
+#include "string-search.h"
 #include "stub-cache.h"
 
 namespace v8 {
@@ -508,43 +509,50 @@ void InitScriptLineEnds(Handle<Script> script) {
 }
 
 
-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"));
+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"));
 
-  // Pass 1: Identify line count.
-  int line_count = 0;
+  // Find and record line ends.
   int position = 0;
   while (position != -1 && position < src_len) {
-    position = Runtime::StringMatch(src, new_line, position);
+    position = search.Search(src, position);
     if (position != -1) {
+      line_ends->Add(position);
       position++;
-    }
-    if (position != -1) {
-      line_count++;
-    } else if (with_imaginary_last_new_line) {
+    } else if (with_last_line) {
       // Even if the last line misses a line end, it is counted.
-      line_count++;
+      line_ends->Add(src_len);
+      return;
     }
   }
+}
 
-  // Pass 2: Fill in line ends positions
-  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));
+
+Handle<FixedArray> CalculateLineEnds(Handle<String> src,
+                                     bool with_last_line) {
+  src = FlattenGetString(src);
+  // 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.
+    // Dispatch on type of strings.
+    if (src->IsAsciiRepresentation()) {
+      CalculateLineEnds(&line_ends, src->ToAsciiVector(), with_last_line);
+    } else {
+      CalculateLineEnds(&line_ends, src->ToUC16Vector(), with_last_line);
     }
   }
-  ASSERT(array_index == line_count);
-
+  int line_count = line_ends.length();
+  Handle<FixedArray> array = Factory::NewFixedArray(line_count);
+  for (int i = 0; i < line_count; i++) {
+    array->set(i, Smi::FromInt(line_ends[i]));
+  }
   return array;
 }
 
@@ -556,11 +564,11 @@ int GetScriptLineNumber(Handle<Script> script, int code_pos) {
   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;
-- 
2.7.4