package tfm.graphs; import com.github.javaparser.ast.stmt.EmptyStmt; import com.github.javaparser.ast.stmt.Statement; import edg.graphlib.Arrow; import tfm.arcs.Arc; import tfm.arcs.pdg.ControlDependencyArc; import tfm.arcs.pdg.DataDependencyArc; import tfm.nodes.Node; import tfm.nodes.PDGNode; import tfm.slicing.SlicingCriterion; import tfm.utils.Logger; import tfm.utils.NodeNotFoundException; import tfm.visitors.PDGCFGVisitor; import java.util.Comparator; import java.util.HashSet; import java.util.Optional; import java.util.Set; import java.util.stream.Collectors; public class PDGGraph extends Graph { private CFGGraph cfgGraph; public PDGGraph() { setRootVertex(new PDGNode(getNextVertexId(), getRootNodeData(), new EmptyStmt())); } public PDGGraph(CFGGraph cfgGraph) { this(); this.cfgGraph = cfgGraph; } protected String getRootNodeData() { return "Entry"; } public PDGNode addNode(PDGNode node) { PDGNode vertex = new PDGNode(node); super.addVertex(vertex); return vertex; } @Override public PDGNode addNode(String instruction, Statement statement) { return addNode(getNextVertexId(), instruction, statement); } public PDGNode addNode(int id, String instruction, Statement statement) { PDGNode vertex = new PDGNode(id, instruction, statement); super.addVertex(vertex); return vertex; } @SuppressWarnings("unchecked") private void addArc(Arc arc) { super.addEdge(arc); } public void addControlDependencyArc(PDGNode from, PDGNode to) { ControlDependencyArc controlDependencyArc = new ControlDependencyArc(from, to); this.addArc(controlDependencyArc); } public void addDataDependencyArc(PDGNode from, PDGNode to, String variable) { DataDependencyArc dataDataDependencyArc = new DataDependencyArc(from, to, variable); this.addArc(dataDataDependencyArc); } public Set getNodesAtLevel(int level) { return getVerticies().stream() .map(vertex -> (PDGNode) vertex) .filter(node -> node.getLevel() == level) .collect(Collectors.toSet()); } public int getLevels() { return getVerticies().stream() .map(vertex -> (PDGNode) vertex) .max(Comparator.comparingInt(PDGNode::getLevel)) .map(PDGNode::getLevel) .get() + 1; } public void setCfgGraph(CFGGraph cfgGraph) { this.cfgGraph = cfgGraph; } @Override public String toGraphvizRepresentation() { String lineSep = System.lineSeparator(); String nodesDeclaration = getNodes().stream() .sorted(Comparator.comparingInt(Node::getId)) .map(Node::toGraphvizRepresentation) .collect(Collectors.joining(lineSep)); StringBuilder rankedNodes = new StringBuilder(); // No level 0 is needed (only one node) for (int i = 0; i < getLevels(); i++) { Set levelNodes = getNodesAtLevel(i); if (levelNodes.size() <= 1) { continue; } // rank same rankedNodes.append("{ rank = same; ") .append(levelNodes.stream() .map(node -> String.valueOf(node.getId())) .collect(Collectors.joining(";"))) .append(" }") .append(lineSep); // invisible arrows for ordering rankedNodes.append(levelNodes.stream() .sorted(Comparator.comparingInt(PDGNode::getId)) .map(node -> String.valueOf(node.getId())) .collect(Collectors.joining(" -> "))) .append("[style = invis];") .append(lineSep); } String arrows = getArcs().stream() .sorted(Comparator.comparingInt(arrow -> ((Node) arrow.getFrom()).getId())) .map(Arc::toGraphvizRepresentation) .collect(Collectors.joining(lineSep)); return "digraph g{" + lineSep + "splines=true;" + lineSep + nodesDeclaration + lineSep + arrows + lineSep + rankedNodes.toString() + "}"; } @Override public PDGGraph slice(SlicingCriterion slicingCriterion) { Optional optionalPDGNode = slicingCriterion.findNode(this); if (!optionalPDGNode.isPresent()) { throw new NodeNotFoundException(slicingCriterion); } PDGNode node = optionalPDGNode.get(); Logger.format("Slicing node: %s", node); Set sliceNodes = getSliceNodes(new HashSet<>(), node); PDGGraph sliceGraph = new PDGGraph(); com.github.javaparser.ast.Node astCopy = node.getAstNode().findRootNode().clone(); astCopy.accept(new PDGCFGVisitor(sliceGraph), sliceGraph.getRootNode()); for (PDGNode sliceNode : sliceGraph.getNodes()) { if (!sliceNodes.contains(sliceNode.getId())) { Logger.log("Removing node " + sliceNode.getId()); sliceNode.getAstNode().removeForced(); sliceGraph.removeNode(sliceNode); } } // for (Arc arc : getArcs()) { // Optional fromOptional = sliceGraph.findNodeById(arc.getFromNode().getId()); // Optional toOptional = sliceGraph.findNodeById(arc.getToNode().getId()); // // if (fromOptional.isPresent() && toOptional.isPresent()) { // PDGNode from = fromOptional.get(); // PDGNode to = toOptional.get(); // // if (arc.isControlDependencyArrow()) { // sliceGraph.addControlDependencyArc(from, to); // } else { // DataDependencyArc dataDependencyArc = (DataDependencyArc) arc; // sliceGraph.addDataDependencyArc(from, to, dataDependencyArc.getData().getVariables().get(0)); // } // } // } return sliceGraph; } private Set getSliceNodes(Set visited, PDGNode root) { visited.add(root.getId()); // Set searchVariables = new HashSet<>(variables); for (Arrow arrow : root.getIncomingArrows()) { Arc arc = (Arc) arrow; // if (arc.isDataDependencyArrow() // && Collections.disjoint(((DataDependencyArc) arc).getData().getVariables(), searchVariables)) { // continue; // } PDGNode from = (PDGNode) arc.getFromNode(); // Logger.log("Arrow from node: " + from); if (visited.contains(from.getId())) { // Logger.log("It's already visited. Continuing..."); continue; } getSliceNodes(visited, from); } // Logger.format("Done with node %s", root.getId()); return visited; } public CFGGraph getCfgGraph() { return cfgGraph; } }