001 /* 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * http://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, 013 * software distributed under the License is distributed on an 014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 015 * KIND, either express or implied. See the License for the 016 * specific language governing permissions and limitations 017 * under the License. 018 */ 019 package org.apache.felix.framework.searchpolicy; 020 021 import java.util.ArrayList; 022 import java.util.Arrays; 023 import java.util.Collections; 024 import java.util.Comparator; 025 import java.util.HashMap; 026 import java.util.HashSet; 027 import java.util.Iterator; 028 import java.util.List; 029 import java.util.Map; 030 import java.util.Set; 031 import java.util.StringTokenizer; 032 import org.apache.felix.framework.Logger; 033 import org.apache.felix.framework.util.Util; 034 import org.apache.felix.framework.util.manifestparser.Capability; 035 import org.apache.felix.framework.util.manifestparser.R4Attribute; 036 import org.apache.felix.framework.util.manifestparser.R4Directive; 037 import org.apache.felix.framework.util.manifestparser.R4Library; 038 import org.apache.felix.framework.util.manifestparser.Requirement; 039 import org.apache.felix.moduleloader.ICapability; 040 import org.apache.felix.moduleloader.IModule; 041 import org.apache.felix.moduleloader.IRequirement; 042 import org.apache.felix.moduleloader.IWire; 043 import org.osgi.framework.Constants; 044 045 public class Resolver 046 { 047 private final Logger m_logger; 048 049 // Execution environment. 050 private final String m_fwkExecEnvStr; 051 private final Set m_fwkExecEnvSet; 052 053 // Reusable empty array. 054 private static final IWire[] m_emptyWires = new IWire[0]; 055 056 public Resolver(Logger logger, String fwkExecEnvStr) 057 { 058 m_logger = logger; 059 m_fwkExecEnvStr = (fwkExecEnvStr != null) ? fwkExecEnvStr.trim() : null; 060 m_fwkExecEnvSet = parseExecutionEnvironments(fwkExecEnvStr); 061 } 062 063 // Returns a map of resolved bundles where the key is the module 064 // and the value is an array of wires. 065 public Map resolve(ResolverState state, IModule rootModule) throws ResolveException 066 { 067 // If the module is already resolved, then we can just return. 068 if (rootModule.isResolved()) 069 { 070 return null; 071 } 072 073 // This variable maps an unresolved module to a list of candidate 074 // sets, where there is one candidate set for each requirement that 075 // must be resolved. A candidate set contains the potential canidates 076 // available to resolve the requirement and the currently selected 077 // candidate index. 078 Map candidatesMap = new HashMap(); 079 080 // The first step is to populate the candidates map. This 081 // will use the target module to populate the candidates map 082 // with all potential modules that need to be resolved as a 083 // result of resolving the target module. The key of the 084 // map is a potential module to be resolved and the value is 085 // a list of candidate sets, one for each of the module's 086 // requirements, where each candidate set contains the potential 087 // candidates for resolving the requirement. Not all modules in 088 // this map will be resolved, only the target module and 089 // any candidates selected to resolve its requirements and the 090 // transitive requirements this implies. 091 populateCandidatesMap(state, candidatesMap, rootModule); 092 093 // The next step is to use the candidates map to determine if 094 // the class space for the root module is consistent. This 095 // is an iterative process that transitively walks the "uses" 096 // relationships of all packages visible from the root module 097 // checking for conflicts. If a conflict is found, it "increments" 098 // the configuration of currently selected potential candidates 099 // and tests them again. If this method returns, then it has found 100 // a consistent set of candidates; otherwise, a resolve exception 101 // is thrown if it exhausts all possible combinations and could 102 // not find a consistent class space. 103 findConsistentClassSpace(state, candidatesMap, rootModule); 104 105 // The final step is to create the wires for the root module and 106 // transitively all modules that are to be resolved from the 107 // selected candidates for resolving the root module's imports. 108 // When this call returns, each module's wiring and resolved 109 // attributes are set. The resulting wiring map is used below 110 // to fire resolved events outside of the synchronized block. 111 // The resolved module wire map maps a module to its array of 112 // wires. 113 return populateWireMap(state, candidatesMap, rootModule, new HashMap()); 114 } 115 116 // TODO: RESOLVER - Fix this return type. 117 // Return candidate wire in result[0] and wire map in result[1] 118 public Object[] resolveDynamicImport(ResolverState state, IModule importer, String pkgName) 119 throws ResolveException 120 { 121 ICapability candidate = null; 122 Map resolvedModuleWireMap = null; 123 124 // We can only create a dynamic import if the following 125 // conditions are met: 126 // 1. The package in question is not already imported. 127 // 2. The package in question is not accessible via require-bundle. 128 // 3. The package in question is not exported by the bundle. 129 // 4. The package in question matches a dynamic import of the bundle. 130 // The following call checks all of these conditions and returns 131 // a matching dynamic requirement if possible. 132 IRequirement dynReq = findAllowedDynamicImport(importer, pkgName); 133 if (dynReq != null) 134 { 135 // Create a new requirement based on the dynamic requirement, 136 // but substitute the precise package name for which we are 137 // looking, because it is not possible to use the potentially 138 // wildcarded version in the dynamic requirement. 139 R4Directive[] dirs = ((Requirement) dynReq).getDirectives(); 140 R4Attribute[] attrs = ((Requirement) dynReq).getAttributes(); 141 R4Attribute[] newAttrs = new R4Attribute[attrs.length]; 142 System.arraycopy(attrs, 0, newAttrs, 0, attrs.length); 143 for (int attrIdx = 0; attrIdx < newAttrs.length; attrIdx++) 144 { 145 if (newAttrs[attrIdx].getName().equals(ICapability.PACKAGE_PROPERTY)) 146 { 147 newAttrs[attrIdx] = new R4Attribute( 148 ICapability.PACKAGE_PROPERTY, pkgName, false); 149 break; 150 } 151 } 152 IRequirement target = new Requirement(ICapability.PACKAGE_NAMESPACE, dirs, newAttrs); 153 154 // See if there is a candidate exporter that satisfies the 155 // constrained dynamic requirement. 156 try 157 { 158 // Get "resolved" and "unresolved" candidates and put 159 // the "resolved" candidates first. 160 List candidates = state.getResolvedCandidates(target, importer); 161 candidates.addAll(state.getUnresolvedCandidates(target, importer)); 162 163 // Take the first candidate that can resolve. 164 for (int candIdx = 0; 165 (candidate == null) && (candIdx < candidates.size()); 166 candIdx++) 167 { 168 try 169 { 170 // If a map is returned, then the candidate resolved 171 // consistently with the importer. 172 resolvedModuleWireMap = 173 resolveDynamicImportCandidate( 174 state, ((ICapability) candidates.get(candIdx)).getModule(), 175 importer); 176 if (resolvedModuleWireMap != null) 177 { 178 candidate = (ICapability) candidates.get(candIdx); 179 } 180 } 181 catch (ResolveException ex) 182 { 183 // Ignore candidates that cannot resolve. 184 } 185 } 186 187 if (candidate != null) 188 { 189 // Create the wire and add it to the module. 190 Object[] result = new Object[2]; 191 result[0] = new R4Wire( 192 importer, dynReq, candidate.getModule(), 193 candidate); 194 result[1] = resolvedModuleWireMap; 195 return result; 196 } 197 } 198 catch (Exception ex) 199 { 200 m_logger.log(Logger.LOG_ERROR, "Unable to dynamically import package.", ex); 201 } 202 } 203 204 return null; 205 } 206 207 public static IRequirement findAllowedDynamicImport(IModule importer, String pkgName) 208 { 209 // We cannot import the default package, so return null in that case. 210 if (pkgName.length() == 0) 211 { 212 return null; 213 } 214 215 // If any of the module exports this package, then we cannot 216 // attempt to dynamically import it. 217 ICapability[] caps = importer.getCapabilities(); 218 for (int i = 0; (caps != null) && (i < caps.length); i++) 219 { 220 if (caps[i].getNamespace().equals(ICapability.PACKAGE_NAMESPACE) 221 && caps[i].getProperties().get(ICapability.PACKAGE_PROPERTY).equals(pkgName)) 222 { 223 return null; 224 } 225 } 226 // If any of our wires have this package, then we cannot 227 // attempt to dynamically import it. 228 IWire[] wires = importer.getWires(); 229 for (int i = 0; (wires != null) && (i < wires.length); i++) 230 { 231 if (wires[i].hasPackage(pkgName)) 232 { 233 return null; 234 } 235 } 236 237 // Loop through the importer's dynamic requirements to determine if 238 // there is a matching one for the package from which we want to 239 // load a class. 240 IRequirement[] dynamics = importer.getDynamicRequirements(); 241 for (int dynIdx = 0; 242 (dynamics != null) && (dynIdx < dynamics.length); 243 dynIdx++) 244 { 245 // First check to see if the dynamic requirement matches the 246 // package name; this means we have to do wildcard matching. 247 String dynPkgName = ((Requirement) dynamics[dynIdx]).getTargetName(); 248 boolean wildcard = (dynPkgName.lastIndexOf(".*") >= 0); 249 // Remove the "*", but keep the "." if wildcarded. 250 dynPkgName = (wildcard) 251 ? dynPkgName.substring(0, dynPkgName.length() - 1) : dynPkgName; 252 // If the dynamic requirement matches the package name, then 253 // create a new requirement for the specific package. 254 if (dynPkgName.equals("*") || 255 pkgName.equals(dynPkgName) || 256 (wildcard && pkgName.startsWith(dynPkgName))) 257 { 258 return dynamics[dynIdx]; 259 } 260 } 261 262 return null; 263 } 264 265 private Map resolveDynamicImportCandidate( 266 ResolverState state, IModule provider, IModule importer) 267 throws ResolveException 268 { 269 // If the provider of the dynamically imported package is not 270 // resolved, then we need to calculate the candidates to resolve 271 // it and see if there is a consistent class space for the 272 // provider. If there is no consistent class space, then a resolve 273 // exception is thrown. 274 Map candidatesMap = new HashMap(); 275 if (!provider.isResolved()) 276 { 277 populateCandidatesMap(state, candidatesMap, provider); 278 findConsistentClassSpace(state, candidatesMap, provider); 279 } 280 281 // If the provider can be successfully resolved, then verify that 282 // its class space is consistent with the existing class space of the 283 // module that instigated the dynamic import. 284 Map moduleMap = new HashMap(); 285 Map importerPkgMap = getModulePackages(moduleMap, importer, candidatesMap); 286 287 // Now we need to calculate the "uses" constraints of every package 288 // accessible to the provider module based on its current candidates. 289 Map usesMap = calculateUsesConstraints(provider, moduleMap, candidatesMap); 290 291 // Verify that none of the provider's implied "uses" constraints 292 // in the uses map conflict with anything in the importing module's 293 // package map. 294 for (Iterator iter = usesMap.entrySet().iterator(); iter.hasNext(); ) 295 { 296 Map.Entry entry = (Map.Entry) iter.next(); 297 298 // For the given "used" package, get that package from the 299 // importing module's package map, if present. 300 ResolvedPackage rp = (ResolvedPackage) importerPkgMap.get(entry.getKey()); 301 302 // If the "used" package is also visible to the importing 303 // module, make sure there is no conflicts in the implied 304 // "uses" constraints. 305 if (rp != null) 306 { 307 // Clone the resolve package so we can modify it. 308 rp = (ResolvedPackage) rp.clone(); 309 310 // Loop through all implied "uses" constraints for the current 311 // "used" package and verify that all packages are 312 // compatible with the packages of the importing module's 313 // package map. 314 List constraintList = (List) entry.getValue(); 315 for (int constIdx = 0; constIdx < constraintList.size(); constIdx++) 316 { 317 // Get a specific "uses" constraint for the current "used" 318 // package. 319 ResolvedPackage rpUses = (ResolvedPackage) constraintList.get(constIdx); 320 // Determine if the implied "uses" constraint is compatible with 321 // the improting module's packages for the given "used" 322 // package. They are compatible if one is the subset of the other. 323 // Retain the union of the two sets if they are compatible. 324 if (rpUses.isSubset(rp)) 325 { 326 // Do nothing because we already have the superset. 327 } 328 else if (rp.isSubset(rpUses)) 329 { 330 // Keep the superset, i.e., the union. 331 rp.m_capList.clear(); 332 rp.m_capList.addAll(rpUses.m_capList); 333 } 334 else 335 { 336 m_logger.log( 337 Logger.LOG_DEBUG, 338 "Constraint violation for " + importer 339 + " detected; module can see " 340 + rp + " and " + rpUses); 341 return null; 342 } 343 } 344 } 345 } 346 347 return populateWireMap(state, candidatesMap, provider, new HashMap()); 348 } 349 350 private void populateCandidatesMap( 351 ResolverState state, Map candidatesMap, IModule targetModule) 352 throws ResolveException 353 { 354 // Detect cycles. 355 if (candidatesMap.containsKey(targetModule)) 356 { 357 return; 358 } 359 360 // Verify that any required execution environment is satisfied. 361 verifyExecutionEnvironment(m_fwkExecEnvStr, m_fwkExecEnvSet, targetModule); 362 363 // Verify that any native libraries match the current platform. 364 verifyNativeLibraries(targetModule); 365 366 // Finally, resolve any dependencies the module may have. 367 368 // Add target module to the candidates map so we can detect cycles. 369 candidatesMap.put(targetModule, null); 370 371 // Create list to hold the resolving candidate sets for the target 372 // module's requirements. 373 List candSetList = new ArrayList(); 374 375 // Loop through each requirement and calculate its resolving 376 // set of candidates. 377 IRequirement[] reqs = targetModule.getRequirements(); 378 for (int reqIdx = 0; (reqs != null) && (reqIdx < reqs.length); reqIdx++) 379 { 380 // Get the candidates from the "resolved" and "unresolved" 381 // package maps. The "resolved" candidates have higher priority 382 // than "unresolved" ones, so put the "resolved" candidates 383 // at the front of the list of candidates. 384 List candidates = state.getResolvedCandidates(reqs[reqIdx], targetModule); 385 candidates.addAll(state.getUnresolvedCandidates(reqs[reqIdx], targetModule)); 386 387 // If we have candidates, then we need to recursively populate 388 // the resolver map with each of them. 389 ResolveException rethrow = null; 390 if (candidates.size() > 0) 391 { 392 for (Iterator it = candidates.iterator(); it.hasNext(); ) 393 { 394 ICapability candidate = (ICapability) it.next(); 395 396 try 397 { 398 // Only populate the resolver map with modules that 399 // are not already resolved. 400 if (!candidate.getModule().isResolved()) 401 { 402 populateCandidatesMap( 403 state, candidatesMap, candidate.getModule()); 404 } 405 } 406 catch (ResolveException ex) 407 { 408 // If we received a resolve exception, then the 409 // current candidate is not resolvable for some 410 // reason and should be removed from the list of 411 // candidates. For now, just null it. 412 it.remove(); 413 rethrow = ex; 414 } 415 } 416 } 417 418 // If no candidates exist at this point, then throw a 419 // resolve exception unless the import is optional. 420 if ((candidates.size() == 0) && !reqs[reqIdx].isOptional()) 421 { 422 // Remove invalid candidate and any cycle byproduct resolved modules. 423 removeInvalidCandidate(targetModule, candidatesMap, new ArrayList()); 424 425 // If we have received an exception while trying to populate 426 // the candidates map, rethrow that exception since it might 427 // be useful. NOTE: This is not necessarily the "only" 428 // correct exception, since it is possible that multiple 429 // candidates were not resolvable, but it is better than 430 // nothing. 431 if (rethrow != null) 432 { 433 throw rethrow; 434 } 435 else 436 { 437 throw new ResolveException( 438 "Unable to resolve.", targetModule, reqs[reqIdx]); 439 } 440 } 441 else if (candidates.size() > 0) 442 { 443 candSetList.add( 444 new CandidateSet(targetModule, reqs[reqIdx], candidates)); 445 } 446 } 447 448 // Now that the module's candidates have been calculated, add the 449 // candidate set list to the candidates map to be used for calculating 450 // uses constraints and ultimately wires. 451 candidatesMap.put(targetModule, candSetList); 452 } 453 454 private static void removeInvalidCandidate( 455 IModule invalidModule, Map candidatesMap, List invalidList) 456 { 457 // TODO: PERFORMANCE - This could be quicker if we kept track of who depended on whom, 458 // or only those modules used as candidates or those in a cycle. 459 460 // Remove the invalid module's candidates set list from the candidates map, 461 // since it should only contain entries for validly resolved modules. 462 candidatesMap.remove(invalidModule); 463 464 // Loop through each candidate set list in the candidates map to try 465 // to find references to the invalid module. 466 for (Iterator itCandidatesMap = candidatesMap.entrySet().iterator(); 467 itCandidatesMap.hasNext(); ) 468 { 469 Map.Entry entry = (Map.Entry) itCandidatesMap.next(); 470 IModule module = (IModule) entry.getKey(); 471 List candSetList = (List) entry.getValue(); 472 if (candSetList != null) 473 { 474 // Loop through each candidate set in the candidate set list 475 // to search for the invalid module. 476 for (Iterator itCandSetList = candSetList.iterator(); itCandSetList.hasNext(); ) 477 { 478 // Loop through the candidate in the candidate set and remove 479 // the invalid module if it is found. 480 CandidateSet cs = (CandidateSet) itCandSetList.next(); 481 for (Iterator itCandidates = cs.m_candidates.iterator(); 482 itCandidates.hasNext(); ) 483 { 484 // If the invalid module is a candidate, then remove it from 485 // the candidate set. 486 ICapability candCap = (ICapability) itCandidates.next(); 487 if (candCap.getModule().equals(invalidModule)) 488 { 489 itCandidates.remove(); 490 491 // If there are no more candidates in the candidate set, then 492 // remove it from the candidate set list. 493 if (cs.m_candidates.size() == 0) 494 { 495 itCandSetList.remove(); 496 497 // If the requirement is not optional, then add the module 498 // to a list which will be removed after removing the current 499 // invalid module. 500 if (!cs.m_requirement.isOptional() && (module != invalidModule) 501 && !invalidList.contains(module)) 502 { 503 invalidList.add(module); 504 } 505 } 506 break; 507 } 508 } 509 } 510 } 511 } 512 513 if (!invalidList.isEmpty()) 514 { 515 while (!invalidList.isEmpty()) 516 { 517 IModule m = (IModule) invalidList.remove(0); 518 removeInvalidCandidate(m, candidatesMap, invalidList); 519 } 520 } 521 } 522 523 // This flag indicates whether candidates have been rotated due to a 524 // "uses" constraint conflict. If so, then it is not necessary to perform 525 // a permutation, since rotating the candidates selected a new permutation. 526 // This part of an attempt to perform smarter permutations. 527 private boolean m_candidatesRotated = false; 528 529 private void findConsistentClassSpace( 530 ResolverState state, Map candidatesMap, IModule rootModule) 531 throws ResolveException 532 { 533 List candidatesList = null; 534 535 // The reusable module map maps a module to a map of 536 // resolved packages that are accessible by the given 537 // module. The set of resolved packages is calculated 538 // from the current candidates of the candidates map 539 // and the module's metadata. 540 Map moduleMap = new HashMap(); 541 542 // Reusable map used to test for cycles. 543 Map cycleMap = new HashMap(); 544 545 // Test the current potential candidates to determine if they 546 // are consistent. Keep looping until we find a consistent 547 // set or an exception is thrown. 548 while (!isSingletonConsistent(state, rootModule, moduleMap, candidatesMap) || 549 !isClassSpaceConsistent(rootModule, moduleMap, cycleMap, candidatesMap)) 550 { 551 // The incrementCandidateConfiguration() method requires 552 // ordered access to the candidates map, so we will create 553 // a reusable list once right here. 554 if (candidatesList == null) 555 { 556 candidatesList = new ArrayList(); 557 for (Iterator iter = candidatesMap.entrySet().iterator(); 558 iter.hasNext(); ) 559 { 560 Map.Entry entry = (Map.Entry) iter.next(); 561 candidatesList.add(entry.getValue()); 562 } 563 564 // Sort the bundles candidate sets according to a weighting 565 // based on how many multi-candidate requirements each has. 566 // The idea is to push bundles with more potential candidate 567 // permutations to the front so we can permutate over them 568 // more quickly, since they are likely to have more issues. 569 Collections.sort(candidatesList, new Comparator() { 570 public int compare(Object o1, Object o2) 571 { 572 int w1 = calculateWeight((List) o1); 573 int w2 = calculateWeight((List) o2); 574 if (w1 < w2) 575 { 576 return -1; 577 } 578 else if (w1 > w2) 579 { 580 return 1; 581 } 582 return 0; 583 } 584 585 private int calculateWeight(List candSetList) 586 { 587 int weight = 0; 588 for (int csIdx = 0; csIdx < candSetList.size(); csIdx++) 589 { 590 CandidateSet cs = (CandidateSet) candSetList.get(csIdx); 591 if ((cs.m_candidates != null) && (cs.m_candidates.size() > 1)) 592 { 593 weight += cs.m_candidates.size(); 594 } 595 } 596 return -weight; 597 } 598 }); 599 } 600 601 // Increment the candidate configuration to a new permutation so 602 // we can test again, unless some candidates have been rotated. 603 // In that case, we re-test the current permutation, since rotating 604 // the candidates effectively selects a new permutation. 605 if (!m_candidatesRotated) 606 { 607 incrementCandidateConfiguration(candidatesList); 608 } 609 else 610 { 611 m_candidatesRotated = false; 612 } 613 614 // Clear the module map. 615 moduleMap.clear(); 616 617 // Clear the cycle map. 618 cycleMap.clear(); 619 } 620 } 621 622 /** 623 * This methd checks to see if the target module and any of the candidate 624 * modules to resolve its dependencies violate any singleton constraints. 625 * Actually, it just creates a map of resolved singleton modules and then 626 * delegates all checking to another recursive method. 627 * 628 * @param targetModule the module that is the root of the tree of modules to check. 629 * @param moduleMap a map to cache the package space of each module. 630 * @param candidatesMap a map containing the all candidates to resolve all 631 * dependencies for all modules. 632 * @return <tt>true</tt> if all candidates are consistent with respect to singletons, 633 * <tt>false</tt> otherwise. 634 **/ 635 private boolean isSingletonConsistent( 636 ResolverState state, IModule targetModule, Map moduleMap, Map candidatesMap) 637 { 638 // Create a map of all resolved singleton modules. 639 Map singletonMap = new HashMap(); 640 IModule[] modules = state.getModules(); 641 for (int i = 0; (modules != null) && (i < modules.length); i++) 642 { 643 if (modules[i].isResolved() && isSingleton(modules[i])) 644 { 645 String symName = modules[i].getSymbolicName(); 646 singletonMap.put(symName, symName); 647 } 648 } 649 650 return areCandidatesSingletonConsistent( 651 state, targetModule, singletonMap, moduleMap, new HashMap(), candidatesMap); 652 } 653 654 /** 655 * This method recursive checks the target module and all of its transitive 656 * dependency modules to verify that they do not violate a singleton constraint. 657 * If the target module is a singleton, then it checks that againts existing 658 * singletons. Then it checks all current unresolved candidates recursively. 659 * 660 * @param targetModule the module that is the root of the tree of modules to check. 661 * @param singletonMap the current map of singleton symbolic names. 662 * @param moduleMap a map to cache the package space of each module. 663 * @param cycleMap a map to detect cycles. 664 * @param candidatesMap a map containing the all candidates to resolve all 665 * dependencies for all modules. 666 * @return <tt>true</tt> if all candidates are consistent with respect to singletons, 667 * <tt>false</tt> otherwise. 668 **/ 669 private boolean areCandidatesSingletonConsistent( 670 ResolverState state, IModule targetModule, 671 Map singletonMap, Map moduleMap, Map cycleMap, Map candidatesMap) 672 { 673 // If we are in a cycle, then assume true for now. 674 if (cycleMap.get(targetModule) != null) 675 { 676 return true; 677 } 678 679 // Record the target module in the cycle map. 680 cycleMap.put(targetModule, targetModule); 681 682 // Check to see if the targetModule violates a singleton. 683 // If not and it is a singleton, then add it to the singleton 684 // map since it will constrain other singletons. 685 String symName = targetModule.getSymbolicName(); 686 boolean isSingleton = isSingleton(targetModule); 687 if (isSingleton && singletonMap.containsKey(symName)) 688 { 689 return false; 690 } 691 else if (isSingleton) 692 { 693 singletonMap.put(symName, symName); 694 } 695 696 // Get the package space of the target module. 697 Map pkgMap = null; 698 try 699 { 700 pkgMap = getModulePackages(moduleMap, targetModule, candidatesMap); 701 } 702 catch (ResolveException ex) 703 { 704 m_logger.log( 705 Logger.LOG_DEBUG, 706 "Constraint violation for " + targetModule + " detected.", 707 ex); 708 return false; 709 } 710 711 // Loop through all of the target module's accessible packages and 712 // verify that all packages are consistent. 713 for (Iterator iter = pkgMap.entrySet().iterator(); iter.hasNext(); ) 714 { 715 Map.Entry entry = (Map.Entry) iter.next(); 716 // Get the resolved package, which contains the set of all 717 // packages for the given package. 718 ResolvedPackage rp = (ResolvedPackage) entry.getValue(); 719 // Loop through each capability and test if it is consistent. 720 for (int capIdx = 0; capIdx < rp.m_capList.size(); capIdx++) 721 { 722 // If the module for this capability is not resolved, then 723 // we have to see if resolving it would violate a singleton 724 // constraint. 725 ICapability cap = (ICapability) rp.m_capList.get(capIdx); 726 if (!cap.getModule().isResolved()) 727 { 728 return areCandidatesSingletonConsistent( 729 state, cap.getModule(), singletonMap, moduleMap, cycleMap, candidatesMap); 730 } 731 } 732 } 733 734 return true; 735 } 736 737 /** 738 * Returns true if the specified module is a singleton 739 * (i.e., directive singleton:=true in Bundle-SymbolicName). 740 * 741 * @param module the module to check for singleton status. 742 * @return true if the module is a singleton, false otherwise. 743 **/ 744 private static boolean isSingleton(IModule module) 745 { 746 final ICapability[] modCaps = Util.getCapabilityByNamespace( 747 module, Capability.MODULE_NAMESPACE); 748 if (modCaps == null || modCaps.length == 0) 749 { 750 // this should never happen? 751 return false; 752 } 753 final R4Directive[] dirs = ((Capability) modCaps[0]).getDirectives(); 754 for (int dirIdx = 0; (dirs != null) && (dirIdx < dirs.length); dirIdx++) 755 { 756 if (dirs[dirIdx].getName().equalsIgnoreCase(Constants.SINGLETON_DIRECTIVE) 757 && Boolean.valueOf(dirs[dirIdx].getValue()).booleanValue()) 758 { 759 return true; 760 } 761 } 762 return false; 763 } 764 765 private boolean isClassSpaceConsistent( 766 IModule targetModule, Map moduleMap, Map cycleMap, Map candidatesMap) 767 { 768 //System.out.println("isClassSpaceConsistent("+targetModule+")"); 769 // If we are in a cycle, then assume true for now. 770 if (cycleMap.get(targetModule) != null) 771 { 772 return true; 773 } 774 775 // Record the target module in the cycle map. 776 cycleMap.put(targetModule, targetModule); 777 778 // Get the package map for the target module, which is a 779 // map of all packages accessible to the module and their 780 // associated capabilities. 781 Map pkgMap = null; 782 try 783 { 784 pkgMap = getModulePackages(moduleMap, targetModule, candidatesMap); 785 } 786 catch (ResolveException ex) 787 { 788 m_logger.log( 789 Logger.LOG_DEBUG, 790 "Constraint violation for " + targetModule + " detected.", 791 ex); 792 return false; 793 } 794 795 // Loop through all of the target module's accessible packages and 796 // verify that all packages are consistent. 797 for (Iterator iter = pkgMap.entrySet().iterator(); iter.hasNext(); ) 798 { 799 Map.Entry entry = (Map.Entry) iter.next(); 800 // Get the resolved package, which contains the set of all 801 // capabilities for the given package. 802 ResolvedPackage rp = (ResolvedPackage) entry.getValue(); 803 // Loop through each capability and test if it is consistent. 804 for (int capIdx = 0; capIdx < rp.m_capList.size(); capIdx++) 805 { 806 ICapability cap = (ICapability) rp.m_capList.get(capIdx); 807 if (!isClassSpaceConsistent(cap.getModule(), moduleMap, cycleMap, candidatesMap)) 808 { 809 return false; 810 } 811 } 812 } 813 814 // Now we need to calculate the "uses" constraints of every package 815 // accessible to the target module based on the current candidates. 816 Map usesMap = null; 817 try 818 { 819 usesMap = calculateUsesConstraints(targetModule, moduleMap, candidatesMap); 820 } 821 catch (ResolveException ex) 822 { 823 m_logger.log( 824 Logger.LOG_DEBUG, 825 "Constraint violation for " + targetModule + " detected.", 826 ex); 827 return false; 828 } 829 830 // Verify that none of the implied "uses" constraints in the uses map 831 // conflict with anything in the target module's package map. 832 for (Iterator iter = usesMap.entrySet().iterator(); iter.hasNext(); ) 833 { 834 Map.Entry entry = (Map.Entry) iter.next(); 835 836 // For the given "used" package, get that package from the 837 // target module's package map, if present. 838 ResolvedPackage rp = (ResolvedPackage) pkgMap.get(entry.getKey()); 839 840 // If the "used" package is also visible to the target module, 841 // make sure there is no conflicts in the implied "uses" 842 // constraints. 843 if (rp != null) 844 { 845 // Clone the resolve package so we can modify it. 846 rp = (ResolvedPackage) rp.clone(); 847 848 // Loop through all implied "uses" constraints for the current 849 // "used" package and verify that all packages are 850 // compatible with the packages of the root module's 851 // package map. 852 List constraintList = (List) entry.getValue(); 853 for (int constIdx = 0; constIdx < constraintList.size(); constIdx++) 854 { 855 // Get a specific "uses" constraint for the current "used" 856 // package. 857 ResolvedPackage rpUses = (ResolvedPackage) constraintList.get(constIdx); 858 // Determine if the implied "uses" constraint is compatible with 859 // the target module's packages for the given "used" 860 // package. They are compatible if one is the subset of the other. 861 // Retain the union of the two sets if they are compatible. 862 if (rpUses.isSubset(rp)) 863 { 864 // Do nothing because we already have the superset. 865 } 866 else if (rp.isSubset(rpUses)) 867 { 868 // Keep the superset, i.e., the union. 869 rp.m_capList.clear(); 870 rp.m_capList.addAll(rpUses.m_capList); 871 } 872 else 873 { 874 m_logger.log( 875 Logger.LOG_DEBUG, 876 "Constraint violation for " + targetModule 877 + " detected; module can see " 878 + rp + " and " + rpUses); 879 880 // If the resolved package has a candidate set, then 881 // attempt to directly rotate the candidates to fix the 882 // "uses" constraint conflict. The idea is rather than 883 // blinding incrementing to the next permutation, we will 884 // try to target the permutation to the bundle with a 885 // conflict, which in some cases will be smarter. Only 886 // rotate the candidates if we have more than one and we 887 // haven't already rotated them completely. 888 if ((rp.m_cs != null) && (rp.m_cs.m_candidates.size() > 1) 889 && (rp.m_cs.m_rotated < rp.m_cs.m_candidates.size())) 890 { 891 // Rotate candidates. 892 ICapability first = (ICapability) rp.m_cs.m_candidates.get(0); 893 for (int i = 1; i < rp.m_cs.m_candidates.size(); i++) 894 { 895 rp.m_cs.m_candidates.set(i - 1, rp.m_cs.m_candidates.get(i)); 896 } 897 rp.m_cs.m_candidates.set(rp.m_cs.m_candidates.size() - 1, first); 898 rp.m_cs.m_rotated++; 899 m_candidatesRotated = true; 900 } 901 902 return false; 903 } 904 } 905 } 906 } 907 908 return true; 909 } 910 911 private static Map calculateUsesConstraints( 912 IModule targetModule, Map moduleMap, Map candidatesMap) 913 throws ResolveException 914 { 915 //System.out.println("calculateUsesConstraints("+targetModule+")"); 916 // Map to store calculated uses constraints. This maps a 917 // package name to a list of resolved packages, where each 918 // resolved package represents a constraint on anyone 919 // importing the given package name. This map is returned 920 // by this method. 921 Map usesMap = new HashMap(); 922 923 // Re-usable map to detect cycles. 924 Map cycleMap = new HashMap(); 925 926 // Get all packages accessible by the target module. 927 Map pkgMap = getModulePackages(moduleMap, targetModule, candidatesMap); 928 929 // Each package accessible from the target module is potentially 930 // comprised of one or more capabilities. The "uses" constraints 931 // implied by all capabilities must be calculated and combined to 932 // determine the complete set of implied "uses" constraints for 933 // each package accessible by the target module. 934 for (Iterator iter = pkgMap.entrySet().iterator(); iter.hasNext(); ) 935 { 936 Map.Entry entry = (Map.Entry) iter.next(); 937 ResolvedPackage rp = (ResolvedPackage) entry.getValue(); 938 for (int capIdx = 0; capIdx < rp.m_capList.size(); capIdx++) 939 { 940 usesMap = calculateUsesConstraints( 941 (ICapability) rp.m_capList.get(capIdx), 942 moduleMap, usesMap, cycleMap, candidatesMap); 943 } 944 } 945 return usesMap; 946 } 947 948 private static Map calculateUsesConstraints( 949 ICapability capTarget, Map moduleMap, Map usesMap, 950 Map cycleMap, Map candidatesMap) 951 throws ResolveException 952 { 953 //System.out.println("calculateUsesConstraints2("+psTarget.m_module+")"); 954 // If we are in a cycle, then return for now. 955 if (cycleMap.get(capTarget) != null) 956 { 957 return usesMap; 958 } 959 960 // Record the target capability in the cycle map. 961 cycleMap.put(capTarget, capTarget); 962 963 // Get all packages accessible from the module of the 964 // target capability. 965 Map pkgMap = getModulePackages(moduleMap, capTarget.getModule(), candidatesMap); 966 967 // Cast to implementation class to get access to cached data. 968 Capability cap = (Capability) capTarget; 969 970 // Loop through all "used" packages of the capability. 971 for (int i = 0; i < cap.getUses().length; i++) 972 { 973 // The target capability's module should have a resolved package 974 // for the "used" package in its set of accessible packages, 975 // since it claims to use it, so get the associated resolved 976 // package. 977 ResolvedPackage rp = (ResolvedPackage) pkgMap.get(cap.getUses()[i]); 978 979 // In general, the resolved package should not be null, 980 // but check for safety. 981 if (rp != null) 982 { 983 // First, iterate through all capabilities for the resolved 984 // package associated with the current "used" package and calculate 985 // and combine the "uses" constraints for each package. 986 for (int srcIdx = 0; srcIdx < rp.m_capList.size(); srcIdx++) 987 { 988 usesMap = calculateUsesConstraints( 989 (ICapability) rp.m_capList.get(srcIdx), 990 moduleMap, usesMap, cycleMap, candidatesMap); 991 } 992 993 // Then, add the resolved package for the current "used" package 994 // as a "uses" constraint too; add it to an existing constraint 995 // list if the current "used" package is already in the uses map. 996 List constraintList = (List) usesMap.get(cap.getUses()[i]); 997 if (constraintList == null) 998 { 999 constraintList = new ArrayList(); 1000 } 1001 constraintList.add(rp); 1002 usesMap.put(cap.getUses()[i], constraintList); 1003 } 1004 } 1005 1006 return usesMap; 1007 } 1008 1009 private static Map getModulePackages(Map moduleMap, IModule module, Map candidatesMap) 1010 throws ResolveException 1011 { 1012 Map map = (Map) moduleMap.get(module); 1013 1014 if (map == null) 1015 { 1016 map = calculateModulePackages(module, candidatesMap); 1017 moduleMap.put(module, map); 1018 } 1019 return map; 1020 } 1021 1022 /** 1023 * <p> 1024 * Calculates the module's set of accessible packages and their 1025 * assocaited package capabilities. This method uses the current candidates 1026 * for resolving the module's requirements from the candidate map 1027 * to calculate the module's accessible packages. 1028 * </p> 1029 * @param module the module whose package map is to be calculated. 1030 * @param candidatesMap the map of potential candidates for resolving 1031 * the module's requirements. 1032 * @return a map of the packages accessible to the specified module where 1033 * the key of the map is the package name and the value of the map 1034 * is a ResolvedPackage. 1035 **/ 1036 private static Map calculateModulePackages(IModule module, Map candidatesMap) 1037 throws ResolveException 1038 { 1039 //System.out.println("calculateModulePackages("+module+")"); 1040 Map importedPackages = calculateImportedPackages(module, candidatesMap); 1041 Map exportedPackages = calculateExportedPackages(module); 1042 Map requiredPackages = calculateRequiredPackages(module, candidatesMap); 1043 1044 // Merge exported packages into required packages. If a package is both 1045 // exported and required, then append the exported package to the end of 1046 // the require packages; otherwise just add it to the package map. 1047 for (Iterator i = exportedPackages.entrySet().iterator(); i.hasNext(); ) 1048 { 1049 Map.Entry entry = (Map.Entry) i.next(); 1050 ResolvedPackage rpReq = (ResolvedPackage) requiredPackages.get(entry.getKey()); 1051 if (rpReq != null) 1052 { 1053 // Merge exported and required packages, avoiding duplicate 1054 // packages and maintaining ordering. 1055 ResolvedPackage rpExport = (ResolvedPackage) entry.getValue(); 1056 rpReq.merge(rpExport); 1057 } 1058 else 1059 { 1060 requiredPackages.put(entry.getKey(), entry.getValue()); 1061 } 1062 } 1063 1064 // Merge imported packages into required packages. Imports overwrite 1065 // any required and/or exported package. 1066 for (Iterator i = importedPackages.entrySet().iterator(); i.hasNext(); ) 1067 { 1068 Map.Entry entry = (Map.Entry) i.next(); 1069 requiredPackages.put(entry.getKey(), entry.getValue()); 1070 } 1071 1072 return requiredPackages; 1073 } 1074 1075 private static Map calculateImportedPackages(IModule targetModule, Map candidatesMap) 1076 throws ResolveException 1077 { 1078 return (candidatesMap.get(targetModule) == null) 1079 ? calculateImportedPackagesResolved(targetModule) 1080 : calculateImportedPackagesUnresolved(targetModule, candidatesMap); 1081 } 1082 1083 private static Map calculateImportedPackagesUnresolved(IModule targetModule, Map candidatesMap) 1084 throws ResolveException 1085 { 1086 //System.out.println("calculateImportedPackagesUnresolved("+targetModule+")"); 1087 Map pkgMap = new HashMap(); 1088 1089 // Get the candidate set list to get all candidates for 1090 // all of the target module's requirements. 1091 List candSetList = (List) candidatesMap.get(targetModule); 1092 1093 // Loop through all candidate sets that represent import dependencies 1094 // for the target module and add the current candidate's packages 1095 // to the imported package map. 1096 for (int candSetIdx = 0; 1097 (candSetList != null) && (candSetIdx < candSetList.size()); 1098 candSetIdx++) 1099 { 1100 CandidateSet cs = (CandidateSet) candSetList.get(candSetIdx); 1101 ICapability candCap = (ICapability) cs.m_candidates.get(cs.m_idx); 1102 1103 if (candCap.getNamespace().equals(ICapability.PACKAGE_NAMESPACE)) 1104 { 1105 String pkgName = (String) 1106 candCap.getProperties().get(ICapability.PACKAGE_PROPERTY); 1107 1108 ResolvedPackage rp = new ResolvedPackage(pkgName, cs); 1109 rp.m_capList.add(candCap); 1110 pkgMap.put(rp.m_name, rp); 1111 } 1112 } 1113 1114 return pkgMap; 1115 } 1116 1117 private static Map calculateImportedPackagesResolved(IModule targetModule) 1118 throws ResolveException 1119 { 1120 //System.out.println("calculateImportedPackagesResolved("+targetModule+")"); 1121 Map pkgMap = new HashMap(); 1122 1123 // Loop through the target module's wires for package 1124 // dependencies and add the resolved packages to the 1125 // imported package map. 1126 IWire[] wires = targetModule.getWires(); 1127 for (int wireIdx = 0; (wires != null) && (wireIdx < wires.length); wireIdx++) 1128 { 1129 if (wires[wireIdx].getCapability().getNamespace().equals(ICapability.PACKAGE_NAMESPACE)) 1130 { 1131 String pkgName = (String) 1132 wires[wireIdx].getCapability().getProperties().get(ICapability.PACKAGE_PROPERTY); 1133 ResolvedPackage rp = (ResolvedPackage) pkgMap.get(pkgName); 1134 rp = (rp == null) ? new ResolvedPackage(pkgName, null) : rp; 1135 rp.m_capList.add(wires[wireIdx].getCapability()); 1136 pkgMap.put(rp.m_name, rp); 1137 } 1138 } 1139 1140 return pkgMap; 1141 } 1142 1143 private static Map calculateExportedPackages(IModule targetModule) 1144 { 1145 //System.out.println("calculateExportedPackages("+targetModule+")"); 1146 Map pkgMap = new HashMap(); 1147 1148 // Loop through the target module's capabilities that represent 1149 // exported packages and add them to the exported package map. 1150 ICapability[] caps = targetModule.getCapabilities(); 1151 for (int capIdx = 0; (caps != null) && (capIdx < caps.length); capIdx++) 1152 { 1153 if (caps[capIdx].getNamespace().equals(ICapability.PACKAGE_NAMESPACE)) 1154 { 1155 String pkgName = (String) 1156 caps[capIdx].getProperties().get(ICapability.PACKAGE_PROPERTY); 1157 ResolvedPackage rp = (ResolvedPackage) pkgMap.get(pkgName); 1158 rp = (rp == null) ? new ResolvedPackage(pkgName, null) : rp; 1159 rp.m_capList.add(caps[capIdx]); 1160 pkgMap.put(rp.m_name, rp); 1161 } 1162 } 1163 1164 return pkgMap; 1165 } 1166 1167 private static Map calculateRequiredPackages(IModule targetModule, Map candidatesMap) 1168 { 1169 return (candidatesMap.get(targetModule) == null) 1170 ? calculateRequiredPackagesResolved(targetModule) 1171 : calculateRequiredPackagesUnresolved(targetModule, candidatesMap); 1172 } 1173 1174 private static Map calculateRequiredPackagesUnresolved(IModule targetModule, Map candidatesMap) 1175 { 1176 //System.out.println("calculateRequiredPackagesUnresolved("+targetModule+")"); 1177 Map pkgMap = new HashMap(); 1178 1179 // Loop through target module's candidate list for candidates 1180 // for its module dependencies and merge re-exported packages. 1181 List candSetList = (List) candidatesMap.get(targetModule); 1182 for (int candSetIdx = 0; 1183 (candSetList != null) && (candSetIdx < candSetList.size()); 1184 candSetIdx++) 1185 { 1186 CandidateSet cs = (CandidateSet) candSetList.get(candSetIdx); 1187 ICapability candCap = (ICapability) cs.m_candidates.get(cs.m_idx); 1188 1189 // If the capabaility is a module dependency, then flatten it to packages. 1190 if (candCap.getNamespace().equals(ICapability.MODULE_NAMESPACE)) 1191 { 1192 // Calculate transitively required packages. 1193 Map cycleMap = new HashMap(); 1194 cycleMap.put(targetModule, targetModule); 1195 Map requireMap = 1196 calculateExportedAndReexportedPackages( 1197 candCap, candidatesMap, cycleMap); 1198 1199 // Take the flattened required package map for the current 1200 // module dependency and merge it into the existing map 1201 // of required packages. 1202 for (Iterator reqIter = requireMap.entrySet().iterator(); reqIter.hasNext(); ) 1203 { 1204 Map.Entry entry = (Map.Entry) reqIter.next(); 1205 ResolvedPackage rp = (ResolvedPackage) pkgMap.get(entry.getKey()); 1206 if (rp != null) 1207 { 1208 // Merge required packages, avoiding duplicate 1209 // packages and maintaining ordering. 1210 ResolvedPackage rpReq = (ResolvedPackage) entry.getValue(); 1211 rp.merge(rpReq); 1212 } 1213 else 1214 { 1215 pkgMap.put(entry.getKey(), entry.getValue()); 1216 } 1217 } 1218 } 1219 } 1220 1221 return pkgMap; 1222 } 1223 1224 private static Map calculateRequiredPackagesResolved(IModule targetModule) 1225 { 1226 //System.out.println("calculateRequiredPackagesResolved("+targetModule+")"); 1227 Map pkgMap = new HashMap(); 1228 1229 // Loop through target module's wires for module dependencies 1230 // and merge re-exported packages. 1231 IWire[] wires = targetModule.getWires(); 1232 for (int i = 0; (wires != null) && (i < wires.length); i++) 1233 { 1234 // If the wire is a module dependency, then flatten it to packages. 1235 if (wires[i].getCapability().getNamespace().equals(ICapability.MODULE_NAMESPACE)) 1236 { 1237 // Calculate transitively required packages. 1238 // We can call calculateExportedAndReexportedPackagesResolved() 1239 // directly, since we know all dependencies have to be resolved 1240 // because this module itself is resolved. 1241 Map cycleMap = new HashMap(); 1242 cycleMap.put(targetModule, targetModule); 1243 Map requireMap = 1244 calculateExportedAndReexportedPackagesResolved( 1245 wires[i].getExporter(), cycleMap); 1246 1247 // Take the flattened required package map for the current 1248 // module dependency and merge it into the existing map 1249 // of required packages. 1250 for (Iterator reqIter = requireMap.entrySet().iterator(); reqIter.hasNext(); ) 1251 { 1252 Map.Entry entry = (Map.Entry) reqIter.next(); 1253 ResolvedPackage rp = (ResolvedPackage) pkgMap.get(entry.getKey()); 1254 if (rp != null) 1255 { 1256 // Merge required packages, avoiding duplicate 1257 // packages and maintaining ordering. 1258 ResolvedPackage rpReq = (ResolvedPackage) entry.getValue(); 1259 rp.merge(rpReq); 1260 } 1261 else 1262 { 1263 pkgMap.put(entry.getKey(), entry.getValue()); 1264 } 1265 } 1266 } 1267 } 1268 1269 return pkgMap; 1270 } 1271 1272 private static Map calculateExportedAndReexportedPackages( 1273 ICapability capTarget, Map candidatesMap, Map cycleMap) 1274 { 1275 return (candidatesMap.get(capTarget.getModule()) == null) 1276 ? calculateExportedAndReexportedPackagesResolved(capTarget.getModule(), cycleMap) 1277 : calculateExportedAndReexportedPackagesUnresolved(capTarget, candidatesMap, cycleMap); 1278 } 1279 1280 private static Map calculateExportedAndReexportedPackagesUnresolved( 1281 ICapability capTarget, Map candidatesMap, Map cycleMap) 1282 { 1283 //System.out.println("calculateExportedAndReexportedPackagesUnresolved("+psTarget.m_module+")"); 1284 Map pkgMap = new HashMap(); 1285 1286 if (cycleMap.get(capTarget.getModule()) != null) 1287 { 1288 return pkgMap; 1289 } 1290 1291 cycleMap.put(capTarget.getModule(), capTarget.getModule()); 1292 1293 // Loop through all current candidates for target module's dependencies 1294 // and calculate the module's complete set of required packages (and 1295 // their associated packages) and the complete set of required 1296 // packages to be re-exported. 1297 Map allRequiredMap = new HashMap(); 1298 Map reexportedPkgMap = new HashMap(); 1299 List candSetList = (List) candidatesMap.get(capTarget.getModule()); 1300 for (int candSetIdx = 0; candSetIdx < candSetList.size(); candSetIdx++) 1301 { 1302 CandidateSet cs = (CandidateSet) candSetList.get(candSetIdx); 1303 ICapability candCap = (ICapability) cs.m_candidates.get(cs.m_idx); 1304 1305 // If the candidate is resolving a module dependency, then 1306 // flatten the required packages if they are re-exported. 1307 if (candCap.getNamespace().equals(ICapability.MODULE_NAMESPACE)) 1308 { 1309 // Determine if required packages are re-exported. 1310 boolean reexport = false; 1311 R4Directive[] dirs = ((Requirement) cs.m_requirement).getDirectives(); 1312 for (int dirIdx = 0; 1313 !reexport && (dirs != null) && (dirIdx < dirs.length); dirIdx++) 1314 { 1315 if (dirs[dirIdx].getName().equals(Constants.VISIBILITY_DIRECTIVE) 1316 && dirs[dirIdx].getValue().equals(Constants.VISIBILITY_REEXPORT)) 1317 { 1318 reexport = true; 1319 } 1320 } 1321 1322 // Recursively calculate the required packages for the 1323 // current candidate. 1324 Map requiredMap = 1325 calculateExportedAndReexportedPackages(candCap, candidatesMap, cycleMap); 1326 1327 // Merge the candidate's exported and required packages 1328 // into the complete set of required packages. 1329 for (Iterator reqIter = requiredMap.entrySet().iterator(); reqIter.hasNext(); ) 1330 { 1331 Map.Entry entry = (Map.Entry) reqIter.next(); 1332 String pkgName = (String) entry.getKey(); 1333 1334 // Merge the current set of required packages into 1335 // the overall complete set of required packages. 1336 // We calculate all the required packages, because 1337 // despite the fact that some packages will be required 1338 // "privately" and some will be required "reexport", any 1339 // re-exported packages will ultimately need to 1340 // be combined with privately required packages, 1341 // if the required packages overlap. This is one of the 1342 // bad things about require-bundle behavior, it does not 1343 // necessarily obey the visibility rules declared in the 1344 // dependency. 1345 ResolvedPackage rp = (ResolvedPackage) allRequiredMap.get(pkgName); 1346 if (rp != null) 1347 { 1348 // Create the union of all packages. 1349 ResolvedPackage rpReq = (ResolvedPackage) entry.getValue(); 1350 rp.merge(rpReq); 1351 } 1352 else 1353 { 1354 // Add package to required map. 1355 allRequiredMap.put(pkgName, entry.getValue()); 1356 } 1357 1358 // Keep track of all required packages to be re-exported. 1359 // All re-exported packages will need to be merged into the 1360 // target module's package map and become part of its overall 1361 // export signature. 1362 if (reexport) 1363 { 1364 reexportedPkgMap.put(pkgName, pkgName); 1365 } 1366 } 1367 } 1368 } 1369 1370 // For the target module we have now calculated its entire set 1371 // of required packages and their associated packages in 1372 // allRequiredMap and have calculated all packages to be re-exported 1373 // in reexportedPkgMap. Add all re-exported required packages to the 1374 // target module's package map since they will be part of its export 1375 // signature. 1376 for (Iterator iter = reexportedPkgMap.entrySet().iterator(); iter.hasNext(); ) 1377 { 1378 String pkgName = (String) ((Map.Entry) iter.next()).getKey(); 1379 pkgMap.put(pkgName, allRequiredMap.get(pkgName)); 1380 } 1381 1382 // Now loop through the target module's export package capabilities and add 1383 // the target module's export capability as a source for any exported packages. 1384 ICapability[] candCaps = capTarget.getModule().getCapabilities(); 1385 for (int capIdx = 0; (candCaps != null) && (capIdx < candCaps.length); capIdx++) 1386 { 1387 if (candCaps[capIdx].getNamespace().equals(ICapability.PACKAGE_NAMESPACE)) 1388 { 1389 String pkgName = (String) 1390 candCaps[capIdx].getProperties().get(ICapability.PACKAGE_PROPERTY); 1391 ResolvedPackage rp = (ResolvedPackage) pkgMap.get(pkgName); 1392 rp = (rp == null) ? new ResolvedPackage(pkgName, null) : rp; 1393 rp.m_capList.add(candCaps[capIdx]); 1394 pkgMap.put(rp.m_name, rp); 1395 } 1396 } 1397 1398 return pkgMap; 1399 } 1400 1401 private static Map calculateExportedAndReexportedPackagesResolved( 1402 IModule targetModule, Map cycleMap) 1403 { 1404 //System.out.println("calculateExportedAndRequiredPackagesResolved("+targetModule+")"); 1405 Map pkgMap = new HashMap(); 1406 1407 if (cycleMap.get(targetModule) != null) 1408 { 1409 return pkgMap; 1410 } 1411 1412 cycleMap.put(targetModule, targetModule); 1413 1414 // Loop through all wires for the target module's module dependencies 1415 // and calculate the module's complete set of required packages (and 1416 // their associated sources) and the complete set of required 1417 // packages to be re-exported. 1418 Map allRequiredMap = new HashMap(); 1419 Map reexportedPkgMap = new HashMap(); 1420 IWire[] wires = targetModule.getWires(); 1421 for (int i = 0; (wires != null) && (i < wires.length); i++) 1422 { 1423 // If the wire is a module dependency, then flatten it to packages. 1424 if (wires[i].getCapability().getNamespace().equals(ICapability.MODULE_NAMESPACE)) 1425 { 1426 // Determine if required packages are re-exported. 1427 boolean reexport = false; 1428 R4Directive[] dirs = ((Requirement) wires[i].getRequirement()).getDirectives(); 1429 for (int dirIdx = 0; 1430 !reexport && (dirs != null) && (dirIdx < dirs.length); dirIdx++) 1431 { 1432 if (dirs[dirIdx].getName().equals(Constants.VISIBILITY_DIRECTIVE) 1433 && dirs[dirIdx].getValue().equals(Constants.VISIBILITY_REEXPORT)) 1434 { 1435 reexport = true; 1436 } 1437 } 1438 1439 // Recursively calculate the required packages for the 1440 // wire's exporting module. 1441 Map requiredMap = calculateExportedAndReexportedPackagesResolved( 1442 wires[i].getExporter(), cycleMap); 1443 1444 // Merge the wires exported and re-exported packages 1445 // into the complete set of required packages. 1446 for (Iterator reqIter = requiredMap.entrySet().iterator(); reqIter.hasNext(); ) 1447 { 1448 Map.Entry entry = (Map.Entry) reqIter.next(); 1449 String pkgName = (String) entry.getKey(); 1450 1451 // Merge the current set of required packages into 1452 // the overall complete set of required packages. 1453 // We calculate all the required packages, because 1454 // despite the fact that some packages will be required 1455 // "privately" and some will be required "reexport", any 1456 // re-exported packages will ultimately need to 1457 // be combined with privately required packages, 1458 // if the required packages overlap. This is one of the 1459 // bad things about require-bundle behavior, it does not 1460 // necessarily obey the visibility rules declared in the 1461 // dependency. 1462 ResolvedPackage rp = (ResolvedPackage) allRequiredMap.get(pkgName); 1463 if (rp != null) 1464 { 1465 // Create the union of all packages. 1466 ResolvedPackage rpReq = (ResolvedPackage) entry.getValue(); 1467 rp.merge(rpReq); 1468 } 1469 else 1470 { 1471 // Add package to required map. 1472 allRequiredMap.put(pkgName, entry.getValue()); 1473 } 1474 1475 // Keep track of all required packages to be re-exported. 1476 // All re-exported packages will need to be merged into the 1477 // target module's package map and become part of its overall 1478 // export signature. 1479 if (reexport) 1480 { 1481 reexportedPkgMap.put(pkgName, pkgName); 1482 } 1483 } 1484 } 1485 } 1486 1487 // For the target module we have now calculated its entire set 1488 // of required packages and their associated source capabilities in 1489 // allRequiredMap and have calculated all packages to be re-exported 1490 // in reexportedPkgMap. Add all re-exported required packages to the 1491 // target module's package map since they will be part of its export 1492 // signature. 1493 for (Iterator iter = reexportedPkgMap.entrySet().iterator(); iter.hasNext(); ) 1494 { 1495 String pkgName = (String) ((Map.Entry) iter.next()).getKey(); 1496 pkgMap.put(pkgName, allRequiredMap.get(pkgName)); 1497 } 1498 1499 // Now loop through the target module's export package capabilities and 1500 // add the target module as a source for any exported packages. 1501 ICapability[] caps = targetModule.getCapabilities(); 1502 for (int i = 0; (caps != null) && (i < caps.length); i++) 1503 { 1504 if (caps[i].getNamespace().equals(ICapability.PACKAGE_NAMESPACE)) 1505 { 1506 String pkgName = (String) 1507 caps[i].getProperties().get(ICapability.PACKAGE_PROPERTY); 1508 ResolvedPackage rp = (ResolvedPackage) pkgMap.get(pkgName); 1509 rp = (rp == null) ? new ResolvedPackage(pkgName, null) : rp; 1510 rp.m_capList.add(caps[i]); 1511 pkgMap.put(rp.m_name, rp); 1512 } 1513 } 1514 1515 return pkgMap; 1516 } 1517 1518 private static Map calculateCandidateRequiredPackages( 1519 IModule module, ICapability capTarget, Map candidatesMap) 1520 { 1521 //System.out.println("calculateCandidateRequiredPackages("+module+")"); 1522 Map cycleMap = new HashMap(); 1523 cycleMap.put(module, module); 1524 return calculateExportedAndReexportedPackages(capTarget, candidatesMap, cycleMap); 1525 } 1526 1527 private static void incrementCandidateConfiguration(List resolverList) 1528 throws ResolveException 1529 { 1530 for (int i = 0; i < resolverList.size(); i++) 1531 { 1532 List candSetList = (List) resolverList.get(i); 1533 for (int j = 0; j < candSetList.size(); j++) 1534 { 1535 CandidateSet cs = (CandidateSet) candSetList.get(j); 1536 // See if we can increment the candidate set, without overflowing 1537 // the candidate array bounds. 1538 if ((cs.m_idx + 1) < cs.m_candidates.size()) 1539 { 1540 cs.m_idx++; 1541 return; 1542 } 1543 // If the index will overflow the candidate array bounds, 1544 // then set the index back to zero and try to increment 1545 // the next candidate. 1546 else 1547 { 1548 cs.m_idx = 0; 1549 } 1550 } 1551 } 1552 throw new ResolveException( 1553 "Unable to resolve due to constraint violation.", null, null); 1554 } 1555 1556 private static Map populateWireMap( 1557 ResolverState state, Map candidatesMap, IModule importer, Map wireMap) 1558 { 1559 // If the module is already resolved or it is part of 1560 // a cycle, then just return the wire map. 1561 if (importer.isResolved() || (wireMap.get(importer) != null)) 1562 { 1563 return wireMap; 1564 } 1565 1566 // Get the candidate set list for the importer. 1567 List candSetList = (List) candidatesMap.get(importer); 1568 1569 List moduleWires = new ArrayList(); 1570 List packageWires = new ArrayList(); 1571 1572 // Put the module in the wireMap with an empty wire array; 1573 // we do this early so we can use it to detect cycles. 1574 wireMap.put(importer, m_emptyWires); 1575 1576 // Loop through each candidate Set and create a wire 1577 // for the selected candidate for the associated import. 1578 for (int candSetIdx = 0; candSetIdx < candSetList.size(); candSetIdx++) 1579 { 1580 // Get the current candidate set. 1581 CandidateSet cs = (CandidateSet) candSetList.get(candSetIdx); 1582 1583 // Create a module wire for module dependencies. 1584 if (cs.m_requirement.getNamespace().equals(ICapability.MODULE_NAMESPACE)) 1585 { 1586 moduleWires.add(new R4WireModule( 1587 importer, 1588 cs.m_requirement, 1589 ((ICapability) cs.m_candidates.get(cs.m_idx)).getModule(), 1590 ((ICapability) cs.m_candidates.get(cs.m_idx)), 1591 calculateCandidateRequiredPackages( 1592 importer, (ICapability) cs.m_candidates.get(cs.m_idx), candidatesMap))); 1593 } 1594 // Create a package wire for package dependencies. 1595 // Filter out the case where a module imports from 1596 // itself, since the module should simply load from 1597 // its internal class path in this case. 1598 else if (importer != ((ICapability) cs.m_candidates.get(cs.m_idx)).getModule()) 1599 { 1600 // Add wire for imported package. 1601 packageWires.add(new R4Wire( 1602 importer, 1603 cs.m_requirement, 1604 ((ICapability) cs.m_candidates.get(cs.m_idx)).getModule(), 1605 ((ICapability) cs.m_candidates.get(cs.m_idx)))); 1606 } 1607 1608 // Create any necessary wires for the selected candidate module. 1609 wireMap = populateWireMap( 1610 state, candidatesMap, 1611 ((ICapability) cs.m_candidates.get(cs.m_idx)).getModule(), 1612 wireMap); 1613 } 1614 1615 packageWires.addAll(moduleWires); 1616 wireMap.put(importer, packageWires.toArray(new IWire[packageWires.size()])); 1617 1618 return wireMap; 1619 } 1620 1621 // 1622 // Utility methods. 1623 // 1624 1625 private static void verifyNativeLibraries(IModule module) 1626 throws ResolveException 1627 { 1628 // Next, try to resolve any native code, since the module is 1629 // not resolvable if its native code cannot be loaded. 1630 R4Library[] libs = module.getNativeLibraries(); 1631 if (libs != null) 1632 { 1633 String msg = null; 1634 // Verify that all native libraries exist in advance; this will 1635 // throw an exception if the native library does not exist. 1636 for (int libIdx = 0; (msg == null) && (libIdx < libs.length); libIdx++) 1637 { 1638 String entryName = libs[libIdx].getEntryName(); 1639 if (entryName != null) 1640 { 1641 if (!module.getContent().hasEntry(entryName)) 1642 { 1643 msg = "Native library does not exist: " + entryName; 1644 } 1645 } 1646 } 1647 // If we have a zero-length native library array, then 1648 // this means no native library class could be selected 1649 // so we should fail to resolve. 1650 if (libs.length == 0) 1651 { 1652 msg = "No matching native libraries found."; 1653 } 1654 if (msg != null) 1655 { 1656 throw new ResolveException(msg, module, null); 1657 } 1658 } 1659 } 1660 1661 /** 1662 * Checks to see if the passed in module's required execution environment 1663 * is provided by the framework. 1664 * @param fwkExecEvnStr The original property value of the framework's 1665 * supported execution environments. 1666 * @param fwkExecEnvSet Parsed set of framework's supported execution environments. 1667 * @param module The module whose required execution environment is to be to verified. 1668 * @throws ResolveException if the module's required execution environment does 1669 * not match the framework's supported execution environment. 1670 **/ 1671 private static void verifyExecutionEnvironment( 1672 String fwkExecEnvStr, Set fwkExecEnvSet, IModule module) 1673 throws ResolveException 1674 { 1675 String bundleExecEnvStr = (String) 1676 module.getHeaders().get(Constants.BUNDLE_REQUIREDEXECUTIONENVIRONMENT); 1677 if (bundleExecEnvStr != null) 1678 { 1679 bundleExecEnvStr = bundleExecEnvStr.trim(); 1680 1681 // If the bundle has specified an execution environment and the 1682 // framework has an execution environment specified, then we must 1683 // check for a match. 1684 if (!bundleExecEnvStr.equals("") 1685 && (fwkExecEnvStr != null) 1686 && (fwkExecEnvStr.length() > 0)) 1687 { 1688 StringTokenizer tokens = new StringTokenizer(bundleExecEnvStr, ","); 1689 boolean found = false; 1690 while (tokens.hasMoreTokens() && !found) 1691 { 1692 if (fwkExecEnvSet.contains(tokens.nextToken().trim())) 1693 { 1694 found = true; 1695 } 1696 } 1697 if (!found) 1698 { 1699 throw new ResolveException( 1700 "Execution environment not supported: " 1701 + bundleExecEnvStr, module, null); 1702 } 1703 } 1704 } 1705 } 1706 1707 /** 1708 * Updates the framework wide execution environment string and a cached Set of 1709 * execution environment tokens from the comma delimited list specified by the 1710 * system variable 'org.osgi.framework.executionenvironment'. 1711 * @param frameworkEnvironment Comma delimited string of provided execution environments 1712 **/ 1713 private static Set parseExecutionEnvironments(String fwkExecEnvStr) 1714 { 1715 Set newSet = new HashSet(); 1716 if (fwkExecEnvStr != null) 1717 { 1718 StringTokenizer tokens = new StringTokenizer(fwkExecEnvStr, ","); 1719 while (tokens.hasMoreTokens()) 1720 { 1721 newSet.add(tokens.nextToken().trim()); 1722 } 1723 } 1724 return newSet; 1725 } 1726 1727 // 1728 // Inner classes. 1729 // 1730 1731 public static interface ResolverState 1732 { 1733 IModule[] getModules(); 1734 List getResolvedCandidates(IRequirement req, IModule reqModule); 1735 List getUnresolvedCandidates(IRequirement req, IModule reqModule); 1736 } 1737 }