You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@felix.apache.org by ri...@apache.org on 2010/03/21 08:40:52 UTC
svn commit: r925736 -
/felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/proto3/Proto3Resolver.java
Author: rickhall
Date: Sun Mar 21 07:40:52 2010
New Revision: 925736
URL: http://svn.apache.org/viewvc?rev=925736&view=rev
Log:
Align sandbox resolver with changes from trunk.
Modified:
felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/proto3/Proto3Resolver.java
Modified: felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/proto3/Proto3Resolver.java
URL: http://svn.apache.org/viewvc/felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/proto3/Proto3Resolver.java?rev=925736&r1=925735&r2=925736&view=diff
==============================================================================
--- felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/proto3/Proto3Resolver.java (original)
+++ felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/proto3/Proto3Resolver.java Sun Mar 21 07:40:52 2010
@@ -43,7 +43,6 @@ import org.apache.felix.resolver.cs.Capa
import org.apache.felix.resolver.cs.Directive;
import org.apache.felix.resolver.cs.Requirement;
import org.apache.felix.resolver.manifestparser.Constants;
-import org.apache.felix.resolver.manifestparser.Util;
// 1. Treat hard pkg constraints separately from implied package constraints
// 2. Map pkg constraints to a set of capabilities, not a single capability.
@@ -356,6 +355,7 @@ dumpCandidateMap(state, candidateMap);
}
}
+// TODO: FELIX3 - Modify to not be recursive.
private static void populateCandidates(
ResolverState state, Module module,
Map<Requirement, Set<Capability>> candidateMap,
@@ -378,9 +378,9 @@ dumpCandidateMap(state, candidateMap);
// 3. An array containing the cycle count, current map of candidates
// for already processed requirements, and a list of remaining
// requirements whose candidates still need to be calculated.
- // For case 1, rethrow the exception. For case 3, simply return immediately.
+ // For case 1, rethrow the exception. For case 2, simply return immediately.
// For case 3, this means we have a cycle so we should continue to populate
- // the candidate where we left off and not record any results globally
+ // the candidates where we left off and not record any results globally
// until we've popped completely out of the cycle.
// Keeps track of the number of times we've reentered this method
@@ -411,10 +411,13 @@ dumpCandidateMap(state, candidateMap);
// This is case 3.
else if (cacheValue != null)
{
- cycleCount = (Integer) ((Object[]) cacheValue)[0];
- ((Object[]) cacheValue)[0] = new Integer(cycleCount.intValue() + 1);
- cycleCount = (Integer) ((Object[]) cacheValue)[0];
+ // Increment and get the cycle count.
+ cycleCount = (Integer)
+ (((Object[]) cacheValue)[0]
+ = new Integer(((Integer) ((Object[]) cacheValue)[0]).intValue() + 1));
+ // Get the already populated candidates.
localCandidateMap = (Map) ((Object[]) cacheValue)[1];
+ // Get the remaining requirements.
remainingReqs = (List) ((Object[]) cacheValue)[2];
}
@@ -426,8 +429,8 @@ dumpCandidateMap(state, candidateMap);
// Record cycle count.
cycleCount = new Integer(0);
- // Store candidates in a local map first, just in case the module
- // is not resolvable.
+ // Create a local map for populating candidates first, just in case
+ // the module is not resolvable.
localCandidateMap = new HashMap();
// Create a modifiable list of the module's requirements.
@@ -559,11 +562,12 @@ System.out.println("RE: Candidate not re
}
}
+// TODO: FELIX3 - Modify to not be recursive.
private void findConsistentCandidates(
Module module, List<Requirement> incomingReqs,
Map<Requirement, Set<Capability>> candidateMap,
Map<Module, Packages> modulePkgMap,
- Map<Module, Object> cycleMap)
+ Map<Module, Object> resultCache)
{
if (m_isInvokeCount)
{
@@ -573,9 +577,20 @@ System.out.println("RE: Candidate not re
m_invokeCounts.put(methodName, count);
}
+ // Determine if we've already checked candidate consistency for this
+ // module. The result cache will have one of two values:
+ // 1. Boolean.TRUE if candidate consistency has been checked.
+ // 2. An array containing the cycle count and a list of wires for an
+ // already resolved (and consistent) module or a list of remaining
+ // requirments whose candidates still need to be checked for an
+ // unresolved module.
+ // For case 1, return immediately. For case 2, this means we are in a
+ // cycle so we should just continue checking consistency where we left
+ // off.
+
Integer cycleCount = null;
- Object o = cycleMap.get(module);
+ Object o = resultCache.get(module);
if (o instanceof Boolean)
{
@@ -592,14 +607,15 @@ System.out.println("RE: Candidate not re
{
list = new ArrayList(module.getRequirements());
}
- cycleMap.put(module, o = new Object[] { cycleCount = new Integer(0), list });
+ resultCache.put(module, o = new Object[] { cycleCount = new Integer(0), list });
calculateExportedPackages(module, incomingReqs, modulePkgMap);
}
else
{
- cycleCount = (Integer) ((Object[]) o)[0];
- ((Object[]) o)[0] = new Integer(cycleCount.intValue() + 1);
- cycleCount = (Integer) ((Object[]) o)[0];
+ // Increment and get the cycle count.
+ cycleCount = (Integer)
+ (((Object[]) o)[0]
+ = new Integer(((Integer) ((Object[]) o)[0]).intValue() + 1));
}
//System.out.println("+++ RESOLVING " + module);
@@ -618,7 +634,7 @@ System.out.println("RE: Candidate not re
incomingReqs,
candidateMap,
modulePkgMap,
- cycleMap);
+ resultCache);
// If we are here, the candidate was consistent. Try to
// merge the candidate into the target module's packages.
@@ -661,7 +677,7 @@ System.out.println("+++ TRYING CAND " +
outgoingReqs,
candidateMap,
modulePkgMap,
- cycleMap);
+ resultCache);
// If we are here, the candidate was consistent. Try to
// merge the candidate into the target module's packages.
@@ -705,7 +721,7 @@ ex.printStackTrace();
else if (cycleCount.intValue() == 0)
{
// Record that the module was successfully populated.
- cycleMap.put(module, Boolean.TRUE);
+ resultCache.put(module, Boolean.TRUE);
}
}
@@ -1142,36 +1158,9 @@ dumpModulePkgs(current, currentPkgs);
else if ((currentImportedBlame != null)
&& !isCompatible(currentImportedBlame.m_cap, candSourceBlame.m_cap, modulePkgMap))
{
-//System.out.println("+++ CIB " + currentImportedBlame + " SB " + sourceBlame);
- // Try to remove the previously selected candidate associated
- // with the requirement blamed for adding the constraint. This
- // Permutate the candidate map.
- if (currentImportedBlame.m_reqs.size() != 0)
- {
- // Permutate the candidate map.
- for (int reqIdx = 0; reqIdx < currentImportedBlame.m_reqs.size(); reqIdx++)
- {
- Map<Requirement, Set<Capability>> copy = copyCandidateMap(candidateMap);
- Set<Capability> candidates =
- copy.get(currentImportedBlame.m_reqs.get(reqIdx));
- Iterator it = candidates.iterator();
- it.next();
- it.remove();
-// TODO: PROTO3 RESOLVER - We could check before doing the candidate map copy.
- if (candidates.size() > 0)
- {
- m_candidatePermutations.add(copy);
- }
- }
- }
-
- throw new ResolveException(
- "Constraint violation for package '" + usedPkgName
- + "' when resolving module " + current
- + " between existing constraint "
- + currentImportedBlame
- + " and candidate constraint "
- + candSourceBlame, null, null);
+ permutateCandidates(
+ current, usedPkgName, currentImportedBlame,
+ candSourceBlame, candidateMap);
}
}
@@ -1186,27 +1175,65 @@ dumpModulePkgs(current, currentPkgs);
Map<Requirement, Set<Capability>> candidateMap)
throws ResolveException
{
- // Try to remove the previously selected candidate associated
- // with the requirement blamed for adding the constraint. This
- // blamed requirement may be null if the bundle itself is
- // exports the package imposing the uses constraint.
+// TODO: FELIX3 - I think permutation is not as efficient as it could be, since
+// the check for subsets is costly. Maybe we can just check if the candidates
+// for the blamed requirements are a subset, rather than computing the
+// entire permutation first.
+
+ // When we detect a conflict, we need to permutate the candidate map
+ // we when we try again, we'll select different candidates. To achieve
+ // this, we create a different permutation for each requirement in
+ // the set of blames requirements by eliminating the first candidate
+ // (i.e., the selected candidate) for each. We need to create an separate
+ // permutation for each blamed requirement to ensure we try all possible
+ // combination. This is a form of back tracking, since we eliminate each
+ // requirement's selected candidate, which will force them to choose
+ // another in the new permutation.
+ //
+ // The blamed requirement may be null if the bundle itself is exports
+ // the package imposing the uses constraint.
if ((currentBlame.m_reqs != null) && (currentBlame.m_reqs.size() != 0))
{
- // Permutate the candidate map.
+ // Permutate the candidate map for each blamed requirement.
for (int reqIdx = 0; reqIdx < currentBlame.m_reqs.size(); reqIdx++)
{
- Map<Requirement, Set<Capability>> copy = copyCandidateMap(candidateMap);
- Set<Capability> candidates = copy.get(currentBlame.m_reqs.get(reqIdx));
- Iterator it = candidates.iterator();
- it.next();
- it.remove();
- // TODO: PROTO3 RESOLVER - We could check before doing the candidate map copy.
- if (candidates.size() > 0)
- {
- m_candidatePermutations.add(copy);
+ // Verify whether we have more than one candidate to create
+ // a permutation.
+ Set<Capability> candidates = candidateMap.get(currentBlame.m_reqs.get(reqIdx));
+ if (candidates.size() > 1)
+ {
+ // Create a copy of the current candidate map and then remove
+ // the first (i.e., selected) candidate for the current
+ // blamed requirement.
+ Map<Requirement, Set<Capability>> copy = copyCandidateMap(candidateMap);
+ Set<Capability> candCopy = copy.get(currentBlame.m_reqs.get(reqIdx));
+ Iterator it = candCopy.iterator();
+ it.next();
+ it.remove();
+
+ // Check if the created permutation is a subset of a previously
+ // created permutation. If so, then we don't need to record it
+ // since it will be generated again when the superset permutation
+ // is processed.
+ boolean isSubset = false;
+ for (int permIdx = 0; !isSubset && (permIdx < m_candidatePermutations.size()); permIdx++)
+ {
+ if (isSubsetPermutation(m_candidatePermutations.get(permIdx), copy))
+ {
+ isSubset = true;
+ }
+ }
+ if (!isSubset)
+ {
+//System.out.println("+++ SETTING "
+// + currentBlame.m_reqs.get(reqIdx)
+// + " CANDS FROM " + candidates + " TO " + candCopy);
+ m_candidatePermutations.add(0, copy);
+ }
}
}
}
+
throw new ResolveException(
"Constraint violation for package '"
+ pkgName + "' when resolving module "
@@ -1215,6 +1242,24 @@ dumpModulePkgs(current, currentPkgs);
+ candBlame, null, null);
}
+ private static boolean isSubsetPermutation(
+ Map<Requirement, Set<Capability>> orig, Map<Requirement, Set<Capability>> copy)
+ {
+ for (Entry<Requirement, Set<Capability>> entry : orig.entrySet())
+ {
+ Set<Capability> copyCands = copy.get(entry.getKey());
+ if (copyCands == null)
+ {
+ return false;
+ }
+ if (!entry.getValue().containsAll(copyCands))
+ {
+ return false;
+ }
+ }
+ return true;
+ }
+
private static boolean isCompatible(
Capability currentCap, Capability candCap, Map<Module, Packages> modulePkgMap)
{
@@ -1310,7 +1355,7 @@ dumpModulePkgs(current, currentPkgs);
populateWireMap(cand.getModule(),
modulePkgMap, wireMap, candidateMap);
}
- // Ignore modules that import themselves.
+ // Ignore modules that import themselves.
if (req.getNamespace().equals(Capability.PACKAGE_NAMESPACE)
&& !module.equals(cand.getModule()))
{