Change locationFromPosition() and locationFromLine() to use a binary search t...

src/messages.js

 // Copyright 2006-2008 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 212 matching lines @@
 
 function MakeEvalError(type, args) {
   return MakeGenericError($EvalError, type, args);
 }
 
 
 function MakeError(type, args) {
   return MakeGenericError($Error, type, args);
 }
 
+/**
+ * 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.
+ */
+Script.prototype.lineFromPosition = function(position) {
+  var lower = 0;
+  var upper = this.lineCount() - 1;
+
+  // We'll never find invalid positions so bail right away.
+  if (position > this.line_ends[upper]) {
+    return -1;
+  }
+
+  // This means we don't have to safe-guard indexing line_ends[i - 1].
+  if (position <= this.line_ends[0]) {
+    return 0;
+  }
+
+  // Binary search to find line # from position range.
+  while (upper >= 1) {
+    var i = (lower + upper) >> 1;
+
+    if (position > this.line_ends[i]) {
+      lower = i + 1;
+    } else if (position <= this.line_ends[i - 1]) {
+      upper = i - 1;
+    } else {
+      return i;
+    }
+  }
+  return -1;
+}
 
 /**
  * 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.
  */
 Script.prototype.locationFromPosition = function (position,
                                                   include_resource_offset) {
-  var lineCount = this.lineCount();
-  var line = -1;
-  if (position <= this.line_ends[0]) {
-    line = 0;
-  } else {
-    for (var i = 1; i < lineCount; i++) {
-      if (this.line_ends[i - 1] < position && position <= this.line_ends[i]) {
-        line = i;
-        break;
-      }
-    }
-  }
-
+  var line = this.lineFromPosition(position);
   if (line == -1) return null;
 
   // Determine start, end and column.
   var start = line == 0 ? 0 : this.line_ends[line - 1] + 1;
   var end = this.line_ends[line];
   if (end > 0 && this.source.charAt(end - 1) == '\r') end--;
   var column = position - start;
 
   // Adjust according to the offset within the resource.
   if (include_resource_offset) {
@@ skipping 34 matching lines @@
   var column = opt_column || 0;
   if (line == 0) {
     column -= this.column_offset
   }
 
   var offset_position = opt_offset_position || 0;
   if (line < 0 || column < 0 || offset_position < 0) return null;
   if (line == 0) {
     return this.locationFromPosition(offset_position + column, false);
   } else {
-    // Find the line where the offset position is located
-    var lineCount = this.lineCount();
-    var offset_line;
-    for (var i = 0; i < lineCount; i++) {
-      if (offset_position <= this.line_ends[i]) {
-        offset_line = i;
-        break;
-      }
+    // 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;
     }
-    if (offset_line + line >= lineCount) return null;
+
     return this.locationFromPosition(this.line_ends[offset_line + line - 1] + 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
@@ skipping 350 matching lines @@
     return this.name + ": " + FormatMessage({ type: type, args: this.arguments });
   }
   var message = this.message;
   return this.name + (message ? (": " + message) : "");
 }, DONT_ENUM);
 
 
 // Boilerplate for exceptions for stack overflows. Used from
 // Top::StackOverflow().
 const kStackOverflowBoilerplate = MakeRangeError('stack_overflow', []);