[Rubyeclipse-commit] SF.net SVN: rubyeclipse: [2749] trunk/org.rubypeople.rdt.core/src/org/ rubypeople/rdt

[<caw...@us...>]

Revision: 2749
          http://svn.sourceforge.net/rubyeclipse/?rev=2749&view=rev
Author:   cawilliams
Date:     2007-07-11 13:32:07 -0700 (Wed, 11 Jul 2007)

Log Message:
-----------
first stab at the core code for type hierarchy stuff

Modified Paths:
--------------
    trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/RubyElement.java
    trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/search/indexing/SourceIndexer.java
    trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/search/indexing/SourceIndexerRequestor.java
    trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/util/Messages.java
    trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/util/Util.java

Added Paths:
-----------
    trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/core/IRegion.java
    trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/IPathRequestor.java
    trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/LogicalType.java
    trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/Region.java
    trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/TypeVector.java
    trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/hierarchy/
    trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/hierarchy/ChangeCollector.java
    trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/hierarchy/HierarchyBuilder.java
    trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/hierarchy/HierarchyResolver.java
    trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/hierarchy/IndexBasedHierarchyBuilder.java
    trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/hierarchy/TypeHierarchy.java
    trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/search/SubTypeSearchJob.java
    trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/search/matching/SuperTypeReferencePattern.java

Added: trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/core/IRegion.java
===================================================================
--- trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/core/IRegion.java	                        (rev 0)
+++ trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/core/IRegion.java	2007-07-11 20:32:07 UTC (rev 2749)
@@ -0,0 +1,67 @@
+/*******************************************************************************
+ * Copyright (c) 2000, 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.rubypeople.rdt.core;
+
+/**
+ * A Ruby model region describes a hierarchical set of elements.
+ * Regions are often used to describe a set of elements to be considered
+ * when performing operations; for example, the set of elements to be
+ * considered during a search. A region may include elements from different
+ * projects.
+ * <p>
+ * When an element is included in a region, all of its children
+ * are considered to be included. Children of an included element 
+ * <b>cannot</b> be selectively excluded.
+ * </p>
+ * <p>
+ * This interface is not intended to be implemented by clients.
+ * Instances can be created via the <code>RubyCore.newRegion</code>.
+ * </p>
+ *
+ * @see RubyCore#newRegion()
+ */
+public interface IRegion {
+	/**
+	 * Adds the given element and all of its descendents to this region.
+	 * If the specified element is already included, or one of its
+	 * ancestors is already included, this has no effect. If the element
+	 * being added is an ancestor of an element already contained in this
+	 * region, the ancestor subsumes the descendent.
+	 * 
+	 * @param element the given element
+	 */
+	void add(IRubyElement element);
+	/**
+	 * Returns whether the given element is contained in this region.
+	 * 
+	 * @param element the given element
+	 * @return true if the given element is contained in this region, false otherwise
+	 */
+	boolean contains(IRubyElement element);
+	/**
+	 * Returns the top level elements in this region.
+	 * All descendents of these elements are also included in this region.
+	 * 
+	 * @return the top level elements in this region
+	 */
+	IRubyElement[] getElements();
+	/**
+	 * Removes the specified element from the region and returns
+	 * <code>true</code> if successful, <code>false</code> if the remove
+	 * fails. If an ancestor of the given element is included, the
+	 * remove fails (in other words, it is not possible to selectively
+	 * exclude descendants of included ancestors).
+	 * 
+	 * @param element the given element
+	 * @return <code>true</code> if successful, <code>false</code> if the remove fails
+	 */
+	boolean remove(IRubyElement element);
+}

Added: trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/IPathRequestor.java
===================================================================
--- trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/IPathRequestor.java	                        (rev 0)
+++ trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/IPathRequestor.java	2007-07-11 20:32:07 UTC (rev 2749)
@@ -0,0 +1,15 @@
+/*******************************************************************************
+ * Copyright (c) 2000, 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.rubypeople.rdt.internal.core;
+
+public interface IPathRequestor {
+	void acceptPath(String path, boolean containsLocalTypes);
+}

Added: trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/LogicalType.java
===================================================================
--- trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/LogicalType.java	                        (rev 0)
+++ trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/LogicalType.java	2007-07-11 20:32:07 UTC (rev 2749)
@@ -0,0 +1,39 @@
+package org.rubypeople.rdt.internal.core;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import org.rubypeople.rdt.core.IRubyElement;
+import org.rubypeople.rdt.core.IType;
+import org.rubypeople.rdt.core.RubyModelException;
+
+public class LogicalType extends RubyType implements IType {
+
+	private IType[] types;
+
+	public LogicalType(IType[] types) {
+		super(null, types[0].getElementName());
+		this.types = types;
+	}
+	
+	@Override
+	public IRubyElement[] getChildren() throws RubyModelException {
+		List<IRubyElement> children = new ArrayList<IRubyElement>();
+		for (int i = 0; i < types.length; i++) {
+			IRubyElement[] subchildren = types[i].getChildren();
+			for (int j = 0; j < subchildren.length; j++) {
+				children.add(subchildren[j]);
+			}
+		}
+		return (IRubyElement[]) children.toArray(new IRubyElement[children.size()]);
+	}
+	
+	@Override
+	public boolean hasChildren() throws RubyModelException {
+		for (int i = 0; i < types.length; i++) {
+			if (types[i].hasChildren()) return true;
+		}
+		return false;
+	}
+
+}

Added: trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/Region.java
===================================================================
--- trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/Region.java	                        (rev 0)
+++ trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/Region.java	2007-07-11 20:32:07 UTC (rev 2749)
@@ -0,0 +1,151 @@
+/*******************************************************************************
+ * Copyright (c) 2000, 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.rubypeople.rdt.internal.core;
+
+import java.util.ArrayList;
+
+import org.rubypeople.rdt.core.IParent;
+import org.rubypeople.rdt.core.IRegion;
+import org.rubypeople.rdt.core.IRubyElement;
+
+
+/**
+ * @see IRegion
+ */
+ 
+public class Region implements IRegion {
+
+	/**
+	 * A collection of the top level elements
+	 * that have been added to the region
+	 */
+	protected ArrayList fRootElements;
+/**
+ * Creates an empty region.
+ *
+ * @see IRegion
+ */
+public Region() {
+	fRootElements = new ArrayList(1);
+}
+/**
+ * @see IRegion#add(IRubyElement)
+ */
+public void add(IRubyElement element) {
+	if (!contains(element)) {
+		//"new" element added to region
+		removeAllChildren(element);
+		fRootElements.add(element);
+		fRootElements.trimToSize();
+	}
+}
+/**
+ * @see IRegion
+ */
+public boolean contains(IRubyElement element) {
+	
+	int size = fRootElements.size();
+	ArrayList parents = getAncestors(element);
+	
+	for (int i = 0; i < size; i++) {
+		IRubyElement aTop = (IRubyElement) fRootElements.get(i);
+		if (aTop.equals(element)) {
+			return true;
+		}
+		for (int j = 0, pSize = parents.size(); j < pSize; j++) {
+			if (aTop.equals(parents.get(j))) {
+				//an ancestor is already included
+				return true;
+			}
+		}
+	}
+	return false;
+}
+/**
+ * Returns a collection of all the parents of this element
+ * in bottom-up order.
+ *
+ */
+private ArrayList getAncestors(IRubyElement element) {
+	ArrayList parents = new ArrayList();
+	IRubyElement parent = element.getParent();
+	while (parent != null) {
+		parents.add(parent);
+		parent = parent.getParent();
+	}
+	parents.trimToSize();
+	return parents;
+}
+/**
+ * @see IRegion
+ */
+public IRubyElement[] getElements() {
+	int size= fRootElements.size();
+	IRubyElement[] roots= new IRubyElement[size];
+	for (int i = 0; i < size; i++) {
+		roots[i]= (IRubyElement) fRootElements.get(i);
+	}
+
+	return roots;
+}
+/**
+ * @see IRegion#remove(IRubyElement)
+ */
+public boolean remove(IRubyElement element) {
+
+	removeAllChildren(element);
+	return fRootElements.remove(element);
+}
+/**
+ * Removes any children of this element that are contained within this
+ * region as this parent is about to be added to the region.
+ *
+ * <p>Children are all children, not just direct children.
+ */
+protected void removeAllChildren(IRubyElement element) {
+	if (element instanceof IParent) {
+		ArrayList newRootElements = new ArrayList();
+		for (int i = 0, size = fRootElements.size(); i < size; i++) {
+			IRubyElement currentRoot = (IRubyElement)fRootElements.get(i);
+			//walk the current root hierarchy
+			IRubyElement parent = currentRoot.getParent();
+			boolean isChild= false;
+			while (parent != null) {
+				if (parent.equals(element)) {
+					isChild= true;
+					break;
+				}
+				parent = parent.getParent();
+			}
+			if (!isChild) {
+				newRootElements.add(currentRoot);
+			}
+		}
+		fRootElements= newRootElements;
+	}
+}
+/**
+ * Returns a printable representation of this region.
+ */
+public String toString() {
+	StringBuffer buffer= new StringBuffer();
+	IRubyElement[] roots= getElements();
+	buffer.append('[');
+	for (int i= 0; i < roots.length; i++) {
+		buffer.append(roots[i].getElementName());
+		if (i < (roots.length - 1)) {
+			buffer.append(", "); //$NON-NLS-1$
+		}
+	}
+	buffer.append(']');
+	return buffer.toString();
+}
+}

