Heap profiler: correctly determine equivalence of objects having self-refs.

test/cctest/test-heap-profiler.cc

 // Copyright 2009 the V8 project authors. All rights reserved.
 //
 // Tests for heap profiler
 
 #ifdef ENABLE_LOGGING_AND_PROFILING
 
 #include "v8.h"
 #include "heap-profiler.h"
 #include "string-stream.h"
 #include "cctest.h"
@@ skipping 56 matching lines @@
   while (iterator.has_next()) {
     i::HeapObject* obj = iterator.next();
     cons_profile.CollectStats(obj);
   }
   CHECK_EQ(0, cons_profile.f_count());
   cons_profile.PrintStats();
   CHECK_EQ(2, cons_profile.f_count());
 }
 
 
-static JSObjectsCluster AddHeapObjectToTree(
-    JSObjectsRetainerTree* tree,
-    i::String* constructor,
-    int instance,
-    JSObjectsCluster* ref1 = NULL,
-    JSObjectsCluster* ref2 = NULL,
-    JSObjectsCluster* ref3 = NULL) {
+static JSObjectsCluster AddHeapObjectToTree(JSObjectsRetainerTree* tree,
+                                            i::String* constructor,
+                                            int instance,
+                                            JSObjectsCluster* ref1 = NULL,
+                                            JSObjectsCluster* ref2 = NULL,
+                                            JSObjectsCluster* ref3 = NULL) {
   JSObjectsCluster o(constructor, reinterpret_cast<i::Object*>(instance));
   JSObjectsClusterTree* o_tree = new JSObjectsClusterTree();
   JSObjectsClusterTree::Locator o_loc;
   if (ref1 != NULL) o_tree->Insert(*ref1, &o_loc);
   if (ref2 != NULL) o_tree->Insert(*ref2, &o_loc);
   if (ref3 != NULL) o_tree->Insert(*ref3, &o_loc);
   JSObjectsRetainerTree::Locator loc;
   tree->Insert(o, &loc);
   loc.set_value(o_tree);
   return o;
 }
 
 
+static void AddSelfReferenceToTree(JSObjectsRetainerTree* tree,
+                                   JSObjectsCluster* self_ref) {
+  JSObjectsRetainerTree::Locator loc;
+  CHECK(tree->Find(*self_ref, &loc));
+  JSObjectsClusterTree::Locator o_loc;
+  CHECK_NE(NULL, loc.value());
+  loc.value()->Insert(*self_ref, &o_loc);
+}
+
+
 static inline void CheckEqualsHelper(const char* file, int line,
                                      const char* expected_source,
                                      const JSObjectsCluster& expected,
                                      const char* value_source,
                                      const JSObjectsCluster& value) {
   if (JSObjectsCluster::Compare(expected, value) != 0) {
     i::HeapStringAllocator allocator;
     i::StringStream stream(&allocator);
     stream.Add("#  Expected: ");
     expected.DebugPrint(&stream);
     stream.Add("\n#  Found: ");
     value.DebugPrint(&stream);
     V8_Fatal(file, line, "CHECK_EQ(%s, %s) failed\n%s",
              expected_source, value_source,
              *stream.ToCString());
   }
 }
 
 
 static inline void CheckNonEqualsHelper(const char* file, int line,
                                      const char* expected_source,
                                      const JSObjectsCluster& expected,
                                      const char* value_source,
                                      const JSObjectsCluster& value) {
   if (JSObjectsCluster::Compare(expected, value) == 0) {
     i::HeapStringAllocator allocator;
     i::StringStream stream(&allocator);
-    stream.Add("#  Expected: ");
+    stream.Add("# !Expected: ");
     expected.DebugPrint(&stream);
     stream.Add("\n#  Found: ");
     value.DebugPrint(&stream);
     V8_Fatal(file, line, "CHECK_NE(%s, %s) failed\n%s",
              expected_source, value_source,
              *stream.ToCString());
   }
 }
 
 
@@ skipping 101 matching lines @@
       AddHeapObjectToTree(&tree, i::Heap::Object_symbol(), 0x300, &o21);
   JSObjectsCluster q =
       AddHeapObjectToTree(&tree, i::Heap::Object_symbol(), 0x310, &o21, &o22);
   JSObjectsCluster r =
       AddHeapObjectToTree(&tree, i::Heap::Object_symbol(), 0x320, &o22);
 
   ClustersCoarser coarser;
   coarser.Process(&tree);
 
   CHECK_EQ(JSObjectsCluster(), coarser.GetCoarseEquivalent(o));
+  CHECK_NE(JSObjectsCluster(), coarser.GetCoarseEquivalent(o11));
   CHECK_EQ(coarser.GetCoarseEquivalent(o11), coarser.GetCoarseEquivalent(o12));
   CHECK_EQ(coarser.GetCoarseEquivalent(o21), coarser.GetCoarseEquivalent(o22));
   CHECK_NE(coarser.GetCoarseEquivalent(o11), coarser.GetCoarseEquivalent(o21));
+  CHECK_NE(JSObjectsCluster(), coarser.GetCoarseEquivalent(p));
   CHECK_EQ(coarser.GetCoarseEquivalent(p), coarser.GetCoarseEquivalent(q));
   CHECK_EQ(coarser.GetCoarseEquivalent(q), coarser.GetCoarseEquivalent(r));
   CHECK_NE(coarser.GetCoarseEquivalent(o11), coarser.GetCoarseEquivalent(p));
   CHECK_NE(coarser.GetCoarseEquivalent(o21), coarser.GetCoarseEquivalent(p));
 }
 
 
