/* * Copyright (c) 2013, 2017, 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 java.lang.module; import java.io.PrintStream; import java.lang.module.ModuleDescriptor.Provides; import java.lang.module.ModuleDescriptor.Requires.Modifier; import java.net.URI; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.Collection; import java.util.Deque; import java.util.HashMap; import java.util.HashSet; import java.util.LinkedHashSet; import java.util.List; import java.util.Map; import java.util.Optional; import java.util.Set; import java.util.stream.Collectors; import jdk.internal.module.ModuleHashes; import jdk.internal.module.ModuleReferenceImpl; import jdk.internal.module.ModuleTarget; /** * The resolver used by {@link Configuration#resolve} and {@link * Configuration#resolveAndBind}. * * @implNote The resolver is used at VM startup and so deliberately avoids * using lambda and stream usages in code paths used during startup. */ final class Resolver { private final ModuleFinder beforeFinder; private final List parents; private final ModuleFinder afterFinder; private final PrintStream traceOutput; // maps module name to module reference private final Map nameToReference = new HashMap<>(); // true if all automatic modules have been found private boolean haveAllAutomaticModules; // constraint on target platform private String targetPlatform; String targetPlatform() { return targetPlatform; } /** * @throws IllegalArgumentException if there are more than one parent and * the constraints on the target platform conflict */ Resolver(ModuleFinder beforeFinder, List parents, ModuleFinder afterFinder, PrintStream traceOutput) { this.beforeFinder = beforeFinder; this.parents = parents; this.afterFinder = afterFinder; this.traceOutput = traceOutput; // record constraint on target platform, checking for conflicts for (Configuration parent : parents) { String value = parent.targetPlatform(); if (value != null) { if (targetPlatform == null) { targetPlatform = value; } else { if (!value.equals(targetPlatform)) { String msg = "Parents have conflicting constraints on target" + " platform: " + targetPlatform + ", " + value; throw new IllegalArgumentException(msg); } } } } } /** * Resolves the given named modules. * * @throws ResolutionException */ Resolver resolve(Collection roots) { // create the visit stack to get us started Deque q = new ArrayDeque<>(); for (String root : roots) { // find root module ModuleReference mref = findWithBeforeFinder(root); if (mref == null) { if (findInParent(root) != null) { // in parent, nothing to do continue; } mref = findWithAfterFinder(root); if (mref == null) { findFail("Module %s not found", root); } } if (isTracing()) { trace("root %s", nameAndInfo(mref)); } addFoundModule(mref); q.push(mref.descriptor()); } resolve(q); return this; } /** * Resolve all modules in the given queue. On completion the queue will be * empty and any resolved modules will be added to {@code nameToReference}. * * @return The set of module resolved by this invocation of resolve */ private Set resolve(Deque q) { Set resolved = new HashSet<>(); while (!q.isEmpty()) { ModuleDescriptor descriptor = q.poll(); assert nameToReference.containsKey(descriptor.name()); // if the module is an automatic module then all automatic // modules need to be resolved if (descriptor.isAutomatic() && !haveAllAutomaticModules) { addFoundAutomaticModules().forEach(mref -> { ModuleDescriptor other = mref.descriptor(); q.offer(other); if (isTracing()) { trace("%s requires %s", descriptor.name(), nameAndInfo(mref)); } }); haveAllAutomaticModules = true; } // process dependences for (ModuleDescriptor.Requires requires : descriptor.requires()) { // only required at compile-time if (requires.modifiers().contains(Modifier.STATIC)) continue; String dn = requires.name(); // find dependence ModuleReference mref = findWithBeforeFinder(dn); if (mref == null) { if (findInParent(dn) != null) { // dependence is in parent continue; } mref = findWithAfterFinder(dn); if (mref == null) { findFail("Module %s not found, required by %s", dn, descriptor.name()); } } if (isTracing() && !dn.equals("java.base")) { trace("%s requires %s", descriptor.name(), nameAndInfo(mref)); } if (!nameToReference.containsKey(dn)) { addFoundModule(mref); q.offer(mref.descriptor()); } } resolved.add(descriptor); } return resolved; } /** * Augments the set of resolved modules with modules induced by the * service-use relation. */ Resolver bind() { // Scan the finders for all available service provider modules. As // java.base uses services then the module finders will be scanned // anyway. Map> availableProviders = new HashMap<>(); for (ModuleReference mref : findAll()) { ModuleDescriptor descriptor = mref.descriptor(); if (!descriptor.provides().isEmpty()) { for (Provides provides : descriptor.provides()) { String sn = provides.service(); // computeIfAbsent Set providers = availableProviders.get(sn); if (providers == null) { providers = new HashSet<>(); availableProviders.put(sn, providers); } providers.add(mref); } } } // create the visit stack Deque q = new ArrayDeque<>(); // the initial set of modules that may use services Set initialConsumers; if (ModuleLayer.boot() == null) { initialConsumers = new HashSet<>(); } else { initialConsumers = parents.stream() .flatMap(Configuration::configurations) .distinct() .flatMap(c -> c.descriptors().stream()) .collect(Collectors.toSet()); } for (ModuleReference mref : nameToReference.values()) { initialConsumers.add(mref.descriptor()); } // Where there is a consumer of a service then resolve all modules // that provide an implementation of that service Set candidateConsumers = initialConsumers; do { for (ModuleDescriptor descriptor : candidateConsumers) { if (!descriptor.uses().isEmpty()) { // the modules that provide at least one service Set modulesToBind = null; if (isTracing()) { modulesToBind = new HashSet<>(); } for (String service : descriptor.uses()) { Set mrefs = availableProviders.get(service); if (mrefs != null) { for (ModuleReference mref : mrefs) { ModuleDescriptor provider = mref.descriptor(); if (!provider.equals(descriptor)) { if (isTracing() && modulesToBind.add(provider)) { trace("%s binds %s", descriptor.name(), nameAndInfo(mref)); } String pn = provider.name(); if (!nameToReference.containsKey(pn)) { addFoundModule(mref); q.push(provider); } } } } } } } candidateConsumers = resolve(q); } while (!candidateConsumers.isEmpty()); return this; } /** * Add all automatic modules that have not already been found to the * nameToReference map. */ private Set addFoundAutomaticModules() { Set result = new HashSet<>(); findAll().forEach(mref -> { String mn = mref.descriptor().name(); if (mref.descriptor().isAutomatic() && !nameToReference.containsKey(mn)) { addFoundModule(mref); result.add(mref); } }); return result; } /** * Add the module to the nameToReference map. Also check any constraints on * the target platform with the constraints of other modules. */ private void addFoundModule(ModuleReference mref) { String mn = mref.descriptor().name(); if (mref instanceof ModuleReferenceImpl) { ModuleTarget target = ((ModuleReferenceImpl)mref).moduleTarget(); if (target != null) checkTargetPlatform(mn, target); } nameToReference.put(mn, mref); } /** * Check that the module's constraints on the target platform does * conflict with the constraint of other modules resolved so far. */ private void checkTargetPlatform(String mn, ModuleTarget target) { String value = target.targetPlatform(); if (value != null) { if (targetPlatform == null) { targetPlatform = value; } else { if (!value.equals(targetPlatform)) { findFail("Module %s has constraints on target platform (%s)" + " that conflict with other modules: %s", mn, value, targetPlatform); } } } } /** * Execute post-resolution checks and returns the module graph of resolved * modules as a map. */ Map> finish(Configuration cf) { detectCycles(); checkHashes(); Map> graph = makeGraph(cf); checkExportSuppliers(graph); return graph; } /** * Checks the given module graph for cycles. * * For now the implementation is a simple depth first search on the * dependency graph. We'll replace this later, maybe with Tarjan. */ private void detectCycles() { visited = new HashSet<>(); visitPath = new LinkedHashSet<>(); // preserve insertion order for (ModuleReference mref : nameToReference.values()) { visit(mref.descriptor()); } visited.clear(); } // the modules that were visited private Set visited; // the modules in the current visit path private Set visitPath; private void visit(ModuleDescriptor descriptor) { if (!visited.contains(descriptor)) { boolean added = visitPath.add(descriptor); if (!added) { resolveFail("Cycle detected: %s", cycleAsString(descriptor)); } for (ModuleDescriptor.Requires requires : descriptor.requires()) { String dn = requires.name(); ModuleReference mref = nameToReference.get(dn); if (mref != null) { ModuleDescriptor other = mref.descriptor(); if (other != descriptor) { // dependency is in this configuration visit(other); } } } visitPath.remove(descriptor); visited.add(descriptor); } } /** * Returns a String with a list of the modules in a detected cycle. */ private String cycleAsString(ModuleDescriptor descriptor) { List list = new ArrayList<>(visitPath); list.add(descriptor); int index = list.indexOf(descriptor); return list.stream() .skip(index) .map(ModuleDescriptor::name) .collect(Collectors.joining(" -> ")); } /** * Checks the hashes in the module descriptor to ensure that they match * any recorded hashes. */ private void checkHashes() { for (ModuleReference mref : nameToReference.values()) { // get the recorded hashes, if any if (!(mref instanceof ModuleReferenceImpl)) continue; ModuleHashes hashes = ((ModuleReferenceImpl)mref).recordedHashes(); if (hashes == null) continue; ModuleDescriptor descriptor = mref.descriptor(); String algorithm = hashes.algorithm(); for (String dn : hashes.names()) { ModuleReference mref2 = nameToReference.get(dn); if (mref2 == null) { ResolvedModule resolvedModule = findInParent(dn); if (resolvedModule != null) mref2 = resolvedModule.reference(); } if (mref2 == null) continue; if (!(mref2 instanceof ModuleReferenceImpl)) { findFail("Unable to compute the hash of module %s", dn); } ModuleReferenceImpl other = (ModuleReferenceImpl)mref2; if (other != null) { byte[] recordedHash = hashes.hashFor(dn); byte[] actualHash = other.computeHash(algorithm); if (actualHash == null) findFail("Unable to compute the hash of module %s", dn); if (!Arrays.equals(recordedHash, actualHash)) { findFail("Hash of %s (%s) differs to expected hash (%s)" + " recorded in %s", dn, toHexString(actualHash), toHexString(recordedHash), descriptor.name()); } } } } } private static String toHexString(byte[] ba) { StringBuilder sb = new StringBuilder(ba.length * 2); for (byte b: ba) { sb.append(String.format("%02x", b & 0xff)); } return sb.toString(); } /** * Computes the readability graph for the modules in the given Configuration. * * The readability graph is created by propagating "requires" through the * "requires transitive" edges of the module dependence graph. So if the * module dependence graph has m1 requires m2 && m2 requires transitive m3 * then the resulting readability graph will contain m1 reads m2, m1 reads m3, * and m2 reads m3. */ private Map> makeGraph(Configuration cf) { // initial capacity of maps to avoid resizing int capacity = 1 + (4 * nameToReference.size())/ 3; // the "reads" graph starts as a module dependence graph and // is iteratively updated to be the readability graph Map> g1 = new HashMap<>(capacity); // the "requires transitive" graph, contains requires transitive edges only Map> g2; // need "requires transitive" from the modules in parent configurations // as there may be selected modules that have a dependency on modules in // the parent configuration. if (ModuleLayer.boot() == null) { g2 = new HashMap<>(capacity); } else { g2 = parents.stream() .flatMap(Configuration::configurations) .distinct() .flatMap(c -> c.modules().stream().flatMap(m1 -> m1.descriptor().requires().stream() .filter(r -> r.modifiers().contains(Modifier.TRANSITIVE)) .flatMap(r -> { Optional m2 = c.findModule(r.name()); assert m2.isPresent() || r.modifiers().contains(Modifier.STATIC); return m2.stream(); }) .map(m2 -> Map.entry(m1, m2)) ) ) // stream of m1->m2 .collect(Collectors.groupingBy(Map.Entry::getKey, HashMap::new, Collectors.mapping(Map.Entry::getValue, Collectors.toSet()) )); } // populate g1 and g2 with the dependences from the selected modules Map nameToResolved = new HashMap<>(capacity); for (ModuleReference mref : nameToReference.values()) { ModuleDescriptor descriptor = mref.descriptor(); String name = descriptor.name(); ResolvedModule m1 = computeIfAbsent(nameToResolved, name, cf, mref); Set reads = new HashSet<>(); Set requiresTransitive = new HashSet<>(); for (ModuleDescriptor.Requires requires : descriptor.requires()) { String dn = requires.name(); ResolvedModule m2 = null; ModuleReference mref2 = nameToReference.get(dn); if (mref2 != null) { // same configuration m2 = computeIfAbsent(nameToResolved, dn, cf, mref2); } else { // parent configuration m2 = findInParent(dn); if (m2 == null) { assert requires.modifiers().contains(Modifier.STATIC); continue; } } // m1 requires m2 => m1 reads m2 reads.add(m2); // m1 requires transitive m2 if (requires.modifiers().contains(Modifier.TRANSITIVE)) { requiresTransitive.add(m2); } } // automatic modules read all selected modules and all modules // in parent configurations if (descriptor.isAutomatic()) { // reads all selected modules // `requires transitive` all selected automatic modules for (ModuleReference mref2 : nameToReference.values()) { ModuleDescriptor descriptor2 = mref2.descriptor(); String name2 = descriptor2.name(); if (!name.equals(name2)) { ResolvedModule m2 = computeIfAbsent(nameToResolved, name2, cf, mref2); reads.add(m2); if (descriptor2.isAutomatic()) requiresTransitive.add(m2); } } // reads all modules in parent configurations // `requires transitive` all automatic modules in parent // configurations for (Configuration parent : parents) { parent.configurations() .map(Configuration::modules) .flatMap(Set::stream) .forEach(m -> { reads.add(m); if (m.reference().descriptor().isAutomatic()) requiresTransitive.add(m); }); } } g1.put(m1, reads); g2.put(m1, requiresTransitive); } // Iteratively update g1 until there are no more requires transitive // to propagate boolean changed; List toAdd = new ArrayList<>(); do { changed = false; for (Set m1Reads : g1.values()) { for (ResolvedModule m2 : m1Reads) { Set m2RequiresTransitive = g2.get(m2); if (m2RequiresTransitive != null) { for (ResolvedModule m3 : m2RequiresTransitive) { if (!m1Reads.contains(m3)) { // m1 reads m2, m2 requires transitive m3 // => need to add m1 reads m3 toAdd.add(m3); } } } } if (!toAdd.isEmpty()) { m1Reads.addAll(toAdd); toAdd.clear(); changed = true; } } } while (changed); return g1; } /** * Equivalent to * 
{@code
     *     map.computeIfAbsent(name, k -> new ResolvedModule(cf, mref))
     *
} */ private ResolvedModule computeIfAbsent(Map map, String name, Configuration cf, ModuleReference mref) { ResolvedModule m = map.get(name); if (m == null) { m = new ResolvedModule(cf, mref); map.put(name, m); } return m; } /** * Checks the readability graph to ensure that *
    *

  1. A module does not read two or more modules with the same name. * This includes the case where a module reads another another with the * same name as itself.

    2. *

  2. Two or more modules in the configuration don't export the same * package to a module that reads both. This includes the case where a * module {@code M} containing package {@code p} reads another module * that exports {@code p} to {@code M}.

    3. *

  3. A module {@code M} doesn't declare that it "{@code uses p.S}" * or "{@code provides p.S with ...}" but package {@code p} is neither * in module {@code M} nor exported to {@code M} by any module that * {@code M} reads.

    4. *
*/ private void checkExportSuppliers(Map> graph) { for (Map.Entry> e : graph.entrySet()) { ModuleDescriptor descriptor1 = e.getKey().descriptor(); String name1 = descriptor1.name(); // the names of the modules that are read (including self) Set names = new HashSet<>(); names.add(name1); // the map of packages that are local or exported to descriptor1 Map packageToExporter = new HashMap<>(); // local packages Set packages = descriptor1.packages(); for (String pn : packages) { packageToExporter.put(pn, descriptor1); } // descriptor1 reads descriptor2 Set reads = e.getValue(); for (ResolvedModule endpoint : reads) { ModuleDescriptor descriptor2 = endpoint.descriptor(); String name2 = descriptor2.name(); if (descriptor2 != descriptor1 && !names.add(name2)) { if (name2.equals(name1)) { resolveFail("Module %s reads another module named %s", name1, name1); } else{ resolveFail("Module %s reads more than one module named %s", name1, name2); } } if (descriptor2.isAutomatic()) { // automatic modules read self and export all packages if (descriptor2 != descriptor1) { for (String source : descriptor2.packages()) { ModuleDescriptor supplier = packageToExporter.putIfAbsent(source, descriptor2); // descriptor2 and 'supplier' export source to descriptor1 if (supplier != null) { failTwoSuppliers(descriptor1, source, descriptor2, supplier); } } } } else { for (ModuleDescriptor.Exports export : descriptor2.exports()) { if (export.isQualified()) { if (!export.targets().contains(descriptor1.name())) continue; } // source is exported by descriptor2 String source = export.source(); ModuleDescriptor supplier = packageToExporter.putIfAbsent(source, descriptor2); // descriptor2 and 'supplier' export source to descriptor1 if (supplier != null) { failTwoSuppliers(descriptor1, source, descriptor2, supplier); } } } } // uses/provides checks not applicable to automatic modules if (!descriptor1.isAutomatic()) { // uses S for (String service : descriptor1.uses()) { String pn = packageName(service); if (!packageToExporter.containsKey(pn)) { resolveFail("Module %s does not read a module that exports %s", descriptor1.name(), pn); } } // provides S for (ModuleDescriptor.Provides provides : descriptor1.provides()) { String pn = packageName(provides.service()); if (!packageToExporter.containsKey(pn)) { resolveFail("Module %s does not read a module that exports %s", descriptor1.name(), pn); } } } } } /** * Fail because a module in the configuration exports the same package to * a module that reads both. This includes the case where a module M * containing a package p reads another module that exports p to at least * module M. */ private void failTwoSuppliers(ModuleDescriptor descriptor, String source, ModuleDescriptor supplier1, ModuleDescriptor supplier2) { if (supplier2 == descriptor) { ModuleDescriptor tmp = supplier1; supplier1 = supplier2; supplier2 = tmp; } if (supplier1 == descriptor) { resolveFail("Module %s contains package %s" + ", module %s exports package %s to %s", descriptor.name(), source, supplier2.name(), source, descriptor.name()); } else { resolveFail("Modules %s and %s export package %s to module %s", supplier1.name(), supplier2.name(), source, descriptor.name()); } } /** * Find a module of the given name in the parent configurations */ private ResolvedModule findInParent(String mn) { for (Configuration parent : parents) { Optional om = parent.findModule(mn); if (om.isPresent()) return om.get(); } return null; } /** * Invokes the beforeFinder to find method to find the given module. */ private ModuleReference findWithBeforeFinder(String mn) { return beforeFinder.find(mn).orElse(null); } /** * Invokes the afterFinder to find method to find the given module. */ private ModuleReference findWithAfterFinder(String mn) { return afterFinder.find(mn).orElse(null); } /** * Returns the set of all modules that are observable with the before * and after ModuleFinders. */ private Set findAll() { Set beforeModules = beforeFinder.findAll(); Set afterModules = afterFinder.findAll(); if (afterModules.isEmpty()) return beforeModules; if (beforeModules.isEmpty() && parents.size() == 1 && parents.get(0) == Configuration.empty()) return afterModules; Set result = new HashSet<>(beforeModules); for (ModuleReference mref : afterModules) { String name = mref.descriptor().name(); if (!beforeFinder.find(name).isPresent() && findInParent(name) == null) { result.add(mref); } } return result; } /** * Returns the package name */ private static String packageName(String cn) { int index = cn.lastIndexOf("."); return (index == -1) ? "" : cn.substring(0, index); } /** * Throw FindException with the given format string and arguments */ private static void findFail(String fmt, Object ... args) { String msg = String.format(fmt, args); throw new FindException(msg); } /** * Throw ResolutionException with the given format string and arguments */ private static void resolveFail(String fmt, Object ... args) { String msg = String.format(fmt, args); throw new ResolutionException(msg); } /** * Tracing support */ private boolean isTracing() { return traceOutput != null; } private void trace(String fmt, Object ... args) { if (traceOutput != null) { traceOutput.format(fmt, args); traceOutput.println(); } } private String nameAndInfo(ModuleReference mref) { ModuleDescriptor descriptor = mref.descriptor(); StringBuilder sb = new StringBuilder(descriptor.name()); mref.location().ifPresent(uri -> sb.append(" " + uri)); if (descriptor.isAutomatic()) sb.append(" automatic"); return sb.toString(); } }