1/*
2 * Copyright (c) 2017, 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 jdk.internal.module;
27
28import java.io.PrintStream;
29import java.lang.module.Configuration;
30import java.lang.module.ResolvedModule;
31import java.net.URI;
32import java.nio.file.Path;
33import java.nio.file.Paths;
34import java.util.ArrayDeque;
35import java.util.Collections;
36import java.util.Deque;
37import java.util.HashMap;
38import java.util.HashSet;
39import java.util.LinkedList;
40import java.util.Map;
41import java.util.Set;
42import java.util.function.Consumer;
43import java.util.function.Function;
44import java.util.stream.Stream;
45import static java.util.stream.Collectors.*;
46
47/**
48 * A Builder to compute ModuleHashes from a given configuration
49 */
50public class ModuleHashesBuilder {
51    private final Configuration configuration;
52    private final Set<String> hashModuleCandidates;
53
54    /**
55     * Constructs a ModuleHashesBuilder that finds the packaged modules
56     * from the location of ModuleReference found from the given Configuration.
57     *
58     * @param config Configuration for building module hashes
59     * @param modules the candidate modules to be hashed
60     */
61    public ModuleHashesBuilder(Configuration config, Set<String> modules) {
62        this.configuration = config;
63        this.hashModuleCandidates = modules;
64    }
65
66    /**
67     * Returns a map of a module M to ModuleHashes for the modules
68     * that depend upon M directly or indirectly.
69     *
70     * The key for each entry in the returned map is a module M that has
71     * no outgoing edges to any of the candidate modules to be hashed
72     * i.e. M is a leaf node in a connected subgraph containing M and
73     * other candidate modules from the module graph filtering
74     * the outgoing edges from M to non-candidate modules.
75     */
76    public Map<String, ModuleHashes> computeHashes(Set<String> roots) {
77        // build a graph containing the the packaged modules and
78        // its transitive dependences matching --hash-modules
79        Graph.Builder<String> builder = new Graph.Builder<>();
80        Deque<ResolvedModule> deque = new ArrayDeque<>(configuration.modules());
81        Set<ResolvedModule> visited = new HashSet<>();
82        while (!deque.isEmpty()) {
83            ResolvedModule rm = deque.pop();
84            if (!visited.contains(rm)) {
85                visited.add(rm);
86                builder.addNode(rm.name());
87                for (ResolvedModule dm : rm.reads()) {
88                    if (!visited.contains(dm)) {
89                        deque.push(dm);
90                    }
91                    builder.addEdge(rm.name(), dm.name());
92                }
93            }
94        }
95
96        // each node in a transposed graph is a matching packaged module
97        // in which the hash of the modules that depend upon it is recorded
98        Graph<String> transposedGraph = builder.build().transpose();
99
100        // traverse the modules in topological order that will identify
101        // the modules to record the hashes - it is the first matching
102        // module and has not been hashed during the traversal.
103        Set<String> mods = new HashSet<>();
104        Map<String, ModuleHashes> hashes = new HashMap<>();
105        builder.build()
106               .orderedNodes()
107               .filter(mn -> roots.contains(mn) && !mods.contains(mn))
108               .forEach(mn -> {
109                   // Compute hashes of the modules that depend on mn directly and
110                   // indirectly excluding itself.
111                   Set<String> ns = transposedGraph.dfs(mn)
112                       .stream()
113                       .filter(n -> !n.equals(mn) && hashModuleCandidates.contains(n))
114                       .collect(toSet());
115                   mods.add(mn);
116                   mods.addAll(ns);
117
118                   if (!ns.isEmpty()) {
119                       Map<String, Path> moduleToPath = ns.stream()
120                           .collect(toMap(Function.identity(), this::moduleToPath));
121                       hashes.put(mn, ModuleHashes.generate(moduleToPath, "SHA-256"));
122                   }
123               });
124        return hashes;
125    }
126
127    private Path moduleToPath(String name) {
128        ResolvedModule rm = configuration.findModule(name).orElseThrow(
129            () -> new InternalError("Selected module " + name + " not on module path"));
130
131        URI uri = rm.reference().location().get();
132        Path path = Paths.get(uri);
133        String fn = path.getFileName().toString();
134        if (!fn.endsWith(".jar") && !fn.endsWith(".jmod")) {
135            throw new UnsupportedOperationException(path + " is not a modular JAR or jmod file");
136        }
137        return path;
138    }
139
140    /*
141     * Utility class
142     */
143    static class Graph<T> {
144        private final Set<T> nodes;
145        private final Map<T, Set<T>> edges;
146
147        public Graph(Set<T> nodes, Map<T, Set<T>> edges) {
148            this.nodes = Collections.unmodifiableSet(nodes);
149            this.edges = Collections.unmodifiableMap(edges);
150        }
151
152        public Set<T> nodes() {
153            return nodes;
154        }
155
156        public Map<T, Set<T>> edges() {
157            return edges;
158        }
159
160        public Set<T> adjacentNodes(T u) {
161            return edges.get(u);
162        }
163
164        public boolean contains(T u) {
165            return nodes.contains(u);
166        }
167
168        /**
169         * Returns nodes sorted in topological order.
170         */
171        public Stream<T> orderedNodes() {
172            TopoSorter<T> sorter = new TopoSorter<>(this);
173            return sorter.result.stream();
174        }
175
176        /**
177         * Traverse this graph and performs the given action in topological order
178         */
179        public void ordered(Consumer<T> action) {
180            TopoSorter<T> sorter = new TopoSorter<>(this);
181            sorter.ordered(action);
182        }
183
184        /**
185         * Traverses this graph and performs the given action in reverse topological order
186         */
187        public void reverse(Consumer<T> action) {
188            TopoSorter<T> sorter = new TopoSorter<>(this);
189            sorter.reverse(action);
190        }
191
192        /**
193         * Returns a transposed graph from this graph
194         */
195        public Graph<T> transpose() {
196            Builder<T> builder = new Builder<>();
197            nodes.stream().forEach(builder::addNode);
198            // reverse edges
199            edges.keySet().forEach(u -> {
200                edges.get(u).stream()
201                    .forEach(v -> builder.addEdge(v, u));
202            });
203            return builder.build();
204        }
205
206        /**
207         * Returns all nodes reachable from the given root.
208         */
209        public Set<T> dfs(T root) {
210            return dfs(Set.of(root));
211        }
212
213        /**
214         * Returns all nodes reachable from the given set of roots.
215         */
216        public Set<T> dfs(Set<T> roots) {
217            Deque<T> deque = new LinkedList<>(roots);
218            Set<T> visited = new HashSet<>();
219            while (!deque.isEmpty()) {
220                T u = deque.pop();
221                if (!visited.contains(u)) {
222                    visited.add(u);
223                    if (contains(u)) {
224                        adjacentNodes(u).stream()
225                            .filter(v -> !visited.contains(v))
226                            .forEach(deque::push);
227                    }
228                }
229            }
230            return visited;
231        }
232
233        public void printGraph(PrintStream out) {
234            out.println("graph for " + nodes);
235            nodes.stream()
236                .forEach(u -> adjacentNodes(u).stream()
237                    .forEach(v -> out.format("  %s -> %s%n", u, v)));
238        }
239
240        static class Builder<T> {
241            final Set<T> nodes = new HashSet<>();
242            final Map<T, Set<T>> edges = new HashMap<>();
243
244            public void addNode(T node) {
245                if (nodes.contains(node)) {
246                    return;
247                }
248                nodes.add(node);
249                edges.computeIfAbsent(node, _e -> new HashSet<>());
250            }
251
252            public void addEdge(T u, T v) {
253                addNode(u);
254                addNode(v);
255                edges.get(u).add(v);
256            }
257
258            public Graph<T> build() {
259                return new Graph<T>(nodes, edges);
260            }
261        }
262    }
263
264    /**
265     * Topological sort
266     */
267    private static class TopoSorter<T> {
268        final Deque<T> result = new LinkedList<>();
269        final Deque<T> nodes;
270        final Graph<T> graph;
271
272        TopoSorter(Graph<T> graph) {
273            this.graph = graph;
274            this.nodes = new LinkedList<>(graph.nodes);
275            sort();
276        }
277
278        public void ordered(Consumer<T> action) {
279            result.iterator().forEachRemaining(action);
280        }
281
282        public void reverse(Consumer<T> action) {
283            result.descendingIterator().forEachRemaining(action);
284        }
285
286        private void sort() {
287            Deque<T> visited = new LinkedList<>();
288            Deque<T> done = new LinkedList<>();
289            T node;
290            while ((node = nodes.poll()) != null) {
291                if (!visited.contains(node)) {
292                    visit(node, visited, done);
293                }
294            }
295        }
296
297        private void visit(T node, Deque<T> visited, Deque<T> done) {
298            if (visited.contains(node)) {
299                if (!done.contains(node)) {
300                    throw new IllegalArgumentException("Cyclic detected: " +
301                        node + " " + graph.edges().get(node));
302                }
303                return;
304            }
305            visited.add(node);
306            graph.edges().get(node).stream()
307                .forEach(x -> visit(x, visited, done));
308            done.add(node);
309            result.addLast(node);
310        }
311    }
312}
313