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 package com.sun.tools.jdeps;
  26 
  27 import static com.sun.tools.jdeps.Graph.*;
  28 import static com.sun.tools.jdeps.JdepsFilter.DEFAULT_FILTER;
  29 import static com.sun.tools.jdeps.Module.*;
  30 import static java.lang.module.ModuleDescriptor.Requires.Modifier.*;
  31 import static java.util.stream.Collectors.*;
  32 
  33 import com.sun.tools.classfile.Dependency;
  34 import com.sun.tools.jdeps.JdepsTask.BadArgs;
  35 
  36 import java.io.IOException;
  37 import java.io.OutputStream;
  38 import java.io.PrintWriter;
  39 import java.lang.module.ModuleDescriptor;
  40 import java.nio.file.Files;
  41 import java.nio.file.Path;
  42 import java.util.Collections;
  43 import java.util.Comparator;
  44 import java.util.Deque;
  45 import java.util.HashMap;
  46 import java.util.HashSet;
  47 import java.util.LinkedList;
  48 import java.util.Map;
  49 import java.util.Optional;
  50 import java.util.Set;
  51 import java.util.function.Function;
  52 import java.util.stream.Collectors;
  53 import java.util.stream.Stream;
  54 
  55 /**
  56  * Analyze module dependences and compare with module descriptor.
  57  * Also identify any qualified exports not used by the target module.
  58  */
  59 public class ModuleAnalyzer {
  60     private static final String JAVA_BASE = "java.base";
  61 
  62     private final JdepsConfiguration configuration;
  63     private final PrintWriter log;
  64 
  65     private final DependencyFinder dependencyFinder;
  66     private final Map<Module, ModuleDeps> modules;
  67 
  68     public ModuleAnalyzer(JdepsConfiguration config,
  69                           PrintWriter log) {
  70         this(config, log, Collections.emptySet());
  71     }
  72     public ModuleAnalyzer(JdepsConfiguration config,
  73                           PrintWriter log,
  74                           Set<String> names) {
  75 
  76         if (!config.initialArchives().isEmpty()) {
  77             String list = config.initialArchives().stream()
  78                 .map(Archive::getPathName).collect(joining(" "));
  79             throw new JdepsTask.UncheckedBadArgs(new BadArgs("err.invalid.module.option",
  80                 list, "-check"));
  81         }
  82 
  83         this.configuration = config;
  84         this.log = log;
  85 
  86         this.dependencyFinder = new DependencyFinder(config, DEFAULT_FILTER);
  87         if (names.isEmpty()) {
  88             this.modules = configuration.rootModules().stream()
  89                 .collect(toMap(Function.identity(), ModuleDeps::new));
  90         } else {
  91             this.modules = names.stream()
  92                 .map(configuration::findModule)
  93                 .flatMap(Optional::stream)
  94                 .collect(toMap(Function.identity(), ModuleDeps::new));
  95         }
  96     }
  97 
  98     public boolean run() throws IOException {
  99         try {
 100             // compute "requires public" dependences
 101             modules.values().forEach(ModuleDeps::computeRequiresPublic);
 102 
 103             modules.values().forEach(md -> {
 104                 // compute "requires" dependences
 105                 md.computeRequires();
 106                 // apply transitive reduction and reports recommended requires.
 107                 md.analyzeDeps();
 108             });
 109         } finally {
 110             dependencyFinder.shutdown();
 111         }
 112         return true;
 113     }
 114 
 115     class ModuleDeps {
 116         final Module root;
 117         Set<Module> requiresPublic;
 118         Set<Module> requires;
 119         Map<String, Set<String>> unusedQualifiedExports;
 120 
 121         ModuleDeps(Module root) {
 122             this.root = root;
 123         }
 124 
 125         /**
 126          * Compute 'requires public' dependences by analyzing API dependencies
 127          */
 128         private void computeRequiresPublic() {
 129             // record requires public
 130             this.requiresPublic = computeRequires(true)
 131                 .filter(m -> !m.name().equals(JAVA_BASE))
 132                 .collect(toSet());
 133 
 134             trace("requires public: %s%n", requiresPublic);
 135         }
 136 
 137         private void computeRequires() {
 138             this.requires = computeRequires(false).collect(toSet());
 139             trace("requires: %s%n", requires);
 140         }
 141 
 142         private Stream<Module> computeRequires(boolean apionly) {
 143             // analyze all classes
 144 
 145             if (apionly) {
 146                 dependencyFinder.parseExportedAPIs(Stream.of(root));
 147             } else {
 148                 dependencyFinder.parse(Stream.of(root));
 149             }
 150 
 151             // find the modules of all the dependencies found
 152             return dependencyFinder.getDependences(root)
 153                         .map(Archive::getModule);
 154         }
 155 
 156         ModuleDescriptor descriptor() {
 157             return descriptor(requiresPublic, requires);
 158         }
 159 
 160         private ModuleDescriptor descriptor(Set<Module> requiresPublic,
 161                                             Set<Module> requires) {
 162 
 163             ModuleDescriptor.Builder builder = new ModuleDescriptor.Builder(root.name());
 164 
 165             if (!root.name().equals(JAVA_BASE))
 166                 builder.requires(MANDATED, JAVA_BASE);
 167 
 168             requiresPublic.stream()
 169                 .filter(m -> !m.name().equals(JAVA_BASE))
 170                 .map(Module::name)
 171                 .forEach(mn -> builder.requires(PUBLIC, mn));
 172 
 173             requires.stream()
 174                 .filter(m -> !requiresPublic.contains(m))
 175                 .filter(m -> !m.name().equals(JAVA_BASE))
 176                 .map(Module::name)
 177                 .forEach(mn -> builder.requires(mn));
 178 
 179             return builder.build();
 180         }
 181 
 182         ModuleDescriptor reduced() {
 183             Graph.Builder<Module> bd = new Graph.Builder<>();
 184             requiresPublic.stream()
 185                 .forEach(m -> {
 186                     bd.addNode(m);
 187                     bd.addEdge(root, m);
 188                 });
 189 
 190             // requires public graph
 191             Graph<Module> rbg = bd.build().reduce();
 192 
 193             // transitive reduction
 194             Graph<Module> newGraph = buildGraph(requires).reduce(rbg);
 195             if (DEBUG) {
 196                 System.err.println("after transitive reduction: ");
 197                 newGraph.printGraph(log);
 198             }
 199 
 200             return descriptor(requiresPublic, newGraph.adjacentNodes(root));
 201         }
 202 
 203 
 204         /**
 205          * Apply transitive reduction on the resulting graph and reports
 206          * recommended requires.
 207          */
 208         private void analyzeDeps() {
 209             Graph.Builder<Module> builder = new Graph.Builder<>();
 210             requiresPublic.stream()
 211                 .forEach(m -> {
 212                     builder.addNode(m);
 213                     builder.addEdge(root, m);
 214                 });
 215 
 216             // requires public graph
 217             Graph<Module> rbg = buildGraph(requiresPublic).reduce();
 218 
 219             // transitive reduction
 220             Graph<Module> newGraph = buildGraph(requires).reduce(builder.build().reduce());
 221             if (DEBUG) {
 222                 System.err.println("after transitive reduction: ");
 223                 newGraph.printGraph(log);
 224             }
 225 
 226             printModuleDescriptor(log, root);
 227 
 228             ModuleDescriptor analyzedDescriptor = descriptor();
 229             if (!matches(root.descriptor(), analyzedDescriptor)) {
 230                 log.format("  [Suggested module descriptor for %s]%n", root.name());
 231                 analyzedDescriptor.requires()
 232                     .stream()
 233                     .sorted(Comparator.comparing(ModuleDescriptor.Requires::name))
 234                     .forEach(req -> log.format("    requires %s;%n", req));
 235             }
 236 
 237             ModuleDescriptor reduced = reduced();
 238             if (!matches(root.descriptor(), reduced)) {
 239                 log.format("  [Transitive reduced graph for %s]%n", root.name());
 240                 reduced.requires()
 241                     .stream()
 242                     .sorted(Comparator.comparing(ModuleDescriptor.Requires::name))
 243                     .forEach(req -> log.format("    requires %s;%n", req));
 244             }
 245 
 246             checkQualifiedExports();
 247             log.println();
 248         }
 249 
 250         private void checkQualifiedExports() {
 251             // detect any qualified exports not used by the target module
 252             unusedQualifiedExports = unusedQualifiedExports();
 253             if (!unusedQualifiedExports.isEmpty())
 254                 log.format("  [Unused qualified exports in %s]%n", root.name());
 255 
 256             unusedQualifiedExports.keySet().stream()
 257                 .sorted()
 258                 .forEach(pn -> log.format("    exports %s to %s%n", pn,
 259                     unusedQualifiedExports.get(pn).stream()
 260                         .sorted()
 261                         .collect(joining(","))));
 262         }
 263 
 264         private void printModuleDescriptor(PrintWriter out, Module module) {
 265             ModuleDescriptor descriptor = module.descriptor();
 266             out.format("%s (%s)%n", descriptor.name(), module.location());
 267 
 268             if (descriptor.name().equals(JAVA_BASE))
 269                 return;
 270 
 271             out.println("  [Module descriptor]");
 272             descriptor.requires()
 273                 .stream()
 274                 .sorted(Comparator.comparing(ModuleDescriptor.Requires::name))
 275                 .forEach(req -> out.format("    requires %s;%n", req));
 276         }
 277 
 278 
 279         /**
 280          * Returns a graph of modules required by the specified module.
 281          *
 282          * Requires public edges of the dependences are added to the graph.
 283          */
 284         private Graph<Module> buildGraph(Set<Module> deps) {
 285             Graph.Builder<Module> builder = new Graph.Builder<>();
 286             builder.addNode(root);
 287             Set<Module> visited = new HashSet<>();
 288             visited.add(root);
 289             Deque<Module> deque = new LinkedList<>();
 290             deps.stream()
 291                 .forEach(m -> {
 292                     deque.add(m);
 293                     builder.addEdge(root, m);
 294                 });
 295 
 296             // read requires public from ModuleDescription
 297             Module source;
 298             while ((source = deque.poll()) != null) {
 299                 if (visited.contains(source))
 300                     continue;
 301 
 302                 visited.add(source);
 303                 builder.addNode(source);
 304                 Module from = source;
 305                 source.descriptor().requires().stream()
 306                     .filter(req -> req.modifiers().contains(PUBLIC))
 307                     .map(ModuleDescriptor.Requires::name)
 308                     .map(configuration::findModule)
 309                     .flatMap(Optional::stream)
 310                     .forEach(m -> {
 311                         deque.add(m);
 312                         builder.addEdge(from, m);
 313                     });
 314             }
 315             return builder.build();
 316         }
 317 
 318         /**
 319          * Detects any qualified exports not used by the target module.
 320          */
 321         private Map<String, Set<String>> unusedQualifiedExports() {
 322             Map<String, Set<String>> unused = new HashMap<>();
 323 
 324             // build the qualified exports map
 325             Map<String, Set<String>> qualifiedExports =
 326                 root.exports().entrySet().stream()
 327                     .filter(e -> !e.getValue().isEmpty())
 328                     .map(Map.Entry::getKey)
 329                     .collect(toMap(Function.identity(), _k -> new HashSet<>()));
 330 
 331             Set<Module> mods = new HashSet<>();
 332             root.exports().values()
 333                 .stream()
 334                 .flatMap(Set::stream)
 335                 .forEach(target -> configuration.findModule(target)
 336                     .ifPresentOrElse(mods::add,
 337                         () -> log.format("Warning: %s not found%n", target))
 338                 );
 339 
 340             // parse all target modules
 341             dependencyFinder.parse(mods.stream());
 342 
 343             // adds to the qualified exports map if a module references it
 344             mods.stream().forEach(m ->
 345                 m.getDependencies()
 346                     .map(Dependency.Location::getPackageName)
 347                     .filter(qualifiedExports::containsKey)
 348                     .forEach(pn -> qualifiedExports.get(pn).add(m.name())));
 349 
 350             // compare with the exports from ModuleDescriptor
 351             Set<String> staleQualifiedExports =
 352                 qualifiedExports.keySet().stream()
 353                     .filter(pn -> !qualifiedExports.get(pn).equals(root.exports().get(pn)))
 354                     .collect(toSet());
 355 
 356             if (!staleQualifiedExports.isEmpty()) {
 357                 for (String pn : staleQualifiedExports) {
 358                     Set<String> targets = new HashSet<>(root.exports().get(pn));
 359                     targets.removeAll(qualifiedExports.get(pn));
 360                     unused.put(pn, targets);
 361                 }
 362             }
 363             return unused;
 364         }
 365     }
 366 
 367     private boolean matches(ModuleDescriptor md, ModuleDescriptor other) {
 368         // build requires public from ModuleDescriptor
 369         Set<ModuleDescriptor.Requires> reqPublic = md.requires().stream()
 370             .filter(req -> req.modifiers().contains(PUBLIC))
 371             .collect(toSet());
 372         Set<ModuleDescriptor.Requires> otherReqPublic = other.requires().stream()
 373             .filter(req -> req.modifiers().contains(PUBLIC))
 374             .collect(toSet());
 375 
 376         if (!reqPublic.equals(otherReqPublic)) {
 377             trace("mismatch requires public: %s%n", reqPublic);
 378             return false;
 379         }
 380 
 381         Set<ModuleDescriptor.Requires> unused = md.requires().stream()
 382             .filter(req -> !other.requires().contains(req))
 383             .collect(Collectors.toSet());
 384 
 385         if (!unused.isEmpty()) {
 386             trace("mismatch requires: %s%n", unused);
 387             return false;
 388         }
 389         return true;
 390     }
 391 
 392     /**
 393      * Generate dotfile from module descriptor
 394      *
 395      * @param dir output directory
 396      */
 397     public boolean genDotFiles(Path dir) throws IOException {
 398         Files.createDirectories(dir);
 399         for (Module m : modules.keySet()) {
 400             genDotFile(dir, m.name());
 401         }
 402         return true;
 403     }
 404 
 405 
 406     private void genDotFile(Path dir, String name) throws IOException {
 407         try (OutputStream os = Files.newOutputStream(dir.resolve(name + ".dot"));
 408              PrintWriter out = new PrintWriter(os)) {
 409             Set<Module> modules = configuration.resolve(Set.of(name))
 410                 .collect(Collectors.toSet());
 411 
 412             // transitive reduction
 413             Graph<String> graph = gengraph(modules);
 414 
 415             out.format("digraph \"%s\" {%n", name);
 416             DotGraph.printAttributes(out);
 417             DotGraph.printNodes(out, graph);
 418 
 419             modules.stream()
 420                 .map(Module::descriptor)
 421                 .sorted(Comparator.comparing(ModuleDescriptor::name))
 422                 .forEach(md -> {
 423                     String mn = md.name();
 424                     Set<String> requiresPublic = md.requires().stream()
 425                         .filter(d -> d.modifiers().contains(PUBLIC))
 426                         .map(d -> d.name())
 427                         .collect(toSet());
 428 
 429                     DotGraph.printEdges(out, graph, mn, requiresPublic);
 430                 });
 431 
 432             out.println("}");
 433         }
 434     }
 435 
 436     /**
 437      * Returns a Graph of the given Configuration after transitive reduction.
 438      *
 439      * Transitive reduction of requires public edge and requires edge have
 440      * to be applied separately to prevent the requires public edges
 441      * (e.g. U -> V) from being reduced by a path (U -> X -> Y -> V)
 442      * in which  V would not be re-exported from U.
 443      */
 444     private Graph<String> gengraph(Set<Module> modules) {
 445         // build a Graph containing only requires public edges
 446         // with transitive reduction.
 447         Graph.Builder<String> rpgbuilder = new Graph.Builder<>();
 448         for (Module module : modules) {
 449             ModuleDescriptor md = module.descriptor();
 450             String mn = md.name();
 451             md.requires().stream()
 452                     .filter(d -> d.modifiers().contains(PUBLIC))
 453                     .map(d -> d.name())
 454                     .forEach(d -> rpgbuilder.addEdge(mn, d));
 455         }
 456 
 457         Graph<String> rpg = rpgbuilder.build().reduce();
 458 
 459         // build the readability graph
 460         Graph.Builder<String> builder = new Graph.Builder<>();
 461         for (Module module : modules) {
 462             ModuleDescriptor md = module.descriptor();
 463             String mn = md.name();
 464             builder.addNode(mn);
 465             configuration.reads(module)
 466                     .map(Module::name)
 467                     .forEach(d -> builder.addEdge(mn, d));
 468         }
 469 
 470         // transitive reduction of requires edges
 471         return builder.build().reduce(rpg);
 472     }
 473 
 474     // ---- for testing purpose
 475     public ModuleDescriptor[] descriptors(String name) {
 476         ModuleDeps moduleDeps = modules.keySet().stream()
 477             .filter(m -> m.name().equals(name))
 478             .map(modules::get)
 479             .findFirst().get();
 480 
 481         ModuleDescriptor[] descriptors = new ModuleDescriptor[3];
 482         descriptors[0] = moduleDeps.root.descriptor();
 483         descriptors[1] = moduleDeps.descriptor();
 484         descriptors[2] = moduleDeps.reduced();
 485         return descriptors;
 486     }
 487 
 488     public Map<String, Set<String>> unusedQualifiedExports(String name) {
 489         ModuleDeps moduleDeps = modules.keySet().stream()
 490             .filter(m -> m.name().equals(name))
 491             .map(modules::get)
 492             .findFirst().get();
 493         return moduleDeps.unusedQualifiedExports;
 494     }
 495 }