1 /*
   2  * Copyright (c) 2009, 2012, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 package com.sun.tools.classfile;
  26 
  27 import java.util.Deque;
  28 import java.util.HashMap;
  29 import java.util.HashSet;
  30 import java.util.LinkedList;
  31 import java.util.List;
  32 import java.util.Map;
  33 import java.util.Set;
  34 import java.util.regex.Pattern;
  35 
  36 import com.sun.tools.classfile.Dependency.Filter;
  37 import com.sun.tools.classfile.Dependency.Finder;
  38 import com.sun.tools.classfile.Dependency.Location;
  39 import com.sun.tools.classfile.Type.ArrayType;
  40 import com.sun.tools.classfile.Type.ClassSigType;
  41 import com.sun.tools.classfile.Type.ClassType;
  42 import com.sun.tools.classfile.Type.MethodType;
  43 import com.sun.tools.classfile.Type.SimpleType;
  44 import com.sun.tools.classfile.Type.TypeParamType;
  45 import com.sun.tools.classfile.Type.WildcardType;
  46 import static com.sun.tools.classfile.ConstantPool.*;
  47 
  48 /**
  49  * A framework for determining {@link Dependency dependencies} between class files.
  50  *
  51  * A {@link Dependency.Finder finder} is used to identify the dependencies of
  52  * individual classes. Some finders may return subtypes of {@code Dependency} to
  53  * further characterize the type of dependency, such as a dependency on a
  54  * method within a class.
  55  *
  56  * A {@link Dependency.Filter filter} may be used to restrict the set of
  57  * dependencies found by a finder.
  58  *
  59  * Dependencies that are found may be passed to a {@link Dependencies.Recorder
  60  * recorder} so that the dependencies can be stored in a custom data structure.
  61  */
  62 public class Dependencies {
  63     /**
  64      * Thrown when a class file cannot be found.
  65      */
  66     public static class ClassFileNotFoundException extends Exception {
  67         private static final long serialVersionUID = 3632265927794475048L;
  68 
  69         public ClassFileNotFoundException(String className) {
  70             super(className);
  71             this.className = className;
  72         }
  73 
  74         public ClassFileNotFoundException(String className, Throwable cause) {
  75             this(className);
  76             initCause(cause);
  77         }
  78 
  79         public final String className;
  80     }
  81 
  82     /**
  83      * Thrown when an exception is found processing a class file.
  84      */
  85     public static class ClassFileError extends Error {
  86         private static final long serialVersionUID = 4111110813961313203L;
  87 
  88         public ClassFileError(Throwable cause) {
  89             initCause(cause);
  90         }
  91     }
  92 
  93     /**
  94      * Service provider interface to locate and read class files.
  95      */
  96     public interface ClassFileReader {
  97         /**
  98          * Get the ClassFile object for a specified class.
  99          * @param className the name of the class to be returned.
 100          * @return the ClassFile for the given class
 101          * @throws Dependencies.ClassFileNotFoundException if the classfile cannot be
 102          *   found
 103          */
 104         public ClassFile getClassFile(String className)
 105                 throws ClassFileNotFoundException;
 106     }
 107 
 108     /**
 109      * Service provide interface to handle results.
 110      */
 111     public interface Recorder {
 112         /**
 113          * Record a dependency that has been found.
 114          * @param d
 115          */
 116         public void addDependency(Dependency d);
 117     }
 118 
 119     /**
 120      * Get the  default finder used to locate the dependencies for a class.
 121      * @return the default finder
 122      */
 123     public static Finder getDefaultFinder() {
 124         return new APIDependencyFinder(AccessFlags.ACC_PRIVATE);
 125     }
 126 
 127     /**
 128      * Get a finder used to locate the API dependencies for a class.
 129      * These include the superclass, superinterfaces, and classes referenced in
 130      * the declarations of fields and methods.  The fields and methods that
 131      * are checked can be limited according to a specified access.
 132      * The access parameter must be one of {@link AccessFlags#ACC_PUBLIC ACC_PUBLIC},
 133      * {@link AccessFlags#ACC_PRIVATE ACC_PRIVATE},
 134      * {@link AccessFlags#ACC_PROTECTED ACC_PROTECTED}, or 0 for
 135      * package private access. Members with greater than or equal accessibility
 136      * to that specified will be searched for dependencies.
 137      * @param access the access of members to be checked
 138      * @return an API finder
 139      */
 140     public static Finder getAPIFinder(int access) {
 141         return new APIDependencyFinder(access);
 142     }
 143 
 144     /**
 145      * Get the finder used to locate the dependencies for a class.
 146      * @return the finder
 147      */
 148     public Finder getFinder() {
 149         if (finder == null)
 150             finder = getDefaultFinder();
 151         return finder;
 152     }
 153 
 154     /**
 155      * Set the finder used to locate the dependencies for a class.
 156      * @param f the finder
 157      */
 158     public void setFinder(Finder f) {
 159         f.getClass(); // null check
 160         finder = f;
 161     }
 162 
 163     /**
 164      * Get the default filter used to determine included when searching
 165      * the transitive closure of all the dependencies.
 166      * Unless overridden, the default filter accepts all dependencies.
 167      * @return the default filter.
 168      */
 169     public static Filter getDefaultFilter() {
 170         return DefaultFilter.instance();
 171     }
 172 
 173     /**
 174      * Get a filter which uses a regular expression on the target's class name
 175      * to determine if a dependency is of interest.
 176      * @param pattern the pattern used to match the target's class name
 177      * @return a filter for matching the target class name with a regular expression
 178      */
 179     public static Filter getRegexFilter(Pattern pattern) {
 180         return new TargetRegexFilter(pattern);
 181     }
 182 
 183     /**
 184      * Get a filter which checks the package of a target's class name
 185      * to determine if a dependency is of interest. The filter checks if the
 186      * package of the target's class matches any of a set of given package
 187      * names. The match may optionally match subpackages of the given names as well.
 188      * @param packageNames the package names used to match the target's class name
 189      * @param matchSubpackages whether or not to match subpackages as well
 190      * @return a filter for checking the target package name against a list of package names
 191      */
 192     public static Filter getPackageFilter(Set<String> packageNames, boolean matchSubpackages) {
 193         return new TargetPackageFilter(packageNames, matchSubpackages);
 194     }
 195 
 196     /**
 197      * Get the filter used to determine the dependencies included when searching
 198      * the transitive closure of all the dependencies.
 199      * Unless overridden, the default filter accepts all dependencies.
 200      * @return the filter
 201      */
 202     public Filter getFilter() {
 203         if (filter == null)
 204             filter = getDefaultFilter();
 205         return filter;
 206     }
 207 
 208     /**
 209      * Set the filter used to determine the dependencies included when searching
 210      * the transitive closure of all the dependencies.
 211      * @param f the filter
 212      */
 213     public void setFilter(Filter f) {
 214         f.getClass(); // null check
 215         filter = f;
 216     }
 217 
 218     /**
 219      * Find the dependencies of a class, using the current
 220      * {@link Dependencies#getFinder finder} and
 221      * {@link Dependencies#getFilter filter}.
 222      * The search may optionally include the transitive closure of all the
 223      * filtered dependencies, by also searching in the classes named in those
 224      * dependencies.
 225      * @param classFinder a finder to locate class files
 226      * @param rootClassNames the names of the root classes from which to begin
 227      *      searching
 228      * @param transitiveClosure whether or not to also search those classes
 229      *      named in any filtered dependencies that are found.
 230      * @return the set of dependencies that were found
 231      * @throws ClassFileNotFoundException if a required class file cannot be found
 232      * @throws ClassFileError if an error occurs while processing a class file,
 233      *      such as an error in the internal class file structure.
 234      */
 235     public Set<Dependency> findAllDependencies(
 236             ClassFileReader classFinder, Set<String> rootClassNames,
 237             boolean transitiveClosure)
 238             throws ClassFileNotFoundException {
 239         final Set<Dependency> results = new HashSet<Dependency>();
 240         Recorder r = new Recorder() {
 241             public void addDependency(Dependency d) {
 242                 results.add(d);
 243             }
 244         };
 245         findAllDependencies(classFinder, rootClassNames, transitiveClosure, r);
 246         return results;
 247     }
 248 
 249 
 250 
 251     /**
 252      * Find the dependencies of a class, using the current
 253      * {@link Dependencies#getFinder finder} and
 254      * {@link Dependencies#getFilter filter}.
 255      * The search may optionally include the transitive closure of all the
 256      * filtered dependencies, by also searching in the classes named in those
 257      * dependencies.
 258      * @param classFinder a finder to locate class files
 259      * @param rootClassNames the names of the root classes from which to begin
 260      *      searching
 261      * @param transitiveClosure whether or not to also search those classes
 262      *      named in any filtered dependencies that are found.
 263      * @param recorder a recorder for handling the results
 264      * @throws ClassFileNotFoundException if a required class file cannot be found
 265      * @throws ClassFileError if an error occurs while processing a class file,
 266      *      such as an error in the internal class file structure.
 267      */
 268     public void findAllDependencies(
 269             ClassFileReader classFinder, Set<String> rootClassNames,
 270             boolean transitiveClosure, Recorder recorder)
 271             throws ClassFileNotFoundException {
 272         Set<String> doneClasses = new HashSet<String>();
 273 
 274         getFinder();  // ensure initialized
 275         getFilter();  // ensure initialized
 276 
 277         // Work queue of names of classfiles to be searched.
 278         // Entries will be unique, and for classes that do not yet have
 279         // dependencies in the results map.
 280         Deque<String> deque = new LinkedList<String>(rootClassNames);
 281 
 282         String className;
 283         while ((className = deque.poll()) != null) {
 284             assert (!doneClasses.contains(className));
 285             doneClasses.add(className);
 286 
 287             ClassFile cf = classFinder.getClassFile(className);
 288 
 289             // The following code just applies the filter to the dependencies
 290             // followed for the transitive closure.
 291             for (Dependency d: finder.findDependencies(cf)) {
 292                 recorder.addDependency(d);
 293                 if (transitiveClosure && filter.accepts(d)) {
 294                     String cn = d.getTarget().getClassName();
 295                     if (!doneClasses.contains(cn))
 296                         deque.add(cn);
 297                 }
 298             }
 299         }
 300     }
 301 
 302     private Filter filter;
 303     private Finder finder;
 304 
 305     /**
 306      * A location identifying a class.
 307      */
 308     static class SimpleLocation implements Location {
 309         public SimpleLocation(String className) {
 310             this.className = className;
 311         }
 312 
 313         /**
 314          * Get the name of the class being depended on. This name will be used to
 315          * locate the class file for transitive dependency analysis.
 316          * @return the name of the class being depended on
 317          */
 318         public String getClassName() {
 319             return className;
 320         }
 321 
 322         @Override
 323         public boolean equals(Object other) {
 324             if (this == other)
 325                 return true;
 326             if (!(other instanceof SimpleLocation))
 327                 return false;
 328             return (className.equals(((SimpleLocation) other).className));
 329         }
 330 
 331         @Override
 332         public int hashCode() {
 333             return className.hashCode();
 334         }
 335 
 336         @Override
 337         public String toString() {
 338             return className;
 339         }
 340 
 341         private String className;
 342     }
 343 
 344     /**
 345      * A dependency of one class on another.
 346      */
 347     static class SimpleDependency implements Dependency {
 348         public SimpleDependency(Location origin, Location target) {
 349             this.origin = origin;
 350             this.target = target;
 351         }
 352 
 353         public Location getOrigin() {
 354             return origin;
 355         }
 356 
 357         public Location getTarget() {
 358             return target;
 359         }
 360 
 361         @Override
 362         public boolean equals(Object other) {
 363             if (this == other)
 364                 return true;
 365             if (!(other instanceof SimpleDependency))
 366                 return false;
 367             SimpleDependency o = (SimpleDependency) other;
 368             return (origin.equals(o.origin) && target.equals(o.target));
 369         }
 370 
 371         @Override
 372         public int hashCode() {
 373             return origin.hashCode() * 31 + target.hashCode();
 374         }
 375 
 376         @Override
 377         public String toString() {
 378             return origin + ":" + target;
 379         }
 380 
 381         private Location origin;
 382         private Location target;
 383     }
 384 
 385 
 386     /**
 387      * This class accepts all dependencies.
 388      */
 389     static class DefaultFilter implements Filter {
 390         private static DefaultFilter instance;
 391 
 392         static DefaultFilter instance() {
 393             if (instance == null)
 394                 instance = new DefaultFilter();
 395             return instance;
 396         }
 397 
 398         public boolean accepts(Dependency dependency) {
 399             return true;
 400         }
 401     }
 402 
 403     /**
 404      * This class accepts those dependencies whose target's class name matches a
 405      * regular expression.
 406      */
 407     static class TargetRegexFilter implements Filter {
 408         TargetRegexFilter(Pattern pattern) {
 409             this.pattern = pattern;
 410         }
 411 
 412         public boolean accepts(Dependency dependency) {
 413             return pattern.matcher(dependency.getTarget().getClassName()).matches();
 414         }
 415 
 416         private final Pattern pattern;
 417     }
 418 
 419     /**
 420      * This class accepts those dependencies whose class name is in a given
 421      * package.
 422      */
 423     static class TargetPackageFilter implements Filter {
 424         TargetPackageFilter(Set<String> packageNames, boolean matchSubpackages) {
 425             for (String pn: packageNames) {
 426                 if (pn.length() == 0) // implies null check as well
 427                     throw new IllegalArgumentException();
 428             }
 429             this.packageNames = packageNames;
 430             this.matchSubpackages = matchSubpackages;
 431         }
 432 
 433         public boolean accepts(Dependency dependency) {
 434             String cn = dependency.getTarget().getClassName();
 435             int lastSep = cn.lastIndexOf("/");
 436             String pn = (lastSep == -1 ? "" : cn.substring(0, lastSep));
 437             if (packageNames.contains(pn))
 438                 return true;
 439 
 440             if (matchSubpackages) {
 441                 for (String n: packageNames) {
 442                     if (pn.startsWith(n + "."))
 443                         return true;
 444                 }
 445             }
 446 
 447             return false;
 448         }
 449 
 450         private final Set<String> packageNames;
 451         private final boolean matchSubpackages;
 452     }
 453 
 454 
 455 
 456     /**
 457      * This class identifies class names directly or indirectly in the constant pool.
 458      */
 459     static class ClassDependencyFinder extends BasicDependencyFinder {
 460         public Iterable<? extends Dependency> findDependencies(ClassFile classfile) {
 461             Visitor v = new Visitor(classfile);
 462             for (CPInfo cpInfo: classfile.constant_pool.entries()) {
 463                 v.scan(cpInfo);
 464             }
 465             return v.deps;
 466         }
 467     }
 468 
 469     /**
 470      * This class identifies class names in the signatures of classes, fields,
 471      * and methods in a class.
 472      */
 473     static class APIDependencyFinder extends BasicDependencyFinder {
 474         APIDependencyFinder(int access) {
 475             switch (access) {
 476                 case AccessFlags.ACC_PUBLIC:
 477                 case AccessFlags.ACC_PROTECTED:
 478                 case AccessFlags.ACC_PRIVATE:
 479                 case 0:
 480                     showAccess = access;
 481                     break;
 482                 default:
 483                     throw new IllegalArgumentException("invalid access 0x"
 484                             + Integer.toHexString(access));
 485             }
 486         }
 487 
 488         public Iterable<? extends Dependency> findDependencies(ClassFile classfile) {
 489             try {
 490                 Visitor v = new Visitor(classfile);
 491                 v.addClass(classfile.super_class);
 492                 v.addClasses(classfile.interfaces);
 493                 // inner classes?
 494                 for (Field f : classfile.fields) {
 495                     if (checkAccess(f.access_flags))
 496                         v.scan(f.descriptor, f.attributes);
 497                 }
 498                 for (Method m : classfile.methods) {
 499                     if (checkAccess(m.access_flags)) {
 500                         v.scan(m.descriptor, m.attributes);
 501                         Exceptions_attribute e =
 502                                 (Exceptions_attribute) m.attributes.get(Attribute.Exceptions);
 503                         if (e != null)
 504                             v.addClasses(e.exception_index_table);
 505                     }
 506                 }
 507                 return v.deps;
 508             } catch (ConstantPoolException e) {
 509                 throw new ClassFileError(e);
 510             }
 511         }
 512 
 513         boolean checkAccess(AccessFlags flags) {
 514             // code copied from javap.Options.checkAccess
 515             boolean isPublic = flags.is(AccessFlags.ACC_PUBLIC);
 516             boolean isProtected = flags.is(AccessFlags.ACC_PROTECTED);
 517             boolean isPrivate = flags.is(AccessFlags.ACC_PRIVATE);
 518             boolean isPackage = !(isPublic || isProtected || isPrivate);
 519 
 520             if ((showAccess == AccessFlags.ACC_PUBLIC) && (isProtected || isPrivate || isPackage))
 521                 return false;
 522             else if ((showAccess == AccessFlags.ACC_PROTECTED) && (isPrivate || isPackage))
 523                 return false;
 524             else if ((showAccess == 0) && (isPrivate))
 525                 return false;
 526             else
 527                 return true;
 528         }
 529 
 530         private int showAccess;
 531     }
 532 
 533     static abstract class BasicDependencyFinder implements Finder {
 534         private Map<String,Location> locations = new HashMap<String,Location>();
 535 
 536         Location getLocation(String className) {
 537             Location l = locations.get(className);
 538             if (l == null)
 539                 locations.put(className, l = new SimpleLocation(className));
 540             return l;
 541         }
 542 
 543         class Visitor implements ConstantPool.Visitor<Void,Void>, Type.Visitor<Void, Void> {
 544             private ConstantPool constant_pool;
 545             private Location origin;
 546             Set<Dependency> deps;
 547 
 548             Visitor(ClassFile classFile) {
 549                 try {
 550                     constant_pool = classFile.constant_pool;
 551                     origin = getLocation(classFile.getName());
 552                     deps = new HashSet<Dependency>();
 553                 } catch (ConstantPoolException e) {
 554                     throw new ClassFileError(e);
 555                 }
 556             }
 557 
 558             void scan(Descriptor d, Attributes attrs) {
 559                 try {
 560                     scan(new Signature(d.index).getType(constant_pool));
 561                     Signature_attribute sa = (Signature_attribute) attrs.get(Attribute.Signature);
 562                     if (sa != null)
 563                         scan(new Signature(sa.signature_index).getType(constant_pool));
 564                 } catch (ConstantPoolException e) {
 565                     throw new ClassFileError(e);
 566                 }
 567             }
 568 
 569             void scan(CPInfo cpInfo) {
 570                 cpInfo.accept(this, null);
 571             }
 572 
 573             void scan(Type t) {
 574                 t.accept(this, null);
 575             }
 576 
 577             void addClass(int index) throws ConstantPoolException {
 578                 if (index != 0) {
 579                     String name = constant_pool.getClassInfo(index).getBaseName();
 580                     if (name != null)
 581                         addDependency(name);
 582                 }
 583             }
 584 
 585             void addClasses(int[] indices) throws ConstantPoolException {
 586                 for (int i: indices)
 587                     addClass(i);
 588             }
 589 
 590             private void addDependency(String name) {
 591                 deps.add(new SimpleDependency(origin, getLocation(name)));
 592             }
 593 
 594             // ConstantPool.Visitor methods
 595 
 596             public Void visitClass(CONSTANT_Class_info info, Void p) {
 597                 try {
 598                     if (info.getName().startsWith("["))
 599                         new Signature(info.name_index).getType(constant_pool).accept(this, null);
 600                     else
 601                         addDependency(info.getBaseName());
 602                     return null;
 603                 } catch (ConstantPoolException e) {
 604                     throw new ClassFileError(e);
 605                 }
 606             }
 607 
 608             public Void visitDouble(CONSTANT_Double_info info, Void p) {
 609                 return null;
 610             }
 611 
 612             public Void visitFieldref(CONSTANT_Fieldref_info info, Void p) {
 613                 return visitRef(info, p);
 614             }
 615 
 616             public Void visitFloat(CONSTANT_Float_info info, Void p) {
 617                 return null;
 618             }
 619 
 620             public Void visitInteger(CONSTANT_Integer_info info, Void p) {
 621                 return null;
 622             }
 623 
 624             public Void visitInterfaceMethodref(CONSTANT_InterfaceMethodref_info info, Void p) {
 625                 return visitRef(info, p);
 626             }
 627 
 628             public Void visitInvokeDynamic(CONSTANT_InvokeDynamic_info info, Void p) {
 629                 return null;
 630             }
 631 
 632             public Void visitLong(CONSTANT_Long_info info, Void p) {
 633                 return null;
 634             }
 635 
 636             public Void visitMethodHandle(CONSTANT_MethodHandle_info info, Void p) {
 637                 return null;
 638             }
 639 
 640             public Void visitMethodType(CONSTANT_MethodType_info info, Void p) {
 641                 return null;
 642             }
 643 
 644             public Void visitMethodref(CONSTANT_Methodref_info info, Void p) {
 645                 return visitRef(info, p);
 646             }
 647 
 648             public Void visitNameAndType(CONSTANT_NameAndType_info info, Void p) {
 649                 try {
 650                     new Signature(info.type_index).getType(constant_pool).accept(this, null);
 651                     return null;
 652                 } catch (ConstantPoolException e) {
 653                     throw new ClassFileError(e);
 654                 }
 655             }
 656 
 657             public Void visitString(CONSTANT_String_info info, Void p) {
 658                 return null;
 659             }
 660 
 661             public Void visitUtf8(CONSTANT_Utf8_info info, Void p) {
 662                 return null;
 663             }
 664 
 665             private Void visitRef(CPRefInfo info, Void p) {
 666                 try {
 667                     visitClass(info.getClassInfo(), p);
 668                     return null;
 669                 } catch (ConstantPoolException e) {
 670                     throw new ClassFileError(e);
 671                 }
 672             }
 673 
 674             // Type.Visitor methods
 675 
 676             private void findDependencies(Type t) {
 677                 if (t != null)
 678                     t.accept(this, null);
 679             }
 680 
 681             private void findDependencies(List<? extends Type> ts) {
 682                 if (ts != null) {
 683                     for (Type t: ts)
 684                         t.accept(this, null);
 685                 }
 686             }
 687 
 688             public Void visitSimpleType(SimpleType type, Void p) {
 689                 return null;
 690             }
 691 
 692             public Void visitArrayType(ArrayType type, Void p) {
 693                 findDependencies(type.elemType);
 694                 return null;
 695             }
 696 
 697             public Void visitMethodType(MethodType type, Void p) {
 698                 findDependencies(type.paramTypes);
 699                 findDependencies(type.returnType);
 700                 findDependencies(type.throwsTypes);
 701                 return null;
 702             }
 703 
 704             public Void visitClassSigType(ClassSigType type, Void p) {
 705                 findDependencies(type.superclassType);
 706                 findDependencies(type.superinterfaceTypes);
 707                 return null;
 708             }
 709 
 710             public Void visitClassType(ClassType type, Void p) {
 711                 findDependencies(type.outerType);
 712                 addDependency(type.name);
 713                 findDependencies(type.typeArgs);
 714                 return null;
 715             }
 716 
 717             public Void visitTypeParamType(TypeParamType type, Void p) {
 718                 findDependencies(type.classBound);
 719                 findDependencies(type.interfaceBounds);
 720                 return null;
 721             }
 722 
 723             public Void visitWildcardType(WildcardType type, Void p) {
 724                 findDependencies(type.boundType);
 725                 return null;
 726             }
 727         }
 728     }
 729 }