ahat: Show GC Root Paths.

The Dominator Path in the objects view is replaced by an augmented
Sample Path from GC Root, which includes non-dominator objects
along a sample path and field names.

Also, use blanks instead of "0" in heap tables when the size is 0.
This cleans up the pages a little, and conveniently lets us
distinguish between dominator and non-dominator objects in the Sample
Path from GC Root.

Test: m ahat-test, with new InstanceUtils.gcRootPath test added.

Bug: 27299030
Change-Id: I53d75f9dcb3157c2b5b3afc74958711536cd67b6
diff --git a/tools/ahat/Android.mk b/tools/ahat/Android.mk
index 4003ee0..ebf087d 100644
--- a/tools/ahat/Android.mk
+++ b/tools/ahat/Android.mk
@@ -73,7 +73,7 @@
   $(ART_HOST_EXECUTABLES) \
   $(ART_HOST_SHARED_LIBRARY_DEPENDENCIES) \
   $(HOST_OUT_EXECUTABLES)/art \
-  $(HOST_CORE_IMG_OUT_BASE)-optimizing-pic$(CORE_IMG_SUFFIX)
+  $(HOST_CORE_IMG_OUT_BASE)$(CORE_IMG_SUFFIX)
 
 $(AHAT_TEST_DUMP_HPROF): PRIVATE_AHAT_TEST_ART := $(HOST_OUT_EXECUTABLES)/art
 $(AHAT_TEST_DUMP_HPROF): PRIVATE_AHAT_TEST_DUMP_JAR := $(AHAT_TEST_DUMP_JAR)
diff --git a/tools/ahat/README.txt b/tools/ahat/README.txt
index ecf9e53..8604ff0 100644
--- a/tools/ahat/README.txt
+++ b/tools/ahat/README.txt
@@ -9,7 +9,6 @@
        Serve pages on the given port. Defaults to 7100.
 
 TODO:
- * Show GC Root paths.
  * Have a way to diff two heap dumps.
 
  * Add more tips to the help page.
@@ -76,6 +75,7 @@
 
 Release History:
  0.8 Pending
+   Show sample path from GC root with field names in place of dominator path.
 
  0.7 Aug 16, 2016
    Launch ahat server before processing the heap dump.
