/*

 * Copyright (c) 2009, 2013, Oracle and/or its affiliates. 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.  Oracle designates this

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

 * by Oracle in the LICENSE file that accompanied this code.

 *

 * 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

package com.sun.tools.classfile;

import java.util.Deque;

import java.util.HashMap;

import java.util.HashSet;

import java.util.LinkedList;

import java.util.List;

import java.util.Map;

import java.util.Objects;

import java.util.Set;

import java.util.regex.Pattern;

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

import com.sun.tools.classfile.Dependency.Finder;

import com.sun.tools.classfile.Dependency.Location;

import com.sun.tools.classfile.Type.ArrayType;

import com.sun.tools.classfile.Type.ClassSigType;

import com.sun.tools.classfile.Type.ClassType;

import com.sun.tools.classfile.Type.MethodType;

import com.sun.tools.classfile.Type.SimpleType;

import com.sun.tools.classfile.Type.TypeParamType;

import com.sun.tools.classfile.Type.WildcardType;

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

/**

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

 *

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

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

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

 * method within a class.

 *

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

 * dependencies found by a finder.

 *

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

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

 */

public class Dependencies {

    /**

     * Thrown when a class file cannot be found.

     */

    public static class ClassFileNotFoundException extends Exception {

        private static final long serialVersionUID = 3632265927794475048L;

        public ClassFileNotFoundException(String className) {

            super(className);

            this.className = className;

        }

        public ClassFileNotFoundException(String className, Throwable cause) {

            this(className);

            initCause(cause);

        }

        public final String className;

    }

    /**

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

     */

    public static class ClassFileError extends Error {

        private static final long serialVersionUID = 4111110813961313203L;

        public ClassFileError(Throwable cause) {

            initCause(cause);

        }

    }

    /**

     * Service provider interface to locate and read class files.

     */

    public interface ClassFileReader {

        /**

         * Get the ClassFile object for a specified class.

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

         * @return the ClassFile for the given class

         * @throws Dependencies.ClassFileNotFoundException if the classfile cannot be

         *   found

         */

        public ClassFile getClassFile(String className)

                throws ClassFileNotFoundException;

    }

    /**

     * Service provide interface to handle results.

     */

    public interface Recorder {

        /**

         * Record a dependency that has been found.

         * @param d

         */

        public void addDependency(Dependency d);

    }

    /**

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

     * @return the default finder

     */

    public static Finder getDefaultFinder() {

        return new APIDependencyFinder(AccessFlags.ACC_PRIVATE);

    }

    /**

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

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

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

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

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

     * {@link AccessFlags#ACC_PRIVATE ACC_PRIVATE},

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

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

     * to that specified will be searched for dependencies.

     * @param access the access of members to be checked

     * @return an API finder

     */

    public static Finder getAPIFinder(int access) {

        return new APIDependencyFinder(access);

    }

    /**

     * Get a finder to do class dependency analysis.

     *

     * @return a Class dependency finder

     */

    public static Finder getClassDependencyFinder() {

        return new ClassDependencyFinder();

    }

    /**

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

     * @return the finder

     */

    public Finder getFinder() {

        if (finder == null)

            finder = getDefaultFinder();

        return finder;

    }

    /**

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

     * @param f the finder

     */

    public void setFinder(Finder f) {

        finder = Objects.requireNonNull(f);

    }

    /**

     * Get the default filter used to determine included when searching

     * the transitive closure of all the dependencies.

     * Unless overridden, the default filter accepts all dependencies.

     * @return the default filter.

     */

    public static Filter getDefaultFilter() {

        return DefaultFilter.instance();

    }

    /**

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

     * to determine if a dependency is of interest.

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

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

     */

    public static Filter getRegexFilter(Pattern pattern) {

        return new TargetRegexFilter(pattern);

    }

    /**

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

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

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

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

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

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

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

     */

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

