1 /*
2  * Copyright (C) 2017 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package com.android.ahat.heapdump;
18 
19 import java.util.ArrayList;
20 import java.util.Collections;
21 import java.util.Comparator;
22 import java.util.List;
23 
24 /**
25  * Provides a routine for diffing two collections of static or instance
26  * fields.
27  */
28 public class DiffFields {
29   /**
30    * Returns the result of diffing two collections of field values.
31    *
32    * @param current a list of fields in the current heap dump
33    * @param baseline a list of fields in the baseline heap dump
34    * @return list of diffed fields
35    */
diff(Iterable<FieldValue> current, Iterable<FieldValue> baseline)36   public static List<DiffedFieldValue> diff(Iterable<FieldValue> current,
37                                             Iterable<FieldValue> baseline) {
38     List<FieldValue> currentSorted = new ArrayList<FieldValue>();
39     for (FieldValue field : current) {
40       currentSorted.add(field);
41     }
42     Collections.sort(currentSorted, FOR_DIFF);
43 
44     List<FieldValue> baselineSorted = new ArrayList<FieldValue>();
45     for (FieldValue field : baseline) {
46       baselineSorted.add(field);
47     }
48     Collections.sort(baselineSorted, FOR_DIFF);
49 
50     // Merge the two lists to form the diffed list of fields.
51     List<DiffedFieldValue> diffed = new ArrayList<DiffedFieldValue>();
52     int currentPos = 0;
53     int baselinePos = 0;
54 
55     while (currentPos < currentSorted.size() && baselinePos < baselineSorted.size()) {
56       FieldValue currentField = currentSorted.get(currentPos);
57       FieldValue baselineField = baselineSorted.get(baselinePos);
58       int compare = FOR_DIFF.compare(currentField, baselineField);
59       if (compare < 0) {
60         diffed.add(DiffedFieldValue.added(currentField));
61         currentPos++;
62       } else if (compare == 0) {
63         diffed.add(DiffedFieldValue.matched(currentField, baselineField));
64         currentPos++;
65         baselinePos++;
66       } else {
67         diffed.add(DiffedFieldValue.deleted(baselineField));
68         baselinePos++;
69       }
70     }
71 
72     while (currentPos < currentSorted.size()) {
73       FieldValue currentField = currentSorted.get(currentPos);
74       diffed.add(DiffedFieldValue.added(currentField));
75       currentPos++;
76     }
77 
78     while (baselinePos < baselineSorted.size()) {
79       FieldValue baselineField = baselineSorted.get(baselinePos);
80       diffed.add(DiffedFieldValue.deleted(baselineField));
81       baselinePos++;
82     }
83     return diffed;
84   }
85 
86   /**
87    * Comparator used for sorting fields for the purposes of diff.
88    * Fields with the same name and type are considered comparable, so we sort
89    * by field name and type.
90    */
91   private static final Comparator<FieldValue> FOR_DIFF
92     = Sort.withPriority(Sort.FIELD_VALUE_BY_NAME, Sort.FIELD_VALUE_BY_TYPE);
93 }
94