package Analysis.SSJava;
+import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
+import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import IR.Operation;
import IR.State;
import IR.SymbolTable;
+import IR.TypeDescriptor;
import IR.VarDescriptor;
import IR.Tree.ArrayAccessNode;
import IR.Tree.AssignmentNode;
}
}
+ _debug_printGraph();
+
}
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, new NTuple<Descriptor>());
+ 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 NTuple<Descriptor> analyzeFlowDeclarationNode(MethodDescriptor md, SymbolTable nametable,
- DeclarationNode dn, NTuple<Descriptor> base) {
+ private void analyzeFlowDeclarationNode(MethodDescriptor md, SymbolTable nametable,
+ DeclarationNode dn, NodeTupleSet implicitFlowTupleSet) {
VarDescriptor vd = dn.getVarDescriptor();
- base.add(vd);
- getFlowGraph(md).createNewFlowNode(base);
+ NTuple<Descriptor> tupleLHS = new NTuple<Descriptor>();
+ tupleLHS.add(vd);
+ getFlowGraph(md).createNewFlowNode(tupleLHS);
if (dn.getExpression() != null) {
- NTuple<Descriptor> rhsDescTuple =
- analyzeFlowExpressionNode(md, nametable, dn.getExpression(), new NTuple<Descriptor>());
+ NodeTupleSet tupleSetRHS = new NodeTupleSet();
+ analyzeFlowExpressionNode(md, nametable, dn.getExpression(), tupleSetRHS, null,
+ implicitFlowTupleSet);
// add a new flow edge from rhs to lhs
- if (rhsDescTuple != null) { // rhs is null when values come from the top
- // location
- getFlowGraph(md).addValueFlowEdge(rhsDescTuple, base);
+ for (Iterator<NTuple<Descriptor>> iter = tupleSetRHS.iterator(); iter.hasNext();) {
+ NTuple<Descriptor> from = iter.next();
+ addFlowGraphEdge(md, from, tupleLHS);
}
}
- return null;
-
}
private void analyzeBlockExpressionNode(MethodDescriptor md, SymbolTable nametable,
- BlockExpressionNode ben) {
- analyzeFlowExpressionNode(md, nametable, ben.getExpression(), null);
+ BlockExpressionNode ben, NodeTupleSet implicitFlowTupleSet) {
+ analyzeFlowExpressionNode(md, nametable, ben.getExpression(), null, null, implicitFlowTupleSet);
}
private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
- ExpressionNode en, 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
+ // base is always assigned to null except name node case!
+
+ NTuple<Descriptor> flowTuple;
switch (en.kind()) {
case Kind.AssignmentNode:
- analyzeFlowAssignmentNode(md, nametable, (AssignmentNode) en, base);
+ analyzeFlowAssignmentNode(md, nametable, (AssignmentNode) en, base, implicitFlowTupleSet);
break;
case Kind.FieldAccessNode:
- analyzeFieldAccessNode(md, nametable, (FieldAccessNode) en);
- break;
+ flowTuple =
+ analyzeFlowFieldAccessNode(md, nametable, (FieldAccessNode) en, nodeSet, base,
+ implicitFlowTupleSet);
+ nodeSet.addTuple(flowTuple);
+ return flowTuple;
case Kind.NameNode:
- return analyzeFlowNameNode(md, nametable, (NameNode) en, base);
+ NodeTupleSet nameNodeSet = new NodeTupleSet();
+ flowTuple =
+ analyzeFlowNameNode(md, nametable, (NameNode) en, nameNodeSet, base, implicitFlowTupleSet);
+ nodeSet.addTuple(flowTuple);
+ return flowTuple;
case Kind.OpNode:
- // return analyzeOpNode(md, nametable, (OpNode) en, new
- // HashSet<FlowNode>());
+ analyzeFlowOpNode(md, nametable, (OpNode) en, nodeSet, implicitFlowTupleSet);
break;
case Kind.CreateObjectNode:
}
- private Set<FlowNode> analyzeOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on,
- Set<FlowNode> nodeSet) {
+ private void analyzeFlowOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on,
+ NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
- ClassDescriptor cd = md.getClassDesc();
+ NodeTupleSet leftOpSet = new NodeTupleSet();
+ NodeTupleSet rightOpSet = new NodeTupleSet();
// left operand
- NTuple<Descriptor> leftOpTuple =
- analyzeFlowExpressionNode(md, nametable, on.getLeft(), new NTuple<Descriptor>());
+ analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null, implicitFlowTupleSet);
+ System.out.println("leftOpSet=" + leftOpSet);
if (on.getRight() != null) {
// right operand
- NTuple<Descriptor> rightOpTuple =
- analyzeFlowExpressionNode(md, nametable, on.getRight(), new NTuple<Descriptor>());
+ analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null,
+ implicitFlowTupleSet);
+ System.out.println("rightOpSet=" + rightOpSet);
}
Operation op = on.getOp();
case Operation.UNARYMINUS:
case Operation.LOGIC_NOT:
// single operand
- // return leftLoc;
+ nodeSet.addTupleSet(leftOpSet);
+ break;
case Operation.LOGIC_OR:
case Operation.LOGIC_AND:
case Operation.RIGHTSHIFT:
case Operation.URIGHTSHIFT:
- Set<CompositeLocation> inputSet = new HashSet<CompositeLocation>();
- // inputSet.add(leftLoc);
- // inputSet.add(rightLoc);
- // CompositeLocation glbCompLoc =
- // CompositeLattice.calculateGLB(inputSet, generateErrorMessage(cd, on));
- // return glbCompLoc;
+ // there are two operands
+ nodeSet.addTupleSet(leftOpSet);
+ nodeSet.addTupleSet(rightOpSet);
+ break;
default:
throw new Error(op.toString());
}
private NTuple<Descriptor> analyzeFlowNameNode(MethodDescriptor md, SymbolTable nametable,
- NameNode nn, 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(), base);
+ analyzeFlowExpressionNode(md, nametable, nn.getExpression(), nodeSet, base,
+ implicitFlowTupleSet);
} else {
String varname = nd.toString();
if (varname.equals("this")) {
base.add(md.getThis());
}
- // Location fieldLoc = (Location) fd.getType().getExtension();
- // loc.addLocation(fieldLoc);
base.add(fd);
} else if (d == null) {
// access static field
- // FieldDescriptor fd = nn.getField();
+ // FieldDescriptor fd = nn.getField();addFlowGraphEdge
//
// MethodLattice<String> localLattice = ssjava.getMethodLattice(md);
// String globalLocId = localLattice.getGlobalLoc();
}
- private void analyzeFieldAccessNode(MethodDescriptor md, SymbolTable nametable, FieldAccessNode en) {
- // TODO Auto-generated method stub
+ private NTuple<Descriptor> analyzeFlowFieldAccessNode(MethodDescriptor md, SymbolTable nametable,
+ FieldAccessNode fan, NodeTupleSet nodeSet, NTuple<Descriptor> base,
+ NodeTupleSet implicitFlowTupleSet) {
+
+ ExpressionNode left = fan.getExpression();
+ TypeDescriptor ltd = left.getType();
+ FieldDescriptor fd = fan.getField();
+
+ String varName = null;
+ if (left.kind() == Kind.NameNode) {
+ NameDescriptor nd = ((NameNode) left).getName();
+ varName = nd.toString();
+ }
+
+ if (ltd.isClassNameRef() || (varName != null && varName.equals("this"))) {
+ // using a class name directly or access using this
+ if (fd.isStatic() && fd.isFinal()) {
+ // loc.addLocation(Location.createTopLocation(md));
+ // return loc;
+ }
+ }
+
+ // if (left instanceof ArrayAccessNode) {
+ // ArrayAccessNode aan = (ArrayAccessNode) left;
+ // left = aan.getExpression();
+ // }
+ // fanNodeSet
+ base = analyzeFlowExpressionNode(md, nametable, left, nodeSet, base, implicitFlowTupleSet);
+
+ if (!left.getType().isPrimitive()) {
+
+ if (fd.getSymbol().equals("length")) {
+ // TODO
+ // array.length access, return the location of the array
+ // return loc;
+ }
+
+ base.add(fd);
+ }
+
+ return base;
}
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();
boolean postinc = true;
if (an.getOperation().getBaseOp() == null
// if LHS is array access node, need to capture value flows between an array
// and its index value
- analyzeFlowExpressionNode(md, nametable, an.getDest(), base);
+ 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
- NTuple<Descriptor> rhsDescTuple =
- analyzeFlowExpressionNode(md, nametable, an.getSrc(), new NTuple<Descriptor>());
+ analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null, implicitFlowTupleSet);
+ System.out.println("ASSIGNMENT NODE nodeSetRHS=" + nodeSetRHS);
+
+ // creates edges from RHS to LHS
+ for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.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 {
+ // 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
- // src & dest are same
+ for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
+ NTuple<Descriptor> tuple = iter2.next();
+ addFlowGraphEdge(md, tuple, tuple);
+ }
}
return mapMethodDescriptorToFlowGraph.get(md);
}
+ public void addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from, NTuple<Descriptor> to) {
+ FlowGraph graph = getFlowGraph(md);
+ graph.addValueFlowEdge(from, to);
+ }
+
+ public void _debug_printGraph() {
+ Set<MethodDescriptor> keySet = mapMethodDescriptorToFlowGraph.keySet();
+
+ for (Iterator<MethodDescriptor> iterator = keySet.iterator(); iterator.hasNext();) {
+ MethodDescriptor md = (MethodDescriptor) iterator.next();
+ FlowGraph fg = mapMethodDescriptorToFlowGraph.get(md);
+ try {
+ fg.writeGraph();
+ } catch (IOException e) {
+ e.printStackTrace();
+ }
+ }
+
+ }
+
}
projects / IRC.git / blobdiff