Mailing-List: contact commits-help@felix.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@felix.apache.org
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: svn commit: r748595 - in
 /felix/trunk/framework/src/main/java/org/apache/felix/framework/searchpolicy:
 CandidateSet.java ResolvedPackage.java Resolver.java
Date: Fri, 27 Feb 2009 17:02:56 -0000
To: commits@felix.apache.org
From: rickhall@apache.org
Message-Id: <20090227170256.CE63D2388882@eris.apache.org>

Author: rickhall
Date: Fri Feb 27 17:02:56 2009
New Revision: 748595

URL: http://svn.apache.org/viewvc?rev=748595&view=rev
Log:
Modifed the resolver to try to be a little smarter in how it permutates
among potential candidates. (FELIX-961)

Added:
    felix/trunk/framework/src/main/java/org/apache/felix/framework/searchpolicy/CandidateSet.java
Modified:
    felix/trunk/framework/src/main/java/org/apache/felix/framework/searchpolicy/ResolvedPackage.java
    felix/trunk/framework/src/main/java/org/apache/felix/framework/searchpolicy/Resolver.java

Added: felix/trunk/framework/src/main/java/org/apache/felix/framework/searchpolicy/CandidateSet.java
URL: http://svn.apache.org/viewvc/felix/trunk/framework/src/main/java/org/apache/felix/framework/searchpolicy/CandidateSet.java?rev=748595&view=auto
==============================================================================
--- felix/trunk/framework/src/main/java/org/apache/felix/framework/searchpolicy/CandidateSet.java (added)
+++ felix/trunk/framework/src/main/java/org/apache/felix/framework/searchpolicy/CandidateSet.java Fri Feb 27 17:02:56 2009
@@ -0,0 +1,38 @@
+package org.apache.felix.framework.searchpolicy;
+
+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 int m_idx = 0;
+    public int m_rotated = 0;
+
+    public CandidateSet(int type, IModule module, IRequirement requirement, PackageSource[] 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

Modified: felix/trunk/framework/src/main/java/org/apache/felix/framework/searchpolicy/ResolvedPackage.java
URL: http://svn.apache.org/viewvc/felix/trunk/framework/src/main/java/org/apache/felix/framework/searchpolicy/ResolvedPackage.java?rev=748595&r1=748594&r2=748595&view=diff
==============================================================================
--- felix/trunk/framework/src/main/java/org/apache/felix/framework/searchpolicy/ResolvedPackage.java (original)
+++ felix/trunk/framework/src/main/java/org/apache/felix/framework/searchpolicy/ResolvedPackage.java Fri Feb 27 17:02:56 2009
@@ -30,13 +30,15 @@
  */
 class ResolvedPackage
 {
-    public String m_name = null;
-    public List m_sourceList = new ArrayList();
+    public final String m_name;
+    public final CandidateSet m_cs;
+    public final List m_sourceList = new ArrayList();
 
-    public ResolvedPackage(String name)
+    public ResolvedPackage(String name, CandidateSet cs)
     {
         super();
         m_name = name;
+        m_cs = cs;
     }
 
     public boolean isSubset(ResolvedPackage rp)
@@ -55,7 +57,7 @@
 
     public Object clone()
     {
-        ResolvedPackage rp = new ResolvedPackage(m_name);
+        ResolvedPackage rp = new ResolvedPackage(m_name, m_cs);
         rp.m_sourceList.addAll(m_sourceList);
         return rp;
     }

Modified: felix/trunk/framework/src/main/java/org/apache/felix/framework/searchpolicy/Resolver.java
URL: http://svn.apache.org/viewvc/felix/trunk/framework/src/main/java/org/apache/felix/framework/searchpolicy/Resolver.java?rev=748595&r1=748594&r2=748595&view=diff
==============================================================================
--- felix/trunk/framework/src/main/java/org/apache/felix/framework/searchpolicy/Resolver.java (original)
+++ felix/trunk/framework/src/main/java/org/apache/felix/framework/searchpolicy/Resolver.java Fri Feb 27 17:02:56 2009
@@ -19,6 +19,8 @@
 package org.apache.felix.framework.searchpolicy;
 
 import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
 import java.util.HashMap;
 import java.util.Iterator;
 import java.util.List;
@@ -538,6 +540,12 @@
         }
     }
 
+    // This flag indicates whether candidates have been rotated due to a
+    // "uses" constraint conflict. If so, then it is not necessary to perform
+    // a permutation, since rotating the candidates selected a new permutation.
+    // This part of an attempt to perform smarter permutations.
+    private boolean m_candidatesRotated = false;
+
     private void findConsistentClassSpace(
         ResolverState state, Map candidatesMap, IModule rootModule)
         throws ResolveException
@@ -569,12 +577,59 @@
                 for (Iterator iter = candidatesMap.entrySet().iterator();
                     iter.hasNext(); )
                 {
-                    candidatesList.add(((Map.Entry) iter.next()).getValue());
+                    Map.Entry entry = (Map.Entry) iter.next();
+                    candidatesList.add(entry.getValue());
                 }
