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