diff --git a/tools/ahat/src/HeapTable.java b/tools/ahat/src/HeapTable.java
index ed11d17..5b84048 100644
--- a/tools/ahat/src/HeapTable.java
+++ b/tools/ahat/src/HeapTable.java
@@ -84,10 +84,10 @@
       for (Heap heap : heaps) {
         long size = config.getSize(elem, heap);
         total += size;
-        vals.add(DocString.format("%,14d", size));
+        vals.add(size == 0 ? DocString.text("") : DocString.format("%,14d", size));
       }
       if (showTotal) {
-        vals.add(DocString.format("%,14d", total));
+        vals.add(total == 0 ? DocString.text("") : DocString.format("%,14d", total));
       }
 
       for (ValueConfig<T> value : values) {
diff --git a/tools/ahat/src/InstanceUtils.java b/tools/ahat/src/InstanceUtils.java
index 8769d11..94934a2 100644
--- a/tools/ahat/src/InstanceUtils.java
+++ b/tools/ahat/src/InstanceUtils.java
@@ -19,11 +19,17 @@
 import com.android.tools.perflib.heap.ArrayInstance;
 import com.android.tools.perflib.heap.ClassInstance;
 import com.android.tools.perflib.heap.ClassObj;
+import com.android.tools.perflib.heap.Field;
 import com.android.tools.perflib.heap.Heap;
 import com.android.tools.perflib.heap.Instance;
+import com.android.tools.perflib.heap.RootObj;
 import com.android.tools.perflib.heap.Type;
 
 import java.awt.image.BufferedImage;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import java.util.Map;
 
 /**
  * Utilities for extracting information from hprof instances.
@@ -179,7 +185,7 @@
    * Read a reference field of an instance.
    * Returns null if the field value is null, or if the field couldn't be read.
    */
-  private static Instance getRefField(Instance inst, String fieldName) {
+  public static Instance getRefField(Instance inst, String fieldName) {
     Object value = getField(inst, fieldName);
     if (!(value instanceof Instance)) {
       return null;
@@ -357,4 +363,90 @@
     }
     return new NativeAllocation(size, inst.getHeap(), pointer, referent);
   }
+
+  public static class PathElement {
+    public final Instance instance;
+    public final String field;
+    public boolean isDominator;
+
+    public PathElement(Instance instance, String field) {
+      this.instance = instance;
+      this.field = field;
+      this.isDominator = false;
+    }
+  }
+
+  /**
+   * Returns a sample path from a GC root to this instance.
+   * The given instance is included as the last element of the path with an
+   * empty field description.
+   */
+  public static List<PathElement> getPathFromGcRoot(Instance inst) {
+    List<PathElement> path = new ArrayList<PathElement>();
+
+    Instance dom = inst;
+    for (PathElement elem = new PathElement(inst, ""); elem != null;
+        elem = getNextPathElementToGcRoot(elem.instance)) {
+      if (elem.instance == dom) {
+        elem.isDominator = true;
+        dom = dom.getImmediateDominator();
+      }
+      path.add(elem);
+    }
+    Collections.reverse(path);
+    return path;
+  }
+
+  /**
+   * Returns the next instance to GC root from this object and a string
+   * description of which field of that object refers to the given instance.
+   * Returns null if the given instance has no next instance to the gc root.
+   */
+  private static PathElement getNextPathElementToGcRoot(Instance inst) {
+    Instance parent = inst.getNextInstanceToGcRoot();
+    if (parent == null || parent instanceof RootObj) {
+      return null;
+    }
+
+    // Search the parent for the reference to the child.
+    // TODO: This seems terribly inefficient. Can we use data structures to
+    // help us here?
+    String description = ".???";
+    if (parent instanceof ArrayInstance) {
+      ArrayInstance array = (ArrayInstance)parent;
+      Object[] values = array.getValues();
+      for (int i = 0; i < values.length; i++) {
+        if (values[i] instanceof Instance) {
+          Instance ref = (Instance)values[i];
+          if (ref.getId() == inst.getId()) {
+            description = String.format("[%d]", i);
+            break;
+          }
+        }
+      }
+    } else if (parent instanceof ClassObj) {
+      ClassObj cls = (ClassObj)parent;
+      for (Map.Entry<Field, Object> entries : cls.getStaticFieldValues().entrySet()) {
+        if (entries.getValue() instanceof Instance) {
+          Instance ref = (Instance)entries.getValue();
+          if (ref.getId() == inst.getId()) {
+            description = "." + entries.getKey().getName();
+            break;
+          }
+        }
+      }
+    } else if (parent instanceof ClassInstance) {
+      ClassInstance obj = (ClassInstance)parent;
+      for (ClassInstance.FieldValue fields : obj.getValues()) {
+        if (fields.getValue() instanceof Instance) {
+          Instance ref = (Instance)fields.getValue();
+          if (ref.getId() == inst.getId()) {
+            description = "." + fields.getField().getName();
+            break;
+          }
+        }
+      }
+    }
+    return new PathElement(parent, description);
+  }
 }
diff --git a/tools/ahat/src/ObjectHandler.java b/tools/ahat/src/ObjectHandler.java
index 4df1be5..78aac17 100644
--- a/tools/ahat/src/ObjectHandler.java
+++ b/tools/ahat/src/ObjectHandler.java
@@ -22,7 +22,6 @@
 import com.android.tools.perflib.heap.Field;
 import com.android.tools.perflib.heap.Heap;
 import com.android.tools.perflib.heap.Instance;
-import com.android.tools.perflib.heap.RootObj;
 import com.android.tools.perflib.heap.RootType;
 import java.io.IOException;
 import java.util.ArrayList;
@@ -32,6 +31,8 @@
 import java.util.List;
 import java.util.Map;
 
+import static com.android.ahat.InstanceUtils.PathElement;
+
 class ObjectHandler implements AhatHandler {
 
   private static final String ARRAY_ELEMENTS_ID = "elements";
@@ -62,7 +63,7 @@
     doc.big(Value.render(mSnapshot, inst));
 
     printAllocationSite(doc, query, inst);
-    printDominatorPath(doc, query, inst);
+    printGcRootPath(doc, query, inst);
 
     doc.section("Object Info");
     ClassObj cls = inst.getClassObj();
@@ -202,43 +203,43 @@
     }
   }
 