+
+                // Sort the bundles candidate sets according to a weighting
+                // based on how many multi-candidate requirements each has.
+                // The idea is to push bundles with more potential candidate
+                // permutations to the front so we can permutate over them
+                // more quickly, since they are likely to have more issues.
+                Collections.sort(candidatesList, new Comparator() {
+                    public int compare(Object o1, Object o2)
+                    {
+                        int w1 = calculateWeight((List) o1);
+                        int w2 = calculateWeight((List) o2);
+                        if (w1 < w2)
+                        {
+                            return -1;
+                        }
+                        else if (w1 > w2)
+                        {
+                            return 1;
+                        }
+                        return 0;
+                    }
+
+                    private int calculateWeight(List candSetList)
+                    {
+                        int weight = 0;
+                        for (int csIdx = 0; csIdx < candSetList.size(); csIdx++)
+                        {
+                            CandidateSet cs = (CandidateSet) candSetList.get(csIdx);
+                            if ((cs.m_candidates != null) && (cs.m_candidates.length > 1))
+                            {
+                                weight += cs.m_candidates.length;
+                            }
+                        }
+                        return -weight;
+                    }
+                });
             }
 
-            // Increment the candidate configuration so we can test again.
-            incrementCandidateConfiguration(candidatesList);
+            // Increment the candidate configuration to a new permutation so
+            // we can test again, unless some candidates have been rotated.
+            // In that case, we re-test the current permutation, since rotating
+            // the candidates effectively selects a new permutation.
+            if (!m_candidatesRotated)
+            {
+                incrementCandidateConfiguration(candidatesList);
+            }
+            else
+            {
+                m_candidatesRotated = false;
+            }
 
             // Clear the module map.
             moduleMap.clear();
@@ -840,6 +895,29 @@
                             "Constraint violation for " + targetModule
                             + " detected; module can see "
                             + rp + " and " + rpUses);
+
+                        // If the resolved package has a candidate set, then
+                        // attempt to directly rotate the candidates to fix the
+                        // "uses" constraint conflict. The idea is rather than
+                        // blinding incrementing to the next permutation, we will
+                        // try to target the permutation to the bundle with a
+                        // 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))
+                        {
+                            // Rotate candidates.
+                            PackageSource first = rp.m_cs.m_candidates[0];
+                            for (int i = 1; i < rp.m_cs.m_candidates.length; i++)
+                            {
+                                rp.m_cs.m_candidates[i - 1] = rp.m_cs.m_candidates[i];
+                            }
+                            rp.m_cs.m_candidates[rp.m_cs.m_candidates.length - 1] = first;
+                            rp.m_cs.m_rotated++;
+                            m_candidatesRotated = true;
+                        }
+
                         return false;
                     }
                 }
@@ -1056,7 +1134,7 @@
                 String pkgName = (String)
                     ps.m_capability.getProperties().get(ICapability.PACKAGE_PROPERTY);
 
-                ResolvedPackage rp = new ResolvedPackage(pkgName);
+                ResolvedPackage rp = new ResolvedPackage(pkgName, cs);
                 rp.m_sourceList.add(ps);
                 pkgMap.put(rp.m_name, rp);
             }
@@ -1082,7 +1160,7 @@
                 String pkgName = (String)
                     wires[wireIdx].getCapability().getProperties().get(ICapability.PACKAGE_PROPERTY);
                 ResolvedPackage rp = (ResolvedPackage) pkgMap.get(pkgName);
-                rp = (rp == null) ? new ResolvedPackage(pkgName) : rp;
+                rp = (rp == null) ? new ResolvedPackage(pkgName, null) : rp;
                 rp.m_sourceList.add(new PackageSource(wires[wireIdx].getExporter(), wires[wireIdx].getCapability()));
                 pkgMap.put(rp.m_name, rp);
             }
@@ -1106,7 +1184,7 @@
                 String pkgName = (String)
                     caps[capIdx].getProperties().get(ICapability.PACKAGE_PROPERTY);
                 ResolvedPackage rp = (ResolvedPackage) pkgMap.get(pkgName);
-                rp = (rp == null) ? new ResolvedPackage(pkgName) : rp;
+                rp = (rp == null) ? new ResolvedPackage(pkgName, null) : rp;
                 rp.m_sourceList.add(new PackageSource(targetModule, caps[capIdx]));
                 pkgMap.put(rp.m_name, rp);
             }
@@ -1361,7 +1439,7 @@
                 String pkgName = (String)
                     candCaps[capIdx].getProperties().get(ICapability.PACKAGE_PROPERTY);
                 ResolvedPackage rp = (ResolvedPackage) pkgMap.get(pkgName);
-                rp = (rp == null) ? new ResolvedPackage(pkgName) : rp;
+                rp = (rp == null) ? new ResolvedPackage(pkgName, null) : rp;
                 rp.m_sourceList.add(new PackageSource(psTarget.m_module, candCaps[capIdx]));
                 pkgMap.put(rp.m_name, rp);
             }
@@ -1477,7 +1555,7 @@
                 String pkgName = (String)
                     caps[i].getProperties().get(ICapability.PACKAGE_PROPERTY);
                 ResolvedPackage rp = (ResolvedPackage) pkgMap.get(pkgName);
-                rp = (rp == null) ? new ResolvedPackage(pkgName) : rp;
+                rp = (rp == null) ? new ResolvedPackage(pkgName, null) : rp;
                 rp.m_sourceList.add(new PackageSource(targetModule, caps[i]));
                 pkgMap.put(rp.m_name, rp);
             }
@@ -1719,36 +1797,4 @@
         PackageSource[] getResolvedCandidates(IRequirement req);
         PackageSource[] getUnresolvedCandidates(IRequirement req);
     }
-
-    private static 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 int m_idx = 0;
-
-        public CandidateSet(int type, IModule module, IRequirement requirement, PackageSource[] candidates)
-        {
-            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)
-        {
-            m_type = type;
-            m_module = module;
-            m_requirement = requirement;
-            m_candidates = null;
-            m_modules = fragments;
-        }
-    }
 }
\ No newline at end of file