Modified: trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/RubyElement.java
===================================================================
--- trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/RubyElement.java	2007-07-11 16:52:44 UTC (rev 2748)
+++ trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/RubyElement.java	2007-07-11 20:32:07 UTC (rev 2749)
@@ -627,4 +627,8 @@
 			buffer.append(character);
 		}
 	}
+
+	public IRubyElement unresolved() {
+		return this;
+	}
 }

Added: trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/TypeVector.java
===================================================================
--- trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/TypeVector.java	                        (rev 0)
+++ trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/TypeVector.java	2007-07-11 20:32:07 UTC (rev 2749)
@@ -0,0 +1,114 @@
+/*******************************************************************************
+ * Copyright (c) 2000, 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.rubypeople.rdt.internal.core;
+
+import org.rubypeople.rdt.core.IType;
+
+
+public final class TypeVector {
+	static int INITIAL_SIZE = 10;
+	
+	public int size;
+	int maxSize;
+	IType[] elements;
+	
+	public final static IType[] NoElements = new IType[0];
+	
+public TypeVector() {
+	maxSize = INITIAL_SIZE;
+	size = 0;
+	elements = new IType[maxSize];
+}
+public TypeVector(IType[] types) {
+	this.size = types.length; 
+	this.maxSize = this.size + 1; // when an element is added, it assumes that the length is > 0
+	elements = new IType[this.maxSize];
+	System.arraycopy(types, 0, elements, 0, this.size);	
+}
+public TypeVector(IType type) {
+	this.maxSize = INITIAL_SIZE;
+	this.size = 1;
+	elements = new IType[this.maxSize];
+	elements[0] = type;
+}
+public void add(IType newElement) {
+	if (size == maxSize)	// knows that size starts <= maxSize
+		System.arraycopy(elements, 0, (elements = new IType[maxSize *= 2]), 0, size);
+	elements[size++] = newElement;
+}
+public void addAll(IType[] newElements) {
+	if (size + newElements.length >= maxSize) {
+		maxSize = size + newElements.length;	// assume no more elements will be added
+		System.arraycopy(elements, 0, (elements = new IType[maxSize]), 0, size);
+	}
+	System.arraycopy(newElements, 0, elements, size, newElements.length);
+	size += newElements.length;
+}
+public boolean contains(IType element) {
+	for (int i = size; --i >= 0;)
+		if (element.equals(elements[i]))
+			return true;
+	return false;
+}
+public TypeVector copy() {
+	TypeVector clone = new TypeVector();
+	int length = this.elements.length;
+	System.arraycopy(this.elements, 0, clone.elements = new IType[length], 0, length);
+	clone.size = this.size;
+	clone.maxSize = this.maxSize;
+	return clone;
+}
+public IType elementAt(int index) {
+	return elements[index];
+}
+public IType[] elements() {
+	
+	// do not resize to 0 if empty since may add more elements later
+	if (this.size == 0) return NoElements;
+	
+	if (this.size < this.maxSize) {
+		maxSize = size;
+		System.arraycopy(this.elements, 0, (this.elements = new IType[maxSize]), 0, size);
+	}
+	return this.elements;
+}
+public IType find(IType element) {
+	for (int i = size; --i >= 0;)
+		if (element == elements[i])
+			return elements[i];
+	return null;
+}
+public IType remove(IType element) {
+	// assumes only one occurrence of the element exists
+	for (int i = size; --i >= 0;)
+		if (element == elements[i]) {
+			// shift the remaining elements down one spot
+			System.arraycopy(elements, i + 1, elements, i, --size - i);
+			elements[size] = null;
+			return element;
+		}
+	return null;
+}
+public void removeAll() {
+	for (int i = size; --i >= 0;)
+		elements[i] = null;
+	size = 0;
+}
+public String toString() {
+	StringBuffer buffer = new StringBuffer("["); //$NON-NLS-1$
+	for (int i = 0; i < size; i++) {
+		buffer.append("\n"); //$NON-NLS-1$
+		buffer.append(elements[i]);
+	}
+	buffer.append("\n]"); //$NON-NLS-1$
+	return buffer.toString();
+}
+}

Added: trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/hierarchy/ChangeCollector.java
===================================================================
--- trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/hierarchy/ChangeCollector.java	                        (rev 0)
+++ trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/hierarchy/ChangeCollector.java	2007-07-11 20:32:07 UTC (rev 2749)
@@ -0,0 +1,448 @@
+/*******************************************************************************
+ * Copyright (c) 2000, 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.rubypeople.rdt.internal.core.hierarchy;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.Map;
+
+import org.rubypeople.rdt.core.IImportContainer;
+import org.rubypeople.rdt.core.IImportDeclaration;
+import org.rubypeople.rdt.core.IMember;
+import org.rubypeople.rdt.core.IRubyElement;
+import org.rubypeople.rdt.core.IRubyElementDelta;
+import org.rubypeople.rdt.core.IRubyScript;
+import org.rubypeople.rdt.core.IType;
+import org.rubypeople.rdt.core.RubyModelException;
+import org.rubypeople.rdt.internal.core.RubyElement;
+import org.rubypeople.rdt.internal.core.SimpleDelta;
+
+/*
+ * Collects changes (reported through fine-grained deltas) that can affect a type hierarchy.
+ */
+public class ChangeCollector {
+	
+	/*
+	 * A table from ITypes to TypeDeltas
+	 */
+	HashMap changes = new HashMap();
+	
+	TypeHierarchy hierarchy;
+	
+	public ChangeCollector(TypeHierarchy hierarchy) {
+		this.hierarchy = hierarchy;
+	}
+	
+	/*
+	 * Adds the children of the given delta to the list of changes.
+	 */
+	private void addAffectedChildren(IRubyElementDelta delta) throws RubyModelException {
+		IRubyElementDelta[] children = delta.getAffectedChildren();
+		for (int i = 0, length = children.length; i < length; i++) {
+			IRubyElementDelta child = children[i];
+			IRubyElement childElement = child.getElement();
+			switch (childElement.getElementType()) {
+				case IRubyElement.IMPORT_CONTAINER:
+					addChange((IImportContainer)childElement, child);
+					break;
+				case IRubyElement.IMPORT_DECLARATION:
+					addChange((IImportDeclaration)childElement, child);
+					break;
+				case IRubyElement.TYPE:
+					addChange((IType)childElement, child);
+					break;
+//				case IRubyElement.INITIALIZER:
+				case IRubyElement.FIELD:
+				case IRubyElement.METHOD:
+					addChange((IMember)childElement, child);
+					break;
+			}
+		}
+	}
+	
+	/*
+	 * Adds the given delta on a compilation unit to the list of changes.
+	 */
+	public void addChange(IRubyScript cu, IRubyElementDelta newDelta) throws RubyModelException {
+		int newKind = newDelta.getKind();
+		switch (newKind) {
+			case IRubyElementDelta.ADDED:
+				ArrayList allTypes = new ArrayList();
+				getAllTypesFromElement(cu, allTypes);
+				for (int i = 0, length = allTypes.size(); i < length; i++) {
+					IType type = (IType)allTypes.get(i);
+					addTypeAddition(type, (SimpleDelta)this.changes.get(type));
+				}
+				break;
+			case IRubyElementDelta.REMOVED:
+				allTypes = new ArrayList();
+				getAllTypesFromHierarchy((RubyElement)cu, allTypes);
+				for (int i = 0, length = allTypes.size(); i < length; i++) {
+					IType type = (IType)allTypes.get(i);
+					addTypeRemoval(type, (SimpleDelta)this.changes.get(type));
+				}
+				break;
+			case IRubyElementDelta.CHANGED:
+				addAffectedChildren(newDelta);
+				break;
+		}
+	}
+	
+	private void addChange(IImportContainer importContainer, IRubyElementDelta newDelta) throws RubyModelException {
+		int newKind = newDelta.getKind();
+		if (newKind == IRubyElementDelta.CHANGED) {
+			addAffectedChildren(newDelta);
+			return;
+		}
+		SimpleDelta existingDelta = (SimpleDelta)this.changes.get(importContainer);
+		if (existingDelta != null) {
+			switch (newKind) {
+				case IRubyElementDelta.ADDED:
+					if (existingDelta.getKind() == IRubyElementDelta.REMOVED) {
+						// REMOVED then ADDED
+						this.changes.remove(importContainer);
+					}
+					break;
+				case IRubyElementDelta.REMOVED:
+					if (existingDelta.getKind() == IRubyElementDelta.ADDED) {
+						// ADDED then REMOVED
+						this.changes.remove(importContainer);
+					}
+					break;
+					// CHANGED handled above
+			}
+		} else {
+			SimpleDelta delta = new SimpleDelta();
+			switch (newKind) {
+				case IRubyElementDelta.ADDED:
+					delta.added();
+					break;
+				case IRubyElementDelta.REMOVED:
+					delta.removed();
+					break;
+			}
+			this.changes.put(importContainer, delta);
+		}
+	}
+
+	private void addChange(IImportDeclaration importDecl, IRubyElementDelta newDelta) {
+		SimpleDelta existingDelta = (SimpleDelta)this.changes.get(importDecl);
+		int newKind = newDelta.getKind();
+		if (existingDelta != null) {
+			switch (newKind) {
+				case IRubyElementDelta.ADDED:
+					if (existingDelta.getKind() == IRubyElementDelta.REMOVED) {
+						// REMOVED then ADDED
+						this.changes.remove(importDecl);
+					}
+					break;
+				case IRubyElementDelta.REMOVED:
+					if (existingDelta.getKind() == IRubyElementDelta.ADDED) {
+						// ADDED then REMOVED
+						this.changes.remove(importDecl);
+					}
+					break;
+				// CHANGED cannot happen for import declaration
+			}
+		} else {
+			SimpleDelta delta = new SimpleDelta();
+			switch (newKind) {
+				case IRubyElementDelta.ADDED:
+					delta.added();
+					break;
+				case IRubyElementDelta.REMOVED:
+					delta.removed();
+					break;
+			}
+			this.changes.put(importDecl, delta);
+		}
+	}
+	
+	/*
+	 * Adds a change for the given member (a method, a field or an initializer) and the types it defines.
+	 */
+	private void addChange(IMember member, IRubyElementDelta newDelta) throws RubyModelException {
+		int newKind = newDelta.getKind();
+		switch (newKind) {
+			case IRubyElementDelta.ADDED:
+				ArrayList allTypes = new ArrayList();
+				getAllTypesFromElement(member, allTypes);
+				for (int i = 0, length = allTypes.size(); i < length; i++) {
+					IType innerType = (IType)allTypes.get(i);
+					addTypeAddition(innerType, (SimpleDelta)this.changes.get(innerType));
+				}
+				break;
+			case IRubyElementDelta.REMOVED:
+				allTypes = new ArrayList();
+				getAllTypesFromHierarchy((RubyElement)member, allTypes);
+				for (int i = 0, length = allTypes.size(); i < length; i++) {
+					IType type = (IType)allTypes.get(i);
+					addTypeRemoval(type, (SimpleDelta)this.changes.get(type));
+				}
+				break;
+			case IRubyElementDelta.CHANGED:
+				addAffectedChildren(newDelta);
+				break;
+		}
+	}
+	
+	/*
+	 * Adds a change for the given type and the types it defines.
+	 */
+	private void addChange(IType type, IRubyElementDelta newDelta) throws RubyModelException {
+		 int newKind = newDelta.getKind();
+		SimpleDelta existingDelta = (SimpleDelta)this.changes.get(type);
+		switch (newKind) {
+			case IRubyElementDelta.ADDED:
+				addTypeAddition(type, existingDelta);
+				ArrayList allTypes = new ArrayList();
+				getAllTypesFromElement(type, allTypes);
+				for (int i = 0, length = allTypes.size(); i < length; i++) {
+					IType innerType = (IType)allTypes.get(i);
+					addTypeAddition(innerType, (SimpleDelta)this.changes.get(innerType));
+				}
+				break;
+			case IRubyElementDelta.REMOVED:
+				addTypeRemoval(type, existingDelta);
+				allTypes = new ArrayList();
+				getAllTypesFromHierarchy((RubyElement)type, allTypes);
+				for (int i = 0, length = allTypes.size(); i < length; i++) {
+					IType innerType = (IType)allTypes.get(i);
+					addTypeRemoval(innerType, (SimpleDelta)this.changes.get(innerType));
+				}
+				break;
+			case IRubyElementDelta.CHANGED:
+				addTypeChange(type, newDelta.getFlags(), existingDelta);
+				addAffectedChildren(newDelta);
+				break;
+		}
+	}
+
+	private void addTypeAddition(IType type, SimpleDelta existingDelta) throws RubyModelException {
+		if (existingDelta != null) {
+			switch (existingDelta.getKind()) {
+				case IRubyElementDelta.REMOVED:
+					// REMOVED then ADDED
+					boolean hasChange = false;
+					if (hasSuperTypeChange(type)) {
+						existingDelta.superTypes();
+						hasChange = true;
+					} 
+					if (hasVisibilityChange(type)) {
+						existingDelta.modifiers();
+						hasChange = true;
+					}
+					if (!hasChange) {
+						this.changes.remove(type);
+					}
+					break;
+					// CHANGED then ADDED
+					// or ADDED then ADDED: should not happen
+			}
+		} else {
+			// check whether the type addition affects the hierarchy
+			String typeName = type.getElementName();
+			if (this.hierarchy.hasSupertype(typeName) 
+					|| this.hierarchy.subtypesIncludeSupertypeOf(type) 
+					|| this.hierarchy.missingTypes.contains(typeName)) {
+				SimpleDelta delta = new SimpleDelta();
+				delta.added();
+				this.changes.put(type, delta);
+			}
+		}
+	}
+	
+	private void addTypeChange(IType type, int newFlags, SimpleDelta existingDelta) throws RubyModelException {
+		if (existingDelta != null) {
+			switch (existingDelta.getKind()) {
+				case IRubyElementDelta.CHANGED:
+					// CHANGED then CHANGED
+					int existingFlags = existingDelta.getFlags();
+					boolean hasChange = false;
+					if ((existingFlags & IRubyElementDelta.F_SUPER_TYPES) != 0
+							&& hasSuperTypeChange(type)) {
+						existingDelta.superTypes();
+						hasChange = true;
+					} 
+					if ((existingFlags & IRubyElementDelta.F_MODIFIERS) != 0
+							&& hasVisibilityChange(type)) {
+						existingDelta.modifiers();
+						hasChange = true;
+					}
+					if (!hasChange) {
+						// super types and visibility are back to the ones in the existing hierarchy
+						this.changes.remove(type);
+					}
+					break;
+					// ADDED then CHANGED: leave it as ADDED
+					// REMOVED then CHANGED: should not happen
+			}
+		} else {
+			// check whether the type change affects the hierarchy
+			SimpleDelta typeDelta = null;
+			if ((newFlags & IRubyElementDelta.F_SUPER_TYPES) != 0 
+					&& this.hierarchy.includesTypeOrSupertype(type)) {
+				typeDelta = new SimpleDelta();
+				typeDelta.superTypes();
+			}
+			if ((newFlags & IRubyElementDelta.F_MODIFIERS) != 0
+					&& (this.hierarchy.hasSupertype(type.getElementName())
+						|| type.equals(this.hierarchy.focusType))) {
+				if (typeDelta == null) {
+					typeDelta = new SimpleDelta();
+				}
+				typeDelta.modifiers();
+			}
+			if (typeDelta != null) {
+				this.changes.put(type, typeDelta);
+			}
+		}
+	}
+
+	private void addTypeRemoval(IType type, SimpleDelta existingDelta) {
+		if (existingDelta != null) {
+			switch (existingDelta.getKind()) {
+				case IRubyElementDelta.ADDED:
+					// ADDED then REMOVED
+					this.changes.remove(type);
+					break;
+				case IRubyElementDelta.CHANGED:
+					// CHANGED then REMOVED
+					existingDelta.removed();
+					break;
+					// REMOVED then REMOVED: should not happen
+			}
+		} else {
+			// check whether the type removal affects the hierarchy
+			if (this.hierarchy.contains(type)) {
+				SimpleDelta typeDelta = new SimpleDelta();
+				typeDelta.removed();
+				this.changes.put(type, typeDelta);
+			}
+		}
+	}
+	
+	/*
+	 * Returns all types defined in the given element excluding the given element.
+	 */
+	private void getAllTypesFromElement(IRubyElement element, ArrayList allTypes) throws RubyModelException {
+		switch (element.getElementType()) {
+			case IRubyElement.SCRIPT:
+				IType[] types = ((IRubyScript)element).getTypes();
+				for (int i = 0, length = types.length; i < length; i++) {
+					IType type = types[i];
+					allTypes.add(type);
+					getAllTypesFromElement(type, allTypes);
+				}
+				break;
+			case IRubyElement.TYPE:
+				types = ((IType)element).getTypes();
+				for (int i = 0, length = types.length; i < length; i++) {
+					IType type = types[i];
+					allTypes.add(type);
+					getAllTypesFromElement(type, allTypes);
+				}
+				break;
+//			case IRubyElement.INITIALIZER:
+			case IRubyElement.FIELD:
+			case IRubyElement.METHOD:
+				IRubyElement[] children = ((IMember)element).getChildren();
+				for (int i = 0, length = children.length; i < length; i++) {
+					IType type = (IType)children[i];
+					allTypes.add(type);
+					getAllTypesFromElement(type, allTypes);
+				}
+				break;
+		}
+	}
+	
+	/*
+	 * Returns all types in the existing hierarchy that have the given element as a parent.
+	 */
+	private void getAllTypesFromHierarchy(RubyElement element, ArrayList allTypes) {
+		switch (element.getElementType()) {
+			case IRubyElement.SCRIPT:
+				ArrayList types = (ArrayList)this.hierarchy.files.get(element);
+				if (types != null) {
+					allTypes.addAll(types);
+				}
+				break;
+			case IRubyElement.TYPE:
+//			case IRubyElement.INITIALIZER:
+			case IRubyElement.FIELD:
+			case IRubyElement.METHOD:
+				types = (ArrayList)this.hierarchy.files.get(((IMember)element).getRubyScript());
+				if (types != null) {
+					for (int i = 0, length = types.size(); i < length; i++) {
+						IType type = (IType)types.get(i);
+						if (element.isAncestorOf(type)) {
+							allTypes.add(type);
+						}
+					}
+				}
+				break;
+		}
+	}
+	
+	private boolean hasSuperTypeChange(IType type) throws RubyModelException {
+		// check super class
+		IType superclass = this.hierarchy.getSuperclass(type);
+		String existingSuperclassName = superclass == null ? null : superclass.getElementName();
+		String newSuperclassName = type.getSuperclassName();
+		if (existingSuperclassName != null && !existingSuperclassName.equals(newSuperclassName)) {
+			return true;
+		}
+		
+		// check super interfaces
+		IType[] existingSuperInterfaces = this.hierarchy.getSuperInterfaces(type);
+		String[] newSuperInterfaces = type.getIncludedModuleNames();
+		if (existingSuperInterfaces.length != newSuperInterfaces.length) {
+			return true;
+		}
+		for (int i = 0, length = newSuperInterfaces.length; i < length; i++) {
+			String superInterfaceName = newSuperInterfaces[i];
+			if (!superInterfaceName.equals(newSuperInterfaces[i])) {
+				return true;
+			}
+		}
+		
+		return false;
+	}
+	
+	private boolean hasVisibilityChange(IType type) throws RubyModelException {
+//		int existingFlags = this.hierarchy.getCachedFlags(type);
+//		int newFlags = type.getFlags();
+//		return existingFlags != newFlags;
+		return false; // FIXME Types don't have visibility options in Ruby! We shouldn't even ask this.
+	}
+
+	/*
+	 * Whether the hierarchy needs refresh according to the changes collected so far.
+	 */
+	public boolean needsRefresh() {
+		return changes.size() != 0;
+	}
+	
+	public String toString() {
+		StringBuffer buffer = new StringBuffer();
+		Iterator iterator = this.changes.entrySet().iterator();
+		while (iterator.hasNext()) {
+			Map.Entry entry = (Map.Entry)iterator.next();
+			buffer.append(((RubyElement)entry.getKey()).toDebugString());
+			buffer.append(entry.getValue());
+			if (iterator.hasNext()) {
+				buffer.append('\n');
+			}
+		}
+		return buffer.toString();
+	}
+}

