InverseDepsAnalyzer.java

/*
 * Copyright (c) 2016, 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.jdeps;

import static com.sun.tools.jdeps.JdepsFilter.DEFAULT_FILTER;
import static com.sun.tools.jdeps.Module.trace;
import static com.sun.tools.jdeps.Graph.*;

import java.lang.module.ModuleDescriptor.Requires;
import java.io.IOException;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Optional;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * Inverse transitive dependency analysis (compile-time view)
 */
public class InverseDepsAnalyzer extends DepsAnalyzer {
    // the end points for the resulting paths to be reported
    private final Map<Archive, Set<Archive>> endPoints = new HashMap<>();
    // target archives for inverse transitive dependence analysis
    private final Set<Archive> targets = new HashSet<>();

    public InverseDepsAnalyzer(JdepsConfiguration config,
                               JdepsFilter filter,
                               JdepsWriter writer,
                               Analyzer.Type verbose,
                               boolean apiOnly) {
        super(config, filter, writer, verbose, apiOnly);
    }

    public boolean run() throws IOException {
        try {
            if (apiOnly) {
                finder.parseExportedAPIs(rootArchives.stream());
            } else {
                finder.parse(rootArchives.stream());
            }
            archives.addAll(rootArchives);

            Set<Archive> archives = archives();

            // If -package or -regex is specified, the archives that reference
            // the matching types are used as the targets for inverse
            // transitive analysis.  If -requires is specified, the
            // specified modules are the targets.

            if (filter.requiresFilter().isEmpty()) {
                targets.addAll(archives);
            } else {
                filter.requiresFilter().stream()
                      .map(configuration::findModule)
                      .flatMap(Optional::stream)
                      .forEach(targets::add);
            }

            // If -package or -regex is specified, the end points are
            // the matching archives.  If -requires is specified,
            // the end points are the modules specified in -requires.
            if (filter.requiresFilter().isEmpty()) {
                Map<Archive, Set<Archive>> dependences = finder.dependences();
                targets.forEach(source -> endPoints.put(source, dependences.get(source)));
            } else {
                targets.forEach(t -> endPoints.put(t, Collections.emptySet()));
            }

            analyzer.run(archives, finder.locationToArchive());

            // print the first-level of dependencies
            if (writer != null) {
                writer.generateOutput(archives, analyzer);
            }

        } finally {
            finder.shutdown();
        }
        return true;
    }

    /**
     * Returns the target archives determined from the dependency analysis.
     *
     * Inverse transitive dependency will find all nodes that depend
     * upon the returned set of archives directly and indirectly.
     */
    public Set<Archive> targets() {
        return Collections.unmodifiableSet(targets);
    }

    /**
     * Finds all inverse transitive dependencies using the given requires set
     * as the targets, if non-empty.  If the given requires set is empty,
     * use the archives depending the packages specified in -regex or -p options.
     */
    public Set<Deque<Archive>> inverseDependences() throws IOException {
        // create a new dependency finder to do the analysis
        DependencyFinder dependencyFinder = new DependencyFinder(configuration, DEFAULT_FILTER);
        try {
            // parse all archives in unnamed module to get compile-time dependences
            Stream<Archive> archives =
                Stream.concat(configuration.initialArchives().stream(),
                              configuration.classPathArchives().stream());
            if (apiOnly) {
                dependencyFinder.parseExportedAPIs(archives);
            } else {
                dependencyFinder.parse(archives);
            }

            Graph.Builder<Archive> builder = new Graph.Builder<>();
            // include all target nodes
            targets().forEach(builder::addNode);

            // transpose the module graph
            configuration.getModules().values().stream()
                .forEach(m -> {
                    builder.addNode(m);
                    m.descriptor().requires().stream()
                        .map(Requires::name)
                        .map(configuration::findModule)  // must be present
                        .forEach(v -> builder.addEdge(v.get(), m));
                });

            // add the dependences from the analysis
            Map<Archive, Set<Archive>> dependences = dependencyFinder.dependences();
            dependences.entrySet().stream()
                .forEach(e -> {
                    Archive u = e.getKey();
                    builder.addNode(u);
                    e.getValue().forEach(v -> builder.addEdge(v, u));
                });

            // transposed dependence graph.
            Graph<Archive> graph = builder.build();
            trace("targets: %s%n", targets());

            // Traverse from the targets and find all paths
            // rebuild a graph with all nodes that depends on targets
            // targets directly and indirectly
            return targets().stream()
                .map(t -> findPaths(graph, t))
                .flatMap(Set::stream)
                .collect(Collectors.toSet());
        } finally {
            dependencyFinder.shutdown();
        }
    }

    /**
     * Returns all paths reachable from the given targets.
     */
    private Set<Deque<Archive>> findPaths(Graph<Archive> graph, Archive target) {

        // path is in reversed order
        Deque<Archive> path = new LinkedList<>();
        path.push(target);

        Set<Edge<Archive>> visited = new HashSet<>();

        Deque<Edge<Archive>> deque = new LinkedList<>();
        deque.addAll(graph.edgesFrom(target));
        if (deque.isEmpty()) {
            return makePaths(path).collect(Collectors.toSet());
        }

        Set<Deque<Archive>> allPaths = new HashSet<>();
        while (!deque.isEmpty()) {
            Edge<Archive> edge = deque.pop();

            if (visited.contains(edge))
                continue;

            Archive node = edge.v;
            path.addLast(node);
            visited.add(edge);

            Set<Edge<Archive>> unvisitedDeps = graph.edgesFrom(node)
                    .stream()
                    .filter(e -> !visited.contains(e))
                    .collect(Collectors.toSet());

            trace("visiting %s %s (%s)%n", edge, path, unvisitedDeps);
            if (unvisitedDeps.isEmpty()) {
                makePaths(path).forEach(allPaths::add);
                path.removeLast();
            }

            // push unvisited adjacent edges
            unvisitedDeps.stream().forEach(deque::push);


            // when the adjacent edges of a node are visited, pop it from the path
            while (!path.isEmpty()) {
                if (visited.containsAll(graph.edgesFrom(path.peekLast())))
                    path.removeLast();
                else
                    break;
            }
        }

       return allPaths;
    }

    /**
     * Prepend end point to the path
     */
    private Stream<Deque<Archive>> makePaths(Deque<Archive> path) {
        Set<Archive> nodes = endPoints.get(path.peekFirst());
        if (nodes == null || nodes.isEmpty()) {
            return Stream.of(new LinkedList<>(path));
        } else {
            return nodes.stream().map(n -> {
                Deque<Archive> newPath = new LinkedList<>();
                newPath.addFirst(n);
                newPath.addAll(path);
                return newPath;
            });
        }
    }
}