bundles/org.eclipse.osgi/resolver/src/org/eclipse/osgi/internal/module/GroupingChecker.java - equinox/rt.equinox.framework - Git at Google

 /*******************************************************************************
  * Copyright (c) 2004, 2006 IBM Corporation and others.
  * All rights reserved. This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License v1.0
  * which accompanies this distribution, and is available at
  * http://www.eclipse.org/legal/epl-v10.html
  *
  * Contributors:
  *     IBM Corporation - initial API and implementation
  *******************************************************************************/
 package org.eclipse.osgi.internal.module;

 import java.util.*;
 import org.eclipse.osgi.service.resolver.BundleSpecification;
 import org.osgi.framework.Constants;

 /*
  * The GroupingChecker checks the 'uses' directive on exported packages for consistency
  */
 public class GroupingChecker {
 	// Maps bundles to their exports; keyed by
 	//   ResolverBundle -> exports HashMap
 	//     the exports HashMap is keyed by
 	//       ResolverExport -> Object[] {'uses' constraint ArrayList, transitive constraint cache}
 	HashMap bundles = new HashMap();
 	private boolean checkCycles = false;

 	// Gets all constraints for an exported package.
 	// this will perform transitive closure on the uses constraints.
 	// this method also will cache the transitive results if the bundle is resolved
 	private ResolverExport[] getConstraints(ResolverExport constrained) {
 		// check the cache first
 		Object[] cachedResults = getCachedConstraints(constrained);
 		if (cachedResults != null && cachedResults[1] != null) {
 			if (!constrained.getExporter().isResolved()) {
 				// need to make sure none of the current constraints are dropped
 				ResolverExport[] constraints = (ResolverExport[]) cachedResults[1];
 				boolean dropped = false;
 				for (int i = 0; !dropped && i < constraints.length; i++)
 					dropped = constraints[i].isDropped();
 				if (!dropped)
 					return constraints;
 				// otherwise recompute the transitive constraints below
 			} else {
 				// we have aready cached the results for this return the cached results
 				return (ResolverExport[]) cachedResults[1];
 			}
 		}
 		ArrayList resultlist = getConstraintsList(constrained);
 		ResolverExport[] results = (ResolverExport[]) resultlist.toArray(new ResolverExport[resultlist.size()]);
 		if (!checkCycles || constrained.getExporter().isResolved()) {
 			// if the bundle is resolved or we are not checking cycles then we can add the results to the cached results
 			if (cachedResults == null)
 				cachedResults = createConstraintsCache(constrained); // should have been created by getConstraintsList
 			cachedResults[1] = results;
 		}
 		return results;
 	}

 	private Object[] getCachedConstraints(ResolverExport constrained) {
 		// get the cached constraints for this export
 		HashMap exports = (HashMap) bundles.get(constrained.getExporter());
 		return exports == null ? null : (Object[]) exports.get(constrained);
 	}

 	// Gets all constraints for an exported package
 	// same as getConstraints only the raw ArrayList is returned and
 	// the cache is not consulted.
 	private ArrayList getConstraintsList(ResolverExport constrained) {
 		ArrayList results = new ArrayList();
 		getTransitiveConstraints(constrained, results);
 		return results;
 	}

 	// adds the transitive 'uses' constraints for the specified constrained ResolverExport
 	// to the results ArrayList.
 	private void getTransitiveConstraints(ResolverExport constrained, ArrayList results) {
 		if (constrained.isDropped())
 			return;
 		// first get any constraints that may come from required bundle exports
 		ResolverExport[] constrainedRoots = constrained.getRoots();
 		for (int i = 0; i < constrainedRoots.length; i++)
 			// only search for transitive constraints on other exports (i.e. from required bundles)
 			if (constrainedRoots[i] != constrained)
 				getTransitiveConstraints(constrainedRoots[i], results);
 		// now get the constraints that are specified by this export
 		Object[] cachedConstraints = getCachedConstraints(constrained);
 		ArrayList constraints = (ArrayList) (cachedConstraints != null ? cachedConstraints[0] : null);
 		if (constraints == null)
 			return;
 		for (Iterator iter = constraints.iterator(); iter.hasNext();) {
 			Object constraint = iter.next();
 			ResolverExport[] moreConstraints = null;
 			if (constraint instanceof ResolverExport) {
 				// the constraint is to another export from this bundle
 				ResolverExport export = (ResolverExport) constraint;
 				// get the roots from this export; incase it is split from a required bundle
 				moreConstraints = export.getRoots();
 			} else if (constraint instanceof ResolverImport) {
 				// the constraint is to an imported package
 				ResolverImport imp = (ResolverImport) constraint;
 				// if the import is resolved then we need to add the constraints of the roots from the export
 				if (imp.getMatchingExport() != null)
 					moreConstraints = imp.getMatchingExport().getRoots();
 			} else if (constraint instanceof UsesRequiredExport) {
 				// the constraint is on a package from a required bundle; get the roots from the required bundles
 				moreConstraints = ((UsesRequiredExport) constraint).getRoots();
 			}
 			if (moreConstraints != null)
 				// now add each root as a constraint
 				for (int i = 0; i < moreConstraints.length; i++)
 					if (!results.contains(moreConstraints[i])) {
 						results.add(moreConstraints[i]);
 						if (moreConstraints[i] != constraint)
 							// add the constraints for each root
 							getTransitiveConstraints(moreConstraints[i], results);
 					}
 		}
 	}

 	// creates the Object[] used to cache constraint definitions and transitive
 	// closure results.
 	private Object[] createConstraintsCache(ResolverExport constrained) {
 		HashMap exports = (HashMap) bundles.get(constrained.getExporter());
 		if (exports == null) {
 			exports = new HashMap();
 			bundles.put(constrained.getExporter(), exports);
 		}
 		Object[] constraints = (Object[]) exports.get(constrained);
 		if (constraints == null) {
 			constraints = new Object[2];
 			exports.put(constrained, constraints);
 		}
 		return constraints;
 	}

 	// creates an empty list to hold constraints for the specified export
 	// if a list already exists then a new list is NOT created.
 	private ArrayList createConstraints(ResolverExport constrained) {
 		Object[] constraints = createConstraintsCache(constrained);
 		if (constraints[0] == null)
 			constraints[0] = new ArrayList();
 		return (ArrayList) constraints[0];
 	}

 	// adds a 'uses' constraint to a ResolverExport.  A new 'uses' constraint list
 	// is created if one does not exist.
 	private void addConstraint(ResolverExport constrained, Object constraint) {
 		ArrayList list = createConstraints(constrained);
 		if (!list.contains(constraint))
 			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);
 	}

 	// checks the 'uses' consistency of the required BundleConstraint with other required
 	// BundleConstraints of the specified ResolverBundle
 	ResolverBundle isConsistent(BundleConstraint req, ResolverBundle bundle) {
 		BundleConstraint[] requires = req.getBundle().getRequires();
 		ArrayList visited = new ArrayList(requires.length);
 		for (int i = 0; i < requires.length; i++) {
 			ResolverBundle match = requires[i].getMatchingBundle();
 			if (match == bundle || match == null)
 				continue; // the constraint has not been resolved or is to ourselves
 			// check the consistency of each exported package from the new required match
 			ResolverExport[] exports = match.getSelectedExports();
 			for (int j = 0; j < exports.length; j++)
 				if (checkReqExpConflict(exports[j], getConstraints(exports[j]), bundle, visited) != null)
 					return match;
 		}
 		return null;
 	}

 	// checks the 'uses consistency of the imported ResolverImport with specified
 	// ResolverExport.  This will also check 'uses' consistency with other imported packages
 	// and other required bundles of the importing bundle.
 	ResolverExport isConsistent(ResolverImport imp, ResolverExport exp) {
 		ResolverExport[] expConstraints = getConstraints(exp);
 		// Check imports are consistent
 		ResolverImport[] imports = imp.getBundle().getImportPackages();
 		for (int i = 0; i < imports.length; i++) {
 			// Check new wiring constraints against constraints from previous wirings
 			ResolverExport conflict = checkImpExpConflict(imp, imports[i].getMatchingExport(), exp, expConstraints);
 			if (conflict != null)
 				return conflict;
 		}
 		// Check new wiring against required exports
 		BundleConstraint[] requires = imp.getBundle().getRequires();
 		ArrayList visited = new ArrayList(requires.length); // visited list prevents recursive cycles
 		for (int i = 0; i < requires.length; i++) {
 			ResolverExport conflict = checkReqExpConflict(exp, expConstraints, requires[i].getMatchingBundle(), visited);
 			if (conflict != null)
 				return conflict;
 		}
 		// No clash, so return null
 		return null;
 	}

 	// checks the 'uses' constraints ResolverImport's matching export with the constraints
 	// of the candidate ResolverExport.  If a conflict exists then the conflict is returned.
 	private ResolverExport checkImpExpConflict(ResolverImport imp, ResolverExport existing, ResolverExport candidate, ResolverExport[] candConstraints) {
 		if (existing == null)
 			return null; // for an import that has not been resolved
 		// check the constraints of the existing wire against the candidate only
 		// if the existing wire is not the candidate
 		if (existing != candidate) {
 			ResolverExport[] impConstraints = getConstraints(existing);
 			for (int j = 0; j < impConstraints.length; j++)
 				if (isConflict(candidate, impConstraints[j]))
 					return existing;
 		}
 		// Check existing wirings against constraints from candidate wiring
 		for (int i = 0; i < candConstraints.length; i++) {
 			// check if we export this package
 			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;
 		}
 		return null;
 	}

 	// checks the 'uses' constraints ResolverExport with the constraints of the ResolverExports
 	// from the specified ResolverBundle.  If a conflict exists then the conflict is returned.
 	private ResolverExport checkReqExpConflict(ResolverExport exp, ResolverExport expConstraints[], ResolverBundle bundle, ArrayList visited) {
 		if (bundle == null)
 			return null;
 		if (visited.contains(bundle)) // return if we visited this bundle; prevent endless loops
 			return null;
 		visited.add(bundle); // mark as visited
 		// check the consistency of all the selected exports
 		ResolverExport[] exports = bundle.getSelectedExports();
 		for (int i = 0; i < exports.length; i++) {
 			// first check the constraints of the 'exp' with the exported packages of the 'bundle'
 			for (int j = 0; j < expConstraints.length; j++)
 				if (isConflict(exports[i], expConstraints[j]))
 					return exp;
 			// next check the constraints of each exported package of the 'bundle' with the 'exp'
 			ResolverExport[] constraints = getConstraints(exports[i]);
 			for (int j = 0; j < constraints.length; j++)
 				if (isConflict(exp, constraints[j]))
 					return exp;
 		}
 		// check the consistency of all the required bundles which we reexport
 		BundleConstraint[] requires = bundle.getRequires();
 		for (int i = 0; i < requires.length; i++)
 			if (((BundleSpecification) requires[i].getVersionConstraint()).isExported()) {
 				ResolverExport conflict = checkReqExpConflict(exp, expConstraints, requires[i].getMatchingBundle(), visited);
 				if (conflict != null)
 					return exp;
 			}
 		return null;
 	}

 	// returns true if the candidateRoot is NOT a root of the candidate ResolverExport
 	private boolean isConflict(ResolverExport candidate, ResolverExport candidateRoot) {
 		return candidateRoot.getExporter().isResolvable() && candidateRoot.getName().equals(candidate.getName()) && !isOnRoot(candidate.getRoots(), candidateRoot);
 	}

 	// checks that the specified ResolverExport is contained in the list of roots
 	private boolean isOnRoot(ResolverExport[] roots, ResolverExport re) {
 		for (int i = 0; i < roots.length; i++)
 			// check the exporter; this handles multple exports of the same package name from a bundle
 			if (roots[i].getExporter() == re.getExporter())
 				return true;
 		if (roots.length == 1 && !roots[0].getExportPackageDescription().isRoot())
 			return true; // this is for a reexporter that does not have the import satisfied yet
 		return false;
 	}

 	// Add initial 'uses' constraints for a list of bundles
 	void addInitialGroupingConstraints(ResolverBundle initBundle) {
 		if (bundles.containsKey(initBundle))
 			return; // already processed
 		// for each export; add it uses constraints
 		ResolverExport[] exports = initBundle.getExportPackages();
 		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(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) {
 			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 = 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 (!createConstraints(cur).contains(constraintExports[j])) {
 					addConstraint(exports, constraintExports[j]);
 					addInitialGroupingConstraints(exports, constraintExports[j]);
 				}
 			}
 			ResolverImport constraintImport = exporter.getImport(uses[i]);
 			if (constraintImport != null && !constraintImport.isDynamic())
 				addConstraint(exports, constraintImport);
 			if (constraintExports.length == 0 && (constraintImport == null || constraintImport.isDynamic()))
 				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
 	private class UsesRequiredExport {
 		// the exported package which 'uses' a package from a required bundle
 		private ResolverExport export;
 		// the name of the package which is 'used'
 		private String usesName;

 		UsesRequiredExport(ResolverExport export, String usesName) {
 			this.export = export;
 			this.usesName = usesName;
 		}

 		public ResolverExport[] getRoots() {
 			ArrayList results = new ArrayList(1); // rare to have more than 1
 			BundleConstraint[] requires = export.getExporter().getRequires();
 			for (int i = 0; i < requires.length; i++) {
 				if (requires[i].getMatchingBundle() == null)
 					continue;
 				ResolverExport requiredExport = requires[i].getMatchingBundle().getExport(usesName);
 				if (requiredExport != null && !requiredExport.isDropped()) {
 					ResolverExport[] roots = requiredExport.getRoots();
 					for (int j = 0; j < roots.length; j++)
 						if (!results.contains(requiredExport))
 							results.add(roots[j]);
 				}
 			}
 			return (ResolverExport[]) results.toArray(new ResolverExport[results.size()]);
 		}

 		public boolean equals(Object o) {
 			if (!(o instanceof UsesRequiredExport))
 				return false;
 			return ((UsesRequiredExport) o).export.getExporter() == export.getExporter() && usesName.equals(((UsesRequiredExport) o).usesName);
 		}
 	}

 	public void setCheckCycles(boolean checkCycles) {
 		this.checkCycles = checkCycles;
 	}
 }
	/*******************************************************************************
	* Copyright (c) 2004, 2006 IBM Corporation and others.
	* All rights reserved. This program and the accompanying materials
	* are made available under the terms of the Eclipse Public License v1.0
	* which accompanies this distribution, and is available at
	* http://www.eclipse.org/legal/epl-v10.html
	*
	* Contributors:
	* IBM Corporation - initial API and implementation
	*******************************************************************************/
	package org.eclipse.osgi.internal.module;

	import java.util.*;
	import org.eclipse.osgi.service.resolver.BundleSpecification;
	import org.osgi.framework.Constants;

	/*
	* The GroupingChecker checks the 'uses' directive on exported packages for consistency
	*/
	public class GroupingChecker {
	// Maps bundles to their exports; keyed by
	// ResolverBundle -> exports HashMap
	// the exports HashMap is keyed by
	// ResolverExport -> Object[] {'uses' constraint ArrayList, transitive constraint cache}
	HashMap bundles = new HashMap();
	private boolean checkCycles = false;

	// Gets all constraints for an exported package.
	// this will perform transitive closure on the uses constraints.
	// this method also will cache the transitive results if the bundle is resolved
	private ResolverExport[] getConstraints(ResolverExport constrained) {
	// check the cache first
	Object[] cachedResults = getCachedConstraints(constrained);
	if (cachedResults != null && cachedResults[1] != null) {
	if (!constrained.getExporter().isResolved()) {
	// need to make sure none of the current constraints are dropped
	ResolverExport[] constraints = (ResolverExport[]) cachedResults[1];
	boolean dropped = false;
	for (int i = 0; !dropped && i < constraints.length; i++)
	dropped = constraints[i].isDropped();
	if (!dropped)
	return constraints;
	// otherwise recompute the transitive constraints below
	} else {
	// we have aready cached the results for this return the cached results
	return (ResolverExport[]) cachedResults[1];
	}
	}
	ArrayList resultlist = getConstraintsList(constrained);
	ResolverExport[] results = (ResolverExport[]) resultlist.toArray(new ResolverExport[resultlist.size()]);
	if (!checkCycles \|\| constrained.getExporter().isResolved()) {
	// if the bundle is resolved or we are not checking cycles then we can add the results to the cached results
	if (cachedResults == null)
	cachedResults = createConstraintsCache(constrained); // should have been created by getConstraintsList
	cachedResults[1] = results;
	}
	return results;
	}

	private Object[] getCachedConstraints(ResolverExport constrained) {
	// get the cached constraints for this export
	HashMap exports = (HashMap) bundles.get(constrained.getExporter());
	return exports == null ? null : (Object[]) exports.get(constrained);
	}

	// Gets all constraints for an exported package
	// same as getConstraints only the raw ArrayList is returned and
	// the cache is not consulted.
	private ArrayList getConstraintsList(ResolverExport constrained) {
	ArrayList results = new ArrayList();
	getTransitiveConstraints(constrained, results);
	return results;
	}

	// adds the transitive 'uses' constraints for the specified constrained ResolverExport
	// to the results ArrayList.
	private void getTransitiveConstraints(ResolverExport constrained, ArrayList results) {
	if (constrained.isDropped())
	return;
	// first get any constraints that may come from required bundle exports
	ResolverExport[] constrainedRoots = constrained.getRoots();
	for (int i = 0; i < constrainedRoots.length; i++)
	// only search for transitive constraints on other exports (i.e. from required bundles)
	if (constrainedRoots[i] != constrained)
	getTransitiveConstraints(constrainedRoots[i], results);
	// now get the constraints that are specified by this export
	Object[] cachedConstraints = getCachedConstraints(constrained);
	ArrayList constraints = (ArrayList) (cachedConstraints != null ? cachedConstraints[0] : null);
	if (constraints == null)
	return;
	for (Iterator iter = constraints.iterator(); iter.hasNext();) {
	Object constraint = iter.next();
	ResolverExport[] moreConstraints = null;
	if (constraint instanceof ResolverExport) {
	// the constraint is to another export from this bundle
	ResolverExport export = (ResolverExport) constraint;
	// get the roots from this export; incase it is split from a required bundle
	moreConstraints = export.getRoots();
	} else if (constraint instanceof ResolverImport) {
	// the constraint is to an imported package
	ResolverImport imp = (ResolverImport) constraint;
	// if the import is resolved then we need to add the constraints of the roots from the export
	if (imp.getMatchingExport() != null)
	moreConstraints = imp.getMatchingExport().getRoots();
	} else if (constraint instanceof UsesRequiredExport) {
	// the constraint is on a package from a required bundle; get the roots from the required bundles
	moreConstraints = ((UsesRequiredExport) constraint).getRoots();
	}
	if (moreConstraints != null)
	// now add each root as a constraint
	for (int i = 0; i < moreConstraints.length; i++)
	if (!results.contains(moreConstraints[i])) {
	results.add(moreConstraints[i]);
	if (moreConstraints[i] != constraint)
	// add the constraints for each root
	getTransitiveConstraints(moreConstraints[i], results);
	}
	}
	}

	// creates the Object[] used to cache constraint definitions and transitive
	// closure results.
	private Object[] createConstraintsCache(ResolverExport constrained) {
	HashMap exports = (HashMap) bundles.get(constrained.getExporter());
	if (exports == null) {
	exports = new HashMap();
	bundles.put(constrained.getExporter(), exports);
	}
	Object[] constraints = (Object[]) exports.get(constrained);
	if (constraints == null) {
	constraints = new Object[2];
	exports.put(constrained, constraints);
	}
	return constraints;
	}

	// creates an empty list to hold constraints for the specified export
	// if a list already exists then a new list is NOT created.
	private ArrayList createConstraints(ResolverExport constrained) {
	Object[] constraints = createConstraintsCache(constrained);
	if (constraints[0] == null)
	constraints[0] = new ArrayList();
	return (ArrayList) constraints[0];
	}

	// adds a 'uses' constraint to a ResolverExport. A new 'uses' constraint list
	// is created if one does not exist.
	private void addConstraint(ResolverExport constrained, Object constraint) {
	ArrayList list = createConstraints(constrained);
	if (!list.contains(constraint))
	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);
	}

	// checks the 'uses' consistency of the required BundleConstraint with other required
	// BundleConstraints of the specified ResolverBundle
	ResolverBundle isConsistent(BundleConstraint req, ResolverBundle bundle) {
	BundleConstraint[] requires = req.getBundle().getRequires();
	ArrayList visited = new ArrayList(requires.length);
	for (int i = 0; i < requires.length; i++) {
	ResolverBundle match = requires[i].getMatchingBundle();
	if (match == bundle \|\| match == null)
	continue; // the constraint has not been resolved or is to ourselves
	// check the consistency of each exported package from the new required match
	ResolverExport[] exports = match.getSelectedExports();
	for (int j = 0; j < exports.length; j++)
	if (checkReqExpConflict(exports[j], getConstraints(exports[j]), bundle, visited) != null)
	return match;
	}
	return null;
	}

	// checks the 'uses consistency of the imported ResolverImport with specified
	// ResolverExport. This will also check 'uses' consistency with other imported packages
	// and other required bundles of the importing bundle.
	ResolverExport isConsistent(ResolverImport imp, ResolverExport exp) {
	ResolverExport[] expConstraints = getConstraints(exp);
	// Check imports are consistent
	ResolverImport[] imports = imp.getBundle().getImportPackages();
	for (int i = 0; i < imports.length; i++) {
	// Check new wiring constraints against constraints from previous wirings
	ResolverExport conflict = checkImpExpConflict(imp, imports[i].getMatchingExport(), exp, expConstraints);
	if (conflict != null)
	return conflict;
	}
	// Check new wiring against required exports
	BundleConstraint[] requires = imp.getBundle().getRequires();
	ArrayList visited = new ArrayList(requires.length); // visited list prevents recursive cycles
	for (int i = 0; i < requires.length; i++) {
	ResolverExport conflict = checkReqExpConflict(exp, expConstraints, requires[i].getMatchingBundle(), visited);
	if (conflict != null)
	return conflict;
	}
	// No clash, so return null
	return null;
	}

	// checks the 'uses' constraints ResolverImport's matching export with the constraints
	// of the candidate ResolverExport. If a conflict exists then the conflict is returned.
	private ResolverExport checkImpExpConflict(ResolverImport imp, ResolverExport existing, ResolverExport candidate, ResolverExport[] candConstraints) {
	if (existing == null)
	return null; // for an import that has not been resolved
	// check the constraints of the existing wire against the candidate only
	// if the existing wire is not the candidate
	if (existing != candidate) {
	ResolverExport[] impConstraints = getConstraints(existing);
	for (int j = 0; j < impConstraints.length; j++)
	if (isConflict(candidate, impConstraints[j]))
	return existing;
	}
	// Check existing wirings against constraints from candidate wiring
	for (int i = 0; i < candConstraints.length; i++) {
	// check if we export this package
	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;
	}
	return null;
	}

	// checks the 'uses' constraints ResolverExport with the constraints of the ResolverExports
	// from the specified ResolverBundle. If a conflict exists then the conflict is returned.
	private ResolverExport checkReqExpConflict(ResolverExport exp, ResolverExport expConstraints[], ResolverBundle bundle, ArrayList visited) {
	if (bundle == null)
	return null;
	if (visited.contains(bundle)) // return if we visited this bundle; prevent endless loops
	return null;
	visited.add(bundle); // mark as visited
	// check the consistency of all the selected exports
	ResolverExport[] exports = bundle.getSelectedExports();
	for (int i = 0; i < exports.length; i++) {
	// first check the constraints of the 'exp' with the exported packages of the 'bundle'
	for (int j = 0; j < expConstraints.length; j++)
	if (isConflict(exports[i], expConstraints[j]))
	return exp;
	// next check the constraints of each exported package of the 'bundle' with the 'exp'
	ResolverExport[] constraints = getConstraints(exports[i]);
	for (int j = 0; j < constraints.length; j++)
	if (isConflict(exp, constraints[j]))
	return exp;
	}
	// check the consistency of all the required bundles which we reexport
	BundleConstraint[] requires = bundle.getRequires();
	for (int i = 0; i < requires.length; i++)
	if (((BundleSpecification) requires[i].getVersionConstraint()).isExported()) {
	ResolverExport conflict = checkReqExpConflict(exp, expConstraints, requires[i].getMatchingBundle(), visited);
	if (conflict != null)
	return exp;
	}
	return null;
	}

	// returns true if the candidateRoot is NOT a root of the candidate ResolverExport
	private boolean isConflict(ResolverExport candidate, ResolverExport candidateRoot) {
	return candidateRoot.getExporter().isResolvable() && candidateRoot.getName().equals(candidate.getName()) && !isOnRoot(candidate.getRoots(), candidateRoot);
	}

	// checks that the specified ResolverExport is contained in the list of roots
	private boolean isOnRoot(ResolverExport[] roots, ResolverExport re) {
	for (int i = 0; i < roots.length; i++)
	// check the exporter; this handles multple exports of the same package name from a bundle
	if (roots[i].getExporter() == re.getExporter())
	return true;
	if (roots.length == 1 && !roots[0].getExportPackageDescription().isRoot())
	return true; // this is for a reexporter that does not have the import satisfied yet
	return false;
	}

	// Add initial 'uses' constraints for a list of bundles
	void addInitialGroupingConstraints(ResolverBundle initBundle) {
	if (bundles.containsKey(initBundle))
	return; // already processed
	// for each export; add it uses constraints
	ResolverExport[] exports = initBundle.getExportPackages();
	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(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) {
	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 = 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 (!createConstraints(cur).contains(constraintExports[j])) {
	addConstraint(exports, constraintExports[j]);
	addInitialGroupingConstraints(exports, constraintExports[j]);
	}
	}
	ResolverImport constraintImport = exporter.getImport(uses[i]);
	if (constraintImport != null && !constraintImport.isDynamic())
	addConstraint(exports, constraintImport);
	if (constraintExports.length == 0 && (constraintImport == null \|\| constraintImport.isDynamic()))
	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
	private class UsesRequiredExport {
	// the exported package which 'uses' a package from a required bundle
	private ResolverExport export;
	// the name of the package which is 'used'
	private String usesName;

	UsesRequiredExport(ResolverExport export, String usesName) {
	this.export = export;
	this.usesName = usesName;
	}

	public ResolverExport[] getRoots() {
	ArrayList results = new ArrayList(1); // rare to have more than 1
	BundleConstraint[] requires = export.getExporter().getRequires();
	for (int i = 0; i < requires.length; i++) {
	if (requires[i].getMatchingBundle() == null)
	continue;
	ResolverExport requiredExport = requires[i].getMatchingBundle().getExport(usesName);
	if (requiredExport != null && !requiredExport.isDropped()) {
	ResolverExport[] roots = requiredExport.getRoots();
	for (int j = 0; j < roots.length; j++)
	if (!results.contains(requiredExport))
	results.add(roots[j]);
	}
	}
	return (ResolverExport[]) results.toArray(new ResolverExport[results.size()]);
	}

	public boolean equals(Object o) {
	if (!(o instanceof UsesRequiredExport))
	return false;
	return ((UsesRequiredExport) o).export.getExporter() == export.getExporter() && usesName.equals(((UsesRequiredExport) o).usesName);
	}
	}

	public void setCheckCycles(boolean checkCycles) {
	this.checkCycles = checkCycles;
	}
	}