Added: felix/sandbox/rickhall/framework-proto/src/main/java/org/apache/felix/framework/resolver/ResolverImpl.java URL: http://svn.apache.org/viewvc/felix/sandbox/rickhall/framework-proto/src/main/java/org/apache/felix/framework/resolver/ResolverImpl.java?rev=901272&view=auto ============================================================================== --- felix/sandbox/rickhall/framework-proto/src/main/java/org/apache/felix/framework/resolver/ResolverImpl.java (added) +++ felix/sandbox/rickhall/framework-proto/src/main/java/org/apache/felix/framework/resolver/ResolverImpl.java Wed Jan 20 16:44:13 2010 @@ -0,0 +1,949 @@ +/* + * 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.framework.resolver; + +import java.util.ArrayList; +import java.util.HashMap; +import java.util.HashSet; +import java.util.Iterator; +import java.util.List; +import java.util.Map; +import java.util.Map.Entry; +import java.util.Set; +import java.util.TreeSet; +import org.apache.felix.resolver.CandidateComparator; +import org.apache.felix.resolver.Module; +import org.apache.felix.resolver.ResolveException; +import org.apache.felix.resolver.Resolver; +import org.apache.felix.resolver.ResolverStateImpl; +import org.apache.felix.resolver.Wire; +import org.apache.felix.resolver.cs.Capability; +import org.apache.felix.resolver.cs.CapabilitySet; +import org.apache.felix.resolver.cs.Requirement; + +// 1. Treat hard pkg constraints separately from implied package constraints +// 2. Map pkg constraints to a set of capabilities, not a single capability. +// 3. Uses constraints cannot conflict with other uses constraints, only with hard constraints. +public class ResolverImpl implements Resolver +{ + private static final Map<String, Long> m_invokeCounts = new HashMap<String, Long>(); + private static boolean m_isInvokeCount = false; + + public ResolverImpl() + { +System.out.println("+++ PROTO3 RESOLVER"); + String v = System.getProperty("invoke.count"); + m_isInvokeCount = (v == null) ? false : Boolean.valueOf(v); + } + + private final List<Map<Requirement, Set<Capability>>> m_candidatePermutations = + new ArrayList<Map<Requirement, Set<Capability>>>(); + + public Map<Module, List<Wire>> resolve(ResolverState state, Module module) + { + if (m_isInvokeCount) + { + String methodName = new Exception().fillInStackTrace().getStackTrace()[0].getMethodName(); + Long count = m_invokeCounts.get(methodName); + count = (count == null) ? new Long(1) : new Long(count.longValue() + 1); + m_invokeCounts.put(methodName, count); + } + + Map<Module, Packages> modulePkgMap = new HashMap<Module, Packages>(); + + if (!module.isResolved()) + { +System.out.println("+++ RESOLVING " + module); + Map<Requirement, Set<Capability>> candidateMap = + new HashMap<Requirement, Set<Capability>>(); + + populateCandidates(state, module, candidateMap, new HashSet<Module>()); + m_candidatePermutations.add(candidateMap); + + ResolveException rethrow = null; + + do + { + rethrow = null; + + candidateMap = m_candidatePermutations.remove(0); +dumpCandidateMap(state, candidateMap); + + try + { + findConsistentCandidates( + module, + new ArrayList(), + candidateMap, + modulePkgMap, + new HashMap<Module, Object>()); + } + catch (ResolveException ex) + { + rethrow = ex; + System.out.println("RE: " + ex); + } + } + while ((rethrow != null) && (m_candidatePermutations.size() > 0)); + + if (rethrow != null) + { + throw rethrow; + } +//dumpModulePkgMap(modulePkgMap); + } + + Map<Module, List<Wire>> wireMap = + populateWireMap(module, modulePkgMap, new HashMap<Module, List<Wire>>()); + + if (m_isInvokeCount) + { + System.out.println("INVOKE COUNTS " + m_invokeCounts); + } + + return wireMap; + } + + private static void dumpCandidateMap( + ResolverState state, Map<Requirement, Set<Capability>> candidateMap) + { + System.out.println("=== CANDIDATE MAP ==="); + for (Module module : ((ResolverStateImpl) state).getModules()) + { + if (!module.isResolved()) + { + System.out.println(" " + module); + for (Requirement req : module.getRequirements()) + { + Set<Capability> candidates = candidateMap.get(req); + if ((candidates != null) && (candidates.size() > 0)) + { + System.out.println(" " + req + ": " + candidates); + } + } + } + } + } + + private static void dumpModulePkgMap(Map<Module, Packages> modulePkgMap) + { + System.out.println("+++MODULE PKG MAP+++"); + for (Entry<Module, Packages> entry : modulePkgMap.entrySet()) + { + dumpModulePkgs(entry.getKey(), entry.getValue()); + } + } + + private static void dumpModulePkgs(Module module, Packages packages) + { + System.out.println(module + " (" + (module.isResolved() ? "RESOLVED)" : "UNRESOLVED)")); + System.out.println(" EXPORTED"); + for (Entry<String, Blame> entry : packages.m_exportedPkgs.entrySet()) + { + System.out.println(" " + entry.getKey() + " - " + entry.getValue()); + } + System.out.println(" IMPORTED"); + for (Entry<String, Blame> entry : packages.m_importedPkgs.entrySet()) + { + System.out.println(" " + entry.getKey() + " - " + entry.getValue()); + } + System.out.println(" REQUIRED"); + for (Entry<String, List<Blame>> entry : packages.m_requiredPkgs.entrySet()) + { + System.out.println(" " + entry.getKey() + " - " + entry.getValue()); + } + System.out.println(" USED"); + for (Entry<String, List<Blame>> entry : packages.m_usedPkgs.entrySet()) + { + System.out.println(" " + entry.getKey() + " - " + entry.getValue()); + } + } + + private static void populateCandidates( + ResolverState state, Module module, + Map<Requirement, Set<Capability>> candidateMap, Set<Module> cycles) + { + if (m_isInvokeCount) + { + String methodName = new Exception().fillInStackTrace().getStackTrace()[0].getMethodName(); + Long count = m_invokeCounts.get(methodName); + count = (count == null) ? new Long(1) : new Long(count.longValue() + 1); + m_invokeCounts.put(methodName, count); + } + + // Detect cycles. + if (cycles.contains(module)) + { + return; + } + cycles.add(module); + + // Store candidates in a local map first, just in case the module + // is not resolvable. + Map<Requirement, Set<Capability>> localCandidateMap = new HashMap(); + + // Find candidates for all requirements for the target module. + List<Requirement> reqs = module.getRequirements(); + for (Requirement req : reqs) + { + Set<Capability> candidates = state.getCandidates(module, req); + for (Iterator<Capability> itCandCap = candidates.iterator(); itCandCap.hasNext(); ) + { + Capability candCap = itCandCap.next(); + if (!candCap.getModule().isResolved()) + { + try + { + populateCandidates(state, candCap.getModule(), candidateMap, cycles); + } + catch (ResolveException ex) + { +System.out.println("RE: Candidate not resolveable: " + ex); + itCandCap.remove(); + } + } + } + if ((candidates.size() == 0) && !req.isOptional()) + { + throw new ResolveException("Unable to resolve " + module + + ": missing requirement " + req); + } + else if (candidates.size() > 0) + { + localCandidateMap.put(req, candidates); + } + } + + // Put candidates for all requirements into the global candidate map. + if (localCandidateMap.size() > 0) + { + candidateMap.putAll(localCandidateMap); + } + } + + private void findConsistentCandidates( + Module module, List<Requirement> incomingReqs, Map<Requirement, Set<Capability>> candidateMap, + Map<Module, Packages> modulePkgMap, Map<Module, Object> cycleMap) + { + if (m_isInvokeCount) + { + String methodName = new Exception().fillInStackTrace().getStackTrace()[0].getMethodName(); + Long count = m_invokeCounts.get(methodName); + count = (count == null) ? new Long(1) : new Long(count.longValue() + 1); + m_invokeCounts.put(methodName, count); + } + + // If the module is in the cycle map, then just return. + if (cycleMap.containsKey(module)) + { + return; + } + cycleMap.put(module, module); + +//System.out.println("+++ RESOLVING " + module); + calculateExportedPackages(module, incomingReqs, modulePkgMap); + + if (module.isResolved()) + { +// Packages pkgs = modulePkgMap.get(module); +// calculateResolvedPackages(module, incomingReqs, pkgs); + for (Wire wire : module.getWires()) + { + // Try to resolve the candidate. + findConsistentCandidates( + wire.getCapability().getModule(), + incomingReqs, + candidateMap, + modulePkgMap, + cycleMap); + + // If we are here, the candidate was consistent. Try to + // merge the candidate into the target module's packages. + mergeCandidatePackages( + module, + incomingReqs, + wire.getCapability(), + modulePkgMap, + candidateMap); + + // If we are here, we merged the candidate successfully, + // so we can continue with the next requirement + break; + } + } + else + { + List<Requirement> reqs = module.getRequirements(); + for (Requirement req : reqs) + { + // Get the candidates for the current requirement. + Set<Capability> candCaps = candidateMap.get(req); + // Optional requirements may not have any candidates. + if (candCaps == null) + { + continue; + } + + List<Requirement> outgoingReqs = new ArrayList<Requirement>(incomingReqs); + outgoingReqs.add(req); + + for (Iterator<Capability> it = candCaps.iterator(); it.hasNext(); ) + { + Capability candCap = it.next(); +System.out.println("+++ TRYING CAND " + candCap + " FOR " + req); + try + { + // Try to resolve the candidate. + findConsistentCandidates( + candCap.getModule(), + outgoingReqs, + candidateMap, + modulePkgMap, + cycleMap); + + // If we are here, the candidate was consistent. Try to + // merge the candidate into the target module's packages. + mergeCandidatePackages( + module, + outgoingReqs, + candCap, + modulePkgMap, + candidateMap); + + // If we are here, we merged the candidate successfully, + // so we can continue with the next requirement + break; + } + catch (ResolveException ex) + { +System.out.println("RE: " + ex); +ex.printStackTrace(); +// it.remove(); + if (!it.hasNext() && !req.isOptional()) + { +// candidateMap.remove(req); + throw new ResolveException("Unresolved constraint " + + req + " in " + module); + } + } + } + } + } + } + + private static void calculateExportedPackages( + Module module, List<Requirement> incomingReqs, Map<Module, Packages> modulePkgMap) + { + if (m_isInvokeCount) + { + String methodName = new Exception().fillInStackTrace().getStackTrace()[0].getMethodName(); + Long count = m_invokeCounts.get(methodName); + count = (count == null) ? new Long(1) : new Long(count.longValue() + 1); + m_invokeCounts.put(methodName, count); + } + + Packages packages = new Packages(); + + List<Capability> caps = module.getCapabilities(); + + if (caps.size() > 0) + { + for (int i = 0; i < caps.size(); i++) + { +// TODO: PROTO3 RESOLVER - Assume if a module imports the same package it +// exports that the import will overlap the export. + if (caps.get(i).getNamespace().equals(Capability.PACKAGE_NAMESPACE) + && !hasOverlappingImport(module, caps.get(i))) + { + packages.m_exportedPkgs.put( + (String) caps.get(i).getAttribute(Capability.PACKAGE_ATTR).getValue(), + new Blame(incomingReqs, caps.get(i))); + } + } + } + + modulePkgMap.put(module, packages); + } + + private static boolean hasOverlappingImport(Module module, Capability cap) + { + if (m_isInvokeCount) + { + String methodName = new Exception().fillInStackTrace().getStackTrace()[0].getMethodName(); + Long count = m_invokeCounts.get(methodName); + count = (count == null) ? new Long(1) : new Long(count.longValue() + 1); + m_invokeCounts.put(methodName, count); + } + + List<Requirement> reqs = module.getRequirements(); + for (int i = 0; i < reqs.size(); i++) + { + if (reqs.get(i).getNamespace().equals(Capability.PACKAGE_NAMESPACE) + && CapabilitySet.matches(cap, reqs.get(i).getFilter())) + { + return true; + } + } + return false; + } + + private void mergeCandidatePackages( + Module current, List<Requirement> outgoingReqs, + Capability candCap, Map<Module, Packages> modulePkgMap, + Map<Requirement, Set<Capability>> candidateMap) + { + if (m_isInvokeCount) + { + String methodName = new Exception().fillInStackTrace().getStackTrace()[0].getMethodName(); + Long count = m_invokeCounts.get(methodName); + count = (count == null) ? new Long(1) : new Long(count.longValue() + 1); + m_invokeCounts.put(methodName, count); + } + + if (candCap.getNamespace().equals(Capability.PACKAGE_NAMESPACE)) + { + mergeCandidatePackage( + current, false, new Blame(outgoingReqs, candCap), modulePkgMap, candidateMap); + } + else if (candCap.getNamespace().equals(Capability.MODULE_NAMESPACE)) + { + // Get the candidate's package space to determine which packages + // will be visible to the current module. + Packages candPkgs = modulePkgMap.get(candCap.getModule()); + +// TODO: PROTO3 RESOLVER - For now assume only exports, but eventually we also +// have to support re-exported packages. + for (Entry<String, Blame> entry : candPkgs.m_exportedPkgs.entrySet()) + { + mergeCandidatePackage( + current, + true, + new Blame(outgoingReqs, entry.getValue().m_cap), + modulePkgMap, + candidateMap); + } + } + } + + private void mergeCandidatePackage( + Module current, boolean requires, + Blame candBlame, Map<Module, Packages> modulePkgMap, + Map<Requirement, Set<Capability>> candidateMap) + { + if (m_isInvokeCount) + { + String methodName = new Exception().fillInStackTrace().getStackTrace()[0].getMethodName(); + Long count = m_invokeCounts.get(methodName); + count = (count == null) ? new Long(1) : new Long(count.longValue() + 1); + m_invokeCounts.put(methodName, count); + } + +// TODO: PROTO3 RESOLVER - Check for merging where module imports from itself, +// then it should be listed as an export. + if (candBlame.m_cap.getNamespace().equals(Capability.PACKAGE_NAMESPACE)) + { +System.out.println("+++ MERGING " + candBlame.m_cap + " INTO " + current); + String pkgName = (String) + candBlame.m_cap.getAttribute(Capability.PACKAGE_ATTR).getValue(); + + // Since this capability represents a package, it will become + // a hard constraint on the module's package space, so we need + // to make sure it doesn't conflict with any other hard constraints + // or any other uses constraints. + + // + // First, check to see if the capability conflicts with + // any existing hard constraints. + // + + Packages currentPkgs = modulePkgMap.get(current); + Blame currentExportedBlame = currentPkgs.m_exportedPkgs.get(pkgName); + Blame currentImportedBlame = currentPkgs.m_importedPkgs.get(pkgName); + List<Blame> currentRequiredBlames = currentPkgs.m_requiredPkgs.get(pkgName); + + if (!requires && + (((currentExportedBlame != null) && !currentExportedBlame.m_cap.equals(candBlame.m_cap)) + || ((currentImportedBlame != null) && !currentImportedBlame.m_cap.equals(candBlame.m_cap)) + || ((currentRequiredBlames != null) && !currentRequiredBlames.contains(candBlame)))) + { + throw new ResolveException("Constraint violation between " + + current + " and " + candBlame.m_cap.getModule() + + " for " + pkgName); + } + + // + // Second, check to see if the capability conflicts with + // any existing uses constraints + // + + Packages currentPkgsCopy = currentPkgs; + + if (!current.isResolved()) + { + List<Blame> currentUsedBlames = currentPkgs.m_usedPkgs.get(pkgName); + checkExistingUsesConstraints( + current, pkgName, currentUsedBlames, candBlame, modulePkgMap, candidateMap); + + // + // Last, check to see if any uses constraints implied by the + // candidate conflict with any of the existing hard constraints. + // + + // For now, create a copy of the module's package space and + // add the current candidate to the imported packages. + currentPkgsCopy = new Packages(currentPkgs); + } + + if (requires) + { + if (currentRequiredBlames == null) + { + currentRequiredBlames = new ArrayList<Blame>(); + currentPkgsCopy.m_requiredPkgs.put(pkgName, currentRequiredBlames); + } +// TODO: PROTO2 RESOLVER - This is potentially modifying the original, we need to modify a copy. + currentRequiredBlames.add(candBlame); + } + else + { + currentPkgsCopy.m_importedPkgs.put(pkgName, candBlame); + } +// if not resolved + // Verify and merge the candidate's transitive uses constraints. + verifyAndMergeUses( + current, + currentPkgsCopy, + candBlame, + modulePkgMap, + candidateMap, + new HashMap<String, List<Module>>()); + + // If we are here, then there were no conflict, so we should update + // the module's package space. + if (!current.isResolved()) + { + currentPkgs.m_exportedPkgs.putAll(currentPkgsCopy.m_exportedPkgs); + currentPkgs.m_importedPkgs.putAll(currentPkgsCopy.m_importedPkgs); + currentPkgs.m_requiredPkgs.putAll(currentPkgsCopy.m_requiredPkgs); + currentPkgs.m_usedPkgs.putAll(currentPkgsCopy.m_usedPkgs); + } +dumpModulePkgs(current, currentPkgs); + } + } + + private void checkExistingUsesConstraints( + Module current, String pkgName, List<Blame> currentUsedBlames, + Blame candBlame, Map<Module, Packages> modulePkgMap, + Map<Requirement, Set<Capability>> candidateMap) + { + for (int i = 0; (currentUsedBlames != null) && (i < currentUsedBlames.size()); i++) + { +//System.out.println("+++ CHECK " + candBlame + " IN EXISTING " + currentUsedBlames.get(i)); + if (!isCompatible(currentUsedBlames.get(i).m_cap, candBlame.m_cap, modulePkgMap)) + { + // Try to remove the previously selected candidate associated + // with the requirement blamed for adding the constraint. This + // blamed requirement may be null if the bundle itself is + // exports the package imposing the uses constraint. + if ((currentUsedBlames.get(i).m_reqs != null) + && (currentUsedBlames.get(i).m_reqs.size() != 0)) + { + // Permutate the candidate map. + for (int reqIdx = 0; reqIdx < currentUsedBlames.get(i).m_reqs.size(); reqIdx++) + { + Map<Requirement, Set<Capability>> copy = copyCandidateMap(candidateMap); + Set<Capability> candidates = + copy.get(currentUsedBlames.get(i).m_reqs.get(reqIdx)); + Iterator it = candidates.iterator(); + it.next(); + it.remove(); +// TODO: PROTO3 RESOLVER - We could check before doing the candidate map copy. + if (candidates.size() > 0) + { + m_candidatePermutations.add(copy); + } + } + } + + throw new ResolveException("Constraint violation for package '" + pkgName + + "' when resolving module " + current + + " between existing constraint " + + currentUsedBlames.get(i) + + " and candidate constraint " + + candBlame); + } + } + } + +// TODO: PROTO3 RESOLVER - We end up with duplicates in uses constraints, +// see scenario 2 for an example. + private void verifyAndMergeUses( + Module current, Packages currentPkgs, + Blame candBlame, Map<Module, Packages> modulePkgMap, + Map<Requirement, Set<Capability>> candidateMap, + Map<String, List<Module>> cycleMap) + { + if (m_isInvokeCount) + { + String methodName = new Exception().fillInStackTrace().getStackTrace()[0].getMethodName(); + Long count = m_invokeCounts.get(methodName); + count = (count == null) ? new Long(1) : new Long(count.longValue() + 1); + m_invokeCounts.put(methodName, count); + } + + // Check for cycles. + String pkgName = (String) + candBlame.m_cap.getAttribute(Capability.PACKAGE_ATTR).getValue(); + List<Module> list = cycleMap.get(pkgName); + if ((list != null) && list.contains(current)) + { + return; + } + list = (list == null) ? new ArrayList<Module>() : list; + list.add(current); + cycleMap.put(pkgName, list); + +//System.out.println("+++ VERIFYING USES " + current + " FOR " + candBlame); + for (Capability candSourceCap : getPackageSources(candBlame.m_cap, modulePkgMap, new ArrayList<Capability>())) + { + for (String usedPkgName : candSourceCap.getUses()) + { + Blame currentExportedBlame = currentPkgs.m_exportedPkgs.get(usedPkgName); + Blame currentImportedBlame = currentPkgs.m_importedPkgs.get(usedPkgName); +// TODO: PROTO3 RESOLVER - What do we do with required packages? + List<Blame> currentRequiredBlames = currentPkgs.m_requiredPkgs.get(usedPkgName); + + Packages candSourcePkgs = modulePkgMap.get(candSourceCap.getModule()); +System.out.println("+++ candSourceCap " + candSourceCap); +System.out.println("+++ candSourceCap.getModule() " + candSourceCap.getModule() + " (" + candSourceCap.getModule().isResolved() + ")"); +System.out.println("+++ candSourcePkgs " + candSourcePkgs); +System.out.println("+++ candSourcePkgs.m_exportedPkgs " + candSourcePkgs.m_exportedPkgs); + Blame candSourceBlame = candSourcePkgs.m_exportedPkgs.get(usedPkgName); + candSourceBlame = (candSourceBlame != null) + ? candSourceBlame + : candSourcePkgs.m_importedPkgs.get(usedPkgName); +// sourceCap = (sourceCap != null) +// ? sourceCap +// : sourcePkgs.m_requiredPkgs.get(usedPkgName); + + // If the candidate doesn't actually have a constraint for + // the used package, then just ignore it since this is likely + // an error in its metadata. + if (candSourceBlame == null) + { + return; + } + + // If there is no current mapping for this package, then + // we can just return. + if ((currentExportedBlame == null) + && (currentImportedBlame == null) + && (currentRequiredBlames == null)) + { + List<Blame> usedCaps = currentPkgs.m_usedPkgs.get(usedPkgName); + if (usedCaps == null) + { + usedCaps = new ArrayList<Blame>(); + currentPkgs.m_usedPkgs.put(usedPkgName, usedCaps); + } +System.out.println("+++ MERGING CB " + candBlame + " SB " + candSourceBlame); +// usedCaps.add(new Blame(candBlame.m_reqs, sourceBlame.m_cap)); + usedCaps.add(candSourceBlame); + return; + } + else if (!current.isResolved()) + { + if ((currentExportedBlame != null) + && !isCompatible(currentExportedBlame.m_cap, candSourceBlame.m_cap, modulePkgMap)) + { + throw new ResolveException( + "Constraint violation for package '" + usedPkgName + + "' when resolving module " + current + + " between existing constraint " + + currentExportedBlame + + " and candidate constraint " + + candSourceBlame); + } + else if ((currentImportedBlame != null) + && !isCompatible(currentImportedBlame.m_cap, candSourceBlame.m_cap, modulePkgMap)) + { + //System.out.println("+++ CIB " + currentImportedBlame + " SB " + sourceBlame); + // Try to remove the previously selected candidate associated + // with the requirement blamed for adding the constraint. This + // Permutate the candidate map. + if (currentImportedBlame.m_reqs.size() != 0) + { + // Permutate the candidate map. + for (int reqIdx = 0; reqIdx < currentImportedBlame.m_reqs.size(); reqIdx++) + { + Map<Requirement, Set<Capability>> copy = copyCandidateMap(candidateMap); + Set<Capability> candidates = + copy.get(currentImportedBlame.m_reqs.get(reqIdx)); + Iterator it = candidates.iterator(); + it.next(); + it.remove(); + // TODO: PROTO3 RESOLVER - We could check before doing the candidate map copy. + if (candidates.size() > 0) + { + m_candidatePermutations.add(copy); + } + } + } + + throw new ResolveException( + "Constraint violation for package '" + usedPkgName + + "' when resolving module " + current + + " between existing constraint " + + currentImportedBlame + + " and candidate constraint " + + candSourceBlame); + } + } + } + } + } + + private static boolean isCompatible( + Capability currentCap, Capability candCap, Map<Module, Packages> modulePkgMap) + { + if ((currentCap != null) && (candCap != null)) + { + List<Capability> currentSources = getPackageSources(currentCap, modulePkgMap, new ArrayList<Capability>()); + List<Capability> candSources = getPackageSources(candCap, modulePkgMap, new ArrayList<Capability>()); +//System.out.println("+++ currentSources " + currentSources + " - candSources " + candSources); + return currentSources.containsAll(candSources) || candSources.containsAll(currentSources); + } + return true; + } + + private static List<Capability> getPackageSources( + Capability cap, Map<Module, Packages> modulePkgMap, List<Capability> sources) + { + if (cap.getNamespace().equals(Capability.PACKAGE_NAMESPACE)) + { + Packages pkgs = modulePkgMap.get(cap.getModule()); + sources.add(cap); + String pkgName = cap.getAttribute(Capability.PACKAGE_ATTR).getValue().toString(); + List<Blame> required = pkgs.m_requiredPkgs.get(pkgName); + if (required != null) + { + for (Blame blame : required) + { + getPackageSources(blame.m_cap, modulePkgMap, sources); + } + } + } + + return sources; + } + + private static void calculateResolvedPackages( + Module module, List<Requirement> incomingReqs, Packages pkgs) + { + for (Wire wire : module.getWires()) + { + if (wire.getCapability().getNamespace().equals(Capability.PACKAGE_NAMESPACE)) + { + pkgs.m_importedPkgs.put( + (String) wire.getCapability().getAttribute(Capability.PACKAGE_ATTR).getValue(), + new Blame(incomingReqs, wire.getCapability())); + calculateResolvedUses(wire.getCapability(), pkgs.m_usedPkgs); + } + else if (wire.getCapability().getNamespace().equals(Capability.MODULE_NAMESPACE)) + { + for (Capability cap : wire.getCapability().getModule().getCapabilities()) + { + if (cap.getNamespace().equals(Capability.PACKAGE_ATTR)) + { + String pkgName = (String) cap.getAttribute(Capability.PACKAGE_ATTR).getValue(); + List<Blame> requiredBlames = pkgs.m_requiredPkgs.get(pkgName); + if (requiredBlames == null) + { + requiredBlames = new ArrayList<Blame>(); + pkgs.m_requiredPkgs.put(pkgName, requiredBlames); + } + requiredBlames.add(new Blame(incomingReqs, cap)); + calculateResolvedUses(wire.getCapability(), pkgs.m_usedPkgs); + } + } + } + } + } + + private static void calculateResolvedUses(Capability cap, Map<String, List<Blame>> usedPkgs) + { + } + + private static Map<Requirement, Set<Capability>> copyCandidateMap( + Map<Requirement, Set<Capability>> candidateMap) + { + Map<Requirement, Set<Capability>> copy = + new HashMap<Requirement, Set<Capability>>(); + for (Entry<Requirement, Set<Capability>> entry : candidateMap.entrySet()) + { + Set<Capability> candidates = new TreeSet(new CandidateComparator()); + candidates.addAll(entry.getValue()); + copy.put(entry.getKey(), candidates); + } + return copy; + } + + private static Map<Module, List<Wire>> populateWireMap( + Module module, Map<Module, Packages> modulePkgMap, + Map<Module, List<Wire>> wireMap) + { + if (m_isInvokeCount) + { + String methodName = new Exception().fillInStackTrace().getStackTrace()[0].getMethodName(); + Long count = m_invokeCounts.get(methodName); + count = (count == null) ? new Long(1) : new Long(count.longValue() + 1); + m_invokeCounts.put(methodName, count); + } + + if (!module.isResolved() && (wireMap.get(module) == null)) + { + List<Wire> moduleWires = new ArrayList<Wire>(); + wireMap.put(module, moduleWires); + + Packages pkgs = modulePkgMap.get(module); + for (Entry<String, Blame> entry : pkgs.m_importedPkgs.entrySet()) + { + if (!entry.getValue().m_cap.getModule().isResolved()) + { + populateWireMap(entry.getValue().m_cap.getModule(), modulePkgMap, wireMap); + } + + // Ignore modules that import themselves. + if (!module.equals(entry.getValue().m_cap.getModule())) + { + moduleWires.add( + new Wire(module, + entry.getValue().m_reqs.get(entry.getValue().m_reqs.size() - 1), + entry.getValue().m_cap.getModule(), + entry.getValue().m_cap)); + } + } + List<Requirement> rbReqs = new ArrayList<Requirement>(); + for (Requirement req : module.getRequirements()) + { + if (req.getNamespace().equals(Capability.MODULE_NAMESPACE)) + { + rbReqs.add(req); + } + } + if (!rbReqs.isEmpty()) + { + Map<Requirement, Capability> rbMap = new HashMap<Requirement, Capability>(); + for (Entry<String, List<Blame>> entry : pkgs.m_requiredPkgs.entrySet()) + { + for (Blame blame : entry.getValue()) + { + for (Requirement rbReq : rbReqs) + { + if (blame.m_reqs.get(blame.m_reqs.size() - 1).equals(rbReq)) + { + rbMap.put(rbReq, getModuleCapability(blame.m_cap.getModule())); + if (!blame.m_cap.getModule().isResolved()) + { + populateWireMap( + blame.m_cap.getModule(), modulePkgMap, wireMap); + } + break; + } + } + } + + // Ignore modules that import themselves. + for (Entry<Requirement, Capability> rbEntry : rbMap.entrySet()) + { + if (!module.equals(rbEntry.getValue().getModule())) + { + moduleWires.add( + new Wire(module, + rbEntry.getKey(), + rbEntry.getValue().getModule(), + rbEntry.getValue())); + } + } + } + } + } + return wireMap; + } + + private static Capability getModuleCapability(Module module) + { + for (Capability cap : module.getCapabilities()) + { + if (cap.getNamespace().equals(Capability.MODULE_NAMESPACE)) + { + return cap; + } + } + return null; + } + + private static class Packages + { + public final Map<String, Blame> m_exportedPkgs + = new HashMap<String, Blame>(); + public final Map<String, Blame> m_importedPkgs + = new HashMap<String, Blame>(); + public final Map<String, List<Blame>> m_requiredPkgs + = new HashMap<String, List<Blame>>(); + public final Map<String, List<Blame>> m_usedPkgs + = new HashMap<String, List<Blame>>(); + + public Packages() + { + } + + public Packages(Packages packages) + { + m_exportedPkgs.putAll(packages.m_exportedPkgs); + m_importedPkgs.putAll(packages.m_importedPkgs); + m_requiredPkgs.putAll(packages.m_requiredPkgs); + m_usedPkgs.putAll(packages.m_usedPkgs); + } + } + + private static class Blame + { + public final List<Requirement> m_reqs; + public final Capability m_cap; + + public Blame(List<Requirement> reqs, Capability cap) + { + m_reqs = reqs; + m_cap = cap; + } + + public String toString() + { + return m_cap.getModule() + "." + m_cap.getAttribute(Capability.PACKAGE_ATTR).getValue() + + " BLAMED ON " + m_reqs; + } + + public boolean equals(Object o) + { + return (o instanceof Blame) && m_reqs.equals(((Blame) o).m_reqs) + && m_cap.equals(((Blame) o).m_cap); + } + } +} \ No newline at end of file
Added: felix/sandbox/rickhall/framework-proto/src/main/java/org/apache/felix/framework/resolver/ResolverStateImpl.java URL: http://svn.apache.org/viewvc/felix/sandbox/rickhall/framework-proto/src/main/java/org/apache/felix/framework/resolver/ResolverStateImpl.java?rev=901272&view=auto ============================================================================== --- felix/sandbox/rickhall/framework-proto/src/main/java/org/apache/felix/framework/resolver/ResolverStateImpl.java (added) +++ felix/sandbox/rickhall/framework-proto/src/main/java/org/apache/felix/framework/resolver/ResolverStateImpl.java Wed Jan 20 16:44:13 2010 @@ -0,0 +1,101 @@ +/* + * 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.framework.resolver; + +import java.util.ArrayList; +import java.util.List; +import java.util.Set; +import java.util.TreeSet; +import org.apache.felix.resolver.Resolver.ResolverState; +import org.apache.felix.resolver.cs.Capability; +import org.apache.felix.resolver.cs.CapabilitySet; +import org.apache.felix.resolver.cs.Requirement; +import org.apache.felix.resolver.manifestparser.Constants; + +public class ResolverStateImpl implements ResolverState +{ + private final List<Module> m_modules; + private final CapabilitySet m_pkgCapSet; + private final CapabilitySet m_modCapSet; + + public ResolverStateImpl(List<Module> modules) + { + m_modules = modules; + + List indices = new ArrayList(); + indices.add(Constants.BUNDLE_SYMBOLICNAME_ATTRIBUTE); + m_modCapSet = new CapabilitySet(indices); + + indices = new ArrayList(); + indices.add(Capability.PACKAGE_ATTR); + m_pkgCapSet = new CapabilitySet(indices); + + for (int modIdx = 0; modIdx < m_modules.size(); modIdx++) + { + List<Capability> caps = m_modules.get(modIdx).getCapabilities(); + for (int capIdx = 0; capIdx < caps.size(); capIdx++) + { + if (caps.get(capIdx).getNamespace().equals(Capability.MODULE_NAMESPACE)) + { + m_modCapSet.addCapability(caps.get(capIdx)); + } + else if (caps.get(capIdx).getNamespace().equals(Capability.PACKAGE_NAMESPACE)) + { + m_pkgCapSet.addCapability(caps.get(capIdx)); + } + else + { + System.err.println( + "Ignoring unknown capability: " + caps.get(capIdx).getNamespace()); + } + } + } + } + + public List<Module> getModules() + { + return m_modules; + } + + public Set<Capability> getCandidates(Module module, Requirement req) + { + return getUnresolvedCandidates(module, req); + } + + private Set<Capability> getUnresolvedCandidates(Module module, Requirement req) + { + Set<Capability> result = new TreeSet(new CandidateComparator()); + + if (req.getNamespace().equals(Capability.MODULE_NAMESPACE)) + { + result.addAll(m_modCapSet.match(req.getFilter())); + } + else if (req.getNamespace().equals(Capability.PACKAGE_NAMESPACE)) + { + result.addAll(m_pkgCapSet.match(req.getFilter())); + } + + return result; + } + + private Set<Capability> getResolvedCandidates(Module module, Requirement req) + { + throw new UnsupportedOperationException("Not supported yet."); + } +} \ No newline at end of file Added: felix/sandbox/rickhall/framework-proto/src/main/java/org/apache/felix/framework/resolver/StatefulResolver.java URL: http://svn.apache.org/viewvc/felix/sandbox/rickhall/framework-proto/src/main/java/org/apache/felix/framework/resolver/StatefulResolver.java?rev=901272&view=auto ============================================================================== --- felix/sandbox/rickhall/framework-proto/src/main/java/org/apache/felix/framework/resolver/StatefulResolver.java (added) +++ felix/sandbox/rickhall/framework-proto/src/main/java/org/apache/felix/framework/resolver/StatefulResolver.java Wed Jan 20 16:44:13 2010 @@ -0,0 +1,74 @@ +/* + * 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.framework.resolver; + +import java.util.List; +import java.util.Map; +import java.util.Map.Entry; + +public class StatefulResolver +{ + private final Resolver m_resolver; + private final ResolverStateImpl m_state; + + public StatefulResolver(Resolver resolver, ResolverStateImpl state) + { + m_resolver = resolver; + m_state = state; + } + + public ResolverStateImpl getState() + { + return m_state; + } + + public void resolve(Module module) + { + System.out.println("Target: " + module + " (" + module.getRequirements().size() + ")"); + long starttime = System.currentTimeMillis(); + Map<Module, List<Wire>> wireMap = m_resolver.resolve(m_state, module); + long endtime = System.currentTimeMillis(); + System.out.println("Resolve time: " + (endtime - starttime)); + System.out.println("Modules resolved: " + wireMap.size()); + + // Mark all modules as resolved. + markResolvedModules(wireMap); + } + + private void markResolvedModules(Map<Module, List<Wire>> wireMap) + { + if (wireMap != null) + { + // Iterate over the map to mark the modules as resolved and + // update our resolver data structures. + for (Entry<Module, List<Wire>> entry : wireMap.entrySet()) + { + // Only add wires attribute if some exist; export + // only modules may not have wires. +// TODO: RESOLVER - Seems stupid that we package these up as wires to tear them apart. + List<Wire> wires = entry.getValue(); + for (int wireIdx = 0; wireIdx < wires.size(); wireIdx++) + { + System.out.println("WIRE: " + wires.get(wireIdx)); + } + entry.getKey().resolve(wires); + } + } + } +} \ No newline at end of file Modified: felix/sandbox/rickhall/framework-proto/src/main/java/org/apache/felix/framework/util/Util.java URL: http://svn.apache.org/viewvc/felix/sandbox/rickhall/framework-proto/src/main/java/org/apache/felix/framework/util/Util.java?rev=901272&r1=901271&r2=901272&view=diff ============================================================================== --- felix/sandbox/rickhall/framework-proto/src/main/java/org/apache/felix/framework/util/Util.java (original) +++ felix/sandbox/rickhall/framework-proto/src/main/java/org/apache/felix/framework/util/Util.java Wed Jan 20 16:44:13 2010 @@ -25,9 +25,12 @@ import java.util.List; import java.util.Map; import java.util.Properties; +import org.apache.felix.framework.candidateset.Capability; +import org.apache.felix.framework.candidateset.CapabilitySet; +import org.apache.felix.framework.candidateset.Module; +import org.apache.felix.framework.candidateset.Requirement; +import org.apache.felix.framework.candidateset.Wire; -import org.apache.felix.framework.util.manifestparser.Capability; -import org.apache.felix.moduleloader.*; import org.osgi.framework.Bundle; import org.osgi.framework.Constants; import org.osgi.framework.ServiceReference; @@ -229,15 +232,15 @@ return allow; } - public static ICapability getSatisfyingCapability(IModule m, IRequirement req) + public static Capability getSatisfyingCapability(Module m, Requirement req) { - ICapability[] caps = m.getCapabilities(); - for (int i = 0; (caps != null) && (i < caps.length); i++) + List<Capability> caps = m.getCapabilities(); + for (int i = 0; (caps != null) && (i < caps.size()); i++) { - if (caps[i].getNamespace().equals(req.getNamespace()) && - req.isSatisfied(caps[i])) + if (caps.get(i).getNamespace().equals(req.getNamespace()) + && CapabilitySet.matches(caps.get(i), req.getFilter())) { - return caps[i]; + return caps.get(i); } } return null; @@ -250,29 +253,29 @@ * @param namespace capability namespace * @return array of matching capabilities or empty if none found */ - public static ICapability[] getCapabilityByNamespace(IModule module, String namespace) + public static List<Capability> getCapabilityByNamespace(Module module, String namespace) { - final List matching = new ArrayList(); - final ICapability[] caps = module.getCapabilities(); - for (int capIdx = 0; (caps != null) && (capIdx < caps.length); capIdx++) + final List<Capability> matching = new ArrayList(); + final List<Capability> caps = module.getCapabilities(); + for (int capIdx = 0; (caps != null) && (capIdx < caps.size()); capIdx++) { - if (caps[capIdx].getNamespace().equals(namespace)) + if (caps.get(capIdx).getNamespace().equals(namespace)) { - matching.add(caps[capIdx]); + matching.add(caps.get(capIdx)); } } - return (ICapability[]) matching.toArray(new ICapability[matching.size()]); + return matching; } - public static IWire getWire(IModule m, String name) + public static Wire getWire(Module m, String name) { - IWire[] wires = m.getWires(); - for (int i = 0; (wires != null) && (i < wires.length); i++) + List<Wire> wires = m.getWires(); + for (int i = 0; (wires != null) && (i < wires.size()); i++) { - if (wires[i].getCapability().getNamespace().equals(ICapability.PACKAGE_NAMESPACE) && - ((Capability) wires[i].getCapability()).getPackageName().equals(name)) + if (wires.get(i).getCapability().getNamespace().equals(Capability.PACKAGE_NAMESPACE) && + wires.get(i).getCapability().getAttribute(Capability.PACKAGE_ATTR).getValue().equals(name)) { - return wires[i]; + return wires.get(i); } } return null; @@ -522,13 +525,12 @@ * @return <code>true</code> if the module declares a fragment host, <code>false</code> * otherwise. */ - public static boolean isFragment(IModule module) + public static boolean isFragment(Module module) { Map headerMap = module.getHeaders(); return headerMap.containsKey(Constants.FRAGMENT_HOST); } - // // The following substring-related code was lifted and modified // from the LDAP parser code. Modified: felix/sandbox/rickhall/framework-proto/src/main/java/org/apache/felix/framework/util/manifestparser/ManifestParser.java URL: http://svn.apache.org/viewvc/felix/sandbox/rickhall/framework-proto/src/main/java/org/apache/felix/framework/util/manifestparser/ManifestParser.java?rev=901272&r1=901271&r2=901272&view=diff ============================================================================== --- felix/sandbox/rickhall/framework-proto/src/main/java/org/apache/felix/framework/util/manifestparser/ManifestParser.java (original) +++ felix/sandbox/rickhall/framework-proto/src/main/java/org/apache/felix/framework/util/manifestparser/ManifestParser.java Wed Jan 20 16:44:13 2010 @@ -736,18 +736,18 @@ * @return <tt>null</tt> if there are no native libraries, a zero-length * array if no libraries matched, or an array of selected libraries. **/ - public R4Library[] getLibraries() + public List<R4Library> getLibraries() { - R4Library[] libs = null; + ArrayList<R4Library> libs = null; try { R4LibraryClause clause = getSelectedLibraryClause(); if (clause != null) { String[] entries = clause.getLibraryEntries(); - libs = new R4Library[entries.length]; + libs = new ArrayList<R4Library>(entries.length); int current = 0; - for (int i = 0; i < libs.length; i++) + for (int i = 0; i < libs.size(); i++) { String name = getName(entries[i]); boolean found = false; @@ -757,23 +757,18 @@ } if (!found) { - libs[current++] = new R4Library( + libs.add(new R4Library( clause.getLibraryEntries()[i], clause.getOSNames(), clause.getProcessors(), clause.getOSVersions(), - clause.getLanguages(), clause.getSelectionFilter()); + clause.getLanguages(), clause.getSelectionFilter())); } } - if (current < libs.length) - { - R4Library[] tmp = new R4Library[current]; - System.arraycopy(libs, 0, tmp, 0, current); - libs = tmp; - } + libs.trimToSize(); } } catch (Exception ex) { - libs = new R4Library[0]; + libs = new ArrayList<R4Library>(0); } return libs; } Added: felix/sandbox/rickhall/framework-proto/src/main/java/org/apache/felix/framework/util/manifestparser/ParsedHeaderClause.java URL: http://svn.apache.org/viewvc/felix/sandbox/rickhall/framework-proto/src/main/java/org/apache/felix/framework/util/manifestparser/ParsedHeaderClause.java?rev=901272&view=auto ============================================================================== --- felix/sandbox/rickhall/framework-proto/src/main/java/org/apache/felix/framework/util/manifestparser/ParsedHeaderClause.java (added) +++ felix/sandbox/rickhall/framework-proto/src/main/java/org/apache/felix/framework/util/manifestparser/ParsedHeaderClause.java Wed Jan 20 16:44:13 2010 @@ -0,0 +1,37 @@ +/* + * 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.framework.util.manifestparser; + +import java.util.List; +import org.apache.felix.framework.candidateset.Attribute; +import org.apache.felix.framework.candidateset.Directive; + +public class ParsedHeaderClause +{ + public final List<String> m_paths; + public final List<Directive> m_dirs; + public final List<Attribute> m_attrs; + + public ParsedHeaderClause(List<String> paths, List<Directive> dirs, List<Attribute> attrs) + { + m_paths = paths; + m_dirs = dirs; + m_attrs = attrs; + } +} \ No newline at end of file
