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