layoutlib/create/DependencyFinder.java

/*
 * Copyright (C) 2012 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.android.tools.layoutlib.create;

import com.android.tools.layoutlib.annotations.VisibleForTesting;
import com.android.tools.layoutlib.annotations.VisibleForTesting.Visibility;

import org.objectweb.asm.AnnotationVisitor;
import org.objectweb.asm.Attribute;
import org.objectweb.asm.ClassReader;
import org.objectweb.asm.ClassVisitor;
import org.objectweb.asm.FieldVisitor;
import org.objectweb.asm.Label;
import org.objectweb.asm.MethodVisitor;
import org.objectweb.asm.Type;
import org.objectweb.asm.signature.SignatureReader;
import org.objectweb.asm.signature.SignatureVisitor;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Enumeration;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.zip.ZipEntry;
import java.util.zip.ZipFile;

/**
 * Analyzes the input JAR using the ASM java bytecode manipulation library
 * to list the classes and their dependencies. A "dependency" is a class
 * used by another class.
 */
public class DependencyFinder {

    // Note: a bunch of stuff has package-level access for unit tests. Consider it private.

    /** Output logger. */
    private final Log mLog;

    /**
     * Creates a new analyzer.
     *
     * @param log The log output.
     */
    public DependencyFinder(Log log) {
        mLog = log;
    }

    /**
     * Starts the analysis using parameters from the constructor.
     *
     * @param osJarPath The input source JARs to parse.
     * @return A pair: [0]: map { class FQCN => set of FQCN class dependencies }.
     *                 [1]: map { missing class FQCN => set of FQCN class that uses it. }
     */
    public List<Map<String, Set<String>>> findDeps(List<String> osJarPath) throws IOException {

        Map<String, ClassReader> zipClasses = parseZip(osJarPath);
        mLog.info("Found %d classes in input JAR%s.",
                zipClasses.size(),
                osJarPath.size() > 1 ? "s" : "");

        Map<String, Set<String>> deps = findClassesDeps(zipClasses);

        Map<String, Set<String>> missing = findMissingClasses(deps, zipClasses.keySet());

        List<Map<String, Set<String>>> result = new ArrayList<>(2);
        result.add(deps);
        result.add(missing);
        return result;
    }

    /**
     * Prints dependencies to the current logger, found stuff and missing stuff.
     */
    public void printAllDeps(List<Map<String, Set<String>>> result) {
        assert result.size() == 2;
        Map<String, Set<String>> deps = result.get(0);
        Map<String, Set<String>> missing = result.get(1);

        // Print all dependences found in the format:
        // +Found: <FQCN from zip>
        //     uses: FQCN

        mLog.info("++++++ %d Entries found in source JARs", deps.size());
        mLog.info("");

        for (Entry<String, Set<String>> entry : deps.entrySet()) {
            mLog.info(    "+Found  : %s", entry.getKey());
            for (String dep : entry.getValue()) {
                mLog.info("    uses: %s", dep);
            }

            mLog.info("");
        }


        // Now print all missing dependences in the format:
        // -Missing <FQCN>:
        //     used by: <FQCN>

        mLog.info("");
        mLog.info("------ %d Entries missing from source JARs", missing.size());
        mLog.info("");

        for (Entry<String, Set<String>> entry : missing.entrySet()) {
            mLog.info(    "-Missing  : %s", entry.getKey());
            for (String dep : entry.getValue()) {
                mLog.info("   used by: %s", dep);
            }

            mLog.info("");
        }
    }

    /**
     * Prints only a summary of the missing dependencies to the current logger.
     */
    public void printMissingDeps(List<Map<String, Set<String>>> result) {
        assert result.size() == 2;
        @SuppressWarnings("unused") Map<String, Set<String>> deps = result.get(0);
        Map<String, Set<String>> missing = result.get(1);

        for (String fqcn : missing.keySet()) {
            mLog.info("%s", fqcn);
        }
    }

    // ----------------