Added: trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/hierarchy/HierarchyBuilder.java
===================================================================
--- trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/hierarchy/HierarchyBuilder.java	                        (rev 0)
+++ trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/hierarchy/HierarchyBuilder.java	2007-07-11 20:32:07 UTC (rev 2749)
@@ -0,0 +1,168 @@
+/*******************************************************************************
+ * Copyright (c) 2000, 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.rubypeople.rdt.internal.core.hierarchy;
+
+import java.util.HashMap;
+import java.util.Map;
+
+import org.eclipse.core.runtime.CoreException;
+import org.rubypeople.rdt.core.IType;
+import org.rubypeople.rdt.core.RubyModelException;
+import org.rubypeople.rdt.internal.core.RubyElement;
+import org.rubypeople.rdt.internal.core.RubyProject;
+
+
+
+public abstract class HierarchyBuilder {
+	/**
+	 * The hierarchy being built.
+	 */
+	protected TypeHierarchy hierarchy;
+
+	/**
+	 * A temporary cache of infos to handles to speed info
+	 * to handle translation - it only contains the entries
+	 * for the types in the region (in other words, it contains
+	 * no supertypes outside the region).
+	 */
+	protected Map infoToHandle;
+	/*
+	 * The dot-separated fully qualified name of the focus type, or null of none.
+	 */
+	protected String focusQualifiedName;
+
+	protected HierarchyResolver hierarchyResolver;
+	
+	public HierarchyBuilder(TypeHierarchy hierarchy) throws RubyModelException {
+		
+		this.hierarchy = hierarchy;
+		RubyProject project = (RubyProject) hierarchy.javaProject();
+		
+		IType focusType = hierarchy.getType();
+		org.rubypeople.rdt.core.IRubyScript unitToLookInside = focusType == null ? null : focusType.getRubyScript();
+		org.rubypeople.rdt.core.IRubyScript[] workingCopies = this.hierarchy.workingCopies;
+		org.rubypeople.rdt.core.IRubyScript[] unitsToLookInside;
+		if (unitToLookInside != null) {
+			int wcLength = workingCopies == null ? 0 : workingCopies.length;
+			if (wcLength == 0) {
+				unitsToLookInside = new org.rubypeople.rdt.core.IRubyScript[] {unitToLookInside};
+			} else {
+				unitsToLookInside = new org.rubypeople.rdt.core.IRubyScript[wcLength+1];
+				unitsToLookInside[0] = unitToLookInside;
+				System.arraycopy(workingCopies, 0, unitsToLookInside, 1, wcLength);
+			}
+		} else {
+			unitsToLookInside = workingCopies;
+		}
+		if (project != null) {
+//			SearchableEnvironment searchableEnvironment = project.newSearchableNameEnvironment(unitsToLookInside);
+//			this.nameLookup = searchableEnvironment.nameLookup;
+			this.hierarchyResolver =
+				new HierarchyResolver(
+//					searchableEnvironment,
+					project.getOptions(true),
+					this
+					);
+//					new DefaultProblemFactory());
+		}
+		this.infoToHandle = new HashMap(5);
+		this.focusQualifiedName = focusType == null ? null : focusType.getFullyQualifiedName();
+	}
+	
+	public abstract void build(boolean computeSubtypes)
+		throws RubyModelException, CoreException;
+	
+	/**
+	 * Connect the supplied type to its superclass & superinterfaces.
+	 * The superclass & superinterfaces are the identical binary or source types as
+	 * supplied by the name environment.
+	 */
+	public void connect(
+		IType typeHandle,
+		IType superclassHandle,
+		IType[] superinterfaceHandles) {
+
+		/*
+		 * Temporary workaround for 1G2O5WK: ITPJCORE:WINNT - NullPointerException when selecting "Show in Type Hierarchy" for a inner class
+		 */
+		if (typeHandle == null)
+			return;
+		if (TypeHierarchy.DEBUG) {
+			System.out.println(
+				"Connecting: " + ((RubyElement) typeHandle).toStringWithAncestors()); //$NON-NLS-1$
+			System.out.println(
+				"  to superclass: " //$NON-NLS-1$
+					+ (superclassHandle == null
+						? "<None>" //$NON-NLS-1$
+						: ((RubyElement) superclassHandle).toStringWithAncestors()));
+			System.out.print("  and superinterfaces:"); //$NON-NLS-1$
+			if (superinterfaceHandles == null || superinterfaceHandles.length == 0) {
+				System.out.println(" <None>"); //$NON-NLS-1$
+			} else {
+				System.out.println();
+				for (int i = 0, length = superinterfaceHandles.length; i < length; i++) {
+					if (superinterfaceHandles[i] == null) continue;
+					System.out.println(
+						"    " + ((RubyElement) superinterfaceHandles[i]).toStringWithAncestors()); //$NON-NLS-1$
+				}
+			}
+		}
+		// now do the caching
+		if (typeHandle.isModule()) {
+			this.hierarchy.addInterface(typeHandle);
+		} else {
+			if (superclassHandle == null) {
+				this.hierarchy.addRootClass(typeHandle);
+			} else {
+				this.hierarchy.cacheSuperclass(typeHandle, superclassHandle);
+			}
+		}
+		if (superinterfaceHandles == null) {
+			superinterfaceHandles = TypeHierarchy.NO_TYPE;
+		}
+		this.hierarchy.cacheSuperInterfaces(typeHandle, superinterfaceHandles);
+		 
+		// record flags
+		this.hierarchy.cacheFlags(typeHandle, /*type.getModifiers()*/ 0 );
+	}
+	
+	protected IType getType() {
+		return this.hierarchy.getType();
+	}
+	
+	
+	/**
+	 * Configure this type hierarchy by computing the supertypes only.
+	 */
+	protected void buildSupertypes() {
+		IType focusType = this.getType();
+		if (focusType == null)
+			return;
+		// get generic type from focus type
+//		IGenericType type;
+//		try {
+//			type = (IGenericType) ((JavaElement) focusType).getElementInfo();
+//		} catch (JavaModelException e) {
+//			// if the focus type is not present, or if cannot get workbench path
+//			// we cannot create the hierarchy
+//			return;
+//		}
+		//NB: no need to set focus type on hierarchy resolver since no other type is injected
+		//    in the hierarchy resolver, thus there is no need to check that a type is 
+		//    a sub or super type of the focus type.
+		this.hierarchyResolver.resolve(focusType);
+
+		// Add focus if not already in (case of a type with no explicit super type)
+		if (!this.hierarchy.contains(focusType)) {
+			this.hierarchy.addRootClass(focusType);
+		}
+	}
+}

