1 /*
2 * Copyright (c) 2013, 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
32 import java.util.ArrayDeque;
33 import java.util.ArrayList;
34 import java.util.Arrays;
35 import java.util.Collection;
36 import java.util.Deque;
37 import java.util.HashMap;
38 import java.util.HashSet;
39 import java.util.LinkedHashSet;
40 import java.util.List;
41 import java.util.Map;
42 import java.util.Objects;
43 import java.util.Optional;
44 import java.util.Set;
45 import java.util.StringJoiner;
46 import java.util.stream.Collectors;
47
48 import jdk.internal.module.ModuleHashes;
49 import jdk.internal.module.ModuleReferenceImpl;
50
51 /**
52 * The resolver used by {@link Configuration#resolveRequires} and
53 * {@link Configuration#resolveRequiresAndUses}.
54 *
55 * @implNote The resolver is used at VM startup and so deliberately avoids
56 * using lambda and stream usages in code paths used during startup.
57 */
58
59 final class Resolver {
60
61 private final ModuleFinder beforeFinder;
62 private final List<Configuration> parents;
63 private final ModuleFinder afterFinder;
64 private final PrintStream traceOutput;
65
66 // maps module name to module reference
67 private final Map<String, ModuleReference> nameToReference = new HashMap<>();
68
69
70 Resolver(ModuleFinder beforeFinder,
71 List<Configuration> parents,
72 ModuleFinder afterFinder,
73 PrintStream traceOutput) {
74 this.beforeFinder = beforeFinder;
75 this.parents = parents;
76 this.afterFinder = afterFinder;
77 this.traceOutput = traceOutput;
78 }
79
80
81 /**
82 * Resolves the given named modules.
83 *
84 * @throws ResolutionException
85 */
86 Resolver resolveRequires(Collection<String> roots) {
87
88 // create the visit stack to get us started
89 Deque<ModuleDescriptor> q = new ArrayDeque<>();
90 for (String root : roots) {
91
92 // find root module
93 ModuleReference mref = findWithBeforeFinder(root);
94 if (mref == null) {
95
96 if (findInParent(root) != null) {
97 // in parent, nothing to do
98 continue;
99 }
100
101 mref = findWithAfterFinder(root);
102 if (mref == null) {
103 fail("Module %s not found", root);
104 }
105 }
106
107 if (isTracing()) {
108 trace("Root module %s located", root);
109 mref.location().ifPresent(uri -> trace(" (%s)", uri));
110 }
111
112 assert mref.descriptor().name().equals(root);
113 nameToReference.put(root, mref);
114 q.push(mref.descriptor());
115 }
116
117 resolve(q);
118
119 return this;
120 }
121
122 /**
123 * Resolve all modules in the given queue. On completion the queue will be
124 * empty and any resolved modules will be added to {@code nameToReference}.
125 *
126 * @return The set of module resolved by this invocation of resolve
127 */
128 private Set<ModuleDescriptor> resolve(Deque<ModuleDescriptor> q) {
129 Set<ModuleDescriptor> resolved = new HashSet<>();
130
131 while (!q.isEmpty()) {
132 ModuleDescriptor descriptor = q.poll();
133 assert nameToReference.containsKey(descriptor.name());
135 // process dependences
136 for (ModuleDescriptor.Requires requires : descriptor.requires()) {
137
138 // only required at compile-time
139 if (requires.modifiers().contains(Modifier.STATIC))
140 continue;
141
142 String dn = requires.name();
143
144 // find dependence
145 ModuleReference mref = findWithBeforeFinder(dn);
146 if (mref == null) {
147
148 if (findInParent(dn) != null) {
149 // dependence is in parent
150 continue;
151 }
152
153 mref = findWithAfterFinder(dn);
154 if (mref == null) {
155 fail("Module %s not found, required by %s",
156 dn, descriptor.name());
157 }
158 }
159
160 if (!nameToReference.containsKey(dn)) {
161 nameToReference.put(dn, mref);
162 q.offer(mref.descriptor());
163 resolved.add(mref.descriptor());
164
165 if (isTracing()) {
166 trace("Module %s located, required by %s",
167 dn, descriptor.name());
168 mref.location().ifPresent(uri -> trace(" (%s)", uri));
169 }
170 }
171
172 }
173
174 resolved.add(descriptor);
175 }
176
177 return resolved;
178 }
179
180 /**
181 * Augments the set of resolved modules with modules induced by the
182 * service-use relation.
183 */
184 Resolver resolveUses() {
185
186 // Scan the finders for all available service provider modules. As
187 // java.base uses services then then module finders will be scanned
188 // anyway.
189 Map<String, Set<ModuleReference>> availableProviders = new HashMap<>();
190 for (ModuleReference mref : findAll()) {
191 ModuleDescriptor descriptor = mref.descriptor();
192 if (!descriptor.provides().isEmpty()) {
193
194 for (Provides provides : descriptor.provides()) {
195 String sn = provides.service();
196
197 // computeIfAbsent
198 Set<ModuleReference> providers = availableProviders.get(sn);
199 if (providers == null) {
200 providers = new HashSet<>();
201 availableProviders.put(sn, providers);
202 }
203 providers.add(mref);
204 }
229 Set<ModuleDescriptor> candidateConsumers = initialConsumers;
230 do {
231 for (ModuleDescriptor descriptor : candidateConsumers) {
232 if (!descriptor.uses().isEmpty()) {
233 for (String service : descriptor.uses()) {
234 Set<ModuleReference> mrefs = availableProviders.get(service);
235 if (mrefs != null) {
236 for (ModuleReference mref : mrefs) {
237 ModuleDescriptor provider = mref.descriptor();
238 if (!provider.equals(descriptor)) {
239
240 trace("Module %s provides %s, used by %s",
241 provider.name(), service, descriptor.name());
242
243 String pn = provider.name();
244 if (!nameToReference.containsKey(pn)) {
245 if (isTracing()) {
246 mref.location()
247 .ifPresent(uri -> trace(" (%s)", uri));
248 }
249 nameToReference.put(pn, mref);
250 q.push(provider);
251 }
252 }
253 }
254 }
255 }
256 }
257 }
258
259 candidateConsumers = resolve(q);
260 } while (!candidateConsumers.isEmpty());
261
262 return this;
263 }
264
265
266 /**
267 * Execute post-resolution checks and returns the module graph of resolved
268 * modules as {@code Map}. The resolved modules will be in the given
269 * configuration.
270 *
271 * @param check {@true} to execute the post resolution checks
272 */
273 Map<ResolvedModule, Set<ResolvedModule>> finish(Configuration cf,
274 boolean check)
275 {
276 if (isTracing()) {
277 trace("Result:");
278 Set<String> names = nameToReference.keySet();
279 names.stream().sorted().forEach(name -> trace(" %s", name));
280 }
281
282 if (check) {
283 detectCycles();
284 checkPlatformConstraints();
285 checkHashes();
286 }
287
288 Map<ResolvedModule, Set<ResolvedModule>> graph = makeGraph(cf);
289
290 if (check) {
291 checkExportSuppliers(graph);
292 }
293
294 return graph;
295 }
296
297 /**
298 * Checks the given module graph for cycles.
299 *
300 * For now the implementation is a simple depth first search on the
301 * dependency graph. We'll replace this later, maybe with Tarjan.
302 */
303 private void detectCycles() {
304 visited = new HashSet<>();
305 visitPath = new LinkedHashSet<>(); // preserve insertion order
306 for (ModuleReference mref : nameToReference.values()) {
307 visit(mref.descriptor());
308 }
309 visited.clear();
310 }
311
312 // the modules that were visited
313 private Set<ModuleDescriptor> visited;
314
315 // the modules in the current visit path
316 private Set<ModuleDescriptor> visitPath;
317
318 private void visit(ModuleDescriptor descriptor) {
319 if (!visited.contains(descriptor)) {
320 boolean added = visitPath.add(descriptor);
321 if (!added) {
322 throw new ResolutionException("Cycle detected: " +
323 cycleAsString(descriptor));
324 }
325 for (ModuleDescriptor.Requires requires : descriptor.requires()) {
326 String dn = requires.name();
327
328 ModuleReference mref = nameToReference.get(dn);
329 if (mref != null) {
330 ModuleDescriptor other = mref.descriptor();
331 if (other != descriptor) {
332 // dependency is in this configuration
333 visit(other);
334 }
335 }
336 }
337 visitPath.remove(descriptor);
338 visited.add(descriptor);
339 }
340 }
341
342 /**
343 * Returns a String with a list of the modules in a detected cycle.
344 */
345 private String cycleAsString(ModuleDescriptor descriptor) {
346 List<ModuleDescriptor> list = new ArrayList<>(visitPath);
347 list.add(descriptor);
348 int index = list.indexOf(descriptor);
349 return list.stream()
350 .skip(index)
351 .map(ModuleDescriptor::name)
352 .collect(Collectors.joining(" -> "));
353 }
354
355
356 /**
357 * If there are platform specific modules then check that the OS name,
358 * architecture and version match.
359 *
360 * @apiNote This method does not currently check if the OS matches
361 * platform specific modules in parent configurations.
362 */
363 private void checkPlatformConstraints() {
364
365 // first module encountered that is platform specific
366 String savedModuleName = null;
367 String savedOsName = null;
368 String savedOsArch = null;
369 String savedOsVersion = null;
370
371 for (ModuleReference mref : nameToReference.values()) {
372 ModuleDescriptor descriptor = mref.descriptor();
373
374 String osName = descriptor.osName().orElse(null);
375 String osArch = descriptor.osArch().orElse(null);
376 String osVersion = descriptor.osVersion().orElse(null);
377
378 if (osName != null || osArch != null || osVersion != null) {
379
380 if (savedModuleName == null) {
381
382 savedModuleName = descriptor.name();
383 savedOsName = osName;
384 savedOsArch = osArch;
385 savedOsVersion = osVersion;
386
387 } else {
388
389 boolean matches = platformMatches(osName, savedOsName)
390 && platformMatches(osArch, savedOsArch)
391 && platformMatches(osVersion, savedOsVersion);
392
393 if (!matches) {
394 String s1 = platformAsString(savedOsName,
395 savedOsArch,
396 savedOsVersion);
397
398 String s2 = platformAsString(osName, osArch, osVersion);
399 fail("Mismatching constraints on target platform: "
400 + savedModuleName + ": " + s1
401 + ", " + descriptor.name() + ": " + s2);
402 }
403
404 }
405
406 }
407 }
408
409 }
410
411 /**
412 * Returns true if the s1 and s2 are equal or one of them is null.
413 */
414 private boolean platformMatches(String s1, String s2) {
415 if (s1 == null || s2 == null)
416 return true;
417 else
418 return Objects.equals(s1, s2);
419 }
420
421 /**
422 * Return a string that encodes the OS name/arch/version.
423 */
424 private String platformAsString(String osName,
425 String osArch,
426 String osVersion) {
427
428 return new StringJoiner("-")
429 .add(Objects.toString(osName, "*"))
430 .add(Objects.toString(osArch, "*"))
431 .add(Objects.toString(osVersion, "*"))
432 .toString();
433
434 }
435
436 /**
437 * Checks the hashes in the module descriptor to ensure that they match
438 * any recorded hashes.
439 */
440 private void checkHashes() {
441 for (ModuleReference mref : nameToReference.values()) {
442
443 // get the recorded hashes, if any
444 if (!(mref instanceof ModuleReferenceImpl))
445 continue;
446 ModuleHashes hashes = ((ModuleReferenceImpl)mref).recordedHashes();
447 if (hashes == null)
448 continue;
449
450 ModuleDescriptor descriptor = mref.descriptor();
451 String algorithm = hashes.algorithm();
452 for (String dn : hashes.names()) {
453 ModuleReference mref2 = nameToReference.get(dn);
454 if (mref2 == null) {
455 ResolvedModule resolvedModule = findInParent(dn);
456 if (resolvedModule != null)
457 mref2 = resolvedModule.reference();
458 }
459 if (mref2 == null)
460 continue;
461
462 if (!(mref2 instanceof ModuleReferenceImpl)) {
463 fail("Unable to compute the hash of module %s", dn);
464 }
465
466 // skip checking the hash if the module has been patched
467 ModuleReferenceImpl other = (ModuleReferenceImpl)mref2;
468 if (other != null && !other.isPatched()) {
469 byte[] recordedHash = hashes.hashFor(dn);
470 byte[] actualHash = other.computeHash(algorithm);
471 if (actualHash == null)
472 fail("Unable to compute the hash of module %s", dn);
473 if (!Arrays.equals(recordedHash, actualHash)) {
474 fail("Hash of %s (%s) differs to expected hash (%s)" +
475 " recorded in %s", dn, toHexString(actualHash),
476 toHexString(recordedHash), descriptor.name());
477 }
478 }
479 }
480
481 }
482 }
483
484 private static String toHexString(byte[] ba) {
485 StringBuilder sb = new StringBuilder(ba.length * 2);
486 for (byte b: ba) {
487 sb.append(String.format("%02x", b & 0xff));
488 }
489 return sb.toString();
490 }
491
492
493 /**
494 * Computes the readability graph for the modules in the given Configuration.
677 */
678 private void checkExportSuppliers(Map<ResolvedModule, Set<ResolvedModule>> graph) {
679
680 for (Map.Entry<ResolvedModule, Set<ResolvedModule>> e : graph.entrySet()) {
681 ModuleDescriptor descriptor1 = e.getKey().descriptor();
682
683 // the map of packages that are local or exported to descriptor1
684 Map<String, ModuleDescriptor> packageToExporter = new HashMap<>();
685
686 // local packages
687 Set<String> packages = descriptor1.packages();
688 for (String pn : packages) {
689 packageToExporter.put(pn, descriptor1);
690 }
691
692 // descriptor1 reads descriptor2
693 Set<ResolvedModule> reads = e.getValue();
694 for (ResolvedModule endpoint : reads) {
695 ModuleDescriptor descriptor2 = endpoint.descriptor();
696
697 for (ModuleDescriptor.Exports export : descriptor2.exports()) {
698
699 if (export.isQualified()) {
700 if (!export.targets().contains(descriptor1.name()))
701 continue;
702 }
703
704 // source is exported to descriptor2
705 String source = export.source();
706 ModuleDescriptor other
707 = packageToExporter.putIfAbsent(source, descriptor2);
708
709 if (other != null && other != descriptor2) {
710 // package might be local to descriptor1
711 if (other == descriptor1) {
712 fail("Module %s contains package %s"
713 + ", module %s exports package %s to %s",
714 descriptor1.name(),
715 source,
716 descriptor2.name(),
717 source,
718 descriptor1.name());
719 } else {
720 fail("Modules %s and %s export package %s to module %s",
721 descriptor2.name(),
722 other.name(),
723 source,
724 descriptor1.name());
725 }
726
727 }
728 }
729 }
730
731 // uses/provides checks not applicable to automatic modules
732 if (!descriptor1.isAutomatic()) {
733
734 // uses S
735 for (String service : descriptor1.uses()) {
736 String pn = packageName(service);
737 if (!packageToExporter.containsKey(pn)) {
738 fail("Module %s does not read a module that exports %s",
739 descriptor1.name(), pn);
740 }
741 }
742
743 // provides S
744 for (ModuleDescriptor.Provides provides : descriptor1.provides()) {
745 String pn = packageName(provides.service());
746 if (!packageToExporter.containsKey(pn)) {
747 fail("Module %s does not read a module that exports %s",
748 descriptor1.name(), pn);
749 }
750
751 for (String provider : provides.providers()) {
752 if (!packages.contains(packageName(provider))) {
753 fail("Provider %s not in module %s",
754 provider, descriptor1.name());
755 }
756 }
757 }
758
759 }
760
761 }
762
763 }
764
765 /**
766 * Find a module of the given name in the parent configurations
767 */
768 private ResolvedModule findInParent(String mn) {
769 for (Configuration parent : parents) {
770 Optional<ResolvedModule> om = parent.findModule(mn);
771 if (om.isPresent())
772 return om.get();
773 }
774 return null;
775 }
776
777
778 /**
779 * Invokes the beforeFinder to find method to find the given module.
780 */
781 private ModuleReference findWithBeforeFinder(String mn) {
782 try {
783 return beforeFinder.find(mn).orElse(null);
784 } catch (FindException e) {
785 // unwrap
786 throw new ResolutionException(e.getMessage(), e.getCause());
787 }
788 }
789
790 /**
791 * Invokes the afterFinder to find method to find the given module.
792 */
793 private ModuleReference findWithAfterFinder(String mn) {
794 try {
795 return afterFinder.find(mn).orElse(null);
796 } catch (FindException e) {
797 // unwrap
798 throw new ResolutionException(e.getMessage(), e.getCause());
799 }
800 }
801
802 /**
803 * Returns the set of all modules that are observable with the before
804 * and after ModuleFinders.
805 */
806 private Set<ModuleReference> findAll() {
807 try {
808
809 Set<ModuleReference> beforeModules = beforeFinder.findAll();
810 Set<ModuleReference> afterModules = afterFinder.findAll();
811
812 if (afterModules.isEmpty())
813 return beforeModules;
814
815 if (beforeModules.isEmpty()
816 && parents.size() == 1
817 && parents.get(0) == Configuration.empty())
818 return afterModules;
819
820 Set<ModuleReference> result = new HashSet<>(beforeModules);
821 for (ModuleReference mref : afterModules) {
822 String name = mref.descriptor().name();
823 if (!beforeFinder.find(name).isPresent()
824 && findInParent(name) == null) {
825 result.add(mref);
826 }
827 }
828
829 return result;
830
831 } catch (FindException e) {
832 // unwrap
833 throw new ResolutionException(e.getMessage(), e.getCause());
834 }
835 }
836
837 /**
838 * Returns the package name
839 */
840 private static String packageName(String cn) {
841 int index = cn.lastIndexOf(".");
842 return (index == -1) ? "" : cn.substring(0, index);
843 }
844
845 /**
846 * Throw ResolutionException with the given format string and arguments
847 */
848 private static void fail(String fmt, Object ... args) {
849 String msg = String.format(fmt, args);
850 throw new ResolutionException(msg);
851 }
852
853 /**
854 * Tracing support
855 */
856
857 private boolean isTracing() {
858 return traceOutput != null;
859 }
860
861 private void trace(String fmt, Object ... args) {
862 if (traceOutput != null) {
863 traceOutput.format("[Resolver] " + fmt, args);
864 traceOutput.println();
865 }
866 }
867
868 }
|
1 /*
2 * Copyright (c) 2013, 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
32 import java.util.ArrayDeque;
33 import java.util.ArrayList;
34 import java.util.Arrays;
35 import java.util.Collection;
36 import java.util.Deque;
37 import java.util.HashMap;
38 import java.util.HashSet;
39 import java.util.LinkedHashSet;
40 import java.util.List;
41 import java.util.Map;
42 import java.util.Objects;
43 import java.util.Optional;
44 import java.util.Set;
45 import java.util.StringJoiner;
46 import java.util.stream.Collectors;
47
48 import jdk.internal.module.ModuleHashes;
49 import jdk.internal.module.ModuleReferenceImpl;
50
51 /**
52 * The resolver used by {@link Configuration#resolve} and {@link
53 * Configuration#resolveAndBind}.
54 *
55 * @implNote The resolver is used at VM startup and so deliberately avoids
56 * using lambda and stream usages in code paths used during startup.
57 */
58
59 final class Resolver {
60
61 private final ModuleFinder beforeFinder;
62 private final List<Configuration> parents;
63 private final ModuleFinder afterFinder;
64 private final PrintStream traceOutput;
65
66 // maps module name to module reference
67 private final Map<String, ModuleReference> nameToReference = new HashMap<>();
68
69 // module constraints on target platform
70 private String osName;
71 private String osArch;
72 private String osVersion;
73
74 String osName() { return osName; }
75 String osArch() { return osArch; }
76 String osVersion() { return osVersion; }
77
78 /**
79 * @throws IllegalArgumentException if there are more than one parent and
80 * the constraints on the target platform conflict
81 */
82 Resolver(ModuleFinder beforeFinder,
83 List<Configuration> parents,
84 ModuleFinder afterFinder,
85 PrintStream traceOutput) {
86 this.beforeFinder = beforeFinder;
87 this.parents = parents;
88 this.afterFinder = afterFinder;
89 this.traceOutput = traceOutput;
90
91 // record constraints on target platform, checking that they don't conflict
92 for (Configuration parent : parents) {
93 String value = parent.osName();
94 if (value != null) {
95 if (osName == null) {
96 osName = value;
97 } else {
98 if (!value.equals(osName)) {
99 failParentConflict("Operating System", osName, value);
100 }
101 }
102 }
103 value = parent.osArch();
104 if (value != null) {
105 if (osArch == null) {
106 osArch = value;
107 } else {
108 if (!value.equals(osArch)) {
109 failParentConflict("OS architecture", osArch, value);
110 }
111 }
112 }
113 value = parent.osVersion();
114 if (value != null) {
115 if (osVersion == null) {
116 osVersion = value;
117 } else {
118 if (!value.equals(osVersion)) {
119 failParentConflict("OS version", osVersion, value);
120 }
121 }
122 }
123 }
124 }
125
126 private void failParentConflict(String constraint, String s1, String s2) {
127 String msg = "Parents have conflicting constraints on target "
128 + constraint + ": " + s1 + ", " + s2;
129 throw new IllegalArgumentException(msg);
130 }
131
132 /**
133 * Resolves the given named modules.
134 *
135 * @throws ResolutionException
136 */
137 Resolver resolve(Collection<String> roots) {
138
139 // create the visit stack to get us started
140 Deque<ModuleDescriptor> q = new ArrayDeque<>();
141 for (String root : roots) {
142
143 // find root module
144 ModuleReference mref = findWithBeforeFinder(root);
145 if (mref == null) {
146
147 if (findInParent(root) != null) {
148 // in parent, nothing to do
149 continue;
150 }
151
152 mref = findWithAfterFinder(root);
153 if (mref == null) {
154 findFail("Module %s not found", root);
155 }
156 }
157
158 if (isTracing()) {
159 trace("Root module %s located", root);
160 mref.location().ifPresent(uri -> trace(" (%s)", uri));
161 }
162
163 addFoundModule(mref);
164 q.push(mref.descriptor());
165 }
166
167 resolve(q);
168
169 return this;
170 }
171
172 /**
173 * Resolve all modules in the given queue. On completion the queue will be
174 * empty and any resolved modules will be added to {@code nameToReference}.
175 *
176 * @return The set of module resolved by this invocation of resolve
177 */
178 private Set<ModuleDescriptor> resolve(Deque<ModuleDescriptor> q) {
179 Set<ModuleDescriptor> resolved = new HashSet<>();
180
181 while (!q.isEmpty()) {
182 ModuleDescriptor descriptor = q.poll();
183 assert nameToReference.containsKey(descriptor.name());
185 // process dependences
186 for (ModuleDescriptor.Requires requires : descriptor.requires()) {
187
188 // only required at compile-time
189 if (requires.modifiers().contains(Modifier.STATIC))
190 continue;
191
192 String dn = requires.name();
193
194 // find dependence
195 ModuleReference mref = findWithBeforeFinder(dn);
196 if (mref == null) {
197
198 if (findInParent(dn) != null) {
199 // dependence is in parent
200 continue;
201 }
202
203 mref = findWithAfterFinder(dn);
204 if (mref == null) {
205 findFail("Module %s not found, required by %s",
206 dn, descriptor.name());
207 }
208 }
209
210 if (!nameToReference.containsKey(dn)) {
211 addFoundModule(mref);
212 q.offer(mref.descriptor());
213 resolved.add(mref.descriptor());
214
215 if (isTracing()) {
216 trace("Module %s located, required by %s",
217 dn, descriptor.name());
218 mref.location().ifPresent(uri -> trace(" (%s)", uri));
219 }
220 }
221
222 }
223
224 resolved.add(descriptor);
225 }
226
227 return resolved;
228 }
229
230 /**
231 * Augments the set of resolved modules with modules induced by the
232 * service-use relation.
233 */
234 Resolver bind() {
235
236 // Scan the finders for all available service provider modules. As
237 // java.base uses services then then module finders will be scanned
238 // anyway.
239 Map<String, Set<ModuleReference>> availableProviders = new HashMap<>();
240 for (ModuleReference mref : findAll()) {
241 ModuleDescriptor descriptor = mref.descriptor();
242 if (!descriptor.provides().isEmpty()) {
243
244 for (Provides provides : descriptor.provides()) {
245 String sn = provides.service();
246
247 // computeIfAbsent
248 Set<ModuleReference> providers = availableProviders.get(sn);
249 if (providers == null) {
250 providers = new HashSet<>();
251 availableProviders.put(sn, providers);
252 }
253 providers.add(mref);
254 }
279 Set<ModuleDescriptor> candidateConsumers = initialConsumers;
280 do {
281 for (ModuleDescriptor descriptor : candidateConsumers) {
282 if (!descriptor.uses().isEmpty()) {
283 for (String service : descriptor.uses()) {
284 Set<ModuleReference> mrefs = availableProviders.get(service);
285 if (mrefs != null) {
286 for (ModuleReference mref : mrefs) {
287 ModuleDescriptor provider = mref.descriptor();
288 if (!provider.equals(descriptor)) {
289
290 trace("Module %s provides %s, used by %s",
291 provider.name(), service, descriptor.name());
292
293 String pn = provider.name();
294 if (!nameToReference.containsKey(pn)) {
295 if (isTracing()) {
296 mref.location()
297 .ifPresent(uri -> trace(" (%s)", uri));
298 }
299 addFoundModule(mref);
300 q.push(provider);
301 }
302 }
303 }
304 }
305 }
306 }
307 }
308
309 candidateConsumers = resolve(q);
310 } while (!candidateConsumers.isEmpty());
311
312 return this;
313 }
314
315
316 /**
317 * Add the module to the nameToReference map. Also check any constraints on
318 * the target platform with the constraints of other modules.
319 */
320 private void addFoundModule(ModuleReference mref) {
321 ModuleDescriptor descriptor = mref.descriptor();
322 nameToReference.put(descriptor.name(), mref);
323
324 if (descriptor.osName().isPresent()
325 || descriptor.osArch().isPresent()
326 || descriptor.osVersion().isPresent())
327 checkTargetConstraints(descriptor);
328 }
329
330 /**
331 * Check that the module's constraints on the target platform do not
332 * conflict with the constraints of other modules resolved so far or
333 * modules in parent configurations.
334 */
335 private void checkTargetConstraints(ModuleDescriptor descriptor) {
336 String value = descriptor.osName().orElse(null);
337 if (value != null) {
338 if (osName == null) {
339 osName = value;
340 } else {
341 if (!value.equals(osName)) {
342 failTargetConstraint(descriptor);
343 }
344 }
345 }
346 value = descriptor.osArch().orElse(null);
347 if (value != null) {
348 if (osArch == null) {
349 osArch = value;
350 } else {
351 if (!value.equals(osArch)) {
352 failTargetConstraint(descriptor);
353 }
354 }
355 }
356 value = descriptor.osVersion().orElse(null);
357 if (value != null) {
358 if (osVersion == null) {
359 osVersion = value;
360 } else {
361 if (!value.equals(osVersion)) {
362 failTargetConstraint(descriptor);
363 }
364 }
365 }
366 }
367
368 private void failTargetConstraint(ModuleDescriptor md) {
369 String s1 = targetAsString(osName, osArch, osVersion);
370 String s2 = targetAsString(md);
371 findFail("Module %s has constraints on target platform that conflict" +
372 " with other modules: %s, %s", md.name(), s1, s2);
373 }
374
375 private String targetAsString(ModuleDescriptor descriptor) {
376 String osName = descriptor.osName().orElse(null);
377 String osArch = descriptor.osArch().orElse(null);
378 String osVersion = descriptor.osVersion().orElse(null);
379 return targetAsString(osName, osArch, osVersion);
380 }
381
382 private String targetAsString(String osName, String osArch, String osVersion) {
383 return new StringJoiner("-")
384 .add(Objects.toString(osName, "*"))
385 .add(Objects.toString(osArch, "*"))
386 .add(Objects.toString(osVersion, "*"))
387 .toString();
388 }
389
390
391 /**
392 * Execute post-resolution checks and returns the module graph of resolved
393 * modules as {@code Map}. The resolved modules will be in the given
394 * configuration.
395 *
396 * @param check {@true} to execute the post resolution checks
397 */
398 Map<ResolvedModule, Set<ResolvedModule>> finish(Configuration cf,
399 boolean check)
400 {
401 if (isTracing()) {
402 trace("Result:");
403 Set<String> names = nameToReference.keySet();
404 names.stream().sorted().forEach(name -> trace(" %s", name));
405 }
406
407 if (check) {
408 detectCycles();
409 checkHashes();
410 }
411
412 Map<ResolvedModule, Set<ResolvedModule>> graph = makeGraph(cf);
413
414 if (check) {
415 checkExportSuppliers(graph);
416 }
417
418 return graph;
419 }
420
421 /**
422 * Checks the given module graph for cycles.
423 *
424 * For now the implementation is a simple depth first search on the
425 * dependency graph. We'll replace this later, maybe with Tarjan.
426 */
427 private void detectCycles() {
428 visited = new HashSet<>();
429 visitPath = new LinkedHashSet<>(); // preserve insertion order
430 for (ModuleReference mref : nameToReference.values()) {
431 visit(mref.descriptor());
432 }
433 visited.clear();
434 }
435
436 // the modules that were visited
437 private Set<ModuleDescriptor> visited;
438
439 // the modules in the current visit path
440 private Set<ModuleDescriptor> visitPath;
441
442 private void visit(ModuleDescriptor descriptor) {
443 if (!visited.contains(descriptor)) {
444 boolean added = visitPath.add(descriptor);
445 if (!added) {
446 resolveFail("Cycle detected: %s", cycleAsString(descriptor));
447 }
448 for (ModuleDescriptor.Requires requires : descriptor.requires()) {
449 String dn = requires.name();
450
451 ModuleReference mref = nameToReference.get(dn);
452 if (mref != null) {
453 ModuleDescriptor other = mref.descriptor();
454 if (other != descriptor) {
455 // dependency is in this configuration
456 visit(other);
457 }
458 }
459 }
460 visitPath.remove(descriptor);
461 visited.add(descriptor);
462 }
463 }
464
465 /**
466 * Returns a String with a list of the modules in a detected cycle.
467 */
468 private String cycleAsString(ModuleDescriptor descriptor) {
469 List<ModuleDescriptor> list = new ArrayList<>(visitPath);
470 list.add(descriptor);
471 int index = list.indexOf(descriptor);
472 return list.stream()
473 .skip(index)
474 .map(ModuleDescriptor::name)
475 .collect(Collectors.joining(" -> "));
476 }
477
478
479 /**
480 * Checks the hashes in the module descriptor to ensure that they match
481 * any recorded hashes.
482 */
483 private void checkHashes() {
484 for (ModuleReference mref : nameToReference.values()) {
485
486 // get the recorded hashes, if any
487 if (!(mref instanceof ModuleReferenceImpl))
488 continue;
489 ModuleHashes hashes = ((ModuleReferenceImpl)mref).recordedHashes();
490 if (hashes == null)
491 continue;
492
493 ModuleDescriptor descriptor = mref.descriptor();
494 String algorithm = hashes.algorithm();
495 for (String dn : hashes.names()) {
496 ModuleReference mref2 = nameToReference.get(dn);
497 if (mref2 == null) {
498 ResolvedModule resolvedModule = findInParent(dn);
499 if (resolvedModule != null)
500 mref2 = resolvedModule.reference();
501 }
502 if (mref2 == null)
503 continue;
504
505 if (!(mref2 instanceof ModuleReferenceImpl)) {
506 findFail("Unable to compute the hash of module %s", dn);
507 }
508
509 // skip checking the hash if the module has been patched
510 ModuleReferenceImpl other = (ModuleReferenceImpl)mref2;
511 if (other != null && !other.isPatched()) {
512 byte[] recordedHash = hashes.hashFor(dn);
513 byte[] actualHash = other.computeHash(algorithm);
514 if (actualHash == null)
515 findFail("Unable to compute the hash of module %s", dn);
516 if (!Arrays.equals(recordedHash, actualHash)) {
517 findFail("Hash of %s (%s) differs to expected hash (%s)" +
518 " recorded in %s", dn, toHexString(actualHash),
519 toHexString(recordedHash), descriptor.name());
520 }
521 }
522 }
523
524 }
525 }
526
527 private static String toHexString(byte[] ba) {
528 StringBuilder sb = new StringBuilder(ba.length * 2);
529 for (byte b: ba) {
530 sb.append(String.format("%02x", b & 0xff));
531 }
532 return sb.toString();
533 }
534
535
536 /**
537 * Computes the readability graph for the modules in the given Configuration.
720 */
721 private void checkExportSuppliers(Map<ResolvedModule, Set<ResolvedModule>> graph) {
722
723 for (Map.Entry<ResolvedModule, Set<ResolvedModule>> e : graph.entrySet()) {
724 ModuleDescriptor descriptor1 = e.getKey().descriptor();
725
726 // the map of packages that are local or exported to descriptor1
727 Map<String, ModuleDescriptor> packageToExporter = new HashMap<>();
728
729 // local packages
730 Set<String> packages = descriptor1.packages();
731 for (String pn : packages) {
732 packageToExporter.put(pn, descriptor1);
733 }
734
735 // descriptor1 reads descriptor2
736 Set<ResolvedModule> reads = e.getValue();
737 for (ResolvedModule endpoint : reads) {
738 ModuleDescriptor descriptor2 = endpoint.descriptor();
739
740 if (descriptor2.isAutomatic()) {
741 // automatic modules read self and export all packages
742 if (descriptor2 != descriptor1){
743 for (String source : descriptor2.packages()) {
744 ModuleDescriptor supplier
745 = packageToExporter.putIfAbsent(source, descriptor2);
746
747 // descriptor2 and 'supplier' export source to descriptor1
748 if (supplier != null) {
749 failTwoSuppliers(descriptor1, source, descriptor2, supplier);
750 }
751 }
752
753 }
754 } else {
755 for (ModuleDescriptor.Exports export : descriptor2.exports()) {
756 if (export.isQualified()) {
757 if (!export.targets().contains(descriptor1.name()))
758 continue;
759 }
760
761 // source is exported by descriptor2
762 String source = export.source();
763 ModuleDescriptor supplier
764 = packageToExporter.putIfAbsent(source, descriptor2);
765
766 // descriptor2 and 'supplier' export source to descriptor1
767 if (supplier != null) {
768 failTwoSuppliers(descriptor1, source, descriptor2, supplier);
769 }
770 }
771
772 }
773 }
774
775 // uses/provides checks not applicable to automatic modules
776 if (!descriptor1.isAutomatic()) {
777
778 // uses S
779 for (String service : descriptor1.uses()) {
780 String pn = packageName(service);
781 if (!packageToExporter.containsKey(pn)) {
782 resolveFail("Module %s does not read a module that exports %s",
783 descriptor1.name(), pn);
784 }
785 }
786
787 // provides S
788 for (ModuleDescriptor.Provides provides : descriptor1.provides()) {
789 String pn = packageName(provides.service());
790 if (!packageToExporter.containsKey(pn)) {
791 resolveFail("Module %s does not read a module that exports %s",
792 descriptor1.name(), pn);
793 }
794 }
795
796 }
797
798 }
799
800 }
801
802 /**
803 * Fail because a module in the configuration exports the same package to
804 * a module that reads both. This includes the case where a module M
805 * containing a package p reads another module that exports p to at least
806 * module M.
807 */
808 private void failTwoSuppliers(ModuleDescriptor descriptor,
809 String source,
810 ModuleDescriptor supplier1,
811 ModuleDescriptor supplier2) {
812
813 if (supplier2 == descriptor) {
814 ModuleDescriptor tmp = supplier1;
815 supplier1 = supplier2;
816 supplier2 = tmp;
817 }
818
819 if (supplier1 == descriptor) {
820 resolveFail("Module %s contains package %s"
821 + ", module %s exports package %s to %s",
822 descriptor.name(),
823 source,
824 supplier2.name(),
825 source,
826 descriptor.name());
827 } else {
828 resolveFail("Modules %s and %s export package %s to module %s",
829 supplier1.name(),
830 supplier2.name(),
831 source,
832 descriptor.name());
833 }
834
835 }
836
837
838 /**
839 * Find a module of the given name in the parent configurations
840 */
841 private ResolvedModule findInParent(String mn) {
842 for (Configuration parent : parents) {
843 Optional<ResolvedModule> om = parent.findModule(mn);
844 if (om.isPresent())
845 return om.get();
846 }
847 return null;
848 }
849
850
851 /**
852 * Invokes the beforeFinder to find method to find the given module.
853 */
854 private ModuleReference findWithBeforeFinder(String mn) {
855
856 return beforeFinder.find(mn).orElse(null);
857
858 }
859
860 /**
861 * Invokes the afterFinder to find method to find the given module.
862 */
863 private ModuleReference findWithAfterFinder(String mn) {
864 return afterFinder.find(mn).orElse(null);
865 }
866
867 /**
868 * Returns the set of all modules that are observable with the before
869 * and after ModuleFinders.
870 */
871 private Set<ModuleReference> findAll() {
872 Set<ModuleReference> beforeModules = beforeFinder.findAll();
873 Set<ModuleReference> afterModules = afterFinder.findAll();
874
875 if (afterModules.isEmpty())
876 return beforeModules;
877
878 if (beforeModules.isEmpty()
879 && parents.size() == 1
880 && parents.get(0) == Configuration.empty())
881 return afterModules;
882
883 Set<ModuleReference> result = new HashSet<>(beforeModules);
884 for (ModuleReference mref : afterModules) {
885 String name = mref.descriptor().name();
886 if (!beforeFinder.find(name).isPresent()
887 && findInParent(name) == null) {
888 result.add(mref);
889 }
890 }
891
892 return result;
893 }
894
895 /**
896 * Returns the package name
897 */
898 private static String packageName(String cn) {
899 int index = cn.lastIndexOf(".");
900 return (index == -1) ? "" : cn.substring(0, index);
901 }
902
903 /**
904 * Throw FindException with the given format string and arguments
905 */
906 private static void findFail(String fmt, Object ... args) {
907 String msg = String.format(fmt, args);
908 throw new FindException(msg);
909 }
910
911 /**
912 * Throw ResolutionException with the given format string and arguments
913 */
914 private static void resolveFail(String fmt, Object ... args) {
915 String msg = String.format(fmt, args);
916 throw new ResolutionException(msg);
917 }
918
919 /**
920 * Tracing support
921 */
922
923 private boolean isTracing() {
924 return traceOutput != null;
925 }
926
927 private void trace(String fmt, Object ... args) {
928 if (traceOutput != null) {
929 traceOutput.format("[Resolver] " + fmt, args);
930 traceOutput.println();
931 }
932 }
933
934 }
|