Only record one in n line endings to save space.

src/messages.js

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 // -------------------------------------------------------------------
 
 var $errorToString;
 var $getStackTraceLine;
 var $messageGetPositionInLine;
 var $messageGetLineNumber;
@@ skipping 22 matching lines @@
 %CheckIsBootstrapping();
 
 // -------------------------------------------------------------------
 // Imports
 
 var GlobalObject = global.Object;
 var InternalArray = utils.InternalArray;
 var ObjectDefineProperty = utils.ObjectDefineProperty;
 
 var ArrayJoin;
+var MathFloor;
 var ObjectToString;
 var StringCharAt;
 var StringIndexOf;
 var StringSubstring;
 
 utils.Import(function(from) {
   ArrayJoin = from.ArrayJoin;
+  MathFloor = from.MathFloor;
   ObjectToString = from.ObjectToString;
   StringCharAt = from.StringCharAt;
   StringIndexOf = from.StringIndexOf;
   StringSubstring = from.StringSubstring;
 });
 
 // -------------------------------------------------------------------
 
 var GlobalError;
 var GlobalTypeError;
@@ skipping 136 matching lines @@
 // Returns the source code line containing the given source
 // position, or the empty string if the position is invalid.
 function GetSourceLine(message) {
   var script = %MessageGetScript(message);
   var start_position = %MessageGetStartPosition(message);
   var location = script.locationFromPosition(start_position, true);
   if (location == null) return "";
   return location.sourceText();
 }
 