    /**
     * Parses a JAR file and returns a list of all classes founds using a map
     * class name => ASM ClassReader. Class names are in the form "android.view.View".
     */
    Map<String,ClassReader> parseZip(List<String> jarPathList) throws IOException {
        TreeMap<String, ClassReader> classes = new TreeMap<>();

        for (String jarPath : jarPathList) {
            ZipFile zip = new ZipFile(jarPath);
            Enumeration<? extends ZipEntry> entries = zip.entries();
            ZipEntry entry;
            while (entries.hasMoreElements()) {
                entry = entries.nextElement();
                if (entry.getName().endsWith(".class")) {
                    ClassReader cr = new ClassReader(zip.getInputStream(entry));
                    String className = classReaderToClassName(cr);
                    classes.put(className, cr);
                }
            }
        }

        return classes;
    }

    /**
     * Utility that returns the fully qualified binary class name for a ClassReader.
     * E.g. it returns something like android.view.View.
     */
    static String classReaderToClassName(ClassReader classReader) {
        if (classReader == null) {
            return null;
        } else {
            return classReader.getClassName().replace('/', '.');
        }
    }

    /**
     * Utility that returns the fully qualified binary class name from a path-like FQCN.
     * E.g. it returns android.view.View from android/view/View.
     */
    static String internalToBinaryClassName(String className) {
        if (className == null) {
            return null;
        } else {
            return className.replace('/', '.');
        }
    }

    /**
     * Finds all dependencies for all classes in keepClasses which are also
     * listed in zipClasses. Returns a map of all the dependencies found.
     */
    Map<String, Set<String>> findClassesDeps(Map<String, ClassReader> zipClasses) {

        // The dependencies that we'll collect.
        // It's a map Class name => uses class names.
        Map<String, Set<String>> dependencyMap = new TreeMap<>();

        DependencyVisitor visitor = getVisitor();

        int count = 0;
        try {
            for (Entry<String, ClassReader> entry : zipClasses.entrySet()) {
                String name = entry.getKey();

                TreeSet<String> set = new TreeSet<>();
                dependencyMap.put(name, set);
                visitor.setDependencySet(set);

                ClassReader cr = entry.getValue();
                cr.accept(visitor, 0 /* flags */);

                visitor.setDependencySet(null);

                mLog.debugNoln("Visited %d classes\r", ++count);
            }
        } finally {
            mLog.debugNoln("\n");
        }

        return dependencyMap;
    }

    /**
     * Computes which classes FQCN were found as dependencies that are NOT listed
     * in the original JAR classes.
     *
     * @param deps The map { FQCN => dependencies[] } returned by {@link #findClassesDeps(Map)}.
     * @param zipClasses The set of all classes FQCN found in the JAR files.
     * @return A map { FQCN not found in the zipClasses => classes using it }
     */
    private Map<String, Set<String>> findMissingClasses(
            Map<String, Set<String>> deps,
            Set<String> zipClasses) {
        Map<String, Set<String>> missing = new TreeMap<>();

        for (Entry<String, Set<String>> entry : deps.entrySet()) {
            String name = entry.getKey();

            for (String dep : entry.getValue()) {
                if (!zipClasses.contains(dep)) {
                    // This dependency doesn't exist in the zip classes.
                    Set<String> set = missing.get(dep);
                    if (set == null) {
                        set = new TreeSet<>();
                        missing.put(dep, set);
                    }
                    set.add(name);
                }
            }

        }

        return missing;
    }


    // ----------------------------------

    /**
     * Instantiates a new DependencyVisitor. Useful for unit tests.
     */
    @VisibleForTesting(visibility=Visibility.PRIVATE)
    DependencyVisitor getVisitor() {
        return new DependencyVisitor();
    }

    /**
     * Visitor to collect all the type dependencies from a class.
     */
    public class DependencyVisitor extends ClassVisitor {

        private Set<String> mCurrentDepSet;

        /**
         * Creates a new visitor that will find all the dependencies for the visited class.
         */
        public DependencyVisitor() {
            super(Main.ASM_VERSION);
        }