Added: trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/hierarchy/HierarchyResolver.java
===================================================================
--- trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/hierarchy/HierarchyResolver.java	                        (rev 0)
+++ trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/hierarchy/HierarchyResolver.java	2007-07-11 20:32:07 UTC (rev 2749)
@@ -0,0 +1,114 @@
+package org.rubypeople.rdt.internal.core.hierarchy;
+
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+
+import org.eclipse.core.runtime.IPath;
+import org.eclipse.core.runtime.IProgressMonitor;
+import org.rubypeople.rdt.core.IType;
+import org.rubypeople.rdt.core.RubyModelException;
+import org.rubypeople.rdt.internal.codeassist.RubyElementRequestor;
+import org.rubypeople.rdt.internal.core.LogicalType;
+import org.rubypeople.rdt.internal.core.Openable;
+
+public class HierarchyResolver {
+
+	private boolean superTypesOnly;
+	private HierarchyBuilder builder;
+
+	public HierarchyResolver(Map options, HierarchyBuilder builder) {
+		this.builder = builder;
+	}
+
+	public void resolve(Openable[] openables, HashSet localTypes, IProgressMonitor monitor) {
+		try {
+			int openablesLength = openables.length;
+			boolean[] hasLocalType = new boolean[openablesLength];
+			org.rubypeople.rdt.core.IRubyScript[] cus = new org.rubypeople.rdt.core.IRubyScript[openablesLength];
+			int unitsIndex = 0;
+			
+			IType focus = this.builder.getType();
+			Openable focusOpenable = null;
+			if (focus != null) {
+				focusOpenable = (Openable)focus.getRubyScript();
+			}
+			
+			for (int i = 0; i < openablesLength; i++) {
+				Openable openable = openables[i];
+				if (openable instanceof org.rubypeople.rdt.core.IRubyScript) {
+					org.rubypeople.rdt.core.IRubyScript cu = (org.rubypeople.rdt.core.IRubyScript)openable;
+
+					// contains a potential subtype as a local or anonymous type?
+					boolean containsLocalType = false;
+					if (localTypes == null) { // case of hierarchy on region
+						containsLocalType = true;
+					} else {
+						IPath path = cu.getPath();
+						containsLocalType = localTypes.contains(path.toString());
+					}
+					
+					// Grab the types from the script and then connect them up!
+					IType[] types = cu.getAllTypes();
+					for (int j = 0; j < types.length; j++) {
+						try {
+							reportHierarchy(types[i]);
+						} catch (RubyModelException e) {
+							// ignore
+						}
+					}
+				}
+			}			
+		} catch (ClassCastException e){ // work-around for 1GF5W1S - can happen in case duplicates are fed to the hierarchy with binaries hiding sources
+		} catch (RubyModelException e){ 
+		} finally {
+			reset();
+		}		
+	}
+
+	private void reportHierarchy(IType type) throws RubyModelException {
+		IType superclass;
+		if (type.isModule()){ // do not connect interfaces to Object
+			superclass = null;
+		} else {
+			superclass = findSuperClass(type);
+		}
+		IType[] superinterfaces = findSuperInterfaces(type);
+		
+		this.builder.connect(type, superclass, superinterfaces);
+	}
+
+	private IType[] findSuperInterfaces(IType type) throws RubyModelException {
+		String[] names = type.getIncludedModuleNames();
+		List<IType> types = new ArrayList<IType>();
+		for (int i = 0; i < names.length; i++) {
+			types.add(getLogicalType(type, names[i]));
+		}
+		return (IType[]) types.toArray(new IType[types.size()]);
+	}
+
+	private IType findSuperClass(IType type) throws RubyModelException {
+		String name = type.getSuperclassName();
+		return getLogicalType(type, name);
+	}
+
+	private IType getLogicalType(IType type, String name) {
+		RubyElementRequestor requestor = new RubyElementRequestor(type.getRubyScript());
+		return new LogicalType(requestor.findType(name));
+	}
+
+	private void reset() {
+//		this.focusType = null;
+		this.superTypesOnly = false;		
+	}
+
+	public void resolve(IType type) {
+		org.rubypeople.rdt.core.IRubyScript cu = type.getRubyScript();
+		HashSet localTypes = new HashSet();
+		localTypes.add(cu.getPath().toString());
+		this.superTypesOnly = true;
+		resolve(new Openable[] {(Openable)cu}, localTypes, null);		
+	}
+
+}

Added: trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/hierarchy/IndexBasedHierarchyBuilder.java
===================================================================
--- trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/hierarchy/IndexBasedHierarchyBuilder.java	                        (rev 0)
+++ trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/hierarchy/IndexBasedHierarchyBuilder.java	2007-07-11 20:32:07 UTC (rev 2749)
@@ -0,0 +1,430 @@
+package org.rubypeople.rdt.internal.core.hierarchy;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.Map;
+
+import org.eclipse.core.runtime.CoreException;
+import org.eclipse.core.runtime.IProgressMonitor;
+import org.eclipse.core.runtime.SubProgressMonitor;
+import org.rubypeople.rdt.core.IRubyProject;
+import org.rubypeople.rdt.core.IType;
+import org.rubypeople.rdt.core.RubyModelException;
+import org.rubypeople.rdt.core.search.IRubySearchConstants;
+import org.rubypeople.rdt.core.search.IRubySearchScope;
+import org.rubypeople.rdt.core.search.SearchParticipant;
+import org.rubypeople.rdt.core.search.SearchPattern;
+import org.rubypeople.rdt.internal.compiler.util.HashtableOfObject;
+import org.rubypeople.rdt.internal.core.IPathRequestor;
+import org.rubypeople.rdt.internal.core.Member;
+import org.rubypeople.rdt.internal.core.Openable;
+import org.rubypeople.rdt.internal.core.RubyModelManager;
+import org.rubypeople.rdt.internal.core.RubyProject;
+import org.rubypeople.rdt.internal.core.SourceFolder;
+import org.rubypeople.rdt.internal.core.search.HandleFactory;
+import org.rubypeople.rdt.internal.core.search.IndexQueryRequestor;
+import org.rubypeople.rdt.internal.core.search.RubySearchParticipant;
+import org.rubypeople.rdt.internal.core.search.SubTypeSearchJob;
+import org.rubypeople.rdt.internal.core.search.indexing.IIndexConstants;
+import org.rubypeople.rdt.internal.core.search.indexing.IndexManager;
+import org.rubypeople.rdt.internal.core.search.matching.MatchLocator;
+import org.rubypeople.rdt.internal.core.search.matching.SuperTypeReferencePattern;
+import org.rubypeople.rdt.internal.core.util.CharOperation;
+
+public class IndexBasedHierarchyBuilder extends HierarchyBuilder {
+	public static final int MAXTICKS = 800; // heuristic so that there still progress for deep hierachies
+	
+	private IRubySearchScope scope;
+	private HashMap binariesFromIndexMatches;
+
+	public IndexBasedHierarchyBuilder(TypeHierarchy hierarchy, IRubySearchScope scope) throws RubyModelException {
+		super(hierarchy);
+		this.binariesFromIndexMatches = new HashMap(10);
+		this.scope = scope;
+	}
+
+	@Override
+	public void build(boolean computeSubtypes) throws RubyModelException,
+			CoreException {
+				
+			if (computeSubtypes) {
+				// Note by construction there always is a focus type here
+				IType focusType = getType();
+				boolean focusIsObject = focusType.getElementName().equals(new String(IIndexConstants.OBJECT));
+				int amountOfWorkForSubtypes = focusIsObject ? 5 : 80; // percentage of work needed to get possible subtypes
+				IProgressMonitor possibleSubtypesMonitor = 
+					this.hierarchy.progressMonitor == null ? 
+						null : 
+						new SubProgressMonitor(this.hierarchy.progressMonitor, amountOfWorkForSubtypes);
+				HashSet localTypes = new HashSet(10); // contains the paths that have potential subtypes that are local/anonymous types
+				String[] allPossibleSubtypes;
+				if (((Member)focusType).getOuterMostLocalContext() == null) {
+					// top level or member type
+					allPossibleSubtypes = this.determinePossibleSubTypes(localTypes, possibleSubtypesMonitor);
+				} else {
+					// local or anonymous type
+					allPossibleSubtypes = new String[0];
+				}
+				if (allPossibleSubtypes != null) {
+					IProgressMonitor buildMonitor = 
+						this.hierarchy.progressMonitor == null ? 
+							null : 
+							new SubProgressMonitor(this.hierarchy.progressMonitor, 100 - amountOfWorkForSubtypes);
+					this.hierarchy.initialize(allPossibleSubtypes.length);
+					buildFromPotentialSubtypes(allPossibleSubtypes, localTypes, buildMonitor);
+				}
+			} else {
+				this.hierarchy.initialize(1);
+				this.buildSupertypes();
+			}
+	}
+	
+	/**
+	 * Configure this type hierarchy based on the given potential subtypes.
+	 */
+	private void buildFromPotentialSubtypes(String[] allPotentialSubTypes, HashSet localTypes, IProgressMonitor monitor) {
+		IType focusType = this.getType();
+			
+		// substitute compilation units with working copies
+		HashMap wcPaths = new HashMap(); // a map from path to working copies
+		int wcLength;
+		org.rubypeople.rdt.core.IRubyScript[] workingCopies = this.hierarchy.workingCopies;
+		if (workingCopies != null && (wcLength = workingCopies.length) > 0) {
+			String[] newPaths = new String[wcLength];
+			for (int i = 0; i < wcLength; i++) {
+				org.rubypeople.rdt.core.IRubyScript workingCopy = workingCopies[i];
+				String path = workingCopy.getPath().toString();
+				wcPaths.put(path, workingCopy);
+				newPaths[i] = path;
+			}
+			int potentialSubtypesLength = allPotentialSubTypes.length;
+			System.arraycopy(allPotentialSubTypes, 0, allPotentialSubTypes = new String[potentialSubtypesLength+wcLength], 0, potentialSubtypesLength);
+			System.arraycopy(newPaths, 0, allPotentialSubTypes, potentialSubtypesLength, wcLength);
+		}
+				
+		int length = allPotentialSubTypes.length;
+
+		// inject the compilation unit of the focus type (so that types in
+		// this cu have special visibility permission (this is also usefull
+		// when the cu is a working copy)
+		Openable focusCU = (Openable)focusType.getRubyScript();
+		String focusPath = null;
+		if (focusCU != null) {
+			focusPath = focusCU.getPath().toString();
+			if (length > 0) {
+				System.arraycopy(allPotentialSubTypes, 0, allPotentialSubTypes = new String[length+1], 0, length);
+				allPotentialSubTypes[length] = focusPath;	
+			} else {
+				allPotentialSubTypes = new String[] {focusPath};
+			}
+			length++;
+		}
+		
+		// sort by projects
+		/*
+		 * NOTE: To workaround pb with hierarchy resolver that requests top  
+		 * level types in the process of caching an enclosing type, this needs to
+		 * be sorted in reverse alphabetical order so that top level types are cached
+		 * before their inner types.
+		 */
+		org.rubypeople.rdt.internal.core.util.Util.sortReverseOrder(allPotentialSubTypes);
+		
+		ArrayList potentialSubtypes = new ArrayList();
+
+		try {
+			// create element infos for subtypes
+			HandleFactory factory = new HandleFactory();
+			IRubyProject currentProject = null;
+			if (monitor != null) monitor.beginTask("", length*2 /* 1 for build binding, 1 for connect hierarchy*/); //$NON-NLS-1$
+			for (int i = 0; i < length; i++) {
+				try {
+					String resourcePath = allPotentialSubTypes[i];
+					
+					// skip duplicate paths (e.g. if focus path was injected when it was already a potential subtype)
+					if (i > 0 && resourcePath.equals(allPotentialSubTypes[i-1])) continue;
+					
+					Openable handle;
+					org.rubypeople.rdt.core.IRubyScript workingCopy = (org.rubypeople.rdt.core.IRubyScript)wcPaths.get(resourcePath);
+					if (workingCopy != null) {
+						handle = (Openable)workingCopy;
+					} else {
+						handle = 
+							resourcePath.equals(focusPath) ? 
+								focusCU :
+								factory.createOpenable(resourcePath);
+						if (handle == null) continue; // match is outside loadpath
+					}
+					
+					IRubyProject project = handle.getRubyProject();
+					if (currentProject == null) {
+						currentProject = project;
+						potentialSubtypes = new ArrayList(5);
+					} else if (!currentProject.equals(project)) {
+						// build current project
+						this.buildForProject((RubyProject)currentProject, potentialSubtypes, workingCopies, localTypes, monitor);
+						currentProject = project;
+						potentialSubtypes = new ArrayList(5);
+					}
+					
+					potentialSubtypes.add(handle);
+				} catch (RubyModelException e) {
+					continue;
+				}
+			}
+			
+			// build last project
+			try {
+				if (currentProject == null) {
+					// case of no potential subtypes
+					currentProject = focusType.getRubyProject();
+					potentialSubtypes.add(focusType.getRubyScript());
+				}
+				this.buildForProject((RubyProject)currentProject, potentialSubtypes, workingCopies, localTypes, monitor);
+			} catch (RubyModelException e) {
+				// ignore
+			}
+			
+			// Compute hierarchy of focus type if not already done (case of a type with potential subtypes that are not real subtypes)
+			if (!this.hierarchy.contains(focusType)) {
+				try {
+					currentProject = focusType.getRubyProject();
+					potentialSubtypes = new ArrayList();
+					potentialSubtypes.add(focusType.getRubyScript());
+					
+					this.buildForProject((RubyProject)currentProject, potentialSubtypes, workingCopies, localTypes, monitor);
+				} catch (RubyModelException e) {
+					// ignore
+				}
+			}
+			
+			// Add focus if not already in (case of a type with no explicit super type)
+			if (!this.hierarchy.contains(focusType)) {
+				this.hierarchy.addRootClass(focusType);
+			}
+		} finally {
+			if (monitor != null) monitor.done();
+		}
+	}
+	
+	private void buildForProject(RubyProject project, ArrayList potentialSubtypes, org.rubypeople.rdt.core.IRubyScript[] workingCopies, HashSet localTypes, IProgressMonitor monitor) throws RubyModelException {
+		// copy vectors into arrays
+		int openablesLength = potentialSubtypes.size();
+		Openable[] openables = new Openable[openablesLength];
+		potentialSubtypes.toArray(openables);
+
+		// resolve
+		if (openablesLength > 0) {
+			IType focusType = this.getType();
+			boolean inProjectOfFocusType = focusType != null && focusType.getRubyProject().equals(project);
+			org.rubypeople.rdt.core.IRubyScript[] unitsToLookInside = null;
+			if (inProjectOfFocusType) {
+				org.rubypeople.rdt.core.IRubyScript unitToLookInside = focusType.getRubyScript();
+				if (unitToLookInside != null) {
+					int wcLength = workingCopies == null ? 0 : workingCopies.length;
+					if (wcLength == 0) {
+						unitsToLookInside = new org.rubypeople.rdt.core.IRubyScript[] {unitToLookInside};
+					} else {
+						unitsToLookInside = new org.rubypeople.rdt.core.IRubyScript[wcLength+1];
+						unitsToLookInside[0] = unitToLookInside;
+						System.arraycopy(workingCopies, 0, unitsToLookInside, 1, wcLength);
+					}
+				} else {
+					unitsToLookInside = workingCopies;
+				}
+			}
+
+//			SearchableEnvironment searchableEnvironment = project.newSearchableNameEnvironment(unitsToLookInside);
+//			this.nameLookup = searchableEnvironment.nameLookup;
+//			Map options = project.getOptions(true);
+//			// disable task tags to speed up parsing
+//			options.put(RubyCore.COMPILER_TASK_TAGS, ""); //$NON-NLS-1$
+//			this.hierarchyResolver = 
+//				new HierarchyResolver(searchableEnvironment, options, this, new DefaultProblemFactory());
+			if (focusType != null) {
+				Member declaringMember = ((Member)focusType).getOuterMostLocalContext();
+				if (declaringMember == null) {
+					// top level or member type
+					if (!inProjectOfFocusType) {
+						char[] typeQualifiedName = focusType.getTypeQualifiedName("::").toCharArray();
+						String[] packageName = ((SourceFolder) focusType.getSourceFolder()).names;
+//						if (searchableEnvironment.findType(typeQualifiedName, Util.toCharArrays(packageName)) == null) {
+//							// focus type is not visible in this project: no need to go further
+//							return;
+//						}
+					}
+				} else {
+					// local or anonymous type
+					Openable openable;
+					openable = (Openable)declaringMember.getRubyScript();
+					
+					localTypes = new HashSet();
+					localTypes.add(openable.getPath().toString());
+					this.hierarchyResolver.resolve(new Openable[] {openable}, localTypes, monitor);
+					return;
+				}
+			}
+			this.hierarchyResolver.resolve(openables, localTypes, monitor);
+		}
+	}
+
+	/**
+	 * Returns all of the possible subtypes of this type hierarchy.
+	 * Returns null if they could not be determine.
+	 */
+	private String[] determinePossibleSubTypes(final HashSet localTypes, IProgressMonitor monitor) {
+
+		class PathCollector implements IPathRequestor {
+			HashSet paths = new HashSet(10);
+			public void acceptPath(String path, boolean containsLocalTypes) {
+				this.paths.add(path);
+				if (containsLocalTypes) {
+					localTypes.add(path);
+				}
+			}
+		}
+		PathCollector collector = new PathCollector();
+		
+		try {
+			if (monitor != null) monitor.beginTask("", MAXTICKS); //$NON-NLS-1$
+			searchAllPossibleSubTypes(
+				this.getType(),
+				this.scope,
+				this.binariesFromIndexMatches,
+				collector,
+				IRubySearchConstants.WAIT_UNTIL_READY_TO_SEARCH,
+				monitor);
+		} finally {
+			if (monitor != null) monitor.done();
+		}
+
+		HashSet paths = collector.paths;
+		int length = paths.size();
+		String[] result = new String[length];
+		int count = 0;
+		for (Iterator iter = paths.iterator(); iter.hasNext();) {
+			result[count++] = (String) iter.next();
+		} 
+		return result;
+	}
+	
+	/**
+	 * Collection used to queue subtype index queries
+	 */
+	static class Queue {
+		public char[][] names = new char[10][];
+		public int start = 0;
+		public int end = -1;
+		public void add(char[] name){
+			if (++this.end == this.names.length){
+				this.end -= this.start;
+				System.arraycopy(this.names, this.start, this.names = new char[this.end*2][], 0, this.end);
+				this.start = 0;
+			}
+			this.names[this.end] = name;
+		}
+		public char[] retrieve(){
+			if (this.start > this.end) return null; // none
+			
+			char[] name = this.names[this.start++];
+			if (this.start > this.end){
+				this.start = 0;
+				this.end = -1;
+			}
+			return name;
+		}
+		public String toString(){
+			StringBuffer buffer = new StringBuffer("Queue:\n"); //$NON-NLS-1$
+			for (int i = this.start; i <= this.end; i++){
+				buffer.append(this.names[i]).append('\n');		
+			}
+			return buffer.toString();
+		}
+	}
+	
+	/**
+	 * Find the set of candidate subtypes of a given type.
+	 *
+	 * The requestor is notified of super type references (with actual path of
+	 * its occurrence) for all types which are potentially involved inside a particular
+	 * hierarchy.
+	 * The match locator is not used here to narrow down the results, the type hierarchy
+	 * resolver is rather used to compute the whole hierarchy at once.
+	 * @param type
+	 * @param scope
+	 * @param binariesFromIndexMatches
+	 * @param pathRequestor
+	 * @param waitingPolicy
+	 * @param progressMonitor
+	 */
+	public static void searchAllPossibleSubTypes(
+		IType type,
+		IRubySearchScope scope,
+		final Map binariesFromIndexMatches,
+		final IPathRequestor pathRequestor,
+		int waitingPolicy,	// WaitUntilReadyToSearch | ForceImmediateSearch | CancelIfNotReadyToSearch
+		IProgressMonitor progressMonitor) {
+
+		/* embed constructs inside arrays so as to pass them to (inner) collector */
+		final Queue queue = new Queue();
+		final HashtableOfObject foundSuperNames = new HashtableOfObject(5);
+
+		IndexManager indexManager = RubyModelManager.getRubyModelManager().getIndexManager();
+
+		/* use a special collector to collect paths and queue new subtype names */
+		IndexQueryRequestor searchRequestor = new IndexQueryRequestor() {
+			public boolean acceptIndexMatch(String documentPath, SearchPattern indexRecord, SearchParticipant participant) {
+				SuperTypeReferencePattern record = (SuperTypeReferencePattern)indexRecord;
+				boolean isLocalOrAnonymous = record.enclosingTypeName == IIndexConstants.ONE_ZERO;
+				pathRequestor.acceptPath(documentPath, isLocalOrAnonymous);
+				char[] typeName = record.simpleName;
+				if (!isLocalOrAnonymous // local or anonymous types cannot have subtypes outside the cu that define them
+						&& !foundSuperNames.containsKey(typeName)){
+					foundSuperNames.put(typeName, typeName);
+					queue.add(typeName);
+				}
+				return true;
+			}		
+		};
+
+		int superRefKind;
+//		try {
+			superRefKind = type.isClass() ? SuperTypeReferencePattern.ONLY_SUPER_CLASSES : SuperTypeReferencePattern.ALL_SUPER_TYPES;
+//		} catch (RubyModelException e) {
+//			superRefKind = SuperTypeReferencePattern.ALL_SUPER_TYPES;
+//		}
+		SuperTypeReferencePattern pattern =
+			new SuperTypeReferencePattern(null, null, superRefKind, SearchPattern.R_EXACT_MATCH | SearchPattern.R_CASE_SENSITIVE);
+		MatchLocator.setFocus(pattern, type);
+		SubTypeSearchJob job = new SubTypeSearchJob(
+			pattern, 
+			new RubySearchParticipant(), // ruby search only
+			scope, 
+			searchRequestor);
+
+		int ticks = 0;
+		queue.add(type.getElementName().toCharArray());
+		try {
+			while (queue.start <= queue.end) {
+				if (progressMonitor != null && progressMonitor.isCanceled()) return;
+
+				// all subclasses of OBJECT are actually all types
+				char[] currentTypeName = queue.retrieve();
+				if (CharOperation.equals(currentTypeName, IIndexConstants.OBJECT))
+					currentTypeName = null;
+
+				// search all index references to a given supertype
+				pattern.superSimpleName = currentTypeName;
+				indexManager.performConcurrentJob(job, waitingPolicy, null); // no sub progress monitor since its too costly for deep hierarchies
+				if (progressMonitor != null && ++ticks <= MAXTICKS)
+					progressMonitor.worked(1);
+
+				// in case, we search all subtypes, no need to search further
+				if (currentTypeName == null) break;
+			}
+		} finally {
+			job.finished();
+		}
+	}
+}

Added: trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/hierarchy/TypeHierarchy.java
===================================================================
--- trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/hierarchy/TypeHierarchy.java	                        (rev 0)
+++ trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/core/hierarchy/TypeHierarchy.java	2007-07-11 20:32:07 UTC (rev 2749)
@@ -0,0 +1,1522 @@
+/*******************************************************************************
+ * Copyright (c) 2000, 2006 IBM Corporation and others.
+ * All rights reserved. Thi...
 
[truncated message content]