+
+function Newlines(source, from, to, reduction) {
+  var newLines = new InternalArray();
+  if (!IS_STRING(source)) return newLines;
+
+  var length = source.length;
+  for (; from < to && from < length && newLines.length < reduction - 1
+       ; ++from) {
+    var c = %_StringCharCodeAt(source, from);
+    if (c == ASCII_CR) {
+      if (from < length - 1) {
+        var c2 = %_StringCharCodeAt(source, from + 1);
+        if (c2 == ASCII_NL) {
+          from++;  // CR-LF counts as one newline.
+        }
+      }
+      newLines.push(from);
+    } else if (c == ASCII_NL) {
+      newLines.push(from);
+    }
+  }
+  // End-of-file virtual end-of-line.
+  if (to >= length) {
+    var last = length != 0 ? %_StringCharCodeAt(source, length - 1) : 0;
+    if (last != ASCII_NL && last != ASCII_CR) newLines.push(source.length - 1);
+  }
+  return newLines;
+}
+
+
+function ScriptLineEnd(line) {
+  if (line < 0) return -1;
+  var source = this.source;
+  if (!IS_STRING(source)) return -1;
+  var line_ends = this.line_ends;
+  var reduction = line_ends[REDUCTION_INDEX];
+  var index = MathFloor(line / reduction) + FIRST_LINE_END_INDEX;
+  if (index >= line_ends.length) return -1;
+  var position = line_ends[index];
+  if (line % reduction == 0) return position;
+  var lines = Newlines(source, position + 1, source.length, reduction);
+  return lines[line % reduction - 1];
+}
+
+
 /**
  * Find a line number given a specific source position.
  * @param {number} position The source position.
- * @return {number} 0 if input too small, -1 if input too large,
-       else the line number.
+ * @return {number} -1 if position too large, else the 0-based line number.
  */
 function ScriptLineFromPosition(position) {
-  var lower = 0;
-  var upper = this.lineCount() - 1;
+  var source = this.source;
+  if (!IS_STRING(source)) return -1;
+
   var line_ends = this.line_ends;
+  var lower = FIRST_LINE_END_INDEX;
+  var upper = line_ends.length - 1;
 
-  // We'll never find invalid positions so bail right away.
+  var reduction = line_ends[REDUCTION_INDEX];
+  // This '>' would normally be a '>=', but due to {}-less 'with' statements in
+  // top-level code we sometimes encounter code positions that are one character
+  // after the end of the source. See comment in Rewriter::Rewrite.
+  if (position > source.length) return -1;
+
+  var index = 0;
+
+  // Binary search to find line # from position range.
   if (position > line_ends[upper]) {
-    return -1;
+    index = upper;
+  } else {
+    // Invariant: position > line_ends[lower]
+    // Invariant: position <= line_ends[upper]
+    while (lower + 1 < upper) {
+      // Since they differ by at least 2, i must be different from both
+      // upper or lower.
+      var i = (lower + upper) >> 1;
+      if (position > line_ends[i]) {
+        lower = i;
+      } else {
+        upper = i;
+      }
+    }
+    index = lower;
   }
 
-  // This means we don't have to safe-guard indexing line_ends[i - 1].
-  if (position <= line_ends[0]) {
-    return 0;
-  }
-
-  // Binary search to find line # from position range.
-  while (upper >= 1) {
-    var i = (lower + upper) >> 1;
-
-    if (position > line_ends[i]) {
-      lower = i + 1;
-    } else if (position <= line_ends[i - 1]) {
-      upper = i - 1;
-    } else {
-      return i;
-    }
-  }
-
-  return -1;
+  var line = (index - FIRST_LINE_END_INDEX) * reduction;
+  return line +
+      Newlines(source, line_ends[index] + 1, position, reduction).length;
 }
 
 /**
  * Get information on a specific source position.
  * @param {number} position The source position
  * @param {boolean} include_resource_offset Set to true to have the resource
  *     offset added to the location
  * @return {SourceLocation}
  *     If line is negative or not in the source null is returned.
  */
 function ScriptLocationFromPosition(position,
                                     include_resource_offset) {
+  // Get zero-based line number.
   var line = this.lineFromPosition(position);
   if (line == -1) return null;
 
   // Determine start, end and column.
-  var line_ends = this.line_ends;
-  var start = line == 0 ? 0 : line_ends[line - 1] + 1;
-  var end = line_ends[line];
-  if (end > 0 && %_CallFunction(this.source, end - 1, StringCharAt) == '\r') {
+  var start = this.lineEnd(line) + 1;
+  // End will be used for substr, so make it non-inclusive.
+  var end = this.lineEnd(line + 1) + 1;
+  if (end > this.source.length) end = this.source.length;
+  // But trim the newline if there is one (there might not be at EOF).
+  while (end > start) {
+    var trim_char = %_CallFunction(this.source, end - 1, StringCharAt);
+    if (trim_char != '\n' && trim_char != '\r') break;
     end--;
   }
   var column = position - start;
 
   // Adjust according to the offset within the resource.
   if (include_resource_offset) {
     line += this.line_offset;
     if (line == this.line_offset) {
       column += this.column_offset;
     }
@@ skipping 39 matching lines @@
     return this.locationFromPosition(offset_position + column, false);
   } else {
     // Find the line where the offset position is located.
     var offset_line = this.lineFromPosition(offset_position);
 
     if (offset_line == -1 || offset_line + line >= this.lineCount()) {
       return null;
     }
 
     return this.locationFromPosition(
-        this.line_ends[offset_line + line - 1] + 1 + column);  // line > 0 here.
+        this.lineEnd(offset_line + line) + 1 + column);  // line > 0 here.
   }
 }
 
 
 /**
  * Get a slice of source code from the script. The boundaries for the slice is
  * specified in lines.
  * @param {number} opt_from_line The first line (zero bound) in the slice.
  *     Default is 0
  * @param {number} opt_to_column The last line (zero bound) in the slice (non
@@ skipping 13 matching lines @@
   if (from_line < 0) from_line = 0;
   if (to_line > this.lineCount()) to_line = this.lineCount();
 
   // Check parameters.
   if (from_line >= this.lineCount() ||
       to_line < 0 ||
       from_line > to_line) {
     return null;
   }
 
-  var line_ends = this.line_ends;
-  var from_position = from_line == 0 ? 0 : line_ends[from_line - 1] + 1;
-  var to_position = to_line == 0 ? 0 : line_ends[to_line - 1] + 1;
+  var from_position = this.lineEnd(from_line) + 1;
+  var to_position = this.lineEnd(to_line) + 1;
 
   // Return a source slice with line numbers re-adjusted to the resource.
   return new SourceSlice(this,
                          from_line + this.line_offset,
                          to_line + this.line_offset,
-                          from_position, to_position);
+                         from_position, to_position);
 }
 
 
 function ScriptSourceLine(opt_line) {
   // Default is the first line in the script. Lines in the script are relative
   // to the offset within the resource.
   var line = 0;
   if (!IS_UNDEFINED(opt_line)) {
     line = opt_line - this.line_offset;
   }
 
   // Check parameter.
   if (line < 0 || this.lineCount() <= line) {
     return null;
   }
 
   // Return the source line.
-  var line_ends = this.line_ends;
-  var start = line == 0 ? 0 : line_ends[line - 1] + 1;
-  var end = line_ends[line];
+  var start = this.lineEnd(line) + 1;
+  var end = this.lineEnd(line + 1);
   return %_CallFunction(this.source, start, end, StringSubstring);
 }
 
 
 /**
  * Returns the number of source lines.
  * @return {number}
  *     Number of source lines.
  */
 function ScriptLineCount() {
   // Return number of source lines.
-  return this.line_ends.length;
+  return this.line_ends[NUMBER_OF_LINES_INDEX];
 }
 
 
 /**
  * If sourceURL comment is available returns sourceURL comment contents.
  * Otherwise, script name is returned. See
  * http://fbug.googlecode.com/svn/branches/firebug1.1/docs/ReleaseNotes_1.1.txt
  * and Source Map Revision 3 proposal for details on using //# sourceURL and
  * deprecated //@ sourceURL comment to identify scripts that don't have name.
  *
@@ skipping 14 matching lines @@
     "line_ends",
     "line_offset",
     "column_offset"
   ], [
     "lineFromPosition", ScriptLineFromPosition,
     "locationFromPosition", ScriptLocationFromPosition,
     "locationFromLine", ScriptLocationFromLine,
     "sourceSlice", ScriptSourceSlice,
     "sourceLine", ScriptSourceLine,
     "lineCount", ScriptLineCount,
-    "nameOrSourceURL", ScriptNameOrSourceURL
+    "nameOrSourceURL", ScriptNameOrSourceURL,
+    "lineEnd", ScriptLineEnd
   ]
 );
 
 
 /**
  * Class for source location. A source location is a position within some
  * source with the following properties:
  *   script   : script object for the source
  *   line     : source line number
  *   column   : source column within the line
@@ skipping 642 matching lines @@
   // Define accessors first, as this may fail and throw.
   ObjectDefineProperty(obj, 'stack', { get: StackTraceGetter,
                                        set: StackTraceSetter,
                                        configurable: true });
   %CollectStackTrace(obj, cons_opt ? cons_opt : captureStackTrace);
 };
 
 GlobalError.captureStackTrace = captureStackTrace;
 
 });