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.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 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 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 279 // Consider a candidate module for the given requesting module and 280 // dependence 281 // 282 private boolean resolve(int depth, Choice nextChoice, 283 ModuleInfo rmi, ViewDependence dep, 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) 334 trace(1, depth, "fail: permits %s", smv.permits()); 335 return false; 336 } 337 338 // Save the ModuleView in the moduleViewForName map, 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()) { 383 final String serviceInterface = sd.service(); 384 385 // If this service interface has not been placed on the queue 386 if (!serviceInterfaceQueue.contains(serviceInterface)) { 387 serviceInterfaceQueue.addLast(serviceInterface); 388 if (tracing) 389 trace(1, depth, "pushing service interface %s", serviceInterface); 390 } 391 } 392 } 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) 437 throws IOException 438 { 439 Set<ViewDependence> serviceDependences = 440 synthesizedServiceDependences.get(serviceInterface); 441 if (serviceDependences != null) 442 return serviceDependences; 443 444 serviceDependences = new LinkedHashSet<>(); 445 for (ModuleId providerId : cat.listDeclaringModuleIds()) { 446 final ModuleInfo provider = cat.readModuleInfo(providerId); 447 // If any view provides a service provider class then 448 // add an optional view dependency for the module 449 // itself 450 for (ModuleView providerView : provider.views()) { 451 if (providerView.services().containsKey(serviceInterface)) { 452 ModuleIdQuery q = 453 new ModuleIdQuery(provider.id().name(), null); 454 ViewDependence vd = 455 new ViewDependence(EnumSet.of(Modifier.OPTIONAL), q); 456 serviceDependences.add(vd); 457 break; 458 } 459 } 460 } 461 synthesizedServiceDependences.put(serviceInterface, serviceDependences); 462 return serviceDependences; 463 } 464 465 // Phase n, n > 0: resolve services 466 // 467 // Resolving of service provider module dependencies may 468 // result further service provider module dependencies. 469 // These are treated as distinct phases 470 private void resolveServices() throws ConfigurationException, IOException { 471 int phase = 0; 472 473 while (!serviceInterfaceQueue.isEmpty()) { 474 phase++; 475 if (tracing) 476 trace(1, 0, "service provider module dependency resolving phase %d", phase); 477 478 // Get the service provider module dependencies for the 479 // service interface and create choices 480 // ## Include from remote repositories? 481 List<Choice> choices = new ArrayList<>(); 482 while (!serviceInterfaceQueue.isEmpty()) { 483 String serviceInterface = serviceInterfaceQueue.removeFirst(); 484 trace(1, 1, "service interface %s", serviceInterface); 485 486 Set<ViewDependence> vds = getServiceProviderDependences(serviceInterface, cat); 487 if (vds.isEmpty()) { 488 trace(1, 2, "no service provider modules found"); 489 } 490 491 for (ViewDependence vd: vds) { 492 if (tracing) 493 trace(1, 2, "dependency %s", vd); 494 495 // ## Should duplicate service provider dependencies 496 // be retained 497 choices.add(new ServiceProviderChoice(vd, null)); 498 } 499 } 500 501 // Resolve each service provider module dependency in this phase 502 for (Choice c: choices) { 503 // Result will always be true since dependency is optional 504 resolve(1, c); 505 506 // ## If the service provider module dependency has not been 507 // resolved then log warning as to why 508 } 509 } 510 } 511 512 // Checks that chosen modules that require a service have at least one 513 // implementation in the chosen set. 514 // 515 private void ensureServicesPresent() throws ConfigurationException { 516 Set<String> serviceTypes = new HashSet<>(); 517 for (ModuleInfo mi: modules) { 518 for (ModuleView view: mi.views()) { 519 Map<String,Set<String>> services = view.services(); 520 serviceTypes.addAll(services.keySet()); 521 } 522 } 523 for (ModuleInfo mi: modules) { 524 for (ServiceDependence sd: mi.requiresServices()) { 525 if (!sd.modifiers().contains((Modifier.OPTIONAL))) { 526 String sn = sd.service(); 527 if (!serviceTypes.contains(sn)) { 528 fail("No implementations of service %s, required by %s", 529 sn, mi.id()); 530 } 531 532 } 533 } 534 } 535 } 536 537 private boolean run() 538 throws ConfigurationException, IOException 539 { 540 Choice ch = null; 541 for (ModuleIdQuery midq : rootQueries) { 542 ViewDependence dep = new ViewDependence(EnumSet.noneOf(Modifier.class), 543 midq); 544 ch = new RootChoice(dep, ch); 545 } 546 547 // Phase 0: resolve application 548 boolean resolved = resolve(0, ch); 549 if (resolved) { 550 // If success then resolve service provider modules, if any 551 resolveServices(); 552 ensureServicesPresent(); 553 } 554 return resolved; 555 } 556 557 // Entry point 558 // 559 static Resolution run(Catalog cat, Collection<ModuleIdQuery> rootQueries) 560 throws ConfigurationException, IOException 561 { 562 Resolver r = new Resolver(cat, rootQueries); 563 if (!r.run()) 564 fail("%s: Cannot resolve", 565 (rootQueries.size() == 1 566 ? rootQueries.iterator().next() 567 : rootQueries)); 568 return new Resolution(rootQueries, r.modules, 569 r.moduleViewForName, 570 r.locationForName, 571 r.modulesNeeded, 572 r.downloadRequired, r.spaceRequired); 573 } 574 575 } --- EOF ---