/*
 * Copyright 2003-2004 Sun Microsystems, Inc.  All Rights Reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
 * CA 95054 USA or visit www.sun.com if you need additional information or
 * have any questions.
 *
 */

import java.io.*;
import java.util.*;


/**
<p> This class finds transitive closure of dependencies from a given
root set of classes. If your project has lots of .class files and you
want to ship only those .class files which are used (transitively)
from a root set of classes, then you can use this utility.  </p> <p>
How does it work?</p>

<p> We walk through all constant pool entries of a given class and
find all modified UTF-8 entries. Anything that looks like a class name is
considered as a class and we search for that class in the given
classpath. If we find a .class of that name, then we add that class to
list.</p>

<p> We could have used CONSTANT_ClassInfo type constants only. But
that will miss classes used through Class.forName or xyz.class
construct.  But, if you refer to a class name in some other string we
would include it as dependency :(. But this is quite unlikely
anyway. To look for exact Class.forName argument(s) would involve
bytecode analysis. Also, we handle only simple reflection. If you
accept name of a class from externally (for eg properties file or
command line args for example, this utility will not be able to find
that dependency. In such cases, include those classes in the root set.
</p>
*/

public class ClosureFinder {
    private Collection roots;            // root class names Collection<String>
    private Map        visitedClasses;   // set of all dependencies as a Map
    private String     classPath;        // classpath to look for .class files
    private String[]   pathComponents;   // classpath components
    private static final boolean isWindows = File.separatorChar != '/';

    public ClosureFinder(Collection roots, String classPath) {
        this.roots = roots;
        this.classPath = classPath;
        parseClassPath();
    }

    // parse classPath into pathComponents array
    private void parseClassPath() {
        List paths = new ArrayList();
        StringTokenizer st = new StringTokenizer(classPath, File.pathSeparator);
        while (st.hasMoreTokens())
            paths.add(st.nextToken());

        Object[] arr = paths.toArray();
        pathComponents = new String[arr.length];
        System.arraycopy(arr, 0, pathComponents, 0, arr.length);
    }

    // if output is aleady not computed, compute it now
    // result is a map from class file name to base path where the .class was found
    public Map find() {
        if (visitedClasses == null) {
            visitedClasses = new HashMap();
            computeClosure();
        }
        return visitedClasses;
    }

    // compute closure for all given root classes
    private void computeClosure() {
        for (Iterator rootsItr = roots.iterator(); rootsItr.hasNext();) {
            String name = (String) rootsItr.next();
            name = name.substring(0, name.indexOf(".class"));
            computeClosure(name);
        }
    }


    // looks up for .class in pathComponents and returns
    // base path if found, else returns null
    private String lookupClassFile(String classNameAsPath) {
        for (int i = 0; i < pathComponents.length; i++) {
            File f =  new File(pathComponents[i] + File.separator +
                               classNameAsPath + ".class");
            if (f.exists()) {
                if (isWindows) {
                    String name = f.getName();
                    // Windows reports special devices AUX,NUL,CON as files
                    // under any directory. It does not care about file extention :-(
                    if (name.compareToIgnoreCase("AUX.class") == 0 ||
                        name.compareToIgnoreCase("NUL.class") == 0 ||
                        name.compareToIgnoreCase("CON.class") == 0) {
                        return null;
                    }
                }
                return pathComponents[i];
            }
        }
        return null;
    }


    // from JVM spec. 2'nd edition section 4.4
    private static final int CONSTANT_Class = 7;
    private static final int CONSTANT_FieldRef = 9;
    private static final int CONSTANT_MethodRef = 10;
    private static final int CONSTANT_InterfaceMethodRef = 11;
    private static final int CONSTANT_String = 8;
    private static final int CONSTANT_Integer = 3;
    private static final int CONSTANT_Float = 4;
    private static final int CONSTANT_Long = 5;
    private static final int CONSTANT_Double = 6;
    private static final int CONSTANT_NameAndType = 12;
    private static final int CONSTANT_Utf8 = 1;

    // whether a given string may be a class name?
    private boolean mayBeClassName(String internalClassName) {
        int len = internalClassName.length();
        for (int s = 0; s < len; s++) {
            char c = internalClassName.charAt(s);
            if (!Character.isJavaIdentifierPart(c) && c != '/')
                return false;
        }
        return true;
    }

    // compute closure for a given class
    private void computeClosure(String className) {
        if (visitedClasses.get(className) != null) return;
        String basePath = lookupClassFile(className);
        if (basePath != null) {
            visitedClasses.put(className, basePath);
            try {
                File classFile = new File(basePath + File.separator + className + ".class");
                FileInputStream fis = new FileInputStream(classFile);
                DataInputStream dis = new DataInputStream(fis);
                // look for .class signature
                if (dis.readInt() != 0xcafebabe) {
                    System.err.println(classFile.getAbsolutePath() + " is not a valid .class file");
                    return;
                }

                // ignore major and minor version numbers
                dis.readShort();
                dis.readShort();

                // read number of constant pool constants
                int numConsts = (int) dis.readShort();
                String[] strings = new String[numConsts];

                // zero'th entry is unused
                for (int cpIndex = 1; cpIndex < numConsts; cpIndex++) {
                    int constType = (int) dis.readByte();
                    switch (constType) {
                    case CONSTANT_Class:
                    case CONSTANT_String:
                        dis.readShort(); // string name index;
                        break;

                    case CONSTANT_FieldRef:
                    case CONSTANT_MethodRef:
                    case CONSTANT_InterfaceMethodRef:
                    case CONSTANT_NameAndType:
                    case CONSTANT_Integer:
                    case CONSTANT_Float:
                        // all these are 4 byte constants
                        dis.readInt();
                        break;

                    case CONSTANT_Long:
                    case CONSTANT_Double:
                        // 8 byte constants
                        dis.readLong();
                        // occupies 2 cp entries
                        cpIndex++;
                        break;


                    case CONSTANT_Utf8: {
                        strings[cpIndex] = dis.readUTF();
                        break;
                    }

                    default:
                        System.err.println("invalid constant pool entry");
                        return;
                    }
                }

            // now walk thru the string constants and look for class names
            for (int s = 0; s < numConsts; s++) {
                if (strings[s] != null && mayBeClassName(strings[s]))
                    computeClosure(strings[s].replace('/', File.separatorChar));
            }

            } catch (IOException exp) {
                // ignore for now
            }

        }
    }

    // a sample main that accepts roots classes in a file and classpath as args
    public static void main(String[] args) {
        if (args.length != 2) {
            System.err.println("Usage: ClosureFinder <root class file> <class path>");
            System.exit(1);
        }

        List roots = new ArrayList();
        try {
            FileInputStream fis = new FileInputStream(args[0]);
            DataInputStream dis = new DataInputStream(fis);
            String line = null;
            while ((line = dis.readLine()) != null) {
                if (isWindows) {
                    line = line.replace('/', File.separatorChar);
                }
                roots.add(line);
            }
        } catch (IOException exp) {
            System.err.println(exp.getMessage());
            System.exit(2);
        }

        ClosureFinder cf = new ClosureFinder(roots, args[1]);
        Map out = cf.find();
        Iterator res = out.keySet().iterator();
        for(; res.hasNext(); ) {
            String className = (String) res.next();
            System.out.println(className + ".class");
        }
    }
}