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 }