diff options
Diffstat (limited to 'org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg')
17 files changed, 457 insertions, 0 deletions
diff --git a/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/CVS/Entries b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/CVS/Entries new file mode 100644 index 0000000..60f510d --- /dev/null +++ b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/CVS/Entries @@ -0,0 +1,13 @@ +/IBasicBlock.java/1.6/Thu Jun 3 17:01:53 2010//TCDT_7_0_0 +/IBranchNode.java/1.4/Thu Jun 3 17:01:53 2010//TCDT_7_0_0 +/ICfgData.java/1.2/Tue Jun 1 02:24:14 2010//TCDT_7_0_0 +/IConnectorNode.java/1.5/Thu Jun 3 17:01:53 2010//TCDT_7_0_0 +/IControlFlowGraph.java/1.5/Thu Jun 3 17:01:53 2010//TCDT_7_0_0 +/IDecisionNode.java/1.4/Thu Jun 3 17:01:53 2010//TCDT_7_0_0 +/IExitNode.java/1.4/Thu Jun 3 17:01:53 2010//TCDT_7_0_0 +/IJumpNode.java/1.5/Thu Jun 3 17:01:53 2010//TCDT_7_0_0 +/INodeFactory.java/1.4/Thu Jun 3 17:01:53 2010//TCDT_7_0_0 +/IPlainNode.java/1.4/Thu Jun 3 17:01:53 2010//TCDT_7_0_0 +/ISingleIncoming.java/1.4/Thu Jun 3 17:01:53 2010//TCDT_7_0_0 +/ISingleOutgoing.java/1.4/Thu Jun 3 17:01:53 2010//TCDT_7_0_0 +/IStartNode.java/1.3/Thu Jun 3 17:01:53 2010//TCDT_7_0_0 diff --git a/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/CVS/Repository b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/CVS/Repository new file mode 100644 index 0000000..52814e4 --- /dev/null +++ b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/CVS/Repository @@ -0,0 +1 @@ +org.eclipse.cdt/codan/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg diff --git a/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/CVS/Root b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/CVS/Root new file mode 100644 index 0000000..04efa23 --- /dev/null +++ b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/CVS/Root @@ -0,0 +1 @@ +:pserver:anonymous@dev.eclipse.org:/cvsroot/tools diff --git a/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/CVS/Tag b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/CVS/Tag new file mode 100644 index 0000000..49a449a --- /dev/null +++ b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/CVS/Tag @@ -0,0 +1 @@ +NCDT_7_0_0 diff --git a/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/IBasicBlock.java b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/IBasicBlock.java new file mode 100644 index 0000000..406ab84 --- /dev/null +++ b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/IBasicBlock.java @@ -0,0 +1,46 @@ +/******************************************************************************* + * Copyright (c) 2010 Alena Laskavaia and others. + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Eclipse Public License v1.0 + * which accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + * Contributors: + * Alena Laskavaia - initial API and implementation + *******************************************************************************/ +package org.eclipse.cdt.codan.core.model.cfg; + +/** + * Control flow graph's basic block node - super interface of all nodes. + * It has set on incoming nodes and outgoing nodes. + * <p/> + * + * @noextend This interface is not intended to be extended by clients. + * @noimplement This interface is not intended to be implemented by clients. + */ +public interface IBasicBlock { + /** + * Incoming nodes - nodes that executed immediately before this one + * + * @return array of incoming nodes, empty array of none + */ + IBasicBlock[] getIncomingNodes(); + + /** + * Outgoing nodes - where control would be passed. Can be more than one if + * node is condition. + * + * @return array of outgoing nodes, empty of none + */ + IBasicBlock[] getOutgoingNodes(); + + /** + * @return size of array of incoming nodes + */ + int getIncomingSize(); + + /** + * @return size of array of outgoing nodes + */ + int getOutgoingSize(); +} diff --git a/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/IBranchNode.java b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/IBranchNode.java new file mode 100644 index 0000000..77e7fb3 --- /dev/null +++ b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/IBranchNode.java @@ -0,0 +1,38 @@ +/******************************************************************************* + * Copyright (c) 2009, 2010 Alena Laskavaia + * 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: + * Alena Laskavaia - initial API and implementation + *******************************************************************************/ +package org.eclipse.cdt.codan.core.model.cfg; + +/** + * Node that represent empty operator with label, such as case branch or label + * + * @noextend This interface is not intended to be extended by clients. + * @noimplement This interface is not intended to be implemented by clients. + */ +public interface IBranchNode extends IBasicBlock, ISingleIncoming, + ISingleOutgoing { + /** + * Then branch of "if" statement + */ + public static String THEN = "then"; //$NON-NLS-1$ + /** + * Else branch of "if" statement + */ + public static String ELSE = "else"; //$NON-NLS-1$ + /** + * Default branch of "switch" statement + */ + public static String DEFAULT = "default"; //$NON-NLS-1$ + + /** + * @return label of a branch + */ + String getLabel(); +} diff --git a/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/ICfgData.java b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/ICfgData.java new file mode 100644 index 0000000..1e43450 --- /dev/null +++ b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/ICfgData.java @@ -0,0 +1,32 @@ +/******************************************************************************* + * Copyright (c) 2009,2010 Alena Laskavaia + * 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: + * Alena Laskavaia - initial API and implementation + *******************************************************************************/ +package org.eclipse.cdt.codan.core.model.cfg; + +/** + * Interface to access data object that control flow graph block carries, + * usually it is an ast node. + * + * @noextend This interface is not intended to be extended by clients. + * @noimplement This interface is not intended to be implemented by clients. + */ +public interface ICfgData { + /** + * @return data object + */ + public abstract Object getData(); + + /** + * Sets data object for the node + * + * @param data + */ + public abstract void setData(Object data); +}
\ No newline at end of file diff --git a/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/IConnectorNode.java b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/IConnectorNode.java new file mode 100644 index 0000000..f58fdd1 --- /dev/null +++ b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/IConnectorNode.java @@ -0,0 +1,25 @@ +/******************************************************************************* + * Copyright (c) 2010 Alena Laskavaia and others. + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Eclipse Public License v1.0 + * which accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + * Contributors: + * Alena Laskavaia - initial API and implementation + *******************************************************************************/ +package org.eclipse.cdt.codan.core.model.cfg; + +/** + * Connector node has multiple incoming branches and single outgoing. + * Incoming nodes are usually instance of {@link IJumpNode} + * + * @noextend This interface is not intended to be extended by clients. + * @noimplement This interface is not intended to be implemented by clients. + */ +public interface IConnectorNode extends IBasicBlock, ISingleOutgoing { + /** + * @return true if one of the incoming arcs is backward arc + */ + boolean hasBackwardIncoming(); +} diff --git a/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/IControlFlowGraph.java b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/IControlFlowGraph.java new file mode 100644 index 0000000..a8f9269 --- /dev/null +++ b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/IControlFlowGraph.java @@ -0,0 +1,69 @@ +/******************************************************************************* + * Copyright (c) 2009, 2010 Alena Laskavaia + * 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: + * Alena Laskavaia - initial API and implementation + *******************************************************************************/ +package org.eclipse.cdt.codan.core.model.cfg; + +import java.util.Collection; +import java.util.Iterator; + +/** + * Represents control flow graph (CFG) object. + * This is "normalized" control flow graph, with typed nodes: + * <br> + * <li> {@link IStartNode} - start node of the cfg (source) + * <li> {@link IExitNode} - exit node of the cfg (sink) + * <li> {@link IPlainNode} - has one incoming one outgoing + * <li> {@link IDecisionNode} - has one incoming and the only node that can have + * multiple outcoming + * arcs + * <li> {@link IConnectorNode} - the only node that can have multiple incoming + * arcs, and one outgoing + * <li> {@link IJumpNode} - has one incoming and one outgoing but represent + * change of control direction + * <li> {@link IBranchNode} - usually node where decision node connect to, + * labels represent a way where controls goes to + * + * @noextend This interface is not intended to be extended by clients. + * @noimplement This interface is not intended to be implemented by clients. + */ +public interface IControlFlowGraph { + /** + * @return start node of the graph. CFG only has one start node. + */ + IStartNode getStartNode(); + + /** + * @return iterator over exit nodes of control flow graph. Exit nodes + * include return statement, + * and statements with throw and abort/exit functions. + */ + Iterator<IExitNode> getExitNodeIterator(); + + /** + * @return size of exit nodes list + */ + int getExitNodeSize(); + + /** + * @return list of roots of dead code sections, they don't have incoming + * arcs + */ + Iterator<IBasicBlock> getUnconnectedNodeIterator(); + + /** + * @return size of unconnected nodes list + */ + int getUnconnectedNodeSize(); + + /** + * @return collection of all nodes + */ + Collection<IBasicBlock> getNodes(); +} diff --git a/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/IDecisionNode.java b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/IDecisionNode.java new file mode 100644 index 0000000..7f2f561 --- /dev/null +++ b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/IDecisionNode.java @@ -0,0 +1,29 @@ +/******************************************************************************* + * Copyright (c) 2010 Alena Laskavaia and others. + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Eclipse Public License v1.0 + * which accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + * Contributors: + * Alena Laskavaia - initial API and implementation + *******************************************************************************/ +package org.eclipse.cdt.codan.core.model.cfg; + +/** + * + * Interface for decision node. This node represent condition node in the graph, + * it has one incoming arc and many outgoing, each of outgoing node should be + * IBranchNode + * + * @noextend This interface is not intended to be extended by clients. + * @noimplement This interface is not intended to be implemented by clients. + */ +public interface IDecisionNode extends IBasicBlock, ISingleIncoming { + /** + * Node where branches of decision node merge + * + * @return the "merge" node + */ + IConnectorNode getMergeNode(); +} diff --git a/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/IExitNode.java b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/IExitNode.java new file mode 100644 index 0000000..71d7e25 --- /dev/null +++ b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/IExitNode.java @@ -0,0 +1,25 @@ +/******************************************************************************* + * Copyright (c) 2009, 2010 Alena Laskavaia + * 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: + * Alena Laskavaia - initial API and implementation + *******************************************************************************/ +package org.eclipse.cdt.codan.core.model.cfg; + +/** + * Exit node of the graph. Usually return from the function, can also be throw + * or abort, such at exit(0) call. + * + * @noextend This interface is not intended to be extended by clients. + * @noimplement This interface is not intended to be implemented by clients. + */ +public interface IExitNode extends IBasicBlock, ISingleIncoming { + /** + * @return reference to a start node a graph + */ + IStartNode getStartNode(); +} diff --git a/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/IJumpNode.java b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/IJumpNode.java new file mode 100644 index 0000000..d2e298b --- /dev/null +++ b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/IJumpNode.java @@ -0,0 +1,33 @@ +/******************************************************************************* + * Copyright (c) 2010 Alena Laskavaia and others. + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Eclipse Public License v1.0 + * which accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + * Contributors: + * Alena Laskavaia - initial API and implementation + *******************************************************************************/ +package org.eclipse.cdt.codan.core.model.cfg; + +/** + * Node that changes the control of the graph, i.e. passes control to non-next + * statement. Can be used to implement gotos, break, continue, end of branches. + * Outgoing node is always {@link IConnectorNode} + * + * @noextend This interface is not intended to be extended by clients. + * @noimplement This interface is not intended to be implemented by clients. + */ +public interface IJumpNode extends IBasicBlock, ISingleOutgoing { + /** + * @return true of outgoing arc is backward one, see definition of backward + * arc in a "network" graph + */ + boolean isBackwardArc(); + + /** + * @return reference to a connector node to which this one "jumps" (same as + * outgoing node) + */ + IConnectorNode getJumpNode(); +} diff --git a/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/INodeFactory.java b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/INodeFactory.java new file mode 100644 index 0000000..bd10ded --- /dev/null +++ b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/INodeFactory.java @@ -0,0 +1,54 @@ +/******************************************************************************* + * Copyright (c) 2009, 2010 Alena Laskavaia + * 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: + * Alena Laskavaia - initial API and implementation + *******************************************************************************/ +package org.eclipse.cdt.codan.core.model.cfg; + +/** + * Control Flow Graph Node factory + * + * @noextend This interface is not intended to be extended by clients. + */ +public interface INodeFactory { + /** + * @return new plain node + */ + IPlainNode createPlainNode(); + + /** + * @return new jump node + */ + IJumpNode createJumpNode(); + + /** + * @return new decision node + */ + IDecisionNode createDecisionNode(); + + /** + * @return new connector node + */ + IConnectorNode createConnectorNode(); + + /** + * @param label + * @return new branch node + */ + IBranchNode createBranchNode(String label); + + /** + * @return new start node + */ + IStartNode createStartNode(); + + /** + * @return new exit node + */ + IExitNode createExitNode(); +} diff --git a/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/IPlainNode.java b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/IPlainNode.java new file mode 100644 index 0000000..fac5599 --- /dev/null +++ b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/IPlainNode.java @@ -0,0 +1,22 @@ +/******************************************************************************* + * Copyright (c) 2010 Alena Laskavaia and others. + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Eclipse Public License v1.0 + * which accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + * Contributors: + * Alena Laskavaia - initial API and implementation + *******************************************************************************/ +package org.eclipse.cdt.codan.core.model.cfg; + +/** + * Has one incoming, one outgoing connection. Usually expression statement or + * declaration. + * + * @noextend This interface is not intended to be extended by clients. + * @noimplement This interface is not intended to be implemented by clients. + */ +public interface IPlainNode extends IBasicBlock, ISingleOutgoing, + ISingleIncoming { +} diff --git a/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/ISingleIncoming.java b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/ISingleIncoming.java new file mode 100644 index 0000000..2900ce8 --- /dev/null +++ b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/ISingleIncoming.java @@ -0,0 +1,23 @@ +/******************************************************************************* + * Copyright (c) 2010 Alena Laskavaia and others. + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Eclipse Public License v1.0 + * which accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + * Contributors: + * Alena Laskavaia - initial API and implementation + *******************************************************************************/ +package org.eclipse.cdt.codan.core.model.cfg; + +/** + * Node with one incoming arc + * + * @noextend This interface is not intended to be extended by clients. + */ +public interface ISingleIncoming { + /** + * @return single incoming node + */ + IBasicBlock getIncoming(); +} diff --git a/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/ISingleOutgoing.java b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/ISingleOutgoing.java new file mode 100644 index 0000000..3427826 --- /dev/null +++ b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/ISingleOutgoing.java @@ -0,0 +1,23 @@ +/******************************************************************************* + * Copyright (c) 2010 Alena Laskavaia and others. + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Eclipse Public License v1.0 + * which accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + * Contributors: + * Alena Laskavaia - initial API and implementation + *******************************************************************************/ +package org.eclipse.cdt.codan.core.model.cfg; + +/** + * Node with one outgoing arc + * + * @noextend This interface is not intended to be extended by clients. + */ +public interface ISingleOutgoing { + /** + * @return outgoing node + */ + IBasicBlock getOutgoing(); +} diff --git a/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/IStartNode.java b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/IStartNode.java new file mode 100644 index 0000000..7c20c3e --- /dev/null +++ b/org.eclipse.cdt.codan.core/src/org/eclipse/cdt/codan/core/model/cfg/IStartNode.java @@ -0,0 +1,22 @@ +/******************************************************************************* + * Copyright (c) 2010 Alena Laskavaia and others. + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Eclipse Public License v1.0 + * which accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + * Contributors: + * Alena Laskavaia - initial API and implementation + *******************************************************************************/ +package org.eclipse.cdt.codan.core.model.cfg; + +/** + * Start node of the control flow graph. Each graph has only one start node. It + * has no incoming arcs and one outgoing arc. It also contains iterator for + * function exit nodes. + * + * @noextend This interface is not intended to be extended by clients. + * @noimplement This interface is not intended to be implemented by clients. + */ +public interface IStartNode extends IBasicBlock, ISingleOutgoing { +} |