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
23 * questions.
24 */
25
26 package java.lang.module;
27
28 import java.lang.module.ModuleDescriptor.Requires.Modifier;
29 import java.lang.reflect.Layer;
30 import java.util.ArrayDeque;
31 import java.util.ArrayList;
32 import java.util.Collection;
33 import java.util.Deque;
34 import java.util.HashMap;
35 import java.util.HashSet;
36 import java.util.LinkedHashSet;
37 import java.util.List;
38 import java.util.Map;
39 import java.util.Map.Entry;
40 import java.util.Objects;
41 import java.util.Optional;
42 import java.util.Set;
43 import java.util.StringJoiner;
44 import java.util.stream.Collectors;
45
46 import jdk.internal.module.Hasher;
47
48 /**
49 * The resolver used by {@link Configuration#resolveRequires} and
50 * {@link Configuration#resolveRequiresAndUses}.
51 */
52
53 final class Resolver {
54
55 private final ModuleFinder beforeFinder;
56 private final Configuration parent;
57 private final ModuleFinder afterFinder;
58
59 // maps module name to module reference
60 private final Map<String, ModuleReference> nameToReference = new HashMap<>();
61
62
63 Resolver(ModuleFinder beforeFinder,
64 Configuration parent,
65 ModuleFinder afterFinder) {
66 this.beforeFinder = beforeFinder;
67 this.parent = parent;
68 this.afterFinder = afterFinder;
69 }
70
71
72 /**
73 * Resolves the given named modules.
74 *
75 * @throws ResolutionException
76 */
77 Resolver resolveRequires(Collection<String> roots) {
78
79 long start = trace_start("Resolve");
80
81 // create the visit stack to get us started
82 Deque<ModuleDescriptor> q = new ArrayDeque<>();
83 for (String root : roots) {
84
85 // find root module
86 ModuleReference mref = findWithBeforeFinder(root);
87 if (mref == null) {
88 if (parent.findModule(root).isPresent()) {
89 // in parent, nothing to do
90 continue;
91 }
92 mref = findWithAfterFinder(root);
93 if (mref == null) {
94 fail("Module %s not found", root);
95 }
96 }
97
98 if (TRACE) {
99 trace("Root module %s located", root);
100 if (mref.location().isPresent())
101 trace(" (%s)", mref.location().get());
102 }
103
104 assert mref.descriptor().name().equals(root);
105 nameToReference.put(root, mref);
106 q.push(mref.descriptor());
107 }
108
109 resolve(q);
110
111 if (TRACE) {
112 long duration = System.currentTimeMillis() - start;
113 Set<String> names = nameToReference.keySet();
114 trace("Resolver completed in %s ms", duration);
115 names.stream().sorted().forEach(name -> trace(" %s", name));
116 }
117
118 return this;
119 }
120
121 /**
122 * Resolve all modules in the given queue. On completion the queue will be
123 * empty and any resolved modules will be added to {@code nameToReference}.
124 *
125 * @return The set of module resolved by this invocation of resolve
126 */
127 private Set<ModuleDescriptor> resolve(Deque<ModuleDescriptor> q) {
128 Set<ModuleDescriptor> resolved = new HashSet<>();
129
130 while (!q.isEmpty()) {
131 ModuleDescriptor descriptor = q.poll();
132 assert nameToReference.containsKey(descriptor.name());
133
134 // process dependences
135 for (ModuleDescriptor.Requires requires : descriptor.requires()) {
136 String dn = requires.name();
137
138 // find dependence
139 ModuleReference mref = findWithBeforeFinder(dn);
140 if (mref == null) {
141 if (parent.findModule(dn).isPresent())
142 continue;
143
144 mref = findWithAfterFinder(dn);
145 if (mref == null) {
146 fail("Module %s not found, required by %s",
147 dn, descriptor.name());
148 }
149 }
150
151 if (!nameToReference.containsKey(dn)) {
152 nameToReference.put(dn, mref);
153 q.offer(mref.descriptor());
154 resolved.add(mref.descriptor());
155
156 if (TRACE) {
157 trace("Module %s located, required by %s",
158 dn, descriptor.name());
159 if (mref.location().isPresent())
160 trace(" (%s)", mref.location().get());
161 }
162 }
163
164 }
165
166 resolved.add(descriptor);
167 }
168
169 return resolved;
170 }
171
172 /**
173 * Augments the set of resolved modules with modules induced by the
174 * service-use relation.
175 */
176 Resolver resolveUses() {
177
178 long start = trace_start("Bind");
179
180 // Scan the finders for all available service provider modules. As
181 // java.base uses services then then module finders will be scanned
182 // anyway.
183 Map<String, Set<ModuleReference>> availableProviders = new HashMap<>();
184 for (ModuleReference mref : findAll()) {
185 ModuleDescriptor descriptor = mref.descriptor();
186 if (!descriptor.provides().isEmpty()) {
187
188 for (String sn : descriptor.provides().keySet()) {
189 // computeIfAbsent
190 Set<ModuleReference> providers = availableProviders.get(sn);
191 if (providers == null) {
192 providers = new HashSet<>();
193 availableProviders.put(sn, providers);
194 }
195 providers.add(mref);
196 }
197
198 }
199 }
200
201 // create the visit stack
202 Deque<ModuleDescriptor> q = new ArrayDeque<>();
203
204 // the initial set of modules that may use services
205 Set<ModuleDescriptor> candidateConsumers = new HashSet<>();
206 Configuration p = parent;
207 while (p != null) {
208 candidateConsumers.addAll(p.descriptors());
209 p = p.parent().orElse(null);
210 }
211 for (ModuleReference mref : nameToReference.values()) {
212 candidateConsumers.add(mref.descriptor());
213 }
214
215
216 // Where there is a consumer of a service then resolve all modules
217 // that provide an implementation of that service
218 do {
219 for (ModuleDescriptor descriptor : candidateConsumers) {
220 if (!descriptor.uses().isEmpty()) {
221 for (String service : descriptor.uses()) {
222 Set<ModuleReference> mrefs = availableProviders.get(service);
223 if (mrefs != null) {
224 for (ModuleReference mref : mrefs) {
225 ModuleDescriptor provider = mref.descriptor();
226 if (!provider.equals(descriptor)) {
227
228 trace("Module %s provides %s, used by %s",
229 provider.name(), service, descriptor.name());
230
231 String pn = provider.name();
232 if (!nameToReference.containsKey(pn)) {
233
234 if (TRACE && mref.location().isPresent())
235 trace(" (%s)", mref.location().get());
236
237 nameToReference.put(pn, mref);
238 q.push(provider);
239 }
240 }
241 }
242 }
243 }
244 }
245 }
246
247 candidateConsumers = resolve(q);
248
249 } while (!candidateConsumers.isEmpty());
250
251
252 if (TRACE) {
253 long duration = System.currentTimeMillis() - start;
254 Set<String> names = nameToReference.keySet();
255 trace("Bind completed in %s ms", duration);
256 names.stream().sorted().forEach(name -> trace(" %s", name));
257 }
258
259 return this;
260 }
261
262
263 /**
264 * Execute post-resolution checks and returns the module graph of resolved
265 * modules as {@code Map}. The resolved modules will be in the given
266 * configuration.
267 */
268 Map<ResolvedModule, Set<ResolvedModule>> finish(Configuration cf) {
269
270 detectCycles();
271
272 checkPlatformConstraints();
273
274 checkHashes();
275
276 Map<ResolvedModule, Set<ResolvedModule>> graph = makeGraph(cf);
277
278 checkExportSuppliers(graph);
279
280 return graph;
281 }
282
283
284 /**
285 * Checks the given module graph for cycles.
286 *
287 * For now the implementation is a simple depth first search on the
288 * dependency graph. We'll replace this later, maybe with Tarjan.
289 */
290 private void detectCycles() {
291 visited = new HashSet<>();
292 visitPath = new LinkedHashSet<>(); // preserve insertion order
293 for (ModuleReference mref : nameToReference.values()) {
294 visit(mref.descriptor());
295 }
296 visited.clear();
297 }
298
299 // the modules that were visited
300 private Set<ModuleDescriptor> visited;
301
302 // the modules in the current visit path
303 private Set<ModuleDescriptor> visitPath;
304
305 private void visit(ModuleDescriptor descriptor) {
306 if (!visited.contains(descriptor)) {
307 boolean added = visitPath.add(descriptor);
308 if (!added) {
309 throw new ResolutionException("Cycle detected: " +
310 cycleAsString(descriptor));
311 }
312 for (ModuleDescriptor.Requires requires : descriptor.requires()) {
313 String dn = requires.name();
314
315 ModuleReference mref = nameToReference.get(dn);
316 if (mref != null) {
317 ModuleDescriptor other = mref.descriptor();
318 if (other != descriptor) {
319 // dependency is in this configuration
320 visit(other);
321 }
322 }
323 }
324 visitPath.remove(descriptor);
325 visited.add(descriptor);
326 }
327 }
328
329 /**
330 * Returns a String with a list of the modules in a detected cycle.
331 */
332 private String cycleAsString(ModuleDescriptor descriptor) {
333 List<ModuleDescriptor> list = new ArrayList<>(visitPath);
334 list.add(descriptor);
335 int index = list.indexOf(descriptor);
336 return list.stream()
337 .skip(index)
338 .map(ModuleDescriptor::name)
339 .collect(Collectors.joining(" -> "));
340 }
341
342
343 /**
344 * If there are platform specific modules then check that the OS name,
345 * architecture and version match.
346 *
347 * @apiNote This method does not currently check if the OS matches
348 * platform specific modules in parent configurations.
349 */
350 private void checkPlatformConstraints() {
351
352 // first module encountered that is platform specific
353 String savedModuleName = null;
354 String savedOsName = null;
355 String savedOsArch = null;
356 String savedOsVersion = null;
357
358 for (ModuleReference mref : nameToReference.values()) {
359 ModuleDescriptor descriptor = mref.descriptor();
360
361 String osName = descriptor.osName().orElse(null);
362 String osArch = descriptor.osArch().orElse(null);
363 String osVersion = descriptor.osVersion().orElse(null);
364
365 if (osName != null || osArch != null || osVersion != null) {
366
367 if (savedModuleName == null) {
368
369 savedModuleName = descriptor.name();
370 savedOsName = osName;
371 savedOsArch = osArch;
372 savedOsVersion = osVersion;
373
374 } else {
375
376 boolean matches = platformMatches(osName, savedOsName)
377 && platformMatches(osArch, savedOsArch)
378 && platformMatches(osVersion, savedOsVersion);
379
380 if (!matches) {
381 String s1 = platformAsString(savedOsName,
382 savedOsArch,
383 savedOsVersion);
384
385 String s2 = platformAsString(osName, osArch, osVersion);
386 fail("Mismatching constraints on target platform: "
387 + savedModuleName + ": " + s1
388 + ", " + descriptor.name() + ": " + s2);
389 }
390
391 }
392
393 }
394 }
395
396 }
397
398 /**
399 * Returns true if the s1 and s2 are equal or one of them is null.
400 */
401 private boolean platformMatches(String s1, String s2) {
402 if (s1 == null || s2 == null)
403 return true;
404 else
405 return Objects.equals(s1, s2);
406 }
407
408 /**
409 * Return a string that encodes the OS name/arch/version.
410 */
411 private String platformAsString(String osName,
412 String osArch,
413 String osVersion) {
414
415 return new StringJoiner("-")
416 .add(Objects.toString(osName, "*"))
417 .add(Objects.toString(osArch, "*"))
418 .add(Objects.toString(osVersion, "*"))
419 .toString();
420
421 }
422
423
424 /**
425 * Checks the hashes in the module descriptor to ensure that they match
426 * the hash of the dependency's module reference.
427 */
428 private void checkHashes() {
429
430 for (ModuleReference mref : nameToReference.values()) {
431 ModuleDescriptor descriptor = mref.descriptor();
432
433 // get map of module names to hash
434 Optional<Hasher.DependencyHashes> ohashes = descriptor.hashes();
435 if (!ohashes.isPresent())
436 continue;
437 Hasher.DependencyHashes hashes = ohashes.get();
438
439 // check dependences
440 for (ModuleDescriptor.Requires d : descriptor.requires()) {
441 String dn = d.name();
442 String recordedHash = hashes.hashFor(dn);
443
444 if (recordedHash != null) {
445
446 ModuleReference other = nameToReference.get(dn);
447 if (other == null) {
448 other = parent.findModule(dn)
449 .map(ResolvedModule::reference)
450 .orElse(null);
451 }
452 if (other == null)
453 throw new InternalError(dn + " not found");
454
455 String actualHash = other.computeHash(hashes.algorithm());
456 if (actualHash == null)
457 fail("Unable to compute the hash of module %s", dn);
458
459 if (!recordedHash.equals(actualHash)) {
460 fail("Hash of %s (%s) differs to expected hash (%s)",
461 dn, actualHash, recordedHash);
462 }
463
464 }
465
466 }
467 }
468
469 }
470
471
472 /**
473 * Computes and sets the readability graph for the modules in the given
474 * Resolution object.
475 *
476 * The readability graph is created by propagating "requires" through the
477 * "public requires" edges of the module dependence graph. So if the module
478 * dependence graph has m1 requires m2 && m2 requires public m3 then the
479 * resulting readability graph will contain m1 reads m2, m1
480 * reads m3, and m2 reads m3.
481 *
482 * TODO: Use a more efficient algorithm, maybe cache the requires public
483 * in parent configurations.
484 */
485 private Map<ResolvedModule, Set<ResolvedModule>> makeGraph(Configuration cf) {
486
487 // the "reads" graph starts as a module dependence graph and
488 // is iteratively updated to be the readability graph
489 Map<ResolvedModule, Set<ResolvedModule>> g1 = new HashMap<>();
490
491 // the "requires public" graph, contains requires public edges only
492 Map<ResolvedModule, Set<ResolvedModule>> g2 = new HashMap<>();
493
494
495 // need "requires public" from the modules in parent configurations as
496 // there may be selected modules that have a dependency on modules in
497 // the parent configuration.
498
499 Configuration p = parent;
500 while (p != null) {
501 for (ModuleDescriptor descriptor : p.descriptors()) {
502 ResolvedModule x = p.findModule(descriptor.name()).orElse(null);
503 if (x == null)
504 throw new InternalError();
505 for (ModuleDescriptor.Requires requires : descriptor.requires()) {
506 if (requires.modifiers().contains(Modifier.PUBLIC)) {
507 String dn = requires.name();
508 ResolvedModule y = p.findModule(dn).orElse(null);
509 if (y == null)
510 throw new InternalError(dn + " not found");
511 g2.computeIfAbsent(x, k -> new HashSet<>()).add(y);
512 }
513 }
514 }
515
516 p = p.parent().orElse(null);
517 }
518
519 // populate g1 and g2 with the dependences from the selected modules
520 for (ModuleReference mref : nameToReference.values()) {
521 ModuleDescriptor descriptor = mref.descriptor();
522 ResolvedModule x = new ResolvedModule(cf, mref);
523
524 Set<ResolvedModule> reads = new HashSet<>();
525 g1.put(x, reads);
526
527 Set<ResolvedModule> requiresPublic = new HashSet<>();
528 g2.put(x, requiresPublic);
529
530 for (ModuleDescriptor.Requires requires : descriptor.requires()) {
531 String dn = requires.name();
532
533 ResolvedModule y;
534 ModuleReference other = nameToReference.get(dn);
535 if (other != null) {
536 y = new ResolvedModule(cf, other); // cache?
537 } else {
538 y = parent.findModule(dn).orElse(null);
539 if (y == null)
540 throw new InternalError("unable to find " + dn);
541 }
542
543 // m requires other => m reads other
544 reads.add(y);
545
546 // m requires public other
547 if (requires.modifiers().contains(Modifier.PUBLIC)) {
548 requiresPublic.add(y);
549 }
550
551 }
552
553 // automatic modules reads all selected modules and all modules
554 // in parent configurations
555 if (descriptor.isAutomatic()) {
556 String name = descriptor.name();
557
558 // reads all selected modules
559 // requires public` all selected automatic modules
560 for (ModuleReference mref2 : nameToReference.values()) {
561 ModuleDescriptor descriptor2 = mref2.descriptor();
562 if (!name.equals(descriptor2.name())) {
563 ResolvedModule m = new ResolvedModule(cf, mref2);
564 reads.add(m);
565 if (descriptor2.isAutomatic())
566 requiresPublic.add(m);
567 }
568 }
569
570 // reads all modules in parent configurations
571 // `requires public` all automatic modules in parent configurations
572 p = parent;
573 while (p != null) {
574 for (ResolvedModule m : p.modules()) {
575 reads.add(m);
576 if (m.reference().descriptor().isAutomatic())
577 requiresPublic.add(m);
578 }
579 p = p.parent().orElse(null);
580 }
581
582 }
583
584 }
585
586 // Iteratively update g1 until there are no more requires public to propagate
587 boolean changed;
588 Map<ResolvedModule, Set<ResolvedModule>> changes = new HashMap<>();
589 do {
590 changed = false;
591 for (Entry<ResolvedModule, Set<ResolvedModule>> entry : g1.entrySet()) {
592
593 ResolvedModule m1 = entry.getKey();
594 Set<ResolvedModule> m1Reads = entry.getValue();
595
596 for (ResolvedModule m2 : m1Reads) {
597 Set<ResolvedModule> m2RequiresPublic = g2.get(m2);
598 if (m2RequiresPublic != null) {
599 for (ResolvedModule m3 : m2RequiresPublic) {
600 if (!m1Reads.contains(m3)) {
601
602 // computeIfAbsent
603 Set<ResolvedModule> s = changes.get(m1);
604 if (s == null) {
605 s = new HashSet<>();
606 changes.put(m1, s);
607 }
608 s.add(m3);
609 changed = true;
610
611 }
612 }
613 }
614 }
615 }
616
617 if (changed) {
618 for (Map.Entry<ResolvedModule, Set<ResolvedModule>> e :
619 changes.entrySet()) {
620 ResolvedModule m = e.getKey();
621 g1.get(m).addAll(e.getValue());
622 }
623 changes.clear();
624 }
625
626 } while (changed);
627
628
629 return g1;
630 }
631
632
633 /**
634 * Checks the readability graph to ensure that no two modules export the
635 * same package to a module. This includes the case where module M has
636 * a local package P and M reads another module that exports P to M.
637 * Also checks the uses/provides of module M to ensure that it reads a
638 * module that exports the package of the service type to M.
639 */
640 private void checkExportSuppliers(Map<ResolvedModule, Set<ResolvedModule>> graph) {
641
642 for (Map.Entry<ResolvedModule, Set<ResolvedModule>> e : graph.entrySet()) {
643 ModuleDescriptor descriptor1 = e.getKey().descriptor();
644
645 // the map of packages that are local or exported to descriptor1
646 Map<String, ModuleDescriptor> packageToExporter = new HashMap<>();
647
648 // local packages
649 Set<String> packages = descriptor1.packages();
650 for (String pn : packages) {
651 packageToExporter.put(pn, descriptor1);
652 }
653
654 // descriptor1 reads descriptor2
655 Set<ResolvedModule> reads = e.getValue();
656 for (ResolvedModule endpoint : reads) {
657 ModuleDescriptor descriptor2 = endpoint.descriptor();
658
659 for (ModuleDescriptor.Exports export : descriptor2.exports()) {
660
661 if (export.isQualified()) {
662 if (!export.targets().contains(descriptor1.name()))
663 continue;
664 }
665
666 // source is exported to descriptor2
667 String source = export.source();
668 ModuleDescriptor other
669 = packageToExporter.put(source, descriptor2);
670
671 if (other != null && other != descriptor2) {
672 // package might be local to descriptor1
673 if (other == descriptor1) {
674 fail("Module %s contains package %s"
675 + ", module %s exports package %s to %s",
676 descriptor1.name(),
677 source,
678 descriptor2.name(),
679 source,
680 descriptor1.name());
681 } else {
682 fail("Modules %s and %s export package %s to module %s",
683 descriptor2.name(),
684 other.name(),
685 source,
686 descriptor1.name());
687 }
688
689 }
690 }
691 }
692
693 // uses S
694 for (String service : descriptor1.uses()) {
695 String pn = packageName(service);
696 if (!packageToExporter.containsKey(pn)) {
697 fail("Module %s does not read a module that exports %s",
698 descriptor1.name(), pn);
699 }
700 }
701
702 // provides S
703 for (Map.Entry<String, ModuleDescriptor.Provides> entry :
704 descriptor1.provides().entrySet()) {
705 String service = entry.getKey();
706 ModuleDescriptor.Provides provides = entry.getValue();
707
708 String pn = packageName(service);
709 if (!packageToExporter.containsKey(pn)) {
710 fail("Module %s does not read a module that exports %s",
711 descriptor1.name(), pn);
712 }
713
714 for (String provider : provides.providers()) {
715 if (!packages.contains(packageName(provider))) {
716 fail("Provider %s not in module %s",
717 provider, descriptor1.name());
718 }
719 }
720 }
721
722 }
723
724 }
725
726
727 /**
728 * Invokes the beforeFinder to find method to find the given module.
729 */
730 private ModuleReference findWithBeforeFinder(String mn) {
731 try {
732 return beforeFinder.find(mn).orElse(null);
733 } catch (FindException e) {
734 // unwrap
735 throw new ResolutionException(e.getMessage(), e.getCause());
736 }
737 }
738
739 /**
740 * Invokes the afterFinder to find method to find the given module.
741 */
742 private ModuleReference findWithAfterFinder(String mn) {
743 try {
744 return afterFinder.find(mn).orElse(null);
745 } catch (FindException e) {
746 // unwrap
747 throw new ResolutionException(e.getMessage(), e.getCause());
748 }
749 }
750
751 /**
752 * Returns the set of all modules that are observable with the before
753 * and after ModuleFinders.
754 */
755 private Set<ModuleReference> findAll() {
756 try {
757
758 Set<ModuleReference> beforeModules = beforeFinder.findAll();
759 Set<ModuleReference> afterModules = afterFinder.findAll();
760
761 if (afterModules.isEmpty())
762 return beforeModules;
763
764 if (beforeModules.isEmpty() && parent == Configuration.empty())
765 return afterModules;
766
767 Set<ModuleReference> result = new HashSet<>(beforeModules);
768 for (ModuleReference mref : afterModules) {
769 String name = mref.descriptor().name();
770 if (!beforeFinder.find(name).isPresent()
771 && !parent.findModule(name).isPresent())
772 result.add(mref);
773 }
774
775 return result;
776
777 } catch (FindException e) {
778 // unwrap
779 throw new ResolutionException(e.getMessage(), e.getCause());
780 }
781 }
782
783 /**
784 * Returns the package name
785 */
786 private static String packageName(String cn) {
787 int index = cn.lastIndexOf(".");
788 return (index == -1) ? "" : cn.substring(0, index);
789 }
790
791 /**
792 * Throw ResolutionException with the given format string and arguments
793 */
794 private static void fail(String fmt, Object ... args) {
795 String msg = String.format(fmt, args);
796 throw new ResolutionException(msg);
797 }
798
799
800 /**
801 * Tracing support, limited to boot layer for now.
802 */
803
804 private final static boolean TRACE
805 = Boolean.getBoolean("jdk.launcher.traceResolver")
806 && (Layer.boot() == null);
807
808 private String op;
809
810 private long trace_start(String op) {
811 this.op = op;
812 return System.currentTimeMillis();
813 }
814
815 private void trace(String fmt, Object ... args) {
816 if (TRACE) {
817 System.out.print("[" + op + "] ");
818 System.out.format(fmt, args);
819 System.out.println();
820 }
821 }
822
823 }