src/jdk.jdeps/share/classes/com/sun/tools/jdeps/InverseDepsAnalyzer.java - platform/libcore - Git at Google

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