Author: pauls Date: Fri Feb 23 13:52:46 2018 New Revision: 1825128 URL: http://svn.apache.org/viewvc?rev=1825128&view=rev Log: Merge FELIX-5601 into the r7 resolver, update to the latest OSGi sources, and set the version to 1.2.0-SNAPSHOT.
Modified: felix/trunk/osgi-r7/resolver/pom.xml felix/trunk/osgi-r7/resolver/src/main/java/org/apache/felix/resolver/Candidates.java felix/trunk/osgi-r7/resolver/src/main/java/org/apache/felix/resolver/ResolverImpl.java felix/trunk/osgi-r7/resolver/src/main/java/org/osgi/service/resolver/ResolveContext.java felix/trunk/osgi-r7/resolver/src/main/java/org/osgi/service/resolver/Resolver.java felix/trunk/osgi-r7/resolver/src/test/java/org/apache/felix/resolver/test/ResolverTest.java Modified: felix/trunk/osgi-r7/resolver/pom.xml URL: http://svn.apache.org/viewvc/felix/trunk/osgi-r7/resolver/pom.xml?rev=1825128&r1=1825127&r2=1825128&view=diff ============================================================================== --- felix/trunk/osgi-r7/resolver/pom.xml (original) +++ felix/trunk/osgi-r7/resolver/pom.xml Fri Feb 23 13:52:46 2018 @@ -29,7 +29,7 @@ <description> Provide OSGi resolver service. </description> - <version>1.11.0-SNAPSHOT</version> + <version>1.2.0-SNAPSHOT</version> <artifactId>org.apache.felix.resolver</artifactId> <scm> <connection>scm:svn:http://svn.apache.org/repos/asf/felix/trunk/resolver</connection> Modified: felix/trunk/osgi-r7/resolver/src/main/java/org/apache/felix/resolver/Candidates.java URL: http://svn.apache.org/viewvc/felix/trunk/osgi-r7/resolver/src/main/java/org/apache/felix/resolver/Candidates.java?rev=1825128&r1=1825127&r2=1825128&view=diff ============================================================================== --- felix/trunk/osgi-r7/resolver/src/main/java/org/apache/felix/resolver/Candidates.java (original) +++ felix/trunk/osgi-r7/resolver/src/main/java/org/apache/felix/resolver/Candidates.java Fri Feb 23 13:52:46 2018 @@ -1201,7 +1201,61 @@ class Candidates public boolean canRemoveCandidate(Requirement req) { CandidateSelector candidates = m_candidateMap.get(req); - return ((candidates != null) && (candidates.getRemainingCandidateCount() > 1 || Util.isOptional(req))); + if (candidates != null) + { + Capability current = candidates.getCurrentCandidate(); + if (current != null) + { + // IMPLEMENTATION NOTE: + // Here we check for a req that is used for a substitutable export. + // If we find a substitutable req then an extra check is done to see + // if the substitutable capability is currently depended on as the + // only provider of some other requirement. If it is then we do not + // allow the candidate to be removed. + // This is done because of the way we attempt to reduce permutations + // checked by permuting all used requirements that conflict with a + // directly imported/required capability in one go. + // If we allowed these types of substitutable requirements to move + // to the next capability then the permutation would be thrown out + // because it would cause some other resource to not resolve. + // That in turn would throw out the complete permutation along with + // any follow on permutations that could have resulted. + // See ResolverImpl::checkPackageSpaceConsistency + + // Check if the current candidate is substitutable by the req; + // This check is necessary here because of the way we traverse used blames + // allows multiple requirements to be permuted in one Candidates + if (req.equals(m_subtitutableMap.get(current))) + { + // this is a substitute req, + // make sure there is not an existing dependency that would fail if we substitute + Set<Requirement> dependents = m_dependentMap.get(current); + if (dependents != null) + { + for (Requirement dependent : dependents) + { + CandidateSelector dependentSelector = m_candidateMap.get( + dependent); + // If the dependent selector only has one capability left then check if + // the current candidate is the selector's current candidate. + if (dependentSelector != null + && dependentSelector.getRemainingCandidateCount() <= 1) + { + if (current.equals( + dependentSelector.getCurrentCandidate())) + { + // return false since we do not want to allow this requirement + // to substitute the capability + return false; + } + } + } + } + } + } + return candidates.getRemainingCandidateCount() > 1 || Util.isOptional(req); + } + return false; } static class DynamicImportFailed extends ResolutionError { Modified: felix/trunk/osgi-r7/resolver/src/main/java/org/apache/felix/resolver/ResolverImpl.java URL: http://svn.apache.org/viewvc/felix/trunk/osgi-r7/resolver/src/main/java/org/apache/felix/resolver/ResolverImpl.java?rev=1825128&r1=1825127&r2=1825128&view=diff ============================================================================== --- felix/trunk/osgi-r7/resolver/src/main/java/org/apache/felix/resolver/ResolverImpl.java (original) +++ felix/trunk/osgi-r7/resolver/src/main/java/org/apache/felix/resolver/ResolverImpl.java Fri Feb 23 13:52:46 2018 @@ -23,6 +23,8 @@ import java.util.*; import java.util.Map.Entry; import java.util.concurrent.*; import java.util.concurrent.atomic.AtomicInteger; +import java.util.concurrent.atomic.AtomicReference; + import org.apache.felix.resolver.util.ArrayMap; import org.apache.felix.resolver.util.CandidateSelector; import org.apache.felix.resolver.util.OpenHashMap; @@ -1308,8 +1310,6 @@ public class ResolverImpl implements Res Packages pkgs = resourcePkgMap.get(resource); ResolutionError rethrow = null; - Candidates permutation = null; - Set<Requirement> mutated = null; // Check for conflicting imports from fragments. // TODO: Is this only needed for imports or are generic and bundle requirements also needed? @@ -1351,6 +1351,16 @@ public class ResolverImpl implements Res } } } + // IMPLEMENTATION NOTE: + // Below we track the mutated reqs that have been permuted + // in a single candidates permutation. This permutation may contain a + // delta of several reqs which conflict with a directly imported/required candidates. + // When several reqs are permuted at the same time this reduces the number of solutions tried. + // See the method Candidates::canRemoveCandidate for a case where substitutions must be checked + // because of this code that may permute multiple reqs in on candidates permutation. + AtomicReference<Candidates> permRef1 = new AtomicReference<Candidates>(); + AtomicReference<Candidates> permRef2 = new AtomicReference<Candidates>(); + Set<Requirement> mutated = null; // Check if there are any uses conflicts with exported packages. for (Entry<String, Blame> entry : pkgs.m_exportedPkgs.fast()) @@ -1366,54 +1376,11 @@ public class ResolverImpl implements Res { if (!isCompatible(exportBlame, usedBlames.m_cap, resourcePkgMap)) { - for (Blame usedBlame : usedBlames.m_blames) - { - if (session.checkMultiple(usedBlames, usedBlame, allCandidates)) - { - // Continue to the next usedBlame, if possible we - // removed the conflicting candidates. - continue; - } - // Create a candidate permutation that eliminates all candidates - // that conflict with existing selected candidates. - permutation = (permutation != null) - ? permutation - : allCandidates.copy(); - if (rethrow == null) - { - rethrow = new UseConstraintError( - session.getContext(), allCandidates, resource, pkgName, usedBlame); - } - mutated = (mutated != null) + mutated = (mutated != null) ? mutated : new HashSet<Requirement>(); - - for (int reqIdx = usedBlame.m_reqs.size() - 1; reqIdx >= 0; reqIdx--) - { - Requirement req = usedBlame.m_reqs.get(reqIdx); - // Sanity check for multiple. - if (Util.isMultiple(req)) - { - continue; - } - // If we've already permutated this requirement in another - // uses constraint, don't permutate it again just continue - // with the next uses constraint. - if (mutated.contains(req)) - { - break; - } - - // See if we can permutate the candidates for blamed - // requirement; there may be no candidates if the resource - // associated with the requirement is already resolved. - if (permutation.canRemoveCandidate(req)) { - permutation.removeFirstCandidate(req); - mutated.add(req); - break; - } - } - } + rethrow = permuteUsedBlames(session, rethrow, allCandidates, resource, + pkgName, null, usedBlames, permRef1, permRef2, mutated); } } @@ -1421,7 +1388,8 @@ public class ResolverImpl implements Res { if (!mutated.isEmpty()) { - session.addPermutation(PermutationType.USES, permutation); + session.addPermutation(PermutationType.USES, permRef1.get()); + session.addPermutation(PermutationType.USES, permRef2.get()); } if (m_logger.isDebugEnabled()) { @@ -1463,60 +1431,12 @@ public class ResolverImpl implements Res { if (!isCompatible(requirementBlames, usedBlames.m_cap, resourcePkgMap)) { - // Split packages, need to think how to get a good message for split packages (sigh) + mutated = (mutated != null) + ? mutated + : new HashSet<Requirement>();// Split packages, need to think how to get a good message for split packages (sigh) // For now we just use the first requirement that brings in the package that conflicts Blame requirementBlame = requirementBlames.get(0); - for (Blame usedBlame : usedBlames.m_blames) - { - if (session.checkMultiple(usedBlames, usedBlame, allCandidates)) - { - // Continue to the next usedBlame, if possible we - // removed the conflicting candidates. - continue; - } - // Create a candidate permutation that eliminates all candidates - // that conflict with existing selected candidates. - permutation = (permutation != null) - ? permutation - : allCandidates.copy(); - if (rethrow == null) - { - rethrow = new UseConstraintError( - session.getContext(), allCandidates, - resource, pkgName, - requirementBlame, usedBlame); - } - - mutated = (mutated != null) - ? mutated - : new HashSet<Requirement>(); - - for (int reqIdx = usedBlame.m_reqs.size() - 1; reqIdx >= 0; reqIdx--) - { - Requirement req = usedBlame.m_reqs.get(reqIdx); - // Sanity check for multiple. - if (Util.isMultiple(req)) - { - continue; - } - // If we've already permutated this requirement in another - // uses constraint, don't permutate it again just continue - // with the next uses constraint. - if (mutated.contains(req)) - { - break; - } - - // See if we can permutate the candidates for blamed - // requirement; there may be no candidates if the resource - // associated with the requirement is already resolved. - if (permutation.canRemoveCandidate(req)) { - permutation.removeFirstCandidate(req); - mutated.add(req); - break; - } - } - } + rethrow = permuteUsedBlames(session, rethrow, allCandidates, resource, pkgName, requirementBlame, usedBlames, permRef1, permRef2, mutated); } // If there was a uses conflict, then we should add a uses @@ -1530,7 +1450,8 @@ public class ResolverImpl implements Res // Add uses permutation if we m_mutated any candidates. if (!mutated.isEmpty()) { - session.addPermutation(PermutationType.USES, permutation); + session.addPermutation(PermutationType.USES, permRef1.get()); + session.addPermutation(PermutationType.USES, permRef2.get()); } // Try to permutate the candidate for the original @@ -1598,7 +1519,99 @@ public class ResolverImpl implements Res } return null; } + + private ResolutionError permuteUsedBlames(ResolveSession session, + ResolutionError rethrow, Candidates allCandidates, Resource resource, + String pkgName, Blame requirementBlame, UsedBlames usedBlames, + AtomicReference<Candidates> permRef1, AtomicReference<Candidates> permRef2, + Set<Requirement> mutated) + { + for (Blame usedBlame : usedBlames.m_blames) + { + if (session.checkMultiple(usedBlames, usedBlame, allCandidates)) + { + // Continue to the next usedBlame, if possible we + // removed the conflicting candidates. + continue; + } + + if (rethrow == null) + { + if (requirementBlame == null) + { + rethrow = new UseConstraintError(session.getContext(), allCandidates, + resource, pkgName, usedBlame); + } + else + { + rethrow = new UseConstraintError(session.getContext(), allCandidates, + resource, pkgName, requirementBlame, usedBlame); + } + } + + // Create a candidate permutation that eliminates all candidates + // that conflict with existing selected candidates going from direct requirement -> root + Candidates perm1 = permRef1.get(); + if (perm1 == null) + { + perm1 = allCandidates.copy(); + permRef1.set(perm1); + } + for (int reqIdx = usedBlame.m_reqs.size() - 1; reqIdx >= 0; reqIdx--) + { + Requirement req = usedBlame.m_reqs.get(reqIdx); + if (permuteUsedBlameRequirement(req, mutated, perm1)) + { + break; + } + } + // Create a candidate permutation that eliminates all candidates + // that conflict with existing selected candidates going from root -> direct requirement + Candidates perm2 = permRef2.get(); + if (perm2 == null) + { + perm2 = allCandidates.copy(); + permRef2.set(perm2); + } + for (int reqIdx = 0; reqIdx < usedBlame.m_reqs.size(); reqIdx++) + { + Requirement req = usedBlame.m_reqs.get(reqIdx); + if (permuteUsedBlameRequirement(req, mutated, perm2)) + { + break; + } + } + } + return rethrow; + } + private boolean permuteUsedBlameRequirement(Requirement req, Set<Requirement> mutated, Candidates permutation) + { + // Sanity check for multiple. + if (Util.isMultiple(req)) + { + return false; + } + // If we've already permutated this requirement in another + // uses constraint, don't permutate it again just continue + // with the next uses constraint. + if (mutated.contains(req)) + { + return true; + } + + // See if we can permutate the candidates for blamed + // requirement; there may be no candidates if the resource + // associated with the requirement is already resolved. + if (permutation.canRemoveCandidate(req)) + { + permutation.removeFirstCandidate(req); + mutated.add(req); + return true; + } + return false; + } + private static OpenHashMap<String, Blame> calculateExportedPackages( ResolveSession session, Candidates allCandidates, Modified: felix/trunk/osgi-r7/resolver/src/main/java/org/osgi/service/resolver/ResolveContext.java URL: http://svn.apache.org/viewvc/felix/trunk/osgi-r7/resolver/src/main/java/org/osgi/service/resolver/ResolveContext.java?rev=1825128&r1=1825127&r2=1825128&view=diff ============================================================================== --- felix/trunk/osgi-r7/resolver/src/main/java/org/osgi/service/resolver/ResolveContext.java (original) +++ felix/trunk/osgi-r7/resolver/src/main/java/org/osgi/service/resolver/ResolveContext.java Fri Feb 23 13:52:46 2018 @@ -1,5 +1,5 @@ /* - * Copyright (c) OSGi Alliance (2011, 2016). All Rights Reserved. + * Copyright (c) OSGi Alliance (2011, 2017). All Rights Reserved. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -66,7 +66,7 @@ import org.osgi.resource.Wiring; * capabilities, wires and effective requirements. * * @ThreadSafe - * @author $Id: 887cb785c112f51b400164044b822c291d081bdb $ + * @author $Id: 5a3d32eb947b703bcca36f00d1ba6a86ae4a8e4b $ */ @ConsumerType public abstract class ResolveContext { Modified: felix/trunk/osgi-r7/resolver/src/main/java/org/osgi/service/resolver/Resolver.java URL: http://svn.apache.org/viewvc/felix/trunk/osgi-r7/resolver/src/main/java/org/osgi/service/resolver/Resolver.java?rev=1825128&r1=1825127&r2=1825128&view=diff ============================================================================== --- felix/trunk/osgi-r7/resolver/src/main/java/org/osgi/service/resolver/Resolver.java (original) +++ felix/trunk/osgi-r7/resolver/src/main/java/org/osgi/service/resolver/Resolver.java Fri Feb 23 13:52:46 2018 @@ -1,5 +1,5 @@ /* - * Copyright (c) OSGi Alliance (2006, 2016). All Rights Reserved. + * Copyright (c) OSGi Alliance (2006, 2017). All Rights Reserved. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -36,7 +36,7 @@ import org.osgi.resource.Wiring; * by the caller. * * @ThreadSafe - * @author $Id: 555f3cd1543e7a2c3492a71d74dcf728668265b6 $ + * @author $Id: 86bff007315e1e3c03eca6aaacdcfa379be9ddea $ */ @ProviderType public interface Resolver { @@ -77,13 +77,15 @@ public interface Resolver { Map<Resource, List<Wire>> resolve(ResolveContext context) throws ResolutionException; /** - * Resolves a given dynamic requirement dynamically for the given host - * wiring using the given resolve context and return any new resources and - * wires to the caller. + * Resolves a given requirement dynamically for the given host wiring using + * the given resolve context and return any new resources and wires to the + * caller. * <p> * The requirement must be a {@link Wiring#getResourceRequirements(String) * requirement} of the wiring and must use the - * {@link PackageNamespace#PACKAGE_NAMESPACE package} namespace. + * {@link PackageNamespace#PACKAGE_NAMESPACE package} namespace with a + * {@link Namespace#REQUIREMENT_RESOLUTION_DIRECTIVE resolution} of type + * {@link PackageNamespace#RESOLUTION_DYNAMIC dynamic}. * <p> * The resolve context is not asked for * {@link ResolveContext#getMandatoryResources() mandatory} resources or for Modified: felix/trunk/osgi-r7/resolver/src/test/java/org/apache/felix/resolver/test/ResolverTest.java URL: http://svn.apache.org/viewvc/felix/trunk/osgi-r7/resolver/src/test/java/org/apache/felix/resolver/test/ResolverTest.java?rev=1825128&r1=1825127&r2=1825128&view=diff ============================================================================== --- felix/trunk/osgi-r7/resolver/src/test/java/org/apache/felix/resolver/test/ResolverTest.java (original) +++ felix/trunk/osgi-r7/resolver/src/test/java/org/apache/felix/resolver/test/ResolverTest.java Fri Feb 23 13:52:46 2018 @@ -905,6 +905,14 @@ public class ResolverTest resolver.resolve(rci); } + @Test + public void testScenario18() throws Exception + { + ResolveContext rci = populateScenario18(); + ResolverImpl resolver = new ResolverImpl(new Logger(Logger.LOG_DEBUG), 1); + resolver.resolve(rci); + } + private ResolveContext populateScenario17(boolean realSubstitute, boolean felixResolveContext, boolean existingWirings) { @@ -999,6 +1007,91 @@ public class ResolverTest } } + private ResolveContext populateScenario18() + { + Map<Requirement, List<Capability>> candMap = new HashMap<Requirement, List<Capability>>(); + + ResourceImpl core1 = new ResourceImpl("core1"); + Capability core1_pkgCap1 = addCap(core1, PackageNamespace.PACKAGE_NAMESPACE, + "corepkg1"); + Capability core1_pkgCap2 = addCap(core1, PackageNamespace.PACKAGE_NAMESPACE, + "corepkg2", "corepkg1"); + Capability core1_pkgCap3 = addCap(core1, PackageNamespace.PACKAGE_NAMESPACE, + "corepkg3", "corepkg2"); + + ResourceImpl core2 = new ResourceImpl("core2"); + Capability core2_pkgCap1 = addCap(core2, PackageNamespace.PACKAGE_NAMESPACE, + "corepkg1"); + Capability core2_pkgCap2 = addCap(core2, PackageNamespace.PACKAGE_NAMESPACE, + "corepkg2", "corepkg1"); + Capability core2_pkgCap3 = addCap(core2, PackageNamespace.PACKAGE_NAMESPACE, + "corepkg3", "corepkg2"); + Requirement core2_pkgReq1 = addReq(core2, PackageNamespace.PACKAGE_NAMESPACE, + "corepkg1"); + Requirement core2_pkgReq2 = addReq(core2, PackageNamespace.PACKAGE_NAMESPACE, + "corepkg2"); + Requirement core2_pkgReq3 = addReq(core2, PackageNamespace.PACKAGE_NAMESPACE, + "corepkg3"); + + ResourceImpl core3 = new ResourceImpl("core3"); + Capability core3_pkgCap1 = addCap(core3, PackageNamespace.PACKAGE_NAMESPACE, + "corepkg1"); + Capability core3_pkgCap2 = addCap(core3, PackageNamespace.PACKAGE_NAMESPACE, + "corepkg2", "corepkg1"); + Capability core3_pkgCap3 = addCap(core3, PackageNamespace.PACKAGE_NAMESPACE, + "corepkg3", "corepkg2"); + Requirement core3_pkgReq1 = addReq(core3, PackageNamespace.PACKAGE_NAMESPACE, + "corepkg1"); + Requirement core3_pkgReq2 = addReq(core3, PackageNamespace.PACKAGE_NAMESPACE, + "corepkg2"); + Requirement core3_pkgReq3 = addReq(core3, PackageNamespace.PACKAGE_NAMESPACE, + "corepkg3"); + + ResourceImpl client1 = new ResourceImpl("client1"); + Capability client1_pkgCap = addCap(client1, PackageNamespace.PACKAGE_NAMESPACE, + "clientpkg1", "corepkg3"); + Requirement client1_pkgReq1 = addReq(client1, PackageNamespace.PACKAGE_NAMESPACE, + "corepkg3"); + + ResourceImpl client2 = new ResourceImpl("client2"); + Capability client2_pkgCap = addCap(client2, PackageNamespace.PACKAGE_NAMESPACE, + "clientpkg1", "corepkg3"); + Requirement client2_pkgReq1 = addReq(client2, PackageNamespace.PACKAGE_NAMESPACE, + "corepkg3"); + + ResourceImpl bundle1 = new ResourceImpl("bundle1"); + Requirement bundle1_pkgReq1 = addReq(bundle1, PackageNamespace.PACKAGE_NAMESPACE, + "corepkg1"); + Requirement bundle1_pkgReq2 = addReq(bundle1, PackageNamespace.PACKAGE_NAMESPACE, + "clientpkg1"); + + ResourceImpl bundle2 = new ResourceImpl("bundle2"); + Requirement bundle2_pkgReq1 = addReq(bundle2, PackageNamespace.PACKAGE_NAMESPACE, + "corepkg1"); + + candMap.put(core2_pkgReq1, Arrays.asList(core3_pkgCap1, core2_pkgCap1)); + candMap.put(core2_pkgReq2, Arrays.asList(core3_pkgCap2, core2_pkgCap2)); + candMap.put(core2_pkgReq3, Arrays.asList(core3_pkgCap3, core2_pkgCap3)); + + candMap.put(core3_pkgReq1, Arrays.asList(core3_pkgCap1, core2_pkgCap1)); + candMap.put(core3_pkgReq2, Arrays.asList(core3_pkgCap2, core2_pkgCap2)); + candMap.put(core3_pkgReq3, Arrays.asList(core3_pkgCap3, core2_pkgCap3)); + + candMap.put(client1_pkgReq1, + Arrays.asList(core3_pkgCap3, core2_pkgCap3, core1_pkgCap3)); + candMap.put(client2_pkgReq1, Arrays.asList(core3_pkgCap3)); + + candMap.put(bundle1_pkgReq1, Arrays.asList(core1_pkgCap1)); + candMap.put(bundle1_pkgReq2, Arrays.asList(client1_pkgCap)); + + candMap.put(bundle2_pkgReq1, Arrays.asList(core3_pkgCap1)); + + Collection<Resource> mandatory = Arrays.<Resource> asList(core1, core2, core3, + client1, client2, bundle1, bundle2); + return new ResolveContextImpl(Collections.<Resource, Wiring> emptyMap(), candMap, + mandatory, Collections.<Resource> emptyList()); + } + private static String getResourceName(Resource r) { return r.getCapabilities(IdentityNamespace.IDENTITY_NAMESPACE).get(0).getAttributes()