Bug 144730 [performance] resolver is slow with large number of uses directiver32x_v20060731R32x_v20060717

3 files changed, 72 insertions, 37 deletions

diff --git a/bundles/org.eclipse.osgi/resolver/src/org/eclipse/osgi/internal/module/GroupingChecker.java b/bundles/org.eclipse.osgi/resolver/src/org/eclipse/osgi/internal/module/GroupingChecker.java
index 3241f4c1a..02be81def 100644
--- a/bundles/org.eclipse.osgi/resolver/src/org/eclipse/osgi/internal/module/GroupingChecker.java
+++ b/bundles/org.eclipse.osgi/resolver/src/org/eclipse/osgi/internal/module/GroupingChecker.java
@@ -151,6 +151,11 @@ public class GroupingChecker {
 			list.add(constraint);
 	}
 
+	private void addConstraint(ArrayList export, Object constraint) {
+		for (Iterator iExport = export.iterator(); iExport.hasNext();)
+			addConstraint((ResolverExport) iExport.next(), constraint);
+	}
+
 	// removes all constraints specified by this bundles exports
 	void removeAllExportConstraints(ResolverBundle bundle) {
 		bundles.remove(bundle);
@@ -215,11 +220,20 @@ public class GroupingChecker {
 		// Check existing wirings against constraints from candidate wiring
 		for (int i = 0; i < candConstraints.length; i++) {
 			// check if we export this package
-			ResolverExport[] importerExp = imp != null ? imp.getBundle().getExports(candConstraints[i].getName()) : new ResolverExport[0];
-			for (int j = 0; j < importerExp.length; j++)
-				if (!importerExp[j].isDropped() && !isOnRoot(importerExp[j].getRoots(), candConstraints[i]))
-					// if we export the package and it is not the same one then we have a clash
-					return existing;
+			if (imp.getBundle() != candConstraints[i].getExporter()) {
+				// there is no need to do this check if the candidate constaint is from ourselves
+				ResolverExport[] importerExp = imp.getBundle().getExports(candConstraints[i].getName());
+				if (importerExp.length > 0) {
+					ResolverImport alsoImported = imp.getBundle().getImport(candConstraints[i].getName());
+					// only do the extra check if we do not import the package or if we do and the import is resolved
+					if (alsoImported == null || alsoImported.getMatchingExport() != null)
+						for (int j = 0; j < importerExp.length; j++)
+							if (!importerExp[j].isDropped() && !isOnRoot(importerExp[j].getRoots(), candConstraints[i]))
+								// if we export the package and it is not the same one then we have a clash
+								return existing;
+				}
+			}
+			// check the existing resolved import against the candidate constraint
 			if (isConflict(existing, candConstraints[i]))
 				return existing;
 		}
@@ -280,36 +294,55 @@ public class GroupingChecker {
 			return; // already processed
 		// for each export; add it uses constraints
 		ResolverExport[] exports = initBundle.getExportPackages();
-		for (int j = 0; j < exports.length; j++)
-			addInitialGroupingConstraints(exports[j], null);
+		for (int j = 0; j < exports.length; j++) {
+			ArrayList export = new ArrayList();
+			export.add(exports[j]);
+			addInitialGroupingConstraints(export, null);
+		}
 		if (bundles.get(initBundle) == null)
 			bundles.put(initBundle, null); // mark this bundle as processed
 	}
 
 	// Add constraints from other exports (due to 'uses' being transitive)
-	private void addInitialGroupingConstraints(ResolverExport export, ResolverExport constraint) {
-		if (export == constraint)
+	private void addInitialGroupingConstraints(ArrayList exports, ResolverExport constraint) {
+		// pop the intitial export off as the current export we are checking
+		ResolverExport cur = (ResolverExport) exports.get(0);
+		if (cur == constraint)
 			return;
-		if (constraint == null)
-			constraint = export;
+		if (constraint == null) {
+			if (getCachedConstraints(cur) != null)
+				// we have already processed the current export; just return
+				return;
+			constraint = cur;
+		}
 		String[] uses = (String[]) constraint.getExportPackageDescription().getDirective(Constants.USES_DIRECTIVE);
 		if (uses == null)
 			return;
+		boolean constraintAdded = false;
+		if (!exports.contains(constraint) && getCachedConstraints(constraint) == null) {
+			// the constraints have not been evaluated for this export add it to the list to process 
+			exports.add(constraint);
+			constraintAdded = true;
+		}
+		ResolverBundle exporter = cur.getExporter();
 		for (int i = 0; i < uses.length; i++) {
-			ResolverExport[] constraintExports = export.getExporter().getExports(uses[i]);
+			ResolverExport[] constraintExports = exporter.getExports(uses[i]);
 			for (int j = 0; j < constraintExports.length; j++) {
 				// Check if the constraint has already been added so we don't recurse infinitely
-				if (!getConstraintsList(export).contains(constraintExports[j])) {
-					addConstraint(export, constraintExports[j]);
-					addInitialGroupingConstraints(export, constraintExports[j]);
+				if (!createConstraints(cur).contains(constraintExports[j])) {
+					addConstraint(exports, constraintExports[j]);
+					addInitialGroupingConstraints(exports, constraintExports[j]);
 				}
 			}
-			ResolverImport constraintImport = export.getExporter().getImport(uses[i]);
+			ResolverImport constraintImport = exporter.getImport(uses[i]);
 			if (constraintImport != null && !constraintImport.isDynamic())
-				addConstraint(export, constraintImport);
+				addConstraint(exports, constraintImport);
 			if (constraintExports.length == 0 && (constraintImport == null || constraintImport.isDynamic()))
-				addConstraint(export, new UsesRequiredExport(constraint, uses[i]));
+				addConstraint(exports, new UsesRequiredExport(constraint, uses[i]));
 		}
+		if (constraintAdded)
+			// we have finished processing all the uses for the constraint; remove it from the list to process
+			exports.remove(constraint);
 	}
 
 	// Used to hold a 'uses' constraint on a package that is accessed through a required bundle
diff --git a/bundles/org.eclipse.osgi/resolver/src/org/eclipse/osgi/internal/module/ResolverBundle.java b/bundles/org.eclipse.osgi/resolver/src/org/eclipse/osgi/internal/module/ResolverBundle.java
index 5cea1935b..7e94894f6 100644
--- a/bundles/org.eclipse.osgi/resolver/src/org/eclipse/osgi/internal/module/ResolverBundle.java
+++ b/bundles/org.eclipse.osgi/resolver/src/org/eclipse/osgi/internal/module/ResolverBundle.java
@@ -102,18 +102,17 @@ public class ResolverBundle extends VersionSupplier {
 	}
 
 	ResolverExport getExport(String name) {
-		ResolverExport[] allExports = getExportPackages();
-		for (int i = 0; i < allExports.length; i++)
-			if (name.equals(allExports[i].getName()))
-				return allExports[i];
-		return null;
+		ResolverExport[] allExports = getExports(name);
+		return allExports.length == 0 ? null : allExports[0];
 	}
 
 	ResolverExport[] getExports(String name) {
 		ArrayList results = new ArrayList(1); // rare to have more than one
-		for (int i = 0; i < exports.length; i++)
-			if (name.equals(exports[i].getName()))
-				results.add(exports[i]);
+		// it is faster to ask the VersionHashMap for this package name and then compare the exporter to this
+		Object[] resolverExports = resolver.getResolverExports().get(name);
+		for (int i = 0; i < resolverExports.length; i++)
+			if (((ResolverExport)resolverExports[i]).getExporter() == this)
+				results.add(resolverExports[i]);
 		return (ResolverExport[]) results.toArray(new ResolverExport[results.size()]);
 	}
 
diff --git a/bundles/org.eclipse.osgi/resolver/src/org/eclipse/osgi/internal/module/ResolverImpl.java b/bundles/org.eclipse.osgi/resolver/src/org/eclipse/osgi/internal/module/ResolverImpl.java
index 5618c2b68..00d250960 100644
--- a/bundles/org.eclipse.osgi/resolver/src/org/eclipse/osgi/internal/module/ResolverImpl.java
+++ b/bundles/org.eclipse.osgi/resolver/src/org/eclipse/osgi/internal/module/ResolverImpl.java
@@ -815,19 +815,22 @@ public class ResolverImpl implements org.eclipse.osgi.service.resolver.Resolver
 				if (result)
 					continue;
 				imp.setMatchingExport(export); // Wire the import to the export
+				ResolverExport[] importerExps = null;
 				if (imp.getBundle() != export.getExporter()) {
-					ResolverExport[] exps = imp.getBundle().getExports(imp.getName());
-					for (int j = 0; j < exps.length; j++) {
-						if (exps[j].getExportPackageDescription().isRoot() && !export.getExportPackageDescription().isRoot())
+					// Save the exports of this package from the importer in case we need to add them back
+					importerExps = imp.getBundle().getExports(imp.getName());
+					for (int j = 0; j < importerExps.length; j++) {
+						if (importerExps[j].getExportPackageDescription().isRoot() && !export.getExportPackageDescription().isRoot())
 							continue exportsloop; // to prevent imports from getting wired to re-exports if we offer a root export
-						if (exps[j].getExportPackageDescription().isRoot()) // do not drop reexports when import wins
-							resolverExports.remove(exps[j]); // Import wins, remove export
+						if (importerExps[j].getExportPackageDescription().isRoot()) // do not drop reexports when import wins
+							resolverExports.remove(importerExps[j]); // Import wins, remove export
 					}
 					if ((originalState != ResolverBundle.RESOLVED && !resolveBundle(export.getExporter(), cycle)) || export.isDropped()) {
 						if (imp.getMatchingExport() != null && imp.getMatchingExport() != export) // has been resolved to some other export recursively
 							return true;
-						for (int j = 0; j < exps.length; j++)
-							resolverExports.put(exps[j].getName(), exps[j]);
+						// add back the exports of this package from the importer
+						for (int j = 0; j < importerExps.length; j++)
+							resolverExports.put(importerExps[j].getName(), importerExps[j]);
 						imp.setMatchingExport(null);
 						continue; // Bundle hasn't resolved || export has not been selected and is unavailable
 					}
@@ -836,7 +839,7 @@ public class ResolverImpl implements org.eclipse.osgi.service.resolver.Resolver
 				if (!imp.getBundle().isResolvable())
 					return false;
 				// Check grouping dependencies
-				if (checkImportConstraints(imp, imp.getMatchingExport(), cycle) && imp.getMatchingExport() != null) {
+				if (checkImportConstraints(imp, imp.getMatchingExport(), cycle, importerExps) && imp.getMatchingExport() != null) {
 					// Record any cyclic dependencies
 					if (export != imp.getMatchingExport())
 						export = imp.getMatchingExport();
@@ -926,7 +929,7 @@ public class ResolverImpl implements org.eclipse.osgi.service.resolver.Resolver
 
 	// This method checks and resolves (if possible) grouping dependencies
 	// Returns true, if the dependencies can be resolved, false otherwise
-	private boolean checkImportConstraints(ResolverImport imp, ResolverExport exp, ArrayList cycle) {
+	private boolean checkImportConstraints(ResolverImport imp, ResolverExport exp, ArrayList cycle, ResolverExport[] importerExps) {
 		if (DEBUG_GROUPING)
 			ResolverImpl.log("  Checking grouping for " + imp.getBundle() + ":" + imp.getName() + " -> " + exp.getExporter() + ":" + exp.getName()); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$
 		ResolverBundle importer = imp.getBundle();
@@ -952,8 +955,8 @@ public class ResolverImpl implements org.eclipse.osgi.service.resolver.Resolver
 				imports[i].setMatchingExport(null); // clear the conflicting wire
 				// If the clashing import package was also exported then
 				// we need to put the export back into resolverExports
-				ResolverExport removed[] = importer.getExports(imports[i].getName());
-				resolverExports.put(removed);
+				if (importerExps != null)
+					resolverExports.put(importerExps);
 			}
 		}
 		// Try to re-resolve the bundle