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 com.sun.tools.classfile.Dependency.Location;
  29 import java.io.IOException;
  30 import java.util.ArrayList;
  31 import java.util.Collection;
  32 import java.util.Deque;
  33 import java.util.LinkedHashSet;
  34 import java.util.LinkedList;
  35 import java.util.List;
  36 import java.util.Optional;
  37 import java.util.Set;
  38 import java.util.concurrent.ConcurrentLinkedDeque;
  39 import java.util.stream.Collectors;
  40 import java.util.stream.Stream;
  41 
  42 import static com.sun.tools.jdeps.Analyzer.Type.CLASS;
  43 import static com.sun.tools.jdeps.Analyzer.Type.VERBOSE;
  44 import static com.sun.tools.jdeps.Module.trace;
  45 import static java.util.stream.Collectors.*;
  46 
  47 /**
  48  * Dependency Analyzer.
  49  *
  50  * Type of filters:
  51  * source filter: -include <pattern>
  52  * target filter: -package, -regex, --require
  53  *
  54  * The initial archive set for analysis includes
  55  * 1. archives specified in the command line arguments
  56  * 2. observable modules matching the source filter
  57  * 3. classpath archives matching the source filter or target filter
  58  * 4. --add-modules and -m root modules
  59  */
  60 public class DepsAnalyzer {
  61     final JdepsConfiguration configuration;
  62     final JdepsFilter filter;
  63     final JdepsWriter writer;
  64     final Analyzer.Type verbose;
  65     final boolean apiOnly;
  66 
  67     final DependencyFinder finder;
  68     final Analyzer analyzer;
  69     final List<Archive> rootArchives = new ArrayList<>();
  70 
  71     // parsed archives
  72     final Set<Archive> archives = new LinkedHashSet<>();
  73 
  74     public DepsAnalyzer(JdepsConfiguration config,
  75                         JdepsFilter filter,
  76                         JdepsWriter writer,
  77                         Analyzer.Type verbose,
  78                         boolean apiOnly) {
  79         this.configuration = config;
  80         this.filter = filter;
  81         this.writer = writer;
  82         this.verbose = verbose;
  83         this.apiOnly = apiOnly;
  84 
  85         this.finder = new DependencyFinder(config, filter);
  86         this.analyzer = new Analyzer(configuration, verbose, filter);
  87 
  88         // determine initial archives to be analyzed
  89         this.rootArchives.addAll(configuration.initialArchives());
  90 
  91         // if -include pattern is specified, add the matching archives on
  92         // classpath to the root archives
  93         if (filter.hasIncludePattern() || filter.hasTargetFilter()) {
  94             configuration.getModules().values().stream()
  95                 .filter(source -> include(source) && filter.matches(source))
  96                 .forEach(this.rootArchives::add);
  97         }
  98 
  99         // class path archives
 100         configuration.classPathArchives().stream()
 101             .filter(filter::matches)
 102             .forEach(this.rootArchives::add);
 103 
 104         // Include the root modules for analysis
 105         this.rootArchives.addAll(configuration.rootModules());
 106 
 107         trace("analyze root archives: %s%n", this.rootArchives);
 108     }
 109 
 110     /*
 111      * Perform runtime dependency analysis
 112      */
 113     public boolean run() throws IOException {
 114         return run(false, 1);
 115     }
 116 
 117     /**
 118      * Perform compile-time view or run-time view dependency analysis.
 119      *
 120      * @param compileTimeView
 121      * @param maxDepth  depth of recursive analysis.  depth == 0 if -R is set
 122      */
 123     public boolean run(boolean compileTimeView, int maxDepth) throws IOException {
 124         try {
 125             // parse each packaged module or classpath archive
 126             if (apiOnly) {
 127                 finder.parseExportedAPIs(rootArchives.stream());
 128             } else {
 129                 finder.parse(rootArchives.stream());
 130             }
 131             archives.addAll(rootArchives);
 132 
 133             int depth = maxDepth > 0 ? maxDepth : Integer.MAX_VALUE;
 134 
 135             // transitive analysis
 136             if (depth > 1) {
 137                 if (compileTimeView)
 138                     transitiveArchiveDeps(depth-1);
 139                 else
 140                     transitiveDeps(depth-1);
 141             }
 142 
 143             Set<Archive> archives = archives();
 144 
 145             // analyze the dependencies collected
 146             analyzer.run(archives, finder.locationToArchive());
 147 
 148             if (writer != null) {
 149                 writer.generateOutput(archives, analyzer);
 150             }
 151         } finally {
 152             finder.shutdown();
 153         }
 154         return true;
 155     }
 156 
 157     /**
 158      * Returns the archives for reporting that has matching dependences.
 159      *
 160      * If --require is set, they should be excluded.
 161      */
 162     Set<Archive> archives() {
 163         if (filter.requiresFilter().isEmpty()) {
 164             return archives.stream()
 165                 .filter(this::include)
 166                 .filter(Archive::hasDependences)
 167                 .collect(Collectors.toSet());
 168         } else {
 169             // use the archives that have dependences and not specified in --require
 170             return archives.stream()
 171                 .filter(source -> !filter.requiresFilter().contains(source.getName()))
 172                 .filter(this::include)
 173                 .filter(source ->
 174                         source.getDependencies()
 175                               .map(finder::locationToArchive)
 176                               .anyMatch(a -> a != source))
 177                 .collect(Collectors.toSet());
 178         }
 179     }
 180 
 181     /**
 182      * Returns the dependences, either class name or package name
 183      * as specified in the given verbose level.
 184      */
 185     Set<String> dependences() {
 186         return analyzer.archives().stream()
 187                        .map(analyzer::dependences)
 188                        .flatMap(Set::stream)
 189                        .collect(Collectors.toSet());
 190     }
 191 
 192     /**
 193      * Returns the archives that contains the given locations and
 194      * not parsed and analyzed.
 195      */
 196     private Set<Archive> unresolvedArchives(Stream<Location> locations) {
 197         return locations.filter(l -> !finder.isParsed(l))
 198                         .distinct()
 199                         .map(configuration::findClass)
 200                         .flatMap(Optional::stream)
 201                         .collect(toSet());
 202     }
 203 
 204     /*
 205      * Recursively analyzes entire module/archives.
 206     */
 207     private void transitiveArchiveDeps(int depth) throws IOException {
 208         Stream<Location> deps = archives.stream()
 209                                         .flatMap(Archive::getDependencies);
 210 
 211         // start with the unresolved archives
 212         Set<Archive> unresolved = unresolvedArchives(deps);
 213         do {
 214             // parse all unresolved archives
 215             Set<Location> targets = apiOnly
 216                 ? finder.parseExportedAPIs(unresolved.stream())
 217                 : finder.parse(unresolved.stream());
 218             archives.addAll(unresolved);
 219 
 220             // Add dependencies to the next batch for analysis
 221             unresolved = unresolvedArchives(targets.stream());
 222         } while (!unresolved.isEmpty() && depth-- > 0);
 223     }
 224 
 225     /*
 226      * Recursively analyze the class dependences
 227      */
 228     private void transitiveDeps(int depth) throws IOException {
 229         Stream<Location> deps = archives.stream()
 230                                         .flatMap(Archive::getDependencies);
 231 
 232         Collection<Module> modules = configuration.getModules().values();
 233         Deque<Location> unresolved = deps.collect(Collectors.toCollection(LinkedList::new));
 234         ConcurrentLinkedDeque<Location> deque = new ConcurrentLinkedDeque<>();
 235         do {
 236             Location target;
 237             while ((target = unresolved.poll()) != null) {
 238                 if (finder.isParsed(target))
 239                     continue;
 240 
 241                 Archive archive = configuration.findClass(target).orElse(null);
 242                 if (archive != null) {
 243                     archives.add(archive);
 244 
 245                     String name = target.getName();
 246                     Set<Location> targets = apiOnly
 247                             ? finder.parseExportedAPIs(archive, name)
 248                             : finder.parse(archive, name);
 249 
 250                     // build unresolved dependencies
 251                     targets.stream()
 252                            .filter(t -> !finder.isParsed(t))
 253                            .forEach(deque::add);
 254                 }
 255             }
 256             unresolved = deque;
 257             deque = new ConcurrentLinkedDeque<>();
 258         } while (!unresolved.isEmpty() && depth-- > 0);
 259     }
 260 
 261     /*
 262      * Tests if the given archive is requested for analysis.
 263      * It includes the root modules specified in --module, --add-modules and
 264      * dependences specified in --require
 265      */
 266     public boolean include(Archive source) {
 267         Module module = source.getModule();
 268         // skip system module by default
 269         return  !module.isSystem()
 270                     || configuration.rootModules().contains(source)
 271                     || filter.requiresFilter().contains(module.name());
 272     }
 273 
 274     // ----- for testing purpose -----
 275 
 276     public static enum Info {
 277         REQUIRES,
 278         REQUIRES_TRANSITIVE,
 279         EXPORTED_API,
 280         MODULE_PRIVATE,
 281         QUALIFIED_EXPORTED_API,
 282         INTERNAL_API,
 283         JDK_INTERNAL_API,
 284         JDK_REMOVED_INTERNAL_API
 285     }
 286 
 287     public static class Node {
 288         public final String name;
 289         public final String source;
 290         public final Info info;
 291         Node(String name, Info info) {
 292             this(name, name, info);
 293         }
 294         Node(String name, String source, Info info) {
 295             this.name = name;
 296             this.source = source;
 297             this.info = info;
 298         }
 299 
 300         @Override
 301         public String toString() {
 302             StringBuilder sb = new StringBuilder();
 303             if (info != Info.REQUIRES && info != Info.REQUIRES_TRANSITIVE)
 304                 sb.append(source).append("/");
 305 
 306             sb.append(name);
 307             if (info == Info.QUALIFIED_EXPORTED_API)
 308                 sb.append(" (qualified)");
 309             else if (info == Info.JDK_INTERNAL_API)
 310                 sb.append(" (JDK internal)");
 311             else if (info == Info.INTERNAL_API)
 312                 sb.append(" (internal)");
 313             return sb.toString();
 314         }
 315 
 316         @Override
 317         public boolean equals(Object o) {
 318             if (!(o instanceof Node))
 319                 return false;
 320 
 321             Node other = (Node)o;
 322             return this.name.equals(other.name) &&
 323                     this.source.equals(other.source) &&
 324                     this.info.equals(other.info);
 325         }
 326 
 327         @Override
 328         public int hashCode() {
 329             int result = name.hashCode();
 330             result = 31 * result + source.hashCode();
 331             result = 31 * result + info.hashCode();
 332             return result;
 333         }
 334     }
 335 
 336     /**
 337      * Returns a graph of module dependences.
 338      *
 339      * Each Node represents a module and each edge is a dependence.
 340      * No analysis on "requires transitive".
 341      */
 342     public Graph<Node> moduleGraph() {
 343         Graph.Builder<Node> builder = new Graph.Builder<>();
 344 
 345         archives().stream()
 346             .forEach(m -> {
 347                 Node u = new Node(m.getName(), Info.REQUIRES);
 348                 builder.addNode(u);
 349                 analyzer.requires(m)
 350                     .map(req -> new Node(req.getName(), Info.REQUIRES))
 351                     .forEach(v -> builder.addEdge(u, v));
 352             });
 353         return builder.build();
 354     }
 355 
 356     /**
 357      * Returns a graph of dependences.
 358      *
 359      * Each Node represents a class or package per the specified verbose level.
 360      * Each edge indicates
 361      */
 362     public Graph<Node> dependenceGraph() {
 363         Graph.Builder<Node> builder = new Graph.Builder<>();
 364 
 365         archives().stream()
 366             .map(analyzer.results::get)
 367             .filter(deps -> !deps.dependencies().isEmpty())
 368             .flatMap(deps -> deps.dependencies().stream())
 369             .forEach(d -> addEdge(builder, d));
 370         return builder.build();
 371     }
 372 
 373     private void addEdge(Graph.Builder<Node> builder, Analyzer.Dep dep) {
 374         Archive source = dep.originArchive();
 375         Archive target = dep.targetArchive();
 376         String pn = dep.target();
 377         if (verbose == CLASS || verbose == VERBOSE) {
 378             int i = dep.target().lastIndexOf('.');
 379             pn = i > 0 ? dep.target().substring(0, i) : "";
 380         }
 381         final Info info;
 382         Module targetModule = target.getModule();
 383         if (source == target) {
 384             info = Info.MODULE_PRIVATE;
 385         } else if (!targetModule.isNamed()) {
 386             info = Info.EXPORTED_API;
 387         } else if (targetModule.isExported(pn) && !targetModule.isJDKUnsupported()) {
 388             info = Info.EXPORTED_API;
 389         } else {
 390             Module module = target.getModule();
 391             if (module == Analyzer.REMOVED_JDK_INTERNALS) {
 392                 info = Info.JDK_REMOVED_INTERNAL_API;
 393             } else if (!source.getModule().isJDK() && module.isJDK())
 394                 info = Info.JDK_INTERNAL_API;
 395                 // qualified exports or inaccessible
 396             else if (module.isExported(pn, source.getModule().name()))
 397                 info = Info.QUALIFIED_EXPORTED_API;
 398             else
 399                 info = Info.INTERNAL_API;
 400         }
 401 
 402         Node u = new Node(dep.origin(), source.getName(), info);
 403         Node v = new Node(dep.target(), target.getName(), info);
 404         builder.addEdge(u, v);
 405     }
 406 
 407 }