diff options
| -rwxr-xr-x | bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/Candidates.java | 208 | ||||
| -rwxr-xr-x | bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/ResolverImpl.java | 849 |
2 files changed, 474 insertions, 583 deletions
diff --git a/bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/Candidates.java b/bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/Candidates.java index bfa80c6ec..9dcf5a89e 100755 --- a/bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/Candidates.java +++ b/bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/Candidates.java @@ -18,34 +18,14 @@ */ package org.apache.felix.resolver; -import java.util.ArrayList; -import java.util.Collection; -import java.util.Collections; -import java.util.HashMap; -import java.util.HashSet; -import java.util.Iterator; -import java.util.LinkedList; -import java.util.List; -import java.util.Map; +import java.util.*; import java.util.Map.Entry; -import java.util.Set; -import java.util.TreeMap; - -import org.apache.felix.resolver.util.CopyOnWriteList; -import org.apache.felix.resolver.util.CopyOnWriteSet; -import org.apache.felix.resolver.util.OpenHashMap; -import org.apache.felix.resolver.util.OpenHashMapList; -import org.apache.felix.resolver.util.OpenHashMapSet; -import org.apache.felix.resolver.util.ShadowList; +import org.apache.felix.resolver.ResolverImpl.PermutationType; +import org.apache.felix.resolver.ResolverImpl.ResolveSession; +import org.apache.felix.resolver.util.*; import org.osgi.framework.Version; -import org.osgi.framework.namespace.HostNamespace; -import org.osgi.framework.namespace.IdentityNamespace; -import org.osgi.framework.namespace.PackageNamespace; -import org.osgi.resource.Capability; -import org.osgi.resource.Requirement; -import org.osgi.resource.Resource; -import org.osgi.resource.Wire; -import org.osgi.resource.Wiring; +import org.osgi.framework.namespace.*; +import org.osgi.resource.*; import org.osgi.service.resolver.HostedCapability; import org.osgi.service.resolver.ResolveContext; @@ -63,7 +43,7 @@ class Candidates } } - private final Set<Resource> m_mandatoryResources; + private final ResolveSession m_session; // Maps a capability to requirements that match it. private final OpenHashMapSet<Capability, Requirement> m_dependentMap; // Maps a requirement to the capability it matches. @@ -74,8 +54,6 @@ class Candidates // Map used when populating candidates to hold intermediate and final results. private final OpenHashMap<Resource, PopulateResult> m_populateResultCache; - private final Map<Resource, Boolean> m_validOnDemandResources; - private final Map<Capability, Requirement> m_subtitutableMap; private final OpenHashMapSet<Requirement, Capability> m_delta; @@ -84,21 +62,19 @@ class Candidates * Private copy constructor used by the copy() method. */ private Candidates( - Set<Resource> mandatoryResources, + ResolveSession session, OpenHashMapSet<Capability, Requirement> dependentMap, OpenHashMapList<Requirement, Capability> candidateMap, Map<Resource, WrappedResource> wrappedHosts, OpenHashMap<Resource, PopulateResult> populateResultCache, - Map<Resource, Boolean> onDemandResources, Map<Capability, Requirement> substitutableMap, OpenHashMapSet<Requirement, Capability> delta) { - m_mandatoryResources = mandatoryResources; + m_session = session; m_dependentMap = dependentMap; m_candidateMap = candidateMap; m_allWrappedHosts = wrappedHosts; m_populateResultCache = populateResultCache; - m_validOnDemandResources = onDemandResources; m_subtitutableMap = substitutableMap; m_delta = delta; } @@ -106,14 +82,13 @@ class Candidates /** * Constructs an empty Candidates object. */ - public Candidates(Map<Resource, Boolean> validOnDemandResources) + public Candidates(ResolveSession session) { - m_mandatoryResources = new HashSet<Resource>(); + m_session = session; m_dependentMap = new OpenHashMapSet<Capability, Requirement>(); m_candidateMap = new OpenHashMapList<Requirement, Capability>(); m_allWrappedHosts = new HashMap<Resource, WrappedResource>(); m_populateResultCache = new OpenHashMap<Resource, PopulateResult>(); - m_validOnDemandResources = validOnDemandResources; m_subtitutableMap = new OpenHashMap<Capability, Requirement>(); m_delta = new OpenHashMapSet<Requirement, Capability>(3); } @@ -123,35 +98,47 @@ class Candidates return m_populateResultCache.size(); } - public Map<Resource, Resource> getHosts() + public Map<Resource, Resource> getRootHosts() { - Map<Resource, Resource> hosts = new HashMap<Resource, Resource>(); - for (Resource res : m_mandatoryResources) + Map<Resource, Resource> hosts = new LinkedHashMap<Resource, Resource>(); + for (Resource res : m_session.getMandatoryResources()) { - if (res instanceof WrappedResource) - { - res = ((WrappedResource) res).getDeclaredResource(); - } - if (!Util.isFragment(res)) - { - hosts.put(res, getWrappedHost(res)); - } + addHost(res, hosts); } - for (Capability cap : m_dependentMap.keySet()) + + for (Resource res : m_session.getOptionalResources()) { - Resource res = cap.getResource(); - if (res instanceof WrappedResource) - { - res = ((WrappedResource) res).getDeclaredResource(); - } - if (!Util.isFragment(res)) - { - hosts.put(res, getWrappedHost(res)); + if (isPopulated(res)) { + addHost(res, hosts); } } + return hosts; } + private void addHost(Resource res, Map<Resource, Resource> hosts) { + if (res instanceof WrappedResource) + { + res = ((WrappedResource) res).getDeclaredResource(); + } + if (!Util.isFragment(res)) + { + hosts.put(res, getWrappedHost(res)); + } else { + Requirement hostReq = res.getRequirements(HostNamespace.HOST_NAMESPACE).get(0); + Capability hostCap = getFirstCandidate(hostReq); + // If the resource is an already resolved fragment and can not + // be attached to new hosts, there will be no matching host, + // so ignore this resource + if (hostCap != null) { + res = getWrappedHost(hostCap.getResource()); + if (res instanceof WrappedResource) { + hosts.put(((WrappedResource) res).getDeclaredResource(), res); + } + } + } + } + /** * Returns the delta which is the differences in the candidates from the * original Candidates permutation. @@ -162,14 +149,10 @@ class Candidates return m_delta; } - public void addMandatoryResources(Collection<Resource> resources) - { - m_mandatoryResources.addAll(resources); - } - @SuppressWarnings("ThrowableResultOfMethodCallIgnored") - public ResolutionError populate(ResolveContext rc, Collection<Resource> resources) + public void populate(Collection<Resource> resources) { + ResolveContext rc = m_session.getContext(); Set<Resource> toRemove = new HashSet<Resource>(); LinkedList<Resource> toPopulate = new LinkedList<Resource>(resources); while (!toPopulate.isEmpty()) @@ -201,14 +184,7 @@ class Candidates Collection<Resource> ondemandFragments = ((FelixResolveContext) rc).getOndemandResources(resource); for (Resource fragment : ondemandFragments) { - Boolean valid = m_validOnDemandResources.get(fragment); - if (valid == null) - { - // Mark this resource as a valid on demand resource - m_validOnDemandResources.put(fragment, Boolean.TRUE); - valid = Boolean.TRUE; - } - if (valid) + if (m_session.isValidOnDemandResource(fragment)) { // This resource is a valid on demand resource; // populate it now, consider it optional @@ -220,13 +196,13 @@ class Candidates } // We have a requirement to process Requirement requirement = result.remaining.remove(0); - if (!isEffective(rc, requirement)) + if (!isEffective(requirement)) { continue; } List<Capability> candidates = rc.findProviders(requirement); LinkedList<Resource> newToPopulate = new LinkedList<Resource>(); - ResolutionError thrown = processCandidates(rc, newToPopulate, requirement, candidates); + ResolutionError thrown = processCandidates(newToPopulate, requirement, candidates); if (candidates.isEmpty() && !Util.isOptional(requirement)) { if (Util.isFragment(resource) && rc.getWirings().containsKey(resource)) @@ -261,11 +237,10 @@ class Candidates iterator.remove(); remove(resource, toRemove); } - return null; } - private boolean isEffective(ResolveContext rc, Requirement req) { - if (!rc.isEffective(req)) { + private boolean isEffective(Requirement req) { + if (!m_session.getContext().isEffective(req)) { return false; } String res = req.getDirectives().get(PackageNamespace.REQUIREMENT_RESOLUTION_DIRECTIVE); @@ -352,7 +327,7 @@ class Candidates private static final int SUBSTITUTED = 2; private static final int EXPORTED = 3; - ResolutionError checkSubstitutes(List<Candidates> importPermutations) + ResolutionError checkSubstitutes() { OpenHashMap<Capability, Integer> substituteStatuses = new OpenHashMap<Capability, Integer>(m_subtitutableMap.size()); for (Capability substitutable : m_subtitutableMap.keySet()) @@ -373,7 +348,7 @@ class Candidates Requirement substitutedReq = m_subtitutableMap.get(substituteStatus.getKey()); if (substitutedReq != null) { - permutateIfNeeded(substitutedReq, importPermutations); + m_session.permutateIfNeeded(PermutationType.SUBSTITUTE, substitutedReq, this); } Set<Requirement> dependents = m_dependentMap.get(substituteStatus.getKey()); if (dependents != null) @@ -477,58 +452,53 @@ class Candidates return false; } - public ResolutionError populateDynamic( - ResolveContext rc, Resource resource, - Requirement req, List<Capability> candidates) + public ResolutionError populateDynamic() { - // Record the revision associated with the dynamic require - // as a mandatory revision. - m_mandatoryResources.add(resource); // Process the candidates, removing any candidates that // cannot resolve. // TODO: verify the two following statements LinkedList<Resource> toPopulate = new LinkedList<Resource>(); - ResolutionError rethrow = processCandidates(rc, toPopulate, req, candidates); + ResolutionError rethrow = processCandidates(toPopulate, m_session.getDynamicRequirement(), m_session.getDynamicCandidates()); // Add the dynamic imports candidates. // Make sure this is done after the call to processCandidates since we want to ensure // fragment candidates are properly hosted before adding the candidates list which makes a copy - addCandidates(req, candidates); + addCandidates(m_session.getDynamicRequirement(), m_session.getDynamicCandidates()); - populate(rc, toPopulate); + populate(toPopulate); - CopyOnWriteList<Capability> caps = m_candidateMap.get(req); + CopyOnWriteList<Capability> caps = m_candidateMap.get(m_session.getDynamicRequirement()); if (caps != null) { - candidates.retainAll(caps); + m_session.getDynamicCandidates().retainAll(caps); } else { - candidates.clear(); + m_session.getDynamicCandidates().clear(); } - if (candidates.isEmpty()) + if (m_session.getDynamicCandidates().isEmpty()) { if (rethrow == null) { - rethrow = new DynamicImportFailed(req); + rethrow = new DynamicImportFailed(m_session.getDynamicRequirement()); } return rethrow; } PopulateResult result = new PopulateResult(); result.success = true; - m_populateResultCache.put(resource, result); + m_populateResultCache.put(m_session.getDynamicHost(), result); return null; } private ResolutionError processCandidates( - ResolveContext rc, LinkedList<Resource> toPopulate, Requirement req, List<Capability> candidates) { + ResolveContext rc = m_session.getContext(); // Get satisfying candidates and populate their candidates if necessary. ResolutionError rethrow = null; Set<Capability> fragmentCands = null; @@ -551,6 +521,14 @@ class Candidates fragmentCands.add(candCap); } + // Do a sanity check incase the resolve context tries to attach + // a fragment to an already resolved host capability + if (HostNamespace.HOST_NAMESPACE.equals(req.getNamespace())) { + if (rc.getWirings().containsKey(candCap.getResource())) { + itCandCap.remove(); + continue; + } + } // If the candidate revision is a fragment, then always attempt // to populate candidates for its dependency, since it must be // attached to a host to be used. Otherwise, if the candidate @@ -780,7 +758,7 @@ class Candidates * @return ResolutionError if the removal of any unselected fragments * result in the root module being unable to resolve. */ - public ResolutionError prepare(ResolveContext rc) + public ResolutionError prepare() { // Maps a host capability to a map containing its potential fragments; // the fragment map maps a fragment symbolic name to a map that maps @@ -931,7 +909,7 @@ class Candidates original.remove(removeIdx); cands.remove(removeIdx); } - int insertIdx = rc.insertHostedCapability( + int insertIdx = m_session.getContext().insertHostedCapability( original, new SimpleHostedCapability( hostResource.getDeclaredResource(), @@ -971,7 +949,7 @@ class Candidates // Lastly, verify that all mandatory revisions are still // populated, since some might have become unresolved after // selecting fragments/singletons. - for (Resource resource : m_mandatoryResources) + for (Resource resource : m_session.getMandatoryResources()) { if (!isPopulated(resource)) { @@ -1154,12 +1132,11 @@ class Candidates public Candidates copy() { return new Candidates( - m_mandatoryResources, + m_session, m_dependentMap.deepClone(), m_candidateMap.deepClone(), m_allWrappedHosts, m_populateResultCache, - m_validOnDemandResources, m_subtitutableMap, m_delta.deepClone()); } @@ -1206,14 +1183,15 @@ class Candidates System.out.println("=== END CANDIDATE MAP ==="); } - public void permutate(Requirement req, List<Candidates> permutations) + public Candidates permutate(Requirement req) { if (!Util.isMultiple(req) && canRemoveCandidate(req)) { Candidates perm = copy(); perm.removeFirstCandidate(req); - permutations.add(perm); + return perm; } + return null; } public boolean canRemoveCandidate(Requirement req) @@ -1222,36 +1200,6 @@ class Candidates return ((candidates != null) && (candidates.size() > 1 || Util.isOptional(req))); } - public void permutateIfNeeded(Requirement req, List<Candidates> permutations) - { - List<Capability> candidates = m_candidateMap.get(req); - if ((candidates != null) && (candidates.size() > 1)) - { - // Check existing permutations to make sure we haven't - // already permutated this requirement. This check for - // duplicate permutations is simplistic. It assumes if - // there is any permutation that contains a different - // initial candidate for the requirement in question, - // then it has already been permutated. - boolean permutated = false; - for (Candidates existingPerm : permutations) - { - List<Capability> existingPermCands = existingPerm.m_candidateMap.get(req); - if (existingPermCands != null && !existingPermCands.get(0).equals(candidates.get(0))) - { - permutated = true; - break; - } - } - // If we haven't already permutated the existing - // import, do so now. - if (!permutated) - { - permutate(req, permutations); - } - } - } - static class DynamicImportFailed extends ResolutionError { private final Requirement requirement; diff --git a/bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/ResolverImpl.java b/bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/ResolverImpl.java index ded683fd7..b435aabae 100755 --- a/bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/ResolverImpl.java +++ b/bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/ResolverImpl.java @@ -18,43 +18,16 @@ */ package org.apache.felix.resolver; -import java.security.AccessControlContext; -import java.security.AccessController; -import java.security.PrivilegedAction; -import java.util.ArrayList; -import java.util.Collection; -import java.util.Collections; -import java.util.HashMap; -import java.util.HashSet; -import java.util.LinkedHashSet; -import java.util.List; -import java.util.Map; +import java.security.*; +import java.util.*; import java.util.Map.Entry; -import java.util.Set; -import java.util.concurrent.ConcurrentHashMap; -import java.util.concurrent.ConcurrentMap; -import java.util.concurrent.Executor; -import java.util.concurrent.ExecutorService; -import java.util.concurrent.Executors; +import java.util.concurrent.*; import java.util.concurrent.atomic.AtomicInteger; - import org.apache.felix.resolver.util.ArrayMap; import org.apache.felix.resolver.util.OpenHashMap; -import org.osgi.framework.namespace.BundleNamespace; -import org.osgi.framework.namespace.ExecutionEnvironmentNamespace; -import org.osgi.framework.namespace.HostNamespace; -import org.osgi.framework.namespace.IdentityNamespace; -import org.osgi.framework.namespace.PackageNamespace; -import org.osgi.resource.Capability; -import org.osgi.resource.Namespace; -import org.osgi.resource.Requirement; -import org.osgi.resource.Resource; -import org.osgi.resource.Wire; -import org.osgi.resource.Wiring; -import org.osgi.service.resolver.HostedCapability; -import org.osgi.service.resolver.ResolutionException; -import org.osgi.service.resolver.ResolveContext; -import org.osgi.service.resolver.Resolver; +import org.osgi.framework.namespace.*; +import org.osgi.resource.*; +import org.osgi.service.resolver.*; public class ResolverImpl implements Resolver { @@ -69,29 +42,65 @@ public class ResolverImpl implements Resolver private final Executor m_executor; + enum PermutationType { + USES, + IMPORT, + SUBSTITUTE + } + // Note this class is not thread safe. // Only use in the context of a single thread. - class ResolveSession + static class ResolveSession { // Holds the resolve context for this session private final ResolveContext m_resolveContext; + private final Collection<Resource> m_mandatoryResources; + private final Collection<Resource> m_optionalResources; + private final Resource m_dynamicHost; + private final Requirement m_dynamicReq; + private final List<Capability> m_dynamicCandidates; + // keeps track of valid on demand fragments that we have seen. + // a null value or TRUE indicate it is valid + Map<Resource, Boolean> m_validOnDemandResources = new HashMap<Resource, Boolean>(0); // Holds candidate permutations based on permutating "uses" chains. // These permutations are given higher priority. - private final List<Candidates> m_usesPermutations = new ArrayList<Candidates>(); + private final List<Candidates> m_usesPermutations = new LinkedList<Candidates>(); + private int m_usesIndex = 0; // Holds candidate permutations based on permutating requirement candidates. // These permutations represent backtracking on previous decisions. - private final List<Candidates> m_importPermutations = new ArrayList<Candidates>(); + private final List<Candidates> m_importPermutations = new LinkedList<Candidates>(); + private int m_importIndex = 0; + // Holds candidate permutations based on substituted packages + private final List<Candidates> m_substPermutations = new LinkedList<Candidates>(); + private int m_substituteIndex = 0; // Holds candidate permutations based on removing candidates that satisfy // multiple cardinality requirements. // This permutation represents a permutation that is consistent because we have // removed the offending capabilities private Candidates m_multipleCardCandidates = null; - + // The delta is used to detect that we have already processed this particular permutation + private final Set<Object> m_processedDeltas = new HashSet<Object>(); + private final Executor m_executor; + private final Set<Requirement> m_mutated = new HashSet<Requirement>(); + private final Set<Requirement> m_sub_mutated = new HashSet<Requirement>(); private final ConcurrentMap<String, List<String>> m_usesCache = new ConcurrentHashMap<String, List<String>>(); + private ResolutionError m_currentError; - ResolveSession(ResolveContext resolveContext) + ResolveSession(ResolveContext resolveContext, Executor executor, Resource dynamicHost, Requirement dynamicReq, List<Capability> dynamicCandidates) { m_resolveContext = resolveContext; + m_executor = executor; + m_dynamicHost = dynamicHost; + m_dynamicReq = dynamicReq; + m_dynamicCandidates = dynamicCandidates; + if (m_dynamicHost != null) { + m_mandatoryResources = Collections.singletonList(dynamicHost); + m_optionalResources = Collections.emptyList(); + } else { + // Make copies of arguments in case we want to modify them. + m_mandatoryResources = new ArrayList<Resource>(resolveContext.getMandatoryResources()); + m_optionalResources = new ArrayList<Resource>(resolveContext.getOptionalResources()); + } } Candidates getMultipleCardCandidates() @@ -99,19 +108,198 @@ public class ResolverImpl implements Resolver return m_multipleCardCandidates; } - void setMultipleCardCandidates(Candidates multipleCardCandidates) - { - m_multipleCardCandidates = multipleCardCandidates; - } - ResolveContext getContext() { return m_resolveContext; } - public ConcurrentMap<String, List<String>> getUsesCache() { + ConcurrentMap<String, List<String>> getUsesCache() { return m_usesCache; } + + void permutateIfNeeded(PermutationType type, Requirement req, Candidates permutation) { + List<Capability> candidates = permutation.getCandidates(req); + if ((candidates != null) && (candidates.size() > 1)) + { + if ((type == PermutationType.SUBSTITUTE)) { + if (!m_sub_mutated.add(req)) { + return; + } + } else if (!m_mutated.add(req)) { + return; + } + // If we haven't already permutated the existing + // import, do so now. + addPermutation(type, permutation.permutate(req)); + } + } + + private void clearMutateIndexes() { + m_usesIndex = 0; + m_importIndex = 0; + m_substituteIndex = 0; + m_mutated.clear(); + // NOTE: m_sub_mutated is never cleared. + // It is unclear if even more permutations based on a substitutions will ever help. + // Being safe and reducing extra permutations until we get a scenario that proves + // more permutations would really help. + } + + void addPermutation(PermutationType type, Candidates permutation) { + if (permutation != null) + { + List<Candidates> typeToAddTo = null; + try { + switch (type) { + case USES : + typeToAddTo = m_usesPermutations; + m_usesPermutations.add(m_usesIndex++, permutation); + break; + case IMPORT : + typeToAddTo = m_importPermutations; + m_importPermutations.add(m_importIndex++, permutation); + break; + case SUBSTITUTE : + typeToAddTo = m_substPermutations; + m_substPermutations.add(m_substituteIndex++, permutation); + break; + default : + throw new IllegalArgumentException("Unknown permitation type: " + type); + } + } catch (IndexOutOfBoundsException e) { + // just a safeguard, this really should never happen + typeToAddTo.add(permutation); + } + } + } + + Candidates getNextPermutation() { + Candidates next = null; + do { + if (!m_usesPermutations.isEmpty()) + { + next = m_usesPermutations.remove(0); + } + else if (!m_importPermutations.isEmpty()) + { + next = m_importPermutations.remove(0); + } + else if (!m_substPermutations.isEmpty()) + { + next = m_substPermutations.remove(0); + } + else { + return null; + } + } + while(!m_processedDeltas.add(next.getDelta())); + // Null out each time a new permutation is attempted. + // We only use this to store a valid permutation which is a + // delta of the current permutation. + m_multipleCardCandidates = null; + // clear mutateIndexes also so we insert new permutations + // based of this permutation as a higher priority + clearMutateIndexes(); + return next; + } + + void clearPermutations() { + m_usesPermutations.clear(); + m_importPermutations.clear(); + m_substPermutations.clear(); + m_multipleCardCandidates = null; + m_processedDeltas.clear(); + m_currentError = null; + } + + boolean checkMultiple( + UsedBlames usedBlames, + Blame usedBlame, + Candidates permutation) + { + // Check the root requirement to see if it is a multiple cardinality + // requirement. + List<Capability> candidates = null; + Requirement req = usedBlame.m_reqs.get(0); + if (Util.isMultiple(req)) + { + // Create a copy of the current permutation so we can remove the + // candidates causing the blame. + if (m_multipleCardCandidates == null) + { + m_multipleCardCandidates = permutation.copy(); + } + // Get the current candidate list and remove all the offending root + // cause candidates from a copy of the current permutation. + candidates = m_multipleCardCandidates.clearCandidates(req, usedBlames.getRootCauses(req)); + } + // We only are successful if there is at least one candidate left + // for the requirement + return (candidates != null) && !candidates.isEmpty(); + } + + long getPermutationCount() { + return m_usesPermutations.size() + m_importPermutations.size() + m_substPermutations.size(); + } + + Executor getExecutor() { + return m_executor; + } + + ResolutionError getCurrentError() { + return m_currentError; + } + + void setCurrentError(ResolutionError error) { + this.m_currentError = error; + } + + boolean isDynamic() { + return m_dynamicHost != null; + } + + Collection<Resource> getMandatoryResources() { + return m_mandatoryResources; + } + + Collection<Resource> getOptionalResources() { + return m_optionalResources; + } + + Resource getDynamicHost() { + return m_dynamicHost; + } + + Requirement getDynamicRequirement() { + return m_dynamicReq; + } + + List<Capability> getDynamicCandidates() { + return m_dynamicCandidates; + } + + public boolean isValidOnDemandResource(Resource fragment) { + Boolean valid = m_validOnDemandResources.get(fragment); + if (valid == null) + { + // Mark this resource as a valid on demand resource + m_validOnDemandResources.put(fragment, Boolean.TRUE); + valid = Boolean.TRUE; + } + return valid; + } + + public boolean invalidateOnDemandResource(Resource faultyResource) { + Boolean valid = m_validOnDemandResources.get(faultyResource); + if (valid != null && valid) + { + // This was an ondemand resource. + // Invalidate it and try again. + m_validOnDemandResources.put(faultyResource, Boolean.FALSE); + return true; + } + return false; + } } public ResolverImpl(Logger logger) @@ -182,16 +370,12 @@ public class ResolverImpl implements Resolver public Map<Resource, List<Wire>> resolve(ResolveContext rc, Executor executor) throws ResolutionException { - ResolveSession session = new ResolveSession(rc); - Map<Resource, List<Wire>> wireMap = - new HashMap<Resource, List<Wire>>(); + ResolveSession session = new ResolveSession(rc, executor, null, null, null); + return doResolve(session); + } - // Make copies of arguments in case we want to modify them. - Collection<Resource> mandatoryResources = new ArrayList<Resource>(rc.getMandatoryResources()); - Collection<Resource> optionalResources = new ArrayList<Resource>(rc.getOptionalResources()); - // keeps track of valid on demand fragments that we have seen. - // a null value or TRUE indicate it is valid - Map<Resource, Boolean> validOnDemandResources = new HashMap<Resource, Boolean>(0); + private Map doResolve(ResolveSession session) throws ResolutionException { + Map<Resource, List<Wire>> wireMap = new HashMap<Resource, List<Wire>>(); boolean retry; do @@ -199,212 +383,40 @@ public class ResolverImpl implements Resolver retry = false; try { - // Create object to hold all candidates. - Candidates allCandidates = new Candidates(validOnDemandResources); - - List<Resource> mandatory = new ArrayList<Resource>(); - List<Resource> toPopulate = new ArrayList<Resource>(); - - // Populate mandatory resources; since these are mandatory - // resources, failure throws a resolve exception. - for (Resource resource : mandatoryResources) - { - if (Util.isFragment(resource) || (rc.getWirings().get(resource) == null)) - { - mandatory.add(resource); - toPopulate.add(resource); - } - } - // Populate optional resources; since these are optional - // resources, failure does not throw a resolve exception. - for (Resource resource : optionalResources) - { - if (Util.isFragment(resource) || (rc.getWirings().get(resource) == null)) - { - toPopulate.add(resource); - } - } - - allCandidates.addMandatoryResources(mandatory); - allCandidates.populate(rc, toPopulate); - - // Merge any fragments into hosts. - ResolutionError rethrow = allCandidates.prepare(rc); - if (rethrow != null) - { - throw rethrow.toException(); - } - - // Create a combined list of populated resources; for - // optional resources. We do not need to consider ondemand - // fragments, since they will only be pulled in if their - // host is already present. - Set<Resource> allResources = - new LinkedHashSet<Resource>(mandatoryResources); - for (Resource resource : optionalResources) - { - if (allCandidates.isPopulated(resource)) - { - allResources.add(resource); - } - } - - // Holds candidate permutations based on permutating "uses" chains. - // These permutations are given higher priority. - List<Candidates> usesPermutations = new ArrayList<Candidates>(); - // Holds candidate permutations based on permutating requirement candidates. - // These permutations represent backtracking on previous decisions. - List<Candidates> importPermutations = new ArrayList<Candidates>(); - // Holds candidate permutations based on substituted packages - List<Candidates> substPermutations = new ArrayList<Candidates>(); - - // Record the initial candidate permutation. - usesPermutations.add(allCandidates); - - // If a populated resource is a fragment, then its host - // must ultimately be verified, so store its host requirement - // to use for package space calculation. - Map<Resource, Requirement> hostReqs = new HashMap<Resource, Requirement>(); - for (Resource resource : allResources) - { - if (Util.isFragment(resource)) - { - hostReqs.put( - resource, - resource.getRequirements(HostNamespace.HOST_NAMESPACE).get(0)); - } + getInitialCandidates(session); + if (session.getCurrentError() != null) { + throw session.getCurrentError().toException(); } - Set<Object> processedDeltas = new HashSet<Object>(); - Map<Resource, ResolutionError> faultyResources = null; - do - { - if (!usesPermutations.isEmpty()) - { - allCandidates = usesPermutations.remove(0); - } - else if (!importPermutations.isEmpty()) - { - allCandidates = importPermutations.remove(0); - } - else if (!substPermutations.isEmpty()) - { - allCandidates = substPermutations.remove(0); - } - else - { - break; - } - - // The delta is used to detect that we have already processed this particular permutation - if (!processedDeltas.add(allCandidates.getDelta())) - { - // This permutation has already been tried - // Don't try it again - continue; - } - - // Null out each time a new permutation is attempted. - // We only use this to store a valid permutation which is a - // delta of the current permutation. - session.setMultipleCardCandidates(null); - -//allCandidates.dump(); - - rethrow = allCandidates.checkSubstitutes(substPermutations); - if (rethrow != null) - { - continue; - } - - // Compute the list of hosts - Map<Resource, Resource> hosts = new OpenHashMap<Resource, Resource>(); - for (Resource resource : allResources) - { - // If we are resolving a fragment, then get its - // host candidate and verify it instead. - Requirement hostReq = hostReqs.get(resource); - if (hostReq != null) - { - Capability hostCap = allCandidates.getFirstCandidate(hostReq); - // If the resource is an already resolved fragment and can not - // be attached to new hosts, there will be no matching host, - // so ignore this resource - if (hostCap == null) - { - continue; - } - resource = hostCap.getResource(); - } - hosts.put(resource, allCandidates.getWrappedHost(resource)); - } - - Map<Resource, ResolutionError> currentFaultyResources = new HashMap<Resource, ResolutionError>(); - - List<Candidates> newUses = new ArrayList<Candidates>(); - List<Candidates> newImports = new ArrayList<Candidates>(); - - rethrow = checkConsistency( - executor, - session, - newUses, - newImports, - allCandidates, - currentFaultyResources, - hosts, - false); - - usesPermutations.addAll(0, newUses); - importPermutations.addAll(0, newImports); - - if (!currentFaultyResources.isEmpty()) - { - if (faultyResources == null) - { - faultyResources = currentFaultyResources; - } - else if (faultyResources.size() > currentFaultyResources.size()) - { - // save the optimal faultyResources which has less - faultyResources = currentFaultyResources; - } - } - } - while (rethrow != null); + Map<Resource, ResolutionError> faultyResources = new HashMap<Resource, ResolutionError>(); + Candidates allCandidates = findValidCandidates(session, faultyResources); // If there is a resolve exception, then determine if an // optionally resolved resource is to blame (typically a fragment). // If so, then remove the optionally resolved resolved and try - // again; otherwise, rethrow the resolve exception. - if (rethrow != null) + // again; otherwise, m_currentError the resolve exception. + if (session.getCurrentError() != null) { - if (faultyResources != null) + Set<Resource> resourceKeys = faultyResources.keySet(); + retry = (session.getOptionalResources().removeAll(resourceKeys)); + for (Resource faultyResource : resourceKeys) { - Set<Resource> resourceKeys = faultyResources.keySet(); - retry = (optionalResources.removeAll(resourceKeys)); - for (Resource faultyResource : resourceKeys) - { - Boolean valid = validOnDemandResources.get(faultyResource); - if (valid != null && valid) - { - // This was an ondemand resource. - // Invalidate it and try again. - validOnDemandResources.put(faultyResource, Boolean.FALSE); - retry = true; - } - } - // log all the resolution exceptions for the uses constraint violations - for (Map.Entry<Resource, ResolutionError> usesError : faultyResources.entrySet()) + if (session.invalidateOnDemandResource(faultyResource)) { - m_logger.logUsesConstraintViolation(usesError.getKey(), usesError.getValue()); + retry = true; } } + // log all the resolution exceptions for the uses constraint violations + for (Map.Entry<Resource, ResolutionError> usesError : faultyResources.entrySet()) + { + m_logger.logUsesConstraintViolation(usesError.getKey(), usesError.getValue()); + } if (!retry) { - throw rethrow.toException(); + throw session.getCurrentError().toException(); } } - // If there is no exception to rethrow, then this was a clean + // If there is no exception to m_currentError, then this was a clean // resolve, so populate the wire map. else { @@ -415,32 +427,23 @@ public class ResolverImpl implements Resolver // Use the consistent permutation allCandidates = session.getMultipleCardCandidates(); } - for (Resource resource : allResources) + if (session.isDynamic() ) { - Resource target = resource; - - // If we are resolving a fragment, then we - // actually want to populate its host's wires. - Requirement hostReq = hostReqs.get(resource); - if (hostReq != null) + wireMap = populateDynamicWireMap(session.getContext(), + session.getDynamicHost(), session.getDynamicRequirement(), + wireMap, allCandidates); + } + else + { + for (Resource resource : allCandidates.getRootHosts().keySet()) { - Capability hostCap = allCandidates.getFirstCandidate(hostReq); - // If the resource is an already resolved fragment and can not - // be attached to new hosts, there will be no matching host, - // so ignore this resource - if (hostCap == null) + if (allCandidates.isPopulated(resource)) { - continue; + wireMap = + populateWireMap( + session.getContext(), allCandidates.getWrappedHost(resource), + wireMap, allCandidates); } - target = hostCap.getResource(); - } - - if (allCandidates.isPopulated(target)) - { - wireMap = - populateWireMap( - rc, allCandidates.getWrappedHost(target), - wireMap, allCandidates); } } } @@ -448,7 +451,7 @@ public class ResolverImpl implements Resolver finally { // Always clear the state. - session.setMultipleCardCandidates(null); + session.clearPermutations(); } } while (retry); @@ -456,28 +459,123 @@ public class ResolverImpl implements Resolver return wireMap; } + private void getInitialCandidates(ResolveSession session) { + // Create object to hold all candidates. + Candidates initialCandidates; + if (session.isDynamic()) { + // Create all candidates pre-populated with the single candidate set + // for the resolving dynamic import of the host. + initialCandidates = new Candidates(session); + ResolutionError prepareError = initialCandidates.populateDynamic(); + if (prepareError != null) { + session.setCurrentError(prepareError); + return; + } + } else { + List<Resource> toPopulate = new ArrayList<Resource>(); + + // Populate mandatory resources; since these are mandatory + // resources, failure throws a resolve exception. + for (Resource resource : session.getMandatoryResources()) + { + if (Util.isFragment(resource) || (session.getContext().getWirings().get(resource) == null)) + { + toPopulate.add(resource); + } + } + // Populate optional resources; since these are optional + // resources, failure does not throw a resolve exception. + for (Resource resource : session.getOptionalResources()) + { + if (Util.isFragment(resource) || (session.getContext().getWirings().get(resource) == null)) + { + toPopulate.add(resource); + } + } + + initialCandidates = new Candidates(session); + initialCandidates.populate(toPopulate); + } + + // Merge any fragments into hosts. + ResolutionError prepareError = initialCandidates.prepare(); + if (prepareError != null) + { + session.setCurrentError(prepareError); + } + else + { + // Record the initial candidate permutation. + session.addPermutation(PermutationType.USES, initialCandidates); + } + } + + private Candidates findValidCandidates(ResolveSession session, Map<Resource, ResolutionError> faultyResources) { + Candidates allCandidates = null; + boolean foundFaultyResources = false; + do + { + allCandidates = session.getNextPermutation(); + if (allCandidates == null) + { + break; + } + +//allCandidates.dump(); + + Map<Resource, ResolutionError> currentFaultyResources = new HashMap<Resource, ResolutionError>(); + + session.setCurrentError( + checkConsistency( + session, + allCandidates, + currentFaultyResources + ) + ); + + if (!currentFaultyResources.isEmpty()) + { + if (!foundFaultyResources) + { + foundFaultyResources = true; + faultyResources.putAll(currentFaultyResources); + } + else if (faultyResources.size() > currentFaultyResources.size()) + { + // save the optimal faultyResources which has less + faultyResources.clear(); + faultyResources.putAll(currentFaultyResources); + } + } + } + while (session.getCurrentError() != null); + + return allCandidates; + } + private ResolutionError checkConsistency( - Executor executor, ResolveSession session, - List<Candidates> usesPermutations, - List<Candidates> importPermutations, Candidates allCandidates, - Map<Resource, ResolutionError> currentFaultyResources, - Map<Resource, Resource> hosts, - boolean dynamic) + Map<Resource, ResolutionError> currentFaultyResources) { + ResolutionError rethrow = allCandidates.checkSubstitutes(); + if (rethrow != null) + { + return rethrow; + } + Map<Resource, Resource> allhosts = allCandidates.getRootHosts(); // Calculate package spaces Map<Resource, Packages> resourcePkgMap = - calculatePackageSpaces(executor, session, allCandidates, hosts.values()); + calculatePackageSpaces(session, allCandidates, allhosts.values()); ResolutionError error = null; // Check package consistency Map<Resource, Object> resultCache = new OpenHashMap<Resource, Object>(resourcePkgMap.size()); - for (Entry<Resource, Resource> entry : hosts.entrySet()) + for (Entry<Resource, Resource> entry : allhosts.entrySet()) { - ResolutionError rethrow = checkPackageSpaceConsistency( - session, usesPermutations, importPermutations, entry.getValue(), - allCandidates, dynamic, resourcePkgMap, resultCache); + rethrow = checkPackageSpaceConsistency( + session, entry.getValue(), + allCandidates, session.isDynamic(), resourcePkgMap, resultCache); if (rethrow != null) { Resource faultyResource = entry.getKey(); @@ -528,9 +626,6 @@ public class ResolverImpl implements Resolver List<Capability> matches) throws ResolutionException { - ResolveSession session = new ResolveSession(rc); - Map<Resource, List<Wire>> wireMap = new HashMap<Resource, List<Wire>>(); - // We can only create a dynamic import if the following // conditions are met: // 1. The specified resource is resolved. @@ -549,122 +644,11 @@ public class ResolverImpl implements Resolver "Matching candidate does not provide a package name."); } } - - Map<Resource, Packages> resourcePkgMap = new HashMap<Resource, Packages>(); - Map<Resource, Boolean> onDemandResources = new HashMap<Resource, Boolean>(); - - boolean retry; - do - { - retry = false; - - try - { - // Create all candidates pre-populated with the single candidate set - // for the resolving dynamic import of the host. - Candidates allCandidates = new Candidates(onDemandResources); - ResolutionError rethrow = allCandidates.populateDynamic(rc, host, dynamicReq, matches); - if (rethrow == null) - { - // Merge any fragments into hosts. - rethrow = allCandidates.prepare(rc); - } - if (rethrow != null) - { - throw rethrow.toException(); - } - - List<Candidates> usesPermutations = new ArrayList<Candidates>(); - List<Candidates> importPermutations = new ArrayList<Candidates>(); - - // Record the initial candidate permutation. - usesPermutations.add(allCandidates); - - do - { - resourcePkgMap.clear(); - - allCandidates = (usesPermutations.size() > 0) - ? usesPermutations.remove(0) - : importPermutations.remove(0); -//allCandidates.dump(); - - rethrow = allCandidates.checkSubstitutes(importPermutations); - if (rethrow != null) - { - continue; - } - // For a dynamic import, the instigating resource - // will never be a fragment since fragments never - // execute code, so we don't need to check for - // this case like we do for a normal resolve. - rethrow = checkConsistency( - new DumbExecutor(), - session, usesPermutations, importPermutations, allCandidates, - new OpenHashMap<Resource, ResolutionError>(resourcePkgMap.size()), - allCandidates.getHosts(), - true); - } - while ((rethrow != null) - && ((usesPermutations.size() > 0) || (importPermutations.size() > 0))); - - // If there is a resolve exception, then determine if an - // optionally resolved resource is to blame (typically a fragment). - // If so, then remove the optionally resolved resource and try - // again; otherwise, rethrow the resolve exception. - if (rethrow != null) - { - Collection<Requirement> exReqs = rethrow.getUnresolvedRequirements(); - Requirement faultyReq = ((exReqs == null) || (exReqs.isEmpty())) - ? null : exReqs.iterator().next(); - Resource faultyResource = (faultyReq == null) - ? null : getDeclaredResource(faultyReq.getResource()); - // If the faulty requirement is wrapped, then it may - // be from a fragment, so consider the fragment faulty - // instead of the host. - if (faultyReq instanceof WrappedRequirement) - { - faultyResource = - ((WrappedRequirement) faultyReq) - .getDeclaredRequirement().getResource(); - } - Boolean valid = onDemandResources.get(faultyResource); - if (valid != null && valid) - { - onDemandResources.put(faultyResource, Boolean.FALSE); - retry = true; - } - else - { - throw rethrow.toException(); - } - } - // If there is no exception to rethrow, then this was a clean - // resolve, so populate the wire map. - else - { - if (session.getMultipleCardCandidates() != null) - { - // TODO this was not done before; but I think it should be; - // Candidates for multiple cardinality requirements were - // removed in order to provide a consistent class space. - // Use the consistent permutation - allCandidates = session.getMultipleCardCandidates(); - } - wireMap = populateDynamicWireMap(rc, - host, dynamicReq, wireMap, allCandidates); - } - } - finally - { - // Always clear the state. - session.setMultipleCardCandidates(null); - } - } - while (retry); + ResolveSession session = new ResolveSession(rc, new DumbExecutor(), host, dynamicReq, matches); + return doResolve(session); } - return wireMap; + return Collections.emptyMap(); } private static List<WireCandidate> getWireCandidates(ResolveSession session, Candidates allCandidates, Resource resource) @@ -707,23 +691,12 @@ public class ResolverImpl implements Resolver // the dynamic import is added here last to the // list is used later when checking to see if the package being // dynamically imported shadows an existing provider. - for (Requirement req : wiring.getResourceRequirements(null)) + Requirement dynamicReq = session.getDynamicRequirement(); + if (dynamicReq != null && resource.equals(session.getDynamicHost())) { - if (!Util.isDynamic(req)) - { - continue; - } // Grab first (i.e., highest priority) candidate. - Capability cap = allCandidates.getFirstCandidate(req); - // Optional requirements may not have any candidates. - if (cap == null) - { - continue; - } - wireCandidates.add(new WireCandidate(req, cap)); - // Can only dynamically import one at a time, so break - // out of the loop after the first. - break; + Capability cap = allCandidates.getFirstCandidate(dynamicReq); + wireCandidates.add(new WireCandidate(dynamicReq, cap)); } } else @@ -1117,12 +1090,11 @@ public class ResolverImpl implements Resolver } private static Map<Resource, Packages> calculatePackageSpaces( - final Executor innerExecutor, final ResolveSession session, final Candidates allCandidates, Collection<Resource> hosts) { - final EnhancedExecutor executor = new EnhancedExecutor(innerExecutor); + final EnhancedExecutor executor = new EnhancedExecutor(session.getExecutor()); // Parallel compute wire candidates final Map<Resource, List<WireCandidate>> allWireCandidates = new ConcurrentHashMap<Resource, List<WireCandidate>>(); @@ -1289,8 +1261,6 @@ public class ResolverImpl implements Resolver private ResolutionError checkPackageSpaceConsistency( ResolveSession session, - List<Candidates> usesPermutations, - List<Candidates> importPermutations, Resource resource, Candidates allCandidates, boolean dynamic, @@ -1333,9 +1303,9 @@ public class ResolverImpl implements Resolver else if (!sourceBlame.m_cap.getResource().equals(blame.m_cap.getResource())) { // Try to permutate the conflicting requirement. - allCandidates.permutate(blame.m_reqs.get(0), importPermutations); + session.addPermutation(PermutationType.IMPORT, allCandidates.permutate(blame.m_reqs.get(0))); // Try to permutate the source requirement. - allCandidates.permutate(sourceBlame.m_reqs.get(0), importPermutations); + session.addPermutation(PermutationType.IMPORT, allCandidates.permutate(sourceBlame.m_reqs.get(0))); // Report conflict. rethrow = new UseConstraintError( session.getContext(), allCandidates, @@ -1370,7 +1340,7 @@ public class ResolverImpl implements Resolver { for (Blame usedBlame : usedBlames.m_blames) { - if (checkMultiple(session, usedBlames, usedBlame, allCandidates)) + if (session.checkMultiple(usedBlames, usedBlame, allCandidates)) { // Continue to the next usedBlame, if possible we // removed the conflicting candidates. @@ -1423,7 +1393,7 @@ public class ResolverImpl implements Resolver { if (!mutated.isEmpty()) { - usesPermutations.add(permutation); + session.addPermutation(PermutationType.USES, permutation); } if (m_logger.isDebugEnabled()) { @@ -1470,7 +1440,7 @@ public class ResolverImpl implements Resolver Blame requirementBlame = requirementBlames.get(0); for (Blame usedBlame : usedBlames.m_blames) { - if (checkMultiple(session, usedBlames, usedBlame, allCandidates)) + if (session.checkMultiple(usedBlames, usedBlame, allCandidates)) { // Continue to the next usedBlame, if possible we // removed the conflicting candidates. @@ -1529,10 +1499,10 @@ public class ResolverImpl implements Resolver // for the conflicting uses constraint. if (rethrow != null) { - // Add uses permutation if we mutated any candidates. + // Add uses permutation if we m_mutated any candidates. if (!mutated.isEmpty()) { - usesPermutations.add(permutation); + session.addPermutation(PermutationType.USES, permutation); } // Try to permutate the candidate for the original @@ -1547,7 +1517,7 @@ public class ResolverImpl implements Resolver // with existing import decisions, we may end up trying // to permutate the same import a lot of times, so we should // try to check if that the case and only permutate it once. - allCandidates.permutateIfNeeded(req, importPermutations); + session.permutateIfNeeded(PermutationType.IMPORT, req, allCandidates); } } @@ -1569,7 +1539,7 @@ public class ResolverImpl implements Resolver // current resource depends. Keep track of the current number // of permutations so we know if the lower level check was // able to create a permutation or not in the case of failure. - int permCount = usesPermutations.size() + importPermutations.size(); + long permCount = session.getPermutationCount(); for (Requirement req : resource.getRequirements(null)) { Capability cap = allCandidates.getFirstCandidate(req); @@ -1578,7 +1548,7 @@ public class ResolverImpl implements Resolver if (!resource.equals(cap.getResource())) { rethrow = checkPackageSpaceConsistency( - session, usesPermutations, importPermutations, cap.getResource(), + session, cap.getResource(), allCandidates, false, resourcePkgMap, resultCache); if (rethrow != null) { @@ -1586,9 +1556,9 @@ public class ResolverImpl implements Resolver // then we should create an import permutation for the // requirement with the dependency on the failing resource // to backtrack on our current candidate selection. - if (permCount == (usesPermutations.size() + importPermutations.size())) + if (permCount == session.getPermutationCount()) { - allCandidates.permutate(req, importPermutations); + session.addPermutation(PermutationType.IMPORT, allCandidates.permutate(req)); } return rethrow; } @@ -1598,33 +1568,6 @@ public class ResolverImpl implements Resolver return null; } - private boolean checkMultiple( - ResolveSession session, - UsedBlames usedBlames, - Blame usedBlame, - Candidates permutation) - { - // Check the root requirement to see if it is a multiple cardinality - // requirement. - List<Capability> candidates = null; - Requirement req = usedBlame.m_reqs.get(0); - if (Util.isMultiple(req)) - { - // Create a copy of the current permutation so we can remove the - // candidates causing the blame. - if (session.getMultipleCardCandidates() == null) - { - session.setMultipleCardCandidates(permutation.copy()); - } - // Get the current candidate list and remove all the offending root - // cause candidates from a copy of the current permutation. - candidates = session.getMultipleCardCandidates().clearCandidates(req, usedBlames.getRootCauses(req)); - } - // We only are successful if there is at least one candidate left - // for the requirement - return (candidates != null) && !candidates.isEmpty(); - } - private static OpenHashMap<String, Blame> calculateExportedPackages( ResolveSession session, Candidates allCandidates, |