/*
 * 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)
/** * 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.
/** * 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.
/** * 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.
/** * 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
/** * 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; }); } } }