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
26package com.sun.tools.jdeps;
27
28import com.sun.tools.classfile.Dependency.Location;
29import java.io.IOException;
30import java.util.ArrayList;
31import java.util.Collection;
32import java.util.Deque;
33import java.util.LinkedHashSet;
34import java.util.LinkedList;
35import java.util.List;
36import java.util.Optional;
37import java.util.Set;
38import java.util.concurrent.ConcurrentLinkedDeque;
39import java.util.stream.Collectors;
40import java.util.stream.Stream;
41
42import static com.sun.tools.jdeps.Analyzer.Type.CLASS;
43import static com.sun.tools.jdeps.Analyzer.Type.VERBOSE;
44import static com.sun.tools.jdeps.Module.trace;
45import 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 */
60public 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(this::include)
172                .filter(source -> !filter.requiresFilter().contains(source.getName()))
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        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) {
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    /*
261     * Tests if the given archive is requested for analysis.
262     * It includes the root modules specified in --module, --add-modules
263     * or modules specified on the command line
264     *
265     * This filters system module by default unless they are explicitly
266     * requested.
267     */
268    public boolean include(Archive source) {
269        Module module = source.getModule();
270        // skip system module by default
271        return  !module.isSystem()
272                    || configuration.rootModules().contains(source);
273    }
274
275    // ----- for testing purpose -----
276
277    public static enum Info {
278        REQUIRES,
279        REQUIRES_TRANSITIVE,
280        EXPORTED_API,
281        MODULE_PRIVATE,
282        QUALIFIED_EXPORTED_API,
283        INTERNAL_API,
284        JDK_INTERNAL_API,
285        JDK_REMOVED_INTERNAL_API
286    }
287
288    public static class Node {
289        public final String name;
290        public final String source;
291        public final Info info;
292        Node(String name, Info info) {
293            this(name, name, info);
294        }
295        Node(String name, String source, Info info) {
296            this.name = name;
297            this.source = source;
298            this.info = info;
299        }
300
301        @Override
302        public String toString() {
303            StringBuilder sb = new StringBuilder();
304            if (info != Info.REQUIRES && info != Info.REQUIRES_TRANSITIVE)
305                sb.append(source).append("/");
306
307            sb.append(name);
308            if (info == Info.QUALIFIED_EXPORTED_API)
309                sb.append(" (qualified)");
310            else if (info == Info.JDK_INTERNAL_API)
311                sb.append(" (JDK internal)");
312            else if (info == Info.INTERNAL_API)
313                sb.append(" (internal)");
314            return sb.toString();
315        }
316
317        @Override
318        public boolean equals(Object o) {
319            if (!(o instanceof Node))
320                return false;
321
322            Node other = (Node)o;
323            return this.name.equals(other.name) &&
324                    this.source.equals(other.source) &&
325                    this.info.equals(other.info);
326        }
327
328        @Override
329        public int hashCode() {
330            int result = name.hashCode();
331            result = 31 * result + source.hashCode();
332            result = 31 * result + info.hashCode();
333            return result;
334        }
335    }
336
337    /**
338     * Returns a graph of module dependences.
339     *
340     * Each Node represents a module and each edge is a dependence.
341     * No analysis on "requires transitive".
342     */
343    public Graph<Node> moduleGraph() {
344        Graph.Builder<Node> builder = new Graph.Builder<>();
345
346        archives().stream()
347            .forEach(m -> {
348                Node u = new Node(m.getName(), Info.REQUIRES);
349                builder.addNode(u);
350                analyzer.requires(m)
351                    .map(req -> new Node(req.getName(), Info.REQUIRES))
352                    .forEach(v -> builder.addEdge(u, v));
353            });
354        return builder.build();
355    }
356
357    /**
358     * Returns a graph of dependences.
359     *
360     * Each Node represents a class or package per the specified verbose level.
361     * Each edge indicates
362     */
363    public Graph<Node> dependenceGraph() {
364        Graph.Builder<Node> builder = new Graph.Builder<>();
365
366        archives().stream()
367            .map(analyzer.results::get)
368            .filter(deps -> !deps.dependencies().isEmpty())
369            .flatMap(deps -> deps.dependencies().stream())
370            .forEach(d -> addEdge(builder, d));
371        return builder.build();
372    }
373
374    private void addEdge(Graph.Builder<Node> builder, Analyzer.Dep dep) {
375        Archive source = dep.originArchive();
376        Archive target = dep.targetArchive();
377        String pn = dep.target();
378        if (verbose == CLASS || verbose == VERBOSE) {
379            int i = dep.target().lastIndexOf('.');
380            pn = i > 0 ? dep.target().substring(0, i) : "";
381        }
382        final Info info;
383        Module targetModule = target.getModule();
384        if (source == target) {
385            info = Info.MODULE_PRIVATE;
386        } else if (!targetModule.isNamed()) {
387            info = Info.EXPORTED_API;
388        } else if (targetModule.isExported(pn) && !targetModule.isJDKUnsupported()) {
389            info = Info.EXPORTED_API;
390        } else {
391            Module module = target.getModule();
392            if (module == Analyzer.REMOVED_JDK_INTERNALS) {
393                info = Info.JDK_REMOVED_INTERNAL_API;
394            } else if (!source.getModule().isJDK() && module.isJDK())
395                info = Info.JDK_INTERNAL_API;
396                // qualified exports or inaccessible
397            else if (module.isExported(pn, source.getModule().name()))
398                info = Info.QUALIFIED_EXPORTED_API;
399            else
400                info = Info.INTERNAL_API;
401        }
402
403        Node u = new Node(dep.origin(), source.getName(), info);
404        Node v = new Node(dep.target(), target.getName(), info);
405        builder.addEdge(u, v);
406    }
407
408}
409