        /**
         * Sets the {@link Set} where to record direct dependencies for this class.
         * This will change before each {@link ClassReader#accept(ClassVisitor, int)} call.
         */
        public void setDependencySet(Set<String> set) {
            mCurrentDepSet = set;
        }

        /**
         * Considers the given class name as a dependency.
         */
        public void considerName(String className) {
            if (className == null) {
                return;
            }

            className = internalToBinaryClassName(className);

            try {
                // exclude classes that are part of the default JRE (the one executing this program)
                // or in java package (we won't be able to load them anyway).
                if (className.startsWith("java.") ||
                        getClass().getClassLoader().loadClass(className) != null) {
                    return;
                }
            } catch (ClassNotFoundException e) {
                // ignore
            }

            // Add it to the dependency set for the currently visited class, as needed.
            assert mCurrentDepSet != null;
            mCurrentDepSet.add(className);
        }

        /**
         * Considers this array of names using considerName().
         */
        public void considerNames(String[] classNames) {
            if (classNames != null) {
                for (String className : classNames) {
                    considerName(className);
                }
            }
        }

        /**
         * Considers this signature or type signature by invoking the {@link SignatureVisitor}
         * on it.
         */
        public void considerSignature(String signature) {
            if (signature != null) {
                SignatureReader sr = new SignatureReader(signature);
                // SignatureReader.accept will call accessType so we don't really have
                // to differentiate where the signature comes from.
                sr.accept(new MySignatureVisitor());
            }
        }

        /**
         * Considers this {@link Type}. For arrays, the element type is considered.
         * If the type is an object, it's internal name is considered.
         */
        public void considerType(Type t) {
            if (t != null) {
                if (t.getSort() == Type.ARRAY) {
                    t = t.getElementType();
                }
                if (t.getSort() == Type.OBJECT) {
                    considerName(t.getInternalName());
                }
            }
        }

        /**
         * Considers a descriptor string. The descriptor is converted to a {@link Type}
         * and then considerType() is invoked.
         */
        public boolean considerDesc(String desc) {
            if (desc != null) {
                try {
                    if (desc.length() > 0 && desc.charAt(0) == '(') {
                        // This is a method descriptor with arguments and a return type.
                        Type t = Type.getReturnType(desc);
                        considerType(t);

                        for (Type arg : Type.getArgumentTypes(desc)) {
                            considerType(arg);
                        }

                    } else {
                        Type t = Type.getType(desc);
                        considerType(t);
                    }
                    return true;
                } catch (ArrayIndexOutOfBoundsException e) {
                    // ignore, not a valid type.
                }
            }
            return false;
        }


        // ---------------------------------------------------
        // --- ClassVisitor, FieldVisitor
        // ---------------------------------------------------

        // Visits a class header
        @Override
        public void visit(int version, int access, String name,
                String signature, String superName, String[] interfaces) {
            // signature is the signature of this class. May be null if the class is not a generic
            // one, and does not extend or implement generic classes or interfaces.

            if (signature != null) {
                considerSignature(signature);
            }

            // superName is the internal of name of the super class (see getInternalName).
            // For interfaces, the super class is Object. May be null but only for the Object class.
            considerName(superName);

            // interfaces is the internal names of the class's interfaces (see getInternalName).
            // May be null.
            considerNames(interfaces);
        }


        @Override
        public AnnotationVisitor visitAnnotation(String desc, boolean visible) {
            // desc is the class descriptor of the annotation class.
            considerDesc(desc);
            return new MyAnnotationVisitor();
        }

        @Override
        public void visitAttribute(Attribute attr) {
            // pass
        }

        // Visits the end of a class
        @Override
        public void visitEnd() {
            // pass
        }

        private class MyFieldVisitor extends FieldVisitor {

            public MyFieldVisitor() {
                super(Main.ASM_VERSION);
            }

            @Override
            public AnnotationVisitor visitAnnotation(String desc, boolean visible) {
                // desc is the class descriptor of the annotation class.
                considerDesc(desc);
                return new MyAnnotationVisitor();
            }

