Author: [email protected]
Date: Tue Jun 9 00:03:21 2009
New Revision: 2125
Modified:
branches/bleeding_edge/src/messages.js
branches/bleeding_edge/test/mjsunit/debug-sourceinfo.js
Log:
Change locationFromPosition() and locationFromLine() to use a binary search
to locate line numbers from position numbers. Modify test
debug-sourceinfo.js to include more tests, including error conditions.
Patch by Matt Hanselman, see http://codereview.chromium.org/118371.
BUG=213
TEST=test/mjsunit/debug-sourceinfo.js
Review URL: http://codereview.chromium.org/118425
Modified: branches/bleeding_edge/src/messages.js
==============================================================================
--- branches/bleeding_edge/src/messages.js (original)
+++ branches/bleeding_edge/src/messages.js Tue Jun 9 00:03:21 2009
@@ -230,6 +230,40 @@
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.
@@ -241,19 +275,7 @@
*/
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.
@@ -308,16 +330,13 @@
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.
}
}
Modified: branches/bleeding_edge/test/mjsunit/debug-sourceinfo.js
==============================================================================
--- branches/bleeding_edge/test/mjsunit/debug-sourceinfo.js (original)
+++ branches/bleeding_edge/test/mjsunit/debug-sourceinfo.js Tue Jun 9
00:03:21 2009
@@ -38,6 +38,23 @@
return 1;
}
};
+function d(x) {
+ x = 1 ;
+ x = 2 ;
+ x = 3 ;
+ x = 4 ;
+ x = 5 ;
+ x = 6 ;
+ x = 7 ;
+ x = 8 ;
+ x = 9 ;
+ x = 10;
+ x = 11;
+ x = 12;
+ x = 13;
+ x = 14;
+ x = 15;
+}
// Get the Debug object exposed from the debug context global object.
Debug = debug.Debug
@@ -45,22 +62,42 @@
// This is the number of comment lines above the first test function.
var comment_lines = 29;
+// This is the last position in the entire file (note: this equals
+// file size of <debug-sourceinfo.js> - 1, since starting at 0).
+var last_position = 14072;
+// This is the last line of entire file (note: starting at 0).
+var last_line = 345;
+// This is the last column of last line (note: starting at 0 and +2, due
+// to trailing <CR><LF>).
+var last_column = 48;
+
// This magic number is the length or the first line comment (actually
number
// of characters before 'function a(...'.
var comment_line_length = 1726;
var start_a = 10 + comment_line_length;
var start_b = 37 + comment_line_length;
var start_c = 71 + comment_line_length;
+var start_d = 163 + comment_line_length;
+
+// The position of the first line of d(), i.e. "x = 1 ;".
+var start_code_d = start_d + 7;
+// The line # of the first line of d() (note: starting at 0).
+var start_line_d = 41;
+var line_length_d = 11;
+var num_lines_d = 15;
assertEquals(start_a, Debug.sourcePosition(a));
assertEquals(start_b, Debug.sourcePosition(b));
assertEquals(start_c, Debug.sourcePosition(c));
+assertEquals(start_d, Debug.sourcePosition(d));
var script = Debug.findScript(a);
assertTrue(script.data === Debug.findScript(b).data);
assertTrue(script.data === Debug.findScript(c).data);
+assertTrue(script.data === Debug.findScript(d).data);
assertTrue(script.source === Debug.findScript(b).source);
assertTrue(script.source === Debug.findScript(c).source);
+assertTrue(script.source === Debug.findScript(d).source);
// Test that when running through source positions the position, line and
// column progresses as expected.
@@ -89,6 +126,19 @@
column = location.column;
}
+// Every line of d() is the same length. Verify we can loop through all
+// positions and find the right line # for each.
+var p = start_code_d;
+for (line = 0; line < num_lines_d; line++) {
+ for (column = 0; column < line_length_d; column++) {
+ var location = script.locationFromPosition(p);
+ assertEquals(p, location.position);
+ assertEquals(start_line_d + line, location.line);
+ assertEquals(column, location.column);
+ p++;
+ }
+}
+
// Test first position.
assertEquals(0, script.locationFromPosition(0).position);
assertEquals(0, script.locationFromPosition(0).line);
@@ -99,21 +149,26 @@
assertEquals(0, script.locationFromPosition(1).line);
assertEquals(1, script.locationFromPosition(1).column);
-// Test first position in finction a.
+// Test first position in function a().
assertEquals(start_a, script.locationFromPosition(start_a).position);
assertEquals(0, script.locationFromPosition(start_a).line - comment_lines);
assertEquals(10, script.locationFromPosition(start_a).column);
-// Test first position in finction b.
+// Test first position in function b().
assertEquals(start_b, script.locationFromPosition(start_b).position);
assertEquals(1, script.locationFromPosition(start_b).line - comment_lines);
assertEquals(13, script.locationFromPosition(start_b).column);
-// Test first position in finction b.
+// Test first position in function c().
assertEquals(start_c, script.locationFromPosition(start_c).position);
assertEquals(4, script.locationFromPosition(start_c).line - comment_lines);
assertEquals(12, script.locationFromPosition(start_c).column);
+// Test first position in function d().
+assertEquals(start_d, script.locationFromPosition(start_d).position);
+assertEquals(11, script.locationFromPosition(start_d).line -
comment_lines);
+assertEquals(10, script.locationFromPosition(start_d).column);
+
// Test first line.
assertEquals(0, script.locationFromLine().position);
assertEquals(0, script.locationFromLine().line);
@@ -122,17 +177,17 @@
assertEquals(0, script.locationFromLine(0).line);
assertEquals(0, script.locationFromLine(0).column);
-// Test first line column 1
+// Test first line column 1.
assertEquals(1, script.locationFromLine(0, 1).position);
assertEquals(0, script.locationFromLine(0, 1).line);
assertEquals(1, script.locationFromLine(0, 1).column);
-// Test first line offset 1
+// Test first line offset 1.
assertEquals(1, script.locationFromLine(0, 0, 1).position);
assertEquals(0, script.locationFromLine(0, 0, 1).line);
assertEquals(1, script.locationFromLine(0, 0, 1).column);
-// Test offset function a
+// Test offset function a().
assertEquals(start_a, script.locationFromLine(void 0, void 0,
start_a).position);
assertEquals(0, script.locationFromLine(void 0, void 0, start_a).line -
comment_lines);
assertEquals(10, script.locationFromLine(void 0, void 0, start_a).column);
@@ -143,27 +198,27 @@
assertEquals(0, script.locationFromLine(0, 0, start_a).line -
comment_lines);
assertEquals(10, script.locationFromLine(0, 0, start_a).column);
-// Test second line offset function a
+// Test second line offset function a().
assertEquals(start_a + 14, script.locationFromLine(1, 0,
start_a).position);
assertEquals(1, script.locationFromLine(1, 0, start_a).line -
comment_lines);
assertEquals(0, script.locationFromLine(1, 0, start_a).column);
-// Test second line column 2 offset function a
+// Test second line column 2 offset function a().
assertEquals(start_a + 14 + 2, script.locationFromLine(1, 2,
start_a).position);
assertEquals(1, script.locationFromLine(1, 2, start_a).line -
comment_lines);
assertEquals(2, script.locationFromLine(1, 2, start_a).column);
-// Test offset function b
+// Test offset function b().
assertEquals(start_b, script.locationFromLine(0, 0, start_b).position);
assertEquals(1, script.locationFromLine(0, 0, start_b).line -
comment_lines);
assertEquals(13, script.locationFromLine(0, 0, start_b).column);
-// Test second line offset function b
+// Test second line offset function b().
assertEquals(start_b + 6, script.locationFromLine(1, 0, start_b).position);
assertEquals(2, script.locationFromLine(1, 0, start_b).line -
comment_lines);
assertEquals(0, script.locationFromLine(1, 0, start_b).column);
-// Test second line column 11 offset function b
+// Test second line column 11 offset function b().
assertEquals(start_b + 6 + 11, script.locationFromLine(1, 11,
start_b).position);
assertEquals(2, script.locationFromLine(1, 11, start_b).line -
comment_lines);
assertEquals(11, script.locationFromLine(1, 11, start_b).column);
@@ -187,6 +242,21 @@
assertEquals(52 + start_c, Debug.findFunctionSourceLocation(c, 4,
0).position);
assertEquals(69 + start_c, Debug.findFunctionSourceLocation(c, 5,
0).position);
assertEquals(76 + start_c, Debug.findFunctionSourceLocation(c, 6,
0).position);
+assertEquals(0 + start_d, Debug.findFunctionSourceLocation(d, 0,
0).position);
+assertEquals(7 + start_d, Debug.findFunctionSourceLocation(d, 1,
0).position);
+for (i = 1; i <= num_lines_d; i++) {
+ assertEquals(7 + (i * line_length_d) + start_d,
Debug.findFunctionSourceLocation(d, (i + 1), 0).position);
+}
+assertEquals(175 + start_d, Debug.findFunctionSourceLocation(d, 17,
0).position);
+
+// Make sure invalid inputs work properly.
+assertEquals(0, script.locationFromPosition(-1).line);
+assertEquals(null, script.locationFromPosition(last_position + 1));
+
+// Test last position.
+assertEquals(last_position,
script.locationFromPosition(last_position).position);
+assertEquals(last_line, script.locationFromPosition(last_position).line);
+assertEquals(last_column,
script.locationFromPosition(last_position).column);
// Test source line and restriction. All the following tests start from
line 1
// column 2 in function b, which is the call to c.
--~--~---------~--~----~------------~-------~--~----~
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
-~----------~----~----~----~------~----~------~--~---
