1 /* 2 * Copyright (C) 2023 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 libcore.tools.analyzer.openjdk; 18 19 import static java.util.stream.Collectors.toMap; 20 21 import libcore.tools.analyzer.openjdk.SignaturesCollector.MemberInfo; 22 import libcore.tools.analyzer.openjdk.SignaturesCollector.SignaturesCollection; 23 24 import org.objectweb.asm.tree.AbstractInsnNode; 25 import org.objectweb.asm.tree.ClassNode; 26 import org.objectweb.asm.tree.FieldInsnNode; 27 import org.objectweb.asm.tree.InvokeDynamicInsnNode; 28 import org.objectweb.asm.tree.MethodInsnNode; 29 import org.objectweb.asm.tree.MethodNode; 30 31 import java.io.Closeable; 32 import java.io.IOException; 33 import java.io.InputStream; 34 import java.io.UncheckedIOException; 35 import java.nio.file.Path; 36 import java.util.ArrayList; 37 import java.util.Arrays; 38 import java.util.Comparator; 39 import java.util.HashMap; 40 import java.util.HashSet; 41 import java.util.LinkedHashMap; 42 import java.util.LinkedList; 43 import java.util.List; 44 import java.util.Locale; 45 import java.util.Map; 46 import java.util.Queue; 47 import java.util.Set; 48 import java.util.function.Predicate; 49 import java.util.stream.Collectors; 50 import java.util.zip.ZipEntry; 51 import java.util.zip.ZipFile; 52 53 /** 54 * Dependency analyzer of a class in a OpenJDK version specified in the classpath. 55 * 56 * @see #analyze(List) 57 * 58 */ 59 public class DependencyAnalyzer { 60 private final Path mClassPath; 61 private final Path mExcludeClasspath; 62 private final boolean mIncludeInternal; 63 private final boolean mUsesExpectedUpstreamAsBaseDeps; 64 65 /** 66 * The public constructor with the analyzing configs. 67 * 68 * @param classpath must contains the classes in {@code classesOrPackages} 69 * @param excludeClasspath see {@link ExcludeClasspathFilter} 70 * @param includeInternal Dependency on the {@code classesOrPackages} are not included in the 71 * {@link Result} 72 * @param usesExpectedUpstreamAsBaseDeps see {@link ExpectedUpstreamFilter} 73 * 74 * @see #analyze(List) 75 */ DependencyAnalyzer(Path classpath, Path excludeClasspath, boolean includeInternal, boolean usesExpectedUpstreamAsBaseDeps)76 public DependencyAnalyzer(Path classpath, Path excludeClasspath, boolean includeInternal, 77 boolean usesExpectedUpstreamAsBaseDeps) { 78 mClassPath = classpath; 79 mExcludeClasspath = excludeClasspath; 80 mIncludeInternal = includeInternal; 81 mUsesExpectedUpstreamAsBaseDeps = usesExpectedUpstreamAsBaseDeps; 82 } 83 84 /** 85 * Analyze the dependencies of classes. 86 * 87 * @param classesOrPackages a list of classes and / or packages. 88 * @throws IllegalArgumentException {@code classesOrPackages} is not found in the class path. 89 * @throws UncheckedIOException error occurs when reading and parsing the .class files in 90 * the given classpaths. 91 */ analyze(List<String> classesOrPackages)92 public Result analyze(List<String> classesOrPackages) throws IllegalArgumentException, 93 UncheckedIOException { 94 try (ZipFile zipFile = new ZipFile(mClassPath.toFile()); 95 ExcludeClasspathFilter excludeFilter = ExcludeClasspathFilter 96 .getInstance(mExcludeClasspath); 97 ExpectedUpstreamFilters expectedUpstreamFilters = 98 ExpectedUpstreamFilters.getInstance(mUsesExpectedUpstreamAsBaseDeps)) { 99 List<ZipEntry> zipEntries = new ArrayList<>(classesOrPackages.size()); 100 for (String classOrPackage : classesOrPackages) { 101 zipEntries.addAll(getEntriesFromNameOrThrow(zipFile, mClassPath, classOrPackage)); 102 } 103 // Collect all class names by reading zip entry name. 104 // We could also read the class names to acquire the true class names, but 105 // it will take extra I/O and .class file parsing. 106 Set<String> classNames = zipEntries.stream() 107 .map(ZipEntry::getName) 108 .map(s -> s.substring(0, s.length() - ".class".length())) 109 .map(s -> s.startsWith("classes/") ? s.substring("classes/".length()) : s) 110 .collect(Collectors.toSet()); 111 112 Predicate<String> baseClassNamePredicate = (s) -> 113 mIncludeInternal || !classNames.contains(s); 114 baseClassNamePredicate = baseClassNamePredicate.and(excludeFilter::testClass); 115 116 Predicate<SignaturesCollector.Method> baseMethodPredicate = (m) -> 117 mIncludeInternal || !classNames.contains(m.getOwner()); 118 baseMethodPredicate = baseMethodPredicate.and(excludeFilter); 119 120 Predicate<SignaturesCollector.Field> baseFieldPredicate = (m) -> 121 mIncludeInternal || !classNames.contains(m.getOwner()); 122 baseFieldPredicate = baseFieldPredicate.and(excludeFilter); 123 124 Result result = new Result(); 125 SignaturesCollector topCollector = new SignaturesCollector(); 126 for (ZipEntry entry : zipEntries) { 127 try (InputStream in = zipFile.getInputStream(entry)) { 128 ClassNode classNode = ClassFileUtil.parseClass(in); 129 // Create predicates using the expectedUpstreamFilter filter 130 ExpectedUpstreamFilter expectedUpstreamFilter = expectedUpstreamFilters 131 .getFilter(classNode.name); 132 Predicate<String> classNamePredicate = baseClassNamePredicate 133 .and(expectedUpstreamFilter::testClass); 134 topCollector.setClassFilter(classNamePredicate); 135 136 Predicate<SignaturesCollector.Method> methodPredicate = baseMethodPredicate 137 .and(expectedUpstreamFilter); 138 139 Predicate<SignaturesCollector.Field> fieldPredicate = baseFieldPredicate 140 .and(expectedUpstreamFilter); 141 142 // Scan the super classes / interfaces and field types. 143 topCollector.addClassesFromClassNode(classNode); 144 List<MethodNode> methods = new ArrayList<>(classNode.methods); 145 methods.sort(Comparator.comparing(n -> n.name + n.desc)); 146 for (MethodNode method : methods) { 147 SignaturesCollector collector = new SignaturesCollector(); 148 collector.setMethodFilter(methodPredicate); 149 collector.setFieldFilter(fieldPredicate); 150 for (AbstractInsnNode insn : method.instructions) { 151 if (insn instanceof MethodInsnNode) { 152 collector.add((MethodInsnNode) insn); 153 } else if (insn instanceof FieldInsnNode) { 154 collector.add((FieldInsnNode) insn); 155 } else if (insn instanceof InvokeDynamicInsnNode) { 156 collector.add((InvokeDynamicInsnNode) insn); 157 } 158 } 159 SignaturesCollection collection = collector.getCollection(); 160 result.addMethodDependency(classNode, method, collection); 161 topCollector.add(collection); 162 } 163 } 164 } 165 result.setAggregatedDependency(topCollector.getCollection()); 166 167 return result; 168 } catch (IOException e) { 169 throw new UncheckedIOException(e); 170 } 171 } 172 173 /** 174 * {@link #getDetails()} and {@link #getAggregated()} return the dependencies. 175 */ 176 public static class Result { 177 178 public static class MethodDependency { 179 public final MethodNode mNode; 180 public final SignaturesCollection mDependency; 181 MethodDependency(MethodNode node, SignaturesCollection dependency)182 private MethodDependency(MethodNode node, SignaturesCollection dependency) { 183 mNode = node; 184 mDependency = dependency; 185 } 186 } 187 188 /** 189 * @return dependencies of every method in each class. The returned 190 * {@link SignaturesCollection} doesn't contain type dependencies, i.e. 191 * {@link SignaturesCollection#getClassStream()} returns an empty stream. 192 */ getDetails()193 public Map<String, List<MethodDependency>> getDetails() { 194 return mDetails; 195 } 196 getAggregated()197 public SignaturesCollection getAggregated() { 198 return mAggregated; 199 } 200 201 private SignaturesCollection mAggregated; 202 203 private final Map<String, List<MethodDependency>> mDetails = 204 new LinkedHashMap<>(); 205 Result()206 private Result() {} 207 setAggregatedDependency(SignaturesCollection dependency)208 private void setAggregatedDependency(SignaturesCollection dependency) { 209 this.mAggregated = dependency; 210 } 211 addMethodDependency(ClassNode classNode, MethodNode node, SignaturesCollection dependency)212 private void addMethodDependency(ClassNode classNode, MethodNode node, 213 SignaturesCollection dependency) { 214 List<MethodDependency> list = mDetails.computeIfAbsent(classNode.name, 215 k -> new ArrayList<>()); 216 217 list.add(new MethodDependency(node, dependency)); 218 } 219 } 220 getEntriesFromNameOrThrow(ZipFile zipFile, Path zipPath, String classOrPackage)221 private static List<ZipEntry> getEntriesFromNameOrThrow(ZipFile zipFile, Path zipPath, 222 String classOrPackage) throws IllegalArgumentException { 223 String part = classOrPackage.replaceAll("\\.", "/"); 224 String[] prefixes = new String[] { 225 part + ".class", 226 "classes/" + part + ".class", 227 // inner class 228 part + "$", 229 "classes/" + part + "$", 230 // package 231 part + "/", 232 "classes/" + part + "/", 233 234 }; 235 List<ZipEntry> entries = zipFile.stream() 236 .filter(zipEntry -> zipEntry.getName().endsWith(".class")) 237 .filter(zipEntry -> Arrays.stream(prefixes) 238 .anyMatch(prefix -> zipEntry.getName().startsWith(prefix))) 239 .collect(Collectors.toUnmodifiableList()); 240 if (entries.isEmpty()) { 241 throw new IllegalArgumentException(String.format(Locale.US, 242 "%s has no class files with a prefix of %s", zipPath.toString(), 243 String.join(", ", prefixes))); 244 } 245 return entries; 246 } 247 248 /** 249 * Filter the classes / methods / fields that exists in the given {@link classpath}. 250 */ 251 static class ExcludeClasspathFilter implements Predicate<MemberInfo>, Closeable { 252 protected final Path classpath; 253 getInstance(Path classpath)254 public static ExcludeClasspathFilter getInstance(Path classpath) 255 throws IOException { 256 if (classpath == null) { 257 return new ExcludeClasspathFilter(null); 258 } 259 return new Impl(classpath); 260 } 261 ExcludeClasspathFilter(Path classpath)262 private ExcludeClasspathFilter(Path classpath) { 263 this.classpath = classpath; 264 } 265 266 @Override close()267 public void close() throws IOException { 268 } 269 270 @Override test(MemberInfo methodOrField)271 public boolean test(MemberInfo methodOrField) { 272 return true; 273 } 274 hasClass(String internalClassName)275 protected boolean hasClass(String internalClassName) { 276 return false; 277 } 278 279 /** 280 * Return true if the class is not found in the classpath. Return false if the class 281 * is a primitive type or null. 282 */ testClass(String internalClassName)283 public final boolean testClass(String internalClassName) { 284 return !hasClass(internalClassName); 285 } 286 287 private static class Impl extends ExcludeClasspathFilter { 288 289 private static final ClassNode PLACEHOLDER = new ClassNode(); 290 291 private final ZipFile zipFile; 292 293 private final HashMap<String, ClassNode> classNodes = new HashMap<>(); 294 Impl(Path classpath)295 private Impl(Path classpath) throws IOException { 296 super(classpath); 297 this.zipFile = new ZipFile(classpath.toFile()); 298 } 299 300 @Override close()301 public void close() throws IOException { 302 zipFile.close(); 303 } 304 305 /** 306 * {@inheritDoc} 307 */ 308 @Override test(MemberInfo methodOrField)309 public boolean test(MemberInfo methodOrField) { 310 String className = methodOrField.getOwner(); 311 312 List<ClassNode> nodes = getClassNodes(className); 313 if (nodes.isEmpty()) { 314 return true; 315 } 316 317 if (methodOrField instanceof SignaturesCollector.Method) { 318 SignaturesCollector.Method i = (SignaturesCollector.Method) methodOrField; 319 return nodes.stream() 320 .flatMap(n -> n.methods.stream()) 321 .noneMatch(m -> i.getName().equals(m.name) && i.getDesc().equals(m.desc)); 322 } else { 323 SignaturesCollector.Field i = (SignaturesCollector.Field) methodOrField; 324 return nodes.stream() 325 .flatMap(n -> n.fields.stream()) 326 .noneMatch(f -> i.getName().equals(f.name) && i.getDesc().equals(f.desc)); 327 } 328 } 329 330 /** 331 * @return all {@link ClassNode} in the class hierarchy. 332 */ getClassNodes(String className)333 private List<ClassNode> getClassNodes(String className) { 334 // There isn't a .class file for an Array class. 335 // Look for an Object class instead. 336 if (className.startsWith("[")) { 337 className = "java/lang/Object"; 338 } 339 Set<String> visited = new HashSet<>(); 340 Queue<String> queue = new LinkedList<>(); 341 List<ClassNode> results = new ArrayList<>(); 342 queue.add(className); 343 while (!queue.isEmpty()) { 344 String next = queue.poll(); 345 if (visited.contains(next)) { 346 continue; 347 } 348 visited.add(next); 349 ClassNode node = getClassNode(next); 350 if (node == null) { 351 continue; 352 } 353 results.add(node); 354 if (node.superName != null) { 355 queue.add(node.superName); 356 } 357 queue.addAll(node.interfaces); 358 } 359 return results; 360 } 361 getClassNode(String className)362 private ClassNode getClassNode(String className) { 363 ClassNode val = classNodes.get(className); 364 if (val == PLACEHOLDER) { 365 return null; 366 } else if (val != null) { 367 return val; 368 } 369 370 ZipEntry entry = ClassFileUtil.getEntryFromClassName(zipFile, className, true); 371 if (entry == null) { 372 classNodes.put(className, PLACEHOLDER); 373 return null; 374 } 375 376 try { 377 val = ClassFileUtil.parseClass(zipFile.getInputStream(entry)); 378 } catch (IOException e) { 379 throw new UncheckedIOException(e); 380 } 381 382 classNodes.put(className, val); 383 return val; 384 } 385 386 @Override hasClass(String className)387 protected boolean hasClass(String className) { 388 ClassNode val = classNodes.get(className); 389 if (val == PLACEHOLDER) { 390 return false; 391 } else if (val != null) { 392 return true; 393 } 394 395 ZipEntry e = ClassFileUtil.getEntryFromClassName(zipFile, className, true); 396 if (e == null) { 397 classNodes.put(className, PLACEHOLDER); 398 return false; 399 } 400 401 return true; 402 } 403 } 404 } 405 406 private static class ExpectedUpstreamFilters implements Closeable { 407 408 private static final ExpectedUpstreamFilter PASS_THROUGH_FILTER = 409 new ExpectedUpstreamFilter(null); 410 411 private final Map<String, ZipFile> mZipFiles = new HashMap<>(); 412 private final Map<String, ExpectedUpstreamFilter> mFiltersCache = new HashMap<>(); 413 private final Map<String, ExpectedUpstreamFile.ExpectedUpstreamEntry> mEntries; 414 private final boolean mEnabled; 415 getInstance(boolean usesExpectedUpstreamAsBaseDeps)416 public static ExpectedUpstreamFilters getInstance(boolean usesExpectedUpstreamAsBaseDeps) 417 throws IOException { 418 return new ExpectedUpstreamFilters(usesExpectedUpstreamAsBaseDeps); 419 } 420 ExpectedUpstreamFilters(boolean usesExpectedUpstreamAsBaseDeps)421 private ExpectedUpstreamFilters(boolean usesExpectedUpstreamAsBaseDeps) throws IOException { 422 this.mEnabled = usesExpectedUpstreamAsBaseDeps; 423 List<ExpectedUpstreamFile.ExpectedUpstreamEntry> entries = 424 new ExpectedUpstreamFile().readAllEntries(); 425 this.mEntries = entries.stream() 426 .collect(toMap(e -> e.dstPath, e -> e)); 427 } 428 429 /** 430 * @return non-null instance 431 */ getFilter(String internalClassName)432 public ExpectedUpstreamFilter getFilter(String internalClassName) 433 throws UncheckedIOException { 434 if (!mEnabled) { 435 return PASS_THROUGH_FILTER; 436 } 437 438 ExpectedUpstreamFilter filter = mFiltersCache.get(internalClassName); 439 if (filter != null) { 440 return filter; 441 } 442 443 SignaturesCollection signatures; 444 try { 445 signatures = getSignatureCollection(internalClassName); 446 } catch (IOException e) { 447 throw new UncheckedIOException(e); 448 } 449 450 if (signatures == null) { 451 filter = PASS_THROUGH_FILTER; 452 } else { 453 filter = new ExpectedUpstreamFilter(signatures); 454 } 455 456 mFiltersCache.put(internalClassName, filter); 457 return filter; 458 } 459 getZipFile(String jdkVersion)460 private ZipFile getZipFile(String jdkVersion) throws IOException { 461 ZipFile result = mZipFiles.get(jdkVersion); 462 if (result != null) { 463 return result; 464 } 465 466 Path classpath; 467 switch (jdkVersion) { 468 case "jdk8u": 469 classpath = AndroidHostEnvUtil.parseInputClasspath("8"); 470 break; 471 case "jdk9u": 472 classpath = AndroidHostEnvUtil.parseInputClasspath("9"); 473 break; 474 case "jdk11u": 475 classpath = AndroidHostEnvUtil.parseInputClasspath("11"); 476 break; 477 case "jdk17u": 478 classpath = AndroidHostEnvUtil.parseInputClasspath("17"); 479 break; 480 case "jdk21u": 481 classpath = AndroidHostEnvUtil.parseInputClasspath("21"); 482 break; 483 default: 484 // unrecognized java version. Not supported until we obtain a specific 485 // java.base.jmod file from the specific git revision. 486 return null; 487 } 488 489 result = new ZipFile(classpath.toFile()); 490 mZipFiles.put(jdkVersion, result); 491 return result; 492 } 493 /** 494 * 495 * @param internalClassName class name with '/' separator 496 */ getClassNode(String internalClassName)497 private ClassNode getClassNode(String internalClassName) throws IOException { 498 String outerClassName = internalClassName.split("\\$")[0]; 499 String dstPath = "ojluni/src/main/java/" + outerClassName + ".java"; 500 501 ExpectedUpstreamFile.ExpectedUpstreamEntry e = mEntries.get(dstPath); 502 if (e == null) { 503 return null; 504 } 505 506 String jdkVersion = e.gitRef.split("/")[0]; 507 ZipFile zipFile = getZipFile(jdkVersion); 508 if (zipFile == null) { 509 return null; 510 } 511 512 ZipEntry zipEntry = ClassFileUtil.getEntryFromClassName(zipFile, 513 internalClassName, true); 514 if (zipEntry == null) { 515 return null; 516 } 517 try (InputStream in = zipFile.getInputStream(zipEntry)) { 518 return ClassFileUtil.parseClass(in); 519 } 520 } 521 getSignatureCollection(String internalClassName)522 private SignaturesCollection getSignatureCollection(String internalClassName) 523 throws IOException { 524 ClassNode node = getClassNode(internalClassName); 525 if (node == null) { 526 return null; 527 } 528 529 SignaturesCollector collector = new SignaturesCollector(); 530 collector.addClassesFromClassNode(node); 531 for (MethodNode method : node.methods) { 532 for (AbstractInsnNode inst : method.instructions) { 533 if (inst instanceof FieldInsnNode) { 534 collector.add((FieldInsnNode) inst); 535 } else if (inst instanceof MethodInsnNode) { 536 collector.add((MethodInsnNode) inst); 537 } else if (inst instanceof InvokeDynamicInsnNode) { 538 collector.add((InvokeDynamicInsnNode) inst); 539 } 540 } 541 } 542 543 return collector.getCollection(); 544 } 545 546 @Override close()547 public void close() throws IOException { 548 for (ZipFile zip : mZipFiles.values()) { 549 zip.close(); 550 } 551 mZipFiles.clear(); 552 } 553 } 554 555 /** 556 * This class filter the dependency that exist in the expected upstream version of 557 * the given class, specified in the libcore/EXPECTED_UPSTREAM file. Internally, the dependency 558 * are stored as {@code mSignatures}. 559 * Such dependencies are likely to be eliminated / replaced in the current libcore version 560 * even though the new OpenJDK version still depends on them, and is likely not needed 561 * when the class is upgraded to the target OpenJDK version. 562 */ 563 static class ExpectedUpstreamFilter implements Predicate<MemberInfo> { 564 565 /** 566 * It contains mappings of classes and / or packages renamed in a new OpenJDK version. 567 */ 568 private static final Map<String, String> PREFIX_RENAMES = new HashMap<>() {{ 569 put("sun/", "jdk/internal/"); 570 }}; 571 572 /** 573 * Contains the dependency of a given class in the expected upstream version. 574 */ 575 private final SignaturesCollection mSignatures; 576 ExpectedUpstreamFilter(SignaturesCollection signatures)577 public ExpectedUpstreamFilter(SignaturesCollection signatures) { 578 this.mSignatures = signatures; 579 } 580 581 /** 582 * Return false if the type dependency exists in the expected upstream version. 583 */ testClass(String internalClassName)584 public boolean testClass(String internalClassName) { 585 if (mSignatures == null) { 586 return true; 587 } 588 589 if (mSignatures.containsClass(internalClassName)) { 590 return false; 591 } 592 593 594 for (var e : PREFIX_RENAMES.entrySet()) { 595 String oldPrefix = e.getKey(); 596 String newPrefix = e.getValue(); 597 String className = internalClassName; 598 if (!className.startsWith(newPrefix)) { 599 continue; 600 } 601 className = oldPrefix + className.substring(newPrefix.length()); 602 if (mSignatures.containsClass(className)) { 603 return false; 604 } 605 } 606 607 return true; 608 } 609 610 /** 611 * Returns false if the method / field dependency exist in the expected upstream version. 612 */ 613 @Override test(MemberInfo member)614 public boolean test(MemberInfo member) { 615 if (mSignatures == null) { 616 return true; 617 } 618 619 if (mSignatures.contains(member)) { 620 return false; 621 } 622 623 for (var e : PREFIX_RENAMES.entrySet()) { 624 String newPrefix = e.getValue(); 625 boolean hasPrefixInOwner = member.getOwner().startsWith(newPrefix); 626 if (!hasPrefixInOwner && !member.getDesc().contains(newPrefix)) { 627 continue; 628 } 629 String oldPrefix = e.getKey(); 630 String owner = member.getOwner(); 631 if (hasPrefixInOwner) { 632 owner = oldPrefix + owner.substring(newPrefix.length()); 633 } 634 String desc = member.getDesc().replace(newPrefix, oldPrefix); 635 String name = member.getName(); 636 637 if (member instanceof SignaturesCollector.Method) { 638 if (mSignatures.containsMethod(owner, name, desc)) { 639 return false; 640 } 641 } else { 642 if (mSignatures.containsField(owner, name, desc)) { 643 return false; 644 } 645 } 646 } 647 648 return true; 649 } 650 } 651 } 652