1 /*

     2  * Copyright 2009 Sun Microsystems, Inc.  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.  Sun designates this

     8  * particular file as subject to the "Classpath" exception as provided

     9  * by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

    22  * CA 95054 USA or visit www.sun.com if you need additional information or

    23  * have any 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.Finder;

    37 import com.sun.tools.classfile.Dependency.Filter;

    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 

    47 import static com.sun.tools.classfile.ConstantPool.*;

    48 

    49 /**

    50  * A framework for determining {@link Dependency dependencies} between class files.

    51  *

    52  * A {@link Dependency.Finder finder} is used to identify the dependencies of

    53  * individual classes. Some finders may return subtypes of {@code Dependency} to

    54  * further characterize the type of dependency, such as a dependency on a

    55  * method within a class.

    56  *

    57  * A {@link Dependency.Filter filter} may be used to restrict the set of

    58  * dependencies found by a finder.

    59  *

    60  * Dependencies that are found may be passed to a {@link Dependencies.Recorder

    61  * recorder} so that the dependencies can be stored in a custom data structure.

    62  */

    63 public class Dependencies {

    64     /**

    65      * Thrown when a class file cannot be found.

    66      */

    67     public static class ClassFileNotFoundException extends Exception {

    68         private static final long serialVersionUID = 3632265927794475048L;

    69 

    70         public ClassFileNotFoundException(String className) {

    71             super(className);

    72             this.className = className;

    73         }

    74 

    75         public ClassFileNotFoundException(String className, Throwable cause) {

    76             this(className);

    77             initCause(cause);

    78         }

    79 

    80         public final String className;

    81     }

    82 

    83     /**

    84      * Thrown when an exception is found processing a class file.

    85      */

    86     public static class ClassFileError extends Error {

    87         private static final long serialVersionUID = 4111110813961313203L;

    88 

    89         public ClassFileError(Throwable cause) {

    90             initCause(cause);

    91         }

    92     }

    93 

    94     /**

    95      * Service provider interface to locate and read class files.

    96      */

    97     public interface ClassFileReader {

    98         /**

    99          * Get the ClassFile object for a specified class.

   100          * @param className the name of the class to be returned.

   101          * @return the ClassFile for the given class

   102          * @throws Dependencies#ClassFileNotFoundException if the classfile cannot be

   103          *   found

   104          */

   105         public ClassFile getClassFile(String className)

   106                 throws ClassFileNotFoundException;

   107     }

   108 

   109     /**

   110      * Service provide interface to handle results.

   111      */

   112     public interface Recorder {

   113         /**

   114          * Record a dependency that has been found.

   115          * @param d

   116          */

   117         public void addDependency(Dependency d);

   118     }

   119 

   120     /**

   121      * Get the  default finder used to locate the dependencies for a class.

   122      * @return the default finder

   123      */

   124     public static Finder getDefaultFinder() {

   125         return new APIDependencyFinder(AccessFlags.ACC_PRIVATE);

   126     }

   127 

   128     /**

   129      * Get a finder used to locate the API dependencies for a class.

   130      * These include the superclass, superinterfaces, and classes referenced in

   131      * the declarations of fields and methods.  The fields and methods that

   132      * are checked can be limited according to a specified access.

   133      * The access parameter must be one of {@link AccessFlags#ACC_PUBLIC ACC_PUBLIC},

   134      * {@link AccessFlags#ACC_PRIVATE ACC_PRIVATE},

   135      * {@link AccessFlags#ACC_PROTECTED ACC_PROTECTED}, or 0 for

   136      * package private access. Members with greater than or equal accessibility

   137      * to that specified will be searched for dependencies.

   138      * @param access the access of members to be checked

   139      * @return an API finder

   140      */

   141     public static Finder getAPIFinder(int access) {

   142         return new APIDependencyFinder(access);

   143     }

   144 

   145     /**

   146      * Get the finder used to locate the dependencies for a class.

   147      * @return the finder

   148      */

   149     public Finder getFinder() {

   150         if (finder == null)

   151             finder = getDefaultFinder();

   152         return finder;

   153     }

   154 

   155     /**

   156      * Set the finder used to locate the dependencies for a class.

   157      * @param f the finder

   158      */

   159     public void setFinder(Finder f) {

   160         f.getClass(); // null check

   161         finder = f;

   162     }

   163 

   164     /**

   165      * Get the default filter used to determine included when searching

   166      * the transitive closure of all the dependencies.

   167      * Unless overridden, the default filter accepts all dependencies.

   168      * @return the default filter.

   169      */

   170     public static Filter getDefaultFilter() {

   171         return DefaultFilter.instance();

   172     }

   173 

   174     /**

   175      * Get a filter which uses a regular expression on the target's class name

   176      * to determine if a dependency is of interest.

   177      * @param pattern the pattern used to match the target's class name

   178      * @return a filter for matching the target class name with a regular expression

   179      */

   180     public static Filter getRegexFilter(Pattern pattern) {

   181         return new TargetRegexFilter(pattern);

   182     }

   183 

   184     /**

   185      * Get a filter which checks the package of a target's class name

   186      * to determine if a dependency is of interest. The filter checks if the

   187      * package of the target's class matches any of a set of given package

   188      * names. The match may optionally match subpackages of the given names as well.

   189      * @param packageNames the package names used to match the target's class name

   190      * @param matchSubpackages whether or not to match subpackages as well

   191      * @return a filter for checking the target package name against a list of package names

   192      */

   193     public static Filter getPackageFilter(Set<String> packageNames, boolean matchSubpackages) {

   194         return new TargetPackageFilter(packageNames, matchSubpackages);

   195     }

   196 

   197     /**

   198      * Get the filter used to determine the dependencies included when searching

   199      * the transitive closure of all the dependencies.

   200      * Unless overridden, the default filter accepts all dependencies.

   201      * @return the filter

   202      */

   203     public Filter getFilter() {

   204         if (filter == null)

   205             filter = getDefaultFilter();

   206         return filter;

   207     }

   208 

   209     /**

   210      * Set the filter used to determine the dependencies included when searching

   211      * the transitive closure of all the dependencies.

   212      * @param f the filter

   213      */

   214     public void setFilter(Filter f) {

   215         f.getClass(); // null check

   216         filter = f;

   217     }

   218 

   219     /**

   220      * Find the dependencies of a class, using the current

   221      * {@link Dependencies#getFinder finder} and

   222      * {@link Dependencies#getFilter filter}.

   223      * The search may optionally include the transitive closure of all the

   224      * filtered dependencies, by also searching in the classes named in those

   225      * dependencies.

   226      * @param classFinder a finder to locate class files

   227      * @param rootClassNames the names of the root classes from which to begin

   228      *      searching

   229      * @param transitiveClosure whether or not to also search those classes

   230      *      named in any filtered dependencies that are found.

   231      * @return the set of dependencies that were found

   232      * @throws ClassFileNotFoundException if a required class file cannot be found

   233      * @throws ClassFileError if an error occurs while processing a class file,

   234      *      such as an error in the internal class file structure.

   235      */

   236     public Set<Dependency> findAllDependencies(

   237             ClassFileReader classFinder, Set<String> rootClassNames,

   238             boolean transitiveClosure)

   239             throws ClassFileNotFoundException {

   240         final Set<Dependency> results = new HashSet<Dependency>();

   241         Recorder r = new Recorder() {

   242             public void addDependency(Dependency d) {

   243                 results.add(d);

   244             }

   245         };

   246         findAllDependencies(classFinder, rootClassNames, transitiveClosure, r);

   247         return results;

   248     }

   249 

   250 

   251 

   252     /**

   253      * Find the dependencies of a class, using the current

   254      * {@link Dependencies#getFinder finder} and

   255      * {@link Dependencies#getFilter filter}.

   256      * The search may optionally include the transitive closure of all the

   257      * filtered dependencies, by also searching in the classes named in those

   258      * dependencies.

   259      * @param classFinder a finder to locate class files

   260      * @param rootClassNames the names of the root classes from which to begin

   261      *      searching

   262      * @param transitiveClosure whether or not to also search those classes

   263      *      named in any filtered dependencies that are found.

   264      * @param recorder a recorder for handling the results

   265      * @throws ClassFileNotFoundException if a required class file cannot be found

   266      * @throws ClassFileError if an error occurs while processing a class file,

   267      *      such as an error in the internal class file structure.

   268      */

   269     public void findAllDependencies(

   270             ClassFileReader classFinder, Set<String> rootClassNames,

   271             boolean transitiveClosure, Recorder recorder)

   272             throws ClassFileNotFoundException {

   273         Set<String> doneClasses = new HashSet<String>();

   274 

   275         getFinder();  // ensure initialized

   276         getFilter();  // ensure initialized

   277 

   278         // Work queue of names of classfiles to be searched.

   279         // Entries will be unique, and for classes that do not yet have

   280         // dependencies in the results map.

   281         Deque<String> deque = new LinkedList<String>(rootClassNames);

   282 

   283         String className;

   284         while ((className = deque.poll()) != null) {

   285             assert (!doneClasses.contains(className));

   286             doneClasses.add(className);

   287 

   288             ClassFile cf = classFinder.getClassFile(className);

   289 

   290             // The following code just applies the filter to the dependencies

   291             // followed for the transitive closure.

   292             for (Dependency d: finder.findDependencies(cf)) {

   293                 recorder.addDependency(d);

   294                 if (transitiveClosure && filter.accepts(d)) {

   295                     String cn = d.getTarget().getClassName();

   296                     if (!doneClasses.contains(cn))

   297                         deque.add(cn);

   298                 }

   299             }

   300         }

   301     }

   302 

   303     private Filter filter;

   304     private Finder finder;

   305 

   306     /**

   307      * A location identifying a class.

   308      */

   309     static class SimpleLocation implements Location {

   310         public SimpleLocation(String className) {

   311             this.className = className;

   312         }

   313 

   314         /**

   315          * Get the name of the class being depended on. This name will be used to

   316          * locate the class file for transitive dependency analysis.

   317          * @return the name of the class being depended on

   318          */

   319         public String getClassName() {

   320             return className;

   321         }

   322 

   323         @Override

   324         public boolean equals(Object other) {

   325             if (this == other)

   326                 return true;

   327             if (!(other instanceof SimpleLocation))

   328                 return false;

   329             return (className.equals(((SimpleLocation) other).className));

   330         }

   331 

   332         @Override

   333         public int hashCode() {

   334             return className.hashCode();

   335         }

   336 

   337         @Override

   338         public String toString() {

   339             return className;

   340         }

   341 

   342         private String className;

   343     }

   344 

   345     /**

   346      * A dependency of one class on another.

   347      */

   348     static class SimpleDependency implements Dependency {

   349         public SimpleDependency(Location origin, Location target) {

   350             this.origin = origin;

   351             this.target = target;

   352         }

   353 

   354         public Location getOrigin() {

   355             return origin;

   356         }

   357 

   358         public Location getTarget() {

   359             return target;

   360         }

   361 

   362         @Override

   363         public boolean equals(Object other) {

   364             if (this == other)

   365                 return true;

   366             if (!(other instanceof SimpleDependency))

   367                 return false;

   368             SimpleDependency o = (SimpleDependency) other;

   369             return (origin.equals(o.origin) && target.equals(o.target));

   370         }

   371 

   372         @Override

   373         public int hashCode() {

   374             return origin.hashCode() * 31 + target.hashCode();

   375         }

   376 

   377         @Override

   378         public String toString() {

   379             return origin + ":" + target;

   380         }

   381 

   382         private Location origin;

   383         private Location target;

   384     }

   385 

   386 

   387     /**

   388      * This class accepts all dependencies.

   389      */

   390     static class DefaultFilter implements Filter {

   391         private static DefaultFilter instance;

   392 

   393         static DefaultFilter instance() {

   394             if (instance == null)

   395                 instance = new DefaultFilter();

   396             return instance;

   397         }

   398 

   399         public boolean accepts(Dependency dependency) {

   400             return true;

   401         }

   402     }

   403 

   404     /**

   405      * This class accepts those dependencies whose target's class name matches a

   406      * regular expression.

   407      */

   408     static class TargetRegexFilter implements Filter {

   409         TargetRegexFilter(Pattern pattern) {

   410             this.pattern = pattern;

   411         }

   412 

   413         public boolean accepts(Dependency dependency) {

   414             return pattern.matcher(dependency.getTarget().getClassName()).matches();

   415         }

   416 

   417         Pattern pattern;

   418     }

   419 

   420     /**

   421      * This class accepts those dependencies whose class name is in a given

   422      * package.

   423      */

   424     static class TargetPackageFilter implements Filter {

   425         TargetPackageFilter(Set<String> packageNames, boolean matchSubpackages) {

   426             for (String pn: packageNames) {

   427                 if (pn.length() == 0) // implies null check as well

   428                     throw new IllegalArgumentException();

   429             }

   430             this.packageNames = packageNames;

   431             this.matchSubpackages = matchSubpackages;

   432         }

   433 

   434         public boolean accepts(Dependency dependency) {

   435             String cn = dependency.getTarget().getClassName();

   436             int lastSep = cn.lastIndexOf("/");

   437             String pn = (lastSep == -1 ? "" : cn.substring(0, lastSep));

   438             if (packageNames.contains(pn))

   439                 return true;

   440 

   441             if (matchSubpackages) {

   442                 for (String n: packageNames) {

   443                     if (pn.startsWith(n + "."))

   444                         return true;

   445                 }

   446             }

   447 

   448             return false;

   449         }

   450 

   451         Set<String> packageNames;

   452         boolean matchSubpackages;

   453     }

   454 

   455 

   456 

   457     /**

   458      * This class identifies class names directly or indirectly in the constant pool.

   459      */

   460     static class ClassDependencyFinder extends BasicDependencyFinder {

   461         public Iterable<? extends Dependency> findDependencies(ClassFile classfile) {

   462             Visitor v = new Visitor(classfile);

   463             for (CPInfo cpInfo: classfile.constant_pool.entries()) {

   464                 v.scan(cpInfo);

   465             }

   466             return v.deps;

   467         }

   468     }

   469 

   470     /**

   471      * This class identifies class names in the signatures of classes, fields,

   472      * and methods in a class.

   473      */

   474     static class APIDependencyFinder extends BasicDependencyFinder {

   475         APIDependencyFinder(int access) {

   476             switch (access) {

   477                 case AccessFlags.ACC_PUBLIC:

   478                 case AccessFlags.ACC_PROTECTED:

   479                 case AccessFlags.ACC_PRIVATE:

   480                 case 0:

   481                     showAccess = access;

   482                     break;

   483                 default:

   484                     throw new IllegalArgumentException("invalid access 0x"

   485                             + Integer.toHexString(access));

   486             }

   487         }

   488 

   489         public Iterable<? extends Dependency> findDependencies(ClassFile classfile) {

   490             try {

   491                 Visitor v = new Visitor(classfile);

   492                 v.addClass(classfile.super_class);

   493                 v.addClasses(classfile.interfaces);

   494                 // inner classes?

   495                 for (Field f : classfile.fields) {

   496                     if (checkAccess(f.access_flags))

   497                         v.scan(f.descriptor, f.attributes);

   498                 }

   499                 for (Method m : classfile.methods) {

   500                     if (checkAccess(m.access_flags)) {

   501                         v.scan(m.descriptor, m.attributes);

   502                         Exceptions_attribute e =

   503                                 (Exceptions_attribute) m.attributes.get(Attribute.Exceptions);

   504                         if (e != null)

   505                             v.addClasses(e.exception_index_table);

   506                     }

   507                 }

   508                 return v.deps;

   509             } catch (ConstantPoolException e) {

   510                 throw new ClassFileError(e);

   511             }

   512         }

   513 

   514         boolean checkAccess(AccessFlags flags) {

   515             // code copied from javap.Options.checkAccess

   516             boolean isPublic = flags.is(AccessFlags.ACC_PUBLIC);

   517             boolean isProtected = flags.is(AccessFlags.ACC_PROTECTED);

   518             boolean isPrivate = flags.is(AccessFlags.ACC_PRIVATE);

   519             boolean isPackage = !(isPublic || isProtected || isPrivate);

   520 

   521             if ((showAccess == AccessFlags.ACC_PUBLIC) && (isProtected || isPrivate || isPackage))

   522                 return false;

   523             else if ((showAccess == AccessFlags.ACC_PROTECTED) && (isPrivate || isPackage))

   524                 return false;

   525             else if ((showAccess == 0) && (isPrivate))

   526                 return false;

   527             else

   528                 return true;

   529         }

   530 

   531         private int showAccess;

   532     }

   533 

   534     static abstract class BasicDependencyFinder implements Finder {

   535         private Map<String,Location> locations = new HashMap<String,Location>();

   536 

   537         Location getLocation(String className) {

   538             Location l = locations.get(className);

   539             if (l == null)

   540                 locations.put(className, l = new SimpleLocation(className));

   541             return l;

   542         }

   543 

   544         class Visitor implements ConstantPool.Visitor<Void,Void>, Type.Visitor<Void, Void> {

   545             private ConstantPool constant_pool;

   546             private Set<Dependency> deps;

   547             private Location origin;

   548 

   549             Visitor(ClassFile classFile) {

   550                 try {

   551                     constant_pool = classFile.constant_pool;

   552                     origin = getLocation(classFile.getName());

   553                     deps = new HashSet<Dependency>();

   554                 } catch (ConstantPoolException e) {

   555                     throw new ClassFileError(e);

   556                 }

   557             }

   558 

   559             void scan(Descriptor d, Attributes attrs) {

   560                 try {

   561                     scan(new Signature(d.index).getType(constant_pool));

   562                     Signature_attribute sa = (Signature_attribute) attrs.get(Attribute.Signature);

   563                     if (sa != null)

   564                         scan(new Signature(sa.signature_index).getType(constant_pool));

   565                 } catch (ConstantPoolException e) {

   566                     throw new ClassFileError(e);

   567                 }

   568             }

   569 

   570             void scan(CPInfo cpInfo) {

   571                 cpInfo.accept(this, null);

   572             }

   573 

   574             void scan(Type t) {

   575                 t.accept(this, null);

   576             }

   577 

   578             void addClass(int index) throws ConstantPoolException {

   579                 if (index != 0) {

   580                     String name = constant_pool.getClassInfo(index).getBaseName();

   581                     if (name != null)

   582                         addDependency(name);

   583                 }

   584             }

   585 

   586             void addClasses(int[] indices) throws ConstantPoolException {

   587                 for (int i: indices)

   588                     addClass(i);

   589             }

   590 

   591             private void addDependency(String name) {

   592                 deps.add(new SimpleDependency(origin, getLocation(name)));

   593             }

   594 

   595             // ConstantPool.Visitor methods

   596 

   597             public Void visitClass(CONSTANT_Class_info info, Void p) {

   598                 try {

   599                     if (info.getName().startsWith("["))

   600                         new Signature(info.name_index).getType(constant_pool).accept(this, null);

   601                     else

   602                         addDependency(info.getBaseName());

   603                     return null;

   604                 } catch (ConstantPoolException e) {

   605                     throw new ClassFileError(e);

   606                 }

   607             }

   608 

   609             public Void visitDouble(CONSTANT_Double_info info, Void p) {

   610                 return null;

   611             }

   612 

   613             public Void visitFieldref(CONSTANT_Fieldref_info info, Void p) {

   614                 return visitRef(info, p);

   615             }

   616 

   617             public Void visitFloat(CONSTANT_Float_info info, Void p) {

   618                 return null;

   619             }

   620 

   621             public Void visitInteger(CONSTANT_Integer_info info, Void p) {

   622                 return null;

   623             }

   624 

   625             public Void visitInterfaceMethodref(CONSTANT_InterfaceMethodref_info info, Void p) {

   626                 return visitRef(info, p);

   627             }

   628 

   629             public Void visitLong(CONSTANT_Long_info info, Void p) {

   630                 return null;

   631             }

   632 

   633             public Void visitNameAndType(CONSTANT_NameAndType_info info, Void p) {

   634                 try {

   635                     new Signature(info.type_index).getType(constant_pool).accept(this, null);

   636                     return null;

   637                 } catch (ConstantPoolException e) {

   638                     throw new ClassFileError(e);

   639                 }

   640             }

   641 

   642             public Void visitMethodref(CONSTANT_Methodref_info info, Void p) {

   643                 return visitRef(info, p);

   644             }

   645 

   646             public Void visitString(CONSTANT_String_info info, Void p) {

   647                 return null;

   648             }

   649 

   650             public Void visitUtf8(CONSTANT_Utf8_info info, Void p) {

   651                 return null;

   652             }

   653 

   654             private Void visitRef(CPRefInfo info, Void p) {

   655                 try {

   656                     visitClass(info.getClassInfo(), p);

   657                     return null;

   658                 } catch (ConstantPoolException e) {

   659                     throw new ClassFileError(e);

   660                 }

   661             }

   662 

   663             // Type.Visitor methods

   664 

   665             private void findDependencies(Type t) {

   666                 if (t != null)

   667                     t.accept(this, null);

   668             }

   669 

   670             private void findDependencies(List<? extends Type> ts) {

   671                 if (ts != null) {

   672                     for (Type t: ts)

   673                         t.accept(this, null);

   674                 }

   675             }

   676 

   677             public Void visitSimpleType(SimpleType type, Void p) {

   678                 return null;

   679             }

   680 

   681             public Void visitArrayType(ArrayType type, Void p) {

   682                 findDependencies(type.elemType);

   683                 return null;

   684             }

   685 

   686             public Void visitMethodType(MethodType type, Void p) {

   687                 findDependencies(type.paramTypes);

   688                 findDependencies(type.returnType);

   689                 findDependencies(type.throwsTypes);

   690                 return null;

   691             }

   692 

   693             public Void visitClassSigType(ClassSigType type, Void p) {

   694                 findDependencies(type.superclassType);

   695                 findDependencies(type.superinterfaceTypes);

   696                 return null;

   697             }

   698 

   699             public Void visitClassType(ClassType type, Void p) {

   700                 findDependencies(type.outerType);

   701                 addDependency(type.name);

   702                 findDependencies(type.typeArgs);

   703                 return null;

   704             }

   705 

   706             public Void visitTypeParamType(TypeParamType type, Void p) {

   707                 findDependencies(type.classBound);

   708                 findDependencies(type.interfaceBounds);

   709                 return null;

   710             }

   711 

   712             public Void visitWildcardType(WildcardType type, Void p) {

   713                 findDependencies(type.boundType);

   714                 return null;

   715             }

   716         }

   717     }

   718 }