Author: rickhall
Date: Mon Jan 4 21:55:22 2010
New Revision: 895797
URL: http://svn.apache.org/viewvc?rev=895797&view=rev
Log:
Another resolver algorithm prototype.
Added:
felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/proto3/
felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/proto3/Proto3Resolver.java
Modified:
felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/Main.java
felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/manifestparser/Main.java
Modified:
felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/Main.java
URL:
http://svn.apache.org/viewvc/felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/Main.java?rev=895797&r1=895796&r2=895797&view=diff
==============================================================================
---
felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/Main.java
(original)
+++
felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/Main.java
Mon Jan 4 21:55:22 2010
@@ -27,7 +27,7 @@
import java.util.Map.Entry;
import org.apache.felix.resolver.cs.Capability;
import org.apache.felix.resolver.felix.FelixResolver;
-import org.apache.felix.resolver.proto2.Proto2Resolver;
+import org.apache.felix.resolver.proto3.Proto3Resolver;
import org.apache.felix.resolver.prototype.ProtoResolver;
public class Main
@@ -53,7 +53,7 @@
}
else if (args[i].equals("-proto"))
{
- legacy = true;
+ proto = true;
}
else
{
@@ -75,7 +75,7 @@
}
else
{
- resolver = new Proto2Resolver(moduleList);
+ resolver = new Proto3Resolver(moduleList);
}
try
@@ -651,6 +651,10 @@
return target;
}
+ // SOLUTION:
+ // A: foo->B, bar->C, woz->E
+ // B: woz->E
+ // C: woz->E
private static Module scenario13(List<Module> moduleList)
{
Module m, target;
@@ -660,17 +664,17 @@
target = (m = new Module("A"))
.requiring(new
RequirementImpl(Capability.PACKAGE_NAMESPACE).with("package=foo"))
.requiring(new
RequirementImpl(Capability.PACKAGE_NAMESPACE).with("package=bar"))
- .requiring(new
RequirementImpl(Capability.PACKAGE_NAMESPACE).with("package=woz")));
+ .requiring(new
RequirementImpl(Capability.PACKAGE_NAMESPACE).with("package=woz").with("version=2.0.0")));
// Bundle B
moduleList.add(
(m = new Module("B"))
.providing(new CapabilityImpl(m,
Capability.PACKAGE_NAMESPACE).with("package=foo").using("woz"))
- .requiring(new
RequirementImpl(Capability.PACKAGE_NAMESPACE).with("package=woz").with("version=1.0.0")));
+ .requiring(new
RequirementImpl(Capability.PACKAGE_NAMESPACE).with("package=woz")));
// Bundle C
moduleList.add(
(m = new Module("C"))
.providing(new CapabilityImpl(m,
Capability.PACKAGE_NAMESPACE).with("package=bar").using("woz"))
- .requiring(new
RequirementImpl(Capability.PACKAGE_NAMESPACE).with("package=woz").with("version=2.0.0")));
+ .requiring(new
RequirementImpl(Capability.PACKAGE_NAMESPACE).with("package=woz")));
// Bundle D
moduleList.add(
(m = new Module("D"))
@@ -682,4 +686,187 @@
return target;
}
+
+ private static Module scenario14(List<Module> moduleList)
+ {
+ Module m, target;
+
+ // Bundle A
+ moduleList.add(
+ target = (m = new Module("A"))
+ .providing(new CapabilityImpl(m,
Capability.PACKAGE_NAMESPACE).with("package=bar"))
+ .requiring(new
RequirementImpl(Capability.MODULE_NAMESPACE).with("bundle-symbolic-name=B"))
+ .requiring(new
RequirementImpl(Capability.MODULE_NAMESPACE).with("bundle-symbolic-name=C")));
+ // Bundle B
+ moduleList.add(
+ (m = new Module("B"))
+ .providing(new CapabilityImpl(m,
Capability.MODULE_NAMESPACE).with("bundle-symbolic-name=B"))
+ .providing(new CapabilityImpl(m,
Capability.PACKAGE_NAMESPACE).with("package=bar")));
+ // Bundle C
+ moduleList.add(
+ (m = new Module("C"))
+ .providing(new CapabilityImpl(m,
Capability.MODULE_NAMESPACE).with("bundle-symbolic-name=C"))
+ .providing(new CapabilityImpl(m,
Capability.PACKAGE_NAMESPACE).with("package=bar")));
+
+ return target;
+ }
+
+ private static Module scenario15(List<Module> moduleList)
+ {
+ Module m, target;
+
+ // Bundle A
+ moduleList.add(
+ target = (m = new Module("A"))
+ .requiring(new
RequirementImpl(Capability.PACKAGE_NAMESPACE).with("package=bar").with("vendor=B"))
+ .requiring(new
RequirementImpl(Capability.PACKAGE_NAMESPACE).with("package=foo").with("vendor=E")));
+ // Bundle B
+ moduleList.add(
+ (m = new Module("B"))
+ .providing(new CapabilityImpl(m,
Capability.PACKAGE_NAMESPACE).with("package=bar").with("vendor=B"))
+ .requiring(new
RequirementImpl(Capability.MODULE_NAMESPACE).with("bundle-symbolic-name=C"))
+ .requiring(new
RequirementImpl(Capability.MODULE_NAMESPACE).with("bundle-symbolic-name=D")));
+ // Bundle C
+ moduleList.add(
+ (m = new Module("C"))
+ .providing(new CapabilityImpl(m,
Capability.MODULE_NAMESPACE).with("bundle-symbolic-name=C"))
+ .providing(new CapabilityImpl(m,
Capability.PACKAGE_NAMESPACE).with("package=bar")));
+ // Bundle D
+ moduleList.add(
+ (m = new Module("D"))
+ .providing(new CapabilityImpl(m,
Capability.MODULE_NAMESPACE).with("bundle-symbolic-name=D"))
+ .providing(new CapabilityImpl(m,
Capability.PACKAGE_NAMESPACE).with("package=bar").using("foo"))
+ .requiring(new
RequirementImpl(Capability.PACKAGE_NAMESPACE).with("package=foo")));
+ // Bundle E
+ moduleList.add(
+ (m = new Module("E"))
+ .providing(new CapabilityImpl(m,
Capability.PACKAGE_NAMESPACE).with("package=foo")));
+ // Bundle F
+ moduleList.add(
+ (m = new Module("F"))
+ .providing(new CapabilityImpl(m,
Capability.PACKAGE_NAMESPACE).with("package=foo").with("vendor=E")));
+
+ return target;
+ }
+
+ private static Module scenario16(List<Module> moduleList)
+ {
+ Module m, target;
+
+ // Bundle A
+ moduleList.add(
+ target = (m = new Module("A"))
+ .requiring(new
RequirementImpl(Capability.PACKAGE_NAMESPACE).with("package=bar").with("vendor=C"))
+ .requiring(new
RequirementImpl(Capability.PACKAGE_NAMESPACE).with("package=foo")));
+ // Bundle B
+ moduleList.add(
+ (m = new Module("B"))
+ .providing(new CapabilityImpl(m,
Capability.PACKAGE_NAMESPACE).with("package=foo").using("bar"))
+ .providing(new CapabilityImpl(m,
Capability.PACKAGE_NAMESPACE).with("package=bar"))
+ .requiring(new
RequirementImpl(Capability.MODULE_NAMESPACE).with("bundle-symbolic-name=C"))
+ .requiring(new
RequirementImpl(Capability.MODULE_NAMESPACE).with("bundle-symbolic-name=D")));
+ // Bundle C
+ moduleList.add(
+ (m = new Module("C"))
+ .providing(new CapabilityImpl(m,
Capability.MODULE_NAMESPACE).with("bundle-symbolic-name=C"))
+ .providing(new CapabilityImpl(m,
Capability.PACKAGE_NAMESPACE).with("package=bar").with("vendor=C")));
+ // Bundle D
+ moduleList.add(
+ (m = new Module("D"))
+ .providing(new CapabilityImpl(m,
Capability.MODULE_NAMESPACE).with("bundle-symbolic-name=D"))
+ .providing(new CapabilityImpl(m,
Capability.PACKAGE_NAMESPACE).with("package=bar")));
+
+ return target;
+ }
+
+ private static Module scenario17(List<Module> moduleList)
+ {
+ Module m, target;
+
+ // Bundle A
+ moduleList.add(
+ target = (m = new Module("A"))
+ .requiring(new
RequirementImpl(Capability.PACKAGE_NAMESPACE).with("package=foo"))
+ .requiring(new
RequirementImpl(Capability.PACKAGE_NAMESPACE).with("package=woz"))
+ .requiring(new
RequirementImpl(Capability.PACKAGE_NAMESPACE).with("package=bar")));
+ // Bundle B
+ moduleList.add(
+ (m = new Module("B"))
+ .providing(new CapabilityImpl(m,
Capability.PACKAGE_NAMESPACE).with("package=foo").using("bar"))
+ .providing(new CapabilityImpl(m,
Capability.PACKAGE_NAMESPACE).with("package=bar"))
+ .requiring(new
RequirementImpl(Capability.MODULE_NAMESPACE).with("bundle-symbolic-name=C"))
+ .requiring(new
RequirementImpl(Capability.MODULE_NAMESPACE).with("bundle-symbolic-name=D")));
+ // Bundle C
+ moduleList.add(
+ (m = new Module("C"))
+ .providing(new CapabilityImpl(m,
Capability.MODULE_NAMESPACE).with("bundle-symbolic-name=C"))
+ .providing(new CapabilityImpl(m,
Capability.PACKAGE_NAMESPACE).with("package=bar").with("vendor=C")));
+ // Bundle D
+ moduleList.add(
+ (m = new Module("D"))
+ .providing(new CapabilityImpl(m,
Capability.MODULE_NAMESPACE).with("bundle-symbolic-name=D"))
+ .providing(new CapabilityImpl(m,
Capability.PACKAGE_NAMESPACE).with("package=bar")));
+ // Bundle BB
+ moduleList.add(
+ (m = new Module("BB"))
+ .providing(new CapabilityImpl(m,
Capability.PACKAGE_NAMESPACE).with("package=woz").using("bar"))
+ .providing(new CapabilityImpl(m,
Capability.PACKAGE_NAMESPACE).with("package=bar"))
+ .requiring(new
RequirementImpl(Capability.MODULE_NAMESPACE).with("bundle-symbolic-name=CC"))
+ .requiring(new
RequirementImpl(Capability.MODULE_NAMESPACE).with("bundle-symbolic-name=DD")));
+ // Bundle CC
+ moduleList.add(
+ (m = new Module("CC"))
+ .providing(new CapabilityImpl(m,
Capability.MODULE_NAMESPACE).with("bundle-symbolic-name=CC"))
+ .providing(new CapabilityImpl(m,
Capability.PACKAGE_NAMESPACE).with("package=bar").with("vendor=CC")));
+ // Bundle DD
+ moduleList.add(
+ (m = new Module("DD"))
+ .providing(new CapabilityImpl(m,
Capability.MODULE_NAMESPACE).with("bundle-symbolic-name=DD"))
+ .providing(new CapabilityImpl(m,
Capability.PACKAGE_NAMESPACE).with("package=bar")));
+
+ return target;
+ }
+
+ private static Module scenario18(List<Module> moduleList)
+ {
+ Module m, target;
+
+ // Bundle A
+ moduleList.add(
+ target = (m = new Module("A"))
+ .requiring(new
RequirementImpl(Capability.PACKAGE_NAMESPACE).with("package=foo"))
+ .requiring(new
RequirementImpl(Capability.PACKAGE_NAMESPACE).with("package=woz"))
+ .requiring(new
RequirementImpl(Capability.PACKAGE_NAMESPACE).with("package=bar")));
+ // Bundle B
+ moduleList.add(
+ (m = new Module("B"))
+ .providing(new CapabilityImpl(m,
Capability.PACKAGE_NAMESPACE).with("package=foo").using("bar"))
+ .providing(new CapabilityImpl(m,
Capability.PACKAGE_NAMESPACE).with("package=bar"))
+ .requiring(new
RequirementImpl(Capability.MODULE_NAMESPACE).with("bundle-symbolic-name=C"))
+ .requiring(new
RequirementImpl(Capability.MODULE_NAMESPACE).with("bundle-symbolic-name=D")));
+ // Bundle C
+ moduleList.add(
+ (m = new Module("C"))
+ .providing(new CapabilityImpl(m,
Capability.MODULE_NAMESPACE).with("bundle-symbolic-name=C"))
+ .providing(new CapabilityImpl(m,
Capability.PACKAGE_NAMESPACE).with("package=bar").with("vendor=C")));
+ // Bundle D
+ moduleList.add(
+ (m = new Module("D"))
+ .providing(new CapabilityImpl(m,
Capability.MODULE_NAMESPACE).with("bundle-symbolic-name=D"))
+ .providing(new CapabilityImpl(m,
Capability.PACKAGE_NAMESPACE).with("package=bar")));
+ // Bundle BB
+ moduleList.add(
+ (m = new Module("BB"))
+ .providing(new CapabilityImpl(m,
Capability.PACKAGE_NAMESPACE).with("package=woz").using("bar"))
+ .providing(new CapabilityImpl(m,
Capability.PACKAGE_NAMESPACE).with("package=bar"))
+ .requiring(new
RequirementImpl(Capability.MODULE_NAMESPACE).with("bundle-symbolic-name=CC"))
+ .requiring(new
RequirementImpl(Capability.MODULE_NAMESPACE).with("bundle-symbolic-name=D")));
+ // Bundle CC
+ moduleList.add(
+ (m = new Module("CC"))
+ .providing(new CapabilityImpl(m,
Capability.MODULE_NAMESPACE).with("bundle-symbolic-name=CC"))
+ .providing(new CapabilityImpl(m,
Capability.PACKAGE_NAMESPACE).with("package=bar").with("vendor=CC")));
+
+ return target;
+ }
}
\ No newline at end of file
Modified:
felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/manifestparser/Main.java
URL:
http://svn.apache.org/viewvc/felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/manifestparser/Main.java?rev=895797&r1=895796&r2=895797&view=diff
==============================================================================
---
felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/manifestparser/Main.java
(original)
+++
felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/manifestparser/Main.java
Mon Jan 4 21:55:22 2010
@@ -38,6 +38,7 @@
import org.apache.felix.resolver.cs.Capability;
import org.apache.felix.resolver.cs.Requirement;
import org.apache.felix.resolver.felix.FelixResolver;
+import org.apache.felix.resolver.proto3.Proto3Resolver;
import org.apache.felix.resolver.prototype.ProtoResolver;
public class Main
@@ -46,19 +47,24 @@
{
if (args.length < 1)
{
- System.err.println("usage: [-Dinvoke.count=true] [-legacy]
[-nodupes] <bundle-dir>");
+ System.err.println("usage: [-Dinvoke.count=true] [-legacy |
-proto] [-nodupes] <bundle-dir>");
System.exit(0);
}
boolean legacy = false;
+ boolean proto = false;
boolean duplicates = true;
String dir = args[args.length - 1];
- for (int i = 0; i < args.length - 1; i++)
+ for (int i = 0; i < args.length; i++)
{
if (args[i].equals("-legacy"))
{
legacy = true;
}
+ else if (args[i].equals("-proto"))
+ {
+ proto = true;
+ }
else if (args[i].equals("-nodupes"))
{
duplicates = false;
@@ -334,10 +340,14 @@
{
resolver = new FelixResolver(moduleList);
}
- else
+ else if (proto)
{
resolver = new ProtoResolver(moduleList);
}
+ else
+ {
+ resolver = new Proto3Resolver(moduleList);
+ }
try
{
@@ -400,9 +410,9 @@
private static Module getTarget(List<Module> modules)
{
-// return getTargetByUnresolved(modules);
+ return getTargetByUnresolved(modules);
// return getTargetBySymbolicName(modules, "org.springframework.faces");
- return getTargetBySymbolicName(modules, "bundle1");
+// return getTargetBySymbolicName(modules, "bundle1");
}
private static Module getTargetByUnresolved(List<Module> modules)
Added:
felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/proto3/Proto3Resolver.java
URL:
http://svn.apache.org/viewvc/felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/proto3/Proto3Resolver.java?rev=895797&view=auto
==============================================================================
---
felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/proto3/Proto3Resolver.java
(added)
+++
felix/sandbox/rickhall/resolver/src/main/java/org/apache/felix/resolver/proto3/Proto3Resolver.java
Mon Jan 4 21:55:22 2010
@@ -0,0 +1,848 @@
+/*
+ * 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.proto3;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+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.Module;
+import org.apache.felix.resolver.ResolveException;
+import org.apache.felix.resolver.Resolver;
+import org.apache.felix.resolver.Version;
+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;
+import org.apache.felix.resolver.manifestparser.Constants;
+
+// 1. Treat hard pkg constraints separately from implied package constraints
+// 2. Map pkg constraints to a set of capabilities, not a single capability.
+// 3. Uses constraints cannot conflict with other uses constraints, only with
hard constraints.
+public class Proto3Resolver implements Resolver
+{
+ private final List<Module> m_modules;
+ private final CapabilitySet m_pkgCapSet;
+ private final CapabilitySet m_modCapSet;
+
+ private static final Map<String, Long> m_invokeCounts = new
HashMap<String, Long>();
+
+ private static boolean m_isInvokeCount = false;
+
+ public Proto3Resolver(List<Module> modules)
+ {
+System.out.println("+++ PROTO3 RESOLVER");
+ 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));
+ }
+ }
+ }
+
+ 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(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);
+ }
+
+ if (!module.isResolved())
+ {
+ Map<Requirement, Set<Capability>> candidateMap =
+ new HashMap<Requirement, Set<Capability>>();
+ Map<Module, Packages> modulePkgMap = new HashMap<Module,
Packages>();
+
+ populateCandidates(module, candidateMap, new HashSet<Module>());
+ m_candidatePermutations.add(candidateMap);
+
+ ResolveException rethrow = null;
+
+ do
+ {
+ rethrow = null;
+
+ candidateMap = m_candidatePermutations.remove(0);
+dumpCandidateMap(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);
+ }
+
+ return null;
+ }
+
+ private void dumpCandidateMap(Map<Requirement, Set<Capability>>
candidateMap)
+ {
+ System.out.println("=== CANDIDATE MAP ===");
+ for (Module module : m_modules)
+ {
+ 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);
+ 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 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 resolved, then it is consistent by definition,
+ // so just return.
+ if (module.isResolved())
+ {
+ return;
+ }
+ // If the module is in the cycle map, then just return.
+ else if (cycleMap.containsKey(module))
+ {
+ return;
+ }
+ cycleMap.put(module, module);
+
+System.out.println("+++ RESOLVING " + module);
+ calculateExportedPackages(module, incomingReqs, modulePkgMap);
+
+ 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 resolved. Try to merge
+ // the candidate's 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 void populateCandidates(
+ 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);
+
+ // Find candidates for all requirements for the target module.
+ List<Requirement> reqs = module.getRequirements();
+ for (Requirement req : reqs)
+ {
+ Set<Capability> candidates = findCandidates(req);
+ for (Iterator<Capability> itCandCap = candidates.iterator();
itCandCap.hasNext(); )
+ {
+ Capability candCap = itCandCap.next();
+ if (!candCap.getModule().isResolved())
+ {
+ try
+ {
+ populateCandidates(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 RuntimeException("Unable to resolve " + module
+ + ": missing requirement " + req);
+ }
+ else if (candidates.size() > 0)
+ {
+ candidateMap.put(req, candidates);
+ }
+ }
+ }
+
+ private static Set<Capability> createCandidateSet()
+ {
+ return new TreeSet(new Comparator() {
+ public int compare(Object arg1, Object arg2)
+ {
+ Capability cap1 = (Capability) arg1;
+ Capability cap2 = (Capability) arg2;
+ if (cap1.getNamespace().equals(Capability.MODULE_NAMESPACE))
+ {
+ int c = ((Comparable)
cap1.getAttribute(Constants.BUNDLE_SYMBOLICNAME_ATTRIBUTE)
+
.getValue()).compareTo(cap2.getAttribute(Constants.BUNDLE_SYMBOLICNAME_ATTRIBUTE)
+ .getValue());
+ if (c == 0)
+ {
+ Version v1 =
(cap1.getAttribute(Constants.BUNDLE_VERSION_ATTRIBUTE) == null)
+ ? Version.emptyVersion
+ : (Version)
cap1.getAttribute(Constants.BUNDLE_VERSION_ATTRIBUTE).getValue();
+ Version v2 =
(cap1.getAttribute(Constants.BUNDLE_VERSION_ATTRIBUTE) == null)
+ ? Version.emptyVersion
+ : (Version)
cap1.getAttribute(Constants.BUNDLE_VERSION_ATTRIBUTE).getValue();
+ // Compare these in reverse order, since we want
+ // highest version to have priority.
+ c = v2.compareTo(v1);
+ if (c == 0)
+ {
+ c =
cap1.getModule().getName().compareTo(cap2.getModule().getName());
+ }
+ }
+ return c;
+ }
+// TODO: PROTO2 RESOLVER - Need to change this to handle arbitrary capabilities
+// that may not have a natural ordering.
+ // Assume everything else is a package capability.
+ else
+ {
+ int c = ((Comparable)
cap1.getAttribute(Capability.PACKAGE_ATTR).getValue())
+
.compareTo(cap2.getAttribute(Capability.PACKAGE_ATTR).getValue());
+ if (c == 0)
+ {
+ Version v1 =
(cap1.getAttribute(Capability.VERSION_ATTR) == null)
+ ? Version.emptyVersion
+ : (Version)
cap1.getAttribute(Capability.VERSION_ATTR).getValue();
+ Version v2 =
(cap1.getAttribute(Capability.VERSION_ATTR) == null)
+ ? Version.emptyVersion
+ : (Version)
cap1.getAttribute(Capability.VERSION_ATTR).getValue();
+ // Compare these in reverse order, since we want
+ // highest version to have priority.
+ c = v2.compareTo(v1);
+ if (c == 0)
+ {
+ c =
cap1.getModule().getName().compareTo(cap2.getModule().getName());
+ }
+ }
+ return c;
+ }
+ }
+ });
+ }
+
+ private Set<Capability> findCandidates(Requirement req)
+ {
+ 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);
+ }
+
+ Set<Capability> result = createCandidateSet();
+
+ 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 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: PROTO2 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 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)
+ && m_pkgCapSet.matches(cap, reqs.get(i).getFilter()))
+ {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ private void mergeCandidatePackages(
+ Module current, List<Requirement> blameReqs,
+ 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(blameReqs, 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: PROTO2 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(blameReqs, 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);
+ }
+
+ 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();
+ Packages candPkgs = modulePkgMap.get(candBlame.m_cap.getModule());
+
+ // 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))))
+ {
+dumpModulePkgs(current, currentPkgs);
+ 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
+ //
+
+ 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.
+ 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);
+ }
+
+ // Verify and merge the candidate's transitive uses constraints.
+ verifyAndMergeUses(current, currentPkgsCopy, candBlame,
modulePkgMap, candidateMap);
+
+ // If we are here, then there were no conflict, so we should update
+ // the module's package space.
+ 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: PROTO2 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)
+ {
+System.out.println("+++ VERIFYING USES " + current + " FOR " + candBlame);
+ 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);
+ }
+
+ for (Capability candCapSource : getPackageSources(candBlame.m_cap,
modulePkgMap))
+ {
+ for (String usedPkgName : candCapSource.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 sourcePkgs =
modulePkgMap.get(candCapSource.getModule());
+ Blame sourceBlame = sourcePkgs.m_exportedPkgs.get(usedPkgName);
+ sourceBlame = (sourceBlame != null)
+ ? sourceBlame
+ : sourcePkgs.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 (sourceBlame == 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 " + sourceBlame);
+// usedCaps.add(new Blame(candBlame.m_reqs,
sourceBlame.m_cap));
+ usedCaps.add(sourceBlame);
+ return;
+ }
+ else if ((currentExportedBlame != null)
+ && !isCompatible(currentExportedBlame.m_cap,
sourceBlame.m_cap, modulePkgMap))
+ {
+ throw new ResolveException("Constraint violation for
package '" + usedPkgName
+ + "' when resolving module " + current
+ + " between existing constraint "
+ + currentExportedBlame
+ + " and candidate constraint "
+ + sourceBlame);
+ }
+ else if ((currentImportedBlame != null)
+ && !isCompatible(currentImportedBlame.m_cap,
sourceBlame.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 "
+ + sourceBlame);
+ }
+
+ // Verify the candidate's uses constraints do not conflict.
+ verifyAndMergeUses(current, currentPkgs, sourceBlame,
modulePkgMap, candidateMap);
+ }
+ }
+ }
+
+ private static boolean isCompatible(
+ Capability currentCap, Capability candCap, Map<Module, Packages>
modulePkgMap)
+ {
+ if ((currentCap != null) && (candCap != null))
+ {
+ List<Capability> currentSources = getPackageSources(currentCap,
modulePkgMap);
+ List<Capability> candSources = getPackageSources(candCap,
modulePkgMap);
+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 = null;
+ if (cap.getNamespace().equals(Capability.PACKAGE_NAMESPACE))
+ {
+ Packages pkgs = modulePkgMap.get(cap.getModule());
+ sources = new ArrayList<Capability>();
+ 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)
+ {
+ sources.add(blame.m_cap);
+ }
+ }
+ }
+ return sources;
+ }
+
+ 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 = createCandidateSet();
+ candidates.addAll(entry.getValue());
+ copy.put(entry.getKey(), candidates);
+ }
+ return copy;
+ }
+
+ private 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 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
