Bug 294969: Stack overflow with deeply nested binary expressions.

5 files changed, 199 insertions, 54 deletions

diff --git a/core/org.eclipse.cdt.core.tests/parser/org/eclipse/cdt/core/parser/tests/ast2/AST2Tests.java b/core/org.eclipse.cdt.core.tests/parser/org/eclipse/cdt/core/parser/tests/ast2/AST2Tests.java
index a4409097aca..e8c9b3218f2 100644
--- a/core/org.eclipse.cdt.core.tests/parser/org/eclipse/cdt/core/parser/tests/ast2/AST2Tests.java
+++ b/core/org.eclipse.cdt.core.tests/parser/org/eclipse/cdt/core/parser/tests/ast2/AST2Tests.java
@@ -1,5 +1,5 @@
 /*******************************************************************************
- * Copyright (c) 2004, 2009 IBM Corporation and others.
+ * Copyright (c) 2004, 2010 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
@@ -7208,4 +7208,17 @@ public class AST2Tests extends AST2BaseTest {
         final String code = getAboveComment();
 		parseAndCheckBindings(code, ParserLanguage.C, false, true);
 	}
+	
+	public void testDeepBinaryExpression_294969() throws Exception {
+		sValidateCopy= false;
+		StringBuilder buf= new StringBuilder("void f() {0");
+		for (int i = 0; i < 150000; i++) {
+			buf.append('+').append(i);
+		}
+		buf.append(";}");
+		String code= buf.toString();
+	    for(ParserLanguage lang : ParserLanguage.values()) {
+			IASTTranslationUnit tu = parseAndCheckBindings(code, lang);
+	    }
+	}
 }
diff --git a/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/ASTNode.java b/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/ASTNode.java
index 4ae8d8d3e12..41f3fb565c2 100644
--- a/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/ASTNode.java
+++ b/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/ASTNode.java
@@ -1,5 +1,5 @@
 /*******************************************************************************
- * Copyright (c) 2005, 2009 IBM Corporation and others.
+ * Copyright (c) 2005, 2010 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
@@ -63,13 +63,8 @@ public abstract class ASTNode implements IASTNode {
 		return active;
 	}
 	
-	public void freeze() {
+	void setIsFrozen() {
 		frozen = true;
-		for(IASTNode child : getChildren()) {
-			if(child != null) {
-				((ASTNode)child).freeze();
-			}
-		}
 	}
 	
 	public void setInactive() {
diff --git a/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/ASTTranslationUnit.java b/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/ASTTranslationUnit.java
index 5dd2bcb0472..54f51d54750 100644
--- a/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/ASTTranslationUnit.java
+++ b/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/ASTTranslationUnit.java
@@ -1,5 +1,5 @@
 /*******************************************************************************
- * Copyright (c) 2008, 2009 Wind River Systems, Inc. and others.
+ * Copyright (c) 2008, 2010 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
@@ -14,6 +14,7 @@ import java.util.List;
 
 import org.eclipse.cdt.core.CCorePlugin;
 import org.eclipse.cdt.core.dom.IName;
+import org.eclipse.cdt.core.dom.ast.ASTGenericVisitor;
 import org.eclipse.cdt.core.dom.ast.ASTVisitor;
 import org.eclipse.cdt.core.dom.ast.IASTComment;
 import org.eclipse.cdt.core.dom.ast.IASTDeclaration;
@@ -383,4 +384,14 @@ public abstract class ASTTranslationUnit extends ASTNode implements IASTTranslat
 		
 		copy.setOffsetAndLength(this);
 	}
+	
+	public final void freeze() {
+		accept(new ASTGenericVisitor(true) {
+			@Override
+			protected int genericVisit(IASTNode node) {
+				((ASTNode) node).setIsFrozen();
+				return PROCESS_CONTINUE;
+			}
+		});
+	}
 }
diff --git a/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/c/CASTBinaryExpression.java b/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/c/CASTBinaryExpression.java
index 8d926304649..9216dada5fd 100644
--- a/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/c/CASTBinaryExpression.java
+++ b/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/c/CASTBinaryExpression.java
@@ -1,5 +1,5 @@
 /*******************************************************************************
- * Copyright (c) 2005, 2009 IBM Corporation and others.
+ * Copyright (c) 2005, 2010 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
@@ -90,6 +90,10 @@ public class CASTBinaryExpression extends ASTNode implements
 
     @Override
 	public boolean accept( ASTVisitor action ){
+    	if (operand1 instanceof IASTBinaryExpression || operand2 instanceof IASTBinaryExpression) {
+    		return acceptWithoutRecursion(this, action);
+    	}
+    	
         if( action.shouldVisitExpressions ){
 		    switch( action.visit( this ) ){
 	            case ASTVisitor.PROCESS_ABORT : return false;
@@ -98,18 +102,75 @@ public class CASTBinaryExpression extends ASTNode implements
 	        }
 		}
         
-        if( operand1 != null ) if( !operand1.accept( action ) ) return false;
-        if( operand2 != null ) if( !operand2.accept( action ) ) return false;
+		if (operand1 != null && !operand1.accept(action)) 
+			return false;
+		if (operand2 != null && !operand2.accept(action)) 
+			return false;
         
-        if(action.shouldVisitExpressions ){
-        	switch( action.leave( this ) ){
-        		case ASTVisitor.PROCESS_ABORT : return false;
-        		case ASTVisitor.PROCESS_SKIP  : return true;
-        		default : break;
-        	}
-        }
-        return true;
+		if (action.shouldVisitExpressions && action.leave(this) == ASTVisitor.PROCESS_ABORT) 
+			return false;
+
+		return true;
     }
+
+	private static class N {
+		final IASTBinaryExpression fExpression;
+		int fState;
+		N fNext;
+
+		N(IASTBinaryExpression expr) {
+			fExpression = expr;
+		}
+	}
+	
+	public static boolean acceptWithoutRecursion(IASTBinaryExpression bexpr, ASTVisitor action) {
+		N stack= new N(bexpr);
+		while(stack != null) {
+			IASTBinaryExpression expr= stack.fExpression;
+			if (stack.fState == 0) {
+				if (action.shouldVisitExpressions) {
+					switch (action.visit(expr)) {
+					case ASTVisitor.PROCESS_ABORT : 
+						return false;
+					case ASTVisitor.PROCESS_SKIP: 
+						stack= stack.fNext;
+						continue;
+					}
+				}
+				stack.fState= 1;
+				IASTExpression op1 = expr.getOperand1();
+				if (op1 instanceof IASTBinaryExpression) {
+					N n= new N((IASTBinaryExpression) op1);
+					n.fNext= stack;
+					stack= n;
+					continue;
+				}
+				if (op1 != null && !op1.accept(action)) 
+					return false;
+			}
+			if (stack.fState == 1) {
+				stack.fState= 2;
+		        
+				IASTExpression op2 = expr.getOperand2();
+				if (op2 instanceof IASTBinaryExpression) {
+					N n= new N((IASTBinaryExpression) op2);
+					n.fNext= stack;
+					stack= n;
+					continue;
+				} 
+				if (op2 != null && !op2.accept(action)) 
+					return false;
+			}
+			
+			if (action.shouldVisitExpressions && action.leave(expr) == ASTVisitor.PROCESS_ABORT) 
+				return false;
+		
+			stack= stack.fNext;
+		}
+		
+		return true;
+	}
+
     
     public void replace(IASTNode child, IASTNode other) {
         if( child == operand1 )
diff --git a/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/cpp/CPPASTBinaryExpression.java b/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/cpp/CPPASTBinaryExpression.java
index 19ae917afc9..dee8ac63cc1 100644
--- a/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/cpp/CPPASTBinaryExpression.java
+++ b/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/cpp/CPPASTBinaryExpression.java
@@ -1,5 +1,5 @@
 /*******************************************************************************
- * Copyright (c) 2004, 2009 IBM Corporation and others.
+ * Copyright (c) 2004, 2010 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
@@ -17,6 +17,7 @@ import org.eclipse.cdt.core.dom.ast.DOMException;
 import org.eclipse.cdt.core.dom.ast.IASTBinaryExpression;
 import org.eclipse.cdt.core.dom.ast.IASTExpression;
 import org.eclipse.cdt.core.dom.ast.IASTImplicitName;
+import org.eclipse.cdt.core.dom.ast.IASTImplicitNameOwner;
 import org.eclipse.cdt.core.dom.ast.IASTNode;
 import org.eclipse.cdt.core.dom.ast.IPointerType;
 import org.eclipse.cdt.core.dom.ast.IProblemBinding;
@@ -112,52 +113,116 @@ public class CPPASTBinaryExpression extends ASTNode implements ICPPASTBinaryExpr
 	}
 
 	
-	
     @Override
-	public boolean accept( ASTVisitor action ){
-        if( action.shouldVisitExpressions ){
-		    switch( action.visit( this ) ){
+	public boolean accept(ASTVisitor action) {
+    	if (operand1 instanceof IASTBinaryExpression || operand2 instanceof IASTBinaryExpression) {
+    		return acceptWithoutRecursion(this, action);
+    	}
+    	
+		if (action.shouldVisitExpressions) {
+			switch (action.visit(this)) {
 	            case ASTVisitor.PROCESS_ABORT : return false;
 	            case ASTVisitor.PROCESS_SKIP  : return true;
 	            default : break;
 	        }
 		}
         
-        if( operand1 != null ) if( !operand1.accept( action ) ) return false;
+		if (operand1 != null && !operand1.accept(action))
+			return false;
         
-        if(action.shouldVisitImplicitNames) { 
-        	for(IASTImplicitName name : getImplicitNames()) {
-        		if(!name.accept(action)) return false;
-        	}
-        }
+		if (action.shouldVisitImplicitNames) {
+			for (IASTImplicitName name : getImplicitNames()) {
+				if (!name.accept(action))
+					return false;
+			}
+		}
         
-        if( operand2 != null ) if( !operand2.accept( action ) ) return false;
+		if (operand2 != null && !operand2.accept(action))
+			return false;
         
-        if(action.shouldVisitExpressions ){
-        	switch( action.leave( this ) ){
-        		case ASTVisitor.PROCESS_ABORT : return false;
-        		case ASTVisitor.PROCESS_SKIP  : return true;
-        		default : break;
-        	}
-        }
-        return true;
-    }
+		
+		if (action.shouldVisitExpressions && action.leave(this) == ASTVisitor.PROCESS_ABORT)
+			return false;
 
-    public void replace(IASTNode child, IASTNode other) {
-        if( child == operand1 )
-        {
-            other.setPropertyInParent( child.getPropertyInParent() );
-            other.setParent( child.getParent() );
-            operand1  = (IASTExpression) other;
-        }
-        if( child == operand2 )
-        {
-            other.setPropertyInParent( child.getPropertyInParent() );
-            other.setParent( child.getParent() );
-            operand2  = (IASTExpression) other;
-        }
+		return true;
     }
 
+	private static class N {
+		final IASTBinaryExpression fExpression;
+		int fState;
+		N fNext;
+
+		N(IASTBinaryExpression expr) {
+			fExpression = expr;
+		}
+	}
+	
+	public static boolean acceptWithoutRecursion(IASTBinaryExpression bexpr, ASTVisitor action) {
+		N stack= new N(bexpr);
+		while(stack != null) {
+			IASTBinaryExpression expr= stack.fExpression;
+			if (stack.fState == 0) {
+				if (action.shouldVisitExpressions) {
+					switch (action.visit(expr)) {
+					case ASTVisitor.PROCESS_ABORT : 
+						return false;
+					case ASTVisitor.PROCESS_SKIP: 
+						stack= stack.fNext;
+						continue;
+					}
+				}
+				stack.fState= 1;
+				IASTExpression op1 = expr.getOperand1();
+				if (op1 instanceof IASTBinaryExpression) {
+					N n= new N((IASTBinaryExpression) op1);
+					n.fNext= stack;
+					stack= n;
+					continue;
+				}
+				if (op1 != null && !op1.accept(action)) 
+					return false;
+			}
+			if (stack.fState == 1) {
+				if (action.shouldVisitImplicitNames) {
+					for (IASTImplicitName name : ((IASTImplicitNameOwner) expr).getImplicitNames()) {
+		        		if(!name.accept(action)) return false;
+		        	}
+		        }
+				stack.fState= 2;
+		        
+				IASTExpression op2 = expr.getOperand2();
+				if (op2 instanceof IASTBinaryExpression) {
+					N n= new N((IASTBinaryExpression) op2);
+					n.fNext= stack;
+					stack= n;
+					continue;
+				} 
+				if (op2 != null && !op2.accept(action)) 
+					return false;
+			}
+			
+			if (action.shouldVisitExpressions && action.leave(expr) == ASTVisitor.PROCESS_ABORT) 
+				return false;
+		
+			stack= stack.fNext;
+		}
+		
+		return true;
+	}
+
+	public void replace(IASTNode child, IASTNode other) {
+		if (child == operand1) {
+			other.setPropertyInParent(child.getPropertyInParent());
+			other.setParent(child.getParent());
+			operand1 = (IASTExpression) other;
+		}
+		if (child == operand2) {
+			other.setPropertyInParent(child.getPropertyInParent());
+			other.setParent(child.getParent());
+			operand2 = (IASTExpression) other;
+		}
+	}
+
     public IType getExpressionType() {
     	if (type == null) {
     		type= createExpressionType();