        return new TargetPackageFilter(packageNames, matchSubpackages);

    }

    /**

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

     * the transitive closure of all the dependencies.

     * Unless overridden, the default filter accepts all dependencies.

     * @return the filter

     */

    public Filter getFilter() {

        if (filter == null)

            filter = getDefaultFilter();

        return filter;

    }

    /**

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

     * the transitive closure of all the dependencies.

     * @param f the filter

     */

    public void setFilter(Filter f) {

        filter = Objects.requireNonNull(f);

    }

    /**

     * Find the dependencies of a class, using the current

     * {@link Dependencies#getFinder finder} and

     * {@link Dependencies#getFilter filter}.

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

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

     * dependencies.

     * @param classFinder a finder to locate class files

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

     *      searching

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

     *      named in any filtered dependencies that are found.

     * @return the set of dependencies that were found

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

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

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

     */

    public Set<Dependency> findAllDependencies(

            ClassFileReader classFinder, Set<String> rootClassNames,

            boolean transitiveClosure)

            throws ClassFileNotFoundException {

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

        Recorder r = new Recorder() {

            public void addDependency(Dependency d) {

                results.add(d);

            }

        };

        findAllDependencies(classFinder, rootClassNames, transitiveClosure, r);

        return results;

    }

    /**

     * Find the dependencies of a class, using the current

     * {@link Dependencies#getFinder finder} and

     * {@link Dependencies#getFilter filter}.

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

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

     * dependencies.

     * @param classFinder a finder to locate class files

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

     *      searching

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

     *      named in any filtered dependencies that are found.

     * @param recorder a recorder for handling the results

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

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

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

     */

    public void findAllDependencies(

            ClassFileReader classFinder, Set<String> rootClassNames,

            boolean transitiveClosure, Recorder recorder)

            throws ClassFileNotFoundException {

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

        getFinder();  // ensure initialized

        getFilter();  // ensure initialized

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

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

        // dependencies in the results map.

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

        String className;

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

            assert (!doneClasses.contains(className));

            doneClasses.add(className);

            ClassFile cf = classFinder.getClassFile(className);

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

            // followed for the transitive closure.

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

                recorder.addDependency(d);

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

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

                    if (!doneClasses.contains(cn))

                        deque.add(cn);

                }

            }

        }

    }

    private Filter filter;

    private Finder finder;

    /**

     * A location identifying a class.

     */

    static class SimpleLocation implements Location {

        public SimpleLocation(String name) {

            this.name = name;

            this.className = name.replace('/', '.');

        }

        public String getName() {

            return name;

        }

        public String getClassName() {

            return className;

        }

        public String getPackageName() {

            int i = name.lastIndexOf('/');

            return (i > 0) ? name.substring(0, i).replace('/', '.') : "";

        }

        @Override

        public boolean equals(Object other) {

            if (this == other)

                return true;

            if (!(other instanceof SimpleLocation))

                return false;

            return (name.equals(((SimpleLocation) other).name));

        }

        @Override

        public int hashCode() {

            return name.hashCode();

        }

        @Override

        public String toString() {

            return name;

        }

        private String name;

        private String className;

    }

    /**

     * A dependency of one class on another.

     */

    static class SimpleDependency implements Dependency {

        public SimpleDependency(Location origin, Location target) {

            this.origin = origin;

            this.target = target;

        }

        public Location getOrigin() {

            return origin;

        }

        public Location getTarget() {

            return target;

        }

        @Override

        public boolean equals(Object other) {

            if (this == other)

                return true;

            if (!(other instanceof SimpleDependency))

                return false;

            SimpleDependency o = (SimpleDependency) other;

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

        }

        @Override

        public int hashCode() {

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

        }

        @Override

        public String toString() {

            return origin + ":" + target;

        }

        private Location origin;

        private Location target;

    }

    /**

     * This class accepts all dependencies.

     */

    static class DefaultFilter implements Filter {

        private static DefaultFilter instance;

        static DefaultFilter instance() {

            if (instance == null)

                instance = new DefaultFilter();

            return instance;

        }

        public boolean accepts(Dependency dependency) {

            return true;

        }

    }

    /**

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

     * regular expression.

     */

    static class TargetRegexFilter implements Filter {

        TargetRegexFilter(Pattern pattern) {

            this.pattern = pattern;

        }

        public boolean accepts(Dependency dependency) {

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

        }

        private final Pattern pattern;

    }

    /**

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

     * package.

     */

    static class TargetPackageFilter implements Filter {

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

            for (String pn: packageNames) {

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

                    throw new IllegalArgumentException();

            }

            this.packageNames = packageNames;

            this.matchSubpackages = matchSubpackages;

        }

        public boolean accepts(Dependency dependency) {

            String pn = dependency.getTarget().getPackageName();

            if (packageNames.contains(pn))

                return true;

            if (matchSubpackages) {

                for (String n: packageNames) {

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

                        return true;

                }

            }

            return false;

        }

        private final Set<String> packageNames;

        private final boolean matchSubpackages;

    }

    /**

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

     */

    static class ClassDependencyFinder extends BasicDependencyFinder {

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

            Visitor v = new Visitor(classfile);

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

                v.scan(cpInfo);

            }

            try {

                v.addClass(classfile.super_class);

                v.addClasses(classfile.interfaces);

                v.scan(classfile.attributes);

                for (Field f : classfile.fields) {

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

                }

                for (Method m : classfile.methods) {

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

                    Exceptions_attribute e =

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

                    if (e != null) {

                        v.addClasses(e.exception_index_table);

                    }

                }

            } catch (ConstantPoolException e) {

                throw new ClassFileError(e);

            }

            return v.deps;

        }

    }

    /**

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

     * and methods in a class.

     */

    static class APIDependencyFinder extends BasicDependencyFinder {

        APIDependencyFinder(int access) {

            switch (access) {

                case AccessFlags.ACC_PUBLIC:

                case AccessFlags.ACC_PROTECTED:

                case AccessFlags.ACC_PRIVATE:

                case 0:

                    showAccess = access;

                    break;

                default:

                    throw new IllegalArgumentException("invalid access 0x"

                            + Integer.toHexString(access));

            }

        }

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

            try {

                Visitor v = new Visitor(classfile);

                v.addClass(classfile.super_class);

                v.addClasses(classfile.interfaces);