ahat: Improve field diffing.

* Factor field diffing code out of Diff into its own class.
* Switch to a new interface for diffing fields that does not rely on
  being passed mutable lists.
* Reimplement field diff to work better when fields have been added,
  deleted, or reordered.

Bug: 62408050
Test: m ahat-test, with new tests for field diff added.
Change-Id: I56c0414f8f4c11809895d809494d752201d33563

12 files changed, 457 insertions, 178 deletions

diff --git a/tools/ahat/src/ObjectHandler.java b/tools/ahat/src/ObjectHandler.java
index d6f1faa3c3..cc55b7a7df 100644
--- a/tools/ahat/src/ObjectHandler.java
+++ b/tools/ahat/src/ObjectHandler.java
@@ -21,13 +21,15 @@ import com.android.ahat.heapdump.AhatClassInstance;
 import com.android.ahat.heapdump.AhatClassObj;
 import com.android.ahat.heapdump.AhatInstance;
 import com.android.ahat.heapdump.AhatSnapshot;
-import com.android.ahat.heapdump.Diff;
+import com.android.ahat.heapdump.DiffFields;
+import com.android.ahat.heapdump.DiffedFieldValue;
 import com.android.ahat.heapdump.FieldValue;
 import com.android.ahat.heapdump.PathElement;
 import com.android.ahat.heapdump.Site;
 import com.android.ahat.heapdump.Value;
 import java.io.IOException;
 import java.util.Collection;
+import java.util.Collections;
 import java.util.List;
 import java.util.Objects;
 