-  private void printDominatorPath(Doc doc, Query query, Instance inst) {
-    doc.section("Dominator Path from Root");
-    List<Instance> path = new ArrayList<Instance>();
-    for (Instance parent = inst;
-        parent != null && !(parent instanceof RootObj);
-        parent = parent.getImmediateDominator()) {
-      path.add(parent);
-    }
+  private void printGcRootPath(Doc doc, Query query, Instance inst) {
+    doc.section("Sample Path from GC Root");
+    List<PathElement> path = InstanceUtils.getPathFromGcRoot(inst);
 
     // Add 'null' as a marker for the root.
-    path.add(null);
-    Collections.reverse(path);
+    path.add(0, null);
 
-    HeapTable.TableConfig<Instance> table = new HeapTable.TableConfig<Instance>() {
+    HeapTable.TableConfig<PathElement> table = new HeapTable.TableConfig<PathElement>() {
       public String getHeapsDescription() {
-        return "Bytes Retained by Heap";
+        return "Bytes Retained by Heap (Dominators Only)";
       }
 
-      public long getSize(Instance element, Heap heap) {
+      public long getSize(PathElement element, Heap heap) {
         if (element == null) {
           return mSnapshot.getHeapSize(heap);
         }
-        int index = mSnapshot.getHeapIndex(heap);
-        return element.getRetainedSize(index);
+        if (element.isDominator) {
+          int index = mSnapshot.getHeapIndex(heap);
+          return element.instance.getRetainedSize(index);
+        }
+        return 0;
       }
 
-      public List<HeapTable.ValueConfig<Instance>> getValueConfigs() {
-        HeapTable.ValueConfig<Instance> value = new HeapTable.ValueConfig<Instance>() {
+      public List<HeapTable.ValueConfig<PathElement>> getValueConfigs() {
+        HeapTable.ValueConfig<PathElement> value = new HeapTable.ValueConfig<PathElement>() {
           public String getDescription() {
-            return "Object";
+            return "Path Element";
           }
 
-          public DocString render(Instance element) {
+          public DocString render(PathElement element) {
             if (element == null) {
               return DocString.link(DocString.uri("rooted"), DocString.text("ROOT"));
             } else {
-              return DocString.text("→ ").append(Value.render(mSnapshot, element));
+              DocString label = DocString.text(" → ");
+              label.append(Value.render(mSnapshot, element.instance));
+              label.append(element.field);
+              return label;
             }
           }
         };
diff --git a/tools/ahat/test-dump/Main.java b/tools/ahat/test-dump/Main.java
index 3936f29..e08df67 100644
--- a/tools/ahat/test-dump/Main.java
+++ b/tools/ahat/test-dump/Main.java
@@ -29,6 +29,16 @@
   // collected before we take the heap dump.
   public static DumpedStuff stuff;
 
+  public static class ObjectTree {
+    public ObjectTree left;
+    public ObjectTree right;
+
+    public ObjectTree(ObjectTree left, ObjectTree right) {
+      this.left = left;
+      this.right = right;
+    }
+  }
+
   // We will take a heap dump that includes a single instance of this
   // DumpedStuff class. Objects stored as fields in this class can be easily
   // found in the hprof dump by searching for the instance of the DumpedStuff
@@ -42,6 +52,11 @@
     public PhantomReference aPhantomReference = new PhantomReference(anObject, referenceQueue);
     public WeakReference aWeakReference = new WeakReference(anObject, referenceQueue);
     public byte[] bigArray;
+    public ObjectTree[] gcPathArray = new ObjectTree[]{null, null,
+      new ObjectTree(
+          new ObjectTree(null, new ObjectTree(null, null)),
+          new ObjectTree(null, null)),
+      null};
 
     DumpedStuff() {
       int N = 1000000;
@@ -53,6 +68,8 @@
       NativeAllocationRegistry registry = new NativeAllocationRegistry(
           Main.class.getClassLoader(), 0x12345, 42);
       registry.registerNativeAllocation(anObject, 0xABCDABCD);
+
+      gcPathArray[2].right.left = gcPathArray[2].left.right;
     }
   }
 
diff --git a/tools/ahat/test/InstanceUtilsTest.java b/tools/ahat/test/InstanceUtilsTest.java
index 59b1c90..ec77e70 100644
--- a/tools/ahat/test/InstanceUtilsTest.java
+++ b/tools/ahat/test/InstanceUtilsTest.java
@@ -16,11 +16,16 @@
 
 package com.android.ahat;
 
+import com.android.tools.perflib.heap.ArrayInstance;
+import com.android.tools.perflib.heap.ClassObj;
 import com.android.tools.perflib.heap.Instance;
 import java.io.IOException;
+import java.util.List;
 import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertNotNull;
 import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertTrue;
 import org.junit.Test;
 
 public class InstanceUtilsTest {
@@ -123,4 +128,55 @@
     assertEquals(referent, InstanceUtils.getReferent(wref));
     assertNull(InstanceUtils.getReferent(referent));
   }
+
+  @Test
+  public void gcRootPath() throws IOException {
+    TestDump dump = TestDump.getTestDump();
+
+    ClassObj main = dump.getAhatSnapshot().findClass("Main");
+    ArrayInstance gcPathArray = (ArrayInstance)dump.getDumpedThing("gcPathArray");
+    Object[] values = gcPathArray.getValues();
+    Instance base = (Instance)values[2];
+    Instance left = InstanceUtils.getRefField(base, "left");
+    Instance right = InstanceUtils.getRefField(base, "right");
+    Instance target = InstanceUtils.getRefField(left, "right");
+
+    List<InstanceUtils.PathElement> path = InstanceUtils.getPathFromGcRoot(target);
+    assertEquals(6, path.size());
+
+    assertEquals(main, path.get(0).instance);
+    assertEquals(".stuff", path.get(0).field);
+    assertTrue(path.get(0).isDominator);
+
+    assertEquals(".gcPathArray", path.get(1).field);
+    assertTrue(path.get(1).isDominator);
+
+    assertEquals(gcPathArray, path.get(2).instance);
+    assertEquals("[2]", path.get(2).field);
+    assertTrue(path.get(2).isDominator);
+
+    assertEquals(base, path.get(3).instance);
+    assertTrue(path.get(3).isDominator);
+
+    // There are two possible paths. Either it can go through the 'left' node,
+    // or the 'right' node.
+    if (path.get(3).field.equals(".left")) {
+      assertEquals(".left", path.get(3).field);
+
+      assertEquals(left, path.get(4).instance);
+      assertEquals(".right", path.get(4).field);
+      assertFalse(path.get(4).isDominator);
+
+    } else {
+      assertEquals(".right", path.get(3).field);
+
+      assertEquals(right, path.get(4).instance);
+      assertEquals(".left", path.get(4).field);
+      assertFalse(path.get(4).isDominator);
+    }
+
+    assertEquals(target, path.get(5).instance);
+    assertEquals("", path.get(5).field);
+    assertTrue(path.get(5).isDominator);
+  }
 }