[FELIX-4942] Use depth-first search
git-svn-id: https://svn.apache.org/repos/asf/felix/trunk@1690733 13f79535-47bb-0310-9956-ffa450edef68
diff --git a/resolver/src/main/java/org/apache/felix/resolver/ResolverImpl.java b/resolver/src/main/java/org/apache/felix/resolver/ResolverImpl.java
index 7c3a696..481f0fb 100644
--- a/resolver/src/main/java/org/apache/felix/resolver/ResolverImpl.java
+++ b/resolver/src/main/java/org/apache/felix/resolver/ResolverImpl.java
@@ -211,6 +211,8 @@
// 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);
@@ -241,6 +243,10 @@
{
allCandidates = importPermutations.remove(0);
}
+ else if (!substPermutations.isEmpty())
+ {
+ allCandidates = substPermutations.remove(0);
+ }
else
{
break;
@@ -261,7 +267,7 @@
//allCandidates.dump();
- rethrow = allCandidates.checkSubstitutes(importPermutations);
+ rethrow = allCandidates.checkSubstitutes(substPermutations);
if (rethrow != null)
{
continue;
@@ -290,16 +296,23 @@
}
Map<Resource, ResolutionError> currentFaultyResources = new HashMap<Resource, ResolutionError>();
+
+ List<Candidates> newUses = new ArrayList<Candidates>();
+ List<Candidates> newImports = new ArrayList<Candidates>();
+
rethrow = checkConsistency(
executor,
session,
- usesPermutations,
- importPermutations,
+ newUses,
+ newImports,
allCandidates,
currentFaultyResources,
hosts,
false);
+ usesPermutations.addAll(0, newUses);
+ importPermutations.addAll(0, newImports);
+
if (!currentFaultyResources.isEmpty())
{
if (faultyResources == null)