            @Override
            public void visitAttribute(Attribute attr) {
                // pass
            }

            // Visits the end of a class
            @Override
            public void visitEnd() {
                // pass
            }
        }

        @Override
        public FieldVisitor visitField(int access, String name, String desc,
                String signature, Object value) {
            // desc is the field's descriptor (see Type).
            considerDesc(desc);

            // signature is the field's signature. May be null if the field's type does not use
            // generic types.
            considerSignature(signature);

            return new MyFieldVisitor();
        }

        @Override
        public void visitInnerClass(String name, String outerName, String innerName, int access) {
            // name is the internal name of an inner class (see getInternalName).
            // Note: outerName/innerName seems to be null when we're reading the
            // _Original_ClassName classes generated by layoutlib_create.
            if (outerName != null) {
                considerName(name);
            }
        }

        @Override
        public MethodVisitor visitMethod(int access, String name, String desc,
                String signature, String[] exceptions) {
            // desc is the method's descriptor (see Type).
            considerDesc(desc);
            // signature is the method's signature. May be null if the method parameters, return
            // type and exceptions do not use generic types.
            considerSignature(signature);

            return new MyMethodVisitor();
        }

        @Override
        public void visitOuterClass(String owner, String name, String desc) {
            // pass
        }

        @Override
        public void visitSource(String source, String debug) {
            // pass
        }


        // ---------------------------------------------------
        // --- MethodVisitor
        // ---------------------------------------------------

        private class MyMethodVisitor extends MethodVisitor {

            public MyMethodVisitor() {
                super(Main.ASM_VERSION);
            }


            @Override
            public AnnotationVisitor visitAnnotationDefault() {
                return new MyAnnotationVisitor();
            }

            @Override
            public void visitCode() {
                // pass
            }

            // field instruction
            @Override
            public void visitFieldInsn(int opcode, String owner, String name, String desc) {
                // owner is the class that declares the field.
                considerName(owner);
                // desc is the field's descriptor (see Type).
                considerDesc(desc);
            }

            @Override
            public void visitFrame(int type, int local, Object[] local2, int stack, Object[] stack2) {
                // pass
            }

            @Override
            public void visitIincInsn(int var, int increment) {
                // pass -- an IINC instruction
            }

            @Override
            public void visitInsn(int opcode) {
                // pass -- a zero operand instruction
            }

            @Override
            public void visitIntInsn(int opcode, int operand) {
                // pass -- a single int operand instruction
            }

            @Override
            public void visitJumpInsn(int opcode, Label label) {
                // pass -- a jump instruction
            }

            @Override
            public void visitLabel(Label label) {
                // pass -- a label target
            }

            // instruction to load a constant from the stack
            @Override
            public void visitLdcInsn(Object cst) {
                if (cst instanceof Type) {
                    considerType((Type) cst);
                }
            }

            @Override
            public void visitLineNumber(int line, Label start) {
                // pass
            }

            @Override
            public void visitLocalVariable(String name, String desc,
                    String signature, Label start, Label end, int index) {
                // desc is the type descriptor of this local variable.
                considerDesc(desc);
                // signature is the type signature of this local variable. May be null if the local
                // variable type does not use generic types.
                considerSignature(signature);
            }

            @Override
            public void visitLookupSwitchInsn(Label dflt, int[] keys, Label[] labels) {
                // pass -- a lookup switch instruction
            }

            @Override
            public void visitMaxs(int maxStack, int maxLocals) {
                // pass
            }

            // instruction that invokes a method
            @Override
            public void visitMethodInsn(int opcode, String owner, String name, String desc,
                    boolean itf) {

                // owner is the internal name of the method's owner class
                if (!considerDesc(owner) && owner.indexOf('/') != -1) {
                    considerName(owner);
                }
                // desc is the method's descriptor (see Type).
                considerDesc(desc);
            }

            // instruction multianewarray, whatever that is
            @Override
            public void visitMultiANewArrayInsn(String desc, int dims) {

                // desc an array type descriptor.
                considerDesc(desc);
            }

