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
17package libcore;
18
19import java.io.*;
20import java.nio.file.Path;
21import java.util.ArrayList;
22import java.util.Arrays;
23import java.util.Collections;
24import java.util.Comparator;
25import java.util.LinkedHashMap;
26import java.util.List;
27import java.util.Locale;
28import java.util.Map;
29import java.util.Objects;
30import java.util.regex.Matcher;
31import java.util.regex.Pattern;
32
33/**
34 * Helps compare openjdk_java_files contents against upstream file contents.
35 *
36 * Outputs a tab-separated table comparing each openjdk_java_files entry
37 * against OpenJDK upstreams. This can help verify updates to later upstreams
38 * or focus attention towards files that may have been missed in a previous
39 * update (http://b/36461944) or are otherwise surprising (http://b/36429512).
40 *
41 * - Identifies each file as identical to, different from or missing from
42 * each upstream; diffs are not produced.
43 * - Optionally, copies all openjdk_java_files from the default upstream
44 * (eg. OpenJDK8u121-b13) to a new directory, for easy directory comparison
45 * using e.g. kdiff3, which allows inspecting detailed diffs.
46 * - The ANDROID_BUILD_TOP environment variable must be set to point to the
47 * AOSP root directory (parent of libcore).
48 *
49 * To check out upstreams OpenJDK 7u40, 8u60, 8u121-b13, and 9+181, run:
50 *
51 *  mkdir ~/openjdk
52 *  cd ~/openjdk
53 *  export OPENJDK_HOME=$PWD
54 *  hg clone http://hg.openjdk.java.net/jdk7u/jdk7u40/ 7u40
55 *  (cd !$ ; sh get_source.sh)
56 *  hg clone http://hg.openjdk.java.net/jdk8u/jdk8u 8u121-b13
57 *  (cd !$ ; hg update -r jdk8u121-b13 && sh get_source.sh && sh common/bin/hgforest.sh update -r jdk8u121-b13)
58 *  hg clone http://hg.openjdk.java.net/jdk8u/jdk8u60/ 8u60
59 *  (cd !$ ; sh get_source.sh)
60 *  hg clone http://hg.openjdk.java.net/jdk9/jdk9/ 9+181
61 *  (cd !$ ; hg update -r jdk-9+181 && sh get_source.sh && sh common/bin/hgforest.sh update -r jdk-9+181)
62 *
63 *  To get the 9b113+ upstream, follow the instructions from the commit
64 *  message of AOSP libcore commit 29957558cf0db700bfaae360a80c42dc3871d0e5
65 *  at https://android-review.googlesource.com/c/304056/
66 */
67public class CompareUpstreams {
68
69    private final StandardRepositories standardRepositories;
70
71    public CompareUpstreams(StandardRepositories standardRepositories) {
72        this.standardRepositories = Objects.requireNonNull(standardRepositories);
73    }
74
75    private static Map<String, Integer> androidChangedComments(List<String> lines) {
76        List<String> problems = new ArrayList<>();
77        Map<String, Integer> result = new LinkedHashMap<>();
78        Pattern pattern = Pattern.compile(
79                "// (BEGIN |END |)Android-((?:changed|added|removed|note)(?:: )?.*)$");
80        for (String line : lines) {
81            Matcher matcher = pattern.matcher(line);
82            if (matcher.find()) {
83                String type = matcher.group(1);
84                if (type.equals("END")) {
85                    continue;
86                }
87                String match = matcher.group(2);
88                if (match.isEmpty()) {
89                    match = "[empty comment]";
90                }
91                Integer oldCount = result.get(match);
92                if (oldCount == null) {
93                    oldCount = 0;
94                }
95                result.put(match, oldCount + 1);
96            } else if (line.contains("Android-")) {
97                problems.add(line);
98            }
99        }
100        if (!problems.isEmpty()) {
101            throw new IllegalArgumentException(problems.toString());
102        }
103        return result;
104    }
105
106    private static String androidChangedCommentsSummary(List<String> lines) {
107        Map<String, Integer> map = androidChangedComments(lines);
108        List<String> comments = new ArrayList<>(map.keySet());
109        Collections.sort(comments, Comparator.comparing(map::get).reversed());
110        List<String> result = new ArrayList<>();
111        for (String comment : comments) {
112            int count = map.get(comment);
113            if (count == 1) {
114                result.add(comment);
115            } else {
116                result.add(comment + " (x" + count + ")");
117            }
118        }
119        return escapeTsv(String.join("\n", result));
120    }
121
122    /**
123     * Computes the edit distance of two lists, i.e. the smallest number of list items to delete,
124     * insert or replace that would transform the content of one list into the other.
125     */
126    private <T> int editDistance(List<T> a, List<T> b) {
127        int numB = b.size();
128        int[] prevCost = new int[numB + 1];
129        for (int i = 0; i <= numB; i++) {
130            prevCost[i] = i;
131        }
132        int[] curCost = new int[numB + 1];
133        for (int endA = 1; endA <= a.size(); endA++) {
134            // For each valid index i, prevCost[i] is the edit distance between
135            // a.subList(0, endA-1) and b.sublist(0, i).
136            // We now calculate curCost[end_b] as the edit distance between
137            // a.subList(0, endA) and b.subList(0, endB)
138            curCost[0] = endA;
139            for (int endB = 1; endB <= numB; endB++) {
140                boolean endsMatch = a.get(endA - 1).equals(b.get(endB - 1));
141                curCost[endB] = min(
142                        curCost[endB - 1] + 1, // append item from b
143                        prevCost[endB] + 1, // append item from a
144                        prevCost[endB - 1] + (endsMatch ? 0 : 1)); // match or replace item
145            }
146            int[] tmp = curCost;
147            curCost = prevCost;
148            prevCost = tmp;
149        }
150        return prevCost[numB];
151    }
152
153    private static int min(int a, int b, int c) {
154        if (a < b) {
155            return a < c ? a : c;
156        } else {
157            return b < c ? b : c;
158        }
159    }
160
161    private static String escapeTsv(String value) {
162        if (value.contains("\t")) {
163            throw new IllegalArgumentException(value); // tsv doesn't support escaping tabs
164        }
165        return "\"" + value.replace("\"", "\"\"") + "\"";
166    }
167
168    private static void printTsv(PrintStream out, List<String> values) {
169        out.println(String.join("\t", values));
170    }
171
172    /**
173     * Prints tab-separated values comparing ojluni files vs. each
174     * upstream, for each of the rel_paths, suitable for human
175     * analysis in a spreadsheet.
176     * This includes whether the corresponding upstream file is
177     * missing, identical, or by how many lines it differs, and
178     * a guess as to the correct upstream based on minimal line
179     * difference (ties broken in favor of upstreams that occur
180     * earlier in the list).
181     */
182    private void run(PrintStream out, List<Path> relPaths) throws IOException {
183        // upstreams are in decreasing order of preference
184        List<String> headers = new ArrayList<>();
185        headers.addAll(Arrays.asList(
186                "rel_path", "expected_upstream", "guessed_upstream", "changes", "vs. expected"));
187        for (Repository upstream : standardRepositories.historicUpstreams()) {
188            headers.add(upstream.name());
189        }
190        headers.add("diff");
191        printTsv(out, headers);
192        for (Path relPath : relPaths) {
193            Repository expectedUpstream = standardRepositories.currentUpstream(relPath);
194            out.print(relPath + "\t");
195            Path ojluniFile = standardRepositories.ojluni().absolutePath(relPath);
196            List<String> linesB = Util.readLines(ojluniFile);
197            int bestDistance = Integer.MAX_VALUE;
198            Repository guessedUpstream = null;
199            List<Repository> upstreams = new ArrayList<>();
200            upstreams.add(expectedUpstream);
201            upstreams.addAll(standardRepositories.historicUpstreams());
202            List<String> comparisons = new ArrayList<>(upstreams.size());
203            for (Repository upstream : upstreams) {
204                final String comparison;
205                Path upstreamFile = upstream.absolutePath(relPath);
206                if (upstreamFile == null) {
207                    comparison = "missing";
208                } else {
209                    List<String> linesA = Util.readLines(upstreamFile);
210                    int distance = editDistance(linesA, linesB);
211                    if (distance == 0) {
212                        comparison = "identical";
213                    } else {
214                        double percentDifferent = 100.0 * distance / Math
215                                .max(linesA.size(), linesB.size());
216                        comparison = String
217                                .format(Locale.US, "%.1f%% different (%d lines)", percentDifferent,
218                                        distance);
219                    }
220                    if (distance < bestDistance) {
221                        bestDistance = distance;
222                        guessedUpstream = upstream;
223                    }
224                }
225                comparisons.add(comparison);
226            }
227            String changedCommentsSummary = androidChangedCommentsSummary(linesB);
228
229            String diffCommand = "";
230            if (!comparisons.get(0).equals("identical")) {
231                Path expectedUpstreamPath = expectedUpstream.pathFromRepository(relPath);
232                if (expectedUpstreamPath != null) {
233                    diffCommand = "${ANDROID_BUILD_TOP}/libcore/tools/upstream/upstream-diff " + relPath;
234                } else {
235                    diffCommand = "FILE MISSING";
236                }
237            }
238            List<String> values = new ArrayList<>();
239            values.add(expectedUpstream.name());
240            values.add(guessedUpstream == null ? "" : guessedUpstream.name());
241            values.add(changedCommentsSummary);
242            values.addAll(comparisons);
243            values.add(diffCommand);
244            printTsv(out, values);
245        }
246    }
247
248    public void run() throws IOException {
249        List<Path> relPaths = standardRepositories.ojluni().loadRelPathsFromMakefile();
250        run(System.out, relPaths);
251    }
252
253    public static void main(String[] args) throws IOException {
254        StandardRepositories standardRepositories = StandardRepositories.fromEnv();
255        CompareUpstreams action = new CompareUpstreams(standardRepositories);
256        action.run();
257    }
258}
259