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 static com.sun.tools.jdeps.JdepsFilter.DEFAULT_FILTER;
29import static com.sun.tools.jdeps.Module.trace;
30import static com.sun.tools.jdeps.Graph.*;
31
32import java.lang.module.ModuleDescriptor.Requires;
33import java.io.IOException;
34import java.util.Collections;
35import java.util.Deque;
36import java.util.HashMap;
37import java.util.HashSet;
38import java.util.LinkedList;
39import java.util.Map;
40import java.util.Optional;
41import java.util.Set;
42import java.util.stream.Collectors;
43import java.util.stream.Stream;
44
45/**
46 * Inverse transitive dependency analysis (compile-time view)
47 */
48public 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
144            configuration.getModules().values().stream()
145                .forEach(m -> {
146                    builder.addNode(m);
147                    m.descriptor().requires().stream()
148                        .map(Requires::name)
149                        .map(configuration::findModule)  // must be present
150                        .forEach(v -> builder.addEdge(v.get(), m));
151                });
152
153            // add the dependences from the analysis
154            Map<Archive, Set<Archive>> dependences = dependencyFinder.dependences();
155            dependences.entrySet().stream()
156                .forEach(e -> {
157                    Archive u = e.getKey();
158                    builder.addNode(u);
159                    e.getValue().forEach(v -> builder.addEdge(v, u));
160                });
161
162            // transposed dependence graph.
163            Graph<Archive> graph = builder.build();
164            trace("targets: %s%n", targets());
165
166            // Traverse from the targets and find all paths
167            // rebuild a graph with all nodes that depends on targets
168            // targets directly and indirectly
169            return targets().stream()
170                .map(t -> findPaths(graph, t))
171                .flatMap(Set::stream)
172                .collect(Collectors.toSet());
173        } finally {
174            dependencyFinder.shutdown();
175        }
176    }
177
178    /**
179     * Returns all paths reachable from the given targets.
180     */
181    private Set<Deque<Archive>> findPaths(Graph<Archive> graph, Archive target) {
182
183        // path is in reversed order
184        Deque<Archive> path = new LinkedList<>();
185        path.push(target);
186
187        Set<Edge<Archive>> visited = new HashSet<>();
188
189        Deque<Edge<Archive>> deque = new LinkedList<>();
190        deque.addAll(graph.edgesFrom(target));
191        if (deque.isEmpty()) {
192            return makePaths(path).collect(Collectors.toSet());
193        }
194
195        Set<Deque<Archive>> allPaths = new HashSet<>();
196        while (!deque.isEmpty()) {
197            Edge<Archive> edge = deque.pop();
198
199            if (visited.contains(edge))
200                continue;
201
202            Archive node = edge.v;
203            path.addLast(node);
204            visited.add(edge);
205
206            Set<Edge<Archive>> unvisitedDeps = graph.edgesFrom(node)
207                    .stream()
208                    .filter(e -> !visited.contains(e))
209                    .collect(Collectors.toSet());
210
211            trace("visiting %s %s (%s)%n", edge, path, unvisitedDeps);
212            if (unvisitedDeps.isEmpty()) {
213                makePaths(path).forEach(allPaths::add);
214                path.removeLast();
215            }
216
217            // push unvisited adjacent edges
218            unvisitedDeps.stream().forEach(deque::push);
219
220
221            // when the adjacent edges of a node are visited, pop it from the path
222            while (!path.isEmpty()) {
223                if (visited.containsAll(graph.edgesFrom(path.peekLast())))
224                    path.removeLast();
225                else
226                    break;
227            }
228        }
229
230       return allPaths;
231    }
232
233    /**
234     * Prepend end point to the path
235     */
236    private Stream<Deque<Archive>> makePaths(Deque<Archive> path) {
237        Set<Archive> nodes = endPoints.get(path.peekFirst());
238        if (nodes == null || nodes.isEmpty()) {
239            return Stream.of(new LinkedList<>(path));
240        } else {
241            return nodes.stream().map(n -> {
242                Deque<Archive> newPath = new LinkedList<>();
243                newPath.addFirst(n);
244                newPath.addAll(path);
245                return newPath;
246            });
247        }
248    }
249}
250