            @Override
            public AnnotationVisitor visitParameterAnnotation(int parameter, String desc,
                    boolean visible) {
                // desc is the class descriptor of the annotation class.
                considerDesc(desc);
                return new MyAnnotationVisitor();
            }

            @Override
            public void visitTableSwitchInsn(int min, int max, Label dflt, Label[] labels) {
                // pass -- table switch instruction

            }

            @Override
            public void visitTryCatchBlock(Label start, Label end, Label handler, String type) {
                // type is the internal name of the type of exceptions handled by the handler,
                // or null to catch any exceptions (for "finally" blocks).
                considerName(type);
            }

            // type instruction
            @Override
            public void visitTypeInsn(int opcode, String type) {
                // type is the operand of the instruction to be visited. This operand must be the
                // internal name of an object or array class.
                considerName(type);
            }

            @Override
            public void visitVarInsn(int opcode, int var) {
                // pass -- local variable instruction
            }
        }

        private class MySignatureVisitor extends SignatureVisitor {

            public MySignatureVisitor() {
                super(Main.ASM_VERSION);
            }

            // ---------------------------------------------------
            // --- SignatureVisitor
            // ---------------------------------------------------

            private String mCurrentSignatureClass = null;

            // Starts the visit of a signature corresponding to a class or interface type
            @Override
            public void visitClassType(String name) {
                mCurrentSignatureClass = name;
                considerName(name);
            }

            // Visits an inner class
            @Override
            public void visitInnerClassType(String name) {
                if (mCurrentSignatureClass != null) {
                    mCurrentSignatureClass += "$" + name;
                    considerName(mCurrentSignatureClass);
                }
            }

            @Override
            public SignatureVisitor visitArrayType() {
                return new MySignatureVisitor();
            }

            @Override
            public void visitBaseType(char descriptor) {
                // pass -- a primitive type, ignored
            }

            @Override
            public SignatureVisitor visitClassBound() {
                return new MySignatureVisitor();
            }

            @Override
            public SignatureVisitor visitExceptionType() {
                return new MySignatureVisitor();
            }

            @Override
            public void visitFormalTypeParameter(String name) {
                // pass
            }

            @Override
            public SignatureVisitor visitInterface() {
                return new MySignatureVisitor();
            }

            @Override
            public SignatureVisitor visitInterfaceBound() {
                return new MySignatureVisitor();
            }

            @Override
            public SignatureVisitor visitParameterType() {
                return new MySignatureVisitor();
            }

            @Override
            public SignatureVisitor visitReturnType() {
                return new MySignatureVisitor();
            }

            @Override
            public SignatureVisitor visitSuperclass() {
                return new MySignatureVisitor();
            }

            @Override
            public SignatureVisitor visitTypeArgument(char wildcard) {
                return new MySignatureVisitor();
            }

            @Override
            public void visitTypeVariable(String name) {
                // pass
            }

            @Override
            public void visitTypeArgument() {
                // pass
            }
        }


        // ---------------------------------------------------
        // --- AnnotationVisitor
        // ---------------------------------------------------

        private class MyAnnotationVisitor extends AnnotationVisitor {

            public MyAnnotationVisitor() {
                super(Main.ASM_VERSION);
            }

            // Visits a primitive value of an annotation
            @Override
            public void visit(String name, Object value) {
                // value is the actual value, whose type must be Byte, Boolean, Character, Short,
                // Integer, Long, Float, Double, String or Type
                if (value instanceof Type) {
                    considerType((Type) value);
                }
            }

            @Override
            public AnnotationVisitor visitAnnotation(String name, String desc) {
                // desc is the class descriptor of the nested annotation class.
                considerDesc(desc);
                return new MyAnnotationVisitor();
            }

            @Override
            public AnnotationVisitor visitArray(String name) {
                return new MyAnnotationVisitor();
            }

            @Override
            public void visitEnum(String name, String desc, String value) {
                // desc is the class descriptor of the enumeration class.
                considerDesc(desc);
            }
        }
    }
}