Refactor script position calculation

src/objects.cc

 // Copyright 2015 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.
 
 #include "src/objects.h"
 
 #include <cmath>
 #include <iomanip>
 #include <sstream>
 
@@ skipping 12360 matching lines @@
   Handle<FixedArray> array = String::CalculateLineEnds(src, true);
 
   if (*array != isolate->heap()->empty_fixed_array()) {
     array->set_map(isolate->heap()->fixed_cow_array_map());
   }
 
   script->set_line_ends(*array);
   DCHECK(script->line_ends()->IsFixedArray());
 }
 
+bool Script::GetPositionInfo(Handle<Script> script, int position,
+                             PositionInfo* info, bool with_offset) {
+  InitLineEnds(script);

[Yang, 2016/05/18 13:23:09]

You can avoid this wrapper if you do something like this:

bool Script::GetPositionInfo(int position,
                             PositionInfo* info, bool with_offset) {
  Handle<Script> script(this);
  InitLineEnds(script);
  DisallowHeapAllocation no_gc;
  ...
}

[jgruber1, 2016/05/19 08:05:24]

I used the wrapper in order to keep Script::GetLineNumber(int) allocation-free.
Not sure how essential that is, do you know more about it?

[jgruber1, 2016/05/19 08:56:01]

Done, removed the static wrapper.

+  return script->GetPositionInfo(position, info, with_offset);
+}
+
+#define SMI_VALUE(x) (Smi::cast(x)->value())
+bool Script::GetPositionInfo(int position, PositionInfo* info,
+                             bool with_offset) {
+  DisallowHeapAllocation no_allocation;
+
+  DCHECK(line_ends()->IsFixedArray());
+  FixedArray* ends = FixedArray::cast(line_ends());
+
+  const int ends_len = ends->length();
+  if (ends_len == 0) return false;
+
+  // Return early on invalid positions. Negative positions behave as if 0 was
+  // passed, and positions beyond the end of the script return as failure.
+  if (position < 0) {
+    position = 0;
+  } else if (position > SMI_VALUE(ends->get(ends_len - 1))) {
+    return false;
+  }
+
+  // Determine line number by doing a binary search on the line ends array.
+  if (SMI_VALUE(ends->get(0)) >= position) {
+    info->line = 0;
+    info->line_start = 0;
+    info->column = position;
+  } else {
+    int left = 0;
+    int right = ends_len - 1;
+
+    while (right > 0) {
+      const int mid = (left + right) / 2;
+      if (right < left) {

[Yang, 2016/05/18 13:23:09]

Let's just DCHECK_GE(right, left);

[jgruber1, 2016/05/19 08:05:24]

Done (DCHECK_LT(left, right)).

+        UNREACHABLE();
+      } else if (position > SMI_VALUE(ends->get(mid))) {
+        left = mid + 1;
+      } else if (position <= SMI_VALUE(ends->get(mid - 1))) {
+        right = mid - 1;
+      } else {
+        info->line = mid;
+        break;
+      }
+    }
+    DCHECK(SMI_VALUE(ends->get(info->line)) >= position &&
+           SMI_VALUE(ends->get(info->line - 1)) < position);
+    info->line_start = SMI_VALUE(ends->get(info->line - 1)) + 1;
+    info->column = position - info->line_start;
+  }
+
+  // Line end is position of the linebreak character.
+  info->line_end = SMI_VALUE(ends->get(info->line));
+  if (info->line_end > 0) {
+    DCHECK(source()->IsString());
+    Handle<String> src(String::cast(source()));
+    if (src->Get(info->line_end - 1) == '\r') {
+      info->line_end--;
+    }
+  }
+
+  // Add offsets if requested.
+  if (with_offset) {
+    if (info->line == 0) {
+      info->column += column_offset();
+    }
+    info->line += line_offset();
+  }
+
+  return true;
+}
+#undef SMI_VALUE
 
 int Script::GetColumnNumber(Handle<Script> script, int code_pos) {
-  int line_number = GetLineNumber(script, code_pos);
-  if (line_number == -1) return -1;
+  PositionInfo info;
+  if (!GetPositionInfo(script, code_pos, &info, true)) {
+    return -1;
+  }
 
-  DisallowHeapAllocation no_allocation;
-  FixedArray* line_ends_array = FixedArray::cast(script->line_ends());
-  line_number = line_number - script->line_offset();
-  if (line_number == 0) return code_pos + script->column_offset();
-  int prev_line_end_pos =
-      Smi::cast(line_ends_array->get(line_number - 1))->value();
-  return code_pos - (prev_line_end_pos + 1);
+  return info.column;
+}
+
+int Script::GetLineNumberWithArray(int code_pos) {
+  PositionInfo info;
+  if (!GetPositionInfo(code_pos, &info, true)) {
+    return -1;
+  }
+
+  return info.line;
 }
 
 
-int Script::GetLineNumberWithArray(int code_pos) {
-  DisallowHeapAllocation no_allocation;
-  DCHECK(line_ends()->IsFixedArray());
-  FixedArray* line_ends_array = FixedArray::cast(line_ends());
-  int line_ends_len = line_ends_array->length();
-  if (line_ends_len == 0) return -1;
-
-  if ((Smi::cast(line_ends_array->get(0)))->value() >= code_pos) {
-    return line_offset();
-  }
-
-  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;
-    }
-  }
-  return right + line_offset();
-}
-
-
 int Script::GetLineNumber(Handle<Script> script, int code_pos) {
   InitLineEnds(script);
   return script->GetLineNumberWithArray(code_pos);
 }
 
 
 int Script::GetLineNumber(int code_pos) {
   DisallowHeapAllocation no_allocation;
   if (!line_ends()->IsUndefined()) return GetLineNumberWithArray(code_pos);
 
@@ skipping 5951 matching lines @@
   if (cell->value() != *new_value) {
     cell->set_value(*new_value);
     Isolate* isolate = cell->GetIsolate();
     cell->dependent_code()->DeoptimizeDependentCodeGroup(
         isolate, DependentCode::kPropertyCellChangedGroup);
   }
 }
 
 }  // namespace internal
 }  // namespace v8