From 18360ea0c9cd1fce259ba7cf6824b48736334c4f Mon Sep 17 00:00:00 2001 From: Elliott Baron Date: Mon, 5 Oct 2009 20:48:19 -0400 Subject: Initial implementation of intra-procedural property simulation. * org.eclipse.cdt.codan.extension/plugin.xml: Moved checker to new package. * org.eclipse.cdt.codan.extension/src/org/eclipse/cdt/codan/extension/CloseOpenedFilesChecker.java: Moved. * org.eclipse.cdt.codan.extension/src/org/eclipse/cdt/codan/extension/ExecutionState.java: New file. * org.eclipse.cdt.codan.extension/src/org/eclipse/cdt/codan/extension/PropertyState.java: New file. * org.eclipse.cdt.codan.extension/src/org/eclipse/cdt/codan/extension/SymbolicState.java: New file. * org.eclipse.cdt.codan.extension/src/org/eclipse/cdt/codan/extension/checkers/FunctionNameParser.java: New file. * org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/IBlock.java: Added edge support. * org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/IControlFlowEdge.java: Store CFG edges. * org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/IControlFlowGraph.java: Added getEdges. * org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/Block.java: Store CFG edges. * org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/ControlFlowEdge.java: New file. * org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/ControlFlowGraph.java: Compute CFG edges. --- org.eclipse.cdt.codan.extension/plugin.xml | 2 +- .../org/eclipse/cdt/codan/extension/Activator.java | 10 + .../codan/extension/CloseOpenedFilesChecker.java | 157 ---- .../cdt/codan/extension/ExecutionState.java | 61 ++ .../eclipse/cdt/codan/extension/PropertyState.java | 19 + .../eclipse/cdt/codan/extension/SymbolicState.java | 40 + .../checkers/CloseOpenedFilesChecker.java | 410 ++++++++++ .../extension/checkers/FunctionNameParser.java | 61 ++ .../ptp/pldt/mpi/analysis/cdt/graphs/IBlock.java | 9 + .../mpi/analysis/cdt/graphs/IControlFlowEdge.java | 28 + .../mpi/analysis/cdt/graphs/IControlFlowGraph.java | 10 + .../pldt/mpi/analysis/cdt/graphs/impl/Block.java | 24 +- .../analysis/cdt/graphs/impl/ControlFlowEdge.java | 39 + .../analysis/cdt/graphs/impl/ControlFlowGraph.java | 840 +++++++++++---------- 14 files changed, 1141 insertions(+), 569 deletions(-) delete mode 100644 org.eclipse.cdt.codan.extension/src/org/eclipse/cdt/codan/extension/CloseOpenedFilesChecker.java create mode 100644 org.eclipse.cdt.codan.extension/src/org/eclipse/cdt/codan/extension/ExecutionState.java create mode 100644 org.eclipse.cdt.codan.extension/src/org/eclipse/cdt/codan/extension/PropertyState.java create mode 100644 org.eclipse.cdt.codan.extension/src/org/eclipse/cdt/codan/extension/SymbolicState.java create mode 100644 org.eclipse.cdt.codan.extension/src/org/eclipse/cdt/codan/extension/checkers/CloseOpenedFilesChecker.java create mode 100644 org.eclipse.cdt.codan.extension/src/org/eclipse/cdt/codan/extension/checkers/FunctionNameParser.java create mode 100644 org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/IControlFlowEdge.java create mode 100644 org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/ControlFlowEdge.java diff --git a/org.eclipse.cdt.codan.extension/plugin.xml b/org.eclipse.cdt.codan.extension/plugin.xml index f0ae36c..829c8fd 100644 --- a/org.eclipse.cdt.codan.extension/plugin.xml +++ b/org.eclipse.cdt.codan.extension/plugin.xml @@ -4,7 +4,7 @@ 0) { - IProject proj = resources[0].getProject(); - - // Create call graph for project - ICallGraph cg = creator.createCallGraph(proj); - creator.computeCallGraph(cg); - - // Create control flow graph - ICallGraphNode cgRoot = cg.topEntry(); - IASTStatement fnBody = cgRoot.getFuncDef().getBody(); - IControlFlowGraph cfg = new ControlFlowGraph(fnBody); - cfg.buildCFG(); - cfg.print(); - - ast.accept(visitor); - } - } - - - private void reportProblem(IASTName closeFD) { - String message = MessageFormat.format("File descriptor \"{0}\" has not been opened", closeFD.toString()); - reportProblem(ERR_ID, closeFD, message); - } - - - class CloseOpenedFilesVisitor extends ASTVisitor { - - public static final String OPEN = "open"; - public static final String CLOSE = "close"; - - private List openedFDs; - - public CloseOpenedFilesVisitor() { - openedFDs = new ArrayList(); - shouldVisitExpressions = true; - } - - @Override - public int visit(IASTExpression expression) { - if (expression instanceof IASTFunctionCallExpression) { - IASTFunctionCallExpression callExpression = (IASTFunctionCallExpression) expression; - IASTExpression funcName = callExpression.getFunctionNameExpression(); - if (funcName instanceof IASTIdExpression) { - IASTName name = ((IASTIdExpression) funcName).getName(); - String simpleName = String.valueOf(name.getSimpleID()); - if (simpleName.equals(OPEN)) { - IASTNode parent = callExpression.getParent(); - // Handle initialization in declaration - if (parent instanceof IASTInitializerExpression) { - parent = parent.getParent(); - if (parent instanceof IASTDeclarator) { - openedFDs.add(((IASTDeclarator) parent).getName()); - } - } - // Assignment after declaration - else if (parent instanceof IASTBinaryExpression) { - IASTExpression op2 = ((IASTBinaryExpression) parent).getOperand2(); - int operator = ((IASTBinaryExpression) parent).getOperator(); - if (callExpression.equals(op2) && operator == IASTBinaryExpression.op_assign) { - IASTExpression op1 = ((IASTBinaryExpression) parent).getOperand1(); - if (op1 instanceof IASTIdExpression) { - openedFDs.add(((IASTIdExpression) op1).getName()); - } - } - } - } - else if (simpleName.equals(CLOSE)) { - IASTExpression paramExpression = callExpression.getParameterExpression(); - if (paramExpression instanceof IASTIdExpression) { - IASTName fd = ((IASTIdExpression) paramExpression).getName(); - // Add only if no matching opened FD - boolean match = false; - for (int i = 0; !match && i < openedFDs.size(); i++) { - IASTName opened = openedFDs.get(i); - match = matchingFileDescriptors(fd, opened); - } - - if (!match) { - reportProblem(fd); - } - } - } - } - - return PROCESS_SKIP; - } - else { - return PROCESS_CONTINUE; - } - } - - private boolean matchingFileDescriptors(IASTName closeFD, IASTName openFD) { - // FIXME elaborate - IBinding closeBinding = closeFD.getBinding(); - IBinding openBinding = openFD.getBinding(); - - return openBinding != null && closeBinding != null && openBinding.equals(closeBinding); - } - } - -} diff --git a/org.eclipse.cdt.codan.extension/src/org/eclipse/cdt/codan/extension/ExecutionState.java b/org.eclipse.cdt.codan.extension/src/org/eclipse/cdt/codan/extension/ExecutionState.java new file mode 100644 index 0000000..ffefec7 --- /dev/null +++ b/org.eclipse.cdt.codan.extension/src/org/eclipse/cdt/codan/extension/ExecutionState.java @@ -0,0 +1,61 @@ +/******************************************************************************* + * Copyright (c) 2009 Elliott Baron + * 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: + * Elliott Baron - initial API and implementation + *******************************************************************************/ +package org.eclipse.cdt.codan.extension; + +import java.util.ArrayList; +import java.util.List; + +import org.eclipse.cdt.core.dom.ast.IASTNode; + +public class ExecutionState { + private List nodes; + private boolean top; + private boolean bottom; + + public ExecutionState() { + nodes = new ArrayList(); + } + + public void addClause(IASTNode node) { + setTop(false); + setBottom(false); + nodes.add(node); + } + + public void removeClause(IASTNode node) { + nodes.remove(node); + if (nodes.size() == 0) { + setTop(true); + setBottom(false); + } + } + + public IASTNode[] getClauses() { + return nodes.toArray(new IASTNode[nodes.size()]); + } + + public boolean isTop() { + return top; + } + + public boolean isBottom() { + return bottom; + } + + public void setTop(boolean top) { + this.top = top; + } + + public void setBottom(boolean bottom) { + this.bottom = bottom; + } + +} diff --git a/org.eclipse.cdt.codan.extension/src/org/eclipse/cdt/codan/extension/PropertyState.java b/org.eclipse.cdt.codan.extension/src/org/eclipse/cdt/codan/extension/PropertyState.java new file mode 100644 index 0000000..0b02211 --- /dev/null +++ b/org.eclipse.cdt.codan.extension/src/org/eclipse/cdt/codan/extension/PropertyState.java @@ -0,0 +1,19 @@ +/******************************************************************************* + * Copyright (c) 2009 Elliott Baron + * 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: + * Elliott Baron - initial API and implementation + *******************************************************************************/ +package org.eclipse.cdt.codan.extension; + +import org.eclipse.cdt.core.dom.ast.IASTStatement; + +public abstract class PropertyState { + + public abstract PropertyState transition(IASTStatement stmt); + +} diff --git a/org.eclipse.cdt.codan.extension/src/org/eclipse/cdt/codan/extension/SymbolicState.java b/org.eclipse.cdt.codan.extension/src/org/eclipse/cdt/codan/extension/SymbolicState.java new file mode 100644 index 0000000..0907ce5 --- /dev/null +++ b/org.eclipse.cdt.codan.extension/src/org/eclipse/cdt/codan/extension/SymbolicState.java @@ -0,0 +1,40 @@ +/******************************************************************************* + * Copyright (c) 2009 Elliott Baron + * 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: + * Elliott Baron - initial API and implementation + *******************************************************************************/ +package org.eclipse.cdt.codan.extension; + +import java.util.Collections; +import java.util.Set; + +public class SymbolicState { + private Set propertyStates; + private ExecutionState executionState; + + public SymbolicState(Set propertyStates, ExecutionState executionState) { + this.propertyStates = propertyStates; + this.executionState = executionState; + } + + public ExecutionState getExecutionState() { + return executionState; + } + + public void setExecutionState(ExecutionState es) { + executionState = es; + } + + public Set getPropertyStates() { + return Collections.unmodifiableSet(propertyStates); + } + + public void setPropertyStates(Set ps) { + propertyStates = ps; + } +} diff --git a/org.eclipse.cdt.codan.extension/src/org/eclipse/cdt/codan/extension/checkers/CloseOpenedFilesChecker.java b/org.eclipse.cdt.codan.extension/src/org/eclipse/cdt/codan/extension/checkers/CloseOpenedFilesChecker.java new file mode 100644 index 0000000..5ed04cc --- /dev/null +++ b/org.eclipse.cdt.codan.extension/src/org/eclipse/cdt/codan/extension/checkers/CloseOpenedFilesChecker.java @@ -0,0 +1,410 @@ +/******************************************************************************* + * Copyright (c) 2009 Elliott Baron + * 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: + * Elliott Baron - initial API and implementation + *******************************************************************************/ +package org.eclipse.cdt.codan.extension.checkers; + +import java.io.File; +import java.net.URI; +import java.text.MessageFormat; +import java.util.ArrayList; +import java.util.HashMap; +import java.util.HashSet; +import java.util.List; +import java.util.Map; +import java.util.Set; +import java.util.Stack; + +import org.eclipse.cdt.codan.core.model.AbstractIndexAstChecker; +import org.eclipse.cdt.codan.extension.Activator; +import org.eclipse.cdt.codan.extension.ExecutionState; +import org.eclipse.cdt.codan.extension.PropertyState; +import org.eclipse.cdt.codan.extension.SymbolicState; +import org.eclipse.cdt.core.dom.ast.ASTVisitor; +import org.eclipse.cdt.core.dom.ast.IASTBinaryExpression; +import org.eclipse.cdt.core.dom.ast.IASTDeclarator; +import org.eclipse.cdt.core.dom.ast.IASTExpression; +import org.eclipse.cdt.core.dom.ast.IASTExpressionStatement; +import org.eclipse.cdt.core.dom.ast.IASTFunctionCallExpression; +import org.eclipse.cdt.core.dom.ast.IASTIdExpression; +import org.eclipse.cdt.core.dom.ast.IASTInitializerExpression; +import org.eclipse.cdt.core.dom.ast.IASTName; +import org.eclipse.cdt.core.dom.ast.IASTNode; +import org.eclipse.cdt.core.dom.ast.IASTStatement; +import org.eclipse.cdt.core.dom.ast.IASTTranslationUnit; +import org.eclipse.cdt.core.dom.ast.IBinding; +import org.eclipse.core.resources.IProject; +import org.eclipse.core.resources.IResource; +import org.eclipse.core.resources.IWorkspaceRoot; +import org.eclipse.core.resources.ResourcesPlugin; +import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.GraphCreator; +import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.IBlock; +import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.ICallGraph; +import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.ICallGraphNode; +import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.IControlFlowEdge; +import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.IControlFlowGraph; +import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.impl.ControlFlowGraph; + +public class CloseOpenedFilesChecker extends AbstractIndexAstChecker { + private static final String ERR_ID = Activator.PLUGIN_ID + ".CloseOpenedFilesProblem"; + + private static final String OPEN = "open"; + private static final String CLOSE = "close"; + private Stack worklist; + + // Property simulation state info for CFG's edges + private Map> edgeInfo; + + // Property FSM states + private PropertyState uninit; + private PropertyState error; + private PropertyState opened; + + public CloseOpenedFilesChecker() { + worklist = new Stack(); + edgeInfo = new HashMap>(); + initFSM(); + } + + public void processAst(IASTTranslationUnit ast) { + // traverse the AST using the visitor pattern + CloseOpenedFilesVisitor visitor = new CloseOpenedFilesVisitor(); + + GraphCreator creator = new GraphCreator(); + + // Retrieve resource corresponding to this translation unit + String path = ast.getFilePath(); + URI fileURI = new File(path).toURI(); + IWorkspaceRoot wsRoot = ResourcesPlugin.getWorkspace().getRoot(); + IResource[] resources = wsRoot.findFilesForLocationURI(fileURI); + if (resources != null && resources.length > 0) { + IProject proj = resources[0].getProject(); + + // Create call graph for project + ICallGraph cg = creator.createCallGraph(proj); + creator.computeCallGraph(cg); + + // Create control flow graph + ICallGraphNode cgRoot = cg.topEntry(); + IASTStatement fnBody = cgRoot.getFuncDef().getBody(); + IControlFlowGraph cfg = new ControlFlowGraph(fnBody); + cfg.buildCFG(); + //cfg.print(); + + solve(cfg); + + // ast.accept(visitor); + } + } + + + private void solve(IControlFlowGraph cfg) { + for (IControlFlowEdge edge : cfg.getEdges()) { + IASTNode from = edge.getFrom().getContent(); + IASTNode to = edge.getTo().getContent(); + System.out.println((from != null ? from.getRawSignature() : from) + " -> " + (to != null ? to.getRawSignature() : to)); + + // Initialize edgeInfo for each edge + Set set = new HashSet(); + edgeInfo.put(edge, set); + } + + // Create edgeInfo for entry edge + IControlFlowEdge entryEdge = cfg.getEntry().getOutEdges()[0]; + Set symStates = edgeInfo.get(entryEdge); + Set propStates = new HashSet(); + propStates.add(uninit); + ExecutionState es = new ExecutionState(); + es.setTop(true); + symStates.add(new SymbolicState(propStates, es)); + + worklist.push(entryEdge.getTo()); + + while (!worklist.isEmpty()) { + IBlock blk = worklist.pop(); + if (isMerge(blk)) { + // Apply flow function for a merge block + Set newStates = flowMerge(blk, edgeInfo.get(blk.getInEdges()[0]), edgeInfo.get(blk.getInEdges()[1])); + add(blk.getOutEdges()[0], newStates); + } + else if (isBranch(blk)) { + // Apply flow function for a branch block + Set oldStates = edgeInfo.get(blk.getInEdges()[0]); + Set newStatesTrue = flowBranch(blk, oldStates, true); + Set newStatesFalse = flowBranch(blk, oldStates, false); + + // Assumes 0th out-edge is true branch, 1st out-edge is false branch + add(blk.getOutEdges()[0], newStatesTrue); + add(blk.getOutEdges()[1], newStatesFalse); + } + else { + // Apply flow function for a normal block + Set newStates = flowOther(blk, edgeInfo.get(blk.getInEdges()[0])); + printStates(newStates); + + // Don't process the null exit block + if (!blk.equals(cfg.getExit())) { + add(blk.getOutEdges()[0], newStates); + } + } + } + } + + + private void printStates(Set states) { + StringBuffer buf = new StringBuffer(); + for (SymbolicState s : states) { + buf.append("{"); + for (PropertyState ps : s.getPropertyStates()) { + buf.append("{"); + if (ps.equals(uninit)) { + buf.append("$u"); + } + else if (ps.equals(opened)) { + buf.append("o"); + } + else /* error */ { + buf.append("$e"); + } + buf.append(", "); + } + buf.replace(buf.length() - 2, buf.length(), "}, "); + if (s.getExecutionState().isTop()) { + buf.append("[TOP]"); + } + else if (s.getExecutionState().isBottom()) { + buf.append("[BOT]"); + } + else { + buf.append("["); + ExecutionState es = s.getExecutionState(); + IASTNode[] nodes = es.getClauses(); + for (IASTNode n : nodes) { + buf.append(n.getRawSignature()); + buf.append(" "); + } + buf.replace(buf.length() - 1, buf.length(), "]"); + } + buf.append("}"); + } + System.out.println(buf.toString()); + } + + private Set flowMerge(IBlock blk, Set ss1, + Set ss2) { + ss1.addAll(ss2); + return group(ss1); + } + + private Set flowBranch(IBlock blk, Set ss, boolean value) { + Set ret = new HashSet(); + for (SymbolicState s : ss) { + SymbolicState s0 = transferBranch(blk, s, value); + if (!s0.getExecutionState().isBottom()) { + ret.add(s0); + } + } + return group(ret); + } + + private Set flowOther(IBlock blk, Set ss) { + Set ret = new HashSet(); + for (SymbolicState s : ss) { + SymbolicState s0 = transferOther(blk, s); + ret.add(s0); + } + return group(ret); + } + + private Set group(Set ss) { + // FIXME Fully Path Sensitive + return ss; + } + + private SymbolicState transferBranch(IBlock blk, SymbolicState s, boolean value) { + // TODO Auto-generated method stub + return s; + } + + private SymbolicState transferOther(IBlock blk, SymbolicState s) { + IASTNode node = blk.getContent(); + + if (node instanceof IASTExpressionStatement) { + // Process property state transition + Set oldStates = s.getPropertyStates(); + Set newStates = new HashSet(); + for (PropertyState state : oldStates) { + newStates.add(state.transition((IASTStatement) node)); + } + s.setPropertyStates(newStates); + + // Check if we have an assignment statement + IASTExpression expr = ((IASTExpressionStatement) node).getExpression(); + if (expr instanceof IASTBinaryExpression) { + IASTBinaryExpression binExpr = (IASTBinaryExpression) expr; + int op = binExpr.getOperator(); + + // Check operator is an assignment operator + if (op >= IASTBinaryExpression.op_assign + && op <= IASTBinaryExpression.op_binaryOrAssign) { + IASTExpression o1 = binExpr.getOperand1(); + if (o1 instanceof IASTIdExpression) { + s.getExecutionState().addClause(((IASTIdExpression) o1).getName()); + } + } + } + } + return s; + } + + private void add(IControlFlowEdge edge, + Set ss) { + if (!edgeInfo.get(edge).equals(ss)) { + edgeInfo.put(edge, ss); + worklist.push(edge.getTo()); + } + } + + private void initFSM() { + uninit = new PropertyState() { + @Override + public PropertyState transition(IASTStatement stmt) { + PropertyState dest = uninit; + if (containsOpen(stmt)) { + dest = opened; + } + else if (containsClose(stmt)) { + dest = error; + } + return dest; + } + }; + + opened = new PropertyState() { + @Override + public PropertyState transition(IASTStatement stmt) { + PropertyState dest = opened; + if (containsOpen(stmt)) { + dest = error; + } + if (containsClose(stmt)) { + dest = uninit; + } + return dest; + } + }; + + error = new PropertyState() { + + @Override + public PropertyState transition(IASTStatement stmt) { + return error; + } + }; + } + + protected boolean containsOpen(IASTStatement stmt) { + // TODO Examine more than just name + FunctionNameParser parser = new FunctionNameParser(stmt, OPEN); + return parser.matches(); + } + + protected boolean containsClose(IASTStatement stmt) { + // TODO Examine more than just name + FunctionNameParser parser = new FunctionNameParser(stmt, CLOSE); + return parser.matches(); + } + + private boolean isBranch(IBlock blk) { + return blk.getOutEdges().length > 1; + } + + private boolean isMerge(IBlock blk) { + return blk.getInEdges().length > 1; + } + + private void reportProblem(IASTName closeFD) { + String message = MessageFormat.format("File descriptor \"{0}\" has not been opened", closeFD.toString()); + reportProblem(ERR_ID, closeFD, message); + } + + + class CloseOpenedFilesVisitor extends ASTVisitor { + + private List openedFDs; + + public CloseOpenedFilesVisitor() { + openedFDs = new ArrayList(); + shouldVisitExpressions = true; + } + + @Override + public int visit(IASTExpression expression) { + if (expression instanceof IASTFunctionCallExpression) { + IASTFunctionCallExpression callExpression = (IASTFunctionCallExpression) expression; + IASTExpression funcName = callExpression.getFunctionNameExpression(); + if (funcName instanceof IASTIdExpression) { + IASTName name = ((IASTIdExpression) funcName).getName(); + String simpleName = String.valueOf(name.getSimpleID()); + if (simpleName.equals(OPEN)) { + IASTNode parent = callExpression.getParent(); + // Handle initialization in declaration + if (parent instanceof IASTInitializerExpression) { + parent = parent.getParent(); + if (parent instanceof IASTDeclarator) { + openedFDs.add(((IASTDeclarator) parent).getName()); + } + } + // Assignment after declaration + else if (parent instanceof IASTBinaryExpression) { + IASTExpression op2 = ((IASTBinaryExpression) parent).getOperand2(); + int operator = ((IASTBinaryExpression) parent).getOperator(); + if (callExpression.equals(op2) && operator == IASTBinaryExpression.op_assign) { + IASTExpression op1 = ((IASTBinaryExpression) parent).getOperand1(); + if (op1 instanceof IASTIdExpression) { + openedFDs.add(((IASTIdExpression) op1).getName()); + } + } + } + } + else if (simpleName.equals(CLOSE)) { + IASTExpression paramExpression = callExpression.getParameterExpression(); + if (paramExpression instanceof IASTIdExpression) { + IASTName fd = ((IASTIdExpression) paramExpression).getName(); + // Add only if no matching opened FD + boolean match = false; + for (int i = 0; !match && i < openedFDs.size(); i++) { + IASTName opened = openedFDs.get(i); + match = matchingFileDescriptors(fd, opened); + } + + if (!match) { + reportProblem(fd); + } + } + } + } + + return PROCESS_SKIP; + } + else { + return PROCESS_CONTINUE; + } + } + + private boolean matchingFileDescriptors(IASTName closeFD, IASTName openFD) { + // FIXME elaborate + IBinding closeBinding = closeFD.getBinding(); + IBinding openBinding = openFD.getBinding(); + + return openBinding != null && closeBinding != null && openBinding.equals(closeBinding); + } + } + +} diff --git a/org.eclipse.cdt.codan.extension/src/org/eclipse/cdt/codan/extension/checkers/FunctionNameParser.java b/org.eclipse.cdt.codan.extension/src/org/eclipse/cdt/codan/extension/checkers/FunctionNameParser.java new file mode 100644 index 0000000..ae287f1 --- /dev/null +++ b/org.eclipse.cdt.codan.extension/src/org/eclipse/cdt/codan/extension/checkers/FunctionNameParser.java @@ -0,0 +1,61 @@ +/******************************************************************************* + * Copyright (c) 2009 Elliott Baron + * 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: + * Elliott Baron - initial API and implementation + *******************************************************************************/ +package org.eclipse.cdt.codan.extension.checkers; + +import org.eclipse.cdt.core.dom.ast.ASTVisitor; +import org.eclipse.cdt.core.dom.ast.IASTExpression; +import org.eclipse.cdt.core.dom.ast.IASTFunctionCallExpression; +import org.eclipse.cdt.core.dom.ast.IASTIdExpression; +import org.eclipse.cdt.core.dom.ast.IASTName; +import org.eclipse.cdt.core.dom.ast.IASTStatement; + +public class FunctionNameParser { + private IASTStatement stmt; + private String funcName; + + public FunctionNameParser(IASTStatement stmt, String funcName) { + this.stmt = stmt; + this.funcName = funcName; + } + + public boolean matches() { + FunctionNameVisitor visitor = new FunctionNameVisitor(); + stmt.accept(visitor); + return visitor.getResult(); + } + + private class FunctionNameVisitor extends ASTVisitor { + private boolean result; + + public FunctionNameVisitor() { + shouldVisitExpressions = true; + } + + @Override + public int visit(IASTExpression expr) { + if (expr instanceof IASTFunctionCallExpression) { + IASTFunctionCallExpression callExpression = (IASTFunctionCallExpression) expr; + IASTExpression funcName = callExpression.getFunctionNameExpression(); + if (funcName instanceof IASTIdExpression) { + IASTName name = ((IASTIdExpression) funcName).getName(); + result = name.toString().equals(FunctionNameParser.this.funcName); + return PROCESS_SKIP; + } + } + return PROCESS_CONTINUE; + } + + public boolean getResult() { + return result; + } + + } +} diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/IBlock.java b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/IBlock.java index f61b879..cc5ec77 100644 --- a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/IBlock.java +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/IBlock.java @@ -41,6 +41,15 @@ public interface IBlock { */ public List getPreds(); + + public IControlFlowEdge[] getInEdges(); + + public IControlFlowEdge[] getOutEdges(); + + public void addInEdge(IControlFlowEdge edge); + + public void addOutEdge(IControlFlowEdge edge); + /** * @return the next block in CFG according to the topological * order (top-down order) diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/IControlFlowEdge.java b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/IControlFlowEdge.java new file mode 100644 index 0000000..076f9c9 --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/IControlFlowEdge.java @@ -0,0 +1,28 @@ +/********************************************************************** + * Copyright (c) 2009 Elliott Baron. + * 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: + * Elliott Baron - initial API and implementation + *******************************************************************************/ +package org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs; + +/** + * An edge in the {@link IControlFlowGraph} between two {@link IBlock} objects. + */ +public interface IControlFlowEdge { + + /** + * @return the block for which this is an outgoing edge + */ + public abstract IBlock getFrom(); + + /** + * @return the block for which this is an incoming edge + */ + public abstract IBlock getTo(); + +} \ No newline at end of file diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/IControlFlowGraph.java b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/IControlFlowGraph.java index ecc4449..a817f1c 100644 --- a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/IControlFlowGraph.java +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/IControlFlowGraph.java @@ -60,4 +60,14 @@ public interface IControlFlowGraph { public void buildCFG(); public void print(); + + /** + * @return all of the blocks in this {@link IControlFlowGraph} + */ + public IBlock[] getBlocks(); + + /** + * @return all of the edges in this {@link IControlFlowGraph} + */ + public IControlFlowEdge[] getEdges(); } diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/Block.java b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/Block.java index db76c50..ccaaec2 100644 --- a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/Block.java +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/Block.java @@ -1,5 +1,5 @@ /********************************************************************** - * Copyright (c) 2007 IBM Corporation. + * Copyright (c) 2007, 2009 IBM Corporation. * 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 @@ -7,6 +7,7 @@ * * Contributors: * IBM Corporation - initial API and implementation + * Elliott Baron - fixed print issue *******************************************************************************/ package org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.impl; @@ -21,6 +22,7 @@ import org.eclipse.cdt.core.dom.ast.IASTName; import org.eclipse.cdt.core.dom.ast.IASTNode; import org.eclipse.cdt.core.dom.ast.IASTStatement; import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.IBlock; +import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.IControlFlowEdge; /** * @@ -30,6 +32,8 @@ import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.IBlock; public class Block implements IBlock { protected List succs_; protected List preds_; + protected List inEdges_; + protected List outEdges_; protected IBlock topNext_ = null; protected IBlock botNext_ = null; protected List DOM_ = null; @@ -105,6 +109,8 @@ public class Block implements IBlock { protected void blockInit(){ succs_ = new ArrayList(); preds_ = new ArrayList(); + inEdges_ = new ArrayList(); + outEdges_ = new ArrayList(); DOM_ = new ArrayList(); PDOM_ = new ArrayList(); attrs_ = new Hashtable(); @@ -193,6 +199,22 @@ public class Block implements IBlock { return succs_; } + public IControlFlowEdge[] getInEdges() { + return inEdges_.toArray(new IControlFlowEdge[inEdges_.size()]); + } + + public void addInEdge(IControlFlowEdge edge) { + inEdges_.add(edge); + } + + public IControlFlowEdge[] getOutEdges() { + return outEdges_.toArray(new IControlFlowEdge[outEdges_.size()]); + } + + public void addOutEdge(IControlFlowEdge edge) { + outEdges_.add(edge); + } + public List getDOM(){ return DOM_; } diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/ControlFlowEdge.java b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/ControlFlowEdge.java new file mode 100644 index 0000000..9364fe7 --- /dev/null +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/ControlFlowEdge.java @@ -0,0 +1,39 @@ +/********************************************************************** + * Copyright (c) 2009 Elliott Baron. + * 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: + * Elliott Baron - initial API and implementation + *******************************************************************************/ +package org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.impl; + +import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.IBlock; +import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.IControlFlowEdge; + +public class ControlFlowEdge implements IControlFlowEdge { + private IBlock from; + private IBlock to; + + public ControlFlowEdge(IBlock from, IBlock to) { + this.from = from; + this.to = to; + } + + /* (non-Javadoc) + * @see org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.IControlFlowEdge#getFrom() + */ + public IBlock getFrom() { + return from; + } + + /* (non-Javadoc) + * @see org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.IControlFlowEdge#getTo() + */ + public IBlock getTo() { + return to; + } + +} diff --git a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/ControlFlowGraph.java b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/ControlFlowGraph.java index 3ee0072..3fd7aae 100644 --- a/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/ControlFlowGraph.java +++ b/org.eclipse.ptp.pldt.mpi.analysis.cdt/src/org/eclipse/ptp/pldt/mpi/analysis/cdt/graphs/impl/ControlFlowGraph.java @@ -1,5 +1,5 @@ /********************************************************************** - * Copyright (c) 2007,2008 IBM Corporation. + * Copyright (c) 2007, 2009 IBM Corporation. * 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 @@ -7,6 +7,7 @@ * * Contributors: * IBM Corporation - initial API and implementation + * Elliott Baron - added use of ControlFlowEdge type *******************************************************************************/ package org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.impl; @@ -40,35 +41,38 @@ import org.eclipse.cdt.core.dom.ast.IASTStatement; import org.eclipse.cdt.core.dom.ast.IASTSwitchStatement; import org.eclipse.cdt.core.dom.ast.IASTWhileStatement; import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.IBlock; +import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.IControlFlowEdge; import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.IControlFlowGraph; /** * Control Flow Graph implementation * * @author Yuan Zhang - * + * */ public class ControlFlowGraph implements IControlFlowGraph { protected IASTStatement prog_; protected List BBs_; + protected List edges_; protected IBlock entry_; protected IBlock exit_; private static final boolean traceOn = false; - - public ControlFlowGraph(IASTStatement prog){ + + public ControlFlowGraph(IASTStatement prog) { this.prog_ = prog; BBs_ = new ArrayList(); + edges_ = new ArrayList(); } - /** Constructing a CFG consists of several steps: - * Step 1: collecting all blocks in a function - * Step 2: calculating control flows among blocks - * Step 3: calculating dominator and post-dominator relations - * Step 4: Sort all blocks according to the topological order - * Step 5: Other additional operations + /** + * Constructing a CFG consists of several steps: Step 1: collecting all + * blocks in a function Step 2: calculating control flows among blocks Step + * 3: calculating dominator and post-dominator relations Step 4: Sort all + * blocks according to the topological order Step 5: Other additional + * operations */ - public void buildCFG(){ + public void buildCFG() { collectBlocks(); setBlockFlow(); buildDOM(); @@ -76,614 +80,617 @@ public class ControlFlowGraph implements IControlFlowGraph { sort(); otherOPs(); } - + /** Collecting all blocks in a function */ - protected void collectBlocks(){ + protected void collectBlocks() { entry_ = new Block(); exit_ = new Block(); BasicBlockCollector bc = new BasicBlockCollector(); bc.run(); } - + /** Calculating control flows among blocks */ - protected void setBlockFlow(){ + protected void setBlockFlow() { FlowBuilder flowBuilder = new FlowBuilder(); flowBuilder.run(); } - - class BasicBlockCollector extends ASTVisitor{ - public void run(){ + class BasicBlockCollector extends ASTVisitor { + + public void run() { this.shouldVisitStatements = true; this.shouldVisitDeclarations = true; prog_.accept(this); } - - public int visit(IASTStatement stmt) - { + + public int visit(IASTStatement stmt) { IBlock block; - if(stmt instanceof IASTBreakStatement){ + if (stmt instanceof IASTBreakStatement) { block = new Block(stmt); addBlock(block); - } - else if(stmt instanceof IASTCaseStatement){ + } else if (stmt instanceof IASTCaseStatement) { block = new Block(stmt); addBlock(block); - } - else if(stmt instanceof IASTCompoundStatement){ - } - else if(stmt instanceof IASTContinueStatement){ + } else if (stmt instanceof IASTCompoundStatement) { + } else if (stmt instanceof IASTContinueStatement) { block = new Block(stmt); addBlock(block); - } - else if(stmt instanceof IASTDeclarationStatement){ + } else if (stmt instanceof IASTDeclarationStatement) { block = new Block(stmt); addBlock(block); - } - else if(stmt instanceof IASTDefaultStatement){ + } else if (stmt instanceof IASTDefaultStatement) { block = new Block(stmt); addBlock(block); - } - else if(stmt instanceof IASTDoStatement){ - IASTDoStatement doStmt = (IASTDoStatement)stmt; + } else if (stmt instanceof IASTDoStatement) { + IASTDoStatement doStmt = (IASTDoStatement) stmt; block = new Block(doStmt.getCondition(), stmt); addBlock(block); IBlock exitjoin = new Block(null, stmt, Block.exit_join_type); addBlock(exitjoin); - IBlock continuejoin = new Block(null, stmt, Block.continue_join_type); + IBlock continuejoin = new Block(null, stmt, + Block.continue_join_type); addBlock(continuejoin); - } - else if(stmt instanceof IASTExpressionStatement){ + } else if (stmt instanceof IASTExpressionStatement) { block = new Block(stmt); addBlock(block); - } - else if(stmt instanceof IASTForStatement){ - IASTForStatement forStmt = (IASTForStatement)stmt; + } else if (stmt instanceof IASTForStatement) { + IASTForStatement forStmt = (IASTForStatement) stmt; /* The initialization is a statement, and will be added later */ block = new Block(forStmt.getConditionExpression(), stmt); addBlock(block); - if(forStmt.getIterationExpression() != null){ + if (forStmt.getIterationExpression() != null) { block = new Block(forStmt.getIterationExpression(), stmt); addBlock(block); } - IBlock continuejoin = new Block(null, stmt, Block.continue_join_type); + IBlock continuejoin = new Block(null, stmt, + Block.continue_join_type); addBlock(continuejoin); IBlock exitjoin = new Block(null, stmt, Block.exit_join_type); addBlock(exitjoin); - } - else if(stmt instanceof IASTGotoStatement){ + } else if (stmt instanceof IASTGotoStatement) { block = new Block(stmt); addBlock(block); - } - else if(stmt instanceof IASTIfStatement){ - IASTIfStatement ifStmt = (IASTIfStatement)stmt; + } else if (stmt instanceof IASTIfStatement) { + IASTIfStatement ifStmt = (IASTIfStatement) stmt; block = new Block(ifStmt.getConditionExpression(), stmt); addBlock(block); IBlock join = new Block(null, stmt, Block.exit_join_type); addBlock(join); - } - else if(stmt instanceof IASTLabelStatement){ - IASTLabelStatement labelS = (IASTLabelStatement)stmt; + } else if (stmt instanceof IASTLabelStatement) { + IASTLabelStatement labelS = (IASTLabelStatement) stmt; block = new Block(labelS.getName(), stmt, Block.label_type); addBlock(block); - } - else if(stmt instanceof IASTNullStatement){ + } else if (stmt instanceof IASTNullStatement) { block = new Block(stmt); addBlock(block); - } - else if(stmt instanceof IASTProblemStatement){ + } else if (stmt instanceof IASTProblemStatement) { block = new Block(stmt); addBlock(block); - } - else if(stmt instanceof IASTReturnStatement){ - IASTReturnStatement rtStmt = (IASTReturnStatement)stmt; + } else if (stmt instanceof IASTReturnStatement) { + IASTReturnStatement rtStmt = (IASTReturnStatement) stmt; block = new Block(rtStmt.getReturnValue(), stmt); addBlock(block); - } - else if(stmt instanceof IASTSwitchStatement){ - IASTSwitchStatement swStmt = (IASTSwitchStatement)stmt; + } else if (stmt instanceof IASTSwitchStatement) { + IASTSwitchStatement swStmt = (IASTSwitchStatement) stmt; block = new Block(swStmt.getControllerExpression(), stmt); addBlock(block); IBlock join = new Block(null, stmt, Block.exit_join_type); addBlock(join); - } - else if(stmt instanceof IASTWhileStatement){ - IASTWhileStatement whStmt = (IASTWhileStatement)stmt; + } else if (stmt instanceof IASTWhileStatement) { + IASTWhileStatement whStmt = (IASTWhileStatement) stmt; block = new Block(whStmt.getCondition(), stmt); addBlock(block); IBlock join = new Block(null, stmt, Block.continue_join_type); addBlock(join); IBlock exitjoin = new Block(null, stmt, Block.exit_join_type); addBlock(exitjoin); - } + } return PROCESS_CONTINUE; } } - - public class FlowBuilder extends ASTVisitor{ + + public class FlowBuilder extends ASTVisitor { private boolean exitBlock = false; - - public void run(){ + + public void run() { this.shouldVisitStatements = true; this.shouldVisitDeclarations = true; this.shouldVisitTranslationUnit = true; this.shouldVisitExpressions = true; IBlock first = firstBlock(prog_); - ControlFlowEdge(entry_, first); + addControlFlowEdge(entry_, first); prog_.accept(this); } - - public int visit(IASTStatement stmt){ - if(stmt instanceof IASTBreakStatement){ + + public int visit(IASTStatement stmt) { + if (stmt instanceof IASTBreakStatement) { /** A break statement flows to a block with exit_join_type */ - if(traceOn) System.out.println("BreakStatement"); + if (traceOn) + System.out.println("BreakStatement"); IBlock block = getBlock(stmt); IASTNode parent = stmt.getParent(); - while(true){ - if(parent instanceof IASTDoStatement || - parent instanceof IASTForStatement || - parent instanceof IASTWhileStatement || - parent instanceof IASTSwitchStatement){ - IBlock exitjoin = getBlock(null, (IASTStatement)parent, - Block.exit_join_type); - ControlFlowEdge(block, exitjoin); + while (true) { + if (parent instanceof IASTDoStatement + || parent instanceof IASTForStatement + || parent instanceof IASTWhileStatement + || parent instanceof IASTSwitchStatement) { + IBlock exitjoin = getBlock(null, + (IASTStatement) parent, Block.exit_join_type); + addControlFlowEdge(block, exitjoin); break; - } - else{ + } else { parent = parent.getParent(); } } - } - else if(stmt instanceof IASTCaseStatement || - stmt instanceof IASTDefaultStatement){ - /** A case(default) statement flows from the switch - * condition block or the previous case statement, and - * flows to the first statement in the case(default) body. + } else if (stmt instanceof IASTCaseStatement + || stmt instanceof IASTDefaultStatement) { + /** + * A case(default) statement flows from the switch condition + * block or the previous case statement, and flows to the first + * statement in the case(default) body. */ - if(traceOn) System.out.println("CaseStatement / DefaultStatement"); + if (traceOn) + System.out.println("CaseStatement / DefaultStatement"); IASTNode parent = stmt.getParent(); - while(true){ - if(parent instanceof IASTSwitchStatement) break; - else parent = parent.getParent(); + while (true) { + if (parent instanceof IASTSwitchStatement) + break; + else + parent = parent.getParent(); } - IASTSwitchStatement swStmt = (IASTSwitchStatement)parent; - IBlock swblock = getBlock(swStmt.getControllerExpression(), - (IASTStatement)parent); + IASTSwitchStatement swStmt = (IASTSwitchStatement) parent; + IBlock swblock = getBlock(swStmt.getControllerExpression(), + (IASTStatement) parent); IBlock caseblock = getBlock(stmt); - ControlFlowEdge(swblock, caseblock); + addControlFlowEdge(swblock, caseblock); IBlock next = nextBlock(stmt); - ControlFlowEdge(caseblock, next); - } - else if(stmt instanceof IASTCompoundStatement){ - } - else if(stmt instanceof IASTContinueStatement){ + addControlFlowEdge(caseblock, next); + } else if (stmt instanceof IASTCompoundStatement) { + } else if (stmt instanceof IASTContinueStatement) { /** A continue statement flows to the continue_join_type block */ - if(traceOn) System.out.println("ContinueStatement"); + if (traceOn) + System.out.println("ContinueStatement"); IBlock block = getBlock(stmt); IASTNode parent = stmt.getParent(); - while(true){ - if(parent instanceof IASTDoStatement || - parent instanceof IASTForStatement || - parent instanceof IASTWhileStatement){ - IBlock continuejoin = getBlock(null, (IASTStatement)parent, + while (true) { + if (parent instanceof IASTDoStatement + || parent instanceof IASTForStatement + || parent instanceof IASTWhileStatement) { + IBlock continuejoin = getBlock(null, + (IASTStatement) parent, Block.continue_join_type); - ControlFlowEdge(block, continuejoin); + addControlFlowEdge(block, continuejoin); break; - } - else{ + } else { parent = parent.getParent(); } } - } - else if(stmt instanceof IASTDeclarationStatement){ - /** Except the regular variable declaration statements, the - * initializer of a for statement could also be a - * declaration statement. In the latter case, the flow - * relation is already calculated and therefore nothing - * is done here. */ - if(traceOn) System.out.println("DeclarationStatement"); + } else if (stmt instanceof IASTDeclarationStatement) { + /** + * Except the regular variable declaration statements, the + * initializer of a for statement could also be a declaration + * statement. In the latter case, the flow relation is already + * calculated and therefore nothing is done here. + */ + if (traceOn) + System.out.println("DeclarationStatement"); IASTNode parent = stmt.getParent(); - if(parent instanceof IASTForStatement){ - IASTForStatement forStmt = (IASTForStatement)parent; - if(forStmt.getInitializerStatement() == stmt) + if (parent instanceof IASTForStatement) { + IASTForStatement forStmt = (IASTForStatement) parent; + if (forStmt.getInitializerStatement() == stmt) return PROCESS_CONTINUE; } IBlock block = getBlock(stmt); IBlock next = nextBlock(stmt); - ControlFlowEdge(block, next); - } - else if(stmt instanceof IASTDoStatement){ - /** We calculate four types of control flows here: - * (1) the condition block flows to the first block of the loop body - * (2) the condition block flows to the exit_join_type block - * (3) the continue_join_type block flows to the condition block - * (4) the exit_join_type block flows to the next statement after - * this do loop + addControlFlowEdge(block, next); + } else if (stmt instanceof IASTDoStatement) { + /** + * We calculate four types of control flows here: (1) the + * condition block flows to the first block of the loop body (2) + * the condition block flows to the exit_join_type block (3) the + * continue_join_type block flows to the condition block (4) the + * exit_join_type block flows to the next statement after this + * do loop */ - if(traceOn) System.out.println("DoStatement"); - IASTDoStatement doStmt = (IASTDoStatement)stmt; + if (traceOn) + System.out.println("DoStatement"); + IASTDoStatement doStmt = (IASTDoStatement) stmt; IBlock cond = getBlock(doStmt.getCondition(), stmt); - if(doStmt.getBody() == null){ - ControlFlowEdge(cond, cond); + if (doStmt.getBody() == null) { + addControlFlowEdge(cond, cond); } else { IBlock first = firstBlock(doStmt.getBody()); - ControlFlowEdge(cond, first); - IBlock continuejoin = getBlock(null, stmt, Block.continue_join_type); - ControlFlowEdge(continuejoin, cond); + addControlFlowEdge(cond, first); + IBlock continuejoin = getBlock(null, stmt, + Block.continue_join_type); + addControlFlowEdge(continuejoin, cond); } IBlock exitjoin = getBlock(null, stmt, Block.exit_join_type); - ControlFlowEdge(cond, exitjoin); + addControlFlowEdge(cond, exitjoin); IBlock next = nextBlock(stmt); - ControlFlowEdge(exitjoin, next); - } - else if(stmt instanceof IASTExpressionStatement){ - /** If the expression statement is the initializer of a for - * loop, do nothing here. If this statement contains an - * "exit" function call, it flows to the exit block of the - * current function */ - if(traceOn) System.out.println("ExpressionSatement"); + addControlFlowEdge(exitjoin, next); + } else if (stmt instanceof IASTExpressionStatement) { + /** + * If the expression statement is the initializer of a for loop, + * do nothing here. If this statement contains an "exit" + * function call, it flows to the exit block of the current + * function + */ + if (traceOn) + System.out.println("ExpressionSatement"); IASTNode parent = stmt.getParent(); - if(parent instanceof IASTForStatement){ - IASTForStatement forStmt = (IASTForStatement)parent; - if(forStmt.getInitializerStatement() == stmt) + if (parent instanceof IASTForStatement) { + IASTForStatement forStmt = (IASTForStatement) parent; + if (forStmt.getInitializerStatement() == stmt) return PROCESS_CONTINUE; } IBlock block = getBlock(stmt); - IASTExpressionStatement exprStmt = (IASTExpressionStatement)stmt; + IASTExpressionStatement exprStmt = (IASTExpressionStatement) stmt; exitBlock = false; exprStmt.getExpression().accept(this); - if(exitBlock){ - ControlFlowEdge(block, exit_); - } - else { + if (exitBlock) { + addControlFlowEdge(block, exit_); + } else { IBlock next = nextBlock(stmt); - ControlFlowEdge(block, next); + addControlFlowEdge(block, next); } - } - else if(stmt instanceof IASTForStatement){ - /** In a for loop, the initializer flows to the loop condition, + } else if (stmt instanceof IASTForStatement) { + /** + * In a for loop, the initializer flows to the loop condition, * the loop condition flows to the first statement in the loop - * body and the block with exit_join_type. The continue_join_type - * block flows to the iterator, and the iterator flows to the - * condition block */ - if(traceOn) System.out.println("ForStatement"); - IASTForStatement forStmt = (IASTForStatement)stmt; + * body and the block with exit_join_type. The + * continue_join_type block flows to the iterator, and the + * iterator flows to the condition block + */ + if (traceOn) + System.out.println("ForStatement"); + IASTForStatement forStmt = (IASTForStatement) stmt; IASTStatement initStmt = forStmt.getInitializerStatement(); IBlock init = getBlock(initStmt); IBlock cond = getBlock(forStmt.getConditionExpression(), stmt); IBlock iter = null; - IBlock continuejoin = getBlock(null, stmt, Block.continue_join_type); + IBlock continuejoin = getBlock(null, stmt, + Block.continue_join_type); IBlock exitjoin = getBlock(null, stmt, Block.exit_join_type); - - if(forStmt.getIterationExpression() != null) + + if (forStmt.getIterationExpression() != null) iter = getBlock(forStmt.getIterationExpression(), stmt); - + /* The empty initialization will be a Null statement */ - ControlFlowEdge(init, cond); - - if(forStmt.getBody() != null){ + addControlFlowEdge(init, cond); + + if (forStmt.getBody() != null) { IBlock first = firstBlock(forStmt.getBody()); - ControlFlowEdge(cond, first); - if(iter != null){ - ControlFlowEdge(continuejoin, iter); - ControlFlowEdge(iter, cond); + addControlFlowEdge(cond, first); + if (iter != null) { + addControlFlowEdge(continuejoin, iter); + addControlFlowEdge(iter, cond); } else - ControlFlowEdge(continuejoin, cond); + addControlFlowEdge(continuejoin, cond); } else { - if(iter != null){ - ControlFlowEdge(cond, iter); - ControlFlowEdge(iter, cond); + if (iter != null) { + addControlFlowEdge(cond, iter); + addControlFlowEdge(iter, cond); } else { - ControlFlowEdge(cond, cond); + addControlFlowEdge(cond, cond); } - } - ControlFlowEdge(cond, exitjoin); + } + addControlFlowEdge(cond, exitjoin); IBlock next = nextBlock(stmt); - ControlFlowEdge(exitjoin, next); - } - else if(stmt instanceof IASTGotoStatement){ + addControlFlowEdge(exitjoin, next); + } else if (stmt instanceof IASTGotoStatement) { /** Goto statement flows to the corresponding label statement */ - if(traceOn) System.out.println("GotoStatement"); - IASTGotoStatement gotoStmt = (IASTGotoStatement)stmt; - IBlock label = getBlock(gotoStmt.getName(), gotoStmt, Block.label_type); - if(label == null){ + if (traceOn) + System.out.println("GotoStatement"); + IASTGotoStatement gotoStmt = (IASTGotoStatement) stmt; + IBlock label = getBlock(gotoStmt.getName(), gotoStmt, + Block.label_type); + if (label == null) { System.out.println("Null Label Error"); } IBlock block = getBlock(gotoStmt); - ControlFlowEdge(block, label); - } - else if(stmt instanceof IASTIfStatement){ - /** The if condition block flows to the first block of the + addControlFlowEdge(block, label); + } else if (stmt instanceof IASTIfStatement) { + /** + * The if condition block flows to the first block of the * then(else) clause if it is not empty, the exit_join_type - * block otherwise */ - if(traceOn) System.out.println("IfStatement"); - IASTIfStatement ifStmt = (IASTIfStatement)stmt; + * block otherwise + */ + if (traceOn) + System.out.println("IfStatement"); + IASTIfStatement ifStmt = (IASTIfStatement) stmt; IBlock condb = getBlock(ifStmt.getConditionExpression(), stmt); IBlock join = getBlock(null, stmt, Block.exit_join_type); - if(ifStmt.getThenClause() != null){ + if (ifStmt.getThenClause() != null) { IBlock thenb = firstBlock(ifStmt.getThenClause()); - ControlFlowEdge(condb, thenb); + addControlFlowEdge(condb, thenb); } else { - ControlFlowEdge(condb, join); + addControlFlowEdge(condb, join); } - - if(ifStmt.getElseClause() != null){ + + if (ifStmt.getElseClause() != null) { IBlock elseb = firstBlock(ifStmt.getElseClause()); - ControlFlowEdge(condb, elseb); + addControlFlowEdge(condb, elseb); } else { - ControlFlowEdge(condb, join); + addControlFlowEdge(condb, join); } IBlock next = nextBlock(stmt); - ControlFlowEdge(join, next); - } - else if(stmt instanceof IASTLabelStatement){ - /** If there is a nested statement, the label statement flows - * to the first block of the nested statement + addControlFlowEdge(join, next); + } else if (stmt instanceof IASTLabelStatement) { + /** + * If there is a nested statement, the label statement flows to + * the first block of the nested statement */ - if(traceOn) System.out.println("LabelStatement"); - IASTLabelStatement label = (IASTLabelStatement)stmt; + if (traceOn) + System.out.println("LabelStatement"); + IASTLabelStatement label = (IASTLabelStatement) stmt; IBlock block = getBlock(label.getName(), stmt, Block.label_type); - if(label.getNestedStatement() == null){ + if (label.getNestedStatement() == null) { IBlock next = nextBlock(stmt); - ControlFlowEdge(block, next); + addControlFlowEdge(block, next); } else { IBlock next = firstBlock(label.getNestedStatement()); - ControlFlowEdge(block, next); + addControlFlowEdge(block, next); } - } - else if(stmt instanceof IASTNullStatement){ - if(traceOn) System.out.println("NullStatement"); + } else if (stmt instanceof IASTNullStatement) { + if (traceOn) + System.out.println("NullStatement"); IASTNode parent = stmt.getParent(); - if(parent instanceof IASTForStatement){ - IASTForStatement forStmt = (IASTForStatement)parent; - if(forStmt.getInitializerStatement() == stmt) + if (parent instanceof IASTForStatement) { + IASTForStatement forStmt = (IASTForStatement) parent; + if (forStmt.getInitializerStatement() == stmt) return PROCESS_CONTINUE; } IBlock block = getBlock(stmt); IBlock next = nextBlock(stmt); - ControlFlowEdge(block, next); - } - else if(stmt instanceof IASTProblemStatement){ - if(traceOn) System.out.println("ProblemStatement"); + addControlFlowEdge(block, next); + } else if (stmt instanceof IASTProblemStatement) { + if (traceOn) + System.out.println("ProblemStatement"); IBlock block = getBlock(stmt); IBlock next = nextBlock(stmt); - ControlFlowEdge(block, next); - } - else if(stmt instanceof IASTReturnStatement){ + addControlFlowEdge(block, next); + } else if (stmt instanceof IASTReturnStatement) { /* The return statement flows to the exit block */ - if(traceOn) System.out.println("ReturnStatement"); - IASTReturnStatement rtStmt = (IASTReturnStatement)stmt; + if (traceOn) + System.out.println("ReturnStatement"); + IASTReturnStatement rtStmt = (IASTReturnStatement) stmt; IBlock rv = getBlock(rtStmt.getReturnValue(), stmt); - ControlFlowEdge(rv, exit_); - } - else if(stmt instanceof IASTSwitchStatement){ - /** The exit_join block of a switch statement flows to the - * first block of the next statement + addControlFlowEdge(rv, exit_); + } else if (stmt instanceof IASTSwitchStatement) { + /** + * The exit_join block of a switch statement flows to the first + * block of the next statement */ - if(traceOn) System.out.println("SwitchStatement"); + if (traceOn) + System.out.println("SwitchStatement"); IBlock join = getBlock(null, stmt, Block.exit_join_type); IBlock next = nextBlock(stmt); - ControlFlowEdge(join, next); - } - else if(stmt instanceof IASTWhileStatement){ - /** The condition block of a while loop flows to the first - * statement in the loop body and the exit_join block. - * The condition_join block flows to the condition block. + addControlFlowEdge(join, next); + } else if (stmt instanceof IASTWhileStatement) { + /** + * The condition block of a while loop flows to the first + * statement in the loop body and the exit_join block. The + * condition_join block flows to the condition block. */ - if(traceOn) System.out.println("WhileStatement"); - IASTWhileStatement whStmt = (IASTWhileStatement)stmt; + if (traceOn) + System.out.println("WhileStatement"); + IASTWhileStatement whStmt = (IASTWhileStatement) stmt; IBlock cond = getBlock(whStmt.getCondition(), stmt); - IBlock continuejoin = getBlock(null, stmt, Block.continue_join_type); + IBlock continuejoin = getBlock(null, stmt, + Block.continue_join_type); IBlock exitjoin = getBlock(null, stmt, Block.exit_join_type); - if(whStmt.getBody() == null){ - ControlFlowEdge(cond, cond); + if (whStmt.getBody() == null) { + addControlFlowEdge(cond, cond); } else { IBlock first = firstBlock(whStmt.getBody()); - ControlFlowEdge(cond, first); - ControlFlowEdge(continuejoin, cond); + addControlFlowEdge(cond, first); + addControlFlowEdge(continuejoin, cond); } IBlock next = nextBlock(stmt); - ControlFlowEdge(cond, exitjoin); - ControlFlowEdge(exitjoin, next); + addControlFlowEdge(cond, exitjoin); + addControlFlowEdge(exitjoin, next); } return PROCESS_CONTINUE; } - + /* * @return the first block of stmt */ - public IBlock firstBlock(IASTStatement stmt){ - - if(stmt instanceof IASTBreakStatement){ + public IBlock firstBlock(IASTStatement stmt) { + + if (stmt instanceof IASTBreakStatement) { return getBlock(stmt); - } - else if(stmt instanceof IASTCaseStatement){ + } else if (stmt instanceof IASTCaseStatement) { return getBlock(stmt); - } - else if(stmt instanceof IASTCompoundStatement){ - IASTCompoundStatement cmpStmt = (IASTCompoundStatement)stmt; + } else if (stmt instanceof IASTCompoundStatement) { + IASTCompoundStatement cmpStmt = (IASTCompoundStatement) stmt; IASTStatement[] stmts = cmpStmt.getStatements(); - for(int i=0; i i = BBs_.iterator(); i.hasNext();){ + for (Iterator i = BBs_.iterator(); i.hasNext();) { IBlock bb = i.next(); - if(bb.search(expr, parent)) return bb; + if (bb.search(expr, parent)) + return bb; } return null; } - public IBlock getBlock(IASTStatement stmt){ - for(Iterator i = BBs_.iterator(); i.hasNext();){ + public IBlock getBlock(IASTStatement stmt) { + for (Iterator i = BBs_.iterator(); i.hasNext();) { IBlock bb = i.next(); - if(bb.search(stmt)) return bb; + if (bb.search(stmt)) + return bb; } return null; } - - public IBlock getBlock(IASTName label){ - for(Iterator i = BBs_.iterator(); i.hasNext();){ + + public IBlock getBlock(IASTName label) { + for (Iterator i = BBs_.iterator(); i.hasNext();) { IBlock bb = i.next(); - if(bb.search(label)) return bb; + if (bb.search(label)) + return bb; } return null; } - - public IBlock getBlock(IASTNode content, IASTStatement parent, int type){ - for(Iterator i = BBs_.iterator(); i.hasNext();){ - Block bb = (Block)i.next(); - if(bb.search(content, parent, type)) return bb; + + public IBlock getBlock(IASTNode content, IASTStatement parent, int type) { + for (Iterator i = BBs_.iterator(); i.hasNext();) { + Block bb = (Block) i.next(); + if (bb.search(content, parent, type)) + return bb; } return null; } - + + public IBlock[] getBlocks() { + return BBs_.toArray(new IBlock[BBs_.size()]); + } + + public IControlFlowEdge[] getEdges() { + return edges_.toArray(new IControlFlowEdge[edges_.size()]); + } + public IBlock getEntry() { return entry_; } @@ -691,129 +698,142 @@ public class ControlFlowGraph implements IControlFlowGraph { public IBlock getExit() { return exit_; } - - public void addBlock(IBlock bb){ - if(!BBs_.contains(bb)) + + public void addBlock(IBlock bb) { + if (!BBs_.contains(bb)) BBs_.add(bb); } @SuppressWarnings("unchecked") - public void buildDOM(){ + public void buildDOM() { List all = new ArrayList(); all.add(entry_); all.addAll(BBs_); all.add(exit_); - + entry_.getDOM().add(entry_); - + Iterator i; - for(i = BBs_.iterator(); i.hasNext();){ + for (i = BBs_.iterator(); i.hasNext();) { i.next().setDOM(all); } exit_.setDOM(all); - + boolean change = true; - while(change){ + while (change) { change = false; - for(i = all.iterator(); i.hasNext();){ + for (i = all.iterator(); i.hasNext();) { IBlock block = i.next(); - if(block == entry_) continue; + if (block == entry_) + continue; List temp = new ArrayList(all); - for(Iterator ii = block.getPreds().iterator(); ii.hasNext();){ + for (Iterator ii = block.getPreds().iterator(); ii + .hasNext();) { IBlock pred = ii.next(); temp = intersect(temp, pred.getDOM()); } List D = new ArrayList(temp); - if(!D.contains(block)) D.add(block); - if(!equals(D, block.getDOM())){ + if (!D.contains(block)) + D.add(block); + if (!equals(D, block.getDOM())) { change = true; block.setDOM(D); } } } } - - public void buildPDOM(){ + + public void buildPDOM() { /* TODO */ } - + @SuppressWarnings("unchecked") - public List intersect(List A, List B){ - if(A == null || B == null) return null; + public List intersect(List A, List B) { + if (A == null || B == null) + return null; List list = new ArrayList(); - for(Iterator i = A.iterator(); i.hasNext();){ + for (Iterator i = A.iterator(); i.hasNext();) { Object o = i.next(); - if(B.contains(o)) list.add(o); + if (B.contains(o)) + list.add(o); } return list; } + @SuppressWarnings("unchecked") - public boolean equals(List A, List B){ - if(A == null && B == null) return true; - if(A == null && B != null) return false; - if(A != null && B == null) return false; - if(A.size() != B.size()) return false; - for(Iterator i = A.iterator(); i.hasNext();){ - if(!B.contains(i.next())) return false; + public boolean equals(List A, List B) { + if (A == null && B == null) + return true; + if (A == null && B != null) + return false; + if (A != null && B == null) + return false; + if (A.size() != B.size()) + return false; + for (Iterator i = A.iterator(); i.hasNext();) { + if (!B.contains(i.next())) + return false; } return true; } - + /** * Sort Blocks in topological order */ private Stack order; - protected void sort(){ + + protected void sort() { List all = new ArrayList(); all.add(entry_); all.addAll(BBs_); all.add(exit_); - for(Iterator i = all.iterator(); i.hasNext();){ + for (Iterator i = all.iterator(); i.hasNext();) { IBlock block = i.next(); block.setAttr("color", new Integer(0)); } order = new Stack(); - for(Iterator i = all.iterator(); i.hasNext();){ - IBlock block = (IBlock)i.next(); - int color = ((Integer)block.getAttr("color")).intValue(); - if(color == 0) + for (Iterator i = all.iterator(); i.hasNext();) { + IBlock block = (IBlock) i.next(); + int color = ((Integer) block.getAttr("color")).intValue(); + if (color == 0) DFSVisit(block); } IBlock b1 = order.pop(); IBlock b2 = null; - while(!order.empty()){ + while (!order.empty()) { b2 = order.pop(); b1.setTopNext(b2); b1 = b2; } } - - protected void DFSVisit(IBlock block){ - block.setAttr("color", new Integer(1)); //gray - for(Iterator i = block.getSuccs().iterator(); i.hasNext();){ + + protected void DFSVisit(IBlock block) { + block.setAttr("color", new Integer(1)); // gray + for (Iterator i = block.getSuccs().iterator(); i.hasNext();) { IBlock succ = i.next(); - if(isBackEdgeSucc(block, succ)) continue; - int color = ((Integer)succ.getAttr("color")).intValue(); - if(color == 0) //white + if (isBackEdgeSucc(block, succ)) + continue; + int color = ((Integer) succ.getAttr("color")).intValue(); + if (color == 0) // white DFSVisit(succ); } order.push(block); } - + /** - * @return "true" if edge (from, to) is a back edge. + * @return "true" if edge (from, to) is a back edge. */ - protected boolean isBackEdgeSucc(IBlock from, IBlock to){ + protected boolean isBackEdgeSucc(IBlock from, IBlock to) { return from.getSuccs().contains(to) && from.getDOM().contains(to); } - - protected void otherOPs(){ + + protected void otherOPs() { /* Empty method for future extensions */ } - - public void print(){ - for(IBlock b = entry_; b != null; b = b.topNext()) + + public void print() { + for (IBlock b = entry_; b != null; b = b.topNext()) b.print(); } -- cgit