1/* 2 * Copyright (C) 2012 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 com.android.tools.layoutlib.create; 18 19import com.android.tools.layoutlib.annotations.VisibleForTesting; 20import com.android.tools.layoutlib.annotations.VisibleForTesting.Visibility; 21 22import org.objectweb.asm.AnnotationVisitor; 23import org.objectweb.asm.Attribute; 24import org.objectweb.asm.ClassReader; 25import org.objectweb.asm.ClassVisitor; 26import org.objectweb.asm.FieldVisitor; 27import org.objectweb.asm.Label; 28import org.objectweb.asm.MethodVisitor; 29import org.objectweb.asm.Opcodes; 30import org.objectweb.asm.Type; 31import org.objectweb.asm.signature.SignatureReader; 32import org.objectweb.asm.signature.SignatureVisitor; 33 34import java.io.IOException; 35import java.util.ArrayList; 36import java.util.Enumeration; 37import java.util.List; 38import java.util.Map; 39import java.util.Map.Entry; 40import java.util.Set; 41import java.util.TreeMap; 42import java.util.TreeSet; 43import java.util.zip.ZipEntry; 44import java.util.zip.ZipFile; 45 46/** 47 * Analyzes the input JAR using the ASM java bytecode manipulation library 48 * to list the classes and their dependencies. A "dependency" is a class 49 * used by another class. 50 */ 51public class DependencyFinder { 52 53 // Note: a bunch of stuff has package-level access for unit tests. Consider it private. 54 55 /** Output logger. */ 56 private final Log mLog; 57 58 /** 59 * Creates a new analyzer. 60 * 61 * @param log The log output. 62 */ 63 public DependencyFinder(Log log) { 64 mLog = log; 65 } 66 67 /** 68 * Starts the analysis using parameters from the constructor. 69 * 70 * @param osJarPath The input source JARs to parse. 71 * @return A pair: [0]: map { class FQCN => set of FQCN class dependencies }. 72 * [1]: map { missing class FQCN => set of FQCN class that uses it. } 73 */ 74 public List<Map<String, Set<String>>> findDeps(List<String> osJarPath) throws IOException { 75 76 Map<String, ClassReader> zipClasses = parseZip(osJarPath); 77 mLog.info("Found %d classes in input JAR%s.", 78 zipClasses.size(), 79 osJarPath.size() > 1 ? "s" : ""); 80 81 Map<String, Set<String>> deps = findClassesDeps(zipClasses); 82 83 Map<String, Set<String>> missing = findMissingClasses(deps, zipClasses.keySet()); 84 85 List<Map<String, Set<String>>> result = new ArrayList<Map<String,Set<String>>>(2); 86 result.add(deps); 87 result.add(missing); 88 return result; 89 } 90 91 /** 92 * Prints dependencies to the current logger, found stuff and missing stuff. 93 */ 94 public void printAllDeps(List<Map<String, Set<String>>> result) { 95 assert result.size() == 2; 96 Map<String, Set<String>> deps = result.get(0); 97 Map<String, Set<String>> missing = result.get(1); 98 99 // Print all dependences found in the format: 100 // +Found: <FQCN from zip> 101 // uses: FQCN 102 103 mLog.info("++++++ %d Entries found in source JARs", deps.size()); 104 mLog.info(""); 105 106 for (Entry<String, Set<String>> entry : deps.entrySet()) { 107 mLog.info( "+Found : %s", entry.getKey()); 108 for (String dep : entry.getValue()) { 109 mLog.info(" uses: %s", dep); 110 } 111 112 mLog.info(""); 113 } 114 115 116 // Now print all missing dependences in the format: 117 // -Missing <FQCN>: 118 // used by: <FQCN> 119 120 mLog.info(""); 121 mLog.info("------ %d Entries missing from source JARs", missing.size()); 122 mLog.info(""); 123 124 for (Entry<String, Set<String>> entry : missing.entrySet()) { 125 mLog.info( "-Missing : %s", entry.getKey()); 126 for (String dep : entry.getValue()) { 127 mLog.info(" used by: %s", dep); 128 } 129 130 mLog.info(""); 131 } 132 } 133 134 /** 135 * Prints only a summary of the missing dependencies to the current logger. 136 */ 137 public void printMissingDeps(List<Map<String, Set<String>>> result) { 138 assert result.size() == 2; 139 @SuppressWarnings("unused") Map<String, Set<String>> deps = result.get(0); 140 Map<String, Set<String>> missing = result.get(1); 141 142 for (String fqcn : missing.keySet()) { 143 mLog.info("%s", fqcn); 144 } 145 } 146 147 // ---------------- 148 149 /** 150 * Parses a JAR file and returns a list of all classes founds using a map 151 * class name => ASM ClassReader. Class names are in the form "android.view.View". 152 */ 153 Map<String,ClassReader> parseZip(List<String> jarPathList) throws IOException { 154 TreeMap<String, ClassReader> classes = new TreeMap<String, ClassReader>(); 155 156 for (String jarPath : jarPathList) { 157 ZipFile zip = new ZipFile(jarPath); 158 Enumeration<? extends ZipEntry> entries = zip.entries(); 159 ZipEntry entry; 160 while (entries.hasMoreElements()) { 161 entry = entries.nextElement(); 162 if (entry.getName().endsWith(".class")) { 163 ClassReader cr = new ClassReader(zip.getInputStream(entry)); 164 String className = classReaderToClassName(cr); 165 classes.put(className, cr); 166 } 167 } 168 } 169 170 return classes; 171 } 172 173 /** 174 * Utility that returns the fully qualified binary class name for a ClassReader. 175 * E.g. it returns something like android.view.View. 176 */ 177 static String classReaderToClassName(ClassReader classReader) { 178 if (classReader == null) { 179 return null; 180 } else { 181 return classReader.getClassName().replace('/', '.'); 182 } 183 } 184 185 /** 186 * Utility that returns the fully qualified binary class name from a path-like FQCN. 187 * E.g. it returns android.view.View from android/view/View. 188 */ 189 static String internalToBinaryClassName(String className) { 190 if (className == null) { 191 return null; 192 } else { 193 return className.replace('/', '.'); 194 } 195 } 196 197 /** 198 * Finds all dependencies for all classes in keepClasses which are also 199 * listed in zipClasses. Returns a map of all the dependencies found. 200 */ 201 Map<String, Set<String>> findClassesDeps(Map<String, ClassReader> zipClasses) { 202 203 // The dependencies that we'll collect. 204 // It's a map Class name => uses class names. 205 Map<String, Set<String>> dependencyMap = new TreeMap<String, Set<String>>(); 206 207 DependencyVisitor visitor = getVisitor(); 208 209 int count = 0; 210 try { 211 for (Entry<String, ClassReader> entry : zipClasses.entrySet()) { 212 String name = entry.getKey(); 213 214 TreeSet<String> set = new TreeSet<String>(); 215 dependencyMap.put(name, set); 216 visitor.setDependencySet(set); 217 218 ClassReader cr = entry.getValue(); 219 cr.accept(visitor, 0 /* flags */); 220 221 visitor.setDependencySet(null); 222 223 mLog.debugNoln("Visited %d classes\r", ++count); 224 } 225 } finally { 226 mLog.debugNoln("\n"); 227 } 228 229 return dependencyMap; 230 } 231 232 /** 233 * Computes which classes FQCN were found as dependencies that are NOT listed 234 * in the original JAR classes. 235 * 236 * @param deps The map { FQCN => dependencies[] } returned by {@link #findClassesDeps(Map)}. 237 * @param zipClasses The set of all classes FQCN found in the JAR files. 238 * @return A map { FQCN not found in the zipClasses => classes using it } 239 */ 240 private Map<String, Set<String>> findMissingClasses( 241 Map<String, Set<String>> deps, 242 Set<String> zipClasses) { 243 Map<String, Set<String>> missing = new TreeMap<String, Set<String>>(); 244 245 for (Entry<String, Set<String>> entry : deps.entrySet()) { 246 String name = entry.getKey(); 247 248 for (String dep : entry.getValue()) { 249 if (!zipClasses.contains(dep)) { 250 // This dependency doesn't exist in the zip classes. 251 Set<String> set = missing.get(dep); 252 if (set == null) { 253 set = new TreeSet<String>(); 254 missing.put(dep, set); 255 } 256 set.add(name); 257 } 258 } 259 260 } 261 262 return missing; 263 } 264 265 266 // ---------------------------------- 267 268 /** 269 * Instantiates a new DependencyVisitor. Useful for unit tests. 270 */ 271 @VisibleForTesting(visibility=Visibility.PRIVATE) 272 DependencyVisitor getVisitor() { 273 return new DependencyVisitor(); 274 } 275 276 /** 277 * Visitor to collect all the type dependencies from a class. 278 */ 279 public class DependencyVisitor extends ClassVisitor { 280 281 private Set<String> mCurrentDepSet; 282 283 /** 284 * Creates a new visitor that will find all the dependencies for the visited class. 285 */ 286 public DependencyVisitor() { 287 super(Opcodes.ASM4); 288 } 289 290 /** 291 * Sets the {@link Set} where to record direct dependencies for this class. 292 * This will change before each {@link ClassReader#accept(ClassVisitor, int)} call. 293 */ 294 public void setDependencySet(Set<String> set) { 295 mCurrentDepSet = set; 296 } 297 298 /** 299 * Considers the given class name as a dependency. 300 */ 301 public void considerName(String className) { 302 if (className == null) { 303 return; 304 } 305 306 className = internalToBinaryClassName(className); 307 308 try { 309 // exclude classes that are part of the default JRE (the one executing this program) 310 // or in java package (we won't be able to load them anyway). 311 if (className.startsWith("java.") || 312 getClass().getClassLoader().loadClass(className) != null) { 313 return; 314 } 315 } catch (ClassNotFoundException e) { 316 // ignore 317 } 318 319 // Add it to the dependency set for the currently visited class, as needed. 320 assert mCurrentDepSet != null; 321 mCurrentDepSet.add(className); 322 } 323 324 /** 325 * Considers this array of names using considerName(). 326 */ 327 public void considerNames(String[] classNames) { 328 if (classNames != null) { 329 for (String className : classNames) { 330 considerName(className); 331 } 332 } 333 } 334 335 /** 336 * Considers this signature or type signature by invoking the {@link SignatureVisitor} 337 * on it. 338 */ 339 public void considerSignature(String signature) { 340 if (signature != null) { 341 SignatureReader sr = new SignatureReader(signature); 342 // SignatureReader.accept will call accessType so we don't really have 343 // to differentiate where the signature comes from. 344 sr.accept(new MySignatureVisitor()); 345 } 346 } 347 348 /** 349 * Considers this {@link Type}. For arrays, the element type is considered. 350 * If the type is an object, it's internal name is considered. 351 */ 352 public void considerType(Type t) { 353 if (t != null) { 354 if (t.getSort() == Type.ARRAY) { 355 t = t.getElementType(); 356 } 357 if (t.getSort() == Type.OBJECT) { 358 considerName(t.getInternalName()); 359 } 360 } 361 } 362 363 /** 364 * Considers a descriptor string. The descriptor is converted to a {@link Type} 365 * and then considerType() is invoked. 366 */ 367 public boolean considerDesc(String desc) { 368 if (desc != null) { 369 try { 370 if (desc.length() > 0 && desc.charAt(0) == '(') { 371 // This is a method descriptor with arguments and a return type. 372 Type t = Type.getReturnType(desc); 373 considerType(t); 374 375 for (Type arg : Type.getArgumentTypes(desc)) { 376 considerType(arg); 377 } 378 379 } else { 380 Type t = Type.getType(desc); 381 considerType(t); 382 } 383 return true; 384 } catch (ArrayIndexOutOfBoundsException e) { 385 // ignore, not a valid type. 386 } 387 } 388 return false; 389 } 390 391 392 // --------------------------------------------------- 393 // --- ClassVisitor, FieldVisitor 394 // --------------------------------------------------- 395 396 // Visits a class header 397 @Override 398 public void visit(int version, int access, String name, 399 String signature, String superName, String[] interfaces) { 400 // signature is the signature of this class. May be null if the class is not a generic 401 // one, and does not extend or implement generic classes or interfaces. 402 403 if (signature != null) { 404 considerSignature(signature); 405 } 406 407 // superName is the internal of name of the super class (see getInternalName). 408 // For interfaces, the super class is Object. May be null but only for the Object class. 409 considerName(superName); 410 411 // interfaces is the internal names of the class's interfaces (see getInternalName). 412 // May be null. 413 considerNames(interfaces); 414 } 415 416 417 @Override 418 public AnnotationVisitor visitAnnotation(String desc, boolean visible) { 419 // desc is the class descriptor of the annotation class. 420 considerDesc(desc); 421 return new MyAnnotationVisitor(); 422 } 423 424 @Override 425 public void visitAttribute(Attribute attr) { 426 // pass 427 } 428 429 // Visits the end of a class 430 @Override 431 public void visitEnd() { 432 // pass 433 } 434 435 private class MyFieldVisitor extends FieldVisitor { 436 437 public MyFieldVisitor() { 438 super(Opcodes.ASM4); 439 } 440 441 @Override 442 public AnnotationVisitor visitAnnotation(String desc, boolean visible) { 443 // desc is the class descriptor of the annotation class. 444 considerDesc(desc); 445 return new MyAnnotationVisitor(); 446 } 447 448 @Override 449 public void visitAttribute(Attribute attr) { 450 // pass 451 } 452 453 // Visits the end of a class 454 @Override 455 public void visitEnd() { 456 // pass 457 } 458 } 459 460 @Override 461 public FieldVisitor visitField(int access, String name, String desc, 462 String signature, Object value) { 463 // desc is the field's descriptor (see Type). 464 considerDesc(desc); 465 466 // signature is the field's signature. May be null if the field's type does not use 467 // generic types. 468 considerSignature(signature); 469 470 return new MyFieldVisitor(); 471 } 472 473 @Override 474 public void visitInnerClass(String name, String outerName, String innerName, int access) { 475 // name is the internal name of an inner class (see getInternalName). 476 // Note: outerName/innerName seems to be null when we're reading the 477 // _Original_ClassName classes generated by layoutlib_create. 478 if (outerName != null) { 479 considerName(name); 480 } 481 } 482 483 @Override 484 public MethodVisitor visitMethod(int access, String name, String desc, 485 String signature, String[] exceptions) { 486 // desc is the method's descriptor (see Type). 487 considerDesc(desc); 488 // signature is the method's signature. May be null if the method parameters, return 489 // type and exceptions do not use generic types. 490 considerSignature(signature); 491 492 return new MyMethodVisitor(); 493 } 494 495 @Override 496 public void visitOuterClass(String owner, String name, String desc) { 497 // pass 498 } 499 500 @Override 501 public void visitSource(String source, String debug) { 502 // pass 503 } 504 505 506 // --------------------------------------------------- 507 // --- MethodVisitor 508 // --------------------------------------------------- 509 510 private class MyMethodVisitor extends MethodVisitor { 511 512 public MyMethodVisitor() { 513 super(Opcodes.ASM4); 514 } 515 516 517 @Override 518 public AnnotationVisitor visitAnnotationDefault() { 519 return new MyAnnotationVisitor(); 520 } 521 522 @Override 523 public void visitCode() { 524 // pass 525 } 526 527 // field instruction 528 @Override 529 public void visitFieldInsn(int opcode, String owner, String name, String desc) { 530 // owner is the class that declares the field. 531 considerName(owner); 532 // desc is the field's descriptor (see Type). 533 considerDesc(desc); 534 } 535 536 @Override 537 public void visitFrame(int type, int local, Object[] local2, int stack, Object[] stack2) { 538 // pass 539 } 540 541 @Override 542 public void visitIincInsn(int var, int increment) { 543 // pass -- an IINC instruction 544 } 545 546 @Override 547 public void visitInsn(int opcode) { 548 // pass -- a zero operand instruction 549 } 550 551 @Override 552 public void visitIntInsn(int opcode, int operand) { 553 // pass -- a single int operand instruction 554 } 555 556 @Override 557 public void visitJumpInsn(int opcode, Label label) { 558 // pass -- a jump instruction 559 } 560 561 @Override 562 public void visitLabel(Label label) { 563 // pass -- a label target 564 } 565 566 // instruction to load a constant from the stack 567 @Override 568 public void visitLdcInsn(Object cst) { 569 if (cst instanceof Type) { 570 considerType((Type) cst); 571 } 572 } 573 574 @Override 575 public void visitLineNumber(int line, Label start) { 576 // pass 577 } 578 579 @Override 580 public void visitLocalVariable(String name, String desc, 581 String signature, Label start, Label end, int index) { 582 // desc is the type descriptor of this local variable. 583 considerDesc(desc); 584 // signature is the type signature of this local variable. May be null if the local 585 // variable type does not use generic types. 586 considerSignature(signature); 587 } 588 589 @Override 590 public void visitLookupSwitchInsn(Label dflt, int[] keys, Label[] labels) { 591 // pass -- a lookup switch instruction 592 } 593 594 @Override 595 public void visitMaxs(int maxStack, int maxLocals) { 596 // pass 597 } 598 599 // instruction that invokes a method 600 @Override 601 public void visitMethodInsn(int opcode, String owner, String name, String desc) { 602 603 // owner is the internal name of the method's owner class 604 if (!considerDesc(owner) && owner.indexOf('/') != -1) { 605 considerName(owner); 606 } 607 // desc is the method's descriptor (see Type). 608 considerDesc(desc); 609 } 610 611 // instruction multianewarray, whatever that is 612 @Override 613 public void visitMultiANewArrayInsn(String desc, int dims) { 614 615 // desc an array type descriptor. 616 considerDesc(desc); 617 } 618 619 @Override 620 public AnnotationVisitor visitParameterAnnotation(int parameter, String desc, 621 boolean visible) { 622 // desc is the class descriptor of the annotation class. 623 considerDesc(desc); 624 return new MyAnnotationVisitor(); 625 } 626 627 @Override 628 public void visitTableSwitchInsn(int min, int max, Label dflt, Label[] labels) { 629 // pass -- table switch instruction 630 631 } 632 633 @Override 634 public void visitTryCatchBlock(Label start, Label end, Label handler, String type) { 635 // type is the internal name of the type of exceptions handled by the handler, 636 // or null to catch any exceptions (for "finally" blocks). 637 considerName(type); 638 } 639 640 // type instruction 641 @Override 642 public void visitTypeInsn(int opcode, String type) { 643 // type is the operand of the instruction to be visited. This operand must be the 644 // internal name of an object or array class. 645 considerName(type); 646 } 647 648 @Override 649 public void visitVarInsn(int opcode, int var) { 650 // pass -- local variable instruction 651 } 652 } 653 654 private class MySignatureVisitor extends SignatureVisitor { 655 656 public MySignatureVisitor() { 657 super(Opcodes.ASM4); 658 } 659 660 // --------------------------------------------------- 661 // --- SignatureVisitor 662 // --------------------------------------------------- 663 664 private String mCurrentSignatureClass = null; 665 666 // Starts the visit of a signature corresponding to a class or interface type 667 @Override 668 public void visitClassType(String name) { 669 mCurrentSignatureClass = name; 670 considerName(name); 671 } 672 673 // Visits an inner class 674 @Override 675 public void visitInnerClassType(String name) { 676 if (mCurrentSignatureClass != null) { 677 mCurrentSignatureClass += "$" + name; 678 considerName(mCurrentSignatureClass); 679 } 680 } 681 682 @Override 683 public SignatureVisitor visitArrayType() { 684 return new MySignatureVisitor(); 685 } 686 687 @Override 688 public void visitBaseType(char descriptor) { 689 // pass -- a primitive type, ignored 690 } 691 692 @Override 693 public SignatureVisitor visitClassBound() { 694 return new MySignatureVisitor(); 695 } 696 697 @Override 698 public SignatureVisitor visitExceptionType() { 699 return new MySignatureVisitor(); 700 } 701 702 @Override 703 public void visitFormalTypeParameter(String name) { 704 // pass 705 } 706 707 @Override 708 public SignatureVisitor visitInterface() { 709 return new MySignatureVisitor(); 710 } 711 712 @Override 713 public SignatureVisitor visitInterfaceBound() { 714 return new MySignatureVisitor(); 715 } 716 717 @Override 718 public SignatureVisitor visitParameterType() { 719 return new MySignatureVisitor(); 720 } 721 722 @Override 723 public SignatureVisitor visitReturnType() { 724 return new MySignatureVisitor(); 725 } 726 727 @Override 728 public SignatureVisitor visitSuperclass() { 729 return new MySignatureVisitor(); 730 } 731 732 @Override 733 public SignatureVisitor visitTypeArgument(char wildcard) { 734 return new MySignatureVisitor(); 735 } 736 737 @Override 738 public void visitTypeVariable(String name) { 739 // pass 740 } 741 742 @Override 743 public void visitTypeArgument() { 744 // pass 745 } 746 } 747 748 749 // --------------------------------------------------- 750 // --- AnnotationVisitor 751 // --------------------------------------------------- 752 753 private class MyAnnotationVisitor extends AnnotationVisitor { 754 755 public MyAnnotationVisitor() { 756 super(Opcodes.ASM4); 757 } 758 759 // Visits a primitive value of an annotation 760 @Override 761 public void visit(String name, Object value) { 762 // value is the actual value, whose type must be Byte, Boolean, Character, Short, 763 // Integer, Long, Float, Double, String or Type 764 if (value instanceof Type) { 765 considerType((Type) value); 766 } 767 } 768 769 @Override 770 public AnnotationVisitor visitAnnotation(String name, String desc) { 771 // desc is the class descriptor of the nested annotation class. 772 considerDesc(desc); 773 return new MyAnnotationVisitor(); 774 } 775 776 @Override 777 public AnnotationVisitor visitArray(String name) { 778 return new MyAnnotationVisitor(); 779 } 780 781 @Override 782 public void visitEnum(String name, String desc, String value) { 783 // desc is the class descriptor of the enumeration class. 784 considerDesc(desc); 785 } 786 } 787 } 788} 789