1 /* 2 * Copyright (c) 2009, 2012, 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 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 55 // 56 // mi = ModuleInfo 57 // mid = ModuleId 58 // nm = module name 59 // pn = package name 60 // cn = class name 61 // 62 // Prefixes: 'r' for a requesting module, 's' for a supplying module 63 64 private final Catalog cat; 65 private Collection<ModuleIdQuery> rootQueries; 66 67 private Resolver(Catalog c, Collection<ModuleIdQuery> rqs) { 68 cat = c; 69 rootQueries = rqs; 70 } 71 72 private Set<ModuleInfo> modules = new HashSet<>(); 73 74 private Map<String,ModuleView> moduleViewForName 75 = new HashMap<>(); 76 private Map<String,URI> locationForName = new HashMap<>(); 77 78 // modules needs to be downloaded from remote repository 79 private Set<ModuleId> modulesNeeded = new HashSet<>(); 80 81 private long spaceRequired = 0; 82 private long downloadRequired = 0; 83 84 // Cache of service interface to synthesized dependences of 85 // service provider modules 86 private Map<String,Set<ViewDependence>> synthesizedServiceDependences = new HashMap<>(); 87 // FIFO queue of service interfaces corresponding to "requires service" 88 // clauses of modules that have been visited by the resolver. 89 // ## This queue should be sorted in a topological order 90 private Deque<String> serviceInterfaceQueue = new LinkedList<>(); 91 92 private static void fail(String fmt, Object ... args) // cf. Linker.fail 93 throws ConfigurationException 94 { 95 throw new ConfigurationException(fmt, args); 96 } 97 98 // ## Open issue: should aliases have versions? 99 // 100 // ## If alias has no version, a query matches an alias only if 101 // ## the query does not specify a version (i.e. requires java.base;) 102 // ## However, this conflicts with the current spec of the 103 // ## synthesized dependence on java.base with a version constraint of 104 // ## >= N version constraint is inserted in the module-info.class 105 // ## at compile time if the module doesn't declare an explicit 106 // ## dependence on java.base or not the java.base module itself. 107 private boolean matchesQuery(ViewDependence dep, ModuleId mid) { 108 boolean rv = dep.query().matches(mid); 109 if (!rv) { 110 // Allow this synthesized dependence for now until this issue 111 // is resolved. 112 String mn = dep.query().name(); 113 if (dep.modifiers().contains(Modifier.SYNTHESIZED) && mn.equals("java.base")) { 114 return mid.name().equals(mn); 115 } 116 } 117 118 return rv; 119 } 120 121 private ModuleId getModuleId(String mn, ModuleView mv) { 122 if (mv.id().name().equals(mn)) { 123 return mv.id(); 124 } else { 125 for (ModuleId alias : mv.aliases()) { 126 // ## if alias has version, multiple aliases matching the given name? 127 if (alias.name().equals(mn)) { 128 return alias; 129 } 130 } 131 } 132 return null; 133 } 134 135 // Does the supplying module smi permit the requesting module rmi 136 // to require it? 137 // 138 private boolean permits(ModuleInfo rmi, ViewDependence dep, ModuleView smv) { 139 assert matchesQuery(dep, getModuleId(dep.query().name(), smv)); 140 if (rmi == null) { 141 // Special case: Synthetic root dependence 142 return true; 143 } 144 Set<String> ps = smv.permits(); 145 if (ps.isEmpty() && !dep.modifiers().contains(Modifier.LOCAL)) { 146 // Non-local dependences are implicitly permitted 147 // when the permit set is empty 148 return true; 149 } 150 return ps.contains(rmi.id().name()); 151 } 152 153 // A choice which remains to be made. Choices are arranged in a stack, 154 // using the next field. Initially the stack is primed with the choice of 155 // which module to assign as the root module. When a candidate module is 156 // identified for a particular choice then that module's dependences are 157 // pushed onto the stack as further choices to be made. If the stack ever 158 // becomes empty then the algorithm terminates successfully. If the search 159 // completes without emptying the stack then it fails. 160 // 161 private static class Choice { 162 protected final ModuleInfo rmi; // Requesting module 163 protected final ViewDependence dep; // Dependence to be satisfied 164 protected final Choice next; // Next choice in stack 165 private Choice(ModuleInfo mi, ViewDependence d, Choice ch) { 166 rmi = mi; 167 dep = d; 168 next = ch; 169 } 170 171 public String toString() { 172 return (rmi != null ? rmi.id() : "ROOT") + " " + dep; 173 } 174 } 175 176 private static class RootChoice extends Choice { 177 private RootChoice(ViewDependence d, Choice ch) { 178 super(null, d, ch); 179 } 180 } 181 182 private static class ServiceProviderChoice extends Choice { 183 private ServiceProviderChoice(ViewDependence d, Choice ch) { 184 super(null, d, ch); 185 } 186 187 public String toString() { 188 return "SERVICE PROVIDER " + dep; 189 } 190 } 191 192 // Resolve the given choice 193 // 194 private boolean resolve(int depth, Choice choice) 195 throws ConfigurationException, IOException 196 { 197 198 if (choice == null) { 199 // Success! 200 return true; 201 } 202 203 ModuleInfo rmi = choice.rmi; 204 ViewDependence dep = choice.dep; 205 206 if (tracing) 207 trace(1, depth, "resolving %s", choice); 208 209 String mn = dep.query().name(); 210 211 // First check to see whether we've already resolved a module with 212 // the given name. If so then it must satisfy the constraints, else 213 // we fail since we don't support side-by-side versioning at run time. 214 // 215 ModuleView mv = moduleViewForName.get(mn); 216 ModuleInfo mi = mv != null ? mv.moduleInfo() : null; 217 if (mi != null) { 218 boolean rv = (matchesQuery(dep, getModuleId(mn, mv)) 219 && permits(rmi, dep, mv)); 220 if (!rv) { 221 if (tracing) 222 trace(1, depth, "fail: previously-resolved %s (module %s) unacceptable", 223 mv.id(), mi.id()); 224 return false; 225 } 226 return resolve(depth + 1, choice.next); 227 } 228 229 // No resolved module of this name yet, so go try to find one. 230 // We prefer newer versions to older versions, and we consider 231 // all modules of the given name in our catalog and its parent 232 // catalog(s), if any. 233 // 234 List<ModuleId> candidates = cat.findModuleIds(mn); 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 280 // Consider a candidate module for the given requesting module and 281 // dependence 282 // 283 private boolean resolve(int depth, Choice nextChoice, 284 ModuleInfo rmi, ViewDependence dep, 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) 335 trace(1, depth, "fail: permits %s", smv.permits()); 336 return false; 337 } 338 339 // Save the ModuleView in the moduleViewForName map, 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()) { 384 final String serviceInterface = sd.service(); 385 386 // If this service interface has not been placed on the queue 387 if (!serviceInterfaceQueue.contains(serviceInterface)) { 388 serviceInterfaceQueue.addLast(serviceInterface); 389 if (tracing) 390 trace(1, depth, "pushing service interface %s", serviceInterface); 391 } 392 } 393 } 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) 438 throws IOException 439 { 440 Set<ViewDependence> serviceDependences = 441 synthesizedServiceDependences.get(serviceInterface); 442 if (serviceDependences != null) 443 return serviceDependences; 444 445 serviceDependences = new LinkedHashSet<>(); 446 for (ModuleId providerId : cat.listDeclaringModuleIds()) { 447 final ModuleInfo provider = cat.readModuleInfo(providerId); 448 // If any view provides a service provider class then 449 // add an optional view dependency for the module 450 // itself 451 for (ModuleView providerView : provider.views()) { 452 if (providerView.services().containsKey(serviceInterface)) { 453 ModuleIdQuery q = 454 new ModuleIdQuery(provider.id().name(), null); 455 ViewDependence vd = 456 new ViewDependence(EnumSet.of(Modifier.OPTIONAL), q); 457 serviceDependences.add(vd); 458 break; 459 } 460 } 461 } 462 synthesizedServiceDependences.put(serviceInterface, serviceDependences); 463 return serviceDependences; 464 } 465 466 // Phase n, n > 0: resolve services 467 // 468 // Resolving of service provider module dependencies may 469 // result further service provider module dependencies. 470 // These are treated as distinct phases 471 private void resolveServices() throws ConfigurationException, IOException { 472 int phase = 0; 473 474 while (!serviceInterfaceQueue.isEmpty()) { 475 phase++; 476 if (tracing) 477 trace(1, 0, "service provider module dependency resolving phase %d", phase); 478 479 // Get the service provider module dependencies for the 480 // service interface and create choices 481 // ## Include from remote repositories? 482 List<Choice> choices = new ArrayList<>(); 483 while (!serviceInterfaceQueue.isEmpty()) { 484 String serviceInterface = serviceInterfaceQueue.removeFirst(); 485 trace(1, 1, "service interface %s", serviceInterface); 486 487 Set<ViewDependence> vds = getServiceProviderDependences(serviceInterface, cat); 488 if (vds.isEmpty()) { 489 trace(1, 2, "no service provider modules found"); 490 } 491 492 for (ViewDependence vd: vds) { 493 if (tracing) 494 trace(1, 2, "dependency %s", vd); 495 496 // ## Should duplicate service provider dependencies 497 // be retained 498 choices.add(new ServiceProviderChoice(vd, null)); 499 } 500 } 501 502 // Resolve each service provider module dependency in this phase 503 for (Choice c: choices) { 504 // Result will always be true since dependency is optional 505 resolve(1, c); 506 507 // ## If the service provider module dependency has not been 508 // resolved then log warning as to why 509 } 510 } 511 } 512 513 // Checks that chosen modules that require a service have at least one 514 // implementation in the chosen set. 515 // 516 private void ensureServicesPresent() throws ConfigurationException { 517 Set<String> serviceTypes = new HashSet<>(); 518 for (ModuleInfo mi: modules) { 519 for (ModuleView view: mi.views()) { 520 Map<String,Set<String>> services = view.services(); 521 serviceTypes.addAll(services.keySet()); 522 } 523 } 524 for (ModuleInfo mi: modules) { 525 for (ServiceDependence sd: mi.requiresServices()) { 526 if (!sd.modifiers().contains((Modifier.OPTIONAL))) { 527 String sn = sd.service(); 528 if (!serviceTypes.contains(sn)) { 529 fail("No implementations of service %s, required by %s", 530 sn, mi.id()); 531 } 532 533 } 534 } 535 } 536 } 537 538 private boolean run() 539 throws ConfigurationException, IOException 540 { 541 Choice ch = null; 542 for (ModuleIdQuery midq : rootQueries) { 543 ViewDependence dep = new ViewDependence(EnumSet.noneOf(Modifier.class), 544 midq); 545 ch = new RootChoice(dep, ch); 546 } 547 548 // Phase 0: resolve application 549 boolean resolved = resolve(0, ch); 550 if (resolved) { 551 // If success then resolve service provider modules, if any 552 resolveServices(); 553 ensureServicesPresent(); 554 } 555 return resolved; 556 } 557 558 // Entry point 559 // 560 static Resolution run(Catalog cat, Collection<ModuleIdQuery> rootQueries) 561 throws ConfigurationException, IOException 562 { 563 Resolver r = new Resolver(cat, rootQueries); 564 if (!r.run()) 565 fail("%s: Cannot resolve", 566 (rootQueries.size() == 1 567 ? rootQueries.iterator().next() 568 : rootQueries)); 569 return new Resolution(rootQueries, r.modules, 570 r.moduleViewForName, 571 r.locationForName, 572 r.modulesNeeded, 573 r.downloadRequired, r.spaceRequired); 574 } 575 576 } --- EOF ---