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