felix-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From rickh...@apache.org
Subject svn commit: r807795 [2/5] - in /felix/sandbox/rickhall/resolver: ./ src/ src/main/ src/main/java/ src/main/java/org/ src/main/java/org/apache/ src/main/java/org/apache/felix/ src/main/java/org/apache/felix/resolver/ src/main/java/org/apache/felix/resol...
Date Tue, 25 Aug 2009 20:30:34 GMT
Added: felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/felix/FelixResolverImpl.java
URL: http://svn.apache.org/viewvc/felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/felix/FelixResolverImpl.java?rev=807795&view=auto
==============================================================================
--- felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/felix/FelixResolverImpl.java (added)
+++ felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/felix/FelixResolverImpl.java Tue Aug 25 20:30:33 2009
@@ -0,0 +1,818 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.felix.resolver.felix;
+
+import java.util.*;
+import org.apache.felix.resolver.*;
+
+public class FelixResolverImpl
+{
+    // Reusable empty array.
+    private static final Wire[] m_emptyWires = new Wire[0];
+    private static final Module[] m_emptyModules = new Module[0];
+    private static final PackageSource[] m_emptySources = new PackageSource[0];
+
+    public FelixResolverImpl()
+    {
+    }
+
+    // Returns a map of resolved bundles where the key is the module
+    // and the value is an array of wires.
+    public Map resolve(ResolverState state, Module rootModule)
+    {
+        // If the module is already resolved, then we can just return.
+        if (rootModule.isResolved())
+        {
+            return null;
+        }
+
+        // This variable maps an unresolved module to a list of candidate
+        // sets, where there is one candidate set for each requirement that
+        // must be resolved. A candidate set contains the potential canidates
+        // available to resolve the requirement and the currently selected
+        // candidate index.
+        Map candidatesMap = new HashMap();
+
+        // The first step is to populate the candidates map. This
+        // will use the target module to populate the candidates map
+        // with all potential modules that need to be resolved as a
+        // result of resolving the target module. The key of the
+        // map is a potential module to be resolved and the value is
+        // a list of candidate sets, one for each of the module's
+        // requirements, where each candidate set contains the potential
+        // candidates for resolving the requirement. Not all modules in
+        // 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);
+
+        // The next step is to use the candidates map to determine if
+        // the class space for the root module is consistent. This
+        // is an iterative process that transitively walks the "uses"
+        // relationships of all packages visible from the root module
+        // checking for conflicts. If a conflict is found, it "increments"
+        // the configuration of currently selected potential candidates
+        // and tests them again. If this method returns, then it has found
+        // a consistent set of candidates; otherwise, a resolve exception
+        // is thrown if it exhausts all possible combinations and could
+        // not find a consistent class space.
+        findConsistentClassSpace(state, candidatesMap, rootModule);
+
+        // The final step is to create the wires for the root module and
+        // transitively all modules that are to be resolved from the
+        // selected candidates for resolving the root module's imports.
+        // When this call returns, each module's wiring and resolved
+        // attributes are set. The resulting wiring map is used below
+        // to fire resolved events outside of the synchronized block.
+        // The resolved module wire map maps a module to its array of
+        // wires.
+        return populateWireMap(state, candidatesMap, rootModule, new HashMap());
+    }
+
+    private void populateCandidatesMap(
+        ResolverState state, Map candidatesMap, Map byproductMap,
+        Module instigatingModule, Module targetModule)
+    {
+        // Detect cycles.
+        if (candidatesMap.containsKey(targetModule))
+        {
+            return;
+        }
+
+        // Finally, resolve any dependencies the module may have.
+
+        // Add target module to the candidates map so we can detect cycles.
+        candidatesMap.put(targetModule, null);
+
+        // Create list to hold the resolving candidate sets for the target
+        // module's requirements.
+        List candSetList = new ArrayList();
+
+        // Loop through each requirement and calculate its resolving
+        // set of candidates.
+        List<ImportedPackage> reqs = targetModule.getImports();
+        for (int reqIdx = 0; (reqs != null) && (reqIdx < reqs.size()); reqIdx++)
+        {
+            // Get the candidates from the "resolved" and "unresolved"
+            // package maps. The "resolved" candidates have higher priority
+            // than "unresolved" ones, so put the "resolved" candidates
+            // at the front of the list of candidates.
+            PackageSource[] resolved = state.getResolvedCandidates(reqs.get(reqIdx));
+            PackageSource[] unresolved = state.getUnresolvedCandidates(reqs.get(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);
+
+            // If we have candidates, then we need to recursively populate
+            // the resolver map with each of them.
+            RuntimeException rethrow = null;
+            if (candidates.length > 0)
+            {
+                for (int candIdx = 0; candIdx < candidates.length; candIdx++)
+                {
+                    try
+                    {
+                        // Only populate the resolver map with modules that
+                        // are not already resolved.
+                        if (!candidates[candIdx].m_module.isResolved())
+                        {
+                            populateCandidatesMap(
+                                state, candidatesMap, byproductMap,
+                                targetModule, candidates[candIdx].m_module);
+                        }
+                    }
+                    catch (RuntimeException ex)
+                    {
+                        // If we received a resolve exception, then the
+                        // 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;
+                        rethrow = ex;
+                    }
+                }
+
+                // Remove any nulled candidates to create the final list
+                // of available 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)
+            {
+                // 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 byproduct resolved modules.
+// TODO: FELIX-1422 - Maybe this goes too far and should only discard the
+//       the failing module as a candidate, since some modules may have
+//       resolved correctly because they didn't depend on the failing module.
+                removeByproductModules(candidatesMap, byproductMap, targetModule);
+
+                // If we have received an exception while trying to populate
+                // the candidates map, rethrow that exception since it might
+                // be useful. NOTE: This is not necessarily the "only"
+                // correct exception, since it is possible that multiple
+                // candidates were not resolvable, but it is better than
+                // nothing.
+                if (rethrow != null)
+                {
+                    throw rethrow;
+                }
+                else
+                {
+                    throw new ResolveException(
+                        "Unable to resolve: " + targetModule + " - " + reqs.get(reqIdx));
+                }
+            }
+            else if (candidates.length > 0)
+            {
+                candSetList.add(
+                    new CandidateSet(CandidateSet.NORMAL, targetModule, reqs.get(reqIdx), candidates));
+            }
+        }
+
+        // Now that the module's candidates have been calculated, add the
+        // candidate set list to the candidates map to be used for calculating
+        // uses constraints and ultimately wires.
+        candidatesMap.put(targetModule, candSetList);
+
+        // Also add this module as a byproduct of the instigating module,
+        // since it caused it to be resolved; this is necessary if we have
+        // a failure to resolver somewhere higher up.
+        if (instigatingModule != null)
+        {
+            Module[] modules = (Module[]) byproductMap.get(instigatingModule);
+            if (modules == null)
+            {
+                modules = new Module[] { targetModule };
+            }
+            else
+            {
+                Module[] tmp = new Module[modules.length + 1];
+                System.arraycopy(modules, 0, tmp, 0, modules.length);
+                tmp[modules.length] = targetModule;
+                modules = tmp;
+            }
+            byproductMap.put(instigatingModule, modules);
+        }
+    }
+
+    private static void removeByproductModules(
+        Map candidatesMap, Map byproductMap, Module targetModule)
+    {
+        Module[] modules = (Module[]) byproductMap.remove(targetModule);
+        if (modules != null)
+        {
+            for (int i = 0; i < modules.length; i++)
+            {
+                candidatesMap.remove(modules[i]);
+                removeByproductModules(candidatesMap, byproductMap, modules[i]);
+            }
+        }
+    }
+
+    // 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, Module rootModule)
+        throws ResolveException
+    {
+        List candidatesList = null;
+
+        // The reusable module map maps a module to a map of
+        // resolved packages that are accessible by the given
+        // module. The set of resolved packages is calculated
+        // from the current candidates of the candidates map
+        // and the module's metadata.
+        Map moduleMap = new HashMap();
+
+        // Reusable map used to test for cycles.
+        Map cycleMap = new HashMap();
+
+        // Test the current potential candidates to determine if they
+        // are consistent. Keep looping until we find a consistent
+        // set or an exception is thrown.
+        while (!isClassSpaceConsistent(rootModule, moduleMap, cycleMap, candidatesMap))
+        {
+            // The incrementCandidateConfiguration() method requires
+            // ordered access to the candidates map, so we will create
+            // a reusable list once right here.
+            if (candidatesList == null)
+            {
+                candidatesList = new ArrayList();
+                for (Iterator iter = candidatesMap.entrySet().iterator();
+                    iter.hasNext(); )
+                {
+                    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 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();
+
+            // Clear the cycle map.
+            cycleMap.clear();
+        }
+    }
+
+    private boolean isClassSpaceConsistent(
+        Module targetModule, Map moduleMap, Map cycleMap, Map candidatesMap)
+    {
+//System.out.println("isClassSpaceConsistent("+targetModule+")");
+        // If we are in a cycle, then assume true for now.
+        if (cycleMap.get(targetModule) != null)
+        {
+            return true;
+        }
+
+        // Record the target module in the cycle map.
+        cycleMap.put(targetModule, targetModule);
+
+        // Get the package map for the target module, which is a
+        // map of all packages accessible to the module and their
+        // associated package sources.
+        Map pkgMap = null;
+        try
+        {
+            pkgMap = getModulePackages(moduleMap, targetModule, candidatesMap);
+        }
+        catch (ResolveException ex)
+        {
+            System.out.println(
+                "Constraint violation for " + targetModule + " detected." +
+                ex);
+            return false;
+        }
+
+        // Loop through all of the target module's accessible packages and
+        // verify that all package sources are consistent.
+        for (Iterator iter = pkgMap.entrySet().iterator(); iter.hasNext(); )
+        {
+            Map.Entry entry = (Map.Entry) iter.next();
+            // Get the resolved package, which contains the set of all
+            // package sources for the given package.
+            ResolvedPackage rp = (ResolvedPackage) entry.getValue();
+            // Loop through each package source and test if it is consistent.
+            for (int srcIdx = 0; srcIdx < rp.m_sourceList.size(); srcIdx++)
+            {
+                PackageSource ps = (PackageSource) rp.m_sourceList.get(srcIdx);
+                if (!isClassSpaceConsistent(ps.m_module, moduleMap, cycleMap, candidatesMap))
+                {
+                    return false;
+                }
+            }
+        }
+
+        // Now we need to calculate the "uses" constraints of every package
+        // accessible to the target module based on the current candidates.
+        Map usesMap = null;
+        try
+        {
+            usesMap = calculateUsesConstraints(targetModule, moduleMap, candidatesMap);
+        }
+        catch (ResolveException ex)
+        {
+            System.out.println(
+                "Constraint violation for " + targetModule + " detected." +
+                ex);
+            return false;
+        }
+
+        // Verify that none of the implied "uses" constraints in the uses map
+        // conflict with anything in the target module's package map.
+        for (Iterator iter = usesMap.entrySet().iterator(); iter.hasNext(); )
+        {
+            Map.Entry entry = (Map.Entry) iter.next();
+
+            // For the given "used" package, get that package from the
+            // target module's package map, if present.
+            ResolvedPackage rp = (ResolvedPackage) pkgMap.get(entry.getKey());
+
+            // If the "used" package is also visible to the target module,
+            // make sure there is no conflicts in the implied "uses"
+            // constraints.
+            if (rp != null)
+            {
+                // Clone the resolve package so we can modify it.
+                rp = (ResolvedPackage) rp.clone();
+
+                // Loop through all implied "uses" constraints for the current
+                // "used" package and verify that all package sources are
+                // compatible with the package source of the root module's
+                // package map.
+                List constraintList = (List) entry.getValue();
+                for (int constIdx = 0; constIdx < constraintList.size(); constIdx++)
+                {
+                    // Get a specific "uses" constraint for the current "used"
+                    // package.
+                    ResolvedPackage rpUses = (ResolvedPackage) constraintList.get(constIdx);
+                    // Determine if the implied "uses" constraint is compatible with
+                    // the target module's package sources for the given "used"
+                    // package. They are compatible if one is the subset of the other.
+                    // Retain the union of the two sets if they are compatible.
+                    if (rpUses.isSubset(rp))
+                    {
+                        // Do nothing because we already have the superset.
+                    }
+                    else if (rp.isSubset(rpUses))
+                    {
+                        // Keep the superset, i.e., the union.
+                        rp.m_sourceList.clear();
+                        rp.m_sourceList.addAll(rpUses.m_sourceList);
+                    }
+                    else
+                    {
+//                        System.out.println(
+//                            "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;
+                    }
+                }
+            }
+        }
+
+        return true;
+    }
+
+    private static Map calculateUsesConstraints(
+        Module targetModule, Map moduleMap, Map candidatesMap)
+        throws ResolveException
+    {
+//System.out.println("calculateUsesConstraints("+targetModule+")");
+        // Map to store calculated uses constraints. This maps a
+        // package name to a list of resolved packages, where each
+        // resolved package represents a constraint on anyone
+        // importing the given package name. This map is returned
+        // by this method.
+        Map usesMap = new HashMap();
+
+        // Re-usable map to detect cycles.
+        Map cycleMap = new HashMap();
+
+        // Get all packages accessible by the target module.
+        Map pkgMap = getModulePackages(moduleMap, targetModule, candidatesMap);
+
+        // Each package accessible from the target module is potentially
+        // comprised of one or more modules, called package sources. The
+        // "uses" constraints implied by all package sources must be
+        // calculated and combined to determine the complete set of implied
+        // "uses" constraints for each package accessible by the target module.
+        for (Iterator iter = pkgMap.entrySet().iterator(); iter.hasNext(); )
+        {
+            Map.Entry entry = (Map.Entry) iter.next();
+            ResolvedPackage rp = (ResolvedPackage) entry.getValue();
+            for (int srcIdx = 0; srcIdx < rp.m_sourceList.size(); srcIdx++)
+            {
+                usesMap = calculateUsesConstraints(
+                    (PackageSource) rp.m_sourceList.get(srcIdx),
+                    moduleMap, usesMap, cycleMap, candidatesMap);
+            }
+        }
+        return usesMap;
+    }
+
+    private static Map calculateUsesConstraints(
+        PackageSource psTarget, Map moduleMap, Map usesMap,
+        Map cycleMap, Map candidatesMap)
+        throws ResolveException
+    {
+//System.out.println("calculateUsesConstraints2("+psTarget.m_module+")");
+        // If we are in a cycle, then return for now.
+        if (cycleMap.get(psTarget) != null)
+        {
+            return usesMap;
+        }
+
+        // Record the target package source in the cycle map.
+        cycleMap.put(psTarget, psTarget);
+
+        // Get all packages accessible from the module of the
+        // target package source.
+        Map pkgMap = getModulePackages(moduleMap, psTarget.m_module, candidatesMap);
+
+        // Get capability (i.e., package) of the target package source.
+        ExportedPackage cap = psTarget.m_capability;
+
+        // Loop through all "used" packages of the capability.
+        for (int i = 0; i < cap.getUses().size(); i++)
+        {
+            // The target package source module should have a resolved package
+            // for the "used" package in its set of accessible packages,
+            // since it claims to use it, so get the associated resolved
+            // package.
+            ResolvedPackage rp = (ResolvedPackage) pkgMap.get(cap.getUses().get(i));
+
+            // In general, the resolved package should not be null,
+            // but check for safety.
+            if (rp != null)
+            {
+                // First, iterate through all package sources for the resolved
+                // package associated with the current "used" package and calculate
+                // and combine the "uses" constraints for each package source.
+                for (int srcIdx = 0; srcIdx < rp.m_sourceList.size(); srcIdx++)
+                {
+                    usesMap = calculateUsesConstraints(
+                        (PackageSource) rp.m_sourceList.get(srcIdx),
+                        moduleMap, usesMap, cycleMap, candidatesMap);
+                }
+
+                // Then, add the resolved package for the current "used" package
+                // as a "uses" constraint too; add it to an existing constraint
+                // list if the current "used" package is already in the uses map.
+                List constraintList = (List) usesMap.get(cap.getUses().get(i));
+                if (constraintList == null)
+                {
+                    constraintList = new ArrayList();
+                }
+                constraintList.add(rp);
+                usesMap.put(cap.getUses().get(i), constraintList);
+            }
+        }
+
+        return usesMap;
+    }
+
+    private static Map getModulePackages(Map moduleMap, Module module, Map candidatesMap)
+        throws ResolveException
+    {
+        Map map = (Map) moduleMap.get(module);
+
+        if (map == null)
+        {
+            map = calculateModulePackages(module, candidatesMap);
+            moduleMap.put(module, map);
+        }
+        return map;
+    }
+
+    /**
+     * <p>
+     * Calculates the module's set of accessible packages and their
+     * assocaited package sources. This method uses the current candidates
+     * for resolving the module's requirements from the candidate map
+     * to calculate the module's accessible packages.
+     * </p>
+     * @param module the module whose package map is to be calculated.
+     * @param candidatesMap the map of potential candidates for resolving
+     *        the module's requirements.
+     * @return a map of the packages accessible to the specified module where
+     *         the key of the map is the package name and the value of the map
+     *         is a ResolvedPackage.
+    **/
+    private static Map calculateModulePackages(Module module, Map candidatesMap)
+        throws ResolveException
+    {
+//System.out.println("calculateModulePackages("+module+")");
+        Map importedPackages = calculateImportedPackages(module, candidatesMap);
+        Map exportedPackages = calculateExportedPackages(module);
+        Map requiredPackages = new HashMap();
+
+        // Merge exported packages into required packages. If a package is both
+        // exported and required, then append the exported source to the end of
+        // the require package sources; otherwise just add it to the package map.
+        for (Iterator i = exportedPackages.entrySet().iterator(); i.hasNext(); )
+        {
+            Map.Entry entry = (Map.Entry) i.next();
+            ResolvedPackage rpReq = (ResolvedPackage) requiredPackages.get(entry.getKey());
+            if (rpReq != null)
+            {
+                // Merge exported and required packages, avoiding duplicate
+                // package sources and maintaining ordering.
+                ResolvedPackage rpExport = (ResolvedPackage) entry.getValue();
+                rpReq.merge(rpExport);
+            }
+            else
+            {
+                requiredPackages.put(entry.getKey(), entry.getValue());
+            }
+        }
+
+        // Merge imported packages into required packages. Imports overwrite
+        // any required and/or exported package.
+        for (Iterator i = importedPackages.entrySet().iterator(); i.hasNext(); )
+        {
+            Map.Entry entry = (Map.Entry) i.next();
+            requiredPackages.put(entry.getKey(), entry.getValue());
+        }
+
+        return requiredPackages;
+    }
+
+    private static Map calculateImportedPackages(Module targetModule, Map candidatesMap)
+        throws ResolveException
+    {
+        return calculateImportedPackagesUnresolved(targetModule, candidatesMap);
+    }
+
+    private static Map calculateImportedPackagesUnresolved(Module targetModule, Map candidatesMap)
+        throws ResolveException
+    {
+//System.out.println("calculateImportedPackagesUnresolved("+targetModule+")");
+        Map pkgMap = new HashMap();
+
+        // Get the candidate set list to get all candidates for
+        // all of the target module's requirements.
+        List candSetList = (List) candidatesMap.get(targetModule);
+
+        // Loop through all candidate sets that represent import dependencies
+        // for the target module and add the current candidate's package source
+        // to the imported package map.
+        for (int candSetIdx = 0;
+            (candSetList != null) && (candSetIdx < candSetList.size());
+            candSetIdx++)
+        {
+            CandidateSet cs = (CandidateSet) candSetList.get(candSetIdx);
+            PackageSource ps = cs.m_candidates[cs.m_idx];
+
+            String pkgName = ps.m_capability.getName();
+
+            ResolvedPackage rp = new ResolvedPackage(pkgName, cs);
+            rp.m_sourceList.add(ps);
+            pkgMap.put(rp.m_name, rp);
+        }
+
+        return pkgMap;
+    }
+
+    private static Map calculateExportedPackages(Module targetModule)
+    {
+//System.out.println("calculateExportedPackages("+targetModule+")");
+        Map pkgMap = new HashMap();
+
+        // Loop through the target module's capabilities that represent
+        // exported packages and add them to the exported package map.
+        List<ExportedPackage> caps = targetModule.getExports();
+        for (int capIdx = 0; (caps != null) && (capIdx < caps.size()); capIdx++)
+        {
+            String pkgName = caps.get(capIdx).getName();
+            ResolvedPackage rp = (ResolvedPackage) pkgMap.get(pkgName);
+            rp = (rp == null) ? new ResolvedPackage(pkgName, null) : rp;
+            rp.m_sourceList.add(new PackageSource(targetModule, caps.get(capIdx)));
+            pkgMap.put(rp.m_name, rp);
+        }
+
+        return pkgMap;
+    }
+
+    private static void incrementCandidateConfiguration(List resolverList)
+        throws ResolveException
+    {
+        for (int i = 0; i < resolverList.size(); i++)
+        {
+            List candSetList = (List) resolverList.get(i);
+            for (int j = 0; j < candSetList.size(); j++)
+            {
+                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)
+                {
+                    cs.m_idx++;
+                    return;
+                }
+                // If the index will overflow the candidate array bounds,
+                // then set the index back to zero and try to increment
+                // the next candidate.
+                else
+                {
+                    cs.m_idx = 0;
+                }
+            }
+        }
+        throw new ResolveException(
+            "Unable to resolve due to constraint violation.");
+    }
+
+    private static Map populateWireMap(
+        ResolverState state, Map candidatesMap, Module importer, Map wireMap)
+    {
+        // If the module is already resolved or it is part of
+        // a cycle, then just return the wire map.
+        if (importer.isResolved() || (wireMap.get(importer) != null))
+        {
+            return wireMap;
+        }
+
+        // Get the candidate set list for the importer.
+        List candSetList = (List) candidatesMap.get(importer);
+
+        List moduleWires = new ArrayList();
+        List packageWires = new ArrayList();
+
+        // Put the module in the wireMap with an empty wire array;
+        // we do this early so we can use it to detect cycles.
+        wireMap.put(importer, m_emptyWires);
+
+        // Loop through each candidate Set and create a wire
+        // for the selected candidate for the associated import.
+        for (int candSetIdx = 0; candSetIdx < candSetList.size(); candSetIdx++)
+        {
+            // Get the current candidate set.
+            CandidateSet cs = (CandidateSet) candSetList.get(candSetIdx);
+
+            // 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.
+            if (importer != cs.m_candidates[cs.m_idx].m_module)
+            {
+                // Add wire for imported package.
+                packageWires.add(new Wire(
+                    importer,
+                    cs.m_requirement,
+                    cs.m_candidates[cs.m_idx].m_module,
+                    cs.m_candidates[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);
+        }
+
+        packageWires.addAll(moduleWires);
+        wireMap.put(importer, packageWires.toArray(new Wire[packageWires.size()]));
+
+        return wireMap;
+    }
+
+    //
+    // Utility methods.
+    //
+
+    private static PackageSource[] shrinkCandidateArray(PackageSource[] candidates)
+    {
+        if (candidates == null)
+        {
+            return m_emptySources;
+        }
+
+        // Move all non-null values to one end of the array.
+        int lower = 0;
+        for (int i = 0; i < candidates.length; i++)
+        {
+            if (candidates[i] != null)
+            {
+                candidates[lower++] = candidates[i];
+            }
+        }
+
+        if (lower == 0)
+        {
+            return m_emptySources;
+        }
+
+        // Copy non-null values into a new array and return.
+        PackageSource[] newCandidates= new PackageSource[lower];
+        System.arraycopy(candidates, 0, newCandidates, 0, lower);
+        return newCandidates;
+    }
+
+    //
+    // Inner classes.
+    //
+
+    public static interface ResolverState
+    {
+        Module[] getModules();
+        PackageSource[] getResolvedCandidates(ImportedPackage req);
+        PackageSource[] getUnresolvedCandidates(ImportedPackage req);
+    }
+}
\ No newline at end of file

Added: felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/felix/PackageSource.java
URL: http://svn.apache.org/viewvc/felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/felix/PackageSource.java?rev=807795&view=auto
==============================================================================
--- felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/felix/PackageSource.java (added)
+++ felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/felix/PackageSource.java Tue Aug 25 20:30:33 2009
@@ -0,0 +1,78 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.felix.resolver.felix;
+
+import org.apache.felix.resolver.*;
+
+/**
+ * This utility class represents a source for a given package, where
+ * the package is indicated by a particular module and the module's
+ * capability associated with that package. This class also implements
+ * <tt>Comparable</tt> so that two package sources can be compared based
+ * on version and bundle identifiers.
+ */
+public class PackageSource implements Comparable
+{
+    public Module m_module = null;
+    public ExportedPackage m_capability = null;
+
+    public PackageSource(Module module, ExportedPackage capability)
+    {
+        super();
+        m_module = module;
+        m_capability = capability;
+    }
+
+    public int compareTo(Object o)
+    {
+        return 1;
+    }
+
+    public int hashCode()
+    {
+        final int PRIME = 31;
+        int result = 1;
+        result = PRIME * result + ((m_capability == null) ? 0 : m_capability.hashCode());
+        result = PRIME * result + ((m_module == null) ? 0 : m_module.hashCode());
+        return result;
+    }
+
+    public boolean equals(Object o)
+    {
+        if (this == o)
+        {
+            return true;
+        }
+        if (o == null)
+        {
+            return false;
+        }
+        if (getClass() != o.getClass())
+        {
+            return false;
+        }
+        PackageSource ps = (PackageSource) o;
+        return m_module.equals(ps.m_module) && (m_capability == ps.m_capability);
+    }
+
+    public String toString()
+    {
+        return m_module.toString();
+    }
+}
\ No newline at end of file

Added: felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/felix/ResolvedPackage.java
URL: http://svn.apache.org/viewvc/felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/felix/ResolvedPackage.java?rev=807795&view=auto
==============================================================================
--- felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/felix/ResolvedPackage.java (added)
+++ felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/felix/ResolvedPackage.java Tue Aug 25 20:30:33 2009
@@ -0,0 +1,100 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.felix.resolver.felix;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * This utility class is a resolved package, which is comprised of a
+ * set of <tt>PackageSource</tt>s that is calculated by the resolver
+ * algorithm. A given resolved package may have a single package source,
+ * as is the case with imported packages, or it may have multiple
+ * package sources, as is the case with required bundles.
+ */
+class ResolvedPackage
+{
+    public final String m_name;
+    public final CandidateSet m_cs;
+    public final List m_sourceList = new ArrayList();
+
+    public ResolvedPackage(String name, CandidateSet cs)
+    {
+        super();
+        m_name = name;
+        m_cs = cs;
+    }
+
+    public boolean isSubset(ResolvedPackage rp)
+    {
+        if (m_sourceList.size() > rp.m_sourceList.size())
+        {
+            return false;
+        }
+        else if (!m_name.equals(rp.m_name))
+        {
+            return false;
+        }
+        // Determine if the target set of source modules is a subset.
+        return rp.m_sourceList.containsAll(m_sourceList);
+    }
+
+    public Object clone()
+    {
+        ResolvedPackage rp = new ResolvedPackage(m_name, m_cs);
+        rp.m_sourceList.addAll(m_sourceList);
+        return rp;
+    }
+
+    public void merge(ResolvedPackage rp)
+    {
+        // Merge required packages, avoiding duplicate
+        // package sources and maintaining ordering.
+        for (int srcIdx = 0; srcIdx < rp.m_sourceList.size(); srcIdx++)
+        {
+            if (!m_sourceList.contains(rp.m_sourceList.get(srcIdx)))
+            {
+                m_sourceList.add(rp.m_sourceList.get(srcIdx));
+            }
+        }
+    }
+
+    public String toString()
+    {
+        return toString("", new StringBuffer()).toString();
+    }
+
+    public StringBuffer toString(String padding, StringBuffer sb)
+    {
+        sb.append(padding);
+        sb.append(m_name);
+        sb.append(" from [");
+        for (int i = 0; i < m_sourceList.size(); i++)
+        {
+            PackageSource ps = (PackageSource) m_sourceList.get(i);
+            sb.append(ps.m_module);
+            if ((i + 1) < m_sourceList.size())
+            {
+                sb.append(", ");
+            }
+        }
+        sb.append("]");
+        return sb;
+    }
+}

Added: felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/manifestparser/Capability.java
URL: http://svn.apache.org/viewvc/felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/manifestparser/Capability.java?rev=807795&view=auto
==============================================================================
--- felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/manifestparser/Capability.java (added)
+++ felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/manifestparser/Capability.java Tue Aug 25 20:30:33 2009
@@ -0,0 +1,342 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.felix.resolver.manifestparser;
+
+import org.apache.felix.resolver.Version;
+import java.util.*;
+
+public class Capability
+{
+    public static final String MODULE_NAMESPACE = "module";
+    public static final String HOST_NAMESPACE = "host";
+    public static final String PACKAGE_NAMESPACE = "package";
+
+    public static final String PACKAGE_PROPERTY = "package";
+    public static final String VERSION_PROPERTY = "version";
+
+
+    private String m_namespace;
+    private R4Directive[] m_directives;
+    private R4Attribute[] m_attributes;
+    private Map m_attrMap;
+    private String[] m_uses = new String[0];
+    private String[][] m_includeFilter;
+    private String[][] m_excludeFilter;
+
+    // Cached properties for performance reasons.
+    private String m_pkgName;
+    private Version m_pkgVersion = Version.emptyVersion;
+
+    public Capability(String namespace, R4Directive[] dirs, R4Attribute[] attrs)
+    {
+        m_namespace = namespace;
+        m_directives = dirs;
+        m_attributes = attrs;
+
+        // Find all export directives: uses, mandatory, include, and exclude.
+        String mandatory = "";
+        for (int dirIdx = 0; (m_directives != null) && (dirIdx < m_directives.length); dirIdx++)
+        {
+            if (m_directives[dirIdx].getName().equals(Constants.USES_DIRECTIVE))
+            {
+                // Parse these uses directive.
+                StringTokenizer tok = new StringTokenizer(m_directives[dirIdx].getValue(), ",");
+                m_uses = new String[tok.countTokens()];
+                for (int i = 0; i < m_uses.length; i++)
+                {
+                    m_uses[i] = tok.nextToken().trim();
+                }
+            }
+            else if (m_directives[dirIdx].getName().equals(Constants.MANDATORY_DIRECTIVE))
+            {
+                mandatory = m_directives[dirIdx].getValue();
+            }
+            else if (m_directives[dirIdx].getName().equals(Constants.INCLUDE_DIRECTIVE))
+            {
+                String[] ss = ManifestParser.parseDelimitedString(m_directives[dirIdx].getValue(), ",");
+                m_includeFilter = new String[ss.length][];
+                for (int filterIdx = 0; filterIdx < ss.length; filterIdx++)
+                {
+                    m_includeFilter[filterIdx] = Util.parseSubstring(ss[filterIdx]);
+                }
+            }
+            else if (m_directives[dirIdx].getName().equals(Constants.EXCLUDE_DIRECTIVE))
+            {
+                String[] ss = ManifestParser.parseDelimitedString(m_directives[dirIdx].getValue(), ",");
+                m_excludeFilter = new String[ss.length][];
+                for (int filterIdx = 0; filterIdx < ss.length; filterIdx++)
+                {
+                    m_excludeFilter[filterIdx] = Util.parseSubstring(ss[filterIdx]);
+                }
+            }
+        }
+
+        // Parse mandatory directive and mark specified
+        // attributes as mandatory.
+        StringTokenizer tok = new StringTokenizer(mandatory, ", ");
+        while (tok.hasMoreTokens())
+        {
+            // Get attribute name.
+            String attrName = tok.nextToken().trim();
+            // Find attribute and mark it as mandatory.
+            boolean found = false;
+            for (int i = 0; (!found) && (i < m_attributes.length); i++)
+            {
+                if (m_attributes[i].getName().equals(attrName))
+                {
+                    m_attributes[i] = new R4Attribute(
+                        m_attributes[i].getName(),
+                        m_attributes[i].getValue(), true);
+                    found = true;
+                }
+            }
+            // If a specified mandatory attribute was not found,
+            // then error.
+            if (!found)
+            {
+                throw new IllegalArgumentException(
+                    "Mandatory attribute '" + attrName + "' does not exist.");
+            }
+        }
+
+        // For performance reasons, find the package name and version properties.
+        for (int i = 0; i < m_attributes.length; i++)
+        {
+            if (m_attributes[i].getName().equals(Capability.PACKAGE_PROPERTY))
+            {
+                m_pkgName = (String) m_attributes[i].getValue();
+            }
+            else if (m_attributes[i].getName().equals(Capability.VERSION_PROPERTY))
+            {
+                m_pkgVersion = (Version) m_attributes[i].getValue();
+            }
+        }
+    }
+
+    public String getNamespace()
+    {
+        return m_namespace;
+    }
+
+// TODO: RB - Determine how to eliminate these non-generic methods;
+//            at least make sure they are not used in the generic resolver.
+    public String getPackageName()
+    {
+        return m_pkgName;
+    }
+
+    public Version getPackageVersion()
+    {
+        return m_pkgVersion;
+    }
+
+    public R4Directive[] getDirectives()
+    {
+        // TODO: RB - We should return copies of the arrays probably.
+        return m_directives;
+    }
+
+    public R4Attribute[] getAttributes()
+    {
+        // TODO: RB - We should return copies of the arrays probably.
+        return m_attributes;
+    }
+
+    public String[] getUses()
+    {
+        // TODO: RB - We should return copies of the arrays probably.
+        return m_uses;
+    }
+
+    public boolean isIncluded(String name)
+    {
+        if ((m_includeFilter == null) && (m_excludeFilter == null))
+        {
+            return true;
+        }
+
+        // Get the class name portion of the target class.
+        String className = Util.getClassName(name);
+
+        // If there are no include filters then all classes are included
+        // by default, otherwise try to find one match.
+        boolean included = (m_includeFilter == null);
+        for (int i = 0;
+            (!included) && (m_includeFilter != null) && (i < m_includeFilter.length);
+            i++)
+        {
+            included = Util.checkSubstring(m_includeFilter[i], className);
+        }
+
+        // If there are no exclude filters then no classes are excluded
+        // by default, otherwise try to find one match.
+        boolean excluded = false;
+        for (int i = 0;
+            (!excluded) && (m_excludeFilter != null) && (i < m_excludeFilter.length);
+            i++)
+        {
+            excluded = Util.checkSubstring(m_excludeFilter[i], className);
+        }
+        return included && !excluded;
+    }
+
+// TODO: RB - Terminology mismatch property vs. attribute.
+    public Map getProperties()
+    {
+        if (m_attrMap == null)
+        {
+            m_attrMap = new Map() {
+
+                public int size()
+                {
+                    // A name and version attribute is always present, since it has a
+                    // default value.
+                    return m_attributes.length + 2;
+                }
+
+                public boolean isEmpty()
+                {
+                    // A version attribute is always present, since it has a
+                    // default value.
+                    return false;
+                }
+
+                public boolean containsKey(Object key)
+                {
+                    return (get(key) != null);
+                }
+
+                public boolean containsValue(Object value)
+                {
+                    // Check the package name.
+                    if (m_pkgName.equals(value))
+                    {
+                        return true;
+                    }
+
+                    // Check the package version.
+                    if (m_pkgVersion.equals(value))
+                    {
+                        return true;
+                    }
+
+                    // Check all attributes.
+                    for (int i = 0; i < m_attributes.length; i++)
+                    {
+                        if (m_attributes[i].getValue().equals(value))
+                        {
+                            return true;
+                        }
+                    }
+
+                    return false;
+                }
+
+                public Object get(Object key)
+                {
+                    if (Capability.PACKAGE_PROPERTY.equals(key))
+                    {
+                        return m_pkgName;
+                    }
+                    else if (Capability.VERSION_PROPERTY.equals(key))
+                    {
+                        return m_pkgVersion;
+                    }
+
+                    for (int i = 0; i < m_attributes.length; i++)
+                    {
+                        if (m_attributes[i].getName().equals(key))
+                        {
+                            return m_attributes[i].getValue();
+                        }
+                    }
+
+                    return null;
+                }
+
+                public Object put(Object key, Object value)
+                {
+                    throw new UnsupportedOperationException("Map.put() not implemented.");
+                }
+
+                public Object remove(Object key)
+                {
+                    throw new UnsupportedOperationException("Map.remove() not implemented.");
+                }
+
+                public void putAll(Map t)
+                {
+                    throw new UnsupportedOperationException("Map.putAll() not implemented.");
+                }
+
+                public void clear()
+                {
+                    throw new UnsupportedOperationException("Map.clear() not implemented.");
+                }
+
+                public Set keySet()
+                {
+                    Set set = new HashSet();
+                    set.add(Capability.PACKAGE_PROPERTY);
+                    set.add(Capability.VERSION_PROPERTY);
+                    for (int i = 0; i < m_attributes.length; i++)
+                    {
+                        set.add(m_attributes[i].getName());
+                    }
+                    return set;
+                }
+
+                public Collection values()
+                {
+                    throw new UnsupportedOperationException("Map.values() not implemented.");
+                }
+
+                public Set entrySet()
+                {
+                    throw new UnsupportedOperationException("Map.entrySet() not implemented.");
+                }
+            };
+        }
+        return m_attrMap;
+    }
+
+// TODO: RB - Remove or simplify toString() for final version.
+    public String toString()
+    {
+        StringBuffer sb = new StringBuffer();
+        sb.append(getNamespace());
+        for (int i = 0; (m_directives != null) && (i < m_directives.length); i++)
+        {
+            sb.append(";");
+            sb.append(m_directives[i].getName());
+            sb.append(":=\"");
+            sb.append(m_directives[i].getValue());
+            sb.append("\"");
+        }
+        for (int i = 0; (m_attributes != null) && (i < m_attributes.length); i++)
+        {
+            sb.append(";");
+            sb.append(m_attributes[i].getName());
+            sb.append("=\"");
+            sb.append(m_attributes[i].getValue());
+            sb.append("\"");
+        }
+        return sb.toString();
+    }
+}
\ No newline at end of file



Mime
View raw message