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 org.openjdk.jigsaw;
27
28 import java.lang.module.*;
29 import java.io.*;
30 import java.net.URI;
31 import java.util.*;
32
33 import static java.lang.module.Dependence.Modifier;
34 import static org.openjdk.jigsaw.Repository.ModuleMetaData;
35 import static org.openjdk.jigsaw.Trace.*;
36
37
38 // We resolve module versions by doing a recursive depth-first search of
39 // the space of possible choices.
40 //
41 // This algorithm will find the optimal set of module versions, if one
42 // exists, in the sense that each version chosen will be the newest version
43 // that satisfies all dependences upon it.
44 //
45 // Naively one might expect that we could just walk the dependence graph,
46 // but that doesn't work. Each choice that we make can change the shape
47 // of the dependence graph since different versions of the same module can
48 // have completely different dependences.
49
50 // ## TODO: Improve error messages
51
52 final class Resolver {
53
54 // Variable-name conventions
235 Collections.sort(candidates, Collections.reverseOrder());
236 for (ModuleId mid : candidates) {
237 if (!matchesQuery(dep, mid))
238 continue;
239 if (resolve(depth + 1, choice.next, rmi, dep, cat, mid))
240 return true;
241 }
242
243 if (dep.modifiers().contains(Modifier.OPTIONAL)) {
244 // Don't fail; it's just an optional dependence
245 return resolve(depth + 1, choice.next);
246 }
247
248 // No local module found, so if this catalog is a library then
249 // consider its remote repositories, if any
250 //
251 // ## Policy issues: Anywhere vs. local, child vs. parent, ...
252 //
253 if (cat instanceof Library) {
254 Library lib = (Library)cat;
255 RemoteRepositoryList rrl = lib.repositoryList();
256 RemoteRepository rr = rrl.firstRepository();
257 if (rr != null) {
258 candidates = rr.findModuleIds(mn);
259 Collections.sort(candidates, Collections.reverseOrder());
260 if (tracing)
261 trace(1, depth,
262 "considering candidates from repos of %s: %s",
263 lib.name(), candidates);
264 for (ModuleId mid : candidates) {
265 if (!matchesQuery(dep, mid))
266 continue;
267 if (resolve(depth + 1, choice.next, rmi, dep, rr, mid))
268 return true;
269 }
270 }
271 }
272
273 if (tracing)
274 trace(1, depth, "fail: %s", dep);
275 return false;
276
277 }
278
284 Catalog cat, ModuleId mid)
285 throws ConfigurationException, IOException
286 {
287
288 if (tracing) {
289 String loc = "";
290 if (cat instanceof RemoteRepository)
291 loc = " " + ((LocatableCatalog)cat).location();
292 trace(1, depth, "trying %s%s", mid, loc);
293 }
294
295 assert matchesQuery(dep, mid);
296
297 assert moduleViewForName.get(mid.name()) == null;
298
299 // Find and read the ModuleInfo, saving its location
300 // and size data, if any
301 //
302 ModuleInfo mi = null;
303 URI ml = null;
304 ModuleMetaData mmd = null;
305 for (Catalog c = cat; c != null; c = c.parent()) {
306 mi = c.readLocalModuleInfo(mid);
307 if (mi != null) {
308 if (c != this.cat && c instanceof LocatableCatalog) {
309 ml = ((LocatableCatalog)c).location();
310 assert ml != null;
311 }
312 if (c instanceof RemoteRepository)
313 mmd = ((RemoteRepository)c).fetchMetaData(mid);
314 break;
315 }
316 }
317 if (mi == null)
318 throw new AssertionError("No ModuleInfo for " + mid
319 + "; initial catalog " + cat.name());
320
321 // Find the supplying module view
322 ModuleView smv = null;
323 for (ModuleView mv : mi.views()) {
324 if (mv.id().equals(mid) || mv.aliases().contains(mid)) {
325 smv = mv;
326 break;
327 }
328 }
329
330 // Check this module's permits constraints
331 //
332 if (!permits(rmi, dep, smv)) {
333 if (tracing)
339 // which also serves as our visited-node set
340 //
341 String smn = mi.id().name();
342 modules.add(mi);
343
344 // add module views to the map
345 for (ModuleView mv : mi.views()) {
346 moduleViewForName.put(mv.id().name(), mv);
347 for (ModuleId alias : mv.aliases()) {
348 moduleViewForName.put(alias.name(), mv);
349 }
350 }
351
352 // Save the module's location, if known
353 //
354 if (ml != null)
355 locationForName.put(smn, ml);
356
357 // Save the module's download and install sizes, if any
358 //
359 if (mmd != null) {
360 modulesNeeded.add(mi.id());
361 downloadRequired += mmd.getDownloadSize();
362 spaceRequired += mmd.getInstallSize();
363 }
364
365 // Push this module's dependences onto the choice stack,
366 // in reverse order so that the choices are examined in
367 // forward order
368 //
369 Choice ch = nextChoice;
370 // ## ModuleInfo.requires() should be a list, not a set
371 List<ViewDependence> dl = new ArrayList<>(mi.requiresModules());
372 Collections.reverse(dl);
373 for (ViewDependence d : dl)
374 ch = new Choice(mi, d, ch);
375
376 // Push the service interfaces, if any, onto queue to be processed later
377 Set<ServiceDependence> serviceDeps = mi.requiresServices();
378 // Check point the service interface queue size so partial state can be
379 // reverted if dependencies of this module cannot be resolved
380 int sizeOfServiceInterfaceQueue = serviceInterfaceQueue.size();
381 if (!serviceDeps.isEmpty()) {
382 for (ServiceDependence sd: mi.requiresServices()) {
393
394 // Recursively examine the next choice
395 //
396 if (!resolve(depth + 1, ch)) {
397 // Revert service interface queue
398 int d = serviceInterfaceQueue.size() - sizeOfServiceInterfaceQueue;
399 while (d-- > 0) {
400 serviceInterfaceQueue.removeLast();
401 }
402
403 // Revert maps, then fail
404 modules.remove(mi);
405 for (ModuleView mv : mi.views()) {
406 moduleViewForName.remove(mv.id().name());
407 for (ModuleId alias : mv.aliases()) {
408 moduleViewForName.remove(alias.name());
409 }
410 }
411 if (ml != null)
412 locationForName.remove(smn);
413 if (mmd != null) {
414 modulesNeeded.remove(mi.id());
415 downloadRequired -= mmd.getDownloadSize();
416 spaceRequired -= mmd.getInstallSize();
417 }
418 if (tracing)
419 trace(1, depth, "fail: %s", mid);
420 return false;
421
422 }
423
424 return true;
425 }
426
427
428 // Get the synthesized service provider module dependences for a
429 // service interface.
430 //
431 // The catalog will be searched for service provider modules and the
432 // result will be cached since such a search is potentially expensive.
433 // TODO: The catalog could index service provider modules.
434 //
435 private Set<ViewDependence> getServiceProviderDependences(String serviceInterface,
436 Catalog cat)
|
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 org.openjdk.jigsaw;
27
28 import java.lang.module.*;
29 import java.io.*;
30 import java.net.URI;
31 import java.util.*;
32
33 import static java.lang.module.Dependence.Modifier;
34 import static org.openjdk.jigsaw.Repository.ModuleFileMetaData;
35 import static org.openjdk.jigsaw.Trace.*;
36
37
38 // We resolve module versions by doing a recursive depth-first search of
39 // the space of possible choices.
40 //
41 // This algorithm will find the optimal set of module versions, if one
42 // exists, in the sense that each version chosen will be the newest version
43 // that satisfies all dependences upon it.
44 //
45 // Naively one might expect that we could just walk the dependence graph,
46 // but that doesn't work. Each choice that we make can change the shape
47 // of the dependence graph since different versions of the same module can
48 // have completely different dependences.
49
50 // ## TODO: Improve error messages
51
52 final class Resolver {
53
54 // Variable-name conventions
235 Collections.sort(candidates, Collections.reverseOrder());
236 for (ModuleId mid : candidates) {
237 if (!matchesQuery(dep, mid))
238 continue;
239 if (resolve(depth + 1, choice.next, rmi, dep, cat, mid))
240 return true;
241 }
242
243 if (dep.modifiers().contains(Modifier.OPTIONAL)) {
244 // Don't fail; it's just an optional dependence
245 return resolve(depth + 1, choice.next);
246 }
247
248 // No local module found, so if this catalog is a library then
249 // consider its remote repositories, if any
250 //
251 // ## Policy issues: Anywhere vs. local, child vs. parent, ...
252 //
253 if (cat instanceof Library) {
254 Library lib = (Library)cat;
255 ModuleArchitecture modArch = lib.architecture();
256 RemoteRepositoryList rrl = lib.repositoryList();
257 RemoteRepository rr = rrl.firstRepository();
258 if (rr != null) {
259 candidates = rr.findlocalModuleIds(mn, modArch);
260 Collections.sort(candidates, Collections.reverseOrder());
261 if (tracing)
262 trace(1, depth,
263 "considering candidates from repos of %s: %s",
264 lib.name(), candidates);
265 for (ModuleId mid : candidates) {
266 if (!matchesQuery(dep, mid))
267 continue;
268 if (resolve(depth + 1, choice.next, rmi, dep, rr, mid))
269 return true;
270 }
271 }
272 }
273
274 if (tracing)
275 trace(1, depth, "fail: %s", dep);
276 return false;
277
278 }
279
285 Catalog cat, ModuleId mid)
286 throws ConfigurationException, IOException
287 {
288
289 if (tracing) {
290 String loc = "";
291 if (cat instanceof RemoteRepository)
292 loc = " " + ((LocatableCatalog)cat).location();
293 trace(1, depth, "trying %s%s", mid, loc);
294 }
295
296 assert matchesQuery(dep, mid);
297
298 assert moduleViewForName.get(mid.name()) == null;
299
300 // Find and read the ModuleInfo, saving its location
301 // and size data, if any
302 //
303 ModuleInfo mi = null;
304 URI ml = null;
305 ModuleFileMetaData mfmd = null;
306 for (Catalog c = cat; c != null; c = c.parent()) {
307 mi = c.readLocalModuleInfo(mid);
308 if (mi != null) {
309 if (c != this.cat && c instanceof LocatableCatalog) {
310 ml = ((LocatableCatalog)c).location();
311 assert ml != null;
312 }
313 if (c instanceof RemoteRepository)
314 mfmd = ((RemoteRepository)c).fetchMetaData(mid);
315 break;
316 }
317 }
318 if (mi == null)
319 throw new AssertionError("No ModuleInfo for " + mid
320 + "; initial catalog " + cat.name());
321
322 // Find the supplying module view
323 ModuleView smv = null;
324 for (ModuleView mv : mi.views()) {
325 if (mv.id().equals(mid) || mv.aliases().contains(mid)) {
326 smv = mv;
327 break;
328 }
329 }
330
331 // Check this module's permits constraints
332 //
333 if (!permits(rmi, dep, smv)) {
334 if (tracing)
340 // which also serves as our visited-node set
341 //
342 String smn = mi.id().name();
343 modules.add(mi);
344
345 // add module views to the map
346 for (ModuleView mv : mi.views()) {
347 moduleViewForName.put(mv.id().name(), mv);
348 for (ModuleId alias : mv.aliases()) {
349 moduleViewForName.put(alias.name(), mv);
350 }
351 }
352
353 // Save the module's location, if known
354 //
355 if (ml != null)
356 locationForName.put(smn, ml);
357
358 // Save the module's download and install sizes, if any
359 //
360 if (mfmd != null) {
361 modulesNeeded.add(mi.id());
362 downloadRequired += mfmd.getDownloadSize();
363 spaceRequired += mfmd.getInstallSize();
364 }
365
366 // Push this module's dependences onto the choice stack,
367 // in reverse order so that the choices are examined in
368 // forward order
369 //
370 Choice ch = nextChoice;
371 // ## ModuleInfo.requires() should be a list, not a set
372 List<ViewDependence> dl = new ArrayList<>(mi.requiresModules());
373 Collections.reverse(dl);
374 for (ViewDependence d : dl)
375 ch = new Choice(mi, d, ch);
376
377 // Push the service interfaces, if any, onto queue to be processed later
378 Set<ServiceDependence> serviceDeps = mi.requiresServices();
379 // Check point the service interface queue size so partial state can be
380 // reverted if dependencies of this module cannot be resolved
381 int sizeOfServiceInterfaceQueue = serviceInterfaceQueue.size();
382 if (!serviceDeps.isEmpty()) {
383 for (ServiceDependence sd: mi.requiresServices()) {
394
395 // Recursively examine the next choice
396 //
397 if (!resolve(depth + 1, ch)) {
398 // Revert service interface queue
399 int d = serviceInterfaceQueue.size() - sizeOfServiceInterfaceQueue;
400 while (d-- > 0) {
401 serviceInterfaceQueue.removeLast();
402 }
403
404 // Revert maps, then fail
405 modules.remove(mi);
406 for (ModuleView mv : mi.views()) {
407 moduleViewForName.remove(mv.id().name());
408 for (ModuleId alias : mv.aliases()) {
409 moduleViewForName.remove(alias.name());
410 }
411 }
412 if (ml != null)
413 locationForName.remove(smn);
414 if (mfmd != null) {
415 modulesNeeded.remove(mi.id());
416 downloadRequired -= mfmd.getDownloadSize();
417 spaceRequired -= mfmd.getInstallSize();
418 }
419 if (tracing)
420 trace(1, depth, "fail: %s", mid);
421 return false;
422
423 }
424
425 return true;
426 }
427
428
429 // Get the synthesized service provider module dependences for a
430 // service interface.
431 //
432 // The catalog will be searched for service provider modules and the
433 // result will be cached since such a search is potentially expensive.
434 // TODO: The catalog could index service provider modules.
435 //
436 private Set<ViewDependence> getServiceProviderDependences(String serviceInterface,
437 Catalog cat)
|