src/share/classes/org/openjdk/jigsaw/Resolver.java

Print this page




  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)