1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one 3 * or more contributor license agreements. See the NOTICE file 4 * distributed with this work for additional information 5 * regarding copyright ownership. The ASF licenses this file 6 * to you under the Apache License, Version 2.0 (the 7 * "License"); you may not use this file except in compliance 8 * with the License. You may obtain a copy of the License at 9 * 10 * http://www.apache.org/licenses/LICENSE-2.0 11 * 12 * Unless required by applicable law or agreed to in writing, 13 * software distributed under the License is distributed on an 14 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 15 * KIND, either express or implied. See the License for the 16 * specific language governing permissions and limitations 17 * under the License. 18 */ 19 package org.apache.felix.resolver; 20 21 import java.util.*; 22 import java.util.Map.Entry; 23 import java.util.concurrent.atomic.AtomicBoolean; 24 25 import org.apache.felix.resolver.ResolverImpl.PermutationType; 26 import org.apache.felix.resolver.ResolverImpl.ResolveSession; 27 import org.apache.felix.resolver.reason.ReasonException; 28 import org.apache.felix.resolver.util.*; 29 import org.osgi.framework.Version; 30 import org.osgi.framework.namespace.*; 31 import org.osgi.resource.*; 32 import org.osgi.service.resolver.HostedCapability; 33 import org.osgi.service.resolver.ResolutionException; 34 import org.osgi.service.resolver.ResolveContext; 35 36 class Candidates 37 { 38 static class PopulateResult { 39 boolean success; 40 ResolutionError error; 41 List<Requirement> remaining; 42 Map<Requirement, List<Capability>> candidates; 43 44 @Override toString()45 public String toString() { 46 return success ? "true" : error != null ? error.getMessage() : "???"; 47 } 48 } 49 50 private final ResolveSession m_session; 51 // Maps a capability to requirements that match it. 52 private final OpenHashMapSet<Capability, Requirement> m_dependentMap; 53 // Maps a requirement to the capability it matches. 54 private final OpenHashMapList m_candidateMap; 55 // Maps a bundle revision to its associated wrapped revision; this only happens 56 // when a revision being resolved has fragments to attach to it. 57 private final Map<Resource, WrappedResource> m_allWrappedHosts; 58 // Map used when populating candidates to hold intermediate and final results. 59 private final OpenHashMap<Resource, PopulateResult> m_populateResultCache; 60 61 private final Map<Capability, Requirement> m_subtitutableMap; 62 63 private final OpenHashMapSet<Requirement, Capability> m_delta; 64 private final AtomicBoolean m_candidateSelectorsUnmodifiable; 65 66 /** 67 * Private copy constructor used by the copy() method. 68 */ Candidates( ResolveSession session, AtomicBoolean candidateSelectorsUnmodifiable, OpenHashMapSet<Capability, Requirement> dependentMap, OpenHashMapList candidateMap, Map<Resource, WrappedResource> wrappedHosts, OpenHashMap<Resource, PopulateResult> populateResultCache, Map<Capability, Requirement> substitutableMap, OpenHashMapSet<Requirement, Capability> delta)69 private Candidates( 70 ResolveSession session, 71 AtomicBoolean candidateSelectorsUnmodifiable, 72 OpenHashMapSet<Capability, Requirement> dependentMap, 73 OpenHashMapList candidateMap, 74 Map<Resource, WrappedResource> wrappedHosts, 75 OpenHashMap<Resource, PopulateResult> populateResultCache, 76 Map<Capability, Requirement> substitutableMap, 77 OpenHashMapSet<Requirement, Capability> delta) 78 { 79 m_session = session; 80 m_candidateSelectorsUnmodifiable = candidateSelectorsUnmodifiable; 81 m_dependentMap = dependentMap; 82 m_candidateMap = candidateMap; 83 m_allWrappedHosts = wrappedHosts; 84 m_populateResultCache = populateResultCache; 85 m_subtitutableMap = substitutableMap; 86 m_delta = delta; 87 } 88 89 /** 90 * Constructs an empty Candidates object. 91 */ Candidates(ResolveSession session)92 public Candidates(ResolveSession session) 93 { 94 m_session = session; 95 m_candidateSelectorsUnmodifiable = new AtomicBoolean(false); 96 m_dependentMap = new OpenHashMapSet<Capability, Requirement>(); 97 m_candidateMap = new OpenHashMapList(); 98 m_allWrappedHosts = new HashMap<Resource, WrappedResource>(); 99 m_populateResultCache = new OpenHashMap<Resource, PopulateResult>(); 100 m_subtitutableMap = new OpenHashMap<Capability, Requirement>(); 101 m_delta = new OpenHashMapSet<Requirement, Capability>(3); 102 } 103 getNbResources()104 public int getNbResources() 105 { 106 return m_populateResultCache.size(); 107 } 108 getRootHosts()109 public Map<Resource, Resource> getRootHosts() 110 { 111 Map<Resource, Resource> hosts = new LinkedHashMap<Resource, Resource>(); 112 for (Resource res : m_session.getMandatoryResources()) 113 { 114 addHost(res, hosts); 115 } 116 117 for (Resource res : m_session.getOptionalResources()) 118 { 119 if (isPopulated(res)) { 120 addHost(res, hosts); 121 } 122 } 123 124 return hosts; 125 } 126 addHost(Resource res, Map<Resource, Resource> hosts)127 private void addHost(Resource res, Map<Resource, Resource> hosts) { 128 if (res instanceof WrappedResource) 129 { 130 res = ((WrappedResource) res).getDeclaredResource(); 131 } 132 if (!Util.isFragment(res)) 133 { 134 hosts.put(res, getWrappedHost(res)); 135 } else { 136 Requirement hostReq = res.getRequirements(HostNamespace.HOST_NAMESPACE).get(0); 137 Capability hostCap = getFirstCandidate(hostReq); 138 // If the resource is an already resolved fragment and can not 139 // be attached to new hosts, there will be no matching host, 140 // so ignore this resource 141 if (hostCap != null) { 142 res = getWrappedHost(hostCap.getResource()); 143 if (res instanceof WrappedResource) { 144 hosts.put(((WrappedResource) res).getDeclaredResource(), res); 145 } 146 } 147 } 148 } 149 150 /** 151 * Returns the delta which is the differences in the candidates from the 152 * original Candidates permutation. 153 * @return the delta 154 */ getDelta()155 public Object getDelta() 156 { 157 return m_delta; 158 } 159 populate(Collection<Resource> resources)160 public void populate(Collection<Resource> resources) 161 { 162 ResolveContext rc = m_session.getContext(); 163 Set<Resource> toRemove = new HashSet<Resource>(); 164 LinkedList<Resource> toPopulate = new LinkedList<Resource>(resources); 165 while (!toPopulate.isEmpty()) 166 { 167 Resource resource = toPopulate.getFirst(); 168 // Get cached result 169 PopulateResult result = m_populateResultCache.get(resource); 170 if (result == null) 171 { 172 result = new PopulateResult(); 173 result.candidates = new OpenHashMap<Requirement, List<Capability>>(); 174 result.remaining = new ArrayList<Requirement>(resource.getRequirements(null)); 175 m_populateResultCache.put(resource, result); 176 } 177 if (result.success || result.error != null) 178 { 179 toPopulate.removeFirst(); 180 continue; 181 } 182 if (result.remaining.isEmpty()) 183 { 184 toPopulate.removeFirst(); 185 result.success = true; 186 addCandidates(result.candidates); 187 result.candidates = null; 188 result.remaining = null; 189 Collection<Resource> relatedResources = rc.findRelatedResources(resource); 190 m_session.setRelatedResources(resource, relatedResources); 191 for (Resource relatedResource : relatedResources) 192 { 193 if (m_session.isValidRelatedResource(relatedResource)) 194 { 195 // This resource is a valid related resource; 196 // populate it now, consider it optional 197 toPopulate.addFirst(relatedResource); 198 } 199 } 200 continue; 201 } 202 // We have a requirement to process 203 Requirement requirement = result.remaining.remove(0); 204 if (!isEffective(requirement)) 205 { 206 continue; 207 } 208 List<Capability> candidates = rc.findProviders(requirement); 209 LinkedList<Resource> newToPopulate = new LinkedList<Resource>(); 210 ResolutionError thrown = processCandidates(newToPopulate, requirement, candidates); 211 if (candidates.isEmpty() && !Util.isOptional(requirement)) 212 { 213 if (Util.isFragment(resource) && rc.getWirings().containsKey(resource)) 214 { 215 // This is a fragment that is already resolved and there is no unresolved hosts to attach it to. 216 result.success = true; 217 } 218 else 219 { 220 result.error = new MissingRequirementError(requirement, thrown); 221 toRemove.add(resource); 222 } 223 toPopulate.removeFirst(); 224 } 225 else 226 { 227 if (!candidates.isEmpty()) 228 { 229 result.candidates.put(requirement, candidates); 230 } 231 if (!newToPopulate.isEmpty()) 232 { 233 toPopulate.addAll(0, newToPopulate); 234 } 235 } 236 } 237 238 while (!toRemove.isEmpty()) 239 { 240 Iterator<Resource> iterator = toRemove.iterator(); 241 Resource resource = iterator.next(); 242 iterator.remove(); 243 remove(resource, toRemove); 244 } 245 } 246 isEffective(Requirement req)247 private boolean isEffective(Requirement req) { 248 if (!m_session.getContext().isEffective(req)) { 249 return false; 250 } 251 String res = req.getDirectives().get(PackageNamespace.REQUIREMENT_RESOLUTION_DIRECTIVE); 252 return !PackageNamespace.RESOLUTION_DYNAMIC.equals(res); 253 } 254 populateSubstitutables()255 private void populateSubstitutables() 256 { 257 for (Map.Entry<Resource, PopulateResult> populated : m_populateResultCache.fast()) 258 { 259 if (populated.getValue().success) 260 { 261 populateSubstitutables(populated.getKey()); 262 } 263 } 264 } 265 populateSubstitutables(Resource resource)266 private void populateSubstitutables(Resource resource) 267 { 268 // Collect the package names exported 269 @SuppressWarnings("serial") 270 OpenHashMap<String, List<Capability>> exportNames = new OpenHashMap<String, List<Capability>>() { 271 @Override 272 protected List<Capability> compute(String s) { 273 return new ArrayList<Capability>(1); 274 } 275 }; 276 for (Capability packageExport : resource.getCapabilities(null)) 277 { 278 if (!PackageNamespace.PACKAGE_NAMESPACE.equals(packageExport.getNamespace())) 279 { 280 continue; 281 } 282 String packageName = (String) packageExport.getAttributes().get(PackageNamespace.PACKAGE_NAMESPACE); 283 List<Capability> caps = exportNames.getOrCompute(packageName); 284 caps.add(packageExport); 285 } 286 if (exportNames.isEmpty()) 287 { 288 return; 289 } 290 // Check if any requirements substitute one of the exported packages 291 for (Requirement req : resource.getRequirements(null)) 292 { 293 if (!PackageNamespace.PACKAGE_NAMESPACE.equals(req.getNamespace())) 294 { 295 continue; 296 } 297 CandidateSelector substitutes = m_candidateMap.get(req); 298 if (substitutes != null && !substitutes.isEmpty()) 299 { 300 String packageName = (String) substitutes.getCurrentCandidate().getAttributes().get(PackageNamespace.PACKAGE_NAMESPACE); 301 List<Capability> exportedPackages = exportNames.get(packageName); 302 if (exportedPackages != null) 303 { 304 // The package is exported; 305 // Check if the requirement only has the bundle's own export as candidates 306 if (!exportedPackages.containsAll(substitutes.getRemainingCandidates())) 307 { 308 for (Capability exportedPackage : exportedPackages) 309 { 310 m_subtitutableMap.put(exportedPackage, req); 311 } 312 } 313 } 314 } 315 } 316 } 317 318 private static final int UNPROCESSED = 0; 319 private static final int PROCESSING = 1; 320 private static final int SUBSTITUTED = 2; 321 private static final int EXPORTED = 3; 322 checkSubstitutes()323 ResolutionError checkSubstitutes() 324 { 325 OpenHashMap<Capability, Integer> substituteStatuses = new OpenHashMap<Capability, Integer>(m_subtitutableMap.size()); 326 for (Capability substitutable : m_subtitutableMap.keySet()) 327 { 328 // initialize with unprocessed 329 substituteStatuses.put(substitutable, UNPROCESSED); 330 } 331 // note we are iterating over the original unmodified map by design 332 for (Capability substitutable : m_subtitutableMap.keySet()) 333 { 334 isSubstituted(substitutable, substituteStatuses); 335 } 336 337 // Remove any substituted exports from candidates 338 for (Map.Entry<Capability, Integer> substituteStatus : substituteStatuses.fast()) 339 { 340 // add a permutation that imports a different candidate for the substituted if possible 341 Requirement substitutedReq = m_subtitutableMap.get(substituteStatus.getKey()); 342 if (substitutedReq != null) 343 { 344 m_session.permutateIfNeeded(PermutationType.SUBSTITUTE, substitutedReq, this); 345 } 346 Set<Requirement> dependents = m_dependentMap.get(substituteStatus.getKey()); 347 if (dependents != null) 348 { 349 for (Requirement dependent : dependents) 350 { 351 CandidateSelector candidates = m_candidateMap.get(dependent); 352 if (candidates != null) 353 { 354 candidates: 355 while (!candidates.isEmpty()) 356 { 357 Capability candidate = candidates.getCurrentCandidate(); 358 Integer candidateStatus = substituteStatuses.get(candidate); 359 if (candidateStatus == null) 360 { 361 candidateStatus = EXPORTED; 362 } 363 switch (candidateStatus) 364 { 365 case EXPORTED: 366 // non-substituted candidate hit before the substituted one; do not continue 367 break candidates; 368 case SUBSTITUTED: 369 default: 370 // Need to remove any substituted that comes before an exported candidate 371 candidates.removeCurrentCandidate(); 372 // continue to next candidate 373 break; 374 } 375 } 376 if (candidates.isEmpty()) 377 { 378 if (Util.isOptional(dependent)) 379 { 380 m_candidateMap.remove(dependent); 381 } 382 else 383 { 384 return new MissingRequirementError(dependent); 385 } 386 } 387 } 388 } 389 } 390 } 391 return null; 392 } 393 isSubstituted(Capability substitutableCap, Map<Capability, Integer> substituteStatuses)394 private boolean isSubstituted(Capability substitutableCap, Map<Capability, Integer> substituteStatuses) 395 { 396 Integer substituteState = substituteStatuses.get(substitutableCap); 397 if (substituteState == null) 398 { 399 return false; 400 } 401 402 switch (substituteState) 403 { 404 case PROCESSING: 405 // found a cycle mark the initiator as not substituted 406 substituteStatuses.put(substitutableCap, EXPORTED); 407 return false; 408 case SUBSTITUTED: 409 return true; 410 case EXPORTED: 411 return false; 412 default: 413 break; 414 } 415 416 Requirement substitutableReq = m_subtitutableMap.get(substitutableCap); 417 if (substitutableReq == null) 418 { 419 // this should never happen. 420 return false; 421 } 422 // mark as processing to detect cycles 423 substituteStatuses.put(substitutableCap, PROCESSING); 424 // discover possible substitutes 425 CandidateSelector substitutes = m_candidateMap.get(substitutableReq); 426 if (substitutes != null) 427 { 428 for (Capability substituteCandidate : substitutes.getRemainingCandidates()) 429 { 430 if (substituteCandidate.getResource().equals(substitutableCap.getResource())) 431 { 432 substituteStatuses.put(substitutableCap, EXPORTED); 433 return false; 434 } 435 if (!isSubstituted(substituteCandidate, substituteStatuses)) 436 { 437 // The resource's exported package is substituted for this permutation. 438 substituteStatuses.put(substitutableCap, SUBSTITUTED); 439 return true; 440 } 441 } 442 } 443 // if we get here then the export is not substituted 444 substituteStatuses.put(substitutableCap, EXPORTED); 445 return false; 446 } 447 populateDynamic()448 public ResolutionError populateDynamic() 449 { 450 451 // Process the candidates, removing any candidates that 452 // cannot resolve. 453 // TODO: verify the two following statements 454 LinkedList<Resource> toPopulate = new LinkedList<Resource>(); 455 ResolutionError rethrow = processCandidates(toPopulate, m_session.getDynamicRequirement(), m_session.getDynamicCandidates()); 456 457 // Add the dynamic imports candidates. 458 // Make sure this is done after the call to processCandidates since we want to ensure 459 // fragment candidates are properly hosted before adding the candidates list which makes a copy 460 addCandidates(m_session.getDynamicRequirement(), m_session.getDynamicCandidates()); 461 462 populate(toPopulate); 463 464 CandidateSelector caps = m_candidateMap.get(m_session.getDynamicRequirement()); 465 if (caps != null) 466 { 467 m_session.getDynamicCandidates().retainAll(caps.getRemainingCandidates()); 468 } 469 else 470 { 471 m_session.getDynamicCandidates().clear(); 472 } 473 474 if (m_session.getDynamicCandidates().isEmpty()) 475 { 476 if (rethrow == null) 477 { 478 rethrow = new DynamicImportFailed(m_session.getDynamicRequirement()); 479 } 480 return rethrow; 481 } 482 483 PopulateResult result = new PopulateResult(); 484 result.success = true; 485 m_populateResultCache.put(m_session.getDynamicHost(), result); 486 return null; 487 } 488 processCandidates( LinkedList<Resource> toPopulate, Requirement req, List<Capability> candidates)489 private ResolutionError processCandidates( 490 LinkedList<Resource> toPopulate, 491 Requirement req, 492 List<Capability> candidates) 493 { 494 ResolveContext rc = m_session.getContext(); 495 // Get satisfying candidates and populate their candidates if necessary. 496 ResolutionError rethrow = null; 497 Set<Capability> fragmentCands = null; 498 for (Iterator<Capability> itCandCap = candidates.iterator(); 499 itCandCap.hasNext();) 500 { 501 Capability candCap = itCandCap.next(); 502 503 boolean isFragment = Util.isFragment(candCap.getResource()); 504 505 // If the capability is from a fragment, then record it 506 // because we have to insert associated host capabilities 507 // if the fragment is already attached to any hosts. 508 if (isFragment) 509 { 510 if (fragmentCands == null) 511 { 512 fragmentCands = new HashSet<Capability>(); 513 } 514 fragmentCands.add(candCap); 515 } 516 517 // Do a sanity check incase the resolve context tries to attach 518 // a fragment to an already resolved host capability 519 if (HostNamespace.HOST_NAMESPACE.equals(req.getNamespace())) { 520 if (rc.getWirings().containsKey(candCap.getResource())) { 521 itCandCap.remove(); 522 continue; 523 } 524 } 525 // If the candidate revision is a fragment, then always attempt 526 // to populate candidates for its dependency, since it must be 527 // attached to a host to be used. Otherwise, if the candidate 528 // revision is not already resolved and is not the current version 529 // we are trying to populate, then populate the candidates for 530 // its dependencies as well. 531 // NOTE: Technically, we don't have to check to see if the 532 // candidate revision is equal to the current revision, but this 533 // saves us from recursing and also simplifies exceptions messages 534 // since we effectively chain exception messages for each level 535 // of recursion; thus, any avoided recursion results in fewer 536 // exceptions to chain when an error does occur. 537 if ((isFragment || !rc.getWirings().containsKey(candCap.getResource())) 538 && !candCap.getResource().equals(req.getResource())) 539 { 540 PopulateResult result = m_populateResultCache.get(candCap.getResource()); 541 if (result != null) 542 { 543 if (result.error != null) 544 { 545 if (rethrow == null) 546 { 547 rethrow = result.error; 548 } 549 // Remove the candidate since we weren't able to 550 // populate its candidates. 551 itCandCap.remove(); 552 } 553 else if (!result.success) 554 { 555 toPopulate.add(candCap.getResource()); 556 } 557 } 558 else 559 { 560 toPopulate.add(candCap.getResource()); 561 } 562 } 563 } 564 565 // If any of the candidates for the requirement were from a fragment, 566 // then also insert synthesized hosted capabilities for any other host 567 // to which the fragment is attached since they are all effectively 568 // unique capabilities. 569 if (fragmentCands != null) 570 { 571 for (Capability fragCand : fragmentCands) 572 { 573 String fragCandName = fragCand.getNamespace(); 574 if (IdentityNamespace.IDENTITY_NAMESPACE.equals(fragCandName)) 575 { 576 // no need to wrap identity namespace ever 577 continue; 578 } 579 // Only necessary for resolved fragments. 580 Wiring wiring = rc.getWirings().get(fragCand.getResource()); 581 if (wiring != null) 582 { 583 // Fragments only have host wire, so each wire represents 584 // an attached host. 585 for (Wire wire : wiring.getRequiredResourceWires(HostNamespace.HOST_NAMESPACE)) 586 { 587 // If the capability is a package, then make sure the 588 // host actually provides it in its resolved capabilities, 589 // since it may be a substitutable export. 590 if (!fragCandName.equals(PackageNamespace.PACKAGE_NAMESPACE) 591 || rc.getWirings().get(wire.getProvider()) 592 .getResourceCapabilities(null).contains(fragCand)) 593 { 594 // Note that we can just add this as a candidate 595 // directly, since we know it is already resolved. 596 // NOTE: We are synthesizing a hosted capability here, 597 // but we are not using a ShadowList like we do when 598 // we synthesizing capabilities for unresolved hosts. 599 // It is not necessary to use the ShadowList here since 600 // the host is resolved, because in that case we can 601 // calculate the proper package space by traversing 602 // the wiring. In the unresolved case, this isn't possible 603 // so we need to use the ShadowList so we can keep 604 // a reference to a synthesized resource with attached 605 // fragments so we can correctly calculate its package 606 // space. 607 // Must remove the fragment candidate because we must 608 // only use hosted capabilities for package namespace 609 candidates.remove(fragCand); 610 rc.insertHostedCapability( 611 candidates, 612 new WrappedCapability( 613 wire.getCapability().getResource(), 614 fragCand)); 615 } 616 } 617 } 618 } 619 } 620 621 return rethrow; 622 } 623 isPopulated(Resource resource)624 public boolean isPopulated(Resource resource) 625 { 626 PopulateResult value = m_populateResultCache.get(resource); 627 return (value != null && value.success); 628 } 629 getResolutionError(Resource resource)630 public ResolutionError getResolutionError(Resource resource) 631 { 632 PopulateResult value = m_populateResultCache.get(resource); 633 return value != null ? value.error : null; 634 } 635 636 /** 637 * Adds a requirement and its matching candidates to the internal data 638 * structure. This method assumes it owns the data being passed in and does 639 * not make a copy. It takes the data and processes, such as calculating 640 * which requirements depend on which capabilities and recording any 641 * fragments it finds for future merging. 642 * 643 * @param req the requirement to add. 644 * @param candidates the candidates matching the requirement. 645 */ addCandidates(Requirement req, List<Capability> candidates)646 private void addCandidates(Requirement req, List<Capability> candidates) 647 { 648 // Record the candidates. 649 m_candidateMap.put(req, new CandidateSelector(candidates, m_candidateSelectorsUnmodifiable)); 650 for (Capability cap : candidates) 651 { 652 m_dependentMap.getOrCompute(cap).add(req); 653 } 654 } 655 656 /** 657 * Adds requirements and candidates in bulk. The outer map is not retained 658 * by this method, but the inner data structures are, so they should not be 659 * further modified by the caller. 660 * 661 * @param candidates the bulk requirements and candidates to add. 662 */ addCandidates(Map<Requirement, List<Capability>> candidates)663 private void addCandidates(Map<Requirement, List<Capability>> candidates) 664 { 665 for (Map.Entry<Requirement, List<Capability>> entry : candidates.entrySet()) 666 { 667 addCandidates(entry.getKey(), entry.getValue()); 668 } 669 } 670 671 /** 672 * Returns the wrapped resource associated with the given resource. If the 673 * resource was not wrapped, then the resource itself is returned. This is 674 * really only needed to determine if the root resources of the resolve have 675 * been wrapped. 676 * 677 * @param r the resource whose wrapper is desired. 678 * @return the wrapper resource or the resource itself if it was not 679 * wrapped. 680 */ getWrappedHost(Resource r)681 public Resource getWrappedHost(Resource r) 682 { 683 Resource wrapped = m_allWrappedHosts.get(r); 684 return (wrapped == null) ? r : wrapped; 685 } 686 687 /** 688 * Gets the candidates associated with a given requirement. 689 * 690 * @param req the requirement whose candidates are desired. 691 * @return the matching candidates or null. 692 */ getCandidates(Requirement req)693 public List<Capability> getCandidates(Requirement req) 694 { 695 CandidateSelector candidates = m_candidateMap.get(req); 696 if (candidates != null) 697 { 698 return candidates.getRemainingCandidates(); 699 } 700 return null; 701 } 702 getFirstCandidate(Requirement req)703 public Capability getFirstCandidate(Requirement req) 704 { 705 CandidateSelector candidates = m_candidateMap.get(req); 706 if (candidates != null && !candidates.isEmpty()) 707 { 708 return candidates.getCurrentCandidate(); 709 } 710 return null; 711 } 712 removeFirstCandidate(Requirement req)713 public void removeFirstCandidate(Requirement req) 714 { 715 CandidateSelector candidates = m_candidateMap.get(req); 716 // Remove the conflicting candidate. 717 Capability cap = candidates.removeCurrentCandidate(); 718 if (candidates.isEmpty()) 719 { 720 m_candidateMap.remove(req); 721 } 722 // Update the delta with the removed capability 723 CopyOnWriteSet<Capability> capPath = m_delta.getOrCompute(req); 724 capPath.add(cap); 725 } 726 clearMultipleCardinalityCandidates(Requirement req, Collection<Capability> caps)727 public CandidateSelector clearMultipleCardinalityCandidates(Requirement req, Collection<Capability> caps) 728 { 729 // this is a special case where we need to completely replace the CandidateSelector 730 // this method should never be called from normal Candidates permutations 731 CandidateSelector candidates = m_candidateMap.get(req); 732 List<Capability> remaining = new ArrayList<Capability>(candidates.getRemainingCandidates()); 733 remaining.removeAll(caps); 734 candidates = new CandidateSelector(remaining, m_candidateSelectorsUnmodifiable); 735 m_candidateMap.put(req, candidates); 736 return candidates; 737 } 738 739 /** 740 * Merges fragments into their hosts. It does this by wrapping all host 741 * modules and attaching their selected fragments, removing all unselected 742 * fragment modules, and replacing all occurrences of the original fragments 743 * in the internal data structures with the wrapped host modules instead. 744 * Thus, fragment capabilities and requirements are merged into the 745 * appropriate host and the candidates for the fragment now become 746 * candidates for the host. Likewise, any module depending on a fragment now 747 * depend on the host. Note that this process is sort of like 748 * multiplication, since one fragment that can attach to two hosts 749 * effectively gets multiplied across the two hosts. So, any modules being 750 * satisfied by the fragment will end up having the two hosts as potential 751 * candidates, rather than the single fragment. 752 * 753 * @return ResolutionError if the removal of any unselected fragments 754 * result in the root module being unable to resolve. 755 */ prepare()756 public ResolutionError prepare() 757 { 758 // Maps a host capability to a map containing its potential fragments; 759 // the fragment map maps a fragment symbolic name to a map that maps 760 // a version to a list of fragments requirements matching that symbolic 761 // name and version. 762 Map<Capability, Map<String, Map<Version, List<Requirement>>>> hostFragments = 763 getHostFragments(); 764 765 // This method performs the following steps: 766 // 1. Select the fragments to attach to a given host. 767 // 2. Wrap hosts and attach fragments. 768 // 3. Remove any unselected fragments. This is necessary because 769 // other revisions may depend on the capabilities of unselected 770 // fragments, so we need to remove the unselected fragments and 771 // any revisions that depends on them, which could ultimately cause 772 // the entire resolve to fail. 773 // 4. Replace all fragments with any host it was merged into 774 // (effectively multiplying it). 775 // * This includes setting candidates for attached fragment 776 // requirements as well as replacing fragment capabilities 777 // with host's attached fragment capabilities. 778 // Steps 1 and 2 779 List<WrappedResource> hostResources = new ArrayList<WrappedResource>(); 780 List<Resource> unselectedFragments = new ArrayList<Resource>(); 781 for (Entry<Capability, Map<String, Map<Version, List<Requirement>>>> hostEntry : hostFragments.entrySet()) 782 { 783 // Step 1 784 Capability hostCap = hostEntry.getKey(); 785 Map<String, Map<Version, List<Requirement>>> fragments = 786 hostEntry.getValue(); 787 List<Resource> selectedFragments = new ArrayList<Resource>(); 788 for (Entry<String, Map<Version, List<Requirement>>> fragEntry 789 : fragments.entrySet()) 790 { 791 boolean isFirst = true; 792 for (Entry<Version, List<Requirement>> versionEntry 793 : fragEntry.getValue().entrySet()) 794 { 795 for (Requirement hostReq : versionEntry.getValue()) 796 { 797 // Selecting the first fragment in each entry, which 798 // is equivalent to selecting the highest version of 799 // each fragment with a given symbolic name. 800 if (isFirst) 801 { 802 selectedFragments.add(hostReq.getResource()); 803 isFirst = false; 804 } 805 // For any fragment that wasn't selected, remove the 806 // current host as a potential host for it and remove it 807 // as a dependent on the host. If there are no more 808 // potential hosts for the fragment, then mark it as 809 // unselected for later removal. 810 else 811 { 812 m_dependentMap.get(hostCap).remove(hostReq); 813 CandidateSelector hosts = removeCandidate(hostReq, hostCap); 814 if (hosts.isEmpty()) 815 { 816 unselectedFragments.add(hostReq.getResource()); 817 } 818 } 819 } 820 } 821 } 822 823 // Step 2 824 WrappedResource wrappedHost = 825 new WrappedResource(hostCap.getResource(), selectedFragments); 826 hostResources.add(wrappedHost); 827 m_allWrappedHosts.put(hostCap.getResource(), wrappedHost); 828 } 829 830 // Step 3 831 for (Resource fragment : unselectedFragments) 832 { 833 removeResource(fragment, new FragmentNotSelectedError(fragment)); 834 } 835 836 // Step 4 837 // First copy candidates for wrapped requirements to the host. 838 for (WrappedResource hostResource : hostResources) { 839 for (Requirement r : hostResource.getRequirements(null)) 840 { 841 Requirement origReq = ((WrappedRequirement) r).getDeclaredRequirement(); 842 CandidateSelector cands = m_candidateMap.get(origReq); 843 if (cands != null) 844 { 845 if (cands instanceof ShadowList) 846 { 847 m_candidateMap.put(r, ShadowList.deepCopy((ShadowList) cands)); 848 } else { 849 m_candidateMap.put(r, cands.copy()); 850 } 851 for (Capability cand : cands.getRemainingCandidates()) 852 { 853 Set<Requirement> dependents = m_dependentMap.get(cand); 854 dependents.remove(origReq); 855 dependents.add(r); 856 } 857 } 858 } 859 } 860 861 for (WrappedResource hostResource : hostResources) 862 { 863 // Replaces capabilities from fragments with the capabilities 864 // from the merged host. 865 for (Capability c : hostResource.getCapabilities(null)) 866 { 867 // Don't replace the host capability, since the fragment will 868 // really be attached to the original host, not the wrapper. 869 if (!c.getNamespace().equals(HostNamespace.HOST_NAMESPACE)) 870 { 871 Capability origCap = ((HostedCapability) c).getDeclaredCapability(); 872 // Note that you might think we could remove the original cap 873 // from the dependent map, but you can't since it may come from 874 // a fragment that is attached to multiple hosts, so each host 875 // will need to make their own copy. 876 CopyOnWriteSet<Requirement> dependents = m_dependentMap.get(origCap); 877 if (dependents != null) 878 { 879 dependents = new CopyOnWriteSet<Requirement>(dependents); 880 m_dependentMap.put(c, dependents); 881 for (Requirement r : dependents) 882 { 883 // We have synthesized hosted capabilities for all 884 // fragments that have been attached to hosts by 885 // wrapping the host bundle and their attached 886 // fragments. We need to use the ResolveContext to 887 // determine the proper priority order for hosted 888 // capabilities since the order may depend on the 889 // declaring host/fragment combination. However, 890 // internally we completely wrap the host revision 891 // and make all capabilities/requirements point back 892 // to the wrapped host not the declaring host. The 893 // ResolveContext expects HostedCapabilities to point 894 // to the declaring revision, so we need two separate 895 // candidate lists: one for the ResolveContext with 896 // HostedCapabilities pointing back to the declaring 897 // host and one for the resolver with HostedCapabilities 898 // pointing back to the wrapped host. We ask the 899 // ResolveContext to insert its appropriate HostedCapability 900 // into its list, then we mirror the insert into a 901 // shadow list with the resolver's HostedCapability. 902 // We only need to ask the ResolveContext to find 903 // the insert position for fragment caps since these 904 // were synthesized and we don't know their priority. 905 // However, in the resolver's candidate list we need 906 // to replace all caps with the wrapped caps, no 907 // matter if they come from the host or fragment, 908 // since we are completing replacing the declaring 909 // host and fragments with the wrapped host. 910 CandidateSelector cands = m_candidateMap.get(r); 911 ShadowList shadow; 912 if (!(cands instanceof ShadowList)) 913 { 914 shadow = ShadowList.createShadowList(cands); 915 m_candidateMap.put(r, shadow); 916 cands = shadow; 917 } 918 else 919 { 920 shadow = (ShadowList) cands; 921 } 922 923 // If the original capability is from a fragment, then 924 // ask the ResolveContext to insert it and update the 925 // shadow copy of the list accordingly. 926 if (!origCap.getResource().equals(hostResource.getDeclaredResource())) 927 { 928 shadow.insertHostedCapability( 929 m_session.getContext(), 930 (HostedCapability) c, 931 new SimpleHostedCapability( 932 hostResource.getDeclaredResource(), 933 origCap)); 934 } 935 // If the original capability is from the host, then 936 // we just need to replace it in the shadow list. 937 else 938 { 939 shadow.replace(origCap, c); 940 } 941 } 942 } 943 } 944 } 945 } 946 947 // Lastly, verify that all mandatory revisions are still 948 // populated, since some might have become unresolved after 949 // selecting fragments/singletons. 950 for (Resource resource : m_session.getMandatoryResources()) 951 { 952 if (!isPopulated(resource)) 953 { 954 return getResolutionError(resource); 955 } 956 } 957 958 populateSubstitutables(); 959 960 m_candidateMap.trim(); 961 m_dependentMap.trim(); 962 963 // mark the selectors as unmodifiable now 964 m_candidateSelectorsUnmodifiable.set(true); 965 return null; 966 } 967 968 // Maps a host capability to a map containing its potential fragments; 969 // the fragment map maps a fragment symbolic name to a map that maps 970 // a version to a list of fragments requirements matching that symbolic 971 // name and version. getHostFragments()972 private Map<Capability, Map<String, Map<Version, List<Requirement>>>> getHostFragments() 973 { 974 Map<Capability, Map<String, Map<Version, List<Requirement>>>> hostFragments = 975 new HashMap<Capability, Map<String, Map<Version, List<Requirement>>>>(); 976 for (Entry<Requirement, CandidateSelector> entry : m_candidateMap.fast()) 977 { 978 Requirement req = entry.getKey(); 979 CandidateSelector caps = entry.getValue(); 980 for (Capability cap : caps.getRemainingCandidates()) 981 { 982 // Keep track of hosts and associated fragments. 983 if (req.getNamespace().equals(HostNamespace.HOST_NAMESPACE)) 984 { 985 String resSymName = Util.getSymbolicName(req.getResource()); 986 Version resVersion = Util.getVersion(req.getResource()); 987 988 Map<String, Map<Version, List<Requirement>>> fragments = hostFragments.get(cap); 989 if (fragments == null) 990 { 991 fragments = new HashMap<String, Map<Version, List<Requirement>>>(); 992 hostFragments.put(cap, fragments); 993 } 994 Map<Version, List<Requirement>> fragmentVersions = fragments.get(resSymName); 995 if (fragmentVersions == null) 996 { 997 fragmentVersions = 998 new TreeMap<Version, List<Requirement>>(Collections.reverseOrder()); 999 fragments.put(resSymName, fragmentVersions); 1000 } 1001 List<Requirement> actual = fragmentVersions.get(resVersion); 1002 if (actual == null) 1003 { 1004 actual = new ArrayList<Requirement>(); 1005 if (resVersion == null) 1006 resVersion = new Version(0, 0, 0); 1007 fragmentVersions.put(resVersion, actual); 1008 } 1009 actual.add(req); 1010 } 1011 } 1012 } 1013 1014 return hostFragments; 1015 } 1016 1017 /** 1018 * Removes a module from the internal data structures if it wasn't selected 1019 * as a fragment or a singleton. This process may cause other modules to 1020 * become unresolved if they depended on the module's capabilities and there 1021 * is no other candidate. 1022 * 1023 * @param resource the module to remove. 1024 * @param ex the resolution error 1025 */ removeResource(Resource resource, ResolutionError ex)1026 private void removeResource(Resource resource, ResolutionError ex) 1027 { 1028 // Add removal reason to result cache. 1029 PopulateResult result = m_populateResultCache.get(resource); 1030 result.success = false; 1031 result.error = ex; 1032 // Remove from dependents. 1033 Set<Resource> unresolvedResources = new HashSet<Resource>(); 1034 remove(resource, unresolvedResources); 1035 // Remove dependents that failed as a result of removing revision. 1036 while (!unresolvedResources.isEmpty()) 1037 { 1038 Iterator<Resource> it = unresolvedResources.iterator(); 1039 resource = it.next(); 1040 it.remove(); 1041 remove(resource, unresolvedResources); 1042 } 1043 } 1044 1045 /** 1046 * Removes the specified module from the internal data structures, which 1047 * involves removing its requirements and its capabilities. This may cause 1048 * other modules to become unresolved as a result. 1049 * 1050 * @param resource the module to remove. 1051 * @param unresolvedResources a list to containing any additional modules 1052 * that that became unresolved as a result of removing this module and will 1053 * also need to be removed. 1054 */ remove(Resource resource, Set<Resource> unresolvedResources)1055 private void remove(Resource resource, Set<Resource> unresolvedResources) 1056 { 1057 for (Requirement r : resource.getRequirements(null)) 1058 { 1059 remove(r); 1060 } 1061 1062 for (Capability c : resource.getCapabilities(null)) 1063 { 1064 remove(c, unresolvedResources); 1065 } 1066 } 1067 1068 /** 1069 * Removes a requirement from the internal data structures. 1070 * 1071 * @param req the requirement to remove. 1072 */ remove(Requirement req)1073 private void remove(Requirement req) 1074 { 1075 CandidateSelector candidates = m_candidateMap.remove(req); 1076 if (candidates != null) 1077 { 1078 for (Capability cap : candidates.getRemainingCandidates()) 1079 { 1080 Set<Requirement> dependents = m_dependentMap.get(cap); 1081 if (dependents != null) 1082 { 1083 dependents.remove(req); 1084 } 1085 } 1086 } 1087 } 1088 1089 /** 1090 * Removes a capability from the internal data structures. This may cause 1091 * other modules to become unresolved as a result. 1092 * 1093 * @param c the capability to remove. 1094 * @param unresolvedResources a list to containing any additional modules 1095 * that that became unresolved as a result of removing this module and will 1096 * also need to be removed. 1097 */ remove(Capability c, Set<Resource> unresolvedResources)1098 private void remove(Capability c, Set<Resource> unresolvedResources) 1099 { 1100 Set<Requirement> dependents = m_dependentMap.remove(c); 1101 if (dependents != null) 1102 { 1103 for (Requirement r : dependents) 1104 { 1105 CandidateSelector candidates = removeCandidate(r, c); 1106 if (candidates.isEmpty()) 1107 { 1108 m_candidateMap.remove(r); 1109 if (!Util.isOptional(r)) 1110 { 1111 PopulateResult result = m_populateResultCache.get(r.getResource()); 1112 if (result != null) 1113 { 1114 result.success = false; 1115 result.error = 1116 new MissingRequirementError(r, m_populateResultCache.get(c.getResource()).error); 1117 } 1118 unresolvedResources.add(r.getResource()); 1119 } 1120 } 1121 } 1122 } 1123 } 1124 removeCandidate(Requirement req, Capability cap)1125 private CandidateSelector removeCandidate(Requirement req, Capability cap) { 1126 CandidateSelector candidates = m_candidateMap.get(req); 1127 candidates.remove(cap); 1128 return candidates; 1129 } 1130 1131 /** 1132 * Creates a copy of the Candidates object. This is used for creating 1133 * permutations when package space conflicts are discovered. 1134 * 1135 * @return copy of this Candidates object. 1136 */ copy()1137 public Candidates copy() 1138 { 1139 return new Candidates( 1140 m_session, 1141 m_candidateSelectorsUnmodifiable, 1142 m_dependentMap, 1143 m_candidateMap.deepClone(), 1144 m_allWrappedHosts, 1145 m_populateResultCache, 1146 m_subtitutableMap, 1147 m_delta.deepClone()); 1148 } 1149 dump(ResolveContext rc)1150 public void dump(ResolveContext rc) 1151 { 1152 // Create set of all revisions from requirements. 1153 Set<Resource> resources = new CopyOnWriteSet<Resource>(); 1154 for (Entry<Requirement, CandidateSelector> entry 1155 : m_candidateMap.entrySet()) 1156 { 1157 resources.add(entry.getKey().getResource()); 1158 } 1159 // Now dump the revisions. 1160 System.out.println("=== BEGIN CANDIDATE MAP ==="); 1161 for (Resource resource : resources) 1162 { 1163 Wiring wiring = rc.getWirings().get(resource); 1164 System.out.println(" " + resource 1165 + " (" + ((wiring != null) ? "RESOLVED)" : "UNRESOLVED)")); 1166 List<Requirement> reqs = (wiring != null) 1167 ? wiring.getResourceRequirements(null) 1168 : resource.getRequirements(null); 1169 for (Requirement req : reqs) 1170 { 1171 CandidateSelector candidates = m_candidateMap.get(req); 1172 if ((candidates != null) && (!candidates.isEmpty())) 1173 { 1174 System.out.println(" " + req + ": " + candidates); 1175 } 1176 } 1177 reqs = (wiring != null) 1178 ? Util.getDynamicRequirements(wiring.getResourceRequirements(null)) 1179 : Util.getDynamicRequirements(resource.getRequirements(null)); 1180 for (Requirement req : reqs) 1181 { 1182 CandidateSelector candidates = m_candidateMap.get(req); 1183 if ((candidates != null) && (!candidates.isEmpty())) 1184 { 1185 System.out.println(" " + req + ": " + candidates); 1186 } 1187 } 1188 } 1189 System.out.println("=== END CANDIDATE MAP ==="); 1190 } 1191 permutate(Requirement req)1192 public Candidates permutate(Requirement req) 1193 { 1194 if (!Util.isMultiple(req) && canRemoveCandidate(req)) 1195 { 1196 Candidates perm = copy(); 1197 perm.removeFirstCandidate(req); 1198 return perm; 1199 } 1200 return null; 1201 } 1202 canRemoveCandidate(Requirement req)1203 public boolean canRemoveCandidate(Requirement req) 1204 { 1205 CandidateSelector candidates = m_candidateMap.get(req); 1206 if (candidates != null) 1207 { 1208 Capability current = candidates.getCurrentCandidate(); 1209 if (current != null) 1210 { 1211 // IMPLEMENTATION NOTE: 1212 // Here we check for a req that is used for a substitutable export. 1213 // If we find a substitutable req then an extra check is done to see 1214 // if the substitutable capability is currently depended on as the 1215 // only provider of some other requirement. If it is then we do not 1216 // allow the candidate to be removed. 1217 // This is done because of the way we attempt to reduce permutations 1218 // checked by permuting all used requirements that conflict with a 1219 // directly imported/required capability in one go. 1220 // If we allowed these types of substitutable requirements to move 1221 // to the next capability then the permutation would be thrown out 1222 // because it would cause some other resource to not resolve. 1223 // That in turn would throw out the complete permutation along with 1224 // any follow on permutations that could have resulted. 1225 // See ResolverImpl::checkPackageSpaceConsistency 1226 1227 // Check if the current candidate is substitutable by the req; 1228 // This check is necessary here because of the way we traverse used blames 1229 // allows multiple requirements to be permuted in one Candidates 1230 if (req.equals(m_subtitutableMap.get(current))) 1231 { 1232 // this is a substitute req, 1233 // make sure there is not an existing dependency that would fail if we substitute 1234 Set<Requirement> dependents = m_dependentMap.get(current); 1235 if (dependents != null) 1236 { 1237 for (Requirement dependent : dependents) 1238 { 1239 CandidateSelector dependentSelector = m_candidateMap.get( 1240 dependent); 1241 // If the dependent selector only has one capability left then check if 1242 // the current candidate is the selector's current candidate. 1243 if (dependentSelector != null 1244 && dependentSelector.getRemainingCandidateCount() <= 1) 1245 { 1246 if (current.equals( 1247 dependentSelector.getCurrentCandidate())) 1248 { 1249 // return false since we do not want to allow this requirement 1250 // to substitute the capability 1251 return false; 1252 } 1253 } 1254 } 1255 } 1256 } 1257 } 1258 return candidates.getRemainingCandidateCount() > 1 || Util.isOptional(req); 1259 } 1260 return false; 1261 } 1262 1263 static class DynamicImportFailed extends ResolutionError { 1264 1265 private final Requirement requirement; 1266 DynamicImportFailed(Requirement requirement)1267 public DynamicImportFailed(Requirement requirement) { 1268 this.requirement = requirement; 1269 } 1270 getMessage()1271 public String getMessage() { 1272 return "Dynamic import failed."; 1273 } 1274 getUnresolvedRequirements()1275 public Collection<Requirement> getUnresolvedRequirements() { 1276 return Collections.singleton(requirement); 1277 } 1278 1279 @Override toException()1280 public ResolutionException toException() { 1281 return new ReasonException(ReasonException.Reason.DynamicImport, getMessage(), null, getUnresolvedRequirements()); 1282 } 1283 1284 } 1285 1286 static class FragmentNotSelectedError extends ResolutionError { 1287 1288 private final Resource resource; 1289 FragmentNotSelectedError(Resource resource)1290 public FragmentNotSelectedError(Resource resource) { 1291 this.resource = resource; 1292 } 1293 getMessage()1294 public String getMessage() { 1295 return "Fragment was not selected for attachment: " + resource; 1296 } 1297 1298 @Override getUnresolvedRequirements()1299 public Collection<Requirement> getUnresolvedRequirements() { 1300 return resource.getRequirements(HostNamespace.HOST_NAMESPACE); 1301 } 1302 1303 @Override toException()1304 public ResolutionException toException() { 1305 return new ReasonException(ReasonException.Reason.FragmentNotSelected, getMessage(), null, getUnresolvedRequirements()); 1306 } 1307 1308 } 1309 1310 static class MissingRequirementError extends ResolutionError { 1311 1312 private final Requirement requirement; 1313 private final ResolutionError cause; 1314 MissingRequirementError(Requirement requirement)1315 public MissingRequirementError(Requirement requirement) { 1316 this(requirement, null); 1317 } 1318 MissingRequirementError(Requirement requirement, ResolutionError cause)1319 public MissingRequirementError(Requirement requirement, ResolutionError cause) { 1320 this.requirement = requirement; 1321 this.cause = cause; 1322 } 1323 getMessage()1324 public String getMessage() { 1325 String msg = "Unable to resolve " + requirement.getResource() 1326 + ": missing requirement " + requirement; 1327 if (cause != null) 1328 { 1329 msg = msg + " [caused by: " + cause.getMessage() + "]"; 1330 } 1331 return msg; 1332 } 1333 getUnresolvedRequirements()1334 public Collection<Requirement> getUnresolvedRequirements() { 1335 return Collections.singleton(requirement); 1336 } 1337 1338 @Override toException()1339 public ResolutionException toException() { 1340 return new ReasonException( 1341 ReasonException.Reason.MissingRequirement, getMessage(), cause != null ? cause.toException() : null, getUnresolvedRequirements()); 1342 } 1343 1344 } 1345 1346 } 1347