[debugger] implement per-function code coverage.

src/debug/debug-coverage.cc

Index: src/debug/debug-coverage.cc
diff --git a/src/debug/debug-coverage.cc b/src/debug/debug-coverage.cc
new file mode 100644
index 0000000000000000000000000000000000000000..5446cdfab66291d649c096721d777b9966efce62
--- /dev/null
+++ b/src/debug/debug-coverage.cc
@@ -0,0 +1,137 @@
+// Copyright 2017 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/debug/debug-coverage.h"
+
+#include "src/base/hashmap.h"
+#include "src/objects-inl.h"
+#include "src/objects.h"
+
+namespace v8 {
+namespace internal {
+
+class SharedToCounterMap
+    : public base::TemplateHashMapImpl<SharedFunctionInfo*, uint32_t,
+                                       base::KeyEqualityMatcher<void*>,
+                                       base::DefaultAllocationPolicy> {
+ public:
+  typedef base::TemplateHashMapEntry<SharedFunctionInfo*, uint32_t> Entry;
+  inline void Add(SharedFunctionInfo* key, uint32_t count) {
+    Entry* entry = LookupOrInsert(key, Hash(key), []() { return 0; });
+    uint32_t old_count = entry->value;
+    if (UINT32_MAX - count < old_count) {
+      entry->value = UINT32_MAX;
+    } else {
+      entry->value = old_count + count;
+    }
+  }
+
+  inline uint32_t Get(SharedFunctionInfo* key) {
+    Entry* entry = Lookup(key, Hash(key));
+    if (entry == nullptr) return 0;
+    return entry->value;
+  }
+
+ private:
+  static uint32_t Hash(SharedFunctionInfo* key) {
+    return static_cast<uint32_t>(reinterpret_cast<intptr_t>(key));
+  }
+};
+
+class ScriptDataBuilder {
+ public:
+  void Add(int end_position, uint32_t count) {
+    DCHECK(entries_.empty() || entries_.back().end_position <= end_position);
+    if (entries_.empty()) {
+      if (end_position > 0) entries_.push_back({end_position, count});
+    } else if (entries_.back().count == count) {
+      // Extend last range.
+      entries_.back().end_position = end_position;
+    } else if (entries_.back().end_position < end_position) {
+      // Add new range.
+      entries_.push_back({end_position, count});
+    }
+  }
+  std::vector<Coverage::RangeEntry> Finish() { return std::move(entries_); }

[jgruber, 2017/02/09 15:43:22]

To be safe we could add a check to make sure Add is never called after Finish?

[Yang, 2017/02/09 17:11:01]

Apparently creating a temporary vector, swapping the content with entries_, and
return the temporary vector, is the way to go.

+
+ private:
+  std::vector<Coverage::RangeEntry> entries_;
+};
+
+std::vector<Coverage::ScriptData> Coverage::Collect(Isolate* isolate) {
+  SharedToCounterMap counter_map;
+  // Iterate the heap to find all feedback vectors and accumulate the
+  // invocation counts into the map for each shared function info.
+  HeapIterator heap_iterator(isolate->heap());
+  HeapObject* current_obj;
+  while ((current_obj = heap_iterator.next())) {
+    if (!current_obj->IsFeedbackVector()) continue;
+    FeedbackVector* vector = FeedbackVector::cast(current_obj);
+    SharedFunctionInfo* shared = vector->shared_function_info();
+    if (!shared->IsSubjectToDebugging()) continue;
+    uint32_t count = static_cast<uint32_t>(vector->invocation_count());
+    counter_map.Add(shared, count);
+  }
+
+  // Make sure entries in the counter map is not invalidated by GC.
+  DisallowHeapAllocation no_gc;
+
+  // Stack to track nested functions.
+  struct FunctionNode {
+    int start;
+    int end;
+    uint32_t count;
+  };
+  std::vector<FunctionNode> stack;
+
+  // Iterate shared function infos of every script and build a mapping
+  // between source ranges and invocation counts.
+  std::vector<Coverage::ScriptData> result;
+  Script::Iterator scripts(isolate);
+  while (Script* script = scripts.Next()) {
+    // Dismiss non-user scripts.
+    if (script->type() != Script::TYPE_NORMAL) continue;
+    DCHECK(stack.empty());
+    int script_end = String::cast(script->source())->length();
+    // If not rooted, the top-level function is likely no longer alive. Set the
+    // outer-most count to 1 to indicate that the script has run at least once.
+    stack.push_back({0, script_end, 1});
+    ScriptDataBuilder builder;
+    // Iterate through the list of shared function infos, reconstruct the
+    // nesting, and compute the ranges covering different invocation counts.
+    HandleScope scope(isolate);
+    SharedFunctionInfo::ScriptIterator infos(Handle<Script>(script, isolate));
+    while (SharedFunctionInfo* info = infos.Next()) {
+      int start = info->function_token_position();
+      if (start == kNoSourcePosition) start = info->start_position();
+      int end = info->end_position();
+      uint32_t count = counter_map.Get(info);
+      // The shared function infos are sorted by start.

[jgruber, 2017/02/09 15:43:22]

Is end also taken into account? I'm thinking of a case in which two functions
have the same start position:

a: {0, 5}
b: {0, 7}

Can b ever come before a? I suppose not, but maybe we can add a DCHECK.

[Yang, 2017/02/09 17:11:01]

actually b can only come before a, since we parse from outer functions into
inner functions. I added a DCHECK. Then again I can't think of a way to do this
except for the top-level function.

+      DCHECK(stack.back().start <= start);

[jgruber, 2017/02/09 15:43:22]

Nit: DCHECK_LE here and below.

[Yang, 2017/02/09 17:11:01]

Done.

+      // Drop the stack to the outer function.
+      while (start > stack.back().end) {
+        // Write out rest of function being dropped.
+        builder.Add(stack.back().end, stack.back().count);
+        stack.pop_back();
+      }
+      // Write out outer function up to the start of new function.
+      builder.Add(start, stack.back().count);
+      // New nested function.
+      DCHECK(end <= stack.back().end);
+      stack.push_back({start, end, count});
+    }
+
+    // Drop the stack to the script level.
+    while (!stack.empty()) {
+      // Write out rest of function being dropped.
+      builder.Add(stack.back().end, stack.back().count);
+      stack.pop_back();
+    }
+    result.push_back({script->id(), builder.Finish()});

[jgruber, 2017/02/09 15:43:22]

I guess these vector copies are turned into moves by the compiler.. What about
using emplace_back to construct in-place?

[jgruber, 2017/02/09 15:53:22]

Actually, we probably need a move constructor for ScriptData.

[Yang, 2017/02/09 17:11:01]

Done.

[Yang, 2017/02/09 17:11:01]

We are fine with the default move constructor?

+  }
+  return result;
+}
+
+}  // namespace internal
+}  // namespace v8