felix-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From rickh...@apache.org
Subject svn commit: r935394 - in /felix/trunk/framework/src/main/java/org/apache/felix/framework: Felix.java ModuleImpl.java capabilityset/Requirement.java resolver/ResolverImpl.java util/manifestparser/ManifestParser.java util/manifestparser/RequirementImpl.java
Date Sun, 18 Apr 2010 19:22:48 GMT
Author: rickhall
Date: Sun Apr 18 19:22:48 2010
New Revision: 935394

URL: http://svn.apache.org/viewvc?rev=935394&view=rev
Log:
Rewrite of the new prototype resolver's core data structure and algorithm.
The code still needs a bit of cleaning, but this captures the nearly fully
working algorithm for safety before tinkering with it. (FELIX-2035,
FELIX-2036, FELIX-2037)

Modified:
    felix/trunk/framework/src/main/java/org/apache/felix/framework/Felix.java
    felix/trunk/framework/src/main/java/org/apache/felix/framework/ModuleImpl.java
    felix/trunk/framework/src/main/java/org/apache/felix/framework/capabilityset/Requirement.java
    felix/trunk/framework/src/main/java/org/apache/felix/framework/resolver/ResolverImpl.java
    felix/trunk/framework/src/main/java/org/apache/felix/framework/util/manifestparser/ManifestParser.java
    felix/trunk/framework/src/main/java/org/apache/felix/framework/util/manifestparser/RequirementImpl.java

Modified: felix/trunk/framework/src/main/java/org/apache/felix/framework/Felix.java
URL: http://svn.apache.org/viewvc/felix/trunk/framework/src/main/java/org/apache/felix/framework/Felix.java?rev=935394&r1=935393&r2=935394&view=diff
==============================================================================
--- felix/trunk/framework/src/main/java/org/apache/felix/framework/Felix.java (original)
+++ felix/trunk/framework/src/main/java/org/apache/felix/framework/Felix.java Sun Apr 18 19:22:48 2010
@@ -3043,7 +3043,7 @@ ex.printStackTrace();
         List<Directive> dirs = new ArrayList<Directive>(0);
         List<Attribute> attrs = new ArrayList<Attribute>(1);
         attrs.add(new Attribute(Capability.PACKAGE_ATTR, pkgName, false));
-        Requirement req = new RequirementImpl(Capability.PACKAGE_NAMESPACE, dirs, attrs);
+        Requirement req = new RequirementImpl(null, Capability.PACKAGE_NAMESPACE, dirs, attrs);
         Set<Capability> exports = m_resolverState.getCandidates(null, req, false);
 
         // We only want resolved capabilities.
@@ -3184,7 +3184,7 @@ ex.printStackTrace();
                         List<Attribute> attrs = new ArrayList<Attribute>(1);
                         attrs.add(new Attribute(Capability.PACKAGE_ATTR, pkgName, false));
                         Requirement req =
-                            new RequirementImpl(Capability.PACKAGE_NAMESPACE, dirs, attrs);
+                            new RequirementImpl(null, Capability.PACKAGE_NAMESPACE, dirs, attrs);
                         Set<Capability> exports = m_resolverState.getCandidates(null, req, false);
                         // We only want resolved capabilities.
                         for (Iterator<Capability> it = exports.iterator(); it.hasNext(); )
@@ -3356,7 +3356,7 @@ ex.printStackTrace();
                 throw new BundleException(
                     "Unresolved constraint in bundle " + b + ": "
                     + ((ex.getRequirement() == null)
-                        ? ex.getMessage() : ex.getRequirement().toString()));
+                        ? ex.getMessage() : ex.getMessage() + " - " + ex.getRequirement().toString()));
             }
             else
             {

Modified: felix/trunk/framework/src/main/java/org/apache/felix/framework/ModuleImpl.java
URL: http://svn.apache.org/viewvc/felix/trunk/framework/src/main/java/org/apache/felix/framework/ModuleImpl.java?rev=935394&r1=935393&r2=935394&view=diff
==============================================================================
--- felix/trunk/framework/src/main/java/org/apache/felix/framework/ModuleImpl.java (original)
+++ felix/trunk/framework/src/main/java/org/apache/felix/framework/ModuleImpl.java Sun Apr 18 19:22:48 2010
@@ -2085,7 +2085,7 @@ public class ModuleImpl implements Modul
             List<Attribute> attrs = new ArrayList(1);
             attrs.add(new Attribute(Capability.PACKAGE_ATTR, pkgName, false));
             Requirement req = new RequirementImpl(
-            Capability.PACKAGE_NAMESPACE, dirs, attrs);
+                module, Capability.PACKAGE_NAMESPACE, dirs, attrs);
             Set<Capability> exporters = resolver.getCandidates(module, req, false);
 
             Wire wire = null;
@@ -2124,7 +2124,7 @@ public class ModuleImpl implements Modul
         List<Attribute> attrs = new ArrayList(1);
         attrs.add(new Attribute(Capability.PACKAGE_ATTR, pkgName, false));
         Requirement req = new RequirementImpl(
-            Capability.PACKAGE_NAMESPACE, dirs, attrs);
+            module, Capability.PACKAGE_NAMESPACE, dirs, attrs);
         Set<Capability> exports = resolver.getCandidates(module, req, false);
         if (exports.size() > 0)
         {
@@ -2244,6 +2244,11 @@ public class ModuleImpl implements Modul
             return m_fragment;
         }
 
