Back to index...

	/*
	* Copyright (c) 2017, 2018, Oracle and/or its affiliates. All rights reserved.
	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
	*
	* This code is free software; you can redistribute it and/or modify it
	* under the terms of the GNU General Public License version 2 only, as
	* published by the Free Software Foundation. Oracle designates this
	* particular file as subject to the "Classpath" exception as provided
	* by Oracle in the LICENSE file that accompanied this code.
	*
	* This code is distributed in the hope that it will be useful, but WITHOUT
	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	* version 2 for more details (a copy is included in the LICENSE file that
	* accompanied this code).
	*
	* You should have received a copy of the GNU General Public License version
	* 2 along with this work; if not, write to the Free Software Foundation,
	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
	*
	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
	* or visit www.oracle.com if you need additional information or have any
	* questions.
	*/

	package jdk.internal.module;

	import java.io.PrintStream;
	import java.lang.module.Configuration;
	import java.lang.module.ResolvedModule;
	import java.net.URI;
	import java.nio.file.Path;
	import java.util.ArrayDeque;
	import java.util.Collections;
	import java.util.Deque;
	import java.util.HashMap;
	import java.util.HashSet;
	import java.util.Map;
	import java.util.Set;
	import java.util.function.Consumer;
	import java.util.function.Function;
	import java.util.stream.Stream;
	import static java.util.stream.Collectors.*;

	/**
	* A Builder to compute ModuleHashes from a given configuration
	*/
	public class ModuleHashesBuilder {
	private final Configuration configuration;
	private final Set<String> hashModuleCandidates;

	/**
	* Constructs a ModuleHashesBuilder that finds the packaged modules
	* from the location of ModuleReference found from the given Configuration.
	*
	* @param config Configuration for building module hashes
	* @param modules the candidate modules to be hashed
	*/
	public ModuleHashesBuilder(Configuration config, Set<String> modules) {
	this.configuration = config;
	this.hashModuleCandidates = modules;
	}

	/**
	* Returns a map of a module M to ModuleHashes for the modules
	* that depend upon M directly or indirectly.
	*
	* The key for each entry in the returned map is a module M that has
	* no outgoing edges to any of the candidate modules to be hashed
	* i.e. M is a leaf node in a connected subgraph containing M and
	* other candidate modules from the module graph filtering
	* the outgoing edges from M to non-candidate modules.
	*/
	public Map<String, ModuleHashes> computeHashes(Set<String> roots) {
	// build a graph containing the packaged modules and
	// its transitive dependences matching --hash-modules
	Graph.Builder<String> builder = new Graph.Builder<>();
	Deque<ResolvedModule> todo = new ArrayDeque<>(configuration.modules());
	Set<ResolvedModule> visited = new HashSet<>();
	ResolvedModule rm;
	while ((rm = todo.poll()) != null) {
	if (visited.add(rm)) {
	builder.addNode(rm.name());
	for (ResolvedModule dm : rm.reads()) {
	if (!visited.contains(dm)) {
	todo.push(dm);
	}
	builder.addEdge(rm.name(), dm.name());
	}
	}
	}

	// each node in a transposed graph is a matching packaged module
	// in which the hash of the modules that depend upon it is recorded
	Graph<String> transposedGraph = builder.build().transpose();

	// traverse the modules in topological order that will identify
	// the modules to record the hashes - it is the first matching
	// module and has not been hashed during the traversal.
	Set<String> mods = new HashSet<>();
	Map<String, ModuleHashes> hashes = new HashMap<>();
	builder.build()
	.orderedNodes()
	.filter(mn -> roots.contains(mn) && !mods.contains(mn))
	.forEach(mn -> {
	// Compute hashes of the modules that depend on mn directly and
	// indirectly excluding itself.
	Set<String> ns = transposedGraph.dfs(mn)
	.stream()
	.filter(n -> !n.equals(mn) && hashModuleCandidates.contains(n))
	.collect(toSet());
	mods.add(mn);
	mods.addAll(ns);

	if (!ns.isEmpty()) {
	Map<String, Path> moduleToPath = ns.stream()
	.collect(toMap(Function.identity(), this::moduleToPath));
	hashes.put(mn, ModuleHashes.generate(moduleToPath, "SHA-256"));
	}
	});
	return hashes;
	}

	private Path moduleToPath(String name) {
	ResolvedModule rm = configuration.findModule(name).orElseThrow(
	() -> new InternalError("Selected module " + name + " not on module path"));

	URI uri = rm.reference().location().get();
	Path path = Path.of(uri);
	String fn = path.getFileName().toString();
	if (!fn.endsWith(".jar") && !fn.endsWith(".jmod")) {
	throw new UnsupportedOperationException(path + " is not a modular JAR or jmod file");
	}
	return path;
	}

	/*
	* Utility class
	*/
	static class Graph<T> {
	private final Set<T> nodes;
	private final Map<T, Set<T>> edges;

	public Graph(Set<T> nodes, Map<T, Set<T>> edges) {
	this.nodes = Collections.unmodifiableSet(nodes);
	this.edges = Collections.unmodifiableMap(edges);
	}

	public Set<T> nodes() {
	return nodes;
	}

	public Map<T, Set<T>> edges() {
	return edges;
	}

	public Set<T> adjacentNodes(T u) {
	return edges.get(u);
	}

	public boolean contains(T u) {
	return nodes.contains(u);
	}

	/**
	* Returns nodes sorted in topological order.
	*/
	public Stream<T> orderedNodes() {
	TopoSorter<T> sorter = new TopoSorter<>(this);
	return sorter.result.stream();
	}

	/**
	* Traverses this graph and performs the given action in topological order.
	*/
	public void ordered(Consumer<T> action) {
	TopoSorter<T> sorter = new TopoSorter<>(this);
	sorter.ordered(action);
	}

	/**
	* Traverses this graph and performs the given action in reverse topological order.
	*/
	public void reverse(Consumer<T> action) {
	TopoSorter<T> sorter = new TopoSorter<>(this);
	sorter.reverse(action);
	}

	/**
	* Returns a transposed graph from this graph.
	*/
	public Graph<T> transpose() {
	Builder<T> builder = new Builder<>();
	nodes.forEach(builder::addNode);
	// reverse edges
	edges.keySet().forEach(u -> {
	edges.get(u).forEach(v -> builder.addEdge(v, u));
	});
	return builder.build();
	}

	/**
	* Returns all nodes reachable from the given root.
	*/
	public Set<T> dfs(T root) {
	return dfs(Set.of(root));
	}

	/**
	* Returns all nodes reachable from the given set of roots.
	*/
	public Set<T> dfs(Set<T> roots) {
	ArrayDeque<T> todo = new ArrayDeque<>(roots);
	Set<T> visited = new HashSet<>();
	T u;
	while ((u = todo.poll()) != null) {
	if (visited.add(u) && contains(u)) {
	adjacentNodes(u).stream()
	.filter(v -> !visited.contains(v))
	.forEach(todo::push);
	}
	}
	return visited;
	}

	public void printGraph(PrintStream out) {
	out.println("graph for " + nodes);
	nodes
	.forEach(u -> adjacentNodes(u)
	.forEach(v -> out.format(" %s -> %s%n", u, v)));
	}

	static class Builder<T> {
	final Set<T> nodes = new HashSet<>();
	final Map<T, Set<T>> edges = new HashMap<>();

	public void addNode(T node) {
	if (nodes.add(node)) {
	edges.computeIfAbsent(node, _e -> new HashSet<>());
	}
	}

	public void addEdge(T u, T v) {
	addNode(u);
	addNode(v);
	edges.get(u).add(v);
	}

	public Graph<T> build() {
	return new Graph<T>(nodes, edges);
	}
	}
	}

	/**
	* Topological sort
	*/
	private static class TopoSorter<T> {
	final Deque<T> result = new ArrayDeque<>();
	final Graph<T> graph;

	TopoSorter(Graph<T> graph) {
	this.graph = graph;
	sort();
	}

	public void ordered(Consumer<T> action) {
	result.forEach(action);
	}

	public void reverse(Consumer<T> action) {
	result.descendingIterator().forEachRemaining(action);
	}

	private void sort() {
	Set<T> visited = new HashSet<>();
	Deque<T> stack = new ArrayDeque<>();
	graph.nodes.forEach(node -> visit(node, visited, stack));
	}

	private Set<T> children(T node) {
	return graph.edges().get(node);
	}

	private void visit(T node, Set<T> visited, Deque<T> stack) {
	if (visited.add(node)) {
	stack.push(node);
	children(node).forEach(child -> visit(child, visited, stack));
	stack.pop();
	result.addLast(node);
	}
	else if (stack.contains(node)) {
	throw new IllegalArgumentException(
	"Cycle detected: " + node + " -> " + children(node));
	}
	}
	}
	}

Back to index...