Completely discard results from broken cycles to avoid erroneous resolver
results. (FELIX-1710)
git-svn-id: https://svn.apache.org/repos/asf/felix/trunk@823130 13f79535-47bb-0310-9956-ffa450edef68
diff --git a/framework/src/main/java/org/apache/felix/framework/searchpolicy/CandidateSet.java b/framework/src/main/java/org/apache/felix/framework/searchpolicy/CandidateSet.java
index 207490a..f16165c 100644
--- a/framework/src/main/java/org/apache/felix/framework/searchpolicy/CandidateSet.java
+++ b/framework/src/main/java/org/apache/felix/framework/searchpolicy/CandidateSet.java
@@ -18,39 +18,24 @@
*/
package org.apache.felix.framework.searchpolicy;
+import java.util.List;
import org.apache.felix.moduleloader.IModule;
import org.apache.felix.moduleloader.IRequirement;
class CandidateSet
{
public static final int NORMAL = 0;
- public static final int FRAGMENT = 1;
- public static final int HOST = 2;
- public final int m_type;
public final IModule m_module;
public final IRequirement m_requirement;
- public final PackageSource[] m_candidates;
- public final IModule[] m_modules;
+ public final List m_candidates;
public int m_idx = 0;
public int m_rotated = 0;
- public CandidateSet(int type, IModule module, IRequirement requirement, PackageSource[] candidates)
+ public CandidateSet(IModule module, IRequirement requirement, List candidates)
{
super();
- m_type = type;
m_module = module;
m_requirement = requirement;
m_candidates = candidates;
- m_modules = null;
}
-
- public CandidateSet(int type, IModule module, IRequirement requirement, IModule[] fragments)
- {
- super();
- m_type = type;
- m_module = module;
- m_requirement = requirement;
- m_candidates = null;
- m_modules = fragments;
- }
-}
+}
\ No newline at end of file
diff --git a/framework/src/main/java/org/apache/felix/framework/searchpolicy/Resolver.java b/framework/src/main/java/org/apache/felix/framework/searchpolicy/Resolver.java
index ea72017..e75ccef 100644
--- a/framework/src/main/java/org/apache/felix/framework/searchpolicy/Resolver.java
+++ b/framework/src/main/java/org/apache/felix/framework/searchpolicy/Resolver.java
@@ -19,6 +19,7 @@
package org.apache.felix.framework.searchpolicy;
import java.util.ArrayList;
+import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
@@ -89,7 +90,7 @@
// this map will be resolved, only the target module and
// any candidates selected to resolve its requirements and the
// transitive requirements this implies.
- populateCandidatesMap(state, candidatesMap, new HashMap(), null, rootModule);
+ populateCandidatesMap(state, candidatesMap, rootModule);
// The next step is to use the candidates map to determine if
// the class space for the root module is consistent. This
@@ -279,7 +280,7 @@
Map candidatesMap = new HashMap();
if (!provider.isResolved())
{
- populateCandidatesMap(state, candidatesMap, new HashMap(), null, provider);
+ populateCandidatesMap(state, candidatesMap, provider);
findConsistentClassSpace(state, candidatesMap, provider);
}
@@ -353,33 +354,12 @@
}
private void populateCandidatesMap(
- ResolverState state, Map candidatesMap, Map cycleByproductMap,
- IModule instigatingModule, IModule targetModule)
+ ResolverState state, Map candidatesMap, IModule targetModule)
throws ResolveException
{
// Detect cycles.
if (candidatesMap.containsKey(targetModule))
{
- // Check to see if we are really in a cyclical dependency so
- // we can add the instigating module to the target module's
- // byproduct map. We know we are in a cycle if the target module's
- // candidates map entry is null.
- if ((instigatingModule != null) && (candidatesMap.get(targetModule) == null))
- {
- IModule[] modules = (IModule[]) cycleByproductMap.get(targetModule);
- if (modules == null)
- {
- modules = new IModule[] { instigatingModule };
- }
- else
- {
- IModule[] tmp = new IModule[modules.length + 1];
- System.arraycopy(modules, 0, tmp, 0, modules.length);
- tmp[modules.length] = instigatingModule;
- modules = tmp;
- }
- cycleByproductMap.put(targetModule, modules);
- }
return;
}
@@ -409,26 +389,27 @@
// at the front of the list of candidates.
PackageSource[] resolved = state.getResolvedCandidates(reqs[reqIdx]);
PackageSource[] unresolved = state.getUnresolvedCandidates(reqs[reqIdx]);
- PackageSource[] candidates = new PackageSource[resolved.length + unresolved.length];
- System.arraycopy(resolved, 0, candidates, 0, resolved.length);
- System.arraycopy(unresolved, 0, candidates, resolved.length, unresolved.length);
+ PackageSource[] cand = new PackageSource[resolved.length + unresolved.length];
+ System.arraycopy(resolved, 0, cand, 0, resolved.length);
+ System.arraycopy(unresolved, 0, cand, resolved.length, unresolved.length);
+ List candidates = new ArrayList(Arrays.asList(cand));
// If we have candidates, then we need to recursively populate
// the resolver map with each of them.
ResolveException rethrow = null;
- if (candidates.length > 0)
+ if (candidates.size() > 0)
{
- for (int candIdx = 0; candIdx < candidates.length; candIdx++)
+ for (int candIdx = 0; candIdx < candidates.size(); candIdx++)
{
try
{
// Only populate the resolver map with modules that
// are not already resolved.
- if (!candidates[candIdx].m_module.isResolved())
+ if (!((PackageSource) candidates.get(candIdx)).m_module.isResolved())
{
populateCandidatesMap(
- state, candidatesMap, cycleByproductMap,
- targetModule, candidates[candIdx].m_module);
+ state, candidatesMap,
+ ((PackageSource) candidates.get(candIdx)).m_module);
}
}
catch (ResolveException ex)
@@ -437,27 +418,23 @@
// current candidate is not resolvable for some
// reason and should be removed from the list of
// candidates. For now, just null it.
- candidates[candIdx] = null;
+ candidates.remove(candIdx);
+ candIdx--;
rethrow = ex;
}
}
// Remove any nulled candidates to create the final list
// of available candidates.
- candidates = shrinkCandidateArray(candidates);
+// candidates = shrinkCandidateArray(candidates);
}
// If no candidates exist at this point, then throw a
// resolve exception unless the import is optional.
- if ((candidates.length == 0) && !reqs[reqIdx].isOptional())
+ if ((candidates.size() == 0) && !reqs[reqIdx].isOptional())
{
- // Since the target module cannot resolve, remove its
- // candidates set list from the candidates map, since
- // it is invalid.
- candidatesMap.remove(targetModule);
-
- // Also remove any cycle byproduct resolved modules.
- removeCycleByproducts(candidatesMap, cycleByproductMap, targetModule);
+ // Remove invalid candidate and any cycle byproduct resolved modules.
+ removeInvalidCandidate(targetModule, candidatesMap, new ArrayList());
// If we have received an exception while trying to populate
// the candidates map, rethrow that exception since it might
@@ -475,10 +452,10 @@
"Unable to resolve.", targetModule, reqs[reqIdx]);
}
}
- else if (candidates.length > 0)
+ else if (candidates.size() > 0)
{
candSetList.add(
- new CandidateSet(CandidateSet.NORMAL, targetModule, reqs[reqIdx], candidates));
+ new CandidateSet(targetModule, reqs[reqIdx], candidates));
}
}
@@ -488,16 +465,71 @@
candidatesMap.put(targetModule, candSetList);
}
- private static void removeCycleByproducts(
- Map candidatesMap, Map cycleByproductMap, IModule targetModule)
+ private static void removeInvalidCandidate(
+ IModule invalidModule, Map candidatesMap, List invalidList)
{
- IModule[] modules = (IModule[]) cycleByproductMap.remove(targetModule);
- if (modules != null)
+// TODO: PERFORMANCE - This could be quicker if we kept track of who depended on whom,
+// or only those modules used as candidates or those in a cycle.
+
+ // Remove the invalid module's candidates set list from the candidates map,
+ // since it should only contain entries for validly resolved modules.
+ candidatesMap.remove(invalidModule);
+
+ // Loop through each candidate set list in the candidates map to try
+ // to find references to the invalid module.
+ for (Iterator itCandidatesMap = candidatesMap.entrySet().iterator();
+ itCandidatesMap.hasNext(); )
{
- for (int i = 0; i < modules.length; i++)
+ Map.Entry entry = (Map.Entry) itCandidatesMap.next();
+ IModule module = (IModule) entry.getKey();
+ List candSetList = (List) entry.getValue();
+ if (candSetList != null)
{
- candidatesMap.remove(modules[i]);
- removeCycleByproducts(candidatesMap, cycleByproductMap, modules[i]);
+ // Loop through each candidate set in the candidate set list
+ // to search for the invalid module.
+ for (Iterator itCandSetList = candSetList.iterator(); itCandSetList.hasNext(); )
+ {
+ // Loop through the candidate in the candidate set and remove
+ // the invalid module if it is found.
+ CandidateSet cs = (CandidateSet) itCandSetList.next();
+ for (Iterator itCandidates = cs.m_candidates.iterator();
+ itCandidates.hasNext(); )
+ {
+ // If the invalid module is a candidate, then remove it from
+ // the candidate set.
+ PackageSource ps = (PackageSource) itCandidates.next();
+ if (ps.m_module.equals(invalidModule))
+ {
+ itCandidates.remove();
+
+ // If there are no more candidates in the candidate set, then
+ // remove it from the candidate set list.
+ if (cs.m_candidates.size() == 0)
+ {
+ itCandSetList.remove();
+
+ // If the requirement is not optional, then add the module
+ // to a list which will be removed after removing the current
+ // invalid module.
+ if (!cs.m_requirement.isOptional() && (module != invalidModule)
+ && !invalidList.contains(module))
+ {
+ invalidList.add(module);
+ }
+ }
+ break;
+ }
+ }
+ }
+ }
+ }
+
+ if (!invalidList.isEmpty())
+ {
+ while (!invalidList.isEmpty())
+ {
+ IModule m = (IModule) invalidList.remove(0);
+ removeInvalidCandidate(m, candidatesMap, invalidList);
}
}
}
@@ -570,9 +602,9 @@
for (int csIdx = 0; csIdx < candSetList.size(); csIdx++)
{
CandidateSet cs = (CandidateSet) candSetList.get(csIdx);
- if ((cs.m_candidates != null) && (cs.m_candidates.length > 1))
+ if ((cs.m_candidates != null) && (cs.m_candidates.size() > 1))
{
- weight += cs.m_candidates.length;
+ weight += cs.m_candidates.size();
}
}
return -weight;
@@ -867,16 +899,16 @@
// conflict, which in some cases will be smarter. Only
// rotate the candidates if we have more than one and we
// haven't already rotated them completely.
- if ((rp.m_cs != null) && (rp.m_cs.m_candidates.length > 1)
- && (rp.m_cs.m_rotated < rp.m_cs.m_candidates.length))
+ if ((rp.m_cs != null) && (rp.m_cs.m_candidates.size() > 1)
+ && (rp.m_cs.m_rotated < rp.m_cs.m_candidates.size()))
{
// Rotate candidates.
- PackageSource first = rp.m_cs.m_candidates[0];
- for (int i = 1; i < rp.m_cs.m_candidates.length; i++)
+ PackageSource first = (PackageSource) rp.m_cs.m_candidates.get(0);
+ for (int i = 1; i < rp.m_cs.m_candidates.size(); i++)
{
- rp.m_cs.m_candidates[i - 1] = rp.m_cs.m_candidates[i];
+ rp.m_cs.m_candidates.set(i - 1, rp.m_cs.m_candidates.get(i));
}
- rp.m_cs.m_candidates[rp.m_cs.m_candidates.length - 1] = first;
+ rp.m_cs.m_candidates.set(rp.m_cs.m_candidates.size() - 1, first);
rp.m_cs.m_rotated++;
m_candidatesRotated = true;
}
@@ -1080,7 +1112,7 @@
candSetIdx++)
{
CandidateSet cs = (CandidateSet) candSetList.get(candSetIdx);
- PackageSource ps = cs.m_candidates[cs.m_idx];
+ PackageSource ps = (PackageSource) cs.m_candidates.get(cs.m_idx);
if (ps.m_capability.getNamespace().equals(ICapability.PACKAGE_NAMESPACE))
{
@@ -1167,7 +1199,7 @@
candSetIdx++)
{
CandidateSet cs = (CandidateSet) candSetList.get(candSetIdx);
- PackageSource ps = cs.m_candidates[cs.m_idx];
+ PackageSource ps = (PackageSource) cs.m_candidates.get(cs.m_idx);
// If the capabaility is a module dependency, then flatten it to packages.
if (ps.m_capability.getNamespace().equals(ICapability.MODULE_NAMESPACE))
@@ -1283,7 +1315,7 @@
for (int candSetIdx = 0; candSetIdx < candSetList.size(); candSetIdx++)
{
CandidateSet cs = (CandidateSet) candSetList.get(candSetIdx);
- PackageSource ps = cs.m_candidates[cs.m_idx];
+ PackageSource ps = (PackageSource) cs.m_candidates.get(cs.m_idx);
// If the candidate is resolving a module dependency, then
// flatten the required packages if they are re-exported.
@@ -1517,7 +1549,7 @@
CandidateSet cs = (CandidateSet) candSetList.get(j);
// See if we can increment the candidate set, without overflowing
// the candidate array bounds.
- if ((cs.m_idx + 1) < cs.m_candidates.length)
+ if ((cs.m_idx + 1) < cs.m_candidates.size())
{
cs.m_idx++;
return;
@@ -1568,28 +1600,28 @@
moduleWires.add(new R4WireModule(
importer,
cs.m_requirement,
- cs.m_candidates[cs.m_idx].m_module,
- cs.m_candidates[cs.m_idx].m_capability,
+ ((PackageSource) cs.m_candidates.get(cs.m_idx)).m_module,
+ ((PackageSource) cs.m_candidates.get(cs.m_idx)).m_capability,
calculateCandidateRequiredPackages(
- importer, cs.m_candidates[cs.m_idx], candidatesMap)));
+ importer, (PackageSource) cs.m_candidates.get(cs.m_idx), candidatesMap)));
}
// Create a package wire for package dependencies.
// Filter out the case where a module imports from
// itself, since the module should simply load from
// its internal class path in this case.
- else if (importer != cs.m_candidates[cs.m_idx].m_module)
+ else if (importer != ((PackageSource) cs.m_candidates.get(cs.m_idx)).m_module)
{
// Add wire for imported package.
packageWires.add(new R4Wire(
importer,
cs.m_requirement,
- cs.m_candidates[cs.m_idx].m_module,
- cs.m_candidates[cs.m_idx].m_capability));
+ ((PackageSource) cs.m_candidates.get(cs.m_idx)).m_module,
+ ((PackageSource) cs.m_candidates.get(cs.m_idx)).m_capability));
}
// Create any necessary wires for the selected candidate module.
wireMap = populateWireMap(
- state, candidatesMap, cs.m_candidates[cs.m_idx].m_module, wireMap);
+ state, candidatesMap, ((PackageSource) cs.m_candidates.get(cs.m_idx)).m_module, wireMap);
}
packageWires.addAll(moduleWires);