[
Date Prev][
Date Next][
Thread Prev][
Thread Next][
Date Index][
Thread Index]
[
List Home]
|
[cdt-patch] patch for AST View - speed + display problems
|
This patch includes:
- several enhancements made to the DOM
AST View to improve performance
- "Display Problems" button
that will display all found IASTProblems in the AST via the Search View
Note:
- with this patch the view now generates/searches
the AST View's model with a vastly improved algorithm (so that only the
necessary branches of the AST are taken when searching for a node)... although
this is much faster than the previous algorithm, any small bugs will cause
the AST View to less resemble the actual AST itself (ex: if a parent is
not displayed in the AST View because it has 0 offset, then all children
of that parent are grouped under that parent instead of having a proper
tree)
- another enhancement was to use arrays
instead of ArrayLists and to only sort nodes when they are viewed graphically
in the tree (instead of sorting nodes everytime they are merged into the
tree) ... this helps improve the speed when the View is generated, but
slows things down when expanding a tree with a large set of children
- I raised the following bugs that were
found with this patch via #including <windows.h>:
87894 [Offset] example from windows.h
generates weird AST in DOM View
86993 [Selection] CPPASTLinkageSpecification
with bad offset due to macro expansion causes selection to fail in CPP
Devin Steffler
IBM's Eclipse CDT
Ottawa (Palladium), Ontario, Canada
Index: parser/org/eclipse/cdt/core/parser/util/ArrayUtil.java
===================================================================
RCS file: /home/tools/org.eclipse.cdt-core/org.eclipse.cdt.core/parser/org/eclipse/cdt/core/parser/util/ArrayUtil.java,v
retrieving revision 1.6
diff -u -r1.6 ArrayUtil.java
--- parser/org/eclipse/cdt/core/parser/util/ArrayUtil.java 3 Mar 2005 19:28:53 -0000 1.6
+++ parser/org/eclipse/cdt/core/parser/util/ArrayUtil.java 14 Mar 2005 15:34:57 -0000
@@ -188,4 +188,30 @@
if( array[i] == obj ) return true;
return false;
}
+
+ /**
+ * Removes all of the nulls from the array and returns a new
+ * array that contains all of the non-null elements.
+ *
+ * If there are no nulls in the original array then the original
+ * array is returned.
+ *
+ * @return
+ */
+ public static Object[] removeNulls(Class c, Object[] array) {
+ if( array == null )
+ return (Object[]) Array.newInstance( c, 0 );
+
+ int i = 0;
+ int j = 0;
+ Object[] newArray = new Object[array.length];
+ for( ; i < array.length; i++ ){
+ if( array[i] != null ) newArray[j++] = array[i];
+ }
+
+ if (j<i) return ArrayUtil.trim(c, newArray);
+
+ return array;
+ }
+
}Index: src/org/eclipse/cdt/ui/tests/DOMAST/CPPPopulateASTViewAction.java
===================================================================
RCS file: /home/tools/org.eclipse.cdt-core/org.eclipse.cdt.ui.tests/src/org/eclipse/cdt/ui/tests/DOMAST/CPPPopulateASTViewAction.java,v
retrieving revision 1.16
diff -u -r1.16 CPPPopulateASTViewAction.java
--- src/org/eclipse/cdt/ui/tests/DOMAST/CPPPopulateASTViewAction.java 8 Mar 2005 19:32:09 -0000 1.16
+++ src/org/eclipse/cdt/ui/tests/DOMAST/CPPPopulateASTViewAction.java 14 Mar 2005 15:35:25 -0000
@@ -36,8 +36,10 @@
import org.eclipse.cdt.core.dom.ast.cpp.ICPPASTConstructorChainInitializer;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPASTFunctionDeclarator;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPASTFunctionTryBlockDeclarator;
+import org.eclipse.cdt.core.dom.ast.cpp.ICPPASTLinkageSpecification;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPASTNamespaceDefinition;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPASTCompositeTypeSpecifier.ICPPASTBaseSpecifier;
+import org.eclipse.cdt.core.parser.util.ArrayUtil;
import org.eclipse.cdt.internal.core.dom.parser.ASTNode;
import org.eclipse.cdt.internal.core.parser.scanner2.LocationMap.ASTInclusionStatement;
import org.eclipse.core.runtime.IProgressMonitor;
@@ -46,6 +48,7 @@
* @author dsteffle
*/
public class CPPPopulateASTViewAction extends CPPASTVisitor implements IPopulateDOMASTAction {
+ private static final int INITIAL_PROBLEM_SIZE = 4;
private static final int INITIAL_INCLUDE_STATEMENT_SIZE = 8;
{
shouldVisitNames = true;
@@ -64,6 +67,7 @@
TreeParent root = null;
IProgressMonitor monitor = null;
+ IASTProblem[] astProblems = new IASTProblem[INITIAL_PROBLEM_SIZE];
public CPPPopulateASTViewAction(IASTTranslationUnit tu, IProgressMonitor monitor) {
root = new TreeParent(tu);
@@ -75,7 +79,8 @@
if (node == null) return PROCESS_CONTINUE;
IASTNodeLocation[] nodeLocations = node.getNodeLocations();
- if (!(nodeLocations.length > 0 &&
+ // TODO Devin !(node instanceof ICPPASTLinkageSpecification) below is a hack job for bug 86993
+ if (!(node instanceof ICPPASTLinkageSpecification) && !(nodeLocations.length > 0 &&
nodeLocations[0].getNodeOffset() >= 0 &&
nodeLocations[0].getNodeLength() > 0))
return PROCESS_CONTINUE;
@@ -89,8 +94,14 @@
parent.addChild(tree);
// set filter flags
- if (node instanceof IASTProblemHolder || node instanceof IASTProblem)
+ if (node instanceof IASTProblemHolder || node instanceof IASTProblem) {
tree.setFiltersFlag(TreeObject.FLAG_PROBLEM);
+
+ if (node instanceof IASTProblemHolder)
+ astProblems = (IASTProblem[])ArrayUtil.append(IASTProblemHolder.class, astProblems, ((IASTProblemHolder)node).getProblem());
+ else
+ astProblems = (IASTProblem[])ArrayUtil.append(IASTProblemHolder.class, astProblems, node);
+ }
if (node instanceof IASTPreprocessorStatement)
tree.setFiltersFlag(TreeObject.FLAG_PREPROCESSOR);
if (node instanceof IASTPreprocessorIncludeStatement)
@@ -247,20 +258,18 @@
int index = 0;
for(int i=0; i<statements.length; i++) {
if (monitor != null && monitor.isCanceled()) return;
- if (index+1 > includes.length) {
- IASTPreprocessorIncludeStatement[] newIncludes = new IASTPreprocessorIncludeStatement[includes.length * 2];
- for (int j=0; j<includes.length; j++) {
- newIncludes[j] = includes[j];
+ if (statements[i] instanceof IASTPreprocessorIncludeStatement) {
+ if (index == includes.length) {
+ includes = (IASTPreprocessorIncludeStatement[])ArrayUtil.append(IASTPreprocessorIncludeStatement.class, includes, statements[i]);
+ index++;
+ } else {
+ includes[index++] = (IASTPreprocessorIncludeStatement)statements[i];
}
- includes = newIncludes;
}
-
- if (statements[i] instanceof IASTPreprocessorIncludeStatement)
- includes[index++] = (IASTPreprocessorIncludeStatement)statements[i];
}
// get the tree model elements corresponding to the includes
- TreeParent[] treeIncludes = new TreeParent[includes.length];
+ TreeParent[] treeIncludes = new TreeParent[index];
for (int i=0; i<treeIncludes.length; i++) {
if (monitor != null && monitor.isCanceled()) return;
treeIncludes[i] = root.findTreeObject(includes[i], false);
@@ -269,14 +278,14 @@
// loop through the includes and make sure that all of the nodes
// that are children of the TU are in the proper include (based on offset)
TreeObject child = null;
- for (int i=treeIncludes.length-1; i>=0; i--) {
+ outerLoop: for (int i=treeIncludes.length-1; i>=0; i--) {
if (treeIncludes[i] == null) continue;
- for(int j=root.getChildren().length-1; j>=0; j--) {
+ for(int j=root.getChildren(false).length-1; j>=0; j--) {
if (monitor != null && monitor.isCanceled()) return;
- child = root.getChildren()[j];
-
- if (treeIncludes[i] != child &&
+ child = root.getChildren(false)[j];
+
+ if (child != null && treeIncludes[i] != child &&
includes[i] instanceof ASTInclusionStatement &&
((ASTNode)child.getNode()).getOffset() >= ((ASTInclusionStatement)includes[i]).startOffset &&
((ASTNode)child.getNode()).getOffset() <= ((ASTInclusionStatement)includes[i]).endOffset) {
@@ -285,5 +294,9 @@
}
}
}
+ }
+
+ public IASTProblem[] getASTProblems() {
+ return astProblems;
}
}
Index: src/org/eclipse/cdt/ui/tests/DOMAST/CPopulateASTViewAction.java
===================================================================
RCS file: /home/tools/org.eclipse.cdt-core/org.eclipse.cdt.ui.tests/src/org/eclipse/cdt/ui/tests/DOMAST/CPopulateASTViewAction.java,v
retrieving revision 1.19
diff -u -r1.19 CPopulateASTViewAction.java
--- src/org/eclipse/cdt/ui/tests/DOMAST/CPopulateASTViewAction.java 8 Mar 2005 19:32:09 -0000 1.19
+++ src/org/eclipse/cdt/ui/tests/DOMAST/CPopulateASTViewAction.java 14 Mar 2005 15:35:25 -0000
@@ -33,6 +33,7 @@
import org.eclipse.cdt.core.dom.ast.IASTEnumerationSpecifier.IASTEnumerator;
import org.eclipse.cdt.core.dom.ast.c.CASTVisitor;
import org.eclipse.cdt.core.dom.ast.c.ICASTDesignator;
+import org.eclipse.cdt.core.parser.util.ArrayUtil;
import org.eclipse.cdt.internal.core.dom.parser.ASTNode;
import org.eclipse.cdt.internal.core.parser.scanner2.LocationMap.ASTInclusionStatement;
import org.eclipse.core.runtime.IProgressMonitor;
@@ -41,6 +42,7 @@
* @author dsteffle
*/
public class CPopulateASTViewAction extends CASTVisitor implements IPopulateDOMASTAction {
+ private static final int INITIAL_PROBLEM_SIZE = 4;
private static final int INITIAL_INCLUDE_STATEMENT_SIZE = 8;
{
shouldVisitNames = true;
@@ -58,6 +60,7 @@
TreeParent root = null;
IProgressMonitor monitor = null;
+ IASTProblem[] astProblems = new IASTProblem[INITIAL_PROBLEM_SIZE];
public CPopulateASTViewAction(IASTTranslationUnit tu, IProgressMonitor monitor) {
root = new TreeParent(tu);
@@ -83,13 +86,21 @@
parent.addChild(tree);
// set filter flags
- if (node instanceof IASTProblemHolder || node instanceof IASTProblem)
+ if (node instanceof IASTProblemHolder || node instanceof IASTProblem) {
tree.setFiltersFlag(TreeObject.FLAG_PROBLEM);
+
+ if (node instanceof IASTProblemHolder)
+ astProblems = (IASTProblem[])ArrayUtil.append(IASTProblemHolder.class, astProblems, ((IASTProblemHolder)node).getProblem());
+ else
+ astProblems = (IASTProblem[])ArrayUtil.append(IASTProblemHolder.class, astProblems, node);
+ }
if (node instanceof IASTPreprocessorStatement)
tree.setFiltersFlag(TreeObject.FLAG_PREPROCESSOR);
if (node instanceof IASTPreprocessorIncludeStatement)
tree.setFiltersFlag(TreeObject.FLAG_INCLUDE_STATEMENTS);
+
+
return PROCESS_CONTINUE;
}
@@ -220,20 +231,18 @@
int index = 0;
for(int i=0; i<statements.length; i++) {
if (monitor != null && monitor.isCanceled()) return;
- if (index+1 > includes.length) {
- IASTPreprocessorIncludeStatement[] newIncludes = new IASTPreprocessorIncludeStatement[includes.length * 2];
- for (int j=0; j<includes.length; j++) {
- newIncludes[j] = includes[j];
+ if (statements[i] instanceof IASTPreprocessorIncludeStatement) {
+ if (index == includes.length) {
+ includes = (IASTPreprocessorIncludeStatement[])ArrayUtil.append(IASTPreprocessorIncludeStatement.class, includes, statements[i]);
+ index++;
+ } else {
+ includes[index++] = (IASTPreprocessorIncludeStatement)statements[i];
}
- includes = newIncludes;
}
-
- if (statements[i] instanceof IASTPreprocessorIncludeStatement)
- includes[index++] = (IASTPreprocessorIncludeStatement)statements[i];
}
// get the tree model elements corresponding to the includes
- TreeParent[] treeIncludes = new TreeParent[includes.length];
+ TreeParent[] treeIncludes = new TreeParent[index];
for (int i=0; i<treeIncludes.length; i++) {
if (monitor != null && monitor.isCanceled()) return;
treeIncludes[i] = root.findTreeObject(includes[i], false);
@@ -242,14 +251,15 @@
// loop through the includes and make sure that all of the nodes
// that are children of the TU are in the proper include (based on offset)
TreeObject child = null;
- for (int i=treeIncludes.length-1; i>=0; i--) {
+ outerLoop: for (int i=treeIncludes.length-1; i>=0; i--) {
if (treeIncludes[i] == null) continue;
- for(int j=root.getChildren().length-1; j>=0; j--) {
+ for(int j=root.getChildren(false).length-1; j>=0; j--) {
if (monitor != null && monitor.isCanceled()) return;
- child = root.getChildren()[j];
-
- if (treeIncludes[i] != child &&
+ child = root.getChildren(false)[j];
+
+ if (child != null &&
+ treeIncludes[i] != child &&
includes[i] instanceof ASTInclusionStatement &&
((ASTNode)child.getNode()).getOffset() >= ((ASTInclusionStatement)includes[i]).startOffset &&
((ASTNode)child.getNode()).getOffset() <= ((ASTInclusionStatement)includes[i]).endOffset) {
@@ -258,5 +268,9 @@
}
}
}
+ }
+
+ public IASTProblem[] getASTProblems() {
+ return astProblems;
}
}
Index: src/org/eclipse/cdt/ui/tests/DOMAST/DOMAST.java
===================================================================
RCS file: /home/tools/org.eclipse.cdt-core/org.eclipse.cdt.ui.tests/src/org/eclipse/cdt/ui/tests/DOMAST/DOMAST.java,v
retrieving revision 1.29
diff -u -r1.29 DOMAST.java
--- src/org/eclipse/cdt/ui/tests/DOMAST/DOMAST.java 11 Mar 2005 20:35:18 -0000 1.29
+++ src/org/eclipse/cdt/ui/tests/DOMAST/DOMAST.java 14 Mar 2005 15:35:25 -0000
@@ -131,10 +131,12 @@
private static final String POPUPMENU = "#PopupMenu"; //$NON-NLS-1$
private static final String OPEN_DECLARATIONS = "Open Declarations"; //$NON-NLS-1$
private static final String OPEN_REFERENCES = "Open References"; //$NON-NLS-1$
+ private static final String DISPLAY_PROBLEMS = "Display Problems"; //$NON-NLS-1$
TreeViewer viewer;
private DrillDownAdapter drillDownAdapter;
private Action openDeclarationsAction;
private Action openReferencesAction;
+ private Action displayProblemsAction;
private Action displayNodeTypeAction;
private Action displayNodeSignatureAction;
private Action displayExpressionAction;
@@ -164,9 +166,10 @@
public class ViewContentProvider implements IStructuredContentProvider,
ITreeContentProvider {
private static final String POPULATING_AST_VIEW = "Populating AST View"; //$NON-NLS-1$
- private TreeParent invisibleRoot;
+ private TreeParent invisibleRoot;
private TreeParent tuTreeParent = null;
private IASTTranslationUnit tu = null;
+ private IASTProblem[] astProblems = null;
public ViewContentProvider() {
}
@@ -343,7 +346,7 @@
return Status.CANCEL_STATUS;
if (monitor.isCanceled()) return Status.CANCEL_STATUS;
- monitor.beginTask(name, 7);
+ monitor.beginTask(name, 8);
start=System.currentTimeMillis();
IPopulateDOMASTAction action = null;
@@ -414,6 +417,12 @@
System.out.println("[DOM AST View] done " + GROUPING_AST + ": " + (System.currentTimeMillis()- start) );
root.addChild(action.getTree());
+
+ // get the IASTProblems from the action
+ if (action instanceof CPopulateASTViewAction)
+ astProblems = ((CPopulateASTViewAction)action).getASTProblems();
+ else if (action instanceof CPPPopulateASTViewAction)
+ astProblems = ((CPPPopulateASTViewAction)action).getASTProblems();
provider.setInvisibleRoot(root);
@@ -423,11 +432,15 @@
return Status.OK_STATUS;
}
-
+
}
+
+ public IASTProblem[] getASTProblems() {
+ return astProblems;
+ }
private void initialize() {
- invisibleRoot = new TreeParent(null); // blank the AST View, when the job above is complete it will update the AST View with the proper tree
+ invisibleRoot = new TreeParent(); // blank the AST View, when the job above is complete it will update the AST View with the proper tree
}
protected void setInvisibleRoot(TreeParent root) {
@@ -533,6 +546,7 @@
class ViewLabelProvider extends LabelProvider {
public String getText(Object obj) {
+ if (obj == null) return "";
return obj.toString();
}
@@ -598,6 +612,7 @@
}
class NameSorter extends ViewerSorter {
+
}
public DOMAST() {
@@ -628,6 +643,7 @@
viewer.setLabelProvider(new ViewLabelProvider());
viewer.setInput(getViewSite());
+
makeActions();
hookContextMenu();
hookSingleClickAction();
@@ -757,6 +773,7 @@
manager.add(clearAction);
manager.add(new Separator());
manager.add(searchNamesAction);
+ manager.add(displayProblemsAction);
manager.add(new Separator());
drillDownAdapter.addNavigationActions(manager);
}
@@ -840,6 +857,10 @@
openReferencesAction.setImageDescriptor(PlatformUI.getWorkbench().getSharedImages()
.getImageDescriptor(ISharedImages.IMG_OBJS_INFO_TSK));
+ displayProblemsAction = new DisplayProblemsResultAction();
+ displayProblemsAction.setText(DISPLAY_PROBLEMS);
+ displayProblemsAction.setImageDescriptor(DOMASTPluginImages.DESC_IASTProblem);
+
displayNodeTypeAction = new Action() {
public void run() {
ISelection selection = viewer.getSelection();
@@ -1026,6 +1047,26 @@
NewSearchUI.runQuery(job);
}
}
+
+ private class DisplayProblemsResultAction extends Action {
+ private static final String IASTPROBLEM = "IASTProblem"; //$NON-NLS-1$
+ private static final String PROBLEMS_FOUND = "Problems Found"; //$NON-NLS-1$
+ protected void displayProblems(IASTProblem[] problems, String queryLabel, String pattern) {
+ DOMQuery job = new DOMQuery(problems, queryLabel, pattern);
+ NewSearchUI.activateSearchResultView();
+ NewSearchUI.runQuery(job);
+ }
+
+ public void run() {
+ if (viewer.getTree().getItems().length == 0) {
+ showMessage(DOM_AST_HAS_NO_CONTENT);
+ }
+
+ if (viewer.getContentProvider() instanceof ViewContentProvider) {
+ displayProblems(((ViewContentProvider)viewer.getContentProvider()).getASTProblems(), PROBLEMS_FOUND, IASTPROBLEM);
+ }
+ }
+ }
private void hookSingleClickAction() {
viewer.addSelectionChangedListener(new ISelectionChangedListener() {
Index: src/org/eclipse/cdt/ui/tests/DOMAST/DOMQuery.java
===================================================================
RCS file: /home/tools/org.eclipse.cdt-core/org.eclipse.cdt.ui.tests/src/org/eclipse/cdt/ui/tests/DOMAST/DOMQuery.java,v
retrieving revision 1.3
diff -u -r1.3 DOMQuery.java
--- src/org/eclipse/cdt/ui/tests/DOMAST/DOMQuery.java 3 Feb 2005 15:26:24 -0000 1.3
+++ src/org/eclipse/cdt/ui/tests/DOMAST/DOMQuery.java 14 Mar 2005 15:35:26 -0000
@@ -12,7 +12,9 @@
import org.eclipse.cdt.core.dom.ast.IASTFileLocation;
import org.eclipse.cdt.core.dom.ast.IASTName;
+import org.eclipse.cdt.core.dom.ast.IASTNode;
import org.eclipse.cdt.core.dom.ast.IASTNodeLocation;
+import org.eclipse.cdt.core.dom.ast.IASTProblem;
import org.eclipse.cdt.core.model.ICElement;
import org.eclipse.cdt.core.search.BasicSearchMatch;
import org.eclipse.cdt.core.search.IMatch;
@@ -41,15 +43,15 @@
private static final String BLANK_STRING = ""; //$NON-NLS-1$
private CSearchResult _result;
- private IASTName[] names = null;
+ private IASTNode[] nodes = null;
private String queryLabel = null;
/**
*
*/
- public DOMQuery(IASTName[] names, String queryLabel, String pattern) {
+ public DOMQuery(IASTNode[] nodes, String queryLabel, String pattern) {
super(CTestPlugin.getWorkspace(), pattern, false, null, null, null, queryLabel, null);
- this.names = names;
+ this.nodes = nodes;
this.queryLabel = queryLabel;
}
@@ -66,15 +68,15 @@
collector.aboutToStart();
- for (int i=0; i<names.length; i++) {
+ for (int i=0; i<nodes.length; i++) {
try {
String fileName = null;
IFile file = null;
IPath path = null;
int start = 0;
int end = 0;
- if ( names[i] != null ) {
- IASTNodeLocation [] location = names[i].getNodeLocations();
+ if ( nodes[i] != null ) {
+ IASTNodeLocation [] location = nodes[i].getNodeLocations();
if( location.length > 0 && location[0] instanceof IASTFileLocation )
fileName = ((IASTFileLocation)location[0]).getFileName(); // TODO Devin this is in two places now, put into one, and fix up the location[0] for things like macros
else
@@ -83,11 +85,11 @@
path = new Path(fileName);
file = ResourcesPlugin.getWorkspace().getRoot().getFileForLocation(path);
- if (names[i].getNodeLocations().length > 0) { // fix for 84223
- start = names[i].getNodeLocations()[0].getNodeOffset();
- end = names[i].getNodeLocations()[0].getNodeOffset() + names[i].getNodeLocations()[0].getNodeLength();
+ if (nodes[i].getNodeLocations().length > 0) { // fix for 84223
+ start = nodes[i].getNodeLocations()[0].getNodeOffset();
+ end = nodes[i].getNodeLocations()[0].getNodeOffset() + nodes[i].getNodeLocations()[0].getNodeLength();
- collector.acceptMatch( createMatch(file, start, end, names[i], path ) );
+ collector.acceptMatch( createMatch(file, start, end, nodes[i], path ) );
}
}
} catch (CoreException ce) {}
@@ -99,7 +101,7 @@
return new Status(IStatus.OK, CTestPlugin.getPluginId(), 0, BLANK_STRING, null); //$NON-NLS-1$
}
- public IMatch createMatch( Object fileResource, int start, int end, IASTName name, IPath referringElement ) {
+ public IMatch createMatch( Object fileResource, int start, int end, IASTNode node, IPath referringElement ) {
BasicSearchMatch result = new BasicSearchMatch();
if( fileResource instanceof IResource )
result.resource = (IResource) fileResource;
@@ -111,7 +113,12 @@
result.parentName = BLANK_STRING; //$NON-NLS-1$
result.referringElement = referringElement;
- result.name = name.toString();
+ if (node instanceof IASTName)
+ result.name = node.toString();
+ else if (node instanceof IASTProblem)
+ result.name = ((IASTProblem)node).getMessage();
+ else
+ result.name = node.toString();
result.type = ICElement.C_FIELD; // TODO Devin static for now, want something like BasicSearchResultCollector#setElementInfo
result.visibility = ICElement.CPP_PUBLIC; // TODO Devin static for now, want something like BasicSearchResultCollector#setElementInfo
Index: src/org/eclipse/cdt/ui/tests/DOMAST/FindIASTNameTarget.java
===================================================================
RCS file: /home/tools/org.eclipse.cdt-core/org.eclipse.cdt.ui.tests/src/org/eclipse/cdt/ui/tests/DOMAST/FindIASTNameTarget.java,v
retrieving revision 1.4
diff -u -r1.4 FindIASTNameTarget.java
--- src/org/eclipse/cdt/ui/tests/DOMAST/FindIASTNameTarget.java 8 Mar 2005 19:32:09 -0000 1.4
+++ src/org/eclipse/cdt/ui/tests/DOMAST/FindIASTNameTarget.java 14 Mar 2005 15:35:26 -0000
@@ -401,7 +401,7 @@
// get the TreeObject from the AST View's model corresponding to that name
TreeObject treeNode = null;
TreeItem treeItem = null;
- treeNode = tuTreeParent.findTreeObject(foundName, true, true);
+ treeNode = tuTreeParent.findTreeObject(foundName, true);
if (treeNode != null && treeNode.getParent() != null) {
// found a matching TreeObject, so expand the tree to that object
@@ -413,7 +413,7 @@
((searchForward && index < matchingNames.length) ||
(!searchForward && index >= 0))) {
foundName = findNextMatchingName( findString, searchForward, caseSensitive, wholeWord, regExSearch );
- treeNode = tuTreeParent.findTreeObject(foundName, true, true);
+ treeNode = tuTreeParent.findTreeObject(foundName, true);
if (treeNode != null && treeNode.getParent() != null) {
// found a matching TreeObject, so expand the tree to that object
Index: src/org/eclipse/cdt/ui/tests/DOMAST/TreeParent.java
===================================================================
RCS file: /home/tools/org.eclipse.cdt-core/org.eclipse.cdt.ui.tests/src/org/eclipse/cdt/ui/tests/DOMAST/TreeParent.java,v
retrieving revision 1.7
diff -u -r1.7 TreeParent.java
--- src/org/eclipse/cdt/ui/tests/DOMAST/TreeParent.java 23 Feb 2005 17:21:34 -0000 1.7
+++ src/org/eclipse/cdt/ui/tests/DOMAST/TreeParent.java 14 Mar 2005 15:35:26 -0000
@@ -10,81 +10,103 @@
**********************************************************************/
package org.eclipse.cdt.ui.tests.DOMAST;
-import java.util.ArrayList;
-import java.util.Iterator;
+import java.util.Arrays;
+import java.util.Comparator;
-import org.eclipse.cdt.core.dom.ast.IASTName;
import org.eclipse.cdt.core.dom.ast.IASTNode;
import org.eclipse.cdt.core.dom.ast.IASTNodeLocation;
+import org.eclipse.cdt.core.dom.ast.IASTPreprocessorIncludeStatement;
+import org.eclipse.cdt.core.dom.ast.IASTTranslationUnit;
+import org.eclipse.cdt.core.parser.util.ArrayUtil;
import org.eclipse.cdt.internal.core.dom.parser.ASTNode;
/**
* @author dsteffle
*/
public class TreeParent extends TreeObject {
- private ArrayList children;
+ private static final TreeObject[] EMPTY_CHILDREN_ARRAY = new TreeObject[0];
+ private static final int DEFAULT_NODE_CHAIN_SIZE = 4;
+ private static final int DEFAULT_CHILDREN_SIZE = 4;
+ int index=0;
+ private TreeObject[] children;
+ boolean cleanupedElements = false;
+
+ public int getStartSearch() {
+ return index;
+ }
+ public TreeParent() {
+ super(null);
+ children = EMPTY_CHILDREN_ARRAY;
+ }
+
public TreeParent(IASTNode node) {
super(node);
- children = new ArrayList();
+ children = new TreeObject[DEFAULT_CHILDREN_SIZE];
}
public void addChild(TreeObject child) {
- int index = 0;
- for(int i=0; i<children.size(); i++) {
- TreeObject treeObj = (TreeObject)children.get(i);
- int treeObjOffset = 0;
- int childObjOffset = 0;
- if( treeObj.getNode() instanceof ASTNode )
- treeObjOffset = ((ASTNode)treeObj.getNode()).getOffset();
-
- if( child.getNode() instanceof ASTNode )
- childObjOffset = ((ASTNode)child.getNode()).getOffset();
-
- if ( treeObjOffset < childObjOffset ){
- index = i+1;
- } else {
- break;
- }
+ if (index==children.length) {
+ children = (TreeObject[])ArrayUtil.append(TreeObject.class, children, child);
+ index++;
+ } else {
+ children[index++] = child;
}
- children.add(index, child);
-
child.setParent(this);
}
public void removeChild(TreeObject child) {
- children.remove(child);
+ for(int i=0; i<children.length; i++) {
+ if (children[i] == child) {
+ children[i] = null;
+ break;
+ }
+ }
child.setParent(null);
}
- public TreeObject [] getChildren() {
- return (TreeObject [])children.toArray(new TreeObject[children.size()]);
- }
- public boolean hasChildren() {
- return children.size()>0;
+
+ public TreeObject[] getChildren(boolean cleanupElements) {
+ if (cleanupElements) {
+ return getChildren();
+ } else {
+ return children;
+ }
}
-
- /**
- * Returns the TreeParent whose IASTNode is the parent of the IASTNode.
- *
- * @param trees
- * @param node
- * @return
- */
- private TreeParent findTreeParentForNode(TreeObject[] trees, IASTNode node) {
- for (int i=0; i<trees.length; i++) {
-
- if (trees[i] != null && trees[i] instanceof TreeParent) {
- if ( ((TreeParent)trees[i]).getNode() == node.getParent() ) {
- return (TreeParent)trees[i];
- } else if ( ((TreeParent)trees[i]).hasChildren() ){
- TreeParent tree = findTreeParentForNode( ((TreeParent)trees[i]).getChildren(), node );
- if (tree != null) return tree;
+
+ public TreeObject [] getChildren() {
+ // remove null children from the array (if not already done so)
+ if (!cleanupedElements) {
+ // remove null elements
+ children = (TreeObject[])ArrayUtil.removeNulls(TreeObject.class, children);
+
+ // sort the elements
+ Arrays.sort(children, new Comparator() {
+ public int compare(Object a, Object b) {
+ if(a instanceof TreeObject && b instanceof TreeObject &&
+ ((TreeObject)a).getNode() instanceof ASTNode &&
+ ((TreeObject)b).getNode() instanceof ASTNode) {
+ return ((ASTNode)((TreeObject)a).getNode()).getOffset() - ((ASTNode)((TreeObject)b).getNode()).getOffset();
+ }
+
+ return 0;
+ }
+ });
+
+ // need to also clean up the children's children, to make sure all nulls are removed (prevent expansion sign when there isn't one)
+ for(int i=0; i<children.length; i++) {
+ if (children[i] instanceof TreeParent) {
+ ((TreeParent)children[i]).setChildren((TreeObject[])ArrayUtil.removeNulls(TreeObject.class, ((TreeParent)children[i]).getChildren()));
}
}
+
+ cleanupedElements = true;
}
- return null; // nothing found
+ return children;
}
-
+ public boolean hasChildren() {
+ return children.length>0;
+ }
+
/**
* Returns the TreeParent whose IASTNode is the parent of the IASTNode.
*
@@ -94,15 +116,43 @@
public TreeParent findTreeParentForNode(IASTNode node) {
if (node == null || node.getParent() == null) return null;
- Iterator itr = children.iterator();
- while (itr.hasNext()) {
- Object o = itr.next();
- if (o != null && o instanceof TreeParent) {
- if ( ((TreeParent)o).getNode() == node.getParent() ) {
- return (TreeParent)o;
- } else if ( ((TreeParent)o).hasChildren() ){
- TreeParent tree = findTreeParentForNode( ((TreeParent)o).getChildren(), node );
- if (tree != null) return tree;
+ IASTNode parentToFind = node.getParent();
+
+ // first check this node before checking children
+ if (this.getNode() == parentToFind) {
+ return this;
+ }
+
+ // build the chain of nodes... and use it to search the tree for the TreeParent that owns the node's parent
+ IASTNode[] nodeChain = new IASTNode[DEFAULT_NODE_CHAIN_SIZE];
+ IASTNode topNode = node.getParent();
+ ArrayUtil.append(IASTNode.class, nodeChain, node);
+ nodeChain = (IASTNode[])ArrayUtil.append(IASTNode.class, nodeChain, topNode);
+ while(topNode.getParent() != null && !(topNode.getParent() instanceof IASTTranslationUnit)) {
+ topNode = topNode.getParent();
+ nodeChain = (IASTNode[])ArrayUtil.append(IASTNode.class, nodeChain, topNode);
+ }
+
+ // loop through the chain of nodes and use it to only search the necessary children required to find the node
+ TreeObject[] childrenToSearch = children;
+ int j=getStartSearch();
+ outerLoop: for(int i=nodeChain.length-1; i>=0; i--) {
+ if (nodeChain[i] != null) {
+ parentToFind = nodeChain[i];
+
+ for(; j>=0; j--) { // use the TreeParent's index to start searching at the end of it's children (performance optimization)
+ if (j<childrenToSearch.length && childrenToSearch[j] instanceof TreeParent) {
+ if ( childrenToSearch[j].getNode() == node.getParent() ) {
+ return (TreeParent)childrenToSearch[j];
+ }
+
+ if (childrenToSearch[j].getNode() == parentToFind) {
+ int pos = j;
+ j = ((TreeParent)childrenToSearch[pos]).getStartSearch();
+ childrenToSearch = ((TreeParent)childrenToSearch[pos]).getChildren(false);
+ continue outerLoop;
+ }
+ }
}
}
}
@@ -124,77 +174,71 @@
* Returns the TreeParent that corresponds to the IASTNode. This is the TreeParent
* that represents the IASTNode in the DOM AST View.
*
- * @param trees
- * @param node
- * @return
- */
- private TreeParent findTreeObject(TreeObject[] trees, IASTNode node, boolean useOffset, boolean useName) {
- for (int i=0; i<trees.length; i++) {
-
- if (trees[i] != null && trees[i] instanceof TreeParent) {
- if ( equalNodes( ((TreeParent)trees[i]).getNode(), node, useOffset, useName ) ) {
- return (TreeParent)trees[i];
- } else if ( ((TreeParent)trees[i]).hasChildren() ){
- TreeParent tree = findTreeObject( ((TreeParent)trees[i]).getChildren(), node, useOffset, useName );
- if (tree != null) return tree;
- }
- }
- }
-
- return null; // nothing found
- }
-
- /**
- * Returns the TreeParent that corresponds to the IASTNode. This is the TreeParent
- * that represents the IASTNode in the DOM AST View.
- *
* @param node
* @return
*/
public TreeParent findTreeObject(IASTNode node, boolean useOffset) {
- return findTreeObject(node, useOffset, false);
- }
-
- /**
- * Returns the TreeParent that corresponds to the IASTNode. This is the TreeParent
- * that represents the IASTNode in the DOM AST View.
- *
- * @param node
- * @return
- */
- public TreeParent findTreeObject(IASTNode node, boolean useOffset, boolean useName) {
if (node == null) return null;
- Iterator itr = children.iterator();
- while (itr.hasNext()) {
- Object o = itr.next();
- if (o != null && o instanceof TreeParent) {
- IASTNode treeNode = ((TreeParent)o).getNode();
-
- if (equalNodes(node, ((TreeParent)o).getNode(), useOffset, useName))
- return (TreeParent)o;
+ IASTNode nodeToFind = node;
+
+ // first check this node before checking children
+ if (equalNodes(node, this.getNode(), useOffset)) {
+ return this;
+ }
+
+ // build the chain of nodes... and use it to search the tree for the TreeParent that contains the node
+ IASTNode[] nodeChain = new IASTNode[DEFAULT_NODE_CHAIN_SIZE];
+ IASTNode topNode = node;
+ nodeChain = (IASTNode[])ArrayUtil.append(IASTNode.class, nodeChain, topNode);
+ while(topNode.getParent() != null && !(topNode.getParent() instanceof IASTTranslationUnit)) {
+ topNode = topNode.getParent();
+ nodeChain = (IASTNode[])ArrayUtil.append(IASTNode.class, nodeChain, topNode);
+ }
+
+ // loop through the chain of nodes and use it to only search the necessary children required to find the node
+ TreeObject[] childrenToSearch = children;
+ outerLoop: for(int i=nodeChain.length-1; i>=0; i--) {
+ if (nodeChain[i] != null) {
+ nodeToFind = nodeChain[i];
- // search the children
- if ( ((TreeParent)o).hasChildren() ){
- TreeParent tree = findTreeObject( ((TreeParent)o).getChildren(), node, useOffset, useName );
- if (tree != null) return tree;
+ for(int j=0; j<childrenToSearch.length; j++) {
+ if (childrenToSearch[j] instanceof TreeParent) {
+
+ if ( equalNodes(childrenToSearch[j].getNode(), node, useOffset) ) {
+ return (TreeParent)childrenToSearch[j];
+ }
+
+ if ( equalNodes(childrenToSearch[j].getNode(), nodeToFind, useOffset) ) {
+ childrenToSearch = ((TreeParent)childrenToSearch[j]).getChildren(false);
+ continue outerLoop;
+ }
+
+ // since the nodeChain doesn't include #includes, if an #include is encountered then search it's children
+ if (childrenToSearch[j].getNode() instanceof IASTPreprocessorIncludeStatement) {
+ TreeParent foundParentInInclude = ((TreeParent)childrenToSearch[j]).findTreeObject(node, useOffset);
+ if(foundParentInInclude != null) {
+ return foundParentInInclude;
+ }
+ }
+ }
}
}
}
return null; // nothing found
}
-
- private boolean equalNodes(IASTNode node1, IASTNode node2, boolean useOffset, boolean useName) {
- if (useName &&
- (!(node1 instanceof IASTName) || !(node2 instanceof IASTName) ||
- !(((IASTName)node1).toString().equals(((IASTName)node2).toString())))) return false;
-
+
+ private boolean equalNodes(IASTNode node1, IASTNode node2, boolean useOffset) {
if (useOffset) {
if (node1 instanceof ASTNode && node2 instanceof ASTNode) {
if (((ASTNode)node1).getOffset() == ((ASTNode)node2).getOffset() &&
- ((ASTNode)node1).getLength() == ((ASTNode)node2).getLength())
- return true;
+ ((ASTNode)node1).getLength() == ((ASTNode)node2).getLength()) {
+ if (node1.getClass().equals(node2.getClass()))
+ return true;
+ else
+ return false;
+ }
} else {
IASTNodeLocation[] locs1 = node1.getNodeLocations();
IASTNodeLocation[] locs2 = node2.getNodeLocations();
@@ -204,7 +248,10 @@
return false;
}
- return true;
+ if (node1.getClass().equals(node2.getClass()))
+ return true;
+ else
+ return false;
}
} else {
if ( node1 == node2 )
@@ -212,6 +259,10 @@
}
return false;
+ }
+
+ public void setChildren(TreeObject[] children) {
+ this.children = children;
}
}