+        public Module getModule()
+        {
+            return m_req.getModule();
+        }
+
         public String getNamespace()
         {
             return m_req.getNamespace();

Modified: felix/trunk/framework/src/main/java/org/apache/felix/framework/capabilityset/Requirement.java
URL: http://svn.apache.org/viewvc/felix/trunk/framework/src/main/java/org/apache/felix/framework/capabilityset/Requirement.java?rev=935394&r1=935393&r2=935394&view=diff
==============================================================================
--- felix/trunk/framework/src/main/java/org/apache/felix/framework/capabilityset/Requirement.java (original)
+++ felix/trunk/framework/src/main/java/org/apache/felix/framework/capabilityset/Requirement.java Sun Apr 18 19:22:48 2010
@@ -19,9 +19,11 @@
 package org.apache.felix.framework.capabilityset;
 
 import java.util.List;
+import org.apache.felix.framework.resolver.Module;
 
 public interface Requirement
 {
+    Module getModule();
     String getNamespace();
     SimpleFilter getFilter();
     boolean isOptional();

Modified: felix/trunk/framework/src/main/java/org/apache/felix/framework/resolver/ResolverImpl.java
URL: http://svn.apache.org/viewvc/felix/trunk/framework/src/main/java/org/apache/felix/framework/resolver/ResolverImpl.java?rev=935394&r1=935393&r2=935394&view=diff
==============================================================================
--- felix/trunk/framework/src/main/java/org/apache/felix/framework/resolver/ResolverImpl.java (original)
+++ felix/trunk/framework/src/main/java/org/apache/felix/framework/resolver/ResolverImpl.java Sun Apr 18 19:22:48 2010
@@ -38,9 +38,6 @@ import org.apache.felix.framework.capabi
 import org.apache.felix.framework.util.manifestparser.RequirementImpl;
 import org.osgi.framework.Constants;
 
-// 1. Treat hard pkg constraints separately from implied package constraints
-// 2. Map pkg constraints to a set of capabilities, not a single capability.
-// 3. Uses constraints cannot conflict with other uses constraints, only with hard constraints.
 public class ResolverImpl implements Resolver
 {
     private final Logger m_logger;
@@ -60,7 +57,13 @@ public class ResolverImpl implements Res
         m_isInvokeCount = (v == null) ? false : Boolean.valueOf(v);
     }
 
-    private final List<Map<Requirement, Set<Capability>>> m_candidatePermutations =
+    // Holds candidate permutations based on permutating "uses" chains.
+    // These permutations are given higher priority.
+    private final List<Map<Requirement, Set<Capability>>> m_usesPermutations =
+        new ArrayList<Map<Requirement, Set<Capability>>>();
+    // Holds candidate permutations based on permutating requirement candidates.
+    // These permutations represent backtracking on previous decisions.
+    private final List<Map<Requirement, Set<Capability>>> m_importPermutations =
         new ArrayList<Map<Requirement, Set<Capability>>>();
 
     public Map<Module, List<Wire>> resolve(ResolverState state, Module module)
@@ -81,32 +84,42 @@ public class ResolverImpl implements Res
 
         if (!module.isResolved())
         {
-            m_candidatePermutations.clear();
+            m_usesPermutations.clear();
+            m_importPermutations.clear();
 
 //System.out.println("+++ RESOLVING " + module);
             Map<Requirement, Set<Capability>> candidateMap =
                 new HashMap<Requirement, Set<Capability>>();
 
             populateCandidates(state, module, candidateMap, new HashMap<Module, Object>());
-            m_candidatePermutations.add(candidateMap);
+            m_usesPermutations.add(candidateMap);
 
             ResolveException rethrow = null;
 
+            Map<Capability, Set<Requirement>> capDepSet = new HashMap();
+
             do
             {
                 rethrow = null;
 
-                candidateMap = m_candidatePermutations.remove(0);
+                modulePkgMap.clear();
+                capDepSet.clear();
+
+                candidateMap = (m_usesPermutations.size() > 0)
+                    ? m_usesPermutations.remove(0)
+                    : m_importPermutations.remove(0);
 //dumpCandidateMap(state, candidateMap);
 
+                calculatePackageSpaces(
+                    module, candidateMap, modulePkgMap, capDepSet, new HashSet());
+//System.out.println("+++ PACKAGE SPACES START +++");
+//dumpModulePkgMap(modulePkgMap);
+//System.out.println("+++ PACKAGE SPACES END +++");
+
                 try
                 {
-                    findConsistentCandidates(
-                        module,
-                        new ArrayList(),
-                        candidateMap,
-                        modulePkgMap,
-                        new HashMap<Module, Object>());
+                    checkPackageSpaceConsistency(
+                        module, candidateMap, modulePkgMap, capDepSet, new HashMap());
                 }
                 catch (ResolveException ex)
                 {
@@ -114,13 +127,13 @@ public class ResolverImpl implements Res
                     System.out.println("RE: " + ex);
                 }
             }
-            while ((rethrow != null) && (m_candidatePermutations.size() > 0));
+            while ((rethrow != null)
+                && ((m_usesPermutations.size() > 0) || (m_importPermutations.size() > 0)));
 
             if (rethrow != null)
             {
                 throw rethrow;
             }
-//dumpModulePkgMap(modulePkgMap);
 
             wireMap =
                 populateWireMap(module, modulePkgMap, wireMap,
@@ -160,31 +173,37 @@ public class ResolverImpl implements Res
             getDynamicImportCandidates(state, module, pkgName);
         if (candidateMap != null)
         {
-            m_candidatePermutations.clear();
+            m_usesPermutations.clear();
 
             Map<Module, List<Wire>> wireMap = new HashMap();
             Map<Module, Packages> modulePkgMap = new HashMap();
 
 //System.out.println("+++ DYNAMICALLY RESOLVING " + module + " - " + pkgName);
             populateDynamicCandidates(state, module, candidateMap);
-            m_candidatePermutations.add(candidateMap);
+            m_usesPermutations.add(candidateMap);
 
             ResolveException rethrow = null;
 
+            Map<Capability, Set<Requirement>> capDepSet = new HashMap();
+
             do
             {
                 rethrow = null;
 
-                candidateMap = m_candidatePermutations.remove(0);
-//dumpCandidateMap(state, candidateMap);
+                modulePkgMap.clear();
+                capDepSet.clear();
+
+                candidateMap = (m_usesPermutations.size() > 0)
+                    ? m_usesPermutations.remove(0)
+                    : m_importPermutations.remove(0);
+
+                calculateDynamicPackageSpaces(
+                    module, candidateMap, modulePkgMap, capDepSet);
 
                 try
                 {
-                    findConsistentDynamicCandidate(
-                        module,
-                        new ArrayList(),
-                        candidateMap,
-                        modulePkgMap);
+                    checkPackageSpaceConsistency(
+                        module, candidateMap, modulePkgMap, capDepSet, new HashMap());
                 }
                 catch (ResolveException ex)
                 {
@@ -192,7 +211,8 @@ public class ResolverImpl implements Res
                     System.out.println("RE: " + ex);
                 }
             }
-            while ((rethrow != null) && (m_candidatePermutations.size() > 0));
+            while ((rethrow != null)
+                && ((m_usesPermutations.size() > 0) || (m_importPermutations.size() > 0)));
 
             if (rethrow != null)
             {
@@ -259,7 +279,7 @@ public class ResolverImpl implements Res
         List<Attribute> attrs = new ArrayList(1);
         attrs.add(new Attribute(Capability.PACKAGE_ATTR, pkgName, false));
         Requirement req = new RequirementImpl(
-            Capability.PACKAGE_NAMESPACE, dirs, attrs);
+            module, Capability.PACKAGE_NAMESPACE, dirs, attrs);
         Set<Capability> candidates = state.getCandidates(module, req, false);
         List<Requirement> dynamics = module.getDynamicRequirements();
 
@@ -298,7 +318,6 @@ public class ResolverImpl implements Res
             candidates.clear();
         }
 
-
         if (candidates.size() > 0)
         {
             Map<Requirement, Set<Capability>> candidateMap = new HashMap();
@@ -322,7 +341,7 @@ public class ResolverImpl implements Res
                 Set<Capability> candidates = candidateMap.get(req);
                 if ((candidates != null) && (candidates.size() > 0))
                 {
-                    System.out.println("    " + req + ": " + candidates);
+                        System.out.println("    " + req + ": " + candidates);
                 }
             }
             for (Requirement req : module.getDynamicRequirements())
@@ -578,18 +597,19 @@ System.out.println("RE: Candidate not re
         // Add existing wires as candidates.
         for (Wire wire : module.getWires())
         {
+// TODO: FELIX3 - HOW ARE CAPABILITIES BEING SORTED NOW?
             Set<Capability> cs = new TreeSet();
             cs.add(wire.getCapability());
             candidateMap.put(wire.getRequirement(), cs);
         }
     }
 
-// TODO: FELIX3 - Modify to not be recursive.
-    private void findConsistentCandidates(
-        Module module, List<Requirement> incomingReqs,
+    private void calculatePackageSpaces(
+        Module module,
         Map<Requirement, Set<Capability>> candidateMap,
         Map<Module, Packages> modulePkgMap,
-        Map<Module, Object> resultCache)
+        Map<Capability, Set<Requirement>> capDepSet,
+        Set<Module> cycle)
     {
         if (m_isInvokeCount)
         {
@@ -598,83 +618,88 @@ System.out.println("RE: Candidate not re
             count = (count == null) ? new Long(1) : new Long(count.longValue() + 1);
             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 = resultCache.get(module);
-
-        if (o instanceof Boolean)
+        if (cycle.contains(module))
         {
             return;
         }
-        else if (o == null)
-        {
-            List list;
-            if (module.isResolved())
-            {
-                list = new ArrayList(module.getWires());
-            }
-            else
-            {
-                list = new ArrayList(module.getRequirements());
-            }
-            resultCache.put(module, o = new Object[] { cycleCount = new Integer(0), list });
-            calculateExportedPackages(module, incomingReqs, modulePkgMap);
-        }
-        else
-        {
-            // Increment and get the cycle count.
-            cycleCount = (Integer)
-                (((Object[]) o)[0]
-                    = new Integer(((Integer) ((Object[]) o)[0]).intValue() + 1));
-        }
-
-//System.out.println("+++ RESOLVING " + module);
+        cycle.add(module);
 
         if (module.isResolved())
         {
-            List<Wire> wires = (List<Wire>) ((Object[]) o)[1];
-
+            // First, add all exported packages to our package space.
+            calculateExportedPackages(module, modulePkgMap);
+            Packages modulePkgs = modulePkgMap.get(module);
+
+            // Second, add all imported packages to our candidate space.
+            List<Wire> wires = new ArrayList(module.getWires());
+            List<Capability> selected = new ArrayList();
             while (wires.size() > 0)
             {
                 Wire wire = wires.remove(0);
-
-                // Try to resolve the candidate.
-                findConsistentCandidates(
-                    wire.getCapability().getModule(),
-                    incomingReqs,
-                    candidateMap,
-                    modulePkgMap,
-                    resultCache);
-
-                // If we are here, the candidate was consistent. Try to
-                // merge the candidate into the target module's packages.
-                mergeCandidatePackages(
+                selected.add(wire.getCapability());
+                calculateExportedPackages(wire.getCapability().getModule(), modulePkgMap);
+                mergeCandidatePackagesNoUses(
                     module,
-                    incomingReqs,
+                    wire.getRequirement(),
                     wire.getCapability(),
                     modulePkgMap,
                     candidateMap);
+                addCapabilityDependency(wire.getCapability(), wire.getRequirement(), capDepSet);
+            }
+
+            // Third, ask our candidates to calculate their package space.
+            while (selected.size() > 0)
+            {
+                Capability candidate = selected.remove(0);
+                calculatePackageSpaces(candidate.getModule(), candidateMap, modulePkgMap, capDepSet, cycle);
+            }
+
+            // Fourth, add all of the uses constraints implied by our imported
+            // and required packages.
+            for (Entry<String, Blame> entry : modulePkgs.m_importedPkgs.entrySet())
+            {
+                List<Requirement> blameReqs = new ArrayList();
+                blameReqs.add(entry.getValue().m_reqs.get(0));
+
+                mergeUses(
+                    module,
+                    modulePkgs,
+                    entry.getValue().m_cap,
+                    blameReqs,
+                    modulePkgMap,
+                    candidateMap,
+                    new HashMap<String, List<Module>>());
+            }
+            for (Entry<String, List<Blame>> entry : modulePkgs.m_requiredPkgs.entrySet())
+            {
+                for (Blame blame : entry.getValue())
+                {
+                    List<Requirement> blameReqs = new ArrayList();
+                    blameReqs.add(blame.m_reqs.get(0));
+
+                    mergeUses(
+                        module,
+                        modulePkgs,
+                        blame.m_cap,
+                        blameReqs,
+                        modulePkgMap,
+                        candidateMap,
+                        new HashMap<String, List<Module>>());
+                }
             }
         }
         else
         {
-            List<Requirement> reqs = (List<Requirement>) ((Object[]) o)[1];
-
-            while (reqs.size() > 0)
+            // First, add all exported packages to our package space.
+            calculateExportedPackages(module, modulePkgMap);
+            Packages modulePkgs = modulePkgMap.get(module);
+
+            // Second, add all imported packages to our candidate space.
+            List<Requirement> list = new ArrayList(module.getRequirements());
+            List<Capability> selected = new ArrayList();
+            while (list.size() > 0)
             {
-                Requirement req = reqs.remove(0);
+                Requirement req = list.remove(0);
 
                 // Get the candidates for the current requirement.
                 Set<Capability> candCaps = candidateMap.get(req);
@@ -684,69 +709,64 @@ System.out.println("RE: Candidate not re
                     continue;
                 }
 
-                List<Requirement> outgoingReqs = new ArrayList<Requirement>(incomingReqs);
-                outgoingReqs.add(req);
+                calculateExportedPackages(module, modulePkgMap);
+                Capability candidate = candCaps.iterator().next();
+                selected.add(candidate);
+                calculateExportedPackages(candidate.getModule(), modulePkgMap);
+                mergeCandidatePackagesNoUses(module, req, candidate, modulePkgMap, candidateMap);
+                addCapabilityDependency(candidate, req, capDepSet);
+            }
 
-                for (Iterator<Capability> it = candCaps.iterator(); it.hasNext(); )
-                {
-                    Capability candCap = it.next();
-//System.out.println("+++ TRYING CAND " + candCap + " FOR " + req);
-                    try
-                    {
-                        // Try to resolve the candidate.
-                        findConsistentCandidates(
-                            candCap.getModule(),
-                            outgoingReqs,
-                            candidateMap,
-                            modulePkgMap,
-                            resultCache);
+            // Third, ask our candidates to calculate their package space.
+            while (selected.size() > 0)
+            {
+                Capability candidate = selected.remove(0);
+                calculatePackageSpaces(candidate.getModule(), candidateMap, modulePkgMap, capDepSet, cycle);
+            }
 
-                        // If we are here, the candidate was consistent. Try to
-                        // merge the candidate into the target module's packages.
-                        mergeCandidatePackages(
-                            module,
-                            outgoingReqs,
-                            candCap,
-                            modulePkgMap,
-                            candidateMap);
+            // Fourth, add all of the uses constraints implied by our imported
+            // and required packages.
+// TODO: FELIX3 - DUPLICATES CODE ABOVE FOR RESOLVED MODULES.
+            for (Entry<String, Blame> entry : modulePkgs.m_importedPkgs.entrySet())
+            {
+                List<Requirement> blameReqs = new ArrayList();
+                blameReqs.add(entry.getValue().m_reqs.get(0));
 
-                        // If we are here, we merged the candidate successfully,
-                        // so we can continue with the next requirement
-                        break;
-                    }
-                    catch (ResolveException ex)
-                    {
-//System.out.println("RE: " + ex);
-//ex.printStackTrace();
-                        // Remove the current candidate since it failed to resolve.
-                        it.remove();
-                        if (!it.hasNext() && !req.isOptional())
-                        {
-                            throw new ResolveException("Unresolved constraint "
-                                + req + " in " + module, module, req);
-                        }
-                    }
-                }
+                mergeUses(
+                    module,
+                    modulePkgs,
+                    entry.getValue().m_cap,
+                    blameReqs,
+                    modulePkgMap,
+                    candidateMap,
+                    new HashMap<String, List<Module>>());
             }
-        }
+            for (Entry<String, List<Blame>> entry : modulePkgs.m_requiredPkgs.entrySet())
+            {
+                for (Blame blame : entry.getValue())
+                {
+                    List<Requirement> blameReqs = new ArrayList();
+                    blameReqs.add(blame.m_reqs.get(0));
 
-        // If we are exiting from a cycle then decrement
-        // cycle counter, otherwise record the result.
-        if (cycleCount.intValue() > 0)
-        {
-            ((Object[]) o)[0] = new Integer(cycleCount.intValue() - 1);
-        }
-        else if (cycleCount.intValue() == 0)
-        {
-            // Record that the module was successfully populated.
-            resultCache.put(module, Boolean.TRUE);
+                    mergeUses(
+                        module,
+                        modulePkgs,
+                        blame.m_cap,
+                        blameReqs,
+                        modulePkgMap,
+                        candidateMap,
+                        new HashMap<String, List<Module>>());
+                }
+            }
         }
     }
 
-    private void findConsistentDynamicCandidate(
-        Module module, List<Requirement> incomingReqs,
+// TODO: FELIX3 - This code duplicates a lot of calculatePackageSpaces()
+    private void calculateDynamicPackageSpaces(
+        Module module,
         Map<Requirement, Set<Capability>> candidateMap,
-        Map<Module, Packages> modulePkgMap)
+        Map<Module, Packages> modulePkgMap,
+        Map<Capability, Set<Requirement>> capDepSet)
     {
         if (m_isInvokeCount)
         {
@@ -756,13 +776,18 @@ System.out.println("RE: Candidate not re
             m_invokeCounts.put(methodName, count);
         }
 
-//System.out.println("+++ RESOLVING " + module);
-        calculateExportedPackages(module, incomingReqs, modulePkgMap);
+        // First, add all exported packages to our package space.
+        calculateExportedPackages(module, modulePkgMap);
+        Packages modulePkgs = modulePkgMap.get(module);
 
+        // Second, add all imported packages to our candidate space.
         List<Requirement> reqs = new ArrayList(module.getRequirements());
         reqs.addAll(module.getDynamicRequirements());
-        for (Requirement req : reqs)
+        List<Capability> selected = new ArrayList();
+        while (reqs.size() > 0)
         {
+            Requirement req = reqs.remove(0);
+
             // Get the candidates for the current requirement.
             Set<Capability> candCaps = candidateMap.get(req);
             // Optional requirements may not have any candidates.
@@ -771,112 +796,61 @@ System.out.println("RE: Candidate not re
                 continue;
             }
 
-            List<Requirement> outgoingReqs = new ArrayList<Requirement>(incomingReqs);
-            outgoingReqs.add(req);
-
-            for (Iterator<Capability> it = candCaps.iterator(); it.hasNext(); )
-            {
-                Capability candCap = it.next();
-//System.out.println("+++ TRYING CAND " + candCap + " FOR " + req);
-                try
-                {
-                    // Try to resolve the candidate.
-                    findConsistentCandidates(
-                        candCap.getModule(),
-                        outgoingReqs,
-                        candidateMap,
-                        modulePkgMap,
-                        new HashMap());
-
-                    // If we are here, the candidate was consistent. Try to
-                    // merge the candidate into the target module's packages.
-                    mergeCandidatePackages(
-                        module,
-                        outgoingReqs,
-                        candCap,
-                        modulePkgMap,
-                        candidateMap);
-
-                    // If we are here, we merged the candidate successfully,
-                    // so we can continue with the next requirement
-                    break;
-                }
-                catch (ResolveException ex)
-                {
-System.out.println("RE: " + ex);
-ex.printStackTrace();
-                    // Remove the current candidate since it failed to resolve.
-                    it.remove();
-                    if (!it.hasNext() && !req.isOptional())
-                    {
-                        throw new ResolveException("Unresolved constraint "
-                            + req + " in " + module, module, req);
-                    }
-                }
-            }
+            calculateExportedPackages(module, modulePkgMap);
+            Capability candidate = candCaps.iterator().next();
+            selected.add(candidate);
+            calculateExportedPackages(candidate.getModule(), modulePkgMap);
+            mergeCandidatePackagesNoUses(module, req, candidate, modulePkgMap, candidateMap);
+            addCapabilityDependency(candidate, req, capDepSet);
+        }
+
+        // Third, ask our candidates to calculate their package space.
+        while (selected.size() > 0)
+        {
+            Capability candidate = selected.remove(0);
+            calculatePackageSpaces(
+                candidate.getModule(), candidateMap,
+                modulePkgMap, capDepSet, new HashSet());
+        }
+
+        // Fourth, add all of the uses constraints implied by our imported
+        // and required packages.
+        for (Entry<String, Blame> entry : modulePkgs.m_importedPkgs.entrySet())
+        {
+            List<Requirement> blameReqs = new ArrayList();
+            blameReqs.add(entry.getValue().m_reqs.get(0));
+
+            mergeUses(
+                module,
+                modulePkgs,
+                entry.getValue().m_cap,
+                blameReqs,
+                modulePkgMap,
+                candidateMap,
+                new HashMap<String, List<Module>>());
         }
-    }
-
-    private static void calculateExportedPackages(
-        Module module, List<Requirement> incomingReqs, Map<Module, Packages> modulePkgMap)
-    {
-        if (m_isInvokeCount)
+        for (Entry<String, List<Blame>> entry : modulePkgs.m_requiredPkgs.entrySet())
         {
-            String methodName = new Exception().fillInStackTrace().getStackTrace()[0].getMethodName();
-            Long count = m_invokeCounts.get(methodName);
-            count = (count == null) ? new Long(1) : new Long(count.longValue() + 1);
-            m_invokeCounts.put(methodName, count);
-        }
-
-        Packages packages = new Packages();
-
-        List<Capability> caps = module.getCapabilities();
-
-        if (caps.size() > 0)
-        {
-            for (int i = 0; i < caps.size(); i++)
+            for (Blame blame : entry.getValue())
             {
-// TODO: FELIX3 - Assume if a module imports the same package it
-//       exports that the import will overlap the export.
-                if (caps.get(i).getNamespace().equals(Capability.PACKAGE_NAMESPACE)
-                    && !hasOverlappingImport(module, caps.get(i)))
-                {
-                    packages.m_exportedPkgs.put(
-                        (String) caps.get(i).getAttribute(Capability.PACKAGE_ATTR).getValue(),
-                        new Blame(incomingReqs, caps.get(i)));
-                }
-            }
-        }
-
-        modulePkgMap.put(module, packages);
-    }
-
-    private static boolean hasOverlappingImport(Module module, Capability cap)
-    {
-        if (m_isInvokeCount)
-        {
-            String methodName = new Exception().fillInStackTrace().getStackTrace()[0].getMethodName();
-            Long count = m_invokeCounts.get(methodName);
-            count = (count == null) ? new Long(1) : new Long(count.longValue() + 1);
-            m_invokeCounts.put(methodName, count);
-        }
+                List<Requirement> blameReqs = new ArrayList();
+                blameReqs.add(blame.m_reqs.get(0));
 
-        List<Requirement> reqs = module.getRequirements();
-        for (int i = 0; i < reqs.size(); i++)
-        {
-            if (reqs.get(i).getNamespace().equals(Capability.PACKAGE_NAMESPACE)
-                && CapabilitySet.matches(cap, reqs.get(i).getFilter()))
-            {
-                return true;
+                mergeUses(
+                    module,
+                    modulePkgs,
+                    blame.m_cap,
+                    blameReqs,
+                    modulePkgMap,
+                    candidateMap,
+                    new HashMap<String, List<Module>>());
             }
         }
-        return false;
     }
 
-    private void mergeCandidatePackages(
-        Module current, List<Requirement> outgoingReqs,
-        Capability candCap, Map<Module, Packages> modulePkgMap,
-        Map<Requirement, Set<Capability>> candidateMap)
+    private void mergeCandidatePackagesNoUses(
+        Module current, Requirement currentReq, Capability candCap,
+        Map<Module, Packages> modulePkgMap, Map<Requirement, Set<Capability>> candidateMap)
     {
         if (m_isInvokeCount)
         {
@@ -888,11 +862,14 @@ ex.printStackTrace();
 
         if (candCap.getNamespace().equals(Capability.PACKAGE_NAMESPACE))
         {
-            mergeCandidatePackage(
-                current, false, new Blame(outgoingReqs, candCap), modulePkgMap, candidateMap);
+            mergeCandidatePackageNoUses(
+                current, false, currentReq, candCap, modulePkgMap);
         }
         else if (candCap.getNamespace().equals(Capability.MODULE_NAMESPACE))
         {
+// TODO: FELIX3 - THIS NEXT LINE IS A HACK. IMPROVE HOW/WHEN WE CALCULATE EXPORTS.
+            calculateExportedPackages(candCap.getModule(), modulePkgMap);
+
             // Get the candidate's package space to determine which packages
             // will be visible to the current module.
             Packages candPkgs = modulePkgMap.get(candCap.getModule());
@@ -901,12 +878,12 @@ ex.printStackTrace();
             // since the current module requires it.
             for (Entry<String, Blame> entry : candPkgs.m_exportedPkgs.entrySet())
             {
-                mergeCandidatePackage(
+                mergeCandidatePackageNoUses(
                     current,
                     true,
-                    new Blame(outgoingReqs, entry.getValue().m_cap),
-                    modulePkgMap,
-                    candidateMap);
+                    currentReq,
+                    entry.getValue().m_cap,
+                    modulePkgMap);
             }
 
             // If the candidate requires any other bundles with reexport visibility,
@@ -919,9 +896,9 @@ ex.printStackTrace();
                     if ((dir != null) && dir.getValue().equals(Constants.VISIBILITY_REEXPORT)
                         && (candidateMap.get(req) != null))
                     {
-                        mergeCandidatePackages(
+                        mergeCandidatePackagesNoUses(
                             current,
-                            outgoingReqs,
+                            currentReq,
                             candidateMap.get(req).iterator().next(),
                             modulePkgMap,
                             candidateMap);
@@ -931,10 +908,10 @@ ex.printStackTrace();
         }
     }
 
-    private void mergeCandidatePackage(
+    private void mergeCandidatePackageNoUses(
         Module current, boolean requires,
-        Blame candBlame, Map<Module, Packages> modulePkgMap,
-        Map<Requirement, Set<Capability>> candidateMap)
+        Requirement currentReq, Capability candCap,
+        Map<Module, Packages> modulePkgMap)
     {
         if (m_isInvokeCount)
         {
@@ -946,143 +923,64 @@ ex.printStackTrace();
 
 // TODO: FELIX3 - Check for merging where module imports from itself,
 //       then it should be listed as an export for requiring bundles.
-        if (candBlame.m_cap.getNamespace().equals(Capability.PACKAGE_NAMESPACE))
+        if (candCap.getNamespace().equals(Capability.PACKAGE_NAMESPACE))
         {
 //System.out.println("+++ MERGING " + candBlame.m_cap + " INTO " + current);
             String pkgName = (String)
-                candBlame.m_cap.getAttribute(Capability.PACKAGE_ATTR).getValue();
+                candCap.getAttribute(Capability.PACKAGE_ATTR).getValue();
 
             // Since this capability represents a package, it will become
             // a hard constraint on the module's package space, so we need
             // to make sure it doesn't conflict with any other hard constraints
             // or any other uses constraints.
 
+            List blameReqs = new ArrayList();
+            blameReqs.add(currentReq);
+
             //
             // First, check to see if the capability conflicts with
             // any existing hard constraints.
             //
 
             Packages currentPkgs = modulePkgMap.get(current);
-            Blame currentExportedBlame = currentPkgs.m_exportedPkgs.get(pkgName);
-            Blame currentImportedBlame = currentPkgs.m_importedPkgs.get(pkgName);
             List<Blame> currentRequiredBlames = currentPkgs.m_requiredPkgs.get(pkgName);
 
-            // We don't need to worry about an import conflicting with a required
-            // bundle's export, since imported package wires are terminal the
-            // bundle will never see the exported package from the required bundle.
-// TODO: FELIX3 - See scenario 21, this seems odd.
-            if (!requires &&
-                (currentImportedBlame != null) && !currentImportedBlame.m_cap.equals(candBlame.m_cap))
-//            if (!requires &&
-//                (((currentExportedBlame != null) && !currentExportedBlame.m_cap.equals(candBlame.m_cap))
-//                || ((currentImportedBlame != null) && !currentImportedBlame.m_cap.equals(candBlame.m_cap))))
-//                || ((currentRequiredBlames != null) && !currentRequiredBlames.contains(candBlame))))
-            {
-                // Permutate the candidate map and throw a resolve exception.
-                // NOTE: This method ALWAYS throws an exception.
-                permutateCandidates(
-                    current,
-                    pkgName,
-                    currentImportedBlame,
-                    candBlame,
-                    candidateMap);
-            }
-
-            //
-            // Second, check to see if the capability conflicts with
-            // any existing uses constraints
-            //
-
-            Packages currentPkgsCopy = currentPkgs;
-
-            if (!current.isResolved())
-            {
-                List<Blame> currentUsedBlames = currentPkgs.m_usedPkgs.get(pkgName);
-                checkExistingUsesConstraints(
-                    current, pkgName, currentUsedBlames, candBlame, modulePkgMap, candidateMap);
-
-                //
-                // Last, check to see if any uses constraints implied by the
-                // candidate conflict with any of the existing hard constraints.
-                //
-
-                // For now, create a copy of the module's package space and
-                // add the current candidate to the imported packages.
-                currentPkgsCopy = new Packages(currentPkgs);
-            }
-
             if (requires)
             {
                 if (currentRequiredBlames == null)
                 {
                     currentRequiredBlames = new ArrayList<Blame>();
-                    currentPkgsCopy.m_requiredPkgs.put(pkgName, currentRequiredBlames);
+                    currentPkgs.m_requiredPkgs.put(pkgName, currentRequiredBlames);
                 }
-// TODO: FELIX3 - This is potentially modifying the original, we need to modify a copy.
-                currentRequiredBlames.add(candBlame);
+                currentRequiredBlames.add(new Blame(candCap, blameReqs));
             }
             else
             {
-                currentPkgsCopy.m_importedPkgs.put(pkgName, candBlame);
+// TODO: FELIX3 - We might need to make this a list, since fragments can add duplicates.
+                currentPkgs.m_importedPkgs.put(pkgName, new Blame(candCap, blameReqs));
             }
 
-            // Verify and merge the candidate's transitive uses constraints.
-            verifyAndMergeUses(
-                current,
-                currentPkgsCopy,
-                candBlame,
-                modulePkgMap,
-                candidateMap,
-                new HashMap<String, List<Module>>());
-
-            // If we are here, then there were no conflict, so we should update
-            // the module's package space.
-            if (!current.isResolved())
-            {
-                currentPkgs.m_exportedPkgs.putAll(currentPkgsCopy.m_exportedPkgs);
-                currentPkgs.m_importedPkgs.putAll(currentPkgsCopy.m_importedPkgs);
-                currentPkgs.m_requiredPkgs.putAll(currentPkgsCopy.m_requiredPkgs);
-                currentPkgs.m_usedPkgs.putAll(currentPkgsCopy.m_usedPkgs);
-            }
 //dumpModulePkgs(current, currentPkgs);
         }
     }
 
-    private void checkExistingUsesConstraints(
-        Module current, String pkgName, List<Blame> currentUsedBlames,
-        Blame candBlame, Map<Module, Packages> modulePkgMap,
-        Map<Requirement, Set<Capability>> candidateMap)
+    private static void addCapabilityDependency(
+        Capability cap, Requirement req, Map<Capability, Set<Requirement>> capDepSet)
     {
-        if (m_isInvokeCount)
+        Set<Requirement> reqs = capDepSet.get(cap);
+        if (reqs == null)
         {
-            String methodName = new Exception().fillInStackTrace().getStackTrace()[0].getMethodName();
-            Long count = m_invokeCounts.get(methodName);
-            count = (count == null) ? new Long(1) : new Long(count.longValue() + 1);
-            m_invokeCounts.put(methodName, count);
-        }
-
-        for (int i = 0; (currentUsedBlames != null) && (i < currentUsedBlames.size()); i++)
-        {
-//System.out.println("+++ CHECK " + candBlame + " IN EXISTING " + currentUsedBlames.get(i));
-            if (!isCompatible(currentUsedBlames.get(i).m_cap, candBlame.m_cap, modulePkgMap))
-            {
-                // Permutate the candidate map and throw a resolve exception.
-                // NOTE: This method ALWAYS throws an exception.
-                permutateCandidates(
-                    current,
-                    pkgName,
-                    currentUsedBlames.get(i),
-                    candBlame,
-                    candidateMap);
-            }
+            reqs = new HashSet();
+            capDepSet.put(cap, reqs);
         }
+        reqs.add(req);
     }
 
 // TODO: FELIX3 - We end up with duplicates in uses constraints,
 //       see scenario 2 for an example.
-    private void verifyAndMergeUses(
+    private static void mergeUses(
         Module current, Packages currentPkgs,
-        Blame candBlame, Map<Module, Packages> modulePkgMap,
+        Capability mergeCap, List<Requirement> blameReqs, Map<Module, Packages> modulePkgMap,
         Map<Requirement, Set<Capability>> candidateMap,
         Map<String, List<Module>> cycleMap)
     {
@@ -1094,9 +992,21 @@ ex.printStackTrace();
             m_invokeCounts.put(methodName, count);
         }
 
+        if (!mergeCap.getNamespace().equals(Capability.PACKAGE_NAMESPACE))
+        {
+            return;
+        }
+        // If the candidate module is the same as the current module,
+        // then we don't need to verify and merge the uses constraints
+        // since this will happen as we build up the package space.
+        else if (current == mergeCap.getModule())
+        {
+            return;
+        }
+
         // Check for cycles.
         String pkgName = (String)
-            candBlame.m_cap.getAttribute(Capability.PACKAGE_ATTR).getValue();
+            mergeCap.getAttribute(Capability.PACKAGE_ATTR).getValue();
         List<Module> list = cycleMap.get(pkgName);
         if ((list != null) && list.contains(current))
         {
@@ -1106,87 +1016,51 @@ ex.printStackTrace();
         list.add(current);
         cycleMap.put(pkgName, list);
 
-//System.out.println("+++ VERIFYING USES " + current + " FOR " + candBlame);
+//System.out.println("+++ MERGING USES " + current + " FOR " + candBlame);
         for (Capability candSourceCap : getPackageSources(
-            candBlame.m_cap, modulePkgMap, new ArrayList<Capability>(), new HashSet<Capability>()))
+            mergeCap, modulePkgMap, new ArrayList<Capability>(), new HashSet<Capability>()))
         {
             for (String usedPkgName : candSourceCap.getUses())
             {
-                Blame currentExportedBlame = currentPkgs.m_exportedPkgs.get(usedPkgName);
-                Blame currentImportedBlame = currentPkgs.m_importedPkgs.get(usedPkgName);
-// TODO: FELIX3 - What do we do with required packages?
-                List<Blame> currentRequiredBlames = currentPkgs.m_requiredPkgs.get(usedPkgName);
-
                 Packages candSourcePkgs = modulePkgMap.get(candSourceCap.getModule());
-//System.out.println("+++ candSourceCap " + candSourceCap);
-//System.out.println("+++ candSourceCap.getModule() " + candSourceCap.getModule() + " (" + candSourceCap.getModule().isResolved() + ")");
-//System.out.println("+++ candSourcePkgs " + candSourcePkgs);
-//System.out.println("+++ candSourcePkgs.m_exportedPkgs " + candSourcePkgs.m_exportedPkgs);
                 Blame candSourceBlame = candSourcePkgs.m_exportedPkgs.get(usedPkgName);
                 candSourceBlame = (candSourceBlame != null)
                     ? candSourceBlame
                     : candSourcePkgs.m_importedPkgs.get(usedPkgName);
-//                sourceCap = (sourceCap != null)
-//                    ? sourceCap
-//                    : sourcePkgs.m_requiredPkgs.get(usedPkgName);
-
-                // If the candidate doesn't actually have a constraint for
-                // the used package, then just ignore it since this is likely
-                // an error in its metadata.
+
                 if (candSourceBlame == null)
                 {
-                    return;
+                    continue;
                 }
 
-                // If there is no current mapping for this package, then
-                // we can just return.
-                if ((currentExportedBlame == null)
-                    && (currentImportedBlame == null)
-                    && (currentRequiredBlames == null))
+                List<Blame> usedCaps = currentPkgs.m_usedPkgs.get(usedPkgName);
+                if (usedCaps == null)
                 {
-                    List<Blame> usedCaps = currentPkgs.m_usedPkgs.get(usedPkgName);
-                    if (usedCaps == null)
-                    {
-                        usedCaps = new ArrayList<Blame>();
-                        currentPkgs.m_usedPkgs.put(usedPkgName, usedCaps);
-                    }
-//System.out.println("+++ MERGING CB " + candBlame + " SB " + candSourceBlame);
-//                    usedCaps.add(new Blame(candBlame.m_reqs, sourceBlame.m_cap));
-                    usedCaps.add(candSourceBlame);
-//                    return;
+                    usedCaps = new ArrayList<Blame>();
+                    currentPkgs.m_usedPkgs.put(usedPkgName, usedCaps);
                 }
-                else if (!current.isResolved())
+                if (candSourceBlame.m_reqs != null)
                 {
-                    if ((currentExportedBlame != null)
-                        && !isCompatible(currentExportedBlame.m_cap, candSourceBlame.m_cap, modulePkgMap))
-                    {
-                        throw new ResolveException(
-                            "Constraint violation for package '" + usedPkgName
-                            + "' when resolving module " + current
-                            + " between existing constraint "
-                            + currentExportedBlame
-                            + " and candidate constraint "
-                            + candSourceBlame, null, null);
-                    }
-                    else if ((currentImportedBlame != null)
-                        && !isCompatible(currentImportedBlame.m_cap, candSourceBlame.m_cap, modulePkgMap))
-                    {
-                        permutateCandidates(
-                            current, usedPkgName, currentImportedBlame,
-                            candSourceBlame, candidateMap);
-                    }
+                    List<Requirement> blameReqs2 = new ArrayList(blameReqs);
+                    blameReqs2.add(candSourceBlame.m_reqs.get(candSourceBlame.m_reqs.size() - 1));
+                    usedCaps.add(new Blame(candSourceBlame.m_cap, blameReqs2));
+                    mergeUses(current, currentPkgs, candSourceBlame.m_cap, blameReqs2,
+                        modulePkgMap, candidateMap, cycleMap);
+                }
+                else
+                {
+                    usedCaps.add(new Blame(candSourceBlame.m_cap, blameReqs));
+                    mergeUses(current, currentPkgs, candSourceBlame.m_cap, blameReqs,
+                        modulePkgMap, candidateMap, cycleMap);
                 }
-
-                verifyAndMergeUses(current, currentPkgs, candSourceBlame,
-                    modulePkgMap, candidateMap, cycleMap);
             }
         }
     }
 
-    private void permutateCandidates(
-        Module current, String pkgName, Blame currentBlame, Blame candBlame,
-        Map<Requirement, Set<Capability>> candidateMap)
-        throws ResolveException
+    private void checkPackageSpaceConsistency(
+        Module module, Map<Requirement, Set<Capability>> candidateMap,
+        Map<Module, Packages> modulePkgMap, Map<Capability, Set<Requirement>> capDepSet,
+        Map<Module, Object> resultCache)
     {
         if (m_isInvokeCount)
         {
@@ -1196,73 +1070,235 @@ ex.printStackTrace();
             m_invokeCounts.put(methodName, count);
         }
 
-// TODO: FELIX3 - I think permutation is not as efficient as it could be, since
-//       the check for subsets is costly.
+        if (module.isResolved())
+        {
+            return;
+        }
+        else if (resultCache.containsKey(module))
+        {
+            return;
+        }
+
+//System.out.println("+++ checkPackageSpaceConsistency(" + module + ")");
+        Packages pkgs = modulePkgMap.get(module);
+
+        ResolveException rethrow = null;
+        Map<Requirement, Set<Capability>> copyConflict = null;
+        Set<Requirement> mutated = null;
+
+        Set<Module> checkModules = new HashSet();
+
+        for (Entry<String, Blame> entry : pkgs.m_exportedPkgs.entrySet())
+        {
+            String pkgName = entry.getKey();
+            if (!pkgs.m_usedPkgs.containsKey(pkgName))
+            {
+                continue;
+            }
+            for (Blame blame : pkgs.m_usedPkgs.get(pkgName))
+            {
+                if (!isCompatible(entry.getValue().m_cap, blame.m_cap, modulePkgMap))
+                {
+                    copyConflict = (copyConflict != null)
+                        ? copyConflict
+                        : copyCandidateMap(candidateMap);
+                    rethrow = (rethrow != null)
+                        ? rethrow
+                        : new ResolveException(
+                            "3Constraint violation for package '"
+                            + pkgName + "' when resolving module "
+                            + module + " between existing exported constraint "
+                            + entry.getValue() + " and uses constraint "
+                            + blame, null, null);
+                    mutated = (mutated != null)
+                        ? mutated
+                        : new HashSet();
+// TODO: FELIX3 - I think we need to walk up this chain too.
+// TODO: FELIX3 - What about uses and import permutations?
+                    Requirement req = blame.m_reqs.get(blame.m_reqs.size() - 1);
+                    if (!mutated.contains(req))
+                    {
+                        mutated.add(req);
+                        Set<Capability> caps = copyConflict.get(req);
+                        Iterator it = caps.iterator();
+                        it.next();
+                        it.remove();
+                        if (caps.size() == 0)
+                        {
+                            removeInvalidateCandidate(req.getModule(), capDepSet, copyConflict);
+                        }
+                    }
+                }
+            }
+            if (rethrow != null)
+            {
+                m_usesPermutations.add(copyConflict);
+                throw rethrow;
+            }
+        }
+
+        // Check if there are any conflicts with imported packages.
+        for (Entry<String, Blame> entry : pkgs.m_importedPkgs.entrySet())
+        {
+            if (!module.equals(entry.getValue().m_cap.getModule()))
+            {
+                checkModules.add(entry.getValue().m_cap.getModule());
+            }
 
-        // 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 for each blamed requirement.
-            for (int reqIdx = 0; reqIdx < currentBlame.m_reqs.size(); reqIdx++)
-            {
-                // 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++)
+            String pkgName = entry.getKey();
+            if (!pkgs.m_usedPkgs.containsKey(pkgName))
+            {
+                continue;
+            }
+            for (Blame blame : pkgs.m_usedPkgs.get(pkgName))
+            {
+                if (!isCompatible(entry.getValue().m_cap, blame.m_cap, modulePkgMap))
+                {
+                    // Create a candidate permutation that eliminates any candidates
+                    // that conflict with existing selected candidates.
+                    copyConflict = (copyConflict != null)
+                        ? copyConflict
+                        : copyCandidateMap(candidateMap);
+                    rethrow = (rethrow != null)
+                        ? rethrow
+                        : new ResolveException(
+                            "4Constraint violation for package '"
+                            + pkgName + "' when resolving module "
+                            + module + " between existing imported constraint "
+                            + entry.getValue() + " and uses constraint "
+                            + blame, null, null);
+
+                    mutated = (mutated != null)
+                        ? mutated
+                        : new HashSet();
+
+                    for (int reqIdx = blame.m_reqs.size() - 1; reqIdx >= 0; reqIdx--)
                     {
-                        if (isSubsetPermutation(m_candidatePermutations.get(permIdx), copy))
+                        Requirement req = blame.m_reqs.get(reqIdx);
+
+                        // 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 module
+                        // associated with the requirement is already resolved.
+                        Set<Capability> candidates = copyConflict.get(req);
+                        if ((candidates != null) && (candidates.size() > 1))
                         {
-                            isSubset = true;
+                            mutated.add(req);
+                            Iterator it = candidates.iterator();
+                            it.next();
+                            it.remove();
+                            // Continue with the next uses constraint.
+                            break;
                         }
                     }
-                    if (!isSubset)
+                }
+            }
+
+            if (rethrow != null)
+            {
+                // If we couldn't permutate the uses constraints,
+                // then try to permutate the import.
+// TODO: FELIX3 - Maybe we will push too many permutations this way, since
+//       we will push one on each level as we move down.
+                Requirement req = entry.getValue().m_reqs.get(0);
+                if (!mutated.contains(req))
+                {
+                    Set<Capability> candidates = candidateMap.get(req);
+                    if (candidates.size() > 1)
                     {
-//System.out.println("+++ SETTING "
-//    + currentBlame.m_reqs.get(reqIdx)
-//    + " CANDS FROM " + candidates + " TO " + candCopy);
-                        m_candidatePermutations.add(0, copy);
+                        Map<Requirement, Set<Capability>> importPerm =
+                            copyCandidateMap(candidateMap);
+                        candidates = importPerm.get(req);
+                        Iterator it = candidates.iterator();
+                        it.next();
+                        it.remove();
+System.out.println("+++ ADDING IMPORT PERM " + req);
+                        m_importPermutations.add(importPerm);
                     }
                 }
+
+                if (mutated.size() > 0)
+                {
+System.out.println("+++ ADDING CONFLICT PERM " + mutated);
+                    m_usesPermutations.add(copyConflict);
+                }
+
+                throw rethrow;
             }
         }
 
-        throw new ResolveException(
-            "Constraint violation for package '"
-            + pkgName + "' when resolving module "
-            + current + " between existing constraint "
-            + currentBlame + " and candidate constraint "
-            + candBlame, null, null);
+        resultCache.put(module, Boolean.TRUE);
+
+        // Now check the consistency of all modules on which the
+        // current module depends.
+        for (Module m : checkModules)
+        {
+            checkPackageSpaceConsistency(m, candidateMap, modulePkgMap, capDepSet, resultCache);
+        }
     }
 
-    private static boolean isSubsetPermutation(
-        Map<Requirement, Set<Capability>> orig, Map<Requirement, Set<Capability>> copy)
+    private void removeInvalidateCandidate(
+        Module invalid, Map<Capability, Set<Requirement>> capDepSet,
+        Map<Requirement, Set<Capability>> candidateMap)
+    {
+System.out.println("+++ REMOVING INVALID CANDIDATE: " + invalid + ":" + invalid.getSymbolicName());
+        Set<Module> invalidated = new HashSet();
+
+        for (Requirement req : invalid.getRequirements())
+        {
+            candidateMap.remove(req);
+        }
+
+        boolean wasRequired = false;
+
+        for (Capability cap : invalid.getCapabilities())
+        {
+            Set<Requirement> reqs = capDepSet.remove(cap);
+            if (reqs == null)
+            {
+                continue;
+            }
+            wasRequired = true;
+            for (Requirement req : reqs)
+            {
+                Set<Capability> candidates = candidateMap.get(req);
+                if (candidates != null)
+                {
+                    candidates.remove(cap);
+                    if (candidates.size() == 0)
+                    {
+                        candidateMap.remove(req);
+                        invalidated.add(req.getModule());
+                    }
+                }
+                else
+                {
+                    System.out.println("+++ INVALIDATED REQ WITH NULL CAPS: " + req);
+                }
+            }
+        }
+
+        if (!wasRequired)
+        {
+            throw new ResolveException(
+                "Unable to resolve module", invalid, null);
+        }
+
+        for (Module m : invalidated)
+        {
+            removeInvalidateCandidate(m, capDepSet, candidateMap);
+        }
+    }
+
+    private static void calculateExportedPackages(
+        Module module, Map<Module, Packages> modulePkgMap)
     {
         if (m_isInvokeCount)
         {
@@ -1272,19 +1308,54 @@ ex.printStackTrace();
             m_invokeCounts.put(methodName, count);
         }
 
-        for (Entry<Requirement, Set<Capability>> entry : orig.entrySet())
+        Packages packages = modulePkgMap.get(module);
+        if (packages != null)
         {
-            Set<Capability> copyCands = copy.get(entry.getKey());
-            if (copyCands == null)
+            return;
+        }
+        packages = new Packages();
+
+        List<Capability> caps = module.getCapabilities();
+
+        if (caps.size() > 0)
+        {
+            for (int i = 0; i < caps.size(); i++)
             {
-                return false;
+// TODO: FELIX3 - Assume if a module imports the same package it
+//       exports that the import will overlap the export.
+                if (caps.get(i).getNamespace().equals(Capability.PACKAGE_NAMESPACE)
+                    && !hasOverlappingImport(module, caps.get(i)))
+                {
+                    packages.m_exportedPkgs.put(
+                        (String) caps.get(i).getAttribute(Capability.PACKAGE_ATTR).getValue(),
+                        new Blame(caps.get(i), null));
+                }
             }
-            if (!entry.getValue().containsAll(copyCands))
+        }
+
+        modulePkgMap.put(module, packages);
+    }
+
+    private static boolean hasOverlappingImport(Module module, Capability cap)
+    {
+        if (m_isInvokeCount)
+        {
+            String methodName = new Exception().fillInStackTrace().getStackTrace()[0].getMethodName();
+            Long count = m_invokeCounts.get(methodName);
+            count = (count == null) ? new Long(1) : new Long(count.longValue() + 1);
+            m_invokeCounts.put(methodName, count);
+        }
+
+        List<Requirement> reqs = module.getRequirements();
+        for (int i = 0; i < reqs.size(); i++)
+        {
+            if (reqs.get(i).getNamespace().equals(Capability.PACKAGE_NAMESPACE)
+                && CapabilitySet.matches(cap, reqs.get(i).getFilter()))
             {
-                return false;
+                return true;
             }
         }
-        return true;
+        return false;
     }
 
     private static boolean isCompatible(
@@ -1300,6 +1371,11 @@ ex.printStackTrace();
 
         if ((currentCap != null) && (candCap != null))
         {
+            if (currentCap.equals(candCap))
+            {
+                return true;
+            }
+
             List<Capability> currentSources =
                 getPackageSources(
                     currentCap,
@@ -1489,7 +1565,7 @@ ex.printStackTrace();
                         // We need an unique requirement here or else subsequent
                         // dynamic imports for the same dynamic requirement will
                         // conflict with previous ones.
-                        new RequirementImpl(Capability.PACKAGE_NAMESPACE, new ArrayList(0), attrs),
+                        new RequirementImpl(module, Capability.PACKAGE_NAMESPACE, new ArrayList(0), attrs),
                         entry.getValue().m_cap.getModule(),
                         entry.getValue().m_cap));
             }
@@ -1552,22 +1628,22 @@ ex.printStackTrace();
 
     private static class Blame
     {
-        public final List<Requirement> m_reqs;
         public final Capability m_cap;
+        public final List<Requirement> m_reqs;
 
-        public Blame(List<Requirement> reqs, Capability cap)
+        public Blame(Capability cap, List<Requirement> reqs)
         {
-            m_reqs = reqs;
             m_cap = cap;
+            m_reqs = reqs;
         }
 
         public String toString()
         {
             return m_cap.getModule()
                 + "." + m_cap.getAttribute(Capability.PACKAGE_ATTR).getValue()
-                + ((m_reqs.size() == 0)
+                + (((m_reqs == null) || (m_reqs.size() == 0))
                     ? " NO BLAME"
-                    : " BLAMED ON " + m_reqs.get(m_reqs.size() - 1));
+                    : " BLAMED ON " + m_reqs);
         }
 
         public boolean equals(Object o)

Modified: felix/trunk/framework/src/main/java/org/apache/felix/framework/util/manifestparser/ManifestParser.java
URL: http://svn.apache.org/viewvc/felix/trunk/framework/src/main/java/org/apache/felix/framework/util/manifestparser/ManifestParser.java?rev=935394&r1=935393&r2=935394&view=diff
==============================================================================
--- felix/trunk/framework/src/main/java/org/apache/felix/framework/util/manifestparser/ManifestParser.java (original)
+++ felix/trunk/framework/src/main/java/org/apache/felix/framework/util/manifestparser/ManifestParser.java Sun Apr 18 19:22:48 2010
@@ -125,7 +125,7 @@ public class ManifestParser
         // Parse Fragment-Host.
         //
 
-        List<Requirement> hostReqs = parseFragmentHost(m_logger, m_headerMap);
+        List<Requirement> hostReqs = parseFragmentHost(m_logger, owner, m_headerMap);
 
         //
         // Parse Require-Bundle
@@ -134,7 +134,7 @@ public class ManifestParser
         List<ParsedHeaderClause> requireClauses =
             parseStandardHeader((String) headerMap.get(Constants.REQUIRE_BUNDLE));
         requireClauses = normalizeRequireClauses(m_logger, requireClauses, getManifestVersion());
-        List<Requirement> requireReqs = convertRequires(requireClauses);
+        List<Requirement> requireReqs = convertRequires(requireClauses, owner);
 
         //
         // Parse Import-Package.
@@ -143,7 +143,7 @@ public class ManifestParser
         List<ParsedHeaderClause> importClauses =
             parseStandardHeader((String) headerMap.get(Constants.IMPORT_PACKAGE));
         importClauses = normalizeImportClauses(m_logger, importClauses, getManifestVersion());
-        List<Requirement> importReqs = convertImports(importClauses);
+        List<Requirement> importReqs = convertImports(importClauses, owner);
 
         //
         // Parse DynamicImport-Package.
@@ -152,7 +152,7 @@ public class ManifestParser
         List<ParsedHeaderClause> dynamicClauses =
             parseStandardHeader((String) headerMap.get(Constants.DYNAMICIMPORT_PACKAGE));
         dynamicClauses = normalizeDynamicImportClauses(m_logger, dynamicClauses, getManifestVersion());
-        m_dynamicRequirements = convertImports(dynamicClauses);
+        m_dynamicRequirements = convertImports(dynamicClauses, owner);
 
         //
         // Parse Export-Package.
@@ -173,7 +173,7 @@ public class ManifestParser
         {
             List<ParsedHeaderClause> implicitClauses =
                 calculateImplicitImports(exportCaps, importClauses);
-            importReqs.addAll(convertImports(implicitClauses));
+            importReqs.addAll(convertImports(implicitClauses, owner));
 
             List<ParsedHeaderClause> allImportClauses =
                 new ArrayList<ParsedHeaderClause>(implicitClauses.size() + importClauses.size());
@@ -376,7 +376,8 @@ public class ManifestParser
         return clauses;
     }
 
-    private static List<Requirement> convertImports(List<ParsedHeaderClause> clauses)
+    private static List<Requirement> convertImports(
+        List<ParsedHeaderClause> clauses, Module owner)
     {
         // Now convert generic header clauses into requirements.
         List reqList = new ArrayList();
@@ -397,6 +398,7 @@ public class ManifestParser
                 // Create package requirement and add to requirement list.
                 reqList.add(
                     new RequirementImpl(
+                        owner,
                         Capability.PACKAGE_NAMESPACE,
                         clauses.get(clauseIdx).m_dirs,
                         newAttrs));
@@ -1113,7 +1115,8 @@ public class ManifestParser
         return null;
     }
 
-    private static List<Requirement> parseFragmentHost(Logger logger, Map headerMap)
+    private static List<Requirement> parseFragmentHost(
+        Logger logger, Module owner, Map headerMap)
         throws BundleException
     {
         List<Requirement> reqs = new ArrayList();
@@ -1164,7 +1167,8 @@ public class ManifestParser
                     clauses.get(0).m_paths.get(0), false));
                 newAttrs.addAll(attrs);
 
-                reqs.add(new RequirementImpl(Capability.HOST_NAMESPACE,
+                reqs.add(new RequirementImpl(
+                    owner, Capability.HOST_NAMESPACE,
                     clauses.get(0).m_dirs,
                     newAttrs));
             }
@@ -1262,7 +1266,8 @@ public class ManifestParser
         return clauses;
     }
 
-    private static List<Requirement> convertRequires(List<ParsedHeaderClause> clauses)
+    private static List<Requirement> convertRequires(
+        List<ParsedHeaderClause> clauses, Module owner)
     {
         List<Requirement> reqList = new ArrayList();
         for (int clauseIdx = 0; clauseIdx < clauses.size(); clauseIdx++)
@@ -1283,6 +1288,7 @@ public class ManifestParser
                 // Create package requirement and add to requirement list.
                 reqList.add(
                     new RequirementImpl(
+                        owner,
                         Capability.MODULE_NAMESPACE,
                         clauses.get(clauseIdx).m_dirs,
                         newAttrs));

Modified: felix/trunk/framework/src/main/java/org/apache/felix/framework/util/manifestparser/RequirementImpl.java
URL: http://svn.apache.org/viewvc/felix/trunk/framework/src/main/java/org/apache/felix/framework/util/manifestparser/RequirementImpl.java?rev=935394&r1=935393&r2=935394&view=diff
==============================================================================
--- felix/trunk/framework/src/main/java/org/apache/felix/framework/util/manifestparser/RequirementImpl.java (original)
+++ felix/trunk/framework/src/main/java/org/apache/felix/framework/util/manifestparser/RequirementImpl.java Sun Apr 18 19:22:48 2010
@@ -25,11 +25,13 @@ import org.apache.felix.framework.capabi
 import org.apache.felix.framework.capabilityset.Directive;
 import org.apache.felix.framework.capabilityset.Requirement;
 import org.apache.felix.framework.capabilityset.SimpleFilter;
+import org.apache.felix.framework.resolver.Module;
 import org.apache.felix.framework.util.VersionRange;
 import org.osgi.framework.Constants;
 
 public class RequirementImpl implements Requirement
 {
+    private final Module m_module;
     private final String m_namespace;
     private final SimpleFilter m_filter;
     private final boolean m_optional;
@@ -37,8 +39,10 @@ public class RequirementImpl implements 
     private final List<Directive> m_dirsConst;
 
     public RequirementImpl(
-        String namespace, List<Directive> dirs, List<Attribute> attrs)
+        Module module, String namespace,
+        List<Directive> dirs, List<Attribute> attrs)
     {
+        m_module = module;
         m_namespace = namespace;
         m_dirs = dirs;
         m_dirsConst = Collections.unmodifiableList(m_dirs);
@@ -56,6 +60,11 @@ public class RequirementImpl implements 
         m_optional = optional;
     }
 
+    public Module getModule()
+    {
+        return m_module;
+    }
+
     public String getNamespace()
     {
         return m_namespace;
@@ -90,7 +99,7 @@ public class RequirementImpl implements 
 
     public String toString()
     {
-        return m_namespace + "; " + getFilter().toString();
+        return "[" + m_module + "] " + m_namespace + "; " + getFilter().toString();
     }
 
     private static SimpleFilter convertToFilter(List<Attribute> attrs)



Mime
View raw message