@@ -108,13 +110,9 @@ class ObjectHandler implements AhatHandler {
   private static void printClassInstanceFields(Doc doc, Query query, AhatClassInstance inst) {
     doc.section("Fields");
     AhatInstance base = inst.getBaseline();
-    List<FieldValue> fields = inst.getInstanceFields();
-    if (!base.isPlaceHolder()) {
-      Diff.fields(fields, base.asClassInstance().getInstanceFields());
-    }
-    SubsetSelector<FieldValue> selector = new SubsetSelector(query, INSTANCE_FIELDS_ID, fields);
-    printFields(doc, inst != base && !base.isPlaceHolder(), selector.selected());
-    selector.render(doc);
+    printFields(doc, query, INSTANCE_FIELDS_ID, !base.isPlaceHolder(),
+        inst.asClassInstance().getInstanceFields(),
+        base.isPlaceHolder() ? null : base.asClassInstance().getInstanceFields());
   }
 
   private static void printArrayElements(Doc doc, Query query, AhatArrayInstance array) {
@@ -145,36 +143,61 @@ class ObjectHandler implements AhatHandler {
     selector.render(doc);
   }
 
-  private static void printFields(Doc doc, boolean diff, List<FieldValue> fields) {
+  /**
+   * Helper function for printing static or instance fields.
+   * @param id - id to use for the field subset selector.
+   * @param diff - whether a diff should be shown for the fields.
+   * @param current - the fields to show.
+   * @param baseline - the baseline fields to diff against if diff is true,
+   *                   ignored otherwise.
+   */
+  private static void printFields(Doc doc, Query query, String id, boolean diff,
+      List<FieldValue> current, List<FieldValue> baseline) {
+
+    if (!diff) {
+      // To avoid having to special case when diff is disabled, always diff
+      // the fields, but diff against an empty list.
+      baseline = Collections.emptyList();
+    }
+
+    List<DiffedFieldValue> fields = DiffFields.diff(current, baseline);
+    SubsetSelector<DiffedFieldValue> selector = new SubsetSelector(query, id, fields);
+
     doc.table(
         new Column("Type"),
         new Column("Name"),
         new Column("Value"),
         new Column("Δ", Column.Align.LEFT, diff));
 
-    for (FieldValue field : fields) {
-      Value current = field.getValue();
-      DocString value;
-      if (field.isPlaceHolder()) {
-        value = DocString.removed("del");
-      } else {
-        value = Summarizer.summarize(current);
-      }
+    for (DiffedFieldValue field : selector.selected()) {
+      Value previous = Value.getBaseline(field.baseline);
+      DocString was = DocString.text("was ");
+      was.append(Summarizer.summarize(previous));
+      switch (field.status) {
+        case ADDED:
+          doc.row(DocString.text(field.type),
+                  DocString.text(field.name),
+                  Summarizer.summarize(field.current),
+                  DocString.added("new"));
+          break;
 
-      DocString delta = new DocString();
-      FieldValue basefield = field.getBaseline();
-      if (basefield.isPlaceHolder()) {
-        delta.append(DocString.added("new"));
-      } else {
-        Value previous = Value.getBaseline(basefield.getValue());
-        if (!Objects.equals(current, previous)) {
-          delta.append("was ");
-          delta.append(Summarizer.summarize(previous));
-        }
+        case MATCHED:
+          doc.row(DocString.text(field.type),
+                  DocString.text(field.name),
+                  Summarizer.summarize(field.current),
+                  Objects.equals(field.current, previous) ? new DocString() : was);
+          break;
+
+        case DELETED:
+          doc.row(DocString.text(field.type),
+                  DocString.text(field.name),
+                  DocString.removed("del"),
+                  was);
+          break;
       }
-      doc.row(DocString.text(field.getType()), DocString.text(field.getName()), value, delta);
     }
     doc.end();
+    selector.render(doc);
   }
 
   private static void printClassInfo(Doc doc, Query query, AhatClassObj clsobj) {
@@ -188,13 +211,9 @@ class ObjectHandler implements AhatHandler {
 
     doc.section("Static Fields");
     AhatInstance base = clsobj.getBaseline();
-    List<FieldValue> fields = clsobj.getStaticFieldValues();
-    if (!base.isPlaceHolder()) {
-      Diff.fields(fields, base.asClassObj().getStaticFieldValues());
-    }
-    SubsetSelector<FieldValue> selector = new SubsetSelector(query, STATIC_FIELDS_ID, fields);
-    printFields(doc, clsobj != base && !base.isPlaceHolder(), selector.selected());
-    selector.render(doc);
+    printFields(doc, query, STATIC_FIELDS_ID, !base.isPlaceHolder(),
+        clsobj.getStaticFieldValues(),
+        base.isPlaceHolder() ? null : base.asClassObj().getStaticFieldValues());
   }
 
   private static void printReferences(Doc doc, Query query, AhatInstance inst) {
diff --git a/tools/ahat/src/heapdump/AhatClassInstance.java b/tools/ahat/src/heapdump/AhatClassInstance.java
index c10d604630..158de5240d 100644
--- a/tools/ahat/src/heapdump/AhatClassInstance.java
+++ b/tools/ahat/src/heapdump/AhatClassInstance.java
@@ -54,8 +54,8 @@ public class AhatClassInstance extends AhatInstance {
 
   @Override public Value getField(String fieldName) {
     for (FieldValue field : mFieldValues) {
-      if (fieldName.equals(field.getName())) {
-        return field.getValue();
+      if (fieldName.equals(field.name)) {
+        return field.value;
       }
     }
     return null;
diff --git a/tools/ahat/src/heapdump/Diff.java b/tools/ahat/src/heapdump/Diff.java
index 943e6e63f5..489f709b04 100644
--- a/tools/ahat/src/heapdump/Diff.java
+++ b/tools/ahat/src/heapdump/Diff.java
@@ -336,48 +336,4 @@ public class Diff {
       placeholder.getBaseline().getSite().getBaseline().addPlaceHolderInstance(placeholder);
     }
   }
-
-  /**
-   * Diff two lists of field values.
-   * PlaceHolder objects are added to the given lists as needed to ensure
-   * every FieldValue in A ends up with a corresponding FieldValue in B.
-   */
-  public static void fields(List<FieldValue> a, List<FieldValue> b) {
-    // Fields with the same name and type are considered matching fields.
-    // For simplicity, we assume the matching fields are in the same order in
-    // both A and B, though some fields may be added or removed in either
-    // list. If our assumption is wrong, in the worst case the quality of the
-    // field diff is poor.
-
-    for (int i = 0; i < a.size(); i++) {
-      FieldValue afield = a.get(i);
-      afield.setBaseline(null);
-
-      // Find the matching field in B, if any.
-      for (int j = i; j < b.size(); j++) {
-        FieldValue bfield = b.get(j);
-        if (afield.getName().equals(bfield.getName())
-            && afield.getType().equals(bfield.getType())) {
-          // We found the matching field in B.
-          // Assume fields i, ..., j-1 in B have no match in A.
-          for ( ; i < j; i++) {
-            a.add(i, FieldValue.newPlaceHolderFieldValue(b.get(i)));
-          }
-
-          afield.setBaseline(bfield);
-          bfield.setBaseline(afield);
-          break;
-        }
-      }
-
-      if (afield.getBaseline() == null) {
-        b.add(i, FieldValue.newPlaceHolderFieldValue(afield));
-      }
-    }
-
-    // All remaining fields in B are unmatched by any in A.
-    for (int i = a.size(); i < b.size(); i++) {
-      a.add(i, FieldValue.newPlaceHolderFieldValue(b.get(i)));
-    }
-  }
 }
diff --git a/tools/ahat/src/heapdump/DiffFields.java b/tools/ahat/src/heapdump/DiffFields.java
new file mode 100644
index 0000000000..dd73456c0f
--- /dev/null
+++ b/tools/ahat/src/heapdump/DiffFields.java
@@ -0,0 +1,85 @@
+/*
+ * Copyright (C) 2017 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.ahat.heapdump;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.List;
+
+/**
+ * This class contains a routine for diffing two collections of static or
+ * instance fields.
+ */
+public class DiffFields {
+  /**
+   * Return the result of diffing two collections of field values.
+   * The input collections 'current' and 'baseline' are not modified by this function.
+   */
+  public static List<DiffedFieldValue> diff(Collection<FieldValue> current,
+                                            Collection<FieldValue> baseline) {
+    List<FieldValue> currentSorted = new ArrayList<FieldValue>(current);
+    Collections.sort(currentSorted, FOR_DIFF);
+
+    List<FieldValue> baselineSorted = new ArrayList<FieldValue>(baseline);
+    Collections.sort(baselineSorted, FOR_DIFF);
+
+    // Merge the two lists to form the diffed list of fields.
+    List<DiffedFieldValue> diffed = new ArrayList<DiffedFieldValue>();
+    int currentPos = 0;
+    int baselinePos = 0;
+
+    while (currentPos < currentSorted.size() && baselinePos < baselineSorted.size()) {
+      FieldValue currentField = currentSorted.get(currentPos);
+      FieldValue baselineField = baselineSorted.get(baselinePos);
+      int compare = FOR_DIFF.compare(currentField, baselineField);
+      if (compare < 0) {
+        diffed.add(DiffedFieldValue.added(currentField));
+        currentPos++;
+      } else if (compare == 0) {
+        diffed.add(DiffedFieldValue.matched(currentField, baselineField));
+        currentPos++;
+        baselinePos++;
+      } else {
+        diffed.add(DiffedFieldValue.deleted(baselineField));
+        baselinePos++;
+      }
+    }
+
+    while (currentPos < currentSorted.size()) {
+      FieldValue currentField = currentSorted.get(currentPos);
+      diffed.add(DiffedFieldValue.added(currentField));
+      currentPos++;
+    }
+
+    while (baselinePos < baselineSorted.size()) {
+      FieldValue baselineField = baselineSorted.get(baselinePos);
+      diffed.add(DiffedFieldValue.deleted(baselineField));
+      baselinePos++;
+    }
+    return diffed;
+  }
+
+  /**
+   * Comparator used for sorting fields for the purposes of diff.
+   * Fields with the same name and type are considered comparable, so we sort
+   * by field name and type.
+   */
+  private static final Comparator<FieldValue> FOR_DIFF
+    = new Sort.WithPriority(Sort.FIELD_VALUE_BY_NAME, Sort.FIELD_VALUE_BY_TYPE);
+}
diff --git a/tools/ahat/src/heapdump/DiffedFieldValue.java b/tools/ahat/src/heapdump/DiffedFieldValue.java
new file mode 100644
index 0000000000..e2dcf3e8f0
--- /dev/null
+++ b/tools/ahat/src/heapdump/DiffedFieldValue.java
@@ -0,0 +1,101 @@
+/*
+ * Copyright (C) 2017 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.ahat.heapdump;
+
+import java.util.Objects;
+
+/** DiffedFieldValue is used by the DiffedField class to return the result of
+ * diffing two collections of fields.
+ */
+public class DiffedFieldValue {
+  public final String name;
+  public final String type;
+  public final Value current;
+  public final Value baseline;
+
+  public final Status status;
+
+  public static enum Status {
+    ADDED,      // The current field has no matching baseline value.
+    MATCHED,    // The current field has a matching baseline value.
+    DELETED     // The baseline field has no matching current value.
+  };
+
+  /**
+   * Return a DiffedFieldValue where there is both a current and baseline.
+   */
+  public static DiffedFieldValue matched(FieldValue current, FieldValue baseline) {
+    return new DiffedFieldValue(current.name,
+                                current.type,
+                                current.value,
+                                baseline.value,
+                                Status.MATCHED);
+  }
+
+  /**
+   * Return a DiffedFieldValue where there is no baseline.
+   */
+  public static DiffedFieldValue added(FieldValue current) {
+    return new DiffedFieldValue(current.name, current.type, current.value, null, Status.ADDED);
+  }
+
+  /**
+   * Return a DiffedFieldValue where there is no current.
+   */
+  public static DiffedFieldValue deleted(FieldValue baseline) {
+    return new DiffedFieldValue(baseline.name, baseline.type, null, baseline.value, Status.DELETED);
+  }
+
+  private DiffedFieldValue(String name, String type, Value current, Value baseline, Status status) {
+    this.name = name;
+    this.type = type;
+    this.current = current;
+    this.baseline = baseline;
+    this.status = status;
+  }
+
+  @Override
+  public boolean equals(Object otherObject) {
+    if (otherObject instanceof DiffedFieldValue) {
+      DiffedFieldValue other = (DiffedFieldValue)otherObject;
+      return name.equals(other.name)
+        && type.equals(other.type)
+        && Objects.equals(current, other.current)
+        && Objects.equals(baseline, other.baseline)
+        && Objects.equals(status, other.status);
+    }
+    return false;
+  }
+
+  @Override
+  public String toString() {
+    switch (status) {
+      case ADDED:
+        return "(" + name + " " + type + " +" + current + ")";
+
+      case MATCHED:
+        return "(" + name + " " + type + " " + current + " " + baseline + ")";
+
+      case DELETED:
+        return "(" + name + " " + type + " -" + baseline + ")";
+
+      default:
+        // There are no other members.
+        throw new AssertionError("unsupported enum member");
+    }
+  }
+}
diff --git a/tools/ahat/src/heapdump/FieldValue.java b/tools/ahat/src/heapdump/FieldValue.java
index 3f65cd3030..6d725953b3 100644
--- a/tools/ahat/src/heapdump/FieldValue.java
+++ b/tools/ahat/src/heapdump/FieldValue.java
@@ -16,68 +16,14 @@
 
 package com.android.ahat.heapdump;
 
-public class FieldValue implements Diffable<FieldValue> {
-  private final String mName;
-  private final String mType;
-  private final Value mValue;
-  private FieldValue mBaseline;
-  private final boolean mIsPlaceHolder;
+public class FieldValue {
+  public final String name;
+  public final String type;
+  public final Value value;
 
   public FieldValue(String name, String type, Value value) {
-    mName = name;
-    mType = type;
-    mValue = value;
-    mBaseline = this;
-    mIsPlaceHolder = false;
-  }
-
-  /**
-   * Construct a place holder FieldValue
-   */
-  private FieldValue(FieldValue baseline) {
-    mName = baseline.mName;
-    mType = baseline.mType;
-    mValue = Value.getBaseline(baseline.mValue);
-    mBaseline = baseline;
-    mIsPlaceHolder = true;
-  }
-
-  static FieldValue newPlaceHolderFieldValue(FieldValue baseline) {
-    FieldValue field = new FieldValue(baseline);
-    baseline.setBaseline(field);
-    return field;
-  }
-
-  /**
-   * Returns the name of the field.
-   */
-  public String getName() {
-    return mName;
-  }
-
-  /**
-   * Returns a description of the type of the field.
-   */
-  public String getType() {
-    return mType;
-  }
-
-  /**
-   * Returns the value of this field.
-   */
-  public Value getValue() {
-    return mValue;
-  }
-
-  public void setBaseline(FieldValue baseline) {
-    mBaseline = baseline;
-  }
-
-  @Override public FieldValue getBaseline() {
-    return mBaseline;
-  }
-
-  @Override public boolean isPlaceHolder() {
-    return mIsPlaceHolder;
+    this.name = name;
+    this.type = type;
+    this.value = value;
   }
 }
diff --git a/tools/ahat/src/heapdump/Sort.java b/tools/ahat/src/heapdump/Sort.java
index 0745803817..efe0d6b59b 100644
--- a/tools/ahat/src/heapdump/Sort.java
+++ b/tools/ahat/src/heapdump/Sort.java
@@ -200,5 +200,27 @@ public class Sort {
       return aName.compareTo(bName);
     }
   };
+
+  /**
+   * Compare FieldValue by field name.
+   */
+  public static final Comparator<FieldValue> FIELD_VALUE_BY_NAME
+    = new Comparator<FieldValue>() {
+    @Override
+    public int compare(FieldValue a, FieldValue b) {
+      return a.name.compareTo(b.name);
+    }
+  };
+
+  /**
+   * Compare FieldValue by type name.
+   */
+  public static final Comparator<FieldValue> FIELD_VALUE_BY_TYPE
+    = new Comparator<FieldValue>() {
+    @Override
+    public int compare(FieldValue a, FieldValue b) {
+      return a.type.compareTo(b.type);
+    }
+  };
 }
 
diff --git a/tools/ahat/src/heapdump/Value.java b/tools/ahat/src/heapdump/Value.java
index 6b2d38f7b1..c1f30228e0 100644
--- a/tools/ahat/src/heapdump/Value.java
+++ b/tools/ahat/src/heapdump/Value.java
@@ -28,7 +28,7 @@ public class Value {
    * The Object must either be a boxed Java primitive type or a subclass of
    * AhatInstance. The object must not be null.
    */
-  Value(Object object) {
+  public Value(Object object) {
     // TODO: Check that the Object is either an AhatSnapshot or boxed Java
     // primitive type?
     assert object != null;
diff --git a/tools/ahat/test/DiffFieldsTest.java b/tools/ahat/test/DiffFieldsTest.java
new file mode 100644
index 0000000000..6abdd47ef6
--- /dev/null
+++ b/tools/ahat/test/DiffFieldsTest.java
@@ -0,0 +1,181 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.ahat;
+
+import com.android.ahat.heapdump.DiffFields;
+import com.android.ahat.heapdump.DiffedFieldValue;
+import com.android.ahat.heapdump.FieldValue;
+import com.android.ahat.heapdump.Value;
+import java.util.ArrayList;
+import java.util.List;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNull;
+
+public class DiffFieldsTest {
+  @Test
+  public void normalMatchedDiffedFieldValues() {
+    FieldValue normal1 = new FieldValue("name", "type", new Value(1));
+    FieldValue normal2 = new FieldValue("name", "type", new Value(2));
+
+    DiffedFieldValue x = DiffedFieldValue.matched(normal1, normal2);
+    assertEquals("name", x.name);
+    assertEquals("type", x.type);
+    assertEquals(new Value(1), x.current);
+    assertEquals(new Value(2), x.baseline);
+    assertEquals(DiffedFieldValue.Status.MATCHED, x.status);
+  }
+
+  @Test
+  public void nulledMatchedDiffedFieldValues() {
+    FieldValue normal = new FieldValue("name", "type", new Value(1));
+    FieldValue nulled = new FieldValue("name", "type", null);
+
+    DiffedFieldValue x = DiffedFieldValue.matched(normal, nulled);
+    assertEquals("name", x.name);
+    assertEquals("type", x.type);
+    assertEquals(new Value(1), x.current);
+    assertNull(x.baseline);
+    assertEquals(DiffedFieldValue.Status.MATCHED, x.status);
+
+    DiffedFieldValue y = DiffedFieldValue.matched(nulled, normal);
+    assertEquals("name", y.name);
+    assertEquals("type", y.type);
+    assertNull(y.current);
+    assertEquals(new Value(1), y.baseline);
+    assertEquals(DiffedFieldValue.Status.MATCHED, y.status);
+  }
+
+  @Test
+  public void normalAddedDiffedFieldValues() {
+    FieldValue normal = new FieldValue("name", "type", new Value(1));
+
+    DiffedFieldValue x = DiffedFieldValue.added(normal);
+    assertEquals("name", x.name);
+    assertEquals("type", x.type);
+    assertEquals(new Value(1), x.current);
+    assertEquals(DiffedFieldValue.Status.ADDED, x.status);
+  }
+
+  @Test
+  public void nulledAddedDiffedFieldValues() {
+    FieldValue nulled = new FieldValue("name", "type", null);
+
+    DiffedFieldValue x = DiffedFieldValue.added(nulled);
+    assertEquals("name", x.name);
+    assertEquals("type", x.type);
+    assertNull(x.current);
+    assertEquals(DiffedFieldValue.Status.ADDED, x.status);
+  }
+
+  @Test
+  public void normalDeletedDiffedFieldValues() {
+    FieldValue normal = new FieldValue("name", "type", new Value(1));
+
+    DiffedFieldValue x = DiffedFieldValue.deleted(normal);
+    assertEquals("name", x.name);
+    assertEquals("type", x.type);
+    assertEquals(new Value(1), x.baseline);
+    assertEquals(DiffedFieldValue.Status.DELETED, x.status);
+  }
+
+  @Test
+  public void nulledDeletedDiffedFieldValues() {
+    FieldValue nulled = new FieldValue("name", "type", null);
+
+    DiffedFieldValue x = DiffedFieldValue.deleted(nulled);
+    assertEquals("name", x.name);
+    assertEquals("type", x.type);
+    assertNull(x.baseline);
+    assertEquals(DiffedFieldValue.Status.DELETED, x.status);
+  }
+
+  @Test
+  public void basicDiff() {
+    List<FieldValue> a = new ArrayList<FieldValue>();
+    a.add(new FieldValue("n0", "t0", null));
+    a.add(new FieldValue("n2", "t2", null));
+    a.add(new FieldValue("n3", "t3", null));
+    a.add(new FieldValue("n4", "t4", null));
+    a.add(new FieldValue("n5", "t5", null));
+    a.add(new FieldValue("n6", "t6", null));
+
+    List<FieldValue> b = new ArrayList<FieldValue>();
+    b.add(new FieldValue("n0", "t0", null));
+    b.add(new FieldValue("n1", "t1", null));
+    b.add(new FieldValue("n2", "t2", null));
+    b.add(new FieldValue("n3", "t3", null));
+    b.add(new FieldValue("n5", "t5", null));
+    b.add(new FieldValue("n6", "t6", null));
+    b.add(new FieldValue("n7", "t7", null));
+
+    // Note: The expected result makes assumptions about the implementation of
+    // field diff to match the order of the returned fields. If the
+    // implementation changes, this test may need to be generalized to accept
+    // the new implementation.
+    List<DiffedFieldValue> expected = new ArrayList<DiffedFieldValue>();
+    expected.add(DiffedFieldValue.matched(a.get(0), b.get(0)));
+    expected.add(DiffedFieldValue.deleted(b.get(1)));
+    expected.add(DiffedFieldValue.matched(a.get(1), b.get(2)));
+    expected.add(DiffedFieldValue.matched(a.get(2), b.get(3)));
+    expected.add(DiffedFieldValue.added(a.get(3)));
+    expected.add(DiffedFieldValue.matched(a.get(4), b.get(4)));
+    expected.add(DiffedFieldValue.matched(a.get(5), b.get(5)));
+    expected.add(DiffedFieldValue.deleted(b.get(6)));
+
+    List<DiffedFieldValue> diffed = DiffFields.diff(a, b);
+    assertEquals(expected, diffed);
+  }
+
+  @Test
+  public void reorderedDiff() {
+    List<FieldValue> a = new ArrayList<FieldValue>();
+    a.add(new FieldValue("n0", "t0", null));
+    a.add(new FieldValue("n1", "t1", null));
+    a.add(new FieldValue("n2", "t2", null));
+    a.add(new FieldValue("n3", "t3", null));
+    a.add(new FieldValue("n4", "t4", null));
+    a.add(new FieldValue("n5", "t5", null));
+    a.add(new FieldValue("n6", "t6", null));
+
+    List<FieldValue> b = new ArrayList<FieldValue>();
+    b.add(new FieldValue("n4", "t4", null));
+    b.add(new FieldValue("n1", "t1", null));
+    b.add(new FieldValue("n3", "t3", null));
+    b.add(new FieldValue("n0", "t0", null));
+    b.add(new FieldValue("n5", "t5", null));
+    b.add(new FieldValue("n2", "t2", null));
+    b.add(new FieldValue("n6", "t6", null));
+
+    // Note: The expected result makes assumptions about the implementation of
+    // field diff to match the order of the returned fields. If the
+    // implementation changes, this test may need to be generalized to accept
+    // the new implementation.
+    List<DiffedFieldValue> expected = new ArrayList<DiffedFieldValue>();
+    expected.add(DiffedFieldValue.matched(a.get(0), b.get(3)));
+    expected.add(DiffedFieldValue.matched(a.get(1), b.get(1)));
+    expected.add(DiffedFieldValue.matched(a.get(2), b.get(5)));
+    expected.add(DiffedFieldValue.matched(a.get(3), b.get(2)));
+    expected.add(DiffedFieldValue.matched(a.get(4), b.get(0)));
+    expected.add(DiffedFieldValue.matched(a.get(5), b.get(4)));
+    expected.add(DiffedFieldValue.matched(a.get(6), b.get(6)));
+
+    List<DiffedFieldValue> diffed = DiffFields.diff(a, b);
+    assertEquals(expected, diffed);
+  }
+}
diff --git a/tools/ahat/test/DiffTest.java b/tools/ahat/test/DiffTest.java
index 52b6b7b3ae..d0349fd178 100644
--- a/tools/ahat/test/DiffTest.java
+++ b/tools/ahat/test/DiffTest.java
@@ -20,7 +20,6 @@ import com.android.ahat.heapdump.AhatHeap;
 import com.android.ahat.heapdump.AhatInstance;
 import com.android.ahat.heapdump.AhatSnapshot;
 import com.android.ahat.heapdump.Diff;
-import com.android.ahat.heapdump.FieldValue;
 import com.android.tools.perflib.heap.hprof.HprofClassDump;
 import com.android.tools.perflib.heap.hprof.HprofConstant;
 import com.android.tools.perflib.heap.hprof.HprofDumpRecord;
@@ -129,35 +128,4 @@ public class DiffTest {
     // Diffing should not crash.
     Diff.snapshots(snapshot, snapshot);
   }
-
-  @Test
-  public void diffFields() {
-    List<FieldValue> a = new ArrayList<FieldValue>();
-    a.add(new FieldValue("n0", "t0", null));
-    a.add(new FieldValue("n2", "t2", null));
-    a.add(new FieldValue("n3", "t3", null));
-    a.add(new FieldValue("n4", "t4", null));
-    a.add(new FieldValue("n5", "t5", null));
-    a.add(new FieldValue("n6", "t6", null));
-
-    List<FieldValue> b = new ArrayList<FieldValue>();
-    b.add(new FieldValue("n0", "t0", null));
-    b.add(new FieldValue("n1", "t1", null));
-    b.add(new FieldValue("n2", "t2", null));
-    b.add(new FieldValue("n3", "t3", null));
-    b.add(new FieldValue("n5", "t5", null));
-    b.add(new FieldValue("n6", "t6", null));
-    b.add(new FieldValue("n7", "t7", null));
-
-    Diff.fields(a, b);
-    assertEquals(8, a.size());
-    assertEquals(8, b.size());
-    for (int i = 0; i < 8; i++) {
-      assertEquals(a.get(i), b.get(i).getBaseline());
-      assertEquals(b.get(i), a.get(i).getBaseline());
-    }
-    assertTrue(a.get(1).isPlaceHolder());
-    assertTrue(a.get(7).isPlaceHolder());
-    assertTrue(b.get(4).isPlaceHolder());
-  }
 }
diff --git a/tools/ahat/test/TestDump.java b/tools/ahat/test/TestDump.java
index ceb7346bc4..3dce2dccfe 100644
--- a/tools/ahat/test/TestDump.java
+++ b/tools/ahat/test/TestDump.java
@@ -118,9 +118,9 @@ public class TestDump {
   private Value getDumpedValue(String name, AhatSnapshot snapshot) {
     AhatClassObj main = snapshot.findClass("Main");
     AhatInstance stuff = null;
-    for (FieldValue fields : main.getStaticFieldValues()) {
-      if ("stuff".equals(fields.getName())) {
-        stuff = fields.getValue().asAhatInstance();
+    for (FieldValue field : main.getStaticFieldValues()) {
+      if ("stuff".equals(field.name)) {
+        stuff = field.value.asAhatInstance();
       }
     }
     return stuff.getField(name);
diff --git a/tools/ahat/test/Tests.java b/tools/ahat/test/Tests.java
index c7e9b1811b..a95788e3bd 100644
--- a/tools/ahat/test/Tests.java
+++ b/tools/ahat/test/Tests.java
@@ -22,6 +22,7 @@ public class Tests {
   public static void main(String[] args) {
     if (args.length == 0) {
       args = new String[]{
+        "com.android.ahat.DiffFieldsTest",
         "com.android.ahat.DiffTest",
         "com.android.ahat.InstanceTest",
         "com.android.ahat.NativeAllocationTest",