import Analysis.OoOJava.ConflictEdge;
import Analysis.OoOJava.ConflictNode;
import IR.Descriptor;
+import IR.FieldDescriptor;
import IR.MethodDescriptor;
+import IR.VarDescriptor;
public class FlowGraph {
NTuple<Descriptor> endTuple) {
FlowEdge edge = new FlowEdge(fromNode, toNode, initTuple, endTuple);
-
fromNode.addOutEdge(edge);
System.out.println("add a new edge=" + edge);
if (mapDescTupleToInferNode.containsKey(descTuple)) {
return mapDescTupleToInferNode.get(descTuple);
} else {
- FlowNode node = new FlowNode(descTuple);
- mapDescTupleToInferNode.put(descTuple, node);
+ FlowNode node = createNewFlowNode(descTuple);
return node;
}
}
return thisVarNode;
}
- public void createNewFlowNode(NTuple<Descriptor> tuple) {
+ public FlowNode createNewFlowNode(NTuple<Descriptor> tuple) {
if (!mapDescTupleToInferNode.containsKey(tuple)) {
FlowNode node = new FlowNode(tuple);
}
System.out.println("Creating new node=" + node);
+ return node;
+ } else {
+ return mapDescTupleToInferNode.get(tuple);
}
}
+ private void drawEdges(FlowNode node, BufferedWriter bw, Set<FlowNode> addedNodeSet,
+ Set<FlowEdge> addedEdgeSet) throws IOException {
+
+ Set<FlowEdge> edgeSet = node.getOutEdgeSet();
+
+ for (Iterator<FlowEdge> iterator = edgeSet.iterator(); iterator.hasNext();) {
+ FlowEdge flowEdge = iterator.next();
+
+ FlowNode u = flowEdge.getSrc();
+ FlowNode v = flowEdge.getDst();
+
+ if (u.getDescTuple().equals(flowEdge.getInitTuple())
+ && v.getDescTuple().equals(flowEdge.getEndTuple())) {
+ // only draw an edge of the actual value flow
+
+ if (!addedEdgeSet.contains(flowEdge)) {
+
+ if (!addedNodeSet.contains(u)) {
+ drawNode(u, bw);
+ addedNodeSet.add(u);
+ }
+ if (!addedNodeSet.contains(v)) {
+ drawNode(v, bw);
+ addedNodeSet.add(v);
+ }
+
+ bw.write("" + u.getID() + " -> " + v.getID() + ";\n");
+ addedEdgeSet.add(flowEdge);
+ }
+ }
+
+ }
+
+ }
+
+ private void drawNode(FlowNode node, BufferedWriter bw) throws IOException {
+ bw.write(node.getID() + " [label=\"" + node.getPrettyID() + "\"]" + ";\n");
+ }
+
public void writeGraph() throws java.io.IOException {
String graphName = md.toString();
Iterator<FlowNode> iter = nodeSet.iterator();
- Set<FlowEdge> addedSet = new HashSet<FlowEdge>();
+ Set<FlowEdge> addedEdgeSet = new HashSet<FlowEdge>();
+ Set<FlowNode> addedNodeSet = new HashSet<FlowNode>();
while (iter.hasNext()) {
FlowNode node = iter.next();
- if (node.getFieldNodeSet().size() > 0) {
- drawSubgraph(node, bw);
- }
-
- String attributes = " [";
-
- attributes += "label=\"" + node.getID() + "\"]";
-
- bw.write(node.getID() + attributes + ";\n");
-
- Set<FlowEdge> edgeSet = node.getOutEdgeSet();
-
- for (Iterator<FlowEdge> iterator = edgeSet.iterator(); iterator.hasNext();) {
- FlowEdge flowEdge = iterator.next();
-
- FlowNode u = flowEdge.getSrc();
- FlowNode v = flowEdge.getDst();
-
- if (!addedSet.contains(flowEdge)) {
- bw.write("" + u.getID() + " -> " + v.getID() + ";\n");
- addedSet.add(flowEdge);
+ if (node.getDescTuple().size() == 1) {
+ // here, we just care about the local variable
+ if (node.getFieldNodeSet().size() > 0) {
+ drawSubgraph(node, bw, addedEdgeSet);
}
-
}
- }
+ drawEdges(node, bw, addedNodeSet, addedEdgeSet);
- bw.write("graphTitle[label=\"" + graphName + "\",shape=box];\n");
+ }
bw.write("}\n");
bw.close();
}
- private void drawSubgraph(FlowNode node, BufferedWriter bw) throws IOException {
+ public boolean constainsNode(FlowNode node) {
+ return nodeSet.contains(node);
+ }
- bw.write(" subgraph sg" + node.getID() + "{\n");
- // bw.write(" color=gray;\n");
- bw.write(" label=\"" + node.getID() + "\";\n");
+ private void drawSubgraph(FlowNode node, BufferedWriter bw, Set<FlowEdge> addedSet)
+ throws IOException {
+
+ bw.write("subgraph cluster_" + node.getID() + "{\n");
+ bw.write("label=\"" + node.getPrettyID() + "\";\n");
Set<FlowNode> fieldNodeSet = node.getFieldNodeSet();
for (Iterator iterator = fieldNodeSet.iterator(); iterator.hasNext();) {
FlowNode fieldNode = (FlowNode) iterator.next();
- String attribute = fieldNode.getID() + ";\n";
- bw.write(" " + attribute);
+ if (fieldNode.getFieldNodeSet().size() > 0) {
+ drawSubgraph(fieldNode, bw, addedSet);
+ } else {
+ Descriptor desc = fieldNode.getDescTuple().getLastElement();
+ if (desc instanceof VarDescriptor) {
+ VarDescriptor varDesc = (VarDescriptor) desc;
+ if (varDesc.getType().isPrimitive()) {
+ bw.write(fieldNode.getID() + " [label=\"" + fieldNode.getPrettyID() + "\"];\n");
+ }
+ } else if (desc instanceof FieldDescriptor) {
+ FieldDescriptor fieldDesc = (FieldDescriptor) desc;
+ if (fieldDesc.getType().isPrimitive()) {
+ bw.write(fieldNode.getID() + " [label=\"" + fieldNode.getPrettyID() + "\"];\n");
+ }
+ }
+ }
}
- bw.write(" }\n");
+ bw.write("}\n");
}
}
\ No newline at end of file
private void analyzeMethodBody(ClassDescriptor cd, MethodDescriptor md) {
BlockNode bn = state.getMethodBody(md);
- analyzeBlockNode(md, md.getParameterTable(), bn);
+ analyzeFlowBlockNode(md, md.getParameterTable(), bn, null);
}
- private void analyzeBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn) {
+ private void analyzeFlowBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn,
+ NodeTupleSet implicitFlowTupleSet) {
bn.getVarTable().setParent(nametable);
for (int i = 0; i < bn.size(); i++) {
BlockStatementNode bsn = bn.get(i);
- analyzeBlockStatementNode(md, bn.getVarTable(), bsn);
+ analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
}
}
private void analyzeBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
- BlockStatementNode bsn) {
+ BlockStatementNode bsn, NodeTupleSet implicitFlowTupleSet) {
switch (bsn.kind()) {
case Kind.BlockExpressionNode:
- analyzeBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn);
+ analyzeBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn, implicitFlowTupleSet);
break;
case Kind.DeclarationNode:
- analyzeFlowDeclarationNode(md, nametable, (DeclarationNode) bsn);
+ analyzeFlowDeclarationNode(md, nametable, (DeclarationNode) bsn, implicitFlowTupleSet);
break;
case Kind.IfStatementNode:
- analyzeIfStatementNode(md, nametable, (IfStatementNode) bsn);
+ analyzeFlowIfStatementNode(md, nametable, (IfStatementNode) bsn, implicitFlowTupleSet);
break;
case Kind.LoopNode:
- analyzeLoopNode(md, nametable, (LoopNode) bsn);
+ analyzeFlowLoopNode(md, nametable, (LoopNode) bsn, implicitFlowTupleSet);
break;
case Kind.ReturnNode:
break;
case Kind.SubBlockNode:
- analyzeSubBlockNode(md, nametable, (SubBlockNode) bsn);
+ analyzeFlowSubBlockNode(md, nametable, (SubBlockNode) bsn, implicitFlowTupleSet);
break;
case Kind.ContinueBreakNode:
}
- private void analyzeSubBlockNode(MethodDescriptor md, SymbolTable nametable, SubBlockNode bsn) {
- // TODO Auto-generated method stub
-
+ private void analyzeFlowSubBlockNode(MethodDescriptor md, SymbolTable nametable,
+ SubBlockNode sbn, NodeTupleSet implicitFlowTupleSet) {
+ analyzeFlowBlockNode(md, nametable, sbn.getBlockNode(), implicitFlowTupleSet);
}
private void analyzeReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode bsn) {
}
- private void analyzeLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode bsn) {
- // TODO Auto-generated method stub
+ private void analyzeFlowLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln,
+ NodeTupleSet implicitFlowTupleSet) {
+
+ if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
+
+ NodeTupleSet condTupleNode = new NodeTupleSet();
+ analyzeFlowExpressionNode(md, nametable, ln.getCondition(), condTupleNode, null,
+ implicitFlowTupleSet);
+ condTupleNode.addTupleSet(implicitFlowTupleSet);
+ System.out.println("condTupleNode=" + condTupleNode);
+
+ // add edges from condNodeTupleSet to all nodes of conditional nodes
+ analyzeFlowBlockNode(md, nametable, ln.getBody(), condTupleNode);
+
+ } else {
+ // check 'for loop' case
+ BlockNode bn = ln.getInitializer();
+ analyzeFlowBlockNode(md, nametable, bn, implicitFlowTupleSet);
+ bn.getVarTable().setParent(nametable);
+
+ NodeTupleSet condTupleNode = new NodeTupleSet();
+ analyzeFlowExpressionNode(md, nametable, ln.getCondition(), condTupleNode, null,
+ implicitFlowTupleSet);
+ condTupleNode.addTupleSet(implicitFlowTupleSet);
+ System.out.println("condTupleNode=" + condTupleNode);
+
+ analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(), condTupleNode);
+ analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(), condTupleNode);
+
+ }
}
- private void analyzeIfStatementNode(MethodDescriptor md, SymbolTable nametable,
- IfStatementNode bsn) {
- // TODO Auto-generated method stub
+ private void analyzeFlowIfStatementNode(MethodDescriptor md, SymbolTable nametable,
+ IfStatementNode isn, NodeTupleSet implicitFlowTupleSet) {
+
+ NodeTupleSet condTupleNode = new NodeTupleSet();
+ analyzeFlowExpressionNode(md, nametable, isn.getCondition(), condTupleNode, null,
+ implicitFlowTupleSet);
+
+ // add edges from condNodeTupleSet to all nodes of conditional nodes
+ condTupleNode.addTupleSet(implicitFlowTupleSet);
+ analyzeFlowBlockNode(md, nametable, isn.getTrueBlock(), condTupleNode);
+
+ if (isn.getFalseBlock() != null) {
+ analyzeFlowBlockNode(md, nametable, isn.getFalseBlock(), condTupleNode);
+ }
}
private void analyzeFlowDeclarationNode(MethodDescriptor md, SymbolTable nametable,
- DeclarationNode dn) {
+ DeclarationNode dn, NodeTupleSet implicitFlowTupleSet) {
VarDescriptor vd = dn.getVarDescriptor();
NTuple<Descriptor> tupleLHS = new NTuple<Descriptor>();
if (dn.getExpression() != null) {
NodeTupleSet tupleSetRHS = new NodeTupleSet();
- analyzeFlowExpressionNode(md, nametable, dn.getExpression(), tupleSetRHS, null);
+ analyzeFlowExpressionNode(md, nametable, dn.getExpression(), tupleSetRHS, null,
+ implicitFlowTupleSet);
// add a new flow edge from rhs to lhs
for (Iterator<NTuple<Descriptor>> iter = tupleSetRHS.iterator(); iter.hasNext();) {
}
private void analyzeBlockExpressionNode(MethodDescriptor md, SymbolTable nametable,
- BlockExpressionNode ben) {
- analyzeFlowExpressionNode(md, nametable, ben.getExpression(), null, null);
+ BlockExpressionNode ben, NodeTupleSet implicitFlowTupleSet) {
+ analyzeFlowExpressionNode(md, nametable, ben.getExpression(), null, null, implicitFlowTupleSet);
}
private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
- ExpressionNode en, NodeTupleSet nodeSet, NTuple<Descriptor> base) {
+ ExpressionNode en, NodeTupleSet nodeSet, NTuple<Descriptor> base,
+ NodeTupleSet implicitFlowTupleSet) {
// note that expression node can create more than one flow node
// nodeSet contains of flow nodes
switch (en.kind()) {
case Kind.AssignmentNode:
- analyzeFlowAssignmentNode(md, nametable, (AssignmentNode) en, base);
+ analyzeFlowAssignmentNode(md, nametable, (AssignmentNode) en, base, implicitFlowTupleSet);
break;
case Kind.FieldAccessNode:
- flowTuple = analyzeFlowFieldAccessNode(md, nametable, (FieldAccessNode) en, nodeSet, base);
+ flowTuple =
+ analyzeFlowFieldAccessNode(md, nametable, (FieldAccessNode) en, nodeSet, base,
+ implicitFlowTupleSet);
nodeSet.addTuple(flowTuple);
return flowTuple;
case Kind.NameNode:
NodeTupleSet nameNodeSet = new NodeTupleSet();
- flowTuple = analyzeFlowNameNode(md, nametable, (NameNode) en, nameNodeSet, base);
+ flowTuple =
+ analyzeFlowNameNode(md, nametable, (NameNode) en, nameNodeSet, base, implicitFlowTupleSet);
nodeSet.addTuple(flowTuple);
return flowTuple;
case Kind.OpNode:
- analyzeFlowOpNode(md, nametable, (OpNode) en, nodeSet);
+ analyzeFlowOpNode(md, nametable, (OpNode) en, nodeSet, implicitFlowTupleSet);
break;
case Kind.CreateObjectNode:
}
private void analyzeFlowOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on,
- NodeTupleSet nodeSet) {
-
- System.out.println("### OPNode=" + on.printNode(0));
+ NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
NodeTupleSet leftOpSet = new NodeTupleSet();
NodeTupleSet rightOpSet = new NodeTupleSet();
// left operand
- analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null);
+ analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null, implicitFlowTupleSet);
System.out.println("leftOpSet=" + leftOpSet);
if (on.getRight() != null) {
// right operand
- analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null);
+ analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null,
+ implicitFlowTupleSet);
System.out.println("rightOpSet=" + rightOpSet);
}
}
private NTuple<Descriptor> analyzeFlowNameNode(MethodDescriptor md, SymbolTable nametable,
- NameNode nn, NodeTupleSet nodeSet, NTuple<Descriptor> base) {
+ NameNode nn, NodeTupleSet nodeSet, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
if (base == null) {
base = new NTuple<Descriptor>();
NameDescriptor nd = nn.getName();
if (nd.getBase() != null) {
- analyzeFlowExpressionNode(md, nametable, nn.getExpression(), nodeSet, base);
+ analyzeFlowExpressionNode(md, nametable, nn.getExpression(), nodeSet, base,
+ implicitFlowTupleSet);
} else {
String varname = nd.toString();
if (varname.equals("this")) {
}
private NTuple<Descriptor> analyzeFlowFieldAccessNode(MethodDescriptor md, SymbolTable nametable,
- FieldAccessNode fan, NodeTupleSet nodeSet, NTuple<Descriptor> base) {
+ FieldAccessNode fan, NodeTupleSet nodeSet, NTuple<Descriptor> base,
+ NodeTupleSet implicitFlowTupleSet) {
ExpressionNode left = fan.getExpression();
TypeDescriptor ltd = left.getType();
// left = aan.getExpression();
// }
// fanNodeSet
- base = analyzeFlowExpressionNode(md, nametable, left, nodeSet, base);
+ base = analyzeFlowExpressionNode(md, nametable, left, nodeSet, base, implicitFlowTupleSet);
if (!left.getType().isPrimitive()) {
}
private void analyzeFlowAssignmentNode(MethodDescriptor md, SymbolTable nametable,
- AssignmentNode an, NTuple<Descriptor> base) {
+ AssignmentNode an, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
System.out.println("analyzeFlowAssignmentNode=" + an);
- ClassDescriptor cd = md.getClassDesc();
-
NodeTupleSet nodeSetRHS = new NodeTupleSet();
NodeTupleSet nodeSetLHS = new NodeTupleSet();
// if LHS is array access node, need to capture value flows between an array
// and its index value
- analyzeFlowExpressionNode(md, nametable, an.getDest(), nodeSetLHS, null);
+ analyzeFlowExpressionNode(md, nametable, an.getDest(), nodeSetLHS, null, implicitFlowTupleSet);
System.out.println("ASSIGNMENT NODE nodeSetLHS=" + nodeSetLHS);
// NTuple<Descriptor> lhsDescTuple = analyzeFlowExpressionNode(md,
// nametable, an.getDest(), base);
if (!postinc) {
// analyze value flows of rhs expression
- analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null);
+ analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null, implicitFlowTupleSet);
System.out.println("ASSIGNMENT NODE nodeSetRHS=" + nodeSetRHS);
// creates edges from RHS to LHS
}
}
+ // creates edges from implicitFlowTupleSet to LHS
+ for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
+ NTuple<Descriptor> fromTuple = iter.next();
+ for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
+ NTuple<Descriptor> toTuple = iter2.next();
+ addFlowGraphEdge(md, fromTuple, toTuple);
+ }
+ }
+
} else {
// postinc case
for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {