Call Hierarchy: Avoid generating AST

10 files changed, 629 insertions, 94 deletions

diff --git a/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CElementSet.java b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CElementSet.java
new file mode 100644
index 00000000000..da6c4d262cd
--- /dev/null
+++ b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CElementSet.java
@@ -0,0 +1,86 @@
+/*******************************************************************************
+ * Copyright (c) 2006 Wind River Systems, Inc. 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:
+ *    Markus Schorn - initial API and implementation
+ *******************************************************************************/ 
+
+package org.eclipse.cdt.internal.ui.callhierarchy;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.Set;
+
+import org.eclipse.cdt.core.model.ICElement;
+
+import org.eclipse.cdt.internal.ui.viewsupport.WorkingSetFilterUI;
+
+public class CElementSet {
+	private Set fSet= new HashSet();
+	private int fHashCode;
+	
+	CElementSet( ICElement[] elements) {
+		fSet.addAll(Arrays.asList(elements));
+		fHashCode= 0;
+        for (int i = 0; i < elements.length; i++) {
+        	fHashCode = 31*fHashCode + elements[i].hashCode();
+        }
+	}
+
+	public int hashCode() {
+		return fHashCode;
+	}
+
+	public boolean equals(Object obj) {
+		if (this == obj) {
+			return true;
+		}
+		if (obj == null) {
+			return false;
+		}
+		if (getClass() != obj.getClass()) {
+			return false;
+		}
+		final CElementSet other = (CElementSet) obj;
+		if (fHashCode != other.fHashCode) {
+			return false;
+		}
+		if (fSet == null) {
+			if (other.fSet != null) {
+				return false;
+			}
+		} 
+		else {
+			if (fSet.size() != other.fSet.size()) {
+				return false;
+			}
+			for (Iterator iter = fSet.iterator(); iter.hasNext(); ) {
+				if (!other.fSet.contains(iter.next())) { 
+					return false;
+				}
+			}
+		}
+		return true;
+	}
+
+	public boolean isEmpty() {
+		return fSet.isEmpty();
+	}
+
+	public ICElement[] getElements(WorkingSetFilterUI filter) {
+		ArrayList result= new ArrayList(fSet.size());
+		for (Iterator iter = fSet.iterator(); iter.hasNext(); ) {
+			ICElement element = (ICElement) iter.next();
+			if (filter == null || filter.isPartOfWorkingSet(element)) {
+				result.add(element);
+			}
+		}
+		return (ICElement[]) result.toArray(new ICElement[result.size()]);
+	}
+}
\ No newline at end of file
diff --git a/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CHContentProvider.java b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CHContentProvider.java
index 1b3e926ea8e..d50814fff90 100644
--- a/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CHContentProvider.java
+++ b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CHContentProvider.java
@@ -12,31 +12,26 @@
 package org.eclipse.cdt.internal.ui.callhierarchy;
 
 import java.util.ArrayList;
-import java.util.Arrays;
 
 import org.eclipse.core.runtime.CoreException;
 import org.eclipse.core.runtime.IProgressMonitor;
 import org.eclipse.core.runtime.NullProgressMonitor;
-import org.eclipse.jface.text.Region;
 import org.eclipse.swt.widgets.Display;
 
+import org.eclipse.cdt.core.CCorePlugin;
+import org.eclipse.cdt.core.dom.ast.DOMException;
 import org.eclipse.cdt.core.dom.ast.IEnumerator;
+import org.eclipse.cdt.core.index.IIndex;
+import org.eclipse.cdt.core.index.IIndexName;
 import org.eclipse.cdt.core.model.CoreModel;
 import org.eclipse.cdt.core.model.ICElement;
 import org.eclipse.cdt.core.model.ICProject;
-import org.eclipse.cdt.core.model.ISourceRange;
-import org.eclipse.cdt.core.model.ISourceReference;
 import org.eclipse.cdt.core.model.ITranslationUnit;
 import org.eclipse.cdt.core.model.IVariable;
 import org.eclipse.cdt.ui.CUIPlugin;
 
 import org.eclipse.cdt.internal.corext.util.CModelUtil;
 
-import org.eclipse.cdt.internal.ui.missingapi.CElementSet;
-import org.eclipse.cdt.internal.ui.missingapi.CIndexQueries;
-import org.eclipse.cdt.internal.ui.missingapi.CIndexReference;
-import org.eclipse.cdt.internal.ui.missingapi.CalledByResult;
-import org.eclipse.cdt.internal.ui.missingapi.CallsToResult;
 import org.eclipse.cdt.internal.ui.viewsupport.AsyncTreeContentProvider;
 import org.eclipse.cdt.internal.ui.viewsupport.WorkingSetFilterUI;
 
@@ -96,64 +91,115 @@ public class CHContentProvider extends AsyncTreeContentProvider {
 			IProgressMonitor monitor) {
 		if (parentElement instanceof CHNode) {
 			CHNode node = (CHNode) parentElement;
-			ICElement elem= node.getRepresentedDeclaration();
-			if (elem != null) {
+			try {
 				if (fComputeReferencedBy) {
-					return asyncronouslyComputeReferencedBy(node, elem);
+					return asyncronouslyComputeReferencedBy(node);
 				}
 				else {
-					return asyncronouslyComputeRefersTo(node, elem);
+					return asyncronouslyComputeRefersTo(node);
 				}
+			} catch (CoreException e) {
+				CUIPlugin.getDefault().log(e);
+			} catch (DOMException e) {
+				CUIPlugin.getDefault().log(e);
+			} catch (InterruptedException e) {
 			}
 		}
 		return NO_CHILDREN;
 	}
 	
-	private Object[] asyncronouslyComputeReferencedBy(CHNode parent, ICElement elem) {
+	private Object[] asyncronouslyComputeReferencedBy(CHNode parent) throws CoreException, InterruptedException, DOMException {
+		ICProject[] scope= CoreModel.getDefault().getCModel().getCProjects();
+		IIndex index= CCorePlugin.getIndexManager().getIndex(scope);
+		index.acquireReadLock();
 		try {
-			ICProject[] scope= CoreModel.getDefault().getCModel().getCProjects();
-			CalledByResult calledBy= CIndexQueries.getInstance().findCalledBy(scope, elem, NPM);
-			ArrayList result= new ArrayList();
-			
-			ICElement[] elements= calledBy.getElements();
-			for (int i = 0; i < elements.length; i++) {
-				ICElement element = elements[i];
-				if (element != null) {
-					if (fFilter == null || fFilter.isPartOfWorkingSet(element)) {
-						CIndexReference[] refs= calledBy.getReferences(element);
-						if (refs != null && refs.length > 0) {
-							CHNode node = createRefbyNode(parent, element, refs);
-							result.add(node);
-						}
+			return CHQueries.findCalledBy(this, parent, index, NPM);
+		}
+		finally {
+			index.releaseReadLock();
+		}
+	}
+
+	private Object[] asyncronouslyComputeRefersTo(CHNode parent) throws CoreException, InterruptedException, DOMException {
+		ICProject[] scope= CoreModel.getDefault().getCModel().getCProjects();
+		IIndex index= CCorePlugin.getIndexManager().getIndex(scope);
+		index.acquireReadLock();
+		try {
+			return CHQueries.findCalls(this, parent, index, NPM);
+		}
+		finally {
+			index.releaseReadLock();
+		}
+	}
+
+	public void setComputeReferencedBy(boolean value) {
+		fComputeReferencedBy = value;
+	}
+
+	public boolean getComputeReferencedBy() {
+		return fComputeReferencedBy;
+	}
+
+	public void setWorkingSetFilter(WorkingSetFilterUI filterUI) {
+		fFilter= filterUI;
+		recompute();
+	}
+
+	CHNode[] createNodes(CHNode node, CalledByResult result) throws CoreException {
+		ArrayList nodes= new ArrayList();
+		ICElement[] elements= result.getElements();
+		for (int i = 0; i < elements.length; i++) {
+			ICElement element = elements[i];
+			if (element != null) {
+				if (fFilter == null || fFilter.isPartOfWorkingSet(element)) {
+					IIndexName[] refs= result.getReferences(element);
+					if (refs != null && refs.length > 0) {
+						CHNode newNode = createRefbyNode(node, element, refs);
+						nodes.add(newNode);
 					}
 				}
 			}
-			return result.toArray();
-		} catch (CoreException e) {
-			CUIPlugin.getDefault().log(e);
 		}
-		return NO_CHILDREN;
+		return (CHNode[]) nodes.toArray(new CHNode[nodes.size()]);
 	}
-
-	private CHNode createRefbyNode(CHNode parent, ICElement element, CIndexReference[] refs) {
+	
+	private CHNode createRefbyNode(CHNode parent, ICElement element, IIndexName[] refs) throws CoreException {
 		ITranslationUnit tu= CModelUtil.getTranslationUnit(element);
-		CHNode node= new CHNode(parent, tu, refs[0].getTimestamp(), element);
+		CHNode node= new CHNode(parent, tu, refs[0].getFile().getTimestamp(), element);
 		if (element instanceof IVariable || element instanceof IEnumerator) {
 			node.setInitializer(true);
 		}
-		Arrays.sort(refs, CIndexReference.COMPARE_OFFSET);
 		for (int i = 0; i < refs.length; i++) {
-			CIndexReference reference = refs[i];
-			node.addReference(new CHReferenceInfo(reference.getOffset(), reference.getLength()));
+			IIndexName reference = refs[i];
+			node.addReference(new CHReferenceInfo(reference.getNodeOffset(), reference.getNodeLength()));
 		}
+		node.sortReferencesByOffset();
 		return node;
 	}
 
-	private CHNode createReftoNode(CHNode parent, ITranslationUnit tu, ICElement[] elements, CIndexReference[] references) {
+	CHNode[] createNodes(CHNode node, CallsToResult callsTo) throws CoreException {
+		ITranslationUnit tu= CModelUtil.getTranslationUnit(node.getRepresentedDeclaration());
+		ArrayList result= new ArrayList();
+		CElementSet[] elementSets= callsTo.getElementSets();
+		for (int i = 0; i < elementSets.length; i++) {
+			CElementSet set = elementSets[i];
+			if (!set.isEmpty()) {
+				IIndexName[] refs= callsTo.getReferences(set);
+				ICElement[] elements= set.getElements(fFilter);
+				if (elements.length > 0) {
+					CHNode childNode = createReftoNode(node, tu, elements, refs);
+					result.add(childNode);
+				}
+			}
+		}
+		return (CHNode[]) result.toArray(new CHNode[result.size()]);
+	}
+
+	private CHNode createReftoNode(CHNode parent, ITranslationUnit tu, ICElement[] elements, IIndexName[] references) throws CoreException {
 		assert elements.length > 0;
 
 		CHNode node;
-		long timestamp= references[0].getTimestamp();
+		long timestamp= references[0].getFile().getTimestamp();
 		
 		if (elements.length == 1) {
 			node= new CHNode(parent, tu, timestamp, elements[0]);
@@ -162,53 +208,11 @@ public class CHContentProvider extends AsyncTreeContentProvider {
 			node= new CHMultiDefNode(parent, tu, timestamp, elements);
 		}
 		
-		Arrays.sort(references, CIndexReference.COMPARE_OFFSET);		
 		for (int i = 0; i < references.length; i++) {
-			CIndexReference reference = references[i];
-			node.addReference(new CHReferenceInfo(reference.getOffset(), reference.getLength()));
+			IIndexName reference = references[i];
+			node.addReference(new CHReferenceInfo(reference.getNodeOffset(), reference.getNodeLength()));
 		}
+		node.sortReferencesByOffset();
 		return node;
 	}
-
-	private Object[] asyncronouslyComputeRefersTo(CHNode parent, ICElement elem) {
-		try {
-			if (elem instanceof ISourceReference) {
-				ISourceReference sf= (ISourceReference) elem;
-				ITranslationUnit tu= sf.getTranslationUnit();
-				ISourceRange range= sf.getSourceRange();
-				ICProject[] scope= CoreModel.getDefault().getCModel().getCProjects();
-				CallsToResult callsTo= CIndexQueries.getInstance().findCallsInRange(scope, tu, new Region(range.getStartPos(), range.getLength()), NPM);
-				ArrayList result= new ArrayList();
-				CElementSet[] elementSets= callsTo.getElementSets();
-				for (int i = 0; i < elementSets.length; i++) {
-					CElementSet set = elementSets[i];
-					if (!set.isEmpty()) {
-						CIndexReference[] refs= callsTo.getReferences(set);
-						ICElement[] elements= set.getElements(fFilter);
-						if (elements.length > 0) {
-							CHNode node = createReftoNode(parent, tu, elements, refs);
-							result.add(node);
-						}
-					}
-				}
-				return result.toArray();
-			}
-		} catch (CoreException e) {
-			CUIPlugin.getDefault().log(e);
-		}
-		return NO_CHILDREN;
-	}
-
-	public void setComputeReferencedBy(boolean value) {
-		fComputeReferencedBy = value;
-	}
-
-	public boolean getComputeReferencedBy() {
-		return fComputeReferencedBy;
-	}
-
-	public void setWorkingSetFilter(WorkingSetFilterUI filterUI) {
-		fFilter= filterUI;
-		recompute();
-	}
 }
diff --git a/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CHDropTargetListener.java b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CHDropTargetListener.java
index b67879d5324..b31c14be871 100644
--- a/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CHDropTargetListener.java
+++ b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CHDropTargetListener.java
@@ -24,7 +24,6 @@ import org.eclipse.swt.widgets.Display;
 
 import org.eclipse.cdt.core.model.ICElement;
 
-import org.eclipse.cdt.internal.ui.missingapi.CIndexQueries;
 
 public class CHDropTargetListener implements DropTargetListener {
     
@@ -46,7 +45,7 @@ public class CHDropTargetListener implements DropTargetListener {
         if (event.detail != DND.DROP_NONE) {
 			if (LocalSelectionTransfer.getTransfer().isSupportedType(event.currentDataType)) {
 				fInput= checkLocalSelection();
-				if (!CIndexQueries.isRelevantForCallHierarchy(fInput)) {
+				if (!CallHierarchyUI.isRelevantForCallHierarchy(fInput)) {
 					event.detail= DND.DROP_NONE;
 					fInput= null;
 				}
diff --git a/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CHNode.java b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CHNode.java
index 7ffe1385112..8dec0a69bc0 100644
--- a/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CHNode.java
+++ b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CHNode.java
@@ -167,4 +167,10 @@ public class CHNode implements IAdaptable {
 	public void setInitializer(boolean isInitializer) {
 		fIsInitializer = isInitializer;
 	}
+
+	public void sortReferencesByOffset() {
+		if (fReferences.size() > 1) {
+			Collections.sort(fReferences, CHReferenceInfo.COMPARE_OFFSET);
+		}
+	}
 }
diff --git a/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CHQueries.java b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CHQueries.java
new file mode 100644
index 00000000000..74a84e379a4
--- /dev/null
+++ b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CHQueries.java
@@ -0,0 +1,230 @@
+/*******************************************************************************
+ * Copyright (c) 2006 Wind River Systems, Inc. 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:
+ *    Markus Schorn - initial API and implementation
+ *******************************************************************************/ 
+
+package org.eclipse.cdt.internal.ui.callhierarchy;
+
+import java.util.ArrayList;
+
+import org.eclipse.core.resources.IFile;
+import org.eclipse.core.runtime.CoreException;
+import org.eclipse.core.runtime.IPath;
+import org.eclipse.core.runtime.IProgressMonitor;
+import org.eclipse.core.runtime.Path;
+import org.eclipse.jface.text.IRegion;
+import org.eclipse.jface.text.Region;
+
+import org.eclipse.cdt.core.CCorePlugin;
+import org.eclipse.cdt.core.IPositionConverter;
+import org.eclipse.cdt.core.dom.IName;
+import org.eclipse.cdt.core.dom.ast.DOMException;
+import org.eclipse.cdt.core.dom.ast.IASTFileLocation;
+import org.eclipse.cdt.core.dom.ast.IASTName;
+import org.eclipse.cdt.core.dom.ast.IBinding;
+import org.eclipse.cdt.core.index.IIndex;
+import org.eclipse.cdt.core.index.IIndexBinding;
+import org.eclipse.cdt.core.index.IIndexFile;
+import org.eclipse.cdt.core.index.IIndexName;
+import org.eclipse.cdt.core.model.CModelException;
+import org.eclipse.cdt.core.model.ICElement;
+import org.eclipse.cdt.core.model.ICProject;
+import org.eclipse.cdt.core.model.ISourceRange;
+import org.eclipse.cdt.core.model.ISourceReference;
+import org.eclipse.cdt.core.model.ITranslationUnit;
+import org.eclipse.cdt.ui.CUIPlugin;
+
+import org.eclipse.cdt.internal.core.model.ext.CElementHandleFactory;
+import org.eclipse.cdt.internal.corext.util.CModelUtil;
+
+
+/**
+ * Access to high level queries in the index.
+ * @since 4.0
+ */
+public class CHQueries {
+	private static final ICElement[] EMPTY_ELEMENTS = new ICElement[0];
+	private static final CHNode[] EMPTY_NODES= new CHNode[0];
+	
+    private CHQueries() {}
+    
+	/**
+	 * Searches for functions and methods that call a given element.
+	 * @throws DOMException 
+	 */
+	public static CHNode[] findCalledBy(CHContentProvider cp, CHNode node, 
+			IIndex index, IProgressMonitor pm) throws CoreException, DOMException {
+		CalledByResult result= new CalledByResult();
+		ICElement callee= node.getRepresentedDeclaration();
+		if (! (callee instanceof ISourceReference)) {
+			return EMPTY_NODES;
+		}
+		IBinding calleeBinding= elementToBinding(index, callee);
+		findCalledBy(index, calleeBinding, callee.getCProject(), result);	
+		
+		return cp.createNodes(node, result);
+	}
+
+	private static IIndexBinding elementToBinding(IIndex index, ICElement element) throws CoreException {
+		IIndexName name= elementToName(index, element);
+		if (name != null) {
+			return index.findBinding(name);
+		}
+		return null;
+	}
+
+	private static IIndexName elementToName(IIndex index, ICElement element) throws CoreException {
+		if (element instanceof ISourceReference) {
+			ISourceReference sf = ((ISourceReference)element);
+			ITranslationUnit tu= sf.getTranslationUnit();
+			if (tu != null) {
+				IPath location= tu.getLocation();
+				if (location != null) {
+					IIndexFile file= index.getFile(location);
+					if (file != null) {
+						String elementName= element.getElementName();
+						int idx= elementName.lastIndexOf(":")+1; //$NON-NLS-1$
+						ISourceRange pos= sf.getSourceRange();
+						IRegion region= new Region(pos.getIdStartPos()+idx, pos.getIdLength());
+						IPositionConverter converter= CCorePlugin.getPositionTrackerManager().findPositionConverter(tu, file.getTimestamp());
+						if (converter != null) {
+							region= converter.actualToHistoric(region);
+						}
+						IIndexName[] names= file.findNames(region.getOffset(), region.getLength());
+						for (int i = 0; i < names.length; i++) {
+							IIndexName name = names[i];
+							if (!name.isReference() && elementName.endsWith(new String(name.toCharArray()))) {
+								return name;
+							}
+						}
+					}
+				}
+			}
+		}
+		return null;
+	}
+
+	private static void findCalledBy(IIndex index, IBinding callee, ICProject project, CalledByResult result) throws CoreException, DOMException {
+		if (callee != null) {
+			IIndexName[] names= index.findReferences(callee);
+			for (int i = 0; i < names.length; i++) {
+				IIndexName rname = names[i];
+				IIndexName caller= rname.getEnclosingDefinition();
+				if (caller != null) {
+					ICElement elem= getCElementForName(project, index, caller);
+					if (elem != null) {
+						result.add(elem, rname);
+					} 
+				}
+			}
+		}
+	}
+
+	private static ITranslationUnit getTranslationUnit(ICProject cproject, IName name) {
+		IPath path= Path.fromOSString(name.getFileLocation().getFileName());
+		try {
+			return CModelUtil.findTranslationUnitForLocation(path, cproject);
+		} catch (CModelException e) {
+			CUIPlugin.getDefault().log(e);
+			return null;
+		}
+	}
+
+	/**
+	 * Searches for all calls that are made within a given range.
+	 * @throws DOMException 
+	 */
+	public static CHNode[] findCalls(CHContentProvider cp, CHNode node, IIndex index, IProgressMonitor pm) throws CoreException, DOMException {
+		ICElement caller= node.getRepresentedDeclaration();
+		CallsToResult result= new CallsToResult();
+		IIndexName callerName= elementToName(index, caller);
+		if (callerName != null) {
+			IIndexName[] refs= callerName.getEnclosedNames();
+			for (int i = 0; i < refs.length; i++) {
+				IIndexName name = refs[i];
+				IBinding binding= index.findBinding(name);
+				if (CallHierarchyUI.isRelevantForCallHierarchy(binding)) {
+					ICElement[] defs = findAllDefinitions(index, binding);
+					if (defs.length == 0) {
+						ICElement elem = findAnyDeclaration(index, null, binding);
+						if (elem != null) {
+							defs = new ICElement[] { elem };
+						}
+					}
+					if (defs != null && defs.length > 0) {
+						result.add(defs, name);
+					}
+				}
+			}
+		}
+		return cp.createNodes(node, result);
+	}
+	
+	public static ICElement[] findAllDefinitions(IIndex index, IBinding binding) throws CoreException, DOMException {
+		if (binding != null) {
+			IIndexName[] defs= index.findDefinitions(binding);
+
+			ArrayList result= new ArrayList();
+			for (int i = 0; i < defs.length; i++) {
+				IIndexName in = defs[i];
+				ICElement definition= getCElementForName(null, index, in);
+				if (definition != null) {
+					result.add(definition);
+				}
+				
+			}
+			return (ICElement[]) result.toArray(new ICElement[result.size()]);
+		}
+		return EMPTY_ELEMENTS;
+	}
+			
+	static ICElement getCElementForName(ICProject preferProject, IIndex index, IASTName declName) throws CoreException, DOMException {
+		assert !declName.isReference();
+		IBinding binding= declName.resolveBinding();
+		if (binding != null) {
+			ITranslationUnit tu= getTranslationUnit(preferProject, declName);
+			if (tu != null) {
+				IFile file= (IFile) tu.getResource();
+				long timestamp= file.getLocalTimeStamp();
+				IASTFileLocation loc= declName.getFileLocation();
+				IRegion region= new Region(loc.getNodeOffset(), loc.getNodeLength());
+				IPositionConverter converter= CCorePlugin.getPositionTrackerManager().findPositionConverter(file, timestamp);
+				if (converter != null) {
+					region= converter.actualToHistoric(region);
+				}
+				return CElementHandleFactory.create(tu, binding, region, timestamp);
+			}
+		}
+		return null;
+	}
+
+	static ICElement getCElementForName(ICProject preferProject, IIndex index, IIndexName declName) throws CoreException, DOMException {
+		assert !declName.isReference();
+		ITranslationUnit tu= getTranslationUnit(preferProject, declName);
+		if (tu != null) {
+			IRegion region= new Region(declName.getNodeOffset(), declName.getNodeLength());
+			long timestamp= declName.getFile().getTimestamp();
+			return CElementHandleFactory.create(tu, index.findBinding(declName), region, timestamp);
+		}
+		return null;
+	}
+
+	public static ICElement findAnyDeclaration(IIndex index, ICProject preferProject, IBinding binding) throws CoreException, DOMException {
+		if (binding != null) {
+			IIndexName[] names= index.findNames(binding, IIndex.FIND_DECLARATIONS);
+			for (int i = 0; i < names.length; i++) {
+				ICElement elem= getCElementForName(preferProject, index, names[i]);
+				if (elem != null) {
+					return elem;
+				}
+			}
+		}
+		return null;
+	}
+}
diff --git a/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CHReferenceInfo.java b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CHReferenceInfo.java
index ee1ab2dc8f5..f57518272d2 100644
--- a/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CHReferenceInfo.java
+++ b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CHReferenceInfo.java
@@ -11,7 +11,16 @@
 
 package org.eclipse.cdt.internal.ui.callhierarchy;
 
+import java.util.Comparator;
+
 public class CHReferenceInfo {
+	public static final Comparator COMPARE_OFFSET = new Comparator() {
+		public int compare(Object o1, Object o2) {
+			CHReferenceInfo r1= (CHReferenceInfo) o1;
+			CHReferenceInfo r2= (CHReferenceInfo) o2;
+			return r1.fOffset - r2.fOffset;
+		}
+	};
 	private int fOffset;
 	private int fLength;
 
diff --git a/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CallHierarchyUI.java b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CallHierarchyUI.java
index 1b834b6a73e..71aaad33222 100644
--- a/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CallHierarchyUI.java
+++ b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CallHierarchyUI.java
@@ -23,9 +23,14 @@ import org.eclipse.ui.IWorkbenchPage;
 import org.eclipse.ui.IWorkbenchWindow;
 
 import org.eclipse.cdt.core.CCorePlugin;
+import org.eclipse.cdt.core.dom.ast.DOMException;
 import org.eclipse.cdt.core.dom.ast.IASTName;
 import org.eclipse.cdt.core.dom.ast.IASTTranslationUnit;
 import org.eclipse.cdt.core.dom.ast.IBinding;
+import org.eclipse.cdt.core.dom.ast.IEnumerator;
+import org.eclipse.cdt.core.dom.ast.IFunction;
+import org.eclipse.cdt.core.dom.ast.IVariable;
+import org.eclipse.cdt.core.dom.ast.c.ICExternalBinding;
 import org.eclipse.cdt.core.index.IIndex;
 import org.eclipse.cdt.core.index.IIndexManager;
 import org.eclipse.cdt.core.model.ICElement;
@@ -36,7 +41,6 @@ import org.eclipse.cdt.ui.CUIPlugin;
 
 import org.eclipse.cdt.internal.ui.actions.OpenActionUtil;
 import org.eclipse.cdt.internal.ui.editor.CEditor;
-import org.eclipse.cdt.internal.ui.missingapi.CIndexQueries;
 import org.eclipse.cdt.internal.ui.util.ExceptionHandler;
 import org.eclipse.cdt.internal.ui.viewsupport.CElementLabels;
 import org.eclipse.cdt.internal.ui.viewsupport.FindNameForSelectionVisitor;
@@ -120,7 +124,6 @@ public class CallHierarchyUI {
     
 	private static ICElement[] findDefinitions(ICProject project, IEditorInput editorInput, ITextSelection sel) throws CoreException {
 		try {
-			CIndexQueries indexq= CIndexQueries.getInstance();
 			IIndex index= CCorePlugin.getIndexManager().getIndex(project, IIndexManager.ADD_DEPENDENCIES | IIndexManager.ADD_DEPENDENT);
 
 			index.acquireReadLock();
@@ -128,19 +131,19 @@ public class CallHierarchyUI {
 				IASTName name= getSelectedName(index, editorInput, sel);
 				if (name != null) {
 					IBinding binding= name.resolveBinding();
-					if (CIndexQueries.isRelevantForCallHierarchy(binding)) {
+					if (CallHierarchyUI.isRelevantForCallHierarchy(binding)) {
 						if (name.isDefinition()) {
-							ICElement elem= indexq.getCElementForName(project, name);
+							ICElement elem= CHQueries.getCElementForName(project, index, name);
 							if (elem != null) {
 								return new ICElement[]{elem};
 							}
 						}
 						else {
-							ICElement[] elems= indexq.findAllDefinitions(index, name);
+							ICElement[] elems= CHQueries.findAllDefinitions(index, binding);
 							if (elems.length == 0) {
-								elems= indexq.findAllDefinitions(index, name);
+								elems= CHQueries.findAllDefinitions(index, binding);
 								if (elems.length == 0) {
-									ICElement elem= indexq.findAnyDeclaration(index, project, name);
+									ICElement elem= CHQueries.findAnyDeclaration(index, project, binding);
 									if (elems != null) {
 										elems= new ICElement[]{elem};
 									}
@@ -160,6 +163,9 @@ public class CallHierarchyUI {
 		catch (CoreException e) {
 			CUIPlugin.getDefault().log(e);
 		} 
+		catch (DOMException e) {
+			CUIPlugin.getDefault().log(e);
+		} 
 		catch (InterruptedException e) {
 		}
 		return null;
@@ -179,4 +185,39 @@ public class CallHierarchyUI {
 		ast.accept(finder);
 		return finder.getSelectedName();
 	}
+
+	public static boolean isRelevantForCallHierarchy(IBinding binding) {
+		if (binding instanceof ICExternalBinding ||
+				binding instanceof IEnumerator ||
+				binding instanceof IFunction ||
+				binding instanceof IVariable) {
+			return true;
+		}
+		return false;
+	}
+
+	public static boolean isRelevantForCallHierarchy(ICElement elem) {
+		if (elem == null) {
+			return false;
+		}
+		switch (elem.getElementType()) {
+		case ICElement.C_CLASS_CTOR:
+		case ICElement.C_CLASS_DTOR:
+		case ICElement.C_ENUMERATOR:
+		case ICElement.C_FIELD:
+		case ICElement.C_FUNCTION:
+		case ICElement.C_FUNCTION_DECLARATION:
+		case ICElement.C_METHOD:
+		case ICElement.C_METHOD_DECLARATION:
+		case ICElement.C_TEMPLATE_FUNCTION:
+		case ICElement.C_TEMPLATE_FUNCTION_DECLARATION:
+		case ICElement.C_TEMPLATE_METHOD:
+		case ICElement.C_TEMPLATE_METHOD_DECLARATION:
+		case ICElement.C_TEMPLATE_VARIABLE:
+		case ICElement.C_VARIABLE:
+		case ICElement.C_VARIABLE_DECLARATION:
+			return true;
+		}
+		return false;
+	}
 }
diff --git a/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CalledByResult.java b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CalledByResult.java
new file mode 100644
index 00000000000..ef9d9d0552a
--- /dev/null
+++ b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CalledByResult.java
@@ -0,0 +1,44 @@
+/*******************************************************************************
+ * Copyright (c) 2006 Wind River Systems, Inc. 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:
+ *    Markus Schorn - initial API and implementation
+ *******************************************************************************/ 
+
+package org.eclipse.cdt.internal.ui.callhierarchy;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import org.eclipse.cdt.core.index.IIndexName;
+import org.eclipse.cdt.core.model.ICElement;
+
+public class CalledByResult {
+	private Map fElementToReferences= new HashMap();
+
+	public ICElement[] getElements() {
+		Set elements = fElementToReferences.keySet();
+		return (ICElement[]) elements.toArray(new ICElement[elements.size()]);
+	}
+	
+	public IIndexName[] getReferences(ICElement calledElement) {
+		List references= (List) fElementToReferences.get(calledElement);
+		return (IIndexName[]) references.toArray(new IIndexName[references.size()]);
+	}
+
+	public void add(ICElement elem, IIndexName ref) {
+		List list= (List) fElementToReferences.get(elem);
+		if (list == null) {
+			list= new ArrayList();
+			fElementToReferences.put(elem, list);
+		}
+		list.add(ref);
+	}
+}
diff --git a/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CallsToResult.java b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CallsToResult.java
new file mode 100644
index 00000000000..e345f88b83c
--- /dev/null
+++ b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/CallsToResult.java
@@ -0,0 +1,45 @@
+/*******************************************************************************
+ * Copyright (c) 2006 Wind River Systems, Inc. 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:
+ *    Markus Schorn - initial API and implementation
+ *******************************************************************************/ 
+
+package org.eclipse.cdt.internal.ui.callhierarchy;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import org.eclipse.cdt.core.index.IIndexName;
+import org.eclipse.cdt.core.model.ICElement;
+
+public class CallsToResult {
+	private Map fElementSetsToReferences= new HashMap();
+
+	public CElementSet[] getElementSets() {
+		Set elementSets = fElementSetsToReferences.keySet();
+		return (CElementSet[]) elementSets.toArray(new CElementSet[elementSets.size()]);
+	}
+	
+	public IIndexName[] getReferences(CElementSet elementSet) {
+		List references= (List) fElementSetsToReferences.get(elementSet);
+		return (IIndexName[]) references.toArray(new IIndexName[references.size()]);
+	}
+
+	public void add(ICElement[] elems, IIndexName ref) {
+		CElementSet key= new CElementSet(elems);
+		List list= (List) fElementSetsToReferences.get(key);
+		if (list == null) {
+			list= new ArrayList();
+			fElementSetsToReferences.put(key, list);
+		}
+		list.add(ref);
+	}
+}
diff --git a/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/ReferenceVisitor.java b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/ReferenceVisitor.java
new file mode 100644
index 00000000000..87805ab1d14
--- /dev/null
+++ b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/callhierarchy/ReferenceVisitor.java
@@ -0,0 +1,71 @@
+/*******************************************************************************
+ * Copyright (c) 2006 Wind River Systems, Inc. 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:
+ *    Markus Schorn - initial API and implementation
+ *******************************************************************************/ 
+
+package org.eclipse.cdt.internal.ui.callhierarchy;
+
+import java.util.ArrayList;
+
+import org.eclipse.cdt.core.dom.ast.ASTVisitor;
+import org.eclipse.cdt.core.dom.ast.IASTDeclaration;
+import org.eclipse.cdt.core.dom.ast.IASTFileLocation;
+import org.eclipse.cdt.core.dom.ast.IASTName;
+
+/**
+ * Visitor to find references in a given range of the source code.
+ * @since 4.0
+ */
+class ReferenceVisitor extends ASTVisitor {
+	private ArrayList fReferences= new ArrayList();
+	private int fOffset;
+	private int fEndOffset;
+	private String fFileName;
+	
+	ReferenceVisitor(String fileName, int offset, int length) {
+		shouldVisitNames= true;
+		shouldVisitDeclarations= true;
+		
+		fFileName= fileName;
+		fOffset= offset;
+		fEndOffset= offset+length;
+	}
+	
+	public IASTName[] getReferences() {
+		return (IASTName[]) fReferences.toArray(new IASTName[fReferences.size()]);
+	}
+
+	public int visit(IASTName name) {
+		if (name.isReference()) {
+			IASTFileLocation loc= name.getFileLocation();
+			if (!loc.getFileName().equals(fFileName)) {
+				return PROCESS_SKIP;
+			}
+			int offset= loc.getNodeOffset();
+			if (fOffset <= offset && offset+loc.getNodeLength() <= fEndOffset) {
+				fReferences.add(name);
+			}
+		}
+		return super.visit(name);
+	}
+
+	public int visit(IASTDeclaration declaration) {
+		IASTFileLocation loc= declaration.getFileLocation();
+		if (loc != null) {
+			if (!loc.getFileName().equals(fFileName)) {
+				return PROCESS_SKIP;
+			}
+			int offset= loc.getNodeOffset();
+			if (offset + loc.getNodeLength() <= fOffset || fEndOffset <= offset) {
+				return PROCESS_SKIP;
+			}
+		}
+		return PROCESS_CONTINUE;
+	}
+}