+TEST(ClustersCoarserSelf) {
+  v8::HandleScope scope;
+  v8::Handle<v8::Context> env = v8::Context::New();
+  env->Enter();
+
+  i::ZoneScope zn_scope(i::DELETE_ON_EXIT);
+
+  JSObjectsRetainerTree tree;
+
+  // On the following graph:
+  //
+  // p (self-referencing)
+  //          <- o1     <-
+  // q (self-referencing)   o
+  //          <- o2     <-
+  // r (self-referencing)
+  //
+  // we expect that coarser will deduce equivalences: p ~ q ~ r, o1 ~ o2;
+
+  JSObjectsCluster o =
+      AddHeapObjectToTree(&tree, i::Heap::Object_symbol(), 0x100);
+  JSObjectsCluster o1 =
+      AddHeapObjectToTree(&tree, i::Heap::Object_symbol(), 0x110, &o);
+  JSObjectsCluster o2 =
+      AddHeapObjectToTree(&tree, i::Heap::Object_symbol(), 0x120, &o);
+  JSObjectsCluster p =
+      AddHeapObjectToTree(&tree, i::Heap::Object_symbol(), 0x300, &o1);
+  AddSelfReferenceToTree(&tree, &p);
+  JSObjectsCluster q =
+      AddHeapObjectToTree(&tree, i::Heap::Object_symbol(), 0x310, &o1, &o2);
+  AddSelfReferenceToTree(&tree, &q);
+  JSObjectsCluster r =
+      AddHeapObjectToTree(&tree, i::Heap::Object_symbol(), 0x320, &o2);
+  AddSelfReferenceToTree(&tree, &r);
+
+  ClustersCoarser coarser;
+  coarser.Process(&tree);
+
+  CHECK_EQ(JSObjectsCluster(), coarser.GetCoarseEquivalent(o));
+  CHECK_NE(JSObjectsCluster(), coarser.GetCoarseEquivalent(o1));
+  CHECK_EQ(coarser.GetCoarseEquivalent(o1), coarser.GetCoarseEquivalent(o2));
+  CHECK_NE(JSObjectsCluster(), coarser.GetCoarseEquivalent(p));
+  CHECK_EQ(coarser.GetCoarseEquivalent(p), coarser.GetCoarseEquivalent(q));
+  CHECK_EQ(coarser.GetCoarseEquivalent(q), coarser.GetCoarseEquivalent(r));
+  CHECK_NE(coarser.GetCoarseEquivalent(o1), coarser.GetCoarseEquivalent(p));
+}
+
+
 namespace {
 
 class RetainerProfilePrinter : public RetainerHeapProfile::Printer {
  public:
   RetainerProfilePrinter() : stream_(&allocator_), lines_(100) {}
 
   void PrintRetainers(const JSObjectsCluster& cluster,
                       const i::StringStream& retainers) {
     cluster.Print(&stream_);
     stream_.Add("%s", *(retainers.ToCString()));
@@ skipping 62 matching lines @@
   CHECK_EQ(static_cast<int>(strlen("(global property);1,B;2,C;2")),
            static_cast<int>(strlen(retainers_of_a)));
   CHECK(strstr(retainers_of_a, "(global property);1") != NULL);
   CHECK(strstr(retainers_of_a, "B;2") != NULL);
   CHECK(strstr(retainers_of_a, "C;2") != NULL);
   CHECK_EQ("(global property);2", printer.GetRetainers("B"));
   CHECK_EQ("(global property);1", printer.GetRetainers("C"));
 }
 
 #endif  // ENABLE_LOGGING_AND_PROFILING