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
