content: /*
   * 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.heapdump;
  
  import java.util.ArrayDeque;
  import java.util.ArrayList;
  import java.util.Collections;
  import java.util.Deque;
  import java.util.HashMap;
  import java.util.List;
  import java.util.Map;
  import java.util.Objects;
  
  public class Diff {
    /**
     * Perform a diff between two heap lists.
     *
     * Heaps are diffed based on heap name. PlaceHolder heaps will be added to
     * the given lists as necessary so that every heap in A has a corresponding
     * heap in B and vice-versa.
     */
    private static void heaps(List<AhatHeap> a, List<AhatHeap> b) {
      int asize = a.size();
      int bsize = b.size();
      for (int i = 0; i < bsize; i++) {
        // Set the B heap's baseline as null to mark that we have not yet
        // matched it with an A heap.
        b.get(i).setBaseline(null);
      }
  
      for (int i = 0; i < asize; i++) {
        AhatHeap aheap = a.get(i);
        aheap.setBaseline(null);
        for (int j = 0; j < bsize; j++) {
          AhatHeap bheap = b.get(j);
          if (bheap.getBaseline() == null && aheap.getName().equals(bheap.getName())) {
            // We found a match between aheap and bheap.
            aheap.setBaseline(bheap);
            bheap.setBaseline(aheap);
            break;
          }
        }
  
        if (aheap.getBaseline() == null) {
          // We did not find any match for aheap in snapshot B.
          // Create a placeholder heap in snapshot B to use as the baseline.
          b.add(AhatHeap.newPlaceHolderHeap(aheap.getName(), aheap));
        }
      }
  
      // Make placeholder heaps in snapshot A for any unmatched heaps in
      // snapshot B.
      for (int i = 0; i < bsize; i++) {
        AhatHeap bheap = b.get(i);
        if (bheap.getBaseline() == null) {
          a.add(AhatHeap.newPlaceHolderHeap(bheap.getName(), bheap));
        }
      }
    }
  
    /**
     * Key represents an equivalence class of AhatInstances that are allowed to
     * be considered for correspondence between two different snapshots.
     */
    private static class Key {
      // Corresponding objects must belong to classes of the same name.
      private final String mClass;
  
      // Corresponding objects must belong to heaps of the same name.
      private final String mHeapName;
  
      // Corresponding string objects must have the same value.
      // mStringValue is set to the empty string for non-string objects.
      private final String mStringValue;
  
      // Corresponding class objects must have the same class name.
      // mClassName is set to the empty string for non-class objects.
      private final String mClassName;
  
      // Corresponding array objects must have the same length.
      // mArrayLength is set to 0 for non-array objects.
      private final int mArrayLength;
  
  
      private Key(AhatInstance inst) {
        mClass = inst.getClassName();
        mHeapName = inst.getHeap().getName();
        mClassName = inst.isClassObj() ? inst.asClassObj().getName() : "";
        String string = inst.asString();
        mStringValue = string == null ? "" : string;
        AhatArrayInstance array = inst.asArrayInstance();
        mArrayLength = array == null ? 0 : array.getLength();
      }
  
      /**
       * Return the key for the given instance.
       */
      public static Key keyFor(AhatInstance inst) {
        return new Key(inst);
      }
  
      @Override
      public boolean equals(Object other) {
        if (!(other instanceof Key)) {
          return false;
        }
        Key o = (Key)other;
        return mClass.equals(o.mClass)
            && mHeapName.equals(o.mHeapName)
            && mStringValue.equals(o.mStringValue)
            && mClassName.equals(o.mClassName)
            && mArrayLength == o.mArrayLength;
      }
  
      @Override
      public int hashCode() {
        return Objects.hash(mClass, mHeapName, mStringValue, mClassName, mArrayLength);
      }
    }
  
    private static class InstanceListPair {
      public final List<AhatInstance> a;
      public final List<AhatInstance> b;
  
      public InstanceListPair() {
        this.a = new ArrayList<AhatInstance>();
        this.b = new ArrayList<AhatInstance>();
      }
  
      public InstanceListPair(List<AhatInstance> a, List<AhatInstance> b) {
        this.a = a;
        this.b = b;
      }
    }
  
    /**
     * Recursively create place holder instances for the given instance and
     * every instance dominated by that instance.
     * Returns the place holder instance created for the given instance.
     * Adds all allocated placeholders to the given placeholders list.
     */
    private static AhatInstance createPlaceHolders(AhatInstance inst,
        List<AhatInstance> placeholders) {
      // Don't actually use recursion, because we could easily smash the stack.
      // Instead we iterate.
      AhatInstance result = inst.newPlaceHolderInstance();
      placeholders.add(result);
      Deque<AhatInstance> deque = new ArrayDeque<AhatInstance>();
      deque.push(inst);
      while (!deque.isEmpty()) {
        inst = deque.pop();
  
        for (AhatInstance child : inst.getDominated()) {
          placeholders.add(child.newPlaceHolderInstance());
          deque.push(child);
        }
      }
      return result;
    }
  
    /**
     * Recursively diff two dominator trees of instances.
     * PlaceHolder objects are appended to the lists as needed to ensure every
     * object has a corresponding baseline in the other list. All PlaceHolder
     * objects are also appended to the given placeholders list, so their Site
     * info can be updated later on.
     */
    private static void instances(List<AhatInstance> a, List<AhatInstance> b,
        List<AhatInstance> placeholders) {
      // Don't actually use recursion, because we could easily smash the stack.
      // Instead we iterate.
      Deque<InstanceListPair> deque = new ArrayDeque<InstanceListPair>();
      deque.push(new InstanceListPair(a, b));
      while (!deque.isEmpty()) {
        InstanceListPair p = deque.pop();
  
        // Group instances of the same equivalence class together.
        Map<Key, InstanceListPair> byKey = new HashMap<Key, InstanceListPair>();
        for (AhatInstance inst : p.a) {
          Key key = Key.keyFor(inst);
          InstanceListPair pair = byKey.get(key);
          if (pair == null) {
            pair = new InstanceListPair();
            byKey.put(key, pair);
          }
          pair.a.add(inst);
        }
        for (AhatInstance inst : p.b) {
          Key key = Key.keyFor(inst);
          InstanceListPair pair = byKey.get(key);
          if (pair == null) {
            pair = new InstanceListPair();
            byKey.put(key, pair);
          }
          pair.b.add(inst);
        }
  
        // diff objects from the same key class.
        for (InstanceListPair pair : byKey.values()) {
          // Sort by retained size and assume the elements at the top of the lists
          // correspond to each other in that order. This could probably be
          // improved if desired, but it gives good enough results for now.
          Collections.sort(pair.a, Sort.INSTANCE_BY_TOTAL_RETAINED_SIZE);
          Collections.sort(pair.b, Sort.INSTANCE_BY_TOTAL_RETAINED_SIZE);
  
          int common = Math.min(pair.a.size(), pair.b.size());
          for (int i = 0; i < common; i++) {
            AhatInstance ainst = pair.a.get(i);
            AhatInstance binst = pair.b.get(i);
            ainst.setBaseline(binst);
            binst.setBaseline(ainst);
            deque.push(new InstanceListPair(ainst.getDominated(), binst.getDominated()));
          }
  
          // Add placeholder objects for anything leftover.
          for (int i = common; i < pair.a.size(); i++) {
            p.b.add(createPlaceHolders(pair.a.get(i), placeholders));
          }
  
          for (int i = common; i < pair.b.size(); i++) {
            p.a.add(createPlaceHolders(pair.b.get(i), placeholders));
          }
        }
      }
    }
  
    /**
     * Sets the baseline for root and all its descendants to baseline.
     */
    private static void setSitesBaseline(Site root, Site baseline) {
      root.setBaseline(baseline);
      for (Site child : root.getChildren()) {
        setSitesBaseline(child, baseline);
      }
    }
  
    /**
     * Recursively diff the two sites, setting them and their descendants as
     * baselines for each other as appropriate.
     *
     * This requires that instances have already been diffed. In particular, we
     * require all AhatClassObjs in one snapshot have corresponding (possibly
     * place-holder) AhatClassObjs in the other snapshot.
     */
    private static void sites(Site a, Site b) {
      // Set the sites as baselines of each other.
      a.setBaseline(b);
      b.setBaseline(a);
  
      // Set the site's ObjectsInfos as baselines of each other. This implicitly
      // adds new empty ObjectsInfo as needed.
      for (Site.ObjectsInfo ainfo : a.getObjectsInfos()) {
        AhatClassObj baseClassObj = null;
        if (ainfo.classObj != null) {
          baseClassObj = (AhatClassObj) ainfo.classObj.getBaseline();
        }
        ainfo.setBaseline(b.getObjectsInfo(ainfo.heap.getBaseline(), baseClassObj));
      }
      for (Site.ObjectsInfo binfo : b.getObjectsInfos()) {
        AhatClassObj baseClassObj = null;
        if (binfo.classObj != null) {
          baseClassObj = (AhatClassObj) binfo.classObj.getBaseline();
        }
        binfo.setBaseline(a.getObjectsInfo(binfo.heap.getBaseline(), baseClassObj));
      }
  
      // Set B children's baselines as null to mark that we have not yet matched
      // them with A children.
      for (Site bchild : b.getChildren()) {
        bchild.setBaseline(null);
      }
  
      for (Site achild : a.getChildren()) {
        achild.setBaseline(null);
        for (Site bchild : b.getChildren()) {
          if (achild.getLineNumber() == bchild.getLineNumber()
              && achild.getMethodName().equals(bchild.getMethodName())
              && achild.getSignature().equals(bchild.getSignature())
              && achild.getFilename().equals(bchild.getFilename())) {
            // We found a match between achild and bchild.
            sites(achild, bchild);
            break;
          }
        }
  
        if (achild.getBaseline() == null) {
          // We did not find any match for achild in site B.
          // Use B for the baseline of achild and its descendants.
          setSitesBaseline(achild, b);
        }
      }
  
      for (Site bchild : b.getChildren()) {
        if (bchild.getBaseline() == null) {
          setSitesBaseline(bchild, a);
        }
      }
    }
  
    /**
     * Perform a diff of the two snapshots, setting each as the baseline for the
     * other.
     */
    public static void snapshots(AhatSnapshot a, AhatSnapshot b) {
      a.setBaseline(b);
      b.setBaseline(a);
  
      // Diff the heaps of each snapshot.
      heaps(a.getHeaps(), b.getHeaps());
  
      // Diff the instances of each snapshot.
      List<AhatInstance> placeholders = new ArrayList<AhatInstance>();
      instances(a.getRooted(), b.getRooted(), placeholders);
  
      // Diff the sites of each snapshot.
      // This requires the instances have already been diffed.
      sites(a.getRootSite(), b.getRootSite());
  
      // Add placeholders to their corresponding sites.
      // This requires the sites have already been diffed.
      for (AhatInstance placeholder : placeholders) {
        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)));
      }
    }
  }
  