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 ---