1 /* 2 * Copyright (c) 2016, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package com.sun.tools.jdeps; 27 28 import static com.sun.tools.jdeps.JdepsFilter.DEFAULT_FILTER; 29 import static com.sun.tools.jdeps.Module.trace; 30 import static com.sun.tools.jdeps.Graph.*; 31 32 import java.lang.module.ModuleDescriptor.Requires; 33 import java.io.IOException; 34 import java.util.Collections; 35 import java.util.Deque; 36 import java.util.HashMap; 37 import java.util.HashSet; 38 import java.util.LinkedList; 39 import java.util.Map; 40 import java.util.Optional; 41 import java.util.Set; 42 import java.util.stream.Collectors; 43 import java.util.stream.Stream; 44 45 /** 46 * Inverse transitive dependency analysis (compile-time view) 47 */ 48 public class InverseDepsAnalyzer extends DepsAnalyzer { 49 // the end points for the resulting paths to be reported 50 private final Map<Archive, Set<Archive>> endPoints = new HashMap<>(); 51 // target archives for inverse transitive dependence analysis 52 private final Set<Archive> targets = new HashSet<>(); 53 54 public InverseDepsAnalyzer(JdepsConfiguration config, 55 JdepsFilter filter, 56 JdepsWriter writer, 57 Analyzer.Type verbose, 58 boolean apiOnly) { 59 super(config, filter, writer, verbose, apiOnly); 60 } 61 62 public boolean run() throws IOException { 63 try { 64 if (apiOnly) { 65 finder.parseExportedAPIs(rootArchives.stream()); 66 } else { 67 finder.parse(rootArchives.stream()); 68 } 69 archives.addAll(rootArchives); 70 71 Set<Archive> archives = archives(); 72 73 // If -package or -regex is specified, the archives that reference 74 // the matching types are used as the targets for inverse 75 // transitive analysis. If -requires is specified, the 76 // specified modules are the targets. 77 78 if (filter.requiresFilter().isEmpty()) { 79 targets.addAll(archives); 80 } else { 81 filter.requiresFilter().stream() 82 .map(configuration::findModule) 83 .flatMap(Optional::stream) 84 .forEach(targets::add); 85 } 86 87 // If -package or -regex is specified, the end points are 88 // the matching archives. If -requires is specified, 89 // the end points are the modules specified in -requires. 90 if (filter.requiresFilter().isEmpty()) { 91 Map<Archive, Set<Archive>> dependences = finder.dependences(); 92 targets.forEach(source -> endPoints.put(source, dependences.get(source))); 93 } else { 94 targets.forEach(t -> endPoints.put(t, Collections.emptySet())); 95 } 96 97 analyzer.run(archives, finder.locationToArchive()); 98 99 // print the first-level of dependencies 100 if (writer != null) { 101 writer.generateOutput(archives, analyzer); 102 } 103 104 } finally { 105 finder.shutdown(); 106 } 107 return true; 108 } 109 110 /** 111 * Returns the target archives determined from the dependency analysis. 112 * 113 * Inverse transitive dependency will find all nodes that depend 114 * upon the returned set of archives directly and indirectly. 115 */ 116 public Set<Archive> targets() { 117 return Collections.unmodifiableSet(targets); 118 } 119 120 /** 121 * Finds all inverse transitive dependencies using the given requires set 122 * as the targets, if non-empty. If the given requires set is empty, 123 * use the archives depending the packages specified in -regex or -p options. 124 */ 125 public Set<Deque<Archive>> inverseDependences() throws IOException { 126 // create a new dependency finder to do the analysis 127 DependencyFinder dependencyFinder = new DependencyFinder(configuration, DEFAULT_FILTER); 128 try { 129 // parse all archives in unnamed module to get compile-time dependences 130 Stream<Archive> archives = 131 Stream.concat(configuration.initialArchives().stream(), 132 configuration.classPathArchives().stream()); 133 if (apiOnly) { 134 dependencyFinder.parseExportedAPIs(archives); 135 } else { 136 dependencyFinder.parse(archives); 137 } 138 139 Graph.Builder<Archive> builder = new Graph.Builder<>(); 140 // include all target nodes 141 targets().forEach(builder::addNode); 142 143 // transpose the module graph - may filter JDK module 144 configuration.getModules().values().stream() 145 .filter(filter::include) 146 .forEach(m -> { 147 builder.addNode(m); 148 m.descriptor().requires().stream() 149 .map(Requires::name) 150 .map(configuration::findModule) // must be present 151 .forEach(v -> builder.addEdge(v.get(), m)); 152 }); 153 154 // add the dependences from the analysis 155 Map<Archive, Set<Archive>> dependences = dependencyFinder.dependences(); 156 dependences.entrySet().stream() 157 .forEach(e -> { 158 Archive u = e.getKey(); 159 builder.addNode(u); 160 e.getValue().forEach(v -> builder.addEdge(v, u)); 161 }); 162 163 // transposed dependence graph. 164 Graph<Archive> graph = builder.build(); 165 trace("targets: %s%n", targets()); 166 167 // Traverse from the targets and find all paths 168 // rebuild a graph with all nodes that depends on targets 169 // targets directly and indirectly 170 return targets().stream() 171 .map(t -> findPaths(graph, t)) 172 .flatMap(Set::stream) 173 .collect(Collectors.toSet()); 174 } finally { 175 dependencyFinder.shutdown(); 176 } 177 } 178 179 /** 180 * Returns all paths reachable from the given targets. 181 */ 182 private Set<Deque<Archive>> findPaths(Graph<Archive> graph, Archive target) { 183 184 // path is in reversed order 185 Deque<Archive> path = new LinkedList<>(); 186 path.push(target); 187 188 Set<Edge<Archive>> visited = new HashSet<>(); 189 190 Deque<Edge<Archive>> deque = new LinkedList<>(); 191 deque.addAll(graph.edgesFrom(target)); 192 if (deque.isEmpty()) { 193 return makePaths(path).collect(Collectors.toSet()); 194 } 195 196 Set<Deque<Archive>> allPaths = new HashSet<>(); 197 while (!deque.isEmpty()) { 198 Edge<Archive> edge = deque.pop(); 199 200 if (visited.contains(edge)) 201 continue; 202 203 Archive node = edge.v; 204 path.addLast(node); 205 visited.add(edge); 206 207 Set<Edge<Archive>> unvisitedDeps = graph.edgesFrom(node) 208 .stream() 209 .filter(e -> !visited.contains(e)) 210 .collect(Collectors.toSet()); 211 212 trace("visiting %s %s (%s)%n", edge, path, unvisitedDeps); 213 if (unvisitedDeps.isEmpty()) { 214 makePaths(path).forEach(allPaths::add); 215 path.removeLast(); 216 } 217 218 // push unvisited adjacent edges 219 unvisitedDeps.stream().forEach(deque::push); 220 221 222 // when the adjacent edges of a node are visited, pop it from the path 223 while (!path.isEmpty()) { 224 if (visited.containsAll(graph.edgesFrom(path.peekLast()))) 225 path.removeLast(); 226 else 227 break; 228 } 229 } 230 231 return allPaths; 232 } 233 234 /** 235 * Prepend end point to the path 236 */ 237 private Stream<Deque<Archive>> makePaths(Deque<Archive> path) { 238 Set<Archive> nodes = endPoints.get(path.peekFirst()); 239 if (nodes == null || nodes.isEmpty()) { 240 return Stream.of(new LinkedList<>(path)); 241 } else { 242 return nodes.stream().map(n -> { 243 Deque<Archive> newPath = new LinkedList<>(); 244 newPath.addFirst(n); 245 newPath.addAll(path); 246 return newPath; 247 }); 248 } 249 } 250 }