Description Jed Anderson 2002-09-10 13:10:37 EDT

Build: 20020903

The JavaProject#updateCycleParticipants(...) method implements an 
algorithm that takes O(pow(n - 1, n - 1)) in the worst case scenario.  The worst case scenario is when 
each project in the cycle is dependent on every other project in the cycle (a complete graph of 
dependencies).

Normally this is not a problem since developers tend to try and resolve 
circular dependencies.  However, some tools create ear files that contain (faulty?) manifest 
information that points each war in the ear to every other war in the ear.  When these ear files are 
imported into Eclipse, the resulting projects contain complete cyclic dependencies causing 
the cycle dependency code to never return (i.e. doesn't return for > 100 years).

A simple 
test:

1. Create 10 projects (A, B, ..., J)
2. For each project
  a. open the java build path 
dialog
  b. add all of the other projects to the build path
  c. click ok.

As you iterate 
through list, it will start taking longer & longer for the dialog to update after you select a 
project and longer & longer for the progress dialog to complete when you click OK to set the 
classpath.

When I ran this test, things became noticebly slower when I was editing project 
H's path (going alphabetically).  When I clicked 'OK' to set J's classpath it took 1m 15s to 
complete.

I propose the following code replace the current 
updateCycleParticipants(IClasspathEntry[], ArrayList, HashSet, IWorkspaceRoot) method 
in JavaProject.  

The previous version of this code would return the entire cycle that this 
project was involved in.  This will just return the first cycle found.  I think since we are only 
notifying the user of the existance of a cycle it is not necessary to find the entire 
cycle.

private static class CycleException extends Exception {
}
	
public void 
updateCycleParticipants(IClasspathEntry[] preferredClasspath, ArrayList visited, 
HashSet cycleParticipants, IWorkspaceRoot workspaceRoot){
	try 
{
		updateCycleParticipants0(preferredClasspath, visited, cycleParticipants, 
workspaceRoot);
	} catch (CycleException e) {
	}
}
	
/**
 * If a cycle is detected, 
then cycleParticipants contains all the project involved in this cycle (directly),
 * no cycle 
if the set is empty (and started empty)
 */
private void 
updateCycleParticipants0(IClasspathEntry[] preferredClasspath, ArrayList visited, 
HashSet cycleParticipants, IWorkspaceRoot workspaceRoot) throws CycleException {
	int 
index = visited.indexOf(this);
	if (index >= 0){
		// only consider direct participants 
inside the cycle
		for (int i = index, size = visited.size(); i < size; 
i++){
			cycleParticipants.add(visited.get(i)); 
		}
		throw new 
CycleException();
	} else {
		visited.add(this);
	}
	
	try 
{
		IClasspathEntry[] classpath;
		if (preferredClasspath == null) {
			classpath = 
getResolvedClasspath(true);
		} else {
			classpath = 
preferredClasspath;
		}
		for (int i = 0, length = classpath.length; i < length; i++) 
{
			IClasspathEntry entry = classpath[i];
			
			if (entry.getEntryKind() == 
IClasspathEntry.CPE_PROJECT){
				String projectName = 
entry.getPath().lastSegment();
				JavaProject project = 
(JavaProject)JavaCore.create(workspaceRoot.getProject(projectName));
				project.updateCycleParticipants0(null, 
visited, cycleParticipants, workspaceRoot);
			}
		}
	} catch(JavaModelException e) 
{
	}
	visited.remove(this);
}